逐次的な判定手続きに基づくショット境界の高速検出手法

映像からカメラの切り替え点を検出するショット境界検出は連続的なデータである映像を小さな構成単位（ショット）に分割する技術であり，映像解析における最も基本的な処理の１つである。本稿では，従来手法と同程度の検出精度を維持したまま，より高速にショット境界を検出する手法として，ショット境界の可能性が低いフレームに対しては処理を省略し，可能性の高い部分についてだけさまざまな特徴量を逐次的に算出する手法を提案する。実際の放送映像に対する実験では，再現率が90.4％，適合率が92.8％という良好な結果が得られた。また，約425分のテストデータに対する処理時間は208秒（MPEG-1のデコード時間を除く）であり，実時間の約１/123という高速な処理を実現した。

1. まえがき

放送映像は連続的なデータなので，映像解析を行うためには，まず，映像を小さな構成単位に分割する必要がある。構成単位としては，テキストにおける単語のように意味的にまとまりを持つものが望ましいが，映像解析では，一般的に，映像の物理的な特徴に基づいて分割が可能であるショット（１台のカメラで連続的に撮影されたフレーム列）が利用される。放送映像をショットに分割するためには，ショットとショットのつなぎ目であるショット境界を検出する必要がある。この検出処理は映像解析における最も基本的な処理の１つであり，ショット境界検出と呼ばれている。

ショット境界は前のショットから次のショットへ瞬時にショットを切り替える瞬時切り替えと，複数フレームにわたって徐々に切り替える漸次切り替えに大別できる。瞬時切り替えはカットとも呼ばれ，映像編集において最も頻繁に使用される切り替え方法である。漸次切り替えは２つのフレームの合成の割合を徐々に変化させるディゾルブやフェードなどに分類できる。ディゾルブは前のショットの画面全体が徐々に消えていき，次のショットの画面全体が徐々に現れてくるような切り替え方法である。また，フェードはディゾルブの１種であり，前のショットあるいは次のショットの全体が黒であるものを指す。

ショット境界は近接フレーム間の類似度に基づいて検出することができる。これは，２つのフレームが同一のショットに属している場合にはフレーム間の差分は小さく，２つのフレームの間にショット境界が存在する場合にはフレーム間の差分が大きいという特性に基づいている。フレーム間の差分を表す特徴量としては，色や輝度のヒストグラム差分¹⁾，エッジの変化量²⁾，動きベクトルの変化量³⁾，階調値の分散⁴⁾，画素間の相互情報量⁵⁾ など，さまざまな特徴量が提案されている。しかし，１種類の特徴量だけでは，カメラや被写体の動きによる変化と，ショット切り替えによる絵柄の変化とを精度よく区別することは難しい。そこで，近年，複数の特徴量を組み合わせる手法が提案されている^6)7)8)9)。エッジや色などの特徴を総合的に判断することで，単一の特徴量に基づく手法と比較して，高い検出精度を得ることができる。しかし，これらの手法では，入力映像の各フレームに対してさまざまな特徴量を計算する必要があり，計算コストが高くなるという問題がある。

そこで，本稿では，従来手法と同程度の検出精度を維持したまま，計算コストを削減する手法を提案する。提案手法では，従来手法のように，すべてのフレームに対して多くの特徴量を算出するのではなく，フレームごとに画像特徴量の算出とその特徴量に基づくショット境界の判定処理を逐次実行する。ショット境界ではないと判定した時点でそのフレームに対する処理を終了し，次のフレームの処理に移る。放送映像の大部分はショット境界以外のフレームによって占められており，これらのフレームに要する処理時間を短縮することで，全体の計算コストを大幅に削減することができる。

２章で提案手法の概要を説明し，３章，４章および５章で検出器の詳細について説明する。６章では提案手法を検出精度と計算コストの両面から評価する。７章で全体のまとめと課題を述べる。

2. 逐次判定によるショット境界検出

1図に提案手法の概要を示す。まず，入力された放送映像をデコードし，フレーム画像を取得する。次に，カット検出器，フェード検出器およびディゾルブ検出器を利用してショット境界を検出する。ショット境界の検出精度を上げるために，瞬時切り替え（カット）と漸次切り替え（フェード，ディゾルブ）の検出器を並列に配置する。なお，漸次切り替えはフェード，ディゾルブの順に処理する。フェードが検出された場合には，ディゾルブの検出処理を実行しないことで，誤検出の軽減と処理の高速化を図る。また，各検出器で算出されるさまざまなフレーム特徴量を３種類の検出器で共有し，同じ特徴量を重複して計算しないようにする。最後に，複数の検出器で検出されたショット切り替えを統合し，最終的な検出結果を出力する。統合処理では，ディゾルブと検出された区間内にカットが検出された場合や１つのディゾルブ区間と考えられる区間に複数のディゾルブ区間が検出された場合などを最終的にどのような検出結果とするかを経験則に基づいて判断する。以下，本稿の主題である３種類の検出器の詳細について述べる。

