JPH09259288A - 画素列の折線近似装置 - Google Patents

Abstract

(57)【要約】 【課題】 ２値画素列について折線近似ベクトルを発生
させる際の計算量を飛躍的に減少させ、処理時間を大幅
に短縮する。 【解決手段】 折線近似装置１０において、２値画素列
をチェーンコード列で記述したデータを記憶する記憶部
１２と、間引きベクトル列の始点と終点を設定する設定
部１４と、この始点と終点とを結ぶ線分の方向を表わす
単位ベクトルを求める単位ベクトル算出部１５と上で求
めた単位ベクトルと注目画素の近傍内の各画素の相対座
標を用いてコード距離を計算する距離算出部１６と、上
記始点から終点までの各コード値に従い、対応するコー
ド距離を順次加算する加算部１８と、このコード距離の
加算値と許容値を比較する比較部２０と、上記加算値が
許容値内であるか否かに応じて、始点、終点及び注目点
に対応する添数を設定する添数設定部２２と、逆の時に
間引きベクトルを発生する発生部２４とを備えている。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、画素列の折線近似
装置、特にチェーンコード列で記述された２次元画素列
から１又は２以上の間引きベクトルからなる折線近似ベ
クトルを作成する際に適用して好適な、画素列の折線近
似装置に関する。

【０００２】

【従来の技術】一般に、例えば、２値画像の輪郭等を２
値画素列で規定する場合、そのデータ量を削減するため
に、許容される範囲内で画素を間引いて２値画素列を折
線の間引きベクトル列に近似することが行われている。
このように、２値画素列から間引ベクトルからなる折線
近似ベクトルを作成する主な方法としては、分割・合成
法と追跡法がある。

【０００３】分割・合成法は、２値画素列について最初
に粗い近似（始点画素と終点画素を結ぶ等）を行い、順
次近似する画素列を、許容誤差を満たす範囲内で分割し
たり合成したりしながら、所要の近似精度のベクトルデ
ータを求める方法である。又、追跡法は、始点から所要
の近似精度を満足する範囲内で、順次画素をベクトル化
する方法である。

【０００４】上記２方法のいずれの場合にも、誤差の評
価方法としては、ミニマックス評価と最小２乗評価とが
用いられている。

【０００５】ミニマックス評価とは、図８に示すよう
に、複数の要素（画素）Ｐｉで構成される２値画素列に
おいて、始点を決定すると共に、任意の終点を予想し、
これら始点と予想した終点とを結ぶ近似線Ｌに対し、２
値画素列の各要素Ｐｉからこの近似線Ｌへのユークリッ
ド距離Ｅｉを算出し、該距離Ｅｉが、許容値εを越える
か否かで評価を行い、εを越えない範囲で求められる最
長の近似直線Ｌを１つの間引きベクトルとする方法であ
る。

【０００６】一方、最小２乗評価とは、図９に示す面積
｜Ｓ｜に相当する、近似線Ｌと２値画素列との２乗誤差
の総和｛Σ（Ｅi ² ）｝^1/2 が許容値εを越えないとい
う条件で評価を行い、そのときの最長の直線Ｌを同様に
間引きベクトルとする方法である。

【０００７】以上、現状における折線近似ベクトルの作
成方法の概要を述べたが、いずれの方法を採用するにし
ても、近似線Ｌと要素Ｐｉとの間の距離Ｅｉの距離を高
速に求めることが必要とされる。そして、この距離計算
は、図１０フローチャートに従って行う間引き処理の手
法で折線近似ベクトルを作成する過程で行うのが一般的
である。

【０００８】以下、この間引き処理について説明する
が、まず使用する記号の説明をしておく。ここでは、便
宜上、ベクトルをアルファベットの大文字で表記する。

【０００９】 Ｖi ＝（ｘ1i，ｘ2i），（ｉ＝１，２，…，ｎ） …（１）

【００１０】ここで、Ｖi は、実数ｘ1iとｘ2iで規定さ
れる２次元のベクトル座標列を表わし、i はデータ番号
を表わす添字で、１〜ｎまでの自然数である。

【００１１】ε；間引きベクトル列の元のベクトル列に
対する最大誤差で、正の実数である。

