(57)【特許請求の範囲】
【請求項１】
記憶された複数のテンプレートベクトルデータの中から入力ベクトルデータに類似したテンプレートベクトルデータを検索し、検索したテンプレートベクトルデータのコードを出力する検索手段を有するベクトル量子化装置であって、
上記検索を行う際に、上記入力ベクトルデータの特徴量と上記テンプレートベクトルデータの特徴量とを比較し、その比較の結果に基づいて、検索対象とするテンプレートベクトルデータを選択する検索対象選択手段を備え、
上記検索手段は、上記テンプレートベクトルデータの個々の要素と上記入力ベクトルデータの対応する個々の要素との間で差分をとり、それぞれの絶対値の総和であるマンハッタン距離が最小となるテンプレートベクトルデータを検索するものであり、
上記検索対象選択手段は、あるテンプレートベクトルデータについて、上記入力ベクトルデータとの間で上記マンハッタン距離Ｍを演算するマンハッタン距離演算手段と、上記あるテンプレートベクトルデータとは異なる他のテンプレートベクトルデータの特徴量と上記入力ベクトルデータの特徴量との差分絶対値Ｄを演算する差分演算手段と、上記マンハッタン距離Ｍと上記差分絶対値Ｄとを比較して、Ｍ≦Ｄの関係を有する場合に、上記他のテンプレートベクトルデータについては上記入力ベクトルデータとのマンハッタン距離の演算を省略する演算省略手段とを備えることを特徴とするベクトル量子化装置。
【請求項２】
記憶された複数のテンプレートベクトルデータの中から入力ベクトルデータに類似したテンプレートベクトルデータを検索し、検索したテンプレートベクトルデータのコードを出力する検索手段を有するベクトル量子化装置であって、
上記複数のテンプレートベクトルデータに関してあらかじめ求められた特徴量を記憶する特徴量記憶手段と、
入力ベクトルデータの特徴量を求める特徴量演算手段と、
上記特徴量記憶手段に記憶されている各テンプレートベクトルデータの特徴量と上記特徴量演算手段により求められた入力ベクトルデータの特徴量とに基づいて、検索対象とするテンプレートベクトルデータを選択する検索対象選択手段とを備え、
上記検索手段は、上記テンプレートベクトルデータの個々の要素と上記入力ベクトルデータの対応する個々の要素との間で差分をとり、それぞれの絶対値の総和であるマンハッタン距離が最小となるテンプレートベクトルデータを検索するものであり、
上記検索対象選択手段は、あるテンプレートベクトルデータの特徴量と上記入力ベクトルデータの特徴量との差分絶対値を求める差分演算手段と、上記差分演算手段により求められた差分絶対値が、他のコードベクトルについて既に求められている類似度を表すマンハッタン距離の最小値以上の場合に、上記あるテンプレートベクトルデータについてのマンハッタン距離の演算を省略する演算省略手段とを備えることを特徴とするベクトル量子化装置。
【請求項３】
上記入力ベクトルデータは画像データから構成されることを特徴とする請求項１又は２に記載のベクトル量子化装置。
【請求項４】
上記特徴量は、ベクトルデータを構成する個々の要素の値の総和、平均値もしくは直流成分であることを特徴とする請求項１〜３の何れか１項に記載のベクトル量子化装置。
【請求項５】
上記特徴量は、ベクトルデータを構成する個々の要素のうち一部の要素の値を、とり得る値の中間値を基準として反転するように操作した後の値の総和、平均値もしくは直流成分であることを特徴とする請求項１〜３の何れか１項に記載のベクトル量子化装置。
【請求項６】
上記検索対象選択手段は、異なる種類の複数の特徴量を用いて検索対象とするテンプレートベクトルデータを選択することを特徴とする請求項１〜５の何れか１項に記載のベクトル量子化装置。
【請求項７】
上記検索対象選択手段は、上記入力ベクトルデータの第１の特徴量と上記テンプレートベクトルデータの第１の特徴量とを比較し、その比較の結果に基づいて、検索対象とするテンプレートベクトルデータの範囲を絞り込み、上記入力ベクトルデータの第２の特徴量と上記テンプレートベクトルデータの第２の特徴量とを比較し、その比較の結果に基づいて、上記検索対象とするテンプレートベクトルデータの範囲を更に絞り込むことを特徴とする請求項６に記載のベクトル量子化装置。
【請求項８】
上記ベクトルデータを構成する全要素を複数に分割し、分割した各々の要素についての特徴量を用いて検索対象とするテンプレートベクトルデータを選択することを特徴とする請求項１〜７の何れか１項に記載の記載のベクトル量子化装置。
【請求項９】
上記検索手段は、上記テンプレートベクトルデータの特徴量の大きさ順に検索を行うことを特徴とする請求項１〜８の何れか１項に記載のベクトル量子化装置。
【請求項１０】
上記検索手段は、上記入力ベクトルデータの特徴量および上記テンプレートベクトルデータの特徴量に基づいて、最も答えに近いと判断されるテンプレートベクトルデータから検索を行うことを特徴とする請求項９に記載のベクトル量子化装置。
【請求項１１】
上記テンプレートベクトルデータは、その記憶装置内で特徴量の大きさ順に並べられており、かつ上記テンプレートベクトルデータが複数の特徴量を用いて多次元的に並べられることを特徴とする請求項９又は１０に記載のベクトル量子化装置。
【請求項１２】
上記検索手段は、上記検索対象選択手段により検索対象とされた複数のテンプレートベクトルデータを並列的に読み込み、上記入力ベクトルデータに類似したテンプレートベクトルデータを並列的に検索する複数の類似度演算手段と、
上記複数の類似度演算手段での演算結果に基づいて、その中でも上記入力ベクトルデータに最も類似したテンプレートベクトルデータを特定し、対応するコードを出力するテンプレート特定手段とを備えることを特徴とする請求項１〜１１の何れか１項に記載のベクトル量子化装置。
【請求項１３】
記憶された複数のテンプレートベクトルデータの中から入力ベクトルデータに類似したテンプレートベクトルデータを検索し、検索したテンプレートベクトルデータのコードを出力するベクトル量子化方法であって、
上記検索を行う際に、上記入力ベクトルデータの特徴量と上記テンプレートベクトルデータの特徴量とを比較し、その比較の結果に基づいて、検索対象とするテンプレートベクトルデータを選択する検索対象選択の処理を行い、
上記検索の処理は、上記テンプレートベクトルデータの個々の要素と上記入力ベクトルデータの対応する個々の要素との間で差分をとり、それぞれの絶対値の総和であるマンハッタン距離が最小となるテンプレートベクトルデータを検索するものであり、
上記検索対象選択の処理は、あるテンプレートベクトルデータについて、上記入力ベクトルデータとの間で上記マンハッタン距離Ｍを演算するとともに、上記あるテンプレートベクトルデータとは異なる他のテンプレートベクトルデータの特徴量と上記入力ベクトルデータの特徴量との差分絶対値Ｄを演算し、上記マンハッタン距離Ｍと上記差分絶対値Ｄとを比較して、Ｍ≦Ｄの関係を有する場合に、上記他のテンプレートベクトルデータについては上記入力ベクトルデータとのマンハッタン距離の演算を省略するようにしたものであることを特徴とするベクトル量子化方法。
【請求項１４】
異なる種類の複数の特徴量を用いて検索対象とするテンプレートベクトルデータを選択するようにしたことを特徴とする請求項１３に記載のベクトル量子化方法。
【請求項１５】
上記ベクトルデータを構成する全要素を複数に分割し、分割した各々の要素についての特徴量を用いて検索対象とするテンプレートベクトルデータを選択するようにしたことを特徴とする請求項１３又は１４に記載の記載のベクトル量子化方法。
【請求項１６】
検索対象とされた複数のテンプレートベクトルデータを並列的に読み込み、上記入力ベクトルデータに類似したテンプレートベクトルデータを並列的に検索するようにしたことを特徴とする請求項１３〜１５の何れか１項に記載のベクトル量子化方法。
【請求項１７】
請求項１〜１２の何れか１項に記載の各手段としてコンピュータを機能させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１８】
請求項１３〜１６の何れか１項に記載のベクトル量子化方法の処理手順をコンピュータに実行させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ベクトル量子化装置および方法、更にはこれらの処理を実行させるためのプログラムを記憶した記録媒体に関するものである。
【０００２】
【従来の技術】
従来、データ圧縮の手法が種々提案されている。その中で、圧縮データの伸長処理を非常に簡単に行うことが可能なデータ圧縮アルゴリズムの１つとして、「ベクトル量子化」という手法が良く知られている。このアルゴリズムは、古くから信号処理の分野で知られており、特に、画像信号や音声信号のデータ圧縮、あるいはパターン認識に応用されてきた。
【０００３】
このベクトル量子化では、ある大きさ（例えば４×４画素のブロック）の画素パターン（テンプレートベクトル、もしくはコードベクトルとも言う）を幾つか用意しておき、それぞれにユニークな番号などを与える（この集合体を「コードブック」という）。そして、例えば２次元配列の画像データ中から同じ大きさ（例えば４×４画素）のブロックを順次取り出し、それと最も似通ったパターンをコードブック中から見つけ出して、そのパターンの番号を当該ブロックに当てはめるというデータ圧縮を行う。ベクトル量子化では、１つのブロック内のデータ列が１つのベクトルに対応する。
【０００４】
このようにコード化された圧縮データの受信側あるいは伸長側では、各ブロック毎にコード番号に対応するパターンをコードブックの中から取り出すだけで、元の画像を再現することができる。したがって、伸長側では、コードブックさえ受け取っているか、あるいはあらかじめ保持していれば、特に特殊な演算は必要としないため、非常に簡単なハードウェアで元の画像を再生することが可能となる。
【０００５】
上述のように、ベクトル量子化装置では、コードブック内のテンプレートベクトル群の中から原画像の入力ベクトルデータに類似するものを見つけ出す検索処理を行う必要がある。そして、２つのベクトルデータが類似しているかどうかを判断するための手段として、２つのベクトルデータを所定の関数に入力して演算し、どのくらい似ているかを数値化してこの数値の大きさによって判断する手段が用いられてきた。
【０００６】
以下、２つのベクトルデータがどのくらい似ているかを数値化したものを「類似度」と称する。この類似度を求めるための関数の代表的なものとして、２つの入力ベクトルデータのマンハッタン距離やユークリッド距離を求める関数が挙げられるが、目的に応じて任意の関数を使うことができる。
【０００７】
なお、マンハッタン距離は、２つの入力ベクトルデータ間でそれらを構成する個々の要素どうしの差分絶対値を夫々計算し、各要素毎に計算したこの差分絶対値をすべて加算することによって求めるものである。また、ユークリッド距離は、上述のような差分絶対値の二乗和を求めるものである。
【０００８】
【発明が解決しようとする課題】
しかしながら、従来のベクトル量子化装置では、テンプレートベクトルデータ群の中から入力ベクトルデータに類似するものを見つけ出す際に、最も類似するものを探すために、全てのテンプレートベクトルデータについて入力ベクトルデータとの類似度を演算する必要があった。したがって、テンプレートベクトルのデータ数が膨大になると、入力ベクトルデータと類似しているか否かを判断する演算量も膨大になってしまうという問題があった。
【０００９】
本発明は、このような問題を解決するために成されたものであり、ベクトル量子化を行う際に、テンプレートベクトルデータと入力ベクトルデータとがどのくらい類似しているかを数値化するための演算量を減少させ、ベクトル量子化処理の高速化、低消費電力化を実現できるようにすることを目的とする。
【００１０】
【課題を解決するための手段】
本発明のベクトル量子化装置は、記憶された複数のテンプレートベクトルデータの中から入力ベクトルデータに類似したテンプレートベクトルデータを検索し、検索したテンプレートベクトルデータのコードを出力する検索手段を有するベクトル量子化装置であって、上記検索を行う際に、上記入力ベクトルデータの特徴量と上記テンプレートベクトルデータの特徴量とを比較し、その比較の結果に基づいて、検索対象とするテンプレートベクトルデータを選択する検索対象選択手段を備え、上記検索手段は、上記テンプレートベクトルデータの個々の要素と上記入力ベクトルデータの対応する個々の要素との間で差分をとり、それぞれの絶対値の総和であるマンハッタン距離が最小となるテンプレートベクトルデータを検索するものであり、上記検索対象選択手段は、あるテンプレートベクトルデータについて、上記入力ベクトルデータとの間で上記マンハッタン距離Ｍを演算するマンハッタン距離演算手段と、上記あるテンプレートベクトルデータとは異なる他のテンプレートベクトルデータの特徴量と上記入力ベクトルデータの特徴量との差分絶対値Ｄを演算する差分演算手段と、上記マンハッタン距離Ｍと上記差分絶対値Ｄとを比較して、Ｍ≦Ｄの関係を有する場合に、上記他のテンプレートベクトルデータについては上記入力ベクトルデータとのマンハッタン距離の演算を省略する演算省略手段とを備えることを特徴とする。
本発明の他のベクトル量子化装置は、記憶された複数のテンプレートベクトルデータの中から入力ベクトルデータに類似したテンプレートベクトルデータを検索し、検索したテンプレートベクトルデータのコードを出力する検索手段を有するベクトル量子化装置であって、上記複数のテンプレートベクトルデータに関してあらかじめ求められた特徴量を記憶する特徴量記憶手段と、入力ベクトルデータの特徴量を求める特徴量演算手段と、上記特徴量記憶手段に記憶されている各テンプレートベクトルデータの特徴量と上記特徴量演算手段により求められた入力ベクトルデータの特徴量とに基づいて、検索対象とするテンプレートベクトルデータを選択する検索対象選択手段とを備え、上記検索手段は、上記テンプレートベクトルデータの個々の要素と上記入力ベクトルデータの対応する個々の要素との間で差分をとり、それぞれの絶対値の総和であるマンハッタン距離が最小となるテンプレートベクトルデータを検索するものであり、上記検索対象選択手段は、あるテンプレートベクトルデータの特徴量と上記入力ベクトルデータの特徴量との差分絶対値を求める差分演算手段と、上記差分演算手段により求められた差分絶対値が、他のコードベクトルについて既に求められている類似度を表すマンハッタン距離の最小値以上の場合に、上記あるテンプレートベクトルデータについてのマンハッタン距離の演算を省略する演算省略手段とを備えることを特徴とする。
【００１１】
本発明において、ベクトル量子化装置とは、記憶されたテンプレートベクトルデータ群の中から入力ベクトルデータに最も類似した、もしくは実用上問題ない程度に類似したテンプレートベクトルデータを検索し、検索されたテンプレートベクトルデータの値、またはその番地もしくはテンプレートベクトルデータに付加されたインデックス番号等をコードとしてを出力する検索手段を有する装置を意味する。
【００１２】
また、本発明において、ベクトルデータとは、数値化された情報の集合であるベクトルを表す。テンプレートベクトルデータとは、あらかじめ用意された複数のベクトルデータの集合を構成する個々のベクトルデータであり、各々のテンプレートベクトルデータにはインデックス番号等が付加される場合もある。このテンプレートベクトルデータ群は、一般にコードブックと呼ばれることもある。また、入力ベクトルデータとは、ベクトル量子化装置に入力されるベクトルデータである。
【００１３】
また、本発明において、特徴量とはベクトルデータの性質を端的に表すスカラ量のことである。一例として、ベクトルデータの各要素の総和や平均値、もしくはベクトルデータの各要素の分散などが挙げられるが、これらに限ったものではない。
【００１４】
本発明の他の態様では、上記検索対象選択手段は、異なる種類の複数の特徴量を用いて検索対象とするテンプレートベクトルデータを選択することを特徴としている。
また、上記ベクトルデータを構成する全要素を複数に分割し、分割した各々の要素についての特徴量を用いて検索対象とするテンプレートベクトルデータを選択するようにしても良い。
【００１５】
本発明のその他の態様では、上記検索手段は、上記検索対象選択手段により検索対象とされた複数のテンプレートベクトルデータを並列的に読み込み、上記入力ベクトルデータに類似したテンプレートベクトルデータを並列的に検索する複数の類似度演算手段と、上記複数の類似度演算手段での演算結果に基づいて、その中でも上記入力ベクトルデータに最も類似したテンプレートベクトルデータを特定し、対応するコードを出力するテンプレート特定手段とを備えることを特徴としている。
【００１６】
また、本発明のベクトル量子化方法は、記憶された複数のテンプレートベクトルデータの中から入力ベクトルデータに類似したテンプレートベクトルデータを検索し、検索したテンプレートベクトルデータのコードを出力するベクトル量子化方法であって、上記検索を行う際に、上記入力ベクトルデータの特徴量と上記テンプレートベクトルデータの特徴量とを比較し、その比較の結果に基づいて、検索対象とするテンプレートベクトルデータを選択する検索対象選択の処理を行い、上記検索の処理は、上記テンプレートベクトルデータの個々の要素と上記入力ベクトルデータの対応する個々の要素との間で差分をとり、それぞれの絶対値の総和であるマンハッタン距離が最小となるテンプレートベクトルデータを検索するものであり、上記検索対象選択の処理は、あるテンプレートベクトルデータについて、上記入力ベクトルデータとの間で上記マンハッタン距離Ｍを演算するとともに、上記あるテンプレートベクトルデータとは異なる他のテンプレートベクトルデータの特徴量と上記入力ベクトルデータの特徴量との差分絶対値Ｄを演算し、上記マンハッタン距離Ｍと上記差分絶対値Ｄとを比較して、Ｍ≦Ｄの関係を有する場合に、上記他のテンプレートベクトルデータについては上記入力ベクトルデータとのマンハッタン距離の演算を省略するようにしたものであることを特徴とする。
【００１７】
また、本発明のコンピュータ読み取り可能な記録媒体は、請求項１〜１２の何れか１項に記載の各手段としてコンピュータを機能させるためのプログラムを記録したことを特徴とする。
また、請求項１３〜１６の何れか１項に記載のベクトル量子化方法の処理手順をコンピュータに実行させるためのプログラムを記録しても良い。
【００１８】
【発明の実施の形態】
（第１の実施形態）
図１は、本発明によるベクトル量子化装置の一実施形態を示すブロック図である。図１において、１０１は複数のテンプレートベクトルデータを記憶するテンプレート記憶部、１０２は類似度演算部であり、入力ベクトルデータ１ａと、上記テンプレート記憶部１０１内のあるテンプレートベクトルデータ１ｂとがどれほど類似しているのかを数値化して表現する類似度を演算し、出力する。
【００１９】
１０３は最大類似度検索部であり、上記類似度演算部１０２で各テンプレートベクトルデータについて演算された類似度１ｄに基づいて、入力ベクトルデータ１ａと最も類似度が大きくなるテンプレートベクトルデータがどれなのかを判断する。また、１０７はアドレス指示部であり、テンプレート記憶部１０１内のテンプレートベクトルデータの読み出しアドレスを指示する。また、このアドレス指示部１０７は、最大類似度のテンプレートベクトルデータに対応するアドレスを、その入力ベクトルデータ１ａについてのコード番号として出力する。
【００２０】
以上のような構成のベクトル量子化装置において、本実施形態においては、新たに以下のような機能ブロックを追加している。すなわち、特徴量記憶部１０４と、特徴量演算部１０５と、演算省略判定部１０６である。
特徴量記憶部１０４は、テンプレート記憶部１０１内の各テンプレートベクトルデータの特徴量を記憶するものである。特徴量演算部１０５は、入力ベクトルデータ１ａの特徴量を演算するものである。
【００２１】
また、演算省略判定部１０６は、特徴量記憶部１０４から読み出されたテンプレートベクトルデータに関する特徴量１ｅと、特徴量演算部１０５で求められた入力ベクトルデータに関する特徴量１ｆと、場合によっては類似度演算部１０２で求められた類似度１ｄとを用いて、あるテンプレートベクトルデータが検索の対象となるか否か、言い換えれば、あるテンプレートベクトルデータと入力ベクトルデータとの類似度を演算する必要があるかを否かを判断する。
【００２２】
この演算省略判定部１０６は、類似度演算部１０２およびアドレス指示部１０７に演算省略判定信号１ｇを出力し、類似度の演算を行うか否かをテンプレートベクトルデータ毎に制御する。例えば、あるテンプレートベクトルデータについて類似度の演算を省略できると判断した場合は、そのアドレスのテンプレートベクトルデータの読み出しはスキップし、類似度の演算を行わないようにする。
【００２３】
本実施形態では以上の構成により、例えば、あるテンプレートベクトルデータの類似度の演算に先立って、入力ベクトルデータの特徴量とテンプレートベクトルデータの特徴量とを比較し、その比較結果に基づいて、上記あるテンプレートベクトルデータについて類似度の演算を行うか否かを決定するようにする。これにより、ベクトル量子化装置で行われる類似度演算を少なくすることができ、検索に必要な演算量を減少させることが可能となる。
【００２４】
なお、上記に示した実施形態の説明では、入力ベクトルデータと最も類似度が大きくなる、つまり最も類似したテンプレートベクトルデータを探す操作を行っている。そのために最大類似度検索部１０３を備えている。しかし、本発明は最も類似度が大きくなるものを探す場合にとどまらず、類似度が実用上問題ない程度に大きくなるようなテンプレートベクトルデータを検索する場合にも応用が可能である。これは、最大類似度検索部１０３の動作を変更すれば容易に実現することができる。
【００２５】
また、特徴量記憶部１０４内に記憶するテンプレートベクトルデータに関する特徴量は、検索の実行に先立ってあらかじめ演算して求めておいても良い。または、演算省略判定部１０６における判定のための演算と、特徴量演算部１０５における入力ベクトルデータの特徴量の演算と合わせても、類似度の演算に比べて少ない演算量で行えるならば、検索時に特徴量を演算しても全体の演算量は減少させることができる。
【００２６】
図１に示したベクトル量子化装置の各部分は、専用のハードウェア回路で実現することも可能であるし、上述の処理を実行させるためのプログラムにより動くコンピュータで実現することも可能である。
【００２７】
（第２の実施形態）
次に、本発明の第２の実施形態を図２を用いて説明する。図２は、上記図１に示したベクトル量子化装置をより具体的に実施した構成を示す図である。この図２では、２つのベクトルが類似しているか否かを数値化した類似度を求める関数としてマンハッタン距離を利用し、特徴量としてベクトルデータの要素の総和を利用した場合のベクトル量子化装置の構成を示している。なお、類似度としてマンハッタン距離を用いた場合、距離が小さいほうが類似度は大きい。
【００２８】
最初に、演算が省略できる原理を説明する。
ベクトルデータの次元数（要素数）をｎ、テンプレート記憶部２０１内のテンプレートベクトル（コードベクトル）データの総数をｋとする。このとき、
入力ベクトルデータ：Ｉ＝（Ｉ1 ，Ｉ2 ，…，Ｉn ）
テンプレートベクトルデータ：Ｔm ＝（Ｔm1，Ｔm2，…Ｔmn）
（ｍ＝１，２，…，ｋ）
について、入力ベクトルデータＩとテンプレートベクトルデータＴm との類似度を、以下の式(1) で示すマンハッタン距離Ｍm で定義すると、入力ベクトルデータＩに最も類似しているテンプレートベクトルデータＴm を検索する操作とは、全てのマンハッタン距離Ｍm （ｍ＝１，２，…，ｋ）の中で距離Ｍm が最も小さくなるｍの値を探し出す操作に相当する。
【００２９】
【数１】
0003676577.tif 000002
【００３０】
ここで、以下の式(2) に示すような、入力ベクトルデータＩの要素の総和とテンプレートベクトルデータＴm の要素の総和との差の絶対値Ｄm と、上記式(1) に示したマンハッタン距離Ｍm との間には、Ｄm ≦Ｍm という関係が成り立つことに注目すると、以下のような議論が成り立つ。
【００３１】
【数２】
0003676577.tif 000003
【００３２】
すなわち、テンプレート記憶部２０１内にあるテンプレートベクトルデータＴm と入力ベクトルデータＩとのマンハッタン距離Ｍm が判明しているとする。このとき、テンプレート記憶部２０１内にあって、上記テンプレートベクトルデータＴm とは別な任意のテンプレートベクトルデータＴo と入力ベクトルデータＩとについて、各々のベクトルデータの要素の総和をとり、その総和どうしの差の絶対値Ｄo を計算した結果、Ｄo ≧Ｍm となっている場合を仮定する。
【００３３】
この場合、上述のＤm ≦Ｍm という関係により、常にＭo ＞Ｍm が成り立つ。よって、テンプレートベクトルデータＴo と入力ベクトルデータＩとのマンハッタン距離Ｍo を計算せずとも、差分絶対値Ｄo を計算するだけで、テンプレートベクトルデータＴo はテンプレートベクトルデータＴm に比べて入力ベクトルデータＩに類似していないことが分かる。つまり、テンプレートベクトルデータＴo を検索対象から除外できることになる。
【００３４】
以上だけを見ると、テンプレートベクトルデータＴo について、マンハッタン距離Ｍo を計算しなくても、差分絶対値Ｄo を計算する必要があるのならば、検索に関わる処理は減少していないように見える。しかし、差分絶対値Ｄo の演算において、テンプレートベクトルデータＴm の特徴量である要素の総和ΣＴmi（式(2) 中の右辺第２項）は、あらかじめ計算して特徴量記憶部２０４に記憶しておくことができる。
【００３５】
よって、差分絶対値Ｄo の算出は、入力ベクトルデータＩの特徴量の演算と、これと特徴量記憶部２０４内に記憶されている特徴量との差をとる演算を行うだけで済む。また、入力ベクトルデータＩの特徴量の算出は、１つの入力ベクトルデータに対して１回の演算で済む。このため、差分絶対値Ｄo の算出は、マンハッタン距離Ｍo の算出に比べて非常に少ない演算量で行うことができる。
【００３６】
なお、特徴量としてベクトルデータの要素の総和を用いることと、要素の平均値を用いることとは等価である。何故ならば、要素の平均値とは要素の総和を要素数で割っただけのものに過ぎないからである。
【００３７】
次に、図２を使って具体的に説明する。
図２において、入力ベクトルデータＩおよびテンプレート記憶部２０１内の複数のテンプレートベクトルデータＴ1 ，Ｔ2 ，Ｔ3 ，Ｔ4 ，…は、例として共に６次元のベクトルデータとなっているが、任意の次元でかまわない。特徴量記憶部２０４には、テンプレート記憶部２０１内に記憶されている各テンプレートベクトルデータＴ1 ，Ｔ2 ，Ｔ3 ，Ｔ4 ，…の特徴量（例えば要素の総和）ΣＴ1 ，ΣＴ2 ，ΣＴ3 ，ΣＴ4 ，…が記憶されている。
【００３８】
図２中では、テンプレート記憶部２０１内の各テンプレートベクトルデータＴ1 ，Ｔ2 ，Ｔ3 ，Ｔ4 ，…と、すぐ左側に位置する特徴量記憶部２０４内の各特徴量ΣＴ1 ，ΣＴ2 ，ΣＴ3 ，ΣＴ4 ，…とは対応している。つまり、テンプレートベクトルデータＴ1 の特徴量はΣＴ1 、テンプレートベクトルデータＴ2 の特徴量はΣＴ2 、以下同様となる。これらのテンプレート記憶部２０１および特徴量記憶部２０４内のデータは、アドレスカウンタ２０８からのアドレスに従って順に読み出される。
【００３９】
また、マンハッタン距離演算部２０２は、テンプレート記憶部２０１から転送された２ｂで示される各テンプレートベクトルデータＴm と、２ａで示される入力ベクトルデータＩとのマンハッタン距離Ｍm （ｍ＝１〜ｋ）を求め、２ｄで示されるマンハッタン距離データを出力する。また、最小マンハッタン距離記憶部２０３は、演算省略判定部２０７による更新制御に従って、今までに計算されたマンハッタン距離Ｍm のうち、最小の距離ｍｉｎＭを記憶する。
【００４０】
ある１つの入力ベクトルデータＩについて全てのテンプレートベクトルデータＴm との演算が終了したとき、この最小マンハッタン距離記憶部２０３に記憶されているものに対応するテンプレートベクトルデータが、入力ベクトルデータＩに最も類似するデータである。そして、このように最も類似する（最も距離が短い）テンプレートベクトルデータのアドレスｍｉｎＡは、演算省略判定部２０７による更新制御に従って、アドレスカウンタ２０８から最小距離アドレス記憶部２０９に与えられて記憶されている。
【００４１】
そこで、ある１つの入力ベクトルデータＩについて処理が終わったときに、この最小距離アドレス記憶部２０９に記憶されているアドレスｍｉｎＡが、当該ブロックのコード番号に相当することになる。なお、このコード番号は、１つの入力ベクトルデータＩの処理が終わる毎に出力しても良いし、１枚の画像全体の処理が終わったときにまとめて出力するようにしても良い。
【００４２】
特徴量演算部２０５は、入力ベクトルデータＩの各要素の総和を演算し、その結果を出力する。少なくとも同じ入力ベクトルデータＩについて類似度を求める演算を行っている間は、ここで演算した特徴量は保存されている。特徴量差分演算部２０６は、上記特徴量演算部２０５で求められた入力ベクトルデータＩの特徴量２ｆと、特徴量記憶部２０４から読み出されたテンプレートベクトルデータＴm の特徴量２ｅとの差分を演算し、出力する。
【００４３】
演算省略判定部２０７は、最小マンハッタン距離記憶部２０３より出力される、今までに分かっている最小のマンハッタン距離２ｃと、特徴量差分演算部２０６で演算された特徴量の差分２ｇとを利用して、テンプレートベクトルデータＴm と入力ベクトルデータＩのマンハッタン距離を演算する必要があるか否かを判別する。
【００４４】
そして、その判別結果をマンハッタン距離演算部２０２に伝え、必要でない演算を省略するようにするとともに、最小マンハッタン距離記憶部２０３、アドレスカウンタ２０８および最小距離アドレス記憶部２０９に所定の制御信号を出力し、それぞれの内容の更新制御を行う。
【００４５】
アドレスカウンタ２０８の内容は、１回の処理が終わることに更新されるが、最小マンハッタン距離記憶部２０３および最小距離アドレス記憶部２０９の内容は、所定の条件を満たしたときのみ更新される。なお、テンプレートベクトルデータを読み出す前にアドレスカウンタ２０８の値をインクリメントすれば、マンハッタン距離演算部２０２への制御信号は必ずしも必要ではない。
【００４６】
次に、上記のように構成したベクトル量子化装置のベクトル量子化の手順を示す。演算の省略の様子も同時に説明する。
１）まず、入力ベクトルデータＩの特徴量を特徴量演算部２０５によって演算し、その結果を保存する。この特徴量は、１つの入力ベクトルデータＩに対して１度だけ演算すればよい。
【００４７】
２）次に、入力ベクトルデータＩと、テンプレート記憶部２０１内の第１番目のテンプレートベクトルデータＴ1 とのマンハッタン距離Ｍ1 をマンハッタン距離演算部２０２によって演算する。この演算結果はＭ1 ＝７０である。この段階ではマンハッタン距離はまだ１つしか演算していないので、現在までに見つかっている最小のマンハッタン距離ｍｉｎＭは、Ｍ1 となる。したがって、このマンハッタン距離Ｍ1 を最小マンハッタン距離記憶部２０３に記憶する。つまり、ｍｉｎＭ＝Ｍ1 ＝７０である。
【００４８】
３）次に、特徴量記憶部２０４内の第２番目のテンプレートベクトルデータＴ2 の特徴量ΣＴ2 と、特徴量演算部２０５に保存されている入力ベクトルデータＩの特徴量２ｆ（この例では２６５）との差の絶対値Ｄ2 を特徴量差分演算部２０６で求める。この演算結果は、Ｄ2 ＝４である。
【００４９】
４）さらに、手順３）で求めた特徴量の差の絶対値Ｄ2 と、現在までに見つかっている最小のマンハッタン距離ｍｉｎＭとをもとに、第２番目のテンプレートベクトルデータＴ2 と入力ベクトルデータＩとのマンハッタン距離Ｍ2 を演算する必要があるかどうかを、演算省略判定部２０７で判断する。今の場合、Ｄ2 ＜ｍｉｎＭ（＝Ｍ1 ）であるから、第２番目のテンプレートベクトルデータＴ2 と入力ベクトルデータＩとのマンハッタン距離Ｍ2 の演算は省略できない。
【００５０】
５）手順４）により、第２番目のテンプレートベクトルデータＴ2 と入力ベクトルデータＩとのマンハッタン距離Ｍ2 の演算が必要と判定されたので、マンハッタン距離演算部２０２はこの演算を行う。この演算の結果は、Ｍ2 ＝２２であるが、これは今までに見つかっている最小のマンハッタン距離ｍｉｎＭ（＝Ｍ1 ）よりも小さいので、ｍｉｎＭの値をＭ2 に更新する。よって、ｍｉｎＭ＝Ｍ2 となる。つまり、最小マンハッタン距離記憶部２０３には第２番目のテンプレートベクトルデータＴ2 に関するマンハッタン距離Ｍ2 が記憶される。
【００５１】
６）次に、特徴量記憶部２０４内の第３番目のテンプレートベクトルデータＴ3 の特徴量ΣＴ3 と、特徴量演算部２０５に保存されている入力ベクトルデータＩの特徴量２ｆとの差の絶対値Ｄ3 を特徴量差分演算部２０６で求める。この演算結果は、Ｄ3 ＝４６である。
【００５２】
７）さらに、手順６）で求めた特徴量の差の絶対値Ｄ3 と、現在までに見つかっている最小のマンハッタン距離ｍｉｎＭとをもとに、第３番目のテンプレートベクトルデータＴ3 と入力ベクトルデータＩとのマンハッタン距離Ｍ3 を演算する必要があるかどうかを、演算省略判定部２０７で判断する。今の場合、Ｄ3 ＞ｍｉｎＭ（＝Ｍ2 ）であるから、第３番目のテンプレートベクトルデータＴ3 と入力ベクトルデータＩとのマンハッタン距離Ｍ3 の演算は省略できる。
【００５３】
８）手順７）により、第３番目のテンプレートベクトルデータＴ3 と入力ベクトルデータＩとのマンハッタン距離Ｍ3 の演算は省略できると判明したので、この演算は省略する。そして、第４番目のテンプレートベクトルデータＴ4 の特徴量ΣＴ4 と入力ベクトルデータＩの特徴量２ｆとの差の絶対値Ｄ4 を特徴量差分演算部２０６で演算する。その演算結果は、Ｄ4 ＝１５７である。
【００５４】
９）手順８）で求めた特徴量の差の絶対値Ｄ4 と、現在までに見つかっている最小のマンハッタン距離ｍｉｎＭとをもとに、第４番目のテンプレートベクトルデータＴ4 と入力ベクトルデータＩとのマンハッタン距離Ｍ4 を演算する必要があるかどうかを、演算省略判定部２０７で判断する。今の場合、Ｄ4 ＞ｍｉｎＭ（＝Ｍ2 ）であるから、第４番目のテンプレートベクトルデータＴ4 と入力ベクトルデータＩとのマンハッタン距離Ｍ4 の演算も省略できる。
【００５５】
１０）以下、同様の処理をｍ＝ｋとなるまで繰り返す。
【００５６】
図３は、上記した本実施形態によるベクトル量子化処理の手順を示すフローチャートである。以下、このフローチャートについて説明する。
図３において、まず最初にステップＳ１で入力ベクトルデータＩを入力する。そして、ステップＳ２で、その入力ベクトルデータＩの要素の総和（特徴量）を演算し、その結果を保存する。
【００５７】
次に、ステップＳ３で、検索するテンプレートベクトルデータの番号（アドレス）をｍ＝１、ｍｉｎＡ＝１に初期化するとともに、現在までに見つかっている最小のマンハッタン距離ｍｉｎＭの値を∞に初期化する。次に、ステップＳ４で、アドレスカウンタｍの値がテンプレートベクトルデータの数ｋを越えたかどうかを判断し、越えていない場合はステップＳ５に進む。
【００５８】
ステップＳ５では、検索するテンプレートベクトルデータＴm についてあらかじめ記憶されている特徴量と、演算の結果保存されている入力ベクトルデータＩの特徴量との差の絶対値Ｄm を求める。そして、ステップＳ６で、その演算した差分絶対値Ｄm が、現在までに見つかっている最小のマンハッタン距離ｍｉｎＭの値以上かどうかを判断する。
【００５９】
ここで、差分絶対値Ｄm が現在の最小マンハッタン距離ｍｉｎＭの値以上の場合は、ステップＳ１０でアドレスカウンタｍの値をインクリメントした後、ステップＳ４の処理に戻る。一方、上記差分絶対値Ｄm が現在の最小マンハッタン距離ｍｉｎＭより小さい場合は、ステップＳ７に進み、入力ベクトルデータＩと、検索するテンプレートベクトルデータＴm とのマンハッタン距離Ｍm の演算を実行する。
【００６０】
そして、ステップＳ８で、演算したマンハッタン距離Ｍm が現在の最小マンハッタン距離ｍｉｎＭ以上であるかどうかを判断し、そうである場合はステップＳ１０でアドレスカウンタｍの値をインクリメントした後、ステップＳ４の処理に戻る。一方、演算したマンハッタン距離Ｍm が現在の最小マンハッタン距離ｍｉｎＭより小さい場合は、ステップＳ９に進む。
【００６１】
ステップＳ９では、最小マンハッタン距離ｍｉｎＭの値を上記演算したマンハッタン距離Ｍm に更新するとともに、探し出したテンプレートベクトルデータの番号（アドレス）を最小距離アドレス記憶部２０９に記録する。その後、ステップＳ１０でアドレスカウンタｍの値をインクリメントした後、ステップＳ４の処理に戻る。
【００６２】
以上の手順の中でも示した通り、図２に記載した構成のベクトル最子化装置を用いれば、入力ベクトルデータＩに最も類似したテンプレートベクトルデータを検索する操作を行う際に、その検索に必要な類似度の演算を少なくすることができ、高速に演算を行うことができる。
【００６３】
なお、図２では、テンプレート記憶部２０１内の各テンプレートベクトルデータＴ1 ，Ｔ2 ，Ｔ3 ，Ｔ4 ，…は任意の順で並んでいたが、特徴量の大きい順に並べておいても良い。テンプレートベクトルデータが特徴量順に並んでいる場合は、テンプレートベクトルデータを検索する際、入力ベクトルデータＩと特徴量が最も近いテンプレートベクトルデータから検索をすることが容易になる。特徴量が近い２つのベクトルデータは、類似度も大きい傾向があるので、入力ベクトルデータと特徴量が最も近いテンプレートベクトルデータから検索を行うことで、類似度の演算をより多く省略することができる。
【００６４】
また、本実施形態では、ベクトル量子化装置が取り扱うベクトルデータの次元を６次元としたが、ベクトルデータの次元は任意で良い。
また、図２のベクトル量子化装置は、専用のハードウェアで実現することも可能であるし、コンピュータ上のプログラムによってソフトウェアで実現することもできる。ハードウェアで実現する場合、新たに設けた特徴量演算部２０５、特徴量差分演算部２０６および演算省略判定部２０７は、それ程大きなハードウェア面積を必要としない。
【００６５】
また、上記実施形態において、ベクトルデータの特徴量としては、ベクトルデータの要素の総和に限定されるものではない。例えば、ベクトルデータの分散を使いたい場合は、特徴量演算部２０５と演算省略判定部２０７とを分散演算用のものに変更すれば良い。また、類似度を求める関数をマンハッタン距離以外の関数、例えばユークリッド距離を求める関数等に変更したい場合は、マンハッタン距離演算部２０２と最小マンハッタン距離記憶部２０３と演算省略判定部２０７とを変更すれば良い。
【００６６】
（第３の実施形態）
第３の実施形態では、上記第２の実施形態で示したベクトル量子化装置への入力として画像データを用い、上記実施形態のベクトル量子化装置を画像圧縮装置に応用した例を、図４および図５を使って説明する。まず、ベクトル量子化装置を使って画像圧縮を行う場合の一般的な例を図４により説明する。
【００６７】
図４において、入力される原画像４０１は、画素と呼ばれる要素が多数集まって構成されている。個々の画素は輝度値、あるいは色差信号などの情報を持っている。入力画像４０１中から複数画素で構成されるブロックを取り出したのが、入力画像ブロック４０２である。図４の例では、入力画像ブロック４０２の大きさとして４×４画素を選んでいるが、この大きさは何であっても良い。
【００６８】
入力画像ブロック４０２は、上述の通り複数の画素を持っているから、各々の画素が持つ輝度値などを集めてベクトルデータとすることができる。これを図２で説明したベクトル量子化装置の入力ベクトルデータＩとする。
【００６９】
人間の視覚特性上、入力画像４０１中の幾つかの入力画像ブロックは、見た目では殆ど同じに見える場合がある。こういった同じに見える複数の入力画像ブロックを、より少ない数の画像ブロックで代表させることが可能である。画像ブロックコードブック４０３は、入力画像４０１上の多数の入力画像ブロックを代表する画像ブロック（テンプレートベクトルデータ）を複数持ったものである。テンプレートベクトルデータは、画像ブロックコードブック４０３内の画像ブロック各々の画素が持つ輝度をベクトルデータとしたものである。
【００７０】
ベクトル量子化装置では、入力画像４０１全体を画像ブロックとして分割し、各々の画像ブロック４０２を入力ベクトルデータとして、その入力ベクトルデータに類似するテンプレートベクトルデータをコードブック４０３内から検索する。そして、該当するテンプレートベクトルデータの番号のみを転送することで、画像を圧縮することが可能である。圧縮された画像を再生して再現画像４０４を得るには、上記転送された番号に対応するテンプレートベクトルデータをコードブック４０３から読み出し、画像に当てはめれば良い。
【００７１】
本実施形態において、入力画像４０１中から画像ブロック４０２で示される入力ベクトルデータを取り出してしまえば、類似度を求める関数としてマンハッタン距離を用い、特徴量としてベクトルデータの要素の総和を用いた場合、ベクトル量子化の手順は上述した第２の実施形態と全く同一である（ここではその詳細な手順の説明は省略する）。よって、入力ベクトルデータに類似するテンプレートベクトルデータを検索する際、検索にまつわる演算を少なくできるので、高速な画像の圧縮が可能となる。
【００７２】
以上のような方法によって画像データに対してベクトル量子化の操作を行ったときに、マンハッタン距離の演算をどれほど省略できるのかを示したのが、図５である。図５は、屋外風景写真、屋内風景写真、人物写真を入力画像としたときに、様々なテンプレートベクトルデータ群に対して、各々のテンプレートベクトルデータ群の中でマンハッタン距離を演算しなければならないテンプレートベクトルデータの割合を表している。
【００７３】
この図５によると、テンプレートベクトルデータ群の中で、入力ベクトルデータとのマンハッタン距離を演算しなければならないテンプレートベクトルデータは、せいぜい１４％以内となっていることが分かり、本実施形態の有用性が示されている。
【００７４】
なお、以上の例では画素の輝度値をベクトルデータとしたが、輝度値だけでなく、各画素が有する数値化された情報は何であれベクトルデータとすることができる。また、入力画像４０１中から入力画像ブロック４０２を取り出した後、離散余弦変換をはじめとする様々な変換をかけ、変換後の画像からベクトルデータを作ってベクトル量子化装置の入力としても良い。
【００７５】
また、入力ベクトルデータが画像データの場合は、特徴量としてベクトルデータの要素の総和を用いても、画像データを周波数分解した際の直流成分を用いても、両者は等価である。何故ならば、上記直流成分は、ベクトルデータの要素の総和に対してある係数を掛けたものに過ぎないからである。
【００７６】
（第４の実施形態）
上記第２の実施形態で示したベクトル量子化装置への入力として画像データを用いた場合、ベクトルデータの特徴量として、画像特有の性質を使うことが可能である。本実施形態では、ベクトル量子化装置の入力を画像データとした場合の画像データ特有な特微量について説明し、幾つかの特徴量を組み合わせてベクトル量子化処理の演算量を減少させることが可能であることを以下に示す。
【００７７】
まず、画像データに対して、類似度を演算する関数をマンハッタン距離とし、特徴量としてベクトル要素の総和を用いた場合の問題点を、図６を使って説明する。図６において、入力ベクトルデータに対応する画像ブロック６０１と、テンプレートベクトルデータに対応する画像ブロック６０２は、ほぼ同じブロックである。一方、入力ベクトルデータに対応する画像ブロック６０１と、もう一方のテンプレートベクトルデータに対応する画像ブロック６０３は、全く上下左右が反転したブロックとなっており、見た目では全く異なるものである。
【００７８】
実際に、入力画像ブロック６０１とテンプレート画像ブロック６０２，６０３との画素の輝度値を取り出して、それぞれをベクトルデータとしてマンハッタン距離を演算すると、テンプレート画像ブロック６０３は、もう一方のテンプレート画像ブロック６０２と比較して入力画像ブロック６０１と類似していないことが明らかになる。
【００７９】
しかしながら、特徴量であるベクトルデータの要素の総和は、２つのテンプレート画像ブロック６０２と６０３とで等しい。このことは、特徴量としてベクトルデータの要素の総和を使っただけでは、無駄な類似度演算が多く残ることを意味している。
この問題を解決するための手段としては、特徴量として、ベクトルデータの各要素の一部を画素の明暗が反転するように操作した後の各要素の総和を使うという手段が考えられる。
【００８０】
図７は、ベクトルデータの要素の一部の明暗を反転させた場合、画像ブロックがどのように変化するかを表している。初期の画像ブロック７０１に対して、３種類の反転パターン７０２〜７０４を用いて、黒で塗りつぶされた部分の画素が明暗反転するように操作した結果が、反転後画像ブロック７０５〜７０７である。このように、１つの画像に対して異なる反転パターン７０２〜７０４で明暗反転をすると、初期の画像ブロックが同じでも、反転後画像ブロック７０５〜７０７の画素の輝度値の総和７０８〜７１０は異なった値となる。
【００８１】
また、図８は、ベクトルデータの要素の総和が等しい場合でも、ベクトルデータの要素の一部を画素の明暗が反転するように操作してから、ベクトルデータの要素の総和を求めて特徴量とすると、特徴量に差が現れてくる例を示したものである。図８において、初期の画像ブロック８０１と８０２は、画素の輝度値の総和は全く同じである。よって、ベクトルデータの要素の総和、すなわち、ブロック内の画素の輝度値の総和を特徴量としても両者は全く区別できない。
【００８２】
このような２つの初期画像ブロック８０１，８０２に対して、同じ反転パターン８０３の黒塗りの部分を明暗反転し、反転後の画像ブロック８０４，８０５について画素の輝度値の総和８０６，８０７を計算すると、両者は全く異なった値となる。
【００８３】
本実施形態は、以上のことを利用して、無駄なマンハッタン距離の演算を更に減少させることができるようにしたものである。すなわち、以上の例からも分かるように、ある特徴量を使ったときには省略できない類似度の演算が、別の特徴量を使うと省略できる場合がある。この場合、異なる特徴量を２つ以上利用して演算量を更に減少させることができる。
【００８４】
具体的には、ある特徴量でテンプレートベクトルデータの中から類似度を演算しなければならない範囲を絞り込み、別の特徴量で更に範囲を絞り込むという、２段階で特徴量を使う方法や、同時に２つの特徴量を使って、特徴量の差が大きい方を演算省略の判断に使う方法などが挙げられる。
【００８５】
なお、ある画像から入力画像ブロックを取り出してきてベクトル量子化装置の入力とする場合、上述の「ベクトルデータの要素の一部を画素の明暗が反転するように操作した後のベクトルデータの総和」の他にも、画像特有の特徴量がいくつか考えられる。以下では、画像ブロックの四隅の画素の情報を特徴量として使う方法と、画像ブロック上の画素値の変化の様子を特徴量として使う方法とを説明する。
【００８６】
最初に、画像ブロックの四隅の画素の情報を特徴量として使う方法について説明する。画像ブロックを入力画像中から取り出してきた場合に、ブロック内で画素値がある方向に滑らかに変化する画像に対しては、画像ブロックの四隅から特徴量を得ることができる。図９は、画像ブロックの四隅を特徴量として使う方法を説明した図である。
【００８７】
図９（ａ）において、画像ブロック９０１は、ブロックの右下から左上方向に輝度が徐々に明るくなる変化をしている。この画像ブロック９０１から四隅９０３を取り出し、それらの４画素の輝度値を比較すると、画像ブロック９０１はどのような方向に輝度が変化しているのかを把握することができる。
【００８８】
また、画像ブロック９０２とその四隅９０４は、画素値の変化する方向が上記とは異なる場合の一例を示すものであり、画像ブロックの右辺から左辺方向に輝度が徐々に明るくなる変化をしている。なお、９０３および９０４中に示した矢印は、画素の輝度の大小関係を示すものであり、矢印の先にある画素の方が輝度が大きい。また、輝度の大小に差がない場合には、線分で表している。
【００８９】
このように、画像ブロックの四隅の画素の間で輝度を大小比較し、大小を判別することで、画像ブロックの特徴を捉えることができる。四隅の画素の間での輝度の大小パターンは幾通りもあるので、それらのパターンを番号付けして特徴量とすることができる。すなわち、図９（ｂ）に示すように、四隅の画素の間での輝度の大小の各パターンに対して番号を付与し、その番号を特徴量として本実施形態のベクトル量子化装置に組み込むことができる。
【００９０】
なお、図９では、画像ブロックの大きさを４×４画素としているが、この大きさは任意で良い。また、画素値として輝度値を用いているが、他の画素値（例えば色信号値）を用いても良い。
【００９１】
次に、画像ブロック上での画素値の変化を特微量として使う方法を説明する。入力画像中から画像ブロックを幾つか切り出してくると、それらの画像ブロックの中には、画素値の変化の様子が似ているものがある。図１０は、画素値の変化の周期および変化率が同じである２つの画像ブロック１００１，１００２を示している。これらの画像ブロック１００１と１００２は何れも左右方向にのみ画素値が変化している。
【００９２】
画像ブロック１００１の左右方向の画素値の変化は、もう一方の画像ブロック１００２の左右方向の画素値の変化に所定の係数をかけて、変化の振幅を抑えたものに他ならない。このような状態を、画像ブロック１００１，１００２の画像ブロック上での画素値の変化のモードが同じであると言うことにする。
【００９３】
画像ブロック上での画素値の変化のモードは多数あるので、それらの変化のモードを番号付けすることにより特徴量とすることができる。すなわち、画素値の変化のモードに対してそれぞれ番号を付与し、その番号を特徴量として本実施形態のベクトル量子化装置に組み込むことができる。
なお、この図１０でも画像ブロックの大きさを４×４画素としているが、この大きさは任意で良い。
【００９４】
最後に、第１の特徴量として画像ブロック上での画素値の変化、つまり画像ブロック上での変化のモードを番号付けしたものを用いるとともに、第２の特徴量として画像ブロック上の画素の値の総和、つまりベクトルデータの要素の総和を用いた場合の、第４の実施形態に係るベクトル量子化装置の構成を、図１１を用いて説明する。なお、図１１において、図２に示したブロックと同じブロックには同一の符号を付している。また、ここでは類似度をマンハッタン距離によって求めている。また、図１１中ではベクトルデータを、相当する画像ブロックとして視覚的に表現している。
【００９５】
入力ベクトルデータＩは、第１の特徴量である画像ブロック上での画素値の変化モードによって分類される。すなわち、変化モード判定部１１０１は、画素値の変化モードの典型的なベクトルデータを集めた特徴テンプレート記憶部１１０２に記憶されているベクトルデータの情報をもとに、入力ベクトルデータＩの第１の特徴量である画像ブロック上での画素値の変化モードが、テンプレートの何番に相当するものであるかを示すデータ２ｈを出力する。
【００９６】
テンプレートベクトルデータを記憶するテンプレート記憶部２０１と、テンプレートベクトルデータの第２の特徴量であるベクトルデータの要素の総和を記憶する特徴量記憶部２０４の内部には、第１の特徴量の種類ごとにデータが並べられている。図１１の例では、入力ベクトルデータＩの第１の特徴量は“２”と判断されたので、テンプレート記憶部２０１と特徴量記憶部２０４の中から、第１の特徴量が“２”となる部分１１０３のみが選択され、残りの部分は検索対象外となる。
【００９７】
テンプレート記憶部２０１および特徴量記憶部２０４の中で、以上のようにして第１の特徴量が“２”となる部分１１０３に関してのみ、上記第２の実施形態と同様の手順でテンプレートベクトルデータの検索を行う。すなわち、入力ベクトルデータＩの第２の特徴量を特徴量演算部２０５で演算し、その結果２ｆと、特徴量記憶部２０４内の特徴量２ｅとを用いて、特徴量差分演算部２０６ならびに演算省略判定部２０７により、テンプレート記憶部２０１内の第１の特徴量が“２”となるテンプレートベクトルデータの中でも特にマンハッタン距離の演算が必要ないものを判断する。
【００９８】
以上のように、第４の実施形態によれば、第２の実施形態で説明したように特徴量を単独で使う場合に比べて、より多くの演算を省略することができる。これは、第１の特徴量によってあらかじめ検索対象となるテンプレートベクトルデータの範囲を限定し、第２の特徴量で更に検索対象を絞り込むようにしているからである。これによって、特徴量を１つだけ使う場合に比べてより多くの演算の省略が可能となり、より高速に演算を行うことができる。
【００９９】
また、テンプレートベクトルデータは、第１の特徴量だけでなく、第２の特徴量の大きさ順によっても並べることで２次元的な配列にしておくことにより、入力ベクトルデータＩと第２の特徴量が似たテンプレートベクトルデータから検索を始めることができるので、入力ベクトルデータＩと類似するテンプレートベクトルデータをより効率的に検索することができる。
なお、図１１では、画像ブロックの大きさとして４×４画素、つまりベクトルデータに直せば１６次元のものを例に説明したが、この大きさは任意である。
【０１００】
（第５の実施形態）
次に、本発明の第５の実施形態について説明する。第５の実施形態では、１つのベクトルデータを幾つかの部分に分解し、分解した各々の部分についての特徴量を利用してテンプレートベクトルデータの検索にまつわる演算量を減少させる方法を説明する。
【０１０１】
図１２は、第５の実施形態によるベクトル量子化装置の構成例を示すブロック図である。図１２では、４×４画素で構成される画像ブロックを１６次元の入力ベクトルデータとし、この入力ベクトルデータを４次元のベクトル４つに分割して各々の特徴量を求め、それを利用して類似度の演算を減少させる方法を説明している。なお、図１２中では、画像ブロックの形でベクトルデータを視覚的に表現している。また、図１２の例では、特徴量として、ベクトルデータの各要素の平均値を利用している。
【０１０２】
図１２において、部分毎の平均値演算部１２０１は、入力ベクトルデータｄ１を４つの部分（２×２画素のブロック）に分割し、各々の部分について特徴量である平均値を演算する。これにより、１つの入力ベクトルデータｄ１から特徴量は４つ算出され、それらを１つの特徴量ベクトルデータｄ２として出力する。平均値演算部１２０１内に視覚的に表現した４つのブロックの各々は、４つに分割された領域の特徴量を示している。
【０１０３】
一方、テンプレート記憶部１２０２に記憶されるテンプレートベクトルデータについては、あらかじめ、入力ベクトルデータと同様の手順で４分割された領域毎に特徴量が求められて１つの特徴量ベクトルデータが生成される。そして、その特徴量ベクトルデータの似ているもの同士を集めて集合とし、集合毎にテンプレートベクトルデータが記憶される。また、各集合毎にユニークな番号を付ける。例えば枠１２０５で示される縦１列が、１つの集合に相当する。
【０１０４】
さらに、テンプレートベクトルデータの上記集合を代表する特徴量ベクトルデータ１２０６が各集合毎に生成され、これもテンプレート記憶部１２０２に記憶される。これらの各集合を代表する特徴量ベクトルデータ１２０６のことを、以下では「テンプレート概形データ」と称する。テンプレート概形データ１２０６には、上記集合と同じ番号が振られている。このテンプレート概形データ１２０６および番号は、テンプレート概形データ記憶部１２０３にも保存される。
【０１０５】
入力ベクトルデータｄ１から抽出された特徴量ベクトルデータｄ２は、テンプレート概形データ記憶部１２０３からの各テンプレート概形データｄ３と共に概形判断部１２０４に入力される。概形判断部１２０４は、入力ベクトルデータｄ１の特徴量ベクトルデータｄ２と最も似ているテンプレート概形データを判断し、その番号ｄ４を出力する。これにより、テンプレート記憶部１２０２からは、出力された番号ｄ４に対応する集合のテンプレートベクトルデータのみが読み出される。
【０１０６】
類似度演算部１２０７は、概形判断部１２０４より出力された番号ｄ４に対応するテンプレートベクトルデータの集合のみを検索対象として類似度の演算を実行する。図１２の例では、概形判断部１２０４より“４”の番号が出力されているので、類似度演算部１２０７は、これに対応する集合１２０５のテンプレートベクトルデータのみを対象として類似度の演算を行う。これにより、テンプレートベクトールデータの検索にまつわる演算量を減少させることができる。
【０１０７】
なお、以上の実施形態ではテンプレート記憶部１２０２内にテンプレート概形データ１２０６も併せて記憶しているが、入力される番号ｄ４に対応するテンプレートベクトルデータの集合を識別できるように構成していれば、このテンプレート概形データ１２０６は必ずしも記憶する必要はない。
また、上記の実施形態では、入力ベクトルデータの大きさとして４×４画素を用い、分割する各々の大きさを２×２画素としたが、これらは何れも単なる例に過ぎず、これに限定されるものではない。
【０１０８】
（第６の実施形態）
次に、本発明の第６の実施形態を説明する。以上の各実施形態では、検索対象とするテンプレートベクトルデータの数を減らすことはできたが、それらは全数順次に検索する必要がある。これに対して、本実施形態では、ベクトル量子化装置をハードウェアにより構成する場合に、類似度の演算を並列化する仕組みを導入することにより、更なる演算の高速化を図るものである。
【０１０９】
図１３は、本実施形態によるベクトル量子化装置のハードウェア構成例を示す図である。図１３において、テンプレート記憶装置１３０１は、複数のメモリ部２，３，…，４を備え、２次元的な記憶領域を有しており、それぞれに複数のテンプレートベクトルデータを記憶している。そして、アドレス部１のある部分が指定されると、そのアドレスで示される行（横一列）に記憶されている複数のテンプレートベクトルデータが各メモリ部２，３，…，４から並列的に読み出されるようになっている。
【０１１０】
このテンプレート記憶装置１３０１には、複数のテンプレートベクトルデータが、図の左下から右上に向かって特徴量（例えばベクトルデータの各要素の平均値）の大きさ順に格納されている。例えば、２行目（アドレス０１）に格納されているテンプレートベクトルデータの特徴量は、１行目（アドレス００）に格納されているテンプレートベクトルデータの特徴量より大きい。
【０１１１】
したがって、同じ行アドレスには、ある程度特徴量の似通ったテンプレートベクトルデータが複数格納されている。なお、行を跨いで同じ特徴量のテンプレートベクトルデータが存在する場合もあり得る。特徴量範囲記憶装置１３０２は、同じ行に格納されているテンプレートベクトルデータの特徴量の範囲を記憶している。
【０１１２】
また、特徴量演算装置１３０３は、入力ベクトルデータの特徴量（ベクトルデータの各要素の平均値）を求めるものである。検索開始行決定装置・検索行カウンタ１３０４は、この特徴量演算装置１３０３により算出された入力ベクトルデータの特徴量と、特徴量範囲記憶装置１３０２に記憶されている特徴量の範囲とに基づいて、類似度の演算を行うべきテンプレートベクトルデータの検索範囲を決定する。
【０１１３】
すなわち、特徴量の近似している２つのベクトルは類似度が大きい傾向があるので（言い換えると、特徴量の似ていない２つのベクトルは類似度が小さい傾向がある）、入力ベクトルデータの特徴量が特徴量範囲記憶装置１３０２内のどの範囲に属するかを見ることによって、テンプレート記憶装置１３０１内のどの行に、入力ベクトルデータとの類似度が大きくなるテンプレートベクトルデータがあるかを判断できる。そして、その行のみを対象として類似度の演算を実行すれば足りることとなる。
【０１１４】
そこで、検索開始行決定装置・検索行カウンタ１３０４は、算出された入力ベクトルデータの特徴量と、特徴量範囲記憶装置１３０２内の特徴量の範囲とに基づいて、入力ベクトルデータの特徴量とある程度近似する特徴量を持ったテンプレートベクトルデータが格納されている１つまたは複数の行を検索範囲１３０７として決定し、検索行カウンタの値を検索開始行１３０８から順次インクリメントしていく。
【０１１５】
これにより、上記検索行アドレスで指定される行の各テンプレートベクトルデータがメモリ部２，３，…，４より並列的に読み出され、類似度演算装置１３０５に与えられる。類似度演算装置１３０５は、列毎の類似度演算・記憶装置５，６，…，７を備えており、各メモリ部２，３，…，４から読み出された複数のテンプレートベクトルデータを並列的に処理し、それぞれの列の中での最大類似度とそれを与えたときの行アドレスとを特定する。
【０１１６】
各類似度演算・記憶装置５，６，…，７は、例えば、図１４のように構成される。図１４において、類似度演算装置１４０１は、入力ベクトルデータと各テンプレートベクトルデータとの類似度を順次算出し、その算出結果を類似度一時記憶装置１４０２に格納する（なお、この類似度一時記憶装置１４０２は必ずしも必要ではない）。比較器１４０３は、類似度一時記憶装置１４０２からの類似度と、最大類似度記憶装置１４０４に格納されている、現在までに見つかっている最大類似度とを比較し、どちかが大きいかを判断する。
【０１１７】
ここで、類似度一時記憶装置１４０２から与えられる今回算出された類似度の方が大きい場合は、その旨を内容更新制御装置１４０５に伝え、この制御に従って最大類似度記憶装置１４０４の内容を上記今回算出された類似度の値に書き換える。これと同時に内容更新制御装置１４０５は、そのとき検索開始行決定装置・検索行カウンタ１３０４より入力されている検索行アドレスを最大類似度アドレス記憶装置１４０６に記憶する。
【０１１８】
ある１つの入力ベクトルデータについて検索範囲１３０７内の全てのテンプレートベクトルデータとの類似度演算が終了したとき、この最大類似度記憶装置１４０４および最大類似度アドレス記憶装置１４０６に記憶されているものが、検索範囲１３０７の各列の中で入力ベクトルデータに最も類似するテンプレートベクトルデータの類似度およびそれを与えたときの行アドレスである。そして、これらのデータは、図１３の最大類似度テンプレートアドレス特定装置１３０６に出力される。
【０１１９】
最大類似度テンプレートアドレス特定装置１３０６は、各列の類似度演算・記憶装置５，６，…，７より出力されたそれぞれの列における最大類似度およびそれを与えたときの行アドレスとに基づいて、テンプレート記憶装置１３０１全体の中で最も類似度が大きいテンプレートベクトルデータのアドレスを特定し、それをコード番号として出力する。
【０１２０】
図１５は、上記図１３および図１４のように構成したベクトル量子化装置の動作を示すフローチャートである。図１５において、まずステップＳ１１で初期化処理を行う。ここでは、各類似度演算・記憶装置５，６，…，７内に備えられた最大類似度記憶装置１４０４および最大類似度アドレス記憶装置１４０６の記憶内容をクリアする処理を行う。
【０１２１】
次に、ステップＳ１２で、特徴量演算装置１３０３によって入力ベクトルデータの特徴量を計算する。そして、ステップＳ１３で、その算出した入力ベクトルデータの特徴量をもとに特徴量範囲記憶装置１３０２内の情報を参照し、入力ベクトルデータと特徴量が最も似ているテンプレートベクトルデータが記憶されている行を特定する。そして、その特定した行から一定のオフセットを引いて検索開始行１３０８を決定する。
【０１２２】
次に、ステップＳ１４で、検索開始行決定装置・検索行カウンタ１３０４に上記決定した検索開始行１３０８をセットする。検索行カウンタは、現在検索している行（アドレス）を指し示すものである。次のステップＳ１５では、上記検索行カウンタが示している行に格納されている複数のテンプレートベクトルデータについて、各列の類似度演算・記憶装置５，６，…，７で並列的に類似度を算出し、その結果に応じてそれぞれの列で適宜最大類似度記憶装置１４０４および最大類似度アドレス記憶装置１４０６の更新処理を実行する。
【０１２３】
そして、ステップＳ１６で検索行カウンタの値がまだ検索範囲１３０７内かどうかを判断し、そうであればステップＳ１７に進んで上記検索行カウンタを１だけ増やした後、ステップＳ１５の処理に戻る。一方、検索行カウンタが所定の値になって検索範囲１３０７を越えると、検索処理は終了する。この段階で、各列の最大類似度記憶装置１４０４には、その列内で最も大きかった類似度の値が記憶されており、各列の最大類似度アドレス記憶装置１４０６には、その列内で最も大きな類似度を出したテンプレートベクトルデータの格納されていた行アドレスが記憶されている。
【０１２４】
最後に、ステップＳ１８で最大類似度テンプレートアドレス特定装置１３０６は、各列の最大類似度記憶装置１４０４に記憶されている類似度をもとに、どの列に入力ベクトルデータとの類似度が最も大きいテンプレートベクトルデータがあるかを判断し、その列アドレスを特定する。さらに、その特定した列の最大類似度アドレス記憶装置１４０６に記憶されている行アドレスと合わせて最終的なアドレスを発生する。
【０１２５】
以上のように、第６の実施形態によれば、ベクトルデータから抽出される特徴量に基づいて検索対象の範囲を絞り込んでいるので、類似度演算を行うテンプレートベクトルデータの数を少なくすることができ、演算時間を短くすることができる。さらに、本実施形態では、ベクトル量子化装置をハードウェア構成するに当たって、類似度の演算を並列処理する仕組みを取り入れているので、演算時間を更に短くすることができる。
【０１２６】
なお、上述のように検索範囲をテンプレート記憶装置１３０１内の一部の行に限定した場合、入力ベクトルデータとの類似度が最大となるテンプレートベクトルデータを必ず選択できるという保証はなくなる。しかしながら、特徴量の似通った範囲内で検索を行っているので、見た目の上では問題ないほど似ているテンプレートベクトルデータが選ばれることとなり、実用上問題なく適用することができる。
【０１２７】
（その他の実施形態）
上記様々な実施形態に示した各機能ブロックおよび処理手順は、ハードウェアにより構成しても良いし、ＣＰＵあるいはＭＰＵ、ＲＯＭおよびＲＡＭ等からなるマイクロコンピュータシステムによって構成し、その動作をＲＯＭやＲＡＭに格納された作業プログラムに従って実現するようにしても良い。また、上記各機能ブロックの機能を実現するように当該機能を実現するためのソフトウェアのプログラムをＲＡＭに供給し、そのプログラムに従って上記各機能ブロックを動作させることによって実施したものも、本発明の範疇に含まれる。
【０１２８】
この場合、上記ソフトウェアのプログラム自体が上述した各実施形態の機能を実現することになり、そのプログラム自体、およびそのプログラムをコンピュータに供給するための手段、例えばかかるプログラムを格納した記録媒体は本発明を構成する。かかるプログラムを記憶する記録媒体としては、上記ＲＯＭやＲＡＭの他に、例えばフロッピーディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｉ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ、ｚｉｐ、磁気テープ、あるいは不揮発性のメモリカード等を用いることができる。
【０１２９】
また、コンピュータが供給されたプログラムを実行することにより、上述の実施形態の機能が実現されるだけでなく、そのプログラムがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）あるいは他のアプリケーションソフト等の共同して上述の実施形態の機能が実現される場合にもかかるプログラムは本発明の実施形態に含まれることは言うまでもない。
【０１３０】
さらに、供給されたプログラムがコンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後、そのプログラムの指示に基づいてその機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって上述した実施形態の機能が実現される場合にも本発明に含まれることは言うまでもない。
【０１３１】
【発明の効果】
本発明は上述したように、検索対象の範囲を狭く制限することができ、入力ベクトルデータとテンプレートベクトルデータとの類似度を求める演算量を少なくすることができる。これにより、ベクトル量子化の演算を全体として高速に行うことができる。
【０１３２】
また、本発明の他の特徴によれば、異なる複数の特徴量を用いて検索対象とするテンプレートベクトルデータを選択するようにしたので、検索対象の範囲を更に狭く制限することができ、ベクトル量子化の演算を更に高速に行うことができる。
また、本発明のその他の特徴によれば、検索対象とされた複数のテンプレートベクトルデータを並列的に処理する仕組みを導入したので、ベクトル量子化の演算を更に高速に行うことができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態によるベクトル量子化装置の構成を示す図である。
【図２】本発明の第２の実施形態によるベクトル量子化装置の構成を示す図である。
【図３】本発明の第２の実施形態によるベクトル量子化装置の動作を示すフローチャートである。
【図４】本発明の第３の実施形態を示し、ベクトル量子化装置への入力を画像データとして画像圧縮を行う方法を説明するための概念図である。
【図５】本発明の第３の実施形態を示し、類似度の演算確率を示す図である。
【図６】本発明の第４の実施形態について説明するための図である。
【図７】本発明の第４の実施形態について説明するための図である。
【図８】本発明の第４の実施形態について説明するための図である。
【図９】本発明の第４の実施形態について説明するための図である。
【図１０】本発明の第４の実施形態について説明するための図である。
【図１１】本発明の第４の実施形態によるベクトル量子化装置の構成を示す図である。
【図１２】本発明の第５の実施形態によるベクトル量子化装置の構成を示す図である。
【図１３】本発明の第６の実施形態によるベクトル量子化装置の構成を示す図である。
【図１４】図１３に示した類似度演算・記憶装置の構成を示す図である。
【図１５】本発明の第６の実施形態によるベクトル量子化装置の動作を示すフローチャートである。
【符号の説明】
１０４  特徴量記憶部
１０５  特徴量演算部
１０６  演算省略判定部
２０１  テンプレート記憶部
２０２  マンハッタン距離演算部
２０３  最小マンハッタン距離記憶部
２０４  特徴量記憶部
２０５  特徴量演算部
２０６  特徴量差分演算部
２０７  演算省略判定部
２０８  アドレスカウンタ
２０９  最小距離アドレス記憶部
１１０１  変化モード判定部
１１０２  特徴テンプレート記憶部
１２０１  部分毎の平均値記憶部
１２０２  テンプレート記憶部
１２０３  テンプレート概形データ記憶部
１２０４  概形判断部
１３０１  テンプレート記憶装置
１３０２  特徴量範囲記憶装置
１３０３  特徴量演算装置
１３０４  検索開始行決定装置・検索行カウンタ
１３０５  類似度演算装置
１３０６  最大類似度テンプレートアドレス特定装置
【図１】
0003676577.tif 000004
【図２】
0003676577.tif 000005
【図３】
0003676577.tif 000006
【図４】
0003676577.tif 000007
【図５】
0003676577.tif 000008
【図６】
0003676577.tif 000009
【図７】
0003676577.tif 000010
【図８】
0003676577.tif 000011
【図９】
0003676577.tif 000012
【図１０】
0003676577.tif 000013
【図１１】
0003676577.tif 000014
【図１２】
0003676577.tif 000015
【図１３】
0003676577.tif 000016
【図１４】
0003676577.tif 000017
【図１５】
0003676577.tif 000018