Vandaag leren we hoe we lijnen en cirkels in een afbeelding kunnen detecteren met behulp van een techniek die Hough transform heet.

Wat is de Hough ruimte?

Voordat we de Hough transformatie gaan toepassen op afbeeldingen, moeten we begrijpen wat een Hough ruimte is, en dat zullen we leren aan de hand van een voorbeeld.

Parameterruimte

Wanneer we met afbeeldingen werken, kunnen we ons voorstellen dat de afbeelding een 2d matrix is over enkele x en y coördinaten, waaronder een lijn zou kunnen worden beschreven als y = mx + b

Maar in de parameterruimte, die we Hough-ruimte zullen noemen, kan ik diezelfde lijn in plaats daarvan voorstellen als m vs b, zodat de karakterisering van een lijn in de beeldruimte, een enkel punt zal zijn op de positie m-b in de Hough-ruimte.

Maar we hebben een probleem, met y = mx + b, we kunnen geen verticale lijn weergeven, want de helling is oneindig. We hebben dus een betere parametrisering nodig, polaire coördinaten (rho en theta).

Hough-ruimte

• rho: beschrijft de afstand van de lijn tot de oorsprong
• theta: beschrijft de hoek verwijderd van horizontaal

Een zeer belangrijke observatie is echter wat er gebeurt als we meerdere punten rond een lijn nemen, en we transformeren in onze Hough-ruimte.

Een enkel punt op de beeldruimte vertaalt zich naar een kromme op de Hough-ruimte, met de bijzonderheid dat punten onder een lijn op de beeldruimte zullen worden voorgesteld door meerdere krommen met een enkel raakpunt.

En dit zal ons doel zijn, het vinden van de punten waar een groep krommen elkaar snijdt.

Wat is Hough transform?

Hough transform is een kenmerk-extractiemethode voor het detecteren van eenvoudige vormen zoals cirkels, lijnen, enz. in een afbeelding.

De “eenvoudige” eigenschap wordt afgeleid door de representatie van de vorm in termen van parameters. Een “eenvoudige” vorm zal slechts door enkele parameters worden voorgesteld, bijvoorbeeld een lijn kan worden voorgesteld door zijn helling en intercept, of een cirkel die kan worden voorgesteld door x, y en radius.

In ons lijnvoorbeeld zal een Hough-transformatie verantwoordelijk zijn voor het verwerken van de punten op de afbeelding en het berekenen van de waarden in de Hough-ruimte.

Het algoritme voor het laten plaatsvinden van de transformatie en vervolgens het vinden van de kruisende curven is een beetje ingewikkeld, en valt dus buiten het bestek van deze post. We zullen echter een blik werpen op een implementatie van dit algoritme, dat deel uitmaakt van de OpenCV bibliotheek.

Lijnen detecteren met OpenCV

In OpenCV is lijndetectie met behulp van Hough Transform geïmplementeerd in de functies HoughLines en HoughLinesP (Probabilistic Hough Transform). We zullen ons concentreren op de laatste.

De functie verwacht de volgende parameters:

• image: 8-bit, enkel-kanaals binair bronbeeld. De afbeelding kan door de functie worden gewijzigd.
• lines: Uitvoervector van lijnen. Elke lijn wordt voorgesteld door een vector van 4 elementen (x_1, y_1, x_2, y_2) , waarbij (x_1,y_1) en (x_2, y_2) de eindpunten zijn van elk gedetecteerd lijnsegment.
• rho: Afstandresolutie van de accumulator in pixels.
• theta: Hoekresolutie van de accumulator in radialen.
• threshold: Accumulator drempel parameter. Alleen de lijnen die genoeg stemmen krijgen worden teruggegeven.
• minLineLength: Minimale lijnlengte. Lijnsegmenten korter dan dat worden verworpen.
• maxLineGap: Maximum toegestane afstand tussen punten op dezelfde lijn om ze te verbinden.

Te ingewikkeld? het is makkelijker met een voorbeeld:

# Read image img = cv2.imread('lanes.jpg', cv2.IMREAD_COLOR)# Convert the image to gray-scalegray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)# Find the edges in the image using canny detectoredges = cv2.Canny(gray, 50, 200)# Detect points that form a linelines = cv2.HoughLinesP(edges, 1, np.pi/180, max_slider, minLineLength=10, maxLineGap=250)# Draw lines on the imagefor line in lines: x1, y1, x2, y2 = line cv2.line(img, (x1, y1), (x2, y2), (255, 0, 0), 3)# Show resultcv2.imshow("Result Image", img)

