(57)【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現する方法であって、
オブジェクトの輪郭線上の位置を示すパラメータを用いた表現により、前記オブジェクトの輪郭線を表現し、
オブジェクトの輪郭線を滑らかにするフィルタを用いて前記オブジェクトの輪郭線を滑らかにし、
前記フィルタを施した回数を示すパラメータに関して、対応する滑らかにされた前記オブジェクトの輪郭線の曲率関数のゼロ交差を特定し、前記位置を表現するパラメータと前記フィルタを施した回数を示すパラメータとに対応する軸をもつグラフ上に前記ゼロ交差点をプロットすることで、前記オブジェクトの輪郭線の特性を示す複数の特性曲線を得て、
前記特性曲線のピークを特定し、特定したピークの位置とピーク高さ値からなる座標対に対応する座標を取り出し、曲率尺度空間(ＣＳＳ)表現を形成するステップと、
前記ピーク高さ値をピーク高さ値が小さくなっていく順に並べ、形状のコード化表現を得るために前記ピーク高さ値を量子化するステップと、
を有し、
前記量子化するステップにおいて、１番目に高いピーク高さ値の量子化は、量子化の範囲を所定のピーク用最大値とし、量子化ビット数を第１のビット数で行い、（ｓ＋１）番目（ｓは正整数）に高いピーク高さ値の量子化は、量子化の範囲をｓ番目に高いピーク高さ値とし、量子化ビット数を前記第１のビット数より小さい第２のビット数で行う、
ことを特徴とする方法。
【請求項２】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現するコンピュータで構成された装置であって、
オブジェクトの輪郭線上の位置を示すパラメータを用いた表現により、前記オブジェクトの輪郭線を表現し、
オブジェクトの輪郭線を滑らかにするフィルタを用いて前記オブジェクトの輪郭線を滑らかにし、
前記フィルタを施した回数を示すパラメータに関して、対応する滑らかにされた前記オブジェクトの輪郭線の曲率関数のゼロ交差を特定し、前記位置を表現するパラメータと前記フィルタを施した回数を示すパラメータとに対応する軸をもつグラフ上に前記ゼロ交差点をプロットすることで、前記オブジェクトの輪郭線の特性を示す複数の特性曲線を得て、
前記特性曲線のピークを特定し、特定したピークの位置とピーク高さ値からなる座標対に対応する座標を取り出し、曲率尺度空間(ＣＳＳ)表現を形成する手段と、
前記ピーク高さ値をピーク高さ値が小さくなっていく順に並べ、形状のコード化表現を得るために前記ピーク高さ値を量子化する手段と、
を有し、
前記量子化する手段において、１番目に高いピーク高さ値の量子化は、量子化の範囲を所定のピーク用最大値とし、量子化ビット数を第１のビット数で行い、（ｓ＋１）番目（ｓは正整数）に高いピーク高さ値の量子化は、量子化の範囲をｓ番目に高いピーク高さ値とし、量子化ビット数を前記第１のビット数より小さい第２のビット数で行う、
ことを特徴とする装置。
【請求項３】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現するコンピュータ・ビデオデータベースシステムであって、
オブジェクトの輪郭線上の位置を示すパラメータを用いた表現により、前記オブジェクトの輪郭線を表現し、
オブジェクトの輪郭線を滑らかにするフィルタを用いて前記オブジェクトの輪郭線を滑らかにし、
前記フィルタを施した回数を示すパラメータに関して、対応する滑らかにされた前記オブジェクトの輪郭線の曲率関数のゼロ交差を特定し、前記位置を表現するパラメータと前記フィルタを施した回数を示すパラメータとに対応する軸をもつグラフ上に前記ゼロ交差点をプロットすることで、前記オブジェクトの輪郭線の特性を示す複数の特性曲線を得て、
前記特性曲線のピークを特定し、特定したピークの位置とピーク高さ値からなる座標対に対応する座標を取り出し、曲率尺度空間(ＣＳＳ)表現を形成する手段と、
前記ピーク高さ値をピーク高さ値が小さくなっていく順に並べ、形状のコード化表現を得るために前記ピーク高さ値を量子化する手段と、
を有し、
前記量子化する手段において、１番目に高いピーク高さ値の量子化は、量子化の範囲を所定のピーク用最大値とし、量子化ビット数を第１のビット数で行い、（ｓ＋１）番目（ｓは正整数）に高いピーク高さ値の量子化は、量子化の範囲をｓ番目に高いピーク高さ値とし、量子化ビット数を前記第１のビット数より小さい第２のビット数で行う、
ことを特徴とするコンピュータ・ビデオデータベースシステム。
【請求項４】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現するためのコンピュータに、
オブジェクトの輪郭線上の位置を示すパラメータを用いた表現により、前記オブジェクトの輪郭線を表現し、
オブジェクトの輪郭線を滑らかにするフィルタを用いて前記オブジェクトの輪郭線を滑らかにし、
前記フィルタを施した回数を示すパラメータに関して、対応する滑らかにされた前記オブジェクトの輪郭線の曲率関数のゼロ交差を特定し、前記位置を表現するパラメータと前記フィルタを施した回数を示すパラメータとに対応する軸をもつグラフ上に前記ゼロ交差点をプロットすることで、前記オブジェクトの輪郭線の特性を示す複数の特性曲線を得て、
前記特性曲線のピークを特定し、特定したピークの位置とピーク高さ値からなる座標対に対応する座標を取り出し、曲率尺度空間(ＣＳＳ)表現を形成する手順と、
前記ピーク高さ値をピーク高さ値が小さくなっていく順に並べ、形状のコード化表現を得るために前記ピーク高さ値を量子化する手順と、
を行実行させ、
前記量子化する手順において、１番目に高いピーク高さ値の量子化は、量子化の範囲を所定のピーク用最大値とし、量子化ビット数を第１のビット数で行い、（ｓ＋１）番目（ｓは正整数）に高いピーク高さ値の量子化は、量子化の範囲をｓ番目に高いピーク高さ値とし、量子化ビット数を前記第１のビット数より小さい第２のビット数で行うことを実行させるためのプログラムを記録したコンピュータ読み取り可能な記憶媒体。
【請求項５】
画像に対応する信号を処理することで、画像又は連続する画像に表示されるオブジェクトを表現するためにコンピュータに、
オブジェクトの輪郭線上の位置を示すパラメータを用いた表現により、前記オブジェクトの輪郭線を表現し、
オブジェクトの輪郭線を滑らかにするフィルタを用いて前記オブジェクトの輪郭線を滑らかにし、
前記フィルタを施した回数を示すパラメータに関して、対応する滑らかにされた前記オブジェクトの輪郭線の曲率関数のゼロ交差を特定し、前記位置を表現するパラメータと前記フィルタを施した回数を示すパラメータとに対応する軸をもつグラフ上に前記ゼロ交差点をプロットすることで、前記オブジェクトの輪郭線の特性を示す複数の特性曲線を得て、
前記特性曲線のピークを特定し、特定したピークの位置とピーク高さ値からなる座標対に対応する座標を取り出し、曲率尺度空間(ＣＳＳ)表現を形成する手順と、
前記ピーク高さ値をピーク高さ値が小さくなっていく順に並べ、形状のコード化表現を得るために前記ピーク高さ値を量子化する手順と、
を行実行させ、
前記量子化する手順において、１番目に高いピーク高さ値の量子化は、量子化の範囲を所定のピーク用最大値とし、量子化ビット数を第１のビット数で行い、（ｓ＋１）番目（ｓは正整数）に高いピーク高さ値の量子化は、量子化の範囲をｓ番目に高いピーク高さ値とし、量子化ビット数を前記第１のビット数より小さい第２のビット数で行うことを実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、マルチメディア・データベースに格納された画像などの静止画像またはビデオ画像に表示されるオブジェクトの表現に関し、詳細には、このような表現のコード化に関する。
【０００２】
【従来の技術】
画像ライブラリまたはビデオライブラリなどの用途では、静止画像またはビデオ画像に表示されるオブジェクトまたはオブジェクトの一部の輪郭線すなわち形状を効率的に表現および格納することが望ましい。形状を基本とするインデクシングおよび検索用の公知の技法は、ＣＳＳ(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氏によるもので、それらの内容は、参照によって、本明細書に組み入れられている。
【０００３】
ＣＳＳ表現は、オブジェクトの輪郭線上の任意の点から始まる、その輪郭線用の曲率関数を用いる。この形状を滑らかにする一連の変形により輪郭線形状が展開されるときに、この曲率関数が調べられる。さらに具体的に言えば、ガウスフィルタのファミリーで巻き込まれた曲率関数の導関数のゼロ交差を計算する。「曲率尺度空間」として知られているゼロ交差が、グラフ上にプロットされる。このグラフにおいて、ｘ軸は、この曲線の正規化された弧長であり、またｙ軸は、その展開パラメータ、具体的に言えば、施されたフィルタのパラメータである。グラフ上のこれらのプロットは、この輪郭線の特性を示しているループを形成する。オブジェクト輪郭線のそれぞれの凸部または凹部は、ＣＳＳ画像におけるループに対応する。ＣＳＳ画像におけるもっとも顕著なループのピークの座標が、輪郭線の表現として利用される。
【０００４】
データベースに格納された画像の中から、入力オブジェクトの形状に一致するオブジェクトを探すために、入力形状のＣＳＳ表現を計算する。入力形状と格納された形状とが類似するかどうかは、照合アルゴリズムを用いて、それぞれのＣＳＳ画像におけるピークの位置および高さを比較して、決定される。
【０００５】
【発明が解決しようとする課題】
輪郭形状の性質を、記述子で表現するのに必要なビットの数は、効率的な格納および伝送を容易に行うために、できる限り少ないものでなければならない。
【０００６】
本発明のいくつかの態様は、併記の特許請求の範囲に述べられる。
【０００７】
【課題を解決するための手段】
本発明は、検索性能に著しい劣化がまったくなく、非常にコンパクトな(格納に用いられたビットの数に関して)表現を提供できる。
【０００８】
【発明の実施の形態】
本発明の実施の形態は、添付図面を参照して述べられる。
【０００９】
図１は、本発明の一実施の形態によるコンピュータ・ビデオデータベースシステムを示している。このシステムは、コンピュータの形式の制御ユニット２、モニタの形式の表示ユニット４、マウスの形式のポインティング・デバイス６、格納された静止画像とビデオ画像を含む画像データベース８、および、画像データベース８に格納された画像に表示されるオブジェクトまたはオブジェクトの一部の記述子を格納する記述子データベース１０を含む。
【００１０】
画像データベース内の画像に表示されるそれぞれの該当オブジェクトの形状に関する記述子は、制御ユニット２によって得られて、記述子データベース１０に格納される。制御ユニット２は、以下に述べられる方法を実施する適切なプログラムの制御のもとで働く記述子を得る。
【００１１】
まず最初に、所与のオブジェクト輪郭線では、この輪郭線のＣＳＳ表現が得られる。これは、上述の論文の１つに記述される公知の方法を用いて行われる。
【００１２】
さらに具体的に言えば、この輪郭線は、表現Ψ＝{ｘ(ｕ)，ｙ(ｕ)，ｕ∈[０，１]}によって表わされる。式中、ｕは、正規化された弧長パラメータであり、また(ｘ，ｙ)は、オブジェクト輪郭上のこれらの点の座標である。
【００１３】
この輪郭線は、Ψを、ガウス核ｇ(ｕ，σ)、もしくはそれに類する核で巻き込むことで、滑らかにされる。また、展開曲線の曲率ゼロ交差は、σが変わると調べられる。このゼロ交差は、曲率に関する以下の式を用いて、特定される：
【００１４】
【数１】
0004975932.tif 000002
【００１５】
上記の説明において、＊は、合成積(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に対して、さらに粗い量子化を利用することができる。
【００２７】
いずれの例でも、最大ピークに対して７ビットまたは６ビットの量子化を用い、かつ、残るすべてのピークに対して４ビットまたは３ビットの量子化を用いれば、良好な結果を得ることができる。他のビット数を用いることもできる。
【００２８】
上記の処理は、同時係属中の出願第ＧＢ９９１５６９９．４号に記述されるように、これらの座標値が、従法線フィルタリングと非線形変換を受けた後でも、実施できる。この出願の内容は、参照によって、本明細書に組み入れられている。上述の方針に従って、ｙ値ではなくて、ｘ座標をコード化できるか、あるいは、ｙの値だけでなく、ｘ座標もコード化できる。
【００２９】
結果として得られた値は、本願発明者らの同時係属中の出願第ＧＢ９９１５６９９．４号、第ＧＢ９９１５６９８．６号、第ＧＢ９９１６６８４．５号に述べられるように、例えば、適切な照合手順に用いるために、格納されることもあり、その場合、例えば、照合を実施する前に、それらの格納された記述子に逆量子化を実施して、適切な変更が加えられる。
【図面の簡単な説明】
【図１】  ビデオ・データベースシステムのブロック図である。
【図２】  輪郭線のＣＳＳ表現である。
【図３】  ＣＳＳ表現の座標値のコード化を示す図である。
【図１】
0004975932.tif 000003
【図２】
0004975932.tif 000004
【図３】
0004975932.tif 000005