Two-Step Detection of Video Shot Boundaries in a Wavelet Transform Domain

本論文は、オンラインや編集済みの動画コンテンツが急増し、手作業での閲覧や検索が現実的でなくなっていることから、自動的な動画インデキシング（索引化）の必要性を扱う。内容に基づく動画インデキシング（content-based video indexing）では、動画を意味のある時間的単位に分割することが基本的なステップであり、「ショット（shot）」が最も基本的な構造要素として扱われる。著者らは、多くの確立されたショット境界検出法がフレーム間差分（例：画素値やヒストグラムの比較）に依存しており、急激な遷移（カット）は検出できても、緩やかな遷移（例：フェードやディゾルブ）では信頼性が低いことを指摘する。緩やかな遷移では2つのショットが混ざった中間フレームが生じ、距離信号がカットほど鋭くも、ショット内ほど安定もせず、見逃しや過剰な誤検出（false positives）につながる。これらを踏まえ、急激な遷移と緩やかな遷移の両方を検出できる堅牢性を高めるために、本論文はウェーブレット変換領域（wavelet transform domain）で動作する2段階のショット境界検出アルゴリズムを提案する。提案の動機として、ウェーブレット表現が粗い内容と局所的な活動をコンパクトに捉えやすいこと、また部分的にデコードされたMotion-JPEG 2000データに対しても処理できる可能性があることを挙げている。

報告された実験全体を通じて、提案する2段階のウェーブレット領域アルゴリズムは、比較対象の手法の中で総合的に最も良好な再現率–適合率（recall–precision）の挙動を示し、とりわけ緩やかな遷移が存在する場合に優れていた。27分のドキュメンタリー系列 *Challenge at Glen Canyon*（48,450フレーム）は、247個のショット境界（232カット、11ディゾルブ、4フェード）を含み、フィルム由来のノイズ（例：傷、フリッカー、位置ずれ）も含む。このデータでは、カット検出については全手法が良好に動作した一方、複数のフレームベース手法は、フェードによって誤検出が誘発されるため、高い再現率域で性能が大きく劣化した。これに対し、2段階法はこれらのフェードに対して頑健であり、テストされたアルゴリズムの中で最良の再現率–適合率曲線を示したと報告されている。47分のニュース番組 *V1-1*（71,379フレーム、477遷移：373カット、90ディゾルブ、7ワイプ、7特殊効果）では、2段階法は広い再現率範囲で高い適合率を維持したのに対し、競合手法は再現率が上がるにつれて適合率が低下した。著者らはその理由を、ディゾルブやワイプのような緩やかな遷移が多いことに帰している。より一般的に、著者らは、純粋なフレームベース検出器はノイズ、カメラ動作、短い緩やかな効果に過敏になり得る一方で、ゆっくりしたディゾルブには感度が不十分になり得ると結論づけ、提案する2段階手順はノイズに対する頑健性を高めつつ、緩やかな遷移への感度を向上させるとしている。

本手法は、ウェーブレット領域の特徴ベクトルで動画内容を表現し、2つの時間スケールで距離を計算する。各フレームについて、7段の分解レベルをもつ2次元の空間ウェーブレット変換を計算し、最も細かい2レベルは切り捨てる。特徴ベクトル (F={C,S}) は、(i) フレームの粗い近似として扱う最粗サブバンド係数 (C) と、(ii) より細かいサブバンド上の2値の有意マップ（binary significance map） (S) からなる。「有意」係数の大きさ閾値を明示的に選ばないために、上位(N)規則（top-(N) rule）を用い、絶対値が大きい順に上位(N)個の係数を有意としてマークする（実験では (N=50)）。それらの位置が (S) を構成する。フレーム間距離は、最粗サブバンドに対する (L_1) 距離と、有意マップに対するハミング距離（Hamming distance）の加重和として計算する。重みは、(w_0) を最粗サブバンド係数数の逆数、(w_1=1) とする。

