説明

ヒストグラム近似復元装置及びヒストグラム近似復元方法、並びに画像検索装置及び画像検索方法

【課題】ランレングス符号化圧縮した画像データの離散的な画素値ヒストグラムから原画像の連続的な画素値ヒストグラムを近似復元する方法を提供する。近似復元した画素値ヒストグラムを用いて画像検索する方法および装置を提供する。
【解決手段】
圧縮画像データにおける画素値Ciに対応する画素値度数Liを算出することにより離散ヒストグラムデータを生成し、画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明はランレングス符号化された画像データから、原画像の画素値のヒストグラムを近似的に復元するヒストグラム近似復元技術、及び、近似復元された画素値ヒストグラムを用いて画像検索を行う画像検索技術に関する。
【背景技術】
【0002】
多数の画像データの中から基準画像と同一の画像データを探し出す画像検索が、各種のアプリケーションで必要とされる。圧縮画像についても同様である。従来、圧縮画像について画像検索を行うためには、圧縮画像を元の画像データに戻して(復号して)、復号された画像データを基準画像のデータと直接比較する必要があったが、復号に時間を要するので、高速検索には不向きであった。そこで、近年は画像データを直接比較するのではなく、検索画像中の各画素値の出現頻度(画素値ヒストグラム)と基準画像の画素値ヒストグラムの類似度を求めて、画像検索を行う方法が各種提案されている(例えば、特許文献1)。
【特許文献1】特開2002−150287号公報
【特許文献2】特開2004−312693号公報
【特許文献3】特開2003−312693号公報
【非特許文献1】鎌田清一郎,「ヒルベルト走査を利用した濃淡画像の情報圧縮に関する考察」,電子情報通信学会論文誌,Vol.J80-D-II,No.2,pp.426-433,1997年2月
【発明の開示】
【発明が解決しようとする課題】
【0003】
しかしながら、ランレングス符号化された画像データは、画素値を量子化しているので、この画像データから画素値ヒストグラムを作成すると、図5に示すような離散的なヒストグラムになる。一方、基準画像のヒストグラムは図7に示すような連続的なヒストグラムになる。このような、外見が全く異なるヒストグラム同士を直接比較しても、一致点が少ないので、基準画像に類似する画像データを発見することは出来なかった。
【0004】
そこで、本発明は、ランレングス符号化圧縮した画像データの離散的な画素値ヒストグラムから原画像の連続的な画素値ヒストグラムを近似復元する方法を提供することを目的とする。また、近似復元した画素値ヒストグラムを用いて画像検索する方法および装置を提供することを目的とする。
【課題を解決するための手段】
【0005】
本発明に係るヒストグラム近似復元装置の第1の構成は、圧縮画像記憶手段に記憶された、原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)から、前記原画像の画素値ヒストグラムを近似的に復元するヒストグラム近似復元装置であって、前記圧縮画像記憶手段に記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する離散ヒストグラム生成手段と、前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する近似ヒストグラム生成手段と、を有することを特徴とする。
【0006】
この構成によれば、離散ヒストグラム生成手段は、圧縮画像データの各画素値Ciに対し、上記画素値度数Liを算出することにより、圧縮画像データの復元を行うことなく圧縮画像データの全体領域又は特定部分領域における画素値のヒストグラム(離散ヒストグラムデータ)を算出することができる。すなわち、復号動作が伴わないので、圧縮画像データから高速に離散ヒストグラムデータを再生できる。更に、近似ヒストグラム生成手段は、画素値に対して離散的な画素値度数を持った離散ヒストグラムデータに対して、上記分散配分を行うことによって、画素値に対して連続的な画素値度数を持つ近似ヒストグラムデータに変換する。これにより原画像データに近いヒストグラムデータを復元することができる。
【0007】
本発明に係るヒストグラム近似復元装置の第2の構成は、前記第1の構成において、前記近似ヒストグラム生成手段は、前記離散ヒストグラムデータ{(Ci, Li)|i=1,2,…,M}の各画素値度数Li(i=1,2,…,M)を、(数1)の正規分布関数G(x)で表される正規分布となるように画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記近似ヒストグラムデータを生成することを特徴とする。
【0008】
【数1】