【００１２】‖ ‖；ユークリッドノルム（距離）例
えば、ベクトルＡに対して‖Ａ‖＝（Ａ，Ａ）^1/2 であ
る。

【００１３】（ ， ）；ベクトル内積 Ｐ；ベクトル表記した始点 Ｑ；ベクトル表記した終点 Ｒ；ベクトル表記した比較点

【００１４】

【数１】

【００１５】Ｐ＝（ｐ1 ，ｐ2 ）；点Ｐの成分表示 Ｑ＝（ｑ1 ，ｐ2 ）；点Ｑの成分表示 Ｒ＝（ｒ1 ，ｒ2 ）；点Ｒの成分表示

【００１６】まず、ベクトル列の間引き処理を開始する
初期値を設定するべく、以降の繰返し計算で利用する添
数ｉ、ｊ、ｋを、それぞれｉ＝１、ｊ＝１、ｋ＝２とす
る（ステップＳ３１）。この時、ステップＳ３２で設定
される始点Ｐ、比較点Ｒ、及び終点Ｑはベクトル列の最
初の３点Ｖ１、Ｖ２、Ｖ３となる。

【００１７】次に、図１１に示すように、比較点Ｒから
線分ＰＱ（前記近似線Ｌに当る）へ下ろした垂線の足を
ベクトルＳとし、このとき、次の（２）式によりＲＳ間
の距離‖Ｒ−Ｓ‖を求めると共に、この距離が許容値ε
の範囲内か否かを比較する（ステップＳ３３、Ｓ３
４）。

【００１８】

【数２】

【００１９】上記ステップＳ３４で、距離‖Ｒ−Ｓ‖が
許容範囲内のときは、比較点を１つ先に進めるため、添
数ｊを１つ増やす（ステップＳ３５）。この時、もし添
数ｊと添数ｋがｊ＜ｋの関係を満たしているとすると、
このｊによって再び比較を行うことができ、比較点Ｒを
再設定するために、ステップＳ３２へ戻る（ステップＳ
３６）。これは、図１２において、基準となる始点Ｐ
（＝Ｖi ）、終点Ｑ（＝Ｖi+K ）はそのままにして、両
者の間にある比較点Ｒ（＝Ｖi+J ）のみ１つ先に進める
操作を表わしている。この場合には、前述の（２）式を
用いて上と全く同様にＲＳ間の距離を算出することがで
き、この操作は、距離‖Ｒ−Ｓ‖が、許容値ε以上とな
るか、もしくは添数ｊと添数ｋが等しくなる迄繰返され
ることとなる。

【００２０】ここにおいて、上記ステップＳ３５でｊを
１増やした結果、ステップＳ３６でｋと一致した場合、
即ち比較点Ｒが終点Ｑと一致した場合は、ステップＳ３
７でｋ←ｋ＋１として、終点の候補であるベクトルＶi+
k を１つだけ先に延ばす。この結果として、Ｖi+k が対
象としている２値画素列の最終点を越えてしまった場
合、即ち、ｉ＋ｋがデータ総数ｎを超えてしまった場合
には（ステップＳ３８）、Ｖi+k-1 を最終点として登録
し処理を終了する（ステップＳ３９）。

【００２１】一方、Ｖi+k が対象画素列内におさまって
いる場合には、再び上記と同様の間引き処理を行うべ
く、ｊを１に戻し（ステップＳ４０）、ステップＳ３２
に戻って始点Ｐ、終点Ｑ及び比較点Ｒの再設定を行う。

【００２２】又、前記ステップＳ３４で、比較点Ｒと近
似線Ｌとの距離が許容誤差εを超えているＮｏの場合
は、１つ手前の点ベクトルＶi+k-1 を間引きベクトル列
に追加し（ステップＳ４１）、この点を次の間引きベク
トル列の始点として登録すると共に、これを登録点の次
の点であるｉ＋ｋの値とし、且つ、ｊ、ｋもそれぞれ初
期値１、２に戻し（ステップＳ４２、４３）、次のステ
ップＳ４４でそのときのｉ＋ｋがデータ総数ｎを超えて
いるか否かを判定し、超えていないＮｏの場合には、そ
のときのｉ、ｊ、ｋの各添数を用いて、前記ステップＳ
３２に戻り、それぞれ始点Ｐ、比較点Ｒ、終点Ｑを設定
し、同様の処理を繰返す。

