(57)【要約】      （修正有）【課題】マルチメディア・データベースに保存された画像のような静止画像またはビデオ画像中に現れるオブジェクトの表示に関し、特に、そのような表示を用いてオブジェクトを検索する方法及び装置を提供する。【解決手段】静止画像またはビデオ画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、オブジェクトの輪郭を平滑化することにより、オブジェクトの輪郭の曲率スケール空間(ＣＳＳ)表示を導き出すステップと、元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出すステップと、前記ＣＳＳ表示と前記追加パラメータとを関連させて前記オブジェクトの形状記述子を形成するステップとを有する。【選択図】図１
2011100465.tif 000002
【特許請求の範囲】
【請求項１】
１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、
オブジェクトの輪郭を平滑化することにより、オブジェクトの輪郭の曲率スケール空間(ＣＳＳ)表示を導き出すステップと、
元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出すステップと、
前記ＣＳＳ表示と前記追加パラメータとを関連させて前記オブジェクトの形状記述子を形成するステップと
を有することを特徴とする方法。
【請求項２】
前記追加パラメータは、ＣＳＳ画像のピークに対応する前記平滑化された輪郭の真円度である
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記追加パラメータは、前記ＣＳＳ画像の最も高いピークに対応する前記平滑化された輪郭の真円度である
ことを特徴とする請求項２に記載の方法。
【請求項４】
１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れる複数のオブジェクトを表示する方法であって、
各オブジェクトの輪郭について、曲率スケール空間(ＣＳＳ)画像内に少なくとも１つのピークが存在する場合、およびスケール空間画像内に少なくとも１つのピークが存在する場合に、請求項１に記載の方法を用いて形状記述子を導き出すステップと、
曲率スケール空間(ＣＳＳ)画像内にピークが存在しない場合に、前記オブジェクトの輪郭のＣＳＳ表現および元のオブジェクトの輪郭の真円度の少なくとも一方を含む形状記述子を導き出すステップと
を有することを特徴とする方法。
【請求項５】
請求項１乃至４のいずれか１つに記載の方法を実行するように適合される画像中に現れるオブジェクトを表示する装置。
【請求項６】
１つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトの輪郭の曲率スケール空間(ＣＳＳ)表示を導き出す手段と、
元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出す手段と、
前記ＣＳＳ表示と前記追加パラメータとを関連させて前記オブジェクトの形状記述子を形成する手段と
を有することを特徴とする請求項５に記載の装置。
【請求項７】
画像および／または形状記述子を記憶する記憶手段をさらに有することを特徴とする請求項６に記載の方法。
【請求項８】
請求項１乃至４のいずれか１つに記載の方法を実現するための画像中に現れるオブジェクトを表示するコンピュータ・プログラム。
【請求項９】
請求項１乃至４のいずれか１つに記載の方法に従って作動する画像中に現れるオブジェクトを表示するコンピュータ・システム・プログラム。
【請求項１０】
請求項１乃至４のいずれか１つに記載の方法を実行するためのコンピュータによって実行可能な処理を保存するコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索を目的とする、マルチメディア・データベースに保存された画像のような静止画像またはビデオ画像中に現れるオブジェクトの表示に関し、特に、そのような表示を用いてオブジェクトを検索する方法及び装置に関する。
【背景技術】
【０００２】
ビデオ・ライブラリの画像のようなアプリケーションでは、ビデオ画像あるいは静止画像中に現れるオブジェクトの輪郭や形状またはオブジェクトの一部の効率的な表示および保存を行うことが望ましい。形状ベースの索引付けと検索を行うための公知の手法では曲率スケール空間(ＣＳＳ)表示が用いられる。ＣＳＳの詳細については、論文「曲率スケール空間によるロバストで効率的な形状索引付け」(英国マシーン・ビジョン会報pp.５３〜６２、エジンバラ、英国、１９９６年)ならびに「曲率スケール空間を用いる形状内容による画像データベースの索引付け」(インテリジェント・データベースに関するＩＥＥ専門家会議会報、ロンドン、１９９６年)の中で入手することができる。両論文ともMokhtarian、S.AbbasiならびにJ.Kittlerによるものであり、その内容は本明細書中に参考文献として取り入れられている。
【０００３】
ＣＳＳ表示では、オブジェクトの輪郭を求めるために曲率関数が使用され、輪郭上の任意の点から表示が開始される。形状を平滑化する一連の変形を行うことにより輪郭の形状を展開しながら、曲率関数が検討される。さらに具体的には、ガウスフィルタの族と共に畳み込まれた曲率関数の導関数のゼロ・クロスが計算される。曲率スケール空間として周知のように、ゼロ・クロスはグラフ上にプロットされる。但し、ｘ軸は曲線の正規化された弧長であり、ｙ軸は展開パラメータ、特に、適用フィルタのパラメータである。グラフ上のプロットは輪郭の特徴を示すループを形成する。オブジェクトの輪郭の各凸状または凹状を成す部分はＣＳＳ画像におけるループに対応する。ＣＳＳ画像において最も突起したループのピークの縦座標は輪郭の表示として利用される。
【０００４】
入力オブジェクトの形状に一致する、データベース中の保存画像のオブジェクトを検索するために、入力形状のＣＳＳ表示が計算される。マッチング・アルゴリズムを用いて、それぞれのＣＳＳ画像のピークの位置および高さを比較することにより、入力形状と保存形状との間の類似度が判定される。
【０００５】
上述の最初の論文によれば、２つの追加パラメータ(元の形状の真円度と離心率)を用いて、これと著しく異なる真円度と離心率パラメータを持つ形状がマッチング処理から除外されることが知られている。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述のような表示に関する問題点として、往々にして検索精度が低くなる場合があり、特に、少数の凹状または凸状を持つ曲線について検索精度が低くなるという点が挙げられる。特に、この表示は種々の凸状の曲線の区別を行うことができない。
【０００７】
本発明の１つの態様は“プロトタイプ輪郭の形状”の形状について記述する追加手段を導入することである。好適にはプロトタイプの輪郭の形状は以下のように定義することが望ましい：
１)  輪郭中に凹凸が存在しない(すなわちＣＳＳ画像にピークが存在しない)場合には、元の形状。
２)  ＣＳＳ画像中の最も高いピークに等しい平滑化を行った後の形状の輪郭。
【０００８】
プロトタイプ輪郭の形状は常に凸状であることに留意されたい。
例えば、MK.HUの論文“モーメント不変量による視覚パターン認識”(情報理論に関するＩＥＥＥ処理、Ｖｏｌ.ＩＴ−８、１７９〜１８１、１９６２年)に記載されているような領域モーメントに基づく不変量によってプロトタイプ輪郭の形状を記述してもよい。上記論文の内容は本明細書に参考文献として取り入れられている。あるいは、Cho-Huak Theの論文“モーメント法による画像分析について”(パターン分析およびマシーン・インテリジェンスに関するＩＥＥＥ処理、Ｖｏｌ.１０. Ｎｏ.４、１９８８年７月)に記載されているようなフーリエ記述子あるいは離心率、真円度などのようなパラメータを用いてプロトタイプ輪郭の形状を記述してもよい。この論文の内容も本明細書に参考文献として取り入れられている。上述の公知の方法では離心率と真円度は元の形状に対してしか使用されない。本発明では、曲線について異なる離心率と真円度が“プロトタイプ形状”に対して用いられる。この形状は少なくとも１つのＣＳＳピークを有する。もう１つの違いは、公知の方法による離心率と真円度を用いて、類似度マッチングからある一定の形状が除外されるという点である。本発明では(ＣＳＳピークに加えて)離心率と真円度とを用いて類似度測定値が導き出される。最後に、マッチング処理に用いる追加パラメータをモーメント不変量、フーリエ記述子およびゼルニック(Zernicke)モーメントに対して拡張する。
【０００９】
本発明の結果として検索精度の改善を行うことができる。
【課題を解決するための手段】
【００１０】
この発明に係る請求項１に記載の画像中に現れるオブジェクトを表示する方法は、１つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトを表示する方法であって、オブジェクトの輪郭を平滑化することにより、オブジェクトの輪郭の曲率スケール空間(ＣＳＳ)表示を導き出すステップと、元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出すステップと、ＣＳＳ表示と追加パラメータとを関連させてオブジェクトの形状記述子を形成するステップとを有する。
【００１１】
この発明に係る請求項２に記載の画像中に現れるオブジェクトを表示する方法は、追加パラメータは、ＣＳＳ画像のピークに対応する平滑化された輪郭の真円度である。
【００１２】
この発明に係る請求項３に記載の画像中に現れるオブジェクトを表示する方法は、追加パラメータは、ＣＳＳ画像の最も高いピークに対応する平滑化された輪郭の真円度である。
【００１３】
この発明に係る請求項４に記載の画像中に現れるオブジェクトを表示する方法は、１つの画像または一連の画像に対応する信号を処理することにより、画像中に現れる複数のオブジェクトを表示する方法であって、各オブジェクトの輪郭について、曲率スケール空間(ＣＳＳ)画像内に少なくとも１つのピークが存在する場合、およびスケール空間画像内に少なくとも１つのピークが存在する場合に、請求項１に記載の方法を用いて形状記述子を導き出すステップと、曲率スケール空間(ＣＳＳ)画像内にピークが存在しない場合に、オブジェクトの輪郭のＣＳＳ表現および元のオブジェクトの輪郭の真円度の少なくとも一方を含む形状記述子を導き出すステップとを有する。
【００１４】
この発明に係る請求項５に記載の画像中に現れるオブジェクトを表示する装置は、請求項１乃至４のいずれか１つに記載の方法を実行するように適合される。
【００１５】
この発明に係る請求項６に記載の画像中に現れるオブジェクトを表示する装置は、１つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトの輪郭の曲率スケール空間(ＣＳＳ)表示を導き出す手段と、元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出す手段と、ＣＳＳ表示と追加パラメータとを関連させてオブジェクトの形状記述子を形成する手段とを有する。
【００１６】
この発明に係る請求項７に記載の画像中に現れるオブジェクトを表示する装置は、画像および／または形状記述子を記憶する記憶手段をさらに有する。
【００１７】
この発明に係る請求項８に記載の画像中に現れるオブジェクトを表示するコンピュータ・プログラムは、請求項１乃至４のいずれか１つに記載の方法を実現する。
【００１８】
この発明に係る請求項９に記載の画像中に現れるオブジェクトを表示するコンピュータ・システム・プログラムは、請求項１乃至４のいずれか１つに記載の方法に従って作動する。
【００１９】
この発明に係る請求項１０に記載のコンピュータ可読記憶媒体は、請求項１乃至４のいずれか１つに記載の方法を実行するためのコンピュータによって実行可能な処理を保存する。
【発明の効果】
【００２０】
本発明によるシステムは例えば画像ライブラリ中に設けることができる。或いは、データベースは、インターネットのようなネットワークにより電話線のような一時的リンクによって制御装置と接続し、システムの制御装置から遠隔地に配置することができる。例えば、画像データベースおよび記述子データベースは永久記憶装置またはＲＯＭやＤＶＤのような携帯用記憶媒体中に設けることができる。
【図面の簡単な説明】
【００２１】
【図１】ビデオ・データベース・システムを示すブロック図、
【図２】あるオブジェクトの輪郭を示す図、
【図３】図２の輪郭を示すＣＳＳ表示の図である。
【発明を実施するための形態】
【００２２】
添付図面を参照して本発明の実施の形態について説明する。
実施の形態１．
図１は、本発明の実施の形態によるコンピュータ処理が行われたビデオ・データベース・システムを図示する。このシステムには、コンピュータの形の制御装置２、モニターの形の表示装置４、マウスの形のポインティング・デバイス６、保存された静止画像とビデオ画像とを含む画像データベース８および画像データベース８に保存された画像中に現れるオブジェクトまたはオブジェクトのいくつかの部分の記述子を保存する記述子データベース１０が含まれる。
【００２３】
画像データベースの画像中に現れる興味のある各オブジェクトの形状を表す記述子は、制御装置２によって導き出され、記述子データベース１０に保存される。制御装置２は、以下に説明するような方法を実行する適切なプログラムの制御によって動作して記述子を導き出す。
【００２４】
第一に、所定のオブジェクトの輪郭について、この輪郭のＣＳＳ表示が導き出される。上述の論文の１つに記載されているような周知の方法を用いてこのＣＳＳ表示が行われる。
【００２５】
さらに具体的には、この輪郭はΨ＝{(x(u),y(u),u∈[0,1]}によって表される(ただし、uは正規化された弧長パラメータである)。
【００２６】
この輪郭は、ＩＤガウスカーネルｇ(ｕ,ρ)を用いて畳み込みを行う(convolve)ことにより平滑化され、ρの変化として展開(evolving)曲線の曲率ゼロ・クロスが調べられる。ゼロクロスは曲率を表す下記の式を用いて特定される。
【００２７】
【数１】
2011100465.tif 000003
【００２８】
但し、
【００２９】
【数２】
2011100465.tif 000004
【００３０】
かつ、
【００３１】
【数３】
2011100465.tif 000005
【００３２】
上記で、＊は畳み込みを表し、添え字は導関数を表す。
曲率ゼロ・クロスの数はρの変化につれて変化し、ρが十分に高いときΨはゼロ・クロスの凸状の曲線となる。
【００３３】
ゼロクロス・ポイント(u、ρ)はＣＳＳ画像空間として知られるグラフ上にプロットされる。この結果元の輪郭の特徴を示す曲線が生じる。この特徴を示す曲線のピークが特定され、対応する縦座標が抽出され保存される。一般に上記の結果、ｎ個の座標の対((x１, y１)、(x２, y２)、...(xn, yn)の組(ただし、ｎはピークの数、xiはｉ番目のピークの弧長の位置、yiはピークの高さである)が与えられる。これらのピークの縦座標によってＣＳＳ表示ピークが構成される。
【００３４】
ＣＳＳ表示に加えて、さらなるパラメータが形状と関連付けられ、形状記述子が生成される。本実施の形態では、追加パラメータは形状の“プロトタイプ領域”の離心率と真円度であり、この場合この形状の“プロトタイプ領域”は最終平滑化ステップ後の、すなわち最も高いピーク値ρに等しい点における形状の輪郭である。プロトタイプ領域について他のρ値を選択してもよい。この結果、形の中にＳ字形を表す形状記述子｛ＥＰＲ、ＣＰＲ、ピーク｝が生じる(但し、ＥＰＲはプロトタイプ領域の離心率、ＣＰＲはプロトタイプ領域の真円度、ＰＥＡＫＳはＣＳＳ表示を表す)。
【００３５】
本発明の実施の形態１に準拠する画像中のオブジェクトの検索方法について説明する。
【００３６】
本明細書では、図１のシステムの記述子データベース１０中に上述の方法に従って導き出された形状記述子が保存される。
【００３７】
ポインティング・デバイスを用いてディスプレイにオブジェクトの輪郭を描くことによりユーザーは検索を開始する。次いで、制御装置２は上述の方法で、入力輪郭を示す形状記述子を導き出す。次いで、制御装置はデータベースに保存されている各形状記述子を用いてマッチング比較を行う。
【００３８】
入力輪郭の形状Ｓ１を保存形状Ｓ２と比較すると仮定すると、Ｓ１とＳ２はそれぞれの記述子が下記のようになる：
Ｓ１：(ＥＰＲ１、ＣＰＲ１、ＰＥＡＫＳ１)
Ｓ２：(ＥＰＲ２、ＣＰＲ２、ＰＥＡＫＳ２)
【００３９】
但し、ＥＰＲはプロトタイプ領域の離心率を意味し、ＣＰＲはプロトタイプ領域の真円度を意味し、ＰＥＡＫＳはＣＳＳ画像中のピーク座標の設定値を意味する(この設定値は空であってもよい)。２つの形状間の類似度測定値は以下のように計算される。
【００４０】
【数４】
2011100465.tif 000006
【００４１】
但し、ａとｂは２つの係数であり、ＳＭは２組のピーク[1]値に関して定義された標準的類似度測定値であり、ａｂｓは絶対値を示す。ＳＭは、上述の論文に記載されているような公知のマッチング・アルゴリズムを用いて計算される。このマッチング処理について以下手短に説明する。
【００４２】
２つの閉鎖した輪郭の形状、画像曲線Ψ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)だけを取り除く。
上記条件が当てはまらない(マッチしなかった画像ピークしか存在しない、またはマッチしなかったモデル・ピークしか存在しない)場合、マッチしないままの状態に放置する。
【００５１】
マッチしなかった画像ピークまたはモデル・ピークの最も高い高さとしてマッチのコストを定義しリストからピークを取り除く。
【００５２】
８．  ７でノードを拡大した後、画像リストおよびモデル・リストの双方にマッチしないピークが存在しない場合マッチング処理は終了する。このノードのコストは画像とモデル曲線間の類似度測定値である。ピークが存在する場合には、ポイント７へ戻り最低コストのノードを拡大する。
【００５３】
画像曲線ピーク値とモデル曲線ピーク値とを交換して上記手順を繰り返す。最終マッチング値はこれら２つのピーク値のうちの低い方の値である。
【００５４】
データベースの各モデルについて上記ステップを繰り返す。
【００５５】
マッチング比較から結果として生じる類似度測定値はソートされ、次いで、最も接近したマッチを示す類似度測定値を持つ記述子に対応するオブジェクト(すなわち本発明で最低の類似度測定値)がユーザーに対して表示装置４上に表示される。表示対象のオブジェクト数はユーザーが予め設定するか選択することができる。
【００５６】
代替の実施の形態では、様々なパラメータを用いて“プロトタイプ領域”の形状について記述することができる。例えば曲線の３つのフーリエ係数を使用することができる。類似度測定値は以下のように定義することができる。すなわち：
【００５７】
【数５】
2011100465.tif 000007
【００５８】
但し、ＥＵＣは、モデルと画像の形状を示す３つの主要なフーリエ係数から形成されるベクトルＦ１とＦ２間のユークリッド距離であり、ＳＭはＣＳＳピークの類似度測定値を表し、ほぼ上述のような方法を用いて計算される。
【００５９】
以上説明したようなシステムの構成要素は、ソフトウェアまたはハードウェアの形で設けることができる。コンピュータ・システムの形で本発明について説明したが、本発明は専用チップなどを用いて他の形で実現することもできる。
【００６０】
オブジェクトの２Ｄ形状を表す方法および２つの形状間の類似度を表す値を計算する方法を示す特定の例を示したが、同様の任意の適切な方法を用いることができる。
【００６１】
例えば、確認目的のためにオブジェクト画像のマッチングを行うために、またはフィルタリングを行うために本発明を用いることができる。
【図１】
2011100465.tif 000008
【図２】
2011100465.tif 000009
【図３】
2011100465.tif 000010