【0009】
この構成によれば、上記正規分布関数G(x)は離散ヒストグラムデータ{(Ci, Li)|i=1,2,…,M}の各画素値Ci、画素値度数Liおよび標準偏差σの関数なので、標準偏差σを仮定するだけで、原画像データに近いヒストグラムデータを復元することができる。
【0010】
本発明に係るヒストグラム近似復元装置の第3の構成は、前記第1又は2の構成において、前記近似ヒストグラム生成手段は、前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σ=Ci/4の正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成することを特徴とする。
【0011】
この構成によれば、標準偏差σの値をCi/4とするので、離散ヒストグラムデータ{(Ci, Li)|i=1,2,…,M}から一意的に上記正規分布を決定することができる。これにより、ヒストグラムデータの復元を更に高速化できる。
【0012】
本発明に係るヒストグラム近似復元装置の第4の構成は、前記第1又は2の構成において、前記圧縮画像データは、前記原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、前記近似ヒストグラム生成手段は、前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σ=Γ1/2の正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成することを特徴とする。
【0013】
この構成によれば、各ランに対応する原画像データの画素値の分散の閾値Γの平方根を標準偏差σの値とするので、標準偏差σの精度の良い推定値が得られ、ヒストグラムデータの近似復元の精度が向上する。
【0014】
本発明に係るヒストグラム近似復元装置の第5の構成は、前記第1の構成において、前記圧縮画像データは、前記原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、前記近似ヒストグラム生成手段は、前記標準偏差σが、Ci/4又は前記閾値Γの平方根のうちの何れか小さい値であることを特徴とする。
【0015】
この構成によれば、標準偏差σの値をCi/4又は前記閾値Γの平方根のうちの何れか小さい値とするので、標準偏差σの値が過大に推定されるのを避けることができる。これにより、ヒストグラムデータの近似復元の精度が向上する。
【0016】
本発明に係る画像検索装置の第1の構成は、原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)が複数記憶された画像データベース、及び、基準画像の画素値ヒストグラムデータ(以下「基準ヒストグラムデータ」という。)が記憶された基準ヒストグラム記憶手段を有し、前記画像データベースに記憶された前記圧縮画像データの中から前記基準画像に類似するものを検索する画像検索装置において、前記画像データベースに記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する離散ヒストグラム生成手段と、前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する近似ヒストグラム生成手段と、前記基準ヒストグラム記憶手段に記憶されている前記基準ヒストグラムデータと前記近似ヒストグラムデータとの類似度を算出する類似度計算手段と、前記各圧縮画像データの前記類似度に基づいて、前記基準画像に類似する一乃至複数の前記圧縮画像データを選出する画像選出手段と、を備えていることを特徴とする。
【0017】
この構成によれば、離散ヒストグラム生成手段は、圧縮画像データの各画素値Ciに対し、上記画素値度数Liを算出することにより、圧縮画像データの復元を行うことなく圧縮画像データの全体領域又は特定部分領域における画素値のヒストグラム(離散ヒストグラムデータ)を算出することができる。すなわち、基準ヒストグラムデータ、圧縮画像データから高速に離散ヒストグラムデータを再生できる。更に、近似ヒストグラム生成手段は、画素値に対して離散的な画素値度数を持った離散ヒストグラムデータに対して、上記分散配分を行うことによって、画素値に対して連続的な画素値度数を持つ近似ヒストグラムデータに変換する。そして、前記近似ヒストグラムデータと基準ヒストグラムデータとの類似度が算出される。これにより、圧縮画像データの復元を行うことなく原画像データに近いヒストグラムデータを復元して、基準ヒストグラムデータとの類似度を算出できるので、圧縮画像データに対する画像検索を高速化できる。
【0018】
本発明に係る画像検索装置の第2の構成は、前記第1の構成において、前記類似度計算手段は、前記近似ヒストグラムデータと前記基準ヒストグラムデータとの差分を前記類似度として算出することを特徴とする。
【0019】
この構成によれば、類似度計算手段は、前記近似ヒストグラムデータと前記基準ヒストグラムデータとの差分を前記類似度として算出するので、類似度の算出が単純になり、画像検索に要する時間を更に短縮できる。
【0020】
本発明に係るヒストグラム近似復元方法の第1の構成は、原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)から、前記原画像の画素値ヒストグラムを近似的に復元するヒストグラム近似復元方法において、圧縮画像記憶手段に記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する第1ステップ、及び、前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する第2ステップを有することを特徴とする。
【0021】
本発明に係るヒストグラム近似復元方法の第2の構成は、前記第1の構成において、前記第2ステップにおいて、前記離散ヒストグラムデータ{(Ci, Li)|i=1,2,…,M}の各画素値度数Li(i=1,2,…,M)を、(数2)の正規分布関数G(x)で表される正規分布となるように画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記近似ヒストグラムデータを生成することを特徴とする。
【0022】
【数2】

