(57)【要約】【課題】ポリゴン又はポリラインを表すベクタ形式の図形データの符号化に関し圧縮効率の向上を図る。【解決手段】対象図形を内側に含む最小の矩形である境界ボックスの形状及び画像上の配置を表す境界ボックス情報を求める。連鎖の予め定められた起点Ｐ１について、境界ボックス上の基準点を原点とした座標を求める。対象図形を構成するエッジ数Ｋを取得し、又、起点Ｐ１からｋ番目のエッジを始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、１〜Ｋ番目のエッジについて順番にＥｋの長さＬｋ及び向きＡｋの情報を取得する（図形情報抽出ステップＳ１６）。境界ボックス情報、起点Ｐ１の座標、エッジ数Ｋ、並びにＫ個のＥｋのＬｋ，Ａｋを符号化する。図形情報抽出ステップは、２〜Ｋ番目のエッジについての向きＡｋを、Ｅｋ−１の向きに対してＥｋの向きが右向きか左向きかの二値情報で表す。【選択図】図８
2019053669.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ互いに交差するＸ方向及びＹ方向のいずれかに沿う複数の要素線分の連鎖からなる図形を対象図形とし、画像内における前記対象図形を表すベクタ形式データを圧縮符号化する方法であって、
前記Ｘ方向の辺及び前記Ｙ方向の辺からなり前記対象図形を内側に含む最小の矩形である境界ボックスの形状及び前記画像における配置を表す境界ボックス情報を求めるステップと、
前記連鎖の予め定められた起点Ｐ１について、前記境界ボックスにおける所定の基準点を原点とした座標を求めるステップと、
前記対象図形を構成する前記要素線分の数Ｋを取得すると共に、前記連鎖の起点Ｐ１からｋ番目（ｋはＫ以下の任意の自然数である。）の前記要素線分を始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、１番目乃至Ｋ番目の前記要素線分について順番に前記ベクトルＥｋの長さＬｋ及び向きＡｋの情報を取得する図形情報抽出ステップと、
前記境界ボックス情報、前記起点Ｐ１の座標、前記要素線分の数Ｋ、並びにＫ個の前記ベクトルＥｋの前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化して前記対象図形の符号化データとする符号化ステップと、を有し、
前記図形情報抽出ステップは、２番目乃至Ｋ番目の前記要素線分についての前記向きＡｋを、ベクトルＥｋ−１の向きに対してベクトルＥｋの向きが右向きか左向きかの二値情報で表すこと、を特徴とする図形圧縮符号化方法。
【請求項２】
それぞれ互いに交差するＸ方向及びＹ方向のいずれかに沿う複数の要素線分の連鎖からなる図形を対象図形とし、画像内における前記対象図形を表すベクタ形式データを圧縮符号化する方法であって、
前記Ｘ方向の辺及び前記Ｙ方向の辺からなり前記対象図形を内側に含む最小の矩形である境界ボックスの形状及び前記画像における配置を表す境界ボックス情報を求めるステップと、
前記連鎖の予め定められた起点Ｐ１について、前記境界ボックスにおける所定の基準点を原点とした座標を求めるステップと、
前記対象図形を構成する前記要素線分の数Ｋを取得すると共に、前記連鎖の起点Ｐ１からｋ番目（ｋはＫ以下の任意の自然数である。）の前記要素線分を始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、１番目乃至Ｋ番目の前記要素線分について順番に前記ベクトルＥｋの長さＬｋ及び向きＡｋの情報を取得する図形情報抽出ステップと、
前記境界ボックス情報、前記起点Ｐ１の座標、前記要素線分の数Ｋ、並びにＫ個の前記ベクトルＥｋの前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化して前記対象図形の符号化データとする符号化ステップと、を有し、
前記図形情報抽出ステップは、任意の前記要素線分が前記境界ボックスの任意の一つの辺である第１の辺に重なると、後続の前記要素線分の終点が前記境界ボックスの前記第１の辺に隣接する辺である第２の辺に達するまでの間、前記第１の辺から遠ざかる向き及び前記第２の辺に近づく向きを順向き、また前記第１の辺に近づく向き及び前記第２の辺から遠ざかる向きを逆向きと定義し、前記向きＡｋを前記順向きか前記逆向きかの二値情報で表すこと、を特徴とする図形圧縮符号化方法。
【請求項３】
それぞれ互いに交差するＸ方向及びＹ方向のいずれかに沿う複数の要素線分の連鎖からなる図形を対象図形とし、画像内における前記対象図形を表すベクタ形式データを圧縮符号化する方法であって、
前記Ｘ方向の辺及び前記Ｙ方向の辺からなり前記対象図形を内側に含む最小の矩形である境界ボックスの形状及び前記画像における配置を表す境界ボックス情報を求めるステップと、
前記連鎖の予め定められた起点Ｐ１について、前記境界ボックスにおける所定の基準点を原点とした座標を求めるステップと、
前記対象図形を構成する前記要素線分の数Ｋを取得すると共に、前記連鎖の起点Ｐ１からｋ番目（ｋはＫ以下の任意の自然数である。）の前記要素線分を始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、１番目乃至Ｋ番目の前記要素線分について順番に前記ベクトルＥｋの長さＬｋ及び向きＡｋの情報を取得する図形情報抽出ステップと、
前記境界ボックス情報、前記起点Ｐ１の座標、前記要素線分の数Ｋ、並びにＫ個の前記ベクトルＥｋの前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化して前記対象図形の符号化データとする符号化ステップと、を有し、
前記図形情報抽出ステップは、３番目以降の前記要素線分の向きＡαについて、前記要素線分の向きＡα−１に対する前記向きＡαが前記要素線分の向きＡα−２に対する前記向きＡα−１と同一であれば非正則、また反対であれば正則と定義し、前記向きＡαを前記正則か前記非正則かの二値情報で表すこと、を特徴とする図形圧縮符号化方法。
【請求項４】
請求項１から請求項３のいずれか１つに記載の図形圧縮符号化方法において、
前記符号化ステップは、前記境界ボックスの任意の一つの辺に重なる前記要素線分の向きＡｋ及びその次の前記要素線分の向きＡｋ＋１の情報を符号化の対象から省略すること、を特徴とする図形圧縮符号化方法。
【請求項５】
請求項２から請求項４のいずれか１つに記載の図形圧縮符号化方法において、
前記符号化ステップは、１番目乃至Ｋ番目の前記要素線分についての前記向きＡｋの二値情報列をランレングス圧縮すること、を特徴とする図形圧縮符号化方法。
【請求項６】
請求項１から請求項５のいずれか１つに記載の図形圧縮符号化方法において、
前記符号化ステップは、前記連鎖の順に並ぶ前記長さＬｋからなるデータ列を順番にβ個（βは２以上の整数である。）ずつ区切って生成される複数のデータセグメントをそのデータの並びの種類ごとに集計して出現頻度が高いものほど短い符号を割り当てた符号化テーブルを作成し、前記長さＬｋを表す情報として前記対象図形の符号化データに、当該符号化テーブルと、当該符号化テーブルを用いて前記複数のデータセグメントを変換した可変長符号とを含めること、を特徴とする図形圧縮符号化方法。
【請求項７】
請求項１から請求項５のいずれか１つに記載の図形圧縮符号化方法において、
任意の前記長さＬｋは整数であり、
前記符号化ステップは、前記長さＬｋを表す情報として、前記長さＬｋのうち前記図形における最頻出長以外の長さＬＮＦＲについてだけ、当該長さＬＮＦＲと対応付けて当該長さＬＮＦＲの前記連鎖における出現位置の情報を含めること、を特徴とする図形圧縮符号化方法。
【請求項８】
請求項１から請求項７のいずれか１つに記載の図形圧縮符号化方法において、
前記図形は多角形であり、
前記符号化ステップは、前記連鎖の末尾の２つの前記要素線分の前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化の対象から省略すること、を特徴とする図形圧縮符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポリゴン又はポリラインを表すベクタ形式データを圧縮符号化する方法に関する。
【背景技術】
【０００２】
例えば、リモートセンシング分野における画像の解析では、衛星写真や航空写真等の画像をスペクトル情報やテクスチャ情報などの特徴が共通する画素からなる領域に分割することが行われる。そのような処理で生成される領域は、画像における当該領域の輪郭の形状及び位置で特定することができる。ここで、当該領域の輪郭は画素に対応する矩形の境界を辺とする多角形、つまりポリゴンで表され、領域の図形データとしてベクタ形式のポリゴンデータを生成することができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第４２３０１３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
衛星写真等の画像の領域分割で生成される領域は、複雑な形状となることが多く、またその数も大量となることが多い。そのため、個々の分割領域の図形データ及び、画像全体での図形データのサイズが巨大になるケースが多い。この傾向は、撮影機器の高性能化や記憶装置の大容量化により高解像度や広範囲の画像を取得し取り扱うことが可能になるにつれ顕著となる。
【０００５】
一方、図形データをネットワーク経由で伝送し利用することも広く行われ、データの迅速な転送が求められる。特に近年では、モバイル端末など帯域の限られたネットワークで接続された機器でのデータ利用も行われるようになっている。そのため、図形データのデータサイズの縮小が必要となる。
【０００６】
本発明は、上記問題点を解決するためになされたものであり、ポリゴン又はポリラインを表すベクタ形式の図形データの符号化に関し、圧縮効率の向上が図れる方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
（１）本発明に係る図形圧縮符号化方法は、それぞれ互いに交差するＸ方向及びＹ方向のいずれかに沿う複数の要素線分の連鎖からなる図形を対象図形とし、画像内における前記対象図形を表すベクタ形式データを圧縮符号化する方法であって、前記Ｘ方向の辺及び前記Ｙ方向の辺からなり前記対象図形を内側に含む最小の矩形である境界ボックスの形状及び前記画像における配置を表す境界ボックス情報を求めるステップと、前記連鎖の予め定められた起点Ｐ１について、前記境界ボックスにおける所定の基準点を原点とした座標を求めるステップと、前記対象図形を構成する前記要素線分の数Ｋを取得すると共に、前記連鎖の起点Ｐ１からｋ番目（ｋはＫ以下の任意の自然数である。）の前記要素線分を始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、１番目乃至Ｋ番目の前記要素線分について順番に前記ベクトルＥｋの長さＬｋ及び向きＡｋの情報を取得する図形情報抽出ステップと、前記境界ボックス情報、前記起点Ｐ１の座標、前記要素線分の数Ｋ、並びにＫ個の前記ベクトルＥｋの前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化して前記対象図形の符号化データとする符号化ステップと、を有し、前記図形情報抽出ステップは、２番目乃至Ｋ番目の前記要素線分についての前記向きＡｋを、ベクトルＥｋ−１の向きに対してベクトルＥｋの向きが右向きか左向きかの二値情報で表す。
【０００８】
（２）本発明に係る他の図形圧縮符号化方法は、それぞれ互いに交差するＸ方向及びＹ方向のいずれかに沿う複数の要素線分の連鎖からなる図形を対象図形とし、画像内における前記対象図形を表すベクタ形式データを圧縮符号化する方法であって、前記Ｘ方向の辺及び前記Ｙ方向の辺からなり前記対象図形を内側に含む最小の矩形である境界ボックスの形状及び前記画像における配置を表す境界ボックス情報を求めるステップと、前記連鎖の予め定められた起点Ｐ１について、前記境界ボックスにおける所定の基準点を原点とした座標を求めるステップと、前記対象図形を構成する前記要素線分の数Ｋを取得すると共に、前記連鎖の起点Ｐ１からｋ番目（ｋはＫ以下の任意の自然数である。）の前記要素線分を始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、１番目乃至Ｋ番目の前記要素線分について順番に前記ベクトルＥｋの長さＬｋ及び向きＡｋの情報を取得する図形情報抽出ステップと、前記境界ボックス情報、前記起点Ｐ１の座標、前記要素線分の数Ｋ、並びにＫ個の前記ベクトルＥｋの前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化して前記対象図形の符号化データとする符号化ステップと、を有し、前記図形情報抽出ステップは、任意の前記要素線分が前記境界ボックスの任意の一つの辺である第１の辺に重なると、後続の前記要素線分の終点が前記境界ボックスの前記第１の辺に隣接する辺である第２の辺に達するまでの間、前記第１の辺から遠ざかる向き及び前記第２の辺に近づく向きを順向き、また前記第１の辺に近づく向き及び前記第２の辺から遠ざかる向きを逆向きと定義し、前記向きＡｋを前記順向きか前記逆向きかの二値情報で表す。
【０００９】
（３）本発明に係るさらに他の図形圧縮符号化方法は、それぞれ互いに交差するＸ方向及びＹ方向のいずれかに沿う複数の要素線分の連鎖からなる図形を対象図形とし、画像内における前記対象図形を表すベクタ形式データを圧縮符号化する方法であって、前記Ｘ方向の辺及び前記Ｙ方向の辺からなり前記対象図形を内側に含む最小の矩形である境界ボックスの形状及び前記画像における配置を表す境界ボックス情報を求めるステップと、前記連鎖の予め定められた起点Ｐ１について、前記境界ボックスにおける所定の基準点を原点とした座標を求めるステップと、前記対象図形を構成する前記要素線分の数Ｋを取得すると共に、前記連鎖の起点Ｐ１からｋ番目（ｋはＫ以下の任意の自然数である。）の前記要素線分を始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、１番目乃至Ｋ番目の前記要素線分について順番に前記ベクトルＥｋの長さＬｋ及び向きＡｋの情報を取得する図形情報抽出ステップと、前記境界ボックス情報、前記起点Ｐ１の座標、前記要素線分の数Ｋ、並びにＫ個の前記ベクトルＥｋの前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化して前記対象図形の符号化データとする符号化ステップと、を有し、前記図形情報抽出ステップは、３番目以降の前記要素線分の向きＡαについて、前記要素線分の向きＡα−１に対する前記向きＡαが前記要素線分の向きＡα−２に対する前記向きＡα−１と同一であれば非正則、また反対であれば正則と定義し、前記向きＡαを前記正則か前記非正則かの二値情報で表す。
【００１０】
（４）上記（１）〜（３）に記載の図形圧縮符号化方法において、前記符号化ステップは、前記境界ボックスの任意の一つの辺に重なる前記要素線分の向きＡｋ及びその次の前記要素線分の向きＡｋ＋１の情報を符号化の対象から省略する構成とすることができる。
【００１１】
（５）上記（２）〜（４）に記載の図形圧縮符号化方法において、前記符号化ステップは、１番目乃至Ｋ番目の前記要素線分についての前記向きＡｋの二値情報列をランレングス圧縮する構成とすることができる。
【００１２】
（６）上記（１）〜（５）に記載の図形圧縮符号化方法において、前記符号化ステップは、前記連鎖の順に並ぶ前記長さＬｋからなるデータ列を順番にβ個（βは２以上の整数である。）ずつ区切って生成される複数のデータセグメントをそのデータの並びの種類ごとに集計して出現頻度が高いものほど短い符号を割り当てた符号化テーブルを作成し、前記長さＬｋを表す情報として前記対象図形の符号化データに、当該符号化テーブルと、当該符号化テーブルを用いて前記複数のデータセグメントを変換した可変長符号とを含める構成とすることができる。
【００１３】
（７）上記（１）〜（５）に記載の図形圧縮符号化方法において、任意の前記長さＬｋは整数であり、前記符号化ステップは、前記長さＬｋを表す情報として、前記長さＬｋのうち前記図形における最頻出長以外の長さＬＮＦＲについてだけ、当該長さＬＮＦＲと対応付けて当該長さＬＮＦＲの前記連鎖における出現位置の情報を含める構成とすることができる。
【００１４】
（８）上記（１）〜（７）に記載の図形圧縮符号化方法において、前記図形は多角形であり、前記符号化ステップは、前記連鎖の末尾の２つの前記要素線分の前記長さＬｋを表す情報及び前記向きＡｋを表す情報を符号化の対象から省略する構成とすることができる。
【発明の効果】
【００１５】
本発明によれば、ポリゴン又はポリラインを表すベクタ形式の図形データの符号化に関し、圧縮効率の向上が図れる。
【図面の簡単な説明】
【００１６】
【図１】画像を類似画素からなる領域に分割した結果の一例を示す模式図である。
【図２】領域分割で生成される輪郭ポリゴンの一例を示す模式図である。
【図３】符号化図形データファイルの概略の構造の一例を示す模式図である。
【図４】図形ヘッダに格納される情報の例を示す模式図である。
【図５】境界ボックスの一例を示す模式図である。
【図６】エッジ長テーブルの例を示す模式図である。
【図７】符号化図形データファイルの生成の概略のフロー図である。
【図８】図形データの生成処理の概略のフロー図である。
【図９】符号化の説明に用いるポリゴンの一例を示す模式図である。
【図１０】ポリゴンのエッジ長データ及びエッジ方向データの記述において、エッジの連鎖のうち末尾の２つについての記述を省略可能であることを説明する模式図である。
【図１１】最頻出エッジ長以外のエッジの出現位置を表す符号を説明するための図である。
【図１２】エッジ長パターンを表す符号を説明するための図である。
【図１３】「エッジ方向符号化ルールへの適合エッジ数」を記述する態様の他の適用例を説明するポリゴンの模式図である。
【図１４】エッジ数が４，６，８であるポリゴンの模式図である。
【図１５】上下左右以外の向きのエッジを有するポリゴンの符号化を説明するための図である。
【図１６】ポリラインを仮想ノードの追加によりポリゴン化する例を示す模式図である。
【図１７】ポリラインの部分ごとに境界ボックスを設定する例を示す模式図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態（以下実施形態という）である図形圧縮符号化方法について、図面に基づいて説明する。
【００１８】
本発明の図形圧縮符号化方法は、それぞれ互いに交差するＸ方向及びＹ方向のいずれかに沿う複数のエッジ（要素線分）の連鎖からなる図形を対象図形とし、画像内における対象図形を表すベクタ形式データを圧縮符号化する際に用いられる。当該方法は、Ｘ方向とＹ方向とが直交する場合に限られず適用可能であるが、本実施形態では、画像の水平方向をＸ方向、垂直方向をＹ方向とする。また、各方向の長さは、画素（ピクセル）数で定義することで整数値で表すことができる。画素は画像をＸ方向及びＹ方向に沿って格子状に区切ることで生成される矩形で定義され、例えば、正方形とすることができる。本実施形態では例えば、衛星写真や航空写真等の画像にて類似画素からなる領域の輪郭を表すポリゴンを圧縮符号化の対象図形とする。図１は、画像２０を類似画素からなる領域に分割した結果の一例を示す模式図であり、画像はサイズや形状が様々なポリゴン２１である多数の領域に分割されている。
【００１９】
本実施形態の符号化方法は、コンピュータプログラムに表され、コンピュータは当該プログラムを実行して、入力データとして与えられるベクタ形式のポリゴンデータを圧縮符号化し、出力データとしてポリゴンの符号化データを生成する。以下、本発明の図形圧縮符号化方法を実行するコンピュータを便宜上、符号化装置１として、実施形態を説明する。
【００２０】
以下に説明する例では、図１に示したような複数の輪郭ポリゴンを含み得る画像を入力データとする。例えば、入力データは、画像に含まれるポリゴンそれぞれについて、当該ポリゴンのノード（頂点）の座標群を記述したものとすることができる。図２は、図１に示したような領域分割で生成される輪郭ポリゴンの一例を示す模式図であり、同図に示すポリゴン２２は８個のノードＰ１〜Ｐ８を有する。ポリゴン２２の輪郭は画素境界に沿って定義され、ポリゴン２２のノードは画素境界が交差する格子点上に位置する。画像上での各ノードの位置は、画像の左上隅を原点とし水平方向右向きをＸ軸の正の向き、垂直方向下向きをＹ軸の正の向きとして各軸方向の位置を画素数で数えた一対の座標値（Ｘ座標、Ｙ座標）で表される。
【００２１】
ポリゴンの輪郭はＸ方向又はＹ方向に隣接する一対のノードを結ぶ線分をエッジとし、当該エッジの連鎖で構成される。例えば、ポリゴン２２の境界は、線分ＰｋＰｋ＋１（ｋ＝１〜７）及びＰ８Ｐ１の８本のエッジの連鎖からなる。ちなみに、ポリゴンの輪郭は閉じた図形であるので、エッジの連鎖は、任意のノードを起点として定義することができ、当該連鎖は輪郭を時計回り又は反時計回りに一巡し、連鎖の終点は起点としたノードに一致する。
【００２２】
なお、ポリゴンは、ノードを図２に示した輪郭ポリゴンの例のような画素境界の格子点ではなく、画素の中心に設定して定義したものであっても、本発明の圧縮符号化方法を適用することができる。
【００２３】
ここで、画素値の定義などにおいては画素の座標は通常、画素の中心位置を記述しており、この中心位置の座標を画素数に応じた整数値で表すこととすると、上述の格子点の座標は整数値とはならない。つまり、画素の中心位置に対し、当該画素の四隅の座標は、Ｘ方向、Ｙ方向に±０．５ずれた値となる。ノードの座標の情報量を圧縮して格納する場合に、このような実数形式による数値表現は好ましくない。そこで、画素の中心座標を整数で表現する場合には、ノードの座標値（ｐＸ，ｐＹ）に対し、ｐＸ’＝ｐＸ＋0.5，ｐＹ’＝ｐＹ＋0.5のようにオフセット値0.5を加算する変換を行う。これにより、ノードの座標は０以上の整数値で表現可能となる。これにより、±０．５ずれた値のままでは例えば通常、浮動小数４バイトまたは８バイトで表現する必要のあるノード座標の情報が整数２バイトで表現可能となる。なお、実際の座標を算出する際には、逆の演算、つまりｐＸ＝ｐＸ’−0.5等を行えばよい。
【００２４】
符号化装置１は、入力データに表されるポリゴンを、エッジの長さの情報と方向の情報とに分解する。そして符号化装置１は、それぞれエッジの連鎖に従った順で並ぶ長さ情報の列と方向情報の列とを符号化する。
【００２５】
以下の説明にて、必要に応じてｎビットのビット列をｂ（ｎ）又は類似の記号で表し、ｎ１ビットの列の後にｎ２ビットの列が続いたビット列は、ｂ（ｎ１）ｂ（ｎ２）やｂ（ｎ１，ｎ２）といった記号で表す。なお、当該記号は基本的には、単にビット列を構成する複数符号の区切りを理解しやすくするために用いるものであり、特定の符号を表すものではない。
【００２６】
［Ａ］符号化図形データファイルの構造
図３は符号化装置１から出力される符号化図形データファイル３の概略の構造の一例を示す模式図である。当該ファイルには、先頭にファイルヘッダ４となるデータブロックが置かれ、これに続いて、画像に含まれる対象図形それぞれに対応する図形データ５のブロックが格納される。
【００２７】
（Ａ−１）ファイルヘッダ
ファイルヘッダ４には例えば、数値の表現形式に関する設定、ファイルに含まれる図形データの数、及びエッジの連鎖の周回方向を記述する。
【００２８】
（Ａ−１−１）数値の表現形式に関する設定情報
数値の表現形式に関する設定情報は具体的には、固定長／可変長の種別を表す１ビットの識別情報と、これに続く所定ビット数の付属情報とで構成される。数値表現に固定長形式を用いる場合には、識別情報に例えば値“１”を設定し、付属情報に固定長の大きさを示すビット数（又はバイト数）を記述する。一方、データ長を所定の単位長ｎＵずつ変化させる可変長形式を数値表現に用いる場合には、識別情報に例えば値“０”を設定し、付属情報には、各可変長データにて単位長を記述するために用いるビット数（単位長記述ビット数）ｎＡを設定する。
【００２９】
なお、単位長記述ビット数に関しては二進法での表記を、一般的な二進法表記から１を減じたものとする。例えば、単位長記述ビット数“８”は、通常の二進数では“１０００”となり４ビット必要となるところ、本実施形態の表記では“１１１”となり３ビットで表現される。なお、当該表記では、十進数“１”が二進数“０００”で表されるが、単位長記述ビット数は１以上であり、０となることはないので支障は無い。
【００３０】
ここで、可変長形式の数値表示の例を示す。可変長形式の数値は、単位長を示すビット列（単位長記述ビット列）ｂ（ｎＡ）と、単位長の整数倍（倍率γ）のビット数からなり表示対象の数値（表示数値）を表すビット列（数値記述ビット列）ｂ（γ・ｎＵ）との組み合わせで表現される。上述の可変長形式の付属情報にてｎＡ＝３を設定されたとすると、３ビットで表示可能な二進数“０００”〜“１１１”は、十進数の１〜８を表す。つまり、単位長は１〜８ビットの範囲で指定できる。この場合において単位長ｎＵを２とすると、単位長記述ビット列ｂ（ｎＡ）は“００１”となり、例えば、表示数値“３”は、その数値記述ビット列ｂ（ｎＵ）である“１１”を単位長記述ビット列ｂ（ｎＡ）である“００１”に続けたビット列ｂ（ｎＡ，ｎＵ）である“００１１１”と表される。また、表示数値“４”は、１つの単位長のビット列で表現可能な上限値“３”を超えるため、数値記述ビット列は単位長の２倍である４ビットを用いて表記する。具体的には、表示数値が２ビットで記述可能な３を超えたことを示すビット列“００”に、４から３を除いた残りである１を示すビット列“０１”を続ける。つまり、表示数値“４”は、単位長記述ビット列“００１”に数値記述ビット列ｂ（２ｎＵ）として“０００１”を続けたビット列“００１０００１”と表される。また、表示数値“７”については、７から３を除いても残りが４となり依然として１つの単位長のビット列で表現可能な上限値“３”を超えるため、そのことを示すビット列“００”を追加し、数値記述ビット列を単位長の３倍である６ビットからなる“０００００１”とする。つまり表示数値“７”は、可変長形式ではビット列ｂ（ｎＡ，３ｎＵ）＝“００１０００００１”と表される。ちなみに、可変長形式では表示数値“０”を扱わないこととすることにより、復号時には、ビット列から単位長記述ビット数分を取り出してまず単位長を取得し、しかる後、続くビット列を単位長ずつ読み込んで、１を含むビット列が現れると、そこが数値記述ビット列の末尾であることが判る。つまり、上述の可変長形式の数値表示は、明示的には数値記述ビット列の長さの情報を与えられないが数値表示の区切りを検出可能であり、復号可能である。
【００３１】
（Ａ−１−２）ファイルに含まれる図形データの数
ファイルに含まれる図形データの数は、ファイルヘッダ４に続く図形データ５のブロック数であり、本実施形態では基本的に画像に含まれる図形の数となる。ちなみに、この数値は上述の数値の表現形式の設定情報に従って、固定長又は可変長で記述される。
【００３２】
（Ａ−１−３）エッジの連鎖の周回方向
既に述べたようにポリゴンはエッジの連鎖として捉えることができ、エッジの連鎖の周回方向は、当該連鎖の順序を時計回りに定義するか反時計回りに定義するかを表す。ちなみに、連鎖の起点から終点に向かう際に、ポリゴン内部が右側に位置する場合が時計回りであり、左側に位置する場合が反時計回りである。
【００３３】
周回方向は二者択一であるので１ビットで表現でき、例えば、時計回りをビット値“０”、反時計回りをビット値“１”とすることができる。
【００３４】
エッジの連鎖の周回方向は、ここで述べるファイルヘッダ４にて設定できるほか、個々の図形データ５でも設定でき、符号化図形データファイル３に格納される全ポリゴンに共通に設定する場合には、ファイルヘッダ４にて設定され、ポリゴンごとに設定する場合には図形データ５にて設定される。
【００３５】
（Ａ−２）図形データ
図３には図形データ５の概略の構造が示されている。図形データ５のブロックには、先頭に図形ヘッダ６となるデータブロックが置かれ、これに続いて、エッジ長テーブル７、出現位置テーブル８、エッジ長データ９及びエッジ方向データ１０のブロックが格納される。
【００３６】
（Ａ−２−１）図形ヘッダ
図４は図形ヘッダ６に格納される情報の例を示す模式図である。図形ヘッダ６には例えば、存在範囲データ、エッジ（ノード）数、起点ノード位置、及びエッジの連鎖の周回方向を示す情報が格納され、さらに、エッジ長情報として、エッジ長識別フラグ、エッジ長符号化モード、エッジ長テーブル変更フラグ、及び出現位置テーブル変更フラグが格納され、また、エッジ方向情報として、エッジ方向符号化ルール、ランレングス記述ビット数、及びエッジ方向符号化オプションが格納される。なお、図形ヘッダ６内におけるこれらの情報の格納順序は任意に定義することができる。また、これら情報を表す数値は、上述のファイルヘッダ４に設定された数値の表現形式に従って記述される。
【００３７】
（Ａ−２−１−１）存在範囲データ
存在範囲データは対象図形の存在範囲を規定する情報である。対象図形の存在範囲は、Ｘ方向及びＹ方向にそれぞれ平行な２対の辺からなり当該対象図形を内側に含む最小の矩形で規定され、以降、当該矩形を境界ボックスと称する。
【００３８】
図５は境界ボックスの一例を示す模式図であり、ポリゴン２３に外接する矩形が境界ボックス２４である。符号化装置１は、入力データとして与えられる対象図形のデータから、境界ボックスの形状及び画像における配置を表す境界ボックス情報を求め、これを存在範囲データとして図形ヘッダ６に格納する。
【００３９】
具体的には、符号化装置１は境界ボックス情報（又は存在範囲データ）として、境界ボックスの所定の基準点の画像内での座標、並びに境界ボックスの高さ及び幅を求める。例えば、基準点は、境界ボックスの左上の頂点ＰＢ０とすることができる。対象図形のノードのＸ座標の最小値、最大値をそれぞれＸＰｍｉｎ，ＸＰｍａｘとし、Ｙ座標の最小値、最大値をそれぞれＹＰｍｉｎ，ＹＰｍａｘとすると、ＰＢ０の座標は（ＸＰｍｉｎ，ＹＰｍｉｎ）で与えられ、境界ボックスの高さΔＹ，幅ΔＸはそれぞれＹＰｍａｘ−ＹＰｍｉｎ、ＸＰｍａｘ−ＸＰｍｉｎで与えられる。
【００４０】
（Ａ−２−１−２）エッジ（ノード）数
エッジ（ノード）数は、対象図形を構成するエッジ（ノード）の個数を記述する。
【００４１】
（Ａ−２−１−３）起点ノード位置
起点ノード位置は、対象図形のノードのうちエッジの連鎖の起点とするものの座標であり、境界ボックスの基準点ＰＢ０を原点としたＸ，Ｙ座標値で表される。対象図形がポリラインである場合は起点はポリラインの両端のいずれか一方となるが、対象図形がポリゴンである場合は、任意のノードを起点にすることが可能である。しかしながら、後述するエッジ方向データの圧縮符号化では、起点は境界ボックスの辺上に設定することが好適であるので、起点を境界ボックスの上下左右の辺のいずれの上に設定するか制限を課してもよい。この場合、起点のＸ，Ｙ座標値のいずれかは上述の境界ボックス情報（存在範囲データ）から算出されるので、図形ヘッダ６に記述する情報から省略することができる。
【００４２】
（Ａ−２−１−４）エッジの連鎖の周回方向
上述したように、エッジの連鎖の周回方向は、ポリゴンごとに設定する場合に、ファイルヘッダ４での設定に代えて、図形ヘッダ６にて設定される。
【００４３】
（Ａ−２−１−５）エッジ長情報
（Ａ−２−１−５−１）エッジ長識別フラグ
エッジ長識別フラグは、対象図形を構成する全てのエッジが同一の長さであるか否かを示すフラグであり、１ビットで表現可能である。例えば、全エッジが同じ長さである場合、ビット値“１”とし、異なる長さのエッジが存在する場合、ビット値“０”とすることができる。全エッジが同じ長さである場合、当該フラグに続いて、例えば、可変長形式で、当該エッジ長を記述する一方、エッジ長テーブル７、出現位置テーブル８及びエッジ長データ９といった他の箇所でのエッジ長に関する情報は省略される。
【００４４】
（Ａ−２−１−５−２）エッジ長符号化モード
本実施形態では後述するように、エッジ長の符号化に関して２種類の方法を用意しており、エッジ長符号化モードはそれらのうちいずれを用いるかに関する。具体的には、図形ヘッダ６に１ビットの情報で当該モードを記述し、２種類のモードのうち、「最頻出のエッジ長以外の出現位置」を記述する方法を用いるモードをビット値“０”、「連続エッジの出現パターン」を記述する方法を用いるモードをビット値“１”とする。「連続エッジの出現パターン」を記述する方法をとった場合、当該フラグに続いて、例えば、可変長形式で、出現パターンとして扱うエッジ数βを記述する。
【００４５】
（Ａ−２−１−５−３）エッジ長テーブル変更フラグ
エッジ長テーブル変更フラグは、１つ前の図形データ５で使用したエッジ長テーブルをそのまま使用できるか否かを表すフラグであり、そのまま使用する場合には「変更なし」を示す値に設定され、そうでなければ「変更」を示す値に設定される。当該フラグは１ビットで表現可能であり、例えば、「変更なし」をビット値“０”、「変更」をビット値“１”とする。図形データ５は図形ヘッダ６にて「変更なし」に設定されると、当該図形データ５におけるエッジ長テーブル７の記述を省略される。
【００４６】
（Ａ−２−１−５−４）出現位置テーブル変更フラグ
出現位置テーブル変更フラグは１つ前の図形データ５で使用した出現位置テーブルをそのまま使用できるか否かを表すフラグであり、そのまま使用する場合には「変更なし」を示す値に設定され、そうでなければ「変更」を示す値に設定される。当該フラグは１ビットで表現可能であり、例えば、「変更なし」をビット値“０”、「変更」をビット値“１”とする。図形データ５は図形ヘッダ６にて「変更なし」に設定されると、当該図形データ５における出現位置テーブル８の記述を省略される。
【００４７】
（Ａ−２−１−６）エッジ方向情報
（Ａ−２−１−６−１）エッジ方向符号化ルール
本実施形態では後述するように、隣り合う一対のエッジにて一方のエッジに対する他方の向きは一方のエッジに交差する軸方向に沿った２つの向き（右向き、左向き）に制限されるという特徴か、エッジ方向に現れる規則性に関する特徴を、エッジ方向の符号化に際し「エッジ方向符号化ルール」として利用する。ここで、エッジ方向に現れる規則性に関する特徴は２種類ある。よって、エッジ方向符号化ルールは３種類設定され、図形ヘッダ６に、いずれのエッジ方向符号化ルールを用いるかを記述する。具体的には、図形ヘッダ６に１ビットの情報で、向きが左右の２通りに制限されることについてのエッジ方向符号化ルールを用いるか、エッジ方向に現れる規則性に関するエッジ方向符号化ルール（規則性エッジ方向符号化ルール）を用いるかを記述する。例えば、向きが左右の２通りに制限されることについてのエッジ方向符号化ルールを用いる場合をビット値“０”、規則性エッジ方向符号化ルールを用いる場合をビット値“１”とする。
【００４８】
規則性エッジ方向符号化ルールを用いる場合はさらに、続く１ビットの情報で規則性の種類を記述し、後述する２種類の規則性のうち、「回転規則」を適用する場合をビット値“０”、「ＬＲ規則」を適用する場合をビット値“１”とする。
【００４９】
なお、向きが左右の２通りに制限されることについてのエッジ方向符号化ルールを用いる場合は、エッジ方向情報のうち、ここで述べた規則性の種類を記述するビット、及び以下に述べる「ランレングス記述ビット数」、「エッジ方向符号化オプション」の記述は不要であり省略される。
【００５０】
（Ａ−２−１−６−２）ランレングス記述ビット数
本実施形態では後述するように、エッジ方向の符号化に際し、規則性エッジ方向符号化ルールを用いる場合は、エッジの連鎖のうち規則性に適合する部分におけるエッジの連続本数を適合エッジ数としてカウントし、また適合しない部分におけるエッジの連続本数を非適合エッジ数としてカウントし、ランレングス圧縮に利用する。ランレングス記述ビット数は、適合エッジ数と非適合エッジ数の記述に用いるビット数をそれぞれ設定する。
【００５１】
なお、全てのエッジが適合している場合は、エッジ方向データ１０の記述を省略することができ、ランレングス圧縮も不要であるため、適合エッジ数、非適合エッジ数ともに当該ビット数として“０”を設定することにする。また、非適合エッジ数の連続本数が１本のみの場合は、非適合エッジ数に関する当該ビット数は“１”に設定する。
【００５２】
（Ａ−２−１−６−３）エッジ方向符号化オプション
本実施形態では後述するように、規則性エッジ方向符号化ルールを用いたエッジ方向の符号化に関して以下の２種類のオプションを用意している。
（ｉ）「境界ボックスを単位としたエッジ方向符号化ルールへの適合エッジ数」を記述する。
（ｉｉ）「適合エッジ数の規定値への合致度」を記述する。
【００５３】
エッジ方向符号化オプションはこれらのうち用いるものがいずれであるかに関する。具体的には、図形ヘッダ６に２ビットの情報で当該オプションの選択を記述する。例えば、これら両方共を適用しない場合は当該２ビットに“００”を記述し、（ｉ）のみ適用する場合は“０１”、（ｉｉ）のみ適用する場合は“１０”、両方を適用する場合は“１１”を記述する。
【００５４】
（Ａ−２−２）エッジ長テーブル
図６はエッジ長テーブル７の例を示す模式図である。エッジ長テーブル７は対象図形に現れるエッジ長と当該エッジ長を表す符号とを対応付ける変換テーブルである。例えば、対象図形に現れる複数種類のエッジ長を順番にテーブルに格納し、格納位置の順番をエッジ長を表す符号として対応付けることができる。格納位置の順番の最大値は対象図形を構成するエッジ長の種類数で定まり、基本的に、対象図形におけるエッジ長の最大値以下となるので、格納位置の順番を符号として用いることでデータ圧縮を図ることができる。また、エッジ長の出現頻度に応じて格納順序を定めることで、出現頻度が高いエッジ長ほど小さな順位とし、符号化に際し例えば、当該順位を可変長形式で表現したり、順位に応じてハフマン符号を割り当てたりすることで圧縮効率を高めることができる。
【００５５】
エッジ長テーブル７は、上述したように、図形ヘッダ６のエッジ長テーブル変更フラグに「変更」が設定された場合に記述される。当該変更の態様は複数あり、テーブルの入れ替えモードで当該態様を指定する。例えば、テーブルの入れ替えモードはエッジ長テーブル７の先頭に設定される。テーブルの入れ替えモードは例えば、エッジ長テーブル７の内容を全て入れ替える場合は値“０”、一部のエッジ長を入れ替える場合は値“１”、エッジ長のテーブル内での順番を入れ替える場合は値“２”とし、これらの値を２ビットを用いて記述する。
【００５６】
入れ替えモードが「全て入れ替え」である場合、入れ替えモードを記述するビット列に続いて、テーブルに登録するエッジ長の個数を例えば、可変長形式で記述する。当該個数は基本的に、対象図形に含まれるエッジ長の種類数で与えられる。そして、当該個数の後に、当該個数分のエッジ長に関するレコードを記述する。当該レコードにはエッジ長が可変長形式で記述される。
【００５７】
入れ替えモードが「一部入れ替え」である場合、入れ替えモードを記述するビット列に続いて、入れ替えるエッジ長の個数を例えば、可変長形式で記述する。そして、テーブル内の入れ替え位置と、当該位置に新たに格納するエッジ長とを含むレコードを、入れ替え個数分、順番に例えば可変ビット長で記述する。
【００５８】
入れ替えモードが「順番の入れ替え」である場合、入れ替えモードを記述するビット列に続いて、順番を入れ替えるエッジ長対の個数を例えば、可変長形式で記述する。そして、テーブル内での入れ替えるエッジ長の位置の対を含むレコードを、入れ替える対の数だけ順番に例えば可変ビット長で記述する。
【００５９】
ちなみに、エッジ長符号化モードにて「連続エッジの出現パターン」を記述する方法を設定された場合、個々のエッジ長に代えて、エッジ長符号化モードで設定した連続する所定個数のエッジ群におけるエッジ長の並び（エッジ長パターン）を単位として符号化する。この場合には、エッジ長テーブル７に代えて、エッジ長のパターンテーブルが記述される。パターンテーブルの構成は基本的にエッジ長テーブル７と同様とすることができる。
【００６０】
この点に関し、或る図形データ５において、エッジ長符号化モードが、１つ前の図形データ５と異なる場合は、図形ヘッダ６に記述するエッジ長テーブル変更フラグは「変更」に設定され、テーブルの入れ替えモードは「全て入れ替え」に設定される。
【００６１】
（Ａ−２−３）出現位置テーブル
出現位置テーブル８は、エッジ長符号化モードとして「最頻出のエッジ長以外の出現位置」を記述する方法を用いる場合に関し、対象図形に現れる最頻出エッジ長（ＬＦＲと表す。）以外のエッジ長（ＬＮＦＲと表す。）の出現位置と当該出現位置を表す符号とを対応付ける変換テーブルである。出現位置テーブル８は、図６を用いて上述したエッジ長テーブル７と基本的に同様の構造とすることができる。
【００６２】
例えば、或るＬＮＦＲの出現位置は、後述するように、エッジの連鎖の順に並べたエッジ長の数列での先行するＬＮＦＲから距離で定義することができる。このように、エッジの連鎖の順に並べたエッジ長の数列上での先頭など基準位置からの絶対座標ではなく、当該数列内のＬＮＦＲ間の位置の差分という相対座標で出現位置を表現することで、その種類を少なくすることができ、基本的に、当該種類は対象図形におけるエッジ数Ｋより少なくなる。
【００６３】
例えば、対象図形に現れる複数種類の当該出現位置の値を順番にテーブルに格納し、格納位置の順番を当該出現位置の値を表す符号として対応付けることができる。上述のように出現位置の値の種類が少なくなるので、格納位置の順番を符号として用いることでデータ圧縮を図ることができる。また、出現位置の値の出現頻度に応じて格納順序を定めることで、出現頻度が高い出現位置の値ほど小さな順位とし、符号化に際し例えば、当該順位を可変長形式で表現したり、順位に応じてハフマン符号を割り当てたりすることで圧縮効率を高めることができる。
【００６４】
具体的には、エッジの連鎖の順に並べたエッジ長の数列での最頻出エッジ長以外のエッジ長ＬＮＦＲの順番をξｉ（ここでｉは１≦ｉ≦ｉｍａｘなる整数であり、ｉｍａｘはＬＮＦＲの個数である。）と表し、またξ０＝０とすると、ＬＮＦＲの出現位置はξｉ−ξｉ−１で表現される。出現位置テーブル８によりξｉ−ξｉ−１とそれを表す符号（Ξｉと表す。）との対応関係が定義される。
【００６５】
出現位置テーブル８は、上述したように、図形ヘッダ６の出現位置テーブル変更フラグに「変更」が設定された場合に記述される。当該変更の態様は複数あり、テーブルの入れ替えモードで当該態様を指定する。例えば、テーブルの入れ替えモードは出現位置テーブル８の先頭に設定される。テーブルの入れ替えモードは例えば、出現位置テーブル８の内容を全て入れ替える場合は値“０”、一部の出現位置の値を入れ替える場合は値“１”、出現位置の値のテーブル内での順番を入れ替える場合は値“２”とし、これらの値を２ビットを用いて記述する。
【００６６】
入れ替えモードが「全て入れ替え」である場合、入れ替えモードを記述するビット列に続いて、テーブルに登録する出現位置の個数を例えば、可変長形式で記述する。そして、当該個数の後に、当該個数分の出現位置に関するレコードを記述する。当該レコードには出現位置の値が可変長形式で記述される。
【００６７】
入れ替えモードが「一部入れ替え」である場合、入れ替えモードを記述するビット列に続いて、入れ替える出現位置の個数を例えば、可変長形式で記述する。そして、テーブル内の入れ替え位置と、当該位置に新たに格納する出現位置の値とを含むレコードを、入れ替え個数分、順番に例えば可変ビット長で記述する。
【００６８】
入れ替えモードが「順番の入れ替え」である場合、入れ替えモードを記述するビット列に続いて、順番を入れ替える出現位置の値の対の個数を例えば、可変長形式で記述する。そして、テーブル内にて入れ替える出現位置のテーブル内での位置の対を含むレコードを、入れ替える対の数だけ順番に例えば可変ビット長で記述する。
【００６９】
（Ａ−２−４）エッジ長データ
エッジ長データ９は、対象図形のエッジの連鎖に従って並ぶエッジ長の列を、図形ヘッダ６のエッジ長符号化モードで設定された手法で符号化したデータである。なお、エッジ長データ９は、エッジ長識別フラグに基づいて、対象図形全体で同一のエッジ長でない場合のみ記述される。
【００７０】
（Ａ−２−５）エッジ方向データ
エッジ方向データ１０は、対象図形のエッジの連鎖に従って並ぶエッジ方向の情報を、図形ヘッダ６のエッジ方向情報の設定内容に基づいて符号化したデータである。なお、上述したように、全てのエッジが規則性エッジ方向符号化ルールに適合している場合にはエッジ方向データ１０は記述を省略される。
【００７１】
［Ｂ］図形データの生成の全体的な説明
図７は符号化図形データファイル３の生成の概略のフロー図である。
【００７２】
符号化装置１は、符号化対象の図形ファイルを入力されると、ファイルヘッダ４を生成した後（ステップＳ２）、画像の対象図形ごとに図形データ５を作成する。図形データ５の生成開始に際し、カウンタＩを初期値“０”に設定する（ステップＳ４）。
【００７３】
符号化装置１は、カウンタＩを１ずつインクリメントし（ステップＳ６）Ｉ番目の図形データ５を生成する処理（ステップＳ１０）を反復する。当該処理の反復は、Ｉが画像における符号化の対象図形の総数Ｉｍａｘ以下である間、継続され（ステップＳ８にて「Ｙｅｓ」の場合）、ＩがＩｍａｘを超えると当該画像についての符号化図形データファイル３の生成は終了する（ステップＳ８にて「Ｎｏ」の場合）。
【００７４】
図８は図形データ５の生成処理Ｓ１０の概略のフロー図である。また、図９はポリゴンの一例を示す模式図である。図８のフロー図、並びに図９に示されるポリゴン２３を用い、図形データ５の生成について説明する。
【００７５】
符号化装置１は、入力データとして与えられる対象図形のデータから、境界ボックス情報を求める（ステップＳ１２）。また、符号化装置１は、エッジの連鎖の予め定められた起点Ｐ１についての境界ボックスの基準点ＰＢ０を原点とした座標値である起点ノード位置を求める（ステップＳ１４）。
【００７６】
さらに、符号化装置１は、入力データとして与えられる対象図形のデータから、当該対象図形を構成するエッジの数Ｋを取得する。また、エッジの連鎖の起点Ｐ１からｋ番目（ｋはＫ以下の任意の自然数である。）のエッジを始点がＰｋであり終点がＰｋ＋１であるベクトルＥｋとして、符号化装置１は、１番目乃至Ｋ番目のエッジについて順番にベクトルＥｋの長さＬｋ及び向きＡｋの情報を取得する（図形情報抽出ステップＳ１６）。
【００７７】
そして、符号化装置１は  境界ボックス情報、起点ノード位置、エッジの数Ｋ、並びにＫ個のベクトルＥｋの長さＬｋを表す情報及び向きＡｋを表す情報を符号化する（符号化ステップＳ１８）。符号化装置１は、境界ボックス情報、起点ノード位置及びエッジの数Ｋに関する符号化データを図形ヘッダ６に格納する。また、長さＬｋを表す情報の符号化にてエッジ長テーブル７、出現位置テーブル８及びエッジ長データ９が生成され、向きＡｋを表す情報の符号化によりエッジ方向データ１０が生成される。
【００７８】
本実施形態では、ポリゴン２３を構成するＫ本（図９の例ではＫ＝５０）のエッジのうち境界ボックスの上辺に位置するものの右側のノードを起点Ｐ１に設定し、エッジの連鎖の周回方向は反時計回りに設定する。なお、境界ボックスの上辺に複数のエッジが存在する場合には、それらのうち最も左側のエッジの右側ノードを起点Ｐ１とする。
【００７９】
ここで、境界ボックスの上辺は対象図形にてＹ座標が０になるので、境界ボックスの上辺に起点を設定することで、図形ヘッダ６に格納される起点ノード位置のＹ座標の記述が不要となる。境界ボックスの上辺に複数のエッジが存在する場合には、それらのうち最も左側のエッジを連鎖の先頭として選択することで、起点のＸ座標が小さくなり、起点ノード位置のデータビット数の抑制に資する。
【００８０】
符号化装置１は、起点ノード位置と、ファイルヘッダ４又は図形ヘッダ６に設定されたエッジの連鎖の周回方向とに基づいて、エッジの連鎖順序を求める。
【００８１】
ポリゴン２３のＫ個のノードを起点Ｐ１から反時計回りに順にＰ２，Ｐ３，…，ＰＫとすると、エッジの連鎖にてｋ番目はエッジＰｋＰｋ＋１（ここでｋはＫ以下の任意の自然数である。）となる。ここで、ＰＫ＋１＝Ｐ１である。
【００８２】
Ｐｋの座標は入力データのポリゴンデータで与えられ、当該データに基づいてエッジＥｋの長さＬｋ及びＡｋを求めることができる。
【００８３】
符号化装置１は全てのｋについてのＬｋが同一であるか否かを調べ、同一である場合は、図形ヘッダ６に格納されるエッジ長識別フラグの値を“１”に設定し、既に述べたように、当該フラグに続いて、例えば、Ｌｋを記述する。この場合、図形データ５にエッジ長テーブル７、出現位置テーブル８及びエッジ長データ９を記述しないので、符号化装置１におけるそれらの生成処理は省略される。
【００８４】
向きＡｋを表す情報に関して、２番目乃至Ｋ番目のエッジについての向きＡｋは、ベクトルＥｋ−１の向きに対してベクトルＥｋの向きが右向きか左向きかの二値情報で表すことができる。つまり、一般にはベクトルの向きとしてＸ軸、Ｙ軸それぞれの正負両方向の４通りがあり、その表現には２ビットを要するところ、ベクトルＥｋの向きは１つ前のベクトルＥｋ−１との関係から２つに制限されるので１ビットで表現でき、符号化データのデータ量圧縮が可能である。さらに、本実施形態では、ポリゴンの性質などを利用したエッジ方向符号化ルールやエッジ方向符号化オプションを符号化に適用して一層のデータ圧縮を可能とする態様を説明する。
【００８５】
［Ｃ］エッジ長テーブルの生成
符号化装置１は上述したように全てのｋについてのＬｋが同一であるか否かを調べる。その結果、Ｌｋに複数種類の値が存在する場合には、符号化装置１は各Ｌｋの出現頻度を求める。符号化装置１は、出現頻度順に並べたＬｋからなる数列を、同じ画像にて現ポリゴンの１つ前に処理したポリゴンで求めた当該数列と比較して、図形ヘッダ６に格納するエッジ長テーブル変更フラグの値を設定する。具体的には、同じ数列が得られた場合は、エッジ長テーブル変更フラグを「変更なし」に設定する。この場合、上述したように現ポリゴンについてのエッジ長テーブル７は省略される。現ポリゴンと先行ポリゴンとでＬｋの上述の数列に違いがある場合は、符号化装置１はエッジ長テーブル変更フラグを「変更」に設定すると共に、エッジ長テーブル７の記述内容を生成する。具体的には、符号化装置１は、数列の相違箇所に基づいて、エッジ長テーブル７に記述する入れ替えモードを設定し、当該モードに対応した入れ替え内容の記述を生成する。
【００８６】
なお、エッジ長符号化モードを「連続エッジの出現パターン」を記述するモードとする場合には、エッジ長テーブル７に代えてエッジ長のパターンテーブルが用いられるが、当該パターンテーブルもエッジ長テーブル７と基本的に同様にして生成される。
【００８７】
ここで、符号化装置１は、符号化図形データファイル３における図形データ５の格納順序を、エッジ長テーブル変更フラグが「変更なし」となる場合が多くなるように設定することができ、これにより、符号化図形データファイル３全体にてエッジ長テーブル７に使用するデータ量を減らすことができる。
【００８８】
［Ｄ］出現位置テーブルの生成
符号化装置１は（ξｉ−ξｉ−１）の各値の出現頻度を求める。符号化装置１は、出現頻度順に並べた（ξｉ−ξｉ−１）の値からなる数列を、同じ画像にて現ポリゴンの１つ前に処理したポリゴンで求めた当該数列と比較して、図形ヘッダ６に格納する出現位置テーブル変更フラグの値を設定する。具体的には、同じ数列が得られた場合は、出現位置テーブル変更フラグを「変更なし」に設定する。この場合、上述したように現ポリゴンについての出現位置テーブル８は省略される。現ポリゴンと先行ポリゴンとで（ξｉ−ξｉ−１）の上述の数列に違いがある場合は、符号化装置１は出現位置テーブル変更フラグを「変更」に設定すると共に、出現位置テーブル８の記述内容を生成する。具体的には、符号化装置１は、数列の相違箇所に基づいて、出現位置テーブル８に記述する入れ替えモードを設定し、当該モードに対応した入れ替え内容の記述を生成する。
【００８９】
ここで、符号化装置１は、符号化図形データファイル３における図形データ５の格納順序を、出現位置テーブル変更フラグが「変更なし」となる場合が多くなるように設定することができ、これにより、符号化図形データファイル３全体にて出現位置テーブル８に使用するデータ量を減らすことができる。
【００９０】
［Ｅ］エッジ長データの生成
エッジ長データ９はエッジ長符号化モードに応じた方法で生成される。ここで、エッジ長符号化モードは、画像内の複数の対象図形に対して、例えばユーザが予め定めた１種類に固定することもできるし、対象図形ごとに別々に設定することもできる。本実施形態の符号化装置１は、２種類のエッジ長符号化モードそれぞれで、対象図形を符号化して、圧縮効率が高いモードを選択・設定する。
【００９１】
ここで、ポリゴンのエッジ長データ９及びエッジ方向データ１０の記述において、エッジの連鎖のうち末尾の２つについての記述は省略可能である。図１０はこれを説明する模式図であり、図９に示したポリゴン２３の連鎖の起点Ｐ１近傍を示している。最後から３番目のエッジＰ４８Ｐ４９に対応するベクトルＥ４８の向き及び終点が与えられると、ベクトルＥｋの向きは４通りに制限されること、隣接するベクトルＥｋとＥｋ＋１とは向きが異なること、及び２つのエッジでノードＰ１とＰ４９とをつなぐ必要があることから、ノードＰ５０の位置は必然的に定まる。よって、ベクトルＥ４９，Ｅ５０の方向及び長さを省略して、図形データ５のデータ量を減らすことができる。
【００９２】
（Ｅ−１）エッジ長符号化モードが「最頻出のエッジ長以外の出現位置」を記述する方法である場合
（Ｅ−１−１）概要
一般的なポリラインやポリゴン図形におけるエッジ長の出現頻度の特徴的な性質として、短いエッジ長ほど出現頻度が高く、長くなるほど出現頻度が低くなる。ポリゴンの場合は特に、境界ボックスの縁にて必ず進行方向が変化するため当該傾向がより顕著となる。そこで、本エッジ長符号化モードでは、対象図形において最も多く出現するエッジ長（最頻出エッジ長）についての記述の省略を図ることで圧縮効率の向上を図る。ちなみに、通常は、最頻出エッジ長は最も短いエッジ長である場合が多い。
【００９３】
最頻出エッジ長ＬＦＲは、エッジ長テーブル７の生成処理で述べたエッジ長の出現頻度の集計結果から求められる。符号化装置１は、エッジの連鎖内における位置に関し、最頻出エッジ長以外であるエッジ長ＬＮＦＲの位置を示す情報を符号化する。具体的には、ＬＮＦＲの位置を示す情報は上述した（ξｉ−ξｉ−１）であり、これに対し符号Ξｉが対応付けられる。エッジ長データ９には、連鎖にてξｉ番目に現れるＬＮＦＲの値を表す符号とΞｉとの組をｉの昇順にて順番に記述する。なお、対象図形のエッジ数は図形ヘッダ６に記述されるので、ＬＮＦＲの位置が特定されれば、ＬＦＲの位置も特定される。
【００９４】
（Ｅ−１−２）ＬＮＦＲの値を表す符号
ＬＮＦＲの値を表す符号はエッジ長テーブル７に定義される。例えば、上述したようにエッジ長テーブル７にはエッジ長Ｌｋの各種類の値が頻度順に格納され、その格納順序をエッジ長の符号として用いることができる。
【００９５】
ここでは、本エッジ長符号化モードが設定された場合におけるエッジ長Ｌｋの符号化の他の例を説明する。符号化装置１はエッジ長テーブル７の生成にて、既に述べたように、エッジ長の種類分のレコードを作成し、当該レコードにエッジ長を記述する。出現頻度が高い順にレコードを記述する場合、１番目のレコードにはＬＦＲの値が格納され、２番目以降のレコードにはＬＮＦＲの値が格納される。ここで、エッジ長データ９には上述のようにＬＮＦＲの値を表す符号は記述するが、ＬＦＲの値を表す符号は記述されないので、エッジ長を表す符号はＬＮＦＲについてだけ用意すればよい。ＬＮＦＲはエッジ長の種類より１つ少ない種類の符号で表すことができ、全種類のエッジ長を符号化する場合よりも符号のビット数を減らし得る。例えば、エッジ長がＬＦＲ＝１及びＬＮＦＲ＝２，３の３種類である場合、ＬＮＦＲは２種類となるのでＬＮＦＲの値を表す符号は１ビットで定義できる。
【００９６】
なお、ＬＮＦＲの値を表す符号は、基本的に圧縮効率が高くなり得る任意の方式を採用することができ、例えば、ハフマン符号を用いることができる。
【００９７】
また、ＬＮＦＲの値を表す符号の方式を、予め定めた種類の中で図形データ５ごとに切り換え可能として、図形データ５ごとに最も圧縮効率が高くなるものを採用してもよい。当該構成では、どの方式を用いるかを示す識別ビットを図形ヘッダ６又はエッジ長データ９の所定位置に記述する。
【００９８】
（Ｅ−１−３）ＬＮＦＲの出現位置を表す符号Ξ
ＬＮＦＲの出現位置を表す符号Ξは、基本的にデータ量の圧縮が図れる任意の方式を採用することができる。例えば、単純には、対象図形に現れる（ξｉ−ξｉ−１）の複数種類の値を順番にテーブルに格納し、格納位置の順番を（ξｉ−ξｉ−１）を表す符号Ξｉとして対応付けることができるが、本実施形態では符号化装置１は（ξｉ−ξｉ−１）の数値の出現頻度を求め、出現頻度が高い数値に短い符号を割り当てることで一層の圧縮効率の向上を図る。例えば、符号Ξとして、出現頻度に応じてハフマン符号を割り当てることができる。
【００９９】
また、ＬＮＦＲの出現位置を表す符号Ξの他の例として、以下の規則に基づいて生成したもの（独自符号）を用いることもできる。以下、独自符号にて符号化対象とする状態数を記号λで表す。ここでは（ξｉ−ξｉ−１）の種類数がλで表される。まず、二進数の状態数がλ以下となる最大のビット数ｎを選ぶ（例えばλ＝７の場合、ｎ＝２）。
【０１００】
λ＝２ｎである場合、Ξはビット列ｂ（ｎ）で表現可能な２ｎ種類の符号とする。一方、λ＞２ｎである場合、（ξｉ−ξｉ−１）のうち出現頻度が高い２ｎ−１種類の符号Ξをビット列ｂ１（ｎ）で表現する。残りの種類（λ−２ｎ＋１種類）の符号Ξは、残りの種類であることを識別するために、ビット列ｂ１（ｎ）のうち符号Ξに割り当てられていない１種類を用い、これと、λ−２ｎ＋１種類の識別に要する最低ビット数の追加ビット列ｂ２（ｎ＋）とを組み合わせたビット列ｂ１（ｎ）ｂ２（ｎ＋）で表現する。ちなみに、２≦λ−２ｎ＋１≦２ｎであるので、ｎ＋は１〜ｎの範囲で設定される。
【０１０１】
具体例として、λ＝４の場合、ｎ＝２であり、λ＝２ｎであるので、Ξはビット列ｂ１（２）である“００”，“０１”，“１０”，“１１”とされる。λ＝７での場合、ｎ＝２であり、λ＞２ｎであるので、（ξｉ−ξｉ−１）のうち出現頻度の上位３種類のΞに例えば、ｂ１（２）のうち“０１”，“１０”，“１１”を割り当てる。残りは４種類であるのでｎ＋＝２となり、当該４種類のΞにはｂ１（２）の残りである“００”と、追加ビット列ｂ２（２）の４通りのビットパターンとを組み合わせた符号を割り当てる。
【０１０２】
なお、図形データ５ごとにＬＮＦＲの出現位置を表す符号の方式を予め定めた種類の中で切り換え可能として、最も圧縮効率が高くなるものを採用する構成とすることができ、この場合、どの方式を用いるかを示す識別ビットを図形ヘッダ６又はエッジ長データ９の所定位置に記述する。
【０１０３】
（Ｅ−１−４）適用例
エッジ長データ９に関する上述の「最頻出のエッジ長以外の出現位置」を記述する方法の適用例として図９のポリゴン２３を説明する。
【０１０４】
ポリゴン２３のエッジ数Ｋは５０であり、エッジの連鎖におけるエッジ長の並びは“２１２１１３２１１１２１１１２１１１２１３１２１１１２２１３１１１１１３１１３１１２２１３１１１１２”である。ここで、上述したように、エッジ長データ９の記述にて最後の２つのエッジを省略し、４８個のエッジ長を符号化して記述する。
【０１０５】
当該省略後のエッジ長列における最頻出エッジ長ＬＦＲは１であり、ＬＮＦＲは２及び３であり、ＬＮＦＲの出現箇所は１７である。ＬＮＦＲは２種類なのでＬＮＦＲの値を表す符号は１ビットで定義できる。
【０１０６】
図１１はＬＮＦＲの出現位置を表す符号Ξを説明する説明図であり、当該１７箇所のＬＮＦＲの出現位置（ξｉ−ξｉ−１）についての出現頻度の集計結果と、符号化の順位と、符号Ξの例とを表形式で表している。符号Ξの例には上述した独自符号とハフマン符号とを示している。（ξｉ−ξｉ−１）の値の種類数は５、つまりλ＝５であり、独自符号では、上位３種類の符号Ξがビット列ｂ１（２）で表現され、残りは２種類であるのでｎ＋＝１とすることができビット列ｂ１（２）ｂ２（１）で表現される。
【０１０７】
ちなみに、３種類の値を取る４８個のエッジ長の列を単純にビット列符号化すると、１つの値の表現に２ビットを要するので、エッジ長データの記述に９６ビット必要である。
【０１０８】
一方、上述の方式では、エッジ長データは１７箇所のＬＮＦＲについてその値を識別する符号と出現位置の符号Ξとの組を含む。ＬＮＦＲの値を表す符号は、それぞれ１ビットであるので、全体で１７ビットである。また、出現位置の符号Ξに関しては、上位３種類の出現頻度が１３、残り２種類の出現頻度が４であることから、１７個の符号Ξを独自符号では３８ビットで表現できる。また、ハフマン符号では４１ビットで表現できる。
【０１０９】
よって、エッジ長データ９はハフマン符号では５８ビットで表現可能である。また、独自符号では、５５ビットで表現可能である。
【０１１０】
（Ｅ−２）エッジ長符号化モードが「連続エッジの出現パターン」を記述する方法である場合
（Ｅ−２−１）概要
一般的なポリラインやポリゴン図形におけるエッジ長の出現頻度には偏りが見られる。具体的には、短いエッジ長ほど出現頻度が高くなる傾向がある。そのため、エッジの連鎖にて連続する複数のエッジ長の並びのパターンにおいても出現頻度に偏りが生じる。そこで本エッジ長符号化モードでは、この連続エッジにおけるエッジ長のパターンの性質を利用することで、エッジ長データの圧縮効率の向上を図る。
【０１１１】
エッジの連鎖を先頭からそれぞれ連続するβ本（β≧２）ずつのエッジ群からなる複数の断片に区切り、各断片のβ本のエッジ長の順列パターンであるエッジ長パターンをそれぞれ１つの符号で表現する。ここで、エッジ長の種類をＭとすると、対象図形には最大でＭβ通りのエッジ長パターンが現れ得る。βが大きくなると、断片の個数が減ることにより符号の個数が減る一方、エッジ長パターンの増加により符号のビット数が増加するので、このトレードオフを考慮して好適な圧縮効率が得られるようにβを設定することができる。
【０１１２】
本実施形態ではβ＝２とした構成を説明する。すなわち、断片は一対のエッジからなる。この場合、エッジ長パターンについての上述の出現頻度の偏りに関し概念的に述べると、短いエッジとの組み合わせからなる断片のパターンの出現頻度が高くなり、断片が長いエッジ長同士の組み合わせになるほど出現頻度が低くなる。
【０１１３】
この点について、符号化装置１は、Ｋ個の長さＬｋからなるデータ列を順番にβ個ずつ区切って生成される複数のデータセグメントをそのデータの並び（エッジ長パターン）の種類ごとに集計して、上述したようにエッジ長テーブル７に代えてエッジ長のパターンテーブルを生成する。パターンテーブルは、対象図形に現れる断片のエッジ長の順列パターンと当該順列パターンを表す符号とを対応付ける符号化テーブルである。当該符号は、上述したエッジ長の符号と同様、基本的に対象図形において出現頻度が高い順列パターンほど短いビット列となるように設定された可変長符号である。
【０１１４】
エッジ長データ９には、連鎖における断片の順番に従い、各断片のエッジ長パターンを表す符号を順番に記述する。
【０１１５】
なお、エッジがＸ方向とＹ方向とに限定されるポリゴンでは符号化するエッジ長の数は偶数であるので、β＝２で断片を生成した場合、末尾のエッジは１つ前のエッジと対を形成する。一方、βがその他の値である場合や、β＝２でもポリラインでエッジ数Ｋが奇数である場合など、断片化にて末尾に端数分のエッジが生じることもある。この場合には、エッジの連鎖の末尾のエッジはその後に挿入するダミーのエッジと組み合わせて１つの断片とされ、符号化される。ダミーエッジのエッジ長は、例えば連結エッジのパターンテーブルに基づいて、末尾エッジのエッジ長との組み合わせにて最も出現頻度が多いものを選ぶことができ、このように選ぶことで、エッジ長データのビット数削減に寄与する。ちなみに、復号時には、対象図形のエッジ数が既知であるため、ダミーで入れたエッジについては無視される。
【０１１６】
（Ｅ−２−２）エッジ長パターンを表す符号
エッジ長パターンを表す符号は基本的に圧縮効率が高くなり得る任意の方式を採用することができ、例えば、連結エッジのパターンテーブルにエッジ長パターンをその頻度順に格納し、その格納順序をエッジ長の符号として用いることができる。また、上述した独自符号やハフマン符号を用いることができる。
【０１１７】
なお、エッジ長パターンを表す符号の方式を、予め定めた種類の中で図形データ５ごとに切り換え可能として、図形データ５ごとに最も圧縮効率が高くなるものを採用する構成とすることができ、この場合、どの方式を用いるかを示す識別ビットを図形ヘッダ６又はエッジ長データ９の所定位置に記述する。
【０１１８】
（Ｅ−２−３）適用例
エッジ長データ９に関する上述の「連続エッジの出現パターン」を記述する方法の適用例として図９のポリゴン２３を説明する。
【０１１９】
上に示したポリゴン２３のエッジの連鎖における５０個のエッジ長の並びにおける最後の２つのエッジを、上述したようにエッジ長データ９の記述にて省略し、残りの４８個のエッジ長の並びを符号化して記述する。
【０１２０】
エッジ長Ｌｋは１，２，３の３種類であり、２つのエッジ長の並びのパターンは９通りとなる。また、４８個のエッジ長の並びは２４個の断片に区切られる。
【０１２１】
図１２はエッジ長パターンを表す符号を説明する説明図であり、当該２４個の断片のエッジ長パターンについての出現頻度の集計結果と、符号化の順位と、符号の例とを表形式で表している。符号の例には上述した独自符号とハフマン符号とを示している。
【０１２２】
ここでは、集計結果におけるエッジ長パターンの種類数を、上述の独自符号の説明でのλとする。ポリゴン２３の上述の２４個の断片についてλ＝６であり、ハフマン符号では１〜５ビットで表される。また、独自符号では、上位３種類の符号がビット列ｂ１（２）で表現され、残りの符号は３種類であるのでｎ＋＝２とすることができビット列ｂ１（２）ｂ２（２）で表現される。
【０１２３】
ちなみに、３種類の値を取る４８個のエッジ長の列を単純にビット列符号化すると、上述したようにエッジ長データの記述に９６ビット必要である。
【０１２４】
一方、上述の連続エッジの出現パターンを記述する方法では、上位３種類の出現頻度が１９、残り３種類の出現頻度が５であることから、２４個のエッジ長パターンを独自符号では５８ビットで表現できる。また、ハフマン符号では５５ビットで表現できる。
【０１２５】
よって、エッジ長データ９はハフマン符号では５５ビットで表現可能である。また、独自符号では、５８ビットで表現可能である。
【０１２６】
［Ｆ］エッジ方向データの生成
エッジ方向データ１０は各図形データ５に格納するエッジ方向情報に応じた方法で生成される。本実施形態の符号化装置１は、エッジ方向情報に応じた各種の方法で対象図形のエッジ方向を符号化して、圧縮効率が高いエッジ方向情報の設定を選択し、図形データ５に格納する。
【０１２７】
（Ｆ−１）規則性エッジ方向符号化ルール
エッジ方向情報に設定されるエッジ方向符号化ルールのうち規則性エッジ方向符号化ルールは、既に述べたようにエッジ方向に現れる規則性に関する。当該ルールとして本実施形態では「回転規則」及び「ＬＲ規則」の２種類を設けている。
【０１２８】
（Ｆ−１−１）回転規則
ポリゴン図形の特性で、ポリゴン内部に設定した点から見ると、エッジの連鎖は概して一定の方向に連なっていく。例えば、エッジの周回方向が反時計回りである場合、境界ボックスの上辺のエッジから左辺のエッジまではエッジの連鎖は巨視的には左下向きに延び、同様に左辺のエッジから下辺のエッジまでは右下向き、下辺のエッジから右辺のエッジまでは右上向き、右辺のエッジから上辺のエッジまでは左上向きに延びる。つまり、統計的には以下の傾向がある。
（ａ）境界ボックスの上辺から左辺までのエッジの向きは、下、又は左
（ｂ）境界ボックスの左辺から下辺までのエッジの向きは、下、又は右
（ｃ）境界ボックスの下辺から右辺までのエッジの向きは、上、又は右
（ｄ）境界ボックスの右辺から上辺までのエッジの向きは、上、又は左
【０１２９】
つまり、或るエッジが境界ボックスの任意の一つの辺である第１の辺に重なると、後続のエッジの終点が境界ボックスの第１の辺に隣接する辺である第２の辺に達するまでの間、エッジの向きは第１の辺から遠ざかる向き及び第２の辺に近づく向きとなりやすい。この傾向を「回転規則」と称する。
【０１３０】
エッジ方向符号化ルールとして「回転規則」を利用する場合、第１の辺から遠ざかる向き及び第２の辺に近づく向きを順向き、また第１の辺に近づく向き及び第２の辺から遠ざかる向きを逆向きと定義する。そして、符号化装置１は図形情報抽出ステップでの向きＡｋの情報の取得において、向きＡｋが順向きである場合、回転規則に「適合」とし、逆向きである場合、回転規則に「非適合」とし、向きＡｋを「適合」（順向き）か「非適合」（逆向き）かの二値情報、つまり１ビットで表現する。例えば、適合状態をビット値“０”、非適合状態をビット値“１”とする。
【０１３１】
なお、エッジの連鎖の先頭エッジＥ１を境界ボックスの辺上に選択することで、回転規則をエッジの連鎖の先頭から適用することができる。
【０１３２】
回転規則における順向き／逆向きは、ポリゴンを上記（ａ）〜（ｄ）の４つの区間に分け、各区間にて共通に定義される。ここで、境界ボックスの辺上に複数のエッジが存在する場合も、ポリゴン全体を４つの区間に分けて回転規則を利用する。例えば、本実施形態では上述のように、境界ボックスの上辺に位置するエッジのうち最も左側のものをエッジＥ１としポリゴンを反時計回りに周回する。この場合、例えば、上記（ａ）の区間はエッジＥ１から最後に左辺に達するエッジＥα１−１まで、上記（ｂ）の区間はエッジＥα１から最後に下辺に達するエッジＥα２−１まで、上記（ｃ）の区間はエッジＥα２から最後に右辺に達するエッジＥα３−１まで、そして上記（ｄ）の区間はエッジＥα３から最後に上辺に達するエッジＥＫまでと定めることができる。
【０１３３】
（Ｆ−１−２）ＬＲ規則
上述したようにベクトルＥｋ−１の向きＡｋ−１に対するベクトルＥｋの向きＡｋは右向きか左向きかの二値情報で表すことができる。この左右の向きに関して、ベクトルＥｋ−１の向きＡｋ−１に対するベクトルＥｋの向きＡｋは、ベクトルＥｋ−２の向きＡｋ−２に対するベクトルＥｋ−１の向きＡｋ−１と逆となることが多い。つまり、例えば、Ａｋ−２に対しＡｋ−１が右向きであれば、Ａｋ−１に対しＡｋは左向きとなりやすく、逆にＡｋ−１が左向きであればＡｋは右向きとなりやすく、その結果、エッジの連鎖にてエッジの向きは左右交互に現れやすい。この傾向を、左右、つまりＬｅｆｔ／Ｒｉｇｈｔにちなんで「ＬＲ規則」と称する。
【０１３４】
ちなみに、エッジの連鎖内にはＬＲ規則に従わない部分も当然生じ得、「左・左」「右・右」と同じ方向が続く場合があるが、全体からみると少数となる。また、「左」ないしは「右」が連続すると、エッジがとぐろを巻く状態となり、あまり続くと図形として成り立たなくなる。従って、実質的には、同一方向の回転は４，５回程度が限度となる。
【０１３５】
エッジ方向符号化ルールとして「ＬＲ規則」を利用する場合、符号化装置１は、図形情報抽出ステップでの向きＡｋの情報の取得において、ベクトルＥｋ−１の向きＡｋ−１に対するベクトルＥｋの向きＡｋの左右関係が、ベクトルＥｋ−２の向きＡｋ−２に対するベクトルＥｋ−１の向きＡｋ−１との左右関係と逆である場合を、ＬＲ規則に「適合」（正則）とし、一方、連続する２つのベクトルＥｋ，Ｅｋ−１での向きＡｋ，Ａｋ−１の左右関係が同じある場合、ＬＲ規則に「非適合」（非正則）とし、向きＡｋを「適合」か「非適合」かの二値情報、つまり１ビットで表現する。例えば、適合状態をビット値“０”、非適合状態をビット値“１”とする。
【０１３６】
（Ｆ−２）エッジ方向符号化ルールの適用省略箇所
符号化装置１は図形情報抽出ステップにてエッジの連鎖順に向きＡｋの情報を抽出して、符号化ステップにて当該向きＡｋの情報を符号化する。その際、境界ボックスとの位置関係などにより、向きが一意に定まるエッジがある。具体的には、境界ボックスの辺上に存在するエッジ及び、その次のエッジの向きは一意に定まる。
【０１３７】
例えば、エッジＥαの始点が境界ボックスの辺上にあれば、当該エッジの向きＡαは、当該辺に沿った２つの向きのうちエッジの周回方向で定まる一方となる。また、境界ボックスの辺上のエッジＥαの次のエッジＥα＋１の向きＡα＋１は、ポリゴンの内側向きに定まる。
【０１３８】
つまり、これらの向きが一意に決まるエッジについては、エッジ方向データ１０の記述にて向きの情報を直接的には含める必要がなく、よって、エッジ方向符号化ルールへの適合／非適合の判断、及び符号化を省略することができる。
【０１３９】
（Ｆ−２）エッジ方向符号化の態様
（Ｆ−２−１）「進行方向（左・右）」を記述する態様
本態様は、３種類設定された上述の「エッジ方向符号化ルール」のうち、エッジ方向の符号化に際し、隣接する一対のエッジにて一方のエッジに対する他方の向きは一方のエッジに交差する軸方向に沿った２つの向き（右向き、左向き）に制限されるという特徴を利用するものである。
【０１４０】
上述したようにベクトルＥｋ−１の向きＡｋ−１に対するベクトルＥｋの向きＡｋは右向きか左向きかの二値情報で表すことができる。そこで、符号化対象の各エッジについて、例えば、右向きをビット値“０”、左向きをビット値“１”で符号化する。一般にはベクトルの向きとしてＸ軸、Ｙ軸それぞれの正負両方向の４通りがあり、その表現には２ビットを要するところ、本態様では１ビットで表現でき、符号化データのデータ量圧縮が可能である。対象図形の形状が複雑である場合に、この態様での符号化の方が有効となる場合がある。
【０１４１】
（Ｆ−２−１−１）適用例
図９のポリゴン２３に「進行方向（左・右）」を記述する態様を適用した例を説明する。
【０１４２】
２番目乃至５０番目の前記要素線分についての前記向きＡｋが右向きか左向きかを表すビット値の並びは“（１）０１０（１１）０１０１１００１０１０１０１０１０１０（１１）０（１１）０１０１０１０１１００１０（１１）０１００”となる。
【０１４３】
ここで、符号化装置１は上述したエッジ方向符号化ルールの適用省略箇所を考慮して符号化することができる。適用省略箇所はエッジＥ１，Ｅ２，Ｅ６，Ｅ７，Ｅ２７，Ｅ２８，Ｅ３０，Ｅ３１，Ｅ４５，Ｅ４６であるので、具体的には、上記ビットの並びにて括弧内が適用省略箇所のエッジとして省略される。
【０１４４】
（Ｆ−２−２）「エッジ方向符号化ルールへの適合エッジ数」を記述する態様
（Ｆ−２−２−１）概要
この態様では、符号化装置１はエッジＥｋ（１≦ｋ≦Ｋ）について符号化ステップにて上述の規則性エッジ方向符号化ルール、つまり回転規則又はＬＲ規則を適用して得られた向きＡｋの二値情報列を、符号化ステップにてランレングス圧縮する。すなわち、エッジの連鎖にて、規則性エッジ方向符号化ルールの適合状態が続くエッジ数、及び非適合状態が続くエッジ数を符号化する。
【０１４５】
ここで、エッジ方向符号化ルールの適用省略箇所のエッジの向きについては、向きＡｋの二値情報列から省略できる。また、上述したように、エッジの連鎖のうち末尾の２つのエッジの向きについても向きＡｋの二値情報列から省略できる。よって、符号化装置１はこれらの箇所を省略した二値情報列を符号化する構成とすることができる。
【０１４６】
適合状態及び非適合状態のランレングスの符号化に関し、図形ヘッダ６にランレングス記述ビット数として記述される「適合エッジ数を記述するビット数」、「非適合エッジ数を記述するビット数」が用いられる。
【０１４７】
（Ｆ−２−２−２）符号化方法の第１の例
適合状態のランレングスの符号化において、符号化装置１は、適合状態が連続するエッジ数の分布に基づいて、「適合エッジ数を記述するビット数」を予め定める。
【０１４８】
適合エッジ数を記述するビット数をｎで表すと、ビット列ｂ（ｎ）で表現可能な２ｎ種類の符号のうち２ｎ−１種類（ビット列ｂＡ（ｎ）と表す。）を１〜２ｎ−１本の連続エッジ数を表現するものとして用い、残りの１種類（ビット列ｂＢ（ｎ）と表す。）を適合エッジ数が２ｎ 本以上継続していることを表現するものとして用いる。符号化装置１は、適合状態の区間のエッジ数の符号化にて、符号化対象のエッジ数μｊが１〜２ｎ−１であればｂＡ（ｎ）を割り当て、一方、μｊが２ｎ以上であればｂＢ（ｎ）の後に、μｊ−（２ｎ−１）をμｊ＋１として、μｊ＋１に対してμｊと同様の処理を繰り返した結果のビット列をつなげた符号とする。つまり、適合エッジ数μ０が１≦μ０≦２ｎ−１であれば、ビット列ｂＡ（ｎ）で表現される符号とされ、２ｎ≦μ０≦２（２ｎ−１）であれば、ビット列ｂＢ（ｎ）ｂＡ（ｎ）で表現される符号とされ、また、１＋ｍ（２ｎ−１）≦μ０≦（ｍ＋１）（２ｎ−１）（ｍは任意の自然数である。）であれば、ビット列ｂＢ（ｎ）をｍ回繰り返した後にｂＡ（ｎ）をつなげた符号とされる。
【０１４９】
非適合状態のランレングスの符号化も、「非適合エッジ数を記述するビット数」をｎとして、上述の適合状態のランレングスの符号化と同様に行う。なお、「非適合エッジ数を記述するビット数」は、「適合エッジ数を記述するビット数」と同様に、非適合状態が連続するエッジ数の分布に基づいて定めてもよいし、基本的に非適合状態が連続するエッジ数は適合状態よりも短いので「適合エッジ数を記述するビット数」を基準にして、それと同じかそれ以下の値に設定してもよい。
【０１５０】
符号化装置１は、エッジの連鎖にて交互に現れる適合状態の区間、非適合状態の区間それぞれについてランレングス符号化を行い、それらを順番に並べたランレングス符号列を生成する。また、当該ランレングス符号列の最初の符号が適合状態の区間、非適合状態の区間のいずれのものであるかを識別する１ビットのフラグを当該ランレングス符号列の先頭に付す。例えば、適合状態の区間から始まる場合の当該フラグは“０”とし、非適合状態の区間から始まる場合は“１”とする。
【０１５１】
例えば、「適合エッジ数を記述するビット数」と「非適合エッジ数を記述するビット数」とを共にｎ＝２とし、値“１”，“２”，“３”にそれぞれビット列ｂＡ（２）として“０１”，“１０”，“１１”を割り当て、ビット列ｂＢ（２）を“００”とする。エッジの連鎖が適合状態の区間から始まり、適合／非適合区間が交互に、８本、１本、６本、２本、２本、１本、１３本と続く場合は、“０/００・００・１０/０１/００・１１/１０/１０/０１/００・００・００・００・０１”と符号化される。
【０１５２】
（Ｆ−２−２−３）符号化方法の第２の例
本方法は「非適合」エッジが非常に少ない場合を想定したものである。具体的には、符号化装置１は非適合エッジの連続発生状況を予め調べて、「非適合エッジ数を記述するビット数」を定め、その際、非適合エッジが１本も無い場合と、非適合エッジが２本以上連続して発生しない場合（つまり非適合エッジの連続数が１本に限定される場合）には、上述の第１の方法とは異なるエッジ方向データ１０の記述とする。
【０１５３】
（ａ）非適合エッジが無い場合
この場合、全てのエッジが規則性エッジ方向符号化ルールに合致しているため、上記第１の方法のランレングスの符号化を省略できる。そこで、この場合であることを、例えば、図形ヘッダ６にランレングス記述ビット数として記述する「適合エッジ数を記述するビット数」及び「非適合エッジ数を記述するビット数」を共に“０”とすることで識別し、エッジ方向データ１０にはエッジの向きＡｋの情報の明示的な記述を行わない。
【０１５４】
（ｂ）非適合エッジの連続数が１本に限定される場合
この場合、非適合状態の区間のエッジ数は１であることが分かっているので、非適合状態について当該区間のランレングス符号を記述する必要が無い。そこで、この場合であることを例えば「非適合エッジ数を記述するビット数」を“０”とすることで識別し、エッジ方向データ１０には、適合状態の区間のエッジ数を表すランレングス符号だけを連続して記述する。なお、符号化の開始位置からの最初のエッジが、適合エッジであるか非適合エッジであるかを識別する上述のフラグはランレングス符号列の先頭に付す。
【０１５５】
（Ｆ−２−２−４）符号化方法の第３の例
適合エッジ数を記述するビット数をｎで表すと、ビット列ｂ（ｎ）で表現可能な２ｎ種類の符号（ビット列ｂＣ（ｎ）と表す。）で１〜２ｎ本の連続エッジ数を表現する。また、適合状態の区間のエッジ数の符号化にて２ｎを表すｂＣ（ｎ）が現れたとき、その後にさらに当該区間におけるエッジ数の符号が継続するのか否かを識別する継続識別ビットとして１ビットのｂＤ（ｎ）を付す。継続識別ビットは例えば、直前のｂＣ（ｎ）と同じ区間のエッジ数を表現する符号が継続する場合には“０”とし、継続せず、次に別の区間のエッジ数を表現するｂＣ（ｎ）を記述する場合には“１”とする。
【０１５６】
すなわち、符号化装置１は、適合状態の区間のエッジ数の符号化にて、符号化対象のエッジ数μｊが１〜２ｎであればｂＣ（ｎ）を割り当て、さらにμｊ＝２ｎの場合は当該ｂＣ（ｎ）の後に非継続を示すｂＤ（ｎ）をつなげ、一方、μｊが２ｎ＋１以上であれば２ｎを表すｂＣ（ｎ）の後に継続を示すｂＤ（ｎ）を付した上で、継続μｊ−２ｎをμｊ＋１とし当該μｊ＋１に対してμｊと同様の処理を繰り返した結果のビット列をつなげた符号とする。つまり、符号は、適合エッジ数μ０が１≦μ０≦２ｎ−１であればビット列“ｂＣ（ｎ）”で表現され、μ０＝２ｎであればビット列“ｂＣ（ｎ）・１”で表現され、２ｎ＋１≦μ０≦２ｎ＋１−１であればビット列“ｂＣ（ｎ）・０・ｂＣ（ｎ）”で表現され、μ０＝２ｎ＋１であればビット列“ｂＣ（ｎ）・０・ｂＣ（ｎ）・１”で表現される。さらに、任意の自然数ｍについて、ｍ・２ｎ＋１≦μ０≦（ｍ＋１）・２ｎ−１であれば、ビット列“ｂＣ（ｎ）・０”をｍ回繰り返した後に“ｂＣ（ｎ）”をつなげた符号とされ、μ０＝（ｍ＋１）２ｎであれば、ビット列“ｂＣ（ｎ）・０”をｍ回繰り返した後に“ｂＣ（ｎ）・１”をつなげた符号とされる。
【０１５７】
なお、非適合状態のランレングスの符号化も、「非適合エッジ数を記述するビット数」をｎとして、上述の適合状態のランレングスの符号化と同様に行うことができるが、非適合状態の連続エッジ数は基本的に少ないビット数ｎ’で表現できると期待できるため、単独のビット列ｂＣ（ｎ’）を符号として割り当てる構成とすることもできる。
【０１５８】
符号化装置１は、エッジの連鎖にて交互に現れる適合状態の区間、非適合状態の区間それぞれについてランレングス符号化を行い、それらを順番に並べたランレングス符号列を生成する。また、既に述べたように、当該ランレングス符号列の最初の符号が適合状態の区間、非適合状態の区間のいずれのものであるかを識別する１ビットのフラグを当該ランレングス符号列の先頭に付す。例えば、適合状態の区間から始まる場合の当該フラグは“０”とし、非適合状態の区間から始まる場合は“１”とする。
【０１５９】
例えば、「適合エッジ数を記述するビット数」と「非適合エッジ数を記述するビット数」とを共にｎ＝２とし、値“１”，“２”，“３”，“４”にそれぞれビット列ｂＣ（２）として“０１”，“１０”，“１１”，“００”を割り当てる。エッジの連鎖が第１の方法で挙げた例と同じ場合、つまり、適合状態の区間から始まり、適合／非適合区間が交互に、８本、１本、６本、２本、２本、１本、１３本と続く場合は、“０/００・０・００・１/０１／００・０・１０/１０/１０/０１/００・０・００・０・００・０・０１”と符号化される。
【０１６０】
また、非適合エッジの連続数が１本に限定される場合は上述した第２の方法の（ｂ）で述べた手法と同様にして、非適合状態の区間のランレングス符号を省略する記述とすることもできる。
【０１６１】
（Ｆ−２−２−５）第１の適用例
図９のポリゴン２３に「エッジ方向符号化ルールへの適合エッジ数」を記述する態様を適用した例を説明する。この例では、規則性エッジ方向符号化ルールに用いる規則性の種類は回転規則である。
【０１６２】
符号化装置１は適合状態、非適合状態のランレングス符号化を行うために、まず、符号化対象のエッジの回転規則への適合／非適合を調べる。当該ポリゴンでは非適合エッジはＥ１２，Ｅ４０であり、その連続数は１本に限定される。そこで、上述の符号化方法の第２の例の（ｂ）の方法で符号化することにする。よって、非適合エッジ数を記述するビット数は０に設定して、エッジ方向データ１０には、非適合状態の区間のエッジ数を表すランレングス符号の記述は省略し、適合状態の区間のエッジ数を表すランレングス符号だけを連続して記述する。
【０１６３】
なお、適合状態の区間のエッジ数を表すランレングス符号は上述の符号化方法の第１の例の方法で生成する。具体的には、適合エッジ数を記述するビット数は４に設定する。ｎ＝４として、値１〜１５の二進数表示を上述のビット列ｂＡ（４）とし、ｂＢ（４）は“００００”と定義する。
【０１６４】
また、上述したエッジ方向符号化ルールの適用省略箇所を考慮して符号化する。よって、エッジＥ１，Ｅ２，Ｅ６，Ｅ７，Ｅ２７，Ｅ２８，Ｅ３０，Ｅ３１，Ｅ４５，Ｅ４６はエッジの向きＡｋの情報の符号化の対象外となる。また、上述したようにエッジの連鎖の末尾の２つのエッジＥ４９，Ｅ５０も対象外とする。
【０１６５】
その結果、符号化対象の最初のエッジはＥ３となり、当該エッジは適合エッジである。つまり、符号化対象のエッジ列は適合状態の区間から始まるので、ランレングス符号列の先頭に付す１ビットの識別フラグは“０”に設定される。
【０１６６】
適合状態の区間は、Ｅ３〜Ｅ５，Ｅ８〜Ｅ１１，Ｅ１３〜Ｅ２６，Ｅ２９，Ｅ３２〜Ｅ３９，Ｅ４１〜Ｅ４４，Ｅ４７〜Ｅ４８である。区間Ｅ３〜Ｅ５と区間Ｅ８〜Ｅ１１との間のエッジＥ６，Ｅ７は符号化対象外なので、適合状態のランレングスの算出にて当該両区間のエッジ数は通算し、１番目の適合状態の区間のランレングスμ０は７となる。同様に、３つの区間Ｅ１３〜Ｅ２６，Ｅ２９，Ｅ３２〜Ｅ３９のエッジ数を通算し、２番目の適合状態の区間のランレングスμ０は２３となり、また区間Ｅ４１〜Ｅ４４，Ｅ４７〜Ｅ４８のエッジ数を通算し、３番目の適合状態の区間のランレングスμ０は６となる。
【０１６７】
１番目の適合状態の区間についてμ０＝７は“ｂＡ（４）”の形に符号化され、具体的には“０１１１”となる。
【０１６８】
２番目の適合状態の区間のμ０＝２３は、１６≦μ０≦３０、つまり、上述の１＋ｍ（２ｎ−１）≦μ０≦（ｍ＋１）（２ｎ−１）にてｎ＝４，ｍ＝１の場合に当たり、よって、“ｂＢ（４）ｂＡ（４）”の形に符号化され、具体的には“００００１０００”となる。
【０１６９】
３番目の適合状態の区間のμ０＝６を表す“ｂＡ（４）”は“０１００”となる。ここで、符号化対象のエッジ列の最後が適合状態の区間である場合、当該区間のランレングスは、符号化対象のエッジの連鎖の長さから、当該区間より前の区間の長さの合計を引いて求めることができる。とすれば、当該区間のランレングスを表す符号の末尾のｂＡ（ｎ）はｎビットの任意のパターンとすることができる。よって、ここでは、上述の方法で生成されたエッジ方向データ１０のビット列をさらにハフマン符号化圧縮などを用いて２次圧縮する際に圧縮効率が高くなるように、当該末尾のビットパターンを定める。具体的には、同じ数値が継続する方が圧縮率が高まることが期待できることから、末尾を上述のｂＡ（４）で与えられる“０１００”に代えて“００００”とする。
【０１７０】
その結果、エッジ方向データ１０に記述するビット列として１７ビットの“０/０１１１/００００・１０００/００００”が得られる。例えば、２次圧縮として、ｂＡ（４），ｂＢ（４）が並ぶビット列部分について、４ビットずつに区切り、出現率の高い“００００”を１ビットの“１”に置き換え、それ以外の４ビットのパターン（ここではｂＡ（４）の１５パターンとなる。）を“０・ｂＡ（４）”に置き換えるとすると、上述のビット列は１３ビットの“０/０・０１１１/１・０・１０００/１”に変換される。
【０１７１】
（Ｆ−２−２−６）第２の適用例
図１３は「エッジ方向符号化ルールへの適合エッジ数」を記述する態様の他の適用例を説明するポリゴンの模式図である。この例は、符号化対象のエッジのエッジ方向符号化ルールにＬＲ規則を用いた場合に関する。ちなみに、同図に示すポリゴンのエッジ数はＫ＝５２である。また、エッジの周回方向は反時計回りとし、エッジＥ１は境界ボックスの上辺に位置する最も左のエッジとする。
【０１７２】
符号化装置１は適合状態、非適合状態のランレングス符号化を行うために、まず、符号化対象のエッジのＬＲ規則への適合／非適合を調べる。当該ポリゴンでは非適合エッジはＥ１２，Ｅ２２，Ｅ４２，Ｅ４４であり、その連続数は１本に限定される。そこで、上述の符号化方法の第２の例の（ｂ）の方法で符号化する。よって、非適合エッジ数を記述するビット数は０に設定して、エッジ方向データ１０には、非適合状態の区間のエッジ数を表すランレングス符号の記述は省略し、適合状態の区間のエッジ数を表すランレングス符号だけを連続して記述する。
【０１７３】
適合状態の区間のエッジ数を表すランレングス符号は上述の符号化方法の第１の例の方法で生成する。ここでは、適合エッジ数を記述するビット数は３に設定する。ｎ＝３として、値１〜７の二進数表示を上述のビット列ｂＡ（３）とし、ｂＢ（３）は“０００”と定義する。
【０１７４】
また、上述したエッジ方向符号化ルールの適用省略箇所を考慮して符号化する。よって、エッジＥ１，Ｅ２，Ｅ６，Ｅ７，Ｅ２９，Ｅ３０，Ｅ３２，Ｅ３３，Ｅ４７，Ｅ４８はエッジの向きＡｋの情報の符号化の対象外となる。また、上述したようにエッジの連鎖の末尾の２つのエッジＥ５１，Ｅ５２も対象外とする。
【０１７５】
その結果、符号化対象の最初のエッジはＥ３となり、当該エッジは適合エッジである。つまり、符号化対象のエッジ列は適合状態の区間から始まるので、ランレングス符号列の先頭に付す１ビットの識別フラグは“０”に設定される。
【０１７６】
適合状態の区間は、Ｅ３〜Ｅ５，Ｅ８〜Ｅ１１，Ｅ１３〜Ｅ２１，Ｅ２３〜Ｅ２８，Ｅ３１，Ｅ３４〜Ｅ４１，Ｅ４３，Ｅ４５〜Ｅ４６，Ｅ４９〜Ｅ５０である。区間Ｅ３〜Ｅ５と区間Ｅ８〜Ｅ１１との間のエッジＥ６，Ｅ７は符号化対象外なので、適合状態のランレングスの算出にて当該両区間のエッジ数は通算し、１番目の適合状態の区間のランレングスμ０は７となる。そして次の区間Ｅ１３〜Ｅ２１が２番目の適合状態の区間となり、μ０＝９となる。次の３つの区間Ｅ２３〜Ｅ２８，Ｅ３１，Ｅ３４〜Ｅ４１のエッジ数は通算でき、３番目の適合状態の区間についてμ０＝１５が得られる。区間Ｅ４３は４番目の適合状態の区間となり、μ０＝１となる。区間Ｅ４５〜Ｅ４６，Ｅ４９〜Ｅ５０のエッジ数は通算でき、５番目の適合状態の区間についてμ０＝４が得られる。
【０１７７】
１番目、４番目及び５番目の適合状態の区間のμ０＝７，１，４は“ｂＡ（３）”の形に符号化され、具体的にはそれぞれ“１１１”，“００１”，“１００”となる。
【０１７８】
２番目の適合状態の区間のμ０＝９は“ｂＢ（３）ｂＡ（３）”の形に符号化され、具体的には“００００１０”となる。
【０１７９】
３番目の適合状態の区間のμ０＝１５は“ｂＢ（３）ｂＢ（３）ｂＡ（３）”の形に符号化され、具体的には“００００００００１”となる。
【０１８０】
その結果、エッジ方向データ１０に記述するビット列として２５ビットの“０/１１１/０００・０１０/０００・０００・００１/００１/１００”が得られる。
【０１８１】
（Ｆ−２−３）「境界ボックスを単位としたエッジ方向符号化ルールへの適合エッジ数」を記述する態様
本態様は、規則性エッジ方向符号化ルールを用いた符号化において、「境界ボックスを単位としたエッジ方向符号化ルールへの適合エッジ数」を記述するオプションを適用するものである。
ここでは、上述したように、エッジの連鎖の先頭は、境界ボックスの上辺に位置するエッジのうち、最も左側のエッジとし、エッジの周回方向は反時計方向とする。この場合、エッジの連鎖は境界ボックスの上辺からスタートし、左辺、下辺、右辺、上辺の順に到達する。エッジの連鎖のうち、境界ボックスの或る辺から次の辺に到達する部分を部分列とする。本態様は全ての部分列が適合状態の区間から始まる場合に適用し、部分列ごとに以下の符号化を行う。
【０１８２】
部分列の先頭から末尾まで規則性エッジ方向符号化ルールに適合する場合、それを例えば、１ビットの値“１”で符号化する。
【０１８３】
一方、部分列の途中に非適合状態の区間が存在する場合には、例えば、図形ヘッダ６に記述するランレングス記述ビット数を用いて、上述の符号化方法の第１の例の方法、第２の例の方法の（ｂ）の場合、第３の例の方法などで部分列の先頭から順番に符号化する。また、この場合に、部分列の途中から末尾まで適合状態が連続する区間は１ビットの値“１”で符号化し、それ以外の区間は識別ビット“０”に続けて、当該区間の適合状態又は非適合状態の連続エッジ数を表すビット列を記述した符号とすることができる。
【０１８４】
（Ｆ−２−３−１）適用例
図９のポリゴン２３に「境界ボックスを単位としたエッジ方向符号化ルールへの適合エッジ数」を記述する態様を適用した例を説明する。
【０１８５】
ここでは、部分列の先頭又は途中から末尾まで適合状態が連続する区間は１ビットの値“１”で符号化し、部分列におけるそれ以外の区間は識別ビット“０”に続けて、当該区間の連続エッジ数を表すビット列を記述した符号とする例を述べる。また、図９のポリゴンでは上述したように非適合状態の連続エッジ数は１本に限定される。そこで、上述の符号化方法の第２の例の方法の（ｂ）を適用する。よって、識別ビット“０”を付す符号は、適合状態の区間についてだけ生成される。なお、適合エッジ数を記述するビット数を４とする。
【０１８６】
符号化対象エッジのうち境界ボックスの上辺から左辺にかけての部分列をなすエッジＥ３〜Ｅ５は全てルールに適合するので、１ビットの値“１”に符号化する。
【０１８７】
符号化対象エッジのうち境界ボックスの左辺から下辺にかけての部分列をなすエッジＥ８〜Ｅ２６には途中に非適合エッジＥ１２が存在する。そこで、エッジＥ８〜Ｅ１１の連続エッジ数“４”が“０・０１００”に符号化され、エッジＥ１３〜Ｅ２６は部分列の末尾まで適合状態が連続するので“１”に符号化される。
【０１８８】
符号化対象エッジのうち境界ボックスの下辺から右辺にかけての部分列はエッジＥ２９からなり、これは適合エッジであるので、１ビットの値“１”に符号化する。
【０１８９】
符号化対象エッジのうち境界ボックスの右辺から上辺にかけての部分列をなすエッジＥ３２〜Ｅ４４，Ｅ４７〜Ｅ４８は途中に非適合エッジＥ４０が存在する。そこで、エッジＥ３２〜Ｅ３９の連続エッジ数“８”が“０・１０００”に符号化され、エッジＥ４１〜Ｅ４４，Ｅ４７〜Ｅ４８は部分列の末尾まで適合状態が連続するので“１”に符号化される。
【０１９０】
その結果、エッジ方向データ１０に記述するビット列として１４ビットの“１/０・０１００/１/１/０・１０００/１”が得られる。
【０１９１】
（Ｆ−２−４）「適合エッジ数の規定値への合致度」を記述する態様
本態様は、規則性エッジ方向符号化ルールを用いた符号化において、「適合エッジ数の規定値への合致度」を記述するオプションを適用するものである。
【０１９２】
規則性エッジ方向符号化ルールの適合状態の連続数についての規定値μＤを所定ビット数ｎ１で予め設定する。また、指定エッジ数κを所定ビット数ｎ２で予め設定する。例えば、ｎ１＝２とし、当該２ビットで表現可能な４状態でμＤ＝２〜５のいずれかを設定することにする。また、ｎ２＝２とし、当該２ビットで表現可能な４状態でκ＝１〜４のいずれかを設定することにする。
【０１９３】
まず、エッジの連鎖における符号化対象のエッジを先頭のμＤ本のエッジの向きが全て適合状態であれば、適合状態の連続数が規定値に合致するとして、当該μＤ本のエッジの向きを１ビットの値“１”で符号化する。一方、適合状態の連続数が規定値に合致しない場合は、それを識別する１ビットの値“０”に続けて、符号化対象のエッジの先頭から指定エッジ数κのエッジの適合／非適合状態を記述する。例えば、適合状態は１ビットの値“１”、非適合状態は１ビットの値“０”で記述する。また、同様の符号化を残りのエッジについて順番に行う。
【０１９４】
（Ｆ−３）その他
（Ｆ−３−１）エッジ数が４，６，８であるポリゴン
エッジ数が４，６，８であるポリゴンについては、エッジの向き以外の情報からポリゴンの形状が一意に定まるため、エッジ方向データ１０におけるエッジの向きＡｋの記述は不要である。
【０１９５】
図１４はこれを説明するポリゴンの模式図である。図１４（ａ）はエッジ数が４のポリゴンである。この場合、図形ヘッダ６に記述される存在範囲データ、起点ノード位置、及びエッジの連鎖の周回方向からポリゴンの形状が一意に定まる。
【０１９６】
図１４（ｂ）はエッジ数が６のポリゴンの例である。また、エッジ数が８のポリゴンの形状は図１４（ｃ）〜（ｆ）に示す４つのパターンに分類できる。エッジ数が６，８のポリゴンは、図形ヘッダ６に記述する存在範囲データ、エッジの連鎖の周回方向、境界ボックス上に設定される起点ノード位置、及びエッジ長データ９からポリゴンの形状が一意に定まる。
【０１９７】
よって、エッジ数が４，６，８の場合には、エッジの向きＡｋの情報の符号化に必要なデータ量は０ビットとすることができる。
【０１９８】
（Ｆ−３−２）対象図形の全てのエッジが規則性エッジ方向符号化ルールに従う場合
特に画像領域分割によって生成されたポリゴン等にて、このような場合は比較的数多く生じる。また、ポリゴンの大きさ（またはエッジ数）が小さくなるほど、このような場合となる図形の出現率がさらに高くなる。
【０１９９】
境界ボックス上に設定される起点ノード位置、及びエッジの連鎖の周回方向からエッジＥ１の向きＡ１は一意に定まる。向きＡ１が定まると、ここで述べる全てのエッジが規則性エッジ方向符号化ルールに従う場合、当該ルールとエッジ長の情報とから、エッジに対応するベクトルＥ２〜ＥＫが順番に求められる。つまり、各エッジの向きＡ２〜ＡＫを再現可能である。
【０２００】
よって、この場合のエッジ方向データ１０として必要な情報は、対象図形の全てのエッジが規則性エッジ方向符号化ルールに従うか否かの識別に必要な情報１ビットのみとなる。
【０２０１】
［変形例］
（１）４方向以外のエッジの記述
上記の実施形態では、エッジの向きがＸ方向及びＹ方向に対応した４つの向き（上下左右）である対象図形について図形圧縮符号化方法を説明した。ここでは当該方法を、エッジが任意の向きをとり得る対象図形に拡張することを説明する。
【０２０２】
具体的には、任意方向に進行するエッジに対しては、その始点ノードと終点ノードの間に仮想ノードを設定することで、エッジの進行方向が４方向になるようにする。
【０２０３】
図１５はその例を示すポリゴンの模式図である。図１５（ａ）は上下左右以外の向きのエッジを有するポリゴンの例を示しており、図１５（ｂ）は当該ポリゴンに仮想ノードを設定して、上下左右の向きのエッジのみからなるポリゴンに変換した状態を示している。具体的には、図１５（ａ）のポリゴンのエッジＰ２Ｐ３，Ｐ４Ｐ５，Ｐ７Ｐ１が斜めであり、図１５（ｂ）ではこれらエッジにそれぞれ仮想ノードＰ２／３，Ｐ４／５，Ｐ７／１を設定している。
【０２０４】
仮想ノードを追加することにより、これまで述べてきた手法がそのまま適用可能となる。元の図形のノード間に仮想ノードを追加したかどうかは、各エッジにつき、１ビットずつを割り当てて符号化して記述する。但し、仮想ノードの追加箇所がかなり少ない場合や、逆にかなり多い場合、前者については仮想ノードの追加位置のみを、後者の場合には仮想ノードを追加しない位置のみを符号化して記述することにより、データ量を減らすことが可能となる。仮想ノードの追加位置、または仮想ノードでない位置に関する符号化は、ハフマン符号等、適合／非適合状態のランレングス符号化で述べた方法と同等の手段により行うことができる。なお、ノード位置に関する情報を展開する場合には、情報の復元後、仮想ノード点となっているノードを削除すればよい。
【０２０５】
（２）対象図形がポリラインである場合
上記の実施形態では基本的にポリゴンを圧縮符号化の対象図形として本発明を説明したが、上述した本発明の特徴の少なくとも一部はポリラインを対象図形とした圧縮符号化に適用することができる。例えば、エッジ長データ９に関する符号化の基本的な方法はポリラインにも適用できる。
【０２０６】
また、エッジ方向データ１０の符号化に関しても、２番目乃至Ｋ番目のエッジについての向きＡｋを、ベクトルＥｋ−１の向きに対してベクトルＥｋの向きが右向きか左向きかの二値情報で表すことができる点はポリラインにも共通である。よって、ポリラインに関しては、境界ボックスを使用しないＬＲ規則に合わせたエッジの進行方向の変更ルールの適用は可能である。
【０２０７】
一方、境界ボックスの辺上に位置するエッジ及びその次のエッジに関する符号化の省略等、ポリゴンに関して上述した特徴の中にはポリラインへの適用に制限があるものがある。ここで、ポリライン図形においても、ポリゴンで説明した境界ボックスを利用した圧縮効果を得るために、次のような手法を導入することができる。
【０２０８】
（ａ）仮想ノードの追加によるポリライン図形のポリゴン化
仮想的なノード、エッジを追加して、ポリラインの起点ノードと終点ノードの間を結ぶポリラインを仮想的に生成して、当該ポリラインを仮想的にポリゴンにする。
【０２０９】
図１６はポリラインの例と、当該ポリラインから生成した仮想的なポリゴンの例とを示す模式図である。図１６（ａ）はポリライン３０を示しており、図１６（ｂ），（ｃ）はポリライン３０に少数の仮想的なノードとエッジを追加して生成したポリゴン３２ａ，３２ｂを示している。仮想ノードは基本的に１又は２個で足りるが、３個又は４個などとすることもできる。ポリライン３０がＫ＋１個のノード、Ｋ本のエッジ（ベクトルＥ１〜ＥＫ）からなるとして、図１６（ｂ）では、１つの仮想ノードＰＫ＋２、並びにポリラインの３０の起点Ｐ１及び終点ＰＫ＋１と仮想ノードＰＫ＋２とを結ぶ２本の仮想エッジＰＫ＋１ＰＫ＋２，ＰＫ＋２Ｐ１（ベクトルＥＫ＋１，ＥＫ＋２）を追加して、ポリゴン３２ａを形成している。そして、当該ポリゴン３２ａに対して境界ボックス３４ａが設定される。また、図１６（ｃ）では、３つの仮想ノードＰＫ＋２〜ＰＫ＋４、並びに４本の仮想エッジＰＫ＋１ＰＫ＋２，ＰＫ＋２ＰＫ＋３，ＰＫ＋３ＰＫ＋４，ＰＫ＋４Ｐ１（ベクトルＥＫ＋１〜ＥＫ＋４）を追加して、ポリゴン３２ｂを形成している。そして、当該ポリゴン３２ｂに対して境界ボックス３４ｂが設定される。ちなみに、仮想ノードの位置は、各仮想エッジの方向がＸ方向又はＹ方向となり、また仮想エッジがポリラインの各エッジに交差しないように定める。
【０２１０】
このポリラインのポリゴン化により、ポリゴンについて上述したエッジ方向符号化ルールやエッジ方向符号化オプションを利用して、ポリラインについても圧縮効率の向上を図ることが可能となる。
【０２１１】
ちなみに、仮想ノードは元のポリライン図形の終点から何点追加したかを符号化しておき、復元時に取り除く。
【０２１２】
或るポリラインの符号化にどのルールやオプションを採用するかは圧縮効率に応じて選択することができる。また、ポリゴン化には図１６（ｂ），（ｃ）に示したように異なる形が可能である。そのいずれを選択するかも圧縮効率に応じて選択することができる。
【０２１３】
（ｂ）ポリラインの部分ごとに境界ボックスを選択
複雑な形状のポリラインにおいては上記（ａ）によって十分な圧縮の効果が得られない場合があり得る。このような場合には、ポリラインの部分ごとに、符号化に有利な境界ボックスを設定する手法が有効である場合がある。
【０２１４】
図１７はポリラインの２つの部分それぞれに境界ボックスを設定する例を示す模式図である。図１７（ａ）は対象図形である１つのポリライン３６を示しており、図１７（ｂ）はポリライン３６を始点のノードＰ１から途中のノードＰＭまでの区間とノードＰＭから終点のノードＰＫ＋１までの区間とに分け、それぞれにて境界ボックス３８ａ，３８ｂを設定した様子を示している。
【０２１５】
符号化装置１は符号化に先立って、エッジの向きＡｋの解析を行い、ノードＰＭで分割された各区間でのエッジ方向が符号化ルールになるべく合致するようにノードＰＭの位置を定める。
【０２１６】
具体的には、分割されたポリラインの形状を境界ボックスとの関係に関し「上辺から左辺を経由して下辺に達する形状」、「左辺から下辺を経由して右辺に達する形状」、「下辺から右辺を経由して上辺に達する形状」、「右辺から上辺を経由して左辺に達する形状」の４パターンに分け、ポリラインの各区間の形状がそれらのいずれかのパターンになるべく合致するように分割ノードＰＭの位置を選ぶ。
【０２１７】
例えば、図１７の例では、起点ノードＰ１からノードＰＭまでの区間の形状については、 「下辺から右辺を経由して上辺に達する形状」が当てはまり、起点ノードＰＭからノードＰＫ＋１までの区間の形状については、「左辺から下辺を経由して右辺に達する形状」が当てはまる。
【０２１８】
各区間については上述したパターンのどれを適用するか、といった形式で符号化を行う。さらに各区間については、エッジ方向符号化ルールに基づいたエッジの向きの符号化を行い、追加情報として記録する。
【０２１９】
（３）本発明の図形圧縮符号化方法は上述のようにエッジを方向の情報と長さの情報とに分けて符号化する。ここで、上述の実施形態ではエッジの長さは整数である例を説明したが、本発明は基本的に当該長さが実数である場合に適用できる。特に方向の符号化に関しては、エッジの長さが整数であるか実数であるかにかかわらずデータ量の圧縮について基本的に同等の効果を得ることが可能である。
【産業上の利用可能性】
【０２２０】
本発明によれば、ポリゴン、ポリラインのデータ量の圧縮が図れることから、それら図形を扱う地理情報システム（geographic information system：ＧＩＳ）やＣＡＤ（computer-aided design）等にて、データ格納用の記憶装置等の容量を大幅に削減でき、また、ネットワーク経由での伝送データ量の削減、伝送時間の短縮が図れる。特に、カーナビ用途や、自動運転車両に対する地図データの配信や、車両搭載センサから取得される道路関連情報のうち、ベクトル図形化が可能な情報をサーバーへ送信する際に有効活用が可能となる。
【符号の説明】
【０２２１】
１  符号化装置、３  符号化図形データファイル、４  ファイルヘッダ、５  図形データ、６  図形ヘッダ、７  エッジ長テーブル、８  出現位置テーブル、９  エッジ長データ、１０  エッジ方向データ。
【図１】
2019053669.tif 000003
【図２】
2019053669.tif 000004
【図３】
2019053669.tif 000005
【図４】
2019053669.tif 000006
【図５】
2019053669.tif 000007
【図６】
2019053669.tif 000008
【図７】
2019053669.tif 000009
【図８】
2019053669.tif 000010
【図９】
2019053669.tif 000011
【図１０】
2019053669.tif 000012
【図１１】
2019053669.tif 000013
【図１２】
2019053669.tif 000014
【図１３】
2019053669.tif 000015
【図１４】
2019053669.tif 000016
【図１５】
2019053669.tif 000017
【図１６】
2019053669.tif 000018
【図１７】
2019053669.tif 000019