【００２３】更に、上記ステップＳ４４でｉ＋ｋがｎを
超えているＹｅｓの場合には、前記と同様に１つ手前の
点ベクトルＶi+k-1 を間引きベクトル列の最終点として
登録し、処理を終了する（ステップＳ３９）。

【００２４】以上詳述したステップＳ３１〜Ｓ４３まで
の処理を行うことにより、もとの２値画素列からのずれ
が許容誤差εを超えない最も効率的な間引きベクトル列
を順次決定することができる。

【００２５】その結果、図１３に示すような、最大誤差
が±ε内に収まる間引きベクトルＬ１、Ｌ２、Ｌ３から
なる折線近似ベクトルを求めることが可能となる。

【００２６】

【発明が解決しようとする課題】しかしながら、上述し
た従来の方法で折線近似ベクトルを求めるためには、終
点Ｑを１つ延ばす毎に、ＰとＱの間にある比較点Ｒに対
して全て直線ＰＱとの間の距離を算出する処理を繰り返
さなければならないため、計算量が膨大となり、処理時
間がかかり過ぎるという問題があった。

【００２７】本発明は、前記従来の問題点を解決するべ
くなされたもので、２値画素列について折線近似ベクト
ルを発生させる際の計算量を飛躍的に減少させ、処理時
間を大幅に短縮することができる画素列の折線近似装置
を提供することを課題とする。

【００２８】

【課題を解決するための手段】本発明は、２値画素列か
ら許容誤差内に収まる画素を間引いて作成される間引き
ベクトルからなる折線近似ベクトルを発生させる画素列
の折線近似装置において、２値画素列をチェーンコード
列で記述したデータを記憶する手段と、２値画素列の範
囲内で間引きベクトルの始点と終点とを設定する手段
と、設定した始点と終点とを結ぶ線分と同一の傾斜角の
線分を、注目画素の中心に一致させた場合の該線分から
各コードに対応する注目画素の近傍８画素の各中心まで
のコード距離を計算する手段と、始点から終点までの画
素列を記述した各コード値に従い、対応するコード距離
を順次加算する手段と、始点から終点までの画素列につ
いて、コード距離の加算値が許容誤差内にあるか否かを
判定する手段と、コード距離の加算値が全て許容誤差内
にあると判定された場合に、前記終点の次の画素を新た
な終点に更新する手段と、コード距離の加算値が許容誤
差を超えたと判定された場合に、前記終点の１つ前の画
素を終点と決定し、間引きベクトルを発生させる手段
と、を備えた構成とすることにより、前記課題を解決し
たものである。

【００２９】

【発明の実施の形態】本発明者等は、種々検討した結
果、間引き前の点列（２値画素列）をチェーンコード列
で記述する場合には、個々の比較点に対する直接の距離
計算を省き、効率的に間引きベクトル列を発生させるこ
とができることを知見した。

【００３０】ここで、チェーンコードとは、フリーマン
（Ｆreeman) により考え出された、２値画像の輪郭等の
２値画素列を記述する際に使用するコード番号であり、
図１に示すように３×３の９画素を考え、斜線を付した
中心画素を注目画素に割り当て、この注目画素に連結し
ている次の画素が、中心画素の周囲８近傍座標の何処に
くるかにより、その位置と方向を規定するための、例え
ば１〜８の番号である。

【００３１】このように、次の画素のコードが確定した
ら、その確定した画素に注目画素を移し、同様に次の画
素のコードを確定する操作を繰り返すことにより、２値
画素列を１〜８の数字からなるコード列で記述すること
ができる。従って、最初の一点目を登録し、２点目から
１〜８の数字の列で、例えば２、３、３、・・・のよう
にして、画素列を記述することができる。上記チェーン
コードとしては、図１に示すような時計廻り近傍系とし
ても、又図２のように反時計廻りの近傍系とすることも
できる。

