画像検索方法及び装置
【課題】 本発明の目的は、ロバストかつ高速(モデル数に対し対数オーダーの計算量)な画像検索方法を提供すること。
【解決手段】 本発明の画像検索方法は、一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化工程と、正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をいくつかの部分集合に分類する分類工程と、各部分集合ごとに分類された各定型領域内の特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類工程と、各分類時の定型領域内における特定領域の位置、及び、分類に際しての特定領域の特徴を出力する出力工程とを備えたことを特徴としている。
【解決手段】 本発明の画像検索方法は、一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化工程と、正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をいくつかの部分集合に分類する分類工程と、各部分集合ごとに分類された各定型領域内の特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類工程と、各分類時の定型領域内における特定領域の位置、及び、分類に際しての特定領域の特徴を出力する出力工程とを備えたことを特徴としている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速な画像検索を行うことが可能なデータベースの作成や高速な検索自体に関する画像検索方法及び装置に関する。
【背景技術】
【０００２】
複数の画像間で対応関係にある小領域を算出することは、対象認識、三次元情報復元、画像検索など様々な画像処理アプリケーションによって重要な問題である。画像内の局所的な領域をアフィン変換や回転変換に対して正規化した状態で抽出し（以降、アフィン不変領域と呼ぶこととする）、それらのアフィン不変領域間の対応関係を利用する画像認識手段は、認識対象に対する視点変化を幾何学的にモデリングできるという利点がある。また、局所的なアフィン不変領域を利用するため、認識対象の部分隠れに対する対応能力が高いという利点もある。
【非特許文献１】Ｄ．Ｇ．Ｌｏｗｅ ”Ｄｉｓｔｉｎｃｔｉｖｅ ｉｍａｇｅ ｆｅａｔｕｒｅｓ ｆｒｏｍ ｓｃａｌｅ−ｉｎｖａｒｉａｎｔ ｋｅｙｐｏｉｎｔｓ” Ｉｎｔ． Ｊ． Ｃｏｍｐｔ． Ｖｉｓｉｏｎ， ６０（２）：９１−１１０，２００４
【非特許文献２】Ｊ．Ｍａｔｅｓ， Ｏ．Ｃｈｕｍ， Ｍ．Ｕｒｂａｎ， ａｎｄ Ｔ．Ｐａｊｄｌａ ”Ｒｏｂｕｓｔ Ｗｉｄｅ Ｂａｓｅｌｉｎｅ Ｓｔｅｒｅｏ ｆｒｏｍ Ｅｘｔｒｅｍａｌ Ｒｅｇｉｏｎｓ” ＢＭＶＣ０２，２００２
【０００３】
これらの手法は、一般に下記の三段階の処理によって実現される（図８参照）。（１）一枚又は複数枚のモデル画像及び検索対象画像（供試画像）からアフィン不変領域を抽出する。（２）抽出したアフィン不変領域の対応関係を局所的な情報に基づいて算出する。（３）大局的な情報を利用して上記（２）で算出した対応関係を検証する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ここで、上記（２）のアフィン不変領域間の対応関係を算出する際に、ロバスト性とともに実行速度も重要な問題となる。例えば、複数の対象を認識する際場合、図９に示すように、複数のモデル画像から抽出したアフィン不変領域と検索対象画像から抽出したアフィン不変領域との一致を逐次比較するような方法では、モデル画像数（即ち、それらから抽出されるアフィン不変領域数）が増加した場合、計算負荷も線形的に増大し，実時間アプリケーションにとって致命的である。従って、本発明の目的は，ロバストかつ高速(モデル数に対し対数オーダーの計算量)な画像検索方法及び装置を提供することにある。
【０００５】
また、上述した［非特許文献１］では、画像ヒストグラムを指標として、アフィン不変領域間の対応付けを行うことで二つの画像の比較を行う。ただし、検索対象としたい部分以外の背景部分も含めて比較を行っているため、背景部分の比率が大きい場合アフィン不変領域間の対応を正確にとることができない。
【課題を解決するための手段】
【０００６】
請求項１に記載の画像検索方法は、一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化工程と、正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をいくつかの部分集合に分類する分類工程と、各部分集合ごとに分類された各定型領域内の特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類工程と、各分類時の定型領域内における特定領域の位置、及び、分類に際しての特定領域の特徴を出力する出力工程とを備えたことを特徴としている。
【０００７】
請求項２に記載の発明は、請求項１に記載の画像検索方法において、分類に際して利用される特定領域の特徴が、該特定領域に関する輝度情報であることを特徴としている。
【０００８】
請求項３に記載の発明は、請求項１又は２に記載の画像検索方法において、正規化工程において定型領域を背景部と検索部とに分割し、分類工程又は再帰分類工程における特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴としている。
【０００９】
請求項４に記載の発明は、請求項１〜３の何れか一項に記載の画像検索方法において、正規化工程において、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１０】
請求項５に記載の発明は、請求項１〜３の何れか一項に記載の画像検索方法において、正規化工程において、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１１】
請求項６に記載の発明は、請求項１〜５の何れか一項に記載の画像検索方法において、検索対象から抽出した領域を正規化した所定領域を検出対象として入力する入力工程と、出力工程における出力結果に基づいて、所定領域が末端のどの部分集合に属するかを検索することで、所定領域と定型領域の部分集合とを対応づける検索工程とをさらに備えることを特徴としている。
【００１２】
請求項７に記載の発明は、請求項６に記載の画像検索方法において、検索工程において、入力行程で所定領域を正規化する際の定型領域との位置ズレを考慮して、所定領域と定型領域の部分集合との対応付けを行うことを特徴としている。
【００１３】
請求項８に記載の画像検索装置は、一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化手段と、正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をいくつかの部分集合に分類する分類手段と、各部分集合ごとに分類された各定型領域内の特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類手段と、各分類時の定型領域内における特定領域の位置、及び、分類に際しての特定領域の特徴を出力する出力手段とを備えたことを特徴としている。
【００１４】
請求項９に記載の発明は、請求項８に記載の画像検索装置において、分類に際して利用される特定領域の特徴が、該特定領域に関する輝度情報であることを特徴としている。
【００１５】
請求項１０に記載の発明は、請求項８又は９に記載の画像検索装置において、正規化手段によって定型領域を背景部と検索部とに分割し、分類手段による分類時又は再帰分類手段による再帰分類時における特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴としている。
【００１６】
請求項１１に記載の発明は、請求項８〜１０の何れか一項に記載の画像検索装置において、正規化手段による正規化の際に、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１７】
請求項１２に記載の発明は、請求項８〜１０の何れか一項に記載の画像検索装置において、正規化手段による正規化の際に、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１８】
請求項１３に記載の発明は、請求項８〜１２の何れか一項に記載の画像検索装置において、対象画像から抽出した領域を正規化した所定領域を検出対象として入力する入力手段と、出力手段における出力結果に基づいて、所定領域が末端のどの部分集合に属するかを検索することで、所定領域と定型領域の部分集合とを対応づける検索手段とをさらに備えることを特徴としている。
【００１９】
請求項１４に記載の発明は、請求項１３に記載の画像検索装置において、検索手段による検索時の際に、入力工程により所定領域を正規化する際の定型領域との位置ズレを考慮して、所定領域と定型領域の部分集合との対応付けを行うことを特徴としている。
【発明の効果】
【００２０】
本発明の画像検索方法又は画像検索装置によれば、定型領域内の特定領域に基づいてモデル画像を部分集合の繰り返しとして分類することで、ロバストかつ高速な検索が可能な画像データベースを構築することができる。そして、検索対象となる対象画像が与えられたときには、上述したデータベースを利用して、対象画像における定型領域内の特定領域を利用して、ロバストかつ高速な検索を行うことができる。
【発明を実施するための最良の形態】
【００２１】
本発明の画像検索装置は、検索対象となる対象画像とこの対象画像と比較するためのデータベースとなるモデル画像とを入力する入力部、入力された画像に対してアフィン不変領域などを求める演算や検索のための比較対象を行うを行う演算部、構築したデータベースや検索結果を出力する出力部、演算に必要なプログラムや途中の演算内容・構築したデータベースなどを記憶しておく記憶部などを備えている。
【００２２】
入力部は、カメラであったり、スキャナであったり、データとして画像を入力する入出力ドライブであったりする。演算部は、ＣＰＵやＧＰＵ・ＲＯＭ・ＲＡＭなどであったりする。出力部は、モニタディスプレイであったりプリンタであったり入出力ドライブであったりする。記憶部は、ハードディスクやＲＡＭその他のストレージデバイスであったりする。
【００２３】
本実施形態における画像検索方法（データベース構築方法）についての概要を説明する。以下の説明では、画像として道路標識を扱う場合を例にして説明する。また、以下では、本発明をアフィン不変領域の対応算出手法として説明するが、適応の範囲はアフィン不変領域に限らない。ラスタスキャン等の他手法であっても、一定サイズに正規化された画像であれば、その対応関係算出に広く応用できるものである
【００２４】
まず、背景部分の影響を排除できる、アフィン不変領域の比較手法を考える。ここで、供試画像（検索対象画像）から抽出したアフィン不変領域(以降，供試アフィン不変領域)の背景部分は未知、検索データベースの元となるモデル画像から抽出した複数のアフィン不変領域(以降，モデルアフィン不変領域)の背景部分は既知である。
【００２５】
背景部分は各モデルアフィン不変領域に対して異なるため、全てのモデルアフィン不変領域に対して供試アフィン不変領域との類似度評価を統一的に扱うことができない。このため、供試アフィン不変領域と全てのモデルアフィン不変領域との類似度を一対一で評価する必要がある。これでは、計算量がモデル数に対し線形増加してしまうため、上述したように、多数のモデルを扱う実時間アプリケーションにとって致命的である。
【００２６】
そこで、本実施形態では、アフィン不変領域の各画素値を比較の指標として、供試アフィン不変領域に対応するモデルアフィン不変領域の絞込みのために最適な着目画素の選択と実際の絞込みとを交互に行い、その際に選択画素が背景部分であるモデルは絞込みの対象としないことでモデル数が多い場合も高速かつ背景の影響を排除したロバストな対応算出を実現する。図１及び図２に本発明の概念図を示す。
【００２７】
図１は、対象画像が与えられたときの比較の元となるデータベースの構築について示されている。ここでは、データベースの元となるモデルアフィン不変領域（モデル画像中から正規化されて抽出されたアフィン不変領域）は図中左上に示された三つである。実際のアフィン不変領域は必ずしも標識全体とはならないが、説明の便宜上、図中では段差を示す交通標識と信号を示す交通標識とＸ印の交通標識の全体をモデルアフィン不変領域としている。ここでは、予め標識以外の背景部分は背景として設定されている。まず、この各モデル画像（定型領域）に対して特定領域（表中の□で示された領域）を設定し、特定領域の輝度情報に基づいて、三つのモデル画像（定型領域）をいくつかの部分集合に分類する。
【００２８】
ただし、特定領域が背景であるモデル画像（定型領域）の場合は、分類された部分集合の全てに含ませることにする。この分類工程によって図中真ん中の列のように、二つの部分集合が構築される。そして、各部分集合内で、先ほどとは異なる位置に別の特定領域を設定し、特定領域の輝度情報に基づいて、各モデル画像（定型領域）を再帰的にさらにいくつかの部分集合に分類する。最終的に、この再帰分類工程によって図中右側の列のように、要素が一つの計四つの部分集合が構築される。
【００２９】
このように、ツリー状のデータベースが構築され、これに基づいて検索対象画像が入力された場合、その検索対象画像がモデル画像のいずれと一致するかが判定される。この様子を示した図が図２である。図２の最も左方の二つが、検索対象画像から抽出された供試アフィン不変領域（対象画像中から正規化されて抽出されたアフィン不変領域）の例示（二種類）である。検索対象画像には、交通標識の他に背景も含まれている。この各対象画像（定型領域）に対して、データベースに従って特定領域（表中の□で示された領域）を設定し、特定領域の輝度情報に基づいて、いずれの部分集合に属するかを順次判定（分岐判断）していく。
【００３０】
ただし、対象画像は上述したように背景を有しているため、特定領域が背景であるような場合は、その背景の輝度情報によっていずれの部分集合に属するかの判断（分岐判断）が決定されてしまう。しかし、データベースの構築時に、モデル画像中の特定領域が背景である場合は、下位の全ての部分集合にその定型領域を含ませることとしてるため、問題はない。
【００３１】
以下、フローチャートに基づいて説明する。図３は、全体の流れを示すフローチャートである。まず、ステップ３００であるが、背景が占める領域が既知である複数のモデル画像から，アフィン変換(または回転変換)に関わらず形状を正規化できる性質を持つ領域を抽出し、一定サイズの矩形(または円形等)に正規化する（定型領域とする）。この処理は複数の公知手法で行うことができる。ここで抽出された正規化領域数をＮ、その集合をＳ＝｛ｓ１，ｓ２，…，ｓＮ｝とする。特徴領域抽出と正規化を、複数の手法やパラメータを併用して行う場合は，ステップ３０５以降の処理はそれぞれの手法やパラメータで独立に行う。
【００３２】
次に、ステップ３０５では、∀Ａ∈Ｓに対して画素位置ｘでの画素値νを考察する。Ａに対応する供試アフィン不変領域は、何らかのノイズを含んでおりＡと完全には一致しない。ロバストな対応探索のためには、ノイズの影響を考慮して画素位置ｘの画素値νを確率関数ｐｘ，Ａ（ν）としてモデル化する必要がある。ここでは、アフィン不変領域抽出の際の幾何的なずれと、光学的なずれの影響を考慮する。
【００３３】
アフィン不変領域抽出の際、画像量子化損失やその他の要因で正規化のためのアフィン変換行列に誤差が生じることが幾何的なずれの原因である。各画素に対する幾何的なずれ量は、二次元ガウシアン分布に従うと仮定すれば、その確率分布は共分散行列として表現することが可能であり、Ｈ行列が既知である複数枚の画像対を利用して実験的に算出することができる。上述した［非特許文献２］の各手法でアフィン不変領域を抽出した際の幾何的ずれの確率分布を、図４に模式的に示す。（ａ）は領域共分散行列による手法の場合、（ｂ）はｂｉ−ｔａｎｇｅｎｔによる手法の場合、（ｃ）はｃｏｎｃａｖｉｔｙによる手法の場合である。楕円の向きと大きさが、ずれの向きと大きさを示している。
【００３４】
Ａの画素位置ｘで画素値νが観測される確率ｐｘ，Ａ（ν）は、画素位置ｘでの幾何的なずれの確率分布をｌｘ、画素値がνであるＡ中の領域Ων，Ａを用いて以下の式で表される。
【数１】
【００３５】
図５（ａ），（ｂ）に幾何学的なずれのモデリングを模式的に示す。図５（ａ），（ｂ）は、確率ｐｘ，Ａ（ν）の分布を示しており、（ａ）は画素位置ｘに対して推定された幾何的なずれｌｘを示しており、（ｂ）は画素値νに対する確率ｐｘ，Ａ（ν）の範囲を示している。また、図５（ｃ）は、（ｂ）に対してさらに光学的なずれを考慮した場合を示している。
【００３６】
また、光学的なずれに関しては、撮影条件の相違からモデルアフィン不変領域と供試アフィン不変領域との間で光学的な特性が一致しないことが要因である。観測された画素値νに対し、実験の画素値は［ν−ε，ν＋ε］に一様分布すると仮定すると、画素位置ｘで画素値νを観測する確率は図５（ｃ）に示すように、ｐｘ，Ａ（ν）／２εとなる。
【００３７】
次に、ステップ３１０では、∀Ａ∈Ｓに対し，木構造（部分集合化の繰り返し構造）の分岐中にＡが存在する確率ｐＡを１に初期化する。次いで、ステップ３１５では、ＳとｐＡとを入力として、図６のサブルーチンを呼び出す。ステップ３１５の後、ステップ３２０では、選択着目画素の位置と分岐判断のための画素値の閾値を対応候補絞込戦略として出力する。
【００３８】
図６のサブルーチンのフローチャートについて説明する。学習対象のアフィン不変領域の集合ＳとＡ∈Ｓに対する存在確率ｐＡとを入力として学習を開始する。まず、ステップ６００において、Ｓの要素数が閾値以下の場合は、これ以上分割する必要がないと判断してステップ６０５に進む。ステップ６０５では、これ以上部分集合に分割することが不可能であるため、入力されたアフィン不変領域の集合Ｓをそのまま木構造の末節とする。
【００３９】
一方、ステップ６００が否定され、Ｓの要素数が閾値を超えている場合は、ステップ６１０において、Ｓを画素位置ｘに着目し，画素値の閾値θｘにより、二つの部分集合ＳＬ，ＳＲに分割することを考える。θｘを画素位置ｘの画素値分布のメディアンとすれば、ＳＬとＳＲとの要素数が等しくなり、木構造の深さが最小になる。この戦略では、θｘは以下の式で与えられる（なお、ここでは、画素値は０〜２５５の２５６段階とされている）。
【数２】
【００４０】
さらに画素位置ｘでサブグループ分割した場合の分割の良悪を分割度ｄｘを指標として表す。分割度ｄｘは下記式によって算出される。ここで、分割が完璧であった場合の分割度ｄｘは０，最悪の場合で０．５である。
【数３】
よって、最良の分割を与える画素位置ｘｂａｒは以下の式で与えられる。
【数４】
【００４１】
ステップ６１５では、ｄｘｂａｒが閾値以上であれば、部分集合ＳＬ，ＳＲに分割が不可能であるとしてステップ６０５へ、そうでなければステップ６２０に進む。ステップ６０５では、これ以上部分集合ＳＬ，ＳＲに分割することが不可能であるため、入力されたアフィン不変領域の集合Ｓをそのまま木構造の末節とする。ステップ６２０では、全てのＡ∈Ｓに対して、以下のステップ６２５〜６４５を繰り返す。
【００４２】
ステップ６２５では、Ａが各々の部分集合ＳＬ，ＳＲに分割される確率ｐＬ，ｐＲを下記式より求める。ここで，明らかにｐＡ＝ｐＬ＋ｐＲである．
【数５】
【００４３】
ステップ６３０では、ｐＬが所定の閾値以上であるかどうかを判定し、閾値以上であれば、ステップ６３５によってＡは部分集合ＳＬに登録される（Ａと対応するサブグループ存在確率ｐＬを部分集合ＳＬに追加する）。ステップ６３０が否定される場合（又はステップ６３５の後）、ステップ６４０では、ｐＲが所定の閾値以上であるかどうかを判定し、閾値以上であれば、ステップ６４５によってＡは部分集合ＳＲに登録される（Ａと対応するサブグループ存在確率ｐＲを部分集合ＳＲに追加する）。ステップ６２０によって、全てのＡ∈Ｓについて部分集合ＳＬ，ＳＲへの分割が行われる。
【００４４】
その後、ステップ６４０が否定される場合（又はステップ６４５の後）、ステップ６５０では部分集合ＳＬの要素数が０以外かどうかを判定する。部分集合ＳＬの要素数が０以外である場合は、ステップ６５５にて、部分集合ＳＬと確率ｐＬとを入力として再帰的に学習サブルーチンを呼び出す（下位の分岐を行う）。ステップ６５０が否定される場合（又はステップ６５５の後）、ステップ６６０では部分集合ＳＲの要素数が０以外かどうかを判定する。部分集合ＳＲの要素数が０以外である場合は、ステップ６６５にて、部分集合ＳＲと確率ｐＲとを入力として再帰的に学習サブルーチンを呼び出す（下位の分岐を行う）。
【００４５】
次に、ステップ７０５において、実際に対応候補の絞り込み（検索対象画像と学習されて構築されたデータベースとの照合）を行う流れを、図７のフローチャートに基づいて説明する。ステップ７００において、供試画像から複数のアフィン不変領域（定型領域）を抽出する。これには、学習時の図３のフローチャートにおけるステップ３００と同等の手法で実現できる。次に、検索対象画像から抽出した各アフィン不変領域（定型領域）に対して学習した絞込戦略（データベース）を利用して対応候補を算出する。実際には、絞込戦略に従って着目画素の選択（特定領域の選択）、及び、画素値と閾値との比較を利用した分岐選択を木構造の末端まで繰り返す。これにより、モデル画像の定型領域と検索対象画像の定型領域とのマッチングが行われる。
【図面の簡単な説明】
【００４６】
【図１】本発明の画像検索方法及び装置における学習の概要を示す説明図である。
【図２】本発明の画像検索方法及び装置における検索の概要を示す説明図である。
【図３】本発明の画像検索方法及び装置における全体の流れを示すフローチャートである。
【図４】アフィン不変領域を抽出した際の幾何的ずれを模式的に示した説明図である。
【図５】アフィン不変領域を抽出した際の幾何学的なずれのモデリングを模式的に示した説明図である。
【図６】本発明の画像検索方法及び装置における学習サブルーチンを示すフローチャートである。
【図７】本発明の画像検索方法及び装置における検索を示すフローチャートである。
【図８】画像内の局所的な領域をアフィン変換や回転変換に対して不変な状態で抽出する状態を示す説明図である。
【図９】抽出した局所画像同士のマッチングを示す説明図である。
【技術分野】
【０００１】
本発明は、高速な画像検索を行うことが可能なデータベースの作成や高速な検索自体に関する画像検索方法及び装置に関する。
【背景技術】
【０００２】
複数の画像間で対応関係にある小領域を算出することは、対象認識、三次元情報復元、画像検索など様々な画像処理アプリケーションによって重要な問題である。画像内の局所的な領域をアフィン変換や回転変換に対して正規化した状態で抽出し（以降、アフィン不変領域と呼ぶこととする）、それらのアフィン不変領域間の対応関係を利用する画像認識手段は、認識対象に対する視点変化を幾何学的にモデリングできるという利点がある。また、局所的なアフィン不変領域を利用するため、認識対象の部分隠れに対する対応能力が高いという利点もある。
【非特許文献１】Ｄ．Ｇ．Ｌｏｗｅ ”Ｄｉｓｔｉｎｃｔｉｖｅ ｉｍａｇｅ ｆｅａｔｕｒｅｓ ｆｒｏｍ ｓｃａｌｅ−ｉｎｖａｒｉａｎｔ ｋｅｙｐｏｉｎｔｓ” Ｉｎｔ． Ｊ． Ｃｏｍｐｔ． Ｖｉｓｉｏｎ， ６０（２）：９１−１１０，２００４
【非特許文献２】Ｊ．Ｍａｔｅｓ， Ｏ．Ｃｈｕｍ， Ｍ．Ｕｒｂａｎ， ａｎｄ Ｔ．Ｐａｊｄｌａ ”Ｒｏｂｕｓｔ Ｗｉｄｅ Ｂａｓｅｌｉｎｅ Ｓｔｅｒｅｏ ｆｒｏｍ Ｅｘｔｒｅｍａｌ Ｒｅｇｉｏｎｓ” ＢＭＶＣ０２，２００２
【０００３】
これらの手法は、一般に下記の三段階の処理によって実現される（図８参照）。（１）一枚又は複数枚のモデル画像及び検索対象画像（供試画像）からアフィン不変領域を抽出する。（２）抽出したアフィン不変領域の対応関係を局所的な情報に基づいて算出する。（３）大局的な情報を利用して上記（２）で算出した対応関係を検証する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ここで、上記（２）のアフィン不変領域間の対応関係を算出する際に、ロバスト性とともに実行速度も重要な問題となる。例えば、複数の対象を認識する際場合、図９に示すように、複数のモデル画像から抽出したアフィン不変領域と検索対象画像から抽出したアフィン不変領域との一致を逐次比較するような方法では、モデル画像数（即ち、それらから抽出されるアフィン不変領域数）が増加した場合、計算負荷も線形的に増大し，実時間アプリケーションにとって致命的である。従って、本発明の目的は，ロバストかつ高速(モデル数に対し対数オーダーの計算量)な画像検索方法及び装置を提供することにある。
【０００５】
また、上述した［非特許文献１］では、画像ヒストグラムを指標として、アフィン不変領域間の対応付けを行うことで二つの画像の比較を行う。ただし、検索対象としたい部分以外の背景部分も含めて比較を行っているため、背景部分の比率が大きい場合アフィン不変領域間の対応を正確にとることができない。
【課題を解決するための手段】
【０００６】
請求項１に記載の画像検索方法は、一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化工程と、正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をいくつかの部分集合に分類する分類工程と、各部分集合ごとに分類された各定型領域内の特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類工程と、各分類時の定型領域内における特定領域の位置、及び、分類に際しての特定領域の特徴を出力する出力工程とを備えたことを特徴としている。
【０００７】
請求項２に記載の発明は、請求項１に記載の画像検索方法において、分類に際して利用される特定領域の特徴が、該特定領域に関する輝度情報であることを特徴としている。
【０００８】
請求項３に記載の発明は、請求項１又は２に記載の画像検索方法において、正規化工程において定型領域を背景部と検索部とに分割し、分類工程又は再帰分類工程における特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴としている。
【０００９】
請求項４に記載の発明は、請求項１〜３の何れか一項に記載の画像検索方法において、正規化工程において、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１０】
請求項５に記載の発明は、請求項１〜３の何れか一項に記載の画像検索方法において、正規化工程において、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１１】
請求項６に記載の発明は、請求項１〜５の何れか一項に記載の画像検索方法において、検索対象から抽出した領域を正規化した所定領域を検出対象として入力する入力工程と、出力工程における出力結果に基づいて、所定領域が末端のどの部分集合に属するかを検索することで、所定領域と定型領域の部分集合とを対応づける検索工程とをさらに備えることを特徴としている。
【００１２】
請求項７に記載の発明は、請求項６に記載の画像検索方法において、検索工程において、入力行程で所定領域を正規化する際の定型領域との位置ズレを考慮して、所定領域と定型領域の部分集合との対応付けを行うことを特徴としている。
【００１３】
請求項８に記載の画像検索装置は、一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化手段と、正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をいくつかの部分集合に分類する分類手段と、各部分集合ごとに分類された各定型領域内の特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類手段と、各分類時の定型領域内における特定領域の位置、及び、分類に際しての特定領域の特徴を出力する出力手段とを備えたことを特徴としている。
【００１４】
請求項９に記載の発明は、請求項８に記載の画像検索装置において、分類に際して利用される特定領域の特徴が、該特定領域に関する輝度情報であることを特徴としている。
【００１５】
請求項１０に記載の発明は、請求項８又は９に記載の画像検索装置において、正規化手段によって定型領域を背景部と検索部とに分割し、分類手段による分類時又は再帰分類手段による再帰分類時における特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴としている。
【００１６】
請求項１１に記載の発明は、請求項８〜１０の何れか一項に記載の画像検索装置において、正規化手段による正規化の際に、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１７】
請求項１２に記載の発明は、請求項８〜１０の何れか一項に記載の画像検索装置において、正規化手段による正規化の際に、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴としている。
【００１８】
請求項１３に記載の発明は、請求項８〜１２の何れか一項に記載の画像検索装置において、対象画像から抽出した領域を正規化した所定領域を検出対象として入力する入力手段と、出力手段における出力結果に基づいて、所定領域が末端のどの部分集合に属するかを検索することで、所定領域と定型領域の部分集合とを対応づける検索手段とをさらに備えることを特徴としている。
【００１９】
請求項１４に記載の発明は、請求項１３に記載の画像検索装置において、検索手段による検索時の際に、入力工程により所定領域を正規化する際の定型領域との位置ズレを考慮して、所定領域と定型領域の部分集合との対応付けを行うことを特徴としている。
【発明の効果】
【００２０】
本発明の画像検索方法又は画像検索装置によれば、定型領域内の特定領域に基づいてモデル画像を部分集合の繰り返しとして分類することで、ロバストかつ高速な検索が可能な画像データベースを構築することができる。そして、検索対象となる対象画像が与えられたときには、上述したデータベースを利用して、対象画像における定型領域内の特定領域を利用して、ロバストかつ高速な検索を行うことができる。
【発明を実施するための最良の形態】
【００２１】
本発明の画像検索装置は、検索対象となる対象画像とこの対象画像と比較するためのデータベースとなるモデル画像とを入力する入力部、入力された画像に対してアフィン不変領域などを求める演算や検索のための比較対象を行うを行う演算部、構築したデータベースや検索結果を出力する出力部、演算に必要なプログラムや途中の演算内容・構築したデータベースなどを記憶しておく記憶部などを備えている。
【００２２】
入力部は、カメラであったり、スキャナであったり、データとして画像を入力する入出力ドライブであったりする。演算部は、ＣＰＵやＧＰＵ・ＲＯＭ・ＲＡＭなどであったりする。出力部は、モニタディスプレイであったりプリンタであったり入出力ドライブであったりする。記憶部は、ハードディスクやＲＡＭその他のストレージデバイスであったりする。
【００２３】
本実施形態における画像検索方法（データベース構築方法）についての概要を説明する。以下の説明では、画像として道路標識を扱う場合を例にして説明する。また、以下では、本発明をアフィン不変領域の対応算出手法として説明するが、適応の範囲はアフィン不変領域に限らない。ラスタスキャン等の他手法であっても、一定サイズに正規化された画像であれば、その対応関係算出に広く応用できるものである
【００２４】
まず、背景部分の影響を排除できる、アフィン不変領域の比較手法を考える。ここで、供試画像（検索対象画像）から抽出したアフィン不変領域(以降，供試アフィン不変領域)の背景部分は未知、検索データベースの元となるモデル画像から抽出した複数のアフィン不変領域(以降，モデルアフィン不変領域)の背景部分は既知である。
【００２５】
背景部分は各モデルアフィン不変領域に対して異なるため、全てのモデルアフィン不変領域に対して供試アフィン不変領域との類似度評価を統一的に扱うことができない。このため、供試アフィン不変領域と全てのモデルアフィン不変領域との類似度を一対一で評価する必要がある。これでは、計算量がモデル数に対し線形増加してしまうため、上述したように、多数のモデルを扱う実時間アプリケーションにとって致命的である。
【００２６】
そこで、本実施形態では、アフィン不変領域の各画素値を比較の指標として、供試アフィン不変領域に対応するモデルアフィン不変領域の絞込みのために最適な着目画素の選択と実際の絞込みとを交互に行い、その際に選択画素が背景部分であるモデルは絞込みの対象としないことでモデル数が多い場合も高速かつ背景の影響を排除したロバストな対応算出を実現する。図１及び図２に本発明の概念図を示す。
【００２７】
図１は、対象画像が与えられたときの比較の元となるデータベースの構築について示されている。ここでは、データベースの元となるモデルアフィン不変領域（モデル画像中から正規化されて抽出されたアフィン不変領域）は図中左上に示された三つである。実際のアフィン不変領域は必ずしも標識全体とはならないが、説明の便宜上、図中では段差を示す交通標識と信号を示す交通標識とＸ印の交通標識の全体をモデルアフィン不変領域としている。ここでは、予め標識以外の背景部分は背景として設定されている。まず、この各モデル画像（定型領域）に対して特定領域（表中の□で示された領域）を設定し、特定領域の輝度情報に基づいて、三つのモデル画像（定型領域）をいくつかの部分集合に分類する。
【００２８】
ただし、特定領域が背景であるモデル画像（定型領域）の場合は、分類された部分集合の全てに含ませることにする。この分類工程によって図中真ん中の列のように、二つの部分集合が構築される。そして、各部分集合内で、先ほどとは異なる位置に別の特定領域を設定し、特定領域の輝度情報に基づいて、各モデル画像（定型領域）を再帰的にさらにいくつかの部分集合に分類する。最終的に、この再帰分類工程によって図中右側の列のように、要素が一つの計四つの部分集合が構築される。
【００２９】
このように、ツリー状のデータベースが構築され、これに基づいて検索対象画像が入力された場合、その検索対象画像がモデル画像のいずれと一致するかが判定される。この様子を示した図が図２である。図２の最も左方の二つが、検索対象画像から抽出された供試アフィン不変領域（対象画像中から正規化されて抽出されたアフィン不変領域）の例示（二種類）である。検索対象画像には、交通標識の他に背景も含まれている。この各対象画像（定型領域）に対して、データベースに従って特定領域（表中の□で示された領域）を設定し、特定領域の輝度情報に基づいて、いずれの部分集合に属するかを順次判定（分岐判断）していく。
【００３０】
ただし、対象画像は上述したように背景を有しているため、特定領域が背景であるような場合は、その背景の輝度情報によっていずれの部分集合に属するかの判断（分岐判断）が決定されてしまう。しかし、データベースの構築時に、モデル画像中の特定領域が背景である場合は、下位の全ての部分集合にその定型領域を含ませることとしてるため、問題はない。
【００３１】
以下、フローチャートに基づいて説明する。図３は、全体の流れを示すフローチャートである。まず、ステップ３００であるが、背景が占める領域が既知である複数のモデル画像から，アフィン変換(または回転変換)に関わらず形状を正規化できる性質を持つ領域を抽出し、一定サイズの矩形(または円形等)に正規化する（定型領域とする）。この処理は複数の公知手法で行うことができる。ここで抽出された正規化領域数をＮ、その集合をＳ＝｛ｓ１，ｓ２，…，ｓＮ｝とする。特徴領域抽出と正規化を、複数の手法やパラメータを併用して行う場合は，ステップ３０５以降の処理はそれぞれの手法やパラメータで独立に行う。
【００３２】
次に、ステップ３０５では、∀Ａ∈Ｓに対して画素位置ｘでの画素値νを考察する。Ａに対応する供試アフィン不変領域は、何らかのノイズを含んでおりＡと完全には一致しない。ロバストな対応探索のためには、ノイズの影響を考慮して画素位置ｘの画素値νを確率関数ｐｘ，Ａ（ν）としてモデル化する必要がある。ここでは、アフィン不変領域抽出の際の幾何的なずれと、光学的なずれの影響を考慮する。
【００３３】
アフィン不変領域抽出の際、画像量子化損失やその他の要因で正規化のためのアフィン変換行列に誤差が生じることが幾何的なずれの原因である。各画素に対する幾何的なずれ量は、二次元ガウシアン分布に従うと仮定すれば、その確率分布は共分散行列として表現することが可能であり、Ｈ行列が既知である複数枚の画像対を利用して実験的に算出することができる。上述した［非特許文献２］の各手法でアフィン不変領域を抽出した際の幾何的ずれの確率分布を、図４に模式的に示す。（ａ）は領域共分散行列による手法の場合、（ｂ）はｂｉ−ｔａｎｇｅｎｔによる手法の場合、（ｃ）はｃｏｎｃａｖｉｔｙによる手法の場合である。楕円の向きと大きさが、ずれの向きと大きさを示している。
【００３４】
Ａの画素位置ｘで画素値νが観測される確率ｐｘ，Ａ（ν）は、画素位置ｘでの幾何的なずれの確率分布をｌｘ、画素値がνであるＡ中の領域Ων，Ａを用いて以下の式で表される。
【数１】
【００３５】
図５（ａ），（ｂ）に幾何学的なずれのモデリングを模式的に示す。図５（ａ），（ｂ）は、確率ｐｘ，Ａ（ν）の分布を示しており、（ａ）は画素位置ｘに対して推定された幾何的なずれｌｘを示しており、（ｂ）は画素値νに対する確率ｐｘ，Ａ（ν）の範囲を示している。また、図５（ｃ）は、（ｂ）に対してさらに光学的なずれを考慮した場合を示している。
【００３６】
また、光学的なずれに関しては、撮影条件の相違からモデルアフィン不変領域と供試アフィン不変領域との間で光学的な特性が一致しないことが要因である。観測された画素値νに対し、実験の画素値は［ν−ε，ν＋ε］に一様分布すると仮定すると、画素位置ｘで画素値νを観測する確率は図５（ｃ）に示すように、ｐｘ，Ａ（ν）／２εとなる。
【００３７】
次に、ステップ３１０では、∀Ａ∈Ｓに対し，木構造（部分集合化の繰り返し構造）の分岐中にＡが存在する確率ｐＡを１に初期化する。次いで、ステップ３１５では、ＳとｐＡとを入力として、図６のサブルーチンを呼び出す。ステップ３１５の後、ステップ３２０では、選択着目画素の位置と分岐判断のための画素値の閾値を対応候補絞込戦略として出力する。
【００３８】
図６のサブルーチンのフローチャートについて説明する。学習対象のアフィン不変領域の集合ＳとＡ∈Ｓに対する存在確率ｐＡとを入力として学習を開始する。まず、ステップ６００において、Ｓの要素数が閾値以下の場合は、これ以上分割する必要がないと判断してステップ６０５に進む。ステップ６０５では、これ以上部分集合に分割することが不可能であるため、入力されたアフィン不変領域の集合Ｓをそのまま木構造の末節とする。
【００３９】
一方、ステップ６００が否定され、Ｓの要素数が閾値を超えている場合は、ステップ６１０において、Ｓを画素位置ｘに着目し，画素値の閾値θｘにより、二つの部分集合ＳＬ，ＳＲに分割することを考える。θｘを画素位置ｘの画素値分布のメディアンとすれば、ＳＬとＳＲとの要素数が等しくなり、木構造の深さが最小になる。この戦略では、θｘは以下の式で与えられる（なお、ここでは、画素値は０〜２５５の２５６段階とされている）。
【数２】
【００４０】
さらに画素位置ｘでサブグループ分割した場合の分割の良悪を分割度ｄｘを指標として表す。分割度ｄｘは下記式によって算出される。ここで、分割が完璧であった場合の分割度ｄｘは０，最悪の場合で０．５である。
【数３】
よって、最良の分割を与える画素位置ｘｂａｒは以下の式で与えられる。
【数４】
【００４１】
ステップ６１５では、ｄｘｂａｒが閾値以上であれば、部分集合ＳＬ，ＳＲに分割が不可能であるとしてステップ６０５へ、そうでなければステップ６２０に進む。ステップ６０５では、これ以上部分集合ＳＬ，ＳＲに分割することが不可能であるため、入力されたアフィン不変領域の集合Ｓをそのまま木構造の末節とする。ステップ６２０では、全てのＡ∈Ｓに対して、以下のステップ６２５〜６４５を繰り返す。
【００４２】
ステップ６２５では、Ａが各々の部分集合ＳＬ，ＳＲに分割される確率ｐＬ，ｐＲを下記式より求める。ここで，明らかにｐＡ＝ｐＬ＋ｐＲである．
【数５】
【００４３】
ステップ６３０では、ｐＬが所定の閾値以上であるかどうかを判定し、閾値以上であれば、ステップ６３５によってＡは部分集合ＳＬに登録される（Ａと対応するサブグループ存在確率ｐＬを部分集合ＳＬに追加する）。ステップ６３０が否定される場合（又はステップ６３５の後）、ステップ６４０では、ｐＲが所定の閾値以上であるかどうかを判定し、閾値以上であれば、ステップ６４５によってＡは部分集合ＳＲに登録される（Ａと対応するサブグループ存在確率ｐＲを部分集合ＳＲに追加する）。ステップ６２０によって、全てのＡ∈Ｓについて部分集合ＳＬ，ＳＲへの分割が行われる。
【００４４】
その後、ステップ６４０が否定される場合（又はステップ６４５の後）、ステップ６５０では部分集合ＳＬの要素数が０以外かどうかを判定する。部分集合ＳＬの要素数が０以外である場合は、ステップ６５５にて、部分集合ＳＬと確率ｐＬとを入力として再帰的に学習サブルーチンを呼び出す（下位の分岐を行う）。ステップ６５０が否定される場合（又はステップ６５５の後）、ステップ６６０では部分集合ＳＲの要素数が０以外かどうかを判定する。部分集合ＳＲの要素数が０以外である場合は、ステップ６６５にて、部分集合ＳＲと確率ｐＲとを入力として再帰的に学習サブルーチンを呼び出す（下位の分岐を行う）。
【００４５】
次に、ステップ７０５において、実際に対応候補の絞り込み（検索対象画像と学習されて構築されたデータベースとの照合）を行う流れを、図７のフローチャートに基づいて説明する。ステップ７００において、供試画像から複数のアフィン不変領域（定型領域）を抽出する。これには、学習時の図３のフローチャートにおけるステップ３００と同等の手法で実現できる。次に、検索対象画像から抽出した各アフィン不変領域（定型領域）に対して学習した絞込戦略（データベース）を利用して対応候補を算出する。実際には、絞込戦略に従って着目画素の選択（特定領域の選択）、及び、画素値と閾値との比較を利用した分岐選択を木構造の末端まで繰り返す。これにより、モデル画像の定型領域と検索対象画像の定型領域とのマッチングが行われる。
【図面の簡単な説明】
【００４６】
【図１】本発明の画像検索方法及び装置における学習の概要を示す説明図である。
【図２】本発明の画像検索方法及び装置における検索の概要を示す説明図である。
【図３】本発明の画像検索方法及び装置における全体の流れを示すフローチャートである。
【図４】アフィン不変領域を抽出した際の幾何的ずれを模式的に示した説明図である。
【図５】アフィン不変領域を抽出した際の幾何学的なずれのモデリングを模式的に示した説明図である。
【図６】本発明の画像検索方法及び装置における学習サブルーチンを示すフローチャートである。
【図７】本発明の画像検索方法及び装置における検索を示すフローチャートである。
【図８】画像内の局所的な領域をアフィン変換や回転変換に対して不変な状態で抽出する状態を示す説明図である。
【図９】抽出した局所画像同士のマッチングを示す説明図である。
【特許請求の範囲】
【請求項１】
一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化工程と、
正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をいくつかの部分集合に分類する分類工程と、
各部分集合ごとに分類された各定型領域内の前記特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類工程と、
各分類時の前記定型領域内における前記特定領域の位置、及び、分類に際しての前記特定領域の特徴を出力する出力工程とを備えたことを特徴とする画像検索方法。
【請求項２】
分類に際して利用される前記特定領域の特徴が、該特定領域に関する輝度情報であることを特徴とする請求項１に記載の画像検索方法。
【請求項３】
前記正規化工程において定型領域を背景部と検索部とに分割し、前記分類工程又は前記再帰分類工程における前記特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴とする請求項１又は２に記載の画像検索方法。
【請求項４】
前記正規化工程において、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項１〜３の何れか一項に記載の画像検索方法。
【請求項５】
前記正規化工程において、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項１〜３の何れか一項に記載の画像検索方法。
【請求項６】
検索対象から抽出した領域を正規化した所定領域を検出対象として入力する入力工程と、
前記出力工程における出力結果に基づいて、前記所定領域が末端のどの部分集合に属するかを検索することで、前記所定領域と前記定型領域の部分集合とを対応づける検索工程とをさらに備えることを特徴とする請求項１〜５の何れか一項に記載の画像検索方法。
【請求項７】
前記検索工程において、前記入力行程で前記所定領域を正規化する際の前記定型領域との位置ズレを考慮して、前記所定領域と前記定型領域の部分集合との対応付けを行うことを特徴とする請求項６に記載の画像検索方法。
【請求項８】
一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化手段と、
正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をいくつかの部分集合に分類する分類手段と、
各部分集合ごとに分類された各定型領域内の前記特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類手段と、
各分類時の前記定型領域内における前記特定領域の位置、及び、分類に際しての前記特定領域の特徴を出力する出力手段とを備えたことを特徴とする画像検索装置。
【請求項９】
分類に際して利用される前記特定領域の特徴が、該特定領域に関する輝度情報であることを特徴とする請求項８に記載の画像検索装置。
【請求項１０】
前記正規化手段によって定型領域を背景部と検索部とに分割し、前記分類手段による分類時又は前記再帰分類手段による再帰分類時における前記特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴とする請求項８又は９に記載の画像検索装置。
【請求項１１】
前記正規化手段による正規化の際に、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項８〜１０の何れか一項に記載の画像検索装置。
【請求項１２】
前記正規化手段による正規化の際に、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項８〜１０の何れか一項に記載の画像検索装置。
【請求項１３】
対象画像から抽出した領域を正規化した所定領域を検出対象として入力する入力手段と、
前記出力手段における出力結果に基づいて、前記所定領域が末端のどの部分集合に属するかを検索することで、前記所定領域と前記定型領域の部分集合とを対応づける検索手段とをさらに備えることを特徴とする請求項８〜１２の何れか一項に記載の画像検索装置。
【請求項１４】
前記検索手段による検索時の際に、前記入力工程により前記所定領域を正規化する際の前記定型領域との位置ズレを考慮して、前記所定領域と前記定型領域の部分集合との対応付けを行うことを特徴とする請求項１３に記載の画像検索装置。
【請求項１】
一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化工程と、
正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をいくつかの部分集合に分類する分類工程と、
各部分集合ごとに分類された各定型領域内の前記特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類工程と、
各分類時の前記定型領域内における前記特定領域の位置、及び、分類に際しての前記特定領域の特徴を出力する出力工程とを備えたことを特徴とする画像検索方法。
【請求項２】
分類に際して利用される前記特定領域の特徴が、該特定領域に関する輝度情報であることを特徴とする請求項１に記載の画像検索方法。
【請求項３】
前記正規化工程において定型領域を背景部と検索部とに分割し、前記分類工程又は前記再帰分類工程における前記特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴とする請求項１又は２に記載の画像検索方法。
【請求項４】
前記正規化工程において、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項１〜３の何れか一項に記載の画像検索方法。
【請求項５】
前記正規化工程において、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項１〜３の何れか一項に記載の画像検索方法。
【請求項６】
検索対象から抽出した領域を正規化した所定領域を検出対象として入力する入力工程と、
前記出力工程における出力結果に基づいて、前記所定領域が末端のどの部分集合に属するかを検索することで、前記所定領域と前記定型領域の部分集合とを対応づける検索工程とをさらに備えることを特徴とする請求項１〜５の何れか一項に記載の画像検索方法。
【請求項７】
前記検索工程において、前記入力行程で前記所定領域を正規化する際の前記定型領域との位置ズレを考慮して、前記所定領域と前記定型領域の部分集合との対応付けを行うことを特徴とする請求項６に記載の画像検索方法。
【請求項８】
一枚又は複数枚のモデル画像から複数の領域を抽出して定型領域として正規化する正規化手段と、
正規化された各定型領域内に特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をいくつかの部分集合に分類する分類手段と、
各部分集合ごとに分類された各定型領域内の前記特定領域とは異なる位置に別の特定領域を設定し、該特定領域の特徴に基づいて複数の前記定型領域をさらにいくつかの部分集合に分類することを繰り返し行う再帰分類手段と、
各分類時の前記定型領域内における前記特定領域の位置、及び、分類に際しての前記特定領域の特徴を出力する出力手段とを備えたことを特徴とする画像検索装置。
【請求項９】
分類に際して利用される前記特定領域の特徴が、該特定領域に関する輝度情報であることを特徴とする請求項８に記載の画像検索装置。
【請求項１０】
前記正規化手段によって定型領域を背景部と検索部とに分割し、前記分類手段による分類時又は前記再帰分類手段による再帰分類時における前記特定領域の位置が背景部であるときには、分類時に全ての部分集合に該特定領域を含ませることを特徴とする請求項８又は９に記載の画像検索装置。
【請求項１１】
前記正規化手段による正規化の際に、そのアフィン変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項８〜１０の何れか一項に記載の画像検索装置。
【請求項１２】
前記正規化手段による正規化の際に、その回転変換に関わらず形状を正規化できる性質を持つ領域を定型領域として正規化することを特徴とする請求項８〜１０の何れか一項に記載の画像検索装置。
【請求項１３】
対象画像から抽出した領域を正規化した所定領域を検出対象として入力する入力手段と、
前記出力手段における出力結果に基づいて、前記所定領域が末端のどの部分集合に属するかを検索することで、前記所定領域と前記定型領域の部分集合とを対応づける検索手段とをさらに備えることを特徴とする請求項８〜１２の何れか一項に記載の画像検索装置。
【請求項１４】
前記検索手段による検索時の際に、前記入力工程により前記所定領域を正規化する際の前記定型領域との位置ズレを考慮して、前記所定領域と前記定型領域の部分集合との対応付けを行うことを特徴とする請求項１３に記載の画像検索装置。
【図３】
【図６】
【図７】
【図１】
【図２】
【図４】
【図５】
【図８】
【図９】
【図６】
【図７】
【図１】
【図２】
【図４】
【図５】
【図８】
【図９】
【公開番号】特開２００７−６６０１９（Ｐ２００７−６６０１９Ａ）
【公開日】平成１９年３月１５日（２００７．３．１５）
【国際特許分類】
【出願番号】特願２００５−２５１６６５（Ｐ２００５−２５１６６５）
【出願日】平成１７年８月３１日（２００５．８．３１）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【出願人】（５０５３２８４０９）チェスケ ヴィソケ ウチェニ テクニチュケ ヴ プラジェ (2)
【Ｆターム（参考）】
【公開日】平成１９年３月１５日（２００７．３．１５）
【国際特許分類】
【出願日】平成１７年８月３１日（２００５．８．３１）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【出願人】（５０５３２８４０９）チェスケ ヴィソケ ウチェニ テクニチュケ ヴ プラジェ (2)
【Ｆターム（参考）】
[ Back to top ]