Transformacja Hougha

Transformacja Hougha (ang. Hough transform) jest techniką przetwarzania obrazu służącą do wykrywania geometrycznych struktur, najczęściej prostych i okręgów, w dwuwymiarowych obrazach cyfrowych. Metoda polega na przekształceniu punktów przestrzeni obrazu do przestrzeni parametrów, w której kształt poszukiwanej figury jest reprezentowany jako punkt (lub krzywa) o wysokiej koncentracji.

Historia

Metodę opracował w 1962 roku amerykański inżynier Richard D. Hough, początkowo w celu wykrywania prostych w danych radarowych. Od tego czasu technika została rozszerzona o wykrywanie innych krzywych oraz zaadaptowana do licznych dziedzin, takich jak robotyka, analiza medyczna czy zarządzanie ruchem drogowym.

Podstawy matematyczne

Najprostsza wersja – transformacja Hougha dla linii – opiera się na równaniu prostej w postaci biegunowej:

r = x·cosθ + y·sinθ

gdzie (x, y) to współrzędne punktu w obrazie, r to odległość prostej od początku układu współrzędnych, a θ to kąt między wektorem normalnym a osią x. Dla każdego punktu (x, y) wyznacza się krzywą w dwuwymiarowej przestrzeni (r, θ). Punkty należące do tej samej linii w obrazie generują krzywe, które przecinają się w jednym wspólnym punkcie parametrycznym – wskazującą na współrzędne prostej w obrazie.

W przypadku wykrywania okręgów wykorzystuje się równanie:

(x‑a)² + (y‑b)² = R²

gdzie (a, b) to środek okręgu, a R jego promień. Każdy punkt obrazu głosuje w trójwymiarowej przestrzeni parametrów (a, b, R).

Algorytm

1. Przygotowanie obrazu – najczęściej stosuje się filtrację i detekcję krawędzi (np. metodę Canny'ego), aby zredukować liczbę punktów.
2. Inicjalizacja akumulatora – tworzy się wielowymiarową tablicę (akumulator) odpowiadającą dyskretyzowanej przestrzeni parametrów.
3. Głosowanie – dla każdego punktu krawędzi oblicza się wszystkie możliwe kombinacje parametrów (np. zakres θ od 0° do 180° z krokiem Δθ) i zwiększa odpowiednie komórki akumulatora.
4. Wykrywanie maksimów – po zakończeniu głosowania szuka się lokalnych maksimów w akumulatorze, które przekraczają ustalony próg.
5. Rekonstrukcja elementów – z wartości parametrów odczytanych z maksimów odtwarza się odpowiednie linie lub okręgi w obrazie źródłowym.

Rodzaje transformacji Hougha

• Transformacja Hougha dla linii – najczęściej stosowana, działa w przestrzeni 2‑D (r, θ).
• Transformacja Hougha dla okręgów – wymaga przestrzeni 3‑D (a, b, R).
• Transformacja Hougha dla elips – rozszerzenie do 5‑D przestrzeni parametrów.
• Transformacja Hougha adaptacyjna – dynamiczne dopasowanie rozdzielczości akumulatora w zależności od lokalnej gęstości krawędzi.

Zastosowania

Transformacja Hougha znajduje zastosowanie w wielu dziedzinach:

• Systemy wizyjne – wykrywanie pasów drogowych, linii tramwajowych, znaków.
• Medicina – identyfikacja struktur anatomicznych w tomografii komputerowej i rezonansie magnetycznym.
• Robotyka – nawigacja autonomiczna przy pomocy detekcji linii i zakrętów.
• Geologia – analiza rysów strukturalnych w zdjęciach lotniczych.
• Rozpoznawanie znaków – ekstrakcja konturów liter i cyfr w systemach OCR.

Zalety i ograniczenia

Zalety	Ograniczenia
Odporność na przerwy w linii – pojedyncze przerwy nie zakłócają wykrywania. Możliwość wykrywania kształtów o znanej postaci niezależnie od ich położenia i orientacji. Relatywnie prosty do implementacji algorytm.	Wysokie zapotrzebowanie na pamięć i moc obliczeniową przy dużej rozdzielczości akumulatora. Wrażliwość na szum – fałszywe krawędzie mogą generować niepożądane maksy. Trudności w wykrywaniu bardzo zakrzywionych lub nieregularnych kształtów.

Implementacje i biblioteki

Współczesne środowiska programistyczne udostępniają gotowe funkcje implementujące transformację Hougha, m.in.:

• OpenCV – funkcje HoughLines, HoughLinesP (wersja probabilistyczna) oraz HoughCircles.
• scikit-image – moduł transform.hough_line i transform.hough_circle.
• Biblioteka MATLAB – funkcje hough, houghpeaks, houghlines.

Przykładowy kod (Python + OpenCV)

import cv2
import numpy as np

# wczytanie obrazu i konwersja na skalę szarości
img = cv2.imread('sciezka/do/obrazu.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# detekcja krawędzi metodą Canny'ego
edges = cv2.Canny(gray, 50, 150, apertureSize=3)

# transformacja Hougha dla linii
lines = cv2.HoughLines(edges, rho=1, theta=np.pi/180, threshold=120)

# rysowanie wykrytych linii
for rho, theta in lines[:,0]:
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a * rho
    y0 = b * rho
    pt1 = (int(x0 + 1000*(-b)), int(y0 + 1000*(a)))
    pt2 = (int(x0 - 1000*(-b)), int(y0 - 1000*(a)))
    cv2.line(img, pt1, pt2, (0,0,255), 2)

cv2.imshow('Wykryte linie', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

Perspektywy rozwoju

Obecne badania koncentrują się na integracji transformacji Hougha z metodami uczenia głębokiego, co umożliwia dynamiczne dostosowywanie parametrów akumulatora oraz redukcję szumu. Inne kierunki to przyspieszenie obliczeń na GPU oraz opracowanie wersji probabilistycznych o jeszcze niższym koszcie obliczeniowym.

Transformacja Hougha pozostaje jednym z fundamentów klasycznej analizy obrazu, a jej prostota i wszechstronność sprawiają, że jest nieodłącznym elementem wielu nowoczesnych systemów wizyjnych.