コンピュータビジョン特論 第７回対象追跡 ２００６年１１月１５日 加藤丈和

レポート予告 追跡プログラムコンテスト 動画ファイルの対象を追跡 初期位置は手で与える アルゴリズムはなんでもよい 照明、位置、向きが変化する対象 初期位置は手で与える アルゴリズムはなんでもよい 具体的には、次週の終わりに出題

対象追跡とは（検出と追跡） コンピュータビジョンにおける追跡タスクとは？ 検出と追跡はどう違うのか？ 検出：一枚の画像から指定した条件をみたす画像領域を抜き出す処理 追跡：動画像から指定した領域を抜き出し、フレーム間で対応づける処理

検出と追跡 検出 追跡 一枚の画像から 対象を抜き出す 対象のモデル 入力画像 複数フレーム間で対象を対応づける t-1フレーム tフレーム

検出と追跡 毎フレーム対象を検出すれば追跡？ 対象のモデル フレーム 入力画像 フレーム間で対応づけていない →追跡ではない

検出と追跡 二個検出された t-1フレーム tフレーム どちらが対応している？ 検出だけではわからない フレーム間で対応付けていないのは追跡ではない 検出結果をフレーム間で対応付ければ追跡

追跡の応用分野 サーベイランス（観測、監視） 運動解析 ３次元形状復元（Structure from Motion）

追跡手法に要求される要素 計算コスト 複雑な背景の元でのロバスト性 環境変動への対応 パラメータ調整の容易さ リアルタイム（ビデオレート） 室内、屋外、雑踏 環境変動への対応 照明変化、背景変動 パラメータ調整の容易さ 初期設定、閾値

追跡手法の分類 対象の表現（モデル）による分類 類似性尺度による分類 探索方法による分類 これらは互いに関連する 追跡対象の情報を何で表現するか 見え（局所画像）、色ヒストグラム、エッジなど 類似性尺度による分類 モデルと画像をどう対応付けるか 二乗誤差、相関、など 探索方法による分類 どうやって追跡対象を見つけるか （周辺）全探索、勾配法、動き予測 これらは互いに関連する

