I dag vil vi lære at detektere linjer og cirkler i et billede ved hjælp af en teknik, der kaldes Hough-transformation.

Hvad er Hough-rum?

Hvor vi begynder at anvende Hough-transformation på billeder, skal vi forstå, hvad et Hough-rum er, og det vil vi lære ved hjælp af et eksempel.

Parameterrum

Når vi arbejder med billeder, kan vi forestille os, at billedet er en 2d-matrix over nogle x- og y-koordinater, hvorunder en linje kan beskrives som y = mx + b

Men i parameterrum, som vi vil kalde Hough-rummet, kan jeg repræsentere den samme linje som m vs b i stedet, så karakteriseringen af en linje i billedrummet vil være et enkelt punkt på positionen m-b i Hough-rummet.

Men vi har dog et problem, med y = mx + b, vi kan ikke repræsentere en lodret linje, da hældningen er uendelig. Så vi har brug for en bedre måde at parametrisere på, polære koordinater (rho og theta).

Hough space

• rho: beskriver linjens afstand fra oprindelsen
• theta: beskriver vinklen væk fra vandret

En meget vigtig observation er dog, hvad der sker, når vi tager flere punkter rundt om en linje, og vi transformerer til vores Hough space.

Et enkelt punkt i billedrummet oversættes til en kurve i Hough-rummet, med den særlige egenskab, at punkter blandt en linje i billedrummet vil blive repræsenteret ved flere kurver med et enkelt berøringspunkt.

Og dette vil være vores mål, nemlig at finde de punkter, hvor en gruppe af kurver skærer hinanden.

Hvad er Hough-transformation?

Hough-transformation er en metode til udtræk af funktioner til detektering af enkle former som cirkler, linjer osv. i et billede.

Den “enkle” egenskab er afledt af formrepræsentationen i form af parametre. En “simpel” form vil kun være repræsenteret af få parametre, f.eks. kan en linje repræsenteres ved dens hældning og skæringspunkt, eller en cirkel, som kan repræsenteres ved x, y og radius.

I vores linjeeksempel vil en Hough-transformation være ansvarlig for at behandle prikkerne på billedet og beregne værdierne i Hough-rummet.

Algoritmen til at få transformationen til at ske og efterfølgende finde de skærende kurver er lidt kompliceret, og derfor uden for rammerne af dette indlæg. Vi vil dog tage et kig på en implementering af denne algoritme, som er en del af OpenCV-biblioteket.

Detektering af linjer ved hjælp af OpenCV

I OpenCV er linjedetektering ved hjælp af Hough-transformation implementeret i funktionerne HoughLines og HoughLinesP (Probabilistisk Hough-transformation). Vi vil fokusere på sidstnævnte.

Funktionen forventer følgende parametre:

• image: 8-bit, single-channel binært kildebillede. Billedet kan ændres af funktionen.
• lines: Output-vektor af linjer. Hver linje repræsenteres af en 4-elementvektor (x_1, y_1, x_2, y_2) , hvor (x_1, y_1) og (x_2, y_2) er slutpunkterne for hvert detekteret linjesegment.
• rho: Afstandsløsning for akkumulatoren i pixels.
• theta: Vinkelopløsning for akkumulatoren i radianer.
• threshold: Parameter for akkumulatorens tærskelværdi. Der returneres kun de linjer, der får nok stemmer
• minLineLength: Mindste linjelængde. Linjesegmenter, der er kortere end dette, afvises.
• maxLineGap: Maksimal tilladt afstand mellem punkter på samme linje for at forbinde dem.

Tå kompliceret? det er nemmere med et eksempel:

# 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)

Og her er resultatet:

Det er meget vigtigt, at vi rent faktisk kun bruger et billede med en kant som parameter for Hough Transform, ellers vil algoritmen ikke fungere efter hensigten.

Detektering af cirkler ved hjælp af OpenCV

Processen foregår nogenlunde på samme måde som for linjer, bortset fra at vi denne gang vil bruge en anden funktion fra OpenCV-biblioteket. Vi vil nu bruge HoughCircles, som accepterer følgende parametre:

• image: 8-bit, single-channel, grayscale input image.
• circles: Outputvektor af fundne cirkler. Hver vektor er kodet som en 3-element-flydepunktsvektor (x, y, radius).
• circle_storage: I C-funktionen er dette et hukommelseslager, der vil indeholde outputsekvensen af de fundne cirkler.
• method: Detektionsmetode, der skal anvendes. I øjeblikket er den eneste implementerede metode CV_HOUGH_GRADIENT , som grundlæggende er 21HT
• dp: Omvendt forhold mellem akkumulatorens opløsning og billedets opløsning. Hvis dp=1 , har akkumulatoren f.eks. den samme opløsning som indgangsbilledet. Hvis dp=2 , har akkumulatoren halvt så stor bredde og højde.
• minDist: Minimumsafstand mellem centrumene af de detekterede cirkler. Hvis parameteren er for lille, kan flere nabokredse blive fejlagtigt detekteret ud over en sand cirkel. Hvis den er for stor, kan nogle cirkler blive overset.
• param1: Første metodespecifikke parameter. I tilfælde af CV_HOUGH_GRADIENT er det den højeste tærskelværdi af de to, der overføres til Canny()-kantdetektoren (den lavere er dobbelt så lille).
• param2: Anden metodespecifik parameter. I tilfælde af CV_HOUGH_GRADIENT er det den akkumulatoriske tærskelværdi for cirkelcentre i detektionsfasen. Jo mindre den er, jo flere falske cirkler kan blive detekteret. Cirkler, der svarer til de større akkumulatorværdier, vil blive returneret først.
• minRadius: Mindste cirkelradius.
• maxRadius:

Husk, at parametrene skal være forskellige, da vi ikke kan beskrive en cirkel med den samme parametrisering, som vi brugte for linjer, og i stedet skal vi bruge en ligning som (x - x0)^^2 + (y - y0)^^2 = r^^2.

Og til koden:

# 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)

Bemærk, at sammenlignet med det foregående eksempel anvender vi her ikke nogen kantdetekteringsfunktion. Dette skyldes, at funktionen HoughCircles har indbygget canny-detektion.

Og resultatet:

Konklusion

Hough Transform er en fremragende teknik til at detektere simple former i billeder og har flere anvendelser, lige fra medicinske anvendelser som røntgen-, CT- og MRI-analyse til selvkørende biler. Hvis du er interesseret i at vide mere om Hough-rum, anbefaler jeg, at du rent faktisk kører koden, prøver forskellige konfigurationer selv, og at du tjekker OpenCV-dokumentationen for yderligere oplysninger.

Tak for læsning!