(57)【特許請求の範囲】
【請求項１】
画像情報の特徴量をヒストグラム（または、ベクトル）化し、該ヒストグラム同士を比較することで、類似像を検索するシステムにおける形状情報のヒストグラム化方法において、
画像情報から形状の特徴量を得る場合に、
特定の基準に基づいた円を描き、
前記円の円周上の各点Ｘｉから中心に向かった直線を描き、
前記直線が図形と最初にぶつかった地点をＺｉとし、
または、前記直線が中心までに前記図形とぶつからない場合には前記円の中心をＺｉとし、
前記点Ｘｉと前記地点Ｚｉとの距離をＤとし、
前記各点Ｘｉにおけるヒストグラム値を距離Ｄとし、
前記各点Ｘｉと前記地点Ｚｉの間を塗りつぶし、
塗りつぶせない領域が発生した場合には、
再度外周点から塗りつぶせなかった領域をヒストグラム化する処理を行い、
前記塗りつぶせなかった領域をヒストグラム化する処理を特定の回数または、塗りつぶせない領域が存在しなくなるまで繰り返すことを特徴とする形状情報のヒストグラム化方法。
【請求項２】
利用者からの検索キー図形入力を行い、入力された該図形の特徴量のヒストグラム（または、ベクトル）として抽出し、該ヒストグラムとデータベース中のヒストグラム間の類似度の計算を行うことで、キー図形に近い図形の検索結果を返す部分形状情報による検索方法において、
前記検索キー図形の入力を行う際に、円で入力領域を制限し、
前記利用者は、前記入力領域を検索対象図形の重心を中心とする外接円、または、最小外接円とみなしたときの検索対象図形の一部分の形状を指定し、
入力された部分形状から前記外接円を使った形状のヒストグラム方法により、部分形状が指定された部分では、該部分形状の情報をヒストグラム化し、該部分形状が指定されなかった部分では、例外値を取るヒストグラムとし、
ヒストグラム内の例外値でない部分を検索キーとして、
前記データベース内のヒストグラムと最も類似する部分の検出を行い、
類似形状を検索することを特徴とする部分形状情報による検索方法。
【請求項３】
前記利用者が前記部分図形がどの角度の範囲に存在するかを指定すると、
指定された角度の範囲に対応するヒストグラムの部分に限定して、ヒストグラム内の例外値でない部分を検索キーとし、前記データベース内のヒストグラムと最も類似する部分の検出を行い、
類似図形を検索する請求項２記載の部分形状情報による検索方法。
【請求項４】
前記部分形状の入力を受け付けると、前記利用者は、１つの検索対象図形の複数の部分形状の指定を行い、
複数の図形間の角度の許容範囲の入力を行い、
指定された前記角度の範囲の入力を行い、指定された角度範囲に対応するヒストグラムの部分に限定して、該ヒストグラム内の例外値でない部分を検索キーとし、
前記データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する請求項２または、３記載の部分形状情報による検索方法。
【請求項５】
利用者からの検索キー図形の入力を行うキー図形入力手段と、該キー図形入力手段によって入力された図形の特徴量をヒストグラム（または、ベクトル）として抽出するヒストグラム作成手段と、該ヒストグラムとデータベース中に格納されているヒストグラム間の類似度計算を行うことで、該検索キー図形に近い図形の検索結果を返す類似度算出手段とを有する部分形状情報による検索装置であって、
円で入力領域を制限した部分キー図形の入力を行う部分キー図形入力手段と、
前記利用者から前記入力領域を検索対象図形の重心を中心とする外接円、または、最小外接円とみなしたときの検索対象図形の一部分を指定する部分形状入力手段を含み、
前記ヒストグラム作成手段は、
外接円を用いた形状のヒストグラム化方法を用いて、部分形状が指定された部分では、該部分形状の情報をヒストグラムかし、該部分形状が指定されなかった部分では、例外値を取るヒストグラムとする部分形状情報ヒストグラム化手段を含み、
前記類似度算出手段は、
前記ヒストグラム内の例外値でない部分を検索キーとして、前記データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する部分的類似度算出手段を含むことを特徴とする部分形状情報による検索装置。
【請求項６】
前記部分形状入力手段は、
前記利用者により指定された前記部分図形がどの角度の範囲に存在するかの指定を行う角度入力手段を含み、
前記部分類似度算出手段は、
前記角度入力手段により指定された前記角度の範囲に対応するヒストグラムの部分に限定して該ヒストグラム内の例外値でない部分を検索キー図形とし、前記データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する限定部分的類似度算出手段を含む請求項５記載の部分形状情報による検索装置。
【請求項７】
前記部分形状入力手段は、
複数の前記部分形状の入力を受け付け、前記利用者は、１つの検索対象図形の複数の部分形状の指定を行う部分形状指定手段を含み、
前記部分類似度算出手段は、
前記角度入力手段で指定された前記角度の範囲に対応するヒストグラムの部分に限定して、該ヒストグラム内の例外値でない部分を検索キー図形とし、前記データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する検索キー設定手段を含む請求項５または６記載の部分形状情報による検索装置。
【請求項８】
利用者からの検索キー図形の入力を受け付けるキー図形入力ステップと、該キー図形入力ステップによって入力された図形の特徴量をヒストグラム（または、ベクトル）として抽出するヒストグラム作成ステップと、該ヒストグラムとデータベース中に格納されているヒストグラム間の類似度計算を行うことで、前記検索キー図形に近い図形の検索結果を返す類似度算出ステップとを実行する部分形状情報による検索プログラムを格納した記憶媒体であって、
前記キー図形入力ステップは、
円で入力領域を制限した部分キー図形の入力を受け取る部分キー図形入力ステップと、
前記利用者から、前記入力領域を検索対象図形の重心を中心とする外接円、または、最小外接円とみなしたときの検索対象図形の一部分の形状の指定を取得する部分形状入力ステップと、を実行し、
前記ヒストグラム作成ステップは、
外接円を用いた形状のヒストグラム化方法を用いて、部分形状が指定された部分では、該部分形状の情報をヒストグラム化し、該部分形状が指定されなかった部分では、例外値をとるヒストグラムとする部分形状情報ヒストグラム化ステップを実行し、
前記類似度算出ステップは、
前記ヒストグラム内の例外値でない部分を検索キー図形として、前記データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する部分的類似度算出ステップを実行するプログラムを格納したことを特徴とする部分形状情報による検索プログラムを格納した記憶媒体。
【請求項９】
前記部分形状入力ステップは、
前記利用者により指定された前記部分図形がどの角度の範囲に存在するかの指定を受け取る角度入力ステップを実行し、
前記部分類似度算出ステップは、
前記角度入力ステップにより指定された前記角度の範囲に対応するヒストグラムの部分に限定して該ヒストグラム内の例外値でない部分を検索キー図形とし、前記データベース内のヒストグラム内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する限定部分的類似度算出ステップを実行する請求項８記載の部分形状情報による検索プログラムを格納した記憶媒体。
【請求項１０】
前記部分形状入力ステップは、
複数の前記部分形状の入力を受け付け、前記利用者からの１つの検索対象図形の複数の部分形状の指定を受け取る部分形状指定ステップを実行し、
前記部分的類似度算出ステップは、
前記角度入力ステップで指定された前記角度の範囲に対応するヒストグラムの部分に限定して、該ヒストグラム内の例外値でない部分を検索キーとし、前記データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する検索キー設定ステップを実行する請求項８または９記載の部分形状情報による検索プログラムを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、形状情報のヒストグラム化方法に係り、特に、画像認識や画像に対する検索を行うマルチメディアシステムにおいて、画像の形状に関する特徴量を取得する形状情報のヒストグラム化方法に関する。
また、本発明は、部分形状情報による検索方法、製造及び部分形状情報による検索プログラムを格納した記憶媒体に係り、画像認識や画像に対する検索を行うマルチメディアシステムにおいて、画像内オブジェクトや図形の部分的な形状を使った部分形状情報による検索方法、装置及び部分形状情報による検索プログラムを格納した記憶媒体に関する。
【０００２】
【従来の技術】
多くの画像検索はヒストグラムをベースに行われている。なお、このヒストグラムは単にベクトルと言い換えても構わない。
【０００３】
画像からの部分画像を抽出する処理を持つ画像検索システムの場合には、画像の場合と同様に、その抽出された部分画像（以後、図形と呼ぶ）に対して形状や色の特徴量をヒストグラム化して比較する。
これまでの画像検索システムにおいて、色情報からのヒストグラム作成は頻繁に行われている。色が３色（白、灰色、黒）とした場合の例を図１５に示す。同図において、色情報をヒストグラム化するためには、それぞれの色の出現回数を求める。この場合には、白が１０４回、灰色が２１回、黒が４３回なので、１０４、２１、４３という３本の棒からなるヒストグラムを生成することができる。
【０００４】
同様に白黒図形の場合には、図１６のようになる。この例では、示していないが、通常は１６色や２７色を用いる。
これまで、形をヒストグラム化する手法については、エッジの方向を利用する方法や、４方向からの距離を利用する方法が存在している。エッジの方向を８種類（上、右上、右、右下、下、左下、左、左上）に限定した場合の例を図１７に示す。この場合には、上が４、右上が２、右が８、右下が２、下が４、左下が４、左が４、左上が４という８本の棒からなるヒストグラムを生成することができる。
【０００５】
４方向からの距離を利用する方法の例を図１８に示す。この場合、辺から図形までの距離をそのままヒストグラムとする。これを４辺それぞれに対して行うため、ヒストグラムは４つ生成される。これを４つとして扱うか１つに纏めて扱うかはシステムに依存する。
次に従来の類似図形の検索方法について説明する。
【０００６】
図１９に示す従来のキー図形入力部１２は、図形全体の形状に対する入力部しかなく、図形の全体の形状に対する入力部のみが存在する。
また、類似図形検索部（類似図形を含む画像の検索部１８）においても、ヒストグラム全体に対する類似度計算しか行っていない。
この主たる理由は、従来の形状検索の精度が悪く、形状検索自体が不可能であるためである。従って、擬似的に部分的な形状について検索を行いたい場合は、予め部分形状のテンプレート（突起、直線、丸み、等）を用意し、その範囲でデータベース（図形とベクトルの組の管理部１７）に格納する図形及び検索キー図形から各テンプレートへの類似度を特徴量としたものをベクトル値として抽出し、それらの類似度計算として実現している。
【０００７】
例えば、図２０の（ａ），（ｃ）〜（ｅ）はいずれも丸状の突起が２つあるという情報になる。
【０００８】
【発明が解決しようとする課題】
しかしながら、上記従来の形状のヒストグラム化の手法には以下のような問題がある。
エッジ方向による方法では、エッジ方向の頻度を表しているため、たとえ、同じヒストグラムの形であっても、全く異なる図形である可能性が高い。また、直感的に形状の情報を表現しているも認識しがたい。
【０００９】
また、４辺からの距離による方法では、図形の形を素直に表現できるが、傾いた図形の場合には全く異なるヒストグラムになってしまう。また、内部に空間を持たない図形（例えば●）と、内部に空間を持つ図形（例えば、○）が同じになってしまう。
また、上記従来の部分形状のテンプレートを使った類似図形検索では、部分形状の種類が予め制限され、図２０に示すような微妙な違いを指定することが難しく、インタフェースとしても、２次元的ではなく、選択的なものしかない。
【００１０】
特に、単純なイラストでなく写真等から抽出したオブジェクトの場合は、影や光沢によって図形の一部が不明である場合や、オブジェクト間の重なり（前後関係）によって図形の一部が抽出できないことが多い。
このような応用に適用するためにも微妙な形状指定が可能で、部分的な形状情報だけでも検索が可能なシステムが求められている。
【００１１】
本発明は、上記の点に鑑みなされたもので、ヒストグラムが図形の形状を直感的に表現することが可能であり、より精度の高い類似図形の検索が可能な形状情報のヒストグラム化方法を提供することを目的とする。
更なる本発明の目的は、回転した図形に対してもマッチングを容易に行うことが可能な形状情報のヒストグラム化方法を提供することである。
【００１２】
更なる本発明の目的は、塗りつぶせない領域が発生した場合に、内部に空間を持つ図形についてもヒストグラム化を可能とする形状情報のヒストグラム化方法を提供することである。
更なる本発明の目的は、より柔軟な部分的な形状に対する類似検索手法及び装置を与えることが可能な部分形状情報による検索方法、装置及び部分形状情報による検索プログラムを格納した記憶媒体を提供することである。
【００１３】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
本発明は、画像情報の特徴量をヒストグラム（または、ベクトル）化し、該ヒストグラム同士を比較することで、類似像を検索するシステムにおける形状情報のヒストグラム化方法において、
画像情報から形状の特徴量を得る場合に、
特定の基準に基づいた円を描き（ステップ１）、
円の円周上の各点Ｘｉから中心に向かった直線を描き（ステップ２）、
直線が図形と最初にぶつかった地点をＺｉとし（ステップ３）、
または、直線が中心までに図形とぶつからない場合には円の中心をＺｉとし（ステップ４）、
点Ｘｉと地点Ｚｉとの距離をＤとし（ステップ５）、
各点Ｘｉにおけるヒストグラム値を距離Ｄとし（ステップ６）、
各点Ｘｉと地点Ｚｉの間を塗りつぶし、
塗りつぶせない領域が発生した場合には、
再度外周点から塗りつぶせなかった領域をヒストグラム化する処理を行い、
塗りつぶせなかった領域をヒストグラム化する処理を特定の回数または、塗りつぶせない領域が存在しなくなるまで繰り返す。
【００１９】
本発明は、利用者からの検索キー図形入力を行い、入力された該図形の特徴量のヒストグラム（または、ベクトル）として抽出し、該ヒストグラムとデータベース中のヒストグラム間の類似度の計算を行うことで、キー図形に近い図形の検索結果を返す部分形状情報による検索方法において、
検索キー図形の入力を行う際に、円で入力領域を制限し、
利用者は、入力領域を検索対象図形の重心を中心とする外接円、または、最小外接円とみなしたときの検索対象図形の一部分の形状を指定し、
入力された部分形状から外接円を使った形状のヒストグラム方法により、部分形状が指定された部分では、該部分形状の情報をヒストグラム化し、該部分形状が指定されなかった部分では、例外値を取るヒストグラムとし、
ヒストグラム内の例外値でない部分を検索キーとして、
データベース内のヒストグラムと最も類似する部分の検出を行い、
類似形状を検索する。
【００２０】
また、本発明の部分形状情報による検索方法は、利用者が部分図形がどの角度の範囲に存在するかを指定すると、指定された角度の範囲に対応するヒストグラムの部分に限定して、ヒストグラム内の例外値でない部分を検索キーとし、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する。
【００２１】
また、本発明の部分形状情報による検索方法は、部分形状の入力を受け付けると、利用者は、１つの検索対象図形の複数の部分形状の指定を行い、複数の図形間の角度の許容範囲の入力を行い、指定された角度の範囲の入力を行い、指定された角度範囲に対応するヒストグラムの部分に限定して、該ヒストグラム内の例外値でない部分を検索キーとし、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する。
【００２２】
また、本発明は、利用者からの検索キー図形の入力を行うキー図形入力手段と、該キー図形入力手段によって入力された図形の特徴量をヒストグラム（または、ベクトル）として抽出するヒストグラム作成手段と、該ヒストグラムとデータベース中に格納されているヒストグラム間の類似度計算を行うことで、検索キー図形に近い図形の検索結果を返す類似度算出手段とを有する部分形状情報による検索装置であって、
キー図形入力手段は、
円で入力領域を制限した部分キー図形の入力を行う部分キー図形入力手段と、利用者から入力領域を検索対象図形の重心を中心とする外接円、または、最小外接円とみなしたときの検索対象図形の一部分の形状を指定する部分形状入力手段を含み、
ヒストグラム作成手段は、
外接円を用いた形状のヒストグラム化方法を用いて、部分形状が指定された部分では、該部分形状の情報をヒストグラム化し、該部分形状が指定されなかった部分では、例外値をとるヒストグラムとする部分形状情報ヒストグラム化手段を含み、
類似度算出手段は、
ヒストグラム内の例外値でない部分を検索キーとして、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する部分的類似度算出手段を含む。
【００２３】
また、上記の部分形状入力手段は、利用者により指定された部分図形がどの角度の範囲に存在するかの指定を行う角度入力手段を含み、
部分的類似度算出手段は、角度入力手段により指定された角度の範囲に対応するヒストグラムの部分に限定して該ヒストグラム内の例外値でない部分を検索キー図形とし、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する限定部分的類似度算出手段を含む。
【００２４】
また、上記の部分形状入力手段は、複数の部分形状の入力を受け付け、利用者は、１つの検索対象図形の複数の部分形状の指定を行う部分形状指定手段を含み、
部分的類似度算出手段は、角度入力手段で指定された角度の範囲に対応するヒストグラムの部分に限定して、該ヒストグラム内の例外値でない部分を検索キー図形とし、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する検索キー設定手段を含む。
【００２５】
本発明は、利用者からの検索キー図形の入力を受け付けるキー図形入力ステップと、該キー図形入力ステップによって入力された図形の特徴量をヒストグラム（または、ベクトル）として抽出するヒストグラム作成ステップと、該ヒストグラムとデータベース中に格納されているヒストグラム間の類似度計算を行うことで、検索キー図形に近い図形の検索結果を返す類似度算出ステップとを実行する部分形状情報による検索プログラムを格納した記憶媒体であって、
キー図形入力ステップは、
円で入力領域を制限した部分キー図形の入力を受け取る部分キー図形入力ステップと、
利用者から、入力領域を検索対象図形の重心を中心とする外接円、または、最小外接円とみなしたときの検索対象図形の一部分の形状の指定を取得する部分形状入力ステップと、を実行し、
ヒストグラム作成ステップは、
外接円を用いた形状のヒストグラム化方法を用いて、部分形状が指定された部分では、該部分形状の情報をヒストグラム化し、該部分形状が指定されなかった部分では、例外値をとるヒストグラムとする部分形状情報ヒストグラム化ステップを実行し、
類似度算出ステップは、
ヒストグラム内の例外値でない部分を検索キー図形として、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する部分的類似度算出ステップを実行するプログラムを格納する。
【００２６】
上記の部分形状入力ステップは、
利用者により指定された部分図形がどの角度の範囲に存在するかの指定を受け取る角度入力ステップを実行し、
部分類似度算出ステップは、
角度入力ステップにより指定された角度の範囲に対応するヒストグラムの部分に限定して該ヒストグラム内の例外値でない部分を検索キー図形とし、データベース内のヒストグラム内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する限定部分的類似度算出ステップを実行する。
【００２７】
また、上記の部分形状入力ステップは、
複数の部分形状の入力を受け付け、利用者からの１つの検索対象図形の複数の部分形状の指定を受け取る部分形状指定ステップを実行し、
部分的類似度算出ステップは、
角度入力ステップで指定された角度の範囲に対応するヒストグラムの部分に限定して、該ヒストグラム内の例外値でない部分を検索キーとし、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索する検索キー設定ステップを実行する。
【００２８】
上記のように、画像情報の特徴量をヒストグラム（または、ベクトル）化し、そのヒストグラム同士を比較することで類似画像を検索するシステム内のその形状情報をヒストグラム化する部分について、画像情報からの形状の特徴量を得る場合に、特定の基準に基づいた円を描き、その円周上の各点Ｘi から中心に向かった直線を描きその直線が図形と最初にぶつかった地点をＺi とし、または、その直線が中心までに図形とぶつからない場合には、円の中心をＺi とし、ＤをＸi とＺi との距離とし、各点Ｘi におけるヒストグラム値をＤとすることで、直感的に優れた形状情報のヒストグラムが得られる。
【００２９】
さらに、本発明は、各Ｘi とＺi の間を塗りつぶし、塗りつぶせない領域が発生した場合には、再度外周点から塗りつぶせなかった領域をヒストグラム化する処理を行い、これを特定の回数または、塗りつぶせない領域が存在しなくなるまで、実行することで内部空間を持つ図形に対しても、その形状情報のヒストグラム化が可能となる。
【００３０】
なお、特定の基準に基づいた円として、想定する円を円の中心を図形の重心とし、円の半径を重心から最も遠い図形内の点と中心との距離とした場合と、想定する円を円の中心を図形の最小外接円とし、円の半径をその最小外接円の半径とした場合には、円の基準として、数学的に安定した基盤を与えることができ、多くのシステムで共通に利用する基準として有効である。
【００３１】
また、距離の基準を距離を円周上の点からＺi までの距離ではなく、中心からＺi までの距離とした場合は、全く同等の効果を持ち、距離を半径Ｒで正規化した（距離をＲで割った）距離を利用する場合は、距離基準としてユークリット距離以外を用いた場合に有効になる。例えば、距離基準として、画素数（コンピュータ画面上でのドット数）とした場合、半径距離が直線の角度によって変化してくる。
【００３２】
その場合、半径で正規化することで他の角度の距離との比較が可能になり、距離として画素数を用いることで、コンピュータ上での計算処理が容易になる。
さらに、生成されたヒストグラムについて、最も値の大きな位置、または、小さな位置Ｘi に着目し、その位置が定位置（例えば、先頭）にくるようにヒストグラムを巡回させ、ヒストグラムの図形の回転に対する正規化を行う仮定を持つことで回転した図形に対しても同一のヒストグラムを得ることが可能になり、検索システムの性能が向上できる。
【００３３】
なお、外周上の点からの直線が図形と最初にぶつかった地点をＺi とし、または、その直線が中心までに図形とぶつかった場合には、さらに、延長した直線上で図形と最初にぶつかった地点をＺi とし、もし、それでも図形にぶつからなければ中心から見てＸi の反対側の円周上の点をＺi とすることでも可能であり、この場合、図形内部に関する１回で取得できる情報量が若干増加する。
【００３４】
また、予め、等間隔にとった外周上の点からヒストグラムを作成するだけでなく、外周の全点（コンピュータ上で認識可能な全点）についてヒストグラムを作成し、最後にメディアン方などでヒストグラムの階数を調整することも可能であり、この場合には、外周上の点が飛ぶ（点と点との間隔があく）ことにより情報の欠陥を防ぐことが可能となる。
【００３５】
更に、本発明の部分形状情報による類似図形を検索する際に、図形の部分的な形状特徴を指定することにより、検索図形の検索が可能となる。
また、形状の指定は、部分的な図形を指定することにより、微妙なニュアンスの指定が可能となり、特徴的な部分が複数ある場合には、それらの形状の指定や、形状間の位置関係の指定等を行うことにより類似する図形の検索が可能となる。
【００３６】
【発明の実施の形態】
図２は、本発明の画像情報から形状の特徴量を得るための処理のフローチャートである。
ステップ１０１）  特定の基準に基づいた円（中心位置Ｙ，半径Ｒ）を描く。
ステップ１０２）  ステップ１０１で描いた円の円周上の各点Ｘi について以下の処理を繰り返す。
【００３７】
ステップ１０３）  Ｘi と円の中心Ｙを結ぶ直線上でＸi から見て、初めて図形に接した地点をＺi とする。図形に接しなければ、中心または反対側の外周点をＺi とする。
ステップ１０４）  Ｘi とＺi との距離をＡとする。
ステップ１０５）  点Ｘi におけるヒストグラム値をＡとし、追加出力し、ステップ１０２に移行する。
【００３８】
図３は、本発明の塗りつぶせない領域が発生した場合の処理のフローチャートである。
ステップ２０１）  特定の基準に基づいた円（中心位置Ｙ、半径Ｒ）を描く。
ステップ２０２）  ステップ２０１で描いた円の円周上の各点Ｘi について以下の処理を繰り返し、全てのＸi についての処理が終了したらステップ２０６に移行する。
【００３９】
ステップ２０３）  点Ｘi と円の中心Ｙを結ぶ直線上で、Ｘi から見て、初めて図形に接した地点をＺi とする図形に接しなければ、中心または反対側の外周点をＺi とする。
ステップ２０４）  点Ｘi とＺi との距離をＡとする。
ステップ２０５）  点Ｘi におけるヒストグラム値をＡとし、追加出力し、ステップ２０２に移行する。
【００４０】
ステップ２０６）  各点Ｘi とＺi の間の領域は塗りつぶし、残った領域を図形と見做す。
ステップ２０７）  残った領域がなければ終了する。
ステップ２０８）  形状内部情報のヒストグラム化を行うために処理を繰り返す。
【００４１】
図４は、本発明の類似画像検索システムの構成例を示す。
同図に示す類似画像検索システム１００は、利用者から検索キー図形の入力を行うキー図形の入力部１１０、登録データ画像の入力部１２０、画像からの図形の抽出部１３０、図形の特徴量をヒストグラム（または、ベクトル）として抽出する図形情報のヒストグラム作成部１４０、図形とベクトルの組の管理部１５０、ヒストグラムとデータベース中のヒストグラム間の類似度計算を行うヒストグラム間の類似度算出部１６０、類似度によりキー図形に近い図形を検索する類似図形を含む画像の検索部１７０、類似画像の出力部１８０及び類似図形の出力部１９０から構成される。
【００４２】
キー図形の入力部１１０は、部分キー図形の入力部１１１と角度の入力部１１２とを有する。
部分キー図形入力部１１１は、円で入力領域を制限する。具体的には、利用者が円で制限した入力領域を検索対象図形の重心を中心とする外接円、または、最小外接円とみなしたときの検索対象図形の一部分の形状等の指定を取得する。また、部分キー図形入力部１１１は、複数の部分図形の入力を受け付け、利用者からの１つの検索対象図形の複数の部分形状の指定を受け付ける。
【００４３】
角度の入力部１１２は、利用者が部分キー図形入力部１１１で指定した部分図形がどの角度の範囲に存在するかを指定する。また、角度の入力部１１２は、複数の図形間の角度の許容範囲の入力も行う。
図形のヒストグラム（または、ベクトル）作成部１４０は、部分図形情報のヒストグラム作成部１４１を有する。部分図形情報のヒストグラム作成部１４１は、前述の外接円を用いた形状のヒストグラム方法を用いて、部分形状が指定された部分では、その形状の情報をヒストグラム化し、部分形状が指定されなかった部分では、例外値をとるヒストグラムとする。
【００４４】
ヒストグラム間の部分的類似度算出部１６０は、ヒストグラム間の部分的類似度算出部１６１を有する。部分的類似度算出部１６１は、ヒストグラム内の例外値でない部分を検索キーとし、データベース内のヒストグラムと最も類似する部分の検出を行い、その結果を類似度図形を含む画像の検索部１７０及び類似図形出力部１９０に転送する。また、部分的類似度算出部１６１は、角度の入力部１１２により指定された角度範囲に対応するヒストグラムの部分に限定して、ヒストグラム内の例外値でない部分を検索キーとし、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形の出力部１９０及び類似図形を含む画像の検索部１７０に転送する。さらに、部分的類似度算出部１６１は、角度の入力部１１２により取得した角度範囲に対応するヒストグラムの部分に限定してヒストグラム内の例外値でない部分を検索キーとし、データベース内のヒストグラムと最も類似する部分の検出を行い、類似図形を検索して、類似図形の出力部１９０、及び類似図形を含む画像の検索部１７０に転送する。
【００４５】
図５は、本発明の部分形状情報による検索方法を示すフローチャートである。
ステップ３０１）  利用者は、キー図形の入力部１１０の部分キー図形の入力部１１１より円で制限した入力域を経由し、部分図形を入力する。
ステップ３０２）  ステップ３０１の処理を部分図形の個数だけ繰り返す。
ステップ３０３）  全ての部分図形の個数分の入力が終了したら、角度の入力部１１２より部分図形の角度の許容範囲の入力を行う、または、この入力を行わない場合にはスキップする。
【００４６】
ステップ３０４）  角度の入力部１１２から複数の部分図形間の角度の許容範囲の入力を行う、または、この入力を行わない場合にはスキップする。
ステップ３０５）  外接円の各点について以下の処理を繰り返し、全ての外接円の各点の処理が終了したらステップ３０９に移行する。
ステップ３０６）  解錠が指定された部分かを判定し、そうであれば、ステップ３０７に移行し、そうでない場合にはステップ３０８に移行する。
【００４７】
ステップ３０７）  図形情報のヒストグラム作成部１４０は、外接円を使った形状のヒストグラムを作成する。
ステップ３０８）  ヒストグラム値として例外値を指定する。
ステップ３０９）  角度の範囲指定が行われている場合には、ステップ３１１に移行し、行われていない場合にはステップ３１０に移行する。
【００４８】
ステップ３１０）  ヒストグラム間の類似度算出部１６０は、ヒストグラム内の例外値でない部分のみを対象としてデータベース（図形とベクトルの組の管理部）１５０内のヒストグラムとの類似度を算出し、ステップ３１４に移行する。
ステップ３１１）  角度からヒストグラムの範囲を算出する。
ステップ３１２）  ヒストグラムの範囲について、比較起点をずらしながら以下のステップを繰り返し、範囲内の全ての起点における処理が終了したらステップ３１４に移行する。
【００４９】
ステップ３１３）  ヒストグラム内の例外値でない部分のみを対象として、データベース１５０内のヒストグラムとの類似度を計算する。
ステップ３１４）  類似図形の出力部１９０は、類似度の高い順に出力する。
【００５０】
【実施例】
以下、図面と共に本発明の実施例を説明する。
［形状情報のヒストグラム化の実施例］
最初に、形状情報のヒストグラム化に関する実施例について説明する。
まず、従来の技術の項で説明した図形に対して、図形の外側に円を描いた例を図６は、本発明の形状情報のヒストグラム化の一実施例の画像情報から形状の特徴量を得る過程を示す図（その１）である。
【００５１】
同図（Ａ）は図形の外側に円を描いた例であり、同図（Ｂ）は、図形の重心を中心として最も遠い点を半径Ｒとして外円を描いた例であり、同図（Ｃ）は、図形に外接する最小の円を描いた例である。
図６に示すこの（Ａ）〜（Ｃ）の過程において、図形の重心を求め、図形の外周をトレースすることで図形の重心を中心として最も遠い点を求め、図形の最大長（点Ａ，Ｂ）を求め、それと外周トレース点との作る角度の中で最小の角度の点Ｃを求め、その角度が鋭角の場合には、最大長の点と点Ｃから外接円を求め、その角度が鈍角の場合には、点Ａ，Ｂを直径とする円を外接円とすることが可能であり、容易に実装可能である。
【００５２】
さらに、別の図形について説明する。
図７は、本発明の形状情報のヒストグラム化の一実施例の画像情報から形状の特徴量を得る過程を示す図（その２）である。
同図（Ａ）は図形の外側に円を描いた例であり、同図（Ｂ）は、図形の重心を中心として最も遠い点を半径Ｒとして外円を描いた例であり、同図（Ｃ）は、図形に外接する最小の円を描いた例である。なお、重心は同図（Ｂ）において白丸で示した。
【００５３】
図７において、円周を１６分割した各点Ｘi に対し、その点から中心に向かう直線を引いた例を図８に示す。同図において、Ｘi から中心に向かう直線を引いた場合に、外円の取り方によってヒストグラムは変化する。この時、図形に最初にぶつかった地点で直線を止めておく。この地点をＺｉとする。そして、図８（Ａ）に対し、その各直線の長さをヒストグラム化した例を図９に示し、図形のＸi とＺi の間の領域を塗りつぶした状態を図７に示す。但し、図９、図１０では、分かり易さのために、外周上の１６点ではなく、識別可能な全点を対象として塗りつぶしている。図１０では、残った領域、ヒストグラムに反映されなかった内部領域が存在することを示している。
【００５４】
そこで当該内部領域に対して、再度ヒストグラム化を行うために、外周から直線を引いた状態を図１１に示す。同図からヒストグラムを求め、先程のヒストグラムとあわせれば、内部状態をも表現したヒストグラムとなる。
さらに、この２回目のヒストグラム過程でも、領域が残れば、その領域が無くなるまで、このヒストグラム化の過程を繰り返すことができる。
【００５５】
また、図１１に対するヒストグラムを回転に対する巡回によって正規化する例を図１２に示す。この例では、ヒストグラム中の最小の値の地点に注目し、その地点がヒストグラムの先頭にくるように巡回させて正規化している。この正規化によって、図９の図形は図１２内の図形のように正規化されたことになり、回転した図形に対してもヒストグラムが一致するようになる。
【００５６】
［部分形状情報による検索の実施例］
・第１の実施例
図１３は、本発明の部分形状情報による検索の第１の実施例の部分的な図形に対するヒストグラムの作成及び検索の例を示す。
同図（Ａ）は、図形全体が指定された場合のヒストグラムである。一方、同図（Ｂ）は図形の一部のみが指定された場合のヒストグラムの例である。同図（Ｂ）に示す図形が指定されていない部分ｂ５〜ｂ１５については例外値として最大値をとっているが、例えば、負の値などでも構わない。
【００５７】
次に、検索の例を示す。
データベース内に格納されている図形に対しては、全体のヒストグラムが作成されており、キー図形に対しては、部分的なヒストグラムが作成される。
図１３（Ａ）をデータベース内図形のヒストグラム、図１３（Ｂ）をキー図形ヒストグラムとすると、キー図形内の例外値でない部分ｂ１〜ｂ４について対応するａ１〜ａ５に対して類似度の算出を行う。
【００５８】
例えば、類似度をユークリッド距離Ｌａとし、ｓｑｒｌ（ｋ）をｋの平方根とした場合、
Ｌａ＝ｓｑｒｌ（（ｂ１−ａ１）* （ｂ１−ａ１）＋（ｂ２−ａ２）* （ｂ２−ａ２）＋（ｂ３−ａ３）* （ｂ３−ａ３）＋（ｂ４−ａ４）* （ｂ−ａ４））
が類似度算出の式となり、この場合Ｌａの値は０となる（ユークリッド距離の場合、小さい程類似度が高い）。
【００５９】
次に、入力時に角度の指定があった場合の検索の例を示す。
再びキー図形を図１３（Ｂ）とし、その角度の許容範囲として円の右側に存在するとの指定があった場合、図１３（Ａ）のデータベース内の図形のヒストグラムとの比較は、比較の始点を０度〜１８０度分変えながら行う。この場合、円を１６等分してヒストグラム化しているので、１８０度は９本のヒストグラムとなり、キー図形が４本のヒストグラムで表現されているので、６回の比較が必要となる。つまり、以下のそれぞれの類似度を求め、
Ｌ０＝ｓｑｒｔ（（ｂ１−ａ１）・（ｂ１−ａ１）＋（ｂ２−ａ２）・（ｂ２−ａ２）＋（ｂ３−ａ３）・（ｂ３−ａ３）＋（ｂ４−ａ４）* （ｂ４−ａ４））
Ｌ１＝ｓｑｒｔ（（ｂ１−ａ２）・（ｂ１−ａ２）＋（ｂ２−ａ３）・（ｂ２−ａ３）＋（ｂ３−ａ４）・（ｂ３−ａ４）＋（ｂ４−ａ５）* （ｂ４−ａ５））
Ｌ２＝ｓｑｒｔ（（ｂ１−ａ３）・（ｂ１−ａ３）＋（ｂ２−ａ４）・（ｂ２−ａ４）＋（ｂ３−ａ５）・（ｂ３−ａ５）＋（ｂ４−ａ６）* （ｂ４−ａ６））
Ｌ３＝ｓｑｒｔ（（ｂ１−ａ４）・（ｂ１−ａ４）＋（ｂ２−ａ５）・（ｂ２−ａ５）＋（ｂ３−ａ６）・（ｂ３−ａ６）＋（ｂ４−ａ７）* （ｂ４−ａ７））
Ｌ４＝ｓｑｒｔ（（ｂ１−ａ５）・（ｂ１−ａ５）＋（ｂ２−ａ６）・（ｂ２−ａ６）＋（ｂ３−ａ７）・（ｂ３−ａ７）＋（ｂ４−ａ８）* （ｂ４−ａ８））
Ｌ５＝ｓｑｒｔ（（ｂ１−ａ６）・（ｂ１−ａ６）＋（ｂ２−ａ７）・（ｂ２−ａ７）＋（ｂ３−ａ８）・（ｂ３−ａ８）＋（ｂ４−ａ９）* （ｂ４−ａ９））
その中の最小値をそのデータベース内図形の最大の類似度とする。これを他のデータベース内の図形についても行い、最大の類似度の図形から順に出力する。
・第２の実施例
本実施例では、図形の部分的な特徴を指定した場合の検索例を示す。
【００６０】
図１４は、本発明の部分形状による第２の実施例の検索キー（部分形状）の指定の例を示す。
図１４において、（ｈ）をキー指定すると、そのヒストグラム形状は、例えば、図２０（ａ）〜（ｆ）の耳の部分のヒストグラムや、（ｇ）の頭の部分のヒストグラムが近いので、類似度の高いものとなる。
【００６１】
また、図１４（ｈ）と共にその角度を±５度以内と指定すると、図１６の（ａ），（ｅ）〜（ｇ）の最も類似度の高い部分との角度が±５度を越えるので、検索結果から除かれる。
なお、この結果は、角度の入力のＧＵＩには影響されず、テキスト入力であってもスライダ入力方法であっても構わない。
【００６２】
また、従来では区別しにくかった微妙な違いの指定も可能になる。
図１４（ｈ）を指定した場合、図２０の（ｃ）〜（ｅ）が最も類似度が高くなる。また、図１４（ｉ）を指定した場合、図２０の（ａ）が最も類似度が高くなる。
・第３の実施例
本実施例では、図形の部分的な特徴を複数指定した場合の検索例を示す。
【００６３】
図１４の（ｊ）のような指定をし、その２つの図形間の角度の許容度を図１４の（ｊ）〜（ｋ）まで許すとした場合、図２０（ｃ）〜（ｆ）までが適合する。（ａ），（ｂ）は、間が狭過ぎるために適合せず、（ｇ）は間が広過ぎるために適合しない。
上記では、指定が２つの場合を示したが、３つ以上の場合についても同様である。
【００６４】
角度の指定方法については、指定対象図形の選択方法として最近傍の図形間の許容度を指定する場合と、最遠の図形間の許容度を指定する場合があり、図形内の基準点としては、最近点（図１４（ｊ）の耳の頭初）、中心点、最遠点（図１４）（ｊ）の耳の下側）などがあるが、いずれでもよい。
さらに、図１４（ｌ）に示すように、検索キー図形が内部形状を持つ場合については、前述の形状情報のヒストグラム化方法に示したように、図形内部の情報のヒストグラム化も行っておけば同様に実現可能である。
【００６５】
この場合、図２０（ａ），（ｄ），（ｅ）等の類似度が他に比べて高くなる。
なお、角度が指定されない場合とは、キー図形の角度のみを有効とする場合で、角度を無視する（＝回転に対する正規化を行う）場合は、角度を０〜３６０度と指定した場合と考える。
なお、上記の部分形状情報による検索については、図４に示す構成について図５に示すフローチャートに沿ったプログラムを構築し、当該プログラムを類似画像を検索するためのコンピュータに接続されるディスク装置等の記憶媒体に格納しておき、類似画像検索処理時に適宜呼び出して実行することも可能である。
【００６６】
また、上記のプログラムをフロッピーディスクやＣＤ−ＲＯＭ等の可搬記憶媒体に格納することも可能である。
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内で種々変更・応用が可能となる。
【００６７】
【発明の効果】
上述のように、本発明によれば、図形の外部の円周上から図形への距離をヒストグラムとすることで、ヒストグラムは図形の形状を直観的に表現するものとなる。
さらに、ヒストグラムの回転による正規化を行うことが、回転した図形に対してのマッチングを容易に行うことができる。
【００６８】
また、塗りつぶせない領域が発生した場合に、再度外周点から塗りつぶせなかった領域への距離をヒストグラムとし、これを何回かまたは塗りつぶせない領域が存在しなくなるまで実行することで、内部に空間を持つ図形についてもヒストグラム化が可能になる。
これらにより、従来のエッジ方向や４方向からの距離を使った形状に関する類似図形検索システムに比べ、より精度の高い類似図形の検索が可能になる。
【００６９】
また、本発明の部分形状による類似画像検索によれば、図形の部分的な形状特徴を指定することにより、図形検索が可能となる。その形状の指定は、従来に比べて微妙なニュアンスの指定が可能となる。さらに、特徴的な部分が複数あれば、それらの形状の指定とその形状間の位置関係について指定による検索も可能になる。
【００７０】
また、本発明を他の特徴（色調、テクスチャ、大きさ、位置、向き、等）の情報を組み合わせて指定すれば、より多様な検索が可能になる。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の画像情報から形状の特徴量を得るための処理のフローチャートである。
【図３】本発明の塗りつぶせない領域が発生した場合の処理のフローチャートである。
【図４】本発明の類似画像検索システムの例を示す図である。
【図５】本発明の部分形状情報による検索方法を示すフローチャートである。
【図６】本発明の形状情報のヒストグラム化の一実施例の画像情報から形状の特徴量を得る過程を示す図（その１）である。
【図７】本発明の形状情報のヒストグラム化の一実施例の画像情報から形状の特徴量を得る過程を示す図（その２）である。
【図８】本発明の形状情報のヒストグラム化の一実施例の図７における例の円周を１６分割した点に対して中心に向かって直線を引いた例である。
【図９】本発明の形状情報のヒストグラム化の一実施例の円周上の各点から中心に向かう直線上で最初に図形と接した点までの距離をヒストグラムにする例である。
【図１０】本発明の形状情報のヒストグラム化の一実施例の外周上の点と図形または、中心までの間を塗りつぶした例である。
【図１１】本発明の形状情報のヒストグラム化の一実施例の残った領域に対して再度外周上の各点から直線を引いた例である。
【図１２】本発明の形状情報のヒストグラム化の一実施例のヒストグラムを最長値が先頭に来るように巡回させた例である。
【図１３】本発明の部分形状による第１の実施例の部分的なヒストグラムの作成及び検索の例を示す図である。
【図１４】本発明の部分形状による第２の実施例の検索キー（部分形状）の指定の例である。
【図１５】従来の色情報をヒストグラム化する例である。
【図１６】従来の色情報をヒストグラム化する例である。
【図１７】従来のエッジ方向をヒストグラムにする例である。
【図１８】従来の４辺から図形までの距離をヒストグラムにする例である。
【図１９】従来の画像検索システムの例である。
【図２０】微妙な図形の差の例である。
【符号の説明】
１００  類似画像検索システム
１１０  キー図形の入力部
１１１  部分キー図形の入力部
１１２  角度の入力部
１２０  登録データ画像の入力部
１３０  画像からの図形の抽出部
１４０  図形情報のヒストグラム（または、ベクトル）作成部
１４１  部分図形情報のヒストグラム作成部
１５０  図形とベクトルの組の管理部（データベース）
１６０  ヒストグラム間の類似度（または、ベクトル間の距離）算出部
１６１  ヒストグラム間の部分的類似度算出部
１７０  類似図形を含む画像の検索部
１８０  類似画像の出力部
１９０  類似図形の出力部
【図１】
0003539139.tif 000002
【図２】
0003539139.tif 000003
【図３】
0003539139.tif 000004
【図４】
0003539139.tif 000005
【図５】
0003539139.tif 000006
【図６】
0003539139.tif 000007
【図７】
0003539139.tif 000008
【図８】
0003539139.tif 000009
【図９】
0003539139.tif 000010
【図１０】
0003539139.tif 000011
【図１１】
0003539139.tif 000012
【図１２】
0003539139.tif 000013
【図１３】
0003539139.tif 000014
【図１４】
0003539139.tif 000015
【図１５】
0003539139.tif 000016
【図１６】
0003539139.tif 000017
【図１７】
0003539139.tif 000018
【図１８】
0003539139.tif 000019
【図１９】
0003539139.tif 000020
【図２０】
0003539139.tif 000021