【００３２】今、図１に示すように時計廻りの近傍系を
採用する場合を考えると、チェーンコード列では、上述
した如く次点は常に注目画素の近傍８座標のいずれかと
なる。従って、予め各コードに対応して、比較点が始点
と終点を結ぶ線分（近似線）から、どれだけ近付くか
（あるいは遠ざかるか）を計算して距離（以下コード距
離ともいう）を求めておくことにより、間引きベクトル
の始点と終点の間にある複数の比較点について、予め求
めておいた上記距離を加算する処理を繰り返すことによ
り、上記線分から各比較点までの距離（以下、実距離と
もいう）を順次求めていくことができる。

【００３３】これを具体的に説明すると、次のようにな
る。図３に示すように始点Ｐ、終点Ｑを結ぶ直線を平行
移動し、比較点（注目画素）Ｒの中心を通るようにした
線分をＬ′とし、該比較点Ｒの近傍のコード番号を付し
た黒点で示した各画素の中心点と線分Ｌ′との各々の距
離であるコード距離をＤ１〜Ｄ８とする。

【００３４】又、ｘ方向、ｙ方向の各画素間の距離をｄ
x 、ｄy とし、Ｌの始点Ｐから終点Ｑへと向かう向きを
示す単位ベクトルを（ｅx ，ｅy ）とすると、コード距
離Ｄ１〜Ｄ８は、図３における近傍中心に対する近傍内
の各画素の相対座標を表わすベクトルと（ｅx ，ｅy ）
の組からなる２×２行列の行列式を求めることにより得
られる。なぜならば、図４に示すように、この行列式の
値は上の２ベクトルのなす平行四辺形の面積に符号を付
けた値となるが、（ｅx ，ｅy ）が単位ベクトルである
ことにより、その長さは１に等しく、結局上で求めた行
列式の値の絶対値は、各画素の相対座標を表わすベクト
ルの終点からＬへ降ろした垂線の長さに等しく、その符
号は、各画素の相対座標を表わすベクトルが（ｅx ，ｅ
y ）に対して左廻りの位置にあるのか、あるいは右廻り
の位置にあるのかを示すこととなる。

【００３５】具体的に時計廻りの近傍系の場合につい
て、Ｄ１〜Ｄ８を求めてみると、以下のようになる。

【００３６】

【数３】

【００３７】以上のようにして予めコード距離Ｄ１〜Ｄ
８を求めておくことにより、例えば２値画素列の中心が
図５に模式的に示したようになっている場合であれば、
比較点Ｒ１、Ｒ２、Ｒ３の各コードから、予め求めてお
いた距離Ｄｒ₁ 、Ｄｒ₂ 、Ｄｒ₃ （全てＤ１〜Ｄ８のい
ずれかで与えられる）を単に加算するだけで、各比較点
が、許容誤差ε以内に収まっているか否かを判定するこ
とが可能となる。

【００３８】従って、本発明においては、前述の如く、
２値画素列をチェーンコード列で記述すると共に、間引
きベクトルの始点と終点を設定し、その間に存在する画
素列（比較点）について、始点と終点とを結ぶ線分から
の実距離を、前記図３に示した方法で予め求めておいた
各コードに対応するコード距離Ｄ１〜Ｄ８の距離を、上
記画素列のコード値に従って、始点側から順次加算する
だけで求めることができるようにしたので、各比較点に
ついて、上記実距離を計算する際の計算量を大幅に削減
することが可能となり、処理時間を大幅に短縮すること
が可能となる。

【００３９】以下、図面を参照して、より具体的な本発
明の実施の形態の例を詳細に説明する。

【００４０】図６は、本発明に係る一実施の形態の画素
列の折線近似装置の概略構成を示すブロック図である。