【0023】
本発明に係るヒストグラム近似復元方法の第3の構成は、前記第1又は2の構成において、前記第2ステップで、前記標準偏差σはCi/4であることを特徴とする。
【0024】
本発明に係るヒストグラム近似復元方法の第4の構成は、前記第1又は2の構成において、前記圧縮画像データは、原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、前記第2ステップにおいて、前記標準偏差σは前記閾値Γの平方根であることを特徴とする。
【0025】
本発明に係るヒストグラム近似復元方法の第5の構成は、前記第1又は2の構成において、前記圧縮画像データは、原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、前記第2ステップにおいて、前記標準偏差σは、Ci/4又は前記閾値Γの平方根のうちの何れか小さい値であることを特徴とする。
【0026】
本発明に係る画像検索方法の第1の構成は、原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)が複数記憶された画像データベース、及び、基準画像の画素値ヒストグラムデータ(以下「基準ヒストグラムデータ」という。)が記憶された基準ヒストグラム記憶手段を有するシステムにおいて、前記画像データベースに記憶された前記圧縮画像データの中から前記基準画像に類似するものを検索する画像検索方法であって、前記画像データベースに記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する離散ヒストグラム生成ステップ、前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する近似ヒストグラム生成ステップ、及び、前記基準ヒストグラム記憶手段に記憶されている前記基準ヒストグラムデータと前記近似ヒストグラムデータとの類似度を算出する類似度計算ステップからなる画像比較過程を、前記画像データベースに記憶されているすべての圧縮画像データに対して実行する第1ステップと、前記各圧縮画像データの前記類似度に基づいて前記基準画像に類似する一乃至複数の前記圧縮画像データを選出する第2ステップと、を有することを特徴とする。
【0027】
本発明に係る画像検索方法の第2の構成は、前記第1の構成において、前記類似度計算ステップで、前記近似ヒストグラムデータと前記基準ヒストグラムデータとの差分を前記類似度として算出することを特徴とする。
【0028】
本発明に係るプログラムは、上記第1乃至第5の構成のヒストグラム近似復元方法をコンピュータに実行されることを特徴とする。
【0029】
本発明に係るプログラムは、上記第1又は第2の構成の画像検索方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【0030】
以上説明したように、本発明はランレングス符号化圧縮した画像データの離散的な画素値ヒストグラムの近傍に画素が正規分布するように画素を配分して、離散的な画素値ヒストグラムから原画像の連続的な画素値ヒストグラムを近似復元するので、原画像の画素値ヒストグラムを効率よく、かつ精度良く復元する方法を提供することができる。また、近似復元した画素値ヒストグラムと基準画像の画素値ヒストグラムを比較して類似度を求めるので画像データの検索を高速処理できる。このような効果により、本発明は画像検索の高速化と高精度化に資するものである。
【発明を実施するための最良の形態】
【0031】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例1】
【0032】
図1は、本発明の実施例1に係るヒストグラム近似復元装置及び画像検索装置の構成を表すブロック図である。
【0033】
本実施例の画像検索装置1は、ヒストグラム近似復元装置2、フレーム・メモリ3、領域抽出手段4、領域圧縮画像記憶手段5、ヒストグラム作成手段6、基準ヒストグラム記憶手段7、画像データベース(圧縮画像記憶手段)8、領域抽出手段9、類似度計算手段10、及び画像選出手段11を備えている。
【0034】
尚、本実施例の画像検索装置1は、CCDカメラ20により撮像された微粒子の画像と類似する画像を画像データベース8に記憶されている微粒子画像と照合することにより、微粒子の種類を判別するシステム等に用いられる。
【0035】
フレーム・メモリ3は、CCDカメラ20により撮像され、AD変換器21によりデジタル化された画像を記憶するメモリである。領域抽出手段4は、フレーム・メモリ3に記憶された画像中から部分画像(例えば、微粒子部分の画像)を抽出し、領域圧縮画像記憶手段5に保存する。
【0036】
ヒストグラム作成手段6は、領域圧縮画像記憶手段5に記憶された部分画像のデータ(以下、「基準画像」という。)に含まれる各画素の画素値についてヒストグラム(以下、「基準ヒストグラムデータ」という。)を生成して、基準ヒストグラム記憶手段7に保存する。
【0037】
画像データベース8には、複数の圧縮画像データが記憶されている。ここで、圧縮画像データは、原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データである。尚、このランレングス符号化の詳細に関しては後述する。
【0038】
領域抽出手段9は、画像データベース8から圧縮画像データを読み出して、その全部を出力し又は一部の領域を切り出して出力する。これは、例えば、圧縮画像データの一部領域に微粒子画像がある場合などに、その微粒子画像の部分のみを抽出するためのものである。
【0039】
ヒストグラム近似復元装置2は、領域抽出手段9により画像データベース8から読み出された圧縮画像データ又はその部分データ(以下「領域圧縮画像データ」という。)から、原画像又はその部分画像の画素値ヒストグラムを近似的に復元する。ヒストグラム近似復元装置2は、領域圧縮画像記憶手段12、離散ヒストグラム生成手段13、及び近似ヒストグラム生成手段14を備えている。
【0040】
領域圧縮画像記憶手段12は、領域抽出手段9が出力する領域圧縮画像データを一時的に記憶する。離散ヒストグラム生成手段13は、領域圧縮画像記憶手段12に記憶された領域圧縮画像データから離散ヒストグラムデータを生成する。離散ヒストグラムデータについては後述する。近似ヒストグラム生成手段14は、領域圧縮画像記憶手段12が出力する離散ヒストグラムデータに対して、画素値度数に分散をもたせることによって近似ヒストグラムデータを生成する。
【0041】
類似度計算手段10は、基準ヒストグラム記憶手段7に記憶されている基準ヒストグラムデータと、近似ヒストグラム生成手段14が出力する近似ヒストグラムデータとの類似度を算出する。画像選出手段11は、各圧縮画像データの前記類似度に基づいて、基準画像に類似する一乃至複数の圧縮画像データを選出し、それを出力装置22に出力する。尚、出力装置22には、磁気ディスクなどの外部記憶装置、ネットワーク上に出力する通信インタフェース等が使用される。
【0042】
尚、本実施例の画像検索装置1は、LSIチップとしてハードウェア的に構成してもよいが、汎用のコンピュータにプログラムをロードすることによって各構成部分を機能モジュールとして構成してもよい。
【0043】
次に、画像データベース8に記憶された圧縮画像データについて説明する。画像データベース8に記憶された圧縮画像データは、原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものである。この圧縮アルゴリズムについては、特許文献2,3又は非特許文献1に詳細に記載されている。ここではその圧縮アルゴリズムの一例を説明するに止める。
【0044】
まず、2次元の原画像の画像データ(以下「原画像データ」という。)を走査して1次元の原画像データとする。この1次元化された原画像データを{xi ; i=1,2,…,N}と記す。ここで、Nは原画像データの画素数である。
【0045】
次に、この1次元化された原画像データに対して、以下のような再帰的な2分割処理を実行する。
【0046】
まず、区間lの1次元画素列を{xi ; i=1,2,…,N}とする。区間Lを区間Lと区間Lに分割する。図2にその分割例を示す。区間L,L,Lの平均値は、それぞれ式(3),式(4),式(5)により表される。但し、区間Lの画素数をNとする。
【0047】
【数3】

