(57)【特許請求の範囲】
【請求項１】
第１の透視ビューにおいて第１の２次元輪郭を有し、画像に現れる物体を、前記画像に対応する信号を処理することによって、表現する方法であって、
前記画像における前記物体の輪郭を抽出するステップと、
前記第１の透視ビューにおいて前記物体の前記輪郭の形状を表現するビューデスクリプタを導出するステップと、
少なくとも１つの追加の異なる透視ビューで前記物体あるいは前記物体の異なる例の少なくとも１つの追加の輪郭を取得するステップと、
少なくとも１つの追加の異なる透視ビューで前記物体あるいは前記物体の異なる例の輪郭の形状を表現する少なくとも１つの追加のビューデスクリプタを導出するステップと、
曲率スケール空間表現を用いて導出された複数のビューデスクリプタであって、異なる透視ビューで前記物体あるいは前記物体の異なる例の輪郭の形状を表現する複数のビューデスクリプタを結合することによって物体デスクリプタを形成するステップと
を含む物体を表現する方法。
【請求項２】
前記画像はビデオである
請求項１記載の方法。
【請求項３】
画像に対応する信号を処理することにより、画像の物体を探索する方法であって、
物体の少なくとも１つの２次元ビューの形態でクエリを入力するステップと、
前記クエリの物体のデスクリプタを導出するステップと、
前記クエリのデスクリプタを、請求項１又は請求項２に記載の方法に従って導出された画像の物体の格納された物体デスクリプタと比較するステップと、
各デスクリプタと前記クエリのデスクリプタとの比較が前記クエリと前記物体との類似の度合を示す、その対象となる物体を含む画像に対応する少なくとも１つの結果を選択して表示するステップと
を含む物体を探索する方法。
【請求項４】
クエリは、物体の複数の２次元ビューの形態で入力され、
クエリビューデスクリプタは、前記ビューの各々について導出され、
前記比較するステップは、前記クエリビューデスクリプタの各々を、格納された各物体デスクリプタの各ビューデスクリプタと比較することによって、複数のビュー類似値を導出する
請求項３記載の方法。
【請求項５】
前記ビュー類似値が分析されて、物体類似値を導出する
請求項４記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、形状を用いて静止またはビデオ画像の物体を表現し、特に探索に使用される方法に関するものである。また、この発明は、形状表現を用いて画像の物体を探索する方法に関するものである。
【０００２】
【従来の技術】
画像に現れる物体の表現を用いて、例えば画像ライブラリに静止またはビデオ画像を格納することが知られている。この表現が探索方法において使用されることにより、対象となる物体を含む画像を検索することが可能となる。この表現は、カラー（colour）、テクスチャ（texture）および形状（shape）を含む物体のあらゆる特徴に基づくことができる。
【０００３】
画像内の物体の形状を表現するあらゆる方法が知られている。周知の方法には、チェインコーディング、４分木方法および曲率スケール空間表現方法がある。
【０００４】
画像探索システムにおいて探索を実行するために、ユーザは、捜している物体のスケッチまたは画像をシステムに提示することにより、あるいは、システムに格納されている物体のビューを選択することにより、クエリを入力する。そして、システムは、クエリ物体の表現を導出または取得し、適当なマッチング方法を用いて、そのクエリ表現をデータベースに格納された画像の表現と比較する。その最も近似して一致したものが、表示装置に表示される。
【０００５】
大抵の場合、ビデオ画像に現れる物体は、３次元の現実の物体を２次元画像平面に投影したものである。このため、画像に現れる物体の２次元形状または輪郭は、ビューイング位置、ビューイング角度、カメラおよび光学系パラメータ等の要素によって決まる。従って、物体は、異なるビューに対応する異なる輪郭を有することとなる。
【０００６】
【発明が解決しようとする課題】
周知の画像データベースシステムの欠点は、あらゆる輪郭を有するある物体のそれぞれのビューが異なる物体として処理されるということである。その結果、例えば、ユーザが物体Ａの前方のビューに基づいてクエリを入力するが、その物体Ａがビデオシーケンスにおいて後方および側方のビューからしか現れていない場合、適切に一致せず、その物体は検索されない。
【０００７】
【課題を解決するための手段】
本発明は、デジタル画像に現れる物体を表現する方法であって、その物体に対応する複数の異なる２次元ビューの表現を導出することを含む方法を提供する。
【０００８】
また、本発明は、クエリを入力することと、物体の画像に対応する信号を処理することにより、クエリを物体の異なるビューの複数の表現と比較して最も近似した一致を見つけることと、を含む物体をマッチングする方法を提供する。
【０００９】
【発明の実施の形態】
実施の形態１．
本発明の実施の形態を、添付図面を参照して説明する。
【００１０】
本発明の実施の形態によるシステムを、図１に示す。本システムは、システムの動作を制御するコンピュータ等の制御装置２と、制御装置２に接続され、画像およびテキストを含む出力を表示するモニタ等の表示装置４と、制御装置２への命令を入力するマウス等のポインティングデバイス６と、を有している。また、本システムは、複数のビデオシーケンスのデジタルバージョンを格納する画像データベース８と、画像データベース８に格納されたビデオシーケンスの各々に現れる物体について、後に詳述するデスクリプタ情報を格納するデスクリプタデータベース１０と、も有している。画像データベース８およびデスクリプタデータベース１０の各々は、制御装置２に接続されている。
【００１１】
本実施の形態において、システムの要素は、画像ライブラリ等の単一サイトに設けられており、システムの構成要素は永久的にリンクされている。
【００１２】
本発明の実施の形態による物体のデスクリプタを導出する方法について、図２および図３を参照して説明する。本方法では、比較的単純な形状を有する物体、この場合は円筒状物体について説明する。
【００１３】
この例では、画像データベース８に格納されたビデオシーケンスにおいて、円筒状物体は２回現れる。図２を参照すると、第１の出現において、物体の輪郭は側方からのビューであるビュー１に対応しており、第２の出現では、側方および上方からの透視ビューであるビュー３に対応している。
【００１４】
ここで、本方法のステップを、図３に示すフローチャートを参照して説明する。
【００１５】
データベースインデクサ（indexer）は、２つの輪郭が同じ物体のものであり、それら輪郭に対応する３次元物体が円筒であることを認識する（ステップ１０）。ビュー１およびビュー３の各々について、曲率スケール空間（ＣＳＳ）表現を用いる形状デスクリプタを導出する（ステップ２０）。また、データベースインデクサは、その物体を表していると思われるいずれかの追加のビューを、検討中のビデオシーケンスにそれらが現れていない場合であっても選択する（ステップ３０）。この例では、上方からの円筒のビューであるビュー２がその物体を表しているものとして選択される。そのビューのＣＳＳ表現もまた、取得する（ステップ４０）。
【００１６】
Farzin Mokhtarian、Sadegh AbbassiおよびJosef Kittlerによる論文「Robust and Efficient Shape Indexing through Curvature Scale Space」（Proc. British Machine Vision Conference, pp.53-62, Edinburgh, U.K.,1996）では、曲率スケール空間表現の方法が述べられており、この論文の内容は引用をもって本明細書に包含されたものとする。簡単に言えば、形状の輪郭を表現する曲線が、その曲線を平滑化することによって展開される。その曲線は、展開の多くの異なる段階で考慮される。より具体的には、展開の各段階で、曲率関数における曲率ゼロ交差が識別される。曲率ゼロ交差のグラフは、展開のすべての段階からのゼロ交差を結合することによって得られる。そのグラフの一方の軸は、曲線の展開パラメータを表すσに対応し、他方の軸は、曲線円弧長パラメータｕに対応する。そして、形状は、グラフの輪郭線の最大値の位置によって表される。
【００１７】
物体を表すビューのＣＳＳ形状表現に加えて、物体のビューとは無関係な、物体のグローバル３Ｄ形状パラメータを取得する（ステップ５０）。この例では、グローバルパラメータは、現実の物体の体積である。この体積はすでに知られていてもよく、あるいは、ビデオシーケンスに現れる、寸法を近似させることができる人間等の他の物体に関連して、近似させるようにしてもよい。
【００１８】
グローバルパラメータおよびビュー形状デスクリプタを結合することにより、３Ｄ物体形状デスクリプタを形成する（ステップ６０）。
【００１９】
上述した方法により、画像データベース８の画像に現れる対象となるすべての物体について、３Ｄ物体形状デスクリプタが取得される。所定の物体に対するビューの数と、いずれのビューが使用されるかとは、その物体の複雑さによって決まる。物体によっては、例えば、体積の値が既知ではないかまたは容易に導出されない場合に、３Ｄ物体形状デスクリプタにグローバルパラメータを有していない場合がある。各ビューは、それがビデオシーケンスのいずれのフレームに現れるか、および、それはそのフレームのいずれの物体であるかを示す参照ポインタを有する。例えば、物体のビューは、それがフレーム１０００に現れ物体番号３であることを示すポインタを有することができる。
【００２０】
また、異なる形状表現方法を用いる他の実施の形態においても、ビューの数および特徴は、使用される形状表現方法によって決まる。例えば、ビューイングジオメトリの変化に起因する形状の変形に影響を受け難い方法では、必要とするビューの数は少なくなる。
【００２１】
デスクリプタデータベース１０は、画像データベース８に格納されたビデオシーケンスの物体に対し３Ｄ物体形状デスクリプタを格納する。
【００２２】
ここで、ビデオシーケンスの物体を探索する方法について、図４および図５を参照して説明する。
【００２３】
ユーザは、クエリを入力することによって探索を開始する。クエリは、ポインティングデバイス６を用いて表示装置４上に１つまたは複数の形状輪郭を描くことによって入力される（ステップ６２）。この例では、２つのクエリ輪郭１００が入力されている。これらは、クエリビューである。ユーザはまた、探索している物体の体積を表すパラメータを入力する（ステップ６４）。
【００２４】
そして、制御装置２は、それらクエリビューの各々に対しＣＳＳビューデスクリプタを導出する（ステップ６６）。
【００２５】
他の実施の形態では、ユーザは、制御装置２によって表示装置４に表示される形状のメニューから１つまたは複数のクエリ形状を選択することによってクエリを入力する。かかる実施の形態では、ビューデスクリプタをデスクリプタデータベース１０においてすでに入手することができる。
【００２６】
クエリ体積パラメータおよびクエリビューデスクリプタが結合され、クエリ３Ｄ物体デスクリプタが形成される。
【００２７】
そして、システムは、クエリ物体デスクリプタとデスクリプタデータベース１０に格納された物体デスクリプタ（以下、モデル物体デスクリプタと言う）との類似性を判断するマッチングプロシージャを実行する。デスクリプタデータベース内の各モデル物体デスクリプタを、セレクタ２０５によって順次選択し（ステップ６８）、各モデル物体デスクリプタに対しそれぞれ順番がくると以下のステップを実行する。
【００２８】
まず、グローバル類似測度（ＧＳ）を、コンパレータ２００により、クエリ物体デスクリプタおよびモデル物体デスクリプタのグローバルパラメータを用いて取得する（ステップ７０）。本実施の形態では、ＧＳは、クエリ体積パラメータの、データベースから取出されたデスクリプタのモデル体積パラメータに対する割合を求めることにより、導出される。その割合が区域（１／ｃ，ｃ）（ｃ＞１）にある場合、物体は類似しているとみなされ、ＧＳは値０をとる。それ以外の場合、ＧＳは無限大の値をとる。ｃの値は、その適用法によって決まる。例えば、劇映画の場合、ｃ＝５である。
【００２９】
クエリ物体デスクリプタとモデル物体デスクリプタの少なくとも一方がグローバルパラメータ値を有していない場合、ＧＳ＝０となる。
【００３０】
ＧＳ≠０である場合、デスクリプタデータベースから新たなモデル物体デスクリプタを選択する。ＧＳ＝０である場合、以下のようにビューデスクリプタ比較を実行する（ステップ７２）。
【００３１】
コンパレータ８１０において、マッチング機能を用いてビュー類似測度を導出することにより、各クエリビューデスクリプタを、検討中のモデル物体デスクリプタの各ビューデスクリプタと比較する（ステップ７４）。ｉ番目のクエリビューデスクリプタとｊ番目のモデルビューデスクリプタとを比較することにより、ビュー類似測度ｓijが得られる。
【００３２】
より詳細には、セレクタ６００を用いてクエリビューデスクリプタを選択し、セレクタ７００を用いてデータベースビューデスクリプタを選択する。まず、第１のクエリビューに対するビューデスクリプタを、データベースからのモデル物体デスクリプタの各ビューデスクリプタと比較する。各ペアに対し、適切なマッチングアルゴリズムを用いてビュー類似値ｓを計算する。本実施の形態では、ビュー類似値ｓは、上述したMokhtarian、AbbasiおよびKittlerの論文において述べられているマッチングアルゴリズムを用いて計算する。この特定の類似測度を使用する場合、ビュー類似値が小さいほど、一致がより近似する。この結果、第１のクエリビューに対するｋ個のビュー類似測度の組が得られる。なお、ｋは、検討中のモデル物体デスクリプタのビューデスクリプタの数であり、ｋ個の測度は、グローバルおよびローカル類似コンバイナ８２０に格納される。
【００３３】
そして、同様に、第２のクエリビューデスクリプタとデータベースからのモデルビューデスクリプタとに対し、ビュー類似値を計算し格納する。その結果、更にｋ個のビュー類似測度が得られる。
【００３４】
各クエリビューに対し、検討中のデータベースデスクリプタ値の最小ビュー類似値を選択する（ステップ７６）。この最小値は、各クエリビューと、考慮中の物体デスクリプタのビューの１つとの間の最も近接した一致の測度である。この結果、ｐ個の最小ビュー類似値が得られる。なお、ｐはクエリビューの数である。この例では、ｐ＝２である。
【００３５】
クエリデスクリプタと考慮中のモデル物体デスクリプタとに対する全類似測度Ｓを、ｐ個の類似値の中央値として求める（ステップ７８）。これは、すべてのビューを考慮して、クエリデスクリプタとモデル物体デスクリプタとが最も近似して一致していることを表している。このため、一方のクエリビューがデータベースデスクリプタのビューと近似して一致するが、他方のクエリビューがデータベースデスクリプタのいかなるビューとも近似して一致しない場合、これは、中間値によってＳに反映される。
【００３６】
上記ステップを、デスクリプタデータベース８の各物体デスクリプタに対して繰返し、その結果、ｎ個の類似測度Ｓが得られる（ステップ８０）。なお、ｎは、デスクリプタデータベースの３Ｄ物体デスクリプタの数である。そして、ｎ個の類似測度を、最も近似した一致を示す最低値から開始して順序付ける（ステップ８２）。その後、ｍ個の最低値（ｍは、ユーザが選択した値か、もしくは制御装置の設定によって決定された値である）を選択し、物体を含む対応するｍ個のビデオシーケンスの各々からの画像を表示装置４に表示する（ステップ８４）。
【００３７】
本発明によれば、１つの物体の複数のビューが格納されることにより、輪郭形状の完全なまたは準完全な記述が形成される。検索に重要であると考えられるビューのみが格納される場合、表現は準完全なものとなる。例えば、劇映画を格納する一般的なデータベースの場合、車の前方、後方、側方および上方のビューのみが統合された表現として格納されるが、車の下方からのビューは格納されない。それは、そのビューがクエリとして使用される可能性が低いためである。
【００３８】
本発明によるシステムは、例えば、画像ライブラリに設けることができる。あるいは、データベースを、システムの制御装置から遠隔に設置し、電話線などの一時的なリンクによるかまたはインタネット等のネットワークにより制御装置に接続することも可能である。画像データベースおよびデスクリプタデータベースを、例えば、永久記憶装置、あるいは、ＣＤ−ＲＯＭまたはＤＶＤ等のポータブルデータ記憶媒体に設けるようにしてもよい。
【００３９】
上述したセレクタおよびコンパレータ等のシステムの構成要素は、ソフトウェア形態でもハードウェア形態でも設けることができる。本発明は、コンピュータシステムの形態で説明されているが、例えば専用チップを使用して他の形態で実装することも可能である。
【００４０】
物体の２Ｄ形状を表現する方法および２つの形状の類似性を表す値を計算する方法の特定の例を与えたが、そのような他の適切な方法を用いることも可能である。
【００４１】
完全なまたは準完全な形状記述を構成するあらゆるビューは、例えば、フィルムの製作者によって与えられるようにしてもよい。例えば、車を含むフィルムでは、製作者は、データベースのフィルムのインデクシング（indexing）に使用するために、その車の２０の異なるビューが撮影されるようにすることができる。あるいは、ビューを見つけることができるシーケンスにおいて、物体のすべての異なるビューの間にリンクを設けるようにしてもよく、例えば、シーケンスに現れないあらゆる有用なビューに対する形状を、物体の第１のビューのデータが含まれる場合に、与えるようにしてもよい。
【００４２】
本発明はまた、例えば、検査の目的で物体の画像をマッチングするため、またはフィルタリングするためにも使用することも可能である。
【図面の簡単な説明】
【図１】  本発明の実施の形態によるシステムのブロック図である。
【図２】  物体のデスクリプタが取得される方法を示す図である。
【図３】  物体のデスクリプタが取得される方法を示すフローチャートである。
【図４】  探索する装置および方法を示す図である。
【図５】  探索方法を示すフローチャートである。
【符号の説明】
２  制御装置、４  表示装置、６  ポインティングデバイス、８  画像データベース、１０  デスクリプタデータベース。
【図１】
0005121086.tif 000002
【図２】
0005121086.tif 000003
【図３】
0005121086.tif 000004
【図４】
0005121086.tif 000005
【図５】
0005121086.tif 000006