【００４１】本実施の形態の折線近似装置１０は、２値
画素列から許容誤差内に収まる画素を間引いて作成され
る１以上の間引きベクトルからなる折線近似ベクトルを
発生させる機能を有しており、対象の２値画素列全体を
チェーンコード列で記述したデータを記憶する記憶部１
２と、上記２値画素列の範囲内で間引きベクトルの始点
と終点とを設定する始点・終点設定部１４と、始点と終
点を結ぶ線の向きを示す単位ベクトルを求める単位ベク
トル算出部１５と、設定した始点と終点とを結ぶ線分か
らその方向に示す単位ベクトルを求め、これと各コード
に対応する相対座標値からコード距離を計算するコード
距離算出部１６と、上記始点から終点までの画素列を記
述した各コード値に従い、上記算出部１６で算出した各
コードに対応する上記コード距離を順次加算するコード
距離加算部１８と、上記始点から終点までの各画素につ
いて、上記加算部１８で算出したコード距離の加算値が
許容誤差内にあるか否かを判定する比較部２０と、この
比較部２０において、上記コード距離の加算値が全て許
容誤差内にあると判定された場合には、終点の添数を１
つ増やし次の画素とすると共に、比較点をリセットして
始点の次の画素とする処理を行い、許容誤差を超えた場
合には、新たに始点、終点を設定するべく添数をリセッ
トする処理を行う添数設定部２２と、上記比較部２０で
加算値が許容誤差を超えていると判定された場合に、そ
の終点より１つ前の画素を終点と決定し、間引きベクト
ルを発生させる間引きベクトル発生部２４とを備えてお
り、その間引きベクトルを前記記憶部１２に記憶するよ
うになっている。

【００４２】本実施の形態においては、前記図１０に示
したフローチャートに相当する図７に示したフローチャ
ートに従って、間引きベクトルを作成し、１又は２以上
の間引きベクトル列からなる折線近似ベクトルを発生さ
せることができる。なお、ここでもアルファベットの大
文字は原則としてベクトルを表わす。

【００４３】まず、対象とする２値画素のベクトル列全
てをチェーンコード列で記述して上記記憶部１２に記憶
すると共に、該ベクトル列の最初の３点をそれぞれ始
点、比較点、終点とするべく添数の初期設定を行う（ス
テップＳ１）。

【００４４】ここで、データ総数ｎの画素からなるベク
トル列をチェーンコード化して得られるチェーンコード
列をＣｉ（ｉ＝１，２，…，ｎ）とすると、始点座標Ｖ
１＝（ｘ11，ｘ21）を用いて、ｌ点目のＱの座標は次の
（１１）式のようにして求めることができる。なお、Ｃ
ｉは前述した１〜８のいずれかの数値を表わす。

【００４５】

【数４】

【００４６】上記（１１）式におけるｘ［Ｃｉ］、ｙ
［Ｃｉ］は、コード値が前記図１に示したように時計廻
りで設定されている場合には、次の各値を取ることにす
る。

【００４７】 （ｘ［１］，ｙ［１］）＝（−ｄx ，ｄy ）， （ｘ［２］，ｙ［２］）＝（０，ｄy ）， （ｘ［３］，ｙ［３］）＝（ｄx ，ｄy ）， （ｘ［４］，ｙ［４］）＝（ｄx ，０）， （ｘ［５］，ｙ［５］）＝（ｄx ，−ｄy ）， （ｘ［６］，ｙ［６］）＝（０，−ｄy ）， （ｘ［７］，ｙ［７］）＝（−ｄx ，−ｄy ）， （ｘ［８］，ｙ［８］）＝（−ｄx ，０）

【００４８】ここで、ｄx 、ｄy は、コード距離の計算
方法を説明する際に用いたｘ方向、ｙ方向の各画素間の
距離である。

【００４９】又、前記図２に示した反時計廻りの場合
は、次の各値とする。

【００５０】 （ｘ［１］，ｙ［１］）＝（−ｄx ，ｄy ）， （ｘ［２］，ｙ［２］）＝（−ｄx ，０）， （ｘ［３］，ｙ［３］）＝（−ｄx ，−ｄy ）， （ｘ［４］，ｙ［４］）＝（０，−ｄy ）， （ｘ［５］，ｙ［５］）＝（ｄx ，−ｄy ）， （ｘ［６］，ｙ［６］）＝（ｄx ，０）， （ｘ［７］，ｙ［７］）＝（ｄx ，ｄy ）， （ｘ［８］，ｙ［８］）＝（０，ｄy ）