【0048】
再帰的な2分割を行う上で、区間L,L,Lの累積自乗誤差を、それぞれe,e,eとすると、これらは式(6),式(7),式(8)により表される。
【0049】
【数4】

【0050】
二分割点は、次の評価式が最小となるN(1<N<N)とする。
【0051】
【数5】

【0052】
この2分割操作を、Evalが所定の閾値Γ以下且つNがNmax以下となるまで再帰的に繰り返して行う。
【0053】
以上のようなアルゴリズムにより、1次元化された原画像データは複数の区間に分割される。分割された各区間をランとし、その区間(ラン)における画素の平均値をそのランにおける画素値としてランレングス符号化を行う。このランレングス符号化によって、1次元化された原画像データは、各ランにおいて画素値が量子化され、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となる。このようにして得られた圧縮画像データが、画像データベース8に複数保存されている。
【0054】
図3は、ランレングス符号化により圧縮された画像データの例を示す模式図である。図3では、横軸が走査の順を表し、縦軸が画素値(輝度)を表す。図中に括弧書きした数字の組は、前の数字が画素値(ここでは輝度)、後の数字がランレングスを表す。一般に、圧縮画像データは下記の式(10)で表される。但し、Cは画素値、lはランレングス、Nはランの数である。
【0055】
【数6】

