UberのソフトウェアエンジニアであるOleksii Trekhleb氏は、最近、動的計画法を使って、CPUを消費するコンテンツ・アウェアな画像サイズ変更アルゴリズムを高速化する方法を検討した。開発者は、コンテンツ・アウェアなサイズ変更を使って、画像のキーとなる特徴を維持しながら、画像をさまざまな含みを持つコンテキスト(画面のフォームファクタ、レスポンシブレイアウトコンテナなど)にフィットさせることができる。
コンテンツ・アウェアな画像サイズ変更のためのSeam Carvingというタイトルの論文では、コンテンツ・アウェアな画像サイズ変更の背後にある動機について次のように説明している。
今日のディスプレイデバイスの多様性と多用途性は、デジタルメディアに新たな要求を課しています。 […] HTMLは、ページレイアウトとテキストの動的な変更をサポートします。それにもかかわらず、[…画像]は通常、サイズが固定されたままであり、異なるレイアウトに自動的に合うように形を変えることはできません。[…]携帯電話やPDAなどのさまざまなディスプレイに合うようにするには、そして、特定の用紙サイズや解像度で印刷するようにするには、画像のサイズやアスペクト比を変更する必要があります。 標準の画像スケーリングは十分ではありません。画像の内容を認識せず、通常は一様にしか適用できないためです。トリミングは制限されており、画像の外縁からピクセルの削除しかできません。より効果的なサイズ変更は、幾何学的な制約だけでなく、画像の内容を考慮することによってのみ達成できます。
したがって、コンテンツ・アウェアな画像サイズ変更では、画像の重要な特徴を維持し、歪みなしで画像のサイズ変更(縮小または拡大)できるように努めている。
オリジナルの画像 | 顔検出あり | 顔検出なし |
---|---|---|
(顔の特徴を保持するコンテンツ・アウェアな画像サイズ変更の例。画像ソース。アルゴリズムの実装:Caire。)
前記の画像サンプルは、Caireによって提供されている。CaireはPigo顔検出ライブラリを使用するオープンソースのGoライブラリである。ライブラリの作成者は、サードパーティのモジュールをインストールすることなく、完全なGoソリューションによって高速処理(Goはネイティブコードにコンパイル)が可能になると説明した。
Trekhleb氏は、高速を維持するJavaScript実装を提案した。この実装には、時間の複雑さをO(3^h)
からO(w + h)
に減らす動的計画法のアプローチを使って同じシームカービングアルゴリズムが適用されている。h
とw
はそれぞれ画像の高さと幅である。結果として得られるJS IMAGE CARVER Webアプリでは、現在、ユーザはブラウザで画像を縮小できる(ダウンスケーリング)。
前記のアニメーションは、シームカービングアルゴリズムの基礎を示している。白い線(シーム)は、削除のタグが付けられた画像のピクセルの集合である。オリジナルの論文で、アルゴリズムについて次のように説明されている。
[シームカービングアルゴリズム]は、画像のさまざまな部分にピクセルを体裁良くカービングまたは挿入することにより、画像のサイズを変更する。シームカービングは、ピクセルの重要性を定義するエネルギー関数を使用する。シームは、画像を上から下、あるいは左から右にクロスする低エネルギーピクセルの接続パスである。シームを連続して削除または挿入することにより、画像のサイズを両方向に縮小および拡大できる。画像縮小のために、[…]低エネルギーピクセルをより多く削除し、高エネルギーピクセルをあまり削除しないようにする。
画像サイズ変更アルゴリズムのJavaScript実装をデモするインタラクティブなWebアプリケーションをオンラインで入手できる。興味を持って、技術的な詳細をさらに求める読者は、イラストやコードサンプルがたくさん含まれているオリジナルのブログ記事を参照することを勧める。画像サイズ変更アルゴリズムのCaire Go実装とJavaScript実装はどちらも、MITライセンスの下で配布されているオープンソースプロジェクトである。