【００５１】続いて、始点・終点設定部１４でチェーン
コード値を利用して、始点Ｖi 、比較点Ｖi+j 、終点Ｖ
i+k の座標値を求める（ステップＳ２）。これは、前記
（１１）式を用いて帰納的に求めることができる。又、
始点と終点を結ぶ直線Ｌと比較点との距離を格納する変
数Λを初期化する（ステップＳ３）。次に単位ベクトル
算出部１５では、始点の座標を（ｐx ，ｐy ）、終点の
座標を（ｑx ，ｑy ）とするとき、次の（１２）、（１
３）式を用いて単位ベクトル（ｅx ，ｅy ）を求める
（ステップＳ４）。

【００５２】 ｅx ＝（ｑx −ｐx ）／｛（ｑx −ｐx ）² ＋（ｑy −ｐy ）² ｝^1/2 …（１２） ｅy ＝（ｑy −ｐy ）／｛（ｑx −ｐx ）² ＋（ｑy −ｐy ）² ｝^1/2 …（１３）

【００５３】又、同時に、上記算出部１６で、上で求め
た上記（１２）、（１３）式の結果を用いて、前記図３
に示したものと同様のコード距離Ｄ１〜Ｄ８を予め算出
し、記憶しておく。

【００５４】続いて、最初の比較点について直線Ｌと比
較点との距離わ表わすΛの値を、Λにコード距離Ｄｃ_i
を加えることにより求め（ステップＳ６）、これの絶対
値と許容誤差εと比較し（ステップＳ７）、ε内であれ
ば、添数ｊに１を加える（ステップＳ８）。ここでｊが
ｋより小の場合には、まだ比較点が終点と一致していな
いのでステップＳ６に戻り、同様の加算処理を繰返すこ
とができる（ステップＳ９）。

【００５５】ステップＳ９でｊとｋが等しくなった場合
は、比較点と終点が一致していることから、始点と終点
の間の全ての比較点が許容誤差ε内に入っていることと
なる。この場合には、ｋに１に加える（ステップＳ１
０）。この時、もしｉ＋ｋがデータ総数ｎを超えてしま
う場合は、ｋに１を加える前の点、即ち前記の終点が総
データの最終点となっている場合に相当する。従って、
この場合には、前記の終点Ｖi+k-1 （ｋに１を加えた後
なので１を引いてもとに戻す必要がある）を最終点とし
て間引きベクトル列に登録して（ステップＳ１２）処理
を終了する。

【００５６】一方、ｉ＋ｋの値がデータ総数ｎ以下の場
合は、比較点をリセットするためにｊ＝１とし（ステッ
プＳ１３）、新たに設定された終点Ｖi+k の値を次の
（１４）式から求める（ステップＳ１４）。

【００５７】

【数５】

【００５８】ここでステップＳ３に戻り、再び同様の繰
返し計算を行っていく。前に戻り、ステップＳ７で直線
Ｌと比較点との距離を示す変数Λの絶対値がεを超えて
しまった場合の処理は、次の様になる。

【００５９】この場合は、終点を延ばし過ぎているた
め、比較点の中で許容誤差εの範囲に収まりきれなくな
ったことを示している。従って、始点を１つ前に戻した
点Ｖi+k-1 が始点・終点間の全ての比較点が許容誤差ε
内に収まるような終点のうちで始点から最も離れたもの
となる。従ってこれを間引きベクトル列に追加し（ステ
ップＳ１５）、前の計算過程での終点を始点とした次の
処理を行うために添数ｉ、ｋの設定を行う（ステップＳ
１６、Ｓ１７）。

【００６０】この時、前記と同様にｉ＋ｋがデータ総数
ｎを超えるか否かを調べ、ｎ以下である場合には、比較
点を表わす添数ｊをリセットし（ステップＳ１９）、比
較点Ｖi+j と終点Ｖi+k の座標値を次の（１５）、（１
６）式によって求める（ステップＳ２０、Ｓ２１）。

【００６１】

【数６】

【００６２】そして、再びステップＳ３に戻り、対象画
素列間引きのための、コード距離加算等の処理を続行す
る。

【００６３】又、ｉ＋ｋがｎを超える場合には、上記ス
テップＳ１２と全く同様にＶi+k-1を最終点として登録
し、処理を終了する（ステップＳ１２）。