緩やかな遷移をより捉えるため、動画を固定長の区間に分割する（提示例では30 fpsで1.0秒、すなわち区間あたり30フレーム）。区間特徴ベクトルは、空間的に最も粗いサブバンドの時間系列を取り出して1次元の時間ウェーブレット変換（Haar wavelet）を適用し、同様に区間有意マップを構成する。区間距離は、同じ結合メトリクスを3次元インデクシングに拡張して用いる。検出は2段階で行う。**STEP 1** では隣接区間間の区間距離を計算し、距離が閾値を超える区間にフラグを立てる。**STEP 2** では、「拡張」区間（次区間の最初のフレームを付加して形成）内でフレーム距離を計算し、最大距離を与えるフレームインデックスについて、距離が閾値を超える場合に境界を宣言する。この設計により、変化なしと判断された区間についてフレームレベル特徴を生成しないで済む。実装にはリフティングスキーム（lifting-scheme）のウェーブレット変換を用い、空間分解には（JPEG 2000と同様の）5/3-tap整数ウェーブレット、時間分解にはHaarを用いる。評価では、(a) 各8-bit RGBチャネルの上位2ビットを用いた（6-bitコードの）64ビンcolor codeヒストグラム距離法、および(b) 同じヒストグラム距離に基づいて実装したZhangのtwin-comparison法（下側閾値の重みをテストして最良のものを選択）と比較する。動画はMPEG-1であり、Motion-JPEGおよびMotion-JPEG 2000へトランスコードした。性能は、多数の閾値設定にわたる再現率–適合率曲線で評価した。

本論文は、ウェーブレット変換領域で動作する2段階検出戦略が、粗い内容の類似性（最粗サブバンド）と構造／活動の手がかり（より細かいサブバンドの有意マップ）を組み合わせることで、急激なショット遷移と緩やかなショット遷移の双方を高精度に検出できると結論づける。複数のテスト系列で得られた再現率–適合率曲線から、提案する2段階アルゴリズムは2つのベースライン手法およびウェーブレット法のフレームのみ版を上回り、とくに（フェードやディゾルブを含む）緩やかな遷移への対処で改善が見られ、カットに対しても有効であることが示された。さらに、特徴ベクトルが部分的にデコードしたビットストリームから導出できるため、Motion-JPEG 2000の圧縮領域（compressed-domain）処理と両立し、完全な画素領域処理に比べて計算量とメモリ要求を低減できる可能性がある点も意義として主張している（ただし、Motion-JPEG 2000のエントロピー復号により、実装はMotion-JPEGと異なりリアルタイムより遅くなったとも報告している）。総じて、本研究はウェーブレット領域でのマルチスケール比較を、より広いcontent-based video indexingおよび検索パイプラインにおけるショット分割の実用的な基盤として位置づけている。

著者らは複数の限界を挙げ、それに対応する今後の方向性を示す。第一に、ズームやパンなどのカメラ動作は、緩やかな遷移に似た区間距離・フレーム距離パターンを生み得るため誤検出の原因となる。これに対し、先行研究でモーション解析により誤検出を減らした例にならい、2段階検出器の後段にカメラ動作解析（例：motion estimationやoptical flow）を追加することを提案する。第二に、大きな物体の高速運動は、その結果のフレーム距離がカットに似るためショット遷移と誤検出され得る。著者らは、ショットのセマンティクスを理解せずにこのケースを区別するのは難しく、セマンティック解析は計算コストが高いと述べる。第三に、本論文は検出閾値を自動選択する方法を提供しておらず、代わりに閾値を掃引して再現率–適合率曲線を作成し、いくつかのパラメータを手動調整している（例：短いサブセットから導いた固定重み1.25）。実用上は、フレーム距離の分布に基づく自動閾値選択法が有益になり得るとしている。最後に、同じウェーブレット領域特徴ベクトル定義（(F={C,S})）を用いてcontent-based video retrieval方式を構築し、分割能力を視覚的類似性に基づく検索へ拡張する計画を述べている。

