(57)【要約】【課題】撮影位置が異なり被写体の画像が歪んだ場合でも適切に画像の類似度を決定し，類似画像を検索することを可能とする。【解決手段】格子化手段１１が対象となる画像を格子化して第１の処理画像とし，検索対象画像を格子化して第２の処理画像とし，各列コスト算出手段１５が，第１の処理画像の第ｉ列の画像と第２の処理画像の第ｊ列の画像間でＤＰマッチングを行い，最短路に対応するＤＰパスに対応するミニマムコストｄ［ｉ，ｊ］を算出し，ＤＰコスト格子空間生成手段１６がｄ［ｉ，ｊ］をマトリックス位置（ｉ，ｊ）に割り当ててＤＰコスト格子空間を生成し，ＤＰパス・ミニマムコスト決定手段１７がＤＰコスト格子空間でのＤＰパスを求め，そのＤＰパスに対応する最終ミニマムコストを決定し，類似度決定手段１９が最終ミニマムコストをもとに対象となる画像と検索対象画像との類似度を決定する。【選択図】図１
2005327065.tif 000002
【特許請求の範囲】
【請求項１】
対象となる画像の類似画像を検索する類似画像検索装置であって，
前記対象となる画像と，検索対象画像群から選択された検索対象画像とを，それぞれａ×ｂ画素（ａ≧１，ｂ≧１）の画像要素に分割し格子化する格子化手段と，
前記格子化された対象となる画像および検索対象画像における縦または横の格子列方向に並ぶ画像要素列間に対してＤＰマッチングを行うことで，その格子列方向に並ぶ２つの画像要素列間のＤＰパスに対応するミニマムコストを算出するコスト算出手段と，
前記ミニマムコストを，その算出元となった前記２つの画像要素列の位置によって定まるマトリックス位置に割り当てることによりＤＰコスト格子空間を生成するＤＰコスト格子空間生成手段と，
前記ＤＰコスト格子空間におけるＤＰパスおよびそれに対応するミニマムコストを最終ミニマムコストとして算出するＤＰパス・ミニマムコスト決定手段と，
前記最終ミニマムコストに基づいて前記対象となる画像と前記検索対象画像との類似度を決定する類似度決定手段とを備える
ことを特徴とする類似画像検索装置。
【請求項２】
対象となる画像の類似画像をコンピュータによって検索する類似画像検索方法であって，
前記対象となる画像と，検索対象画像群から選択された検索対象画像とを，それぞれａ×ｂ画素（ａ≧１，ｂ≧１）の画像要素に分割し格子化する格子化ステップと，
前記格子化された対象となる画像および検索対象画像における縦または横の格子列方向に並ぶ画像要素列間に対してＤＰマッチングを行うことで，その格子列方向に並ぶ２つの画像要素列間のＤＰパスに対応するミニマムコストを算出するコスト算出ステップと，
前記ミニマムコストを，その算出元となった前記２つの画像要素列の位置によって定まるマトリックス位置に割り当てることによりＤＰコスト格子空間を生成するＤＰコスト格子空間生成ステップと，
前記ＤＰコスト格子空間におけるＤＰパスおよびそれに対応するミニマムコストを最終ミニマムコストとして算出するＤＰパス・ミニマムコスト決定ステップと，
前記最終ミニマムコストに基づいて前記対象となる画像と前記検索対象画像との類似度を決定する類似度決定ステップとを有する
ことを特徴とする類似画像検索方法。
【請求項３】
対象となる画像の類似画像を検索する処理をコンピュータに実行させるための類似画像検索プログラムであって，
前記コンピュータを，
前記対象となる画像と，検索対象画像群から選択された検索対象画像とを，それぞれａ×ｂ画素（ａ≧１，ｂ≧１）の画像要素に分割し格子化する格子化手段と，
前記格子化された対象となる画像および検索対象画像における縦または横の格子列方向に並ぶ画像要素列間に対してＤＰマッチングを行うことで，その格子列方向に並ぶ２つの画像要素列間のＤＰパスに対応するミニマムコストを算出するコスト算出手段と，
前記ミニマムコストを，その算出元となった前記２つの画像要素列の位置によって定まるマトリックス位置に割り当てることによりＤＰコスト格子空間を生成するＤＰコスト格子空間生成手段と，
前記ＤＰコスト格子空間におけるＤＰパスおよびそれに対応するミニマムコストを最終ミニマムコストとして算出するＤＰパス・ミニマムコスト決定手段と，
前記最終ミニマムコストに基づいて前記対象となる画像と前記検索対象画像との類似度を決定する類似度決定手段として
機能させるための類似画像検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，類似画像検索技術に関し，特に，動的計画法（ＤＰ:Dynamic Programming）によるマッチングを多段に適用することにより類似画像を判定・検索する類似画像検索装置，類似画像検索方法および類似画像検索プログラムに関する。
【背景技術】
【０００２】
従来は，例えば，下記の特許文献１に記載された技術のように，画像内の領域の特徴ベクトルを抽出し，画像検索を行なっていた。
【特許文献１】特開２０００−０８２０７５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら，従来の方法では，同じ被写体であっても，撮影位置が異なり被写体の画像が歪んだ場合などには，抽出される特徴ベクトルが異なり，画像類似度が異なるものと判定されていた。
【０００４】
本発明は，上記従来技術の問題点を解決し，撮影位置が異なり被写体の画像に歪みが生じたような場合でも，適切に画像の類似度を決定し，類似画像を検索することが可能な新しい類似画像検索技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明では，ＤＰマッチングを多段に用い，縦方向および横方向のずれや画像の大小もしくは歪みを考慮に入れ，画像の類似度を判定・検索する。
【０００６】
すなわち，上記課題を解決するため，本発明は，対象となる画像の類似画像を検索する類似画像検索装置であって，前記対象となる画像と，検索対象画像群から選択された検索対象画像とを，それぞれａ×ｂ画素（ａ≧１，ｂ≧１）の画像要素に分割し格子化する格子化手段と，前記格子化された対象となる画像および検索対象画像における縦または横の格子列方向に並ぶ画像要素列間に対してＤＰマッチングを行うことで，その格子列方向に並ぶ２つの画像要素列間のＤＰパスに対応するミニマムコストを算出するコスト算出手段と，前記ミニマムコストを，その算出元となった前記２つの画像要素列の位置によって定まるマトリックス位置に割り当てることによりＤＰコスト格子空間を生成するＤＰコスト格子空間生成手段と，前記ＤＰコスト格子空間におけるＤＰパスおよびそれに対応するミニマムコストを最終ミニマムコストとして算出するＤＰパス・ミニマムコスト決定手段と，前記最終ミニマムコストに基づいて前記対象となる画像と前記検索対象画像との類似度を決定する類似度決定手段とを備えることを特徴とする。
【０００７】
また，本発明は，対象となる画像の類似画像をコンピュータによって検索する類似画像検索方法であって，前記対象となる画像と，検索対象画像群から選択された検索対象画像とを，それぞれａ×ｂ画素（ａ≧１，ｂ≧１）の画像要素に分割し格子化する格子化ステップと，前記格子化された対象となる画像および検索対象画像における縦または横の格子列方向に並ぶ画像要素列間に対してＤＰマッチングを行うことで，その格子列方向に並ぶ２つの画像要素列間のＤＰパスに対応するミニマムコストを算出するコスト算出ステップと，前記ミニマムコストを，その算出元となった前記２つの画像要素列の位置によって定まるマトリックス位置に割り当てることによりＤＰコスト格子空間を生成するＤＰコスト格子空間生成ステップと，前記ＤＰコスト格子空間におけるＤＰパスおよびそれに対応するミニマムコストを最終ミニマムコストとして算出するＤＰパス・ミニマムコスト決定ステップと，前記最終ミニマムコストに基づいて前記対象となる画像と前記検索対象画像との類似度を決定する類似度決定ステップとを有することを特徴とする。
【０００８】
また，本発明に係る類似画像検索プログラムは，コンピュータを，上記類似画像検索装置が持つ各手段として機能させるためのプログラムである。このプログラムは，コンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【発明の効果】
【０００９】
本発明では，ＤＰマッチングを多段に用い，縦方向および横方向のずれや画像の大小もしくは歪みを考慮にいれ，画像の類似度を判定・検索する。従って，本発明によれば，撮影位置が異なり被写体の画像が歪んだような場合でも，適切に画像の類似度を決定し，類似画像を検索することができる。
【発明を実施するための最良の形態】
【００１０】
以下，実施の形態に従って本発明を詳細に説明する。図１は，本発明の類似画像検索装置の構成の一例を示す図である。図１において，１はＣＰＵ，メモリおよび類似画像検索の処理をＣＰＵに実行させるためのソフトウェアプログラムなどからなる類似画像検索装置である。２は画像入力装置であり，対象となる画像（検索キーとなる画像）を入力するもの，３は検索対象画像群を記憶する検索対象画像記憶装置である。
【００１１】
類似画像検索装置１は，対象となる画像と検索対象画像記憶装置３に記憶されている検索対象画像群から選択された検索対象画像とを格子化する格子化手段１１と，対象となる画像を格子化した結果を記憶する第１の処理画像メモリ１２と，検索対象画像を格子化した結果を記憶する第２の処理画像メモリ１３と，格子化した対象となる画像と検索対象画像の画像要素列を選択する列画像選択手段１４と，選択した２つの画像要素列に対してＤＰマッチングを行い各列間のミニマムコストを算出する各列コスト算出手段１５と，算出したミニマムコストを各列の位置に対応するマトリックス位置に割り当てることによりＤＰコスト格子空間を生成するＤＰコスト格子空間生成手段１６と，ＤＰコスト格子空間におけるＤＰパスおよびそれに対するミニマムコスト（最終ミニマムコスト）を決定するＤＰパス・ミニマムコスト決定手段１７と，最終ミニマムコストを記憶する最終ミニマムコスト記憶手段１８と，最終ミニマムコスト記憶手段１８に格納された最終ミニマムコストに基づいて，対象となる画像と検索対象画像との類似度を決定する類似度決定手段１９とから構成される。
【００１２】
格子化手段１１は，画像入力装置２から入力した対象となる画像をａ×ｂ画素（ａ≧１，ｂ≧１）の画像要素に分割し格子化することで第１の処理画像を生成し，第１の処理画像メモリ１２に書き込む。なお，対象となる画像は，画像入力装置２から入力されたものではなく，あらかじめ記憶装置に格納されていたものでもよい。また，対象となる画像がアナログ画像の場合には，格子化する前にデジタル化する。
【００１３】
また，格子化手段１１は，検索対象画像記憶装置３に記憶される検索対象画像群から順序選択した検索対象画像を，同様にａ×ｂ画素（ａ≧１，ｂ≧１）の画像要素に分割し格子化することで第２の処理画像を生成し，第２の処理画像メモリ１３に書き込む。検索対象画像は，ネットワークを介して他の装置から読み込まれるような画像でもよい。
【００１４】
この格子化手段１１の処理によって，第１の処理画像メモリ１２には，例えば図２に示すように，（ｎ＋１）×（ｍ＋１）の格子に分割された第１の処理画像が記憶され，第２の処理画像メモリ１３には，例えば図３に示すように，（ｑ＋１）×（ｐ＋１）の格子に分割された第２の処理画像が記憶されることになる。
【００１５】
列画像選択手段１４は，第１の処理画像メモリ１２に記憶される第１の処理画像の持つ第ｉ列（ｉ＝０〜ｍ）の列画像（第ｉ列に並ぶ画像要素群）を選択して読み出すとともに，第２の処理画像メモリ１３から，第２の処理画像の持つ第ｊ列（ｊ＝０〜ｐ）の列画像（第ｊ列に並ぶ画像要素群）を選択して読み出す。
【００１６】
各列コスト算出手段１５では，図４に示すように，ＤＰマッチング手段１５１が，列画像選択手段１４の出力する第１の処理画像の持つ第ｉ列の列画像と，列画像選択手段１４の出力する第２の処理画像の持つ第ｊ列の列画像との間でＤＰマッチングを行うことで，最短路のＤＰパスを求めるとともに，ミニマムコスト算出手段１５２が，そのＤＰパスに対応するミニマムコストｄ［ｉ，ｊ］を算出する。
【００１７】
図５は，第１の処理画像の第ｉ列の画像を構成する画像要素と，第２の処理画像の第ｊ列の画像を構成する画像要素との類似度を求めるための，ＤＰマッチングによるミニマムコストｄ［ｉ，ｊ］の算出を説明する図である。
【００１８】
図５に示すように，第１の処理画像の持つ第ｉ列の列画像を構成する画像要素［０，１］，…，［ｎ，ｉ］と，第２の処理画像の持つ第ｊ列の列画像を構成する画像要素［０，ｊ］，…，［ｑ，ｊ］との間でＤＰによるマッチングを行う。ＤＰマッチングにおける距離の計算には，例えばａ×ｂ画素の画像要素における対応するユークリッド距離やユークリッド距離の二乗和（差分値の二乗和）等を用いる。始状態から終状態までの距離が最小となる最短路を求め，この最短路に対応する，太線で示されるＤＰパスを求める。そして，求めたＤＰパスに対応するミニマムコストｄ［ｉ，ｊ］を算出する。
【００１９】
この処理をｉが０からｍまで，ｊが０からｐまで繰り返す。なお，ｉとｊのすべての組み合わせについて行うのではなく，ｉとｊの組み合わせに制限を設けて，最短路になる可能性のある対角方向の格子点の部分だけを選択的に計算して，他の部分の計算を省略することにより，計算処理を高速化するようにしてもよい。
【００２０】
ＤＰコスト格子空間生成手段１６は，各列コスト算出手段１５の算出したミニマムコストｄ［ｉ，ｊ］をマトリックス位置（ｉ，ｊ）に割り当てることで，ＤＰコスト格子空間を生成する。
【００２１】
図６は，このようにしてＤＰコスト格子空間生成手段１６によって生成したＤＰコスト格子空間を示している。このＤＰコスト格子空間では，マトリックス位置（ｉ，ｊ）に，各列コスト算出手段１５の算出したミニマムコストｄ［ｉ，ｊ］が割り当てられている。ＤＰコスト格子空間は，図６に示すように（ｍ＋１）×（ｐ＋１）の大きさを持つ。
【００２２】
ＤＰパス・ミニマムコスト決定手段１７は，ＤＰコスト格子空間についてのＤＰマッチングを行う。つまり，これはＤＰマッチングにおけるＤＰ漸化式のベクトル間距離の項にＤＰコスト格子空間のマトリックス位置（ｉ，ｊ）に代入されたミニマムコストｄ［ｉ，ｊ］を用いてＤＰパス・ミニマムコストを求めることを意味する。
【００２３】
このようにして，ＤＰパス・ミニマムコスト決定手段１７の処理によって，例えば図７に示すようなＤＰコスト格子空間におけるＤＰパスが求められることになる。ＤＰパス・ミニマムコスト決定手段１７は，決定されたＤＰパスに対応するコスト（最終ミニマムコスト）を決定し，最終ミニマムコスト記憶手段１８に格納する。
【００２４】
類似度決定手段１９は，最終ミニマムコスト記憶手段１８内に格納された最終ミニマムコストをもとに，対象となる画像と検索対象画像との類似度を決定する。
【００２５】
図８を用いて，本発明の類似画像検索方法の処理フローの一例を説明する。まず，類似画像検索装置１の格子化手段１１は，対象となる画像を画像入力装置２から入力し，必要に応じてデジタル化した後，ａ×ｂ画素のブロックに分割して格子化する（ステップＳ１）。この格子化処理によって，例えば図２に示すような，（ｎ＋１）×（ｍ＋１）の格子に分割された第１の処理画像が得られる（ステップＳ１）。
【００２６】
また，格子化手段１１は，検索対象画像記憶装置３に記憶されている検索対象画像群から検索対象画像を選択し，その選択した検索対象画像を格子化する（ステップＳ２）。この格子化処理によって，図３に示すような，（ｑ＋１）×（ｐ＋１）の格子に分割された第２の処理画像が得られる。
【００２７】
第１の処理画像の［０］列〜［ｍ］列と第２の処理画像の［０］列〜［ｐ］列のそれぞれにＤＰマッチングを行い，ＤＰパス（最短路）を求め，そのＤＰパスに対応するミニマムコストを算出する（ステップＳ３）。
【００２８】
算出したＤＰパスに対応するミニマムコストを，ＤＰコスト格子空間の該当する格子点にそれぞれ代入することにより，図６のようなＤＰコスト格子空間を生成する。（ステップＳ４）。上記代入したそれぞれのミニマムコストを用いて，ＤＰコスト格子空間でのＤＰパスを求め，そのＤＰパスに対応するコスト（最終ミニマムコスト）を決定する（ステップＳ５）。
【００２９】
決定した最終ミニマムコストを最終ミニマムコスト記憶手段１８に格納し，格納された最終ミニマムコストをもとに，対象となる画像と検索対象画像との類似度を決定する（ステップＳ６）。最終ミニマムコストが小さいほど，類似度が大きいものとする。以上の処理をすべての検索対象画像について繰り返し，未処理の検索対象画像がなくなったならば（ステップＳ７），処理を終了する。
【００３０】
対象となる画像と各検索対象画像との類似度を決定した結果，最も類似度が大きい検索対象画像，もしくは類似度が上位何個かの検索対象画像，もしくは類似度が所定の閾値以上の検索対象画像が検索結果として出力される。
【００３１】
なお，上記ステップＳ２では，第１の処理画像の［０］列〜［ｍ］列と第２の処理画像の［０］列〜［ｐ］列のそれぞれにＤＰマッチングを行ったが，本発明では，ＤＰマッチングを行う画像は，横方向にその画像要素が並ぶ行画像でもよく，例えば，第１の処理画像の［０］行〜［ｎ］行と第２の処理画像の［０］行〜［ｑ］行のそれぞれにＤＰマッチングを行ってもよい。
【００３２】
以上のようにして，本発明では，列画像または行画像についてのＤＰマッチングを行った後，そのミニマムコストによって生成されるＤＰコスト格子空間によるＤＰマッチングを行い，縦方向および横方向のずれや画像の大小もしくは歪みを考慮した画像の類似度の決定および検索を実現する。
【図面の簡単な説明】
【００３３】
【図１】本発明の類似画像検索装置の構成の一例を示す図である。
【図２】第１の処理画像を示す図である。
【図３】第２の処理画像を示す図である。
【図４】ＤＰマッチングを通じたミニマムコストｄ［ｉ，ｊ］の算出を説明する図である。
【図５】列画像間のＤＰマッチングによるミニマムコストｄ［ｉ，ｊ］の算出を説明する図である。
【図６】ＤＰコスト格子空間を示す図である。
【図７】ＤＰコスト格子空間におけるＤＰパスを示す図である。
【図８】本発明の類似画像検索方法の処理フローの一例を示す図である。
【符号の説明】
【００３４】
１    類似画像検索装置
２    画像入力装置
３    検索対象画像記憶装置
１１  格子化手段
１２  第１の処理画像メモリ
１３  第２の処理画像メモリ
１４  列画像選択手段
１５  各列コスト算出手段
１６  ＤＰコスト格子空間生成手段
１７  ＤＰパス・ミニマムコスト決定手段
１８  最終ミニマムコスト記憶手段
１９  類似度決定手段
１５１  ＤＰマッチング手段
１５２  ミニマムコスト算出手段
【図１】
2005327065.tif 000003
【図２】
2005327065.tif 000004
【図３】
2005327065.tif 000005
【図４】
2005327065.tif 000006
【図５】
2005327065.tif 000007
【図６】
2005327065.tif 000008
【図７】
2005327065.tif 000009
【図８】
2005327065.tif 000010