画像中に現れるオブジェクトを表示または検索する方法、その装置、コンピュータ・システム、及びコンピュータ・プログラムまたはコンピュータ可読記憶媒体
【課題】オブジェクト検索のパフォーマンスを改善する。
【解決手段】１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、前記信号に基づいて曲率スケール空間（ＣＳＳ）における前記オブジェクトの輪郭のピークの縦座標値を複数導き出すステップを有し、ＣＳＳ表示を導き出す方法として、２項フィルタが用いられる。また、輪郭の表示に到達するために、縦座標値に対してスケーリングあるいは非線形変換を行うステップをさらに有する。
【解決手段】１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、前記信号に基づいて曲率スケール空間（ＣＳＳ）における前記オブジェクトの輪郭のピークの縦座標値を複数導き出すステップを有し、ＣＳＳ表示を導き出す方法として、２項フィルタが用いられる。また、輪郭の表示に到達するために、縦座標値に対してスケーリングあるいは非線形変換を行うステップをさらに有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索を目的とする、マルチメディア・データベースに保存された画像のような静止画像またはビデオ画像中に現れるオブジェクトの表示に関し、特に、そのような表示を用いてオブジェクトを検索する方法及び装置に関する。
【背景技術】
【０００２】
ビデオ・ライブラリの画像のようなアプリケーションでは、ビデオ画像あるいは静止画像中に現れるオブジェクトの輪郭や形状またはオブジェクトの一部の効率的な表示および保存を行うことが望ましい。形状ベースの索引付けと検索を行うための公知の手法では曲率スケール空間(ＣＳＳ)表示が用いられる。ＣＳＳの詳細については、論文「曲率スケール空間によるロバストで効率的な形状索引付け」(英国マシーン・ビジョン会報pp.５３〜６２、エジンバラ、英国、１９９６年)ならびに「曲率スケール空間を用いる形状内容による画像データベースの索引付け」(インテリジェント・データベースに関するＩＥＥ専門家会議会報、ロンドン、１９９６年)の中で入手することができる。両論文ともMokhtarian、S.AbbasiならびにJ.Kittlerによるものであり、その内容は本明細書中に参考文献として取り入れられている。
【０００３】
ＣＳＳ表示では、オブジェクトの輪郭を求めるために曲率関数が使用され、輪郭上の任意の点から表示が開始される。形状を平滑化する一連の変形を行うことにより輪郭の形状を展開しながら、曲率関数が検討される。さらに具体的には、ガウスフィルタの族と共に畳み込まれた曲率関数の導関数のゼロ・クロスが計算される。曲率スケール空間として周知のように、ゼロ・クロスはグラフ上にプロットされる。但し、ｘ軸は曲線の正規化された弧長であり、ｙ軸は展開パラメータ、特に、適用フィルタのパラメータである。グラフ上のプロットは輪郭の特徴を示すループを形成する。オブジェクトの輪郭の各凸状または凹状を成す部分はＣＳＳ画像におけるループに対応する。ＣＳＳ画像において最も突起したループのピークの縦座標は輪郭の表示として利用される。
【０００４】
入力オブジェクトの形状に一致する、データベース中の保存画像のオブジェクトを検索するために、入力形状のＣＳＳ表示が計算される。マッチング・アルゴリズムを用いて、それぞれのＣＳＳ画像のピークの位置および高さを比較することにより、入力形状と保存形状との間の類似度が判定される。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
スケールの変化、回転、何らかの輪郭の変形および射影変換のような作像状態の変化の下でも変わらないオブジェクトの輪郭表示が得られることが望しい。また、さらに広いクラスの範囲で、形状の変動に対して鈍感な方法で形状を表すことが望まれる。例えば、オブジェクト‘車’の表示をその車のモデルとメーカーに対して不変にして抽出された特徴表示を利用してすべての車らしさを示す形状を容易に検索できるようにするほうがよい。
【０００６】
したがって本発明は、画像に対応する信号を処理することにより静止画像またはビデオ画像中に現れるオブジェクトを表す方法を提供するものであり、該方法は、オブジェクトの輪郭上に現れる特徴を表す複数の数値を導き出すステップと、前記値に対してスカラーまたは非線形変換を適用して輪郭の表示を得るステップとを有する。好適には、この変換は非線形変換であることが望ましい。好適には、ＣＳＳ表示を用いることが望ましく、また、好適には、展開パラメータに対応するピークの高さを示す値を変換することが望ましい。
【０００７】
本発明の場合のように、特にＣＳＳ値に対して変換を適用することにより、オブジェクト検索のパフォーマンスが改善することが判明した。
【課題を解決するための手段】
【０００８】
この発明に係る請求項１に記載の画像中に現れるオブジェクトを表示する方法は、１つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトを表示する方法であって、信号に基づいて曲率スケール空間（ＣＳＳ）におけるオブジェクトの輪郭のピークの縦座標値を複数導き出すステップを有し、ＣＳＳ表示を導き出す方法として、２項フィルタが用いられる。
【０００９】
この発明に係る請求項２に記載の画像中に現れるオブジェクトを表示する方法は、２項フィルタが、係数（１/４、１/２、１/４）を有する。
【００１０】
この発明に係る請求項３に記載の画像中に現れるオブジェクトを表示する方法は、輪郭の表示に到達するために、前記縦座標値に対してスケーリングあるいは非線形変換を行うステップをさらに有する。
【００１１】
この発明に係る請求項４に記載の画像中に現れるオブジェクトを検索する方法は、１つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトを検索する方法であって、２次元の輪郭の形状のクエリを入力するステップと、請求項１ないし３のいずれか１項に記載の方法を用いて輪郭の記述子を導き出すステップと、請求項１ないし３のいずれか１項に記載の方法を用いて導出され、記憶された画像内のオブジェクトの記述子を取得し、クエリの記述子と、記憶されたオブジェクトに対するそれぞれの記述子とを比較するステップと、クエリとの類似度を示す比較がなされたオブジェクトを含む画像に対応した、少なくとも１つの比較結果を選択し、表示するステップとを有する
【００１２】
この発明に係る請求項５に記載の画像中に現れるオブジェクトを表示する装置は、請求項１ないし４のいずれか１項に記載の方法を実行するように適合される。
【００１３】
この発明に係る請求項６に記載の画像中に現れるオブジェクトを表示するコンピュータ・システムは、請求項１ないし４のいずれか１項に記載の方法に従って作動するようにプログラムされている。
【００１４】
この発明に係る請求項７に記載のコンピュータ・プログラムまたはコンピュータ可読記憶媒体は、請求項１ないし４のいずれか１項に記載の方法を実現するためのコンピュータで実行可能な処理ステップを保存する。
【発明の効果】
【００１５】
本発明によるシステムは例えば画像ライブラリ中に設けることができる。或いは、データベースは、インターネットのようなネットワークにより電話線のような一時的リンクによって制御装置と接続し、システムの制御装置から遠隔地に配置することができる。例えば、画像データベースおよび記述子データベースは永久記憶装置またはＲＯＭやＤＶＤのような携帯用記憶媒体中に設けることができる。
【図面の簡単な説明】
【００１６】
【図１】ビデオ・データベース・システムのブロック図である。
【図２】オブジェクトの輪郭の図である。
【図３】図２の輪郭を示すＣＳＳ表示の図である。
【図４】ある形状の表示を例示する図である。
【図５】あるオブジェクトの形状を示す図である。
【図６】図５の形状のＣＳＳ表示の図である。
【図７】図５の形状の変換された表示の図である。
【図８】検索方法を例示するブロック図である。
【発明を実施するための形態】
【００１７】
添付図面を参照して本発明の実施の形態について説明する。
実施の形態１．
図１は、本発明の実施の形態によるコンピュータ処理を行うビデオ・データベース・システムを図示する。このシステムには、コンピュータの形の制御装置２、モニターの形の表示装置４、マウスの形のポインティング・デバイス６、保存された静止画像とビデオ画像とを含む画像データベース８および画像データベース８に保存された画像中に現れるオブジェクトまたはオブジェクトのいくつかの部分の記述子を保存する記述子データベース１０が含まれる。
【００１８】
画像データベースの画像中に現れる興味のある各オブジェクトの形状を表す記述子は、制御装置２によって導き出され、記述子データベース１０に保存される。制御装置２は、以下に説明するような方法を実行する適切なプログラムの制御によって動作して記述子を導き出す。
【００１９】
第一に、所定のオブジェクトの輪郭について、この輪郭のＣＳＳ表示が導き出される。上述の論文の１つに記載されているような周知の方法を用いてこのＣＳＳ表示が行われる。
【００２０】
さらに具体的には、この輪郭は写像表現Ψ＝{(x(u),y(u),u∈[0,1]}によって表される(ただし、uは正規化された弧長パラメータである)。
【００２１】
この輪郭は、ＩＤガウスカーネルｇ(ｕ,ρ)を用いて畳み込みを行う(convolve)ことにより平滑化され、ρの変化として展開(evolving)曲線の曲率ゼロ・クロスが調べられる。ゼロクロスは曲率を表す下記の式を用いて特定される。
【００２２】
【数１】
【００２３】
但し、
【００２４】
【数２】
【００２５】
かつ、
【００２６】
【数３】
【００２７】
上記で、＊は畳み込みを表し、添え字は導関数を表す。
曲率ゼロ・クロスの数はρの変化につれて変化し、ρが十分に高いときΨはゼロ・クロスの凸状の曲線となる。
【００２８】
ゼロクロス・ポイントはＣＳＳ画像空間として知られるグラフ上にプロットされる。この結果複数の特徴を示す曲線が生じる。この特徴を示す曲線のピークが特定され、対応する縦座標が抽出され保存される。一般に上記の結果、ｎ個の座標の対((x１, y１)、(x２, y２)、...(xn, yn)の集合(ただし、ｎはピークの数、ｘｉはｉ番目のピークの弧長の位置、ｙｉはピークの高さである)が与えられる。
【００２９】
本実施の形態では、ガウスフィルタの近似値として係数(１/４、１/２、１/４)の２項フィルタが用いられ計算上の複雑さが若干減少する。この計算上の複雑さの減少は、ＤＳＰや汎用プロセッサ上で効率的に実行することができる便利なフィルタ係数から結果として生じるものである。
【００３０】
次いで、ピーク値、すなわちピークを表すｙ成分値はさらに処理される。具体的には、ｙ値は次の変換を用いて変換される。
【００３１】
【数４】
【００３２】
但し、ｐｏｗ(y，b)はｙbを示す。
この結果、ピーク値[(x1，y'1)、(x2２，y'2)...(xn，y'n)]からなる新しい集合が生じ、これらの値は輪郭を示す記述子として記述子データベースに保存される。
特定の例として、図２に図示の輪郭は図３に図示のようなＣＳＳ画像を結果として生じる。ＣＳＳ画像中の曲線のピークの縦座標の詳細を以下の表１に示す。
【００３３】
【表１】
【００３４】
次いで、ａ＝６、ｂ＝０.５、ｃ＝０を用いて上記の変換が適用される。すなわち、元のｙ値の平方根を計算しこれに定数を乗じる。この結果以下の値が生じる：
【００３５】
【表２】
【００３６】
ここで、これらの値は最も近い整数に丸められるが、別の丸め方を用いてもよい。
【００３７】
実施の形態２． 別の例を図４に示す。 図５はオブジェクト形状(この場合カメ)についてのもう１つの例を図示するものである。図６は図５の形状のＣＳＳピーク示す。図７は、ａ＝６、ｂ＝０.５、ｃ＝０を用いて上記式(１)で示す変換を用いた図６の変換されたピークを示す。
保存された記述子は検索目的に利用される。ユーザーは、ポインティング・デバイスを用いて、ディスプレイ上にオブジェクトの輪郭を描くことにより検索を開始する(ステップ５１０)。次いで、制御装置２が入力輪郭のＣＳＳ表示を導き出し(ステップ５２０)、次いで、上述のようにｙ値に対する変換が適用される(ステップ５３０)。次いで、この結果生じる入力輪郭の記述子は、以下モデル記述子として知られる記述子データベースに保存された各記述子と公知のマッチング手順を用いて比較される(ステップ５４０)。
【００３８】
このマッチング比較は適切なアルゴリズムを用いて行われ、データベースに各記述子の類似度測定値が結果として得られる。上述の論文に記載されているような公知のマッチング・アルゴリズムを用いてもよい。このマッチング手順について以下簡単に説明する。
【００３９】
２つの閉鎖した輪郭の形状、画像曲線Ψiとモデル曲線Ψmおよびそれらの曲線のピークのそれぞれの設定値{(xi1, yi1),(xi2, yi2),..,(xin, yin)}と{(xm1, ym1), (xm2, ym2),..,(xmn, ymn)}が与えられれば、類似度測定値が計算される。類似度測定値は、画像中のピークとモデル中のピークのマッチングの総コストとして定義される。総コストを最少化するマッチングはダイナミック・プログラミングを用いて計算される。アルゴリズムによって、モデルから得たピークが画像から得たピークに再帰的にマッチされ、このようなマッチの各々のコスト計算が行われる。各モデルのピークを唯一の画像ピークとマッチさせることができ、各画像ピークを唯一のモデル・ピークとマッチさせることができる。モデルおよび／または画像ピークのなかにはマッチしないままのものがある場合もあり、各マッチしないピークについては追加のペナルティ・コストが存在する。２つのピークの水平距離が０.２未満の場合、２つのピークをマッチすることができる。マッチのコストは２つのマッチしたピーク間の直線の長さである。マッチしなかったピークのコストはその高さである。
【００４０】
更に詳述すれば、アルゴリズムは、ノードがマッチしたピークに対応するツリー状の構造を作成し拡張することにより機能する。
【００４１】
１．画像(xik, yik)の最大値とモデル(xir, yir)の最大値とから成る開始ノードを作成する。
【００４２】
２．画像ピークの最大値の８０％以内の各残りのモデル・ピークについて追加の開始ノードを作成する。
【００４３】
３．１および２で作成した各開始ノードのコストを、この開始ノードとリンクした画像ピークおよびモデル・ピークのｙ座標の差の絶対値に初期化する。
【００４４】
４．３の各開始ノードについて、この開始ノードでマッチしたモデル・ピークと画像ピークのｘ(水平)座標の差として定義するＣＳＳシフト・パラメータアルファを計算する。シフト・パラメータは各ノードについて異なるものとなる。
【００４５】
５．各開始ノードについて、モデル・ピークのリストおよび画像ピークのリストを作成する。このリストにはどのピークがまだマッチしていないかに関する情報が含まれる。各開始ノードについて、“マッチしたもの”としてこのノードでマッチしたピークにマークをつけ、他のすべてのピークには“マッチしなかったもの”としてマークをつける。
【００４６】
６．ポイント８の条件が満たされるまで、最低コストのノードを再帰的に拡大する(ステップ１〜６で作成した各ノードから始めて、各ノードの子ノードが後に続く)。ノードを拡大するために以下の手順を用いる。
【００４７】
７．ノードの拡大：
マッチしないままになっている少なくとも１つの画像と１つのモデル・ピークが存在する場合、
マッチしない最も大きなスケール画像曲線ＣＳＳの最大値(xip, yip)を選択する。(ステップ４で計算した)開始ノード・シフト・パラメータを適用して選択した最大値をモデルＣＳＳ画像に写像し、選択されたピークは座標(xip-alpha, yip)を持つことになる。マッチしない最も近いモデル曲線ピーク(xms, yms)を決定する。２つのピーク間の水平距離が０.２未満(すなわち|xip-alpha-xms|＜０.２)である場合、２つのピークをマッチさせ、２つのピーク間の直線の長さとしてマッチのコストを定義する。そのノードの総コストにマッチのコストを加える。マッチしたピークに“マッチした”ものとしてマークをつけることによりそれぞれのリストからマッチしたピークを取り除く。２つのピーク間の水平距離が０.２より大きい場合、画像ピーク(xip, yip)はマッチすることはできない。その場合総コストに画像ピークの高さyipを加え、“マッチした”ものとしてそのピークにマークをつけることにより画像ピーク・リストからピーク(xip, yip)だけを取り除く。
【００４８】
上記条件が当てはまらない(マッチしなかった画像ピークしか存在しない、またはマッチしなかったモデル・ピークしか存在しない)場合、マッチしないままの状態に放置する。
【００４９】
マッチしなかった画像ピークまたはモデル・ピークの最も高い高さとしてマッチのコストを定義しリストからピークを取り除く。
【００５０】
８．７でノードを拡大した後、画像リストおよびモデル・リストの双方にマッチしないピークが存在しない場合マッチング処理は終了する。このノードのコストは画像とモデル曲線間の類似度測定値である。ピークが存在する場合には、ポイント７へ戻り最低コストのノードを拡大する。
【００５１】
画像曲線ピーク値とモデル曲線ピーク値とを交換して上記手順を繰り返す。最終マッチング値はこれら２つのピーク値のうちの低い方の値である。
【００５２】
もう１つの例として、ソートされた順序の各位置について、入力されたｘ値とそれに対応するモデルのｘ値との間の距離および入力されたｙ値とそれに対応するモデルのｙ値との間の距離が計算される。すべての位置について合計距離が計算され、合計距離が小さければ小さいほどマッチの程度は近くなる。入力輪郭とモデルのピークの数が異なる場合、合計距離の中に残りのマッチしなかったピークの高さが含まれる。
【００５３】
上記ステップがデータベースの各モデルについて繰り返される(ステップ４８０)。
【００５４】
マッチング比較の結果生じる類似度値がソートされ(ステップ４９０)、次いで、最も近いマッチング値(すなわち本例では最も低い類似度値)を示す類似度値を持つ記述子に対応するオブジェクトがユーザーに対して表示装置４に表示される(ステップ５００)。表示対象のオブジェクト数はユーザーが予め設定するか選択することができる。
【００５５】
実施の形態３．
別の実施の形態について説明する。本実施の形態は、様々な変換が用いられることを除けば前回の実施の形態と同じである。具体的にはｙ値は以下の変換を用いて変換される：
【００５６】
【数５】
【００５７】
すなわち、線形スケーリング変換が適用される。
ここで、ａ0＝４１、ａ1＝０.１９である。
変更例では、ａ0＝０、ａ1＝０.２７である。
ａ0、ａ1の様々な値を適宜使用することができる。
【００５８】
検索およびマッチング手順は前回の実施の形態で説明したものとほぼ同様である。 変換、特に、上述のようなスケーリングまたは非線形変換を含む線形変換を適用することにより、オブジェクト・クラスの範囲で形状輪郭の変化などに対して敏感でない記述子が結果として得られ、その結果オブジェクトの検索の改善という結果が得られるということが判明した。
【００５９】
上述の実施の形態では、記述子データベース１０に保存する前のＣＳＳ値に対して変換が適用される。上記とは別に、ＣＳＳ値をデータベース１０に保存してもよい。次いで、マッチング手順を行う前に検索処理の一部として変換を行ってもよい。
【００６０】
以上記載の実施の形態では変換はｙ座標値に対して適用される。しかし、ｘ座標値に対して変換を適用することもできる。
【００６１】
以上説明したようなシステムの構成要素は、ソフトウェアまたはハードウェアの形で設けることができる。コンピュータ・システムの形で本発明について説明したが、本発明は専用チップなどを用いて他の形で実現することもできる。
(本発明ではＣＳＳ表示を利用して)オブジェクトの２Ｄ形状を表す方法および２つの形状間の類似度を表す値を計算する方法を示す特定の例を示したが、同様の任意の適切な方法を用いることができる。
【００６２】
例えば、確認目的のためのオブジェクト画像のマッチングを行うために、またはフィルタリングを行うために本発明を用いることができる。
【技術分野】
【０００１】
本発明は、検索を目的とする、マルチメディア・データベースに保存された画像のような静止画像またはビデオ画像中に現れるオブジェクトの表示に関し、特に、そのような表示を用いてオブジェクトを検索する方法及び装置に関する。
【背景技術】
【０００２】
ビデオ・ライブラリの画像のようなアプリケーションでは、ビデオ画像あるいは静止画像中に現れるオブジェクトの輪郭や形状またはオブジェクトの一部の効率的な表示および保存を行うことが望ましい。形状ベースの索引付けと検索を行うための公知の手法では曲率スケール空間(ＣＳＳ)表示が用いられる。ＣＳＳの詳細については、論文「曲率スケール空間によるロバストで効率的な形状索引付け」(英国マシーン・ビジョン会報pp.５３〜６２、エジンバラ、英国、１９９６年)ならびに「曲率スケール空間を用いる形状内容による画像データベースの索引付け」(インテリジェント・データベースに関するＩＥＥ専門家会議会報、ロンドン、１９９６年)の中で入手することができる。両論文ともMokhtarian、S.AbbasiならびにJ.Kittlerによるものであり、その内容は本明細書中に参考文献として取り入れられている。
【０００３】
ＣＳＳ表示では、オブジェクトの輪郭を求めるために曲率関数が使用され、輪郭上の任意の点から表示が開始される。形状を平滑化する一連の変形を行うことにより輪郭の形状を展開しながら、曲率関数が検討される。さらに具体的には、ガウスフィルタの族と共に畳み込まれた曲率関数の導関数のゼロ・クロスが計算される。曲率スケール空間として周知のように、ゼロ・クロスはグラフ上にプロットされる。但し、ｘ軸は曲線の正規化された弧長であり、ｙ軸は展開パラメータ、特に、適用フィルタのパラメータである。グラフ上のプロットは輪郭の特徴を示すループを形成する。オブジェクトの輪郭の各凸状または凹状を成す部分はＣＳＳ画像におけるループに対応する。ＣＳＳ画像において最も突起したループのピークの縦座標は輪郭の表示として利用される。
【０００４】
入力オブジェクトの形状に一致する、データベース中の保存画像のオブジェクトを検索するために、入力形状のＣＳＳ表示が計算される。マッチング・アルゴリズムを用いて、それぞれのＣＳＳ画像のピークの位置および高さを比較することにより、入力形状と保存形状との間の類似度が判定される。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
スケールの変化、回転、何らかの輪郭の変形および射影変換のような作像状態の変化の下でも変わらないオブジェクトの輪郭表示が得られることが望しい。また、さらに広いクラスの範囲で、形状の変動に対して鈍感な方法で形状を表すことが望まれる。例えば、オブジェクト‘車’の表示をその車のモデルとメーカーに対して不変にして抽出された特徴表示を利用してすべての車らしさを示す形状を容易に検索できるようにするほうがよい。
【０００６】
したがって本発明は、画像に対応する信号を処理することにより静止画像またはビデオ画像中に現れるオブジェクトを表す方法を提供するものであり、該方法は、オブジェクトの輪郭上に現れる特徴を表す複数の数値を導き出すステップと、前記値に対してスカラーまたは非線形変換を適用して輪郭の表示を得るステップとを有する。好適には、この変換は非線形変換であることが望ましい。好適には、ＣＳＳ表示を用いることが望ましく、また、好適には、展開パラメータに対応するピークの高さを示す値を変換することが望ましい。
【０００７】
本発明の場合のように、特にＣＳＳ値に対して変換を適用することにより、オブジェクト検索のパフォーマンスが改善することが判明した。
【課題を解決するための手段】
【０００８】
この発明に係る請求項１に記載の画像中に現れるオブジェクトを表示する方法は、１つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトを表示する方法であって、信号に基づいて曲率スケール空間（ＣＳＳ）におけるオブジェクトの輪郭のピークの縦座標値を複数導き出すステップを有し、ＣＳＳ表示を導き出す方法として、２項フィルタが用いられる。
【０００９】
この発明に係る請求項２に記載の画像中に現れるオブジェクトを表示する方法は、２項フィルタが、係数（１/４、１/２、１/４）を有する。
【００１０】
この発明に係る請求項３に記載の画像中に現れるオブジェクトを表示する方法は、輪郭の表示に到達するために、前記縦座標値に対してスケーリングあるいは非線形変換を行うステップをさらに有する。
【００１１】
この発明に係る請求項４に記載の画像中に現れるオブジェクトを検索する方法は、１つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトを検索する方法であって、２次元の輪郭の形状のクエリを入力するステップと、請求項１ないし３のいずれか１項に記載の方法を用いて輪郭の記述子を導き出すステップと、請求項１ないし３のいずれか１項に記載の方法を用いて導出され、記憶された画像内のオブジェクトの記述子を取得し、クエリの記述子と、記憶されたオブジェクトに対するそれぞれの記述子とを比較するステップと、クエリとの類似度を示す比較がなされたオブジェクトを含む画像に対応した、少なくとも１つの比較結果を選択し、表示するステップとを有する
【００１２】
この発明に係る請求項５に記載の画像中に現れるオブジェクトを表示する装置は、請求項１ないし４のいずれか１項に記載の方法を実行するように適合される。
【００１３】
この発明に係る請求項６に記載の画像中に現れるオブジェクトを表示するコンピュータ・システムは、請求項１ないし４のいずれか１項に記載の方法に従って作動するようにプログラムされている。
【００１４】
この発明に係る請求項７に記載のコンピュータ・プログラムまたはコンピュータ可読記憶媒体は、請求項１ないし４のいずれか１項に記載の方法を実現するためのコンピュータで実行可能な処理ステップを保存する。
【発明の効果】
【００１５】
本発明によるシステムは例えば画像ライブラリ中に設けることができる。或いは、データベースは、インターネットのようなネットワークにより電話線のような一時的リンクによって制御装置と接続し、システムの制御装置から遠隔地に配置することができる。例えば、画像データベースおよび記述子データベースは永久記憶装置またはＲＯＭやＤＶＤのような携帯用記憶媒体中に設けることができる。
【図面の簡単な説明】
【００１６】
【図１】ビデオ・データベース・システムのブロック図である。
【図２】オブジェクトの輪郭の図である。
【図３】図２の輪郭を示すＣＳＳ表示の図である。
【図４】ある形状の表示を例示する図である。
【図５】あるオブジェクトの形状を示す図である。
【図６】図５の形状のＣＳＳ表示の図である。
【図７】図５の形状の変換された表示の図である。
【図８】検索方法を例示するブロック図である。
【発明を実施するための形態】
【００１７】
添付図面を参照して本発明の実施の形態について説明する。
実施の形態１．
図１は、本発明の実施の形態によるコンピュータ処理を行うビデオ・データベース・システムを図示する。このシステムには、コンピュータの形の制御装置２、モニターの形の表示装置４、マウスの形のポインティング・デバイス６、保存された静止画像とビデオ画像とを含む画像データベース８および画像データベース８に保存された画像中に現れるオブジェクトまたはオブジェクトのいくつかの部分の記述子を保存する記述子データベース１０が含まれる。
【００１８】
画像データベースの画像中に現れる興味のある各オブジェクトの形状を表す記述子は、制御装置２によって導き出され、記述子データベース１０に保存される。制御装置２は、以下に説明するような方法を実行する適切なプログラムの制御によって動作して記述子を導き出す。
【００１９】
第一に、所定のオブジェクトの輪郭について、この輪郭のＣＳＳ表示が導き出される。上述の論文の１つに記載されているような周知の方法を用いてこのＣＳＳ表示が行われる。
【００２０】
さらに具体的には、この輪郭は写像表現Ψ＝{(x(u),y(u),u∈[0,1]}によって表される(ただし、uは正規化された弧長パラメータである)。
【００２１】
この輪郭は、ＩＤガウスカーネルｇ(ｕ,ρ)を用いて畳み込みを行う(convolve)ことにより平滑化され、ρの変化として展開(evolving)曲線の曲率ゼロ・クロスが調べられる。ゼロクロスは曲率を表す下記の式を用いて特定される。
【００２２】
【数１】
【００２３】
但し、
【００２４】
【数２】
【００２５】
かつ、
【００２６】
【数３】
【００２７】
上記で、＊は畳み込みを表し、添え字は導関数を表す。
曲率ゼロ・クロスの数はρの変化につれて変化し、ρが十分に高いときΨはゼロ・クロスの凸状の曲線となる。
【００２８】
ゼロクロス・ポイントはＣＳＳ画像空間として知られるグラフ上にプロットされる。この結果複数の特徴を示す曲線が生じる。この特徴を示す曲線のピークが特定され、対応する縦座標が抽出され保存される。一般に上記の結果、ｎ個の座標の対((x１, y１)、(x２, y２)、...(xn, yn)の集合(ただし、ｎはピークの数、ｘｉはｉ番目のピークの弧長の位置、ｙｉはピークの高さである)が与えられる。
【００２９】
本実施の形態では、ガウスフィルタの近似値として係数(１/４、１/２、１/４)の２項フィルタが用いられ計算上の複雑さが若干減少する。この計算上の複雑さの減少は、ＤＳＰや汎用プロセッサ上で効率的に実行することができる便利なフィルタ係数から結果として生じるものである。
【００３０】
次いで、ピーク値、すなわちピークを表すｙ成分値はさらに処理される。具体的には、ｙ値は次の変換を用いて変換される。
【００３１】
【数４】
【００３２】
但し、ｐｏｗ(y，b)はｙbを示す。
この結果、ピーク値[(x1，y'1)、(x2２，y'2)...(xn，y'n)]からなる新しい集合が生じ、これらの値は輪郭を示す記述子として記述子データベースに保存される。
特定の例として、図２に図示の輪郭は図３に図示のようなＣＳＳ画像を結果として生じる。ＣＳＳ画像中の曲線のピークの縦座標の詳細を以下の表１に示す。
【００３３】
【表１】
【００３４】
次いで、ａ＝６、ｂ＝０.５、ｃ＝０を用いて上記の変換が適用される。すなわち、元のｙ値の平方根を計算しこれに定数を乗じる。この結果以下の値が生じる：
【００３５】
【表２】
【００３６】
ここで、これらの値は最も近い整数に丸められるが、別の丸め方を用いてもよい。
【００３７】
実施の形態２． 別の例を図４に示す。 図５はオブジェクト形状(この場合カメ)についてのもう１つの例を図示するものである。図６は図５の形状のＣＳＳピーク示す。図７は、ａ＝６、ｂ＝０.５、ｃ＝０を用いて上記式(１)で示す変換を用いた図６の変換されたピークを示す。
保存された記述子は検索目的に利用される。ユーザーは、ポインティング・デバイスを用いて、ディスプレイ上にオブジェクトの輪郭を描くことにより検索を開始する(ステップ５１０)。次いで、制御装置２が入力輪郭のＣＳＳ表示を導き出し(ステップ５２０)、次いで、上述のようにｙ値に対する変換が適用される(ステップ５３０)。次いで、この結果生じる入力輪郭の記述子は、以下モデル記述子として知られる記述子データベースに保存された各記述子と公知のマッチング手順を用いて比較される(ステップ５４０)。
【００３８】
このマッチング比較は適切なアルゴリズムを用いて行われ、データベースに各記述子の類似度測定値が結果として得られる。上述の論文に記載されているような公知のマッチング・アルゴリズムを用いてもよい。このマッチング手順について以下簡単に説明する。
【００３９】
２つの閉鎖した輪郭の形状、画像曲線Ψiとモデル曲線Ψmおよびそれらの曲線のピークのそれぞれの設定値{(xi1, yi1),(xi2, yi2),..,(xin, yin)}と{(xm1, ym1), (xm2, ym2),..,(xmn, ymn)}が与えられれば、類似度測定値が計算される。類似度測定値は、画像中のピークとモデル中のピークのマッチングの総コストとして定義される。総コストを最少化するマッチングはダイナミック・プログラミングを用いて計算される。アルゴリズムによって、モデルから得たピークが画像から得たピークに再帰的にマッチされ、このようなマッチの各々のコスト計算が行われる。各モデルのピークを唯一の画像ピークとマッチさせることができ、各画像ピークを唯一のモデル・ピークとマッチさせることができる。モデルおよび／または画像ピークのなかにはマッチしないままのものがある場合もあり、各マッチしないピークについては追加のペナルティ・コストが存在する。２つのピークの水平距離が０.２未満の場合、２つのピークをマッチすることができる。マッチのコストは２つのマッチしたピーク間の直線の長さである。マッチしなかったピークのコストはその高さである。
【００４０】
更に詳述すれば、アルゴリズムは、ノードがマッチしたピークに対応するツリー状の構造を作成し拡張することにより機能する。
【００４１】
１．画像(xik, yik)の最大値とモデル(xir, yir)の最大値とから成る開始ノードを作成する。
【００４２】
２．画像ピークの最大値の８０％以内の各残りのモデル・ピークについて追加の開始ノードを作成する。
【００４３】
３．１および２で作成した各開始ノードのコストを、この開始ノードとリンクした画像ピークおよびモデル・ピークのｙ座標の差の絶対値に初期化する。
【００４４】
４．３の各開始ノードについて、この開始ノードでマッチしたモデル・ピークと画像ピークのｘ(水平)座標の差として定義するＣＳＳシフト・パラメータアルファを計算する。シフト・パラメータは各ノードについて異なるものとなる。
【００４５】
５．各開始ノードについて、モデル・ピークのリストおよび画像ピークのリストを作成する。このリストにはどのピークがまだマッチしていないかに関する情報が含まれる。各開始ノードについて、“マッチしたもの”としてこのノードでマッチしたピークにマークをつけ、他のすべてのピークには“マッチしなかったもの”としてマークをつける。
【００４６】
６．ポイント８の条件が満たされるまで、最低コストのノードを再帰的に拡大する(ステップ１〜６で作成した各ノードから始めて、各ノードの子ノードが後に続く)。ノードを拡大するために以下の手順を用いる。
【００４７】
７．ノードの拡大：
マッチしないままになっている少なくとも１つの画像と１つのモデル・ピークが存在する場合、
マッチしない最も大きなスケール画像曲線ＣＳＳの最大値(xip, yip)を選択する。(ステップ４で計算した)開始ノード・シフト・パラメータを適用して選択した最大値をモデルＣＳＳ画像に写像し、選択されたピークは座標(xip-alpha, yip)を持つことになる。マッチしない最も近いモデル曲線ピーク(xms, yms)を決定する。２つのピーク間の水平距離が０.２未満(すなわち|xip-alpha-xms|＜０.２)である場合、２つのピークをマッチさせ、２つのピーク間の直線の長さとしてマッチのコストを定義する。そのノードの総コストにマッチのコストを加える。マッチしたピークに“マッチした”ものとしてマークをつけることによりそれぞれのリストからマッチしたピークを取り除く。２つのピーク間の水平距離が０.２より大きい場合、画像ピーク(xip, yip)はマッチすることはできない。その場合総コストに画像ピークの高さyipを加え、“マッチした”ものとしてそのピークにマークをつけることにより画像ピーク・リストからピーク(xip, yip)だけを取り除く。
【００４８】
上記条件が当てはまらない(マッチしなかった画像ピークしか存在しない、またはマッチしなかったモデル・ピークしか存在しない)場合、マッチしないままの状態に放置する。
【００４９】
マッチしなかった画像ピークまたはモデル・ピークの最も高い高さとしてマッチのコストを定義しリストからピークを取り除く。
【００５０】
８．７でノードを拡大した後、画像リストおよびモデル・リストの双方にマッチしないピークが存在しない場合マッチング処理は終了する。このノードのコストは画像とモデル曲線間の類似度測定値である。ピークが存在する場合には、ポイント７へ戻り最低コストのノードを拡大する。
【００５１】
画像曲線ピーク値とモデル曲線ピーク値とを交換して上記手順を繰り返す。最終マッチング値はこれら２つのピーク値のうちの低い方の値である。
【００５２】
もう１つの例として、ソートされた順序の各位置について、入力されたｘ値とそれに対応するモデルのｘ値との間の距離および入力されたｙ値とそれに対応するモデルのｙ値との間の距離が計算される。すべての位置について合計距離が計算され、合計距離が小さければ小さいほどマッチの程度は近くなる。入力輪郭とモデルのピークの数が異なる場合、合計距離の中に残りのマッチしなかったピークの高さが含まれる。
【００５３】
上記ステップがデータベースの各モデルについて繰り返される(ステップ４８０)。
【００５４】
マッチング比較の結果生じる類似度値がソートされ(ステップ４９０)、次いで、最も近いマッチング値(すなわち本例では最も低い類似度値)を示す類似度値を持つ記述子に対応するオブジェクトがユーザーに対して表示装置４に表示される(ステップ５００)。表示対象のオブジェクト数はユーザーが予め設定するか選択することができる。
【００５５】
実施の形態３．
別の実施の形態について説明する。本実施の形態は、様々な変換が用いられることを除けば前回の実施の形態と同じである。具体的にはｙ値は以下の変換を用いて変換される：
【００５６】
【数５】
【００５７】
すなわち、線形スケーリング変換が適用される。
ここで、ａ0＝４１、ａ1＝０.１９である。
変更例では、ａ0＝０、ａ1＝０.２７である。
ａ0、ａ1の様々な値を適宜使用することができる。
【００５８】
検索およびマッチング手順は前回の実施の形態で説明したものとほぼ同様である。 変換、特に、上述のようなスケーリングまたは非線形変換を含む線形変換を適用することにより、オブジェクト・クラスの範囲で形状輪郭の変化などに対して敏感でない記述子が結果として得られ、その結果オブジェクトの検索の改善という結果が得られるということが判明した。
【００５９】
上述の実施の形態では、記述子データベース１０に保存する前のＣＳＳ値に対して変換が適用される。上記とは別に、ＣＳＳ値をデータベース１０に保存してもよい。次いで、マッチング手順を行う前に検索処理の一部として変換を行ってもよい。
【００６０】
以上記載の実施の形態では変換はｙ座標値に対して適用される。しかし、ｘ座標値に対して変換を適用することもできる。
【００６１】
以上説明したようなシステムの構成要素は、ソフトウェアまたはハードウェアの形で設けることができる。コンピュータ・システムの形で本発明について説明したが、本発明は専用チップなどを用いて他の形で実現することもできる。
(本発明ではＣＳＳ表示を利用して)オブジェクトの２Ｄ形状を表す方法および２つの形状間の類似度を表す値を計算する方法を示す特定の例を示したが、同様の任意の適切な方法を用いることができる。
【００６２】
例えば、確認目的のためのオブジェクト画像のマッチングを行うために、またはフィルタリングを行うために本発明を用いることができる。
【特許請求の範囲】
【請求項１】
１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、
前記信号に基づいて曲率スケール空間（ＣＳＳ）における前記オブジェクトの輪郭のピークの縦座標値を複数導き出すステップ
を有し、
ＣＳＳ表示を導き出す方法として、２項フィルタが用いられる
ことを特徴とする方法。
【請求項２】
前記２項フィルタは、係数（１/４、１/２、１/４）を有する
ことを特徴とする方法。
【請求項３】
前記輪郭の表示に到達するために、前記縦座標値に対してスケーリングあるいは非線形変換を行うステップをさらに有する
ことを特徴とする方法。
【請求項４】
１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを検索する方法であって、
２次元の輪郭の形状のクエリを入力するステップと、
請求項１ないし３のいずれか１項に記載の方法を用いて前記輪郭の記述子を導き出すステップと、
請求項１ないし３のいずれか１項に記載の方法を用いて導出され、記憶された画像内のオブジェクトの記述子を取得し、前記クエリの記述子と、記憶されたオブジェクトに対するそれぞれの記述子とを比較するステップと、
前記クエリとの類似度を示す比較がなされたオブジェクトを含む画像に対応した、少なくとも１つの比較結果を選択し、表示するステップと
を有することを特徴とする方法。
【請求項５】
請求項１ないし４のいずれか１項に記載の方法を実行するように適合される画像中に現れるオブジェクトを表示する装置。
【請求項６】
請求項１ないし４のいずれか１項に記載の方法に従って作動するようにプログラムされた画像中に現れるオブジェクトを表示するコンピュータ・システム。
【請求項７】
請求項１ないし４のいずれか１項に記載の方法を実現するためのコンピュータで実行可能な処理ステップを保存するコンピュータ・プログラムまたはコンピュータ可読記憶媒体。
【請求項１】
１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、
前記信号に基づいて曲率スケール空間（ＣＳＳ）における前記オブジェクトの輪郭のピークの縦座標値を複数導き出すステップ
を有し、
ＣＳＳ表示を導き出す方法として、２項フィルタが用いられる
ことを特徴とする方法。
【請求項２】
前記２項フィルタは、係数（１/４、１/２、１/４）を有する
ことを特徴とする方法。
【請求項３】
前記輪郭の表示に到達するために、前記縦座標値に対してスケーリングあるいは非線形変換を行うステップをさらに有する
ことを特徴とする方法。
【請求項４】
１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを検索する方法であって、
２次元の輪郭の形状のクエリを入力するステップと、
請求項１ないし３のいずれか１項に記載の方法を用いて前記輪郭の記述子を導き出すステップと、
請求項１ないし３のいずれか１項に記載の方法を用いて導出され、記憶された画像内のオブジェクトの記述子を取得し、前記クエリの記述子と、記憶されたオブジェクトに対するそれぞれの記述子とを比較するステップと、
前記クエリとの類似度を示す比較がなされたオブジェクトを含む画像に対応した、少なくとも１つの比較結果を選択し、表示するステップと
を有することを特徴とする方法。
【請求項５】
請求項１ないし４のいずれか１項に記載の方法を実行するように適合される画像中に現れるオブジェクトを表示する装置。
【請求項６】
請求項１ないし４のいずれか１項に記載の方法に従って作動するようにプログラムされた画像中に現れるオブジェクトを表示するコンピュータ・システム。
【請求項７】
請求項１ないし４のいずれか１項に記載の方法を実現するためのコンピュータで実行可能な処理ステップを保存するコンピュータ・プログラムまたはコンピュータ可読記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−１００４６８（Ｐ２０１１−１００４６８Ａ）
【公開日】平成２３年５月１９日（２０１１．５．１９）
【国際特許分類】
【出願番号】特願２０１０−２６８５２２（Ｐ２０１０−２６８５２２）
【出願日】平成２２年１２月１日（２０１０．１２．１）
【分割の表示】特願２００１−５０８７８２（Ｐ２００１−５０８７８２）の分割
【原出願日】平成１２年７月３日（２０００．７．３）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
【公開日】平成２３年５月１９日（２０１１．５．１９）
【国際特許分類】
【出願日】平成２２年１２月１日（２０１０．１２．１）
【分割の表示】特願２００１−５０８７８２（Ｐ２００１−５０８７８２）の分割
【原出願日】平成１２年７月３日（２０００．７．３）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
[ Back to top ]