画像検索装置、画像検索装置のデータ処理方法、および画像検索システム
【課題】効率よく高精度な画像検索が可能な画像検索装置、画像検索装置のデータ処理方法、および画像検索システムを提供する。
【解決手段】画像検索装置１００は、検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶部１０２と、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出する構成直線候補抽出部１０４と、構成直線候補抽出部１０４で抽出した構成直線の組合せ候補情報とクエリーなす角度情報とから、形状間距離を算出する形状間距離算出部１０６と、を備える。
【解決手段】画像検索装置１００は、検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶部１０２と、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出する構成直線候補抽出部１０４と、構成直線候補抽出部１０４で抽出した構成直線の組合せ候補情報とクエリーなす角度情報とから、形状間距離を算出する形状間距離算出部１０６と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像検索装置、画像検索装置のデータ処理方法、および画像検索システムに関し、特に、形状情報をクエリーとした画像検索装置、画像検索装置のデータ処理方法、および画像検索システムに関する。
【背景技術】
【０００２】
ユーザの指定するクエリー形状による画像検索を実現するためには、ユーザが指定するクエリー形状と、検索対象画像中の形状に関する類似度を算出する必要がある。
検索時に高速に照合するためには、検索対象画像群からあらかじめ特徴量を抽出しておく必要がある。画像全面が検索対象の場合は画像全体から特徴量を抽出すればよいが、画像の一部であるオブジェクトが検索対象となる場合、検索対象画像から該当する領域の特徴量を抽出する必要がある。
【０００３】
図１７は、形状をクエリーとした画像検索方法の一例を説明する図である。ユーザは検索したい形状をクエリー形状として入力すると、類似形状を含む画像が検索結果として出力される。
画像検索装置の例が以下の各特許文献に記載されている。
特許文献１に記載された画像検索装置は、ユーザが選択した検索対象となるクエリーの形状及び色特徴および検索対象となる位置を取得し、検索対象画像群の画像の中から、探索窓を走査して類似する領域を探索し、類似画像を抽出する。
【０００４】
特許文献２に記載された画像検索装置は、検索対象画像に含まれる主要な形状（たとえば、円形、三角形、または四角形など）の種類を予め決定し、登録しておくことで、ユーザが与える特定のオブジェクトの形状の種類をクエリーとし検索する。
【０００５】
特許文献３に記載された画像検索装置は、検索対象画像から予め注目領域を自動で抽出し、クエリー領域との類似度を判定している。
特許文献４に記載された直線による画像の検索装置は、検索対象画像に含まれる直線の特徴（始点、終点、重心、傾き、または長さ）を登録しておき、ユーザが与える直線情報と直線周辺の色などの類似度を算出し、検索する。連続する可能性のある直線を一直線とみなすことで、一部欠けのある直線も検索できる。
【０００６】
特許文献５に記載された画像特徴抽出装置は、画像中に含まれる直線の傾きを登録しておき、ユーザが与える画像内の直線情報との類似度を算出し検索する。また、特許文献６に記載された画像形成システムは、線分のなす角度を用いて形状の類似度を算出する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０００−７６３０２号公報
【特許文献２】特開２００９−１９３３９８号公報
【特許文献３】特開２００７−１９９７４９号公報
【特許文献４】特開２０００−８２０７５号公報
【特許文献５】特開平５−１３５１７４号公報
【特許文献６】特開２００６−２５２００７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述した従来のシステムでは、次のような問題があった。
特許文献１に記載の例での問題点は、探索窓を設定するためスケールや回転の影響を受けやすく、検索時に検索対象画像を探索し、特徴量を抽出するため非常に時間がかかることである。
特許文献２に記載の例での問題点は、ユーザが検索に用いるクエリー形状は多様であり、予め形状を規定することは困難である。また、その形状登録の自動化が困難であることである。
【０００９】
特許文献３に記載の例の問題点はユーザが所望する検索結果が出ないことである。その理由は、検索対象画像の注目領域は、支配的な単一色として抽出されており、ユーザの関心に関わらず固定されるが、クエリーとなる領域はユーザが自由に選択できるため、注目領域として選択されたものがユーザの意図と異なるためである。ユーザが関心を持つ注目領域は一定ではなく、検索目的などにより変化するため、予め検索対象画像から注目領域を決定することは非常に困難である。
【００１０】
特許文献４に記載の例での問題点は、画像中における直線位置や周辺色などの類似度を判定するため、特定の形状による検索は行えないことや、位置情報に依存するため回転に頑強ではないことである。
特許文献５に記載の例での問題点は、大きな角度の回転に頑強ではないことである。その理由は、メンバシップ関数の導入による吸収可能な回転ずれは小さな角度に限定され、４５度や９０度の回転には対応できないためである。また、画像全体の直線の傾きの集合を特徴量としているため、クエリーと類似する形状が画像の大部分を占める場合以外では、検索精度が落ちると考えられる。
【００１１】
また、特許文献６に記載の例での問題点は、線分のなす角度のみに基づく類似度であるため、たとえば、長方形と正方形など、いずれもなす角度が、９０度、９０度、９０度、９０度の場合、区別がつかない点である。
【００１２】
このように、形状による画像検索では、ユーザが検索に用いるクエリー形状が未知であるため、その多様性から予め決定しておくことは困難であり、また検索時に決定された形状の探索を行うのでは時間がかかりすぎる問題がある。特別な選択基準に基づき画像中の検索対象領域を自動抽出する方法では、選択基準が固定されているため、多様な形状に対応できない。検索対象画像群から直線成分を抽出して一致度を判定する方法があるものの、直線の傾きを用いているため、画像の回転に弱い問題がある。
【００１３】
本発明は上記事情に鑑みてなされたものであり、その目的とするところは、効率よく高精度な画像検索が可能な画像検索装置、画像検索装置のデータ処理方法、および画像検索システムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の第一の画像検索装置は、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
を備える。
【００１５】
本発明の第二の画像検索装置は、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得手段と、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出するなす角度情報算出手段と、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
前記なす角度情報算出手段で取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と、前記クエリー多角形情報取得手段で得た前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する形状間距離算出手段と、
を備える。
【００１６】
本発明の第１の画像検索装置のデータ処理方法は、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する。
【００１７】
本発明の第２の画像検索装置のデータ処理方法は、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得し、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出し、
取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した前記構成直線の組合せ候補情報と、得られた前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する。
【００１８】
本発明の画像検索システムは、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
算出された前記形状間距離をユーザに提示する提示手段と、
を備える。
【００１９】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【００２０】
また、本発明の各種の構成要素は、必ずしも個々に独立した存在である必要はなく、複数の構成要素が一個の部材として形成されていること、一つの構成要素が複数の部材で形成されていること、ある構成要素が他の構成要素の一部であること、ある構成要素の一部と他の構成要素の一部とが重複していること、等でもよい。
【００２１】
また、本発明のデータ処理方法またはコンピュータプログラムには複数の手順を順番に記載してあるが、その記載の順番は複数の手順を実行する順番を限定するものではない。このため、本発明のデータ処理方法およびコンピュータプログラムを実施するときには、その複数の手順の順番は内容的に支障しない範囲で変更することができる。
【００２２】
さらに、本発明のデータ処理方法またはコンピュータプログラムの複数の手順は個々に相違するタイミングで実行されることに限定されない。このため、ある手順の実行中に他の手順が発生すること、ある手順の実行タイミングと他の手順の実行タイミングとの一部ないし全部が重複していること、等でもよい。
【発明の効果】
【００２３】
本発明によれば、効率よく高精度な画像検索が可能な画像検索装置、画像検索装置のデータ処理方法、および画像検索システムが提供される。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図２】本発明の実施の形態に係る画像検索装置における検索対象画像から直線情報の抽出を説明するための図である。
【図３】本発明の実施の形態に係る画像検索装置の構成直線情報記憶部に記録される直線情報の例を示す図である。
【図４】本発明の実施の形態に係る画像検索装置の構成直線情報記憶部に記録される直線情報の例を示す図である。
【図５】本発明の実施の形態に係る画像検索装置における検索クエリーに対応する検索対象画像内の類似する図形の検索を説明するための図である。
【図６】本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。
【図７】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図８】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図９】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図１０】本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。
【図１１】本発明の実施の形態に係る画像検索装置の構成直線検出処理を説明するための図である。
【図１２】本発明の実施の形態に係る画像検索装置の検索結果表示画面の一例を示す図である。
【図１３】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図１４】本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。
【図１５】本発明の実施の形態に係る画像検索装置の２直線の交点座標の算出精度を説明するための図である。
【図１６】本発明の実施の形態に係る画像検索装置の検索対象画像の直線抽出における直線の角度パラメータ精度を説明するための図である。
【図１７】検索対象画像群からの検索クエリー形状を用いた画像検索を説明するための図である。
【発明を実施するための形態】
【００２５】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００２６】
（第１の実施の形態）
図１は、本発明の実施の形態に係る画像検索装置１００の構成を示す機能ブロック図である。
本実施形態の画像検索装置１００は、検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶部１０２と、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出する構成直線候補抽出部１０４と、構成直線候補抽出部１０４で抽出した構成直線の組合せ候補情報とクエリーなす角度情報とから、形状間距離を算出する形状間距離算出部１０６と、を備える。
【００２７】
詳細には、図１を参照すると、本発明の実施の形態の画像検索装置１００は、構成直線情報記憶部１０２と、構成直線候補抽出部１０４と、形状間距離算出部１０６と、を含む。
【００２８】
画像検索装置１００の各構成要素は、任意のコンピュータのＣＰＵ（Central Processing Unit）、メモリ、メモリにロードされた本図の構成要素を実現するプログラム、そのプログラムを格納するハードディスクなどの記憶ユニット、ネットワーク接続用インタフェースを中心にハードウェアとソフトウェアの任意の組合せによって実現される。そして、その実現方法、装置にはいろいろな変形例があることは、当業者には理解されるところである。以下説明する各図は、ハードウェア単位の構成ではなく、機能単位のブロックを示している。
【００２９】
具体的には、画像検索装置１００は、たとえば、図示しないＣＰＵやメモリ、ハードディスク、および通信装置を備え、キーボードやマウス等の入力装置やディスプレイやプリンタ等の出力装置と接続されるサーバコンピュータやパーソナルコンピュータ、またはそれらに相当する装置により実現することができる。そして、ＣＰＵが、ハードディスクに記憶されるプログラムをメモリに読み出して実行することにより、上記各ユニットの各機能を実現することができる。
なお、以下の各図において、本発明の本質に関わらない部分の構成については省略してあり、図示されていない。
【００３０】
構成直線情報記憶部１０２は、検索対象となる画像群から抽出した直線に関する情報を記憶する。
本発明では、検索対象となる画像とは、静止画像および動画像を含むことができる。
【００３１】
直線を抽出する方法は、特許文献４に記載されているハフ変換を用いるとよい。または、Ｈａｒｒｉｓ Ｃｏｒｎｅｒ Ｄｅｔｅｃｔｏｒ（シー． ハリス（C. Harris）、外１名、「ア コンバインド コーナー アンド エッジ デテクター（A combined corner and edge detector）」、第４回アルビービジョンカンファレンス予稿集（Proc. 4th Alvey Vision Conf.）、（英国）、ザ プレシー カンパニー ピーエルシー．（The Plessey Company plc.）、１９８８年８月、p.147-151）などのコーナー点検出により抽出した画像内のコーナー点の組合せのうち、点と点を結んだ直線上にエッジを有する画素が多数存在するものを直線として抽出してもよい。
このようにして抽出された直線における原点からの距離ρと直線へ引いた垂線の傾き角度θのペアを直線情報として構成直線情報記憶部１０２に記録する。
【００３２】
図２に、検索対象画像から直線情報を抽出する例を示す。
直線情報は、距離と傾き以外にも、直線の方程式ａｘ＋ｂｙ＋ｃ＝０の係数ａ、ｂ、およびｃを用いてもよく、また、コーナー点間の直線上のエッジ画素による直線検出では、容易に直線を線分として求めることができるため、線分の２つの端点の座標（ｘ１，ｙ１）および（ｘ２，ｙ２）を直線に関する情報として記憶してもよい。ただし、本発明では、なす角度を頻繁に利用するため、傾き角度θを記録しておくのが望ましい。
【００３３】
抽出した直線情報は、直線ごとのρ、θの値とし、図３に示すように記録する。このとき、後の処理を容易化するため、図４に示すように、直線同士の組合せに対する、角度の差を表す値を表として記録しておくとよい。このとき、全ての頂点が画像内に位置する多角形のみを検索対象とする場合は、画像範囲内で交差する直線の組のみを記録することで、処理量を削減することができる。
【００３４】
これらのデータはＣＤ−ＲＯＭ、ＤＶＤ−Ｒ、ハードディスク、メモリなどの記録媒体に一括または複数に分割して記憶する。記憶されているデータはＣＤ−ＲＯＭドライブなどの読み込み装置により単数または複数の媒体から読み込まれるか、あるいはネットワークインターフェースを通じてインターネットやＬＡＮ（Local Area Network）等のネットワークを介して取得することができる。
【００３５】
構成直線候補抽出部１０４は、ｎ角形の検索クエリーの多角形のなす角度θｑｉ（ここで、ｉ＝１〜ｎの自然数。）の情報１０を入力し、入力したクエリーなす角度と一致するなす角度を保有する可能性のある構成直線の候補を構成直線情報記憶部１０２から抽出し、その構成直線の候補に関する情報（対応する構成直線の候補情報１２）を出力する。
【００３６】
ここで、構成直線候補抽出部１０４に入力されるクエリーなす角度情報１０は、たとえば、ユーザが操作部を操作して指定した情報でよいし、予め準備された情報を記録媒体またはネットワークを介して他の装置から読み込んで入力した情報でもよく、特に限定されない。クエリーなす角度情報１０は、受付部（不図示）が受け付け、構成直線候補抽出部１０４および形状間距離算出部１０６に入力することができる。
【００３７】
構成直線情報記憶部１０２に記憶されている全てのＮ枚の画像中の画像ｊにおける構成直線がなす角度の個数をｍｊとし、画像ｊにおけるなす角度の集合を、以下の式（１）とする。
Ｇｊ＝｛θｊ１，θｊ２，・・・，θｊｍｊ｝ ・・・式（１）
このとき、検索クエリーのなす角度ｑ｛θｑ１，θｑ２，・・・，θｑｎ｝に対し、以下の式（２）となるｎ個の組合せを探索する。
θｑｉ＝θｊｋ ・・・式（２）
ただし、角度抽出の誤差などを考慮し、θａとθｂを同一とみなす条件として、閾値ｔｈを用いて、以下の式（３）とするとよい。
｜θａ−θｂ｜＜ｔｈ ・・・式（３）
【００３８】
検出したなす角度の順列から、クエリー形状の辺と対応する直線の順列を求め、各直線のθ、ρの値もしくは頂点位置などの構成直線の候補に関する情報を出力する。
【００３９】
図５の例では、θｑ１＝θｊ１、θｑ２＝θｊ２、θｑ３＝θｊ３となることから、θｑ１とθｑ２を両端に持つＬ１と、θｊ１とθｊ２を両端に持つＬ１’が対応する直線であることが判り、同様に、Ｌ２とＬ２’、Ｌ３とＬ３’がそれぞれ対応する直線であることが判る。
【００４０】
対応する直線の組の順列と、各直線の傾き角度θと距離ρなどの直線に関する情報を出力する。
形状間距離算出部１０６は、構成直線候補抽出部１０４で検出したクエリー形状の辺とそれに対応する直線候補を抽出した画像ごとに、形状間距離１４を算出し、出力する。
形状間距離とは、２つの形状の異なる度合いを表す尺度であり、形状間距離が小さいほど２つの形状は類似していることになり、大きいほど似ていないことになる。
【００４１】
なお、算出された形状間距離に基づき、検索クエリーとの類似性を判定する判定部（不図示）をさらに備えることもできる。
【００４２】
形状間距離の算出方法としては、クエリー形状のなす角度の順列ｑ｛θｑ１，θｑ２，・・・，θｑｎ｝と、検索対象画像ｊにおける直線群のなす角度の順列Ｇｊ’＝｛θｊ１，θｊ２，・・・，θｊｎ｝から、対応するなす角度の差の絶対値の和を距離ｄｊとして以下の式（４）により算出する。
ｄｊ＝Σ｜θｑｉ−θｊｉ｜ ・・・式（４）
ただし、ｉは１〜ｎの自然数。
これ以外にも、２乗和やより一般化したＬｐノルムなど、距離の公理を満たすものであればどのようなものを用いてもよい。
【００４３】
本実施形態では、この形状間距離を類似度の尺度として用いる。ただし、以下の説明では、形状間距離が小さいほど類似度が高くなることに注意を要する。もちろん、類似度の尺度として、形状間距離のかわりに、類似性を表す（類似度が高いほど大きくなる）指標を用いてもよい。例えば、１／（１＋ｄ）（ｄは距離）のような指標を用いてもよい。
この処理をすべての検索対象画像（ｊ＝１〜Ｎ）に対しておこない、算出した形状間距離ｄｊを出力する。
【００４４】
本実施形態の画像検索装置１００は、コンピュータプログラムに対応する各種の処理動作をＣＰＵが実行することにより、前述のような各種ユニットが各種機能として実現される。
【００４５】
本実施形態のコンピュータプログラムは、画像検索装置１００を実現させるためのコンピュータに、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出する手順、抽出した構成直線の組合せ候補情報とクエリーなす角度情報とから、形状間距離を算出する手順を実行させるように記述されている。
【００４６】
本実施形態のコンピュータプログラムは、コンピュータで読み取り可能な記憶媒体に記録されてもよい。記録媒体は特に限定されず、様々な形態のものが考えられる。また、プログラムは、記録媒体からコンピュータのメモリにロードされてもよいし、ネットワークを通じてコンピュータにダウンロードされ、メモリにロードされてもよい。
【００４７】
上述のような構成において、本実施の形態の画像検索装置１００によるデータ処理方法を以下に説明する。図６は、本実施形態の画像検索装置１００の動作の一例を示すフローチャートである。
【００４８】
本実施形態のデータ処理方法は、画像検索装置１００が、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出し（ステップＳ１０３、ステップＳ１０５）、抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する（ステップＳ１０７）。
【００４９】
このように構成された本実施形態の画像検索装置１００の動作について、図６を用いて以下に説明する。
図６は、本実施形態の画像検索装置１００の動作の一例を示すフローチャートである。
構成直線候補抽出部１０４にｎ角形の検索クエリーのクエリーなす角度情報１０が入力される（ステップＳ１０１）。
【００５０】
そして、構成直線候補抽出部１０４が、構成直線情報記憶部１０２を参照し、構成直線情報記憶部１０２に記憶されている全てのＮ枚の検索対象画像中の一つの画像ｊにおける構成直線を抽出し（ステップＳ１０３）、入力したクエリーなす角度と一致するなす角度を有する可能性のある構成直線の候補を抽出する（ステップＳ１０５）。ここでは、対応する直線の組の順列と、各直線の傾き角度θと距離ρなどの直線に関する情報を出力する。
【００５１】
そして、形状間距離算出部１０６が、構成直線候補抽出部１０４で検出したクエリー形状の辺とそれに対応する直線候補を抽出した画像ごとに、形状間距離１４を算出し、出力する（ステップＳ１０７）。これらの処理を構成直線情報記憶部１０２に記憶されている全ての検索対象画像について繰り返し行い（ステップＳ１０９のＮＯ）、すべての検索対象画像について処理が終了した場合（ステップＳ１０９のＹＥＳ）、本処理を終了する。このようにして、検索対象画像について、クエリー多角形との形状間距離が出力される。
【００５２】
以上、説明したように、本実施形態の画像検索装置１００によれば、検索時にクエリー形状と類似する形状を効率的に再構築することが可能となる。このため、検索ごとに検索対象画像から対象となる形状を抽出する必要が無いという効果がある。その理由は、予め検索対象となる検索対象画像について、形状の最小単位である直線情報を抽出してあるためである。また、形状構成成分を直線として記述するため、一部欠けや遮蔽などに頑強となるといった効果も奏する。
【００５３】
（第２の実施の形態）
次に、本発明の実施の形態に係る画像検索システムについて、図７を参照して詳細に説明する。図７は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。本実施形態に係る画像検索システムにおいて、画像検索装置２００は、上記実施の形態の画像検索装置１００とは、検索対象の画像の情報を記憶する点、または、検索結果をユーザに提示する点で相違する。図７を参照すると、本実施形態の画像検索装置２００は、図１の上記実施形態の画像検索装置１００の構成に加えて、検索対象画像情報記憶部２０２と、検索結果表示部２０４と、をさらに含む。
【００５４】
本実施形態の画像検索システムは、上記実施形態の画像検索装置１００の構成に加え、さらに、算出された形状間距離をユーザに提示する提示部（検索結果表示部２０４）を備える。本実施形態の画像検索システムにおいて、提示部は、画像検索装置２００とは異なる他の端末であってもよく、ネットワークなどを介して画像検索装置２００に接続可能な構成とすることができる。
【００５５】
具体的には、検索対象画像情報記憶部２０２は、構成直線情報記憶部１０２に記憶されている検索対象となってすべての画像に関する情報が記憶されている。記憶する情報として、画像のファイル名、サイズ、解像度、作成日、ダウンロードされた画像の場合はＵＲＬなどのほか、オリジナル画像やサムネイル画像などを含むことができる。これらの情報は、構成直線情報記憶部１０２の情報と１対１に対応して記録してもよいが、記憶する容量を削減するため複数の「構成直線情報記憶部１０２に記憶されている情報を抽出した画像」に対し、１つの情報を割り当ててもよい。この場合、例えば動画像における前後数フレーム間はほぼ同一内容を表すため、このような類似性の高いフレーム群に対しては同一の情報（例えば、フレーム群の中央フレームを代表フレームとして設定し、これに対する情報）を割り当てるとよい。
【００５６】
検索結果表示部２０４は、形状間距離算出部で出力した検索対象の形状間距離を昇順にソートし、検索結果をユーザに提示する。提示方法は、画像のファイル名を表示する方法でもよいし、画像を表示してもよい。形状間距離の小さい順（または大きい順）に画像の順位（ランキング）や形状間距離を同時に表示させてもよい。また、クエリー形状と類似する形状の領域を丸印で囲ったり、多角形の辺の色を変えたりして表示するなど目立たせるとよい。検索結果は、画面に提示するだけでなく、結果情報ファイルとして出力したり、印字出力したりしてもよい。また、算出された形状間距離に基づき、検索クエリーとの類似性を判定した結果を提示してもよい。
【００５７】
また、出力するデータとしては、全ての画像における形状間距離を出力してもよいが、予め設定した閾値以下の形状間距離の画像のみを出力するとよい。
検索結果は、図１２に示すように、該当する形状の線分を太くしたり、赤色などの目立つ色に変えたりして表示することにより、検索された形状をユーザに判りやすく提示することができる。
【００５８】
以上、説明したように、本実施形態の画像検索システムによれば、上記実施形態と同様な効果を奏するとともに、検索結果をユーザに視覚的に提示することができる。
【００５９】
（第３の実施の形態）
次に、本発明の実施の形態に係る画像検索装置３００について、図８を参照して詳細に説明する。図８は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
本実施形態の画像検索装置３００は、図１の上記実施の形態とは、クエリー多角形の形状をユーザがユーザインタフェースを用いて指定できる点で相違する。図８を参照すると、本実施形態の画像検索装置３００は、図１の上記実施形態の画像検索装置１００の構成に加えて、クエリー多角形情報取得部３１２と、なす角度情報算出部３１４と、をさらに含む。なお、本実施形態の画像検索装置３００は、図７の上記実施形態の画像検索装置２００の構成も含むことができる。
【００６０】
本実施形態の画像検索装置３００は、検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得部３１２と、検索クエリーの多角形情報からクエリーなす角度情報を算出するなす角度情報算出部３１４と、をさらに備え、構成直線候補抽出部１０４および形状間距離算出部１０６は、なす角度情報算出部３１４が算出したクエリーなす角度情報を用いる。
【００６１】
本実施形態において、画像検索装置３００のユーザは、ディスプレイなどの表示部（不図示）に表示された操作画面上などで、ペン型やマウス型などのポインティングデバイス（不図示）を用いることで任意の多角形形状を指定することができる。
【００６２】
形状の指定方法は、多角形の頂点を指定してもよいし、辺を組み合わせて指定してもよいし、予め用意されている多角形の位置や角度、大きさを変形させて組み合わせた形状を指定してもよい。いずれの方法においても、クエリー多角形情報取得部３１２は、ユーザが指定した多角形の辺をたどって繋がっている頂点の座標位置を順に受け付けて、クエリー頂点座標情報３０として取得する。
【００６３】
クエリー多角形情報取得部３１２は、取得した頂点を順にＶ１，Ｖ２，・・・，Ｖｎとする。
ユーザが多角形の頂点を選択する際に、参考とする画像を表示部に表示させることで、ユーザにポインティングデバイスを用いて、表示された画像中のオブジェクトの頂点位置を選択させて、選択されたオブジェクトの頂点位置をクエリー多角形情報取得部３１２が受け付けてもよい。この構成によれば、ユーザは特定のオブジェクト形状をクエリーとして容易に選択することができる。
【００６４】
なす角度情報算出部３１４は、取得した頂点Ｖｉにおけるなす角度θｉを算出し、クエリーなす角度情報１０として出力する。ここで、取得した頂点Ｖｉにおけるなす角度θｉは、ベクトルＬｉ−１＝Ｖｉ−１−Ｖｉ、Ｌｉ＝Ｖｉ−Ｖｉ＋１を用いて、以下の式（５）により算出できる。
【数１】
だたし、・は内積、｜｜はノルムを表す。
【００６５】
これを１〜ｎに対し行うことにより、クエリーなす角度情報１０を算出し、出力する。
ただし、一般に２つのベクトルのなす角度は、αを正数とした場合、αまたは１８０−αの２通りが考えられる。そこで、小さいなす角度を２つのベクトルのなす角度とすることにより、曖昧性を無くすことができる。このため、θｉが、９０度を越える場合、１８０−θｉを改めてθｉとすればよい。すなわち、以下の式（６）のようにするとよい。
θｉ ＝ｍｉｎ（θｉ、１８０−θｉ） ・・・式（６）
ここで、ｍｉｎは小さい方の値を選択する関数である。
【００６６】
以上、説明したように、本実施形態の画像検索装置３００によれば、上記実施形態と同様な効果を奏するとともに、ユーザがクエリー形状をポインティングデバイスなどを用いて簡単に指定できる。
【００６７】
（第４の実施の形態）
次に、本発明の実施の形態に係る画像検索装置４００について、図９を参照して詳細に説明する。図９は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
本実施形態の画像検索装置４００は、図８の上記実施の形態とは、ユーザが指定した多角形のクエリー形状から、回転、拡大、または移動の変化に頑強な特徴である各辺のなす角度を基に、検索対象画像の直線成分集合から、候補形状を構成する線群を抽出し、類似度判定を行う点で相違する。なお、本実施形態の画像検索装置４００は、図７の上記実施形態の画像検索装置２００の構成も含むこともできる。
【００６８】
本実施形態の画像検索装置４００は、検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得部４１２と、検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出するなす角度情報算出部４１４と、検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶部４０２と、なす角度情報算出部４１４で取得したクエリーなす角度情報の類似性に基づき、構成直線情報記憶部４０２から構成直線の組合せ候補情報を抽出する構成直線候補抽出部４０４と、構成直線候補抽出部４０４で抽出した構成直線の組合せ候補情報と、クエリー多角形情報取得部４１２で得た検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量（幾何パラメータ）を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する形状間距離算出部４０６と、を備える。
【００６９】
具体的には、図９を参照すると、本実施形態の画像検索装置４００は、クエリー多角形情報取得部４１２と、なす角度情報算出部４１４と、構成直線候補抽出部４０４と、形状間距離算出部４０６と、を備える。
【００７０】
クエリー多角形情報取得部４１２は、検索クエリーの形状を表す頂点位置または線分のいずれかを含む多角形情報を取得する。
なす角度情報算出部４１４は、前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報１０を算出する。
【００７１】
構成直線情報記憶部４０２は、検索対象画像中の輪郭を構成する直線の情報を記憶する。
構成直線候補抽出部４０４は、なす角度情報算出部４１４で取得したクエリーなす角度情報の類似性に基づき、構成直線情報記憶部４０２から構成直線の組合せ候補情報を抽出する。
【００７２】
形状間距離算出部４０６は、構成直線候補抽出部４０４で抽出した構成直線の組合せ候補情報と、クエリー多角形情報取得部４１２で得た検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量（幾何パラメータ）を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する。
【００７３】
上記第１の実施の形態と同様にして、形状間距離の算出方法としては、クエリー形状のなす角度の順列ｑ｛θｑ１，θｑ２，・・・，θｑｎ｝と、検索対象画像ｊにおける直線群のなす角度の順列Ｇｊ’＝｛θｊ１，θｊ２，・・・，θｊｎ｝を取得する。そして、対応する直線候補のうちすくなくとも３つの対応する辺の交点を２つ抽出し、幾何変換パラメータを算出し、幾何補正を施した上で形状の形状間距離を算出する。
【００７４】
２つの交点の選択基準としては、たとえば、ｎ個の点から２点を抽出する方法として、クエリー形状の頂点Ｘｑｉにおける両辺をベクトルｖｒ，ｖｌとした際の外積の絶対値｜ｖｒ×ｖｌ｜の大きい順に２つの点を選択するとよい。外積を利用する理由は、辺長の長さとなす角度の直交性を用いるためである。
【００７５】
まず、図１５を参照し、２直線Ｌ１およびＬ２の交点座標の算出精度について説明する。直線Ｌ１の幅（太さ）をΔｄとすると、Ｌ１とＬ２の交点としてユーザが選択するブレ幅は図中破線で示す範囲となる。このブレ幅はΔｄ／ｓｉｎθであり、なす角度θが直角に近いほど小さい値となる。
【００７６】
また、図１６を参照し、検索対象画像の直線抽出における直線の角度パラメータ精度について説明する。２点Ｐ１およびＰ２を通る直線Ｌ１の角度誤差Δθは、点Ｐ２の位置ブレ幅Δｄと、点間の距離Ｌを用いてΔｄ／Ｌと近似することができる。このため、点間距離Ｌである辺長が長いほど抽出される直線の角度パラメータが安定して抽出できる。
【００７７】
幾何補正方法を、以下詳細に説明する。
点Ｐ（ｘ，ｙ）からＰ’（ｘ’，ｙ’）への回転Δθ、拡大率α、並進ΔＸ，ΔＹの幾何変換は、以下の式（７）で表せる。式（７）から、２つの点Ｐ１（ｘ１，ｙ１）、Ｐ２（ｘ２，ｙ２）とそれらの幾何補正後の対応する点Ｐ１’（ｘ１’，ｙ１’）、Ｐ２’（ｘ２’，ｙ２’）の座標位置から、パラメータΔθ、α、ΔＸ，ΔＹを解くことができる。
【００７８】
【数２】
【００７９】
例えば、図５において、θｑ１とθｊ１が等しく、θｑ２とθｊ２が等しいことから、直線Ｌ１とＬ１’が対応する直線であることが判り、同様にして，Ｌ２，とＬ２’、Ｌ３とＬ３’がそれぞれ対応する直線であることが判る。対応付けられた３直線Ｌ１，Ｌ２，Ｌ３とＬ１’，Ｌ２’，Ｌ３’を用いると、Ｌ１とＬ３の交点（Ｘｑ１，Ｙｑ１）とＬ１’とＬ３’の交点（Ｘｊ１，Ｙｊ１）が対応する頂点同士であることがさらに判る。
【００８０】
同様に（Ｘｑ２，Ｙｑ２）と（Ｘｊ２，Ｙｊ２）が対応する頂点である。この２つの対応する頂点を、式（７）に代入し、連立方程式を解くことで、パラメータΔθ、α、ΔＸ，ΔＹを得ることができる。そして、検索対象画像の形状を幾何補正し、頂点をクエリー形状と同一平面に投影し、各頂点の位置のずれを算出する。位置ずれは、２点のＸ，Ｙ各座標値の差分の絶対値の和として、以下の式（８）のように求めることができる。
ｄｊ＝Σ（｜Ｘｑｉ−Ｘｊｉ｜＋｜Ｙｑｉ−Ｙｊｉ｜） ・・・式（８）
ここで、ｉ＝１〜ｎの自然数である。
【００８１】
また、差分の二乗和など、距離の公理を満たしているものであれば何を用いてもよく、上記実施形態と同様であり、これに限定されることはない。
【００８２】
なお、本実施形態の変形として、図８の実施形態の画像検索装置３００の構成に加え、構成直線候補抽出部１０４で抽出した構成直線の組合せ候補情報と、クエリー多角形情報取得部３１２で得た検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正する補正部（不図示）をさらに備え、形状間距離算出部１０６が、補正部により幾何補正した後の形状との頂点の位置ずれ量を基に形状間距離を算出する構成としてもよい。
【００８３】
上述のような構成において、本実施の形態の画像検索装置４００によるデータ処理方法を以下に説明する。図１０は、本実施形態の画像検索装置４００の動作の一例を示すフローチャートである。
【００８４】
本実施形態のデータ処理方法は、画像検索装置４００が、検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得し（ステップＳ３０１）、検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出し（ステップＳ３０３）、取得したクエリーなす角度情報の類似性に基づき、構成直線情報記憶部４０２から構成直線の組合せ候補情報を抽出し（ステップＳ１０３、ステップＳ１０５）、抽出した構成直線の組合せ候補情報と、得られた検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する（ステップＳ１０７）。
【００８５】
以下、図１０に示すフローチャートを用いて本実施形態における画像検索装置４００の動作を説明する。
図１０において、上記実施形態の図６のフローチャートのステップＳ１０３〜ステップＳ１０９と同様なステップを含むとともに、ステップＳ３０１、ステップＳ３０３、およびステップＳ３１１を、さらに含む。
ユーザがペン型ポインティングデバイスなどを用いて指定した多角形の頂点位置（座標）を順に取得し、メモリに格納する（ステップＳ３０１）。
【００８６】
例えば、ユーザがｎ角形を指定した場合、ｎ個の頂点の位置を以下のようにメモリに記録する。
Ｑ［１］．ｘ＝１０
Ｑ［１］．ｙ＝３０
Ｑ［２］．ｘ＝４０
Ｑ［２］．ｙ＝７０
：
Ｑ［ｎ］．ｘ＝１００
Ｑ［ｎ］．ｙ＝２０
Ｑ［０］．ｘ＝１００
Ｑ［０］．ｙ＝２０
このとき、ｎ角形は閉じた形状をするため、Ｑ［０］には、Ｑ［ｎ］と同じ値を代入する。
ここで、Ｑ［ｎ］．ｘ、Ｑ［ｎ］．ｙは、Ｑ［ｎ］のｘ座標およびｙ座標成分を表すものとする。
【００８７】
ｎ角形のクエリー形状が、図１１（ａ）に示すように短い辺を持ち、かつこの辺の両端のなす角Ａ，Ｂの和が１８０度を超える場合、図１１（ｂ）に示すようなｎ−１角形を想定し、クエリー形状として検索に用いるとよい。こうすることにより、検索対象画像における直線検出で短い辺が未検出となる場合でも検索することができるからである。
【００８８】
すなわち、なす角度情報算出部３１４が、クエリー多角形内の鈍角を持つ辺の両端の辺の線分を伸ばしてできる多角形を検索クエリーの多角形とし、クエリーなす角度情報を算出するとよい。
【００８９】
なす角度情報算出部３１４が、クエリー多角形情報取得部３１２で取得したクエリー多角形形状Ｑの各頂点がなす角度を算出する（ステップＳ３０３）
なす角θｉの配列（ｉ＝１、２、・・・、ｎ）は、以下の式（９）、式（１０）のように算出することができる。
θ［ｉ］＝ａｒｃｃｏｓ（（β［ｉ−１］．ｘ＊β［ｉ］．ｘ＋β［ｉ−１］．ｙ＊β［ｉ］．ｙ）／√（（β［ｉ−１］．ｘ＾２＋β［ｉ−１］．ｙ＾２）（β［ｉ］．ｘ＾２＋β［ｉ］．ｙ＾２））） ・・・式（９）
ｉｆ（θ［ｉ］＞π）｛θ［ｉ］＝π−θ［ｉ］｝ ・・・式（１０）
ここで、βは以下の式（１１）〜式（１４）により求めることができる。
β［ｉ］．ｘ＝Ｑ［ｉ＋１］．ｘ−Ｑ［ｉ］．ｘ ・・・式（１１）
β［ｉ］．ｙ＝Ｑ［ｉ＋１］．ｙ−Ｑ［ｉ］．ｙ ・・・式（１２）
β［ｉ−１］．ｘ＝Ｑ［ｉ−１］．ｘ−Ｑ［ｉ］．ｘ ・・・式（１３）
β［ｉ−１］．ｙ＝Ｑ［ｉ−１］．ｙ−Ｑ［ｉ］．ｙ ・・・式（１４）
【００９０】
構成直線情報記憶部１０２で記憶している１つの検索対象画像の直線情報を抽出する（ステップＳ１０３）。
直線情報は、配列Ｌ［Ｍ］に、なす角情報は、２次元配列Ａ［Ｍ］［Ｍ］記憶されているとする。
なす角情報が記憶されていない場合は、直線情報を用いてなす角度情報を作成する。
【００９１】
図３の例で示すと、以下のようになる。
Ｌ［１］．ρ＝ ５０、Ｌ［１］．θ＝ ６０、
Ｌ［２］．ρ＝ ６０、Ｌ［２］．θ＝ １５、
Ｌ［３］．ρ＝ ４０、Ｌ［３］．θ＝ １０５、
Ａ［１］［１］＝０， Ａ［１］［２］＝４５， Ａ［１］［３］＝４５，
Ａ［２］［１］＝４５， Ａ［２］［２］＝０， Ａ［２］［３］＝９０，
Ａ［３］［１］＝４５， Ａ［３］［２］＝９０， Ａ［３］［３］＝０
【００９２】
構成直線候補抽出部４０４では、なす角度情報算出部３１４で算出したクエリー多角形と一致する可能性のある検索対象画像の候補を構成直線情報記憶部４０２から抽出する。
クエリー多角形のなす角度の順列を表す配列θ［ｉ］と一致するなす角度の組合せを、構成直線情報記憶部４０２に記憶されているなす角情報２次元配列Ａ［Ｍ］［Ｍ］から探索する。
【００９３】
すなわち、なす角度情報算出部４１４は、検索クエリーの多角形のなす角度を隣接する順に抽出したなす角度順列情報をクエリーなす角度情報に含み、さらに、構成直線候補抽出部４０４は、なす角度順列情報を用い、構成直線情報記憶部４０２から順列にしたがい類似するなす角度を持つ構成直線の組合せを抽出する。
【００９４】
簡単なフィルタリングとして、すべてのｉ（１〜ｎ）において、以下の式（１５）を満たすｐ、ｑ（１＝＜ｐ，ｑ＜＝Ｍ）が存在する場合のみ、以後の処理を行い、存在しない場合は、ステップＳ１０３に戻り、構成直線情報記憶部１０２で記憶している別の画像の直線情報を抽出する。
｜θ［ｉ］−Ａ［ｐ］［ｑ］｜＜ｔｈ ・・・式（１５）
【００９５】
次に、θ［ｉ］（ｉ＝１〜ｎ）の順列と同様の順列をＡ［Ｍ］［Ｍ］から探索する。
探索方法としては、以下の再帰法を用いるとよい。
ステップＳ２０１：Ａ［ｐ０］［ｑ０］＝＝θ［１］となるｐ０，ｑ０を見つける。
ステップＳ２０２：Ａ［ｑ０］［ｑ］＝＝θ［２］となるｐ０以外のｑを探し、ｐ１とする。
ステップＳ２０３：Ａ［ｐ１］［ｑ］＝＝θ［３］となるｐ０、ｐ１以外のｑを探し、ｐ２とする。
ステップＳ２０４：Ａ［ｐｉ−１］［ｑ］＝＝θ［ｉ］となるｐｊ（ｊ＝０，…，ｉ−１）以外のｑを探し、ｐｉとする。
ステップＳ２０５：ｉ＜ｎならばｉ＝ｉ＋１としてステップＳ２０４を繰り返す。
ステップＳ２０６：ｉ＝ｎ、かつ、ｐｉ＝ｐ０であれば抽出した頂点のなす角度順列と同一の構成直線の組合せｐｊ（１，２，・・・，ｎ）を出力する。それ以外は組合せがないものとする。
このように頂点のなす角度順列と同一の構成直線の組合せｐｊ（１，２，・・・，ｎ）を取得する（ステップＳ１０５）。
【００９６】
形状間距離算出部４０６では、構成直線候補抽出部４０４で検出したクエリー多角形の辺とそれに対応する直線候補を抽出した画像ごとに、形状間距離を算出する（ステップＳ１０７）。
ｐｊの組が得られた場合は、ｐａおよびｐｂの２直線の交点（Ｘｂ，Ｙｂ）を求めることで、１つの頂点座標を算出することができる。これをｎ個のペアに対して行うことで、ｎ角形の頂点座標（Ｘｉ，Ｙｉ）を算出する。このようにして抽出したｎ角形の頂点座標（Ｘｉ，Ｙｉ）（ｉ＝１〜ｎの自然数）と、クエリー多角形（Ｑ［ｉ］．ｘ，Ｑ［ｉ］．ｙ）との対応から、幾何変形パラメータα、Δθ、ΔＸ，ΔＹを算出する。ｎ個の頂点のうち２つを用いて式（７）に代入し、連立方程式を解くことで得られる。
【００９７】
得られたパラメータを基に、クエリー多角形（Ｑ［ｉ］．ｘ，Ｑ［ｉ］．ｙ）を上記式（７）のＸ，Ｙに代入することにより、幾何変形後のクエリー多角形（Ｑ［ｉ］’．ｘ，Ｑ［ｉ］’．ｙ）を算出できる。
【００９８】
形状間距離は、幾何変形後のクエリー多角形（Ｑ［ｉ］’．ｘ，Ｑ［ｉ］’．ｙ）と、抽出したｎ角形の頂点座標（Ｘｉ，Ｙｉ）との距離を以下の式（１６）によって算出することで得られる。ここで、ｉ＝１〜ｎの自然数。
ｄ＝Σ（｜Ｑ［ｉ］．ｘ−Ｘｊ｜＋｜Ｑ［ｉ］．ｙ−Ｙｊ｜） ・・・式（１６）
また、距離の算出はこれに限らず、距離の公理を満たすものであればどのようなものを用いてもよい。
【００９９】
構成直線情報記憶部４０２に記憶されている全ての検索対象画像に対して処理が行われたかを確認し、行われていない場合は（ステップＳ１０９のＮＯ）、ステップＳ１０３へ戻り、新たな検索対象画像を抽出する。
構成直線情報記憶部４０２に記憶されている全ての検索対象画像に対して処理が行われた場合（ステップＳ１０９のＹＥＳ）、算出した形状間距離を距離の短い順にソートする。ソートした形状に対応する画像情報を距離の短い順に検索結果として画面に表示する（ステップＳ３１１）。
【０１００】
以上、説明したように、本実施形態の画像検索装置４００によれば、上記実施形態と同様な効果を奏するとともに、回転、移動、またはスケール変動に頑強な検索が行えることができるという効果がある。その理由は、回転、移動、またはスケール変動に不変な多角形の隣接する辺のなす角度の順列を用いて検索対象画像群から同一順列のなす角度を保有する線の候補を抽出し、類似度を判定するためである。
【０１０１】
（第５の実施の形態）
次に、本発明の実施の形態に係る画像検索装置５００について、図１３を参照して詳細に説明する。図１３は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
本実施形態の画像検索装置５００は、図９の上記実施の形態とは、クエリー多角形の内部領域に対応する視覚的特徴量もさらに考慮して距離を算出する点で相違する。
【０１０２】
本実施形態の画像検索装置５００は、クエリー多角形情報取得部４１２で取得した検索クエリーの多角形の形状を表す頂点の位置および線分のすくなくとも１つを含む情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出するクエリー視覚的特徴量抽出部５２２と、検索対象画像の色およびエッジのすくなくとも１つを含む情報を記録する検索対象画像情報記憶部２０２と、構成直線候補抽出部４０４において抽出された構成直線が囲む領域における検索対象画像の視覚的特徴量を、検索対象画像情報記憶部２０２に記憶されている情報を基に抽出する視覚的特徴量抽出部５２４と、クエリー視覚的特徴量抽出部５２２と視覚的特徴量抽出部５２４で抽出した視覚的特徴量の距離を算出する視覚的特徴量距離算出部５２６と、形状間距離算出部４０６と視覚的特徴量距離算出部５２６とで算出した距離を基に総合距離を算出する総合距離算出部５２８と、をさらに備える。
【０１０３】
図１３を参照すると、本実施形態の画像検索装置５００は、図９の上記実施形態の画像検索装置４００の構成に加えて、クエリー視覚的特徴量抽出部５２２と、視覚的特徴量抽出部５２４と、視覚的特徴量距離算出部５２６と、総合距離算出部５２８と、をさらに含む。なお、本実施形態の画像検索装置５００は、図８の上記実施形態の画像検索装置の構成も含むことができる。
【０１０４】
クエリー視覚的特徴量抽出部５２２は、クエリー多角形情報取得部４１２で取得したクエリー多角形を表す頂点の位置や線分の情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出する。視覚的特徴量を抽出する方法として、該当領域の色に関する特徴量であるドミナントカラー（Dominant Color）（配色全体の印象を支配する色）や対象領域内の色の配置に関する特徴であるカラーレイアウト（Color Layout）、または、模様に関する特徴であるエッジヒストグラムなどの特徴を抽出するとよい。これらの特徴量は予め複数のサンプル色やサンプルパターンに対して作成しておき、ユーザに選択してもらってもよいし、ユーザが検索クエリーの多角形を選択する際に特徴量を抽出するべき画像とその画像内の領域を指定し、その画像の領域から特徴量を算出してもよい。
【０１０５】
視覚的特徴量抽出部５２４は、構成直線候補抽出部４０４において抽出された構成直線によって囲まれる領域における検索対象画像の視覚的特徴量を抽出する。検索対象画像情報記憶部２０２に記憶されている画像情報から、構成直線が囲む領域に対応する画素の色およびエッジなどを抽出し、Ｄｏｍｉｎａｎｔ ＣｏｌｏｒやＣｏｌｏｒ Ｌａｙｏｕｔ、エッジヒストグラムなどの特徴量を算出する。ここで算出される特徴量は上述したクエリー視覚的特徴量抽出部５２２と同一のものを用いる。また、検索対象画像を細かな領域に分割しておき、分割した領域ごとに特徴量を抽出して予め記憶しておくことにより、構成直線が囲む領域に対する特徴量を、範囲内の分割領域の特徴量で代用することにより特徴量の算出処理を省くことができる。
【０１０６】
視覚的特徴量距離算出部５２６は、クエリー視覚的特徴量抽出部５２２と、視覚的特徴量抽出部５２４でそれぞれ抽出した視覚的特徴量の距離である視覚的特徴量距離を算出する。視覚的特徴量距離の算出方法として、視覚的特徴量間のユークリッド距離を用いるとよい。具体的には、視覚的特徴量の各次元での値の差分の２乗をすべての次元において算出し、総和の平方根をとることで距離を算出することができる。差分の２乗の他にも、差分の絶対値など、距離の公理を満たしているものであれば何を用いてもよく、これに限定されることはない。
【０１０７】
総合距離算出部５２８は、形状間距離算出部４０６と、視覚的特徴量距離算出部５２６で算出した２つの距離を用いて統合距離を算出する。距離算出は、２つの距離を足し合わせたり、形状と視覚的の類似度の重要性に応じてそれぞれ重み付けした距離を足し合わせたりして求めることができる。
【０１０８】
検索対象画像情報記憶部２０２と検索結果表示部２０４は、図７の上記実施形態で説明したものと同じであるが、本実施形態では、検索対象画像情報記憶部２０２に、視覚的特徴量の算出に用いるためオリジナル画像やサムネイル画像を記憶しておくとさらによい。
【０１０９】
このように構成された本実施形態の動作について、図１４を用いて以下に説明する。図１４は、本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。本実施形態では、図１０の上記実施形態の画像検索装置４００のフローチャートで、各画像の形状間距離を求めるとともに、以下の処理を行う。
【０１１０】
まず、クエリー視覚的特徴量抽出部５２２が、クエリー多角形情報取得部４１２で取得したクエリー多角形を表す頂点の位置や線分の情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出する（ステップＳ５０１）。
【０１１１】
そして、視覚的特徴量抽出部５２４が、構成直線候補抽出部４０４において抽出された構成直線によって囲まれる領域における検索対象画像の視覚的特徴量を抽出する（ステップＳ５０３）。さらに、視覚的特徴量距離算出部５２６が、クエリー視覚的特徴量抽出部５２２と、視覚的特徴量抽出部５２４でそれぞれ抽出した視覚的特徴量の距離である視覚的特徴量距離を算出する（ステップＳ５０５）。そして、総合距離算出部５２８が、形状間距離算出部４０６と、視覚的特徴量距離算出部５２６で算出した２つの距離を用いて統合距離を算出し、出力する（ステップＳ５０７）。
【０１１２】
出力された総合距離は、上記第２の実施の形態における形状間距離と同様な方法でユーザに提示することができる。
【０１１３】
以上、説明したように、本実施形態の画像検索装置５００によれば、上記実施形態と同様な効果を奏するとともに、クエリー多角形の内部領域の視覚的特徴量を考慮して距離を算出できるので、輪郭だけでなく、よりクエリーに類似した画像を検出できるとともに、検索処理の負荷を低減できる。
【０１１４】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【０１１５】
また、図１３の上記実施形態の画像検索装置５００において、画像検索装置４００は、図１、図２または図７の上記実施形態の画像検索装置の構成とすることもできる。この場合は、クエリー視覚的特徴量抽出部５２２は、ユーザが選択したサンプル色またはパターンに対する視覚的情報を、クエリー多角形の内部領域に対応する視覚的情報として抽出する。また、視覚的特徴量抽出部５２４は、構成直線候補抽出部１０４において抽出された構成直線によって囲まれる領域における検索対象画像の視覚的特徴量を抽出する。また、総合距離算出部５２８は、形状間距離算出部１０６形状間距離算出部４０６と、視覚的特徴量距離算出部５２６で算出した２つの距離を用いて統合距離を算出する。
【０１１６】
また、図９の上記実施形態において、図１０のステップＳ３１１で、検索結果を表示する際に、ソートした形状に対応する画像情報を、図７の画像検索装置２００の検索対象画像情報記憶部２０２から取得し、距離の短い順にオリジナル画像やサムネイル画像を表示するように構成してもよい。この構成によれば、検索結果をユーザに視覚的に分かり易く提示することができる。
【０１１７】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【０１１８】
１ クエリーなす角度情報
１２ 対応する構成直線の候補情報
１４ 形状間距離
３０ クエリー頂点座標情報
１００ 画像検索装置
１０２ 構成直線情報記憶部
１０４ 構成直線候補抽出部
１０６ 形状間距離算出部
２００ 画像検索装置
２０２ 検索対象画像情報記憶部
２０４ 検索結果表示部
３００ 画像検索装置
３１２ クエリー多角形情報取得部
３１４ 角度情報算出部
４００ 画像検索装置
４０２ 構成直線情報記憶部
４０４ 構成直線候補抽出部
４０６ 形状間距離算出部
４１２ クエリー多角形情報取得部
４１４ なす角度情報算出部
５００ 画像検索装置
５２２ クエリー視覚的特徴量抽出部
５２４ 視覚的特徴量抽出部
５２６ 視覚的特徴量距離算出部
５２８ 総合距離算出部
【技術分野】
【０００１】
本発明は、画像検索装置、画像検索装置のデータ処理方法、および画像検索システムに関し、特に、形状情報をクエリーとした画像検索装置、画像検索装置のデータ処理方法、および画像検索システムに関する。
【背景技術】
【０００２】
ユーザの指定するクエリー形状による画像検索を実現するためには、ユーザが指定するクエリー形状と、検索対象画像中の形状に関する類似度を算出する必要がある。
検索時に高速に照合するためには、検索対象画像群からあらかじめ特徴量を抽出しておく必要がある。画像全面が検索対象の場合は画像全体から特徴量を抽出すればよいが、画像の一部であるオブジェクトが検索対象となる場合、検索対象画像から該当する領域の特徴量を抽出する必要がある。
【０００３】
図１７は、形状をクエリーとした画像検索方法の一例を説明する図である。ユーザは検索したい形状をクエリー形状として入力すると、類似形状を含む画像が検索結果として出力される。
画像検索装置の例が以下の各特許文献に記載されている。
特許文献１に記載された画像検索装置は、ユーザが選択した検索対象となるクエリーの形状及び色特徴および検索対象となる位置を取得し、検索対象画像群の画像の中から、探索窓を走査して類似する領域を探索し、類似画像を抽出する。
【０００４】
特許文献２に記載された画像検索装置は、検索対象画像に含まれる主要な形状（たとえば、円形、三角形、または四角形など）の種類を予め決定し、登録しておくことで、ユーザが与える特定のオブジェクトの形状の種類をクエリーとし検索する。
【０００５】
特許文献３に記載された画像検索装置は、検索対象画像から予め注目領域を自動で抽出し、クエリー領域との類似度を判定している。
特許文献４に記載された直線による画像の検索装置は、検索対象画像に含まれる直線の特徴（始点、終点、重心、傾き、または長さ）を登録しておき、ユーザが与える直線情報と直線周辺の色などの類似度を算出し、検索する。連続する可能性のある直線を一直線とみなすことで、一部欠けのある直線も検索できる。
【０００６】
特許文献５に記載された画像特徴抽出装置は、画像中に含まれる直線の傾きを登録しておき、ユーザが与える画像内の直線情報との類似度を算出し検索する。また、特許文献６に記載された画像形成システムは、線分のなす角度を用いて形状の類似度を算出する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０００−７６３０２号公報
【特許文献２】特開２００９−１９３３９８号公報
【特許文献３】特開２００７−１９９７４９号公報
【特許文献４】特開２０００−８２０７５号公報
【特許文献５】特開平５−１３５１７４号公報
【特許文献６】特開２００６−２５２００７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述した従来のシステムでは、次のような問題があった。
特許文献１に記載の例での問題点は、探索窓を設定するためスケールや回転の影響を受けやすく、検索時に検索対象画像を探索し、特徴量を抽出するため非常に時間がかかることである。
特許文献２に記載の例での問題点は、ユーザが検索に用いるクエリー形状は多様であり、予め形状を規定することは困難である。また、その形状登録の自動化が困難であることである。
【０００９】
特許文献３に記載の例の問題点はユーザが所望する検索結果が出ないことである。その理由は、検索対象画像の注目領域は、支配的な単一色として抽出されており、ユーザの関心に関わらず固定されるが、クエリーとなる領域はユーザが自由に選択できるため、注目領域として選択されたものがユーザの意図と異なるためである。ユーザが関心を持つ注目領域は一定ではなく、検索目的などにより変化するため、予め検索対象画像から注目領域を決定することは非常に困難である。
【００１０】
特許文献４に記載の例での問題点は、画像中における直線位置や周辺色などの類似度を判定するため、特定の形状による検索は行えないことや、位置情報に依存するため回転に頑強ではないことである。
特許文献５に記載の例での問題点は、大きな角度の回転に頑強ではないことである。その理由は、メンバシップ関数の導入による吸収可能な回転ずれは小さな角度に限定され、４５度や９０度の回転には対応できないためである。また、画像全体の直線の傾きの集合を特徴量としているため、クエリーと類似する形状が画像の大部分を占める場合以外では、検索精度が落ちると考えられる。
【００１１】
また、特許文献６に記載の例での問題点は、線分のなす角度のみに基づく類似度であるため、たとえば、長方形と正方形など、いずれもなす角度が、９０度、９０度、９０度、９０度の場合、区別がつかない点である。
【００１２】
このように、形状による画像検索では、ユーザが検索に用いるクエリー形状が未知であるため、その多様性から予め決定しておくことは困難であり、また検索時に決定された形状の探索を行うのでは時間がかかりすぎる問題がある。特別な選択基準に基づき画像中の検索対象領域を自動抽出する方法では、選択基準が固定されているため、多様な形状に対応できない。検索対象画像群から直線成分を抽出して一致度を判定する方法があるものの、直線の傾きを用いているため、画像の回転に弱い問題がある。
【００１３】
本発明は上記事情に鑑みてなされたものであり、その目的とするところは、効率よく高精度な画像検索が可能な画像検索装置、画像検索装置のデータ処理方法、および画像検索システムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の第一の画像検索装置は、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
を備える。
【００１５】
本発明の第二の画像検索装置は、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得手段と、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出するなす角度情報算出手段と、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
前記なす角度情報算出手段で取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と、前記クエリー多角形情報取得手段で得た前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する形状間距離算出手段と、
を備える。
【００１６】
本発明の第１の画像検索装置のデータ処理方法は、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する。
【００１７】
本発明の第２の画像検索装置のデータ処理方法は、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得し、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出し、
取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した前記構成直線の組合せ候補情報と、得られた前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する。
【００１８】
本発明の画像検索システムは、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
算出された前記形状間距離をユーザに提示する提示手段と、
を備える。
【００１９】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【００２０】
また、本発明の各種の構成要素は、必ずしも個々に独立した存在である必要はなく、複数の構成要素が一個の部材として形成されていること、一つの構成要素が複数の部材で形成されていること、ある構成要素が他の構成要素の一部であること、ある構成要素の一部と他の構成要素の一部とが重複していること、等でもよい。
【００２１】
また、本発明のデータ処理方法またはコンピュータプログラムには複数の手順を順番に記載してあるが、その記載の順番は複数の手順を実行する順番を限定するものではない。このため、本発明のデータ処理方法およびコンピュータプログラムを実施するときには、その複数の手順の順番は内容的に支障しない範囲で変更することができる。
【００２２】
さらに、本発明のデータ処理方法またはコンピュータプログラムの複数の手順は個々に相違するタイミングで実行されることに限定されない。このため、ある手順の実行中に他の手順が発生すること、ある手順の実行タイミングと他の手順の実行タイミングとの一部ないし全部が重複していること、等でもよい。
【発明の効果】
【００２３】
本発明によれば、効率よく高精度な画像検索が可能な画像検索装置、画像検索装置のデータ処理方法、および画像検索システムが提供される。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図２】本発明の実施の形態に係る画像検索装置における検索対象画像から直線情報の抽出を説明するための図である。
【図３】本発明の実施の形態に係る画像検索装置の構成直線情報記憶部に記録される直線情報の例を示す図である。
【図４】本発明の実施の形態に係る画像検索装置の構成直線情報記憶部に記録される直線情報の例を示す図である。
【図５】本発明の実施の形態に係る画像検索装置における検索クエリーに対応する検索対象画像内の類似する図形の検索を説明するための図である。
【図６】本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。
【図７】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図８】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図９】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図１０】本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。
【図１１】本発明の実施の形態に係る画像検索装置の構成直線検出処理を説明するための図である。
【図１２】本発明の実施の形態に係る画像検索装置の検索結果表示画面の一例を示す図である。
【図１３】本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
【図１４】本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。
【図１５】本発明の実施の形態に係る画像検索装置の２直線の交点座標の算出精度を説明するための図である。
【図１６】本発明の実施の形態に係る画像検索装置の検索対象画像の直線抽出における直線の角度パラメータ精度を説明するための図である。
【図１７】検索対象画像群からの検索クエリー形状を用いた画像検索を説明するための図である。
【発明を実施するための形態】
【００２５】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００２６】
（第１の実施の形態）
図１は、本発明の実施の形態に係る画像検索装置１００の構成を示す機能ブロック図である。
本実施形態の画像検索装置１００は、検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶部１０２と、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出する構成直線候補抽出部１０４と、構成直線候補抽出部１０４で抽出した構成直線の組合せ候補情報とクエリーなす角度情報とから、形状間距離を算出する形状間距離算出部１０６と、を備える。
【００２７】
詳細には、図１を参照すると、本発明の実施の形態の画像検索装置１００は、構成直線情報記憶部１０２と、構成直線候補抽出部１０４と、形状間距離算出部１０６と、を含む。
【００２８】
画像検索装置１００の各構成要素は、任意のコンピュータのＣＰＵ（Central Processing Unit）、メモリ、メモリにロードされた本図の構成要素を実現するプログラム、そのプログラムを格納するハードディスクなどの記憶ユニット、ネットワーク接続用インタフェースを中心にハードウェアとソフトウェアの任意の組合せによって実現される。そして、その実現方法、装置にはいろいろな変形例があることは、当業者には理解されるところである。以下説明する各図は、ハードウェア単位の構成ではなく、機能単位のブロックを示している。
【００２９】
具体的には、画像検索装置１００は、たとえば、図示しないＣＰＵやメモリ、ハードディスク、および通信装置を備え、キーボードやマウス等の入力装置やディスプレイやプリンタ等の出力装置と接続されるサーバコンピュータやパーソナルコンピュータ、またはそれらに相当する装置により実現することができる。そして、ＣＰＵが、ハードディスクに記憶されるプログラムをメモリに読み出して実行することにより、上記各ユニットの各機能を実現することができる。
なお、以下の各図において、本発明の本質に関わらない部分の構成については省略してあり、図示されていない。
【００３０】
構成直線情報記憶部１０２は、検索対象となる画像群から抽出した直線に関する情報を記憶する。
本発明では、検索対象となる画像とは、静止画像および動画像を含むことができる。
【００３１】
直線を抽出する方法は、特許文献４に記載されているハフ変換を用いるとよい。または、Ｈａｒｒｉｓ Ｃｏｒｎｅｒ Ｄｅｔｅｃｔｏｒ（シー． ハリス（C. Harris）、外１名、「ア コンバインド コーナー アンド エッジ デテクター（A combined corner and edge detector）」、第４回アルビービジョンカンファレンス予稿集（Proc. 4th Alvey Vision Conf.）、（英国）、ザ プレシー カンパニー ピーエルシー．（The Plessey Company plc.）、１９８８年８月、p.147-151）などのコーナー点検出により抽出した画像内のコーナー点の組合せのうち、点と点を結んだ直線上にエッジを有する画素が多数存在するものを直線として抽出してもよい。
このようにして抽出された直線における原点からの距離ρと直線へ引いた垂線の傾き角度θのペアを直線情報として構成直線情報記憶部１０２に記録する。
【００３２】
図２に、検索対象画像から直線情報を抽出する例を示す。
直線情報は、距離と傾き以外にも、直線の方程式ａｘ＋ｂｙ＋ｃ＝０の係数ａ、ｂ、およびｃを用いてもよく、また、コーナー点間の直線上のエッジ画素による直線検出では、容易に直線を線分として求めることができるため、線分の２つの端点の座標（ｘ１，ｙ１）および（ｘ２，ｙ２）を直線に関する情報として記憶してもよい。ただし、本発明では、なす角度を頻繁に利用するため、傾き角度θを記録しておくのが望ましい。
【００３３】
抽出した直線情報は、直線ごとのρ、θの値とし、図３に示すように記録する。このとき、後の処理を容易化するため、図４に示すように、直線同士の組合せに対する、角度の差を表す値を表として記録しておくとよい。このとき、全ての頂点が画像内に位置する多角形のみを検索対象とする場合は、画像範囲内で交差する直線の組のみを記録することで、処理量を削減することができる。
【００３４】
これらのデータはＣＤ−ＲＯＭ、ＤＶＤ−Ｒ、ハードディスク、メモリなどの記録媒体に一括または複数に分割して記憶する。記憶されているデータはＣＤ−ＲＯＭドライブなどの読み込み装置により単数または複数の媒体から読み込まれるか、あるいはネットワークインターフェースを通じてインターネットやＬＡＮ（Local Area Network）等のネットワークを介して取得することができる。
【００３５】
構成直線候補抽出部１０４は、ｎ角形の検索クエリーの多角形のなす角度θｑｉ（ここで、ｉ＝１〜ｎの自然数。）の情報１０を入力し、入力したクエリーなす角度と一致するなす角度を保有する可能性のある構成直線の候補を構成直線情報記憶部１０２から抽出し、その構成直線の候補に関する情報（対応する構成直線の候補情報１２）を出力する。
【００３６】
ここで、構成直線候補抽出部１０４に入力されるクエリーなす角度情報１０は、たとえば、ユーザが操作部を操作して指定した情報でよいし、予め準備された情報を記録媒体またはネットワークを介して他の装置から読み込んで入力した情報でもよく、特に限定されない。クエリーなす角度情報１０は、受付部（不図示）が受け付け、構成直線候補抽出部１０４および形状間距離算出部１０６に入力することができる。
【００３７】
構成直線情報記憶部１０２に記憶されている全てのＮ枚の画像中の画像ｊにおける構成直線がなす角度の個数をｍｊとし、画像ｊにおけるなす角度の集合を、以下の式（１）とする。
Ｇｊ＝｛θｊ１，θｊ２，・・・，θｊｍｊ｝ ・・・式（１）
このとき、検索クエリーのなす角度ｑ｛θｑ１，θｑ２，・・・，θｑｎ｝に対し、以下の式（２）となるｎ個の組合せを探索する。
θｑｉ＝θｊｋ ・・・式（２）
ただし、角度抽出の誤差などを考慮し、θａとθｂを同一とみなす条件として、閾値ｔｈを用いて、以下の式（３）とするとよい。
｜θａ−θｂ｜＜ｔｈ ・・・式（３）
【００３８】
検出したなす角度の順列から、クエリー形状の辺と対応する直線の順列を求め、各直線のθ、ρの値もしくは頂点位置などの構成直線の候補に関する情報を出力する。
【００３９】
図５の例では、θｑ１＝θｊ１、θｑ２＝θｊ２、θｑ３＝θｊ３となることから、θｑ１とθｑ２を両端に持つＬ１と、θｊ１とθｊ２を両端に持つＬ１’が対応する直線であることが判り、同様に、Ｌ２とＬ２’、Ｌ３とＬ３’がそれぞれ対応する直線であることが判る。
【００４０】
対応する直線の組の順列と、各直線の傾き角度θと距離ρなどの直線に関する情報を出力する。
形状間距離算出部１０６は、構成直線候補抽出部１０４で検出したクエリー形状の辺とそれに対応する直線候補を抽出した画像ごとに、形状間距離１４を算出し、出力する。
形状間距離とは、２つの形状の異なる度合いを表す尺度であり、形状間距離が小さいほど２つの形状は類似していることになり、大きいほど似ていないことになる。
【００４１】
なお、算出された形状間距離に基づき、検索クエリーとの類似性を判定する判定部（不図示）をさらに備えることもできる。
【００４２】
形状間距離の算出方法としては、クエリー形状のなす角度の順列ｑ｛θｑ１，θｑ２，・・・，θｑｎ｝と、検索対象画像ｊにおける直線群のなす角度の順列Ｇｊ’＝｛θｊ１，θｊ２，・・・，θｊｎ｝から、対応するなす角度の差の絶対値の和を距離ｄｊとして以下の式（４）により算出する。
ｄｊ＝Σ｜θｑｉ−θｊｉ｜ ・・・式（４）
ただし、ｉは１〜ｎの自然数。
これ以外にも、２乗和やより一般化したＬｐノルムなど、距離の公理を満たすものであればどのようなものを用いてもよい。
【００４３】
本実施形態では、この形状間距離を類似度の尺度として用いる。ただし、以下の説明では、形状間距離が小さいほど類似度が高くなることに注意を要する。もちろん、類似度の尺度として、形状間距離のかわりに、類似性を表す（類似度が高いほど大きくなる）指標を用いてもよい。例えば、１／（１＋ｄ）（ｄは距離）のような指標を用いてもよい。
この処理をすべての検索対象画像（ｊ＝１〜Ｎ）に対しておこない、算出した形状間距離ｄｊを出力する。
【００４４】
本実施形態の画像検索装置１００は、コンピュータプログラムに対応する各種の処理動作をＣＰＵが実行することにより、前述のような各種ユニットが各種機能として実現される。
【００４５】
本実施形態のコンピュータプログラムは、画像検索装置１００を実現させるためのコンピュータに、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出する手順、抽出した構成直線の組合せ候補情報とクエリーなす角度情報とから、形状間距離を算出する手順を実行させるように記述されている。
【００４６】
本実施形態のコンピュータプログラムは、コンピュータで読み取り可能な記憶媒体に記録されてもよい。記録媒体は特に限定されず、様々な形態のものが考えられる。また、プログラムは、記録媒体からコンピュータのメモリにロードされてもよいし、ネットワークを通じてコンピュータにダウンロードされ、メモリにロードされてもよい。
【００４７】
上述のような構成において、本実施の形態の画像検索装置１００によるデータ処理方法を以下に説明する。図６は、本実施形態の画像検索装置１００の動作の一例を示すフローチャートである。
【００４８】
本実施形態のデータ処理方法は、画像検索装置１００が、検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、構成直線情報記憶部１０２から構成直線の組合せ候補情報を抽出し（ステップＳ１０３、ステップＳ１０５）、抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する（ステップＳ１０７）。
【００４９】
このように構成された本実施形態の画像検索装置１００の動作について、図６を用いて以下に説明する。
図６は、本実施形態の画像検索装置１００の動作の一例を示すフローチャートである。
構成直線候補抽出部１０４にｎ角形の検索クエリーのクエリーなす角度情報１０が入力される（ステップＳ１０１）。
【００５０】
そして、構成直線候補抽出部１０４が、構成直線情報記憶部１０２を参照し、構成直線情報記憶部１０２に記憶されている全てのＮ枚の検索対象画像中の一つの画像ｊにおける構成直線を抽出し（ステップＳ１０３）、入力したクエリーなす角度と一致するなす角度を有する可能性のある構成直線の候補を抽出する（ステップＳ１０５）。ここでは、対応する直線の組の順列と、各直線の傾き角度θと距離ρなどの直線に関する情報を出力する。
【００５１】
そして、形状間距離算出部１０６が、構成直線候補抽出部１０４で検出したクエリー形状の辺とそれに対応する直線候補を抽出した画像ごとに、形状間距離１４を算出し、出力する（ステップＳ１０７）。これらの処理を構成直線情報記憶部１０２に記憶されている全ての検索対象画像について繰り返し行い（ステップＳ１０９のＮＯ）、すべての検索対象画像について処理が終了した場合（ステップＳ１０９のＹＥＳ）、本処理を終了する。このようにして、検索対象画像について、クエリー多角形との形状間距離が出力される。
【００５２】
以上、説明したように、本実施形態の画像検索装置１００によれば、検索時にクエリー形状と類似する形状を効率的に再構築することが可能となる。このため、検索ごとに検索対象画像から対象となる形状を抽出する必要が無いという効果がある。その理由は、予め検索対象となる検索対象画像について、形状の最小単位である直線情報を抽出してあるためである。また、形状構成成分を直線として記述するため、一部欠けや遮蔽などに頑強となるといった効果も奏する。
【００５３】
（第２の実施の形態）
次に、本発明の実施の形態に係る画像検索システムについて、図７を参照して詳細に説明する。図７は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。本実施形態に係る画像検索システムにおいて、画像検索装置２００は、上記実施の形態の画像検索装置１００とは、検索対象の画像の情報を記憶する点、または、検索結果をユーザに提示する点で相違する。図７を参照すると、本実施形態の画像検索装置２００は、図１の上記実施形態の画像検索装置１００の構成に加えて、検索対象画像情報記憶部２０２と、検索結果表示部２０４と、をさらに含む。
【００５４】
本実施形態の画像検索システムは、上記実施形態の画像検索装置１００の構成に加え、さらに、算出された形状間距離をユーザに提示する提示部（検索結果表示部２０４）を備える。本実施形態の画像検索システムにおいて、提示部は、画像検索装置２００とは異なる他の端末であってもよく、ネットワークなどを介して画像検索装置２００に接続可能な構成とすることができる。
【００５５】
具体的には、検索対象画像情報記憶部２０２は、構成直線情報記憶部１０２に記憶されている検索対象となってすべての画像に関する情報が記憶されている。記憶する情報として、画像のファイル名、サイズ、解像度、作成日、ダウンロードされた画像の場合はＵＲＬなどのほか、オリジナル画像やサムネイル画像などを含むことができる。これらの情報は、構成直線情報記憶部１０２の情報と１対１に対応して記録してもよいが、記憶する容量を削減するため複数の「構成直線情報記憶部１０２に記憶されている情報を抽出した画像」に対し、１つの情報を割り当ててもよい。この場合、例えば動画像における前後数フレーム間はほぼ同一内容を表すため、このような類似性の高いフレーム群に対しては同一の情報（例えば、フレーム群の中央フレームを代表フレームとして設定し、これに対する情報）を割り当てるとよい。
【００５６】
検索結果表示部２０４は、形状間距離算出部で出力した検索対象の形状間距離を昇順にソートし、検索結果をユーザに提示する。提示方法は、画像のファイル名を表示する方法でもよいし、画像を表示してもよい。形状間距離の小さい順（または大きい順）に画像の順位（ランキング）や形状間距離を同時に表示させてもよい。また、クエリー形状と類似する形状の領域を丸印で囲ったり、多角形の辺の色を変えたりして表示するなど目立たせるとよい。検索結果は、画面に提示するだけでなく、結果情報ファイルとして出力したり、印字出力したりしてもよい。また、算出された形状間距離に基づき、検索クエリーとの類似性を判定した結果を提示してもよい。
【００５７】
また、出力するデータとしては、全ての画像における形状間距離を出力してもよいが、予め設定した閾値以下の形状間距離の画像のみを出力するとよい。
検索結果は、図１２に示すように、該当する形状の線分を太くしたり、赤色などの目立つ色に変えたりして表示することにより、検索された形状をユーザに判りやすく提示することができる。
【００５８】
以上、説明したように、本実施形態の画像検索システムによれば、上記実施形態と同様な効果を奏するとともに、検索結果をユーザに視覚的に提示することができる。
【００５９】
（第３の実施の形態）
次に、本発明の実施の形態に係る画像検索装置３００について、図８を参照して詳細に説明する。図８は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
本実施形態の画像検索装置３００は、図１の上記実施の形態とは、クエリー多角形の形状をユーザがユーザインタフェースを用いて指定できる点で相違する。図８を参照すると、本実施形態の画像検索装置３００は、図１の上記実施形態の画像検索装置１００の構成に加えて、クエリー多角形情報取得部３１２と、なす角度情報算出部３１４と、をさらに含む。なお、本実施形態の画像検索装置３００は、図７の上記実施形態の画像検索装置２００の構成も含むことができる。
【００６０】
本実施形態の画像検索装置３００は、検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得部３１２と、検索クエリーの多角形情報からクエリーなす角度情報を算出するなす角度情報算出部３１４と、をさらに備え、構成直線候補抽出部１０４および形状間距離算出部１０６は、なす角度情報算出部３１４が算出したクエリーなす角度情報を用いる。
【００６１】
本実施形態において、画像検索装置３００のユーザは、ディスプレイなどの表示部（不図示）に表示された操作画面上などで、ペン型やマウス型などのポインティングデバイス（不図示）を用いることで任意の多角形形状を指定することができる。
【００６２】
形状の指定方法は、多角形の頂点を指定してもよいし、辺を組み合わせて指定してもよいし、予め用意されている多角形の位置や角度、大きさを変形させて組み合わせた形状を指定してもよい。いずれの方法においても、クエリー多角形情報取得部３１２は、ユーザが指定した多角形の辺をたどって繋がっている頂点の座標位置を順に受け付けて、クエリー頂点座標情報３０として取得する。
【００６３】
クエリー多角形情報取得部３１２は、取得した頂点を順にＶ１，Ｖ２，・・・，Ｖｎとする。
ユーザが多角形の頂点を選択する際に、参考とする画像を表示部に表示させることで、ユーザにポインティングデバイスを用いて、表示された画像中のオブジェクトの頂点位置を選択させて、選択されたオブジェクトの頂点位置をクエリー多角形情報取得部３１２が受け付けてもよい。この構成によれば、ユーザは特定のオブジェクト形状をクエリーとして容易に選択することができる。
【００６４】
なす角度情報算出部３１４は、取得した頂点Ｖｉにおけるなす角度θｉを算出し、クエリーなす角度情報１０として出力する。ここで、取得した頂点Ｖｉにおけるなす角度θｉは、ベクトルＬｉ−１＝Ｖｉ−１−Ｖｉ、Ｌｉ＝Ｖｉ−Ｖｉ＋１を用いて、以下の式（５）により算出できる。
【数１】
だたし、・は内積、｜｜はノルムを表す。
【００６５】
これを１〜ｎに対し行うことにより、クエリーなす角度情報１０を算出し、出力する。
ただし、一般に２つのベクトルのなす角度は、αを正数とした場合、αまたは１８０−αの２通りが考えられる。そこで、小さいなす角度を２つのベクトルのなす角度とすることにより、曖昧性を無くすことができる。このため、θｉが、９０度を越える場合、１８０−θｉを改めてθｉとすればよい。すなわち、以下の式（６）のようにするとよい。
θｉ ＝ｍｉｎ（θｉ、１８０−θｉ） ・・・式（６）
ここで、ｍｉｎは小さい方の値を選択する関数である。
【００６６】
以上、説明したように、本実施形態の画像検索装置３００によれば、上記実施形態と同様な効果を奏するとともに、ユーザがクエリー形状をポインティングデバイスなどを用いて簡単に指定できる。
【００６７】
（第４の実施の形態）
次に、本発明の実施の形態に係る画像検索装置４００について、図９を参照して詳細に説明する。図９は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
本実施形態の画像検索装置４００は、図８の上記実施の形態とは、ユーザが指定した多角形のクエリー形状から、回転、拡大、または移動の変化に頑強な特徴である各辺のなす角度を基に、検索対象画像の直線成分集合から、候補形状を構成する線群を抽出し、類似度判定を行う点で相違する。なお、本実施形態の画像検索装置４００は、図７の上記実施形態の画像検索装置２００の構成も含むこともできる。
【００６８】
本実施形態の画像検索装置４００は、検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得部４１２と、検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出するなす角度情報算出部４１４と、検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶部４０２と、なす角度情報算出部４１４で取得したクエリーなす角度情報の類似性に基づき、構成直線情報記憶部４０２から構成直線の組合せ候補情報を抽出する構成直線候補抽出部４０４と、構成直線候補抽出部４０４で抽出した構成直線の組合せ候補情報と、クエリー多角形情報取得部４１２で得た検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量（幾何パラメータ）を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する形状間距離算出部４０６と、を備える。
【００６９】
具体的には、図９を参照すると、本実施形態の画像検索装置４００は、クエリー多角形情報取得部４１２と、なす角度情報算出部４１４と、構成直線候補抽出部４０４と、形状間距離算出部４０６と、を備える。
【００７０】
クエリー多角形情報取得部４１２は、検索クエリーの形状を表す頂点位置または線分のいずれかを含む多角形情報を取得する。
なす角度情報算出部４１４は、前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報１０を算出する。
【００７１】
構成直線情報記憶部４０２は、検索対象画像中の輪郭を構成する直線の情報を記憶する。
構成直線候補抽出部４０４は、なす角度情報算出部４１４で取得したクエリーなす角度情報の類似性に基づき、構成直線情報記憶部４０２から構成直線の組合せ候補情報を抽出する。
【００７２】
形状間距離算出部４０６は、構成直線候補抽出部４０４で抽出した構成直線の組合せ候補情報と、クエリー多角形情報取得部４１２で得た検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量（幾何パラメータ）を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する。
【００７３】
上記第１の実施の形態と同様にして、形状間距離の算出方法としては、クエリー形状のなす角度の順列ｑ｛θｑ１，θｑ２，・・・，θｑｎ｝と、検索対象画像ｊにおける直線群のなす角度の順列Ｇｊ’＝｛θｊ１，θｊ２，・・・，θｊｎ｝を取得する。そして、対応する直線候補のうちすくなくとも３つの対応する辺の交点を２つ抽出し、幾何変換パラメータを算出し、幾何補正を施した上で形状の形状間距離を算出する。
【００７４】
２つの交点の選択基準としては、たとえば、ｎ個の点から２点を抽出する方法として、クエリー形状の頂点Ｘｑｉにおける両辺をベクトルｖｒ，ｖｌとした際の外積の絶対値｜ｖｒ×ｖｌ｜の大きい順に２つの点を選択するとよい。外積を利用する理由は、辺長の長さとなす角度の直交性を用いるためである。
【００７５】
まず、図１５を参照し、２直線Ｌ１およびＬ２の交点座標の算出精度について説明する。直線Ｌ１の幅（太さ）をΔｄとすると、Ｌ１とＬ２の交点としてユーザが選択するブレ幅は図中破線で示す範囲となる。このブレ幅はΔｄ／ｓｉｎθであり、なす角度θが直角に近いほど小さい値となる。
【００７６】
また、図１６を参照し、検索対象画像の直線抽出における直線の角度パラメータ精度について説明する。２点Ｐ１およびＰ２を通る直線Ｌ１の角度誤差Δθは、点Ｐ２の位置ブレ幅Δｄと、点間の距離Ｌを用いてΔｄ／Ｌと近似することができる。このため、点間距離Ｌである辺長が長いほど抽出される直線の角度パラメータが安定して抽出できる。
【００７７】
幾何補正方法を、以下詳細に説明する。
点Ｐ（ｘ，ｙ）からＰ’（ｘ’，ｙ’）への回転Δθ、拡大率α、並進ΔＸ，ΔＹの幾何変換は、以下の式（７）で表せる。式（７）から、２つの点Ｐ１（ｘ１，ｙ１）、Ｐ２（ｘ２，ｙ２）とそれらの幾何補正後の対応する点Ｐ１’（ｘ１’，ｙ１’）、Ｐ２’（ｘ２’，ｙ２’）の座標位置から、パラメータΔθ、α、ΔＸ，ΔＹを解くことができる。
【００７８】
【数２】
【００７９】
例えば、図５において、θｑ１とθｊ１が等しく、θｑ２とθｊ２が等しいことから、直線Ｌ１とＬ１’が対応する直線であることが判り、同様にして，Ｌ２，とＬ２’、Ｌ３とＬ３’がそれぞれ対応する直線であることが判る。対応付けられた３直線Ｌ１，Ｌ２，Ｌ３とＬ１’，Ｌ２’，Ｌ３’を用いると、Ｌ１とＬ３の交点（Ｘｑ１，Ｙｑ１）とＬ１’とＬ３’の交点（Ｘｊ１，Ｙｊ１）が対応する頂点同士であることがさらに判る。
【００８０】
同様に（Ｘｑ２，Ｙｑ２）と（Ｘｊ２，Ｙｊ２）が対応する頂点である。この２つの対応する頂点を、式（７）に代入し、連立方程式を解くことで、パラメータΔθ、α、ΔＸ，ΔＹを得ることができる。そして、検索対象画像の形状を幾何補正し、頂点をクエリー形状と同一平面に投影し、各頂点の位置のずれを算出する。位置ずれは、２点のＸ，Ｙ各座標値の差分の絶対値の和として、以下の式（８）のように求めることができる。
ｄｊ＝Σ（｜Ｘｑｉ−Ｘｊｉ｜＋｜Ｙｑｉ−Ｙｊｉ｜） ・・・式（８）
ここで、ｉ＝１〜ｎの自然数である。
【００８１】
また、差分の二乗和など、距離の公理を満たしているものであれば何を用いてもよく、上記実施形態と同様であり、これに限定されることはない。
【００８２】
なお、本実施形態の変形として、図８の実施形態の画像検索装置３００の構成に加え、構成直線候補抽出部１０４で抽出した構成直線の組合せ候補情報と、クエリー多角形情報取得部３１２で得た検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正する補正部（不図示）をさらに備え、形状間距離算出部１０６が、補正部により幾何補正した後の形状との頂点の位置ずれ量を基に形状間距離を算出する構成としてもよい。
【００８３】
上述のような構成において、本実施の形態の画像検索装置４００によるデータ処理方法を以下に説明する。図１０は、本実施形態の画像検索装置４００の動作の一例を示すフローチャートである。
【００８４】
本実施形態のデータ処理方法は、画像検索装置４００が、検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得し（ステップＳ３０１）、検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出し（ステップＳ３０３）、取得したクエリーなす角度情報の類似性に基づき、構成直線情報記憶部４０２から構成直線の組合せ候補情報を抽出し（ステップＳ１０３、ステップＳ１０５）、抽出した構成直線の組合せ候補情報と、得られた検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する（ステップＳ１０７）。
【００８５】
以下、図１０に示すフローチャートを用いて本実施形態における画像検索装置４００の動作を説明する。
図１０において、上記実施形態の図６のフローチャートのステップＳ１０３〜ステップＳ１０９と同様なステップを含むとともに、ステップＳ３０１、ステップＳ３０３、およびステップＳ３１１を、さらに含む。
ユーザがペン型ポインティングデバイスなどを用いて指定した多角形の頂点位置（座標）を順に取得し、メモリに格納する（ステップＳ３０１）。
【００８６】
例えば、ユーザがｎ角形を指定した場合、ｎ個の頂点の位置を以下のようにメモリに記録する。
Ｑ［１］．ｘ＝１０
Ｑ［１］．ｙ＝３０
Ｑ［２］．ｘ＝４０
Ｑ［２］．ｙ＝７０
：
Ｑ［ｎ］．ｘ＝１００
Ｑ［ｎ］．ｙ＝２０
Ｑ［０］．ｘ＝１００
Ｑ［０］．ｙ＝２０
このとき、ｎ角形は閉じた形状をするため、Ｑ［０］には、Ｑ［ｎ］と同じ値を代入する。
ここで、Ｑ［ｎ］．ｘ、Ｑ［ｎ］．ｙは、Ｑ［ｎ］のｘ座標およびｙ座標成分を表すものとする。
【００８７】
ｎ角形のクエリー形状が、図１１（ａ）に示すように短い辺を持ち、かつこの辺の両端のなす角Ａ，Ｂの和が１８０度を超える場合、図１１（ｂ）に示すようなｎ−１角形を想定し、クエリー形状として検索に用いるとよい。こうすることにより、検索対象画像における直線検出で短い辺が未検出となる場合でも検索することができるからである。
【００８８】
すなわち、なす角度情報算出部３１４が、クエリー多角形内の鈍角を持つ辺の両端の辺の線分を伸ばしてできる多角形を検索クエリーの多角形とし、クエリーなす角度情報を算出するとよい。
【００８９】
なす角度情報算出部３１４が、クエリー多角形情報取得部３１２で取得したクエリー多角形形状Ｑの各頂点がなす角度を算出する（ステップＳ３０３）
なす角θｉの配列（ｉ＝１、２、・・・、ｎ）は、以下の式（９）、式（１０）のように算出することができる。
θ［ｉ］＝ａｒｃｃｏｓ（（β［ｉ−１］．ｘ＊β［ｉ］．ｘ＋β［ｉ−１］．ｙ＊β［ｉ］．ｙ）／√（（β［ｉ−１］．ｘ＾２＋β［ｉ−１］．ｙ＾２）（β［ｉ］．ｘ＾２＋β［ｉ］．ｙ＾２））） ・・・式（９）
ｉｆ（θ［ｉ］＞π）｛θ［ｉ］＝π−θ［ｉ］｝ ・・・式（１０）
ここで、βは以下の式（１１）〜式（１４）により求めることができる。
β［ｉ］．ｘ＝Ｑ［ｉ＋１］．ｘ−Ｑ［ｉ］．ｘ ・・・式（１１）
β［ｉ］．ｙ＝Ｑ［ｉ＋１］．ｙ−Ｑ［ｉ］．ｙ ・・・式（１２）
β［ｉ−１］．ｘ＝Ｑ［ｉ−１］．ｘ−Ｑ［ｉ］．ｘ ・・・式（１３）
β［ｉ−１］．ｙ＝Ｑ［ｉ−１］．ｙ−Ｑ［ｉ］．ｙ ・・・式（１４）
【００９０】
構成直線情報記憶部１０２で記憶している１つの検索対象画像の直線情報を抽出する（ステップＳ１０３）。
直線情報は、配列Ｌ［Ｍ］に、なす角情報は、２次元配列Ａ［Ｍ］［Ｍ］記憶されているとする。
なす角情報が記憶されていない場合は、直線情報を用いてなす角度情報を作成する。
【００９１】
図３の例で示すと、以下のようになる。
Ｌ［１］．ρ＝ ５０、Ｌ［１］．θ＝ ６０、
Ｌ［２］．ρ＝ ６０、Ｌ［２］．θ＝ １５、
Ｌ［３］．ρ＝ ４０、Ｌ［３］．θ＝ １０５、
Ａ［１］［１］＝０， Ａ［１］［２］＝４５， Ａ［１］［３］＝４５，
Ａ［２］［１］＝４５， Ａ［２］［２］＝０， Ａ［２］［３］＝９０，
Ａ［３］［１］＝４５， Ａ［３］［２］＝９０， Ａ［３］［３］＝０
【００９２】
構成直線候補抽出部４０４では、なす角度情報算出部３１４で算出したクエリー多角形と一致する可能性のある検索対象画像の候補を構成直線情報記憶部４０２から抽出する。
クエリー多角形のなす角度の順列を表す配列θ［ｉ］と一致するなす角度の組合せを、構成直線情報記憶部４０２に記憶されているなす角情報２次元配列Ａ［Ｍ］［Ｍ］から探索する。
【００９３】
すなわち、なす角度情報算出部４１４は、検索クエリーの多角形のなす角度を隣接する順に抽出したなす角度順列情報をクエリーなす角度情報に含み、さらに、構成直線候補抽出部４０４は、なす角度順列情報を用い、構成直線情報記憶部４０２から順列にしたがい類似するなす角度を持つ構成直線の組合せを抽出する。
【００９４】
簡単なフィルタリングとして、すべてのｉ（１〜ｎ）において、以下の式（１５）を満たすｐ、ｑ（１＝＜ｐ，ｑ＜＝Ｍ）が存在する場合のみ、以後の処理を行い、存在しない場合は、ステップＳ１０３に戻り、構成直線情報記憶部１０２で記憶している別の画像の直線情報を抽出する。
｜θ［ｉ］−Ａ［ｐ］［ｑ］｜＜ｔｈ ・・・式（１５）
【００９５】
次に、θ［ｉ］（ｉ＝１〜ｎ）の順列と同様の順列をＡ［Ｍ］［Ｍ］から探索する。
探索方法としては、以下の再帰法を用いるとよい。
ステップＳ２０１：Ａ［ｐ０］［ｑ０］＝＝θ［１］となるｐ０，ｑ０を見つける。
ステップＳ２０２：Ａ［ｑ０］［ｑ］＝＝θ［２］となるｐ０以外のｑを探し、ｐ１とする。
ステップＳ２０３：Ａ［ｐ１］［ｑ］＝＝θ［３］となるｐ０、ｐ１以外のｑを探し、ｐ２とする。
ステップＳ２０４：Ａ［ｐｉ−１］［ｑ］＝＝θ［ｉ］となるｐｊ（ｊ＝０，…，ｉ−１）以外のｑを探し、ｐｉとする。
ステップＳ２０５：ｉ＜ｎならばｉ＝ｉ＋１としてステップＳ２０４を繰り返す。
ステップＳ２０６：ｉ＝ｎ、かつ、ｐｉ＝ｐ０であれば抽出した頂点のなす角度順列と同一の構成直線の組合せｐｊ（１，２，・・・，ｎ）を出力する。それ以外は組合せがないものとする。
このように頂点のなす角度順列と同一の構成直線の組合せｐｊ（１，２，・・・，ｎ）を取得する（ステップＳ１０５）。
【００９６】
形状間距離算出部４０６では、構成直線候補抽出部４０４で検出したクエリー多角形の辺とそれに対応する直線候補を抽出した画像ごとに、形状間距離を算出する（ステップＳ１０７）。
ｐｊの組が得られた場合は、ｐａおよびｐｂの２直線の交点（Ｘｂ，Ｙｂ）を求めることで、１つの頂点座標を算出することができる。これをｎ個のペアに対して行うことで、ｎ角形の頂点座標（Ｘｉ，Ｙｉ）を算出する。このようにして抽出したｎ角形の頂点座標（Ｘｉ，Ｙｉ）（ｉ＝１〜ｎの自然数）と、クエリー多角形（Ｑ［ｉ］．ｘ，Ｑ［ｉ］．ｙ）との対応から、幾何変形パラメータα、Δθ、ΔＸ，ΔＹを算出する。ｎ個の頂点のうち２つを用いて式（７）に代入し、連立方程式を解くことで得られる。
【００９７】
得られたパラメータを基に、クエリー多角形（Ｑ［ｉ］．ｘ，Ｑ［ｉ］．ｙ）を上記式（７）のＸ，Ｙに代入することにより、幾何変形後のクエリー多角形（Ｑ［ｉ］’．ｘ，Ｑ［ｉ］’．ｙ）を算出できる。
【００９８】
形状間距離は、幾何変形後のクエリー多角形（Ｑ［ｉ］’．ｘ，Ｑ［ｉ］’．ｙ）と、抽出したｎ角形の頂点座標（Ｘｉ，Ｙｉ）との距離を以下の式（１６）によって算出することで得られる。ここで、ｉ＝１〜ｎの自然数。
ｄ＝Σ（｜Ｑ［ｉ］．ｘ−Ｘｊ｜＋｜Ｑ［ｉ］．ｙ−Ｙｊ｜） ・・・式（１６）
また、距離の算出はこれに限らず、距離の公理を満たすものであればどのようなものを用いてもよい。
【００９９】
構成直線情報記憶部４０２に記憶されている全ての検索対象画像に対して処理が行われたかを確認し、行われていない場合は（ステップＳ１０９のＮＯ）、ステップＳ１０３へ戻り、新たな検索対象画像を抽出する。
構成直線情報記憶部４０２に記憶されている全ての検索対象画像に対して処理が行われた場合（ステップＳ１０９のＹＥＳ）、算出した形状間距離を距離の短い順にソートする。ソートした形状に対応する画像情報を距離の短い順に検索結果として画面に表示する（ステップＳ３１１）。
【０１００】
以上、説明したように、本実施形態の画像検索装置４００によれば、上記実施形態と同様な効果を奏するとともに、回転、移動、またはスケール変動に頑強な検索が行えることができるという効果がある。その理由は、回転、移動、またはスケール変動に不変な多角形の隣接する辺のなす角度の順列を用いて検索対象画像群から同一順列のなす角度を保有する線の候補を抽出し、類似度を判定するためである。
【０１０１】
（第５の実施の形態）
次に、本発明の実施の形態に係る画像検索装置５００について、図１３を参照して詳細に説明する。図１３は、本発明の実施の形態に係る画像検索装置の構成を示す機能ブロック図である。
本実施形態の画像検索装置５００は、図９の上記実施の形態とは、クエリー多角形の内部領域に対応する視覚的特徴量もさらに考慮して距離を算出する点で相違する。
【０１０２】
本実施形態の画像検索装置５００は、クエリー多角形情報取得部４１２で取得した検索クエリーの多角形の形状を表す頂点の位置および線分のすくなくとも１つを含む情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出するクエリー視覚的特徴量抽出部５２２と、検索対象画像の色およびエッジのすくなくとも１つを含む情報を記録する検索対象画像情報記憶部２０２と、構成直線候補抽出部４０４において抽出された構成直線が囲む領域における検索対象画像の視覚的特徴量を、検索対象画像情報記憶部２０２に記憶されている情報を基に抽出する視覚的特徴量抽出部５２４と、クエリー視覚的特徴量抽出部５２２と視覚的特徴量抽出部５２４で抽出した視覚的特徴量の距離を算出する視覚的特徴量距離算出部５２６と、形状間距離算出部４０６と視覚的特徴量距離算出部５２６とで算出した距離を基に総合距離を算出する総合距離算出部５２８と、をさらに備える。
【０１０３】
図１３を参照すると、本実施形態の画像検索装置５００は、図９の上記実施形態の画像検索装置４００の構成に加えて、クエリー視覚的特徴量抽出部５２２と、視覚的特徴量抽出部５２４と、視覚的特徴量距離算出部５２６と、総合距離算出部５２８と、をさらに含む。なお、本実施形態の画像検索装置５００は、図８の上記実施形態の画像検索装置の構成も含むことができる。
【０１０４】
クエリー視覚的特徴量抽出部５２２は、クエリー多角形情報取得部４１２で取得したクエリー多角形を表す頂点の位置や線分の情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出する。視覚的特徴量を抽出する方法として、該当領域の色に関する特徴量であるドミナントカラー（Dominant Color）（配色全体の印象を支配する色）や対象領域内の色の配置に関する特徴であるカラーレイアウト（Color Layout）、または、模様に関する特徴であるエッジヒストグラムなどの特徴を抽出するとよい。これらの特徴量は予め複数のサンプル色やサンプルパターンに対して作成しておき、ユーザに選択してもらってもよいし、ユーザが検索クエリーの多角形を選択する際に特徴量を抽出するべき画像とその画像内の領域を指定し、その画像の領域から特徴量を算出してもよい。
【０１０５】
視覚的特徴量抽出部５２４は、構成直線候補抽出部４０４において抽出された構成直線によって囲まれる領域における検索対象画像の視覚的特徴量を抽出する。検索対象画像情報記憶部２０２に記憶されている画像情報から、構成直線が囲む領域に対応する画素の色およびエッジなどを抽出し、Ｄｏｍｉｎａｎｔ ＣｏｌｏｒやＣｏｌｏｒ Ｌａｙｏｕｔ、エッジヒストグラムなどの特徴量を算出する。ここで算出される特徴量は上述したクエリー視覚的特徴量抽出部５２２と同一のものを用いる。また、検索対象画像を細かな領域に分割しておき、分割した領域ごとに特徴量を抽出して予め記憶しておくことにより、構成直線が囲む領域に対する特徴量を、範囲内の分割領域の特徴量で代用することにより特徴量の算出処理を省くことができる。
【０１０６】
視覚的特徴量距離算出部５２６は、クエリー視覚的特徴量抽出部５２２と、視覚的特徴量抽出部５２４でそれぞれ抽出した視覚的特徴量の距離である視覚的特徴量距離を算出する。視覚的特徴量距離の算出方法として、視覚的特徴量間のユークリッド距離を用いるとよい。具体的には、視覚的特徴量の各次元での値の差分の２乗をすべての次元において算出し、総和の平方根をとることで距離を算出することができる。差分の２乗の他にも、差分の絶対値など、距離の公理を満たしているものであれば何を用いてもよく、これに限定されることはない。
【０１０７】
総合距離算出部５２８は、形状間距離算出部４０６と、視覚的特徴量距離算出部５２６で算出した２つの距離を用いて統合距離を算出する。距離算出は、２つの距離を足し合わせたり、形状と視覚的の類似度の重要性に応じてそれぞれ重み付けした距離を足し合わせたりして求めることができる。
【０１０８】
検索対象画像情報記憶部２０２と検索結果表示部２０４は、図７の上記実施形態で説明したものと同じであるが、本実施形態では、検索対象画像情報記憶部２０２に、視覚的特徴量の算出に用いるためオリジナル画像やサムネイル画像を記憶しておくとさらによい。
【０１０９】
このように構成された本実施形態の動作について、図１４を用いて以下に説明する。図１４は、本発明の実施の形態に係る画像検索装置の動作の一例を示すフローチャートである。本実施形態では、図１０の上記実施形態の画像検索装置４００のフローチャートで、各画像の形状間距離を求めるとともに、以下の処理を行う。
【０１１０】
まず、クエリー視覚的特徴量抽出部５２２が、クエリー多角形情報取得部４１２で取得したクエリー多角形を表す頂点の位置や線分の情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出する（ステップＳ５０１）。
【０１１１】
そして、視覚的特徴量抽出部５２４が、構成直線候補抽出部４０４において抽出された構成直線によって囲まれる領域における検索対象画像の視覚的特徴量を抽出する（ステップＳ５０３）。さらに、視覚的特徴量距離算出部５２６が、クエリー視覚的特徴量抽出部５２２と、視覚的特徴量抽出部５２４でそれぞれ抽出した視覚的特徴量の距離である視覚的特徴量距離を算出する（ステップＳ５０５）。そして、総合距離算出部５２８が、形状間距離算出部４０６と、視覚的特徴量距離算出部５２６で算出した２つの距離を用いて統合距離を算出し、出力する（ステップＳ５０７）。
【０１１２】
出力された総合距離は、上記第２の実施の形態における形状間距離と同様な方法でユーザに提示することができる。
【０１１３】
以上、説明したように、本実施形態の画像検索装置５００によれば、上記実施形態と同様な効果を奏するとともに、クエリー多角形の内部領域の視覚的特徴量を考慮して距離を算出できるので、輪郭だけでなく、よりクエリーに類似した画像を検出できるとともに、検索処理の負荷を低減できる。
【０１１４】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【０１１５】
また、図１３の上記実施形態の画像検索装置５００において、画像検索装置４００は、図１、図２または図７の上記実施形態の画像検索装置の構成とすることもできる。この場合は、クエリー視覚的特徴量抽出部５２２は、ユーザが選択したサンプル色またはパターンに対する視覚的情報を、クエリー多角形の内部領域に対応する視覚的情報として抽出する。また、視覚的特徴量抽出部５２４は、構成直線候補抽出部１０４において抽出された構成直線によって囲まれる領域における検索対象画像の視覚的特徴量を抽出する。また、総合距離算出部５２８は、形状間距離算出部１０６形状間距離算出部４０６と、視覚的特徴量距離算出部５２６で算出した２つの距離を用いて統合距離を算出する。
【０１１６】
また、図９の上記実施形態において、図１０のステップＳ３１１で、検索結果を表示する際に、ソートした形状に対応する画像情報を、図７の画像検索装置２００の検索対象画像情報記憶部２０２から取得し、距離の短い順にオリジナル画像やサムネイル画像を表示するように構成してもよい。この構成によれば、検索結果をユーザに視覚的に分かり易く提示することができる。
【０１１７】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【０１１８】
１ クエリーなす角度情報
１２ 対応する構成直線の候補情報
１４ 形状間距離
３０ クエリー頂点座標情報
１００ 画像検索装置
１０２ 構成直線情報記憶部
１０４ 構成直線候補抽出部
１０６ 形状間距離算出部
２００ 画像検索装置
２０２ 検索対象画像情報記憶部
２０４ 検索結果表示部
３００ 画像検索装置
３１２ クエリー多角形情報取得部
３１４ 角度情報算出部
４００ 画像検索装置
４０２ 構成直線情報記憶部
４０４ 構成直線候補抽出部
４０６ 形状間距離算出部
４１２ クエリー多角形情報取得部
４１４ なす角度情報算出部
５００ 画像検索装置
５２２ クエリー視覚的特徴量抽出部
５２４ 視覚的特徴量抽出部
５２６ 視覚的特徴量距離算出部
５２８ 総合距離算出部
【特許請求の範囲】
【請求項１】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
を備える画像検索装置。
【請求項２】
請求項１に記載の画像検索装置において、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得手段と、
前記検索クエリーの多角形情報からクエリーなす角度情報を算出するなす角度情報算出手段と、
をさらに備え、
前記構成直線候補抽出手段および前記形状間距離算出手段は、前記なす角度情報算出手段が算出した前記クエリーなす角度情報を用いる画像検索装置。
【請求項３】
請求項２に記載の画像検索装置において、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と、前記クエリー多角形情報取得手段で得た前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正する補正手段をさらに備え、
前記形状間距離算出手段は、前記補正手段により幾何補正した後の形状との頂点の位置ずれ量を基に前記形状間距離を算出する画像検索装置。
【請求項４】
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得手段と、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出するなす角度情報算出手段と、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
前記なす角度情報算出手段で取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と、前記クエリー多角形情報取得手段で得た前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する形状間距離算出手段と、
を備える画像検索装置。
【請求項５】
請求項２乃至４いずれかに記載の画像検索装置において、
前記なす角度情報算出手段は、前記クエリー多角形内の鈍角を持つ辺の両端の辺の線分を伸ばしてできる多角形を前記検索クエリーの多角形とし、前記クエリーなす角度情報を算出することを特徴とする画像検索装置。
【請求項６】
請求項１または４に記載の画像検索装置において、
前記なす角度情報算出手段は、検索クエリーの多角形のなす角度を隣接する順に抽出したなす角度順列情報をクエリーなす角度情報に含み、
前記構成直線候補抽出手段は、なす角度順列情報を用い、前記構成直線情報記憶手段から順列にしたがい類似するなす角度を持つ構成直線の組合せを抽出する画像検索装置。
【請求項７】
請求項４に記載の画像検索装置において、
クエリー多角形情報取得手段で取得した前記検索クエリーの多角形の形状を表す頂点の位置および線分のすくなくとも１つを含む情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出するクエリー視覚的特徴量抽出手段と、
検索対象画像の色およびエッジのすくなくとも１つを含む情報を記録する検索対象画像情報記憶手段と、
構成直線候補抽出手段において抽出された構成直線が囲む領域における検索対象画像の視覚的特徴量を、前記検索対象画像情報記憶手段に記憶されている情報を基に抽出する視覚的特徴量抽出手段と、
前記クエリー視覚的特徴量抽出手段と前記視覚的特徴量抽出手段で抽出した視覚的特徴量の距離を算出する視覚的特徴量距離算出手段と、
前記形状間距離算出手段と前記視覚的特徴量距離算出手段とで算出した距離を基に総合距離を算出する総合距離算出手段と、
をさらに備える画像検索装置。
【請求項８】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した前記構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する画像検索装置のデータ処理方法。
【請求項９】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得し、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出し、
取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した前記構成直線の組合せ候補情報と、得られた前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する画像検索装置のデータ処理方法。
【請求項１０】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
算出された前記形状間距離をユーザに提示する提示手段と、
を備える画像検索システム。
【請求項１】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
を備える画像検索装置。
【請求項２】
請求項１に記載の画像検索装置において、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得手段と、
前記検索クエリーの多角形情報からクエリーなす角度情報を算出するなす角度情報算出手段と、
をさらに備え、
前記構成直線候補抽出手段および前記形状間距離算出手段は、前記なす角度情報算出手段が算出した前記クエリーなす角度情報を用いる画像検索装置。
【請求項３】
請求項２に記載の画像検索装置において、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と、前記クエリー多角形情報取得手段で得た前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正する補正手段をさらに備え、
前記形状間距離算出手段は、前記補正手段により幾何補正した後の形状との頂点の位置ずれ量を基に前記形状間距離を算出する画像検索装置。
【請求項４】
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得するクエリー多角形情報取得手段と、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出するなす角度情報算出手段と、
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
前記なす角度情報算出手段で取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した前記構成直線の組合せ候補情報と、前記クエリー多角形情報取得手段で得た前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する形状間距離算出手段と、
を備える画像検索装置。
【請求項５】
請求項２乃至４いずれかに記載の画像検索装置において、
前記なす角度情報算出手段は、前記クエリー多角形内の鈍角を持つ辺の両端の辺の線分を伸ばしてできる多角形を前記検索クエリーの多角形とし、前記クエリーなす角度情報を算出することを特徴とする画像検索装置。
【請求項６】
請求項１または４に記載の画像検索装置において、
前記なす角度情報算出手段は、検索クエリーの多角形のなす角度を隣接する順に抽出したなす角度順列情報をクエリーなす角度情報に含み、
前記構成直線候補抽出手段は、なす角度順列情報を用い、前記構成直線情報記憶手段から順列にしたがい類似するなす角度を持つ構成直線の組合せを抽出する画像検索装置。
【請求項７】
請求項４に記載の画像検索装置において、
クエリー多角形情報取得手段で取得した前記検索クエリーの多角形の形状を表す頂点の位置および線分のすくなくとも１つを含む情報を基に、クエリー多角形の内部領域に対応する視覚的情報を抽出するクエリー視覚的特徴量抽出手段と、
検索対象画像の色およびエッジのすくなくとも１つを含む情報を記録する検索対象画像情報記憶手段と、
構成直線候補抽出手段において抽出された構成直線が囲む領域における検索対象画像の視覚的特徴量を、前記検索対象画像情報記憶手段に記憶されている情報を基に抽出する視覚的特徴量抽出手段と、
前記クエリー視覚的特徴量抽出手段と前記視覚的特徴量抽出手段で抽出した視覚的特徴量の距離を算出する視覚的特徴量距離算出手段と、
前記形状間距離算出手段と前記視覚的特徴量距離算出手段とで算出した距離を基に総合距離を算出する総合距離算出手段と、
をさらに備える画像検索装置。
【請求項８】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した前記構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する画像検索装置のデータ処理方法。
【請求項９】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶装置を有する画像検索装置のデータ処理方法であって、
前記画像検索装置が、
検索クエリーの形状を表す、頂点位置または線分のいずれかを含む多角形情報を取得し、
前記検索クエリーの多角形情報から多角形のなす角度を含むクエリーなす角度情報を算出し、
取得した前記クエリーなす角度情報の類似性に基づき、前記構成直線情報記憶装置から構成直線の組合せ候補情報を抽出し、
抽出した前記構成直線の組合せ候補情報と、得られた前記検索クエリーの多角形情報とから、多角形の移動、回転、およびスケールのうち少なくとも１つの幾何変形量を算出して幾何補正した後の形状との頂点の位置ずれ量を基に距離を算出する画像検索装置のデータ処理方法。
【請求項１０】
検索対象画像中の輪郭を構成する直線の情報を記憶する構成直線情報記憶手段と、
検索クエリーの多角形のなす角度を含むクエリーなす角度情報の類似性に基づき、前記構成直線情報記憶手段から構成直線の組合せ候補情報を抽出する構成直線候補抽出手段と、
前記構成直線候補抽出手段で抽出した構成直線の組合せ候補情報と前記クエリーなす角度情報とから、形状間距離を算出する形状間距離算出手段と、
算出された前記形状間距離をユーザに提示する提示手段と、
を備える画像検索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１１−２５３４４２（Ｐ２０１１−２５３４４２Ａ）
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願番号】特願２０１０−１２８１５７（Ｐ２０１０−１２８１５７）
【出願日】平成２２年６月３日（２０１０．６．３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願日】平成２２年６月３日（２０１０．６．３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]