(57)【特許請求の範囲】
【請求項１】
検索による特徴素としてカラーヒストグラムを利用するマルチメディアの検索システムにおいて、
通常のカラーヒストグラムを求める段階と、
類似の画像間のグループ化が事前に行われた標本集団から前記カラーヒストグラムを構成する各ビンごとに、グループ内の分散と互いに異なるグループ間の分散とを計算する段階と、
前記計算段階で計算されたグループ内の分散が小さくかつグループ間の分散が大きいほど重要であることを表すビンのうち、前記重要の度合いが高いビンになるほど、データシーケンスの先頭に配列してカラーヒストグラムを再構成する段階と、
前記再構成されたカラーヒストグラムをアクセスして比較検索する時、前記再構成された重要の度合いが高いビンの順序によって問合わせカラーヒストグラムと検索対象カラーヒストグラムとの比較検索を行う段階と、
を含むことを特徴とする漸進的なカラーヒストグラム生成方法。
【請求項２】
前記カラーヒストグラムの特徴を決定づけるメタデータとして、カラーヒストグラムのビンがデータシーケンス上に配列される順序を決定するのに使用されるビンの順序情報を含み、前記ビンの順序情報で示される重要なビンの順にビンを選んで問合わせヒストグラムと検索対象ヒストグラムとを比較検索することを特徴とする請求項１に記載のカラーヒストグラム生成方法。
【請求項３】
検索による特徴素としてカラーヒストグラムを利用したマルチメディアの検索方法において、
類似の画像間のグループ化が事前に行われた標本集団から前記カラーヒストグラムを構成する各ビンごとに、グループ内の分散と互いに異なるグループ間の分散とを計算する段階と、前記段階で計算されたグループ内の分散が小さくかつグループ間の分散が大きいほど重要であることを表すビンを、前記カラーヒストグラムのアクセス時に前記重要な順に再構成する段階と、前記重要な順にビンが再構成されたカラーヒストグラムをアクセスして比較検索する時、前記再構成された重要なビンの順序によって問合わせカラーヒストグラムと検索対象カラーヒストグラムとの比較検索を行う段階と、からなることを特徴とするマルチメディアの検索方法。
【請求項４】
検索による特徴素としてカラーヒストグラムを利用したマルチメディアの検索方法において、
類似の画像間のグループ化が事前に行われた標本集団から前記カラーヒストグラムを構成する各ビンごとに、グループ内の分散と互いに異なるグループ間の分散とを計算する段階と、前記段階で計算されたグループ内の分散が小さくかつグループ間の分散が大きいほど重要であることを表すビンのうち、前記重要なビンから順にアクセスされることを表すアクセス順序を、ビンの順序情報として生成する段階と、前記ビンの順序情報を使用し、かつカラーヒストグラムの一部のビンだけを使用して比較検索する場合に、前記ビンの順序情報で示される重要なビンの順にビンを選んで問合わせカラーヒストグラムと検索対象カラーヒストグラムとを比較検索する段階と、からなることを特徴とする漸進的ヒストグラムを利用したマルチメディア検索方法。
【請求項５】
検索による特徴素としてカラーヒストグラムを利用したマルチメディアの検索方法において、
色空間の量子化によって分割された分割領域を意味するカラーヒストグラムのビンをサンプリングし、低い彩度に相当する分割領域であるほどカラーヒストグラムの重要なビンとして再構成する段階と、前記重要な順にビンが再構成されたカラーヒストグラムをアクセスして比較検索する時、前記再構成された重要なビンの順序によって問合わせカラーヒストグラムと検索対象カラーヒストグラムとの比較検索を行う段階と、からなることを特徴とするマルチメディアの検索方法。
【請求項６】
前記カラーヒストグラムが、Ｈｕｅ、ＳＵＭ（ＭＡＸ（ＲＧＢ）＋ＭＩＮ（ＲＧＢ））、ＤＩＦＦ（ＭＡＸ（ＲＧＢ）−ＭＩＮ（ＲＧＢ））から構成されたＨＭＭＤ色空間を使用して、ＨＭＭＤカラースペースが０〜２５５値のＤＩＦＦ値の範囲を有する時、ＤＩＦＦ軸を基準で分割するために指定したＤＩＦＦ値が各々９、２９、７５、２００であり、これらの値に基づいて分割された４個の領域を各々Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５とした時、Ｓ１はＳＵＭに基づいて８等分し、Ｓ２はＳＵＭに基づいて４等分、かつＨｕｅに基づいて８等分し、Ｓ３はＳＵＭに基づいて４等分、かつＨｕｅに基づいて１２等分し、Ｓ４はＳＵＭに基づいて４等分、かつＨｕｅに基づいて１２等分し、Ｓ５はＳＵＭに基づいて２等分、かつＨｕｅに基づいて２４等分して分割するカラーの量子化方法を使用して１８４個のビンとして構成することを特徴とする請求項５に記載のマルチメディアの検索方法。
【請求項７】
前記ヒストグラムの一部によってもマルチメディア検索を行うことができることを特徴とする請求項３または請求項５に記載のマルチメディアの検索方法。
【請求項８】
問合わせヒストグラムと検索対象ヒストグラムとをビンの順序情報によって一つずつ取り出して前記順序情報で示されるビンの順に比較検索することを特徴とする請求項４に記載のマルチメディアの検索方法。
【請求項９】
検索による特徴素としてカラーヒストグラムを利用したマルチメディアの検索方法において、
類似の画像間のグループ化が事前に行われた標本集団から前記カラーヒストグラムを構成する各ビンごとに、グループ内の分散と互いに異なるグループ間の分散とを計算する段階と、前記段階で計算されたグループ内の分散が小さくかつグループ間の分散が大きいほど重要であることを表すビンの前記重要の度合いを示す重要度を、マルチメディア検索のための特徴情報で求める時、比較検索の対象となる各マルチメディア客体ごとに当該カラーヒストグラムを構成するビンの重要度を区別して求める段階と、前記求めたビンの重要度情報を使用して前記重要度の順序に、問合わせカラーヒストグラムと検索対象カラーヒストグラムとを比較検索する段階と、からなることを特徴とする漸進的ヒストグラムを利用したマルチメディアの検索方法。
【請求項１０】
前記構成したビンの重要度の順にヒストグラムを伝送するが、システムまたはネットワークの状況によってヒストグラムの全部または一部だけを伝送することを特徴とする請求項９に記載の漸進的ヒストグラムを利用したマルチメディアの検索方法。
【請求項１１】
検索による特徴素としてカラーヒストグラムを利用したマルチメディアの検索方法において、
類似の画像間のグループ化が事前に行われた標本集団から前記カラーヒストグラムを構成する各ビンごとに、グループ内の分散と互いに異なるグループ間の分散とを計算する段階と、前記段階で計算されたグループ内の分散が小さくかつグループ間の分散が大きいほど重要であることを表すビンの前記重要の度合いを示す重要度を、マルチメディア検索のための特徴情報で、各マルチメディア固有の特性に合わせて各マルチメディア客体ごとに区別して生成する段階と、前記ヒストグラムビンの前記重要度の大きさ順を表す順序情報を生成して保存する段階と、前記重要度の大きさ順にビンが再構成されたカラーヒストグラムをアクセスして比較検索する時、前記順序情報によって問合わせカラーヒストグラムと検索対象カラーヒストグラムとの比較検索を行う段階と、からなることを特徴とする漸進的ヒストグラム情報の構成方法。
【請求項１２】
前記ヒストグラムビンの順序情報は、ヒストグラムの各ビンの順序が並べられている１次元マトリックスの形態であることを特徴とする請求項１１に記載の漸進的ヒストグラム情報の構成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はヒストグラムを利用したマルチメディア検索に関するものである。
【０００２】
【従来の技術】
最近、内容に基づいて録画したビデオ情報などを含む多様なマルチメディアから所望する情報を得るためにそのマルチメディアを検索する技術が現れてきた。その際に問題となるのは何をどのように検索すれば所望の情報を得ることができるかということである。そのため、検索するもの、すなわち検索の性能を左右するマルチメディアの特徴情報に対する研究が活発に行われている。現在、最も多く使用されている検索エンジンにおいては画像検索のために画面の全体的な、又は部分的なカラー情報とテクスチャー情報などを用いている。この中でもカラー情報は画像の検索において最も重要な影響を与える要素であることが知られている。従って、より効果的なカラー特徴情報の開発が行われており、検索により効果的なカラー空間を開発しようとする試みも行われている。
【０００３】
カラー情報ではカラーヒストグラムが最も広く使われる。カラーヒストグラムとは画像などのマルチメディアデータのカラー分布を示す情報であり、カラー空間をどのように量子化するかによってヒストグラムのビン数が決定される。一般的に量子化をより細かく行って多くのカラービンで表現すると検索の性能は増加する。しかし、ヒストグラムの大きさが増加するので、検索の時間が多くかかるという問題がある。特にネットワークを介した検索時にはネットワークの容量によってヒストグラムの大きさが重要な要素として作用する。また、ネットワークの問題によって検索しようとするデータのヒストグラムが伝送される途中で特定の部分で中断された場合、既に伝送されたヒストグラムの一部だけで検索を行えば、検索の性能が低下するという問題がある。そして、ネットワークの環境だけでなくクライアントのシステムの性能や検索の目的等によってはカラーヒストグラムの全部を必要としないで概略的な検索を行う必要もあるが、従来は問合わせ画像と検索対象の画像に対するカラーヒストグラムの全体を比較検索するので、このような要求を充足させることができなかった。また、システムの性能が低い場合、カラーヒストグラムの全部を比較検索することは検索速度を低下することになり、概略的な検索だけでも満足する場合には不要な検索時間が必要であった。
【０００４】
【発明が解決しようとする課題】
本発明はヒストグラムの一部分だけで比較検索しても高い検索の性能を得ることができるようにする。すなわち、ヒストグラムの一部分だけで問合わせ画像と対象の画像を比較検索しても高い検索の性能を得ることができるようにすることが目的である。
また本発明は、ヒストグラムを表現する情報にヒストグラムの重要なビンの順序情報を含めることで、このビンの順序情報を含むヒストグラムの特徴情報の情報を利用してヒストグラムの一部だけを使用しても高い検索の性能を有することができるようにしたヒストグラムとマルチメディアの検索方法を提示する。
【０００５】
【課題を解決するための手段】
本発明は、ヒストグラムの情報構造をヒストグラムの前部だけを利用しても高い検索の性能を保障するようにして、このヒストグラムを利用してマルチメディアを検索するようにしたこと、すなわち、ヒストグラムが時系列的なアクセスの順序に基づいて相対的に重要な情報が先頭にくるようにしたことを特徴とするものである。
本発明は、カラーヒストグラムのビンがヒストグラムの時系列的なアクセスの順序に基づいて重要なビンが相対的に先頭にくるように重要なビンの順に再構成したカラーヒストグラムの構造を有し、この再構成したカラーヒストグラムを利用してヒストグラムビットストリームの前部から漸進的な部分だけを利用した検索ができるようにしたことを特徴とするカラーヒストグラムとマルチメディアの検索方法である。
【０００６】
また、本発明は、マルチメディア客体ごとに当該客体の特性に合わせて最適化した漸進的ヒストグラムを構成してこれを利用したマルチメディアの検索方法を提示する。
さらに、本発明は、マルチメディアの特性を考慮して重要度の順に再順序化した漸進的ヒストグラムを構成して、重要度の順に再順序化してマルチメディアの特性に合わせて最適化した漸進的ヒストグラムを利用してマルチメディアの検索を行う方法を提示する。
さらに、本発明は、マルチメディア客体の検索のための特徴情報としてヒストグラムを利用する時、特にカラーヒストグラムを利用したマルチメディアの検索システムにおいて、カラーヒストグラムの伝送時にヒストグラムの伝送順序上、前部だけ利用しても高い検索の性能を保障するように、各マルチメディアごとにその特性に合わせて最適化した漸進的カラーヒストグラムを構成する方法とこれを利用したマルチメディアの検索方法を提示する。
【０００７】
このような機能は次のように二つの用途に非常に有用である。
まず、前述したようにデータのヒストグラムを伝送する時、伝送の途中にネットワーク環境などの要因によってヒストグラムビットストリームの伝送が中断された場合、既に伝送された一部分のヒストグラムの情報だけで検索しても高い検索の性能を保障できる。そのためにヒストグラムのビンの順序を伝送順序、すなわち前からＮ（Ｎ＜全体ヒストグラムビンの個数）個のビンだけで検索を行っても高い検索の性能を保障できる。二番目の用途はデータを有しているサーバー側で検索の目的とクライアントの環境、ネットワークの環境に基づいてヒストグラムの一部、または全部を伝送するかの可否を定めることによって、各場合ごとに最適の検索を行うことができるという長所がある。例えば、検索の用途がほぼ似たようなデータを検索する場合や、ネットワーク環境が非常に不安定な場合、検索するデータのヒストグラムの全体ではない一部だけを伝送することによって、最小限の検索の性能を保障しながらネットワーク環境に無理なロードがかからないように検索を行うことができる。その反面に、ネットワーク又はコンピュータ環境が非常に優れていて、正確な検索をしようとする場合には、ヒストグラムの全体を伝送することができる。
【０００８】
前述した有用な機能を提供するためにはヒストグラムを構成する各ビンを前からＮ個だけで検索しても、その検索の性能低下が小さくなるようにヒストグラムを最適化することが必要である。そのためにヒストグラムを重要なビン、すなわち検索により多くの影響を与えるビンほどビットストリームの前の方に位置させた構造でヒストグラムを再構成している。このようなビンの再順序化によって、本発明の目的に合わせてヒストグラムを最適化させることができる。
【０００９】
漸進的ヒストグラムとは、マルチメディアの特徴情報としてヒストグラム、例えばカラーヒストグラムのビンの順序を重要度が高い順に再順序化して、このように再順序化されたヒストグラムを重要度が高い順に伝送することを意味する。漸進的ヒストグラムはデータのヒストグラムの伝送時、途中に伝送が中断された場合にも既に受け取った部分だけで検索でき、またこの一部分のヒストグラムを利用しても高い検索の性能を保障できる。なぜならば、まず伝送されたビンがより重要なビンであるので、この一部のビンを利用してもある程度のマルチメディア客体に対する検索ができるからである。
【００１０】
本発明において重要なビンを決定する方法では次のような二つがある。
一番目の方法は、まずデータの標本集団からデータを区分する各ビンの区分力がどのくらい大きいかを統計的に計算して、その区分力が大きいほど重要なビンとする方法である。区分力の決定は標本集団で各ビン別に値の分散を計算して分散が大きいほどより重要なビンであるとすることができる。標本集団に含まれたデータが既に類似のデータ同士がグループ化されているとすると、同じグループ内では分散が小さく、互いに異なるグループのデータの間では分散が大きいほど重要なビンであると考えることができる。理論的に後者の方法がより優れて正確なビンの重要度を抽出できるが、標本集団をあらかじめグループ化することが容易ではないので前者の方法を使用することが一般的であり、この方法も非常に優れた性能を示していることを実験で検証した。
【００１１】
二番目の方法は標本集団なく色空間（カラースペース）の特性を考慮してビンの重要性を検討する方法である。一般的に色空間でカラーをＭ個に量子化する場合、色相、彩度、明るさ等に基づいて各量子化された色の重要度を事前の知識によって大略的に分けられる。通常、彩度が低い領域が高い領域より検索に重要な影響を与え、色相は赤色の領域が青色の領域に比べて高い影響を及ぼす。したがって、万一色空間を彩度に基づいて分割した場合、分割された部分領域の重要度は低い彩度を有する分割領域がより重要となる。すなわち、低い彩度領域に属したビンであるほどより重要であるということができるので、ヒストグラムのビンの再順序化を行う時低い彩度領域に属した領域に該当するビンをより多く前の方に位置させる。例えば、彩度を大きくＳ１、Ｓ２の二つの領域に分けると仮定する。これと共に、Ｓ１がＳ２より低い彩度領域であって、その重要度の比率の程度が２：１であると仮定すれば、ヒストグラムのビンの順序を決定する際に、前の方に位置する分割領域から順に選択する時、Ｓ１が２個選択される時Ｓ２は一つだけを選択するような式の方法でビンの順序を決定できる。
【００１２】
前述した概念に基づいて本発明の特徴を記述すれば次の通りである。
本発明の第１の特徴は、ヒストグラムを利用したマルチメディア検索において、ヒストグラムのアクセス（伝送を含む）の順序を基準として、先頭にくる漸進的な部分だけを利用した検索ができるように、重要なビンの順にヒストグラムを再構成した漸進的ヒストグラムと、これを利用して検索の用途と環境に合せてヒストグラムの部分だけを利用して検索を行う漸進的マルチメディアの検索方法である。
【００１３】
本発明の第２の特徴は、前記第１の特徴で述べた重要なビンの順にヒストグラムを再構成することが、標本集団から計算した各ビンごとのビン値の分散に基づいて計算し、その際、分散が大きいほど重要なビンと見なすことである。
【００１４】
本発明の第３の特徴は、前記第１の特徴で述べた重要なビンの順にヒストグラムを再構成することが、類似の画像間のグループ化が事前に行われた標本集団から各ビンごとにグループ内の分散と互いに異なるグループ間の分散とを計算して、グループ内の分散が小さくてグループ間の分散が大きいほど重要なビンと見なすことである。
【００１５】
本発明の第４の特徴は、前記第１の特徴で述べた重要なビンの順にヒストグラムを再構成することが、色空間の量子化によって分割された分割領域を意味するビンをサンプリングして構成するが、低い彩度に相当する分割領域であればあるほど高い確率で選択されるようにすることによって、低い彩度に相当する分割領域であるほどヒストグラムの前の方に多く現れるように再構成することである。
【００１６】
本発明の第５の特徴は、前記第４の特徴で述べたカラーヒストグラムが、Ｈｕｅ、ＳＵＭ（ＭＡＸ（ＲＧＢ）＋ＭＩＮ（ＲＧＢ））、ＤＩＦＦ（ＭＡＸ（ＲＧＢ）−ＭＩＮ（ＲＧＢ））から構成されたＨＭＭＤ色空間を使用して、ＨＭＭＤカラースペースが０〜２５５値のＤＩＦＦ値の範囲を有する時、ＤＩＦＦ軸を基準として分割するために指定したＤＩＦＦ値は各々９、２９、７５、２００であり、これらの値に基づいて分割された４個の領域を各々Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５とした時、Ｓ１はＳＵＭに基づいて８等分し、Ｓ２はＳＵＭに基づいて４等分、かつＨｕｅに基づいて８等分し、Ｓ３はＳＵＭに基づいて４等分、かつＨｕｅに基づいて１２等分し、Ｓ４はＳＵＭに基づいて４等分、かつＨｕｅに基づいて１２等分し、Ｓ５はＳＵＭに基づいて２等分、かつＨｕｅに基づいて２４等分して分割するカラーの量子化方法を使用して１８４個のビンとして構成することである。
【００１７】
本発明の第６の特徴は、前記第４の特徴で述べたサンプリングの確率を異なるようにするために、第５の特徴で述べたＳ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５の各領域におけるサンプリングの確率を２４：１２：６：２：１に定めることである。
【００１８】
本発明の第７の特徴は、前記第１の特徴で述べた漸進的ヒストグラムを利用したマルチメディアの検索システムにおいて、検索の目的と検索しようとするクライアントのハードウェア的な環境によってヒストグラムを前から全部または一部だけを利用して、クライアントに伝送するか、または検索する漸進的マルチメディアの検索方法である。
【００１９】
本発明の第８の特徴は、前記第１の特徴で述べた漸進的ヒストグラムを利用したマルチメディアの検索システムにおいて、問合わせデータのヒストグラムデータが伝送時予測できない結果によって中断された時、伝送されたヒストグラムデータだけを利用して検索を行うことである。
【００２０】
また本発明の第９の特徴は、ヒストグラムを利用したマルチメディアの検索において、ヒストグラムの伝送順序（ビットストリーム）を基準とする時先頭にくる漸進的な部分だけを利用した検索ができるように、検索エンジンが重要なビンの順序情報を含んでおり、このビンの順序情報を使用してヒストグラムの一部のビンだけを使用して検索し、重要なビンの順にビンを選んで検索に使用する漸進的ヒストグラムを利用したマルチメディアの検索方法である。
【００２１】
本発明の第１０の特徴は、前記第９の特徴で述べた重要なビンの順序情報を構成することが、標本集団から計算した各ビンごとのビン値の分散に基づいて計算し、分散が大きいほど重要なビンと見なすことである。
【００２２】
本発明の第１１の特徴は、前記第９の特徴で述べた重要なビンの順序情報を構成することが、類似の画像間のグループ化が事前に行われた標本集団から各ビンごとのグループ内の分散と互いに異なるグループ間の分散を計算して、グループ内の分散が小さくてグループ間の分散が大きいほど重要なビンと見なすことである。
【００２３】
本発明の第１２の特徴は、前記第９の特徴で述べた重要なビンの順序情報を構成するに際して、色空間の量子化によって分割された分割領域を意味するビンをサンプリングして構成するが、低い彩度に相当する分割領域であるほど高い確率で選択されるようにすることによって、低い彩度に相当する分割領域であるほどヒストグラムの前の方に多く現れるように再構成することである。
【００２４】
本発明の第１３の特徴は、前記第１２の特徴で述べたヒストグラムはＨｕｅ、ＳＵＭ（ＭＡＸ（ＲＧＢ）＋ＭＩＮ（ＲＧＢ））、ＤＩＦＦ（ＭＡＸ（ＲＧＢ）−ＭＩＮ（ＲＧＢ））から構成されたＨＭＭＤ色空間を使用して、ＨＭＭＤカラースペースが０〜２５５値のＤＩＦＦ値の範囲を有する時、ＤＩＦＦ軸を基準で分割するために指定されたＤＩＦＦ値は各々９、２９、７５、２００であり、これらの値に基づいて分割された４個の領域を各々Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５０とした時、Ｓ１はＳＵＭに基づいて８等分し、Ｓ２はＳＵＭに基づいて４等分、かつＨｕｅに基づいて８等分し、Ｓ３はＳＵＭに基づいて４等分、かつあＨｕｅに基づいて１２等分し、Ｓ４はＳＵＭに基づいて４等分、かつＨｕｅに基づいて１２等分し、Ｓ５はＳＵＭに基づいて２等分、かつＨｕｅに基づいて２４等分して分割するカラー量子化方法を使用して１８４個のビンとして構成することである。
【００２５】
本発明の第１４の特徴は、前記第１２の特徴で述べたサンプリングの確率を異なるようにするために、第１２の特徴で述べたＳ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５の各領域でサンプリングの確率は２４：１２：６：２：１に定めることである。
【００２６】
本発明の第１５の特徴は、前記第９の特徴で述べた漸進的ヒストグラムを利用したマルチメディアの検索システムにおいて、検索目的と検索しようとするクライアントのハードウェア的な環境によってヒストグラムを前から全部または一部だけを利用して、クライアントに伝送するか、または検索する漸進的マルチメディアの検索方法である。
【００２７】
本発明の第１６の特徴は、前記第９の特徴で述べた漸進的ヒストグラの検索対象ヒストグラムを利用したマルチメディアの検索システムにおいて、問合わせヒストグラムと検索対象ヒストグラムをそれぞれのビンの順序情報に基づいて再構成した後、このビンの順序情報に基づいて再構成したヒストグラムを互いに比較して検索することである。
【００２８】
本発明の第１７の特徴は、前記第９の特徴で述べた漸進的ヒストグラムを利用したマルチメディアの検索システムにおいて、問合わせヒストグラムと検索対象ヒストグラムをビンの順序情報に基づいて一つずつ取り出してヒストグラムをビンの順に比較検索することである。
【００２９】
本発明の第１８の特徴は、マルチメディアデータごとに当該客体の固有の特性に合わせて最適化した漸進的ヒストグラムを利用してマルチメディア検索を行うことである。ここでマルチメディアごとに固有の特性に合わせて最適化するということは、比較検索の観点によってそれぞれのマルチメディア客体ごとに当該ヒストグラムを構成するビンの重要度を区別して求めるということを意味する。
【００３０】
【発明の実施の形態】
以下、図面を参照しながら本発明の好ましい実施の形態について説明する。
図１は本発明の応用例を示す。ネットワーク環境における問合わせ画像を使用した画像の検索の際に、問合わせ画像に該当するヒストグラム１０１が伝送中に全体が到着する前に中断されてＰ１までだけを受信したと仮定する。クライアントはその受信されたＰ１までのヒストグラムを使用して対象画像のヒストグラム１０２に対してその位置にあるビンだけを使用して類似度を計算する。このようにヒストグラムの一部だけを使用してもある程度の検索の性能を保障することによって、より効果的な検索が可能になる。
【００３１】
図２はヒストグラムの一部だけを利用しても検索の性能が大きく低下されないようにするために、一般的な方法で生成されたヒストグラムのビンを重要度の順に再構成する方法を示す。まず、多様なデータで構成されている標本集団を構成し、その構成された標本集団に該当するデータのカラーヒストグラムを生成する。続いて、生成されたカラーヒストグラムの各ビンの別に分散を求めた後、分散が大きい順にヒストグラムを再順序化する。
【００３２】
図３は一般的な方法で生成したヒストグラムビンの重要度の順に再順序化する他の一つの例を示す。まず、多様なデータで構成されている標本集団を構成するが、事前に類似のデータに対する情報を知ってそれを利用してグループ化する。構成された標本集団に該当するデータのカラーヒストグラムを生成した後、生成されたカラーヒストグラムの各ビン別にグループに属したデータのヒストグラムだけに対して分散を求めたグループ内の分散と、互いに異なるグループに属したデータのヒストグラムだけに対して分散を求めたグループ間の分散を求める。この時、グループ内の分散が小さくてグループ間の分散が大きい順にヒストグラムを再順序化する。
【００３３】
図４は前述した発明を実現した例としてＨＭＭＤカラースペースを使用した漸進的カラーヒストグラムを説明するための図である。ここではＨＭＭＤカラースペースについて記述する。ＨＭＭＤカラースペースはダブルコーン形態で中心軸はＳＵＭ（ＭＡＸ（ＲＧＢ）＋ＭＩＮ（ＲＧＢ））として現われ、これは明るさに該当する。中心から円錐の縁の方に行くほど彩度が高まるがこれはＤＩＦＦ（ＭＡＸ（ＲＧＢ）−ＭＩＮ（ＲＧＢ））で表現される。円錐の角度は色を現し、これは一般的な色相すなわちＨｕｅで表現される。
【００３４】
図５は図４で説明したＨＭＭＤカラースペースを１８４レベルで量子化した例を示す。図で分かるように、まずＤＩＦＦに基づいて５個の部分領域に分割した後、これをＨｕｅとＳＵＭに基づいて再び細分化して全て１８４個の分割領域に表現した。これらは各１８４個のビンから構成されたカラーヒストグラムを生成するものである。
【００３５】
図６は図５で記述した１８４レベルのカラーヒストグラムで、ＤＩＦＦに基づいて５個の部分領域に分割した時、各分割領域で２４：１２：６：２：１の確率比でビンをサンプリングして再順序化した場合に生成された再順序の情報を示す。ここでビンのサンプリングとは、１８４個のビン一つを特定確率で順々に選択し、選択された順にカラーヒストグラムを再順序化することを意味する。したがって、最も早くサンプリングによって選択されたビンは最も重要なビンでなければならない。したがって確率が高ければ早くサンプリングされる確率が大きいので、再順序化する場合にはそれだけ前の方に位置する可能性が高い。例えば最も彩度が低い二つの分割領域は図５の例で各々８個と３２個の細部分割領域から構成されるが、本発明の実施形態における確率比は２４：１２であるので、最初の領域で２個ごとに一つがサンプリングされると、次の領域では４個ごとに一つがサンプリングされて最初の領域で４個、次の領域で８個のサンプリングが行われる。
【００３６】
図７は本発明を適用して漸進的なカラーヒストグラムを構成した時、１６個、３２個、６４個、１２８個のビンだけを使用した時の性能の変化を示す。この時、各Ｎ個のビンを使用した時のビン値を一般的な小数で表現しないで、本例では空間効率のためにｎ個のビットでビン値を量子化して表現した。例えば、ビン値を１ビットと表現するという意味は０から１の間の小数値を特定臨界値に基づいて０または１と表現することを意味する。したがって１ビットで表現された１６個のビンとして構成される場合、検索に使われたヒストグラム情報の全体のビット数は１６ビットになる。この実験では各Ｎ個のビンを選択した実験別に１ビット、２ビット、４ビットでビン値を表現して性能を求めた。図７において、最初の列は選択したビン数を表し、三番目の列はそのビン値をｎビットと表現して全体が何ビットのヒストグラムの情報を使用したかを表し（ビン値も量子化するという意味である）、中間の列は性能を表現している。同じビン数に対して各々４ビット、２ビット、１ビットで表現した場合が示されている。例えば、ビン数１８４の場合、４ビットで表現した場合（全体ビット数７３６）、２ビットで表現した場合（全体ビット数３６８）、１ビットで表現した場合（全体ビット数１８４）の各々に対して示されており、中間の列の性能は数値が低いほど優秀な場合を意味する。図から分かられるように、ビン値は４ビット程度だけで表現しても高い性能を現し、全体のカラーヒストグラムで検索に使用したビン数が小さいほど性能が低下しても、その低下幅はさほど大きくなかったことが分かられる。
【００３７】
前述したように、ヒストグラムを構成する各ビンを重要な順に並べる方法は多量のマルチメディアデータのヒストグラムを統計的に分析して得ることもできる。しかし、マルチメディアデータは非常に多様であるので、特定のマルチメディアグループでは非常に重要なビンといっても、このビンが他のマルチメディアグループではそれほど重要でない場合もある。したがって、各マルチメディアデータの特性を反映して各マルチメディアデータごとに最適化した他のビンの順に構成したヒストグラムを使用することによって、より高い検索の性能を得ることができる。
【００３８】
ビンの再順序化はマルチメディアの種類と関係なく共通的に適用できるように統計的方法を使用することもできる。しかし、その場合、マルチメディアごとにそれぞれ異なる固有の特性が反映できなかったので、その性能にはある程度の限界がある。したがって、より最適化した漸進的ヒストグラムを生成しようとする場合、各マルチメディア客体ごとにその特性に適切な異なる漸進的ヒストグラムを生成して利用しなければ各マルチメディア客体に最適化した検索を行うことができない。ここで、その特性に適切な異なる漸進的ヒストグラムとは、マルチメディアごとの特性を考慮して重要度の順に再順序化したヒストグラムを意味する。すなわち、マルチメディアの特性を反映した特性によって再順序化したヒストグラムであり、したがって、この場合ヒストグラムを構成するビンの順序は各マルチメディア客体ごとに異なる。このように最適化した漸進的ヒストグラムを構成するためには、まず各マルチメディアごとにその客体を比較検索する観点から各ビンの重要度を求めることが必要である。このように各マルチメディアのビンの重要度は使用者のフィードバックを利用して求めたり、あらかじめグループ化した場合、グループの情報を利用して求めることができる。
【００３９】
まず、使用者のフィードバックを利用した方法について説明する。ここで使用者のフィードバックとは、ある客体を得ようとして問合わせ、同様な客体を検索しようとする時、検索の結果から使用者が類似の客体と類似していない客体に対する情報をフィードバックとしてシステムに知らせる行為をいう。例えば、画像検索の場合、最初の検索結果から使用者が探そうとした画像と類似の画像とそうでない画像とをシステムに使用者が伝達する（使用者のフィードバック）。このような使用者のフィードバックを受信したシステムは、使用者が類似しているあるいは類似していないとフィードバックした情報を使用して当該客体のヒストグラムを構成する各ビンの重要度が計算できる。
【００４０】
ビンｉの重要度（ｗi）を求める方法は次の通りである。
Ｗi＝ａｆI（ｉ）＋ｂｆR（ｉ）
ここで、ａ、ｂは常数であり、ｆI（ｉ）＝（ｐｍi）／ｑｖi（ビンのｉに対する類似の画像間の類似の程度）、ｆR（ｉ）＝ｐｍi×ｑｖi（ビンのｉに対する非類似の画像間の非類似の程度）、ｐ、ｑは常数で、ｍiは当該画像グループ内でのビンｉ値の平均、ｖiは当該画像グループ内でのビンｉ値の分散である。前記のようなビンｉの重要度（ｗi）において、フィードバックされた画像が類似の画像だけであるとか、または非類似の画像だけである場合、常数ａ、ｂの中でいずれかを０と設定することによって各要素の重要度を求めることができる。
【００４１】
図８はヒストグラムの一部だけを利用しても検索の性能が大きく低下しないようにするために、使用者のフィードバックを利用したヒストグラムの再順序の情報を求める順序を示す。この方法では、使用者のフィードバックから再順序化しようとする客体の類似客体に対する情報を受け取った後、ヒストグラムの各ビン別に他の類似の客体の当該ビンとの類似度を測定する。このように計算した類似度に比例して各ビンの重要度が増加し、あらゆる類似の客体に対してこのような重要度の学習をあらゆるビンに対して計算すれば、あらゆるビンに対して重要度が大きい順にビンの再順序化の情報を計算することができる。
【００４２】
図８をより詳しく説明する。段階２０１は初期の検索結果に対する使用者からのフィードバック（類似しているあるいは類似していない）を受け取る段階である。段階２０２は使用者のフィードバックによる類似／非類似のマルチメディア客体情報を受け取る段階である。次の段階２０３では最初の類似／非類似のマルチメディア客体を対象客体として指定して、次の段階２０４ではＩビン＝０と設定する。そして、続いて、段階２０５では問合わせ客体と対象客体のＩ番目のヒストグラムビン値を比較して類似度（Ｓｉ）を測定して、Ｉビンの重要度値をその類似度（Ｓｉ）だけ増加させる（段階２０６）。類似度の測定と測定した類似度だけＩビンの重要度値を増加させる一連の過程をＩが全体のビン数に達するまで繰り返す（段階２０７、２０８）。以上のようにして当該客体に対するＩビンの重要度値を生成完了して、次の客体がなければ既に求めた重要度の順にヒストグラムの順序情報を設定し（段階２０９、２１０）、次の客体がさらにあれば対象客体を次の類似／非類似の客体として設定し、Ｉビン＝０から始めて類似度（Ｓｉ）の測定と重要度値の生成段階を繰り返す（段階２０９、２１１）。
【００４３】
次に、グループ化情報を利用する方法を説明する。より効率的なマルチメディアの検索のために各マルチメディア客体ごとに同じクラスに属する他のマルチメディア客体のグループ情報を含める。または特定データベース内に属するマルチメディア客体を事前に同じクラス同士グループ化することもできる。このように同じクラスのグループに対する情報がある場合にはこの情報を使用して各ビンの重要度を自動的に求めることができる。すなわち、同じクラスに属するマルチメディア客体は前述した使用者のフィードバックで類似の客体にフィードバックされた情報と同一であるので、これらの客体のヒストグラムを前記重要度（ｗi）の計算方法を適用して同じ方法でビンの重要度を求めることができる。
【００４４】
図９はヒストグラムの再順序情報を求める他の一つの方法で、使用者のフィードバックの代わりにグループ化情報を使用する方法の順序を示す。この方法では、再順序化しようとする客体の類似客体に対する情報を既に事前に行われたグループ情報から受け取る（段階３０１）。以後の過程は前記図８で説明した方法と同様に行われる。すなわち、再順序化しようとする客体の中で類似の客体に対する情報を既に行われたグループ情報から得て、類似／非類似のマルチメディア客体情報を受け取り（段階３０２）、最初の類似／非類似のマルチメディア客体を対象客体として指定して（段階３０３）、Ｉ＝０からＮまでのヒストグラムビン値の類似度も測定し、当該Ｉビンの重要度値を類似度（Ｓｉ）だけ増加させて（段階３０４〜３０８）、次の客体がさらになければ前記求めた重要度の順にヒストグラムの順序情報を設定して（段階３０９、３１０）、次の客体がさらにあれば３０４の段階から繰り返す（段階３０９、３１１）。
【００４５】
このように生成したヒストグラムを使用して互いに比較検索するためには、どんな重要度によってどんな順序でビンが再順序化されたかを示す順序情報を有することが必要である。例えば、二つの画像の類似度をヒストグラムを使用して計算する場合を検討する。この場合に二つのヒストグラムの順序が互いに異なるので、互いにマッピングされるビンの間で比較できるためにはビンの順序情報をヒストグラムの特性情報として有していなければならない。そうしてこそ、ヒストグラムの順序が異なっても、どんな重要度によって再順序化されたビン同士の比較ができるからである。
【００４６】
図１０はヒストグラムと再順序情報から構成されたマルチメディア客体の特徴情報の構造を示す。マルチメディア客体の特徴情報の構造４００がそのマルチメディアの特徴情報としてのヒストグラム情報４０１と、ヒストグラムの各ビンの順序がどんな重要度によって並べているかを示す再順序情報の構造４０２を有している。ここで再順序情報はヒストグラムの各ビンの順序が並べられている１次元マトリックスの形態である。
【００４７】
【発明の効果】
以上のように、本発明はヒストグラムを利用したマルチメディア検索において、ヒストグラムの一部分だけで比較検索しても高い検索の性能を得ることができる。特に、データのヒストグラムの伝送時に途中で伝送が中断された場合、既に伝送された部分だけで検索しても高い検索の性能が保障できる。また、本発明はデータを有しているサーバー側で検索の目的とクライアントの環境、ネットワークの環境によってヒストグラムの一部、または全部を伝送するのかの可否を決定することによって、各場合ごとに最適の検索を行うことができるという効果がある。本発明はヒストグラムを利用したマルチメディア検索において、各マルチメディア客体ごとにその特性に最適化した漸進的ヒストグラムを使用することによって、ヒストグラムの一部分だけで比較検索しても高い検索の性能を得ることができるという効果がある。さらに、本発明は客体ごとに異なる特性を漸進的ヒストグラムの再順序情報を考慮することによって、非常に高い性能はもちろん客体中心の検索サービスを提供する。
【図面の簡単な説明】
【図１】  本発明を説明するためのヒストグラムビンの伝送ストリームを示す図である。
【図２】  本発明でカラーヒストグラムの再構成方法の第１実施の形態を説明するためのフローチャートである。
【図３】  本発明でカラーヒストグラムの再構成方法の第２実施の形態を説明するためのフローチャートである。
【図４】  本発明を適用するカラースペース（色空間）の一例として、ＨＭＭＤカラースペースを示す図である。
【図５】  ＨＭＭＤの断面から見た１８４レベルの量子化方法を説明するための図である。
【図６】  本発明で１８４ビンから構成されたカラーヒストグラムの再順序情報の例を示す図である。
【図７】  本発明を利用して部分比較検索を行った時の性能の比較例を示す図である。
【図８】  本発明でヒストグラムの再順序情報を求める方法の第３実施の形態を示すフローチャートである。
【図９】  本発明でヒストグラムの再順序情報を求める方法の第４実施の形態を示すフローチャートである。
【図１０】  は本発明でヒストグラムと再順序情報から構成されたマルチメディア客体の特徴情報の構造を示す図である。
【符号の説明】
１０１  問合わせヒストグラム
１０２  対象ヒストグラム
【図１】
0003701888.tif 000002
【図２】
0003701888.tif 000003
【図３】
0003701888.tif 000004
【図４】
0003701888.tif 000005
【図５】
0003701888.tif 000006
【図６】
0003701888.tif 000007
【図７】
0003701888.tif 000008
【図８】
0003701888.tif 000009
【図９】
0003701888.tif 000010
【図１０】
0003701888.tif 000011