【００６４】以上詳述した如く、間引きベクトル列を作
成して折線近似ベクトルを発生させる場合、従来は各比
較点Ｒについて、その都度実際の距離計算を実行してい
たのに対し、本実施の形態によれば、比較点Ｖi+j のコ
ード番号Ｃi+j に対応する上記Ｄ１〜Ｄ８のコード距離
を、単に加算する処理を繰り返すだけで、目的とする、
例えば前記図１３に示したものと同様に折線近似ベクト
ルを発生させることができる。

【００６５】従って、従来の計算方法に比べ、計算負荷
を大幅に削減することが可能となり、同一の２値画素列
について実際に比較したところ、本実施の形態によって
計算負荷を従来の約１／７にすることができた。

【００６６】以上、本発明について具体的に説明した
が、本発明は、前記実施の形態に示したものに限られる
ものでなく、その要旨を逸脱しない範囲で種々変更可能
である。

【００６７】例えば、折線近似装置の具体的な構成とし
ては、前記実施の形態に示したものに限定されない。

【００６８】

【発明の効果】以上説明したとおり、本発明によれば、
２値画素列について折線近似ベクトルを発生させる際の
計算量を飛躍的に減少させ、処理時間を大幅に短縮する
ことができる。

【図面の簡単な説明】

【図１】チェーンコード列の記述に用いるコード値の一
例を示す説明図

【図２】チェーンコード列の記述に用いるコード値の他
の一例を示す説明図

【図３】コード距離の算出原理を示す線図

【図４】単位ベクトルを利用したコード距離の算出原理
を示す線図

【図５】コード距離を用いる実距離の算出原理を示す線
図

【図６】本発明に係る一実施の形態の折線近似装置の概
略構成を示すブロック図

【図７】実施の形態の折線近似装置による処理手順を示
すフローチャート

【図８】間引きベクトルを作成する従来方法を示す線図

【図９】間引きベクトルを作成する他の従来方法を示す
線図

【図１０】折線近似ベクトルを作成する従来の手順を示
すフローチャート

【図１１】最初に設定する始点、終点と比較点との関係
を示す線図

【図１２】２番目以降に設定する始点、終点と比較点と
の関係を示す線図

【図１３】最終的な折線近似ベクトルの一例を模式的に
示す線図

【符号の説明】

１０…折線近似装置 １２…記憶部 １４…始点・終点設定部 １５…単位ベクトル算出部 １６…コード距離算出部 １８…コード距離加算部 ２０…比較部 ２２…添数設定部 ２４…間引きベクトル発生部

───────────────────────────────────────────────────── フロントページの続き (72)発明者 高倉 章 東京都新宿区市谷加賀町一丁目１番１号 大日本印刷株式会社内 (72)発明者 飯沼 輝明 東京都新宿区市谷加賀町一丁目１番１号 大日本印刷株式会社内

Claims (1)

【特許請求の範囲】
1. 【請求項１】２値画素列から許容誤差内に収まる画素を
   間引いて作成される間引きベクトルからなる折線近似ベ
   クトルを発生させる画素列の折線近似装置において、 ２値画素列をチェーンコード列で記述したデータを記憶
   する手段と、 ２値画素列の範囲内で間引きベクトルの始点と終点とを
   設定する手段と、 設定した始点と終点とを結ぶ線分と同一の傾斜角の線分
   を、注目画素の中心に一致させた場合の該線分から各コ
   ードに対応する注目画素の近傍８画素の各中心までのコ
   ード距離を計算する手段と、 始点から終点までの画素列を記述した各コード値に従
   い、対応するコード距離を順次加算する手段と、 始点から終点までの画素列について、コード距離の加算
   値が許容誤差内にあるか否かを判定する手段と、 コード距離の加算値が全て許容誤差内にあると判定され
   た場合に、前記終点の次の画素を新たな終点に更新する
   手段と、 コード距離の加算値が許容誤差を超えたと判定された場
   合に、前記終点の１つ前の画素を終点と決定し、間引き
   ベクトルを発生させる手段と、を備えていることを特徴
   とする画素列の折線近似装置。