(57)【要約】  画像に対応する信号を処理することによって画像の表現を導出する方法及び装置が記載される。本方法は、画像のトレース変換等の２次元関数（Ｔ（ｄ，θ））を導出することと、その２つの次元のうちの少なくとも一方において２次元関数（Ｔ（ｄ，θ））を（例えばサブサンプリングすることによって）分解することであって、それによって、低減された解像度のトレース変換を得る、分解することとを含む。次いで分解された２次元関数を用いて、画像の表現が導出される。
2010515991.tif 000002
【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
前記画像又は前記画像の２次元関数を処理することであって、それによって前記画像の低減された解像度における２次元関数を得る、前記画像又は前記画像の２次元関数を処理することと、
前記画像の前記低減された解像度の２次元関数を用いることであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の２次元関数を用いることと、
を含む、方法。
【請求項２】
前記画像又は前記画像の２次元関数を処理するステップは、前記画像の前記２次元関数のパラメータのうち少なくとも１つのパラメータの所定の区間にわたって、前記画像の値をサブサンプリングすることを含む、請求項１に記載の方法。
【請求項３】
前記サブサンプリングすることは、前記画像又は前記画像の関数の値に対して、前記画像又は前記画像の２次元関数のパラメータのうち少なくとも１つのパラメータの所定の区間にわたって、統計的計算を行うこと、好ましくは総和又は積分を行うことを含む、請求項２に記載の方法。
【請求項４】
前記処理するステップは、前記画像内の線のセットを用いて前記画像を処理することを含む、請求項１、２又は３に記載の方法。
【請求項５】
前記線のセットは、
前記画像の前記２次元関数の第１のパラメータの区間の１つによって規定される帯、及び
前記画像の前記２次元関数の第２のパラメータの区間の１つによって規定される２つの錐
の一方又は複数に対応する、請求項４に記載の方法。
【請求項６】
前記処理することは、前記線のセットに汎関数を適用することであって、それによって、前記画像の前記低減された解像度の２次元関数を導出する、前記線のセットに汎関数を適用することを含む、請求項４又は５に記載の方法。
【請求項７】
前記処理するステップは、前記画像の前記２次元関数の第１の次元の所定の区間にわたって前記２次元関数の値をサブサンプリングすることによって、前記画像の２次元関数を処理することを含み、それによって、前記第１の次元における前記画像の前記２次元関数の前記解像度を低減する、請求項１、２又は３に記載の方法。
【請求項８】
前記処理するステップは、前記画像の前記２次元関数の第２の次元における所定の区間にわたって前記２次元関数の値をサブサンプリングすることによって、前記画像の２次元関数を処理することを含み、それによって、前記第２の次元における前記画像の前記２次元関数の前記解像度を低減する、請求項１、２、３又は７に記載の方法。
【請求項９】
前記画像の前記２次元関数は、前記画像のすべての線に対して汎関数を適用することによって導出される前記画像のトレース変換を含み、
前記２次元関数は、距離パラメータ及び角度パラメータを有するトレース領域における前記画像の値を規定する、請求項７又は８に記載の方法。
【請求項１０】
前記画像の前記低減された解像度の２次元関数を用いる前記ステップであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の２次元関数を用いる前記ステップは、前記画像の１次元関数を導出することを含む、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記方法は、前記画像のさらなる関数を導出することをさらに含み、
前記画像の平行移動、拡大縮小又は回転させたバージョンの前記さらなる関数は、前記画像の前記さらなる関数の平行移動又は拡大縮小させたバージョンである、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
前記１次元関数又は前記さらなる関数は、サーカス関数であるか、又はサーカス関数から導出される関数である、請求項１０又は１１に記載の方法。
【請求項１３】
前記画像の前記低減された解像度の２次元関数を用いる前記ステップであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の２次元関数を用いる前記ステップは、前記１次元関数又は前記さらなる関数の周波数表現の複数の周波数成分を用いることであって、それによって前記画像の表現を導出する、前記１次元関数又は前記さらなる関数の周波数表現の複数の周波数成分を用いることを含む、請求項１０、１１又は１２に記載の方法。
【請求項１４】
前記周波数成分はフーリエ変換又はハール変換を用いて求められる、請求項１３に記載の方法。
【請求項１５】
前記画像の前記表現は、
複数の周波数係数の前記振幅又は前記振幅の対数を計算するステップと、
各係数の前記振幅又は前記振幅の対数と、前記係数の次の係数の前記振幅又は前記振幅の対数との間の差分を求めるステップと、
を用いて導出される、請求項１３又は１４に記載の方法。
【請求項１６】
前記方法は、求められた差分のそれぞれに閾値を適用することであって、それによって一連のバイナリ値を導出する、求められた差分のそれぞれに閾値を適用することをさらに含み、
前記閾値を適用することは、前記差分が０未満である場合には０のバイナリ値を提供し、前記差分が０以上である場合には１のバイナリ値を提供する、請求項１５に記載の方法。
【請求項１７】
前記画像表現は、前記複数の周波数成分の前記振幅又は前記振幅の対数によって規定される前記バイナリ値を含む、請求項１６に記載の方法。
【請求項１８】
前記方法は、前記区間についてある範囲内の異なる幅にわたって前記処理するステップを行うと共に前記複数の表現を組み合わせて複数解像度の表現を生成することによって、前記画像の複数の表現を導出することを含む、請求項１〜１７のいずれか一項に記載の方法。
【請求項１９】
前記異なる区間幅は、互いに少なくとも２倍異なる、請求項１８に記載の方法。
【請求項２０】
画像を識別する方法であって、
請求項１〜１９のいずれか一項に記載の方法を用いて前記画像の表現を導出することと、
前記表現と前記画像とを関連付けることと、
を含む、方法。
【請求項２１】
画像を比較する方法であって、請求項１〜２０のいずれか一項に記載の方法を用いて導出される各画像の表現を比較することを含む、方法。
【請求項２２】
前記比較することはハミング距離を求めることを含む、請求項２１に記載の方法。
【請求項２３】
表現の比較に基づいて画像を選択することを含む、請求項２１又は２２に記載の方法。
【請求項２４】
請求項１〜１９のいずれか一項に記載の方法を用いて導出される画像の表現の使用であって、送信、受信又は処理を含む使用。
【請求項２５】
請求項１〜２３のいずれか一項に記載の方法を実行する装置。
【請求項２６】
実行されると請求項１〜２３のいずれか一項に記載の方法を実施する命令を含む、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の背景］
［発明の分野］
本発明は、画像を表現する方法及び装置に関し、さらに、（例えば検索又は検証の目的のために）画像を比較又は照合する方法及び装置に関する。
【０００２】
［背景技術の記載］
本発明は、同時係属中の欧州特許出願ＥＰ０６２５５２３９．３に記載されている画像識別技法に対する改良に関する。欧州特許出願ＥＰ０６２５５２３９．３の内容は参照により本明細書に援用される。欧州特許出願ＥＰ０６２５５２３９．３の発明及び実施の形態の詳細は、本発明及び本実施の形態にも同様に適用される。
【０００３】
画像から短いバイナリ記述子を抽出する（図２参照）、欧州特許出願ＥＰ０６２５５２３９．３に記載されている画像識別方法及び装置は、従来技術の多くの欠点に対処しており、特に、
・特徴抽出及び照合の双方について計算複雑度が低減されていること、
・画像記述子のサイズが低減されていること、
・さまざまな画像変更に対するロバスト性が高められていること、並びに
・広範な変更に対して約８０％までの検出率を維持しながら誤報率が１ｐｐｍレベルに低減されていること、
を特徴とする。
【０００４】
しかしながら、実際の用途においては検出率がより高いことが望ましい。特に、平均検出率を９８％超にまで高めると共に、ノイズ及びヒストグラム等化の変更に対するロバスト性も大幅に向上させることが望ましい。
【０００５】
［発明の概要］
第１の態様によれば、本発明は、添付の特許請求の範囲の請求項１に定義されている、画像の表現を導出する方法を提供する。
【０００６】
本発明のさらなる態様は、本発明の第１の態様による方法を用いて導出される画像の表現の使用と、本発明の第１の態様による方法を実施する装置と、命令（実行されると本発明の第１の態様による方法を実施するもの）を含むコンピュータ可読記憶媒体とを含む。
【０００７】
本発明の実施の形態の好ましい特徴及び任意選択の特徴は従属請求項に記載されている。
【０００８】
本発明は、画像のトレース変換（又は画像の２次元関数であって等価なもの）から視覚的な識別特徴を抽出する新規の方法に関する。本方法は、識別子を抽出する前に、例えばフーリエ変換の振幅によって画像のトレース変換に対して領域ベースの処理を行うことによって、画像の複数解像度の表現を作成するのに用いることができる。
【０００９】
本出願において、用語「汎関数」は、その通常の数学的意味を有する。特に、汎関数とは、ベクトル空間Ｖ上の（通常は関数の）実数値関数である。トレース変換の場合、汎関数は画像内の線に適用される。
【００１０】
同時係属中の欧州特許出願ＥＰ０６２５５２３９．３に記載されている方法では、トレース変換は、画像を直線でトレースすることによって計算され、該直線に沿って、画像輝度の特定の汎関数Ｔ又は色関数が計算される。異なる複数の汎関数Ｔが用いられて単一の入力画像から異なる複数のトレース変換が生成される。２Ｄ平面において線は２つのパラメータ、すなわち距離ｄ及び角度θによって特徴付けられるため、画像のトレース変換は各トレース線のパラメータの２Ｄ関数である。次に、トレース変換の列に沿ってダイアメトリカル汎関数(diametrical functional) Ｐを適用することによって「サーカス関数（circus function）」が計算される。サーカス関数の周波数表現（例えばフーリエ変換）が得られ、周波数振幅成分に関して関数が定義され、その符号がバイナリ記述子として取られる。
【００１１】
本発明の実施の形態による方法は、同様の技法を用いて画像の表現を導出することができる。しかしながら、画像の表現（例えばバイナリ記述子）を導出するさらなるステップを行う前に、低減された解像度のトレース変換等の、画像の低減された解像度の関数が導出される。解像度の低減は、処理されるデータ量を低減しながら画像に特有の必須要素（すなわちその視覚的な識別特徴）を維持するべきである。通常、導出される画像の低減された解像度の関数は、以下の記載から明らかになるように、演算によって、画像の選択される部分又はサンプリングされる部分の表現値を組み込む。
【００１２】
本発明の一実施の形態によれば、画像の低減された解像度の関数は、線のセット（これらの線のパラメータは、所定の区間Δｄ及び／又はΔθのものである）を用いて画像をトレースすることと、（画像を横切るすべての線の代わりに）線のセットのすべてを用いてトレース変換（又は等価物）を導出することとによって導出される。線は、画像領域における帯（図１０に示すもの）及び／又は２つの錐（図１１に示すもの）に対応し得る。したがって、より詳細に後述するように、画像の低減された解像度の（すなわちより粗い解像度の）トレース変換が導出される。
【００１３】
本発明の別の実施の形態によれば、最初に、従来のように画像を横切るすべての線をトレースすることによってトレース変換（又は等価物）が導出される。次いで、角度パラメータθの異なる値における複数の帯を用いて画像のトレース変換がトレースされ、（図１２に示すような）距離パラメータｄの複数の区間にわたって解像度の低減が行われ、且つ／又は、距離パラメータｄの異なる値における複数の帯を用いてトレース変換がトレースされ、トレース領域において（図１３に示すような）角度パラメータθの複数の区間にわたって解像度の低減が行われ、より詳細に後述するように画像の低減された解像度の２次元関数が導出される。
【００１４】
有利には、以下でさらに詳細に説明するように、トレース変換領域内の帯及び／又は錐に沿ってトレース変換値を暗黙的に計算することによって、本発明のこの実施の形態の方法を非常に効率的に実施することができる。
【００１５】
同時係属中の欧州特許出願ＥＰ０６２５５２３９．３に開示されている方法のように、本発明の一実施の形態による方法は、異なる複数の汎関数を用いることによって得られる識別子「族」の選択部分を組み合わせる。さらに、いくつかの実施形態では、帯及び／又は２つの錐を用いて得られる識別子は組み合されて単一の記述子になる。さらに、いくつかの実施形態において、幅が異なる複数の帯及び／又は開口角が異なる複数の錐が用いられて、複数解像度の表現が得られる。
【００１６】
添付図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【００１７】
【図１ａ】画像を示す。
【図１ｂ】図１ａの画像を縮小した変形を示す。
【図１ｃ】図１ａの画像を回転させた変形を示す。
【図１ｄ】図１ａの画像をぼかした変形を示す。
【図２】画像と、従来技術によるその画像のビットストリング表現とを示す。
【図３】本発明の一実施形態の方法のステップを示す図である。
【図４】本発明の一実施形態の別の方法のステップを示す図である。
【図５】トレース変換の線パラメータ化を示す図である。
【図６】（ａ）〜（ｃ）は、画像の異なるバージョンから導出される関数を示す。
【図７】本発明の一実施形態による装置のブロック図である。
【図８】複数のトレース変換を用いる一実施形態を示すブロック図である。
【図９】図８の実施形態によって作成されるビットストリームを示す図である。
【図１０】トレース変換のｄパラメータを分解するときの原画像内の区間帯を示す。
【図１１】トレース変換のθパラメータを分解するときの原画像における２つの錐を示す。
【図１２】ｄパラメータにおけるトレース変換の分解を示す。
【図１３】θパラメータにおけるトレース変換の分解を示す。
【発明を実施するための形態】
【００１８】
［実施形態の詳細な説明］
画像の表現（具体的には画像識別子）を導出すると共に、このような表現／識別子を（例えば、１つ又は複数の画像の識別、照合又は検証の目的で）用いるさまざまな実施形態を以下に記載する。本発明は画像の識別に特に有用であるが、これには限定されない。記載される実施形態では、「画像識別子」（ときに「識別子」と単純化される）は画像の表現の一例であり、この用語は画像の表現、すなわち記述子を指すために用いられるに過ぎない。
【００１９】
当業者であれば、本発明の一実施形態による画像識別装置及び方法の具体的な設計と、画像識別に用いる画像識別子の導出とは、設計要件によって決定されることを理解しよう。このような設計要件は、画像識別子がロバストであるべき画像変更のタイプ、識別子のサイズ、抽出及び照合の複雑度、目標誤報率等に関連する。
【００２０】
以下の実施形態は、画像に対する以下の変更にロバストな識別子をもたらす一般的設計を示す（これは網羅的なリストではない）。
・色数削減
・ぼかし
・明るさの変更
・反転（左右及び上下）
・グレースケール変換
・ヒストグラム等化
・ＪＰＥＧ圧縮
・ノイズ
・回転
・拡大縮小
【００２１】
この一般的設計は通常、広範な画像に対して百万分の１（ｐｐｍ）という非常に低い誤報率を達成することができることが分かっている。
【００２２】
図１は、画像及びその画像を変更した変形の一例を示す。より具体的には、図１ａは原画像であり、図１ｂは図１ａの画像を縮小したバージョンであり、図１ｃは図１ａの画像を回転させたバージョンであり、図１ｄは図１ａの画像をぼかしたバージョンである。
【００２３】
本発明の一実施形態は、画像に対応する信号を処理することによって、画像の表現、より具体的には画像識別子を導出する。
【００２４】
図３は、本発明の一実施形態による画像識別子を導出する方法の各ステップ、すなわち識別子抽出工程を示す。
【００２５】
抽出の初期段階において画像を前処理する。これは、画像をサイズ変更し（ステップ１１０）、任意選択でフィルタリングする（ステップ１２０）ことによって行われる。サイズ変更ステップ１１０は、画像を処理前に正規化するために用いられる。ステップ１２０は、画像に対して行われた何らかの処理によって生じるエイリアシング等の効果を除去するためのフィルタリングを含み得、及び／又は、原画像全体を用いるのではなく領域を選択することを含み得る。本方法の好適な一実施形態では、画像の中央から円形領域がさらなる処理のために抽出される。
【００２６】
ステップ１３０において、トレース変換
【００２７】
【数１】
2010515991.tif 000003
【００２８】
を行う。トレース変換は、全ての可能な線を画像に射影し、これらの線に１つ又は複数の汎関数を適用する。上述のように、汎関数とは、ベクトル空間Ｖ上の実数値関数であり、、通常は関数の実数値関数である。トレース変換の場合、画像中の複数の線に汎関数が適用される。図５に示されるように、線は２つのパラメータｄ及びθによってパラメータ化される。後述のように、ステップ１４０においてトレース変換の結果を分解してその解像度を低減することができる。ステップ１５０において、トレース変換の各列にさらなる汎関数を適用して、実数値ベクトルを得ることができる。この第２の汎関数はダイアメトリカル汎関数(diametrical functional)として知られ、結果として得られるベクトルはサーカス関数として知られる。第３の汎関数であるサーカス汎関数をサーカス関数に適用して、単一の数を得ることができる。この結果の特性は、これら３つの異なる汎関数（トレース汎関数、ダイアメトリカル汎関数及びサーカス汎関数）を適切に選択することによって制御することができる。画像及び対応するトレース変換の例を含むトレース変換の全詳細は、例えば、以下の参考文献［１］：参照により本明細書に援用されるAlexander Kadyrov及びMaria Petrou著「The Trace Transform and its Applications」（IEEE Trans. PAMI, 23(8), ２００１年８月、 pp 811-828）に見ることができる。この実施形態の方法では、１Ｄサーカス関数を得るために、最初の２つのステップのみをトレース変換において行う。
【００２９】
本方法の１つの特定の例において、画像のトレース変換
【００３０】
【数２】
2010515991.tif 000004
【００３１】
はトレース汎関数Ｔ
【００３２】
【数３】
2010515991.tif 000005
【００３３】
を用いて抽出され、サーカス関数はダイアメトリカル汎関数Ｐ
【００３４】
【数４】
2010515991.tif 000006
【００３５】
を適用することによって得られる。
【００３６】
サーカス関数が様々な画像処理操作によって受ける影響の例を図６に見ることができる。図６は、画像の様々な変形に対応するサーカス関数を示す。図６（ａ）は原画像に対応し、図６（ｂ）はその画像を回転させたバージョンに対応し、図６（ｃ）はその画像をぼかしたバージョンに対応する。回転は関数をシフトさせる（と共にスケール変化を生じる）ことが分かる。
【００３７】
上で挙げた大部分の画像の変更操作に関して、汎関数Ｔ、Ｐを適切に選択すれば、画像ａのサーカス関数ｆ（ａ）は、変更された画像ａ’のサーカス関数ｆ（ａ’）がシフト又は（振幅が）拡大縮小された変形に過ぎないことを示すことができる（以下の参考文献［１］の第３章を参照）。
【００３８】
【数５】
2010515991.tif 000007
【００３９】
同時係属中の欧州特許出願ＥＰ０６２５５２３９．３に記載されている方法によれば、サーカス関数の周波数表現の周波数成分を用いて画像識別子を導出することができる。画像記述子を導出する他の技法が可能であると共に、本発明と併せて用いることができることは理解されよう。一例では、画像識別子は、サーカス関数のフーリエ変換（又は同様にハール変換）から導出することができる。
【００４０】
したがって、式（３）のフーリエ変換を行うことによって、次式が与えられる。
【００４１】
【数６】
2010515991.tif 000008
【００４２】
次に、式（６）の振幅を取ると次式が得られる。
【００４３】
【数７】
2010515991.tif 000009
【００４４】
式（７）から、この時点では、変更された画像と原画像とはスケーリング係数κを除いて同じであることが分かる。
【００４５】
本実施形態によれば、ここで、フーリエ変換係数の複数の振幅係数について関数ｃ（ω）が定義される。この関数の１つの例示は、各係数とその隣の係数との間の差分を取ることである。
【００４６】
【数８】
2010515991.tif 000010
【００４７】
結果として得られるベクトル（式８）に、以下のように閾値を適用することによってバイナリストリングを抽出することができる。（すべてのωについて）
【００４８】
【数９】
2010515991.tif 000011
【００４９】
次に、これらの値Ｂ＝｛ｂ0，．．．，ｂn｝から画像識別子が構築される。
【００５０】
２つの異なる識別子Ｂ1及びＢ2（いずれも長さＮ）の間で識別子の照合を行うために、正規化ハミング距離を取る。
【００５１】
【数１０】
2010515991.tif 000012
【００５２】
ここで、
【００５３】
【数１１】
2010515991.tif 000013
【００５４】
は排他的ＯＲ（ＸＯＲ）演算子である。識別子又は表現の他の比較方法も用いることができる。
【００５５】
識別子中の特定ビットの選択によって性能をさらに高めることができる。より低い周波数に対応するビットは一般にロバスト性がより高く、より高い周波数に対応するビットは識別性がより高い。本発明の特定の一実施形態では最初のビットを無視し、識別子は続く６４ビットから成る。
【００５６】
本発明の一実施形態によれば、トレース変換（又は等価物）からもたらされる、画像の２次元関数を分解するステップ１４０は、その解像度を低減することを含む。解像度の低減は、その２つの次元ｄ若しくはθのうちのいずれか又は双方の次元において処理することによって達成することができる。
【００５７】
したがって、図１２のように、ｄパラメータをサブサンプリングすることによって、例えば（θの値に対応する）列に沿ってｄの複数の区間にわたって総和をとるか又は積分することによって、「トレース領域」における距離次元において解像度を低減することができる。これは、図１０に示されるように、トレース変換中に幅Δｄの帯を画像に（すなわち画像領域内に）射影することに対応する。距離パラメータｄの複数の区間にわたってサブサンプリングする（すなわちトレース変換の解像度を低減する）任意の技法を用いることができることは理解されよう。したがって、データの本質を維持しながらデータの量を低減する任意の統計的計算を用いることができ、総和をとること及び積分はその例に過ぎない。
【００５８】
代替的に又は付加的に、図１３のように、θパラメータをサブサンプリングすることによって、例えば（ｄの値に対応する）行に沿ってθの複数の区間にわたって総和をとること又は積分することによって、「トレース領域」における角度次元において解像度を低減することができる。これは図１１に示されるように、トレース変換の間に開口角Δθを有する２つの錐を画像に（すなわち画像領域内に）射影することとほぼ等価である。角度パラメータθの複数の区間にわたってサブサンプリングする（すなわちトレース変換の解像度を低減する）任意の技法を用いることができることは理解されよう。したがって、データの本質を維持しながらデータの量を低減する任意の統計的計算を用いることができ、総和をとること及び積分はその例に過ぎない。
【００５９】
本発明の別の実施形態によれば、分解するステップ１４０は、「画像領域」において行うことができ、すなわち、ステップ１２０の後に且つ通常図３のステップ１３０と組み合わせて行うことができる。一例では、ステップ１４０は、画像自体の中の線のセットを結合又は分解すると共に、これらの線に対してトレース変換（又は他の演算）を行って画像識別子を導出する。例えば、画像の複数の線をステップ１３０において共に効率的に処理することができるように、１画素幅の画像の線を結合することができる。線のセットは例えば、図１０に示されるような平行線及び／又は図１１に示されるような２つの錐によって規定される線とすることができる。結合される線の数は上述の区間に対応する。したがって、この実施形態では、トレース変換は、従来のトレース変換のように画像を横切るすべての線をトレースする代わりに、画像を横切る線の選択されたセットをトレースするように有効に変更される。
【００６０】
当業者には理解されるように、画像領域において分解する他の技法が可能である。
【００６１】
上記の方法を行う本発明の一実施形態による装置の一例を図７に示す。具体的には、画像記憶モジュール２１０によって画像２００が受け取られ、画像データベース２３０に記憶される。さらに、識別子抽出及び記憶モジュール２２０が、本発明の方法に従って、受け取った画像毎に画像識別子を抽出し、それらの画像識別子を識別子データベース２４０に、（任意選択で、画像のコンテンツに関連する他の情報と共に）適宜記憶する。
【００６２】
図７はさらに、上記の方法を用いて抽出された画像識別子を用いる画像検索エンジンを具現する装置を示す。画像の検証又は照合が、問い合わせ画像２５０の受け取りに応答して画像検索エンジンによって行われ得る。本発明の方法に従って、問い合わせ画像２５０の画像識別子が識別子抽出モジュール２６０において抽出される。識別子照合モジュール２７０が問い合わせ画像２５０の画像識別子を、識別子データベース２４０に記憶されている画像識別子と比較する。画像検索モジュール２８０が、画像データベース２３０から一致画像２９０を取り出す。この一致画像２９０は、以下で詳述するように、問い合わせ画像識別子と一致する画像識別子を有する。
【００６３】
図４は、フーリエ変換係数に対するバイナリ関数を定義する代替的な方法を示す。特に、フーリエ変換係数を得た（ステップ１７１）後、複数のフーリエ変換係数の振幅の対数を得る（ステップ１７２及び１７３）。以降の係数の差分を上記の式（８）と同様に計算し（ステップ１７４）、その後、この差分の符号を取り、この符号によってバイナリ値を割り当てる（ステップ１７５）。次に、このバイナリ値を用いてバイナリ識別子を形成する。画像の関数の他の周波数表現（ハール変換を含む）の周波数係数にこの技法を用いることができることは理解されよう。
【００６４】
上述した基本識別子は、図８及び図９に示すように、低減された解像度のトレース変換を複数用いてそれぞれの識別子を導出することと、別々の識別子からのビットを組み合わせることとによって改良することができる。低減された解像度のトレース変換の別々のものからのバイナリストリング３６１及び３６２を組み合わせる具体的な方法は、それらを連結して識別子３６３を得ることである。
【００６５】
このようにして、上記の式（１）のトレース汎関数Ｔを、上記の式（２）によって与えられるダイアメトリカル汎関数Ｐと共に用いて１つのバイナリストリングを得た後、トレース汎関数（１）をダイアメトリカル汎関数（１１）
【００６６】
【数１２】
2010515991.tif 000014
【００６７】
と共に用いて第２のストリングを得ることによって良好な結果を得ることができる。各バイナリストリングの最初のビットはスキップし、両方のストリングからの次の６４ビットを連結して１２８ビットの識別子を得る。
【００６８】
本発明によれば、トレース変換における複数解像度の表現を用いることによって大幅な性能改良を得ることができる。特に、１つ又は２つの次元において分解を行うことができる。次いで上記のように、ダイアメトリカル汎関数を適用してバイナリストリングを抽出することができる。通常の結果は、この分解を用いることによって百万分の１の誤報率（false error rate）における検出率が約８０％から９８％に高められることを示す。
【００６９】
この複数解像度のトレース変換は、上述のように、その２つの次元ｄ若しくはθのうちのいずれか又は双方の次元において元のトレース変換をサブサンプリングしてその解像度を低減することによって生成することができる。「トレース領域」においてｄパラメータのサブサンプリングは、例えば図１２のように列に沿って複数の区間にわたって積分することによって行われる。これは、図１０に示されるように、トレース変換中に幅Δｄの帯を画像に射影することに対応する。サブサンプリングは、例えばθパラメータにおける複数の区間にわたって、すなわち行に沿って積分することによって行うこともできる。図１３を参照されたい。これは、トレース変換中に開口角Δθを有する２つの錐にわたって積分することとほぼ同じである。図１１を参照されたい。代替的に、上述のようにこれらの演算を「画像領域」において行うことができる。
【００７０】
複数解像度分解を用いることによって、１つのトレース変換から複数の基本識別子を抽出することができる。ここで、ある範囲内の異なる区間幅にわたってサブサンプリングが行われて、複数の基本識別子から成る複数解像度の表現が生成される。理想的には、複数解像度の表現はある範囲内の区間幅を用いて導出される複数の識別子を用いる。例えば、各区間幅は他の区間幅と少なくとも２倍異なってもよい。トレース変換の出力のサイズが６００×３８４であり、したがってｄパラメータが幅８、１６、３２、６４及び１２８の帯(band)を用いて積分することによってサブサンプリングされ、同様にθパラメータが例えば幅３、６、１２、及び２４の帯を用いて積分することによってサブサンプリングされるシステムを用いることによって、良好な結果が一般的に得られた。
【００７１】
この識別子の１つの応用は、画像検索エンジンとしての応用である。ファイル名、画像、撮影者、取得日時、及び任意の他の有用な情報等の関連する情報と共に、バイナリ識別子を抽出し記憶することによって、データベースが構築される。次に、問い合わせ画像ａqが与えられると、バイナリ識別子が抽出され、データベース中の全ての識別子Ｂ0．．．ＢMと比較される。問い合わせ画像に対するハミング距離が閾値未満である全ての画像が返される。
【００７２】
［代替的な実施態様］
様々な異なるトレース汎関数及びダイアメトリカル汎関数を用いることができ、例として以下が挙げられる（網羅的でないリスト）。
【００７３】
【数１３】
2010515991.tif 000015
【００７４】
２つ又はそれ以上の識別子を組み合わせて、画像をより正確に特徴付けすることができる。この組み合わせは、複数の識別子の連結によって行われることが好ましい。
【００７５】
回転、平行移動及び拡大縮小より高次の幾何変換の場合、上述した識別子のバージョンは適切でなく、式（３）の関係は成り立たない。識別子のロバスト性は、正規化工程を用いるアフィン変換まで拡張することができる。この正規化工程の全詳細は、以下の参考文献［２］に見ることができる。サーカス関数を正規化するために２つのステップが導入され、最初のステップは、いわゆる関連サーカス(associated circus)を求めることを含み、２番目のステップは、正規化された関連サーカス関数を求めることを含む。この正規化に続き、式（３）の関係が真であることが示される。これによって、上記と同様に識別子の抽出工程を継続することができる。
【００７６】
正規化工程と共に用いられるいくつかの適切なトレース汎関数が以下の（Ｇ１）及び（Ｇ２）に与えられ、ダイアメトリカル汎関数の適切な選択が（Ｇ３）に与えられる。
【００７７】
【数１４】
2010515991.tif 000016
【００７８】
ここで、ｒ≡ｔ−ｃであり、ｃ≡ｍｅｄｉａｎ（｛ｔk｝k，｛｜ｇ（ｔk）｜｝k）である。非負の重みｗ1，ｗ2，．．．，ｗnを有する数列ｙ1，ｙ2，．．．，ｙnの加重中央値を、この数列が重みによって昇順でソートされると仮定した場合に次式が成り立つ最大インデックスｍを特定することによって定義する。
【００７９】
【数１５】
2010515991.tif 000017
【００８０】
不等式（１２）が厳密(strict)である場合、中央値はｙmとなる。しかし、不等式が等式である場合、中央値は（ｙm＋ｙm-1）／２となる。
【００８１】
識別子を連続するビットのブロックから構築する代わりに、実験によって選択を行うことができる。このやり方の一例は、ｉ）独立した画像と、ｉｉ）原画像及び変更された画像との２組のデータを用意することである。識別子の性能は、独立したデータの誤受入率と、原画像及び変更された画像の誤拒否率とを比較することによって測定することができる。関心となる点は、等価エラー率、すなわち、１×１０-6の誤受入率における誤拒否率である。最適化は、ビットが選択されていない状態で開始される。各ビットを１つずつ検査して、どのビットが（例えば等価エラー率又は何らかの類似の測度に関して）最良の性能を発揮するかを確かめることが可能である。最良の結果を与えるビットが選択されるべきである。次に、全ての残りのビットを試験して、どれが最初のビットと組み合わせた際に最良の性能を発揮するかを確かめるべきである。ここでもまた、エラー率が最低のビットが選択される。この手順は、全てのビットが選択されるまで繰り返される。このように、全体として最良の性能をもたらすビットの組み合わせを求めることができる。
【００８２】
上記で示したように、パラメータ（ｄ又はθ）の複数の区間にわたって総和をとること又は積分することによって、トレース変換における複数解像度分解を形成することができる。上記で示したように、任意の統計的技法を用いて分解又は解像度低減を達成することができ、他の可能性は、平均値、最大値、最小値等のような統計値を計算することを含む。他の汎関数をこれらの区間に適用することもできる。
【００８３】
さらに、構造を識別子に適用して検索性能を高めることもできる。例えば、２パス探索を実施し、１回目の探索に半分のビットを用い、次に所与のレベルの精度を有するビットのみを２回目の探索パスに認める。
【００８４】
リード・マラー（Reed-Muller）復号器又はウイナー・ジブ（Wyner-Ziv）復号器等の方法を用いて識別子を圧縮し、さらにサイズを縮小することができる。
【００８５】
［代替的な応用］
識別子はまた、ビデオシーケンス中のフレームをインデックス付けするために用いることもできる。新たなシーケンスが与えられると、フレームから識別子を抽出し、次に、同一のシーケンスを見つけるために検索を行うことができる。これは、著作権の検出及びシーケンスの識別のために有用であり得る。
【００８６】
複数の放送会社が同一のコンテンツ、例えば広告又は株式ニュースの映像を送信する場合が多い。放送会社間のナビゲーションのために、識別子を用いてこれらのコンテンツ間にリンクを形成することができる。
【００８７】
画像識別子は、画像を介してコンテンツを結びつける機会を提供する。ユーザがウェブページ上の特定の画像に興味がある場合、同一画像を有する他のページを見つける有効な方法はない。識別子を用いて、画像間のナビゲーション経路を提供することができる。
【００８８】
識別子を用いてブロードキャストフィード中の広告を検出することができる。これを用いて、広告主が自社のキャンペーンを追跡するための自動監視を行うことができる。
【００８９】
大規模な商用集合からパーソナルコンピュータ上の小規模なコレクションまで多くの画像データベースが存在する。データベースが厳格に制御されていない限り、通常は集合の画像に重複があり、余分な記憶領域を無駄に必要とする。識別子は、これらのデータセット中の重複画像を削除又は紐付けするツールとして用いることができる。
【００９０】
本明細書中、「画像」という用語は、画像単位（フィルタリング、解像度の変更、アップサンプリング、ダウンサンプリング等の処理の後のものを含む）を記述するために用いられるが、他の類似の用語（フレーム、フィールド、ピクチャ、又は、画像・フレーム等のサブユニット若しくは領域等）にも当てはまる。本明細書中、画像という用語は、文脈から明らかである場合を除き、画像全体又は画像の領域を意味する。同様に、画像の領域は画像全体を意味し得る。画像は、フレーム又はフィールドを含み、静止画、又はフィルムに関連し、または、ビデオ等の画像シーケンス中の画像に関連し、または、関連する画像のグループ中の画像に関連する。画像は、グレースケール画像又はカラー画像であってもよく、又は別のタイプのマルチスペクトル画像（例えば、ＩＲ、ＵＶ若しくは他の電磁波画像）であってもよく、又は音響画像であってもよく、他の画像であってもよい。
【００９１】
実施形態において、周波数表現は、フーリエ変換を用いて導出されるが、周波数表現は、ハール変換等の他の技法を用いて導出することもできる。特許請求の範囲において、フーリエ変換という単語は、ＤＦＴ及びＦＦＴ等の変形を網羅するものとする。
【００９２】
本発明は、適切な装置を用いて電気的信号を処理することによって実施されることが好ましい。
【００９３】
本発明は、例えば、適切なソフトウェア及び／又はハードウェアの変更を加えたコンピュータシステムにおいて実施することができる。例えば、本発明は、制御手段若しくは処理手段（プロセッサ若しくは制御装置等）、データ記憶手段（メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等のような画像記憶手段を含む）、データ出力手段（ディスプレイ、モニタまたはプリンタ等）、データ入力手段（キーボード等）、及び画像入力手段（スキャナ等）を有する、又はこれらの構成要素の任意の組み合わせを他の付加的な構成要素と共に有する、コンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェア及び／若しくはハードウェアの形態、又は特定用途向け装置において提供することができ、又は、チップ等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置におけるシステムの構成要素は、他の構成要素から離れた場所に、例えばインターネットを介して設けられてもよい。
【００９４】
［参考文献］
［１］Alexander Kadyrov及びMaria Petrou著「The Trace Transform and Its Applications」(IEEE Trans. PAMI, 23 (8), ２００１年８月, pp 811-828)
［２］Maria Petrou及びAlexander Kadyrov著「Affine Invariant Features from the Trace Transform」(IEEE Trans, on PAMI, 26 (1), ２００４年１月, pp 30-44)
【００９５】
当業者であれば理解するように、説明した実施形態に対して多くの変形及び変更を行うことができる。例えば、本発明を、当業者に既知の既存の技法及び関連技法を組み合わせて実施する実施形態において実施することができる。添付の特許請求の範囲に規定される本発明の範囲に入る、説明した実施形態に対するそのような変形、変更及び均等物を全て含むことが意図される。
【図１ａ】
2010515991.tif 000018
【図１ｂ】
2010515991.tif 000019
【図１ｃ】
2010515991.tif 000020
【図１ｄ】
2010515991.tif 000021
【図２】
2010515991.tif 000022
【図３】
2010515991.tif 000023
【図４】
2010515991.tif 000024
【図５】
2010515991.tif 000025
【図６】
2010515991.tif 000026
【図７】
2010515991.tif 000027
【図８】
2010515991.tif 000028
【図９】
2010515991.tif 000029
【図１０】
2010515991.tif 000030
【図１１】
2010515991.tif 000031
【図１２】
2010515991.tif 000032
【図１３】
2010515991.tif 000033
【国際調査報告】
2010515991.tif 000034
2010515991.tif 000035
2010515991.tif 000036