この論文は、インターネット上の動画や編集された動画が急増して、人が手作業で全部見たり探したりするのが難しくなっているため、動画を自動で整理しやすくする仕組みが必要だと考えています。
動画を内容にもとづいて整理するには、まず動画を意味のある時間のまとまりに分けることが大切で、その最小単位として「ショット(1台のカメラが連続して撮影した、時間的にまとまった区間です。動画を分割して整理する基本単位になります。)」を使います。

しかし、よくあるショット境界の検出方法は、隣り合うフレーム同士の違い（画素の値や色の分布など）を比べるものが多く、パッと切り替わる「カット(編集効果なしで、あるショットから次のショットへ一瞬で切り替わる急な遷移です。多くの検出法で見つけやすい基準になります。)」は見つけやすい一方で、ゆっくり切り替わる「フェード(画面がだんだん暗くなって単色に近づくフェードアウト、またはその逆のフェードインのことです。緩やかな遷移の代表例です。)」や「ディゾルブ(前のショットが薄れながら次のショットが現れて、2つが重なった状態がしばらく続く切り替えです。映像編集でよく使われます。)」は見つけにくいという問題があります。ゆっくり切り替わる場面では、2つのショットが混ざったような中間のフレームが続くため、判断があいまいになり、見逃したり、関係ない場所を境界だと間違えたりしやすいからです。

そこでこの論文は、急な切り替わりと、ゆっくりした切り替わりの両方に強い方法として、ウェーブレット変換(画像や信号を「粗い成分」と「細かい成分」に分けて表す変換です。大まかな形と細部の変化を同時に扱えるため、特徴抽出に役立ちます。)を使った「2段階」のショット境界検出アルゴリズムを提案しています。

実験の結果、提案手法（2段階のウェーブレット領域アルゴリズム）は、比べた他の方法よりも、全体として「見つけ漏れの少なさ」と「間違い検出の少なさ」のバランスが良く、とくにフェード(画面がだんだん暗くなって単色に近づくフェードアウト、またはその逆のフェードインのことです。緩やかな遷移の代表例です。)やディゾルブ(前のショットが薄れながら次のショットが現れて、2つが重なった状態がしばらく続く切り替えです。映像編集でよく使われます。)のような緩やかな切り替わりがある動画で強い性能を示しました。

例えば、27分のドキュメンタリー映像では、カット(編集効果なしで、あるショットから次のショットへ一瞬で切り替わる急な遷移です。多くの検出法で見つけやすい基準になります。)の検出はどの方法でもうまくいきましたが、フレーム同士の違いだけで判断する方法はフェードの影響で誤検出が増え、性能が悪化しました。一方、提案手法はフェードに強く、最も良い成績だったと報告されています。
47分のニュース映像でも、提案手法は幅広い条件で高い正確さを保ちましたが、他の方法は「たくさん見つけようとすると間違いも増える」傾向が強くなりました。これはニュース映像にディゾルブやワイプ(画面の一部が移動しながら次のショットに置き換わっていく切り替えです。ディゾルブと違い、画面内で領域が分かれて入れ替わるのが特徴です。)などの緩やかな切り替わりが多かったためだと説明されています。

提案手法は、動画の各フレームをウェーブレット変換(画像や信号を「粗い成分」と「細かい成分」に分けて表す変換です。大まかな形と細部の変化を同時に扱えるため、特徴抽出に役立ちます。)した結果から特徴を作り、2つの時間の見方で「どれくらい変わったか（距離）」を計算します。

まずフレームごとに、2次元の空間ウェーブレット変換を行い、粗い情報を表す部分と、細かい変化を表す部分を使って特徴ベクトル(対象（ここではフレームや区間）を数値のまとまりで表したものです。似ているかどうかを距離で比べるために使います。)を作ります。細かい部分については「どこが重要な変化か」を2値で表したマップを使い、重要な係数を選ぶために、値が大きいものから上位N個だけを重要として扱います。

次に、緩やかな切り替わりを捉えやすくするため、動画を固定長の区間（例：30fpsなら1秒＝30フレーム）に分け、区間どうしの違いも計算します。区間については、粗い情報の時間変化に対して時間方向のウェーブレット変換を行い、区間の特徴を作ります。

