(57)【要約】【課題】  動画像処理の技術分野において蓄積された映像の移動物体抽出、スプライト符号化の前処理に必要なカメラワークパラメータ算出方法、この方法を実施する装置、プログラムおよびその記録媒体を提供する。【解決手段】  映像中のフレーム画像から特徴となる点を代表点として算出する代表点算出部１０４と、或るフレーム画像の代表点に対応する点を他のフレーム画像から算出する対応点算出部１０５と、画像の点対応関係の組を冗長に用いて例外値判定を行ない、例外値を除いたカメラワークパラメータを算出するカメラワークパラメータ算出部１０６と、代表点の算出が必要か否かを判定する代表点算出判定部１０７と、フレーム画像と代表点を更新するフレーム画像更新部１０３とを具備したカメラワークパラメータ算出方法、装置、プログラム、記録媒体。【選択図】  図１
2006190176.tif 000002
【特許請求の範囲】
【請求項１】
映像中のフレーム画像から特徴となる点を代表点として算出する代表点算出部と、或るフレーム画像の代表点に対応する点を他のフレーム画像から算出する対応点算出部と、画像の点対応関係の組を冗長に用いて信頼度判定を行ない、信頼度の低い点対応の組を除いてカメラワークパラメータを算出するカメラワークパラメータ算出部と、代表点の算出が必要かどうかを判定する代表点算出判定部と、フレーム画像と代表点を更新するフレーム画像更新部とを具備したカメラワークパラメータ算出装置。
【請求項２】
映像中のフレーム画像から特徴となる点を代表点として算出する代表点算出部と、或るフレーム画像の代表点に対応する点を他のフレーム画像から算出する対応点算出部と、算出された複数の参照フレーム上の対応点数を比較して採用する参照フレームを決定するフレーム間隔決定部と、画像の点対応関係の組を冗長に用いて信頼度判定を行ない、信頼度の低い点対応の組を除いてカメラワークパラメータを算出するカメラワークパラメータ算出部と、代表点の算出が必要かどうかを判定する代表点算出判定部と、フレーム画像と代表点を更新するフレーム画像更新部と、を具備したカメラワークパラメータ算出装置。
【請求項３】
請求項１および請求項２の内の何れかに記載されるカメラワークパラメータ算出装置において、
カメラワークパラメータ算出部は、代表点と算出された対応点の中からパラメータ算出に必要な最低点数より多くの点数を選択する点組合せ冗長選択部と、選択された冗長な点の組合せから複数のカメラワークパラメータを算出する暫定パラメータ算出部と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証部と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定部とを具備したカメラワークパラメータ算出装置。
【請求項４】
請求項１および請求項２の内の何れかに記載されるカメラワークパラメータ算出装置において、
カメラワークパラメータ算出部は、代表点と算出された対応点の中からパラメータ算出に必要な最低点数より多くの点数を選択する点組合せ冗長選択部と、選択された冗長な点の組合せから複数のカメラワークパラメータを算出する暫定パラメータ算出部と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証部と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定部と、算出されたカメラワークパラメータが正常かどうか判定して異常な場合を算出不能な時刻として記憶するカメラワークパラメータ正常判定部とを備えたカメラワークパラメータ算出装置。
【請求項５】
映像中のフレーム画像から特徴となる点を代表点として算出する代表点算出手順と、或るフレーム画像の代表点に対応する点を他のフレーム画像から算出する対応点算出手順と、画像の点対応関係の組を冗長に用いて信頼度判定を行ない、信頼度の低い点対応の組を除いてカメラワークパラメータを算出するカメラワークパラメータ算出手順と、代表点の算出が必要かどうかを判定する代表点算出判定手順と、フレーム画像と代表点を更新するフレーム画像更新手順と、を有するカメラワークパラメータ算出方法。
【請求項６】
映像中のフレーム画像から特徴となる点を代表点として算出する代表点算出手順と、或るフレーム画像の代表点に対応する点を他のフレーム画像から算出する対応点算出手順と、算出された複数の参照フレーム上の対応点数を比較して採用する参照フレームを決定するフレーム間隔決定手順と、画像の点対応関係の組を冗長に用いて信頼度判定を行ない、信頼度の低い点対応の組を除いてカメラワークパラメータを算出するカメラワークパラメータ算出手順と、代表点の算出が必要かどうかを判定する代表点算出判定手順と、フレーム画像と代表点を更新するフレーム画像更新手順と、を有するカメラワークパラメータ算出方法。
【請求項７】
請求項５および請求項６の内の何れかに記載されるカメラワークパラメータ算出方法において、
カメラワークパラメータ算出手順として、代表点と算出された対応点の中からパラメータ算出に必要な最低点数より多くの点数を選択する点組合せ冗長選択手順と、選択された冗長な点の組合せから複数のカメラワークパラメータを算出する暫定パラメータ算出手順と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証手順と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定手順と、を有するカメラワークパラメータ算出方法。
【請求項８】
請求項５および請求項６の内の何れかに記載されるカメラワークパラメータ算出方法において、
カメラワークパラメータ算出手順として、代表点と算出された対応点の中からパラメータ算出に必要な最低点数より多くの点数を選択する点組合せ冗長選択手順と、選択された冗長な点の組合せから複数のカメラワークパラメータを算出する暫定パラメータ算出手順と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証手順と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定手順と、算出されたカメラワークパラメータが正常かどうか判定して異常な場合を算出不能な時刻として記憶するカメラワークパラメータ正常判定手順とを有するカメラワークパラメータ算出方法。
【請求項９】
請求項５ないし請求項８の内の何れかに記載されるカメラワークパラメータ算出方法を実行すべき指令をコンピュータに対してするカメラワークパラメータ算出プログラム。
【請求項１０】
請求項９に記載されるカメラワークパラメータ算出プログラムを記憶した記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、カメラワークパラメータ算出方法、この方法を実施する装置、プログラムおよびその記憶媒体に関し、特に動画像処理の分野で、蓄積された映像の動物体抽出やスプライト符号化の前処理などに必要なカメラワークパラメータ算出方法、この方法を実施する装置、プログラムおよびその記憶媒体に関する。
【背景技術】
【０００２】
非特許文献１には、３次元物体がカメラに投影される時のカメラモデルを利用して背景に属する特徴点を分類する技術が開示されている。カメラモデルを表す部分空間に、背景に属する特徴点の軌跡ベクトルが存在することを用いて、各点の軌跡を背景とそれ以外の軌跡に分類する。この手法により背景に属する軌跡を持つ点のみを用いてカメラワークに相当する射影変換パラメータを算出、背景を変換してメジアン法により背景パノラマを作成し、その背景パノラマを利用して動物体抽出を行っていた。また、動きベクトル算出に特徴点マッチングを利用している。なお、画面の変化に伴う特徴点の算出方法は特徴点追跡失敗による特徴点の数が少なくなった時である。
【０００３】
背景点軌跡の分類の処理ステップを以下に略記する。
（１）Ｌフレーム分の軌跡ベクトル（Ｌ個の点軌跡を繋げた２Ｌ次元ベクトル）の中から３点の軌跡を取り出す。
（２）取り出したベクトルの重心まわりのモーメント行列Ｍ２（２Ｌ×２Ｌ次元）を計算する。
（３）Ｍ２の大きい２つの固有値と対応する単位固有ベクトルを計算する。
（４）２Ｌ×２Ｌ射影行列を固有ベクトルから算出する。
（５）射影行列から算出される判別値が一定値以下になる全軌跡ベクトル個数を算出する。
（６）（１）〜（５）を別の３点で繰り返して（５）で算出される個数を最大とする射影行列を求め、その行列を用いて更に（５）と同様の判別値を用いて各軌跡ベクトルを背景点とそれ以外の点に分類する。
（７）算出された背景点の対応から射影変換パラメータを、くりこみ法を用いて算出してカメラワークパラメータとする。
【非特許文献１】譲田、金谷ほか「移動ビデオカメラ画像からの運動物体の抽出」(情報処理学会 CVIM March 2004)。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
非特許文献１の手法においては、カメラモデルに基づく背景に属する点の算出処理、また、背景に属する点を利用してカメラワークパラメータに相当する射影変換パラメータを算出する、という２つのステップが必要であった。このため計算ステップが多くなり、処理速度が遅くなる欠点があった。また、ある一つの特徴点に対してＬフレーム長の特徴点追跡履歴を算出した後にその点が背景に属すか否かを判定する必要があり、その途中にカット点の如き急激な画像変化が起こり、且つ対応点が一定数以上誤対応してしまった場合は正常なパラメータ算出ができず、また、変化の起こった点を特定することも難しかった。
【０００５】
この発明は、以上の点を鑑みてなされたものであり、比較的計算速度が早く、画面の急激な変化が起こる時刻を検知することができるカメラワークパラメータ算出方法を提供することをその目的としている。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、請求項１に記載のカメラワークパラメータ算出装置は、必要なフレーム画像を入力し、処理済みのフレーム画像と代表点算出部よりメモリに入出力される代表点を更新して処理に必要なフレーム画像を出力するフレーム画像更新部と、必要に応じて映像中のフレーム画像を入力し特徴となる点を代表点として算出しその座標を出力する代表点算出部と、そのフレーム画像からあるフレーム数だけ後のフレーム画像を参照フレームとしてフレーム画像更新部より入力し、また代表点算出部から代表点座標を入力し、２画像間で比較して算出された代表点と対応する点を参照フレームから算出してその対応する座標の組を出力する対応点算出部と、代表点と算出された対応点を対応点算出部より入力しカメラワークパラメータを冗長に算出することで信頼度の低い点対応の組を取り除いてカメラワークパラメータを算出し出力するカメラワークパラメータ算出部と、代表点と算出されたその対応点やカメラワークパラメータを入力し代表点の算出が必要かどうかを判定し、代表点算出部に必要の有無を出力する代表点算出判定部とを具備している。ここで、特に、カメラワークパラメータ算出部と代表点算出判定部とを具備することにより、比較的速い処理速度でカット点を含む編集済映像などを安定に処理することができる、という効果を奏す。
【０００７】
また、請求項２に記載のカメラワークパラメータ算出装置は、必要なフレーム画像を入力し、処理済みのフレーム画像と代表点算出部より入出力される代表点を更新して処理に必要なフレーム画像と代表点とを出力するフレーム画像更新部と、必要に応じて映像中のフレーム画像を入力し特徴となる点を代表点として算出しその座標を出力する代表点算出部と、そのフレーム画像から後の映像時刻のフレーム画像を参照フレームとしてフレーム画像更新部より複数枚入力し、また代表点算出部から代表点座標を入力し、代表点の算出されたフレーム画像と複数枚の参照画像の間でそれぞれ比較して代表点と対応する点を複数の参照フレームから算出してその対応する座標の組を複数出力する対応点算出部と、代表点と複数出力された対応点を入力してどの参照フレームを採用すべきか決定し、その参照フレームの番号と代表点、対応点の組を出力するフレーム間隔決定部と、代表点と算出された対応点を対応点算出部より入力してカメラワークパラメータを冗長に算出することで信頼度の低い点対応の組を取り除いてカメラワークパラメータを算出し出力するカメラワークパラメータ算出部と、代表点と算出されたその対応点やカメラワークパラメータを入力し代表点の算出が必要かどうかを判定し、代表点算出部に必要の有無を出力する代表点算出判定部とを具備する。ここで、特に、請求項２のカメラワークパラメータ算出装置において、請求項１の構成に加えてフレーム間隔決定部とこれに対応する構成とを具備することにより、更なる処理速度向上を安定に実施することができるに至る。
【０００８】
請求項３に記載のカメラワークパラメータ算出部は、代表点と算出された対応点との組合せの中からパラメータ算出に必要な最低点組数より多くの点組数を選択する点組合せ冗長選択部と、複数のカメラワークパラメータを算出する暫定パラメータ算出部と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証部と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定部とを具備する。ここで、請求項３に記載のカメラワークパラメータ算出装置は、上述した点組合せ冗長選択部と暫定パラメータ算出部とパラメータ検証部とカメラワークパラメータ決定部と、それら全てを具備することにより、非特許文献１の奏する効果と類似した効果、即ち、動物体の動きの影響を抑えたカメラワークパラメータの算出を比較的に速い処理速度にて実行することができるに至る。
【０００９】
また、請求項４に記載のカメラワークパラメータ算出部は、代表点と算出された対応点を入力し、その中からパラメータ算出に必要な最低点数より多くの点数を選択する点組合せ冗長選択部と、複数のカメラワークパラメータを算出する暫定パラメータ算出部と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証部と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定部と、決定されたカメラワークパラメータを入力し、それが正常かどうか判定して異常な場合を算出不能な時刻として記憶或いは出力するカメラワークパラメータ正常判定部とを具備する。ここで、請求項４において、請求項３のカメラワークパラメータ算出装置に加えて、カメラワークパラメータ正常判定部を具備することにより、カット点など映像の急激な変化を検知して安定なパラメータ算出を可能にし、或いはパラメータ算出が不安定な映像区間を検知することができる効果を奏す。
【００１０】
また、上記課題を解決するために、請求項５に記載のカメラワークパラメータ算出方法は、必要なフレーム画像を入力し、処理済みのフレーム画像と代表点算出部よりメモリに入出力される代表点を更新して処理に必要なフレーム画像を出力するフレーム画像更新手順と、必要に応じて映像中のフレーム画像を入力し特徴となる点を代表点として算出しその座標を出力する代表点算出手順と、そのフレーム画像からあるフレーム数だけ後のフレーム画像を参照フレームとしてフレーム画像更新部より入力し、また代表点算出部から代表点座標を入力し、２画像間で比較して算出された代表点と対応する点を参照フレームから算出してその対応する座標の組を出力する対応点算出手順と、代表点と算出された対応点との組を対応点算出手順より入力しカメラワークパラメータを冗長に算出することで信頼度の低い点対応の組を取り除いてカメラワークパラメータを算出し出力するカメラワークパラメータ算出手順と、代表点と算出されたその対応点やカメラワークパラメータを入力し代表点の算出が必要かどうかを判定し、代表点算出手順に必要の有無を出力する代表点算出判定手順とを有することを特徴としている。ここで、特に、カメラワークパラメータ算出手順と代表点算出判定手順とを有することにより、比較的速い処理速度でカット点を含む編集済映像などを安定に処理することができる、という効果を奏す。
【００１１】
また、請求項６に記載のカメラワークパラメータ算出方法は、必要なフレーム画像を入力し、処理済みのフレーム画像と代表点算出手順より入出力される代表点を更新して処理に必要なフレーム画像と代表点とを出力するフレーム画像更新手順と、必要に応じて映像中のフレーム画像を入力し特徴となる点を代表点として算出しその座標を出力する代表点算出手順と、そのフレーム画像から後の映像時刻のフレーム画像を参照フレームとしてフレーム画像更新手順より複数枚入力し、また代表点算出部から代表点座標を入力し、代表点の算出されたフレーム画像と複数枚の参照画像の間でそれぞれ比較して代表点と対応する点を複数の参照フレームから算出して、その対応する座標の組を複数出力する対応点算出手順と、代表点と複数出力された対応点を入力してどの参照フレームを採用すべきか決定し、その参照フレームの番号と代表点、対応点の組を出力するフレーム間隔決定手順と、代表点と算出された対応点を対応点算出手順により入力してカメラワークパラメータを冗長に算出することで信頼度の低い点対応の組を取り除いてカメラワークパラメータを算出し出力するカメラワークパラメータ算出手順と、代表点と算出されたその対応点やカメラワークパラメータを入力し代表点の算出が必要かどうかを判定し、代表点算出手順に対し必要の有無を出力する代表点算出判定手順とを有することを特徴とする。ここで、特に、請求項６のカメラワークパラメータ算出方法において、請求項５の構成に加えてフレーム間隔決定手順とこれに対応する手順とを具備することにより、更なる処理速度向上を安定に実施することができるに至る。
【００１２】
請求項７に記載のカメラワークパラメータ算出方法は、代表点と算出された対応点との組合せの中からパラメータ算出に必要な最低点組数より多くの点組数を選択する点組合せ冗長選択手順と、複数のカメラワークパラメータを算出する暫定パラメータ算出手順と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証手順と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定手順とを有することを特徴とする。ここで、請求項７に記載のカメラワークパラメータ算出方法は、上述した点組合せ冗長選択手順、暫定パラメータ算出手順、パラメータ検証手順、およびカメラワークパラメータ決定部、それら全てを有することにより、非特許文献１の奏する効果と類似した効果、即ち、動物体の動きの影響を抑えたカメラワークパラメータの算出を比較的に速い処理速度にて実行することができるに至る。
【００１３】
また、請求項８に記載のカメラワークパラメータ算出方法は、代表点と算出された対応点を入力し、その中からパラメータ算出に必要な最低点数より多くの点数を選択する点組合せ冗長選択手順と、複数のカメラワークパラメータを算出する暫定パラメータ算出手順と、その分散値等のばらつき度合により閾値処理することで信頼できる値かどうか判定するパラメータ検証手順と、信頼できる値のみを用いてカメラワークパラメータを決定するカメラワークパラメータ決定手順と、決定されたカメラワークパラメータを入力し、それが正常かどうか判定して異常な場合を算出不能な時刻として記憶或いは出力するカメラワークパラメータ正常判定手順とを備えたことを特徴とする。ここで、請求項８において、請求項７のカメラワークパラメータ算出方法に加えて、カメラワークパラメータ正常判定手順を有することにより、カット点など映像の急激な変化を検知して安定なパラメータ算出を可能にし、或いはパラメータ算出が不安定な映像区間を検知することができる効果を奏す。
【００１４】
請求項９として請求項５、請求項６、請求項７、請求項８の内の何れかに記載されるカメラワークパラメータ算出方法を実行すべき指令をコンピュータに対してするカメラワークパラメータ算出プログラムを構成することを特徴とする。
請求項１０として、請求項９に記載されるカメラワークパラメータ算出プログラムを記憶した記憶媒体を構成することを特徴とする。
【発明の効果】
【００１５】
この発明によれば、特徴点を代表点として代表点マッチングを行うことでフレーム間における対応点を算出し、カメラワークパラメータを算出する。なお、特徴点として算出される画像上の点としては、例えば四角形の角のような画像上である程度以上の輝度勾配を持つ角の点を選ぶことで比較的安定した追跡を行えることが知られている。次に、フレーム間での対応関係から射影変換などのフレーム間カメラワークパラメータを算出する。ロバストなカメラワークパラメータ算出を行うために、カメラワークパラメータを冗長に算出しアウトライアの除去を行う。アウトライアとは背景点と見なせない軌跡を持つ点軌跡を指し、動物体上の特徴点や誤追跡の生じた軌跡のことである。即ち、射影変換などのカメラワークパラメータ算出の際には連立一次方程式を解くことになるが、その算出に必要な代表点、対応点の数より多い点数を利用して複数の暫定的なカメラワークパラメータを算出し、算出されたカメラワークパラメータの値のばらつきが大きなものを不適切なカメラワークパラメータと判定することでアウトライアを少なくしたカメラワークパラメータ算出を行う。なお暫定的に算出するカメラワークパラメータの個数は、算出可能な最大個数より少なく２よりは多い個数であれば良い。運動物体がカメラワークモデルに当てはまらない動きをしている場合や背景に代表点が充分な数存在していれば、画像の過半数の画素を動物体による画素が占めている場合でもカメラワークパラメータを算出することができる。この作用は非特許文献１でもあるが、この発明では計算コストの比較的少ない計算方法を発明した。
【００１６】
処理速度に関して、上記代表点マッチングに加えて動きベクトル算出におけるフレーム間隔を１フレーム毎ではなく数フレーム毎或いは可変にして、動きの少ない、或いはカメラワークのほとんど無いフレーム間の場合は複数フレーム飛ばしでカメラワークパラメータを算出することで速度向上を行う。また、パラメータの算出を２フレーム間の代表点の対応関係を用いてアウトライア除去の際に同時に行うため、非特許文献１に比べて計算コストを減少させられる。
計算コストについて非特許文献１と比較する。非特許文献１においてはアウトライア除去に用いる背景点分類に２Ｍ×２Ｍ次元行列の固有値、固有ベクトルを算出するステップがあり、この算出オーダーはＯ(Ｍ2 ）であるといわれている。各特徴点の３点の組においてこのオーダーの処理が必要となる。一方、後述される図４のカメラワークパラメータ算出の際のアウトライア除去における算出オーダーは、各代表点３点の組についてＭフレームでＯ(Ｍ)である。これは後述のカメラワークパラメータ算出を含めない算出オーダーである。それ以外の処理としてカメラワークパラメータ算出の連立一次方程式を解く処理は両者とも同様に必要であり、アウトライア除去処理の面で高速であることが分かる。
【００１７】
上述した通り、比較的速い計算速度でアウトライアを排したカメラワークパラメータを算出することができる。そして、カメラワークパラメータを算出することができないカット点、或いは急激な画像変化などの生じた時刻も同時に算出することができる。
【発明を実施するための最良の形態】
【００１８】
以下、図の実施例を参照して更に具体的に説明する。
図１は請求項１に対応するカメラワークパラメータ算出装置の実施例を説明するブロック図である。
映像蓄積部１０１は、カメラワークパラメータ算出装置に入力して画像処理されるべき映像が蓄積されている記憶部位である。
映像入力部１０２は、映像蓄積部１０１からユーザのキーボードによるコマンドなどにより選択される映像、或いは自動的に映像蓄積部１０１から選択される映像を入力する装置である。入力された映像が符号化されている場合はここで個々の既存の映像符号化技術を用いてデコードしてフレーム画像毎に分割して入力する。
【００１９】
フレーム画像更新部１０３は、映像入力部１０２を介して入力された映像から次段の対応点算出部１０５に入力すべきフレーム画像を選択して出力したりメモリ１００に記憶したりする部位である。フレーム画像更新部１０３での初期の読み込みにおいては、処理対象フレームをメモリ１００の中でフレーム番号(映像時刻)の最も小さなものとし、参照フレームを次フレーム或いはそれ以降のフレーム画像として次段の処理を行う。更新するループ処理においては、現在の参照フレームより前のフレーム画像をクリアし、現参照フレームを次の処理対象フレームにし、また次の参照フレーム画像になるべきフレーム画像を映像入力部１０２から入力することで参照フレーム画像も入力する。
【００２０】
代表点算出部１０４は、処理対象フレーム画像を入力しその画像から特徴点を探索し、その座標を代表点座標として記憶するための装置である。この処理は、例えば、非特許文献２の４節に記載の技術などの既存技術で実現可能である。即ち、例えば、画像の２ｘ２の輝度勾配行列の固有値の小さな方が一定値以上である点を、その値が大きなものから優先的に所望の数だけ選ぶことで角にあたる特徴点を所望の上限点数だけ算出することが可能である。なお、特徴点算出技術としては、単純に画像の輝度勾配のｘ、ｙ方向両者の絶対値の大きな点を代表点の決定基準とするなどの他の既存手法を利用することも勿論可能である。この装置における処理は読み込まれた初期フレームや後段の対応点算出部１０５、代表点算出判定部１０７などで代表点算出フラグが立てられた時に行われる。
【００２１】
対応点算出部１０５は入力された処理対象フレーム画像上の代表点に対応する点を参照フレーム画像内で探索する部位である。この処理には例えば参照文献１の３節の技術などを利用することで実現可能である。また上記手法で定義される非類似度(“dissimilarity”)を閾値処理することで画像上から消失した点を判定することができる。消失した処理対象フレームの特徴点の座標は消去してもよい。
対応点の算出の別例としては代表点の周辺画素を用いたブロックマッチングや、動き補償を用いた符号化がなされた映像に対して、その代表点座標の属するマクロブロックにおける動き補償ベクトルとその座標との和を利用するなど、対応点を算出する他の手法を利用することも勿論可能である。ここで周辺画素の残差絶対値総和などの点対応の評価値がある閾値以下の点は消失したと判断することができる。
【００２２】
カメラワークパラメータ算出部１０６は、処理対象フレームおよび参照フレームの２フレーム間で算出された対応点組集合からカメラワークパラメータを算出する部位である。この動作については図３、図４のフローチャートを参照して後で詳細に説明される。
代表点算出判定部１０７は、対応点算出部１０５の結果を受けて現フレームの特徴点を算出しなおすべきか否かを判定する部位である。この動作については図２のＳ２０４、Ｓ２０６、Ｓ２０９を参照して、後で詳細に説明される。
処理結果出力部１０８は、算出された各フレームにおけるカメラワークパラメータ、抽出物体の座標、特徴点、フレーム画像等を記憶装置に格納したり、ユーザに見えるように表示したりする部位である。なおメモリ１００の中には処理対象フレーム画像、参照フレーム画像、代表点算出フラグ、代表点座標集合、対応点座標集合などがそれぞれ記憶可能とする。
【００２３】
また、各結線に流れるデータはそれぞれ始めにＩＤなどが付され、どの箇所で処理すべきデータかを判別可能であり、各部位はそれぞれ自分の処理すべきデータのみ入力しそれ以外は無視するなどのデータ制御を行うものとする。
図２は図１のカメラワークパラメータ算出装置の具体的な処理手順の内容を記述したフローチャートである。また、実施例５と実施７との組合せに対応するカメラワークパラメータ算出方法の具体的な記述でもある。なお、このフローチャートではリトライフラグは未使用である。リトライフラグは図５で利用する。
【００２４】
(Ｓ２０１)   映像蓄積部１０１から映像入力部１０２へ映像を読み込み、映像入力部１０２にてフレーム毎の画像に変換して出力し、その映像の初期の処理対象フレーム画像(第１フレーム)と初期の参照フレーム画像(フレーム番号Ｆ＋１のフレーム画像。Ｆは自然数の定数)をメモリに入力する。またメモリ１００上の代表点算出フラグをオンにする。処理対象フレーム画像と参照フレーム画像をフレーム画像更新部１０３へ出力し、Ｓ２０２へ移る。
【００２５】
(Ｓ２０２)   請求項５および請求項６の代表点算出手順の具体例である。Ｓ２０１により、或いはＳ２０７によりメモリ１００に記憶されている処理対象フレーム画像と参照フレーム画像を代表点算出部１０４へ入力し、代表点算出の必要がある時には処理対象フレーム画像上の特徴点を算出し、代表点Ｐ＝［ｐ(ｉ)］としてメモリ１００に座標を記憶する。この特徴点算出技術については前述の非特許文献２の４節などを利用して行うことができる。なお、特徴点の算出は、単純に画像の輝度勾配のｘ,ｙ方向両者の絶対値の局所的最大の点を代表点とするなどの他の既存手法を利用することも勿論可能である。ここで得られた特徴点の数 Ｎｕｍ(Ｐ)をメモリ１００に記憶する。また代表点算出フラグをオフにする。処理対象フレーム画像とその代表点の座標、参照フレーム画像を対応点算出部へ出力してＳ２０３へ移る。なお、フレーム画像更新部１０３における更新処理の内容はＳ２０７の説明において述べる。また代表点算出の必要があるかどうかの判定はＳ２０９において行なう。
【００２６】
(Ｓ２０３)   請求項５の対応点算出手順の具体例である。また、この処理は対応点算出部１０５の実行する処理である。処理対象フレーム画像と参照フレーム画像をメモリ１００より、その代表点座標を代表点算出部よりそれぞれ入力し、処理対象フレーム画像における代表点座標に対応する点を参照フレーム画像中から探し、算出された対応点の座標をメモリ１００に記憶する。この手順については非特許文献２の第３節に記載される技術を利用することができる。また消失した処理対象フレームの代表点の座標は消去することもできる。対応点算出の別の例としては代表点の周辺画素を用いたブロックマッチングや、動き補償を用いた符号化がなされた映像に対して、その代表点座標の属するマクロブロックにおける動き補償ベクトルとその座標との和を利用するなど、対応点を算出する他の手法を利用することも勿論可能である。ここで周辺画素の残差絶対値総和などの点対応の評価値がある閾値以下の点は消失したと判断することができる。なお、何れの例についても、算出された対応点の座標をメモリ１００に格納し、その点数Ｎｕｍ(Ｐ’)を代表点算出判定部１０７へ出力し、また、代表点座標とその対応点座標をカメラワークパラメータ算出部１０６へ出力してＳ２０４へ移行する。
【００２７】
(Ｓ２０４)   請求項５の代表点算出判定手順の具体例である。また、この処理は代表点算出判定部１０７の実行する処理の一部である。Ｓ２０３にて算出された対応点と対応点数をメモリ１００から入力し、このフレームにおける処理のスキップ判定を行い、また代表点再算出の必要の有無を判定する。始めに対応点数が極端に減少しているか否かによってスキップ判定を行なう。即ち対応点数が上記とは別の閾値より少なくなっている場合はスキップすると判定しＳ２０６へ、それ以外の場合はＳ２０５へそれぞれ移る。スキップ判定における閾値の例としては、次ステップＳ２０５のカメラワークパラメータ算出に必要な最低点数(後述の図３中の数値Ｍ')、それに１以上のある数を乗じたもの、あるいは記憶された数Ｎｕｍ(Ｐ’)にある数(０〜１)を乗じたもの、あるいはある一定の数など様々な数値を利用することが可能である。次に代表点の再算出が必要か判定する。この判定に利用するのは、例えば、対応点数の条件、対応点の位置関係である。対応点数の条件としては算出された対応点数がある数値Ｖpnより大の時は次回の処理において代表点を算出し直す必要は無いと判定し、Ｖpn以下の時は代表点を取り直す必要が有ると判定する。ここにおいては、一例として、Ｓ２０３で記憶された対応点数Ｎum(Ｐ’)に０から１までの実数を乗じた値をＶpnとして採用する。また、対応点の位置関係の条件としては、例えば、算出された対応点毎に隣接対応点までの距離を算出し、その中間値が閾値を下回ったときに次回の処理において代表点を取り直す必要が有ると判定する。位置関係の条件の例としては、他にも、対応点座標のｘ、ｙ成分それぞれの分散値の最小値なども利用して良い。位置条件の閾値の例としてＳ２０２にて算出された代表点について、位置関係の何れかの条件の値の一定割合を利用するなどできる。また、対応点の位置関係の条件として別の例としては前記と同様に隣接点までの距離の平均値が閾値以下の場合、または対応点座標ｘ, ｙそれぞれについての分散値の和、もしくは小さい方の値、もしくは大きい方の値が閾値を超えたときに代表点を取り直す必要有と判定する、などの例がある。この対応点数の条件、位置関係の条件の何れかによって代表点を取り直す必要があると判定された場合は代表点算出フラグをセット(ＯＮ)にする。或いは対応点数の条件、対応点の位置関係の条件のいずれか一方のみを用いて代表点の再算出判定を行なってもよい。
【００２８】
上記の対応点数の条件は映像内の動物体の後ろなどに代表点の多くが隠れてしまい多くの対応点を算出できず消失と判断された場合、あるいは前記の原因が数フレーム間において生じて代表点数が減少し過ぎてしまった際に代表点をもう一度取り直すための判定処理である。また極端に対応点数が減少する場合は急激なカメラワークやカット点などの映像の不連続が生じていると考えられ、その場合はカメラワークパラメータを算出できないためその処理をスキップする。
対応点の位置関係の条件は、非特許文献２の３節の技術を用いて対応点算出を行なった場合、動物体が画面を移動した時対応点が動物体に付随して集中してしまうことがある。この時には対応点の数は多くともほとんどの対応点が動物体上に存在してしまうこともあり、その場合に適切なカメラワークパラメータを算出することができなくなるので、代表点を取り直すための判定として利用するものである。
【００２９】
(Ｓ２０５)   請求項５および請求項６のカメラワークパラメータ算出手順に対応する処理内容である。またこの処理はカメラワークパラメータ算出部１０６の処理内容であり、Ｓ２０３にて算出された代表点とその対応点からカメラワークパラメータを算出するステップである。メモリ１００より代表点の座標とその対応点の座標をカメラワークパラメータ算出部１０６へ入力して処理を行なう。或る代表点をカメラワークパラメータ算出に最低必要な数より多く取り出し、カメラワークモデルに当てはめて、１次方程式を複数回解き、複数のカメラワークパラメータを算出し、これら複数の値の分散値の如きばらつき度合を表す値を閾値処理することにより運動物体や対応点算出の誤りなどのアウトライアとなる点を排除したカメラワークパラメータ算出を行う。この処理の詳細については図３を参照して後で説明する。算出されたカメラワークパラメータを記憶或いは出力してＳ２０７へ移る。また、算出されたカメラワークパラメータおよび代表点座標、対応点座標を処理結果出力部１０８および代表点算出判定部１０７へそれぞれ出力する。
【００３０】
(Ｓ２０６)   代表点を算出し直すために代表点算出フラグをオンにしてＳ２０７へ移行する。
(Ｓ２０７)   請求項５に記載のフレーム画像更新手順の具体例である。フレーム画像更新部１０３の処理手順であり、代表点算出判定部１０７の動作により信号が出力されたタイミングで次に入力すべきフレーム番号の決定を行なう。処理の内容は、現在の参照フレームを次のループにおける処理対象フレームに、算出された対応点を次のループにおける代表点に、それぞれメモリ１００を更新する。またその更新された処理対象フレームの次のＦフレーム後のフレーム画像をメモリ１００に読み込み、参照フレーム画像も更新する。このようにフレーム画像の読み込みはＦフレーム毎で飛ばして読みこむこととする(Ｆ：自然数の定数)。つまり前回読み込んだのがフレーム番号ｆの画像の時、次に、読み込むのはフレーム番号ｆ＋Ｆの画像であるとする。この次に読み込むべきフレーム番号を映像入力部１０２へ出力する。
【００３１】
(Ｓ２０８)   次に読み込むべきフレーム画像が存在するかどうか、即ち、映像の終りまで読みこんだか否かを判定する。映像入力部１０２にフレーム画像更新部１０３から読み込むべきフレーム番号の入力があった時に、この判定を映像入力部１０２の機能として行なう。映像の最後まで読み込んだ判定の場合は処理を終了し、それ以外の場合では映像入力部１０２はフレーム画像更新部１０３へ要求されたフレーム番号を持つフレーム画像を出力する。具体的には現在の参照フレームのフレーム番号にＦを加えた値が映像の総フレーム数を超えないかどうかを判定する。超えない場合はＳ２０９へ移行し、超える場合は処理を終了する。
【００３２】
(Ｓ２０９)   請求項５に記載の代表点算出判定手順の具体例である。また、この処理は代表点算出判定部１０７において実行される処理である。代表点を算出しなおす必要があるかどうかを代表点算出フラグで判定するステップである。ここでは代表点算出フラグがセットされている(ＯＮ)かどうかを、メモリ１００を参照して判定し、ＯＮの場合はＳ２０２へ移り、ＯＦＦの場合はＳ２０３へそれぞれ移行する。
図９は図１のカメラワークパラメータ算出部の構成の詳細を説明する図である。また、請求項３に対応する実施例を説明するブロック図でもある。動作の詳細は図３を参照して説明される。
【００３３】
点組合せ冗長選択部９０１においては代表点とその対応点の集合を入力し、その中からカメラワークパラメータ算出に必要な個数より多くの点を選択し、その点の組によりパラメータ算出が可能かどうか判定し、可能な場合その組を出力する装置である。なお、一度選択した点の組合せは２度選択しないように記憶する。なおこの部位の動作の詳細は図３のＳ２９９、Ｓ３００、Ｓ３０２、Ｓ３０９、Ｓ３１０で説明される。
暫定パラメータ算出部９０２では点組合せ冗長選択部９０１において選択された冗長な点の組からパラメータ算出に必要な組を総当り的に選択し、暫定のカメラワークパラメータを算出し、それらの値を出力する部位である。また、その代表点の組合せと算出された暫定パラメータの値を記憶しておくテーブルとして暫定パラメータ記憶テーブル９０３を持つ。このテーブルは最終的なカメラワークパラメータをカメラワークパラメータ決定部９０５で出力し、処理対象フレームが変更になる時にクリアされる。なお、この部位の動作の詳細は図３のＳ３０３〜Ｓ３０６において説明される。
【００３４】
パラメータ検証部９０４では暫定パラメータ算出部で算出された複数の暫定カメラワークパラメータのばらつきを分散値等のばらつき度合により検証し、それらの暫定パラメータが信頼できる値かどうか判定する。信頼できる値の場合はそれらの暫定パラメータをカメラワークパラメータ決定部９０５へ出力する。
カメラワークパラメータ決定部９０５においてはパラメータ検証部において信頼できると判定されたカメラワークパラメータから１つの暫定カメラワークパラメータを算出し、また点組合せ冗長選択部９０１にて全ての点の組合せについて処理が終了した後に算出された全ての暫定カメラワークパラメータより１つのカメラワークパラメータに決定する装置である。
【００３５】
図３は図９の動作および図２のＳ２０５の動作を説明する詳細フローチャートであり、即ち、請求項３に記載されているカメラワークパラメータの算出装置の動作を説明している。また請求項７に記載されているカメラワークパラメータ算出方法の具体的説明でもある。入力は代表点集合Ｐ＝[ｐ(ｉ)] （ｉ＝１,２,…, Ｎｐ)とその対応点集合Ｐ'＝[ｐ'(ｉ)] (ただしｐ(ｉ)とｐ’(ｉ)が対応しているとする)である。出力はカメラワークパラメータＣである。なお、カメラワークパラメータとして算出されるのは代表点ｐ＝(ｘ, ｙ, １)とその対応点ｐ’＝(ｘ',ｙ', １) (両者とも同次座標系)を用いて、式１中ので表される射影変換などの線形変換行列である。式１のカメラワークモデルの場合、カメラワークパラメータ数Ｍは９であり、パラメータ算出に必要な最低点数NRは５である。具体例は図４を参照して後で説明される。
【００３６】
【数１】
2006190176.tif 000003
(Ｓ２９９)   カウンタｎを１で初期化する。
【００３７】
(Ｓ３００)   点組合せ冗長選択部９０１により実行される処理であり、また請求項７および請求項８に記載の点組合せ冗長選択手順の具体例である。代表点座標の集合Ｐ(代表点集合と呼ぶ)とそれに対応する対応点座標の集合Ｐ’(対応点集合と呼ぶ)を初めに入力し、その入力により処理を開始する。対応点の算出されている代表点集合Ｐの中から任意のＮＱ個の点集合Ｑ=[ｑ(ｊ)] (ＮＱ ＞ ＮＲ としてｊ=１,２,…, ＮＱ)を重複のないように取り出す。同様に取り出されたＱの対応点の集合Ｑ’も取り出す。なお、このＳ３００の２回目以降はそれぞれ異なる組合せの点集合Ｑを取り出すこととする。このＳ３００で取り出す点の数ＮＱはパラメータ算出に必要な点数ＮＲより多くなるようにする。メモリにＱ、Ｑ’の座標を記憶し、Ｓ３０２へＱ、Ｑ’の座標を出力する。
【００３８】
(Ｓ３０１)   カウンタｍを０で初期化してＳ３０２へ移行する。
(Ｓ３０２)   点組合せ冗長選択部９０１により実行される処理であり、また請求項７および請求項８に記載の点組合せ冗長選択手順の具体例である。Ｓ３０１より入力されるＱによって式１を用いてパラメータが安定に算出できるか否かを判定する。つまり、Ｑ内の任意の３点が同一直線上に存在するなどの場合、算出が不安定とする。
例えば、Ｑ内の任意の３点をｑ1＝（ｘ1、ｙ1）、ｑ2＝（ｘ2、ｙ2）、ｑ3＝（ｘ3、ｙ3）としたとき、Ｔｈを或る閾値として次式の条件を満たさない時を算出が不安定と判定する。
|（ｘ3−ｘ1)（ｙ2−ｙ1）−（ｙ3−ｙ1)（ｘ2−ｘ1）|／（|ｑ3−ｑ1|・|ｑ2−ｑ1|）／２＞Ｔｈ (Ｔｈは閾値。ここでは例として定数とする)。
なお、上式の左辺の意味はｑ1が起点のｑ2、ｑ3へのベクトルの成す角のｓｉｎ値である。また各点間の距離の条件 |ｑ3−ｑ1|＜Ｔｈd , |ｑ2−ｑ1|＜Ｔｈd(Ｔｈdは閾値。定数とする) を更に条件として加えることもできる。また距離の条件の別例としては、３点の作る三角形の重心位置からの距離で閾値処理を行う方法もある。また、距離と直線上判定の２条件の任意の論理演算によって算出不可能かどうか判定してもよい。
上記２条件のいずれかが満たされず、算出が不安定と判定された場合はS３０１へ戻り点集合Ｑを選び直す。そうでない場合はＱ、Ｑ’を出力しＳ３０３へ移る。なお、算出可能の判定の時、点組合せ冗長選択部９０１はこの処理ステップにて暫定パラメータ算出部９０２へＱ、Ｑ’を出力する。
【００３９】
(Ｓ３０３)   暫定パラメータ算出部９０２の実行する処理の一部で、また請求項７および請求項８に記載の暫定パラメータ算出手順の具体例である。Ｑ、Ｑ’を点組合せ冗長選択部９０１より入力する。Ｓ３００で取り出した点集合Ｑ、Ｑ’からパラメータ算出に必要な点数であるＮＲ=[Ｍが偶数ならばＭ／２、Ｍが奇数ならば(Ｍ＋１)／２ ] 個の点を点集合Ｒとして、その対応点をＲ’として取り出し、Ｒ、Ｒ’をＳ３０５へ出力する。また、暫定パラメータ算出部９０２はメモリにＲ、Ｒ’を記憶する。
【００４０】
式１を見ると代表点とその対応点の１組で２つの式が立つため、Ｍ個のパラメータを算出するのに必要な点数は先のＮＲ個である。なお、このステップの２回目以降はそれぞれ異なる組合せの点集合Rを取り出すこととする。
(Ｓ３０４)   カウンタｍをインクリメントしてＳ３０５へ移行する。
【００４１】
(Ｓ３０５)   暫定パラメータ算出部９０２の実行する処理の一部であり、また請求項７および請求項８に記載の暫定パラメータ算出部の具体例である。Ｓ３０３にて記憶されたＲ、Ｒ’を利用する。Ｒ、Ｒ’を用いて式１に基づいてカメラワークパラメータを算出する。つまり、式１を式２のように変形すると、ａ11〜ａ33までの１次方程式となる。よって、ｘ、ｙ、ｘ'、 ｙ'にそれぞれＲ、Ｒ’の値を代入し、必要な式の数がそろうと各パラメータの値を算出することができる。一次方程式の解き方はＬＵ分解と後退法を用いるなど任意の既存手法を利用して実行する。
【００４２】
ｘ’・（ｘａ13＋ｙａ23＋ａ33）＝（ｘａ11＋ｙａ21＋ａ31）
ｙ’・（ｘａ13＋ｙａ23＋ａ33）＝（ｘａ12＋ｙａ22＋ａ32）            （式２）
算出された値は暫定パラメータ記憶テーブル９０３内のｐ(ｉ)の点番号ｉの組合せに対応した箇所に保存し、同じ組の点の算出は１度だけ計算するようにする。この場合の上記方程式を解く回数は最大でNPＣNR回である。ここで算出できたカメラワークパラメータ行列をＣｎｍ(あるｍ、ｎの一つの組合せにつきカメラワークパラメータ行列Ｃｎｍ一つ)とする。なお、算出されたカメラワークパラメータ行列ｎｍをメモリ１００に記憶する。
【００４３】
(Ｓ３０６)   暫定パラメータ算出部９０２の実行する処理の一つである。ＲがＱのある一定の部分集合の全ての組合せを取ったかどうか判定し、ある一定の部分集合全てを取った場合はカメラワークパラメータ行列Ｃｎｍを出力しＳ３０７へ、そうでない場合はＳ３０３へ移る。なお、Ｑから部分集合Ｒを取り出す総数はNQＣNR 通りの組み合わせある。ある一定の部分集合の取り方は、例えば、この総数全てを取ってもよいし、或る一点を必ず組合せるような部分集合(NQＣNR-1通り)を取ってもよい。
また、全てのある一定の部分集合を取った場合、暫定パラメータ算出部はパラメータ検証部９０４へカメラワークパラメータ行列Ｃｎｍを出力する。
【００４４】
(Ｓ３０７)   パラメータ検証部９０４の機能であり、また、請求項７および請求項８に記載のパラメータ検証手順の具体例である。暫定パラメータ算出部９０２よりカメラワークパラメータＣｎｍを入力する。この処理ステップでは算出されたパラメータの信頼性を判定する。取り出された点集合Ｒの中に一つでも式１で表されるカメラワークモデルと異なる動きをもつ点が入っている場合、算出されるパラメータの値がｍによってばらばらになる。また、この場合算出されたパラメータの値も信頼性の低い値となるため、最終的なパラメータ算出(Ｓ３１１)に利用しないことにする。
【００４５】
例えば、パラメータ行列Ｃｎｍの成分それぞれについて、ｍについての分散値の大きさで信頼性を判定する。或る閾値を超える場合は信頼性の低いパラメータとして値を捨ててＳ３１０へ移り、ある閾値以下の場合は信頼性の高いパラメータとして、そのパラメータを記憶してＳ３０８へ移行する。
信頼度を判定する他の値の例としては、Ｃｎｍの異なる２つのｍについてパラメータの差分をとり、各パラメータについてその差分値の小さなものからｍ0番目の値をそれぞれ判定に利用する方法もあるし、その差分値を無作為に選んでその値を判定に用いる方法もある。
【００４６】
(Ｓ３０８)   カメラワークパラメータ決定部９０５の実行する処理の一部であり、また請求項７および請求項８に記載のカメラワークパラメータ決定手順の具体例である。代表点集合Ｑから算出されたパラメータ行列Ｃｍｎの成分それぞれについて平均値を算出し、それらを行列Ｃｎとして記憶する。
また、Ｓ３０７の信頼性判定にて信頼性が高いと判定された場合には、パラメータ検証部９０４はカメラワークパラメータ決定部９０５へ行列Ｃｎを出力する。
(Ｓ３０９)  カウンタｎをインクリメントしてＳ３１０へ移行する。
【００４７】
(Ｓ３１０)   点組合せ冗長選択部９０１の実行する処理の一部であり、また、請求項７および請求項８に記載の点組合せ冗長選択部９０１の具体例である。部分点集合Ｑが点集合Ｐの可能な組合せ全体をとったかどうかを判定し、全体をとった場合はＳ３１１へ移り、まだの場合はＳ３００へ移る。なお、Ｐから部分集合Ｑを取り出す総数はNPＣNQ通りの組合せだけある。
【００４８】
(Ｓ３１１)   カメラワークパラメータ決定部９０５の実行する処理の一部であり、また請求項７および請求項８に記載のカメラワークパラメータ決定手順の具体例である。点組合せ冗長選択部９０１から全ての点についてのパラメータを算出したという信号を受けると、メモリ１００内にあるＣｎを用いて処理を行なう。ＣｎからカメラワークパラメータＣを算出する。算出方法は例としてＣｎの各成分の中間値をＣとする。他のＣの決定方法の例としてはＣｎの成分それぞれのパラメータを量子化した後のヒストグラムにおける最頻値とする方法もあるし、平均値としてもよい。
【００４９】
また、Ｓ３０７の判定により、算出された全てのカメラワークパラメータの信頼性が低いとして捨てられてしまい、Ｃｎが空の場合は算出不能と判定し、異常を表すカメラワークパラメータの値を出力する。異常を表すカメラワークパラメータの値としては全ての成分が０のパラメータ行列など、カメラワークパラメータとして通常算出され得ない値であれば何でも良い。この値は図５の実施例のＳ５０２で異常判定を行なう時に利用する。図２の実施例では算出不能の場合は処理を強制終了してもよいし、算出不能として既定のパラメータ値を出力して終了しても良い。
【００５０】
以上のようにしてカメラワークパラメータ決定部９０５はカメラワークパラメータ算出部１０６の出力として算出されたカメラワークパラメータの値Ｃを出力する。
図４は図３のカメラワークモデルを式３ (Ｍ＝４,ＮＲ＝２)とし、ＮＱ＝３とした場合の具体例を示したフローチャートである。なお、ａ1 はズームパラメータ、ａ2 は回転パラメータ、ａ3 はｘ軸移動パラメータ、ａ4 はｙ軸移動パラメータである。
【数２】
2006190176.tif 000004
(Ｓ４００)   カウンタｎを初期化する。
【００５１】
(Ｓ４０１)   点組合せ冗長選択部９０１の実行する処理の一部である。代表点集合Ｐとその対応点集合Ｐ’を入力する。代表点集合Ｐの中から任意の３個の点集合Ｑ＝[ｑ(１),ｑ(２),ｑ(３)]と、その対応点Ｑ’＝[ｑ’(１),ｑ’(２),ｑ’(３)]を取り出して、Ｐ、Ｐ’、Ｑ、Ｑ’を出力する。なお、このステップの２回目以降はそれぞれ異なる組合せの点集合Ｑ、Ｑ’を取り出すこととする。
【００５２】
(Ｓ４０２)   点組合せ冗長選択部９０１の実行する処理の一部である。Ｓ３０２と同様の処理であり、Ｑによって式３を用いたパラメータの算出ができるか判定する。即ち、Ｑ、Ｑ’を入力しその３点ｑ(１),ｑ(２),ｑ(３)を用いてＳ３０２と同様の基準で算出不安定判定を行い、算出不安定な場合Ｓ４０１へ戻り点集合Ｑを選び直す。そうでない場合はＱ、Ｑ’を出力してＳ４０３へ移行する。
【００５３】
(Ｓ４０３)   暫定パラメータ算出部９０２の実行する処理の一部であり、Ｑ、Ｑ’を入力し、Ｑの中からパラメータ算出に必要な点数である２点の全組合せとその対応点Ｑ’を取り出し対応点と共に出力する。即ち、[ｑ(１),ｑ(２)],[ｑ(２),ｑ(３)],[ｑ(３),ｑ(１)]の３通りである。なお、この２点の集合が図３のＲに相当する。
【００５４】
(Ｓ４０４)   暫定パラメータ算出部９０２の実行する処理の一部である。取り出された全組合せである３通りの２点組合せを入力し、式３に基づいてカメラワークパラメータＣｎ1 〜Ｃｎ3 (図３のＣｎｍ,ｍ＝１,２,３)を算出する。即ち、式３を式４のように変形するとａ1 〜ａ4 までの１次方程式となり、式４に代表点(ｘ,ｙ)とその対応点(ｘ',ｙ')それぞれの値を代入すると２つの１次方程式となるので、Ｓ４０３で取り出した３通りの２点組合せを利用して４つの方程式を立て、１つのパラメータ行列の値を算出することができる。連立１次方程式の解法は既存手法を利用する。なお[ｑ(１),ｑ(２)]から算出されたパラメータ行列をＣｎ1、[ｑ(２),ｑ(３)]から算出されたパラメータ行列をＣｎ2 、[ｑ(３),ｑ(１)]から算出されたパラメータ行列をＣｎ3 と表現する。なお、算出されたそれぞれのパラメータ行列はテーブルに保存し、以降、算出された点の組のパラメータ行列はテーブルを参照することにする。このことによりこの方程式を解く総回数はＮｐ(Ｎｐ−１)／２回となる。
ｘ’ａ1＋ｙａ2−ａ3−ｘ＝０
ｙ’ａ1−ｘａ2−ａ4−ｙ＝０                                    （式４）
【００５５】
(Ｓ４０５)   パラメータ検証部９０４の実行する処理であり、上記算出されたＣｎ1 〜Ｃｎ3 を入力し、|Ｃｎ1−Ｃｎ2 |、|Ｃｎ2−Ｃｎ3|、|Ｃｎ3−Ｃｎ1 |の中のそれぞれのパラメータについて最小値を取り出し、その値の大小をそれぞれ計る。その値がある閾値より大きなものが３つの差分の内２つ以上ある場合は信頼度が低いとしてＳ４０７へ移行する。１つ以下のときは信頼度が高いとしてＣｎ1 〜Ｃｎ3 を出力してＳ４０６へ移行する。パラメータの閾値はパラメータ成分毎に設定してよい。なお、パラメータの各成分それぞれについて分散値を算出して信頼度の高低を測ってもよいし、|Ｃｎ1−Ｃｎ2 |など任意の差分値を単独で用いてそれぞれのパラメータの差分値の大小で信頼度の高低を測ってもよい。
【００５６】
(Ｓ４０６)   カメラワークパラメータ決定部９０５の機能の一部である。算出されたパラメータ行列Ｃｎ1 〜Ｃｎ3 を入力しその成分それぞれについて平均値を算出し、それらを行列Ｃｎとしてメモリに記憶する。また、カウンタｎをインクリメントしてＳ４０７へ移る。
(Ｓ４０７)   点組合せ冗長選択部９０１の実行する処理の一部である。部分点集合Ｑが点集合Ｐの組合せ全体をとったかどうかを判定し、全体をとった場合はＣｎを出力してＳ４０８へ移り、まだの場合はＳ４０１へ移る。なお、ＰからＱの選び方の総数がＣｎの最大個数であり、その数は、NPＣ3＝ＮＰ(ＮＰ−１)(ＮＰ−２)通りである。なお、ここで、ＱがＰの全体の組合せで判定するのではなく、所定の部分集合を取ったかどうかの判定としても良い。
【００５７】
(Ｓ４０８)   カメラワークパラメータ決定部９０５の実行する処理の一部である。Ｃｎを入力し、カメラワークパラメータＣを算出して出力する。ここでは例としてＣｎの各成分の中間値をＣとして採用する。ＣｎからＣの算出方法の他の例として、Ｃｎの平均値をＣとしてもよいし、Ｃｎの各パラメータ毎に量子化した後に最頻値を算出することでＣを決定してもよい。
以上のようにしてカメラワークパラメータ決定部９０５はカメラワークパラメータ算出部１０６の出力として算出されたカメラワークパラメータの値Ｃを出力する。
【００５８】
なお、Ｓ４０４のカメラワークパラメータの別の算出方法として２つの点[ｑ(１),ｑ(２)]からパラメータａ〜1〜ａ〜4を算出しておき、残る一点ｑ(３)はＳ４０５の誤差判定に用いる方法がある。この時はＳ４０５、Ｓ４０６も同時に以下の変更を行う。Ｓ４０５で誤差としてｑ(３)を式３に当てはめた場合の誤差を算出し、それを閾値処理することで誤差判定を行う。即ち、式５の値を誤差として閾値処理することで誤差の大小を決定する。Ｓ４０６では算出されているをそのままパラメータＣｎとする方法や、前記図４の説明の方法と同様にしてＣｎ1 〜Ｃｎ3 まで算出し直して平均値を取り直す方法などがある。
【００５９】
Ｍａｘ（｜ｘ′ａ〜1＋ｙａ〜2−ａ〜3−ｘ｜，｜ｙ′ａ〜1−ｘａ〜2−ａ〜4−ｙ｜）
（式５）
図１０は図９にカメラワークパラメータ正常判定部を追加したフローチャートである。図９に追加されたカメラワークパラメータ正常判定部１００６のみについて説明する。
カメラワークパラメータ正常判定部１００６では算出されたカメラワークパラメータが正常か否かを判定する部位である。この部位の動作はＳ５０２において詳細に説明される。
【００６０】
図５は請求項１と請求項４との組合せに対応した実施例であり、図２のフローチャートにカメラワークパラメータの正常判定を追加したフローチャートである。また、同様に、請求項５と請求項８との組合せに対応したカメラワークパラメータ算出方法の具体的な説明となるフローチャートである。即ち、図５のフローチャートを実行する算出装置自体は図１とほぼ同様のカメラワークパラメータ算出装置であるが、図５の装置はカメラワークパラメータ算出部１０６として、図９の代わりに図１０により図示説明されるカメラワークパラメータ算出部を使用する。またメモリ１００の内容のリトライフラグを使用する。図５のフローチャートにおける処理内容には図２における処理に追加のステップであるＳ５０２が付加されている。以下において、図２から変更、追加された処理のみについて図１および図１０をも参照して説明する。
【００６１】
(Ｓ５０１)   映像蓄積部１０１から映像入力部１０２へ映像を入力し、映像入力部１０２にてフレーム毎の画像に変換して出力し、その初期の処理対象フレーム(第１フレーム)と、それからＦフレーム後のフレーム画像である初期の参照フレーム(フレーム番号Ｆ＋１のフレーム画像)をメモリに入力する。また、代表点算出フラグ、リトライフラグをオフにする。処理対象フレームと参照フレームを出力し、Ｓ２０２へ移行する。
【００６２】
(Ｓ５０２)   図１０のカメラワークパラメータ正常判定部１００６の実行する処理であり、また請求項８に記載のカメラワークパラメータ正常判定手順の具体例である。算出されたカメラワークパラメータを入力し、その値が正常かどうかを判定する。判定方法の例として、一つ前のループにて算出されたカメラワークパラメータが正常な場合はその値と現算出値の差分の二乗総和を取り、その値が閾値を超えない場合を正常とする。一つ前のループにて算出されたカメラワークパラメータが正常と判定されており、かつその値が閾値を超える場合を異常とする。また、一つ前のループにて算出されたカメラワークパラメータが異常と判定されている場合はパラメータ値のそれぞれの値が一定範囲内に納まっているか否かで正常か異常かを判定する。なお、初期フレームでは一つ前のループは存在していないが、一つ前のループのカメラワークパラメータ算出は異常の判定であったと見なして同様に判定する。一つ前のループにて算出されたカメラワークパラメータが異常になった場合も初期フレームの場合と同様の処理を行う。判定方法の他の例として、算出されたパラメータのそれぞれの値が一定範囲内にあるか否かのみで正常か異常かを判定する方法もある。何れの例でも正常と判定された場合はＳ２０７へ、異常と判定された場合はＳ５１２へ移行する。
【００６３】
急激なカメラワーク、編集済み映像などにおけるカット点、または映像内の動物体の裏などに代表点の多くが隠れてしまった時に多くの対応点を算出できない場合、あるいは前記の原因が数フレーム間において生じて代表点数が減少してしまった際に、フレーム間で前記原因が累積して生じた対応点減少か、それともこのフレームの映像時刻がカット点になっている等そもそも対応点算出が不可能なフレームなのかを判定するために、もう一度代表点を算出し直して対応点探索を行うための判定処理がＳ２０４であり、同じ再算出を行わないために必要なフラグがリトライフラグである。Ｓ２０４のスキップ判定は対応点探索に失敗して点数が極端に少なくなった場合の判定であり、このＳ５０７の判定は対応点算出において点の誤対応が多数発生してしまい、対応点数では映像の不連続を判定できない場合の判定条件である。この結果はＳ５１４にて出力される。
【００６４】
(Ｓ５１２)   算出された対応点、あるいはカメラワークパラメータが異常値をとった時に対応するステップである。リトライフラグがセットされている(ＯＮ)か否かを判定する。セットされている場合はＳ５１４へ移行し、されていない時はＳ５１３へ移行する。リトライフラグはＳ２０４、Ｓ５０２で対応点、もしくはカメラワークパラメータが算出不可能と判定されて代表点を再算出、再追跡したことを示し、二度同じ処理を行わないために必要なフラグである。
(Ｓ５１３)   算出されたカメラワークパラメータが異常な時で、その原因が背景部分における代表点と対応点の減少であるか否かをテストするために、代表点を取り直して同一フレーム間でもう一度同じ処理を行う時に来るステップである。ここでは代表点算出フラグ、リトライフラグの両者をセットしＳ２０９へ移行する。
【００６５】
(Ｓ５１４)   算出された対応点、或いはカメラワークパラメータが異常値をとり、リトライフラグがＯＮの時に来るステップで、代表点算出フラグをＯＮに、また、リトライフラグをＯＦＦにしてＳ２０７へ移行する。また、このときカメラワークパラメータ算出部１０６の出力としては、例えば既定のパラメータ値を出力するなどとする。また、この映像時刻を不連続が生じた時刻として記録してもよい。ここのステップに至る場合はフレーム間で映像の不連続等の原因でカメラワークパラメータを算出できない場合である。
図６は請求項２および４の両者を具備した実施例である。即ち、図４の実施例にフレーム間隔を決定するフレーム間隔決定部６０９を追加したものに相当する。その他は基本的には図４と同じ働きをするが、対応点の算出を複数の参照フレーム画像を用いて算出するように処理内容が変更されている。具体的な変更については図７を参照して後に説明される。
【００６６】
フレーム間隔を広げることのメリットは比較的動きの少ない映像区間においてカメラワーク検出の処理を減らし、処理速度向上に繋がることである。ただ広げすぎると大きなカメラワークなどが生じた際に対応点を取りきれないし、またカメラの往復などのカメラワーク変化が取れないことなどがある。そこで、処理を行うフレーム間隔に上限ＦMaxを設ける。また、複数の参照フレームを用いて対応点を算出し、対応点数を比較することで、動きが大きい、即ち、対応点が大きく減少する場合はフレーム間隔を短くし、対応点の減少が少ない或いは無い場合はフレーム間隔を長くする設定をする。
【００６７】
フレーム間隔決定部６０９では複数の参照フレームで算出された対応点の数からどの参照フレームを用いてカメラワークパラメータを算出するかを決定する。具体的な処理内容は図７にて説明する。
図７は図６の具体的処理内容を示すフローチャートであり、また請求項６と請求項８とを組合せた実施例に相当する。図５においてＳ５０１、Ｓ２０３、Ｓ２０４、Ｓ２０７がそれぞれＳ７０１、Ｓ７０３、Ｓ７０４、Ｓ７０７へ変更されたものである。変更部分のみを図６をも参照して説明する。
【００６８】
(Ｓ７０１) 映像蓄積部１０１から映像入力部１０２へ映像を入力し、映像入力部１０２にてフレーム毎の画像に変換して出力し、その初期の処理対象フレームである第１フレームを入力する。 また、参照フレームを次の第２フレームから第ＦMax＋１フレームの内任意のｆ枚(ｆ≦ＦMax＋１)を選び、入力する。また、代表点算出フラグ、リトライフラグをオフにする。処理対象フレームと参照フレームをメモリに記憶および出力し、Ｓ２０２へ移行する。
(Ｓ７０３)   対応点算出部１０５の実行する処理である。また、請求項６に記載の対応点算出手順の具体例である。処理対象フレーム画像と参照フレーム画像をメモリより、その代表点座標を代表点算出部よりそれぞれ入力し、処理対象フレーム画像における代表点座標に対応する点をｆ枚の参照フレーム画像中からそれぞれ探し、算出された対応点の座標をそれぞれメモリに記憶する。即ち、対応点算出部１０５における処理、Ｓ２０３と同様の処理をｆ回行なうことになる。算出された参照フレーム画像ｆ枚のそれぞれの対応点の座標と、その点数を代表点算出判定部１０７へ出力し、また代表点座標とその対応点座標をカメラワークパラメータ算出部１０６へ出力してＳ７０４へ移行する。
【００６９】
(Ｓ７０４)   フレーム間隔決定部６０９が実行する処理であり、また請求項６に記載のフレーム間隔決定手順の具体例である。対応点算出部１０５の処理であるＳ７０３にて算出されたｆフレーム分の対応点とその数をメモリから入力し、Ｓ２０４と同様のスキップ判定を算出された全ての参照フレーム上の対応点に対して行ない、どの参照フレームを採用するのが適切かを判定する。全ての参照フレームにおいてＳ２０４の判定処理によりスキップする必要有りと判定された場合はＳ５１２へ移行する。１つの参照フレームのみスキップする必要が無いと判定された場合はその参照フレーム番号を記憶し、対応点をＳ２０５へ出力する。複数の参照フレームでスキップする必要が無いと判定された場合は、算出された対応点数を比較する。フレーム番号が小さな参照フレームの対応点数から順に比較していき、数が減少しているか調べる。同じ場合は大きなフレーム番号の方を順に採用していく。減少した時にはその参照フレーム番号を記憶し、また、その対応点集合をＳ２０５へ出力する。なお、減少したと判定する条件をある値以上減少したとし、対応点数が同じと判定する条件を対応点数の減少がある値より少ない、として処理しても良い。またこの選択された参照フレームに対してＳ２０４と同様の代表点算出フラグのセット判定を行い、判定に応じて代表点算出フラグの状態を変更する。
【００７０】
(Ｓ７０７)   フレーム画像更新部１０３において現在決定されている参照フレームを次のループにおける処理対象フレームに、またその参照フレームに対して算出された対応点を次のループにおける代表点に、それぞれ更新する。また、現在決定されている参照フレームの、現在のループで決定された処理対象フレームに対するフレーム間隔ｆｐを入力し、ｆ枚の読み込むべき次のループにおける参照フレームの番号をフレーム間隔決定部６０９にて決定する。即ち、その更新された処理対象フレームの次からそのＦMaxフレーム後までのＦMax枚のフレーム画像の中から決定されたｆ枚のフレームをメモリ１００に記憶することで参照フレーム画像も更新する。このフレーム間隔決定部６０９で実行される処理は請求項６に記載のフレーム間隔決定手順の具体例でもある。
【００７１】
参照フレームの選択方法の具体例としてフレーム間隔ｆｐの前後を一定フレーム間隔で、ＦMaxを上限として画像を選択する、などがある。
例えば、ｆ＝２、ＦMax＝１０、ｆｐ＝９、一定間隔２で選ぶ場合には読み込んだフレームの９−２＝７枚目、９＋２＝１１＞１０ で１０枚目を参照画像に選択する。また、例えば、ｆ＝５、ＦMax＝１０、ｆｐ＝９、一定間隔２で選ぶ場合には読み込んだフレームから数えて９−２2＝５枚目、９−２1＝７枚目、９＋０＝９枚目、９＋２＝１１＞１０ で１０枚目を参照画像に選択する。この例は１０枚目の画像は２回選ばれるが、１回選ばれたとすることで、選択される画像数は４枚となる。
【００７２】
また、参照フレームの選択方法の別の例としては、更新後の処理対象フレームから次のｆ枚のフレームを、ランダムに選ぶ、または、ＦMax枚のフレーム画像を一定間隔でｆ枚になるように選ぶ、などが考えられる。また、このフレーム間のカメラワークパラメータが算出不能(リトライフラグＯＦＦ、代表点算出フラグＯＮ)の場合には、この間に大きな画像変化があったと見なし、その画像変化がどこで起こったかを詳細に調べるために更新された処理対象フレームの次から１フレーム毎にｆ枚を取り出して再実行を行うことも可能である。もしくは、上記以外の他の数値計算、条件を用いて算出することもむろん可能である。
【００７３】
最後に決定された参照フレーム番号をフレーム画像更新部１０３へ全て出力し、ｆ枚の参照フレームをメモリ１００へ読み込む。
この発明の図７の実施例を、図４のカメラワーク算出の実施例を用いて行なった実例を以下に示す。背景の一致を見るために重ね合わせて差分を取った画像を図８(ａ)に、またその差分を取る前の処理対象フレーム画像、参照フレーム画像とその代表点を図８(ｂ)、(ｃ)にそれぞれ示す。なお、図８(ｂ)および(ｃ)間のフレーム間隔は７フレームである。また、図中に示した代表点は算出されたカメラワークパラメータを用いて処理対象フレームの代表点を変換し参照フレームの対応点との差分の大きさを算出し、その値が大きな時にその代表点は背景以外の動きを持つ物体の点であると判定し、また、その値が小さなものを背景に属する点とすることで各代表点を分類して、点の濃淡を変更して表示したものである。ここで、灰色で示した丸が背景を示し、白丸がアウトライアを示す。これは非特許文献１と類似した表示方法である。また、図８(ａ)中右端と上下端にライン状に残っている画素値はカメラワークが右とズームアウト方向に生じて差分の取られなかった画素である。
【００７４】
このフレーム間ではカメラは少し右に動き、かつズームアウトしており、画像上で背景物体は左方向と画像中央方向に動くが、テロップ（図８に明示されていない）は止まっており、また、運動物体は異なる動きをしている。即ち、テロップや運動物体はカメラワークパラメータに則さないが、テロップおよび運動物体上に代表点が取られているのに関わらず、背景の一致が行えていることが分かる。
なお、運動物体上の代表点で背景に属する点として分類されているものがあるが、これはその点の運動が偶然カメラワークパラメータと同じ動きをしていたか、もしくは対応点が正確に算出できておらず、偶然カメラワークパラメータと同様の動きをしていると判断されているためである。逆に、背景上の代表点であるにもかかわらず背景に属さないと分類されているものがあるが、これは映像のノイズなどの影響で対応点算出に若干のずれが生じている点で、算出されたカメラワークパラメータの示す動きと若干異なる対応点が算出されたためと考えられる。
【００７５】
また、カット点等の画像の著しい変化が生じたフレーム間ではカメラワークパラメータ算出不可能と判定できていた。
この発明の最適な実施例として、図６により図示説明される実施例を図７のフローチャートの処理方法で実行する例を挙げることができる。カメラワークパラメータ算出法は図４を用いて説明した方法を用いる。
ところで、この発明のカメラワークパラメータ算出装置は、これをDSP(Digital Signal  Processor) により構成することができる。また、コンピュータのよりプログラムを実行させることにより機能させてもよい。この場合は、そのプログラムはC-ROM、フロッピー (登録商標)ディスク、磁気ディスクなどに記録されたものを、コンピュータ内のプログラム用メモリに取り込んで行うことになる。このプログラム用メモリには、通信によりプログラムをダウンロードさせてもよい。
【００７６】
[参照文献１]  Jianbo Shi, Carlo Tomasi. "Good Features to Track ", IEEE Conference  CVPR 94, June 1994.
【図面の簡単な説明】
【００７７】
【図１】請求項１に対応する実施例を説明するブロック図。
【図２】図１の実施例の動作フローチャート。請求項５に対応する実施例を説明する詳細フローチャート。
【図３】図２のＳ２０５の詳細フローチャート。請求項７に対応する実施例を説明する詳細フローチャート。
【図４】図３のカメラワークパラメータ算出の手順の具体例を示した動作フローチャート。請求項８に対応する実施例を説明する詳細フローチャート。
【図５】図１の実施例にカメラワークパラメータ正常判定部を付加した実施例の動作フローチャート。請求項５の中のカメラワーク算出手順に請求項８の手順を採用した実施例を示すフローチャート。
【図６】図１の実施例にフレーム間隔決定部を付加した実施例を説明するブロック図。
【図７】図６の実施例の動作フローチャート。請求項６の中のカメラワーク算出手順に請求項８の手順を採用した実施例を示すフローチャート。
【図８】算出パラメータを用いた映像に対する適用例を示す図。
【図９】請求項３に対応する実施例を説明するブロック図。図１の実施例のカメラワークパラメータ算出部の詳細な構成を示すブロック図。
【図１０】請求項４に対応する実施例を説明するブロック図。カメラワークパラメータ算出部にカメラワークパラメータ正常判定部を付加した構成を示す図。
【符号の説明】
【００７８】
１００ メモリ                        １０１ 映像蓄積部
１０２ 映像入力部                    １０３ フレーム画像更新部
１０４ 代表点算出部                  １０５ 対応点算出部
１０６ カメラワークパラメータ算出部  １０７ 代表点算出判定部
１０８ 処理結果出力部                ６０９ フレーム間隔決定部
９０１ 点組合せ冗長選択部            ９０２ 暫定パラメータ算出部
９０３ 暫定パラメータ記憶テーブル    ９０４ パラメータ検証部
９０５ カメラワークパラメータ決定部  １００６ カメラワークパラメータ正常判定部
【図１】
2006190176.tif 000005
【図２】
2006190176.tif 000006
【図３】
2006190176.tif 000007
【図４】
2006190176.tif 000008
【図５】
2006190176.tif 000009
【図６】
2006190176.tif 000010
【図７】
2006190176.tif 000011
【図９】
2006190176.tif 000012
【図１０】
2006190176.tif 000013
【図８】
2006190176.tif 000014