3. カット検出器

2図にカット検出器の検出手順を示す。カットは切り替えの前後でフレーム画像が大きく変化する。そのため，まず始めに，隣接フレームにおける赤（R)，緑（G)，青（B）の各階調値の絶対差分和d_sadを算出して，カットであるかどうかを判定する（2図(a))。d_sadは(1)式で与えられる。

ここで，ƒ_i(r)はi番目のフレームの座標rにおける画素値を表す。また，Fはフレーム全体の画素を，|F|は画素の総数を表す。実際にはR，G，Bごとに階調値の絶対差分和を求めるが，式が煩雑になるので，ここでは簡略化した式を示した。d_sadはフレームの変化に対して敏感に反応するので，誤検出が多発する可能性があるが，未検出は少ないという特徴がある。d_sadがしきい値T_sad以下である場合には，カットではないと判定して，そのフレームに対する処理を終了し，次のフレームの処理に移る。

次に，より精度の高いブロックマッチング差分d_bmを算出する（2図(b))。ブロックマッチングでは，フレームの映像を空間的に複数の矩形（くけい）状のブロックに分割し，各ブロックの映像と前のフレームの各ブロックの映像との差（以下，ブロック間コストと呼ぶ）が最小となる位置を探索する。ブロック間コストの算出には，カメラの動きに頑健な輝度ヒストグラムの絶対差分和を用いる。ブロック間の最小コストがしきい値を超えるブロックの数を総数で正規化した値をd_bmとする。なお，輝度ヒストグラムはR，G，Bのそれぞれに対して算出する。ショット境界の判定には，カメラの激しい動きなどによる誤検出を防ぐために，ブロックマッチング差分の増加量を用いる。カットと判定する条件を(2)式に示す。

ここで，d_ƒbmは前のフレームに対して算出するフレーム間差分であり，(3)式で与えられる。

本稿では，d_ƒbmを高速ブロックマッチング差分と呼ぶ。(2)式を用いてカットでないと判定された場合には，そのフレームに対する処理を終了して，次のフレームの処理に移る。

最後に，カメラのフラッシュによって引き起こされる誤検出を判定する（2図(c))。フラッシュが発光されると，最初の数フレームの間だけ輝度が上昇し，その後，元に戻る。そこで，フレームƒ_iからフレームƒ_i+Nƒの同じ位置における画素の最小輝度値で構成される画像を合成する。(4)式にの生成式を示す。

ここで，N_ƒはフラッシュの発光時間よりも長く設定する。ƒ_iがフラッシュによって輝度上昇した場合には，ƒ_i-1とは類似すると考えられる。そこで，ƒ_i-1との高速ブロックマッチング差分d_ƒbmを算出し，d_ƒbm(ƒ_i-2, ƒ_i-1)との差分がしきい値T_cut以下であればフラッシュによる誤検出，T_cutより大きければカットと判定する。カットと判定する条件は(5)式である。

カット検出器では，前述のすべての判定処理を通過したフレームをカットと判定する。

4. フェード検出器

漸次切り替えでは，まず，ディゾルブよりも検出精度の高いフェード検出を行う。先にも述べたように，フェードはディゾルブの１種で，切り替え区間の開始フレームあるいは終了フレームの画面全体が黒（以下，黒フレームと呼ぶ）である。フェード検出器の検出手順を3図に示す。

最初に，入力フレームが黒フレームであるかどうかを判定する。黒フレームの判定には，フレーム全体の平均輝度値と，輝度値の低い画素の割合を利用する。平均輝度値がしきい値T_blum以下であり（3図(a))，暗い画素の割合がしきい値T_blumより大きい場合に（3図(b)）黒フレームと判定する。黒フレームでないと判定した場合には，そのフレームに対する処理を終了し，ディゾルブの検出に移る。