検出は2段階です。
STEP 1では、隣り合う区間どうしの距離を見て、怪しい区間を見つけます。
STEP 2では、怪しいとされた区間の中だけを詳しく調べ、フレーム間距離が最も大きくなる場所を探して、そこがしきい値(距離がこの値を超えたら境界だと判断するための基準値です。高くすると誤検出は減りやすいが見逃しが増えやすく、低くするとその逆になりやすいです。)を超えるとショット(1台のカメラが連続して撮影した、時間的にまとまった区間です。動画を分割して整理する基本単位になります。)境界だと判断します。
この仕組みにより、変化がなさそうな区間については細かい処理を省けるので、計算の無駄を減らせます。

比較対象として、色ヒストグラム(画像の中に各色がどれだけあるかなど、値の分布をまとめた表現です。細かな位置の違いに鈍感なので、ノイズにある程度強い利点があります。)による方法や、Zhangのtwin-comparison法（2つのしきい値を使う方法）と比べ、再現率(本当のショット境界のうち、どれだけ検出できたかの割合です。見逃しの少なさを表します。)と適合率(検出した境界のうち、本当に正しかったものの割合です。誤検出の少なさを表します。)の関係で性能を評価しています。

この論文は、ウェーブレット変換(画像や信号を「粗い成分」と「細かい成分」に分けて表す変換です。大まかな形と細部の変化を同時に扱えるため、特徴抽出に役立ちます。)を使って「粗い見た目の変化」と「細かい構造的な変化」を組み合わせ、さらに区間レベルとフレームレベルの2段階で調べることで、カット(編集効果なしで、あるショットから次のショットへ一瞬で切り替わる急な遷移です。多くの検出法で見つけやすい基準になります。)のような急な切り替わりだけでなく、フェード(画面がだんだん暗くなって単色に近づくフェードアウト、またはその逆のフェードインのことです。緩やかな遷移の代表例です。)やディゾルブ(前のショットが薄れながら次のショットが現れて、2つが重なった状態がしばらく続く切り替えです。映像編集でよく使われます。)のような緩やかな切り替わりも高精度に検出できると結論づけています。実験でも、比較した手法より良い結果が示され、とくに緩やかな切り替わりへの強さが確認されました。

また、Motion-JPEG 2000のような圧縮データから一部だけ復号した情報でも特徴を作れる可能性があり、画素を完全に復号して処理するより計算量やメモリを減らせる点も意義として述べています（ただし、Motion-JPEG 2000では復号処理が重く、リアルタイムより遅くなったとも報告しています）。

今後の課題として、次の点が挙げられています。
まず、ズームやパンなどのカメラ動作は、緩やかな切り替わりと似た変化のパターンを作るため、誤検出の原因になります。これを減らすために、2段階検出(まず区間単位で怪しい場所を絞り込み、次にその範囲だけフレーム単位で正確な位置を決める方式です。緩やかな遷移への対応と計算削減の両方に効きます。)の後にカメラ動作解析（動きを推定する処理）を追加する案が示されています。
次に、大きな物体が速く動く場面は、フレーム間の差がカット(編集効果なしで、あるショットから次のショットへ一瞬で切り替わる急な遷移です。多くの検出法で見つけやすい基準になります。)のように見えて誤検出されることがありますが、映像の意味まで理解しないと区別が難しく、その解析は計算コストが高いと述べています。
さらに、この論文ではしきい値(距離がこの値を超えたら境界だと判断するための基準値です。高くすると誤検出は減りやすいが見逃しが増えやすく、低くするとその逆になりやすいです。)を自動で決める方法がなく、実験ではしきい値をいろいろ試して評価しています。実用上は、距離の分布などからしきい値を自動決定する方法があると役立つとしています。
最後に、同じ特徴ベクトル(対象（ここではフレームや区間）を数値のまとまりで表したものです。似ているかどうかを距離で比べるために使います。)を使って、内容が似た映像部分を探す検索（動画検索）にも発展させたいと述べています。