(57)【要約】【課題】処理対象画像から選択した部分画像を順次ずらしながらハフ変換を行ってハフ変換値を求める処理を高速に行う。【解決手段】処理対象画像から選択した部分画像に対してハフ変換を行ってハフ変換値を算出する（Ｓ２）。そして、移動単位ごとの移動方向及び移動量に基づく分配比によって、ハフ変換値を（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置に分配するハフ変換値分配処理を行う（Ｓ４）。また、移動後の部分画像におけるハフ変換値の増加分及びハフ変換値の減少分を移動差分ハフ変換値として算出する移動差分ハフ変換値算出処理を行い（Ｓ６）、その移動差分ハフ変換値をθ軸方向の各角度に対するｒ軸方向の各位置のハフ変換値に反映させる移動差分ハフ変換値反映処理を行う（Ｓ７）。そして、ハフ変換分配処理、移動差分ハフ変換値算出処理及び移動差分ハフ変換値反映処理を部分画像が前記移動単位で移動するごとに再帰的に行う。【選択図】図７
2009104510.tif 000002
【特許請求の範囲】
【請求項１】
処理対象画像から選択された部分画像を、設定された移動方向及び移動量を移動単位と
して当該移動単位ごとに順次移動させながら前記部分画像に対するハフ変換値を求める画
像処理方法であって、
前記処理対象画像から初期のハフ変換対象となる部分画像を選択し、選択した部分画像
に対してハフ変換を行ってハフ変換値を算出する第１ステップと、
前記移動単位ごとの移動方向及び移動量に基づいて設定された分配比によって、ハフ変
換値を（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置に分配するハフ変換
値分配処理を行う第２ステップと、
前記移動単位で移動した移動後の部分画像に新たに加わる領域に対応するハフ変換値の
増加分及び前記移動後の部分画像から外れる領域に対応するハフ変換値の減少分を前記（
ｒ，θ）座標における移動差分ハフ変換値として算出する移動差分ハフ変換値算出処理を
行う第３ステップと、
前記算出した移動差分ハフ変換値を前記（ｒ，θ）座標のθ軸方向の各角度に対するｒ
軸方向の各位置のハフ変換値に反映させる移動差分ハフ変換値反映処理を行う第４ステッ
プと、
を有し、前記ハフ変換分配処理、前記移動差分ハフ変換値算出処理及び前記移動差分ハ
フ変換値反映処理を前記部分画像が前記移動単位で移動するごとに再帰的に行うことを特
徴とする画像処理方法。
【請求項２】
請求項１に記載の画像処理方法において、
前記（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置におけるハフ変換値
は、前記（ｒ，θ）座標のθ軸方向の各角度に対応してハフ変換値記憶部に記憶され、前
記部分画像が前記移動単位で移動するごとに前記ハフ変換値記憶部に記憶される前記（ｒ
，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置におけるハフ変換値が更新され
ることを特徴とする画像処理方法。
【請求項３】
処理対象画像から選択された部分画像を、設定された移動方向及び移動量を移動単位と
して当該移動単位ごとに順次移動させながら前記部分画像に対するハフ変換値を求める処
理をコンピュータに実行させるための画像処理プログラムであって、
前記処理対象画像から初期のハフ変換対象となる部分画像を選択し、選択した部分画像
に対してハフ変換を行ってハフ変換値を算出する第１ステップと、
前記移動単位ごとの移動方向及び移動量に基づいて設定された分配比によって、ハフ変
換値を（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置に分配するハフ変換
値分配処理を行う第２ステップと、
前記移動単位で移動した移動後の部分画像に新たに加わる領域に対応するハフ変換値の
増加分及び前記移動後の部分画像から外れる領域に対応するハフ変換値の減少分を前記（
ｒ，θ）座標における移動差分ハフ変換値として算出する移動差分ハフ変換値算出処理を
行う第３ステップと、
前記算出した移動差分ハフ変換値を前記（ｒ，θ）座標のθ軸方向の各角度に対するｒ
軸方向の各位置のハフ変換値に反映させる移動差分ハフ変換値反映処理を行う第４ステッ
プと、
を有し、前記ハフ変換分配処理、前記移動差分ハフ変換値算出処理及び前記移動差分ハ
フ変換値反映処理を前記部分画像が前記移動単位で移動するごとに再帰的に行うことを特
徴とする画像処理プログラム。
【請求項４】
処理対象画像から選択された部分画像を、設定された移動方向及び移動量を移動単位と
して当該移動単位ごとに順次移動させながら前記部分画像に対するハフ変換値を求める画
像処理装置であって、
前記処理対象画像から部分画像を選択する部分画像選択部と、
前記処理対象画像から選択された初期のハフ変換対象となる部分画像に対してハフ変換
を行うハフ変換処理部と、
前記移動単位ごとの移動方向及び移動量に基づいて設定された分配比によって、ハフ変
換値を（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置に分配するハフ変換
値分配処理を行うハフ変換分配処理部と、
前記移動単位で移動した移動後の部分画像に新たに加わる領域に対応するハフ変換値の
増加分及び前記移動後の部分画像から外れる領域に対応するハフ変換値の減少分を前記（
ｒ，θ）座標における移動差分ハフ変換値として算出する移動差分ハフ変換値算出処理を
行う移動差分ハフ変換値算出処理部と、
前記算出した移動差分ハフ変換値を前記（ｒ，θ）座標のθ軸方向の各角度に対するｒ
軸方向の各位置のハフ変換値に反映させる移動差分ハフ変換値反映処理を行う移動差分ハ
フ変換値反映処理部と、
を有し、前記ハフ変換分配処理、前記移動差分ハフ変換値算出処理及び前記移動差分ハ
フ変換値反映処理を前記部分画像が前記移動単位で移動するごとに再帰的に行うことを特
徴とする画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハフ変換値を高速に求める画像処理方法、画像処理プログラム及び画像処理
装置に関する。
【背景技術】
【０００２】
図１０及び図１１はハフ変換について説明する図である。ハフ変換は（Ｘ，Ｙ）座標系
で表現される画像を（ｒ，θ）座標系に写像するものである。例えば、図１０（ａ）にお
いて、（Ｘ，Ｙ）座標系のある点（ｘ，ｙ）を考える。これは、（ｄ×ｃｏｓ（φ），ｄ
×ｓｉｎ（φ））と書き換えることも可能である。そうすると、この点はハフ変換によっ
て、下記（１）式に示す（ｒ，θ）座標系の曲線に写像される（図１０（ｂ）参照）。な
お、ハフ変換を行う際の（Ｘ，Ｙ）座標の原点は、処理対象となる画像の中心に置くもの
とする。
【０００３】
ｒ＝ｄ×ｃｏｓ(θ−φ）・・・・・（１）
（１）式で表される曲線に、点（ｘ，ｙ）の値（画素値とする）を重みとして乗算し、
変換対象領域内の全ての点について積算する処理がハフ変換である。具体例として、例え
ば、図１１（ａ）に示すような原点からの距離がｄで、かつ、角度φに直交する直線Ｌは
、ハフ変換の結果、図１１（ｂ）に示すように、（ｒ，θ）座標上で（ｄ，φ）の点Ｐに
画素値の極大値を持つ曲線群に写像される。極大値を与える点Ｐは直線Ｌを表すものであ
るといえる。
【０００４】
なお、図１１（ｂ）は（ｒ，θ）の２次元座標として表されているが、実際には、（ｒ
，θ）平面に直交する軸方向にハフ変換値の大きさを有している。図１１（ｂ）において
は、ハフ変換値の大きさをグレースケールのグラデーションで表している。すなわち、図
１１（ｂ）におけるグレースケールで描かれた部分は、極大値を与える点Ｐを通る曲線群
が表すハフ変換値の大きさを模式的に表現したものである。
【０００５】
図１２はハフ変換された（ｒ，θ）座標から（Ｘ，Ｙ）座標への変換を説明する図であ
る。図１２（ａ）は図１０（ｂ）に対応するものであり、ハフ変換によって得られた（ｒ
，θ）座標上の曲線のある点（ｄ，φ）は、（Ｘ，Ｙ）座標上の直線Ｌに写像される（図
１２（ｂ）参照）。つまり、ハフ変換による（ｒ，θ）座標系の（ｄ，φ）なる点は、（
Ｘ，Ｙ）座標系においては、原点からの距離がｄで、かつ、Ｙ軸と図に示すように角度φ
で交差する直線Ｌに対応する。
【０００６】
図１０〜図１２の説明からも明らかであるように、ハフ変換は線分検出に好適なもので
ある。画像から線分を検出する技術は、画像認識、文字認識、ステレオビジョン、ロボッ
トビジョンなどにおいて多用される重要な技術である。そのため、ハフ変換処理の高速化
は、これらの技術の高速化に非常に大きな効果がある。
【０００７】
ハフ変換の高速化に係わる従来技術としては、例えば、特許文献１〜３に開示された技
術がある。特許文献１に開示された技術（第１従来技術という）は、ハフ変換をハードウ
エアにおいて処理する際、ハードウエア上で使用されるゲート数、ゲート段数を削減する
ことにより、ハフ変換の高速化を図ろうとするものである。
【０００８】
特許文献２に開示された技術（第２従来技術という）は、ハフ変換のθの範囲を分割し
、そのそれぞれに最適な演算、変換手段を用いることにより、ハフ変換の高速化を図ろう
とするものである。
【０００９】
特許文献３に開示された技術（第３従来技術という）は、ハフ変換対象となる画像を部
分領域に分割し、重複する演算を排除することにより、ハフ変換の高速化を図ろうとする
ものである。
【００１０】
【特許文献１】特開平８−６９５２８号公報
【特許文献２】特開平１０−１４３６５８号公報
【特許文献３】特開平１０−３３４２３５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上記第１〜第３従来技術は、単独の画像に対して如何に高速なハフ変換を可能とするか
についての技術である。一方、図１３に示すように、全体画像の中から部分画像を選択し
、選択した部分画像を順次ずらしながらハフ変換を行う場合がある。これは、例えば、画
像中から特定の特徴部分を検出したり、あるいは複数の画像間の相関を求めたりする場合
に必要となる処理である。
【００１２】
このような場合、第１〜第３従来技術においては、その選択した部分画像のそれぞれに
同等のハフ変換処理を行わなければならない。そのため、検出精度を向上させるために非
常に小さな移動単位で部分画像の選択を行うと、選択される部分画像の総数が多くなり、
演算量がそれに比例して増大するという問題がある。
【００１３】
そこで本発明は、全体画像の中から部分画像を選択し、選択した部分画像を順次ずらし
ながらハフ変換値を求める場合に、高速化を可能とする画像処理方法、画像処理プログラ
ム及び画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の画像処理方法は、処理対象画像から選択された部分画像を、設定された移動方
向及び移動量を移動単位として当該移動単位ごとに順次移動させながら前記部分画像に対
するハフ変換値を求める画像処理方法であって、前記処理対象画像から初期のハフ変換対
象となる部分画像を選択し、選択した部分画像に対してハフ変換を行ってハフ変換値を算
出する第１ステップと、前記移動単位ごとの移動方向及び移動量に基づいて設定された分
配比によって、ハフ変換値を（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位
置に分配するハフ変換値分配処理を行う第２ステップと、前記移動単位で移動した移動後
の部分画像に新たに加わる領域に対応するハフ変換値の増加分及び前記移動後の部分画像
から外れる領域に対応するハフ変換値の減少分を前記（ｒ，θ）座標における移動差分ハ
フ変換値として算出する移動差分ハフ変換値算出処理を行う第３ステップと、前記算出し
た移動差分ハフ変換値を前記（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位
置のハフ変換値に反映させる移動差分ハフ変換値反映処理を行う第４ステップとを有し、
前記ハフ変換分配処理、前記移動差分ハフ変換値算出処理及び前記移動差分ハフ変換値反
映処理を前記部分画像が前記移動単位で移動するごとに再帰的に行うことを特徴とする。
【００１５】
このように、本発明の画像処理方法は、処理対象画像から部分画像を選択し、選択した
部分画像を順次ずらしながらハフ変換を行ってハフ変換値を求める場合に好適な画像処理
方法である。なお、部分画像の移動単位ごとの移動量は、当該部分画像全体から見るとわ
ずかな量であるとする。このような場合において、本発明では移動後の部分画像における
ハフ変換値の大部分については、移動前の部分画像のハフ変換値を分配処理することによ
って求め、また、部分画像の移動により新たに加わる領域及び処理対象から外れる領域に
ついては、新たに加わる領域に対応するハフ変換値の増加分及び処理対象から外れる領域
に対応して算出した移動差分ハフ変換値を、（ｒ，θ）座標のθ軸方向の各角度に対する
ｒ軸方向の各位置に反映させるようにして移動後の部分画像全体のハフ変換値を求めるよ
うにしている。
【００１６】
このような処理を行うことにより、移動後の部分画像それぞれに対して、初期のハフ変
換と同等のハフ変換を行う必要がなくなる。なお、ハフ変換値の分配処理は、単に、分配
比によって比例配分するだけの処理であるので、移動後の各部分画像それぞれにおいてハ
フ変換を行う場合に比べて、演算量を大幅に削減することができる。また、移動差分ハフ
変換値を算出して算出した移動差分ハフ変換値を反映する処理も、移動単位としての移動
量が部分画像全体に比べて非常に小さければ、その演算量はそれほど大きなものとはなら
ない。
【００１７】
したがって、本発明の画像処理方法によれば、処理対象画像から部分画像を選択し、選
択した部分画像を順次ずらしながらハフ変換を行ってハフ変換値を求める場合、選択され
たそれぞれの部分画像に対するハフ変換を少ない演算量で、かつ、高速に行うことができ
る。特に、本発明の画像処理方法は、小さな移動単位で部分画像を移動させるような場合
、選択される部分画像の総数が多くなることから、より大きな効果が得られる
【００１８】
本発明の画像処理方法において、前記（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸
方向の各位置におけるハフ変換値は、前記（ｒ，θ）座標のθ軸方向の各角度に対応して
ハフ変換値記憶部に記憶され、前記部分画像が前記移動単位で移動するごとに前記ハフ変
換値記憶部に記憶される前記（ｒ，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位
置におけるハフ変換値が更新されるようにしている。
これにより、部分画像の移動ごとに再帰的なハフ変換分配処理を行うことができ、移動
後の部分画像の各位置におけるハフ変換値を少ない演算量で求めることができる。
【００１９】
本発明の画像処理プログラムは、処理対象画像から選択された部分画像を、設定された
移動方向及び移動量を移動単位として当該移動単位ごとに順次移動させながら前記部分画
像に対するハフ変換値を求める処理をコンピュータに実行させるための画像処理プログラ
ムであって、前記処理対象画像から初期のハフ変換対象となる部分画像を選択し、選択し
た部分画像に対してハフ変換を行ってハフ変換値を算出する第１ステップと、前記移動単
位ごとの移動方向及び移動量に基づいて設定された分配比によって、ハフ変換値を（ｒ，
θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置に分配するハフ変換値分配処理を
行う第２ステップと、前記移動単位で移動した移動後の部分画像に新たに加わる領域に対
応するハフ変換値の増加分及び前記移動後の部分画像から外れる領域に対応するハフ変換
値の減少分を前記（ｒ，θ）座標における移動差分ハフ変換値として算出する移動差分ハ
フ変換値算出処理を行う第３ステップと、前記算出した移動差分ハフ変換値を前記（ｒ，
θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置のハフ変換値に反映させる移動差
分ハフ変換値反映処理を行う第４ステップとを有し、前記ハフ変換分配処理、移動差分ハ
フ変換値算出処理及び前記移動差分ハフ変換値反映処理を前記部分画像が前記移動単位で
移動するごとに再帰的に行うことを特徴とする。
【００２０】
本発明の画像処理プログラムをコンピュータに実行させることによって、前記本発明の
画像処理方法で行うべき処理の実行が可能となり、前記本発明の画像処理方法と同様の効
果を得ることができる。なお、本発明の画像処理プログラムにおいても、前記本発明の画
像処理方法のそれぞれの特徴を有することが好ましい。
【００２１】
本発明の画像処理装置は、処理対象画像から選択された部分画像を、設定された移動方
向及び移動量を移動単位として当該移動単位ごとに順次移動させながら前記部分画像に対
するハフ変換値を求める画像処理装置であって、前記処理対象画像から部分画像の選択を
可能とする部分画像選択部と、前記処理対象画像から選択された初期のハフ変換対象とな
る部分画像に対してハフ変換を行うハフ変換処理部と、前記移動単位ごとの移動方向及び
移動量に基づいて設定された分配比によって、ハフ変換値を（ｒ，θ）座標のθ軸方向の
各角度に対するｒ軸方向の各位置に分配するハフ変換値分配処理を行うハフ変換分配処理
部と、前記移動単位で移動した移動後の部分画像に新たに加わる領域に対応するハフ変換
値の増加分及び前記移動後の部分画像から外れる領域に対応するハフ変換値の減少分を前
記（ｒ，θ）座標における移動差分ハフ変換値として算出する移動差分ハフ変換値算出処
理を行う移動差分ハフ変換値算出処理部と、前記算出した移動差分ハフ変換値を前記（ｒ
，θ）座標のθ軸方向の各角度に対するｒ軸方向の各位置のハフ変換値に反映させる移動
差分ハフ変換値反映処理を行う移動差分ハフ変換値反映処理部とを有し、前記ハフ変換分
配処理、前記移動差分ハフ変換値算出処理及び前記移動差分ハフ変換値反映処理を前記部
分画像が前記移動単位で移動するごとに再帰的に行うことを特徴とする。
【００２２】
本発明の画像処理装置がこのような構成を有することにより、前記本発明の画像処理方
法で行うべき処理の実行が可能となり、前記本発明の画像処理方法と同様の効果を得るこ
とができる。なお、本発明の画像処理装置においても、前記本発明の画像処理方法のそれ
ぞれの特徴を有することが好ましい。
【発明を実施するための最良の形態】
【００２３】
図１は処理対象となる画像から選択された部分画像に対するハフ変換処理について説明
する図である。図１（ａ）に示すように、部分画像Ｇ１に３つの直線Ｌ１，Ｌ２，Ｌ３が
あったとする。なお、部分画像の中心は（Ｘ，Ｙ）座標の原点におくものとする。また、
直線Ｌ１のＸ軸に対する角度はθ、直線Ｌ２のＸ軸に対する角度はπ／２、直線Ｌ３のＸ
軸に対する角度はφであるとする。そうすると、これら３本の直線Ｌ１，Ｌ２，Ｌ３はハ
フ変換により、（ｒ，θ）座標系において、図１（ｂ）に示すように、極大値を与える点
Ｐ１，Ｐ２，Ｐ３に変換される。
【００２４】
図２は図１で示した部分画像Ｇ１を移動させた場合について説明する図である。図２（
ａ）において、実線で示す領域が移動後の部分画像（部分画像Ｇ１’とする）であり、こ
の部分画像Ｇ１’は、部分画像Ｇ１（一点鎖線で示す）の位置からＸ軸方向へ所定量だけ
移動している。この場合、部分画像Ｇ１と部分画像Ｇ１’とにおいて、図示の領域Ｍはそ
れぞれの部分画像において重複する領域である。なお、移動量は部分画像全体から見ると
わずかな量であるとする。
【００２５】
このように、選択すべき部分画像をＸ軸方向にわずかな量だけ移動させると、移動後の部
分画像Ｇ１’は、移動前の部分画像Ｇ１に比べて、新たに加わる領域（増加領域αという
）と処理対象から外れる領域（減少領域βという）が生じる。なお、増加領域α及び減少
領域βは図２（ａ）においては灰色で示されている。
【００２６】
また、図２（ａ）の例のように、部分画像Ｇ１がＸ軸方向にわずかに移動すると、移動
後の部分画像Ｇ１’においては、角度θの直線Ｌ１は、角度θはそのままで、原点からの
距離ｒが小さくなる方向へ変化する。また、角度π／２の直線Ｌ２は、角度π／２と原点
からの距離ｒは変化しない。また、角度φの直線Ｌ３は、角度φはそのままで、原点から
の距離ｒが大きくなる方向へ変化することになる。なお、図２（ａ）においては、移動後
の部分画像Ｇ１’における原点から各直線Ｌ１，Ｌ２，Ｌ３までの距離をｒ’で表わして
いる。
【００２７】
また、移動後の部分画像Ｇ１’には移動前の部分画像Ｇ１に比べて、増加領域αが新た
に加わることになるため、移動後の部分画像Ｇ１’においては、増加領域α内の直線Ｌ１
，Ｌ２に対応するハフ変換値（ハフ変換値増加分という）を移動後の部分画像Ｇ１’の各
位置におけるハフ変換値に反映（加算）させる必要がある。同様に、移動後の部分画像Ｇ
１’には減少領域βが存在し、この減少領域内の直線Ｌ２，Ｌ３に対応するハフ変換値が
処理対象から外れることとなるため、移動後の部分画像Ｇ１’においては、これら減少領
域βに対応するハフ変換値（ハフ変換値減少分という）を移動後の部分画像Ｇ１’の各位
置におけるハフ変換値に反映（減算）させる必要がある。
【００２８】
図２（ｂ）は図２（ａ）に示した部分画像Ｇ１の移動に伴う（ｒ，θ）座標上での極大
値を与える点Ｐ１，Ｐ２，Ｐ３のｒ軸方向への変化とハフ変換値の変化を示す図である。
図２からも明らかなように、移動前の部分画像Ｇ１において（ｒ，θ）にあった点Ｐ１は
、移動後の部分画像Ｇ１’においては、ｒが小さくなる方向へ移動し、かつ、ハフ変換値
が増加することになる。
また、移動前の部分画像Ｇ１において（ｒ，π／２）にあった点Ｐ２は、移動後の部分
画像Ｇ１’においては、ｒは変化しないが、ハフ変換値が増加及び減少することになる。
また、移動前の部分画像Ｇ１において（ｒ，φ）にあった点は、移動後の部分画像Ｇ１’
においては、ｒが大きくなる方向へ移動し、かつ、ハフ変換値が減少することになる。す
なわち、部分画像が移動することにより、ハフ変換値は（ｒ，θ）座標において、ｒが増
加または減少する方向に移動し、かつ、その値が変化する。
【００２９】
なお、図２においては、部分画像を（Ｘ，Ｙ）座標におけるＸ方向に移動させる場合に
ついて説明したが、Ｘ軸方向への移動に限らず、任意の方向の移動であっても同様に考え
ることができる。つまり、ハフ変換を行うことにより、（Ｘ，Ｙ）座標系での回転は、（
ｒ，θ）座標系においては単にθ軸方向への移動に変換されるだけであり、図２で説明し
た内容は任意の方向への移動について成り立つ。
【００３０】
図３は部分画像の移動方向を任意の方向とした場合について説明する図である。なお、
ここでは、部分画像Ｇ１の移動方向をΦとする。図３（ａ）に示すように、部分画像Ｇ１
の移動方向Φを中心とする±π／２の範囲（ただし、Φ±π／２の位置は除く）において
は、ｒが小さくなる方向へハフ変換値が移動する。なお、移動方向Φにおいては、ｒは小
さくなる方向にその変化量が最大となる。
【００３１】
また、部分画像の移動方向Φに対して±π／２の位置、すなわち、Φ±π／２の位置（
部分画像の移動方向Φと直交する方向）においてはｒ方向へのハフ変換値の移動はない。
また、部分画像の移動方向Φに対して、±π／２を超える範囲においては、ｒが大きく
なる方向へハフ変換値が移動する。なお、部分画像の移動方向Φに対して、Φ±πの位置
においては、ｒは大きくなる方向にその変化量が最大となる。
【００３２】
図３（ｂ），（ｃ）は、図３（ａ）で示した部分画像の移動に伴うハフ変換値の変化を
模式的に示す図である。図３（ｂ），（ｃ）において、太線の四角の領域は部分画像Ｇ１
に対応する領域であるとし、その領域内の細線で示す多数の小さな升目には、それぞれ所
定のハフ変換値が求められているものとする。
【００３３】
ここで、図３（ａ）で説明したように、部分画像が移動方向Φに所定量（部分画像の領
域全体に比べてわずかな量）だけ移動したとすると、図３（ｃ）に示すように、移動後の
部分画像におけるハフ変換値は、ｒが変化する方向にその値を移動させたものとなる。し
たがって、部分画像をわずかに移動させた場合、移動前の部分画像において求められてい
るハフ変換値を移動後の部分画像に分配する処理（ハフ変換値分配処理という）を行うこ
とにより、移動後の部分画像におけるハフ変換値の大部分を求めることができる。
【００３４】
図４は移動後の部分画像のハフ変換値をハフ変換値分配処理によって求める方法につい
て説明する図である。説明を簡単にするために、図４（ａ）のように、（ｒ，θ）座標の
ある角度に対するｒ軸方向のハフ変換値がＡ，Ｂ，Ｃ，Ｄであり、また、部分画像が図４
（ｂ）のように移動量δで移動した場合を考える。
【００３５】
なお、部分画像の移動量は、（ｒ，θ）座標系におけるｒ軸方向のｒ値の刻み整数倍で
はないものとする。このため、図４（ｃ）のように、移動量δに基づく分配比でハフ変換
値をｒ軸方向に分配するという処理を行う。具体的には、（１−δ）とδの分配比を設定
し、その分配比でハフ変換値を移動後の部分画像の各位置に分配する。ただし、このよう
なハフ変換値分配処理によって求めることができるのは、移動後の部分画像と移動前の部
分画像とにおいて重複する領域に対するハフ変換値である。
これにより、移動後の部分画像の各位置におけるハフ変換値は、図４（ｃ）に示すよう
に、移動前の部分画像における各位置のハフ変換値が（１−δ）とδの分配比によって分
配されたものとなる。
【００３６】
このように、部分画像の移動単位ごとの移動量がわずかである場合、移動後における部
分画像のハフ変換値の大部分は、図４に示すようなｒ軸方向におけるハフ変換値分配処理
により求められることになる。
【００３７】
ただし、図４で説明したハフ変換値分配処理は、移動前の部分画像と移動後の部分画像
とにおいて重複する領域のみに対して行なわれるものである。このため、図４で説明した
ハフ変換値分配処理では、部分画像の移動によって生じる増加領域（例えば、図２におけ
る増加領域αなど）に対応するハフ変換値及び減少領域（例えば、図２における減少領域
βなど）に対応するハフ変換値は移動後の部分画像に反映されない。
【００３８】
したがって、増加領域に対応するハフ変換値（ハフ変換値増加分）及び減少領域に対応
するハフ変換値（ハフ変換値減少分）を、移動後の部分画像の各位置におけるハフ変換値
にそれぞれ反映させる処理を行う必要があり、このような反映処理を行うことによって、
移動後の部分画像全体の各位置におけるハフ変換値を求めることができる。なお、増加領
域に対応するハフ変換値増加分及び減少領域に対応するハフ変換値減少分をまとめて移動
差分ハフ変換値と呼ぶことにする。
【００３９】
図５は移動差分ハフ変換値を反映させる移動差分ハフ変換値反映処理について説明する
図である。なお、図５では、部分画像を（Ｘ，Ｙ）座標におけるＸ軸方向に移動させた場
合を示し、太線で示す領域が移動後の部分画像Ｇ１’であるとする。図５（ａ）において
、部分画像の移動により生じる増加領域α及び減少領域βをそれぞれ灰色で示している。
【００４０】
ここで、例えば、図５（ａ）における増加領域α内のある１つの位置（Ｑ１とする）及
び減少領域β内のある１つの位置（Ｑ２とする）における移動差分ハフ変換値を移動後の
部分画像Ｇ１’に反映させる場合について考える。図５（ｂ）は位置Ｑ１，Ｑ２をハフ変
換することによって得られる（ｒ，θ）座標上の曲線を示すものである。すなわち、位置
Ｑ１は（ｒ，θ）座標においては、図５の実線で示す曲線Ｃ１のように写像され、位置Ｑ
２は（ｒ，θ）座標においては、図５の破線で示す曲線Ｃ２のように写像される。
【００４１】
よって、曲線Ｃ１に対応する移動差分ハフ変換値を移動後の部分画像Ｇ１’の対応する
位置のハフ変換値に加算することによって、増加領域αのある１つの位置（この例では、
Ｑ１としている）における移動差分ハフ変換値を移動後の部分画像Ｇ１’に反映させるこ
とができる。同様に、曲線Ｃ２に対応する移動差分ハフ変換値を移動後の部分画像Ｇ１’
の対応する位置のハフ変換値から減算することによって、減少領域βのある１つの位置（
この例では、Ｑ２としている）における移動差分ハフ変換値を移動後の部分画像Ｇ１’に
反映させることができる。
【００４２】
なお、図５においては増加領域α及び減少領域βそれぞれにおいて、ある一点のみにつ
いての移動差分ハフ変換値を反映させる例について説明したが、増加領域α及び減少領域
β内の他の位置についても同様の処理を行うことにより、移動後の部分画像Ｇ１’の各位
置に対して移動差分ハフ変換値を反映させることができる。
【００４３】
ところで、増加領域α及び減少領域βは、図５（ａ）に示されるように、部分画像全体
に比べて非常に小さな領域である。よって、増加領域α及び減少領域βの各位置において
求められた移動差分ハフ変換値を移動後の部分画像Ｇ１’に反映させる処理を行ったとし
ても、その演算量はそれほど大きなものとはならない。具体的には、（Ｘ，Ｙ）座標にお
けるＹ軸方向の点をＮ点、（ｒ，θ）座標におけるθ軸方向の点をＫ点とすれば、図５の
例では、（２Ｎ×Ｋ）回の加減算によって行うことができる。
【００４４】
以上の説明から明らかであるように、本発明の実施形態に係る画像処理方法によれば、
移動後の部分画像におけるハフ変換値の大部分は、ハフ変換値分配処理により求めること
ができ、さらに、移動差分ハフ変換値反映処理を行うことにより、移動後の部分画像全体
のハフ変換値を求めることができる。なお、部分画像の移動により生じる増加領域及び減
少領域のハフ変換値を移動後の部分画像のどの部分に反映させるかについては、移動方向
、移動量が定まった時点で一意に定まる。よって、その値を予め持つことにより、三角関
数の計算などを省略することが可能となる。
【００４５】
以上説明した本発明の実施形態に係る画像処理方法において、移動後の部分画像全体の
ハフ変換値を求めるに必要な演算量を具体的な例で示す。例えば、部分画像におけるＸ方
向のデータ数が３２、Ｙ方向のデータ数が３２、その対角方向つまりｒ軸方向のデータ数
が４６であるとし、また、θ軸方向のデータ数が９０、移動がＸ軸方向に１であるとする
。そうすると、従来のハフ変換で行われている単純な演算においては、３２×３２×９０
＝９２１６０回の三角関数の計算、および加算処理が必要となる。
【００４６】
一方、本発明の実施形態に係る画像処理方法によれば、図４で説明したようなハフ変換
値分配処理が、９０×４６＝４１４０回、また、図５で説明したような移動差分ハフ変換
値反映処理が、３２×２×９０＝５７６０回であり、両者を加えても９９００回である。
つまり、このような非常に粗い演算処理の見積もりにおいても、本発明の実施形態に係る
画像処理方法は、従来のハフ変換で行われている単純な演算の１０数パーセント程度の演
算量でハフ変換を実行できることになる。
【００４７】
図６は本発明の実施形態に係る画像処理装置の構成を示す図である。本発明の実施形態
に係る画像処理装置１００は、図１に示すように、処理対象となる画像が入力される画像
入力部１１０、処理対象となる画像から初期のハフ変換対象となる初期の部分画像を選択
する機能及び移動単位となる移動方向及び移動量に基づいて移動後の部分画像を選択する
機能を有する部分画像選択部１２０、部分画像の移動単位となる移動方向と移動量を設定
する移動方向及び移動量設定部１３０、部分画像選択部１２０によって選択された初期の
部分画像に対して初期のハフ変換を行って初期のハフ変換値を算出するハフ変換処理部１
４０を有している。
【００４８】
また、ハフ変換処理部１４０で算出された（ｒ，θ）座標におけるｒ軸方向の初期のハ
フ変換値及び部分画像の移動単位ごとの移動後において更新されたハフ変換値をθ軸方向
の各θ値ごとに記憶するハフ変換値記憶部１５０、ハフ変換値記憶部１５０に記憶された
各θ値ごとのハフ変換値を（ｒ，θ）座標におけるｒ軸方向に分配するハフ変換値分配処
理部１６０を有している。
【００４９】
また、移動方向及び移動量設定部１３０により設定された移動方向と移動量により生じ
る増加領域減少領域に対応するハフ変換値増加分及びハフ変換値減少分を移動差分ハフ変
換値として算出する移動差分ハフ変換値算出部１７０、移動差分ハフ変換値算出部１７０
で算出された移動差分ハフ変換値を移動後の部分画像の対応する位置に反映させる移動差
分ハフ変換値反映処理部１８０を有している。
【００５０】
ハフ変換値記憶部１５０は、（ｒ，θ）座標における各θ値ごとにｒ軸方向のハフ変換
値を記憶するｒ軸方向ハフ変換値記憶部１５１，１５２，１５３，・・・を有している。
また、ハフ変換値分配処理部１６０は、ｒ軸方向ハフ変換値記憶部１５１，１５２，１５
３，・・・からそれぞれ対応するｒ軸方向ハフ変換値を取得してｒ軸方向に分配するｒ軸
方向ハフ変換値分配処理部１６１，１６２，１６３，・・・を有している。
【００５１】
図７は図６に示した実施形態に係る画像処理装置の動作手順を説明するフローチャート
である。まず、初期の部分画像を選択し（ステップＳ１）、選択した初期の部分画像に対
して初期のハフ変換を行って初期のハフ変換値を設定する（ステップＳ２）。ステップＳ
２において行われるハフ変換は、どのような手法によるハフ変換であってもよく、例えば
、ハフ変換の原理に従った演算量の多い手法によるハフ変換であってもよく、また、ハフ
変換の高速化を目的とした前述の第１〜第３従来技術によるものであってもよい。
【００５２】
そして、部分画像の選択がすべて終了したか否かを判定し（ステップＳ３）、部分画像
の選択がすべて終了していなければ、移動方向及び移動量設定部１３０で設定された移動
単位としての移動方向及び移動量に基づいて、ハフ変換値分配処理を行う(ステップＳ４)
。このハフ変換値分配処理は、図３及び図４により説明した処理であり、これは、図６に
示したハフ変換分配処理部１６０のｒ軸方向ハフ変換値分配処理部１６１，１６２，１６
３，・・・が、ハフ変換値記憶部１５０のｒ軸方向ハフ変換値記憶部１５１，１５２，１
５３，・・・からそれぞれ対応するｒ軸方向ハフ変換値を取得することによって行う。
【００５３】
そして、移動方向及び移動量設定部１３０で設定された移動方向及び移動量に基づいて
部分画像を選択し（ステップＳ５）、部分画像の移動によって生じる増加領域（例えば、
図５の増加領域α）に対応するハフ変換値増加分及び減少領域（例えば、図５の減少領域
β）に対応するハフ変換値減少分をそれぞれ移動差分ハフ変換値として算出する（ステッ
プＳ６）。そして、算出した移動差分ハフ変換値をステップＳ４で求められた移動後の部
分画像の各位置におけるハフ変換値に反映させる移動差分ハフ変換値反映処理を行い（ス
テップＳ７）、移動後の部分画像のハフ変換値を求める。そしてステップ３に戻る。ステ
ップＳ７で行われる移動差分ハフ変換値反映処理は、図５により説明したような処理であ
る。
【００５４】
以上、ステップＳ３〜Ｓ７の処理を、選択すべき部分画像が終了するまで行う。なお、
ハフ変換値記憶部１５０のｒ軸方向ハフ変換値記憶部１５１，１５２，１５３，・・・に
記憶される各ｒ軸方向のハフ変換値は、部分画像の移動に伴うハフ変換値分配処理及び移
動差分ハフ変換値反映処理がなされるごとにその記憶内容が更新される。
【００５５】
図８は図６のハフ変換値分配処理部１６０が行うハフ変換値分配処理（図７におけるス
テップＳ４）の処理手順を説明するフローチャートである。このハフ変換値配分処理につ
いては、図３及び図４により具体的に説明したので、ここでは処理手順のみについて簡単
に説明する。
【００５６】
図８に示すように、まず、（ｒ，θ）座標におけるθ軸方向の各θに対応する全てのｒ
軸方向ラインを処理したか否かを判定し（ステップＳ１１）、全てのｒ軸方向ラインを処
理していれば処理を終了するが、全てのｒ軸方向ラインを処理していなければ、処理対象
となるｒ軸方向ラインを選択し、その時点で設定されている移動方向及び移動量に基づい
てハフ変換値分配比を求める（ステップＳ１２）。そして、選択されたｒ軸方向ラインの
各位置に対し、ステップＳ１２によって求められた分配比でハフ変換値を分配する（ステ
ップＳ１３）。
【００５７】
図９は図６の移動差分ハフ変換値反映処理部１８０が行う移動差分ハフ変換値反映処理
（図７におけるステップＳ７）の処理手順を説明するフローチャートである。この移動差
分ハフ変換値反映処理については、図５により具体的に説明したので、ここでは処理手順
のみについて簡単に説明する。図９に示すように、まず、まず、全ての移動差分ハフ変換
値（ハフ変換値増加分またはハフ変換値減少分）について反映処理を行ったか否かを判定
し（ステップＳ２１）、全ての移動差分ハフ変換値について反映処理が終了していれば処
理を終了するが、全ての移動差分ハフ変換値について反映処理が終了していなければ、移
動差分ハフ変換値を１つ選択する（ステップＳ２２）。
【００５８】
ここで、選択した移動差分ハフ変換値は減算すべきハフ変換値（ハフ変換値減少分）で
あるか否かを判定し（ステップＳ２３）、減算すべきハフ変換値でなければ、そのままス
テップＳ２４の処理を行い、減算すべきハフ変換値である場合には、当該移動差分ハフ変
換値を−１倍（ステップＳ２５）したのち、ステップＳ２４の処理を行う。
【００５９】
ステップＳ２４の処理は、（ｒ，θ）座標における全てのθについて移動差分ハフ変換
値反映処理が終了したか否かを判定するものであり、全てのθについて反映処理が終了し
ていなければ、当該θにおけるｒ軸方向ラインの位置を求め（ステップＳ２６）、求めた
ｒ軸方向ラインの位置のハフ変換値に移動差分ハフ変換値を加算する(ステップＳ２７)。
なお、ステップＳ２６におけるｒ軸方向ラインの位置を求める処理は、例えば、図５にお
いて説明したように、（ｒ，θ）座標上に写像された曲線Ｃ１，Ｃ２（図５（ｂ）参照）
に対応する位置を求める処理である。
【００６０】
そして、ステップＳ２４に戻り、全てのθについて移動差分ハフ変換値反映処理が終了
したか否かを判定し、全てのθについて移動差分ハフ変換値反映処理が終了していなけれ
ば、ステップＳ２６以降の処理を行い、全てのθについて移動差分ハフ変換値反映処理が
終了していれば、ステップＳ２１に戻る。そして、全ての移動差分ハフ変換値について反
映処理が行われたか否かを判定し（ステップＳ２１）、全ての移動差分ハフ変換値につい
て反映処理を終了していなければ、ステップＳ２２以降の処理を行い、全ての移動差分ハ
フ変換値について反映処理が終了していれば処理を終了する。
【００６１】
以上説明したように、本発明の実施形態によれば、図７のステップＳ２において求めた
初期のハフ変換値を基にして、部分画像の移動方向及び移動量に基づくハフ変換分配処理
、移動差分ハフ変換値算出処理及び移動差分ハフ変換値反映処理を部分画像の移動ごとに
再帰的に行うことにより、移動後の部分画像の各位置におけるハフ変換値を求めるように
している。このような処理を行うことにより、全体画像の中から部分画像を選択し、選択
した部分画像をわずかずつ順次ずらしながらハフ変換を行う場合、各移動後の部分画像に
おけるハフ変換値を少ない演算量で高速に求めることができる。
【００６２】
なお、本発明は上述の実施形態に限られるものではなく、本発明の要旨を逸脱しない範
囲で種々変形実施可能となるものである。例えば、移動単位としての移動方向及び移動量
は、部分画像を選択するごとに任意の移動方向と移動単位量の設定が可能である。
【００６３】
また、前述の各実施形態において説明したハフ変換を行うための処理をコンピュータに
実行させるためのプログラムとしての画像処理プログラムを作成することが可能であり、
また、作成した画像処理プログラムを各種の記録媒体に記録させておくことも可能である
。したがって、本発明は、これら画像処理プログラムとその画像処理プログラムを記録し
た記録媒体をも含むものである。また、画像処理プログラムはネットワークから取得する
ようにしてもよい。
【図面の簡単な説明】
【００６４】
【図１】処理対象画像において選択されたある部分画像のハフ換について説明する図。
【図２】図１で示した部分画像Ｇ１を移動させた場合について説明する図。
【図３】部分画像の移動方向を任意の方向とした場合について説明する図。
【図４】移動後の部分画像のハフ変換値をハフ変換値分配処理によって求める方法について説明する図。
【図５】移動差分ハフ変換値を反映させる移動差分ハフ変換値反映処理について説明する図。
【図６】発明の実施形態に係る画像処理装置の構成を示す図。
【図７】図１に示した実施形態１に係る画像処理装置の動作手順を説明するフローチャート。
【図８】図１のハフ変換値分配処理部１６０が行うハフ変換値分配処理の処理手順を説明するフローチャート。
【図９】図１の移動差分ハフ変換値反映処理部１８０が行う移動差分ハフ変換値反映処理の処理手順を説明するフローチャート。
【図１０】ハフ変換について説明する図。
【図１１】ハフ変換について説明する図。
【図１２】ハフ変換された（ｒ，θ）座標から（Ｘ．Ｙ）座標への変換を説明する図。
【図１３】全体画像の中から部分画像を選択し、選択した部分画像を順次ずらしながらハフ変換を行う例を示す図。
【符号の説明】
【００６５】
１００・・・画像処理装置、１１０・・・画像データ入力部、１２０・・・部分画像選
択部、１３０・・・移動方向及び移動量設定部、１４０・・・ハフ変換初期値設定部、１
５０・・・ハフ変換値記憶部、１６０・・・ハフ変換値分配処理部、１７０・・・移動差
分ハフ変換値算出部、１８０・・・移動差分ハフ変換値反映処理部、Ｇ１・・・部分画像
、Ｇ１’・・・移動後の部分画像、Ｌ１，Ｌ２，Ｌ３・・・直線
【図１】
2009104510.tif 000003
【図３】
2009104510.tif 000004
【図４】
2009104510.tif 000005
【図６】
2009104510.tif 000006
【図７】
2009104510.tif 000007
【図８】
2009104510.tif 000008
【図９】
2009104510.tif 000009
【図２】
2009104510.tif 000010
【図５】
2009104510.tif 000011
【図１０】
2009104510.tif 000012
【図１１】
2009104510.tif 000013
【図１２】
2009104510.tif 000014
【図１３】
2009104510.tif 000015