Cirkel Hough Transform

Cirkeln Hough Transform (CHT) är en grundläggande funktionsextraktionsteknik som används vid digital bildbehandling för att detektera cirklar i ofullkomliga bilder. Cirkelkandidaterna framställs genom att ”rösta” i Hough-parameterutrymmet och sedan välja lokala maxima i en ackumulatormatris.

Det är en specialisering av Hough-transformen .

Teori

I ett tvådimensionellt utrymme kan en cirkel beskrivas med:

$\left(xa\right)^{2}+\left(yb\right)^{2}=r^{2 }\ \ \ \ \ (1)$

där (a,b) är cirkelns mittpunkt och r är radien. Om en 2D-punkt (x,y) är fixerad kan parametrarna hittas enligt (1). Parameterutrymmet skulle vara tredimensionellt, (a, b, r). Och alla parametrar som uppfyller (x, y) skulle ligga på ytan av en inverterad rätvinklig kon vars spets är vid (x, y, 0). I 3D-utrymmet kan cirkelparametrarna identifieras genom skärningspunkten mellan många koniska ytor som definieras av punkter på 2D-cirkeln. Denna process kan delas in i två steg. Det första steget är att fixera radien och sedan hitta det optimala mitten av cirklar i ett 2D-parameterutrymme. Det andra steget är att hitta den optimala radien i ett endimensionellt parameterutrymme.

Hitta parametrar med känd radie R

Om radien är fixerad skulle parameterutrymmet reduceras till 2D (positionen för cirkelcentrum). För varje punkt (x, y) på den ursprungliga cirkeln kan den definiera en cirkel centrerad vid (x, y) med radien R enligt (1). Skärningspunkten för alla sådana cirklar i parameterutrymmet skulle motsvara den ursprungliga cirkelns mittpunkt.

Betrakta 4 punkter på en cirkel i originalbilden (vänster). Cirkeln Hough-transform visas till höger. Observera att radien antas vara känd. För varje (x,y) av de fyra punkterna (vita punkterna) i originalbilden kan den definiera en cirkel i Hough-parameterutrymmet centrerad på (x, y) med radien r. En ackumulatormatris används för att spåra skärningspunkten. I parameterutrymmet skulle röstantalet punkter genom vilka cirkeln passerar ökas med en. Då kan den lokala maximapunkten (den röda punkten i mitten i den högra figuren) hittas. Positionen (a, b) för maxima skulle vara centrum för den ursprungliga cirkeln.

Flera cirklar med känd radie R

Flera cirklar med samma radie kan hittas med samma teknik.

Observera att det i ackumulatormatrisen (höger fig) skulle finnas minst 3 lokala maximapunkter.

Ackumulatormatris och röstning

I praktiken introduceras en ackumulatormatris för att hitta skärningspunkten i parameterrummet. Först måste vi dela upp parameterutrymmet i "hinkar" med hjälp av ett rutnät och producera en ackumulatormatris enligt rutnätet. Elementet i ackumulatormatrisen anger antalet "cirklar" i parameterutrymmet som passerar genom motsvarande rutnätscell i parameterutrymmet. Numret kallas även röstnummer. Inledningsvis är varje element i matrisen nollor. Sedan kan vi för varje "kant"-punkt i det ursprungliga utrymmet formulera en cirkel i parameterutrymmet och öka rösttalet för rutnätscellen som cirkeln passerar genom. Denna process kallas "röstning".

Efter röstning kan vi hitta lokala maxima i ackumulatormatrisen. Positionerna för de lokala maxima motsvarar cirkelcentrum i det ursprungliga utrymmet.

Hitta cirkelparameter med okänd radie

Eftersom parameterutrymmet är 3D, skulle ackumulatormatrisen också vara 3D. Vi kan iterera genom möjliga radier; för varje radie använder vi föregående teknik. Slutligen, hitta de lokala maxima i 3D-ackumulatormatrisen. Accumulator array bör vara A[x,y,r] i 3D-utrymmet. Röstning bör vara för varje pixel, radie och theta A[x,y,r] += 1

Algoritmen:

1. För varje A[a,b,r] = 0;
2. Bearbeta filtreringsalgoritmen på bilden Gaussisk oskärpa, konvertera bilden till gråskala (gråskala), gör Canny-operatorn , Canny-operatorn ger kanterna på bilden.
3. Rösta alla möjliga cirklar i ackumulator.
4. De lokala maximalt röstade cirklarna för ackumulator A ger cirkeln Hough utrymme.
5. Den maximalt röstade cirkeln av Accumulator ger cirkeln.

Ökningen för bästa kandidat:

För varje A[a,b,r] = 0; // fyll med nollor initialt, instansiera 3D-matris För varje cell(x,y) För varje theta t = 0 till 360 // den möjliga theta 0 till 360 b = y – r * sin(t * PI / 180); //polär koordinat för centrum (omvandla till radianer) a = x – r * cos(t * PI / 180); //polär koordinat för centrum (omvandla till radianer) A[a,b,r] +=1; //röstningen slut slut

Exempel

Hitta cirklar i ett skoavtryck

Den ursprungliga bilden (höger) omvandlas först till en binär bild (vänster) med hjälp av ett tröskelvärde och ett Gaussiskt filter. Sedan hittas kanter (mitten) från den med hjälp av canny edge-detektion . Efter detta används alla kantpunkter av Circle Hough Transform för att hitta underliggande cirkelstruktur.

Begränsningar

Eftersom parameterutrymmet för CHT är tredimensionellt kan det kräva mycket lagring och beräkning. Att välja en större rutnätsstorlek kan lindra detta problem.

Det är dock svårt att välja en lämplig rutstorlek. Eftersom ett för grovt rutnät kan leda till att höga röstvärden erhålls felaktigt eftersom många ganska olika strukturer motsvarar en enda hink. Ett för fint rutnät kan leda till att strukturer inte hittas eftersom röster som härrör från tokens som inte är exakt inriktade hamnar i olika hinkar, och ingen hink har en stor röst.

Dessutom är CHT inte särskilt robust mot brus.

Tillägg

Adaptiv Hough Transform

J. Illingworth och J. Kittler introducerade denna metod för att implementera Hough Transform effektivt. AHT använder en liten ackumulatormatris och idén om en flexibel iterativ "grov till fin" ackumulerings- och sökstrategi för att identifiera signifikanta toppar i Hough-parameterutrymmena. Denna metod är avsevärt överlägsen standardimplementeringen av Hough Transform i både lagrings- och beräkningskrav.

Ansökan

Människor som räknar

Eftersom huvudet skulle likna en cirkel i en bild, kan CHT användas för att detektera huvuden i en bild, för att räkna antalet personer i bilden.

Detektering av hjärnaneurysm

Modifierad Hough Circle Transform (MHCT) används på bilden extraherad från Digital Subtraction Angiogram (DSA) för att detektera och klassificera aneurysmtyp.

Implementeringskod

• Circle Detection via Standard Hough Transform , av Amin Sarafraz, Mathworks (File Exchange)
• Hough Circle Transform , OpenCV-Python Tutorials (arkiverad version på archive.org)

Se även

• Hough transformera
• Generaliserad Hough-transform
• Randomiserad Hough-transform
• Föreläsning 10: Hough Circle Transform , av Harvey Rhody, Chester F. Carlson Center for Imaging Science, Rochester Institute of Technology (11 oktober 2005)