(57)【要約】ディジタル画像の簡潔な表現を発生する方法が記述されている。ディジタル画像は正方形ビットマップに変換され、複数個のセルに分割される。各セルは複数個の領域に副分割される。複数個のセルの各組で各セルの最小明暗度領域と最大明暗度領域とが認識される。セルの最小明暗度領域と最大明暗度領域の位置を基にセルの各組中の各セルに対してセル表現データが発生される。画像のセルの各組のセル表現データの全てを組合わせて、元のディジタル画像の簡潔な表現を作成する。セル表現データを比較する方法も説明されている。ソース画像の集合のセル表現データがデータベースに構成される。データベースの探索は、ターゲット画像に少なくとも最小に同様である候補画像を識別する。次いでターゲット画像が各識別された候補画像と直接比較され、各候補画像の同様性スコアが計算され記録される。
2004522228.tif 000002
【特許請求の範囲】
【請求項１】
ディジタル画像の簡潔な表現を発生する方法であって、
ディジタル画像を複数個のセルに分割する段階と、
複数個のセルの各組中で各セルの最小明暗度領域を識別する段階と、
複数個のセルの各組中で各セルの最大明暗度領域を識別する段階と、
当該セル中の最小明暗度領域と最大明暗度領域の位置を基にセルの各組で各セルに対してセル表現データを発生する段階と、
ディジタル画像の表現を発生する段階であって、該表現はセル表現データを含む前記発生段階と、
を含む方法。
【請求項２】
請求項１記載の方法において、ディジタル画像を複数個のセルに分割する前に元のディジタル画像を正方形ビットマップに変換する段階をさらに含む方法。
【請求項３】
請求項１記載の方法において、各セルを複数個の領域に副分割する段階をさらに含む方法。
【請求項４】
請求項３記載の方法において、各領域のピクセル明暗度和を計算する段階をさらに含み、各領域のピクセル明暗度和は当該領域に含まれるピクセルの明暗度の和を表す方法。
【請求項５】
請求項４記載の方法において、最小及び最大明暗度領域は計算されたピクセル明暗度和を基に識別される方法。
【請求項６】
請求項１記載の方法において、低コントラストを有するセルを識別する段階をさらに含み、低コントラスト識別子を各識別されたセルに関連付ける方法。
【請求項７】
請求項６記載の方法において、低コントラストのセルが優勢である画像を検出した時に、画像のコントラストを動的に増加して、そのセル表現データを再計算する方法。
【請求項８】
請求項６記載の方法において、低コントラスト識別子は負の整数である方法。
【請求項９】
請求項６記載の方法において、ディジタル画像の表現はセル表現データを含む方法。
【請求項１０】
請求項１記載の方法において、各セルの明暗度角度は、水平基準線とセルの最小明暗度領域とその最大明暗度領域との間で形成された線との間の角度を基にして発生される方法。
【請求項１１】
請求項１０記載の方法において、各セルのセル表現データは、セルの明暗度角度の値または低コントラスト識別子のどちらかを表す整数である方法。
【請求項１２】
第１及び第２のディジタル画像を比較し、比較した画像の同様性の程度を決定する方法であって、
画像内の最小及び最大明暗度領域の相対位置を基に第１及び第２ディジタル画像の表現を発生する段階と、
第１及び第２のディジタル画像の表現を比較し、比較を基にして同様性スコアを発生する段階であって、同様性スコアは画像間の同様性の程度を表す前記発生段階と、
を含む方法。
【請求項１３】
請求項１２記載の方法において、第１及び第２のディジタル画像の各々の表現は、
第１及び第２ディジタル画像を複数個のセルに分割する段階と、
複数個のセルの各組で各セル中の最小明暗度領域を識別する段階と、
複数個のセルの各組で各セル中の最大明暗度領域を識別する段階と、
当該セル中の最小明暗度領域と最大明暗度領域との位置を基にセルの各組で各セルのセル表現データを発生する段階と、
第１及び第２ディジタル画像の表現を発生する段階であって、表現はセル表現データを含む前記発生段階と、
により発生される方法。
【請求項１４】
請求項１３記載の方法において、第１及び第２ディジタル画像の各々を複数個のセルに分割する前に、第１及び第２ディジタル画像の各々を正方形ビットマップに変換する段階をさらに含む方法。
【請求項１５】
請求項１３記載の方法において、各セルを複数個の領域にさらに副分割する段階をさらに含む方法。
【請求項１６】
請求項１５記載の方法において、各領域のピクセル明暗度和を計算する段階をさらに含み、ピクセル明暗度和は当該領域に含まれるピクセルの明暗度の和を表す方法。
【請求項１７】
請求項１６記載の方法において、最小及び最大明暗度領域は計算されたピクセル明暗度和を基に識別される方法。
【請求項１８】
請求項１３記載の方法において、低コントラストを有するセルを識別し、各識別されたセルに低コントラスト識別子を関連付ける段階をさらに含む方法。
【請求項１９】
請求項１８記載の方法において、第１及び第２ディジタル画像の各々の表現はセル表現データを含む方法。
【請求項２０】
請求項１３記載の方法において、各セルの明暗度角度は、基準線とセルの最小明暗度領域とその最大明暗度領域との間で形成された線との間の角度を基に発生される方法。
【請求項２１】
請求項２０記載の方法において、各セルのセル表現データは、そのセルの明暗度角度かまたは低コントラスト識別子のどちらかを表す整数である方法。
【請求項２２】
ディジタル・ターゲット画像と同様であるディジタル画像のライブラリ中の候補画像を識別し、ターゲット画像に対する候補画像の同様性の程度を決定する方法であって、
ディジタル・ターゲット画像とディジタル画像のライブラリ中のディジタル・ソース画像を複数個のセルに分割する段階と、
ディジタル・ターゲット及びライブラリ中のソース画像の各セル中の最小明暗度領域を識別する段階と、
ディジタル・ターゲット及びライブラリ中のソース画像の各セル中の最大明暗度領域を識別する段階と、
各ディジタル・ソース及びターゲット画像の各セル中の最小明暗度領域と最大明暗度領域の位置を基に、各ディジタル・ターゲット及びライブラリ中のソース画像中の各々のセルに対してセル表現データを発生する段階と、
各ソース画像のセル表現データに従って画像を組織する候補画像データベースを発生する段階と、
候補画像データベースを探索して、ターゲット画像と同様な少なくとも１つのセルを有する候補画像を識別する段階と、
ターゲット画像と同様の少なくとも１つのセルを有するものとして識別された候補データベースからの各画像をターゲット画像と比較する段階と、
ターゲット画像と比較したディジタル画像の同様性スコアを計算する段階と、
を含む方法。
【請求項２３】
請求項２２記載の方法において、候補データベースは複数個の角度インデックス分類に構成され、分類の数は可能なセル表現データ値の数の置換されたカウントに対応し、各分類は一連のアレイにさらに副分割され、アレイの数は各ディジタル画像が分割されたセル数までの数に対応し、該アレイは角度インデックス分類と関係するアレイに対応するセルの現在の角度インデックス分類に割当てた値に対応するセル表現データを有する画像の識別子を含む、方法。
【請求項２４】
ターゲット画像と同様のソース画像のライブラリ中の候補画像を識別する方法であって、
ターゲット及びソース画像内の最小及び最大明暗度領域の相対位置を基にターゲット画像とソース画像の各々の表現を発生する段階と、
候補画像リストを発生する段階であって、各候補画像はターゲット画像との少なくとも所定の同様性の程度を有する前記発生段階と、
ターゲット画像と候補画像の表現を比較し、この比較を基に同様性スコアを発生する段階であって、同様性スコアはディジタル画像の同様性の程度を表す前記発生段階と、
を含む方法。
【請求項２５】
請求項２４記載の方法において、第１及び第２ディジタル画像の表現は複数個の明暗度角度を含む方法。
【請求項２６】
請求項２４記載の方法において、第１及び第２ディジタル画像からのセル表現はセルの複数個の組間でセル毎に比較される方法。
【請求項２７】
請求項２５記載の方法において、ターゲット及び候補ディジタル画像の表現を含む複数個の明暗度角度を置き換える段階をさらに含む方法。
【請求項２８】
請求項２４記載の方法において、ターゲット及び候補ディジタル画像の各々の表現は、明暗度、色、色相、彩度、バリュー、輝度、及びクロミナンスを含むリストから選択された１つ以上の画像属性を基にしている方法。
【請求項２９】
ディジタル画像の簡潔な表現を発生する方法であって、
ディジタル画像を複数個のセルに分割する段階と、
複数個のセルの各組の各セル中で最小画像データ値領域を認識する段階と、
複数個のセルの各組の各セル中で最大画像データ値領域を認識する段階と、
当該セルの最小画像データ値領域と最大画像データ値領域の位置を基にセルの各組中の各セルに対してセル表現データを発生する段階と、
ディジタル画像の表現を発生する段階であって、この表現はセル表現データを含む前記発生段階と、
を含む方法。
【請求項３０】
請求項２９記載のディジタル画像の簡潔な表現を発生する方法において、画像データ値は、明暗度、色、色相、彩度、バリュー、輝度、及びクロミナンスを含むグループのうちの１つから得られる方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願との相互参照）なし
本発明は、異なる画像を互いに比較することを可能とする方法でディジタル画像を表現する方法に関係する。ディジタル画像を画像データベースに記憶する時、どの画像を記憶したか、そして各々をどこに配置したかを覚えるのは困難である。個人が新たな画像を追加する時、新たな画像を記憶画像と迅速に比較し、データベースが既に同様の画像またはこれと似たものを含んでいるかどうかを決定できると有用である。
【背景技術】
【０００２】
同様な似た画像はいくつかの異なるソースから発生する。例えば、画像ソフトウェアを使用して、ディジタル写真のテキストを追加したり、トリミングしたり、またはコントラストを増加できる。さらに、わずかに異なった視点から、または異なった露出設定で２つの画像が同じ対象を表示しても良い。このような場合、同一ではないが互いに同様な似た画像が生じる。ユーザーに同様な画像が既にデータベースに記憶されているかどうかを知らせて、ユーザーの時間と記憶空間を節約するシステムがあると有用である。さらに、関連画像を識別することにより、前記システムは関連画像を互いに自動的に構成しグループ分けすることにより画像管理処理を補助できる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
多数の画像管理アプリケーションが、ユーザーがデータベース中の画像にテキストを、通常コメントまたは説明欄に手動で関連付けることを可能としている。ユーザーはこの記憶テキストを基に画像を検索可能である（例えば「バラ」コメントを有する全ての画像を表示する）。複雑な画像処理技術により同様な画像を識別するコンテンツベースの画像検索システムが開発されてきた。これらの画像比較アルゴリズムはしばしば計算量が膨大であり、その結果を返すまでに相当な時間が掛かる。これらのシステムで使用される方法は、色、形状、及びテキスチャ計算としばしば関係し、ユーザーによる膨大なパラメータ調節を必要とし、時間のかかるデータ処理技術を使用している。同様な画像を見出すため、ディジタル画像を互いに比較する簡単で高速な方法の必要がある。
【課題を解決するための手段】
【０００４】
（発明の要約）
本発明によるディジタル画像の表現を発生する方法は、元の画像を正方形のビットマップに変換し、次いでビットマップを複数個の正方形セルに分割する段階を含む。各セルはさらに複数個の正方形領域に副分割される。各セルで最小明暗度(intensity)（輝度:brightness）を有する領域と最大明暗度を有する領域の両方を見出す。最小明暗度値、最大明暗度値、及び最大明暗度領域に対する最小明暗度領域の相対位置が各セルの表現データを構成する。元のディジタル画像の簡潔な表現を作成するために、本方法は正方形ビットマップ中の各セルの表現データを組合わせる。
【０００５】
本発明の方法の重要な関係式は、視覚的に同様な画像は同様なセル表現データを発生する点である。画像を比較し画像ライブラリ中の同様な画像を検索するために本方法により相対的に少量の情報が使用される。本発明の方法は、ディジタル画像を表現し互いに比較する従来技術より複雑でなく、かつより効率的である。画像は少量の情報により正確に表現され、相対的に迅速で堅牢な方法で互いに比較できる。
【０００６】
（発明の詳細な説明）
開示の都合上、ソース画像を、セル表現データを計算する画像または大画像の一部として定義する。ターゲット画像は現在の同様な画像検索の対象であるソース画像を一般的に識別する。候補画像は、現在のターゲット画像との同様性を決定するために検査されている画像である。ターゲット及び候補画像の表現データを含む画像の集団を画像ライブラリまたは画像データベースと呼ぶ。
【０００７】
画像を本方法で表現する時、そのセル表現データが計算され、必要に応じて、ユーザーのデータベースの同様の画像を探索する。または、本方法を使用して、ユーザーが探索を実行したい時にターゲット及び候補画像のセル表現データを計算し、これによりユーザーが永続的な画像データベースを保持することをオプションとしてもよい。
【０００８】
図１は、本発明の方法を矩形（１０２１ｘ７３９ピクセル）ソース画像に適用することにより発生された正方形ビットマップ画像２８Ａを示す。（本発明により操作されるビットマップを一般的に指す時、参照番号「２８」を使用し、特定のビットマップを指す時には、番号「２８」に文字を追加する。）ビットマップ２８Ａは本方法によりたまたま９個のセル３０に分割された。いくつかのセルをマーク付けして、その最小明暗度（最も暗い）領域３２Ａとその最大明暗度（最も明るい）領域３２Ｂと相対位置を示す。これらの領域３２Ａと３２Ｂは最暗領域から最明領域へ引かれた線３６により接続される。（一般的に明暗度領域を参照する時、参照番号「３２」を使用し、最小及び最大明暗度領域を参照する時、文字「Ａ」と「Ｂ」を各々参照番号「３２」に添付する。）セル明暗度角度３８は、線３６が水平基準線４０に対して形成する角度（０から３５９）として示される。明確な最明及び最暗領域を決定するセル中の十分なコントラストがない場合、そのセルの明暗度角度値は「低コントラスト」定数値に設定される。図１の上右隅に示すように、この値は−1が望ましいが、他の値を使用してもよい。
【０００９】
本発明の方法は、明暗度以外の画像属性にも、単独でまたは明暗度値と組合わせて、組み込むようにできることも理解すべきである。このような属性には、以下には限定されないが、色、色相、彩度、バリュー、輝度、及びクロミナンスを含む。さらに、本方法が画像明暗度を使用してセル表現データを計算していて、低コントラスト・セル３０が優勢な画像に出会った時に、ビットマップ画像２８のセルのコントラストを動的に増強し、当該画像のセル表現データを再計算する。これは、「ぼやけ（washed out）」画像が実際には顕著な相違がある時に互いに同様なものとして誤って分類されることを防止する助けとなる。
【００１０】
図２は、本発明によるディジタル画像の表現を発生する望ましい方法を図示する流れ図である。ディジタル画像はその本来のファイル形式（．ｊｐｇ、．ｂｍｐ、．ｔｉｆまたはその他の形式）で本方法に提供され、次いで「装置独立なビットマップ」に変換されてマイクロソフト（Ｒ）・ウィンドウズ（Ｒ）画像プログラム技術を使用する（図２のブロック１０）。ソース画像が正方形ビットマップ２８に変換されると、これは元のソース画像の正方形表現を作成するために引伸ばされる、及び／または圧縮される。例えば、９４２ｘ６１７ピクセルのソース画像を５００ｘ５００ピクセルのビットマップ（他の寸法を使用してもよい）に圧縮し、垂直方向より水平方向により短縮する。この結果、元のソース画像が、その寸法に係わらず、本方法には正方形ビットマップ２８として提示される。望ましい実施例では、このビットマップ変換にウィンドウズ（Ｒ）・オペレーティングシステムの「ビット伸張（ＳｔｒｅｔｃｈＢｉｔ）」画像関数を使用するが、同様の作業を他の画像処理ルーティンが実行することも可能である。
【００１１】
正方形ビットマップ２８は次いで以後の解析用に多数のセル３０に分割される（ブロック１２）。ビットマップ２８は、多分３かける３格子（９格子）から開始して多分９かける９格子（８１格子）まで、連続的により細かいセル格子に分割することが望ましい。各格子はセルの２次元アレイを近似し、アレイの各寸法は都合上セル寸法と呼ぶ。各格子のセルは、格子の左上隅のセルをセル（１、１）と識別できるよう番号付けされることが望ましい。残りのセルも同様に番号付けられ、各セルはその行と列を識別子として使用して格子の位置を識別する。ビットマップ２８の各連続した分割から発生される追加データは比較過程で繰返し的に使用されることが望ましく、各格子寸法の同様性スコアが集められてより正確な結果を生成する。
【００１２】
図２のブロック１４では、ビットマップ２８のセル３０の各々がさらに正方形領域３２に副分割される。領域３２は６かける６格子、各セル３０中で全体で３６領域として実装されることが望ましいが、この領域数は変更してもよい。
【００１３】
ブロック１６では、領域３２の各々が処理されて当該領域に含まれるピクセルの全体明暗度を合計する。２４ビット色深度を使用する実装では、各ピクセルの赤、青、及び緑成分を表す３バイトを加算する段階を含む。ピクセル明暗度を計算するために定義された各種の公式に従って、オプションの重み付けを適用して赤、青及び緑値を調節する。この過程は各領域３２の全体明暗度（輝度）を表す整数値を計算する。上述したように、ピクセル明暗度の代わりに、またはこれに加えてその他の画像属性を使用してもよいことに注意されたい。各領域３２の全体ピクセル明暗度をセル３０の現在の最小及び最大ピクセル明暗度と比較する。領域３２のピクセル明暗度がセル３０の新たな最小または最大である場合、その値を当該セルの新たな最小または最大明暗度値として保存する。セル３０の当該領域３２の相対Ｘ及びＹ座標も保存され、従ってセル３０の最暗３２Ａと最輝３２Ｂ領域の位置も容易に検索される。各セル３０の全ての領域３２の全ピクセル明暗度を計算するまでこの段階が続行する。明確な最暗領域３２Ａと最輝領域３２Ｂを決定するのに十分なコントラストがセル３０にない場合、当該セル３０の値は任意に定義された「低コントラスト」定数値ブロック２０に設定される。
【００１４】
明確な最暗領域３２Ａと明確な最輝領域３２Ｂがセル３０に見出された場合、セル３０の最暗領域３２Ａから最輝領域３２Ｂへの線３６と水辺基準線４０との間に形成された角度が計算される。この角度はセル３０ブロック２２の明暗度角度と呼ばれる。角度計算は、ブロック１８により表される段階で各セル３０に見出された最小明暗度領域３２Ａと最大明暗度領域３２ＢのＸ及びＹ座標を使用する。水平基準線４０は最小明暗度領域３２Ａを通過する。明暗度角度は、基準線４０から開始して最小明暗度領域３２Ａから最大明暗度領域３２Ｂへ反時計回り方向に移動することにより計算することが望ましい。角度は０から３５９までの範囲の整数として表現されることが望ましいが、計測単位はこの代わりに、整数でコード化されたまたは浮動小数点数として表現されたラディアン値も可能である。
【００１５】
本発明の方法は元のソース画像の特定のコンピュータ・ファイル形式に依存しない。本方法はツルーカラー画像（１６７０万色、２４ビット色深度）と共に、画像のピクセルの相対明暗度（輝度）が決定可能である限り、他の全ての色深度も解析可能である。同様に、本方法は、望ましい実施例ではその色ではなく画像のピクセルの明暗度を主に問題にしているため、カラー画像と白黒画像の両方を処理可能である。本方法はマイクロソフト（Ｒ）・ウィンドウズ（Ｒ）を使用したパーソナルコンピュータで実行されることが望ましいが、その他の計算装置やオペレーティングシステムを使用してもよい。
【００１６】
上述したように、本発明の方法は正方形ビットマップ２８中の複数個のセルの各々に対して明暗度角度を計算するか、または「低コントラスト」定数を割当てる。これらの明暗度角度値が、本発明が画像の比較用に使用する重要なセル表現データであるが、各セルからの最小及び最大領域明暗度和も明暗度角度に加えて記憶し使用してもよい。画像比較及び検索システムでその他の画像データも収集し、その他の値も計算し、その他の処理段階を実行してもよい。
【００１７】
視覚的に同様なディジタル画像に対して、本発明の方法は画像間の対応するセルに対して同様の似た明暗度角度値を計算することが示されている。画像が画像エディタにより変更され（例えば、全体の赤色バランスを増加する）、データ圧縮の各種レベルで保存され（従って各種サイズのディジタル画像ファイルを生成）、または異なる画像寸法に再形成されたとしてもこれは正しい。本方法はディジタル画像の比較過程を自動化し、画像データベースから同様の似た画像を検索することを可能とする。
【００１８】
図３Ａから３Ｃは、ソース画像の異なる３つの版に本発明を適用することにより発生された３つの正方形ビットマップ画像２８を図示する。図３Ａに示した、ビットマップ画像２８Ｂは元の３１６、０４７バイトｊｐｅｇ（．ｊｐｇ）ソース画像から得られる。図３Ｂは、図３Ａのソース画像と、ファイルサイズと画像寸法の両方が小さい、圧縮版である６７、２１０バイトｊｐｅｇソース画像から得られる。図３Ｃは、図３Ａのソース画像の他の版である２、８５０、９５４バイト・ビットマップ画像（．ｊｐｇではなく．ｂｍｐファイル）から得られる。画像寸法を増大し、テキストを追加し、ファイル型式を変更し、コントラストを減少し、赤色バランスを増加することを含む、各種の変更を加えて図３Ｃのソース画像を作成している。
【００１９】
図３Ａ、３Ｂ、３Ｃの３つの異なるビットマップ画像２８Ｂ、２８Ｃ、２８Ｄの対応するセルの比較から、対応するセルのセル表現データは大体同一であるかまたは同様であることが分かる。様々な技術を使用して整合画像を検出し、ターゲット画像と候補画像の集合との間で同様性の程度を決定する。例えば、角度範囲を設定して整合セルを識別可能である（例えば、ターゲット画像の各セルの明暗度角度、プラスマイナス１０度）。次いで候補画像の対応するセルの明暗度角度が指定した角度範囲内である場合、２つのセル３０は整合セルであるものと見なす。整合画像を指示するために、整合しなければならないセル数の最小閾値を指定してもよい（例えば、２５の内の２１整合セルが必要）。以下に記述する同様の画像を見出す別の技術は、ターゲット画像と各候補画像の対応するセル間の相違を加算することにより各画像の「同様性スコア」を計算する段階を含む。セル表現データを解析することにより同様の画像を識別するその他の技術も使用してもよい。セル表現データのデータベースは探索を実行する度に発生されてもよいが、画像ライブラリ自体を作成する時にデータベースを作成し、画像ライブラリから画像を追加または削除した時にセル表現データベースを更新することが望ましい。
【００２０】
画像を比較する時、画像のある部分に焦点を当てることも有用である。例えば、多くの写真プロセッサは顧客の注文で全寸法の画像の小さな「サムネール(thumbnail:親指の爪)」画像のアレイから構成されるインデックス画像を提供する。サムネール画像の一つをターゲット画像として選択することにより、ユーザーはインデックス画像の選択部分と同様な画像を画像ライブラリから検索できる。検索用にターゲット画像を選択することは、ソース画像に他の型式のトリミングを適用し、これによりビットマップ画像２８の定義をソース画像の丁度選択した部分に限定することにより達成される。さらに、セル表現データ値の相違を同等に扱うのではなく、比較過程がターゲット画像と各候補画像間のある相違の重要性を増減するよう、ビットマップ画像２８のセル表現データ３８を重み付けしてもよい。
【００２１】
図４を参照して、ターゲットと候補画像の同様性を計算する１つの処理過程を説明する。図２と関連して説明したように得られたセル表現データ３８を使用して比較過程が実行される。この処理では、同様画像検索ブロック４０を実行するのに必要な時間とメモリを削減するため、画像の明暗度角度を他のより小さなスケールに置き換えるのが有用である。本発明の方法の１つの例示実施例では、０から３５９の範囲の元の明暗度角度を４のモジュラスを使用して置き換えて、０から８９の明暗度角度インデックス範囲の値に縮める。さらに、「低コントラスト」値を９０の明暗度角度インデックス値に置き換える。この置き換え段階は必ずしも必要な段階ではなく、必要ならば除いてもよいことに注意されたい。
【００２２】
ユーザーの画像データベースは、ソース画像の各セルの明暗度角度値に従って構成されるのが望ましく、さらには、上述した置換明暗度角度インデックスに従って構成されるのが望ましい。本発明のこの特定の例では、９１の角度インデックス分類５０が、０から９０の各明暗度角度インデックスに対して１つづつデータベースに保持される（図５参照）。各角度インデックス分類５０は１つ以上の２次元アレイ５２を含む。最大で、ソース画像が分割される各セル寸法に対して1つのこれらのアレイがあってもよいが、より少ないアレイを使用してもよい。アレイ５２は画像セル格子と同様な方法で指標付けされ、従って、例えば、あるセル寸法のアレイの位置１、１は関係するセル格子の上左隅に対応する。画像データベースを構成するこの段階は本発明の方法を実装する際に有用であるが、画像を比較する度に全セル表現データのデータベースをアクセスし検索してもよいという点でオプションであることを理解すべきである。
【００２３】
各アレイ５２は、アレイ５２と対応するセル格子中のそのセル表現データから同じ与えられた明暗度角度インデックスを計算したデータベース中の全てのソース画像を識別する。例えば、図５を参照すると、角度インデックス分類０のアレイ位置（１、１）は、ビットマップ画像２８格子のセル（１、１）に０の明暗度角度インデックスを有するデータベース中の各画像を識別する。図５の例では、画像ライブラリ中の画像の中で、ソース画像ｉｍｇ３、ｉｍｇ５及びｉｍｇ８がセル（１、１）の明暗度角度インデックス０を有する。認められるように、このようなデータ構造は、与えられたターゲット画像のそれと同一または同様な明暗度角度インデックスを有する少なくとも1つのセルを含む候補画像を識別するよう迅速に検索できる。
【００２４】
本発明の方法を効率的に実装するため、同様な画像を探索する時に全画像ライブラリを走査することを避けるのが望ましい。しかしながら、同時に、同様な画像探索を実行する時に、多分同様な画像の脱落を避けることもきわめて重要である。従って、セル表現データのデータベースを探索する1つの方法の第１段階は、現在のターゲット画像と少なくともある程度の同様性を有する候補画像の識別を含む。この段階は、ターゲット画像と少なくとも1点の同様性を有するデータベース中の全ての画像を候補画像として選択する。この検査に合格した全ての画像は、ターゲット画像中の対応するセル３０のセル表現データ３８と同様であるか、または指定した偏差内であるセル表現データ３８を有するセル３０を有している。
【００２５】
上記した探索アルゴリズムを使用して、セル表現データベースを走査し、現在のターゲット画像の候補画像のリストを作成する。この段階は図４の４４に示している。この比較的制限のゆるいベンチマーク作業に合格した候補画像の各々に対して、ターゲット及び候補画像を分割した全てのセル寸法に渡って完全なセル対セル比較を実行する（図４の段階４６）。個々のセル同様性を加算すると、各候補画像の全体画像同様性スコアを作成する。候補画像は次いでその同様性スコアによりソートされてどの画像がターゲット画像と一番似ているかを示す。通常、ターゲット画像自体が第１の同様画像としてリストされ、これに基本の同様性スコアが割当てられ、これに対して全ての候補画像のスコアが比較される。望ましい実施例では、完全な同様性は任意に零に初期化され、従ってこの同様性スコアが各探索の開始時に各ターゲット画像に割当てられる。この例では、ターゲット画像と同一ではない各候補画像の同様性スコアは零より大きい。この例では、同様性スコアが高くなればなるほど、ターゲットと候補画像間の相違が大きくなる。この過程を高速化する1つの方法は、同様性スコアの計算に上限を設定することである。画像が上限を越えた時、可能な同様画像としてのその画像への考慮は停止する。
【００２６】
ターゲット画像の対応するセルに対する候補画像の各セルの同様性は、対応するセル明暗度角度間のコサイン差とサイン差を決定することにより計算される。望ましい実装では、コサイン及びサイン差が次いで２乗され、互いに加算され、任意のスケーリング因子を乗算される。このスケールされたセル同様性は次いで、対応する候補画像セルと比較したターゲット画像セルの相対輝度とコントラスト間の差異を考慮するためオプションとして調節される。言い換えると、明暗度角度差のみにより計算された個々のセル同様性は、各セルの相対輝度とコントラストに関してスケールされる、または重み付けされる。この最後の相対輝度とコントラストを基にしたセル同様性の調整操作は除いてもよいことに注意されたい。
【００２７】
本発明を望ましい実施例を参照して記述してきたが、当業者は、本発明の要旨と範囲から逸脱することなく形式と詳細に変更を加えうることを認める。
【図面の簡単な説明】
【００２８】
【図１】本発明により正方形ビットマップに変換され、次いでセルに分割されたディジタル画像で、最小及び最大明暗度領域を強調してある。
【図２】本発明によりディジタル画像の表現を発生する望ましい方法を図示する流れ図。
【図３Ａ】ソース画像の第１版に本発明を適用することにより発生されたビットマップ画像を図示する。
【図３Ｂ】ソース画像の第２版に本発明を適用することにより発生されたビットマップ画像を図示する。
【図３Ｃ】ソース画像の第３版に本発明を適用することにより発生されたビットマップ画像を図示する。
【図４】ターゲット及び候補画像の表現を比較する方法を図示する流れ図。
【図５】画像データベースの１実施例の構成構造を図示する概略線図。
【図２】
2004522228.tif 000003
【図４】
2004522228.tif 000004
【国際公開パンフレット】
2004522228.tif 000005
2004522228.tif 000006
2004522228.tif 000007
2004522228.tif 000008
2004522228.tif 000009
2004522228.tif 000010
2004522228.tif 000011
2004522228.tif 000012
2004522228.tif 000013
2004522228.tif 000014
2004522228.tif 000015
2004522228.tif 000016
2004522228.tif 000017
2004522228.tif 000018
2004522228.tif 000019
2004522228.tif 000020
2004522228.tif 000021
2004522228.tif 000022
2004522228.tif 000023
2004522228.tif 000024
2004522228.tif 000025
2004522228.tif 000026
2004522228.tif 000027
2004522228.tif 000028
2004522228.tif 000029
2004522228.tif 000030
2004522228.tif 000031
2004522228.tif 000032
2004522228.tif 000033
2004522228.tif 000034
【国際公開パンフレット（コレクトバージョン）】
2004522228.tif 000035
2004522228.tif 000036
【国際調査報告】
2004522228.tif 000037