JPS61874A - ２値化画像デ−タ符号化方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は、道路地図など線画像データで表わされる画像
データの処理方式に係り、特にこのような画像データの
データ量を圧縮するだめの符号化方式に関する。

〔発明の背景〕

自動車用ナビゲーシ肩ンシステムなトニおいては、多数
の異なった範囲の道路地図な予じめ用意しておき、必要
に応じてそのうちの一つを任意に表示できるようにして
おかなければならない。

しかして、このため、従来は、フィルムや紙などに描い
た道路地図を用いていたので、地図の選択や表示切換が
面倒で、自動化が難めて困難であるという問題点があっ
た。

そこで、電子的な画像処理技術により、多数の道路地図
などを画像データ化し、これをメモリに予じめ記憶して
おき、必要に応じてＣＲＴなどにより画像再生するよう
にしたシステムが使用されるようになってきた。

ところで、上記したナビゲーシ四ンシステムなどでは、
かなり多くの地図を必要とする。従って、これをそのま
ま画像データ化すると、そのデータ量はかなり膨大なも
のとなり、メモリ容量が多く必要になってコストアップ
となり、実装が困難になるという問題点がある。

そこで、従来から種々の画像データ圧縮方式、例えばベ
クトル化方式やランレングスコード化方式などが提案さ
れているが、ベクトル化方式では情報量の損失が生じて
画質の低下が避けられず、ランレングスコード化方式で
は画像再生に時間が掛り過ぎ、ナビゲーシ層ンシステム
には不向キであるなどの欠点があった。

一方、このような欠点を除（ものとしては特開昭５８−
１３９５６７号公報による発明が提案されており、情報
量の損失を少くするという点では有効な提案であるが、
汎用性に重点が置かれているため、データ圧縮の面では
いささかもの足りない点がある。

〔発明の目゛的〕

本発明の目的は、上記した従来技術の欠点を除き、情報
量の損失を生じることなく充分なデータ圧縮が得られ、
しかも画像のリフレッシュ時間が短かくて済む２値化画
像データ符号化方式を提供するにある。

〔発明の概要〕 この目的を達成するため、本発明は、道路地図など線画
を主体とした画像の特性を活かし、画像を複数の線分の
集合とみなした上でそれぞれの線分をその始点位置デー
タと、この始点から順次隣接して連続する画素ごとの隣
接方向を表わすデータと、それぞれの線分の終点を表わ
すデータとによって表現するようにした点を特徴とする
。

〔発明の実施例〕

以下１本発明による２値化画像データ符号化方式につい
て、図示の実施例を参照して詳細に説明する。

第１図は本発明の一実施例で、１は画像データを読取る
べき地図（原画）、２は画像データ読取り用の入力部で
、ＣＣＤや撮像管を用いたテレビジョンカメラ、或いは
ドラムスキャナなどからなるもの、３は入力部２で読取
った画像データを２値化するための２値化部、４は画像
を線画化するための細線化部であり、さらに５は始点検
出部、６は符号化部、７は出力部、８はメモリであり、
これらの部分により符号化処理が行なわれる。

次に、この実施例の動作について説明する。

入力部２によって地図１から読取った画像データは２値
化部３によって白部分と黒部分とだけからなる２値化画
像データに変換された上でメモリに一旦、記憶される。

しかしながら、この時点で得られた画像データは、地図
１に対応して線画データになってはいるものの、その線
の幅がまちまちになっているから、これを細線化部４に
よって細線化処理を行ない、１画素分の幅の線画データ
とする。このようにして細線化処理を施こした画像デー
タの一例を第２図に示すっ 、　こ５して、地図１の細線化データがメモリ８つ中に
格納されたら、符号化処理に進む。

まず、始点検出部５で画像データの始点Ｓ（第２図）の
検出を行なう。この始点検出動作は、画像データの各画
素をＸ方向とｙ方向に順次走査し、最初に見つかった画
素の位置を検出することＫよって行なわれる。従って、
第２図の画像データでは始点Ｓ（４，２）となる。

こうして始点Ｓが検出できたら、その座標（４，２）を
メモリ８に記憶する。この場合、符号化すべき地図１の
大きさなどによって、このＸ座標とｙ座標を表わすのに
必要なビット数は異なってくるが、この実施例では、そ
れぞれ１バイトを用いることにし、従って、この始点Ｓ
を表わすデータは第３図に示すようになる。なお、この
第３図で、１１がＸ座標（４）を表わし、１２がｙ座標
（２）を表わす。

次に、この始点Ｓに連続する次の画素の隣接力°向を探
す。このときの隣接方向は第４図に示すように３×３の
マスクを用い、１から８までの８方向について調べる。

第２図のデータの場合、始点Ｓに第４図のマスクの中心
を一致させると、３の方向に次の画素が隣接しているこ
とが判る。こうして隣接方向が判別したら、これをデー
タ化するのであるが、このときには方向が全部で８種類
あり、さらに始点Ｓに隣接画素がない場合な０で表わす
ため４ビツトを用い、第２図の始点Ｓに隣接する画素（
４，３）は、その隣接方向が第４図の方向３であるから
、第５図の１３で示すように符号化されろう こうして隣接する画素の符号化が終了したら、その画素
は元の画像データ（細線化データ、例えば第２図）から
消去する。

