画像認識のための画像記述子
画像に対応する信号を処理することによって画像の表現を導出する方法であって、当該方法は、画像の関数を導出することであって、画像を平行移動、拡大縮小、又は回転させたものの関数は、画像の関数を平行移動又は拡大縮小させたものである、画像の関数を導出することと、画像の表現を導出するために、関数の周波数表現の複数の周波数成分を用いることとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を表現する方法及び装置、並びに、例えば検索又は検証のために画像を比較又は照合する方法及び装置に関する。
【背景技術】
【０００２】
多数の画像データベースが存在し、特定の画像のコピー或いはその画像の変更バージョンを探し出す必要がある場合も多い。このような機能は、例えば、権利管理或いは検索のために必要であり得る。種々のウェブサイトに載せられた同一画像は、同様のコンテンツを示す可能性があるため、貴重な検索の手掛かりとなる。別の重要な用途は、「フィルム」写真及びネガと、他のディジタルアーカイブとの間の識別及び紐付けである。
【０００３】
ＭＤ５等のハッシュアルゴリズムを用いて同一画像を検出することができる。ハッシュ関数はコンテンツに基づく値を生成するものであり、２つの画像が同じであればそのハッシュ値も同じになる。しかしながら、ＭＤ５等の従来の手法はビットに敏感(sensitive)である、すなわち、たった１ビットの変化が全く異なるハッシュ値を生じることになる。通常、画像には何らかの形の変更、例えば圧縮が施されるため、従来のハッシュ法では失敗してしまう。
【０００４】
重複画像を検出する１つの一般的な画像処理手法は、画像対を位置合わせして共通領域間の差異を見つけ出そうと試みることである。この問題として、位置合わせ工程が計算上複雑であり、大規模データベースでは検索に膨大な時間がかかる。新たな問い合わせ画像が提示される度に、完全な位置合わせ及び照合工程をデータベースの各エントリに対して行う必要がある。さらに重大な欠点は、検索を行うために原画像が利用可能で（又は送信され）なければならないことである。
【０００５】
代替的な手法は、画像の特徴を捉える小さな識別子の抽出を伴う。このような工程の利点は、識別子を一度だけ抽出して記憶すればよいことである。したがって、照合工程が効率的であれば、この方法は高速な検索性能を提供する。画像識別子は通常、画像を表現するビット列である（図２を参照）。
【０００６】
画像識別子は色分布又は階調分布に基づくものであってもよい。H. Chi Wong、Marshall Bern、David Goldberg著「An Image Signature for any Kind of Image」（Proc. ICIP 2002, pp. 409-412, 2002）［参考文献１］では、ｍ×ｎの格子点を用いて、特徴を抽出する位置を定義する。これらの特徴は、画素とその８近傍画素との間のグレーレベルの強度差に基づく。したがって、特徴ベクトルのサイズは８ｍｎとなる。２つの特徴ベクトル間の比較は、正規化Ｌ2距離測度を用いて行われる。この距離測度は、ヒストグラム間の差分絶対値和に基づく。提示される結果は、この手法がサイズ変更及び圧縮に対しては非常に正確に機能するが、回転に対しては正確に機能しないことを示唆する。
【０００７】
米国特許第６，６７１，４０７号［参考文献１４］の請求項は、R. Venkatesan、S.-M. Koon、M. H. Jakubowski、P. Moulin著「Robust Image Hashing」（Proc. IEEE ICIP 2000, pp. 664-666, Sep., 2000）［参考文献２］における研究に基づく。画像をデータベースに記憶し、画像に埋め込む透かしを生成するために、ハッシュ関数が生成される。ハッシュ関数は、入力画像にウェーブレット変換を行うことによって生成される。各サブバンドはランダムな大きさのブロックに分割され、各ブロックの統計量（平均又は分散）が計算される。次に、これらの統計量が８レベルに量子化され、この量子化が変更に対して或る程度のロバスト性を与える。量子化された値は、３ビットのバイナリ列で表現される。
【０００８】
上記の２つの方法は、入力画像を矩形領域に分割する事に依存する。したがって、いずれの方法も、いくらかの量の画像回転があると失敗してしまう。
【０００９】
色分布及び階調分布の代案として、周波数領域情報が画像識別子に用いられることがある。離散ウェーブレット変換（ＤＷＴ）に基づく手法が、ドベシィ（Daubechies）フィルタを用いるEdward Y. Chang、James Ze Wang、Chen Li、Gio Wiederhold著「RIME: A Replicated Image Detector for the World Wide Web」（Proc. of SPIE Symp. of Voice, Video, and Data Comms., pp. 58-67, Boston, MA, Nov., 1998）［参考文献３］に記載されている。ウェーブレット変換の最下位階層の部分領域を用いて画像が表現される。ＤＷＴに基づく上記［参考文献２］の方法では、ＤＷＴのＤＣＴ成分を求め、反復的且つ決定論的な領域成長法を用いて、原画像のバイナリバージョンを形成する。この方法は、大きな量の回転にはロバストでない。
【００１０】
ラドン変換に基づくF. Lefebvre、J. Czyz、B. Macq著「A Robust Soft Hash Algorithm for Digital Image Signature」（Proc. IEEE Int. Conf. Image Processing, pp. 495-498, 2003）［参考文献４］において、画像ハッシュ関数が開発されている。このハッシュ関数は透かし入れのために開発されたものであるが、回転、スケーリング、圧縮、フィルタリング、及びぼかし処理に対するロバスト性等のいくつかの非常に有用な特性を有するように設計されている。ラドン変換の後、共分散行列が計算され、２つの最大固有値に対応する固有ベクトルから署名が形成される。
【００１１】
Jin S. Seo、Jaap Haitsma、Ton Kalker、Chang D. Yoo著「A Robust Image Fingerprinting System using the Radon Transform」（Signal Processing: Image Communication, 19, pp. 325-339, 2004）［参考文献５］では、画像のラドン変換を用いて画像識別子が形成される。ラドン変換を行った後、自己相関、対数マッピング、及び２Ｄフーリエ変換を含むいくつかのステップが行われる。これにより、２Ｄのバイナリ識別子が抽出される。この方法は画像の左右反転に対してロバストでない。
【００１２】
識別子の抽出に対する最後の代案は、画像特徴の使用である。ウェーブレット変換を用いて特徴点の検出及び抽出を行う手法が、Vishal Monga、Brian Evans著「Robust Perceptual Image Hashing using Feature Points」（Proc. IEEE ICIP 2004, pp. 677-680, Oct., 2004）［参考文献６］に提案されている。検出された特徴を用いて画像署名が構築される。この方法は、回転に対するロバスト性に欠ける。
【００１３】
Alejandro Jaimes、Shih-Fu Chang、Alexander C. Loui著「Detection of Non-Identical Duplicate Consumer Photographs」（ICICS-PCM 2003, pp. 16-20, Dec., 2003）［参考文献７］では、特徴点が検出され、ＲＡＮＳＡＣアルゴリズムを用いて大域的な画像の位置合わせが行われる。相関及び自己顕著性マップから類似点の一致度が導出される。
【００１４】
米国特許出願第２００４／０１０３１０１号［参考文献８］は、画像の幾何変換コピーを検出する問題の解決に関するものである。これは、２つの画像間で一致する物体及び特徴の検出に基づく。画像間で一致が見つかると幾何変換が計算され、その２つの画像が位置合わせされ、画像間の類似度マップとして差分が計算される。
【００１５】
一般に、特徴点検出に基づく方法に用いられる検索工程及び照合工程は、高い計算能力が要求される。そのため、大規模データベースでの使用や、処理能力が限られている場合の使用には適していない。
【００１６】
エッジに基づく画像検索システムが、米国特許第６，０７２，９０４号［参考文献９］に開示されている。画像中のエッジ特徴に基づく固有ベクトルが画像毎に形成され、これらのベクトルの比較により検索が行われる。
【００１７】
画像特徴に基づくハッシュ値を生成する方式が、米国特許出願第５，４６５，３５３号［参考文献１０］に開示されている。画像毎に局所特徴点の集合が抽出される。特徴から３つ一組のハッシュ値が形成され、画像がデータベースに記憶される。問い合わせ画像に最も一致する特徴を有する文書を検索することができる投票方式が説明されている。使用される投票方式により、検索に高い計算能力が要求される。
【００１８】
米国特許出願第５，８１９，２８８号［参考文献１１］、米国特許出願第５，８５２，８２３号［参考文献１２］、及び米国特許出願第５，８９９，９９９号［参考文献１３］に提示される方法では、特徴は、一組の事前定義されたガウス導関数（２５個のフィルタ）を用いる多重解像度（３レベル）処理から導出される。これにより、各カラーチャネルにつき１５，６２５（２５3）個の特徴、すなわち、４６，８７５個の特徴が得られる。全ての画像にわたって特徴の統計量（平均及び分散）を計算することによって、画像の集合を記憶及び／又は問い合わせのためにグループ化することができる。この方法により用いられる記憶要件は非常に高い。
【００１９】
トレース変換に基づく画像特徴の抽出方法が、Maria Petrou、Alexander Kadyrov著「Affine Invariant Features from the Trace Transform」（IEEE Trans. on PAMI, 26(1), Jan, 2004, pp 30-44）［参考文献１６］に提案されている。汎関数の組み合わせを用いて、（７×６×１４）５８８個の数字から成る特徴ベクトルが得られる。この手法は、特徴ベクトルの５８８個の全ての数字を得るためにトレース変換を画像毎に何度も行う必要があるため、計算量が多い。
【発明の概要】
【発明が解決しようとする課題】
【００２０】
既存のアルゴリズム及びシステムの主な問題として以下が挙げられる。
・特徴の抽出及び／又は照合に関して計算量が多い。
・記述子が膨大な記憶空間を必要とする。
・画像の変更に対するロバスト性に欠ける。
・誤受入率（false acceptance rate）が高すぎて大規模なデータセットには効果的に使用できない。
【課題を解決するための手段】
【００２１】
本発明の態様が添付の特許請求の範囲に記載される。
【００２２】
本発明は、効率的な特徴抽出及び非常に単純で高速な照合を提供する。また、識別子は非常に小さく、通常１２８ビット（１６バイト）以下である。そのため、１ＫＢでは６４個の画像識別子を記憶し、１ＭＢでは６５，５３６個の識別子を記憶することができる。
【００２３】
最も良く知られている従来技術の方法は、画像当たり４００ビットを必要とする。
【００２４】
本発明の誤受入率は百万分の１程度である。
【００２５】
本発明は、画像から識別子を抽出する新規の方法に関する。一実施の形態において、トレース変換の使用と、フーリエ変換の振幅に基づく係数のバイナリ符号化とを組み合わせる方法により、ロバストな識別子が得られる。バイナリ符号化方法は、（トレース変換の）サーカス関数（circus function）のフーリエ変換を用いて、バイナリ識別子を抽出する。
【００２６】
トレース変換では、直線によって画像をトレースし、この直線に沿って画像強度又はカラー関数の特定の汎関数Ｔを計算する。種々のトレース汎関数Ｔを用いて、単一の入力画像から様々なトレース変換を作成してもよい。２Ｄ平面において、線は、２つのパラメータ（ｄ，θ）により特徴付けることができる。そのため、２Ｄ画像のトレース変換は、各トレース線のパラメータ（ｄ，θ）の２Ｄ関数となる。
【００２７】
次に、トレース変換の（トレース領域の）列に沿ってダイアメトリック汎関数（diametric functional）Ｐを適用することによって「サーカス関数」を計算する（すなわち、距離パラメータｄにわたってダイアメトリック汎関数Ｐを適用し、角度θに関する１Ｄサーカス関数を得る）。
【００２８】
本発明によれば、サーカス関数の周波数表現（例えばフーリエ変換）が得られ、周波数振幅成分に対して関数が定義され、その符号がバイナリ記述子として採用される。
【００２９】
本方法の他の態様は、異なる汎関数の組み合わせを用いることにより得られる識別子の「族」から部分的に選択したものを組み合わせて単一の記述子にする。このような組み合わせを用いることによって識別子の性能は大きく向上する。
【００３０】
添付図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【００３１】
【図１ａ】画像を示す図である。
【図１ｂ】図１ａの画像を縮小したバージョンを示す図である。
【図１ｃ】図１ａの画像を回転させたバージョンを示す図である。
【図１ｄ】図１ａの画像をぼかしたバージョンを示す図である。
【図２】従来技術による画像及びそのビット列表現を示す図である。
【図３】本発明の一実施形態の方法のステップを示す図である。
【図４】本発明の一実施形態の別の方法のステップを示す図である。
【図５】トレース変換の線パラメータ化を示す図である。
【図６】種々の画像から導出される関数を示す図である。
【図７】本発明の一実施形態による装置のブロック図である。
【図８】複数のトレース変換を用いる一実施形態を示すブロック図である。
【図９】図８の実施形態により作成されるビットストリームを示す図である。
【発明を実施するための形態】
【００３２】
画像表現を導出すると共に、そのような表現を例えば１つ又は複数の画像の識別、照合、或いは検証のために用いる様々な実施形態を以下に説明する。本発明は、上述のように画像を識別するために特に有用であるが、画像の識別に限定されるものではない。同様に、実施形態で説明される画像識別子は画像表現又は画像記述子の一例である。
【００３３】
本発明の一実施形態による視覚識別子の具体的設計は、ロバスト性を持たせたい画像の変更の種類、識別子の大きさ、抽出及び照合の複雑度、目標誤検出率(target false-alarm rate)等に関連する要件によって決まる。
【００３４】
ここでは、画像に対する以下の変更にロバストな識別子をもたらす一般的設計を示す。
・減色
・ぼかし
・輝度値変更
・反転（左右及び上下）
・グレースケール変換
・ヒストグラム等化
・ＪＰＥＧ圧縮
・ノイズ
・回転
・スケーリング
【００３５】
識別子は、広範な画像に対して百万分の１という非常に低い誤検出率を達成することが好ましい。
【００３６】
図１は、画像及びその画像の変更バージョンの一例を示す。より具体的には、図１ａは原画像であり、図１ｂは図１ａの画像を縮小したバージョンであり、図１ｃは図１ａの画像を回転させたバージョンであり、図１ｄは図１ａの画像をぼかしたバージョンである。
【００３７】
本発明の実施形態は画像の表現を導出する。より具体的には、画像に対応する信号を処理することによって画像識別子を導出する。
【００３８】
図３は、本発明の一実施形態による画像識別子を導出する方法のステップ、すなわち識別子抽出工程を示す。
【００３９】
トレース変換を適用する前処理として、画像をサイズ変更し（ステップ１１０）、また任意選択でフィルタリングする（ステップ１２０）。サイズ変更ステップ１１０は、画像を処理前に正規化するために用いられる。ステップ１２０は、画像に対して行われた何らかの処理、及び／又は、原画像全体を用いるのではなく領域を選択することにより生じるエイリアシング等の効果を除去するためのフィルタリングを含み得る。本方法の好適な一実施形態では、さらなる処理のために画像の中心から円形領域が抽出される。
【００４０】
ステップ１３０において、トレース変換Ｔ（ｄ，θ）が行われる。トレース変換１３０は、全ての可能な線を画像に射影してこれらの線に汎関数を適用する。汎関数は、通常は関数のベクトル空間Ｖ上の実数値関数である。
【００４１】
トレース変換の場合、画像中の線にトレース汎関数Ｔが適用される。図５に示されるように、線はｄ及びθによりパラメータ化される。次にステップ１４０において、トレース変換の列に（すなわち距離パラメータｄに沿って）さらなる汎関数Ｄを適用して、実数値ベクトルを得ることができる。この第２の汎関数Ｐはダイアメトリック汎関数として知られ、結果として得られるベクトル（θに関する１次元関数）はサーカス関数として知られる。第３の汎関数であるサーカス汎関数(circus functionl)をサーカス関数に適用して、単一の数を得ることができる。この結果の特性は、３つの異なる汎関数（トレース汎関数、ダイアメトリック汎関数、及びサーカス汎関数）を適切に選択することによって制御することができる。画像及び対応するトレース変換の例を含むトレース変換の全詳細は、例えば参照として本明細書中に援用されるAlexander Kadyrov、Maria Petrou著「The Trace Transform and Its Applications」（IEEE Trans. PAMI, 23(8), Aug., 2001, pp 811-828）［参考文献１５］に見ることができる。
【００４２】
本発明の実施形態の方法では、最初の２つのステップのみをトレース変換において行う。すなわち、トレース変換の後にダイアメトリック汎関数を適用して１次元のサーカス関数を得る。
【００４３】
本方法の１つの特定の例において、トレース汎関数Ｔは
【００４４】
【数１】
【００４５】
によって与えられ、ダイアメトリック汎関数Ｐは
【００４６】
【数２】
【００４７】
によって与えられる。
【００４８】
サーカス関数が様々な画像処理操作により受ける影響の例を図６に見ることができる。図６は、画像の様々な変形に対応するサーカス関数を示す。図６（ａ）は原画像に対応し、図６（ｂ）は元画像を回転させたバージョンに対応し、図６（ｃ）は元画像をぼかしたバージョンに対応する。回転は関数をシフトさせる（と共にスケール変化を生じる）ことが見て取れる。
【００４９】
上で挙げた全ての画像の変更操作に関して、汎関数を適切に選択することにより、画像ａのサーカス関数ｆ（ａ）は、変更された画像ａ’のサーカス関数ｆ（ａ’）がシフト又は（振幅が）スケーリングされたものに過ぎないことを示すことができる（参考文献１５の第３章を参照）。
【００５０】
【数３】
【００５１】
次に、式（３）のフーリエ変換を行うことによって次式が得られる。
【００５２】
【数４】
【００５３】
次に、式（６）の振幅を取ると次式が得られる。
【００５４】
【数５】
【００５５】
式（７）から、変更された画像及び原画像はもはや、スケーリング係数κを除いて同じであることが分かる。
【００５６】
ここで、本実施形態によれば、関数ｃ（ω）が複数のフーリエ変換係数の振幅係数上で定義される。この関数の１つの例示は、隣り合う係数の差分を取ることである。
【００５７】
【数６】
【００５８】
式（８）の結果として得られるベクトルに以下のような閾値を適用することによって、バイナリ列を抽出することができる。
【００５９】
【数７】
【００６０】
次に、これらの値Ｂ＝｛ｂ0，．．．，ｂn｝から、本発明の実施形態の画像識別子が構築される。
【００６１】
共に長さＮの２つの異なる識別子Ｂ1及びＢ2間での識別子の照合を行うために、正規化ハミング距離を取る。
【００６２】
【数８】
【００６３】
ここで、
【００６４】
【数９】
【００６５】
は排他的ＯＲ（ＸＯＲ）演算子である。識別子又は表現における他の比較方法も用いることができる。
【００６６】
識別子中の特定ビットを選択することにより、性能をさらに高めることができる。下位ビットは一般にロバスト性がより高く、上位ビットは識別性がより高い。本発明の特定の一実施形態では、最初のビットは無視され、識別子はその次の６４ビットから作られる。
【００６７】
上記の方法を行う本発明の一実施形態による装置の一例を図７に示す。具体的には、画像記憶モジュール２１０により画像２００が受け取られ、画像データベース２３０に記憶される。さらに、識別子抽出記憶モジュール２２０が、受け取った画像毎に本発明の方法に従って画像識別子を抽出し、それらの画像識別子を識別子データベース２４０に記憶する。このとき、任意選択では画像のコンテンツに関連する他の情報も一緒に適宜記憶する。
【００６８】
図７はさらに、上記の方法を用いて抽出された画像識別子を用いる画像検索エンジンを具現化する装置を示す。問い合わせ画像２５０の受け取りに応答して、画像検索エンジンによって画像の検証又は照合が行われる。本発明の方法に従って、識別子抽出モジュール２６０において問い合わせ画像２５０の画像識別子が抽出される。識別子照合モジュール２７０は、問い合わせ画像２５０の画像識別子を、識別子データベース２４０に記憶されている画像識別子と比較する。画像検索モジュール２８０は、画像データベース２３０から一致画像２９０を取り出す。以下で詳述するように、この一致画像２９０は、問い合わせ画像識別子と一致する画像識別子を有する。
【００６９】
図４は、フーリエ変換係数に対するバイナリ関数を定義する代替方法を示す。詳細には、フーリエ変換係数を得た（ステップ１７１）後、複数のフーリエ変換係数の振幅の対数を得る（ステップ１７２及び１７３）。係数の差分を上記の式（８）と同様に計算し（ステップ１７４）、その後、この差分の符号を取り、この符号によりバイナリ値を割り当てる（ステップ１７５）。次に、このバイナリ値を用いてバイナリ識別子を形成する。
【００７０】
上述した基本識別子は、図８及び図９に示すように、複数のトレース変換を用いて、別個の変換からのビットを組み合わせることによって改良することができる。２つの別個の変換３６１及び３６２からのバイナリ列を組み合わせる具体的な方法は、それらを連結して識別子３６３を得ることである。このようにして、式（１）のトレース汎関数Ｔを、式（２）によって与えられるダイアメトリック汎関数Ｐと共に用いて１つのバイナリ列を得た後、式（１）のトレース汎関数Ｔをダイアメトリック汎関数Ｐ
【００７１】
【数１０】
【００７２】
と共に用いて第２の列を得ることによって良好な結果を得ている。各バイナリ列の最初のビットは飛ばし、双方のストリングにおけるその次の６４ビットが連結されて１２８ビットの識別子を得る。
【００７３】
この識別子の１つの応用は、図７に示し上述したような画像検索エンジンとしての応用である。データベース２４０は、ファイル名、画像、撮影者、取得日時、及び任意の他の有用な情報等の関連する情報と共に、画像のバイナリ識別子を抽出して記憶することによって構築される。次に、問い合わせ画像ａqが与えられると、バイナリ識別子が抽出され、データベース中の全ての識別子Ｂ0．．．ＢMと比較される。問い合わせ画像に対するハミング距離が閾値未満である全ての画像が返される。
【００７４】
様々なトレース汎関数Ｔ及びダイアメトリック汎関数Ｄを用いることができ、例として以下が挙げられる（網羅的でないリスト）。
【００７５】
【数１１】
【００７６】
２つ又はそれ以上の識別子を組み合わせて、画像をもっとよく特徴付けすることができる。この組み合わせは、複数の識別子の連結によって行われることが好ましい。
【００７７】
回転、平行移動、及びスケーリングよりも高次の幾何変換の場合、上述した識別子のバージョンは適切ではなく、式（３）の関係は成り立たない。識別子のロバスト性は、正規化工程を用いることによってアフィン変換まで拡張することができる。この正規化工程の全詳細は、上記［参考文献１６］に見ることができる。サーカス関数を正規化するために２つのステップが導入される。最初のステップは、いわゆる関連サーカス(associated circus)を求めることを含み、２番目のステップは、正規化された関連サーカス関数を求めることを含む。この正規化の結果、（３）の関係が真であることが示される。これにより、上記と同様に識別子の抽出工程を継続することができる。
【００７８】
正規化工程と共に用いられるいくつかの適切なトレース汎関数が以下の（Ｇ１）及び（Ｇ２）で与えられる。また、ダイアメトリック汎関数の適切な選択が（Ｇ３）で与えられる。
【００７９】
【数１２】
【００８０】
ここで、ｒ≡ｔ−ｃであり、ｃ≡ｍｅｄｉａｎ（｛ｔk｝k，｛｜ｇ（ｔk）｜｝k）である。非負の重みｗ1，ｗ2，．．．，ｗnを有する数列ｙ1，ｙ2，．．．，ｙnの加重中央値を、この数列が重みにより昇順でソートされると仮定した場合に次式が成り立つ最大インデックスｍを見つけることによって定義する。
【００８１】
【数１３】
【００８２】
（式１２の）不等式が厳密である場合、中央値はｙmとなる。しかし、不等式が等式である場合、中央値は（ｙm＋ｙm-1）／２となる。
【００８３】
識別子を連続ビットブロックから構築する代わりに、実験的に選択を行うこともできる。このやり方の一例は、２組のデータ、すなわち、ｉ）独立した画像と、ｉｉ）原画像及び変更された画像とを用意することである。識別子の性能は、独立したデータの誤受入率(false acceptance rate)と、原画像及び変更された画像の誤拒否率(false rejection rate)とを比較することによって測定することができる。関心がある点は、等価エラー率(equal error rate)、又は、１×１０-6の誤受入率における誤拒否率である。最適化は、ビットが選択されていない状態で開始される。各ビットを１つずつ検査して、どのビットが（例えば等価エラー率又は何らかの同様の測度に関して）最良の性能を発揮するかを調べることが可能である。これにより、最良の結果を与えるビットが選択される。次に、全ての残りのビットを試験して、どれが最初のビットと組み合わせた際に最良の性能を発揮するかを見つけ出す。ここでもまた、エラー率が最低のビットが選択される。この手順は、全てのビットが選択されるまで繰り返される。そうすると、全体として最良の性能をもたらすビットの組み合わせを選択することが可能になる。
【００８４】
識別子を構造化して検索性能を高めることもできる。例えば、２パス探索を実施して、半分のビットを用いて１回目の探索を行い、次に所与のレベルの精度を有するものにのみ２回目の探索を行う。
【００８５】
リード・マラー(Reed-Muller)復号器或いはウイナー・ジブ(Wyner-Ziv)復号器等の方法を用いて識別子を圧縮し、さらにサイズを縮小することができる。
【００８６】
識別子はまた、ビデオシーケンス中のフレームをインデックス付けするために用いることもできる。新たなシーケンスが与えられると、フレームから識別子を抽出し、次に、同一シーケンスを見つけるために検索を行うことができる。これは、著作権の検出及びシーケンスの識別のために有用であり得る。
【００８７】
複数の放送会社が同一のコンテンツ、例えば広告又は株式ニュースの映像を送信する場合が多い。放送会社間のナビゲーションのために、識別子を用いてこれらのコンテンツ間にリンクを形成することができる。
【００８８】
画像識別子は、画像によりコンテンツを結びつける機会を提供する。ユーザがウェブページ上の特定の画像に興味がある場合、同一画像を有する他のページを見つける有効な方法は現在のところない。識別子を用いて、画像間のナビゲーション経路を提供することができる。
【００８９】
識別子を用いてブロードキャストフィード中の広告を検出することができる。これを用いて、広告主が自社のキャンペーンを追跡するための自動監視を行うことができる。
【００９０】
大規模な商用セットからパーソナルコンピュータ上の小規模なコレクションまで多くの画像データベースが存在する。データベースが厳格に制御されていない限り、通常はセット中の画像に重複があり、余分な記憶領域を無駄に必要とする。識別子は、これらのデータセット中の重複画像を削除又は紐付けするツールとして用いることができる。
【００９１】
本明細書中、「画像」という用語は、フィルタリング、解像度の変更、アップサンプリング、ダウンサンプリング等の後処理を含む画像単位を説明するために用いられるが、フレーム、フィールド、ピクチャ、又は画像、フレーム等のサブユニット若しくは領域等の他の同様の用語にも当てはまる。本明細書中、画像という用語は、文脈から明らかである場合を除き、画像全体又は画像の領域を意味する。同様に、画像の領域は画像全体を意味し得る。画像は、フレーム又はフィールドを含み、静止画、又はフィルム若しくはビデオ等の画像シーケンス、又は関連画像群中の画像に関連する。画像は、グレースケール画像又はカラー画像、又は別のタイプのマルチスペクトル画像、例えば、ＩＲ、ＵＶ若しくは他の電磁波画像、又は音響画像等であり得る。
【００９２】
実施形態において、周波数表現はフーリエ変換を用いて導出されるが、周波数表現はハール変換等の他の技法を用いて導出することもできる。特許請求の範囲において、フーリエ変換という単語は、ＤＦＴ及びＦＦＴ等の変形を網羅するものとする。
【００９３】
本発明は、適切な装置を用いて電気信号を処理することによって実施されることが好ましい。
【００９４】
本発明は、例えば、適切なソフトウェア及び／又はハードウェアの変更を加えたコンピュータシステムにおいて実施することができる。例えば、本発明は、プロセッサ若しくは制御装置等の制御手段若しくは処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等のような画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ若しくはプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はこれらの構成要素の任意の組み合わせを他の付加的な構成要素と共に有するコンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェア及び／若しくはハードウェアの形態において提供することができる。又は、特定用途向け装置或いはチップ等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置におけるシステムの構成要素は、他の構成要素から離れた場所に、例えばインターネットを介して設けられてもよい。
【００９５】
当業者であれば理解するように、説明した実施形態に対して多くの変形及び修正を行ってもよい。これは、添付の特許請求の範囲に規定される本発明の精神及び範囲に入る変形、修正及び等価物を全て含むことが意図される。
【技術分野】
【０００１】
本発明は、画像を表現する方法及び装置、並びに、例えば検索又は検証のために画像を比較又は照合する方法及び装置に関する。
【背景技術】
【０００２】
多数の画像データベースが存在し、特定の画像のコピー或いはその画像の変更バージョンを探し出す必要がある場合も多い。このような機能は、例えば、権利管理或いは検索のために必要であり得る。種々のウェブサイトに載せられた同一画像は、同様のコンテンツを示す可能性があるため、貴重な検索の手掛かりとなる。別の重要な用途は、「フィルム」写真及びネガと、他のディジタルアーカイブとの間の識別及び紐付けである。
【０００３】
ＭＤ５等のハッシュアルゴリズムを用いて同一画像を検出することができる。ハッシュ関数はコンテンツに基づく値を生成するものであり、２つの画像が同じであればそのハッシュ値も同じになる。しかしながら、ＭＤ５等の従来の手法はビットに敏感(sensitive)である、すなわち、たった１ビットの変化が全く異なるハッシュ値を生じることになる。通常、画像には何らかの形の変更、例えば圧縮が施されるため、従来のハッシュ法では失敗してしまう。
【０００４】
重複画像を検出する１つの一般的な画像処理手法は、画像対を位置合わせして共通領域間の差異を見つけ出そうと試みることである。この問題として、位置合わせ工程が計算上複雑であり、大規模データベースでは検索に膨大な時間がかかる。新たな問い合わせ画像が提示される度に、完全な位置合わせ及び照合工程をデータベースの各エントリに対して行う必要がある。さらに重大な欠点は、検索を行うために原画像が利用可能で（又は送信され）なければならないことである。
【０００５】
代替的な手法は、画像の特徴を捉える小さな識別子の抽出を伴う。このような工程の利点は、識別子を一度だけ抽出して記憶すればよいことである。したがって、照合工程が効率的であれば、この方法は高速な検索性能を提供する。画像識別子は通常、画像を表現するビット列である（図２を参照）。
【０００６】
画像識別子は色分布又は階調分布に基づくものであってもよい。H. Chi Wong、Marshall Bern、David Goldberg著「An Image Signature for any Kind of Image」（Proc. ICIP 2002, pp. 409-412, 2002）［参考文献１］では、ｍ×ｎの格子点を用いて、特徴を抽出する位置を定義する。これらの特徴は、画素とその８近傍画素との間のグレーレベルの強度差に基づく。したがって、特徴ベクトルのサイズは８ｍｎとなる。２つの特徴ベクトル間の比較は、正規化Ｌ2距離測度を用いて行われる。この距離測度は、ヒストグラム間の差分絶対値和に基づく。提示される結果は、この手法がサイズ変更及び圧縮に対しては非常に正確に機能するが、回転に対しては正確に機能しないことを示唆する。
【０００７】
米国特許第６，６７１，４０７号［参考文献１４］の請求項は、R. Venkatesan、S.-M. Koon、M. H. Jakubowski、P. Moulin著「Robust Image Hashing」（Proc. IEEE ICIP 2000, pp. 664-666, Sep., 2000）［参考文献２］における研究に基づく。画像をデータベースに記憶し、画像に埋め込む透かしを生成するために、ハッシュ関数が生成される。ハッシュ関数は、入力画像にウェーブレット変換を行うことによって生成される。各サブバンドはランダムな大きさのブロックに分割され、各ブロックの統計量（平均又は分散）が計算される。次に、これらの統計量が８レベルに量子化され、この量子化が変更に対して或る程度のロバスト性を与える。量子化された値は、３ビットのバイナリ列で表現される。
【０００８】
上記の２つの方法は、入力画像を矩形領域に分割する事に依存する。したがって、いずれの方法も、いくらかの量の画像回転があると失敗してしまう。
【０００９】
色分布及び階調分布の代案として、周波数領域情報が画像識別子に用いられることがある。離散ウェーブレット変換（ＤＷＴ）に基づく手法が、ドベシィ（Daubechies）フィルタを用いるEdward Y. Chang、James Ze Wang、Chen Li、Gio Wiederhold著「RIME: A Replicated Image Detector for the World Wide Web」（Proc. of SPIE Symp. of Voice, Video, and Data Comms., pp. 58-67, Boston, MA, Nov., 1998）［参考文献３］に記載されている。ウェーブレット変換の最下位階層の部分領域を用いて画像が表現される。ＤＷＴに基づく上記［参考文献２］の方法では、ＤＷＴのＤＣＴ成分を求め、反復的且つ決定論的な領域成長法を用いて、原画像のバイナリバージョンを形成する。この方法は、大きな量の回転にはロバストでない。
【００１０】
ラドン変換に基づくF. Lefebvre、J. Czyz、B. Macq著「A Robust Soft Hash Algorithm for Digital Image Signature」（Proc. IEEE Int. Conf. Image Processing, pp. 495-498, 2003）［参考文献４］において、画像ハッシュ関数が開発されている。このハッシュ関数は透かし入れのために開発されたものであるが、回転、スケーリング、圧縮、フィルタリング、及びぼかし処理に対するロバスト性等のいくつかの非常に有用な特性を有するように設計されている。ラドン変換の後、共分散行列が計算され、２つの最大固有値に対応する固有ベクトルから署名が形成される。
【００１１】
Jin S. Seo、Jaap Haitsma、Ton Kalker、Chang D. Yoo著「A Robust Image Fingerprinting System using the Radon Transform」（Signal Processing: Image Communication, 19, pp. 325-339, 2004）［参考文献５］では、画像のラドン変換を用いて画像識別子が形成される。ラドン変換を行った後、自己相関、対数マッピング、及び２Ｄフーリエ変換を含むいくつかのステップが行われる。これにより、２Ｄのバイナリ識別子が抽出される。この方法は画像の左右反転に対してロバストでない。
【００１２】
識別子の抽出に対する最後の代案は、画像特徴の使用である。ウェーブレット変換を用いて特徴点の検出及び抽出を行う手法が、Vishal Monga、Brian Evans著「Robust Perceptual Image Hashing using Feature Points」（Proc. IEEE ICIP 2004, pp. 677-680, Oct., 2004）［参考文献６］に提案されている。検出された特徴を用いて画像署名が構築される。この方法は、回転に対するロバスト性に欠ける。
【００１３】
Alejandro Jaimes、Shih-Fu Chang、Alexander C. Loui著「Detection of Non-Identical Duplicate Consumer Photographs」（ICICS-PCM 2003, pp. 16-20, Dec., 2003）［参考文献７］では、特徴点が検出され、ＲＡＮＳＡＣアルゴリズムを用いて大域的な画像の位置合わせが行われる。相関及び自己顕著性マップから類似点の一致度が導出される。
【００１４】
米国特許出願第２００４／０１０３１０１号［参考文献８］は、画像の幾何変換コピーを検出する問題の解決に関するものである。これは、２つの画像間で一致する物体及び特徴の検出に基づく。画像間で一致が見つかると幾何変換が計算され、その２つの画像が位置合わせされ、画像間の類似度マップとして差分が計算される。
【００１５】
一般に、特徴点検出に基づく方法に用いられる検索工程及び照合工程は、高い計算能力が要求される。そのため、大規模データベースでの使用や、処理能力が限られている場合の使用には適していない。
【００１６】
エッジに基づく画像検索システムが、米国特許第６，０７２，９０４号［参考文献９］に開示されている。画像中のエッジ特徴に基づく固有ベクトルが画像毎に形成され、これらのベクトルの比較により検索が行われる。
【００１７】
画像特徴に基づくハッシュ値を生成する方式が、米国特許出願第５，４６５，３５３号［参考文献１０］に開示されている。画像毎に局所特徴点の集合が抽出される。特徴から３つ一組のハッシュ値が形成され、画像がデータベースに記憶される。問い合わせ画像に最も一致する特徴を有する文書を検索することができる投票方式が説明されている。使用される投票方式により、検索に高い計算能力が要求される。
【００１８】
米国特許出願第５，８１９，２８８号［参考文献１１］、米国特許出願第５，８５２，８２３号［参考文献１２］、及び米国特許出願第５，８９９，９９９号［参考文献１３］に提示される方法では、特徴は、一組の事前定義されたガウス導関数（２５個のフィルタ）を用いる多重解像度（３レベル）処理から導出される。これにより、各カラーチャネルにつき１５，６２５（２５3）個の特徴、すなわち、４６，８７５個の特徴が得られる。全ての画像にわたって特徴の統計量（平均及び分散）を計算することによって、画像の集合を記憶及び／又は問い合わせのためにグループ化することができる。この方法により用いられる記憶要件は非常に高い。
【００１９】
トレース変換に基づく画像特徴の抽出方法が、Maria Petrou、Alexander Kadyrov著「Affine Invariant Features from the Trace Transform」（IEEE Trans. on PAMI, 26(1), Jan, 2004, pp 30-44）［参考文献１６］に提案されている。汎関数の組み合わせを用いて、（７×６×１４）５８８個の数字から成る特徴ベクトルが得られる。この手法は、特徴ベクトルの５８８個の全ての数字を得るためにトレース変換を画像毎に何度も行う必要があるため、計算量が多い。
【発明の概要】
【発明が解決しようとする課題】
【００２０】
既存のアルゴリズム及びシステムの主な問題として以下が挙げられる。
・特徴の抽出及び／又は照合に関して計算量が多い。
・記述子が膨大な記憶空間を必要とする。
・画像の変更に対するロバスト性に欠ける。
・誤受入率（false acceptance rate）が高すぎて大規模なデータセットには効果的に使用できない。
【課題を解決するための手段】
【００２１】
本発明の態様が添付の特許請求の範囲に記載される。
【００２２】
本発明は、効率的な特徴抽出及び非常に単純で高速な照合を提供する。また、識別子は非常に小さく、通常１２８ビット（１６バイト）以下である。そのため、１ＫＢでは６４個の画像識別子を記憶し、１ＭＢでは６５，５３６個の識別子を記憶することができる。
【００２３】
最も良く知られている従来技術の方法は、画像当たり４００ビットを必要とする。
【００２４】
本発明の誤受入率は百万分の１程度である。
【００２５】
本発明は、画像から識別子を抽出する新規の方法に関する。一実施の形態において、トレース変換の使用と、フーリエ変換の振幅に基づく係数のバイナリ符号化とを組み合わせる方法により、ロバストな識別子が得られる。バイナリ符号化方法は、（トレース変換の）サーカス関数（circus function）のフーリエ変換を用いて、バイナリ識別子を抽出する。
【００２６】
トレース変換では、直線によって画像をトレースし、この直線に沿って画像強度又はカラー関数の特定の汎関数Ｔを計算する。種々のトレース汎関数Ｔを用いて、単一の入力画像から様々なトレース変換を作成してもよい。２Ｄ平面において、線は、２つのパラメータ（ｄ，θ）により特徴付けることができる。そのため、２Ｄ画像のトレース変換は、各トレース線のパラメータ（ｄ，θ）の２Ｄ関数となる。
【００２７】
次に、トレース変換の（トレース領域の）列に沿ってダイアメトリック汎関数（diametric functional）Ｐを適用することによって「サーカス関数」を計算する（すなわち、距離パラメータｄにわたってダイアメトリック汎関数Ｐを適用し、角度θに関する１Ｄサーカス関数を得る）。
【００２８】
本発明によれば、サーカス関数の周波数表現（例えばフーリエ変換）が得られ、周波数振幅成分に対して関数が定義され、その符号がバイナリ記述子として採用される。
【００２９】
本方法の他の態様は、異なる汎関数の組み合わせを用いることにより得られる識別子の「族」から部分的に選択したものを組み合わせて単一の記述子にする。このような組み合わせを用いることによって識別子の性能は大きく向上する。
【００３０】
添付図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【００３１】
【図１ａ】画像を示す図である。
【図１ｂ】図１ａの画像を縮小したバージョンを示す図である。
【図１ｃ】図１ａの画像を回転させたバージョンを示す図である。
【図１ｄ】図１ａの画像をぼかしたバージョンを示す図である。
【図２】従来技術による画像及びそのビット列表現を示す図である。
【図３】本発明の一実施形態の方法のステップを示す図である。
【図４】本発明の一実施形態の別の方法のステップを示す図である。
【図５】トレース変換の線パラメータ化を示す図である。
【図６】種々の画像から導出される関数を示す図である。
【図７】本発明の一実施形態による装置のブロック図である。
【図８】複数のトレース変換を用いる一実施形態を示すブロック図である。
【図９】図８の実施形態により作成されるビットストリームを示す図である。
【発明を実施するための形態】
【００３２】
画像表現を導出すると共に、そのような表現を例えば１つ又は複数の画像の識別、照合、或いは検証のために用いる様々な実施形態を以下に説明する。本発明は、上述のように画像を識別するために特に有用であるが、画像の識別に限定されるものではない。同様に、実施形態で説明される画像識別子は画像表現又は画像記述子の一例である。
【００３３】
本発明の一実施形態による視覚識別子の具体的設計は、ロバスト性を持たせたい画像の変更の種類、識別子の大きさ、抽出及び照合の複雑度、目標誤検出率(target false-alarm rate)等に関連する要件によって決まる。
【００３４】
ここでは、画像に対する以下の変更にロバストな識別子をもたらす一般的設計を示す。
・減色
・ぼかし
・輝度値変更
・反転（左右及び上下）
・グレースケール変換
・ヒストグラム等化
・ＪＰＥＧ圧縮
・ノイズ
・回転
・スケーリング
【００３５】
識別子は、広範な画像に対して百万分の１という非常に低い誤検出率を達成することが好ましい。
【００３６】
図１は、画像及びその画像の変更バージョンの一例を示す。より具体的には、図１ａは原画像であり、図１ｂは図１ａの画像を縮小したバージョンであり、図１ｃは図１ａの画像を回転させたバージョンであり、図１ｄは図１ａの画像をぼかしたバージョンである。
【００３７】
本発明の実施形態は画像の表現を導出する。より具体的には、画像に対応する信号を処理することによって画像識別子を導出する。
【００３８】
図３は、本発明の一実施形態による画像識別子を導出する方法のステップ、すなわち識別子抽出工程を示す。
【００３９】
トレース変換を適用する前処理として、画像をサイズ変更し（ステップ１１０）、また任意選択でフィルタリングする（ステップ１２０）。サイズ変更ステップ１１０は、画像を処理前に正規化するために用いられる。ステップ１２０は、画像に対して行われた何らかの処理、及び／又は、原画像全体を用いるのではなく領域を選択することにより生じるエイリアシング等の効果を除去するためのフィルタリングを含み得る。本方法の好適な一実施形態では、さらなる処理のために画像の中心から円形領域が抽出される。
【００４０】
ステップ１３０において、トレース変換Ｔ（ｄ，θ）が行われる。トレース変換１３０は、全ての可能な線を画像に射影してこれらの線に汎関数を適用する。汎関数は、通常は関数のベクトル空間Ｖ上の実数値関数である。
【００４１】
トレース変換の場合、画像中の線にトレース汎関数Ｔが適用される。図５に示されるように、線はｄ及びθによりパラメータ化される。次にステップ１４０において、トレース変換の列に（すなわち距離パラメータｄに沿って）さらなる汎関数Ｄを適用して、実数値ベクトルを得ることができる。この第２の汎関数Ｐはダイアメトリック汎関数として知られ、結果として得られるベクトル（θに関する１次元関数）はサーカス関数として知られる。第３の汎関数であるサーカス汎関数(circus functionl)をサーカス関数に適用して、単一の数を得ることができる。この結果の特性は、３つの異なる汎関数（トレース汎関数、ダイアメトリック汎関数、及びサーカス汎関数）を適切に選択することによって制御することができる。画像及び対応するトレース変換の例を含むトレース変換の全詳細は、例えば参照として本明細書中に援用されるAlexander Kadyrov、Maria Petrou著「The Trace Transform and Its Applications」（IEEE Trans. PAMI, 23(8), Aug., 2001, pp 811-828）［参考文献１５］に見ることができる。
【００４２】
本発明の実施形態の方法では、最初の２つのステップのみをトレース変換において行う。すなわち、トレース変換の後にダイアメトリック汎関数を適用して１次元のサーカス関数を得る。
【００４３】
本方法の１つの特定の例において、トレース汎関数Ｔは
【００４４】
【数１】
【００４５】
によって与えられ、ダイアメトリック汎関数Ｐは
【００４６】
【数２】
【００４７】
によって与えられる。
【００４８】
サーカス関数が様々な画像処理操作により受ける影響の例を図６に見ることができる。図６は、画像の様々な変形に対応するサーカス関数を示す。図６（ａ）は原画像に対応し、図６（ｂ）は元画像を回転させたバージョンに対応し、図６（ｃ）は元画像をぼかしたバージョンに対応する。回転は関数をシフトさせる（と共にスケール変化を生じる）ことが見て取れる。
【００４９】
上で挙げた全ての画像の変更操作に関して、汎関数を適切に選択することにより、画像ａのサーカス関数ｆ（ａ）は、変更された画像ａ’のサーカス関数ｆ（ａ’）がシフト又は（振幅が）スケーリングされたものに過ぎないことを示すことができる（参考文献１５の第３章を参照）。
【００５０】
【数３】
【００５１】
次に、式（３）のフーリエ変換を行うことによって次式が得られる。
【００５２】
【数４】
【００５３】
次に、式（６）の振幅を取ると次式が得られる。
【００５４】
【数５】
【００５５】
式（７）から、変更された画像及び原画像はもはや、スケーリング係数κを除いて同じであることが分かる。
【００５６】
ここで、本実施形態によれば、関数ｃ（ω）が複数のフーリエ変換係数の振幅係数上で定義される。この関数の１つの例示は、隣り合う係数の差分を取ることである。
【００５７】
【数６】
【００５８】
式（８）の結果として得られるベクトルに以下のような閾値を適用することによって、バイナリ列を抽出することができる。
【００５９】
【数７】
【００６０】
次に、これらの値Ｂ＝｛ｂ0，．．．，ｂn｝から、本発明の実施形態の画像識別子が構築される。
【００６１】
共に長さＮの２つの異なる識別子Ｂ1及びＢ2間での識別子の照合を行うために、正規化ハミング距離を取る。
【００６２】
【数８】
【００６３】
ここで、
【００６４】
【数９】
【００６５】
は排他的ＯＲ（ＸＯＲ）演算子である。識別子又は表現における他の比較方法も用いることができる。
【００６６】
識別子中の特定ビットを選択することにより、性能をさらに高めることができる。下位ビットは一般にロバスト性がより高く、上位ビットは識別性がより高い。本発明の特定の一実施形態では、最初のビットは無視され、識別子はその次の６４ビットから作られる。
【００６７】
上記の方法を行う本発明の一実施形態による装置の一例を図７に示す。具体的には、画像記憶モジュール２１０により画像２００が受け取られ、画像データベース２３０に記憶される。さらに、識別子抽出記憶モジュール２２０が、受け取った画像毎に本発明の方法に従って画像識別子を抽出し、それらの画像識別子を識別子データベース２４０に記憶する。このとき、任意選択では画像のコンテンツに関連する他の情報も一緒に適宜記憶する。
【００６８】
図７はさらに、上記の方法を用いて抽出された画像識別子を用いる画像検索エンジンを具現化する装置を示す。問い合わせ画像２５０の受け取りに応答して、画像検索エンジンによって画像の検証又は照合が行われる。本発明の方法に従って、識別子抽出モジュール２６０において問い合わせ画像２５０の画像識別子が抽出される。識別子照合モジュール２７０は、問い合わせ画像２５０の画像識別子を、識別子データベース２４０に記憶されている画像識別子と比較する。画像検索モジュール２８０は、画像データベース２３０から一致画像２９０を取り出す。以下で詳述するように、この一致画像２９０は、問い合わせ画像識別子と一致する画像識別子を有する。
【００６９】
図４は、フーリエ変換係数に対するバイナリ関数を定義する代替方法を示す。詳細には、フーリエ変換係数を得た（ステップ１７１）後、複数のフーリエ変換係数の振幅の対数を得る（ステップ１７２及び１７３）。係数の差分を上記の式（８）と同様に計算し（ステップ１７４）、その後、この差分の符号を取り、この符号によりバイナリ値を割り当てる（ステップ１７５）。次に、このバイナリ値を用いてバイナリ識別子を形成する。
【００７０】
上述した基本識別子は、図８及び図９に示すように、複数のトレース変換を用いて、別個の変換からのビットを組み合わせることによって改良することができる。２つの別個の変換３６１及び３６２からのバイナリ列を組み合わせる具体的な方法は、それらを連結して識別子３６３を得ることである。このようにして、式（１）のトレース汎関数Ｔを、式（２）によって与えられるダイアメトリック汎関数Ｐと共に用いて１つのバイナリ列を得た後、式（１）のトレース汎関数Ｔをダイアメトリック汎関数Ｐ
【００７１】
【数１０】
【００７２】
と共に用いて第２の列を得ることによって良好な結果を得ている。各バイナリ列の最初のビットは飛ばし、双方のストリングにおけるその次の６４ビットが連結されて１２８ビットの識別子を得る。
【００７３】
この識別子の１つの応用は、図７に示し上述したような画像検索エンジンとしての応用である。データベース２４０は、ファイル名、画像、撮影者、取得日時、及び任意の他の有用な情報等の関連する情報と共に、画像のバイナリ識別子を抽出して記憶することによって構築される。次に、問い合わせ画像ａqが与えられると、バイナリ識別子が抽出され、データベース中の全ての識別子Ｂ0．．．ＢMと比較される。問い合わせ画像に対するハミング距離が閾値未満である全ての画像が返される。
【００７４】
様々なトレース汎関数Ｔ及びダイアメトリック汎関数Ｄを用いることができ、例として以下が挙げられる（網羅的でないリスト）。
【００７５】
【数１１】
【００７６】
２つ又はそれ以上の識別子を組み合わせて、画像をもっとよく特徴付けすることができる。この組み合わせは、複数の識別子の連結によって行われることが好ましい。
【００７７】
回転、平行移動、及びスケーリングよりも高次の幾何変換の場合、上述した識別子のバージョンは適切ではなく、式（３）の関係は成り立たない。識別子のロバスト性は、正規化工程を用いることによってアフィン変換まで拡張することができる。この正規化工程の全詳細は、上記［参考文献１６］に見ることができる。サーカス関数を正規化するために２つのステップが導入される。最初のステップは、いわゆる関連サーカス(associated circus)を求めることを含み、２番目のステップは、正規化された関連サーカス関数を求めることを含む。この正規化の結果、（３）の関係が真であることが示される。これにより、上記と同様に識別子の抽出工程を継続することができる。
【００７８】
正規化工程と共に用いられるいくつかの適切なトレース汎関数が以下の（Ｇ１）及び（Ｇ２）で与えられる。また、ダイアメトリック汎関数の適切な選択が（Ｇ３）で与えられる。
【００７９】
【数１２】
【００８０】
ここで、ｒ≡ｔ−ｃであり、ｃ≡ｍｅｄｉａｎ（｛ｔk｝k，｛｜ｇ（ｔk）｜｝k）である。非負の重みｗ1，ｗ2，．．．，ｗnを有する数列ｙ1，ｙ2，．．．，ｙnの加重中央値を、この数列が重みにより昇順でソートされると仮定した場合に次式が成り立つ最大インデックスｍを見つけることによって定義する。
【００８１】
【数１３】
【００８２】
（式１２の）不等式が厳密である場合、中央値はｙmとなる。しかし、不等式が等式である場合、中央値は（ｙm＋ｙm-1）／２となる。
【００８３】
識別子を連続ビットブロックから構築する代わりに、実験的に選択を行うこともできる。このやり方の一例は、２組のデータ、すなわち、ｉ）独立した画像と、ｉｉ）原画像及び変更された画像とを用意することである。識別子の性能は、独立したデータの誤受入率(false acceptance rate)と、原画像及び変更された画像の誤拒否率(false rejection rate)とを比較することによって測定することができる。関心がある点は、等価エラー率(equal error rate)、又は、１×１０-6の誤受入率における誤拒否率である。最適化は、ビットが選択されていない状態で開始される。各ビットを１つずつ検査して、どのビットが（例えば等価エラー率又は何らかの同様の測度に関して）最良の性能を発揮するかを調べることが可能である。これにより、最良の結果を与えるビットが選択される。次に、全ての残りのビットを試験して、どれが最初のビットと組み合わせた際に最良の性能を発揮するかを見つけ出す。ここでもまた、エラー率が最低のビットが選択される。この手順は、全てのビットが選択されるまで繰り返される。そうすると、全体として最良の性能をもたらすビットの組み合わせを選択することが可能になる。
【００８４】
識別子を構造化して検索性能を高めることもできる。例えば、２パス探索を実施して、半分のビットを用いて１回目の探索を行い、次に所与のレベルの精度を有するものにのみ２回目の探索を行う。
【００８５】
リード・マラー(Reed-Muller)復号器或いはウイナー・ジブ(Wyner-Ziv)復号器等の方法を用いて識別子を圧縮し、さらにサイズを縮小することができる。
【００８６】
識別子はまた、ビデオシーケンス中のフレームをインデックス付けするために用いることもできる。新たなシーケンスが与えられると、フレームから識別子を抽出し、次に、同一シーケンスを見つけるために検索を行うことができる。これは、著作権の検出及びシーケンスの識別のために有用であり得る。
【００８７】
複数の放送会社が同一のコンテンツ、例えば広告又は株式ニュースの映像を送信する場合が多い。放送会社間のナビゲーションのために、識別子を用いてこれらのコンテンツ間にリンクを形成することができる。
【００８８】
画像識別子は、画像によりコンテンツを結びつける機会を提供する。ユーザがウェブページ上の特定の画像に興味がある場合、同一画像を有する他のページを見つける有効な方法は現在のところない。識別子を用いて、画像間のナビゲーション経路を提供することができる。
【００８９】
識別子を用いてブロードキャストフィード中の広告を検出することができる。これを用いて、広告主が自社のキャンペーンを追跡するための自動監視を行うことができる。
【００９０】
大規模な商用セットからパーソナルコンピュータ上の小規模なコレクションまで多くの画像データベースが存在する。データベースが厳格に制御されていない限り、通常はセット中の画像に重複があり、余分な記憶領域を無駄に必要とする。識別子は、これらのデータセット中の重複画像を削除又は紐付けするツールとして用いることができる。
【００９１】
本明細書中、「画像」という用語は、フィルタリング、解像度の変更、アップサンプリング、ダウンサンプリング等の後処理を含む画像単位を説明するために用いられるが、フレーム、フィールド、ピクチャ、又は画像、フレーム等のサブユニット若しくは領域等の他の同様の用語にも当てはまる。本明細書中、画像という用語は、文脈から明らかである場合を除き、画像全体又は画像の領域を意味する。同様に、画像の領域は画像全体を意味し得る。画像は、フレーム又はフィールドを含み、静止画、又はフィルム若しくはビデオ等の画像シーケンス、又は関連画像群中の画像に関連する。画像は、グレースケール画像又はカラー画像、又は別のタイプのマルチスペクトル画像、例えば、ＩＲ、ＵＶ若しくは他の電磁波画像、又は音響画像等であり得る。
【００９２】
実施形態において、周波数表現はフーリエ変換を用いて導出されるが、周波数表現はハール変換等の他の技法を用いて導出することもできる。特許請求の範囲において、フーリエ変換という単語は、ＤＦＴ及びＦＦＴ等の変形を網羅するものとする。
【００９３】
本発明は、適切な装置を用いて電気信号を処理することによって実施されることが好ましい。
【００９４】
本発明は、例えば、適切なソフトウェア及び／又はハードウェアの変更を加えたコンピュータシステムにおいて実施することができる。例えば、本発明は、プロセッサ若しくは制御装置等の制御手段若しくは処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等のような画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ若しくはプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はこれらの構成要素の任意の組み合わせを他の付加的な構成要素と共に有するコンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェア及び／若しくはハードウェアの形態において提供することができる。又は、特定用途向け装置或いはチップ等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置におけるシステムの構成要素は、他の構成要素から離れた場所に、例えばインターネットを介して設けられてもよい。
【００９５】
当業者であれば理解するように、説明した実施形態に対して多くの変形及び修正を行ってもよい。これは、添付の特許請求の範囲に規定される本発明の精神及び範囲に入る変形、修正及び等価物を全て含むことが意図される。
【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することによって該画像の表現を導出する方法であって、
前記画像の関数を導出することであって、前記画像を平行移動、拡大縮小、又は回転させたものの関数は、前記画像の前記関数を平行移動又は拡大縮小させたものである、画像の関数を導出することと、
前記画像の表現を導出するために、前記関数の周波数表現における複数の周波数成分を用いることと
を含む、画像の表現を導出する方法。
【請求項２】
前記関数は１次元関数である、請求項１に記載の方法。
【請求項３】
前記関数は、サーカス関数、又はサーカス関数から導出される関数である、請求項１又は２に記載の方法。
【請求項４】
前記画像の表現を導出するために、前記周波数成分の振幅を用いることを含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記周波数成分の前記振幅を用いて表現関数を定義することを含む、請求項４に記載の方法。
【請求項６】
画像に対応する信号を処理することによって該画像の表現を導出する方法であって、
前記画像の１次元関数を導出することと、
該関数の周波数成分を求めることと、
該周波数成分の振幅を用いて表現関数を定義することと
を含む、画像の表現を導出する方法。
【請求項７】
前記表現関数はバイナリ関数である、請求項５又は６に記載の方法。
【請求項８】
前記表現は、前記表現関数の値を含む、請求項５〜７のいずれか一項に記載の方法。
【請求項９】
前記周波数成分は、フーリエ変換又はハール変換を用いて求められる、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記表現関数は、
複数の周波数係数の振幅を計算するステップと、
各係数とその次の係数との間の前記振幅の差分を求めるステップと
を用いて得られる、請求項５〜８のいずれか一項に記載の方法。
【請求項１１】
前記表現関数は、
複数の周波数係数の振幅の対数を計算するステップと、
各係数とその次の係数との間の前記振幅の前記対数の差分を求めるステップと
を用いて得られる、請求項５〜８のいずれか一項に記載の方法。
【請求項１２】
前記周波数係数は、フーリエ変換係数又はハール変換係数である、請求項１０又は１１に記載の方法。
【請求項１３】
前記方法は、バイナリ関数を導出することをさらに含み、
該バイナリ関数は、前記求められた各差分に閾値を適用することによって導出され、該差分が０未満である場合にはバイナリ値０を与え、該差分が０以上である場合にはバイナリ値１を与えることによって、一連のバイナリ値が導出される、
請求項１０〜１２のいずれか一項に記載の方法。
【請求項１４】
前記画像の表現は、複数の周波数成分の振幅に対して定義される関数の値、好ましくはバイナリ関数の値を含む、請求項１、２、３、又は６のいずれか一項に記載の方法。
【請求項１５】
２つ以上のそれぞれのサーカス関数を用いて２つ以上の表現を導出することと、
該２つ以上の表現を組み合わせることと
を含む、請求項１〜１４のいずれか一項に記載の方法。
【請求項１６】
前記組み合わせることは、前記２つ以上の表現を連結することを含む、請求項１５に記載の方法。
【請求項１７】
ｎ個の数字又はビットを有する表現を導出することを含み、
ｍ個の数字又はビットの部分集合を選択することをさらに含む、
請求項１〜１６のいずれか一項に記載の方法。
【請求項１８】
前記関数は、以下の関数：
【数１】
のうちの１つ又は複数を用いて導出される、請求項１〜１７のいずれか一項に記載の方法。
【請求項１９】
周波数成分を求める前に前記関数を正規化することを含む、請求項１〜１８のいずれか一項に記載の方法。
【請求項２０】
関連サーカス関数又は正規化されたサーカス関数を導出することを含む、請求項１９に記載の方法。
【請求項２１】
以下の関数：
【数２】
のうちの１つ又は複数を用いる、請求項２０に記載の方法。
【請求項２２】
画像を識別又は比較するための、請求項１〜２１のいずれか一項に記載の方法。
【請求項２３】
画像を識別する方法であって、
請求項１〜２２のいずれか一項に記載の方法を用いて該画像の表現を導出することと、
該表現を該画像と関連付けることと
を含む、画像を識別する方法。
【請求項２４】
画像を比較する方法であって、
請求項１〜２３のいずれか一項に記載の方法を用いて導出される各画像の表現を比較することを含む、画像を比較する方法。
【請求項２５】
前記比較は、次式：
【数３】
を用いてハミング距離を求めることを含み、
【数４】
は排他的ＯＲ（ＸＯＲ）演算子であり、Ｎは長さである、
請求項２４に記載の方法。
【請求項２６】
表現の前記比較に基づいて画像を選択することを含む、請求項２４又は２５に記載の方法。
【請求項２７】
請求項１〜２１のいずれか一項に記載の方法を用いて導出される表現の例えば送信又は受信を含む使用。
【請求項２８】
請求項１〜２６のいずれか一項に記載の方法を実行する装置。
【請求項２９】
請求項１〜２６のいずれか一項に記載の方法を実行するために前記装置の動作を制御する制御装置を備える、請求項２８に記載の装置。
【請求項３０】
画像及び／又は画像の表現を記憶する記憶手段、例えば画像データベース及び／又は記述子データベース、表示手段、並びに画像選択手段のうちの１つ又は複数をさらに備える、請求項２９に記載の装置。
【請求項３１】
請求項１〜２６のいずれか一項に記載の方法を実行するコンピュータプログラム、システム、又はコンピュータ読み取り可能な記憶媒体。
【請求項１】
画像に対応する信号を処理することによって該画像の表現を導出する方法であって、
前記画像の関数を導出することであって、前記画像を平行移動、拡大縮小、又は回転させたものの関数は、前記画像の前記関数を平行移動又は拡大縮小させたものである、画像の関数を導出することと、
前記画像の表現を導出するために、前記関数の周波数表現における複数の周波数成分を用いることと
を含む、画像の表現を導出する方法。
【請求項２】
前記関数は１次元関数である、請求項１に記載の方法。
【請求項３】
前記関数は、サーカス関数、又はサーカス関数から導出される関数である、請求項１又は２に記載の方法。
【請求項４】
前記画像の表現を導出するために、前記周波数成分の振幅を用いることを含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記周波数成分の前記振幅を用いて表現関数を定義することを含む、請求項４に記載の方法。
【請求項６】
画像に対応する信号を処理することによって該画像の表現を導出する方法であって、
前記画像の１次元関数を導出することと、
該関数の周波数成分を求めることと、
該周波数成分の振幅を用いて表現関数を定義することと
を含む、画像の表現を導出する方法。
【請求項７】
前記表現関数はバイナリ関数である、請求項５又は６に記載の方法。
【請求項８】
前記表現は、前記表現関数の値を含む、請求項５〜７のいずれか一項に記載の方法。
【請求項９】
前記周波数成分は、フーリエ変換又はハール変換を用いて求められる、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記表現関数は、
複数の周波数係数の振幅を計算するステップと、
各係数とその次の係数との間の前記振幅の差分を求めるステップと
を用いて得られる、請求項５〜８のいずれか一項に記載の方法。
【請求項１１】
前記表現関数は、
複数の周波数係数の振幅の対数を計算するステップと、
各係数とその次の係数との間の前記振幅の前記対数の差分を求めるステップと
を用いて得られる、請求項５〜８のいずれか一項に記載の方法。
【請求項１２】
前記周波数係数は、フーリエ変換係数又はハール変換係数である、請求項１０又は１１に記載の方法。
【請求項１３】
前記方法は、バイナリ関数を導出することをさらに含み、
該バイナリ関数は、前記求められた各差分に閾値を適用することによって導出され、該差分が０未満である場合にはバイナリ値０を与え、該差分が０以上である場合にはバイナリ値１を与えることによって、一連のバイナリ値が導出される、
請求項１０〜１２のいずれか一項に記載の方法。
【請求項１４】
前記画像の表現は、複数の周波数成分の振幅に対して定義される関数の値、好ましくはバイナリ関数の値を含む、請求項１、２、３、又は６のいずれか一項に記載の方法。
【請求項１５】
２つ以上のそれぞれのサーカス関数を用いて２つ以上の表現を導出することと、
該２つ以上の表現を組み合わせることと
を含む、請求項１〜１４のいずれか一項に記載の方法。
【請求項１６】
前記組み合わせることは、前記２つ以上の表現を連結することを含む、請求項１５に記載の方法。
【請求項１７】
ｎ個の数字又はビットを有する表現を導出することを含み、
ｍ個の数字又はビットの部分集合を選択することをさらに含む、
請求項１〜１６のいずれか一項に記載の方法。
【請求項１８】
前記関数は、以下の関数：
【数１】
のうちの１つ又は複数を用いて導出される、請求項１〜１７のいずれか一項に記載の方法。
【請求項１９】
周波数成分を求める前に前記関数を正規化することを含む、請求項１〜１８のいずれか一項に記載の方法。
【請求項２０】
関連サーカス関数又は正規化されたサーカス関数を導出することを含む、請求項１９に記載の方法。
【請求項２１】
以下の関数：
【数２】
のうちの１つ又は複数を用いる、請求項２０に記載の方法。
【請求項２２】
画像を識別又は比較するための、請求項１〜２１のいずれか一項に記載の方法。
【請求項２３】
画像を識別する方法であって、
請求項１〜２２のいずれか一項に記載の方法を用いて該画像の表現を導出することと、
該表現を該画像と関連付けることと
を含む、画像を識別する方法。
【請求項２４】
画像を比較する方法であって、
請求項１〜２３のいずれか一項に記載の方法を用いて導出される各画像の表現を比較することを含む、画像を比較する方法。
【請求項２５】
前記比較は、次式：
【数３】
を用いてハミング距離を求めることを含み、
【数４】
は排他的ＯＲ（ＸＯＲ）演算子であり、Ｎは長さである、
請求項２４に記載の方法。
【請求項２６】
表現の前記比較に基づいて画像を選択することを含む、請求項２４又は２５に記載の方法。
【請求項２７】
請求項１〜２１のいずれか一項に記載の方法を用いて導出される表現の例えば送信又は受信を含む使用。
【請求項２８】
請求項１〜２６のいずれか一項に記載の方法を実行する装置。
【請求項２９】
請求項１〜２６のいずれか一項に記載の方法を実行するために前記装置の動作を制御する制御装置を備える、請求項２８に記載の装置。
【請求項３０】
画像及び／又は画像の表現を記憶する記憶手段、例えば画像データベース及び／又は記述子データベース、表示手段、並びに画像選択手段のうちの１つ又は複数をさらに備える、請求項２９に記載の装置。
【請求項３１】
請求項１〜２６のいずれか一項に記載の方法を実行するコンピュータプログラム、システム、又はコンピュータ読み取り可能な記憶媒体。
【図１ａ】
【図１ｂ】
【図１ｃ】
【図１ｄ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１ｂ】
【図１ｃ】
【図１ｄ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公表番号】特表２０１０−５０６３２３（Ｐ２０１０−５０６３２３Ａ）
【公表日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００９−５３１９１１（Ｐ２００９−５３１９１１）
【出願日】平成１９年１０月１１日（２００７．１０．１１）
【国際出願番号】ＰＣＴ／ＧＢ２００７／００３８５９
【国際公開番号】ＷＯ２００８／０４４０２６
【国際公開日】平成２０年４月１７日（２００８．４．１７）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
【公表日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願日】平成１９年１０月１１日（２００７．１０．１１）
【国際出願番号】ＰＣＴ／ＧＢ２００７／００３８５９
【国際公開番号】ＷＯ２００８／０４４０２６
【国際公開日】平成２０年４月１７日（２００８．４．１７）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
[ Back to top ]