最近傍探索を用いた高速フラクタル圧縮

大西 秀明  和田 俊和  

誌名
電子情報通信学会論文誌 D   Vol.J100-D   No.12   pp.964-973
発行日: 2017/12/01
Online ISSN: 1881-0225
論文種別: 論文
専門分野: 画像・映像処理
キーワード: 
フラクタル画像圧縮,  最近傍部分空間探索,  最近傍探索,  高速化,  

本文: PDF(1.4MB)
>>論文を購入


あらまし: 
画像を写像の不動点として符号化するフラクタル圧縮は,単に画像圧縮だけでなく,部分画像の共起性に基づくテクスチャの分析や超解像処理などにも利用することができ,これまでに数多くの研究が行われてきた.フラクタル圧縮では,局所的な画像ブロック(ドメイン)から他の画像ブロック(レンジ)への縮小写像を求めることで,符号化を行う.このとき,様々なドメインに対してレンジとの誤差が最小になるように「明るさの倍率」と「オフセット」を求め,誤差が最小となるドメインを探索する「最近傍部分空間探索問題」を解かなければならず,探索に要する計算コストが極めて高い.本論文では,この最近傍部分空間探索問題の特殊性に着目し,一切の近似を導入することなく,単なる最近傍探索問題に変換できることを示す.D. Saupeも同様に最近傍探索によってフラクタル圧縮の高速化を図っているが,その問題設定の検討が不十分である.本論文では,より一般的に問題の変換を行うことにより,様々な条件での最近傍探索問題の設定が可能になり,これら全てを比較することによって,D. Saupeの高速化よりも更に高速化が可能であることを示す.また,この解釈に基づき,フラクタル圧縮の拡張法についても論じる.