(57)【特許請求の範囲】
【請求項１】
動画像のフレーム画像を取得する取得手段と、
フレーム画像の特徴量を抽出する抽出手段と、
前記特徴量を前記フレーム画像に対応付けて蓄積する蓄積手段と、
前記抽出手段で抽出した特徴量と前記蓄積手段に蓄積している特徴量とを比較し、前記動画像のシーンチェンジを検出する検出手段と、
前記検出手段による前記動画像のシーンチェンジの検出頻度に応じて前記検出手段の検出感度を制御する制御手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
前記シーンチェンジの検出が多い場合に、前記制御手段が前記検出手段のシーンチェンジの検出感度を下げることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記シーンチェンジの検出が少ない場合に、前記制御手段が前記検出手段のシーンチェンジの検出感度を上げることを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記検出手段は、前記抽出手段で所定のフレームから抽出した特徴量が、前記所定のフレームから複数個前までの各フレームから抽出された特徴量の何れにも類似しないと判断された場合に前記所定のフレームにシーンチェンジがあるとして検出することを特徴とする請求項１乃至３の何れか１項に記載の画像処理装置。
【請求項５】
前記検出手段で検出した前記シーンチェンジのフレームに関する情報を前記フレーム画像と関連付けて記憶する記憶手段をさらに備えることを特徴とする請求項１乃至４の何れか１項に記載の画像処理装置。
【請求項６】
前記記憶手段が、前記検出されたシーンチェンジに関するフレームの情報として、検出されたシーンチェンジのフレームの動画先頭からのフレーム数あるいは経過時間を記憶することを特徴とする請求項５に記載の画像処理装置。
【請求項７】
前記抽出手段が、前記フレーム画像を複数のブロックに分割し、ブロック毎に抽出した特徴量を量子化しラベル行列とすることを特徴とする請求項１乃至６の何れか１項に記載の画像処理装置。
【請求項８】
前記検出手段が、前記抽出手段で抽出したラベル行列と前記蓄積手段に蓄積しているラベル行列とを、行又は列毎にＤＰマッチングで比較することを特徴とする請求項７に記載の画像処理装置。
【請求項９】
前記検出感度は前記検出手段におけるＤＰマッチングの整合窓の幅であって、前記制御手段がシーンチェンジの検出頻度に応じて前記整合窓の幅を調節することを特徴とする請求項８に記載の画像処理装置。
【請求項１０】
前記検出手段は、ラベル行列を比較する際に類似度を算出し、演算した類似度が所定値以下になった場合にシーンチェンジと判定することを特徴とする請求項９に記載の画像処理装置。
【請求項１１】
前記検出手段は、所定のフレーム画像のラベル行列の値と以前のフレーム画像のラベル行列の値とを比較する際に、ペナルティーテーブルを参照してペナルティー値を取得し、取得したペナルティー値に基づいて類似度を算出することを特徴とする請求項１０に記載の画像処理装置。
【請求項１２】
前記ラベルは、多次元特徴量空間を複数のセルに分割して得られたセルの夫々に与えられる固有のラベルであり、前記ペナルティー値は、２つのラベルが表すセル間の距離に基づいて設定される値であることを特徴とする請求項１１に記載の画像処理装置。
【請求項１３】
前記検出手段は、
シーンチェンジのフレーム候補のフレーム画像データのラベル行列より抽出される行単位のラベル列と、それ以前のフレーム画像データのラベル行列より抽出される行単位のラベル列とをＤＰマッチングによって対応づけて、該抽出された画像データの行並びを得る第１マッチング手段と、
シーンチェンジのフレーム候補のフレーム画像データのラベル行列の行並びと、前記第１マッチング手段で得られた行並びとの類似度をＤＰマッチングによって求める第２マッチング手段とを備えることを特徴とする請求項１乃至１２の何れか１項に記載の画像処理装置。
【請求項１４】
前記第２マッチング手段によって得られた類似度が所定値以下になり、更にそれ以前のフレーム画像に対して上記と同様の処理を行なった結果、前記第２マッチング手段によって得られた類似度が所定値以下になる場合に、シーンチェンジのフレーム候補のフレーム画像データをシーンチェンジのフレーム画像データと決定するフレーム決定手段を更に備えることを特徴とする請求項１３に記載の画像処理装置。
【請求項１５】
前記第２マッチング手段は、行並びにおける各行番号のペアについてペナルティー値を保持する行間ペナルティーテーブルを有し、前記シーンチェンジのフレーム候補のフレーム画像データの行並びと前記それ以前のフレーム画像の行並びの類似度をＤＰマッチング手法を用いて算出するに際して、該行間ペナルティーテーブルを参照することを特徴とする請求項１４に記載の画像処理装置。
【請求項１６】
動画像のフレーム画像を取得する取得工程と、
フレーム画像の特徴量を抽出する抽出工程と、
前記特徴量を前記フレーム画像に対応付けて蓄積する蓄積工程と、
前記抽出手段で抽出した特徴量と前記蓄積手段に蓄積している特徴量とを比較し、前記動画像のシーンチェンジを検出する検出工程と、
前記検出工程における前記動画像のシーンチェンジの検出頻度に応じてシーンチェンジの検出感度を制御する制御工程と、
を備えることを特徴とする画像処理方法。
【請求項１７】
動画像のフレーム画像を取得する取得工程と、
フレーム画像の特徴量を抽出する抽出工程と、
前記特徴量を前記フレーム画像に対応付けて蓄積する蓄積工程と、
前記抽出手段で抽出した特徴量と前記蓄積手段に蓄積している特徴量とを比較し、前記動画像のシーンチェンジを検出する検出工程と、
前記検出工程における前記動画像のシーンチェンジの検出頻度に応じてシーンチェンジの検出感度を制御する制御工程と、
をコンピュータに実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動画から動画シーンの変わり目、いわゆるシーンチェンジを検出する画像処理方法及び画像処理装置に関するものである。
【０００２】
【従来の技術】
従来より、動画からシーンチェンジを抽出する方法として、動画を構成する各フレームの色のヒストグラムを取りその変化を演算し、その評価値を何らかのしきい値処理を行なうことで検出する方法や、ＭＰＥＧ２等で用いる動きベクトル情報を用いた方法が提案されてきた。
【０００３】
【発明が解決しようとする課題】
しかしながら、ヒストグラムを用いる方法は、計算コストが小さく処理が早くリアルタイム性があるという長所がある反面、次のシーンが似たようなヒストグラムを持つシーンにおいてはシーンチェンジが検出できない、あるいは物体の急激な変形や回転によりシーンチェンジが過剰に検出されるなどの欠点もあった。
【０００４】
また、動きベクトルを用いた方法は、精度が高くオブジェクト抽出等の他の応用も考えられる処理であるが、計算に非常に多くの時間がかかり、リアルタイム性がないという欠点がある。また、ＭＰＥＧ２でエンコードされたデータから動きベクトル情報を抜き出し、動きベクトル演算を省略する場合でも、この動きベクトル演算の精度はエンコーダの性能に依存しているので、必ずしも全てのＭＰＥＧ２のファイルに対して高い性能を約東できないなどの弱点があった。
【０００５】
本発明は、上記の問題点に鑑みてなされたものであり、色とその構図を考慮したシーンチェンジ検出を行う画像処理方法及び画像処理装置を提供することを目的とする。
【０００６】
また、本発明の他の目的は、ファイルのエンコーダに依存せず、しかもリアルタイム性のある効果的で且つ処理の軽いシーンチェンジ検出を行う画像処理方法及び画像処理装置を提供することにある。
【０００７】
【課題を解決するための手段】
上記の目的を達成するための本発明の画像処理装置は、動画像のフレーム画像を取得する取得手段と、フレーム画像の特徴量を抽出する抽出手段と、前記特徴量を前記フレーム画像に対応付けて蓄積する蓄積手段と、前記抽出手段で抽出した特徴量と前記蓄積手段に蓄積している特徴量とを比較し、前記動画像のシーンチェンジを検出する検出手段と、前記検出手段による前記動画像のシーンチェンジの検出頻度に応じて前記検出手段の検出感度を制御する制御手段と、
を備えることを特徴とする。
【０００８】
また、上記目的を達成する本発明の画像処理方法は、動画像のフレーム画像を取得する取得工程と、フレーム画像の特徴量を抽出する抽出工程と、前記特徴量を前記フレーム画像に対応付けて蓄積する蓄積工程と、前記抽出手段で抽出した特徴量と前記蓄積手段に蓄積している特徴量とを比較し、前記動画像のシーンチェンジを検出する検出工程と、前記検出工程における前記動画像のシーンチェンジの検出頻度に応じてシーンチェンジの検出感度を制御する制御工程と、を備えることを特徴とする。
【０００９】
また、上記目的を達成する本発明の記憶媒体は、動画像のフレーム画像を取得する取得工程と、フレーム画像の特徴量を抽出する抽出工程と、前記特徴量を前記フレーム画像に対応付けて蓄積する蓄積工程と、前記抽出手段で抽出した特徴量と前記蓄積手段に蓄積している特徴量とを比較し、前記動画像のシーンチェンジを検出する検出工程と、前記検出工程における前記動画像のシーンチェンジの検出頻度に応じてシーンチェンジの検出感度を制御する制御工程と、をコンピュータに実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体である。
【００１０】
【発明の実施の形態】
以下、添付の図面を参照して本発明の好適な一実施の形態を説明する。
【００１１】
＜本実施の形態の画像処理装置の構成例＞
図１は、本実施の形態のシーンチェンジ検出機能を有する画像処理装置の構成例を示すブロック図である。
【００１２】
同図において、１０１はＣＰＵであり、本実施の形態のシーンチェンジ検出装置における各種演算・制御を実行する。１０２はＲＯＭであり、本装置の立ち上げ時に実行されるブートプログラムや各種の固定データを格納する。１０３はＲＡＭであり、ＣＰＵ１０１が処理するための制御プログラムを格納するとともに、ＣＰＵ１０１が各種制御を実行する際の作業領域を提供する。例えば、ＲＡＭ１０３は、動画像の複数フレームのラベル列を記憶するラベル列記憶部１０３ａと、ラベル列生成モジュールやＤＰマッチングモジュール等を含むプログラム記憶部１０３ｂとを有し、例えば、以下に説明するフレーム画像メモリとしても使用される。１０４はキーボード、１０５はマウスであり、ユーザによる各種入力操作環境を提供する。
【００１３】
１０６は外部記憶装置であり、ハードディスクやフロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ等で構成され、例えば、以下に説明する動画像管理データベースを記憶する。１０７は表示器である。１０８はネットワークインターフェースであり、ネットワーク上の各機器との通信を可能とする。１０９はインターフェース、１１０は動画像入力のための周辺機器である。また、１１１は上記の各構成を接続するパスである。
【００１４】
なお、上記の構成において外部記憶装置１０６はネットワーク上に配置されたもので代用してもよく、動画像入力のための周辺機器１１０はビデオカメラのほかビデオデッキやビデオプレーヤー及びテレビチューナーの様に動画を入力する様々な機器を指す。また、ＲＡＭ１０３の制御プログラムは、外部記憶装置１０６あるいは周辺装置１１０やネットワークからロードされて実行されるよう構成されてもよい。
【００１５】
図２は、本実施の形態の画像処理装置装置のシーンチェンジ検出機能の構成を示すブロック図である。
【００１６】
同図において、１１はユーザインターフェース部であり、表示器１０７、キーボード１０４及びマウス１０５を用いて、ユーザからの各種の操作入力を検出する。１２は動画像入力部であり、動画像入力のための周辺機器１１０による動画像のフレーム取り込みを行う。１３はフレーム画像メモリであり、動画像入力部１２によって得られたフレーム画像のデータをＲＡＭ１０３の所定の領域に格納する。
【００１７】
１４は画像特微量抽出部であり、フレーム画像メモリ１３に格納した画像について、後述の手順で特徴量を抽出する。１５は特徴量ラベル列化部であり、画像特徴量抽出部１４によって得られた特徴量に基づいてラベル列を生成する。１６はパターンマッチングによるシーンチェンジ検出部であり、ＲＡＭ１０３の所定の領域に格納されているＮ個の隣接あるいは近傍のフレーム画像のラベル列群との類似度を算出し、その値を閾値処理することによりシーンチェンジフレームを検出する。そして、ＦＩＦＯ(First In First Out)の原理でＲＡＭ１０３に格納した最も古いフレーム画像のラベル列を破棄し、現在のフレーム画像のラベル列を格納する。
【００１８】
１７はシーンチェンジ情報蓄積部であり、動画像入力部１２等によって得られた動画像データのどのフレームがシーンチェンジ点であるかを記憶・蓄積する。
【００１９】
図３は、シーンチェンジ情報蓄積部１７におけるシーンチェンジ情報の格納状態を説明する図である。
【００２０】
動画像データ中の各画像フレームにはその動画中におけるユニークな画像フレームＩＤが付与され、シーンチェンジ情報蓄積部１７にはシーンチェンジ情報１１２が新しいシーンの開始する画像フレームのＩＤの形で保持される。
【００２１】
１８は動画像管理データベース（以下、動画像管理ＤＢ）であり、図８で示されるデータ形態で、動画像データ１１３とシーンチェンジ情報蓄積部１７に格納されたシーンチェンジ情報１１２を対応づけて管理する。
【００２２】
シーンチェンジ検出処理に関してさらに説明を行なう。
【００２３】
まず、動画像から各フレーム画像を順に取り出し、これらのフレーム画像を、図５のように、複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与する。次に、付与されたラベルを所定のブロック順序に基づいて並べることによりラベル列を生成し、生成されたラベル列を過去Ｎフレーム分メモリに記憶する。この時に、メモリに記憶された過去のフレームのラベル列と生成された現在のフレームのラベル列の比較を行ない、比較に基づいてシーンチェンジの有無を判定する。
【００２４】
＜本実施の形態の画像処理装置の動作例＞
以上のような構成を備えた本実施の形態の画像処理装置の動作例を以下に説明する。なお、以下の例では、色に着目した画像特徴量として、赤（Ｒ）、緑（Ｇ）、青（Ｂ）の３色を採用し、３次元の色空間での処理を用いて説明する。
【００２５】
（フレームからラベル列を得る処理）
まず、動画像から１つのフレーム画像を取り出し、このフレーム画像を複数のブロックに分割し、各ブロックについて取得された特徴量に応じてラベルを付与し、付与されたラベルを所定のブロック順序に基づいて並べることによりラベル列を生成する処理を説明する。
【００２６】
図４は、本実施の形態によるフレームからラベル列を得る処理の手順を表すフローチャートである。
【００２７】
ユーザーインターフェース部１１を介しての指示により、シーンチェンジ検出を行なう動画ファイルを指示すると、ステップＳ１０の判定により、残りのフレーム画像が存在するだけステップＳ１１からステップＳ１８までの処理が繰り返される。
【００２８】
まず、ステップＳ１１において、動画ファイルをシークし、１フレームの画像を読み出しフレーム画像メモリ１３に保持する。次に、ステップＳ１２において、この画像を複数のブロックに分割する。本実施の形態では、画像を縦横の複数ブロックに分割する。図５は、本実施の形態による画像のブロック分割例を示す図である。同図に示されるように、本実施の形態では、３×３の計９個に画像を分割するものとする。次に、ステップＳ１３において、分割された各ブロックの特徴量を算出し、得られた特徴量を次の手順でラベル化する。
【００２９】
図６は、本実施の形態による多次元特徴量空間を説明する図である。
【００３０】
図６に示すように、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロック（色ブロック）、即ちセル（色セル）に分割し、夫々のセル（色セル）に対して通し番号でユニークなラベルを付与する。ここで、多次元特徴量空間（ＲＧＢカラー空間）を複数のブロックに分けたのは微妙な特徴量（色）の違いを吸収するためである。
【００３１】
ステップＳ１３では、ステップＳ１２で得られた各分割ブロックに対して、定められた画像特徴量計算処理を行い、上記多次元特徴量空間上のどのセルに属するかを求め、対応するラベルを求める。この処理を全てのブロックに対して行う。すなわち、本例の画像特徴量計算処理では、分割画像ブロックに対して、全ての画素がどの色セルに属するかの計算処理を行い、もっとも頻度の多い色セルのラベルをその分割画像ブロックのパラメータラベル（カラーラベル）として決定し、この処理を全てのブロックに対して行う。
【００３２】
以上のようにして各ブロックに対してパラメータラベルが付与されると、ステップＳ１４において、各ブロックに付与されたパラメータラベルを所定のブロック順序で並べることにより、パラメータラベル列（以下、ラベル列という）が生成される。
【００３３】
図７は、ラベル列を生成する際のブロック順序例を説明する図である。同図の分割画像ブロックの升にある数字の小さい順に上記のパラメータラベルを並べ、ラベル列を作る。
【００３４】
なお、本実施の形態に適用可能なスキャンの方法としては、例えば、
・水平方向のスキャン（例えば、左から右へのスキャンを上から下へ行う：図７の（ａ）、左から右へのスキャンを下から上へ行う：図７の（ｃ）、右から左へのスキャンを上から下へ行う：図７の（ｂ）、右から左へのスキャンを下から上へ行う：図７の（ｄ）、等のスキャン方法が考えられる）と、
・垂直方向のスキャン（例えば、図示しないが、上から下へのスキャンを左から右へ行う、上から下へのスキャンを右から左へ行う、下から上へのスキャンを左から右へ行う、下から上へのスキャンを右から左へ行う、等のスキャン方法が考えられる）とがある。しかしながら、これに限定されるものではない。
【００３５】
本実施の形態では、以下の条件を満足するスキャン方法を採用する。
（１）ラベル列同士の時系列的な比較であるので、この順序に逆転が生じることは好ましくない。よって、すべての画像を所定のスキャン方法でスキャンしてラベル列化を行う必要がある。
（２）位置の近いブロックはラベル列中においても近くに位置することが望ましい。
（３）注目する物体に引っ掛かるブロックのラベルが出来る限り早く現れ、且つ長く続くことがマッチングを行いやすくする。
（４）物体が動いたり、アングルが変わったりしても、ラベルの並びが極端に変わらないようにする。
【００３６】
本実施の形態では、図７の（ａ）のように左から右方向への水平スキャンを上から下へ行うスキャンを採用する。
【００３７】
（シーンチェンジを検出する処理）
以上のようにして得たラベル列が過去Ｎフレーム分だけメモリ上に蓄積してあり、続いてステップＳ１５において、過去のＮフレームと現在のフレームのラベル列を比較し、シーンチェンジを検出する。ここで、Ｎは最小値を２とする。
【００３８】
以下、全く違うシーンが結合されたもののシーンチェンジを検出する方法を例に、本実施の形態のラベル列からシーンチェンジを検出する一例を、ステップＳ１５を更に詳細に示した図９のフローチャートを用いて説明する。尚、全く違うシーンが結合されたものにおいても、編集におけるコマ落ち等の不備や、カメラのフラッシュ等のように１コマだけ大きく明るさの変わるものがあり、これに対して誤動作（シーンチェンジの過剰検出）を行なわないようにすることが大切である。
【００３９】
まず、ステップＳ２０において現在のフレーム画像から得たラベル列と直前のフレーム画像から得たラベル列の類似度を後で述べる方法で求め、ステップＳ２１においてこの類似度と閾値とを比較し、類似度が閾値より大きければステップＳ２５においてシーンチェンジ無しというステータスを返し、リターンする。補足をするとこの後は、図４に戻ってステップＳ１６からステップ１８に進んで、現在のフレーム画像のラベル列をＲＡＭに記憶したのち、ステップＳ１０に戻り続いてステップＳ１１以下における新しいフレーム画像を読み込み込む処理に戻る。
【００４０】
ステップＳ２１において類似度が閾値以下であれば、ステップＳ２２において、先に求めＲＡＭ上に記憶してある現在の２つ前のフレーム画像から得たラベル列と現在のフレーム画像から得たラベル列とを比較し、ステップＳ２３においてその類似度がやはり閾値以下であれば、ステップＳ２４においてシーンチェンジありというステータスを返す。もし、ステップＳ２３においてその類似度が閾値より大きければ、編集における不備や、カメラのフラッシュ等のように１コマだけ大きく明るさの変わったものとみなし、ステップＳ２５においてシーンチェンジ無しというステータスを返す。
【００４１】
（類似度を算出する処理）
次に、フレーム画像間の類似度の算出、即ちラベル列同士の類似比較（類似度の算出）を行う方法について詳細に述べる。なお、以下では、ステップＳ１４で取得したラベル行列を検索元フレーム画像の検索元ラベル行列と称する。
【００４２】
ラベル間のパターンマッチングの際に隣接するセル同士ではペナルティー（距離の）を小さくし、遠いものには大きなペナルティーを与えるために、図１０に示すようなラベル間でのペナルティーマトリックスを導入する。ステップＳ１５内のステップＳ２０やＳ２２では、このペナルティーマトリックスを考慮してラベル行列同士を比較するが、その際に以下に説明する２次元的なＤＰマッチング（以下、２次元ＤＰマッチングという）を使用する。
【００４３】
図１１は、本実施の形態による類似度算出処理を説明する図である。
【００４４】
上述のステップＳ１４において取得された検索元ラベル行列は、そのスキャン方法に従って図１１の（ｂ）のように並べることができる。また、ＲＡＭに格納された過去Ｎフレーム分のフレーム画像のラベル行列のうちの１つを比較先フレーム画像の比較先ラベル行列とすると、そのラベル行列は図１１の（ａ）のように並べることができる。
【００４５】
まず、比較先ラベル行列の第１行目のラベル列「ａｂｃ」と、検索元ラベル行列の第１から第３行目のラベル列（「１２３」、「４５６」、「７８９」）のそれぞれとの距離をＤＰマッチングによって求め、その距離が最少となるラベル列の検索元ラベル行列における行番号を類似ライン行列（図１１の（ｃ））の該当する位置に記憶する。また、得られた最小距離が所定の閾値よりも大きい場合には、どの行とも類似していないと判断し、類似ライン行列の該当する位置に「！」を記憶する。ＤＰマッチングの性質により、たとえば画像のアングルが水平方向に多少変わっていたとしても、上記処理により類似する行（ライン）を検出可能である。以上の処理を、類似比較先画像の全ての行（「ｄｅｆ」、「ｇｈｉ」）について行うことで、図１１の（ｃ）のような列方向の類似ライン行列が得られる。
【００４６】
図１１の（ｃ）では、「ａｂｃ」に類似した行が検索元ラベル行列に存在せず、「ｄｅｆ」に類似した行が検索元ラベル行列の第１行目、「ｇｈｉ」に類似した行が検索元ラベル行列の第２行目であったことを示している。以上のようにして得られた類似ライン行列と標準ライン行列（検索元フレーム画像の行の並びであり、本例では「１２３」となる）との類似度を、更にＤＰマッチングを用いて算出し、これを当該検索元フレーム画像と当該比較先フレーム画像との類似度として出力する。
【００４７】
なお、ＤＰマッチングでは、周知のように、比較するラベルシーケンスが最も類似距離が小さくなるように、比較するラベルシーケンスを伸縮（比較する相手を次に進めないで我慢する）させて比較するという処理を行う。また、何処まで伸縮（我慢）できるかを制約条件（整合窓の幅）で与えることも可能である。
【００４８】
図１２は、本実施の形態による２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。上記図１１を参照して説明した処理を、図１２のフローチャートを参照して更に詳細に説明する。尚、このフローチャートの処理がステップＳ２０、Ｓ２２でそれぞれ異なる類似比較先画像に基づいて実行される。
【００４９】
まず、ステップＳ１０１において、比較先フレーム画像の行番号を表す変数ｉと、検索元フレーム画像の行番号を表す変数ｊを１に初期化し、ともに第１行目を示すように設定する。次に、ステップＳ１０２において、比較先フレーム画像の第ｉ行目のラベル列を取得する。例えば図１１の場合、ｉ＝１であれば「ａｂｃ」が取得される。そして、ステップＳ１０３において、検索元フレーム画像の第ｊ行目のラベル列を取得する。例えば、図１１において、ｊ＝１であれば、「１２３」が取得される。
【００５０】
次にステップＳ１０４では、上記ステップＳ１０２、Ｓ１０３で得られた２つのラベル列間の距離を、図１０で説明した色セルのペナルティー・マトリクスを用いながら、ＤＰマッチングによって求める。そして、ステップＳ１０５において、ステップＳ１０４で得た距離が第ｉ行目に関してそれまでに得られた距離の最小値であれば、当該行番号（ｊ）をライン行列要素ＬＩＮＥ［ｉ］に記憶する。
【００５１】
以上のステップＳ１０３からステップＳ１０５の処理を、類似検索元画像の全ての行について行う（ステップＳ１０６、Ｓ１０７）。以上のようにして、比較先フレーム画像の第ｉ行目のラベル列に対して、検索元フレーム画像に含まれる行のうち最も距離の近い行の番号がＬＩＮＥ［ｉ］に格納されることになる。
【００５２】
そして、ステップＳ１０８において、上記処理で得られたＬＩＮＥ［ｉ］と所定の閾値（Ｔｈｒｅｓｈ）とを比較する。そして、ＬＩＮＥ［ｉ］がＴｈｒｅｓｈ以上であればステップＳ１０９へ進み、いずれの行とも類似していないことを表す「！」をＬＩＮＥ［ｉ］に格納する。
【００５３】
以上説明したステップＳ１０２からＳ１０８の処理を比較先フレーム画像の全ての行について実行する（ステップＳ１１０、Ｓ１１１）ことにより、ＬＩＮＥ［１］のＬＩＮＥ［ｉｍａｘ］が得られるので、これを類似ライン行列ＬＩＮＥ［ｉ］として出力する。
【００５４】
次に、ステップＳ１１３において、標準ライン行列［１，２，…，ｉｍａｘ］と類似ライン行列ＬＩＮＥ［１，２，…，ｉｍａｘ］とのＤＰマッチングを行い、両者の距離を算出する。なお、ここで、標準ライン行列とは、１から始まり、列方向に１ずつ増加する行列である。
【００５５】
ここで、標準ライン行列と類似ライン行列間とのＤＰマッチングにおいて用いられるペナルティーについて説明する。列方向の類似ライン行列と標準ライン行列とのＤＰマッチングのペナルティーの設定として動的なペナルティーを提案する。動的なペナルティーとは、動的にライン番号間のペナルティーを設定するものであり、画像によってライン番号間のペナルティーは変化する。本実施の形態では、類似検索元画像の自分自身の横（行）方向のラベル行列の距離を求め、これに基づいて各行間のペナルティーを求める。
【００５６】
図１３は、本実施の形態による動的なペナルティー値の設定手順を示すフローチャートである。
【００５７】
ステップＳ１２１において、変数ｉを１に、変数ｊを２にそれぞれセットする。次に、ステップＳ１２２において、検索元フレーム画像の第ｉ行目のラベル列を取得し、ステップＳ１２３において、検索元フレーム画像の第ｊ行目のラベル列を取得する。そして、ステップＳ１２４において、検索元フレーム画像の第ｉ行目のラベル列と第ｊ行目のラベル列とについて、色ペナルティーマトリクスを用いてＤＰマッチングを行い、距離を獲得する。ステップＳ１２５では、ステップＳ１２４で得たＤＰマッチングの距離を、検索元フレーム画像のｉ行目のラベル列とｊ行目のラベル列間のペナルティーとしてＬＩＮＥ［i］［j］に記憶すると共に、検索元フレーム画像のｊ行目のラベル列とｉ行目のラベル列間のペナルティーとしてＬＩＮＥ［j］［i］に記憶する。
【００５８】
ステップＳ１２６によって、変数ｊの値がｊｍａｘとなるまで、ステップＳ１２３、Ｓ１２５の処理が繰返される。この結果、第ｉ行目のラベル列について、ｉ＋１からｊｍａｘ行目の各ラベル列との間のペナルティー値が決定される。そして、ステップＳ１２８、Ｓ１２９、Ｓ１３０により、ステップＳ１２３、Ｓ１２６の処理を変数ｉの値が（ｉｍａｘ−１）となるまで繰返される。この結果、ＬＩＮＥ［i］［j］には、ｉ＝ｊの対角成分を除く全てに、上記処理で決定されたペナルティー値が記憶されることになる。
【００５９】
次にステップＳ１３１では、上記処理で決定されていないＬＩＮＥ［i］［j］の対角成分のペナルティーを決定する。この部分はｉ＝ｊであり、同一のラベル列であるから、その距離は０であり、従ってペナルティー０が記憶される。また、ステップＳ１３２では、「！」に関してペナルティーを決定する。すなわち、「！」に対するペナルティーは、ＬＩＮＥ［i］［j］の全てのペナルティー値の中で、最大のペナルティー値よりもある程度大きな値を設定する。ただし、このペナルティー値を極端に大きくすると、曖昧にヒットする性質が損なわれてしまう。
【００６０】
以上のようにして検索元フレーム画像に関して計算されたラベル列間のペナルティーを用いて、上記ステップＳ１１３におけるＤＰマッチングを行い、検索元フレーム画像と比較先フレーム画像との類似度を獲得する。
【００６１】
以上説明したマッチング処理は次のような特徴を有する。もし、図１１の（ａ）と（ｂ）が極めて類似していれば、類似ライン行列は「１２３」となり、その距離は０となる。また、類似ライン行列が「！１２」や「２１２」であれば、検索元フレーム画像に対して比較先フレーム画像は下方向へずれたものである可能性があるし、類似ライン行列が「２３！」や「２３３」であれば検索元フレーム画像に対して比較先フレーム画像が上方向へずれたものである可能性がある。また、類似ライン行列が「１３！」や「！１３」であれば、検索元フレーム画像に対して比較先フレーム画像が縮小したものである可能性がある。同様に、検索元フレーム画像が比較先フレーム画像を拡大したようなものである場合も検出可能である。
【００６２】
上述のステップＳ１１３で説明したように、類似ライン行列と標準ライン行列との間でＤＰマッチングを行うことにより、垂直方向へのずれが効果的に吸収される。このため、上述したような、上方向や下方向へのずれや拡大、縮小等に起因する検索元フレーム画像と比較先フレーム画像との相違が効果的に吸収され、動画のフレーム画像間の良好な類似判定を行うことが可能となる。
【００６３】
すなわち、本実施の形態の２次元ＤＰマッチングは、ラベル行列の各ラベル列における前後の曖昧さを許容するマッチングであり、画像の位置ずれの影響を吸収する性質を有する。また、アングルの違い等により物体の位置が変わり、ブロックによって切りとられる物体の位置が変わることにより、ブロックの色合いも微妙に異なることが予想されるが、この違いは上述のペナルティーマトリクスにより吸収されることになる。このように、本実施の形態の２次元ＤＰマッチングによる曖昧さを許容するマッチングと、ペナルティーマトリクスによる特徴量の曖昧さの許容との相乗効果によって、上下左右や拡大、縮小のずれに対しても影響の少ないマッチングを可能としている。
【００６４】
ここで動的なペナルティーの利点の他の例を挙げると、例えば、一面麦畑の検索元フレーム画像があったとした場合、どのラインも似たようなラベル列となることが考えられる。一方、比較先フレーム画像にも一面麦畑の画像があったとした場合に、この画像の類似ライン行列には全て最初のライン番号１が入り、「１１１」となってしまう可能性がある。この場合、類似検索元画像のどのラインも似たような画像となっており、ライン番号間のペナルティーが極めて小さくなければ低い距離でのヒットはしない。しかしながら、動的なペナルティーを用いた場合は、ライン番号間のペナルティーが低くなり、類似度の高い結果を得ることができる。
【００６５】
なお、上記実施の形態では、水平方向のブロック並びに対応するラベル列を用いて類似ライン行列を得たが、垂直方向のブロック並びに対応するラベル列を用いて類似ライン行列を得るようにすることも、上記と同様の手法で実現可能である。又、水平及び垂直方向の両方を組み合わせてもよい。
【００６６】
また、上記実施の形態では画像特徴量として色情報を選んだが、本発明はこれに限られるものではなく、その他の画像パラメータを画像分割ブロックごとに求めることで実施することも可能である。
【００６７】
また、検索元フレーム画像と比較先フレーム画像を比較する際に曖昧度を指定することにより、ＤＰマッチングにおけるいわゆる整合窓の幅を変更することにより、比較の暖味度を所望に設定可能とすることもできる。
【００６８】
図１４はＤＰマッチングにおける整合窓を説明する図である。図１４において直線ＡはＪ＝Ｉ＋ｒで表され、直線ＢはＪ＝Ｉ−ｒで表される。整合窓の幅はｒの値を変更することで行える。したがって、曖昧度を可変することにより、このｒの値が変更されるように構成すれば、所望の曖昧度（整合窓の幅）で類似度演算を行えるようになり、例えば動きが極めて激しい動画におけるシーンチェンジ検出や、手ぶれの激しいムービーなどのシーンチェンジ検出にも効果的である。むろんキーボード１０４から、ユーザが手動でｒの値を変化させシーンチェンジの感度を変化させる事も可能であるし、過度にシーンチェンジを検出する場合には自動的にｒの値を増加させたり、逆にシーンチェンジが少なすぎる場合にはｒの値を自動的に小さくすることも考えられる。
【００６９】
また、上記実施の形態のような２次元ＤＰマッチングにおいては、水平方向のＤＰマッチングにおける整合窓の幅と、垂直方向のＤＰマッチングにおける整合窓の幅とを別々に設定できるようにしてもよい。或いは、両整合窓が異なる変化率で変化するように構成してもよい。このようにすれば、類似比較演算に際してよりきめ細かい曖昧さの設定を行えるようになる。例えば、図７の（ａ）で示されたようなブロック順序を用いた場合において、検索元の画像中における注目物体の横方向への移動を許容したいような場合には、横方向への暖味度を大きくするために水平方向のＤＰマッチングにおける整合窓の幅をより大きくすればよい。
【００７０】
再び図４のフローチャートの説明に戻るが、ステップＳ１５において、シーンチェンジを検出したかどうかをステップＳ１６において判断を行い、シーンチェンジを検出していればステップＳ１７の処理でシーンチェンジ情報蓄積部へシーンチェンジ情報を追記する。そして最後にステップＳ１８で、Ｎ個過去のフレーム画像のラベル列を破棄し、現在のフレーム画像のラベル列をＲＡＭに格納する。そしてステップＳ１０の処理に戻り、残りのフレーム画像が存在するだけ上記処理を繰り返す。
【００７１】
以上説明したように、特徴量群（特徴量空間を分割して得られる特徴量のグループ）を１つのシンボルで表現し（すなわちラベル化し）、ラベル同士の類似度に基づく距離を、上述の２次元ＤＰマッチングとペナルティーマトリクスによって与える。このため、２つの画像のブロック間の距離の計算量を大幅に減少させることができるとともに、類似した特徴量が同じラベルで表されることになるので、２つの画像の類似度計算を良好に行うことができる。
【００７２】
また、（１）ペナルティーマトリクスによるラベル同士の距離概念を導入し、（２）比較するラベル位置を前後曖昧に移動させることが出来て、トータルの距離が最小（類以度が最大）となるようなラベル行列の比較を実現する上記２次元ＤＰマッチングを導入したことにより、隣接あるいは近傍の画像フレームに関してはカメラのパンなどによる画像のアングルの変化、被写体の位置の変化や変形、あるいは光源等の撮影条件が変わったりすることによって生じる、色のある程度の違い等を吸収するなど、動画像の或程度の連続した変化を吸収しつつ、真に連続性の無いフレームの出現で顕著にフレーム間類似度が低下するフレーム間パターンマッチャーの実現が可能となる。
【００７３】
なお、本発明は、例えばホストコンピュータ，インタフェイス機器，記憶媒体などの複数の機器から構成されるシステムに適用しても、一つの機器からなる装置（例えば、ビデオ編集装置など）に適用してもよい。
【００７４】
また、本発明の目的は、前述した実施の形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、達成されることは言うまでもない。この場合、記憶媒体から読出されたプログラムコード自体が前述した実施の形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００７５】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピーデイスク，ハードデイスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリカード，ＲＯＭなどを用いることができる。
【００７６】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【００７７】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【００７８】
本発明を上記記憶媒体に適用する場合、その記憶媒体には、先に説明した（図４、図９、図１２、図１３等に示す）フローチャートに対応するプログラムコードと含むプログラムが格納されることになる。
【００７９】
【発明の効果】
以上説明したように、本発明によれば、カメラのパンなどによる画像のアングルの変化、被写体の位置の変化や変形、あるいは光源等の撮影条件が変わったりすることによって生じる色のある程度の違い等を吸収するなど、動画像の或程度の連続した変化を吸収しつつ、真に連続性の無いフレームの出現で顕著にフレーム間類似度が低下するフレーム間パターンマッチャーの実現によるシーンチェンジ検出が可能となる。
【図面の簡単な説明】
【図１】本実施の形態によるシーンチェンジ検出機能を有する画像処理装置の構成例を示すブロック図である。
【図２】本実施の形態によるシーンチェンジ検出機能の構成例を示すブロック図である。
【図３】本実施の形態によるシーンチェンジ情報蓄管理ＤＢにおけるシーンチェンジ情報の格納状態を説明する図である。
【図４】本実施の形態によるシーンチェンジ情報生成処理の手順を表すフローチャートである。
【図５】本実施の形態による画像のブロック分割例を示す図である。
【図６】本実施の形態による多次元特徴量空間を説明する図である。
【図７】本実施の形態によるラベル列を生成する際のブロック順序例を説明する図である。
【図８】本実施の形態による動画像管理データベースによる動画像データファイル情報の格納形態を説明する図である。
【図９】ｌ本実施の形態による図４におけるシーンチェンジ検出処理の詳細な手順を説明するフローチャートである。
【図１０】本実施の形態によるラベル列を比較し類似度を求める際に用いるラベル間のペナルティーマトリックスの一例を示す図である。
【図１１】本実施の形態による類似度算出処理を説明する図である。
【図１２】本実施の形態による２次元ＤＰマッチングを採用した類似度算出の手順を説明するフローチャートである。
【図１３】本実施の形態による動的なペナルティー値の設定手順を示すフローチャートである。
【図１４】本実施の形態によるＤＰマッチングにおける整合窓の調整を説明する図である。
【図１】
0004146955.tif 000002
【図２】
0004146955.tif 000003
【図３】
0004146955.tif 000004
【図４】
0004146955.tif 000005
【図５】
0004146955.tif 000006
【図６】
0004146955.tif 000007
【図７】
0004146955.tif 000008
【図８】
0004146955.tif 000009
【図９】
0004146955.tif 000010
【図１０】
0004146955.tif 000011
【図１１】
0004146955.tif 000012
【図１２】
0004146955.tif 000013
【図１３】
0004146955.tif 000014
【図１４】
0004146955.tif 000015