画像識別子抽出装置
【課題】画像識別子を照合する画像識別子照合装置を提供すること。
【解決手段】画像を識別する情報である画像識別子を照合する照合部を備える。上記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、かつ、当該差分値が所定の値より小さい場合には特定の値に量子化されている。照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも上記特定の値の場合に、各次元の値の少なくとも一方が上記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する。
【解決手段】画像を識別する情報である画像識別子を照合する照合部を備える。上記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、かつ、当該差分値が所定の値より小さい場合には特定の値に量子化されている。照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも上記特定の値の場合に、各次元の値の少なくとも一方が上記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、画像を識別する(同一性を判定する)ための特徴量である画像識別子を抽出する装置に関する。
【背景技術】
【0002】
画像識別子は、画像を識別する(同一性を判定する)ための画像特徴量である。ある画像から抽出した画像識別子と、別の画像から抽出した画像識別子とを比較し、その比較結果から、2つの画像が同一である度合いを示す同一性尺度(一般的には、類似度または距離という)を算出することができる。また、算出した同一性尺度をある閾値と比較することにより、2つの画像が同一であるか否かを判定することができる。ここで「2つの画像が同一」とは、画像信号(画像を構成する画素の画素値)のレベルで2つの画像が同一である場合だけに限らず、画像の圧縮形式(フォーマット)の変換、画像のサイズ・アスペクト比の変換、画像の色調の調整、画像への各種フィルタ処理(鮮鋭化、平滑化など)、画像への局所的な加工(テロップ重畳、切抜きなど)、画像の再キャプチャリング、などの各種改変処理によって、一方の画像が他方の画像の複製された画像である場合も含む。画像識別子を用いれば、例えば、画像、または画像の集合体である動画像の複製を検知できるため、画像または動画像の違法コピー検知システムなどに応用することができる。
【0003】
画像識別子の一例が、特許文献1に記載されている。図18は、特許文献1に記載されている画像識別子の抽出方法を示す図である。この画像識別子は、複数の次元(図18では16次元)の特徴ベクトルである。画像240内のあらかじめ定められた位置の32個の長方形領域244(図18ではそのうち16個の長方形領域が描かれている)からそれぞれ平均輝度値を算出し、対となる長方形領域の間(図18では対となる長方形領域を点線248で結んでいる)で平均輝度値の差を算出し、16次元の差ベクトル250を求める。差ベクトル250に対してベクトル変換により合成ベクトルを生成し、合成ベクトルの各次元を量子化して得られた16次元の量子化インデックスベクトルを画像識別子とする。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特表平8−500471号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
複数の次元の特徴ベクトルで構成される画像識別子は、次元間の相関が小さいほど、特徴ベクトルが持つ情報量が大きい(冗長性が小さい)ので、異なる画像を識別できる度合いである識別能力が高くなる。反対に、特徴ベクトルの次元間の相関が大きいと、特徴ベクトルが持つ情報量が小さい(冗長性が大きい)ので、識別能力が低くなる。ここで次元間の相関とは、次元の特徴量の生起の類似性の度合いであり、数学的には、例えば、各次元の特徴量の生起を確率変数とした場合の、確率変数間の相関係数や、相互情報量として算出できる値である。このため、複数の次元の特徴ベクトルで構成される画像識別子は、次元間の相関が小さくなるように設計されていることが望ましい。
【0006】
画像信号(画像を構成する画素の画素値)は、画像の局所領域間において相関がある。一般的に、局所領域間の距離が近いほど、相関は大きくなる。特に、例えば、ある特定の画像パターンが繰り返し出現する(特にそれが規則正しい周期で出現する場合に)画像(例えば格子状に配置されたビルの窓の画像など、図19(A)を参照)や、ある特定のテクスチャで構成されている画像(図19(B)を参照)などは、画像の局所領域間の相関が大きくなる。
【0007】
[第1の問題点]
特許文献1に記載されているような、画像の複数の局所領域から抽出した特徴量から成る特徴ベクトルで構成されている画像識別子は、画像の局所領域間の相関が大きい画像に対して、各次元において特徴量を抽出する局所領域の形状が同一であるため(特許文献1の例では同一の形状の長方形領域)、抽出される特徴量の次元間の相関が大きくなる。そのため、画像識別子(特徴ベクトル)の識別能力が低くなる、という第1の問題点がある。ここで形状が同一とは、領域の大きさや角度(傾き或いは姿勢)も含めて同一であるということである。
【0008】
例えば、ある特定の画像パターンが繰り返し出現する画像(図19(A)参照)や、ある特定のテクスチャで構成されている画像(図19(B)参照)などに対しては、特許文献1で記載されているような画像識別子は、識別能力が低くなる。
【0009】
[第2の問題点]
特許文献1に記載されている画像識別子の第2の問題点は、特徴量(特徴ベクトル)を算出するための各次元の領域の形状(大きさ、角度も含めて)が同一の長方形であるため、長方形の辺の長さと同じ、あるいは、その整数分の1の周期を持つ周波数成分を検知できないという、周波数上の盲点が存在するということである。その理由は、この特定の周波数の信号成分について領域内で平均をとると、信号成分の大小によらず0となってしまい、その周波数成分の信号を全く検知できなくなるためである。より具体的には、長方形の辺の長さと同じ周期を持つ周波数をf0とすると,周波数nf0(n=1,2,3,…)の成分が検知できなくなる。このため、直流成分とこの周波数成分に信号が集中している画像に対しては、画素値の平均値は直流成分と同じになってしまい、領域間で値の差がなくなる結果、領域間の平均画素値の差として抽出される特徴量は全て0になってしまい、識別できなくなる(識別能力が著しく低下する)。実際には、周波数nf0(n=1,2,3,…)の成分のみではなく、その近傍の一定の周波数領域に対しては同様に検知困難となるため、上記特定周波数に信号成分が集中していなくても、その周波数帯の信号成分が使えないことにより、識別能力が低下する。この問題を軽減するには、周波数f0の値を大きくし、上記検知困難な周波数帯に陥る信号電力を下げることが考えられる。しかしながら、周波数f0の値を大きくすることは、領域の大きさを小さくすることを意味し、特徴量の頑健性(各種改変処理やノイズに対して特徴量が変化しない度合い)の低下につながる。例えば、領域が小さくなることで、多少の位置ずれに対しても、特徴量の値が大きく変化することになり、特徴量の頑健性が下がる。このように、同一の長方形領域を用いる場合には、識別能力をあげた上で頑健性を確保することが極めて難しい。
【0010】
[発明の目的]
本発明の目的は、画像の局所領域間の相関が大きい画像や特定の周波数に信号が集中している画像から抽出される画像識別子は異なる画像を識別できる度合いである識別能力が低下する、という課題を解決する画像識別子抽出装置を提供することである。
【課題を解決するための手段】
【0011】
本発明の一形態にかかる画像識別子抽出装置は、対をなす2つの部分領域の形状の組み合わせと、対をなす2つの部分領域の相対的な位置関係との双方が、他の少なくとも1つの部分領域対と相違する1以上の部分領域対を含む、画像中の複数の部分領域対に従って、画像の各部分領域から領域特徴量を抽出し、該抽出した各部分領域毎の領域特徴量に基づいて、上記画像の識別に用いる画像識別子を生成する画像識別子生成手段と、上記画像識別子を符号化する符号化手段とを備える。
【発明の効果】
【0012】
本発明は上述したように構成されているため、画像識別子の、異なる画像を識別できる度合いである識別能力を高くすることができる。特に、画像の局所領域間の相関が大きい画像に対して、この効果は顕著である。
【0013】
また本発明によれば、特定の周波数に信号が集中している画像に対しても、識別能力が低下しないという効果がある。
【図面の簡単な説明】
【0014】
【図1】本発明の第1の実施の形態のブロック図である。
【図2】次元別抽出情報が示す次元ごとの抽出領域の対の例を示す図である。
【図3】本発明の第1の実施の形態における比較手段の一例を示すブロック図である。
【図4】本発明の第1の実施の形態における比較手段の別の例を示すブロック図である。
【図5】本発明の第1の実施の形態の処理の流れを示すフローチャートである。
【図6】本発明の第2の実施の形態の要部ブロック図である。
【図7】本発明の第2の実施の形態の処理の流れを示すフローチャートである。
【図8】本発明の第3の実施の形態のブロック図である。
【図9】次元ごとの領域特徴量算出方法の例を示す図である。
【図10】本発明の第3の実施の形態の処理の流れを示すフローチャートである。
【図11】本発明の第4の実施の形態のブロック図である。
【図12】次元ごとの比較・量子化方法の例を示す図である。
【図13】本発明の第4の実施の形態の処理の流れを示すフローチャートである。
【図14−a】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−b】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−c】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−d】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−e】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−f】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−g】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−h】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−i】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−j】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図15−a】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−b】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−c】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−d】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−e】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−a】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−b】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−c】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−d】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−e】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図17−a】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−b】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−c】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−d】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−e】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図18】特許文献1に記載されている画像識別子の抽出方法を示す図である。
【図19】局所領域間の相関が大きくなる画像の例を示す図である。
【図20】本発明の第5の実施の形態のブロック図である。
【図21】量子化インデックスベクトルを照合する照合手段のブロック図である。
【図22】量子化インデックスベクトルを照合する照合手段の処理例を示すフローチャートである。
【図23】量子化インデックスベクトルを照合する照合手段の別の処理例を示すフローチャートである。
【図24】量子化インデックスベクトルを照合する照合手段の更に別の処理例を示すフローチャートである。
【図25】量子化インデックスベクトルを照合する照合手段の別の構成のブロック図である。
【図26】量子化インデックスベクトルを照合する照合手段の処理例を示すフローチャートである。
【図27】量子化インデックスベクトルを照合する照合手段の別の処理例を示すフローチャートである。
【図28】画像を縦方向32、横方向32に分割してできる1024個のブロックに対して付与するインデックスの一例を示す図である。
【図29−a】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−b】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−c】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−d】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−e】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−f】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−g】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図30】各次元の領域タイプと次元数、閾値に対応するインデックスとの関係を示す図である。
【図31−a】領域タイプaの次元の第1、第2の抽出領域の一例を示す図である。
【図31−b】領域タイプbの次元の第1、第2の抽出領域の一例を示す図である。
【図31−c】領域タイプcの次元の第1、第2の抽出領域の一例を示す図である。
【図31−d】領域タイプdの次元の第1、第2の抽出領域の一例を示す図である。
【図31−e】領域タイプeの次元の第1、第2の抽出領域の一例を示す図である。
【図31−f】領域タイプfの次元の第1、第2の抽出領域の一例を示す図である。
【図31−g】領域タイプgの次元の第1、第2の抽出領域の一例を示す図である。
【発明を実施するための形態】
【0015】
[第1の実施の形態]
[第1の実施の形態の構成]
次に、本発明の第1の実施の形態について図面を参照して詳細に説明する。
【0016】
図1を参照すると、本発明の第1の実施の形態に係る画像識別子抽出装置は、入力された画像に対して、複数の次元から成る特徴ベクトル(より具体的には量子化インデックスベクトル)を画像識別子として出力するシステムであり、次元決定手段1と、抽出領域取得手段2と、領域特徴量算出手段3と、比較手段4と、から構成されている。
【0017】
次元決定手段1は、次に抽出する特徴ベクトルの次元を決定し、抽出領域取得手段2へ供給する。次元決定手段1は、順次、抽出する特徴ベクトルの次元を供給し、抽出領域取得手段2以降の構成要素は、供給された次元に対応する特徴量を抽出する。例えば、特徴ベクトルがN次元から構成される場合、次元決定手段1は第1次元から第N次元までを順に抽出領域取得手段2へ供給してもよい。最終的に特徴ベクトルの全ての次元が供給されれば、供給する次元の順番は任意でよい。複数の次元が並列に供給されてもよい。
【0018】
抽出領域取得手段2には、次元決定手段1からの次元とは別に、入力として次元別抽出領域情報が供給される。
【0019】
次元別抽出領域情報は、あらかじめ規定された、特徴ベクトルの次元ごとに対応付けられた、その次元の特徴量を抽出するための第1の抽出領域と第2の抽出領域の対を示す情報である。第1および第2の抽出領域は必須条件として、以下の特徴を有する。
【0020】
[第1および第2の抽出領域の必須条件]
第1および第2の抽出領域の必須条件は、次元間で抽出領域対の相対的な位置が異なることに加えて、次元間で抽出領域対の形状の組み合わせが異なることである。
【0021】
上記必須条件を満たす、次元別抽出情報が示す次元ごとの抽出領域の対の例を図2に示す。図18に示した画像識別子の抽出領域とは異なり、次元間の抽出領域の対の形状の組み合わせが異なる。ここで異なる形状とは、角度の異なる合同な形状や(例えば、図2の第1次元の第2の抽出領域と、第7次元の第1の抽出領域)、大きさの異なる相似な形状(例えば、図2の第1次元の第2の抽出領域と、第9次元の第2の抽出領域)も含む。なお、特徴ベクトルの全次元の中に、抽出領域の対の形状の組み合わせの異なる次元のペアが、少なくとも1つ存在することが最低条件である。抽出領域の対の形状(の組み合わせ)が相互に異なる次元が多いほど、望ましい。これは、抽出領域の対の形状(の組み合わせ)が相互に異なる次元が多いほど、特徴ベクトルのより多くの次元間で相関が小さくなり、識別能力が高くなるからである。例えば、特徴ベクトルの全ての次元間で、抽出領域の対の形状(の組み合わせ)が相互に異なっていてもよい。
【0022】
ある次元における第1の抽出領域と、第2の抽出領域とは、図2の第9次元のように、同じ形状である必要はなく、図2の他の次元のように、形状が異なっていてもよい。各次元での第1の抽出領域と第2の抽出領域の形状が異なっていると、第1の抽出領域と第2の抽出領域から抽出される特徴量の相関が小さくなり、識別能力が高くなるため、望ましい。また、第1の抽出領域と第2の抽出領域が同時に同じ周波数に関して周波数的な盲点となる可能性が低くなるため、識別能力が高くなる。
【0023】
各々の抽出領域の形状は任意である。例えば、図2の第6次元の第2の抽出領域のような、任意の複雑な形状であっても構わない。画像の複数の画素で構成されるものであれば、例えば、図2の第7次元や第10次元のように、線分や曲線であっても構わない。また例えば、第8次元の第1の抽出領域、第11次元の第1と第2の抽出領域、第12次元の第1の抽出領域のように、抽出領域が、連続しない複数の小領域から構成されるものであってもよい。このように、任意の複雑な形状の抽出領域を含むことによって、そこから抽出される特徴量の次元間の相関を小さくすることができ、識別能力を高くすることができる。
【0024】
また、例えば、図2の第5次元のように、第1の抽出領域と第2の抽出領域の一部が重複していてもよい。また抽出領域対のいずれか一方が、もう一方の中に内包されていてもよい。このように、抽出領域の対に重複を許容することにより、より多くの抽出領域対のパターン(相対的位置・距離)を取れるため、次元間の相関を小さくすることができるパターンを増やすことができ、識別能力をより高くする可能性が増える。
【0025】
また、図18に示した画像識別子の抽出領域とは異なり、図2に示した各次元のように、次元間で抽出領域が一部重複していてもよい。図18に示した画像識別子の抽出領域のように、次元間で抽出領域を排他的に取ると、取れる抽出領域対のパターンが限られてしまう。図2に示したように、次元間での抽出領域に重複を許容することにより、より多くの抽出領域対のパターンを取れるため、次元間の相関を小さくすることができるパターンを増やすことができ、識別能力をより高くする可能性が増える。ただし、次元間での抽出領域の重複が多すぎると、次元間の相関が大きくなってしまい、識別能力が低くなるため、望ましくない。
【0026】
また、全ての次元の抽出領域を統合した場合に、画像内で特徴量が抽出されない領域が小さくなるような(すなわち、画像のほぼ全画面をカバーする)抽出領域の取り方であることが望ましい。これは、図18のように、画像内で特徴量が抽出されない領域が多く含まれていると、画像信号(画像を構成する画素の画素値)に含まれる多くの情報を使用しないことになり、識別能力が高くならないためである。全ての次元の抽出領域を統合した場合に、画像内で特徴量が抽出されない領域が小さくなるような(すなわち、画像のほぼ全画面をカバーする)抽出領域の取り方であることにより、画像信号に含まれるより多くの情報を特徴量に反映できるため、識別能力を高くすることができる。また、全ての次元の抽出領域を統合した場合に、抽出領域に偏りがなく、画像全体から満遍なく取得されていることが望ましい。ただし、ある特定の領域にテロップ重畳などの局所的な加工が施される確率が高い場合は、その領域を避けて抽出領域が取得されていることが望ましい。また、画像の縁などの周辺領域には画像の特徴部分が一般的に存在しないことが多いため、周辺領域を避けて抽出領域が取得されていることが望ましい。
【0027】
その他、抽出領域の大きさ、相対的位置(距離、方向)が一定の分布(例えば一様分布)に従うことが望ましい。その理由は、相対的位置(距離、方向)が一様分布に従うことによって、距離や方向に対して偏りがなく、特定の距離や方向に集中することがないため、より多くの多様性がとれるためである。また、相対的位置が近いほど、その領域間の相関が大きくなるため、それを打ち消すために、相対的位置が近いものほどより形状の差が大きいほうが望ましい。
【0028】
次元別抽出領域情報は、次元ごとの第1の抽出領域と第2の抽出領域とが一意に特定できる情報であれば、どのような形式の情報であっても構わない。また抽出領域は、如何なるサイズやアスペクト比の画像に対しても、常に同じ領域である必要があるため、次元別抽出領域情報は、如何なるサイズやアスペクト比の画像に対しても、同じ抽出領域を取得できる形式の情報である必要がある。例えば、次元別抽出領域情報は、ある規定のサイズとアスペクト比の画像(例えば、横幅320画素×縦幅240画素の画像)に対して、その抽出領域の位置・形状を記述したものであってもよい。この場合、ある任意のサイズとアスペクト比で入力された画像に対しては、まず画像をその規定のサイズとアスペクト比にリサイズしてから、次元別抽出領域情報に記述されている抽出領域の位置・形状に従って、抽出領域を特定すればよい。あるいは逆に、入力された画像の任意のサイズとアスペクト比の画像に合わせて、次元別抽出領域情報に記述されている抽出領域の位置・形状を変換して、抽出領域を特定してもよい。
【0029】
次元別抽出領域情報に含まれる各々の抽出領域を示す情報は、例えば、ある規定のサイズとアスペクト比の画像(例えば、横幅320画素×縦幅240画素の画像)に対して、抽出領域を構成する全ての画素の座標値の集合を記述した情報であってもよい。また次元別抽出領域情報に含まれる各々の抽出領域を示す情報は、例えば、ある規定のサイズとアスペクト比の画像に対して、抽出領域の位置・形状をパラメータ記述した情報であってもよい。例えば抽出領域の形が四角形である場合は、四角形の四隅の座標値を記述した情報であってもよい。また例えば抽出領域の形が円である場合は、円の中心の座標値と半径の値としてもよい。
【0030】
また、擬似乱数の種(シード)を次元別抽出領域情報として、抽出領域取得手段2の内部でその種からスタートして擬似乱数を発生させて、乱数に従って異なる形状の抽出領域を生成していく(例えば乱数に従って四角形の四隅を決定していくなど)、という方法も採用することができる。具体的には、例えば以下の手順で、次元別抽出領域を取得することができる。
(1)擬似乱数の種(シード)が次元別抽出領域情報として供給される。
(2)次元n=1とする。
(3)擬似乱数を発生させ、次元nの第1の抽出領域の四角形の四隅を決定する。
(4)擬似乱数を発生させ、次元nの第2の抽出領域の四角形の四隅を決定する。
(5)次元n=n+1として、(3)へ戻る。
【0031】
乱数に基づいて抽出領域を決定しているので、生成される抽出領域は次元毎に異なる形状になる。また、擬似乱数のシードが同じであれば、毎回(どの画像に対しても)同じ乱数列が発生されるため、異なる画像に対しても同じ抽出領域が再現される。
【0032】
抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元決定手段1から供給される次元に対応する第1の抽出領域と第2の抽出領域を示す情報を取得し、抽出領域代表値算出手段3へ供給する。
【0033】
領域特徴量算出手段3には、抽出領域取得手段2からの入力(第1の抽出領域と第2の抽出領域を示す情報)とは別に、入力として、画像識別子の抽出対象となる画像が供給される。領域特徴量算出手段3は、第1の領域特徴量算出手段31と第2の領域特徴量算出手段32とを有する。領域特徴量算出手段3は、第1の領域特徴量算出手段31を用いて、入力として供給される画像から、次元ごとに、抽出領域取得手段2から供給される第1の抽出領域を示す情報に基づき、第1の抽出領域の特徴量を第1の領域特徴量として算出し、比較手段4へ供給する。また、領域特徴量算出手段3は、第2の領域特徴量算出手段32を用いて、入力として供給される画像から、次元ごとに、抽出領域取得手段2から供給される第2の抽出領域を示す情報に基づき、第2の抽出領域の特徴量を第2の領域特徴量として算出し、比較手段4へ供給する。
【0034】
なお、第1の抽出領域と第2の抽出領域を示す情報に基づいて、入力される画像に対するそれぞれの抽出領域を特定するためには、必要に応じて領域特徴量算出手段3は、次元別抽出領域情報の規定のサイズとアスペクト比に画像をリサイズする。
【0035】
領域特徴量算出手段3は、それぞれの抽出領域に含まれる画素群の画素値を用いて、それぞれの抽出領域の領域特徴量を算出する。ここで画素値とは、画像の各画素が持つ信号の値であり、スカラー量またはベクトル量である。例えば、画像が輝度画像の場合は、画素値は輝度値(スカラー量)である。また例えば、画像がカラー画像の場合は、画素値は色成分を表すベクトル量である。例えばカラー画像がRGB画像である場合は、画素値はR成分、G成分、B成分の3次元のベクトル量である。また例えばカラー画像がYCbCr画像である場合は、画素値はY成分、Cb成分、Cr成分の3次元のベクトル量である。
【0036】
抽出領域の領域特徴量を算出する方法は、その次元の抽出領域(第1の抽出領域と第2の抽出領域)における算出方法が一定である(どの入力画像に対しても同じ算出方法である)限りは、任意の方法でよい。
【0037】
また、算出する領域特徴量は、スカラー量でもよいし、ベクトル量であってもよい。例えば、画素値が輝度値などのスカラー量である場合、領域特徴量を、その抽出領域に含まれる画素値の、平均値、メディアン値、最頻値、最大値、最小値、などと算出してもよい(いずれもスカラー量である)。また例えば、抽出領域に含まれる画素値をソートし、分布(ソートされた順列)の上位または下位から規定の割合の位置にある画素値を、領域特徴量として算出してもよい(これもスカラー量である)。より具体的に、規定の割合として、百分率でP%とした場合(例えばP=25%)を例に挙げて説明する。抽出領域に含まれる計N個の画素の画素値(輝度値)を昇順にソートし、昇順にソートされた画素値(輝度値)の集合をY(i)={Y(0)、Y(1)、Y(2)、…、Y(N−1)}と表す。ここで、昇順にソートされた順列の下位からP%の位置にある画素値は、例えば、Y(floor(N×P/100))となり、この値を抽出領域の領域特徴量として算出する。なお、floor()は、小数点以下の切り捨てを行う関数である。ここで、抽出領域に含まれる画素の輝度値に対して、この式(Y(floor(N×P/100)))を適用して算出された領域特徴量を、「パーセンタイル輝度値特徴量」と呼ぶことにする。
【0038】
また例えば、画素値が色成分などのベクトル量の場合は、まずそれらを任意の方法でスカラー量に変換してから、上述した方法によって領域特徴量を算出してもよい。例えば、画素値がRGB成分の3次元のベクトル量である場合は、まずそれらをスカラー量である輝度値に変換してから、上述した方法によって領域特徴量を算出してもよい。また画素値がベクトル量の場合は、例えば、その抽出領域に含まれる画素値の平均ベクトルを領域特徴量としてもよい。
【0039】
また例えば、抽出領域に対してエッジ検出や、テンプレートマッチングなどの任意の演算(微分演算、フィルタ演算)を行い、その演算結果を領域特徴量としてもよい。例えば、エッジの方向(勾配の方向)を表す2次元のベクトル量であってもよい。また例えば、あるテンプレートとの類似度などを表すスカラー量であってもよい。
【0040】
また例えば、抽出領域に含まれる色分布や、エッジの方向分布、エッジの強度分布を表すヒストグラムを、領域特徴量として算出してもよい(いずれもベクトル量である)。
【0041】
また例えば、国際標準規格ISO/IEC 15938−3に規定されている各種特徴量、すなわち、Dominant Color、Color Layout、Scalable Color、Color Structure、Edge Histogram、Homogeneous Texture、Texture Browsing、Region Shape、Contour Shape、Shape 3D、Parametric Motion、Motion Activityなどであってもよい。
【0042】
比較手段4は、次元ごとに、領域特徴量算出手段3から供給される第1の領域特徴量と、第2の領域特徴量とを比較し、比較した結果を量子化して得られた量子化インデックスを出力する。比較手段4が、次元ごとに、量子化インデックスを出力することで、最終的に、複数の次元の量子化インデックスから成る量子化インデックスベクトルが出力されることになる。
【0043】
比較手段4が、第1の領域特徴量と、第2の領域特徴量とを比較して、量子化する方法は、任意である。また、1つの次元当たりの量子化インデックスの数も任意である。
【0044】
比較手段4は、例えば、領域特徴量がスカラー量である場合(例えば輝度値の平均値)、その大小を比較して第1の領域特徴量のほうが大きい場合は量子化インデックスを+1、それ以外の場合は量子化インデックスを−1とする、のようにして+1と−1の2値の量子化インデックスに量子化してもよい。ここで、次元nの第1の領域特徴量をVn1、第2の領域特徴量をVn2とすると、次元nの量子化インデックスQnは、次式で算出することができる。
【0045】
[式1]
Qn=+1 (Vn1>Vn2 の場合)
−1 (Vn1≦Vn2 の場合)
【0046】
ここで、比較手段4が、上述の式1に基づいた比較・量子化を行う場合における、比較手段4のより詳細な構成図を図3に示す。
【0047】
図3を参照すると、比較手段4は、大小比較手段41と、量子化手段42と、から構成されている。
【0048】
大小比較手段41は、第1の領域特徴量と、第2の領域特徴量とが供給されると、第1の領域特徴量の値と第2の領域特徴量の値との大小を比較し、その比較結果を量子化手段42へ供給する。すなわち、大小比較手段41は、Vn1とVn2の大小を比較し、比較結果が、Vn1>Vn2であるか、Vn1≦Vn2であるか、のいずれであるかを示す情報を、大小比較結果として量子化手段42へ供給する。
【0049】
量子化手段42は、大小比較手段41から供給される大小比較結果に基づいて、式1に従って量子化を行い、量子化インデックスを出力する。すなわち量子化手段42は、比較結果がVn1>Vn2であることを示す情報が供給される場合は、量子化インデックスを+1、比較結果がVn1≦Vn2であることを示す情報が供給される場合は、量子化インデックスを−1、として量子化インデックスを出力する。
【0050】
なお、この式1に基づいた比較・量子化方法を比較・量子化方法Aと呼ぶことにする。
【0051】
また、比較手段4は、例えば、領域特徴量がスカラー量である場合(例えば輝度値の平均値)、差分値の絶対値がある規定の閾値以下の場合は、第1の領域特徴量と第2の領域特徴量との差がないものをみなし、差がないことを示す量子化インデックス0とし、それ以外の場合は、その大小を比較して第1の領域特徴量のほうが大きい場合は量子化インデックスを+1、それ以外の場合は量子化インデックスを−1とする、のようにして+1、0、−1の3値の量子化インデックスに量子化してもよい。ここで、次元nの第1の領域特徴量をVn1、第2の領域特徴量をVn2とし、規定の閾値をthとすると、次元nの量子化インデックスQnは、次式で算出することができる。
【0052】
[式2]
Qn=+1 (|Vn1−Vn2|>th かつ Vn1>Vn2 の場合)
0 (|Vn1−Vn2|≦th の場合)
−1 (|Vn1−Vn2|>th かつ Vn1≦Vn2 の場合)
【0053】
ここで、比較手段4が、上述の式2に基づいた比較・量子化を行う場合における、比較手段4のより詳細な構成図を図4に示す。
【0054】
図4を参照すると、比較手段4は、差分値算出手段43と、量子化手段44と、から構成されている。量子化手段44には、あらかじめ規定された、量子化の境界を表す情報(量子化境界情報)である閾値が、入力として供給される。
【0055】
差分値算出手段43は、第1の領域特徴量と、第2の領域特徴量とが供給されると、第1の領域特徴量の値と第2の領域特徴量の値との差分値を算出し、算出した差分値を量子化手段44へ供給する。すなわち、差分値算出手段43は、Vn1−Vn2を算出し、その値を量子化手段44へ供給する。
【0056】
量子化手段44は、差分値算出手段43から供給される差分値と、入力として供給されるあらかじめ規定された量子化の境界を表す情報(量子化境界情報)である閾値とに基づいて、式2に従って量子化を行い、量子化インデックスを出力する。すなわち量子化手段42は、差分値算出手段41から供給されるVn1−Vn2の値と、入力として供給される閾値thとに基づいて、|Vn1−Vn2|>th かつ Vn1−Vn2>0 の場合は量子化インデックスを+1、|Vn1−Vn2|>th かつ Vn1−Vn2≦0 の場合は量子化インデックスを−1、|Vn1−Vn2|≦th の場合は量子化インデックスを0、として量子化インデックスを出力する。
【0057】
なお、この式2に基づいた比較・量子化方法を比較・量子化方法Bと呼ぶことにする。
【0058】
また、ここでは差分値に基づいて3値に量子化しているが、差分値の大きさに応じて、より多数(のレベルの)の量子化インデックスに量子化してもよい。この場合も、比較手段4は、図4に示した構成をとり、量子化手段44には、あらかじめ規定された、各レベルの量子化の境界を表す情報(量子化境界情報)として複数の閾値が、入力として供給される。なお、この差分値と、入力として供給される複数の閾値とに基づいて、4レベル以上の複数のレベルの量子化インデックスに量子化する比較・量子化方法を比較・量子化方法Cと呼ぶことにする。
【0059】
このように、第1の領域特徴量と第2の領域特徴量との差が小さい(規定の閾値以下の)ときに、差がないものとして、差がないことを表す量子化インデックスを導入することで、式1の方法に比べて、領域特徴量の差が小さい抽出領域の対の次元の特徴量(量子化インデックス)をより安定に、すなわち各種改変処理やノイズに対してより頑健に、することができる。そのため、局所領域間の特徴の差が全体的に少ない、全体的に変化の少ない平坦な画像(例えば青空の画像)に対しても安定した、すなわち各種改変処理やノイズに対しても頑健な、画像識別子(量子化インデックスベクトル)を出力することができる。
【0060】
また、比較手段4は、例えば、領域特徴量がベクトル量である場合は、ベクトル量をまずそれらを任意の方法でスカラー量に変換してから、上述した方法によって量子化を行ってもよい(この比較・量子化方法を比較・量子化方法Dと呼ぶことにする)。また例えば、第1の抽出領域のベクトルから第2の抽出領域のベクトルとの差分である差分ベクトルを算出し、差分ベクトルをベクトル量子化して量子化インデックスを算出してもよい。この場合は、例えば、あらかじめ規定された量子化インデックスごとの代表ベクトル(重心ベクトルなど)が供給され、それら代表ベクトルと差分ベクトルとの類似度が最も大きく(距離が最も小さく)なる量子化インデックスに分類してもよい(この比較・量子化方法を比較・量子化方法Eと呼ぶことにする)。また、上述の式2によるスカラー量の量子化と同様に、差分ベクトルのノルムがある規定の閾値以下の場合は、第1の領域特徴量と第2の領域特徴量との差がないものをみなし、差がないことを示す量子化インデックス0として、差がないことを表す量子化インデックスを導入してもよい。
【0061】
なお、本発明で出力される量子化インデックスベクトルを照合する際(ある画像から抽出した量子化インデックスベクトルと、別の画像から抽出した量子化インデックスベクトルとを比較して、それらの画像が同一であるか否かを判定する際)は、量子化インデックスが一致する次元数(類似度)、あるいは量子化インデックスが非一致である次元数(ハミング距離)を同一性尺度として算出し、算出された同一性尺度をある閾値と比較して、画像の同一性の判定を行うことができる。また、比較手段4において、量子化インデックスが式2に基づいて算出された場合は、以下のように同一性尺度(類似度)を算出することができる。まず、2つの画像の量子化インデックスベクトルを対応する次元どうしで比較して、「共に量子化インデックスが0」ではない次元の数を算出する(この値をAとする)。次に、「共に量子化インデックスが0」ではない次元において、量子化インデックスが一致する次元の数を算出する(この値をBとする)。そして、類似度をB/Aとして算出する。ここでA=0の場合(すなわち、全ての次元が共に量子化インデックスが0となる場合)は、類似度を規定の数値(例えば0.5)とする。
【0062】
[第1の実施の形態の動作]
次に、図5のフローチャートを参照して、第1の実施の形態における画像識別子抽出装置の動作を説明する。図5のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0063】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2へ供給する(ステップA1)。
【0064】
次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、領域特徴量算出手段3へ供給する(ステップA2)。
【0065】
次に、領域特徴量算出手段3は、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、比較手段4へ供給する(ステップA3)。
【0066】
次に、比較手段4は、次元nの第1の領域特徴量と第2の領域特徴量とを比較し、比較した結果を量子化して、量子化インデックスを出力する(ステップA4)。
【0067】
次に、全ての次元に対して量子化インデックスの出力が終了したか否かを判定(すなわちn<Nが真であるか偽であるかを判定)する(ステップA5)。全ての次元に対して量子化インデックスの出力が終了した場合(すなわちn<Nが偽である場合)は処理を終了する。全ての次元に対して量子化インデックスの出力が終了していない場合(すなわちn<Nが真である場合)は、ステップA6へ移行する。ステップA6では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2へ供給する。そして、再度ステップA2へ移行する。
【0068】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。またこの処理手順に限らず、複数の次元に対する抽出処理を並列に行うようにしてもよい。
【0069】
[第1の実施の形態の効果]
次に、本発明の第1の実施の形態の効果について説明する。
【0070】
第1の効果は、複数の次元から成る特徴ベクトルで構成される画像識別子の、異なる画像を識別できる度合いである識別能力を高くすることができることである。特に、画像の局所領域間の相関が大きい画像に対して、この効果は顕著である。
【0071】
その理由は、次元間で特徴量を抽出する領域の形状が異なる(領域の形状に多様性がある)ことにより、次元間の相関を小さくできるからである。
【0072】
第2の効果は、特定の周波数に信号が集中している画像に対しても、識別能力が低下することがないことである。
【0073】
その理由は、次元間で特徴量を抽出する領域の形状が異なる(領域の形状に多様性がある)ことにより、ある特定の周波数に信号が集中している画像に対しても、同時に全ての(多くの)抽出領域の対(次元)の間で特徴量の差が無くなり識別能力が低下するようなことが発生しにくくなるからである。
【0074】
[第2の実施の形態]
[第2の実施の形態の構成]
次に、本発明の第2の実施の形態について図面を参照して詳細に説明する。
【0075】
本発明の第2の実施の形態は、図1に示した第1の実施の形態における比較手段4が、図6に詳細を示す比較手段4Aに置き換わる点において、異なる。比較手段4A以外に関しては、第1の実施の形態と同様であるため、ここでは説明を省略する。
【0076】
図6を参照すると、比較手段4Aは、差分値算出手段43と、量子化境界決定手段45と、量子化手段44と、から構成されている。
【0077】
差分値算出手段43は、次元ごとに、領域特徴量算出手段3から供給される第1の領域特徴量と、第2の領域特徴量との差分値を算出し、量子化境界決定手段45と、量子化手段44とへ供給する。
【0078】
差分値は、領域特徴量がスカラー量の場合(例えば輝度値の平均値)は、例えば、第1の領域特徴量から第2の領域特徴量を(あるいはその逆)減算して得られたスカラー量である。また、領域特徴量がベクトル量の場合は、例えば、それぞれのベクトルを任意の方法でスカラー量に変換してから、スカラー量の差分値を求めてもよい。また、領域特徴量がベクトル量の場合は、第1の領域特徴量と第2の領域特徴量との差分ベクトルを、差分値(ベクトル量)としてもよい。
【0079】
量子化境界決定手段45は、差分値算出手段43から供給される特徴ベクトルの全ての次元の差分値が供給されると、全ての次元の差分値の分布に基づいて、量子化の境界を決定し、決定した量子化境界の情報を量子化手段44へ供給する。ここで全ての次元の差分値の分布とは、差分値(あるいは差分ベクトル)に対する生起の頻度(確率)である。
【0080】
また量子化の境界を決定するとは、差分値を量子化する際に、漏れなく、かつ排他的に量子化インデックスに割り当てるためのパラメータを決定する、ということである。差分値がスカラー量である場合は、例えば、各量子化インデックス(量子化レベル)に対する値域(すなわち閾値)を決定し、その値域(閾値)を量子化境界の情報として量子化手段43へ供給する。また差分値がベクトル量である場合は、例えばベクトル量子化を行うためのパラメータ、例えば、各量子化インデックスの代表ベクトル(重心ベクトルなど)を決定し、それを量子化境界の情報として量子化手段44へ供給する。
【0081】
量子化境界決定手段45は、差分値がスカラー量の場合であって、M値の量子化を行う場合(M=2、3、…など)に、全ての次元の差分値の分布に基づいて、それぞれの量子化インデックスの全次元に対する割合が均等になるように、量子化の値域(閾値)を決定してもよい。
【0082】
例えば、前記式1の変形として、定数αを用いて、Vn1+α>Vn2の場合は量子化インデックス+1、Vn1+α≦Vnの場合は量子化インデックス−1とする2値の量子化(M=2)の場合に、量子化インデックスの+1と−1の割合が均等になるように、差分値の分布の中央の点(左右の分布の積分値が等しくなる点)を量子化の閾値αとして決定してもよい。また差分値がベクトル量である場合も同様に、M値の量子化を行う場合に、全ての次元の差分ベクトルの分布に基づいて、それぞれの量子化インデックスの全次元に対する割合が均等になるように、各量子化インデックスに割り当てられるベクトル空間の領域を決定したり、ベクトル量子化を行う際の各量子化インデックスの代表ベクトル(重心ベクトルなど)を決定してもよい。このように、どの画像に対しても、全次元に対する量子化インデックスの割合を均等にすることで(すなわち、量子化インデックスの偏りを無くす)、エントロピーを高くすることができるため、識別能力を高くすることができる。
【0083】
なお、量子化境界決定手段45が、量子化インデックスの全次元に対する割合が均等になるように量子化の境界を決定し、それに基づいて量子化手段44が量子化を行う比較・量子化方法を、比較・量子化方法Fと呼ぶことにする。
【0084】
また例えば、量子化境界決定手段45は、差分値がスカラー量の場合であって、上述の式2による3値の量子化を行う場合に(量子化インデックスが+1、0、−1)、差分がないことを示す量子化インデックス0に量子化する際の閾値th(この閾値以下の場合に量子化インデックスを0とする)を、全ての次元の差分値の分布に基づいて決定し、決定した閾値thを量子化手段44へ供給してもよい(第1の実施の形態の図4の比較手段4では、この閾値thはあらかじめ規定されているものである)。例えば、全ての次元の差分値の絶対値を算出し、算出した差分値の絶対値をソートして、その上位または下位から、ある規定の割合(なおこの規定の割合は、例えば、入力として供給されるとする)の点を閾値thとしてもよい(この比較・量子化方法を比較・量子化方法Gと呼ぶことにする)。またここで規定の割合ではなく、+1、0、−1の量子化インデックスの割合が均等に近づくように、閾値thを決定してもよい(この比較・量子化方法を比較・量子化方法Hと呼ぶことにする)。比較・量子化方法Hは、式2に従った場合の、比較・量子化方法Fの具体例に相当する。
【0085】
比較・量子化方法Gのより具体的な方法を、規定の割合として、百分率でP%とした場合(例えばP=25%)を例に挙げて説明する。全ての次元(次元数=Nとする)の差分値の絶対値を、昇順にソートし、昇順にソートされた差分値の絶対値の集合をD(i)={D(0)、D(1)、D(2)、…、D(N−1)}と表す。ここで、昇順にソートされた順列の下位からP%の位置にある値は、例えば、D(floor(N×P/100))となり、閾値th=D(floor(N×P/100))となる。なお、floor()は、小数点以下の切り捨てを行う関数である。
【0086】
本実施の形態における方法は、第1の実施の形態における、比較手段4が図4の構成をとる場合と対比することができる。第1の実施の形態における図4の構成では、あらかじめ規定された閾値thが入力として供給されるのに対して、第2の実施の形態における上述の方法は、量子化境界決定手段45において、全ての次元の差分値の分布に基づいて、画像に対して適応的に閾値thが算出される。このように第1の実施の形態では閾値thが固定化されており、第2の実施の形態では閾値thが画像に適応的に算出される。画像に適応的に閾値thが算出されることで、閾値thが固定化されている場合と比較して、特徴ベクトルの次元の値が、特定の量子化インデックスに偏る(特定の量子化インデックスの出現確率が高い)ことを抑えることができるため(特に起伏の少ない画像に対してなど)、識別能力を高くすることができる。例えば、第1の実施の形態における固定化された閾値thを用いた場合、起伏の少ない画像は、特徴ベクトルの大多数の次元(または全ての次元)が量子化インデックス0になってしまうのに対して、第2の実施の形態における適応的な閾値thを用いると、起伏の少ない画像に対しては閾値thが小さい値に自動的に調整されるため、特徴ベクトルの大多数の次元が量子化インデックス0になるような事態が発生しない。
【0087】
量子化手段44は、次元ごとに、差分値算出手段43から供給される次元ごとの差分値と、量子化境界決定手段45から供給される量子化境界の情報とに基づいて、量子化を行い、量子化インデックスを出力する。
【0088】
なお、量子化手段44は、量子化境界決定手段45が出力した量子化境界の情報を無視した量子化を行っては意味がなくなるため、量子化境界決定手段45で量子化境界を決定した際に想定していた量子化方法に従う必要がある。
【0089】
[第2の実施の形態の動作]
次に、図7のフローチャートを参照して、第2の実施の形態における画像識別子抽出装置の動作を説明する。図7のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0090】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2へ供給する(ステップB1)。
【0091】
次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、抽出領域代表値算出手段3へ供給する(ステップB2)。
【0092】
次に、抽出領域代表値算出手段3は、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、差分値算出手段43へ供給する(ステップB3)。
【0093】
次に、差分値算出手段43は、次元nの第1の領域特徴量と第2の領域特徴量との差分値を算出し、量子化境界決定手段45と、量子化手段44とへ供給する(ステップB4)。
【0094】
次に、全ての次元に対する差分値の算出までの処理が終了したか否かを判定(すなわちn<Nが真であるか偽であるかを判定)する(ステップB5)。全ての次元に対する差分値算出までの処理を終了した場合(すなわちn<Nが偽である場合)はステップB7へ移行する。全ての次元に対する処理が終了していない場合(すなわちn<Nが真である場合)は、ステップB6へ移行する。ステップB6では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2へ供給する。そして、再度ステップB2へ移行する。
【0095】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0096】
次に、量子化境界決定手段45は、差分値算出手段43から供給される特徴ベクトルの全ての次元の差分値が供給されると、全ての次元の差分値の分布に基づいて、量子化の境界を決定し、決定した量子化境界の情報を量子化手段44へ供給する(ステップB7)。
【0097】
次にステップB8では、量子化を行う(量子化インデックスを算出する)特徴ベクトルの最初の次元として、次元1をセット(n=1)する。
【0098】
次に、量子化手段44は、次元nの差分値と、量子化境界決定手段45から供給される量子化境界とに基づいて、量子化を行い、量子化インデックスを出力する(ステップB9)。
【0099】
次に、全ての次元に対する量子化インデックスの出力が終了したか否かを判定(すなわちn<Nが真であるか偽であるかを判定)する(ステップB10)。全ての次元に対する量子化インデックスの出力を終了した場合(すなわちn<Nが偽である場合)は処理を終了する。全ての次元に対する量子化インデックスの出力が終了していない場合(すなわちn<Nが真である場合)は、ステップB11へ移行する。ステップB11では、量子化を行う(量子化インデックスを算出する)特徴ベクトルの次元として、次の次元をセットする(n=n+1)。そして、再度ステップB9へ移行する。
【0100】
なお、ここでは、次元1から次元Nまで順番に量子化処理を行っているが、順番はこれに限らず任意でよい。
【0101】
[第2の実施の形態の効果]
第2の実施の形態では、量子化の境界が固定されている第1の実施の形態と比較して、量子化の境界が画像に対して適応的に(動的に)算出される点が異なる。第1の実施の形態のように、量子化の境界が固定化されていると、特定の画像(例えば起伏の少ない平坦な画像など)に対して、特徴ベクトルの次元の値が、特定の量子化インデックスに偏る(特定の量子化インデックスの出現確率が高い)という事態が発生し(エントロピーが低くなる)、これらの画像に対して識別能力が低下するという問題が発生する。一方で第2の実施の形態のように、量子化の境界が画像に対して適応的に(動的に)算出されることにより、どの画像に対しても、特徴ベクトルの次元の値が、特定の量子化インデックスに偏る(特定の量子化インデックスの出現確率が高い)ことを抑えることができるため、識別能力を高くすることができる。
【0102】
[第3の実施の形態]
[第3の実施の形態の構成]
次に、本発明の第3の実施の形態について図面を参照して詳細に説明する。
【0103】
図8を参照すると、本発明の第3の実施の形態は、図1に示した第1の実施の形態の構成に、領域特徴量算出方法取得手段5が追加され、領域特徴量算出手段3が、第1および第2の領域特徴量算出手段31Aおよび32Aを有する領域特徴量算出手段3Aに置き換わる点で異なる。なお、それ以外の構成に関しては、第1の実施の形態の構成と同様であるため、ここでは説明を省略する。なお、ここでは、第1の実施の形態との組み合わせとして説明しているが、第2の実施の形態との組み合わせであってもよい。
【0104】
領域特徴量算出方法取得手段5には、次元決定手段1からの次元と、次元別領域特徴量算出方法情報とが供給される。
【0105】
次元別領域特徴量算出方法情報は、あらかじめ規定された、特徴ベクトルの次元ごとに対応付けられた、その次元での領域特徴量の算出方法を示す情報であり、次元間で領域特徴量算出方法が異なることが必須条件である。なおここで、領域特徴量算出方法が異なるとは、同一の手順に対して異なるパラメータ(閾値など)を適用する場合も含む。
【0106】
ここで領域特徴量算出方法とは、例えば、第1の実施の形態の領域特徴量算出手段3の説明で記述した各種方法、またそれに伴うパラメータなどである。
【0107】
なお次元別領域特徴量算出方法情報が示す次元ごとの領域特徴量算出方法は、特徴ベクトルの全次元の中に、領域特徴量算出方法の異なる次元のペアが、少なくとも1つ存在することが最低条件である。領域特徴量算出方法が相互に異なる次元が多いほど、望ましい。これは、領域特徴量算出方法が相互に異なる次元が多いほど、特徴ベクトルのより多くの次元間で相関が小さくなり、識別能力が高くなるからである。例えば、特徴ベクトルの全ての次元間で、領域特徴量算出方法が相互に異なっていてもよい。
【0108】
なお、次元ごとの領域特徴量算出方法を示す情報の形式は、領域特徴量を算出する方法が一意に特定される限りは、任意の形式であってよい。
【0109】
図9に、次元ごとの領域特徴量算出方法の例を示す。図9に示すように、次元間で領域特徴量算出方法が異なる。また図9に示した例のように、スカラー量とベクトル量の特徴量が混在していてもよい(第1、3、5、6、8、9、10、12次元はスカラー量、第2、4、7、11次元はベクトル量)。
【0110】
領域特徴量算出方法取得手段5は、入力として供給される次元別領域特徴量算出方法情報から、次元決定手段1から供給される次元に対応する領域特徴量算出方法を示す情報を取得し、領域特徴量算出手段3Aへ供給する。
【0111】
領域特徴量算出手段3Aは、入力として供給される画像から、次元ごとに、抽出領域取得手段2から供給される第1の抽出領域と第2の抽出領域とを示す情報に基づき、領域特徴量算出方法取得手段5から供給される領域特徴量算出方法を示す情報に従って、第1の抽出領域の特徴量と、第2の抽出領域の特徴量とを、それぞれ第1の領域特徴量と第2の領域特徴量として算出し、比較手段4へ供給する。
【0112】
領域特徴量算出手段3Aでは、供給される抽出領域を示す情報の次元と、領域特徴量算出方法を示す情報の次元との同期が取れている必要がある。
【0113】
[第3の実施の形態の動作]
次に、図10のフローチャートを参照して、第3の実施の形態における画像識別子抽出装置の動作を説明する。図10のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0114】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2と領域特徴量算出方法取得手段5とへ供給する(ステップC1)。次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、領域特徴量算出手段3Aへ供給する(ステップC2)。
【0115】
次に、領域特徴量算出方法取得手段5は、入力として供給される次元別領域特徴量算出方法情報から、次元nに対応する領域特徴量算出方法を示す情報を取得し、領域特徴量算出手段3Aへ供給する(ステップC3)。
【0116】
次に、領域特徴量算出手段3Aは、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、比較手段4へ供給する(ステップC4)。次に、比較手段4は、次元nの第1の領域特徴量と第2の領域特徴量とを比較し、比較した結果を量子化して、量子化インデックスを出力する(ステップC5)。次に、全ての次元に対して量子化インデックスの出力が終了したか否かを判定する(ステップC6)。全ての次元に対して量子化インデックスの出力が終了した場合は処理を終了する。全ての次元に対して量子化インデックスの出力が終了していない場合は、ステップC7へ移行する。ステップC7では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2と領域特徴量算出方法取得手段5とへ供給する。そして、再度ステップC2へ移行する。
【0117】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。またこの処理手順に限らず、複数の次元に対する抽出処理を並列に行うようにしてもよい。さらに、ステップC2とステップC3の順序を逆にしてもよい。
【0118】
[第3の実施の形態の効果]
第1の実施の形態の効果に加えて、異なる画像を識別できる度合いである識別能力を更に高くすることができる。
【0119】
その理由は、次元間で領域特徴量算出方法が異なる(領域特徴量算出方法に多様性がある)ことにより、次元間の相関をより小さくできるからである。
【0120】
[第4の実施の形態]
[第4の実施の形態の構成]
次に、本発明の第4の実施の形態について図面を参照して詳細に説明する。
【0121】
図11を参照すると、本発明の第4の実施の形態は、図1に示した第1の実施の形態の構成に、比較方法取得手段6が追加され、比較手段4が比較手段4Bに置き換わる点で異なる。なお、それ以外の構成に関しては、第1の実施の形態の構成と同様であるため、ここでは説明を省略する。なお、ここでは、第1の実施の形態との組み合わせとして説明しているが、第2の実施の形態および第3の実施の形態との組み合わせであってもよい。
【0122】
比較方法取得手段6には、次元決定手段1からの次元と、次元別比較方法情報とが供給される。
【0123】
次元別比較・量子化方法情報は、あらかじめ規定された、特徴ベクトルの次元ごとに対応付けられた、その次元での領域特徴量を比較して量子化を行う方法を示す情報であり、次元間で比較・量子化方法が異なることが必須条件である。なおここで、比較・量子化方法が異なるとは、同一の手順に対して異なるパラメータ(閾値、量子化インデックス数など)を適用する場合も含む。
【0124】
ここで比較・量子化方法とは、例えば第1の実施の形態の比較手段4の説明で記述した各種比較・量子化の方法、またそれに伴うパラメータ(閾値、量子化インデックス数など)や、第2の実施の形態の比較手段4Aの説明で記述した各種比較・量子化の方法、またそれに伴うパラメータ(閾値、量子化インデックス数など)などである。
【0125】
なお次元別比較・量子化方法情報が示す次元ごとの比較・量子化方法は、特徴ベクトルの全次元の中に、比較・量子化方法の異なる次元のペアが、少なくとも1つ存在することが最低条件である。比較・量子化方法が相互に異なる次元が多いほど、望ましい。これは、比較・量子化方法が相互に異なる次元が多いほど、特徴ベクトルのより多くの次元間で相関が小さくなり、識別能力が高くなるからである。例えば、特徴ベクトルの全ての次元間で、比較・量子化方法が相互に異なっていてもよい。
【0126】
なお、次元ごとの比較・量子化方法を示す情報の形式は、領域特徴量を比較して量子化する方法が一意に特定される限りは、任意の形式であってよい。
【0127】
図12に、次元ごとの比較・量子化方法の例を示す。図12に示すように、次元間で比較・量子化方法が異なる。また、第3、5、12次元のように、同じ比較・量子化方法で、異なるパラメータ(閾値th)を設定してもよい。なお、図12に示した、次元ごとの比較・量子化方法の例は、図9に示した、次元ごとの領域特徴量算出方法の例と対応させており、スカラー量の領域特徴量に対してはスカラー量の比較・量子化方法を、ベクトル量の領域特徴量に対してはベクトル量の比較・量子化方法を例として示した。
【0128】
比較方法取得手段6は、入力として供給される次元別比較・量子化方法情報から、次元決定手段1から供給される次元に対応する比較・量子化方法を示す情報を取得し、比較手段4Bへ供給する。
【0129】
比較手段4Bは、次元ごとに、領域特徴量算出手段3から供給される第1の領域特徴量と、第2の領域特徴量とを、比較方法取得手段6から供給される比較・量子化方法を示す情報に従って、比較・量子化して、量子化インデックスを出力する。比較手段4Bは、比較・量子化方法によって、必要に応じて、第1の実施の形態の比較手段4と、第2の実施の形態の比較手段4Bの両方を内包した構成となる場合もある。
【0130】
比較手段4Bでは、供給される領域特徴量の次元と、比較・量子化方法を示す情報の次元の同期が取れている必要がある。
【0131】
[第4の実施の形態の動作]
次に、図13のフローチャートを参照して、第4の実施の形態における画像識別子抽出装置の動作を説明する。図13のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0132】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2と比較方法取得手段6とへ供給する(ステップD1)。次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、領域特徴量算出手段3へ供給する(ステップD2)。
【0133】
次に、比較方法取得手段6は、入力として供給される次元別比較・量子化方法情報から、次元nに対応する比較・量子化方法を示す情報を取得し、比較手段4Bへ供給する(ステップD3)。
【0134】
次に、領域特徴量算出手段3は、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、比較手段4Bへ供給する(ステップD4)。次に、比較手段4Bは、次元nの第1の領域特徴量と第2の領域特徴量とを比較し、比較した結果を量子化して、量子化インデックスを出力する(ステップD5)。次に、全ての次元に対して量子化インデックスの出力が終了したか否かを判定する(ステップD6)。全ての次元に対して量子化インデックスの出力が終了した場合は処理を終了する。全ての次元に対して量子化インデックスの出力が終了していない場合は、ステップD7へ移行する。ステップD7では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2と比較方法取得手段6とへ供給する。そして、再度ステップD2へ移行する。
【0135】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。またこの処理手順に限らず、複数の次元に対する抽出処理を並列に行うようにしてもよい。さらに、ステップD2とステップD3との順序を逆にしてもよく、ステップD3をステップD5の直前に実行するようにしてもよい。
【0136】
[第4の実施の形態の効果]
第1の実施の形態の効果に加えて、異なる画像を識別できる度合いである識別能力を更に高くすることができる。
【0137】
その理由は、次元間で比較・量子化方法が異なる(比較・量子化方法に多様性がある)ことにより、次元間の相関をより小さくできるからである。
【0138】
[第5の実施の形態]
[第5の実施の形態の構成]
次に、本発明の第5の実施の形態について図面を参照して詳細に説明する。
【0139】
図20を参照すると、本発明の第5の実施の形態は、図1に示した第1の実施の形態の構成に、符号化手段7が追加される点で異なる。なお、それ以外の構成に関しては、第1の実施の形態の構成と同様であるため、ここでは説明を省略する。なお、ここでは、第1の実施の形態との組み合わせとして説明しているが、第2の実施の形態、または第3の実施の形態、または第4の実施の形態との組み合わせであってもよい。
【0140】
符号化手段7は、比較手段4から供給される量子化インデックスベクトルを、データ量が小さくなるように一意に復号可能な形式に符号化し、符号化された量子化インデックスベクトルを出力する。
【0141】
符号化手段7は、例えば、量子化インデックスベクトルの各次元を独立に符号化するのではなく、複数の次元をまとめて符号化することによって、データ量を小さく符号化してもよい。
【0142】
ここで、量子化インデックスが式2に基づいて算出された場合において、符号化手段7が効率的に符号化する方法について述べる。式2に基づいて量子化インデックスを算出すると、各次元の量子化インデックスは、(+1、0、−1)の3値のいずれかの値をとる。各次元を独立に符号化する場合は、各次元に対して2ビット(=4状態)が必要となる。ここで、5次元をまとめて符号化することを考えると(この5次元はどのような組合せでもよい。例えば連続する5次元でもよい)、その状態数は3の5乗=243状態となり、1バイト=8ビット(=256状態)で表す(256状態以内に収めることができる)ことができる。こうすると、1次元あたりに必要な平均ビット数は8/5=1.6ビットとなり、各次元を独立に符号する場合よりも、データ量を小さくすることができる(1次元あたり0.4ビットの削減が可能)。例えば、量子化インデックスベクトルの全次元数が300次元の場合、各次元を独立に符号化した場合は2ビット×300=600ビット=75バイトとなる。一方で、5次元ごとにまとめて符号化すると、1.6ビット×300=480ビット=60バイトとなり、15バイト削減できる。
【0143】
式2で算出される(+1、0、−1)の3値の状態を5次元ごとに符号化する具体例を以下に示す。各5次元の組合せは、どのような組合せでも良いが、例えば、連続する5つの次元ごとに符号化する方法がある。すなわち、第1次元から第5次元をまとめて符号化し、第6次元から第10次元をまとめて符号化し、第11次元から第15次元をまとめて符号化していくことができる(もちろん、重複がない限りは、どのような5つの次元の組み合わせでもよい)。ここで、まとめて符号化する5次元の量子化インデックスの値をQn、Qn+1、Qn+2、Qn+3、Qn+4とすると(それぞれは+1、0、−1のいずれかの値をとる)、例えば、以下の式に従って符号化された値Zを算出することができる。
【0144】
[式3]
Z={34×(Qn+1)}+{33×(Qn+1+1)}+{32×(Qn+2+1)}+{31×(Qn+3+1)}+{30×(Qn+4+1)}
【0145】
この符号化された値Zは、0から242の値をとるため(243状態)、1バイト(8ビット)のデータとして符号化されることになる。なお、まとめて符号化する5次元の量子化インデックスの値をQn、Qn+1、Qn+2、Qn+3、Qn+4を、0から242の値(243状態)にマッピングする方法は、[式3]だけに限られず、5次元の量子化インデックスの異なる組み合わせに対して、異なる値(243状態の値)にマッピングされる方法であれば、どのような方法であってもよい。[式3]のように与えられた式に基づいて、マッピング(符号化後の値)を算出し、符号化してもよいし、またあらかじめマッピングの対応表を生成・記憶しておき、記憶された対応表を参照しながらマッピング(符号化後の値)を取得し、符号化してもよい。
【0146】
段落0142から段落0145において説明した、量子化インデックスが式2に基づいて算出された場合において効率的に符号化する方法は、量子化インデックスが式2に基づいて算出された場合に限らず、量子化インデックスが3値の状態の量子化インデックスベクトルであれば、同様に適用可能である。すなわち、量子化インデックスベクトルが、3値の状態の量子化インデックスから成る場合は、5次元をまとめて1バイト=8ビットとして符号化することができる。3値の状態を持つ5次元の量子化インデックスは、5次元の量子化インデックスの異なる組み合わせが243種類可能であるため、それぞれの組み合わせを0から242の値(243状態)にマッピングすることによって、1バイト=8ビットで符号化することができる。なおこのマッピングは、[式3]のように与えられた式に基づいて、マッピング(符号化後の値)を算出し、符号化してもよいし、またあらかじめマッピングの対応表を生成・記憶しておき、記憶された対応表を参照しながらマッピング(符号化後の値)を取得し、符号化してもよい。
【0147】
このように、量子化インデックスベクトルの各次元を独立に符号化するのではなく、複数の次元をまとめて符号化することによって、量子化インデックスベクトルの各次元を独立に符号化する場合と比較して、データ量を小さく符号化できる、という効果がある。
【0148】
これは、量子化インデックスが3値の状態で表現される場合に限られない。例えば、量子化インデックスが5値の状態で表現される場合は、3次元をまとめて符号化することにより5の3乗=125状態となり、7ビット=128状態で符号化する(128状態以内に収めることができる)ことができる。3次元を独立に符号化すると3ビット(8状態)×3次元=9ビット必要となるため、3次元をまとめて符号化することにより2ビット削除することができる。
【0149】
なお、符号化手段7から出力される符号化された量子化インデックスベクトルを照合する際(ある画像から抽出した量子化インデックスベクトルと、別の画像から抽出した量子化インデックスベクトルとを比較して、それらの画像が同一であるか否かを判定する際)は、符号化された状態から、各次元ごとの量子化インデックスの値を復号し(例えば上記の例では、各次元ごとに+1、0、−1の量子化インデックス値に復号し)、復号された量子化インデックスをもとに同一性尺度(量子化インデックスが一致する次元数(類似度)、あるいは量子化インデックスが非一致である次元数(ハミング距離))を算出してもよい。
【0150】
また、ルックアップテーブルを用いることで、符号化された状態のままで、各次元ごとの量子化インデックスの値に復号することなしに、照合を行うこともできる。すなわち、符号化された単位ごとに、あらかじめ同一性尺度(類似度や距離)をテーブル(ルックアップテーブル)の形で保存しておき、ルックアップテーブルを参照することにより、符号化された単位ごとの同一性尺度(類似度や距離)を取得し、それらを総計することで(例えば総和を算出する)、全次元の同一性尺度を算出することができる。
【0151】
例えば上記の、5次元ごとにまとめて1バイト(8ビット)に符号化された場合には、それぞれの5次元単位が243状態のいずれかであるため、243×243のサイズのルックアップテーブルをあらかじめ生成しておくことで、対処することができる。すなわち、比較する2つの5次元単位の符号の、可能な全ての組合せの状態(243状態×243状態)の間の同一性尺度、すなわち5次元のうち量子化インデックスが一致する数(類似度)、あるいは5次元のうち量子化インデックスが非一致である数(ハミング距離)をあらかじめ算出しておく。そしてそれを243×243のサイズのルックアップテーブルとして記憶しておく。そうすると、5次元単位ごとに、ルックアップテーブルを参照して(各次元ごとの量子化インデックスに復号することなしに)、5次元単位ごとの同一性尺度を取得することができる。例えば、量子化インデックスベクトルの全次元数が300次元の場合、5次元ごとに1バイトで、合計60バイトで符号化されているため、ルックアップテーブルを60回参照して、それぞれの5次元単位の同一性尺度を取得し、それらを総和することで全体(300次元)の同一性尺度(類似度あるいはハミング距離)を算出することができる。ルックアップテーブルを用いることで、各次元ごとの量子化インデックスへの復号を行うことなしに照合(同一性尺度の算出)が可能になるので、照合(同一性尺度の算出)の際の処理コストを低減することができ、高速な照合(同一性尺度の算出)が可能になる、という効果がある。
【0152】
また、2つの量子化インデックスベクトルの間の同一性尺度を、単純に量子化インデックスが一致する次元数(類似度)や、量子化インデックスが非一致である次元数(ハミング距離)として算出するのではなく、より複雑な計算式に基づいて算出する場合においても、ルックアップテーブルを用いることで、各次元ごとの量子化インデックスへの復号を行うことなしに照合(同一性尺度の算出)することができる。例えば、量子化インデックスが式2に基づいて算出された量子化インデックスベクトルの同一性尺度として、以下のような同一性尺度の算出方法を考える。まず、2つの画像の量子化インデックスベクトルを対応する次元どうしで比較して、「共に量子化インデックスが0」ではない次元の数を算出し、この値をAとする。次に、「共に量子化インデックスが0」ではない次元において、量子化インデックスが一致する次元数をBとして算出する(または、「共に量子化インデックスが0」ではない次元において、量子化インデックスが非一致である次元数をCとして算出する)。そして、同一性尺度をB/Aとして算出する(または、同一性尺度をC/Aとして算出する)。ただし、A=0の場合(すなわち、全ての次が共に量子化インデックスが0となる場合)は、同一性尺度を規定の数値(例えば0.5)とする。このような同一性尺度の算出方法を採用した場合、Aの値とBの値(またはCの値)の2つの値を算出する必要がある。この場合、5次元ごとのAの値を参照するための243×243のサイズのルックアップテーブルと、5次元ごとのBの値(またはCの値)を参照するための243×243のサイズのルックアップテーブルの、2つのルックアップテーブルをあらかじめ生成しておくことで、対処することができる。すなわち、比較する2つの5次元単位の符号の、可能な全ての組み合わせの状態(243状態×243状態)の間のAの値(「共に量子化インデックスが0」ではない次元数)と、可能な全ての組み合わせの状態(243状態×243状態)の間のBの値(またはCの値)をあらかじめ算出しておく。そしてそれぞれを243×243のサイズのルックアップテーブルとして記憶しておく。そうすると、5次元単位ごとに、ルックアップテーブルを参照して(各次元ごとの量子化インデックスを復号することなしに)、5次元単位ごとのAの値と、Bの値(またはCの値)を取得することができる。例えば、量子化インデックスベクトルの全次元数が300次元の場合、5次元ごとに1バイトで、合計60バイトで符号化されているため、ルックアップテーブルを60回×2参照して、それぞれの5次元単位のAの値とBの値(またはCの値)を取得し、全て5次元単位のAの値とBの値(またはCの値)を総和することで、全次元(300次元)のAの値とBの値(またはCの値)を算出することができる。そして、最後にB/A(またはC/A)を算出することで、同一性尺度を算出できる。このように、同一性尺度を、単純に量子化インデックスが一致する次元数(類似度)や、量子化インデックスが非一致である次元数(ハミング距離)として算出するのではなく、より複雑な計算式に基づいて算出する場合においても、複数のルックアップテーブルを用いることで、各次元ごとの量子化インデックスへの復号を行うことなしに照合(同一性尺度の算出)が可能になるので、照合(同一性尺度の算出)の際の処理コストを低減することができ、高速な照合(同一性尺度の算出)が可能になる、という効果がある。
【0153】
[第5の実施の形態の効果]
より小さいデータ量として、量子化インデックスベクトルを出力することができる。
【0154】
次に、本発明における第6〜第8の実施の形態を説明する。
【0155】
[第6の実施の形態]
第6の実施の形態では、抽出する特徴ベクトルの次元数は300次元(第1次元から第300次元)である。
【0156】
第6の実施の形態では、次元ごとの抽出領域(第1の抽出領域と第2の抽出領域)は、様々な形状の四角形から構成される。第6の実施の形態において、抽出領域取得手段2に入力として供給される次元別抽出領域情報を図14に示す。図14は、規定の画像サイズである、横幅320画素×縦幅240画素の画像サイズに対する、次元ごとの抽出領域(第1の抽出領域と第2の抽出領域)の四角形の四隅のXY座標値を示す。例えば、第1次元の抽出領域は、座標値(262.000,163.000)、座標値(178.068,230.967)、座標値(184.594,67.411)、座標値(100.662,135.378)を四隅とする四角形で構成される第1の抽出領域と、座標値(161.000,133.000)、座標値(156.027,132.477)、座標値(164.240,102.170)、座標値(159.268,101.647)を四隅とする四角形で構成される第1の抽出領域とで構成される。
【0157】
次元ごとの抽出領域(第1の抽出領域と第2の抽出領域)は、横幅320画素×縦幅240画素の画像サイズに正規化された画像に対して、この四隅の座標値で囲まれる領域の中に含まれる整数値の座標値の画素の集合となる。ただし、四隅の座標値で囲まれる領域の中に含まれる負の座標値は、抽出領域に含まない。
【0158】
第6の実施の形態において、領域特徴量算出方法取得手段5に入力として供給される次元別領域特徴量算出方法情報を図15に示す。第6の実施の形態では、全ての次元に対して、それぞれの抽出領域(第1の抽出領域と第2の抽出領域)に含まれる画素群の輝度値の平均値が、それぞれの抽出領域の領域特徴量となる。
【0159】
第6の実施の形態において、比較方法取得手段6に入力として供給される次元別比較・量子化方法情報を図17に示す。第6の実施の形態では、次元ごとに、比較・量子化方法Bまたは比較・量子化方法Gが用いられ、次元ごとにそのパラメータの値も異なる。例えば、第1次元は、比較・量子化方法Gで、閾値th=D(floor(300×5.0/100))である。また、例えば第2次元は、比較・量子化方法Gで、閾値th=D(floor(300×10.0/100))である。また、例えば第9次元は、比較・量子化方法Bで、閾値th=3.0である。
【0160】
[第7の実施の形態]
第7の実施の形態は、第6の実施の形態と同じく、抽出する特徴ベクトルの次元数は300次元(第1次元から第300次元)である。また第7の実施の形態では、抽出領域取得手段2に入力として供給される次元別抽出領域情報として、第6の実施の形態と同じく図14に示す情報を使用する。さらに第7の実施の形態では、比較方法取得手段6に入力として供給される次元別比較・量子化方法情報として、第6の実施の形態と同じく図17に示す情報を使用する。
【0161】
第7の実施の形態において、領域特徴量算出方法取得手段5に入力として供給される次元別領域特徴量算出方法情報を図16に示す。第7の実施の形態では、次元ごとに、抽出領域(第1の抽出領域と第2の抽出領域)に含まれる画素群の輝度値の平均値、または、パーセンタイル輝度値特徴量が用いられ、同じパーセンタイル輝度値特徴量を用いる場合でも、次元ごとにその特徴量は異なる。例えば、第1次元は、抽出領域に含まれる画素の輝度値の平均値である。また、例えば第4次元は、パーセンタイル輝度値特徴量で、Y(floor(N×20.0/100)である。また、第8次元は、パーセンタイル輝度値特徴量で、Y(floor(N×80.0/100)である。
【0162】
[第8の実施の形態]
第8の実施の形態は、抽出する特徴ベクトルの次元数は325次元(第1次元から第325次元)である。第8の実施の形態の場合は、各領域は、画像を縦方向32、横方向32に分割してできる1024個のブロックの組み合わせによって構成されている。ここで、各ブロックに対して、図28に示すように、左上から順に0から始まるインデックスを付与し、このインデックスを用いて領域を記述する。具体的には、長方形領域を、その左上のブロックのインデックスaと右下のブロックのインデックスbを用いてa−bのように表現する。例えば、インデックス0、1、32、33の4つのブロックからなる長方形は、0−33のように記述する。また、このようにしてできる長方形を記号“|”によって繋げた場合は、その記号の前後の長方形を連結してできる領域を表現するものとする。例えば、0−33|2−67は、0−33で定義される長方形と、2−67で定義される長方形を連結してできる領域、すなわち、ブロック番号0、1、2、3、32、33、34、35、66、67によって構成される領域を表している。
【0163】
この表記によって第8の実施の形態の各次元に対応する領域を示したものが図26である。図では、領域のタイプ別に図29−a、図29−b、図29−c、図29−d、図29−e、図29−f、図29−gに分けて上述の325次元を記述している。ここで、領域のタイプとは、第1、第2の抽出領域間の相対位置や形状の組み合わせによって定まる領域パターンが似たもの同士でグループ化(類型化)したものである。
【0164】
具体的には、図29−aの場合は、図31−aに一例を示すように、縦横4ブロックからなる正方形を縦方向か横方向に2等分してできる2つの領域を第1、第2の抽出領域とした場合に相当する。このため、第1、第2の抽出領域の形状は、ともに縦4ブロック、横2ブロックからなる長方形、あるいは縦2ブロック、横4ブロックからなる長方形である。また、第1、第2の抽出領域の相対的な位置関係を見ると、長方形の長い辺同士が重なるように隣接する位置に存在する。
【0165】
図29−bの場合は、図31−bに一例を示すように、縦横8ブロックからなる正方形を縦横2等分してできる4つの正方形のうち、左上と右下、右上と左下をそれぞれ組み合わせてできる2つの領域を第1、第2の抽出領域とした場合に相当する。このため、第1、第2の抽出領域の形状は、ともに縦横2ブロックからなる正方形を1つの頂点を共有するように45度あるいは135度の対角線上に2つ配置した形状となっている。また、領域の相対的な位置関係を見ると、第2の領域を構成する2つの正方形が、第1の領域の左上の正方形のすぐ左と下に隣接する位置に第2の領域が存在する。
【0166】
図29−cの場合は、図31−cに一例を示すように、第1、第2の抽出領域の形状は、ともに縦横10ブロックからなる正方形である。また、第1、第2の抽出領域の相対的な位置関係を見ると、縦横ともに10ブロックの整数倍だけ離れた位置に存在する。
【0167】
図29−dの場合は、図31−dに一例を示すように、第1、第2の抽出領域の形状は、ともに縦横6ブロックからなる正方形である。また第1、第2の抽出領域の相対的な位置関係を見ると、縦横ともに6ブロックの整数倍だけ離れた位置に存在する。
【0168】
図29−eの場合は、図31−eに一例を示すように、正方形領域を中心部分の正方形とその外側の2つに分けてできる2つの領域を第1、第2の抽出領域とした場合に相当する。このため、領域の形状は、第2の抽出領域が中心部分の正方形、第1の正方形は全体の正方形から第2の抽出領域をくりぬいた形状である。また、領域の相対的な位置関係を見ると、第1の抽出領域の中央の穴の位置に第2の抽出領域が存在する。
【0169】
図29−fの場合は、図31−fに一例を示すように、領域の形状は、第1の抽出領域は縦6ブロック、横10ブロックの長方形、第2の抽出領域は縦10ブロック、横6ブロックの長方形である。また、第1、第2の抽出領域の相対的な位置関係を見ると、中心位置が一致するように配置されている。
【0170】
図29−gの場合には、図31−gに一例を示すように、縦4ブロック、横12ブロックからなる長方形、あるいは縦12ブロック、横4ブロックからなる長方形を、長い辺を3等分してできる中央の正方形とそれ以外の2領域を第1、第2の抽出領域とした場合に相当する。このため、領域の形状は、第1の抽出領域は縦横4ブロックからなる正方形を2つ、縦か横に4ブロック離れて配置した形状で、第2の抽出領域は縦横4ブロックからなる正方形である。また、領域の相対的な位置関係を見ると、第1の抽出領域の間に第2の抽出領域が存在する。
【0171】
以後、図29−a、図29−b、図29−c、図29−d、図29−e、図29−f、図29−gの領域タイプを、それぞれ領域タイプa、領域タイプb、領域タイプc、領域タイプd、領域タイプe、領域タイプf、領域タイプgと呼ぶことにする。
【0172】
第8の実施の形態では、図29で示した各領域において、領域特徴量として輝度値の平均を算出し、各次元の特徴量を算出する。もちろん、輝度値の平均のかわりにメディアンや最大値など、前述の様々な抽出方法によって抽出した値を領域特徴量として求めるようにしてもよい。
【0173】
各次元の特徴量の量子化では、上述の領域のタイプ別に閾値を定め、量子化を行うようにする。例えば、式2に従って特徴量を3値に量子化する場合には、領域のタイプ別に、0、1、−1の生起の割合が均等になるように量子化の閾値thを決定し、量子化を行うようにする。具体的には、段落0085で記述した方法をP=33.333%、Nを領域タイプ別の次元数として領域タイプ別に適用し、閾値thを求める。例えば、領域タイプaの場合にはN=113となるため、th=D(floor(113×33.333/100))=D(37)により閾値を算出する。ここで、D(i)(i=0、1、…、N−1)は、領域タイプaに該当する第1次元から第113次元の差分値の絶対値を昇順にソートした集合になる。この場合は閾値に対応するインデックスが37となる。同様に、他の領域タイプに対しても、閾値に対応するインデックスを求めることができる。これを示したのが図30である。このように領域タイプ別に閾値を求める方が、全体で閾値を決める場合に比べて各次元での0、1、−1の発生確率を均一化できるようになり、識別能力が向上する。もちろん、前述の他の様々な量子化方法によって量子化するようにしてもよい。
【0174】
なお、第8の実施の形態の場合には、図28で示したブロックごとに代表値(例えば、ブロック内の画素の輝度値の平均値)を先に算出し、それから領域特徴量を抽出するようにしてもよい。これにより、領域内の全画素から直接領域特徴量を抽出する場合よりも高速に抽出できるようになる。また、各領域タイプの抽出領域は、全体として対称性を有する。このため、画像の右と左を反転させたり、上下を反転させたりした場合でも、次元の対応関係と符号を適切に変更することによって、左右または上下反転した画像から抽出された特徴量からもとの画像の特徴量を復元できる。このため、左右あるいは上下を反転させた画像とも照合することができるようになる。
【0175】
[照合手段の実施の形態]
次に、本発明で出力される量子化インデックスベクトルを照合する照合手段についてブロック図を用いて説明する。
【0176】
図21を参照すると、本発明で出力される量子化インデックスベクトルを照合する照合手段100のブロック図が示されており、次元決定手段101、量子化値取得手段102、103、尺度算出手段104とからなる。
【0177】
次元決定手段101は量子化値取得手段102、103へ接続され、決定された次元情報を出力する。量子化値取得手段102は、第1の量子化インデックスベクトルから、次元決定手段101から入力される次元の量子化インデックス値を取得し、第1の量子化インデックス値として尺度算出手段104へ出力する。量子化値取得手段103は、第2の量子化インデックスベクトルから、次元決定手段101から入力される次元の量子化インデックス値を取得し、第2の量子化インデックス値として尺度算出手段104へ出力する。尺度算出手段104は、量子化値取得手段102、103からそれぞれ出力される第1、第2の量子化インデックス値から同一性を表す尺度を算出し、出力する。
【0178】
次に、図21の照合手段100の動作について説明する。
【0179】
まず、照合手段100へは、第1の画像から抽出される量子化インデックスベクトルである第1の量子化インデックスベクトルと、第2の画像から抽出される量子化インデックスベクトルである第2の量子化インデックスベクトルとが入力される。入力された第1、第2の量子化インデックスベクトルは、それぞれ量子化値取得手段102、103へ入力される。
【0180】
量子化値取得手段102、103へは、次元決定手段101から出力される次元情報も入力される。次元決定手段101では、N次元ベクトルである量子化インデックスベクトルの各次元を指定する情報を順次出力する。出力する順序は必ずしも1からNまで1つずつ増えていく必要はなく、1からNまでの次元が過不足なく指定される順序であれば、どのような順序であってもよい。
【0181】
量子化値取得手段102、103では、入力された量子化インデックスベクトルから、次元決定手段101から出力される次元情報で指定される次元の量子化インデックス値を取得する。そして、取得した量子化インデックス値を尺度算出手段104へ出力する。
【0182】
尺度算出手段104では、量子化値取得手段102から出力される第1の量子化インデックス値と第2の量子化インデックス値とを比較する。この比較を各次元に対して行い、第1、第2の量子化インデックスベクトル間の類似尺度(あるいは距離尺度)を同一性尺度として算出する。
【0183】
得られた同一性尺度値は予め定めた閾値と比較し、同一性の判定を行う。同一性尺度が類似度をあらわす尺度である場合には、尺度値が閾値以上の場合に同一と判定する。一方、同一性尺度が距離をあらわす尺度である場合には、尺度値が閾値以下の場合に同一と判定する。
【0184】
次に、フローチャートを用いて図21の照合手段100の動作を説明する。まず、同一性尺度として類似度を用いる場合の動作について説明する。
【0185】
図22は、照合手段100の動作を示すフローチャートである。図22のフローチャートでは、量子化インデックスベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。また、類似度を算出する変数をBで表すこととする。
【0186】
まず、次元決定手段101は、照合する量子化インデックスベクトルの最初の次元として、次元1を決定し(n=1)、量子化値取得手段102、103へ供給するとともに、尺度算出手段104において変数Bを0にセットする。(ステップS100)。
【0187】
次に、量子化値取得手段102、103において、第1の量子化インデックスベクトル、第2の量子化インデックスベクトルから、次元nの第1の量子化インデックス値と第2の量子化インデックス値とを取得し、尺度算出手段104へ供給する(ステップS102)。
【0188】
次に、尺度算出手段104において、第1の量子化インデックス値と第2の量子化インデックス値とから、それぞれの量子化インデックスに対応する特徴量の間の類似度ΔBを算出する(ステップS104)。例えば、量子化インデックスが一致する場合にはΔB=1とし、それ以外の場合はΔB=0とする。あるいは、量子化インデックスから量子化前の特徴量の代表値を算出し、代表値間の差分が小さいほど大きくなる値をΔBとして用いてもよい。この際、特徴量の代表値を算出して差分を求めるかわりに、量子化インデックス値の組み合わせによってΔBの値を引くことができるテーブルを保持しておき、量子化インデックス値の組み合わせからこのテーブルを用いてΔBの値を直接求めるようになっていてもよい。
【0189】
次に、ΔBの値は変数Bに加算される(ステップS106)。この際、ΔBの値が0の場合には、変数Bに0を加算するかわりに、加算しないように制御してもよい。
【0190】
次に、次元の番号nが次元数Nに到達したかどうかを調べ(ステップS108)、到達しない場合はステップS112へ移行し、到達した場合には、そのときの変数Bの値を同一性尺度(類似度を表す尺度)として出力し(ステップS110)、処理を終了する。
【0191】
ステップ112では、次元決定手段101が、取得する量子化インデックスの次元として、n=n+1によって次の次元を決定し、量子化値取得手段102、103へ供給する。そして、再度ステップS102へ移行する。
【0192】
なお、ここでは、次元1からNまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0193】
次に、同一性尺度として距離を用いる場合の動作について説明する。
【0194】
図23は、照合手段100の動作を示す別のフローチャートである。図23のフローチャートでも、量子化インデックスベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。また、距離尺度を算出する変数をCで表すこととする。
【0195】
基本的なフローは、図22の場合と同じであるが、ステップS100、S104、S106、S110がそれぞれステップS200、S204、S206、S210に置き換わっている点が異なる。
【0196】
まず、ステップS200では、次元決定手段101において、照合する量子化インデックスベクトルの最初の次元として、次元1を決定し(n=1)、量子化値取得手段102、103へ供給するとともに、尺度算出手段104において変数Cを0にセットする。
【0197】
ステップS204では、尺度算出手段104において、第1の量子化インデックス値と第2の量子化インデックス値とから、それぞれの量子化インデックスに対応する特徴量の距離ΔCを算出する。例えば、量子化インデックスが一致する場合にはΔC=0とし、それ以外の場合はΔC=1とする。あるいは、量子化インデックスから量子化前の特徴量の代表値を算出し、代表値間の差分が小さいほど小さくなる値をΔCとして用いてもよい。この際、特徴量の代表値を算出して差分を求めるかわりに、量子化インデックス値の組み合わせによってΔCの値を引くことができるテーブルを保持しておき、量子化インデックス値の組み合わせからこのテーブルを用いてΔCの値を直接求めるようになっていてもよい。
【0198】
ステップS206では、ΔCの値は変数Cに加算される。この際、ΔCの値が0の場合には、変数Cに0を加算するかわりに、加算しないように制御してもよい。
【0199】
ステップS210では、そのときの変数Cの値を同一性尺度(距離を表す尺度)として出力し、処理を終了する。
【0200】
それ以外のステップについては、図22の場合と同様である。ただし、ステップS108で次元の番号nが次元数Nに到達した場合にはステップS210へ移行する。
【0201】
なお、ここでは、次元1からNまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0202】
次に、第1の量子化インデックス値と第2の量子化インデックス値とで、「共に量子化インデックスが0」である次元を除外し、同一性尺度として類似度を用いる場合の動作について説明する。
【0203】
図24は、照合手段100の動作を示す別のフローチャートである。図24のフローチャートでも、量子化インデックスベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。また、類似度を算出する変数をBで表すこととし、「共に量子化インデックスが0」ではない次元をカウントするための変数をAで表すこととする。
【0204】
まず、次元決定手段101は、照合する量子化インデックスベクトルの最初の次元として、次元1を決定し(n=1)、量子化値取得手段102、103へ供給するとともに、尺度算出手段104において変数A、Bを0にセットし(ステップS300)、ステップS102へ移行する。
【0205】
ステップS102は図22の場合と同様であり、終了後、ステップS314へ移行する。
【0206】
ステップS314では、尺度算出手段104において、第1の量子化インデックス値と第2の量子化インデックス値とがともに0であるかどうかを調べる。ともに0である場合には、ステップS108へ移行し、どちらか一方が0でない場合には、変数Aの値をひとつ増やし(ステップS316)、ステップS104へ移行する。
【0207】
ステップS104、S106、S108、S112の動作は図22の場合と同様である。ステップS108で次元の番号nが次元数Nに到達した場合には、ステップS310へ移行する。
【0208】
ステップS310では、尺度算出手段104において、B/Aの値を算出し、同一性尺度として出力し、処理を終了する。ただし、A=0の場合には、規定の値(例えば0.5)を出力する。
【0209】
なお、ここでは、次元1からNまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0210】
[照合手段の別の実施の形態]
次に、本発明で出力される量子化インデックスベクトルを照合する照合手段の別の実施の形態についてブロック図を用いて説明する。
【0211】
図25を参照すると、本発明で出力される量子化インデックスベクトルを照合する照合手段200のブロック図が示されており、符号決定手段201、符号値取得手段202、203、尺度算出手段204とからなる。
【0212】
符号決定手段201は符号値取得手段202、203へ接続され、決定された符号指定情報を出力する。符号値取得手段202は、第1の符号化量子化インデックスベクトルから、符号決定手段201から入力される符号指定情報により定まる符号の値を取得し、第1の符号値として尺度算出手段204へ出力する。符号値取得手段203は、第2の符号化量子化インデックスベクトルから、符号決定手段201から入力される符号指定情報により定まる符号の値を取得し、第2の符号値として尺度算出手段204へ出力する。尺度算出手段204は、符号値取得手段202、203からそれぞれ出力される第1、第2の符号値から同一性を表す尺度を算出し、出力する。
【0213】
次に、図25の照合手段200の動作について説明する。
【0214】
まず、照合手段200へは、第1の画像から抽出される量子化インデックスベクトルを符号化したベクトルである第1の符号化量子化インデックスベクトルと、第2の画像から抽出される量子化インデックスベクトルを符号化したベクトルである第2の符号化量子化インデックスベクトルとが入力される。ここで、符号化量子化インデックスベクトルは、量子化インデックスベクトルの量子化インデックス値を複数次元分まとめて符号化して得られる符号からなる符号列である。段落0142で説明したように、特徴ベクトルの各次元の特徴量を3値に量子化し、5次元分まとめて符号化する場合には、5次元ごとに1つの符号が生成される。よって、特徴ベクトルの次元数がNの場合には、N/5個の符号が生成される。この場合、符号化量子化インデックスベクトルはN/5個の符号からなる符号列となる。
【0215】
入力された第1、第2の符号化量子化インデックスベクトルは、それぞれ符号値取得手段202、203へ入力される。
【0216】
符号値取得手段202、203へは、符号決定手段201から出力される符号指定情報も入力される。符号決定手段201では、符号列中の各符号を指定する情報を順次出力する。符号列中の符号の数をM(上述の例ではM=N/5)とすると、出力する順序は必ずしも1からMまで1つずつ増えていく必要はなく、1からMまでの値が過不足なく指定される順序であれば、どのような順序であってもよい。
【0217】
符号値取得手段202、203では、入力された符号化量子化インデックスベクトルから、符号決定手段201から出力される符号指定情報で指定される符号の値を取得する。そして、取得した符号値を尺度算出手段204へ出力する。
【0218】
尺度算出手段204では、符号取得手段201、202から出力される第1の符号値と第2の符号値とを比較する。この際、符号値を復号して量子化インデックス値に戻してから比較するのではなく、符号値のまま比較する。段落0150から段落0152で説明したように、尺度算出手段204では、2つの符号値からそれらの符号の間の同一性尺度をひくことができるルックアップテーブルが用意されており、これを用いて符号単位で同一性尺度を算出する。これを各符号に対して行い、第1、第2の符号値間の類似尺度(あるいは距離尺度)を同一性尺度として算出する。
【0219】
得られた同一性尺度値は予め定めた閾値と比較し、同一性の判定を行う。同一性尺度が類似度をあらわす尺度である場合には、尺度値が閾値以上の場合に同一と判定する。一方、同一性尺度が距離をあらわす尺度である場合には、尺度値が閾値以下の場合に同一と判定する。
【0220】
次に、フローチャートを用いて図25の照合手段200の動作を説明する。ここでは、同一性尺度として類似度を用いる場合の動作について説明する。
【0221】
図26は、照合手段200の動作を示すフローチャートである。図26のフローチャートでは、符号化量子化インデックスベクトルの符号の番号をmで表し、番号は1からMまでの合計M個の符号があるものとする。また、類似度を算出する変数をBで表すこととする。
【0222】
まず、符号決定手段201は、照合する符号化量子化インデックスベクトルの最初の符号として、1番目の符号を取得することを決定し(m=1)、符号値取得手段202、203へ供給するとともに、尺度算出手段204において変数Bを0にセットする。(ステップS600)。
【0223】
次に、符号値取得手段202、203において、第1の符号化量子化インデックスベクトル、第2の符号化量子化インデックスベクトルから、m番目の第1の符号値と第2の符号値とを取得し、尺度算出手段204へ供給する(ステップS602)。
【0224】
次に、尺度算出手段204において、第1の符号値と第2の符号値とから、それぞれの符号値に対応する複数次元の特徴量間の類似度ΔBを、段落0150で説明したルックアップテーブルを参照することにより算出する(ステップS604)。
【0225】
次に、ΔBの値は変数Bに加算される(ステップS106)。この際、ΔBの値が0の場合には、変数Bに0を加算するかわりに、加算しないように制御してもよい。
【0226】
次に、符号の番号mが符号数Mに到達したかどうかを調べ(ステップS608)、到達しない場合はステップS612へ移行し、到達した場合には、そのときの変数Bの値を同一性尺度(類似度を表す尺度)として出力し(ステップS110)、処理を終了する。
【0227】
ステップ612では、符号決定手段201が、取得する量子化インデックスの次元として、m=m+1によって次の符号の番号を決定し、符号指定情報として符号値取得手段202、203へ供給する。そして、再度ステップS602へ移行する。
【0228】
なお、ここでは、符号の番号1からMまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。また、ここでは類似度を算出する場合について述べたが、同様にして、距離尺度を同一性尺度として算出することもできる。この場合、ルックアップテーブルには、類似度の変わりに距離尺度を保持しておくようにする。
【0229】
図27は、照合手段200の動作を示す別のフローチャートである。図27のフローチャートでも、符号化量子化インデックスベクトルの符号の番号をmで表し、番号は1からMまでの合計M個の符号があるものとする。また、類似度を算出する変数をBで表すこととし、「共に量子化インデックスが0」ではない次元をカウントするための変数をAで表すこととする。
【0230】
まず、符号決定手段201は、照合する符号化量子化インデックスベクトルの最初の符号として、1番目の符号を取得することを決定し(m=1)、符号値取得手段202、203へ供給するとともに、尺度算出手段204において変数A、Bを0にセットし(ステップS700)、ステップS602へ移行する。
【0231】
ステップS602は図26の場合と同様であり、終了後、ステップS714へ移行する。
【0232】
ステップS714では、尺度算出手段204において、第1の符号値と第2の符号値とから、符号値に対応する複数の特徴ベクトルの次元内に、「ともに0」とはならない次元がいくつあるかを調べる。この数をΔAとする。これも、段落0152で述べたように、符号値とΔAとの関係を記述したルックアップテーブルを用いることによって算出できる。
【0233】
次に、ΔAの値は変数Aに加算される(ステップS716)。この際、ΔAの値が0の場合には、変数Aに0を加算するかわりに、加算しないように制御してもよい。
【0234】
ステップS604、S106、S608、S612の処理は図26の場合と同様である。ステップS608で符号の番号mが符号数Mに到達した場合には、ステップS310へ移行する。
【0235】
ステップS310では、尺度算出手段204において、B/Aの値を算出し、同一性尺度として出力し、処理を終了する。ただし、A=0の場合には、規定の値(例えば0.5)を出力する。
【0236】
なお、ここでは、符号の番号mからMまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。また、ここでは類似度を算出する場合について述べたが、同様にして、距離尺度を同一性尺度として算出することもできる。この場合、ルックアップテーブルには、類似度の変わりに距離尺度を保持しておくようにする。
【0237】
以上本発明の実施の形態について説明したが、本発明は、上述した実施形態に限定されるものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解しうる様々な変更をすることができる。また、本発明の画像識別子抽出装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における次元決定手段、抽出領域取得手段、領域特徴量算出手段、比較手段、領域特徴量算出方法取得手段、比較方法取得手段として機能させる。
【0238】
なお、本発明は、日本国にて2009年3月13日に特許出願された特願2009−061022の特許出願、および日本国にて2009年4月14日に特許出願された特願2009−097864の特許出願に基づく優先権主張の利益を享受するものであり、当該特許出願に記載された内容は、全て本明細書に含まれるものとする。
【符号の説明】
【0239】
1…次元決定手段
2…抽出領域取得手段
3、3A…領域特徴量算出手段
31、31A…第1の領域特徴量算出手段
32、32A…第2の領域特徴量算出手段
4、4B…比較手段
41…大小比較手段
42、44…量子化手段
43…差分値算出手段
45…量子化境界決定手段
5…領域特徴量算出方法取得手段
6…比較方法取得手段
7…符号化手段
【技術分野】
【0001】
本発明は、画像を識別する(同一性を判定する)ための特徴量である画像識別子を抽出する装置に関する。
【背景技術】
【0002】
画像識別子は、画像を識別する(同一性を判定する)ための画像特徴量である。ある画像から抽出した画像識別子と、別の画像から抽出した画像識別子とを比較し、その比較結果から、2つの画像が同一である度合いを示す同一性尺度(一般的には、類似度または距離という)を算出することができる。また、算出した同一性尺度をある閾値と比較することにより、2つの画像が同一であるか否かを判定することができる。ここで「2つの画像が同一」とは、画像信号(画像を構成する画素の画素値)のレベルで2つの画像が同一である場合だけに限らず、画像の圧縮形式(フォーマット)の変換、画像のサイズ・アスペクト比の変換、画像の色調の調整、画像への各種フィルタ処理(鮮鋭化、平滑化など)、画像への局所的な加工(テロップ重畳、切抜きなど)、画像の再キャプチャリング、などの各種改変処理によって、一方の画像が他方の画像の複製された画像である場合も含む。画像識別子を用いれば、例えば、画像、または画像の集合体である動画像の複製を検知できるため、画像または動画像の違法コピー検知システムなどに応用することができる。
【0003】
画像識別子の一例が、特許文献1に記載されている。図18は、特許文献1に記載されている画像識別子の抽出方法を示す図である。この画像識別子は、複数の次元(図18では16次元)の特徴ベクトルである。画像240内のあらかじめ定められた位置の32個の長方形領域244(図18ではそのうち16個の長方形領域が描かれている)からそれぞれ平均輝度値を算出し、対となる長方形領域の間(図18では対となる長方形領域を点線248で結んでいる)で平均輝度値の差を算出し、16次元の差ベクトル250を求める。差ベクトル250に対してベクトル変換により合成ベクトルを生成し、合成ベクトルの各次元を量子化して得られた16次元の量子化インデックスベクトルを画像識別子とする。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特表平8−500471号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
複数の次元の特徴ベクトルで構成される画像識別子は、次元間の相関が小さいほど、特徴ベクトルが持つ情報量が大きい(冗長性が小さい)ので、異なる画像を識別できる度合いである識別能力が高くなる。反対に、特徴ベクトルの次元間の相関が大きいと、特徴ベクトルが持つ情報量が小さい(冗長性が大きい)ので、識別能力が低くなる。ここで次元間の相関とは、次元の特徴量の生起の類似性の度合いであり、数学的には、例えば、各次元の特徴量の生起を確率変数とした場合の、確率変数間の相関係数や、相互情報量として算出できる値である。このため、複数の次元の特徴ベクトルで構成される画像識別子は、次元間の相関が小さくなるように設計されていることが望ましい。
【0006】
画像信号(画像を構成する画素の画素値)は、画像の局所領域間において相関がある。一般的に、局所領域間の距離が近いほど、相関は大きくなる。特に、例えば、ある特定の画像パターンが繰り返し出現する(特にそれが規則正しい周期で出現する場合に)画像(例えば格子状に配置されたビルの窓の画像など、図19(A)を参照)や、ある特定のテクスチャで構成されている画像(図19(B)を参照)などは、画像の局所領域間の相関が大きくなる。
【0007】
[第1の問題点]
特許文献1に記載されているような、画像の複数の局所領域から抽出した特徴量から成る特徴ベクトルで構成されている画像識別子は、画像の局所領域間の相関が大きい画像に対して、各次元において特徴量を抽出する局所領域の形状が同一であるため(特許文献1の例では同一の形状の長方形領域)、抽出される特徴量の次元間の相関が大きくなる。そのため、画像識別子(特徴ベクトル)の識別能力が低くなる、という第1の問題点がある。ここで形状が同一とは、領域の大きさや角度(傾き或いは姿勢)も含めて同一であるということである。
【0008】
例えば、ある特定の画像パターンが繰り返し出現する画像(図19(A)参照)や、ある特定のテクスチャで構成されている画像(図19(B)参照)などに対しては、特許文献1で記載されているような画像識別子は、識別能力が低くなる。
【0009】
[第2の問題点]
特許文献1に記載されている画像識別子の第2の問題点は、特徴量(特徴ベクトル)を算出するための各次元の領域の形状(大きさ、角度も含めて)が同一の長方形であるため、長方形の辺の長さと同じ、あるいは、その整数分の1の周期を持つ周波数成分を検知できないという、周波数上の盲点が存在するということである。その理由は、この特定の周波数の信号成分について領域内で平均をとると、信号成分の大小によらず0となってしまい、その周波数成分の信号を全く検知できなくなるためである。より具体的には、長方形の辺の長さと同じ周期を持つ周波数をf0とすると,周波数nf0(n=1,2,3,…)の成分が検知できなくなる。このため、直流成分とこの周波数成分に信号が集中している画像に対しては、画素値の平均値は直流成分と同じになってしまい、領域間で値の差がなくなる結果、領域間の平均画素値の差として抽出される特徴量は全て0になってしまい、識別できなくなる(識別能力が著しく低下する)。実際には、周波数nf0(n=1,2,3,…)の成分のみではなく、その近傍の一定の周波数領域に対しては同様に検知困難となるため、上記特定周波数に信号成分が集中していなくても、その周波数帯の信号成分が使えないことにより、識別能力が低下する。この問題を軽減するには、周波数f0の値を大きくし、上記検知困難な周波数帯に陥る信号電力を下げることが考えられる。しかしながら、周波数f0の値を大きくすることは、領域の大きさを小さくすることを意味し、特徴量の頑健性(各種改変処理やノイズに対して特徴量が変化しない度合い)の低下につながる。例えば、領域が小さくなることで、多少の位置ずれに対しても、特徴量の値が大きく変化することになり、特徴量の頑健性が下がる。このように、同一の長方形領域を用いる場合には、識別能力をあげた上で頑健性を確保することが極めて難しい。
【0010】
[発明の目的]
本発明の目的は、画像の局所領域間の相関が大きい画像や特定の周波数に信号が集中している画像から抽出される画像識別子は異なる画像を識別できる度合いである識別能力が低下する、という課題を解決する画像識別子抽出装置を提供することである。
【課題を解決するための手段】
【0011】
本発明の一形態にかかる画像識別子抽出装置は、対をなす2つの部分領域の形状の組み合わせと、対をなす2つの部分領域の相対的な位置関係との双方が、他の少なくとも1つの部分領域対と相違する1以上の部分領域対を含む、画像中の複数の部分領域対に従って、画像の各部分領域から領域特徴量を抽出し、該抽出した各部分領域毎の領域特徴量に基づいて、上記画像の識別に用いる画像識別子を生成する画像識別子生成手段と、上記画像識別子を符号化する符号化手段とを備える。
【発明の効果】
【0012】
本発明は上述したように構成されているため、画像識別子の、異なる画像を識別できる度合いである識別能力を高くすることができる。特に、画像の局所領域間の相関が大きい画像に対して、この効果は顕著である。
【0013】
また本発明によれば、特定の周波数に信号が集中している画像に対しても、識別能力が低下しないという効果がある。
【図面の簡単な説明】
【0014】
【図1】本発明の第1の実施の形態のブロック図である。
【図2】次元別抽出情報が示す次元ごとの抽出領域の対の例を示す図である。
【図3】本発明の第1の実施の形態における比較手段の一例を示すブロック図である。
【図4】本発明の第1の実施の形態における比較手段の別の例を示すブロック図である。
【図5】本発明の第1の実施の形態の処理の流れを示すフローチャートである。
【図6】本発明の第2の実施の形態の要部ブロック図である。
【図7】本発明の第2の実施の形態の処理の流れを示すフローチャートである。
【図8】本発明の第3の実施の形態のブロック図である。
【図9】次元ごとの領域特徴量算出方法の例を示す図である。
【図10】本発明の第3の実施の形態の処理の流れを示すフローチャートである。
【図11】本発明の第4の実施の形態のブロック図である。
【図12】次元ごとの比較・量子化方法の例を示す図である。
【図13】本発明の第4の実施の形態の処理の流れを示すフローチャートである。
【図14−a】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−b】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−c】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−d】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−e】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−f】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−g】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−h】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−i】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図14−j】本発明の第6の実施の形態および第7の実施の形態で使用する次元別抽出領域情報を示す図である。
【図15−a】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−b】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−c】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−d】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図15−e】本発明の第6の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−a】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−b】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−c】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−d】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図16−e】本発明の第7の実施の形態で使用する次元別領域特徴量算出方法情報を示す図である。
【図17−a】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−b】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−c】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−d】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図17−e】本発明の第6の実施の形態および第7の実施の形態で使用する次元別比較・量子化方法情報を示す図である。
【図18】特許文献1に記載されている画像識別子の抽出方法を示す図である。
【図19】局所領域間の相関が大きくなる画像の例を示す図である。
【図20】本発明の第5の実施の形態のブロック図である。
【図21】量子化インデックスベクトルを照合する照合手段のブロック図である。
【図22】量子化インデックスベクトルを照合する照合手段の処理例を示すフローチャートである。
【図23】量子化インデックスベクトルを照合する照合手段の別の処理例を示すフローチャートである。
【図24】量子化インデックスベクトルを照合する照合手段の更に別の処理例を示すフローチャートである。
【図25】量子化インデックスベクトルを照合する照合手段の別の構成のブロック図である。
【図26】量子化インデックスベクトルを照合する照合手段の処理例を示すフローチャートである。
【図27】量子化インデックスベクトルを照合する照合手段の別の処理例を示すフローチャートである。
【図28】画像を縦方向32、横方向32に分割してできる1024個のブロックに対して付与するインデックスの一例を示す図である。
【図29−a】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−b】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−c】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−d】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−e】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−f】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図29−g】本発明の第8の実施の形態の各次元に対応する領域のうち或る1つのタイプに属する領域を示す図である。
【図30】各次元の領域タイプと次元数、閾値に対応するインデックスとの関係を示す図である。
【図31−a】領域タイプaの次元の第1、第2の抽出領域の一例を示す図である。
【図31−b】領域タイプbの次元の第1、第2の抽出領域の一例を示す図である。
【図31−c】領域タイプcの次元の第1、第2の抽出領域の一例を示す図である。
【図31−d】領域タイプdの次元の第1、第2の抽出領域の一例を示す図である。
【図31−e】領域タイプeの次元の第1、第2の抽出領域の一例を示す図である。
【図31−f】領域タイプfの次元の第1、第2の抽出領域の一例を示す図である。
【図31−g】領域タイプgの次元の第1、第2の抽出領域の一例を示す図である。
【発明を実施するための形態】
【0015】
[第1の実施の形態]
[第1の実施の形態の構成]
次に、本発明の第1の実施の形態について図面を参照して詳細に説明する。
【0016】
図1を参照すると、本発明の第1の実施の形態に係る画像識別子抽出装置は、入力された画像に対して、複数の次元から成る特徴ベクトル(より具体的には量子化インデックスベクトル)を画像識別子として出力するシステムであり、次元決定手段1と、抽出領域取得手段2と、領域特徴量算出手段3と、比較手段4と、から構成されている。
【0017】
次元決定手段1は、次に抽出する特徴ベクトルの次元を決定し、抽出領域取得手段2へ供給する。次元決定手段1は、順次、抽出する特徴ベクトルの次元を供給し、抽出領域取得手段2以降の構成要素は、供給された次元に対応する特徴量を抽出する。例えば、特徴ベクトルがN次元から構成される場合、次元決定手段1は第1次元から第N次元までを順に抽出領域取得手段2へ供給してもよい。最終的に特徴ベクトルの全ての次元が供給されれば、供給する次元の順番は任意でよい。複数の次元が並列に供給されてもよい。
【0018】
抽出領域取得手段2には、次元決定手段1からの次元とは別に、入力として次元別抽出領域情報が供給される。
【0019】
次元別抽出領域情報は、あらかじめ規定された、特徴ベクトルの次元ごとに対応付けられた、その次元の特徴量を抽出するための第1の抽出領域と第2の抽出領域の対を示す情報である。第1および第2の抽出領域は必須条件として、以下の特徴を有する。
【0020】
[第1および第2の抽出領域の必須条件]
第1および第2の抽出領域の必須条件は、次元間で抽出領域対の相対的な位置が異なることに加えて、次元間で抽出領域対の形状の組み合わせが異なることである。
【0021】
上記必須条件を満たす、次元別抽出情報が示す次元ごとの抽出領域の対の例を図2に示す。図18に示した画像識別子の抽出領域とは異なり、次元間の抽出領域の対の形状の組み合わせが異なる。ここで異なる形状とは、角度の異なる合同な形状や(例えば、図2の第1次元の第2の抽出領域と、第7次元の第1の抽出領域)、大きさの異なる相似な形状(例えば、図2の第1次元の第2の抽出領域と、第9次元の第2の抽出領域)も含む。なお、特徴ベクトルの全次元の中に、抽出領域の対の形状の組み合わせの異なる次元のペアが、少なくとも1つ存在することが最低条件である。抽出領域の対の形状(の組み合わせ)が相互に異なる次元が多いほど、望ましい。これは、抽出領域の対の形状(の組み合わせ)が相互に異なる次元が多いほど、特徴ベクトルのより多くの次元間で相関が小さくなり、識別能力が高くなるからである。例えば、特徴ベクトルの全ての次元間で、抽出領域の対の形状(の組み合わせ)が相互に異なっていてもよい。
【0022】
ある次元における第1の抽出領域と、第2の抽出領域とは、図2の第9次元のように、同じ形状である必要はなく、図2の他の次元のように、形状が異なっていてもよい。各次元での第1の抽出領域と第2の抽出領域の形状が異なっていると、第1の抽出領域と第2の抽出領域から抽出される特徴量の相関が小さくなり、識別能力が高くなるため、望ましい。また、第1の抽出領域と第2の抽出領域が同時に同じ周波数に関して周波数的な盲点となる可能性が低くなるため、識別能力が高くなる。
【0023】
各々の抽出領域の形状は任意である。例えば、図2の第6次元の第2の抽出領域のような、任意の複雑な形状であっても構わない。画像の複数の画素で構成されるものであれば、例えば、図2の第7次元や第10次元のように、線分や曲線であっても構わない。また例えば、第8次元の第1の抽出領域、第11次元の第1と第2の抽出領域、第12次元の第1の抽出領域のように、抽出領域が、連続しない複数の小領域から構成されるものであってもよい。このように、任意の複雑な形状の抽出領域を含むことによって、そこから抽出される特徴量の次元間の相関を小さくすることができ、識別能力を高くすることができる。
【0024】
また、例えば、図2の第5次元のように、第1の抽出領域と第2の抽出領域の一部が重複していてもよい。また抽出領域対のいずれか一方が、もう一方の中に内包されていてもよい。このように、抽出領域の対に重複を許容することにより、より多くの抽出領域対のパターン(相対的位置・距離)を取れるため、次元間の相関を小さくすることができるパターンを増やすことができ、識別能力をより高くする可能性が増える。
【0025】
また、図18に示した画像識別子の抽出領域とは異なり、図2に示した各次元のように、次元間で抽出領域が一部重複していてもよい。図18に示した画像識別子の抽出領域のように、次元間で抽出領域を排他的に取ると、取れる抽出領域対のパターンが限られてしまう。図2に示したように、次元間での抽出領域に重複を許容することにより、より多くの抽出領域対のパターンを取れるため、次元間の相関を小さくすることができるパターンを増やすことができ、識別能力をより高くする可能性が増える。ただし、次元間での抽出領域の重複が多すぎると、次元間の相関が大きくなってしまい、識別能力が低くなるため、望ましくない。
【0026】
また、全ての次元の抽出領域を統合した場合に、画像内で特徴量が抽出されない領域が小さくなるような(すなわち、画像のほぼ全画面をカバーする)抽出領域の取り方であることが望ましい。これは、図18のように、画像内で特徴量が抽出されない領域が多く含まれていると、画像信号(画像を構成する画素の画素値)に含まれる多くの情報を使用しないことになり、識別能力が高くならないためである。全ての次元の抽出領域を統合した場合に、画像内で特徴量が抽出されない領域が小さくなるような(すなわち、画像のほぼ全画面をカバーする)抽出領域の取り方であることにより、画像信号に含まれるより多くの情報を特徴量に反映できるため、識別能力を高くすることができる。また、全ての次元の抽出領域を統合した場合に、抽出領域に偏りがなく、画像全体から満遍なく取得されていることが望ましい。ただし、ある特定の領域にテロップ重畳などの局所的な加工が施される確率が高い場合は、その領域を避けて抽出領域が取得されていることが望ましい。また、画像の縁などの周辺領域には画像の特徴部分が一般的に存在しないことが多いため、周辺領域を避けて抽出領域が取得されていることが望ましい。
【0027】
その他、抽出領域の大きさ、相対的位置(距離、方向)が一定の分布(例えば一様分布)に従うことが望ましい。その理由は、相対的位置(距離、方向)が一様分布に従うことによって、距離や方向に対して偏りがなく、特定の距離や方向に集中することがないため、より多くの多様性がとれるためである。また、相対的位置が近いほど、その領域間の相関が大きくなるため、それを打ち消すために、相対的位置が近いものほどより形状の差が大きいほうが望ましい。
【0028】
次元別抽出領域情報は、次元ごとの第1の抽出領域と第2の抽出領域とが一意に特定できる情報であれば、どのような形式の情報であっても構わない。また抽出領域は、如何なるサイズやアスペクト比の画像に対しても、常に同じ領域である必要があるため、次元別抽出領域情報は、如何なるサイズやアスペクト比の画像に対しても、同じ抽出領域を取得できる形式の情報である必要がある。例えば、次元別抽出領域情報は、ある規定のサイズとアスペクト比の画像(例えば、横幅320画素×縦幅240画素の画像)に対して、その抽出領域の位置・形状を記述したものであってもよい。この場合、ある任意のサイズとアスペクト比で入力された画像に対しては、まず画像をその規定のサイズとアスペクト比にリサイズしてから、次元別抽出領域情報に記述されている抽出領域の位置・形状に従って、抽出領域を特定すればよい。あるいは逆に、入力された画像の任意のサイズとアスペクト比の画像に合わせて、次元別抽出領域情報に記述されている抽出領域の位置・形状を変換して、抽出領域を特定してもよい。
【0029】
次元別抽出領域情報に含まれる各々の抽出領域を示す情報は、例えば、ある規定のサイズとアスペクト比の画像(例えば、横幅320画素×縦幅240画素の画像)に対して、抽出領域を構成する全ての画素の座標値の集合を記述した情報であってもよい。また次元別抽出領域情報に含まれる各々の抽出領域を示す情報は、例えば、ある規定のサイズとアスペクト比の画像に対して、抽出領域の位置・形状をパラメータ記述した情報であってもよい。例えば抽出領域の形が四角形である場合は、四角形の四隅の座標値を記述した情報であってもよい。また例えば抽出領域の形が円である場合は、円の中心の座標値と半径の値としてもよい。
【0030】
また、擬似乱数の種(シード)を次元別抽出領域情報として、抽出領域取得手段2の内部でその種からスタートして擬似乱数を発生させて、乱数に従って異なる形状の抽出領域を生成していく(例えば乱数に従って四角形の四隅を決定していくなど)、という方法も採用することができる。具体的には、例えば以下の手順で、次元別抽出領域を取得することができる。
(1)擬似乱数の種(シード)が次元別抽出領域情報として供給される。
(2)次元n=1とする。
(3)擬似乱数を発生させ、次元nの第1の抽出領域の四角形の四隅を決定する。
(4)擬似乱数を発生させ、次元nの第2の抽出領域の四角形の四隅を決定する。
(5)次元n=n+1として、(3)へ戻る。
【0031】
乱数に基づいて抽出領域を決定しているので、生成される抽出領域は次元毎に異なる形状になる。また、擬似乱数のシードが同じであれば、毎回(どの画像に対しても)同じ乱数列が発生されるため、異なる画像に対しても同じ抽出領域が再現される。
【0032】
抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元決定手段1から供給される次元に対応する第1の抽出領域と第2の抽出領域を示す情報を取得し、抽出領域代表値算出手段3へ供給する。
【0033】
領域特徴量算出手段3には、抽出領域取得手段2からの入力(第1の抽出領域と第2の抽出領域を示す情報)とは別に、入力として、画像識別子の抽出対象となる画像が供給される。領域特徴量算出手段3は、第1の領域特徴量算出手段31と第2の領域特徴量算出手段32とを有する。領域特徴量算出手段3は、第1の領域特徴量算出手段31を用いて、入力として供給される画像から、次元ごとに、抽出領域取得手段2から供給される第1の抽出領域を示す情報に基づき、第1の抽出領域の特徴量を第1の領域特徴量として算出し、比較手段4へ供給する。また、領域特徴量算出手段3は、第2の領域特徴量算出手段32を用いて、入力として供給される画像から、次元ごとに、抽出領域取得手段2から供給される第2の抽出領域を示す情報に基づき、第2の抽出領域の特徴量を第2の領域特徴量として算出し、比較手段4へ供給する。
【0034】
なお、第1の抽出領域と第2の抽出領域を示す情報に基づいて、入力される画像に対するそれぞれの抽出領域を特定するためには、必要に応じて領域特徴量算出手段3は、次元別抽出領域情報の規定のサイズとアスペクト比に画像をリサイズする。
【0035】
領域特徴量算出手段3は、それぞれの抽出領域に含まれる画素群の画素値を用いて、それぞれの抽出領域の領域特徴量を算出する。ここで画素値とは、画像の各画素が持つ信号の値であり、スカラー量またはベクトル量である。例えば、画像が輝度画像の場合は、画素値は輝度値(スカラー量)である。また例えば、画像がカラー画像の場合は、画素値は色成分を表すベクトル量である。例えばカラー画像がRGB画像である場合は、画素値はR成分、G成分、B成分の3次元のベクトル量である。また例えばカラー画像がYCbCr画像である場合は、画素値はY成分、Cb成分、Cr成分の3次元のベクトル量である。
【0036】
抽出領域の領域特徴量を算出する方法は、その次元の抽出領域(第1の抽出領域と第2の抽出領域)における算出方法が一定である(どの入力画像に対しても同じ算出方法である)限りは、任意の方法でよい。
【0037】
また、算出する領域特徴量は、スカラー量でもよいし、ベクトル量であってもよい。例えば、画素値が輝度値などのスカラー量である場合、領域特徴量を、その抽出領域に含まれる画素値の、平均値、メディアン値、最頻値、最大値、最小値、などと算出してもよい(いずれもスカラー量である)。また例えば、抽出領域に含まれる画素値をソートし、分布(ソートされた順列)の上位または下位から規定の割合の位置にある画素値を、領域特徴量として算出してもよい(これもスカラー量である)。より具体的に、規定の割合として、百分率でP%とした場合(例えばP=25%)を例に挙げて説明する。抽出領域に含まれる計N個の画素の画素値(輝度値)を昇順にソートし、昇順にソートされた画素値(輝度値)の集合をY(i)={Y(0)、Y(1)、Y(2)、…、Y(N−1)}と表す。ここで、昇順にソートされた順列の下位からP%の位置にある画素値は、例えば、Y(floor(N×P/100))となり、この値を抽出領域の領域特徴量として算出する。なお、floor()は、小数点以下の切り捨てを行う関数である。ここで、抽出領域に含まれる画素の輝度値に対して、この式(Y(floor(N×P/100)))を適用して算出された領域特徴量を、「パーセンタイル輝度値特徴量」と呼ぶことにする。
【0038】
また例えば、画素値が色成分などのベクトル量の場合は、まずそれらを任意の方法でスカラー量に変換してから、上述した方法によって領域特徴量を算出してもよい。例えば、画素値がRGB成分の3次元のベクトル量である場合は、まずそれらをスカラー量である輝度値に変換してから、上述した方法によって領域特徴量を算出してもよい。また画素値がベクトル量の場合は、例えば、その抽出領域に含まれる画素値の平均ベクトルを領域特徴量としてもよい。
【0039】
また例えば、抽出領域に対してエッジ検出や、テンプレートマッチングなどの任意の演算(微分演算、フィルタ演算)を行い、その演算結果を領域特徴量としてもよい。例えば、エッジの方向(勾配の方向)を表す2次元のベクトル量であってもよい。また例えば、あるテンプレートとの類似度などを表すスカラー量であってもよい。
【0040】
また例えば、抽出領域に含まれる色分布や、エッジの方向分布、エッジの強度分布を表すヒストグラムを、領域特徴量として算出してもよい(いずれもベクトル量である)。
【0041】
また例えば、国際標準規格ISO/IEC 15938−3に規定されている各種特徴量、すなわち、Dominant Color、Color Layout、Scalable Color、Color Structure、Edge Histogram、Homogeneous Texture、Texture Browsing、Region Shape、Contour Shape、Shape 3D、Parametric Motion、Motion Activityなどであってもよい。
【0042】
比較手段4は、次元ごとに、領域特徴量算出手段3から供給される第1の領域特徴量と、第2の領域特徴量とを比較し、比較した結果を量子化して得られた量子化インデックスを出力する。比較手段4が、次元ごとに、量子化インデックスを出力することで、最終的に、複数の次元の量子化インデックスから成る量子化インデックスベクトルが出力されることになる。
【0043】
比較手段4が、第1の領域特徴量と、第2の領域特徴量とを比較して、量子化する方法は、任意である。また、1つの次元当たりの量子化インデックスの数も任意である。
【0044】
比較手段4は、例えば、領域特徴量がスカラー量である場合(例えば輝度値の平均値)、その大小を比較して第1の領域特徴量のほうが大きい場合は量子化インデックスを+1、それ以外の場合は量子化インデックスを−1とする、のようにして+1と−1の2値の量子化インデックスに量子化してもよい。ここで、次元nの第1の領域特徴量をVn1、第2の領域特徴量をVn2とすると、次元nの量子化インデックスQnは、次式で算出することができる。
【0045】
[式1]
Qn=+1 (Vn1>Vn2 の場合)
−1 (Vn1≦Vn2 の場合)
【0046】
ここで、比較手段4が、上述の式1に基づいた比較・量子化を行う場合における、比較手段4のより詳細な構成図を図3に示す。
【0047】
図3を参照すると、比較手段4は、大小比較手段41と、量子化手段42と、から構成されている。
【0048】
大小比較手段41は、第1の領域特徴量と、第2の領域特徴量とが供給されると、第1の領域特徴量の値と第2の領域特徴量の値との大小を比較し、その比較結果を量子化手段42へ供給する。すなわち、大小比較手段41は、Vn1とVn2の大小を比較し、比較結果が、Vn1>Vn2であるか、Vn1≦Vn2であるか、のいずれであるかを示す情報を、大小比較結果として量子化手段42へ供給する。
【0049】
量子化手段42は、大小比較手段41から供給される大小比較結果に基づいて、式1に従って量子化を行い、量子化インデックスを出力する。すなわち量子化手段42は、比較結果がVn1>Vn2であることを示す情報が供給される場合は、量子化インデックスを+1、比較結果がVn1≦Vn2であることを示す情報が供給される場合は、量子化インデックスを−1、として量子化インデックスを出力する。
【0050】
なお、この式1に基づいた比較・量子化方法を比較・量子化方法Aと呼ぶことにする。
【0051】
また、比較手段4は、例えば、領域特徴量がスカラー量である場合(例えば輝度値の平均値)、差分値の絶対値がある規定の閾値以下の場合は、第1の領域特徴量と第2の領域特徴量との差がないものをみなし、差がないことを示す量子化インデックス0とし、それ以外の場合は、その大小を比較して第1の領域特徴量のほうが大きい場合は量子化インデックスを+1、それ以外の場合は量子化インデックスを−1とする、のようにして+1、0、−1の3値の量子化インデックスに量子化してもよい。ここで、次元nの第1の領域特徴量をVn1、第2の領域特徴量をVn2とし、規定の閾値をthとすると、次元nの量子化インデックスQnは、次式で算出することができる。
【0052】
[式2]
Qn=+1 (|Vn1−Vn2|>th かつ Vn1>Vn2 の場合)
0 (|Vn1−Vn2|≦th の場合)
−1 (|Vn1−Vn2|>th かつ Vn1≦Vn2 の場合)
【0053】
ここで、比較手段4が、上述の式2に基づいた比較・量子化を行う場合における、比較手段4のより詳細な構成図を図4に示す。
【0054】
図4を参照すると、比較手段4は、差分値算出手段43と、量子化手段44と、から構成されている。量子化手段44には、あらかじめ規定された、量子化の境界を表す情報(量子化境界情報)である閾値が、入力として供給される。
【0055】
差分値算出手段43は、第1の領域特徴量と、第2の領域特徴量とが供給されると、第1の領域特徴量の値と第2の領域特徴量の値との差分値を算出し、算出した差分値を量子化手段44へ供給する。すなわち、差分値算出手段43は、Vn1−Vn2を算出し、その値を量子化手段44へ供給する。
【0056】
量子化手段44は、差分値算出手段43から供給される差分値と、入力として供給されるあらかじめ規定された量子化の境界を表す情報(量子化境界情報)である閾値とに基づいて、式2に従って量子化を行い、量子化インデックスを出力する。すなわち量子化手段42は、差分値算出手段41から供給されるVn1−Vn2の値と、入力として供給される閾値thとに基づいて、|Vn1−Vn2|>th かつ Vn1−Vn2>0 の場合は量子化インデックスを+1、|Vn1−Vn2|>th かつ Vn1−Vn2≦0 の場合は量子化インデックスを−1、|Vn1−Vn2|≦th の場合は量子化インデックスを0、として量子化インデックスを出力する。
【0057】
なお、この式2に基づいた比較・量子化方法を比較・量子化方法Bと呼ぶことにする。
【0058】
また、ここでは差分値に基づいて3値に量子化しているが、差分値の大きさに応じて、より多数(のレベルの)の量子化インデックスに量子化してもよい。この場合も、比較手段4は、図4に示した構成をとり、量子化手段44には、あらかじめ規定された、各レベルの量子化の境界を表す情報(量子化境界情報)として複数の閾値が、入力として供給される。なお、この差分値と、入力として供給される複数の閾値とに基づいて、4レベル以上の複数のレベルの量子化インデックスに量子化する比較・量子化方法を比較・量子化方法Cと呼ぶことにする。
【0059】
このように、第1の領域特徴量と第2の領域特徴量との差が小さい(規定の閾値以下の)ときに、差がないものとして、差がないことを表す量子化インデックスを導入することで、式1の方法に比べて、領域特徴量の差が小さい抽出領域の対の次元の特徴量(量子化インデックス)をより安定に、すなわち各種改変処理やノイズに対してより頑健に、することができる。そのため、局所領域間の特徴の差が全体的に少ない、全体的に変化の少ない平坦な画像(例えば青空の画像)に対しても安定した、すなわち各種改変処理やノイズに対しても頑健な、画像識別子(量子化インデックスベクトル)を出力することができる。
【0060】
また、比較手段4は、例えば、領域特徴量がベクトル量である場合は、ベクトル量をまずそれらを任意の方法でスカラー量に変換してから、上述した方法によって量子化を行ってもよい(この比較・量子化方法を比較・量子化方法Dと呼ぶことにする)。また例えば、第1の抽出領域のベクトルから第2の抽出領域のベクトルとの差分である差分ベクトルを算出し、差分ベクトルをベクトル量子化して量子化インデックスを算出してもよい。この場合は、例えば、あらかじめ規定された量子化インデックスごとの代表ベクトル(重心ベクトルなど)が供給され、それら代表ベクトルと差分ベクトルとの類似度が最も大きく(距離が最も小さく)なる量子化インデックスに分類してもよい(この比較・量子化方法を比較・量子化方法Eと呼ぶことにする)。また、上述の式2によるスカラー量の量子化と同様に、差分ベクトルのノルムがある規定の閾値以下の場合は、第1の領域特徴量と第2の領域特徴量との差がないものをみなし、差がないことを示す量子化インデックス0として、差がないことを表す量子化インデックスを導入してもよい。
【0061】
なお、本発明で出力される量子化インデックスベクトルを照合する際(ある画像から抽出した量子化インデックスベクトルと、別の画像から抽出した量子化インデックスベクトルとを比較して、それらの画像が同一であるか否かを判定する際)は、量子化インデックスが一致する次元数(類似度)、あるいは量子化インデックスが非一致である次元数(ハミング距離)を同一性尺度として算出し、算出された同一性尺度をある閾値と比較して、画像の同一性の判定を行うことができる。また、比較手段4において、量子化インデックスが式2に基づいて算出された場合は、以下のように同一性尺度(類似度)を算出することができる。まず、2つの画像の量子化インデックスベクトルを対応する次元どうしで比較して、「共に量子化インデックスが0」ではない次元の数を算出する(この値をAとする)。次に、「共に量子化インデックスが0」ではない次元において、量子化インデックスが一致する次元の数を算出する(この値をBとする)。そして、類似度をB/Aとして算出する。ここでA=0の場合(すなわち、全ての次元が共に量子化インデックスが0となる場合)は、類似度を規定の数値(例えば0.5)とする。
【0062】
[第1の実施の形態の動作]
次に、図5のフローチャートを参照して、第1の実施の形態における画像識別子抽出装置の動作を説明する。図5のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0063】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2へ供給する(ステップA1)。
【0064】
次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、領域特徴量算出手段3へ供給する(ステップA2)。
【0065】
次に、領域特徴量算出手段3は、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、比較手段4へ供給する(ステップA3)。
【0066】
次に、比較手段4は、次元nの第1の領域特徴量と第2の領域特徴量とを比較し、比較した結果を量子化して、量子化インデックスを出力する(ステップA4)。
【0067】
次に、全ての次元に対して量子化インデックスの出力が終了したか否かを判定(すなわちn<Nが真であるか偽であるかを判定)する(ステップA5)。全ての次元に対して量子化インデックスの出力が終了した場合(すなわちn<Nが偽である場合)は処理を終了する。全ての次元に対して量子化インデックスの出力が終了していない場合(すなわちn<Nが真である場合)は、ステップA6へ移行する。ステップA6では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2へ供給する。そして、再度ステップA2へ移行する。
【0068】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。またこの処理手順に限らず、複数の次元に対する抽出処理を並列に行うようにしてもよい。
【0069】
[第1の実施の形態の効果]
次に、本発明の第1の実施の形態の効果について説明する。
【0070】
第1の効果は、複数の次元から成る特徴ベクトルで構成される画像識別子の、異なる画像を識別できる度合いである識別能力を高くすることができることである。特に、画像の局所領域間の相関が大きい画像に対して、この効果は顕著である。
【0071】
その理由は、次元間で特徴量を抽出する領域の形状が異なる(領域の形状に多様性がある)ことにより、次元間の相関を小さくできるからである。
【0072】
第2の効果は、特定の周波数に信号が集中している画像に対しても、識別能力が低下することがないことである。
【0073】
その理由は、次元間で特徴量を抽出する領域の形状が異なる(領域の形状に多様性がある)ことにより、ある特定の周波数に信号が集中している画像に対しても、同時に全ての(多くの)抽出領域の対(次元)の間で特徴量の差が無くなり識別能力が低下するようなことが発生しにくくなるからである。
【0074】
[第2の実施の形態]
[第2の実施の形態の構成]
次に、本発明の第2の実施の形態について図面を参照して詳細に説明する。
【0075】
本発明の第2の実施の形態は、図1に示した第1の実施の形態における比較手段4が、図6に詳細を示す比較手段4Aに置き換わる点において、異なる。比較手段4A以外に関しては、第1の実施の形態と同様であるため、ここでは説明を省略する。
【0076】
図6を参照すると、比較手段4Aは、差分値算出手段43と、量子化境界決定手段45と、量子化手段44と、から構成されている。
【0077】
差分値算出手段43は、次元ごとに、領域特徴量算出手段3から供給される第1の領域特徴量と、第2の領域特徴量との差分値を算出し、量子化境界決定手段45と、量子化手段44とへ供給する。
【0078】
差分値は、領域特徴量がスカラー量の場合(例えば輝度値の平均値)は、例えば、第1の領域特徴量から第2の領域特徴量を(あるいはその逆)減算して得られたスカラー量である。また、領域特徴量がベクトル量の場合は、例えば、それぞれのベクトルを任意の方法でスカラー量に変換してから、スカラー量の差分値を求めてもよい。また、領域特徴量がベクトル量の場合は、第1の領域特徴量と第2の領域特徴量との差分ベクトルを、差分値(ベクトル量)としてもよい。
【0079】
量子化境界決定手段45は、差分値算出手段43から供給される特徴ベクトルの全ての次元の差分値が供給されると、全ての次元の差分値の分布に基づいて、量子化の境界を決定し、決定した量子化境界の情報を量子化手段44へ供給する。ここで全ての次元の差分値の分布とは、差分値(あるいは差分ベクトル)に対する生起の頻度(確率)である。
【0080】
また量子化の境界を決定するとは、差分値を量子化する際に、漏れなく、かつ排他的に量子化インデックスに割り当てるためのパラメータを決定する、ということである。差分値がスカラー量である場合は、例えば、各量子化インデックス(量子化レベル)に対する値域(すなわち閾値)を決定し、その値域(閾値)を量子化境界の情報として量子化手段43へ供給する。また差分値がベクトル量である場合は、例えばベクトル量子化を行うためのパラメータ、例えば、各量子化インデックスの代表ベクトル(重心ベクトルなど)を決定し、それを量子化境界の情報として量子化手段44へ供給する。
【0081】
量子化境界決定手段45は、差分値がスカラー量の場合であって、M値の量子化を行う場合(M=2、3、…など)に、全ての次元の差分値の分布に基づいて、それぞれの量子化インデックスの全次元に対する割合が均等になるように、量子化の値域(閾値)を決定してもよい。
【0082】
例えば、前記式1の変形として、定数αを用いて、Vn1+α>Vn2の場合は量子化インデックス+1、Vn1+α≦Vnの場合は量子化インデックス−1とする2値の量子化(M=2)の場合に、量子化インデックスの+1と−1の割合が均等になるように、差分値の分布の中央の点(左右の分布の積分値が等しくなる点)を量子化の閾値αとして決定してもよい。また差分値がベクトル量である場合も同様に、M値の量子化を行う場合に、全ての次元の差分ベクトルの分布に基づいて、それぞれの量子化インデックスの全次元に対する割合が均等になるように、各量子化インデックスに割り当てられるベクトル空間の領域を決定したり、ベクトル量子化を行う際の各量子化インデックスの代表ベクトル(重心ベクトルなど)を決定してもよい。このように、どの画像に対しても、全次元に対する量子化インデックスの割合を均等にすることで(すなわち、量子化インデックスの偏りを無くす)、エントロピーを高くすることができるため、識別能力を高くすることができる。
【0083】
なお、量子化境界決定手段45が、量子化インデックスの全次元に対する割合が均等になるように量子化の境界を決定し、それに基づいて量子化手段44が量子化を行う比較・量子化方法を、比較・量子化方法Fと呼ぶことにする。
【0084】
また例えば、量子化境界決定手段45は、差分値がスカラー量の場合であって、上述の式2による3値の量子化を行う場合に(量子化インデックスが+1、0、−1)、差分がないことを示す量子化インデックス0に量子化する際の閾値th(この閾値以下の場合に量子化インデックスを0とする)を、全ての次元の差分値の分布に基づいて決定し、決定した閾値thを量子化手段44へ供給してもよい(第1の実施の形態の図4の比較手段4では、この閾値thはあらかじめ規定されているものである)。例えば、全ての次元の差分値の絶対値を算出し、算出した差分値の絶対値をソートして、その上位または下位から、ある規定の割合(なおこの規定の割合は、例えば、入力として供給されるとする)の点を閾値thとしてもよい(この比較・量子化方法を比較・量子化方法Gと呼ぶことにする)。またここで規定の割合ではなく、+1、0、−1の量子化インデックスの割合が均等に近づくように、閾値thを決定してもよい(この比較・量子化方法を比較・量子化方法Hと呼ぶことにする)。比較・量子化方法Hは、式2に従った場合の、比較・量子化方法Fの具体例に相当する。
【0085】
比較・量子化方法Gのより具体的な方法を、規定の割合として、百分率でP%とした場合(例えばP=25%)を例に挙げて説明する。全ての次元(次元数=Nとする)の差分値の絶対値を、昇順にソートし、昇順にソートされた差分値の絶対値の集合をD(i)={D(0)、D(1)、D(2)、…、D(N−1)}と表す。ここで、昇順にソートされた順列の下位からP%の位置にある値は、例えば、D(floor(N×P/100))となり、閾値th=D(floor(N×P/100))となる。なお、floor()は、小数点以下の切り捨てを行う関数である。
【0086】
本実施の形態における方法は、第1の実施の形態における、比較手段4が図4の構成をとる場合と対比することができる。第1の実施の形態における図4の構成では、あらかじめ規定された閾値thが入力として供給されるのに対して、第2の実施の形態における上述の方法は、量子化境界決定手段45において、全ての次元の差分値の分布に基づいて、画像に対して適応的に閾値thが算出される。このように第1の実施の形態では閾値thが固定化されており、第2の実施の形態では閾値thが画像に適応的に算出される。画像に適応的に閾値thが算出されることで、閾値thが固定化されている場合と比較して、特徴ベクトルの次元の値が、特定の量子化インデックスに偏る(特定の量子化インデックスの出現確率が高い)ことを抑えることができるため(特に起伏の少ない画像に対してなど)、識別能力を高くすることができる。例えば、第1の実施の形態における固定化された閾値thを用いた場合、起伏の少ない画像は、特徴ベクトルの大多数の次元(または全ての次元)が量子化インデックス0になってしまうのに対して、第2の実施の形態における適応的な閾値thを用いると、起伏の少ない画像に対しては閾値thが小さい値に自動的に調整されるため、特徴ベクトルの大多数の次元が量子化インデックス0になるような事態が発生しない。
【0087】
量子化手段44は、次元ごとに、差分値算出手段43から供給される次元ごとの差分値と、量子化境界決定手段45から供給される量子化境界の情報とに基づいて、量子化を行い、量子化インデックスを出力する。
【0088】
なお、量子化手段44は、量子化境界決定手段45が出力した量子化境界の情報を無視した量子化を行っては意味がなくなるため、量子化境界決定手段45で量子化境界を決定した際に想定していた量子化方法に従う必要がある。
【0089】
[第2の実施の形態の動作]
次に、図7のフローチャートを参照して、第2の実施の形態における画像識別子抽出装置の動作を説明する。図7のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0090】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2へ供給する(ステップB1)。
【0091】
次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、抽出領域代表値算出手段3へ供給する(ステップB2)。
【0092】
次に、抽出領域代表値算出手段3は、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、差分値算出手段43へ供給する(ステップB3)。
【0093】
次に、差分値算出手段43は、次元nの第1の領域特徴量と第2の領域特徴量との差分値を算出し、量子化境界決定手段45と、量子化手段44とへ供給する(ステップB4)。
【0094】
次に、全ての次元に対する差分値の算出までの処理が終了したか否かを判定(すなわちn<Nが真であるか偽であるかを判定)する(ステップB5)。全ての次元に対する差分値算出までの処理を終了した場合(すなわちn<Nが偽である場合)はステップB7へ移行する。全ての次元に対する処理が終了していない場合(すなわちn<Nが真である場合)は、ステップB6へ移行する。ステップB6では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2へ供給する。そして、再度ステップB2へ移行する。
【0095】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0096】
次に、量子化境界決定手段45は、差分値算出手段43から供給される特徴ベクトルの全ての次元の差分値が供給されると、全ての次元の差分値の分布に基づいて、量子化の境界を決定し、決定した量子化境界の情報を量子化手段44へ供給する(ステップB7)。
【0097】
次にステップB8では、量子化を行う(量子化インデックスを算出する)特徴ベクトルの最初の次元として、次元1をセット(n=1)する。
【0098】
次に、量子化手段44は、次元nの差分値と、量子化境界決定手段45から供給される量子化境界とに基づいて、量子化を行い、量子化インデックスを出力する(ステップB9)。
【0099】
次に、全ての次元に対する量子化インデックスの出力が終了したか否かを判定(すなわちn<Nが真であるか偽であるかを判定)する(ステップB10)。全ての次元に対する量子化インデックスの出力を終了した場合(すなわちn<Nが偽である場合)は処理を終了する。全ての次元に対する量子化インデックスの出力が終了していない場合(すなわちn<Nが真である場合)は、ステップB11へ移行する。ステップB11では、量子化を行う(量子化インデックスを算出する)特徴ベクトルの次元として、次の次元をセットする(n=n+1)。そして、再度ステップB9へ移行する。
【0100】
なお、ここでは、次元1から次元Nまで順番に量子化処理を行っているが、順番はこれに限らず任意でよい。
【0101】
[第2の実施の形態の効果]
第2の実施の形態では、量子化の境界が固定されている第1の実施の形態と比較して、量子化の境界が画像に対して適応的に(動的に)算出される点が異なる。第1の実施の形態のように、量子化の境界が固定化されていると、特定の画像(例えば起伏の少ない平坦な画像など)に対して、特徴ベクトルの次元の値が、特定の量子化インデックスに偏る(特定の量子化インデックスの出現確率が高い)という事態が発生し(エントロピーが低くなる)、これらの画像に対して識別能力が低下するという問題が発生する。一方で第2の実施の形態のように、量子化の境界が画像に対して適応的に(動的に)算出されることにより、どの画像に対しても、特徴ベクトルの次元の値が、特定の量子化インデックスに偏る(特定の量子化インデックスの出現確率が高い)ことを抑えることができるため、識別能力を高くすることができる。
【0102】
[第3の実施の形態]
[第3の実施の形態の構成]
次に、本発明の第3の実施の形態について図面を参照して詳細に説明する。
【0103】
図8を参照すると、本発明の第3の実施の形態は、図1に示した第1の実施の形態の構成に、領域特徴量算出方法取得手段5が追加され、領域特徴量算出手段3が、第1および第2の領域特徴量算出手段31Aおよび32Aを有する領域特徴量算出手段3Aに置き換わる点で異なる。なお、それ以外の構成に関しては、第1の実施の形態の構成と同様であるため、ここでは説明を省略する。なお、ここでは、第1の実施の形態との組み合わせとして説明しているが、第2の実施の形態との組み合わせであってもよい。
【0104】
領域特徴量算出方法取得手段5には、次元決定手段1からの次元と、次元別領域特徴量算出方法情報とが供給される。
【0105】
次元別領域特徴量算出方法情報は、あらかじめ規定された、特徴ベクトルの次元ごとに対応付けられた、その次元での領域特徴量の算出方法を示す情報であり、次元間で領域特徴量算出方法が異なることが必須条件である。なおここで、領域特徴量算出方法が異なるとは、同一の手順に対して異なるパラメータ(閾値など)を適用する場合も含む。
【0106】
ここで領域特徴量算出方法とは、例えば、第1の実施の形態の領域特徴量算出手段3の説明で記述した各種方法、またそれに伴うパラメータなどである。
【0107】
なお次元別領域特徴量算出方法情報が示す次元ごとの領域特徴量算出方法は、特徴ベクトルの全次元の中に、領域特徴量算出方法の異なる次元のペアが、少なくとも1つ存在することが最低条件である。領域特徴量算出方法が相互に異なる次元が多いほど、望ましい。これは、領域特徴量算出方法が相互に異なる次元が多いほど、特徴ベクトルのより多くの次元間で相関が小さくなり、識別能力が高くなるからである。例えば、特徴ベクトルの全ての次元間で、領域特徴量算出方法が相互に異なっていてもよい。
【0108】
なお、次元ごとの領域特徴量算出方法を示す情報の形式は、領域特徴量を算出する方法が一意に特定される限りは、任意の形式であってよい。
【0109】
図9に、次元ごとの領域特徴量算出方法の例を示す。図9に示すように、次元間で領域特徴量算出方法が異なる。また図9に示した例のように、スカラー量とベクトル量の特徴量が混在していてもよい(第1、3、5、6、8、9、10、12次元はスカラー量、第2、4、7、11次元はベクトル量)。
【0110】
領域特徴量算出方法取得手段5は、入力として供給される次元別領域特徴量算出方法情報から、次元決定手段1から供給される次元に対応する領域特徴量算出方法を示す情報を取得し、領域特徴量算出手段3Aへ供給する。
【0111】
領域特徴量算出手段3Aは、入力として供給される画像から、次元ごとに、抽出領域取得手段2から供給される第1の抽出領域と第2の抽出領域とを示す情報に基づき、領域特徴量算出方法取得手段5から供給される領域特徴量算出方法を示す情報に従って、第1の抽出領域の特徴量と、第2の抽出領域の特徴量とを、それぞれ第1の領域特徴量と第2の領域特徴量として算出し、比較手段4へ供給する。
【0112】
領域特徴量算出手段3Aでは、供給される抽出領域を示す情報の次元と、領域特徴量算出方法を示す情報の次元との同期が取れている必要がある。
【0113】
[第3の実施の形態の動作]
次に、図10のフローチャートを参照して、第3の実施の形態における画像識別子抽出装置の動作を説明する。図10のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0114】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2と領域特徴量算出方法取得手段5とへ供給する(ステップC1)。次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、領域特徴量算出手段3Aへ供給する(ステップC2)。
【0115】
次に、領域特徴量算出方法取得手段5は、入力として供給される次元別領域特徴量算出方法情報から、次元nに対応する領域特徴量算出方法を示す情報を取得し、領域特徴量算出手段3Aへ供給する(ステップC3)。
【0116】
次に、領域特徴量算出手段3Aは、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、比較手段4へ供給する(ステップC4)。次に、比較手段4は、次元nの第1の領域特徴量と第2の領域特徴量とを比較し、比較した結果を量子化して、量子化インデックスを出力する(ステップC5)。次に、全ての次元に対して量子化インデックスの出力が終了したか否かを判定する(ステップC6)。全ての次元に対して量子化インデックスの出力が終了した場合は処理を終了する。全ての次元に対して量子化インデックスの出力が終了していない場合は、ステップC7へ移行する。ステップC7では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2と領域特徴量算出方法取得手段5とへ供給する。そして、再度ステップC2へ移行する。
【0117】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。またこの処理手順に限らず、複数の次元に対する抽出処理を並列に行うようにしてもよい。さらに、ステップC2とステップC3の順序を逆にしてもよい。
【0118】
[第3の実施の形態の効果]
第1の実施の形態の効果に加えて、異なる画像を識別できる度合いである識別能力を更に高くすることができる。
【0119】
その理由は、次元間で領域特徴量算出方法が異なる(領域特徴量算出方法に多様性がある)ことにより、次元間の相関をより小さくできるからである。
【0120】
[第4の実施の形態]
[第4の実施の形態の構成]
次に、本発明の第4の実施の形態について図面を参照して詳細に説明する。
【0121】
図11を参照すると、本発明の第4の実施の形態は、図1に示した第1の実施の形態の構成に、比較方法取得手段6が追加され、比較手段4が比較手段4Bに置き換わる点で異なる。なお、それ以外の構成に関しては、第1の実施の形態の構成と同様であるため、ここでは説明を省略する。なお、ここでは、第1の実施の形態との組み合わせとして説明しているが、第2の実施の形態および第3の実施の形態との組み合わせであってもよい。
【0122】
比較方法取得手段6には、次元決定手段1からの次元と、次元別比較方法情報とが供給される。
【0123】
次元別比較・量子化方法情報は、あらかじめ規定された、特徴ベクトルの次元ごとに対応付けられた、その次元での領域特徴量を比較して量子化を行う方法を示す情報であり、次元間で比較・量子化方法が異なることが必須条件である。なおここで、比較・量子化方法が異なるとは、同一の手順に対して異なるパラメータ(閾値、量子化インデックス数など)を適用する場合も含む。
【0124】
ここで比較・量子化方法とは、例えば第1の実施の形態の比較手段4の説明で記述した各種比較・量子化の方法、またそれに伴うパラメータ(閾値、量子化インデックス数など)や、第2の実施の形態の比較手段4Aの説明で記述した各種比較・量子化の方法、またそれに伴うパラメータ(閾値、量子化インデックス数など)などである。
【0125】
なお次元別比較・量子化方法情報が示す次元ごとの比較・量子化方法は、特徴ベクトルの全次元の中に、比較・量子化方法の異なる次元のペアが、少なくとも1つ存在することが最低条件である。比較・量子化方法が相互に異なる次元が多いほど、望ましい。これは、比較・量子化方法が相互に異なる次元が多いほど、特徴ベクトルのより多くの次元間で相関が小さくなり、識別能力が高くなるからである。例えば、特徴ベクトルの全ての次元間で、比較・量子化方法が相互に異なっていてもよい。
【0126】
なお、次元ごとの比較・量子化方法を示す情報の形式は、領域特徴量を比較して量子化する方法が一意に特定される限りは、任意の形式であってよい。
【0127】
図12に、次元ごとの比較・量子化方法の例を示す。図12に示すように、次元間で比較・量子化方法が異なる。また、第3、5、12次元のように、同じ比較・量子化方法で、異なるパラメータ(閾値th)を設定してもよい。なお、図12に示した、次元ごとの比較・量子化方法の例は、図9に示した、次元ごとの領域特徴量算出方法の例と対応させており、スカラー量の領域特徴量に対してはスカラー量の比較・量子化方法を、ベクトル量の領域特徴量に対してはベクトル量の比較・量子化方法を例として示した。
【0128】
比較方法取得手段6は、入力として供給される次元別比較・量子化方法情報から、次元決定手段1から供給される次元に対応する比較・量子化方法を示す情報を取得し、比較手段4Bへ供給する。
【0129】
比較手段4Bは、次元ごとに、領域特徴量算出手段3から供給される第1の領域特徴量と、第2の領域特徴量とを、比較方法取得手段6から供給される比較・量子化方法を示す情報に従って、比較・量子化して、量子化インデックスを出力する。比較手段4Bは、比較・量子化方法によって、必要に応じて、第1の実施の形態の比較手段4と、第2の実施の形態の比較手段4Bの両方を内包した構成となる場合もある。
【0130】
比較手段4Bでは、供給される領域特徴量の次元と、比較・量子化方法を示す情報の次元の同期が取れている必要がある。
【0131】
[第4の実施の形態の動作]
次に、図13のフローチャートを参照して、第4の実施の形態における画像識別子抽出装置の動作を説明する。図13のフローチャートでは、特徴ベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。
【0132】
まず、次元決定手段1は、抽出する特徴ベクトルの最初の次元として、次元1を決定し(n=1)、抽出領域取得手段2と比較方法取得手段6とへ供給する(ステップD1)。次に、抽出領域取得手段2は、入力として供給される次元別抽出領域情報から、次元nの第1の抽出領域と第2の抽出領域とを示す情報を取得し、領域特徴量算出手段3へ供給する(ステップD2)。
【0133】
次に、比較方法取得手段6は、入力として供給される次元別比較・量子化方法情報から、次元nに対応する比較・量子化方法を示す情報を取得し、比較手段4Bへ供給する(ステップD3)。
【0134】
次に、領域特徴量算出手段3は、入力として供給される画像から、次元nの第1の領域特徴量と、第2の領域特徴量とを算出し、比較手段4Bへ供給する(ステップD4)。次に、比較手段4Bは、次元nの第1の領域特徴量と第2の領域特徴量とを比較し、比較した結果を量子化して、量子化インデックスを出力する(ステップD5)。次に、全ての次元に対して量子化インデックスの出力が終了したか否かを判定する(ステップD6)。全ての次元に対して量子化インデックスの出力が終了した場合は処理を終了する。全ての次元に対して量子化インデックスの出力が終了していない場合は、ステップD7へ移行する。ステップD7では、次元決定手段1が、抽出する特徴ベクトルの次元として、次の次元を決定し(n=n+1)、抽出領域取得手段2と比較方法取得手段6とへ供給する。そして、再度ステップD2へ移行する。
【0135】
なお、ここでは、次元1から次元Nまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。またこの処理手順に限らず、複数の次元に対する抽出処理を並列に行うようにしてもよい。さらに、ステップD2とステップD3との順序を逆にしてもよく、ステップD3をステップD5の直前に実行するようにしてもよい。
【0136】
[第4の実施の形態の効果]
第1の実施の形態の効果に加えて、異なる画像を識別できる度合いである識別能力を更に高くすることができる。
【0137】
その理由は、次元間で比較・量子化方法が異なる(比較・量子化方法に多様性がある)ことにより、次元間の相関をより小さくできるからである。
【0138】
[第5の実施の形態]
[第5の実施の形態の構成]
次に、本発明の第5の実施の形態について図面を参照して詳細に説明する。
【0139】
図20を参照すると、本発明の第5の実施の形態は、図1に示した第1の実施の形態の構成に、符号化手段7が追加される点で異なる。なお、それ以外の構成に関しては、第1の実施の形態の構成と同様であるため、ここでは説明を省略する。なお、ここでは、第1の実施の形態との組み合わせとして説明しているが、第2の実施の形態、または第3の実施の形態、または第4の実施の形態との組み合わせであってもよい。
【0140】
符号化手段7は、比較手段4から供給される量子化インデックスベクトルを、データ量が小さくなるように一意に復号可能な形式に符号化し、符号化された量子化インデックスベクトルを出力する。
【0141】
符号化手段7は、例えば、量子化インデックスベクトルの各次元を独立に符号化するのではなく、複数の次元をまとめて符号化することによって、データ量を小さく符号化してもよい。
【0142】
ここで、量子化インデックスが式2に基づいて算出された場合において、符号化手段7が効率的に符号化する方法について述べる。式2に基づいて量子化インデックスを算出すると、各次元の量子化インデックスは、(+1、0、−1)の3値のいずれかの値をとる。各次元を独立に符号化する場合は、各次元に対して2ビット(=4状態)が必要となる。ここで、5次元をまとめて符号化することを考えると(この5次元はどのような組合せでもよい。例えば連続する5次元でもよい)、その状態数は3の5乗=243状態となり、1バイト=8ビット(=256状態)で表す(256状態以内に収めることができる)ことができる。こうすると、1次元あたりに必要な平均ビット数は8/5=1.6ビットとなり、各次元を独立に符号する場合よりも、データ量を小さくすることができる(1次元あたり0.4ビットの削減が可能)。例えば、量子化インデックスベクトルの全次元数が300次元の場合、各次元を独立に符号化した場合は2ビット×300=600ビット=75バイトとなる。一方で、5次元ごとにまとめて符号化すると、1.6ビット×300=480ビット=60バイトとなり、15バイト削減できる。
【0143】
式2で算出される(+1、0、−1)の3値の状態を5次元ごとに符号化する具体例を以下に示す。各5次元の組合せは、どのような組合せでも良いが、例えば、連続する5つの次元ごとに符号化する方法がある。すなわち、第1次元から第5次元をまとめて符号化し、第6次元から第10次元をまとめて符号化し、第11次元から第15次元をまとめて符号化していくことができる(もちろん、重複がない限りは、どのような5つの次元の組み合わせでもよい)。ここで、まとめて符号化する5次元の量子化インデックスの値をQn、Qn+1、Qn+2、Qn+3、Qn+4とすると(それぞれは+1、0、−1のいずれかの値をとる)、例えば、以下の式に従って符号化された値Zを算出することができる。
【0144】
[式3]
Z={34×(Qn+1)}+{33×(Qn+1+1)}+{32×(Qn+2+1)}+{31×(Qn+3+1)}+{30×(Qn+4+1)}
【0145】
この符号化された値Zは、0から242の値をとるため(243状態)、1バイト(8ビット)のデータとして符号化されることになる。なお、まとめて符号化する5次元の量子化インデックスの値をQn、Qn+1、Qn+2、Qn+3、Qn+4を、0から242の値(243状態)にマッピングする方法は、[式3]だけに限られず、5次元の量子化インデックスの異なる組み合わせに対して、異なる値(243状態の値)にマッピングされる方法であれば、どのような方法であってもよい。[式3]のように与えられた式に基づいて、マッピング(符号化後の値)を算出し、符号化してもよいし、またあらかじめマッピングの対応表を生成・記憶しておき、記憶された対応表を参照しながらマッピング(符号化後の値)を取得し、符号化してもよい。
【0146】
段落0142から段落0145において説明した、量子化インデックスが式2に基づいて算出された場合において効率的に符号化する方法は、量子化インデックスが式2に基づいて算出された場合に限らず、量子化インデックスが3値の状態の量子化インデックスベクトルであれば、同様に適用可能である。すなわち、量子化インデックスベクトルが、3値の状態の量子化インデックスから成る場合は、5次元をまとめて1バイト=8ビットとして符号化することができる。3値の状態を持つ5次元の量子化インデックスは、5次元の量子化インデックスの異なる組み合わせが243種類可能であるため、それぞれの組み合わせを0から242の値(243状態)にマッピングすることによって、1バイト=8ビットで符号化することができる。なおこのマッピングは、[式3]のように与えられた式に基づいて、マッピング(符号化後の値)を算出し、符号化してもよいし、またあらかじめマッピングの対応表を生成・記憶しておき、記憶された対応表を参照しながらマッピング(符号化後の値)を取得し、符号化してもよい。
【0147】
このように、量子化インデックスベクトルの各次元を独立に符号化するのではなく、複数の次元をまとめて符号化することによって、量子化インデックスベクトルの各次元を独立に符号化する場合と比較して、データ量を小さく符号化できる、という効果がある。
【0148】
これは、量子化インデックスが3値の状態で表現される場合に限られない。例えば、量子化インデックスが5値の状態で表現される場合は、3次元をまとめて符号化することにより5の3乗=125状態となり、7ビット=128状態で符号化する(128状態以内に収めることができる)ことができる。3次元を独立に符号化すると3ビット(8状態)×3次元=9ビット必要となるため、3次元をまとめて符号化することにより2ビット削除することができる。
【0149】
なお、符号化手段7から出力される符号化された量子化インデックスベクトルを照合する際(ある画像から抽出した量子化インデックスベクトルと、別の画像から抽出した量子化インデックスベクトルとを比較して、それらの画像が同一であるか否かを判定する際)は、符号化された状態から、各次元ごとの量子化インデックスの値を復号し(例えば上記の例では、各次元ごとに+1、0、−1の量子化インデックス値に復号し)、復号された量子化インデックスをもとに同一性尺度(量子化インデックスが一致する次元数(類似度)、あるいは量子化インデックスが非一致である次元数(ハミング距離))を算出してもよい。
【0150】
また、ルックアップテーブルを用いることで、符号化された状態のままで、各次元ごとの量子化インデックスの値に復号することなしに、照合を行うこともできる。すなわち、符号化された単位ごとに、あらかじめ同一性尺度(類似度や距離)をテーブル(ルックアップテーブル)の形で保存しておき、ルックアップテーブルを参照することにより、符号化された単位ごとの同一性尺度(類似度や距離)を取得し、それらを総計することで(例えば総和を算出する)、全次元の同一性尺度を算出することができる。
【0151】
例えば上記の、5次元ごとにまとめて1バイト(8ビット)に符号化された場合には、それぞれの5次元単位が243状態のいずれかであるため、243×243のサイズのルックアップテーブルをあらかじめ生成しておくことで、対処することができる。すなわち、比較する2つの5次元単位の符号の、可能な全ての組合せの状態(243状態×243状態)の間の同一性尺度、すなわち5次元のうち量子化インデックスが一致する数(類似度)、あるいは5次元のうち量子化インデックスが非一致である数(ハミング距離)をあらかじめ算出しておく。そしてそれを243×243のサイズのルックアップテーブルとして記憶しておく。そうすると、5次元単位ごとに、ルックアップテーブルを参照して(各次元ごとの量子化インデックスに復号することなしに)、5次元単位ごとの同一性尺度を取得することができる。例えば、量子化インデックスベクトルの全次元数が300次元の場合、5次元ごとに1バイトで、合計60バイトで符号化されているため、ルックアップテーブルを60回参照して、それぞれの5次元単位の同一性尺度を取得し、それらを総和することで全体(300次元)の同一性尺度(類似度あるいはハミング距離)を算出することができる。ルックアップテーブルを用いることで、各次元ごとの量子化インデックスへの復号を行うことなしに照合(同一性尺度の算出)が可能になるので、照合(同一性尺度の算出)の際の処理コストを低減することができ、高速な照合(同一性尺度の算出)が可能になる、という効果がある。
【0152】
また、2つの量子化インデックスベクトルの間の同一性尺度を、単純に量子化インデックスが一致する次元数(類似度)や、量子化インデックスが非一致である次元数(ハミング距離)として算出するのではなく、より複雑な計算式に基づいて算出する場合においても、ルックアップテーブルを用いることで、各次元ごとの量子化インデックスへの復号を行うことなしに照合(同一性尺度の算出)することができる。例えば、量子化インデックスが式2に基づいて算出された量子化インデックスベクトルの同一性尺度として、以下のような同一性尺度の算出方法を考える。まず、2つの画像の量子化インデックスベクトルを対応する次元どうしで比較して、「共に量子化インデックスが0」ではない次元の数を算出し、この値をAとする。次に、「共に量子化インデックスが0」ではない次元において、量子化インデックスが一致する次元数をBとして算出する(または、「共に量子化インデックスが0」ではない次元において、量子化インデックスが非一致である次元数をCとして算出する)。そして、同一性尺度をB/Aとして算出する(または、同一性尺度をC/Aとして算出する)。ただし、A=0の場合(すなわち、全ての次が共に量子化インデックスが0となる場合)は、同一性尺度を規定の数値(例えば0.5)とする。このような同一性尺度の算出方法を採用した場合、Aの値とBの値(またはCの値)の2つの値を算出する必要がある。この場合、5次元ごとのAの値を参照するための243×243のサイズのルックアップテーブルと、5次元ごとのBの値(またはCの値)を参照するための243×243のサイズのルックアップテーブルの、2つのルックアップテーブルをあらかじめ生成しておくことで、対処することができる。すなわち、比較する2つの5次元単位の符号の、可能な全ての組み合わせの状態(243状態×243状態)の間のAの値(「共に量子化インデックスが0」ではない次元数)と、可能な全ての組み合わせの状態(243状態×243状態)の間のBの値(またはCの値)をあらかじめ算出しておく。そしてそれぞれを243×243のサイズのルックアップテーブルとして記憶しておく。そうすると、5次元単位ごとに、ルックアップテーブルを参照して(各次元ごとの量子化インデックスを復号することなしに)、5次元単位ごとのAの値と、Bの値(またはCの値)を取得することができる。例えば、量子化インデックスベクトルの全次元数が300次元の場合、5次元ごとに1バイトで、合計60バイトで符号化されているため、ルックアップテーブルを60回×2参照して、それぞれの5次元単位のAの値とBの値(またはCの値)を取得し、全て5次元単位のAの値とBの値(またはCの値)を総和することで、全次元(300次元)のAの値とBの値(またはCの値)を算出することができる。そして、最後にB/A(またはC/A)を算出することで、同一性尺度を算出できる。このように、同一性尺度を、単純に量子化インデックスが一致する次元数(類似度)や、量子化インデックスが非一致である次元数(ハミング距離)として算出するのではなく、より複雑な計算式に基づいて算出する場合においても、複数のルックアップテーブルを用いることで、各次元ごとの量子化インデックスへの復号を行うことなしに照合(同一性尺度の算出)が可能になるので、照合(同一性尺度の算出)の際の処理コストを低減することができ、高速な照合(同一性尺度の算出)が可能になる、という効果がある。
【0153】
[第5の実施の形態の効果]
より小さいデータ量として、量子化インデックスベクトルを出力することができる。
【0154】
次に、本発明における第6〜第8の実施の形態を説明する。
【0155】
[第6の実施の形態]
第6の実施の形態では、抽出する特徴ベクトルの次元数は300次元(第1次元から第300次元)である。
【0156】
第6の実施の形態では、次元ごとの抽出領域(第1の抽出領域と第2の抽出領域)は、様々な形状の四角形から構成される。第6の実施の形態において、抽出領域取得手段2に入力として供給される次元別抽出領域情報を図14に示す。図14は、規定の画像サイズである、横幅320画素×縦幅240画素の画像サイズに対する、次元ごとの抽出領域(第1の抽出領域と第2の抽出領域)の四角形の四隅のXY座標値を示す。例えば、第1次元の抽出領域は、座標値(262.000,163.000)、座標値(178.068,230.967)、座標値(184.594,67.411)、座標値(100.662,135.378)を四隅とする四角形で構成される第1の抽出領域と、座標値(161.000,133.000)、座標値(156.027,132.477)、座標値(164.240,102.170)、座標値(159.268,101.647)を四隅とする四角形で構成される第1の抽出領域とで構成される。
【0157】
次元ごとの抽出領域(第1の抽出領域と第2の抽出領域)は、横幅320画素×縦幅240画素の画像サイズに正規化された画像に対して、この四隅の座標値で囲まれる領域の中に含まれる整数値の座標値の画素の集合となる。ただし、四隅の座標値で囲まれる領域の中に含まれる負の座標値は、抽出領域に含まない。
【0158】
第6の実施の形態において、領域特徴量算出方法取得手段5に入力として供給される次元別領域特徴量算出方法情報を図15に示す。第6の実施の形態では、全ての次元に対して、それぞれの抽出領域(第1の抽出領域と第2の抽出領域)に含まれる画素群の輝度値の平均値が、それぞれの抽出領域の領域特徴量となる。
【0159】
第6の実施の形態において、比較方法取得手段6に入力として供給される次元別比較・量子化方法情報を図17に示す。第6の実施の形態では、次元ごとに、比較・量子化方法Bまたは比較・量子化方法Gが用いられ、次元ごとにそのパラメータの値も異なる。例えば、第1次元は、比較・量子化方法Gで、閾値th=D(floor(300×5.0/100))である。また、例えば第2次元は、比較・量子化方法Gで、閾値th=D(floor(300×10.0/100))である。また、例えば第9次元は、比較・量子化方法Bで、閾値th=3.0である。
【0160】
[第7の実施の形態]
第7の実施の形態は、第6の実施の形態と同じく、抽出する特徴ベクトルの次元数は300次元(第1次元から第300次元)である。また第7の実施の形態では、抽出領域取得手段2に入力として供給される次元別抽出領域情報として、第6の実施の形態と同じく図14に示す情報を使用する。さらに第7の実施の形態では、比較方法取得手段6に入力として供給される次元別比較・量子化方法情報として、第6の実施の形態と同じく図17に示す情報を使用する。
【0161】
第7の実施の形態において、領域特徴量算出方法取得手段5に入力として供給される次元別領域特徴量算出方法情報を図16に示す。第7の実施の形態では、次元ごとに、抽出領域(第1の抽出領域と第2の抽出領域)に含まれる画素群の輝度値の平均値、または、パーセンタイル輝度値特徴量が用いられ、同じパーセンタイル輝度値特徴量を用いる場合でも、次元ごとにその特徴量は異なる。例えば、第1次元は、抽出領域に含まれる画素の輝度値の平均値である。また、例えば第4次元は、パーセンタイル輝度値特徴量で、Y(floor(N×20.0/100)である。また、第8次元は、パーセンタイル輝度値特徴量で、Y(floor(N×80.0/100)である。
【0162】
[第8の実施の形態]
第8の実施の形態は、抽出する特徴ベクトルの次元数は325次元(第1次元から第325次元)である。第8の実施の形態の場合は、各領域は、画像を縦方向32、横方向32に分割してできる1024個のブロックの組み合わせによって構成されている。ここで、各ブロックに対して、図28に示すように、左上から順に0から始まるインデックスを付与し、このインデックスを用いて領域を記述する。具体的には、長方形領域を、その左上のブロックのインデックスaと右下のブロックのインデックスbを用いてa−bのように表現する。例えば、インデックス0、1、32、33の4つのブロックからなる長方形は、0−33のように記述する。また、このようにしてできる長方形を記号“|”によって繋げた場合は、その記号の前後の長方形を連結してできる領域を表現するものとする。例えば、0−33|2−67は、0−33で定義される長方形と、2−67で定義される長方形を連結してできる領域、すなわち、ブロック番号0、1、2、3、32、33、34、35、66、67によって構成される領域を表している。
【0163】
この表記によって第8の実施の形態の各次元に対応する領域を示したものが図26である。図では、領域のタイプ別に図29−a、図29−b、図29−c、図29−d、図29−e、図29−f、図29−gに分けて上述の325次元を記述している。ここで、領域のタイプとは、第1、第2の抽出領域間の相対位置や形状の組み合わせによって定まる領域パターンが似たもの同士でグループ化(類型化)したものである。
【0164】
具体的には、図29−aの場合は、図31−aに一例を示すように、縦横4ブロックからなる正方形を縦方向か横方向に2等分してできる2つの領域を第1、第2の抽出領域とした場合に相当する。このため、第1、第2の抽出領域の形状は、ともに縦4ブロック、横2ブロックからなる長方形、あるいは縦2ブロック、横4ブロックからなる長方形である。また、第1、第2の抽出領域の相対的な位置関係を見ると、長方形の長い辺同士が重なるように隣接する位置に存在する。
【0165】
図29−bの場合は、図31−bに一例を示すように、縦横8ブロックからなる正方形を縦横2等分してできる4つの正方形のうち、左上と右下、右上と左下をそれぞれ組み合わせてできる2つの領域を第1、第2の抽出領域とした場合に相当する。このため、第1、第2の抽出領域の形状は、ともに縦横2ブロックからなる正方形を1つの頂点を共有するように45度あるいは135度の対角線上に2つ配置した形状となっている。また、領域の相対的な位置関係を見ると、第2の領域を構成する2つの正方形が、第1の領域の左上の正方形のすぐ左と下に隣接する位置に第2の領域が存在する。
【0166】
図29−cの場合は、図31−cに一例を示すように、第1、第2の抽出領域の形状は、ともに縦横10ブロックからなる正方形である。また、第1、第2の抽出領域の相対的な位置関係を見ると、縦横ともに10ブロックの整数倍だけ離れた位置に存在する。
【0167】
図29−dの場合は、図31−dに一例を示すように、第1、第2の抽出領域の形状は、ともに縦横6ブロックからなる正方形である。また第1、第2の抽出領域の相対的な位置関係を見ると、縦横ともに6ブロックの整数倍だけ離れた位置に存在する。
【0168】
図29−eの場合は、図31−eに一例を示すように、正方形領域を中心部分の正方形とその外側の2つに分けてできる2つの領域を第1、第2の抽出領域とした場合に相当する。このため、領域の形状は、第2の抽出領域が中心部分の正方形、第1の正方形は全体の正方形から第2の抽出領域をくりぬいた形状である。また、領域の相対的な位置関係を見ると、第1の抽出領域の中央の穴の位置に第2の抽出領域が存在する。
【0169】
図29−fの場合は、図31−fに一例を示すように、領域の形状は、第1の抽出領域は縦6ブロック、横10ブロックの長方形、第2の抽出領域は縦10ブロック、横6ブロックの長方形である。また、第1、第2の抽出領域の相対的な位置関係を見ると、中心位置が一致するように配置されている。
【0170】
図29−gの場合には、図31−gに一例を示すように、縦4ブロック、横12ブロックからなる長方形、あるいは縦12ブロック、横4ブロックからなる長方形を、長い辺を3等分してできる中央の正方形とそれ以外の2領域を第1、第2の抽出領域とした場合に相当する。このため、領域の形状は、第1の抽出領域は縦横4ブロックからなる正方形を2つ、縦か横に4ブロック離れて配置した形状で、第2の抽出領域は縦横4ブロックからなる正方形である。また、領域の相対的な位置関係を見ると、第1の抽出領域の間に第2の抽出領域が存在する。
【0171】
以後、図29−a、図29−b、図29−c、図29−d、図29−e、図29−f、図29−gの領域タイプを、それぞれ領域タイプa、領域タイプb、領域タイプc、領域タイプd、領域タイプe、領域タイプf、領域タイプgと呼ぶことにする。
【0172】
第8の実施の形態では、図29で示した各領域において、領域特徴量として輝度値の平均を算出し、各次元の特徴量を算出する。もちろん、輝度値の平均のかわりにメディアンや最大値など、前述の様々な抽出方法によって抽出した値を領域特徴量として求めるようにしてもよい。
【0173】
各次元の特徴量の量子化では、上述の領域のタイプ別に閾値を定め、量子化を行うようにする。例えば、式2に従って特徴量を3値に量子化する場合には、領域のタイプ別に、0、1、−1の生起の割合が均等になるように量子化の閾値thを決定し、量子化を行うようにする。具体的には、段落0085で記述した方法をP=33.333%、Nを領域タイプ別の次元数として領域タイプ別に適用し、閾値thを求める。例えば、領域タイプaの場合にはN=113となるため、th=D(floor(113×33.333/100))=D(37)により閾値を算出する。ここで、D(i)(i=0、1、…、N−1)は、領域タイプaに該当する第1次元から第113次元の差分値の絶対値を昇順にソートした集合になる。この場合は閾値に対応するインデックスが37となる。同様に、他の領域タイプに対しても、閾値に対応するインデックスを求めることができる。これを示したのが図30である。このように領域タイプ別に閾値を求める方が、全体で閾値を決める場合に比べて各次元での0、1、−1の発生確率を均一化できるようになり、識別能力が向上する。もちろん、前述の他の様々な量子化方法によって量子化するようにしてもよい。
【0174】
なお、第8の実施の形態の場合には、図28で示したブロックごとに代表値(例えば、ブロック内の画素の輝度値の平均値)を先に算出し、それから領域特徴量を抽出するようにしてもよい。これにより、領域内の全画素から直接領域特徴量を抽出する場合よりも高速に抽出できるようになる。また、各領域タイプの抽出領域は、全体として対称性を有する。このため、画像の右と左を反転させたり、上下を反転させたりした場合でも、次元の対応関係と符号を適切に変更することによって、左右または上下反転した画像から抽出された特徴量からもとの画像の特徴量を復元できる。このため、左右あるいは上下を反転させた画像とも照合することができるようになる。
【0175】
[照合手段の実施の形態]
次に、本発明で出力される量子化インデックスベクトルを照合する照合手段についてブロック図を用いて説明する。
【0176】
図21を参照すると、本発明で出力される量子化インデックスベクトルを照合する照合手段100のブロック図が示されており、次元決定手段101、量子化値取得手段102、103、尺度算出手段104とからなる。
【0177】
次元決定手段101は量子化値取得手段102、103へ接続され、決定された次元情報を出力する。量子化値取得手段102は、第1の量子化インデックスベクトルから、次元決定手段101から入力される次元の量子化インデックス値を取得し、第1の量子化インデックス値として尺度算出手段104へ出力する。量子化値取得手段103は、第2の量子化インデックスベクトルから、次元決定手段101から入力される次元の量子化インデックス値を取得し、第2の量子化インデックス値として尺度算出手段104へ出力する。尺度算出手段104は、量子化値取得手段102、103からそれぞれ出力される第1、第2の量子化インデックス値から同一性を表す尺度を算出し、出力する。
【0178】
次に、図21の照合手段100の動作について説明する。
【0179】
まず、照合手段100へは、第1の画像から抽出される量子化インデックスベクトルである第1の量子化インデックスベクトルと、第2の画像から抽出される量子化インデックスベクトルである第2の量子化インデックスベクトルとが入力される。入力された第1、第2の量子化インデックスベクトルは、それぞれ量子化値取得手段102、103へ入力される。
【0180】
量子化値取得手段102、103へは、次元決定手段101から出力される次元情報も入力される。次元決定手段101では、N次元ベクトルである量子化インデックスベクトルの各次元を指定する情報を順次出力する。出力する順序は必ずしも1からNまで1つずつ増えていく必要はなく、1からNまでの次元が過不足なく指定される順序であれば、どのような順序であってもよい。
【0181】
量子化値取得手段102、103では、入力された量子化インデックスベクトルから、次元決定手段101から出力される次元情報で指定される次元の量子化インデックス値を取得する。そして、取得した量子化インデックス値を尺度算出手段104へ出力する。
【0182】
尺度算出手段104では、量子化値取得手段102から出力される第1の量子化インデックス値と第2の量子化インデックス値とを比較する。この比較を各次元に対して行い、第1、第2の量子化インデックスベクトル間の類似尺度(あるいは距離尺度)を同一性尺度として算出する。
【0183】
得られた同一性尺度値は予め定めた閾値と比較し、同一性の判定を行う。同一性尺度が類似度をあらわす尺度である場合には、尺度値が閾値以上の場合に同一と判定する。一方、同一性尺度が距離をあらわす尺度である場合には、尺度値が閾値以下の場合に同一と判定する。
【0184】
次に、フローチャートを用いて図21の照合手段100の動作を説明する。まず、同一性尺度として類似度を用いる場合の動作について説明する。
【0185】
図22は、照合手段100の動作を示すフローチャートである。図22のフローチャートでは、量子化インデックスベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。また、類似度を算出する変数をBで表すこととする。
【0186】
まず、次元決定手段101は、照合する量子化インデックスベクトルの最初の次元として、次元1を決定し(n=1)、量子化値取得手段102、103へ供給するとともに、尺度算出手段104において変数Bを0にセットする。(ステップS100)。
【0187】
次に、量子化値取得手段102、103において、第1の量子化インデックスベクトル、第2の量子化インデックスベクトルから、次元nの第1の量子化インデックス値と第2の量子化インデックス値とを取得し、尺度算出手段104へ供給する(ステップS102)。
【0188】
次に、尺度算出手段104において、第1の量子化インデックス値と第2の量子化インデックス値とから、それぞれの量子化インデックスに対応する特徴量の間の類似度ΔBを算出する(ステップS104)。例えば、量子化インデックスが一致する場合にはΔB=1とし、それ以外の場合はΔB=0とする。あるいは、量子化インデックスから量子化前の特徴量の代表値を算出し、代表値間の差分が小さいほど大きくなる値をΔBとして用いてもよい。この際、特徴量の代表値を算出して差分を求めるかわりに、量子化インデックス値の組み合わせによってΔBの値を引くことができるテーブルを保持しておき、量子化インデックス値の組み合わせからこのテーブルを用いてΔBの値を直接求めるようになっていてもよい。
【0189】
次に、ΔBの値は変数Bに加算される(ステップS106)。この際、ΔBの値が0の場合には、変数Bに0を加算するかわりに、加算しないように制御してもよい。
【0190】
次に、次元の番号nが次元数Nに到達したかどうかを調べ(ステップS108)、到達しない場合はステップS112へ移行し、到達した場合には、そのときの変数Bの値を同一性尺度(類似度を表す尺度)として出力し(ステップS110)、処理を終了する。
【0191】
ステップ112では、次元決定手段101が、取得する量子化インデックスの次元として、n=n+1によって次の次元を決定し、量子化値取得手段102、103へ供給する。そして、再度ステップS102へ移行する。
【0192】
なお、ここでは、次元1からNまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0193】
次に、同一性尺度として距離を用いる場合の動作について説明する。
【0194】
図23は、照合手段100の動作を示す別のフローチャートである。図23のフローチャートでも、量子化インデックスベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。また、距離尺度を算出する変数をCで表すこととする。
【0195】
基本的なフローは、図22の場合と同じであるが、ステップS100、S104、S106、S110がそれぞれステップS200、S204、S206、S210に置き換わっている点が異なる。
【0196】
まず、ステップS200では、次元決定手段101において、照合する量子化インデックスベクトルの最初の次元として、次元1を決定し(n=1)、量子化値取得手段102、103へ供給するとともに、尺度算出手段104において変数Cを0にセットする。
【0197】
ステップS204では、尺度算出手段104において、第1の量子化インデックス値と第2の量子化インデックス値とから、それぞれの量子化インデックスに対応する特徴量の距離ΔCを算出する。例えば、量子化インデックスが一致する場合にはΔC=0とし、それ以外の場合はΔC=1とする。あるいは、量子化インデックスから量子化前の特徴量の代表値を算出し、代表値間の差分が小さいほど小さくなる値をΔCとして用いてもよい。この際、特徴量の代表値を算出して差分を求めるかわりに、量子化インデックス値の組み合わせによってΔCの値を引くことができるテーブルを保持しておき、量子化インデックス値の組み合わせからこのテーブルを用いてΔCの値を直接求めるようになっていてもよい。
【0198】
ステップS206では、ΔCの値は変数Cに加算される。この際、ΔCの値が0の場合には、変数Cに0を加算するかわりに、加算しないように制御してもよい。
【0199】
ステップS210では、そのときの変数Cの値を同一性尺度(距離を表す尺度)として出力し、処理を終了する。
【0200】
それ以外のステップについては、図22の場合と同様である。ただし、ステップS108で次元の番号nが次元数Nに到達した場合にはステップS210へ移行する。
【0201】
なお、ここでは、次元1からNまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0202】
次に、第1の量子化インデックス値と第2の量子化インデックス値とで、「共に量子化インデックスが0」である次元を除外し、同一性尺度として類似度を用いる場合の動作について説明する。
【0203】
図24は、照合手段100の動作を示す別のフローチャートである。図24のフローチャートでも、量子化インデックスベクトルの次元(の番号)をnで表し、次元は1からNまでの合計N次元あるものとする。また、類似度を算出する変数をBで表すこととし、「共に量子化インデックスが0」ではない次元をカウントするための変数をAで表すこととする。
【0204】
まず、次元決定手段101は、照合する量子化インデックスベクトルの最初の次元として、次元1を決定し(n=1)、量子化値取得手段102、103へ供給するとともに、尺度算出手段104において変数A、Bを0にセットし(ステップS300)、ステップS102へ移行する。
【0205】
ステップS102は図22の場合と同様であり、終了後、ステップS314へ移行する。
【0206】
ステップS314では、尺度算出手段104において、第1の量子化インデックス値と第2の量子化インデックス値とがともに0であるかどうかを調べる。ともに0である場合には、ステップS108へ移行し、どちらか一方が0でない場合には、変数Aの値をひとつ増やし(ステップS316)、ステップS104へ移行する。
【0207】
ステップS104、S106、S108、S112の動作は図22の場合と同様である。ステップS108で次元の番号nが次元数Nに到達した場合には、ステップS310へ移行する。
【0208】
ステップS310では、尺度算出手段104において、B/Aの値を算出し、同一性尺度として出力し、処理を終了する。ただし、A=0の場合には、規定の値(例えば0.5)を出力する。
【0209】
なお、ここでは、次元1からNまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。
【0210】
[照合手段の別の実施の形態]
次に、本発明で出力される量子化インデックスベクトルを照合する照合手段の別の実施の形態についてブロック図を用いて説明する。
【0211】
図25を参照すると、本発明で出力される量子化インデックスベクトルを照合する照合手段200のブロック図が示されており、符号決定手段201、符号値取得手段202、203、尺度算出手段204とからなる。
【0212】
符号決定手段201は符号値取得手段202、203へ接続され、決定された符号指定情報を出力する。符号値取得手段202は、第1の符号化量子化インデックスベクトルから、符号決定手段201から入力される符号指定情報により定まる符号の値を取得し、第1の符号値として尺度算出手段204へ出力する。符号値取得手段203は、第2の符号化量子化インデックスベクトルから、符号決定手段201から入力される符号指定情報により定まる符号の値を取得し、第2の符号値として尺度算出手段204へ出力する。尺度算出手段204は、符号値取得手段202、203からそれぞれ出力される第1、第2の符号値から同一性を表す尺度を算出し、出力する。
【0213】
次に、図25の照合手段200の動作について説明する。
【0214】
まず、照合手段200へは、第1の画像から抽出される量子化インデックスベクトルを符号化したベクトルである第1の符号化量子化インデックスベクトルと、第2の画像から抽出される量子化インデックスベクトルを符号化したベクトルである第2の符号化量子化インデックスベクトルとが入力される。ここで、符号化量子化インデックスベクトルは、量子化インデックスベクトルの量子化インデックス値を複数次元分まとめて符号化して得られる符号からなる符号列である。段落0142で説明したように、特徴ベクトルの各次元の特徴量を3値に量子化し、5次元分まとめて符号化する場合には、5次元ごとに1つの符号が生成される。よって、特徴ベクトルの次元数がNの場合には、N/5個の符号が生成される。この場合、符号化量子化インデックスベクトルはN/5個の符号からなる符号列となる。
【0215】
入力された第1、第2の符号化量子化インデックスベクトルは、それぞれ符号値取得手段202、203へ入力される。
【0216】
符号値取得手段202、203へは、符号決定手段201から出力される符号指定情報も入力される。符号決定手段201では、符号列中の各符号を指定する情報を順次出力する。符号列中の符号の数をM(上述の例ではM=N/5)とすると、出力する順序は必ずしも1からMまで1つずつ増えていく必要はなく、1からMまでの値が過不足なく指定される順序であれば、どのような順序であってもよい。
【0217】
符号値取得手段202、203では、入力された符号化量子化インデックスベクトルから、符号決定手段201から出力される符号指定情報で指定される符号の値を取得する。そして、取得した符号値を尺度算出手段204へ出力する。
【0218】
尺度算出手段204では、符号取得手段201、202から出力される第1の符号値と第2の符号値とを比較する。この際、符号値を復号して量子化インデックス値に戻してから比較するのではなく、符号値のまま比較する。段落0150から段落0152で説明したように、尺度算出手段204では、2つの符号値からそれらの符号の間の同一性尺度をひくことができるルックアップテーブルが用意されており、これを用いて符号単位で同一性尺度を算出する。これを各符号に対して行い、第1、第2の符号値間の類似尺度(あるいは距離尺度)を同一性尺度として算出する。
【0219】
得られた同一性尺度値は予め定めた閾値と比較し、同一性の判定を行う。同一性尺度が類似度をあらわす尺度である場合には、尺度値が閾値以上の場合に同一と判定する。一方、同一性尺度が距離をあらわす尺度である場合には、尺度値が閾値以下の場合に同一と判定する。
【0220】
次に、フローチャートを用いて図25の照合手段200の動作を説明する。ここでは、同一性尺度として類似度を用いる場合の動作について説明する。
【0221】
図26は、照合手段200の動作を示すフローチャートである。図26のフローチャートでは、符号化量子化インデックスベクトルの符号の番号をmで表し、番号は1からMまでの合計M個の符号があるものとする。また、類似度を算出する変数をBで表すこととする。
【0222】
まず、符号決定手段201は、照合する符号化量子化インデックスベクトルの最初の符号として、1番目の符号を取得することを決定し(m=1)、符号値取得手段202、203へ供給するとともに、尺度算出手段204において変数Bを0にセットする。(ステップS600)。
【0223】
次に、符号値取得手段202、203において、第1の符号化量子化インデックスベクトル、第2の符号化量子化インデックスベクトルから、m番目の第1の符号値と第2の符号値とを取得し、尺度算出手段204へ供給する(ステップS602)。
【0224】
次に、尺度算出手段204において、第1の符号値と第2の符号値とから、それぞれの符号値に対応する複数次元の特徴量間の類似度ΔBを、段落0150で説明したルックアップテーブルを参照することにより算出する(ステップS604)。
【0225】
次に、ΔBの値は変数Bに加算される(ステップS106)。この際、ΔBの値が0の場合には、変数Bに0を加算するかわりに、加算しないように制御してもよい。
【0226】
次に、符号の番号mが符号数Mに到達したかどうかを調べ(ステップS608)、到達しない場合はステップS612へ移行し、到達した場合には、そのときの変数Bの値を同一性尺度(類似度を表す尺度)として出力し(ステップS110)、処理を終了する。
【0227】
ステップ612では、符号決定手段201が、取得する量子化インデックスの次元として、m=m+1によって次の符号の番号を決定し、符号指定情報として符号値取得手段202、203へ供給する。そして、再度ステップS602へ移行する。
【0228】
なお、ここでは、符号の番号1からMまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。また、ここでは類似度を算出する場合について述べたが、同様にして、距離尺度を同一性尺度として算出することもできる。この場合、ルックアップテーブルには、類似度の変わりに距離尺度を保持しておくようにする。
【0229】
図27は、照合手段200の動作を示す別のフローチャートである。図27のフローチャートでも、符号化量子化インデックスベクトルの符号の番号をmで表し、番号は1からMまでの合計M個の符号があるものとする。また、類似度を算出する変数をBで表すこととし、「共に量子化インデックスが0」ではない次元をカウントするための変数をAで表すこととする。
【0230】
まず、符号決定手段201は、照合する符号化量子化インデックスベクトルの最初の符号として、1番目の符号を取得することを決定し(m=1)、符号値取得手段202、203へ供給するとともに、尺度算出手段204において変数A、Bを0にセットし(ステップS700)、ステップS602へ移行する。
【0231】
ステップS602は図26の場合と同様であり、終了後、ステップS714へ移行する。
【0232】
ステップS714では、尺度算出手段204において、第1の符号値と第2の符号値とから、符号値に対応する複数の特徴ベクトルの次元内に、「ともに0」とはならない次元がいくつあるかを調べる。この数をΔAとする。これも、段落0152で述べたように、符号値とΔAとの関係を記述したルックアップテーブルを用いることによって算出できる。
【0233】
次に、ΔAの値は変数Aに加算される(ステップS716)。この際、ΔAの値が0の場合には、変数Aに0を加算するかわりに、加算しないように制御してもよい。
【0234】
ステップS604、S106、S608、S612の処理は図26の場合と同様である。ステップS608で符号の番号mが符号数Mに到達した場合には、ステップS310へ移行する。
【0235】
ステップS310では、尺度算出手段204において、B/Aの値を算出し、同一性尺度として出力し、処理を終了する。ただし、A=0の場合には、規定の値(例えば0.5)を出力する。
【0236】
なお、ここでは、符号の番号mからMまで順番に抽出処理を行っているが、順番はこれに限らず任意でよい。また、ここでは類似度を算出する場合について述べたが、同様にして、距離尺度を同一性尺度として算出することもできる。この場合、ルックアップテーブルには、類似度の変わりに距離尺度を保持しておくようにする。
【0237】
以上本発明の実施の形態について説明したが、本発明は、上述した実施形態に限定されるものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解しうる様々な変更をすることができる。また、本発明の画像識別子抽出装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における次元決定手段、抽出領域取得手段、領域特徴量算出手段、比較手段、領域特徴量算出方法取得手段、比較方法取得手段として機能させる。
【0238】
なお、本発明は、日本国にて2009年3月13日に特許出願された特願2009−061022の特許出願、および日本国にて2009年4月14日に特許出願された特願2009−097864の特許出願に基づく優先権主張の利益を享受するものであり、当該特許出願に記載された内容は、全て本明細書に含まれるものとする。
【符号の説明】
【0239】
1…次元決定手段
2…抽出領域取得手段
3、3A…領域特徴量算出手段
31、31A…第1の領域特徴量算出手段
32、32A…第2の領域特徴量算出手段
4、4B…比較手段
41…大小比較手段
42、44…量子化手段
43…差分値算出手段
45…量子化境界決定手段
5…領域特徴量算出方法取得手段
6…比較方法取得手段
7…符号化手段
【特許請求の範囲】
【請求項1】
画像を識別する情報である画像識別子を照合する照合部を備え、
前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも前記特定の値の場合に、各次元の値の少なくとも一方が前記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項2】
請求項1に記載の画像識別子照合装置であって、
前記照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致する次元の数をBとした場合に、BをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項3】
請求項1に記載の画像識別子照合装置であって、
前記照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致しない次元の数をCとした場合に、CをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項4】
画像を識別する情報である画像識別子を照合する照合部を備え、
前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合部が照合する前記画像識別子は、当該画像識別子を構成する複数の次元に対応して量子化された各値が1ビットの値に符号化された情報を含むように符号化され、
前記照合部は、照合する2つの画像識別子が含む前記符号化された値に基づいて、当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項5】
請求項4に記載の画像識別子照合装置であって、
前記照合部は、前記符号化された値に対応する複数の次元の量子化された値の間のハミング距離に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項6】
請求項4に記載の画像識別子照合装置であって、
前記照合部は、前記符号化された値に対応する複数の次元の量子化された値の間の類似度に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項7】
画像を識別する情報である画像識別子を照合し、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも前記特定の値の場合に、各次元の値の少なくとも一方が前記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項8】
請求項7に記載の画像識別子照合方法であって、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致する次元の数をBとした場合に、BをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項9】
請求項7に記載の画像識別子照合方法であって、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致しない次元の数をCとした場合に、CをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項10】
画像を識別する情報である画像識別子を照合し、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
さらに、当該画像識別子を構成する複数の次元に対応して量子化された各値が1ビットの値に符号化された情報を含むように符号化され、
前記照合では、照合する2つの画像識別子が含む前記符号化された値に基づいて、当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項11】
請求項10に記載の画像識別子照合方法であって、
前記照合では、前記符号化された値に対応する複数の次元の量子化された値の間のハミング距離に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項12】
請求項10に記載の画像識別子照合方法であって、
前記照合では、前記符号化された値に対応する複数の次元の量子化された値の間の類似度に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項13】
コンピュータを、
画像を識別する情報である画像識別子を照合する照合部として機能させるためのプログラムであって、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも前記特定の値の場合に、各次元の値の少なくとも一方が前記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する、プログラム。
【請求項14】
コンピュータを、
画像を識別する情報である画像識別子を照合する照合部として機能させるためのプログラムであって、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
さらに、当該画像識別子を構成する複数の次元に対応して量子化された各値が1ビットの値に符号化された情報を含むように符号化され、
前記照合では、照合する2つの画像識別子が含む前記符号化された値に基づいて、当該2つの画像識別子を照合する、プログラム。
【請求項1】
画像を識別する情報である画像識別子を照合する照合部を備え、
前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも前記特定の値の場合に、各次元の値の少なくとも一方が前記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項2】
請求項1に記載の画像識別子照合装置であって、
前記照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致する次元の数をBとした場合に、BをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項3】
請求項1に記載の画像識別子照合装置であって、
前記照合部は、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致しない次元の数をCとした場合に、CをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項4】
画像を識別する情報である画像識別子を照合する照合部を備え、
前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合部が照合する前記画像識別子は、当該画像識別子を構成する複数の次元に対応して量子化された各値が1ビットの値に符号化された情報を含むように符号化され、
前記照合部は、照合する2つの画像識別子が含む前記符号化された値に基づいて、当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項5】
請求項4に記載の画像識別子照合装置であって、
前記照合部は、前記符号化された値に対応する複数の次元の量子化された値の間のハミング距離に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項6】
請求項4に記載の画像識別子照合装置であって、
前記照合部は、前記符号化された値に対応する複数の次元の量子化された値の間の類似度に基づいて当該2つの画像識別子を照合する、画像識別子照合装置。
【請求項7】
画像を識別する情報である画像識別子を照合し、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも前記特定の値の場合に、各次元の値の少なくとも一方が前記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項8】
請求項7に記載の画像識別子照合方法であって、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致する次元の数をBとした場合に、BをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項9】
請求項7に記載の画像識別子照合方法であって、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値の少なくとも一方が前記特定の値ではない、次元の数をAとし、前記A個の前記次元のうち量子化された値が画像識別子の間で一致しない次元の数をCとした場合に、CをAで割った結果の値に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項10】
画像を識別する情報である画像識別子を照合し、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
さらに、当該画像識別子を構成する複数の次元に対応して量子化された各値が1ビットの値に符号化された情報を含むように符号化され、
前記照合では、照合する2つの画像識別子が含む前記符号化された値に基づいて、当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項11】
請求項10に記載の画像識別子照合方法であって、
前記照合では、前記符号化された値に対応する複数の次元の量子化された値の間のハミング距離に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項12】
請求項10に記載の画像識別子照合方法であって、
前記照合では、前記符号化された値に対応する複数の次元の量子化された値の間の類似度に基づいて当該2つの画像識別子を照合する、画像識別子照合方法。
【請求項13】
コンピュータを、
画像を識別する情報である画像識別子を照合する照合部として機能させるためのプログラムであって、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
前記照合では、照合する2つの画像識別子を構成するある次元のそれぞれの値がいずれも前記特定の値の場合に、各次元の値の少なくとも一方が前記特定の値でない場合とは異なる処理を用いて当該2つの画像識別子を照合する、プログラム。
【請求項14】
コンピュータを、
画像を識別する情報である画像識別子を照合する照合部として機能させるためのプログラムであって、
前記照合される前記画像識別子は、当該画像識別子を構成する各次元に関連付けられる、画像中の、2つの部分領域から領域特徴量が当該次元毎に算出され、
次元毎に算出された前記領域特徴量の差分値の絶対値に基づいて、当該差分値が前記画像識別子の各次元の値として量子化されている情報であり、
かつ、当該差分値が所定の値より小さい場合には特定の値に量子化され、
さらに、当該画像識別子を構成する複数の次元に対応して量子化された各値が1ビットの値に符号化された情報を含むように符号化され、
前記照合では、照合する2つの画像識別子が含む前記符号化された値に基づいて、当該2つの画像識別子を照合する、プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14−a】
【図14−b】
【図14−c】
【図14−d】
【図14−e】
【図14−f】
【図14−g】
【図14−h】
【図14−i】
【図14−j】
【図15−a】
【図15−b】
【図15−c】
【図15−d】
【図15−e】
【図16−a】
【図16−b】
【図16−c】
【図16−d】
【図16−e】
【図17−a】
【図17−b】
【図17−c】
【図17−d】
【図17−e】
【図18】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29−a】
【図29−b】
【図29−c】
【図29−d】
【図29−e】
【図29−f】
【図29−g】
【図30】
【図31−a】
【図31−b】
【図31−c】
【図31−d】
【図31−e】
【図31−f】
【図31−g】
【図19】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14−a】
【図14−b】
【図14−c】
【図14−d】
【図14−e】
【図14−f】
【図14−g】
【図14−h】
【図14−i】
【図14−j】
【図15−a】
【図15−b】
【図15−c】
【図15−d】
【図15−e】
【図16−a】
【図16−b】
【図16−c】
【図16−d】
【図16−e】
【図17−a】
【図17−b】
【図17−c】
【図17−d】
【図17−e】
【図18】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29−a】
【図29−b】
【図29−c】
【図29−d】
【図29−e】
【図29−f】
【図29−g】
【図30】
【図31−a】
【図31−b】
【図31−c】
【図31−d】
【図31−e】
【図31−f】
【図31−g】
【図19】
【公開番号】特開2012−195012(P2012−195012A)
【公開日】平成24年10月11日(2012.10.11)
【国際特許分類】
【出願番号】特願2012−157616(P2012−157616)
【出願日】平成24年7月13日(2012.7.13)
【分割の表示】特願2011−503732(P2011−503732)の分割
【原出願日】平成22年3月12日(2010.3.12)
【出願人】(000004237)日本電気株式会社 (19,353)
【Fターム(参考)】
【公開日】平成24年10月11日(2012.10.11)
【国際特許分類】
【出願日】平成24年7月13日(2012.7.13)
【分割の表示】特願2011−503732(P2011−503732)の分割
【原出願日】平成22年3月12日(2010.3.12)
【出願人】(000004237)日本電気株式会社 (19,353)
【Fターム(参考)】
[ Back to top ]