15 ホフ変換
チャプター 14 の探索線法には自明の前提がある：目標がおおよそどこにあるかをあらかじめ知っていることである。まずROIを指定し、次に探索線を配置する——この一連のパイプラインは「1つのROIにつき1つの幾何プリミティブ」という事前知識に基づいている。しかし、この前提が成立しない場合はどうなるだろうか？画像内に複数の直線や複数の円があり、それぞれがどこにあるか事前にはわからない状況である。さらに目標が途切れていたり（破線、反射による切れ目）、部分的に隠れていたりすることもある。この場合、探索線を配置する場所がなくなり、点ごとの追跡も最初の切れ目で途切れてしまう。ホフ変換（Hough transform）は問いの立て方を変える：「この直線はどこにあるか」を問うのではなく、すべてのエッジ点が、自身を通るすべての可能性のある直線に投票（voting）することで、最も多くの票を集めたパラメータの組み合わせが自然に選ばれるのである。本章では、480×360の合成シーン（図 15.1）を用いて、この投票機構を全体的に実行する。このシーンには3本の直線——そのうち1本は欠落率約47%の破線——と2つの円——そのうち1つは40%が隠れている——に加え、40個の散在する斑点とσ=8のガウシアンノイズが含まれている。途切れ、隠れ、雑点、ノイズの4種類の妨害がすべて揃っており、ホフ変換の真価を引き出すのにちょうどよい。
15.1 パラメータ空間と投票
直線に投票するには、まず直線に適切なパラメータの組を与える必要がある。ホフ変換は法線式（normal form）によるパラメータ化を採用している(Duda と Hart 1972)：
\[ \rho = x\cos\theta + y\sin\theta, \]
ここで\(\theta\in[0^\circ,180^\circ)\)は直線の法線方向と\(x\)軸のなす角、\(\rho\)は原点から直線までの符号付き距離である。\((\rho,\theta)\)の組は1本の直線を一意に定め、両方のパラメータには上限・下限がある：\(|\rho|\)は画像の対角線長を超えず、\(\theta\)は半周分だけでよい。
なぜより馴染みのある斜截式\(y=kx+b\)を使わないのだろうか？鉛直線は傾き\(k\to\infty\)となるため、パラメータ空間（parameter space）が\(k\)方向に上限を持たず、有限の格子に離散化できない。さらに、\(k\)を等間隔に分割すると、対応する直線の方向が極端に不均一になる（\(k\)が0から1までで45°を掃引するのに対し、10から11まででは約0.5°しか掃引しない）。法線式は両方のパラメータに上限・下限があり、方向に対して均一であるため、投票専用に設計されたパラメータ化といえる。
法線式は美しい双対関係をもたらす。画像空間内の1点\((x_0,y_0)\)を上式に代入し、\(\theta\)を\([0^\circ,180^\circ)\)の範囲で動かすと、得られる\(\rho(\theta)=x_0\cos\theta+y_0\sin\theta\)はパラメータ空間内の1本の正弦曲線となる——これはその点を通るすべての直線を列挙したものである。逆に、一群の点が\((\rho^*,\theta^*)\)で共線であれば、それぞれの正弦曲線はパラメータ空間内の同一点\((\rho^*,\theta^*)\)をすべて通る。したがって、直線の検出は正弦曲線族の共通の交点を見つけることに帰着する。
工学的な実装はアキュムレータ（accumulator）である：\((\theta,\rho)\)平面を格子（例えば1°×1 px）に離散化し、0で初期化する。各エッジ点について、\(\theta\)を掃引して対応する\(\rho\)を計算し、該当する格子に1票を加える。すべての点の投票が終わった後、アキュムレータ内のピーク（peak）が画像内の直線となる——票数はその直線上にあるエッジ点の数である。大域的な幾何学的検出問題が、配列のピーク探索に単純化されるのである。
エッジ点はどこから得るのだろうか？任意のエッジ検出器でよい（系統的な解説は チャプター 13 を参照）——本章では 図 15.1 に対してSobel勾配振幅の閾値処理を行い（閾値200、σ=8のノイズレベルの約7σに相当し、チャプター 7 の考え方に従って閾値をノイズより高く設定することで、虚警はほぼない）、6677個のエッジ点を得た（図 15.2）。破線の切れ目と円の欠けた円弧がエッジ図にそのまま残っていることに注意されたい——次の投票でこれらに真正面から取り組むことになる。
15.2 アキュムレータの読み取り
SDKを呼び出す前に、手作業で180×1201のアキュムレータを作成し（\(\theta\)方向は1°/セル、\(\rho\)方向は1 px/セル、\(|\rho|\le 600\)）、6677個の点に1つずつ投票させる。結果を 図 15.3 に示す：横軸が\(\theta\)、縦軸が\(\rho\)で、グレースケール値は平方根で伸張されている。図には2層の構造が見える：下半分を埋め尽くす正弦曲線族——淡く明るい各曲線が1つ（または1クラスタ）のエッジ点の投票軌跡である——と、曲線族の中にある3つの明らかにより明るい交点——3本の直線のピークである。40個の散在する斑点の票はそれぞれの正弦曲線上に散らばり、共通の交点を持たないため、どこにもピークを形成しない。
ピークは本来あるべき位置にあるだろうか？3本の線分の真値の端点から、それぞれの\((\rho,\theta)\)を予測できる。アキュムレータから3つの最大ピークを抽出し（大域最大値＋近傍抑制、5×5の加重重心を用いてサブセル精度に精緻化）、SDKのFindHoughLinesによる検出結果と比較した：
| 直線 | 予測 \((\rho,\theta)\) | アキュムレータピーク \((\rho,\theta,\text{票数})\) | SDK 検出 \((\rho,\theta)\) |
|---|---|---|---|
| L1（実線） | (119.79, 15.00°) | (120.77, 15.30°, 291 票) | (121.04, 15.01°) |
| L2（破線、47%欠落） | (9.15, 104.25°) | (9.11, 104.25°, 190 票) | (9.22, 104.01°) |
| L3（実線） | (378.55, 47.60°) | (377.31, 48.05°, 260 票) | (379.19, 48.02°) |
3本すべての直線が検証をパスした：\(\theta\)の偏差は0.5度以内、\(\rho\)の偏差は1.3 px以内である。この1.3 pxは不可解な誤差の下限ではなく、明確な原因がある：シーン内の線の太さは約2.8 pxであり、Sobelは線の両側にそれぞれエッジ点の列を検出する。この2列の点はそれぞれ共線で約2.8 px離れており、投票後のピークは2列の票の妥協点となるため、位置は両側の間を変動する——アキュムレータのピークは常にエッジ点の幾何に忠実であり、エッジ点の幾何は線の太さによって決まるのである。
表の中で最も注目に値するのはL2である：破線は線の47%が欠落しており、票数は実線の約290から190に減少しているが、ピークの位置は全く動かず、依然として明瞭に識別できる。これがホフ変換の真髄——途切れに対する耐性である。投票は「この点はこの直線上にあるか」だけを問い、「隣の点とつながっているか」は問わない：切れ目は単に票数を比例的に減らすだけで、ピークを移動させることも消滅させることもない。これに対し、局所的な連続性に依存する手法（エッジ追跡、輪郭連結）は、最初の14 pxの切れ目で途切れてしまう。大域的な証拠の蓄積と局所的な連続性追跡は2つの世界観であり；目標が本質的に途切れている場合、前者だけが有効なのである。
15.3 複数インスタンスと頑健性
投票を使わず、「直線を探す」を最も馴染みのある最小二乗法に任せたらどうなるだろうか？逆実験を行う：6677個すべてのエッジ点に対して全体で1本の総最小二乗直線を当てはめると、結果は\(\rho=180.04\)、\(\theta=93.76°\)、全点のRMS距離は82.6 pxとなった——図 15.4 の画像を横切る白線であり、L1、L2、L3のいずれとも一致しない。これは実装のミスではなく、問いの立て方自体が間違っているのである：最小二乗法はすべての点が同一のモデルに従うことを仮定しているのに対し、ここの点は3本の直線、2つの円、40個の雑点に属している。「すべての点に対する最適な1本の直線」は存在しない対象に対する妥協であり、すべての構造の重心付近に位置し、ばらつきの最大の主軸に沿った方向を向く——誰でもない「平均的な線」に過ぎないのである。
ホフ変換はこのジレンマを本質的に持たない：各インスタンスがアキュムレータ内で自身のピークを形成し、互いに干渉しない——L1の291票、L2の190票、L3の260票はそれぞれ自身の位置に存在する；どの直線にも属さない円弧の点と雑点の票は至る所に散らばり、ピークを形成することはない。複数インスタンスの分離と雑点に対する頑健性は同一のメカニズムの両面である：票が集中したものが勝ち、散らばったものが負けるのである。図 15.5 はSDKのFindHoughLinesによる検出結果である：破線を含む3本の直線がすべて検出されている（白線）。
FindHoughLinesによって検出された3本の直線（白線、無限直線を画像の境界で切り取り）。破線L2は47%の欠落の下でも通常通り検出され；円と雑点から虚警は発生しなかった。
ホフ変換と チャプター 14 の頑健な当てはめ（Huber、RANSAC）はどのように使い分けるべきだろうか？頑健な当てはめは「1つのインスタンス＋少数の外れ値」を扱い、前提としてROIで目標をおおよそ囲んでいる必要があり、サブピクセル精度が得られるという利点がある；RANSACは「1つ見つけて、そのインライア点を除去し、次を探す」という方法で複数インスタンスを扱えるが、インスタンスの数が多くなると効率が悪くなる。ホフ変換は「数不明のインスタンス＋多数の無関係な構造」を扱い、位置の事前知識を一切必要としないが、精度はアキュムレータの量子化によって制限されるという代償がある。経験則として：ROIがあり精度が必要な場合は——探索線＋頑健な当てはめ；事前知識がなくすべてを見つける必要がある場合は——ホフ変換、である。
15.4 ハフ円
円は3つのパラメータ \((c_x,c_y,r)\) を持つため、アキュムレータは2次元から3次元に拡張される。エッジ点の投票軌跡は正弦曲線ではなく、パラメータ空間内の円錐面となる（候補中心が点から遠いほど、必要な半径は大きくなる）。直接実装した場合、メモリ消費と投票計算のコストは直線の場合より1桁大きくなるため、実用的なアルゴリズムはほぼ例外なく勾配方向を用いて高速化する。エッジ点の勾配方向は円の中心を向く（あるいは背く）ため、勾配方向の射線に沿って候補中心に投票するだけでよく、3次元の問題は「2次元の中心投票 + 1次元の半径ヒストグラム」の2段階に縮退される。これがOpenCVや多くの産業用ライブラリを含む主流の実装が採用する2-1ハフ戦略である。
規模感の目安：480×360の画像、半径探索範囲40 pxの場合、単純な3次元アキュムレータは480×360×40 ≈ 690万個のセルを持ち、すべてのエッジ点は各半径層で1周分の投票を行う必要がある。勾配方向による高速化後は、各点は1本の射線に沿って数十票を投じるだけで済む。この処理がなければ、ハフ円は生産ラインのタクト内で実行できない。
実験は同じシーンで継続する（図 15.6）。FindHoughCircles はちょうど2つの円を検出した。完全な円C1の真値は \((150,230,50)\)、検出値は \((151.0,231.0,50.2)\) であり、中心誤差は1.41 px、半径誤差は0.20 pxであった。円弧の40%が欠落したC2の真値は \((380,270,60)\)、検出値は \((377.0,267.0,57.8)\) であり、中心誤差は4.24 px、半径誤差は2.20 pxであった。これら2組の数値は1つの結論を導く：遮蔽下では精度は低下するが、検出は失敗しない。精度低下の原因は直線のρオフセットと同様であるが、影響はより大きい。円の3つのパラメータは相互に結合しており、欠落した円弧によって投票の重心が残存する円弧側に偏り、ピークはわずかに引きずられる。しかし、残存する60%の円弧がピークを形成するのに十分な票を寄与するため、これは円における断絶耐性の再現である。
FindHoughCirclesによる検出結果（白い円と十字が検出された円と中心）。完全な円C1の誤差は1.41/0.20 pxであり、40%の円弧が欠落したC2の誤差は4.24/2.20 pxである。遮蔽下で精度は低下するが検出は失敗しない。
精度の本質的な上限も明確に把握しておく必要がある。実測によると、このSDKの円中心は2 pxの格子に量子化され、半径は約0.2 px刻みである。これはアキュムレータのセルサイズの直接的な反映であり、いくら票を集めてもセルサイズ未満の分解能は得られない。そのため、産業分野での標準的な手順は2段階である：ハフによる粗位置出し、サーチラインによる精測。まずハフを用いて画像全体からすべての円を検出し（事前情報不要、遮蔽に耐性あり）、検出された中心と半径を事前情報として環状ROIを作成し、チャプター 14 の放射状サーチライン + ロバストフィッティングに渡してサブピクセル精度の精測を行う。ハフは「どこにあるか」を担当し、サーチラインは「どれだけ正確か」を担当する。両章の手法は競合関係ではなく、パイプラインの上流と下流の関係にある。
15.5 SciVision実装
ハフ直線はSCIMV::SciSvHoughLinesから提供され、内部でCannyエッジ抽出を行い、グレースケール画像を直接入力とする。
SCIMV::SciSvHoughLines houghL;
SciPointArray term;
SciVarArray lineAng, lineLen;
long rc = houghL.FindHoughLines(src, fullROI, /*cannyLow*/ 60, /*cannyHigh*/ 120,
/*accumThreshold*/ 65, /*minAngle*/ -90, /*maxAngle*/ 90,
/*AngleGap*/ 5, /*DistGap*/ 10, /*maxNum*/ 6, /*AngleCheck 範囲内*/ false,
&term, &lineAng, &lineLen);cannyLow/cannyHighは内部のCannyの2つの閾値である。accumThreshold=65は票数の閾値であり、65票未満のピークは報告されない。minAngle/maxAngleは受け入れる直線の角度範囲を限定する。AngleGap=5、DistGap=10はピークの重複除去のための近傍領域を定義し（角度差<5°かつ距離差<10 pxのピークは1本の直線に統合される）、maxNum=6は返される直線の最大数を制限する。本例では6本の返却を許可したところ、ちょうど3本の真値直線のみが検出され、このパラメータでは虚警が発生しないことが確認された。
実測では、このAPIに直感（またはドキュメント）とは異なる、正直に記録しておくべき3つの挙動が見られた。1つ目は、ヘッダーファイルにAngleCheckの値の意味が明記されていないことである。実測によると、falseが「角度範囲内の直線を探す」であり、trueが範囲外の直線を探すである。trueを全範囲[-90,90]と組み合わせて渡すと、「適切な直線が見つからない」というエラーコード122408001が直接返される。2つ目は、デフォルトのCanny閾値20/40が本シーンでは機能しないことである。σ=8のノイズ下では虚警のエッジ点が多すぎ、真の直線の票がノイズの票に埋もれ、アキュムレータ内に画像全体を貫く幻影の対角線が出現する。閾値を60/120に上げて初めて結果が安定した。これは@sec-ht-voting の手動エッジ画像で7σの閾値を用いたのと同じ理屈で、Cannyの閾値はノイズレベルより上に設定する必要がある。3つ目は、戻り値のセマンティクスである。term内の「端点」は線分の端点ではなく、無限直線と画像境界との交点であり（図 15.5 の白い線がすべて画像を貫いているのはこのためである）、lineLenthはクリップ後の長さである。また、lineAngに返される角度は \(90^\circ-\theta\)（法線角ではなく直線の方向角）であるため、換算時に逆にしないよう注意する必要がある。
ハフ円はSCIMV::SciSvHoughCirclesから提供される。
SCIMV::SciSvHoughCircles houghC;
SciPointArray centers;
SciVarArray radii;
rc = houghC.FindHoughCircles(src, fullROI, /*minDist*/ 100, /*edgeThreshold*/ 160,
/*accumThreshold*/ 65, /*minRadius*/ 35, /*maxRadius*/ 75, /*maxNum*/ 4,
¢ers, &radii);minDist=100は2つの円の中心間の最小間隔（重複除去用）である。edgeThresholdは内部のエッジ抽出の強度閾値である。accumThreshold=65は中心アキュムレータの票数閾値である。minRadius/maxRadiusは半径探索帯35～75 pxを規定する。ここにも落とし穴がある：デフォルトのedgeThreshold=80は低すぎるため、ノイズのエッジが半径がmaxRadiusに張り付いた幻影円として集まってしまう（大きな半径の円は円周が長く、通過するノイズ点が多いため、本来的に票数で有利になる）。これを160に上げ、accumThreshold=65と組み合わせることで、maxNum=4を許可しても2つの真値円のみが検出されるようになった。最後に出力の量子化粒度について再度注意する：中心は2 pxの格子に載り、半径は約0.2 px刻みである。結果を受け取った時点で「粗位置出し」であることを認識し、精測は下流の処理に委ねるべきである。本章のすべての画像と数値を生成する完全なプロジェクトはcode/hough_transform/にある。
産業事例：トレイ上のピンカウント
あるICトレイの検査ステーションでは、各ポケット内のチップのピン数を計数する必要がある。リング照明下で金属ピンは反射し、途切れ途切れの短い輝線の集合として撮像される。各ピンは2～3つのセグメントに分断され、本数はチップのモデルによって異なる。テンプレートマッチングは適用できず（ピン数が不定で、外観が反射によって変化する）、サーチラインもROIを設定することができない。ハフ直線はまさにこの用途に適している。ピンの方向は既知（チップ本体と垂直）であるため、minAngle/maxAngleをその方向の±10°の角度帯に絞ることで、無関係な方向の反射は最初から排除される。分断された数個の輝線セグメントはアキュムレータ内で同じピークに票を集め、断絶耐性によって「数個のセグメント」が自動的に「1本のピン」に統合される。最後に票数閾値で散発的な反射をフィルタリングし、検出されたピーク数がピン数となる。パラメータ調整の重点は本章の実験とまったく同じである：まず生産ラインの画像のノイズレベルを測定し、内部のCanny閾値をノイズレベルより上に固定する。幻影線が出現した時点で、計数は信頼できなくなる。
15.6 まとめ
- ハフ変換は幾何検出を投票に変える：法線式 \(\rho=x\cos\theta+y\sin\theta\) のもと、画像点はパラメータ空間の正弦曲線に双対され、共線な点の曲線は1点で交わる。離散アキュムレータが投票をカウントし、ピークが直線となる。
- 断絶耐性はハフ変換の核心である：投票は「直線上にあるか否か」だけを見て「連続しているか否か」は見ないため、欠けは票数を減らすだけでピークの位置は移動しない。47%の欠けを持つ破線は190票で通常通りピークを形成し、40%遮蔽された円も通常通り検出された。
- 多インスタンスの分離と雑音に対するロバスト性は同じメカニズムである：各インスタンスは自身のピークを形成し、散在する票はピークを形成できない。対照実験では、6677点に対して単一直線の最小二乗フィッティングを行ったところ、RMS 82.6 pxの「平均直線」が得られた。多インスタンスのデータにおいて、全体で最適な解は無意味な妥協案に過ぎない。
- ハフの精度はアキュムレータの量子化によって上限が定まる（本例では円中心は2 px格子、半径は0.2 px刻み。直線のρ偏差はさらに線の両側からの投票の影響を受ける）。そのため、エンジニアリングの手順は「ハフによる粗位置出し + サーチラインによる精測」であり、チャプター 14 とともに上流-下流の関係を構成する。
- パラメータはノイズに固定し、セマンティクスは実測で検証する：内部のCanny閾値がノイズレベルを下回ると幻影直線/幻影円が発生する。本章のSDKは
AngleCheckのセマンティクスがドキュメントと逆であり、戻りの端点は境界クリップ後の交点であり、角度は \(90^\circ-\theta\) である。重要なセマンティクスは、必ず真値が既知の合成画像で検証してから本番に適用するべきである。
ハフ変換の原典はDudaとHartの古典的な論文(Duda と Hart 1972)である。直線から任意の形状への一般化はBallardの一般化ハフ変換(Ballard 1981)であり、IllingworthとKittlerのサーベイは各種の変形と計算戦略を体系的に整理している(Illingworth と Kittler 1988)。幾何測定パイプラインとの接続については、Stegerらの著作をさらに参照できる(Steger, Ulrich, と Wiedemann 2018)。