(57)【特許請求の範囲】
【請求項１】
映像を構成する複数の画像のうち、１つ以上の画像にインデックスを付与する映像シーン分類装置であって、
サンプリングによって前記映像から複数の画像を取得する映像サンプリング手段と、
取得された前記画像毎に画像処理を施す範囲を決定する処理範囲決定手段と、
前記複数の画像について、前記処理範囲決定手段で決定された範囲に画像処理を施し、画像上の特徴を表す分類指標に基づいて複数のクラスタに分類する画像分類手段と、
分類された前記複数のクラスタの中から少なくとも１つのクラスタを選択するクラスタ選択手段と、
分類された前記クラスタに係る前記分類指標、又は前記映像の番組内容情報に基づいて、インデキシングルールを選択するインデキシングルール選択手段と、
前記選択されたクラスタを構成する画像のうち、少なくとも１つの画像に対して、選択された前記インデキシングルールを用いてインデックスを付与するインデックス生成手段とを備え、
前記インデキシングルール選択手段は、前記番組内容情報に基づいて、
（１）選択されたクラスタに含まれる少なくとも１つ以上の画像にインデックスを付与する、
（２）選択されたクラスタに含まれる少なくとも１つ以上の画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックスを付与する、及び、
（３）所定のクラスタに含まれる映像ブロックのうち、他の所定のクラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックスを付与する、のいずれかを選択する
ことを特徴とする映像シーン分類装置。
【請求項２】
前記インデキシングルール選択手段は、さらに、前記番組内容情報に基づいて、
（１）選択されたクラスタに含まれる全ての画像にインデックスを付与する、
（２）選択されたクラスタに含まれる全ての画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックスを付与する、及び、
（３）所定のクラスタに含まれる映像ブロックのうち、他の所定のクラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックスを付与する、の何れかを選択する
ことを特徴とする請求項１記載の映像シーン分類装置。
【請求項３】
前記クラスタ選択手段は、
選択するクラスタの数を決定するクラスタ数決定部と、
選択するクラスタの種類を決定するクラスタ種決定部の少なくとも一つを備え、
前記クラスタ数決定部は、
（１）前記番組内容情報もしくは画像情報から映像のジャンルを特定し、特定されたジャンルに対応した所定の数を、前記選択するクラスタの数として決定する、及び
（２）前記番組内容情報もしくは画像情報から映像のジャンルを特定し、特定されたジャンルと前記画像分類手段における分類結果によって求まる所定の数を、前記選択するクラスタの数として決定する、
とする何れかの手法に基づいて前記クラスタ数を決定し、
前記クラスタ種決定部は、
（１）クラスタの映像ブロック数が最大のクラスタから所定個数を選択する、
（２）クラスタの映像ブロックの出現時間平均値が所定時刻に近いクラスタから所定個数を選択する、
（３）クラスタの映像ブロックの出現時間分布が所定時間帯に近いクラスタから所定個数を選択する、及び
（４）クラスタの映像ブロックの出現時間分布が所定時間帯に含まれていないクラスタから所定個数を選択する、
とする何れかの手法に基づいて前記クラスタの種類を決定する
ことを特徴とする請求項１記載の映像シーン分類装置。
【請求項４】
前記処理範囲決定手段は、
前記映像に係る前記画像の輝度情報若しくは色情報を用いて前記画像処理を施す範囲を決定する、又は前記番組内容情報を用いて、
（１）前記画像処理を施す範囲の決定に際して、位置に関する重み付けを行う、及び
（２）キャプション若しくはテロップが出現する位置を推定し、位置に関する重み付けを行う、
とする何れかの手法に基づいて前記画像処理を施す範囲を決定する
ことを特徴とする請求項１記載の映像シーン分類装置。
【請求項５】
前記処理範囲決定手段は、
前記番組内容情報が、野球番組に関する情報を意味するときに、前記重み付けを画像中心部に設定する、又は前記キャプションの位置推定をスコア表示および選手紹介の表示位置を用いて行う
ことを特徴とする請求項４記載の映像シーン分類装置。
【請求項６】
前記画像分類手段は、
（１）前記画像処理を施す範囲の大きさ若しくはその位置のいずれかを用いて、又は
（２）前記画像処理を施す範囲の内部の画像情報、前記画像処理を施す範囲の所定の周辺部の画像情報、若しくは前記画像処理を施す範囲の外部の画像情報のいずれかを用いて、前記クラスタの分類を行い、当該分類において、前記画像の色情報もしくは輝度情報のヒストグラムを用いる
ことを特徴とする請求項１記載の映像シーン分類装置。
【請求項７】
前記画像分類手段は、
前記画像処理を施す範囲の位置の各前記画像間での差分量によって第１の画像の分類を行い、
前記第１の画像の分類における分類結果から、映像ブロック数が最も多い所定数のクラスタに含まれる映像ブロックを用い、前記画像処理を施す範囲の周辺部の色情報若しくは輝度情報のヒストグラムによって第２の画像の分類を行う
ことを特徴とする請求項６記載の映像シーン分類装置。
【請求項８】
映像シーン分類装置が、映像を構成する複数の画像のうち、１つ以上の画像にインデックスを付与する映像シーン分類方法であって、
前記映像シーン分類装置は、映像サンプリング手段と、処理範囲決定手段と、画像分類手段と、クラスタ選択手段、インデキシングルール選択手段と、インデックス生成手段とを備え、
前記映像シーン分類方法は、
映像サンプリング手段が、サンプリングによって前記映像から複数の画像を取得する映像サンプリングステップと、
処理範囲決定手段が、取得された前記画像毎に画像処理を施す範囲を決定する処理範囲決定ステップと、
画像分類手段が、前記複数の画像について、前記処理範囲決定ステップで決定された範囲に画像処理を施し、画像上の特徴を表す分類指標に基づいて複数のクラスタに分類する画像分類ステップと、
クラスタ選択手段が、分類された前記複数のクラスタの中から少なくとも１つのクラスタを選択するクラスタ選択ステップと、
インデキシングルール選択手段が、分類された前記クラスタに係る前記分類指標、又は前記映像の番組内容情報に基づいて、インデキシングルールを選択するインデキシングルール選択ステップと、
インデックス生成手段が、前記選択されたクラスタを構成する画像のうち、少なくとも１つの画像に対して、選択された前記インデキシングルールを用いてインデックスを付与するインデックス生成ステップとを含み、
前記インデキシングルール選択ステップでは、インデキシングルール選択手段が、前記番組内容情報に基づいて、
（１）選択されたクラスタに含まれる少なくとも１つ以上の画像にインデックスを付与する、
（２）選択されたクラスタに含まれる少なくとも１つ以上の画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックスを付与する、及び
（３）所定のクラスタに含まれる映像ブロックのうち、他の所定のクラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックスを付与する、のいずれかを選択する
ことを特徴とする映像シーン分類方法。
【請求項９】
映像を構成する複数の画像のうち、１つ以上の画像にインデックスを付与する映像シーン分類装置に用いる、コンピュータに実行させるためのプログラムであって、
前記プログラムは、
サンプリングによって前記映像から複数の画像を取得する映像サンプリングステップと、
取得された前記画像毎に画像処理を施す範囲を決定する処理範囲決定ステップと、
前記複数の画像について、前記処理範囲決定ステップで決定された範囲に画像処理を施し、画像上の特徴を表す分類指標に基づいて複数のクラスタに分類する画像分類ステップと、
分類された前記複数のクラスタの中から少なくとも１つのクラスタを選択するクラスタ選択ステップと、
分類された前記クラスタに係る前記分類指標、又は前記映像の番組内容情報に基づいて、インデキシングルールを選択するインデキシングルール選択ステップと、
前記選択されたクラスタを構成する画像のうち、少なくとも１つの画像に対して、選択された前記インデキシングルールを用いてインデックスを付与するインデックス生成ステップとを含み、
前記インデキシングルール選択ステップでは、前記番組内容情報に基づいて、
（１）選択されたクラスタに含まれる少なくとも１つ以上の画像にインデックスを付与する、
（２）選択されたクラスタに含まれる少なくとも１つ以上の画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックスを付与する、及び
（３）所定のクラスタに含まれる映像ブロックのうち、他の所定のクラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックスを付与する、のいずれかを選択する
ことを特徴とするプログラム。
【請求項１０】
映像を構成する複数の画像のうち、１つ以上の画像にインデックスを付与するためのプログラムが記録された記録媒体であって、
前記プログラムは、
サンプリングによって前記映像から複数の画像を取得する映像サンプリングステップと、
取得された前記画像毎に画像処理を施す範囲を決定する処理範囲決定ステップと、
前記複数の画像について、前記処理範囲決定ステップで決定された範囲に画像処理を施し、画像上の特徴を表す分類指標に基づいて複数のクラスタに分類する画像分類ステップと、
分類された前記複数のクラスタの中から少なくとも１つのクラスタを選択するクラスタ選択ステップと、
分類された前記クラスタに係る前記分類指標、又は前記映像の番組内容情報に基づいて、インデキシングルールを選択するインデキシングルール選択ステップと、
前記選択されたクラスタを構成する画像のうち、少なくとも１つの画像に対して、選択された前記インデキシングルールを用いてインデックスを付与するインデックス生成ステップとを含み、
前記インデキシングルール選択ステップでは、前記番組内容情報に基づいて、
（１）選択されたクラスタに含まれる少なくとも１つ以上の画像にインデックスを付与する、
（２）選択されたクラスタに含まれる少なくとも１つ以上の画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックスを付与する、及び
（３）所定のクラスタに含まれる映像ブロックのうち、他の所定のクラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックスを付与する、のいずれかを選択する
ことを特徴とするプログラムが記録された、コンピュータが読み取り可能な記録媒体。
【請求項１１】
映像を構成する複数の画像のうち、１つ以上の画像にインデックスを付与する集積回路であって、
サンプリングによって前記映像から複数の画像を取得する映像サンプリング手段と、
取得された前記画像毎に画像処理を施す範囲を決定する処理範囲決定手段と、
前記複数の画像について、前記処理範囲決定手段で決定された範囲に画像処理を施し、画像上の特徴を表す分類指標に基づいて複数のクラスタに分類する画像分類手段と、
分類された前記複数のクラスタの中から少なくとも１つのクラスタを選択するクラスタ選択手段と、
分類された前記クラスタに係る前記分類指標、又は前記映像の番組内容情報に基づいて、インデキシングルールを選択するインデキシングルール選択手段と、
前記選択されたクラスタを構成する画像のうち、少なくとも１つの画像に対して、選択された前記インデキシングルールを用いてインデックスを付与するインデックス生成手段とを備え、
前記インデキシングルール選択手段は、前記番組内容情報に基づいて、
（１）選択されたクラスタに含まれる少なくとも１つ以上の画像にインデックスを付与する、
（２）選択されたクラスタに含まれる少なくとも１つ以上の画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックスを付与する、及び
（３）所定のクラスタに含まれる映像ブロックのうち、他の所定のクラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックスを付与する、のいずれかを選択する
ことを特徴とする集積回路。
【請求項１２】
サーバ装置とクライアント装置とを有するサーバ−クライアントシステムであって、
前記サーバ装置は、
サンプリングによって前記映像から複数の画像を取得する映像サンプリング手段と、
取得された前記画像毎に画像処理を施す範囲を決定する処理範囲決定手段と、
前記複数の画像について、前記処理範囲決定手段で決定された範囲に画像処理を施し、画像上の特徴を表す分類指標に基づいて複数のクラスタに分類する画像分類手段と、
分類された前記複数のクラスタの中から少なくとも１つのクラスタを選択するクラスタ選択手段と、
分類された前記クラスタに係る前記分類指標、又は前記映像の番組内容情報に基づいて、インデキシングルールを選択するインデキシングルール選択手段と、
前記選択されたクラスタを構成する画像のうち、少なくとも１つの画像に対して、選択された前記インデキシングルールを用いてインデックスを付与するインデックス生成手段とを備え、
前記インデキシングルール選択手段は、前記番組内容情報に基づいて、
（１）選択されたクラスタに含まれる少なくとも１つ以上の画像にインデックスを付与する、
（２）選択されたクラスタに含まれる少なくとも１つ以上の画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックスを付与する、及び
（３）所定のクラスタに含まれる映像ブロックのうち、他の所定のクラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックスを付与する、のいずれかを選択し、
前記クライアント装置は、
前記サーバ装置から画像データを受信する受信手段と、
受信した前記画像データに係るインデックスに基づいて、受信した前記画像データに係る画像の再生時に頭出し、又はスキップを伴う再生を行う再生手段とを備える
ことを特徴とするサーバ−クライアントシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像コンテンツを対象としたインデックスの自動生成技術に関し、特に放送映像コンテンツにチャプタ（インデックス）を自動的に付加するチャプタリング技術に関する。
【背景技術】
【０００２】
近年、デジタルコンテンツの撮像や蓄積に関する環境が急速に整ったことを背景として、これらのコンテンツをどのように取り扱うかについての検討が拡がっている。ＨＤＤ／ＤＶＤレコーダを始めとするデジタル家電の普及は、個人での大量の映像コンテンツの所有やアクセスを容易なものとしている。
【０００３】
このような「コンテンツ爆発」とも呼べる状況においては、ユーザに対して、映像コンテンツの視聴時（さらに、検索時や編集時等）における利便性をいかに提供するかが課題となる。例えば、テレビ番組等の放送コンテンツに対しては、意味のあるまとまり毎に自動でチャプタ（インデックス）を付与し、このチャプタを使用してボタン一つで見たいシーンを頭出しできるようにする等の視聴支援技術が重要になる。
【０００４】
また、番組中のカット点を検出し、タイムスタンプをメタデータとしてチャプタリングする手法もあるが、これは、特許庁標準技術集にもあるように、古くから提示されている手法である（例えば、非特許文献１参照）。しかし、一般に放送コンテンツの場合は、数秒ないし十数秒に１回程度カット点が出現し、コマーシャル放送や音楽プロモーションなどのビデオクリップの場合は、１秒未満に１回カット点が出現することも珍しくない。これは、１つの番組でもチャプタが数百〜数千に及ぶことを意味する。利便性を考えると、好みのシーンを探すために数百回以上の操作をすることは現実性に乏しく、カット点をそのままチャプタリングに用いることは殆ど無意味であると言わざるを得ない。
【０００５】
これに対し、いくつかのカット点をまとめることによってチャプタの数を減らす試みも行われている。また、映像に言語情報や音声信号を組み合わせることによってチャプタリングを行うもの（例えば、非特許文献１又は特許文献１参照）や、カット点間の画像の類似性に基づくもの（例えば、非特許文献２参照）、テンプレートマッチングなどの特定シーンに対する認識抽出処理や隠れマルコフなどのモデルにより、映像におけるカット構成の規則性や映像コンテンツの構成上の特徴を用いるもの（例えば、非特許文献３又は特許文献２参照）、カット点の代わりに単純に一定時間毎にパケット化するもの（例えば、非特許文献４参照）などが提案されている。便宜上、これらをカテゴリモデリング法（ＣＭ法）と呼ぶことにする。
【特許文献１】特開２０００−２８５２４３号公報
【特許文献２】特開２００３−５２００３号公報
【特許文献３】特開２００４−３６１９８７号公報
【非特許文献１】「ショット分類に基づく映像への自動的索引付け手法」（井手一郎、他、信学論（Ｄ−ＩＩ）、  Ｖｏｌ．Ｊ８２−Ｄ−ＩＩ、  Ｎｏ．１０、  ｐｐ．１５４３−１５５１、  Ｏｃｔ．  １９９９．）
【非特許文献２】「映像対話検出によるテレビ番組コーナ構成高速解析システム」（青木恒、信学論（Ｄ−ＩＩ）、  Ｖｏｌ．Ｊ８８−Ｄ−ＩＩ、  Ｎｏ．１、  ｐｐ．１７−２７、  Ｊａｎ．  ２００５．）
【非特許文献３】「カット構成の規則性を利用したスポーツ映像のプレイ単位への分割」（椋木雅之、他、信学論（Ｄ−ＩＩ）、  Ｖｏｌ．Ｊ８５−Ｄ−ＩＩ、  Ｎｏ．６、  ｐｐ．１０１６−１０２４、  Ｊｕｎ．  ２００２．）
【非特許文献４】「固定長の時空間画像に基づく映像シーンのクラスタリング」（岡本啓嗣、他、信学論（Ｄ−ＩＩ）、  Ｖｏｌ．Ｊ８６−Ｄ−ＩＩ、  Ｎｏ．６、  ｐｐ．８７７−８８５、  Ｊｕｎ．  ２００３．）
【非特許文献５】「Ｅｖｅｎｔ  Ｄｅｔｅｃｔｉｏｎ  ａｎｄ  Ｓｕｍｍａｒｉｚａｔｉｏｎ  ｉｎ  Ｓｐｏｒｔｓ  Ｖｉｄｅｏ」（Ｂ．Ｌｉ、他、ＩＥＥＥ  Ｗｏｒｋｓｈｏｐ  ｏｎ  ＣＢＡＩＶＬ  ２００１、  ｐｐ．１１４−１３８、  Ｄｅｃ．  ２００１．）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、理想的な視聴支援技術を実現するためには、なんらかの形でメタデータを付与するための技術が必要である。ところが、一般的には、メタデータを付与するためには高度なメディア理解技術が必要と考えられており、これが大きな実用上の障壁となっている。
【０００７】
つまり、汎用的なメタデータを付与し得るシステムの構築には、膨大な知識ベースと理解ルールの構築が必要であるため、メタデータ付与の自動化プロセスは、用手的アプローチが認められている（人海戦術的なメタデータ付与が必要視されている）アセットマネジメントシステムなど一部の業務用システム以外は不向きであると考えられてきた。
【０００８】
言い換えると、従来の「対象物を個別特定」するトップダウン的手法は、ロバスト性に乏しく、被写対象が特定されにくい一般状況下では非常に困難な課題を抱えている（ここでいうトップダウン的手法とは、テンプレートマッチングや事前学習等、対象物を限定した処理を伴う、対象物を事前に特定しなければ対象物を抽出できないタイプの手法を指している）。
【０００９】
トップダウン型の手法は、そのシステムにおける検出対象を検出する際の性能に大きく依存していることや、理想的モデルと現実データとの乖離に課題があり、顔、ヒト、車又は建築構造物といった対象物やシーン特徴量の変化など、事前に検出対象を特定した上で検出しモデルに当て嵌めてメタデータを付与しているため、ロバスト性を失いやすいのである。
【００１０】
更に、ここで、従来技術における実用上の課題について考える。
【００１１】
まず、第一に、チャプタの付与基準がユーザにとって自明的でなければならない。例えば、視聴中に次のチャプタへジャンプする「スキップ視聴」をする場合、ユーザは、「スキップ後のシーンがどのようなシーンであるか」を事前にイメージできなければ現実的に使用できない。ユーザにとって「次にどのようなシーンまでジャンプするのか分からない」状況は、乱数でスキップしていることと変わりなく、次第に視聴意欲が削がれることとなる。
【００１２】
つまり、「チャプタ」の位置がユーザにとって自明的でない場合には、視聴対象のシーンが「どのシーンがスキップされたのか分からない」ことになり、「（重要なシーンを見逃している可能性もあるため、）使い勝手が悪い」ことにつながる。「どのシーンがスキップされて、次にどのシーンが来るのか」が予測可能でなければ、自明的なチャプタとは云えない。
【００１３】
このように、視聴時、検索時又は編集時においてユーザを支援するためには、チャプタがユーザにとって自明的な位置に付与されていることが絶対条件であると云える。チャプタの位置は有意でしかもなるべく固定的な意味を持つシーンであることが望ましく、重要なシーンの見逃しを招かないためには、特に再現率が重視されなければならない。
【００１４】
ここで、有意で固定的な意味を持つシーンとは、例えば、バラエティ番組での各グループの登場シーンや野球番組での各ピッチングシーンなど、ユーザが暗黙裡に「次のチャプタ」として意識するであろうシーンであり、しかも比較的出現頻度が高いものを指す。
【００１５】
この視点で考えると、これまでに開示されている技術はいずれも十分ではない。
【００１６】
例えば、あるチャプタについて、意味のあるカット点として必ずしも間違っていなければ正解に準じて評価するケースがある。この場合、あるチャプタは１０分程度の意味のある固まり（シーン）に付与され、また別のチャプタは３秒程度のシーンに付与されるなど、番組内での各チャプタの粒度が変化してしまうため、利用者は、次に１０分間分のシーンがスキップされるのか数秒分のシーンがスキップされるのか分からず、非常に困惑する。
【００１７】
また、野球やサッカーなど特定の番組コンテンツに限定するケースでは、当然汎用性が無く、野球放送に限っても、天候の変化や球場の変化などに対応することができない。
【００１８】
また、映像をショットの切り替わり点や適当な映像の変化点や時間幅で幾つかの小区間に区切り、それぞれの区間を適当な手法で分類し、分類された各クラスタの相互関係を総当りで検査しながら映像の構造要素を抽出してチャプタを生成するケースもある（例えば、特許文献１参照）。
【００１９】
しかし、このケースでは、分類性能により構造要素の抽出性能が左右される。一般の放送映像は、必ずしも撮影条件が安定しているとは限らず、天候が変化したり、テロップやキャプションが挿入されたりと、多種多様な変化が発生する。このため、現在の技術水準における一般映像に対する分類性能は、非常に低く不安定である。
【００２０】
このように分類性能が不安定であるが故に、従来の手法では、分類の結果できあがったクラスタ同士を総当りで比較（相互相関などにより類似度を比較）し、同じようなシーンがクラスタに含まれていないかを検索（又は推定）する必要があった。
【００２１】
上記特許文献１では、総当り検索をチェーン検出と称して、映像内の番組構造を抽出するために用いている。しかし、元々、同じであると判定できなかった（ために同一クラスタに分類できなかった）二つのクラスタを、どうやって同一であるとしてチェーン化するかについては言及されていない。
【００２２】
そのため、現実的な精度を有して実装することが不可能であると考えられるが、仮にチェーン化するための類似判定エンジンが実現できたとしても、クラスタを総当りで検索し、その中から構造要素を抽出しなければならず、計算コストは莫大なものになる。その上、でき上がったチャプタが自明的なものになるかどうかは、更に別問題として残ったままである。
【００２３】
一般に、ＣＭ法のチャプタ性能は、想定したモデルに対しての再現率（Ｒｅｃａｌｌ）と適合率（Ｐｒｅｃｉｓｉｏｎ）によって表される。
【００２４】
例えば、上記特許文献２および非特許文献５に開示されているように、条件を極めて限定し（この例では、映像を野球放送に限定）、分類する画像の種類も事前に固定的に決定し（この例では、ピッチングシーンと固定）、分類のための特徴量をピッチングシーンに特化した場合でも（この例では、後述の図２のステップＳ３０４及びステップＳ３０５のように、「ピッチングシーンは緑色の領域と褐色の領域が出現するはず」と決め打ちで特徴量を設定しても）、再現率は９８％、適合率は９５％と報告されている。
【００２５】
一見、これらの数値は、性能として十分であると見えるかも知れない。しかし、この数値は、構造化がしやすく画像パターンが比較的変化しない野球の場合に対し、条件を特化したものであることに注意されたい。
【００２６】
しかも、この例では、野球放送中の各投球シーンにチャプタが付与されることになるが、一試合では、おおよそ２００〜３００球程度の投球シーンが発生する。例えば２５０球とした場合、一試合中に各投球シーンを逃さずチャプタリングできる確率は、単純計算で９８％の２５０乗に相当する確率である。０．９８の２５０乗は約０．００６４である。つまり、ほぼ０％である。
【００２７】
まとめると、従来のビデオ処理（ビデオチャプタリング）システムは、画像の分類性能に立脚している。しかし、動画像データの（時間）変化・変動により、必ずしも良好な分類結果を得られるとは限らない。これまでは、動画像を複数のフレームからなるセグメントに分割し、各セグメントの特徴量（画像全体の色ヒストグラムや時間方向での変化量など）を用いて分類していた。しかし、放送中には、任意のタイミングでテロップが入ったり、カメラの切り替えが行なわれるため、人間が見た時に同じカテゴリに分類して欲しいセグメントが、別のカテゴリに分類されることが往々にして発生してしまう。特にトップダウン型では、こういった状況の変化に全く追従できない。
【００２８】
このような、雑音耐性が低く使用条件が限定された不安定な分類方法による、ビデオ処理は結果として非常に性能が低く、実用性に乏しいものとなる。しかも、分類性能の低さを後段（チャプタ位置決定ルーチン）が補おうとするため、分類された各カテゴリ間の類似度を全検索しながら映像構造を推定するなど、速度面でも非常に遅いアプローチとなっている。そのため、分類性能の低さから逃れるために、放送コンテンツの内容に対して特化したアプローチを取らざるを得ず、汎用性が犠牲となっていた。
【００２９】
更に、繰り返しになるが、生成されるチャプタの付与基準はユーザにとって自明的でなければならず、有意で固定的な意味を持つシーンであることが要求される。
【００３０】
本発明は、上記課題に鑑みてなされたものであり、汎用的且つ高速で、ユーザにとって自明的なチャプタを生成し得る映像シーン分類装置等を提供することを目的とする。
【課題を解決するための手段】
【００３１】
上記課題を解決するために、本発明に係る映像シーン分類装置は、映像を構成する複数の画像のうち、１つ以上の画像にインデックスを付与する映像シーン分類装置であって、前記複数の画像について、画像上の特徴を表す分類指標に基づいて複数のクラスタに分類する画像分類手段と、分類された前記複数のクラスタの中から少なくとも１つのクラスタを選択するクラスタ選択手段と、前記選択されたクラスタを構成する画像のうち、少なくとも１つの画像にインデックスを付与するインデックス生成手段とを備える。
【００３２】
この構成によって、映像を構成する画像について分類指標に基づいてクラスタリングすることにより、ロバスト性の良い分類を行うと共に、インデックスを付与すべきクラスタを特定することが可能になるため、ユーザにとってより自明的なチャプタリングが可能になる。
【００３３】
また、前記映像シーン分類装置は、さらに、サンプリングすることによって前記映像から複数の画像を取得する映像サンプリング手段と、取得された前記画像毎に画像処理を施す処理範囲を決定し、当該処理範囲に対して画像処理を施すことにより分類指標を特定する処理範囲決定手段とを備え、前記画像分類手段は、決定された前記処理範囲における画像上の特徴を表す分類指標に基づいて前記分類を行うことを特徴とする。
【００３４】
この構成により、それぞれの画像内でより有意な範囲を動的に限定して画像処理を施して分類指標を決定するので、画像内にキャプションが入るなど、画像に変動が生じた場合であっても、分類指標に基づいて安定したクラスタリングを行うことが可能となる。
【００３５】
また、前記映像シーン分類装置は、さらに、分類された前記クラスタの分類指標又は前記映像の番組内容情報に基づいて、インデキシングルールを決定するインデキシングルール選択手段を備え、前記インデックス生成手段は、選択された前記クラスタに対して、選択された前記インデキシングルールを用いて、前記画像にインデックスを付与することを特徴とする。
【００３６】
この構成により、分類指標又は番組内容情報に基づいて、選択されたクラスタに対してインデックスを付与する際のルールを選択することができ、より画像の特徴に応じたインデックスを付与することが可能となる。
【００３７】
また、前記インデキシングルール選択手段は、前記番組内容情報に基づいて、（１）選択されたクラスタに含まれる全ての画像にインデックス付与する、（２）選択されたクラスタに含まれる全ての画像を時間軸でソートし、所定時間以内の画像の固まり毎にインデックス付与する、及び、（３）所定のクラスタに含まれる映像ブロックのうち、他の所定クラスタにより連続的な固まりに含まれることのなかった映像ブロックにインデックス付与する、とする何れかのルールの中からインデキシングルールを選択することを特徴とする。
【００３８】
この構成により、より木目細かいインデックスの付与ルールを設定することができるため、ユーザにとってより自明的なチャプタを生成することが可能になる。
【００３９】
なお、本発明は、上記映像シーン分類装置における特徴的な構成手段をステップとする映像シーン分類方法として実現したり、それらステップをコンピュータ等に実行させるプログラムとして実現したりすることもできる。そして、そのプログラムをＤＶＤ等の記録媒体やインターネット等の伝送媒体を介して広く流通させることができるのは云うまでもない。さらに、本発明は、上記特徴的な構成手段を備える集積回路として実現することもできる。
【００４０】
さらに、本発明は、上記映像シーン分類装置１００の特徴的な構成手段を備えるクライアント−サーバシステムとして実現することも可能である。
【発明の効果】
【００４１】
本発明により、番組内容に対して、汎用的かつロバストで、ユーザにとってより分かりやすいチャプタリングが可能となる。そして、ユーザにとって自明的で有意なチャプタを生成することができる。
【００４２】
同時に、生成されるクラスタ精度が高いため、従来手法のような生成クラスタ間に対する類似検査やクラスタ同士の分類行程が不要であるため、高速処理が可能となる。
【発明を実施するための最良の形態】
【００４３】
以下、本発明の実施の形態について、図面を参照しながら説明する。なお、本発明について、以下の実施の形態および添付の図面を用いて説明を行うが、これは例示を目的としており、本発明がこれらに限定されることを意図しない。
【００４４】
また、本発明は、映像データ（放送コンテンツや個人コンテンツといった、動画データ及び静止画データ）をより効果的、かつ効率的に分類し、より精度良く、高速にチャプタを生成する映像シーン分類チャプタリング技術に関するものである。この映像シーン分類チャプタリング技術は、映像データの種類に対する事前知識が与えられる場合には、更に良い性能を有する。この事前知識の例として、放送コンテンツでは番組情報（ＥＰＧ情報）１２０、個人コンテンツではユーザ入力による「旅行」「運動会」といった情報やＧＰＳなどによる位置情報や屋内外情報などがある。
【００４５】
（実施の形態）
図４は、本実施の形態における映像シーン分類装置１００の機能構成を示すブロック図である。まず、映像シーン分類装置１００の機能の概略を説明し、その後、各部の機能について詳細な説明を行う。
【００４６】
最初に、映像入力部１０１において映像情報（例えば、映像自体を表す映像データ及び映像の制御又は管理に関連する情報など）が入力される。入力された映像情報は、映像サンプリング部１０２において、予め規定された時間間隔（又は／及び予め決められた規則）に基づいてサンプリングされ、静止画像の集合体が形成される。なお、カット検出機能（即ち、映像を撮影するカメラの切り替わりを示すカット点を検出する機能）を用いることによって、カット点で映像をサンプリングしてもよい（以降の説明では、映像サンプリング部１０２からの出力を、便宜上「カット画像」と呼ぶことにする。もちろん、任意のサンプリング手段によって映像をサンプリングしてもよい。）。
【００４７】
画像分類部１０４は、カット画像を分類（以下「クラスタリング」ともいう。）することによって、１又は複数のクラスタを生成する部分である。なお、上記カット画像をクラスタリングすることにより得られた、１又は複数の静止画像で構成される画像グループを「クラスタ」という。画像分類部１０４における分類性能が、本映像シーン分類装置１００全体の性能に大きく影響することは、既に従来技術の課題として述べた通りである。カット画像を分類する際の指標（以下「分類指標」という。）は、各カット画像の画像情報（例えば、カット画像自体を表す画像データ及びカット画像の特徴等を表す情報など）から算出する訳であるが、カット画像内の変化に適応的に追従し、安定した分類を可能とするために、画像分類部１０４の前段に、処理範囲決定部１０３を設ける。
【００４８】
処理範囲決定部１０３は、分類指標（即ち、クラスタリングに用いる物理量）を各カット画像の画像情報から算出する際に、画像全体ではなく、各カット画像内で分類に適した情報を持つ範囲を動的に変更し設定する部分である。なお、ユーザは、操作入力手段（図示せず）を用いて、上記分類指標の変更が可能である。
【００４９】
次に、処理範囲決定部１０３の機能について、簡単に説明する。例えば、野球放送でピッチングシーンにインデックス（チャプタ）を付与する場合を考える。ピッチングシーンは、ヒトが見ればすぐピッチングシーンであると分かるが、実際のピッチングシーンのカット画像には様々なバリエーションがある（図１２参照）。
【００５０】
例えば、カット画像１２０１を基本のピッチングシーンとすると、カット画像１２０２は、スコアやボールカウントを表すキャプションが付加されたピッチングシーンであり、更にカメラの角度が若干変化している（カット画像１２０２ではバックネット側の壁が見えている）。また、カット画像１２０３は、バッターに関するキャプションが付加されたピッチングシーンである。
【００５１】
処理範囲決定部１０３は、このような複数のカット画像に対し、ヒトが番組内容を把握するにあたって注目すると予想される範囲（例えば、野球であれば、ピッチャーとバッターの対戦を表示している範囲）を、各カット画像について動的に設定する（図１３参照）。図１３に示されている処理範囲設定例１３０１、処理範囲設定例１３０２及び処理範囲設定例１３０３が、それぞれ、図１２におけるカット画像１２０１、カット画像１２０２及びカット画像１２０３についての処理範囲設定例に相当する。
【００５２】
このように、本実施の形態では、従来のような画像全体の情報を用いる（又は、画像全体を対象とする）のではなく、処理範囲決定部１０３によって設定された処理範囲の画像情報を用いることで、画像分類部１０４により、分類対象の変化に適応してロバストな分類（クラスタリング）を可能とする（処理範囲決定部１０３の動作原理及び内部動作に関する説明は後述する）。
【００５３】
次に、クラスタ選択部１０６の機能について説明する。クラスタ選択部１０６は、画像分類部１０４において分類されたクラスタの中から、どのクラスタをチャプタ付与に用いるかを、予め規定したルールに従って選択する。当然ながら、各クラスタの要素はカット画像であり、１以上のカット画像が集まって各クラスタを形成している。
【００５４】
クラスタ選択部１０６におけるクラスタを選択する際のルールの一例として、「最も要素数の多いクラスタを選択する」場合について説明する。
【００５５】
クラスタ選択部１０６は、画像分類部１０４によって分類されたクラスタについて、それらの要素数（カット画像数）が多いもの順にソートすることとする。この場合、最も要素数の多いクラスタは、最も頻繁に放送された同種のカット画像で構成されており、最も頻繁に放送されたということは、配信側が最も伝えたい（伝えなければならない）番組の主構成要素であると云える（正しく分類できない従来の映像分類方法では、このような推論が成立しないことに留意されたい。）。
【００５６】
例えば、野球放送であれば、放送中に最も頻繁に出現するカットは、図１２（ａ）〜図１２（ｃ）のようなピッチングシーンのカット画像である（実験により、他のカット画像に較べて圧倒的に出現頻度が高いことを確認している）。そして、当然ながら、ピッチングシーンが野球プレイのトリガーであり、最も重要な構成要素である。
【００５７】
即ち、野球放送において、最も要素数の多いクラスタを選択すると、そのクラスタにはピッチングシーンのカット画像が集まっている。
【００５８】
他の種類の番組では、クラスタの選択方法を変えるべき場合も考えられるが、クラスタ選択部１０６の基本的な動作は、このように必要な（又は重要な）クラスタを選択することである（クラスタ選択部１０６の詳細説明は後述する）。
【００５９】
次に、インデキシングルール選択部１０７の機能について説明する。インデキシングルール選択部１０７は、上記クラスタ選択部１０６で選択されたクラスタのカット画像にインデックス（チャプタ）を付与する際のルールであるインデックス生成ルール（「チャプタ生成ルール」ともいう。）を決定する。
【００６０】
例えば、先述の「最も要素数の多いクラスタ」がクラスタ選択部１０６で選択された場合のインデックス生成ルールについて説明する。この場合、インデキシングルール選択部１０７が決定するインデックス生成ルールは、「クラスタ選択部１０６で選択されたクラスタに含まれるカット画像全てに、インデックスを付与する」こととする。これは、後述の図９のフローチャート中で、ステップＳ９０９の「直接生成」に相当する。
【００６１】
その他のインデックス生成ルールについては後述するが、インデキシングルール選択部１０７の基本的な動作は、このようにチャプタを付与する際に必要なルールを決定することである（インデキシングルール選択部１０７についての詳細な説明は後述する）。
【００６２】
次に、インデックス生成部１０８の機能について説明する。インデックス生成部１０８は、クラスタ選択部１０６で選択されたクラスタ（これを「選択クラスタ」という。）を構成する全てのカット画像又はその一部のカット画像について、インデキシングルール選択部１０７で選択されたインデックス生成ルールに沿って、インデックスを付与する。
【００６３】
インデックス生成部１０８の動作について、先述のインデキシングルール選択部１０７の例に沿って具体的に説明すると、クラスタ選択部１０６において「最も要素数の多いクラスタ」が選択され、インデキシングルール選択部１０７において、「直接生成」ルールが選択される。そこで、インデックス生成部１０８は、「最も要素数の多いクラスタ」を画像分類部１０４によって分類されたクラスタ群から読み出し、「最も要素数の多いクラスタ」に含まれるカット画像の全てにインデックスを付与する。
【００６４】
このようにクラスタ選択部１０６において選択された選択クラスタを、画像分類部１０４によって分類されたクラスタ群から読み出し、インデキシングルール選択部１０７で選択されたルールに沿って、選択クラスタのカット画像の一部もしくは全部にインデックスを付与する。
【００６５】
次に、インデックス再生部１０９の機能について説明する。インデックス再生部１０９は、インデックス生成部１０８で生成されたインデックス（チャプタ）を用いて映像の再生を行う。次のチャプタが付与されているカット画像への移動や、前のチャプタが付与されているカット画像への移動、チャプタが付与されているカット画像単位での手動スキップや自動スキップ、各チャプタが付与されているカット画像以降を所定の秒数間再生して、次のチャプタが付与されているカット画像に移動するなどを行う。
【００６６】
次に、出力部１１０の機能について説明する。出力部１１０は、生成されたインデックスを表すインデックス情報を出力する。出力部１１０は、インデックス情報を単独で出力しても、入力された映像に関連づけて出力しても、入力された映像にチャプタを設定して、チャプタ付与済み映像として出力してもよい。
【００６７】
最後に、番組情報１２０について説明する。番組情報１２０は、インターネット、放送電波又はユーザの入力によって取得可能な、番組に関する情報を意味しており、ＥＰＧ情報などを含む意である。上記処理範囲決定部１０３、クラスタ選択部１０６及びインデキシングルール選択部１０７は、補助情報としてこの番組情報１２０を利用することができる。
【００６８】
以上が、映像シーン分類装置１００の機能の概略である。
【００６９】
なお、図４の構成図は例示を目的としており、本発明は図４に含まれる構成要素を必ずしも全て含まなくてもよく、必要な機能を果たす最小限の構成を選択して実現してもよい。
【００７０】
なお、映像サンプリング部１０２でのサンプリング間隔は、固定の時間幅（例えば、１秒）でも、ＭＰＥＧストリームのＩフレームのサンプリングでも、カット点でのサンプリングでもよく、任意の既存の手法を用いてサンプリングしてもよい。
【００７１】
また、映像サンプリング部１０２では、静止画像であるカット画像を出力する代わりに、入力映像を適当な長さの映像小ストリームに分割して、映像ストリーム群として出力してもよい。この場合、サンプリングされた静止画像に対する一連の後処理は、映像小ストリームの一部もしくは全フレームに対する処理と読み替えることができる。
【００７２】
なお、ユーザや上位システムからの指示入力を受け付けることが必要な場合は、映像入力部１０１を介して受け付けてもよい。
【００７３】
以下、本発明に係る映像シーン分類装置１００の各主要部分の動作について、詳細に説明する。
【００７４】
図５は、映像シーン分類装置１００のより詳細な機能ブロック図である。そして、各部の内部動作の様子を示すフローチャートを図６〜図１０に示す。
【００７５】
図５に示されるように、まず、映像入力部１０１に映像データが入力されると（Ｓ５０１）、映像サンプリング部１０２によってサンプリングされたカット画像群が生成される（Ｓ５０２）。カット画像群を生成する手法は、前述のように、映像内容の変化点でサンプリングすることによる生成（Ｓ５３０）や、カットの変化点を検出し、変化点でサンプリングすることによる生成（Ｓ５３１）、一定時間毎のサンプリングによる生成（Ｓ５３２）など、従来の任意の手法を用いることができる。
【００７６】
次に、処理範囲決定部１０３の動作について詳細に説明する（図５、図１０参照）。
【００７７】
サンプリングされたカット画像群の画像データが入力されると（Ｓ１００１）、処理範囲決定部１０３は、各カット画像から画像特徴量を算出する（Ｓ５０３／Ｓ１００２）。ここで用いる画像特徴量は、画像に関する物理的な情報であり、輝度情報（エッジ、マッハ効果量など）や色情報（色相、色差など）である。処理範囲決定部１０３は、抽出された画像特徴量に基づいて、画素単位もしくは小ブロック単位で画像特徴量の解析を行う（Ｓ５０４／Ｓ１００３）。解析された各画像特徴量には、所定の重み付けが付加され、重み付けされた各画像特徴量が合算され（Ｓ５０５／Ｓ１００４）、閾値処理がなされる（Ｓ１００５）。
【００７８】
さらに、処理範囲決定部１０３は、閾値処理によって特定された画像特徴量に対応するカット画素群に対し、それらを内包もしくは外接する、カット画像内における矩形を決定する（Ｓ１００６）。処理範囲決定部１０３は、このように決定された矩形を処理範囲として出力する（Ｓ５０５／Ｓ１００７）。
【００７９】
ここで、画像特徴量の解析や重み付け、閾値の処理を、番組内容情報、番組書誌情報又は関連情報を用いて適応的に変化させてもよい。
【００８０】
例えば、ＥＰＧ情報を介して番組内容情報を取得し（Ｓ１０２０）、キャプションの発生しそうな領域や発生頻度を推定（Ｓ１００９）したり、テロップ／各種情報の発生しそうな領域や発生頻度の推定（Ｓ１０１０）や、キャプションやテロップなどの補助情報ではなく、主たる画像情報が表示されている領域の推定（Ｓ１０１１）を行うこともできる。そして、画像特徴量を解析する際に、主たる画像領域の画像特徴量を優先的に使用したり、重み付けの際に、キャプション領域から発生した画像特徴量の重みを相対的に低く（又は高く）することにより、主たる画像情報の影響を相対的に高く（又は低く）することができる。加えて、閾値の範囲については、テロップやキャプションが発生しやすい場合には画像全体の変化量が大きくなりやすいため、閾値を上げたり、逆に、テロップやキャプションの発生が少ない場合には、閾値を下げるなど、領域・頻度の推定と各処理とを任意に組み合わせた処理を行うこともできる。
【００８１】
なお、決定される処理範囲の形状は矩形に限定されない。なお、閾値処理で残った点を内包もしくは外接する矩形の代わりに、閾値処理を行わず、単位面積当たりの画像特徴量がより大きくなるように、所定（又は所定以上）の大きさの領域を画像中に動かしながら処理範囲を決定してもよい。なお、ＥＰＧ情報を介して番組の内容情報を取得した際に、映像中の主体的な色を番組内容から推定し（例えば、サッカー放送なら緑色など）、その色との乖離度を画像特徴量としてもよい。
【００８２】
以上の結果、図１２および図１３に示すように、カット画像１２０１、カット画像１２０２及びカット画像１２０３の各画像に対する処理範囲として、処理範囲設定例１３０１、処理範囲設定例１３０２及び処理範囲設定例１３０３が決定される。
【００８３】
処理範囲決定部１０３において、処理範囲は、おおよそ次のように決定する。例えば、処理範囲設定例１３０１の場合、投手の左右にエッジおよび色の差が顕著に現れる。バッターボックスの白線、打者、キャッチャー、アンパイヤについても同様である。これらを重み付けしながら足し合わせることで、所定の閾値よりも大きい画像特徴量を有する点（小ブロック）が発生する。
【００８４】
所定の閾値を超えた点（小ブロック）のうち、もっとも画像中で左側にあるものが、ピッチャーの左側のエッジ、右側にあるものがバッターボックスの白線、上側は打者の頭及びキャッチャーの頭、下側はピッチャーのユニフォームのウエストラインおよびグラウンドの緑と茶色の境目である。この４辺が決定し、処理範囲設定例１３０１のような範囲となる。処理範囲設定例１３０２、処理範囲設定例１３０３も同様であり、ユニフォームやバッターボックスなどのエッジの他、キャプション（スコア表示およびボールカウント表示）、テロップ（打者紹介）などのエッジに沿って処理範囲が決定されている。
【００８５】
次に画像分類部１０４について詳細に説明する（図５、図６参照）。
【００８６】
図６は、画像分類部１０４の内部動作の様子を示すフローチャートである。
【００８７】
画像分類部１０４が呼び出されると（Ｓ６０１）、変数ｎが「１」にセットされ（Ｓ６０２）、前述のカット画像の入力とともにクラスタリングが開始される（Ｓ６０３）。その後、分類指標が選択され（Ｓ６０４／Ｓ５０６）、選択された分類指標でクラスタリングが実施される（Ｓ６０５／Ｓ５０７）。クラスタリングアルゴリズムは、既存の任意の手法でよい。
【００８８】
なお、クラスタリング手法を大別すると、似たもの同士を併合してまとめて行く階層的なクラスタリングと、似たものが結果的に同じグループに入るように集合を分割する非階層的クラスタリングとがある。非階層的クラスタリングの代表例として、「ｋ−ｍｅａｎ法」がある。また、階層的なクラスタリングでは、最初、各対象をばらばらの一つのクラスタとみなして、近いクラスタを次々と統合することによって、最終的な分類結果を得る。階層的クラスタリングの代表例として、「最小距離法」などが挙げられる。
【００８９】
さて、クラスタリングの結果、Ｃｎ個クラスタが生成される（Ｓ６０６）。ここではｎ＝１なので、Ｃ1個である。ここで、定数ｋとｎを比較し（Ｓ６０７）、ｋとｎが等しくない場合には、Ｃn個のクラスタからｐ個のクラスタを選択し（Ｓ６０８／Ｓ５０９）、ｎに１を付加して（Ｓ６１０）、ｐ個のクラスタに含まれるカット画像群を新たな入力画像データとしてクラスタリングをやり直す（Ｓ６０３）。このとき、ｐはＣn以下の正の整数である。ｐの決定方法は、要素数の多いクラスタから順に、総入力カット画像数の所定パーセントに達するまでの個数とし、Ｃnの２分の１を超えないものとする。
【００９０】
また、上記ステップＳ６０７でｋとｎが等しい場合には、クラスタリングを完了する（Ｓ６１１）。
【００９１】
なお、ｐの決定方法は上記に限らず、単に、要素数の多いクラスタから順に、総入力カット画像数の所定パーセントに達するまでの個数として決定してもよい。また、定数によってｐを決定していてもよい。また、Ｃnの所定割合としてもｐを設定してもよい。
【００９２】
なお、定数ｋは、２ないし３といった固定値でよいが、Ｓ６０７の代わりに、特定のクラスタ（要素数が上位のクラスタ）に所定の割合以上のカット画像が分類されているか否かでもう一度クラスタリングをおこなうかどうか決定してもよい。
【００９３】
なお、処理範囲決定部１０３から処理範囲が入力されてもよい（Ｓ６３０）。処理範囲が入力された場合、クラスタリングする分類指標として、処理範囲によって限定される物理量を表す情報を用いてもよい。例えば、処理範囲の形状、位置及びサイズなどをクラスタリングする際の分類指標としてもよい。
【００９４】
なお、分類指標を選択する際に、データベースに格納されている分類指標を参照してもよい（Ｓ６２０）。例えば、上記のような処理範囲の形状、位置及びサイズといった分類指標の他、画像情報から物理量として色指標（色相指標、色差指標など）や、輝度指標を選び出し、分類指標としてもよい。
【００９５】
なお、処理範囲の内側の画像のみを対象として、色差指標や、輝度指標などの画像特徴量を算出してもよい。これはもちろん、処理範囲の外側の画像のみでもよく、更に、所定の幅を持つ処理範囲の周辺領域のみを対象としてもよい。
【００９６】
これらの分類指標は、物理量を直接使用するほか、ヒストグラムを用いてもよい。また、ＤＣＴ（Discrete Cosine Transform）やＦＦＴ（Fast Fourier Transform）などの周波数変換を行い、その直流成分又は交流成分を指標として用いてもよい。
【００９７】
なお、以下の２つの物理量を利用してクラスタリングする際の分類指標としてもよい。「１．処理範囲のカット画像中における位置」、「２．処理範囲の内外の一定範囲の画像特徴（例えば周囲２０ピクセルなど）」。
【００９８】
特に、上記「２．」の物理量は、具体的には処理範囲の境界線から内外一定範囲の画素について、エッジ強度と色相のヒストグラムをそれぞれ取得し、ヒストグラムは参照した画素数で正規化しておく。カット画像の分類は、上記「１．」および「２．」の二つの分類指標から、例えば最短距離法に基づくクラスタリングによって行う。この際、２つの分類指標を個別に用いることで、２段階のクラスタリングを行ってもよい。
【００９９】
まず、はじめに、処理範囲間の距離Ｄ１を距離尺度としてクラスタリングを行う。処理範囲を矩形とした場合、Ｄ１は二つの矩形の対応する頂点間の距離である。処理範囲間の距離を比較することで、カット画像の大まかな構図を判定する効果が見込まれる。次に、１回目のクラスタリングで要素数が多いクラスタから順に一定個数のクラスタを選び、そのクラスタに属するカット画像に対してヒストグラムに基づいて距離Ｄ２を設定し、２回目のクラスタリングを行う。
【０１００】
Ｄ２は、エッジ強度のヒストグラムＨｅ、色相のヒストグラムＨｈを用いて定義し、
【０１０１】
【数１】
0004841553.tif 000002
のように表される。なお、ＭＩＮ｛ｘ，ｙ｝は、ｘ，ｙのうち、小さい方の値を表す。また、Ｎｅ、Ｎｈは、ヒストグラムの次数を表す。例えば、Ｎｅは１６、Ｎｈは１５として色相のヒストグラムＨｅは、有彩色１２段階と無彩色３段階を含むものとする。エッジ強度ヒストグラムＨｅと色相ヒストグラムＨｈを用いて、カット画像の前景および背景の類似度を判定する効果が見込まれる。両者を組み合わせることによって、「ヒトがどこを見て類似性を判断しているか」を大まかに考慮しつつ、注目している部分の近傍の特徴を捉えることで、よりヒトの直感に近い分類が可能となる。
【０１０２】
次に、クラスタ選択部１０６について詳細に説明する（図５、図７参照）。
【０１０３】
図７は、クラスタ選択部１０６の内部動作の様子を示すフローチャートである。
【０１０４】
画像分類部１０４においてクラスタリングが終了すると（Ｓ７０１）、クラスタ選択指標が決定される（Ｓ７０２）。クラスタ選択指標には大きく３種類あり、「クラスタの要素数で選択」、「所定の算出式から選択」及び「特定のクラスタを選択」のうちから何れかが選択される。
【０１０５】
ここで、クラスタの要素数に基づいて選択された場合（Ｓ７０３：Ｙｅｓ）、要素数の多いクラスタの上位Ｓ１個が選択され（Ｓ７０４、Ｓ５４０）（例えば野球の場合、ピッチングシーンのクラスタに相当する。この場合、Ｓ１が１であり、上位１個のクラスタが選択され）、ステップＳ７０５に移動する。
【０１０６】
クラスタの要素数順で選択されず（Ｓ７０３：Ｎｏ）、所定の算出式より選択されていた場合（Ｓ７０５：Ｙｅｓ）、所定の算出式を用いてＳ２個のクラスタが選択される（Ｓ７０６）。
【０１０７】
所定の算出式（条件式）は、例えば、次のように記述することができる。「ｉ番目のクラスタＣｉの要素数をＲｉとするとき、Ｔｈ１＜Ｒｉ＜Ｔｈ２を満たすｉのうち、Ｒｉの大きいものから順にＳ２個を選択」する（このケースは、例えば、要素数が５〜１０枚のカット画像からなるクラスタを選択する場合などが相当する。クイズ番組の出題シーンなど、番組構成上のトピックの総数がおおよそ予想される場合に有効である。クイズ番組のタイトルなどから、おおよその問題数が予め定義され、その数に有った要素数を持つクラスタを自動選択する。）。その後、次のステップＳ７０７に移動する。
【０１０８】
所定の算出式より選択されておらず（Ｓ７０５：Ｎｏ）、特定のクラスタより選択されていた場合（Ｓ７０７：Ｙｅｓ）、クラスタを選択するためのマッチングのテンプレートが読み込まれる（Ｓ７０８）。テンプレートはパターンＤＢとしてデータベース化し、記憶しておいても、必要に応じて読み出してもよい（Ｓ７１０）。読み込まれたテンプレートを用いて、各クラスタとパターンマッチングを行い、テンプレートに適合するパターンのクラスタを選択して（Ｓ７０９）、クラスタ選択は完了する（Ｓ７１１）。
【０１０９】
一方、特定のクラスタからの選択がされていない場合（Ｓ７０７：Ｎｏ）、これまでに何らかのクラスタの選択がなされているかどうかを判定する（Ｓ７５０）。これまでに何らかのクラスタの選択がされていれば、クラスタ選択完了（Ｓ７１１）に移動する。何も選択されていなければ、これまでの３通りの何れかの選択手法に限定するよう、フィードバックを選択決定ステップ（Ｓ７０２）に返す（Ｓ７２１）。
【０１１０】
なお、上記ステップＳ７０９でのパターンマッチングは、全クラスタについて行っても、一部のクラスタについて行ってもよく、各クラスタの一部の画像（代表画像）についてのみ行ってもよい。
【０１１１】
また、番組情報１２０、例えばＥＰＧ情報を介して番組内容情報、番組書誌情報又は関連情報を取得し（Ｓ７２０）、クラスタ選択指標の決定（Ｓ７０２）や、読み込むテンプレート種類の決定（Ｓ７０８）、Ｓ１、Ｓ２の決定（Ｓ７０４、Ｓ７０６）などの補助情報として用いてもよい。
【０１１２】
例えば、番組情報１２０から番組のジャンルが「野球」と分かった場合には、前述のように、「クラスタの要素数で選択」し、「Ｓ１は１」とすることができる。同じく前述のように、（１０問前後が出題される）クイズ番組と分かった場合には、「所定の算出式から選択」し、算出式は「Ｔｈ１を７、Ｔｈ２を１３」とし、「Ｓ２は５」などと設定できる。
【０１１３】
また、上記ステップＳ７０６では、要素数Ｒｉだけではなく、時間分布を用いて条件式としてもよい。例えば、条件式をｉ番目のクラスタＣｉのｊ番目の要素（カット画像）ＲｉｊのタイムスタンプをＴＲｉｊとし、時間軸で最小のＴＲｉｊをＭＩＮ＿ＴＲｉｊ、最大のＴＲｉｊをＭＡＸ＿ＴＲｉｊとするとき、番組の本編の時間幅をＴ１からＴ２として、本編時間に対する出現時間ズレ（ＤＩＦ１）を（ＭＩＮ＿ＴＲｉｊ−Ｔ１）＋（Ｔ２−ＭＡＸ＿ＴＲｉｊ）で定義してもよい。この場合、よりＤＩＦ１が小さいクラスタを選択することで、同じ要素数のクラスタであっても、より番組全般の特徴を捉えたクラスタを取得することができる。
【０１１４】
逆に、ＭＩＮ＿ＴＲｉｊとＭＡＸ＿ＴＲｉｊが、所定の時間幅の中に収まっているようなクラスタを選択するような条件式としてもよい。例えば、１時間番組の中の最初の１０分から１５分の間に収まっているようなクラスタを選択する、などである。このようなクラスタを時間幅を変えながら複数選択することで、番組内でコーナー毎に大きく構成が変化し、コーナー相互に類似性が無いような番組であっても、適切にインデックス（チャプタ）を付与するためのクラスタを選択することができる。
【０１１５】
同様に考えると、ニュース番組など、アンカーパーソンのシーンには類似性があっても、ＶＴＲシーンには類似性がないような番組であれば、番組本編全体に渡って、時間分布の均質なクラスタと、局所的に固まって出現するクラスタを組み合わせることで、容易にチャプタ付与ができる。
【０１１６】
ちなみに、後述のＢｒｉｃｋ（チャプタ／インデックス候補の固まり）を生成する際に、チャプタに有効な固まり（インデックスを付与すべき範囲を示す固まり）を生成するのか、無効な固まり（インデックスを付与すべきでない範囲を示す固まり）を生成するのかを決定しなければならない。このニュース番組の例では、局所的に固まって出現するクラスタは、インデックスに不向きな「無効な固まり」を生成するためのクラスタといえ、この「無効な固まり」に含まれないカット画像を有する時間分布が均質なクラスタは、インデックスを付与すべきクラスタであると云える。
【０１１７】
もちろん、条件式は上記に限らない。上記の例のように、番組情報１２０を補助情報として、一般に想定し得る番組構造への仮説（仮定）を数式化したものであれば任意のものを扱ってよい。例えば、時間軸では、カット画像の分布、分散、平均又は最頻出現時間帯などを用いて、番組構造との対比を行い、適切なクラスタ選択に役立ててもよい。要素数でも同様に、出現カット数、最大数、平均などを用いて、番組構造との対比を行い、適切なクラスタ選択に役立ててもよい。
【０１１８】
更に、番組情報１２０を用いて、使用するテンプレートを決定してもよい。特定の図柄やレイアウトを有するシーンが存在する番組であれば、固定的なテンプレートの使用は非常に有効である。このとき、画像分類部１０４によって各クラスタは適切に分類されているため、各クラスタの代表画像（例えば、平均画像）とのマッチングを行い、最も近いクラスタを選択するだけで、他の同様の構図を持つカット画像を一度に取得することができる。画像全体に対して、同じマッチングを行った場合と同様の結果を各クラスタの代表画像（例えば、平均画像）とのマッチングを行っただけで得られるため、大幅な計算コストの削減にもつながる。
【０１１９】
ステップＳ７７７では、選択クラスタと選択クラスタの属性情報を出力する。ここで、「選択クラスタの属性情報」とは、クラスタを選択した際の「Ｂｒｉｃｋを生成するのに有効／無効なクラスタかどうか」及び「直接インデックスを付与すべきクラスタかどうか」について表す情報である。
【０１２０】
属性情報を決定する判断基準は、先のニュース番組や野球番組の例で述べたクラスタ自身の選択基準と同一である。「単独で適切にインデックスを付与するためのクラスタとして選択した」クラスタであれば「直接インデックスを付与すべきクラスタ」という趣旨を伝える属性情報がそのクラスタに付与されて出力される。他の属性情報について同様である。
【０１２１】
なお、このＢｒｉｃｋに関する動作については、次のインデキシングルール選択部１０７にて詳しく説明し、その後、クラスタ選択部１０６における各Ｂｒｉｃｋ用のクラスタ選択例を示すこととする。
【０１２２】
なお、単純に、番組構成においてより意味を持つシーン群やショット群が、他のシーン群やショット群に較べて利用（放送）されることが多くなることは、合理的な仮定であると云える。これは、作成者側の構造的に番組を構成し視聴者に流れを伝えたいという意図を考えた場合でも同様と思われる。番組内容を理解するために必要な導入部分やブリッジ部分は、映像文法的にも高い頻度で繰り返され、番組内のコーナーやシーン（の先頭や重要部分の開始位置）を構成するものと考えられる。クラスタ選択部１０６は、このような番組構成上の特徴を踏まえた上で、クラスタを選択することができる。
【０１２３】
なお、クラスタを選択する個数について、例えば次のように求めてもよい。
【０１２４】
コマーシャルなどを含んだ番組の総放送時間をＬｐとし、番組内での平均カット出現数をＣｒとする（カット画像を用いた場合）。ｉ番目のクラスタＣiに含まれるカット数をＮＣiとするとき、選択する個数となるクラスタ数は、
【０１２５】
【数２】
0004841553.tif 000003
を満たす最小の正の整数ｋとして求めてもよい。なおＴｃはしきい値であり、γをパラメータとしてＴｃはγとＴｐとＣｒの積で求められる。γは番組中において特に重要なカットがどの程度含まれるかを表すパラメータである。
【０１２６】
次に、インデキシングルール選択部１０７の動作について詳細に説明する（図５、図９参照）。後半では、クラスタ選択部１０６における各Ｂｒｉｃｋ用のクラスタ選択例を併せて示す。
【０１２７】
図９は、インデキシングルール選択部１０７の内部動作の様子を示すフローチャートである。
【０１２８】
インデキシングルール選択部１０７は、クラスタリング結果（Ｓ９０２）を示すデータの入力（Ｓ９０３）を受け、まず、使用するクラスタ数やクラスタの要素数から、Ｂｒｉｃｋの生成が必要かどうかを判断する（Ｓ９０４）。ここでは、選択されたクラスタ内のカット画像が、時間的にほぼ連続した固まりを形成している場合に、その固まりをＢｒｉｃｋと呼んでいる。
【０１２９】
Ｂｒｉｃｋの生成が必要と判断された場合、Ｂｒｉｃｋ生成が必要であることを次段に伝えるシグナルが発行される（Ｓ９０５／Ｓ５４３）。そして、そのＢｒｉｃｋがチャプタとして「有効」な候補なのか、「無効」な候補なのかを決め（Ｓ９０６）、有効な場合は「有効チャプタ」シグナルを発行する（Ｓ９０７）。無効の場合は「無効チャプタ」シグナルを発行する（Ｓ９０８／Ｓ５４２）。その後、各発行シグナルを入力映像に対するインデキシングルールとして出力し（Ｓ９１０／Ｓ５１１）、インデキシングルールの決定処理を終了する（Ｓ９１１）。
【０１３０】
Ｂｒｉｃｋを用いたチャプタリングルールの概略について、図１１を用いて説明する。映像データとしてカット画像が入力され（Ｓ１１０１）、クラスタリングされる（Ｓ１１０２）。クラスタのうち、クラスタＡ、Ｂ、Ｆが選択されたとして、選択クラスタ内のカット画像を元の映像データの時系列上に配置する（Ｓ１１０３）。Ｓ１１０４の黒色のデータ位置（黒カット画像）が、クラスタＡ、Ｂ、Ｆの何れかに属しているカット画像のデータ位置に相当し、白色（白カット画像）がそれ以外に相当する。ここで、Ｂｒｉｃｋを生成すると、Ｓ１１０５Ａ、Ｓ１１０５Ｂ、Ｓ１１０５Ｃ、Ｓ１１０５Ｄのように、４つのＢｒｉｃｋ（固まり）ができる。
【０１３１】
ここでのＢｒｉｃｋの生成アルゴリズムは、先述のように選択されたクラスタ内のカット画像が、時間的にほぼ連続した固まりを形成している場合にＢｒｉｃｋとし、連続していない場合にはＢｒｉｃｋとしないという比較的単純な方法を取っている。時間的に連続かどうかの判定は、図１１の任意の黒カット画像と黒カット画像の間に所定の時間幅（Ｔｗｈ）以上、一つ以上の白カット画像が含まれている場合、その黒カット同士は同じＢｒｉｃｋを形成しない。つまり、Ｔｗｈ以上、時間的に間を置かずに黒カット画像が出現する限り、時間的にほぼ連続であるとする。
【０１３２】
この所定の時間幅Ｔｗｈは、インデックスを生成する際に必要となる（インデックス生成部１０８で必要となる）が、インデキシングルール選択部１０７では、時間幅Ｔｗｈを特定する必要はない（インデキシングルール選択部１０７は、必要最低限、Ｂｒｉｃｋ作成が必要かどうかのみをルールとして決定すれば良い）。
【０１３３】
なお、図１１のＢｒｉｃｋ生成（Ｓ１１０５）及びインデックス付与（Ｓ１１０６）の例は、図９のＳ９０７の有効チャプタが選択された場合に相当する。後述のインデックス生成部１０８でも触れるが、「Ｂｒｉｃｋを有効チャプタ」とした場合、インデックスは各Ｂｒｉｃｋの先頭（もしくは各Ｂｒｉｃｋ内の任意箇所）に付与される。
【０１３４】
逆に、ステップＳ９０８の「Ｂｒｉｃｋを無効チャプタ」とした場合は、無効なＢｒｉｃｋ生成用のクラスタと、Ｂｒｉｃｋを生成しないクラスタがクラスタ選択部１０６で選択されている（先述のニュース番組など、アンカーパーソンのシーンには類似性があっても、ＶＴＲシーンには類似性がないような番組などのケース）。
【０１３５】
無効Ｂｒｉｃｋも、Ｂｒｉｃｋの生成アルゴリズムとしては、先の有効Ｂｒｉｃｋと同様である。無効Ｂｒｉｃｋ生成用のクラスタに属するカット画像から無効Ｂｒｉｃｋが生成される。ここで、便宜上、『Ｂｒｉｃｋを生成しないクラスタに選択されたクラスタ』に属するカット画像を有意カット画像と呼ぶことにする。
【０１３６】
この「Ｂｒｉｃｋを無効チャプタ」とした場合、インデックスは無効Ｂｒｉｃｋではなく、有意カット画像に付与されるが、有意カット画像のうち、各無効Ｂｒｉｃｋに含まれるカット画像には付与されない。
【０１３７】
図１１と同様、無効Ｂｒｉｃｋを用いたチャプタリングルールの概略について、図１４を用いて説明する。映像データとしてカット画像が入力され（Ｓ１４０１）、クラスタリングされる（Ｓ１４０２）。クラスタのうち、クラスタＡ、Ｂ、Ｆが無効Ｂｒｉｃｋを生成するクラスタとして選択され、クラスタＤが有効なクラスタとして選択されたとする。これらの選択クラスタ内のカット画像を元の映像データの時系列上に配置する（Ｓ１４０３）。ステップＳ１４０４の黒色のデータ位置（黒カット画像）が無効ＢｒｉｃｋクラスタＡ、Ｂ、Ｆの何れかに属しているカット画像のデータ位置に相当し、白黒の斜め線の模様が入ったデータ位置（模様カット画像）がクラスタＤの有意カット画像（６つあるとする）のデータ位置に相当し、白色（白カット画像）がそれ以外に相当する。ここで、先のＢｒｉｃｋと同じように無効Ｂｒｉｃｋを生成すると、Ｓ１４０５Ａ、Ｓ１４０５Ｂ、Ｓ１４０５Ｃ、Ｓ１４０５Ｄのように４つの無効Ｂｒｉｃｋができる。
【０１３８】
ここで、６つの有意カット画像Ｓ１４１０Ａ、Ｓ１４１０Ｂ、Ｓ１４１０Ｃ、Ｓ１４１０Ｄ、Ｓ１４１０Ｅ及びＳ１４１０Ｆにインデックスを付与するが、このうち、無効Ｂｒｉｃｋに含まれているＳ１４１０Ｂ及びＳ１４１０Ｄにはインデックスが付与されず、残りの４つにインデックスが付与される。
【０１３９】
インデキシングルール選択部１０７におけるＢｒｉｃｋ生成時のインデキシングルールの決定方法は、以上の通りである。
【０１４０】
次に、ステップＳ９０４でＢｒｉｃｋ生成が必要ないと判断された場合について説明する。この場合は、選択されているクラスタのカット画像に直接インデックスを付与する「直接生成」シグナルを発行する（Ｓ９０９／Ｓ５４４）。そして、ステップＳ９１０に進む。
【０１４１】
基本的に、Ｂｒｉｃｋの生成が必要かどうかの判断は、クラスタ選択部１０６で（このクラスタは無効Ｂｒｉｃｋ用のクラスタ、このクラスタは有効Ｂｒｉｃｋ用のクラスタなどと）選択された情報に従って決定される。しかし、何らかの原因でクラスタ選択部１０６でのクラスタ指定情報が欠落した場合などには、上記図７のＳ７２０と同様に、番組内容情報、番組書誌情報又は関連情報を、ＥＰＧ情報を介して補助情報として入力してもよい（Ｓ７２０）。Ｂｒｉｃｋの生成が必要かどうかについて、補助情報に基づいて判断してもよい。
【０１４２】
このように、インデキシングルール選択部１０７では、Ｂｒｉｃｋ生成が必要かどうかに基づいて、Ｂｒｉｃｋ生成が必要であれば有効Ｂｒｉｃｋか無効Ｂｒｉｃｋかを決定し、Ｂｒｉｃｋ生成の必要がなければ直接生成を決定する。
【０１４３】
この「直接生成」、「有効Ｂｒｉｃｋ生成」及び「無効Ｂｒｉｃｋ生成」の各シグナルに対する実インデキシングルールをまとめると次のようになる。
【０１４４】
・直接生成：選択されたクラスタに含まれる全カット画像にインデックスを付与する。
【０１４５】
・有効Ｂｒｉｃｋ生成：選択されたクラスタに含まれる全カット画像を時間軸でソート、所定時間以内の固まり毎にインデックスを付与する。
【０１４６】
・無効Ｂｒｉｃｋ生成：所定のクラスタ（有意なクラスタ）に含まれるカット画像（有意カット画像）のうち、他の所定クラスタ（無効クラスタ）によるＢｒｉｃｋに含まれることのなかったカット画像にインデックスを付与する。
【０１４７】
なお、クラスタ選択部１０６で、有効Ｂｒｉｃｋを生成するクラスタや、無効Ｂｒｉｃｋを生成するクラスタとインデックス付与に有効なクラスタをどのように選択するかについてであるが、上述したクラスタ選択部１０６の説明においても触れたように、各クラスタの要素数や総要素数で判断する。他にも、各クラスタの時間分布状況や、ＥＰＧ情報を始めとする番組情報１２０を用いることも前に述べた通りである。
【０１４８】
重複するが、ニュース番組など、アンカーパーソンのシーンには類似性があっても、ＶＴＲシーンには類似性がないような番組であれば、番組本編全体に渡って、時間分布の均質なクラスタと、局所的に固まって出現するクラスタを組み合わせることで、容易にチャプタを付与することができる。
【０１４９】
つまり、ニュース番組であれば、時間分布の均質なクラスタをチャプタに有効なクラスタ（有意カットを含むクラスタ）とし、時間分布に偏りのあるクラスタを無効Ｂｒｉｃｋ生成用のクラスタとする、という方法を用いることができる。
【０１５０】
また、上位ｎ個（例えば１個）のクラスタに含まれるカット画像数の総カット画像数に占める割合が、所定値（例えば１５％）以上である場合には、直接生成用のクラスタとして、そのクラスタを選択する、という方法を用いることができる。これは特に野球などのスポーツ番組において有効な手法である。もちろんこの場合、番組情報１２０から野球番組である、という情報を取得して、上位ｎ個を無条件に選択してもよいし、逆に、野球番組で且つ所定割合以上という複数条件にしてもよい。
【０１５１】
また、上位ｎ個（例えば１０個）のクラスタのカット数の総和を取っても、総カット数の所定割合を超えないような場合や、上位のクラスタが時間分布でそれぞれ偏っている場合などは、上位ｎ個のクラスタや、時間的に偏っている各クラスタを「有効Ｂｒｉｃｋ」生成用として選択する、という方法を用いることができる。これは、特にバラエティ番組や音楽番組に有効である。もちろんこの場合も、先の野球の例と同じように番組情報１２０から補助情報を得てもよい。
【０１５２】
なお、この「直接生成」、「有効Ｂｒｉｃｋ生成」及び「無効Ｂｒｉｃｋ生成」のいずれかを選択する際に、クラスタ選択部１０６におけるマッチングテンプレートを用いたパターンに適合したクラスタ（Ｓ７０８、Ｓ７０９）を用いてもよい。
【０１５３】
例えば、特定のシーンには必ずインデックスを付与したい場合には、テンプレートのパターンに適合したクラスタを「直接生成」に用いてもよい。アンカーパーソンのシーンを集め、無効Ｂｒｉｃｋに含まれた以内の場合には、インデックスを付与したい場合には、アンカーパーソン用のテンプレートを利用し当該のシーンを集めてもよい。
【０１５４】
なお、上記図９の説明では、インデックス付与ルールとして、「直接生成」、「有効Ｂｒｉｃｋ生成」及び「無効Ｂｒｉｃｋ生成」についてのみ記述したが、これらを組み合わせてインデックス付与ルールを構築してもよい。例えば、無効Ｂｒｉｃｋと有効Ｂｒｉｃｋをそれぞれ生成し、無効Ｂｒｉｃｋと重複しない（内包しない／内包されない／一部共有しない）ような有効Ｂｒｉｃｋにインデックスを付与してもよい。また、階層的にインデックスを生成するようなルールとしてもよい。例えば、より細かいレイヤーのインデックスとして「直接生成」を用い、より粗い（上位の）レイヤーのインデックスとして「有効Ｂｒｉｃｋ生成」を用いてもよい。ここで、階層構造とした場合に、互いのレイヤーの情報を相互で利用できるようにしても、もちろんよい。
【０１５５】
なお、「直接生成」、「有効Ｂｒｉｃｋ生成」及び「無効Ｂｒｉｃｋ生成」のみではなく、単純に「利用する」クラスタ、「利用しない」クラスタを指定して、それらを組み合わせることでルールを構成してもよい。「直接生成」、「有効Ｂｒｉｃｋ生成」及び「無効Ｂｒｉｃｋ生成」は、「利用する」クラスタ、「利用しない」クラスタを指定して組み合わせた特殊なケースの一つである。
【０１５６】
また、「利用する」クラスタ、「利用しない」クラスタの選択と組み合わせルールを、番組情報１２０を補助情報として生成してもよい。
【０１５７】
なお、Ｂｒｉｃｋを生成する際の閾値条件である所定の時間幅（Ｔｗｈ）を、Ｂｒｉｃｋを構成しないクラスタに属するカット画像の枚数（Ｎlim）に置き換えても良く、例えば、一つのＢｒｉｃｋとして継続できる許容限界（他のカットが連続して混入してよい枚数）をＮlimとすると、Ｎlimは、
【０１５８】
【数３】
0004841553.tif 000004
を満たす最小の正整数として求めてもよい。
【０１５９】
あるＢｒｉｃｋ内において、Ｂｒｉｃｋ構成対象のｋ個のクラスタ以外に属するカット画像が連続してＮlim枚を超えて出現した場合、そのＢｒｉｃｋは分割されるものとする。なお、ＴHは閾値であり、ηをパラメータとして、ηとｋの積をＣｒで割ったものとして求められる。ηは、番組中において非重要なカットがどの程度含まれるかを表すパラメータである。先のγと合わせてηの値は、複数の番組から実験的に求めた値の平均値を採用できる。
【０１６０】
次にインデックス生成部１０８の動作について詳細に説明する（図５、図８参照）。
【０１６１】
図８は、インデックス生成部１０８の内部動作の様子を示すフローチャートである。
【０１６２】
インデキシングルールの入力（Ｓ８０１）、クラスタリング結果の入力（Ｓ８０２）、クラスタ選択結果の入力（Ｓ８９３）によるデータ入力後（Ｓ８０４）、インデキシングルールの発行シグナルに沿って実際にインデックスの生成を行う。直接生成シグナルが発行されている場合、選択されたクラスタのカット画像を直接利用することになり（Ｓ８０５：Ｙｅｓ）、選択されたクラスタ内の全カット画像のタイムスタンプを抽出（Ｓ８０６／Ｓ５４５）した後、抽出したタイムスタンプの各時刻に合わせてインデックスを生成し（Ｓ８１２）、出力する（Ｓ８１３）。
【０１６３】
直接生成シグナルが発行されていない場合（Ｓ８０５：Ｎｏ）、Ｂｒｉｃｋを生成することが基本となる。そのため、Ｂｒｉｃｋ生成のシグナルが発行されていない場合は（Ｓ８０７：Ｎｏ）、エラー処理を行う（Ｓ８３０）。
【０１６４】
Ｂｒｉｃｋ生成のシグナルが発行されている場合（Ｓ８０７：Ｙｅｓ）、有効Ｂｒｉｃｋもしくは無効Ｂｒｉｃｋを、選択されているクラスタを用いて実際に生成する（Ｓ８０８）。生成方法の説明は、既にクラスタ選択部１０６やインデキシングルール選択部１０７の説明時に述べている通りである。
【０１６５】
次に、生成されたＢｒｉｃｋが有効チャプタである場合（Ｓ８０９：Ｙｅｓ／Ｓ５４８）、すなわちチャプタ生成（インデックスの付与）に有効なＢｒｉｃｋである場合、各Ｂｒｉｃｋの先頭画像のタイムスタンプを抽出し（Ｓ８１０／Ｓ５４６）、タイムスタンプの各時刻に合わせてインデックスを生成して（Ｓ８１２）、出力する（Ｓ８１３）。
【０１６６】
さらに、生成されたＢｒｉｃｋが無効チャプタである場合（Ｓ８０９：Ｎｏ／Ｓ５４７）、すなわちチャプタ生成（インデックスの付与）に無効なＢｒｉｃｋである場合、各Ｂｒｉｃｋに含まれない選択クラスタのカット画像のタイムスタンプを抽出し（Ｓ８１１／Ｓ５４７）、タイムスタンプの各時刻に合わせてインデックスを生成して（Ｓ８１２）、出力する（Ｓ８１３）。
【０１６７】
なお、Ｓ８１０では各Ｂｒｉｃｋの先頭画像のタイムスタンプを抽出したが、各Ｂｒｉｃｋ内の任意のタイミング（例えば、平均時間、中央時間など）をタイムスタンプとして抽出してもよい。
【０１６８】
なお、上記では、インデックス生成のアルゴリズムの一例を示したが、インデックス生成のアルゴリズムはこれに限定されるものではなく、インデックスルールとして決定されたルールを実際に実行するアルゴリズムであれば任意の形をとって良いことは云うまでもない。
【０１６９】
以上が、本発明に係る実施の形態１における映像シーン分類装置１００の説明である。
【０１７０】
なお、ここで、参考までに従来例と本願との比較を行ってみる。
【０１７１】
図１は、従来例１（特許文献１）の実質的な概略処理ステップを示している。映像をセグメント化し、音響特徴量と映像特徴量からセグメントの類似度を測り、クラスタリングする。その上で互いに類似するセグメントを含むクラスタを探し出し、類似チェーンを構成している。
【０１７２】
発明が解決しようとする課題にて先述したように、精度や速度両面をはじめ、実現性そのものにも課題を有しているが（仮に出願時の技術水準で複数のジャンルに適用した場合、適合率・再現率とも３０〜５０％程度になると試算）、放送番組に汎用的にインデックスを付けようとする点で、本願と目的は同一であり、先行例として従来技術水準を表す文献である。
【０１７３】
本願発明とは、明らかに構成が異なる上、実現可能であるという点で大きな違いがある。更に、得られる精度や速度面での圧倒的な優位性があり、しかも、カット画像内のテロップなどにもロバストな分類を行い、ヒトの知覚に沿った分類ができるという、従来例１にはない特有の効果も有している。
【０１７４】
図２は、従来例２（特許文献２）の実質的な概略処理ステップを示している。映像ジャンルを特定し、例えば野球の場合には、水平方向に３つの小領域を設定し、緑色および褐色の領域を検出することでピッチングシーンの検出を試みるものである。
【０１７５】
上記発明が解決しようとする課題にて述べたように、ジャンルに対する汎用性がない上、球場や天候にも左右される。また、図１２のように水平方向に大きくテロップが出た場合にも無力である（先に示した再現率は９８％、適合率は９５％という数値は、テロップを含んだカット画像群に対してではない）。経験的に、野球のカット画像には、２０〜３０％の確率で複数のキャプションやテロップがカット画像中に含まれている。このような場合には、特に再現率が約６０〜８０％に大きく低下すると試算される。
【０１７６】
このように、実現時には映像状況へのロバスト性とジャンルの汎用性の無さが課題になるが、放送番組にインデックスを付けようとする点で、本願と目的は同一であり、先行例として従来技術水準を表す文献である。
【０１７７】
本願発明とは、明らかに構成が異なる上、得られる精度で本願発明は圧倒的な優位性があり、しかも、カット画像内のテロップなどにもロバストな分類を行い、ヒトの知覚に沿った分類ができるという、従来例２にはない特有の効果も有している。
【０１７８】
図３は、従来例３（特許文献３）の実質的な概略処理ステップを示している。画像を領域分割し、各領域の形状についてその形状の異質度を算出し、更に、特に色特徴量から誘目度を算出している（主として、赤色を最も目立つ色と定義し、赤色からの色距離を測ることで誘目度を算出している）。異質度と誘目度から領域分割された領域で最も注目される領域を決定している。更に、別途、画像を小ブロックに分け、小ブロックごとにこの誘目度の平均値を求め、複数個（例えばｋ個）の小ブロックの誘目度を順に並べたｋ次元の特徴ベクトルを生成し、その特徴ベクトルで画像を分類している。
【０１７９】
この従来例３は、チャプタ生成等を意図したものではなく、画像を検索する際に、画像のなかで特徴的な部分に特化した検索を可能とするためのものである。例えば、ユーザが「花が主体的に写っている画像」をキー画像に検索する場合、画像全体を捉えて類似度を評価するよりも、特徴的な部分（花の写っている部分）のみで類似度を評価したほうがユーザの検索したいと考えている実情に沿っていて良い、という主張である。
【０１８０】
本願発明とは、分類画像の類似分類に際して、ヒトの知覚特性を考慮した分類を行うと言う大くぐりな着想で類似しているものの、本願では主体的に映っている物の検出は行っておらず、逆に比較的普遍的な特徴を持つ範囲を算出している。
【０１８１】
従来例３を、例えば野球放送に応用した場合、図１２のカット画像１２０２の打者が赤いユニフォームを着ていたとすると、カット画像１２０２では、打者の形状だけが注目領域として検出される。一般に同じチームの選手は同じ色のユニフォームを着用しているので、ピッチングシーンに限らず、同じ赤いユニフォームの選手が映っているカット画像は、高い類似度を持ち同じカテゴリに分類されることが容易に想像される。更に、カット画像１２０３の選手紹介キャプションが、赤色の背景を有していた場合、カット画像１２０３では選手紹介キャプションだけが注目領域として検出される。カット画像１２０３とカット画像１２０２は同じカテゴリに分類されないことも容易に想像できる。
【０１８２】
更に、攻守交替した場合には、ユニフォームの色が入れ替わるため、ピッチングシーンに限っても、同じカテゴリへの分類は非常に困難であり、またピッチングシーン以外のカット画像が紛れ込む誤分類も頻発することが予測される。
【０１８３】
つまり、本願発明とは明らかに構成が異なる上、分類のみで見た時の得られる精度についても、本願発明は圧倒的な優位性がある。しかも、カット画像内のテロップなどにもロバストな分類を行うことができるという、従来例３にはない特有の効果も有している。
【０１８４】
このように、従来技術では、分類精度を上げるために、入力画像の種類を限定した上で、分類に用いる特徴量を特化するアプローチが取られていたことに、改めて留意して頂きたい。例えば、野球放送のみと言った限定をした上で、野球放送に特化した特徴量を用いて分類を行っていた。
【０１８５】
逆に、限定を行わない従来の分類方法では、分類の結果、できあがったクラスタは、本来同じクラスタであるべきカット画像が別々のクラスタに属していたり、全く異なるカット画像が同一クラスタに属しているなど、基本分類性能に問題がある。後段の処理ではそれを吸収するため、総当り的処理が必要となり精度及び速度両面で課題があったことも改めて留意して頂きたい。
【０１８６】
以上が、本願と従来例との比較である。
【０１８７】
なお、客観的な実験データによる優位性も確認できている。以下にデータを転記する。
【０１８８】
本願発明の構成によるインデキシングを行うと、例えば野球放送の場合、ピッチングシーンの適合率は平均９９．６％以上であった。これは、コマーシャルを含む野球放送全編を対象とした場合の数値であり、しかも、比較的悪条件の放送を用いた、実応用を念頭に置いたテストでの数値である（テストには、３本の野球放送を用いた。その内１本は、試合開始当初は明るい晴天であったが、次第に曇天になって暗くなり、途中から雪が降り出して一時は映像が白くなるほどの降雪があった映像であり、さらに別の１本は、晴天から後半は強い雨になった映像である。云うまでもなく、従来のロバスト性のないクラスタリング手法では破綻するケースであり、野球に特化した特許文献２のようなシステムでも色情報が失われるため破綻するケースである。）。
【０１８９】
また、他のジャンルの番組でも良好な結果を得ており、処理時間も約１００分（カット画像数１４１１枚）の野球映像に対して、約４５秒（３ＧＨｚＣＰＵ）であった。この処理時間は、カット画像の読み込み、処理範囲の決定、クラスタリング、インデキシングにかかる時間の総計である。
【０１９０】
以上のように、本願発明は、明らかに従来例と構成が異なる上、従来の技術水準では到底成し得ない精度と速度を達成することができる。さらに、従来にはない特有の効果も有していることが確認される。
【０１９１】
なお、上記では、放送コンテンツの分類やインデックスの付与を中心に説明してきたが、分類の対象となるデータは放送コンテンツに限らず、任意の画像データであってもよい。
【０１９２】
特に、静止画を中心とした個人コンテンツ（デジタルカメラで撮影した画像群）には非常に有効である。例えば、同じ場所に複数回行った時の写真を本方式によって同じカテゴリに分類し、同じタグを付与することが（インデキシングすることが）できる。
【０１９３】
間歇撮影や連続撮影をしたような画像群の場合、その利点は更に大きくなる。上記従来技術での個人コンテンツの分類では、撮影時間のバラつきなどを利用するものがほとんどであるため、画像の視覚的な特徴に基づいた納得性の高い分類はできない。更に、連続的に取得された画像群では撮影が一定間隔で行われているため、従来技術が拠り所としている時間的なバラつきも利用することができないため、従来手法での分類はほぼ破綻してしまう。
【０１９４】
しかし、本手法であれば、離散的な時間間隔で撮られた静止画像群（個人の旅行毎の写真など）であっても、連続的な時間間隔で撮られた画像群（監視カメラ映像や、個人のビデオ映像、個人記録写真など）であっても、視覚的な特徴に基づいてインデキシングすることが可能である。そのため、本手法の利点は更に大きくなる。
【０１９５】
例えば、仮に間歇撮影のできるカメラを用いて静止画像（例えば１枚／秒間隔で撮影された画像）を、数時間分から数日分に渡り大量に蓄積する状況を考える。具体的には、例えば監視カメラの画像であってもよいし、個人が旅行中にカメラを体に装着して旅行記を撮影した画像であってもよい。このような大量画像を自動的に整理したい、もしくはインデックスを付与したいというのは自然な動機として発生すると考えられる。
【０１９６】
個人旅行の場合で考えると、旅行先の風景の変化（山間部にいる、海辺にいる、街中にいるなど）や天候の変化、屋内外の変化などで撮影される画像は少しずつ変化する。これらの画像は短い時間（数秒から数分）では、おおきな変化は殆ど発生せず、おおよそヒトには同じようなシーンであると知覚されることが多い。しかしコンピュータビジョンの観点では、人の眼には同じようなシーンであってもそれを同じカテゴリに分類することは一般に困難である。これは先に説明した放送コンテンツにおけるテロップの有無や細かな相違が、従来技術における分類の阻害要因になっていることと同じである。大量の自然画像（個人コンテンツ）の中から局所的に雰囲気が似ているものを、画像情報で「似ている」として同じカテゴリに分類することは、非常に困難である。
【０１９７】
そこで、本方式の分類方法を導入する。本方式によりヒトの視覚特徴量（見た目の雰囲気）に基づいた分類が可能となる。視覚的に重要では無いところ（注目されない領域）の画像情報による影響を軽減することができるため、よりヒトの直感に近いような、「似ている」と思う画像群を一かたまり（クラスタ）としてインデキシングすることができる。
【０１９８】
もちろん、それぞれのクラスタに属する画像に対してタグを付与してもよい。
【０１９９】
このように、分類の対象となるデータは放送コンテンツに限らず、任意の画像データであってもよい。
【０２００】
なお、ここでは個人コンテンツの例として個人旅行の間歇撮影画像を取り上げたが実施の形態はこれに限定されるものではなく、任意の静止画像や動画像を対象として良いことは云うまでもない。
【０２０１】
以上のように、本発明により、「対象物を特定しない（トップダウン型ではない）、ヒトの知覚に近い安定した映像の新しい分類方法による、汎用的且つ高速で、ユーザにとって自明的なインデックス（チャプタ）を生成するチャプタリングシステムの構築が可能となり、快適な映像再生検索システムを構築することが可能になる。
【産業上の利用可能性】
【０２０２】
本発明は、ビデオレコーダ（ＨＤＤレコーダやＤＶＤレコーダなど）をはじめ、ＴＶ、携帯電話、カーナビゲーションシステム、ＤＶＤプレーヤ等といった、録画もしくは再生機器等に適用できることはもちろん、サーバでチャプタリングし、そのデータを映像と併せてクライアント装置に配信するようなサーバ−クライアントシステム等としても利用が可能である。
【図面の簡単な説明】
【０２０３】
【図１】図１は、従来例１の概略を表す図である。
【図２】図２は、従来例２の概略を表す図である。
【図３】図３は、従来例３の概略を表す図である。
【図４】図４は、実施の形態１における映像シーン分類装置の機能構成を示すブロック図である。
【図５】図５は、実施の形態１における映像シーン分類装置の詳細な機能構成を示すブロック図である。
【図６】図６は、画像分類部の内部動作の様子を示すフローチャートである。
【図７】図７は、クラスタ選択部の内部動作の様子を示すフローチャートである。
【図８】図８は、インデックス生成部の内部動作の様子を示すフローチャートである。
【図９】図９は、インデックスルール選択部の内部動作の様子を示すフローチャートである。
【図１０】図１０は、処理範囲決定部の内部動作の様子を示すフローチャートである。
【図１１】図１１は、有効Ｂｒｉｃｋによるインデックスを付与する様子を模式的に示す図である。
【図１２】図１２（ａ）〜（ｃ）は、カット画像例を示す図である。
【図１３】図１３（ａ）〜（ｃ）は、処理範囲の決定例を示す図である。
【図１４】図１４は、無効Ｂｒｉｃｋによるインデックスを付与する様子を模式的に示す図である。
【符号の説明】
【０２０４】
１００    映像シーン分類装置
１０１    映像入力部
１０２    映像サンプリング部
１０３    処理範囲決定部
１０４    画像分類部
１０６    クラスタ選択部
１０７    インデキシングルール選択部
１０８    インデックス生成部
１０９    インデックス再生部
１１０    出力部
１２０    番組情報
１２０１    カット画像
１２０２    カット画像
１２０３    カット画像
１３０１    処理範囲設定例
１３０２    処理範囲設定例
１３０３    処理範囲設定例
【図１】
0004841553.tif 000005
【図２】
0004841553.tif 000006
【図３】
0004841553.tif 000007
【図４】
0004841553.tif 000008
【図５】
0004841553.tif 000009
【図６】
0004841553.tif 000010
【図７】
0004841553.tif 000011
【図８】
0004841553.tif 000012
【図９】
0004841553.tif 000013
【図１０】
0004841553.tif 000014
【図１１】
0004841553.tif 000015
【図１２】
0004841553.tif 000016
【図１３】
0004841553.tif 000017
【図１４】
0004841553.tif 000018