【0056】
次に、上述のように構成された本実施例に係る画像検索装置1について、その動作を説明する。
【0057】
最初に、前処理として、撮像された画像データから基準ヒストグラムデータの作成が行われる。まず、CCDカメラ20により、微粒子等の被写体が撮像される。CCDカメラ20から出力される画像データは、AD変換器21においてデジタル化され、フレーム・メモリ3に保存される。領域抽出手段4は、フレーム・メモリ3に記憶された画像から目的の領域を抽出して基準画像として領域圧縮画像記憶手段5に保存する。尚、領域抽出手段4による領域抽出方法は、種々の公知の方法を使用することができるが、本発明とは直接関係がないので説明は省略する。
【0058】
次に、ヒストグラム作成手段6は、領域圧縮画像記憶手段5に記憶された基準画像から画素値のヒストグラムを作成し、基準ヒストグラムデータとして基準ヒストグラム記憶手段7に保存する。
【0059】
以上のような前処理が終了した後に、画像データベース8に記憶された圧縮画像データから、基準画像に類似する画像の圧縮画像データを検索する画像検索処理を以下のように実行する。
【0060】
図4は、画像検索処理の流れを表すフローチャートである。ます、最初に画像検索装置1は、画像データベース8から読み出す圧縮画像データの番号iを1に初期化する(S1)。
【0061】
次に、領域抽出手段9は、画像データベース8からi番目の圧縮画像データを読み出す(S2)。そして、読み出した圧縮画像データから所定の領域(領域圧縮画像データ)を抽出する(S3)。ここで、抽出する領域は目的に応じて圧縮画像の一部分とされたり、圧縮画像全体とされたりする。抽出された領域圧縮画像データは、領域圧縮画像記憶手段12に保存される。
【0062】
次に、離散ヒストグラム生成手段13は、領域圧縮画像記憶手段12に記憶された領域圧縮画像データから離散ヒストグラムデータを生成する(S4)。
【0063】
図5は、領域圧縮画像データから作成した基準ヒストグラムである。図5で、横軸は画素値(輝度)、縦軸は画素の出現頻度を表す。画素の出現頻度は、画素値が等しい区間のランレングスの総和である。例えば、画素値70の画素の出現頻度とは、領域圧縮画像データ全体から、画素値70を持つデータを全て拾い出して、それらのデータのランレングスを合計したものである。領域圧縮画像データにおいて画素値がCであるランの集合をL(C)と記す。基準ヒストグラムは、一般的に、次式で表される。但し、Lは画素値度数(ランレングスの総和)、Mは画素値の個数である。
【0064】
【数7】

