(57)【要約】【課題】輝度または色の微小変動に伴って生じるカットチェンジの誤検出を減らす。【解決手段】精細ヒストグラム生成部４０１は、カットチェンジ検出の処理対象とする第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、特徴分布算出部４０２は、精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出する。そして、類似度算出部４０４は、第１の画像と第２の画像のそれぞれの特徴分布の類似度を算出する。判定部４０５は、特徴分布の類似度に基づいて、第１の画像と第２の画像の境界がカットチェンジであるかを判定する。【選択図】図５
2008085539.tif 000002
【特許請求の範囲】
【請求項１】
画像のカットチェンジを検出する検出処理をコンピュータに実行させるプログラムにおいて、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、
前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出し、
前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する
ステップを備えるプログラム。
【請求項２】
前記特徴分布に間引き処理を行うステップをさらに備え、
前記類似度算出ステップは、前記第１の画像と前記第２の画像のそれぞれの、前記間引き処理後の前記特徴分布の類似度を算出する
請求項１に記載のプログラム。
【請求項３】
前記フィルタ処理には、低域通過型のフィルタを用いる
請求項１に記載のプログラム。
【請求項４】
前記フィルタ処理には、前記精細ヒストグラムの頻度軸を非線形に圧縮するフィルタを用いる
請求項１に記載のプログラム。
【請求項５】
前記類似度算出ステップは、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の形状が最もよく一致するように、サンプルの対応関係を決定し、
前記対応関係で対応するサンプルどうしを比較することにより、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する
ステップを備える請求項１に記載のプログラム。
【請求項６】
画像のカットチェンジを検出する検出方法において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、
前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出し、
前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する
ステップを備える検出方法。
【請求項７】
画像のカットチェンジを検出する検出装置において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段と、
前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出する特徴分布算出手段と、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する類似度算出手段と、
前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する判定手段と
を備える検出装置。
【請求項８】
画像の類似度を算出する画像処理をコンピュータに実行させるプログラムにおいて、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、
前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する
ステップを備えるプログラム。
【請求項９】
画像の類似度を算出する画像処理方法において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、
前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する
ステップを備える画像処理方法。
【請求項１０】
画像の類似度を算出する画像処理装置において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段と、
前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出する特徴分布算出手段と、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する類似度算出手段と
を備える画像処理装置。
【請求項１１】
画像のカットをグルーピングする画像処理をコンピュータに実行させるプログラムにおいて、
入力された画像の境界がカットチェンジであるかを検出し、
検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムを生成し、
前記第１のカットと前記第２のカットの前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出し、
前記第１のカットを構成する各画像の前記特徴分布をそれぞれ積算するとともに、前記第２のカットを構成する各画像の前記特徴分布をそれぞれ積算し、
前記第１のカットの積算された前記特徴分布と、前記第２のカットの積算された前記特徴分布との類似度を算出し、
前記類似度に基づいて、前記第１のカットと前記第２のカットをグルーピングする
ステップを備えるプログラム。
【請求項１２】
前記カットチェンジを検出する検出ステップは、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、
前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出し、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出し、
前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する
ステップを備え、
前記第１のカットと前記第２のカットは、前記カットチェンジで区切られたカットである
請求項１１に記載のプログラム。
【請求項１３】
画像のカットをグルーピングする画像処理方法において、
入力された画像の境界がカットチェンジであるかを検出し、
検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムを生成し、
前記第１のカットと前記第２のカットの前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出し、
前記第１のカットを構成する各画像の前記特徴分布をそれぞれ積算するとともに、前記第２のカットを構成する各画像の前記特徴分布をそれぞれ積算し、
前記第１のカットの積算された前記特徴分布と、前記第２のカットの積算された前記特徴分布との類似度を算出し、
前記類似度に基づいて、前記第１のカットと前記第２のカットをグルーピングする
ステップを備える画像処理方法。
【請求項１４】
画像のカットをグルーピングする画像処理装置において、
入力された画像の境界がカットチェンジであるかを検出する検出手段と、
検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段と、
前記第１のカットと前記第２のカットの前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出する特徴分布算出手段と、
前記第１のカットを構成する各画像の前記特徴分布をそれぞれ積算するとともに、前記第２のカットを構成する各画像の前記特徴分布をそれぞれ積算する特徴分布積算手段と、
前記第１のカットの積算された前記特徴分布と、前記第２のカットの積算された前記特徴分布との類似度を算出する類似度算出手段と、
前記類似度に基づいて、前記第１のカットと前記第２のカットをグルーピングするグルーピング手段と
を備える画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム、検出方法、検出装置、画像処理方法、及び画像処理装置に関し、特に、カットチェンジの検出を高精度に行うことができるようにするプログラム、検出方法、検出装置、画像処理方法、及び画像処理装置に関する。
【背景技術】
【０００２】
画像からカットチェンジを検出する処理は、画像の分析、符号化、検索等を行う場合に有用である。
【０００３】
ここで、カットとは、空間的に連続するひとまとまりの画像区間（画像クリップ）を意味し、カットチェンジは、カットの切り替え点、すなわち、時間的若しくは空間的に不連続な画像クリップどうしが連結された境界である画像の変化点のことを意味する。
【０００４】
なお、カットチェンジは、ショットチェンジ、シーンチェンジ、画像変化点等と称される場合があるが、本明細書においては、カットチェンジと称する。
【０００５】
ところで、従来のカットチェンジの検出方法として、統計量差分法、画素差分法、符号化データ法、エッジ法等が知られているが、最も精度がよいと認識されているのは、ヒストグラム差分法である。
【０００６】
ヒストグラム差分法においては、ヒストグラムの差分値が用いられる。
【０００７】
ここで、ヒストグラムは、あるフレームの画像の各ピクセルを、その輝度または色の画素値に対応して、適当な階調数（一般には、16乃至64階調がよく用いられる）に分割された各要素（ビン）に投票することで、その画像の輝度または色の頻度分布を求めたものである。
【０００８】
ヒストグラム差分法には、単純ヒストグラム差分法と分割ヒストグラム差分法がある。
【０００９】
単純ヒストグラム差分法においては、処理対象とする、例えば２フレームの画像のそれぞれのヒストグラムどうしの違いが評価量として算出される（例えば、非特許文献１参照）。
【００１０】
また、単純ヒストグラム差分法においては、一般に、ヒストグラムどうしの違いとして、ヒストグラムの同じビンどうしの差分値のヒストグラム全体に関する絶対和（以下、適宜、ヒストグラム差分絶対和という）が評価量として算出される。
【００１１】
分割ヒストグラム差分法においては、処理対象とする、例えば２フレームの画像のそれぞれの画像全体が所定数のブロック（例えば、非特許文献１では、１６個のブロック）に分割され、各ブロックのヒストグラムどうしの違いが求められ、そのヒストグラムどうしの違いが小さい方から所定数のブロックのみが、評価量の算出に用いられる（例えば、非特許文献１及び２参照）。
【００１２】
ヒストグラム差分法（単純ヒストグラム差分法及び分割ヒストグラム差分法）を用いた場合、輝度の微小変動が、カットチェンジと誤って判定されてしまうおそれがある。
【００１３】
次に、図１乃至図３を参照して、ヒストグラム差分法を用いた場合の輝度の微小変動とヒストグラムの関係について説明する。
【００１４】
図１は、カットチェンジが正しく検出される場合のヒストグラムの変化を示している。
【００１５】
図１において、フレームＦ３１乃至Ｆ３３は、時間的に隣接する一連の画像であり、フレームＦ３１から順番に２フレームずつの画像が、カットチェンジを検出する処理対象とされる。すなわち、最初に、フレームＦ３１とフレームＦ３２が処理対象とされ、次に、フレームＦ３２とフレームＦ３３が処理対象とされる。
【００１６】
また、ヒストグラムＨ３１乃至Ｈ３３は、それぞれフレームＦ３１乃至Ｆ３３の画像全体に関する輝度のヒストグラムである。
【００１７】
図１において、フレームＦ３１とフレームＦ３２の間の画像の変化は、主に、撮影対象としての人の移動の分なので、ヒストグラムＨ３１とヒストグラムＨ３２の分布はほぼ一致している。
【００１８】
この場合、ヒストグラムＨ３１とヒストグラムＨ３２の違いとして、例えば、ヒストグラムＨ３１とヒストグラムＨ３２のヒストグラム差分絶対和を計算すると、そのヒストグラム差分絶対和は十分に小さくなる。したがって、ヒストグラムＨ３１とヒストグラムＨ３２の間の違いは十分に小さいので、フレームＦ３１とフレームＦ３２の間の画像の変化は、カットチェンジではないと正しく判定することができる。
【００１９】
これに対して、フレームＦ３２とフレームＦ３３の間では、撮影対象が全く異なっている（前者は人であるのに対して後者は山である）ので、ヒストグラムＨ３２とヒストグラムＨ３３の間で、ヒストグラムが大きく変化している。
【００２０】
この場合、ヒストグラムＨ３２とヒストグラムＨ３３の間の違いとして、例えば、ヒストグラムＨ３２とヒストグラムＨ３３のヒストグラム差分絶対和を計算すると、そのヒストグラム差分絶対和は十分に大きく、したがって、ヒストグラムＨ３２とヒストグラムＨ３３の間の違いは十分に大きいので、フレームＦ３２とフレームＦ３３の間の画像の変化は、カットチェンジと正しく判定することができる。
【００２１】
図２は、輝度の微小変動が生じた場合のヒストグラムの変化を示している。
【００２２】
図２において、フレームＦ４１乃至Ｆ４５は、時間的に隣接する一連の画像であり、フレームＦ４１から順番に２つずつの画像がカットチェンジを検出する処理対象とされる。すなわち、最初に、フレームＦ４１とフレームＦ４２が処理対象とされ、次に、フレームＦ４２とフレームＦ４３が処理対象とされる。以下、同様に、２フレームずつの画像が処理対象とされる。
【００２３】
また、ヒストグラムＨ４１乃至Ｈ４５は、それぞれフレームＦ４１乃至Ｆ４５の画像全体に関する輝度のヒストグラムである。
【００２４】
フレームＦ４１乃至Ｆ４５は、例えば、それぞれ単色の画像であり、さらに、各画像の輝度は画像全体で同じである。
【００２５】
図２において、ヒストグラムのビンの数は64個、ビンの幅は4階調である。また、ビンの分割境界は、例えば、76階調と77階調の間、80階調と81階調の間等とされている。そして、フレームＦ４１乃至Ｆ４５には、73，75，77，79，81と、微小な輝度変動が生じており、画像全体の輝度がわずかずつ増加している。また、フレームＦ４１乃至Ｆ４５のそれぞれの画像全体の輝度は同じであるので、ヒストグラムＨ４１乃至Ｈ４５のそれぞれは、１つのビンに頻度が集中している。ヒストグラムの、あるビンに頻度が集中している部分を、以下、適宜、ヒストグラムピークという。
【００２６】
フレームＦ４１乃至Ｆ４５の画像の変化、つまり、輝度の微小変動は、カット内の画像の変化であり、カットチェンジではない。
【００２７】
フレームＦ４３は、フレームＦ４２に比べて、画像全体の輝度が75から77に微かではあるが増えており、画像全体の輝度がビンの分割境界の１つの76と77の間を跨いだので、ヒストグラムＨ４３は、ヒストグラムＨ４２と比べて、ヒストグラムピークが右隣のビンに移動するように、大きく変化している。そして、例えば、ヒストグラムＨ４２とヒストグラムＨ４３のヒストグラム差分絶対和を計算すると、そのヒストグラム差分絶対和は、ヒストグラムの違いとしては最大となるので、フレームＦ４２とフレームＦ４３の間の切り替え点がカットチェンジと誤検出されてしまう。
【００２８】
同様に、フレームＦ４５は、フレームＦ４４に比べて、画像全体の輝度が79から81に微かではあるが増えており、画像全体の輝度がビンの分割境界の１つの80と81の間を跨いだので、ヒストグラムＨ４５は、ヒストグラムＨ４４と比べて、ヒストグラムピークが右隣のビンに移動するように変化している。そして、例えば、ヒストグラムＨ４４とヒストグラムＨ４５のヒストグラム差分絶対和を計算すると、そのヒストグラム差分絶対和は、ヒストグラムの違いとしては最大となるので、フレームＦ４４とフレームＦ４５の間の切り替え点がカットチェンジと誤検出されてしまう。
【００２９】
かかるカットチェンジの誤検出は、上述したように、特に、単色の画像を処理する場合に典型的に観測されるが、複数色の画像である一般の画像を処理する場合であっても、輝度または色の微小変動に伴って、輝度または色のヒストグラムのビンの分割境界を跨ぐピクセルの数が大きく変化する場合に観測される。このように、処理対象とする２フレームの画像の間の輝度または色の微小変動に伴って、その２つの画像のヒストグラムどうしの違いのブレが生じることは、カットチェンジの検出精度を下げる原因の１つとなっている。
【００３０】
特許文献１には、処理対象とする２つの画像どうしの画像全体の輝度の平均値を一致させる処理を行うことにより、２つの画像のそれぞれのヒストグラムの全体を輝度の軸の方向にシフトさせ（以下、適宜、ヒストグラムシフトという）、ヒストグラムシフト後のヒストグラムどうしの違いを計算する方法が提案されている。この方法を、例えば、図２のような比較的単純な例に採用すると、ヒストグラムシフト後のヒストグラムどうしがほぼ同じ形状、位置となるので、ヒストグラムどうしの違いのブレは吸収され、誤検出が抑制される。
【００３１】
しかし、図３に示されるような場合、誤検出が発生する。すなわち、図３は、画像の左半分と右半分のそれぞれに輝度の微小変動が生じた場合のヒストグラムの変化を示している。
【００３２】
図３において、フレームＦ５１とフレームＦ５２は、時間的に隣接する処理対象とする２つの画像であり、ヒストグラムＨ５１とヒストグラムＨ５２は、それぞれフレームＦ５１とフレームＦ５２の画像全体に関する輝度のヒストグラムである。
【００３３】
フレームＦ５１及びフレームＦ５２の左半分と右半分の領域は、それぞれ単色の画像となっている。
【００３４】
図３において、ヒストグラムのビンの数は64個、ビンの幅は4階調である。また、ビンの分割境界は、例えば、76階調と77階調の間、80階調と81階調の間等とされている。
【００３５】
図３において、フレームＦ５１の左半分と右半分のそれぞれの輝度は、75と81であり、フレームＦ５２の左半分と右半分のそれぞれの輝度は、77と83である。したがって、ヒストグラムＨ５１には、75と81を含むビンのそれぞれにヒストグラムピークがあり、また、フレームＦ５２には、77と83を含むビンのそれぞれにヒストグラムピークがある。
【００３６】
フレームＦ５１とフレームＦ５２の間の画像の変化、つまり、輝度の微小変動は、カット内の画像の変化であり、したがって、フレームＦ５１とフレームＦ５２の境界は、カットチェンジではない。
【００３７】
フレームＦ５２の左半分は、フレームＦ５１の左半分に比べて、画像全体の輝度が75から77に微かではあるが増えており、画像左半分の輝度がビンの分割境界の１つの76と77の間を跨いでいる。一方、フレームＦ５２の右半分は、フレームＦ５１の右半分に比べて、画像全体の輝度が81から83に微かではあるが増えているが、ビンの分割境界を跨いでいない。したがって、ヒストグラムＨ５１とヒストグラムＨ５２の間では、左のヒストグラムピークのみが分割境界である76と77の間を跨いで右隣のビンに移動している。その結果、例えば、ヒストグラムＨ５１とヒストグラムＨ５２のヒストグラム差分絶対和を計算した場合、そのヒストグラム差分絶対和が所定の閾値以上になると、フレームＦ５１とフレームＦ５２の間の画像の変化がカットチェンジと誤検出されてしまう。
【００３８】
このように輝度の微小変動に伴ってヒストグラムの形状が変化する場合には、ヒストグラムシフトだけでは、ヒストグラムどうしの違いのブレを吸収することは難しい。つまり、画像の変化が図２に示した場合より少し複雑化するだけで、ヒストグラムシフトが有効に機能しなくなってしまう。
【００３９】
そこで、特許文献２には、ヒストグラムの生成時に、投票をするビンだけでなく、そのビンに隣接するビンにも所定の割合で投票する方法が提案されている。
【００４０】
かかる方法を用いた場合、画像全体の輝度の変動量が、ヒストグラムのビンの幅に対して十分に小さい場合は、ヒストグラムどうしの違いのブレを緩和させる効果を期待できるが、画像全体の輝度の変動量が、ヒストグラムのビンの幅に対して無視できないほどである場合は、隣接するビンへの投票だけでは、ヒストグラムどうしの違いのブレを吸収できなくなってしまう。
【００４１】
【非特許文献１】情報処理学会論文誌，長坂晃朗，田中譲，１９９２年４月，Vol.33，No.4，P.543-550
【非特許文献２】Comparison of Video Shot Boundary Detection Techniques, John S. Boreczky, Lawrence A. Rowe. Storage and Retrieval for Image and Video Databases (SPIE) (1996) p170-179
【特許文献１】特開２００６−１２１２７４号公報
【特許文献２】特開２００４−２８２３１８号公報
【発明の開示】
【発明が解決しようとする課題】
【００４２】
以上のように、ヒストグラム差分法では、輝度または色の微小変動に伴って生じるカットチェンジの誤検出を減らすことが困難であった。
【００４３】
本発明は、このような状況に鑑みてなされたものであり、輝度または色の微小変動に伴って生じるカットチェンジの誤検出を減らすことができるようにするものである。
【課題を解決するための手段】
【００４４】
本発明の第１の側面のプログラムまたは検出方法は、画像のカットチェンジを検出する検出処理をコンピュータに実行させるプログラムまたは検出方法において、第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出し、前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定するステップを備える。
【００４５】
本発明の第１の側面のプログラムには、前記特徴分布に間引き処理を行うステップをさらに設け、前記類似度算出ステップには、前記第１の画像と前記第２の画像のそれぞれの、前記間引き処理後の前記特徴分布の類似度を算出させることができる。
【００４６】
前記類似度算出ステップには、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の形状が最もよく一致するように、サンプルの対応関係を決定し、前記対応関係で対応するサンプルどうしを比較することにより、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出するステップを設けることができる。
【００４７】
本発明の第１の側面の検査装置は、画像のカットチェンジを検出する検出装置において、第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段と、前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出する特徴分布算出手段と、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する類似度算出手段と、前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する判定手段とを備える。
【００４８】
本発明の第２の側面のプログラムまたは画像処理方法は、画像の類似度を算出する画像処理をコンピュータに実行させるプログラムまたは画像処理方法において、第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出するステップを備える。
【００４９】
本発明の第２の側面の画像処理装置は、画像の類似度を算出する画像処理装置において、第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段と、前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出する特徴分布算出手段と、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する類似度算出手段とを備える。
【００５０】
本発明の第３の側面のプログラムまたは画像処理方法は、画像のカットをグルーピングする画像処理をコンピュータに実行させるプログラムまたは画像処理方法において、入力された画像の境界がカットチェンジであるかを検出し、検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムを生成し、前記第１のカットと前記第２のカットの前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出し、前記第１のカットを構成する各画像の前記特徴分布をそれぞれ積算するとともに、前記第２のカットを構成する各画像の前記特徴分布をそれぞれ積算し、前記第１のカットの積算された前記特徴分布と、前記第２のカットの積算された前記特徴分布との類似度を算出し、前記類似度に基づいて、前記第１のカットと前記第２のカットをグルーピングするステップを備える。
【００５１】
前記カットチェンジを検出する検出ステップには、第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し、前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出し、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出し、前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定するステップを設け、前記第１のカットと前記第２のカットは、前記カットチェンジで区切られたカットとすることができる。
【００５２】
本発明の第３の側面の画像処理装置は、画像のカットをグルーピングする画像処理装置において、入力された画像の境界がカットチェンジであるかを検出する検出手段と、検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段と、前記第１のカットと前記第２のカットの前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出する特徴分布算出手段と、前記第１のカットを構成する各画像の前記特徴分布をそれぞれ積算するとともに、前記第２のカットを構成する各画像の前記特徴分布をそれぞれ積算する特徴分布積算手段と、前記第１のカットの積算された前記特徴分布と、前記第２のカットの積算された前記特徴分布との類似度を算出する類似度算出手段と、前記類似度に基づいて、前記第１のカットと前記第２のカットをグルーピングするグルーピング手段とを備える。
【００５３】
本発明の第１の側面においては、第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムが生成され、精細ヒストグラムに対してフィルタ処理を施して特徴分布が算出される。また、第１の画像と第２の画像のそれぞれの特徴分布の類似度が算出され、特徴分布の類似度に基づいて、第１の画像と第２の画像の境界がカットチェンジであるかが判定される。
【００５４】
本発明の第２の側面においては、第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムが生成され、第１の画像と第２の画像の精細ヒストグラムに対してフィルタ処理を施して特徴分布が算出される。そして、第１の画像と第２の画像のそれぞれの特徴分布の類似度が算出される。
【００５５】
本発明の第３の側面においては、入力された画像の境界がカットチェンジであるかが検出され、検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムが生成され、第１のカットと第２のカットの精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布が算出される。また、第１のカットを構成する各画像の特徴分布がそれぞれ積算されるとともに、第２のカットを構成する各画像の特徴分布がそれぞれ積算され、第１のカットの積算された特徴分布と、第２のカットの積算された特徴分布との類似度が算出される。そして、類似度に基づいて、第１のカットと第２のカットがグルーピングされる。
【発明の効果】
【００５６】
本発明の第１の側面によれば、カットチェンジの誤検出を減らすことができる。特に、輝度または色の微小変動に伴って生じるカットチェンジの誤検出を減少させることができる。
【００５７】
本発明の第２の側面によれば、画像どうしの類似度を求めることができる。特に、輝度または色の微小変動が生じても、画像どうしの類似度を求めることができる。
【００５８】
本発明の第３の側面によれば、簡単かつ確実にカットどうしをグルーピングすることができる。特に、輝度または色の微小変動が生じたとしても、簡単かつ確実にカットどうしをグルーピングすることができる。
【発明を実施するための最良の形態】
【００５９】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、明細書又は図面に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、明細書又は図面に記載されていることを確認するためのものである。従って、明細書又は図面中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００６０】
本発明の第１の側面のプログラムまたは検出方法は、
画像のカットチェンジを検出する検出処理をコンピュータに実行させるプログラムまたは検出方法において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し（例えば、図６のステップＳ４０１）、
前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し（例えば、図６のステップＳ４０２）、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出し（例えば、図６のステップＳ４０４）、
前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する（例えば、図６のステップＳ４０５）
ステップを備える。
【００６１】
本発明の第１の側面のプログラムには、
前記特徴分布に間引き処理を行う（例えば、図６のステップＳ４０３）ステップをさらに設け、
前記類似度算出ステップには、前記第１の画像と前記第２の画像のそれぞれの、前記間引き処理後の前記特徴分布の類似度を算出させることができる。
【００６２】
前記類似度算出ステップには、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の形状が最もよく一致するように、サンプルの対応関係を決定し（例えば、図１１のステップＳ４２１）、
前記対応関係で対応するサンプルどうしを比較することにより、前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する（例えば、図１１のステップＳ４２２）
ステップを設けることができる。
【００６３】
本発明の第１の側面の検査装置は、
画像のカットチェンジを検出する検出装置（例えば、図４のパーソナルコンピュータ１）において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段（図５の精細ヒストグラム生成部４０１）と、
前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出する特徴分布算出手段（例えば、図５の特徴分布算出部４０２）と、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する類似度算出手段（例えば、図５の類似度算出部４０４）と、
前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する判定手段（例えば、図５の判定部４０５）と
を備える。
【００６４】
本発明の第２の側面のプログラムまたは画像処理方法は、
画像の類似度を算出する画像処理をコンピュータに実行させるプログラムまたは画像処理方法において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し（例えば、図１５のステップＳ４３１）、
前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出し（例えば、図１５のステップＳ４３２）、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する（例えば、図１５のステップＳ４３４）
ステップを備える。
【００６５】
本発明の第２の側面の画像処理装置は、
画像の類似度を算出する画像処理装置（例えば、図１４の類似度算出装置４６１）において、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段（例えば、図１４の精細ヒストグラム生成部４７１及び精細ヒストグラム生成部４７４）と、
前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してフィルタ処理を施して特徴分布を算出する特徴分布算出手段（例えば、図１４の特徴分布算出部４７２及び特徴分布算出部４７５）と、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出する類似度算出手段（例えば、図１４の類似度算出部４７７）と
を備える。
【００６６】
本発明の第３の側面のプログラムまたは画像処理方法は、
画像のカットをグルーピングする画像処理をコンピュータに実行させるプログラムまたは画像処理方法において、
入力された画像の境界がカットチェンジであるかを検出し（例えば、図１８のステップＳ４７１乃至Ｓ４７７）、
検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムを生成し（例えば、図１９のステップＳ４７８）、
前記第１のカットと前記第２のカットの前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出し（例えば、図１９のステップＳ４７９）、
前記第１のカットを構成する各画像の前記特徴分布をそれぞれ積算するとともに、前記第２のカットを構成する各画像の前記特徴分布をそれぞれ積算し（例えば、図１９のステップＳ４８１）、
前記第１のカットの積算された前記特徴分布と、前記第２のカットの積算された前記特徴分布との類似度を算出し（例えば、図１９のステップＳ４８３）、
前記類似度に基づいて、前記第１のカットと前記第２のカットをグルーピングする（例えば、図１９のステップＳ４８４）
ステップを備える。
【００６７】
前記カットチェンジを検出する検出ステップには、
第１の画像と第２の画像のそれぞれの輝度または色の精細ヒストグラムを生成し（例えば、図１８のステップＳ４７１）、
前記第１の画像と前記第２の画像の前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出し（例えば、図１８のステップＳ４７２）、
前記第１の画像と前記第２の画像のそれぞれの前記特徴分布の類似度を算出し（例えば、図１８のステップＳ４７４）、
前記特徴分布の類似度に基づいて、前記第１の画像と前記第２の画像の境界がカットチェンジであるかを判定する（例えば、図１８のステップＳ４７５乃至Ｓ４７７）
ステップを設け、
前記第１のカットと前記第２のカットは、前記カットチェンジで区切られたカットとすることができる。
【００６８】
本発明の第３の側面の画像処理装置は、
画像のカットをグルーピングする画像処理装置（例えば、図１７の画像グルーピング装置５０１）において、
入力された画像の境界がカットチェンジであるかを検出する検出手段（例えば、図１７のカットチェンジ検出部５１４）と、
検出された第１のカットと第２のカットのそれぞれを構成する各画像の輝度または色の精細ヒストグラムを生成する精細ヒストグラム生成手段（例えば、図１７の精細ヒストグラム生成部５１１）と、
前記第１のカットと前記第２のカットの前記精細ヒストグラムに対してそれぞれフィルタ処理を施して特徴分布を算出する特徴分布算出手段（例えば、図１７の特徴分布算出部５１２）と、
前記第１のカットを構成する各画像の前記特徴分布をそれぞれ積算するとともに、前記第２のカットを構成する各画像の前記特徴分布をそれぞれ積算する特徴分布積算手段（例えば、図１７の特徴分布統合部５１５）と、
前記第１のカットの積算された前記特徴分布と、前記第２のカットの積算された前記特徴分布との類似度を算出する類似度算出手段（例えば、図１７の類似度算出部５１７）と、
前記類似度に基づいて、前記第１のカットと前記第２のカットをグルーピングするグルーピング手段（例えば、図１７のグルーピング部５１８）と
を備える。
【００６９】
以下、図面を参照して本発明を適用した実施の形態について説明する。
【００７０】
図４は、本発明を適用した検出装置の一実施の形態の構成例を示すブロック図である。
【００７１】
図４において、検出装置としてのパーソナルコンピュータ１は、CPU（Central Processing Unit）２１，ROM（Read Only Memory）２２，RAM（Random Access Memory）２３、バス２４、入出力インタフェース２５、入力部２６、出力部２７、記憶部２８、通信部２９、ドライブ３０、及びリムーバブルメディア３１から構成される。
【００７２】
バス２４には、CPU２１、ROM２２、RAM２３、および入出力インタフェース２５が接続され、入出力インタフェース２５には、バス２４、入力部２６、出力部２７、記憶部２８、通信部２９、及びドライブ３０が接続されている。
【００７３】
CPU２１は、ROM２２または記憶部２８に記憶されたプログラムに従って各種の処理を実行する。また、CPU２１は、入力部２６から入力される指令に対応して各種の処理を実行し、また、処理の結果を出力部２７に出力する。
【００７４】
ROM２２は、CPU２１が実行するプログラム等を記憶する。
【００７５】
RAM２３は、CPU２１が実行するプログラムやデータなどを適宜記憶する。また、RAM２３は、例えば、外部から入力される画像を一時的に記憶するバッファを有する。
【００７６】
入力部２６は、キーボード、マウス、マイクロホン等で構成される。
【００７７】
出力部２７は、ディスプレイ、スピーカ等で構成される。
【００７８】
記憶部２８は、例えばハードディスクからなり、CPU２１が実行するプログラムや各種のデータを記憶する。
【００７９】
通信部２９は、インターネットやローカルエリアネットワークなどのネットワークを介して外部の装置と通信する。
【００８０】
なお、通信部２９を介してプログラムが取得され、記憶部２８に記憶されてもよい。
【００８１】
ドライブ３０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア３１が装着されたとき、それらを駆動し、そこに記録されているプログラムやデータなどを取得する。取得されたプログラムやデータは、必要に応じて記憶部２８に転送され、記憶される。
【００８２】
コンピュータにインストールされ、コンピュータによって実行可能な状態とされるプログラムを格納するプログラム記録媒体は、図４に示すように、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)を含む）、光磁気ディスク、もしくは半導体メモリなどよりなるパッケージメディアであるリムーバブルメディア３１、ROM２２や、記憶部２８を構成するハードディスクなどにより構成される。プログラム記録媒体へのプログラムの格納は、必要に応じてルータ、モデムなどのインタフェースである通信部２９を介して、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の通信媒体を利用して行われる。
【００８３】
また、パーソナルコンピュータ１のCPU２１は、ROM２２または記憶部２８に記憶されたプログラムを実行することにより、カットチェンジを検出するカットチェンジ検出装置として機能する。
【００８４】
図５は、パーソナルコンピュータ１のソフトウェアにより構成されるカットチェンジ検出装置５１の実施の形態の構成を示すブロック図である。
【００８５】
図５において、カットチェンジ検出装置５１は、外部からの画像を、例えば、RAM２３のバッファから読み出すことにより入力し、カットチェンジ検出処理を行う。
【００８６】
図５において、カットチェンジ検出装置５１は、精細ヒストグラム生成部４０１、特徴分布算出部４０２、間引き処理部４０３、類似度算出部４０４、及び判定部４０５から構成される。
【００８７】
精細ヒストグラム生成部４０１には、カットチェンジ検出装置５１に入力された画像が供給される。精細ヒストグラム生成部４０１は、そこに供給される画像のヒストグラムとして、できるだけ細かい分割幅の、例えば、256階調の場合には1階調の分割幅のヒストグラムである精細ヒストグラムを生成し、特徴分布算出部４０２に供給する。
【００８８】
特徴分布算出部４０２は、精細ヒストグラム生成部４０１から供給される精細ヒストグラムにフィルタ処理を施し、その結果得られる特徴分布を、間引き処理部４０３に供給する。特徴分布算出部４０２によるフィルタ処理には、適切に設計された低域通過型フィルタを用いることが望ましいが、非線形な応答を持つフィルタを用いてもよい。
【００８９】
間引き処理部４０３は、特徴分布算出部４０２から供給される特徴分布に対して、その特徴分布を忠実に再現する（サンプリング定理で許される）範囲のサンプリング周波数に対応する間隔で間引きを行う間引き処理を施し、その結果得られる間引き処理後の特徴分布を類似度算出部４０４に供給する。
【００９０】
なお、間引き処理部４０３による間引き処理は、主に、データ量を削減して演算量や記憶容量を節約するための処理であり、必要がなければ省略してもよい。
【００９１】
類似度算出部４０４は、間引き処理部４０３から供給される間引き処理後の第１の画像の特徴分布と間引き処理後の第２の画像の特徴分布とを比較し、その間引き処理後の第１の画像の特徴分布と間引き処理後の第２の画像の特徴分布の類似度を算出する。
【００９２】
特徴分布どうしの類似度は、通常のヒストグラム差分法と同様に、第１の画像の特徴分布と、例えば、第１の画像より前のフレームの第２の画像の特徴分布の間の距離を求め、その距離が小さいほど特徴分布どうしの類似度が高くなるようにすればよい。
【００９３】
類似度算出部４０４は、この類似度を判定部４０５に供給する。
【００９４】
判定部４０５は、類似度算出部４０４から供給される類似度が、その類似度に対して設定された適切な閾値に対して大きいかまたは小さいかを判定する閾値判定を行い、カットチェンジであるかを判定する。
【００９５】
次に、図６のフローチャートを参照して、図５のカットチェンジ検出装置５１によるカットチェンジ検出処理について説明する。
【００９６】
図５の精細ヒストグラム生成部４０１には、カットチェンジ検出装置５１に入力された画像が供給される。ステップＳ４０１において、精細ヒストグラム生成部４０１は、そこに供給される画像の精細ヒストグラムを生成し、特徴分布算出部４０２に供給する。
【００９７】
いま、図７Ａに示されるように、フレームＦ２１１とフレームＦ２１２が処理対象の画像であるとする。これらの画像は、図３のフレームＦ５１とフレームＦ５２と同じ輝度の分布を持つ画像となっている。すなわち、フレームＦ２１１の画像の左半分は75、右半分は81の輝度を有し、フレームＦ２１２の画像の左半分は77、右半分は83の輝度を有している。図７Ｂの精細ヒストグラムＨ２１１と精細ヒストグラムＨ２１２は、それぞれ、フレームＦ２１１とフレームＦ２１２の画像から生成された精細ヒストグラムである。精細ヒストグラムＨ２１１は、輝度75，81に、精細ヒストグラムＨ２１２は、輝度77，83にそれぞれヒストグラムピークを有している。
【００９８】
図７の精細ヒストグラムＨ２１１は、入力される画像がN階調の画像であれば、ビンの分割数をN段階とすることが望ましい。その場合、後述するヒストグラム生成の演算の不連続性は、画像がそもそも有する量子化レベルに留まり、新たな誤差が導入されることがない。また、演算量や記憶容量を節約する観点からすると、ビンの分割数をN段階未満とすることも可能ではあるが、分割が粗ければ粗い程、一般のヒストグラム差分法と同様に、ヒストグラム生成の演算の不連続性によって生じる誤差が導入されてしまう。
【００９９】
ステップＳ４０２において、特徴分布算出部４０２は、精細ヒストグラム生成部４０１から供給される精細ヒストグラムにフィルタ処理を施し、その結果得られる特徴分布を、間引き処理部４０３に供給する。
【０１００】
図７Ｃの特徴分布Ｃ２１１は、精細ヒストグラムＨ２１１にフィルタ処理を施すことによって得られたものであり、また、特徴分布Ｃ２１２は、精細ヒストグラムＨ２１２にフィルタ処理を施すことによって得られたものである。
【０１０１】
フィルタ処理には、図８に示すような低域通過型フィルタを用いるのが望ましい。低域通過型フィルタを用いることにより、隣接のビンに投票する方法を用いる場合のようにヒストグラム生成の演算の不連続性による新たな誤差を導入することなく、輝度の微小変動によるヒストグラムの違いのブレを吸収することができる。
【０１０２】
また、低域通過型フィルタによるフィルタ処理によって得られる特徴分布は、ヒストグラムに比べて高周波成分が低減されているので、サンプリング定理に従う範囲で間引き処理を行うことにより、以降の演算量を低く抑えつつ、フィルタ処理または間引き処理による誤差を導入しないようにできるか、あるいは、非常に少ない誤差に抑えることができる。
【０１０３】
したがって、上述した方法を採用することにより、ヒストグラム差分法が本質的に有するヒストグラム生成の演算の不連続性による誤差が排除された特徴分布を用いて、対象画像どうしの類似度を算出することができるので、より高精度のカットチェンジ検出を行うことができる。
【０１０４】
特徴分布算出部４０２によるフィルタ処理には、上述した低域通過型フィルタの他、非線形応答を持つフィルタである非線形フィルタを用いることもできる。
【０１０５】
例えば、非線形フィルタには、特徴分布の対数を取ることにより、特徴値軸を対数的に圧縮または伸張するものを用いることもできる。
【０１０６】
図９は、特定の輝度に特徴分布が集中している画像に、上述の非線形フィルタによる処理を施した場合の特徴分布を示している。
【０１０７】
図９Ａはフィルタ処理される画像を示し、図９Ｂは、その画像に線形フィルタによる処理を施した場合の特徴分布を示し、図９Ｃは、その画像に非線形フィルタによる処理を施した場合の特徴分布を示す。
【０１０８】
図９Ａの原画像は、単純色の物体の前景が、複雑な背景の前に位置する画像である。
【０１０９】
図９Ｂの特徴分布では、その単純色の物体の輝度に特徴分布が集中している。この場合、前述したように、単純色の物体の輝度の変動が、カットチェンジの検出結果に過度に支配的となってしまう。
【０１１０】
これに対して、図９Ｃの特徴分布では、非線形なフィルタリングによって、大きすぎる輝度が抑えられるので、特定の輝度に特徴分布が集中するのを抑制することができる。
【０１１１】
ステップＳ４０３において、間引き処理部４０３は、特徴分布算出部４０２から供給される特徴分布に対して、例えば、４階調ごとに間引く間引き処理を施し、その結果得られる間引き処理後の特徴分布を類似度算出部４０４に供給する。図７Ｃの特徴分布Ｃ２１１と特徴分布Ｃ２１２を間引き処理することで、それぞれ図７Ｃの特徴分布Ｄ２１１と特徴分布Ｄ２１２が得られる。
【０１１２】
ステップＳ４０４において、類似度算出部４０４は、間引き処理部４０３から供給される間引き処理後の第１の画像の特徴分布と間引き処理後の第２の画像（前フレームの画像）の特徴分布とを比較し、その間引き処理後の第１の画像の特徴分布と間引き処理後の第２の画像の特徴分布の類似度を算出するための類似度算出処理を実行する。
【０１１３】
この類似度算出処理を実行するため、図５の類似度算出部４０４は、図１０に示されるように構成される。すなわち、類似度算出部４０４は、対応サンプル決定部４３１及び類似度決定部４３２から構成される。
【０１１４】
対応サンプル決定部４３１は、間引き処理部４０３から供給される、第１の画像の間引き処理後の特徴分布と第２の画像の間引き処理後の特徴分布を比較し、第１の画像と第２の画像のそれぞれの特徴分布どうしの形状が最もよく一致するようにサンプルどうしの対応関係を決定し、その対応関係を表す対応関係情報を類似度決定部４３２に供給する。
【０１１５】
類似度決定部４３２は、対応サンプル決定部４３１から供給される対応関係情報に基づいて、例えば、第１の画像の特徴分布と第２の画像の特徴分布の距離を求め、その距離が小さいほど高くなる類似度である特徴分布類似度を、判定部４０５に供給する。
【０１１６】
図１１のフローチャートを参照して、図１０の類似度算出部４０４による類似度算出処理について説明する。
【０１１７】
ステップＳ４２１において、対応サンプル決定部４３１は、間引き処理部４０３から供給される、第１の画像の間引き処理後の特徴分布と第２の画像の間引き処理後の特徴分布を比較し、第１の画像と第２の画像のそれぞれの特徴分布どうしの形状が最もよく一致するようにサンプルどうしの対応関係を、図１２に示されるように決定し、その対応関係を表す対応関係情報を類似度決定部４３２に供給する。ここで、サンプルは、特徴分布の要素（ビン）のことを表す。
【０１１８】
図１２の上の図は、第１の画像としてのフレームＦ２３１の特徴分布を示し、図１２の下の図は第２の画像としてのフレームＦ２３２の特徴分布を示す。
【０１１９】
図１２において、フレームＦ２３１の特徴分布とフレームＦ２３２の特徴分布のそれぞれのサンプルを、矢印で示されるように対応付けることで、２つの特徴分布の形状が最もよく一致する状態になる。
【０１２０】
特徴分布どうしの対応関係を求める方法には、例えば、特徴分布どうしの相関を最大とするように求める方法、特徴分布どうしの２乗誤差を最小とするように求める方法、あるいは、特徴分布どうしの重心を一致させるように求める方法等がある。
【０１２１】
あるいは、一般に、輝度の変化によって特徴分布の形状の歪みが発生するため、DP(Dynamic Programming)マッチングの技法等の非線形な方法を用いて、対応関係を決定してもよい。
【０１２２】
ステップＳ４２２において、類似度決定部４３２は、対応サンプル決定部４３１から供給される対応関係情報に基づいて、例えば、第１の画像の特徴分布と第２の画像の特徴分布の距離を求め、その距離が小さいほど高くなる類似度である特徴分布類似度を、判定部４０５に供給する。
【０１２３】
図６に戻って、次に、ステップＳ４０５において、判定部４０５は、類似度算出部４０４から供給される類似度（特徴分布類似度）を、その類似度に対して設定された適切な閾値と比較し、カットチェンジであるかを判定する。
【０１２４】
なお、判定部４０５は、その他、ベイズの定理に従って事象の確率を求めるベイズ識別法や、ニューラルネットワーク法、統計的学習理論を応用したサポートベクターマシン法等の、いわゆる統計的判別法を利用して、カットチェンジであるかを判定するようにしてもよい。
【０１２５】
前述したように、ヒストグラム差分法では、微小な輝度変動が生じたときに、カットチェンジの誤検出が発生するおそれがあったが、その原因は、ヒストグラムを求める際に、ビンの区切りを挟んで不連続な演算を行っていることにある。特許文献２の方法を用いた場合、この演算の不連続性を緩和することができるので、カットチェンジの誤検出をある程度抑制できるが、ビンの区切り自体を解消するには至っていないので、効果が限定的となるのである。これに対して、本実施の形態では、特徴分布の形状が一致するようにサンプルを対応付けるので、ビンの区切りによる影響をより少なくすることができ、したがって、カットチェンジの誤検出を減らすことができる。
【０１２６】
ところで、「写真などの静止画を類似している順に並べたい」という要求、つまり、複数の画像のうちの、１枚の画像と他の１枚の画像の類似度を求め、複数の画像を類似度の高い順に並べたいという要求等があった場合、この１枚の画像と他の１枚の画像としての、例えば、図１３に示される２枚の画像どうしの類似度を定量的に評価する必要がある。
【０１２７】
図１４は、このような場合のために、２枚の画像の類似度を算出する本発明を適用した類似度算出装置の一実施の形態の構成を示すブロック図である。
【０１２８】
図１４において、類似度算出装置４６１は、精細ヒストグラム生成部４７１、特徴分布算出部４７２、間引き処理部４７３、精細ヒストグラム生成部４７４、特徴分布算出部４７５、間引き処理部４７６、及び類似度算出部４７７から構成される。
【０１２９】
図１４において、精細ヒストグラム生成部４７１、特徴分布算出部４７２、及び間引き処理部４７３は、それぞれ図５における精細ヒストグラム生成部４０１、特徴分布算出部４０２、及び間引き処理部４０３と同様に構成される。また、精細ヒストグラム生成部４７４、特徴分布算出部４７５、及び間引き処理部４７６は、それぞれ図５における精細ヒストグラム生成部４０１、特徴分布算出部４０２、及び間引き処理部４０３と同様に構成される。さらに、類似度算出部４７７は図５における類似度算出部４０４と同様に構成される。
【０１３０】
なお、類似度算出部４７７は、間引き処理後の第１の画像の特徴分布を間引き処理部４７３から取得し、また、間引き処理後の第２の画像の特徴分布を、間引き処理部４７６から取得する。そして、類似度算出部４７７は、間引き処理後の第１の画像の特徴分布と間引き処理後の第２の画像の特徴分布の類似度を算出し、第１の画像と第２の画像の類似度である画像類似度として出力する。
【０１３１】
次に、図１５のフローチャートを参照して、図１４の類似度算出装置４６１による静止画像類似度算出処理について説明する。
【０１３２】
精細ヒストグラム生成部４７１と精細ヒストグラム生成部４７４には、外部から入力された画像、すなわち、類似度を計算する処理対象とする第１の画像と第２の画像がそれぞれ供給される。
【０１３３】
ステップＳ４３１において、精細ヒストグラム生成部４７１と精細ヒストグラム生成部４７４は、それぞれそこに供給される第１の画像と第２の画像の精細ヒストグラムを生成し、特徴分布算出部４７２と特徴分布算出部４７５に供給する。
【０１３４】
ステップＳ４３２において、特徴分布算出部４７２と特徴分布算出部４７５は、それぞれ精細ヒストグラム生成部４７１と精細ヒストグラム生成部４７４から供給される第１の画像の精細ヒストグラムと第２の画像の精細ヒストグラムにフィルタ処理を施し、その結果得られる特徴分布を、間引き処理部４７３と間引き処理部４７６に供給する。
【０１３５】
ステップＳ４３３において、間引き処理部４７３と間引き処理部４７６は、特徴分布算出部４７２と特徴分布算出部４７５から供給される第１の画像の特徴分布と第２の画像の特徴分布に対して、間引き処理を施し、その結果得られる間引き処理後の第１の画像の特徴分布と間引き処理後の第２の画像の特徴分布を類似度算出部４７７に供給する。
【０１３６】
ステップＳ４３４において、類似度算出部４７７は、間引き処理後の第１の画像の特徴分布と間引き処理後の第２の画像の特徴分布の類似度を算出し、第１の画像と第２の画像の類似度である画像類似度として出力する。
【０１３７】
以上のようにして、輝度または色の微小変動が生じた場合にも、簡単かつ確実に、画像どうしの類似度を求めることができる。
【０１３８】
画像は、複数のカットどうしが結合されたカットのまとまりと捉えることができる。かかる複数のカットの中には、図１６のカット１とカット３、あるいはカット２とカット５のように、同じ場所や類似したアングルで撮影されたカット等の類似したカットが複数あることがあり、このような類似したカットを自動的にグルーピングしたい場合がある。
【０１３９】
図１７は、このように画像を自動的にグルーピングするための、本発明を適用した画像グルーピング装置の一実施の形態の構成を示すブロック図である。
【０１４０】
図１７において、画像グルーピング装置５０１は、精細ヒストグラム生成部５１１、特徴分布算出部５１２、間引き処理部５１３、カットチェンジ検出部５１４、特徴分布統合部５１５、保存部５１６、類似度算出部５１７、及びグルーピング部５１８から構成される。
【０１４１】
図１７において、精細ヒストグラム生成部５１１、特徴分布算出部５１２、及び間引き処理部５１３は、それぞれ図５における精細ヒストグラム生成部４０１、特徴分布算出部４０２、及び間引き処理部４０３と同様に構成され、カットチェンジ検出部５１４は、図５におけるカットチェンジ検出装置５１と同様に構成される。類似度算出部５１７は、図５における類似度算出部４０４と同様に構成される。
【０１４２】
精細ヒストグラム生成部５１１には、外部から入力された画像が供給される。
【０１４３】
精細ヒストグラム生成部５１１は、そこに供給される画像の精細ヒストグラムを生成し、特徴分布算出部５１２に供給する。特徴分布算出部５１２は、精細ヒストグラム生成部５１１から供給される精細ヒストグラムにフィルタ処理を施し、その結果得られる特徴分布を、間引き処理部５１３に供給する。
【０１４４】
間引き処理部５１３は、特徴分布算出部５１２から供給される特徴分布に対して、所定の間隔で間引きを行う間引き処理を施し、その結果得られる間引き処理後の特徴分布を特徴分布統合部５１５に供給する。
【０１４５】
カットチェンジ検出部５１４には、外部から入力された画像が供給される。カットチェンジ検出部５１４は、図５におけるカットチェンジ検出装置５１と同様に構成される。
【０１４６】
すなわち、カットチェンジ検出部５１４は、そこに供給される画像に所定の処理を施すことによって、カットチェンジを検出する処理対象とする第１の画像と第２の画像の類似度を計算し、その第１の画像と第２の画像の類似度に基づいて、第１の画像と第２の画像の境界が、時間的に不連続な画像の変化を伴う境界であるカットチェンジであるかを判定し、その判定結果を表す判定結果情報を特徴分布統合部５１５に供給する。
【０１４７】
特徴分布統合部５１５は、カットチェンジ検出部５１４から供給される判定結果情報がカットチェンジではないことを表す場合、同一カットが継続中であると判断し、間引き処理部５１３から供給される間引き処理後の特徴分布を、保持している統合特徴分布に積算し、積算後の統合特徴分布を保持する。また、特徴分布統合部５１５は、カットチェンジ検出部５１４から供給される判定結果情報がカットチェンジであることを表す場合、カットチェンジと判断し、それまでの積算によって得た統合特徴分布を保存部５１６に供給し、そして、保持している統合特徴分布を、例えば、一旦リセットする。
【０１４８】
保存部５１６は、特徴分布統合部５１５から供給された積算特徴分布を保存する。このようにして、保存部５１６には、カットごとの統合特徴分布がそれぞれ保存される。
【０１４９】
類似度算出部５１７は、保存部５１６から、画像グルーピング処理の対象とする第１のカットと第２のカットのそれぞれの統合特徴分布を読み出し、第１のカットの統合特徴分布と第２のカットの統合特徴分布とを比較し、第１のカットの統合特徴分布と第２のカットの統合特徴分布との類似度である統合特徴分布類似度を算出し、グルーピング部５１８に供給する。
【０１５０】
グルーピング部５１８は、類似度算出部５１７から供給される統合特徴分布類似度に基づいて、例えば、第１のカットと第２のカットを同じグループとするかどうかを判定する。そして、グルーピング部５１８は、同様にして、類似度算出部５１７から供給されるカットをグルーピングする。
【０１５１】
次に、図１８及び図１９のフローチャートを参照して、図１７の画像グルーピング装置５０１による画像グルーピング処理について説明する。
【０１５２】
画像グルーピング処理は、例えば、外部から画像グルーピング装置５０１に、画像が供給されると、開始される。
【０１５３】
ステップＳ４７１において、カットチェンジ検出部５１４の精細ヒストグラム生成部４０１は、そこに供給される画像の精細ヒストグラムを生成し、カットチェンジ検出部５１４の特徴分布算出部４０２に供給する。
【０１５４】
ステップＳ４７２において、カットチェンジ検出部５１４の特徴分布算出部４０２は、精細ヒストグラム生成部４０１から供給される精細ヒストグラムにフィルタ処理を施し、その結果得られる画像の特徴分布を、間引き処理部５１３に供給する。
【０１５５】
ステップＳ４７３において、カットチェンジ検出部５１４の間引き処理部４０３は、特徴分布算出部４０２から供給される特徴分布に対して、所定の間隔で間引きを行う間引き処理を施し、その結果得られる間引き処理後の画像の特徴分布を特徴分布統合部５１５に供給する。
【０１５６】
ステップＳ４７４において、カットチェンジ検出部５１４の図１０に示されるように構成される類似度算出部４０４は、類似度算出処理、すなわち、間引き処理後の画像の特徴分布と、間引き処理後の前フレームの画像の特徴分布の類似度を算出する。以上のステップＳ４７１乃至Ｓ４７４の処理は、図６におけるステップＳ４０１乃至Ｓ４０４の処理と同様の処理である。
【０１５７】
ステップＳ４７５において、カットチェンジ検出部５１４の判定部４０５は、類似度算出部４０４から供給される類似度が所定の閾値以下かどうかを判定する。類似度が所定の閾値以下と判定された場合、ステップＳ４７６において、判定部４０５は、カットチェンジを検出する処理対象とする第１の画像（現フレームの画像）と第２の画像（前フレームの画像）の境界が、時間的に不連続な画像の変化を伴う境界であるカットチェンジと判定する。
【０１５８】
これにより、カットチェンジ検出部５１４は、カットチェンジであることを表す判定結果情報を、特徴分布統合部５１５に供給する。
【０１５９】
一方、ステップＳ４７５において、類似度が所定の閾値以下ではないと判定された場合、ステップＳ４７７において、判定部４０５は、カットチェンジを検出する処理対象とする第１の画像と第２の画像の境界が、カットチェンジではないと判定する。
【０１６０】
これにより、カットチェンジ検出部５１４は、カットチェンジではないことを表す判定結果情報を、特徴分布統合部５１５に供給する。
【０１６１】
ステップＳ４７８において、精細ヒストグラム生成部５１１は、そこに供給される画像の精細ヒストグラムを生成し、特徴分布算出部５１２に供給する。
【０１６２】
ステップＳ４７９において、特徴分布算出部５１２は、精細ヒストグラム生成部５１１から供給される精細ヒストグラムにフィルタ処理を施し、その結果得られる特徴分布を、間引き処理部５１３に供給する。
【０１６３】
ステップＳ４８０において、間引き処理部５１３は、特徴分布算出部５１２から供給される特徴分布に対して、所定の間隔で間引きを行う間引き処理を施し、その結果得られる間引き処理後の特徴分布を特徴分布統合部５１５に供給する。以上のステップＳ４７８乃至Ｓ４８０の処理は、図６におけるステップＳ４０１乃至Ｓ４０３の処理と同様の処理である。
【０１６４】
ステップＳ４８１において、特徴分布統合部５１５は、カットチェンジ検出部５１４から供給される判定結果情報がカットチェンジではないことを表す場合、同一カットが継続中であると認識し、間引き処理部５１３から供給される間引き処理後の特徴分布を、保持している統合特徴分布に積算し、積算後の統合特徴分布を保持する。また、特徴分布統合部５１５は、カットチェンジ検出部５１４から供給される判定結果情報がカットチェンジであることを表す場合、それまでの積算によって得たそのカットの統合特徴分布を保存部５１６に供給し、そして、保持している統合特徴分布を、一旦リセットし、新たなカットの特徴分布を積算する。
【０１６５】
ステップＳ４８２において、保存部５１６は、特徴分布統合部５１５から供給されるカットごとの統合特徴分布を保存する。
【０１６６】
ステップＳ４８３において、類似度算出部５１７は、保存部５１６から、画像グルーピング処理対象とする第１のカットと第２のカットのそれぞれの統合特徴分布を読み出し、第１のカットの統合特徴分布と第２のカットの統合特徴分布とを比較し、第１のカットの統合特徴分布と第２のカットの統合特徴分布の類似度である統合特徴分布類似度を算出し、グルーピング部５１８に供給する。この類似度の算出も、ステップＳ４７４における場合と同様に行われる。
【０１６７】
ステップＳ４８４において、グルーピング部５１８は、類似度算出部５１７から供給される統合特徴分布類似度に基づいて、例えば、第１のカットと第２のカットを同じグループとするかどうかを判定する。そして、グルーピング部５１８は、同様にして、類似度算出部５１７から供給されるカットをグルーピングする。
【０１６８】
以上のようにして、輝度または色の微小変動が生じた場合でも、簡単かつ確実に、類似するカットが同じグループに属するようにグルーピングが行われる。
【０１６９】
なお、上述した各処理では、画像をフレーム単位で扱うように説明したが、画像をフィールド単位で扱うようにすることもできる。
【０１７０】
また、本明細書において、プログラム記録媒体に格納されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７１】
本発明は、ソフトウェアにより構成する他、ハードウェアにより構成することができる。
【０１７２】
本発明は、放送機器、画像編集機器、カムコーダ、画像処理用のパーソナルコンピュータ、DVDレコーダ、ハードディスクレコーダ等の画像を処理するあらゆる検出装置に適用することができる。
【０１７３】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１７４】
【図１】カットチェンジが生じた場合のヒストグラムの変化を示す図である。
【図２】輝度の微小変動が生じた場合のヒストグラムの変化を示す図である。
【図３】フレームの左半分と右半分のそれぞれに輝度の微小変動が生じた場合のヒストグラムの変化を示す図である。
【図４】本発明を適用した検出装置としてのパーソナルコンピュータの一実施の形態の構成を示すブロック図である。
【図５】カットチェンジ検出装置の一実施の形態の構成を示すブロック図である。
【図６】カットチェンジ検出処理を説明するフローチャートである。
【図７】精細ヒストグラム及び特徴分布の変化を示す図である。
【図８】低域通過型フィルタの周波数応答特性を示す図である。
【図９】非線形フィルタによるフィルタ処理を説明する図である。
【図１０】類似度算出部の一実施の形態の構成を示すブロック図である。
【図１１】図６のステップＳ４０４の類似度算出処理を説明するフローチャートである。
【図１２】サンプルの対応付けを説明する図である。
【図１３】２枚の画像の類似度を説明する図である。
【図１４】本発明を適用した類似度算出装置の一実施の形態の構成を示すブロック図である。
【図１５】図１４の類似度算出装置による静止画像類似度算出処理を説明するフローチャートである。
【図１６】類似するカットを説明する図である。
【図１７】本発明を適用した画像グルーピング装置の一実施の形態の構成を示すブロック図である。
【図１８】画像グルーピング処理を説明するフローチャートである。
【図１９】画像グルーピング処理を説明するフローチャートである。
【符号の説明】
【０１７５】
１  パーソナルコンピュータ，  ２１  CPU，  ２２  ROM，  ２３  RAM，  ２４  バス，  ２５  入出力インタフェース，  ２６  入力部，  ２７  出力部，  ２８  記憶部，  ２９  通信部，  ３０  ドライブ，  ３１  リムーバブルメディア，  ５１  カットチェンジ検出装置，  ４０１  精細ヒストグラム生成部，  ４０２  特徴分布算出部，  ４０３  間引き処理部，  ４０４  類似度算出部，  ４０５  判定部，  ４３１  対応サンプル決定部，  ４３２  類似度決定部，  ４６１  類似度算出装置，  ４７１  精細ヒストグラム生成部，  ４７２  特徴分布算出部，  ４７３  間引き処理部，  ４７４  精細ヒストグラム生成部，  ４７５  特徴分布算出部，  ４７６  間引き処理部，  ４７７  類似度算出部，  ５０１  画像グルーピング装置，  ５１１  精細ヒストグラム生成部，  ５１２  特徴分布算出部，  ５１３  間引き処理部，  ５１４  カットチェンジ検出部，  ５１５  特徴分布統合部，  ５１６  保存部，  ５１７  類似度算出部，  ５１８  グルーピング部
【図１】
2008085539.tif 000003
【図２】
2008085539.tif 000004
【図３】
2008085539.tif 000005
【図４】
2008085539.tif 000006
【図５】
2008085539.tif 000007
【図６】
2008085539.tif 000008
【図７】
2008085539.tif 000009
【図８】
2008085539.tif 000010
【図９】
2008085539.tif 000011
【図１０】
2008085539.tif 000012
【図１１】
2008085539.tif 000013
【図１２】
2008085539.tif 000014
【図１３】
2008085539.tif 000015
【図１４】
2008085539.tif 000016
【図１５】
2008085539.tif 000017
【図１６】
2008085539.tif 000018
【図１７】
2008085539.tif 000019
【図１８】
2008085539.tif 000020
【図１９】
2008085539.tif 000021