TOP > 国内特許検索 > 類似画像検索装置、方法およびプログラム > 明細書

明細書 :類似画像検索装置、方法およびプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4134024号 (P4134024)
公開番号 特開2006-185364 (P2006-185364A)
登録日 平成20年6月6日(2008.6.6)
発行日 平成20年8月13日(2008.8.13)
公開日 平成18年7月13日(2006.7.13)
発明の名称または考案の名称 類似画像検索装置、方法およびプログラム
国際特許分類 G06F  17/30        (2006.01)
G06T   1/00        (2006.01)
G06T   7/00        (2006.01)
FI G06F 17/30 350C
G06F 17/30 170B
G06T 1/00 200E
G06T 7/00 300F
請求項の数または発明の数 23
全頁数 17
出願番号 特願2004-380878 (P2004-380878)
出願日 平成16年12月28日(2004.12.28)
審査請求日 平成16年12月28日(2004.12.28)
特許権者または実用新案権者 【識別番号】503360115
【氏名又は名称】独立行政法人科学技術振興機構
発明者または考案者 【氏名】寅市 和男
【氏名】クァン・ポール・ウィン・ヒン
個別代理人の代理人 【識別番号】100103171、【弁理士】、【氏名又は名称】雨貝 正彦
審査官 【審査官】紀田 馨
参考文献・文献 特許第2646475(JP,B2)
長嶋 秀世,自己相関関数のグラフの形を利用した商標図形の分類,電気学会論文誌C,日本,(社)電気学会,2003年 9月 1日,第123巻,第9号,第1547-1554頁
解 秋生,スプライン補間を用いたパターンの回転変換に不変なパターン認識系の一構成,電子情報通信学会論文誌,日本,社団法人電子情報通信学会,1992年 2月25日,第J75-D-II巻,第2号,第324-334頁
調査した分野 G06F 17/30
G06T 1/00
G06T 7/00
特許請求の範囲 【請求項1】
被検索対象画像を取り込む画像取込手段と、
前記画像取込手段によって取り込まれた前記被検索対象画像の自己相関波形を抽出する自己相関波形抽出手段と、
前記自己相関波形抽出手段によって抽出された前記自己相関波形の傾向が変化する接合点を抽出する接合点抽出手段と、
前記接合点によって分割される前記自己相関波形の各区分領域のそれぞれを関数で近似する関数近似手段と、
前記関数近似手段による近似処理に関連する特徴情報に基づいて、複数の比較対象画像の中から類似した画像を検索する画像検索手段と、
を備え、前記自己相関波形抽出手段は、前記被検索対象画像が内接する面積最小の矩形と前記被検索対象画像の重心位置を算出し、前記矩形の長辺と短辺の比が基準値以上であるときに前記長辺に沿った向きに自己相関波形を抽出し、前記矩形の長辺と短辺の比が基準値より小さいときには前記重心位置を回転中心とした所定の回転方向に自己相関波形を抽出することを特徴とする類似画像検索装置。
【請求項2】
請求項1において、
前記比較対象画像に対応する自己相関波形の各区分領域を関数近似する処理に関連して作成された特徴情報が、前記複数の比較対象画像毎に格納された特徴情報格納手段をさらに備え、
前記画像検索手段は、前記被検索対象画像に対応する特徴情報と、前記特徴情報格納手段に格納されている前記複数の比較対象画像に対応する特徴情報とを比較することにより、前記被検索対象画像に類似する前記比較対象画像を抽出することを特徴とする類似画像検索装置。
【請求項3】
請求項2において、
前記画像取込手段、前記自己相関波形抽出手段、前記接合点抽出手段、前記関数近似手段を用いて前記比較対象画像に対応する特徴情報が取得されたときに、この特徴情報を前記特徴情報格納手段に格納する特徴情報格納処理手段をさらに備えることを特徴とする類似画像検索装置。
【請求項4】
請求項1~3のいずれかにおいて、
前記画像取込手段は、光学的に前記被検索対象画像の濃淡情報あるいは色情報を読み取る光学読取装置であることを特徴とする類似画像検索装置。
【請求項5】
請求項1~3のいずれかにおいて、
前記画像取込手段は、前記被検索対象画像を構成する複数の画素のそれぞれに対応する濃淡情報あるいは色情報からなる画像データが格納された記録媒体から画像データを読み取るデータ読取装置であることを特徴とする類似画像検索装置。
【請求項6】
請求項1~5のいずれかにおいて、
前記特徴情報には、前記自己相関波形を構成する複数の前記区分領域に対応する複数の関数の順番が含まれており、
前記画像検索手段は、前記複数の関数の順番に基づいて前記複数の比較対象画像の中から前記被検索対象画像に類似するものを検索することを特徴とする類似画像検索装置。
【請求項7】
請求項1~5のいずれかにおいて、
前記特徴情報には、前記自己相関波形を構成する複数の前記区分領域に対応する複数の関数の各区間長の並びが含まれており、
前記画像検索手段は、前記区間長の並びに基づいて前記複数の比較対象画像の中から前記被検索対象画像に類似するものを検索することを特徴とする類似画像検索装置。
【請求項8】
請求項1~5のいずれかにおいて、
前記画像検索手段は、前記被検索対象画像と前記比較対象画像のそれぞれの自己相関波形を構成する複数の前記区分領域に対応する関数の相関度を計算し、相関度が大きい順に、前記被検索対象画像に類似する前記比較対象画像を検索することを特徴とする類似画像検索装置。
【請求項9】
請求項1~8のいずれかにおいて、
前記画像検索手段は、前記被検索対象画像に対応する前記自己相関波形に含まれる前記区分領域の総数に着目して、検索対象候補として所定数の前記比較対象画像を選択した後、前記特徴情報に基づいて前記被検索対象画像に類似する前記比較対象画像を検索することを特徴とする類似画像検索装置。
【請求項10】
被検索対象画像を取り込む画像取込ステップと、
前記画像取込ステップにおいて取り込まれた前記被検索対象画像の自己相関波形を抽出する自己相関波形抽出ステップと、
前記自己相関波形抽出ステップにおいて抽出された前記自己相関波形の傾向が変化する接合点を抽出する接合点抽出ステップと、
前記接合点によって分割される前記自己相関波形の各区分領域のそれぞれを関数で近似する関数近似ステップと、
前記関数近似ステップにおける近似処理に関連する特徴情報に基づいて、複数の比較対象画像の中から類似した画像を検索する画像検索ステップと、
を備え、前記自己相関波形抽出ステップは、前記被検索対象画像が内接する面積最小の矩形と前記被検索対象画像の重心位置を算出し、前記矩形の長辺と短辺の比が基準値以上であるときに前記長辺に沿った向きに自己相関波形を抽出し、前記矩形の長辺と短辺の比が基準値より小さいときには前記重心位置を回転中心とした所定の回転方向に自己相関波形を抽出することを特徴とする類似画像検索方法。
【請求項11】
請求項10において、
前記比較対象画像に対応する自己相関波形の各区分領域を関数近似する処理に関連して作成された特徴情報が、前記複数の比較対象画像毎に格納された特徴情報格納手段をさらに備え、
前記画像検索ステップは、前記被検索対象画像に対応する特徴情報と、前記特徴情報格納手段に格納されている前記複数の比較対象画像に対応する特徴情報とを比較することにより、前記被検索対象画像に類似する前記比較対象画像を抽出することを特徴とする類似
画像検索方法。
【請求項12】
請求項11において、
前記画像取込ステップ、前記自己相関波形抽出ステップ、前記接合点抽出ステップ、前記関数近似ステップを用いて前記比較対象画像に対応する特徴情報が取得されたときに、この特徴情報を前記特徴情報格納手段に格納する特徴情報格納処理ステップをさらに備えることを特徴とする類似画像検索方法。
【請求項13】
請求項10~12のいずれかにおいて、
前記画像取込ステップは、光学的に前記被検索対象画像の濃淡情報あるいは色情報を読み取る光学読取装置を用いて行われることを特徴とする類似画像検索方法。
【請求項14】
請求項10~12のいずれかにおいて、
前記画像取込ステップは、前記被検索対象画像を構成する複数の画素のそれぞれに対応する濃淡情報あるいは色情報からなる画像データが格納された記録媒体から画像データを読み取るデータ読取装置を用いて行われることを特徴とする類似画像検索方法。
【請求項15】
請求項10~14のいずれかにおいて、
前記特徴情報には、前記自己相関波形を構成する複数の前記区分領域に対応する複数の関数の順番が含まれており、
前記画像検索ステップは、前記複数の関数の順番に基づいて前記複数の比較対象画像の中から前記被検索対象画像に類似するものを検索することを特徴とする類似画像検索方法。
【請求項16】
請求項10~14のいずれかにおいて、
前記特徴情報には、前記自己相関波形を構成する複数の前記区分領域に対応する複数の関数の各区間長の並びが含まれており、
前記画像検索ステップは、前記区間長の並びに基づいて前記複数の比較対象画像の中から前記被検索対象画像に類似するものを検索することを特徴とする類似画像検索方法。
【請求項17】
請求項10~14のいずれかにおいて、
前記画像検索ステップは、前記被検索対象画像と前記比較対象画像のそれぞれの自己相関波形を構成する複数の前記区分領域に対応する関数の相関度を計算し、相関度が大きい順に、前記被検索対象画像に類似する前記比較対象画像を検索することを特徴とする類似画像検索方法。
【請求項18】
請求項10~17のいずれかにおいて、
前記画像検索ステップは、前記被検索対象画像に対応する前記自己相関波形に含まれる前記区分領域の総数に着目して、検索対象候補として所定数の前記比較対象画像を選択した後、前記特徴情報に基づいて前記被検索対象画像に類似する前記比較対象画像を検索することを特徴とする類似画像検索方法。
【請求項19】
コンピュータを、画像取込手段によって取り込まれた被検索対象画像の自己相関波形を抽出する自己相関波形抽出手段と、
前記自己相関波形抽出手段によって抽出された前記自己相関波形の傾向が変化する接合点を抽出する接合点抽出手段と、
前記接合点によって分割される前記自己相関波形の各区分領域のそれぞれを関数で近似する関数近似手段と、
前記関数近似手段による近似処理に関連する特徴情報に基づいて、複数の比較対象画像の中から類似した画像を検索する画像検索手段と、
して機能させる類似画像検索プログラムであって、
前記自己相関波形抽出手段は、前記被検索対象画像が内接する面積最小の矩形と前記被検索対象画像の重心位置を算出し、前記矩形の長辺と短辺の比が基準値以上であるときに前記長辺に沿った向きに自己相関波形を抽出し、前記矩形の長辺と短辺の比が基準値より小さいときには前記重心位置を回転中心とした所定の回転方向に自己相関波形を抽出する類似画像検索プログラム。
【請求項20】
請求項19において、
前記比較対象画像に対応する自己相関波形の各区分領域を関数近似する処理に関連して作成された特徴情報が、前記複数の比較対象画像毎に特徴情報格納手段に格納されており、
前記画像検索手段は、前記被検索対象画像に対応する特徴情報と、前記特徴情報格納手段に格納されている前記複数の比較対象画像に対応する特徴情報とを比較することにより、前記被検索対象画像に類似する前記比較対象画像を抽出することを特徴とする類似画像検索プログラム。
【請求項21】
請求項20において、
コンピュータを、さらに、前記画像取込手段、前記自己相関波形抽出手段、前記接合点抽出手段、前記関数近似手段を用いて前記比較対象画像に対応する特徴情報が取得されたときに、この特徴情報を前記特徴情報格納手段に格納する特徴情報格納処理手段として機能させる類似画像検索プログラム。
【請求項22】
請求項19~21のいずれかにおいて、
前記画像検索手段は、前記被検索対象画像と前記比較対象画像のそれぞれの自己相関波形を構成する複数の前記区分領域に対応する関数の相関度を計算し、相関度が大きい順に、前記被検索対象画像に類似する前記比較対象画像を検索することを特徴とする類似画像検索プログラム。
【請求項23】
請求項19~21のいずれかにおいて、
前記画像検索手段は、前記被検索対象画像に対応する前記自己相関波形に含まれる前記区分領域の総数に着目して、検索対象候補として所定数の前記比較対象画像を選択した後、前記特徴情報に基づいて前記被検索対象画像に類似する前記比較対象画像を検索することを特徴とする類似画像検索プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、検索対象の画像を登録された複数の画像と比較して類似する画像を検索する類似画像検索装置、方法およびプログラムに関する。特に、本発明は、機械図面、電気配線図、電子回路図、半導体の配線パターン、ロゴマーク、商標、家紋、写真、絵画、映像など、多くの類似した画像が含まれるファイルや全体図の中から、所望の画像を検索したり、画像が含まれる箇所を特定したり、部分図に類似あるいは一致する箇所を有する全体図を取り出したりする処理などに有効な類似画像検索装置、方法およびプログラムに関する。
【背景技術】
【0002】
近年、マルチメディア技術の進展により、パーソナルコンピュータやマイクロコンピュータ、専用画像処理装置等を含む計算機を用いて画像を処理する要求が高まっており、そのためのソフトウェア技術の進展も著しい。一般に、計算機では画像は画素毎のデジタルデータとして扱われるが、大量のデータを処理する必要から、画像処理の速度は計算機の高速演算処理能力に依存するところが大きい。計算機上で扱われる画像処理技術として多くの提案がなされているが、この中では画像の検索技術が重要課題の一つにあげられる。
【0003】
画像の検索とは、あらかじめ記憶されている大量の画像の中から、検索対象となっている所望の画像を抽出することである。従来から行われている画像検索の代表的なものとしては、検索対象画像の自己相関関数を利用する検索方法が知られている(例えば、非特許文献1参照。)。この検索方法では、検索対象画像から求めた自己相関関数を3つの区間に分け、それぞれの区間を指数関数、正弦関数、3次多項式で表した類似関数を求め、これらの類似関数を表すパラメータを用いて検索対象画像に類似する登録画像を抽出している。

【非特許文献1】長嶋秀世、外2名,「自己相関関数のグラフの形を利用した商標図形の分類」,電気学会論文誌C,電気学会,平成15年8月21日,第123巻,第9号,p1547-1554
【発明の開示】
【発明が解決しようとする課題】
【0004】
ところで、上述した非特許文献1の検索方法では、自己相関関数に含まれる3つの区間のそれぞれを異なる種類の類似関数で近似しているが、自己相関関数のほとんどを占める中央の区間を単一の正弦関数で近似しているため、自己相関関数の微細な特徴が検索に反映されず、検索対象画像の内容によっては検索精度が低下するという問題があった。
【0005】
本発明は、このような点に鑑みて創作されたものであり、その目的は、検索精度を上げることができる類似画像検索装置、方法およびプログラムを提供することにある。
【課題を解決するための手段】
【0006】
上述した課題を解決するために、本発明の類似画像検索装置は、被検索対象画像を取り込む画像取込手段と、画像取込手段によって取り込まれた被検索対象画像の自己相関波形を抽出する自己相関波形抽出手段と、自己相関波形抽出手段によって抽出された自己相関波形の傾向が変化する接合点を抽出する接合点抽出手段と、接合点によって分割される自己相関波形の各区分領域のそれぞれを関数で近似する関数近似手段と、関数近似手段による近似処理に関連する特徴情報に基づいて、複数の比較対象画像の中から類似した画像を検索する画像検索手段とを備えている。
【0007】
また、本発明の類似画像検索方法は、被検索対象画像を取り込む画像取込ステップと、画像取込ステップにおいて取り込まれた被検索対象画像の自己相関波形を抽出する自己相関波形抽出ステップと、自己相関波形抽出ステップにおいて抽出された自己相関波形の傾向が変化する接合点を抽出する接合点抽出ステップと、接合点によって分割される自己相関波形の各区分領域のそれぞれを関数で近似する関数近似ステップと、関数近似ステップにおける近似処理に関連する特徴情報に基づいて、複数の比較対象画像の中から類似した画像を検索する画像検索ステップとを備えている。
【0008】
また、本発明の類似画像検索プログラムは、コンピュータを、画像取込手段によって取り込まれた被検索対象画像の自己相関波形を抽出する自己相関波形抽出手段と、自己相関波形抽出手段によって抽出された自己相関波形の傾向が変化する接合点を抽出する接合点抽出手段と、接合点によって分割される自己相関波形の各区分領域のそれぞれを関数で近似する関数近似手段と、関数近似手段による近似処理に関連する特徴情報に基づいて、複数の比較対象画像の中から類似した画像を検索する画像検索手段として機能させる。
【0009】
自己相関波形に含まれる各接合点で分割される各区分領域のそれぞれを関数化処理することにより、自己相関波形の微細な特徴を含む全体を正確に関数化近似することができ、この近似処理において抽出された特徴情報を用いることにより、類似画像を検索する際の検索精度を向上させることが可能になる。
【0010】
また、上述した比較対象画像に対応する自己相関波形の各区分領域を関数近似する処理に関連して作成された特徴情報が、複数の比較対象画像毎に格納された特徴情報格納手段をさらに備え、画像検索手段は、被検索対象画像に対応する特徴情報と、特徴情報格納手段に格納されている複数の比較対象画像に対応する特徴情報とを比較することにより、被検索対象画像に類似する比較対象画像を抽出することが望ましい。あるいは、上述した比較対象画像に対応する自己相関波形の各区分領域を関数近似する処理に関連して作成された特徴情報が、複数の比較対象画像毎に格納された特徴情報格納手段をさらに備え、画像検索ステップは、被検索対象画像に対応する特徴情報と、特徴情報格納手段に格納されている複数の比較対象画像に対応する特徴情報とを比較することにより、被検索対象画像に類似する比較対象画像を抽出することが望ましい。これにより、あらかじめ格納された特徴情報を順番に読み出して、取り込まれた被検索対象画像の特徴情報と比較することにより、容易に類似画像の検索を行うことができ、比較対象となる画像が多い場合であっても操作が煩雑にならず、操作の簡略化が可能になる。
また、上述した画像取込手段、自己相関波形抽出手段、接合点抽出手段、関数近似手段を用いて比較対象画像に対応する特徴情報が取得されたときに、この特徴情報を特徴情報格納手段に格納する特徴情報格納処理手段をさらに備えることが望ましい。あるいは、上述した画像取込ステップ、自己相関波形抽出ステップ、接合点抽出ステップ、関数近似ステップを用いて比較対象画像に対応する特徴情報が取得されたときに、この特徴情報を特徴情報格納手段に格納する特徴情報格納処理ステップをさらに備えることが望ましい。これにより、比較対象となる画像を適宜追加することが可能になる。
【0011】
また、上述した画像取込手段は、光学的に被検索対象画像の濃淡情報あるいは色情報を読み取る光学読取装置であることが望ましい。あるいは、上述した画像取込ステップは、光学的に被検索対象画像の濃淡情報あるいは色情報を読み取る光学読取装置を用いて行われることが望ましい。これにより、検索したい画像を容易に取り込むことが可能になる。
【0012】
また、上述した画像取込手段は、被検索対象画像を構成する複数の画素のそれぞれに対応する濃淡情報あるいは色情報からなる画像データが格納された記録媒体から画像データを読み取るデータ読取装置であることが望ましい。あるいは、上述した画像取込ステップは、被検索対象画像を構成する複数の画素のそれぞれに対応する濃淡情報あるいは色情報からなる画像データが格納された記録媒体から画像データを読み取るデータ読取装置を用いて行われることが望ましい。これにより、既に画像データの形式で保持されている場合に、この画像データを用いることができ、検索したい画像の取り込みをさらに容易に行うことが可能になる。
【0013】
また、上述した特徴情報には、自己相関波形を構成する複数の区分領域に対応する複数の関数の順番が含まれており、画像検索手段は、複数の関数の順番に基づいて複数の比較対象画像の中から被検索対象画像に類似するものを検索することが望ましい。あるいは、上述した特徴情報には、自己相関波形を構成する複数の区分領域に対応する複数の関数の順番が含まれており、画像検索ステップは、複数の関数の順番に基づいて複数の比較対象画像の中から被検索対象画像に類似するものを検索することが望ましい。自己相関波形を構成する複数の関数の順番は、自己相関波形の形状を表す重要な特徴であると考えられる。したがって、関数の順番を用いて画像の類似判定を行うことにより、精度の高い画像検索を行うことができる。
【0014】
また、上述した特徴情報には、自己相関波形を構成する複数の区分領域に対応する複数の関数の各区間長の並びが含まれており、画像検索手段は、区間長の並びに基づいて複数の比較対象画像の中から被検索対象画像に類似するものを検索することが望ましい。あるいは、上述した特徴情報には、自己相関波形を構成する複数の区分領域に対応する複数の関数の各区間長の並びが含まれており、画像検索ステップは、区間長の並びに基づいて複数の比較対象画像の中から被検索対象画像に類似するものを検索することが望ましい。自己相関波形を構成する複数の関数(複数の区分領域)のそれぞれに対応する区間長の並びは、自己相関波形の形状を表す重要な特徴であると考えられる。したがって、区間長の並びを用いて画像の類似判定を行うことにより、精度の高い画像検索を行うことができる。
【0015】
また、上述した画像検索手段は、被検索対象画像と比較対象画像のそれぞれの自己相関波形を構成する複数の区分領域に対応する関数の相関度を計算し、相関度が大きい順に、被検索対象画像に類似する比較対象画像を検索することが望ましい。あるいは、上述した画像検索ステップは、被検索対象画像と比較対象画像のそれぞれの自己相関波形を構成する複数の区分領域に対応する関数の相関度を計算し、相関度が大きい順に、被検索対象画像に類似する比較対象画像を検索することが望ましい。自己相関波形を構成する各関数の相関度は、自己相関波形の形状を表す重要な特徴であると考えられる。したがって、関数の相関度を用いて画像の類似判定を行うことにより、精度の高い画像検索を行うことができる。
【0016】
また、上述した画像検索手段は、被検索対象画像に対応する自己相関波形に含まれる区分領域の総数に着目して、検索対象候補として所定数の比較対象画像を選択した後、特徴情報に基づいて被検索対象画像に類似する比較対象画像を検索することが望ましい。あるいは、上述した画像検索ステップは、被検索対象画像に対応する自己相関波形に含まれる区分領域の総数に着目して、検索対象候補として所定数の比較対象画像を選択した後、特徴情報に基づいて被検索対象画像に類似する比較対象画像を検索することが望ましい。これにより、検索の対象となる画像の数を減らすことができるため、さらに処理負担を軽減して、処理時間を短縮することが可能となる。
【0017】
また、上述した自己相関波形抽出手段は、被検索対象画像の長手方向に沿って自己相関波形を抽出することが望ましい。あるいは、上述した自己相関波形抽出ステップは、被検索対象画像の長手方向に沿って自己相関波形を抽出することが望ましい。長手方向に沿って抽出した自己相関波形は画像の複雑な形状の特徴をよく表しているため、このような自己相関波形を用いることにより、検索精度をさらに高めることが可能になる。
【0018】
また、上述した自己相関波形抽出手段は、被検索対象画像が内接する面積最小の矩形を算出し、この矩形の長辺に沿った向きに自己相関波形を抽出することが望ましい。自己相関波形抽出ステップは、被検索対象画像が内接する面積最小の矩形を算出し、この矩形の長辺に沿った向きに自己相関波形を抽出することが望ましい。これにより、画像の長手方向の再現性を確保することが可能になり、同じ画像に対して常に同じ自己相関波形を取得することができる。
【0019】
また、上述した自己相関波形抽出手段は、被検索対象画像の重心位置を算出し、この重心位置を回転中心とした所定の回転方向に自己相関波形を抽出することが望ましい。あるいは、上述した自己相関波形抽出ステップは、被検索対象画像の重心位置を算出し、この重心位置を回転中心とした所定の回転方向に自己相関波形を抽出することが望ましい。これにより、方向に影響されない安定した自己相関波形を抽出することが可能になる。
【0020】
また、上述した自己相関波形抽出手段は、被検索対象画像が内接する面積最小の矩形と被検索対象画像の重心位置を算出し、矩形の長辺と短辺の比が基準値以上であるときに長辺に沿った向きに自己相関波形を抽出し、矩形の長辺と短辺の比が基準値より小さいときには重心位置を回転中心とした所定の回転方向に自己相関波形を抽出することが望ましい。あるいは、上述した自己相関波形抽出ステップは、被検索対象画像が内接する面積最小の矩形と被検索対象画像の重心位置を算出し、矩形の長辺と短辺の比が基準値以上であるときに長辺に沿った向きに自己相関波形を抽出し、矩形の長辺と短辺の比が基準値より小さいときには重心位置を回転中心とした所定の回転方向に自己相関波形を抽出することが望ましい。一方向に長い画像については長手方向に自己相関波形を抽出し、それ以外の画像については回転方向に自己相関波形を抽出することにより、画像の形状に適した自己相関波形を取得することが可能になる。
【発明を実施するための最良の形態】
【0021】
以下、本発明を適用した一実施形態の類似画像検索装置について、図面を参照しながら詳細に説明する。
【0022】
図1は、一実施形態の類似画像検索装置の構成を示す図である。図1に示す類似画像検索装置は、被検索対象画像が入力されたときにこの画像に類似する登録済みの画像(類似画像)を検索して検索結果を出力するためのものであり、画像入力部110、画像DB(データベース)120、検索処理部130、操作部150、表示部160、印刷装置170を備えている。
【0023】
画像入力部110は、検索処理部130に被検索対象画像を取り込むためのものであり、被検索対象画像を構成する各画素毎の濃淡情報や色情報等を示す画像データの入力を行う。例えば、画像入力部110として、光学的に被検索対象画像を構成する各画素の濃淡情報や色情報を読み取る光学スキャナやデジタルカメラ等の光学読取装置が用いられる。なお、結果的に被検索対象画像を構成する各画素毎の濃淡情報等を示す画像データが得られればよいため、被検索対象画像を構成する各画素の濃淡情報等を示す画像データがCD、DVD、半導体メモリ等の各種の情報記録媒体に記録されている場合に、これらの記録媒体から画像データを読み取るディスクドライブ装置等のデータ読取装置を画像入力部110として用いるようにしてもよい。
【0024】
画像DB120は、被検索対象画像と類似度が比較される複数の画像(これらの画像を「比較対象画像」と称する)に対して関数化近似処理を行って得られる特徴情報を格納する。特徴情報の具体例については、被検索対象画像について行われる関数近似処理において説明する。検索処理部130による処理に先だって、画像DB120に複数の比較対象画像の特徴情報を登録する必要がある。この登録処理の詳細については後述する。
【0025】
検索処理部130は、被検索対象画像の特徴情報を抽出し、この特徴情報に基づいて被検索対象画像に類似する比較対象画像を検索する処理を行う。このために、検索処理部130は、自己相関波形抽出処理部132、接合点抽出処理部134、関数近似処理部136、類似度判定処理部140、検索結果出力処理部142を備えている。
【0026】
自己相関波形抽出処理部132は、画像入力部110によって取り込まれる被検索対象画像の自己相関波形を抽出する。図2および図3は、自己相関波形を抽出する処理の概要を示す図である。自己相関波形を抽出する場合、同一の被検索対象画像G1、G2を2つ重ねた状態(図2)から、一方の被検索対象画像G2を一方向に次第に移動していく(図3)。この過程において、同一座標に対応する2つの被検索対象画像G1、G2の各構成画素同士の内積を計算してそれらを合計して自己相関値が得られる。当然ながら、図2に示すように同一の2つの被検索対象画像G1、G2が重ねられた状態において計算した内積の合計値が最も大きくなる。この合計値を用いて自己相関値の正規化が行われる。このようにして、2つの被検索対象画像G1、G2の間の相対的な移動量と、正規化された自己相関値との関係を示すものが自己相関波形である。
【0027】
図4および図5は、自己相関波形の具体例を示す図である。図4に示すように、横書きされた「Fluency」という文字図形を水平方向に移動させることにより、図5に示すような自己相関波形が得られる。
【0028】
図6および図7は、自己相関波形の他の具体例を示す図である。図6に示すように、横書きされた「Fluency」という文字図形を垂直方向に移動させることにより、図7に示すような自己相関波形が得られる。
【0029】
このように、自己相関波形を抽出する方向が異なると、得られた自己相関波形が異なってしまうため、どの方向に自己相関波形を抽出するかは重要な問題である。しかも、図6および図7に示すように、被検索対象画像の長さが短い(高さが低い)方向に自己相関波形を抽出すると、得られた自己相関波形が単調になる傾向があるため、最も長い方向を抽出する前処理を行って、この抽出した方向に沿って自己相関波形を求めることが望ましい。例えば、被検索対象画像が内接する面積最小の矩形を求め、この矩形の長辺が延在する向きに被検索対象画像を移動させる場合が考えられる。
【0030】
図8は、自己相関波形を抽出する他の処理の概要を示す図である。自己相関波形を抽出する他の例として、同一の被検索対象画像G1、G2を2つ重ねた状態(図2)から、一方の被検索対象画像G2を所定方向に回転させるようにしてもよい(図8)。このときの回転中心は任意の位置を指定することができるが、比較対象画像と被検索対象画像とで回転中心の設定の仕方を同じにする必要がある。例えば、画像の重心位置を求める前処理を行って、その重心位置を中心に画像を回転させることが考えられる。2つの被検索対象画像G1、G2の自己相関値を求める処理については同様であり、このようにして、2つの被検索対象画像G1、G2の間の相対的な回転量(回転角0°~360°の範囲)と、正規化された自己相関値との関係を示すものが自己相関波形である。
【0031】
接合点抽出処理部134は、自己相関波形抽出処理部132によって抽出した自己相関波形に基づいて、この自己相関波形の傾向が変化する接合点を抽出する。例えば、自己相関波形の角度が急に変化する角点が接合点として抽出される。関数近似処理部136は、自己相関波形に沿って隣接する2つの接合点で区分される(分割される)部分的な領域(区分領域)を、直線、円弧、自由曲線のいずれかの関数を用いて近似し、この近似処理に関連する特徴情報を作成する。例えば、区分領域が直線で近似可能な場合には近似関数として直線が用いられ、直線で近似不可能であって円弧で近似可能な場合には近似関数として円弧が用いられる。円弧でも近似不可能な場合には近似関数として自由曲線が用いられる。近似関数として直線を用いた場合には、用いた関数が直線であることを示す符号と、直線で近似される区分領域の形状を示すパラメータとが、この区分領域に対応する近似関数に関する特徴情報として作成される。同様に、近似関数として円弧を用いた場合には、用いた関数が円弧であることを示す符号と、円弧で近似される区分領域の形状を示すパラメータとが、この区分領域に対応する近似関数に関する特徴情報として作成される。近似関数として自由曲線を用いた場合には、用いた関数が自由曲線であることを示す符号と、自由曲線で近似される区分領域の形状を示すパラメータとが、この区分領域に対応する近似関数に関する特徴情報として作成される。
【0032】
なお、着目している区分領域がどの関数で近似可能であるか否かの判定は、区分領域と近似関数との間の誤差(最小二乗法で求めた誤差)が所定値以下であるか否かを調べることにより行われる。また、区分領域の形状を示すパラメータは、この区分領域の形状を特定することが可能であればよいが、例えば、特許第2646475号公報に開示されているように、以下に示すものを用いるようにしてもよい。
(1)直線の場合:直線を示すフラグ、区分領域の始点の座標
(2)円弧の場合:円弧を示すフラグ、円弧の始点の座標、接合点間の中心角の係数、接合点間に存在する輪郭点数、近似関数の係数(円弧を例えば三角関数の線形結合の式で表現した場合の各係数)
(3)自由曲線の場合:接合点間の自由曲線を示す近似関数の次元数(≧3)、接合点間に存在する輪郭点数、接合点間における輪郭点列の変動の中心、近似関数の係数。
【0033】
類似度判定処理部140は、被検索対象画像に対応して抽出される特徴情報に基づいて、被検索対象画像と各比較対象画像との類似度を判定し、被検索対象画像に類似する比較対象画像を決定する。この類似度判定に用いられる特徴情報には、上述した区分領域の形状を示すパラメータの他に、自己相関波形を構成する複数の区分領域に対応する複数の関数の順番、これら複数の関数のそれぞれに対応する区間長(区分領域の長さ)の並び、被検索対象画像と比較対象画像のそれぞれに対応する自己相関波形を構成する関数の相関度などが含まれている。
【0034】
図9は、自己相関波形抽出処理部132、接合点抽出処理部134、関数近似処理部136の各処理によって抽出される特徴情報が含まれる関数テーブルを示す図である。なお、以下の説明に含まれる輪郭線とは、自己相関波形の輪郭線、すなわち自己相関波形そのものを指している。図9に示す関数表には、関数総数、輪郭長、総標本点数、直線個数、直線総長、円弧個数、円弧総長、曲線個数、曲線総長の他に、各輪郭線毎の区間長、標本点数、各関数に対応する区間長やパラメータが含まれている。関数総数は、着目している輪郭線に含まれる関数の総数であって区分領域の数に等しい。輪郭長は、着目している輪郭線の長さである。直線個数は、着目している輪郭線を構成する各区分領域の中で直線によって近似される区分領域の数である。直線総長は、着目している輪郭線を構成する各区分領域の中で直線によって近似される区分領域の長さの合計値である。円弧個数は、着目している輪郭線を構成する各区分領域の中で円弧によって近似される区分領域の数である。円弧総長は、着目している輪郭線を構成する各区分領域の中で円弧によって近似される区分領域の長さの合計値である。曲線個数は、着目している輪郭線を構成する各区分領域の中で自由曲線によって近似される区分領域の数である。曲線総長は、着目している輪郭線を構成する各区分領域の中で自由曲線によって近似される区分領域の長さの合計値である。また、図9において、「関数」の項で示される複数の関数は、着目している自己相関波形を構成する各区分領域を近似する関数を示しており、これらの配置順が各区分領域の並びに対応している。
【0035】
類似度判定処理部140は、図9に示す関数テーブルを参照することにより、自己相関波形を構成する複数の関数の順番や、これら複数の関数のそれぞれに対応する区間長(区分領域の長さ)の並びを知ることができる。
【0036】
検索結果出力処理部142は、検索結果を表示部160の画面上に表示したり、操作部150を用いた印刷操作がなされた場合には印刷装置170に対して検索結果の印刷を指示する。
【0037】
ところで、図9に示した特徴情報は、画像入力部110から入力される被検索画像の画像データに基づいて作成されるが、この特徴情報と比較して類似画像を抽出するためには、多くの比較対象画像について同じ内容の特徴情報をあらかじめ抽出して画像DB120に登録しておく必要がある。
【0038】
図10は、比較対象画像についてあらかじめ特徴情報の抽出を行って画像DB120に対する登録を行うデータベース作成装置の構成を示す図である。なお、図10に示す構成は、図1に示した類似画像検索装置の一部として備わっている場合が考えられるが、図1に示した類似画像検索装置とは別に構築するようにしてもよい。図10に示すデータベース作成装置は、画像DB120に多くの比較対象画像の特徴情報を登録するために、画像入力部210、データベース作成部220、操作部230、表示部240を備えている。
【0039】
画像入力部210は、比較対象画像を構成する各画素毎の濃淡情報や色情報を示す画像データの入力を行う。図1に示した画像入力部110と同様に、この画像入力部210として光学的スキャナ、デジタルカメラやディスクドライブ装置等を用いることができる。
【0040】
データベース作成部220は、比較対象画像の特徴情報を抽出して画像DB120に登録する処理を行う。このために、データベース作成部220は、自己相関波形抽出処理部222、接合点抽出処理部224、関数近似処理部226、ファイル作成処理部228を備えている。この中で、ファイル作成処理部228を除く自己相関波形抽出処理部222、接合点抽出処理部224、関数近似処理部226の基本的な動作は、図1に示した検索処理部130内の同一名称の各構成部と同じであり、詳細な動作説明は省略する。
【0041】
ファイル作成処理部228は、抽出された各比較対象画像毎の特徴情報(図9に示した関数テーブルに含まれる特徴情報)をひとまとまりのファイルとして画像DB120に登録する。操作部230は、比較対象画像に対応する特徴情報の抽出、登録に必要な動作指示等を行うために用いられる。表示部240は、特徴情報の登録内容を確認したり、登録に必要な各種の操作画面を表示するために用いられる。
【0042】
このような構成を有するデータベース作成装置を用いることにより、図9に示した被検索対象画像の特徴情報と基本的に同じ内容を有する複数の比較対象画像の特徴情報が画像DB120に登録される。
【0043】
上述した画像入力部110、210が画像取込手段に、自己相関波形抽出処理部132、222が自己相関波形抽出手段に、接合点抽出処理部134、224が接合点抽出手段に、関数近似処理部136、226が関数近似手段に、類似度判定処理部140が画像検索手段に、画像DB120が特徴情報格納手段に、ファイル作成処理部228が特徴情報格納処理手段にそれぞれ対応する。また、画像入力部110、210によって行われる動作が画像取込ステップの動作に、自己相関波形抽出処理部132、222によって行われる動作が自己相関波形抽出ステップの動作に、接合点抽出処理部134、224によって行われる動作が接合点抽出ステップの動作に、関数近似処理部136、226によって行われる動作が関数近似ステップの動作に、類似度判定処理部140によって行われる動作が画像検索ステップの動作に、ファイル作成処理部228によって行われる動作が特徴情報格納処理ステップの動作にそれぞれ対応する。
【0044】
本実施形態の類似画像検索装置はこのような構成を有しており、次にその動作を説明する。上述したように、被検索対象画像や比較対象画像から抽出される自己相関波形の形状は、どの方向に自己相関処理を行うかによって大きく異なるため、最もこれらの画像の特徴を表し、かつ、再現性のある方向を自己相関処理の方向として設定する必要がある。
【0045】
図11は、検索処理部130において類似画像の検索を行う動作手順を示す流れ図である。例えば、縦横の比率がほぼ1に近い画像については自己相関処理の方向として回転方向を設定し、それ以外の場合には自己相関処理の方向として画像の長手方向を設定する場合の動作手順が示されている。
【0046】
まず、自己相関波形抽出処理部132は、画像入力部110から入力される被検索対象画像(画像A)を取得すると(ステップ100)、この画像Aが内接する面積最小の矩形を算出する(ステップ101)。次に、自己相関波形抽出処理部132は、抽出した矩形の長辺と短辺の比(長辺/短辺)が所定の基準値以上であるか否かを判定する(ステップ102)。図4~図7を用いて説明したように、一方向に長い図形に対しては長手方向に自己相関波形を抽出することが望ましい。したがって、本実施形態では、一方向に長い図形についてはその長手方向に自己相関波形を抽出し、それ以外の図形については回転方向に自己相関波形を抽出することにしている。
【0047】
長辺と短辺の比が基準値(例えば1.5)以上である場合にはステップ102において肯定判断が行われ、次に、自己相関波形抽出処理部132は、矩形の長辺の向きを自己相関処理の方向として設定する(ステップ103)。一方、長辺と短辺の比が基準値よりも小さい場合にステップ102の判定において否定判断が行われ、次に、自己相関波形抽出処理部132は、画像Aの重心位置を算出するとともに(ステップ104)、この重心位置を回転中心とした反時計回り方向を自己相関処理の方向として設定する(ステップ105)。なお、必ずしも反時計回り方向である必要はなく、回転方向を統一することが目的であるため、時計回り方向を自己相関処理の方向として設定するようにしてもよい。
【0048】
次に、自己相関波形抽出処理部132は、設定した方向に自己相関処理を行って、自己相関波形を取得する(ステップ106)。接合点抽出処理部134は、抽出された自己相関波形に対して接合点を抽出し(ステップ107)、関数近似処理部136は、各接合点によって分割される各区分領域のそれぞれを直線、円弧、自由曲線のいずれかの関数で近似する関数化処理を行い(ステップ108)、図9に示した関数テーブルに含まれる特徴情報を抽出する(ステップ109)。
【0049】
類似度判定処理部140は、このようにして被検索対象画像(画像A)の特徴情報が抽出されると、画像DB120から一の比較対象画像(画像B)の特徴情報を読み出し(ステップ110)、これら2つの画像A、Bの類似度を判定する(ステップ111)。
【0050】
ところで、図9に示した関数テーブルの中のどの特徴情報を用いて類似度を判定するかは、各特徴情報の重要度等に応じて適宜決定することができる。例えば、自己相関波形を構成する各区分領域に対応する複数の関数の順番や、関数総数、直線個数、円弧個数、自由直線個数などの特徴情報(特徴量)が単独あるいは組み合わせて類似度判定に用いられる。
【0051】
類似度判定処理部140は、画像Aの自己相関波形に対応する第1の特徴量と画像Bの自己相関波形に対応する第2の特徴量を用いてマッチング処理を行い、マッチング距離Mと相関度Sを以下の式を用いて計算する。
【0052】
M=∥f-g∥
S=<f、g>/(∥f∥×∥g∥)
ここで、∥・∥はノルムを示しており、<・>は内積を示している。また、fは第1の特徴量を成分とするベクトルである。gは第2の特徴量を成分とするベクトルである。
【0053】
マッチング距離Mは2つのベクトルfとgの差ベクトルの長さを示す。また、相関Sは2つのベクトルfとgのなす角θの余弦値(cosθ)を示す。被検索対象画像に対応する第1の特徴量と比較対象画像に対応する第2の特徴量とが非常に近い場合には、2つのベクトルf、gの長さおよび方向が類似したものになるため、マッチング距離Mが小さく、かつ相関度Sが1に近い値になる。類似度判定に用いる特徴量が2つ以上ある場合には、それぞれの特徴量を用いてマッチング距離Mや相関度Sを計算し、この計算結果を全ての特徴量について合計すればよい。
【0054】
ところで、自己相関波形を構成する各区分領域に対応する各関数は、自己相関波形の形状を最も正確に表しているため、各関数の具体的内容を特定するパラメータを特徴量として用いることが望ましい。具体的には、画像Aと画像Bのそれぞれに対応する関数テーブルの中から1番目の区分領域に対応する関数のパラメータを特徴量として抽出し、上述したマッチング距離Mや相関度Sが計算される。比較される2つの関数の種類が異なる場合にはパラメータの数が異なる場合もあるが、その場合には値が0のパラメータを適宜補充して計算が行われる。このようにして2番目、3番目、…の関数同士についてマッチング距離Mと相関度Sが計算される。関数の数(区分領域の数)が異なる場合には、少ない関数の数に合わせて相関度S等の計算が行われる。このようにして計算された全てのマッチング距離Mと相関度Sとが合計されて2つの画像A、Bの類似度が判定される。
【0055】
次に、類似度判定処理部140は、類似度判定が終了していない他の比較対象画像が存在するか否かを判定する(ステップ112)。他の比較対象画像が存在する場合には肯定判断が行われ、次の比較対象画像についてステップ110以降の処理が繰り返される。他の比較対象画像が存在しない場合にはステップ111の判定において否定判断が行われ、次に、検索結果出力処理部142は、類似度判定の結果を出力する(ステップ113)。判定結果の出力は、例えば、類似度が大きいと判定された順に比較対象画像と類似の程度を順番に表示部160に表示したり、印刷装置170を用いて印刷用紙に印刷したりして行われる。
【0056】
このように、本実施形態の類似画像検索装置では、自己相関波形に含まれる各接合点で分割される各区分領域のそれぞれを関数化処理することにより、自己相関波形の微細な特徴を含む全体を正確に関数化近似することができ、この近似処理において抽出された特徴情報を用いることにより、類似画像を検索する際の検索精度を向上させることが可能になる。また、あらかじめ格納された特徴情報を順番に読み出して、取り込まれた被検索対象画像の特徴情報と比較することにより、容易に類似画像の検索を行うことができ、比較対象となる画像が多い場合であっても操作が煩雑にならず、操作の簡略化が可能になる。また、図10に示したデータベース作成装置を用いることにより、比較対象となる画像を適宜追加することが可能になる。
【0057】
また、上述した特徴情報には、自己相関波形を構成する複数の区分領域に対応する複数の関数の順番が含まれている。自己相関波形を構成する複数の関数の順番は、自己相関波形の形状を表す重要な特徴であると考えられる。したがって、関数の順番を用いて画像の類似判定を行うことにより、精度の高い画像検索を行うことができる。
【0058】
また、上述した特徴情報には、自己相関波形を構成する複数の区分領域に対応する複数の関数の各区間長の並びが含まれている。自己相関波形を構成する複数の関数(複数の区分領域)のそれぞれに対応する区間長の並びは、自己相関波形の形状を表す重要な特徴であると考えられる。したがって、区間長の並びを用いて画像の類似判定を行うことにより、精度の高い画像検索を行うことができる。
【0059】
また、類似度判定処理部140は、被検索対象画像と比較対象画像のそれぞれの自己相関波形を構成する複数の区分領域に対応する関数の相関度を計算し、相関度が大きい順に、被検索対象画像に類似する比較対象画像を検索する。自己相関波形を構成する各関数の相関度は、自己相関波形の形状を表す重要な特徴であると考えられる。したがって、関数の相関度を用いて画像の類似判定を行うことにより、精度の高い画像検索を行うことができる。
【0060】
また、長手方向に沿って抽出した自己相関波形は画像の複雑な形状の特徴をよく表しているため、被検索対象画像の長手方向に沿って自己相関波形を抽出することにより、検索精度をさらに高めることが可能になる。特に、被検索対象画像が内接する面積最小の矩形を算出し、この矩形の長辺に沿った向きに自己相関波形を抽出することにより、画像の長手方向の再現性を確保することが可能になり、同じ画像に対して常に同じ自己相関波形を取得することができる。また、被検索対象画像の重心位置を回転中心とした所定の回転方向に自己相関波形を抽出することにより、方向に影響されない安定した自己相関波形を抽出することが可能になる。また、一方向に長い画像については長手方向に自己相関波形を抽出し、それ以外の画像については回転方向に自己相関波形を抽出することにより、画像の形状に適した自己相関波形を取得することが可能になる。
【0061】
なお、本発明は上記実施形態に限定されるものではなく、本発明の要旨の範囲内で種々の変形実施が可能である。例えば、上述した実施形態の検索処理部130やデータベース作成部220の各動作を、CPU、ROM、RAM等を備えたコンピュータによって実施するようにしてもよい。この場合には、ROMやRAMあるいはその他の記憶装置(ハードディスク装置等)に格納された類似画像検索プログラム(図11に示す各ステップを実行したり、検索処理部130やデータベース作成部220の各部の機能を実現するためのプログラム)をCPUで実行すればよい。
【0062】
また、上述した実施形態では、全ての比較対象画像について特徴情報を読み出して類似度判定を行うようにしたが、被検索対象画像の自己相関波形に含まれる区分領域の総数Mに着目して、検索対象候補としての比較対象画像を減らすようにしてもよい。具体的には、比較対象画像の自己相関波形に含まれる区間領域の総数Nが、総数Mと一致あるいは±数%(例えば10%)の範囲に含まれるもののみ選択的に抽出し、類似度判定を行うようにしてもよい。これにより、明らかに形状が異なる比較対象画像に対する類似度判定が不要になり、処理負担の軽減や処理時間の短縮が可能になる。
【0063】
また、上述した実施形態では、被検索対象画像の長手方向あるいは被検索対象画像が内接する面積最小の矩形の長辺方向に沿って被検索対象画像を移動させて自己相関波形を抽出する場合を考えたが、長辺方向と垂直方向あるいは面積最小の矩形の短辺方向に沿って被検索対象画像を移動させて自己相関波形を抽出するようにしてもよい。
【図面の簡単な説明】
【0064】
【図1】一実施形態の類似画像検索装置の構成を示す図である。
【図2】自己相関波形を抽出する処理の概要を示す図である。
【図3】自己相関波形を抽出する処理の概要を示す図である。
【図4】自己相関波形の具体例を示す図である。
【図5】自己相関波形の具体例を示す図である。
【図6】自己相関波形の他の具体例を示す図である。
【図7】自己相関波形の他の具体例を示す図である。
【図8】自己相関波形を抽出する他の処理の概要を示す図である。
【図9】抽出される特徴情報が含まれる関数テーブルを示す図である。
【図10】データベース作成装置の構成を示す図である。
【図11】検索処理部において類似画像の検索を行う動作手順を示す流れ図である。
【符号の説明】
【0065】
110、210 画像入力部
120 画像DB(データベース)
130 検索処理部
132、222 自己相関波形抽出処理部
134、224 接合点抽出処理部
136、226 関数近似処理部
140 類似度判定処理部
142 検索結果出力処理部
150、230 操作部
160、240 表示部
170 印刷装置
220 データベース作成部
228 ファイル作成処理部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10