(57)【要約】【課題】適応的空間充填走査による画像符号化において、符号化走査情報の符号量を削減し、全体的な画像符号化効率を向上させることが可能な画像符号化技術を提供する。【解決手段】原画像を画素ブロック分割し、各画素ブロックにつき画素値の代表値を算出し、各画素ブロックからなる節点と各節点を連結する辺からなる重み付き連結グラフを生成し、各辺につき節点の代表値の差の大きさを割り当てる。各辺について、辺の重みが閾値以下の場合、その辺が基準木の辺と一致すれば重みを最小値に修正し、一致しないときは最大値に修正する。この重み付き連結グラフに基づき、すべての画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成し、最小全域木と基準木との差分情報を符号化する。また最小全域木に基づき生成される走査線に沿って走査して得られる１次元画像データを符号化する。【選択図】        図１
2005184710.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割された原画像について、原画像の特徴に従って各画素間の走査を行う適応的空間充填走査装置であって、
すべての画素ブロックからなる節点と、各画素ブロックを縦横に接続する辺とから構成されるグラフであって、各辺の両端の画素ブロック内にある画素の画素値の代表値の差の大きさを当該辺の重みとする重み付き連結グラフを生成するグラフ生成手段と、
前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正する重み修正手段と、
前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成する最小全域木生成手段と、
前記最小全域木に基づいて総ての画素を走査する走査線を生成する走査線生成手段と、
を備えたことを特徴とする適応的空間充填走査装置。
【請求項２】
原画像を、少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割するブロック分割手段と、
前記各画素ブロックのそれぞれについて、当該画素ブロック内にある画素の画素値の代表値を算出する代表値演算手段と、
各画素ブロックからなる節点の集合と、各節点を縦及び横方向に連結する辺の集合とからなる重み付き連結グラフを生成するとともに、その各辺について当該辺の両端節点の代表値を取得して、両者の差の大きさを当該辺の重みに割り当てるグラフ生成手段と、
前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正する重み修正手段と、
前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成する最小全域木生成手段と、
前記最小全域木と前記基準木との差分である差分走査情報を生成する差分走査情報生成手段と、
前記差分走査情報を符号化する走査情報符号化手段と、
前記最小全域木に基づいて総ての画素を走査する走査線を生成する走査線生成手段と、
前記走査線に沿って走査して得られる１次元画像データを符号化する画像データ符号化手段と、
を備えたことを特徴とする画像符号化装置。
【請求項３】
前記差分走査情報生成手段は、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との２値差分画像である縦方向差分画像と、前記最小全域木の横方向の枝と前記基準木の横方向の枝との２値差分画像である横方向差分画像とからなる差分走査情報を生成し、
前記走査情報符号化手段は、前記縦方向差分画像及び前記横方向差分画像のそれぞれをランレングス符号化方法により符号化することを特徴とする請求項２記載の画像符号化装置。
【請求項４】
前記差分走査情報生成手段は、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との差分値からなるビットと、前記最小全域木の横方向の枝と前記基準木の横方向の枝との差分値からなるビットとの２ビットの差分画像からなる差分走査情報を生成し、
前記走査情報符号化手段は、前記差分画像を算術符号化方法又はランレングス・ハフマン符号化方法により符号化することを特徴とする請求項２記載の画像符号化装置。
【請求項５】
少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割された原画像について、原画像の特徴に従って各画素間の走査を行う適応的空間充填走査方法であって、
すべての画素ブロックからなる節点と、各画素ブロックを縦横に接続する辺とから構成されるグラフであって、各辺の両端の画素ブロック内にある画素の画素値の代表値の差の大きさを当該辺の重みとする重み付き連結グラフを生成するステップと、
前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正するステップと、
前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成するステップと、
前記最小全域木に基づいて総ての画素を走査する走査線を生成するステップと、
を備えたことを特徴とする適応的空間充填走査方法。
【請求項６】
原画像を、少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割する第１ステップ、
前記各画素ブロックのそれぞれについて、当該画素ブロック内にある画素の画素値の代表値を算出する第２ステップ、
各画素ブロックからなる節点の集合と、各節点を縦及び横方向に連結する辺の集合とからなる重み付き連結グラフを生成するとともに、その各辺について当該辺の両端節点の代表値を取得して、両者の差の大きさを当該辺の重みに割り当てる第３ステップ、
前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正する第４ステップ、
前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成する第５ステップ、
前記最小全域木と前記基準木との差分である差分走査情報を生成する第６ステップ、
前記差分走査情報を符号化する第７ステップ、
前記最小全域木に基づいて総ての画素を走査する走査線を生成する第８ステップ、
及び、前記走査線に沿って走査して得られる１次元画像データを符号化する第９ステップ、
を有することを特徴とする画像符号化方法。
【請求項７】
前記第６ステップにおいて、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との２値差分画像である縦方向差分画像と、前記最小全域木の横方向の枝と前記基準木の横方向の枝との２値差分画像である横方向差分画像とからなる差分走査情報を生成し、
前記第７ステップにおいて、前記縦方向差分画像及び前記横方向差分画像のそれぞれをランレングス符号化方法により符号化することを特徴とする請求項６記載の画像符号化方法。
【請求項８】
前記第６ステップにおいて、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との差分値からなるビットと、前記最小全域木の横方向の枝と前記基準木の横方向の枝との差分値からなるビットとの２ビットの差分画像からなる差分走査情報を生成し、
前記第７ステップにおいて、前記差分画像を算術符号化方法又はランレングス・ハフマン符号化方法により符号化することを特徴とする請求項６記載の画像符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの特徴に適応して画素間の走査を行うことにより画像データを符号化する画像符号化技術に関する。
【背景技術】
【０００２】
従来、画像符号化技術として、適応的空間充填走査を用いた技術が公知である（非特許文献１，２参照）。適応的空間充填走査とは、符号化対象となる原画像の特徴に適応して空間充填曲線を生成し、この空間充填曲線に沿って走査を行うことをいう。適応的空間充填走査による画像符号化技術とは、適応的空間充填走査により原画像を１次元画像データに変換しこれを符号化するとともに、走査経路情報についても符号化を行うことで、原画像の符号化を行う技術をいう。以下、特許文献１，２に記載の適応的空間充填走査による画像符号化技術について概説する。
【０００３】
図１４は適応的空間充填走査による画像符号化方法の基本的な流れを表すフローチャートである。まず、２次元の原画像に対して適応空間充填走査が行われる。この走査により、１次元画像データが得られる。１次元画像データは、後述の区分線型近似により不可逆符号化を行った後に、エントロピ符号化により符号化画像情報とされる。一方、適応空間充填走査における走査径路の情報（走査情報）は、別個に符号化され、符号化走査情報とされる。
【０００４】
（１）適応的空間充填走査
原画像を（数１）のような偶数個の画素からなる２次元配列で表す。ここで、ai,jは原画像を構成する画素の画素値を表す。画素値とは、画素の輝度を表す値であり、白黒画像の場合には輝度値、ＲＧＢ画像の場合には、各色の輝度値等である。
【０００５】
【数１】
2005184710.tif 000003
【０００６】
次に、上記の原画像を４×４画素の画素ブロックに分割する。画素ブロックの集合をBで表すと、集合Bは（数２）により表される。
【０００７】
【数２】
2005184710.tif 000004
【０００８】
これら各画素ブロックbp,qを節点（vertex）とするグラフを考える。画素ブロックbp,qと画素ブロックbp+1,qとを連結する辺（edge）を縦方向の辺といい、e(v)p,qと記す。画素ブロックbp,qと画素ブロックbp,q+1とを連結する辺を横方向の辺といい、e(h)p,qと記す。縦方向の辺の全集合をE(v)={e(v)p,q | p=1,…,M-1, q=1,…,N}、横方向の辺の全集合をE(h)={e(h)p,q | p=1,…,M, q=1,…,N-1}と記す。また、辺の全集合をE=E(v)∪E(h)と記す。
【０００９】
連結グラフG=(B,E)を考える。「連結グラフ」とは、そのグラフに属する総ての節点が辺により連結されたグラフをいう。この連結グラフGの各節点bp,qの重みw(bp,q)を（数３）により定義する。
【００１０】
【数３】
2005184710.tif 000005
【００１１】
また、各枝e(v)p,q，e(h)p,qについて、重みw(e(v)p,q)，w(e(h)p,q)を（数４）のように定義する。
【００１２】
【数４】
2005184710.tif 000006
【００１３】
上記のように重みが定義された連結グラフGを「重み付き連結グラフ」という。あるグラフのすべての節点を包含する部分グラフを「全域部分グラフ」という。また、閉路を含まないグラフを「林」といい、連結な林を「木」という。あるグラフの全域部分グラフで木であるものを「全域木」（spanning tree）という。また、重み付き連結グラフに属する全域木の中で最小の重みを持つものを「最小全域木（minimum spanning tree）」という。
【００１４】
重み付き連結グラフGの全域部分グラフである全域木Tの重みは、（数５）により定義される。最小全域木Tminは、全域木Tのうち、重みw(T)が最小となるものである。
【００１５】
【数５】
2005184710.tif 000007
【００１６】
最小全域木Tminを求めるには、いくつかのアルゴリズムが知られている。ここで対象とする重み付き連結グラフGは、各節点から出る辺の数が最大で４であるので比較的に疎らである。従って、クラスカル（Kruskal）のアルゴリズム（非特許文献３参照）を用いて最小全域木Tminを求めるのがよい。
【００１７】
図１５は適応的空間充填曲線を生成する過程を説明する図である。４×４画素ブロックの集合Bと辺Eの集合からなる重み付き連結グラフGから生成される最小全域木Tminが図１５（ａ）のグラフであるとする。ここで、最小全域木Tminの辺を原画像A上にある迷路の壁とみなす。そして、こんどは原画像Aを２×２画素の画素ブロックに分割する。任意の２×２画素の画素ブロックを始点とする。この始点から、壁を何れか一方の手で触りながら、隣接する２×２画素の画素ブロックへと順次移動していく。このようにして、すべての２×２画素の画素ブロックを辿ると、この移動によって得られる軌跡は、すべての２×２画素の画素ブロックを辿る空間充填曲線となる（図１５（ｂ）参照）。この空間充填曲線を「ブロック走査線」と呼ぶこととする。
【００１８】
最後に、上記ブロック走査線に沿って、２×２画素の画素ブロックを辿りながら、それぞれの２×２画素の画素ブロックについては、図１６に示す走査パターンに沿って走査する。このとき、ブロック走査線に沿った２×２画素の画素ブロック内の走査パターンは、終端の画素ブロックを除き、図１６の走査パターンの何れか一つに一意的に決まる。この結果、すべての画素を辿る空間充填曲線が得られる（図１５（ｃ）参照）。この空間充填曲線を「画素走査線」又は単に「走査線」と呼ぶこととする。
【００１９】
この走査線は走査情報として符号化される。非特許文献１，２では、走査情報の符号化にはDiscontinuity Index Map（DIM）を用いた符号化方法が用いられている。なお、これについては本発明と直接関係しないので、説明は省略する。
【００２０】
（２）１次元画像データの符号化
次に、１次元画像データの符号化について説明する。上述のように走査線が生成されると、得られた走査線に沿って、原画像A内のすべての画素を走査し、１次元画像データを生成する。生成された１次元画像データは、区分線型近似処理により非可逆的に符号化される。
【００２１】
図１７は区分線型近似処理を説明する図である。図１７（ａ）は上記走査によって得られた１次元画像データを表している。横軸は走査順番であり、縦軸は各画素の画素値を表している。まず、この１次元画像データを、一定の長さFSLの小区間に分割する。分割された各小区間に対して、区分線型近似処理を施す。図１７（ｂ）は区分線型近似処理において行われる２分割処理の様子を表している。区間Ｌ内の１次元画像データの長さをNとする。区間Ｌ内の画素の画素値の集合を{xi | i=1,…,N}と記す。２分割処理では、区間Ｌを、２つの区間Ｌ１，Ｌ２に分割する。区間Ｌ１に属する画素数をN1、区間Ｌ２の画素数をN-N1とする。区間Ｌ１，Ｌ２に属する画素の画素値の平均は、それぞれ（数６），（数７）で表される。
【００２２】
【数６】
2005184710.tif 000008
【００２３】
【数７】
2005184710.tif 000009
【００２４】
区間Ｌ１，Ｌ２の累積２乗誤差は、それぞれ、（数８），（数９）で表される。
【００２５】
【数８】
2005184710.tif 000010
【００２６】
【数９】
2005184710.tif 000011
【００２７】
N1（1<N1<N）は、累積２乗誤差の和Eval(N1)=e1(N1)+e2(N1)が最小となる点とする。このようにして１回の２分割処理により区間Ｌは２つの区間Ｌ１，Ｌ２に分割される。区分線型近似処理では、この２分割処理を繰り返し行い、最終的には、すべての区間において累積２乗誤差の和Eval(N1)の値があらかじめ設定された閾値TH1以下となるまで繰り返す。
【００２８】
区分線型近似処理が終了した後、ある小区間はS個の区間に分割されたとする。分割区間Li（i=1,…,S）内の画素数をliとし、画素の平均画素値をciとする。然らば、分割区間LiはLi=(ci, li)で表される。また、長さFSLの小区間は、集合{(ci, li) | i=1,…,S}により表される。
【００２９】
この区分線型近似処理では、１次元画像データを予め長さFSLの小区間に分割している。そのため、隣り合う２つの区間Li=(ci, li)，Li+1=(ci+1, li+1)の境界部分で、（ａ）両区間内の画素の平均画素値が等しいにもかかわらず分割されている場合、（ｂ）両区間内の画素の平均画素値の差が小さく、区間長が短い区間が生じる場合、のような冗長性が生じている。そこで、かかる冗長性をなくすため、隣り合う２つの区間Li，Li+1に対して、
（ａ）ci=ci+1のときは、区間Li，Li+1を１つの区間Li'=(ci, li+li+1)とする。
（ｂ）(|ci-ci+1|<TH2)∧[(li<TH3)∨(li+1<TH3)]が真のとき区間Li，Li+1を１つの区間Li'=(ci', li+li+1)とする。
という区間併合処理を行う。ここで、TH2，TH3は、それぞれ、平均画素値の差の閾値、区間長の閾値である。また、併合後の区間Li'の平均画素値は、（数１０）により決定する。
【００３０】
【数１０】
2005184710.tif 000012
【００３１】
以上のようにして平均画素値ciと区間長liとの組の集合{(ci,li)}として不可逆的に符号化された１次元画像データを、更にエントロピ符号化方法により符号化する。非特許文献１，２においては、平均画素値ciの符号化には、ハフマン符号とＴＣＱ（Trellis Coded Quantization）（非特許文献４参照）を使用し、区間長の符号化にはワイル（Wyle）符号（非特許文献５参照）を使用している。
【非特許文献１】Seiichiro Kamata, Yusuke Hayashi, "Region-based scanning for image compression", Proc. of IEEE Int. Conf. on Image Processing, Vancouver, Vol.II, pp.895-898(2000).
【非特許文献２】板東幸浩，鎌田清一郎，「適応的空間充填走査に基づく非可逆画像圧縮法」，電子情報通信学会，信学技報，IE99-156， pp.55-62, 2000.
【非特許文献３】J.B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, Volume 7, pp. 48-50, 1956.
【非特許文献４】Michael W. Marcellin and Thomas R. Fischer, "Trellis coded quantization of memoryless and Gauss-Markov sources," IEEE Transactions on Communications, Vol.38, No.1, pp. 82-93, January 1990.
【非特許文献５】H. Wyle, T. Erb, and R. Barow, "Reduced time facsimile transmission by digital coding," IRE Trans. on Commun. Syst., vol. CS-9, no. 3, pp. 215-222, Sept. 1961.
【発明の開示】
【発明が解決しようとする課題】
【００３２】
上記従来の画像符号化方法によれば、画像の特徴に適合した適応的空間充填走査を行うことから、１次元画像データは針状の画素値のとびが少なく、隣接画素間の相関が比較的大きいデータとなる。従って、これを符号化した場合には、高い符号化効率が得られる。
【００３３】
しかしながら、画像に対して適応的空間充填走査による符号化を行った場合、これを復号するためには、１次元画像データに関する情報のほかに走査情報が必要となる。従って、符号化後の全体の符号量は符号化１次元画像データの符号量に符号化走査情報の符号量を加えたものとなる。上記従来の画像符号化方法では、この符号化走査情報の占める割合が大きいため、全体的な符号化効率としてはあまり高い効率が得られないという問題がある。
【００３４】
そこで、本発明の目的は、適応的空間充填走査による画像符号化において、符号化走査情報の符号量を削減し、全体的な画像符号化効率を向上させることが可能な画像符号化技術を提供することにある。
【課題を解決するための手段】
【００３５】
本発明に係る適応的空間充填走査装置は、少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割された原画像について、原画像の特徴に従って各画素間の走査を行う適応的空間充填走査装置であって、すべての画素ブロックからなる節点と、各画素ブロックを縦横に接続する辺とから構成されるグラフであって、各辺の両端の画素ブロック内にある画素の画素値の代表値の差の大きさを当該辺の重みとする重み付き連結グラフを生成するグラフ生成手段と、前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正する重み修正手段と、前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成する最小全域木生成手段と、前記最小全域木に基づいて総ての画素を走査する走査線を生成する走査線生成手段と、を備えたことを特徴とする。
【００３６】
本発明に係る画像符号化装置は、原画像を、少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割するブロック分割手段と、前記各画素ブロックのそれぞれについて、当該画素ブロック内にある画素の画素値の代表値を算出する代表値演算手段と、各画素ブロックからなる節点の集合と、各節点を縦及び横方向に連結する辺の集合とからなる重み付き連結グラフを生成するとともに、その各辺について当該辺の両端節点の代表値を取得して、両者の差の大きさを当該辺の重みに割り当てるグラフ生成手段と、前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正する重み修正手段と、前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成する最小全域木生成手段と、前記最小全域木と前記基準木との差分である差分走査情報を生成する差分走査情報生成手段と、前記差分走査情報を符号化する走査情報符号化手段と、前記最小全域木に基づいて総ての画素を走査する走査線を生成する走査線生成手段と、前記走査線に沿って走査して得られる１次元画像データを符号化する画像データ符号化手段と、を備えたことを特徴とする。
【００３７】
グラフ生成手段により生成される重み付き連結グラフの各辺の重みは、原画像の画素値の変化が大きい部分は大きな値となり、原画像の画素値の変化が小さい部分は小さな値となる。すなわち、重みが小さい辺が属する原画像の画素値の変化は小さいと判断される。そして、或る重みが小さい辺について、その辺に隣接する辺の重みも小さい場合には、その辺の周囲の原画像は、画素値の変化が小さい平坦領域であると判断される。
【００３８】
そこで、或る辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、重み修正手段は、当該辺が基準木の辺と一致するときにはその辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときにはその辺の重みを所定の大きい値に修正する。これにより、原画像の平坦領域に属する辺については、基準木に一致する辺は小さい重みに設定され、基準木に一致しない辺は大きな重みに設定される。
【００３９】
このように辺の重みの修正がされた重み付き連結グラフに基づいて、最小全域木生成手段は、すべての画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成する。このようにして生成される最小全域木の辺は、原画像の平坦領域においては基準木に一致するようになる。差分走査情報生成手段は、最小全域木と基準木との差分である差分走査情報を生成する。尚、ここでいう差分とは、ブール演算による差分をいう。すなわち、最小全域木の辺と基準木の辺とが一致する場合は０、一致しない場合は１となる。従って、生成される差分走査情報は２値データである。
【００４０】
差分走査情報は、原画像の平坦領域においては０となり、それ以外の領域においてのみ値を有する。従って、平坦領域に属する走査情報の情報量を大幅に削減することができるため、走査情報符号化手段は、高い符号化効率で差分走査情報を符号化することが可能となる。
【００４１】
また、走査線生成手段は、最小全域木生成手段により生成される全域木に基づいて総ての画素を走査する走査線を生成する。この走査線は、原画像の画素値の変化量の小さい領域を充填するように走査する適応的空間充填走査径路となる。従って、この走査線に沿って走査して得られる１次元画像データは、隣接画素間の相関が大きいデータとなる。そのため、画像データ符号化手段は１次元画像データを符号化した場合に、高い符号化効率で符号化することが可能となる。
【００４２】
結果として、原画像は符号化差分走査情報と符号化１次元画像データに符号化され、全体として、高い符号化効率で原画像を符号化することが可能となる。
【００４３】
ここで、代表値演算手段が算出する「代表値」とは、すべての対象画素の画素値を代表する値をいう。「代表値」としては、総和値、平均値、最頻値、中位値等を用いることができるが、演算の簡便性から総和値を使用するのが好ましい。「代表値の差の大きさ」とは、例えば、差の絶対値や差の二乗値等をいう。演算の簡便性からは、差の絶対値を使用することが好ましい。
【００４４】
重み修正手段が辺の重みの修正をする際の判定に使用する「所定の閾値」は、原画像の平坦性を判定するのに適当な値に設定され、通常は実験的に決定される。
【００４５】
「基準木」とは、全域木であってあらかじめ基準として与えられたものをいう。基準木としては、どのようなものを使用してもよい。例えば、各種空間充填曲線により各節点を分岐のない辺で連結した木を使用することができる。特に、走査線生成手段により生成された走査線ができるだけ画素ブロックごとに走査するようにするには、ヒルベルト曲線を使用するのが好ましい。
【００４６】
重み修正手段が辺の重みを修正する際に使用する「所定の小さい値」としては、重み付き連結グラフに含まれるすべての辺の重みのうちで最小のもの以下の値が用いられる。この場合、簡単のために「所定の小さい値」として０を用いてもよい。また、「所定の大きい値」とは、重み付き連結グラフに含まれるすべての辺の重みのうちで最大のもの以上の値が用いられる。
【００４７】
最小全域木生成手段による最小全域木の生成方法としては、KruskalのアルゴリズムやPrimのアルゴリズム等を使用することができる。特に、最小全域木を生成するもととなる重み付き連結グラフは、各節点から出る辺の数が最大で４であるので比較的に疎らであるため、クラスカル（Kruskal）のアルゴリズム用いることが好ましい。
【００４８】
走査線生成手段が走査線を生成する方法としては、上記「背景技術」の欄で説明した方法と同様の方法を用いることができる。すなわち、まず、最小全域木を原画像上にある迷路の壁とみなす。そして、原画像上の任意の２ｍ-1×２ｎ-1画素の画素ブロックを始点とし、壁を何れか一方の手で触りながら隣接する２ｍ-1×２ｎ-1画素の画素ブロックへと移動する。このようにして、最小全域木に沿ってすべての２ｍ-1×２ｎ-1画素の画素ブロックを辿れば、全画素ブロックを辿ることができる。各２ｍ-1×２ｎ-1画素の画素ブロックが２以上の画素を含む場合には、更に、当該画素ブロック内を空間充填曲線により辿るように走査すればよい。
【００４９】
画像データ符号化手段が１次元画像データを符号化する方法としては、各種公知の可逆符号化又は非可逆符号化の方法を使用することができる。非可逆符号化の方法としては、上記「背景技術」の欄で説明した区分線型近似法が特に適している。上記方法で得られる１次元画像データは、隣接画素間の相関が大きいデータとなるからである。
【００５０】
尚、差分走査情報から走査情報を復号する際には、復号器において符号化の際に使用した基準木と同じ基準木を用意しておいて、この基準木と差分走査情報を加えることにより簡単にもとの走査情報を復元することができる。
【００５１】
また、本発明において、前記差分走査情報生成手段は、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との２値差分画像である縦方向差分画像と、前記最小全域木の横方向の枝と前記基準木の横方向の枝との２値差分画像である横方向差分画像とからなる差分走査情報を生成し、前記走査情報符号化手段は、前記縦方向差分画像及び前記横方向差分画像のそれぞれをランレングス符号化方法により符号化する構成とすることができる。
【００５２】
この構成によれば、前記縦方向差分画像及び前記横方向差分画像の画素値０、もしくは1が連続して現れる画素の個数が統計的に偏りのあるデータとなるため、この画素の個数をハフマン符号化することにより、効率的な情報圧縮を達成することができる。
【００５３】
また、本発明において、前記差分走査情報生成手段は、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との差分値からなるビットと、前記最小全域木の横方向の枝と前記基準木の横方向の枝との差分値からなるビットとの２ビットの差分画像からなる差分走査情報を生成し、前記走査情報符号化手段は、前記差分画像を算術符号化方法又はランレングス・ハフマン符号化方法により符号化する構成とすることができる。
【００５４】
この構成によれば、前記縦方向差分画像及び前記横方向差分画像の画素値0が連続して現れる画素の個数と、その直後に現れる0以外の画素値の組み合わせが統計的に偏りのあるデータとなるため、この画素の個数と0以外の画素値の組み合わせをハフマン符号化することにより、効率的な情報圧縮を達成することができる。
【００５５】
本発明に係る適応的空間充填走査方法は、少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割された原画像について、原画像の特徴に従って各画素間の走査を行う適応的空間充填走査方法であって、すべての画素ブロックからなる節点と、各画素ブロックを縦横に接続する辺とから構成されるグラフであって、各辺の両端の画素ブロック内にある画素の画素値の代表値の差の大きさを当該辺の重みとする重み付き連結グラフを生成するステップと、前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正するステップと、前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成するステップと、前記最小全域木に基づいて総ての画素を走査する走査線を生成するステップと、
を備えたことを特徴とする。
【００５６】
本発明に係る画像符号化方法は、原画像を、少なくとも２ｍ×２ｎ画素（ｍ，ｎは１以上の整数）の大きさを有する方形の画素ブロックの集合に分割する第１ステップ、前記各画素ブロックのそれぞれについて、当該画素ブロック内にある画素の画素値の代表値を算出する第２ステップ、各画素ブロックからなる節点の集合と、各節点を縦及び横方向に連結する辺の集合とからなる重み付き連結グラフを生成するとともに、その各辺について当該辺の両端節点の代表値を取得して、両者の差の大きさを当該辺の重みに割り当てる第３ステップ、前記重み付き連結グラフの各辺について、当該辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の場合、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正する第４ステップ、前記重み付き連結グラフに基づいて、すべての前記画素ブロックを節点とし全辺の重みの和が最小であるような最小全域木を生成する第５ステップ、前記最小全域木と前記基準木との差分である差分走査情報を生成する第６ステップ、前記差分走査情報を符号化する第７ステップ、前記最小全域木に基づいて総ての画素を走査する走査線を生成する第８ステップ、及び、前記走査線に沿って走査して得られる１次元画像データを符号化する第９ステップ、を有することを特徴とする。
【００５７】
また、本発明では、前記第６ステップにおいて、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との２値差分画像である縦方向差分画像と、前記最小全域木の横方向の枝と前記基準木の横方向の枝との２値差分画像である横方向差分画像とからなる差分走査情報を生成し、前記第７ステップにおいて、前記縦方向差分画像及び前記横方向差分画像のそれぞれをランレングス符号化方法により符号化するようにしてもよい。
【００５８】
また、本発明では、前記第６ステップにおいて、前記最小全域木の縦方向の枝と前記基準木の縦方向の枝との差分値からなるビットと、前記最小全域木の横方向の枝と前記基準木の横方向の枝との差分値からなるビットとの２ビットの差分画像からなる差分走査情報を生成し、前記第７ステップにおいて、前記差分画像を算術符号化方法又はランレングス・ハフマン符号化方法により符号化するようにしてもよい。
【発明の効果】
【００５９】
以上のように、本発明によれば、走査線を決定するための全域木を生成する前処理として、重み付き連結グラフの辺のうち、辺の重み及び当該辺に隣接する辺の重みが所定の閾値以下の辺について、当該辺が基準木の辺と一致するときには、その辺の重みを所定の小さい値に修正し、当該辺が基準木の辺と一致しないときには、その辺の重みを所定の大きい値に修正することで、平坦領域における辺の重みの修正を行い、平坦領域における最小全域木の辺は基準木の辺と一致するようにした。そして、最小全域木と基準木との差分をとった差分走査情報を生成し、これを符号化して符号化走査情報とした。これにより、走査情報のうち、平坦領域に属する走査情報の情報量を大幅に削減することができ、符号化走査情報の符号量を大幅に削減することが可能となる。その結果、適応的空間充填走査による画像符号化において、全体的な画像符号化効率を向上させることが可能となる。
【発明を実施するための最良の形態】
【００６０】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００６１】
図１は本発明の実施例１に係る画像符号化装置の構成を表す図である。尚、本発明に係る適応的空間充填走査装置の実施例については、この画像符号化装置の構成の一部として含まれるため、併せて説明することとする。画像符号化装置１は、フレーム・バッファ２、ブロック分割手段３、代表値演算手段４、節点記憶手段５、グラフ生成手段６、辺データ記憶手段７、重み修正手段８、基準木記憶手段９、最小全域木生成手段１０、最小全域木記憶手段１１、差分走査情報生成手段１２、走査情報符号化手段１３、符号化走査情報記憶手段１４、走査線生成手段１５、画像データ符号化手段１６、及び符号化画像データ記憶手段１７を備えた構成からなる。
【００６２】
フレーム・バッファ２は、画像入力手段１８から入力される原画像A={ai,j | i=1,…,2mM, j=1,…,2nN}を一時的に記憶するバッファである。ここで、ai,jは画素値、m，nは１以上の整数、M，Nは正整数、M×Nは画像サイズである。画像入力手段１８は、外部記憶装置や通信インタフェース等により構成される。
【００６３】
ブロック分割手段３は、原画像Aを、２ｍ×２ｎ画素の大きさを有する方形の画素ブロックの集合B={bp,q | p=1,…,M, q=1,…,N}に分割する。代表値演算手段４は、各画素ブロックbp,q（p=1,…,M, q=1,…,N）のそれぞれについて、当該画素ブロックbp,q内にある画素の平均画素値w(bp,q)を算出し、節点記憶手段５に格納する。
【００６４】
グラフ生成手段６は、各画素ブロックからなる節点の集合Bと、各節点bp,q（p=1,…,M, q=1,…,N）を縦及び横方向に連結する辺の集合E=E(v)∪E(h)とからなる重み付き連結グラフG=(B,E)を生成する。ここで、E(v)={e(v)p,q | p=1,…,M-1, q=1,…,N}は縦方向辺の集合、E(h)={e(h)p,q | p=1,…,M, q=1,…,N-1}は横方向辺の集合である。また、グラフ生成手段６は、各辺e(v)p,q，e(h)p,qについて当該辺の両端節点の代表値の差を取得して、両者の絶対値|w(bp+1,q)-w(bp,q)|，|w(bp,q+1)-w(bp,q)|を当該辺の重みw(e(v)p,q)，w(e(h)p,q)に割り当てる。そして、グラフ生成手段６は、辺の重みw(e(v)p,q)，w(e(h)p,q)を辺データ記憶手段７に格納する。
【００６５】
基準木記憶手段９は、走査情報を符号化する際に使用する基準木T(0)を格納する。ここで、基準木T(0)は、重み付き連結グラフGのすべての節点を節点の集合として有する全域木である。基準木記憶手段９には、基準木T(0)の辺の有無を表すデータの集合F=F(v)∪F(h)が格納されている。ここで、F(v)={f(v)p,q | p=1,…,M-1, q=1,…,N}は基準木T(0)の縦方向辺の有無を表すデータの集合である。F(h)={f(h)p,q | p=1,…,M, q=1,…,N-1}は基準木T(0)の横方向辺の有無を表すデータの集合である。f(v)p,q=1（又はf(h)p,q=1）のときには基準木T(0)の辺が存在することを表し、f(v)p,q=0（又はf(h)p,q=0）のときにはそのような辺が存在しないことを表す。
【００６６】
重み修正手段８は、重み付き連結グラフGの各辺e(v)p,q，e(h)p,qについて、辺データ記憶手段７に格納された辺の重みw(e(v)p,q)，w(e(h)p,q)の修正を行う。すなわち、ある辺e(v)p,q（又はe(h)p,q）の重みw(e(v)p,q)（又はw(e(h)p,q)）が所定の閾値Γ(v)（又はΓ(h)）以下であり且つその辺e(v)p,q（又はe(h)p,q）に隣接する４つの辺の重みがすべて所定の閾値Γ(v)（又はΓ(h)）以下の場合、その辺e(v)p,q（又はe(h)p,q）に対応する基準木T(0)の辺があるときには、その辺の重みw(e(v)p,q)（又はw(e(h)p,q)）を所定の小さい値wminに修正する。また、当該辺e(v)p,q（又はe(h)p,q）に対応する基準木T(0)の辺がないときには、その辺の重みw(e(v)p,q)（又はw(e(h)p,q)）を所定の大きい値wmaxに修正する。そして、修正した辺の重みw(e(v)p,q)（又はw(e(h)p,q)）を再び辺データ記憶手段７に格納する。
【００６７】
最小全域木生成手段１０は、辺データ記憶手段７に格納された重み付き連結グラフGの辺の重みデータに基づいて、すべての画素ブロックbp,q（p=1,…,M, q=1,…,N）を節点とし全辺の重みの和が最小であるような最小全域木Tminを生成する。そして、最小全域木生成手段１０は、生成した最小全域木Tminを最小全域木記憶手段１１に格納する。
【００６８】
差分走査情報生成手段１２は、最小全域木記憶手段１１に格納された最小全域木Tminと、基準木記憶手段９に格納された基準木T(0)との差分である差分走査情報を生成する。走査情報符号化手段１３は、差分走査情報生成手段１２が生成する差分走査情報を符号化し、符号化走査情報記憶手段１４に格納する。
【００６９】
走査線生成手段１５は、最小全域木記憶手段１１に格納された最小全域木Tminに基づいて、原画像A内の総ての画素を走査する走査線を生成する。画像データ符号化手段１６は、走査線生成手段１５が生成する走査線に沿って原画像Aを走査して得られる１次元画像データを符号化し、符号化画像データ記憶手段１７に格納する。
【００７０】
符号化画像データ記憶手段１７に格納された符号化画像データ、及び符号化走査情報記憶手段１４に格納された符号化走査情報は、符号化画像出力手段１９により、外部に出力される。尚、符号化画像出力手段１９は、外部記憶装置や通信インタフェースなどで構成される。
【００７１】
以上のように構成された本実施例に係る画像符号化装置について、以下その動作説明をする。
【００７２】
図２は本発明の実施例１に係る画像符号化方法の全体の流れを表すフローチャートである。まず、画像入力手段１８により原画像Aのデータが入力されると、原画像Aのデータはフレーム・バッファ２に格納される（Ｓ１）。そして、最初に適応的空間充填走査による走査情報の生成処理が行われる（Ｓ２）。この走査情報の生成処理において、上述の最小全域木Tminが生成される。
【００７３】
次に、差分走査情報生成手段１２により、差分走査情報の生成処理が行われる（Ｓ３）。この差分走査情報の生成処理において、生成された差分走査情報は、次の差分走査情報符号化処理（Ｓ４）において符号化され、符号化走査情報記憶手段１４に格納される。
【００７４】
一方、最小全域木Tminに基づき、走査線生成手段１５による走査線生成処理が行われる（Ｓ５）。この走査線生成処理により、原画像の全画素を適応的に走査する走査線が決定される。そして、画像データ符号化手段１６による、走査線に沿った原画像の走査及び符号化の処理（１次元画像データ符号化処理）が行われる（Ｓ６）。最後に、符号化画像出力手段１９が、符号化画像データと符号化走査情報とを出力し（Ｓ７）、原画像Aの画像符号化が終了する。
【００７５】
以上が全体的な処理の流れである。次に、それぞれのステップにおける処理について詳細に説明する。尚、上記各処理過程のうち、走査線生成処理（ステップＳ５）及び１次元画像データ符号化処理（Ｓ６）は、上述の背景技術において説明した方法と同様であるため、説明は省略する。
【００７６】
（１）走査情報の生成処理
図３は走査情報の生成処理の全体の流れを表すフローチャートである。まず、ブロック分割手段３は、フレーム・バッファ２に格納された原画像A={ai,j | i=1,…,2mM, j=1,…,2nN}を順次読み出しながら、画素ブロックB={bp,q | p=1,…,M, q=1,…,N}，bp,q={ai,j | i=2m(p-1)+i,…,2mp, j=2n(q-1)+i,…,2nq}（p=1,…,M, q=1,…,N）を生成する（Ｓ１０）。ここで、本実施例における各画素ブロックの大きさは２ｍ×２ｎとした。ｍ，ｎは１以上の整数である。以下では、説明の便宜上、ｍ＝ｎ＝４とする。
【００７７】
次に、代表値演算手段４は、それぞれの画素ブロックbp,qの重みw(bp,q)を算出し、節点記憶手段５に格納する（Ｓ１１）。ここで、画素ブロックbp,qの重みw(bp,q)は、画素ブロックbp,qにおける画素値の総和であり、（数１１）により算出される。
【００７８】
【数１１】
2005184710.tif 000013
【００７９】
次に、グラフ生成手段６は、各画素ブロックbp,qを節点とする縦方向辺E(v)={e(v)p,q | p=1,…,M-1, q=1,…,N}及び横方向辺E(h)={e(h)p,q | p=1,…,M, q=1,…,N-1}を生成する（Ｓ１２）。そして、グラフ生成手段６は、（数４）と同様の計算により、各辺の重みw(e(v)p,q)，w(e(h)p,q)の演算を行う（Ｓ１３）。算出された各辺の重みw(e(v)p,q)，w(e(h)p,q)は、辺データ記憶手段７に格納される。これにより、重み付き連結グラフG=(B,E)，E=E(v)∪E(h)が生成される。
【００８０】
次に、最小全域木Tminを生成する前処理として、重み修正手段８は、上記辺データ記憶手段７に格納された各辺の重みw(e(v)p,q)，w(e(h)p,q)の修正処理を行う（Ｓ１４）。この辺の重み修正処理については、次項で詳細に説明する。
【００８１】
最後に、最小全域木修正手段１０は、辺データ記憶手段７に格納された各辺の重みw(e(v)p,q)，w(e(h)p,q)に基づき、最小全域木Tminを生成しこれを最小全域木記憶手段１１に格納して（Ｓ１５）、走査情報の生成処理を終了する。
【００８２】
尚、最小全域木構成処理に関して簡単に補足説明をしておく。本実施例では、最小全域木構成処理に、クラスカルのアルゴリズムを使用する。図４は最小全域木構成処理の流れを表すアルゴリズムである。最小全域木Tminの節点の集合は、画素ブロックの集合Bである。また、最小全域木Tminの辺の集合をE'とする。また、節点の集合Bと辺の集合E'とで構成されるグラフをT'とする。まず、最小全域木生成手段１０は、集合E'を空集合φに初期化する（Ｓ２０）。具体的には、集合E'として、辺の有無を表す配列変数e'(v)p,q（p=1,…,M-1, q=1,…,N），e'(h)p,q（p=1,…,M, q=1,…,N-1）を用意し、すべてのe'(v)p,q,e'(h)p,qを０とする。ここで、e'(v)p,q=1(e'(h)p,q=1)は節点bp,qと節点bp+1,q（節点bp,qと節点bp,q+1）を連結する辺が存在することを表し、e'(v)p,q=0(e'(h)p,q=0)はそのような辺が存在しないことを表す。
【００８３】
次に、最小全域木生成手段１０は、辺データ記憶手段７に格納された各辺の重みw(e(v)p,q)，w(e(h)p,q)を参照して、重み付き連結グラフG=(B,E)の辺のうち、辺の集合E'に追加してもグラフT'=(B,E')に閉路を生じさせない辺e（∈E）の中で、辺の重みw(e)が最小の辺を探索し、これを辺e'とする（Ｓ２１）。尚、辺eは縦方向辺であっても横方向辺であってもよい。そして、辺e'を辺の集合E'に追加する（Ｓ２２）。すなわち、辺e'に対応する配列変数を１とする。
【００８４】
最後に、最小全域木生成手段１０は、集合E'の大きさ|E'|が集合Bの大きさ|B|=M×Nから１を減じた値よりも小さいか否かを判定する（Ｓ２３）。|E'|<|B|-1のときにはステップＳ２１に戻り、|E'|=|B|-1のときは、最小全域木構成処理を終了する。以上の処理が終了すると、最小全域木Tmin=T'が生成される。
【００８５】
（２）辺の重み修正処理
次に、上記ステップＳ１４における各辺の重み修正処理について詳細に説明する。各辺の重み修正処理においては、原画像の平坦領域に属する辺については、後に生成される最小全域木の辺が基準木の辺と一致するように、辺の重みの修正が行われる。図５〜図７は各辺の重み修正処理を表すフローチャートである。
【００８６】
重み修正手段８は、内部変数として、行番号を表す内部変数p,i、列番号を表す内部変数q,j、平坦領域か否かを判定するための変数k、重み変更フラグc(e(v)p,q)（p=1,…,M-1, q=1,…,N），c(e(h)p,q)（p=1,…,M, q=1,…,N-1）、縦方向辺の重み閾値Γ(v)、横方向辺の重み閾値Γ(h)、辺の最小重みwemin、及び辺の最大重みwemaxを有している。ここでは、wemin=0に設定されており、wemaxは変数w(e(v)p,q), w(e(h)p,q)のとり得る最大値（例えば、nビット変数であれば2n-1）に設定されているものとする。
【００８７】
まず、重み修正手段８は、行番号を表す内部変数pを１とし（Ｓ３０）、列番号を表す内部変数qを１とする（Ｓ３１）。
【００８８】
次に、重み修正手段８は、縦方向辺の重み変更フラグc(e(v)p,q)を０に設定する（Ｓ３２）。そして、重み修正手段８は、辺データ記憶手段７から辺の重みw(e(v)p,q)を読み出し、これを縦方向辺の重み閾値Γ(v)と比較する（Ｓ３３）。
【００８９】
ここで、縦方向辺が平坦領域に属するか否かの判定方法について補足説明する。図８は平坦領域の判定方法の説明図である。図８において、●は2m×2n画素の画素ブロックからなる節点を表す。図８（ａ）において、節点bp,qから出る縦方向辺e(v)p,q（図８（ａ）で太線で示された辺）が、原画像Aの平坦領域に属するか否かを判定する場合、まず、辺の重みw(e(v)p,q)と縦方向辺の重み閾値Γ(v)との比較を行う。w(e(v)p,q)≦Γ(v)であれば、縦方向辺e(v)p,qは平坦領域に属する可能性があると考えられる。但し、これだけでは平坦領域に属しているか否かを精度よく判定することができない。そこで、縦方向辺e(v)p,qに隣接する辺についても同様の判定を行う。縦方向辺e(v)p,qに隣接する辺は全部で６本あるが、本実施例ではこのうちの４本の横方向辺e(h)p,q，e(h)p,q-1，e(h)p+1,q，e(h)p+1,q-1（図８（ａ）の三重線で表した辺）により判定する。これらの辺の重みがすべて横方向辺の重み閾値Γ(h)以下の場合には、縦方向辺e(v)p,qは平坦領域に属すると判定される。尚、本発明においては判定に使用する隣接辺の選択は、これに限られるものではない。
【００９０】
図５に戻って、ステップＳ３３で、w(e(v)p,q)>Γ(v)の場合には、縦方向辺e(v)p,qは平坦領域には属さないものと判断されるので、c(e(v)p,q)=0のままとして次の辺に関する処理に移行すべくステップＳ４３に移行する。
【００９１】
一方、ステップＳ３３でw(e(v)p,q)≦Γ(v)の場合、重み修正手段８は、平坦領域か否かを判定するための変数kを０に初期化する（Ｓ３４）。そして、変数iを０，１の範囲で動かし、変数jを−１，０の範囲で動かして、それぞれの場合について、w(e(h)p+i,q+j)≦Γ(h)が否かを判定し、各場合についてw(e(h)p+i,q+j)≦Γ(h)の場合には変数kの値を１だけ増加させる（Ｓ３５〜Ｓ４０）。横方向辺e(h)p,q，e(h)p,q-1，e(h)p+1,q，e(h)p+1,q-1の重みがすべて横方向辺の重み閾値Γ(h)以下の場合にはk=4となり、それ以外はk<4となる。
【００９２】
次に、k=4の場合には（Ｓ４１）、辺e(v)p,qは平坦領域に属すると判定されるので、縦方向辺の重み変更フラグc(e(v)p,q)を１に設定する（Ｓ４２）。
【００９３】
以上の走査が終わると、変数qがNとなるまで変数qを1だけ増加させながら、ステップＳ３２〜Ｓ４２を繰り返す（Ｓ４３）。変数qについて１〜Nまで処理が終了すると、今度は変数pがM-1となるまで変数pを1だけ増加させながら、ステップＳ３１〜Ｓ４３を繰り返す（Ｓ４４）。
【００９４】
以上の処理により、すべての縦方向辺についての重み変更フラグの設定が終了する。次に、同様な処理を横方向辺についても行う（Ｓ５０〜６４）。横方向辺の処理は、縦方向辺の処理と同様であるため、図６の説明については省略する。
【００９５】
尚、横方向辺が平坦領域に属するか否かの判定方法についてだけ補足説明しておく。図８（ｂ）において、節点bp,qから出る横方向辺e(h)p,q（図８（ｂ）で太線で示された辺）が、原画像Aの平坦領域に属するか否かを判定する場合、まず、辺の重みw(e(h)p,q)と横方向辺の重み閾値Γ(h)との比較を行う。w(e(h)p,q)≦Γ(h)であれば、横方向辺e(h)p,qは平坦領域に属する可能性があると考えられる。但し、これだけでは平坦領域に属しているか否かを精度よく判定することができない。そこで、横方向辺e(h)p,qに隣接する辺についても同様の判定を行う。横方向辺e(h)p,qに隣接する辺は全部で６本あるが、本実施例ではこのうちの４本の縦方向辺e(v)p,q，e(v)p,q+1，e(v)p-1,q，e(v)p-1,q+1（図８（ｂ）の三重線で表した辺）により判定する。これらの辺の重みがすべて横方向辺の重み閾値Γ(v)以下の場合には、横方向辺e(h)p,qは平坦領域に属すると判定される。尚、本発明においては判定に使用する隣接辺の選択は、これに限られるものではない。
【００９６】
すべての縦方向辺及び横方向辺についての重み変更フラグの設定処理が終わると、次に、図７のステップＳ７１に移行する。
【００９７】
まず、ここで、基準木記憶手段９には、予め決められた基準木T(0)のデータF=F(v)∪F(h)，F(v)={f(v)p,q | p=1,…,M-1, q=1,…,N}，F(h)={f(h)p,q | p=1,…,M, q=1,…,N-1}が格納されている。基準木T(0)としては、全域木であればどのような木であってもよいが、符号化効率を高める観点からは、空間を縦横均質に走査するような木を使用することが好ましい。本実施例においては、一例として、図９に示すようなヒルベルト曲線からなる木（ヒルベルト・ツリー）を使用することとする。
【００９８】
重み修正手段８は、内部変数pを１からM-1、内部変数qを１からNまで動かしながら（Ｓ７１，Ｓ７２，Ｓ７７，Ｓ７８）、以下のステップＳ７３〜Ｓ７６の処理を行う。
【００９９】
まず、最小全域木生成手段１０は、縦方向辺についての重み変更フラグc(e(v)p,q)が１であるか否かを判定する（Ｓ７３）。c(e(v)p,q)＝０ならば、以下の処理は行わず、p又はqをインクリメントして（Ｓ７７，Ｓ７８）、次のp又はqに移行する。
【０１００】
ステップＳ７３において、c(e(v)p,q)＝１ならば、次に、重み修正手段８は、基準木記憶手段９より、辺e(v)p,qに対応する基準木T(0)の辺存在フラグf(v)p,qを読み出す。ここで、辺e(v)p,qに対応する基準木T(0)の辺が存在する（f(v)p,q=1）場合（Ｓ７４）、最小全域木生成手段１０は、辺e(v)p,qの重みw(e(v)p,q)を辺の最小重みweminに設定する（Ｓ７５）。一方、辺e(v)p,qに対応する基準木T(0)の辺が存在しない（f(v)p,q=0）場合（Ｓ７４）、最小全域木生成手段１０は、辺e(v)p,qの重みw(e(v)p,q)を辺の最大重みwemaxに設定する（Ｓ７６）。変更された辺e(v)p,qの重みw(e(v)p,q)は、辺データ記憶手段７に格納される。
【０１０１】
以上のような辺e(v)p,qの重みw(e(v)p,q)の変更処理が終了すると、p又はqをインクリメントして（Ｓ７７，Ｓ７８）、次のp又はqに移行する。
【０１０２】
上記ステップＳ７１〜Ｓ７８の処理により、すべての縦方向辺について辺の重みが修正される。同様な処理を、すべての横方向辺に対しても行う（Ｓ７９〜Ｓ８６）。これにより、重み付き連結グラフGの辺のうち、平坦領域に属する辺については、基準木に属する辺については重みが辺の最小重みweminに設定され、基準木に属さない辺については重みが辺の最大重みwemaxに設定される。このように重み変更を行うことで、上述の最小全域木構成処理において、最小全域木Tminの平坦領域においては、基準木T(0)に属する辺のみが残るようにすることが可能となる。
【０１０３】
例えば、図１０に示すような原画像（テレビジョン・システム評価用ディジタル標準画像として広く使用されている「天気予報」画像）について最小全域木を生成する場合を考える。上述のような辺の重みの修正処理を行わずに最小全域木を構成した場合、生成される最小全域木は図１１に示したようなものとなる。一方、上述の辺の重みの修正処理を行うと、生成される最小全域木は図１２に示すようなものになる。図１１と図１２を比較して分かるように、辺の重みの修正処理を行うことによって、原画像において画素値の変化の少ない平坦領域では、最小全域木の辺は、基準木に属する辺のみが残るように修正されている。これにより、最小全域木と基準木とは大きな相関を有することとなる。従って、最小全域木から基準木を差し引くことによって、走査情報の冗長性を除去することが可能となる。
【０１０４】
（３）差分走査情報の生成処理及び差分走査情報符号化処理
次に、最小全域木記憶手段１１に基準木T(0)との相関が大きい最小全域木Tminが格納された後に行われる、差分走査情報の生成処理について説明する。
【０１０５】
まず最初に、最小全域木記憶手段１１に格納されている最小全域木Tminの辺存在フラグの集合をE'=E'(v)∪E'(h), E'(v)={e'(v)p,q | p=1,…,M-1, q=1,…,N}, E'(h)={e'(h)p,q | p=1,…,M, q=1,…,N-1}とする。ここで、e'(v)p,q=1(e'(h)p,q=1)の場合には、節点bp,qと節点bp+1,q（節点bp,qと節点bp,q+1）を連結する最小全域木Tminの縦方向辺（横方向辺）が存在することを表し、e'(v)p,q=0(e'(h)p,q=0)の場合には、そのような辺は存在しないことを表す。
【０１０６】
また、基準木記憶手段９に格納されている基準木T(0)の辺存在フラグの集合をF=F(v)∪F(h), F(v)={f(v)p,q | p=1,…,M-1, q=1,…,N}, F(h)={f(h)p,q | p=1,…,M, q=1,…,N-1}とする。
【０１０７】
また、差分走査情報をD=D(v)∪F(h), D(v)={d(v)p,q | p=1,…,M-1, q=1,…,N}, D(h)={d(h)p,q | p=1,…,M, q=1,…,N-1}とする。なお、d(v)p,q, d(h)p,qは２値変数である。
【０１０８】
差分走査情報生成手段１２は、まず、最小全域木Tminと基準木T(0)のすべての対応する縦方向辺について差分e'(v)p,q-f(v)p,qを算出しこれを変数d(v)p,qに格納する。ここで、e'(v)p,q、f(v)p,qは２値変数なので、差分はブール演算により行われる。また、最小全域木Tminと基準木T(0)のすべての対応する横方向辺について差分e'(h)p,q-f(h)p,qを算出しこれを変数d(h)p,qに格納する。
【０１０９】
最小全域木Tminの辺と基準木T(0)の辺は平坦領域において一致しているので、d(v)p,q，d(h)p,qは、平坦領域ではすべて０となり、それ以外の領域では０又は１の値をとる。図１３は図１２の最小全域木から図９の基準木を差し引いて得られる差分走査情報を示す図である。図１３（ａ）は縦方向辺に対する差分走査情報、図１３（ｂ）は横方向辺に対する差分走査情報を表している。黒色の点が差分が１である点を表す。図１３から分かるように、原画像（図１０参照）の平坦領域においては差分が０の点が連続して現れることが分かる。
【０１１０】
そこで、これらの縦方向辺及び横方向辺に対する差分走査情報を符号化することにより、平坦領域における差分情報の冗長性が除去され、高い符号化効率での符号化が可能となる。
【０１１１】
符号化の方法としては、差分走査情報は２値データであることから、縦方向辺及び横方向辺に対する差分走査情報のそれぞれに対して、ランレングス符号を使用して符号化を行うことができる。
【０１１２】
また、図１３を見て分かるとおり、縦方向辺及び横方向辺に対する差分走査情報の空間的な相関が大きい。従って、この２つの差分走査情報画像を合体させて、各画素が(d(v)p,q, d(h)p,q)で表される２ビット画像とする。そして、この２ビット画像を、ランレングス・ハフマン符号や算術符号などを用いて符号化すれば、より符号化効率を高めることができる。
【図面の簡単な説明】
【０１１３】
【図１】本発明の実施例１に係る画像符号化装置の構成を表す図である。
【図２】本発明の実施例１に係る画像符号化方法の全体の流れを表すフローチャートである。
【図３】走査情報の生成処理の全体の流れを表すフローチャートである。
【図４】最小全域木構成処理の流れを表すアルゴリズムである。
【図５】各辺の重み修正処理を表すフローチャートである。
【図６】各辺の重み修正処理を表すフローチャートである。
【図７】各辺の重み修正処理を表すフローチャートである。
【図８】平坦領域の判定方法の説明図である。
【図９】基準木を表す図である。
【図１０】原画像の一例を示す図である。
【図１１】従来法により生成した最小全域木を示す図である。
【図１２】本発明の方法により生成した最小全域木を示す図である。
【図１３】差分走査情報を示す図である。
【図１４】適応的空間充填走査による画像符号化方法の基本的な流れを表すフローチャートである。
【図１５】適応的空間充填曲線を生成する過程を説明する図である。
【図１６】走査パターンを示す図である。
【図１７】区分線型近似処理を説明する図である。
【符号の説明】
【０１１４】
１  画像符号化装置
２  フレーム・バッファ
３  ブロック分割手段
４  代表値演算手段
５  節点記憶手段
６  グラフ生成手段
７  辺データ記憶手段
８  重み修正手段
９  基準木記憶手段
１０  最小全域木生成手段
１１  最小全域木記憶手段
１２  差分走査情報生成手段
１３  走査情報符号化手段
１４  符号化走査情報記憶手段
１５  走査線生成手段
１６  画像データ符号化手段
１７  符号化画像データ記憶手段
１８  画像入力手段
１９  符号化画像出力手段
【図１】
2005184710.tif 000014
【図２】
2005184710.tif 000015
【図３】
2005184710.tif 000016
【図４】
2005184710.tif 000017
【図５】
2005184710.tif 000018
【図６】
2005184710.tif 000019
【図７】
2005184710.tif 000020
【図８】
2005184710.tif 000021
【図９】
2005184710.tif 000022
【図１０】
2005184710.tif 000023
【図１１】
2005184710.tif 000024
【図１２】
2005184710.tif 000025
【図１３】
2005184710.tif 000026
【図１４】
2005184710.tif 000027
【図１５】
2005184710.tif 000028
【図１６】
2005184710.tif 000029
【図１７】
2005184710.tif 000030