トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 ハフ変換による線分抽出方法
【発明者】 【氏名】鎌田 洋

【目的】 この発明は画素の近傍情報をハフ変換の算出によって繰込むことにより、線分を正確に抽出し得るハフ変換による線分抽出方法を提供することを主要な特徴とする。
【構成】 画像上の点P(Xi ,Yi )を中心とする近傍のセルSP を定義し、点Pを通り360度をK分割する半直線K1〜K16を考え、セル内で予め直線の方向を検出する。各直線の方向をθK に対してρK =xcosθK +ysinθK を演算することにより、θK とρK を決定し、H(ρK ,θK )=h(ρK ,θK )+mK により、画素段階で最大値の数だけ加算を繰返す。
【特許請求の範囲】
【請求項1】 画像上の点P(Xi ,Yi )において、点Pを通り座標軸と角度θで交わり、原点から下した垂線との交点までの距離がρである直線(ρ,θ)を対応させ、すべての画像上の点において、対応の直線群を加算することにより(ρ,θ)に対し、重複度を算出し、重複度の多い順に対応の直線を抽出するハフ変換において、前記画像上の点Pを中心とする近傍のセルを定義し、その点Pを通りセル内のすべての画像点に最も一致する直線を複数本予め算出し、それぞれの直線に対応するρ,θを算出し、予め算出した直線をすべての画像点上で加算することを特徴とする、ハフ変換による線分抽出方法。
【請求項2】 前記画像を前記セルより十分大きな複数個の領域に分割し、それぞれの領域ごとに直線を抽出することを特徴とする、請求項1のハフ変換による線分抽出方法。
【請求項3】画像上の点P(Xi ,Yi )において、点Pを通り座標軸と角度θで交わり、原点から下した垂線との交点までの距離がρである直線(ρ,θ)を対応させ、すべての画像上の点において、対応の直線群を加算することにより(ρ,θ)に対し、重複度を算出し、重複度の多い順に対応の直線を抽出するハフ変換において、前記画像上の点Pを中心とする近傍のセルを定義し、その点Pを通る直線に対し、直線上または当該直線に最も近い画素がすべて画像点である直線を複数本予め算出し、それぞれの直線に対応するρ,θを算出し、予め算出した直線をすべての画像点上で加算することを特徴とする、ハフ変換による線分抽出方法。
【発明の詳細な説明】【0001】
【産業上の利用分野】この発明はハフ変換による線分抽出方法に関し、特に、画像処理において、ハフ変換を用いて画像の線分情報を抽出するようなハフ変換による線分抽出方法に関する。
【0002】
【従来の技術】二次元,三次元画像を認識し、理解するためには、その前処理および特徴抽出方法が最も重要な課題であり、多くの方法が提案され、使われてきた。その中でも、ハフ変換は画像の中から、有効に直線,曲線を抽出する方法であり、コンピュータビジョンなどの分野で広く使われている。
【0003】一方、文字認識の分野でも前処理と特徴抽出方法が最も重要な課題であり、種々の方法が試みられており、ハフ変換を用いる方法(F-H.CHENG et al.“Recognition of handwritten Chinese characters by modifiedHough transform techniques. ”IEEE Trans.Pattern Anal.Machine Intell vol11(´89 )429-439)も提案されているが、正確な線分情報の抽出が困難である。
【0004】従来のハフ変換は、次の第(1)の式で示されるラドン変換において、画像が二値の場合に対応している。すなわち、 X(ρ,θ)=∫f(t)δ(ρ−xcosθ−ysinθ)dt…(1)
ただし、ρは共通の座標原点に対する動径変数であり、θはその角度変数であり、δはデルタ関数であり、積分は全画像域Sについて行なう。第(1)式により、画像中の線分はρ,θ平面での関数H(ρ,θ)のピーク値として検出される。画像が二値のドットで表現されるときは、第(1)式は、次式の計算アルゴリズムで表される。
【0005】
For each(x,y) P doFor θ=0〜2π,Δθ doρ=xcosθ+ysinθH(ρ,θ)=H(ρ,θ)+mendendただし、Δθは分割角度であり、mは加算値(通常1)である。
【0006】図6は第(1)式を演算するためのフロー図である。図6において、xy平面上における黒画素を抽出し、分割角度θが0〜2πについてρ=xcosθ+ysinθの演算を行ない、H(ρ,θ)=H(ρ,θ)+1とする。そして、全画素について演算を終了したか否かを判別し、終了していなければ上述の演算を繰返し、mを+1する。
【0007】
【発明が解決しようとする課題】図7および図8は従来のハフ変換における問題点を説明するための図である。
【0008】図7に示すように、全体画像域を分割角度θ=0〜2πについてρを求め、ρ,θ平面上にプロットすると、ピーク値の重なりの多い部分のサイドローブの影響により、その周辺の弱いピーク値を検出できない場合がある。また、図8の点線で示す仮想的な直線上にある2本の分離した線分の分離ができない。さらに、文字のストロークに対応しない線分を抽出してしまうおそれがあるなどの欠点があった。
【0009】上述の問題点をさけるために、全画像領域を分割して、全画像をセグメント化し、セグメントごとにハフ変換を行なう方法がある。すなわち、次の第(2)式によってハフ変換を行なう。
【0010】Hn (ρ,θ)=∫snf(t)δ(ρ−xcosθ−ysinθ)dt…(2)
ただし、Hn (ρ,θ)はn番目のセグメントのハフ変換であり、Sn はセグメント内での積分範囲である。セグメント化法を用いればセグメントを小さくすればするほど、上述の問題点の解決に対して有効である。しかしながら、セグメントを小さくすることには限界があり、また小さくすればするほど、データ量が増大し、計算時間が増大するという問題点があった。
【0011】それゆえに、この発明の主たる目的は、画素の近傍情報をハフ変換の算出によって繰込むことにより、線分を正確に抽出し得るハフ変換による線分抽出方法を提供することである。
【0012】
【課題を解決するための手段】請求項1に係る発明は、画像上の点P(Xi,Yi )において、点Pを通り座標軸と角度θで交わり、原点から下した垂線との交点までの距離がρである直線(ρ,θ)を対応させ、すべての画像上の点において対応の直線群を加算することにより、直線(ρ,θ)に対し、重複度を算出し、重複度の多い順に対応の直線を抽出するハフ変換であって、画像上の点Pを中心とする近傍のセルを定義し、その点Pを通りセル内のすべての画像点に最も一致する直線を複数本予め算出し、それぞれの直線に対応するρ,θを算出し、予め算出した直線をすべての画像点上で加算するものである。
【0013】請求項2に係る発明は、請求項1に係る発明における画像をセルより十分大きな複数個の領域に分割し、それぞれの領域ごとに直線を抽出する。
【0014】請求項3に係る発明は、画像上の点Pを中心とする近傍セルを定義し、その点Pを通る直線に対し、直線上または当該直線に最も近い画素がすべて画像点である直線を複数本予め算出し、それぞれの直線に対応するρ,θを算出し、予め算出した直線をすべての画像点上で加算するように構成される。
【0015】
【作用】この発明に係るハフ変換による線分抽出方法は、画像上の点Pを中心とする近傍のセルを定義し、その点Pを通りセル内のすべての画像点に最も一致する直線を複数本予め算出するか、あるいは点Pを通る直線に対して直線上またはその直線に最も近い画素がすべて画像点である直線を複数本予め算出し、それぞれの直線に対応する距離ρと角度θを算出し、予め算出した直線をすべての画像点上で加算することにより線分を抽出する。
【0016】
【発明の実施例】図1はこの発明の一実施例の概略ブロック図である。図1を参照して、画像読取装置1は線分を抽出すべき画像を読取り、その画像の二値化出力をメモリ2に与える。メモリ2は二値化された画像データを記憶する。ハフ変換演算部3はメモリ2に記憶されている画像データをハフ変換し、メモリ4に記憶するとともに、表示部5に表示させる。
【0017】図2は画像近傍セルにおける検知すべき線分の方向を示す図であり、図3はこの発明の一実施例の動作を説明するためのフロー図である。
【0018】従来の方法による問題点は、すべての画像点に対してすべての角度方向θについて加算していたため、孤立点や分離している点の間も線分候補として加算することにあった。これに対して本願発明では、この問題点を解決するために、画素単位で線分の方向を検出し、それをセグメントまたは全画面で積分する。このために、図2に示すように、画像上の点P(Xi ,Yi)を中心とした数近傍のセルSp を定義する。
【0019】セルの大きさは要求される角度分解能Δθによって決定され、たとえばΔθが2π/16のときのセルの大きさは5×5である。セルを定義した後、図2に示すように、点Pを通り360度をK分割する半直線K1〜K16を考え、セル内で予め直線の方向を検出する。直線の方向の検出は、それぞれの直線K1〜K16に対応する画素について画像点の総数を計算し、それが最大となる方向を調べることで可能となる。ただし、直線K1〜K16に対応する画素とは、直線上の画素または直線が画素の境界を通るときにはその境界で囲まれた画素と定義する。
【0020】直線の方向が検出されると、その方向をθK とし、その方向θK に対して加算値mK を1に対応させ、それ以外の方向は0に対応させる。ただし、最大値が複数個ある時は、すべての最大値に対応するθK に対しmK を1とする。最大値に対応するθK を決定した後、次の第(3)式によりθK に対応するρK を計算する。
【0021】
ρK =Xi cosθK +Yi sinθK …(3)
上述の計算により、画素段階で加算に寄与するθK とρK とを決定する。その後、ハフ変換として次の第(4)式で加算する。
【0022】
h(ρK ,θK )=h(ρK ,θK )+mK …(4)
上述のごとくして、画素段階で最大値の数だけ加算が繰返され、それをセグメント内全域で行えばHm (ρ,θ)が、求められ、全画素で行えば、H(ρ,θ)が求められる。
【0023】なお、上述の実施例では、点Pを通りセル内のすべての画像上に最も一致する直線を複数本予め算出するようにしたが、これに限ることなく、直線Kに対応する画素として、直線上の画素または直線が画素の境界を通るときはその境界で囲まれた画素と定義してもよい。この段階で検出する半直線がセル内で枠一杯まで連続した画素で構成されている場合のみに限定すれば、不連続なドットで構成される直線は検出されず、またその制約を設けなければ網目状の線分も検出が可能であり、用途により使い分けることが可能である。 なお、上述のセルの定義から明らかなように、この発明の一実施例により抽出可能な直線の角度分解能Δθはセルの大きさで制限され、セルをより多くの画素で構成すればするほど、角度分解能をより高くすることが可能である。
【0024】この発明が従来のセグメント化法と異なる点は、セグメントをセルと同程度の大きさとしても、セグメント化法がセグメント内では通常のハフ変換を用い、画素の近傍情報が繰込まれないため、従来例で説明した3つの問題点が完全には解決できない点にある。しかしながら、画素の近傍情報を繰込むだけでは、3つの問題点の解決に対して有効であるが、十分ではなく、セグメント化法を併用する方法が最善である。
【0025】図4および図5はこの発明の一実施例の効果を検証するための図である。図4(a)に示すように64×64ドット構成の評価用二値パターンをセグメント化法により線分を抽出すると、図4(c)に示すようになり、この発明の一実施例とセグメント化法を併用した場合には図4(b)に示すような線分が抽出され、元の画像をかなり忠実に再現していることが分かる。
【0026】図5(a)は図4(a)に示すパターンに二値のランダムドットを重ね合わせた図であり、従来法によって線分を抽出すると図5(c)に示すようになり、この発明の一実施例とセグメント化法を併用すると、図5(b)に示すように図4(b)に対応する線分が抽出されており、ノイズの影響を受けにくいことが分かる。このシュミレーション結果により、この発明の一実施例の有効性が明らかである。
【0027】
【発明の効果】以上のように、この発明によれば、線画像から正確に線分を抽出することが可能であるため、文書画像から文字領域と画像領域を分離したり、文字や記号からストロークを抽出するなどの広範囲な分野に適用することができる。
【出願人】 【識別番号】000127673
【氏名又は名称】株式会社エイ・テイ・アール視聴覚機構研究所
【出願日】 平成3年(1991)7月5日
【代理人】 【弁理士】
【氏名又は名称】深見 久郎 (外2名)
【公開番号】 特開平5−12438
【公開日】 平成5年(1993)1月22日
【出願番号】 特願平3−165669