【0065】
なお、画素の出現頻度は各画素値の画素値度数を一画面の画素の総数で除して規格化した値で表してもよい。
【0066】
次に、近似ヒストグラム生成手段14は、領域圧縮画像記憶手段12が出力する離散ヒストグラムデータに対して、画素値度数に分散をもたせることによって近似ヒストグラムデータを生成する(S5)。
【0067】
図5の画素値ヒストグラムの画素値Cは量子化された値であるが、原画像では画素値Cの近傍に画素が分布していたと考えられる。そこで、これらの画素が画素値Cを中心に正規分布に従って分布していると仮定し、各画素値Cの画素値度数Lを式(13)の分布関数G(x)に従って、画素値Cの近傍に分散配分する。但し、xは画素値、σは標準偏差を表す。
【0068】
【数8】

【0069】
離散的な画素値ヒストグラムの全ての画素値Cについて、式(13)により画素値度数Lを画素値Cの近傍に配分すると、図6に示すように、画素値Cの近傍に分布する画素を示すヒストグラム31〜34が描ける。なお、標準偏差σは画素値Cの4分の1(C/4)を選ぶと良い結果が得られた。最後にこれらのヒストグラムを全て重畳すると、全ての画素値についての連続的な近似ヒストグラム35が得られる。
【0070】
次に、類似度計算手段10は、近似ヒストグラム生成手段14が出力する近似ヒストグラムデータと、基準ヒストグラム記憶手段7に記憶されている基準ヒストグラムデータとの類似度Sを算出する(S6)。類似度Sは、近似ヒストグラムデータと基準ヒストグラムデータとの差分により計算される。すなわち、近似ヒストグラムデータをH(x)、基準ヒストグラムデータをH(x)とすると、類似度Sは式(14)により表される。但し、x,xは画素値を表す。
【0071】
【数9】

【0072】
次に、画像検索装置1は、画像データベース8に記憶されているすべての圧縮画像データについて、類似度Sの計算が完了したか否かを判定し(S7)、未了であれば、iを1だけ増加させて(S8)、ステップS2の処理に戻る。
【0073】
ステップS7で、すべての圧縮画像データについて類似度Sの計算が完了した場合、画像選出手段11は、各圧縮画像データの前記類似度に基づいて、基準画像に類似する一乃至複数の圧縮画像データを選出し(S9)、それを出力装置22に出力して(S10)、画像検索処理を終了する。
【0074】
尚、画像選出手段11による圧縮画像データを選出の方法としては、類似度Sが最小の圧縮画像データを選出する方法や、類似度Sが所定の閾値以下の圧縮画像データをすべて選出する方法等が考えられる。何れの方法を採用するかは、用途に応じて決めればよい。
【0075】
以上のように、本実施例に係る画像検索装置1では、圧縮画像データから直接近似復元した近似ヒストグラムデータと基準画像の基準ヒストグラムデータの類似度を求め、画像の検索を行うことが出来る。画像のヒストグラムは生の画像データに比べてデータ量が格段少ないので、画像データを直接検索する場合に比べて、10倍以上の速さで高速に検索することができる。
【0076】
尚、特許文献2及び非特許文献1に記載されたように、原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化された画像データの画素値ヒストグラムを近似復元する場合には、前記閾値Γの平方根を前記標準偏差σとすることもできる。
【0077】
あるいは、前記閾値Γの平方根又は画素値Cの4分の1(C/4)のいずれか小さい値を標準偏差σとすることもできる。
【図面の簡単な説明】
【0078】
【図1】本発明の実施例1に係るヒストグラム近似復元装置及び画像検索装置の構成を表すブロック図である。
【図2】区間分割の例を示す図である。
【図3】ランレングス符号化圧縮された画像データの例を示す模式図である。
【図4】画像検索処理の流れを表すフローチャートである。
【図5】図1の画像データから作成した離散的な画素値ヒストグラムである。
【図6】近似復元した連続的な画素値ヒストグラムである。
【図7】基準画像の基準ヒストグラムの例である。
【符号の説明】
【0079】
1 画像検索装置
2 ヒストグラム近似復元装置
3 フレーム・メモリ
4 領域抽出手段
5 領域圧縮画像記憶手段
6 ヒストグラム作成手段
7 基準ヒストグラム記憶手段
8 画像データベース(圧縮画像記憶手段)
9 領域抽出手段
10 類似度計算手段
11 画像選出手段
12 領域圧縮画像記憶手段
13 離散ヒストグラム生成手段
14 近似ヒストグラム生成手段
20 CCDカメラ
21 AD変換器
22 出力装置
31〜34 正規分布に従って配分された画素を示すヒストグラム
35 全ての画素値についての連続的なヒストグラム



