(57)【要約】【課題】ピクセルのサンプリング点が一致していない２枚の画像を、リサンプリング処理を施すことなく結合する。【解決手段】  ステップＳ１で、入力された画像Ｘ，Ｙにグラフ構造を設定する。ステップＳ２で、グラフ構造のノードの平均密度を算出し、その値に応じて画像Ａ１，Ａ２とする。ステップＳ３で、画像Ａ１のグラフ構造のうち、画像Ａ２に重なっている領域をＡ３に決定する。ステップＳ４で、ソース／シンクノードを設定し、ステップＳ５で、ソース／シンクノードと領域Ａ３の外周上に位置する各ノードを連結する。ステップＳ６で、領域Ａ３の各ノードおよび各エッジ、並びにソース／シンクノードに連結したエッジのコストを算出する。ステップＳ７で、コストに基づき、Min-cut Max-flow問題を解く。本発明は、画像レタッチ、パノラマ画像生成、テクスチャ生成等の画像処理に適用することができる。【選択図】図８
2006003982.tif 000002
【特許請求の範囲】
【請求項１】
ピクセルのサンプリング点が一致していない２枚の画像を結合する画像処理装置において、
前記２枚の画像の重複領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定手段と、
前記２枚の画像のピクセルの画素値に基づき、前記重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出手段と、
前記算出手段によって算出された前記コストに基づき、前記重複領域を分断する分断ラインを取得する取得手段と、
前記分断ラインを境として、前記２枚の画像を結合する結合手段と
を含むことを特徴とする画像処理装置。
【請求項２】
前記グラフ構造設定手段は、前記２枚の画像に対してそれぞれ、三角形の領域の組み合わせであってノードとエッジから成るグラフ構造を設定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記グラフ構造設定手段は、前記２枚の画像に対してそれぞれ、アルファシェープを三角形分割したものを求め、三角形の領域の組み合わせであってノードとエッジから成るグラフ構造を設定する
ことを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記グラフ構造設定手段は、前記２枚の画像を前記ノードの平均密度について比較し、比較結果に基づいて前記２枚の画像の一方を第１の画像、他方を第２の画像に指定し、前記第１の画像のノードのみをエッジで連結しグラフ構造を設定する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記グラフ構造設定手段は、前記２枚の画像を前記ノードの平均密度について比較し、前記２枚の画像の前記平均密度の高い方を前記第１の画像、低い方を前記第２の画像に指定する
ことを特徴とする請求項４に記載の画像処理装置。
【請求項６】
前記算出手段は、前記重複領域のノードのコストとして、前記ノードに相当する前記第１の画像のピクセルの画素値と、前記第２の画像のピクセルのうちの前記ノードに最近接のピクセルの画素値との差を算出する
ことを特徴とする請求項４に記載の画像処理装置。
【請求項７】
前記第２の画像のピクセルのうちの前記ノードに最近接の前記ピクセルの決定には、ボロノイ多角形から構成されるボロノイ図を用いる
ことを特徴とする請求項６に記載の画像処理装置。
【請求項８】
前記取得手段は、前記算出手段によって算出された前記コストに基づき、Min-cut Max-flow問題を解くことによって、前記重複領域を分断する前記分断ラインを取得する
ことを特徴とする請求項１に記載の画像処理装置。
【請求項９】
ピクセルのサンプリング点が一致していない２枚の画像を結合する画像処理方法において、
前記２枚の画像の重複領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定ステップと、
前記２枚の画像のピクセルの画素値に基づき、前記重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出ステップと、
前記算出ステップの処理で算出された前記コストに基づき、前記重複領域を分断する分断ラインを取得する取得ステップと、
前記分断ラインを境として、前記２枚の画像を結合する結合ステップと
を含むことを特徴とする画像処理方法。
【請求項１０】
ピクセルのサンプリング点が一致していない２枚の画像を結合するためのプログラムであって、
前記２枚の画像の重複領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定ステップと、
前記２枚の画像のピクセルの画素値に基づき、前記重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出ステップと、
前記算出ステップの処理で算出された前記コストに基づき、前記重複領域を分断する分断ラインを取得する取得ステップと、
前記分断ラインを境として、前記２枚の画像を結合する結合ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項１１】
ピクセルのサンプリング点が一致していない２枚の画像を結合するためのプログラムであって、
前記２枚の画像の重複領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定ステップと、
前記２枚の画像のピクセルの画素値に基づき、前記重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出ステップと、
前記算出ステップの処理で算出された前記コストに基づき、前記重複領域を分断する分断ラインを取得する取得ステップと、
前記分断ラインを境として、前記２枚の画像を結合する結合ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および方法、記録媒体、並びにプログラムに関し、特に、複数の画像を結合して新たな画像を生成する場合に用いて好適な画像処理装置および方法、記録媒体、並びにプログラムに関する。
【背景技術】
【０００２】
例えば、山頂から眼下を見回したときの景色を１枚の画像（いわゆる、パノラマ画像）として生成する場合等においては、異なる方向を向けて撮影した複数の画像を結合して、パノラマ画像を生成することになる。また、パノラマ画像に限らず、複数の画像を連結して新たに画像を生成することは、一般的な画像処理としては非常に頻繁に行われている。
【０００３】
図１に示すように、２枚の画像Ｘ，Ｙを結合する場合、画像Ｘ，Ｙにおける被写体の大きさを揃えたり、被写体の向きを調整したりする必要があるので、例えば、図２に示すように、画像を拡大または縮小、変形、回転等の処理（以下、単に変形処理と記述する）が行われる。ただし、図２の場合は、画像Ｂだけを比較的規則性をもって回転・変形させているが、実際の変形処理においては、より複雑な形状に変形されることも多い。ここで、変形処理が施された画像をＹ’とする。
【０００４】
この回転・変形させる処理では、当該処理以前において通常では図１の画像Ｙ上に黒点で示されるサンプリング点の正方格子構造が、図２の画像Ｙ’上に黒点で示されるように、非正方格子構造に変形されることになる。なお、画像Ｘも同様に変形されることがある。
【０００５】
ところで、従来確立されている２枚の画像を結合する方法（例えば、Graphcut法。非特許文献１参照）では、重なった領域の格子点(サンプリング点)の位置が一致している場合にのみ、２枚の画像を結合することができる。したがって、図２に示された状態では、画像Ｙ’のサンプリング点が非正方格子構造なので結合することができないので、画像Ｘのサンプリング点に重なるように、図３に示すように、画像Ｙ’のサンプリング点を正方格子構造に変換して（以下、この変換の処理をリサンプリング処理と記述する）画像Ｙ”を生成し、Min-cut Max-flow問題を解くことにより、結合ラインを決定して画像Ｘ，Ｙ”を結合することになる。
【０００６】
【非特許文献１】Kwatra et al.“Graphcut textures: image and video synthesis using graph cuts” Siggraph2003 proceedings p.277-286
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述したように、画像Ｙ’にリサンプリング処理を施した場合、生成された画像Ｙ”の画質が劣化してしまうという課題があった。
【０００８】
この画像Ｙ”の画像劣化という問題を解決する方法としては、元の画像Ｙの解像度をできるだけ高くしておくという方法もあるが、その場合、画像Ｙ，Ｙ’，Ｙ”等を記憶するメモリの容量を大きくしなければならなかったり、解像度の高い画像Ｙを用意することができなかったりすることもあり得る等の課題があった。
【０００９】
本発明はこのような状況に鑑みてなされたものであり、サンプリング点が一致していない２枚の画像を、リサンプリング処理を施すことなく結合できるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
本発明の画像処理装置は、２枚の画像の重複領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定手段と、２枚の画像のピクセルの画素値に基づき、重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出手段と、算出手段によって算出されたコストに基づき、重複領域を分断する分断ラインを取得する取得手段と、分断ラインを境として、第１および第２の画像を結合する結合手段とを含むことを特徴とする。
【００１１】
前記グラフ構造決定手段は、２枚の画像に対してそれぞれ、各ピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定手段と、グラフ構造が設定された２枚の画像の一方を第１の画像、他方を第２の画像に指定する指定手段と、第１および第２の画像を結合する位置に配置したとき、第１の画像に設けられたグラフ構造の領域であって、かつ、第２の画像と重なり合う領域を重複領域に決定する決定手段とを含むようにすることができる。
【００１２】
前記グラフ構造設定手段は、２枚の画像に対してそれぞれ、三角形の領域の組み合わせであってノードとエッジから成るグラフ構造を設定するようにすることができる。
【００１３】
前記グラフ構造設定手段は、２枚の画像に対してそれぞれ、アルファシェープを三角形分割したものを求め、三角形の領域の組み合わせであってノードとエッジから成るグラフ構造を設定するようにすることができる。
【００１４】
前記グラフ構造設定手段は、２枚の画像をノードの平均密度について比較し、比較結果に基づいて２枚の画像の一方を第１の画像、他方を第２の画像に指定し、第１の画像のノードのみをエッジで連結しグラフ構造を設定することができる。
【００１５】
前記グラフ構造設定手段は、２枚の画像を前記ノードの平均密度について比較し、２枚の画像の平均密度の高い方を第１の画像、低い方を第２の画像に指定することができる。
【００１６】
前記算出手段は、重複領域のノードのコストとして、ノードに相当する第１の画像のサンプリング点の画素値と、第２の画像のサンプリング点のうちのノードに最近接のサンプリング点の画素値との差を算出するようにすることができる。
【００１７】
第２の画像のサンプリング点のうちのノードに最近接の前記サンプリング点の決定には、ボロノイ多角形から構成されるボロノイ図を用いるようにすることができる。
【００１８】
前記取得手段は、算出手段によって算出されたコストに基づき、Min-cut Max-flow問題を解くことによって、重複領域を分断する分断ラインを取得するようにすることができる。
【００１９】
本発明の画像処理方法は、２枚の画像の重複領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定ステップと、２枚の画像のピクセルの画素値に基づき、重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出ステップと、算出ステップの処理で算出されたコストに基づき、重複領域を分断する分断ラインを取得する取得ステップと、分断ラインを境として、２枚の画像を結合する結合ステップとを含むことを特徴とする。
【００２０】
本発明の記録媒体のプログラムは、２枚の画像の重複領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定ステップと、２枚の画像のピクセルのサンプリング点の画素値に基づき、重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出ステップと、算出ステップの処理で算出されたコストに基づき、重複領域を分断する分断ラインを取得する取得ステップと、分断ラインを境として、２枚の画像を結合する結合ステップとを含むことを特徴とする。
【００２１】
本発明のプログラムは、２枚の画像が重なり合う領域において、原画像中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定ステップと、２枚の画像のピクセルの画素値に基づき、重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出ステップと、算出ステップの処理で算出されたコストに基づき、重複領域を分断する分断ラインを取得する取得ステップと、分断ラインを境として、第１および第２の画像を結合する結合ステップとを含む処理をコンピュータに実行させることを特徴とする。
【００２２】
本発明においては、２枚の画像に対してそれぞれ、各ピクセルをノードとし、それらがエッジで連結されたグラフ構造が設定され、グラフ構造が設定された２枚の画像の一方が第１の画像、他方が第２の画像に指定され、第１および第２の画像を結合する位置に配置したとき、第１の画像に設けられたグラフ構造の領域であって、かつ、第２の画像と重なり合う領域が重複領域に決定される。さらに、第１および第２の画像のサンプリング点の画素値に基づき、重複領域のノードおよびエッジにそれぞれ対応するコストが算出され、算出されたコストに基づき、重複領域を分断する分断ラインが取得され、分断ラインを境として、第１および第２の画像が結合される。
【発明の効果】
【００２３】
本発明によれば、ピクセルのサンプリング点が一致していない２枚の画像を、リサンプリング処理を施すことなく結合することが可能となる。
【発明を実施するための最良の形態】
【００２４】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００２５】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加されたりする発明の存在を否定するものではない。
【００２６】
請求項１に記載の画像処理装置（例えば、図４の画像処理装置１）は、
前記２枚の画像の重複領域において原画中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造（例えば、図５に示すグラフ構造）を設定するグラフ構造設定手段（例えば、図４のグラフ構造設定部２）と、
前記グラフ構造が設定された前記２枚の画像の一方を第１の画像（例えば、図６の画像Ａ１）、他方を第２の画像（例えば、図６の画像Ａ２）に指定する指定手段（例えば、図８のステップＳ２を実行する図４のグラフ構造設定部３）と、
前記第１および第２の画像を結合する位置に配置したとき、前記第１の画像に設けられたグラフ構造の領域であって、かつ、前記第２の画像と重なり合う領域を重複領域（例えば、図６の領域Ａ３）に決定する決定手段（例えば、図８のステップＳ３を実行する図４のグラフ構造設定部３）と、
前記第１および第２の画像のサンプリング点の画素値に基づき、前記重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出手段（例えば、図４のコスト算出部５）と、
前記算出手段によって算出された前記コストに基づき、前記重複領域を分断する分断ライン（例えば、結合ライン）を取得する取得手段（例えば、図４の結合ライン決定部）と、
前記分断ラインを境として、前記第１および第２の画像を結合する結合手段（例えば、図４の結合部７）と
を含むことを特徴とする。
【００２７】
請求項９に記載の画像処理方法は、
前記２枚の画像の重複領域において原画中に存在するピクセルをノードとし、それらがエッジで連結されたグラフ構造を設定するグラフ構造設定ステップ（例えば、図８のステップＳ１）と、
前記グラフ構造が設定された前記２枚の画像の一方を第１の画像、他方を第２の画像に指定する指定ステップ（例えば、図８のステップＳ２）と、
前記第１および第２の画像を結合する位置に配置したとき、前記第１の画像に設けられたグラフ構造の領域であって、かつ、前記第２の画像と重なり合う領域を重複領域に決定する決定ステップ（例えば、図８のステップＳ３）と、
前記第１および第２の画像のサンプリング点の画素値に基づき、前記重複領域のノードおよびエッジにそれぞれ対応するコストを算出する算出ステップ（例えば、図８のステップＳ６）と、
前記算出ステップの処理で算出された前記コストに基づき、前記重複領域を分断する分断ラインを取得する取得ステップ（例えば、図８のステップＳ７）と、
前記分断ラインを境として、前記第１および第２の画像を結合する結合ステップ（例えば、図８のステップＳ８）と
を含むことを特徴とする。
【００２８】
なお、本発明の記録媒体に記録されているプログラム、および本発明のプログラムの請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係は、上述した本発明の画像処理方法のものと同様であるので、その記載は省略する。
【００２９】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。
【００３０】
図４は、本発明の一実施の形態である画像処理装置の構成例を示している。この画像処理装置１は、入力される２枚の画像Ｘ，Ｙを結合して画像Ｚを生成するものであり、グラフ構造設定部２、点密度決定部３、ソース／シンクノード設定部４、コスト算出部５、結合ライン決定部６、および結合部７から構成される。
【００３１】
なお、画像処理装置１に入力される画像Ｘ，Ｙは、既に変形処理が施されたものであり、画像上に設けられているサンプリング点は正方格子構造を有していないものとする。以下、サンプリング点が正方格子構造を有していない画像をISI(Irregularly Sampled Image)と称する。当然ながら、画像Ｘ，Ｙの両方または一方がISIではなくても構わない。
【００３２】
グラフ構造設定部２は、入力される画像Ｘ，Ｙのそれぞれを、画像上のサンプリング点をノード(node)と見なしてノード間をエッジ(edge)で繋ぎ、ノードを頂点とする三角形の領域に分割することにより、グラフ構造（ノードがエッジによって結ばれている構造）を設定して、点密度決定部３に出力する。
【００３３】
画像Ｘ，Ｙをそれぞれ三角形の領域に分割する方法には、例えば、点集合（いまの場合、サンプリング点の集合）のAlpha Shapeをドローネ三角形分割したものを適用する。Alpha Shapeとは、点集合を構成する点を全て含む領域を表す数学的概念であり、入力値alphaを変えることで様々な形になるが、点集合の形を表す概念として用いられる用語である。一般には、点集合をドローネ三角形分割した構造から求めることができ、ここで必要とする「点集合のAlpha Shapeをドローネ三角形分割したもの」は、Alpha Shapeが求まった時点で得られていることになる。
【００３４】
なお、グラフ構造設定部２において、ドローネ三角形分割ではなく、その他の方法で、画像Ｘ，Ｙを三角形の領域に分割するようにしてもよい。ただし、ドローネ三角形分割を用いることにより、得られる三角形の形状が比較的均等になるという利点がある。あるいは、画像Ｘ，Ｙを三角形以外の形状の領域に分割して、グラフ構造を設定するようにしてもよい。ただし、三角形以外の形状の領域に分割することは、点の配置によっては不可能となることも生じ得るが、三角形の領域に分割することは、点の配置に拘わらず常に可能であるという利点がある。
【００３５】
点密度決定部３は、グラフ構造が設定された画像Ｘ，Ｙそれぞれのノード（サンプリング点）の平均密度を算出して、その値が大きい方の画像をＡ１、小さい方の画像をＡ２に決定する。また、点密度決定部３は、図５に示すように、ユーザからの設定に基づいて画像Ａ１とＡ２の位置関係を決定した上で、画像Ａ１のグラフ構造のうち、画像Ａ２に重なっている領域を特定してその領域をＡ３に決定し、画像Ａ１，Ａ２と領域Ａ３をソース／シンクノード設定部４に出力する。なお当然ながら、この領域Ａ３もグラフ構造を有している。またこのとき、画像Ａ１とＡ２の位置関係はユーザの任意であり、それぞれのサンプリング点は非正方格子構造であるので、画像Ａ１のサンプリング点と画像Ａ２のサンプリング点は重なっていなくてもよい。
【００３６】
ソース／シンクノード設定部４は、図６に示すように、画像Ａ１の領域のうち、領域Ａ３に含まれない領域を表すソース(Source)ノードを設定する。また、画像Ａ２の領域のうち、領域Ａ３に含まれない領域を表すシンク(Sink)ノードを設定する。さらに、ソース／シンクノード設定部４は、領域Ａ３の外周上に位置する各ノードについて、領域Ａ３以外の画像Ａ１上のノードに繋がっているものはソースノードに連結し、領域Ａ３以外の画像Ａ１上のノードに繋がっていないものはシンクノードに連結する。
【００３７】
コスト算出部５は、領域Ａ３の各ノードおよび各エッジ、並びにソース／シンクノードに連結したエッジのコストを算出する。領域Ａ３のノードのコストとしては、当該ノード（すなわち、画像Ａ１のサンプリング点）の画素値と、画像Ａ２のサンプリング点（図５および６には図示されていない）のうちの当該ノードに最も距離が近いものの画素値との差が算出される。
【００３８】
なお、画素値の差は、具体的には例えば、RGB各色それぞれについての差の２乗の加算値（（Ｒ１−Ｒ２）２＋（Ｇ１−Ｇ２）２＋（Ｂ１−Ｂ２）２）を採用する。ここで、Ｒ１，Ｇ１，Ｂ１は、画像Ａ１のサンプリング点の画素値であり、Ｒ２，Ｇ２，Ｂ２は、画像Ａ２のサンプリング点の画素値である。
【００３９】
また、領域Ａ３のノード（すなわち、画像Ａ１のサンプリング点）と、画像Ａ２のサンプリング点のうちの当該ノードに最も距離が近いものを検出する方法（以下、最近点探索法と記述する）としては、例えば、図７に示すような、画像Ａ２をボロノイ多角形に分割したボロノイ図を用いる方法がある。このボロノイ図は、画像Ａ２の領域を、最も近いサンプリング点が共通となるように分割したものである。
【００４０】
したがって、領域Ａ３のノードが、ボロノイ図を構成するボロノイ多角形のうちのどれに属するかを判定すれば、画像Ａ２のサンプリング点のうち、領域Ａ３の当該ノードに最も距離が近いものを検出することができる。
【００４１】
なお、最近点探索法には、ボロノイ図を用いる方法以外の方法を適用してもよい。ただし、グラフ構造設定部２において、アルファシェープを求めるアルゴリズムではその過程でドローネ三角形分割を行う場合が多いため、ボロノイ図を用いる方法を用いれば、この結果を利用して容易にボロノイ図を求めることができるという利点がある。
【００４２】
領域Ａ３のエッジのコストとしては、当該エッジの両端のノードのコストを加算して算出する。ソース／シンクノードに連結したエッジのコストとしては、無限大の値を設定する。
【００４３】
結合ライン決定部６は、コスト算出部５によって算出された領域Ａ３の各ノードおよび各エッジ、並びにソース／シンクノードに連結したエッジのコストに基づき、Min-cut Max-flow問題を解くことにより、エッジの集合(Max-flowを与えるMin-cut)が、全ノードをソースに連結したもの(ソース集合)と、シンクに連結したもの(シンク集合)とに分類する結合ラインを得る。
【００４４】
結合部７は、領域Ａ３について、決定された結合ラインよりもソースノード側については画像Ａ１を採用し、決定された結合ラインよりもシンクノード側については画像Ａ２を採用することにより画像Ｚを生成する。
【００４５】
次に、画像処理装置１による画像結合処理について、図８のフローチャートを参照して説明する。
【００４６】
ステップＳ１において、グラフ構造設定部２は、入力された画像Ｘ，Ｙのそれぞれを、画像上のサンプリング点をノードと見なしてノード間をエッジで繋ぎ、ノードを頂点とする三角形の領域に分割することによりグラフ構造を設定して、点密度決定部３に出力する。
【００４７】
ステップＳ２において、点密度決定部３は、グラフ構造が設定された画像Ｘ，Ｙそれぞれのノードの平均密度を算出して、その値が大きい方の画像をＡ１、小さい方の画像をＡ２に決定する。ステップＳ３において、点密度決定部３は、ユーザからの設定に基づいて画像Ａ１とＡ２の位置関係を決定した上で、画像Ａ１のグラフ構造のうち、画像Ａ２に重なっている領域を特定してその領域をＡ３に決定し、画像Ａ１，Ａ２と領域Ａ３をソース／シンクノード設定部４に出力する。
【００４８】
ステップＳ４において、ソース／シンクノード設定部４は、画像Ａ１の領域のうち、領域Ａ３に含まれない領域を表すソースノードを設定する。また、画像Ａ２の領域のうち、領域Ａ３に含まれない領域を表すシンクノードを設定する。ステップＳ５において、ソース／シンクノード設定部４は、領域Ａ３の外周上に位置する各ノードについて、領域Ａ３以外の画像Ａ１上のノードに繋がっているものはソースノードに連結し、領域Ａ３以外の画像Ａ１上のノードに繋がっていないものはシンクノードに連結する。
【００４９】
ステップＳ６において、コスト算出部５は、領域Ａ３の各ノードおよび各エッジ、並びにソース／シンクノードに連結したエッジのコストを算出する。具体的には、領域Ａ３のノードのコストとしては、当該ノード（すなわち、画像Ａ１のサンプリング点）の画素値と、画像Ａ２のサンプリング点（図５および６には図示されていない）のうちの当該ノードに最も距離が近いものの画素値との差を算出する。領域Ａ３のエッジのコストとしては、当該エッジの両端のノードのコストを加算して算出する。ソース／シンクノードに連結したエッジのコストとしては、無限大の値を設定する。
【００５０】
ステップＳ７において、結合ライン決定部６は、コスト算出部５によって算出された領域Ａ３の各ノードおよび各エッジ、並びにソース／シンクノードに連結したエッジのコストに基づき、Min-cut Max-flow問題を解くことにより、エッジの集合(Max-flowを与えるMin-cut)が、全ノードをソースに連結したもの(ソース集合)と、シンクに連結したもの(シンク集合)とに分類する結合ラインを得る。
【００５１】
ステップＳ８において、結合部７は、領域Ａ３について、決定された結合ラインよりもソースノード側については画像Ａ１を採用し、決定された結合ラインよりもシンクノード側については画像Ａ２を採用することにより画像Ｚを生成する。
【００５２】
このようにして生成された画像Ｚは、リサンプリグ処理が施されていない、すなわち、画質が劣化されていない画像Ａ，Ｂが結合ラインを境に結合されたものであるので、そのつなぎ目が最も目立たない状態となっていることが期待できる。以上、画像処理装置１による画像結合処理の説明を終了する。
【００５３】
なお、本実施の形態である画像処理装置１は、画像レタッチ、パノラマ画像生成、テクスチャ生成等の画像処理に適用することが可能である。
【００５４】
ところで、上述した一連の処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば図９に示すよう構成される汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【００５５】
このパーソナルコンピュータ２０は、CPU(Central Processing Unit)２１を内蔵している。CPU２１にはバス２４を介して、入出力インタフェース２５が接続されている。バス２４には、ROM(Read Only Memory)２２およびRAM(Random Access Memory)２３が接続されている。
【００５６】
入出力インタフェース２５には、ユーザが操作コマンドを入力するキーボード、マウス、等の入力デバイスよりなる入力部２６、結合処理結果等の画像を表示するCRT(Cathode Ray Tube)またはLCD(Liquid Crystal Display)等のディスプレイよりなる出力部２７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部２８、およびモデム、LAN（Local Area Network）アダプタなどよりなり、インタネットに代表されるネットワークを介した通信処理を実行する通信部２９が接続されている。また、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory)、DVD(Digital Versatile Disc)を含む）、光磁気ディスク（ＭＤ(Mini Disc)を含む）、もしくは半導体メモリなどの記録媒体３１に対してデータを読み書きするドライブ３０が接続されている。
【００５７】
このパーソナルコンピュータ２０に上述した一連の処理を実行させるプログラムは、記録媒体３１に格納された状態でパーソナルコンピュータ２０に供給され、ドライブ３０によって読み出されて記憶部２８に内蔵されるハードディスクドライブにインストールされている。記憶部２８にインストールされているプログラムは、入力部２６に入力されるユーザからのコマンドに対応するCPU２１の指令によって、記憶部２８からRAM２３にロードされて実行される。
【００５８】
なお、本明細書において、プログラムに基づいて実行されるステップは、記載された順序に従って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【００５９】
また、プログラムは、１台のコンピュータにより処理されるものであってもよいし、複数のコンピュータによって分散処理されるものであってもよい。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであってもよい。
【００６０】
本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【図面の簡単な説明】
【００６１】
【図１】２枚の画像を連結する従来の方法を説明するための図である。
【図２】２枚の画像を連結する従来の方法を説明するための図である。
【図３】２枚の画像を連結する従来の方法を説明するための図である。
【図４】本発明を適用した画像処理装置の構成例を示すブロック図である。
【図５】画像Ａ１，Ａ２と領域Ａ３の関係を示す図である。
【図６】ソース／シンクノードを示す図である。
【図７】ボロノイ図の一例を示す図である。
【図８】画像結合処理を説明するフローチャートである。
【図９】パーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【００６２】
１  画像処理装置，  ２  グラフ構造設定部，  ３  点密度決定部，  ４  ソース／シンクノード設定部，  ５  コスト設定部，  ６  結合ライン決定部，  ７  結合部，  ２０  パーソナルコンピュータ，  ２１  CPU，３１  記録媒体
【図１】
2006003982.tif 000003
【図２】
2006003982.tif 000004
【図３】
2006003982.tif 000005
【図４】
2006003982.tif 000006
【図５】
2006003982.tif 000007
【図６】
2006003982.tif 000008
【図７】
2006003982.tif 000009
【図８】
2006003982.tif 000010
【図９】
2006003982.tif 000011