(57)【要約】【課題】  大量のデータ画像の中からクエリー画像に類似する画像を漏れなく抽出する画像検索方法、装置およびプログラムを提供する。【解決手段】データ画像に属する画素を３次元の色空間に写像する写像手段７と、前記色空間に写像されたクエリー画像に属する全ての画素の集合の重心と前記色空間の原点を通る直線を回転軸とし、前記原点を頂点とする円錐であって、前記クエリー画像に属する全ての画素をその内側の領域に包含する最小の円錐(以下クエリー円錐と言う。）の外側の領域に存在する前記データ画像の画素の数（以下、「画素の数」と言う。）を計数する計数手段８と、前記画素の数が所定の閾値より小さい場合に前記データ画像を前記クエリー画像に近似する画像と判定する閾値判定手段９とを備える  【選択図】        図１
2006268799.tif 000002
【特許請求の範囲】
【請求項１】
データ画像に属する画素を３次元の色空間に写像する写像ステップと、  前記色空間に写像されたクエリー画像に属する全ての画素の集合の重心と前記色空間の原点を通る直線を回転軸とし、前記原点を頂点とする円錐であって、前記クエリー画像に属する全ての画素をその内側の領域に包含する最小の円錐(以下クエリー円錐と言う。）の外側の領域に存在する前記データ画像の画素の数（以下、「画素の数」と言う。）を計数する計数ステップと、
前記画素の数が所定の閾値より小さい場合に前記データ画像を前記クエリー画像に近似する画像と判定する閾値判定ステップと
を有する画像検索方法。
【請求項２】
第１の色空間に写像されたクエリー画像の全ての画素の集合の重心を算出する重心算出ステップと、
前記第１の色空間の原点を原点とし、前記重心と前記第１の色空間の原点を結ぶ直線を第１の座標軸とする第２の色空間を定義する色空間設定ステップと、
前記第２の色空間において、クエリー円錐の頂角と高さを算出するクエリー円錐算出ステップとを有し、
前記写像ステップは前記データ画像を前記第２の色空間に写像すること
を特徴とする請求項１に記載の画像検索方法。
【請求項３】
前記第２の色空間は、直交座標系で定義される３次元色空間であることを特徴とする請求項２に記載の画像検索方法。
【請求項４】
前記第２の色空間は、円筒座標系で定義される３次元色空間であることを特徴とする請求項２に記載の画像検索方法。
【請求項５】
データ画像に属する画素を３次元の色空間に写像する写像手段と、
前記色空間に写像されたクエリー画像に属する全ての画素の集合の重心と前記色空間の原点を通る直線を回転軸とし、前記原点を頂点とする円錐であって、前記クエリー画像に属する全ての画素をその内側の領域に包含する最小の円錐(以下クエリー円錐と言う。）の外側の領域に存在する前記データ画像の画素の数（以下、「画素の数」と言う。）を計数する計数手段と、
前記画素の数が所定の閾値より小さい場合に前記データ画像を前記クエリー画像に近似する画像と判定する閾値判定手段と
を備える画像検索装置。
【請求項６】
第１の色空間に写像されたクエリー画像の全ての画素の集合の重心を算出する重心算出手段と、
前記第１の色空間の原点を原点とし、前記重心と前記第１の色空間の原点を結ぶ直線を第１の座標軸とする第２の色空間を定義する色空間設定手段と、
前記第２の色空間において、クエリー円錐の頂角と高さを算出するクエリー円錐手段とを備え、
前記写像手段は前記データ画像を前記第２の色空間に写像することを特徴とする請求項１に記載の画像検索装置。
【請求項７】
前記第２の色空間は、直交座標系で定義される３次元色空間であることを特徴とする請求項２に記載の画像検索装置。
【請求項８】
前記第２の色空間は、円筒座標系で定義される３次元色空間であることを特徴とする請求項２に記載の画像検索装置。
【請求項９】
請求項１乃至請求項４に記載の画像検索方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量のデータ画像の中からクエリー画像と類似する画像を抽出する画像検索方法、装置及びプログラムに関する。
【背景技術】
【０００２】
画像データベースに蓄えられた大量のデータ画像の中からクエリー画像と同一又は類似する画像を抽出する方法、装置については多くの提案がなされている。例えば、特許文献１には、入力画像中の被写体の形状情報およびテクスチャ情報を抽出して、データベース中の各画像との類似度を算出し、算出された類似度に基づいて、入力画像と類似している類似画像データを検索する類似画像検索装置が開示されている。
【０００３】
しかしながら、クエリー画像と大量のデータ画像の間の類似度を全て算出するのは、時間がかかるという問題がある。また、大部分のデータ画像はクエリー画像とは大きく異なるのが普通だから、全てのデータ画像について精密な検索を行うことは意味がない。そこで、簡易な方法で粗検索を行って、「クエリー画像との差異が大きいデータ画像」を精密検索の対象から排除して、残ったデータ画像に対して精密検索を行うことが行われている。
【０００４】
例えば、特許文献２には、一枚の画像中で使用されている代表色を予め抽出して色空間上にマッピングしておき、画像検索の際に入力して描いた問い合わせ画像の中で使用されている色情報を前記色空間上に投影した後にその近傍にマッピングされている画像に対してのみ整合・評価を行う画像検索方法が開示されている。
【０００５】
【特許文献１】特開２００５−２４３１７８号公報
【特許文献２】特開平６−２４３１７８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
特許文献２に記載の発明は、色空間上にマッピングされたデータ画像の代表色とクエリー画像の色情報の遠近に基づいて粗検索を行った後で、精密検索を行うので、画像検索の高速化が期待できる。しかしながら、代表色の選び方によって、検索漏れが生じるおそれがある。すなわち、代表色はデータ画像の特定の領域の色であるが、クエリー画像の特徴が当該特定の領域にはない場合はクエリー画像に類似するデータ画像を抽出できないという問題が生じる。
【０００７】
本発明は、上記の課題に鑑みてなされたものであり、大量のデータ画像の中からクエリー画像に類似する画像を漏れなく抽出する画像検索方法、装置を提供するものである。
【課題を解決するための手段】
【０００８】
本発明に係る画像検索方法の第１の構成は、データ画像に属する画素を３次元の色空間に写像する写像ステップと、前記色空間に写像されたクエリー画像に属する全ての画素の集合の重心と前記色空間の原点を通る直線を回転軸とし、前記原点を頂点とする円錐であって、前記クエリー画像に属する全ての画素をその内側の領域に包含する最小の円錐(以下クエリー円錐と言う。）の外側の領域に存在する前記データ画像の画素の数（以下、「画素の数」と言う。）を計数する計数ステップと、前記画素の数が所定の閾値より小さい場合に前記データ画像を前記クエリー画像に近似する画像と判定する閾値判定ステップとを有するものである。
【０００９】
この構成によれば、円錐という比較的単純な立体図形を用いて領域を設定し、データ画像の画素がその領域に属すか否かという単純な論理で検索を行うので、高速検索が可能になる。
【００１０】
本発明に係る画像検索方法の第２の構成は、前記第１の構成において、第１の色空間に写像されたクエリー画像の全ての画素の集合の重心を算出する重心算出ステップと、前記第１の色空間の原点を原点とし、前記重心と前記第１の色空間の原点を結ぶ直線を第１の座標軸とする第２の色空間を定義する色空間設定ステップと、前記第２の色空間において、クエリー円錐の頂角と高さを算出するクエリー円錐算出ステップとを有し、前記写像ステップは前記データ画像を前記第２の色空間に写像することを特徴とする。
【００１１】
この構成によれば、データ画像をクエリー円錐の回転軸を座標軸とする座標系で定義される空間に写像するので、前記データ画像の画素がクエリー円錐の領域のどちら側にあるかを判定する演算が簡単になる。
【００１２】
本発明に係る画像検索方法の第３の構成は、前記第２の構成において、前記第２の色空間は、直交座標系で定義される３次元色空間であることを特徴とする。
【００１３】
この構成によれば、前記データ画像の写像は線形変換のみで行えるので、演算がさらに簡単になる。
【００１４】
本発明に係る画像検索方法の第４の構成は、前記第２の構成において、前記第２の色空間は、円筒座標系で定義される３次元色空間であることを特徴とする。
【００１５】
この構成によれば、円筒座標系でクエリー円錐の領域を記述するので、前記データ画像の画素がクエリー円錐の領域のどちら側にあるかを計算する演算が、さらに簡単になる。
【００１６】
本発明に係る画像検索装置の第１の構成は、データ画像に属する画素を３次元の色空間に写像する写像手段と、前記色空間に写像されたクエリー画像に属する全ての画素の集合の重心と前記色空間の原点を通る直線を回転軸とし、前記原点を頂点とする円錐であって、前記クエリー画像に属する全ての画素をその内側の領域に包含する最小の円錐(以下クエリー円錐と言う。）の外側の領域に存在する前記データ画像の画素の数（以下、「画素の数」と言う。）を計数する計数手段と、前記画素の数が所定の閾値より小さい場合に前記データ画像を前記クエリー画像に近似する画像と判定する閾値判定手段とを備えるものである。
【００１７】
本発明に係る画像検索装置の第２の構成は、前記第１の構成において、第１の色空間に写像されたクエリー画像の全ての画素の集合の重心を算出する重心算出手段と、前記第１の色空間の原点を原点とし、前記重心と前記第１の色空間の原点を結ぶ直線を第１の座標軸とする第２の色空間を定義する色空間設定手段と、前記第２の色空間において、クエリー円錐の頂角と高さを算出するクエリー円錐算出手段とを備え、前記写像手段は前記データ画像を前記第２の色空間に写像することを特徴とする。
【００１８】
本発明に係る画像検索装置の第３の構成は、前記第２の構成において、前記第２の色空間は、直交座標系で定義される３次元色空間であることを特徴とする。
【００１９】
本発明に係る画像検索装置の第４の構成は、前記第２の構成において、前記第２の色空間は、円筒座標系で定義される３次元色空間であることを特徴とする請求項２に記載の画像検索装置。
【００２０】
本発明に係るプログラムは、前記第１乃至第４の構成に係る画像検索方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２１】
以上説明したように、本発明によれば、大量のデータ画像の中からクエリー画像に類似する画像を漏れなく、高速で抽出することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例】
【００２３】
〔画像検索装置〕
図１は、本発明の実施例に係る画像検索装置の概念的な構成図であり、画像検索装置１は画像入力手段２、重心算出手段３、色空間設定手段４、クエリー円錐算出手段５、画像データベース６、写像手段７、計数手段８および閾値判定手段９から構成される。
【００２４】
画像入力手段２は、画像検索のためのクエリー画像を入力するインターフェイスである。クエリー画像はデジタルカメラ等の撮像手段から直接入力される他、記録媒体からの入力、通信回線等を経由する他の情報機器から入力などの入力形態を選択することができる。また、画像入力手段２は画像データベース６に記憶されるデータ画像の入力にも使用される。
【００２５】
重心算出手段３は、ＲＧＢ空間に写像された前記クエリー画像に属する全ての画素の重心ＣＧを算出する手段である。なお、重心算出の具体的な手法は後述する。
【００２６】
色空間設定手段４は、前記ＲＧＢ空間の座標原点を原点とし、前記座標原点と前記重心を結ぶ直線を第１の座標軸とする新たな座標系によって定義される新たな色空間を設定する手段である。なお、色空間設定の具体的な手法は後述する。  
【００２７】
クエリー円錐算出手段５は、クエリー円錐の高さと頂角を算出する手段である。本明細書において、クエリー円錐とは前記新たな色空間において、前記新たな色空間に写像された前記クエリー画像に属する全ての画素の集合の重心と前記新たな色空間の原点を通る直線を回転軸とし、前記原点を頂点とする円錐であって、前記クエリー画像に属する全ての画素をその内側の領域に包含する最小の円錐を言う。前記クエリー円錐と前記新たな座標系の定義によれば、前記クエリー円錐の頂点は常に前記新たな座標系の原点にあって、前記クエリー円錐の回転軸は常に前記新たな座標系の前記第１の座標軸に一致するから、高さと頂角を算出すれば、前記新たな色空間において前記クエリー円錐を一意に決定することができる。なお、クエリー円錐算出の具体的な手法は後述する。
【００２８】
画像データベース６は、検索対象の画像データを記憶して、適宜読み出せるようにした記憶手段である。
【００２９】
計数手段８は、画像データベース６から読み出した前記画像データに属する画素の集合を前記新たな色空間に写像して、前記写像された画素の内、前記クエリー円錐の外側の領域に存在する画素を計数する手段である。
【００３０】
閾値判定手段９は、計数手段８で計数した画素数を所定の閾値で判別して、前記画素数が前記閾値を下回る場合に、当該データ画像をクエリー画像に近似する画像であると判定する手段である。なお、判定結果は図示しない出力装置に出力される。
【００３１】
画像検索装置１はコンピュータに画像入力手段２、重心算出手段３、色空間設定手段４、クエリー円錐算出手段５、写像手段７、計数手段８および判定手段９の処理手順を記述したプログラムをインストールし、当該コンピュータの記憶装置に画像データベース６を備えることで実現できる。前記コンピュータは、既成のパーソナルコンピュータ等の中から適当な機種を選択すれば良いが、専用のハードウェアを設計して、ボードあるいはチップに纏めてもよい。
【００３２】
〔画像検索方法〕
図１は本発明の実施例に係る画像検索方法を示すフローチャートであり、図２はＲＧＢ空間に写像したクエリー画像に属する画素の集合を示す図であり、図３は、前記画素の集合の重心を説明する図であり、図４は、新たな色空間とクエリー円錐を説明する図である。以下、図２に付したステップ番号を追いながら、本発明の実施例に係る画像検索方法を説明する。また、図１及び図３乃至図５に付した符号も適宜引用する。
【００３３】
〔ステップ１〕クエリー画像を読み込む。
【００３４】
〔ステップ２〕前記クエリー画像に属する全ての画素の集合をＲＧＢ色空間に写像し、ＲＧＢ色空間における前記画素の集合の重心を算出する。ここで、ＲＧＢ色空間とは、画素の赤（Ｒ）、緑（Ｇ）および青（Ｂ）の各色成分の輝度を直交３軸の座標系の各軸に取る色空間であり、前記クエリー画像に属する画素１０は、図３に示すように、ＲＧＢ空間上に分布する。
【００３５】
ＲＧＢ色空間に写像された前記クエリー画像に属する画素１０をＰi（Ｒi，Ｇi，Ｂi）で表すことにすると、ＲＧＢ色空間に写像された前記クエリー画像に属する全ての画素の集合｛Ｐi｜ｉ＝１，２…，Ｎ｝の重心ＣＧの座標（ＲＧ，ＧＧ，ＢＧ）は下記の式（１）で得られる。
【００３６】
【数１】
2006268799.tif 000003
【００３７】
〔ステップ３〕重心ＣＧの座標（ＲＧ，ＧＧ，ＢＧ）が決定すると、図４に示すように、ＲＧＢ色空間の座標原点Ｏと重心ＣＧを結ぶ直線１１が決定するので、直線１１を基準とする新らたな座標系に基づく色空間を設定する。ここでは、つぎのルールによって新たな直交座標系ＸＹＺを設定する。
【００３８】
（１）ＲＧＢ色空間の座標原点Ｏを直交座標系ＸＹＺの座標原点とする。
（２）直線１１をＺ軸にする。
（３）前記座標原点を通る直線であって、ＲＢ平面内にあって、Ｚ軸に直交する直線をＸ軸にする。
（４）Ｚ軸およびＸ軸に直交する直線をＹ軸にする。
（５）前記座標原点から重心ＣＧに向かう方向をＺ軸の正の方向に決め、他の軸の正の方向は３軸が右手系になるように決める。
以上のようにして、図４に示すような新たな直交座標系ＸＹＺが設定される。
【００３９】
なお、新たな座標系は上記のような座標系には限られない、例えば、直線１１を回転軸とする円筒座標を新たな座標系とすれば、後述するクエリー円錐の取り扱いに便利である。
【００４０】
〔ステップ４〕次に、直交座標系ＸＹＺにおいて、クエリー円錐１２の高さｈと、頂角θを算出する。クエリー円錐１２の頂点と回転軸は、定義により、直交座標系ＸＹＺの座標原点とＺ軸に一致するので、高さｈと頂角θが決定されれば、直交座標系ＸＹＺにおいてクエリー円錐１２を一意に決定することができる。
【００４１】
そこで、まずＲＧＢ色空間上のクエリー画像に属する全ての画素の集合｛Ｐi｜ｉ＝１，２…，Ｎ｝を、直交座標系ＸＹＺで定義される新たな色空間に写像した画素の集合｛Ｐ'i｜i＝１，２…，Ｎ｝を求める。画素Ｐ'iの座標を（Ｘi，Ｘi，Ｚi）と置くと、クエリー円錐１２の高さｈと、頂角θは、次の式（２）及び式（３）によって算出できる。
【００４２】
【数２】
2006268799.tif 000004
【００４３】
〔ステップ５〕データ画像データベース６からデータ画像を読み出す。
【００４４】
〔ステップ６〕前記データ画像に属する全ての画素の集合を直交座標系ＸＹＺで定義される新たな色空間に写像して、画素の集合｛Ｑｊ｜ｊ＝１，２…，Ｍ｝を求める。
【００４５】
〔ステップ７〕さらに、集合｛Ｑｊ｜ｊ＝１，２…，Ｍ｝に属する画素の内、クエリー円錐１２の外側の領域に存在する画素の数を計数する。ここで、画素Ｑｊの座標を（Ｘ'ｊ，Ｙ'ｊ，Ｚ'ｊ）とすると、下記の式（４）又は式（５）のいずれかを満たす場合に画素Ｑｊはクエリー円錐１２の外側の領域に存在する。
【００４６】
【数３】
2006268799.tif 000005
【００４７】
〔ステップ８〕前ステップで計数した画素の数を、所定の閾値と較べて、前記画素の数が前記閾値よりも小さければ当該データ画像はクエリー画像に近似する画像であると判断する。なお、前記閾値は、検索対象の画像の特性（例えば、データ画像相互の分散の大きさ）あるいは目的（精密検索か、粗検索か）に応じて、適当な値を与える。また、前記閾値は絶対値で設定してもよいし、相対値（例えば、データ画像に属する画素の総数Ｍに対する比率）で設定してもよい。
【００４８】
〔ステップ９〕全てのデータ画像を読み出していれば終了し、そうでなければステップ５に戻って検索を続ける。
【００４９】
以上のように、本実施例によれば、クエリー画像に近似するデータ画像を高速で抽出することができる。なお、本発明に係る画像検索方法・装置は、独立した画像検索方法・装置として使用することもできるし、粗検索‐詳細検索の段階を踏む多段階画像検索方法・装置における粗検索ツールとして使用することもできる。
【図面の簡単な説明】
【００５０】
【図１】本発明の実施例に係る実施例に係る画像検索装置の概念的な構成図である。
【図２】本発明の実施例に係る実施例に係る画像検索方法を示すフローチャートである。
【図３】ＲＧＢ空間に写像したクエリー画像に属する画素の集合を示す図である。
【図４】前記画素の集合の重心を説明する図である。
【図５】新たな色空間とクエリー円錐を説明する図である。
【符号の説明】
【００５１】
１  画像検索装置  
２  画像入力手段  
３  重心算出手段
４  色空間設定手段
５  クエリー円錐算出手段
６  画像データベース
７  写像手段
８  計数手段
９  閾値判定手段
１０  画素
１１  直線
１２  クエリー円錐
【図１】
2006268799.tif 000006
【図２】
2006268799.tif 000007
【図３】
2006268799.tif 000008
【図４】
2006268799.tif 000009
【図５】
2006268799.tif 000010