Loading article…
シーム カービング(またはリキッド リスケーリング) は、三菱電機研究所(MERL)の Shai Avidan 氏と、学際研究センターおよび MERLのAriel Shamir 氏によって開発された、コンテンツ認識型画像サイズ変更アルゴリズムです。このアルゴリズムは、画像内にいくつかのシーム(重要度の最も低いパス) を確立し、自動的にシームを削除して画像サイズを縮小したり、シームを挿入して画像サイズを拡張したりすることによって機能します。シーム カービングでは、ピクセルを変更できない領域を手動で定義したり、写真からオブジェクト全体を削除したりすることもできます。
このアルゴリズムの目的は画像の再ターゲティングであり、これはページレイアウトやテキストの動的な変更はサポートしているが画像はサポートしていないHTMLなどの文書標準を使用して、さまざまなサイズのメディア（携帯電話、プロジェクタースクリーン）に歪みなく画像を表示するという問題である。[1]
イメージリターゲティングは、2005年にVidya Setlur、Saeko Takage、Ramesh Raskar、Michael Gleicher、Bruce Goochによって発明されました。[2] Setlurらによる研究は、2015年に10年インパクト賞を受賞しました[どこで? ]。
縫い目
継ぎ目は垂直または水平のいずれかになります。垂直の継ぎ目は、画像内のピクセルが上から下へ、各行に 1 つのピクセルが接続されたパスです。[1]水平の継ぎ目は、接続が左から右であることを除いて同様です。重要度/エネルギー関数は、隣接するピクセルとのコントラストを測定することでピクセルを評価します。
プロセス
以下の例は、継ぎ目の彫刻のプロセスについて説明しています。
削除する継ぎ目は、縮小したい次元（高さまたは幅）によってのみ異なります。また、ステップ 4 を逆にして、低エネルギーの継ぎ目をコピーし、そのピクセルを隣接するピクセルと平均化することで、アルゴリズムを 1 次元で拡大することも可能です。[1]
コンピューティングの継ぎ目
継ぎ目の計算は、画像の端から端までのエネルギーコストが最小の経路を見つけることから成ります。これは、ダイクストラのアルゴリズム、動的計画法、貪欲アルゴリズム、グラフカットなどによって行うことができます。[1]
動的プログラミング
動的プログラミングは、より複雑な結果の計算を簡素化するために、サブ計算の結果を保存するプログラミング方法です。動的プログラミングは、シームを計算するために使用できます。最も低いエネルギーの垂直シーム (パス) を計算する場合、行内の各ピクセルについて、現在のピクセルのエネルギーと、その上にある 3 つのピクセルのいずれかのエネルギーを計算します。
以下の画像は、1つの最適な継ぎ目を計算するDPプロセスを示しています。[1]各四角形はピクセルを表し、左上の赤い値はそのピクセルのエネルギー値を表します。黒の値は、そのピクセルに至るまでのエネルギーの累積合計を表します。
-
一番上の行には上に何もないので、エネルギーはソース画像と同じです。 -
残りの行の各ピクセルのエネルギーは、そのピクセル自体のエネルギーに上記の 3 つのエネルギーの最小値を加えたものになります。一番下に達するまで繰り返します。 -
最後に残ったエネルギーを最小値に戻し、最小限のエネルギーで継ぎ目を回復します。
エネルギー計算は、単純な関数であれば簡単に並列化できます。DP 配列の計算も、プロセス間通信によって並列化できます。ただし、複数のシームを同時に作成するという問題は、2 つの理由から困難です。正確性を保つために、各削除ごとにエネルギーを再生成する必要があり、複数のシームを単純にトレースすると重複が生じる可能性があります。Avidan 2007 は、各シームを繰り返し削除し、生成されたすべてのシームを記録する「インデックス マップ」を保存することで、すべてのシームを計算します。マップには、画像の各ピクセルの「n 番目のシーム」番号が保持され、後でサイズ調整に使用できます。[1]
しかし、両方の問題を無視すれば、平行シームカービングの貪欲近似が可能です。これを行うには、一方の端の最小エネルギーピクセルから始めて、もう一方の端まで最小エネルギーパスを選択し続けます。使用されたピクセルはマークされ、再度選択されません。[3]良好な近似のために、画像のより小さな部分に対して並列にローカルシームを計算することもできます。[4]
問題
- アルゴリズムは、エラーを減らすためにユーザーが提供する情報を必要とする場合があります。これには、保存する領域をペイントすることが含まれます。人間の顔では、顔検出を使用できます。
- 時々、アルゴリズムは、低エネルギーのシームを削除することで、意図せず高エネルギーのシームを作成してしまうことがあります。これを解決するには、シームの削除をシミュレートし、エネルギーデルタをチェックしてエネルギーが増加するかどうかを確認します（順方向エネルギー）。増加する場合は、代わりに他のシームを優先します。[5]
実装
Adobe SystemsはMERLからシームカービング技術の非独占的ライセンスを取得し[6] 、 Photoshop CS4の機能として実装しました。これはContent Aware Scalingと呼ばれています[7] 。 ライセンスは非独占的であるため、他の一般的なコンピュータグラフィックスアプリケーション（GIMP、digiKam、ImageMagickなど）やいくつかのスタンドアロンプログラム（iResizerなど）[8]にもこの技術が実装されており、その一部は無料のオープンソースソフトウェアとしてリリースされています。[9] [10] [11]
改善と拡張
- 2D（時間+1D）シームを導入することでエネルギー機能が向上し、ビデオへの応用が可能になりました。[5]
- GPUでの実装が高速化。[4]
- この順方向エネルギー関数を静止画像に適用する。[12]
- マルチオペレータ：切り抜きとスケーリングを組み合わせる。[13]
- 複数の継ぎ目の除去がはるかに高速化[14]
2010年に行われた8つの画像リターゲティング手法のレビューでは、シームカービングはテストされたアルゴリズムの中で最悪の結果を生み出すことが判明しました。しかし、これは最も高い評価を受けたアルゴリズムの1つ、すなわち前述のマルチオペレータ拡張（クロッピングとスケーリングを組み合わせたもの）の一部でした。[15]
参照
参考文献
- ^ abcdefg Avidan, Shai; Shamir, Ariel (2007 年 7 月)。「コンテンツを考慮した画像サイズ変更のため のシーム カービング」。ACM SIGGRAPH 2007 論文。p. 10。doi : 10.1145 / 1275808.1276390。ISBN 978-1-4503-7836-9。
- ^ Vidya Setlur、Saeko Takage、Ramesh Raskar、Michael Gleicher、Bruce Gooch (2005 年 12 月)。「自動画像リターゲティング」。モバイルおよびユビキタス マルチメディアに関する第 4 回国際会議 MUM '05 の議事録。pp . 59–68。doi : 10.1145 / 1149488.1149499。ISBN 0-473-10658-2。
- ^ ビスト;パラコーデ（2016）。 「パラレルシームカービング」。www.andrew.cmu.edu。
- ^ ab Chen-Kuo Chiang、Shu-Fan Wang、Yi-Ling Chen、Shang-Hong Lai (2009 年 11 月)。「リアルタイム ビデオ リターゲティングのための GPU アクセラレーションによる高速 JND ベース ビデオ カービング」。IEEE Transactions on Circuits and Systems for Video Technology。19 (11): 1588–1597。doi : 10.1109 /TCSVT.2009.2031462。S2CID 15124131 。
- ^ ab ビデオリターゲティングのための改良されたシームカービング。Michael Rubinstein、Ariel Shamir、Shai Avidan。SIGGRAPH 2008。
- ^ 三菱電機プレスリリース、Business Wire、2008年12月16日。
- ^ Adobe Photoshop CS4 の新機能リスト。
- ^ iResizer Teorex によるコンテンツ認識画像サイズ変更ソフトウェア
- ^ Liquid Rescale、 GIMP用のシームカービングプラグイン
- ^ digiKamへの掲載のお知らせ
- ^ ImageMagickにシームカービング機能が搭載されました
- ^ 「前進エネルギーによる縫い目の彫刻の改善」。
- ^ マルチオペレータメディアリターゲティング。Michael Rubinstein、Ariel Shamir、Shai Avidan。SIGGRAPH 2009。
- ^ リアルタイムのコンテンツ認識画像サイズ変更 Science in China Series F: Information Sciences、2009 SCIENCE IN CHINA PRESS。2011年7月7日アーカイブ、Wayback Machine
- ^ Rubinstein, Michael; Gutierrez, Diego; Sorkine, Olga; Shamir, Ariel (2010). 「イメージリターゲティングの比較研究」(PDF) . ACM Transactions on Graphics . 29 (5): 1–10. doi :10.1145/1882261.1866186.RetargetMe ベンチマークも参照してください。
外部リンク
- 縫い目彫刻のインタラクティブデモ
- シームカービングのデモンストレーションビデオ:
- YouTubeで
- 学際センターのウェブサイトのアリエル・シャミールのページ（高解像度）
- ImageMagick のWeb サイトにおけるシーム カービング (Liquid リスケーリング) の説明
- シームカービングの実装チュートリアル
- HitPaw ビデオオブジェクト除去