画素（４，３）の符号化を終ったら、再び第４図に示し
た３×３のマスクを用い、このマスクの中心を画素（４
，３）に一致させ、連続する画素の隣接方向を調べる。

但し、始点Ｓにおける隣接方向の検出には８方向全部を
調べたが、始点Ｓ以外の画素からの場合には、８方向全
部ではな（て、起点となる画素（この場合は画素（４，
３）となる）が、さらにその前の画諏（この場合は画素
（４，２）となる）に対して隣接していた方向（この場
合は方向３）の延長方向と、その右方及び左方の３つの
方向−についてだけ調べるようにするのである。

これは、ナビゲーションシステムに必要な地図などでは
、線で表わした道路が主なデータであり、このような道
路データでは一般の線画と異なってその連続方向が急激
には変化しないという特徴をもっているので、これを利
用して符号化を簡単に行なえるようにしたものである。

つまり、画素（４，３）はその前の画素（始点Ｓ）から
３の方向に隣接しているので、次の画素（５，４）に対
しては、それと同じ３の方向と、画素（４，３）からみ
て前方左側の方向２及び前方右側の方向４だけを調べる
ようにしているのである。

さて、第２図の画像データでは画素（４，３）に連続す
る画素は座標（５，４）であり、これは前方左斜め方向
に当るので、第６図に示すように（０１）２　　と符号
化され、従って、第７図の１４のようなデータとなる。

なお、前方直進方向は第６図に示すように（１０）ｚと
符号化され、同じく前方右斜め方向は（１１）ｚと符号
化される。

こうして画素（５，４）の符号化を終ったら、上記した
ように、この画素は元の画像データから消去する。

次に、画素（５，４）に連続する画素としては、画素（
６，５）と画素（４，５）の２つの画素がある。

しかしながら、第４図の３×３マスクを用い１、これの
中心を画素（５，４）に一致させて隣接方向を調べると
、このときの画素（５，４）の直進方向は３Ｘ３マスク
の２方向であり、従って、その前方左斜め方向は１、そ
して前方右斜め方向は３になっており、これ以外の方向
は第６図から明らかなように無視されてしまう。従って
、このときには、画素（４，５）は方向１．２．３のい
ずれの隣接方向にもないため無視され、一方、画素（６
，５）はその隣接方向が直進方向、つまり第４図のマス
クの２の方向となっているため、第６図から（１０）２
として符号化され、この結果、第８図の１５で示すデー
タが付加される。そして、このあと、画素（６，５）は
消去される。

同様に、次の画素（７，６）も（１０）２として符号化
され、第８図の１６のデータとして付加される。

次に、画素（７，６）を消去し、再び第４図の３×３マ
スクを用い、その中心を（７，６）に一致させ、連続す
る画素を調べると、このときＫは、画素（７，６）の前
進方向、つまり３×３マスクの２の方向にも、それの左
側の１の方向にも、そして右側の３の方向にも画素が隣
接していない。

そこで、このときには、第６図から終点であると判断し
、この終点を表わす符号（００）２によってデータ化し
、第９図のデータ１７として付加する。

ここまでの符号化データは第９図のようになるが、これ
を１バイトづつ区切て示したのが第１０図である。なお
、最後尾の４ビツトは１バイト分に満たないので、その
後に０詰めをして１バイトにする。

ここまでの符号化が終ると、第２図の画像データは符号
化に伴なって画素が消去されているため。

第１１図に示すような画像データになっている。

一方、こうして符号化中の画素に終点が検出されると、
符号化部６（第１図）から再び始点検出部、５に動作が
戻り、画素（４，５）が次の始点Ｓとして検出され、以
下、画素（４，６）、（４，７）、が符号化されるので
、この第１１図の画像データによる符号化データは第１
２図のようになる。

従って、第２図の画像データは結局、第１０図と第１２
図から第１３図に示すように符号化して表わされること
になる。

そこで、出力部７（第１図）は、この第１３図のデータ
を第２図の画像データに対応するものとして、所定の識
別コードを付した上で不揮発性のメモリに書込む。そし
て、このメモリをナビゲーションシステムの画像再生装
置などに組込み、必要に応じて符号化データを選択して
読出し、画像再生を行なうのである。

次に、細線化部４、始点検出部５、それに符号化部６（
第１図）による画像データの符号化処理の詳細を第１４
図（αｌ　、　（Ａ＋のフローチャートによって説明す
る。なお、特に注釈しなかったが、以上の説明で画素と
呼んでいたのは、画像面で背景を白とした場合の黒とな
っている部分（反対でもよい）を指し、白画素のデータ
が“０”なら黒画素のデータは１”となっているもので
あり、以下の説明でもこれと同じで、画像面で線になっ
ている部分の画素は１”、そうでない部分の画素は０”
にしである。

