(57)【特許請求の範囲】
【請求項１】
画像情報が存在する画像空間に任意のクラスタを複数形成し該クラスタごとに量子化を行う画像処理装置であって、
前記量子化において、前記画像空間の中の任意の位置に複数配置されたセントロイドを基準に前記クラスタを複数形成するクラスタ形成手段と、
任意の条件を満たしていない前記セントロイドである不適セントロイドを特定する不適セントロイド特定手段と、
それぞれの前記クラスタについて、一又は複数の任意の地点を境界に複数の領域に分割し、それぞれの前記領域に存在する前記画像情報の任意の値の平均値としての平均値をそれぞれ算出し、隣接する前記領域に存在する前記平均値同士の差の絶対値を算出する絶対値算出手段と、
前記絶対値の大きい前記クラスタから順に前記不適セントロイドを転用するセントロイド転用手段とを備えたことを特徴とする画像処理装置。
【請求項２】
前記絶対値算出手段は、それぞれの前記クラスタについて、任意の地点を境界に一方側領域と他方側領域に二分割し、前記一方側領域に存在する前記画像情報の任意の値の平均値としての第一の平均値と、前記他方側領域に存在する前記画像情報の任意の値の平均値としての第二の平均値とを算出し、前記第一の平均値と前記第二の平均値との差の絶対値を算出し、
前記セントロイド転用手段は、前記絶対値の大きい前記クラスタから順に前記不適セントロイドを転用することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記絶対値算出手段は、前記クラスタの中心位置を前記任意の地点とすることを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記不適セントロイド特定手段は、前記クラスタの中に存在する前記画像情報が特定の限界値以下である場合に該クラスタの中にある前記セントロイドが前記任意の条件を満たしていないと判定することを特徴とする請求項１乃至３の何れか一つに記載の画像処理装置。
【請求項５】
前記画像情報は、色情報又は輝度信号であることを特徴とする請求項１乃至４の何れか一つに記載の画像処理装置。
【請求項６】
前記量子化は、ＬＢＧ法を用いて行われることを特徴とする請求項１乃至５の何れか一つに記載の画像処理装置。
【請求項７】
画像情報が存在する画像空間に任意のクラスタを複数形成し該クラスタごとに量子化を行う画像処理方法であって、
前記量子化において、前記画像空間の中の任意の位置に複数配置されたセントロイドを基準に前記クラスタを複数形成するクラスタ形成手順と、
任意の条件を満たしていない前記セントロイドである不適セントロイドを特定する不適セントロイド特定手順と、
それぞれの前記クラスタについて、それぞれの前記クラスタについて、一又は複数の任意の地点を境界に複数の領域に分割し、それぞれの前記領域に存在する前記画像情報の任意の値の平均値としての平均値をそれぞれ算出し、隣接する前記領域に存在する前記平均値同士の差の絶対値を算出する絶対値算出手順と、
前記絶対値の大きい前記クラスタから順に前記不適セントロイドを転用するセントロイド転用手順とを備えたことを特徴とする画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像情報や画素情報の量子化処理を行う画像処理装置及び画像処理方法に関する。
【背景技術】
【０００２】
従来より、アナログ画像からディジタル画像への変換時や、ディジタル画像を圧縮する際に用いられる量子化において、画像空間を任意の大きさのクラスタ（領域）に区切るクラスタリングを行い、各領域内の画像情報（色情報や輝度信号等）を所定の演算によって任意のディジタル符号に置き換えるという、ベクトル量子化の手法が用いられることが多い。
【０００３】
ベクトル量子化の手法は様々存在する。例えば、ベクトル量子化の手法の一つである、いわゆるＬＢＧ法（Linde-Buzo-Gray法、以下「ＬＢＧ法」と記する。本明細書において同じ。）を用いて画像情報の量子化を行う場合は、画像空間の中の任意の位置に仮のセントロイド（重心点）を配置し、仮のセントロイドを基準に画像空間を区分してクラスタを形成する。形成された各クラスタ内の画像情報に所定の演算を行い、演算結果に基づいて仮のセントロイドを新たに配置すると共に、新たな仮のセントロイドを基準に新たなクラスタを形成し、という処理を繰り返すことで、最終的に正規のセントロイドを配置し、正規のセントロイドを基準に量子化に適したクラスタを形成する。
【０００４】
ＬＢＧ法をはじめとする量子化の手法を画像処理に適用する場合、画像情報の特質に合った最適化をすることが望ましい。しかし、従来、ＬＢＧ法を画像処理の量子化に合った形で最適化する手法は存在しなかった。
【先行技術文献】
【特許文献】
【０００５】
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、画像情報は画像空間の中の任意の位置に偏在したり分散的に存在する場合が多いのに対し、ＬＢＧ法の仮のセントロイドは画像情報の存在状況とは無関係に配置される場合がある。このため、対応する画像情報が存在しない位置などに仮のセントロイドが配置されてしまう場合がある一方で、セントロイドが配置された方がよい位置に仮のセントロイドが配置されない事態が起こりうる。一般に、画像処理装置におけるセントロイドの数は予め決まっている場合が多いため、このような事態はセントロイドを記録するメモリ領域を無駄に消費することにつながるという問題が生ずる。また、不適切なセントロイドの配置は、クラスタリングが最適化するまでの時間の長大化につながるという問題が生ずる。
【０００７】
本発明はこのような課題に鑑みてなされたものであり、量子化において、メモリ領域を効率良く使用し、短時間でクラスタリングの最適化を行う事ができる画像処理装置、画像処理方法を提供することを課題としている。
【課題を解決するための手段】
【０００８】
かかる課題を解決するために、請求項１に記載の発明は、画像情報が存在する画像空間に任意のクラスタを複数形成し該クラスタごとに量子化を行う画像処理装置であって、前記量子化において、前記画像空間の中の任意の位置に複数配置されたセントロイドを基準に前記クラスタを複数形成するクラスタ形成手段と、任意の条件を満たしていない前記セントロイドである不適セントロイドを特定する不適セントロイド特定手段と、それぞれの前記クラスタについて、一又は複数の任意の地点を境界に複数の領域に分割し、それぞれの前記領域に存在する前記画像情報の任意の値の平均値としての平均値をそれぞれ算出し、隣接する前記領域に存在する前記平均値同士の差の絶対値を算出する絶対値算出手段と、前記絶対値の大きい前記クラスタから順に前記不適セントロイドを転用するセントロイド転用手段とを備えたことを特徴とする。
【０００９】
請求項２に記載の発明は、請求項１に記載の構成に加え、前記絶対値算出手段は、それぞれの前記クラスタについて、任意の地点を境界に一方側領域と他方側領域に二分割し、前記一方側領域に存在する前記画像情報の任意の値の平均値としての第一の平均値と、前記他方側領域に存在する前記画像情報の任意の値の平均値としての第二の平均値とを算出し、前記第一の平均値と前記第二の平均値との差の絶対値を算出し、前記セントロイド転用手段は、前記絶対値の大きい前記クラスタから順に前記不適セントロイドを転用することを特徴とする。
【００１０】
請求項３に記載の発明は、請求項１又は２に記載の構成に加え、前記絶対値算出手段は、前記クラスタの中心位置を前記任意の地点とすることを特徴とする。
【００１１】
請求項４に記載の発明は、請求項１乃至３の何れか一つに記載の構成に加え、前記不適セントロイド特定手段は、前記クラスタの中に存在する前記画像情報が特定の限界値以下である場合に該クラスタの中にある前記セントロイドが前記任意の条件を満たしていないと判定することを特徴とする。
【００１２】
請求項５に記載の発明は、請求項１乃至４の何れか一つに記載の構成に加え、前記画像情報は、色情報又は輝度信号であることを特徴とする。
【００１３】
請求項６に記載の発明は、請求項１乃至５の何れか一つに記載の構成に加え、前記量子化は、ＬＢＧ法を用いて行われることを特徴とする。
【００１４】
請求項７に記載の発明は、画像情報が存在する画像空間に任意のクラスタを複数形成し該クラスタごとに量子化を行う画像処理方法であって、前記量子化において、前記画像空間の中の任意の位置に複数配置されたセントロイドを基準に前記クラスタを複数形成するクラスタ形成手順と、任意の条件を満たしていない前記セントロイドである不適セントロイドを特定する不適セントロイド特定手順と、
【００１５】
それぞれの前記クラスタについて、それぞれの前記クラスタについて、一又は複数の任意の地点を境界に複数の領域に分割し、それぞれの前記領域に存在する前記画像情報の任意の値の平均値としての平均値をそれぞれ算出し、隣接する前記領域に存在する前記平均値同士の差の絶対値を算出する絶対値算出手順と、前記絶対値の大きい前記クラスタから順に前記不適セントロイドを転用するセントロイド転用手順とを備えたことを特徴とする。
【発明の効果】
【００１６】
請求項１、請求項７に記載の発明によれば、それぞれのクラスタについて、一又は複数の任意の地点を境界に複数の領域に分割し、それぞれの領域に存在する画像情報の任意の値の平均値としての平均値をそれぞれ算出し、隣接する領域に存在する平均値同士の差の絶対値を算出することにより、絶対値の大きいクラスタほどセントロイドが配置されることが適切な量子化につながるものと判るため、簡単な計算でセントロイドが配置されるべきクラスタを特定できる。また、任意の条件を満たしていないセントロイドである不適セントロイドを特定し、絶対値の大きいクラスタから順に不適セントロイドを転用することにより、量子化に活用されていないセントロイドを、画一的な処理に基づいて、セントロイドが配置されることが適切な量子化につながるクラスタに転用することができる。これにより、量子化において、メモリ領域を効率良く使用し、短時間でクラスタリングの最適化を行う事ができる。
【００１７】
請求項２に記載の発明によれば、それぞれのクラスタについて、任意の地点を境界に一方側領域と他方側領域に二分割し、一方側領域に存在する画像情報の任意の値の平均値としての第一の平均値と、他方側領域に存在する画像情報の任意の値の平均値としての第二の平均値とを算出し、第一の平均値と第二の平均値との差の絶対値を算出することにより、セントロイドが配置されるべきクラスタを特定するための一手順毎の計算量をより少ないものとすることができる。これにより、量子化において、メモリ領域をより効率良く使用し、より短時間でクラスタリングの最適化を行う事ができる。
【００１８】
請求項３に記載の発明によれば、クラスタの中心位置をクラスタを分割する境界とするための任意の地点とすることにより、簡易な手順でクラスタを分割し、かつ、演算によって、セントロイドが配置されるべきクラスタを高い精度で特定できる。これにより、量子化において、メモリ領域をより一層効率良く使用し、より短時間でクラスタリングの最適化を行う事ができる。
【００１９】
請求項４に記載の発明によれば、クラスタの中に存在する画像情報が特定の限界値以下である場合にクラスタの中にあるセントロイドが任意の条件を満たしていないと判定することにより、量子化の単位とするのに不向きなクラスタ及びセントロイドに基づく処理を回避し、高品位な量子化が行えるクラスタリングを短時間で行うことができる。
【００２０】
請求項５に記載の発明によれば、画像情報は色情報又は輝度信号であることにより、数値として特定容易な情報に基づいて、適切な量子化を行うことができる。
【００２１】
請求項６に記載の発明によれば、量子化にＬＢＧ法を用いることにより、本発明を適用した量子化を活用して高品位な量子化を行うことができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施の形態に係る画像処理装置の全体構成を示す機能ブロック図である。
【図２】同上実施の形態に係る画像処理装置において用いられるＬＢＧ法の動作手順の原理を示すイメージ図であって、（ａ）輝度信号と、画像空間に仮のセントロイドを配置した状態を示すイメージ図である。（ｂ）仮のクラスタリングを行った状態を示すイメージ図である。（ｃ）画像空間に新たなセントロイドを配置した状態を示すイメージ図である。
【図３】同上実施の形態におけるセントロイドの転用を示すイメージ図であって、（ａ）他のセントロイドの対応付けに好適なクラスタの一例を示すイメージ図である。（ｂ）他のセントロイドの対応付けが好適ではないクラスタの一例を示すイメージ図である。（ｃ）配置されたセントロイドを他のクラスタに転用することが好適なクラスタの一例を示すイメージ図である。
【図４】同上実施の形態に係る画像処理装置における処理手順を示すフローチャートである。
【図５】同上実施の形態に係る画像処理装置における（ａ）画像空間に仮のセントロイドを配置した状態を示すイメージ図である。（ｂ）仮のクラスタリングを行い、各クラスタの第一の領域の輝度信号の平均値と第二の領域の輝度信号の平均値との差の絶対値を算出した状態を示すイメージ図である。（ｃ）不適セントロイドを絶対値が大きいクラスタに転用した状態を示すイメージ図である。
【発明を実施するための形態】
【００２３】
図１乃至図５に本発明の一の実施の形態を示す。
【００２４】
＜基本構成＞
図１は、この発明の実施の形態に係る画像処理装置の全体構成を示す機能ブロック図である。この画像処理装置１は、画像処理システム１Ａの構成要件の一つであって、ディジタル信号の圧縮処理に際して量子化処理を行う。具体的には、この画像処理装置１は、画像出力部２から供給されたディジタルの画像信号を圧縮処理して外部出力する画像処理システム１Ａにおいて用いられる。画像処理装置１は、画像出力部２から供給された画像信号に対し、画像処理における量子化処理を行う。具体的には、画像処理装置１は、画像情報が存在する画像空間に任意のクラスタを複数形成しクラスタを単位としたベクトル量子化を行う。
【００２５】
図１に示す通り、画像処理装置１は、機能手段として、セントロイド配置部１１、「クラスタ形成手段」としてのクラスタ形成部１２、「不適セントロイド特定手段」としての不適セントロイド特定部１３、「絶対値算出手段」としての絶対値算出部１４、「セントロイド転用手段」としてのセントロイド転用部１５、量子化部１６を備えている。
【００２６】
セントロイド配置部１１は、画像空間の中に複数のセントロイドを配置する。なお、この「画像空間」とは、色情報や輝度情報等が配置される任意の空間の事を指し、輝度と出現頻度とをパラメータとするグラフのような仮想的な空間も含まれる。
【００２７】
クラスタ形成部１２は、画像処理装置１の量子化において、画像空間の中の任意の位置に複数配置されたセントロイドを基準にクラスタを複数形成する。
【００２８】
不適セントロイド特定部１３は、任意の条件を満たしていないセントロイドである不適セントロイドを特定する。
【００２９】
絶対値算出部１４は、それぞれのクラスタを複数の領域に分割し、それぞれの領域に存在する画像情報の値の平均値を算出し、双方の平均値の差の絶対値を算出する。この実施の形態では、絶対値算出部１４は、それぞれのクラスタを二分割する。ただし、絶対値算出部１４がそれぞれのクラスタを三つ以上の領域に分割する構成であってもよい。
【００３０】
セントロイド転用部１５は、絶対値の大きいクラスタから順に不適セントロイドを転用する。
【００３１】
量子化部１６は、形成されたそれぞれのクラスタを単位に画像情報の量子化を行う。
【００３２】
＜セントロイド＞
この実施の形態におけるセントロイドは、クラスタリングで形成された各クラスタの中心位置としての位置情報と、それぞれの位置における画像情報（画像空間内における輝度の大きさや色の種類の出現頻度、出現位置等に関する情報）の値としての色情報を数値化して記録できる機能を有する。一つの画像空間に配置できるセントロイドの数は予め定められている。
【００３３】
＜ＬＧＢ法の一般的な処理原理＞
この実施の形態における画像処理装置１は量子化の際にベクトル量子化を行う。ベクトル量子化の一例として、ＬＢＧ法を用いる場合の一般的な手順を説明する。
【００３４】
画像情報の量子化においてＬＢＧ法を用いる場合、一般的な手順は以下（手順１）〜（手順５）に示す通りである。
【００３５】
（手順１）画像空間の中の任意の位置に、複数の仮のセントロイドを配置する。当初の仮のセントロイドの配置場所はどのようなものでもよい。なお、このセントロイドとは、クラスタリングの中心位置として機能する。
【００３６】
図２の（ａ）に、画像空間２０に仮のセントロイドが配置された状態のイメージ図を示す。同図において、横軸は画像空間２０上における輝度位置、縦軸は輝度の出現頻度を示す。同図において、符号２１は「画像情報」としての出現頻度、即ち任意の画像内における輝度の出現頻度を示す曲線であり、符号２２１，２２２，２２３は仮のセントロイドである。同図において、仮のセントロイド２２１，２２２，２２３は均等に配置されている。
【００３７】
（手順２）画像空間２０に配置された仮のセントロイドを基準に、任意の範囲がクラスタとして形成される。
【００３８】
図２の（ｂ）に示すイメージ図において、符号２１１，２１２，２１３は「画像情報」としての出現頻度、即ち任意の画像内における輝度の出現頻度であり、符号２２１，２２２，２２３は仮のセントロイド、符号２３１，２３２，２３３はそれぞれの仮のセントロイド２２１，２２２，２２３から任意の距離の位置に設けられたクラスタの境界線、符号２４１，２４２，２４３はクラスタである。同図において、クラスタ２４１，２４２，２４３の境界線２３１，２３２，２３３は、仮のセントロイド２２１，２２２，２２３からの距離Ｌ１，Ｌ２等がそれぞれ等距離になるように配置される。
【００３９】
（手順３）画像空間の中の画像情報を、最も近距離に配置された仮のセントロイドに対応付ける。この手順により、図２の（ｂ）に示す、クラスタ２４１内の出現頻度２１１は仮のセントロイド２２１に、クラスタ２４２内の出現頻度２１２は仮のセントロイド２２２に、クラスタ２４３内の出現頻度２１３は仮のセントロイド２２３に、それぞれ対応付けられる。これにより仮のクラスタリングが完成する。
【００４０】
（手順４）各クラスタ内の画像情報の平均値を求める。この平均値の位置に、新たな仮のセントロイドを配置する。図２の（ｃ）に示すイメージ図においては、符号２５１がクラスタ２４１内の輝度信号２１１の平均値、符号２５２がクラスタ２４２内の輝度信号２１２の平均値であり、符号２５３がクラスタ２４３内の輝度信号２１３の平均値である。これらの平均値２５１，２５２，２５３の位置に新たな仮のセントロイド２２４，２２５，２２６を配置する。配置後は（手順２）に戻り、新たな仮のセントロイド２２４，２２５，２２６を基準に、任意の範囲がクラスタとして形成されることになる。
【００４１】
（手順５）上記（手順２）〜（手順４）を繰り返すことで、量子化のための最適化されたクラスタを得ることができる。
【００４２】
なお、図２の（ａ）〜（ｃ）は、アナログの上記（手順１）〜（手順５）はアナログ情報として形成された出現頻度２１１，２１２，２１３に基づいて行ったが、ディジタル情報として形成された出現頻度に基づいても同様の手順で最適化されたクラスタを得ることができる。
【００４３】
＜この実施の形態におけるＬＧＢ法の処理原理＞
一般に、高品位の量子化を行うためには、画像情報の情報量が大きい部分に多くのクラスタが形成されることが望ましい。そのために、画像情報の情報量が大きい部分に多くのセントロイドを対応付けていくことが望ましい。
【００４４】
図３の（a）は、他のセントロイドの対応付けに好適なクラスタの一例を示すイメージ図である。このクラスタ２４４においては、画像空間２０に複数例えば２つ（２群）のディジタル情報として形成された出現頻度２１４，２１５が存在し、複数例えば２つのピーク２６１，２６２が離間して形成されている。このような場合、当該クラスタ２４４内にすでに配置されたセントロイド２２７に加え、他のセントロイドを配置することが、高品位の量子化を行う上で望ましい。
【００４５】
一方、図３の（ｂ）は、他のセントロイドの対応付けが好適ではないクラスタの一例を示すイメージ図である。このクラスタ２４５においては、セントロイド２２８が配置されたクラスタ２４５内に存在する出現頻度２１６は１つのピーク２６３のみ形成している。
【００４６】
また、図３の（ｃ）は、配置されたセントロイドを他のクラスタに転用することが好適なクラスタの一例を示すイメージ図である。図３の（ｃ）においては、セントロイド２２９が配置されたクラスタ２４６内には輝度信号が存在しない。即ちクラスタ２４６内の輝度信号は、平均値が特定の限界値２８以下である。このセントロイド２２９は、画像情報の情報量が少ないクラスタ２４６に配置されたものと考えられ、当該クラスタ２４６に基づく量子化は、高品位な量子化に貢献する度合いが比較的小さいと思われる。
【００４７】
そこで、この実施の形態においては、図３の（ｃ）のようなクラスタ２４６に配置されたセントロイド２２９を図３の（ａ）のクラスタ２４４に再配置し、当該クラスタ２４４内の出現頻度２１４及び出現頻度２１５の少なくとも一部に対応付けることで高品位な量子化を行おうとするものである。
【００４８】
＜セントロイド対応付け及び再配置の処理手順＞
図４は、この実施の形態の画像処理装置１における処理手順を示すフローチャートである。以下、このフローチャートに基づいて処理手順を説明する。
【００４９】
まず、画像形成装置１のセントロイド配置部１１は、図５の（ａ）に示すように、画像空間２０にｎ個（ｎ＞１、図５においてはｎ＝４）の仮のセントロイド２２１０，２２１１，２２１２，２２１３を配置する（ステップＳ１）。この仮のセントロイド２２１０，２２１１，２２１２，２２１３は任意の条件に基づいて配置される。図５の（ａ）のイメージ図においては、仮のセントロイド２２１０，２２１１，２２１２，２２１３は等間隔に配置される。
【００５０】
次に、クラスタ形成部１２は、それぞれの仮のセントロイド２２１０，２２１１，２２１２，２２１３を基準にクラスタリングを行い、図５の（ｂ）に示す通り、画像空間２０内にｎ個（ｎ＞１、図５においてはｎ＝４）のクラスタ２４７，２４８，２４９，２４１０を形成する（ステップＳ２、クラスタ形成手順）。図５の（ｂ）においては、仮のセントロイド２２１０，２２１１，２２１２，２２１３を中心に等しい大きさのクラスタ２４７，２４８，２４９，２４１０が形成されている。
【００５１】
なお、以下説明の簡単のため、特に区別の必要がある場合を除き、セントロイド２２１０，２２１１，２２１２，２２１３、クラスタ２４７，２４８，２４９，２４１０はセントロイド２２、クラスタ２４と記載する。
【００５２】
次に、不適セントロイド特定部１３は、全てのクラスタ２４内のセントロイド２２から、不適セントロイドを特定する（ステップＳ３、不適セントロイド特定手順）。この実施の形態における「不適セントロイド」とは、予め定められた任意の条件を満たしていないセントロイドのことである。この実施の形態においては、不適セントロイド特定部１３は、図５の（ｂ）に示すように、クラスタ２４内の輝度の出現頻度の平均値が任意の限界値２８以下であるセントロイド２２１２を不適セントロイドとして特定する。
【００５３】
なお、上記手順は例示であり、不適セントロイド特定部１３は、上記以外のどのような手順で不適セントロイドを特定してもよい。
【００５４】
次に、絶対値算出部１４は、それぞれのクラスタ２４を二分割し（ステップＳ４）、それぞれの領域に存在する画像情報の値の平均値を算出し（ステップＳ５）、双方の平均値の差の絶対値を算出する（ステップＳ６）。
【００５５】
例えば、図５の（ｂ）におけるクラスタ２４７を例にとって説明すると、絶対値算出部１４は、中心位置３１１を境界に、クラスタ２４７を、一方側領域３２１と他方側領域３３１とに二分割する（ステップＳ４）。
【００５６】
次に、絶対値算出部１４は、図５の（ｂ）に示すように、一方側領域３２１に存在する出現頻度２１７の平均値としての第一の平均値３４１と、他方側領域３３１に存在する出現頻度２１８の平均値としての第二の平均値３５１とを算出する（ステップＳ５）。この「平均値」とは、第一の領域３２１及び第二の領域３３１に存在する輝度の大きさの（つまり、図５の（ａ）（ｂ）（ｃ）のグラフにおける横軸方向の値の大きさ）の平均値である。
【００５７】
次に、絶対値算出部１４は、第一の平均値３４１と第二の平均値３５１との差の絶対値を算出する（ステップＳ６、絶対値算出手順）。図５の（ｂ）に絶対値ｄ１を示す。
【００５８】
ステップＳ４〜ステップＳ６の処理は画像空間２０内の全てのクラスタ２４に対して繰り返し行われる（ステップＳ７の“Ｎｏ”）。即ち、クラスタ２４８，２４９，２４１０も一方側領域３２２，３２３，３２４と他方側領域３３２，３３３，３３４とに二分割され、クラスタ２４８の第一の平均値３４２と第二の平均値３５２に基づく絶対値ｄ２、クラスタ２４１０の第一の平均値３４３と第二の平均値３５３に基づく絶対値ｄ３が算出される。一方、クラスタ２４９には出現頻度が存在しない（つまり、画像情報２０にはクラスタ２４９内の値の輝度は存在しない）ので絶対値は算出されない。
【００５９】
ステップＳ４〜ステップＳ６の処理が全てのクラスタ２４７，２４８，２４９，２４１０に対して行われた後（ステップＳ７の“Ｙｅｓ”）、セントロイド転用部１５は、絶対値の大きいクラスタ２４から順に不適セントロイド２２１２を転用する（ステップＳ８、セントロイド転用手順）。具体的には、セントロイド転用部１５は、ステップＳ６で算出されたそれぞれの絶対値ｄ１，ｄ２，ｄ３を対比し、絶対値の大きいクラスタ２４から順に、ステップＳ３で特定された不適セントロイド２２１２を転用する。図５の（ｃ）においては、絶対値ｄ１の大きさが最大なので、クラスタ２４７に不適セントロイド２２１２を転用する。
【００６０】
不適セントロイド２２１２が転用されたクラスタ２４７においては、そのクラスタ２４内に存在するセントロイド２２１０と、不適セントロイド２２１２とが配置されたものとして扱われる。例えば、セントロイド転用部１５は、クラスタ２４７の平均値３４１の位置及び平均値３５１の位置のうち、一方にセントロイド２２１０を配置し、他方に不適セントロイド２２１２を配置する。
【００６１】
上記の手順が完了した後、セントロイド配置部１１は、それぞれのクラスタ３２１，３３１，２４８，２４１０内に存在する出現頻度２１の平均値を算出し（ステップＳ９）、算出された平均値の位置に新たなセントロイド２２を配置する（ステップＳ１０）。
【００６２】
そして、画像処理装置１は、所定の条件を満たすまでステップＳ２〜ステップＳ１０の処理を繰り返す（ステップＳ１１の“Ｎｏ”）。
【００６３】
なお、上述した１回目のステップＳ２〜ステップＳ１０の手順の後に２回目のステップＳ２の手順が行われる際、上記ステップＳ８においてセントロイド２２１２が無くなったクラスタ２４９は、図５の（ｃ）に示す、セントロイド２２１１とセントロイド２２１３との中間点３１５で分割されて、同図における中間点３１５の左側及び右側が、それぞれ新たなクラスタ２４８及びクラスタ２４９としてクラスタリングされる（ステップＳ２）。また、上記１回目のステップＳ８においてセントロイド２２１０、及び不適セントロイド２２１２が配置された一方側領域３２１と他方側領域３３１とは、２回目のステップＳ２の手順が行われる際、それぞれ新たなクラスタ３２１，３３１としてクラスタリングされる（ステップＳ２）。
【００６４】
上述の、ステップＳ１１の“Ｎｏ”か否かを判断する「所定の条件」とは、繰り返しの回数であってもよいし、形成されたクラスタ２４が全て所定の条件を満たしていることであってもよい。所定の条件を満たした場合（ステップＳ１１の“Ｙｅｓ”）、量子化部１６は、最適化されたそれぞれのクラスタ２４毎に量子化を行う（ステップＳ１２）。即ち、量子化部１６は、それぞれのクラスタ２４内の出現頻度２１の平均値を算出し、これをクラスタ２４毎の出現頻度２１の値として取得する。
【００６５】
以上示すように、この実施の形態においては、それぞれのクラスタ２４７，２４８，２４１０について、セントロイド２２１０，２２１１，２２１３を境界に複数の領域である一方側領域３２１，３２２，３２４と他方側領域３３１，３３２，３３４とに分割し、一方側領域３２１，３２２，３２４に存在する出現頻度２１７，２１９，２１１０の平均値としての第一の平均値３４１，３４２，３４３と、他方側領域３３１，３３２，３３４に存在する出現頻度２１８，２１９，２１１１の平均値としての第二の平均値３５１，３５２，３５３との差の絶対値ｄ１，ｄ２，ｄ３を算出することにより、絶対値ｄ１，ｄ２，ｄ３の大きいクラスタ２４７，２４８，２４１０ほどセントロイド２２が配置されることが適切な量子化につながるものと判るため、簡単な計算でセントロイド２２が配置されるべきクラスタを特定できる。また、任意の条件を満たしていないセントロイドである不適セントロイド２２１２を特定し、絶対値ｄ１，ｄ２，ｄ３の大きいクラスタ２４７，２４８，２４１０から順に不適セントロイド２２１２を転用することにより、量子化に活用されていないセントロイド２２を、画一的な処理に基づいて、セントロイド２２が配置されることが適切な量子化につながるクラスタ２４７，２４８，２４１０に転用することができる。これにより、量子化において、メモリ領域を効率良く使用し、短時間でクラスタリングの最適化を行う事ができる。
【００６６】
この実施の形態においては、それぞれのクラスタ２４７，２４８，２４１０について、セントロイド２２１０，２２１１，２２１３を境界に複数の領域である一方側領域３２１，３２２，３２４と他方側領域３３１，３３２，３３４とに分割することにより、セントロイド２２が配置されるべきクラスタ２４を特定するための一手順毎の計算量をより少ないものとすることができる。
【００６７】
この実施の形態においては、クラスタ２４７，２４８，２４９，２４１０の中心位置３１１，３１２，３１３，３１４をクラスタ２４７，２４８，２４９，２４１０を分割する境界とするための任意の地点とすることにより、簡易な手順でクラスタ２４７，２４８，２４９，２４１０を分割し、かつ、演算によって、セントロイド２２が配置されるべきクラスタ２４７，２４８，２４９，２４１０を高い精度で特定できる。これにより、量子化において、メモリ領域をより効率良く使用し、より短時間でクラスタリングの最適化を行う事ができる。
【００６８】
この実施の形態においては、クラスタ２４７，２４８，２４９，２４１０の中に存在する出現頻度２１７，２１８，２１９，２１１０，２１１１が特定の限界値２８以下である場合にクラスタ２４７，２４８，２４９，２４１０の中にあるセントロイド２２が任意の条件を満たしていないと判定することにより、量子化の単位とするのに不向きなクラスタ２４７，２４８，２４９，２４１０及びセントロイド２２に基づく処理を回避し、高品位な量子化が行えるクラスタリングを短時間で行うことができる。
【００６９】
なお、この実施の形態においては、説明の簡単のため、輝度のみの出現頻度をパラメータとして扱い量子化する構成（即ち、“輝度”という１次元の情報のみを量子化する構成）としたが、２次元以上の情報の出現頻度をパラメータとして扱う構成としてもよい。例えば、色の３原色であるＲＧＢそれぞれの情報の出現頻度をパラメータとして扱い量子化する構成（即ち、“Ｒ”“Ｇ”“Ｂ”という３次元の情報を量子化する構成）としてもよい。
【００７０】
また、この実施の形態においては、一のクラスタ２４に一のセントロイド２２のみを配置し、一のクラスタ２４をセントロイド２２を中心に二分割する構成としたが、これに代えて、一のクラスタ２４に二つ以上のセントロイド２２を配置し、それぞれのセントロイド２２を中心に一のクラスタ２４を三つ以上に分割する構成としてもよい。
【００７１】
また、この実施の形態においては、ベクトル量子化の手法としてＬＧＢ法を用いたが、これに限らず、どのようなベクトル量子化の手法に本発明を適用してもよい。
【００７２】
また、この実施の形態においては、画像情報を輝度の出現頻度２１としたが、これ以外のどのような画像情報に本発明を適用してもよい。
【００７３】
また、この実施の形態においては、絶対値算出部１４がクラスタ２４を一方側領域３２と他方側領域３３とに二分割する境界をクラスタ２４の中心位置３１としたが、これに限らず、クラスタ２４のどの位置でクラスタ２４を二分割してもよい。
【００７４】
なお、上記実施形態は本発明の例示であり、本発明が上記実施形態のみに限定されることを意味するものではないことは、いうまでもない。
【符号の説明】
【００７５】
１・・・画像処理装置
１２・・・クラスタ形成部（クラスタ形成手段）
１３・・・不適セントロイド特定部（不適セントロイド特定手段）
１４・・・絶対値算出部（絶対値算出手段）
１５・・・セントロイド転用部（セントロイド転用手段）
２１，２１１，２１２，２１３，２１４，２１５，２１６，２１７，２１８，２１９，  ２１１０，２１１１・・・出現頻度（画像情報）
２２，２２１，２２２，２２３，２２４，２２５，２２６，２２７，２２８，２２９，  ２２１０，２２１１，２２１２，２２１３・・・セントロイド
２４，２４１，２４２，２４３，２４４，２４５，２４６，２４７，２４８，２４９，  ２４１０・・・クラスタ
２５１，２５２，２５３・・・平均値
２８・・・限界値
３１１，３１２，３１３，３１４・・・中心位置
３２１，３２２，３２３，３２４・・・一方側領域
３３１，３３２，３３３，３３４・・・他方側領域
３４１，３４２，３４３・・・第一の平均値
３５１，３５２，３５３・・・第二の平均値
【要約】      （修正有）【課題】量子化において、メモリ領域を効率良く使用し、短時間でクラスタリングの最適化を行う事ができる画像処理装置、画像処理方法を提供する。【解決手段】クラスタごとに量子化を行う画像処理装置１は、画像空間の中の任意の位置に複数配置されたセントロイドを基準にクラスタを複数形成するクラスタ形成部１２と、任意の条件を満たさない不適セントロイドを特定する不適セントロイド特定部１３と、それぞれのクラスタを複数の領域に分割し、それぞれの領域に存在する画像情報の任意の値の平均値としての平均値をそれぞれ算出し、隣接する前記領域に存在する平均値同士の差の絶対値を算出する絶対値算出部１４と、絶対値の大きいクラスタから順に不適セントロイドを転用するセントロイド転用部１５とを備える。【選択図】図１【図１】
0005176066.tif 000002
【図２】
0005176066.tif 000003
【図３】
0005176066.tif 000004
【図４】
0005176066.tif 000005
【図５】
0005176066.tif 000006