(57)【要約】【課題】多数のコーナーが存在しても相互に干渉して精度を低下させることのない画像処理装置およびその方法を提供する。【解決手段】画像処理方法は、ステップ４０３で画像をハフ変換したハフ平面上でピーク領域を抽出し、一対のピーク領域内のそれぞれのρθデータの座標から、ステップ４０６でρθ座標の表す２直線の交点のｘｙ座標を算出し、ステップ４０７で一対のρθデータから得られる投票値を、交点座標平面上のｘｙ座標の位置に投票することにより、画像内の直線群がそれぞれ交差する位置を求める。【選択図】図４
2010009501.tif 000002
【特許請求の範囲】
【請求項１】
画像をハフ変換したハフ平面上でピーク領域を抽出し、
一対のピーク領域内のそれぞれのρθデータの座標から、そのρθ座標の表す２直線の交点のｘｙ座標を算出し、
前記一対のρθデータから得られる投票値を、交点座標平面上の前記ｘｙ座標の位置に投票することにより、画像内の直線群がそれぞれ交差する位置を求める、
画像処理方法。
【請求項２】
前記投票値として一対のρθデータの平均値を用いる、
請求項１に記載の画像処理方法。
【請求項３】
前記ハフ平面上の投票値の分布に合わせてピーク領域を決定する、
請求項１または２に記載の画像処理方法。
【請求項４】
前記交点座標平面上でそれぞれのピーク領域の重心として交点座標を算出する、
請求項１乃至３の何れか１項に記載の画像処理方法。
【請求項５】
画像データを入力する手段と、
画像をハフ変換したハフ平面上でピーク領域を抽出する手段と、
一対のピーク領域内のそれぞれのρθデータの座標から、そのρθ座標の表す２直線の交点のｘｙ座標を算出する手段と、
前記一対のρθデータから得られる投票値を、交点座標平面上の前記ｘｙ座標の位置に投票することにより、画像内の直線群がそれぞれ交差する位置を求める手段と、
を備える画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置およびその方法に関し、特に、輪郭が直線から形成される物体のコーナーの位置を、低画質の画像からでも正確に求めることを可能とする画像処理装置およびその方法に関する。
【背景技術】
【０００２】
画像中で対象物体の特定領域の位置やサイズを正しく認識するためには、対象物体の輪郭を構成しているコーナーの位置の正確な検出が重要である。これらのコーナーは局所的な演算を用いる各種のコーナー検知器によって検出することが可能であるが、画質が非常に劣化したノイズの多い画像ではコーナーが不明瞭になり、局所的なコーナー検知器ではコーナーを正確に検出することは難しい。画像の画素データが画素領域とその周辺領域で変化する所、すなわち対象物体の輪郭のエッジを追跡してコーナーを探索する方法も、画質が悪くエッジが途切れていたりするとコーナーを正しく検出することが困難である。
【０００３】
特許文献１には処理対象以外の雑音の影響を排除し、ｘｙ平面をρθ平面に変換した空間に対応したメモリを小さくするとともに投票回路の構成をなるべく単純化して処理データ量を少なくし、リアルタイムに処理できる一般化ハフ変換装置が開示されている。ここで、投票とはｘｙ平面上の１点を通る直線群を表す正弦波の各点の頻度数を上げる操作を言う。画像データから任意の線画や図形を抽出するための有効な手法であるハフ変換および一般化ハフ変換は以下に記す問題を有する。
【０００４】
図１は従来技術によるハフ平面のピーク座標からコーナーの座標を計算する方法を示す図である。低画質の画像から対象物体の輪郭を構成しているコーナーの位置を正確に検出する方法としてハフ変換を用いる方法がある。コーナーは輪郭直線の交差点とみなせる場合が多いため、このようなコーナーは、ハフ変換によって直線のパラメータを抽出した後、これら２直線の交点として位置を算出できる。
【０００５】
図１（Ａ）に示す入力画像は輪郭やコーナーが途切れているが、ノイズに強いハフ変換によって図１（Ｂ）に示すようにρθ平面上のピークとして輪郭直線を検出することができる。２点のρθ座標（ρ1，θ1）、（ρ2，θ2）を下に示す式（１）のハフ変換式に入れて連立させて解くことにより、図１（Ｃ）に示すように２直線の交点として各コーナーの座標（ｘ，ｙ）を直接求めることができる。２直線の交点の算出式（２）および（３）を下に示す。
【０００６】
ρ＝ｘｃｏｓθ  ＋  ｙｓｉｎθ  …（１）
【０００７】
ｘ＝(ρ1・ｓｉｎθ2−ρ2・ｓｉｎθ1)／
（ｃｏｓθ1・ｓｉｎθ2  −  ｓｉｎθ1・ｃｏｓθ2)  …（２）
【０００８】
ｙ＝(ρ1・ｃｏｓθ2−ρ2・ｃｏｓθ1)／
（ｓｉｎθ1・ｃｏｓθ2  −  ｓｉｎθ2・ｃｏｓθ1)  …（３）
【０００９】
しかし、この図１に示す従来技術のハフ変換を用いる方法では、輪郭直線を抽出する際、ハフ平面でピーク１点を抽出すれば、そのピーク座標のずれにより交点の計算値に誤差が生じる。あるいは、ピーク近傍からの重心算出などによって精度を上げようとする場合、その近傍領域を正しく決めることが困難であった。なお、ｘｙ平面、ρθ平面は、それぞれ離散化された２次元のデータ配列である。
【００１０】
特許文献２には画像中の用紙のコーナーの座標を元に用紙のコーナーが変形していても正確に傾きを検出できデータ処理量の低いコーナー傾き検出装置が開示されている。しかし、特許文献２に記載のコーナー傾き検出装置は多数のコーナーが存在すると相互に干渉して精度が低下するという問題がある。
【００１１】
図２は従来技術によるハフ平面のピーク座標から逆ハフ変換によりコーナーの座標を計算する方法を示す図である。ハフ平面から輪郭直線の交点を確実に求める方法として、図２に示すように、上記式（１）でハフ変換したρθデータに対してさらに下に示す式（１１）および（１２）で逆ハフ変換を行う方法も考えられる。
【００１２】
ρ1i＝ｘｃｏｓθ1j  ＋  ｙｓｉｎθ1j  …（１１）
【００１３】
ρ2k＝ｘｃｏｓθ2l  ＋  ｙｓｉｎθ2l  …（１２）
【００１４】
図２（Ｂ）に示すρθ平面の１点（ρ1i，θ1j）または（ρ2k，θ2l）は逆ハフ変換によって図２（Ｃ）に示すｘｙ平面の直線に投票され、２点（ρ1i，θ1j）および（ρ2k，θ2l）を変換するとその交点がピークとなってコーナーの位置として検出できる。この方法はノイズに強いものの、投票空間が広く演算量が多いことと、多数のコーナーが存在すると相互に干渉して精度が低下するという問題がある。
【００１５】
ここで、図２（Ｂ）の二重丸あるいは三重丸は、２次元状に広がるρθデータの値を等高線のように模式的に表したものであり、ピークの１点とその周辺の分布を表す。図１（Ｂ）の黒丸は、この等高線のように模式的に表した分布（ピーク領域）の中のピークの１点のみを表したものである。
【００１６】
【特許文献１】特開平４−１８２８８１号公報（特許請求の範囲の［請求項１］、明細書の５１０ページ左上コラム第１１行〜右上コラム第６行、右下コラム第１３行〜第１７行、５１１ページ右下コラム第２０行〜５１２ページ右上コラム第１３行、第１、２図参照）
【特許文献２】特開２００２−１９９１７９号公報（特許請求の範囲の［請求項１］、明細書の段落［０００４］、［０００５］、［００１１］〜［００１６］および図１、図２参照）
【発明の開示】
【発明が解決しようとする課題】
【００１７】
このように、従来技術による特許文献２に記載のコーナー傾き検出装置および逆ハフ変換を用いた画像処理装置には、投票空間が広く演算量が多いという問題と多数のコーナーが存在すると相互に干渉して精度が低下するという問題とがある。
【００１８】
本発明は、このような問題を解決するためになされたものであり、多数のコーナーが存在しても相互に干渉して精度を低下させることのない画像処理装置およびその方法を提供することを目的とする。
【課題を解決するための手段】
【００１９】
実施形態に係る画像処理装置は、画像データを入力する手段と、画像をハフ変換したハフ平面上でピーク領域を抽出する手段と、一対のピーク領域内のそれぞれのρθデータの座標から、そのρθ座標の表す２直線の交点のｘｙ座標を算出する手段と、前記一対のρθデータから得られる投票値を、交点座標平面上の前記ｘｙ座標の位置に投票することにより、画像内の直線群がそれぞれ交差する位置を求める手段と、を備える。
【発明の効果】
【００２０】
実施形態に係る画像処理装置によれば、局所的なコーナー検知器やエッジ追跡によるコーナー検出と異なり、コーナーの検出をハフ変換による直線検出に基いて行っているため、ノイズの多い画像からでも物体のコーナー（輪郭線の交点）を安定かつ正確に抽出することができる。
【００２１】
実施形態に係る画像処理装置によれば、ハフ平面上でρθデータのピーク位置をすぐに求めるのではなく、ピーク近傍のデータ全体を次の交点座標平面に投票して行くため、最後まで情報を保持して正確にコーナー座標を検出することが可能となる。
【００２２】
また、単純な逆ハフ変換に基く投票と異なり、ハフ平面上の２点が交点を持つという条件を利用しているため、より直接的で正確に交点を求めることが可能である。
【００２３】
さらに、２点のピーク近傍のρθデータの様々なペアが、パラメータ平面上へ局所的に投票されるため、処理量を抑えることや、多数のコーナーを持つ場合でも互いの干渉を抑える効果がある。
【発明を実施するための最良の形態】
【００２４】
図３は実施形態に係る画像処理装置によるハフ平面のピーク座標から交点座標平面への変換によりコーナーの座標を計算する方法を示す図である。図３（Ａ）に示すような劣化した画像（ｘｙ平面）であっても、図３（Ｂ）に示すようにハフ変換によってそれぞれの輪郭直線はハフ平面（ρθ平面）のピークとして検出される。
【００２５】
下に式（１）でハフ変換したρθデータに対してさらに下に示す式（２０）および（３０）で交点座標平面への変換を行う。
【００２６】
ρ＝ｘｃｏｓθ  ＋  ｙｓｉｎθ  …（１）
【００２７】
ｘ＝(ρ1i・ｓｉｎθ2l−ρ2k・ｓｉｎθ1j)／
（ｃｏｓθ1j・ｓｉｎθ2l  −  ｓｉｎθ1j・ｃｏｓθ2l)  …（２０）
【００２８】
ｙ＝(ρ1i・ｃｏｓθ2l−ρ2k・ｃｏｓθ1j)／
（ｓｉｎθ1j・ｃｏｓθ2l  −  ｓｉｎθ2l・ｃｏｓθ1j)  …（３０）
【００２９】
輪郭直線の交差点（コーナー）は、ρθ平面上の一対の２点のピークから図１（Ｃ）に示す２直線の交点の算出式（２）および（３）によって表される。従って、図３（Ｂ）に示す２点のピーク近傍のρθデータの様々なペア（ρ1i，θ1j）、（ρ2k，θ2l）を、式（２０）および式（３０）で示す変換式に基いて、コーナー位置の座標を表すｘｙパラメータ平面に投票して行くと、図３（Ｃ）に二重丸および三重丸で示すようにｘｙ平面上でピークが現れる。このピークが、輪郭直線の交差するコーナーの位置を示している。
【００３０】
最後のｘｙ平面上でピークの座標を抽出することにより、コーナーの位置が正しく検出できる。ピーク近傍の投票値の分布に基づいて、コーナーの位置をさらに高精度に検出することも可能である。
【００３１】
図３に示す実施形態に係る画像処理装置は、不図示のＣＰＵ、マウスやキーボード等の入力装置、ＲＡＭ等のメモリ、ハードディスク、ディスプレイやプリンタ等の出力装置および他のコンピュータと通信する通信ユニットを有する。以下、図３および図４のフローチャートを相互に参照しつつハフ平面のピーク座標からコーナー座標を計算する方法について説明する。図４のフローチャートに示す方法はメモリに書込まれたプログラムを実行することにより遂行される。
【００３２】
図４は実施形態のフローチャートを示す図である。
ステップ４０１ではｘｙ平面上の画素値からなる画像データ（ｘ，ｙ）を入力する。
ステップ４０２ではステップ４０１で入力した画像データを図３に示す式（１）を用いてハフ変換する。
【００３３】
ステップ４０３ではステップ４０２でハフ変換した後、ハフ平面ρθ上の２つのピーク領域３１、３２を抽出する。画像内に多数の直線が存在する場合はピーク領域も複数得られる。この場合は、これらのピーク領域の中から、一組ずつペアを順次抽出する。図３の（Ｂ）に示す例では、３つのピーク領域３１、３２、３３が得られ、これら３つのピーク領域３１、３２、３３の中から一対のペア３１、３２を抽出する。３つのピーク領域３１、３２、３３の中から他の一対のペア３２、３３および３１、３３を抽出し、それぞれのペアについて、すなわち交点の数だけステップ４０３〜４０７を繰り返し実行する。次に図５の（Ａ）および（Ｂ）について以下に説明する。
【００３４】
図５はρθ平面から交点座標（ｘ，ｙ）平面へ投票する実施形態を示す図である。すなわち、図５は図３（Ｂ）から図３（Ｃ）を得る実施形態を示す。図５の（Ａ）および（Ｂ）に示す小区分はρθデータおよび画像データの画素の大きさを示す。
【００３５】
図５の（Ａ）に示す２つのピーク領域５１、５２から交点座標（ｘ，ｙ）平面への投票において、ρθデータ平面上に分布する２つのピーク領域５１、５２は、それぞれ、ｉ，ｊおよびｋ，ｌで指し示されるものとする。これらのρθ座標から図３に示した式（２０）および（３０）によって図５の（Ｂ）に示すピーク領域の交点座標５６すなわち（ｘ，ｙ）が計算される。
【００３６】
この交点座標（ｘ，ｙ）の周辺に投票を行うが、通常は最近傍の１点のみに投票を行っても構わない。ｉ，ｊおよびｋ，ｌの全てについてｉ×ｊ×ｋ×ｌ個の投票を行った後には、交点座標（ｘ，ｙ）平面で投票値が２次元の投票領域５８内に分布している。この投票領域５８内に、ピークの座標あるいは重心の座標を求めることにより、交点座標（ｘ，ｙ）が得られる。
【００３７】
再び、図４のフローチャートに戻る。
ステップ４０４では図３（Ｂ）に示す一対のペアのピーク領域３１、３２のうちの一方のピーク領域３１、すなわち図５の（Ａ）に示すピーク領域５１から第１のρθ座標（ρ1i，θ1j）を選択する。
ステップ４０５では図３（Ｂ）に示す一対のペアのピーク領域３１、３２のうちのもう一方のピーク領域３２、すなわち図５の（Ａ）に示すピーク領域５２から第２のρθ座標（ρ2k，θ2l）を選択する。
【００３８】
ステップ４０６では図３（Ｂ）に示す２つの第１ピーク領域３１および第２ピーク領域３２に対応する図５の（Ａ）に示す第１ρθ座標および第２ρθ座標から図３（Ｃ）に示す交点座標３６に対応する図５の（Ｂ）に示す交点座標５６の（ｘ，ｙ）を算出する。すなわち、この交点座標５６の（ｘ，ｙ）を図３に示す式（２０）および(３０)を用いて求める。次に、ステップ４０７について図５を参照しつつ以下に説明する。
【００３９】
ステップ４０７では２つのρθデータ、すなわち、ρθ座標が（ρ1i，θ1j）と（ρ2k，θ2l）であるデータの平均値を（ｘm，ｙn）に投票する。具体的には、図５（Ａ）から図５（Ｂ）を得る。ここで、（ｘm，ｙn）はステップ４０６で得られた交点座標（ｘ，ｙ）を離散化した投票平面上の座標である。通常、この交点座標平面は、画像平面の画素と同じ間隔で離散化して構わない。また、２つのρθデータの平均値以外にも、相乗平均値や最大値／最小値を用いることも可能である。ピーク領域５１、５２を指し示す（ｉ，ｊ）および（ｋ，ｌ）の全ての組み合わせに対して投票を行う。
【００４０】
具体的には、ｉ＝０〜２、ｊ＝０〜３であれば、（ｉ，ｊ）の組み合わせとして１２個のρθデータが存在する。同様に、ｋ＝０〜４、ｌ＝０〜５であれば、（ｋ，ｌ）の組み合わせとして３０個が存在する。従って、ステップ４０４〜４０６は全部で３６０回繰り返し実行することになる。
【００４１】
上記は、式（２０）、（３０）で算出した交点座標（ｘ，ｙ）の最近傍の１点のみに投票を行った場合である。しかし、１点のみに制限せずに、例えば近傍２×２点の範囲の（ｘm，ｙn）に投票することも可能である。投票の処理量が増えるものの、平滑化によりノイズを低減する効果がある。
【００４２】
このようにステップ４０３〜４０７を実行すると、すなわち２つのρθデータの平均値を（ｘm，ｙn）に投票する処理を全ての（ρ1，θ1）と（ρ2，θ2）の組み合わせについて累積して行くと、２次元に分布した交点座標平面上に投票領域５８が得られる。
【００４３】
ステップ４０８では、交点平面ｘｙ上で投票領域５８内のピーク、すなわち周辺の得票値と比べて局所領域内で得票値の高い所である交点座標５６を抽出する。あるいは、得票値の分布の重心座標を求め、その位置を交点座標としてもよい。また、空間フィルタを介した後に局所的最大となる所を検出しても構わない。ここで、空間フィルタは画像データに対して画素値の高い所はより高い画素値に、画素値の低い所はより低い画素値に変換するための係数データである。
【００４４】
前述したピークの座標は、投票領域５８の中で得票値が最大値となるデータの位置を求め、その位置をピーク座標とする。
【００４５】
前述した重心の座標は、ｘm＝１〜４、ｙn＝１〜６としたとき、ｘ方向の重心ｘgは下式（１００）から、ｙ方向の重心ｙgは下式（２００）から算出される。
【００４６】
ｘg＝ΣΣｘｍ×Ｖmn／Ｎ  …  （１００）
ここで、ｘｍはｘ＝１〜４の位置を示し、Ｖmnは（ｘｍ，ｙｎ）におけるデータ値を示し、Ｎはｘｍの幅×ｙｎの幅（画素の数）、この例では２４を示す。
【００４７】
ｙg＝ΣΣｙｎ×Ｖmn／Ｎ  …  （２００）
ここで、ｙｎはｙ＝１〜６の位置を示し、Ｖmnは（ｘｍ，ｙｎ）におけるデータ値を示し、Ｎはｘｍの幅×ｙｎの幅（画素の数）、この例では２４を示す。
【００４８】
このように式（１００）および式（２００）を用いて求めた（ｘg，ｙg）を重心座標とする。
【００４９】
以上の説明において、図４に示す実施形態では、それぞれのペアの投票を全て行った後に、交点座標平面からピーク領域を抽出して交点座標を求めているが、他の実施形態として各ペアの投票の後に逐次ピーク領域の抽出を行って交点座標を求めても構わない。また、これら実施形態で検出する２直線の交点は、物体の角（コーナー）、あるいは、２直線の延長線上の交差点なども含む。
【００５０】
図６は交点座標平面への投票を行うピーク周辺領域を、ハフ平面上の投票値の分布に合わせて決定する方法を示す図である。図６の（Ａ）および（Ｂ）に示す小区分はρθデータおよび画像データの画素の大きさを示す。図６（Ａ）に示すように、局所ピークであるピーク領域６１、６２の周辺において、ρ方向およびθ方向の投票値の分散σを調べ、その一定量、例えば２σの範囲６３、６４を投票領域とする。図６（Ｂ）に示すように、局所ピークであるピーク領域６６、６７の周辺において、例えば「２０」に対して一定値（例えば１／５以上）のρθデータ値「４」以上のρθデータ値を持つデータの範囲６８、６９を投票領域とする。この投票領域６８、６９内に、図５を用いて説明したように、ピークの座標あるいは重心の座標を求めることにより、交点座標（ｘ，ｙ）が得られる。
【００５１】
（付記１）
画像をハフ変換したハフ平面上でピーク領域を抽出し、
一対のピーク領域内のそれぞれのρθデータの座標から、そのρθ座標の表す２直線の交点のｘｙ座標を算出し、
前記一対のρθデータから得られる投票値を、交点座標平面上の前記ｘｙ座標の位置に投票することにより、画像内の直線群がそれぞれ交差する位置を求める、
画像処理方法。  （１）  図３、図４
【００５２】
（付記２）
前記投票値として一対のρθデータの平均値を用いる、
付記１に記載の画像処理方法。  （２）  図４
【００５３】
（付記３）
前記ハフ平面上の投票値の分布に合わせてピーク領域を決定する、
付記１または２に記載の画像処理方法。  （３）  図５
【００５４】
（付記４）
前記交点座標平面上でそれぞれのピーク領域の重心として交点座標を算出する、
付記１乃至３の何れか一つに記載の画像処理方法。  （４）  図６
【００５５】
（付記５）
画像データを入力する手段と、
画像をハフ変換したハフ平面上でピーク領域を抽出する手段と、
一対のピーク領域内のそれぞれのρθデータの座標から、そのρθ座標の表す２直線の交点のｘｙ座標を算出する手段と、
前記一対のρθデータから得られる投票値を、交点座標平面上の前記ｘｙ座標の位置に投票することにより、画像内の直線群がそれぞれ交差する位置を求める手段と、
を備える画像処理装置。  （５）  図３、図４
【００５６】
（付記６）
前記投票値として一対のρθデータの平均値を用いる、
付記５に記載の画像処理装置。  図４
【００５７】
（付記７）
前記ハフ平面上の投票値の分布に合わせてピーク領域を決定する、
付記５または６に記載の画像処理装置。  図５
【００５８】
（付記８）
前記交点座標平面上でそれぞれのピーク領域の重心として交点座標を算出する、
付記５乃至７の何れか一つに記載の画像処理装置。  図６
【図面の簡単な説明】
【００５９】
【図１】従来技術によるハフ平面のピーク座標からコーナーの座標を計算する方法を示す図であり、（Ａ）は入力画像を示す図であり、（Ｂ）は２つのρθ座標を示す図であり、（Ｃ）はコーナーの座標を示す図である。
【図２】従来技術によるハフ平面のピーク座標から逆ハフ変換によりコーナーの座標を計算する方法を示す図であり、（Ａ）は入力画像を示す図であり、（Ｂ）はハフ変換した２つのρθ座標領域を示す図であり、（Ｃ）はハフ変換したコーナーの座標を示す図である。
【図３】実施形態に係る画像処理装置によるハフ平面のピーク座標から逆ハフ変換によりコーナーの座標を計算する方法を示す図であり、（Ａ）は入力画像を示す図であり、（Ｂ）はハフ変換した２つのρθ座標領域を示す図であり、（Ｃ）はｘｙ平面上でピークが現れる輪郭直線の交差するコーナーの位置を示す図である。
【図４】実施形態のフローチャートを示す図である。
【図５】ρθ平面から交点座標（ｘ，ｙ）平面へ投票する実施形態を示す図であり、（Ａ）はρθデータ平面上に分布する２つのピーク領域を示す図であり、（Ｂ）はピーク領域の交点座標（ｘ，ｙ）を示す図である。
【図６】交点座標平面への投票を行うピーク周辺領域を、ハフ平面上の投票値の分布に合わせて決定する方法を示す図であり、（Ａ）は、局所ピーク領域示す図であり、（Ｂ）はピークの座標あるいは重心の座標を求める方法を説明するための図である。
【符号の説明】
【００６０】
３１、３２、３３、５１、５２、６１、６２、６６、６７    ピーク領域
３６、５６    交点座標
５８、６３、６４、６８、６９    投票領域
【図１】
2010009501.tif 000003
【図２】
2010009501.tif 000004
【図３】
2010009501.tif 000005
【図４】
2010009501.tif 000006
【図５】
2010009501.tif 000007
【図６】
2010009501.tif 000008