黒フレームと判定された場合には，現フレームを終点とするフェードアウトであるか，または，現フレームを始点とするフェードインであるかの判定をそれぞれ行う。フェードインあるいはフェードアウトによる切り替え区間は，複数フレームにわたって連続して輝度が単調増加あるいは単調減少するかによって検出する（3図(c))。単調増加あるいは単調減少している画素の割合がしきい値T_fadeより大きい場合にはフェードの可能性があると判定する。

輝度の低い物体の面積が徐々に増加あるいは減少する場合にも，単調増加あるいは単調減少する画素の割合がしきい値T_fadeよりも大きくなることがある。そこで，輝度の低い物体の面積が徐々に変化する場合とフェードとを区別するために，隣接フレーム間の類似度（余弦類似度）を算出し，その値がしきい値T_fsim以下である場合をフェードの可能性があると判定する（3図(d))。3図(c)および3図(d)が連続的に成り立つ区間をフェード区間として検出する。なお，余弦類似度がしきい値T_fsimより大きい場合には，フレーム番号を＋１（または，－１）して，輝度が単調増加あるいは単調減少する画素の割合がしきい値T_fade以下になるまでループする。

最後に，検出されたフェード区間の長さが十分に長い場合をフェードと判定する（3図(e))。なお，3図でフェード開始フレームと検出された場合においても，その次のフレームを3図の最初の入力フレームとして処理を行い，フェードの検出精度を上げる。すなわち，理想的なフェード検出器であれば，１つのフェード区間に対して，複数回，フェード区間であると判定することになる。

5. ディゾルブ検出器

フェード検出器でフェード未検出のフレームに対して，ディゾルブ検出を行う。本稿では，(6)式でディゾルブのモデルを表現する。

ここで，ƒ_dbはディゾルブによる切り替えの開始フレームを，ƒ_deは終了フレームを表す。また，βは開始フレームでは０であり，終了フレームでは１である。

4図にディゾルブ検出器の検出手順を示す。ディゾルブでは複数のフレームにわたって映像が徐々に変化するので，カットと同じ手法で検出することは難しい。

まず，現フレームƒ_iとN_dフレーム前のフレームƒ_i-Ndとの絶対差分和d_sad(ƒ_i-Nd, ƒ_i)を用いて，ディゾルブの可能性がある区間を検出する（4図(a))。d_sad(ƒ_i-Nd, ƒ_i)がしきい値T_sad以下の場合には，ディゾルブではないと判定し，そのフレームに対する処理を終了し，次の入力フレームを待つ。

次に，(6)式のモデルに基づく２種類の特徴量を用いてディゾルブの候補区間を検出する。第１の特徴量は単調に変化する画素の割合である。フレームが(6)式に従って単調に変化するとき，フレームの各画素の値は単調に増加あるいは単調に減少する。そこで，第１の特徴量として(7)式を定義する。

ここで，

である。

第２の特徴量は理想的なディゾルブとの差分である。(6)式においてが一定の速度で変化する場合には，(9)式が成り立つ。

そこで，(10)式で算出される絶対差分和を第２の特徴量とする。

２つの特徴量を用いた候補区間の具体的な判定方法を説明する。(7)式および(10)式のような現フレームとその前後のフレームに基づく特徴量ではカメラや被写体の動きによる誤検出が多発する。そこで，提案手法では，5図に示す４種類のフレームの組み合わせに対して特徴量を算出する。(11)式と(12)式が同時に成り立つ場合には，フレーム番号を＋１してループし，(11)式と(12)式が同時に連続して成り立つ区間（以下，ディゾルブ候補区間と呼ぶ）の長さを求める（4図(b)，(c))。なお，(11)式と(12)式が１度も同時に成り立たない場合には，ディゾルブ候補区間の長さは０である。

次に，検出されたディゾルブ候補区間の長さが十分であるかどうかを判定する。ディゾルブ候補区間の長さがしきい値T_dur以下の場合には，ディゾルブではないと判定し，そのフレームに対する処理を終了する（4図(d))。

アイリスの変動などによって輝度値が時間的に滑らかに変化する場合にも(11)式と(12)式が成り立ち，誤検出となる場合がある。そこで，候補区間の開始フレームƒ_dbと終了フレームƒ_deの類似度を算出し，それがしきい値T_dsimよりも大きい場合には誤検出と判定し，そのフレームに対する処理を終了する（4図(e))。

また，輝度値が空間的に滑らかに変化するような画像が一定の方向に移動した場合にも誤検出となる場合がある。そこで，ƒ_dbおよびƒ_deが滑らかな背景を持つ画像かどうかを判定する（4図(f))。判定には，(13)式の特徴量を利用する。

