(57)【要約】【課題】  迅速に画像のマスク領域の補完をする方法及び装置並びにプログラムを提供すること。【解決手段】  入力画像とマスク画像に繰り返しダウンサンプリングを施して複数レベルのガウシアンピラミッドを構築する。次に、最も粗い第ｎレベルの画像において全領域で探索を行い、ターゲットフラグメントと類似する最適フラグメントの位置を得る。１段下のレベルにおいて、そのレベルのターゲットフラグメントと類似度が最小（最も類似している）のフラグメントを探索する。この探索においては、１段階上の最適フラグメントの位置の近傍に探索範囲を限定している。この探索範囲の限定によって探索効率を向上させて、計算速度を向上させている。以下、同様に各レベルにおける探索を行い、原入力画像のレベルにおける類似度が最も小さい（最も似ている）フラグメントを求めることができる。この結果、処理速度の向上した画像補完方法・装置が得られる。【選択図】      図１
2006332785.tif 000002
【特許請求の範囲】
【請求項１】
入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の部分画像を、所定の他の領域で補完する画像補完方法において、
前記入力画像の解像度を変更して解像度が異なる第１から第ｎレベルまでのｎ種類の入力画像群を生成し、前記入力画像自体を第０レベルの入力画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類の入力画像群を生成する多重解像度入力画像生成ステップと、
前記マスク画像の解像度を変更して解像度が異なる第１レベルから第ｎレベルまでのｎ種類のマスク画像群を生成し、前記マスク画像を第０レベルのマスク画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類のマスク画像群を生成する多重解像度マスク画像生成ステップと、
第ｍレベルの前記入力画像と、第ｍレベルの前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、上位の第ｍ＋１レベルにおける探索ステップにおいて見いだされた類似する領域の位置に基づきこの第ｍレベルにおける探索範囲を限定して前記探索を行い、前記ｍ＋１レベルが存在しない場合、すなわち第ｎレベルの場合は、この第ｍレベルにおける探索領域を前記第ｍレベルの入力画像の全範囲とする探索ステップと、
前記ｍをｎから０まで変化させて、前記探索ステップを順次繰り返す繰り返しステップと、
前記第０レベルにおける探索の結果見いだされた領域を用いて、元の前記マスク画像が指定する領域を補完する補完ステップと、
を含むことを特徴とする画像補完方法。ここで、前記ｎは正の整数であり、前記ｍはｎから０までの整数である。
【請求項２】
請求項１記載の画像補完方法において、
前記多重解像度入力画像生成ステップにおける前記ｎ＋１種類の入力画像群は、所定のローパスフィルタを用いて生成した多重解像度画像群であり、前記多重解像度マスク画像生成ステップにおける前記ｎ＋１種類のマスク画像群も、所定のローパスフィルタを用いて生成した多重解像度画像群であることを特徴とする画像補完方法。
【請求項３】
請求項１記載の画像補完方法において、
最も粗いレベルである第ｎレベルにおける入力画像の縦方向又は横方向のピクセル数のいずれかが１００未満となるように、前記ｎを設定することを特徴とする画像補完方法。
【請求項４】
請求項１記載の画像補完方法において、
前記探索ステップにおいて、前記類似する領域を探索し、類似する領域として類似度が小さい領域を複数個選び出すことを特徴とする画像補完方法。
【請求項５】
請求項１記載の画像補完方法において、  
利用者に前記入力画像を表示する表示ステップと、
前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込みステップと、
前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成ステップと、
を含み、
前記探索ステップにおいては、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域に、探索範囲を限定した前記探索を行うことを特徴とする画像補完方法。
【請求項６】
入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の画像を、所定の他の領域で補完する画像補完装置において、
前記入力画像の解像度を変更して解像度が異なる第１から第ｎレベルまでのｎ種類の入力画像群を生成し、前記入力画像自体を第０レベルの入力画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類の入力画像群を生成する多重解像度入力画像生成手段と、
前記マスク画像の解像度を変更して解像度が異なる第１レベルから第ｎレベルまでのｎ種類のマスク画像群を生成し、前記マスク画像を第０レベルのマスク画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類のマスク画像群を生成する多重解像度マスク画像生成手段と、
第ｍレベルの前記入力画像と、第ｍレベルの前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、上位の第ｍ＋１レベルの上位の第レベルにおける探索ステップにおいて見いだされた類似する領域の位置に基づきこの第ｍレベルにおける探索範囲を限定して前記探索を行い、前記ｍ＋１レベルが存在しない場合、すなわち第ｎレベルの場合は、この第ｍレベルにおける探索領域を前記第ｍレベルの入力画像の全範囲とする探索手段と、
を含み、前記探索手段に、前記ｍとして、ｎから０までを供給し、順次繰り返して探索を行わせる繰り返し手段と、
前記第０レベルにおける探索の結果見いだされた領域を用いて、元の前記マスク画像が指定する領域を補完する補完手段と、
を含むことを特徴とする画像補完装置。ここで、前記ｎは正の整数であり、前記ｍはｎから０までの整数である。
【請求項７】
請求項６記載の画像補完装置において、
前記多重解像度入力画像生成手段が生成する前記ｎ＋１種類の入力画像群は、所定のローパスフィルタを用いて生成した多重解像度画像群であり、前記多重解像度マスク画像生成手段が生成する前記ｎ＋１種類のマスク画像群も、所定のローパスフィルタを用いて生成した多重解像度画像群であることを特徴とする画像補完装置。
【請求項８】
請求項６記載の画像補完装置において、
前記繰り返し手段は、最も粗いレベルである第ｎレベルにおける入力画像の縦方向又は横方向のピクセル数のいずれかが１００未満となるように、前記ｎを設定することを特徴とする画像補完装置。
【請求項９】
請求項６記載の画像補完装置において、
前記探索手段は、前記類似する領域を探索し、類似する領域として類似度が小さい領域を複数個選び出すことを特徴とする画像補完装置。
【請求項１０】
請求項６記載の画像補完装置において、  
利用者に前記入力画像を表示する表示手段と、
前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込み手段と、
前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成手段と、
を含み、
前記探索手段は、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域に、探索範囲を限定して前記探索を行うことを特徴とする画像補完装置。
【請求項１１】
コンピュータを、入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の部分画像を、所定の他の領域で補完する画像補完装置として動作させるプログラムにおいて、前記コンピュータに、
前記入力画像の解像度を変更して解像度が異なる第１から第ｎレベルまでのｎ種類の入力画像群を生成し、前記入力画像自体を第０レベルの入力画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類の入力画像群を生成する多重解像度入力画像生成手順と、
前記マスク画像の解像度を変更して解像度が異なる第１レベルから第ｎレベルまでのｎ種類のマスク画像群を生成し、前記マスク画像を第０レベルのマスク画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類のマスク画像群を生成する多重解像度マスク画像生成手順と、
第ｍレベルの前記入力画像と、第ｍレベルの前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、上位の第ｍ＋１レベルにおける探索ステップにおいて見いだされた類似する領域の位置に基づきこの第ｍレベルにおける探索範囲を限定して前記探索を行い、前記ｍ＋１レベルが存在しない場合、すなわち第ｎレベルの場合は、この第ｍレベルにおける探索領域を前記第ｍレベルの入力画像の全範囲とする探索手順と、
前記ｍをｎから０まで変化させて、前記探索ステップを順次繰り返す繰り返し手順と、
前記第０レベルにおける探索の結果見いだされた領域を用いて、元の前記マスク画像が指定する領域を補完する補完手順と、
を実行させることを特徴とするプログラム。ここで、前記ｎは正の整数であり、前記ｍはｎから０までの整数である。
【請求項１２】
請求項１１記載のプログラムにおいて、
前記多重解像度入力画像生成手順における前記ｎ＋１種類の入力画像群は、所定のローパスフィルタを用いて生成した多重解像度画像群であり、前記多重解像度マスク画像生成手順における前記ｎ＋１種類のマスク画像群も、所定のローパスフィルタを用いて生成した多重解像度画像群であることを特徴とするプログラム。
【請求項１３】
請求項１１記載のプログラムにおいて、さらに前記コンピュータに、
最も粗いレベルである第ｎレベルにおける入力画像の縦方向又は横方向のピクセル数のいずれかが１００未満となるように、前記ｎを設定する設定手順、
を実行させることを特徴とするプログラム。
【請求項１４】
請求項１１記載のプログラムにおいて、
前記探索手順においては、前記コンピュータに、前記類似する領域を探索し、類似する領域として類似度が小さい領域を複数個選び出す手順、
を実行させることを特徴とするプログラム。
【請求項１５】
請求項１１記載のプログラムにおいて、  
利用者に前記入力画像を表示する表示手順と、
前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込み手順と、
前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成手順と、
を実行させ、
前記探索手順においては、前記コンピュータに、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域に、探索範囲を限定した前記探索を行う手順を実行させることを特徴とするプログラム。
【請求項１６】
入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の部分画像を、所定の他の領域で補完する画像補完装置において、
利用者に前記入力画像を表示する表示手段と、
前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込み手段と、
前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成手段と、
前記入力画像と、前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域を探索範囲とした前記探索を行う探索手段と、
前記探索の結果見いだされた類似する領域を用いて、元の前記マスク画像が指定する領域を補完する補完手段と、
を含むことを特徴とする画像補完装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の一部を補完する技術に関する。特に、ガウシアンピラミッドを用いたフラグメントベース画像補完装置及び画像補完方法並びにプログラムに関する。
【背景技術】
【０００２】
画像の一部を除去し、その除去した部分を周囲に合わせて自然に補完することは、画像編集の重要な要素技術である。たとえば、写真にしみや傷がついている場合、そのしみや傷を取り除くことが望まれる。また、文字が入っている場合、その画像の再利用等の目的に応じてその文字を除去する必要が生じることがある。また、画像に不本意なものが写っている場合などには、一般にその部分を取り除くことが求められる。
【０００３】
取り除いた部分は、通常、豊富な経験とノウハウ及び技術力のある人間が、画像編集のための種々の道具を使って補完する。その作業は、一般に多大な労力がかかることが知られている。
【０００４】
従来から、計算機による画像補完手法の開発が種々行われてきた。従来の手法においては、上記除去部分が小さな領域である場合しか補完できないものや、単一のテクスチャ領域のみし補完できないもの、等が知られている。このように、従来の計算機を利用した画像補完技術は、その取り扱える画像が限られている場合が多かった。
【０００５】
たとえば、下記非特許文献１においては、テクスチャ合成の手法を利用した画像補完技術が記されている。この非特許文献１に記されている技術は、小さなテクスチャをもとに大きなテクスチャ画像を生成できるが、その扱えるテクスチャは比較的単純な模様に限られており、画像補完に直接利用できるものではなかった。
【０００６】
また、下記非特許文献２においては、いわゆるインペインティング（Inpainting）の技術が開示されている。インペインティングは修復家の行う方法を真似て、マスクの周辺領域の情報をマスク領域へと「内側へ」広げていくことによって見た目に自然な画像補完結果を得る手法である。
【０００７】
ここで、「マスク」とは、画像中の除去しようとする領域を示すものを言う。そして特に、除去しようとする領域そのものは、「マスク領域」と呼ぶ。また、このマスク領域を指定するための画像を特に「マスク画像」と呼ぶ。マスク画像には種々のものが存在するが、除去しようとするマスク領域の部分を「黒」とし、他の部分を「白」とした白黒の画像が用いられることが多い。
【０００８】
ここで、情報を広げていく方向を適切に計算することで、テクスチャの境界部分が自然なタッチで補完されることが期待される。しかしながら、情報を広げるだけなので、マスク領域がテクスチャを有するあるまとまりを持った領域である場合は、滑らかな補完ができずぼやけてしまう可能性が高い。結果として、このインペインティングでは、マスク領域が細長い画像かテクスチャのない画像しかきれいに補完できなかった。
【０００９】
また、下記非特許文献３においては、上記インペインティング手法とテクスチャ合成を融合した方法が記載されている。すなわち、低周波数成分にはインペインティング手法を使い、高周波数成分にはガウシアンピラミッドを使ったテクスチャ合成手法を用いて補完するのである。
【００１０】
この手法は、明度の変化に弱いというテクスチャ合成法の欠点をインペインティング手法で補っており、比較的多くの画像に対して、見た目上もっともらしく補完をすることができる。特に、テクスチャ合成を使っているので広い領域も補完できる。しかしながらこの方法では複数種類のテクスチャが含まれる領域に関しては、見た目上きれいに滑らかに補完することは困難である。
【００１１】
また、下記非特許文献４においては、フラグメントベース画像補完法が記載されている。
【００１２】
この手法では、まずマスク領域を連続関数として近似することにより画像の低周波成分を補間する。次に画像の高周波成分を埋め込むためにマスク領域の各部分に適合する画像を他の場所から探索し、「フラグメント」として切り出して合成する。この手法は広い領域の画像補完に関して優れた成果を収めている。ただし、補完の計算に時間が非常にかかり（たとえば３８４×２５６ピクセルの画像の場合、１時間単位の時間を要する）、処理可能な画像は低解像度のものに限られていた。
【００１３】
また、下記非特許文献５においては、セグメンテーションとテクスチャ合成を組み合わせた手法が記載されている。最初に画像をセグメンテーションし、次にマスク領域内のテクスチャをテンソル投票によって推論する。最後に各マスク領域にテクスチャ合成を施すことで画像補完を完成する。この方法は、多くの画像に対してほぼ自動的に画像補完を行うことができるが、補完処理の計算時間が多大になってしまうという問題がある。
【００１４】
また、下記特許文献１には、ピラミッド構造データを用いて、探索点を絞り込むことが記載されている。特に、一番大きな相関値を有する点を見つけて、その点を唯一の探索点とする技術が開示されている。
【００１５】
また、下記特許文献２には、ピラミッド構造サーチを使用したパターンマッチング方法の改良が開示されている。特に、パターンマッチングの際のパラメータをユーザが自由に設定変更できる仕組みについて開示されている。特に、設定パラメータの候補を表示する手段や、この候補に基づき、パラーメータを設定する手段等が開示されている。
【００１６】
【非特許文献１】M.Ashikhmin: "Synthesizing Natural Textures" 2001 ACM Symposium on interactive 3D  Graphics, pp.217-226, 2001.
【非特許文献２】M.Bertalmio, G.sapiro, C.Ballester, and V.Caselles: "Image Inpainting," Proc.SIGGRAPH 2000, pp.417-424, 2000.
【非特許文献３】H.Yamauchi, J.Haber, and H.P.Seidel, "Image Restoration using Multiresolution Texture Synthesis and Image Inpainting" Proc.Computer Graphics International (CGI) 2003, pp.120-125, 2003.
【非特許文献４】I.Drori, D.Cohen-Or, and H.Yeshurun: "Fragment-Based Image Completion," Proc.SIGGRAPH 2003, pp.303-312, 2003.
【非特許文献５】J.Jia, and C.-K.Tang: "Inference of Segmented Color and Texture Description by Tensor Voting," IEEE Transactions on Patern Analysis and Machine Intelligence, vol.26, no.6, pp.771-786, 2004.
【特許文献１】特開平７−４９９４９号公報
【特許文献２】特開２００３−１０９００３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
このように、フラグメントベース画像補完法や、セグメンテーションとテクスチャ合成を組み合わせた手法等は、比較的精度の高い補完を行うことができるが、計算時間が過大なものとなってしまう。そのため、計算時間が短く、迅速に補完をすることができる手法が望まれている。
【００１８】
本発明は、上記課題に鑑みなされたものであり、その目的は、迅速に画像のマスク領域の補完をする方法及び装置並びにプログラムを提供することである。
【００１９】
特に、本発明は、上述したフラグメントベース画像補完法を改良し、計算時間を短くし手法を提供するものである。すなわち、本発明は、高解像度の画像に関しても実用的な時間で補完することを目的とする。
【課題を解決するための手段】
【００２０】
Ａ．画像補完方法
（１）本発明は、上記課題を解決するために、入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の部分画像を、所定の他の領域で補完する画像補完方法において、前記入力画像の解像度を変更して解像度が異なる第１から第ｎレベルまでのｎ種類の入力画像群を生成し、前記入力画像自体を第０レベルの入力画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類の入力画像群を生成する多重解像度入力画像生成ステップと、前記マスク画像の解像度を変更して解像度が異なる第１レベルから第ｎレベルまでのｎ種類のマスク画像群を生成し、前記マスク画像を第０レベルのマスク画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類のマスク画像群を生成する多重解像度マスク画像生成ステップと、第ｍレベルの前記入力画像と、第ｍレベルの前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、上位の第ｍ＋１レベルにおける探索ステップにおいて見いだされた類似する領域の位置に基づきこの第ｍレベルにおける探索範囲を限定して前記探索を行い、前記ｍ＋１レベルが存在しない場合、すなわち第ｎレベルの場合は、この第ｍレベルにおける探索領域を前記第ｍレベルの入力画像の全範囲とする探索ステップと、前記ｍをｎから０まで変化させて、前記探索ステップを順次繰り返す繰り返しステップと、前記第０レベルにおける探索の結果見いだされた領域を用いて、元の前記マスク画像が指定する領域を補完する補完ステップと、を含むことを特徴とする画像補完方法である。ここで、前記ｎは正の整数であり、前記ｍはｎから０までの整数である。
【００２１】
（２）また、本発明は、上記（１）記載の画像補完方法において、前記多重解像度入力画像生成ステップにおける前記ｎ＋１種類の入力画像群は、所定のローパスフィルタを用いて生成した多重解像度画像群であり、前記多重解像度マスク画像生成ステップにおける前記ｎ＋１種類のマスク画像群も、所定のローパスフィルタを用いて生成した多重解像度画像群であることを特徴とする画像補完方法である。
【００２２】
なお、ローパスフィルタとしては、たとえばガウシアンフィルターが好ましい一例であるが、その他従来から知られている各種フィルターを利用可能である。ガウシアンフィルターの場合は、このような多重解像度画像群はガウシアンピラミッドとなる。後述する（７）（１２）においても同様である。
【００２３】
（３）また、本発明は、上記（１）記載の画像補完方法において、最も粗いレベルである第ｎレベルにおける入力画像の縦方向又は横方向のピクセル数のいずれかが１００未満となるように、前記ｎを設定することを特徴とする画像補完方法である。
【００２４】
（４）また、本発明は、上記（１）記載の画像補完方法において、前記探索ステップにおいて、前記類似する領域を探索し、類似する領域として類似度が小さい領域を複数個選び出すことを特徴とする画像補完方法である。
【００２５】
（５）また、本発明は、上記（１）記載の画像補完方法において、利用者に前記入力画像を表示する表示ステップと、前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込みステップと、前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成ステップと、を含み、前記探索ステップにおいては、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域に、探索範囲を限定した前記探索を行うことを特徴とする画像補完方法である。
【００２６】
Ｂ．画像補完装置
（６）本発明は、上記課題を解決するために、入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の画像を、所定の他の領域で補完する画像補完装置において、前記入力画像の解像度を変更して解像度が異なる第１から第ｎレベルまでのｎ種類の入力画像群を生成し、前記入力画像自体を第０レベルの入力画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類の入力画像群を生成する多重解像度入力画像生成手段と、前記マスク画像の解像度を変更して解像度が異なる第１レベルから第ｎレベルまでのｎ種類のマスク画像群を生成し、前記マスク画像を第０レベルのマスク画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類のマスク画像群を生成する多重解像度マスク画像生成手段と、第ｍレベルの前記入力画像と、第ｍレベルの前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、上位の第ｍ＋１レベルの上位の第レベルにおける探索ステップにおいて見いだされた類似する領域の位置に基づきこの第ｍレベルにおける探索範囲を限定して前記探索を行い、前記ｍ＋１レベルが存在しない場合、すなわち第ｎレベルの場合は、この第ｍレベルにおける探索領域を前記第ｍレベルの入力画像の全範囲とする探索手段と、を含み、前記探索手段に、前記ｍとして、ｎから０までを供給し、順次繰り返して探索を行わせる繰り返し手段と、前記第０レベルにおける探索の結果見いだされた領域を用いて、元の前記マスク画像が指定する領域を補完する補完手段と、を含むことを特徴とする画像補完装置である。ここで、前記ｎは正の整数であり、前記ｍはｎから０までの整数である。
【００２７】
（７）また、本発明は、上記（６）記載の画像補完装置において、前記多重解像度入力画像生成手段が生成する前記ｎ＋１種類の入力画像群は、所定のローパスフィルタを用いて生成した多重解像度画像群であり、前記多重解像度マスク画像生成手段が生成する前記ｎ＋１種類のマスク画像群も、所定のローパスフィルタを用いて生成した多重解像度画像群であることを特徴とする画像補完装置である。
【００２８】
（８）また、本発明は、上記（６）記載の画像補完装置において、前記繰り返し手段は、最も粗いレベルである第ｎレベルにおける入力画像の縦方向又は横方向のピクセル数のいずれかが１００未満となるように、前記ｎを設定することを特徴とする画像補完装置である。
【００２９】
（９）また、本発明は、上記（６）記載の画像補完装置において、前記探索手段は、前記類似する領域を探索し、類似する領域として類似度が小さい領域を複数個選び出すことを特徴とする画像補完装置である。
【００３０】
（１０）また、本発明は、上記（６）記載の画像補完装置において、利用者に前記入力画像を表示する表示手段と、前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込み手段と、前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成手段と、を含み、前記探索手段は、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域に、探索範囲を限定して前記探索を行うことを特徴とする画像補完装置である。
【００３１】
Ｃ．プログラム
（１１）本発明は、上記課題を解決するために、コンピュータを、入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の部分画像を、所定の他の領域で補完する画像補完装置として動作させるプログラムにおいて、前記コンピュータに、前記入力画像の解像度を変更して解像度が異なる第１から第ｎレベルまでのｎ種類の入力画像群を生成し、前記入力画像自体を第０レベルの入力画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類の入力画像群を生成する多重解像度入力画像生成手順と、前記マスク画像の解像度を変更して解像度が異なる第１レベルから第ｎレベルまでのｎ種類のマスク画像群を生成し、前記マスク画像を第０レベルのマスク画像と定義することによって、第０レベルから第ｎレベルまでのｎ＋１種類のマスク画像群を生成する多重解像度マスク画像生成手順と、第ｍレベルの前記入力画像と、第ｍレベルの前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、上位の第ｍ＋１レベルにおける探索ステップにおいて見いだされた類似する領域の位置に基づきこの第ｍレベルにおける探索範囲を限定して前記探索を行い、前記ｍ＋１レベルが存在しない場合、すなわち第ｎレベルの場合は、この第ｍレベルにおける探索領域を前記第ｍレベルの入力画像の全範囲とする探索手順と、前記ｍをｎから０まで変化させて、前記探索ステップを順次繰り返す繰り返し手順と、前記第０レベルにおける探索の結果見いだされた領域を用いて、元の前記マスク画像が指定する領域を補完する補完手順と、を実行させることを特徴とするプログラムである。ここで、前記ｎは正の整数であり、前記ｍはｎから０までの整数である。
【００３２】
（１２）また、本発明は、上記（１１）記載のプログラムにおいて、前記多重解像度入力画像生成手順における前記ｎ＋１種類の入力画像群は、所定のローパスフィルタを用いて生成した多重解像度画像群であり、前記多重解像度マスク画像生成手順における前記ｎ＋１種類のマスク画像群も、所定のローパスフィルタを用いて生成した多重解像度画像群であることを特徴とするプログラムである。
【００３３】
（１３）また、本発明は、上記（１１）記載のプログラムにおいて、さらに前記コンピュータに、最も粗いレベルである第ｎレベルにおける入力画像の縦方向又は横方向のピクセル数のいずれかが１００未満となるように、前記ｎを設定する設定手順、を実行させることを特徴とするプログラムである。
【００３４】
（１４）また、本発明は、上記（１１）記載のプログラムにおいて、前記探索手順においては、前記コンピュータに、前記類似する領域を探索し、類似する領域として類似度が小さい領域を複数個選び出す手順、を実行させることを特徴とするプログラムである。
【００３５】
（１５）また、本発明は、上記（１１）記載のプログラムにおいて、利用者に前記入力画像を表示する表示手順と、前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込み手順と、前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成手順と、を実行させ、前記探索手順においては、前記コンピュータに、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域に、探索範囲を限定した前記探索を行う手順を実行させることを特徴とするプログラムである。
【００３６】
（１６）また、本発明は、入力画像と、補完したい部分を指定するマスク画像と、を入力し、前記入力画像から、前記マスク画像に対応する領域の部分画像を、所定の他の領域で補完する画像補完装置において、利用者に前記入力画像を表示する表示手段と、前記利用者が前記入力画像に対して指示した１以上のテクスチャ領域を取り込むテクスチャ領域取り込み手段と、前記入力画像と同一の大きさの画像であるテクスチャ分類マップであって、各ピクセルには、そのピクセルが属する前記テクスチャ領域を示す識別子が付与されているテクスチャ分類マップを生成するテクスチャ分類マップ生成手段と、前記入力画像と、前記マスク画像と、に基づき、前記入力画像中から、前記マスク画像が指定するマスク領域の部分画像を取り出し、前記部分画像を補完するためにその部分画像と類似する領域を探索する探索ステップであって、前記マスク領域中のピクセルが属する領域と同一のテクスチャ領域を探索範囲とした前記探索を行う探索手段と、前記探索の結果見いだされた類似する領域を用いて、元の前記マスク画像が指定する領域を補完する補完手段と、を含むことを特徴とする画像補完装置である。
【発明の効果】
【００３７】
以上述べたように、本発明によれば、計算時間の短縮化を図ることができ、高解像度の画像に対しても実用的な時間で画像の補完をすることができる。
【発明を実施するための最良の形態】
【００３８】
以下、本発明の好適な実施の形態を図面に基づき説明する。
【００３９】
第１章  基本的技術事項
以下、本実施の形態における基本的な技術の前提について述べる。
【００４０】
１−１．  入力データ  
本実施の形態においては、
（ａ）写真などのラスタ画像（これを入力画像と呼ぶ）と、
（ｂ）補完したい部分を指定するマスク画像と、
を基本的な入力データとして用いている。後述するように、本実施の形態における応用例においては、さらに入力データとして
（ｃ）テクスチャ分類マップ
を利用している。この３番目のテクスチャ分類マップに関しては、後に詳述する。
【００４１】
１−２．  出力データ
出力データは、入力画像を補完した画像であって、元の入力画像中のマスク領域が人間にとって不自然さなく見た目にもっともらしく補完された画像である。本実施の形態においては、後述するように、従来の技術と比較して処理速度が向上しているので、従来より高解像度の画像でも現実的な時間で処理を行うことが可能となる。そのため、高解像度の画像でも手軽に補完をすることが可能となり、画像補完の用途の幅が大きく広がることが期待される。
【００４２】
１−３．  フラグメントベース画像補完法
本実施の形態で提案する画像補完装置及び方法は、フラグメントベース画像補完法の改良であるので、このフラグメントベース画像補完法を説明する。
【００４３】
フラグメントベース画像補完法は、あるピクセルとその近傍ピクセルとで定義される「フラグメント」単位で画像補完を行う。このフラグメントは、上述した「ある１個のピクセル」に対応して定義されるので、各ピクセルごとに対応するフラグメントが定義される。このように、フラグメントは、所定の１個のピクセルと、その１個のピクセルを中心とする一定の範囲のピクセル群の集合である。特に、本実施の形態におけるフラグメントは、内部に穴があいていない連続した領域を形成するピクセルの集合である。
【００４４】
さて、フラグメントベース画像補完法では、入力として入力画像とマスク画像が与えられる。マスク画像が示す入力画像中の領域をマスク領域と呼ぶ。このマスク領域は、入力画像において除去する領域である。また、マスクとは上述したように画像中の除去しようとする領域を示すものを言う。
【００４５】
そして、入力画像中のマスク領域以外の部分の情報を、マスク領域に合成することによって、人間にとって不自然さのない画像が合成されるのである。このマスク領域の合成の処理は、以下の５ステップを繰り返すことによって実行される。
【００４６】
（ステップ１）
まず、入力画像から、マスク領域を取り除く。具体的にはマスク領域内のピクセルの値は０（黒）とするのである。このようにしてマスク領域を除去した後の画像に対して、まず、ダウンサンプリングを行い、次にアップサンプリングを行う。これによって、画像のマスク領域内での低周波数成分を補間することができる。
【００４７】
（ステップ２）
上で述べたようにマスク領域は低周波数成分が補間されているので、０以外の所定の値になっているはずである。本ステップ２では、前記マスク領域の各ピクセルの信頼度を計算する。信頼度の計算は、上記非特許文献４を参照されたい。そして、信頼度に基づき、補完対象となるマスク領域の一部分であるターゲットフラグメントを決定する。
【００４８】
フラグメントとしては、たとえば注目しているピクセルを中心とする１７×１７の四角形領域ピクセルを採用することができる。すなわち、あるピクセルに対して、その近傍周囲にある１７ドット×１７ドットの四角形のピクセル群を「フラグメント」としている。
【００４９】
そして、マスク領域から、所定のピクセルを取り出し、それに対応するフラグメント（ターゲットフラグメント）を決定する。この取り出すピクセルは、信頼度に基づき決定する。
【００５０】
（ステップ３）
次に、マスク領域以外の部分を探索し、ターゲットフラグメントに最も似ているフラグメント（ソースフラグメント）を得る。
【００５１】
（ステップ４）
得られたソースフラグメントをターゲットフラグメントに合成することによって高周波数成分を補完する。
【００５２】
第２章  本実施の形態における探索手法
本実施の形態で提案する手法の特徴的な事項は、上記ステップ４における探索のアルゴリズムである。このアルゴリズムを以下説明する。
【００５３】
２−１．  ガウシアンピラミッドによる高速化
上記非特許文献４におけるフラグメントベース画像補完法においては、フラグメントの探索が全計算時間の約９０パーセントを占めていた。特に、画像が大きくなると、探索範囲とともに一般的にフラグメントサイズもそれに比例して大きくなるため、探索にかかる計算量はＯ（ｎ＾２）となる。ここで、ｎは、画像のピクセル数である。たとえば、１００×１００ピクセルの画像に比べて、２００×２００ピクセルの画像は、ピクセル数が４倍になっているため、探索時間は１６倍となってしまう。
【００５４】
そこで、本実施の形態では、探索のための時間コストを削減するために多重解像度画像群から成るピラミッドを導入する。これはローパスフィルタリングすることで構築される画像群であって、解像度が段階的に異なる複数の画像群である。
【００５５】
多重解像度画像群のピラミッドを作るにあたり、ローパスフィルタにガウシアンフィルタを用いたものを特にガウシアンピラミッドと呼ぶ。１次元の範囲５（ｍ＝−２，−１，０，１，２）のガウシアンフィルタカーネルｗ（ｍ）は以下の式（１）のように定義される。
【００５６】
【数１】
2006332785.tif 000003
ｌ（エル）段目の画像を
【数２】
2006332785.tif 000004
とすると、２次元のガウシアンフィルタカーネルｗ（ｍ，ｎ）によって、ローパスフィルタリングは次の式（２）で与えられる。
【００５７】
【数３】
2006332785.tif 000005
ここで、ａの値は本実施の形態では、ａ  ＝  １／２としたため、５×５のガウシアンフィルタカーネルが実質的には３×３となっている。
【００５８】
ガウシアンピラミッドを使った探索のイメージ図が、図１に示されている。この図１の（１）において、矢印はダウンサンプリングを表す。Ｌｅｖｅｌ＝０が原入力画像を表し、Ｌｅｖｅｌ＝１が１段階解像度を落とした画像を表す。ここでは、縦横共に１／２にした画像（ピクセル数は１／４）がＬｅｖｅｌ＝１である。さらに、Ｌｅｖｅｌ＝２は２段階解像度を落とした画像を表す。ここでは、画像の大きさを縦横共にさらに１／２にした画像をＬｅｖｅｌ＝２としている。この結果、Ｌｅｖｅｌ＝２の画像は、原入力画像に比べて、大きさが縦横共に１／４であり、ピクセル数は１／１６となっている。
【００５９】
図１（１）において、各レベルの画像中、小さな矩形はそのレベルの画像内のソースフラグメントの位置を表す。また、大きな矩形は探索領域を表す。そして低解像度の画像から高解像度の画像へと探索が進む。これら領域を示す矩形の様子をわかりやすく示したのが図１（２）である。この図１（２）は、図１（１）中の矩形のみを取り出して示した図である。この図１（２）において、小さな矩形（１つ解像度の低いレベルでのソースフラグメントの位置を表す）は太線で示されており、大きな矩形（探索領域を示す）は、破線による矩形で示されている。この図１（２）から明らかなように、本実施の形態では、低解像度の画像で得られたソースフラグメントの位置とその近傍のみが、それより１段高い解像度における探索領域となっている。この結果、探索領域を実質的に狭くすることができ、探索時間の低減を図ることができる。
【００６０】
装置構成
本実施の形態における画像補完装置１０の構成図が図２に示されている。図２に示すように、多重解像度画像群のピラミッド生成手段１２と、制御手段１４と、探索手段１６と、補完手段１８と、記憶手段２０と、表示手段２２と、ディスプレイ２４と、ポインティングデバイスであるマウス２６と、テクスチャ分類マップ生成手段２８とから構成されている。これらのうち、各「手段」は、一般に専用のハードウェアを用いて構成することが速度の点からは好ましいが、画像の大きさが小さい場合等においては、一般的なコンピュータとそのコンピュータに以下の動作を実行させるプログラムを実行させて各手段を構成することも好ましい。以下の説明は、このような構成の画像補完装置１０を前提としたものである。
【００６１】
本実施の形態で提案するガウシアンピラミッドを使ったソースフラグメント探索の高速化アルゴリズムは以下の４種のステップからなる。
【００６２】
（ステップ１）
入力画像とマスク画像に繰り返しダウンサンプリングを施して、ガウシアンピラミッドを構築する。この結果、第０レベルの画像から、・・・第ｎレベルの画像までｎ＋１レベルの解像度が異なる画像群が得られる。ここで、ｎは２以上の整数である。そして、第ｎレベルが最も粗い画像であり、第０レベルの画像が最高解像度、すなわち入力画像そのものである。同様に、第０レベルから第ｎレベルまでマスク画像も解像度の異なる画像を生成する。なお、本実施の形態においてｎは正の整数である。  このような動作は、多重解像度画像群のピラミッド生成手段１２が実行する。なお、入力画像は、図２においては直接多重解像度画像群のピラミッド生成手段１２に供給されているが、記憶手段２０に格納しておき、多重解像度画像群のピラミッド生成手段１２がこれを取り出すように構成することも好ましい。また、上述したように多重解像度画像群のピラミッド生成手段１２は専用のＬＳＩを構築してもよいし、コンピュータが所定のプログラムを実行することによって実現しても好ましい。この場合、そのプログラムは、記憶手段２０に格納しておくことが好ましい。
【００６３】
また、多重解像度画像群のピラミッド生成手段１２は生成したガウシアンピラミッドを、記憶手段２０に格納しておく。そして、後述する各手段がこの記憶手段２０に格納されたガウシアンピラミッドを適宜利用するのである。記憶手段２０は、各種記憶手段が利用可能であり、半導体記憶手段でもよいし、ハードディスク等の磁気記憶手段でもよい。また、各種光ディスクで構成してもよい。
【００６４】
なお、ｎは、制御手段１４が決定する。制御手段１４は、入力画像の大きさからこのｎを決定し、各手段に供給する。そのため、入力画像は、多重解像度画像群のピラミッド生成手段１２だけでなく、この制御手段１４にも供給される。
【００６５】
さらに、多重解像度画像群のピラミッド生成手段１２は、請求の範囲における多重解像度入力画像生成手段と、多重解像度マスク画像生成手段と、の好適な一例に相当する。
【００６６】
（ステップ２）
次に、最も粗い第ｎレベルの画像において、全領域で探索を行い、第ｎレベルのターゲットフラグメントとの類似度が最小の（最適な）フラグメントの位置を得る。これを第１レベルの最適フラグメントと呼ぶ。ターゲットフラグメントを選択するアルゴリズムは上記非特許文献４と同様である。
【００６７】
なお、本実施の形態（本特許）において類似度は、類似していればいるほど値が小さくなり、類似していなければいないほど値は大きくなるものである。この値は、「相違度」と呼ぶ方が人間の感覚には合致するかもしれない。
【００６８】
この動作は、図２の探索手段１６が実行する。探索手段１６は記憶手段２０内の第ｎレベルの画像を取り出し、上記処理を実行する。探索手段１６は、専用のＬＳＩを構築してもよいし、コンピュータが所定のプログラムを実行することによって実現しても好ましい。この場合、そのプログラムは、記憶手段２０に格納しておくことが好ましい。
【００６９】
（ステップ３）
次に、１段階下の第ｎ−１レベルにおいて、第ｎ−１レベルのターゲットフラグメントと類似度が最小のフラグメントを探索する。
【００７０】
本実施の形態において特徴的なことは、この第ｎ−１レベルの探索においては、１段階上の第ｎレベルの最適フラグメント（ソースフラグメントとして最適なフラグメント）の位置の近傍に、探索範囲を限定しているのである。本実施の形態において特徴的なことは、このように探索範囲を限定することによって探索効率を向上させて、計算速度を向上させたことである。この結果、従来に比べて迅速に類似度が最も小さい（＝最も似ている）フラグメントを見つけることが可能である。この様子は、既に図１に示されている。この図１に示すように、粗いレベルにおける最適フラグメントの近傍が細かいレベルにおける探索範囲となるのである。
【００７１】
具体的に言えば、上記第ｎレベルの最適フラグメントの位置と同等の位置のフラグメントを第ｎ−１レベルの画像から見つけ出し、さらに、その見つけ出したフラグメントの８近傍のフラグメントを探索範囲としたのである。その結果、第ｎ−１レベルにおいては、見つけ出した最適フラグメント＋８近傍の合計９個の候補の中から最も類似度の小さい（最も似ている）フラグメントを見つけ出すという作業を行うことになる。なお、８近傍とは、上方向に１ピクセルずらした位置、上右方向に１ピクセルずらした位置、右方向に１ピクセルずらした位置、右下方向に１ピクセルずらした位置、下方向に１ピクセルずらした位置、下左方向に１ピクセルずらした位置、左方向に１ピクセルずらした位置、左上方向に１ピクセルずらした位置、の８個を意味する。
【００７２】
このような動作は、探索手段１６が制御手段１４からの指示に基づき実行する。ｎの値もこの制御手段１４が決定する。
【００７３】
（ステップ４）
以下、同様にして、第ｎ−２レベル、第ｎ−３レベル・・・、第０レベルまで同様の探索処理を繰り返す。この繰り返しの結果、最終的に第０レベル（入力画像のレベル、）における類似度が最も小さい（最も似ている）フラグメント（ソースフラグメント）を求めることが可能である。
【００７４】
この繰り返しの探索は、制御手段１４が繰り返しの指示を探索手段１６に発行することによって実行される。すなわち、制御手段１４は、請求の範囲の繰り返し手段の好適な一例に相当する。なお、この制御手段１４は、本実施の形態の画像補完の処理の流れを管理しており、入力画像からｎを決定する動作等も実行している。
【００７５】
本実施の形態において特徴的なことは、「探索」の処理を上記のステップ１〜４で行ったことであり、その他の処理は、従来技術と同様である。たとえば、ステップ４までに於いて求めたソースフラグメントを用いてターゲットフラグメントと置き換える「補完」の処理は補完手段１８が実行するが、この動作は従来の動作と同様である。また、補完後の画像や入力画像は一般に表示手段２２がディスプレイ２４に描画して表示するのが好ましいが、そのような表示の処理自体は従来技術と同様である。
【００７６】
そこで、以下、このようなステップからなる「探索」処理について検討する。
【００７７】
まず、上記ステップ１では、階層的に画像をダウンサンプリングしたガウシアンピラミッドを用いることで、探索領域とフラグメントの大きさを小さくしている。本実施の形態ではガウシアンピラミッドのレベルが１つ上がるたびに、縦横の解像度がそれぞれ２分の１、ピクセル数にして４分の１になっている。
【００７８】
次に、ステップ２は、画像全体を探索している唯一のレベルである。本実施の形態では、この最も粗いレベルでの「最適解」とその近傍に、最も細かいレベルでの最適解があることを仮定している。この仮定は、多くの場合において妥当な仮定であろう。
【００７９】
したがってテクスチャがつぶれてしまうほどピラミッドの段数を増やしてダウンサンプリングすることは好ましくない。本願発明者らの実験によれば、最も粗いレベルで縦横のピクセル数が縦横共に１００程度になるようにピラミッドの段数を決めることが好ましい。既に述べたようにこの段数を決定することは上記ｎを決定することと等価であり、この決定は制御手段１４が実行する。
【００８０】
たとえば、入力画像をダウンサンプリングによって縮小していき、縦又は横のいずれかが１００ピクセル未満となった時点における画像を最小の画像（＝第ｎレベルの入力画像）と決定することが好ましい動作の一例である。縦又は横が１００ピクセル程度の画像は、一般の写真のような画像を表現する場合に形状等を把握できる最小の解像度と考えられるからである。これより大きい場合は、計算時間の短縮化が十分に図れず、一方これより小さい場合はものの形状が把握できずに画像として意味をなさなくなる場合もあるからである。もちろん、画像の種類や用途に応じて、１００以外の他の基準値を採用することも好ましい。
【００８１】
ステップ３で、第ｎレベルより１つ細かい第ｎ−１レベルでの最適解とその近傍を探索している。この際に特徴的なことは、第ｎレベルにおいて見つけられたターゲットフラグメントの位置の近傍を、探索範囲としていることである。具体的には、探索対象は１つ粗いレベル（第ｎレベル）の最適解とその８近傍だけに限定したので、非常に限られた探索範囲となっている。この結果、探索処理を大幅に高速化することが可能である。
【００８２】
なお、上記の例では、最適フラグメントを１個だけでなく、所定のｋ個選ぶことも好ましい。ここで、ｋは２以上の整数である。つまり、類似度が小さい順（つまり似ている順）に所定のｋ個の候補を選ぶのである。この結果、処理時間は一般にｋ倍になるが、正しい解を選び出す確率は増すと考えられる。なお、このｋ個の候補は、各レベルにおける探索の度に、類似度が小さい順に上位のｋ個を選び出すことを意味する。
【００８３】
また、ステップ４においては、ステップ２における探索処理を最下位の解像度まで再帰的に繰り返す。つまり、ガウシアンピラミッドを使うことによって、最上位の一番粗いレベル（第ｎレベル）では全領域を探索しなければならないが、その他のレベルでは上のレベルでの最適解の近傍ピクセルのみを探索すればよい。
【００８４】
本実施の形態によれば、高解像度の画像でも、ピラミッドの段数を増やすことで計算量の増加を大幅に抑えることができる。このような利点がある一方で、粗いレベルの最適解の近傍に細かいレベルでの最適解があるという仮定は一般的には正しくない場合もあり得るので、最も細かい画像だけで探索した場合に見つけられる最適解（真の最適解）が常に得られるという保証はない。しかしながら、一般的には、十分に高い確率で最適解が見つかることが経験上知られている。また、上述したｋを適宜大きな数として選択することによって最適解を見つける可能性を高めることが可能である。
【００８５】
ただし、探索の目的は十分に自然なフラグメントを見つけてくることであるので、必ずしも（数値的に）最適である必要はない。したがって、本実施の形態によれば、肉眼上自然に見える補完を実現しつつ、高速に補完を処理を行うことが可能である。
【００８６】
なお、上記ステップ１〜ステップ４は、１個のフラグメントの補完に関する動作である。マスク領域は一般に複数のフラグメント（ターゲットフラグメント）から構成されるので、上記処理を各ターゲットフラグメントに対して順次実行することによって、画像の補完が完了する。
【００８７】
２−２．  ガウシアンピラミッドを用いた場合の計算量に関する考察
次に、上で説明した探索手法に要する計算量について検討する。
【００８８】
まずステップ１におけるガウシアンピラミッドの作成について考える。各ピクセル値の計算に、近傍３×３（又は５×５）ピクセルを用いるので１段の計算量はＯ（ｎ）となる。一方ピラミッドの段数は、最も粗いレベルの解像度を固定するとｌｏｇｎに比例する。結局、ピラミッド作成のコストはＯ（ｎｌｏｇｎ）となる。なお、実際に本実施の形態で計算したピラミッドの段数は３段ないし４段であった。
【００８９】
次にステップ２における最も粗いレベルでの探索について検討する。本実施の形態では最も粗いレベルとして縦横のピクセル数が１００弱となるようにガウシアンピラミッドの段数を決めている。すなわち本来の画像のピクセル数によらずほぼ同数のピクセルを探索することとなり、このステップの計算量はＯ（１）と考えられる。
【００９０】
最後にステップ３〜４におけるより細かいレベルでの探索について検討する。ここでは前のレベルでの最適解とその８近傍を探索対象とするため、探索領域は常に一定である。フラグメントの大きさは１段下がるごとに４倍となる。したがって最も細かいレベルでの計算コストが支配的となる。最下段でのフラグメントサイズはｎに比例するので、このステップの計算量はＯ（ｎ）となる。したがって提案する探索アルゴリズムの計算量は全体としてＯ（ｎｌｏｇｎ）で抑えられる。
【００９１】
２−３．  テクスチャ分類マップによる画質の維持
以上述べたように、ガウシアンピラミッドを使うことで、計算の高速化が図れるが、同時に不適切なフラグメントを選択する可能性が多少生じる。
【００９２】
本願発明者らがいくつかの実験を行った結果、異質なテクスチャを合成することもごく希に発生した。また、その結果、見た目の自然さが多少損なわれる場合も希に生じた。なお、この結果については、処理時間及び処理結果の節でさらに詳述する。
【００９３】
そこで、探索領域を適切なテクスチャ部分のみに制限することで、処理結果の質の向上が期待できることが考えられる。ところで、本実施の形態では、最終的に求めているのは人間にとって自然な補完画像である。したがって、上記「適切なテクスチャ部分」としては、人間が似ていると判断するようなテクスチャを用いることが望ましいと考えられる。そこでユーザが元の画像を、そのテクスチャに基づき色で塗り分けた画像を第3の入力として使用する。この「色で塗り分けた画像」をテクスチャ分類マップと呼ぶ。
【００９４】
より詳細に言えば、このテクスチャ分類マップは、利用者（人間）が、「同様の」テクスチャであると判断した領域ごとに色分けを施したマップである。
【００９５】
このマップの入力は、利用者がディスプレイ２４の画面上でマウス２６を利用して所定の領域を指定することによって行うことが好ましい。すなわち、表示手段２２が入力画像をディスプレイ２４に表示する。そして、利用者にこの入力画像の上で所定の領域をマウスカーソルで「なぞらせる」等の操作を行わせて所定の領域を入力させるのである。
【００９６】
また、各領域の色の指定等は従来の画像処理の基本的な操作手法を利用すれば十分に実施可能である。たとえば、ディスプレイ２４の画面上に色のパレットを表示させ、利用者がマウス２６で希望の色彩を選択するように構成してもよい。
【００９７】
なお、マウス２６やディスプレイ２４、表示手段２２は、請求の範囲のテクスチャ領域取り込み手段の好適な一例に相当する。また、このようにして利用者が入力した領域や色彩などに基づきテクスチャ分類マップを実際に構築する手段として、テクスチャ分類マップ生成手段２８が設けられている。このテクスチャ分類マップ生成手段２８は、入力画像と同様の大きさの画像であって、各ピクセルには指定された上記「色」の情報が格納されている画像である。このテクスチャ分類マップ生成手段２８は、生成したテクスチャ分類マップを記憶手段２０に格納しておく。この結果、探索手段６等はテクスチャ分類マップを記憶手段２０から取り出して利用することができる。
【００９８】
なお、ここでは、色を用いているが、領域を識別できる識別子であればどのようなものでもよい。ただし、利用者に対して表示をする場合は、「色」で分けられていた方が識別がしやすいので、識別子の情報を適宜色彩の情報に変換して表示をすることが好ましい。
【００９９】
また、テクスチャ分類マップ生成手段２８は、専用のＬＳＩ等のハードウェアで構成することが好ましいが、汎用的なコンピュータとこのコンピュータが実行するプログラムとから構成することも好ましい。また、この場合、そのプログラムは、記憶手段２０に格納しておくことが好ましい。
【０１００】
あるターゲットフラグメントと類似しているソースフラグメントの探索に際しては、第３の入力画像である上記テクスチャ分類マップにおいて前記ターゲットフラグメントに対して指定されている色と同一の色が付されている領域のみを探索するのである。
【０１０１】
利用者がテクスチャを塗り分けた画像であるテクスチャ分類マップの一例が図４に示されている。図４においては、本願発明者がＦｉｒｅｐｌｕｇＳと呼ぶ画像の例が示されている。図４（１）においては、元のＦｉｒｅｐｌｕｇＳの画像が示されている。図４（２）には、このＦｉｒｅｐｌｕｇＳに対して用意したマスク画像が示されている。この図４（２）において黒の部分が「マスク」であり、このマスクが図４（１）の元の入力画像から除去したいマスク領域を指定している。すなわち、この図４の例においては、採水口をマスク領域に指定して、植物によって補完されることを期待したものである。
【０１０２】
図４（３）には、利用者が入力したテクスチャ分類マップが、（１）の入力画像と重ねられた状態が示されている。この図３（３）に示されている例では、利用者は、テクスチャが似ている部分を植物の部分とコンクリート壁の上端部とに分けて指定している。すなわち、垣根の植物の部分を同一のテクスチャであると判断し、この領域を入力したのである。この例ではこの植物の領域に「赤」が付されている。また、図４（３）の例では、利用者は、コンクリート壁の上端部を同一のテクスチャであると判断した。利用者はこのコンクリートの上端部分の領域を２領域指定している。この例では、この部分の領域に「青」が付されている。これによってこの２個の領域は共に同一のコンクリート上端部の領域というテクスチャ領域であることを利用者は指定したことになる。
【０１０３】
図４（４）には、本実施の形態で説明した手法によって補完した画像が示されている。図４（１）に比べて、マスク領域（すなわち、左側の採水口）が除去され、除去された後が見た目に自然に補完されている。この図４（４）で示した結果は、今まで述べたようにガウシアンピラミッドを探索して見つけたフラグメントを用いて補完を行っている。また、この探索の際には図４（３）で示したテクスチャ分類マップによる一定のテクスチャ領域に限定した探索を行っている。
【０１０４】
なお、このテクスチャ分類マップもガウシアンピラミッド同様に低解像度から高解像度の複数の解像度の画像群、すなわち「ピラミッド」にして用いる。これは、上述した各レベルにおける探索において、このテクスチャ分類マップを利用することを意味している。テクスチャ分類マップによって自然な結果が得られるだけではなく、探索範囲が狭くなるため、計算時間の短縮という効果もある。具体的な効果について、実験結果とともに後に詳述する。
【０１０５】
なお、表示手段２２は、ビデオカードや所定のドライバーソフトウェアなどからなり、ディスプレイ２４に画像を表示する手段である。ディスプレイ２４は、液晶表示装置や、ＣＲＴ等で構成されるディスプレイであり、利用者が実際に肉眼で見る画像を表示する部分である。また、本実施の形態では、マウス２６を用いたが、所定の領域を指定できれば他の手段、他のポインティングデバイスを用いることも好適である。
【０１０６】
２−４．  処理時間
これまで述べた本実施の形態で提案する手法に基づき、コンピュータプログラムを構成し、コンピュータによる画像補完処理を実行した。実行した結果が表１に示されている。
【０１０７】
本実施の形態では、およそ１００万ピクセルレベルの画像に関しては、画像補完処理を実行した。コンピュータはＰｅｎｔｉｕｍ（登録商標）４の２．８ＧＨｚ版ＣＰＵを用いたＰＣ（パーソナルコンピュータ）を使って画像補完処理を実行した。その結果、見た目に自然な処理結果をおよそ数分で得ることができた。上述した非特許文献４とは、計算環境及び細部の手法が異なるので直接的な比較はできないが、参考のため、表１中には、本実施の形態の結果と共に従来例として非特許文献４の結果も引用している。
【０１０８】
【表１】
2006332785.tif 000006
この表１において、ｉｍａｇｅは、処理した画像（入力画像として用いている）の種別を表す。具体的な画像は、後に詳述する。また、表１中、ｗは画像の幅のピクセル数、ｈは画像の高さにのピクセル数、をそれぞれ表す。また、ａは入力画像とマスク領域の面積比（％）を表し、ｔは処理時間（秒）をそれぞれ表す。
【０１０９】
非特許文献４では、計算時間はピクセル数ｎに関してＯ（ｎ＾２）で増加する。
【０１１０】
この理由は、以下の通りである。まず、探索時間は、探索領域とフラグメントサイズの値の両方に比例することは明らかであろう。探索領域は、当然ピクセル数そのものであるのでピクセル数ｎに比例する。また、フラグメントサイズは、ピクセル数が大きくなれば、それに比例して大きくすべきであろうことは自明であろう。その結果、探索時間に関しては、ピクセル数ｎの２乗に比例する。さらに、本願発明者らの実験によれば計算時間のほとんどがフラグメントの探索に使われることが判明した。したがって、計算時間はピクセル数ｎに関してＯ（ｎ＾２）で増加する。
【０１１１】
たとえば、表１に示すように、本実施の形態で提案する手法のＦｉｒｅｐｌｕｇＳは、７６８×５１２ピクセルの画像であるので、先行研究である非特許文献４に記載されている１９２×１２８の画像であるＰｙｒａｍｉｄの画像より、ピクセル数が１６倍となる。したがって、計算時間がピクセル数ｎの２乗に比例するとの仮定に基づけば、上記の計算時間は２５６倍（＝１６×１６）の３３，０２４秒（＝約９時間）程度かかると予想される。
【０１１２】
しかし、マスク領域がほぼ同じ大きさである非特許文献４に記載されたＰｙｒａｍｉｄと本実施の形態のＦｉｒｅｐｌｕｇＳの計算時間を比較すると、表１に示すように、後者の計算時間は３１秒になっている。したがって、大幅な速度の向上が図られていると考えられる。
【０１１３】
なお、Ｐｙｒａｍｉｄは、非特許文献４に記載されている画像であるので、実際の画像は非特許文献４に当たられたい。
【０１１４】
また、計算時間は使用しているコンピュータの性能にも大きく依存するが、非特許文献４の発表時点と、本願出願時点とでは、わずかな期間しか違わないので、使用しているコンピュータの性能がそれほど大幅に異なるとは考えにくい。そのため、表１に示されている計算速度の差は、ほとんどがアルゴリズムの相違に基づくものと考えるのが妥当である。
【０１１５】
本実施の形態において、この高速化が達成できた主な理由としては、３点挙げられる。
【０１１６】
第１の理由は、ガウシアンピラミッドの採用である。これについてはガウシアンピラミッドの特徴として先に議論したが、探索時間コストをＯ（ｎ＾２）からＯ（ｎｌｏｇｎ）に低減することに成功している。
【０１１７】
第２の理由は、テクスチャ分類マップである。ただしテクスチャ分類マップが高速化に寄与するのはガウシアンピラミッドで最も粗いレベルでの探索のみである。実際にテクスチャ分類マップの有無に関して実験を行った結果図３からも明らかなように、このマップによる計算時間への影響は数パーセント程度に過ぎない。図３には、本実施の形態による手法において、ガウシアンピラミッドを用いた場合と、ガウシアンピラミッドに加えてテクスチャ分類マップによる探索領域の限定を行った場合と、の計算時間を比較するグラフが示されている。このグラフにおいて縦軸は処理時間（秒）を表し、横軸は、画像の種類を表す。このグラフにおいてＡは、本願発明者がＧａｒｄｅｎと呼ぶ画像についてテクスチャ分類マップを利用した場合の処理時間であり、Ａ’は、同画像についてテクスチャ分類マップを利用しない場合の処理時間である。また、Ｂは、本願発明者がＴｏｗｎと呼ぶ画像についてテクスチャ分類マップを利用した場合の処理時間であり、Ｂ’は、同画像についてテクスチャ分類マップを利用しない場合の処理時間である。また、Ｃは、本願発明者がＧｕａｒｄｉａｎ  Ｄｏｇと呼ぶ画像についてテクスチャ分類マップを利用した場合の処理時間であり、Ｃ’は、同画像についてテクスチャ分類マップを利用しない場合の処理時間である。また、Ｄは、本願発明者がＦｉｒｅｐｌｕｇＳと呼ぶ画像についてテクスチャ分類マップを利用した場合の処理時間であり、Ｄ’は、同画像についてテクスチャ分類マップを利用しない場合の処理時間である。また、Ｅは、本願発明者がＲｉｖｅｒと呼ぶ画像についてテクスチャ分類マップを利用した場合の処理時間であり、Ｅ’は、同画像についてテクスチャ分類マップを利用しない場合の処理時間である。各画像については後に詳述する。
【０１１８】
さて、高速化が達成できた第３の理由は、本実施の形態では、アルゴリズムの細部において、必ずしも非特許文献４と全く同じアルゴリズムを用いたわけではないことである。たとえば、本実施の形態では非特許文献３と異なり、フラグメントサイズは一定とした。また、非特許文献４と異なり、回転や鏡映変換を施した画像は探索に用いていない。ただし、このような差異の影響があってもそれは高々数倍程度に過ぎないと予想される。本実施の形態によれば、表１に示したように、非特許文献４に比べて、３桁程度の高速化に成功しているので、第３の理由だけでは、この高速化の説明はほとんどつかない。
【０１１９】
したがって、以上述べた点を考慮すれば、本実施の形態における高速化の主要な要因は、ガウシアンピラミッドによる効果であると考えられる。
【０１２０】
第３章  処理結果画像
画像補完手法の評価に当たって、得られた画像がどれだけ人間の見た目にもっともらしく自然な画像であるかは、重要なポイントである。本来ならば定量的にその効果を検証することが望ましいが、人間にとっての自然さを簡単に数値化して測ることは難しく、テクスチャ合成などでも適当な指標は存在しない。たとえば、ある自明な画像の一部をマスク領域として指定し、元の画像と等しく補完できるかを性能の指標とすることが考えられる。ここで与えられるテクスチャとして1ピクセル間隔の縦縞を考える。全く同じ縦縞であれば本実施の形態で用いた類似度は最適となる。一方1ピクセル横にずれた縦縞、すなわち本来の縦縞が反転したものは、類似度は最悪となるが、人間には似た画像と感じられるだろう。
【０１２１】
ここで、本実施の形態で用いた類似度とは、以下のようにして求める。
【０１２２】
まず、フラグメント内の対応する位置にあるピクセル同士の差異ｄ（ｓ，ｔ）を調べる。ここで、ｓはソースフラグメント、ｔはターゲットフラグメントを表しており、対応するソースとターゲットの差異を表す。ここで、差異ｄ（ｓ，ｔ）は、入力画像のＲＧＢ値，明度，明度の垂直勾配と水平勾配それぞれの差を大きさ１に正規化し，Ｌ１ノルムを取り、さらに正規化を施したものである。具体的には、以下のように計算する。
【０１２３】
【数４】
2006332785.tif 000007
ここで、Ｒ＿ｓはソースフラグメントのＲ値であり、Ｒ＿ｔはターゲットフラグメントのＲ値である。また、Ｇ＿ｓはソースフラグメントのＧ値であり、Ｇ＿ｔはターゲットフラグメントのＧ値である。Ｂ＿ｓは、ソースフラグメントのＢ値であり、Ｂ＿ｔはターゲットフラグメントのＢ値である。Ｌ＿ｓはソースフラグメントの明度であり、Ｌ＿ｔはターゲットフラグメントの明度である。ＧＶ＿ｓはソースフラグメントの明度の垂直勾配であり、ＧＶ＿ｔはターゲットフラグメントの明度の垂直勾配である。ＧＨ＿ｓはソースフラグメントの明度の水平勾配であり、ＧＨ＿ｔはターゲットフラグメントの明度の水平勾配である。
【０１２４】
次に，信頼度の影響を考慮したうえで、上記差異をフラグメント内の全てのピクセル分足し合わせた値を、当該フラグメント同士の類似度の値であるＦｒａｇｍｅｎｔＤｉｆ（Ｓ，Ｔ）とする。これが本実施の形態における類似度である。
【０１２５】
なお、類似度としては、従来から知られている種々の尺度を利用することが可能である。
【０１２６】
入力画像、マスク画像、テクスチャ分類マップ、及び処理結果の例として、既に図４を説明したが、同様な例として図５を示す。図５においては、本願発明者がＧａｒｄｅｎと呼ぶ画像の例が示されている。図５（１）においては、元のＧａｒｄｅｎの画像が示されている。図５（２）には、このＧａｒｄｅｎに対して用意したマスク画像が示されている。このように、Ｇａｒｄｅｎでは、「琉」の字の部分をマスク領域として、花が土手のテクスチャで補完されることを期待したのである。図５（３）には、利用者が入力したテクスチャ分類マップが、（１）の入力画像と重ねられた状態が示されている。
【０１２７】
この図５（３）に示されている例では、利用者は、マスク領域は土手のテクスチャのみなので、探索領域として１個の領域のみを指定した。この結果、テクスチャ分類マップにおいて指定された領域は「赤」の単色で指定した。図５（４）には、本実施の形態で説明した手法によって補完した画像が示されている。すべてが草になるわけではなく砂地の部分も現れるなど、それなりにもっともらしく補完されたと言えよう。
【０１２８】
表１に示した他の画像の処理結果も示そう。どの画像においてもおおむね自然に補完されている。
【０１２９】
図６においては、本願発明者がＴｏｗｎ（表１参照）と呼ぶ画像の例が示されている。図６（１）においては、元のＴｏｗｎの画像が示されている。図６（２）には、このＴｏｗｎに対して用意したマスク画像が示されている。このように、Ｔｏｗｎでは、自転車の部分をマスク領域として、道路や川岸のテクスチャで補完されることを期待したのである。図６（３）には、利用者が入力したテクスチャ分類マップが、（１）の入力画像と重ねられた状態で示されている。
【０１３０】
この図６（３）に示されている例では、利用者は、マスク領域には、川、川岸、道路の３種類のテクスチャが含まれていると判断した。そのため、探索領域として３個の領域を指定している。図６（３）に示すように、川の領域は「赤」で示され、川岸の領域は「青」で示され、道路の領域は「黄色」で示した。図６（４）には、本実施の形態で説明した手法によって補完した画像が示されている。テクスチャが似ている部分が多いので、肉眼上ほとんど違和感なく補完されていると言えよう。
【０１３１】
図７においては、本願発明者がＧｕａｒｄｉａｎ Ｄｏｇ（表１参照）と呼ぶ画像の例が示されている。図７（１）においては、元のＧｕａｒｄｉａｎ Ｄｏｇの画像が示されている。図７（２）には、このＧｕａｒｄｉａｎ Ｄｏｇに対して用意したマスク画像が示されている。このように、Ｇｕａｒｄｉａｎ Ｄｏｇでは、建築物の前に置かれたシーサーの部分をマスク領域として、このシーサーを背景である石垣や建物及び庭のテクスチャで補完されることを期待したのである。図７（３）には、利用者が入力したテクスチャ分類マップが、（１）の入力画像と重ねられた状態で示されている。
【０１３２】
この図７（３）に示されている例では、利用者は、マスク領域には、建物、石垣、庭の３種類のテクスチャが含まれていると判断した。そのため、探索領域として３個の領域を指定している。図７（３）に示すように、建物の領域は「赤」で示され、石垣の領域は「青」で示され、庭の領域は「黄色」で示した。図７（４）には、本実施の形態で説明した手法によって補完した画像が示されている。このように、シーサーが除去された画像が、肉眼上ほとんど違和感なく補完されていると言えよう。
【０１３３】
図８においては、本願発明者がＲｉｖｅｒ（表１参照）と呼ぶ画像の例が示されている。図８（１）においては、元のＲｉｖｅｒの画像が示されている。図８（２）には、このＲｉｖｅｒに対して用意したマスク画像が示されている。このように、Ｒｉｖｅｒでは、川縁にたたずむ人の部分をマスク領域として、この人を削除し、背景である川や川原のテクスチャで補完されることを期待したのである。図８（３）には、利用者が入力したテクスチャ分類マップが、（１）の入力画像と重ねられた状態で示されている。
【０１３４】
この図８（３）に示されている例では、利用者は、マスク領域には、向こう岸の森、川、川原の３種類のテクスチャが含まれていると判断した。そのため、探索領域として３個の領域を指定している。図８（３）に示すように、森の領域は「赤」で示され、川の領域は「青」で示され、川原の領域は「黄色」で示した。図８（４）には、本実施の形態で説明した手法によって補完した画像が示されている。このように、人物が除去された画像が、肉眼上自然な感じで得られ、良好に補完されていると言えよう。
【０１３５】
テクスチャ分類マップの画質に及ぼす効果
画質に対するテクスチャ分類マップの効果についても実験を行った。画像補完を完了するまでに合成したフラグメントの類似度の総和（総類似度）の変化を測定した。図９には、テクスチャ分類マップを用いた場合と用いなかった場合の総類似度の値を表すグラフが示されている。このグラフにおいて、縦軸は総類似度であり、横軸は画像の種類及びテクスチャ分類マップの利用の有無を表す。横軸において、Ａは画像Ｇａｒｄｅｎについてテクスチャ分類マップを用いた場合であり、Ａ’は同じく画像Ｇａｒｄｅｎについてテクスチャ分類マップを用いなかった場合である。また、Ｂは画像Ｔｏｗｎについてテクスチャ分類マップを用いた場合であり、Ｂ’は同じく画像Ｔｏｗｎについてテクスチャ分類マップを用いなかった場合である。また、Ｃは画像Ｇｕａｒｄｉａｎ  Ｄｏｇについてテクスチャ分類マップを用いた場合であり、Ｃ’は同じく画像Ｇｕａｒｄｉａｎ  Ｄｏｇについてテクスチャ分類マップを用いなかった場合である。また、Ｄは画像ＦｉｒｅｐｌｕｇＳについてテクスチャ分類マップを用いた場合であり、Ｄ’は同じく画像ＦｉｒｅｐｌｕｇＳについてテクスチャ分類マップを用いなかった場合である。また、Ｅは画像Ｒｉｖｅｒについてテクスチャ分類マップを用いた場合であり、Ｅ’は同じく画像Ｒｉｖｅｒについてテクスチャ分類マップを用いなかった場合である。
【０１３６】
図９に見られるように、テクスチャ分類マップによって総類似度が大きく改善しているわけではない。しかし、場合によってはテクスチャ分類マップを用いないと画質が著しく劣化することがある。これに対して、テクスチャ分類マップを用いることで、画質が良好となる確率を高めることができる。すなわち、よい場合をさらによくする効果は希薄であるが、悪い場合を減らす効果は大きいと考えられる。
【０１３７】
この典型的な例が図１０に示されている。図１０にはテクスチャ分類マップの利用の有無による処理結果の違いを比較した例が示されている。図１０（１）は、画像ＦｉｒｅｐｌｕｇＳについてテクスチャ分類マップを用いた場合であり、図１０（２）は同じく画像ＦｉｒｅｐｌｕｇＳについてテクスチャ分類マップを用いなかった場合である。図９に示すように、総類似度はほとんど同じ値であるが、見た目上、図１０（２）の方にやや不自然な点が見られる。
【０１３８】
また、図１０（３）は、画像Ｇａｒｄｅｎについてテクスチャ分類マップを用いた場合であり、図１０（４）は同じく画像Ｇａｒｄｅｎについてテクスチャ分類マップを用いなかった場合である。図９に示すように、総類似度はほとんど同じ値であるが、見た目上、図１０（４）の方は、花が残存してしまい、花を除去しようとする目的が十分に達成されてはいない。
【０１３９】
また、本実施の形態によれば、処理が十分に速いので、望みどおりの結果が得られない場合はテクスチャ分類マップの指定を変えて結果を調整することも可能である。
【０１４０】
第４章  終言
以上述べたように本実施の形態においては、まとまった広い領域も自然に補完できるフラグメントベース画像補完法を基本とし、その補完結果の自然さを保ちつつ、高解像度の画像を実用的な時間で処理することが可能となった。
【０１４１】
これを実現するために、本実施の形態では、
（１）ガウシアンピラミッドによる探索の高速化、及び
（２）人間によるテクスチャ分類をもとにした探索領域指定
を導入した。ガウシアンピラミッドによる探索の高速化は、多重解像度の画像群を用いることによって、探索領域を大きく削減し、計算時間を大幅に短くすることができた。一方、人間によるテクスチャ分類をもとにした探索領域の指定は、人間がテクスチャを色で塗りわけし、同色の部分のみを探索対象とすることによって、探索領域を制限するとともに処理結果の不自然さを解消できるという効果をもたらした。
【０１４２】
本実施の形態では両手法を組み合わせて計算機上に実装し、高解像度の画像の補完を行った。その結果、先行研究（非特許文献４）の特長である補完結果の自然さを保ちながら、高解像度の画像を実用的な時間で処理できることを確認した。
【０１４３】
第５章  変形例
これまで説明してきた例では、解像度が異なる画像をガウシアンフィルタによって構築したが、段階的な解像度の画像が得られれば他の手法で画像を構築してもよい。たとえば他のフィルタを用いてもよい。また、本実施の形態では、縦方向又は横方向のピクセル数が１：２となるように各レベル間の画像の大きさを調整した（総ピクセル数では１：４）が、他の比率でもかまわない。
【０１４４】
また、上述した実施の形態では、テクスチャを色で塗り分けることを説明したが、各領域を区別できればどのような識別子を用いてもかまわない。単なる「１」「２」「３」のように番号で区別してもよい。ただし、表示上は色で塗り分けた方が肉眼上わかりやすくなるので好ましいであろう。
【０１４５】
また、これまでの説明では、
（１）ガウシアンピラミッドを利用した探索の高速化の例
（２）ガウシアンピラミッドを利用した探索の高速化＋テクスチャ分類マップを利用した画質の向上の例
を説明したが、テクスチャ分類マップのみを利用することも好ましいことは明らかであろう。すなわち、
（３）ガウシアンピラミッドを利用せずに、テクスチャ分類マップを利用した画質の向上の例
という構成を採用することも場合によっては好ましいことは言うまでもない。
【図面の簡単な説明】
【０１４６】
【図１】ガウシアンピラミッドを使った探索のイメージ図である。
【図２】本実施の形態における画像補完装置の構成図である。
【図３】本実施の形態による手法において、ガウシアンピラミッドを用いた場合と、ガウシアンピラミッドに加えてテクスチャ分類マップによる探索領域の限定を行った場合と、の計算時間を比較するグラフである。
【図４】ＦｉｒｅｐｌｕｇＳと呼ぶ画像を本実施の形態における画像補完処理を施した例を示す説明図であり、テクスチャ分類マップの一例も示されている。
【図５】Ｇａｒｄｅｎと呼ぶ画像を本実施の形態における画像補完処理を施した例を示す説明図である。
【図６】Ｔｏｗｎと呼ぶ画像を本実施の形態における画像補完処理を施した例を示す説明図である。
【図７】Ｇｕａｒｄｉａｎ Ｄｏｇと呼ぶ画像を本実施の形態における画像補完処理を施した例を示す説明図である。
【図８】Ｒｉｖｅｒと呼ぶ画像を本実施の形態における画像補完処理を施した例を示す説明図である。
【図９】テクスチャ分類マップを用いた場合と用いなかった場合の総類似度の値を表すグラである。
【図１０】テクスチャ分類マップの利用の有無による処理結果の違いを比較した説明図である。
【符号の説明】
【０１４７】
１０  画像補完装置
１２  多重解像度画像群のピラミッド生成手段
１４  制御手段
１６  探索手段
１８  補完手段
２０  記憶手段
２２  表示手段
２４  ディスプレイ
２６  マウス
２８  テクスチャ分類マップ生成手段
【図２】
2006332785.tif 000008
【図１】
2006332785.tif 000009
【図３】
2006332785.tif 000010
【図４】
2006332785.tif 000011
【図５】
2006332785.tif 000012
【図６】
2006332785.tif 000013
【図７】
2006332785.tif 000014
【図８】
2006332785.tif 000015
【図９】
2006332785.tif 000016
【図１０】
2006332785.tif 000017