さて、第１図では省略しであるが、この実施例ではコン
ピュータ（マイクロコンピュータなど）を含み、それに
格納しであるプログラムに従って符号化処理が行なわれ
るようになっており、このプログラムは２値化部２から
メモリ８に、地図１から読取った１フレ一ム分の画像の
格納が完□了したあとの所定のタイミングでスタートす
る。

１４０１でスタートすると、次の１４０２で２値化され
た画像データを配列Ａ（１，Ｊ）に入力し、　１４０３
で細線化して線幅を１画素分にする。

次に、１４０５から１４０８および１４１０でＡ（Ｉ、
Ｊ）のどの画素が１１”になっているか調べる。■。

Ｊはそれぞれ１から順に増やしていくため、初めに１″
が見つかった画素を線の始点Ｓとする。

このときのＩ、Ｊを１４１１で出力する。１４１２で今
出力した点（Ｉ、Ｊ）の連続方向を調べる。連続方向と
しては第４図に示す８方向を考える。点（Ｉ。

Ｊ）を中心に、その回りの点を調べ、どこが１″となっ
ているか探す。順番は方向１、方向２、方向３の順に調
べ、′１”が見つかるとその方向を１４１３で出力する
。８方向のうちどこにも連続点が見つからなければ、１
４１６で終点を表わす”ｏｏ″を出力する。１４１４で
連続点の方向を変数ＤＩＲに代入する。次に１４１９か
ら１４２３で、ＤＩＲ７）反時計方向に４５゜隣り会っ
た方向をＤＩＲＩに代入し、ＤＩＲ２にＤＩＲを代入し
、ＤＩＲ３にＩ）ＩＲＱ時計方向に４５°隣り合った方
向を代入する。１４１２で見つかった連続点が、更にＤ
ＩＲＩ、ＤＩＦＬ２、ＤＩＲ３のどの方向に連続してい
るかを調べる。１４２４でＤＩＲ２の方向に連続点が見
つかると、１４３１でｌＯ″と出力し、１４３２でＤＩ
ＲＫ　ＤＩ）１２を代入し１４１９へ行く。１４２５で
ＤＩＩ（３の方向に連続点が見つかると１４２９で１１
”と出力し、１４３０でＤＩＲにＤＩＲ３を代入し１４
１９へ行（。１４２６でＤＩＲＩの方向に連続点が見つ
かると１４２７で０１”出力し、１４２８でＤＩＲにＤ
ＩＲ１を代入し１４１９へ行く。ＤＩ　Ｒ１、ＤＩＩ’
ｔ２、ＤＩＲ３のいずれにも連続方向が見つからなけれ
ば、１４１６で”ｏｏ’を出力し、　　１４０４へ行く
。そして、　　１４０８で、Ｊ　＝　ＩＮＹ−ト１とな
った時点で、処理が終了する。

なお、ＩＮＸ　、　ＩＮＹは地図データの大きさである
。

この実施例によれば、画像データの全ての画素について
符号化する必要がないから、データ量を大幅に減少させ
ることができ、成る道路地図データについてみると、元
の画像データに対して数％以内に減少させることができ
たｇ　　′また、有意義な画素については、それらの全
てがデータとして符号化されるため、画像再生に際して
の情報の損失が無く、有意義な画素だけがデータ化され
ているから符号化データのメモリからの読出しや、それ
から画像データへの変換が短時間で行なえ、再生画像の
選択、切替えを高速で行なうことができる。

〔発明の効果〕

以上説明したように、本発明によれば、必要な情報に全
く損失を生じることなく、画像再生に必要なデータ量を
大幅に減少させることができるから、従来技術の欠点を
除き、必要な画像データを少ないメモｌｊ　［１で保持
することができ、しかも再生画像に画質低下を生じるこ
となく、高速での画像のりフレツシーが可能な２値化画
像データ符号化方式を提供することができる。

【図面の簡単な説明】

第１図は本発明による２値化画像データ符号化方式の一
実施例を示すブロック図、第２図ないし第１３図はそれ
ぞれ符号化処理動作中におけるデータの説明図、第１４
図（α）、＜ｈ＞は動作説明用のフローチャートである
。 １・・・・・・地図、２・・・・・・入力部、３・・・
・・・２値化部、４・・・・・・細線化部、５・・・・
・・始点検出部、６・・・・・・符号化部、７・・・・
・・出力部、８・・・・・・メモリ。 →為］々易

Claims (1)

【特許請求の範囲】
1. １、２値化画素データからなる画像データの処理方式に
   おいて、上記画像データを１画素幅で１以上の画素の連
   続からなる複数の線分データに分割し、これら複数の線
   分データのそれぞれを、線分データの始点の画素位置を
   表わすデータと、この始点の画素に順次連続する複数の
   画素のそれぞれの隣接方向を表わす複数のデータ群と、
   線分データの終点の画素を表わすデータの３種のデータ
   によつて表現するように構成したことを特徴とする２値
   化画像データ附号化方式。