(57)【要約】【課題】任意の領域形状に適応して走査線を生成することが可能であり、かつ走査情報の情報量の少ない領域走査技術を提供する。【解決手段】走査領域を一又は複数種類のタイル領域を組み合わせて走査領域を充填し部分領域に分割する部分領域分割手段１１と、各部分領域からなる節点、及び隣接する部分領域間を連結する辺から構成される全域木を生成する全域木生成手段１３と、各部分領域につき、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路からなる部分走査線の情報を生成する部分走査線生成手段１４と、全域木の辺により連結されている一対の部分領域の部分走査線のそれぞれを連結する操作を全域木のすべての辺に対して行い、走査領域に含まれるすべての画素を節点とするハミルトン閉路からなる全域走査線の情報を生成する全域走査線生成手段１６とを備えた。【選択図】        図１
2005198050.tif 000002
【特許請求の範囲】
【請求項１】
走査対象となる画像の一領域（以下、「走査領域」という。）について当該走査領域内の走査を行う領域走査装置であって、
あらかじめ用意された複数種類の所定の大きさ及び形状を有するタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割する部分領域分割手段と、
前記各部分領域からなる節点、及び隣接する部分領域間を連結する辺から構成される全域木の情報である部分領域連結情報を生成する全域木生成手段と、
前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路からなる部分走査線の情報を生成する部分走査線生成手段と、
前記部分領域連結情報に基づいて、前記全域木の辺により連結されている一対の部分領域の部分走査線のそれぞれを連結する操作を前記全域木のすべての辺に対して行い、前記走査領域に含まれるすべての画素を節点とするハミルトン閉路からなる全域走査線の情報を生成する全域走査線生成手段と、
を備えたことを特徴とする領域走査装置。
【請求項２】
前記部分領域分割手段は、あらかじめ用意された各辺の長さが偶数の複数種類の正方形又は長方形のタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割することを特徴とする請求項１記載の領域走査装置。
【請求項３】
前記部分走査線生成手段は、前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路であって、当該部分領域の輪郭を構成する画素｛ai,j | i=1, M, j=1,…, N｝，｛ai,j | i=3,…, M-1, j=1, N｝（M，Nは偶数）のうち、画素ai,2n-1(i=1 or M, n=1,…,N/2)と画素ai,2nを連結する辺、及び画素a2m-1,j(m=1,…,M/2, j=1 or N)と画素a2m,jを連結する辺を含む閉路からなる部分走査線の情報を生成することを特徴とする請求項２記載の領域走査装置。
【請求項４】
走査対象となる画像の一領域（以下、「走査領域」という。）について当該走査領域内の走査を行う領域走査方法であって、
あらかじめ用意された複数種類の所定の大きさ及び形状を有するタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割する第１ステップ、
前記各部分領域からなる節点、及び隣接する部分領域間を連結する辺から構成される全域木の情報である部分領域連結情報を生成する第２ステップ、
前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路からなる部分走査線の情報を生成する第３ステップ、
及び、前記部分領域連結情報に基づいて、前記全域木の辺により連結されている一対の部分領域の部分走査線のそれぞれを連結する操作を前記全域木のすべての辺に対して行い、前記走査領域に含まれるすべての画素を節点とするハミルトン閉路からなる全域走査線の情報を生成する第４ステップ、
を備えたことを特徴とする領域走査方法。
【請求項５】
前記第１ステップにおいて、あらかじめ用意された各辺の長さが偶数の複数種類の正方形又は長方形のタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割することを特徴とする請求項４記載の領域走査方法。
【請求項６】
前記第３ステップにおいて、前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路であって、当該部分領域の輪郭を構成する画素｛ai,j | i=1, M, j=1,…, N｝，｛ai,j | i=2,…, M-1, j=1, N｝（M，Nは偶数）のうち、画素ai,2n-1(i=1 or M, n=1,…,N/2)と画素ai,2nを連結する辺、及び画素a2m-1,j(m=1,…,M/2, j=1 or N)と画素a2m,jを連結する辺を含む閉路からなる部分走査線の情報を生成することを特徴とする請求項５記載の領域走査方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、領域分割された画像の各領域内を走査するための領域走査技術に関する。
【背景技術】
【０００２】
近年、画像符号化技術として、原画像について所与の画像特性に関して均質な領域に領域分割を行い、分割領域ごとに符号化を行う領域指向圧縮方法が研究されている。このような領域指向圧縮方法においては、任意形状に領域分割された領域画像を走査により１次元化する領域走査技術が必要とされる。
【０００３】
方形領域又は三角形領域の領域走査技術としては種々のものが考えらている（例えば、特許文献１〜３参照）。しかしながら、走査領域が任意形状の場合には、これらの方法をそのまま適用することができない。
【０００４】
任意形状領域の走査方法として最も単純なものとしては、横方向又は縦方向若しくは斜め方向にジグザグ走査又はラスタ走査をする方法が考えられる。しかしながら、ジグザグ走査やラスタ走査では、原画像の近傍画素間の画素値に関する相関性を、走査により得られる一次元の画像データ（一次元画像データ）に十分反映させることができない。
【０００５】
そこで、原画像の近傍画素間の画素値に関する相関性を十分に活用し、一次元画像データの局所的相関をできる限り高めるための走査技術として、任意の矩形領域形状に適応したハミルトン閉路を使用する方法が考案されている（非特許文献１参照）。以下、非特許文献１に記載の領域走査方法の概要を説明する。
【０００６】
まず、原画像を、各画素を節点（vertex）とする格子グラフ（grid-graph）Gと考える。すなわち、節点の集合をＶとすると、グラフGはG=(V, φ)である。そして、このグラフGについて、２×２画素の正方形に分割し、各正方形の４つの節点を正方形の辺（edge）で連結する。これにより、グラフGは多数の２×２画素の正方形グラフが格子状に配列したグラフとなる（図１６（ａ）参照）。以下、これらの正方形グラフを小閉路（small circuit）と呼ぶ。すべての小閉路の辺の集合をEとする。
【０００７】
各小閉路の４つの辺には重み付けがされる。辺の重みは、その辺の両端の節点である画素の画素値の差の絶対値が用いられる。カラー画像の場合には、各色の輝度値の差の絶対値和である。例えば、辺e=(a,b)の重みw(e)は、w(e)=|ared-bred|+|agreen-bgreen|+|ablue-bblue|となる。
【０００８】
また、グラフGに小閉路の辺を加えて構成されるグラフ(V, E)に対して、１つの小閉路を１つの節点とする連結格子グラフを二次グラフ（dual graph）と呼び、G'=(V', E')と記す（図１６（ｂ）参照）。グラフG'の隣接する各節点は、縦方向又は横方向の辺で連結されている。
【０００９】
今、グラフ(V,E)において、相隣接する２つの小閉路をA, Bとする。小閉路Aの４つの辺のうち、小閉路Bに隣接する辺をeとする。小閉路Bの４つの辺のうち、小閉路Aに隣接する辺をfとする。また、辺eの一端の節点とその節点に対向する辺fの一端の節点とを連結する仮想の辺を考え、これらの辺をそれぞれu，wとする（図１６（ａ）参照）。一方、グラフG'において、小閉路A,Bに対応する節点をそれぞれA',B'とする。そして、節点A'と節点B'とを連結する辺をv'とする（図１６（ｂ）参照）。
【００１０】
小閉路Aと小閉路Bとを結合する場合、辺e,fを削除して、その代わりに辺u,wが追加されることになる。従って、小閉路Aと小閉路Bとに含まれる辺の重みの総和は、結合によって、w(u)+w(w)-w(e)-w(f)だけ変化する。そこで、グラフ(V,E)の節点A',B'を連結する辺v'の重みW(A,B)をW(A,B)=|w(u)+w(w)-w(e)-w(f)|により定義する。すなわち、辺v'の重みW(A,B)は、小閉路Aと小閉路Bとが結合したときの辺の重みの総和の変化量である。重みW(A,B)は、辺eの両端の節点と、それぞれの節点に対向する辺fの両端の節点との節点値の差が大きいほど大きな値となる。
【００１１】
このようにして各辺の重み付けがされたグラフG'に対して、最小全域木T'を生成する。図１７は最小全域木（及び最小全域木に基づくハミルトン閉路）の生成過程を表した図である。図１７では、左下の小閉路を起点として、最小全域木を生成しながら小閉路の結合が同時に行われている。このようにして、最小全域木T'の辺において、隣接する小閉路の結合を行う。すべての小閉路の結合が終了した時点で、すべての画素を節点とするハミルトン閉路が完成する。
【００１２】
上記小閉路の結合は、画素値が近似する隣接辺が優先して結合される。従って、生成されるハミルトン閉路は原画像のオブジェクト形状に適合したものとなる。従って、このハミルトン閉路に沿って走査を行うことにより、適応的走査を行うことができる。
【特許文献１】特開平１１−１７８０００号公報
【特許文献２】特開２０００−１３６０８号公報
【特許文献３】特開平１０−７０６６４号公報
【非特許文献１】Revital Dafner, Daniel Cohen-Or, and Yossi Matias, "Context-based Space Filling Curves", Computer Graphics Forum, Volume 19, Issue 3 (August 2000)
【非特許文献２】情報処理学会編，「情報処理ハンドブック」，第１版，株式会社オーム社，平成９年９月２０日，pp.1289-1290
【非特許文献３】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.
【非特許文献５】Ｈ．ザーガン著，「空間充填曲線とフラクタル」，シュプリンガー・フェアラーク東京株式会社，１９９８年１２月２２日，pp.30-32
【非特許文献６】E. H. Moore, "On certain crinkly curves", Trans. Amer. Math. Soc., 1, (1900), pp. 72-90.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上記従来の走査方法によれば、走査線に沿った隣接画素の相関が大きくなるため、１次元化された画像の符号化効率を高めることができる。従って、１次元化画像の符号化効率が高いという点で優れた走査方法ということができる。
【００１４】
一方、適応的走査においては、原画像を復号化するために、走査線の形状に関する情報が必要とされる。そのため、原画像の符号化時には走査情報も同時に符号化する必要がある。そして、最終的には、符号化された原画像のデータ量は、符号化された１次元化画像のデータ量と符号化された走査情報のデータ量の和となる。
【００１５】
ところが、上記従来方法により得られる走査径路は、具体的な画像内容に依存して変化し一定ではない。従って、原画像を復号するためには、走査領域の画像全域にわたる走査線の径路情報が常に必要とされるため、走査情報の情報量が大きくなる。従って、符号化された走査情報のデータ量も大きくなるという問題がある。
【００１６】
そこで、本発明の目的は、任意の領域形状に適応して走査線を生成することが可能であり、かつ走査情報の情報量の少ない領域走査技術を提供することにある。
【課題を解決するための手段】
【００１７】
本発明に係る領域走査装置は、走査対象となる画像の一領域（以下、「走査領域」という。）について当該走査領域内の走査を行う領域走査装置であって、あらかじめ用意された複数種類の所定の大きさ及び形状を有するタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割する部分領域分割手段と、前記各部分領域からなる節点、及び隣接する部分領域間を連結する辺から構成される全域木の情報である部分領域連結情報を生成する全域木生成手段と、前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路からなる部分走査線の情報を生成する部分走査線生成手段と、前記部分領域連結情報に基づいて、前記全域木の辺により連結されている一対の部分領域の部分走査線のそれぞれを連結する操作を前記全域木のすべての辺に対して行い、前記走査領域に含まれるすべての画素を節点とするハミルトン閉路からなる全域走査線の情報を生成する全域走査線生成手段とを備えたことを特徴とする。
【００１８】
この構成により、走査領域の形状に適応して、走査領域のすべての画素を通る平面充填曲線に沿った走査線を生成することが可能となる。したがって、走査線に沿って走査領域内の画像を走査すれば、画像データを１次元化することができ、データの加工や符号化等のデータ処理が容易となる。
【００１９】
また、部分領域内の走査径路は予め決められているので、走査情報としては、部分領域の大きさや形状を特定するための情報（例えば、各種のタイル領域にそれぞれ固有に付されたＩＤ等）と、部分領域の配置に関する情報だけあればよい。従って、走査情報の情報量が少ないため、符号化した走査情報の情報量も低減することができる。
【００２０】
ここで、タイル領域の形状や大きさは、特に限定するものではなく、三角形、四角形、その他の多角形などを用いることができる。部分領域分割手段が走査領域内にタイル領域を充填する方法も特に限定するものではなく、種々の公知の方法を使用することが可能である。しかしながら、領域情報の情報量をできる限り削減する点から、できるだけ部分領域の数が少なくなるような区画方法を使用することが望ましい。
【００２１】
また、ハミルトン閉路とは、すべての節点を１回だけ通過するような閉路をいう。ハミルトン閉路の形状は、特に限定するものではなく、辺が交差するような閉路であってもよい。しかしながら、通常の画像データは、２つの画素間の距離が近いほど画素値の相関が大きいという性質を有している。従って、ハミルトン閉路の各辺は、できる限り隣接する画素間を連結する辺とすることが望ましい。また、ハミルトン閉路としては、ムーア曲線のように、閉路上に配列される画素同士のユークリッド距離ができる限り短くなるような閉路を使用するのが好ましい。閉路上に配列される画素同士の画素値の相関係数が大きくなり、符号化する際に圧縮効率が高まるからである。
【００２２】
また、本発明において、前記部分領域分割手段は、あらかじめ用意された各辺の長さが偶数の複数種類の正方形又は長方形のタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割するようにしてもよい。
【００２３】
タイル領域の形状を、正方形又は長方形とすると、走査領域内にタイル領域を充填する方法が簡単となる。また、タイル領域内にハミルトン径路を生成することも容易となる。
【００２４】
また、本発明において、前記部分走査線生成手段は、前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路であって、当該部分領域の輪郭を構成する画素｛ai,j | i=1, M, j=1,…, N｝，｛ai,j | i=2,…, M-1, j=1, N｝（M，Nは偶数）のうち、画素ai,2n-1(i=1 or M, n=1,…,N/2)と画素ai,2nを連結する辺、及び画素a2m-1,j(m=1,…,M/2, j=1 or N)と画素a2m,jを連結する辺を含む閉路からなる部分走査線の情報を生成するようにしてもよい。
【００２５】
このように、部分走査線生成手段が生成する部分走査線を、画素ai,2n-1(i=1 or M, n=1,…,N/2)と画素ai,2nを連結する辺、及び画素a2m-1,j(m=1,…,M/2, j=1 or N)と画素a2m,jを連結する辺を含むハミルトン閉路とすることで、タイル領域の最小サイズを２×２画素の正方形とすることができる。従って、走査可能な走査領域の形状の自由度を大きくすることができる。
【００２６】
本発明に係る領域走査方法は、走査対象となる画像の一領域（以下、「走査領域」という。）について当該走査領域内の走査を行う領域走査方法であって、あらかじめ用意された複数種類の所定の大きさ及び形状を有するタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割する第１ステップ、前記各部分領域からなる節点、及び隣接する部分領域間を連結する辺から構成される全域木の情報である部分領域連結情報を生成する第２ステップ、前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路からなる部分走査線の情報を生成する第３ステップ、及び、前記部分領域連結情報に基づいて、前記全域木の辺により連結されている一対の部分領域の部分走査線のそれぞれを連結する操作を前記全域木のすべての辺に対して行い、前記走査領域に含まれるすべての画素を節点とするハミルトン閉路からなる全域走査線の情報を生成する第４ステップを備えたことを特徴とする。
【００２７】
また、前記第１ステップにおいて、あらかじめ用意された各辺の長さが偶数の複数種類の正方形又は長方形のタイル領域を用いて前記走査領域を充填することにより、各タイル領域により区画される部分領域に分割することができる。
【００２８】
更に、前記第３ステップにおいて、前記各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路であって、当該部分領域の輪郭を構成する画素｛ai,j | i=1, M, j=1,…, N｝，｛ai,j | i=2,…, M-1, j=1, N｝（M，Nは偶数）のうち、画素ai,2n-1(i=1 or M, n=1,…,N/2)と画素ai,2nを連結する辺、及び画素a2m-1,j(m=1,…,M/2, j=1 or N)と画素a2m,jを連結する辺を含む閉路からなる部分走査線の情報を生成することができる。
【発明の効果】
【００２９】
以上のように、本発明によれば、走査領域の形状を問わず、当該走査領域に適応した走査線を生成することが可能となる。したがって、走査線に沿って走査領域内の画像を走査すれば、画像データを１次元化することができ、データの加工や符号化等のデータ処理が容易となる。また、部分領域内の走査径路は予め決められているので、走査情報の情報量を少なくでき、符号化した走査情報の情報量も低減することができる。そのため、任意形状の領域分割による画像符号化に使用するのに適した画像走査技術を提供することができる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００３１】
図１は本発明の実施例１に係る領域走査装置を用いた画像符号化装置の構成を表すブロック図である。図１において、画像符号化装置１は、走査領域分割手段２、走査領域記憶手段３、領域走査装置４、領域情報符号化手段５、区分線形近似手段６、及び区分情報符号化手段７を備えている。
【００３２】
走査領域分割手段２は、画像データ記憶手段８に格納された原画像について、当該原画像を所与の画像特性に関して均質な重複しない連結領域に分割し、走査領域記憶手段３に格納する。ここで、「所与の画像特性」としては、例えば、原画像がグレー・スケールの画像データの場合であれば画像の輝度値等、原画像がカラー画像の場合には、各画素の色ベクトル等が使用される。以下、便宜上、原画像はグレー・スケールの画像データであると仮定して、所与の画像特性としては各画素の輝度値を用いることとする。
【００３３】
走査領域分割手段２による領域分割の方法としては、種々の領域分割（クラスタリング）方法を使用することができる。例えば、分割領域内の輝度値のレンジ（最大値と最小値との差）が所定の閾値以内となるように領域分割する方法などである。現在公知の領域分割方法としては、例えば、統合法（統計的仮説検定法、ヒューリスティック法、関数近似法等）、分割法、分割・統合法、画素結合法等が挙げられる（非特許文献２参照）。
【００３４】
領域走査装置４は、走査領域記憶手段３に格納された各連結領域の画像（以下、「領域画像」という。）について、所定の大きさ及び形状の部分領域に分割するとともに、当該領域画像に含まれるすべての画素を走査する走査線を生成し領域画像を走査することにより１次元領域画像データを生成する。
【００３５】
領域情報符号化手段５は、領域走査装置４により生成される各部分領域の形状等及び配置に関する情報を符号化し、符号化走査情報記憶手段９に格納する。
【００３６】
区分線形近似手段６は、領域走査装置４により生成される１次元領域画像データを区分線形近似により不可逆的に符号化する。尚、区分線形近似の方法については、非特許文献３，４に記載されている。区分線形近似により、１次元領域画像データは複数の区間の区間長データと当該区間の画素値データとの組からなるデータ（以下、「区分線形近似データ」という。）に符号化される。
【００３７】
区分情報符号化手段７は、区分線形近似データを符号化して符号化画像情報を生成し、符号化画像情報記憶手段１０に格納する。
【００３８】
領域走査装置４は、部分領域分割手段１１、部分領域記憶手段１２、全域木生成手段１３、部分走査線生成手段１４、部分走査線情報記憶手段１５、全域走査線生成手段１６、及び走査手段１７を備えている。
【００３９】
部分領域分割手段１１は、各種類の大きさ（辺の長さは偶数とする。）を有する正方形のタイル領域を用いて領域画像を充填することにより、領域画像を各タイル領域により区画される部分領域に分割し、部分領域の大きさと位置に関する情報を部分領域記憶手段１２に格納する。尚、本発明においては、タイル領域の形状は長方形であってもよいし、三角形や六角形の各種平面充填形状であってもよい。本実施例では簡単のために、タイル領域の形状は正方形を使用する。
【００４０】
全域木生成手段１３は、部分領域記憶手段１２に格納された各部分領域を節点とし、隣接する部分領域間を連結する辺を用いて構成される全域木の情報（以下、「部分領域連結情報」という。）を生成する。全域木の構成方法としては、どのような方法を使用してもよい。全域木の構成方法のいくつかの例については後述する。
【００４１】
部分走査線情報記憶手段１５には、各部分領域を充填する空間充填曲線に関する情報が格納されている。この空間充填曲線は、部分領域の画素を節点とし、これら節点と近傍の節点間を連結する辺で構成されるハミルトン閉路により構成される。このようなハミルトン閉路としては、ヒルベルト曲線（Hilbert curve）の変形であるムーア曲線（Moore's Hilbert-curve）（非特許文献５，６参照）等が使用される。
【００４２】
尚、本実施例においては、ハミルトン閉路としては、部分領域の輪郭を構成する画素｛ai,j | i=1, M, j=1,…, N｝，｛ai,j | i=2,…, M-1, j=1, N｝（M，Nは偶数）のうち、画素ai,2n-1(i=1 or M, n=1,…,N/2)と画素ai,2nを連結する辺、及び画素a2m-1,j(m=1,…,M/2, j=1 or N)と画素a2m,jを連結する辺を含む閉路を使用する。このような辺が含まれない場合には、後で説明するように、２×２画素の部分領域を他の大きな部分領域に連結する際に不都合が生じる場合があるからである。従って、上記ムーア曲線を使用する場合には、そのまま使用することはできないので、輪郭辺について上記条件を満たすように修正を施した修正ムーア曲線を使用する。
【００４３】
部分走査線生成手段１４は、部分走査線情報記憶手段１５に格納された空間充填曲線を参照して、部分領域記憶手段１２に格納された各部分領域について、当該部分領域に含まれるすべての画素を節点とするハミルトン閉路からなる部分走査線の情報を生成する。
全域走査線生成手段１６は、全域木生成手段１３が生成する部分領域連結情報に基づいて、全域木の辺により連結されている一対の部分領域の部分走査線のそれぞれを連結する操作を全域木のすべての辺に対して行い、走査領域に含まれるすべての画素を節点とするハミルトン閉路からなる全域走査線の情報を生成する。走査手段１７は、全域走査線生成手段により生成される走査線に沿って領域画像を走査して、一次元領域画像データを生成する。
【００４４】
以上のように構成された本実施例の領域走査装置について、以下その動作を説明する。図２は実施例１に係る領域走査方法の処理の全体の流れを表すフローチャートである。尚、領域走査をするにあたり、前処理として、まず、走査領域分割手段２により原画像の領域分割が行われる。本発明においては、領域分割は、分割領域内の輝度値の最大値と最小値との差が所定の範囲内となるように統合法を用いて行われる。例えば、図３（ａ）に示した画像は領域分割により、図３（ｂ）に示すような各領域に分割される。尚、この領域分割は２×２画素の正方形を最小単位として行われる。各領域画像は、走査領域記憶手段３に格納されている。
【００４５】
このように領域分割された原画像に対して、まず、部分領域分割手段１１は、各領域画像にタイル領域を充填することにより各領域画像を部分画像にブロック分割する（Ｓ１）。そして、部分領域分割手段１１は、これら部分画像の大きさと位置に関するデータを部分領域記憶手段１２に格納する。
【００４６】
次いで、全域木生成手段１３は、それぞれの領域画像について、当該領域画像内の各部分画像を節点とし、隣接する節点間を連結する枝のみを含む全域木の情報（部分領域連結情報）を生成する（Ｓ２）。また、一方で、部分走査線生成手段１４は、それぞれの領域画像について、当該領域画像内の各部分画像を充填するハミルトン閉路からなる走査線を生成する（Ｓ３）。実際には、全域木生成手段１３は、各部分画像のサイズを参照して、部分走査線情報記憶手段１５からそのサイズに対応する空間充填曲線に関する情報を読み出すことで、走査線を生成する。
【００４７】
最後に、全域走査線生成手段１６は、それぞれの領域画像について、部分領域連結情報に基づき各部分領域の走査線を連結して全域走査線を生成する。そして、走査手段１７は、生成された走査線に沿って部分領域内を走査し、１次元領域画像データを生成する（Ｓ４）。
【００４８】
以上が実施例１に係る領域走査方法の処理の全体の流れである。次に、図２のそれぞれのステップについて詳細に説明する。
【００４９】
図４はタイル領域充填により領域画像を部分画像にブロック分割する処理を表すフローチャートである。この処理においては、図３（ｂ）に示したような原画像内のすべての領域画像について、同時にブロック分割を行う。
【００５０】
原画像のサイズをM×N画素とする。ここで、M，Nは２の冪乗であるとする。原画像の画素の集合をA={ai,j | i=1,…,M, j=1,…,N}と記す。領域分割により得られた各領域画像をR={rk | k=1,…,x}と記す。xは原画像内の領域画像の数である。ブロック分割後の部分領域のサイズを2n×2n画素（n=1,2,…,n0）とする。以下では、nを部分画像のブロックサイズと呼ぶ。ブロック分割に用いられる2n×2n画素の正方形ブロックの画素の集合をB(n)={b(n)p,q | p=1,…,M/2n, q=1,…,N/2n}と記す。
【００５１】
また、最初に原画像Aを２×２画素の正方形ブロック（以下、「最小ブロック」という。）に分割しておいて、それぞれの最小ブロックに登録済フラグsp,q（p=1,…,M/2, q=1,…,N/2）を割り当てておく。登録済フラグsp,qは０又は１の値をとる。この登録済フラグsp,qは、対応する最小ブロックが既にブロック分割により確定された部分画像に属しているか否かを表すためのフラグである。sp,q=0の場合には確定済の部分画像には属していないことを表し、sp,q=1の場合には確定済の部分画像に属していることを表す。
【００５２】
まず、部分領域分割手段１１は、初期の部分画像のブロックサイズnをn0に初期化する（Ｓ１１）。そして、すべての登録済フラグsp,q（p=1,…,M/2, q=1,…,N/2）を０に初期化する（Ｓ１２）。
【００５３】
このとき、原画像は、2n×2n画素の正方形ブロックに分割されていると想定する。そして、各正方形ブロックの座標を（p,q）（p=1,…,M/2n, q=1,…,N/2n）とする。また、座標（p,q）の正方形ブロックは、前述の通りb(n)p,qと記す。部分領域分割手段１１は、最初にp=1,q=1に設定する（Ｓ１３）。
【００５４】
次に、部分領域分割手段１１は、正方形ブロックb(n)p,q内の最小ブロックの登録済フラグを参照し、正方形ブロックb(n)p,qが既に確定済の部分画像に属しているか否かを判定する（Ｓ１４）。正方形ブロックb(n)p,qが既に確定済の部分画像に属している場合には、この正方形ブロックに関しては処理をする必要はないので、ステップＳ２０に移行する。
【００５５】
ステップＳ１４で、正方形ブロックb(n)p,qが既に確定済の部分画像には属していない場合、部分領域分割手段１１は、内部変数kを１からｘまで１ずつ変化させながら（Ｓ１５，Ｓ１７）、正方形ブロックb(n)p,qが領域画像rkに完全に包含されている（すなわち、正方形ブロックb(n)p,qが領域画像rkの部分集合（b(n)p,q∈rk）である）か否かを判定する（Ｓ１６）。正方形ブロックb(n)p,qが何れの領域画像にも包含されない場合には、この正方形ブロックb(n)p,qはサイズが大きすぎるので、次の正方形ブロックの処理に移るべく、ステップＳ２０に移行する。
【００５６】
一方、ステップＳ１６において、正方形ブロックb(n)p,qが領域画像rkに包含される場合、部分領域分割手段１１は、この正方形ブロックb(n)p,qを領域画像rkの部分画像に確定する。そして、部分領域分割手段１１は、正方形ブロックb(n)p,qを、部分領域記憶手段１２に格納された登録ブロック構造体に登録する（Ｓ１８）。ここで、登録ブロック構造体は図５に示したようなデータ構造を有する。図５において、各登録ブロックには、確定済の部分画像に関する情報が格納されている（図５（ａ）参照）。それぞれの登録ブロックは、図５（ｂ）に示したように、｛領域画像ＩＤ，部分画像ＩＤ，部分画像の左上画素のｘ座標，部分画像の左上画素のｙ座標，部分画像のブロックサイズ，子節点データ｝により構成される。領域画像ＩＤには、部分画像が属する領域画像rkの番号kが登録される。部分画像ＩＤには、領域画像rk内における部分画像の番号が登録される。この部分画像の番号は、先に登録された順に順次付されていく。従って、ブロックサイズの大きい部分画像ほど若い番号が付される。ブロックサイズには、当該部分画像b(n)p,qのブロックサイズnが登録される。尚、子節点データは、後述の全域木の生成の際に辺情報が格納される部分であり、現段階では何も登録されない。
【００５７】
図４に戻って、次に、部分領域分割手段１１は、確定した部分領域（正方形ブロックb(n)p,q）に属しているすべての最小ブロックの登録済フラグsp',q'（∈b(n)p,q）を１に設定する（Ｓ１９）。そして、ステップＳ２０に移行する。
【００５８】
ステップＳ２０では、qの値がN/2nに達していない場合には、qの値を１だけ繰り上げて、ステップＳ１４に移行する。また、qの値がN/2nの場合には、pの値がM/2nに達していなければ、pの値を１だけ繰り上げるとともにq=1として、ステップＳ１４に移行する。q= N/2nかつp= M/2nの場合には、次のステップＳ２１に移行する。
【００５９】
以上のようなステップＳ１３〜Ｓ２０の処理が終了すると、次に、部分領域分割手段１１は、ブロックサイズnの値を１だけ減少させる（Ｓ２１）。そして、nが１以上の場合には（Ｓ２２）、再びステップＳ１３に戻る。一方、n<1の場合には（Ｓ２２）、処理を終了する。
【００６０】
以上のような処理により、すべての領域画像について部分画像へのブロック分割がなされる。この方法の特徴は、各領域画像は、できるだけブロックサイズが大きい部分画像にブロック分割されることである。各領域画像をブロックサイズが大きい部分画像に分割すれば、各領域画像の分割数は平均的に小さくなる。従って、領域情報（すなわち、登録ブロック構造体）の情報量もその分だけ少ないため、領域情報を符号化した後のデータ量を小さくすることができる。その結果、原画像の符号化を高い符号化効率で行うことができる。
【００６１】
次に、図２におけるステップＳ２の処理（各部分画像を節点とする全域木の生成処理）の詳細を説明する。図６は各部分画像を節点とする全域木の生成処理の全体の流れを表すフローチャートである。図７は図６における全域木生成サブルーチン（Spaning_tree）の処理を表す図である。尚、図６，図７の例では、再帰処理を用いている。
【００６２】
まず、全域木生成手段１３は、処理対象となる領域画像の番号kを１に設定する（Ｓ３１）。そして、部分領域記憶手段１２に格納されている登録ブロック構造体を参照し、部分領域rkに属する一の部分画像を根節点biとする（Ｓ３２）。この場合、根節点biはどの部分画像を選択してもよいが、ここでは簡単のため、部分画像ＩＤが最も小さい部分画像b1を根節点として選択することとする。
【００６３】
そして、選択した根節点の番号ｉ＝１を引数として、全域木生成サブルーチンを呼び出す（Ｓ３３）。
【００６４】
以上のステップＳ３２，Ｓ３３をkが１からxまで繰り返し（Ｓ３４）終了する。
【００６５】
全域木生成サブルーチンにおいては、以下のような再帰処理が行われる。まず、全域木生成サブルーチンが引数をｉとして呼び出されると（Ｓ４０）、まず、全域木生成手段１１は、部分画像biに隣接する部分画像を探索し、隣接する部分画像の中に未連結な部分画像があるか否かを判定する（Ｓ４１）。
【００６６】
ここで、部分画像biに隣接する部分画像の中に未連結な部分画像{bp | p=1,…,ξ}が見つかった場合、全域木生成手段１１は、部分画像biから各隣接部分画像bpに向かう枝epを生成する（Ｓ４２）。具体的には、全域木生成手段１１は、登録ブロック構造体の部分画像biに対応する登録ブロックにおいて、子節点データとして、子節点の数（出次数）ξ、及び未連結な隣接部分画像{bp}を登録する。更に、それぞれの子節点データに対応して、探索済フラグが内部変数として生成され、０（未探索）に初期化される。この探索済フラグは、再帰処理により枝の探索を正常に実行するために用いられるフラグである。
【００６７】
次に、全域木生成手段１１は、部分画像biの子節点{bp}のうち部分画像ＩＤが最も小さい部分画像bj（∈{bp}）を選択する（Ｓ４３）。そして、選択された部分画像bjの番号jを引数として、全域木生成サブルーチンを再帰的に呼び出す（Ｓ４４）。そして、子節点bjに対応する探索済フラグを１（探索済）としてステップＳ４１に戻る。
【００６８】
一方、ステップＳ４１において、部分画像biに隣接する部分画像の中に未連結な部分画像が見つからなかった場合、全域木生成手段１１は、部分画像biの各子節点に対応する探索済みフラグを参照して、未探索の子節点が存在するか否かを判定する（Ｓ４６）。
【００６９】
ここで、未探索の子節点が存在する場合、全域木生成手段１１は、それらの子節点のなかで最も部分画像ＩＤが小さい節点bjを選択する（Ｓ４７）。そして、選択された部分画像bjの番号jを引数として、全域木生成サブルーチンを再帰的に呼び出す（Ｓ４４）。そして、子節点bjに対応する探索済フラグを１（探索済）としてステップＳ４１に戻る。
【００７０】
一方、ステップＳ４６において、未探索の子節点が存在しない場合には、全域木生成手段１１は、全域木生成サブルーチンにおける処理を終了する。
【００７１】
〔例１〕
例えば、領域画像の形状が図８（ａ）に示すようなものであり、この領域画像が部分画像b1〜b8にブロック分割されている場合を考える。この場合、部分画像は、ブロックサイズが大きい順に若い番号が付されている。また、ブロックサイズが同じ部分領域については、最も左上の部分領域から水平方向に昇順に番号が付されている。
【００７２】
まず、最初に、番号が最も小さい部分領域b1が根節点とされる。そして、部分領域b1に隣接する未連結の部分領域b3, b4, b5, b12, b10, b9, b8, b7が部分領域b1の子節点に登録される。ここで、部分領域b1の出次数は８である。
【００７３】
次に、部分領域b1に隣接する部分領域のうち、最も番号が小さい部分領域b3が選択される。そして、この部分領域b3について、上記と同様に、部分領域b3に隣接する未連結の部分領域b2が部分領域b3の子節点に登録される。尚、部分領域b1,b4は既に連結済であるため、部分領域b3の子節点に登録されることはない。
【００７４】
次に、部分領域b2に隣接する部分領域のうち、最も番号が小さい部分領域b2が選択される。そして、この部分領域b2について、上記と同様に、部分領域b2に隣接する未連結の部分領域b6が部分領域b2の子節点に登録される。
【００７５】
次に、部分領域b2に隣接する部分領域のうち、最も番号が小さい部分領域b6が選択される。しかしながら、部分領域b6に隣接する未連結の部分領域はなく、また、部分領域b6の子節点もないため、部分領域b2にバックトラックする。
【００７６】
また、部分領域b2には、他に未探索の子節点がないため、部分領域b3にバックトラックする。部分領域b3にも、他に未探索の子節点がないため、部分領域b1にバックトラックする。
【００７７】
部分領域b1には、未探索の子節点として部分領域b4, b5, b12, b10, b9, b8, b7があるが、まず、このうち、最も番号が小さい部分領域b4が選択される。そして、この部分領域b4について、上記と同様に、部分領域b4に隣接する未連結の部分領域b11が部分領域b4の子節点に登録される。次に、部分領域b4に隣接する部分領域のうち、最も番号が小さい部分領域b11が選択される。しかしながら、部分領域b11に隣接する未連結の部分領域はなく、また、部分領域b11の子節点もないため、部分領域b4にバックトラックする。部分領域b4にも、他に未探索の子節点がないため、再び部分領域b1にバックトラックする。
【００７８】
以下、部分領域b5, b7, b8, b9, b10, b12が順次選択されるが、各部分領域に隣接する未連結の部分領域はなく、また、各部分領域の子節点もないため、部分領域b1にバックトラックする。以上により全域木の生成処理が終了する。この処理により生成される全域木は、図８（ｂ）に示したようなものとなる。
〔例終わり〕
【００７９】
以上のような処理により、各部分画像を節点とする全域木が生成される。尚、図６，図７は一例であり、最小全域木の構成方法としては他にも種々の方法を用いることができる。例えば、図９（ａ）に示すように、各部分領域の部分領域ＩＤを左上から右下に向かって、昇順となるように付け替えて上記図６，図７で説明した処理を行った場合、生成される全域木は図９（ｂ）に示したようなものとなる。また、上記図７のステップＳ４３及びＳ４７において、選択する子節点を、部分画像ＩＤが最小のものではなく、左回りとなるものとすれば、生成される全域木は図１０に示したようなものとなる。何れの方法についても、本発明において使用することが可能である。
【００８０】
次に、図２のステップＳ３における処理（ハミルトン閉路の生成処理）について説明する。この処理は、部分走査線生成手段１４が、部分領域記憶手段１２に格納された領域画像内の各部分画像について、ブロックサイズを参照し、そのブロックサイズに対応する空間充填曲線に関する情報を読み出すだけである。ここで重要なのは、部分走査線情報記憶手段１５に予め格納しておく空間充填曲線の構成である。
【００８１】
この空間充填曲線は、各ブロックサイズの部分領域に含まれる各画素を節点とするハミルトン閉路が選択される。このようなハミルトン閉路としては、例えば、図１１に示したようなムーア曲線が知られている。しかしながら、このムーア曲線を使用した場合、２×２画素の最小ブロックを連結する際に不都合を来す。この不都合に関して、以下に簡単に説明しておく。
【００８２】
図１２（ａ）は最小ブロックの空間充填曲線である。最小ブロックの空間充填曲線は図１２（ａ）に示すもの以外はない。この最小ブロックを、例えば、図１１（ｂ）に示した８×８画素のムーア曲線に連結する場合を考える。図１２（ｂ）に示す位置に最小ブロックを連結した場合には、連結後に得られる走査線は連結したハミルトン閉路であり、特に支障は来さない。しかしながら、図１２（ｃ）の位置に最小ブロックを連結する場合、連結によって孤立閉路が生じると共に、残りの走査線は閉路とはならないという不都合が生じる。
【００８３】
そこで、このムーア曲線を修正し、図１２（ｄ）のような修正ムーア曲線とする。このようにすれば、図１２（ｂ）と同じ位置に最小ブロックを連結した場合であっても、図１２（ｅ）のように、連結後に得られる走査線は連結したハミルトン閉路であり、特に支障は来さない。
【００８４】
すなわち、部分領域の外辺を構成する節点のうち、行番号又は列番号が奇数番目の節点と、当該節点の右又は下方向に隣接する節点とを連結する辺が必ず存在するように、ムーア曲線を修正すればよい。このよにして得られる修正ムーア曲線を図１３に示す。
【００８５】
尚、ここでは、ハミルトン閉路の一例として修正ムーア曲線を使用したが、本発明では、「部分領域の外辺を構成する節点のうち、行番号又は列番号が奇数番目の節点と、当該節点の右又は下方向に隣接する節点とを連結する辺が必ず存在する」という条件を満たすような、他の空間充填曲線を使用することも可能である。
【００８６】
〔例２〕
図９で例示した領域画像について、上記図１３の修正ムーア曲線を用いてハミルトン閉路の生成処理を行うと、図１４のような非連結な走査線が得られる。
〔例終わり〕
【００８７】
最後に、図２におけるステップＳ４の処理（全域走査線生成処理）について説明する。全域走査線生成手段１６は、部分走査線生成手段１４が生成する非連結な走査線を、全域木生成手段が生成する全域木の枝に沿って連結する。連結される２つの部分画像の何れか一方が２×２画素の最小ブロックであれば、図１２に示したように連結位置は一意的に決定する。しかしながら、連結される２つの部分画像の何れもがブロックサイズが４以上の場合、連結位置は一意的に決定しない。そこで、予め連結位置を決定する規則（連結位置決定規則）を定めておく。
【００８８】
連結位置決定規則としては、どのような規則を定めてもよい。例えば、以下の（１）〜（４）の順に優先的に規則を適用していく方法が考えられる。
【００８９】
（１）子節点の部分画像の左上端が連結可能な場合にはその端で連結し、また、親節点の左下端が連結可能な場合にはその端で連結する。
（２）子節点の部分画像の左下端が連結可能な場合にはその端で連結し、また、親節点の左上端が連結可能な場合にはその端で連結する。
（３）子節点の部分画像の右下端が連結可能な場合にはその端で連結し、また、親節点の右上端が連結可能な場合にはその端で連結する。
（４）子節点の部分画像の右上端が連結可能な場合にはその端で連結し、また、親節点の右下端が連結可能な場合にはその端で連結する。
【００９０】
走査線の連結は、親節点の部分画像の辺の１本とそれに対向する子節点の部分画像の辺の１本とを除去し、その結果生じる２対の隣接する端点同士を辺で連結することにより行う。
【００９１】
〔例３〕
図１４の非連結な走査線に対して、上述の連結位置決定規則によって全域走査線生成処理を行うと、図１５のようなハミルトン閉路からなる連結した１本の走査線が得られる。尚、図１５において、破線の円で示した部分が連結された位置を表す。
〔例終わり〕
【００９２】
走査手段１７は、以上のような全域走査線生成処理によって得られる走査線に沿って領域画像を走査し、１次元領域画像データを生成する。
【００９３】
このように、本実施例の領域走査装置によれば、任意の領域形状に適応して走査線を生成することが可能である。また、走査情報は、図５に示したような登録ブロック構造体として得られ、従来技術による走査情報と比較して情報量を極めて低減することができる。従って、走査情報のデータ量を低減することが可能となる。
【００９４】
更に、画像符号化の場合、符号化側と復号側との両者において共通の連結位置決定規則をあらかじめ決めておけば、復号側では、登録ブロック構造体の各登録ブロック内の情報のうち、「領域画像ＩＤ」、「部分画像の左上画素のｘ座標」、「部分画像の左上画素のｙ座標」、及び「部分画像のブロックサイズ」の情報さえあれば、連結位置決定規則に基づいて全域木を再構成することが可能である。従って、連結位置決定規則をあらかじめ決めておく場合には、登録ブロック構造体の情報のうち、「部分画像ＩＤ」及び「子節点データ」の情報は削除することができる。従って、更に走査情報のデータ量を低減することが可能となる。
【００９５】
尚、本実施例では、本発明の領域走査装置（及び領域走査方法）を画像符号化装置に適用した例を示したが、本発明は他にも印刷装置や顕微鏡の走査装置などの任意形状の領域走査を伴う装置に適用することが可能である。
【図面の簡単な説明】
【００９６】
【図１】本発明の実施例１に係る領域走査装置を用いた画像符号化装置の構成を表すブロック図である。
【図２】実施例１に係る領域走査方法の処理の全体の流れを表すフローチャートである。
【図３】原画像の領域分割の一例を示す図である。
【図４】タイル領域充填により領域画像を部分画像にブロック分割する処理を表すフローチャートである。
【図５】登録ブロック構造体のデータ構造を示す図である。
【図６】各部分画像を節点とする全域木の生成処理の全体の流れを表すフローチャートである。
【図７】図６における全域木生成サブルーチン（Spaning_tree）の処理を表す図である。
【図８】全域木の生成処理の一例を説明する図である。
【図９】全域木の生成処理の他の一例を示す図である。
【図１０】全域木の生成処理の他の一例を示す図である。
【図１１】ムーア曲線を表す図である。
【図１２】ムーア曲線を使用した場合に生じる不都合について説明する図である。
【図１３】修正ムーア曲線を表す図である。
【図１４】図９で例示した領域画像について、ハミルトン閉路の生成処理により生成される走査線の一例を示す図である。
【図１５】図１４の走査線に全域走査線生成処理を行うことにより得られる走査線の一例を示す図である。
【図１６】非特許文献１の走査線生成方法において、走査線生成の基礎となる小閉路及び二次グラフを表す図である。
【図１７】非特許文献１の走査線生成方法における、最小全域木（及び最小全域木に基づくハミルトン閉路）の生成過程を表した図である。
【符号の説明】
【００９７】
１  画像符号化装置
２  走査領域分割手段
３  走査領域記憶手段
４  領域走査装置
５  領域情報符号化手段
６  区分線形近似手段
７  区分情報符号化手段
８  画像データ記憶手段
９  符号化走査情報記憶手段
１０  符号化画素情報記憶手段
１１  部分領域分割手段
１２  部分領域記憶手段
１３  全域木生成手段
１４  部分走査線生成手段
１５  部分走査線情報記憶手段
１６  全域走査線生成手段
１７  走査手段
【図１】
2005198050.tif 000003
【図２】
2005198050.tif 000004
【図３】
2005198050.tif 000005
【図４】
2005198050.tif 000006
【図５】
2005198050.tif 000007
【図６】
2005198050.tif 000008
【図７】
2005198050.tif 000009
【図８】
2005198050.tif 000010
【図９】
2005198050.tif 000011
【図１０】
2005198050.tif 000012
【図１１】
2005198050.tif 000013
【図１２】
2005198050.tif 000014
【図１３】
2005198050.tif 000015
【図１４】
2005198050.tif 000016
【図１５】
2005198050.tif 000017
【図１６】
2005198050.tif 000018
【図１７】
2005198050.tif 000019