(57)【特許請求の範囲】
【請求項１】
（ａ）照会映像及びモデル映像から直線情報を得る段階と、
（ｂ）照会映像の直線とモデル映像の直線との間の２進の関係を定義する段階と、
（ｃ）２進の関係を基に照会映像及びモデル映像のノード-ラベル対の両立性を表わす両立係数を求める段階と、
（ｄ）両立係数を用いた連続リラックセーションを基に類似度を求める段階とを含むことを特徴とする直線基準の映像整合方法。
【請求項２】
前記直線情報は、各映像の形状記述子で表わされることを特徴とする請求項１に記載の直線基準の映像整合方法。
【請求項３】
前記モデル映像は、
モデル映像の骨格を抽出する段階と、抽出された骨格を基にピクセルの連結を行うことにより直線の集合を求める段階、及び直線の集合を正規化することにより得られた正規化した直線の集合を前記モデル映像の形状記述子として設定する段階を含む形状記述子の抽出方法によりインデクシングされたデータベース内の映像であることを特徴とする請求項１に記載の直線基準の映像整合方法。
【請求項４】
前記２進の関係は、
照会映像とモデル映像との間の回転、スケーリング、移動に対して不変であることを特徴とする請求項１に記載の直線基準の映像整合方法。
【請求項５】
前記２進の関係は、
両直線間の角度の違い、長さ比、相対位置、及び相対距離のうち少なくとも一つを含むことを特徴とする請求項４に記載の直線基準の映像整合方法。
【請求項６】
前記（ｂ）段階は、
（ｂ−１）照会映像の直線集合内の両ノードνｉ，νｊに対する両立性を両立係数ξｉ，ｊで表わす段階と、
（ｂ−２）モデル映像の直線集合内の両ラベルλ，λ′に対する両立性を両立係数ξλλ′で表わす段階と、
（ｂ−３）照会映像及びモデル映像のノード-ラベル対間の両立性を両立係数ｒｉｊ（λ，λ′）で表わす段階とを含むことを特徴とする請求項１に記載の直線基準の映像整合方法。
【請求項７】
前記両立係数ｒｉｊ（λ，λ′）は、
照会映像の直線集合に対してノードνｉにラベルλを割り当てることが周辺ノード-ラベル対（νｉ，λ′）との相関関係を満足させれば大きい値をもち、相互矛盾すれば小さい値をもつように定義されたことを特徴とする請求項６に記載の直線基準の映像整合方法。
【請求項８】
前記両立係数ｒｉｊ（λ，λ′）は、
照会映像内の直線対（ｉ，ｊ）の２進の関係とモデル映像内の直線対（λ，λ′）の２進の関係とが一致する場合には、ｒｉｊ（λ，λ′）＝１が成立つように定義されたことを特徴とする請求項６に記載の直線基準の映像整合方法。
【請求項９】
前記両立係数ｒｉｊ（λ，λ′）は、
Ｋは定義された２進の関係を表わす特徴ベクターのエレメントの数とし、
【数１】
0003559007.tif 000013
としたとき、
【数２】
0003559007.tif 000014
で定義されたことを特徴とする請求項６に記載の直線基準の映像整合方法。
【請求項１０】
前記（ｄ）段階前に、
（ｄ'-１）各ノード-ラベル対に対してノードが周辺のラベルから受けうる最大の支持値の和が最も大きい一定数の上位ノード-ラベル対にだけ同一の確率を適用することにより初期確率を最終の確率に近いように定める段階をさらに含むことを特徴とする請求項１に記載の直線基準の映像整合方法。
【請求項１１】
前記（ｄ'-１）段階後に、
（ｄ'-２）Ｐｊ（ｋ）（λ′）をノード及びラベルが対応する確率とし、Ｋを反復演算の数としたとき、連続リラックセーション技法を具現するための更新要素を
【数３】
0003559007.tif 000015
で定義する段階をさらに含むことを特徴とする請求項１０に記載の直線基準の映像整合方法。
【請求項１２】
前記（ｄ'-２）段階後に、
（ｄ'-３）
【数４】
0003559007.tif 000016
としたとき、収束速度の速いズッカーの方法を基に
【数５】
0003559007.tif 000017
を用いて確率更新を行う段階をさらに含むことを特徴とする請求項１１に記載の直線基準の映像整合方法。
【請求項１３】
前記（ｄ）段階は、
（ｄ-１）両直線集合間の対応するノード間の距離を計算する段階と、
（ｄ-２）全ての距離の和の逆数を両映像の非類似度として設定する段階とを含むことを特徴とする請求項１に記載の直線基準の映像整合方法。
【請求項１４】
前記距離は、
ユークリッド距離またはハウスドルッフ距離であることを特徴とする請求項１３に記載の直線基準の映像整合方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は映像整合方法に係り、より詳細には、直線基準の形状記述子によってインデクシングされた映像データベースから照会映像と類似した形状記述子をもつモデル映像を検索することが適用できる直線基準の映像整合方法に関する。
【０００２】
【従来の技術】
形状記述子（ｓｈａｐｅ  ｄｉｓｃｒｉｐｔｏｒ）は自動抽出可能なより低い抽象的な段階の抽出（ｌｏｗｅｒ  ａｂｓｔｒａｃｔｉｏｎ  ｌｅｖｅｌ  ｄｅｓｃｒｉｐｔｉｏｎ）に基づく、映像から人間が認識できる基本的な記述子と言える。映像から与えられた特定の物体の形状を記述し、かつ前記形状を基に整合または類似度を測定するアルゴリズムが研究されつつある。しかし、前記アルゴリズムは特定の物体の形状を記述するだけであって、一般的な物体の形状を認識するためには多くの問題点が残されている。現在、ＭＰＥＧ−７などの標準化グループで提案している形状記述子は、前記問題を解決するために与えられた物体の各種の変形を通じて特徴点を見出すことにより求められる。このような形状記述子は、その種類が多い。ＭＰＥＧ−７の標準化段階であるＸＭ（ｅＸｐｅｒｉｍｅｎｔ  Ｍｏｄｅｌ）で採択されている形状記述子は代表的に２種類が知られている。その一つは、物体の各種の形状に対して映像内の前記形状の分布を知るためにジェルニク（Ｚｅｒｎｉｋｅ）基底関数を用意し、一定のサイズの映像を各々の基底関数に投影させてその値を記述子として用いるジェルニクモーメント形状記述子（Ｚｅｒｎｉｋｅ  ｍｏｍｅｎｔ  ｓｈａｐｅ  ｄｅｓｃｒｉｐｔｏｒ）が知られている。もう一つは、以前の映像から抽出された外郭線に沿って低周波通過フィルターリングをしつつ、外郭線上に存在する変曲点の変化をスケール空間上で表わしてピーク値とその位置を２次元ベクターで表わす曲率スケール空間形状記述子（Ｃｕｒｖａｔｕｒｅ  ｓｃａｌｅ  ｓｐａｃｅ  ｓｈａｐｅ  ｄｅｓｃｒｉｐｔｏｒ）が知られている。前者の形状記述子を抽出するためには、形状をなす映像と基底関数とが同一のサイズをもたねばならず、形状が円の形をしていなければならないという制限がある。また、後者の形状記述子を抽出するためには、抽出された形状がたった一つの客体でなければならないという短所をもつ。
【０００３】
また、従来の形状記述子を用いた映像整合方法によれば、照会映像と類似した形状記述子をもつモデル映像をデータベースから検索するために映像から物体を正確に抽出することが求められる。しかし、前述のように従来の映像整合方法によれば、物体が正確に抽出されない場合には検索が不可能であるという問題点がある。
したがって、物体の正確な抽出無しにも直線基準の形状記述子によってインデクシングされた映像データベースから照会映像と類似した形状記述子をもつモデル映像を検索できる映像整合方法が望まれる。
【０００４】
【発明が解決しようとする課題】
本発明は上記事情に鑑みて成されたものであり、その目的は、物体の正確な抽出なしにも形状記述子によってインデクシングされたモデル映像データベースから照会映像と類似した形状記述子をもつ映像を検索できる直線基準の映像整合方法を提供するところにある。
【０００５】
【課題を解決するための手段】
前記目的を達成するために、本発明による直線基準の映像整合方法は、（ａ）照会映像及びモデル映像から直線情報を得る段階と、（ｂ）照会映像の直線とモデル映像の直線との間の２進の関係を定義する段階と、（ｃ）２進の関係を基に照会映像及びモデル映像のノード−ラベル対の両立性を表わす両立係数を求める段階と、（ｄ）両立係数を使用した連続リラックセーションを基に類似度を求める段階と、を含むことを特徴とする。
【０００６】
また、好ましくは、前記直線情報は、各映像の形状記述子で表わされる。
また、好ましくは、前記モデル映像は、モデル映像の骨格を抽出する段階と、抽出された骨格を基にピクセルの連結を行うことにより直線の目録を求める段階、及び直線の目録を正規化することにより得られた正規化した直線目録を前記モデル映像の形状記述子として設定する段階とを含む形状記述子の抽出方法によりインデクシングされたデータベース内の映像である。
【０００７】
また、前記２進の関係は、照会映像とモデル映像との間の回転、スケーリング、移動に対して不変である。
また、好ましくは、前記２進の関係は、両直線間の角度の違い、長さ比、相対位置、及び相対距離のうち少なくとも一つを含む。
また、好ましくは、前記（ｂ）段階は、（ｂ−１）照会映像の直線集合内の両ノードνｉ，νｊに対する両立性を両立係数ξｉ，ｊで表わす段階と、（ｂ−２）モデル映像の直線集合内の両ラベルλ，λ′に対する両立性を両立係数ξλλ′で表わす段階と、（ｂ−３）照会映像及びモデル映像のノード−ラベル対間の両立性を両立係数ｒｉｊ（λ，λ′）で表わす段階とを含む。
【０００８】
また、好ましくは、前記両立係数ｒｉｊ（λ，λ′）は、照会映像の直線集合に対してノードνｉにラベルλを割り当てることが周辺ノード−ラベル対（νｉ，λ′）との相関関係を満足させると大きい値をもち、相互矛盾すれば小さい値をもつように定義される。
また、好ましくは、前記両立係数ｒｉｊ（λ，λ′）は、照会映像内の直線対（ｉ，ｊ）の２進の関係とモデル映像内の直線対（λ，λ′）の２進の関係とが一致する場合には、ｒｉｊ（λ，λ′）＝１が成立つように定義される。
【０００９】
また、好ましくは、前記両立係数ｒｉｊ（λ，λ′）は、  Ｋを定義された２進の関係を表わす特徴ベクターのエレメントの数とし、
【数６】
0003559007.tif 000002
としたとき、
【数７】
0003559007.tif 000003
で定義される。
また、好ましくは、前記（ｄ）段階前に、（ｄ’−１）各ノード−ラベル対に対してノードが周辺のラベルから受けうる最大の支持値の和が最も大きい一定数の上位ノード−ラベル対にだけ同一の確率を適用することにより初期の確率を最終の確率に近いように定める段階をさらに含む。
【００１０】
また、好ましくは、前記（ｄ’−１）段階後に、（ｄ’−２）Ｐｊ（ｋ）（λ′）をノード及びラベルが対応する確率とし、Ｋを反復演算の数としたとき、連続リラックセーション技法を具現するための更新要素を
【数８】
0003559007.tif 000004
と定義する段階をさらに含む。
また、好ましくは、前記（ｄ’−２）段階後に、（ｄ’−３）
【数９】
0003559007.tif 000005
としたとき、収束速度の速いズッカーの方法を基に
【数１０】
0003559007.tif 000006
を用いて確率更新を行う段階をさらに含む。
【００１１】
また、好ましくは、前記（ｄ）段階は、（ｄ−１）両直線集合間の対応するノード間の距離を計算する段階と、（ｄ−２）全ての距離の和の逆数を両映像の非類似度として設定する段階とを含む。
また、好ましくは、前記距離は、ユークリッド距離またはハウスドルッフ距離である。
【００１２】
【発明の実施の形態】
以下、添付した図面に基づき本発明の望ましい実施形態について詳細に説明する。
図１は、本発明の実施形態による直線基準の映像整合方法の主な段階を示したフローチャートである。図１を参照すると、先ず、照会映像及びモデル映像から直線情報を得る（ステップ１０２）。ここで、モデル映像は所定のデータベース内に貯蔵されており、前記データベース内のモデル映像は直線基準の形状記述子によってインデクシングされていると仮定する。前記直線基準の形状記述子は本出願人によって２０００年１０月２１日付けで出願され、本明細書に参照として統合される大韓民国特許出願００−６２１６３号に開示された形状記述子の抽出方法によって抽出されることが可能である。また、前述のような形状記述子の抽出方法によって照会映像から形状記述子を抽出できる。前記形状記述子の抽出方法によって抽出された形状記述子は直線の目録を含む。これにより、照会映像及びモデル映像から直線情報を得ることができる。
【００１３】
次に、照会映像の直線とモデル映像の直線との間の２進の関係を定義する（ステップ１０４）。直線基準の整合システムでは直線の傾斜または長さ、重点の位置などの直線固有の単一属性と、両直線間の角度の違い、長さ比、相対位置、及び相対距離などの２進の関係を直線の特徴として用いることができる。本実施形態では照会映像とモデル映像との回転、スケーリング、移動に対して不変である２進の関係を直線の特徴として用いる。図２（ａ）は、両直線の傾斜の違いを２進の関係として用いる例を説明するための図である。図２（ａ）を参照すると、両直線の傾斜の違いθを両直線の相対的な姿勢として表わすことができる。また、図２（ｂ）は、両直線の重点よりなる直線と１本の直線とがなす角度φを２進の関係として用いる例を説明するための図である。図２（ｂ）を参照すると、両直線の重点よりなる直線と１本の直線とがなす角度φを両直線の相対的な位置で表わすことができる。また、本明細書において、図面には示していないが、両直線間の長さ比ｒを２進の関係として用いることもできる。
【００１４】
本発明では、連続リラックセーションを基に照会映像内の直線集合とモデル映像の直線集合との対応性を決定することにより、直線基準の映像整合を行う。連続リラックセーションを具現するとき、確率の更新は両立係数及び現在のラベリング状態に依存する。初期の確率が設定された後には確率の更新方向は両立係数によって決定される。両立係数は与えられた整合状況をモデリングすることにより目標とするラベリングを得させるような役目をするため、実際の状況を正確に反映させることが重要である。
【００１５】
次に、ステップ１０４で定義された２進の関係を基に照会映像及びモデル映像のノード−ラベル対の両立性を表わす両立係数を求める（ステップ１０６）。ステップ１０６は、下記のような手順によって定義される。先ず、照会映像の直線集合内の両ノードνｉ，νｊに対する両立性を両立係数ξｉｊで表わす。また、モデル映像の直線集合内の両ラベルλ，λ′に対する両立性を両立係数ξλλ′で表わす。また、照会映像とモデル映像のノード−ラベル対との間の両立性を両立係数ｒｉｊ（λ，λ′）で表わす。ここで、前記両立係数ｒｉｊ（λ，λ′）は、照会映像及びモデル映像の２進の関係を用いて両立係数が０と１との間に置かれるように設定する。また、照会映像の直線集合に対してノードνｉにラベルλを割り当てることが周辺ノード−ラベル対（νｉ，λ′）との相関関係を満足させれば大きい値をもち、相互矛盾すれば小さい値をもつように定義される。すなわち、ノード−ラベル対（νｉ，λ′）との相互関係を考慮するとき、ノードνｉにラベルλ２の方よりはλ１を割り当てることがより妥当な場合には、
【数１１】
0003559007.tif 000007
が成立つように定義される。また、前記両立係数ｒｉｊ（λ，λ′）は、照会映像内の直線対（ｉ，ｊ）の２進の関係とモデル映像内の直線対（λ，λ′）の２進の関係とが一致する場合には、ｒｉｊ（λ，λ′）＝１が成立つように定義される。本実施形態では、前記両立係数ｒｉｊ（λ，λ′）は、Ｋを定義された２進の関係を表わす特徴ベクターのエレメントの数とし、
【数１２】
0003559007.tif 000008
としたとき、
【数１３】
0003559007.tif 000009
として定義される。前式２のｐはノード−ラベル対の相関関係の違いを反映する。
【００１６】
次に、両立係数を用いた連続リラックセーションを基に類似度を求める（ステップ１０８）。連続リラックセーションを具現するとき、確率の更新は両立係数及び現在のラベリング状態だけに全く依存する。初期の確率が設定された後には確率の更新方向は両立係数によって決定される。両立係数は与えられた整合状況をモデリングすることにより目標とするラベリングを得させる役目をするため、実際の状況が正確に反映させることが重要である。ステップ１０８は、両立係数を用いた連続リラックセーションによる確率更新段階、正規化段階、及び類似度の測定段階に大別される。先ず、両立係数を用いた連続リラックセーションによる確率更新段階について説明する。先ず、各ノード−ラベル対に対してノードが周辺のラベルから受けうる最大の支持値の和が最も大きい一定数の上位ノード−ラベル対にだけ同一の確率を適用することにより初期の確率を最終の確率に近いように定める。
【００１７】
次に、Ｐｊ（ｋ）（λ′）をノードとラベルとが対応する確率とし、Ｋを反復演算の数としたとき、連続リラックセーション技法を具現するための更新要素を
【数１４】
0003559007.tif 000010
と定義する。次に、
【数１５】
0003559007.tif 000011
としたとき、収束速度の速いズッカーの方法を基に、
【数１６】
0003559007.tif 000012
を用いて確率更新を行う。
【００１８】
しかし、特徴ベクターの各エレメントの値が存在する範囲に違いが出るため、これに対する正規化が必要である。したがって、正規化を行う。リラックセーションを通じて得た対応関係は整合される直線情報を明確に表わす。したがって、照会映像の直線のうち一本の直線を選択し、この直線に対して残りの直線情報を大きさと位置に対して正規化する。正規化過程では、まず、照会映像の直線の集合のうち任意の一本の直線を選択する。次に、選択された直線の長さが１となり、直交座標系のｘ軸上に来るように空間変換関数を定義する。次に、定義された空間変換関数を用いて照会映像の全ての直線情報を変換する。次に、モデル映像の直線のうち照会映像の選択された直線と対応する直線に対して前記過程を反復する。
【００１９】
次に、類似度を測定する。対応したモデル映像の直線に対しても照会映像の選択された直線と対応する直線を基準として対応するノード間の距離の和を求めることにより類似度を得る。類似度を測定する方法は様々である。対応関係が明確であり、かつ、回転及びスケーリングに対して正規化がなされた場合には簡単にノード間のユークリッド距離を直接的に求めることができる。また、代案的に、ハウスドルッフ距離を測定することにより、より精度良く類似度を測定することができる。本実施形態では次のような過程によって両映像の類似度を求める。先ず、両直線集合の間の対応するノード間のユークリッド距離を計算する。次に、全ての距離の和の逆数を両映像の非類似度として設定する。非類似度が小さければ類似度は大きい。したがって、類似度の大きい映像を検索された映像として選択する（ステップ１１０）。
【００２０】
前述のような直線基準の映像整合方法を基に模擬実験を行った。模擬実験では照会映像から境界線を抽出し、抽出された境界線を直線近似化することにより直線近似化した映像を得る。次に、使用者が照会映像から抽出された直線の一部を選択し、選択された直線情報を用いてモデル映像との整合を行う。図３（ａ）には照会映像の一例を示した。また、図３（ｂ）には図３（ａ）の照会映像の直線近似化した映像を示した。さらに、図３（ｃ）には問い合わせのために使用者によって一部のラインが選択された直線映像を示した。
【００２１】
図４（ａ）には模擬実験によって検索されたモデル映像の一例を示し、図４（ｂ）には図４（ａ）のモデル映像の直線近似化した映像を示した。図４（ｂ）を参照すると、検索されたモデル映像の直線近似化した映像は図３（ｃ）に示した照会映像の直線と類似した直線４０２を含む。
また、図５（ａ）には検索されたモデル映像の他の例を示し、図５（ｂ）には図５（ａ）のモデル映像の直線近似化した映像を示した。図５（ｂ）を参照すると、検索されたモデル映像の直線近似化した映像は図３（ｃ）に示した照会映像の直線と類似した直線５０２を含む。
前述のような直線基準の映像整合方法によれば、物体の正確な抽出なしにも直線基準の形状記述子によってインデクシングされた映像データベースから照会映像と類似した形状記述子をもつモデル映像を検索することができる。
【００２２】
【発明の効果】
また、前述のように、本発明による直線基準の映像整合方法は、個人向けまたはサーバ級のコンピュータ内にて実行されるプログラムで作成可能である。前記プログラムを構成するプログラムコード及びコードセグメントは当該分野のコンピュータプログラマーによって容易に推論できる。また、前記プログラムはコンピュータにて読取り可能な媒体に貯蔵できる。前記記録媒体は磁気記録媒体、光記録媒体、及び電波媒体を含む。
以上述べたように、本発明による直線基準の映像整合方法は、物体の正確な抽出なしにも直線基準の形状記述子によってインデクシングされた映像データベースから照会映像と類似した形状記述子をもつモデル映像を検索することができる。
【図面の簡単な説明】
【図１】本発明の実施形態による直線基準の映像整合方法の主な段階を示したフローチャートである。
【図２】図２（ａ）は、両直線の傾斜の違いを２進の関係として用いる例を説明するための図であり、図２（ｂ）は、両直線の重点よりなる直線と１本の直線とがなす角度を２進の関係として用いる例を説明するための図である。
【図３】図３（ａ）は照会映像の一例を示した図であり、図３（ｂ）は図３（ａ）の照会映像の直線近似化した映像を示した図であり、図３（ｃ）は問い合わせのために使用者によって一部のラインが選択された直線映像を示した図である。
【図４】図４（ａ）は模擬実験によって検索されたモデル映像の一例を示した図であり、図４（ｂ）は図４（ａ）のモデル映像の直線近似化した映像を示した図である。
【図５】図５（ａ）は検索されたモデル映像の他の例を示した図であり、図５（ｂ）は図５（ａ）のモデル映像の直線近似化した映像を示した図である。
【符号の説明】
４０２，５０２…直線
【図１】
0003559007.tif 000018
【図２】
0003559007.tif 000019
【図３】
0003559007.tif 000020
【図４】
0003559007.tif 000021
【図５】
0003559007.tif 000022