En hier is het resultaat:

Het is heel belangrijk dat we daadwerkelijk een beeld gebruiken dat alleen uit randen bestaat als parameter voor de Hough Transform, anders werkt het algoritme niet zoals het bedoeld is.

Cirkels detecteren met OpenCV

Het proces gaat ongeveer hetzelfde als bij lijnen, met de uitzondering dat we deze keer een andere functie uit de OpenCV bibliotheek gebruiken. We gebruiken nu HoughCircles, die de volgende parameters accepteert:

• image: 8-bit, één-kanaals, grijstinten invoerafbeelding.
• circles: Uitgaande vector van gevonden cirkels. Elke vector is gecodeerd als een 3-element floating-point vector (x, y, radius).
• circle_storage: In C-functie is dit een geheugenopslag die de uitvoerreeks van gevonden cirkels zal bevatten.
• method: Te gebruiken opsporingsmethode. Momenteel is de enige geïmplementeerde methode CV_HOUGH_GRADIENT , die in principe 21HT
• dp: Inverse verhouding van de accumulatorresolutie tot de beeldresolutie. Bijvoorbeeld, als dp=1 , heeft de accumulator dezelfde resolutie als het invoerbeeld. Als dp=2 , heeft de accumulator een half zo grote breedte en hoogte.
• minDist: Minimum afstand tussen de middelpunten van de gedetecteerde cirkels. Als de parameter te klein is, kunnen meerdere naburige cirkels ten onrechte worden gedetecteerd naast een echte. Als hij te groot is, kunnen sommige cirkels worden gemist.
• param1: Eerste methode-specifieke parameter. In het geval van CV_HOUGH_GRADIENT is dit de hoogste drempelwaarde van de twee die aan de Canny() randdetector worden doorgegeven (de laagste is twee keer kleiner).
• param2: Tweede methode-specifieke parameter. In het geval van CV_HOUGH_GRADIENT , is het de accumulatiedrempel voor de cirkel middelpunten in de detectie fase. Hoe kleiner deze is, hoe meer valse cirkels kunnen worden gedetecteerd. Cirkels, die overeenkomen met de grotere accumulatorwaarden, worden het eerst teruggezonden.
• minRadius: Minimum cirkel radius.
• maxRadius: Maximum cirkel radius.

Bedenk dat de parameters verschillend moeten zijn, omdat we een cirkel niet kunnen beschrijven met dezelfde parametrisatie die we voor lijnen hebben gebruikt, en we in plaats daarvan een vergelijking als (x - x0)^^2 + (y - y0)^^2 = r^^2 moeten gebruiken.

En nu naar de code:

# Read image as gray-scaleimg = cv2.imread('circles.png', cv2.IMREAD_COLOR)# Convert to gray-scalegray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)# Blur the image to reduce noiseimg_blur = cv2.medianBlur(gray, 5)# Apply hough transform on the imagecircles = cv2.HoughCircles(img_blur, cv2.HOUGH_GRADIENT, 1, img.shape/64, param1=200, param2=10, minRadius=5, maxRadius=30)# Draw detected circlesif circles is not None: circles = np.uint16(np.around(circles)) for i in circles: # Draw outer circle cv2.circle(img, (i, i), i, (0, 255, 0), 2) # Draw inner circle cv2.circle(img, (i, i), 2, (0, 0, 255), 3)

Merk op dat in vergelijking met het vorige voorbeeld, we hier geen enkele randdetectiefunctie toepassen. Dit komt omdat de functie HoughCircles ingebouwde canny-detectie heeft.

En het resultaat:

Conclusion

Hough Transform is een uitstekende techniek voor het detecteren van eenvoudige vormen in afbeeldingen en heeft verschillende toepassingen, variërend van medische toepassingen zoals röntgen-, CT- en MRI-analyse, tot zelfrijdende auto’s. Als je meer wilt weten over de Hough ruimte, raad ik je aan om de code daadwerkelijk uit te voeren, zelf verschillende configuraties uit te proberen, en de OpenCV documentatie te bekijken voor aanvullende informatie.

Dank voor het lezen!