改良された画像識別
画像に対応する信号を処理することによって画像の表現を導出する方法及び装置が記載される。本方法は、画像のトレース変換等の2次元関数(T(d,θ))を導出することと、その2つの次元のうちの少なくとも一方において2次元関数(T(d,θ))を(例えばサブサンプリングすることによって)分解することであって、それによって、低減された解像度のトレース変換を得る、分解することとを含む。次いで分解された2次元関数を用いて、画像の表現が導出される。
【発明の詳細な説明】
【技術分野】
【0001】
[発明の背景]
[発明の分野]
本発明は、画像を表現する方法及び装置に関し、さらに、(例えば検索又は検証の目的のために)画像を比較又は照合する方法及び装置に関する。
【0002】
[背景技術の記載]
本発明は、同時係属中の欧州特許出願EP06255239.3に記載されている画像識別技法に対する改良に関する。欧州特許出願EP06255239.3の内容は参照により本明細書に援用される。欧州特許出願EP06255239.3の発明及び実施の形態の詳細は、本発明及び本実施の形態にも同様に適用される。
【0003】
画像から短いバイナリ記述子を抽出する(図2参照)、欧州特許出願EP06255239.3に記載されている画像識別方法及び装置は、従来技術の多くの欠点に対処しており、特に、
・特徴抽出及び照合の双方について計算複雑度が低減されていること、
・画像記述子のサイズが低減されていること、
・さまざまな画像変更に対するロバスト性が高められていること、並びに
・広範な変更に対して約80%までの検出率を維持しながら誤報率が1ppmレベルに低減されていること、
を特徴とする。
【0004】
しかしながら、実際の用途においては検出率がより高いことが望ましい。特に、平均検出率を98%超にまで高めると共に、ノイズ及びヒストグラム等化の変更に対するロバスト性も大幅に向上させることが望ましい。
【0005】
[発明の概要]
第1の態様によれば、本発明は、添付の特許請求の範囲の請求項1に定義されている、画像の表現を導出する方法を提供する。
【0006】
本発明のさらなる態様は、本発明の第1の態様による方法を用いて導出される画像の表現の使用と、本発明の第1の態様による方法を実施する装置と、命令(実行されると本発明の第1の態様による方法を実施するもの)を含むコンピュータ可読記憶媒体とを含む。
【0007】
本発明の実施の形態の好ましい特徴及び任意選択の特徴は従属請求項に記載されている。
【0008】
本発明は、画像のトレース変換(又は画像の2次元関数であって等価なもの)から視覚的な識別特徴を抽出する新規の方法に関する。本方法は、識別子を抽出する前に、例えばフーリエ変換の振幅によって画像のトレース変換に対して領域ベースの処理を行うことによって、画像の複数解像度の表現を作成するのに用いることができる。
【0009】
本出願において、用語「汎関数」は、その通常の数学的意味を有する。特に、汎関数とは、ベクトル空間V上の(通常は関数の)実数値関数である。トレース変換の場合、汎関数は画像内の線に適用される。
【0010】
同時係属中の欧州特許出願EP06255239.3に記載されている方法では、トレース変換は、画像を直線でトレースすることによって計算され、該直線に沿って、画像輝度の特定の汎関数T又は色関数が計算される。異なる複数の汎関数Tが用いられて単一の入力画像から異なる複数のトレース変換が生成される。2D平面において線は2つのパラメータ、すなわち距離d及び角度θによって特徴付けられるため、画像のトレース変換は各トレース線のパラメータの2D関数である。次に、トレース変換の列に沿ってダイアメトリカル汎関数(diametrical functional) Pを適用することによって「サーカス関数(circus function)」が計算される。サーカス関数の周波数表現(例えばフーリエ変換)が得られ、周波数振幅成分に関して関数が定義され、その符号がバイナリ記述子として取られる。
【0011】
本発明の実施の形態による方法は、同様の技法を用いて画像の表現を導出することができる。しかしながら、画像の表現(例えばバイナリ記述子)を導出するさらなるステップを行う前に、低減された解像度のトレース変換等の、画像の低減された解像度の関数が導出される。解像度の低減は、処理されるデータ量を低減しながら画像に特有の必須要素(すなわちその視覚的な識別特徴)を維持するべきである。通常、導出される画像の低減された解像度の関数は、以下の記載から明らかになるように、演算によって、画像の選択される部分又はサンプリングされる部分の表現値を組み込む。
【0012】
本発明の一実施の形態によれば、画像の低減された解像度の関数は、線のセット(これらの線のパラメータは、所定の区間Δd及び/又はΔθのものである)を用いて画像をトレースすることと、(画像を横切るすべての線の代わりに)線のセットのすべてを用いてトレース変換(又は等価物)を導出することとによって導出される。線は、画像領域における帯(図10に示すもの)及び/又は2つの錐(図11に示すもの)に対応し得る。したがって、より詳細に後述するように、画像の低減された解像度の(すなわちより粗い解像度の)トレース変換が導出される。
【0013】
本発明の別の実施の形態によれば、最初に、従来のように画像を横切るすべての線をトレースすることによってトレース変換(又は等価物)が導出される。次いで、角度パラメータθの異なる値における複数の帯を用いて画像のトレース変換がトレースされ、(図12に示すような)距離パラメータdの複数の区間にわたって解像度の低減が行われ、且つ/又は、距離パラメータdの異なる値における複数の帯を用いてトレース変換がトレースされ、トレース領域において(図13に示すような)角度パラメータθの複数の区間にわたって解像度の低減が行われ、より詳細に後述するように画像の低減された解像度の2次元関数が導出される。
【0014】
有利には、以下でさらに詳細に説明するように、トレース変換領域内の帯及び/又は錐に沿ってトレース変換値を暗黙的に計算することによって、本発明のこの実施の形態の方法を非常に効率的に実施することができる。
【0015】
同時係属中の欧州特許出願EP06255239.3に開示されている方法のように、本発明の一実施の形態による方法は、異なる複数の汎関数を用いることによって得られる識別子「族」の選択部分を組み合わせる。さらに、いくつかの実施形態では、帯及び/又は2つの錐を用いて得られる識別子は組み合されて単一の記述子になる。さらに、いくつかの実施形態において、幅が異なる複数の帯及び/又は開口角が異なる複数の錐が用いられて、複数解像度の表現が得られる。
【0016】
添付図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【0017】
【図1a】画像を示す。
【図1b】図1aの画像を縮小した変形を示す。
【図1c】図1aの画像を回転させた変形を示す。
【図1d】図1aの画像をぼかした変形を示す。
【図2】画像と、従来技術によるその画像のビットストリング表現とを示す。
【図3】本発明の一実施形態の方法のステップを示す図である。
【図4】本発明の一実施形態の別の方法のステップを示す図である。
【図5】トレース変換の線パラメータ化を示す図である。
【図6】(a)〜(c)は、画像の異なるバージョンから導出される関数を示す。
【図7】本発明の一実施形態による装置のブロック図である。
【図8】複数のトレース変換を用いる一実施形態を示すブロック図である。
【図9】図8の実施形態によって作成されるビットストリームを示す図である。
【図10】トレース変換のdパラメータを分解するときの原画像内の区間帯を示す。
【図11】トレース変換のθパラメータを分解するときの原画像における2つの錐を示す。
【図12】dパラメータにおけるトレース変換の分解を示す。
【図13】θパラメータにおけるトレース変換の分解を示す。
【発明を実施するための形態】
【0018】
[実施形態の詳細な説明]
画像の表現(具体的には画像識別子)を導出すると共に、このような表現/識別子を(例えば、1つ又は複数の画像の識別、照合又は検証の目的で)用いるさまざまな実施形態を以下に記載する。本発明は画像の識別に特に有用であるが、これには限定されない。記載される実施形態では、「画像識別子」(ときに「識別子」と単純化される)は画像の表現の一例であり、この用語は画像の表現、すなわち記述子を指すために用いられるに過ぎない。
【0019】
当業者であれば、本発明の一実施形態による画像識別装置及び方法の具体的な設計と、画像識別に用いる画像識別子の導出とは、設計要件によって決定されることを理解しよう。このような設計要件は、画像識別子がロバストであるべき画像変更のタイプ、識別子のサイズ、抽出及び照合の複雑度、目標誤報率等に関連する。
【0020】
以下の実施形態は、画像に対する以下の変更にロバストな識別子をもたらす一般的設計を示す(これは網羅的なリストではない)。
・色数削減
・ぼかし
・明るさの変更
・反転(左右及び上下)
・グレースケール変換
・ヒストグラム等化
・JPEG圧縮
・ノイズ
・回転
・拡大縮小
【0021】
この一般的設計は通常、広範な画像に対して百万分の1(ppm)という非常に低い誤報率を達成することができることが分かっている。
【0022】
図1は、画像及びその画像を変更した変形の一例を示す。より具体的には、図1aは原画像であり、図1bは図1aの画像を縮小したバージョンであり、図1cは図1aの画像を回転させたバージョンであり、図1dは図1aの画像をぼかしたバージョンである。
【0023】
本発明の一実施形態は、画像に対応する信号を処理することによって、画像の表現、より具体的には画像識別子を導出する。
【0024】
図3は、本発明の一実施形態による画像識別子を導出する方法の各ステップ、すなわち識別子抽出工程を示す。
【0025】
抽出の初期段階において画像を前処理する。これは、画像をサイズ変更し(ステップ110)、任意選択でフィルタリングする(ステップ120)ことによって行われる。サイズ変更ステップ110は、画像を処理前に正規化するために用いられる。ステップ120は、画像に対して行われた何らかの処理によって生じるエイリアシング等の効果を除去するためのフィルタリングを含み得、及び/又は、原画像全体を用いるのではなく領域を選択することを含み得る。本方法の好適な一実施形態では、画像の中央から円形領域がさらなる処理のために抽出される。
【0026】
ステップ130において、トレース変換
【0027】
【数1】
【0028】
を行う。トレース変換は、全ての可能な線を画像に射影し、これらの線に1つ又は複数の汎関数を適用する。上述のように、汎関数とは、ベクトル空間V上の実数値関数であり、、通常は関数の実数値関数である。トレース変換の場合、画像中の複数の線に汎関数が適用される。図5に示されるように、線は2つのパラメータd及びθによってパラメータ化される。後述のように、ステップ140においてトレース変換の結果を分解してその解像度を低減することができる。ステップ150において、トレース変換の各列にさらなる汎関数を適用して、実数値ベクトルを得ることができる。この第2の汎関数はダイアメトリカル汎関数(diametrical functional)として知られ、結果として得られるベクトルはサーカス関数として知られる。第3の汎関数であるサーカス汎関数をサーカス関数に適用して、単一の数を得ることができる。この結果の特性は、これら3つの異なる汎関数(トレース汎関数、ダイアメトリカル汎関数及びサーカス汎関数)を適切に選択することによって制御することができる。画像及び対応するトレース変換の例を含むトレース変換の全詳細は、例えば、以下の参考文献[1]:参照により本明細書に援用されるAlexander Kadyrov及びMaria Petrou著「The Trace Transform and its Applications」(IEEE Trans. PAMI, 23(8), 2001年8月、 pp 811-828)に見ることができる。この実施形態の方法では、1Dサーカス関数を得るために、最初の2つのステップのみをトレース変換において行う。
【0029】
本方法の1つの特定の例において、画像のトレース変換
【0030】
【数2】
【0031】
はトレース汎関数T
【0032】
【数3】
【0033】
を用いて抽出され、サーカス関数はダイアメトリカル汎関数P
【0034】
【数4】
【0035】
を適用することによって得られる。
【0036】
サーカス関数が様々な画像処理操作によって受ける影響の例を図6に見ることができる。図6は、画像の様々な変形に対応するサーカス関数を示す。図6(a)は原画像に対応し、図6(b)はその画像を回転させたバージョンに対応し、図6(c)はその画像をぼかしたバージョンに対応する。回転は関数をシフトさせる(と共にスケール変化を生じる)ことが分かる。
【0037】
上で挙げた大部分の画像の変更操作に関して、汎関数T、Pを適切に選択すれば、画像aのサーカス関数f(a)は、変更された画像a’のサーカス関数f(a’)がシフト又は(振幅が)拡大縮小された変形に過ぎないことを示すことができる(以下の参考文献[1]の第3章を参照)。
【0038】
【数5】
【0039】
同時係属中の欧州特許出願EP06255239.3に記載されている方法によれば、サーカス関数の周波数表現の周波数成分を用いて画像識別子を導出することができる。画像記述子を導出する他の技法が可能であると共に、本発明と併せて用いることができることは理解されよう。一例では、画像識別子は、サーカス関数のフーリエ変換(又は同様にハール変換)から導出することができる。
【0040】
したがって、式(3)のフーリエ変換を行うことによって、次式が与えられる。
【0041】
【数6】
【0042】
次に、式(6)の振幅を取ると次式が得られる。
【0043】
【数7】
【0044】
式(7)から、この時点では、変更された画像と原画像とはスケーリング係数κを除いて同じであることが分かる。
【0045】
本実施形態によれば、ここで、フーリエ変換係数の複数の振幅係数について関数c(ω)が定義される。この関数の1つの例示は、各係数とその隣の係数との間の差分を取ることである。
【0046】
【数8】
【0047】
結果として得られるベクトル(式8)に、以下のように閾値を適用することによってバイナリストリングを抽出することができる。(すべてのωについて)
【0048】
【数9】
【0049】
次に、これらの値B={b0,...,bn}から画像識別子が構築される。
【0050】
2つの異なる識別子B1及びB2(いずれも長さN)の間で識別子の照合を行うために、正規化ハミング距離を取る。
【0051】
【数10】
【0052】
ここで、
【0053】
【数11】
【0054】
は排他的OR(XOR)演算子である。識別子又は表現の他の比較方法も用いることができる。
【0055】
識別子中の特定ビットの選択によって性能をさらに高めることができる。より低い周波数に対応するビットは一般にロバスト性がより高く、より高い周波数に対応するビットは識別性がより高い。本発明の特定の一実施形態では最初のビットを無視し、識別子は続く64ビットから成る。
【0056】
本発明の一実施形態によれば、トレース変換(又は等価物)からもたらされる、画像の2次元関数を分解するステップ140は、その解像度を低減することを含む。解像度の低減は、その2つの次元d若しくはθのうちのいずれか又は双方の次元において処理することによって達成することができる。
【0057】
したがって、図12のように、dパラメータをサブサンプリングすることによって、例えば(θの値に対応する)列に沿ってdの複数の区間にわたって総和をとるか又は積分することによって、「トレース領域」における距離次元において解像度を低減することができる。これは、図10に示されるように、トレース変換中に幅Δdの帯を画像に(すなわち画像領域内に)射影することに対応する。距離パラメータdの複数の区間にわたってサブサンプリングする(すなわちトレース変換の解像度を低減する)任意の技法を用いることができることは理解されよう。したがって、データの本質を維持しながらデータの量を低減する任意の統計的計算を用いることができ、総和をとること及び積分はその例に過ぎない。
【0058】
代替的に又は付加的に、図13のように、θパラメータをサブサンプリングすることによって、例えば(dの値に対応する)行に沿ってθの複数の区間にわたって総和をとること又は積分することによって、「トレース領域」における角度次元において解像度を低減することができる。これは図11に示されるように、トレース変換の間に開口角Δθを有する2つの錐を画像に(すなわち画像領域内に)射影することとほぼ等価である。角度パラメータθの複数の区間にわたってサブサンプリングする(すなわちトレース変換の解像度を低減する)任意の技法を用いることができることは理解されよう。したがって、データの本質を維持しながらデータの量を低減する任意の統計的計算を用いることができ、総和をとること及び積分はその例に過ぎない。
【0059】
本発明の別の実施形態によれば、分解するステップ140は、「画像領域」において行うことができ、すなわち、ステップ120の後に且つ通常図3のステップ130と組み合わせて行うことができる。一例では、ステップ140は、画像自体の中の線のセットを結合又は分解すると共に、これらの線に対してトレース変換(又は他の演算)を行って画像識別子を導出する。例えば、画像の複数の線をステップ130において共に効率的に処理することができるように、1画素幅の画像の線を結合することができる。線のセットは例えば、図10に示されるような平行線及び/又は図11に示されるような2つの錐によって規定される線とすることができる。結合される線の数は上述の区間に対応する。したがって、この実施形態では、トレース変換は、従来のトレース変換のように画像を横切るすべての線をトレースする代わりに、画像を横切る線の選択されたセットをトレースするように有効に変更される。
【0060】
当業者には理解されるように、画像領域において分解する他の技法が可能である。
【0061】
上記の方法を行う本発明の一実施形態による装置の一例を図7に示す。具体的には、画像記憶モジュール210によって画像200が受け取られ、画像データベース230に記憶される。さらに、識別子抽出及び記憶モジュール220が、本発明の方法に従って、受け取った画像毎に画像識別子を抽出し、それらの画像識別子を識別子データベース240に、(任意選択で、画像のコンテンツに関連する他の情報と共に)適宜記憶する。
【0062】
図7はさらに、上記の方法を用いて抽出された画像識別子を用いる画像検索エンジンを具現する装置を示す。画像の検証又は照合が、問い合わせ画像250の受け取りに応答して画像検索エンジンによって行われ得る。本発明の方法に従って、問い合わせ画像250の画像識別子が識別子抽出モジュール260において抽出される。識別子照合モジュール270が問い合わせ画像250の画像識別子を、識別子データベース240に記憶されている画像識別子と比較する。画像検索モジュール280が、画像データベース230から一致画像290を取り出す。この一致画像290は、以下で詳述するように、問い合わせ画像識別子と一致する画像識別子を有する。
【0063】
図4は、フーリエ変換係数に対するバイナリ関数を定義する代替的な方法を示す。特に、フーリエ変換係数を得た(ステップ171)後、複数のフーリエ変換係数の振幅の対数を得る(ステップ172及び173)。以降の係数の差分を上記の式(8)と同様に計算し(ステップ174)、その後、この差分の符号を取り、この符号によってバイナリ値を割り当てる(ステップ175)。次に、このバイナリ値を用いてバイナリ識別子を形成する。画像の関数の他の周波数表現(ハール変換を含む)の周波数係数にこの技法を用いることができることは理解されよう。
【0064】
上述した基本識別子は、図8及び図9に示すように、低減された解像度のトレース変換を複数用いてそれぞれの識別子を導出することと、別々の識別子からのビットを組み合わせることとによって改良することができる。低減された解像度のトレース変換の別々のものからのバイナリストリング361及び362を組み合わせる具体的な方法は、それらを連結して識別子363を得ることである。
【0065】
このようにして、上記の式(1)のトレース汎関数Tを、上記の式(2)によって与えられるダイアメトリカル汎関数Pと共に用いて1つのバイナリストリングを得た後、トレース汎関数(1)をダイアメトリカル汎関数(11)
【0066】
【数12】
【0067】
と共に用いて第2のストリングを得ることによって良好な結果を得ることができる。各バイナリストリングの最初のビットはスキップし、両方のストリングからの次の64ビットを連結して128ビットの識別子を得る。
【0068】
本発明によれば、トレース変換における複数解像度の表現を用いることによって大幅な性能改良を得ることができる。特に、1つ又は2つの次元において分解を行うことができる。次いで上記のように、ダイアメトリカル汎関数を適用してバイナリストリングを抽出することができる。通常の結果は、この分解を用いることによって百万分の1の誤報率(false error rate)における検出率が約80%から98%に高められることを示す。
【0069】
この複数解像度のトレース変換は、上述のように、その2つの次元d若しくはθのうちのいずれか又は双方の次元において元のトレース変換をサブサンプリングしてその解像度を低減することによって生成することができる。「トレース領域」においてdパラメータのサブサンプリングは、例えば図12のように列に沿って複数の区間にわたって積分することによって行われる。これは、図10に示されるように、トレース変換中に幅Δdの帯を画像に射影することに対応する。サブサンプリングは、例えばθパラメータにおける複数の区間にわたって、すなわち行に沿って積分することによって行うこともできる。図13を参照されたい。これは、トレース変換中に開口角Δθを有する2つの錐にわたって積分することとほぼ同じである。図11を参照されたい。代替的に、上述のようにこれらの演算を「画像領域」において行うことができる。
【0070】
複数解像度分解を用いることによって、1つのトレース変換から複数の基本識別子を抽出することができる。ここで、ある範囲内の異なる区間幅にわたってサブサンプリングが行われて、複数の基本識別子から成る複数解像度の表現が生成される。理想的には、複数解像度の表現はある範囲内の区間幅を用いて導出される複数の識別子を用いる。例えば、各区間幅は他の区間幅と少なくとも2倍異なってもよい。トレース変換の出力のサイズが600×384であり、したがってdパラメータが幅8、16、32、64及び128の帯(band)を用いて積分することによってサブサンプリングされ、同様にθパラメータが例えば幅3、6、12、及び24の帯を用いて積分することによってサブサンプリングされるシステムを用いることによって、良好な結果が一般的に得られた。
【0071】
この識別子の1つの応用は、画像検索エンジンとしての応用である。ファイル名、画像、撮影者、取得日時、及び任意の他の有用な情報等の関連する情報と共に、バイナリ識別子を抽出し記憶することによって、データベースが構築される。次に、問い合わせ画像aqが与えられると、バイナリ識別子が抽出され、データベース中の全ての識別子B0...BMと比較される。問い合わせ画像に対するハミング距離が閾値未満である全ての画像が返される。
【0072】
[代替的な実施態様]
様々な異なるトレース汎関数及びダイアメトリカル汎関数を用いることができ、例として以下が挙げられる(網羅的でないリスト)。
【0073】
【数13】
【0074】
2つ又はそれ以上の識別子を組み合わせて、画像をより正確に特徴付けすることができる。この組み合わせは、複数の識別子の連結によって行われることが好ましい。
【0075】
回転、平行移動及び拡大縮小より高次の幾何変換の場合、上述した識別子のバージョンは適切でなく、式(3)の関係は成り立たない。識別子のロバスト性は、正規化工程を用いるアフィン変換まで拡張することができる。この正規化工程の全詳細は、以下の参考文献[2]に見ることができる。サーカス関数を正規化するために2つのステップが導入され、最初のステップは、いわゆる関連サーカス(associated circus)を求めることを含み、2番目のステップは、正規化された関連サーカス関数を求めることを含む。この正規化に続き、式(3)の関係が真であることが示される。これによって、上記と同様に識別子の抽出工程を継続することができる。
【0076】
正規化工程と共に用いられるいくつかの適切なトレース汎関数が以下の(G1)及び(G2)に与えられ、ダイアメトリカル汎関数の適切な選択が(G3)に与えられる。
【0077】
【数14】
【0078】
ここで、r≡t−cであり、c≡median({tk}k,{|g(tk)|}k)である。非負の重みw1,w2,...,wnを有する数列y1,y2,...,ynの加重中央値を、この数列が重みによって昇順でソートされると仮定した場合に次式が成り立つ最大インデックスmを特定することによって定義する。
【0079】
【数15】
【0080】
不等式(12)が厳密(strict)である場合、中央値はymとなる。しかし、不等式が等式である場合、中央値は(ym+ym-1)/2となる。
【0081】
識別子を連続するビットのブロックから構築する代わりに、実験によって選択を行うことができる。このやり方の一例は、i)独立した画像と、ii)原画像及び変更された画像との2組のデータを用意することである。識別子の性能は、独立したデータの誤受入率と、原画像及び変更された画像の誤拒否率とを比較することによって測定することができる。関心となる点は、等価エラー率、すなわち、1×10-6の誤受入率における誤拒否率である。最適化は、ビットが選択されていない状態で開始される。各ビットを1つずつ検査して、どのビットが(例えば等価エラー率又は何らかの類似の測度に関して)最良の性能を発揮するかを確かめることが可能である。最良の結果を与えるビットが選択されるべきである。次に、全ての残りのビットを試験して、どれが最初のビットと組み合わせた際に最良の性能を発揮するかを確かめるべきである。ここでもまた、エラー率が最低のビットが選択される。この手順は、全てのビットが選択されるまで繰り返される。このように、全体として最良の性能をもたらすビットの組み合わせを求めることができる。
【0082】
上記で示したように、パラメータ(d又はθ)の複数の区間にわたって総和をとること又は積分することによって、トレース変換における複数解像度分解を形成することができる。上記で示したように、任意の統計的技法を用いて分解又は解像度低減を達成することができ、他の可能性は、平均値、最大値、最小値等のような統計値を計算することを含む。他の汎関数をこれらの区間に適用することもできる。
【0083】
さらに、構造を識別子に適用して検索性能を高めることもできる。例えば、2パス探索を実施し、1回目の探索に半分のビットを用い、次に所与のレベルの精度を有するビットのみを2回目の探索パスに認める。
【0084】
リード・マラー(Reed-Muller)復号器又はウイナー・ジブ(Wyner-Ziv)復号器等の方法を用いて識別子を圧縮し、さらにサイズを縮小することができる。
【0085】
[代替的な応用]
識別子はまた、ビデオシーケンス中のフレームをインデックス付けするために用いることもできる。新たなシーケンスが与えられると、フレームから識別子を抽出し、次に、同一のシーケンスを見つけるために検索を行うことができる。これは、著作権の検出及びシーケンスの識別のために有用であり得る。
【0086】
複数の放送会社が同一のコンテンツ、例えば広告又は株式ニュースの映像を送信する場合が多い。放送会社間のナビゲーションのために、識別子を用いてこれらのコンテンツ間にリンクを形成することができる。
【0087】
画像識別子は、画像を介してコンテンツを結びつける機会を提供する。ユーザがウェブページ上の特定の画像に興味がある場合、同一画像を有する他のページを見つける有効な方法はない。識別子を用いて、画像間のナビゲーション経路を提供することができる。
【0088】
識別子を用いてブロードキャストフィード中の広告を検出することができる。これを用いて、広告主が自社のキャンペーンを追跡するための自動監視を行うことができる。
【0089】
大規模な商用集合からパーソナルコンピュータ上の小規模なコレクションまで多くの画像データベースが存在する。データベースが厳格に制御されていない限り、通常は集合の画像に重複があり、余分な記憶領域を無駄に必要とする。識別子は、これらのデータセット中の重複画像を削除又は紐付けするツールとして用いることができる。
【0090】
本明細書中、「画像」という用語は、画像単位(フィルタリング、解像度の変更、アップサンプリング、ダウンサンプリング等の処理の後のものを含む)を記述するために用いられるが、他の類似の用語(フレーム、フィールド、ピクチャ、又は、画像・フレーム等のサブユニット若しくは領域等)にも当てはまる。本明細書中、画像という用語は、文脈から明らかである場合を除き、画像全体又は画像の領域を意味する。同様に、画像の領域は画像全体を意味し得る。画像は、フレーム又はフィールドを含み、静止画、又はフィルムに関連し、または、ビデオ等の画像シーケンス中の画像に関連し、または、関連する画像のグループ中の画像に関連する。画像は、グレースケール画像又はカラー画像であってもよく、又は別のタイプのマルチスペクトル画像(例えば、IR、UV若しくは他の電磁波画像)であってもよく、又は音響画像であってもよく、他の画像であってもよい。
【0091】
実施形態において、周波数表現は、フーリエ変換を用いて導出されるが、周波数表現は、ハール変換等の他の技法を用いて導出することもできる。特許請求の範囲において、フーリエ変換という単語は、DFT及びFFT等の変形を網羅するものとする。
【0092】
本発明は、適切な装置を用いて電気的信号を処理することによって実施されることが好ましい。
【0093】
本発明は、例えば、適切なソフトウェア及び/又はハードウェアの変更を加えたコンピュータシステムにおいて実施することができる。例えば、本発明は、制御手段若しくは処理手段(プロセッサ若しくは制御装置等)、データ記憶手段(メモリ、磁気記憶装置、CD、DVD等のような画像記憶手段を含む)、データ出力手段(ディスプレイ、モニタまたはプリンタ等)、データ入力手段(キーボード等)、及び画像入力手段(スキャナ等)を有する、又はこれらの構成要素の任意の組み合わせを他の付加的な構成要素と共に有する、コンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェア及び/若しくはハードウェアの形態、又は特定用途向け装置において提供することができ、又は、チップ等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置におけるシステムの構成要素は、他の構成要素から離れた場所に、例えばインターネットを介して設けられてもよい。
【0094】
[参考文献]
[1]Alexander Kadyrov及びMaria Petrou著「The Trace Transform and Its Applications」(IEEE Trans. PAMI, 23 (8), 2001年8月, pp 811-828)
[2]Maria Petrou及びAlexander Kadyrov著「Affine Invariant Features from the Trace Transform」(IEEE Trans, on PAMI, 26 (1), 2004年1月, pp 30-44)
【0095】
当業者であれば理解するように、説明した実施形態に対して多くの変形及び変更を行うことができる。例えば、本発明を、当業者に既知の既存の技法及び関連技法を組み合わせて実施する実施形態において実施することができる。添付の特許請求の範囲に規定される本発明の範囲に入る、説明した実施形態に対するそのような変形、変更及び均等物を全て含むことが意図される。
【技術分野】
【0001】
[発明の背景]
[発明の分野]
本発明は、画像を表現する方法及び装置に関し、さらに、(例えば検索又は検証の目的のために)画像を比較又は照合する方法及び装置に関する。
【0002】
[背景技術の記載]
本発明は、同時係属中の欧州特許出願EP06255239.3に記載されている画像識別技法に対する改良に関する。欧州特許出願EP06255239.3の内容は参照により本明細書に援用される。欧州特許出願EP06255239.3の発明及び実施の形態の詳細は、本発明及び本実施の形態にも同様に適用される。
【0003】
画像から短いバイナリ記述子を抽出する(図2参照)、欧州特許出願EP06255239.3に記載されている画像識別方法及び装置は、従来技術の多くの欠点に対処しており、特に、
・特徴抽出及び照合の双方について計算複雑度が低減されていること、
・画像記述子のサイズが低減されていること、
・さまざまな画像変更に対するロバスト性が高められていること、並びに
・広範な変更に対して約80%までの検出率を維持しながら誤報率が1ppmレベルに低減されていること、
を特徴とする。
【0004】
しかしながら、実際の用途においては検出率がより高いことが望ましい。特に、平均検出率を98%超にまで高めると共に、ノイズ及びヒストグラム等化の変更に対するロバスト性も大幅に向上させることが望ましい。
【0005】
[発明の概要]
第1の態様によれば、本発明は、添付の特許請求の範囲の請求項1に定義されている、画像の表現を導出する方法を提供する。
【0006】
本発明のさらなる態様は、本発明の第1の態様による方法を用いて導出される画像の表現の使用と、本発明の第1の態様による方法を実施する装置と、命令(実行されると本発明の第1の態様による方法を実施するもの)を含むコンピュータ可読記憶媒体とを含む。
【0007】
本発明の実施の形態の好ましい特徴及び任意選択の特徴は従属請求項に記載されている。
【0008】
本発明は、画像のトレース変換(又は画像の2次元関数であって等価なもの)から視覚的な識別特徴を抽出する新規の方法に関する。本方法は、識別子を抽出する前に、例えばフーリエ変換の振幅によって画像のトレース変換に対して領域ベースの処理を行うことによって、画像の複数解像度の表現を作成するのに用いることができる。
【0009】
本出願において、用語「汎関数」は、その通常の数学的意味を有する。特に、汎関数とは、ベクトル空間V上の(通常は関数の)実数値関数である。トレース変換の場合、汎関数は画像内の線に適用される。
【0010】
同時係属中の欧州特許出願EP06255239.3に記載されている方法では、トレース変換は、画像を直線でトレースすることによって計算され、該直線に沿って、画像輝度の特定の汎関数T又は色関数が計算される。異なる複数の汎関数Tが用いられて単一の入力画像から異なる複数のトレース変換が生成される。2D平面において線は2つのパラメータ、すなわち距離d及び角度θによって特徴付けられるため、画像のトレース変換は各トレース線のパラメータの2D関数である。次に、トレース変換の列に沿ってダイアメトリカル汎関数(diametrical functional) Pを適用することによって「サーカス関数(circus function)」が計算される。サーカス関数の周波数表現(例えばフーリエ変換)が得られ、周波数振幅成分に関して関数が定義され、その符号がバイナリ記述子として取られる。
【0011】
本発明の実施の形態による方法は、同様の技法を用いて画像の表現を導出することができる。しかしながら、画像の表現(例えばバイナリ記述子)を導出するさらなるステップを行う前に、低減された解像度のトレース変換等の、画像の低減された解像度の関数が導出される。解像度の低減は、処理されるデータ量を低減しながら画像に特有の必須要素(すなわちその視覚的な識別特徴)を維持するべきである。通常、導出される画像の低減された解像度の関数は、以下の記載から明らかになるように、演算によって、画像の選択される部分又はサンプリングされる部分の表現値を組み込む。
【0012】
本発明の一実施の形態によれば、画像の低減された解像度の関数は、線のセット(これらの線のパラメータは、所定の区間Δd及び/又はΔθのものである)を用いて画像をトレースすることと、(画像を横切るすべての線の代わりに)線のセットのすべてを用いてトレース変換(又は等価物)を導出することとによって導出される。線は、画像領域における帯(図10に示すもの)及び/又は2つの錐(図11に示すもの)に対応し得る。したがって、より詳細に後述するように、画像の低減された解像度の(すなわちより粗い解像度の)トレース変換が導出される。
【0013】
本発明の別の実施の形態によれば、最初に、従来のように画像を横切るすべての線をトレースすることによってトレース変換(又は等価物)が導出される。次いで、角度パラメータθの異なる値における複数の帯を用いて画像のトレース変換がトレースされ、(図12に示すような)距離パラメータdの複数の区間にわたって解像度の低減が行われ、且つ/又は、距離パラメータdの異なる値における複数の帯を用いてトレース変換がトレースされ、トレース領域において(図13に示すような)角度パラメータθの複数の区間にわたって解像度の低減が行われ、より詳細に後述するように画像の低減された解像度の2次元関数が導出される。
【0014】
有利には、以下でさらに詳細に説明するように、トレース変換領域内の帯及び/又は錐に沿ってトレース変換値を暗黙的に計算することによって、本発明のこの実施の形態の方法を非常に効率的に実施することができる。
【0015】
同時係属中の欧州特許出願EP06255239.3に開示されている方法のように、本発明の一実施の形態による方法は、異なる複数の汎関数を用いることによって得られる識別子「族」の選択部分を組み合わせる。さらに、いくつかの実施形態では、帯及び/又は2つの錐を用いて得られる識別子は組み合されて単一の記述子になる。さらに、いくつかの実施形態において、幅が異なる複数の帯及び/又は開口角が異なる複数の錐が用いられて、複数解像度の表現が得られる。
【0016】
添付図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【0017】
【図1a】画像を示す。
【図1b】図1aの画像を縮小した変形を示す。
【図1c】図1aの画像を回転させた変形を示す。
【図1d】図1aの画像をぼかした変形を示す。
【図2】画像と、従来技術によるその画像のビットストリング表現とを示す。
【図3】本発明の一実施形態の方法のステップを示す図である。
【図4】本発明の一実施形態の別の方法のステップを示す図である。
【図5】トレース変換の線パラメータ化を示す図である。
【図6】(a)〜(c)は、画像の異なるバージョンから導出される関数を示す。
【図7】本発明の一実施形態による装置のブロック図である。
【図8】複数のトレース変換を用いる一実施形態を示すブロック図である。
【図9】図8の実施形態によって作成されるビットストリームを示す図である。
【図10】トレース変換のdパラメータを分解するときの原画像内の区間帯を示す。
【図11】トレース変換のθパラメータを分解するときの原画像における2つの錐を示す。
【図12】dパラメータにおけるトレース変換の分解を示す。
【図13】θパラメータにおけるトレース変換の分解を示す。
【発明を実施するための形態】
【0018】
[実施形態の詳細な説明]
画像の表現(具体的には画像識別子)を導出すると共に、このような表現/識別子を(例えば、1つ又は複数の画像の識別、照合又は検証の目的で)用いるさまざまな実施形態を以下に記載する。本発明は画像の識別に特に有用であるが、これには限定されない。記載される実施形態では、「画像識別子」(ときに「識別子」と単純化される)は画像の表現の一例であり、この用語は画像の表現、すなわち記述子を指すために用いられるに過ぎない。
【0019】
当業者であれば、本発明の一実施形態による画像識別装置及び方法の具体的な設計と、画像識別に用いる画像識別子の導出とは、設計要件によって決定されることを理解しよう。このような設計要件は、画像識別子がロバストであるべき画像変更のタイプ、識別子のサイズ、抽出及び照合の複雑度、目標誤報率等に関連する。
【0020】
以下の実施形態は、画像に対する以下の変更にロバストな識別子をもたらす一般的設計を示す(これは網羅的なリストではない)。
・色数削減
・ぼかし
・明るさの変更
・反転(左右及び上下)
・グレースケール変換
・ヒストグラム等化
・JPEG圧縮
・ノイズ
・回転
・拡大縮小
【0021】
この一般的設計は通常、広範な画像に対して百万分の1(ppm)という非常に低い誤報率を達成することができることが分かっている。
【0022】
図1は、画像及びその画像を変更した変形の一例を示す。より具体的には、図1aは原画像であり、図1bは図1aの画像を縮小したバージョンであり、図1cは図1aの画像を回転させたバージョンであり、図1dは図1aの画像をぼかしたバージョンである。
【0023】
本発明の一実施形態は、画像に対応する信号を処理することによって、画像の表現、より具体的には画像識別子を導出する。
【0024】
図3は、本発明の一実施形態による画像識別子を導出する方法の各ステップ、すなわち識別子抽出工程を示す。
【0025】
抽出の初期段階において画像を前処理する。これは、画像をサイズ変更し(ステップ110)、任意選択でフィルタリングする(ステップ120)ことによって行われる。サイズ変更ステップ110は、画像を処理前に正規化するために用いられる。ステップ120は、画像に対して行われた何らかの処理によって生じるエイリアシング等の効果を除去するためのフィルタリングを含み得、及び/又は、原画像全体を用いるのではなく領域を選択することを含み得る。本方法の好適な一実施形態では、画像の中央から円形領域がさらなる処理のために抽出される。
【0026】
ステップ130において、トレース変換
【0027】
【数1】
【0028】
を行う。トレース変換は、全ての可能な線を画像に射影し、これらの線に1つ又は複数の汎関数を適用する。上述のように、汎関数とは、ベクトル空間V上の実数値関数であり、、通常は関数の実数値関数である。トレース変換の場合、画像中の複数の線に汎関数が適用される。図5に示されるように、線は2つのパラメータd及びθによってパラメータ化される。後述のように、ステップ140においてトレース変換の結果を分解してその解像度を低減することができる。ステップ150において、トレース変換の各列にさらなる汎関数を適用して、実数値ベクトルを得ることができる。この第2の汎関数はダイアメトリカル汎関数(diametrical functional)として知られ、結果として得られるベクトルはサーカス関数として知られる。第3の汎関数であるサーカス汎関数をサーカス関数に適用して、単一の数を得ることができる。この結果の特性は、これら3つの異なる汎関数(トレース汎関数、ダイアメトリカル汎関数及びサーカス汎関数)を適切に選択することによって制御することができる。画像及び対応するトレース変換の例を含むトレース変換の全詳細は、例えば、以下の参考文献[1]:参照により本明細書に援用されるAlexander Kadyrov及びMaria Petrou著「The Trace Transform and its Applications」(IEEE Trans. PAMI, 23(8), 2001年8月、 pp 811-828)に見ることができる。この実施形態の方法では、1Dサーカス関数を得るために、最初の2つのステップのみをトレース変換において行う。
【0029】
本方法の1つの特定の例において、画像のトレース変換
【0030】
【数2】
【0031】
はトレース汎関数T
【0032】
【数3】
【0033】
を用いて抽出され、サーカス関数はダイアメトリカル汎関数P
【0034】
【数4】
【0035】
を適用することによって得られる。
【0036】
サーカス関数が様々な画像処理操作によって受ける影響の例を図6に見ることができる。図6は、画像の様々な変形に対応するサーカス関数を示す。図6(a)は原画像に対応し、図6(b)はその画像を回転させたバージョンに対応し、図6(c)はその画像をぼかしたバージョンに対応する。回転は関数をシフトさせる(と共にスケール変化を生じる)ことが分かる。
【0037】
上で挙げた大部分の画像の変更操作に関して、汎関数T、Pを適切に選択すれば、画像aのサーカス関数f(a)は、変更された画像a’のサーカス関数f(a’)がシフト又は(振幅が)拡大縮小された変形に過ぎないことを示すことができる(以下の参考文献[1]の第3章を参照)。
【0038】
【数5】
【0039】
同時係属中の欧州特許出願EP06255239.3に記載されている方法によれば、サーカス関数の周波数表現の周波数成分を用いて画像識別子を導出することができる。画像記述子を導出する他の技法が可能であると共に、本発明と併せて用いることができることは理解されよう。一例では、画像識別子は、サーカス関数のフーリエ変換(又は同様にハール変換)から導出することができる。
【0040】
したがって、式(3)のフーリエ変換を行うことによって、次式が与えられる。
【0041】
【数6】
【0042】
次に、式(6)の振幅を取ると次式が得られる。
【0043】
【数7】
【0044】
式(7)から、この時点では、変更された画像と原画像とはスケーリング係数κを除いて同じであることが分かる。
【0045】
本実施形態によれば、ここで、フーリエ変換係数の複数の振幅係数について関数c(ω)が定義される。この関数の1つの例示は、各係数とその隣の係数との間の差分を取ることである。
【0046】
【数8】
【0047】
結果として得られるベクトル(式8)に、以下のように閾値を適用することによってバイナリストリングを抽出することができる。(すべてのωについて)
【0048】
【数9】
【0049】
次に、これらの値B={b0,...,bn}から画像識別子が構築される。
【0050】
2つの異なる識別子B1及びB2(いずれも長さN)の間で識別子の照合を行うために、正規化ハミング距離を取る。
【0051】
【数10】
【0052】
ここで、
【0053】
【数11】
【0054】
は排他的OR(XOR)演算子である。識別子又は表現の他の比較方法も用いることができる。
【0055】
識別子中の特定ビットの選択によって性能をさらに高めることができる。より低い周波数に対応するビットは一般にロバスト性がより高く、より高い周波数に対応するビットは識別性がより高い。本発明の特定の一実施形態では最初のビットを無視し、識別子は続く64ビットから成る。
【0056】
本発明の一実施形態によれば、トレース変換(又は等価物)からもたらされる、画像の2次元関数を分解するステップ140は、その解像度を低減することを含む。解像度の低減は、その2つの次元d若しくはθのうちのいずれか又は双方の次元において処理することによって達成することができる。
【0057】
したがって、図12のように、dパラメータをサブサンプリングすることによって、例えば(θの値に対応する)列に沿ってdの複数の区間にわたって総和をとるか又は積分することによって、「トレース領域」における距離次元において解像度を低減することができる。これは、図10に示されるように、トレース変換中に幅Δdの帯を画像に(すなわち画像領域内に)射影することに対応する。距離パラメータdの複数の区間にわたってサブサンプリングする(すなわちトレース変換の解像度を低減する)任意の技法を用いることができることは理解されよう。したがって、データの本質を維持しながらデータの量を低減する任意の統計的計算を用いることができ、総和をとること及び積分はその例に過ぎない。
【0058】
代替的に又は付加的に、図13のように、θパラメータをサブサンプリングすることによって、例えば(dの値に対応する)行に沿ってθの複数の区間にわたって総和をとること又は積分することによって、「トレース領域」における角度次元において解像度を低減することができる。これは図11に示されるように、トレース変換の間に開口角Δθを有する2つの錐を画像に(すなわち画像領域内に)射影することとほぼ等価である。角度パラメータθの複数の区間にわたってサブサンプリングする(すなわちトレース変換の解像度を低減する)任意の技法を用いることができることは理解されよう。したがって、データの本質を維持しながらデータの量を低減する任意の統計的計算を用いることができ、総和をとること及び積分はその例に過ぎない。
【0059】
本発明の別の実施形態によれば、分解するステップ140は、「画像領域」において行うことができ、すなわち、ステップ120の後に且つ通常図3のステップ130と組み合わせて行うことができる。一例では、ステップ140は、画像自体の中の線のセットを結合又は分解すると共に、これらの線に対してトレース変換(又は他の演算)を行って画像識別子を導出する。例えば、画像の複数の線をステップ130において共に効率的に処理することができるように、1画素幅の画像の線を結合することができる。線のセットは例えば、図10に示されるような平行線及び/又は図11に示されるような2つの錐によって規定される線とすることができる。結合される線の数は上述の区間に対応する。したがって、この実施形態では、トレース変換は、従来のトレース変換のように画像を横切るすべての線をトレースする代わりに、画像を横切る線の選択されたセットをトレースするように有効に変更される。
【0060】
当業者には理解されるように、画像領域において分解する他の技法が可能である。
【0061】
上記の方法を行う本発明の一実施形態による装置の一例を図7に示す。具体的には、画像記憶モジュール210によって画像200が受け取られ、画像データベース230に記憶される。さらに、識別子抽出及び記憶モジュール220が、本発明の方法に従って、受け取った画像毎に画像識別子を抽出し、それらの画像識別子を識別子データベース240に、(任意選択で、画像のコンテンツに関連する他の情報と共に)適宜記憶する。
【0062】
図7はさらに、上記の方法を用いて抽出された画像識別子を用いる画像検索エンジンを具現する装置を示す。画像の検証又は照合が、問い合わせ画像250の受け取りに応答して画像検索エンジンによって行われ得る。本発明の方法に従って、問い合わせ画像250の画像識別子が識別子抽出モジュール260において抽出される。識別子照合モジュール270が問い合わせ画像250の画像識別子を、識別子データベース240に記憶されている画像識別子と比較する。画像検索モジュール280が、画像データベース230から一致画像290を取り出す。この一致画像290は、以下で詳述するように、問い合わせ画像識別子と一致する画像識別子を有する。
【0063】
図4は、フーリエ変換係数に対するバイナリ関数を定義する代替的な方法を示す。特に、フーリエ変換係数を得た(ステップ171)後、複数のフーリエ変換係数の振幅の対数を得る(ステップ172及び173)。以降の係数の差分を上記の式(8)と同様に計算し(ステップ174)、その後、この差分の符号を取り、この符号によってバイナリ値を割り当てる(ステップ175)。次に、このバイナリ値を用いてバイナリ識別子を形成する。画像の関数の他の周波数表現(ハール変換を含む)の周波数係数にこの技法を用いることができることは理解されよう。
【0064】
上述した基本識別子は、図8及び図9に示すように、低減された解像度のトレース変換を複数用いてそれぞれの識別子を導出することと、別々の識別子からのビットを組み合わせることとによって改良することができる。低減された解像度のトレース変換の別々のものからのバイナリストリング361及び362を組み合わせる具体的な方法は、それらを連結して識別子363を得ることである。
【0065】
このようにして、上記の式(1)のトレース汎関数Tを、上記の式(2)によって与えられるダイアメトリカル汎関数Pと共に用いて1つのバイナリストリングを得た後、トレース汎関数(1)をダイアメトリカル汎関数(11)
【0066】
【数12】
【0067】
と共に用いて第2のストリングを得ることによって良好な結果を得ることができる。各バイナリストリングの最初のビットはスキップし、両方のストリングからの次の64ビットを連結して128ビットの識別子を得る。
【0068】
本発明によれば、トレース変換における複数解像度の表現を用いることによって大幅な性能改良を得ることができる。特に、1つ又は2つの次元において分解を行うことができる。次いで上記のように、ダイアメトリカル汎関数を適用してバイナリストリングを抽出することができる。通常の結果は、この分解を用いることによって百万分の1の誤報率(false error rate)における検出率が約80%から98%に高められることを示す。
【0069】
この複数解像度のトレース変換は、上述のように、その2つの次元d若しくはθのうちのいずれか又は双方の次元において元のトレース変換をサブサンプリングしてその解像度を低減することによって生成することができる。「トレース領域」においてdパラメータのサブサンプリングは、例えば図12のように列に沿って複数の区間にわたって積分することによって行われる。これは、図10に示されるように、トレース変換中に幅Δdの帯を画像に射影することに対応する。サブサンプリングは、例えばθパラメータにおける複数の区間にわたって、すなわち行に沿って積分することによって行うこともできる。図13を参照されたい。これは、トレース変換中に開口角Δθを有する2つの錐にわたって積分することとほぼ同じである。図11を参照されたい。代替的に、上述のようにこれらの演算を「画像領域」において行うことができる。
【0070】
複数解像度分解を用いることによって、1つのトレース変換から複数の基本識別子を抽出することができる。ここで、ある範囲内の異なる区間幅にわたってサブサンプリングが行われて、複数の基本識別子から成る複数解像度の表現が生成される。理想的には、複数解像度の表現はある範囲内の区間幅を用いて導出される複数の識別子を用いる。例えば、各区間幅は他の区間幅と少なくとも2倍異なってもよい。トレース変換の出力のサイズが600×384であり、したがってdパラメータが幅8、16、32、64及び128の帯(band)を用いて積分することによってサブサンプリングされ、同様にθパラメータが例えば幅3、6、12、及び24の帯を用いて積分することによってサブサンプリングされるシステムを用いることによって、良好な結果が一般的に得られた。
【0071】
この識別子の1つの応用は、画像検索エンジンとしての応用である。ファイル名、画像、撮影者、取得日時、及び任意の他の有用な情報等の関連する情報と共に、バイナリ識別子を抽出し記憶することによって、データベースが構築される。次に、問い合わせ画像aqが与えられると、バイナリ識別子が抽出され、データベース中の全ての識別子B0...BMと比較される。問い合わせ画像に対するハミング距離が閾値未満である全ての画像が返される。
【0072】
[代替的な実施態様]
様々な異なるトレース汎関数及びダイアメトリカル汎関数を用いることができ、例として以下が挙げられる(網羅的でないリスト)。
【0073】
【数13】
【0074】
2つ又はそれ以上の識別子を組み合わせて、画像をより正確に特徴付けすることができる。この組み合わせは、複数の識別子の連結によって行われることが好ましい。
【0075】
回転、平行移動及び拡大縮小より高次の幾何変換の場合、上述した識別子のバージョンは適切でなく、式(3)の関係は成り立たない。識別子のロバスト性は、正規化工程を用いるアフィン変換まで拡張することができる。この正規化工程の全詳細は、以下の参考文献[2]に見ることができる。サーカス関数を正規化するために2つのステップが導入され、最初のステップは、いわゆる関連サーカス(associated circus)を求めることを含み、2番目のステップは、正規化された関連サーカス関数を求めることを含む。この正規化に続き、式(3)の関係が真であることが示される。これによって、上記と同様に識別子の抽出工程を継続することができる。
【0076】
正規化工程と共に用いられるいくつかの適切なトレース汎関数が以下の(G1)及び(G2)に与えられ、ダイアメトリカル汎関数の適切な選択が(G3)に与えられる。
【0077】
【数14】
【0078】
ここで、r≡t−cであり、c≡median({tk}k,{|g(tk)|}k)である。非負の重みw1,w2,...,wnを有する数列y1,y2,...,ynの加重中央値を、この数列が重みによって昇順でソートされると仮定した場合に次式が成り立つ最大インデックスmを特定することによって定義する。
【0079】
【数15】
【0080】
不等式(12)が厳密(strict)である場合、中央値はymとなる。しかし、不等式が等式である場合、中央値は(ym+ym-1)/2となる。
【0081】
識別子を連続するビットのブロックから構築する代わりに、実験によって選択を行うことができる。このやり方の一例は、i)独立した画像と、ii)原画像及び変更された画像との2組のデータを用意することである。識別子の性能は、独立したデータの誤受入率と、原画像及び変更された画像の誤拒否率とを比較することによって測定することができる。関心となる点は、等価エラー率、すなわち、1×10-6の誤受入率における誤拒否率である。最適化は、ビットが選択されていない状態で開始される。各ビットを1つずつ検査して、どのビットが(例えば等価エラー率又は何らかの類似の測度に関して)最良の性能を発揮するかを確かめることが可能である。最良の結果を与えるビットが選択されるべきである。次に、全ての残りのビットを試験して、どれが最初のビットと組み合わせた際に最良の性能を発揮するかを確かめるべきである。ここでもまた、エラー率が最低のビットが選択される。この手順は、全てのビットが選択されるまで繰り返される。このように、全体として最良の性能をもたらすビットの組み合わせを求めることができる。
【0082】
上記で示したように、パラメータ(d又はθ)の複数の区間にわたって総和をとること又は積分することによって、トレース変換における複数解像度分解を形成することができる。上記で示したように、任意の統計的技法を用いて分解又は解像度低減を達成することができ、他の可能性は、平均値、最大値、最小値等のような統計値を計算することを含む。他の汎関数をこれらの区間に適用することもできる。
【0083】
さらに、構造を識別子に適用して検索性能を高めることもできる。例えば、2パス探索を実施し、1回目の探索に半分のビットを用い、次に所与のレベルの精度を有するビットのみを2回目の探索パスに認める。
【0084】
リード・マラー(Reed-Muller)復号器又はウイナー・ジブ(Wyner-Ziv)復号器等の方法を用いて識別子を圧縮し、さらにサイズを縮小することができる。
【0085】
[代替的な応用]
識別子はまた、ビデオシーケンス中のフレームをインデックス付けするために用いることもできる。新たなシーケンスが与えられると、フレームから識別子を抽出し、次に、同一のシーケンスを見つけるために検索を行うことができる。これは、著作権の検出及びシーケンスの識別のために有用であり得る。
【0086】
複数の放送会社が同一のコンテンツ、例えば広告又は株式ニュースの映像を送信する場合が多い。放送会社間のナビゲーションのために、識別子を用いてこれらのコンテンツ間にリンクを形成することができる。
【0087】
画像識別子は、画像を介してコンテンツを結びつける機会を提供する。ユーザがウェブページ上の特定の画像に興味がある場合、同一画像を有する他のページを見つける有効な方法はない。識別子を用いて、画像間のナビゲーション経路を提供することができる。
【0088】
識別子を用いてブロードキャストフィード中の広告を検出することができる。これを用いて、広告主が自社のキャンペーンを追跡するための自動監視を行うことができる。
【0089】
大規模な商用集合からパーソナルコンピュータ上の小規模なコレクションまで多くの画像データベースが存在する。データベースが厳格に制御されていない限り、通常は集合の画像に重複があり、余分な記憶領域を無駄に必要とする。識別子は、これらのデータセット中の重複画像を削除又は紐付けするツールとして用いることができる。
【0090】
本明細書中、「画像」という用語は、画像単位(フィルタリング、解像度の変更、アップサンプリング、ダウンサンプリング等の処理の後のものを含む)を記述するために用いられるが、他の類似の用語(フレーム、フィールド、ピクチャ、又は、画像・フレーム等のサブユニット若しくは領域等)にも当てはまる。本明細書中、画像という用語は、文脈から明らかである場合を除き、画像全体又は画像の領域を意味する。同様に、画像の領域は画像全体を意味し得る。画像は、フレーム又はフィールドを含み、静止画、又はフィルムに関連し、または、ビデオ等の画像シーケンス中の画像に関連し、または、関連する画像のグループ中の画像に関連する。画像は、グレースケール画像又はカラー画像であってもよく、又は別のタイプのマルチスペクトル画像(例えば、IR、UV若しくは他の電磁波画像)であってもよく、又は音響画像であってもよく、他の画像であってもよい。
【0091】
実施形態において、周波数表現は、フーリエ変換を用いて導出されるが、周波数表現は、ハール変換等の他の技法を用いて導出することもできる。特許請求の範囲において、フーリエ変換という単語は、DFT及びFFT等の変形を網羅するものとする。
【0092】
本発明は、適切な装置を用いて電気的信号を処理することによって実施されることが好ましい。
【0093】
本発明は、例えば、適切なソフトウェア及び/又はハードウェアの変更を加えたコンピュータシステムにおいて実施することができる。例えば、本発明は、制御手段若しくは処理手段(プロセッサ若しくは制御装置等)、データ記憶手段(メモリ、磁気記憶装置、CD、DVD等のような画像記憶手段を含む)、データ出力手段(ディスプレイ、モニタまたはプリンタ等)、データ入力手段(キーボード等)、及び画像入力手段(スキャナ等)を有する、又はこれらの構成要素の任意の組み合わせを他の付加的な構成要素と共に有する、コンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェア及び/若しくはハードウェアの形態、又は特定用途向け装置において提供することができ、又は、チップ等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置におけるシステムの構成要素は、他の構成要素から離れた場所に、例えばインターネットを介して設けられてもよい。
【0094】
[参考文献]
[1]Alexander Kadyrov及びMaria Petrou著「The Trace Transform and Its Applications」(IEEE Trans. PAMI, 23 (8), 2001年8月, pp 811-828)
[2]Maria Petrou及びAlexander Kadyrov著「Affine Invariant Features from the Trace Transform」(IEEE Trans, on PAMI, 26 (1), 2004年1月, pp 30-44)
【0095】
当業者であれば理解するように、説明した実施形態に対して多くの変形及び変更を行うことができる。例えば、本発明を、当業者に既知の既存の技法及び関連技法を組み合わせて実施する実施形態において実施することができる。添付の特許請求の範囲に規定される本発明の範囲に入る、説明した実施形態に対するそのような変形、変更及び均等物を全て含むことが意図される。
【特許請求の範囲】
【請求項1】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
前記画像又は前記画像の2次元関数を処理することであって、それによって前記画像の低減された解像度における2次元関数を得る、前記画像又は前記画像の2次元関数を処理することと、
前記画像の前記低減された解像度の2次元関数を用いることであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の2次元関数を用いることと、
を含む、方法。
【請求項2】
前記画像又は前記画像の2次元関数を処理するステップは、前記画像の前記2次元関数のパラメータのうち少なくとも1つのパラメータの所定の区間にわたって、前記画像の値をサブサンプリングすることを含む、請求項1に記載の方法。
【請求項3】
前記サブサンプリングすることは、前記画像又は前記画像の関数の値に対して、前記画像又は前記画像の2次元関数のパラメータのうち少なくとも1つのパラメータの所定の区間にわたって、統計的計算を行うこと、好ましくは総和又は積分を行うことを含む、請求項2に記載の方法。
【請求項4】
前記処理するステップは、前記画像内の線のセットを用いて前記画像を処理することを含む、請求項1、2又は3に記載の方法。
【請求項5】
前記線のセットは、
前記画像の前記2次元関数の第1のパラメータの区間の1つによって規定される帯、及び
前記画像の前記2次元関数の第2のパラメータの区間の1つによって規定される2つの錐
の一方又は複数に対応する、請求項4に記載の方法。
【請求項6】
前記処理することは、前記線のセットに汎関数を適用することであって、それによって、前記画像の前記低減された解像度の2次元関数を導出する、前記線のセットに汎関数を適用することを含む、請求項4又は5に記載の方法。
【請求項7】
前記処理するステップは、前記画像の前記2次元関数の第1の次元の所定の区間にわたって前記2次元関数の値をサブサンプリングすることによって、前記画像の2次元関数を処理することを含み、それによって、前記第1の次元における前記画像の前記2次元関数の前記解像度を低減する、請求項1、2又は3に記載の方法。
【請求項8】
前記処理するステップは、前記画像の前記2次元関数の第2の次元における所定の区間にわたって前記2次元関数の値をサブサンプリングすることによって、前記画像の2次元関数を処理することを含み、それによって、前記第2の次元における前記画像の前記2次元関数の前記解像度を低減する、請求項1、2、3又は7に記載の方法。
【請求項9】
前記画像の前記2次元関数は、前記画像のすべての線に対して汎関数を適用することによって導出される前記画像のトレース変換を含み、
前記2次元関数は、距離パラメータ及び角度パラメータを有するトレース領域における前記画像の値を規定する、請求項7又は8に記載の方法。
【請求項10】
前記画像の前記低減された解像度の2次元関数を用いる前記ステップであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の2次元関数を用いる前記ステップは、前記画像の1次元関数を導出することを含む、請求項1〜9のいずれか一項に記載の方法。
【請求項11】
前記方法は、前記画像のさらなる関数を導出することをさらに含み、
前記画像の平行移動、拡大縮小又は回転させたバージョンの前記さらなる関数は、前記画像の前記さらなる関数の平行移動又は拡大縮小させたバージョンである、請求項1〜10のいずれか一項に記載の方法。
【請求項12】
前記1次元関数又は前記さらなる関数は、サーカス関数であるか、又はサーカス関数から導出される関数である、請求項10又は11に記載の方法。
【請求項13】
前記画像の前記低減された解像度の2次元関数を用いる前記ステップであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の2次元関数を用いる前記ステップは、前記1次元関数又は前記さらなる関数の周波数表現の複数の周波数成分を用いることであって、それによって前記画像の表現を導出する、前記1次元関数又は前記さらなる関数の周波数表現の複数の周波数成分を用いることを含む、請求項10、11又は12に記載の方法。
【請求項14】
前記周波数成分はフーリエ変換又はハール変換を用いて求められる、請求項13に記載の方法。
【請求項15】
前記画像の前記表現は、
複数の周波数係数の前記振幅又は前記振幅の対数を計算するステップと、
各係数の前記振幅又は前記振幅の対数と、前記係数の次の係数の前記振幅又は前記振幅の対数との間の差分を求めるステップと、
を用いて導出される、請求項13又は14に記載の方法。
【請求項16】
前記方法は、求められた差分のそれぞれに閾値を適用することであって、それによって一連のバイナリ値を導出する、求められた差分のそれぞれに閾値を適用することをさらに含み、
前記閾値を適用することは、前記差分が0未満である場合には0のバイナリ値を提供し、前記差分が0以上である場合には1のバイナリ値を提供する、請求項15に記載の方法。
【請求項17】
前記画像表現は、前記複数の周波数成分の前記振幅又は前記振幅の対数によって規定される前記バイナリ値を含む、請求項16に記載の方法。
【請求項18】
前記方法は、前記区間についてある範囲内の異なる幅にわたって前記処理するステップを行うと共に前記複数の表現を組み合わせて複数解像度の表現を生成することによって、前記画像の複数の表現を導出することを含む、請求項1〜17のいずれか一項に記載の方法。
【請求項19】
前記異なる区間幅は、互いに少なくとも2倍異なる、請求項18に記載の方法。
【請求項20】
画像を識別する方法であって、
請求項1〜19のいずれか一項に記載の方法を用いて前記画像の表現を導出することと、
前記表現と前記画像とを関連付けることと、
を含む、方法。
【請求項21】
画像を比較する方法であって、請求項1〜20のいずれか一項に記載の方法を用いて導出される各画像の表現を比較することを含む、方法。
【請求項22】
前記比較することはハミング距離を求めることを含む、請求項21に記載の方法。
【請求項23】
表現の比較に基づいて画像を選択することを含む、請求項21又は22に記載の方法。
【請求項24】
請求項1〜19のいずれか一項に記載の方法を用いて導出される画像の表現の使用であって、送信、受信又は処理を含む使用。
【請求項25】
請求項1〜23のいずれか一項に記載の方法を実行する装置。
【請求項26】
実行されると請求項1〜23のいずれか一項に記載の方法を実施する命令を含む、コンピュータ可読媒体。
【請求項1】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
前記画像又は前記画像の2次元関数を処理することであって、それによって前記画像の低減された解像度における2次元関数を得る、前記画像又は前記画像の2次元関数を処理することと、
前記画像の前記低減された解像度の2次元関数を用いることであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の2次元関数を用いることと、
を含む、方法。
【請求項2】
前記画像又は前記画像の2次元関数を処理するステップは、前記画像の前記2次元関数のパラメータのうち少なくとも1つのパラメータの所定の区間にわたって、前記画像の値をサブサンプリングすることを含む、請求項1に記載の方法。
【請求項3】
前記サブサンプリングすることは、前記画像又は前記画像の関数の値に対して、前記画像又は前記画像の2次元関数のパラメータのうち少なくとも1つのパラメータの所定の区間にわたって、統計的計算を行うこと、好ましくは総和又は積分を行うことを含む、請求項2に記載の方法。
【請求項4】
前記処理するステップは、前記画像内の線のセットを用いて前記画像を処理することを含む、請求項1、2又は3に記載の方法。
【請求項5】
前記線のセットは、
前記画像の前記2次元関数の第1のパラメータの区間の1つによって規定される帯、及び
前記画像の前記2次元関数の第2のパラメータの区間の1つによって規定される2つの錐
の一方又は複数に対応する、請求項4に記載の方法。
【請求項6】
前記処理することは、前記線のセットに汎関数を適用することであって、それによって、前記画像の前記低減された解像度の2次元関数を導出する、前記線のセットに汎関数を適用することを含む、請求項4又は5に記載の方法。
【請求項7】
前記処理するステップは、前記画像の前記2次元関数の第1の次元の所定の区間にわたって前記2次元関数の値をサブサンプリングすることによって、前記画像の2次元関数を処理することを含み、それによって、前記第1の次元における前記画像の前記2次元関数の前記解像度を低減する、請求項1、2又は3に記載の方法。
【請求項8】
前記処理するステップは、前記画像の前記2次元関数の第2の次元における所定の区間にわたって前記2次元関数の値をサブサンプリングすることによって、前記画像の2次元関数を処理することを含み、それによって、前記第2の次元における前記画像の前記2次元関数の前記解像度を低減する、請求項1、2、3又は7に記載の方法。
【請求項9】
前記画像の前記2次元関数は、前記画像のすべての線に対して汎関数を適用することによって導出される前記画像のトレース変換を含み、
前記2次元関数は、距離パラメータ及び角度パラメータを有するトレース領域における前記画像の値を規定する、請求項7又は8に記載の方法。
【請求項10】
前記画像の前記低減された解像度の2次元関数を用いる前記ステップであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の2次元関数を用いる前記ステップは、前記画像の1次元関数を導出することを含む、請求項1〜9のいずれか一項に記載の方法。
【請求項11】
前記方法は、前記画像のさらなる関数を導出することをさらに含み、
前記画像の平行移動、拡大縮小又は回転させたバージョンの前記さらなる関数は、前記画像の前記さらなる関数の平行移動又は拡大縮小させたバージョンである、請求項1〜10のいずれか一項に記載の方法。
【請求項12】
前記1次元関数又は前記さらなる関数は、サーカス関数であるか、又はサーカス関数から導出される関数である、請求項10又は11に記載の方法。
【請求項13】
前記画像の前記低減された解像度の2次元関数を用いる前記ステップであって、それによって前記画像の前記表現を導出する、前記画像の前記低減された解像度の2次元関数を用いる前記ステップは、前記1次元関数又は前記さらなる関数の周波数表現の複数の周波数成分を用いることであって、それによって前記画像の表現を導出する、前記1次元関数又は前記さらなる関数の周波数表現の複数の周波数成分を用いることを含む、請求項10、11又は12に記載の方法。
【請求項14】
前記周波数成分はフーリエ変換又はハール変換を用いて求められる、請求項13に記載の方法。
【請求項15】
前記画像の前記表現は、
複数の周波数係数の前記振幅又は前記振幅の対数を計算するステップと、
各係数の前記振幅又は前記振幅の対数と、前記係数の次の係数の前記振幅又は前記振幅の対数との間の差分を求めるステップと、
を用いて導出される、請求項13又は14に記載の方法。
【請求項16】
前記方法は、求められた差分のそれぞれに閾値を適用することであって、それによって一連のバイナリ値を導出する、求められた差分のそれぞれに閾値を適用することをさらに含み、
前記閾値を適用することは、前記差分が0未満である場合には0のバイナリ値を提供し、前記差分が0以上である場合には1のバイナリ値を提供する、請求項15に記載の方法。
【請求項17】
前記画像表現は、前記複数の周波数成分の前記振幅又は前記振幅の対数によって規定される前記バイナリ値を含む、請求項16に記載の方法。
【請求項18】
前記方法は、前記区間についてある範囲内の異なる幅にわたって前記処理するステップを行うと共に前記複数の表現を組み合わせて複数解像度の表現を生成することによって、前記画像の複数の表現を導出することを含む、請求項1〜17のいずれか一項に記載の方法。
【請求項19】
前記異なる区間幅は、互いに少なくとも2倍異なる、請求項18に記載の方法。
【請求項20】
画像を識別する方法であって、
請求項1〜19のいずれか一項に記載の方法を用いて前記画像の表現を導出することと、
前記表現と前記画像とを関連付けることと、
を含む、方法。
【請求項21】
画像を比較する方法であって、請求項1〜20のいずれか一項に記載の方法を用いて導出される各画像の表現を比較することを含む、方法。
【請求項22】
前記比較することはハミング距離を求めることを含む、請求項21に記載の方法。
【請求項23】
表現の比較に基づいて画像を選択することを含む、請求項21又は22に記載の方法。
【請求項24】
請求項1〜19のいずれか一項に記載の方法を用いて導出される画像の表現の使用であって、送信、受信又は処理を含む使用。
【請求項25】
請求項1〜23のいずれか一項に記載の方法を実行する装置。
【請求項26】
実行されると請求項1〜23のいずれか一項に記載の方法を実施する命令を含む、コンピュータ可読媒体。
【図1a】
【図1b】
【図1c】
【図1d】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図1b】
【図1c】
【図1d】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公表番号】特表2010−515991(P2010−515991A)
【公表日】平成22年5月13日(2010.5.13)
【国際特許分類】
【出願番号】特願2009−545215(P2009−545215)
【出願日】平成19年12月6日(2007.12.6)
【国際出願番号】PCT/GB2007/004676
【国際公開番号】WO2008/084185
【国際公開日】平成20年7月17日(2008.7.17)
【出願人】(501253316)ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC R&D CENTRE EUROPE B.V.
【住所又は居所原語表記】20 Frederick Sanger Road, The Surrey Research Park, Guildford, Surrey GU2 5YD, Great Britain
【Fターム(参考)】
【公表日】平成22年5月13日(2010.5.13)
【国際特許分類】
【出願日】平成19年12月6日(2007.12.6)
【国際出願番号】PCT/GB2007/004676
【国際公開番号】WO2008/084185
【国際公開日】平成20年7月17日(2008.7.17)
【出願人】(501253316)ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC R&D CENTRE EUROPE B.V.
【住所又は居所原語表記】20 Frederick Sanger Road, The Surrey Research Park, Guildford, Surrey GU2 5YD, Great Britain
【Fターム(参考)】
[ Back to top ]