(57)【要約】【課題】形状記述子パラメータを効率的にコード化する方法等を提供する。【解決手段】画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現する方法であって、オブジェクトの形状の曲率尺度空間(ＣＳＳ)表現を得るステップであり、前記ＣＳＳ表現は曲率尺度空間内の複数のピークの複数の組の座標値を含むものを備え、さらに、前記座標値を量子化して形状のコード化表現を得るステップを含み、所与の座標用の値を有する第１の組の座標値が、第２の組の座標値における対応する座標値より小さい場合に、第１の組の値のための前記所与の座標値の量子化表現に割り当てられるビットの数が、第２の組の値のための対応する座標値の量子化表現に割り当てられたビットの数よりも小さいことを特徴とする方法。【選択図】図３
2011227924.tif 000002
【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現する方法であって、
オブジェクトの形状の曲率尺度空間(ＣＳＳ)表現を得るステップであり、前記ＣＳＳ表現は曲率尺度空間内の複数のピークの複数の組の座標値を含むものを備え、さらに、
前記座標値を量子化して形状のコード化表現を得るステップを含み、
所与の座標用の値を有する第１の組の座標値が、第２の組の座標値における対応する座標値より小さい場合に、
第１の組の値のための前記所与の座標値の量子化表現に割り当てられるビットの数が、第２の組の値のための対応する座標値の量子化表現に割り当てられたビットの数よりも小さいことを特徴とする方法。
【請求項２】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現するコンピュータで構成される装置であって、
オブジェクトの形状の曲率尺度空間(ＣＳＳ)表現を得る手段であり、前記ＣＳＳ表現は曲率尺度空間内の複数のピークの複数の組の座標値を含むものを備え、さらに、
前記座標値を量子化して形状のコード化表現を得る手段を含み、
所与の座標用の値を有する第１の組の座標値が、第２の組の座標値における対応する座標値より小さい場合に、
第１の組の値のための前記所与の座標値の量子化表現に割り当てられるビットの数が、第２の組の値のための対応する座標値の量子化表現に割り当てられたビットの数よりも小さいことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、マルチメディア・データベースに格納された画像などの静止画像またはビデオ画像に表示されるオブジェクトの表現に関し、詳細には、このような表現のコード化に関する。
【背景技術】
【０００２】
画像ライブラリまたはビデオライブラリなどの用途では、静止画像またはビデオ画像に表示されるオブジェクトまたはオブジェクトの一部の輪郭線すなわち形状を効率的に表現および格納することが望ましい。形状を基本とするインデクシングおよび検索用の公知の技法は、ＣＳＳ(Curvature  Scale  Space)(曲率尺度空間)表現を利用している。ＣＳＳ表現の詳細は、「Robust and Efficient Shape Indexing through Curvature Scale Space(曲率尺度空間を通じてのロバストで、かつ効率的な形状インデクシング)」(British Machine Vision会議報告書、５３〜６２ページ、Edinburgh, UK, 1996)の論文と、「Indexing an Image Database by Shape Content using Curvature Scale Space(曲率尺度空間を用いて、形状内容により画像データベースをインデックスする)」(IEE Colloquium on Intelligent Databases、 London 1996)の論文に記載されている。双方の論文は、F. Mokhatarian氏，S. Abbasi氏、及びJ. Kittler氏によるもので、それらの内容は、参照によって、本明細書に組み入れられている。
【０００３】
ＣＳＳ表現は、オブジェクトの輪郭線上の任意の点から始まる、その輪郭線用の曲率関数を用いる。この形状を滑らかにする一連の変形により輪郭線形状が展開されるときに、この曲率関数が調べられる。さらに具体的に言えば、ガウスフィルタのファミリーで巻き込まれた曲率関数の導関数のゼロ交差を計算する。「曲率尺度空間」として知られているゼロ交差が、グラフ上にプロットされる。このグラフにおいて、ｘ軸は、この曲線の正規化された弧長であり、またｙ軸は、その展開パラメータ、具体的に言えば、施されたフィルタのパラメータである。グラフ上のこれらのプロットは、この輪郭線の特性を示しているループを形成する。オブジェクト輪郭線のそれぞれの凸部または凹部は、ＣＳＳ画像におけるループに対応する。ＣＳＳ画像におけるもっとも顕著なループのピークの座標が、輪郭線の表現として利用される。
【０００４】
データベースに格納された画像の中から、入力オブジェクトの形状に一致するオブジェクトを探すために、入力形状のＣＳＳ表現を計算する。入力形状と格納された形状とが類似するかどうかは、照合アルゴリズムを用いて、それぞれのＣＳＳ画像におけるピークの位置および高さを比較して、決定される。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
輪郭形状の性質を、記述子で表現するのに必要なビットの数は、効率的な格納および伝送を容易に行うために、できる限り少ないものでなければならない。
【０００６】
本発明のいくつかの態様は、併記の特許請求の範囲に述べられる。
【課題を解決するための手段】
【０００７】
本発明は、検索性能に著しい劣化がまったくなく、非常にコンパクトな(格納に用いられたビットの数に関して)表現を提供できる。
【図面の簡単な説明】
【０００８】
【図１】ビデオ・データベースシステムのブロック図である。
【図２】輪郭線のＣＳＳ表現である。
【図３】ＣＳＳ表現の座標値のコード化を示す図である。
【発明を実施するための形態】
【０００９】
本発明の実施の形態は、添付図面を参照して述べられる。
図１は、本発明の一実施の形態によるコンピュータ・ビデオデータベースシステムを示している。このシステムは、コンピュータの形式の制御ユニット２、モニタの形式の表示ユニット４、マウスの形式のポインティング・デバイス６、格納された静止画像とビデオ画像を含む画像データベース８、および、画像データベース８に格納された画像に表示されるオブジェクトまたはオブジェクトの一部の記述子を格納する記述子データベース１０を含む。
【００１０】
画像データベース内の画像に表示されるそれぞれの該当オブジェクトの形状に関する記述子は、制御ユニット２によって得られて、記述子データベース１０に格納される。制御ユニット２は、以下に述べられる方法を実施する適切なプログラムの制御のもとで働く記述子を得る。
【００１１】
まず最初に、所与のオブジェクト輪郭線では、この輪郭線のＣＳＳ表現が得られる。これは、上述の論文の１つに記述される公知の方法を用いて行われる。
【００１２】
さらに具体的に言えば、この輪郭線は、表現Ψ＝{ｘ(ｕ)，ｙ(ｕ)，ｕ∈[０，１]}によって表わされる。式中、ｕは、正規化された弧長パラメータであり、また(ｘ，ｙ)は、オブジェクト輪郭上のこれらの点の座標である。
【００１３】
この輪郭線は、Ψを、ガウス核ｇ(ｕ，σ)、もしくはそれに類する核で巻き込むことで、滑らかにされる。また、展開曲線の曲率ゼロ交差は、σが変わると調べられる。このゼロ交差は、曲率に関する以下の式を用いて、特定される：
【００１４】
【数１】
2011227924.tif 000003
【００１５】
上記の説明において、＊は、合成積(convolution)を表わし、また下つきの添字は、導関数を表わす。
【００１６】
曲率ゼロ交差の数は、σが変わると変わり、またσが充分に大きいときには、Ψは、ゼロ交差のない凸曲線である。
【００１７】
ＣＳＳ画像空間として知られているゼロ交点(ｕ，σ)が、グラフ上にプロットされる。これにより、もとの輪郭線の特性を示している複数の曲線が得られる。これらの特性曲線のピークが特定され、対応する座標が取り出されて、格納される。一般的に言うと、これは、ｎ個の座標対から成る一組[(ｘ１，ｙ１)，(ｘ２，ｙ２)，・・・(ｘｎ，ｙｎ)]を与える。ここで、ｎはピークの数であり、またｘｉは、ｉ番目のピークの弧長位置であり、またｙｉはピークの高さである。
【００１８】
特性曲線がＣＳＳ画像空間に表示されるとき、特性曲線の順序と位置、および、対応するピークは、上述の曲率関数に対する始点によって決まる。これらのピーク座標は、以下に述べられるように、再び順序付けられる。
【００１９】
パラメータを取り出す輪郭が、ｎ個のピークを持つと仮定しよう。この場合、これらのピーク・パラメータは、図２に示されるように、{(ｘ1，ｙ1)，(ｘ2，ｙ2)，・・・，(ｘn，ｙn)}の一組を形成する。次に、これらのピークは、高さ(すなわち、ｙ座標値)に基いて、大きい順か小さい順のいずれかに順序付けられる{(ｘ1，ｙ1)，(ｘ2，ｙ2)，・・・，(ｘn，ｙn)}(下つきの添字は、順序付け後のピーク順序数字を表わす)。もっとも大きいピークが第１のピーク(ｘ1，ｙ1)となり、また後続するピークのそれぞれが、この組の中のその直前のピークに等しいか、またはそれよりも小さいように、小さい順に順序付けられると仮定しよう(図３)。
【００２０】
これらの再び順序付けられたピーク座標は、オブジェクト輪郭線用の記述子の基礎を成す。丸さＣ、偏心Ｅ、及びコンパクト性Ｄなどの、形状の追加パラメータ(一部、いわゆる「プロトタイプ輪郭形状」から取り出される)も計算し、格納して、同時係属中の出願第ＧＢ９９１６６８４．５号に記述される照合プロセスに利用され得る。この出願の内容は、参照によって、本明細書に組み入れられている。
【００２１】
次に、ピークの高さの粗い量子化を実施する。量子化を実施する範囲は、ピークごとに異なり、さらに大きいピーク(例えば、この順序付けられた組の中で、先行するピークの高さ)の値によって決まる。
【００２２】
図３を参照すると、第１のピークは、範囲Ｉ１＝[０，Ｙmax]にわたって量子化される。ここで、Ｙmaxは、ある種類の形状で予想されるピーク用の最大値である。残りのピークはそれぞれ、先行するピークの１つまたはいくつかの値によって決まる範囲に量子化される。例えば、ピークｙ2は、間隔Ｉ２＝[０，ｙ1]にわたって量子化され(図３)、ピークｙ3は、間隔[０，ｙ2]にわたって量子化され、以下同様に量子化される。
【００２３】
この実施の形態では、第１のピークは、７ビットを用いて、間隔[０，１０２４]にわたって量子化され、また、残りのほかのピークは、上で取り上げられたように、適切なそれぞれの範囲にわたって、３ビットに量子化される。第１のピークの高さが例えば８９３であるとすると、ｙ2は、３ビットを用いて、範囲[０，８９３]にわたって量子化され、以下同様に量子化される。よって、ピークｙ2〜ｙ5では、その量子化間隔は短くされて、さらに少ないビットを用いるにもかかわらず、精度をさらに高める。各ピークのｘ位置は、[０，１]間隔に一様に配分された６ビットに量子化される。このｘ値は、例えば図２に示されるように、もとのｘ値であるか、あるいは、ｘ軸に沿って、ある大きさだけ移した後で、最大ピークに対するｘ値を０になるようにする場合がある。
【００２４】
本発明からの利益を調べてみよう。従来の解決法では、各ピークは、それぞれ４バイトの２つの浮動小数点数を必要とする。したがって、９つのピークを有する代表的な形状では、記憶要求値は、９＊２＊４＝７２バイト(５７６ビット)である。この提案された実施の形態を適用した後で、第１のピークは、このｘ値がゼロと見なされると仮定して７ビットを必要とし、また、それぞれの連続するピークは、６＋３ビットを必要とし、したがって合計７９ビットが必要となる。
【００２５】
範囲[０，ｙi]でなく、範囲[０，Ｒ(ｙi)]を用いることもできる。ここで、Ｒ(ｙi)は、逆量子化の後で、値ｙiを再構成したものである。
【００２６】
同様な効果を持つことになる代替実施の形態は、ピークのそれぞれの高さ{ｙ２，ｙ３，・・・，ｙｎ}(最大のものを除く)を、それぞれの前のピークの値で割ることである。このような演算の後では、全ｙiの範囲は、[０，１]の組からのものである。これにより、全ｙiに対して、さらに粗い量子化を利用することができる。
【００２７】
いずれの例でも、最大ピークに対して７ビットまたは６ビットの量子化を用い、かつ、残るすべてのピークに対して４ビットまたは３ビットの量子化を用いれば、良好な結果を得ることができる。他のビット数を用いることもできる。
【００２８】
上記の処理は、同時係属中の出願第ＧＢ９９１５６９９．４号に記述されるように、これらの座標値が、従法線フィルタリングと非線形変換を受けた後でも、実施できる。この出願の内容は、参照によって、本明細書に組み入れられている。上述の方針に従って、ｙ値ではなくて、ｘ座標をコード化できるか、あるいは、ｙの値だけでなく、ｘ座標もコード化できる。
【００２９】
結果として得られた値は、本願発明者らの同時係属中の出願第ＧＢ９９１５６９９．４号、第ＧＢ９９１５６９８．６号、第ＧＢ９９１６６８４．５号に述べられるように、例えば、適切な照合手順に用いるために、格納されることもあり、その場合、例えば、照合を実施する前に、それらの格納された記述子に逆量子化を実施して、適切な変更が加えられる。
【図１】
2011227924.tif 000004
【図２】
2011227924.tif 000005
【図３】
2011227924.tif 000006
【手続補正書】
【提出日】平成23年8月10日(2011.8.10)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現する方法であって、
オブジェクトの形状の曲率尺度空間表現を得るステップであり、前記曲率尺度空間表現は曲率尺度空間内の複数のピークの複数の対の座標値を含むものを備え、さらに、
前記座標値を量子化して形状のコード化表現を得るステップを含み、
所与の座標用の値を有する第１の組の座標値が、第２の組の座標値における対応する座標値より小さい場合に、第１の組の値のための前記所与の座標値の量子化表現に割り当てられるビットの数が、第２の組の値のための対応する座標値の量子化表現に割り当てられたビットの数よりも小さいことを特徴とする方法。
【請求項２】
前記第１の組の座標値のうちの前記所与の座標値用の量子化範囲は、少なくとも、前記第２の組の座標値のうちの対応する座標値に基く請求項１記載の方法。
【請求項３】
一連の小さくなる座標値では、各座標値用の量子化範囲は、先行するさらに大きい座標値が存在する場合に、それらの座標値の１つまたは複数に基く請求項２記載の方法。
【請求項４】
前記所与の座標値が量子化される範囲が、前記第１の組の座標値のためのものが前記第２の組の座標値のためのものより少ない請求項１から３までのいずれか１項記載の方法。
【請求項５】
前記第１の組の値用の前記所与の座標値の量子化表現に割り当てられるビットの数は、前記第２の組の値用の対応する座標値の量子化表現に割り当てられるビットの数と同じである請求項１から３のいずれか１項記載の方法。
【請求項６】
変化する量子化範囲は、ピークの高さに一致する座標値に用いられる請求項１から５までのいずれか１項記載の方法。
【請求項７】
量子化範囲は、複数の座標値に対して同一である請求項１から６までのいずれか１項記載の方法。
【請求項８】
座標値を、小さくなるサイズまたは大きくなるサイズに順序付けるステップを含む請求項１から７までのいずれか１項記載の方法。
【請求項９】
画像に対応する信号を処理することで、画像又は連続する画像の中からあるオブジェクトを探す方法であって、
クエリー・オブジェクトを入力するステップと、
前記クエリー・オブジェクトの表現を得るステップと、
前記表現と、請求項１から８までのいずれか１項記載の方法を用いて得られる表現とを比較するステップと、
前記表現が前記クエリーとの類似度を示すオブジェクトを選択して、表示するステップと、
を含む方法。
【請求項１０】
請求項１から９までのいずれか１項記載の方法の全てのステップを実行する手段を備えた装置。
【請求項１１】
請求項１から９までのいずれか１項記載の方法の全てのステップを実施するようにプログラムされた、画像又は連続する画像の中のオブジェクトの表現を得る、又は画像又は連続する画像の中のオブジェクトを探すための制御装置。
【請求項１２】
請求項１１記載の制御装置、および画像と画像の表現の少なくとも一方を格納する記憶手段とを備えた、画像又は連続する画像の中のオブジェクトの表現を得る、又は画像又は連続する画像の中のオブジェクトを探すための装置。
【請求項１３】
前記記憶手段が、画像データベースと記述子データベースの少なくとも一方からなる請求項１２に記載の装置。
【請求項１４】
請求項１から９までのいずれか１項記載の方法の全てのステップを実行するためのコンピュータで実行可能なステップを格納するコンピュータで読み取り可能な記憶媒体。