高性能画像識別
画像の表現を導出する方法及び装置が記載される。本方法は、画像に対応する信号を処理することを含む。画像の２次元関数（少なくとも１つの汎関数Ｔを用いる画像のトレース変換（Ｔ（ｄ，θ））等）が、マスク関数（β）を用いて導出及び処理されて、画像の中間表現（１次元関数に対応する）が導出される。一実施形態では、マスク関数はトレース領域におけるトレース変換の画像帯の対を規定する。導出された１次元関数に既存の技法を適用することによって、画像の表現を導出することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の背景］
［発明の分野］
本発明は、画像を表現する方法及び装置に関し、さらに、例えば検索又は検証の目的のために画像を比較又は照合する方法及び装置に関する。
【背景技術】
【０００２】
［背景技術の説明］
本発明は、同時係属中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２（以下の参考文献［６］及び［７］）に開示されている画像識別技法に対する改良に関する。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の内容は参照により本明細書に援用される。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の発明及び実施の形態の詳細は、本発明及び本実施の形態にも同様に適用される。
【０００３】
欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に記載されている画像識別方法及び装置は、いずれも画像から短いバイナリ記述子を抽出するものであるが（図２参照）、従来技術の多くの欠点に対処しており、特に、
・特徴抽出及び照合の双方について計算複雑度が低減されていること、
・画像記述子のサイズが低減されていること、
・さまざまな画像変更に対するロバスト性が高められていること、並びに
・広範な画像変更に対して９８％を超える検出率を維持しながら誤報率が１ｐｐｍレベルに低減されていること、
を特徴とする。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、多くの実際の用途において、誤報率を１ｐｐｍよりも実質的に低くする必要があると共に、検出率が９８％を超えていることが望ましい。したがって、平均検出率を９８％超にまで高めることが望ましい。加えて、ヒストグラム等化及び画像クロッピング(image cropping)に対するロバスト性を向上させることが望ましい。
【課題を解決するための手段】
【０００５】
［発明のサマリー］
第１の態様によれば、本発明は、添付の特許請求の範囲の請求項１に定義されている、画像の表現を導出する方法を提供する。
【０００６】
本発明のさらなる態様は、本発明の第１の態様による方法を用いて導出される画像の表現の使用と、本発明の第１の態様による方法を実施する装置と、本発明の第１の態様による方法を実施するための命令を含むコンピュータ可読記憶媒体とを含む。
【０００７】
実施の形態の好ましい特徴及び任意選択の特徴は従属請求項に記載されている。
【０００８】
本発明は、画像のトレース変換(Trace transform)（又は画像の２次元関数であってこれと等価なもの）から視覚的な識別特徴を抽出する新規の方法に関する。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２（参照により本明細書に援用される）に記載されている方法は、トレース変換を中間表現として用いる。トレース変換は、画像上の全ての可能な線を射影し、トレース変換表現全体からバイナリ成分記述子が抽出され、次に互いに組み合わされる。
【０００９】
本発明は、１つ又は複数の表現（それぞれが画像内の可能な線のサブセットから構築される）を抽出することを含む。すなわち、中間表現から追加のバイナリ成分識別子が導出されると（後述）、トレース変換は空間的に限定される（マスクされる）。サブセット、又は複数のこのようなサブセットを用いて、画像の特定の部分に関連するさらなる識別情報を抽出することができる。この追加の識別情報を、欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の方法のような他の方法を用いて導出される画像全体の表現に追加することができる。この追加の情報を含むことによって画像識別性能及びロバスト性が著しく高まることが分かっている。さらに、代替的な前処理方法を用いて結果をさらに改善することができる。
【００１０】
本出願において、用語「汎関数(functional)」は、その通常の数学的意味を有する。特に、汎関数とは、ベクトル空間Ｖ上の（通常は関数の）実数値関数である。トレース変換の場合、汎関数は画像内の複数の線に適用される。
【００１１】
同時係属中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に記載されている方法では、トレース変換は、画像を直線でトレースすることによって計算され、該直線に沿って、画像の輝度関数または色関数の特定の汎関数Ｔが計算される。異なる複数の汎関数Ｔが用いられて単一の入力画像から異なる複数のトレース変換が生成される。２Ｄ平面において線は２つのパラメータ、すなわち角度θ及び距離ｄによって特徴付けられるため、画像のトレース変換は各トレース線のパラメータの２Ｄ関数である。次に、トレース変換の列に沿ってダイアメトリカル汎関数（diametrical functional）Ｐを適用することによって「サーカス関数（circus function）」が計算される。英国特許出願ＧＢ０７００４６８．２では、さらなる処理が実施され、該処理において、効率的に、画像が帯（図１１に示すもの）及び／又は２つの錐（図１２に示すもの）を用いてさらにトレースされて、サーカス関数が導出される画像のトレース変換の解像度が低減される。幅が異なる複数の帯及び／又は開口角が異なる複数の錐が用いられて、複数解像度の表現が得られる。各サーカス関数から、サーカス関数の周波数表現を（たとえばフーリエ変換によって）計算して、その周波数振幅成分に関して定義される特定の関数（たとえば、この関数は任意の２つの隣接する周波数振幅の大きさの差分とすることができる）の符号を取ることによって、成分バイナリ識別子が構築される。以下の参考文献［４］に開示されているように、帯及び／又は２つの錐と共に異なる汎関数を用いることによって得られる成分識別子「族」から選択される文字列断片を組み合わせて、単一の記述子にすることが可能である。
【００１２】
トレース変換領域内の帯及び錐に沿ってトレース変換値を暗黙的に計算することによって、記述子の抽出を非常に効率的に実施することができる。
【００１３】
本発明の一態様によれば、マスク関数が、トレース変換の空間的に限定された領域（たとえばトレース領域内の帯（band））を抽出し、これを用いて、追加のバイナリ記述子を抽出するサーカス関数を計算する。下記で説明するように、トレース領域内の帯は画像領域内の錐に対応する。同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に開示されている技法では、各成分バイナリ記述子は、画像に射影される全ての可能な線の表現を含むことが強調されるべきである。対照的に、本発明の一態様によれば、各成分記述子は、画像の選択された部分又は領域内の線の特定のサブセットに焦点を当て、それによって、さらなる独立したロバストな識別情報を提供する。この追加の成分識別子を従来技術の識別子に追加することによって、性能の非常に大きな改良を達成することができる。具体的には、ヒストグラム等化のような色を変更する変換、及び内容が変化する変更（特にクロッピング）に対するロバスト性が向上する。その上、一般的に、従来の技法と比較して十分の一に低減した０．１ｐｐｍという誤報率で平均検出率を９９．８０％にまで高めることができる。
【００１４】
本発明の別の態様によれば、抽出された円形の部分画像の境界にテーパリング（tapering）を追加してさらに性能を高めることができる。
【００１５】
添付図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【００１６】
【図１】（ａ）は画像を示す図であり、（ｂ）は（ａ）の画像を縮小したバージョンを示す図であり、（ｃ）は（ａ）の画像を回転させたバージョンを示す図であり、（ｄ）は（ａ）の画像をぼかしたバージョンを示す図であり、（ｅ）は（ａ）の画像を（左右に）反転させたバージョンを示す図であり、（ｆ）は（ａ）の画像を強く圧縮したバージョンを示す図であり、（ｇ）は（ａ）の画像をクロッピングしたバージョンを示す図である。
【図２】画像と、従来技術によるその画像のビットストリング表現とを示す図である。
【図３】本発明の一実施形態の方法のステップを示す図である。
【図４】サーカス関数からのバイナリ識別子の抽出を示す図である。
【図５】トレース変換のための線パラメータ化を示す図である。
【図６】（ａ）は画像を示す図であり、（ｂ）は（ａ）の画像のトレース変換を示す図であり、（ｃ）は（ａ）の画像のサーカス関数を示す図である。
【図７】（ａ）〜（ｃ）は、画像の異なるバージョンから導出される関数を示す図である。
【図８】本発明の一実施形態による装置のブロック図である。
【図９】複数のトレース変換を用いる一実施形態を示すブロック図である。
【図１０】図８の実施形態によって作成されるビットストリームを示す図である。
【図１１】トレース変換のｄパラメータを分解するときの原画像内の区間帯を示す図である。
【図１２】トレース変換のθパラメータを分解するときの原画像における２つの錐を示す図である。
【図１３】ｄパラメータにおけるトレース変換の分解を示す図である。
【図１４】θパラメータにおけるトレース変換の分解を示す図である。
【図１５】トレース領域における帯と画像領域における線との間の同等性を示す図である。
【図１６】トレース変換からの帯の１Ｄ表現の抽出を示す図である。
【発明を実施するための形態】
【００１７】
［実施形態の詳細な説明］
画像の表現（具体的には画像識別子）を導出すると共に、このような表現／識別子を（例えば、１つ又は複数の画像の識別、照合又は検証の目的で）用いるさまざまな実施形態を以下に記載する。本発明は画像の識別に特に有用であるが、これには限定されない。記載される実施形態では、「画像識別子」（又は単純に「識別子」）は画像の表現の一例であり、この用語は画像の表現、すなわち記述子を指すために用いられるに過ぎない。
【００１８】
当業者であれば、本発明の一実施形態による画像識別装置及び方法の具体的な設計詳細と、画像識別に用いる画像識別子の導出とは、画像識別子がロバストであるべき画像変更のタイプ、識別子のサイズ、抽出及び照合の複雑度、目標誤報率等に関連する要件によって決定されることを理解しよう。
【００１９】
以下の実施例は、画像に対する以下の変更（網羅的なリストではない）に対しロバストな識別子をもたらす一般的設計を示す。
・色数削減
・ぼかし
・明るさの変更
・反転（左右及び上下）
・グレースケール変換
・ヒストグラム等化
・ＪＰＥＧ圧縮
・ノイズ
・回転
・クロッピング
・拡大縮小
【００２０】
この一般的設計は通常、広範なクラスの画像に対して０．１百万分率（ｐｐｍ）を下回る非常に低い誤報率及び９９．８％の検出率を達成することができることが分かっている。
【００２１】
図１は、画像及びその画像を変更したバージョンの一例を示す。より具体的には、図１ａは原画像であり、図１ｂは図１ａの画像を縮小したバージョンであり、図１ｃは図１ａの画像を回転させたバージョンであり、図１ｄは図１ａの画像をぼかしたバージョンであり、図１ｅは図１ａの画像を反転させたバージョンであり、図１ｆは図１ａの画像を圧縮したバージョンであり、図１ｇは図１ａの画像をクロッピングしたバージョンである。
【００２２】
本発明の一実施形態は、画像に対応する信号を処理することによって、画像の表現、より具体的には画像識別子を導出する。通常、画像識別子は一例として図２に示すようなバイナリ識別子である。
【００２３】
図３は、本発明の一実施形態による画像識別子を導出する方法の各ステップ、すなわち識別子抽出工程を示す。
【００２４】
抽出の初期段階において任意選択で画像を前処理する。これは、画像をサイズ変更し（ステップ１１０）、フィルタリングする（ステップ１２０）ことによって行われる。サイズ変更ステップ１１０は、画像を処理前に正規化するために用いられる。フィルタリングステップ１２０は、エイリアシング等の効果を除去するためのフィルタリングを含み得、領域選択及びテーパリングも含み得る。好適な実施形態では、アスペクト比を維持しつつ画像を１９２×Ｎ又はＮ×１９２（ここで、Ｎ≧１９２）の解像度にサイズ変更する。別の実施形態では、画像を１９２×１９２の正方形にサイズ変更する。その後、画像は３×３ガウスカーネルによってローパスフィルタリングされる。画像の中央から円形の領域がさらなる処理のために抽出される。本発明の一態様によれば、この円形中央領域を抽出するときにテーパリングされたエッジを用いることによって性能が向上する。好適な実施形態は、７ピクセルのテーパサイズを用いる。前処理ステップは任意選択であり、上記の任意の組み合わせを含むことができる。
【００２５】
ステップ１３０において、画像のトレース変換
【００２６】
【数１】
【００２７】
を行う。図５に示すように、画像内の線がｄ及びθによってパラメータ化される。トレース変換は、全ての可能な線を画像に射影し、これらの線に汎関数Ｔを適用する。汎関数とは、ベクトル空間Ｖ上の（通常は関数の）実数値関数である。トレース変換の場合、画像内の複数の線に汎関数が適用される。図６ａのトレース変換の例を図６ｂに示す。ステップ１４０においてトレース変換の結果を分解して、その次元ｄ、θのいずれか又は双方におけるその解像度を低減することができる。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の方法では、後続のステップ１５０においてその後、トレース変換の各列にさらなる汎関数Ｐを適用して、実数値ベクトル（すなわち、１次元関数）を得る。この第２の汎関数Ｐはダイアメトリカル汎関数として知られ、結果として得られるベクトルはサーカス関数として知られる。図６ｃは、図６ａのサーカス関数の例を示す。第３の汎関数であるサーカス汎関数をサーカス関数に適用して、単一の数を得ることができるが、好適な実施形態ではこのステップは用いられない。この結果の特性は、これらの汎関数（トレース汎関数、ダイアメトリカル汎関数、サーカス汎関数）を適切に選択することによって制御することができる。画像及び対応するトレース変換の例を含むトレース変換の全詳細は、例えば、参照により本明細書に援用される以下の参考文献［１］に見ることができる。
【００２８】
図６は汎関数Ｔ
【００２９】
【数２】
【００３０】
…（１）
を用いて抽出される、画像のトレース変換
【００３１】
【数３】
【００３２】
、及びダイアメトリカル汎関数Ｐ
ｍａｘ（ξ（ｔ）） …（２）
を適用することによって得られるサーカス関数を示す。
【００３３】
図７は、サーカス関数が様々な画像処理操作によって受ける影響を示す。図７は、画像の様々な変形に対応するサーカス関数を示す。図７ａは原画像のサーカス関数であり、図７ｂはその画像を回転させたバージョンのサーカス関数であり、図７ｃはその画像をぼかしたバージョンのサーカス関数である。回転は関数をシフトさせる（と共にスケール変化を引き起こす）ことが分かる。
【００３４】
再び図３を参照して、本発明の一態様によれば、ステップ１５５を導入して、ステップ１５０によって抽出されるサーカス関数に対する代替として、帯サーカス関数（band-circus function）を得る。ステップ１５５は、以下で詳細に説明するように、値をトレース変換の一部分のみから選択及び処理することによって、トレース変換を画像の線のサブセットに限定する。
【００３５】
本発明の好適な一実施形態によって、図３に示すように、ステップ１６０〜１８０において周波数表現を介して帯サーカス関数（ブロック１５５の出力）からバイナリ識別子を抽出する。
【００３６】
同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２において説明されているように、上で挙げた画像の変更のほとんどに関して、汎関数Ｔ、Ｐを適切に選択すれば、画像ａのサーカス関数ｆ（ａ）は、変更された画像ａ’のサーカス関数ｆ（ａ’）がシフト又は（振幅が）拡大縮小されたバージョンに過ぎないことを示すことができる（以下の参考文献［１］の第３章を参照）。
ｆ（ａ’）＝κｆ（ａ−θ） …（３）
【００３７】
ここで、式（３）のフーリエ変換を行うことによって、次式が与えられる。
Ｆ（Φ）＝Ｆ［κｆ（ａ−θ）］ …（４）
＝κＦ［ｆ（ａ−θ）］ …（５）
＝κｅｘｐ-jθΦＦ［ｆ（ａ）］ …（６）
【００３８】
次に、式（６）の振幅を取ると次式が得られる。
｜Ｆ（Φ）｜＝｜κＦ［ｆ（ａ）］｜ …（７）
【００３９】
式（７）から、この時点では、変更された画像と原画像とに対応する周波数表現の振幅成分はスケーリング係数κを除いて同じであることが分かる。
【００４０】
図４は、フーリエ変換に対するバイナリ関数を定義する方法の一例を示す。具体的には、図３のステップ１７０においてフーリエ変換を得た後、ステップ１７３においてフーリエ変換の振幅の対数を得る。
【００４１】
一実施形態によれば、ここで、フーリエ変換の各振幅係数について関数ｃ（ω）が定義される。この関数の１つの例示は、隣接する係数同士の差分を取ることである（ステップ１７４）。
ｃ（ω）＝｜Ｆ（ω）｜−｜Ｆ（ω＋１）｜ …（８）
【００４２】
式（８）から結果として得られるベクトルに対し、ステップ１７５において、以下の式を満たすように閾値を適用することによって、バイナリストリングを抽出することができる。
【００４３】
【数４】
【００４４】
（すべてのωについて）
…（９）
Ｓに関する適切な選択は、Ｓ＝０及びＳ＝ｍｅａｎ（ｃ）を含む。次に、これらのバイナリストリング値Ｂ＝｛ｂ0，…，ｂn｝から画像識別子が構築される。
【００４５】
２つの異なる識別子Ｂ1及びＢ2（いずれも長さＮ）の間で識別子の照合を行うために、正規化ハミング距離を取る。
【００４６】
【数５】
【００４７】
…（１０）
ここで、
【００４８】
【数６】
【００４９】
は排他的ＯＲ（ＸＯＲ）演算子である。識別子又は表現の他の比較方法も用いることができる。
【００５０】
識別子中の特定のビットを選択することで、識別子サイズと、識別子性能と、ロバスト性との間の所望のトレードオフを達成することができる。より低い周波数に対応するビットは一般にロバスト性がより高く、より高いビットは識別性がより高い。以下の参考文献［３］において提示されている最適化を用いることによって、又は以下の参考文献［５］の従来技術の最適化方法のうちの１つを用いることによって、画像及びそれらの画像の変形の大規模なデータベースを用いて、ビットの選択を実験的に最適化することもできる。本発明の特定の一実施形態では、ＤＣ成分に対応する最初のビットｂ0を無視し、識別子は続く４８ビットから成る。
【００５１】
１つ又は複数のトレース汎関数を用いて複数のトレース変換を得ることによって、性能に対する改善を達成することができる。次に、１つ又は複数のダイアメトリカル汎関数を用いて複数のサーカス関数を得ることができる。各サーカス関数から、１つの「基本」バイナリ識別子を抽出することができる。次に、これらの基本識別子の各ビットを図９及び図１０に示すように組み合わせることができる。２つ以上の異なるサーカス関数３６１及び３６２からのバイナリストリングを組み合わせる具体的な方法は、それらを連結して識別子３６３を得ることである。
【００５２】
このようにして、上記の式（１）のトレース汎関数を、上記の式（２）によって与えられるダイアメトリカル汎関数と共に用いて１つのバイナリストリングを得、その後、（１）のトレース汎関数を以下のダイアメトリカル汎関数（１１）
【００５３】
【数７】
【００５４】
…（１１）
と共に用いて第２のストリングを得ることによって、良好な結果を得ることができる。各バイナリストリングの最初のビット（フーリエ変換のＤＣ成分に対応する）はスキップし、両方のストリングからの次の６４ビットを連結して１２８ビットの識別子を得る。
【００５５】
一実施形態では、トレース変換の複数解像度の表現を形成することによって、さらなる情報を抽出する。画像データの解像度を低減するための分解（たとえばトレース変換）を１次元又は２次元で行うことができる。次に、上記の同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２におけるように、ダイアメトリカル汎関数を適用して１つ又は複数の帯サーカス関数を得て、バイナリストリングを抽出する。
【００５６】
この複数解像度のトレース変換は、英国特許出願ＧＢ０７００４６８．２に詳細に記載されているように、その２つの次元ｄ若しくはθのうちのいずれか又は双方の次元において元のトレース変換をサブサンプリングすることによって生成することができる。「トレース領域」においてｄパラメータのサブサンプリングは、図１３のように列に沿って複数の区間にわたって積分することによって行われる。これは、図１１に示されるように、トレース変換中に幅Δｄの帯を画像に射影することに対応する。サブサンプリングは、θパラメータにおける複数の区間にわたって、すなわち行に沿って積分することによって行うこともできる。図１４を参照されたい。これは、トレース変換中に開口角Δθを有する２つの錐にわたって積分することとほぼ同じである。図１２を参照されたい。代替的に、これらの演算を画像領域において行うことができる。
【００５７】
同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に開示されているような、ステップ１５０を有する図３の方法を用いて、複数解像度分解を用いることによって、１つのトレース変換から複数の基本識別子を抽出することができる。ここで、或る範囲内の異なる区間幅にわたってサブサンプリングが行われて、複数解像度の表現が生成される。トレース変換の出力のサイズが６００×３８４であり、さらに、ｄパラメータが幅１、８、１６、３２、６４及び１２８である帯を用いて積分することによってサブサンプリングされるシステムを用い、かつ、例えば式（２）及び（１１）において定義されるようなダイアメトリカル汎関数を適用して１２個のサーカス関数を得ることによって、良好な結果が得られた。このような組み合わせは、１ｐｐｍの誤受入率で９８％の検出を与える。
【００５８】
それにもかかわらず、多くの用途は９８％を超える検出率で１ｐｐｍを下回るより低い誤受入率を要求する。本発明のある実施態様（以下でより詳細に説明する）は、０．１ｐｐｍを下回る誤受入率で９９．８％を超える検出率を提供することを実験的に示している。
【００５９】
上記で説明したように、同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２において提示されている識別子は、全ての可能な線を画像に射影し、次にこの情報を１Ｄに射影することによって抽出される。本発明の実施の形態によって開示される表現は、線のサブセットのみを用いて、画像の複数の代替的な１Ｄ表現を形成する。
【００６０】
具体的には、画像全体にわたる線のうちのサブセットから識別子を抽出するために、画像全体にわたる線のうちのサブセットの２次元関数（特にトレース変換）の値を１Ｄにマッピングするサーカス関数の等価物（「サーカス帯関数（circus-band function）」と名づけられる）が定義される。したがって、サーカス帯関数は識別子の抽出を画像の一部分に効率的に限定する。これは、画像全体のトレース変換の一部分を選択し、選択された部分内のトレース変換の値を用いて画像識別子を導出することによって達成される。
【００６１】
一実施形態では、トレース変換の選択される部分は距離パラメータｄに対する範囲（ｕ0≦ｄ≦ｕ1）によって規定される。図１５（ａ）に示すように、これは、トレース領域において角度パラメータθの全ての値にわたって延在する水平帯（ｕ0，ｕ1）（帯Ａ）に対応する。水平帯を複数の断片（それぞれがトレース領域におけるθに対する或る範囲の値に対応する）に分割することができる。帯Ａの各断片は、画像領域における対応する２つの錐の領域（図１５（ｂ）に示す）の頂点を通じて延在する全ての線と等価である。したがって、図１５（ａ）内の帯Ａの明るい／暗い灰色の陰影をつけた断片は、図１５（ｂ）の上半分内の明るい／暗い灰色の陰影をつけた領域に対応する。
【００６２】
効率のために、好適な実施の形態では、トレース変換は０〜π（０度〜１８０度）の角度θにわたってのみ行われることに留意されたい。したがって、回転不変性を維持するために、帯を、距離パラメータｄに関して水平中心線（すなわち中心値）（図１５（ａ）及び図１５（ｂ）における、ｄ＝０に対応する中心線）を中心とする対にする必要がある。図１５（ａ）に示すように、帯Ａと帯Ｂとが対にされ、図１５（ａ）内の帯Ｂの明るい／暗い灰色の陰影をつけた断片が図１５（ｂ）の下半分内の明るい／暗い灰色の陰影をつけた領域に対応する。図１５（ｃ）は同様に、トレース領域における対となる帯Ｃ及びＤを示し、これらは中心線値から、また画像領域における対応する２つの錐から、等距離に離間しており、例示のために断片に陰影をつけてある。
【００６３】
一実施形態では、帯の対が組み合わされて、汎関数Ｇが用いられて、帯サーカス関数として知られている１Ｄ関数ｇ（θ）にこれらがマッピングされる。トレース変換
【００６４】
【数８】
【００６５】
と以下のように定義されるマスク関数βとを乗算することによって帯サーカス関数ｇ（θ）を得ることができる。
【００６６】
【数９】
【００６７】
…（１２）
ここで、
【００６８】
【数１０】
【００６９】
…（１３）
式（１２）において、Ｇはトレース変換の抽出された帯のｄパラメータに沿って演算する汎関数である。式（１３）内の２つの値ｕ0及びｕ1は、帯の位置及び幅を規定する。差分ｕ1−ｕ0が大きくなるほど、帯が太くなる。
【００７０】
帯サーカス関数ｇ（θ）のより低い解像度の記述を、図１６に示すような角度（θ）における分解によって得ることができる。この分解は、画像領域に２つの錐を取ることに対応する。分解は好ましくは、幅Δθの区間にわたる積分であり、これは、画像データの解像度を低減できる該区間にわたる任意の適切な汎関数とすることもできる。
【００７１】
バイナリ表現を抽出するために、式（４）〜（９）によって記述されているもの（図３のステップ１６０〜１８０に対応する）と同じ技法を、帯サーカス関数ｇ（θ）及び／又はその分解したバージョンに適用することができる。本発明の好適な一実施形態は、トレース変換から５対の帯を抽出し、１対は中心線（距離パラメータについての中心値）にわたるものであり、４対は残りのパラメータ空間の中央半分にわたって均等に分散される。これらの帯の幅はトレース領域において２ピクセルであり、汎関数Ｇは式（１）で与えられる。得られた５つの帯サーカス関数が分解され、角度次元において解像度が係数６で低減されて、最終的な５つの帯サーカス関数が得られる。最終的な５つの帯サーカス関数から抽出される「基本」識別子と、複数解像度のトレース変換からの１２個の識別子とを組み合わせて、画像のための完全な識別子（１７個の基本識別子を含む）を形成することによって、高い性能が得られる。
【００７２】
上記の方法を行う、本発明の一実施形態による、本発明の応用のための装置の一例を図８に示す。該応用は、データベース２３０内に記憶されている画像のための識別子データベース２４０を構築することを含む。２つのデータベース２３０及び２４０は同じデータベースであってもよいし、又は別個のデータベースであってもよい。本装置は、問い合わせ画像２５０から抽出される識別子２６０を検索して、データベース内で一致するものを見つけることを可能にする。画像リスト（おそらくは順序付けされされたもの）がユーザ２９０又は問い合わせアプリケーションに返される。
【００７３】
この識別子の１つの具体的な応用は、画像検索エンジンとしての応用である。バイナリ識別子を抽出し、関連する情報（ファイル名、画像、撮影者、取得日時、及び任意の他の有用な情報等）と共に記憶することによって、データベースが構築される。次に、問い合わせ画像ａqが与えられると、バイナリ識別子が抽出され、データベース中の全ての識別子Ｂ0…ＢMと比較される。問い合わせ画像に対するハミング距離が閾値未満である全ての画像が返される。
【００７４】
［代替的な実施態様］
様々な異なるトレース汎関数及びダイアメトリカル汎関数を用いることができ、例として以下が挙げられる（網羅的でないリスト）。
【００７５】
【数１１】
【００７６】
バイナリ識別子の異なる組み合わせを組み合わせて、複雑度と、ロバスト性と、記述子サイズとの間の最適なトレードオフを提供することができる。トレース汎関数、ダイアメトリカル汎関数、分解、及び帯を変更することによって、代替的なバイナリ識別子を抽出することができる。
【００７７】
式（１３）によって与えられるマスク関数βは、マスク関数に対する１つの可能性に過ぎない。ｄ及びθの他の関数を用いて、さらなる情報を抽出できる線の代替的サブセットを抽出することができる。
【００７８】
回転、平行移動及び拡大縮小より高次の幾何変換の場合、上述した識別子のバージョンは適切でなく、式（３）の関係は成り立たない。識別子のロバスト性は、正規化工程を用いるアフィン変換まで拡張することができる。この正規化工程の全詳細は、以下の参考文献［２］に見ることができる。サーカス関数を正規化するために２つのステップが導入される。１番目のステップは、いわゆる関連サーカス（associated circus）を求めることを含み、２番目のステップは、正規化された関連サーカス関数を求めることを含む。この正規化に続き、式（３）の関係が真であることが示される。これによって、上記と同様に識別子の抽出工程を継続することができる。
【００７９】
正規化工程と共に用いられるいくつかの適切なトレース汎関数が以下の（Ｇ１）及び（Ｇ２）に与えられ、ダイアメトリカル汎関数の適切な選択が（Ｇ３）に与えられる。
【００８０】
【数１２】
【００８１】
ここで、ｒ≡ｔ−ｃであり、ｃ≡ｍｅｄｉａｎ（｛ｔk｝k，｛｜ｇ（ｔk）｜｝k）である。非負の重みｗ1，ｗ2，…，ｗnを有する数列ｙ1，ｙ2，…，ｙnの加重中央値を、この数列が重みによって昇順でソートされると仮定した場合に次式が成り立つ最大のインデックスｍを特定することによって定義する。
【００８２】
【数１３】
【００８３】
…（１４）
不等式（１４）の不等号が厳密な不等号である場合、中央値はｙmとなる。しかし、この不等式の等号が成り立つ場合、中央値は（ｙm＋ｙm-1）／２となる。
【００８４】
上記で示したように、パラメータ（ｄ又はθ）の複数の区間にわたって総和をとることによって、トレース変換における複数解像度分解を形成することができる。総和をとることは必須ではなく、他の可能性は、平均値、最大値、最小値等のような統計値を含む。他の汎関数をこれらの区間に適用することもできる。
【００８５】
汎関数Ｇは式（１）に限定されず、代替的な汎関数を用いることが可能である。異なる複数の値で分解することによって単一の帯から複数の識別子を抽出することができる。好適な実施形態では係数６が用いられたが、他の係数を用いて代替的な識別子を生成してもよい。トレース変換の中心付近の帯が、クロッピングに対する良好なロバスト性を有することが実験によって分かっている。
【００８６】
識別子に構造を適用して検索性能を高めることもできる。例えば、２パス探索を実施し、１回目の探索に半分のビットを用い、次に所与のレベルの精度を有するもののみを２回目の探索パスに認める。
【００８７】
リード・マラー（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)
［３］Paul Brasnett及びMiroslaw Boder著「A Robust Visual Identifier Using the Trace Transform」（Int. Conf. on Visual Information Eng. 2007 (VIE2007), ２００７年７月, 2007）
［４］Paul Brasnett及びMiroslaw Boder著「Multi-Resolution Trace Transform for Image Identification」（IEEE Int. Conf. on Computer Vision (ICCV 2007), ２００７年１０月）、提出済み
［５］Handbook of Global Optimization, Ed. P. M. Pardalos and H. E. Romeijn, Springer 2002
【００９９】
当業者であれば理解するように、説明した実施形態に対して多くの変形及び変更を行うことができる。例えば、本発明を、上記に記載した参考文献において教示されているもののような他の既存の技法及び関連技法を組み合わせて実施する実施形態において実施することができる。そのような既存の技法及び関連技法の組み合わせは当業者には容易に明らかとなり、本発明の範囲に入る、全てのそのような組み合わせ、並びに説明した実施形態に対する全てのそのような変更及び均等物を含むことが意図される。
【技術分野】
【０００１】
［発明の背景］
［発明の分野］
本発明は、画像を表現する方法及び装置に関し、さらに、例えば検索又は検証の目的のために画像を比較又は照合する方法及び装置に関する。
【背景技術】
【０００２】
［背景技術の説明］
本発明は、同時係属中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２（以下の参考文献［６］及び［７］）に開示されている画像識別技法に対する改良に関する。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の内容は参照により本明細書に援用される。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の発明及び実施の形態の詳細は、本発明及び本実施の形態にも同様に適用される。
【０００３】
欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に記載されている画像識別方法及び装置は、いずれも画像から短いバイナリ記述子を抽出するものであるが（図２参照）、従来技術の多くの欠点に対処しており、特に、
・特徴抽出及び照合の双方について計算複雑度が低減されていること、
・画像記述子のサイズが低減されていること、
・さまざまな画像変更に対するロバスト性が高められていること、並びに
・広範な画像変更に対して９８％を超える検出率を維持しながら誤報率が１ｐｐｍレベルに低減されていること、
を特徴とする。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、多くの実際の用途において、誤報率を１ｐｐｍよりも実質的に低くする必要があると共に、検出率が９８％を超えていることが望ましい。したがって、平均検出率を９８％超にまで高めることが望ましい。加えて、ヒストグラム等化及び画像クロッピング(image cropping)に対するロバスト性を向上させることが望ましい。
【課題を解決するための手段】
【０００５】
［発明のサマリー］
第１の態様によれば、本発明は、添付の特許請求の範囲の請求項１に定義されている、画像の表現を導出する方法を提供する。
【０００６】
本発明のさらなる態様は、本発明の第１の態様による方法を用いて導出される画像の表現の使用と、本発明の第１の態様による方法を実施する装置と、本発明の第１の態様による方法を実施するための命令を含むコンピュータ可読記憶媒体とを含む。
【０００７】
実施の形態の好ましい特徴及び任意選択の特徴は従属請求項に記載されている。
【０００８】
本発明は、画像のトレース変換(Trace transform)（又は画像の２次元関数であってこれと等価なもの）から視覚的な識別特徴を抽出する新規の方法に関する。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２（参照により本明細書に援用される）に記載されている方法は、トレース変換を中間表現として用いる。トレース変換は、画像上の全ての可能な線を射影し、トレース変換表現全体からバイナリ成分記述子が抽出され、次に互いに組み合わされる。
【０００９】
本発明は、１つ又は複数の表現（それぞれが画像内の可能な線のサブセットから構築される）を抽出することを含む。すなわち、中間表現から追加のバイナリ成分識別子が導出されると（後述）、トレース変換は空間的に限定される（マスクされる）。サブセット、又は複数のこのようなサブセットを用いて、画像の特定の部分に関連するさらなる識別情報を抽出することができる。この追加の識別情報を、欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の方法のような他の方法を用いて導出される画像全体の表現に追加することができる。この追加の情報を含むことによって画像識別性能及びロバスト性が著しく高まることが分かっている。さらに、代替的な前処理方法を用いて結果をさらに改善することができる。
【００１０】
本出願において、用語「汎関数(functional)」は、その通常の数学的意味を有する。特に、汎関数とは、ベクトル空間Ｖ上の（通常は関数の）実数値関数である。トレース変換の場合、汎関数は画像内の複数の線に適用される。
【００１１】
同時係属中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に記載されている方法では、トレース変換は、画像を直線でトレースすることによって計算され、該直線に沿って、画像の輝度関数または色関数の特定の汎関数Ｔが計算される。異なる複数の汎関数Ｔが用いられて単一の入力画像から異なる複数のトレース変換が生成される。２Ｄ平面において線は２つのパラメータ、すなわち角度θ及び距離ｄによって特徴付けられるため、画像のトレース変換は各トレース線のパラメータの２Ｄ関数である。次に、トレース変換の列に沿ってダイアメトリカル汎関数（diametrical functional）Ｐを適用することによって「サーカス関数（circus function）」が計算される。英国特許出願ＧＢ０７００４６８．２では、さらなる処理が実施され、該処理において、効率的に、画像が帯（図１１に示すもの）及び／又は２つの錐（図１２に示すもの）を用いてさらにトレースされて、サーカス関数が導出される画像のトレース変換の解像度が低減される。幅が異なる複数の帯及び／又は開口角が異なる複数の錐が用いられて、複数解像度の表現が得られる。各サーカス関数から、サーカス関数の周波数表現を（たとえばフーリエ変換によって）計算して、その周波数振幅成分に関して定義される特定の関数（たとえば、この関数は任意の２つの隣接する周波数振幅の大きさの差分とすることができる）の符号を取ることによって、成分バイナリ識別子が構築される。以下の参考文献［４］に開示されているように、帯及び／又は２つの錐と共に異なる汎関数を用いることによって得られる成分識別子「族」から選択される文字列断片を組み合わせて、単一の記述子にすることが可能である。
【００１２】
トレース変換領域内の帯及び錐に沿ってトレース変換値を暗黙的に計算することによって、記述子の抽出を非常に効率的に実施することができる。
【００１３】
本発明の一態様によれば、マスク関数が、トレース変換の空間的に限定された領域（たとえばトレース領域内の帯（band））を抽出し、これを用いて、追加のバイナリ記述子を抽出するサーカス関数を計算する。下記で説明するように、トレース領域内の帯は画像領域内の錐に対応する。同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に開示されている技法では、各成分バイナリ記述子は、画像に射影される全ての可能な線の表現を含むことが強調されるべきである。対照的に、本発明の一態様によれば、各成分記述子は、画像の選択された部分又は領域内の線の特定のサブセットに焦点を当て、それによって、さらなる独立したロバストな識別情報を提供する。この追加の成分識別子を従来技術の識別子に追加することによって、性能の非常に大きな改良を達成することができる。具体的には、ヒストグラム等化のような色を変更する変換、及び内容が変化する変更（特にクロッピング）に対するロバスト性が向上する。その上、一般的に、従来の技法と比較して十分の一に低減した０．１ｐｐｍという誤報率で平均検出率を９９．８０％にまで高めることができる。
【００１４】
本発明の別の態様によれば、抽出された円形の部分画像の境界にテーパリング（tapering）を追加してさらに性能を高めることができる。
【００１５】
添付図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【００１６】
【図１】（ａ）は画像を示す図であり、（ｂ）は（ａ）の画像を縮小したバージョンを示す図であり、（ｃ）は（ａ）の画像を回転させたバージョンを示す図であり、（ｄ）は（ａ）の画像をぼかしたバージョンを示す図であり、（ｅ）は（ａ）の画像を（左右に）反転させたバージョンを示す図であり、（ｆ）は（ａ）の画像を強く圧縮したバージョンを示す図であり、（ｇ）は（ａ）の画像をクロッピングしたバージョンを示す図である。
【図２】画像と、従来技術によるその画像のビットストリング表現とを示す図である。
【図３】本発明の一実施形態の方法のステップを示す図である。
【図４】サーカス関数からのバイナリ識別子の抽出を示す図である。
【図５】トレース変換のための線パラメータ化を示す図である。
【図６】（ａ）は画像を示す図であり、（ｂ）は（ａ）の画像のトレース変換を示す図であり、（ｃ）は（ａ）の画像のサーカス関数を示す図である。
【図７】（ａ）〜（ｃ）は、画像の異なるバージョンから導出される関数を示す図である。
【図８】本発明の一実施形態による装置のブロック図である。
【図９】複数のトレース変換を用いる一実施形態を示すブロック図である。
【図１０】図８の実施形態によって作成されるビットストリームを示す図である。
【図１１】トレース変換のｄパラメータを分解するときの原画像内の区間帯を示す図である。
【図１２】トレース変換のθパラメータを分解するときの原画像における２つの錐を示す図である。
【図１３】ｄパラメータにおけるトレース変換の分解を示す図である。
【図１４】θパラメータにおけるトレース変換の分解を示す図である。
【図１５】トレース領域における帯と画像領域における線との間の同等性を示す図である。
【図１６】トレース変換からの帯の１Ｄ表現の抽出を示す図である。
【発明を実施するための形態】
【００１７】
［実施形態の詳細な説明］
画像の表現（具体的には画像識別子）を導出すると共に、このような表現／識別子を（例えば、１つ又は複数の画像の識別、照合又は検証の目的で）用いるさまざまな実施形態を以下に記載する。本発明は画像の識別に特に有用であるが、これには限定されない。記載される実施形態では、「画像識別子」（又は単純に「識別子」）は画像の表現の一例であり、この用語は画像の表現、すなわち記述子を指すために用いられるに過ぎない。
【００１８】
当業者であれば、本発明の一実施形態による画像識別装置及び方法の具体的な設計詳細と、画像識別に用いる画像識別子の導出とは、画像識別子がロバストであるべき画像変更のタイプ、識別子のサイズ、抽出及び照合の複雑度、目標誤報率等に関連する要件によって決定されることを理解しよう。
【００１９】
以下の実施例は、画像に対する以下の変更（網羅的なリストではない）に対しロバストな識別子をもたらす一般的設計を示す。
・色数削減
・ぼかし
・明るさの変更
・反転（左右及び上下）
・グレースケール変換
・ヒストグラム等化
・ＪＰＥＧ圧縮
・ノイズ
・回転
・クロッピング
・拡大縮小
【００２０】
この一般的設計は通常、広範なクラスの画像に対して０．１百万分率（ｐｐｍ）を下回る非常に低い誤報率及び９９．８％の検出率を達成することができることが分かっている。
【００２１】
図１は、画像及びその画像を変更したバージョンの一例を示す。より具体的には、図１ａは原画像であり、図１ｂは図１ａの画像を縮小したバージョンであり、図１ｃは図１ａの画像を回転させたバージョンであり、図１ｄは図１ａの画像をぼかしたバージョンであり、図１ｅは図１ａの画像を反転させたバージョンであり、図１ｆは図１ａの画像を圧縮したバージョンであり、図１ｇは図１ａの画像をクロッピングしたバージョンである。
【００２２】
本発明の一実施形態は、画像に対応する信号を処理することによって、画像の表現、より具体的には画像識別子を導出する。通常、画像識別子は一例として図２に示すようなバイナリ識別子である。
【００２３】
図３は、本発明の一実施形態による画像識別子を導出する方法の各ステップ、すなわち識別子抽出工程を示す。
【００２４】
抽出の初期段階において任意選択で画像を前処理する。これは、画像をサイズ変更し（ステップ１１０）、フィルタリングする（ステップ１２０）ことによって行われる。サイズ変更ステップ１１０は、画像を処理前に正規化するために用いられる。フィルタリングステップ１２０は、エイリアシング等の効果を除去するためのフィルタリングを含み得、領域選択及びテーパリングも含み得る。好適な実施形態では、アスペクト比を維持しつつ画像を１９２×Ｎ又はＮ×１９２（ここで、Ｎ≧１９２）の解像度にサイズ変更する。別の実施形態では、画像を１９２×１９２の正方形にサイズ変更する。その後、画像は３×３ガウスカーネルによってローパスフィルタリングされる。画像の中央から円形の領域がさらなる処理のために抽出される。本発明の一態様によれば、この円形中央領域を抽出するときにテーパリングされたエッジを用いることによって性能が向上する。好適な実施形態は、７ピクセルのテーパサイズを用いる。前処理ステップは任意選択であり、上記の任意の組み合わせを含むことができる。
【００２５】
ステップ１３０において、画像のトレース変換
【００２６】
【数１】
【００２７】
を行う。図５に示すように、画像内の線がｄ及びθによってパラメータ化される。トレース変換は、全ての可能な線を画像に射影し、これらの線に汎関数Ｔを適用する。汎関数とは、ベクトル空間Ｖ上の（通常は関数の）実数値関数である。トレース変換の場合、画像内の複数の線に汎関数が適用される。図６ａのトレース変換の例を図６ｂに示す。ステップ１４０においてトレース変換の結果を分解して、その次元ｄ、θのいずれか又は双方におけるその解像度を低減することができる。欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２の方法では、後続のステップ１５０においてその後、トレース変換の各列にさらなる汎関数Ｐを適用して、実数値ベクトル（すなわち、１次元関数）を得る。この第２の汎関数Ｐはダイアメトリカル汎関数として知られ、結果として得られるベクトルはサーカス関数として知られる。図６ｃは、図６ａのサーカス関数の例を示す。第３の汎関数であるサーカス汎関数をサーカス関数に適用して、単一の数を得ることができるが、好適な実施形態ではこのステップは用いられない。この結果の特性は、これらの汎関数（トレース汎関数、ダイアメトリカル汎関数、サーカス汎関数）を適切に選択することによって制御することができる。画像及び対応するトレース変換の例を含むトレース変換の全詳細は、例えば、参照により本明細書に援用される以下の参考文献［１］に見ることができる。
【００２８】
図６は汎関数Ｔ
【００２９】
【数２】
【００３０】
…（１）
を用いて抽出される、画像のトレース変換
【００３１】
【数３】
【００３２】
、及びダイアメトリカル汎関数Ｐ
ｍａｘ（ξ（ｔ）） …（２）
を適用することによって得られるサーカス関数を示す。
【００３３】
図７は、サーカス関数が様々な画像処理操作によって受ける影響を示す。図７は、画像の様々な変形に対応するサーカス関数を示す。図７ａは原画像のサーカス関数であり、図７ｂはその画像を回転させたバージョンのサーカス関数であり、図７ｃはその画像をぼかしたバージョンのサーカス関数である。回転は関数をシフトさせる（と共にスケール変化を引き起こす）ことが分かる。
【００３４】
再び図３を参照して、本発明の一態様によれば、ステップ１５５を導入して、ステップ１５０によって抽出されるサーカス関数に対する代替として、帯サーカス関数（band-circus function）を得る。ステップ１５５は、以下で詳細に説明するように、値をトレース変換の一部分のみから選択及び処理することによって、トレース変換を画像の線のサブセットに限定する。
【００３５】
本発明の好適な一実施形態によって、図３に示すように、ステップ１６０〜１８０において周波数表現を介して帯サーカス関数（ブロック１５５の出力）からバイナリ識別子を抽出する。
【００３６】
同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２において説明されているように、上で挙げた画像の変更のほとんどに関して、汎関数Ｔ、Ｐを適切に選択すれば、画像ａのサーカス関数ｆ（ａ）は、変更された画像ａ’のサーカス関数ｆ（ａ’）がシフト又は（振幅が）拡大縮小されたバージョンに過ぎないことを示すことができる（以下の参考文献［１］の第３章を参照）。
ｆ（ａ’）＝κｆ（ａ−θ） …（３）
【００３７】
ここで、式（３）のフーリエ変換を行うことによって、次式が与えられる。
Ｆ（Φ）＝Ｆ［κｆ（ａ−θ）］ …（４）
＝κＦ［ｆ（ａ−θ）］ …（５）
＝κｅｘｐ-jθΦＦ［ｆ（ａ）］ …（６）
【００３８】
次に、式（６）の振幅を取ると次式が得られる。
｜Ｆ（Φ）｜＝｜κＦ［ｆ（ａ）］｜ …（７）
【００３９】
式（７）から、この時点では、変更された画像と原画像とに対応する周波数表現の振幅成分はスケーリング係数κを除いて同じであることが分かる。
【００４０】
図４は、フーリエ変換に対するバイナリ関数を定義する方法の一例を示す。具体的には、図３のステップ１７０においてフーリエ変換を得た後、ステップ１７３においてフーリエ変換の振幅の対数を得る。
【００４１】
一実施形態によれば、ここで、フーリエ変換の各振幅係数について関数ｃ（ω）が定義される。この関数の１つの例示は、隣接する係数同士の差分を取ることである（ステップ１７４）。
ｃ（ω）＝｜Ｆ（ω）｜−｜Ｆ（ω＋１）｜ …（８）
【００４２】
式（８）から結果として得られるベクトルに対し、ステップ１７５において、以下の式を満たすように閾値を適用することによって、バイナリストリングを抽出することができる。
【００４３】
【数４】
【００４４】
（すべてのωについて）
…（９）
Ｓに関する適切な選択は、Ｓ＝０及びＳ＝ｍｅａｎ（ｃ）を含む。次に、これらのバイナリストリング値Ｂ＝｛ｂ0，…，ｂn｝から画像識別子が構築される。
【００４５】
２つの異なる識別子Ｂ1及びＢ2（いずれも長さＮ）の間で識別子の照合を行うために、正規化ハミング距離を取る。
【００４６】
【数５】
【００４７】
…（１０）
ここで、
【００４８】
【数６】
【００４９】
は排他的ＯＲ（ＸＯＲ）演算子である。識別子又は表現の他の比較方法も用いることができる。
【００５０】
識別子中の特定のビットを選択することで、識別子サイズと、識別子性能と、ロバスト性との間の所望のトレードオフを達成することができる。より低い周波数に対応するビットは一般にロバスト性がより高く、より高いビットは識別性がより高い。以下の参考文献［３］において提示されている最適化を用いることによって、又は以下の参考文献［５］の従来技術の最適化方法のうちの１つを用いることによって、画像及びそれらの画像の変形の大規模なデータベースを用いて、ビットの選択を実験的に最適化することもできる。本発明の特定の一実施形態では、ＤＣ成分に対応する最初のビットｂ0を無視し、識別子は続く４８ビットから成る。
【００５１】
１つ又は複数のトレース汎関数を用いて複数のトレース変換を得ることによって、性能に対する改善を達成することができる。次に、１つ又は複数のダイアメトリカル汎関数を用いて複数のサーカス関数を得ることができる。各サーカス関数から、１つの「基本」バイナリ識別子を抽出することができる。次に、これらの基本識別子の各ビットを図９及び図１０に示すように組み合わせることができる。２つ以上の異なるサーカス関数３６１及び３６２からのバイナリストリングを組み合わせる具体的な方法は、それらを連結して識別子３６３を得ることである。
【００５２】
このようにして、上記の式（１）のトレース汎関数を、上記の式（２）によって与えられるダイアメトリカル汎関数と共に用いて１つのバイナリストリングを得、その後、（１）のトレース汎関数を以下のダイアメトリカル汎関数（１１）
【００５３】
【数７】
【００５４】
…（１１）
と共に用いて第２のストリングを得ることによって、良好な結果を得ることができる。各バイナリストリングの最初のビット（フーリエ変換のＤＣ成分に対応する）はスキップし、両方のストリングからの次の６４ビットを連結して１２８ビットの識別子を得る。
【００５５】
一実施形態では、トレース変換の複数解像度の表現を形成することによって、さらなる情報を抽出する。画像データの解像度を低減するための分解（たとえばトレース変換）を１次元又は２次元で行うことができる。次に、上記の同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２におけるように、ダイアメトリカル汎関数を適用して１つ又は複数の帯サーカス関数を得て、バイナリストリングを抽出する。
【００５６】
この複数解像度のトレース変換は、英国特許出願ＧＢ０７００４６８．２に詳細に記載されているように、その２つの次元ｄ若しくはθのうちのいずれか又は双方の次元において元のトレース変換をサブサンプリングすることによって生成することができる。「トレース領域」においてｄパラメータのサブサンプリングは、図１３のように列に沿って複数の区間にわたって積分することによって行われる。これは、図１１に示されるように、トレース変換中に幅Δｄの帯を画像に射影することに対応する。サブサンプリングは、θパラメータにおける複数の区間にわたって、すなわち行に沿って積分することによって行うこともできる。図１４を参照されたい。これは、トレース変換中に開口角Δθを有する２つの錐にわたって積分することとほぼ同じである。図１２を参照されたい。代替的に、これらの演算を画像領域において行うことができる。
【００５７】
同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２に開示されているような、ステップ１５０を有する図３の方法を用いて、複数解像度分解を用いることによって、１つのトレース変換から複数の基本識別子を抽出することができる。ここで、或る範囲内の異なる区間幅にわたってサブサンプリングが行われて、複数解像度の表現が生成される。トレース変換の出力のサイズが６００×３８４であり、さらに、ｄパラメータが幅１、８、１６、３２、６４及び１２８である帯を用いて積分することによってサブサンプリングされるシステムを用い、かつ、例えば式（２）及び（１１）において定義されるようなダイアメトリカル汎関数を適用して１２個のサーカス関数を得ることによって、良好な結果が得られた。このような組み合わせは、１ｐｐｍの誤受入率で９８％の検出を与える。
【００５８】
それにもかかわらず、多くの用途は９８％を超える検出率で１ｐｐｍを下回るより低い誤受入率を要求する。本発明のある実施態様（以下でより詳細に説明する）は、０．１ｐｐｍを下回る誤受入率で９９．８％を超える検出率を提供することを実験的に示している。
【００５９】
上記で説明したように、同時継続中の欧州特許出願ＥＰ０６２５５２３９．３及び英国特許出願ＧＢ０７００４６８．２において提示されている識別子は、全ての可能な線を画像に射影し、次にこの情報を１Ｄに射影することによって抽出される。本発明の実施の形態によって開示される表現は、線のサブセットのみを用いて、画像の複数の代替的な１Ｄ表現を形成する。
【００６０】
具体的には、画像全体にわたる線のうちのサブセットから識別子を抽出するために、画像全体にわたる線のうちのサブセットの２次元関数（特にトレース変換）の値を１Ｄにマッピングするサーカス関数の等価物（「サーカス帯関数（circus-band function）」と名づけられる）が定義される。したがって、サーカス帯関数は識別子の抽出を画像の一部分に効率的に限定する。これは、画像全体のトレース変換の一部分を選択し、選択された部分内のトレース変換の値を用いて画像識別子を導出することによって達成される。
【００６１】
一実施形態では、トレース変換の選択される部分は距離パラメータｄに対する範囲（ｕ0≦ｄ≦ｕ1）によって規定される。図１５（ａ）に示すように、これは、トレース領域において角度パラメータθの全ての値にわたって延在する水平帯（ｕ0，ｕ1）（帯Ａ）に対応する。水平帯を複数の断片（それぞれがトレース領域におけるθに対する或る範囲の値に対応する）に分割することができる。帯Ａの各断片は、画像領域における対応する２つの錐の領域（図１５（ｂ）に示す）の頂点を通じて延在する全ての線と等価である。したがって、図１５（ａ）内の帯Ａの明るい／暗い灰色の陰影をつけた断片は、図１５（ｂ）の上半分内の明るい／暗い灰色の陰影をつけた領域に対応する。
【００６２】
効率のために、好適な実施の形態では、トレース変換は０〜π（０度〜１８０度）の角度θにわたってのみ行われることに留意されたい。したがって、回転不変性を維持するために、帯を、距離パラメータｄに関して水平中心線（すなわち中心値）（図１５（ａ）及び図１５（ｂ）における、ｄ＝０に対応する中心線）を中心とする対にする必要がある。図１５（ａ）に示すように、帯Ａと帯Ｂとが対にされ、図１５（ａ）内の帯Ｂの明るい／暗い灰色の陰影をつけた断片が図１５（ｂ）の下半分内の明るい／暗い灰色の陰影をつけた領域に対応する。図１５（ｃ）は同様に、トレース領域における対となる帯Ｃ及びＤを示し、これらは中心線値から、また画像領域における対応する２つの錐から、等距離に離間しており、例示のために断片に陰影をつけてある。
【００６３】
一実施形態では、帯の対が組み合わされて、汎関数Ｇが用いられて、帯サーカス関数として知られている１Ｄ関数ｇ（θ）にこれらがマッピングされる。トレース変換
【００６４】
【数８】
【００６５】
と以下のように定義されるマスク関数βとを乗算することによって帯サーカス関数ｇ（θ）を得ることができる。
【００６６】
【数９】
【００６７】
…（１２）
ここで、
【００６８】
【数１０】
【００６９】
…（１３）
式（１２）において、Ｇはトレース変換の抽出された帯のｄパラメータに沿って演算する汎関数である。式（１３）内の２つの値ｕ0及びｕ1は、帯の位置及び幅を規定する。差分ｕ1−ｕ0が大きくなるほど、帯が太くなる。
【００７０】
帯サーカス関数ｇ（θ）のより低い解像度の記述を、図１６に示すような角度（θ）における分解によって得ることができる。この分解は、画像領域に２つの錐を取ることに対応する。分解は好ましくは、幅Δθの区間にわたる積分であり、これは、画像データの解像度を低減できる該区間にわたる任意の適切な汎関数とすることもできる。
【００７１】
バイナリ表現を抽出するために、式（４）〜（９）によって記述されているもの（図３のステップ１６０〜１８０に対応する）と同じ技法を、帯サーカス関数ｇ（θ）及び／又はその分解したバージョンに適用することができる。本発明の好適な一実施形態は、トレース変換から５対の帯を抽出し、１対は中心線（距離パラメータについての中心値）にわたるものであり、４対は残りのパラメータ空間の中央半分にわたって均等に分散される。これらの帯の幅はトレース領域において２ピクセルであり、汎関数Ｇは式（１）で与えられる。得られた５つの帯サーカス関数が分解され、角度次元において解像度が係数６で低減されて、最終的な５つの帯サーカス関数が得られる。最終的な５つの帯サーカス関数から抽出される「基本」識別子と、複数解像度のトレース変換からの１２個の識別子とを組み合わせて、画像のための完全な識別子（１７個の基本識別子を含む）を形成することによって、高い性能が得られる。
【００７２】
上記の方法を行う、本発明の一実施形態による、本発明の応用のための装置の一例を図８に示す。該応用は、データベース２３０内に記憶されている画像のための識別子データベース２４０を構築することを含む。２つのデータベース２３０及び２４０は同じデータベースであってもよいし、又は別個のデータベースであってもよい。本装置は、問い合わせ画像２５０から抽出される識別子２６０を検索して、データベース内で一致するものを見つけることを可能にする。画像リスト（おそらくは順序付けされされたもの）がユーザ２９０又は問い合わせアプリケーションに返される。
【００７３】
この識別子の１つの具体的な応用は、画像検索エンジンとしての応用である。バイナリ識別子を抽出し、関連する情報（ファイル名、画像、撮影者、取得日時、及び任意の他の有用な情報等）と共に記憶することによって、データベースが構築される。次に、問い合わせ画像ａqが与えられると、バイナリ識別子が抽出され、データベース中の全ての識別子Ｂ0…ＢMと比較される。問い合わせ画像に対するハミング距離が閾値未満である全ての画像が返される。
【００７４】
［代替的な実施態様］
様々な異なるトレース汎関数及びダイアメトリカル汎関数を用いることができ、例として以下が挙げられる（網羅的でないリスト）。
【００７５】
【数１１】
【００７６】
バイナリ識別子の異なる組み合わせを組み合わせて、複雑度と、ロバスト性と、記述子サイズとの間の最適なトレードオフを提供することができる。トレース汎関数、ダイアメトリカル汎関数、分解、及び帯を変更することによって、代替的なバイナリ識別子を抽出することができる。
【００７７】
式（１３）によって与えられるマスク関数βは、マスク関数に対する１つの可能性に過ぎない。ｄ及びθの他の関数を用いて、さらなる情報を抽出できる線の代替的サブセットを抽出することができる。
【００７８】
回転、平行移動及び拡大縮小より高次の幾何変換の場合、上述した識別子のバージョンは適切でなく、式（３）の関係は成り立たない。識別子のロバスト性は、正規化工程を用いるアフィン変換まで拡張することができる。この正規化工程の全詳細は、以下の参考文献［２］に見ることができる。サーカス関数を正規化するために２つのステップが導入される。１番目のステップは、いわゆる関連サーカス（associated circus）を求めることを含み、２番目のステップは、正規化された関連サーカス関数を求めることを含む。この正規化に続き、式（３）の関係が真であることが示される。これによって、上記と同様に識別子の抽出工程を継続することができる。
【００７９】
正規化工程と共に用いられるいくつかの適切なトレース汎関数が以下の（Ｇ１）及び（Ｇ２）に与えられ、ダイアメトリカル汎関数の適切な選択が（Ｇ３）に与えられる。
【００８０】
【数１２】
【００８１】
ここで、ｒ≡ｔ−ｃであり、ｃ≡ｍｅｄｉａｎ（｛ｔk｝k，｛｜ｇ（ｔk）｜｝k）である。非負の重みｗ1，ｗ2，…，ｗnを有する数列ｙ1，ｙ2，…，ｙnの加重中央値を、この数列が重みによって昇順でソートされると仮定した場合に次式が成り立つ最大のインデックスｍを特定することによって定義する。
【００８２】
【数１３】
【００８３】
…（１４）
不等式（１４）の不等号が厳密な不等号である場合、中央値はｙmとなる。しかし、この不等式の等号が成り立つ場合、中央値は（ｙm＋ｙm-1）／２となる。
【００８４】
上記で示したように、パラメータ（ｄ又はθ）の複数の区間にわたって総和をとることによって、トレース変換における複数解像度分解を形成することができる。総和をとることは必須ではなく、他の可能性は、平均値、最大値、最小値等のような統計値を含む。他の汎関数をこれらの区間に適用することもできる。
【００８５】
汎関数Ｇは式（１）に限定されず、代替的な汎関数を用いることが可能である。異なる複数の値で分解することによって単一の帯から複数の識別子を抽出することができる。好適な実施形態では係数６が用いられたが、他の係数を用いて代替的な識別子を生成してもよい。トレース変換の中心付近の帯が、クロッピングに対する良好なロバスト性を有することが実験によって分かっている。
【００８６】
識別子に構造を適用して検索性能を高めることもできる。例えば、２パス探索を実施し、１回目の探索に半分のビットを用い、次に所与のレベルの精度を有するもののみを２回目の探索パスに認める。
【００８７】
リード・マラー（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)
［３］Paul Brasnett及びMiroslaw Boder著「A Robust Visual Identifier Using the Trace Transform」（Int. Conf. on Visual Information Eng. 2007 (VIE2007), ２００７年７月, 2007）
［４］Paul Brasnett及びMiroslaw Boder著「Multi-Resolution Trace Transform for Image Identification」（IEEE Int. Conf. on Computer Vision (ICCV 2007), ２００７年１０月）、提出済み
［５］Handbook of Global Optimization, Ed. P. M. Pardalos and H. E. Romeijn, Springer 2002
【００９９】
当業者であれば理解するように、説明した実施形態に対して多くの変形及び変更を行うことができる。例えば、本発明を、上記に記載した参考文献において教示されているもののような他の既存の技法及び関連技法を組み合わせて実施する実施形態において実施することができる。そのような既存の技法及び関連技法の組み合わせは当業者には容易に明らかとなり、本発明の範囲に入る、全てのそのような組み合わせ、並びに説明した実施形態に対する全てのそのような変更及び均等物を含むことが意図される。
【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
前記方法は、
前記画像の少なくとも一部分の２次元関数を導出することと、
前記２次元関数を処理して、前記画像の少なくとも一部分の中間表現を得ることと、
前記中間表現から前記画像の前記表現を導出することと
を含み、
前記中間表現は、前記画像の選択された一部分を用いて、又は、前記画像の少なくとも一部分の２次元関数の選択された一部分を用いて得られる、方法。
【請求項２】
前記中間表現は前記画像の少なくとも一部分の１次元関数である、請求項１に記載の方法。
【請求項３】
前記画像の選択された部分として、前記画像にわたる線のサブセットを選択することと、
前記選択された線のサブセットを用いて前記画像の前記２次元関数を導出することと、
をさらに含む、請求項１又は２に記載の方法。
【請求項４】
前記２次元関数を導出する前記ステップは、前記選択された線のサブセットの線に汎関数を適用することを含む、請求項３に記載の方法。
【請求項５】
前記画像の前記選択された部分は２つの錐を含み、
前記線のサブセットの前記線のそれぞれは前記２つの錐の頂点を通過する、請求項４に記載の方法。
【請求項６】
前記２次元関数の一部分を選択することと、
前記２次元関数の前記選択された部分の値を処理して、前記中間表現を得ることと、
をさらに含む、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記画像の前記２次元関数を処理する前記ステップは、前記２次元関数と、前記２次元関数の前記部分を規定するマスク関数とを乗算することを含む、請求項６に記載の方法。
【請求項８】
前記２次元関数の一部分を選択する前記ステップは、前記２次元関数内の値の少なくとも１つの帯を規定することをさらに含み、
前記帯又は各帯は前記２次元関数の所定範囲の第１のパラメータによって規定される、請求項６又は７に記載の方法。
【請求項９】
前記画像の前記２次元関数は距離パラメータと角度パラメータとを含み、
前記２次元関数の前記部分は、前記距離パラメータの値ｕ0と値ｕ1との間の少なくとも１つの帯によって規定される、請求項８に記載の方法。
【請求項１０】
前記方法は、一対の帯を規定することを含み、
前記一対の帯の範囲は、前記２次元関数の前記距離パラメータの中心値から等距離である、請求項８又は９に記載の方法。
【請求項１１】
前記２次元関数を導出する前記ステップは、前記画像に対してトレース変換を行うことを含む、請求項６、７、８又は９に記載の方法。
【請求項１２】
前記２次元関数を処理する前記ステップは、前記トレース変換の前記選択された部分の値に汎関数を適用して、前記画像の選択された一部分の中間表現を得ることを含む、請求項１１に記載の方法。
【請求項１３】
前記中間表現は前記画像の少なくとも一部分の１次元関数である、請求項１２に記載の方法。
【請求項１４】
前記１次元関数は次式によって定義され、
【数１】
ここで、
Ｇは前記トレース変換の前記選択された部分の前記距離パラメータに沿って演算するダイアメトリカル汎関数であり、
Ｔはトレース変換の汎関数であり、
ｄ及びθは前記トレース変換においてトレースされる前記線の前記距離パラメータ及び前記角度パラメータであり、且つ
βは前記トレース変換の選択された一部分を規定するマスク関数である、請求項１３に記載の方法。
【請求項１５】
前記マスク関数は、前記距離パラメータｄ（ｕ0≦ｄ≦ｕ1）によって前記トレース変換の値の帯を規定し、
【数２】
のように定義される、請求項１０に記載の方法。
【請求項１６】
前記トレース変換は、０度〜１８０度の範囲内の前記角度パラメータに対する値にわたって行われる、請求項３〜５又は１１〜１５のいずれか一項に記載の方法。
【請求項１７】
前記中間表現から前記画像の前記表現を導出する前記ステップは、前記中間表現の周波数表現の複数の周波数成分を用いて、前記画像の前記選択された部分の前記表現を導出することを含む、請求項１〜１６のいずれか一項に記載の方法。
【請求項１８】
前記周波数成分の振幅を用いて表現関数を定義することと、
前記周波数成分の前記振幅を用いることであって、前記画像の前記選択された部分の前記表現を導出する、用いることと、
をさらに含む、請求項１７に記載の方法。
【請求項１９】
前記中間表現から前記画像の前記表現を導出する前記ステップは、前記画像の前記選択された部分の前記導出された表現と、前記画像の１つ又は複数の他の表現とを組み合わせることを含む、請求項１〜１８のいずれか一項に記載の方法。
【請求項２０】
前記２次元関数及び／又は前記中間表現の解像度を低減することをさらに含む、請求項１〜１９のいずれか一項に記載の方法。
【請求項２１】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
前記方法は、前記画像から、実質的に円形である部分画像を抽出することを含み、
前記部分画像はテーパリングされた円形の境界を有し
前記方法は、前記抽出された円形の部分画像から前記画像の前記表現を導出することを含み、
前記画像の前記表現を前記導出することは、好ましくは請求項１〜２０のいずれか一項に記載の方法を用いて行われる、方法。
【請求項２２】
画像を識別する方法であって、
請求項１〜２１のいずれか一項に記載の方法を用いて前記画像の表現を導出することと、
前記表現と前記画像とを関連付けることと、
を含む、方法。
【請求項２３】
画像を比較する方法であって、請求項１〜２２のいずれか一項に記載の方法を用いて導出される各画像の表現を比較することを含む、方法。
【請求項２４】
前記比較することはハミング距離を求めることを含む、請求項２３に記載の方法。
【請求項２５】
表現の比較に基づいて画像を選択することを含む、請求項２３又は２４に記載の方法。
【請求項２６】
請求項１〜２１のいずれか一項に記載の方法を用いて導出される画像の表現の使用であって、前記表現の送信、受信又は処理を含む、使用。
【請求項２７】
請求項１〜２１のいずれか一項に記載の方法を実行する装置。
【請求項２８】
請求項１〜２１のいずれか一項に記載の方法を実施するコンピュータ可読媒体上のコンピュータプログラム。
【請求項１】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
前記方法は、
前記画像の少なくとも一部分の２次元関数を導出することと、
前記２次元関数を処理して、前記画像の少なくとも一部分の中間表現を得ることと、
前記中間表現から前記画像の前記表現を導出することと
を含み、
前記中間表現は、前記画像の選択された一部分を用いて、又は、前記画像の少なくとも一部分の２次元関数の選択された一部分を用いて得られる、方法。
【請求項２】
前記中間表現は前記画像の少なくとも一部分の１次元関数である、請求項１に記載の方法。
【請求項３】
前記画像の選択された部分として、前記画像にわたる線のサブセットを選択することと、
前記選択された線のサブセットを用いて前記画像の前記２次元関数を導出することと、
をさらに含む、請求項１又は２に記載の方法。
【請求項４】
前記２次元関数を導出する前記ステップは、前記選択された線のサブセットの線に汎関数を適用することを含む、請求項３に記載の方法。
【請求項５】
前記画像の前記選択された部分は２つの錐を含み、
前記線のサブセットの前記線のそれぞれは前記２つの錐の頂点を通過する、請求項４に記載の方法。
【請求項６】
前記２次元関数の一部分を選択することと、
前記２次元関数の前記選択された部分の値を処理して、前記中間表現を得ることと、
をさらに含む、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記画像の前記２次元関数を処理する前記ステップは、前記２次元関数と、前記２次元関数の前記部分を規定するマスク関数とを乗算することを含む、請求項６に記載の方法。
【請求項８】
前記２次元関数の一部分を選択する前記ステップは、前記２次元関数内の値の少なくとも１つの帯を規定することをさらに含み、
前記帯又は各帯は前記２次元関数の所定範囲の第１のパラメータによって規定される、請求項６又は７に記載の方法。
【請求項９】
前記画像の前記２次元関数は距離パラメータと角度パラメータとを含み、
前記２次元関数の前記部分は、前記距離パラメータの値ｕ0と値ｕ1との間の少なくとも１つの帯によって規定される、請求項８に記載の方法。
【請求項１０】
前記方法は、一対の帯を規定することを含み、
前記一対の帯の範囲は、前記２次元関数の前記距離パラメータの中心値から等距離である、請求項８又は９に記載の方法。
【請求項１１】
前記２次元関数を導出する前記ステップは、前記画像に対してトレース変換を行うことを含む、請求項６、７、８又は９に記載の方法。
【請求項１２】
前記２次元関数を処理する前記ステップは、前記トレース変換の前記選択された部分の値に汎関数を適用して、前記画像の選択された一部分の中間表現を得ることを含む、請求項１１に記載の方法。
【請求項１３】
前記中間表現は前記画像の少なくとも一部分の１次元関数である、請求項１２に記載の方法。
【請求項１４】
前記１次元関数は次式によって定義され、
【数１】
ここで、
Ｇは前記トレース変換の前記選択された部分の前記距離パラメータに沿って演算するダイアメトリカル汎関数であり、
Ｔはトレース変換の汎関数であり、
ｄ及びθは前記トレース変換においてトレースされる前記線の前記距離パラメータ及び前記角度パラメータであり、且つ
βは前記トレース変換の選択された一部分を規定するマスク関数である、請求項１３に記載の方法。
【請求項１５】
前記マスク関数は、前記距離パラメータｄ（ｕ0≦ｄ≦ｕ1）によって前記トレース変換の値の帯を規定し、
【数２】
のように定義される、請求項１０に記載の方法。
【請求項１６】
前記トレース変換は、０度〜１８０度の範囲内の前記角度パラメータに対する値にわたって行われる、請求項３〜５又は１１〜１５のいずれか一項に記載の方法。
【請求項１７】
前記中間表現から前記画像の前記表現を導出する前記ステップは、前記中間表現の周波数表現の複数の周波数成分を用いて、前記画像の前記選択された部分の前記表現を導出することを含む、請求項１〜１６のいずれか一項に記載の方法。
【請求項１８】
前記周波数成分の振幅を用いて表現関数を定義することと、
前記周波数成分の前記振幅を用いることであって、前記画像の前記選択された部分の前記表現を導出する、用いることと、
をさらに含む、請求項１７に記載の方法。
【請求項１９】
前記中間表現から前記画像の前記表現を導出する前記ステップは、前記画像の前記選択された部分の前記導出された表現と、前記画像の１つ又は複数の他の表現とを組み合わせることを含む、請求項１〜１８のいずれか一項に記載の方法。
【請求項２０】
前記２次元関数及び／又は前記中間表現の解像度を低減することをさらに含む、請求項１〜１９のいずれか一項に記載の方法。
【請求項２１】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
前記方法は、前記画像から、実質的に円形である部分画像を抽出することを含み、
前記部分画像はテーパリングされた円形の境界を有し
前記方法は、前記抽出された円形の部分画像から前記画像の前記表現を導出することを含み、
前記画像の前記表現を前記導出することは、好ましくは請求項１〜２０のいずれか一項に記載の方法を用いて行われる、方法。
【請求項２２】
画像を識別する方法であって、
請求項１〜２１のいずれか一項に記載の方法を用いて前記画像の表現を導出することと、
前記表現と前記画像とを関連付けることと、
を含む、方法。
【請求項２３】
画像を比較する方法であって、請求項１〜２２のいずれか一項に記載の方法を用いて導出される各画像の表現を比較することを含む、方法。
【請求項２４】
前記比較することはハミング距離を求めることを含む、請求項２３に記載の方法。
【請求項２５】
表現の比較に基づいて画像を選択することを含む、請求項２３又は２４に記載の方法。
【請求項２６】
請求項１〜２１のいずれか一項に記載の方法を用いて導出される画像の表現の使用であって、前記表現の送信、受信又は処理を含む、使用。
【請求項２７】
請求項１〜２１のいずれか一項に記載の方法を実行する装置。
【請求項２８】
請求項１〜２１のいずれか一項に記載の方法を実施するコンピュータ可読媒体上のコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公表番号】特表２０１０−５３１５０７（Ｐ２０１０−５３１５０７Ａ）
【公表日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願番号】特願２０１０−５１４０８８（Ｐ２０１０−５１４０８８）
【出願日】平成２０年３月１２日（２００８．３．１２）
【国際出願番号】ＰＣＴ／ＧＢ２００８／０００８６７
【国際公開番号】ＷＯ２００９／００１０２５
【国際公開日】平成２０年１２月３１日（２００８．１２．３１）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
【公表日】平成２２年９月２４日（２０１０．９．２４）
【国際特許分類】
【出願日】平成２０年３月１２日（２００８．３．１２）
【国際出願番号】ＰＣＴ／ＧＢ２００８／０００８６７
【国際公開番号】ＷＯ２００９／００１０２５
【国際公開日】平成２０年１２月３１日（２００８．１２．３１）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
[ Back to top ]