JPH0743764B2 - 線図形折線化処理装置 - Google Patents
線図形折線化処理装置Info
- Publication number
- JPH0743764B2 JPH0743764B2 JP2208118A JP20811890A JPH0743764B2 JP H0743764 B2 JPH0743764 B2 JP H0743764B2 JP 2208118 A JP2208118 A JP 2208118A JP 20811890 A JP20811890 A JP 20811890A JP H0743764 B2 JPH0743764 B2 JP H0743764B2
- Authority
- JP
- Japan
- Prior art keywords
- pixel
- data
- block
- straight line
- connection data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T11/00—2D [Two Dimensional] image generation
- G06T11/20—Drawing from basic elements, e.g. lines or circles
- G06T11/203—Drawing of straight lines or curves
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Image Processing (AREA)
- Image Analysis (AREA)
Description
【産業上の利用分野】 この発明は、線図形画像を２値ディジタルデータとして
読み込み、２値ディジタルデータを折線データに変換す
る線図形折線化処理装置に関するものである。
読み込み、２値ディジタルデータを折線データに変換す
る線図形折線化処理装置に関するものである。
線図形画像を折線化して折線データで表すことは、デー
タ圧縮あるいはデータの再利用といった面で、従来から
よく行われている。従来からの折線化処理の手法は、 画像を細線化して、画素を追跡する方法（特開平１
−134682号公報，特開平１−142880号公報）。 画像の輪郭線を抽出し、その輪郭線の中心線を求め
る方法 画像を小さな正方格子に分割し、各正方格子内の局
所パターンを識別する方法（特開昭62−191988号公報） という３つの主な手法がある。 これらの手法は、いづれも画像全体をアクセスする画像
処理を必要とし、処理時間が長くなり、また、処理の
間、画像を常にメモリ上に置いておく必要があるため
に、大容量のメモリを必要としていた。 また、ラン情報から折線化を行う試みもなされている
（特開昭63−45687号公報）。この方法は、ｍライン目
のランの重心値とｎライン前（ｍ−ｎライン）のランの
重心値の変化を調べることで、傾きの異なる直線線分を
検出している。しかし、この方法は画像中のランという
局所的な情報だけに頼っているために、そのランが折線
化していい画像なのかどうかを判定することができな
い。例えば、線図形中に使用される塗りつぶした矢印等
は、ランの情報のみを見ているだけでは、その形状を把
握することは不可能である。
タ圧縮あるいはデータの再利用といった面で、従来から
よく行われている。従来からの折線化処理の手法は、 画像を細線化して、画素を追跡する方法（特開平１
−134682号公報，特開平１−142880号公報）。 画像の輪郭線を抽出し、その輪郭線の中心線を求め
る方法 画像を小さな正方格子に分割し、各正方格子内の局
所パターンを識別する方法（特開昭62−191988号公報） という３つの主な手法がある。 これらの手法は、いづれも画像全体をアクセスする画像
処理を必要とし、処理時間が長くなり、また、処理の
間、画像を常にメモリ上に置いておく必要があるため
に、大容量のメモリを必要としていた。 また、ラン情報から折線化を行う試みもなされている
（特開昭63−45687号公報）。この方法は、ｍライン目
のランの重心値とｎライン前（ｍ−ｎライン）のランの
重心値の変化を調べることで、傾きの異なる直線線分を
検出している。しかし、この方法は画像中のランという
局所的な情報だけに頼っているために、そのランが折線
化していい画像なのかどうかを判定することができな
い。例えば、線図形中に使用される塗りつぶした矢印等
は、ランの情報のみを見ているだけでは、その形状を把
握することは不可能である。
本発明は、上記問題を解決するためになされたものであ
り、折線化すべき部分を効率よく見出し、その部分のみ
を折線化処理を施せばよいようにし、画像全体をアクセ
スする時間のかかる画像処理を行う必要のない効率的な
線図形折線化処理装置を提供することを目的とするもの
である。
り、折線化すべき部分を効率よく見出し、その部分のみ
を折線化処理を施せばよいようにし、画像全体をアクセ
スする時間のかかる画像処理を行う必要のない効率的な
線図形折線化処理装置を提供することを目的とするもの
である。
本発明の折線化処理装置は、２値ディジタル画像を主走
査方向に走査して、背景画素（白画素）から画像の画素
（黒画素）に変化した画素を開始点の画素とし、画像の
画素から背景画素に変化した画素を終了点の画素とする
画素連結データ（第４図）を生成する画素連結データ生
成手段（第１図３）と、画素連結データの相互の関係を
調べ、画素連結データ同士が上下方向（副走査方向）に
ただ一つの画素連結データとのみ隣接しており、画素連
結データの長さの変化があるしきい値以内で、かつ一定
の方向に沿って配置された位置関係を有するものを連結
して画素ブロックデータを生成する画素ブロックデータ
生成手段（第１図５）と、画素ブロックデータを構成す
る画素連結データの長さを調べ、同一の長さの画素連結
データを一定以上の割合で含む画素ブロックデータを直
線線分を表すものと判定し、さらにその画素ブロックデ
ータの外接矩形の縦横比があるしきい値より大きいか否
かを判定する直線線分判定手段（第１図７）と、直線線
分判定手段により画素ブロックのデータが直線線分であ
ると判定された場合において、直線線分判定手段により
前記縦横比がしきい値より大きいと判定されたとき、そ
の画素ブロックデータの上部の画素連結データと下部の
画素連結データに基づき直線近似データを生成し、直線
線分判定手段により前記縦横比がしきい値未満であると
判定されたとき、画素ブロックデータにおけるブロック
内で左端を表す点と右端を表す点のデータに基づき直線
近似データを生成する直線近似処理手段（第１図８）と
を備えている。
査方向に走査して、背景画素（白画素）から画像の画素
（黒画素）に変化した画素を開始点の画素とし、画像の
画素から背景画素に変化した画素を終了点の画素とする
画素連結データ（第４図）を生成する画素連結データ生
成手段（第１図３）と、画素連結データの相互の関係を
調べ、画素連結データ同士が上下方向（副走査方向）に
ただ一つの画素連結データとのみ隣接しており、画素連
結データの長さの変化があるしきい値以内で、かつ一定
の方向に沿って配置された位置関係を有するものを連結
して画素ブロックデータを生成する画素ブロックデータ
生成手段（第１図５）と、画素ブロックデータを構成す
る画素連結データの長さを調べ、同一の長さの画素連結
データを一定以上の割合で含む画素ブロックデータを直
線線分を表すものと判定し、さらにその画素ブロックデ
ータの外接矩形の縦横比があるしきい値より大きいか否
かを判定する直線線分判定手段（第１図７）と、直線線
分判定手段により画素ブロックのデータが直線線分であ
ると判定された場合において、直線線分判定手段により
前記縦横比がしきい値より大きいと判定されたとき、そ
の画素ブロックデータの上部の画素連結データと下部の
画素連結データに基づき直線近似データを生成し、直線
線分判定手段により前記縦横比がしきい値未満であると
判定されたとき、画素ブロックデータにおけるブロック
内で左端を表す点と右端を表す点のデータに基づき直線
近似データを生成する直線近似処理手段（第１図８）と
を備えている。
本発明は、前記目的を達成するために、画像を階層的な
データ構造に変換して、そのデータ構造を用いて折線化
処理を行う。すなわち、画像を画素連結データと、画素
連結データの集まりである画素ブロックデータにより表
現されるようにし、これらのデータをもとに折線画像を
求める。 画素連結データ生成手段（３）で、画素連結データを生
成する。画素連結データは、２値ディジタル画像を主走
査方向に走査して、背景画素（白画素）から画像の画素
（黒画素）に変化した画素を開始点の画素とし、画像の
画素から背景画素に変化した画素を終了点の画素とする
ものでありいわゆる画像のラン情報である。 画素ブロックデータ生成手段は画素ブロックデータを生
成する。画素ブロックデータとは、所定の関係を有する
画素連結データの集まりをいう。その所定の関係として
は、画素連結データ同士が上下方向（副走査方向）にた
だ一つの画素連結データとのみ隣接しており、画素連結
データの長さがあまり変らず、一定の方向に沿って配置
された位置関係を有するものである。 直線線分判定手段は、各画素ブロックデータを調べ、画
素ブロックが直線線分を表すものかどうかを判定する。
調べるデータとしては、そのブロックに属する画素連結
データの長さの分布、ブロックの外接矩形の大きさなど
の直線の表現に関連する情報がある。また、ブロックの
外接矩形の縦横比を求め、その縦横比がある値以上であ
るか否かを判定する。 直線近似処理手段は、画素ブロックが直線線分であると
判定された場合において、直線線分判定手段により前記
縦横比がしきい値より大きいと判定されたとき、その画
素ブロックデータの上部の画素連結データと下部の画素
連結データに基づき直線近似データを生成し直線線分判
定手段により前記縦横比がしきい値末端であると判定さ
れたとき、画素ブロックデータにおけるブロック内で左
端を表す点と右端を表す点のデータに基づき直線近似デ
ータを生成する。
データ構造に変換して、そのデータ構造を用いて折線化
処理を行う。すなわち、画像を画素連結データと、画素
連結データの集まりである画素ブロックデータにより表
現されるようにし、これらのデータをもとに折線画像を
求める。 画素連結データ生成手段（３）で、画素連結データを生
成する。画素連結データは、２値ディジタル画像を主走
査方向に走査して、背景画素（白画素）から画像の画素
（黒画素）に変化した画素を開始点の画素とし、画像の
画素から背景画素に変化した画素を終了点の画素とする
ものでありいわゆる画像のラン情報である。 画素ブロックデータ生成手段は画素ブロックデータを生
成する。画素ブロックデータとは、所定の関係を有する
画素連結データの集まりをいう。その所定の関係として
は、画素連結データ同士が上下方向（副走査方向）にた
だ一つの画素連結データとのみ隣接しており、画素連結
データの長さがあまり変らず、一定の方向に沿って配置
された位置関係を有するものである。 直線線分判定手段は、各画素ブロックデータを調べ、画
素ブロックが直線線分を表すものかどうかを判定する。
調べるデータとしては、そのブロックに属する画素連結
データの長さの分布、ブロックの外接矩形の大きさなど
の直線の表現に関連する情報がある。また、ブロックの
外接矩形の縦横比を求め、その縦横比がある値以上であ
るか否かを判定する。 直線近似処理手段は、画素ブロックが直線線分であると
判定された場合において、直線線分判定手段により前記
縦横比がしきい値より大きいと判定されたとき、その画
素ブロックデータの上部の画素連結データと下部の画素
連結データに基づき直線近似データを生成し直線線分判
定手段により前記縦横比がしきい値末端であると判定さ
れたとき、画素ブロックデータにおけるブロック内で左
端を表す点と右端を表す点のデータに基づき直線近似デ
ータを生成する。
【実施例】 第１図は本発明の一実施例の構成を示すものである。本
実施例の線図形折れ線化処理装置は、イメージスキャナ
のような画像を２値化して入力する画像入力部１と、画
像入力部１から入力した画像データを記憶する画像デー
タ記憶部２と、その画像データ記憶部２に記憶された２
値ディジタル画像を主走査方向に走査して、背景画素
（白画素）から画像の画素（黒画素）に変化した画素を
開始点の画素とし、黒画素から白画素に変化した画素を
終了点の画素とする画素連結データを生成する画素連結
データ生成部３と、その画素連結データ生成部３によっ
て生成されたデータを記憶する画素連結データ記憶部４
と、上下方向（副走査方向）に隣接する画素連結データ
を調べ、予め定めた関係を有する画素連結データの集ま
りを画素ブロックデータとする画素ブロックデータを生
成部５と、その画素ブロックデータ生成部５により生成
された画素ブロックデータを記憶する画素ブロックデー
タ記憶部６と、各画素ブロックデータに基づきその画素
ブロックが直線線分を表すものかどうかを判定する直線
線分判定部７と、その直線線分判定部７により画素ブロ
ックが直線線分があると判定されたとき、その画素ブロ
ックの一番上の画素連結データの開始点と終了点および
一番下の画素連結データの開始点と終了点のデータに基
づき直線近似データを生成する直線近似処理部８と、直
線近似処理部８により生成されたデータを折線データと
して記憶する折線データ記憶部９からなっている。 以下、第１図を参照しながら順をおって折線化処理の手
順を説明する。 画像入力部１で入力された、２値のディジタル画像デー
タは画像データ記憶部２に記憶される。画素連結データ
生成部３は、画像データ記憶部２の内容から、画像のラ
ン情報である画像連結データを生成し、画素ブロックデ
ータ生成部５により画像中の上下方向に連結している画
素連結データを表す画素ブロックデータを抽出する。 第２図を用いて画素連結データの抽出手順を説明する。
なお、第４図は画素連結データを説明した図である。 画像をラスタ方向（主走査方向）に走査し、画像の背景
画素値から線図形画素値に変化する画素Is（i,j）を見
つける（第２図ステップ201〜204）。すなわち、まず画
像の幅ｍ、画像の高さｎ、黒画素値pxを設定し（ステッ
プ201）、ラスタ走査の開始位置をｉ＝0,j＝０として設
定する（ステップ202）。走査位置の画素Is（i,j）が黒
画素値pxであるかを調べ（ステップ203）、黒画素であ
るときは画素Is（i,j）を開始点として登録する（ステ
ップ204）。 さらに、走査を続けて線図形画素値から背景画素値に変
化する画素Ie（i,j）≠pxを見つける（ステップ205〜20
7）。すなわち、走査が一つの走査ラインの終りに達し
たかどうかをｉ＜ｍにより判定し（ステップ205）、終
りに達していないときは線図形画素値から背景画素値に
変化したかどうかを判定し（ステップ206）、変化して
いなかったときは走査を１画素進め（ステップ207）、
同様の処理を繰り返す。ステップ206の判定で画素の変
化があったときすなわちIe（i,j）≠pxとなったときは
画素Ie（i,j）を画素連結データの終了点として登録す
る（ステップ208）。このとき、画像の右端まで線図形
画素値から背景画素値に変化する画素を見つけられない
ときは、その走査ライン上で画素の連結が終っていると
判断して、線図形画素値から背景画素値に変化する画素
をIe（m,j）と決定する。 なお、画素の登録は、画素Isをｔ番目の画素連結データ
の開始点Ｓ（ｔ）、画素Ieをｔ番目の画素連結データの
終了点Ｅ（ｔ）として、画素連結データ記憶部４に記憶
することにより行う。このとき、付加的な情報として画
素連結データの長さＬ（ｔ）を一緒に登録してもよい。
さらに、この処理を続け、走査ラインが画像の高さ
（ｎ）を越えるまで続ける（ステップ211〜213）。 次に上記で抽出した画素連結データと画像から、画素ブ
ロックデータの抽出を行う。第３図に画素ブロックデー
タ抽出処理に関する流れ図を示す。 まず、画素連結データの総数をｍに設定し（ステップ30
1）、画素連結データの番号ｎおよび画素ブロックデー
タの番号ｉを０に設定する（ステップ302）。 画素連結データ記憶部４から、ｎ番目の画素連結データ
data（ｎ）を取り出し、このデータが既にブロックの一
部として登録されているか否かを調べる（ステップ30
3）。既に登録されているときは次の画素連結データを
取り出すためにｎ＝ｎ＋１とする（ステップ304）。ｎ
＜ｍであるかどうかの判定によりすべての画素連結デー
タについて画素ブロック生成処理が終了したかどうかを
判定する（ステップ305）。 未だ、ステップ303の判定において、登録されていなか
ったときは、新しい画素ブロックデータの生成処理を行
う（ステップ306〜314）。 新しい画素ブロックデータの生成処理について詳細に説
明する。 画素連結データdata（ｎ）が、画素ブロックに登録され
ていなかったとき、画素ブロックデータblock（ｉ）に
登録する（ステップ306）。次に、変数ｎの値を後の利
用のために一時的に退避する（ステップ307）。 そして、この画素連結データdata（ｎ）が次の３つの条
件を満たしているか調べる（ステップ308）。 下方向に連結している連結画素データが１つだけ存
在する。 下方向に連結している連結画素データの長さが急に
変化しない。例えば、自分自身の長さの２倍以上、ある
いは1/2以下にならない。 下方向に連結している画素連結データをブロックに
登録しても、ブロックの伸びる方向は変化しない。 条件のブロックの伸びる方向とは、第６図に示したよ
うに、あるブロック内の上からｉ番目の画素連結データ
datau（ｉ）とｉ＋１番目の画素連結データdatau（ｉ＋
１）との位置の変化の方向（増加／減少）である。つま
り、あるブロック内での画素連結データdatau（ｉ）の
中点のＸ座標と画素連結データdatau（ｉ＋１）の中点
のＸ座標の差［ai＝datau（ｉ＋１）−datau（ｉ）］の
符号と、このブロックに新たに画素連結データdata
u（ｉ＋２）を加えたときの画素連結データdatau（ｉ＋
１）の中点のＸ座標と画素連結データdatau（ｉ＋２）
の中点のＸ座標の差［ai+1＝datau（ｉ＋２）−data
u（ｉ＋１）］の符号が一致していることを表してい
る。 条件を画素連結データdata（ｎ）が満たしていな
い場合、画素ブロックデータblock（ｎ）は終了してい
るとする。 画素連結データdata（ｎ）が以上の条件を満たし
ているときは、このdata（ｎ）に連結する画素連結デー
タdata（ｊ）を画素連結データ記憶部４の中から探す
（ステップ309）。 次に画素連結データdata（ｊ）に対して、次の条件を
満たしているかを調べる（ステップ310）。 上に続く連結画素データはdata（ｎ）のみである。 画素連結データdata（ｊ）が条件を満たしていると
き、この画素連結データdata（ｊ）を画素ブロックデー
タblock（ｉ）に追加登録する（ステップ311）。そし
て、新しく追加登録した画素連結データdata（ｊ）に連
結する画素連結データを探すために変数ｎにｊを設定し
（ステップ312）、ステップ308に戻る。 以上のような処理を画素ブロックデータblock（ｉ）が
終了するまで続ける。この終了は、ステップ308または
ステップ310で、条件〜またはを満たさなかった
ことをもって判定し、ステップ304へ戻る。その際に、
ステップ307で退避した値を変数ｎに設定するとともに
（ステップ313）、変数ｉの値をインクリメントしてお
く（ステップ314）。 そして、画素連結データ記憶部４から画素ブロックデー
タに登録していない画素連結データを探し、以上の処理
を続け、全ての画素連結データが画素ブロックデータに
登録されるまで続ける。 本実施例では画素ブロックデータは、その内にある全て
の画素連結データを実際に持っているように説明した
が、実際の画素ブロックデータは、そのブロックが画像
内で占める領域の外接矩形で代表して表し、ブロック内
に含まれる画素連結データは、画素連結データ記憶部44
における位置のみを記録している。 画像を画素ブロックデータで表した結果の一例を第５図
に示す。 次に、直線線分判定部５において各ブロックが画像中の
直線線分を表現しているかどうか判定する。折線化処理
は、線図形の直線で表されている部分に対して行われる
べきものなので、塗りつぶしある矢印や丸印等を判定
し、折線化の処理を行わないようにするものである。 直線線分判定部５では、各ブロック内にある全ての画素
連結データの長さを調べ、同一の長さを持つ画素連結デ
ータがそのブロック内に多く存在しているときに、その
ブロックを直線線分として判断する。 さらに、ブロックの外接矩形の大きさを調べ、幅÷高さ
の値があるしきい値以上であるか未満であるかを判定す
る。即ち、外接矩形の縦横比を求め、しきい値と比較
し、しきい値未満であるか否かを判定する。この情報も
併せて出力する。 直線近似処理部６では、直線線分判定部５によって直線
線分であると判定された、画素ブロックデータを画素ブ
ロックデータ記憶部６から取り出し、そのブロックが直
線線分判定部７によって外接矩形の縦横比がしきい値以
上と判定されていれば、直線近似処理部８は、その画素
ブロックデータの一番上の画素連結データの中点と、一
番下の画素連結データの中点を直線近似データとして取
り出す。直線線分判定部７によってブロックが外接矩形
の縦横比がしきい値未満と判定されたときは、直線近似
処理部８は、そのブロック内で左端を表す点と右端を表
す点を直線近似データとして取り出す。各ブロックから
取り出された直線近似データは、入力した２値ディジタ
ル画像を表現する折線化データとして、折線データ記憶
部９に記憶される。 以上の一連の処理により、画像に対して折線化処理を行
うことができる。 本実施例では、画素ブロックデータの伸びる方向を各画
素連結データの中点のＸ座標の変化の方向と定義してい
るが、次のような手法によっても、同様の画素ブロック
データを得ることができる。まず、条件を考慮せず
に、画素ブロックデータを生成してから、各ブロックを
さらに小さいいくつかのサブブロックに分割する。この
各サブブロックで、サブブロック内で一番上の画素連結
データの中点と一番下の画素連結データの中点をむすぶ
線分を生成し、この線分の方向を調べ、ブロック内でこ
の線分の方向が予め設定しておいたしきい値以上変化し
ている点で、そのブロックを分割する。
実施例の線図形折れ線化処理装置は、イメージスキャナ
のような画像を２値化して入力する画像入力部１と、画
像入力部１から入力した画像データを記憶する画像デー
タ記憶部２と、その画像データ記憶部２に記憶された２
値ディジタル画像を主走査方向に走査して、背景画素
（白画素）から画像の画素（黒画素）に変化した画素を
開始点の画素とし、黒画素から白画素に変化した画素を
終了点の画素とする画素連結データを生成する画素連結
データ生成部３と、その画素連結データ生成部３によっ
て生成されたデータを記憶する画素連結データ記憶部４
と、上下方向（副走査方向）に隣接する画素連結データ
を調べ、予め定めた関係を有する画素連結データの集ま
りを画素ブロックデータとする画素ブロックデータを生
成部５と、その画素ブロックデータ生成部５により生成
された画素ブロックデータを記憶する画素ブロックデー
タ記憶部６と、各画素ブロックデータに基づきその画素
ブロックが直線線分を表すものかどうかを判定する直線
線分判定部７と、その直線線分判定部７により画素ブロ
ックが直線線分があると判定されたとき、その画素ブロ
ックの一番上の画素連結データの開始点と終了点および
一番下の画素連結データの開始点と終了点のデータに基
づき直線近似データを生成する直線近似処理部８と、直
線近似処理部８により生成されたデータを折線データと
して記憶する折線データ記憶部９からなっている。 以下、第１図を参照しながら順をおって折線化処理の手
順を説明する。 画像入力部１で入力された、２値のディジタル画像デー
タは画像データ記憶部２に記憶される。画素連結データ
生成部３は、画像データ記憶部２の内容から、画像のラ
ン情報である画像連結データを生成し、画素ブロックデ
ータ生成部５により画像中の上下方向に連結している画
素連結データを表す画素ブロックデータを抽出する。 第２図を用いて画素連結データの抽出手順を説明する。
なお、第４図は画素連結データを説明した図である。 画像をラスタ方向（主走査方向）に走査し、画像の背景
画素値から線図形画素値に変化する画素Is（i,j）を見
つける（第２図ステップ201〜204）。すなわち、まず画
像の幅ｍ、画像の高さｎ、黒画素値pxを設定し（ステッ
プ201）、ラスタ走査の開始位置をｉ＝0,j＝０として設
定する（ステップ202）。走査位置の画素Is（i,j）が黒
画素値pxであるかを調べ（ステップ203）、黒画素であ
るときは画素Is（i,j）を開始点として登録する（ステ
ップ204）。 さらに、走査を続けて線図形画素値から背景画素値に変
化する画素Ie（i,j）≠pxを見つける（ステップ205〜20
7）。すなわち、走査が一つの走査ラインの終りに達し
たかどうかをｉ＜ｍにより判定し（ステップ205）、終
りに達していないときは線図形画素値から背景画素値に
変化したかどうかを判定し（ステップ206）、変化して
いなかったときは走査を１画素進め（ステップ207）、
同様の処理を繰り返す。ステップ206の判定で画素の変
化があったときすなわちIe（i,j）≠pxとなったときは
画素Ie（i,j）を画素連結データの終了点として登録す
る（ステップ208）。このとき、画像の右端まで線図形
画素値から背景画素値に変化する画素を見つけられない
ときは、その走査ライン上で画素の連結が終っていると
判断して、線図形画素値から背景画素値に変化する画素
をIe（m,j）と決定する。 なお、画素の登録は、画素Isをｔ番目の画素連結データ
の開始点Ｓ（ｔ）、画素Ieをｔ番目の画素連結データの
終了点Ｅ（ｔ）として、画素連結データ記憶部４に記憶
することにより行う。このとき、付加的な情報として画
素連結データの長さＬ（ｔ）を一緒に登録してもよい。
さらに、この処理を続け、走査ラインが画像の高さ
（ｎ）を越えるまで続ける（ステップ211〜213）。 次に上記で抽出した画素連結データと画像から、画素ブ
ロックデータの抽出を行う。第３図に画素ブロックデー
タ抽出処理に関する流れ図を示す。 まず、画素連結データの総数をｍに設定し（ステップ30
1）、画素連結データの番号ｎおよび画素ブロックデー
タの番号ｉを０に設定する（ステップ302）。 画素連結データ記憶部４から、ｎ番目の画素連結データ
data（ｎ）を取り出し、このデータが既にブロックの一
部として登録されているか否かを調べる（ステップ30
3）。既に登録されているときは次の画素連結データを
取り出すためにｎ＝ｎ＋１とする（ステップ304）。ｎ
＜ｍであるかどうかの判定によりすべての画素連結デー
タについて画素ブロック生成処理が終了したかどうかを
判定する（ステップ305）。 未だ、ステップ303の判定において、登録されていなか
ったときは、新しい画素ブロックデータの生成処理を行
う（ステップ306〜314）。 新しい画素ブロックデータの生成処理について詳細に説
明する。 画素連結データdata（ｎ）が、画素ブロックに登録され
ていなかったとき、画素ブロックデータblock（ｉ）に
登録する（ステップ306）。次に、変数ｎの値を後の利
用のために一時的に退避する（ステップ307）。 そして、この画素連結データdata（ｎ）が次の３つの条
件を満たしているか調べる（ステップ308）。 下方向に連結している連結画素データが１つだけ存
在する。 下方向に連結している連結画素データの長さが急に
変化しない。例えば、自分自身の長さの２倍以上、ある
いは1/2以下にならない。 下方向に連結している画素連結データをブロックに
登録しても、ブロックの伸びる方向は変化しない。 条件のブロックの伸びる方向とは、第６図に示したよ
うに、あるブロック内の上からｉ番目の画素連結データ
datau（ｉ）とｉ＋１番目の画素連結データdatau（ｉ＋
１）との位置の変化の方向（増加／減少）である。つま
り、あるブロック内での画素連結データdatau（ｉ）の
中点のＸ座標と画素連結データdatau（ｉ＋１）の中点
のＸ座標の差［ai＝datau（ｉ＋１）−datau（ｉ）］の
符号と、このブロックに新たに画素連結データdata
u（ｉ＋２）を加えたときの画素連結データdatau（ｉ＋
１）の中点のＸ座標と画素連結データdatau（ｉ＋２）
の中点のＸ座標の差［ai+1＝datau（ｉ＋２）−data
u（ｉ＋１）］の符号が一致していることを表してい
る。 条件を画素連結データdata（ｎ）が満たしていな
い場合、画素ブロックデータblock（ｎ）は終了してい
るとする。 画素連結データdata（ｎ）が以上の条件を満たし
ているときは、このdata（ｎ）に連結する画素連結デー
タdata（ｊ）を画素連結データ記憶部４の中から探す
（ステップ309）。 次に画素連結データdata（ｊ）に対して、次の条件を
満たしているかを調べる（ステップ310）。 上に続く連結画素データはdata（ｎ）のみである。 画素連結データdata（ｊ）が条件を満たしていると
き、この画素連結データdata（ｊ）を画素ブロックデー
タblock（ｉ）に追加登録する（ステップ311）。そし
て、新しく追加登録した画素連結データdata（ｊ）に連
結する画素連結データを探すために変数ｎにｊを設定し
（ステップ312）、ステップ308に戻る。 以上のような処理を画素ブロックデータblock（ｉ）が
終了するまで続ける。この終了は、ステップ308または
ステップ310で、条件〜またはを満たさなかった
ことをもって判定し、ステップ304へ戻る。その際に、
ステップ307で退避した値を変数ｎに設定するとともに
（ステップ313）、変数ｉの値をインクリメントしてお
く（ステップ314）。 そして、画素連結データ記憶部４から画素ブロックデー
タに登録していない画素連結データを探し、以上の処理
を続け、全ての画素連結データが画素ブロックデータに
登録されるまで続ける。 本実施例では画素ブロックデータは、その内にある全て
の画素連結データを実際に持っているように説明した
が、実際の画素ブロックデータは、そのブロックが画像
内で占める領域の外接矩形で代表して表し、ブロック内
に含まれる画素連結データは、画素連結データ記憶部44
における位置のみを記録している。 画像を画素ブロックデータで表した結果の一例を第５図
に示す。 次に、直線線分判定部５において各ブロックが画像中の
直線線分を表現しているかどうか判定する。折線化処理
は、線図形の直線で表されている部分に対して行われる
べきものなので、塗りつぶしある矢印や丸印等を判定
し、折線化の処理を行わないようにするものである。 直線線分判定部５では、各ブロック内にある全ての画素
連結データの長さを調べ、同一の長さを持つ画素連結デ
ータがそのブロック内に多く存在しているときに、その
ブロックを直線線分として判断する。 さらに、ブロックの外接矩形の大きさを調べ、幅÷高さ
の値があるしきい値以上であるか未満であるかを判定す
る。即ち、外接矩形の縦横比を求め、しきい値と比較
し、しきい値未満であるか否かを判定する。この情報も
併せて出力する。 直線近似処理部６では、直線線分判定部５によって直線
線分であると判定された、画素ブロックデータを画素ブ
ロックデータ記憶部６から取り出し、そのブロックが直
線線分判定部７によって外接矩形の縦横比がしきい値以
上と判定されていれば、直線近似処理部８は、その画素
ブロックデータの一番上の画素連結データの中点と、一
番下の画素連結データの中点を直線近似データとして取
り出す。直線線分判定部７によってブロックが外接矩形
の縦横比がしきい値未満と判定されたときは、直線近似
処理部８は、そのブロック内で左端を表す点と右端を表
す点を直線近似データとして取り出す。各ブロックから
取り出された直線近似データは、入力した２値ディジタ
ル画像を表現する折線化データとして、折線データ記憶
部９に記憶される。 以上の一連の処理により、画像に対して折線化処理を行
うことができる。 本実施例では、画素ブロックデータの伸びる方向を各画
素連結データの中点のＸ座標の変化の方向と定義してい
るが、次のような手法によっても、同様の画素ブロック
データを得ることができる。まず、条件を考慮せず
に、画素ブロックデータを生成してから、各ブロックを
さらに小さいいくつかのサブブロックに分割する。この
各サブブロックで、サブブロック内で一番上の画素連結
データの中点と一番下の画素連結データの中点をむすぶ
線分を生成し、この線分の方向を調べ、ブロック内でこ
の線分の方向が予め設定しておいたしきい値以上変化し
ている点で、そのブロックを分割する。
本発明によれば、画像を階層的なデータ構造に変換し
て、そのデータ構造を用いて折線化処理を行うようにし
たので、折線化処理を行う際に、処理時間のかかる画像
処理を行う必要がなく、短い処理時間で折線データを得
ることができる。 また、本発明によれば、画像のラン情報を表す画素連結
データから、画素連結データが上下に連結する画素ブロ
ックデータを得るようにしたので、各ブロックデータが
線分を表現し、正確な折線データを得ることができる。 さらに、画素ブロックデータは画素連結データを含むた
め、画素連結データの長さを測るなどして各ブロック内
の形状を知ることができ、線図形部分についてのみ折線
データを生成することができる。
て、そのデータ構造を用いて折線化処理を行うようにし
たので、折線化処理を行う際に、処理時間のかかる画像
処理を行う必要がなく、短い処理時間で折線データを得
ることができる。 また、本発明によれば、画像のラン情報を表す画素連結
データから、画素連結データが上下に連結する画素ブロ
ックデータを得るようにしたので、各ブロックデータが
線分を表現し、正確な折線データを得ることができる。 さらに、画素ブロックデータは画素連結データを含むた
め、画素連結データの長さを測るなどして各ブロック内
の形状を知ることができ、線図形部分についてのみ折線
データを生成することができる。
第１図は、本発明の一実施例の構成図である。 第２図は、実施例の画素連結データ生成部の処理の流れ
を示す図である。 第３図は、実施例の画素ブロックデータ生成部の処理の
流れを示す図である。 第４図は、画素連結データを説明するための図である。 第５図は、画素ブロックデータを説明するための図であ
る。 第６図は、画素ブロックデータの伸びる方向について説
明した図である。 １……画像入力部、２……画像データ記憶部、３……画
素連結データ生成部、４……画素連結データ記憶部、５
……画素ブロックデータ生成部、６……画素ブロックデ
ータ記憶部、７……直線線分判定部、８……直線近似処
理部、９……折線データ記憶部。
を示す図である。 第３図は、実施例の画素ブロックデータ生成部の処理の
流れを示す図である。 第４図は、画素連結データを説明するための図である。 第５図は、画素ブロックデータを説明するための図であ
る。 第６図は、画素ブロックデータの伸びる方向について説
明した図である。 １……画像入力部、２……画像データ記憶部、３……画
素連結データ生成部、４……画素連結データ記憶部、５
……画素ブロックデータ生成部、６……画素ブロックデ
ータ記憶部、７……直線線分判定部、８……直線近似処
理部、９……折線データ記憶部。
Claims (1)
- 【請求項１】２値ディジタル画像を主走査方向に走査し
て、背景画素から画像の画素に変化した画素を開始点の
画素とし、画像の画素から背景画素に変化した画素を終
了点の画素とする画素連結データを生成する画素連結デ
ータ生成手段と、 画素連結データの相互の関係を調べ、画素連結データ同
士が上下方向（副走査方向）にただ一つの画素連結デー
タとのみ隣接しており、画素連結データの長さの変化が
あるしきい値以内で、かつ一定の方向に沿って配置され
た位置関係を有するものを連結して画素ブロックデータ
を生成する画素ブロックデータ生成手段と、 画素ブロックデータを構成する画素連結データの長さを
調べ、同一の長さの画素連結データを一定以上の割合で
含む画素ブロックデータを直線線分を表すものと判定
し、さらにその画素ブロックデータの外接矩形の縦横比
があるしきい値より大きいか否かを判定する直線線分判
定手段と、 直線線分判定手段により画素ブロックデータが直線線分
であると判定された場合において、直線線分判定手段に
より前記縦横比がしきい値より大きいと判定されたと
き、その画素ブロックデータの上部の画素連結データと
下部の画素連結データに基づき直線近似データを生成
し、直線線分判定手段により前記縦横比がしきい値未満
であると判定されたとき、画素ブロックデータにおける
ブロック内で左端を表す点と右端を表す点のデータに基
づき直線近似データを生成する直線近似処理手段と を備えたことを特徴とする線図形折線化処理装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2208118A JPH0743764B2 (ja) | 1990-08-08 | 1990-08-08 | 線図形折線化処理装置 |
| US08/047,075 US5313529A (en) | 1990-08-08 | 1993-04-16 | System for representing line drawings by polygonal lines |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2208118A JPH0743764B2 (ja) | 1990-08-08 | 1990-08-08 | 線図形折線化処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0495178A JPH0495178A (ja) | 1992-03-27 |
| JPH0743764B2 true JPH0743764B2 (ja) | 1995-05-15 |
Family
ID=16550935
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2208118A Expired - Fee Related JPH0743764B2 (ja) | 1990-08-08 | 1990-08-08 | 線図形折線化処理装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5313529A (ja) |
| JP (1) | JPH0743764B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3327622B2 (ja) * | 1992-04-29 | 2002-09-24 | キヤノン株式会社 | ベジェスプラインから２次多項式フラグメントへの変換 |
| US5519822A (en) * | 1994-12-09 | 1996-05-21 | Hewlett-Packard Company | Method and apparatus for simultaneously selecting a plurality of pixels to lie upon a line segment defined by two end points |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB1587613A (en) * | 1976-11-04 | 1981-04-08 | Norprint Ltd | Character identification |
| GB1517870A (en) * | 1976-12-20 | 1978-07-12 | Ibm | Apparatus for producing vectors from raster scanned data |
| JPS6282486A (ja) * | 1985-10-08 | 1987-04-15 | Hitachi Ltd | オンライン手書き図形認識装置 |
| JPH0664607B2 (ja) * | 1986-02-18 | 1994-08-22 | 日本電気株式会社 | 直線抽出装置 |
| JPS6345687A (ja) * | 1986-08-13 | 1988-02-26 | Yokogawa Electric Corp | デイジタル画像の線分抽出方法 |
| US5064439A (en) * | 1987-01-20 | 1991-11-12 | Richards Medical Company | Orthopedic device of biocompatible polymer with oriented fiber reinforcement |
| JPH07104930B2 (ja) * | 1987-11-20 | 1995-11-13 | 日立ソフトウェアエンジニアリング株式会社 | 折線化処理方法 |
| US4975853A (en) * | 1987-11-20 | 1990-12-04 | Hitachi Software Engineering Co., Ltd. | Image processing system having polygonal line processing of pixel line data |
| JPH07104931B2 (ja) * | 1987-11-30 | 1995-11-13 | 富士通株式会社 | 線図形折線化方法 |
| JPH01231183A (ja) * | 1988-03-10 | 1989-09-14 | Mitsubishi Electric Corp | 画像処理装置における直線性判定装置 |
-
1990
- 1990-08-08 JP JP2208118A patent/JPH0743764B2/ja not_active Expired - Fee Related
-
1993
- 1993-04-16 US US08/047,075 patent/US5313529A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0495178A (ja) | 1992-03-27 |
| US5313529A (en) | 1994-05-17 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3950777B2 (ja) | 画像処理方法、画像処理装置および画像処理プログラム | |
| JP3308032B2 (ja) | スキュー補正方法およびスキュー角検出方法およびスキュー補正装置およびスキュー角検出装置 | |
| JPH03122773A (ja) | 画像形成装置 | |
| JP2002024836A (ja) | ディジタルイメージから表題を抽出する方法 | |
| US7889938B2 (en) | Method and apparatus for processing line drawings in images | |
| JP3571128B2 (ja) | 図面の寸法数値認識方法及びその装置 | |
| JP3718967B2 (ja) | 画像特徴量抽出装置および方法並びに画像特徴量抽出プログラムを記録した記録媒体 | |
| JPH0256707B2 (ja) | ||
| US5228097A (en) | Method for registering image data | |
| US6356657B1 (en) | Image processing method and apparatus for discriminating an input image area or an attribute of image information in the discriminated area | |
| JPH0743764B2 (ja) | 線図形折線化処理装置 | |
| JP2006011967A (ja) | 文字認識装置、文字認識プログラム | |
| JP2007295210A (ja) | 画像処理装置、画像処理方法、画像処理プログラム、およびこれを記録した記録媒体 | |
| JPH03126181A (ja) | 文書画像の領域分割方法 | |
| JP2002133424A (ja) | 文書の傾き角度及び境界の検出方法 | |
| JP3187895B2 (ja) | 文字領域抽出方法 | |
| JP3582734B2 (ja) | 表のベクトル化装置 | |
| JP2558668B2 (ja) | 文字パタ−ン抽出方法 | |
| JP2616967B2 (ja) | 傾き抽出装置 | |
| JP2789622B2 (ja) | 文字／図形領域判定装置 | |
| JP3083609B2 (ja) | 情報処理装置及びそれを用いた文字認識装置 | |
| JPH0495180A (ja) | 線分・曲線認識方式 | |
| JP3045810B2 (ja) | 二値画像処理方法および装置 | |
| JP3104355B2 (ja) | 特徴抽出装置 | |
| JP2800205B2 (ja) | 画像処理装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |