Hough変換の概要

Hough変換の原理とその応用

Hough変換の基本原理

Hough変換の基本原理は、P.V.C.Houghが米国のPatentで1962年に提唱した⁽¹⁾。この中では、次のようにHough変換の原理が導入された。

x-y座標のある点(x₀, y₀)を通過する直線群は、傾きa、切片bをパラメータとして

y₀=a·x₀ + b    (1)

で表せられる。これは、a-bパラメータ空間では、

b = -a·x₀ + y₀     (2)

となり、可能な全てのa, bの組み、(a, b)の描く軌跡は1本の直線となる。したがって、x-y座標上の点(x_i, y_i)i=1,2,,,Nは、a-bパラメータ平面では、N本の直線で表される。ここで、図1(a)に示すように、(x_i, y_i)i = 1,2,,,Nが1本の直線上に乗っている場合、即ち、y =a₀·x+b₀上にある場合、図1(b)に示すように、a-bパラメータ平面では、これらのN本の直線は、(a₀, b₀)の1点で交差する。この性質を利用することにより、x-yパラメータ平面上で最も多くの点を通過する直線を求めるためには、a-bパラメータ平面上で最も多く直線が交差している点を見つければよい。

その後、Rosenfeldが著書⁽²⁾の中で、このパラメータ平面を二次元配列に対応させ、画像中の直線要素を抽出する具体的な方法として詳しく紹介した。これを契機にして、画像中より直線要素を抽出するこの手法が一般的にHough変換と呼ばれるようになり、画像処理基本手法の一つとして定着した。

ところでx-y座標系の直線は、傾きと切片だけで表現するのが唯一の方法ではなく、

    (3)

のように極座標表現することもできる(このような三角関数の合成関数をHough曲線と、しばしば呼ぶ)。これは、図2に示すように一つの直線を垂角θ-距離ρパラメータで表現したものである。

式(1)は

    (4)

に容易に変形でき、これは、傾き-1/tanθ、切片ρ/sinθとなり、数学的に式(1)と等価である。ところで、図3に示すように、式(1)を変換式とした場合、垂角θ→0になると、切片b→±∞になり、また、垂角θ→π/2となると、傾きa→±∞となる。従って、パラメータ空間を表現するために確保するな二次元配列は無限大のサイズが必要となる。この意味から、このようなa-bパラメータ表現法は禁止的である。Duda & Hartはこのことを指摘し、以後、Hough変換では一般に、このθ-ρパラメータ表現を用いるようになった。

典型的なHough変換の直線検出原理

Hough変換による直線検出の原理は、図4に示すように、パターン平面上にあるN個のエッジ点列(x_i, y_i) : i = 1, 2,,,Nに対して、

    (5)

なる変換関数により、θの関数ρを定め、用意したθ-ρパラメータの二次元配列(K×L)にその軌跡を累積する。ここで描かれる曲線は、式(6)のように合成され、

,     (6)

振幅と位相がエッジ点毎に決まる正弦曲線(Hough曲線)となる。N個のエッジ点列全てにこの操作を適用した後、この累積度数分布から極大点群を抽出すれば、その極大点群が対応するx-yパターン平面上の直線群となる。これは、θ-ρパラメータ平面上の一点が、x-yパターン平面上の直線一本に対応しているという原理に基づく。

ここで、以上の直線検出原理の中で用いたHough変換の基本的な性質についてまとめておく。

性質1 : (x, y)を通過する全ての直線群は、パラメータ平面上の一本のHough曲線で表される。図5にこれを示す。

性質2 : パラメータ平面上の一点は、直線一本に対応する。これを図6に示す。

性質3 : 共線上の任意の二点のHough曲線は、パラメータ平面上の(0≦θ<πの区間)でただ一回だけ交差する。これを図7に示す。

性質4 : x-y平面の等間隔な平行直線群は、パラメータ空間でρ軸に平行な等間隔なピーク群として現れる。角度方向に対しても、円接線群はθ軸に平行な等間隔なピーク群として現れる。これを図8に示す。このように、パラメータ空間をθ、ρとも、等間隔に分割すると、この意味で均一な分解能の直線検出感度が得られる。

Hough変換の問題点Hough変換による直線検出は、

1. 画像中の雑音に影響されることなく安定的に直線を検出できる。
2. 隠ぺいや画像処理の不完全性によって直線が不完全になっていても検出できる。
3. 複数の直線を同時に検出できる。

などの有益な特徴があるが、以下に示すような問題点も数多く存在する。

1. パラメータ空間を表すための大きなメモリが必要となる。
2. パラメータ空間をデジタル化する際のサンプリング間隔（解像度）を決める基準が明確でない。
3. 画像中の各エッジ点ごとに一本のHough曲線を描くため計算量が多くなる。
4. Hough曲線の集積点（ピーク）を抽出する方法が明確でない。
5. 直線検出後、その直線の中から必要な線分（セグメント）を抽出する方法が明確でない。

これらの1, 2, 3のような問題について、RVHT⁽¹²⁾、FIHT⁽¹³⁾、CHT⁽¹⁴⁾のような高速化、効率化、高精度化アルゴリズムも数多く開発されている。しかし、これらの効率化アルゴリズムは、通常のHough変換による直線検出全体のプロセスに手を加え改良したものが多い。それゆえ、これらのアルゴリズム中には高速化を追求するあまり精度を犠牲にするというように、特定条件に特化したものや、拡張性に乏しいものなどもある。それに対し、以下で述べる拡張Hough変換⁽⁸⁾⁽⁹⁾は、変換アルゴリズム自体を改良するスタンスに立つものではなく、パラメータ平面を再構築することにより、所望の変換関数を設計し、上のような問題解決を行うことができる。言い換えれば、拡張Hough変換は、どのように変換関数を設計すべきかという変換関数設計法の一方針である。この設計方針にしたがって変換関数を設計することにより、効率化、特に高精度化について、所望の変換関数を得ることができる。