鏡映群を用いた単位超球面ベクトル量子化の高速最近傍探索法

槙 修一  山根 延元  森川 良孝  

誌名
電子情報通信学会論文誌 A   Vol.J90-A   No.3   pp.201-209
発行日: 2007/03/01
Online ISSN: 1881-0195
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: 情報理論
キーワード: 
超球面ベクトル量子化,  最近傍探索,  鏡映群,  前量子化,  ボロノイ領域,  

本文: PDF(990.9KB)>>
論文を購入




あらまし: 
単位超球面上のベクトル量子化(VQ)の高速化法を提案する.一般的なVQにおいて最近傍探索量子化を全探索(FS)によって行えば多くの演算量が必要であり問題となっている.FSVQの演算量を削減する方法が数多く存在するが,その一つとして2段階探索法が知られている.これは入力ベクトルを前量子化器(PQ)によって高速に量子化を行い,その量子化出力をもとに最近傍の候補を削減するものである.従来法のPQにはスカラ量子化(SQ)が採用(P-SQ)されているが,本論文では超球面VQの高速化を目的として,PQに鏡映群を利用した万華鏡VQ(KVQ)を用いる.KVQはベクトルの成分の符号反転とソートによる簡単な処理及び少量の距離計算によって量子化を行うことができPQに適している.提案法では,4及び8次元の単位超球面一様分布に対して設計された符号帳において,直接FSVQを行う計算量の3%程度まで,メモリ量をP-SQ法に比べて8~30%程度まで削減できることを示す.また,候補符号帳を作成するための計算量を削減するために新たに棄却領域を提案し,従来法で必要な計算量に比べて5%まで削減できることを示す.