対象追跡研究の推移 全探索 勾配法 予測に基づく手法 屋外・環境変動への対応 軍需関係？ サーベイランス 見えに基づく手法 動きのモデル化 オフライン処理 リアルタイム処理 屋外・環境変動への対応 軍需関係？ サーベイランス 個人認識、人物監視 全探索 勾配法 予測に基づく手法 ・1968 更新テンプレートマッチング 見えに基づく手法 ・1981 Lucas-Kanade 勾配法(レジストレーション） ・1991 Tomasi-Kanade 勾配法（特徴点追跡） ・1971 航空機画像解析 　（雲の動きの解析） ・1995 モンテカルロフィルタの利用 　　　bootstrap filter 動きのモデル化 時系列フィルタリング ・1980後半 カルマンフィルタの利用 ・1998 M. Isard, A. Blake ConDensation ・1992 J. Boyce, D. Toulson α-β-γトラッカー ・1975 K. Fukunaga 　Mean-Shift Mean-Shift ・2000 D,. Comaniciu P. Meer Mean-Shiftを使った非剛体追跡 クラスタリングに基づく手法 基盤となる要素技術の発展 ・1999　EMベースの追跡 パターン認識に基づく手法 ハードウェアの発展 ・2001　SVMを使った追跡 1980年 1990年 2000年

見えに基づく追跡

見えに基づく追跡手法 （ブロックマッチング＋全探索） １．局所領域（ブロックを切り出す） 比較 ３．ブロックを切り取って比較 ４．最も類似した領域 を結果とする 類似度最大 （相違度最小） t-1フレーム tフレーム ２．前のフレームの周辺を探索 類似性尺度が最大になる領域を周辺領域から探す

見えに基づく手法の類似性尺度 よく用いられる類似度(相違度)１ SSD(Sum of Squared Differences) x 画素毎の差分の二乗和（二乗誤差） x Ｗ I t-1 d x+d I t

見えに基づく手法の類似性尺度 SSD(Sum of Squared Differences) 最も基本的な誤差関数 画像をベクトルとみなせば、ベクトル間のユークリッド距離（の二乗） 外れ値の影響を受けやすい 照明変化の影響を受けやすい 画素値が全体的に変化する ラスタスキャン 多次元ベクトルと考える 画素毎に差をとって二乗 総和

見えに基づく手法の類似性尺度 よく用いられる類似度(相違度)２ SAD(Sum of Absolute Differeces) 画素毎の差分の絶対値の和 画像をベクトルとみなした場合のＬ１距離（市街地距離） SSDに比べて外れ値の影響を受けにくい 照明の影響を受けやすい SSD

見えに基づく手法の類似性尺度 よく用いられる類似度(相違度)３ CC(Cross Correlation) 正規化相互相関 ベクトル間の内積（角度） 照明変化に強い 明るさの正規化 SSD,SAD コントラスト の正規化 CC ノルムが変化しても内積 CCは変わらない

見えに基づく追跡まとめ 類似度（相違度） 類似度最大もしくは相違度最小の変位ｄを求める SSD（二乗誤差） SAD（絶対誤差） CC（正規化相互相関）

見えに基づく追跡の拡張 変位ｄだけでなく、拡大、縮小、回転などの領域の変形を含む追跡 アフィン変換

見えに基づく追跡の拡張 ６パラメータの最小化が必要→計算量が大きい 　　　　　　　　　　　　　　　　　　　全探索では非現実的

見えに基づく追跡＋ 全探索の問題点 計算量が多い 変位量が離散的 勾配法による追跡 ブロックサイズ×探索領域のサイズの計算コスト 回転、スケールなどに拡張した場合はさらに計算コストが増大する 変位量が離散的 勾配法による追跡

見えに基づく追跡 ＋勾配法 勾配法とは、暫定解まわりの勾配（傾き）に基づいて山登り（山くだり）によって極大値（極小値）を見つける Lucas Kanade法

Lucas & Kanade法 Σ内の第一項目をテイラー展開すると 変位が微少であるとして２次以降の項を無視 (ｘ周辺で線形近似）

テイラー展開とは？ のように変換でき、f(x)のaのまわりのテイラー級数展開という

Lucas & Kanade法

Lucas & Kanade法 探索不要で解が求まる アフィン変換などへの拡張も可能

Lucas & Kanade法の実装 空間微分＝ 隣り合う画素の差 Sobelオペレータ 時間微分＝フレーム間の差分

Lucas & Kanade法の実装 t-1フレーム tフレーム フレーム間差分

Lucas & Kanade法と追跡の安定性 の第二固有値が０→ランク落ち→解が求まらない 同じ方向の勾配しか存在しない場合 勾配に直交する方向の位置が定まらない aperture problem(窓問題) 固有値が０に近いと不安定

Lucas & Kanade法と追跡の安定性 　　　　の二つの固有値が大きいとき追跡が安定に行える 強い勾配が存在する いろんな方向（直交する方向）に強い勾配が存在する このようなブロックの追跡は安定

追跡に適した特徴の抽出 GoodFeaturesToTrackアルゴリズム の最小固有値が極大になる特徴点（局所画像）を抽出 　　　　の最小固有値が極大になる特徴点（局所画像）を抽出 ３次元形状復元などでよく用いる

見えに基づく追跡まとめ 局所画像そのものを対象モデルとする SSD,SAD、CCなどの類似性尺度を用いる 平行移動だけでなく、回転、スケールなどへ拡張可能 全探索では計算量が多い→勾配法 Lucas＆Kanade法 追跡しやすい特徴点の抽出 GoodFaturesToTrack

色ヒストグラムによる追跡

色ヒストグラムによる追跡 見えに基づく追跡の問題点 同じ位置の画素ごとに比較するため 対象領域全体の統計量を使う 対象の形状変化に弱い 非剛体の追跡には向いていない 同じ位置の画素ごとに比較するため 対象領域全体の統計量を使う →色ヒストグラム

色ヒストグラムとは？ ヒストグラムを色空間に拡張 色空間を矩形分割し、各色の数をカウントする 照明変動の影響を避けるため、輝度成分をのぞいた色空間を用いることが多い

ヒストグラム間の類似性尺度

ヒストグラム間の類似性評価 Bhattacharyya Coeficient(バタッチャリア係数)

ヒストグラムによる追跡 対象領域ないのヒストグラムを計算 対象モデル モデルヒストグラム 入力ヒストグラム ポジション

ヒストグラムによる追跡 類似度

ヒストグラムによる追跡＋勾配法 Mean Shift 重み付きヒストグラム u番目のbinの値 カーネル関数 ｋ（ｄ） ｄ

Mean Shift 入力画像のヒストグラムも同様に定義 xi y h hはスケール

Mean Shift バタッチャリア係数をテイラー展開（１次の項まで） 前のフレームの位置 重み付きヒストグラムの式を第二項に代入 定数

Mean Shift 第二項を最大化→微分＝０より カーネル関数の微分

Mean Shift ヒストグラムの比 特に とすると １ 微分が定数 ヒストグラムの比 ヒストグラムの比を重みとして、領域内の重心を求める

ヒストグラムに基づく追跡まとめ 対象領域内のヒストグラムを使って類似性を評価 画素ごとの比較をせず、領域ないで積算した特長を使う 形状変化、姿勢変化に強い 姿勢、スケールの推定は難しい 勾配法の適用→MeanShiftアルゴリズム 領域内でヒストグラムの重心を求めるだけでよい

その他の表現を用いた追跡 エッジのマッチングによる追跡 輪郭による追跡 3次元モデルを用いた追跡 　　など。。。

輪郭（エッジ）に基づく追跡 詳細は次週 ConDensation （IJCV98 M. Isard and A. Blake） 対象表現：輪郭モデル 類似度(尤度）：エッジと輪郭の距離 照明変化、色の変化に強い 裾野が広く、滑らかな尤度分布 The Condensation algorithm home pageより

まとめ モデルの表現と類似性尺度について 勾配法に基づく探索について 見えに基づく追跡 色ヒストグラムによる追跡 →Lucas Kanade法 色ヒストグラムによる追跡 →Mean Shift法

出席チェック 出席チェック 次回は予測に基づく追跡について 検出と追跡は何が違うか？ 見えに基づく追跡の弱点はなにか？ 勾配法による探索の利点を２つあげなさい 学籍番号と名前を記入して提出 次回は予測に基づく追跡について