【特許請求の範囲】
【請求項1】
圧縮画像記憶手段に記憶された、原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)から、前記原画像の画素値ヒストグラムを近似的に復元するヒストグラム近似復元装置であって、
前記圧縮画像記憶手段に記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する離散ヒストグラム生成手段と、
前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する近似ヒストグラム生成手段と、
を有することを特徴とするヒストグラム近似復元装置。
【請求項2】
前記近似ヒストグラム生成手段は、
前記離散ヒストグラムデータ{(Ci, Li)|i=1,2,…,M}の各画素値度数Li(i=1,2,…,M)を、(数1)の正規分布関数G(x)で表される正規分布となるように画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記近似ヒストグラムデータを生成すること
を特徴とする請求項1に記載のヒストグラム近似復元装置。
【数1】

【請求項3】
前記近似ヒストグラム生成手段は、
前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σ=Ci/4の正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成すること
を特徴とする請求項1又は2に記載のヒストグラム近似復元装置。
【請求項4】
前記圧縮画像データは、前記原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、
前記近似ヒストグラム生成手段は、
前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σ=Γ1/2の正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成すること
を特徴とする請求項1又は2に記載のヒストグラム近似復元装置。
【請求項5】
前記圧縮画像データは、前記原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、
前記近似ヒストグラム生成手段は、
前記標準偏差σが、Ci/4又は前記閾値Γの平方根のうちの何れか小さい値であること
を特徴とする請求項1又は2に記載のヒストグラム近似復元装置。
【請求項6】
原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)が複数記憶された画像データベース、
及び、基準画像の画素値ヒストグラムデータ(以下「基準ヒストグラムデータ」という。)が記憶された基準ヒストグラム記憶手段
を有し、前記画像データベースに記憶された前記圧縮画像データの中から前記基準画像に類似するものを検索する画像検索装置において、
前記画像データベースに記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する離散ヒストグラム生成手段と、
前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する近似ヒストグラム生成手段と、
前記基準ヒストグラム記憶手段に記憶されている前記基準ヒストグラムデータと前記近似ヒストグラムデータとの類似度を算出する類似度計算手段と、
前記各圧縮画像データの前記類似度に基づいて、前記基準画像に類似する一乃至複数の前記圧縮画像データを選出する画像選出手段と、
を備えていることを特徴とする画像検索装置。
【請求項7】
前記類似度計算手段は、前記近似ヒストグラムデータと前記基準ヒストグラムデータとの差分を前記類似度として算出すること
を特徴とする請求項6に記載の画像検索装置。
【請求項8】
原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)から、前記原画像の画素値ヒストグラムを近似的に復元するヒストグラム近似復元方法において、
圧縮画像記憶手段に記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する第1ステップ、
及び、前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する第2ステップ
を有することを特徴とするヒストグラム近似復元方法。
【請求項9】
前記第2ステップにおいて、
前記離散ヒストグラムデータ{(Ci, Li)|i=1,2,…,M}の各画素値度数Li(i=1,2,…,M)を、(数2)の正規分布関数G(x)で表される正規分布となるように画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記近似ヒストグラムデータを生成すること
を特徴とする請求項8に記載のヒストグラム近似復元方法。
【数2】

