(57)【要約】【課題】本発明は、指定フレーム上の対象物に沿った形状をポリゴンで作成し一連の動きの中で後続フレーム上の対象物を自動的に抽出することを目的とした、信頼性の高いトラッキング機能を具備したマスク処理システムを提供する。【解決手段】最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定し、後続フレームに対しては指定領域（オブジェクト）をトラッキングして後続フレーム上でのその位置を定め、得られた指定領域の新しい位置を基にし、さらに次のフレームに対してトラッキングにより指定領域（オブジェクト）の位置が定められ、このトラッキング処理が後続フレームに対して連続的に実行され、このようにして得られた各フレーム上のオブジェクトに対して指定されたマスク処理を施すことを特徴とするオブジェクトのモザイク処理方法である。【選択図】    図１
2006293883.tif 000002
【特許請求の範囲】
【請求項１】
最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定し、後続フレームに対しては指定領域（オブジェクト）をトラッキングして後続フレーム上でのその位置を定め、得られた指定領域の新しい位置を基にし、さらに次のフレームに対してトラッキングにより指定領域（オブジェクト）の位置が定められ、このトラッキング処理が後続フレームに対して連続的に実行され、このようにして得られた各フレーム上のオブジェクトに対して指定されたマスク処理を施すことを特徴とするオブジェクトのモザイク処理方法。
【請求項２】
「入力ＡＶＩ（映像標準フォーマット）ファイルの読込」ステップ、「最初のフレームを表示」ステップ、「指定領域にポリゴン作成」ステップ、「後続フレーム上での指定領域のトラッキング」ステップ、「トラッキングで得られた指定領域上でのマスク処理（モザイク発生、切り抜き）」ステップ、「マスク処理が付加されたＡＶＩファイルの保存」のステップを有することを特徴とするオブジェクトのモザイク処理方法。
【請求項３】
トラッキング対象領域は、マウスクリックによるポイント（制御点）群によって生成されるポリゴンによって定義され、ユーザが指定した領域に対して後続フレームでのトラッキングが実行され、トラッキングはポリゴン上の各ポイントを対象にして実行され、前フレームのポリゴン上のポイントを現フレームに対してトラッキングする際には、前フレーム上でのポイント座標値が現フレームでのポイント座標初期値として利用され、前フレーム上の各ポリゴンのすべてのポイントに対してポリゴンポイント近傍にブロックを生成し、同一ブロックを現フレーム上の対応ポイント候補位置にも作成し、この両ブロック上でのマッチング比較によって現フレーム上での対応ポイントの位置が確定されることを特徴とする請求項１又は２に記載のオブジェクトのモザイク処理方法。
【請求項４】
ポイント近傍ブロックは、ポリゴン領域内（指定オブジェクト領域内）のピクセルだけから構成されていて、ポリゴン領域外の影響を避けることを特徴とする請求項１〜３のいずれかに記載のオブジェクトのモザイク処理方法。
【請求項５】
前フレームでのポリゴンポイントが、次フレームではどこに位置するかを決定するマッチング処理が、次フレームでのポイント候補位置に対して作成したポイント近傍ブロックと、前フレームでの対応ポイントに対して作成されているポイント近傍ブロックが同じかどうかを判定することによって行われ、この判定は両ブロックの対応する位置にあるピクセルのＲＧＢ値を比較することにより行い、次フレーム上のブロックの全ピクセルがそれぞれ前フレーム上のブロックの対応するピクセルと同じＲＧＢ値であれば、両ブロックは完全にマッチングしていることになり（同様な判定をデリバティブブロックに関しても行う。）、このマッチングの度合いが基準判定値を満足していない場合は、次フレーム上でのポイント候補位置をずらして、再度同様な判定を行い、このプロセスを次フレーム上でのポイント位置が定まるまで繰り返し行うことを特徴とする請求項１〜４のいずれかに記載のオブジェクトのモザイク処理方法。
【請求項６】
マッチング処理において、領域ベーストラッキングと境界ベーストラッキングの両方の概念を有し、シンプルブロックマッチング用のシンプルブロックと、デリバティブブロックマッチング用のデリバティブブロックの２種のブロックを使用し、シンプルブロックの生成とシンプルブロックマッチングは領域トラッキングの優位性を利用するものであり、デリバティブブロックは境界トラッキングの優位性を利用するもので、デリバティブブロックの生成に際しては、境界上と境界近傍のピクセルはブロックには含まないことを特徴とする請求項１〜５のいずれかに記載のオブジェクトのモザイク処理方法。
【請求項７】
ブロックの大きさは対象領域ポリゴンの大きさに基づいて定め、対象全領域をカバーすることはせず、さらにポイント近傍ブロックには、下記で定義される多孔性ブロックという概念を導入し、ブロック内部の全ピクセルをブロックピクセルとして取り扱うのではなく、下記特定の間引き率（多孔率）によって一部のピクセルを間引きした残りのピクセルだけをブロックピクセルとして処理対象にすることを特徴とする請求項１〜６のいずれかに記載のオブジェクトのモザイク処理方法。
［間引き率（多孔率）］
間引き率（多孔率）は、ポリゴン平均幅に比例して定められ、ポリゴン幅が広くなるにつれて多孔率は大きくなり、ポリゴン幅が広い大きなポリゴンの場合はトラッキング精度を上げるにはより大きなブロックサイズが必要であるが、多孔率が大きくなるのでブロックピクセル数はそれほど多くならないし、そして、ブロック生成に際しては境界外のピクセルは除外され、境界内のピクセルが離散的に選択される。
【請求項８】
トラッキング対象オブジェクトは、領域は僅かながらも変形をする可能性があり、トラッキングの際には形状の変化を考慮するものとし、現フレームとのマッチングを行う際に、前フレーム上のブロック形状を不変として比較せず、下記で定義される、“変形”及び“変形限界”という概念をブロックマッチング・アルゴリズムに導入したことを特徴とする請求項１〜７のいずれかに記載のオブジェクトのモザイク処理方法。
［変形及び変形限界］
前フレーム上の各ブロックピクセルに対しては、対応する現フレーム上のピクセルとのマッチングを行うのに加えて、そのピクセルに隣接するピクセルとのマッチングも行い、隣接ピクセル数は適用する変形限界によって定められ、マッチングに使うブロックピクセルのブロックの多孔率は２以上とし、前フレームのブロック上の丸ピクセルが、現フレーム上の対応するブロックの丸ピクセルとマッチングされ、前フレーム上の丸ピクセルは、現フレーム上の対応するブロックピクセルとの比較に加えて、さらに隣接ピクセルともマッチングされること。
【請求項９】
あらかじめ対象オブジェクトが取り得る種々の形状を定義されたフレームを参照フレームとして登録しておくデータベーストラキング方式が導入され、登録されたすべての参照フレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じた参照フレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このポリゴン候補に対してさらにトラッキング処理が実行されることを特徴とする請求項１〜８のいずれかに記載のオブジェクトのモザイク処理方法。
【請求項１０】
対象領域をフレームを追ってトラッキングするに際し、前後のフレーム間には認知し難いレベルの小さな誤差が発生し、この誤差はフレームを追うに従って累積され、ついには明確に認識できるレベルの違いが生じることに対処する方法として下記で定義されるキーフレームという概念を用いて処理することを特徴とする請求項１〜７のいずれかに記載のオブジェクトのモザイク処理方法。
［キーフレーム］
ユーザは前もって数箇所のフレーム上にトラッキング対象オブジェクトを定義しておき（キーフレーム）、トラッキングに次のような問題が発生しやすいと考えられるフレームをキーフレームとして設定する。
（１）オブジェクトが急激、または極めて速い動きをする場合
（２）カメラの動きが大きい場合
（３）複数オブジェクトが重なり合う場合
（４）照明状況が変化する場合
トラッキングの途中でキーフレームに到達すると、キーフレーム上に定義済みのオブジェクトポリゴンを使ってトラッキングを行うものとし、キーフレームに到達した時点で誤差の累積はキャンセルされることになり、登録されたすべてのキーフレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じたキーフレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このトラッキング処理の際にはポリゴン内部領域全体が比較対象となり、さらに最終調整として、上記処理で得られたポリゴン候補に対して現フレーム上で上下左右への平行移動、回転、オフセットを実行して領域全体比較での色の差異を最小にする形状を求める。
【請求項１１】
プロセッサを有するオブジェクトのモザイク処理装置において、最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定し、後続フレームに対しては指定領域（オブジェクト）をトラッキングして後続フレーム上でのその位置を定め、得られた指定領域の新しい位置を基にし、さらに次のフレームに対してトラッキングにより指定領域（オブジェクト）の位置が定められ、このトラッキング処理が後続フレームに対して連続的に実行され、このようにして得られた各フレーム上のオブジェクトに対して指定されたマスク処理を施す構成のプロセッサを有することを特徴とするオブジェクトのモザイク処理装置。
【請求項１２】
プロセッサを有するオブジェクトのモザイク処理装置において、プロセッサは、「入力ＡＶＩ（映像標準フォーマット）ファイルの読込」ステップ、「最初のフレームを表示」ステップ、「指定領域にポリゴン作成」ステップ、「後続フレーム上での指定領域のトラッキング」ステップ、「トラッキングで得られた指定領域上でのマスク処理（モザイク発生、切り抜き）」ステップ、「マスク処理が付加されたＡＶＩファイルの保存」のステップを行う構成であることを特徴とするオブジェクトのモザイク処理装置。
【請求項１３】
トラッキング対象領域は、マウスクリックによるポイント（制御点）群によって生成されるポリゴンによって定義され、ユーザが指定した領域に対して後続フレームでのトラッキングが実行され、トラッキングはポリゴン上の各ポイントを対象にして実行され、前フレームのポリゴン上のポイントを現フレームに対してトラッキングする際には、前フレーム上でのポイント座標値が現フレームでのポイント座標初期値として利用され、前フレーム上の各ポリゴンのすべてのポイントに対してポリゴンポイント近傍にブロックを生成し、同一ブロックを現フレーム上の対応ポイント候補位置にも作成し、この両ブロック上でのマッチング比較によって現フレーム上での対応ポイントの位置が確定される構成のプロセッサを有することを特徴とする請求項１１又は１２に記載のオブジェクトのモザイク処理装置。
【請求項１４】
ポイント近傍ブロックは、ポリゴン領域内（指定オブジェクト領域内）のピクセルだけから構成されていて、ポリゴン領域外の影響を避ける構成のプロセッサを有することを特徴とする請求項１１〜１３のいずれかに記載のオブジェクトのモザイク処理装置。
【請求項１５】
前フレームでのポリゴンポイントが、次フレームではどこに位置するかを決定するマッチング処理が、次フレームでのポイント候補位置に対して作成したポイント近傍ブロックと、前フレームでの対応ポイントに対して作成されているポイント近傍ブロックが同じかどうかを判定することによって行われ、この判定は両ブロックの対応する位置にあるピクセルのＲＧＢ値を比較することにより行い、次フレーム上のブロックの全ピクセルがそれぞれ前フレーム上のブロックの対応するピクセルと同じＲＧＢ値であれば、両ブロックは完全にマッチングしていることになり（同様な判定をデリバティブブロックに関しても行う。）、このマッチングの度合いが基準判定値を満足していない場合は、次フレーム上でのポイント候補位置をずらして、再度同様な判定を行い、このプロセスを次フレーム上でのポイント位置が定まるまで繰り返し行う構成のプロセッサを有することを特徴とする請求項１１〜１４のいずれかに記載のオブジェクトのモザイク処理装置。
【請求項１６】
マッチング処理において、領域ベーストラッキングと境界ベーストラッキングの両方の概念を有し、シンプルブロックマッチング用のシンプルブロックと、デリバティブブロックマッチング用のデリバティブブロックの２種のブロックを使用し、シンプルブロックの生成とシンプルブロックマッチングは領域トラッキングの優位性を利用するものであり、デリバティブブロックは境界トラッキングの優位性を利用するもので、デリバティブブロックの生成に際しては、境界上と境界近傍のピクセルはブロックには含まない処理を行う構成のプロセッサを有することを特徴とする請求項１１〜１５のいずれかに記載のオブジェクトのモザイク処理装置。
【請求項１７】
ブロックの大きさは対象領域ポリゴンの大きさに基づいて定め、対象全領域をカバーすることはせず、さらにポイント近傍ブロックには、下記で定義される多孔性ブロックという概念を導入し、ブロック内部の全ピクセルをブロックピクセルとして取り扱うのではなく、下記特定の間引き率（多孔率）によって一部のピクセルを間引きした残りのピクセルだけをブロックピクセルとして処理対象にする構成のプロセッサを有することを特徴とする請求項１１〜１６のいずれかに記載のオブジェクトのモザイク処理装置。
［間引き率（多孔率）］
間引き率（多孔率）は、ポリゴン平均幅に比例して定められ、ポリゴン幅が広くなるにつれて多孔率は大きくなり、ポリゴン幅が広い大きなポリゴンの場合はトラッキング精度を上げるにはより大きなブロックサイズが必要であるが、多孔率が大きくなるのでブロックピクセル数はそれほど多くならないし、そして、ブロック生成に際しては境界外のピクセルは除外され、境界内のピクセルが離散的に選択される。
【請求項１８】
トラッキング対象オブジェクトは、領域は僅かながらも変形をする可能性があり、トラッキングの際には形状の変化を考慮するものとし、現フレームとのマッチングを行う際に、前フレーム上のブロック形状を不変として比較せず、下記で定義される、“変形”及び“変形限界”という概念をブロックマッチング・アルゴリズムに導入した構成のプロセッサを有することを特徴とする請求項１１〜１７のいずれかに記載のオブジェクトのモザイク処理装置。
［変形及び変形限界］
前フレーム上の各ブロックピクセルに対しては、対応する現フレーム上のピクセルとのマッチングを行うのに加えて、そのピクセルに隣接するピクセルとのマッチングも行い、隣接ピクセル数は適用する変形限界によって定められ、マッチングに使うブロックピクセルのブロックの多孔率は２以上とし、前フレームのブロック上の丸ピクセルが、現フレーム上の対応するブロックの丸ピクセルとマッチングされ、前フレーム上の丸ピクセルは、現フレーム上の対応するブロックピクセルとの比較に加えて、さらに隣接ピクセルともマッチングされること。
【請求項１９】
あらかじめ対象オブジェクトが取り得る種々の形状を定義されたフレームを参照フレームとして登録しておくデータベーストラキング方式が導入され、登録されたすべての参照フレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じた参照フレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このポリゴン候補に対してさらにトラッキング処理が実行される構成のプロセッサを有することを特徴とする請求項１１〜１８のいずれかに記載のオブジェクトのモザイク処理装置。
【請求項２０】
対象領域をフレームを追ってトラッキングするに際し、前後のフレーム間には認知し難いレベルの小さな誤差が発生し、この誤差はフレームを追うに従って累積され、ついには明確に認識できるレベルの違いが生じることに対処する方法として下記で定義されるキーフレームという概念を用いて処理する構成のプロセッサを有することを特徴とする請求項１１〜１７のいずれかに記載のオブジェクトのモザイク処理装置。
［キーフレーム］
ユーザは前もって数箇所のフレーム上にトラッキング対象オブジェクトを定義しておき（キーフレーム）、トラッキングに次のような問題が発生しやすいと考えられるフレームをキーフレームとして設定する。
（１）オブジェクトが急激、または極めて速い動きをする場合
（２）カメラの動きが大きい場合
（３）複数オブジェクトが重なり合う場合
（４）照明状況が変化する場合
トラッキングの途中でキーフレームに到達すると、キーフレーム上に定義済みのオブジェクトポリゴンを使ってトラッキングを行うものとし、キーフレームに到達した時点で誤差の累積はキャンセルされることになり、登録されたすべてのキーフレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じたキーフレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このトラッキング処理の際にはポリゴン内部領域全体が比較対象となり、さらに最終調整として、上記処理で得られたポリゴン候補に対して現フレーム上で上下左右への平行移動、回転、オフセットを実行して領域全体比較での色の差異を最小にする形状を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は映像処理に係わり、特に人物の動きに対応した特定の部位にモザイク処理を生成するオブジェクトのモザイク処理方法及びモザイク処理装置に関する。
【背景技術】
【０００２】
モザイク処理は難易度が高い。なぜなら、モザイク処理が必要な映像は偶発的に収録可能になった状況が多く、モザイク処理を行うために収録を行うという事例は極めて少ないためである。つまり映像処理を行うために撮影側で環境を整備することは困難である。そのような状況下では既存のクロマキー装置やマスク生成装置を使用することも出来ない。ゆえにモザイク処理を行うことを前提にされなかった収録映像を処理する事となる。
【０００３】
より品質の高いモザイク処理を行うためには、それぞれのフレーム内のモザイク処理必要領域を作業者が抽出しマスクを作成することとなり膨大な作業時間が必要となる。
【０００４】
モザイク処理には主に次の２つの方法が挙げられる。
第一に人間が１フレームずつ手書きでマスクを作成する方法である。
１フレームずつモザイク処理を施さなければならない領域を描写していく。１秒間で３０枚の収録映像につき、作業を施すために作業時間、作業工程は必然的に多くなる。
【０００５】
第二に映像合成ソフトを使用してモザイク処理を行う方法である。
第一フレームに作業者がモザイク修正領域を指定する（第一点）。第二点に再び修正領域を指定する。第一点と第二点の間は自動的に補完される。しかしながら、対象物の移動速度は一定ではなく、かつカメラアングルも固定されないため、直線的な補完では対象物が領域外に出てしまう場合が多い。作業者は対象物が領域外に出た箇所を検出し修正をするといった作業の繰り返しとなる。
【０００６】
本発明は、モザイク処理を施さなければならない領域を自動的に抽出することである。従来よりモーショントラッキング機能を利用してトラッキングデータを生成することが行われている。モーショントラッキング機能は映像の色彩データを基に対象物の移動データを生成する。しかし対象物の形状に沿った動きを生成することは出来ない。
【０００７】
この点、ビデオオブジェクトをトラッキングする方法及び装置が、特許文献１によって提案されている。この先提案技術に従うと、オブジェクトは複数の画像フレームでトラッキングされる。最初のフレームでは、オペレータはトラッキングされるべきオブジェクトを選択する。選択されたオブジェクトまたは選択されたオブジェクトの修正された推定値を画像の残りの背景部分と区別して、背景マスクおよび前景マスクを生成する。前景マスクはトラッキングされるべきオブジェクトに対応する。後続のフレーム内では背景マスクのモデルが用いられ、更新され、後続のフレーム内では前景マスクのモデルが用いられ、更新される。後続のフレーム内の画素は背景または前景に属するものとして分類される。そして、後続のフレームの各々では、以下を含む決定がなされる。すなわち、どの画素が背景に属さないか、（元の画像に基づいて）前景内のどの画素が更新されるべきか、背景内のどの画素が現在のフレーム内で不正確に認識されたか、どの背景画素が初めて認識されているのか、を含めての決定がなされる。これらの決定のいくつかは必ずしも他の決定と相互に相反するものではない。
【０００８】
更に、この先提案技術に従えば、画素の分類に加えて、マスクフィルタリングが行なわれて誤りが訂正され、小さな島が除去され、前景マスクの空間的および時間的整合性が維持される。わずかな出力遅延を用いてオブジェクトトラッキングが達成される。ある実施例では、３フレーム待ち時間が採用される。
【０００９】
この先提案技術の利点は、変化が速い形状を有するオブジェクトが動きのない背景に対して正確にトラッキングされることである。前のフレームおよび未来フレーム内の情報を用いてオブジェクトの動きを検出する。オブジェクトは内部で変化し得るものであり、それ自体で自身を隠すものでさえあり得る。別の利点は、以前には現れていない（ｕｎｒｅｖｅａｌｅｄ）（つまり、隠されていた）背景部分が識別され、オブジェクト推定値の正確さが増すことである。別の利点は、オブジェクト内のホールも正確にトラッキングされることである。
【００１０】
しかしこの先提案技術によっても、被処理オブジェクト（映像）の種類によっては、信頼性の点で不充分であった。
【特許文献１】特開２００３−５１９８３
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、指定フレーム上の対象物に沿った形状をポリゴンで作成し一連の動きの中で後続フレーム上の対象物を自動的に抽出することを目的とした、信頼性の高いトラッキング機能を具備したマスク処理システムに関するものである。
【課題を解決するための手段】
【００１２】
上記発明の課題は、下記構成によって解決される。
１．最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定し、後続フレームに対しては指定領域（オブジェクト）をトラッキングして後続フレーム上でのその位置を定め、得られた指定領域の新しい位置を基にし、さらに次のフレームに対してトラッキングにより指定領域（オブジェクト）の位置が定められ、このトラッキング処理が後続フレームに対して連続的に実行され、このようにして得られた各フレーム上のオブジェクトに対して指定されたマスク処理を施すことを特徴とするオブジェクトのモザイク処理方法。
【００１３】
２．「入力ＡＶＩ（映像標準フォーマット）ファイルの読込」ステップ、「最初のフレームを表示」ステップ、「指定領域にポリゴン作成」ステップ、「後続フレーム上での指定領域のトラッキング」ステップ、「トラッキングで得られた指定領域上でのマスク処理（モザイク発生、切り抜き）」ステップ、「マスク処理が付加されたＡＶＩファイルの保存」のステップを有することを特徴とするオブジェクトのモザイク処理方法。
【００１４】
３．トラッキング対象領域は、マウスクリックによるポイント（制御点）群によって生成されるポリゴンによって定義され、ユーザが指定した領域に対して後続フレームでのトラッキングが実行され、トラッキングはポリゴン上の各ポイントを対象にして実行され、前フレームのポリゴン上のポイントを現フレームに対してトラッキングする際には、前フレーム上でのポイント座標値が現フレームでのポイント座標初期値として利用され、前フレーム上の各ポリゴンのすべてのポイントに対してポリゴンポイント近傍にブロックを生成し、同一ブロックを現フレーム上の対応ポイント候補位置にも作成し、この両ブロック上でのマッチング比較によって現フレーム上での対応ポイントの位置が確定されることを特徴とする前記１又は２に記載のオブジェクトのモザイク処理方法。
【００１５】
４．ポイント近傍ブロックは、ポリゴン領域内（指定オブジェクト領域内）のピクセルだけから構成されていて、ポリゴン領域外の影響を避けることを特徴とする前記１〜３のいずれかに記載のオブジェクトのモザイク処理方法。
【００１６】
５．前フレームでのポリゴンポイントが、次フレームではどこに位置するかを決定するマッチング処理が、次フレームでのポイント候補位置に対して作成したポイント近傍ブロックと、前フレームでの対応ポイントに対して作成されているポイント近傍ブロックが同じかどうかを判定することによって行われ、この判定は両ブロックの対応する位置にあるピクセルのＲＧＢ値を比較することにより行い、次フレーム上のブロックの全ピクセルがそれぞれ前フレーム上のブロックの対応するピクセルと同じＲＧＢ値であれば、両ブロックは完全にマッチングしていることになり（同様な判定をデリバティブブロックに関しても行う。）、このマッチングの度合いが基準判定値を満足していない場合は、次フレーム上でのポイント候補位置をずらして、再度同様な判定を行い、このプロセスを次フレーム上でのポイント位置が定まるまで繰り返し行うことを特徴とする前記１〜４のいずれかに記載のオブジェクトのモザイク処理方法。
【００１７】
６．マッチング処理において、領域ベーストラッキングと境界ベーストラッキングの両方の概念を有し、シンプルブロックマッチング用のシンプルブロックと、デリバティブブロックマッチング用のデリバティブブロックの２種のブロックを使用し、シンプルブロックの生成とシンプルブロックマッチングは領域トラッキングの優位性を利用するものであり、デリバティブブロックは境界トラッキングの優位性を利用するもので、デリバティブブロックの生成に際しては、境界上と境界近傍のピクセルはブロックには含まないことを特徴とする前記１〜５のいずれかに記載のオブジェクトのモザイク処理方法。
【００１８】
７．ブロックの大きさは対象領域ポリゴンの大きさに基づいて定め、対象全領域をカバーすることはせず、さらにポイント近傍ブロックには、下記で定義される多孔性ブロックという概念を導入し、ブロック内部の全ピクセルをブロックピクセルとして取り扱うのではなく、下記特定の間引き率（多孔率）によって一部のピクセルを間引きした残りのピクセルだけをブロックピクセルとして処理対象にすることを特徴とする前記１〜６のいずれかに記載のオブジェクトのモザイク処理方法。
【００１９】
［間引き率（多孔率）］
間引き率（多孔率）は、ポリゴン平均幅に比例して定められ、ポリゴン幅が広くなるにつれて多孔率は大きくなり、ポリゴン幅が広い大きなポリゴンの場合はトラッキング精度を上げるにはより大きなブロックサイズが必要であるが、多孔率が大きくなるのでブロックピクセル数はそれほど多くならないし、そして、ブロック生成に際しては境界外のピクセルは除外され、境界内のピクセルが離散的に選択される。
【００２０】
８．トラッキング対象オブジェクトは、領域は僅かながらも変形をする可能性があり、トラッキングの際には形状の変化を考慮するものとし、現フレームとのマッチングを行う際に、前フレーム上のブロック形状を不変として比較せず、下記で定義される、“変形”及び“変形限界”という概念をブロックマッチング・アルゴリズムに導入したことを特徴とする前記１〜７のいずれかに記載のオブジェクトのモザイク処理方法。
【００２１】
［変形及び変形限界］
前フレーム上の各ブロックピクセルに対しては、対応する現フレーム上のピクセルとのマッチングを行うのに加えて、そのピクセルに隣接するピクセルとのマッチングも行い、隣接ピクセル数は適用する変形限界によって定められ、マッチングに使うブロックピクセルのブロックの多孔率は２以上とし、前フレームのブロック上の丸ピクセルが、現フレーム上の対応するブロックの丸ピクセルとマッチングされ、前フレーム上の丸ピクセルは、現フレーム上の対応するブロックピクセルとの比較に加えて、さらに隣接ピクセルともマッチングされること。
【００２２】
９．あらかじめ対象オブジェクトが取り得る種々の形状を定義されたフレームを参照フレームとして登録しておくデータベーストラキング方式が導入され、登録されたすべての参照フレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じた参照フレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このポリゴン候補に対してさらにトラッキング処理が実行されることを特徴とする前記１〜８のいずれかに記載のオブジェクトのモザイク処理方法。
【００２３】
１０．対象領域をフレームを追ってトラッキングするに際し、前後のフレーム間には認知し難いレベルの小さな誤差が発生し、この誤差はフレームを追うに従って累積され、ついには明確に認識できるレベルの違いが生じることに対処する方法として下記で定義されるキーフレームという概念を用いて処理することを特徴とする前記１〜７のいずれかに記載のオブジェクトのモザイク処理方法。
【００２４】
［キーフレーム］
ユーザは前もって数箇所のフレーム上にトラッキング対象オブジェクトを定義しておき（キーフレーム）、トラッキングに次のような問題が発生しやすいと考えられるフレームをキーフレームとして設定する。
（１）オブジェクトが急激、または極めて速い動きをする場合
（２）カメラの動きが大きい場合
（３）複数オブジェクトが重なり合う場合
（４）照明状況が変化する場合
【００２５】
トラッキングの途中でキーフレームに到達すると、キーフレーム上に定義済みのオブジェクトポリゴンを使ってトラッキングを行うものとし、キーフレームに到達した時点で誤差の累積はキャンセルされることになり、登録されたすべてのキーフレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じたキーフレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このトラッキング処理の際にはポリゴン内部領域全体が比較対象となり、さらに最終調整として、上記処理で得られたポリゴン候補に対して現フレーム上で上下左右への平行移動、回転、オフセットを実行して領域全体比較での色の差異を最小にする形状を求める。
【００２６】
１１．プロセッサを有するオブジェクトのモザイク処理装置において、最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定し、後続フレームに対しては指定領域（オブジェクト）をトラッキングして後続フレーム上でのその位置を定め、得られた指定領域の新しい位置を基にし、さらに次のフレームに対してトラッキングにより指定領域（オブジェクト）の位置が定められ、このトラッキング処理が後続フレームに対して連続的に実行され、このようにして得られた各フレーム上のオブジェクトに対して指定されたマスク処理を施す構成のプロセッサを有することを特徴とするオブジェクトのモザイク処理装置。
【００２７】
１２．プロセッサを有するオブジェクトのモザイク処理装置において、プロセッサは、「入力ＡＶＩ（映像標準フォーマット）ファイルの読込」ステップ、「最初のフレームを表示」ステップ、「指定領域にポリゴン作成」ステップ、「後続フレーム上での指定領域のトラッキング」ステップ、「トラッキングで得られた指定領域上でのマスク処理（モザイク発生、切り抜き）」ステップ、「マスク処理が付加されたＡＶＩファイルの保存」のステップを行う構成であることを特徴とするオブジェクトのモザイク処理装置。
【００２８】
１３．トラッキング対象領域は、マウスクリックによるポイント（制御点）群によって生成されるポリゴンによって定義され、ユーザが指定した領域に対して後続フレームでのトラッキングが実行され、トラッキングはポリゴン上の各ポイントを対象にして実行され、前フレームのポリゴン上のポイントを現フレームに対してトラッキングする際には、前フレーム上でのポイント座標値が現フレームでのポイント座標初期値として利用され、前フレーム上の各ポリゴンのすべてのポイントに対してポリゴンポイント近傍にブロックを生成し、同一ブロックを現フレーム上の対応ポイント候補位置にも作成し、この両ブロック上でのマッチング比較によって現フレーム上での対応ポイントの位置が確定される構成のプロセッサを有することを特徴とする前記１１又は１２に記載のオブジェクトのモザイク処理装置。
【００２９】
１４．ポイント近傍ブロックは、ポリゴン領域内（指定オブジェクト領域内）のピクセルだけから構成されていて、ポリゴン領域外の影響を避ける構成のプロセッサを有することを特徴とする前記１１〜１３のいずれかに記載のオブジェクトのモザイク処理装置。
【００３０】
１５．前フレームでのポリゴンポイントが、次フレームではどこに位置するかを決定するマッチング処理が、次フレームでのポイント候補位置に対して作成したポイント近傍ブロックと、前フレームでの対応ポイントに対して作成されているポイント近傍ブロックが同じかどうかを判定することによって行われ、この判定は両ブロックの対応する位置にあるピクセルのＲＧＢ値を比較することにより行い、次フレーム上のブロックの全ピクセルがそれぞれ前フレーム上のブロックの対応するピクセルと同じＲＧＢ値であれば、両ブロックは完全にマッチングしていることになり（同様な判定をデリバティブブロックに関しても行う。）、このマッチングの度合いが基準判定値を満足していない場合は、次フレーム上でのポイント候補位置をずらして、再度同様な判定を行い、このプロセスを次フレーム上でのポイント位置が定まるまで繰り返し行う構成のプロセッサを有することを特徴とする前記１１〜１４のいずれかに記載のオブジェクトのモザイク処理装置。
【００３１】
１６．マッチング処理において、領域ベーストラッキングと境界ベーストラッキングの両方の概念を有し、シンプルブロックマッチング用のシンプルブロックと、デリバティブブロックマッチング用のデリバティブブロックの２種のブロックを使用し、シンプルブロックの生成とシンプルブロックマッチングは領域トラッキングの優位性を利用するものであり、デリバティブブロックは境界トラッキングの優位性を利用するもので、デリバティブブロックの生成に際しては、境界上と境界近傍のピクセルはブロックには含まない処理を行う構成のプロセッサを有することを特徴とする前記１１〜１５のいずれかに記載のオブジェクトのモザイク処理装置。
【００３２】
１７．ブロックの大きさは対象領域ポリゴンの大きさに基づいて定め、対象全領域をカバーすることはせず、さらにポイント近傍ブロックには、下記で定義される多孔性ブロックという概念を導入し、ブロック内部の全ピクセルをブロックピクセルとして取り扱うのではなく、下記特定の間引き率（多孔率）によって一部のピクセルを間引きした残りのピクセルだけをブロックピクセルとして処理対象にする構成のプロセッサを有することを特徴とする前記１１〜１６のいずれかに記載のオブジェクトのモザイク処理装置。
【００３３】
［間引き率（多孔率）］
間引き率（多孔率）は、ポリゴン平均幅に比例して定められ、ポリゴン幅が広くなるにつれて多孔率は大きくなり、ポリゴン幅が広い大きなポリゴンの場合はトラッキング精度を上げるにはより大きなブロックサイズが必要であるが、多孔率が大きくなるのでブロックピクセル数はそれほど多くならないし、そして、ブロック生成に際しては境界外のピクセルは除外され、境界内のピクセルが離散的に選択される。
【００３４】
１８．トラッキング対象オブジェクトは、領域は僅かながらも変形をする可能性があり、トラッキングの際には形状の変化を考慮するものとし、現フレームとのマッチングを行う際に、前フレーム上のブロック形状を不変として比較せず、下記で定義される、“変形”及び“変形限界”という概念をブロックマッチング・アルゴリズムに導入した構成のプロセッサを有することを特徴とする前記１１〜１７のいずれかに記載のオブジェクトのモザイク処理装置。
【００３５】
［変形及び変形限界］
前フレーム上の各ブロックピクセルに対しては、対応する現フレーム上のピクセルとのマッチングを行うのに加えて、そのピクセルに隣接するピクセルとのマッチングも行い、隣接ピクセル数は適用する変形限界によって定められ、マッチングに使うブロックピクセルのブロックの多孔率は２以上とし、前フレームのブロック上の丸ピクセルが、現フレーム上の対応するブロックの丸ピクセルとマッチングされ、前フレーム上の丸ピクセルは、現フレーム上の対応するブロックピクセルとの比較に加えて、さらに隣接ピクセルともマッチングされること。
【００３６】
１９．あらかじめ対象オブジェクトが取り得る種々の形状を定義されたフレームを参照フレームとして登録しておくデータベーストラキング方式が導入され、登録されたすべての参照フレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じた参照フレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このポリゴン候補に対してさらにトラッキング処理が実行される構成のプロセッサを有することを特徴とする前記１１〜１８のいずれかに記載のオブジェクトのモザイク処理装置。
【００３７】
２０．対象領域をフレームを追ってトラッキングするに際し、前後のフレーム間には認知し難いレベルの小さな誤差が発生し、この誤差はフレームを追うに従って累積され、ついには明確に認識できるレベルの違いが生じることに対処する方法として下記で定義されるキーフレームという概念を用いて処理する構成のプロセッサを有することを特徴とする前記１１〜１７のいずれかに記載のオブジェクトのモザイク処理装置。
【００３８】
［キーフレーム］
ユーザは前もって数箇所のフレーム上にトラッキング対象オブジェクトを定義しておき（キーフレーム）、トラッキングに次のような問題が発生しやすいと考えられるフレームをキーフレームとして設定する。
（１）オブジェクトが急激、または極めて速い動きをする場合
（２）カメラの動きが大きい場合
（３）複数オブジェクトが重なり合う場合
（４）照明状況が変化する場合
【００３９】
トラッキングの途中でキーフレームに到達すると、キーフレーム上に定義済みのオブジェクトポリゴンを使ってトラッキングを行うものとし、キーフレームに到達した時点で誤差の累積はキャンセルされることになり、登録されたすべてのキーフレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じたキーフレーム上のポリゴンが現フレーム上でのポリゴン候補として選択され、このトラッキング処理の際にはポリゴン内部領域全体が比較対象となり、さらに最終調整として、上記処理で得られたポリゴン候補に対して現フレーム上で上下左右への平行移動、回転、オフセットを実行して領域全体比較での色の差異を最小にする形状を求める。
【発明を実施するための最良の形態】
【００４０】
本発明はデジタル画像オブジェクトのトラッキング処理及び装置に関するものである。本発明に係るシステムの概念図を図１に示す。
【００４１】
ＡＶＩ（映像標準フォ−マット）ファイルの最初のフレーム上の特定領域（オブジェクト）をユーザが指定し、連続する後続フレームに対してその領域（オブジェクト）をトラッキングする。最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定し、後続フレームに対しては指定領域（オブジェクト）をトラッキングして後続フレーム上でのその位置を定める。得られた指定領域の新しい位置を基にし、さらに次のフレームに対してトラッキングにより指定領域（オブジェクト）の位置が定められる。このトラッキング処理が後続フレームに対して連続的に実行される。このようにして得られた各フレーム上のオブジェクトに対して指定されたマスク処理を施す。この処理の全体フローチャートを図２に示す。
【００４２】
即ち、「入力ＡＶＩファイルの読込」ステップ、「最初のフレームを表示」ステップ、「指定領域にポリゴン作成」ステップ、「後続フレーム上での指定領域のトラッキング」ステップ、「トラッキングで得られた指定領域上でのマスク処理（モザイク発生、切り抜き）」ステップ、「マスク処理が付加されたＡＶＩファイルの保存」のステップで処理されることとなる。
【００４３】
トラッキング対象領域は、マウスクリックによるポイント（制御点）群によって生成されるポリゴンによって定義される。ユーザが指定した領域に対して後続フレームでのトラッキングが実行される。トラッキングはポリゴン上の各ポイントを対象にして実行される。前フレームのポリゴン上のポイントを現フレームに対してトラッキングする際には、トラッキング速度を上げるために、前フレーム上でのポイント座標値が現フレームでのポイント座標初期値として利用される。前フレーム上の各ポリゴンのすべてのポイントに対してポリゴンポイント近傍にブロックを生成し、同一ブロックを現フレーム上の対応ポイント候補位置にも作成し、この両ブロック上でのマッチング比較によって現フレーム上での対応ポイントの位置が確定される。
【００４４】
ポイント近傍ブロック生成の考え方は多くの研究論文で使われているが、本発明で採用したポイント近傍ブロックはポリゴン領域内（指定オブジェクト領域内）のピクセルだけから構成されていて、ポリゴン領域外の影響を避けることができるため、良質なトラッキング結果が期待できる。マッチング処理においては領域ベーストラッキングや境界ベーストラッキングの手法が通常使用されるが、本発明では、領域ベーストラッキングと境界ベーストラッキングの両方の概念を取り入れた独自のアルゴリズムを用いている。本発明ではシンプルブロックマッチング用のシンプルブロックと、デリバティブブロックマッチング用のデリバティブブロックの２種のブロックを使用する。シンプルブロックの生成とシンプルブロックマッチングは領域トラッキングの優位性を利用するものである。デリバティブブロックは境界トラッキングの優位性を利用するもので、デリバティブブロックの生成とマッチングのやり方は、本発明者らによって独自に開発された。このブロックの生成とマッチング法に採用されたやり方は、本発明者らによる多大の検討、研究の中から導かれた。デリバティブブロックの生成に際しては、境界上と境界近傍のピクセルはブロックには含まない。その理由は、これらのピクセルは境界外ピクセルの色の影響を大きく受けることにより、トラッキング結果に悪い影響を与えるためである。
【００４５】
トラッキング処理速度の向上とトラッキング精度の維持という相反する目的を達成するために、ブロックの大きさは対象領域ポリゴンの大きさに基づいて定め、対象全領域をカバーすることはしない。さらにポイント近傍ブロックには多孔性ブロックという新しい概念を導入し、ブロック内部の全ピクセルをブロックピクセルとして取り扱うのではなく、一部のピクセルを間引きした残りのピクセルだけをブロックピクセルとして処理対象にする。
【００４６】
各フレーム上でのトラッキングを繰り返すにつれて小さな誤差が累積される。この誤差はトラッキングを行うフレーム数が少ない内は問題とはならないが、多数のフレームを処理するにつれて誤差累積による形状崩れは無視できなくなる。正確なトラッキングを行うと同時に、オブジェクトの幾何形状を維持することも重要となる。本発明ではこの問題を解決するために形状修正アルゴリズムという手法を導入した。
【００４７】
トラッキング対象オブジェクトは変形無しの剛体移動だけをするとは限らない。オブジェクト領域は僅かながらも変形をする可能性がある。そのため、トラッキングの際には形状の変化を考慮する必要がある。現フレームとのマッチングを行う際に、前フレーム上のブロック形状を不変として比較してはならない。この問題を解決するために、“変形”及び“変形限界”という新しい概念をブロックマッチング・アルゴリズムに導入した。
【００４８】
繰り返し的な極めて速い動きが実際問題においては存在する。このようなケースでは、前フレームの情報だけに基づいて現フレームのトラッキングを行うシーケンシャルトラッキングのやり方では追随できない問題が生じる。このような場合の対処法として、あらかじめ対象オブジェクトが取り得る種々の形状を定義されたフレームを参照フレームとして登録しておくデータベーストラキング方式が導入された。登録されたすべての参照フレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じた参照フレーム上のポリゴンが現フレーム上でのポリゴン候補として選択される。このポリゴン候補に対してさらにトラッキング処理が実行される。
【実施例】
【００４９】
図１にＭａｓｋ  Ｔｒａｃｋｅｒシステムの構成図の例を示す。映像データはオーディオデータとビデオデータの２種から構成されている。映像データはＡＶＩフォーマットに変換される。映像編集ソフトウェアを使ってトラッキング処理を行う映像部分を切り出し、Ｍａｓｋ  Ｔｒａｃｋｅｒプラグインを介してＭａｓｋ  Ｔｒａｃｋｅｒアプリケーションでトラッキング処理を実行する。トラッキングオブジェクトに対するマスク処理を施されたＡＶＩファイルは、Ｍａｓｋ  Ｔｒａｃｋｅｒプラグインを介し映像処理ソフトウェアを使って元の映像ＡＶＩファイルに書き込まれ、さらに変換ハードウェアにより映像テープに変換される。Ｍａｓｋ  Ｔｒａｃｋｅｒプラグインは映像編集ソフトウェアとＭａｓｋ  Ｔｒａｃｋｅｒアプリケーションの仲介的役割を行う。Ｍａｓｋ  Ｔｒａｃｋｅｒアプリケーションへの入力データはＭａｓｋ  Ｔｒａｃｋｅｒプラグインから受け取ったＡＶＩファイルである。ユーザはＭａｓｋ  Ｔｒａｃｋｅｒアプリケーションを使って対象オブジェクトのトラッキングを行うことができる。トラッキング処理されたＡＶＩファイルは再びＭａｓｋ  Ｔｒａｃｋｅｒプラグインを介して映像編集ソフトウェアに戻される。
【００５０】
ＡＶＩファイルの最初のフレーム上の特定領域をユーザが指定し、連続する後続フレームに対してその領域をトラッキングする。最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定する。最初のフレーム上にトラッキング対象のオブジェクト領域をユーザが指定し、後続フレームに対しては指定領域（オブジェクト）をトラッキングして後続フレーム上でのその位置を定める。トラッキング処理の全体フローチャートは、前記図２に示す通りである。
【００５１】
Ｍａｓｋ  Ｔｒａｃｋｅｒハンドラーは領域指定のポリゴンを有する最初のフレームにアクセスし、その後で２番目のフレームを読み込む。このフレーム上で、フレームトラッキングのアルゴリズムを使ってポリゴンのトラッキングを行う。２番目のフレーム上でのポリゴン位置を確定した後で、このポリゴンをベースにして３番目のフレーム上でのトラッキングが実行される。同様の処理が後続フレームに対しても次々と行われる。Ｍａｓｋ  Ｔｒａｃｋｅｒハンドラーアルゴリズムのフローチャートを図３に示す。
【００５２】
即ち、トラッキング領域指定のポリゴンを有する１番目のフレームから現フレームが最後のフレームになるまでは、最後のフレームまで次々とトラッキングが実行される。現フレームが最後のフレームでない限り、トラッキング対象の次のフレームを選択し、フレーム・トラッキングのアルゴリズムを使い、前フレーム上のポリゴンを参照してトラッキングを行うことが繰返される。そして、現フレームが最後のフレームになったとき、ＡＶＩファイルのトラッキングが終了となる。
【００５３】
本発明において、トラッキング対象領域は、マウスクリックによるポイント（制御点）群によって定義されるポリゴンによって定義される。フレーム上に作成されたポイントを通るスプラインが作成されるので、ポリゴンは角を持たない滑らかな曲線として表示される。
【００５４】
前フレーム上に存在するポリゴン上のポイントを現在フレームに対してトラッキングする際にはトラッキング速度を上げるために、前フレーム上でのポイント座標値が現フレームでのポイント座標初期値として利用される。前フレーム上の各ポリゴンのすべてのポイントは現フレーム上でブロックマッチングアルゴリズムを使ってトラッキングされる。前フレーム上の各ポリゴンのすべてのポイントに対してポリゴンポイント近傍にブロックを生成し、同一ブロックを現フレーム上の対応ポイント候補位置にも作成し、この両ブロック上でのマッチング比較によって現フレーム上での対応ポイントの位置が確定するものである。前フレーム上のすべてのポリゴンに対するトラッキングが完了した時点で、現在フレームに対するトラッキング処理は終了となる。このフレームトラッキングアルゴリズムのフローチャートを図４に示す。ブロックマッチングアルゴリズムについては後述する。
【００５５】
フレームトラッキングアルゴリズムは、図４（Ａ）のフローチャートに示ず如く、「ポリゴンを有する前フレームとトラッキングを行う現フレーム」ステップ、「現フレーム上の処理対象ポリゴンにアクセス」ステップ、「選択されたポリゴン上の次のポイントにアクセス」ステップ、「ブロックマッチングハンドラー・アルゴリズムを使って上記ポリゴンポイントのトラッキング」ステップ、下記「（Ａ）」へというステップを経るが、後記「（Ｂ）」は「現フレーム上の処理対象ポリゴンにアクセス」のズテップへ、そして後記「（Ｃ）」は「選択されたポリゴン上の次のポイントにアクセス」のステップを経ることとなる。図４（Ｂ）のフローチャートに示ず如く、前記「（Ａ）」から「前フレームのポイントのＸ、Ｙ座標値を現フレームでのトラッキング初期値に設定」ステップ、「現在のポイントが最後か」のステップへ、このステップにおいてＮＯの場合は前記「（Ｃ）」へ、そしてＹＥＳの場合、「現在のポリゴンが前フレーム上の最後のポリゴンか」ステップへ、ＮＯの場合は前記「（Ｂ）」へ、そしてＹＥＳの場合は「現フレーム上のトラッキング終了」のステップを経て終わる。
【００５６】
ポイント近傍ブロック生成の考え方は多くの研究論文で使われているが、本発明で採用したポイント近傍ブロックはポリゴン領域内（指定オブジェクト領域内）の一部ピクセルだけから構成されていて、ポリゴン領域外の影響を避けることができるため、良質なトラッキング結果が期待できる。トラッキング処理速度はブロック内の処理対象ピクセル数に比例する。そのため、ブロック内部の全ピクセルをブロックピクセルとして取り扱うのではなく、一部のピクセルを間引きした残りのピクセルをブロックピクセルとして処理対象にする多孔性ブロックにすることによってトラッキング速度を向上させることができる。トラッキング速度改善を図って単にブロックサイズを小さくするだけであれば、良いトラッキング結果は得られない。大きなブロックサイズの優位性とトラッキング速度の向上を両立させるやり方として多孔性ブロックという新しい考え方が導入された。間引き率（多孔率）はポリゴン幅を基にして定められる。多孔率が大きいほどトラッキング速度は上がるがトラッキング精度は悪くなる。多孔率はポリゴン平均幅に比例して定められ、ポリゴン幅が広くなるにつれて多孔率は大きくなる。ポリゴン幅が広い大きなポリゴンの場合はトラッキング精度を上げるにはより大きなブロックサイズが必要であるが、多孔率が大きくなるのでブロックピクセル数はそれほど多くならない。図７に多孔ブロックの一例を示す。線１はポリゴン境界を示す。矩形２はポリゴン上のポイントである。この図は多孔率が３である例を示しており、ピクセルは３つおきに選択されている。選択されたピクセルは丸３で示されている。ブロック生成に際しては境界外のピクセルは除外され、境界内のピクセルが離散的に選択される。
【００５７】
マッチング処理においては領域ベーストラッキングや境界ベーストラッキングの手法が通常使用されるが、本発明では、領域ベーストラッキングと境界ベーストラッキングの両方の概念を融合した独自のアルゴリズムを用いている。本発明ではシンプルブロックマッチング用のシンプルブロックと、デリバティブブロックマッチング用のデリバティブブロックの２種のブロックを使用する。
【００５８】
図５にポリゴン上のポイント近傍に生成されたシンプルブロックを示す。灰色の領域５がブロック領域である。丸４はポリゴン上のポイント（制御点）である。灰色領域内部に離散的に存在する点６は選択されたピクセルを示す。これがブロックの多孔性を示している。
【００５９】
ポイント近傍ブロック生成の考え方は多くの研究論文で使われているが、本発明者らが採用したやり方は独自の考え方を基にしている。本発明におけるポイント近傍ブロックはポリゴン領域内（指定オブジェクト領域内）のピクセルだけから構成されている。ポリゴン領域外の影響を避けることができるため、良質なトラッキング結果が期待できる。トラッキング処理速度を上げるために、多孔性ブロックという新しい概念を取り入れた。ブロック内部の全ピクセルをブロックピクセルとして取り扱うのではなく、一部のピクセルを間引きした残りのピクセルをブロックピクセルとして処理対象にする。間引き率（多孔率）はポリゴン幅を基にして定められる。
【００６０】
多孔率が大きいほどトラッキング速度は上がるがトラッキング精度は悪くなる。多孔率はポリゴン平均幅に比例して定められ、ポリゴン幅が広くなるにつれて多孔率は大きくなる。
【００６１】
ポリゴン幅が広い大きなポリゴンの場合はトラッキング精度を上げるにはより大きなブロックサイズが必要であるが、多孔率が大きくなるのでブロックピクセル数はそれほど多くならない。
【００６２】
図５のブロックはポリゴン上のポイント近傍ブロックを模式的に示すもので、ポイント近傍ブロックにはシンプルブロックとデリバティブブロックの２種類があるが、この図はシンプルブロックのケースであり、ブロックの領域は同図の線と線で囲まれた部分であり、各方眼は１ピクセル領域を表しており矩形部分（黒い太線上）がポリゴン上のポイントである。
【００６３】
前フレームでのこのポリゴンポイントが、次フレームではどこに位置するかを決定するのがマッチング処理であり、次フレームでのポイント候補位置に対して作成したポイント近傍ブロックと、前フレームでの対応ポイントに対して作成されているポイント近傍ブロックが同じかどうかを判定する。この判定は両ブロックの対応する位置にあるピクセルのＲＧＢ値を比較することにより行う。次フレーム上のブロックの全ピクセルがそれぞれ前フレーム上のブロックの対応するピクセルと同じＲＧＢ値であれば、両ブロックは完全にマッチングしていることになる（同様な判定をデリバティブブロックに関しても行う。）。マッチングの度合いが基準判定値を満足していない場合は、次フレーム上でのポイント候補位置をずらして、再度同様な判定を行う。このプロセスを次フレーム上でのポイント位置が定まるまで繰り返し行う。
【００６４】
上述のプロセスには膨大な演算が必要となる。この演算量を低減することを目的にして多孔性ブロックが導入された。この場合、ブロック上の全ピクセルを対象にした比較は行わず、一部のピクセルだけをピックアップして比較演算を行う。図５の丸の位置にあるピクセルがピックアップされたピクセルを示している。各丸ピクセル間には空白の３つの方眼がある。これらの空白方眼の位置にあるピクセルは演算対象から除外されている。即ち、この図は多孔率が３の例を示している。
【００６５】
デリバティブブロックの生成に際しては、境界上と境界近傍のピクセルはブロックには含まない。その理由は、これらのピクセルは境界外ピクセルの色の影響を大きく受けることにより、トラッキング結果に悪い影響を与えるためである。境界から遠く離れたピクセルは境界の特性を有しないため、これらのピクセルもデリバティブブロックには含めない。ポリゴン境界とデリバティブブロックの境界ピクセルとの間の最短距離は少なくとも４ピクセル以上とし、最長距離はポリゴン幅に基いて決定される（最長距離＝ポリゴン幅／２．５）。ただし、この最長距離は少なくとも８ピクセル以下にはしない。図６にデリバティブブロックの例を示す。なお、デリバティブブロックはシンプルブロックと同様に多孔性を有する。
【００６６】
シンプルブロックの生成とシンプルブロックマッチングは領域トラッキングの優位性を利用するものである。デリバティブブロックは境界トラッキングの優位性を利用するもので、デリバティブブロックの生成とマッチングのやり方は本発明者らによって開発された。このブロックの生成とマッチング法に採用されたやり方は本発明者らによる多大の研究の中から導かれた。デリバティブブロックの生成に際しては、境界上と境界近傍のピクセルはブロックには含まない。その理由は、これらのピクセルは境界外ピクセルの色の影響を大きく受けることにより、トラッキング結果に悪い影響を与えるためである。
【００６７】
ブロックマッチングハンドラーアルゴリズムのフローチャートを図８に示す。
即ち、「トラッキング対象のポイントを前フレームから得る」ステップ、「ポイント近傍ブロックの生成」ステップ、「ブロックマッチング・アルゴリズムを使って現フレーム上での最適ポイントを決定」ステップ、「ブロックマッチング・アルゴリズムを使って全方向を探索。１番目のポイントに対する探索限界は２０ピクセル、その他のポイントに対し対する探索限界は２ピクセル。」ステップ、「トラッキング結果のポイント変位が１８ピクセル以上か（１番目のポイントに関して。他のポイントの場合は１ピクセル）」のステップを経て、ＹＥＳの場合は、「新たな位置補正をしてマッチング継続」ステップ、「ブロックマッチング・アルゴリズムを使って全方向を探索。１番目のポイントに対する探索限界は２０ピクセル、その他のポイントに対し対する探索限界は２ピクセル。」へのステップへ、そして、ＮＯの場合、「対象ポイントのトラッキング終了」となる。
【００６８】
ブロックマッチングハンドラーアルゴリズムは前フレームのトラッキング対象ポリゴン上のポイント近傍のピクセルから構成されるブロックを生成する。このポイント近傍ブロックに対してはブロックマッチングアルゴリズムを使い現フレーム上でのマッチングが行われる。対象ポイントが前フレームのポリゴン上の最初のポイントの場合、このポイントは位置補正無しで現フレーム上でも使用される。ポイント近傍ブロックは現フレーム上の該当ポイント位置を起点にして全４方向に最大２０ピクセルの範囲内でマッチング処理される。対象ポイントが前フレームのポリゴン上の最初のポイントではない場合、ポイント近傍ブロックは現フレーム上の該当ポイント位置を起点にして全４方向に最大２ピクセルの範囲内でマッチング処理される。
【００６９】
このアルゴリズムがマッチング処理の中核となるアルゴリズムである。前フレーム上のポリゴンの各ポイント（制御点）におけるシンプルブロックとデリバティブブロックに対して現フレーム上でのトラッキングが実行される。ブロックマッチング処理における入力は、現フレーム上でのマッチングにおいて参照する前フレームのブロックピクセルであり、出力は現フレーム上での最適マッチングポイント位置の座標である。最初のポリゴンポイントに対しては現フレーム上のトラッキング探索領域は広く取られる。トラッキング処理時間を短縮するために、２番目以降のポリゴンポイントのトラッキングでは最初のポリゴンポイントの移動変位分を位置補正して使用する。  現フレーム上でのブロックマッチングを図９に示す。
【００７０】
図９に示す二つのフレームにおいて、フレーム１（Ａ図）はトラッキング対象オブジェクトが定義されている前フレームであり、フレーム２（Ｂ図）はトラッキング処理により対象オブジェクトが生成される現フレームである。フレーム１には対象オブジェクトを示すポリゴンの一部が表示されている。丸印のＰ１、Ｐ２、Ｐ３はポリゴンポイントを示している。Ｐ１はトラッキング対象の最初のポリゴンポイントである。Ｐ１は現フレーム上の広い領域（２０画素四方）でマッチングされる。Ｐ１以外のポリゴンポイントに対してはＰ１の移動変位分を位置補正して使用するため、より狭い領域（２画素四方）でのマッチングが実行される。マッチングは探索領域内のの全４方向に対して行われる。この探索領域はフレーム２でポリゴンポイント近傍の矩形領域として示されている。フレーム２の新Ｐ１は最初のポリゴンポイントＰ１に対するトラッキングの結果によって得られた位置である。候補Ｐ２と候補Ｐ３はＰ１の移動変位分を補正した後の前フレーム上のＰ２とＰ３に対応した現フレーム上の候補位置である。これらのポリゴンポイントに対しては位置決めのための探索領域は狭く取られる。
【００７１】
前フレーム上に形成されたシンプルブロックとデリバティブブロックは現フレーム上に置かれ、前フレーム上のブロックピクセルと現フレーム上のブロックピクセルとの間の差異が計算される。シンプルブロック間の色の差異とデリバティブブロック間の色の差異の総和が求められ、この総和が最小となる位置を現フレーム上での対応するポリゴンポイントの位置とする。総和を求める次式は経験則に基づいて決定された。
【００７２】
色の差異の総和＝デリバティブブロック間の色の差異＋
（シンプルブロック間の色の差異×シンプルブロック間の色の差異）
【００７３】
シンプルブロックマッチングでは前フレーム上のブロックピクセルと、現フレーム上の対応ピクセルとの間の色に関する差異が計算される。デリバティブブロックマッチングのアルゴリズムは境界を境にして色の値が大きく変化する性質を利用することを考えて設計されている。オブジェクト領域と隣接領域とは識別可能な境界によって分離されていることが多いため、トラッキングに関しては境界は極めて重要な情報を与えてくれる。
【００７４】
Ｍａｓｋ  Ｔｒａｃｋｅｒアプリケーションで使用されているデリバティブマスクのＸ係数（Ａ）とＹ係数（Ｂ）を図１０に示す。
【００７５】
各フレーム上でのトラッキングを繰り返すにつれて小さな誤差が生じる。この誤差はトラッキングを行うフレーム数が少ない内は問題とはならないが、多数のフレームを処理するにつれて誤差累積による形状崩れは無視できなくなる。正確なトラッキングを行うと同時に、オブジェクトの幾何形状を維持することも重要となる。本発明ではこの問題を解決するために形状修正アルゴリズムという手法を導入した。形状修正アルゴリズムはトラッキング結果の改善を行うものである。前フレーム上のポリゴンの内角を求めておく。トラッキングの結果として得られた現フレーム上のポリゴンの内角も計算により求める。前フレーム上のポリゴンの内角と、現フレーム上のポリゴンの内角に差があるかを計算する。内角に最大の違いがあるポイントに対して内角の差を最小化する位置に現フレーム上のポリゴンポイントを移動させることによりその差を最小化する。内角の差を最小化させるために移動させるポリゴンポイントはブロックマッチング結果とも矛盾しない範囲での移動量となる。これによって現フレーム上でのポリゴン形状の修正がなされる。
【００７６】
トラッキング対象オブジェクトは変形無しの剛体移動だけをするとは限らない。オブジェクト領域は僅かながらも変形をする可能性がある。そのため、現フレームとのマッチングを行う際に、前フレーム上のブロック形状を不変として比較してはならない。この問題を解決するために、“変形”及び“変形限界”という新しい考え方をブロックマッチングアルゴリズムに導入した。変形処理は次のようにして行う。前フレーム上の各ブロックピクセルに対しては、対応する現フレーム上のピクセルとのマッチングを行うのに加えて、そのピクセルに隣接するピクセルとのマッチングも行う。隣接ピクセル数は適用する変形限界によって定められる。図１１の丸７はマッチングに使うブロックピクセルである。このブロックの多孔率は３となっている例である。前フレームのブロック（Ａ）上の丸ピクセル７が、現フレーム上の対応するブロック（Ｂ）の丸ピクセル７とマッチングされる。前フレーム上の丸ピクセル７は、現フレーム上の対応するブロックピクセル７との比較に加えて、さらに隣接ピクセル８ともマッチングされる。すなわち、前フレーム上の各ブロックピクセルは現フレーム上の９側のピクセルとマッチングされることになる。
【００７７】
理想的には、トラッキング対象のオブジェクトを最初のフレーム上で定義すれば、Ｍａｓｋ  Ｔｒａｃｋｅｒアプリケーションが最後のフレームまでトラッキングするのが望ましい。しかし実際には多くの理由によりそれは不可能である。例えば、Ｍａｓｋ  Ｔｒａｃｋｅｒアプリケーションは対象領域をフレームを追ってトラッキングするが、前後のフレーム間には認知し難いレベルの小さな誤差が発生する。この誤差はフレームを追うに従って累積され、ついには明確に認識できるレベルの違いが生じる。この問題に対処する方法としてキーフレームという考え方が導入された。
【００７８】
ユーザは前もって数箇所のフレーム上にトラッキング対象オブジェクトを定義しておく。これらのフレームがキーフレームである。トラッキングに問題が発生しやすいと考えられるフレームをキーフレームとして設定する。問題が起こりやすいケースしては次のような場合がある。
【００７９】
（１）オブジェクトが急激、または極めて速い動きをする場合
（２）カメラの動きが大きい場合
（３）複数オブジェクトが重なり合う場合
（４）照明状況が変化する場合
トラッキングの途中でキーフレームに到達すると、Ｍａｓｋ  Ｔｒａｃｋｅｒアプリケーションはキーフレーム上に定義済みのオブジェクトポリゴンを使ってトラッキングを行う。キーフレームに到達した時点で誤差の累積はキャンセルされることになる。このやり方は処理時間の節約になるとともに、トラッキングが問題なく進行しているかどうかを監視しておく必要がないのでトラッキングのバッチ処理が可能となる。
【００８０】
繰り返し的な極めて速い動きが実際問題においては存在する。このようなケースでは、前フレームの情報だけに基づいて現フレームのトラッキングを行うシーケンシャルトラッキングでは追随能力上で問題が生じる。このような場合の対処法として、あらかじめ対象オブジェクトが取り得る位置を示すフレームをキーフレーム（参照フレーム）として登録しておく方式が開発された。登録されたすべての参照フレームに対して現フレームのトラッキングが実行され、その中で最良の結果を生じた参照フレーム上のポリゴンが現フレーム上でのポリゴン候補として選択される。このトラッキング処理の際にはポリゴン内部領域全体が比較対象となる。さらに最終調整として、上記処理で得られたポリゴン候補に対して現フレーム上で上下左右への平行移動、回転、オフセットを実行して領域全体比較での色の差異を最小にする形状を求める。
【図面の簡単な説明】
【００８１】
【図１】Ｍａｓｋ  Ｍａｓｋ  Ｔｒａｃｋｅｒシステムのブロック図
【図２】Ｍａｓｋ  Ｍａｓｋ  Ｔｒａｃｋｅｒシステムのフローチャート
【図３】Ｍａｓｋ  Ｔｒａｃｋｅｒハンドラーアルゴリズムのフローチャート
【図４】フレームトラッキングアルゴリズムのフローチャート
【図５】ポリゴンポイント近傍に生成されるシンプルブロックの説明図
【図６】ポリゴンポイント近傍に生成されるデリバティブブロックの説明図
【図７】多孔性ブロックの説明図
【図８】ブロックマッチングハンドラーアルゴリズムのフローチャート
【図９】ブロックマッチングの説明図
【図１０】デリバティブマスクのＸ係数とＹ係数の説明図
【図１１】変形限界の説明図
【図１】
2006293883.tif 000003
【図２】
2006293883.tif 000004
【図３】
2006293883.tif 000005
【図４】
2006293883.tif 000006
【図５】
2006293883.tif 000007
【図６】
2006293883.tif 000008
【図７】
2006293883.tif 000009
【図８】
2006293883.tif 000010
【図９】
2006293883.tif 000011
【図１０】
2006293883.tif 000012
【図１１】
2006293883.tif 000013