説明

画像中に現れるオブジェクトを表示する方法、その装置、コンピュータ・プログラム、コンピュータ・システム、及びコンピュータ可読記憶媒体

【課題】マルチメディア・データベースに保存された画像のような静止画像またはビデオ画像中に現れるオブジェクトの表示に関し、特に、そのような表示を用いてオブジェクトを検索する方法及び装置を提供する。
【解決手段】静止画像またはビデオ画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、オブジェクトの輪郭を平滑化することにより、オブジェクトの輪郭の曲率スケール空間(CSS)表示を導き出すステップと、元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出すステップと、前記CSS表示と前記追加パラメータとを関連させて前記オブジェクトの形状記述子を形成するステップとを有する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、検索を目的とする、マルチメディア・データベースに保存された画像のような静止画像またはビデオ画像中に現れるオブジェクトの表示に関し、特に、そのような表示を用いてオブジェクトを検索する方法及び装置に関する。
【背景技術】
【0002】
ビデオ・ライブラリの画像のようなアプリケーションでは、ビデオ画像あるいは静止画像中に現れるオブジェクトの輪郭や形状またはオブジェクトの一部の効率的な表示および保存を行うことが望ましい。形状ベースの索引付けと検索を行うための公知の手法では曲率スケール空間(CSS)表示が用いられる。CSSの詳細については、論文「曲率スケール空間によるロバストで効率的な形状索引付け」(英国マシーン・ビジョン会報pp.53〜62、エジンバラ、英国、1996年)ならびに「曲率スケール空間を用いる形状内容による画像データベースの索引付け」(インテリジェント・データベースに関するIEE専門家会議会報、ロンドン、1996年)の中で入手することができる。両論文ともMokhtarian、S.AbbasiならびにJ.Kittlerによるものであり、その内容は本明細書中に参考文献として取り入れられている。
【0003】
CSS表示では、オブジェクトの輪郭を求めるために曲率関数が使用され、輪郭上の任意の点から表示が開始される。形状を平滑化する一連の変形を行うことにより輪郭の形状を展開しながら、曲率関数が検討される。さらに具体的には、ガウスフィルタの族と共に畳み込まれた曲率関数の導関数のゼロ・クロスが計算される。曲率スケール空間として周知のように、ゼロ・クロスはグラフ上にプロットされる。但し、x軸は曲線の正規化された弧長であり、y軸は展開パラメータ、特に、適用フィルタのパラメータである。グラフ上のプロットは輪郭の特徴を示すループを形成する。オブジェクトの輪郭の各凸状または凹状を成す部分はCSS画像におけるループに対応する。CSS画像において最も突起したループのピークの縦座標は輪郭の表示として利用される。
【0004】
入力オブジェクトの形状に一致する、データベース中の保存画像のオブジェクトを検索するために、入力形状のCSS表示が計算される。マッチング・アルゴリズムを用いて、それぞれのCSS画像のピークの位置および高さを比較することにより、入力形状と保存形状との間の類似度が判定される。
【0005】
上述の最初の論文によれば、2つの追加パラメータ(元の形状の真円度と離心率)を用いて、これと著しく異なる真円度と離心率パラメータを持つ形状がマッチング処理から除外されることが知られている。
【発明の概要】
【発明が解決しようとする課題】
【0006】
上述のような表示に関する問題点として、往々にして検索精度が低くなる場合があり、特に、少数の凹状または凸状を持つ曲線について検索精度が低くなるという点が挙げられる。特に、この表示は種々の凸状の曲線の区別を行うことができない。
【0007】
本発明の1つの態様は“プロトタイプ輪郭の形状”の形状について記述する追加手段を導入することである。好適にはプロトタイプの輪郭の形状は以下のように定義することが望ましい:
1) 輪郭中に凹凸が存在しない(すなわちCSS画像にピークが存在しない)場合には、元の形状。
2) CSS画像中の最も高いピークに等しい平滑化を行った後の形状の輪郭。
【0008】
プロトタイプ輪郭の形状は常に凸状であることに留意されたい。
例えば、MK.HUの論文“モーメント不変量による視覚パターン認識”(情報理論に関するIEEE処理、Vol.IT−8、179〜181、1962年)に記載されているような領域モーメントに基づく不変量によってプロトタイプ輪郭の形状を記述してもよい。上記論文の内容は本明細書に参考文献として取り入れられている。あるいは、Cho-Huak Theの論文“モーメント法による画像分析について”(パターン分析およびマシーン・インテリジェンスに関するIEEE処理、Vol.10. No.4、1988年7月)に記載されているようなフーリエ記述子あるいは離心率、真円度などのようなパラメータを用いてプロトタイプ輪郭の形状を記述してもよい。この論文の内容も本明細書に参考文献として取り入れられている。上述の公知の方法では離心率と真円度は元の形状に対してしか使用されない。本発明では、曲線について異なる離心率と真円度が“プロトタイプ形状”に対して用いられる。この形状は少なくとも1つのCSSピークを有する。もう1つの違いは、公知の方法による離心率と真円度を用いて、類似度マッチングからある一定の形状が除外されるという点である。本発明では(CSSピークに加えて)離心率と真円度とを用いて類似度測定値が導き出される。最後に、マッチング処理に用いる追加パラメータをモーメント不変量、フーリエ記述子およびゼルニック(Zernicke)モーメントに対して拡張する。
【0009】
本発明の結果として検索精度の改善を行うことができる。
【課題を解決するための手段】
【0010】
この発明に係る請求項1に記載の画像中に現れるオブジェクトを表示する方法は、1つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトを表示する方法であって、オブジェクトの輪郭を平滑化することにより、オブジェクトの輪郭の曲率スケール空間(CSS)表示を導き出すステップと、元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出すステップと、CSS表示と追加パラメータとを関連させてオブジェクトの形状記述子を形成するステップとを有する。
【0011】
この発明に係る請求項2に記載の画像中に現れるオブジェクトを表示する方法は、追加パラメータは、CSS画像のピークに対応する平滑化された輪郭の真円度である。
【0012】
この発明に係る請求項3に記載の画像中に現れるオブジェクトを表示する方法は、追加パラメータは、CSS画像の最も高いピークに対応する平滑化された輪郭の真円度である。
【0013】
この発明に係る請求項4に記載の画像中に現れるオブジェクトを表示する方法は、1つの画像または一連の画像に対応する信号を処理することにより、画像中に現れる複数のオブジェクトを表示する方法であって、各オブジェクトの輪郭について、曲率スケール空間(CSS)画像内に少なくとも1つのピークが存在する場合、およびスケール空間画像内に少なくとも1つのピークが存在する場合に、請求項1に記載の方法を用いて形状記述子を導き出すステップと、曲率スケール空間(CSS)画像内にピークが存在しない場合に、オブジェクトの輪郭のCSS表現および元のオブジェクトの輪郭の真円度の少なくとも一方を含む形状記述子を導き出すステップとを有する。
【0014】
この発明に係る請求項5に記載の画像中に現れるオブジェクトを表示する装置は、請求項1乃至4のいずれか1つに記載の方法を実行するように適合される。
【0015】
この発明に係る請求項6に記載の画像中に現れるオブジェクトを表示する装置は、1つの画像または一連の画像に対応する信号を処理することにより、画像中に現れるオブジェクトの輪郭の曲率スケール空間(CSS)表示を導き出す手段と、元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出す手段と、CSS表示と追加パラメータとを関連させてオブジェクトの形状記述子を形成する手段とを有する。
【0016】
この発明に係る請求項7に記載の画像中に現れるオブジェクトを表示する装置は、画像および/または形状記述子を記憶する記憶手段をさらに有する。
【0017】
この発明に係る請求項8に記載の画像中に現れるオブジェクトを表示するコンピュータ・プログラムは、請求項1乃至4のいずれか1つに記載の方法を実現する。
【0018】
この発明に係る請求項9に記載の画像中に現れるオブジェクトを表示するコンピュータ・システム・プログラムは、請求項1乃至4のいずれか1つに記載の方法に従って作動する。
【0019】
この発明に係る請求項10に記載のコンピュータ可読記憶媒体は、請求項1乃至4のいずれか1つに記載の方法を実行するためのコンピュータによって実行可能な処理を保存する。
【発明の効果】
【0020】
本発明によるシステムは例えば画像ライブラリ中に設けることができる。或いは、データベースは、インターネットのようなネットワークにより電話線のような一時的リンクによって制御装置と接続し、システムの制御装置から遠隔地に配置することができる。例えば、画像データベースおよび記述子データベースは永久記憶装置またはROMやDVDのような携帯用記憶媒体中に設けることができる。
【図面の簡単な説明】
【0021】
【図1】ビデオ・データベース・システムを示すブロック図、
【図2】あるオブジェクトの輪郭を示す図、
【図3】図2の輪郭を示すCSS表示の図である。
【発明を実施するための形態】
【0022】
添付図面を参照して本発明の実施の形態について説明する。
実施の形態1.
図1は、本発明の実施の形態によるコンピュータ処理が行われたビデオ・データベース・システムを図示する。このシステムには、コンピュータの形の制御装置2、モニターの形の表示装置4、マウスの形のポインティング・デバイス6、保存された静止画像とビデオ画像とを含む画像データベース8および画像データベース8に保存された画像中に現れるオブジェクトまたはオブジェクトのいくつかの部分の記述子を保存する記述子データベース10が含まれる。
【0023】
画像データベースの画像中に現れる興味のある各オブジェクトの形状を表す記述子は、制御装置2によって導き出され、記述子データベース10に保存される。制御装置2は、以下に説明するような方法を実行する適切なプログラムの制御によって動作して記述子を導き出す。
【0024】
第一に、所定のオブジェクトの輪郭について、この輪郭のCSS表示が導き出される。上述の論文の1つに記載されているような周知の方法を用いてこのCSS表示が行われる。
【0025】
さらに具体的には、この輪郭はΨ={(x(u),y(u),u∈[0,1]}によって表される(ただし、uは正規化された弧長パラメータである)。
【0026】
この輪郭は、IDガウスカーネルg(u,ρ)を用いて畳み込みを行う(convolve)ことにより平滑化され、ρの変化として展開(evolving)曲線の曲率ゼロ・クロスが調べられる。ゼロクロスは曲率を表す下記の式を用いて特定される。
【0027】
【数1】

【0028】
但し、
【0029】
【数2】

【0030】
かつ、
【0031】
【数3】

【0032】
上記で、*は畳み込みを表し、添え字は導関数を表す。
曲率ゼロ・クロスの数はρの変化につれて変化し、ρが十分に高いときΨはゼロ・クロスの凸状の曲線となる。
【0033】
ゼロクロス・ポイント(u、ρ)はCSS画像空間として知られるグラフ上にプロットされる。この結果元の輪郭の特徴を示す曲線が生じる。この特徴を示す曲線のピークが特定され、対応する縦座標が抽出され保存される。一般に上記の結果、n個の座標の対((x1, y1)、(x2, y2)、...(xn, yn)の組(ただし、nはピークの数、xiはi番目のピークの弧長の位置、yiはピークの高さである)が与えられる。これらのピークの縦座標によってCSS表示ピークが構成される。
【0034】
CSS表示に加えて、さらなるパラメータが形状と関連付けられ、形状記述子が生成される。本実施の形態では、追加パラメータは形状の“プロトタイプ領域”の離心率と真円度であり、この場合この形状の“プロトタイプ領域”は最終平滑化ステップ後の、すなわち最も高いピーク値ρに等しい点における形状の輪郭である。プロトタイプ領域について他のρ値を選択してもよい。この結果、形の中にS字形を表す形状記述子{EPR、CPR、ピーク}が生じる(但し、EPRはプロトタイプ領域の離心率、CPRはプロトタイプ領域の真円度、PEAKSはCSS表示を表す)。
【0035】
本発明の実施の形態1に準拠する画像中のオブジェクトの検索方法について説明する。
【0036】
本明細書では、図1のシステムの記述子データベース10中に上述の方法に従って導き出された形状記述子が保存される。
【0037】
ポインティング・デバイスを用いてディスプレイにオブジェクトの輪郭を描くことによりユーザーは検索を開始する。次いで、制御装置2は上述の方法で、入力輪郭を示す形状記述子を導き出す。次いで、制御装置はデータベースに保存されている各形状記述子を用いてマッチング比較を行う。
【0038】
入力輪郭の形状S1を保存形状S2と比較すると仮定すると、S1とS2はそれぞれの記述子が下記のようになる:
S1:(EPR1、CPR1、PEAKS1)
S2:(EPR2、CPR2、PEAKS2)
【0039】
但し、EPRはプロトタイプ領域の離心率を意味し、CPRはプロトタイプ領域の真円度を意味し、PEAKSはCSS画像中のピーク座標の設定値を意味する(この設定値は空であってもよい)。2つの形状間の類似度測定値は以下のように計算される。
【0040】
【数4】

【0041】
但し、aとbは2つの係数であり、SMは2組のピーク[1]値に関して定義された標準的類似度測定値であり、absは絶対値を示す。SMは、上述の論文に記載されているような公知のマッチング・アルゴリズムを用いて計算される。このマッチング処理について以下手短に説明する。
【0042】
2つの閉鎖した輪郭の形状、画像曲線Ψiとモデル曲線Ψmおよびそれらの曲線のピークのそれぞれの設定値{(xi1, yi1),(xi2, yi2),..,(xin, yin)}と{(xm1, ym1), (xm2, ym2),..,(xmn, ymn)}が与えられれば、類似度測定値が計算される。類似度測定値は、画像中のピークとモデル中のピークのマッチングの総コストとして定義される。総コストを最少化するマッチングはダイナミック・プログラミングを用いて計算される。アルゴリズムによって、モデルから得たピークが画像から得たピークに再帰的にマッチされ、このようなマッチの各々のコスト計算が行われる。各モデルのピークを唯一の画像ピークとマッチさせることができ、各画像ピークを唯一のモデル・ピークとマッチさせることができる。モデルおよび/または画像ピークのなかにはマッチしないままのものがある場合もあり、各マッチしないピークについては追加のペナルティ・コストが存在する。2つのピークの水平距離が0.2未満の場合、2つのピークをマッチすることができる。マッチのコストは2つのマッチしたピーク間の直線の長さである。マッチしなかったピークのコストはその高さである。
【0043】
更に詳述すれば、アルゴリズムは、ノードがマッチしたピークに対応するツリー状の構造を作成し拡張することにより機能する。
【0044】
1. 画像(xik, yik)の最大値とモデル(xir, yir)の最大値とから成る開始ノードを作成する。
【0045】
2. 画像ピークの最大値の80%以内の各残りのモデル・ピークについて追加の開始ノードを作成する。
【0046】
3. 1および2で作成した各開始ノードのコストを、この開始ノードとリンクした画像ピークおよびモデル・ピークのy座標の差の絶対値に初期化する。
【0047】
4. 3の各開始ノードについて、この開始ノードでマッチしたモデル・ピークと画像ピークのx(水平)座標の差として定義するCSSシフト・パラメータアルファを計算する。シフト・パラメータは各ノードについて異なるものとなる。
【0048】
5. 各開始ノードについて、モデル・ピークのリストおよび画像ピークのリストを作成する。このリストにはどのピークがまだマッチしていないかに関する情報が含まれる。各開始ノードについて、“マッチしたもの”としてこのノードでマッチしたピークにマークをつけ、他のすべてのピークには“マッチしなかったもの”としてマークをつける。
【0049】
6. ポイント8の条件が満たされるまで、最低コストのノードを再帰的に拡大する(ステップ1〜6で作成した各ノードから始めて、各ノードの子ノードが後に続く)。ノードを拡大するために以下の手順を用いる。
【0050】
7. ノードの拡大:
マッチしないままになっている少なくとも1つの画像と1つのモデル・ピークが存在する場合、マッチしない最も大きなスケール画像曲線CSSの最大値(xip, yip)を選択する。(ステップ4で計算した)開始ノード・シフト・パラメータを適用して選択した最大値をモデルCSS画像に写像し、選択されたピークは座標(xip-alpha, yip)を持つことになる。マッチしない最も近いモデル曲線ピーク(xms, yms)を決定する。2つのピーク間の水平距離が0.2未満(すなわち|xip-alpha-xms|<0.2)である場合、2つのピークをマッチさせ、2つのピーク間の直線の長さとしてマッチのコストを定義する。そのノードの総コストにマッチのコストを加える。マッチしたピークに“マッチした”ものとしてマークをつけることによりそれぞれのリストからマッチしたピークを取り除く。2つのピーク間の水平距離が0.2より大きい場合、画像ピーク(xip, yip)はマッチすることはできない。その場合総コストに画像ピークの高さyipを加え、“マッチした”ものとしてそのピークにマークをつけることにより画像ピーク・リストからピーク(xip, yip)だけを取り除く。
上記条件が当てはまらない(マッチしなかった画像ピークしか存在しない、またはマッチしなかったモデル・ピークしか存在しない)場合、マッチしないままの状態に放置する。
【0051】
マッチしなかった画像ピークまたはモデル・ピークの最も高い高さとしてマッチのコストを定義しリストからピークを取り除く。
【0052】
8. 7でノードを拡大した後、画像リストおよびモデル・リストの双方にマッチしないピークが存在しない場合マッチング処理は終了する。このノードのコストは画像とモデル曲線間の類似度測定値である。ピークが存在する場合には、ポイント7へ戻り最低コストのノードを拡大する。
【0053】
画像曲線ピーク値とモデル曲線ピーク値とを交換して上記手順を繰り返す。最終マッチング値はこれら2つのピーク値のうちの低い方の値である。
【0054】
データベースの各モデルについて上記ステップを繰り返す。
【0055】
マッチング比較から結果として生じる類似度測定値はソートされ、次いで、最も接近したマッチを示す類似度測定値を持つ記述子に対応するオブジェクト(すなわち本発明で最低の類似度測定値)がユーザーに対して表示装置4上に表示される。表示対象のオブジェクト数はユーザーが予め設定するか選択することができる。
【0056】
代替の実施の形態では、様々なパラメータを用いて“プロトタイプ領域”の形状について記述することができる。例えば曲線の3つのフーリエ係数を使用することができる。類似度測定値は以下のように定義することができる。すなわち:
【0057】
【数5】

【0058】
但し、EUCは、モデルと画像の形状を示す3つの主要なフーリエ係数から形成されるベクトルF1とF2間のユークリッド距離であり、SMはCSSピークの類似度測定値を表し、ほぼ上述のような方法を用いて計算される。
【0059】
以上説明したようなシステムの構成要素は、ソフトウェアまたはハードウェアの形で設けることができる。コンピュータ・システムの形で本発明について説明したが、本発明は専用チップなどを用いて他の形で実現することもできる。
【0060】
オブジェクトの2D形状を表す方法および2つの形状間の類似度を表す値を計算する方法を示す特定の例を示したが、同様の任意の適切な方法を用いることができる。
【0061】
例えば、確認目的のためにオブジェクト画像のマッチングを行うために、またはフィルタリングを行うために本発明を用いることができる。

【特許請求の範囲】
【請求項1】
1つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトを表示する方法であって、
オブジェクトの輪郭を平滑化することにより、オブジェクトの輪郭の曲率スケール空間(CSS)表示を導き出すステップと、
元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出すステップと、
前記CSS表示と前記追加パラメータとを関連させて前記オブジェクトの形状記述子を形成するステップと
を有することを特徴とする方法。
【請求項2】
前記追加パラメータは、CSS画像のピークに対応する前記平滑化された輪郭の真円度である
ことを特徴とする請求項1に記載の方法。
【請求項3】
前記追加パラメータは、前記CSS画像の最も高いピークに対応する前記平滑化された輪郭の真円度である
ことを特徴とする請求項2に記載の方法。
【請求項4】
1つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れる複数のオブジェクトを表示する方法であって、
各オブジェクトの輪郭について、曲率スケール空間(CSS)画像内に少なくとも1つのピークが存在する場合、およびスケール空間画像内に少なくとも1つのピークが存在する場合に、請求項1に記載の方法を用いて形状記述子を導き出すステップと、
曲率スケール空間(CSS)画像内にピークが存在しない場合に、前記オブジェクトの輪郭のCSS表現および元のオブジェクトの輪郭の真円度の少なくとも一方を含む形状記述子を導き出すステップと
を有することを特徴とする方法。
【請求項5】
請求項1乃至4のいずれか1つに記載の方法を実行するように適合される画像中に現れるオブジェクトを表示する装置。
【請求項6】
1つの画像または一連の画像に対応する信号を処理することにより、前記画像中に現れるオブジェクトの輪郭の曲率スケール空間(CSS)表示を導き出す手段と、
元のオブジェクトの輪郭の平滑化されたバージョンの真円度である追加パラメータを導き出す手段と、
前記CSS表示と前記追加パラメータとを関連させて前記オブジェクトの形状記述子を形成する手段と
を有することを特徴とする請求項5に記載の装置。
【請求項7】
画像および/または形状記述子を記憶する記憶手段をさらに有することを特徴とする請求項6に記載の方法。
【請求項8】
請求項1乃至4のいずれか1つに記載の方法を実現するための画像中に現れるオブジェクトを表示するコンピュータ・プログラム。
【請求項9】
請求項1乃至4のいずれか1つに記載の方法に従って作動する画像中に現れるオブジェクトを表示するコンピュータ・システム・プログラム。
【請求項10】
請求項1乃至4のいずれか1つに記載の方法を実行するためのコンピュータによって実行可能な処理を保存するコンピュータ可読記憶媒体。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate


【公開番号】特開2011−100465(P2011−100465A)
【公開日】平成23年5月19日(2011.5.19)
【国際特許分類】
【出願番号】特願2010−265275(P2010−265275)
【出願日】平成22年11月29日(2010.11.29)
【分割の表示】特願2001−511636(P2001−511636)の分割
【原出願日】平成12年7月12日(2000.7.12)
【出願人】(501253316)ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】MITSUBISHI ELECTRIC R&D CENTRE EUROPE B.V.
【住所又は居所原語表記】20 Frederick Sanger Road, The Surrey Research Park, Guildford, Surrey GU2 5YD, Great Britain
【Fターム(参考)】