【請求項10】
前記第2ステップにおいて、前記標準偏差σはCi/4であることを特徴とする請求項8又は9に記載のヒストグラム近似復元方法。
【請求項11】
前記圧縮画像データは、原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、
前記第2ステップにおいて、前記標準偏差σは前記閾値Γの平方根であること
を特徴とする請求項8又は9に記載のヒストグラム近似復元方法。
【請求項12】
前記圧縮画像データは、原画像データの各画素の画素値を量子化するとともに、各ランにおいて当該ランに対応する原画像データの画素値の分散が所定の閾値Γ以下となるようにランレングスを決定することによりランレングス符号化されたものであり、
前記第2ステップにおいて、前記標準偏差σは、Ci/4又は前記閾値Γの平方根のうちの何れか小さい値であること
を特徴とする請求項8又は9に記載のヒストグラム近似復元方法。
【請求項13】
原画像の画像データ(以下「原画像データ」という。)の各画素の画素値を量子化するとともにランレングス符号化することにより得られた圧縮画像の画像データ(以下「圧縮画像データ」という。)が複数記憶された画像データベース、
及び、基準画像の画素値ヒストグラムデータ(以下「基準ヒストグラムデータ」という。)が記憶された基準ヒストグラム記憶手段
を有するシステムにおいて、前記画像データベースに記憶された前記圧縮画像データの中から前記基準画像に類似するものを検索する画像検索方法であって、
前記画像データベースに記憶された前記圧縮画像データの各画素値Ci(i=1,2,…,M,Mは圧縮画像データに含まれる全画素値の数)に対して、前記圧縮画像データの全体領域又は特定の部分領域における当該画素値に対応するランレングスの総和(以下「画素値度数」という。)Liを算出することにより離散ヒストグラムデータを生成する離散ヒストグラム生成ステップ、
前記圧縮画像データの各画素値Ci(i=1,2,…,M)に対して、当該画素値Ciに対応する前記離散ヒストグラムデータの前記画素値度数Liを、当該画素値Ciを中心とする標準偏差σの正規分布となるように当該画素値Ciの近傍の画素値xの画素値度数L(x)に分散配分することにより、前記原画像データの画素値の出現頻度を近似的に表す近似ヒストグラムデータを生成する近似ヒストグラム生成ステップ、
及び、前記基準ヒストグラム記憶手段に記憶されている前記基準ヒストグラムデータと前記近似ヒストグラムデータとの類似度を算出する類似度計算ステップ
からなる画像比較過程を、前記画像データベースに記憶されているすべての圧縮画像データに対して実行する第1ステップと、
前記各圧縮画像データの前記類似度に基づいて前記基準画像に類似する一乃至複数の前記圧縮画像データを選出する第2ステップと、
を有することを特徴とする画像検索方法。
【請求項14】
前記類似度計算ステップにおいて、
前記近似ヒストグラムデータと前記基準ヒストグラムデータとの差分を前記類似度として算出すること
を特徴とする請求項13に記載の画像検索方法。
【請求項15】
請求項8乃至請求項12のヒストグラム近似復元方法をコンピュータに実行させることを特徴とするプログラム。
【請求項16】
請求項13又は請求項14の画像検索方法をコンピュータに実行させることを特徴とするプログラム。





【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate


【公開番号】特開2006−139579(P2006−139579A)
【公開日】平成18年6月1日(2006.6.1)
【国際特許分類】
【出願番号】特願2004−329231(P2004−329231)
【出願日】平成16年11月12日(2004.11.12)
【出願人】(802000031)財団法人北九州産業学術推進機構 (187)
【出願人】(899000068)学校法人早稲田大学 (602)
【Fターム(参考)】