画像処理装置および方法、並びにプログラム
【課題】シームカービングにおいて、計算コストを低減させつつ、ピクセルずれを抑制できるようにする。
【解決手段】全画像探索部３１は、入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを縮小した縮小画像エネルギーマップより縮小シームを探索し、部分画像探索部３２に供給する。部分画像探索部３２は、入力画像エネルギーマップのうち、全画像探索部３１により探索された縮小シームに属する画素を起点とする部分シーム候補を探索し、積算エネルギーが最小となる部分シームを探索する。加工部１６は、探索された部分シームに属する画素を入力画像より削除、または挿入することにより、入力画像を縮小、または拡大する。本発明は、画像処理装置に適用することができる。
【解決手段】全画像探索部３１は、入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを縮小した縮小画像エネルギーマップより縮小シームを探索し、部分画像探索部３２に供給する。部分画像探索部３２は、入力画像エネルギーマップのうち、全画像探索部３１により探索された縮小シームに属する画素を起点とする部分シーム候補を探索し、積算エネルギーが最小となる部分シームを探索する。加工部１６は、探索された部分シームに属する画素を入力画像より削除、または挿入することにより、入力画像を縮小、または拡大する。本発明は、画像処理装置に適用することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および方法、並びにプログラムに関し、特に、シームカービング（SeamCarving）による不具合を低減し、処理を高速化できるようにする画像処理装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
シームカービング（SeamCarving）と呼ばれる画像の加工技術が一般に普及しつつある。
【０００３】
シームカービング（SeamCarving）とは、画像内にある主体となるオブジェクトの形状や大きさを不自然なものとならないように、画像を拡大、または縮小させる技術である。より具体的には、シームカービングでは、まず、画像の画素間の画素値や輝度の差分より、各画素単位でエネルギーが求められ、それらからエネルギー画像（エネルギーマップ）が生成される。次に、エネルギー画像を用いて、画像の一方の端部の各画素から順次隣接する画素を経由して他方の端部まで設定される経路において、経由する画素のエネルギーの積算値が最小となるような経路が、シームとして求められる。このシームを構成する、隣接する画素間においては、画素値または輝度値の変化が小さいと考えられる。すなわち、シームは、エネルギー変化の小さい画素が順次配列された領域であるため、シームを構成する画素に隣接する領域は、シームを構成する画素と同系統の画素値、または輝度値であると考えることができる。そこで、シームカービングでは、入力された画像からシームを構成する画素を削除する、または、付加することにより、画像における主体となるオブジェクトの形状や大きさの変化を小さくさせつつ、画像全体の大きさ縮小、または拡大する（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２１７７６５公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、シームカービングでは、画像と同サイズのエネルギー画像が生成され、画像全域から最もエネルギー変化の小さなシームが探索されていた。このため、２本目以降のシームが探索される場合、１本のシームが探索される度に、探索されたシームを削除して画像を再構成し、エネルギー画像が毎度作成され直されるため、計算コストが非常に多くなっていた。
【０００６】
また、エネルギー画像の再作成を抑制するため、一度作成されたエネルギー画像を繰り返し使うようにすることを考える場合、複数のシームが同一のエネルギー画像から同時に削除されることになる。ところが、この場合、複数のシームが交差するような現象が生じると、１本のシームにより削除される幅が、１ピクセル分であったとすると、複数のシームが交差することにより生じる交点となる同一の画素が、複数のシームに含まれることになる。このとき、同時に複数のシームを削除、または付加すると、交点を含む行、または列の画素数が他の行、または列における画素数と異なる、いわゆるピクセルずれが生じてしまう恐れがあった。
【０００７】
本発明はこのような状況に鑑みてなされたものであり、特に、シームカービングにおいて、計算コストを低減させつつ、ピクセルずれを抑制できるようにするものである。
【課題を解決するための手段】
【０００８】
本発明の一側面の画像処理装置は、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段とを含み、前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる。
【０００９】
前記縮小シーム探索手段により探索された縮小シームを構成する、前記縮小画像の全ての画素に対応する前記縮小画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記縮小画像エネルギーマップを更新する縮小画像エネルギーマップ更新手段をさらに含ませるようにすることができる。
【００１０】
前記縮小シーム探索手段には、グリーディ法、または、ダイナミックプログラミング法により、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索させるようにすることができる。
【００１１】
前記部分シーム探索手段には、グリーディ法により、前記縮小シーム探索手段により前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索させるようにすることができる。
【００１２】
本発明の一側面の画像処理方法は、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段とを含み、前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置の画像処理方法であって、前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップとを含み、前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる。
【００１３】
本発明の一側面のプログラムは、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段とを含み、前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置を制御するコンピュータに、前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップとを含む処理を実行させ、前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
【００１４】
本発明の一側面においては、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップが生成され、前記入力画像エネルギーマップが縮小されることにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップが生成され、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素が順次経由されて、前記他方の端部の画素に到達されるまでの複数の経路のうち、経由される画素のエネルギーの積算値が最小となる経路の画素間が結ばれることにより構成される縮小シームが探索され、探索された縮小シームの端部が構成される、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素が順次経由されて、前記他方の端部の画素に到達するまでの複数の経路のうち、経由される画素のエネルギーの積算値が最小となる画素間が結ばれることにより構成される部分シームが探索され、探索された部分シームが構成される、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値が挿入されて置換され、前記入力画像エネルギーマップが更新され、探索された前記部分シームが構成される画素が、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素が挿入されることで前記入力画像が縮小または拡大され、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素が順次経由されて、前記他方の端部の画素に到達するまでの複数の経路が探索されるにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素が隣接される画素として設定され、前記経路が構成される。
【００１５】
本発明の画像処理装置は、独立した装置であっても良いし、画像処理を行うブロックであっても良い。
【発明の効果】
【００１６】
本発明の一側面によれば、シームカービングにおける、計算コストを低減しつつ、ピクセルずれを低減することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明を適用した画像処理装置の一実施の形態の構成例を示すブロック図である。
【図２】図１の探索部の構成例を示すブロック図である。
【図３】シームカービング処理を説明するフローチャートである。
【図４】探索処理を説明するフローチャートである。
【図５】全画像探索処理を説明するフローチャートである。
【図６】全画像探索処理を説明する図である。
【図７】全画像探索処理を説明する図である。
【図８】全画像探索処理を説明する図である。
【図９】部分画像探索処理を説明するフローチャートである。
【図１０】部分画像探索処理を説明する図である。
【図１１】部分画像探索処理を説明する図である。
【図１２】部分画像探索処理を説明する図である。
【図１３】部分画像探索処理を説明する図である。
【図１４】部分画像探索処理を説明する図である。
【図１５】検索処理におけるダイナミックプログラミング法とグリーディ法とを説明する図である。
【図１６】シームカービング処理による処理結果を説明する図である。
【図１７】汎用のパーソナルコンピュータの構成例を説明する図である。
【発明を実施するための最良の形態】
【００１８】
［画像処理装置の構成例］
図１は、本発明を適用した画像処理装置のハードウェアの一実施の形態の構成例を示している。図１の画像処理装置１は、入力画像をシームカービングにより縮小、または拡大し、表示部２に表示するものである。
【００１９】
画像処理装置１は、画像取得部１１、エネルギーマップ生成部１２、入力画像エネルギーマップ記憶部１３、縮小画像エネルギーマップ記憶部１４、探索部１５、および加工部１６を備えている。
【００２０】
画像取得部１１は、入力画像を取得すると共に、エネルギーマップ生成部１２、および加工部１６に供給する。エネルギーマップ生成部１２は、エネルギー算出部２１、および縮小部２２を備えており、画像取得部１１からの入力画像より、入力画像と同サイズの入力画像エネルギーマップ、および、入力画像の縮小画像と同サイズの縮小画像エネルギーマップを生成する。より詳細には、エネルギー算出部２１は、以下の式（１）を算出することにより、各画素のエネルギーｅ（Ｉ）を算出し、入力画像に対応する画素単位のエネルギーからなる入力画像エネルギーマップを生成し、入力画像エネルギーマップ記憶部１３に記憶させる。また、エネルギー算出部２１は、生成した入力画像エネルギーマップを縮小部２２に供給する。
【００２１】
【００２２】
ここで、ｅ（Ｉ）は、Ｉで示される入力画像上の位置の各画素におけるエネルギーを示している。すなわち、式（１）で示される各画素のエネルギーｅ（Ｉ）は、入力画像の各画素におけるｘ，ｙ方向のそれぞれの隣接する画素間の画素値、または輝度値などの差分の絶対値和であることが示されている。
【００２３】
縮小部２２は、エネルギー算出部２１により算出されて生成され、入力画像と同サイズの入力画像エネルギーマップを縮小し、縮小画像エネルギーマップを生成して、縮小画像エネルギーマップ記憶部１４に記憶させる。より詳細には、縮小部２２は、入力画像の、例えば、ｍ画素×ｎ画素を１ブロックとし、その１ブロックを１画素と対応するように、各ブロックの画素のエネルギーの平均や中央値を求めて、エネルギーマップを構成することで縮小画像エネルギーマップを生成する。すなわち、縮小画像エネルギーマップは、入力画像に対して、ｍ画素×ｎ画素を１ブロックとし、その１ブロックを１画素と対応するように生成された縮小画像のエネルギーマップとして求められる。
【００２４】
探索部１５は、縮小画像エネルギーマップ記憶部１４より縮小画像エネルギーマップを読み出し、縮小画像の一方の端部より他方の端部まで順次隣接する画素を選択経路として選択し、選択経路の画素のエネルギーの積算値が最小となるように縮小シームを探索する。この際、探索部１５は、後述するダイナミックプログラミング法、またはグリーディ法により縮小シームを探索する。また、探索部１５は、一旦求めた縮小シームに属する画素のエネルギーを、エネルギー最大値に置換し、順次所定数の部分シームが求められるまで、同様の処理を繰り返す。
【００２５】
ここでいう、一方の端部より他方の端部まで順次隣接する画素からなる経路とは、例えば、縮小画像の上方端部のいずれかの画素に対して、右下、真下、および左下に隣接する３画素のいずれかが選択され、選択された画素に同様に隣接する３画素のいずれかが選択されるといったことが順次繰り返されて、下方端部のいずれかの画素にまで順次選択される画素が結ばれることにより構成される経路である。従って、一方の端部が縮小画像の左端部であり、他方の端部が右端部である場合、左端部のいずれかの画素に対して、右上、真右、および右下に隣接する３画素のいずれかが選択され、選択された画素に同様に隣接する３画素のいずれかが選択されるといったことが順次繰り返されて、右端部のいずれかの画素にまで順次選択される画素が結ばれることにより構成される経路となる。また、以降においては、縮小画像における上方端部から下方端部に縮小シームが探索されるとき、探索方向を下方向と称するものとし、同様に、左端部から右端部に縮小シームが探索されるとき、探索方向を右方向と称するものとする。さらに、注目画素が設定される場合、注目画素に対して探索方向に隣接する画素とは、探索方向が垂直方向のとき、注目画素に対して、右上、真上、および左上に隣接する３画素、または右下、真下、および左下に隣接する３画素を表すものとする。同様に、探索方向が水平方向のとき、注目画素に対して、左上、真左、および左下に隣接する３画素、または右上、真右、および右下に隣接する３画素を表すものとする。
【００２６】
さらに、探索部１５は、縮小画像エネルギーマップで検索された縮小シームを構成する縮小画像の画素に対応するブロックに属する、入力画像の端部の画素より順次隣接する画素のうち最小のエネルギーとなる画素を順次注目画素を設定する。そして、探索部１５は、順次設定された注目画素を結ぶことにより部分シームを探索する。このとき、探索部１５は、後述するグリーディ法により部分シームを探索する。この際、探索部１５は、一旦求めた入力画像の部分シームに属する画素に対応するエネルギーを、エネルギー最大値に置換して、順次所定数の部分シームが求めれらるまで、同様の処理を繰り返し、複数の部分シームを求める。
【００２７】
加工部１６は、画像取得部１１より供給されてくる画像より、探索部１５より求められた部分シームに対応する画素を削除、または同様の画素を付加することにより、画像を縮小、または拡大し、加工処理した後、表示部２に出力して表示させる。
【００２８】
［探索部１５の構成例］
次に、図２を参照して、探索部１５の詳細な構成例について説明する。
【００２９】
探索部１５は、全画像探索部３１、および部分画像探索部３２より構成されている。全画像探索部３１は、縮小画像エネルギーマップより、縮小画像における縮小シームを求めて、部分画像探索部３２に供給する。部分画像探索部３２は、全画像探索部３１より供給されてきた縮小シームの情報に基づいて、入力画像エネルギーマップより部分シームを求め加工部１６に出力する。
【００３０】
まず、全画像探索部３１の構成について説明する。全画像探索部３１は、縮小画像エネルギーマップバッファ５１、積算エネルギーマップ生成部５２、積算エネルギーマップ記憶部５３、縮小シーム決定部５４、およびエネルギー最大値挿入部５５を備えている。縮小画像エネルギーマップバッファ５１は、縮小画像エネルギーマップ記憶部１４に記憶されている縮小画像エネルギーマップを読み出して一旦記憶する。また、縮小画像エネルギーマップバッファ５１は、縮小シームに属する画素のエネルギーがエネルギー最大値挿入部５５より挿入されるエネルギー最大値で置換され、縮小画像エネルギーマップが更新されると、更新された縮小画像エネルギーマップを記憶する。
【００３１】
積算エネルギーマップ生成部５２は、以下の式（２）で示される計算を実行することにより、順次設定される注目画素に対して、縮小画像エネルギーマップの探索方向に対して逆方向に隣接する画素のエネルギーを順次積算し、積算エネルギーとして求める。
【００３２】
【００３３】
ここで、Ｍ（ｉ，ｊ）は、注目画素（ｉ，ｊ）における、それまでに順次設定された注目画素の積算エネルギーを示している。また、ｅ（ｉ，ｊ）は、注目画素（ｉ，ｊ）のエネルギーを閉めている。ｍｉｎ（Ａ，Ｂ，Ｃ）は、Ａ乃至Ｃの値のうち最小値を選択することを示している。
【００３４】
すなわち、積算エネルギーマップ生成部５２は、注目画素（ｉ，ｊ）において、注目画素（ｉ，ｊ）に対して、縮小シームの探索方向と逆方向に隣接する画素（ｉ−１，ｊ−１），（ｉ−１，ｊ），（ｉ−１，ｊ＋１）の積算エネルギーＭ（ｉ−１，ｊ−１），Ｍ（ｉ−１，ｊ），Ｍ（ｉ−１，ｊ＋１）のうち最小のものを選択し、注目画素のエネルギーと加算して、注目画素の積算エネルギーを算出する。積算エネルギーマップ生成部５２は、同様の処理を順次繰り返すことにより、縮小画像エネルギーマップの積算エネルギーマップを生成し、積算エネルギーマップ記憶部５３に記憶させる。尚、式（２）においては、入力画像に対して垂直方向に上方端部から下方端部の方向に向かう縮小シームを探索する場合の例が記載されている。このため、縮小シームの探索方向に対応して、式（２）は変化するものである。
【００３５】
縮小シーム決定部５４は、積算エネルギーマップ記憶部５３に記憶されている積算エネルギーマップの情報に基づいて、縮小画像の一方の端部の各画素より選択経路として選択された画素のエネルギーの積算値が順次最小となるように縮小シームを探索する。そして、縮小シーム決定部５４は、積算エネルギーが最小となる画素を順次結ぶ経路を縮小シームに決定し、部分画像探索部３２に供給する。さらに、縮小シーム決定部５４は、決定した縮小シームの情報をエネルギー最大値挿入部５５に供給する。
【００３６】
エネルギー最大値挿入部５５は、縮小エネルギーマップバッファ５１に記憶されている縮小エネルギーマップの各画素のエネルギーのうち、縮小シームに属する画素のエネルギーにエネルギー最大値を挿入することで更新する。すなわち、エネルギーは、何らかの有限の数値により表現されるが、その最大値で表現される場合は稀であり、事実上、その画素が縮小シームを構成する画素として選択されたことを示すために、実態と異なるエネルギー最大値が挿入される。
【００３７】
次に、部分画像探索部３２の構成について説明する。部分画像探索部３２は、入力画像エネルギーマップバッファ７１、隣接エネルギー比較部７２、非隣接エネルギー比較部７３、選択経路設定部７４、選択経路記憶部７５、部分シーム決定部７６、および部分シーム記憶部７７を備える。また、部分画像探索部３２は、同時処理シーム本数判定部７８、ブロック内部分シーム本数判定部７９、出力部８０、およびエネルギー最大値挿入部８１を備えている。
【００３８】
入力画像エネルギーマップバッファ７１は、入力画像エネルギー記憶部１３に記憶されている入力画像エネルギーマップの情報を読み出して、一旦記憶する。また、入力画像エネルギーマップバッファ７１は、エネルギー最大値挿入部８１により、求められた部分シームに属する画素のエネルギーに、エネルギー最大値が挿入されて置換された、入力画像エネルギーマップを更新して記憶する。
【００３９】
隣接エネルギー比較部７２は、全画像探索部３１より供給されてくる縮小シームを構成するブロックのうち、一方の端部のブロックに属する入力画像の画素のうち、一方の端部の画素より順次注目画素を設定する。そして、隣接エネルギー比較部７２は、順次設定される注目画素と、探索方向に隣接する画素のエネルギーとエネルギー最大値とを比較し、隣接する画素のエネルギーの全てがエネルギー最大値のみとなっているか否かを判定する。そして、隣接エネルギー比較部７２は、判定結果に応じて、全てがエネルギー最大値であるとき判定結果を非隣接エネルギー選択部７３に供給する。
【００４０】
非隣接エネルギー選択部７３は、隣接エネルギー比較部７２の判定結果により、注目画素に隣接する全ての画素がエネルギー最大値である場合、注目画素の位置に応じて、注目画素に隣接していない画素を、隣接画素として選択し、選択経路設定部７４に供給する。すなわち、非隣接エネルギー選択部７３は、注目画素に隣接していないが、注目画素に隣接した画素に、さらに隣接している複数の画素を隣接画素として選択する。
【００４１】
選択経路設定部７４は、入力画像マップバッファ７１に記憶されている入力画像マップの情報、および非隣接エネルギー選択部７３から供給されてくる隣接画素として設定された画素の情報に基づいて、縮小シームに属する入力画像の画素のうち、縮小シームの一方の端部から他方の端部への方向に隣接する画素のうち、エネルギーが最小となる画素を順次選択方向として設定し、選択経路記憶部７５に記憶させる。
【００４２】
部分シーム決定部７６は、選択経路記憶部７５に記憶されている、縮小シームに属する入力画像の一方の端部の各画素より、選択経路記憶部７５に記憶されている選択方向に存在する画素の積算エネルギーが最小となる経路を部分シームとして決定する。部分シーム決定部７６は、決定した部分シームの情報を部分シーム記憶部７７に記憶させる。
【００４３】
同時処理シーム本数判定部７８は、部分シーム記憶部７７に記憶されている部分シームの情報に基づいて、予め設定されている同時に処理可能な部分シームの本数に達しているか否かを判定する。そして、同時処理シーム本数判定部７８は、同時に処理可能なシーム本数に達していない場合、エネルギー最大値挿入部８１に通知する。さらに、同時処理シーム本数判定部７８は、入力画像エネルギーマップに新たに記憶された部分シームに属する画素のエネルギーにエネルギー最大値を挿入させて更新させると共に、新たに部分シームを探索させる。また、同時処理シーム本数判定部７８は、同時に処理可能なシーム本数に達した場合、出力部８０にその旨通知し、出力部８０より部分シーム記憶部７７に記憶されている部分シームの情報を加工部１６に出力させる。
【００４４】
ブロック内部分シーム本数判定部７９は、今現在の部分シーム本数が、縮小シームが求められた縮小画像を構成する画素からなる縮小ブロック単位で予め設定される本数となったか否かを判定する。そして、ブロック内部分シーム本数判定部７９は、今現在の部分シーム本数が、予め設定された本数となった場合、全画像探索部３１に対して新たな縮小シームを探索するように通知する。
【００４５】
［シームカービング処理］
次に、図３のフローチャートを参照して、シームカービング処理について説明する。
【００４６】
ステップＳ１において、画像取得部１１は、入力画像を取得し、取得した入力画像をエネルギーマップ生成部１２、および加工部１６に供給する。
【００４７】
ステップＳ１２において、エネルギーマップ生成部１２は、エネルギー算出部２１を制御して、入力画像の各画素の画素値、または輝度値などに基づいて、上述した式（１）を算出することにより、各画素のエネルギーを算出させる。さらに、エネルギーマップ生成部１２は、エネルギー算出部２１を制御して、各画素単位で算出されたエネルギーの値より入力画像エネルギーマップを生成させ、入力画像エネルギーマップ記憶部１３に記憶させると共に、縮小部２２に供給させる。
【００４８】
ステップＳ１３において、エネルギーマップ生成部１２は、縮小部２２を制御してエネルギーマップを縮小画像のサイズに処理させることにより、縮小画像エネルギーマップを生成させ、縮小画像エネルギーマップ記憶部１４に記憶させる。より詳細には、縮小部２２は、入力画像エネルギーマップを、例えば、ｍ画素×ｎ画素単位でブロック化し、その各ブロックを構成する各画素のエネルギーの平均値や中央値などを、縮小画像の各画素に対応するエネルギーとする縮小画像エネルギーマップを生成する。尚、この例においては、縮小画像に対応するエネルギーマップを縮小画像エネルギーマップと称するものとしているが、縮小画像エネルギーマップは、入力画像エネルギーマップを低解像度化したエネルギーマップと同様のものである。
【００４９】
ステップＳ１４において、探索部１５は、入力画像エネルギーマップ記憶部１３の入力画像エネルギーマップ、および縮小画像エネルギーマップ記憶部１４の縮小画像エネルギーマップに基づいて、探索処理を実行し、所定数の部分シームを探索する。すなわち、探索部１５は、入力画像の水平方向（ｘ方向）、または垂直方向（ｙ方向）に対して、隣接する画素のより構成される経路のうち、画素値、または輝度値の変化が小さい経路を、所定数だけ部分シームとして探索し、その情報を加工部１６に供給する。そして、探索部１５は、探索した所定数の部分シームの情報を加工部１６に供給する。尚、探索処理については、図４のフローチャートを参照して、後述するものとする。
【００５０】
ステップＳ１５において、加工部１６は、入力画像のシームカービングによる入力画像への加工処理が、縮小処理であるのか否かを判定し、例えば、縮小画像である場合、処理は、ステップＳ１６に進む。
【００５１】
ステップＳ１６において、加工部１６は、部分シームの情報に基づいて、入力画像より部分シームを構成する画素を削除し、削除した領域を詰めることにより、画像を縮小させる。
【００５２】
一方、ステップＳ１５において、入力画像のシームカービングによる入力画像への加工処理が、縮小処理ではない、すなわち、拡大処理であると判定された場合、処理は、ステップＳ１７に進む。
【００５３】
ステップＳ１７において、加工部１６は、部分シームの情報に基づいて、入力画像より部分シームを構成する画素に隣接する位置に、部分シームと同一の画素を挿入することにより、画像を拡大させる。
【００５４】
ステップＳ１８において、加工部１６は、加工処理された入力画像のサイズが、設定サイズであるか否かを判定する。ステップＳ１８において、例えば、縮小、または拡大により設定されたサイズではないと判定された場合、処理は、ステップＳ１４に戻り、それ以降の処理により、縮小、または拡大が繰り返される。一方、ステップＳ１８において、縮小、または拡大により設定されたサイズであると判定された場合、ステップＳ１９において、加工部１６は、入力画像に対して加工処理した画像を表示部２に出力して表示させる。
【００５５】
以上の処理により、まず、入力画像において、画素間の画素値、または輝度値の変化の少ない（エネルギーの積算値である積算エネルギーが最小となる）隣接する画素により構成される部分シームが求められる。そして、求められた部分シームを構成する画素が、入力画像より削除される、または挿入される。これにより入力画像が縮小、または拡大される加工処理が実現されるので、画像内における主だったオブジェクトの大きさを変更することなく、入力画像の全体の大きさを変化させることが可能となる。尚、以上の例においては、加工部１６が、部分シームと同一の画素を挿入することで画像を拡大させる例について説明してきたが、部分シーム近傍の画素と違和感の無い画素を挿入できればよいので、必ずしも同一の画像を挿入しなくても良い。従って、例えば、部分シームとして求められた画素の近傍の画素により補間生成される画素を部分シームとして求められた画素の近傍位置に挿入することにより、画像を拡大させるようにしてもよい。
【００５６】
［探索処理］
次に、図４のフローチャートを参照して、探索処理について説明する。
【００５７】
探索処理は、ステップＳ３１において、縮小画像エネルギーマップが用いられて全画像探索処理がなされることにより、縮小画像における縮小シームが求められる。そして縮小シームが求められると、ステップＳ３２において、全画像探索処理の探索結果である縮小シームに基づいて、部分画像探索処理が実行されて、入力画像に対する部分シームが求められる。
【００５８】
［全画像探索処理］
ここで、図５のフローチャートを参照して、縮小画像エネルギーマップを用いた全画像探索処理について説明する。尚、図５のフローチャートにおいては、方形状の画像のうち、上方端部の画素と、下方端部の画素とを隣接する画素間で順次結ぶ縮小シームを求める例について説明する。このように求められる縮小シームは、縮小画像の水平方向に対して、縮小、または拡大をするために求められるものである。従って、縮小画像の垂直方向に対しての縮小、または拡大に際しては、左端部の画素と右端部の画素とを隣接する画素間で順次結ぶことにより得られる縮小シームを同様の処理で求める必要がある。
【００５９】
ステップＳ５１において、縮小画像エネルギーマップバッファ５１は、縮小画像エネルギーマップ記憶部１４より縮小画像エネルギーマップを読み出し、一時的に記憶する。
【００６０】
ステップＳ５２において、積算エネルギーマップ生成部５２は、縮小画像エネルギーマップにおける注目画素（ｘ，ｙ）を（０，１）に設定し、初期化する。尚、ここで設定される座標は、縮小画像の左上端部の画素を原点（０，０）とし、水平方向のｘ座標は右方向を正とするものとし、垂直方向のｙ座標は下方向を正とするものとする。
【００６１】
ステップＳ５３において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｙ座標が縮小画像の垂直方向の高さ（height）より小さいか否かを判定する。ステップＳ５３において、例えば、最初の処理の場合、ｙ座標は、縮小画像の垂直方向の高さになっていないので、処理は、ステップＳ５４に進む。
【００６２】
ステップＳ５４において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｘ座標が縮小画像の水平方向の幅（width）よりも小さいか否かを判定する。ステップＳ５４において、注目画素（ｘ，ｙ）のｘ座標が縮小画像の水平方向の幅（width）よりも小さい場合、処理は、ステップＳ５５に進む。
【００６３】
ステップＳ５５において、積算エネルギーマップ生成部５３は、縮小画像エネルギーマップにおける注目画素（ｘ，ｙ）の左上（ｘ−１，ｙ＋１）、真上（ｘ，ｙ＋１）、および右上（ｘ＋１，ｙ＋１）のエネルギーのうち、最小となる積算エネルギーを持つ画素を選択する。積算エネルギーマップ生成部５３は、選択した画素の積算エネルギーと注目画素のエネルギーとを加算して、注目画素の積算エネルギーを求める。
【００６４】
ステップＳ５６において、積算エネルギーマップ生成部５３は、求めた積算エネルギーを注目画素の積算エネルギーとして、積算エネルギーマップ記憶部５３に記憶させる。尚、注目画素が、上端部より１画素下の場合、上端部の画素のエネルギーそのものが積算エネルギーとして利用される。
【００６５】
ステップＳ５７において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｘ座標を１インクリメントして、処理は、ステップＳ５４に戻る。そして、ステップＳ５４において、注目画素（ｘ，ｙ）のｘ座標が縮小画像の水平方向の幅（width）よりも小さくない、すなわち、水平方向について全ての処理が終了した場合、処理は、ステップＳ５８に進む。
【００６６】
ステップＳ５８において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｙ座標を１インクリメントし、処理は、ステップＳ５３に戻る。すなわち、ステップＳ５３乃至Ｓ５８の処理が繰り返されることにより、縮小画像の各画素について探索方向と逆方向に隣接する３画素の積算エネルギーのうち、最小となる積算エネルギーを持つ画素が選択される。そして、選択された積算エネルギーと各画素のエネルギーとが順次積算されて、積算エネルギーマップが生成され、積算エネルギーマップ記憶部５３に記憶されていく。
【００６７】
より具体的には、例えば、図６の左上部で示されるような３画素×３画素の縮小画像エネルギーマップを考える場合、処理は以下のようにされることになる。尚、図６の左上部の縮小画像エネルギーマップのエネルギーは、上段は左から右に向かって、１，２，３であり、中段は左から右に向かって６，２，４であり、下段は左から右に向かって、２，３，１に設定されている。
【００６８】
ステップＳ５２の処理により、最初の注目画素（ｘ，ｙ）は、（０，１）のエネルギーが６の画素となる。そして、この注目画素（０，１）は、左端部の画素であるので、ステップＳ５５の処理により、真上の画素（０，０）の画素のエネルギー１と、右上の画素（１，０）の画素のエネルギー２との２画素のうち最小となる積算エネルギーの画素（０，０）が選択される。そして、図６の左下部で示されるように、積算エネルギーマップ生成部５３は、この選択された画素（０，０）のエネルギー１（ここでは積算エネルギーとして扱われる）と、注目画素（ｘ，ｙ）のエネルギー６の積算値７を積算エネルギーマップの注目画素（ｘ，ｙ）＝（０，１）における積算エネルギーとして積算エネルギーマップ記憶部５３に記憶させる。
【００６９】
ステップＳ５７の処理により、注目画素（ｘ，ｙ）のｘ座標が１インクリメントされて、エネルギーが注目画素（ｘ，ｙ）は、（１，１）のエネルギーが２の画素となる。そして、この注目画素（１，１）は、ステップＳ５５の処理により、左上の画素（０，０）のエネルギー１、真上の画素（１，０）の画素のエネルギー２と、右上の画素（２，０）の画素のエネルギー３との３画素のうち最小となる積算エネルギーの画素（０，０）が選択される。そして、図６の中央下部で示されるように、積算エネルギーマップ生成部５３は、この選択された画素（０，０）のエネルギー１と、注目画素（ｘ，ｙ）のエネルギー２の積算値３を積算エネルギーマップの注目画素（ｘ，ｙ）＝（１，１）における積算エネルギーとして積算エネルギーマップ記憶部５３に記憶させる。
【００７０】
さらに、ステップＳ５７の処理により、注目画素（ｘ，ｙ）のｘ座標がさらに１インクリメントされて、エネルギーが注目画素（ｘ，ｙ）は、（２，１）のエネルギーが４の画素となる。そして、この注目画素（２，１）は、縮小画像の右端部の画素であるので、ステップＳ５５の処理により、左上の画素（１，０）のエネルギー１、真上の画素（２，０）の画素のエネルギー３との２画素のうち最小となるエネルギーの画素（２，０）が選択される。そして、図６の右下部で示されるように、積算エネルギーマップ生成部５３は、この選択された画素（１，０）のエネルギー２と、注目画素（ｘ，ｙ）のエネルギー４の積算値６を積算エネルギーマップの注目画素（ｘ，ｙ）＝（２，１）における積算エネルギーとして積算エネルギーマップ記憶部５３に記憶させる。
【００７１】
この結果、２段目の積算エネルギーマップにおける中段の積算エネルギーは、図７の右上部のように左から７，３，６となる。このとき、注目画素（ｘ，ｙ）のｘ座標は、縮小画像の水平方向の幅(width＝２)より小さくないので、ステップＳ５８において、ｙ座標が１インクリメントされることにより、縮小画像における下段の各画素が順次注目画素に設定される。尚、図７の左上部は、縮小画像エネルギーマップが示されている。
【００７２】
上述した処理と同様の処理により、注目画素（ｘ，ｙ）が、（０，２）の場合、積算エネルギーマップに基づいて、真上の画素（０，１）の積算エネルギーが７であり、右上の画素（１，１）の積算エネルギーが３となる。このため、最小である積算エネルギー３の右上の画素（１，１）が選択されて、積算エネルギー３と、注目画素（ｘ，ｙ）＝（０，２）のエネルギー２とが積算されて、注目画素（ｘ，ｙ）＝（０，２）の積算エネルギーが５とされて、積算エネルギーマップに登録される。
【００７３】
また、注目画素（ｘ，ｙ）が画素（１，２）である場合、積算エネルギーマップに基づいて、左上の画素（０，１）の積算エネルギーが７であり、真上の画素（１，１）の積算エネルギーが３であり、右上の画素（２，１）の積算エネルギーが６となる。このため、最小である積算エネルギー３の真上の画素（１，１）が選択されて、積算エネルギー３と、注目画素（ｘ，ｙ）＝（１，２）のエネルギー３とが積算されて、注目画素（ｘ，ｙ）＝（１，２）の積算エネルギーが６とされて、積算エネルギーマップに登録される。
【００７４】
さらに、注目画素（ｘ，ｙ）が画素（２，２）である場合、積算エネルギーマップに基づいて、左上の画素（１，１）の積算エネルギーが３であり、真上の画素（２，１）の積算エネルギーが６となる。このため、最小である積算エネルギー３の左上の画素（１，１）が選択されて、積算エネルギー３と、注目画素（ｘ，ｙ）＝（２，２）のエネルギー１とが積算されて、注目画素（ｘ，ｙ）＝（２，２）の積算エネルギーが４とされて、積算エネルギーマップに登録される。
【００７５】
この結果、積算エネルギーマップは、図８の右上部で示されるように構成され、下段の積算エネルギーは、左から５，６，４となる。尚、図８の左上部は、縮小画像エネルギーマップが示されている。
【００７６】
このように、ステップＳ５３乃至Ｓ５８の処理が繰り返されることにより、例えば、図８の左上部で示されるような縮小画像エネルギーマップが得られた場合、図８の右上部で示されるような積算エネルギーマップが求められて、積算エネルギーマップ記憶部５３に記憶されることになる。
【００７７】
ここで、図５のフローチャートの説明に戻る。
【００７８】
ステップＳ５３において、注目画素（ｘ，ｙ）のｙ座標が縮小画像の垂直方向の高さよりも小さくないと判定された場合、すなわち、上述したように積算エネルギーマップが完成されて、積算エネルギーマップ記憶部５３に記憶されたとみなされた場合、処理は、ステップＳ５９に進む。
【００７９】
ステップＳ５９において、縮小シーム決定部５４は、積算エネルギーマップ記憶部５３に記憶されている積算エネルギーマップを読み出し、積算エネルギーが最小となる最下段の画素を検索し、縮小シームの端部を下方の端部とする。さらに、縮小シーム決定部５４は、縮小シームの下方の端部の画素より順次、上方に隣接する画素、すなわち、右上、真上、および左上に隣接する画素のうち、積算エネルギーが最小となる画素を順次上方に向かって探索する処理を繰り返し、上段の端部の画素まで探索する。そして、縮小シーム決定部５４は、順次探索された画素を結ぶ経路を縮小シームとして決定し、その情報を部分画像探索部３２に供給すると共にエネルギー最大値挿入部５５に供給する。
【００８０】
すなわち、図８の右上部の積算エネルギーマップの場合、最下段における積算エネルギーの最小値は、図８の丸印で示される積算エネルギーが４であって、エネルギーが１の画素（２，２）である。すなわち、この画素（２，２）が縮小シームの下方の端部となる。そして、この画素（２，２）からみて、上方に隣接する画素（２，１），（１，１）のうち、積算エネルギーの最小値は、積算エネルギーが３であって、エネルギーが２の画素（１，１）である。さらに、この画素（１，１）からみて、上方に隣接する画素（０，０），（１，０），（２，０）のうち、積算エネルギーの最小値は、積算エネルギーが１であって、エネルギーが１の画素（０，０）である。
【００８１】
すなわち、下方の端部である画素（２，２）より上方の端部である画素（０，０）まで順次探索された画素（２，２），（１，１），（０，０）の経路は、順次積算されるエネルギーが最小となる。したがって、この画素（２，２），（１，１），（０，０）から構成される経路は、隣接する画素間の画素値、または輝度値の変化が最小となる縮小画像上の経路、すなわち、縮小シームを構成していることになる。このため、縮小シーム決定部５４は、これらの探索された画素の座標の情報に基づいて構成される経路を縮小シームに決定する。
【００８２】
ステップＳ６０において、エネルギー最大値挿入部５５は、縮小画像エネルギーマップバッファ５１に記憶されている縮小画像エネルギーマップを読み出し、縮小シーム決定部５４で決定された縮小シームを構成する各画素のエネルギーに最大値を挿入して更新する。この結果、最大値からなる画素については、以降の処理において縮小シームを構成する画素として選択され難い画素とすることが可能となる。結果として、複数に縮小シームが選択されるような場合においても、縮小シームが交差するなどして、同一の画素が、複数の縮小シームに含まれることが抑制され、縮小シームに属する画素を削除、または付加するなどしたときに、画素ずれが生じることを抑制することが可能となる。
【００８３】
尚、図５のフローチャートを参照して説明した処理により縮小シームを求める手法は、一般にダイナミックプログラミング法と呼ばれる手法であるが、縮小シームは、後述するグリーディ法により求めるようにしてもよい。
【００８４】
［部分探索処理］
次に、図９のフローチャートを参照して、部分画像探索処理について説明する。
【００８５】
ステップＳ７１において、隣接エネルギー比較部７２は、上述した全画像探索処理により縮小画像エネルギーマップに基づいて求められた縮小シームに基づいて、入力画像上の端部の画素の座標を取得する。すなわち、縮小シームは、入力画像上の複数の画素（例えば、ｍ画素×ｎ画素）からなるブロックを１画素とした縮小画像、すなわち低解像度画像に基づいて求められたものである。したがって、求められた縮小シームを構成する縮小画像上の画素は、入力画像においては、複数の画素からなるブロックに対応するものである。そこで、隣接エネルギー比較部７２は、縮小シームを構成する画素（ブロック）の、入力画像上の水平方向の一方の端部の画素の座標（Ｘ，Ｙ）を求める。尚、他方の端部の座標については、ブロックサイズがわかっているため、例えば、水平方向の座標としては、（Ｘ＋ｍ）として求めることが可能である。
【００８６】
ステップＳ７２において、入力画像エネルギーマップバッファ７１は、入力画像エネルギーマップ記憶部１３に記憶されている入力画像エネルギーマップを読み出して、一旦記憶する。
【００８７】
ステップＳ７３において、隣接エネルギー比較部７２は、部分シームの候補の起点画素（ｘｓ，ｙｓ）を縮小シームの端部の座標に基づいて、画素（Ｘ，０）に設定する。
【００８８】
ステップＳ７４において、隣接エネルギー比較部７２は、起点画素（ｘｓ，ｙｓ）のｘｓ座標が、（X＋ｍ（ｍ：水平方向ブロックサイズ））よりも小さいか否かを判定する。例えば、ｘｓ座標が（X＋ｍ）よりも小さい場合、処理は、ステップＳ７５に進む。
【００８９】
ステップＳ７５において、隣接エネルギー比較部７２は、起点画素（ｘｓ，ｙｓ）を、注目画素（ｘ，ｙ）に設定する。
【００９０】
ステップＳ７６において、隣接エネルギー比較部７２は、注目画素（ｘ，ｙ）のｙ座標が、入力画像の垂直方向の高さ（height）よりも小さいか否かを判定する。例えば、ｙ座標が入力画像の垂直方向の高さ（height）よりも小さい場合、処理は、ステップＳ７７に進む。
【００９１】
ステップＳ７７において、隣接エネルギー比較部７２は、入力画像エネルギーマップバッファ７１より入力画像エネルギーマップを読み出し、注目画素（ｘ，ｙ）の左下に隣接する画素（ｘ−１，ｙ＋１）、真下に隣接する画素（ｘ，ｙ＋１）、および右下に隣接する画素（ｘ＋１，ｙ＋１）のエネルギーがいずれも全てエネルギー最大値であるか否かを判定する。例えば、注目画素（ｘ，ｙ）の左下（ｘ−１，ｙ＋１）、真下（ｘ，ｙ＋１）、および右下（ｘ＋１，ｙ＋１）のそれぞれの画素のエネルギーがいずれも全てエネルギー最大値ではない場合、処理は、ステップＳ７８に進む。
【００９２】
ステップＳ７８において、隣接エネルギー比較部７２は、注目画素（ｘ，ｙ）の情報と、左下に隣接する画素（ｘ−１，ｙ＋１）、真下に隣接する画素（ｘ，ｙ＋１）、および右下に隣接する画素（ｘ＋１，ｙ＋１）のエネルギーの情報を選択経路設定部７４に通知する。選択経路設定部７４は、注目画素（ｘ，ｙ）の情報と、左下に隣接する画素（ｘ−１，ｙ＋１）、真下に隣接する画素（ｘ，ｙ＋１）、および右下に隣接する画素（ｘ＋１，ｙ＋１）のうち、エネルギーが最小となる画素を注目画素（ｘ，ｙ）からの選択経路に設定する。
【００９３】
ステップＳ７９において、選択経路設定部７４は、設定した注目画素（ｘ，ｙ）に対応付けて、選択経路の情報を選択経路記憶部７５に記憶させる。
【００９４】
ステップＳ８０において、隣接エネルギー比較部７２は、注目画素（ｘ，ｙ）の座標を選択経路として選択した座標に設定する。すなわち、隣接エネルギー比較部７２は、次の注目画素（ｘ，ｙ）の座標を画素（ｘ−１，ｙ＋１）、画素（ｘ，ｙ＋１）、および画素（ｘ＋１，ｙ＋１）のうち、エネルギーが最小となる画素に設定し、処理は、ステップＳ７６に戻る。
【００９５】
すなわち、ステップＳ７６において、ｙ座標が入力画像の高さ（height）に達するまで、ステップＳ７６乃至Ｓ８０の処理が繰り返される。例えば、ステップＳ７７において、注目画素（ｘ，ｙ）の左下、真下、および右下に隣接する画素（ｘ−１，ｙ＋１）、画素（ｘ，ｙ＋１）、および画素（ｘ＋１，ｙ＋１）のエネルギーがいずれも全てエネルギー最大値ではないとすれば、ステップＳ７６乃至Ｓ８０の処理により、順次以下のような処理がなされることになる。
【００９６】
例えば、図１０の最上段で示されるような入力画像エネルギーマップの場合、注目画素は、エネルギーが１の左上の画素に最初に設定されることとなる。このとき、ステップＳ７７の処理により、左下に隣接する画素がないので、真下、および右下に隣接する画素のうち、エネルギーが小さな画素は、図１０の２段目左側で示されるように、点線で囲まれたエネルギーが２の画素となり、その画素が選択経路として選択される。
【００９７】
次の処理では、そのエネルギーが２の画素が注目画素となるため、図１０の２段目右側で示されるように、左下、真下、および右下に隣接する画素のうち、エネルギーが最小となる画素として、点線で囲まれたエネルギーが１の画素が選択経路として選択される。
【００９８】
そして、この処理により、入力画像の高さに達することになるので、図１０の２段目右側で示されるように、図１０の入力画像エネルギーマップにおける、左上のエネルギー１の画素を部分シームの起点としたとき、左上のエネルギー１の画素、中央のエネルギーが２の画素、および右下のエネルギー１の画素からなる画素群が順次接続されることにより構成される経路が、部分シームの候補として設定されることになる。
【００９９】
ステップＳ７６において、ｙ座標が入力画像の高さ（height）より小さくなく、ｙ座標が入力画像の高さに達したと判定された場合、処理は、ステップＳ８５に進む。ステップＳ８５において、選択経路設定部７４は、部分シームの候補として設定された経路を構成する複数の画素群のエネルギーの積算値を求める。さらに、選択経路設定部７４は、部分シームの候補を構成する画素群の情報、および求められた積算値を、起点座標（ｘｓ，ｙｓ）に対応付けて選択経路記憶部７５に記憶させる。すなわち、部分シームの候補は、起点座標（ｘｓ，ｙｓ）により識別され、その起点座標（ｘｓ，ｙｓ）に対応付けて、積算エネルギー、および選択経路として選択された画素群の情報として選択経路記憶部７５に記憶される。
【０１００】
ステップＳ８６において、隣接エネルギー比較部７２は、起点画素（ｘｓ，ｙｓ）のｘｓ座標を１インクリメントし、処理は、ステップＳ７４に戻る。
【０１０１】
したがって、図１０の最上段で示される入力画像エネルギーマップの場合、その上段における左からエネルギーが１，２，３の画素がそれぞれ起点となる。このため、ステップＳ７４乃至Ｓ８０，Ｓ８５，Ｓ８６の処理が繰り返されると、図１０の場合、以下のように起点座標をとるエネルギーが１，２，３の画素のそれぞれについて、部分シーム候補が求められることになる。
【０１０２】
エネルギーが１の画素が起点の部分シームの候補は、上述した図１０の２段目で示される入力画像エネルギーマップにおける左上のエネルギー１画素、中央のエネルギー２の画素、および右下のエネルギーが１の画素から構成され、積算エネルギーが４となる。また、エネルギーが２の画素が起点の部分シームの候補は、図１０の３段目の左右で示される入力画像エネルギーマップにおける左上のエネルギー２画素、中央のエネルギー２の画素、および右下のエネルギーが１の画素から構成され、積算エネルギーが５となる。さらに、エネルギーが３の画素が起点の部分シームの候補は、図１０の４段目の左右で示される入力画像エネルギーマップにおける左上のエネルギー３の画素、中央のエネルギー２の画素、および右下のエネルギーが１の画素から構成され、積算エネルギーが６となる。
【０１０３】
ステップＳ７４において、起点座標（ｘｓ，ｙｓ）のｘｓ座標が（Ｘ＋ｍ）よりも小さくない、すなわち、縮小シームとして求められたブロックを超えると判定された場合、処理は、ステップＳ８７に進む。
【０１０４】
ステップＳ８７において、部分シーム決定部７６は、選択経路記憶部７５に記憶されている候補となる部分シームのうち、積算エネルギーが最も小さな部分シームを、部分シームとして決定し、決定した部分シームの情報を部分シーム記憶部７７に記憶させる。このとき、同時に、部分シーム決定部７６は、決定した部分シームの情報をエネルギー最大値挿入部８１に供給する。
【０１０５】
すなわち、図１０の最上段で示される入力画像エネルギーマップの場合、図１１で示されるように、図１０の２段目で示される起点座標が、左上のエネルギーが１の画素を起点とする部分シーム候補の積算エネルギーが最も小さいため、部分シームとして決定されることになる。尚、図１１においては、左から順に、図１０の２段目、３段目、および４段目の部分シーム候補に対する積算エネルギーの比較により、図１０の２段目に対応する点線で囲まれた左部の経路が部分シームとして選択されたことが示されている。
【０１０６】
ステップＳ８８において、エネルギー最大値挿入部８１は、入力画像エネルギーマップを読み出し、部分シームを構成する画素の座標のエネルギーとして、エネルギー最大値を挿入して処理を終了する。
【０１０７】
一方、ステップＳ７６において、注目画素（ｘ，ｙ）の左下、真下、および右下に隣接する画素（ｘ−１，ｙ＋１）、画素（ｘ，ｙ＋１）、および画素（ｘ＋１，ｙ＋１）のエネルギーがいずれも全てエネルギー最大値である場合、処理は、ステップＳ８１に進む。
【０１０８】
ステップＳ８１において、隣接エネルギー比較部７２は、左下、真下、および右下に隣接する画素のエネルギーがいずれも最大値であることを非隣接エネルギー比較部７３に通知する。非隣接エネルギー比較部７３は、注目画素（ｘ，ｙ）のｘ座標にＮ画素分追加したｘ座標の位置（ｘ＋Ｎ）が、入力画像内であるか否かを判定する。ステップＳ８１において、例えば、注目画素（ｘ，ｙ）のｘ座標にＮ画素分追加したｘ座標の位置（ｘ＋Ｎ）が、入力画像内である場合、処理は、ステップＳ８２に進む。
【０１０９】
ステップＳ８２において、非隣接エネルギー比較部７３は、右下に隣接する画素から右方向に連続して（Ｎ−１）画素分の画素を選択経路を選ぶ候補とする。
【０１１０】
一方、ステップＳ８１において、注目画素（ｘ，ｙ）のｘ座標にＮ画素分追加したｘ座標の位置（ｘ＋Ｎ）が、入力画像内ではない場合、処理は、ステップＳ８４に進む。
【０１１１】
ステップＳ８４において、非隣接エネルギー比較部７３は、左下に隣接する画素から左方向に連続して（Ｎ−１）画素分の画素を選択経路を選ぶ候補とする。
【０１１２】
ステップＳ８３において、非隣接エネルギー比較部７３は、右下に隣接する画素から右方向に連続して（Ｎ−１）画素分の画素、または、左下に隣接する画素から左方向に連続して（Ｎ−１）画素分の画素のうち、エネルギーが最小となる画素を選択経路として選択する。
【０１１３】
すなわち、非隣接エネルギー比較部７３は、図１２の左部で示されるように、注目画素の右下、真下、および左下に隣接する画素がエネルギー最大値である場合、入力画像内であれば、図１２の右部で示されるように、右下に隣接する画素に右方向に連続して隣接する（Ｎ−１）画素を、あたかも注目画素の右下、真下、および左下に隣接する画素として扱う。尚、図１２において、（Ｎ−１）画素＝６画素である場合が示されている。
【０１１４】
これは、全画像探索処理においても説明したが、エネルギー最大値は、求められた部分シームに属する画素に与えられるものであるから、エネルギー最大値である画素は、一旦部分シームとして選択されている可能性が高い画素である。
【０１１５】
例えば、複数の部分シームが選択される際、図１３の左部で示されるように、部分シームが交差すると、交差位置にはいずれの部分シームにも属する画素が存在することとなる。このような場合、複数の部分シームとして求められた画素を削除すると、図１３の右部で示されるように、複数の部分シームに重複して属する画素を含む行、または列では、部分シームの本数分だけ画素が削除できない恐れがある。結果として、他の行、または列とは画素数が異なる行、または列が発生することとなり、いわゆる画素あまり（ピクセルあまり）が生じてしまう。
【０１１６】
例えば、図１４の左部の斜線部で示されるように、一旦求められた部分シームに対して、図１４の右部の黒色で示されるように、エネルギー最大値を設定した場合、図１４の右部における太線で示されるような部分シームが求められ、丸印で示される注目画素において、左下の画素はエネルギー最大値であっても、真下、および右下はエネルギー最大値ではないので、そのいずれかを選択経路として選択することが可能であるので、部分シームが交差しないように設定することが可能である。
【０１１７】
しかしながら、図１０の左部で示されるような場合、単純にステップＳ７８の処理を実行すると、エネルギー最大値となるいずれかの画素が選択経路として選択されることとなってしまい、画素あまりが生じる恐れがあった。
【０１１８】
そこで、ステップＳ８２乃至Ｓ８４の処理が実行されることにより、注目画素の左下、真下、および右下に隣接する画素が、既に部分シームとして求められている可能性の高いエネルギー最大値となる画素である場合には、選択経路の候補から外される。そして、注目画素に対して隣接してはいないが、不連続ながら上記隣接画素に、さらに隣接する複数の画素を候補とする。すなわち、実質的に注目画素とは直接隣接していない画素が、隣接している画素と同様に扱われて、選択経路の候補とされる。さらに、この注目画素とは直接隣接していない選択経路の候補となる画素のうち、エネルギーが最小となる画素が選択経路として選択されることとなる。結果として、同一の画素が、複数の部分シームを構成する画素となる可能性が低減されるため、いわゆる、画素あまり（ピクセルあまり）という問題を生じ難くすることが可能となる。
【０１１９】
ここで、図４のフローチャートの説明に戻る。
【０１２０】
ステップＳ３２の処理により部分画像探索処理が終了し、部分シームが決定されると、処理は、ステップＳ３３に進む。
【０１２１】
ステップＳ３３において、同時処理シーム本数判定部７８は、部分シーム記憶部７７に記憶された部分シームの総本数が同時処理シーム本数に達しているか否かを判定する。ステップＳ３３において、例えば、同時処理本数に達していないと判定された場合、処理は、ステップＳ３４に進む。
【０１２２】
ステップＳ３４において、ブロック内部分シーム本数判定部７９は、部分シーム記憶部７７に記憶された部分シームのうち、現在処理している縮小シームを構成するブロック内で探索された部分シーム本数が、ブロック内で設定される所定本数に達しているか否かを判定する。ステップＳ３４において、例えば、記憶された部分シームのうち、現在処理している縮小シームを構成するブロック内で探索された部分シーム本数が、ブロック内で設定される所定本数に達していない場合、処理は、ステップＳ３２に戻る。すなわち、縮小シームを構成するブロック内において求められるべき部分シームの本数は、予め設定された所定本数であるので、所定本数となるまでは、ステップＳ３２，Ｓ３３の処理が繰り返されて、同一ブロック内で部分シームが探索され続けることになる。
【０１２３】
一方、ステップＳ３４において、記憶された部分シームのうち、現在処理している縮小シームを構成するブロック内で探索された部分シーム本数が、ブロック内で設定される所定本数を超えている場合、処理は、ステップＳ３１に戻る。すなわち、ブロック内で設定される所定数の部分シーム本数に達している場合、再度全画像探索処理により新たに縮小シームを求めて、求められた縮小シームに対して別途部分画像探索処理が必要となるため、処理は、ステップＳ３１に戻る。
【０１２４】
そして、ステップＳ３３において、例えば、同時処理本数に達していると判定された場合、処理は、ステップＳ３５に進む。ステップＳ３５において、同時処理シーム本数判定部７８は、出力部８０を制御して、部分シーム記憶部７７に記憶されている全ての部分シームの情報を加工部１６に出力させる。
【０１２５】
探索処理をまとめると以下のようになる。すなわち、まず、縮小画像に対応する縮小画像エネルギーマップを用いて、全画像探索処理を実行し、縮小シームを探索する。このとき、全画像探索処理は、上述したように、ダイナミックプログラミング法を用いて縮小シームを探索する。ここで求められる縮小シームは、縮小画像に対しては画素単位であるが、縮小画像の画素は、入力画像における複数の画素のブロックに対応するものであるので、ある程度、縮小シームは、入力画像からみて、求めるべき部分シームの探索範囲を限定する情報となる。
【０１２６】
そこで、次に、縮小シームとして求められた範囲の画素について、部分画像探索処理を実行し、部分シームを求める。部分画像探索処理においては、グリーディ法が用いられて部分シームが探索される。この際、求められた部分シームの本数が、同時処理本数として設定された本数に満たず、かつブロック内で設定される所定数の部分シームが求められている場合、再び全画像探索処理により縮小シームが求められ、同様に部分画像探索処理が実行される処理が繰り返される。
【０１２７】
そして、求められた部分シームの本数が、同時処理本数になったところで、求められた部分シームの情報が出力されて、出力された部分シームに基づいて、画像が加工される。
【０１２８】
以上の処理により、画像を削除、または追加する部分シームを探索するに当たり、まず、縮小画像より全画像探索処理で縮小シームを探索してから、探索された縮小シームのブロックの端部を構成する画素を起点とする部分シームのみを検索するようにした。このため、入力画像全体のうち、部分シームを詳細に探索する範囲を限定させることができので、入力画像全体から部分シームを探索するよりも計算量を低減させることが可能となる。
【０１２９】
また、全画像探索処理により探索された縮小シームのブロックを構成する端部を起点とする部分シームの探索に当たっては、全画像探索処理におけるダイナミックプログラミング法ではなく、グリーディ法を用いるようにしたので、計算量を低減することが可能となる。
【０１３０】
［ダイナミックプログラミング法とグリーディ法について］
ここで、ダイナミックプログラミング法とグリーディ法について説明する。ダイナミックプログラミング法とは、上述した全画像探索処理における縮小シームを探索する処理である。また、グリーディ法とは、上述した部分画像探索処理における部分シームを探索する処理である。
【０１３１】
より具体的には、図１５の上部で示されるエネルギーマップに対して、選択経路として設定された画素のエネルギーの積算値が最小となるシームを探索する場合、それぞれの手法は以下のようになる。尚、図１５の上部で示されるエネルギーマップの各画素のエネルギーは、最上段が左から１，４，２，４であり、２段目が５，２，１，３であり、３段目が４，１，２，５であり、４段目が１，３，２，１であり、５段目が１０，１０，３，２である。
【０１３２】
最上段最左部のエネルギーが１の画素を起点としたシームを探索する場合、ダイナミックプログラミング法では、まず、積算エネルギーマップが生成される。すなわち、積算エネルギーマップは、上から２段目の各画素より左上、真上、および右上に隣接する画素のエネルギーのうち最小エネルギーを積算する処理を下方向に順次繰り返すことにより生成される。そして、図１５の左下部で示されるように、積算エネルギーマップにしたがって、終点となる画素のうち積算エネルギーが最小となる画素と起点となる画素とを順次結ぶ選択経路を構成する画素群が最上段最左部のエネルギーが１の画素を起点としたシームが候補として選択される。そして、全ての起点に対して求められた候補となるシームのうち、積算エネルギーが最小となるシームが最終的に探索されることになる。図１５の左下部においては、太線で示される積算エネルギーが８となるシームが選択される。尚、図１５の左下部においては、５段目の画素における積算エネルギーは、左から１５，１５，９，８である。
【０１３３】
これに対して、グリーディ法では、図１５の右下部で示されるように、エネルギーマップに従って、各画素における左下、真下、および右下に隣接する画素のエネルギーのうち最小となるエネルギーの画素が順次選択経路として選択される。そして、各起点からは、候補となるシームが１本だけ求められ、それぞれの積算エネルギーのうち、最小のものが最終的に選択される。図１５の右下部においては、最上段における各起点となるシームの積算エネルギーは、起点となる画素毎に左から１５，１７，１５，１７となる。このため、最終的には、最上段におけるエネルギーが１または２の画素を起点とするシームが選択されることになる。
【０１３４】
以上の処理を比較すると、ダイナミックプログラミング法は、一旦積算エネルギーマップを求めた後、全ての起点となる画素に対して、全ての終点となる画素までのシームの積算エネルギーを比較した上で、シームを選択することとなる。このため、図１５の左下部で示されるように、グリーディ法よりも高い精度で、積算エネルギーが最小となるシームが選択される。しかしながら、一旦積算エネルギーマップを求めた後、全ての起点となる画素に対して、全ての終点となる画素までのシームの積算エネルギーを求めることとなるため、計算量が膨大なものとなる。一方、グリーディ法は、積算エネルギーマップを特に求める必要がなく、各画素について、いずれの選択経路とするかについては、一定の条件となるため、計算量を小さくすることが可能となる。しかしながら、図１５における右下部で示されるように、各画素毎にしか選択経路が決定されないため、真に積算エネルギーが最小となる経路からなるシームを探索することができない。
【０１３５】
しかしながら、本実施例においては、縮小画像に対して全画像探索処理において、精度の高いダイナミックプログラミング法を用いていることから、求められる縮小シームは比較的精度良く求めることが可能となる。また、縮小画像に対してダイナミックプログラミング法で全画像探索処理を実行しているため、入力画像に対してする処理よりも計算量を小さくすることが可能となる。さらに、入力画像のうち、縮小シームとして求められた範囲を起点とする画素のみに対してグリーディ法を用いた部分画像探索処理が実行されるため、軽い計算量でありながら、比較的精度良く求められた縮小シームの情報を用いて、部分シームを探索するため、部分シームの探索精度の低減を抑制しつつ、計算速度を向上させることが可能となる。
【０１３６】
さらに、計算速度を向上させたい場合、全画像探索処理において、グリーディ法を用いるようにしてもよい。すなわち、全画像探索処理において、グリーディ法を用いることで積算エネルギーマップを求めたり、全ての起点について、全ての終点までの積算エネルギーを比較した上でシームを探索する必要がなくなるので、計算速度をさらに向上させることが可能となる。
【０１３７】
また、以上においては、入力画像に対して、垂直方向に下方向にシームを探索する例について説明してきたが、同様の手法により水平方向にシームを探索することにより、水平方向の画素の削除、または挿入が可能となる。そして、これらを組み合わせて処理することにより、入力画像の水平方向、および垂直方向のそれぞれを縮小、または拡大させることが可能となる。
【０１３８】
例えば、図１６の左部で示されるように、２羽の水鳥が撮像されている入力画像に対して、従来のように水平方向、および垂直方向に対して、所定のスケーリングにより縮小すると、図１６の右上部で示されるように、画像の縮小率に合わせて、水鳥そのものも縮小される。これに対して、上述した処理を用いることにより、図１６の右下部で示されるように、画像は縮小されることとなるが、水鳥の大きさは画像全体の縮小率に対して小さなものとすることができる。結果として、画像のサイズは小さくなるが、被写体である水鳥の大きさの変化を小さくすることが可能となる。
【０１３９】
ところで、上述した一連の画像処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０１４０】
図１７は、汎用のパーソナルコンピュータの構成例を示している。このパーソナルコンピュータは、CPU(Central Processing Unit)１００１を内蔵している。CPU１００１にはバス１００４を介して、入出力インタ-フェイス１００５が接続されている。バス１００４には、ROM(Read Only Memory)１００２およびRAM(Random Access Memory)１００３が接続されている。
【０１４１】
入出力インタ-フェイス１００５には、ユーザが操作コマンドを入力するキーボード、マウスなどの入力デバイスよりなる入力部１００６、処理操作画面や処理結果の画像を表示デバイスに出力する出力部１００７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部１００８、LAN（Local Area Network）アダプタなどよりなり、インターネットに代表されるネットワークを介した通信処理を実行する通信部１００９が接続されている。また、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory)、DVD(Digital Versatile Disc)を含む）、光磁気ディスク（ＭＤ(Mini Disc)を含む）、もしくは半導体メモリなどのリムーバブルメディア１０１１に対してデータを読み書きするドライブ１０１０が接続されている。
【０１４２】
CPU１００１は、ROM１００２に記憶されているプログラム、または磁気ディスク、光ディスク、光磁気ディスク、もしくは半導体メモリ等のリムーバブルメディア１０１１から読み出されて記憶部１００８にインストールされ、記憶部１００８からRAM１００３にロードされたプログラムに従って各種の処理を実行する。RAM１００３にはまた、CPU１００１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１４３】
尚、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理は、もちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理を含むものである。
【０１４４】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【符号の説明】
【０１４５】
１ 画像処理装置， １１ 画像取得部， １２ エネルギーマップ生成部， １３ 入力画像エネルギーマップ記憶部， １４ 縮小画像エネルギーマップ記憶部， １５ 探索部， １６ 加工部， ２１ エネルギー算出部、 ２２ 縮小部， ３１ 全画像探索部， ３２ 部分画像探索部， ５１ 縮小画像エネルギーマップバッファ， ５２ 積算エネルギーマップ生成部， ５３ 積算エネルギーマップ記憶部， ５４ 最小シーム決定部， ５５ エネルギー最大値挿入部， ７１ 入力画像エネルギーマップバッファ， ７２ 隣接エネルギー比較部， ７３ 非隣接エネルギー比較部， ７４ 選択経路設定部， ７５ 選択経路記憶部， ７６ 部分シーム決定部， ７７ 部分シーム記憶部， ７８ 同時処理シーム本数判定部， ７９ ブロック内部分シーム本数判定部， ８０ 出力部， ８１ エネルギー最大値挿入部
【技術分野】
【０００１】
本発明は、画像処理装置および方法、並びにプログラムに関し、特に、シームカービング（SeamCarving）による不具合を低減し、処理を高速化できるようにする画像処理装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
シームカービング（SeamCarving）と呼ばれる画像の加工技術が一般に普及しつつある。
【０００３】
シームカービング（SeamCarving）とは、画像内にある主体となるオブジェクトの形状や大きさを不自然なものとならないように、画像を拡大、または縮小させる技術である。より具体的には、シームカービングでは、まず、画像の画素間の画素値や輝度の差分より、各画素単位でエネルギーが求められ、それらからエネルギー画像（エネルギーマップ）が生成される。次に、エネルギー画像を用いて、画像の一方の端部の各画素から順次隣接する画素を経由して他方の端部まで設定される経路において、経由する画素のエネルギーの積算値が最小となるような経路が、シームとして求められる。このシームを構成する、隣接する画素間においては、画素値または輝度値の変化が小さいと考えられる。すなわち、シームは、エネルギー変化の小さい画素が順次配列された領域であるため、シームを構成する画素に隣接する領域は、シームを構成する画素と同系統の画素値、または輝度値であると考えることができる。そこで、シームカービングでは、入力された画像からシームを構成する画素を削除する、または、付加することにより、画像における主体となるオブジェクトの形状や大きさの変化を小さくさせつつ、画像全体の大きさ縮小、または拡大する（特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２１７７６５公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、シームカービングでは、画像と同サイズのエネルギー画像が生成され、画像全域から最もエネルギー変化の小さなシームが探索されていた。このため、２本目以降のシームが探索される場合、１本のシームが探索される度に、探索されたシームを削除して画像を再構成し、エネルギー画像が毎度作成され直されるため、計算コストが非常に多くなっていた。
【０００６】
また、エネルギー画像の再作成を抑制するため、一度作成されたエネルギー画像を繰り返し使うようにすることを考える場合、複数のシームが同一のエネルギー画像から同時に削除されることになる。ところが、この場合、複数のシームが交差するような現象が生じると、１本のシームにより削除される幅が、１ピクセル分であったとすると、複数のシームが交差することにより生じる交点となる同一の画素が、複数のシームに含まれることになる。このとき、同時に複数のシームを削除、または付加すると、交点を含む行、または列の画素数が他の行、または列における画素数と異なる、いわゆるピクセルずれが生じてしまう恐れがあった。
【０００７】
本発明はこのような状況に鑑みてなされたものであり、特に、シームカービングにおいて、計算コストを低減させつつ、ピクセルずれを抑制できるようにするものである。
【課題を解決するための手段】
【０００８】
本発明の一側面の画像処理装置は、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段とを含み、前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる。
【０００９】
前記縮小シーム探索手段により探索された縮小シームを構成する、前記縮小画像の全ての画素に対応する前記縮小画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記縮小画像エネルギーマップを更新する縮小画像エネルギーマップ更新手段をさらに含ませるようにすることができる。
【００１０】
前記縮小シーム探索手段には、グリーディ法、または、ダイナミックプログラミング法により、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索させるようにすることができる。
【００１１】
前記部分シーム探索手段には、グリーディ法により、前記縮小シーム探索手段により前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索させるようにすることができる。
【００１２】
本発明の一側面の画像処理方法は、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段とを含み、前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置の画像処理方法であって、前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップとを含み、前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる。
【００１３】
本発明の一側面のプログラムは、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段とを含み、前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置を制御するコンピュータに、前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップとを含む処理を実行させ、前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
【００１４】
本発明の一側面においては、入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップが生成され、前記入力画像エネルギーマップが縮小されることにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップが生成され、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素が順次経由されて、前記他方の端部の画素に到達されるまでの複数の経路のうち、経由される画素のエネルギーの積算値が最小となる経路の画素間が結ばれることにより構成される縮小シームが探索され、探索された縮小シームの端部が構成される、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素が順次経由されて、前記他方の端部の画素に到達するまでの複数の経路のうち、経由される画素のエネルギーの積算値が最小となる画素間が結ばれることにより構成される部分シームが探索され、探索された部分シームが構成される、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値が挿入されて置換され、前記入力画像エネルギーマップが更新され、探索された前記部分シームが構成される画素が、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素が挿入されることで前記入力画像が縮小または拡大され、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素が順次経由されて、前記他方の端部の画素に到達するまでの複数の経路が探索されるにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素が隣接される画素として設定され、前記経路が構成される。
【００１５】
本発明の画像処理装置は、独立した装置であっても良いし、画像処理を行うブロックであっても良い。
【発明の効果】
【００１６】
本発明の一側面によれば、シームカービングにおける、計算コストを低減しつつ、ピクセルずれを低減することが可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明を適用した画像処理装置の一実施の形態の構成例を示すブロック図である。
【図２】図１の探索部の構成例を示すブロック図である。
【図３】シームカービング処理を説明するフローチャートである。
【図４】探索処理を説明するフローチャートである。
【図５】全画像探索処理を説明するフローチャートである。
【図６】全画像探索処理を説明する図である。
【図７】全画像探索処理を説明する図である。
【図８】全画像探索処理を説明する図である。
【図９】部分画像探索処理を説明するフローチャートである。
【図１０】部分画像探索処理を説明する図である。
【図１１】部分画像探索処理を説明する図である。
【図１２】部分画像探索処理を説明する図である。
【図１３】部分画像探索処理を説明する図である。
【図１４】部分画像探索処理を説明する図である。
【図１５】検索処理におけるダイナミックプログラミング法とグリーディ法とを説明する図である。
【図１６】シームカービング処理による処理結果を説明する図である。
【図１７】汎用のパーソナルコンピュータの構成例を説明する図である。
【発明を実施するための最良の形態】
【００１８】
［画像処理装置の構成例］
図１は、本発明を適用した画像処理装置のハードウェアの一実施の形態の構成例を示している。図１の画像処理装置１は、入力画像をシームカービングにより縮小、または拡大し、表示部２に表示するものである。
【００１９】
画像処理装置１は、画像取得部１１、エネルギーマップ生成部１２、入力画像エネルギーマップ記憶部１３、縮小画像エネルギーマップ記憶部１４、探索部１５、および加工部１６を備えている。
【００２０】
画像取得部１１は、入力画像を取得すると共に、エネルギーマップ生成部１２、および加工部１６に供給する。エネルギーマップ生成部１２は、エネルギー算出部２１、および縮小部２２を備えており、画像取得部１１からの入力画像より、入力画像と同サイズの入力画像エネルギーマップ、および、入力画像の縮小画像と同サイズの縮小画像エネルギーマップを生成する。より詳細には、エネルギー算出部２１は、以下の式（１）を算出することにより、各画素のエネルギーｅ（Ｉ）を算出し、入力画像に対応する画素単位のエネルギーからなる入力画像エネルギーマップを生成し、入力画像エネルギーマップ記憶部１３に記憶させる。また、エネルギー算出部２１は、生成した入力画像エネルギーマップを縮小部２２に供給する。
【００２１】
【００２２】
ここで、ｅ（Ｉ）は、Ｉで示される入力画像上の位置の各画素におけるエネルギーを示している。すなわち、式（１）で示される各画素のエネルギーｅ（Ｉ）は、入力画像の各画素におけるｘ，ｙ方向のそれぞれの隣接する画素間の画素値、または輝度値などの差分の絶対値和であることが示されている。
【００２３】
縮小部２２は、エネルギー算出部２１により算出されて生成され、入力画像と同サイズの入力画像エネルギーマップを縮小し、縮小画像エネルギーマップを生成して、縮小画像エネルギーマップ記憶部１４に記憶させる。より詳細には、縮小部２２は、入力画像の、例えば、ｍ画素×ｎ画素を１ブロックとし、その１ブロックを１画素と対応するように、各ブロックの画素のエネルギーの平均や中央値を求めて、エネルギーマップを構成することで縮小画像エネルギーマップを生成する。すなわち、縮小画像エネルギーマップは、入力画像に対して、ｍ画素×ｎ画素を１ブロックとし、その１ブロックを１画素と対応するように生成された縮小画像のエネルギーマップとして求められる。
【００２４】
探索部１５は、縮小画像エネルギーマップ記憶部１４より縮小画像エネルギーマップを読み出し、縮小画像の一方の端部より他方の端部まで順次隣接する画素を選択経路として選択し、選択経路の画素のエネルギーの積算値が最小となるように縮小シームを探索する。この際、探索部１５は、後述するダイナミックプログラミング法、またはグリーディ法により縮小シームを探索する。また、探索部１５は、一旦求めた縮小シームに属する画素のエネルギーを、エネルギー最大値に置換し、順次所定数の部分シームが求められるまで、同様の処理を繰り返す。
【００２５】
ここでいう、一方の端部より他方の端部まで順次隣接する画素からなる経路とは、例えば、縮小画像の上方端部のいずれかの画素に対して、右下、真下、および左下に隣接する３画素のいずれかが選択され、選択された画素に同様に隣接する３画素のいずれかが選択されるといったことが順次繰り返されて、下方端部のいずれかの画素にまで順次選択される画素が結ばれることにより構成される経路である。従って、一方の端部が縮小画像の左端部であり、他方の端部が右端部である場合、左端部のいずれかの画素に対して、右上、真右、および右下に隣接する３画素のいずれかが選択され、選択された画素に同様に隣接する３画素のいずれかが選択されるといったことが順次繰り返されて、右端部のいずれかの画素にまで順次選択される画素が結ばれることにより構成される経路となる。また、以降においては、縮小画像における上方端部から下方端部に縮小シームが探索されるとき、探索方向を下方向と称するものとし、同様に、左端部から右端部に縮小シームが探索されるとき、探索方向を右方向と称するものとする。さらに、注目画素が設定される場合、注目画素に対して探索方向に隣接する画素とは、探索方向が垂直方向のとき、注目画素に対して、右上、真上、および左上に隣接する３画素、または右下、真下、および左下に隣接する３画素を表すものとする。同様に、探索方向が水平方向のとき、注目画素に対して、左上、真左、および左下に隣接する３画素、または右上、真右、および右下に隣接する３画素を表すものとする。
【００２６】
さらに、探索部１５は、縮小画像エネルギーマップで検索された縮小シームを構成する縮小画像の画素に対応するブロックに属する、入力画像の端部の画素より順次隣接する画素のうち最小のエネルギーとなる画素を順次注目画素を設定する。そして、探索部１５は、順次設定された注目画素を結ぶことにより部分シームを探索する。このとき、探索部１５は、後述するグリーディ法により部分シームを探索する。この際、探索部１５は、一旦求めた入力画像の部分シームに属する画素に対応するエネルギーを、エネルギー最大値に置換して、順次所定数の部分シームが求めれらるまで、同様の処理を繰り返し、複数の部分シームを求める。
【００２７】
加工部１６は、画像取得部１１より供給されてくる画像より、探索部１５より求められた部分シームに対応する画素を削除、または同様の画素を付加することにより、画像を縮小、または拡大し、加工処理した後、表示部２に出力して表示させる。
【００２８】
［探索部１５の構成例］
次に、図２を参照して、探索部１５の詳細な構成例について説明する。
【００２９】
探索部１５は、全画像探索部３１、および部分画像探索部３２より構成されている。全画像探索部３１は、縮小画像エネルギーマップより、縮小画像における縮小シームを求めて、部分画像探索部３２に供給する。部分画像探索部３２は、全画像探索部３１より供給されてきた縮小シームの情報に基づいて、入力画像エネルギーマップより部分シームを求め加工部１６に出力する。
【００３０】
まず、全画像探索部３１の構成について説明する。全画像探索部３１は、縮小画像エネルギーマップバッファ５１、積算エネルギーマップ生成部５２、積算エネルギーマップ記憶部５３、縮小シーム決定部５４、およびエネルギー最大値挿入部５５を備えている。縮小画像エネルギーマップバッファ５１は、縮小画像エネルギーマップ記憶部１４に記憶されている縮小画像エネルギーマップを読み出して一旦記憶する。また、縮小画像エネルギーマップバッファ５１は、縮小シームに属する画素のエネルギーがエネルギー最大値挿入部５５より挿入されるエネルギー最大値で置換され、縮小画像エネルギーマップが更新されると、更新された縮小画像エネルギーマップを記憶する。
【００３１】
積算エネルギーマップ生成部５２は、以下の式（２）で示される計算を実行することにより、順次設定される注目画素に対して、縮小画像エネルギーマップの探索方向に対して逆方向に隣接する画素のエネルギーを順次積算し、積算エネルギーとして求める。
【００３２】
【００３３】
ここで、Ｍ（ｉ，ｊ）は、注目画素（ｉ，ｊ）における、それまでに順次設定された注目画素の積算エネルギーを示している。また、ｅ（ｉ，ｊ）は、注目画素（ｉ，ｊ）のエネルギーを閉めている。ｍｉｎ（Ａ，Ｂ，Ｃ）は、Ａ乃至Ｃの値のうち最小値を選択することを示している。
【００３４】
すなわち、積算エネルギーマップ生成部５２は、注目画素（ｉ，ｊ）において、注目画素（ｉ，ｊ）に対して、縮小シームの探索方向と逆方向に隣接する画素（ｉ−１，ｊ−１），（ｉ−１，ｊ），（ｉ−１，ｊ＋１）の積算エネルギーＭ（ｉ−１，ｊ−１），Ｍ（ｉ−１，ｊ），Ｍ（ｉ−１，ｊ＋１）のうち最小のものを選択し、注目画素のエネルギーと加算して、注目画素の積算エネルギーを算出する。積算エネルギーマップ生成部５２は、同様の処理を順次繰り返すことにより、縮小画像エネルギーマップの積算エネルギーマップを生成し、積算エネルギーマップ記憶部５３に記憶させる。尚、式（２）においては、入力画像に対して垂直方向に上方端部から下方端部の方向に向かう縮小シームを探索する場合の例が記載されている。このため、縮小シームの探索方向に対応して、式（２）は変化するものである。
【００３５】
縮小シーム決定部５４は、積算エネルギーマップ記憶部５３に記憶されている積算エネルギーマップの情報に基づいて、縮小画像の一方の端部の各画素より選択経路として選択された画素のエネルギーの積算値が順次最小となるように縮小シームを探索する。そして、縮小シーム決定部５４は、積算エネルギーが最小となる画素を順次結ぶ経路を縮小シームに決定し、部分画像探索部３２に供給する。さらに、縮小シーム決定部５４は、決定した縮小シームの情報をエネルギー最大値挿入部５５に供給する。
【００３６】
エネルギー最大値挿入部５５は、縮小エネルギーマップバッファ５１に記憶されている縮小エネルギーマップの各画素のエネルギーのうち、縮小シームに属する画素のエネルギーにエネルギー最大値を挿入することで更新する。すなわち、エネルギーは、何らかの有限の数値により表現されるが、その最大値で表現される場合は稀であり、事実上、その画素が縮小シームを構成する画素として選択されたことを示すために、実態と異なるエネルギー最大値が挿入される。
【００３７】
次に、部分画像探索部３２の構成について説明する。部分画像探索部３２は、入力画像エネルギーマップバッファ７１、隣接エネルギー比較部７２、非隣接エネルギー比較部７３、選択経路設定部７４、選択経路記憶部７５、部分シーム決定部７６、および部分シーム記憶部７７を備える。また、部分画像探索部３２は、同時処理シーム本数判定部７８、ブロック内部分シーム本数判定部７９、出力部８０、およびエネルギー最大値挿入部８１を備えている。
【００３８】
入力画像エネルギーマップバッファ７１は、入力画像エネルギー記憶部１３に記憶されている入力画像エネルギーマップの情報を読み出して、一旦記憶する。また、入力画像エネルギーマップバッファ７１は、エネルギー最大値挿入部８１により、求められた部分シームに属する画素のエネルギーに、エネルギー最大値が挿入されて置換された、入力画像エネルギーマップを更新して記憶する。
【００３９】
隣接エネルギー比較部７２は、全画像探索部３１より供給されてくる縮小シームを構成するブロックのうち、一方の端部のブロックに属する入力画像の画素のうち、一方の端部の画素より順次注目画素を設定する。そして、隣接エネルギー比較部７２は、順次設定される注目画素と、探索方向に隣接する画素のエネルギーとエネルギー最大値とを比較し、隣接する画素のエネルギーの全てがエネルギー最大値のみとなっているか否かを判定する。そして、隣接エネルギー比較部７２は、判定結果に応じて、全てがエネルギー最大値であるとき判定結果を非隣接エネルギー選択部７３に供給する。
【００４０】
非隣接エネルギー選択部７３は、隣接エネルギー比較部７２の判定結果により、注目画素に隣接する全ての画素がエネルギー最大値である場合、注目画素の位置に応じて、注目画素に隣接していない画素を、隣接画素として選択し、選択経路設定部７４に供給する。すなわち、非隣接エネルギー選択部７３は、注目画素に隣接していないが、注目画素に隣接した画素に、さらに隣接している複数の画素を隣接画素として選択する。
【００４１】
選択経路設定部７４は、入力画像マップバッファ７１に記憶されている入力画像マップの情報、および非隣接エネルギー選択部７３から供給されてくる隣接画素として設定された画素の情報に基づいて、縮小シームに属する入力画像の画素のうち、縮小シームの一方の端部から他方の端部への方向に隣接する画素のうち、エネルギーが最小となる画素を順次選択方向として設定し、選択経路記憶部７５に記憶させる。
【００４２】
部分シーム決定部７６は、選択経路記憶部７５に記憶されている、縮小シームに属する入力画像の一方の端部の各画素より、選択経路記憶部７５に記憶されている選択方向に存在する画素の積算エネルギーが最小となる経路を部分シームとして決定する。部分シーム決定部７６は、決定した部分シームの情報を部分シーム記憶部７７に記憶させる。
【００４３】
同時処理シーム本数判定部７８は、部分シーム記憶部７７に記憶されている部分シームの情報に基づいて、予め設定されている同時に処理可能な部分シームの本数に達しているか否かを判定する。そして、同時処理シーム本数判定部７８は、同時に処理可能なシーム本数に達していない場合、エネルギー最大値挿入部８１に通知する。さらに、同時処理シーム本数判定部７８は、入力画像エネルギーマップに新たに記憶された部分シームに属する画素のエネルギーにエネルギー最大値を挿入させて更新させると共に、新たに部分シームを探索させる。また、同時処理シーム本数判定部７８は、同時に処理可能なシーム本数に達した場合、出力部８０にその旨通知し、出力部８０より部分シーム記憶部７７に記憶されている部分シームの情報を加工部１６に出力させる。
【００４４】
ブロック内部分シーム本数判定部７９は、今現在の部分シーム本数が、縮小シームが求められた縮小画像を構成する画素からなる縮小ブロック単位で予め設定される本数となったか否かを判定する。そして、ブロック内部分シーム本数判定部７９は、今現在の部分シーム本数が、予め設定された本数となった場合、全画像探索部３１に対して新たな縮小シームを探索するように通知する。
【００４５】
［シームカービング処理］
次に、図３のフローチャートを参照して、シームカービング処理について説明する。
【００４６】
ステップＳ１において、画像取得部１１は、入力画像を取得し、取得した入力画像をエネルギーマップ生成部１２、および加工部１６に供給する。
【００４７】
ステップＳ１２において、エネルギーマップ生成部１２は、エネルギー算出部２１を制御して、入力画像の各画素の画素値、または輝度値などに基づいて、上述した式（１）を算出することにより、各画素のエネルギーを算出させる。さらに、エネルギーマップ生成部１２は、エネルギー算出部２１を制御して、各画素単位で算出されたエネルギーの値より入力画像エネルギーマップを生成させ、入力画像エネルギーマップ記憶部１３に記憶させると共に、縮小部２２に供給させる。
【００４８】
ステップＳ１３において、エネルギーマップ生成部１２は、縮小部２２を制御してエネルギーマップを縮小画像のサイズに処理させることにより、縮小画像エネルギーマップを生成させ、縮小画像エネルギーマップ記憶部１４に記憶させる。より詳細には、縮小部２２は、入力画像エネルギーマップを、例えば、ｍ画素×ｎ画素単位でブロック化し、その各ブロックを構成する各画素のエネルギーの平均値や中央値などを、縮小画像の各画素に対応するエネルギーとする縮小画像エネルギーマップを生成する。尚、この例においては、縮小画像に対応するエネルギーマップを縮小画像エネルギーマップと称するものとしているが、縮小画像エネルギーマップは、入力画像エネルギーマップを低解像度化したエネルギーマップと同様のものである。
【００４９】
ステップＳ１４において、探索部１５は、入力画像エネルギーマップ記憶部１３の入力画像エネルギーマップ、および縮小画像エネルギーマップ記憶部１４の縮小画像エネルギーマップに基づいて、探索処理を実行し、所定数の部分シームを探索する。すなわち、探索部１５は、入力画像の水平方向（ｘ方向）、または垂直方向（ｙ方向）に対して、隣接する画素のより構成される経路のうち、画素値、または輝度値の変化が小さい経路を、所定数だけ部分シームとして探索し、その情報を加工部１６に供給する。そして、探索部１５は、探索した所定数の部分シームの情報を加工部１６に供給する。尚、探索処理については、図４のフローチャートを参照して、後述するものとする。
【００５０】
ステップＳ１５において、加工部１６は、入力画像のシームカービングによる入力画像への加工処理が、縮小処理であるのか否かを判定し、例えば、縮小画像である場合、処理は、ステップＳ１６に進む。
【００５１】
ステップＳ１６において、加工部１６は、部分シームの情報に基づいて、入力画像より部分シームを構成する画素を削除し、削除した領域を詰めることにより、画像を縮小させる。
【００５２】
一方、ステップＳ１５において、入力画像のシームカービングによる入力画像への加工処理が、縮小処理ではない、すなわち、拡大処理であると判定された場合、処理は、ステップＳ１７に進む。
【００５３】
ステップＳ１７において、加工部１６は、部分シームの情報に基づいて、入力画像より部分シームを構成する画素に隣接する位置に、部分シームと同一の画素を挿入することにより、画像を拡大させる。
【００５４】
ステップＳ１８において、加工部１６は、加工処理された入力画像のサイズが、設定サイズであるか否かを判定する。ステップＳ１８において、例えば、縮小、または拡大により設定されたサイズではないと判定された場合、処理は、ステップＳ１４に戻り、それ以降の処理により、縮小、または拡大が繰り返される。一方、ステップＳ１８において、縮小、または拡大により設定されたサイズであると判定された場合、ステップＳ１９において、加工部１６は、入力画像に対して加工処理した画像を表示部２に出力して表示させる。
【００５５】
以上の処理により、まず、入力画像において、画素間の画素値、または輝度値の変化の少ない（エネルギーの積算値である積算エネルギーが最小となる）隣接する画素により構成される部分シームが求められる。そして、求められた部分シームを構成する画素が、入力画像より削除される、または挿入される。これにより入力画像が縮小、または拡大される加工処理が実現されるので、画像内における主だったオブジェクトの大きさを変更することなく、入力画像の全体の大きさを変化させることが可能となる。尚、以上の例においては、加工部１６が、部分シームと同一の画素を挿入することで画像を拡大させる例について説明してきたが、部分シーム近傍の画素と違和感の無い画素を挿入できればよいので、必ずしも同一の画像を挿入しなくても良い。従って、例えば、部分シームとして求められた画素の近傍の画素により補間生成される画素を部分シームとして求められた画素の近傍位置に挿入することにより、画像を拡大させるようにしてもよい。
【００５６】
［探索処理］
次に、図４のフローチャートを参照して、探索処理について説明する。
【００５７】
探索処理は、ステップＳ３１において、縮小画像エネルギーマップが用いられて全画像探索処理がなされることにより、縮小画像における縮小シームが求められる。そして縮小シームが求められると、ステップＳ３２において、全画像探索処理の探索結果である縮小シームに基づいて、部分画像探索処理が実行されて、入力画像に対する部分シームが求められる。
【００５８】
［全画像探索処理］
ここで、図５のフローチャートを参照して、縮小画像エネルギーマップを用いた全画像探索処理について説明する。尚、図５のフローチャートにおいては、方形状の画像のうち、上方端部の画素と、下方端部の画素とを隣接する画素間で順次結ぶ縮小シームを求める例について説明する。このように求められる縮小シームは、縮小画像の水平方向に対して、縮小、または拡大をするために求められるものである。従って、縮小画像の垂直方向に対しての縮小、または拡大に際しては、左端部の画素と右端部の画素とを隣接する画素間で順次結ぶことにより得られる縮小シームを同様の処理で求める必要がある。
【００５９】
ステップＳ５１において、縮小画像エネルギーマップバッファ５１は、縮小画像エネルギーマップ記憶部１４より縮小画像エネルギーマップを読み出し、一時的に記憶する。
【００６０】
ステップＳ５２において、積算エネルギーマップ生成部５２は、縮小画像エネルギーマップにおける注目画素（ｘ，ｙ）を（０，１）に設定し、初期化する。尚、ここで設定される座標は、縮小画像の左上端部の画素を原点（０，０）とし、水平方向のｘ座標は右方向を正とするものとし、垂直方向のｙ座標は下方向を正とするものとする。
【００６１】
ステップＳ５３において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｙ座標が縮小画像の垂直方向の高さ（height）より小さいか否かを判定する。ステップＳ５３において、例えば、最初の処理の場合、ｙ座標は、縮小画像の垂直方向の高さになっていないので、処理は、ステップＳ５４に進む。
【００６２】
ステップＳ５４において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｘ座標が縮小画像の水平方向の幅（width）よりも小さいか否かを判定する。ステップＳ５４において、注目画素（ｘ，ｙ）のｘ座標が縮小画像の水平方向の幅（width）よりも小さい場合、処理は、ステップＳ５５に進む。
【００６３】
ステップＳ５５において、積算エネルギーマップ生成部５３は、縮小画像エネルギーマップにおける注目画素（ｘ，ｙ）の左上（ｘ−１，ｙ＋１）、真上（ｘ，ｙ＋１）、および右上（ｘ＋１，ｙ＋１）のエネルギーのうち、最小となる積算エネルギーを持つ画素を選択する。積算エネルギーマップ生成部５３は、選択した画素の積算エネルギーと注目画素のエネルギーとを加算して、注目画素の積算エネルギーを求める。
【００６４】
ステップＳ５６において、積算エネルギーマップ生成部５３は、求めた積算エネルギーを注目画素の積算エネルギーとして、積算エネルギーマップ記憶部５３に記憶させる。尚、注目画素が、上端部より１画素下の場合、上端部の画素のエネルギーそのものが積算エネルギーとして利用される。
【００６５】
ステップＳ５７において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｘ座標を１インクリメントして、処理は、ステップＳ５４に戻る。そして、ステップＳ５４において、注目画素（ｘ，ｙ）のｘ座標が縮小画像の水平方向の幅（width）よりも小さくない、すなわち、水平方向について全ての処理が終了した場合、処理は、ステップＳ５８に進む。
【００６６】
ステップＳ５８において、積算エネルギーマップ生成部５３は、注目画素（ｘ，ｙ）のｙ座標を１インクリメントし、処理は、ステップＳ５３に戻る。すなわち、ステップＳ５３乃至Ｓ５８の処理が繰り返されることにより、縮小画像の各画素について探索方向と逆方向に隣接する３画素の積算エネルギーのうち、最小となる積算エネルギーを持つ画素が選択される。そして、選択された積算エネルギーと各画素のエネルギーとが順次積算されて、積算エネルギーマップが生成され、積算エネルギーマップ記憶部５３に記憶されていく。
【００６７】
より具体的には、例えば、図６の左上部で示されるような３画素×３画素の縮小画像エネルギーマップを考える場合、処理は以下のようにされることになる。尚、図６の左上部の縮小画像エネルギーマップのエネルギーは、上段は左から右に向かって、１，２，３であり、中段は左から右に向かって６，２，４であり、下段は左から右に向かって、２，３，１に設定されている。
【００６８】
ステップＳ５２の処理により、最初の注目画素（ｘ，ｙ）は、（０，１）のエネルギーが６の画素となる。そして、この注目画素（０，１）は、左端部の画素であるので、ステップＳ５５の処理により、真上の画素（０，０）の画素のエネルギー１と、右上の画素（１，０）の画素のエネルギー２との２画素のうち最小となる積算エネルギーの画素（０，０）が選択される。そして、図６の左下部で示されるように、積算エネルギーマップ生成部５３は、この選択された画素（０，０）のエネルギー１（ここでは積算エネルギーとして扱われる）と、注目画素（ｘ，ｙ）のエネルギー６の積算値７を積算エネルギーマップの注目画素（ｘ，ｙ）＝（０，１）における積算エネルギーとして積算エネルギーマップ記憶部５３に記憶させる。
【００６９】
ステップＳ５７の処理により、注目画素（ｘ，ｙ）のｘ座標が１インクリメントされて、エネルギーが注目画素（ｘ，ｙ）は、（１，１）のエネルギーが２の画素となる。そして、この注目画素（１，１）は、ステップＳ５５の処理により、左上の画素（０，０）のエネルギー１、真上の画素（１，０）の画素のエネルギー２と、右上の画素（２，０）の画素のエネルギー３との３画素のうち最小となる積算エネルギーの画素（０，０）が選択される。そして、図６の中央下部で示されるように、積算エネルギーマップ生成部５３は、この選択された画素（０，０）のエネルギー１と、注目画素（ｘ，ｙ）のエネルギー２の積算値３を積算エネルギーマップの注目画素（ｘ，ｙ）＝（１，１）における積算エネルギーとして積算エネルギーマップ記憶部５３に記憶させる。
【００７０】
さらに、ステップＳ５７の処理により、注目画素（ｘ，ｙ）のｘ座標がさらに１インクリメントされて、エネルギーが注目画素（ｘ，ｙ）は、（２，１）のエネルギーが４の画素となる。そして、この注目画素（２，１）は、縮小画像の右端部の画素であるので、ステップＳ５５の処理により、左上の画素（１，０）のエネルギー１、真上の画素（２，０）の画素のエネルギー３との２画素のうち最小となるエネルギーの画素（２，０）が選択される。そして、図６の右下部で示されるように、積算エネルギーマップ生成部５３は、この選択された画素（１，０）のエネルギー２と、注目画素（ｘ，ｙ）のエネルギー４の積算値６を積算エネルギーマップの注目画素（ｘ，ｙ）＝（２，１）における積算エネルギーとして積算エネルギーマップ記憶部５３に記憶させる。
【００７１】
この結果、２段目の積算エネルギーマップにおける中段の積算エネルギーは、図７の右上部のように左から７，３，６となる。このとき、注目画素（ｘ，ｙ）のｘ座標は、縮小画像の水平方向の幅(width＝２)より小さくないので、ステップＳ５８において、ｙ座標が１インクリメントされることにより、縮小画像における下段の各画素が順次注目画素に設定される。尚、図７の左上部は、縮小画像エネルギーマップが示されている。
【００７２】
上述した処理と同様の処理により、注目画素（ｘ，ｙ）が、（０，２）の場合、積算エネルギーマップに基づいて、真上の画素（０，１）の積算エネルギーが７であり、右上の画素（１，１）の積算エネルギーが３となる。このため、最小である積算エネルギー３の右上の画素（１，１）が選択されて、積算エネルギー３と、注目画素（ｘ，ｙ）＝（０，２）のエネルギー２とが積算されて、注目画素（ｘ，ｙ）＝（０，２）の積算エネルギーが５とされて、積算エネルギーマップに登録される。
【００７３】
また、注目画素（ｘ，ｙ）が画素（１，２）である場合、積算エネルギーマップに基づいて、左上の画素（０，１）の積算エネルギーが７であり、真上の画素（１，１）の積算エネルギーが３であり、右上の画素（２，１）の積算エネルギーが６となる。このため、最小である積算エネルギー３の真上の画素（１，１）が選択されて、積算エネルギー３と、注目画素（ｘ，ｙ）＝（１，２）のエネルギー３とが積算されて、注目画素（ｘ，ｙ）＝（１，２）の積算エネルギーが６とされて、積算エネルギーマップに登録される。
【００７４】
さらに、注目画素（ｘ，ｙ）が画素（２，２）である場合、積算エネルギーマップに基づいて、左上の画素（１，１）の積算エネルギーが３であり、真上の画素（２，１）の積算エネルギーが６となる。このため、最小である積算エネルギー３の左上の画素（１，１）が選択されて、積算エネルギー３と、注目画素（ｘ，ｙ）＝（２，２）のエネルギー１とが積算されて、注目画素（ｘ，ｙ）＝（２，２）の積算エネルギーが４とされて、積算エネルギーマップに登録される。
【００７５】
この結果、積算エネルギーマップは、図８の右上部で示されるように構成され、下段の積算エネルギーは、左から５，６，４となる。尚、図８の左上部は、縮小画像エネルギーマップが示されている。
【００７６】
このように、ステップＳ５３乃至Ｓ５８の処理が繰り返されることにより、例えば、図８の左上部で示されるような縮小画像エネルギーマップが得られた場合、図８の右上部で示されるような積算エネルギーマップが求められて、積算エネルギーマップ記憶部５３に記憶されることになる。
【００７７】
ここで、図５のフローチャートの説明に戻る。
【００７８】
ステップＳ５３において、注目画素（ｘ，ｙ）のｙ座標が縮小画像の垂直方向の高さよりも小さくないと判定された場合、すなわち、上述したように積算エネルギーマップが完成されて、積算エネルギーマップ記憶部５３に記憶されたとみなされた場合、処理は、ステップＳ５９に進む。
【００７９】
ステップＳ５９において、縮小シーム決定部５４は、積算エネルギーマップ記憶部５３に記憶されている積算エネルギーマップを読み出し、積算エネルギーが最小となる最下段の画素を検索し、縮小シームの端部を下方の端部とする。さらに、縮小シーム決定部５４は、縮小シームの下方の端部の画素より順次、上方に隣接する画素、すなわち、右上、真上、および左上に隣接する画素のうち、積算エネルギーが最小となる画素を順次上方に向かって探索する処理を繰り返し、上段の端部の画素まで探索する。そして、縮小シーム決定部５４は、順次探索された画素を結ぶ経路を縮小シームとして決定し、その情報を部分画像探索部３２に供給すると共にエネルギー最大値挿入部５５に供給する。
【００８０】
すなわち、図８の右上部の積算エネルギーマップの場合、最下段における積算エネルギーの最小値は、図８の丸印で示される積算エネルギーが４であって、エネルギーが１の画素（２，２）である。すなわち、この画素（２，２）が縮小シームの下方の端部となる。そして、この画素（２，２）からみて、上方に隣接する画素（２，１），（１，１）のうち、積算エネルギーの最小値は、積算エネルギーが３であって、エネルギーが２の画素（１，１）である。さらに、この画素（１，１）からみて、上方に隣接する画素（０，０），（１，０），（２，０）のうち、積算エネルギーの最小値は、積算エネルギーが１であって、エネルギーが１の画素（０，０）である。
【００８１】
すなわち、下方の端部である画素（２，２）より上方の端部である画素（０，０）まで順次探索された画素（２，２），（１，１），（０，０）の経路は、順次積算されるエネルギーが最小となる。したがって、この画素（２，２），（１，１），（０，０）から構成される経路は、隣接する画素間の画素値、または輝度値の変化が最小となる縮小画像上の経路、すなわち、縮小シームを構成していることになる。このため、縮小シーム決定部５４は、これらの探索された画素の座標の情報に基づいて構成される経路を縮小シームに決定する。
【００８２】
ステップＳ６０において、エネルギー最大値挿入部５５は、縮小画像エネルギーマップバッファ５１に記憶されている縮小画像エネルギーマップを読み出し、縮小シーム決定部５４で決定された縮小シームを構成する各画素のエネルギーに最大値を挿入して更新する。この結果、最大値からなる画素については、以降の処理において縮小シームを構成する画素として選択され難い画素とすることが可能となる。結果として、複数に縮小シームが選択されるような場合においても、縮小シームが交差するなどして、同一の画素が、複数の縮小シームに含まれることが抑制され、縮小シームに属する画素を削除、または付加するなどしたときに、画素ずれが生じることを抑制することが可能となる。
【００８３】
尚、図５のフローチャートを参照して説明した処理により縮小シームを求める手法は、一般にダイナミックプログラミング法と呼ばれる手法であるが、縮小シームは、後述するグリーディ法により求めるようにしてもよい。
【００８４】
［部分探索処理］
次に、図９のフローチャートを参照して、部分画像探索処理について説明する。
【００８５】
ステップＳ７１において、隣接エネルギー比較部７２は、上述した全画像探索処理により縮小画像エネルギーマップに基づいて求められた縮小シームに基づいて、入力画像上の端部の画素の座標を取得する。すなわち、縮小シームは、入力画像上の複数の画素（例えば、ｍ画素×ｎ画素）からなるブロックを１画素とした縮小画像、すなわち低解像度画像に基づいて求められたものである。したがって、求められた縮小シームを構成する縮小画像上の画素は、入力画像においては、複数の画素からなるブロックに対応するものである。そこで、隣接エネルギー比較部７２は、縮小シームを構成する画素（ブロック）の、入力画像上の水平方向の一方の端部の画素の座標（Ｘ，Ｙ）を求める。尚、他方の端部の座標については、ブロックサイズがわかっているため、例えば、水平方向の座標としては、（Ｘ＋ｍ）として求めることが可能である。
【００８６】
ステップＳ７２において、入力画像エネルギーマップバッファ７１は、入力画像エネルギーマップ記憶部１３に記憶されている入力画像エネルギーマップを読み出して、一旦記憶する。
【００８７】
ステップＳ７３において、隣接エネルギー比較部７２は、部分シームの候補の起点画素（ｘｓ，ｙｓ）を縮小シームの端部の座標に基づいて、画素（Ｘ，０）に設定する。
【００８８】
ステップＳ７４において、隣接エネルギー比較部７２は、起点画素（ｘｓ，ｙｓ）のｘｓ座標が、（X＋ｍ（ｍ：水平方向ブロックサイズ））よりも小さいか否かを判定する。例えば、ｘｓ座標が（X＋ｍ）よりも小さい場合、処理は、ステップＳ７５に進む。
【００８９】
ステップＳ７５において、隣接エネルギー比較部７２は、起点画素（ｘｓ，ｙｓ）を、注目画素（ｘ，ｙ）に設定する。
【００９０】
ステップＳ７６において、隣接エネルギー比較部７２は、注目画素（ｘ，ｙ）のｙ座標が、入力画像の垂直方向の高さ（height）よりも小さいか否かを判定する。例えば、ｙ座標が入力画像の垂直方向の高さ（height）よりも小さい場合、処理は、ステップＳ７７に進む。
【００９１】
ステップＳ７７において、隣接エネルギー比較部７２は、入力画像エネルギーマップバッファ７１より入力画像エネルギーマップを読み出し、注目画素（ｘ，ｙ）の左下に隣接する画素（ｘ−１，ｙ＋１）、真下に隣接する画素（ｘ，ｙ＋１）、および右下に隣接する画素（ｘ＋１，ｙ＋１）のエネルギーがいずれも全てエネルギー最大値であるか否かを判定する。例えば、注目画素（ｘ，ｙ）の左下（ｘ−１，ｙ＋１）、真下（ｘ，ｙ＋１）、および右下（ｘ＋１，ｙ＋１）のそれぞれの画素のエネルギーがいずれも全てエネルギー最大値ではない場合、処理は、ステップＳ７８に進む。
【００９２】
ステップＳ７８において、隣接エネルギー比較部７２は、注目画素（ｘ，ｙ）の情報と、左下に隣接する画素（ｘ−１，ｙ＋１）、真下に隣接する画素（ｘ，ｙ＋１）、および右下に隣接する画素（ｘ＋１，ｙ＋１）のエネルギーの情報を選択経路設定部７４に通知する。選択経路設定部７４は、注目画素（ｘ，ｙ）の情報と、左下に隣接する画素（ｘ−１，ｙ＋１）、真下に隣接する画素（ｘ，ｙ＋１）、および右下に隣接する画素（ｘ＋１，ｙ＋１）のうち、エネルギーが最小となる画素を注目画素（ｘ，ｙ）からの選択経路に設定する。
【００９３】
ステップＳ７９において、選択経路設定部７４は、設定した注目画素（ｘ，ｙ）に対応付けて、選択経路の情報を選択経路記憶部７５に記憶させる。
【００９４】
ステップＳ８０において、隣接エネルギー比較部７２は、注目画素（ｘ，ｙ）の座標を選択経路として選択した座標に設定する。すなわち、隣接エネルギー比較部７２は、次の注目画素（ｘ，ｙ）の座標を画素（ｘ−１，ｙ＋１）、画素（ｘ，ｙ＋１）、および画素（ｘ＋１，ｙ＋１）のうち、エネルギーが最小となる画素に設定し、処理は、ステップＳ７６に戻る。
【００９５】
すなわち、ステップＳ７６において、ｙ座標が入力画像の高さ（height）に達するまで、ステップＳ７６乃至Ｓ８０の処理が繰り返される。例えば、ステップＳ７７において、注目画素（ｘ，ｙ）の左下、真下、および右下に隣接する画素（ｘ−１，ｙ＋１）、画素（ｘ，ｙ＋１）、および画素（ｘ＋１，ｙ＋１）のエネルギーがいずれも全てエネルギー最大値ではないとすれば、ステップＳ７６乃至Ｓ８０の処理により、順次以下のような処理がなされることになる。
【００９６】
例えば、図１０の最上段で示されるような入力画像エネルギーマップの場合、注目画素は、エネルギーが１の左上の画素に最初に設定されることとなる。このとき、ステップＳ７７の処理により、左下に隣接する画素がないので、真下、および右下に隣接する画素のうち、エネルギーが小さな画素は、図１０の２段目左側で示されるように、点線で囲まれたエネルギーが２の画素となり、その画素が選択経路として選択される。
【００９７】
次の処理では、そのエネルギーが２の画素が注目画素となるため、図１０の２段目右側で示されるように、左下、真下、および右下に隣接する画素のうち、エネルギーが最小となる画素として、点線で囲まれたエネルギーが１の画素が選択経路として選択される。
【００９８】
そして、この処理により、入力画像の高さに達することになるので、図１０の２段目右側で示されるように、図１０の入力画像エネルギーマップにおける、左上のエネルギー１の画素を部分シームの起点としたとき、左上のエネルギー１の画素、中央のエネルギーが２の画素、および右下のエネルギー１の画素からなる画素群が順次接続されることにより構成される経路が、部分シームの候補として設定されることになる。
【００９９】
ステップＳ７６において、ｙ座標が入力画像の高さ（height）より小さくなく、ｙ座標が入力画像の高さに達したと判定された場合、処理は、ステップＳ８５に進む。ステップＳ８５において、選択経路設定部７４は、部分シームの候補として設定された経路を構成する複数の画素群のエネルギーの積算値を求める。さらに、選択経路設定部７４は、部分シームの候補を構成する画素群の情報、および求められた積算値を、起点座標（ｘｓ，ｙｓ）に対応付けて選択経路記憶部７５に記憶させる。すなわち、部分シームの候補は、起点座標（ｘｓ，ｙｓ）により識別され、その起点座標（ｘｓ，ｙｓ）に対応付けて、積算エネルギー、および選択経路として選択された画素群の情報として選択経路記憶部７５に記憶される。
【０１００】
ステップＳ８６において、隣接エネルギー比較部７２は、起点画素（ｘｓ，ｙｓ）のｘｓ座標を１インクリメントし、処理は、ステップＳ７４に戻る。
【０１０１】
したがって、図１０の最上段で示される入力画像エネルギーマップの場合、その上段における左からエネルギーが１，２，３の画素がそれぞれ起点となる。このため、ステップＳ７４乃至Ｓ８０，Ｓ８５，Ｓ８６の処理が繰り返されると、図１０の場合、以下のように起点座標をとるエネルギーが１，２，３の画素のそれぞれについて、部分シーム候補が求められることになる。
【０１０２】
エネルギーが１の画素が起点の部分シームの候補は、上述した図１０の２段目で示される入力画像エネルギーマップにおける左上のエネルギー１画素、中央のエネルギー２の画素、および右下のエネルギーが１の画素から構成され、積算エネルギーが４となる。また、エネルギーが２の画素が起点の部分シームの候補は、図１０の３段目の左右で示される入力画像エネルギーマップにおける左上のエネルギー２画素、中央のエネルギー２の画素、および右下のエネルギーが１の画素から構成され、積算エネルギーが５となる。さらに、エネルギーが３の画素が起点の部分シームの候補は、図１０の４段目の左右で示される入力画像エネルギーマップにおける左上のエネルギー３の画素、中央のエネルギー２の画素、および右下のエネルギーが１の画素から構成され、積算エネルギーが６となる。
【０１０３】
ステップＳ７４において、起点座標（ｘｓ，ｙｓ）のｘｓ座標が（Ｘ＋ｍ）よりも小さくない、すなわち、縮小シームとして求められたブロックを超えると判定された場合、処理は、ステップＳ８７に進む。
【０１０４】
ステップＳ８７において、部分シーム決定部７６は、選択経路記憶部７５に記憶されている候補となる部分シームのうち、積算エネルギーが最も小さな部分シームを、部分シームとして決定し、決定した部分シームの情報を部分シーム記憶部７７に記憶させる。このとき、同時に、部分シーム決定部７６は、決定した部分シームの情報をエネルギー最大値挿入部８１に供給する。
【０１０５】
すなわち、図１０の最上段で示される入力画像エネルギーマップの場合、図１１で示されるように、図１０の２段目で示される起点座標が、左上のエネルギーが１の画素を起点とする部分シーム候補の積算エネルギーが最も小さいため、部分シームとして決定されることになる。尚、図１１においては、左から順に、図１０の２段目、３段目、および４段目の部分シーム候補に対する積算エネルギーの比較により、図１０の２段目に対応する点線で囲まれた左部の経路が部分シームとして選択されたことが示されている。
【０１０６】
ステップＳ８８において、エネルギー最大値挿入部８１は、入力画像エネルギーマップを読み出し、部分シームを構成する画素の座標のエネルギーとして、エネルギー最大値を挿入して処理を終了する。
【０１０７】
一方、ステップＳ７６において、注目画素（ｘ，ｙ）の左下、真下、および右下に隣接する画素（ｘ−１，ｙ＋１）、画素（ｘ，ｙ＋１）、および画素（ｘ＋１，ｙ＋１）のエネルギーがいずれも全てエネルギー最大値である場合、処理は、ステップＳ８１に進む。
【０１０８】
ステップＳ８１において、隣接エネルギー比較部７２は、左下、真下、および右下に隣接する画素のエネルギーがいずれも最大値であることを非隣接エネルギー比較部７３に通知する。非隣接エネルギー比較部７３は、注目画素（ｘ，ｙ）のｘ座標にＮ画素分追加したｘ座標の位置（ｘ＋Ｎ）が、入力画像内であるか否かを判定する。ステップＳ８１において、例えば、注目画素（ｘ，ｙ）のｘ座標にＮ画素分追加したｘ座標の位置（ｘ＋Ｎ）が、入力画像内である場合、処理は、ステップＳ８２に進む。
【０１０９】
ステップＳ８２において、非隣接エネルギー比較部７３は、右下に隣接する画素から右方向に連続して（Ｎ−１）画素分の画素を選択経路を選ぶ候補とする。
【０１１０】
一方、ステップＳ８１において、注目画素（ｘ，ｙ）のｘ座標にＮ画素分追加したｘ座標の位置（ｘ＋Ｎ）が、入力画像内ではない場合、処理は、ステップＳ８４に進む。
【０１１１】
ステップＳ８４において、非隣接エネルギー比較部７３は、左下に隣接する画素から左方向に連続して（Ｎ−１）画素分の画素を選択経路を選ぶ候補とする。
【０１１２】
ステップＳ８３において、非隣接エネルギー比較部７３は、右下に隣接する画素から右方向に連続して（Ｎ−１）画素分の画素、または、左下に隣接する画素から左方向に連続して（Ｎ−１）画素分の画素のうち、エネルギーが最小となる画素を選択経路として選択する。
【０１１３】
すなわち、非隣接エネルギー比較部７３は、図１２の左部で示されるように、注目画素の右下、真下、および左下に隣接する画素がエネルギー最大値である場合、入力画像内であれば、図１２の右部で示されるように、右下に隣接する画素に右方向に連続して隣接する（Ｎ−１）画素を、あたかも注目画素の右下、真下、および左下に隣接する画素として扱う。尚、図１２において、（Ｎ−１）画素＝６画素である場合が示されている。
【０１１４】
これは、全画像探索処理においても説明したが、エネルギー最大値は、求められた部分シームに属する画素に与えられるものであるから、エネルギー最大値である画素は、一旦部分シームとして選択されている可能性が高い画素である。
【０１１５】
例えば、複数の部分シームが選択される際、図１３の左部で示されるように、部分シームが交差すると、交差位置にはいずれの部分シームにも属する画素が存在することとなる。このような場合、複数の部分シームとして求められた画素を削除すると、図１３の右部で示されるように、複数の部分シームに重複して属する画素を含む行、または列では、部分シームの本数分だけ画素が削除できない恐れがある。結果として、他の行、または列とは画素数が異なる行、または列が発生することとなり、いわゆる画素あまり（ピクセルあまり）が生じてしまう。
【０１１６】
例えば、図１４の左部の斜線部で示されるように、一旦求められた部分シームに対して、図１４の右部の黒色で示されるように、エネルギー最大値を設定した場合、図１４の右部における太線で示されるような部分シームが求められ、丸印で示される注目画素において、左下の画素はエネルギー最大値であっても、真下、および右下はエネルギー最大値ではないので、そのいずれかを選択経路として選択することが可能であるので、部分シームが交差しないように設定することが可能である。
【０１１７】
しかしながら、図１０の左部で示されるような場合、単純にステップＳ７８の処理を実行すると、エネルギー最大値となるいずれかの画素が選択経路として選択されることとなってしまい、画素あまりが生じる恐れがあった。
【０１１８】
そこで、ステップＳ８２乃至Ｓ８４の処理が実行されることにより、注目画素の左下、真下、および右下に隣接する画素が、既に部分シームとして求められている可能性の高いエネルギー最大値となる画素である場合には、選択経路の候補から外される。そして、注目画素に対して隣接してはいないが、不連続ながら上記隣接画素に、さらに隣接する複数の画素を候補とする。すなわち、実質的に注目画素とは直接隣接していない画素が、隣接している画素と同様に扱われて、選択経路の候補とされる。さらに、この注目画素とは直接隣接していない選択経路の候補となる画素のうち、エネルギーが最小となる画素が選択経路として選択されることとなる。結果として、同一の画素が、複数の部分シームを構成する画素となる可能性が低減されるため、いわゆる、画素あまり（ピクセルあまり）という問題を生じ難くすることが可能となる。
【０１１９】
ここで、図４のフローチャートの説明に戻る。
【０１２０】
ステップＳ３２の処理により部分画像探索処理が終了し、部分シームが決定されると、処理は、ステップＳ３３に進む。
【０１２１】
ステップＳ３３において、同時処理シーム本数判定部７８は、部分シーム記憶部７７に記憶された部分シームの総本数が同時処理シーム本数に達しているか否かを判定する。ステップＳ３３において、例えば、同時処理本数に達していないと判定された場合、処理は、ステップＳ３４に進む。
【０１２２】
ステップＳ３４において、ブロック内部分シーム本数判定部７９は、部分シーム記憶部７７に記憶された部分シームのうち、現在処理している縮小シームを構成するブロック内で探索された部分シーム本数が、ブロック内で設定される所定本数に達しているか否かを判定する。ステップＳ３４において、例えば、記憶された部分シームのうち、現在処理している縮小シームを構成するブロック内で探索された部分シーム本数が、ブロック内で設定される所定本数に達していない場合、処理は、ステップＳ３２に戻る。すなわち、縮小シームを構成するブロック内において求められるべき部分シームの本数は、予め設定された所定本数であるので、所定本数となるまでは、ステップＳ３２，Ｓ３３の処理が繰り返されて、同一ブロック内で部分シームが探索され続けることになる。
【０１２３】
一方、ステップＳ３４において、記憶された部分シームのうち、現在処理している縮小シームを構成するブロック内で探索された部分シーム本数が、ブロック内で設定される所定本数を超えている場合、処理は、ステップＳ３１に戻る。すなわち、ブロック内で設定される所定数の部分シーム本数に達している場合、再度全画像探索処理により新たに縮小シームを求めて、求められた縮小シームに対して別途部分画像探索処理が必要となるため、処理は、ステップＳ３１に戻る。
【０１２４】
そして、ステップＳ３３において、例えば、同時処理本数に達していると判定された場合、処理は、ステップＳ３５に進む。ステップＳ３５において、同時処理シーム本数判定部７８は、出力部８０を制御して、部分シーム記憶部７７に記憶されている全ての部分シームの情報を加工部１６に出力させる。
【０１２５】
探索処理をまとめると以下のようになる。すなわち、まず、縮小画像に対応する縮小画像エネルギーマップを用いて、全画像探索処理を実行し、縮小シームを探索する。このとき、全画像探索処理は、上述したように、ダイナミックプログラミング法を用いて縮小シームを探索する。ここで求められる縮小シームは、縮小画像に対しては画素単位であるが、縮小画像の画素は、入力画像における複数の画素のブロックに対応するものであるので、ある程度、縮小シームは、入力画像からみて、求めるべき部分シームの探索範囲を限定する情報となる。
【０１２６】
そこで、次に、縮小シームとして求められた範囲の画素について、部分画像探索処理を実行し、部分シームを求める。部分画像探索処理においては、グリーディ法が用いられて部分シームが探索される。この際、求められた部分シームの本数が、同時処理本数として設定された本数に満たず、かつブロック内で設定される所定数の部分シームが求められている場合、再び全画像探索処理により縮小シームが求められ、同様に部分画像探索処理が実行される処理が繰り返される。
【０１２７】
そして、求められた部分シームの本数が、同時処理本数になったところで、求められた部分シームの情報が出力されて、出力された部分シームに基づいて、画像が加工される。
【０１２８】
以上の処理により、画像を削除、または追加する部分シームを探索するに当たり、まず、縮小画像より全画像探索処理で縮小シームを探索してから、探索された縮小シームのブロックの端部を構成する画素を起点とする部分シームのみを検索するようにした。このため、入力画像全体のうち、部分シームを詳細に探索する範囲を限定させることができので、入力画像全体から部分シームを探索するよりも計算量を低減させることが可能となる。
【０１２９】
また、全画像探索処理により探索された縮小シームのブロックを構成する端部を起点とする部分シームの探索に当たっては、全画像探索処理におけるダイナミックプログラミング法ではなく、グリーディ法を用いるようにしたので、計算量を低減することが可能となる。
【０１３０】
［ダイナミックプログラミング法とグリーディ法について］
ここで、ダイナミックプログラミング法とグリーディ法について説明する。ダイナミックプログラミング法とは、上述した全画像探索処理における縮小シームを探索する処理である。また、グリーディ法とは、上述した部分画像探索処理における部分シームを探索する処理である。
【０１３１】
より具体的には、図１５の上部で示されるエネルギーマップに対して、選択経路として設定された画素のエネルギーの積算値が最小となるシームを探索する場合、それぞれの手法は以下のようになる。尚、図１５の上部で示されるエネルギーマップの各画素のエネルギーは、最上段が左から１，４，２，４であり、２段目が５，２，１，３であり、３段目が４，１，２，５であり、４段目が１，３，２，１であり、５段目が１０，１０，３，２である。
【０１３２】
最上段最左部のエネルギーが１の画素を起点としたシームを探索する場合、ダイナミックプログラミング法では、まず、積算エネルギーマップが生成される。すなわち、積算エネルギーマップは、上から２段目の各画素より左上、真上、および右上に隣接する画素のエネルギーのうち最小エネルギーを積算する処理を下方向に順次繰り返すことにより生成される。そして、図１５の左下部で示されるように、積算エネルギーマップにしたがって、終点となる画素のうち積算エネルギーが最小となる画素と起点となる画素とを順次結ぶ選択経路を構成する画素群が最上段最左部のエネルギーが１の画素を起点としたシームが候補として選択される。そして、全ての起点に対して求められた候補となるシームのうち、積算エネルギーが最小となるシームが最終的に探索されることになる。図１５の左下部においては、太線で示される積算エネルギーが８となるシームが選択される。尚、図１５の左下部においては、５段目の画素における積算エネルギーは、左から１５，１５，９，８である。
【０１３３】
これに対して、グリーディ法では、図１５の右下部で示されるように、エネルギーマップに従って、各画素における左下、真下、および右下に隣接する画素のエネルギーのうち最小となるエネルギーの画素が順次選択経路として選択される。そして、各起点からは、候補となるシームが１本だけ求められ、それぞれの積算エネルギーのうち、最小のものが最終的に選択される。図１５の右下部においては、最上段における各起点となるシームの積算エネルギーは、起点となる画素毎に左から１５，１７，１５，１７となる。このため、最終的には、最上段におけるエネルギーが１または２の画素を起点とするシームが選択されることになる。
【０１３４】
以上の処理を比較すると、ダイナミックプログラミング法は、一旦積算エネルギーマップを求めた後、全ての起点となる画素に対して、全ての終点となる画素までのシームの積算エネルギーを比較した上で、シームを選択することとなる。このため、図１５の左下部で示されるように、グリーディ法よりも高い精度で、積算エネルギーが最小となるシームが選択される。しかしながら、一旦積算エネルギーマップを求めた後、全ての起点となる画素に対して、全ての終点となる画素までのシームの積算エネルギーを求めることとなるため、計算量が膨大なものとなる。一方、グリーディ法は、積算エネルギーマップを特に求める必要がなく、各画素について、いずれの選択経路とするかについては、一定の条件となるため、計算量を小さくすることが可能となる。しかしながら、図１５における右下部で示されるように、各画素毎にしか選択経路が決定されないため、真に積算エネルギーが最小となる経路からなるシームを探索することができない。
【０１３５】
しかしながら、本実施例においては、縮小画像に対して全画像探索処理において、精度の高いダイナミックプログラミング法を用いていることから、求められる縮小シームは比較的精度良く求めることが可能となる。また、縮小画像に対してダイナミックプログラミング法で全画像探索処理を実行しているため、入力画像に対してする処理よりも計算量を小さくすることが可能となる。さらに、入力画像のうち、縮小シームとして求められた範囲を起点とする画素のみに対してグリーディ法を用いた部分画像探索処理が実行されるため、軽い計算量でありながら、比較的精度良く求められた縮小シームの情報を用いて、部分シームを探索するため、部分シームの探索精度の低減を抑制しつつ、計算速度を向上させることが可能となる。
【０１３６】
さらに、計算速度を向上させたい場合、全画像探索処理において、グリーディ法を用いるようにしてもよい。すなわち、全画像探索処理において、グリーディ法を用いることで積算エネルギーマップを求めたり、全ての起点について、全ての終点までの積算エネルギーを比較した上でシームを探索する必要がなくなるので、計算速度をさらに向上させることが可能となる。
【０１３７】
また、以上においては、入力画像に対して、垂直方向に下方向にシームを探索する例について説明してきたが、同様の手法により水平方向にシームを探索することにより、水平方向の画素の削除、または挿入が可能となる。そして、これらを組み合わせて処理することにより、入力画像の水平方向、および垂直方向のそれぞれを縮小、または拡大させることが可能となる。
【０１３８】
例えば、図１６の左部で示されるように、２羽の水鳥が撮像されている入力画像に対して、従来のように水平方向、および垂直方向に対して、所定のスケーリングにより縮小すると、図１６の右上部で示されるように、画像の縮小率に合わせて、水鳥そのものも縮小される。これに対して、上述した処理を用いることにより、図１６の右下部で示されるように、画像は縮小されることとなるが、水鳥の大きさは画像全体の縮小率に対して小さなものとすることができる。結果として、画像のサイズは小さくなるが、被写体である水鳥の大きさの変化を小さくすることが可能となる。
【０１３９】
ところで、上述した一連の画像処理は、ハードウェアにより実行させることもできるが、ソフトウェアにより実行させることもできる。一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、記録媒体からインストールされる。
【０１４０】
図１７は、汎用のパーソナルコンピュータの構成例を示している。このパーソナルコンピュータは、CPU(Central Processing Unit)１００１を内蔵している。CPU１００１にはバス１００４を介して、入出力インタ-フェイス１００５が接続されている。バス１００４には、ROM(Read Only Memory)１００２およびRAM(Random Access Memory)１００３が接続されている。
【０１４１】
入出力インタ-フェイス１００５には、ユーザが操作コマンドを入力するキーボード、マウスなどの入力デバイスよりなる入力部１００６、処理操作画面や処理結果の画像を表示デバイスに出力する出力部１００７、プログラムや各種データを格納するハードディスクドライブなどよりなる記憶部１００８、LAN（Local Area Network）アダプタなどよりなり、インターネットに代表されるネットワークを介した通信処理を実行する通信部１００９が接続されている。また、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory)、DVD(Digital Versatile Disc)を含む）、光磁気ディスク（ＭＤ(Mini Disc)を含む）、もしくは半導体メモリなどのリムーバブルメディア１０１１に対してデータを読み書きするドライブ１０１０が接続されている。
【０１４２】
CPU１００１は、ROM１００２に記憶されているプログラム、または磁気ディスク、光ディスク、光磁気ディスク、もしくは半導体メモリ等のリムーバブルメディア１０１１から読み出されて記憶部１００８にインストールされ、記憶部１００８からRAM１００３にロードされたプログラムに従って各種の処理を実行する。RAM１００３にはまた、CPU１００１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１４３】
尚、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理は、もちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理を含むものである。
【０１４４】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【符号の説明】
【０１４５】
１ 画像処理装置， １１ 画像取得部， １２ エネルギーマップ生成部， １３ 入力画像エネルギーマップ記憶部， １４ 縮小画像エネルギーマップ記憶部， １５ 探索部， １６ 加工部， ２１ エネルギー算出部、 ２２ 縮小部， ３１ 全画像探索部， ３２ 部分画像探索部， ５１ 縮小画像エネルギーマップバッファ， ５２ 積算エネルギーマップ生成部， ５３ 積算エネルギーマップ記憶部， ５４ 最小シーム決定部， ５５ エネルギー最大値挿入部， ７１ 入力画像エネルギーマップバッファ， ７２ 隣接エネルギー比較部， ７３ 非隣接エネルギー比較部， ７４ 選択経路設定部， ７５ 選択経路記憶部， ７６ 部分シーム決定部， ７７ 部分シーム記憶部， ７８ 同時処理シーム本数判定部， ７９ ブロック内部分シーム本数判定部， ８０ 出力部， ８１ エネルギー最大値挿入部
【特許請求の範囲】
【請求項１】
入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、
前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、
前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、
前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、
前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、
前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段と
を含み、
前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
画像処理装置。
【請求項２】
前記縮小シーム探索手段により探索された縮小シームを構成する、前記縮小画像の全ての画素に対応する前記縮小画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記縮小画像エネルギーマップを更新する縮小画像エネルギーマップ更新手段をさらに含む
請求項１に記載の画像処理装置。
【請求項３】
前記縮小シーム探索手段は、グリーディ法、または、ダイナミックプログラミング法により、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する
請求項１に記載の画像処理装置。
【請求項４】
前記部分シーム探索手段は、グリーディ法により、前記縮小シーム探索手段により前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する
請求項１に記載の画像処理装置。
【請求項５】
入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、
前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、
前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、
前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、
前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、
前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段と
を含み、
前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置の画像処理方法であって、
前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、
前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、
前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、
前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、
前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、
前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップと
を含み、
前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
画像処理方法。
【請求項６】
入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、
前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、
前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、
前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、
前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、
前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段と
を含み、
前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置を制御するコンピュータに、
前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、
前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、
前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、
前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、
前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、
前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップと
を含む処理を実行させ、
前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
プログラム。
【請求項１】
入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、
前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、
前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、
前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、
前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、
前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段と
を含み、
前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
画像処理装置。
【請求項２】
前記縮小シーム探索手段により探索された縮小シームを構成する、前記縮小画像の全ての画素に対応する前記縮小画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記縮小画像エネルギーマップを更新する縮小画像エネルギーマップ更新手段をさらに含む
請求項１に記載の画像処理装置。
【請求項３】
前記縮小シーム探索手段は、グリーディ法、または、ダイナミックプログラミング法により、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する
請求項１に記載の画像処理装置。
【請求項４】
前記部分シーム探索手段は、グリーディ法により、前記縮小シーム探索手段により前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する
請求項１に記載の画像処理装置。
【請求項５】
入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、
前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、
前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、
前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、
前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、
前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段と
を含み、
前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置の画像処理方法であって、
前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、
前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、
前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、
前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、
前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、
前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップと
を含み、
前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
画像処理方法。
【請求項６】
入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成手段と、
前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成手段と、
前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索手段と、
前記縮小シーム探索手段により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索手段と、
前記部分シーム探索手段により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新手段と、
前記部分シーム探索手段により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大手段と
を含み、
前記部分シーム探索手段は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる画像処理装置を制御するコンピュータに、
前記入力画像エネルギーマップ生成手段における、前記入力画像より前記入力画像の隣接する画素間のエネルギーに基づいて、入力画像エネルギーマップを生成する入力画像エネルギーマップ生成ステップと、
前記縮小エネルギーマップ生成手段における、前記入力画像エネルギーマップを縮小することにより、前記入力画像における隣接する複数の画素からなる１ブロックを１画素とした縮小画像に対応する、縮小エネルギーマップを生成する縮小エネルギーマップ生成ステップと、
前記縮小シーム探索手段における、前記縮小エネルギーマップにおける縮小画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる経路の画素間を結ぶことにより構成される縮小シームを探索する縮小シーム探索ステップと、
前記部分シーム探索手段における、前記縮小シーム探索ステップの処理により探索された縮小シームの端部を構成する、前記入力画像エネルギーマップにおける入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路のうち、経由する画素のエネルギーの積算値が最小となる画素間を結ぶことにより構成される部分シームを探索する部分シーム探索ステップと、
前記入力画像エネルギーマップ更新手段における、前記部分シーム探索ステップの処理により探索された部分シームを構成する、前記入力画像の全ての画素に対応する前記入力画像エネルギーマップ上のエネルギーに、エネルギー最大値を挿入して置換し、前記入力画像エネルギーマップを更新する入力画像エネルギーマップ更新ステップと、
前記縮小拡大手段における、前記部分シーム探索ステップの処理により探索された前記部分シームを構成する画素を、前記入力画像より削除、または、同一若しくは近傍画素から補間した画素を挿入することで前記入力画像を縮小または拡大する縮小拡大ステップと
を含む処理を実行させ、
前記部分シーム探索ステップの処理は、前記入力画像の一方の端部の画素より、他方の端部の方向に隣接した画素を順次経由して、前記他方の端部の画素に到達するまでの複数の経路を探索するにあたり、隣接する画素の全てが前記入力画像エネルギーマップのエネルギー最大値であった場合、前記隣接する画素に、さらに隣接する所定数の画素のうち、最小エネルギーの画素を隣接する画素として設定し、前記経路を構成させる
プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１１−１７６７４９（Ｐ２０１１−１７６７４９Ａ）
【公開日】平成２３年９月８日（２０１１．９．８）
【国際特許分類】
【出願番号】特願２０１０−４０６９９（Ｐ２０１０−４０６９９）
【出願日】平成２２年２月２５日（２０１０．２．２５）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２３年９月８日（２０１１．９．８）
【国際特許分類】
【出願日】平成２２年２月２５日（２０１０．２．２５）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]