ここで，

である。

g_smooth(ƒ_db)またはg_smooth(ƒ_de)がしきい値T_smoothより大きい場合には，更に，ƒ_dbとƒ_deの輝度ヒストグラム差分d_histを算出し，この値がしきい値T_hist以下である場合には誤検出と判定し，そのフレームに対する処理を終了する（4図(g))。

最後に，ƒ_dbとƒ_deの高速ブロックマッチング差分d_ƒbmを計算し，d_ƒbmの増加量がしきい値T_cutよりも大きい場合にディゾルブと判定する（4図(h))。

ディゾルブの中には，ごくまれに数秒間にわたる長い切り替え時間を持つものがある。このような長いディゾルブでは，隣接フレーム間において画像がほとんど変化しないので，前述の処理では検出が難しい。そこで，通常のディゾルブ検出を実施した後，(11)式と(12)式におけるフレーム間隔をN_ld倍に設定し，再度，検出処理を実行し，切り替え区間の長いディゾルブを検出する。

6. 評価実験

実験にはTRECVID（Text REtrieval Conference — VIDeo retrieval evaluation）2007の映像データセットを利用した。TRECVIDは米国国立標準技術研究所（NIST ： National Institute of Standards and Technology）が主催している映像検索やコンテンツ解析に関する国際的なベンチマークワークショップである¹⁰⁾。映像データはオランダで放送されたテレビ番組であり，内容は主にドキュメンタリーや子供番組，教育番組などである。映像データの合計長は425分である。また，フレームサイズは352×288ピクセル，フレームレートは25 fpsであり，映像はすべてMPEG-1形式でエンコードされている。

本手法で利用するしきい値はさまざまなジャンルの放送映像（ドラマ，スポーツ，ドキュメンタリーなど）を用いた予備実験を行って決定した。具体的には，しきい値をさまざまに変化させて，検出精度が良好な値を実験に用いた。検出精度の評価には，再現率（recall)，適合率（precision)，F値（F — measure）を用いた。再現率および適合率は(18)式で与えられる。

ここで，N_gは映像に含まれるショット境界の総数，N₀は提案手法で検出したショット境界の総数，N_bothは映像に含まれるショット境界のうち提案手法で検出できた数を表す。再現率は未検出の少なさを，適合率は誤検出の少なさを表す指標である。また，(19)式で示すF値は，トレードオフの関係にある再現率と適合率を統合した指標で，未検出および誤検出の両方を考慮した全体的な精度を表す。

6.3．既存手法との比較

既存手法との比較結果を6図に示す。比較に用いた手法はTRECVID 2007のショット境界検出課題に提出された手法¹¹⁾ である。グラフの横軸がF値，縦軸が処理時間であり，右下にある手法ほど高速で高精度な手法であることを表している。提案手法の検出精度はK，B，Mの手法に次いで４番目の精度であった。提案手法のF値は0.915であり，他の手法と比較してもそん色のない結果であった。また，処理時間については，CPUの性能に多少の差はあったが，提案手法が最も高速で，処理時間は他の手法の1/2から1/360程度であった。検出精度が上位の３手法については，提案手法よりもF値は0.01から0.03程度高かったが，処理時間は提案手法の３～８倍程度であった。提案手法は処理時間と検出精度の両方が要求されるアプリケーションにおいて有効な手法と言える。

7. あとがき

高精度で高速にショット境界が検出可能な手法を提案した。提案手法では，ショット境界の可能性が低いフレームについては処理を省略し，可能性が高い部分についてだけさまざまな特徴量を逐次的に算出することで，検出精度と計算コストを両立させた。実際の放送映像を利用した実験では，再現率が90.4％，適合率が92.8％という良好な結果が得られた。また，約425分の放送映像に対する処理時間は208秒（MPEG-1のデコード時間を除く）であり，実時間の約1/123という高速な処理が実現できた。

今後の検討課題としては，各処理におけるしきい値の決定方法がある。学習データから最適な組み合わせを決定するような手法についての検討が必要である。

本稿は電子情報通信学会論文誌に掲載された以下の論文を元に加筆・修正したものである。
河合，住吉，八木：“逐次的な特徴算出によるディゾルブ，フェードを含むショット境界の高速検出手法，” 電子情報通信学会論文誌，Vol.J91-D, No.10, pp.2529-2539（2008)，copyright©2008 IEICE