(57)【要約】マハラノビス距離測定部（６０）を使用して、データベース（４０）内の複数の画像の中から問合せ画像（３０ｑ）を識別する。この測定部（６０）は、問合せ画像（３０ｑ）に対する１つ以上の画像の類似性を配列するために使用される。分散−共分散のマトリックスが、データベース（４０）内の全ての画像に対して計算される。この分散−共分散のマトリックスを使用して、問合せ画像（３０ｑ）とデータベース（４０）内の１つ以上の画像との間のマハラノビスの距離が計算される。マハラノビスの距離の測定を行うことに対して、有望な画像の候補を特定するために、範囲ツリーを使用することができる。
2004532458.tif 000002
【特許請求の範囲】
【請求項１】
複数の画像の１つ以上の特徴を定量化するステップと、
前記１つ以上の特徴を含む問合せ画像を受信するステップと、
前記問合せ画像と前記複数の画像の１つとの間のマハラノビスの距離を計算するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記問合せ画像と前記複数の画像の１つとの間のマハラノビスの距離を計算するステップが、
前記複数の画像の前記１つ以上の特徴を用いて、分散−共分散マトリックスを構築するステップと、
前記複数の画像から、前記１つ以上の特徴を備える第１の画像を選択するステップと、
前記第１の画像と前記問合せ画像との間のマハラノビスの距離を、前記分散−共分散マトリックスを用いて計算するステップと、
をさらに含むことを特徴とする方法。
【請求項３】
請求項２に記載の方法であって、前記複数の画像の前記１つ以上の特徴を用いて、分散−共分散マトリックスを構築するステップが、
前記複数の画像の特徴の平均を計算するステップと、
前記複数の画像の特徴の分散を計算するステップと、
前記複数の画像の一対の特徴間の共分散を計算するステップと、
をさらに含むことを特徴とする方法。
【請求項４】
請求項３に記載の方法が、
計算された分散及び共分散から前記分散−共分散マトリックスを構築するステップをさらに含むことを特徴とする方法。
【請求項５】
請求項２に記載の方法であって、前記第１の画像と前記問合せ画像との間のマハラノビスの距離を、前記分散−共分散マトリックスを用いて計算するステップが、
前記第１の画像の１つ以上の特徴を数値的に特徴付ける、前記第１の画像に対する第１のベクトルを識別するステップと、
前記問合せ画像の１つ以上の特徴を数値的に特徴付ける、前記問合せ画像に対する問合せベクトルを識別するステップと、
差ベクトルを作るために、前記第１のベクトルと前記問合せベクトルとの間の差を計算するステップと、
をさらに含むことを特徴とする方法。
【請求項６】
請求項５に記載の方法が、
中間結果を作るために、前記差ベクトルを分散−共分散マトリックスのインバースで乗算するステップと、
前記中間結果を前記差ベクトルのインバースで乗算するステップと、
をさらに含むことを特徴とする方法。
【請求項７】
請求項６に記載の方法が、
前記複数の画像の特徴を範囲ツリー内に記憶することを特徴とする方法。
【請求項８】
プロセッサと、
複数の画像を含む画像データベースと、
問合せ画像を受信し、前記問合せ画像と前記複数の画像の１つとの間のマハラノビスの距離を計算する、前記プロセッサが実行可能なソフトウェアプログラムと、
を備えることを特徴とするシステム。
【請求項９】
請求項８に記載のシステムであって、前記ソフトウェアプログラムが、
前記画像データベース内の前記複数の画像の１つ以上の特徴を用いて、分散−共分散マトリックスをさらに構築することを特徴とするシステム。
【請求項１０】
請求項９に記載のシステムであって、前記ソフトウェアプログラムが、
前記複数の画像の１つ以上の特徴の平均を計算するステップと、
前記複数の画像の１つ以上の特徴の分散を計算するステップと、
前記複数の画像の特徴の対間の共分散を計算するステップと、
によってマハラノビスの距離をさらに計算することを特徴とするシステム。
【請求項１１】
請求項１０に記載のシステムであって、前記ソフトウェアプログラムが、
前記画像データベースの第１の画像の１つ以上の特徴を数値的に特徴付ける第１のベクトルを含む前記第１の画像を識別するステップと、
前記問合せ画像の１つ以上の特徴を数値的に特徴付ける、前記問合せ画像に対する問合せベクトルを識別するステップと、
によって前記マハラノビスの距離をさらに計算することを特徴とするシステム。
【請求項１２】
請求項１１に記載のシステムであって、前記ソフトウェアプログラムが、
差ベクトルを作るために、前記第１のベクトルと前記問合せベクトルとの間の差を計算するステップと、
前記差ベクトルのインバースを計算するステップと、
によって前記マハラノビスの距離をさらに計算することを特徴とするシステム。
【請求項１３】
請求項１２に記載のシステムであって、前記ソフトウェアプログラムが、
中間結果を作るために、前記差ベクトルと前記分散−共分散マトリックスのインバースとを乗算するステップと、
前記中間結果を前記差ベクトルのインバースで乗算するステップと、
によって前記マハラノビスの距離をさらに計算することを特徴とするシステム。
【請求項１４】
プロセッサベースのシステムに対して、
複数の画像の１つ以上の特徴を定量化するステップと、
前記１つ以上の特徴を含む問合せ画像を受信するステップと、
前記問合せ画像と前記複数の画像１つとの間のマハラノビスの距離を計算するステップと、
を実行可能にさせる命令を記憶する媒体を含むことを特徴とする物品。
【請求項１５】
請求項１４に記載の物品が、前記プロセッサベースのシステムに対して、
前記複数の画像の１つ以上の特徴を用いて分散−共分散マトリックスを構築するステップと、
前記１つ以上の特徴を含む第１の画像を前記複数の画像から選択するステップと、
前記分散−共分散マトリックスを用いて前記第１の画像と前記問合せ画像との間のマハラノビスの距離を計算するステップと、
を実行可能にさせる命令をさらに記憶することを特徴とする物品。
【請求項１６】
請求項１５に記載の物品が、前記プロセッサベースのシステムに対して、
前記複数の画像の特徴の平均を計算するステップと、
前記複数の画像の特徴の分散を計算するステップと、
前記複数の画像の特徴の対の間の共分散を計算するステップと、
を実行可能にさせる命令をさらに記憶することを特徴とする物品。
【請求項１７】
請求項１６に記載の物品が、前記プロセッサベースのシステムに対して、
前記計算された分散及び共分散から分散−共分散マトリックスを構築するステップと、
を実行可能にさせる命令をさらに記憶することを特徴とする物品。
【請求項１８】
請求項１７に記載の物品が、前記プロセッサベースのシステムに対して、
前記第１の画像の１つ以上の特徴を数値的に特徴付ける、前記第１の画像に対する第１のベクトルを識別するステップと、
前記問合せ画像の１つ以上の特徴を数値的に特徴付ける、前記問合せ画像に対する問合せベクトルを識別するステップと、
差ベクトルを作るために、前記第１のベクトルと前記問合せベクトルとの間の差を計算するステップと、
を実行可能にさせる命令をさらに記憶することを特徴とする物品。
【請求項１９】
請求項１８に記載の物品が、前記プロセッサベースのシステムに対して、
中間結果を作るために、前記差ベクトルを前記分散−共分散マトリックスのインバースで乗算するステップと、
前記中間結果を前記差ベクトルのインバースで乗算するステップと、
を実行可能にさせる命令をさらに記憶することを特徴とする物品。
【請求項２０】
請求項１９に記載の物品が、前記プロセッサベースのシステムに対して、
前記複数の画像の特徴を範囲ツリーの中に記憶するステップと、
を実行可能にさせる命令をさらに記憶することを特徴とする物品。
【発明の詳細な説明】
【技術分野】
【０００１】
［背景］
本発明は画像処理に関し、より詳細には、画像の特徴付けに関する。
【背景技術】
【０００２】
画像処理とは、コンピュータを用いて画像を分析及び操作することを指す。この研究分野には、いくつかの例を挙げると、パターン認識及び他の画像分析、画像送信の場合の圧縮及び符号化、及び画像構成を含む多様な技術が含まれる。画像処理は、天文学、医学、軍事行動、通信、地質学、気象学などの多種多様な分野で使用される。
【０００３】
画像は、たとえ自然に見える場合でも、コンピュータ又は他のプロセッサベースのシステムが画像を「見る」ように、又は例えば画像を別の画像から区別するように特徴付けることができる。モーメント、エントロピー、質量中心、向き、又は他のヒストグラムに基づく特徴を識別することは、画像の特徴付けに対する１つの方式である。画像の構造的及び総合的な特徴は、特性パラメータとしての役目をする。周辺、領域、偏心率、又はオイラー数（Euler number）などの幾何学的な指標は、画像を数的に識別することができる。
【０００４】
画像は送信の間などで摂動を受けることが多いので、画像の特性パラメータは変換の後であっても不変であることが理想である。画像変換には、変形、回転、拡大縮小、シャーリング、圧縮、ノイズの包含などが含まれる。
【０００５】
特に、インターネット技術の新興ドメインでは、画像検索は重要なツールである。しかしながら、画像検索で使用される画像の種々の特性により、結果が大きく変わることがある。この種の画像検索は、内容ベースの画像検索として周知である。
【０００６】
画像データベースから画像を検索する１つの技術は、各画像をある数の特徴と関連付けることである。特徴ベクトル（feature vector）を用いて、その特徴ベクトルによって示された各画像は、ｎ個の特徴が識別されるｎ次元の特徴空間（feature space）内の点にマッピングされる。次に、類似性問合せ（similarity query）を用いて、問合せ画像に近い近傍にある画像を検索する。
【０００７】
これらの類似性問合せを実行する場合、画像を取得する正確さは、画像データベースの大きさと類似性問合せの中に含まれる様々な特徴を計算する時間とによって相殺される。
【０００８】
従って、画像検索方法を最適化するための継続的な要求がある。
【発明の開示】
【０００９】
［詳細な説明］
〈オイラー数〉
画像を画像データベースから検索するためには、各画像を特徴付けて、それを他の画像から区別する必要がある。例えば、画像を数値的に特徴付ける。
【００１０】
例えば、２値画像データベースの各２値画像にオイラー数を割り当てる。２値画像のオイラー数は、画像内の連結されたコンポーネント（オブジェクト）の数と画像内の穴（hole）の数との間の差である。
【００１１】
オイラー数は、２値画像の位相的な特徴である。オイラー数は２値画像を変形、回転、拡大縮小及びゴムシート変換（rubber-sheet transformation）する場合でも変化しないで残る。
【００１２】
２値画像１６を、Ｎ×Ｍの画素マトリックス２０の中で表示することができる。ここで、図１に示すように、オブジェクト画素１２は２値の１を表示するために網掛けされているが、一方背景画素１２は２値の０を示すために網掛けされていない。Ｎ×Ｍの画素マトリックス２０の中では、連結成分は、オブジェクト画素のセットであって、そのセット内の任意のオブジェクト画素１２が同じセットの少なくとも１つのオブジェクト画素１２の８（又は４）近傍であるようなオブジェクト画素のセットをいう。４近傍１４及び８近傍１８の両方が、図２に示されている。
【００１３】
２値画像における連結成分に加えて、１つの実施形態では、ホールが、セット内の任意の背景画素が同じセットの少なくとも１つの背景画素の４（又は８）近傍内にあり、背景画素のこの全体のセットが連結成分によって囲まれるような背景画素のセットとして定義される。
【００１４】
画素マトリックス２０のｉ番目の列（又は行）の連なりは、ｉ番目の列（又は行）内の連続する画素の最大の連続体と定義される。各２つの隣接する列（行）内に現れる２つの連なりは、連なりうちの少なくとも１つの画素が他の連なりの画素の８（又は４）近傍の中にある場合は隣接していると称される。
【００１５】
Ｉとして知られる２値画像１６が１つの行（列）ｉから構成する場合、画像１６のオイラー数Ｅ（Ｉ）は、下記の式で示すように、Ｒ（ｉ）として示された画像１６の連なりの数と同じである。
【数１】
2004532458.tif 000003
しかしながら、２値画像１６が複数の行（列）から構成する場合、２値画像Ｉは部分画像Ｉiに分割される。さらに、画像全体のオイラー数は、下記の式を用いて見つけることができる。
【数２】
2004532458.tif 000004
ここで、Ｏｉは２つの連続する行（列）、例えば、（ｉ−１）番目及びｉ番目の間の隣接する連なりの数に等しい。
【００１６】
１つの実施形態によれば、２値画像のオイラー数は、Ｎ×Ｍの画素マトリックスの全ての行（列）の連なりの数の合計と全ての連続する行（列）の対の間の隣接する連なりの合計との間の差として定義される。これを数式で表すと下記のようになる。
【数３】
2004532458.tif 000005
ここで、ＩN＝Ｉは全画像を示す。これにより、２値画像Ｉ内のラインの数及び隣接する連なりの数を知ることによって、オイラー数Ｅ（Ｉ）を計算できる。
【００１７】
〈オイラーベクトル（Euler Vector）〉
２値画像に対するオイラー数を、グレイ諧調の画像にまで拡大することができる。例えば、図３に示すように、グレイ諧調の画像３６をＮ×Ｍのマトリックスで示すことができる。ここで、各成分２２は、画素に対応する輝度を示す、１０進数の０と２５５との間の整数である。各成分の輝度値は、８ビットの２進ベクトル（ｂ7，ｂ6，ｂ5，ｂ4，ｂ3，ｂ2，ｂ1，ｂ0）によって表示できる。このように、グレイ諧調の画像３６は、８ビットのプレーンすなわち８つの区別できる２値画像から構成する。
【００１８】
仮想のグレイ諧調画像３６は、図示のように、それぞれが区別できる輝度値を示す３つの８ビットの画素２２ａ，２２ｂ及び２２ｃを含む。
【００１９】
１つの実施形態では、８ビットの２進ベクトルの第１の４つの最上位ビットのプレーン（ｂ7，ｂ6，ｂ5及びｂ4）が保持される。要するに、４つの２値画像が保持される。図４Ａ〜図４Ｄでは、図３のグレイ諧調画像３６の４つの最上位ビットのプレーンを示す４つの２値画像１８ａ〜１８ｄが示されている。各２値画像１８ａ〜１８ｄに対してオイラー数を計算することができる。
【００２０】
１つの実施形態では、各２値画像１８に対してオイラー数を計算する前に、４ビットの２進ベクトル（ｂ7，ｂ6，ｂ5，ｂ4）が、その対応する交番グレイコードのベクトル（ｇ7，ｇ6，ｇ5，ｇ4）に変換される。この場合：
【数４】
2004532458.tif 000006
ここで、
【数５】
2004532458.tif 000007
はＸＯＲ（モジュロ２）演算を示す。交番グレイコード変換の結果は、１つの実施形態に基づいて、それぞれ図５Ａ〜図５Ｄの２値画像２８ａ〜２８ｄに示されている。任意の２進ベクトルに対して、対応する交番グレイコードは一意的であり、逆の場合も同様であることは周知である。
【００２１】
このため、１つの実施形態では、本来のグレイ諧調画像Ｋのオイラー数ξKは４タプル（Ｅ7，Ｅ6，Ｅ5，Ｅ4）である。ここで、Ｅiは、輝度値の交番グレイコード表示に対応するｉ番目のビットプレーン４≦ｉ≦７によって形成された部分２値画像ｇiのオイラー数である。
【００２２】
従って、２値画像に対してオイラー数を計算することに加えて、画像の４つの最上位の２進ビットプレーンを検討すること、４ビットの２進ベクトルをその対応する交番グレイコードに変換すること、及び各交番グレイコードの表示に対してオイラー数を計算することによって、グレイ諧調画像のオイラーベクトルを計算することができる。
【００２３】
オイラーベクトルを用いてグレイ諧調画像を特徴付けることにおいて、オイラーベクトルの成分は、場合によっては、重要度が減少する順となる。すなわち、成分Ｅ7は画像の特徴付けにおいては最上位であり、次はＥ6、等々である。さらに、オイラーベクトルの種々の成分の範囲及び分散は異なっている。そのような環境では、マハラノビスの距離（Mahalanobis distance）を採用して、画像の集合の特徴に対する特性の類似点及び相違点を捕捉する測度を提供することができる。
【００２４】
〈マハラノビスの距離〉
このように、オイラー数Ｅiは２値画像を特徴付けることができる。拡大することにより、４つのオイラー数Ｅ7，Ｅ6，Ｅ5，及びＥ4を含むオイラーベクトルζiは、グレイ諧調の画像を特徴付けることができる。各オイラー数Ｅiは、１つの実施形態によれば、グレイ諧調画像の「特徴」として説明される。１つの実施形態では、オイラーベクトルの特徴は画像検索用のベースを形成する。
【００２５】
オイラーベクトルξKが、画像データベース内で各グレイ諧調画像Ｋについての特徴を表すと仮定する。オイラーベクトルξqによって定義された特徴を有する新しい画像ｑが、画像データベースから検索されるとする。新たに受信された画像ｑが、画像データベース内のそれぞれの画像と比較される。適合すると認められると、画像検索は完了する。
【００２６】
２つの事物を比較する１つの方法は、それらの間の距離を測定することである。距離の測定は、数などのスカラーの間で行われるが、ベクトル間で行うこともできる。画像がベクトルを用いて表現される場合、そのベクトルとそれ自体のベクトルを有する第２の画像との間の距離は、計算することができる。従って、２つの画像間の距離を計算することができる。
【００２７】
問合せ画像３０ｑが、画像データベース４０の中で見つからないと仮定する。正確に一致しているかどうかを比較するのではなく、１つの実施形態では、問合せ画像３０ｑとデータベース内の他の画像との間の距離の測定が行われる。１つの距離測定法は、マハラノビス距離測定法として周知である。このマハラノビス距離測定法は、問合せ画像３０ｑとデータベース内の他の画像との間の「距離」を計算し、次に、距離の結果を配列する。最小の距離の結果が「一致する」とされる。
【００２８】
マハラノビスの距離測定動作が、１つの実施形態に基づいて、図６に示されている。システム１００は、プロセッサ８０、画像データベース４０及びマハラノビスの距離測定部６０を含む。画像データベース４０は、それぞれが関連するオイラーベクトルξKを有する複数の画像３０を含む。マハラノビスの距離測定部６０は、画像データベース４０から各画像３０を受け取り、それらをそれ自身のオイラーベクトルξqを含む問合せ画像３０ｑと比較する。１つの実施形態では、マハラノビスの距離測定部６０は、問合せ画像３０ｑと画像データベース４０からの１つ以上の画像３０との間のマハラノビスの距離測定を実行するソフトウェアのプログラムである。
【００２９】
１つの実施形態による結果テーブル５０は、問合せ画像３０ｑと画像データベース４０内の１つ以上の画像３０との間の距離を計算する機能を含む。１つの実施形態では、距離の結果が大きさに従って配列される。このため、結果テーブル５０内の最初（又は最後）に記入された結果が距離計算の「適合距離」である。
【００３０】
画像データベース４０内のそれぞれの画像３０は、オイラーベクトルξKに基づいて分類又は表現される。オイラーベクトルの成分すなわちオイラー数Ｅ7，Ｅ6，Ｅ5及びＥ4は、分類されたグレイ諧調画像３０の特徴を示す。従来は、２つのベクトル間の距離の測定値を使用して、２つのベクトルの「親密さ」を捉える。例えば、ベクトルｘとｙとの間のユークリッドの距離（Euclidean distance）は、下記の式によって与えられる。ここで、ｘは４つの成分ｘ1，ｘ2，ｘ3及びｘ4を有し、ｙも同様に４つの成分ｙ1，ｙ2，ｙ3及びｙ4を有する。
【数６】
2004532458.tif 000008
【００３１】
現象によっては、このユークリッド距離が、極めて優れた距離の測定値を示さないことがある。オイラーベクトルによってグレイ諧調画像を特徴付ける場合、ベクトルの成分が重要度の減少レベルを有することを思い出してほしい。すなわち、Ｅ7はグレイ諧調画像３０を特徴付ける上でＥ6よりも重要であり、Ｅ6は画像３０を特徴付ける上でＥ5よりも重要である、等々である。
【００３２】
さらに、ベクトルの成分（Ｅ7，Ｅ6，Ｅ5及びＥ4）の範囲及び分散は、それらの大きさが大きく異なる。そのような環境では、マハラノビスの距離は、データベース４０の画像３０間の類似点／相違点の特性を捉えるために、ユークリッド距離よりもより優れた測定値を提供することができる。
【００３３】
２つのベクトルｘとｙとの間のマハラノビスの距離は、下記の式から引き出すことができる。
【数７】
2004532458.tif 000009
ここで、’はマトリックスの転置を示す。ＭVCは、画像特徴ベクトル：ｘ’＝（ｘ1，ｘ2，．．．ｘN）及びｙ’＝（ｙ1，ｙ2，．．．ｙN）によって形成された分散−共分散マトリックスである。ここで、（ｘ−ｙ）’は（１×ｎ）マトリックス、ＭVC−１は（ｎ×ｎ）マトリックス、及び（ｘ−ｙ）は（ｎ×１）マトリックスであり、このため、それらの積はスカラーである。
【００３４】
ＭVCとして示されたｘの分散−共分散マトリックスは、下記の式によって与えられたＮ×Ｎマトリックスである。
ＭVC（ｉ，ｊ）＝ｉ番目の特徴ｘiの分散、ｉ＝ｊの場合
＝ｉ番目の変数ｘi及びｊ番目の変数ｘjの共分散、ｉ≠ｊの場合
Ｍｖｃ（ｉ，ｊ）＝ＭVC（ｊ，ｉ）であることに注意されたい。ｘの分散−共分散マトリックスは、分散マトリックス（dispersion matrix）としても周知である。
【００３５】
画像特徴ベクトルの分散−共分散マトリックスを計算するために、分散及び共分散の両方を計算する。特徴ｘiの分散は下記のように定義される。
【数８】
2004532458.tif 000010
ここで、Ｌは、変数（特徴）ｘiの観測の数である。
【００３６】
グレイ諧調画像の特徴にも相関がある場合がある。任意の２つの特徴間の相関の測定は、共分散として周知である。共分散は下記のように定義される。
【数９】
2004532458.tif 000011
【００３７】
分散及び共分散の値が決定されると、分散−共分散のマトリックスＭVCを計算することができる。この分散−共分散のマトリックスＭVCは下記のようになる。
【数１０】
2004532458.tif 000012
【００３８】
図７において、画像３０のデータベースに対する分散−共分散のマトリックスＭVCが、１つの実施形態に基づいて計算される。説明のために、画像データベース４０は、それぞれの画像３０Ｋが関連するオイラーベクトルξKを有する画像３０を含むと仮定する。各オイラーベクトルξKは、画像３０Ｋの「特徴」を構成するオイラー数ＥK7，ＥK6，ＥK5及びＥK4を含む。
【００３９】
データベース４０の全ての画像３０に対して、分散−共分散のマトリックスを計算できる。その後、問合せ画像３０ｑが、図６に示すように、システム１００により受信される。いったん分散−共分散のマトリックスＭVCが計算されると、画像の問合せにより所望の画像が迅速に検索される。
【００４０】
１つの実施形態では、マハラノビスの距離測定部６０は、画像データベース４０の各特徴の平均を計算する（ブロック２０２）。オイラーベクトルξKは４つの特徴すなわちオイラー数Ｅ7〜Ｅ4を含むため、下記のように４つの平均計算が行われる。
【数１１】
2004532458.tif 000013
ここで、ｊは画像データベース４０内の画像番号である。
【００４１】
データベース４０内の各画像３０の特徴には相関がある場合がある。任意の２つの特徴間の相関の測定が、上記で定義された共分散方程式内に反映される。このため、１つの実施形態では、画像３０の特徴間の共分散が計算される（ブロック２０６）。例えば、図示したデータベース４０では、下記の共分散の方程式が計算される。
【００４２】
【数１２】
2004532458.tif 000014
共分散が、オイラー数Ｅ7とＥ6、Ｅ7とＥ5、Ｅ7とＥ4、Ｅ6とＥ5、Ｅ6とＥ4、及びＥ5とＥ4との間で計算される。共分散は結合性である。このため、ｃｏｖ（Ｅ7，Ｅ6）＝ｃｏｖ（Ｅ6，Ｅ7）等々となる。
【００４３】
画像データベース４０の特徴Ｅ7，Ｅ6，Ｅ5及びＥ4に対する分散及び共分散を知ることができたので、１つの実施形態に基づいて分散−共分散のマトリックスＭVCを計算することができる（ブロック２０８）。オイラーベクトルξKを用いて特徴付けられた画像データベースに対しては、分散−共分散のマトリックスＭVCは下記のようになる。
【数１３】
2004532458.tif 000015
図７による分散−共分散マトリックスの計算は、このように完了する。
【００４４】
分散−共分散のマトリックスＭVCが判明すると、問合せ画像３０ｑと画像データベース４０内の１つ以上の画像３０との間で、マハラノビスの距離が測定される。
【００４５】
１つの実施形態では、マハラノビスの距離が図８のフローチャートに基づいて計算される（ブロック３０２）。最初に、２つのベクトル間の差が計算される。各ベクトルは、所定の画像３０に対する特徴情報を含む。例えば、問合せ画像３０ｑと画像データベース４０の画像３０ａとの間のマハラノビスの距離を求める場合、オイラーベクトルξqとξaとの間の差が計算される。このオイラーベクトルξqとξaとの間の差は、下記のようになる。
【数１４】
2004532458.tif 000016
同様に、転置（ξq−ξa）’は下記のようになる。
【数１５】
2004532458.tif 000017
【００４６】
さらに、画像３０ｑと画像データベース４０内の任意の画像３０との間のマハラノビスの距離を計算するために、分散−共分散マトリックスＭVCのインバースすなわちＭVC-1が計算される（ブロック３０４）。マトリックスＭVCのインバースは、周知の原理に基づいて計算される。
【００４７】
これらの演算から、マハラノビスの距離が計算される（ブロック３０６）。例えば、問合せ画像３０ｑを用いて、マハラノビスの距離が問合せ画像３０ｑと画像データベース４０内の１つ以上の画像３０との間で、下記のように計算される。
【数１６】
2004532458.tif 000018
【００４８】
１つの実施形態では、マハラノビス距離測定部６０は、最小の値から最大の値に向かう順序で距離の計算結果を配列する。このため、結果テーブル５０への最初のエントリーが、問合せ画像３０ｑに最も近い一致画像である。１つの実施形態では、画像の特徴を表すものとしてオイラーベクトルを、また最も近い尺度としてマハラノビスの距離を用いて、所望の画像が最短の距離にあると判明される。問合せ画像３０ｑのノイズのあるバージョン及び圧縮バージョンは、結果テーブル５０では直ぐ上の階数を有する。
【００４９】
いくつかの実施形態では、画像３０を特徴付けるために使用される様々な特徴は、検索するために等しく重要であるということではない。そのような場合、分散−共分散マトリックスＭVCの成分は、対応する特徴の重要性に従って、適当な重み付け係数によって乗算される。
【００５０】
極めて大きいデータベースについては、問合せ画像３０ｑからデータベース４０内の全ての他の画像３０までの距離を計算するには、かなりの時間を必要とする。このため、分類し次に検索するには極めて時間がかかる。この問題をうまく回避するために、多次元検索技術を使用して、特徴空間内の問合せ画像３０ｑの付近にある画像のサブセットを検索する。次に、提案された距離測定による分類をこのサブセットだけに行う。
【００５１】
〈範囲ツリー（Range Tree）〉
データベース内の項目を見つけるために利用できる多くの技術がある。例として、データベースの順次検索が存在し、ハシュテーブル（hash table）を使用でき、また二分探索技術を採用することができる。二分木は、データセット内の項目を記憶、削除及び検索するために使用されるデータ構造である。画像データベース４０内の画像３０に関しては、データベース４０内の画像の全てのｊを検索せずに、問合せ画像３０ｑに類似した画像３０を見つけ出すことが望ましい。
【００５２】
１つの実施形態では、多次元検索ツリーを例えば画像３０を記憶するために使用する。この多次元検索ツリーは、画像３０の効果的な検索を可能にする。
【００５３】
１つの実施形態では、画像はランダムに二分木内に記憶される。しかしながら、データは二分木内にランダムな順序で挿入されないことがある。このため、二進検索の性能は、最適な場合よりも劣る。二分木は、各データを挿入又は削除した後で「再平衡」（“rebalance”）される。再平衡動作の間に、二分木のノードは回転することにより再整理される。一般に、これらの回転により二分木の高さは最小にされる。
【００５４】
二分木の１つの種類は、（その創作者Adelson-Velskii 及び Landisの名前から名付けられた）ＡＶＬツリーとして知られている。二分木のこの特定の形態では、再平衡を取ることにより、ＡＶＬツリー内の各ノードに対して、平衡係数（balance factor）として周知の、そのサブツリー間の高さの差は１より大きくないことが確実にされる。
【００５５】
１つの実施形態では、図６に示すように、４次元の範囲ツリー（range tree）６２は、データベース４０内の各画像３０に関連したオイラーベクトルξKを記憶するためのデータ構造として使用される。範囲ツリー６２は、オイラーベクトルが４つの特徴、すなわち、オイラー数Ｅ7，Ｅ6，Ｅ5及びＥ4を含むため４次元である。問合せ画像３０ｑに対してオイラーベクトルξqを用いて、範囲ツリー６２は特定のノードを規定する。１つの実施形態では、マハラノビスの距離測定部６０が、問合せ画像３０ｑと、範囲ツリー６２の全ての画像３０ではなくノードにある画像のみとの間で実現される。結果は、第１の距離の値が適合画像３０を指し示すように、降順に配列される。
【００５６】
本発明を限られた数の実施形態に関して説明してきたが、当業者はこれらの実施形態からの多くの修正例及び変更例を理解されよう。添付した特許請求の範囲が、本発明の真の精神及び範囲の中に入る全てのそのような修正例や変更例をカバーするものとする。
【図面の簡単な説明】
【００５７】
【図１】本発明の１つの実施形態による２値画像のブロック図である。
【図２】本発明の１つの実施形態による４近傍及び８近傍のブロック図である。
【図３】本発明の１つの実施形態によるグレー諧調画像のブロック図である。
【図４】図４Ａ〜図４Ｄは、本発明の１つの実施形態による、図３のグレー諧調画像の２値画像である。
【図５】図５Ａ〜図５Ｄは、本発明の１つの実施形態による、図３のグレー諧調画像の交番グレーコードの表示である。
【図６】本発明の１つの実施形態によるシステムのブロック図である。
【図７】本発明の１つの実施形態による、図６のシステムの複数の画像に対して分散−共分散マトリックスを計算するためのフローチャートである。
【図８】本発明の１つの実施形態による、図６のシステムの問合せ画像と複数の画像との間のマハラノビス距離（Mahalanobis distance）を計算するためのフローチャートである。
【図１】
2004532458.tif 000019
【図２】
2004532458.tif 000020
【図３】
2004532458.tif 000021
【図４】
2004532458.tif 000022
【図５】
2004532458.tif 000023
【図６】
2004532458.tif 000024
【図７】
2004532458.tif 000025
【図８】
2004532458.tif 000026
【国際公開パンフレット】
2004532458.tif 000027
2004532458.tif 000028
2004532458.tif 000029
2004532458.tif 000030
2004532458.tif 000031
2004532458.tif 000032
2004532458.tif 000033
2004532458.tif 000034
2004532458.tif 000035
2004532458.tif 000036
2004532458.tif 000037
2004532458.tif 000038
2004532458.tif 000039
2004532458.tif 000040
2004532458.tif 000041
2004532458.tif 000042
2004532458.tif 000043
2004532458.tif 000044
2004532458.tif 000045
2004532458.tif 000046
2004532458.tif 000047
2004532458.tif 000048
2004532458.tif 000049
2004532458.tif 000050
2004532458.tif 000051
2004532458.tif 000052
【国際公開パンフレット（コレクトバージョン）】
2004532458.tif 000053
2004532458.tif 000054
【国際調査報告】
2004532458.tif 000055
2004532458.tif 000056
2004532458.tif 000057
2004532458.tif 000058