画像処理装置、方法及びコンピュータ読取可能な記録媒体
【課題】高速、かつ高品位に欠損画像を修復することを可能にする。
【解決手段】パンチ孔やステープラーの跡などの欠損領域を含む入力画像に対して、欠損領域を修復する画像処理を行う画像処理装置１は、欠損領域を含まない領域の画素の画素値を構造化する構造化手段２１と、構造化された画素値に基づいて欠損領域に含まれる画素の画素値を推定し、欠損領域を修復する画像処理を行う修復手段２２と、を具備する。
【解決手段】パンチ孔やステープラーの跡などの欠損領域を含む入力画像に対して、欠損領域を修復する画像処理を行う画像処理装置１は、欠損領域を含まない領域の画素の画素値を構造化する構造化手段２１と、構造化された画素値に基づいて欠損領域に含まれる画素の画素値を推定し、欠損領域を修復する画像処理を行う修復手段２２と、を具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、方法及びコンピュータ読取可能な記録媒体に関する。
【背景技術】
【０００２】
複写機でコピーを行う際、パンチ孔やステープラーの跡など、画像が欠損している場合が多々ある。このような欠損領域を修復しようとする場合、背景の色がわかっているならば、その色で塗りつぶすだけで、きれいに修復が可能である。特に文書画像の背景は圧倒的に白である可能性が高いため、ほとんどの場合は白で塗りつぶすだけできれいに修復が可能である。
【０００３】
一方、背景の色がわからない場合に、特定の色で塗りつぶす処理をしてしまうと、欠損領域がかえって目立ってしまう場合がある。このような場面に対応するために、古くは拡散方程式を用いた手法が用いられてきた（例えば、非特許文献１）。この手法は、拡散方程式を用いて画素の輝度値を欠損領域の境界から内側へ徐々に伝播させることで欠損領域を滑らかに補間する方法である。該手法を用いると、輝度値の連続性は保たれるという特徴から、写真についたひっかき傷のような細い領域に対しては良好な結果を得ることができ、また、大域的構造や大きなエッジ勾配に強いというメリットがある。その一方で、大きな領域を修復した場合には細かいテクスチャが表現できず、不鮮明な画像が生成されるという問題がある。
【０００４】
図１１は該手法で欠損領域を修復した画像である。左が元画像であり、中央の黒い丸が欠損領域である。一方、右が、修復後の画像である。図から明らかなように該手法を用いて修復を行うと、画像が滑らかにつながってはいるが、ぼけてしまうと言う問題がある。この傾向は特に画像の輝度変化が急峻で有る場合に強くなる。つまり、テクスチャの影響が大きい領域やエッジ領域などでは非特許文献１のような手法では良好な欠損修復ができないということができる。
【０００５】
このような問題から、非特許文献２では周辺画像から欠損領域のテクスチャを推定する手法が提案されている。以下にそのアルゴリズムの概要を示す。まず、図１２に示すように、ある大きさのウィンドウ（図１２の矩形領域）を設定し、内部に欠損領域が含まれるようなウィンドウの中心の動く範囲をΩ’とする。続いて、画像内におけるΩ’以外の領域Φ（以下データ領域と呼ぶ）に中心を持つウィンドウとのパターン類似度を算出し、このパターン類似度の重みつき総和として定義されるエネルギー関数が最小となるようなパターンの位置を探索する。
【０００６】
ここで、パターンの類似度としてはＳＳＤ（Ｓｕｍ ｏｆ Ｓｑｕａｒｅｄ Ｄｉｆｆｅｒｅｎｃｅｓ）を用いる。尚、Ｉ（ｘ）はｘにおける画素値を意味する。
【０００７】
【数１】
【０００８】
エネルギー関数はパターン類似度ＳＳＤの重み付き総和で以下のように記載することができる。
【０００９】
【数２】
【００１０】
ここで、ωｘはＳＳＤの信頼度を反映するためのウェイトであり、補完すべき欠損画素からの距離などで重みを変化させることなども可能で有るが、以下ではωｘ＝１として均等の重みを与えることとする。以上で定義されたエネルギー関数を最小にするように、欠損領域内の各画素ｘに対して類似するパターンをデータ領域内Φで探索し、該パターンの中心画素の画素値で画素ｘの画素値を置き換える。欠損領域内の全ての画素に対して置き換えが終わったら、欠損領域内の各画素について、また最初から探索と置き換えの処理を行い、エネルギーが十分に小さくなるまで繰り返して最適化する。以上の処理を行うことで、細かいテクスチャまで表現が可能であり、高品位な修復画像を得ることができる。例えば、草むらの一部を欠損領域として修復処理をすることを考えると、欠損領域を埋めるべき模様は周辺画像に存在することが容易に予想される。そのため、この手法で欠損領域の細かいテクスチャが表現可能になるのである。
【００１１】
しかし、高品位な修復画像が得られる一方で、本手法には極めて多大な計算時間が必要であるという問題が有った。例えば、画像が２００×２００画素、欠損領域の画素数１０００画素、ウインドウサイズを３×３＝９画素とすると、データ領域の画素数は３９０００画素になる。ＳＳＤ算出には９回の引き算と掛け算が必要で、ＳＳＤ算出を３９０００回行って、やっと一画素を埋められることになる。更にその処理を１０００画素に対して行うことでエネルギーが算出されるが、エネルギーが収束するためには、以上の計算を複数回行わなければならない。
【００１２】
以上のように、従来手法には、一画素を補完するために、データ領域Φ全てをパタンマッチする必要が有り、その処理には極めて時間がかかるという問題が有った。
【００１３】
なお、本発明に関連する特許文献としては、特許文献１，２があり、特許文献１は、画像の内容に応じて複数種の補完方法を切り替えることが記載されている（例えば、段落００３７）。一方、特許文献２は、画像データを修復する際に、拡散方程式を用いて修復を行うが、段階的な縮小処理を行って十分小さな欠損領域に対して修復処理を行うことが記載されている。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明は以上を鑑みてなされたものであり、高速、かつ高品位に欠損画像を修復することを可能にする画像処理装置、方法及びコンピュータ読取可能な記録媒体を提供するものである。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、本発明は、第１の態様として、欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理装置であって、前記欠損領域を含まない領域の画素の画素値を構造化する構造化手段と、構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復手段と、を具備することを特徴とする、画像処理装置を提供する。
【００１６】
また、上記目的を達成するために、本発明は、第２の態様として、欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理方法であって、前記欠損領域を含まない領域の画素の画素値を構造化する構造化工程と、構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復工程と、を含むことを特徴とする、画像処理方法を提供する。
【００１７】
また、上記目的を達成するために、本発明は、第３の態様として、上記画像処理方法をコンピュータに実行させるプログラムを記録したことを特徴とする、コンピュータ読取可能な記録媒体を提供する。
【発明の効果】
【００１８】
本発明によれば、高速、かつ高品位に欠損画像を修復することを可能にする画像処理装置、方法及びコンピュータ読取可能な記録媒体を提供することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本発明による画像処理装置１のハードウェア構成の一例を示す図である。
【図２】本発明による画像処理装置１の主要な機能を示す機能ブロック図である。
【図３】本実施形態に係るアプリケーションにより画像出力部１２に表示されるユーザインターフェースの一例を示す図である。
【図４】本実施形態に係るアプリケーションのユースケースのフローチャートである。
【図５】本実施形態に係る修復処理の動作を示すフローチャートである。
【図６】本実施形態に係る修復処理における構造化処理を説明するための図である。
【図７】本実施形態に係る修復処理における最近傍探索処理を説明するための図である。
【図８】本実施形態に係る修復処理の詳細な流れを示すフローチャートである。
【図９】本実施形態に係る修復処理における構造化処理にて構造化される対象を例示する図である。
【図１０】本実施形態に係る修復処理における構造化処理の二分木構造を示す図である。
【図１１】従来技術の拡散方程式を用いた画像修復の例を示す図である。
【図１２】従来技術の周辺画像から欠損領域のテクスチャを推定する手法の概要を示す図である。
【発明を実施するための形態】
【００２０】
以下、本発明を実施するための一形態を、図面を用いて説明する。以下、画像処理装置に対して本発明を適用した実施形態を示す。
【００２１】
＜構成＞
（ハードウェア）
図１は、本発明による画像処理装置１のハードウェア構成の一例を示す図である。本実施形態に係る画像処理装置１は、欠損領域を含む入力画像に対して、当該欠損領域を修復する画像処理を行う画像処理装置である。具体的に、画像形成装置１は、画像入力部１１、画像出力部１２、ＣＰＵ１３、Ｉ／Ｏ回路１４、ＲＯＭ１５、ＲＡＭ１６、及びＨＤＤ１７を有する構成である。
【００２２】
画像入力部１１は、画像入力を行うもので、例えば、スキャナ、複写機、複合機等の画像機器における画像読取部に相当する。また、外部で読み取られた原稿の画像データをメディア（記録媒体）やネットワーク経由で入力することもできる。
【００２３】
ＣＰＵ１３、Ｉ／Ｏ回路１４、ＲＯＭ１５、ＲＡＭ１６、及びＨＤＤ１７は、バスラインを介して相互に通信可能に接続された構成になっている。ＲＯＭ１５は、画像処理装置１が起動されるときに実行されるプログラムや各種データを格納している。ＲＡＭ１６は、ＲＯＭ１５やＨＤＤ１７から読み出された各種プログラムやデータを一時保存する主記憶装置である。さらに、ＣＰＵ１３は、演算処理を含む本画像処理装置全体の処理の制御を行うとともに、ＲＡＭ１６が一時保存しているプログラムを実行する。Ｉ／Ｏ回路１４は、画像入力部１１及び画像出力部１２を含む周辺機器との入出力を管理する。ＨＤＤ１７は、ＣＰＵ１３による制御の下に処理された画像データや外部から取り込んだ画像データを記憶する。
【００２４】
画像出力部１２は、プリンタやディスプレイなどの出力装置とその制御手段によって構成され、画像処理装置１による処理によって修復された欠損領域のある画像データを印刷出力したり表示画面上に表示出力したりする。また、ネットワーク経由で外部への出力をすることもできる。
【００２５】
（ソフトウェア）
図１のＨＤＤ１７には、画像処理装置１の有するハードウェア資源を利用して、所定の情報処理を行い、下記の機能及び動作を実現するソフトウェア・アプリケーション（以下、「本実施形態に係るアプリケーション」という）が格納されている。本実施形態に係るアプリケーションは、磁気式、光学式ディスク等のコンピュータ読取可能な記録媒体によって画像処理装置１に提供されてもよい。
【００２６】
（機能）
図２は、画像処理装置１の主要機能を示す機能ブロック図である。画像処理装置１は、欠損領域を含む入力画像に対して、当該欠損領域を修復する画像処理を行う画像処理装置であり、以下のような構成を有する。すなわち、画像処理装置１は、主要な機能として、構造化手段２１と修復手段２２を含む構成である。
【００２７】
構造化手段２１は、画像入力部１１により入力された欠損領域を含む入力画像データを、修復処理を行う前に、事前に構造化する。修復手段２２は、構造化された入力画像データを修復する画像処理を行う。以下では、構造化手段２１の実行する処理と修復手段２２の実行する処理を合わせて「修復処理」という場合がある。
【００２８】
（ユースケース）
図３は、本実施形態に係るアプリケーションにより画像出力部１２に表示されるユーザインターフェースの一例を示す図である。図３に示すように、本アプリケーションのユーザインターフェースは、「開くボタン」、「保存ボタン」、「実行ボタン」、及び「画像表示部」を有している。
【００２９】
続いて、本アプリケーションを利用する際のユーザの動作とアプリケーションの動作を図４のフローチャートを用いて説明する。図４において左はユーザの動作、右はアプリケーション動作を示す。ユーザはアプリケーションを起動する（ｓｔｅｐ００１）。続いて、ユーザは図３の開くボタンをマウスでクリックする。するとファイル選択ダイアログがポップアップし、ユーザは該ダイアログを利用して所望の画像ファイルを選択する（ｓｔｅｐ００２）。すると、アプリケーションは図３の画像表示部にユーザの指定した画像を表示する（ｓｔｅｐ００３）。ユーザは該画像表示部に表示された画像内で、除去したい領域、すなわち今後の処理では欠損領域となる領域部分をドラッグする（ｓｔｅｐ００４）。ドラッグされた領域では画像に赤い線が引かれ、該赤い線の領域が欠損領域であることをユーザに通知する。その後、ユーザが図３の開始ボタンを押下すると（ｓｔｅｐ００５）、アプリケーションでは、欠損した領域を画像のその他の領域から推定して修復する（ｓｔｅｐ００６）。修復した画像は画像表示部に表示していた画像に置き換えられる。
【００３０】
以上のような処理を行うことで、ユーザは画像中の不要な被写体を違和感無く削除することができる。こうすることで、例えば、ウェブページにアップロードしたい画像に写った人などを除去すれば、その人のプライバシーを守ることができるなどといったメリットがある。
以下では、ｓｔｅｐ００６で示した修復処理について詳細に述べることとする。
【００３１】
＜動作＞
（修復処理の概略）
図５は図４のｓｔｅｐ００６で示した修復処理の動作を示すフローチャートである。まず画像の色空間をＲＧＢ空間からＬ＊ａ＊ｂ＊空間に変換する（ｓｔｅｐ２０１）。続いて、プレーン分解し、Ｌ＊画像、ａ＊画像、ｂ＊画像の３プレーンに分解する（ｓｔｅｐ２０２）。
【００３２】
Ｌ＊画像についてはそのまま修復処理に入る（ｓｔｅｐ２０３）。一方でａ＊画像とｂ＊画像については縦横それぞれ半分に縮小し（ｓｔｅｐ２０４）、修復処理に入る（ｓｔｅｐ２０５）。ここで述べる修復処理について、それぞれ同様の処理を行うものとする。詳細については後述するが、修復処理は非常に計算量の大きな処理である。続いて、ａ＊画像とｂ＊画像はそれぞれ拡大処理され、縮小前の画像と比較して欠損していた領域だけを修復画像と合成して出力する。それぞれ、修復されたＬ＊画像ａ＊画像およびｂ＊画像はプレーンを統合され（ｓｔｅｐ２０７）、元のＲＧＢ色空間に変換されて出力される（ｓｔｅｐ２０８）。
【００３３】
ここでＬ＊画像とａ＊画像ｂ＊画像をそれぞれ分けて処理するのは、処理の負荷を下げるためである。Ｌ＊ａ＊ｂ＊色空間は輝度成分であるＬ＊信号と色度成分であるａ＊ｂ＊成分から構成される。一般に人間の目は輝度成分の変化に対して敏感であるが、色度成分の変化については鈍感である。そのため、色度成分については、それほど高精度に修復しなくとも、輝度成分を正確に修復すれば、人間の目には高品位な画質が得られることになる。そこで、本実施形態では、色度成分については低解像度に変換してから修復し、高速な処理が行えるようにしている。
【００３４】
本実施形態では輝度成分と色度成分とで同じ処理ではあるが、異なる解像度という構成により高速化を実現したが、他にも様々な方法が考えられる。
【００３５】
例えば、輝度成分に関しては非特許文献２記載の手法で修復し、色度成分については、従来技術で述べた拡散方程式を用いた手法で修復しても構わない。従来技術でも述べた通り、拡散方程式を用いた手法は細かい模様などを表現することは難しいが、欠損領域を滑らかに修復可能で、処理も非特許文献２の手法に比べると極めて高速である。そのため輝度成分と色度成分を同じ解像度で処理しても、十分な高速化が望める。勿論、色度成分を低解像度で処理しても構わない。同様に、拡散方程式を用いずとも、色度成分について線形補間で欠損領域を修復しても同様の効果が得られる。
【００３６】
また、今回輝度、色度成分を示す色空間としてＬ＊ａ＊ｂ＊を用いたが、ＹＣｂＣｒ等であっても構わない。
【００３７】
（修復処理の詳細）
修復処理は従来技術で述べた、非特許文献２の手法を改良した手法を用いてなされる。大きく分けて３つの改良を施したが、この改良について説明する。
【００３８】
非特許文献２の手法は前述の通り、欠損領域に含まれる全ての画素に対してパタンマッチによる探索を行わなければならない。更に欠損領域の推定は一度で済まず、エネルギーが十分に小さくなるまで繰り返されるため、非常に大きな計算量が必要になる。これに対し、本手法では、画像データを事前に構造化することで高速化を行っている。これが、第一の改良点である。構造化により処理が高速化できる理由を以下に説明する。
【００３９】
例えば図６の(イ)で示されるように、ある空間において□で示されるデータが分布しているとする。ここに入力データで有る○が入力されたとし、入力データと最も近い□を求めたい。
【００４０】
例えば○と全ての□の総当りで距離を算出し、比較しても良いが、非常に効率が悪い。そこで例えば、データの分布から事前に、（ロ）のように空間を分割しておき、始めにどの空間に入力データが存在するかを求めれば、たった二つの□との距離を算出するだけでよくなる。以上のように、事前に構造化、すなわち、データの分布から空間を分割して置くことで距離算出を効率化できるので高速化が可能となる。
【００４１】
このような構造化による高速化は一般的な手段で有るが、非特許文献２の手法とは極めて相性が良い。例えば、通常の画像認識などで用いられるパタンマッチ処理で構造化を行うことを考えると、構造化により探索処理そのものは高速化が可能である。一方、事前の構造化に比較的大きな計算量が必要となるため、構造化処理と探索処理を含めた総合的な意味では高速化につながらない事も多い。一方、ここまでで説明したように非特許文献２の修復処理のように、同じ画像に対して、何度もパタンマッチを繰り返す処理の場合、構造化したデータを何度も繰り返して利用することが可能であるため、処理が高速化できることになる。
【００４２】
続いて、第二の改良点について述べる。図６を用いた例の説明では説明を簡単にするため、入力データがどの空間に存在するかを判定し、該空間でのみ最近傍を行えば良いと述べた。一方、実際には以下の図のように最近傍データが判定した空間とは違う空間に存在してしまうことも発生する。そこで、始めに判定した空間で最も近いデータを探し、そのデータと入力データとの距離ｌ0を算出し、該ｌ0よりも近い可能性が有る空間（図７でいう左上の空間）に含まれるデータについても最近傍探索を行うという処理を行わなければ、厳密な最近傍探索ができない。
【００４３】
そのため、事前に行う空間分割は非常に大切なプロセスである。すなわち、始めに判定した空間におけるデータが十分に近ければ、その後空間を跨いだ最近傍判定を行う回数が少なくなる。一方で、全ての入力データに対して、最適な空間分割を事前に行うことは難しい。
【００４４】
そこで、非特許文献３ではＡｐｐｒｏｘｉｍａｔｅ Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ（ＡＮＮ）と呼ばれる手法が提案されている。ＡＮＮではｌ０よりも近い可能性の有る空間に対して最近傍探索する代わりに、ｌ0よりも小さなｌを用いる点が特徴である。厳密な最近傍を得るためには前述のような処理が必要で有るが、最近傍探索に誤差を含むことを許容することにより、高速、かつ最近傍に近いデータを得ることができる。尚、ｌとｌ0の関係は以下の数式で表すことができ、εを大きくすればするほど、誤差は大きくなるが、処理速度は高速になる。
【００４５】
【数３】
【００４６】
ＡＮＮを使うことが、第二の改良点であるが、ここで、精度が落ちるが高速という点は本手法にとって、非常に適していることを説明する。本手法で行う最近傍探索は、欠損領域を仮に埋めるための画素を決定するために行うものであり、必ずしも厳密な最近傍である必要は無いからである。また、本来εは０〜１程度で利用することが、よく行われているが、本手法のように比較的精度を問わないアプリケーションの場合、ε＝１０やε＝１００であっても十分実用に耐えうる。
【００４７】
また、εを欠損領域の推定が終わるたびに、つまりエネルギー算出するたびに、変化させても、効果が有る。これが第３の改良点である。始めに欠損領域を動埋めるかにも左右されるが、一般に最適化の初期においてはエネルギー、すなわち、推定した画素と、最近傍画素との距離の総和は大きい。つまり、最も近いパターンを探してきても、それほど近いパターンで無いということになる。前述した通り、始めに算出したｌ0が十分小さければ、精度良く探索するための処理は小さくて済むが、あまり近いパターンが存在しないということは、ｌ0は大きいということに他ならない。つまり、かなりの確率で処理量が大きくなってしまうことになる。一方、繰り返しの末期、つまり、エネルギーが十分に小さくなった後には、逆に精度良く探索をしても処理が大きくならない可能性が高まることになるのでεを小さくすると、精度が上がりつつ処理速度がそれほど落ちないようになる。そこで本手法では、最適化の初期にはεを１００とし、欠損領域の推定がＮ回目として以下の式によりεを変化させる構成とした。但し、εの最小値は５とした。
【００４８】
【数４】
【００４９】
本実施形態ではεをＮに対して変化させたが、他にもエネルギーに応じて変化させても問題ない。例えばエネルギーをＥとし、初期のエネルギーＥ0に対して、以下の式でεを変化させても良い。但し、εの最小値は同様に５とする。前述の通りエネルギーが小さくなるほど、ｌ0は小さい可能性が高いためエネルギーに応じてεを変化させるとより精度と速度をより細やかに制御することが可能である。
【００５０】
【数５】
【００５１】
以上の修復処理の説明を踏まえて、図８に修復処理の詳細フローを記載する。図８において、まず始めに、画像に含まれる画像データを構造化する（ｓｔｅｐ３０１）。ここで構造化される対象は、注目画素の周辺３×３画素の画素値を並べて作成される９次元のベクトルである（図９）。図９においてグレーの画素（ｖ５）が注目画素で、その周辺画素値ｖ１〜ｖ９が９次元のベクトルとなる。ここで、画像が（ｎ＋１）×（ｍ＋１）画素だったとすればｎ×ｍ個の９次元ベクトルが構造化される対象になる。ただし、９つの画素のうち１画素でも欠損領域が含まれる場合には構造化の対象に含めないものとするので、実際のベクトルの数はｎ×ｍよりも小さくなる。
【００５２】
また、構造化の手法については後述するが、図１０に示すように一つのノードに対して一つのベクトルが対応付けられており、各ノードには２つのノードがぶら下がっているといった２分木構造に構造化するものとする。具体的にはｋｄ−ｔｒｅｅと呼ばれる手法を用いる。ｋｄ−ｔｒｅｅは各ノードにおいて、ベクトルを一つの要素（今回の例では９つの要素のうち一つ）の値を用いて２つのカテゴリに分類する二分木手段である。ルートノードから一つの末端のリーフノードまでを極めて小さい計算量で辿ることができる。
【００５３】
続いて、εを算出する（ｓｔｅｐ３０２）。εの算出方法は数式３（数３）若しくは数式４（数４）を用いて決定すれば良い。その後、欠損領域から一つの画素を選択し、図９を用いた説明と同様に周辺画素を含めた要素を並べる事によって、ベクトルを作成する（ｓｔｅｐ３０３）。その後最近傍探索を行うが（ｓｔｅｐ３０４）、ここでは前述したＡＮＮを用いることになる。すなわち入力ベクトルをルートノードから辿って、末端のリーフノードを得る。リーフノードと入力ベクトルとの距離ｌ0を算出する。ｌ0からｌを算出する。リーフノードから逆にノードを辿り、ｌよりも近い可能性があるリーフノードを列挙する。列挙したリーフノードの中から入力ベクトルと最も近いノードを見つける。といった手順を踏むことになる。
【００５４】
この様に欠損領域における全ての画素に対して最近傍探索を行った後、エネルギーを算出する（ｓｔｅｐ３０５）。このエネルギーとは従来技術で述べたＳＳＤの和すなわち、欠損領域における画素から得た入力ベクトルと、その最近傍ノードとの距離の総和がエネルギーとなる。
【００５５】
Ｓｔｅｐ３０５で算出したエネルギーが十分に小さくなるまで、処理をループさせる。収束判定方法にもいろいろ有るが、今回は前回のループで算出したエネルギーと今回算出したエネルギーとの差が所定の大きさよりも小さくなった場合に処理を終了させるものとする。
【００５６】
以上に述べた本実施形態の構成によれば、欠損領域を含まない領域の画素値を事前に構造化する構造化手段を具備することで、高速、且つ高品位に画像修復を行うことが可能である。また、事前に構造化を行うことにより、極めて効果的に高速化が可能となる。
【００５７】
また、データが二分木に構造化されており、各ノードが一つの画素値の値に基づいて分割されていることで、構造化された画素値パターンから入力画素値パターンと近いパターンを探索することが可能となる。
【００５８】
また、近似的に最近傍探索を行うことにより、より高速に最近傍パターンを探索することが可能となる。
【００５９】
また、最適化の各ステップ毎にｌ0に対するｌの値を小さくすることで、最近傍探索の精度劣化を抑制しつつ高速に最近傍を探索することが可能となる。
【００６０】
また、エネルギーの大きさに応じて、ｌ0に対するｌの値を変化することで、最近傍探索の精度劣化を抑制しつつ高速に最近傍を探索することが可能となる。
【００６１】
また、輝度成分と色度成分とに分けて、それぞれに異なる修復処理を施すことにより、処理速度と修復後の画像の品位をきめ細かく制御することが可能となる。
【００６２】
また、色度画像は縮小してから修復することにより、人間の目が敏感で有る輝度画像にのみ、処理が重いが高品位な修復を行うことで、高速且つ高品位に修復を行うことができる。
【００６３】
また、色度成分について拡散方程式を用いて修復することで、人間の目が敏感である輝度画像にのみ、処理が重いが高品位な修復を行うことで、高速且つ高品位に修復を行うことができる。
【００６４】
また、色度成分については線形補間を用いて修復することで、人間の目が敏感で有る輝度画像にのみ、処理が重いが高品位な修復を行うことで、高速且つ高品位に修復を行うことができる。
【００６５】
以上、本発明を実施するための一形態について述べてきたが、本発明は画像専用ＩＣ等でも実装可能である。そのため、Ｍｕｌｔｉ Ｆｕｎｃｔｉｏｎ Ｐｒｉｎｔｅｒ（ＭＦＰ）等に搭載すれば、スキャンした文書をＭＦＰの操作液晶上でプレビューし、ユーザにパンチ穴等の修復したい領域を指定させ、該領域について修復して出力するといった利用も考えられる。
【符号の説明】
【００６６】
１ 画像処理装置
１１ 画像入力部
１２ 画像出力部
１３ ＣＰＵ
１４ Ｉ／Ｏ回路
１５ ＲＯＭ
１６ ＲＡＭ
１７ ＨＤＤ
２１ 構造化手段
２２ 修復手段
【先行技術文献】
【特許文献】
【００６７】
【特許文献１】特開２００７−２８６７３４号公報
【特許文献２】特開２００６−３３２７８５号公報
【非特許文献】
【００６８】
【非特許文献１】M.Bertalmio, G.Sapiro, V.Caselles and C.Ballester: Image Inpainting, In Proc, SIGGRAPH2000, pp.417-424, 2000.
【非特許文献２】A.Criminisi, P.Perez and K.Toyama: Region Filling and Object Removal by Exemplar-Based Image Inpainting, IEEE Trance, on Image Processing, Vol.13, No.9, 2004.
【非特許文献３】S. Arya, D. M. Mount, N. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In 5th ACM-SIAM Symposium Discrete Algorithms, pp. 573582, 1994.
【技術分野】
【０００１】
本発明は、画像処理装置、方法及びコンピュータ読取可能な記録媒体に関する。
【背景技術】
【０００２】
複写機でコピーを行う際、パンチ孔やステープラーの跡など、画像が欠損している場合が多々ある。このような欠損領域を修復しようとする場合、背景の色がわかっているならば、その色で塗りつぶすだけで、きれいに修復が可能である。特に文書画像の背景は圧倒的に白である可能性が高いため、ほとんどの場合は白で塗りつぶすだけできれいに修復が可能である。
【０００３】
一方、背景の色がわからない場合に、特定の色で塗りつぶす処理をしてしまうと、欠損領域がかえって目立ってしまう場合がある。このような場面に対応するために、古くは拡散方程式を用いた手法が用いられてきた（例えば、非特許文献１）。この手法は、拡散方程式を用いて画素の輝度値を欠損領域の境界から内側へ徐々に伝播させることで欠損領域を滑らかに補間する方法である。該手法を用いると、輝度値の連続性は保たれるという特徴から、写真についたひっかき傷のような細い領域に対しては良好な結果を得ることができ、また、大域的構造や大きなエッジ勾配に強いというメリットがある。その一方で、大きな領域を修復した場合には細かいテクスチャが表現できず、不鮮明な画像が生成されるという問題がある。
【０００４】
図１１は該手法で欠損領域を修復した画像である。左が元画像であり、中央の黒い丸が欠損領域である。一方、右が、修復後の画像である。図から明らかなように該手法を用いて修復を行うと、画像が滑らかにつながってはいるが、ぼけてしまうと言う問題がある。この傾向は特に画像の輝度変化が急峻で有る場合に強くなる。つまり、テクスチャの影響が大きい領域やエッジ領域などでは非特許文献１のような手法では良好な欠損修復ができないということができる。
【０００５】
このような問題から、非特許文献２では周辺画像から欠損領域のテクスチャを推定する手法が提案されている。以下にそのアルゴリズムの概要を示す。まず、図１２に示すように、ある大きさのウィンドウ（図１２の矩形領域）を設定し、内部に欠損領域が含まれるようなウィンドウの中心の動く範囲をΩ’とする。続いて、画像内におけるΩ’以外の領域Φ（以下データ領域と呼ぶ）に中心を持つウィンドウとのパターン類似度を算出し、このパターン類似度の重みつき総和として定義されるエネルギー関数が最小となるようなパターンの位置を探索する。
【０００６】
ここで、パターンの類似度としてはＳＳＤ（Ｓｕｍ ｏｆ Ｓｑｕａｒｅｄ Ｄｉｆｆｅｒｅｎｃｅｓ）を用いる。尚、Ｉ（ｘ）はｘにおける画素値を意味する。
【０００７】
【数１】
【０００８】
エネルギー関数はパターン類似度ＳＳＤの重み付き総和で以下のように記載することができる。
【０００９】
【数２】
【００１０】
ここで、ωｘはＳＳＤの信頼度を反映するためのウェイトであり、補完すべき欠損画素からの距離などで重みを変化させることなども可能で有るが、以下ではωｘ＝１として均等の重みを与えることとする。以上で定義されたエネルギー関数を最小にするように、欠損領域内の各画素ｘに対して類似するパターンをデータ領域内Φで探索し、該パターンの中心画素の画素値で画素ｘの画素値を置き換える。欠損領域内の全ての画素に対して置き換えが終わったら、欠損領域内の各画素について、また最初から探索と置き換えの処理を行い、エネルギーが十分に小さくなるまで繰り返して最適化する。以上の処理を行うことで、細かいテクスチャまで表現が可能であり、高品位な修復画像を得ることができる。例えば、草むらの一部を欠損領域として修復処理をすることを考えると、欠損領域を埋めるべき模様は周辺画像に存在することが容易に予想される。そのため、この手法で欠損領域の細かいテクスチャが表現可能になるのである。
【００１１】
しかし、高品位な修復画像が得られる一方で、本手法には極めて多大な計算時間が必要であるという問題が有った。例えば、画像が２００×２００画素、欠損領域の画素数１０００画素、ウインドウサイズを３×３＝９画素とすると、データ領域の画素数は３９０００画素になる。ＳＳＤ算出には９回の引き算と掛け算が必要で、ＳＳＤ算出を３９０００回行って、やっと一画素を埋められることになる。更にその処理を１０００画素に対して行うことでエネルギーが算出されるが、エネルギーが収束するためには、以上の計算を複数回行わなければならない。
【００１２】
以上のように、従来手法には、一画素を補完するために、データ領域Φ全てをパタンマッチする必要が有り、その処理には極めて時間がかかるという問題が有った。
【００１３】
なお、本発明に関連する特許文献としては、特許文献１，２があり、特許文献１は、画像の内容に応じて複数種の補完方法を切り替えることが記載されている（例えば、段落００３７）。一方、特許文献２は、画像データを修復する際に、拡散方程式を用いて修復を行うが、段階的な縮小処理を行って十分小さな欠損領域に対して修復処理を行うことが記載されている。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明は以上を鑑みてなされたものであり、高速、かつ高品位に欠損画像を修復することを可能にする画像処理装置、方法及びコンピュータ読取可能な記録媒体を提供するものである。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、本発明は、第１の態様として、欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理装置であって、前記欠損領域を含まない領域の画素の画素値を構造化する構造化手段と、構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復手段と、を具備することを特徴とする、画像処理装置を提供する。
【００１６】
また、上記目的を達成するために、本発明は、第２の態様として、欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理方法であって、前記欠損領域を含まない領域の画素の画素値を構造化する構造化工程と、構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復工程と、を含むことを特徴とする、画像処理方法を提供する。
【００１７】
また、上記目的を達成するために、本発明は、第３の態様として、上記画像処理方法をコンピュータに実行させるプログラムを記録したことを特徴とする、コンピュータ読取可能な記録媒体を提供する。
【発明の効果】
【００１８】
本発明によれば、高速、かつ高品位に欠損画像を修復することを可能にする画像処理装置、方法及びコンピュータ読取可能な記録媒体を提供することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本発明による画像処理装置１のハードウェア構成の一例を示す図である。
【図２】本発明による画像処理装置１の主要な機能を示す機能ブロック図である。
【図３】本実施形態に係るアプリケーションにより画像出力部１２に表示されるユーザインターフェースの一例を示す図である。
【図４】本実施形態に係るアプリケーションのユースケースのフローチャートである。
【図５】本実施形態に係る修復処理の動作を示すフローチャートである。
【図６】本実施形態に係る修復処理における構造化処理を説明するための図である。
【図７】本実施形態に係る修復処理における最近傍探索処理を説明するための図である。
【図８】本実施形態に係る修復処理の詳細な流れを示すフローチャートである。
【図９】本実施形態に係る修復処理における構造化処理にて構造化される対象を例示する図である。
【図１０】本実施形態に係る修復処理における構造化処理の二分木構造を示す図である。
【図１１】従来技術の拡散方程式を用いた画像修復の例を示す図である。
【図１２】従来技術の周辺画像から欠損領域のテクスチャを推定する手法の概要を示す図である。
【発明を実施するための形態】
【００２０】
以下、本発明を実施するための一形態を、図面を用いて説明する。以下、画像処理装置に対して本発明を適用した実施形態を示す。
【００２１】
＜構成＞
（ハードウェア）
図１は、本発明による画像処理装置１のハードウェア構成の一例を示す図である。本実施形態に係る画像処理装置１は、欠損領域を含む入力画像に対して、当該欠損領域を修復する画像処理を行う画像処理装置である。具体的に、画像形成装置１は、画像入力部１１、画像出力部１２、ＣＰＵ１３、Ｉ／Ｏ回路１４、ＲＯＭ１５、ＲＡＭ１６、及びＨＤＤ１７を有する構成である。
【００２２】
画像入力部１１は、画像入力を行うもので、例えば、スキャナ、複写機、複合機等の画像機器における画像読取部に相当する。また、外部で読み取られた原稿の画像データをメディア（記録媒体）やネットワーク経由で入力することもできる。
【００２３】
ＣＰＵ１３、Ｉ／Ｏ回路１４、ＲＯＭ１５、ＲＡＭ１６、及びＨＤＤ１７は、バスラインを介して相互に通信可能に接続された構成になっている。ＲＯＭ１５は、画像処理装置１が起動されるときに実行されるプログラムや各種データを格納している。ＲＡＭ１６は、ＲＯＭ１５やＨＤＤ１７から読み出された各種プログラムやデータを一時保存する主記憶装置である。さらに、ＣＰＵ１３は、演算処理を含む本画像処理装置全体の処理の制御を行うとともに、ＲＡＭ１６が一時保存しているプログラムを実行する。Ｉ／Ｏ回路１４は、画像入力部１１及び画像出力部１２を含む周辺機器との入出力を管理する。ＨＤＤ１７は、ＣＰＵ１３による制御の下に処理された画像データや外部から取り込んだ画像データを記憶する。
【００２４】
画像出力部１２は、プリンタやディスプレイなどの出力装置とその制御手段によって構成され、画像処理装置１による処理によって修復された欠損領域のある画像データを印刷出力したり表示画面上に表示出力したりする。また、ネットワーク経由で外部への出力をすることもできる。
【００２５】
（ソフトウェア）
図１のＨＤＤ１７には、画像処理装置１の有するハードウェア資源を利用して、所定の情報処理を行い、下記の機能及び動作を実現するソフトウェア・アプリケーション（以下、「本実施形態に係るアプリケーション」という）が格納されている。本実施形態に係るアプリケーションは、磁気式、光学式ディスク等のコンピュータ読取可能な記録媒体によって画像処理装置１に提供されてもよい。
【００２６】
（機能）
図２は、画像処理装置１の主要機能を示す機能ブロック図である。画像処理装置１は、欠損領域を含む入力画像に対して、当該欠損領域を修復する画像処理を行う画像処理装置であり、以下のような構成を有する。すなわち、画像処理装置１は、主要な機能として、構造化手段２１と修復手段２２を含む構成である。
【００２７】
構造化手段２１は、画像入力部１１により入力された欠損領域を含む入力画像データを、修復処理を行う前に、事前に構造化する。修復手段２２は、構造化された入力画像データを修復する画像処理を行う。以下では、構造化手段２１の実行する処理と修復手段２２の実行する処理を合わせて「修復処理」という場合がある。
【００２８】
（ユースケース）
図３は、本実施形態に係るアプリケーションにより画像出力部１２に表示されるユーザインターフェースの一例を示す図である。図３に示すように、本アプリケーションのユーザインターフェースは、「開くボタン」、「保存ボタン」、「実行ボタン」、及び「画像表示部」を有している。
【００２９】
続いて、本アプリケーションを利用する際のユーザの動作とアプリケーションの動作を図４のフローチャートを用いて説明する。図４において左はユーザの動作、右はアプリケーション動作を示す。ユーザはアプリケーションを起動する（ｓｔｅｐ００１）。続いて、ユーザは図３の開くボタンをマウスでクリックする。するとファイル選択ダイアログがポップアップし、ユーザは該ダイアログを利用して所望の画像ファイルを選択する（ｓｔｅｐ００２）。すると、アプリケーションは図３の画像表示部にユーザの指定した画像を表示する（ｓｔｅｐ００３）。ユーザは該画像表示部に表示された画像内で、除去したい領域、すなわち今後の処理では欠損領域となる領域部分をドラッグする（ｓｔｅｐ００４）。ドラッグされた領域では画像に赤い線が引かれ、該赤い線の領域が欠損領域であることをユーザに通知する。その後、ユーザが図３の開始ボタンを押下すると（ｓｔｅｐ００５）、アプリケーションでは、欠損した領域を画像のその他の領域から推定して修復する（ｓｔｅｐ００６）。修復した画像は画像表示部に表示していた画像に置き換えられる。
【００３０】
以上のような処理を行うことで、ユーザは画像中の不要な被写体を違和感無く削除することができる。こうすることで、例えば、ウェブページにアップロードしたい画像に写った人などを除去すれば、その人のプライバシーを守ることができるなどといったメリットがある。
以下では、ｓｔｅｐ００６で示した修復処理について詳細に述べることとする。
【００３１】
＜動作＞
（修復処理の概略）
図５は図４のｓｔｅｐ００６で示した修復処理の動作を示すフローチャートである。まず画像の色空間をＲＧＢ空間からＬ＊ａ＊ｂ＊空間に変換する（ｓｔｅｐ２０１）。続いて、プレーン分解し、Ｌ＊画像、ａ＊画像、ｂ＊画像の３プレーンに分解する（ｓｔｅｐ２０２）。
【００３２】
Ｌ＊画像についてはそのまま修復処理に入る（ｓｔｅｐ２０３）。一方でａ＊画像とｂ＊画像については縦横それぞれ半分に縮小し（ｓｔｅｐ２０４）、修復処理に入る（ｓｔｅｐ２０５）。ここで述べる修復処理について、それぞれ同様の処理を行うものとする。詳細については後述するが、修復処理は非常に計算量の大きな処理である。続いて、ａ＊画像とｂ＊画像はそれぞれ拡大処理され、縮小前の画像と比較して欠損していた領域だけを修復画像と合成して出力する。それぞれ、修復されたＬ＊画像ａ＊画像およびｂ＊画像はプレーンを統合され（ｓｔｅｐ２０７）、元のＲＧＢ色空間に変換されて出力される（ｓｔｅｐ２０８）。
【００３３】
ここでＬ＊画像とａ＊画像ｂ＊画像をそれぞれ分けて処理するのは、処理の負荷を下げるためである。Ｌ＊ａ＊ｂ＊色空間は輝度成分であるＬ＊信号と色度成分であるａ＊ｂ＊成分から構成される。一般に人間の目は輝度成分の変化に対して敏感であるが、色度成分の変化については鈍感である。そのため、色度成分については、それほど高精度に修復しなくとも、輝度成分を正確に修復すれば、人間の目には高品位な画質が得られることになる。そこで、本実施形態では、色度成分については低解像度に変換してから修復し、高速な処理が行えるようにしている。
【００３４】
本実施形態では輝度成分と色度成分とで同じ処理ではあるが、異なる解像度という構成により高速化を実現したが、他にも様々な方法が考えられる。
【００３５】
例えば、輝度成分に関しては非特許文献２記載の手法で修復し、色度成分については、従来技術で述べた拡散方程式を用いた手法で修復しても構わない。従来技術でも述べた通り、拡散方程式を用いた手法は細かい模様などを表現することは難しいが、欠損領域を滑らかに修復可能で、処理も非特許文献２の手法に比べると極めて高速である。そのため輝度成分と色度成分を同じ解像度で処理しても、十分な高速化が望める。勿論、色度成分を低解像度で処理しても構わない。同様に、拡散方程式を用いずとも、色度成分について線形補間で欠損領域を修復しても同様の効果が得られる。
【００３６】
また、今回輝度、色度成分を示す色空間としてＬ＊ａ＊ｂ＊を用いたが、ＹＣｂＣｒ等であっても構わない。
【００３７】
（修復処理の詳細）
修復処理は従来技術で述べた、非特許文献２の手法を改良した手法を用いてなされる。大きく分けて３つの改良を施したが、この改良について説明する。
【００３８】
非特許文献２の手法は前述の通り、欠損領域に含まれる全ての画素に対してパタンマッチによる探索を行わなければならない。更に欠損領域の推定は一度で済まず、エネルギーが十分に小さくなるまで繰り返されるため、非常に大きな計算量が必要になる。これに対し、本手法では、画像データを事前に構造化することで高速化を行っている。これが、第一の改良点である。構造化により処理が高速化できる理由を以下に説明する。
【００３９】
例えば図６の(イ)で示されるように、ある空間において□で示されるデータが分布しているとする。ここに入力データで有る○が入力されたとし、入力データと最も近い□を求めたい。
【００４０】
例えば○と全ての□の総当りで距離を算出し、比較しても良いが、非常に効率が悪い。そこで例えば、データの分布から事前に、（ロ）のように空間を分割しておき、始めにどの空間に入力データが存在するかを求めれば、たった二つの□との距離を算出するだけでよくなる。以上のように、事前に構造化、すなわち、データの分布から空間を分割して置くことで距離算出を効率化できるので高速化が可能となる。
【００４１】
このような構造化による高速化は一般的な手段で有るが、非特許文献２の手法とは極めて相性が良い。例えば、通常の画像認識などで用いられるパタンマッチ処理で構造化を行うことを考えると、構造化により探索処理そのものは高速化が可能である。一方、事前の構造化に比較的大きな計算量が必要となるため、構造化処理と探索処理を含めた総合的な意味では高速化につながらない事も多い。一方、ここまでで説明したように非特許文献２の修復処理のように、同じ画像に対して、何度もパタンマッチを繰り返す処理の場合、構造化したデータを何度も繰り返して利用することが可能であるため、処理が高速化できることになる。
【００４２】
続いて、第二の改良点について述べる。図６を用いた例の説明では説明を簡単にするため、入力データがどの空間に存在するかを判定し、該空間でのみ最近傍を行えば良いと述べた。一方、実際には以下の図のように最近傍データが判定した空間とは違う空間に存在してしまうことも発生する。そこで、始めに判定した空間で最も近いデータを探し、そのデータと入力データとの距離ｌ0を算出し、該ｌ0よりも近い可能性が有る空間（図７でいう左上の空間）に含まれるデータについても最近傍探索を行うという処理を行わなければ、厳密な最近傍探索ができない。
【００４３】
そのため、事前に行う空間分割は非常に大切なプロセスである。すなわち、始めに判定した空間におけるデータが十分に近ければ、その後空間を跨いだ最近傍判定を行う回数が少なくなる。一方で、全ての入力データに対して、最適な空間分割を事前に行うことは難しい。
【００４４】
そこで、非特許文献３ではＡｐｐｒｏｘｉｍａｔｅ Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ（ＡＮＮ）と呼ばれる手法が提案されている。ＡＮＮではｌ０よりも近い可能性の有る空間に対して最近傍探索する代わりに、ｌ0よりも小さなｌを用いる点が特徴である。厳密な最近傍を得るためには前述のような処理が必要で有るが、最近傍探索に誤差を含むことを許容することにより、高速、かつ最近傍に近いデータを得ることができる。尚、ｌとｌ0の関係は以下の数式で表すことができ、εを大きくすればするほど、誤差は大きくなるが、処理速度は高速になる。
【００４５】
【数３】
【００４６】
ＡＮＮを使うことが、第二の改良点であるが、ここで、精度が落ちるが高速という点は本手法にとって、非常に適していることを説明する。本手法で行う最近傍探索は、欠損領域を仮に埋めるための画素を決定するために行うものであり、必ずしも厳密な最近傍である必要は無いからである。また、本来εは０〜１程度で利用することが、よく行われているが、本手法のように比較的精度を問わないアプリケーションの場合、ε＝１０やε＝１００であっても十分実用に耐えうる。
【００４７】
また、εを欠損領域の推定が終わるたびに、つまりエネルギー算出するたびに、変化させても、効果が有る。これが第３の改良点である。始めに欠損領域を動埋めるかにも左右されるが、一般に最適化の初期においてはエネルギー、すなわち、推定した画素と、最近傍画素との距離の総和は大きい。つまり、最も近いパターンを探してきても、それほど近いパターンで無いということになる。前述した通り、始めに算出したｌ0が十分小さければ、精度良く探索するための処理は小さくて済むが、あまり近いパターンが存在しないということは、ｌ0は大きいということに他ならない。つまり、かなりの確率で処理量が大きくなってしまうことになる。一方、繰り返しの末期、つまり、エネルギーが十分に小さくなった後には、逆に精度良く探索をしても処理が大きくならない可能性が高まることになるのでεを小さくすると、精度が上がりつつ処理速度がそれほど落ちないようになる。そこで本手法では、最適化の初期にはεを１００とし、欠損領域の推定がＮ回目として以下の式によりεを変化させる構成とした。但し、εの最小値は５とした。
【００４８】
【数４】
【００４９】
本実施形態ではεをＮに対して変化させたが、他にもエネルギーに応じて変化させても問題ない。例えばエネルギーをＥとし、初期のエネルギーＥ0に対して、以下の式でεを変化させても良い。但し、εの最小値は同様に５とする。前述の通りエネルギーが小さくなるほど、ｌ0は小さい可能性が高いためエネルギーに応じてεを変化させるとより精度と速度をより細やかに制御することが可能である。
【００５０】
【数５】
【００５１】
以上の修復処理の説明を踏まえて、図８に修復処理の詳細フローを記載する。図８において、まず始めに、画像に含まれる画像データを構造化する（ｓｔｅｐ３０１）。ここで構造化される対象は、注目画素の周辺３×３画素の画素値を並べて作成される９次元のベクトルである（図９）。図９においてグレーの画素（ｖ５）が注目画素で、その周辺画素値ｖ１〜ｖ９が９次元のベクトルとなる。ここで、画像が（ｎ＋１）×（ｍ＋１）画素だったとすればｎ×ｍ個の９次元ベクトルが構造化される対象になる。ただし、９つの画素のうち１画素でも欠損領域が含まれる場合には構造化の対象に含めないものとするので、実際のベクトルの数はｎ×ｍよりも小さくなる。
【００５２】
また、構造化の手法については後述するが、図１０に示すように一つのノードに対して一つのベクトルが対応付けられており、各ノードには２つのノードがぶら下がっているといった２分木構造に構造化するものとする。具体的にはｋｄ−ｔｒｅｅと呼ばれる手法を用いる。ｋｄ−ｔｒｅｅは各ノードにおいて、ベクトルを一つの要素（今回の例では９つの要素のうち一つ）の値を用いて２つのカテゴリに分類する二分木手段である。ルートノードから一つの末端のリーフノードまでを極めて小さい計算量で辿ることができる。
【００５３】
続いて、εを算出する（ｓｔｅｐ３０２）。εの算出方法は数式３（数３）若しくは数式４（数４）を用いて決定すれば良い。その後、欠損領域から一つの画素を選択し、図９を用いた説明と同様に周辺画素を含めた要素を並べる事によって、ベクトルを作成する（ｓｔｅｐ３０３）。その後最近傍探索を行うが（ｓｔｅｐ３０４）、ここでは前述したＡＮＮを用いることになる。すなわち入力ベクトルをルートノードから辿って、末端のリーフノードを得る。リーフノードと入力ベクトルとの距離ｌ0を算出する。ｌ0からｌを算出する。リーフノードから逆にノードを辿り、ｌよりも近い可能性があるリーフノードを列挙する。列挙したリーフノードの中から入力ベクトルと最も近いノードを見つける。といった手順を踏むことになる。
【００５４】
この様に欠損領域における全ての画素に対して最近傍探索を行った後、エネルギーを算出する（ｓｔｅｐ３０５）。このエネルギーとは従来技術で述べたＳＳＤの和すなわち、欠損領域における画素から得た入力ベクトルと、その最近傍ノードとの距離の総和がエネルギーとなる。
【００５５】
Ｓｔｅｐ３０５で算出したエネルギーが十分に小さくなるまで、処理をループさせる。収束判定方法にもいろいろ有るが、今回は前回のループで算出したエネルギーと今回算出したエネルギーとの差が所定の大きさよりも小さくなった場合に処理を終了させるものとする。
【００５６】
以上に述べた本実施形態の構成によれば、欠損領域を含まない領域の画素値を事前に構造化する構造化手段を具備することで、高速、且つ高品位に画像修復を行うことが可能である。また、事前に構造化を行うことにより、極めて効果的に高速化が可能となる。
【００５７】
また、データが二分木に構造化されており、各ノードが一つの画素値の値に基づいて分割されていることで、構造化された画素値パターンから入力画素値パターンと近いパターンを探索することが可能となる。
【００５８】
また、近似的に最近傍探索を行うことにより、より高速に最近傍パターンを探索することが可能となる。
【００５９】
また、最適化の各ステップ毎にｌ0に対するｌの値を小さくすることで、最近傍探索の精度劣化を抑制しつつ高速に最近傍を探索することが可能となる。
【００６０】
また、エネルギーの大きさに応じて、ｌ0に対するｌの値を変化することで、最近傍探索の精度劣化を抑制しつつ高速に最近傍を探索することが可能となる。
【００６１】
また、輝度成分と色度成分とに分けて、それぞれに異なる修復処理を施すことにより、処理速度と修復後の画像の品位をきめ細かく制御することが可能となる。
【００６２】
また、色度画像は縮小してから修復することにより、人間の目が敏感で有る輝度画像にのみ、処理が重いが高品位な修復を行うことで、高速且つ高品位に修復を行うことができる。
【００６３】
また、色度成分について拡散方程式を用いて修復することで、人間の目が敏感である輝度画像にのみ、処理が重いが高品位な修復を行うことで、高速且つ高品位に修復を行うことができる。
【００６４】
また、色度成分については線形補間を用いて修復することで、人間の目が敏感で有る輝度画像にのみ、処理が重いが高品位な修復を行うことで、高速且つ高品位に修復を行うことができる。
【００６５】
以上、本発明を実施するための一形態について述べてきたが、本発明は画像専用ＩＣ等でも実装可能である。そのため、Ｍｕｌｔｉ Ｆｕｎｃｔｉｏｎ Ｐｒｉｎｔｅｒ（ＭＦＰ）等に搭載すれば、スキャンした文書をＭＦＰの操作液晶上でプレビューし、ユーザにパンチ穴等の修復したい領域を指定させ、該領域について修復して出力するといった利用も考えられる。
【符号の説明】
【００６６】
１ 画像処理装置
１１ 画像入力部
１２ 画像出力部
１３ ＣＰＵ
１４ Ｉ／Ｏ回路
１５ ＲＯＭ
１６ ＲＡＭ
１７ ＨＤＤ
２１ 構造化手段
２２ 修復手段
【先行技術文献】
【特許文献】
【００６７】
【特許文献１】特開２００７−２８６７３４号公報
【特許文献２】特開２００６−３３２７８５号公報
【非特許文献】
【００６８】
【非特許文献１】M.Bertalmio, G.Sapiro, V.Caselles and C.Ballester: Image Inpainting, In Proc, SIGGRAPH2000, pp.417-424, 2000.
【非特許文献２】A.Criminisi, P.Perez and K.Toyama: Region Filling and Object Removal by Exemplar-Based Image Inpainting, IEEE Trance, on Image Processing, Vol.13, No.9, 2004.
【非特許文献３】S. Arya, D. M. Mount, N. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In 5th ACM-SIAM Symposium Discrete Algorithms, pp. 573582, 1994.
【特許請求の範囲】
【請求項１】
欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理装置であって、
前記欠損領域を含まない領域の画素の画素値を構造化する構造化手段と、
構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復手段と、
を具備することを特徴とする、画像処理装置。
【請求項２】
前記修復手段は、
前記欠損領域の画素を中心とする周辺画素値パターンを入力とし、最近傍の画素値パターンを、前記入力画像の前記欠損領域を含まない領域から探索して出力する最近傍探索手段と、
前記欠損領域の画素値を、前記探索により得られた画素値パターンの中心画素値で置き換える画素値置き換え手段と、
前記欠損領域すべてについて前記最近傍探索手段による処理及び前記画素値置き換え手段による処理を行うことをワンステップとして、前記最近傍探索手段における入力パターンと出力パターンの差異に基づいて前記ワンステップごとにエネルギーを算出するエネルギー算出手段と、
前記ワンステップごとに前記エネルギーが収束したか否かを判定する最適化手段と、
を有することを特徴とする、請求項１記載の画像処理装置。
【請求項３】
前記最近傍探索手段は、
木構造のノードを辿って仮の最近傍を見つける仮の最近傍探索手段と、
前記仮の最近傍との距離ｌ0を算出する距離算出手段と、
前記ｌ0に基づいて探索範囲ｌを決定する探索範囲決定手段と、を有し、
前記ｌよりも近い可能性があるパターンの中から最近傍を選択することを特徴とする、請求項２記載の画像処理装置。
【請求項４】
前記探索範囲決定手段は、前記ワンステップごとに前記ｌ0に対する前記ｌの値を小さくすることを特徴とする、請求項３記載の画像処理装置。
【請求項５】
前記探索範囲決定手段は、前記エネルギーの大きさに応じて前記ｌ0に対する前記ｌの値を変化させることを特徴とする、請求項３記載の画像処理装置。
【請求項６】
前記構造化手段は、二分木構造に前記欠損領域を含まない領域の画素の画素値を構造化し、各ノードが一つの画素値に基づくよう分割することを特徴とする、請求項１から５のいずれか１項記載の画像処理装置。
【請求項７】
前記入力画像を輝度画像と色度画像とに変換する色変換手段を具備し、
前記修復手段は、変換された前記輝度画像と色度画像とを異なる解像度で、別々に、前記欠損領域の修復を行うことを特徴とする、請求項１から６のいずれか１項記載の画像処理装置。
【請求項８】
前記修復手段は、前記色度画像に対して、縮小処理を行った跡で修復処理を行い、該修復処理後に拡大して前記欠損領域を修復することを特徴とする、請求項７記載の画像処理装置。
【請求項９】
前記修復手段は、前記色度画像に対して、拡散方程式を用いて前記欠損領域を修復することを特徴とする、請求項７又は８記載の画像処理装置。
【請求項１０】
前記修復手段は、前記色度画像に対して、線形補間を用いて前記欠損領域を修復することを特徴とする、請求項７から９のいずれか１項記載の画像処理装置。
【請求項１１】
欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理方法であって、
前記欠損領域を含まない領域の画素の画素値を構造化する構造化工程と、
構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復工程と、
を含むことを特徴とする、画像処理方法。
【請求項１２】
請求項１１記載の画像処理方法をコンピュータに実行させるプログラムを記録したことを特徴とする、コンピュータ読取可能な記録媒体。
【請求項１】
欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理装置であって、
前記欠損領域を含まない領域の画素の画素値を構造化する構造化手段と、
構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復手段と、
を具備することを特徴とする、画像処理装置。
【請求項２】
前記修復手段は、
前記欠損領域の画素を中心とする周辺画素値パターンを入力とし、最近傍の画素値パターンを、前記入力画像の前記欠損領域を含まない領域から探索して出力する最近傍探索手段と、
前記欠損領域の画素値を、前記探索により得られた画素値パターンの中心画素値で置き換える画素値置き換え手段と、
前記欠損領域すべてについて前記最近傍探索手段による処理及び前記画素値置き換え手段による処理を行うことをワンステップとして、前記最近傍探索手段における入力パターンと出力パターンの差異に基づいて前記ワンステップごとにエネルギーを算出するエネルギー算出手段と、
前記ワンステップごとに前記エネルギーが収束したか否かを判定する最適化手段と、
を有することを特徴とする、請求項１記載の画像処理装置。
【請求項３】
前記最近傍探索手段は、
木構造のノードを辿って仮の最近傍を見つける仮の最近傍探索手段と、
前記仮の最近傍との距離ｌ0を算出する距離算出手段と、
前記ｌ0に基づいて探索範囲ｌを決定する探索範囲決定手段と、を有し、
前記ｌよりも近い可能性があるパターンの中から最近傍を選択することを特徴とする、請求項２記載の画像処理装置。
【請求項４】
前記探索範囲決定手段は、前記ワンステップごとに前記ｌ0に対する前記ｌの値を小さくすることを特徴とする、請求項３記載の画像処理装置。
【請求項５】
前記探索範囲決定手段は、前記エネルギーの大きさに応じて前記ｌ0に対する前記ｌの値を変化させることを特徴とする、請求項３記載の画像処理装置。
【請求項６】
前記構造化手段は、二分木構造に前記欠損領域を含まない領域の画素の画素値を構造化し、各ノードが一つの画素値に基づくよう分割することを特徴とする、請求項１から５のいずれか１項記載の画像処理装置。
【請求項７】
前記入力画像を輝度画像と色度画像とに変換する色変換手段を具備し、
前記修復手段は、変換された前記輝度画像と色度画像とを異なる解像度で、別々に、前記欠損領域の修復を行うことを特徴とする、請求項１から６のいずれか１項記載の画像処理装置。
【請求項８】
前記修復手段は、前記色度画像に対して、縮小処理を行った跡で修復処理を行い、該修復処理後に拡大して前記欠損領域を修復することを特徴とする、請求項７記載の画像処理装置。
【請求項９】
前記修復手段は、前記色度画像に対して、拡散方程式を用いて前記欠損領域を修復することを特徴とする、請求項７又は８記載の画像処理装置。
【請求項１０】
前記修復手段は、前記色度画像に対して、線形補間を用いて前記欠損領域を修復することを特徴とする、請求項７から９のいずれか１項記載の画像処理装置。
【請求項１１】
欠損領域を含む入力画像に対して、前記欠損領域を修復する画像処理を行う画像処理方法であって、
前記欠損領域を含まない領域の画素の画素値を構造化する構造化工程と、
構造化された前記画素値に基づいて前記欠損領域に含まれる画素の画素値を推定し、前記欠損領域を修復する画像処理を行う修復工程と、
を含むことを特徴とする、画像処理方法。
【請求項１２】
請求項１１記載の画像処理方法をコンピュータに実行させるプログラムを記録したことを特徴とする、コンピュータ読取可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−３５５６７（Ｐ２０１１−３５５６７Ａ）
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願番号】特願２００９−１７８２６２（Ｐ２００９−１７８２６２）
【出願日】平成２１年７月３０日（２００９．７．３０）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願日】平成２１年７月３０日（２００９．７．３０）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
[ Back to top ]