(57)【特許請求の範囲】
【請求項１】
画像データ内の黒画素を順次注目画素として読み出し、前記注目画素を含む局所領域の黒画素パターンを切り出す手順ａ、
予めマスクテーブルに局所領域の大きさに応じて求まる局所領域内の注目画素と他の画素の関係を求めた値を記憶しておき、該マスクテーブルから前記局所領域に対応したマスクパターン値を有するマスクを読み出し、前記局所領域の各黒画素と前記注目画素を通る直線との距離の平均二乗値に基づき直線度を求める演算を前記マスクを用いて行う手順ｂ、
前記演算した値に基づき直線度を算出し、前記注目画素をパラメータ空間にハフ変換した座標データに、前記注目画素の前記直線度を重みとして統合する手順ｃ、
前記パラメータ空間における前記直線度が極大となる前記ハフ変換した座標データを求めて直線を検出する手順ｄ、
からなることを特徴とする直線検出方法。
【請求項２】
画像データ内の局所領域の各黒画素と注目画素を通る直線との距離の平均二乗値を演算し、前記演算結果に基づき直線度を求める演算を行う直線度算出部と、
前記注目画素をパラメータ空間にハフ変換した座標データに、前記注目画素の前記直線度を重みとして統合する統合部と、
前記パラメータ空間における前記直線度が極大となる前記ハフ変換した座標データを求めて直線を検出する直線検出部と、を設けたことを特徴とする直線検出装置。
【請求項３】
画像データを記憶する画像メモリと、
前記画像メモリから画像データ内の黒画素を順次注目画素として読み出し、前記注目画素を含む局所領域の黒画素パターンを切り出す局所領域部と、
予め局所領域の大きさに応じて求まる局所領域内の注目画素と他の画素の関係を求めた値を記憶しておくマスクテーブルと、
該マスクテーブルから前記局所領域に対応したマスクパターン値を有するマスクを読み出し、前記局所領域の各黒画素と前記注目画素を通る直線との距離の平均二乗値を前記マスクを用いて演算する畳み込み部と、
前記畳み込み部の演算結果に基づき直線度を求める演算を行う直線度算出部と、
前記注目画素をパラメータ空間にハフ変換した座標データに、前記注目画素の前記直線度を重みとして統合する統合部と、
前記パラメータ空間における前記直線度が極大となる前記ハフ変換した座標データを求めて直線を検出する直線検出部とを設けたことを特徴とする直線検出装置。
【請求項４】
前記畳み込み部の演算結果に基づき直線度を求める演算を
下記式により行うことを特徴とする請求項３記載の直線検出装置。
0003653542.tif 000014
但し、
0003653542.tif 000015
Ｎは画素数、
ｉは注目画素、ｅは任意黒画素。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は、画像読み取り装置等により読み取られた画像データから、直線を認識するための直線検出法の改善に関する。
【０００２】
【従来の技術】
画像データから直線を検出する種々の方式があるが、その中の１つの手法としていわゆるハフ変換法と呼ばれる方法がある。このハフ変換は、画像空間（ＸＹ座標空間）上の点をパラメータ空間に写像することであるが、直線検出に際しては画像空間上のすべての点を直線を表すパラメータ空間に写像する。
【０００３】
図６に示すようなＸＹ座標空間に点（ｘｉ，ｙｉ）を通る直線Ａが存在するならば、直線Ａを、
【数１】
0003653542.tif 000002
と表す。
このとき、ρは原点から直線Ａへ下ろした垂線の長さ、θはＸ軸と垂線のなす角である。
これは、図７に示すパラメータ空間（ρ−θ空間）でサイン曲線として表される。例えば図７における点（ｘｉ，ｙｉ）に関するサイン曲線は、図６に示す画像空間の点（ｘｉ，ｙｉ）を通る全ての直線を表している。
【０００４】
一般に、画像データ例えば画像読み取り装置等により読み取ったものは、画像読み取り装置のＸ軸方向及びＹ軸方向の分解能に応じた画素のマトリクス状の配列として捉えることができる。したがって、これらのマトリクス状画素配列上の画素に対しては、ＸＹ座標を適用することができる。
このようなマトリクス状画素配列における画素をすべて、上記（１）式を用いて、図７に示す直線を表すパラメータ空間に写像（投票）する。写像されるいずれの画素もその画素を通る全ての直線を表すサイン曲線に変換されてパラメータ空間に投票される。これらのサイン曲線が交わる点すなわち投票数の多い点のρ及びθ値が画像空間上に存在する直線として表される。図７の場合には、Ｂ点で交わりその交点の値ρｂ、θｂが実際に存在する直線のパラメータとなる。
【０００５】
【発明が解決しようとする課題】
しかしながら、このような従来のハフ変換を用いた直線検出法においては、直線以外のものが存在していた場合、必ずしも正しい直線を検出することができない場合があった。
この発明は、この点に関する改善のために成されたもので、比較的簡単で精度良く直線を検出する直線検出方法及び直線検出装置を提供するものである。
【０００６】
【課題を解決するための手段】
このため、この発明においては、
画像データ中のどこにどの様な直線があるかを検出する直線検出方法において、
注目画素とその画素を中心とする近傍の局所領域を定義する段階と、
該定義された局所領域内に存在する画素の関係から上記注目画素に対する直線らしさ（直線度）を算出する局所領域情報算出段階と、
を有し、
画像データ中の直線を調べる際、上記で求めた直線度を利用するようにした。
【０００７】
【作用】
この発明の直線検出方法では、画像データ中の複数の画素の位置関係を見る際に、画像データ中の全部の画素同士の位置関係（大域的情報）とともに、対象の画素（注目画素）に関する周囲の画素配列を含んだ局所領域に関する情報（局所的情報）をも考慮するようにしている。
局所的情報に関しては、その局所領域内の注目画素とその周囲の画素配列内の画素とからその注目画素の直線らしさ（直線度）を決定する。例えば、注目画素を中心とする５×５のマトリクス状画素配列を有する局所領域を考える。この局所領域内に注目画素以外に複数の画素が存在している場合、注目画素を含む複数の画素が一直線上に配列されていればいるほど当該局所領域内における注目画素の直線度は高くなる。
このような直線度というパラメータは、画像データ中のどこにどの様な直線が存在するか調べる際において、例えば直線の存在確率を示す重みデータとして利用することができる。
【０００８】
【実施例】
以下、本発明について図１〜図３に示す原理図を参照して詳細に説明する。
ここで、図１は画像読み取り装置等によって読み取った画像データを模式的に示す説明図であり、図２は直線度の求めかたの一例を示す模式図、図３は直線度の投票を説明するための模式図である。
【０００９】
この実施例では、画像データ中の画素を、先に示した式（１）に基づき、直線を表すパラメータ空間に写像させる際に、別に当該画素の直線の傾きによる直線度を求め、この直線度を直線の傾きの確からしさの指標としてパラメータ空間に重みとして投票するようにしたものである。従来のように、画像データ中の画素を普通にハフ変換するような場合には、パラメータ空間に投票される値は直線の傾きに対して均等なものとなる。従って、直線以外の画素の情報も同一に投票されてしまい各画素が写像されるパラメータ空間が不鮮明となってしまい、高精度な直線検出が行なえない。この実施例の方式は、直線の傾きの確からしさ（直線度）を新たに導入し、パラメータ空間を鮮鋭化することにより直線の検出を高精度に行なうようにしたものである。
【００１０】
さて、図１に示すような画像データの直線検出について考える。この実施例では、画像データ中の画素（注目画素）をパラメータ空間に写像する際、該注目画素の局所的情報としての直線度を合わせて投票する。図２は、図１の画像データ中の注目画素に関する局所領域の拡大模式図である。これらは、図２に符号ｅで示した黒画素（注目画素）をパラメータ空間に写像する際に、注目画素の直線度の求めかたを示す説明図である。
図２の局所領域は、５×５のマトリクス状画素配列を有しており、この内、符号ａ〜ｈで示す画素が黒画素となっている。
ここで、符号ｅで示した注目画素のＸＹ座標を（ｘｅ，ｙｅ）とすると、この注目画素を通る直線は（１）式の、ｘｉをｘｅ、ｙｉをｙｅとした式で表すことができる。この直線から他の黒画素（ａ〜ｄ及びｆ〜ｈ）に対する距離（垂線の距離）すなわち注目画素を通る直線に対する各画素の誤差をそれぞれ求める。
【００１１】
例えば、符号ｃで示した黒画素（ｘｃ，ｙｃ）との距離ｄｃは、
【数２】
0003653542.tif 000003
で表すことができる。ここで、両辺を２乗すると、
【数３】
0003653542.tif 000004
となる。従って、注目画素を通る直線に対する当該局所領域内の他の黒画素の距離の２乗の総和Ｄ2 （θ）は、次式により表すことができる。なお、この総和は注目画素以外の黒画素について上記のようにして求めた値を全て加算することであるので、以後においては符号ａ〜ｄ及びｆ〜ｈを代表するものとして符号ｉを用いることとする。従って、以下においてΣを用いて示すものは符号ｉを符号ａ〜ｄ及びｆ〜ｈを順次異ならせて加算していくことを示している。
【数４】
0003653542.tif 000005
となる。したがって、この平均２乗距離Ｅ2 （θ）は、
【数５】
0003653542.tif 000006
ここで正規化を行い求める直線度Ｌ（θ）を次式の通り定義した。
【数６】
0003653542.tif 000007
【００１２】
以上で求めた直線度は、図２を参照して言えば、符号ｅで示した注目画素を通る直線に対して他の複数の黒画素がどの程度その直線に対して沿って分布しているかという指標であると言うことができる。
そして、符号ｅに示した注目画素をパラメータ空間に投票する際に、図３に示すように、直線度という指標を投票する。画像データ中の各黒画素について直線度を求めてパラメータ空間に写像されるサイン曲線には、この直線度という指標が重みとして投票される。したがって、画像データ中の直線にのらない黒画素の直線度は低いものとなり、図３に示すような投票量の積み重ねに対する影響度が小さくなる。従来のように、各黒画素が均等な重みとして投票されるものに比べてパラメータ空間の鮮鋭度が著しく向上する。
さらに、この場合、図１の直線系列をはなれた黒画素のようにまばらな分布となっているものについては、その直線度は極めて低い値となるので、ノイズ等であると認識することもできる。
【００１３】
ところで、先に示した式（４）の
「Σ〔（ｘｉ−ｘｅ）の２乗〕」、
「Σ〔（ｙｉ−ｙｅ）の２乗〕」及び
「Σ（ｘｉ−ｘｅ）（ｙｉ−ｙｅ）」については、簡単なマスクと領域内の画像との畳み込み処理を用いることにより計算を簡素化することができる。すなわち、局所領域を５×５とした場合、Σ〔（ｘｉ−ｘｅ）の２乗〕は、
【数７】
0003653542.tif 000008
、Σ〔（ｙｉ−ｙｅ）の２乗〕は、
【数８】
0003653542.tif 000009
、Σ（ｘｉ−ｘｅ）（ｙｉ−ｙｅ）は、
【数９】
0003653542.tif 000010
のマスクパターンで求める事ができる。
【００１４】
式（７）〜（９）は局所領域を５×５とした場合であるが、一般的（（２ｍ＋１）×（２ｍ＋１）；ｍは正の整数）には次のそれぞれの式で表されるマスクパターンが用いられる。
【数１０】
0003653542.tif 000011
【数１１】
0003653542.tif 000012
【数１２】
0003653542.tif 000013
【００１５】
（６）式から分かるように、（σ2 ｘ＋σ2 ｙ）が０となった時不定となる。したがって、このような場合には、目的により直線度として０から１の値（この実施例では直線検出シュミレーションにより１／２を採用）をとるようにすればよい。
また、上記に示した注目画素に関する局所領域のマスクパターンは、局所領域の画像データ（画素パターン）がどのようなパターンをとりうるかあらかじめ決定することができるので、各パターンに関するマスクパターンについてあらかじめ計算しておくことができる。したがって、局所領域の画素パターンがどのようなパターンとなっているかを見ることにより、その都度マスクパターンの計算をする必要がなく、処理速度を向上させることができる。
【００１６】
図４は、この発明の１実施例を示す装置構成を示す構成説明図で、処理演算装置であるＣＰＵ１０と、スキャナ等から読み取られる画像データを保存する画像メモリ１１と画像メモリ１１から読みだされた注目画素を中心とする局所領域の切出しを行なう局所領域部１２と、局所領域部１２により切り出された局所領域の大きさに対応したマスクパターン値を格納しているマスクテーブル１３と、マスクと画像との畳み込みを行なう畳み込み部１４と、畳み込み部１４で計算された値に基づき直線度を算出する直線度算出部１５と、注目画素をハフ変換するとともに直線度算出部１５で算出した直線度を重みとして投票する統合部１６と、統合部１６によって統合されたパラメータ空間から直線を検出する直線検出部１７とを有している。なお、符号１８で示したものは各種計算を早めるための数値演算テーブルである。
ＣＰＵ１０は、画像メモリ１１から順次黒画素を読みだし注目画素とする。次いで、ＣＰＵ１０はこの注目画素の周囲を含む局所領域の黒画素パターンを局所領域部１２を利用して切り出し、どのようなパターンとなっているか決定する。そして、この決定した局所領域の黒画素パターンに対応する直線度をマスクテーブル１３、畳み込み部１４及び直線度算出部１５を利用して算出する。ＣＰＵ１０は、次いで統合部１５を動作させて、注目画素をパラメータ空間にハフ変換するとともに直線度を投票する。
【００１７】
以上の操作を、画像メモリ１１中の黒画素について順次行うことで、ハフ空間上に直線度が上乗せされたサイン曲線群が順次描かれる。投票された各々の直線度は順次加算積み重ねられることになるので、図３に示すように、投票された直線度が極大となるρｉ，θｉを求めて画像データ中の直線を検出する。
図５は、図４に示した装置の処理を示したフローチャートである。ステップ（１）〜（５）が画像データ中の黒画素についての直線度の決定とハフ変換を順次行なうものであり、ステップ（６）、（７）が直線を検出する処理である。
【００１８】
以上の説明では、画像データとして２値化画像を用いた例を示したが、この発明は、例えば２５６段階の濃度情報が付加されたグレイ画像データについても同様に実施することができる。
この場合には、例えば図４の２点鎖線で囲んだ手段、濃度情報部２０及び注目点検出部２１を設けることにより行なえる。濃度情報部２０は画像データ中の各画素の濃度を判定するもので、各画素（ｘｉ，ｙｉ）に関する濃度データｇを付与するものである。注目点検出部２１は、これらの各画素に関する濃度データの内あらかじめ決定されたしきい値を超える濃度を持つ画素を選択するものである。そして、ある濃度以上の画素について、上記の実施例で説明したと同様な処理を行なわせて直線度を算出する。
先の実施例である２値化画像データの場合には求めた直線度Ｌ（θ）をそのまま注目画素についての投票量とするものであったが、グレイ画像データの場合には求めた直線度Ｌ（θ）に濃度データｇを乗じたｇ・Ｌ（θ）を注目画素の投票量とする。
【００１９】
以上、直線検出手法としてハフ変換法を用いた例を示したが、このような方法ではなく、いわゆるラスター・ベクター変換（ＲＶＣ）法と言われる手法を用いることができる。これは、画像データ中の黒画素について順次その位置関係を調べていく方法であるが、このような場合にも本発明で示した直線度を算出決定することにより直線が存在する方向の重みデータとして使用することができ、黒画素の探索を効率化することができる。
【００２０】
【発明の効果】
以上説明したように、本発明では、直線検出に際して画像データ中の複数の画素の関係を調べる際、画素に関する直線度というパラメータを導入するようにしたので、直線以外の部分による直線検出のずれや量子化誤差等による画素のずれをも補正することができ正確な直線検出が可能になる。
また、直線度の検出に際し、注目画素の周囲を含む局所領域の画素パターンに基づきマスクパターン処理を行なうことで計算を簡単にすることができる。
【図面の簡単な説明】
【図１】図１は、本発明の対象である画像データの模式図である。
【図２】図２は、本発明の注目画素の直線度の決定原理を示す原理説明図である。
【図３】図３は、本発明の直線度データの意義を説明するための説明図である。
【図４】図４は、本発明の１実施例装置の構成説明図である。
【図５】図５は、図４の装置の処理の流れを示すフローチャートである。
【図６】図６は、ハフ変換による直線検出の原理説明図である。
【図７】図７は、同じくハフ変換による直線検出の原理説明図である。
【符号の説明】
１１−画像メモリ  １２−局所領域部  １３−マスクテーブル
１４−畳み込み部  １５−直線度算出部  １６−統合部  １７−直線検出部
【図１】
0003653542.tif 000016
【図２】
0003653542.tif 000017
【図３】
0003653542.tif 000018
【図４】
0003653542.tif 000019
【図５】
0003653542.tif 000020
【図６】
0003653542.tif 000021
【図７】
0003653542.tif 000022