(57)【要約】【課題】テンプレートが多い場合にも探索対象画像からテンプレートが存在する位置を高速且つ高精度に探索を行う。【解決手段】特徴圧縮手段１０２はテンプレートの特徴ベクトルから圧縮特徴ベクトルを算出し、統合手段１０３は複数のテンプレートの特徴ベクトルを同種のクラスとして統合し、部分空間作成手段１０４はテンプレートの圧縮特徴ベクトル又はクラスに含まれる特徴ベクトルに対して主成分分析で部分空間を作成する。探索対象画像特徴抽出手段１０５は探索対象画像から特徴ベクトルを抽出し、探索対象画像特徴圧縮手段１０６は圧縮特徴ベクトルを算出し、多段探索手段１０７は探索対象画像の特徴ベクトル、又は圧縮特徴ベクトルを、投影距離法によりテンプレートの存在する候補位置の絞り込み、より次元数の多いテンプレートの特徴ベクトルを使用して探索する。【選択図】  図１
2005339075.tif 000002
【特許請求の範囲】
【請求項１】
探索対象画像に存在する可能性のある特定の微小画像のテンプレートとの整合度合いの高い領域を探索する画像探索装置であって、
テンプレート特徴生成装置は、
テンプレートがカラー画像であれば濃淡画像への変換を行い、濃淡画像に変換したテンプレートに対してアフィン変換や射影変換により幾何変形を行い、幾何変換を行ったテンプレートに対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、テンプレートから特徴ベクトルを抽出するテンプレート画像特徴抽出手段と、
前記テンプレート特徴抽出手段により抽出されたテンプレートの特徴ベクトルに対して主成分分析を行い、その結果算出される寄与率の高い少数次元の主成分ベクトルとテンプレートの特徴ベクトルとの内積から圧縮特徴ベクトルを算出するテンプレート特徴圧縮手段と、
前記テンプレート特徴抽出手段により抽出した幾何変形を含まない複数のテンプレートの特徴ベクトルを一つのクラスとしてクラス間の距離を比較し、特徴の類似度の高いものを同種のクラスとして統合し、それらの統合されたテンプレートの特徴を一つのクラスとして算出することで、クラス数を削減するテンプレート統合手段と、
前記テンプレート特徴圧縮手段、又はテンプレート統合手段により算出された複数の幾何変形を含むテンプレートの圧縮特徴ベクトル、又はクラスに含まれる特徴ベクトルに対して、個別のテンプレートに対する圧縮特徴ベクトル、又は個別のクラスに含まれる特徴ベクトルに対して主成分分析を行い、部分空間を作成する部分空間作成手段とを備え、
テンプレート探索装置は、
探索対象画像がカラー画像であれば、濃淡画像への変換を行い、算出された探索対象画像に対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、探索対象画像から特徴ベクトルを抽出する探索対象画像特徴抽出手段と、
前記探索対象画像特徴抽出手段により抽出された探索対象画像特徴ベクトルに対して、前記テンプレート特徴圧縮手段においてテンプレート特徴の圧縮に使用した主成分ベクトルとの内積から圧縮特徴ベクトルを算出する探索対象画像特徴圧縮手段と、
前記探索対象画像特徴抽出手段、又は前記探索対象画像特徴圧縮手段より算出した探索対象画像の特徴ベクトル、又は圧縮特徴ベクトルを、前記部分空間作成手段によりテンプレートから作成した部分空間に投影し、投影距離法により初めは次元数の少ない圧縮特徴ベクトルを使用した探索対象画像とテンプレートとの類似度（投影距離）を算出することでテンプレートの存在する候補位置を絞り込み、以降は絞り込まれた候補位置に対してより次元数の多いテンプレートの特徴ベクトルを使用して探索を行うことで、特徴ベクトルの次元数を増加させながら所定の回数だけ反復的に探索対象画像の探索を行う多段探索手段とを備えた、
ことを特徴とする画像探索装置。
【請求項２】
請求項１記載のテンプレート統合手段において、クラス間の類似度の高いものを同一クラスとし、複数のクラスからクラス数を減らす過程において、ある数のクラスにおける各クラスに含まれるテンプレートの情報を出力し、クラス数の異なる複数の情報に基づき前記テンプレート特徴圧縮手段、及び部分空間作成手段により部分空間を作成することを特徴とする画像探索装置。
【請求項３】
請求項１又は請求項２記載のテンプレート統合手段において、前記テンプレート特徴圧縮手段により抽出された圧縮特徴ベクトルを使用してクラス間の類似度の高いものを同種のクラスとして統合し、統合されたクラスに含まれる特徴ベクトルから前記部分空間作成手段により部分空間を作成することを特徴とする画像探索装置。
【請求項４】
請求項１記載の多段探索手段において、請求項２又は請求項３記載のテンプレート統合手段により生成された、クラス数の異なる複数の情報に基づき、所定のクラス数及び圧縮特徴次元数の組合せでの探索を行い、このときクラス数、及び／又は圧縮特徴次元数を増加させながら複数段での探索を行うことを特徴とする画像探索装置。
【請求項５】
請求項１又は請求項４記載の多段探索手段において、クラス数、及び／又は圧縮特徴次元数の少ない探索において、探索結果に対して所定の閾値による順位、及び／又は類似度による閾値処理を行い、その結果残された領域に対して、上下左右の４近傍、又は上下左右の他に斜め方向も含んだ８近傍のラベル付けを行い、ラベル毎に類似度の最も高い、及び／又は順位の最も上位となる探索位置を候補位置として残すことで候補領域を絞り込む候補領域絞り込み手段を備えたことを特徴とする画像探索装置。
【請求項６】
請求項１記載のテンプレート統合手段において、最短距離法、又は最長距離法、又は郡平均法、又は重心法、又はウォード法、又はＫ−ｍｅａｎｓ法を使用してクラス間の統合を行うことで、クラス数の削減を行うことを特徴とする画像探索装置。
【請求項７】
探索対象画像に存在する可能性のある特定の微小画像のテンプレートとの整合度合いの高い領域を探索する画像探索方法であって、
テンプレート特徴生成過程は、
テンプレートがカラー画像であれば濃淡画像への変換を行い、濃淡画像に変換したテンプレートに対してアフィン変換や射影変換により幾何変形を行い、幾何変換を行ったテンプレートに対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、テンプレートから特徴ベクトルを抽出するテンプレート画像特徴抽出過程と、
前記テンプレート特徴抽出過程により抽出されたテンプレートの特徴ベクトルに対して主成分分析を行い、その結果算出される寄与率の高い少数次元の主成分ベクトルとテンプレートの特徴ベクトルとの内積から圧縮特徴ベクトルを算出するテンプレート特徴圧縮過程と、
前記テンプレート特徴抽出過程により抽出した幾何変形を含まない複数のテンプレートの特徴ベクトルを一つのクラスとしてクラス間の距離を比較し、特徴の類似度の高いものを同種のクラスとして統合し、それらの統合されたテンプレートの特徴を一つのクラスとして算出することで、クラス数を削減するテンプレート統合過程と、
前記テンプレート特徴圧縮過程、又はテンプレート統合過程により算出された複数の幾何変形を含むテンプレートの圧縮特徴ベクトル、又はクラスに含まれる特徴ベクトルに対して、個別のテンプレートに対する圧縮特徴ベクトル、又は個別のクラスに含まれる特徴ベクトルに対して主成分分析を行い、部分空間を作成する部分空間作成過程とを備え、
テンプレート探索過程は、
探索対象画像がカラー画像であれば、濃淡画像への変換を行い、算出された探索対象画像に対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、探索対象画像から特徴ベクトルを抽出する探索対象画像特徴抽出過程と、
前記探索対象画像特徴抽出過程により抽出された探索対象画像特徴ベクトルに対して、前記テンプレート特徴圧縮過程においてテンプレート特徴の圧縮に使用した主成分ベクトルとの内積から圧縮特徴ベクトルを算出する探索対象画像特徴圧縮過程と、
前記探索対象画像特徴抽出過程、又は前記探索対象画像特徴圧縮過程より算出した探索対象画像の特徴ベクトル、又は圧縮特徴ベクトルを、前記部分空間作成過程によりテンプレートから作成した部分空間に投影し、投影距離法により初めは次元数の少ない圧縮特徴ベクトルを使用した探索対象画像とテンプレートとの類似度（投影距離）を算出することでテンプレートの存在する候補位置を絞り込み、以降は絞り込まれた候補位置に対してより次元数の多いテンプレートの特徴ベクトルを使用して探索を行うことで、特徴ベクトルの次元数を増加させながら所定の回数だけ反復的に探索対象画像の探索を行う多段探索過程とを備えた、
ことを特徴とする画像探索方法。
【請求項８】
請求項７記載のテンプレート統合過程において、クラス間の類似度の高いものを同一クラスとし、複数のクラスからクラス数を減らす過程において、ある数のクラスにおける各クラスに含まれるテンプレートの情報を出力し、クラス数の異なる複数の情報に基づき前記テンプレート特徴圧縮過程、及び部分空間作成過程により部分空間を作成することを特徴とする画像探索方法。
【請求項９】
請求項７又は請求項８記載のテンプレート統合過程において、前記テンプレート特徴圧縮過程により抽出された圧縮特徴ベクトルを使用してクラス間の類似度の高いものを同種のクラスとして統合し、統合されたクラスに含まれる特徴ベクトルから前記部分空間作成過程により部分空間を作成することを特徴とする画像探索方法。
【請求項１０】
請求項７記載の多段探索過程において、請求項８又は請求項９記載のテンプレート統合過程により生成された、クラス数の異なる複数の情報に基づき、所定のクラス数及び圧縮特徴次元数の組合せでの探索を行い、このときクラス数、及び／又は圧縮特徴次元数を増加させながら複数段での探索を行うことを特徴とする画像探索方法。
【請求項１１】
請求項７又は請求項１０記載の多段探索過程において、クラス数、及び／又は圧縮特徴次元数の少ない探索において、探索結果に対して所定の閾値による順位、及び／又は類似度による閾値処理を行い、その結果残された領域に対して、上下左右の４近傍、又は上下左右の他に斜め方向も含んだ８近傍のラベル付けを行い、ラベル毎に類似度の最も高い、及び／又は順位の最も上位となる探索位置を候補位置として残すことで候補領域を絞り込む候補領域絞り込み過程を備えたことを特徴とする画像探索方法。
【請求項１２】
請求項７記載のテンプレート統合過程において、最短距離法、又は最長距離法、又は郡平均法、又は重心法、又はウォード法、又はＫ−ｍｅａｎｓ法を使用してクラス間の統合を行うことで、クラス数の削減を行うことを特徴とする画像探索方法。
【請求項１３】
上記の請求項６〜１２のいずれか１項に記載の画像探索方法を、コンピュータプログラムで記載してそれを実行可能にしたことを特徴とするプログラム。
【請求項１４】
上記の請求項６〜１２のいずれか１項に記載の画像探索方法を、コンピュータで実行可能に構成したプログラムをコンピュータで読み取り可能に記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、探索対象画像の中から、テンプレートに類似した領域を探索する画像探索装置及びその方法に係り、特に、多数のテンプレートを使用した探索時に、類似したテンプレートに共通な、あるいは類似したテンプレートを代表する特徴を使用し、複数のテンプレートの存在する可能性のある位置を高速に探索することができるようにする画像探索装置及びその方法に関する。
【背景技術】
【０００２】
個別テンプレートに対する識別を行う手法としては、圧縮した低次元の特徴ベクトルに対して、類似テンプレートの統合を行い、該類似テンプレートを代表する特徴ベクトルにより高速に識別を行った後、高次元の個別テンプレートの特徴を使用して詳細に探索する手法がある（例えば、特許文献１参照）。
【特許文献１】特開平１０−２８９３２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記の特開平１０−２８９３２０号公報では探索対象画像から抽出された個別のテンプレートに対する識別を行うものであり、対象画像中からテンプレートを抽出できなければ識別することができないという問題があった。
【０００４】
本発明は、かかる事情に鑑みてなされたものであって、テンプレートが多い場合にも探索対象画像からテンプレートが存在する位置を高速且つ高精度に探索を行うことができる画像探索装置、画像探索方法、この方法のプログラム及びこのプログラムを記録した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明は、多数のテンプレートが存在した場合に、まず各テンプレートを一つのクラスとし、クラス間の類似度の高いものを統合することでクラス数を削減し、低次元且つ少数のクラスを使用することで探索を高速に行い、該探索結果に対して探索対象画像からテンプレートの存在する領域を絞り込み、該絞り込み結果に対して高次元の特徴ベクトルを使用し詳細に探索するようにしたものであり、
・テンプレート画像から画像のエッジ情報に基づく特徴ベクトルを算出し、
・算出したテンプレートの特徴ベクトルに対して主成分分析を行い、寄与率の高い少数次元の主成分ベクトルとの内積から圧縮特徴ベクトルを算出し、
・各々のテンプレートの特徴ベクトル、又は圧縮特徴ベクトルを一つのクラスの特徴ベクトルとし、クラス間の類似度を算出し、類似度の高いクラス同士を同一のクラスとして統合することでクラス数の削減を行い、
・個別のテンプレートの特徴ベクトル、又は圧縮特徴ベクトル、又はクラスに含まれるテンプレートの特徴ベクトル、又はクラスに含まれるテンプレートの圧縮特徴ベクトルに対し部分空間を作成し、
・探索対象画像から画像のエッジ情報に基づく特徴ベクトルを算出し、
・算出した探索対象画像の特徴ベクトルに対して、テンプレートの主成分分析により求められた主成分ベクトルとの内積から圧縮特徴ベクトルを算出し、
・個別のテンプレート、又は個別のクラスから求められた部分空間と探索対象画像の圧縮特徴ベクトルとの投影距離に基づきテンプレート、又はクラスとの類似度を算出し、
・算出された類似度を類似度の高い順に順位付けした順位、及び／又は類似度に基づき所定の閾値による閾値処理を行い、
・閾値処理を行った各テンプレート、又は各クラスの結果に対して４近傍、又は８近傍でラベル付けし、
・ラベル毎に類似度の最も高い探索位置をそのテンプレート、又はクラスに含まれるテンプレートの候補位置として絞り込みを行い、
・以降は絞り込まれた候補領域において、クラス数、及び／又は圧縮特徴ベクトルの次元数を増加させることによって詳細な探索を繰り返し行い、
探索対象画像に存在する可能性のあるテンプレート数が増加した場合においても、探索時間の増加を少なくする。
【０００６】
したがって、本発明は、以下の画像探索装置、画像探索方法、この方法のプログラム及びこのプログラムを記録した記録媒体を特徴とする。
【０００７】
（１）探索対象画像に存在する可能性のある特定の微小画像のテンプレートとの整合度合いの高い領域を探索する画像探索装置であって、
テンプレート特徴生成装置は、
テンプレートがカラー画像であれば濃淡画像への変換を行い、濃淡画像に変換したテンプレートに対してアフィン変換や射影変換により幾何変形を行い、幾何変換を行ったテンプレートに対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、テンプレートから特徴ベクトルを抽出するテンプレート画像特徴抽出手段と、
前記テンプレート特徴抽出手段により抽出されたテンプレートの特徴ベクトルに対して主成分分析を行い、その結果算出される寄与率の高い少数次元の主成分ベクトルとテンプレートの特徴ベクトルとの内積から圧縮特徴ベクトルを算出するテンプレート特徴圧縮手段と、
前記テンプレート特徴抽出手段により抽出した幾何変形を含まない複数のテンプレートの特徴ベクトルを一つのクラスとしてクラス間の距離を比較し、特徴の類似度の高いものを同種のクラスとして統合し、それらの統合されたテンプレートの特徴を一つのクラスとして算出することで、クラス数を削減するテンプレート統合手段と、
前記テンプレート特徴圧縮手段、又はテンプレート統合手段により算出された複数の幾何変形を含むテンプレートの圧縮特徴ベクトル、又はクラスに含まれる特徴ベクトルに対して、個別のテンプレートに対する圧縮特徴ベクトル、又は個別のクラスに含まれる特徴ベクトルに対して主成分分析を行い、部分空間を作成する部分空間作成手段とを備え、
テンプレート探索装置は、
探索対象画像がカラー画像であれば、濃淡画像への変換を行い、算出された探索対象画像に対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、探索対象画像から特徴ベクトルを抽出する探索対象画像特徴抽出手段と、
前記探索対象画像特徴抽出手段により抽出された探索対象画像特徴ベクトルに対して、前記テンプレート特徴圧縮手段においてテンプレート特徴の圧縮に使用した主成分ベクトルとの内積から圧縮特徴ベクトルを算出する探索対象画像特徴圧縮手段と、
前記探索対象画像特徴抽出手段、又は前記探索対象画像特徴圧縮手段より算出した探索対象画像の特徴ベクトル、又は圧縮特徴ベクトルを、前記部分空間作成手段によりテンプレートから作成した部分空間に投影し、投影距離法により初めは次元数の少ない圧縮特徴ベクトルを使用した探索対象画像とテンプレートとの類似度（投影距離）を算出することでテンプレートの存在する候補位置を絞り込み、以降は絞り込まれた候補位置に対してより次元数の多いテンプレートの特徴ベクトルを使用して探索を行うことで、特徴ベクトルの次元数を増加させながら所定の回数だけ反復的に探索対象画像の探索を行う多段探索手段とを備えた、
ことを特徴とする画像探索装置。
【０００８】
（２）上記の（１）記載のテンプレート統合手段において、クラス間の類似度の高いものを同一クラスとし、複数のクラスからクラス数を減らす過程において、ある数のクラスにおける各クラスに含まれるテンプレートの情報を出力し、クラス数の異なる複数の情報に基づき前記テンプレート特徴圧縮手段、及び部分空間作成手段により部分空間を作成することを特徴とする画像探索装置。
【０００９】
（３）上記の（１）又は（２）記載のテンプレート統合手段において、前記テンプレート特徴圧縮手段により抽出された圧縮特徴ベクトルを使用してクラス間の類似度の高いものを同種のクラスとして統合し、統合されたクラスに含まれる特徴ベクトルから前記部分空間作成手段により部分空間を作成することを特徴とする画像探索装置。
【００１０】
（４）上記の（１）記載の多段探索手段において、（２）又は（３）記載のテンプレート統合手段により生成された、クラス数の異なる複数の情報に基づき、所定のクラス数及び圧縮特徴次元数の組合せでの探索を行い、このときクラス数、及び／又は圧縮特徴次元数を増加させながら複数段での探索を行うことを特徴とする画像探索装置。
【００１１】
（５）上記の（１）又は（４）記載の多段探索手段において、クラス数、及び／又は圧縮特徴次元数の少ない探索において、探索結果に対して所定の閾値による順位、及び／又は類似度による閾値処理を行い、その結果残された領域に対して、上下左右の４近傍、又は上下左右の他に斜め方向も含んだ８近傍のラベル付けを行い、ラベル毎に類似度の最も高い、及び／又は順位の最も上位となる探索位置を候補位置として残すことで候補領域を絞り込む候補領域絞り込み手段を備えたことを特徴とする画像探索装置。
【００１２】
（６）上記の（１）記載のテンプレート統合手段において、最短距離法、又は最長距離法、又は郡平均法、又は重心法、又はウォード法、又はＫ−ｍｅａｎｓ法を使用してクラス間の統合を行うことで、クラス数の削減を行うことを特徴とする画像探索装置。
【００１３】
（７）探索対象画像に存在する可能性のある特定の微小画像のテンプレートとの整合度合いの高い領域を探索する画像探索方法であって、
テンプレート特徴生成過程は、
テンプレートがカラー画像であれば濃淡画像への変換を行い、濃淡画像に変換したテンプレートに対してアフィン変換や射影変換により幾何変形を行い、幾何変換を行ったテンプレートに対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、テンプレートから特徴ベクトルを抽出するテンプレート画像特徴抽出過程と、
前記テンプレート特徴抽出過程により抽出されたテンプレートの特徴ベクトルに対して主成分分析を行い、その結果算出される寄与率の高い少数次元の主成分ベクトルとテンプレートの特徴ベクトルとの内積から圧縮特徴ベクトルを算出するテンプレート特徴圧縮過程と、
前記テンプレート特徴抽出過程により抽出した幾何変形を含まない複数のテンプレートの特徴ベクトルを一つのクラスとしてクラス間の距離を比較し、特徴の類似度の高いものを同種のクラスとして統合し、それらの統合されたテンプレートの特徴を一つのクラスとして算出することで、クラス数を削減するテンプレート統合過程と、
前記テンプレート特徴圧縮過程、又はテンプレート統合過程により算出された複数の幾何変形を含むテンプレートの圧縮特徴ベクトル、又はクラスに含まれる特徴ベクトルに対して、個別のテンプレートに対する圧縮特徴ベクトル、又は個別のクラスに含まれる特徴ベクトルに対して主成分分析を行い、部分空間を作成する部分空間作成過程とを備え、
テンプレート探索過程は、
探索対象画像がカラー画像であれば、濃淡画像への変換を行い、算出された探索対象画像に対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、探索対象画像から特徴ベクトルを抽出する探索対象画像特徴抽出過程と、
前記探索対象画像特徴抽出過程により抽出された探索対象画像特徴ベクトルに対して、前記テンプレート特徴圧縮過程においてテンプレート特徴の圧縮に使用した主成分ベクトルとの内積から圧縮特徴ベクトルを算出する探索対象画像特徴圧縮過程と、
前記探索対象画像特徴抽出過程、又は前記探索対象画像特徴圧縮過程より算出した探索対象画像の特徴ベクトル、又は圧縮特徴ベクトルを、前記部分空間作成過程によりテンプレートから作成した部分空間に投影し、投影距離法により初めは次元数の少ない圧縮特徴ベクトルを使用した探索対象画像とテンプレートとの類似度（投影距離）を算出することでテンプレートの存在する候補位置を絞り込み、以降は絞り込まれた候補位置に対してより次元数の多いテンプレートの特徴ベクトルを使用して探索を行うことで、特徴ベクトルの次元数を増加させながら所定の回数だけ反復的に探索対象画像の探索を行う多段探索過程とを備えた、
ことを特徴とする画像探索方法。
【００１４】
（８）上記の（７）記載のテンプレート統合過程において、クラス間の類似度の高いものを同一クラスとし、複数のクラスからクラス数を減らす過程において、ある数のクラスにおける各クラスに含まれるテンプレートの情報を出力し、クラス数の異なる複数の情報に基づき前記テンプレート特徴圧縮過程、及び部分空間作成過程により部分空間を作成することを特徴とする画像探索方法。
【００１５】
（９）上記の（７）又は（８）記載のテンプレート統合過程において、前記テンプレート特徴圧縮過程により抽出された圧縮特徴ベクトルを使用してクラス間の類似度の高いものを同種のクラスとして統合し、統合されたクラスに含まれる特徴ベクトルから前記部分空間作成過程により部分空間を作成することを特徴とする画像探索方法。
【００１６】
（１０）上記の（７）記載の多段探索過程において、上記の（８）又は（９）記載のテンプレート統合過程により生成された、クラス数の異なる複数の情報に基づき、所定のクラス数及び圧縮特徴次元数の組合せでの探索を行い、このときクラス数、及び／又は圧縮特徴次元数を増加させながら複数段での探索を行うことを特徴とする画像探索方法。
【００１７】
（１１）上記の（７）又は（１０）記載の多段探索過程において、クラス数、及び／又は圧縮特徴次元数の少ない探索において、探索結果に対して所定の閾値による順位、及び／又は類似度による閾値処理を行い、その結果残された領域に対して、上下左右の４近傍、又は上下左右の他に斜め方向も含んだ８近傍のラベル付けを行い、ラベル毎に類似度の最も高い、及び／又は順位の最も上位となる探索位置を候補位置として残すことで候補領域を絞り込む候補領域絞り込み過程を備えたことを特徴とする画像探索方法。
【００１８】
（１２）上記の（７）記載のテンプレート統合過程において、最短距離法、又は最長距離法、又は郡平均法、又は重心法、又はウォード法、又はＫ−ｍｅａｎｓ法を使用してクラス間の統合を行うことで、クラス数の削減を行うことを特徴とする画像探索方法。
【００１９】
（１３）上記の（６）〜（１２）のいずれか１項に記載の画像探索方法を、コンピュータプログラムで記載してそれを実行可能にしたことを特徴とするプログラム。
【００２０】
（１４）上記の（６）〜（１２）のいずれか１項に記載の画像探索方法を、コンピュータで実行可能に構成したプログラムをコンピュータで読み取り可能に記録したことを特徴とする記録媒体。
【発明の効果】
【００２１】
以上のとおり、探索対象画像に存在する可能性のあるテンプレートを探索する手段を高速化する手法として、従来は特徴ベクトルの次元数の少ない物を使用し、テンプレートの存在する候補領域を絞り込むことで高速化を行っていた。しかしながら、この手法ではテンプレート数の増加に伴い探索時間が増加するという問題があった。また、探索対象画像に存在するテンプレートを抽出し、抽出されたテンプレートに対して識別を行う場合には、探索対象画像からのテンプレートの抽出に失敗し、識別を行えないという問題があった。
【００２２】
本発明によれば、低次元、且つ少数クラスの特徴ベクトルを使用した識別結果を用いて候補領域の絞り込みを行い、探索、及び絞り込みの動作を探索に使用する特徴ベクトルの次元数、及び／又はクラス数を増加させながら行うことで、高速、且つ高精度な探索を行うことが可能となる。
【発明を実施するための最良の形態】
【００２３】
図１に、本発明の実施形態の全体構成図を示す。図１において、１０１はテンプレート特徴抽出手段、１０２はテンプレート特徴圧縮手段、１０３はテンプレート統合手段、１０４は部分空間作成手段、１０５は探索対象画像特徴抽出手段、１０６は探索対象画像特徴圧縮手段、１０７は多段探索手段、１０８は候補領域絞り込み手段である。
【００２４】
これら手段のうち、手段１０１〜１０４は、テンプレート特徴生成装置、または辞書生成装置になる。また、手段１０５〜１０８は、探索対象画像からテンプレートを探索する装置または識別装置になる。
【００２５】
本実施形態では、まずテンプレート特徴抽出手段１０１において、テンプレートから、探索に使用する特徴を抽出する。ここで、抽出する特徴は、画像データから得られるエッジ強度、エッジの方向、それらの特徴を所定の範囲で集計し、ヒストグラム化した特徴を使用する。以下に、テンプレート特徴抽出手段１０１におけるテンプレートの特徴作成を詳細に説明する。
【００２６】
まず初めに、テンプレート画像がカラー画像である場合、テンプレート画像に対してＨＩＳ表色系、又はＨＳＶ表色系、又はＣＩＥ（国際照明委員会）の定めたＸＹＺ表色系、又はＣＩＥの定めたＬ＊ａ＊ｂ表色系への変換を行い、変換により得られた明度、又は輝度をもって濃淡画像への変換を行う。次に、濃淡化されたテンプレートに対して幾何変換パラメータによるアフィン変換、又は射影変換を行い、テンプレートを変形させ、変形させたテンプレートに対して平滑化フィルタを使用することでぼかし画像を作成する。次に、テンプレート画像に対して、ｘ方向、ｙ方向の差分をとる。図２に示す例では、ｆはテンプレート画像の画素値、ｘ，ｙは座標、ｇxはｘ方向差分、ｇyはｙ方向差分を示す。
【００２７】
【数１】
2005339075.tif 000003
【００２８】
次に、ｘ方向、ｙ方向差分からエッジ強度、方向を計算する。ここで、Ｉはエッジ強度、θは方向（−π＜θ≦π）を示す。
【００２９】
【数２】
2005339075.tif 000004
【００３０】
次に、図３に示すように、上記で算出したエッジの方向を所定の数に量子化する。以下に８方向に量子化する場合の例を示す。ここで、Ｄは量子化した方向を示す。
【００３１】
【数３】
2005339075.tif 000005
【００３２】
次に、図４に示すように、テンプレートを所定の大きさ（画素数）のブロックに分割し、ブロック毎に量子化され方向別のエッジ強度の総和を計算する。また、Ｗｄｈはブロック毎、方向毎に集積したエッジ強度のの総和、Ｘ，Ｙはブロックの座標、Ｍは量子化された方向、Ｎは所定のブロックサイズを示す。
【００３３】
【数４】
2005339075.tif 000006
【００３４】
次に、図５に示すように、フィルタにより方向に対するぼかし処理、方向数の削減を行う。以下にＷd＝（1,3,6,3,1）のフィルタを使用する場合の例を示す。ここで、Ｗｄｈ’，Ｍ’はそれぞれぼかし処理と方向数の削減を行った後のブロック毎、方向毎に集積したエッジ強度の総和、量子化された方向を示す。
【００３５】
【数５】
2005339075.tif 000007
【００３６】
但し、ここでＷｄｈの３つ目の引き数が負になる場合は、その変数に量子化した方向数を足して正の値にする。
【００３７】
最後にテンプレート画像から生成した特徴ベクトルに対して、算出した特徴ベクトルを所定の大きさ（ブロック数）で切り出し、切り出した特徴ベクトルを特徴ベクトル全体の２乗和が所定の大きさになるよう正規化する。テンプレート、及びテンプレート特徴抽出手段１０１により算出したテンプレートの特徴ベクトルの例をそれぞれ図６（ａ）、図６（ｂ）に示す。
【００３８】
次に、本実施形態ではテンプレート特徴圧縮手段１０２、又はテンプレート統合手段１０３、又は部分空間作成手段１０４に処理を移す。
【００３９】
まず、テンプレート特徴圧縮手段１０２の動作について説明する。テンプレート特徴圧縮手段１０２では、テンプレート特徴抽出手段１０１より出力された全テンプレートの特徴ベクトルに対して主成分分析を行い、その結果として出力される上位Ｋ個の主成分ベクトルと、特徴抽出手段により出力された特徴ベクトルとの内積を計算し、各内積値をベクトルとみなした圧縮特徴ベクトルを算出する。ここで、特徴の圧縮率は、原特徴の次元数と入力された次元数により算出される。例えば、原特徴の次元数をＤ、入力された次元数をｄとすると、圧縮率はｄ／Ｄで定義される。
【００４０】
次に、テンプレート統合手段１０３の動作について説明する。テンプレート統合手段１０３では、まずテンプレート特徴抽出手段１０１により抽出されたテンプレートの特徴ベクトル、又はテンプレート特徴圧縮手段１０２において圧縮されたテンプレートの圧縮特徴ベクトルの各々を一つのクラスの特徴として扱う。次に、クラス間の類似度を算出し、クラス間の類似度の高いもの同一のクラスとして、クラスの統合を行い以降の処理に移る。
【００４１】
図７（ａ）にテンプレートの特徴ベクトルを２次元と仮定した場合の、特徴ベクトル空間でのそれぞれのテンプレートの位置を示す。図７（ａ）の文字や記号を円で囲った範囲がそれぞれの文字や記号の特徴ベクトルの位置とする。まず初めにのそれぞれの円を一つのクラスとして扱う。ここで、類似度の高いクラスは、図７（ｂ）のように複数のクラスを囲む楕円のように一つのクラスとして扱われ、この処理を繰り返すことによりクラス数を削減する。ここでは特徴ベクトル空間は２次元と仮定しているが、本来は多次元の特徴空間を構成するものとする。
【００４２】
また、テンプレート統合手段１０３において、クラス数削減の途中過程におけクラス数を使用して探索を行う場合は、図８（ａ）〜（ｃ）のようにクラス数削減過程のクラスを出力して使用する。また、クラスの統合手法として、図７、図８ではクラス間の距離の最も小さいものから統合する最短距離法（例えば、文献「パソコンによるデータ解析、赤池弘次監修、村上征勝一・田村義保編集、朝倉書店」を参照）を例としてあげているが、最長距離法、又は郡平均法、又は重心法、又はウォード法（例えば、文献「パソコンによるデータ解析、赤池弘次監修、村上征勝・田村義保編集、朝倉書店」を参照）、又はＫ−ｍｅａｎｓ法（例えば、文献「コンピュータ画像処理、田村秀行編著、オーム社出版局」を参照）を使用してクラスの統合を行う場合もある。
【００４３】
また、テンプレート特徴圧縮手段１０２より算出されたテンプレートの圧縮特徴ベクトルに基づきテンプレート統合手段１０３においてクラスの削減を行う場合も、テンプレート特徴圧縮手段１０２により算出した圧縮特徴ベクトルに基づき図７又は図８のように特徴ベクトル空間を構成し、同様の手段でクラス数の削減を行う。この場合も先程同様、テンプレート特徴圧縮手段１０２により算出された特徴ベクトルの次元数と同数の多次元特徴空間を構成するものとする。
【００４４】
次に、部分空間作成手段１０４の動作について説明する。部分空間作成手段１０４では、テンプレート特徴圧縮手段１０１、又はテンプレート特徴圧縮手段１０２、又はテンプレート統合手段１０３により算出されたテンプレートの特徴ベクトル、又はテンプレートの圧縮特徴ベクトル、又はクラスに含まれるテンプレートの特徴ベクトルに基づき部分空間を作成する。部分空間はテンプレートの特徴ベクトル、又は圧縮特徴ベクトルを使用する場合は個別のテンプレート毎に、全変形テンプレートの特徴ベクトル、又は圧縮特徴ベクトルを主成分分析することにより求める。また、テンプレート統合手段１０３において統合されたクラスに含まれる特徴ベクトルを使用する場合は、クラス毎に、クラスに含まれる全変形テンプレートの特徴ベクトル、又は圧縮特徴ベクトルを主成分分析することで求めることができる。
【００４５】
次に、探索対象画像特徴抽出手段１０５の勲作について説明する。探索対象画像特徴抽出手段１０５における探索対象画像の特徴抽出の方法は、テンプレートに対する特徴作成手段と同様の処理を行うことで作成することができる。すなわち、探索対象画像がカラー画像である場合、探索対象画像に対してＨＩＳ表色系、又はＨＳＶ表色系、又はＣＩＥ（国際照明委員会）の定めたＸＹＺ表色系、又はＣＩＥの定めたＬ＊ａ＊ｂ表色系への変換を行い、変換により得られた明度、又は輝度をもって濃淡画像への変換を行い、算出された探索対象画像に対してぼかし処理を加え、ぼかし処理後の画像に対して微分処理を行い、求められたエッジ強度特徴や、エッジの方向特徴を所定の領域内で集積・ヒストグラム化することで、探索対象画像から特徴ベクトルを抽出する。但し、探索対象画像に対する幾何変換は行わないものとし、探索対象画像の正規化を行う場合は探索を行う際にテンプレートと同数のブロックを切り出し、切り出したブロックに対して正規化を行うものとする。
【００４６】
次に、探索対象画像特徴圧縮手段１０６の動作について説明する。探索対象画像特徴圧縮手段１０６では探索対象画像特徴抽出手段１０５により算出された探索対象画像の特徴ベクトルと、テンプレート特徴圧縮手段１０２においてテンプレートの圧縮特徴ベクトル作成に使用した主成分ベクトルとの内積を計算することにより、探索対象画像の圧縮特徴ベクトルを算出する。
【００４７】
最後に、多段探索手段１０７、及び候補領域絞り込み手段１０８の動作について説明する。多段探索手段１０７では、探索対象画像特徴圧縮手段１０６により算出した探索対象画像の圧縮特徴ベクトルを、部分空間作成手段１０４で作成した部分空間へ投影した距離（投影距離、例えば、文献「田村秀行：コンピュータ画像処理、pp282-286、オーム社出版局、2002」を参照）を算出する。この距離が小さいほど類似度が高いものとする。
【００４８】
ここで、探索対象面像とテンプレートとの類似度の算出には、次元数の少ない特徴、又はテンプレート統合手段１０３により削減された少数のクラスに含まれるテンプレートの特徴ベクトルにより算出した部分空間への投影距離により、まずは文字候補を絞り込む。文字候補の絞り込みは、クラス数、及び／又は圧縮次元数の少ない特徴ベクトルを用いて探索を行った後、クラス、又はテンプレートでの類似度の高い順に順位付けを行った順位、及び／又は類似度による所定の閾値による閾値処理を行い、その結果残された領域に対して、上下左右の４近傍、又は上下左右の他に斜め方向も含んだ８近傍のラベル付けを行い、ラベル毎に類似度の最も高い探索位置を候補位置として残すことにより行う。図９（ａ）から（ｃ）にそれぞれ閾値処理後、４近傍によるラベル付け後、候補領域の絞り込み後のあるカテゴリの例を示す。次に、特徴ベクトル次元数、又はテンプレート数のどちらか一方、又は双方を増加させて識別を複数回繰り返し、最終的にはテンプレート数削減前の、個別のテンプレートの特徴ベクトル、又は高次元の圧縮特徴ベクトルを使用することで高精度な探索を行う。
【００４９】
本実施形態の処理を図１０〜図１２のフローチャートで説明する。
【００５０】
図１０は本実施形態におけるテンプレートの特徴ベクトル算出までの処理の流れを示す図である。テンプレート特徴の作成には、まずＳ１においてテンプレートを読み込む。ここで、テンプレート画像がカラー画像であれば、Ｓ２からＳ３の処理に移り、Ｓ３においてカラー画像から濃淡画像への変換を行う。カラー画像でない場合、又はＳ３の処理によりカラー画像から濃淡画像に変換した後、Ｓ４の処理へ移り、幾何パラメータにより変形させた複数のテンプレートを作成する。
【００５１】
次に、Ｓ５において変形させたテンプレート画像に対して平滑化を行う。次に、Ｓ６からＳ８において、それぞれ画像のＸ方向とＹ方向の微分処理、微分画像からのエッジ強度、量子化されたエッジの方向を算出する。次に、Ｓ９において画像を所定の領域（画素数）で分割し、分割した領域内のエッジ強度を方向別に集積し、Ｓ１０において集積した方向別の特徴に対して方向の平滑化を含む方向数削滅処理を行い、Ｓ１１において特徴ベクトルの二乗和が一定になるように特徴ベクトルの正規化を行う。Ｓ１２，Ｓ１３ではそれぞれ全変形に対して特徴計算を行ったか、全テンプレートに対して特徴計算を行ったかの判定であり、それぞれの条件を満たすまで、Ｓ５からＳ１１，Ｓ１からＳ１２の処理を繰り返し行う。
【００５２】
次に、Ｓ１４の処理に移り、Ｓ１４ではＳ１３までに算出した特徴ベクトルを圧縮する／しないの判定を行う。特徴の圧縮を行う場合はＳ１５において主成分分析を行い、次いでＳ１６で圧縮特徴ベクトルを算出した後にＳ１７の処理へ移る。Ｓ１６の圧縮特徴ベクトル算出時には、圧縮率の異なる複数の圧縮特徴ベクトルを算出することもある。Ｓ１７ではテンプレートを削減する／しないの判定を行い、テンプレート数を削減しない場合はそれまでの結果をもってテンプレート特徴とし、そうでない場合はＳ１８からＳ２１の処理を経てテンプレート特徴を算出する。
【００５３】
Ｓ１８ではまず一つのテンプレートを一つのクラスとして扱い、クラス間の類似度を算出し、類似度の高いクラスを同一のクラスとすることでクラス数の削減を行う。ここで、クラス間の類似度としては、これまでに算出した圧縮／非圧縮のテンプレート特徴の中の幾何変形の加わっていないものを使用することとする。次いで、Ｓ１９においてクラス数の削減過程を出力する／しないの判定を行い、クラス数の削減過程を出力す冬場合はＳ２０においてクラス数削減過程のクラスに含まれるテンプレートの特徴ベクトルを出力し、そうでない場合はＳ２１の処理に移る。Ｓ２１ではＳ１８、又はＳ２０により出力されたクラスに含まれるテンプレートの特徴をテンプレート特徴ベクトルとして算出する。
【００５４】
図１１は本実施形態における探索対象画像の特徴ベクトル算出処理のフローチャートである。探索対象画像の特徴ベクトル算出には、まずＳ２２で探索対象画像を読み込み、次にＳ２３で探索対象画像がカラー画像がそうでないかを判定し、カラー画像の場合はＳ２４において濃淡画像への変換を行う。次に、濃淡画像に対してＳ２５で平滑化を行い、Ｓ２６からＳ２８において、それぞれ画像のＸ方向とＹ方の微分処理、微分画像からのエッジ強度、量子化されたエッジの方向を算出する。
【００５５】
次に、Ｓ２９において画像を所定の領域（画素数）で分割し、分割した領域内のエッジ強度を方向別に集積し、Ｓ３０において集積した方向別の特徴に対して方向の平滑化を含む方向別削減処理を行う。Ｓ３１ではＳ３０までに算出した特徴ベクトルを圧縮する／しないの判定を行う。特徴の圧縮を行う場合はＳ３２において主成分分析を行い、次いでＳ３３で算出した圧縮特徴ベクトルを探索対象画像の特徴ベクトルとし、そうでない場合は非圧縮の特徴ベクトルを探索対象画像の特徴ベクトルとする。ここで、探索対象画像の特徴ベクトルを圧縮する場合は、テンプレート特徴ベクトルと同じ圧縮率で圧縮する。
【００５６】
図１２は本実施形態におけるテンプレート特徴から部分空間を作成する処理のフローチャートである。テンプレートの特徴ベクトルから部分空間を作成するには、まずＳ３４でテンプレートの特徴ベクトルを読み込む。次に、Ｓ３５で読み込んだ特徴ベクトルのテンプレート（削減されている場合はクラス）数が削減されていない／いるの判定を行い、テンプレート（クラス）数が削減されていない場合はＳ３６でテンプレート毎に全変形テンプレートに対して主成分分析を行い、テンプレート数が削減されている場合はＳ３７で類似テンプレート毎に全変形テンプレートに対して主成分分析を行い、これら分析を基にＳ３８で部分空間を作成する。Ｓ３９では全てのテンプレートに対して部分空間を作成した／していないの判定を行い、全てのテンプレートの部分空間を作成した場合は部分空間を出力し、全てのテンプレートの部分空間を作成していない場合は、Ｓ３４へ戻り部分空間を作成していないテンプレートの部分空間を作成する。
【００５７】
図１３は本実施形態における多段探索手段、及び候補領域絞り込み手段の処理のフローチャートである。多段探索手段では、まずＳ４０で部分空間作成手段において作成した部分空間を読み込み、次にＳ４１で探索対象画像の圧縮特徴ベクトルを読み込む。次に、Ｓ４２で部分空間と探索対象画像の圧縮特徴ベクトルから投影距離を算出し、Ｓ４３において投影距離に基づき候補の絞り込みを行う。
【００５８】
次に、Ｓ４４において全部分空間に対して探索が終了したかの判定を行い、全部分空間に対して探索が終了している場合はＳ４５の処理に移り、そうでない場合は探索を行っていない部分空間を使用して繰り返し探索対象画像からの探索を行う。Ｓ４５では候補領域の絞り込みをおこなうかどうかの判定を行い、候補領域を絞り込む場合はＳ４６において順位、及び／又は類似度による閾値処理を行い、Ｓ４７において閾値処理により残された候補領域に対してラベル付けを行い、Ｓ４８においてラベル毎に類似度の最も高い探索位置を候補領域として残しＳ４９の処理へ移る。
【００５９】
候補領域の絞り込みを行わない場合はＳ４５の後にＳ４９の処理へ移る。Ｓ４９では圧縮率の異なるテンプレートの圧縮特徴ベクトル、又は／及び一つのクラスに含まれるテンプレート数が１になっているかどうかの判定を行う。ここで、より高次元のテンプレートの圧縮特徴ベクトル、又は／及び一つのクラスに含まれるテンプレートが１でない場合は、Ｓ５０でテンプレートの圧縮次元数の多い部分空間、又は／及び一つクラスに含まれるテンプレート数のより少ないクラスから算出した部分空間を選択し、繰り返し探索対象画像からの探索を行う。存在しない場合は探索を終了し、その結果を探索結果として出力することで処理を終える。
【００６０】
なお、本発明は、図１０〜図１３に示した方法の一部又は全部の処理機能をプログラムとして構成してコンピュータに実行させることができる。また、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、フレキシブルディスク、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることが可能であり、また、インターネットのような通信ネットワークを介して配布したりすることが可能である。
【図面の簡単な説明】
【００６１】
【図１】本発明の実施形態を示す全体構成図。
【図２】探索対象画濠特徴抽出手段、テンプレート特徴抽出手段における微分処理の一例。
【図３】探索対象画像特徴抽出手段、テンプレート特徴抽出手段におけるエッジ方向の量子化の一例。
【図４】探索対象画像特徴抽出手段、テンプレート特徴抽出手段における所定の領域内での特徴の集積の一例。
【図５】探索対象画像特徴抽出手段、テンプレート特徴抽出手段における方向平滑化による方向数削滅処理の一例。
【図６】探索対象画像と探索対象画像特徴抽出手段により抽出された特徴の一例。
【図７】テンプレート統合手段におけるテンプレート（クラス）数削減の一例。
【図８】テンプレート統合手段におけるテンプレート（クラス）数削減の一例。
【図９】候補領域絞り込み手段における候補領域絞り込みの一例。
【図１０】テンプレート特徴抽出手段、テンプレート特徴圧縮手段、テンプレート統合手段によるテンプレート特徴ベクトル算出までの処理フローチャート。
【図１１】探索対象画像特徴抽出手段、探雫対象画像特徴圧縮手段による探索対象画像の特徴ベクトル算出までの処理フローチャート。
【図１２】部分空間作成手段における処理フローチャート。
【図１３】多段探索手段における処理フローチャート。
【符号の説明】
【００６２】
１０１  探索対象画像特徴抽出手段
１０２  探索対象画像特徴圧縮手段
１０３  テンプレート特徴抽出手段
１０４  テンプレート特徴圧縮手段
１０５  テンプレート統合手段
１０６  部分空間作成手段
１０７  多段探索手段
【図１】
2005339075.tif 000008
【図２】
2005339075.tif 000009
【図３】
2005339075.tif 000010
【図４】
2005339075.tif 000011
【図５】
2005339075.tif 000012
【図７】
2005339075.tif 000013
【図８】
2005339075.tif 000014
【図９】
2005339075.tif 000015
【図１０】
2005339075.tif 000016
【図１１】
2005339075.tif 000017
【図１２】
2005339075.tif 000018
【図１３】
2005339075.tif 000019
【図６】
2005339075.tif 000020