(57)【要約】【課題】ヒストグラムを利用したマルチメディアの検索において、互いに異なるビットの数でビンの値を非正規に量子化して構成したヒストグラムの間でも比較可能な相互運用性を提供して、一部のビットだけを使用した時一定の性能を維持するための漸進的なビットプロセシングを提供するヒストグラムの構成方法を提供するものである。【解決手段】ヒストグラムのビン値を量子化してＮ個のビットで表現する時、互いに異なるビット数で表現されたヒストグラム間の比較ができるように相互運用性を保障するためにＮ個のビット数で表現する時使用した臨界値は、必ずＮ’（＜Ｎ）個のビット数で表現する時に使用した臨界値を全て含むようにし、ヒストグラムのビン値を量子化してＮ個のビットで表現する時、Ｎより小さな数のビットだけを利用して検索できる漸進的なビットプロセシングができるようにするために、Ｎ番目のビットは（Ｎ−１）番目のビットに分割された各領域を各々両分することを意味するようにビン値を量子化して表現した。【選択図】  図１
2005018802.tif 000002
【特許請求の範囲】
【請求項１】
ＨＭＭＤカラースペースのｄｉｆｆ側の区間を決定する臨界値を表現するのにおいて、Ｎ個のビート数で表現する時使用する臨界値などが Ｎ’(Ｎ’＜Ｎ)個のビート数で表現する時使用する臨界値を含むようにすることを特徴とするヒストグラムの量子化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はヒストグラムを利用したマルチメディアの検索に関するもので、より詳しくは、互いに異なるビット数でビン値を量子化して構成したヒストグラムの間でも比較可能な相互運用性を提供して、各ビン値を構成する全体のビットの中から時系列的な順によって、先頭から一部のビットだけを使用した場合にも一定の性能を維持することができる漸進的なビットプロセシングを提供するためのヒストグラムの構成方法に関するものである。
【背景技術】
【０００２】
最近、内容に基づいて録画したビデオ情報などを含む多様なマルチメディアから所望する情報を得るためにそのマルチメディアを検索する技術が現れてきた。その際に問題となるのは何をどのように検索すれば所望の情報を得ることができるかということである。そのため、検索するもの、すなわち検索の性能を左右するマルチメディアの特徴情報に対する研究が活発に行われている。現在、最も多く使用されている検索エンジンにおいては画像検索のために画面の全体的な、又は部分的なカラー情報とテクスチャー情報などを用いている。この中でもカラー情報は画像の検索において最も重要な影響を与える要素であることが知られている。従って、より効果的なカラー特徴情報の開発が行われており、検索により効果的なカラー空間を開発しようとする試みも行われている。
【０００３】
カラー情報ではカラーヒストグラムが最も広く使われる。カラーヒストグラムとは画像などのマルチメディアデータのカラー分布を示す情報であり、カラー空間をどのように量子化するかによってヒストグラムのビン数が決定される。一般的に各ビン値は小数で表現するが、より高い性能と空間的な効率のために小数の表現空間より小さなＮ個のビットで表現して使用している。例えば、一般的に８ビット、すなわち０から１の間の小数を２５６種類の値に区分される数値で表現すれば性能の低下なく十分に空間を節約できることが明らかになった。このようにビン値を量子化する方法としては正規の量子化と非正規の量子化に分けて考えることができる。正規の量子化の方法は０から１間の値を均等な幅で分けて量子化して表現することであり、非正規の量子化の方法は均等でない幅で分けて量子化して表現することである。
【０００４】
非正規の量子化の方法を使用する場合、正規の量子化の方法を使用するか、または小数値をそのまま表現した場合より高い性能を実現できる。例えば重要なビン値の区間はより細かく分けて区分の能力のない値の区間はより疎に分けることによって性能を高めることができる。例えば、ヒストグラムの場合に大部分のビン値が０．２より小さな数で構成されているので、０．２以上を細かく分けることは意味がない。このような理由として非正規化の量子化を利用したビン値の量子化は非常に有効なものとして使用できるが、次のような問題点が発生する可能性がある。
【０００５】
相互運用性の問題：互いに異なる個数で量子化されたビン値の間の比較が難しい。例えば、あるヒストグラムは４ビットで各ビン値を表現したために２4 ＝１６個でビン値を量子化して表現され、他のヒストグラムは２ビットで各ビン値を表現したために２2 ＝４個でビン値を量子化した場合は、これら値に対する比較は各ビンの量子化方法に関する情報がなければ不可能になる。したがって特定の規約による量子化の方法を使用することによって、互いに異なる個数で量子化されたビン値の比較が可能な相互運用性を保障しなければならない。
【０００６】
漸進的なビットプロセシングの問題：カラーヒストグラムがネットワークなどを介して伝送される時、カラーヒストグラムのコーディングスキームに基づいてビンの順で伝送することもでき、また、ビンを構成するビットの順で伝送することもできる。ビンの順で伝送する場合、最初のビンを構成するあらゆるビットがまず伝送された後に次のビンが伝送される。ビットの順で伝送する場合には一番目のビンの一番目のビットが伝送された後、二番目のビンの一番目のビットが伝送される。このように各ビン値を表現するあらゆる一番目のビットが伝送された後に各ビン値を表現するあらゆる二番目のビットが伝送される。このようなコーディングスキームにおいて、万一ヒストグラムが完全に伝送される前に伝送が中断された場合は、既に受け取った部分だけでもヒストグラムの比較ができなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、ヒストグラムを利用したマルチメディアの検索において、互いに異なるビット数でビン値が非正規に量子化されたヒストグラムの間でも相互に比較ができるようにし、且つビットの順でヒストグラムを伝送する時、前に受け取った順の一部だけを使用してもヒストグラムを比較可能にすることが目的である。
【課題を解決するための手段】
【０００８】
前述の目的を達成するために、本発明はヒストグラムを利用したマルチメディアの検索において、ヒストグラムのビン値を量子化してＮ個のビットで表現する時、互いに異なるビット数で表現されたヒストグラム間の比較ができるように相互運用性を保障するために、Ｎ個のビット数で表現する時使用した臨界値は、必ずＮ’（＜Ｎ）個のビット数で表現する時使用した臨界値を全て含むようにすることを特徴とする。
【０００９】
また、本発明は前記相互運用できるようにデザインしたヒストグラムを使用して互いに異なるビット数で表現されたヒストグラムの間で比較を行う時、二つのヒストグラムが、いずれかはＭ、他の一つはＮ（Ｍ＞Ｎ）個のビット数でビン値を表現するとき、少ないビット数Ｎで表現した値で他の一つのビン値を調整して比較することを特徴とする。
【００１０】
また、本発明は前記ビン値の調整がＭ個のビット数で表現する時使用した臨界値（ＴＨ１）の中で、Ｎ個のビット数で表現する時使用する臨界値（ＴＨ２）を除いた余りの臨界値に対して、Ｎ個のビット数で表現する時使用する二つの臨界値の間に存在する前記臨界値（ＴＨ１）により区分されるビン値を足して調整を行うことを特徴とする。
【００１１】
さらに、本発明は前記相互運用できるヒストグラムがＨＭＭＤ色の空間を分割してヒストグラムで構成し、
この時（ａ）  １ビットのビン値を表現するために一つの臨界値２．５／３１０．０を使用して二つのビン値のインデックスを生成し、
（ｂ）  ２ビットのビン値を表現するために３個の臨界値２．５／３１０．０、９．１／３１０．０、３０．０／３１０．０を使用して４個のインデックスを生成し、
（ｃ）  ４ビットのビン値を表現するためにビン値が０．０の値を一つのインデックスに定めて、０と０．６／３１０．０の区間を２等分して２個のインデックスを生成し、０．６／３１０．０と２．５／３１０．０の区間に１個のインデックスを生成して、２．５／３１０．０と１９．０／３１０．０の区間に５個のインデックスを生成して、１９．０／３１０．０と８５．０／３１０．０の区間に６個のインデックスを生成し、８５．０／３１０．０以上の値を一つのインデックスで指定することによって１６個のインデックスを生成し、及び
（ｄ）  ６ビットのビン値を表現するためにビン値が０．０の値を一つのインデックスに定めて、０と０．６／３１０．０の区間を４等分して４個のインデックスを生成し、０．６／３１０．０と２．５／３１０．０の区間を４等分して４個のインデックスを生成し、２．５／３１０．０と１９．０／３１０．０の区間を１０等分して１０個のインデックスを生成し、１９．０／３１０．０と８５．０／３１０．０の区間を３０等分して３０個のインデックスを生成し、８５．０／３１０．０と１２１．０／３１０．０の区間を１４等分して１４個のインデックスを生成して、１２１．０／３１０．０以上の値を一つのインデックスで指定することによって１個のインデックスを生成することを特徴とする。
【００１２】
また、本発明はヒストグラムを利用したマルチメディアの検索において、ヒストグラムのビン値を量子化してＮ個のビットで表現する時、Ｎより小さな数のビットだけを利用して検索できる漸進的なビットプロセシングができるようにするために、Ｎ番目のビットは（Ｎ−１）番目のビットに分割された各領域を各々両分することを意味するようにビン値を量子化して表現することを特徴とする。
【００１３】
さらに、本発明は前述した漸進的なビットプロセシングができるようにビン値を表現したヒストグラムをエンコーディングする時、あらゆるビンの１番目のビットだけをまず並べて、次の二番目のビットを並べる順でヒストグラムをエンコーディングすることを特徴とする。
【００１４】
さらに、本発明は前述した漸進的なビットプロセシングが可能なヒストグラムを使用するマルチメディアの検索において、検索の用途とクライアントの環境に基づいてヒストグラムの一部だけを使用することによって、最適の検索を行うことができるマルチメディア検索システムを特徴とする。
【発明の効果】
【００１５】
本発明はヒストグラムを利用したマルチメディアの検索において、ビン値を小数のビットで表現することによって空間的な効率を考慮して、互いに異なるビット数でビン値を量子化したヒストグラム間の比較検索が可能な相互運用性を提供することができる。それによって一つのサーバーではないインターネット上のあらゆるサーバー間の自由な比較検索ができるようになるという効果がある。本発明の他の一つの長所は、ビン値を量子化して制限されたビット数で表現する時、一部のビットだけで検索を行ってもある程度以上の検索性能を期待することができるようになり、ネットワーク上の問題による伝送中断時にも検索ができ、また検索の用途やクライアントの環境に適当な検索サービスを行うことができるという効果がある。
【発明を実施するための最良の形態】
【００１６】
以下、図面を参照しながら相互運用性と漸進的なビットプロセシングとの、二つの目的を達成するための本発明のビン値の非正規に量子化されたヒストグラムの構成方法とこのヒストグラムを利用したマルチメディアの検索について説明する。
【００１７】
まず、本発明により相互運用性が行われることについて説明する。
マルチメディアデータのヒストグラムの情報は各用途ごとに区別して量子化することができ、同様に各ビン値を表現する方法においても区別してビン値を量子化することができる。例えば、特定の応用では４ビットでビン値を表現すれば十分であるが、他の応用では８ビットで表現しなければ用途に合わせて使うことができない。これら間の類似度を計算できるようにするためには、少なくても同じ４ビットで比較した結果の程度は保障すべきであるが、非正規の量子化では量子化の方法が多様なので互いに異なる量子化の方法を使用した時これら間の比較が不可能である。
したがって本発明ではこれら間の相互運用ができるようにビン値を量子化する方法を提案する。
【００１８】
図１では相互運用が可能なビン値の量子化の例を示す。図１において、１０１は１ビットの表現であるので特定の臨界値（ＴＨ１）を基準としてビン値を０または１で表現する。このような方法で表現したヒストグラムと比較可能な２ビットの表現が図１の１０２に示されている。すなわち図１において、２ビットの表現は、１０１で示されている臨界値（ＴＨ１）を一つの臨界値として含み、他の２個の臨界値（ＴＨ２、ＴＨ３）をさらに使用して４種類のビン値を表現している。２ビットのヒストグラムを１ビットで表現されたヒストグラムと比較しなければならない場合、１ビットの表現方法で使用した臨界値（ＴＨ１）がそのまま２ビットの表現に含まれているので、他の部分を単純に足すことによって２ビットの表現を１ビットの表現と同じになるように調整できる。本例では４個の区間（１０２ａ、１０２ｂ、１０２ｃ、１０２ｄ）の中で２区間（１０２ｂ）、３区間（１０２ｃ）、４区間（１０２ｄ）を全て足せば１０１の表現と同じようになる。このようにより少ない区間で分けた時の臨界値を全て含めて、他の臨界値をさらに使用して区間をより細かく量子化すれば互いに異なるビット数で表現されたビン値でも、それらを小さなビット数の表現で調整した後に比較することができる。
【００１９】
次に、本発明により漸進的なビットプロセシングを行うことについて説明する。図２はマルチメディアデータをヒストグラムで表現して、これをビットの優先順で伝送する様子を示す。図示したように、ヒストグラムの伝送時に各ビンの順でなくあらゆるビンの（ビン１〜ビンＮ）の最初ビットがまず伝送された後に、二番目のビットが伝送されるコーディングスキームを考える。このような方法では、万一図３に示すように完全に伝送される前に伝送が中断された場合は、既に受け取った部分だけでも検索を行うことができる。この時ある程度の性能を保障するためには、各ビンをＮ個のビットでビン値の量子化を行って表現する時、最初のビットから各ビットが表現できる最適の情報を表現しなければならない。そのためには、次のようにビン値を量子化することを考える。１ビットでビン値を表現すると仮定すれば０または１の二つの値でビン値を表現することになる。その際、臨界値としては区別するのに最も相応しいと考えられる一つの最適化した値を使用することになる。そして、２ビットで表現するならば、四つの値でビン値を表現することになるが、最も高い性能を示すことができると考えられる３個の最適な値を使用することになる。この時、その一つを１ビットの時の臨界値を用いると、万一２ビットの中で一つのビットだけを使用しなければならない場合にも、優れた性能を期待することができる。したがって２ビットでビン値を表現する場合３個の臨界値の中の一つは１ビットでビン値を表現した時の一つの臨界値でなければならない。
【００２０】
また、最初のビットで現すのは図４に示すように前述した１ビットの臨界値を基準として分けることを意味し、２番目のビットが現すことは１番目のビットで両分された値の領域を再び各々両分することを意味する。このようにＮ番目のビットの意味は（Ｎ−１）番目のビットで分割されたそれぞれの領域をさらに両分することを意味する。
【００２１】
すなわち、図４から見ると、１ビットでビン値を表現する場合（４０１）、一個の臨界値（Ｔｈ１）を基準として分ける。２ビットでビン値を表現する場合（４０２）には、前で使用した臨界値（Ｔｈ１）を含んで、臨界値（Ｔｈ１）で分けられたそれぞれの領域を再び臨界値（Ｔｈ２、Ｔｈ３）で両分し、３ビットでビン値を表現する場合（４０３）には前に使用した臨界値（Ｔｈ１、Ｔｈ２、Ｔｈ３）を全て含んで、臨界値（Ｔｈ１、Ｔｈ２、Ｔｈ３）で分けられたそれぞれの領域を再び臨界値（Ｔｈ４、Ｔｈ５、Ｔｈ６、ＴＨ７）で両分した。このように漸進的なビットプロセシングができるようにビン値を量子化して少ないビット数で表現すればヒストグラムを伝送する時、伝送の途中で伝送が中断されても既に受け取った部分だけである程度以上の検索性能を保障できる。また検索の用途によってヒストグラムのビン値を全体ビット数より少ない一部だけを使用して検索することもできる。すなわち、検索の用途として高い性能より速くて少ないデータの量が重要である場合、一部だけを使用して検索できる。この時、本発明においては一部だけを使用しても全体のビンの情報を全て表現することができるので優れた性能を期待することができる。
【００２２】
図５は前述した発明を実現した例としてＨＭＭＤカラースペースを使用した漸進的なカラーヒストグラムを説明するためのカラースペースを示している。ＨＭＭＤカラースペースはダブルコーン模様のカラースペースであり；その中心軸はＳＵＭ（［ＭＡＸ（ＲＧＢ）＋ＭＩＮ（ＲＧＢ）］／２）として示されている。これは明るさに該当する。中心から円錐の端の方に行くほど純度が高まるが、これはＤＩＦＦ（ＭＡＸ（ＲＧＢ）−ＭＩＮ（ＲＧＢ））として示されている彩度を表している。円錐の角度は色を示して、これは一般的なＨｕｅ（色相）を表す。図６は図５で説明したＨＭＭＤカラースペースを１８４レベルで量子化した例を示す。図に示すように、まずＤＩＦＦを基準として５個の部分領域に分割した後、これをＨＵＥとＳＵＭを基準として再び細分化して全てで１８４個の分割領域に分割した。これらは各１８４個のビンとして構成されたカラーヒストグラムを次のように生成する。まず、１ビットのビン値を表現するために一つの臨界値２．５／３１０．０を使用して二つのビン値のインデックスを生成する。そして、２ビットのビン値を表現するために３個の臨界値２．５／３１０．０、９．１／３１０．０、３０．０／３１０．０を使用して４個のインデックスを生成する。また、４ビットのビン値を表現するためにビン値が０．０の値を一つのインデックスと定めて、０と０．６／３１０．０の区間を２等分して２個のインデックスを生成し、０．６／３１０．０と２．５／３１０．０の区間に１個のインデックスを生成し、２．５／３１０．０と１９．０／３１０．０の区間に５個のインデックスを生成し、１９．０／３１０．０と８５．０／３１０．０の区間に６個のインデックスを生成し、８５．０／３１０．０以上の値を一つのインデックスに指定することによって、１６個のインデックスを生成する。一方、６ビットのビン値を表現するためにビン値は０．０の値を一つのインデックスに定めて、０と０．６／３１０．０の区間を４等分して４個のインデックスを生成し、０．６／３１０．０と２．５／３１０．０区間を４等分して４個のインデックスを生成し、２．５／３１０．０と１９．０／３１０．０の区間を１０等分して１０個のインデックスを生成し、１９．０／３１０．０と８５．０／３１０．０の区間を３０等分して３０個のインデックスを生成し、８５．０／３１０．０と１２１．０／３１０．０の区間を１４等分して１４個のインデックスを生成し、１２１．０／３１０．０以上の値を一つのインデックスに指定することによって、１個のインデックスを生成する。
【図面の簡単な説明】
【００２３】
【図１】相互運用が可能なビン値の量子化の例を説明するための図面である。
【図２】カラーヒストグラムで表現されたマルチメディアデータをビットの優先順位で伝送する様子を説明するための図面である。
【図３】伝送が中断されたカラーヒストグラムを利用した部分検索を説明するための図面である。
【図４】臨界値とカラーヒストグラムデータとの関係を説明するための図面である。
【図５】本発明を適用したＨＭＭＤカラースペースを示す図面である。
【図６】ＭＭＤの断面からみた１８４レベルの量子化の方法を説明するための図面である。
【図１】
2005018802.tif 000003
【図２】
2005018802.tif 000004
【図３】
2005018802.tif 000005
【図４】
2005018802.tif 000006
【図５】
2005018802.tif 000007
【図６】
2005018802.tif 000008