(57)【要約】【課題】演算量を軽減し、迅速な検索ができるようにする。【解決手段】代表値情報生成部３２が、ブロック毎に符号化された情報の、ブロック毎の代表値に基づく代表値情報を生成し、分布量サンプル数演算部３３が、ブロック内のサンプル値の分布を表す分布量を演算し、代表値情報取得部３２が、検索対象と比較対象の代表値情報を取得し、検索部２４の距離演算部が、検索対象の代表値情報に対する比較対象の代表値情報の距離を演算し、検索部２４の選択部が、演算された距離に基づいて、検索対象に類似する比較対象を選択する。【選択図】図１
2009110210.tif 000002
【特許請求の範囲】
【請求項１】
ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成する代表値情報生成部と、
前記ブロック内のサンプル値の分布を表す分布量を演算する分布量演算部と、
前記代表値情報および前記分布量を、入力された情報毎に保持するデータベースと
を備える情報符号化装置。
【請求項２】
前記分布量演算部は、前記分布量として前記ブロックの分散値を演算する
請求項１に記載の情報符号化装置。
【請求項３】
入力された情報をベクトル量子化し、コードブックを生成するコードブック生成部をさらに備え、
前記代表値情報生成部は、前記コードブックの各ブロックの前記代表値としてのコードワードに基づいて前記代表値情報を生成し、
前記データベースは、前記コードブック、前記代表値情報、および前記分散値を、入力された情報毎に保持する
請求項２に記載の情報符号化装置。
【請求項４】
代表値情報生成部が、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、
分布量演算部が、前記ブロック内のサンプル値の分布を表す分布量を演算し、
データベースが、前記代表値情報および前記分布量を、入力された情報毎に保持する
情報符号化方法。
【請求項５】
ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、
前記ブロック内のサンプル値の分布を表す分布量を演算し、
前記代表値情報および前記分布量を、入力された情報毎にデータベースに保持する
処理をコンピュータに実行させるプログラム。
【請求項６】
検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得する代表値情報取得部と、
前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算する距離演算部と、
演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する選択部と
を備える情報検索装置。
【請求項７】
代表値情報取得部は、前記検索対象と前記比較対象の、ベクトル量子化により生成されたコードブックの各ブロックの前記代表値としてのコードワードに基づいて生成された前記代表値情報を取得し、
前記距離演算部は、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算する
請求項６に記載の情報検索装置。
【請求項８】
前記距離演算部は、
前記検索対象の前記代表値情報の前記コードワードに対応する前記比較対象の前記代表値情報の前記コードワードの度数分布を演算する度数分布演算部と、
前記度数分布に基づいて前記距離を演算する画像間距離演算部と
を備える請求項７に記載の情報検索装置。
【請求項９】
前記代表値情報を保持するデータベースをさらに備え、
前記代表値情報取得部は、前記比較対象の前記代表値情報を、前記データベースから取得する
請求項７に記載の情報検索装置。
【請求項１０】
前記検索対象と前記比較対象の前記コードブックを取得するコードブック取得部と、
前記検索対象と前記比較対象の前記コードブックの各ブロックの分布量を取得する分布量取得部と、
前記コードブックと前記分布量に基づいて重みを演算する重み演算部と
をさらに備え、
前記距離演算部は、前記度数分布と前記重みに基づいて、前記検索対象に対する前記比較対象の距離を演算する
請求項８に記載の情報検索装置。
【請求項１１】
前記分布量取得部は、前記分布量として前記ブロックの分散値を取得し、
前記重み演算部は、前記検索対象と前記比較対象の前記コードワードの距離と前記検索対象の分散値の大きさ、および前記検索対象と前記比較対象の前記コードワードの距離と前記比較対象の分散値の大きさに基づいて、前記重みを演算する
請求項１０に記載の情報検索装置。
【請求項１２】
前記重み演算部は、前記重みを、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも大きい場合第１の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも小さい場合、前記第１の値より小さい第２の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値の一方より大きくかつ他方より小さい場合、前記第１の値より小さくかつ前記第２の値より大きい第３の値に設定する
請求項１１に記載の情報検索装置。
【請求項１３】
前記ブロックのサンプル数を取得するサンプル数取得部をさらに備え、
前記重み演算部は、前記サンプル数が所定の閾値以下であるとき、そのブロックの前記重みを最小値に設定する
請求項１０に記載の情報検索装置。
【請求項１４】
代表値情報取得部が、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、
距離演算部が、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、
選択部が、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する
情報検索方法。
【請求項１５】
検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、
前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、
演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する
処理をコンピュータに実行させるプログラム。
【請求項１６】
検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得する代表値情報取得部と、
前記検索対象と前記比較対象の前記ブロック内のサンプル値の分布を表す分布量を取得する分布量取得部と、
前記分布量に基づいて重みを演算する重み演算部と、
前記代表値情報と前記重みに基づいて、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算する距離演算部と、
演算された前記距離に基づいて前記検索対象に類似する前記比較対象を選択する選択部と
を備える情報検索装置。
【請求項１７】
前記代表値情報取得部は、前記検索対象と前記比較対象の、ベクトル量子化により生成されたコードブックの前記ブロックの前記代表値としてのコードワードに基づいて生成された前記代表値情報を取得し、
前記分布量取得部は、前記分布量として前記ブロックの分散値を取得する
請求項１６に記載の情報検索装置。
【請求項１８】
前記代表値情報を保持するデータベースをさらに備え、
前記代表値情報取得部は、前記比較対象の前記代表値情報を、前記データベースから取得する
請求項１６に記載の情報検索装置。
【請求項１９】
前記コードブックを取得するコードブック取得部をさらに備え、
前記重み演算部は、さらに前記コードブックの各ブロックのコードワード間の距離を演算し、前記コードワード間の距離と前記分散値に基づいて、前記重みを演算する
請求項１７に記載の情報検索装置。
【請求項２０】
前記距離演算部は、前記検索対象の前記代表値情報に対応する前記比較対象の前記代表値情報の度数分布を演算し、前記度数分布に基づいて、前記検索対象に対する前記比較対象の距離を演算する
請求項１７に記載の情報検索装置。
【請求項２１】
前記重み演算部は、前記検索対象と前記比較対象の前記コードワードの距離と前記検索対象の前記分散値の大きさ、および前記検索対象と前記比較対象の前記コードワードの距離と前記比較対象の前記分散値の大きさに基づいて、前記重みを演算する
請求項１７に記載の情報検索装置。
【請求項２２】
前記重み演算部は、前記重みを、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも大きい場合第１の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも小さい場合、前記第１の値より小さい第２の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値の一方より大きくかつ他方より小さい場合、前記第１の値より小さくかつ前記第２の値より大きい第３の値に設定する
請求項２１に記載の情報検索装置。
【請求項２３】
前記ブロックのサンプル数を取得するサンプル数取得部をさらに備え、
前記重み演算部は、前記サンプル数が所定の閾値以下であるとき、そのブロックの前記重みを最小値に設定する
請求項１６に記載の情報検索装置。
【請求項２４】
代表値情報取得部が、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、
分布量取得部が、前記検索対象と前記比較対象の前記ブロック内のサンプル値の分布を表す分布量を取得し、
重み演算部が、前記分布量に基づいて重みを演算し、
距離演算部が、前記代表値情報と前記重みに基づいて、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、
選択部が、演算された前記距離に基づいて前記検索対象に類似する前記比較対象を選択する
情報検索方法。
【請求項２５】
検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、
前記検索対象と前記比較対象の前記ブロック内のサンプル値の分布を表す分布量を取得し、
前記分布量に基づいて重みを演算し、
前記代表値情報と前記重みに基づいて、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、
演算された前記距離に基づいて前記検索対象に類似する前記比較対象を選択する
処理をコンピュータに実行させるプログラム。
【請求項２６】
ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成する代表値情報生成部と、
前記ブロック内のサンプル値の分布を表す分布量を演算する分布量演算部と、
検索対象と比較対象の前記代表値情報を取得する代表値情報取得部と、
前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算する距離演算部と、
演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する選択部と
を備える情報処理システム。
【請求項２７】
代表値情報生成部が、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、
分布量演算部が、前記ブロック内のサンプル値の分布を表す分布量を演算し、
代表値情報取得部が、検索対象と比較対象の前記代表値情報を取得し、
距離演算部が、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、
選択部が、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する
情報処理方法。
【請求項２８】
ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、
前記ブロック内のサンプル値の分布を表す分布量を演算し、
検索対象と比較対象の前記代表値情報を取得し、
前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、
演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する
処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報符号化装置および方法、情報検索装置および方法、情報処理システムおよび方法、並びにプログラムに関し、特に、演算量を軽減し、迅速な検索を可能とする情報符号化装置および方法、情報検索装置および方法、情報処理システムおよび方法、並びにプログラムに関する。
【背景技術】
【０００２】
ネットワークの広帯域化やストレージ容量の増大に伴い、情報、特に画像情報を効率的に整理する手法が求められている。
【０００３】
例えば画像にタグを付加し、そのタグを検索する手法が提案されている。しかし、大量の画像に対して１つ１つタグを付加する処理の負荷が大きく、迅速なデータベースの構築が困難となる。
【０００４】
そこで、画像の特徴量を検出し、この画像の特徴量に基づいて検索を行う手法も提案されている。
【０００５】
例えば特許文献１においては、記録されているＪＰＥＧ（Joint Photographic Experts Group）ファイルとしての画像データを読み出して解凍し、解凍過程で８×８画素のブロック毎の色度情報と輝度情報を取得し、それが検索対象としての画像の定義に合致する範囲の色度情報あるいは輝度情報であるかを判定することで画像が検索される。
【０００６】
【特許文献１】特開２００５−６２９６４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、このような手法は、演算コストがかかり、大量の画像に対して効率的に検索を行うことが困難である。
【０００８】
本発明は、このような状況に鑑みてなされたものであり、演算量を軽減し、迅速な検索を可能とするものである。
【課題を解決するための手段】
【０００９】
本発明の一側面は、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成する代表値情報生成部と、前記ブロック内のサンプル値の分布を表す分布量を演算する分布量演算部と、前記代表値情報および前記分布量を、入力された情報毎に保持するデータベースとを備える情報符号化装置である。
【００１０】
前記分布量演算部は、前記分布量として前記ブロックの分散値を演算することができる。
【００１１】
入力された情報をベクトル量子化し、コードブックを生成するコードブック生成部をさらに備え、前記代表値情報生成部は、前記コードブックの各ブロックの前記代表値としてのコードワードに基づいて前記代表値情報を生成し、前記データベースは、前記コードブック、前記代表値情報、および前記分散値を、入力された情報毎に保持することができる。
【００１２】
本発明の一側面は、代表値情報生成部が、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、分布量演算部が、前記ブロック内のサンプル値の分布を表す分布量を演算し、データベースが、前記代表値情報および前記分布量を、入力された情報毎に保持する情報符号化方法である。
【００１３】
本発明の一側面は、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、前記ブロック内のサンプル値の分布を表す分布量を演算し、前記代表値情報および前記分布量を、入力された情報毎にデータベースに保持する処理をコンピュータに実行させるプログラムである。
【００１４】
本発明の他の側面は、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得する代表値情報取得部と、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算する距離演算部と、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する選択部とを備える情報検索装置である。
【００１５】
代表値情報取得部は、前記検索対象と前記比較対象の、ベクトル量子化により生成されたコードブックの各ブロックの前記代表値としてのコードワードに基づいて生成された前記代表値情報を取得し、前記距離演算部は、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算することができる。
【００１６】
前記距離演算部は、前記検索対象の前記代表値情報の前記コードワードに対応する前記比較対象の前記代表値情報の前記コードワードの度数分布を演算する度数分布演算部と、前記度数分布に基づいて前記距離を演算する画像間距離演算部とを備えることができる。
【００１７】
前記代表値情報を保持するデータベースをさらに備え、前記代表値情報取得部は、前記比較対象の前記代表値情報を、前記データベースから取得することができる。
【００１８】
前記検索対象と前記比較対象の前記コードブックを取得するコードブック取得部と、前記検索対象と前記比較対象の前記コードブックの各ブロックの分布量を取得する分布量取得部と、前記コードブックと前記分布量に基づいて重みを演算する重み演算部とをさらに備え、前記距離演算部は、前記度数分布と前記重みに基づいて、前記検索対象に対する前記比較対象の距離を演算することができる。
【００１９】
前記分布量取得部は、前記分布量として前記ブロックの分散値を取得し、
前記重み演算部は、前記検索対象と前記比較対象の前記コードワードの距離と前記検索対象の分散値の大きさ、および前記検索対象と前記比較対象の前記コードワードの距離と前記比較対象の分散値の大きさに基づいて、前記重みを演算することができる。
【００２０】
前記重み演算部は、前記重みを、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも大きい場合第１の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも小さい場合、前記第１の値より小さい第２の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値の一方より大きくかつ他方より小さい場合、前記第１の値より小さくかつ前記第２の値より大きい第３の値に設定することができる。
【００２１】
前記ブロックのサンプル数を取得するサンプル数取得部をさらに備え、前記重み演算部は、前記サンプル数が所定の閾値以下であるとき、そのブロックの前記重みを最小値に設定することができる。
【００２２】
本発明の他の側面は、代表値情報取得部が、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、距離演算部が、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、選択部が、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する情報検索方法である。
【００２３】
本発明の他の側面は、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する処理をコンピュータに実行させるプログラムである。
【００２４】
本発明のさらに他の側面は、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得する代表値情報取得部と、前記検索対象と前記比較対象の前記ブロック内のサンプル値の分布を表す分布量を取得する分布量取得部と、前記分布量に基づいて重みを演算する重み演算部と、前記代表値情報と前記重みに基づいて、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算する距離演算部と、演算された前記距離に基づいて前記検索対象に類似する前記比較対象を選択する選択部とを備える情報検索装置である。
【００２５】
前記代表値情報取得部は、前記検索対象と前記比較対象の、ベクトル量子化により生成されたコードブックの前記ブロックの前記代表値としてのコードワードに基づいて生成された前記代表値情報を取得し、前記分布量取得部は、前記分布量として前記ブロックの分散値を取得することができる。
【００２６】
前記代表値情報を保持するデータベースをさらに備え、前記代表値情報取得部は、前記比較対象の前記代表値情報を、前記データベースから取得することができる。
【００２７】
前記コードブックを取得するコードブック取得部をさらに備え、前記重み演算部は、さらに前記コードブックの各ブロックのコードワード間の距離を演算し、前記コードワード間の距離と前記分散値に基づいて、前記重みを演算することができる。
【００２８】
前記距離演算部は、前記検索対象の前記代表値情報に対応する前記比較対象の前記代表値情報の度数分布を演算し、前記度数分布に基づいて、前記検索対象に対する前記比較対象の距離を演算することができる。
【００２９】
前記重み演算部は、前記検索対象と前記比較対象の前記コードワードの距離と前記検索対象の前記分散値の大きさ、および前記検索対象と前記比較対象の前記コードワードの距離と前記比較対象の前記分散値の大きさに基づいて、前記重みを演算することができる。
【００３０】
前記重み演算部は、前記重みを、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも大きい場合第１の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値のいずれよりも小さい場合、前記第１の値より小さい第２の値に設定し、前記検索対象と前記比較対象の前記コードワードの距離が前記検索対象の分散値と前記比較対象の分散値の一方より大きくかつ他方より小さい場合、前記第１の値より小さくかつ前記第２の値より大きい第３の値に設定することができる。
【００３１】
前記ブロックのサンプル数を取得するサンプル数取得部をさらに備え、前記重み演算部は、前記サンプル数が所定の閾値以下であるとき、そのブロックの前記重みを最小値に設定することができる。
【００３２】
本発明のさらに他の側面は、代表値情報取得部が、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、分布量取得部が、前記検索対象と前記比較対象の前記ブロック内のサンプル値の分布を表す分布量を取得し、重み演算部が、前記分布量に基づいて重みを演算し、距離演算部が、前記代表値情報と前記重みに基づいて、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、選択部が、演算された前記距離に基づいて前記検索対象に類似する前記比較対象を選択する情報検索方法である。
【００３３】
本発明のさらに他の側面は、検索対象と比較対象をブロック毎に符号化して得られる、前記ブロック毎の代表値に基づいて生成された代表値情報を取得し、前記検索対象と前記比較対象の前記ブロック内のサンプル値の分布を表す分布量を取得し、前記分布量に基づいて重みを演算し、前記代表値情報と前記重みに基づいて、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、演算された前記距離に基づいて前記検索対象に類似する前記比較対象を選択する処理をコンピュータに実行させるプログラムである。
【００３４】
本発明の他の側面は、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成する代表値情報生成部と、前記ブロック内のサンプル値の分布を表す分布量を演算する分布量演算部と、検索対象と比較対象の前記代表値情報を取得する代表値情報取得部と、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算する距離演算部と、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する選択部とを備える情報処理システムである。
【００３５】
本発明の他の側面は、代表値情報生成部が、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、分布量演算部が、前記ブロック内のサンプル値の分布を表す分布量を演算し、代表値情報取得部が、検索対象と比較対象の前記代表値情報を取得し、距離演算部が、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、選択部が、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する情報処理方法である。
【００３６】
本発明の他の側面は、ブロック毎に符号化された情報の、前記ブロック毎の代表値に基づく代表値情報を生成し、前記ブロック内のサンプル値の分布を表す分布量を演算し、検索対象と比較対象の前記代表値情報を取得し、前記検索対象の前記代表値情報に対する前記比較対象の前記代表値情報の距離を演算し、演算された前記距離に基づいて、前記検索対象に類似する前記比較対象を選択する処理をコンピュータに実行させるプログラムである。
【００３７】
本発明の一側面においては、ブロック毎に符号化された情報の、ブロック毎の代表値に基づく代表値情報が生成され、ブロック内のサンプル値の分布を表す分布量が演算され、代表値情報および分布量が、入力された情報毎に保持される。
【００３８】
本発明の他の側面においては、検索対象と比較対象をブロック毎に符号化して得られる、ブロック毎の代表値に基づいて生成された代表値情報が取得され、検索対象の代表値情報に対する比較対象の代表値情報の距離が演算され、演算された距離に基づいて、検索対象に類似する比較対象が選択される。
【００３９】
さらに本発明の他の側面においては、検索対象と比較対象をブロック毎に符号化して得られる、ブロック毎の代表値に基づいて生成された代表値情報が取得され、検索対象と比較対象のブロック内のサンプル値の分布を表す分布量が取得され、分布量に基づいて重みが演算され、代表値情報と重みに基づいて、検索対象の代表値情報に対する比較対象の代表値情報の距離が演算され、演算された距離に基づいて検索対象に類似する比較対象が選択される。
【００４０】
また本発明の他の側面においては、ブロック毎に符号化された情報の、ブロック毎の代表値に基づく代表値情報が生成され、ブロック内のサンプル値の分布を表す分布量が演算され、検索対象と比較対象の代表値情報が取得され、検索対象の代表値情報に対する比較対象の代表値情報の距離が演算され、演算された距離に基づいて、検索対象に類似する比較対象が選択される。
【発明の効果】
【００４１】
以上のように、本発明の側面によれば、演算量を軽減し、迅速な検索が可能となる。
【発明を実施するための最良の形態】
【００４２】
以下、図を参照して本発明の実施の形態について説明する。
【００４３】
図１は本発明の情報処理システムの一実施の形態の構成を表している。情報処理システム１は、情報符号化装置１１と情報検索装置１２とにより構成されている。
【００４４】
情報符号化装置１１は入力部２１、ベクトル量子化部２２、およびデータベース２３により構成されている。
【００４５】
入力部２１はデータベース２３に保持する情報として、この実施の形態の場合、画像信号を入力し、ベクトル量子化部２２に供給する。ベクトル量子化部２２はコードブック生成部３１、代表値情報生成部３２、および分布量サンプル数演算部３３を有している。
【００４６】
コードブック生成部３１は、入力部２１から供給された画像信号をベクトル量子化し、コードブックを生成する。このコードブックには、複数の量子化ベクトルの集合であるグループとしてのブロック毎に、代表ベクトルに対応するコードワードが規定される。代表値情報生成部３２は、ブロック毎に符号化された情報の、ブロック毎の代表値に基づく代表値情報を生成する。具体的には、コードブックの代表値としてのコードワードに基づいて、入力部２１から供給された画像信号から代表値情報としてのコードワード画像を生成する。
【００４７】
分布量サンプル数演算部３３は、コードブックの各ブロック毎に、量子化ベクトルを構成する要素の数であるサンプル数を計測するとともに、ブロック内のサンプル値の分布を表す分布量を演算する。この分布量としては、例えばサンプル値としての画素値の分布を表す分散値が演算される。
【００４８】
データベース２３は、コードブック生成部３１により生成されたコードブック、代表値情報生成部３２により生成された代表値情報、および分布量サンプル数演算部３３により演算された分布量とサンプル数を、入力された画像毎に保持する。
【００４９】
情報検索装置１２は、データベース２３と検索部２４により構成されている。検索部２４の一実施の形態の構成は図２に示されている。
【００５０】
図２に示されるように、検索部２４は、読み出し部４１、代表値情報取得部４２−１，４２−２、コードブック取得部４３−１，４３−２、分布量取得部４４−１，４４−２、サンプル数取得部４５−１，４５−２、距離演算部４６、重み演算部４７、最小距離選択部４８、および表示部４９により構成されている。
【００５１】
読み出し部４１は、データベース２３からそこに保持されている情報を読み出す。代表値情報取得部４２−１、コードブック取得部４３−１、分布量取得部４４−１、サンプル数取得部４５−１は、それぞれ、読み出し部４１により読み出された情報のうちの検索対象としての画像信号から、代表値情報、コードブック、分布量、またはサンプル数を取得する。同様に、代表値情報取得部４２−２、コードブック取得部４３−２、分布量取得部４４−２、またはサンプル数取得部４５−２は、それぞれ、読み出し部４１により読み出された情報のうちの比較対象としての画像信号から、代表値情報、コードブック、分布量、またはサンプル数を取得する。
【００５２】
距離演算部４６は、代表値情報取得部４２−１で取得された検索対象の代表値情報と、代表値情報取得部４２−２で取得された、それに対応する比較対象の代表値情報の距離を演算する。このため距離演算部４６は、度数分布演算部６１と画像間距離演算部６２を有している。
【００５３】
度数分布演算部６１は、代表値情報取得部４２−１，４２−２により取得された代表値情報から、検索対象としての画像信号のコードワードに対応する比較対象としての画像信号のコードワードの度数分布を演算する。
【００５４】
重み演算部４７は、コードワード間距離演算部７１とコードワード間距離重み演算部７２により構成されている。コードワード間距離演算部７１は、コードブック取得部４３−１，４３−２により取得された、検索対象としての画像信号のコードワードと比較対象としての画像信号のコードワードのコードワード間距離を演算する。
【００５５】
コードワード間距離重み演算部７２は、コードワード間距離演算部７１により演算されたコードワード間距離に付加する重みを、コードワード間距離演算部７１により演算されたコードワード間距離と、分布量取得部４４−１，４４−２により取得された分布量の大きさを比較し、その比較結果に基づいて演算する。
【００５６】
すなわち、その重みは、検索対象と比較対象のコードワードの距離が検索対象の分布量と比較対象の分布量のいずれよりも大きい場合第１の値に設定され、検索対象と比較対象のコードワードの距離が検索対象の分布量と比較対象の分布量のいずれよりも小さい場合、第１の値より小さい第２の値に設定され、検索対象と比較対象のコードワードの距離が検索対象の分布量と比較対象の分布量の一方より大きくかつ他方より小さい場合、第１の値より小さくかつ第２の値より大きい第３の値に設定される。
【００５７】
コードワード間距離重み演算部７２は、この重みを演算するに当たり、サンプル数取得部４５−１，４５−２により取得されたサンプル数を予め規定されている所定の閾値と比較し、サンプル数が閾値以下であるとき、そのブロックの重みを最小値に設定する。
【００５８】
画像間距離演算部６２は、度数分布演算部６１により演算された度数分布に基づいて、検索対象としての画像に対する比較対象としての画像の距離を演算する。また、画像間距離演算部６２は、重み演算部４７により演算された重みに基づいてこの画像間距離を演算する。すなわち、度数分布と重みに基づいて画像間距離が演算される。
【００５９】
最小距離選択部４８は、検索対象に類似する比較対象を選択する。すなわち、読み出し部４１により読み出された比較対象としての画像の中から、画像間距離演算部６２により演算された画像間距離が最小である画像が任意の数だけ選択される。表示部４９は最小距離選択部４８により選択された画像情報を復号し、その画像を表示する。このとき、表示部４９は、読み出し部４１により読み出され、最小距離選択部４８を介して供給される検索対象としての画像情報も合わせて復号し、その画像を表示する。
【００６０】
なお、図１と図２において、各部は１つの装置として近接配置し、接続してもよいし、インターネットに代表される各種のネットワークを介して接続することもできる。
【００６１】
次に図３のフローチャートを参照して、情報符号化装置１１が情報をデータベース２３に保持する処理について説明する。
【００６２】
ステップＳ１において、入力部２１はデータベース２３に保持する画像信号を入力する。この画像信号は、他の記録媒体あるいはインターネット、その他のネットワークから供給される。
【００６３】
ステップＳ２において、コードブック生成部３１は入力部２１から入力された画像信号をベクトル量子化し、コードブックを生成する。図４はこの場合の処理を表している。図４においては、画像信号をベクトル量子化することで得られたベクトルを構成する要素(サンプル)が×印で示されている。１０１−１乃至１０１−４は、１個以上の要素で構成されるベクトルとしてのグループであるブロックを表している。ベクトル量子化においては、各ブロックにおいて、量子化誤差の総和が最小となるベクトルが、各要素を最も代表する代表ベクトルとして演算される。コードワード１０３−１乃至１０３−４はこの代表ベクトルに対応する値であり、図４においては、３角形の印で表されている。コードブックはこのコードワードの集合である。
【００６４】
ステップＳ３において、代表値情報生成部３２は、代表値情報を生成する。この代表値情報は、例えば入力部２１から入力された画像信号をコードワードで表した画像であるコードワード画像（後述する図７を参照）として生成される。ステップＳ４において、分布量サンプル数演算部３３は各ブロックの分布量を演算する。この分布量として、ここでは分散値が演算される。そしてステップＳ５において、分布量サンプル数演算部３３は各ブロックの要素の数であるサンプル数を計測する。
【００６５】
分散値は各ブロックの広がり、すなわちブロック内のサンプル値の分布を表すので、図４においては、分散値１０２−１乃至１０２−４として表されている。また図４においてサンプル数は、各ブロック１０１−１乃至１０１−４に含まれる要素である×印の数を意味する。
【００６６】
ステップＳ６において、データベース２３は、ステップＳ２において生成されたコードブック、ステップＳ３において生成された代表値情報、ステップＳ４において演算された分布量、およびステップＳ５において計測されたサンプル数を、ステップＳ１において入力された画像信号に対応して保持する。
【００６７】
以上の処理が複数の画像に対して行われ、データベース２３に、複数の画像が、対応するコードブック、代表値情報、分布量、およびサンプル数とともに保持される。
【００６８】
このように、画像を符号化して保持する際に、符号化時に生成される情報を合わせて保持することで、検索時における処理が軽減され、迅速な検索が可能となる。
【００６９】
次に、図５と図６のフローチャートを参照して、情報検索装置１２における検索処理について説明する。
【００７０】
なお、ここで検索は、類似する情報（同一の情報を含む）を検出する処理を意味する。
【００７１】
ステップＳ４１において、読み出し部４１はデータベース２３から、ユーザにより指定された検索対象の画像信号を読み出す。この画像信号は、代表値情報取得部４２−１、コードブック取得部４３−１、分布量取得部４４−１、サンプル数取得部４５−１、および最小距離選択部４８に供給される。
【００７２】
ステップＳ４２において、代表値情報取得部４２−１は、読み出し部４１から供給された検索対象の信号から代表値情報を取得する。具体的にはコードワード画像が取得される。図７にこの検索対象のコードワード画像８１Ａが示されている。同図に示されている数字はコードワードを表している。この実施の形態のコードワード画像８１Ａは、１乃至４の４個のコードワードで構成されている。
【００７３】
ステップＳ４３において、コードブック取得部４３−１は、読み出し部４１から供給された検索対象の信号からコードブックを取得する。ステップＳ４４において、分布量取得部４４−１は、読み出し部４１から供給された検索対象の信号から分布量（ここでは分散値）を取得する。ステップＳ４５において、サンプル数取得部４５−１は、読み出し部４１から供給された検索対象の信号からサンプル数を取得する。
【００７４】
ステップＳ４６において、読み出し部４１は比較対象の画像信号を全て読み出したかを判定する。データベース２３に保持されている全ての画像を比較対象とすることもできるし、画像が日付、ジャンルなどにより識別可能に保持されている場合には、ユーザにより指定された範囲の画像を比較対象とすることもできる。
【００７５】
いまの場合、まだ比較対象の画像は読み出されていない。そこでステップＳ４７において、読み出し部４１はデータベース２３から、比較対象の画像信号を読み出す。この画像信号は、代表値情報取得部４２−２、コードブック取得部４３−２、分布量取得部４４−２、サンプル数取得部４５−２、および最小距離選択部４８に供給される。
【００７６】
ステップＳ４８において、代表値情報取得部４２−２は、読み出し部４１から供給された比較対象の信号から代表値情報（ここではコードワード画像）を取得する。図７にこの比較対象のコードワード画像８１Ｂが示されている。この実施の形態のコードワード画像８１Ｂも、検索対象のコードワード画像８１Ａと同様に、１乃至４の４個のコードワードで構成されている。後述するように、距離演算部４６は、ステップＳ４２で取得された検索対象の代表値情報と、ステップＳ４８で取得された、それに対応する比較対象の代表値情報の距離を、ステップＳ５２，Ｓ５５において演算する。
【００７７】
ステップＳ４９において、コードブック取得部４３−２は、読み出し部４１から供給された検索対象の信号からコードブックを取得する。ステップＳ５０において、分布量取得部４４−２は、読み出し部４１から供給された比較対象の信号から分布量（ここでは分散値）を取得する。ステップＳ５１において、サンプル数取得部４５−２は、読み出し部４１から供給された比較対象の信号からサンプル数を取得する。
【００７８】
ステップＳ５２において、度数分布演算部６１は度数分布を演算する。すなわち、図７に示されるように、検索対象のコードワード画像８１Ａの所定の着目位置の量子化ブロックのコードワードが検出されるとともに、比較対象のコードワード画像８１Ｂの対応する位置の量子化ブロックのコードワードが検出される。そして比較対象のコードワード画像８１Ｂの対応する位置のコードワードの数が計数される。
【００７９】
例えば、図７に示されるように、検索対象のコードワード画像８１Ａの着目位置の量子化ブロックのコードワードが１であり、比較対象のコードワード画像８１Ｂの対応する位置の量子化ブロックのコードワードが４であれば、検索対象のコードワード画像８１Ａのコードワード１に対応する比較対象のコードワード画像８１Ｂのコードワード４の数が１と計数される。次に、着目位置をずらし、検索対象のコードワード画像８１Ａの着目位置の量子化ブロックのコードワードが１であり、比較対象のコードワード画像８１Ｂの対応する位置の量子化ブロックのコードワードが４であれば、索対象のコードワード画像８１Ａのコードワード１に対応する比較対象のコードワード画像８１Ｂのコードワード４の数は１だけインクリメントされ、２と計数される。
【００８０】
図７の索対象のコードワード画像８１Ａと比較対象のコードワード画像８１Ｂに対して以上の処理を繰り返すことで演算された度数分布が図８に示されている。この実施の形態においては、図８において縦軸に示される検索対象のコードワード画像８１Ａのコードワード１に対応する、図８において横軸に示される比較対象のコードワード画像８１Ｂのコードワードは、１である回数が１０個、２である回数が０個、３である回数が２０個、４である回数が９０個となっている。
【００８１】
以下同様に、検索対象のコードワード画像８１Ａのコードワード２に対応する比較対象のコードワード画像８１Ｂのコードワードは、１である回数が５０個、２である回数が１０個、３である回数が５個、４である回数が０個であり、検索対象のコードワード画像８１Ａのコードワード３に対応する比較対象のコードワード画像８１Ｂのコードワードは、１である回数が５個、２である回数が１０個、３である回数が４０個、４である回数が１０個であり、検索対象のコードワード画像８１Ａのコードワード４に対応する比較対象のコードワード画像８１Ｂのコードワードは、１である回数が１０個、２である回数が８０個、３である回数が０個、４である回数が１０個である。
【００８２】
ステップＳ５３において、コードワード間距離演算部７１は、コードワード間距離を演算する。コードワード間距離は、図９に示されるように、検索対象のコードワード画像８１Ａのコードワード１０３Ａと、対応する比較対象のコードワード画像８１Ｂのコードワード１０３Ｂの距離ＤABである。
【００８３】
ステップＳ５４において、コードワード間距離重み演算部７２は、コードワード間距離と分布量の大きさに応じてコードワード間距離重みを演算する。この演算は例えば、図９の模式図に示されるように行われる。
【００８４】
すなわち、図９Ａに示されるように、コードワード間距離ＤABが、検索対象のコードワード画像８１Ａのブロック１０１Ａの分散値ＶAと、対応する比較対象のコードワード画像８１Ｂのブロック１０１Ｂの分散値ＶBのいずれよりも大きい場合、比較対象のコードワード画像のコードワード１０３Ｂのブロック１０１Ｂは、検索対象のコードワード画像のードワード１０３Ａのブロック１０１Ａに対応していない可能性が高いので、重みｗABは最大の値（この実施の形態の場合１）に設定される。逆に、図９Ｄに示されるように、コードワード間距離ＤABが、検索対象のコードワード画像８１Ａのブロック１０１Ａの分散値ＶAと、対応する比較対象のコードワード画像８１Ｂのブロック１０１Ｂの分散値ＶBのいずれよりも小さい場合、比較対象のコードワード画像のコードワード１０３Ｂのブロック１０１Ｂは、検索対象のコードワード画像のードワード１０３Ａのブロック１０１Ａに対応している可能性が高いので、重みｗABは小さい値（この実施の形態の場合０．５）に設定される。
【００８５】
これに対して、図９Ｂと図９Ｃに示されるように、コードワード間距離ＤABが、検索対象のコードワード画像８１Ａのブロック１０１Ａの分散値ＶAより小さく、かつ、対応する比較対象のコードワード画像８１Ｂのブロック１０１Ｂの分散値ＶBより大きい（図９Ｂ）か、または、検索対象のコードワード画像８１Ａのブロック１０１Ａの分散値ＶAより大きく、かつ、対応する比較対象のコードワード画像８１Ｂのブロック１０１Ｂの分散値ＶBより小さい（図９Ｃ）場合、比較対象のコードワード画像のコードワード１０３Ｂのブロック１０１Ｂが、検索対象のコードワード画像のードワード１０３Ａのブロック１０１Ａに対応する可能性は、図９Ａの場合より大きく、図９Ｄの場合より小さいので、重みｗABは、図９Ａに示される場合より小さく、図９Ｄに示される場合より大きい値（この実施の形態の場合１より小さく、０．７５以上の値）に設定される。
【００８６】
なお、ブロックのサンプル数が少ない場合、その分散値は信頼性が低いと考えられる。そこで、コードワード間距離重み演算部７２は、サンプル数を予め設定されている所定の閾値と比較し、サンプル数が閾値以下の場合には、重みｗABを最小の値（図９の実施の形態の場合、０）に設定する。
【００８７】
以上のように、重みを演算し、これにより後述するように重み付けすることで、検索の精度を向上させることができる。
【００８８】
図１０は、以上のようにして演算された重みの例を表している。図１０においては、検索対象のコードワード画像８１Ａのコードワード１に対応する比較対象のコードワード画像８１Ｂのコードワードの重みは、コードワードが１である場合１、コードワードが２である場合１、コードワードが３である場合０．５、コードワードが４である場合０．７５とされている。
【００８９】
以下同様に、検索対象のコードワード画像８１Ａのコードワード２に対応する比較対象のコードワード画像８１Ｂのコードワードの重みは、コードワードが１である場合０．７５、２である場合０．５、３である場合０．７５、４である場合１であり、検索対象のコードワード画像８１Ａのコードワード３に対応する比較対象のコードワード画像８１Ｂのコードワードの重みは、コードワードが１である場合１、２である場合０．５、３である場合１、４である場合０．７５であり、検索対象のコードワード画像８１Ａのコードワード４に対応する比較対象のコードワード画像８１Ｂのコードワードの重みは、コードワードが１である場合１、２である場合０．７５、３である場合１、４である場合０．７５とされている。
【００９０】
ステップＳ５５において、画像間距離演算部６２は画像間距離を演算する。ここで画像間距離とは、ステップＳ４２で取得された検索対象の代表値情報に対する、ステップＳ４８で取得された比較対象の代表値情報の距離を意味する。この演算は、例えば図１１に示されるように行われる。すなわち、図１１の左側に示される、ステップＳ５２で演算された度数分布に、図１１の中央に示される、テップＳ５４で演算された重みを、図１１の右側に示されるように、対応するコードワードの組み合わせ毎に乗算し、その総和を演算することで行われる。
【００９１】
図１１の場合、画像間距離は、以下の式に表されるように２６８．７５となる。
１０×１＋０×１＋２０×０．５＋９０×０．７５
＋５０×０．７５＋１０×０．５＋５×０．７５＋０×１
＋５×１＋１０×０．５＋４０×１＋１０×０．７５
＋１０×１＋８０×０．７５＋０×１＋１０×０．７５
＝１０＋０＋１０＋６７．５
＋３７．５＋５＋３．７５＋０
＋５＋５＋４０＋７．５
＋１０＋６０＋０＋７．５
＝２６８．７５
【００９２】
次に、ステップＳ４６に戻り、読み出し部４１は比較対象の画像信号を全て読み出したかを判定する。まだ処理していない比較対象の画像信号が存在する場合、ステップＳ４７乃至Ｓ５５の処理が繰り返される。
【００９３】
比較対象の画像信号を全て読み出し、検索対象と比較した場合、ステップＳ５６において、最小距離選択部４８は画像間距離が最小の画像信号を選択する。すなわち、最小距離選択部４８は読み出し部４１から供給される比較対象の画像信号から任意の数の画像信号を、検索対象の画像信号と画像間距離が小さい方から順番に選択する。
【００９４】
ステップＳ５７において、表示部４９は選択された画像信号を復号し、それに対応する画像を表示する。このとき表示部４９は、小距離選択部４９から供給される検索対象の画像信号も復号し、それに対応する画像を表示する。ユーザは選択された比較対象の画像を検索対象の画像と見比べ、検索対象の画像と類似する比較対象の画像をさらに選択、指定することができる。
【００９５】
このように、ベクトル量子化により生成されるコードワードの情報である代表値情報としてのコードワード画像を利用して検索することで、検索時における処理が軽減され、迅速な検索処理が可能となる。
【００９６】
以上においては、画像情報を符号化し、検索する場合について説明したが、本発明は音声情報その他の情報を符号化し、検索する場合にも適用することができる。
【００９７】
上述した一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウエアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【００９８】
コンピュータにインストールされ、コンピュータによって実行可能な状態とされるプログラムを格納するプログラム記録媒体は、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)を含む）、光磁気ディスクを含む）、もしくは半導体メモリなどよりなるパッケージメディアであるリムーバブルメディア、または、プログラムが一時的もしくは永続的に格納されるＲＯＭや、ハードディスクなどにより構成される。プログラム記録媒体へのプログラムの格納は、必要に応じてルータ、モデムなどのインタフェースを介して、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の通信媒体を利用して行われる。
【００９９】
なお、本明細書において、プログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１００】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１０１】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１０２】
【図１】本発明の情報処理システムの一実施の形態の構成を示すブロック図である。
【図２】情報検索装置の一実施の形態の構成を示すブロック図である。
【図３】情報保持処理を説明するフローチャートである。
【図４】コードワードを説明する図である。
【図５】検索処理を説明するフローチャートである。
【図６】検索処理を説明するフローチャートである。
【図７】コードワード画像を説明する図である。
【図８】度数分布を説明する図である。
【図９】重みの演算を説明する図である。
【図１０】重みの例を示す図である。
【図１１】画像間距離の演算を説明する図である。
【符号の説明】
【０１０３】
１  情報処理システム，  １１  情報符号化装置，  １２  情報検索装置，  ２２  ベクトル量子化部，  ２３  データベース，  ２４  検索部，  ３１  コードブック生成部，  ３２  代表値情報生成部，  ３３  分布量サンプル数演算部，  ４１  読み出し部，  ４２−１，４２−２  代表値情報取得部，  ４３−１，４３−２  コードブック取得部，  ４４−１，４４−２  分布量取得部，  ４５−１，４５−２  サンプル数取得部，  ４６  距離演算部，  ４７  重み演算部，  ４８  最小距離選択部，  ４９  表示部，  ６１  度数分布演算部，  ６２  画像間距離演算部，  ７１  コードワード間距離演算部，  ７２  コードワード間距離重み演算部
【図１】
2009110210.tif 000003
【図２】
2009110210.tif 000004
【図３】
2009110210.tif 000005
【図４】
2009110210.tif 000006
【図５】
2009110210.tif 000007
【図６】
2009110210.tif 000008
【図７】
2009110210.tif 000009
【図８】
2009110210.tif 000010
【図９】
2009110210.tif 000011
【図１０】
2009110210.tif 000012
【図１１】
2009110210.tif 000013