(57)【要約】  【課題】  符号化による画質劣化をきたすことなく、符号化量を低減できるフラクタル画像圧縮の符号化量低減装置を提供することにある。  【解決手段】  原画像１０は、画像分割・抽出部１でレンジブロックに分割され、かつ該レンジブロックは１つずつ抽出されて、シェード／エッジブロック判定部２および最適ドメインブロック決定部３に送られる。探索距離指定部４は前記レンジブロックがエッジブロックであった場合の、ドメインブロックの探索距離または探索範囲を指定する。最適ドメインブロック決定部３は該指定された探索範囲内から最適ドメインブロックを決定する。レンジブロックデータ作成部５は、前記レンジブロックがシェードの場合には符号化情報として輝度情報を作成し、一方エッジの場合には、対応するドメインブロックの位置情報（近傍領域）、輝度変換情報、回転・反転変換情報、細分化情報を作成する。  【選択図】  図１
2006067300.tif 000002
【特許請求の範囲】
【請求項１】
原画像を所定サイズのレンジブロックに分割し、該レンジブロックがエッジブロックの場合に該レンジブロックが参照するドメインブロックを決定するフラクタル画像圧縮の符号化量低減装置において、
前記レンジブロックが参照するドメインブロックを探索する範囲を指定する探索範囲指定手段を具備し、
該探索範囲指定手段は、ドメインブロックの探索範囲を当該レンジブロックを含む近傍に限定することを特徴とするフラクタル画像圧縮の符号化量低減装置。
【請求項２】
請求項１に記載のフラクタル画像圧縮の符号化量低減装置において、
フラクタル画像圧縮のデータ構造中のレンジブロックデータを作成するレンジブロックデータ作成手段をさらに具備し、
該レンジブロックデータ中の、対応するドメインブロックの位置情報の情報量を前記探索範囲の限定に伴って低減したことを特徴とするフラクタル画像圧縮の符号化量低減装置。
【請求項３】
請求項１または２に記載のフラクタル画像圧縮の符号化量低減装置において、
前記探索範囲指定手段は、当該レンジブロックからの距離によりドメインブロックの探索範囲を指定することを特徴とするフラクタル画像圧縮の符号化量低減装置。
【請求項４】
請求項１ないし３のいずれかに記載のフラクタル画像圧縮の符号化量低減装置において、
前記探索範囲指定手段は、原画像のサイズに依存したドメインブロックの探索範囲を指定することを特徴とするフラクタル画像圧縮の符号化量低減装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はフラクタル画像圧縮の符号化量低減装置に関し、特にドメインブロックの位置情報を低減して符号化量を低減するようにしたフラクタル画像圧縮の符号化量低減装置に関する。
【背景技術】
【０００２】
フラクタル画像符号化は、まず画像を重複しないレンジブロックに分割し、その各レンジブロックに対して大きなブロック（ドメインブロック）を抜き出し、それに縮小変換、回転、鏡像変換、および／またはアフィン変換を加えた上で、最もレンジブロックと相似したドメインブロックを探し出し、その画像間の関係情報を符号として送信または記憶するものである。
【０００３】
図８は、フラクタル画像圧縮のデータ構造例を示し、該データは、同図(a)に示されているように、ヘッダ（３６０ビット）８１、レンジブロックデータ８２、レンジブロックデータ８３、・・・・、レンジブロックデータ８ｎから構成されている。同図(b)は、レンジブロックがシェードブロックの場合のレンジブロックデータ８２のデータ構造を示し、レンジ／ドメインフラグと輝度情報とから構成される。レンジ／ドメインフラグには１ビット、輝度情報には８ビットを必要とされる。
【０００４】
次に、同図(c)は、レンジブロックがシェードブロックでない場合、すなわちエッジブロックの場合のレンジブロックデータ８３のデータ構造を示す。レンジブロックがエッジブロックの場合には、レンジブロックはドメインブロックを参照して符号化する。このため、そのデータ構造は、レンジ／ドメインフラグ、対応するドメインブロックの位置、輝度変換情報、回転／反転変換、および細分化フラグから構成される。必要とされるビット数は、「対応するドメインブロックの位置」のビット数を除いて、それぞれ１ビット、（４＋６）ビット、３ビット、および１ビットである。
【０００５】
前記「対応するドメインブロックの位置」のビット数は、原画像のサイズおよびドメインブロックのサイズに依存し、例えば画像のサイズが横３５２画素、縦２４０画素、ドメインブロックのサイズが８画素×８画素の場合には、横、縦方向の位置指定にそれぞれ６ビット、５ビットを必要とし、合計で１１ビットとなる。この画面内のドメインブロックの位置情報のビット数は画面のサイズに依存するため、原画像が大きくなるほどレンジブロックのデータビットが多くなる。
【０００６】
前記のことから、レンジブロックがエッジブロックの場合のビット数（図８の例では、２６ビット）はシェードブロックの場合のビット数（９ビット）に比べて多く、またエッジブロックの場合のビット数の中で「対応するドメインブロックの位置」の情報のビット数（１１ビット）が占める割合が大きいことが分かる。
【０００７】
なお、画質の劣化が少なくかつ圧縮率の高い画像圧縮装置を提供する従来技術として、例えば下記の特許文献１に記されたようなものがある。
【特許文献１】特開平９−１８８７７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
前記したように、レンジブロックがエッジブロックの場合、ドメインブロックの位置情報のビット数が大きく、フラクタル画像圧縮の符号化効率が悪いという課題があったが、従来はこの課題を解消するために格別の配慮が何らされていなかった。
【０００９】
本願発明の目的は、前記した従来技術の課題を解消し、符号化による画質劣化をきたすことなく、従来方式に比べて符号化量を低減できるフラクタル画像圧縮の符号化量低減装置を提供することにある。
【課題を解決するための手段】
【００１０】
前記した目的を達成するために、本発明は、原画像を所定サイズのレンジブロックに分割し、該レンジブロックがエッジブロックの場合に該レンジブロックが参照するドメインブロックを決定するフラクタル画像圧縮の符号化量低減装置において、前記レンジブロックが参照するドメインブロックを探索する範囲を指定する探索範囲指定手段を具備し、該探索範囲指定手段は、ドメインブロックの探索範囲を当該レンジブロックを含む近傍に限定した点に第１の特徴がある。
【００１１】
また、フラクタル画像圧縮のデータ構造中のレンジブロックデータを作成するレンジブロックデータ作成手段をさらに具備し、該レンジブロックデータ中の、対応するドメインブロックの位置情報の情報量を前記探索範囲の限定に伴って低減するよにした点に第２の特徴がある。
【発明の効果】
【００１２】
本願発明によれば、レンジブロックがエッジブロックの場合に該レンジブロックが参照するドメインブロックの探索範囲を当該レンジブロックを含む近傍に限定したので、該ドメインブロックの位置情報を従来方式に比べて大きく低減することができるようになる。このため、フラクタル画像圧縮における符号化量の低減を図ることができるようになる。
【００１３】
また、該ドメインブロックの位置情報は、原画像の画面サイズが大きくなっても一定であるので、原画像の画面サイズが大きくなる程、符号化量の低減の割合が大きくなる。
【発明を実施するための最良の形態】
【００１４】
以下に、図面を参照して、本発明を詳細に説明する。図１は、本願発明の一実施形態の概略の構成を示すブロック図である。
【００１５】
画像分割・抽出部１は、図２に示されているように、符号化すべき原画像１０を例えば４×４画素のレンジブロックＲ１、Ｒ２、・・・、Ｒｎ（ｎは正の整数）に分割し、該レンジブロックを順次１個ずつ抽出する。該抽出されたレンジブロックは、シェード／エッジブロック判定部２と最適ドメインブロック決定部３に送られる。シェード／エッジブロック判定部２では、レンジブロックがシェードブロックであるかエッジブロックであるかの判定をする。この判定は、例えば、レンジブロック内の輝度値の分散値がある閾値以上のものをエッジブロック、該閾値より小さいものをシェードブロックとする。該シェード／エッジブロック判定部２においてエッジブロックであると判定されると、その旨が最適ドメインブロック決定部３に送られる。ドメインブロックＤ１、Ｄ２、・・・、Ｄｍ（ｍは正の整数でかつｍ＜ｎ）は、図２に示されているように、前記レンジブロックＲ１、Ｒ２、・・・、Ｒｎより大きなサイズのブロックであり、例えば８×８画素で構成されている。
【００１６】
探索距離（または、探索範囲）指定部４は、前記最適ドメインブロック決定部３で、対応するレンジブロックに係るドメインブロックの探索距離あるいは探索範囲を指定する。なお、符号化される当該レンジブロックの位置情報は前記画像分割・抽出部１から通知される。例えば、レンジブロックから探索距離０，１，２、３、・・・と指定される。図３に示されているように、探索距離０の場合には、当該レンジブロックＲｐを含むドメインブロック（探索範囲：Ｄｑ１）を参照する。この場合の参照ドメインブロック数は１である。探索距離１の場合は、当該レンジブロックＲｐを含むドメインブロックとその周辺のドメインブロック（探索範囲：Ｄｑ２）を参照する。この場合の参照ドメインブロック数は９である。さらに、探索距離２の場合は、当該レンジブロックＲｐを含むドメインブロックとその周辺およびさらにその周辺のドメインブロック（探索範囲：Ｄｑ３）を参照する。この場合の参照ドメインブロック数は２５である。なお、該探索距離あるいは探索範囲は、原画像のサイズに依存させて決定することもできる。例えば、原画像サイズの１０％とか２０％と決めることもできる。また、図示のような正方形に限らず、長方形、楕円、菱形、多角形などの探索範囲とすることができる。
【００１７】
図１の最適ドメインブロック決定部３は、探索距離指定部４で指定された探索距離または探索範囲内のドメインブロックから最適のものを決定する。例えば、該探索範囲内の各ドメインブロックをレンジブロックと同じサイズに縮小変換し、該縮小変換により得られた縮小パターンを、例えば０度、９０度、１８０度および２７０度に回転変換し、それぞれの回転をされた縮小パターンに対して輝度変換を行うことにより合計８種類の縮小パターンを得、その中のレンジブロックとの誤差が最小となる縮小パターンを有するドメインブロックが最適のものとして決定される。
【００１８】
レンジブロックデータ作成部５は、図４(a)に示されているような、フラクタル画像圧縮データ４１中のレンジブロックデータ４１ａ、４１ｂ、・・・、４１ｎを作成する。例えば、該当するレンジブロックがシェードブロックである場合には、同図(b)に示されているように、輝度情報（８ビット）を作成する。一方、エッジブロックである場合には、同図(c)に示されているように、対応するドメインブロックの位置情報（近傍領域）、輝度変換情報（４ビット＋６ビット）、回転・反転変換情報（３ビット）、および細分化フラグ（１ビット）を作成する。ここで、レンジブロックデータ４１ｂ中の、「対応するドメインブロックの位置情報」を除くデータに要するビット数は、従来方式の場合と同じである。
【００１９】
本実施形態では、前記探索距離指定部４で当該レンジブロックに対応するドメインブロックの探索範囲を制限するようにしたので、該ドメインブロックの位置情報のビット数を大きく削減することができるようになる。例えば、探索距離が０、１の場合は１ビット、探索距離が２，３の場合は２ビット、探索距離が４〜７の場合は３ビット、探索距離が８〜１５の場合は４ビットとなり、従来方式の１１ビットに比べて大きく削減することができる。
【００２０】
次に、本実施形態の動作を、図５のフローチャートを参照して説明する。ステップＳ１では、ヘッダでドメインブロックの探索距離を指定する。すなわち、レンジブロックから何個まで離れたドメインブロックまでを探索するかを指定する。ステップＳ２では、原画像を隙間なくレンジブロックに分割する（総数をＮ個とする）。ステップＳ３では、レンジブロックの番号を表す置き数ｎを１とする。ステップＳ４では、第ｎ番目のレンジブロックを抽出する。ステップＳ５では、該抽出したレンジブロックがシェードブロックであるか否かの判断をする。この判断が肯定の場合にはステップＳ６およびＳ７をスキップしてステップＳ８に進む。一方、否定の時、すなわちエッジブロックの時には、ステップＳ６に進んで、前記探索距離内のドメインブロックを抽出する。ステップＳ７では、該探索距離内のドメインブロックの中から最適のドメインブロックを決定する。ステップＳ８では、ｎ＝Ｎ＋１が成立するか否かの判断がなされ、この判断が否定の時にはステップＳ９に進んでｎに１が加算される。そして、再度前記ステップＳ４〜Ｓ９の処理が繰り返される。最後に、ステップＳ８の判断が肯定になると、前記した一連の処理は終了する。
【００２１】
以上の説明から明らかなように、本実施形態によれば、レンジブロックが参照するドメインブロックが原画像のサイズ依存ではなく、指定した探索距離依存となるため、レンジブロック毎の必要符号化量を、最大１０ビット低減することが可能になる。
【００２２】
本発明者は、従来方式と本発明方式とによる画像符号化をシミュレートして、図６に示すような符号化低減率と、図７に示すような符号化後のＰＳＮＲを得た。実験には、４種（Ａ，Ｂ，Ｃ，およびＤ）の画像を用い、従来手法としては、Giovambattista  Pulciniのフラクタル符号化アルゴリズム（http://www.verrando.com/~verrando/pulcini/gp-ifs.html参照）を用いた。また、本発明方法としては、前記探索距離を７とし、２２５のドメインブロックから最適なドメインブロックを探索させた。
【００２３】
図６に示されているように、本発明方式によれば、最大で２４．６％の符号量を削減させることができた。しかし、図７に示されているように、符号量の低減による画質（ＰＳＮＲ）にはあまり影響がなく、逆に画質が向上する場合もあった（画像Ａ、Ｃ、Ｄ参照）。これは、従来方式では、高速化のために、ドメインブロック情報を予め分析し、レンジブロックの探索領域を事前に分割する手法（Yuval Fisher, "Fractal Image Compression" Springer-Verlag, New York,1995参照）を用いているため、画面中から最適なドメインブロックを探索できない可能性があるからであり、それよりは本発明方式のようにレンジブロックの近傍を全探索することにより適当なドメインブロックを指定する方が良いためと考えられる。
【図面の簡単な説明】
【００２４】
【図１】本発明の一実施形態の概略の構成を示すブロック図である。
【図２】原画像から得られるレンジブロックとドメインブロックの説明図である。
【図３】ドメインブロックの探索範囲の説明図である。
【図４】本実施形態によるフラクタル画像圧縮のデータ構造を示す図である。
【図５】本実施形態の動作を説明するフローチャートである。
【図６】本発明方式の従来方式に対する符号化低減率を示す図である。
【図７】本発明方式の従来方式に対する符号化後のＰＳＮＲを示す図である。
【図８】従来方式によるフラクタル画像圧縮のデータ構造を示す図である。
【符号の説明】
【００２５】
１・・・画像分割・抽出部、２・・・シェード／エッジブロック判定部、３・・・最適ドメインブロック決定部、４・・・探索距離指定部、５・・・レンジブロックデータ作成部、１０・・・原画像。
【図１】
2006067300.tif 000003
【図２】
2006067300.tif 000004
【図３】
2006067300.tif 000005
【図４】
2006067300.tif 000006
【図５】
2006067300.tif 000007
【図６】
2006067300.tif 000008
【図７】
2006067300.tif 000009
【図８】
2006067300.tif 000010