(57)【特許請求の範囲】
【請求項１】
（ａ）入力された映像から骨格を抽出する段階と、
（ｂ）抽出された骨格に基づきピクセル間の連結を行うことによりラインセグメントのセットを求める段階と、
（ｃ）ラインセグメントのセットを正規化することにより得られた正規化したラインセグメントのセットを形状記述子として設定する段階とを含み、
前記（ａ）段階は、
（ａ−１）入力された映像に対して距離変換を行うことにより距離マップを求める段階と、
（ａ−２）求められた距離マップ上で骨格を抽出する段階と
を含み、
前記（ｂ）段階は、
（ｂ-１）抽出された骨格を細線化する段階と、
（ｂ-２）細線化した骨格内の各ピクセルの連結を行うことによりラインセグメントを抽出する段階とを含み、
前記（ａ-２）段階は、
エッジ検出方法を利用して距離マップから局部最大を得る段階を含み、
前記（ａ-２）段階は、
（ａ-２-１）局部最大を得るために４方向の局部最大検出マスクを使用してたたみこみを行う段階を含み、
前記（ａ-２-１）段階後に、（ａ-２-２）最も大きい結果の方向に該当するラベルを方向マップ及び大きさマップに記録する段階をさらに含み、
前記（ｂ-１）段階は、前記方向マップで該当方向の所定角度回転された方向で最も大きいピクセルだけを残し、残りのピクセルは除去する段階を含むことを特徴とする形状記述子抽出方法。
【請求項２】
前記（ｃ）段階は、
（ｃ-１）連結されたラインセグメントの開始点及び終点についてのセットを作成する段階と、
（ｃ-２）抽出されたラインセグメントのラインセグメントの併合によりラインセグメントのセットを求める段階と、
（ｃ-３）各ラインセグメントの終点間の最大距離に対してラインセグメントのセットを正規化することにより得られたラインセグメントのセットを形状記述子として設定する段階とを含むことを特徴とする請求項１に記載の形状記述子抽出方法。
【請求項３】
前記距離変換は、
物体の内部の各点を背景から最短距離の値で表す関数に基づくことを特徴とする請求項１に記載の形状記述子抽出方法。
【請求項４】
前記入力された映像は、２進映像であることを特徴とする請求項１に記載の形状記述子抽出方法。
【請求項５】
前記（ｃ-２）段階は、４方向の方向マップを使用し、方向マップで同一のラベルを有するピクセル同士を連結して各々の線セグメントの開始点及び終点をついてのセットを作成する段階を含むことを特徴とする請求項１に記載の形状記述子抽出方法。
【請求項６】
前記（ｃ-２）段階は、得られたラインセグメントのセットから各ラインセグメント間の角度、距離、及びラインセグメントの長さに対するしきい値を変えつつラインセグメントの併合を行う段階を含むことを特徴とする請求項１に記載の形状記述子抽出方法。
【請求項７】
前記ラインセグメントの併合は、残ったラインセグメントの本数が所定の本数以下になるまで繰り返されることを特徴とする請求項６に記載の形状記述子抽出方法。
【請求項８】
問合わせ映像と類似した形状を有する映像を検索する方法において、
（ａ）問合わせ映像から抽出された骨格に基づく形状記述子からラインセグメントのセットを得る段階と、
（ｂ）検索される映像の形状記述子のラインセグメントのセットと問合わせ映像の形状記述子のラインセグメントのセットとを比較することにより非類似度を求める段階と、
（ｃ）求めた非類似度に基づき問合わせ映像と類似した形状特徴を有する映像を検索する段階とを含み、
前記（ａ）段階は、
（ａ−１）入力された映像に対して距離変換を行うことにより距離マップを求める段階と、
（ａ−２）求められた距離マップ上で骨格を抽出する段階と
を含み、
前記（ａ）段階は、
（ａ’-１）抽出された骨格を細線化する段階と、
（ａ’-２）細線化した骨格内の各ピクセルの連結を行うことによりラインセグメントを抽出する段階とをさらに含み、
前記（ａ-２）段階は、
エッジ検出方法を利用して距離マップから局部最大を得る段階を含み、
前記（ａ-２）段階は、
（ａ-２-１）局部最大を得るために４方向の局部最大検出マスクを使用してたたみこみを行う段階を含み、
前記（ａ-２-１）段階後に、（ａ-２-２）最も大きい結果の方向に該当するラベルを方向マップ及び大きさマップに記録する段階をさらに含み、
前記（ａ’-１）段階は、前記方向マップで該当方向の所定角度回転された方向で最も大きいピクセルだけを残し、残りのピクセルは除去する段階を含むことを特徴とする映像検索方法。
【請求項９】
前記（ｂ）段階は、
（ｂ-１）骨格をなすラインセグメントの終点間の距離を測定する段階と、
（ｂ-２）測定された距離の最小値の合計を非類似度として設定する段階とを含むことを特徴とする請求項８に記載の映像検索方法。
【請求項１０】
前記（ｂ-１）段階は、
Ｑは検索しようとするラインセグメント、Ｍは検索されるラインセグメント、Ｓはラインセグメントの開始点、Ｅはラインセグメントの終点、ＮQは問合わせ映像の形状記述子が有するラインセグメントの総数、ＮMは検索される映像の形状記述子が有するラインセグメントの総数であり、Ｎは
【数１】
0004018354.tif 000006
としたとき、骨格をなすラインセグメントの終点間の距離を
【数２】
0004018354.tif 000007
により計算する段階を含み、前記（ｂ-２）段階は、
【数３】
0004018354.tif 000008
で定義される非類似度特定関数を使用して測定する段階を含むことを特徴とする請求項８に記載の映像検索方法。
【請求項１１】
回転によって変わらない値を得るために一定の回転角度間隔で前記（ｂ-１）段階及び（ｂ-２）段階により類似度測定を行うことを特徴とする請求項１０に記載の映像検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は形状記述子を抽出する方法に係り、より詳細には、骨格に基づく形状記述子を抽出する方法に関する。
【０００２】
【従来の技術】
形状記述子(shape descriptor)は、自動抽出可能なより低い抽象的な段階の抽出に基づくものであって、映像から人間が認識できる基本的な記述子と言える。映像から与えられた特定物体の形状を記述し、前記形状に基づき整合または類似度を測定するアルゴリズムが研究されている。しかし、前記アルゴリズムは特定物体の形状を記述するに留まっており、一般的な物体の形状を認識するためには多くの問題点が残っている。現在、ＭＰＥＧ-７などの標準化グループで提案している形状記述子は、前記問題を解決するために、与えられた物体の各種の変形を通じて特徴点を探すことにより求められる。このような形状記述子は、その種類が多い。ＭＰＥＧ-７の標準化段階であるＸＭ（eXperiment Model）で採択されている形状記述子は、代表的に２種類が知られている。第一に、物体の各種の形状に対して映像内の前記形状の分布を知るためにゼルニック基底関数(Zernike base function)を準備し、一定の大きさの映像を各々の基底関数に投影させてその値を記述子として使用するゼルニックモーメント形状記述子が知られている。第二に、以前の映像から抽出された外郭線に沿って低周波通過フィルターリングをしつつ外郭線上に存在する変曲点の変化をスケール空間上で表わしてピーク値(peak value)及びその位置を２次元ベクトルで表わす曲率スケール空間形状記述子が知られている。前者の形状記述子を抽出するためには、形状をなす映像及び基底関数が同一の大きさを有する必要があり、形状が円の形を有さねばならないという制限がある。また、後者の形状記述子を抽出するためには、抽出された形状が単一の客体でなければならないという短所を持つ。
【０００３】
【発明が解決しようとする課題】
本発明が達成しようとする技術的な課題は、動映像圧縮技術及びその技術に基づく映像検索技術に効率良く適用できる形状記述子抽出方法を提供することである。
【０００４】
本発明が達成しようとする他の技術的な課題は、前記形状記述子抽出方法によって抽出された形状記述子を使用してインデクシングされた映像内において問合わせ映像と類似した形状特徴を有する映像を検索する映像検索方法を提供することである。
【０００５】
本発明が達成しようとするさらに他の技術的な課題は、前記形状記述子抽出方法によって抽出された形状記述子を使用してインデクシングされた映像間の非類似度を測定する非類似度測定方法を提供することである。
【０００６】
【課題を解決するための手段】
前記課題を達成するために、本発明の一側面による形状記述子抽出方法は、（ａ）映像の骨格を抽出して抽出された骨格に基づき形状記述子を設定する段階を含むことを特徴とする。
【０００７】
また、前記課題を達成するために、本発明の他の側面による形状記述子抽出方法は、（ａ）入力された映像から骨格を抽出する段階と、（ｂ）抽出された骨格に基づきピクセル間の連結を行うことによりラインセグメントのセット(a set of line segments)を求める段階と、（ｃ）ラインセグメントのセットを正規化することにより得られた正規化したラインセグメントのセットを形状記述子として設定する段階とを含むことを特徴とする。
【０００８】
また、前記（ａ）段階は、（ａ-１）入力された映像に対して距離変換を行うことにより距離マップを求める段階と、（ａ-２）求められた距離マップ上で骨格を抽出する段階とを含むことが望ましい。
【０００９】
また、前記（ｂ）段階は、（ｂ-１）抽出された骨格を細線化する段階と、（ｂ-２）細線化した骨格内の各ピクセルの連結を行うことによりラインセグメントを抽出する段階とを含むことが望ましい。
【００１０】
また、前記（ｃ）段階は、（ｃ-１）連結されたラインセグメントの開始点及び終点についてのセットを作成する段階と、（ｃ-２）抽出されたラインセグメントのラインセグメントの併合(merging of the line segments)によりラインセグメントのセットを求める段階と、（ｃ-３）各ラインセグメントの終点間の最大距離に対してラインセグメントのセットを正規化することにより得られたラインセグメントのセットを形状記述子として設定する段階とを含むことが望ましい。
【００１１】
また、前記距離変換は、物体の内部の各点を背景から最短距離の値で表わす関数に基づくことが望ましい。
また、前記（ａ-２）段階は、エッジ検出方法を利用して距離マップから局部最大を得る段階を含むことが望ましい。
【００１２】
また、前記（ａ-２）段階は、（ａ-２-１）局部最大を得るために４方向の局部最大検出マスクを使用してたたみこみ(convolution)を行う段階を含むことが望ましい。
また、前記（ａ-２-１）段階後に、（ａ-２-２）最も大きい結果の方向に該当するラベルを方向マップ及び大きさマップに記録する段階をさらに含むことが望ましい。
【００１３】
また、前記入力された映像は、２進映像であることが望ましい。
また、前記（ｂ-１）段階は、方向マップで該当方向の９０°回転された方向で最も大きいピクセルだけを残し、残りのピクセルは除去する段階を含むことが望ましい。
【００１４】
また、前記（ｃ-２）段階は、４方向の方向マップを使用し、方向マップで同一のラベルを有するピクセル同士を連結して各々の線セグメントの開始点及び終点についてのセットを作成する段階を含むことが望ましい。
【００１５】
また、前記（ｃ-２）段階は、得られたラインセグメントのセットから各ラインセグメント間の角度、距離、及びラインセグメントの長さに対するしきい値を変えつつラインセグメントの併合を行う段階を含むことが望ましい。
また、前記ラインセグメントの併合は、残ったラインセグメントの本数が所定の本数以下になるまで繰り返されることが望ましい。
【００１６】
さらに、前記他の課題を達成するために、本発明による映像検索方法は、（ａ）問合わせ映像の形状記述子からラインセグメントのセットを得る段階と、（ｂ）検索される映像の形状記述子のラインセグメントのセットと問合わせ映像の形状記述子のラインセグメントのセットとを比較することにより非類似度を求める段階と、（ｃ）求めた非類似度に基づき問合わせ映像と類似した形状特徴を有する映像を検索する段階とを含むことを特徴とする。
【００１７】
また、前記さらに他の課題を達成するために、本発明による非類似度測定方法は、骨格に基づきなされた形状記述子を使用してインデクシングされた映像間の非類似度を測定する方法において、（ａ）問合わせ映像の形状記述子からラインセグメントのセットを得る段階と、（ｂ）検索される映像の形状記述子のラインセグメントのセットと問合わせ映像の形状記述子のラインセグメントのセットとを比較することにより非類似度を求める段階とを含むことを特徴とする。
【００１８】
【発明の実施の形態】
以下、添付した図面に基づき、本発明の望ましい実施形態について詳細に説明する。
本発明によれば、骨格を使用した形状記述子が定義される。骨格を使用した形状記述子は、与えられた形状から人間の認識で最も基礎となる線を抽出し、抽出された線を簡略化することにより簡略化された線を形状記述子として表現する。特に、前記のような形状記述子抽出方法によれば、エッジ部分よりは骨格を抽出することにより記述子をできる限り簡略化することが可能である。
【００１９】
図３は、本発明の実施形態による形状記述子抽出方法の主な段階を示したフローチャートである。図３を参照すれば、本発明の実施形態による形状記述子抽出方法では、先ず、映像を入力（ステップ１０２）して、入力された映像に対し距離変換を行うことにより距離マップを求める（ステップ１０４）。距離マップを得るための距離変換は、物体の内部の各点を背景から最短距離の値で表わす関数を使用する。次に、距離マップ上で骨格を抽出する（ステップ１０６）。距離マップの局部最大が骨格をなす点であるということはよく知られている。距離マップを得るための距離変換は、物体の内部の各点を背景から最短距離の値で表わす関数に基づく。この実施形態では、距離変換によって距離マップの局部最大に該当する部分を骨格として設定する。距離マップから局部最大を得るために、この実施形態では、本明細書に参照として統合される、アール・ネバシア(R.Nevatia)とケイ・アール・バブ(K.R.Babu)による"Linear Feature Extraction and Description（線形特徴抽出及び記述）"というタイトルの資料(Computer Graphics and Image Processing,Vol.13,pp.257-269,1980)で使用されたエッジ検出方法を使用できる。図２Ａないし図２Ｄは、局部最大を検出するためのマスクの例を示している。図２Ａないし図２Ｄを参照すれば、局部最大を検出するために４方向の局部最大検出マスクを使用する。図２Ａは、０°の方向に該当するマスクである。図２Ｂは、４５°の方向に該当するマスクである。図２Ｃは、９０°の方向に該当するマスクである。図２Ｄは、１３５°の方向に該当するマスクである。次に、前記マスクを使用してたたみこみを行う。その結果、最も大きい結果の方向に該当するラベルを方向マップ及び大きさマップに記録する。これにより、図３Ａに示した２進映像から距離変換を通じて得られた距離マップで局部最大を得ることにより、骨格を抽出する。
【００２０】
次に、抽出された骨格を細線化する（ステップ１０８）。細線化は、例えば、方向マップで該当方向の９０°回転された方向で最も大きいピクセルだけを残し、残りのピクセルは除去することにより行われる。図３Ｄは、細線化された骨格化映像の一例を示している。
【００２１】
次に、細線化された骨格内の各ピクセルの連結によりラインセグメントを抽出する（ステップ１１０）。すなわち、細線化された骨格内の各ピクセルを一つの方向に沿って連結し、その開始点及び終点についてのセットを作成することによりラインセグメントを抽出する。この実施形態では、図２Ａないし図２Ｄに示した４方向の方向マップを使用し、方向マップで同一のラベルを有するピクセル同士を連結して各々の線セグメントの開始点及び終点についてのセットを作成する。
【００２２】
次に、抽出されたラインセグメントのラインセグメントの併合によりラインセグメントのセットを得る（ステップ１１２）。すなわち、得られたラインセグメントのセットから各ラインセグメント間の角度、距離、及びラインセグメントの長さに対するしきい値を変えつつラインセグメントの併合を行う。前記ラインセグメントの併合は残ったラインセグメントの本数が所定の本数以下になるまで繰り返される。図３Ｅには、ラインセグメントに近似化された結果を示している。次に、各ラインセグメントの終点間の最大距離に対しラインセグメントのセットを正規化することにより得られたラインセグメントのセットを形状記述子として設定する（ステップ１１４）。すなわち、前記のような形状記述子抽出方法によれば、２進映像の骨格を抽出して抽出された骨格を形状記述子として使用する。
【００２３】
前記形状記述子抽出方法によれば、２進映像の骨格を形状記述子として抽出し、抽出された形状記述子は映像の併合に使用できる。また、前記形状記述子抽出方法では２進映像から骨格を抽出し、抽出された骨格をラインセグメントに近似化する。また、効率良いラインセグメント抽出のために２進映像を距離変換して局部最大を求めることにより骨格を抽出する。抽出された骨格はエッジ抽出方法を使用して一定本数のラインセグメントに近似化される。近似化されたラインセグメントの数は一定の本数に制限されることにより、より速い整合が行えるようにする。
【００２４】
以下では、前記のような形状記述子抽出方法によってインデクシングされた映像を貯蔵するデータベースから問合わせ映像と類似した映像を検索するための方法を説明する。また、図１を参照して説明された形状記述子抽出方法によって抽出された形状記述子を使用してインデクシングされた映像を含む映像データベース内において問合わせ映像の形状と類似した映像を検索するときの検索性能を評価することにより、前記形状記述子抽出方法の効果を述べる。
【００２５】
図６は、本発明による映像検索方法の主な段階を示したフローチャートである。先ず、問合わせ映像（待ち映像）の形状記述子からラインセグメントのセットを得る（ステップ４０２）。次に、検索される映像の形状記述子のラインセグメントのセットと問合わせ映像の形状記述子のラインセグメントのセットとを比較することにより非類似度を求める（ステップ４０４）。
【００２６】
この実施形態では、骨格をなすラインセグメントの終点間の距離を測定し、測定された距離の最小値の合計を非類似度値として設定する。非類似度特定関数は、Ｎ、Ｄ1k及びＤ2kを各々、
【００２７】
【数４】
0004018354.tif 000002
【００２８】
【数５】
0004018354.tif 000003
【００２９】
【数６】
0004018354.tif 000004
【００３０】
としたとき、
【００３１】
【数７】
0004018354.tif 000005
である。
【００３２】
ここで、Ｑは検索しようとするラインセグメント、Ｍは検索されるラインセグメント、Ｓはラインセグメントの開始点、Ｅはラインセグメントの終点、ＮQは問合わせ映像の形状記述子が有するラインセグメントの総数、ＮMは検索される映像の形状記述子が有するラインセグメントの総数である。
【００３３】
前式（７）を参照すれば、式（５）及び式（６）により測定されたラインセグメント間の距離の最小値の合計が二つの記述子の非類似度として設定される。すなわち、前記式（７）の結果値が小さいほど二つの物体が類似すると決定される。また、一定の回転角度間隔で前記のような測定を行うことにより、回転によって変わらない値が得られもする。
【００３４】
次に、ステップ４０４で求めた非類似度に基づき、問合わせ映像と類似した形状特徴を有する映像を検索する。検索される映像のうち問合わせ映像に対する非類似度が最も小さい映像が検索された映像として決定される。このように非類似度に基づき映像を検索する技法を整合技法と呼び、検索された映像は整合映像と呼ぶ。
【００３５】
前記のような方法の性能を評価するために、ＭＰＥＧ-７標準のＸＭ(eXperimental Model)バージョンで実験映像として使用される２進映像に対し模擬実験を行った。ラインセグメントの併合のための各種のしきい値は経験的に定めた。ラインセグメントの併合は３０°以下の角度だけでなされるようにし、かつ、併合がなされる二本のラインセグメントの終点間の距離は実際映像の横、縦長さのうち小さい値の５％、ラインセグメントの併合後に無視されるラインセグメントの長さは横、縦長さのうち大きい値の１％と定めた。また、毎繰り返し遂行時ごとにそのしきい値を１０％ずつ増やしつつ、ラインセグメントの数を１０本以下にした。実験結果を図５及び図６に示す。図５を参照すれば、本発明による映像検索方法は全く分類されない映像から問合わせ映像と類似した形状を有する映像を検索するときにはあまり良好でない検索性能を示している。これは、ラインセグメントへの近似化過程で詳細な部分の情報を失うからである。また、図６を参照すれば、分類された映像、すなわち、同一のカテゴリー内のデータ集合から問合わせ映像と類似した形状を有する映像を検索するときには極めて良好な検索性能を示している。したがって、前記形状記述子抽出方法は、同一のカテゴリー内のデータ集合において局部的な動きを抽出するに当たって有利であるということが分かる。同一の物体の部分的な動きを検出するに当たって有利である理由は、本発明の形状記述子抽出方法によって抽出された形状記述子は映像内に含まれている形状の概略的な様子に関する情報をそのまま有しているからであると理解できる。
【００３６】
以上の実施形態では、図１を参照して述べた形状記述子抽出方法によりインデクシングされた映像に対して問合わせ映像と類似した形状を有する映像を検索する方法について説明した。しかし、前記映像検索方法において、問合わせ映像と検索される映像との間の非類似度を測定する段階は、測定された非類似度に基づき類似した形状を有する映像をクラスタリングする分野などにも適用できる。
【００３７】
前記のような形状記述子抽出方法は、客体基盤の圧縮記述子であるＭＰＥＧ-４、ＭＰＥＧ-７、及びＭＰＥＧ-２１などの標準に基づく動映像圧縮技術に適用できる。また、前記動映像圧縮技術に基づく映像検索技術に効率良く適用できる。
【００３８】
【発明の効果】
以上述べたように、本発明による形状記述子抽出方法によって抽出された形状記述子は、映像内に含まれている形状の概略的な様子に関する情報をそのまま有しているため、同一のカテゴリー内のデータ集合において局部的な動きを効率良く抽出する。また、前記形状記述子抽出方法によってインデクシングされた映像データベース内において問合わせ映像と類似した形状を有する映像を検索する本発明による映像検索方法は、分類された映像から問合わせ映像と類似した形状を有する映像を検索するとき、検索性能が極めて良好である。
【００３９】
また、前記のように、本発明による形状記述子抽出方法及び映像検索方法は、個人向けまたはサーバ級のコンピュータ内にて実行されるプログラムにて作成可能である。前記プログラムを構成するプログラムコード及びコードセグメントは当該分野のコンピュータプログラマーによって容易に推論できる。また、前記プログラムはコンピュータにて読取り可能な記録媒体に貯蔵できる。前記記録媒体は磁気記録媒体、光記録媒体、及び電波媒体(radio media)を含む。
【図面の簡単な説明】
【図１】  本発明の実施形態による形状記述子抽出方法の主な段階を示したフローチャートである。
【図２Ａ】  局部最大を検出するためのマスクの例を示した図であり、０°の方向に該当するマスクである。
【図２Ｂ】  局部最大を検出するためのマスクの例を示した図であり、４５°の方向に該当するマスクである。
【図２Ｃ】  局部最大を検出するためのマスクの例を示した図であり、９０°の方向に該当するマスクである。
【図２Ｄ】  局部最大を検出するためのマスクの例を示した図であり、１３５°の方向に該当するマスクである。
【図３Ａ】  ２進映像の例を示した図である。
【図３Ｂ】  白黒映像からスケーリングされた距離マップを示した図である。
【図３Ｃ】  骨格化映像を示した図である。
【図３Ｄ】  細線化された骨格化映像を示した図である。
【図３Ｅ】  ラインセグメントに近似化された結果を示した図である。
【図４】  本発明の実施形態による形状記述子基盤の映像検索方法の主な段階を示したフローチャートである。
【図５】  本発明による映像検索方法の性能を評価するためにＭＰＥＧ-７標準のＸＭバージョンで実験映像として使用される２進映像に対して模擬実験を行った結果を示した図である。
【図６】  本発明による映像検索方法の性能を評価するためにＭＰＥＧ-７標準のＸＭバージョンで実験映像として使用される２進映像に対して模擬実験を行った結果を示した図である。
【図１】
0004018354.tif 000009
【図２Ａ】
0004018354.tif 000010
【図２Ｂ】
0004018354.tif 000011
【図２Ｃ】
0004018354.tif 000012
【図２Ｄ】
0004018354.tif 000013
【図３Ａ】
0004018354.tif 000014
【図３Ｂ】
0004018354.tif 000015
【図３Ｃ】
0004018354.tif 000016
【図３Ｄ】
0004018354.tif 000017
【図３Ｅ】
0004018354.tif 000018
【図４】
0004018354.tif 000019
【図５】
0004018354.tif 000020
【図６】
0004018354.tif 000021