画像補正装置および方法
【課題】補正領域を変化させないことによる画質低下を防止する。
【解決手段】画像パターン変形手段１４０は、補正領域の画像を変形させる。境界部補正手段１５０は、その変形ごとに、補正領域とその周辺領域との境界部をグラフカットにより補正する。コスト最小化判定手段１６０は、グラフカットによる補正ごとに、そのグラフカットのコストが最小か否かを判定する。表示手段１７０は、最小と判定されたときの補正領域とその周辺領域の画像を表示する。
【解決手段】画像パターン変形手段１４０は、補正領域の画像を変形させる。境界部補正手段１５０は、その変形ごとに、補正領域とその周辺領域との境界部をグラフカットにより補正する。コスト最小化判定手段１６０は、グラフカットによる補正ごとに、そのグラフカットのコストが最小か否かを判定する。表示手段１７０は、最小と判定されたときの補正領域とその周辺領域の画像を表示する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本発明は、例えば、マルチメディア分野、符号化分野、通信分野において、画像内の一部のパケットロスによる欠落で失われた画像情報を画像処理的に補間することで、元の画像に近い画像を復元することに関係する産業分野に関する。
【背景技術】
【０００２】
マルチメディア分野において、ビデオ会議、符号化、画像生成、画像補間などの急速な進展はインターネットの利便性を高めている。これまで、数多くの画像中の穴領域をfilling-in法（非特許文献１〜３）で補正する研究されてきている。従来法は、１枚の画像中の穴領域（補間されるべき画像領域であり、補正領域という）を埋めるために、基本テクスチャパターンに基づいた方法や拡散系、ナビエ・ストークス方程式に基づいた方法（非特許文献１）、グラフカット（ＧＣ）法（非特許文献２）などを適用する。
【０００３】
しかし、海や雲といったダイナミック・テクスチャや確率的なパターンに隔たりの大きい補正領域が存在する場合には、ほとんどの方法がうまく補正できない。ほとんどの方法は準規則的あるいは規則的なテクスチャをターゲットとしたコピーに基づいたもの（非特許文献３）であり、ダイナミック・テクスチャ向けではなかった。パッチは近傍の画像で埋められるのだが、最終工程まで、この補正領域は、終始変化せず一定のままである。補正領域は周辺の類似テクスチャから合成されていく。そのため、動的な変化があるにも関わらず、補正領域は変化しなかった。また、境界付近から補正領域内部へ段階的に伝播させていく方法が主体だったため、補正領域は、境界から離れて内部に向かうほど不自然になる。特に、大きい補正領域のときほど、補正領域に周期的な模様が生じてしまった。
【非特許文献１】M.Bertalmio, G.Sapiro, V.Caselles, and C.Ballester, "Image inpainting", ACM Proc.SIGGRAPH., pp.417-424, 2000.
【非特許文献２】V.Kwatra, A.Schodl, I.Essa, G.Turk, and A.Bobick, "Graphcut textures, image and video synthesis using graph cut", ACM Proc. SIGGRAPH, 2004.
【非特許文献３】A.Criminisi, P.Perez, and K.Toyama, "Region filling and object removal by exemplar-based image inpainting", IEEE Trans. Image Process, vol.13, no.9, pp.1200-1212, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
第１の課題は、補正領域のテクスチャそのものが変化しない問題を解決することである。第２の課題は、グラフカット法では、補正領域の境界部のみの補正であったことである。第３の課題は、補正領域内の速度変化をもたらす仕組みが必要であったことである。
【課題を解決するための手段】
【０００５】
上記の課題を解決するために、本発明は、補正領域を動的に変化させ、補正領域の境界と周辺を段階的に反復的に補正する仕組みを導入したことを特徴とする。
【発明の効果】
【０００６】
第１の効果は、補正領域内部に向かって生じる周期性が解消し、補正領域内部から周辺までが、違和感のない自然なテクスチャで画像補間できることである。
【０００７】
第二の効果は、補正領域自体を動的に変化させることで、境界部の連続性が高まり、特に、ダイナミック・テクスチャほど、その効果が顕著となることである。
【発明を実施するための最良の形態】
【０００８】
以下、本発明の実施の形態を図面を参照して説明する。
【０００９】
図１は、本実施の形態に係るシステム構成図である。
【００１０】
本システムは、データ入力手段１００、データ蓄積手段１１０、近傍画像抽出手段１２０、重なり補正手段１３０、画像パターン変形手段１４０、境界部補正手段１５０、コスト最小化判定手段１６０および表示手段１７０を備え、これらにより画像補正装置が構成される。
【００１１】
データ入力手段１００は、例えば、カメラ（撮像装置）を介して、河川やダムなどの水面の画像を取り込む。データ蓄積手段１１０は、その時系列の画像のデータを蓄積する。伝送の途中でパケットロスによる画像の一部分の欠落や画像内の不要な物体の部分を消去することなどにより、画像には補正すべき領域（補正領域）が含まれることとなる。
【００１２】
近傍画像抽出手段１２０は、補正領域とその周辺領域において違和感が生じないように画像補間を行う。近傍画像抽出手段１２０は、補正領域の近傍にある近傍画像を抽出し、これを移流方程式と動きベクトルにより補正領域へ重ねるように移動させる。
【００１３】
重なり補正手段１３０は、補正領域内で重なりが生じる領域を連続性をもたせるよに補正する。画像パターン変形手段１４０は、補正領域内部とその周辺のテクスチャが自然な変化を双方で示すように、補正領域の画像を変形させる。画像パターン変形手段１４０は、この変形に移流方程式と動きベクトルを用いる。
【００１４】
境界部補正手段１５０は、その変形ごとに、補正領域とその周辺領域との境界部をグラフカット（ＧＣ：Graph Cut）により補正する。これにより、補正領域とその周辺領域が連続性をもつ。コスト最小化判定手段１６０は、グラフカットによる補正ごとに、そのグラフカットのコストが最小か否かを判定する。表示手段１７０は、最小と判定されたときの補正領域とその周辺領域の画像を表示する。表示手段１７０は、画像の全領域を表示すればよい。
【００１５】
なお、画像パターン変形手段１４０による画像変形のそれぞれは、変形の結果が異なるようなものであればよい。例えば、画像パターン変形手段１４０は、移流方程式と動きベクトルを用いる際のパラメータを異ならせることで変形結果を異ならせればよい。
【００１６】
次に、近傍画像抽出手段１２０が、補正領域の近傍にある近傍画像を補正領域へ重ねるように移動させるとき、ならびに、画像パターン変形手段１４０が、補正領域の画像を変形させるときに使用される移流方程式と動きベクトルについて説明する。
【００１７】
式（１）は移流方程式（ＡＥ）を示す。Ｉi,jnは画素（ｉ，ｊ）、時間ｎにおける画像の輝度である。ｕはオプティカルフロー（動きベクトル）である。オプティカルフローは後述のように与えられるものとする。
【００１８】
式（１）には、必ず初期画像として１枚の画像（情報）が必要とされる。式（１）を時間発展（n step）を計算していくとき、Ｉi,jnはオプティカルフローに沿ってその輝度を変化させることができる。１枚以上の画像を合成していくためには、式（１）の時間ｎと時間ｎ＋１のときの輝度を差し替えていくだけでよい。
【数１】
【００１９】
かかる例に相当する内容が参考文献１の「3 The digital inpainting algorithm」に記載されている。
【００２０】
図２は、パッチのある１枚の画像の例と本システムのアルゴリズムの初期段階について示す。
【００２１】
近傍画像抽出手段１２０は、図２（ａ）に示す画像の画像情報だけに基づいて補間を行う。画像は補正領域（パッチΦ）を含む。ここで、パッチΦの近傍（周辺）にある近傍画像をソースΩと定義する。ソースΩの大きさはパッチΦの大きさと同じにした。ソースΩの数は１０であり、式（１）が１０回用いられる。オプティカルフローの方向ベクトルはΦの中心を向いている。これらは経験的に決定した。
【００２２】
図３は、反復的にパッチ内部と境界とをシームレスにするアルゴリズムについて示す。 図３（ａ）に示すように、ソースΩがパッチΦへ集められたあと、図３（ｂ）に示すように、重なり補正手段１３０は、グラフカット法により、パッチΦ内で重なりが生じる領域を連続性をもたせるように補正する。つまり、該領域をシームレスにする。
【００２３】
パッチΦ内を変化させるときのオプティカルフローの与え方には、いくつか方法がある。１つは、予め用意してある振動ベクトルの時系列データを適用する方法である。時系列データとオプティカルフローと式（１）と初期のパッチを用い、時間変化を計算していけば、パッチのテクスチャは、オプティカルフローに従って振動しながら変化する。
【００２４】
次に、境界部補正手段１５０は、パッチΦとソースΩとの境界部をグラフカット（Graph Cut:GC）により補正する。境界部補正手段１５０は、初期のグラフカットのコストを求めて記憶する。境界部補正手段１５０は、初期のパッチΦのテクスチャを移流方程式とオプティカルフローを適用することで変化させて、グラフカットのコストを計算し記憶する。コスト最小化判定手段１６０は、グラフカットによる補正ごとに、そのグラフカットのコストが最小か否かを判定する。表示手段１７０は、最小と判定されたときのパッチΦとソースΩの画像を表示する。
【００２５】
図３（ｃ）の円Ｃ１、Ｃ２は、それぞれパッチΦの縁部、ソースΩの縁部を明示的に示す。上記の反復過程により、円Ｃ１と円Ｃ２の間の領域が最終的にはシームレスになる。
【００２６】
しかも、パッチΦ内は既に重なり補正手段１３０がシームレスにしているので、ソースΩから、ソースΩとパッチΦの境界部を経て、パッチΦの内部までにおいて、一貫して自然に変化するテクスチャが得られる。
【００２７】
図４は、グラフカットのコストが変化する一例を示す。グラフカットについては、後述する参考文献２が詳しい。
【００２８】
グラフカット法による内部の処理では、組み合わせの最小化問題が解かれる。グラフカット法は、２つの画像の重なりがあったときに、それぞれの画素の輝度（８ビット階調とする）の差が最小になるように、双方の画素が選択される。計算時間は双方の重なる画素の幅によるが、多くの場合、１〜１０画素程度の範囲である。また、ダイナミック・テクスチャであるほど、隣接する輝度の上下幅も広くなり、重なった領域から、それぞれの輝度を選択していくとき、最終的に得られる双方の輝度差がコストである。
【００２９】
そのため、重ねた段階で、双方の画像の輝度が一定のときは、このコストはこれ以上低くなることはない。あくまで、グラフカット法は、与えられた双方の輝度の差が最小になる組み合わせを見出すだけであるが、視覚的にはシームレスに満足のいくものにはなるとは限らない。
【００３０】
そこで、本システムでは、双方の輝度のうち、パッチの周辺は固定であることから、パッチ自身のテクスチャを変化させることで、パッチの輝度を変化させている。これにより、グラフカット法で用いられる重なり領域の輝度が変化することから、コストも変化する。同時に、パッチ内部も変化していく。
【００３１】
図５は、グラフカット法の効果を示す。
【００３２】
図５（ａ）に示すようにテクスチャをもつ画像５０１と５０２があるとする。たとえば、枠で囲んだ領域５０１１と５０２１が重なり領域とする。図５（ｂ）に示すように、処理せずに画像をつなぐとテクスチャが不連続となりシームレスとはならない。境界線５０３がはっきりとみえたままとなる。
【００３３】
しかし、グラフカット法によれば、枠内の画素の差が最小となるコストをみつけると、図５（ｃ）に示す、縦に走る線５０４をみいだせる。この線５０４に沿って、それぞれの枠の画像を断面として、２つの画像を接続すれば、図５（ｄ）に示すシームレスな画像５０５が得られる。
【００３４】
図６は、パッチΦ内部のテクスチャが変化していく様子を示す。本システムでは、上記のように、パッチΦとその周辺の輝度を初期値として与えたときのコストを基準とする。そして、所定の回数（１０回程度）で、グラフカットのコストが最小になる。
【００３５】
なお，パッチ内のテクスチャをどのように動かすかについては、まず、パッチを含む画像に関連する別の時系列画像において、予め、動きベクトルをオプティカルフロー法などで検出しておく。そして、見かけのテクスチャの類似性に基づいて、テクスチャが類似する領域に対応した動きベクトルを取り出し、その動きベクトルを、補正すべき画像のパッチを動かすのに用いればよい。なお、かかる処理はサブブロック単位に行えばよい。
【００３６】
図７は、本システムにおいてグラフカットのコストが最小になったときの図６の点線６０１内の画像を示す。図８は、従来法により補正された図６の点線６０１内の画像を示す。図７の画像の方がシームレスで自然な画像であることは明らかである。つまり、本システムによればシームレスで自然な画像を得ることができる。
【００３７】
グラフカット処理を５×３のネットワーク網を例に説明する。
【００３８】
図９、図１０に示すように、グラフカット処理とは、○で示されたソース（Source）と●で示されたシンク（Sink）のいずれにもまだ分類されていない□で示された９点にソース（○）の値あるいはシンク（●）の値を適用する処理である。
【００３９】
ソース（○）は、補正領域内の点であり、シンク（●）は、補正領域の周辺領域の点である。
【００４０】
５×３のネットワーク網は、１８個の枝を有する。１８個の枝は、横方向の枝と縦方向の枝とからなる。横方向の枝は枝ｒ１ないし枝ｒ１２である。縦方向の枝は枝ｒ１３ないし枝ｒ１８である。
【００４１】
各枝は、一方向に流れが生じる流路と反対方向に流れが生じる流路をもつ。
【００４２】
各流路を流れることができる容量は、ソース（○）の画素値と、シンク（●）の画素値の差により設定する。
【００４３】
図１１には、分類されていない点間の流路であって、矢印で明らかなように左側の点（始点から、右側の点（終点）へ流れる流路が示されているが、この流路の容量Ｃは、式（２）により求まる。
【数２】
【００４４】
ここで、Ｍ、Ｎはそれぞれソース、シンクを示す。添え字ｓ、ｅはそれぞれ流路の始点（start）、終点（end）を示す。また、Ｒ、Ｇ、Ｂはそれぞれ、赤（Red）、緑（Green）、青（Blue）の画素値を示す。例えば、Ｒ（Ｍｓ）は、図１１のソース１１０１の赤の画素値を示す。
【００４５】
式（２）でわかるように、一方向に流れが生じる流路の容量と反対方向に流れが生じる流路の容量は同一である。つまり、容量は流れる方向によらず同一である。
【００４６】
これに対し、ソースまたはシンクから分類されていない点へ流れる流路の容量は無限大と設定する。例えば、図９の枝ｒ１、ｒ５およびｒ９における右方向の流路、ならびに、枝ｒ４、ｒ８およびｒ１２における左方向の流路の容量は無限大である。
【００４７】
また、分類されていない点からソースまたはシンクへ流れる流路の容量は０（零）と設定する。例えば、図９の枝ｒ１、ｒ５およびｒ９における左方向の流路、ならびに、枝ｒ４、ｒ８およびｒ１２における右方向の流路の容量は無限大である。
【００４８】
本システムでは、ソースからシンクへと少しずつ流していき、もうこれ以上ソースからシンクへ流すことができなくなった状態で、容量が最小となる流路の位置の左右で区分けを行う。
【００４９】
ここで、Ｒの輝度だけを考え、図９の□で示した点の数を減らし、グラフカットの経過を例で示す。かかる例に相当する内容が参考文献２の「3 Patch Fitting using Graph Cut」に記載されている。
【００５０】
図１２（ａ）には、□で示した点が６点あり、各点にはソースの画素値が示されている。なお、６点の左側にはソース、右側にはシンクがあることとする。
【００５１】
図１２（ｂ）は、当該６点と各点におけるシンクの画素値を示している。
【００５２】
図１２（ｃ）は、式（２）の第１項および第４項に相当する値を□内に示している。また、同図は、この値から求まる２点間の流路の容量を示している。容量は流れる方向によらず同一なのでその同一の容量を示している。
【００５３】
これに加え、図１２（ｄ）は、グラフカットのラインを示している。ラインの左では、□で示した点にソースの輝度が設定される。一方、ラインの右では、□で示した点にシンクの輝度が設定される。したがい、グラフカットのラインは、□で示した点の領域をソース側とシンク側とに分けるものとなる。また、グラフカットのラインは複数の流路を横切るものとなる。ラインに横切られた流路の容量の合計が、グラフカットのコストである。同図の例では、グラフカットのコストは、５＋５＋２＝１２であり、最小となっている。
【００５４】
本システムは、このグラフカットのコストが最小と判定されたときの補正領域とその周辺領域の画像を表示するのである。
【００５５】
なお、本システムにおける画像補正方法をコンピュータに実行させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に格納し、陳列などして流通させたり、当該コンピュータプログラムをインターネットなどの通信網を介して伝送させてもよい。
【００５６】
（参考文献１）
M.Bertalmio, G.Sapiro, V.Caselles, and C.Ballester, "Image inpainting", ACM Proc.SIGGRAPH., pp.417-424, 2000.
（参考文献２）
V.Kwatra, A.Schodl, I.Essa, G.Turk, and A.Bobick, "Graphcut textures, image and video synthesis using graph cut", ACM Proc. SIGGRAPH, 2004.
【図面の簡単な説明】
【００５７】
【図１】図１は、本実施の形態に係るシステム構成図である。
【図２】図２ｈ、パッチのある１枚のテクスチャ画像の例と本システムのアルゴリズムの初期段階について示す。
【図３】図３は、反復的にパッチ内部と境界とをシームレスにするアルゴリズムについて示す。
【図４】図４は、グラフカットのコストが変化する一例を示す。
【図５】図５は、グラフカット法の効果を示す。
【図６】図６は、パッチΦ内部のテクスチャが変化していく様子を示す。
【図７】図７は、本システムにおいてグラフカットのコストが最小になったときの画像を示す。
【図８】図８は、従来法により補正された画像を示す。
【図９】図９は、グラフカット処理の説明に用いたネットワーク網を示す。
【図１０】図１０は、図９の□で示された９点にソースの値あるいはシンクの値を適用することを示す。
【図１１】図１１は、図９の□で示された２点間の流路を示す。
【図１２】図１２は、グラフカット処理の経過を例で示す。
【符号の説明】
【００５８】
１００ データ入力手段
１１０ データ蓄積手段
１２０ 近傍画像抽出手段
１３０ 重なり補正手段
１４０ 画像パターン変形手段
１５０ 境界部補正手段
１６０ コスト最小化判定手段
１７０ 表示手段
【技術分野】
【０００１】
本発明は、本発明は、例えば、マルチメディア分野、符号化分野、通信分野において、画像内の一部のパケットロスによる欠落で失われた画像情報を画像処理的に補間することで、元の画像に近い画像を復元することに関係する産業分野に関する。
【背景技術】
【０００２】
マルチメディア分野において、ビデオ会議、符号化、画像生成、画像補間などの急速な進展はインターネットの利便性を高めている。これまで、数多くの画像中の穴領域をfilling-in法（非特許文献１〜３）で補正する研究されてきている。従来法は、１枚の画像中の穴領域（補間されるべき画像領域であり、補正領域という）を埋めるために、基本テクスチャパターンに基づいた方法や拡散系、ナビエ・ストークス方程式に基づいた方法（非特許文献１）、グラフカット（ＧＣ）法（非特許文献２）などを適用する。
【０００３】
しかし、海や雲といったダイナミック・テクスチャや確率的なパターンに隔たりの大きい補正領域が存在する場合には、ほとんどの方法がうまく補正できない。ほとんどの方法は準規則的あるいは規則的なテクスチャをターゲットとしたコピーに基づいたもの（非特許文献３）であり、ダイナミック・テクスチャ向けではなかった。パッチは近傍の画像で埋められるのだが、最終工程まで、この補正領域は、終始変化せず一定のままである。補正領域は周辺の類似テクスチャから合成されていく。そのため、動的な変化があるにも関わらず、補正領域は変化しなかった。また、境界付近から補正領域内部へ段階的に伝播させていく方法が主体だったため、補正領域は、境界から離れて内部に向かうほど不自然になる。特に、大きい補正領域のときほど、補正領域に周期的な模様が生じてしまった。
【非特許文献１】M.Bertalmio, G.Sapiro, V.Caselles, and C.Ballester, "Image inpainting", ACM Proc.SIGGRAPH., pp.417-424, 2000.
【非特許文献２】V.Kwatra, A.Schodl, I.Essa, G.Turk, and A.Bobick, "Graphcut textures, image and video synthesis using graph cut", ACM Proc. SIGGRAPH, 2004.
【非特許文献３】A.Criminisi, P.Perez, and K.Toyama, "Region filling and object removal by exemplar-based image inpainting", IEEE Trans. Image Process, vol.13, no.9, pp.1200-1212, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
第１の課題は、補正領域のテクスチャそのものが変化しない問題を解決することである。第２の課題は、グラフカット法では、補正領域の境界部のみの補正であったことである。第３の課題は、補正領域内の速度変化をもたらす仕組みが必要であったことである。
【課題を解決するための手段】
【０００５】
上記の課題を解決するために、本発明は、補正領域を動的に変化させ、補正領域の境界と周辺を段階的に反復的に補正する仕組みを導入したことを特徴とする。
【発明の効果】
【０００６】
第１の効果は、補正領域内部に向かって生じる周期性が解消し、補正領域内部から周辺までが、違和感のない自然なテクスチャで画像補間できることである。
【０００７】
第二の効果は、補正領域自体を動的に変化させることで、境界部の連続性が高まり、特に、ダイナミック・テクスチャほど、その効果が顕著となることである。
【発明を実施するための最良の形態】
【０００８】
以下、本発明の実施の形態を図面を参照して説明する。
【０００９】
図１は、本実施の形態に係るシステム構成図である。
【００１０】
本システムは、データ入力手段１００、データ蓄積手段１１０、近傍画像抽出手段１２０、重なり補正手段１３０、画像パターン変形手段１４０、境界部補正手段１５０、コスト最小化判定手段１６０および表示手段１７０を備え、これらにより画像補正装置が構成される。
【００１１】
データ入力手段１００は、例えば、カメラ（撮像装置）を介して、河川やダムなどの水面の画像を取り込む。データ蓄積手段１１０は、その時系列の画像のデータを蓄積する。伝送の途中でパケットロスによる画像の一部分の欠落や画像内の不要な物体の部分を消去することなどにより、画像には補正すべき領域（補正領域）が含まれることとなる。
【００１２】
近傍画像抽出手段１２０は、補正領域とその周辺領域において違和感が生じないように画像補間を行う。近傍画像抽出手段１２０は、補正領域の近傍にある近傍画像を抽出し、これを移流方程式と動きベクトルにより補正領域へ重ねるように移動させる。
【００１３】
重なり補正手段１３０は、補正領域内で重なりが生じる領域を連続性をもたせるよに補正する。画像パターン変形手段１４０は、補正領域内部とその周辺のテクスチャが自然な変化を双方で示すように、補正領域の画像を変形させる。画像パターン変形手段１４０は、この変形に移流方程式と動きベクトルを用いる。
【００１４】
境界部補正手段１５０は、その変形ごとに、補正領域とその周辺領域との境界部をグラフカット（ＧＣ：Graph Cut）により補正する。これにより、補正領域とその周辺領域が連続性をもつ。コスト最小化判定手段１６０は、グラフカットによる補正ごとに、そのグラフカットのコストが最小か否かを判定する。表示手段１７０は、最小と判定されたときの補正領域とその周辺領域の画像を表示する。表示手段１７０は、画像の全領域を表示すればよい。
【００１５】
なお、画像パターン変形手段１４０による画像変形のそれぞれは、変形の結果が異なるようなものであればよい。例えば、画像パターン変形手段１４０は、移流方程式と動きベクトルを用いる際のパラメータを異ならせることで変形結果を異ならせればよい。
【００１６】
次に、近傍画像抽出手段１２０が、補正領域の近傍にある近傍画像を補正領域へ重ねるように移動させるとき、ならびに、画像パターン変形手段１４０が、補正領域の画像を変形させるときに使用される移流方程式と動きベクトルについて説明する。
【００１７】
式（１）は移流方程式（ＡＥ）を示す。Ｉi,jnは画素（ｉ，ｊ）、時間ｎにおける画像の輝度である。ｕはオプティカルフロー（動きベクトル）である。オプティカルフローは後述のように与えられるものとする。
【００１８】
式（１）には、必ず初期画像として１枚の画像（情報）が必要とされる。式（１）を時間発展（n step）を計算していくとき、Ｉi,jnはオプティカルフローに沿ってその輝度を変化させることができる。１枚以上の画像を合成していくためには、式（１）の時間ｎと時間ｎ＋１のときの輝度を差し替えていくだけでよい。
【数１】
【００１９】
かかる例に相当する内容が参考文献１の「3 The digital inpainting algorithm」に記載されている。
【００２０】
図２は、パッチのある１枚の画像の例と本システムのアルゴリズムの初期段階について示す。
【００２１】
近傍画像抽出手段１２０は、図２（ａ）に示す画像の画像情報だけに基づいて補間を行う。画像は補正領域（パッチΦ）を含む。ここで、パッチΦの近傍（周辺）にある近傍画像をソースΩと定義する。ソースΩの大きさはパッチΦの大きさと同じにした。ソースΩの数は１０であり、式（１）が１０回用いられる。オプティカルフローの方向ベクトルはΦの中心を向いている。これらは経験的に決定した。
【００２２】
図３は、反復的にパッチ内部と境界とをシームレスにするアルゴリズムについて示す。 図３（ａ）に示すように、ソースΩがパッチΦへ集められたあと、図３（ｂ）に示すように、重なり補正手段１３０は、グラフカット法により、パッチΦ内で重なりが生じる領域を連続性をもたせるように補正する。つまり、該領域をシームレスにする。
【００２３】
パッチΦ内を変化させるときのオプティカルフローの与え方には、いくつか方法がある。１つは、予め用意してある振動ベクトルの時系列データを適用する方法である。時系列データとオプティカルフローと式（１）と初期のパッチを用い、時間変化を計算していけば、パッチのテクスチャは、オプティカルフローに従って振動しながら変化する。
【００２４】
次に、境界部補正手段１５０は、パッチΦとソースΩとの境界部をグラフカット（Graph Cut:GC）により補正する。境界部補正手段１５０は、初期のグラフカットのコストを求めて記憶する。境界部補正手段１５０は、初期のパッチΦのテクスチャを移流方程式とオプティカルフローを適用することで変化させて、グラフカットのコストを計算し記憶する。コスト最小化判定手段１６０は、グラフカットによる補正ごとに、そのグラフカットのコストが最小か否かを判定する。表示手段１７０は、最小と判定されたときのパッチΦとソースΩの画像を表示する。
【００２５】
図３（ｃ）の円Ｃ１、Ｃ２は、それぞれパッチΦの縁部、ソースΩの縁部を明示的に示す。上記の反復過程により、円Ｃ１と円Ｃ２の間の領域が最終的にはシームレスになる。
【００２６】
しかも、パッチΦ内は既に重なり補正手段１３０がシームレスにしているので、ソースΩから、ソースΩとパッチΦの境界部を経て、パッチΦの内部までにおいて、一貫して自然に変化するテクスチャが得られる。
【００２７】
図４は、グラフカットのコストが変化する一例を示す。グラフカットについては、後述する参考文献２が詳しい。
【００２８】
グラフカット法による内部の処理では、組み合わせの最小化問題が解かれる。グラフカット法は、２つの画像の重なりがあったときに、それぞれの画素の輝度（８ビット階調とする）の差が最小になるように、双方の画素が選択される。計算時間は双方の重なる画素の幅によるが、多くの場合、１〜１０画素程度の範囲である。また、ダイナミック・テクスチャであるほど、隣接する輝度の上下幅も広くなり、重なった領域から、それぞれの輝度を選択していくとき、最終的に得られる双方の輝度差がコストである。
【００２９】
そのため、重ねた段階で、双方の画像の輝度が一定のときは、このコストはこれ以上低くなることはない。あくまで、グラフカット法は、与えられた双方の輝度の差が最小になる組み合わせを見出すだけであるが、視覚的にはシームレスに満足のいくものにはなるとは限らない。
【００３０】
そこで、本システムでは、双方の輝度のうち、パッチの周辺は固定であることから、パッチ自身のテクスチャを変化させることで、パッチの輝度を変化させている。これにより、グラフカット法で用いられる重なり領域の輝度が変化することから、コストも変化する。同時に、パッチ内部も変化していく。
【００３１】
図５は、グラフカット法の効果を示す。
【００３２】
図５（ａ）に示すようにテクスチャをもつ画像５０１と５０２があるとする。たとえば、枠で囲んだ領域５０１１と５０２１が重なり領域とする。図５（ｂ）に示すように、処理せずに画像をつなぐとテクスチャが不連続となりシームレスとはならない。境界線５０３がはっきりとみえたままとなる。
【００３３】
しかし、グラフカット法によれば、枠内の画素の差が最小となるコストをみつけると、図５（ｃ）に示す、縦に走る線５０４をみいだせる。この線５０４に沿って、それぞれの枠の画像を断面として、２つの画像を接続すれば、図５（ｄ）に示すシームレスな画像５０５が得られる。
【００３４】
図６は、パッチΦ内部のテクスチャが変化していく様子を示す。本システムでは、上記のように、パッチΦとその周辺の輝度を初期値として与えたときのコストを基準とする。そして、所定の回数（１０回程度）で、グラフカットのコストが最小になる。
【００３５】
なお，パッチ内のテクスチャをどのように動かすかについては、まず、パッチを含む画像に関連する別の時系列画像において、予め、動きベクトルをオプティカルフロー法などで検出しておく。そして、見かけのテクスチャの類似性に基づいて、テクスチャが類似する領域に対応した動きベクトルを取り出し、その動きベクトルを、補正すべき画像のパッチを動かすのに用いればよい。なお、かかる処理はサブブロック単位に行えばよい。
【００３６】
図７は、本システムにおいてグラフカットのコストが最小になったときの図６の点線６０１内の画像を示す。図８は、従来法により補正された図６の点線６０１内の画像を示す。図７の画像の方がシームレスで自然な画像であることは明らかである。つまり、本システムによればシームレスで自然な画像を得ることができる。
【００３７】
グラフカット処理を５×３のネットワーク網を例に説明する。
【００３８】
図９、図１０に示すように、グラフカット処理とは、○で示されたソース（Source）と●で示されたシンク（Sink）のいずれにもまだ分類されていない□で示された９点にソース（○）の値あるいはシンク（●）の値を適用する処理である。
【００３９】
ソース（○）は、補正領域内の点であり、シンク（●）は、補正領域の周辺領域の点である。
【００４０】
５×３のネットワーク網は、１８個の枝を有する。１８個の枝は、横方向の枝と縦方向の枝とからなる。横方向の枝は枝ｒ１ないし枝ｒ１２である。縦方向の枝は枝ｒ１３ないし枝ｒ１８である。
【００４１】
各枝は、一方向に流れが生じる流路と反対方向に流れが生じる流路をもつ。
【００４２】
各流路を流れることができる容量は、ソース（○）の画素値と、シンク（●）の画素値の差により設定する。
【００４３】
図１１には、分類されていない点間の流路であって、矢印で明らかなように左側の点（始点から、右側の点（終点）へ流れる流路が示されているが、この流路の容量Ｃは、式（２）により求まる。
【数２】
【００４４】
ここで、Ｍ、Ｎはそれぞれソース、シンクを示す。添え字ｓ、ｅはそれぞれ流路の始点（start）、終点（end）を示す。また、Ｒ、Ｇ、Ｂはそれぞれ、赤（Red）、緑（Green）、青（Blue）の画素値を示す。例えば、Ｒ（Ｍｓ）は、図１１のソース１１０１の赤の画素値を示す。
【００４５】
式（２）でわかるように、一方向に流れが生じる流路の容量と反対方向に流れが生じる流路の容量は同一である。つまり、容量は流れる方向によらず同一である。
【００４６】
これに対し、ソースまたはシンクから分類されていない点へ流れる流路の容量は無限大と設定する。例えば、図９の枝ｒ１、ｒ５およびｒ９における右方向の流路、ならびに、枝ｒ４、ｒ８およびｒ１２における左方向の流路の容量は無限大である。
【００４７】
また、分類されていない点からソースまたはシンクへ流れる流路の容量は０（零）と設定する。例えば、図９の枝ｒ１、ｒ５およびｒ９における左方向の流路、ならびに、枝ｒ４、ｒ８およびｒ１２における右方向の流路の容量は無限大である。
【００４８】
本システムでは、ソースからシンクへと少しずつ流していき、もうこれ以上ソースからシンクへ流すことができなくなった状態で、容量が最小となる流路の位置の左右で区分けを行う。
【００４９】
ここで、Ｒの輝度だけを考え、図９の□で示した点の数を減らし、グラフカットの経過を例で示す。かかる例に相当する内容が参考文献２の「3 Patch Fitting using Graph Cut」に記載されている。
【００５０】
図１２（ａ）には、□で示した点が６点あり、各点にはソースの画素値が示されている。なお、６点の左側にはソース、右側にはシンクがあることとする。
【００５１】
図１２（ｂ）は、当該６点と各点におけるシンクの画素値を示している。
【００５２】
図１２（ｃ）は、式（２）の第１項および第４項に相当する値を□内に示している。また、同図は、この値から求まる２点間の流路の容量を示している。容量は流れる方向によらず同一なのでその同一の容量を示している。
【００５３】
これに加え、図１２（ｄ）は、グラフカットのラインを示している。ラインの左では、□で示した点にソースの輝度が設定される。一方、ラインの右では、□で示した点にシンクの輝度が設定される。したがい、グラフカットのラインは、□で示した点の領域をソース側とシンク側とに分けるものとなる。また、グラフカットのラインは複数の流路を横切るものとなる。ラインに横切られた流路の容量の合計が、グラフカットのコストである。同図の例では、グラフカットのコストは、５＋５＋２＝１２であり、最小となっている。
【００５４】
本システムは、このグラフカットのコストが最小と判定されたときの補正領域とその周辺領域の画像を表示するのである。
【００５５】
なお、本システムにおける画像補正方法をコンピュータに実行させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に格納し、陳列などして流通させたり、当該コンピュータプログラムをインターネットなどの通信網を介して伝送させてもよい。
【００５６】
（参考文献１）
M.Bertalmio, G.Sapiro, V.Caselles, and C.Ballester, "Image inpainting", ACM Proc.SIGGRAPH., pp.417-424, 2000.
（参考文献２）
V.Kwatra, A.Schodl, I.Essa, G.Turk, and A.Bobick, "Graphcut textures, image and video synthesis using graph cut", ACM Proc. SIGGRAPH, 2004.
【図面の簡単な説明】
【００５７】
【図１】図１は、本実施の形態に係るシステム構成図である。
【図２】図２ｈ、パッチのある１枚のテクスチャ画像の例と本システムのアルゴリズムの初期段階について示す。
【図３】図３は、反復的にパッチ内部と境界とをシームレスにするアルゴリズムについて示す。
【図４】図４は、グラフカットのコストが変化する一例を示す。
【図５】図５は、グラフカット法の効果を示す。
【図６】図６は、パッチΦ内部のテクスチャが変化していく様子を示す。
【図７】図７は、本システムにおいてグラフカットのコストが最小になったときの画像を示す。
【図８】図８は、従来法により補正された画像を示す。
【図９】図９は、グラフカット処理の説明に用いたネットワーク網を示す。
【図１０】図１０は、図９の□で示された９点にソースの値あるいはシンクの値を適用することを示す。
【図１１】図１１は、図９の□で示された２点間の流路を示す。
【図１２】図１２は、グラフカット処理の経過を例で示す。
【符号の説明】
【００５８】
１００ データ入力手段
１１０ データ蓄積手段
１２０ 近傍画像抽出手段
１３０ 重なり補正手段
１４０ 画像パターン変形手段
１５０ 境界部補正手段
１６０ コスト最小化判定手段
１７０ 表示手段
【特許請求の範囲】
【請求項１】
画像において補正が必要な補正領域の近傍にある近傍画像を抽出し、移流方程式により、前記補正領域へ重ねるように移動させる手段と、
前記補正領域で重なりが生じる領域を連続性をもたせるように補正する手段と、
前記補正領域の画像を変形させる手段と、
前記補正領域とその周辺領域との境界部をグラフカットにより補正する手段と、
前記境界部の補正におけるグラフカットのコストが最小か否かを判定する手段と、
最小と判定されたときの前記補正領域とその周辺領域の画像を表示する手段と
を備えることを特徴とする画像補正装置。
【請求項２】
前記補正領域の画像を変形させるときに移流方程式と動きベクトルを用いることを特徴とする請求項１記載の画像補正装置。
【請求項３】
画像において補正が必要な補正領域の近傍にある近傍画像を抽出し、移流方程式により、前記補正領域へ重ねるように移動させ、
前記補正領域で重なりが生じる領域を連続性をもたせるように補正し、
前記補正領域の画像を変形させ、
前記補正領域とその周辺領域との境界部をグラフカットにより補正し、
前記境界部の補正におけるグラフカットのコストが最小か否かを判定し、
最小と判定されたときの前記補正領域とその周辺領域の画像を表示する
ことを特徴とする画像補正方法。
【請求項４】
前記補正領域の画像を変形させるときに移流方程式と動きベクトルを用いることを特徴とする請求項３記載の画像補正方法。
【請求項５】
請求項３または４記載の画像補正方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項１】
画像において補正が必要な補正領域の近傍にある近傍画像を抽出し、移流方程式により、前記補正領域へ重ねるように移動させる手段と、
前記補正領域で重なりが生じる領域を連続性をもたせるように補正する手段と、
前記補正領域の画像を変形させる手段と、
前記補正領域とその周辺領域との境界部をグラフカットにより補正する手段と、
前記境界部の補正におけるグラフカットのコストが最小か否かを判定する手段と、
最小と判定されたときの前記補正領域とその周辺領域の画像を表示する手段と
を備えることを特徴とする画像補正装置。
【請求項２】
前記補正領域の画像を変形させるときに移流方程式と動きベクトルを用いることを特徴とする請求項１記載の画像補正装置。
【請求項３】
画像において補正が必要な補正領域の近傍にある近傍画像を抽出し、移流方程式により、前記補正領域へ重ねるように移動させ、
前記補正領域で重なりが生じる領域を連続性をもたせるように補正し、
前記補正領域の画像を変形させ、
前記補正領域とその周辺領域との境界部をグラフカットにより補正し、
前記境界部の補正におけるグラフカットのコストが最小か否かを判定し、
最小と判定されたときの前記補正領域とその周辺領域の画像を表示する
ことを特徴とする画像補正方法。
【請求項４】
前記補正領域の画像を変形させるときに移流方程式と動きベクトルを用いることを特徴とする請求項３記載の画像補正方法。
【請求項５】
請求項３または４記載の画像補正方法をコンピュータに実行させるためのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００９−１５６２９（Ｐ２００９−１５６２９Ａ）
【公開日】平成２１年１月２２日（２００９．１．２２）
【国際特許分類】
【出願番号】特願２００７−１７７１７９（Ｐ２００７−１７７１７９）
【出願日】平成１９年７月５日（２００７．７．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２１年１月２２日（２００９．１．２２）
【国際特許分類】
【出願日】平成１９年７月５日（２００７．７．５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]