---

Som endnu et af utallige besøg i, for mig, nye områder, er jeg nået til
hough-transformationen.
Ideen bag den er jo mildest talt elementær, og at implementere den for snart
sagt hvad som helst, der kan beskrives ved et endeligt antal parametre, er
lige så elementært.

Problemerne kommer imidlertid hvis jeg forsøger at implementere bare en
simpel 3D cirkeldetektion (x,y,r) for et 512*512 pixel stort bitmap.
Problemet er hastigheden. Det tager særdeles lang tid, hvilket siger sig
selv, når man ser på antallet af parametre som bør testes for at få en
fornuftig opløsning.

Det kan umuligt være et nyt problem, men jeg kan sjovt nok ikke finde noget
videre information omkring optimering.

Nu gør jeg det at jeg beregner kanter i mit billede. Jeg beregner det som et
binært bitmap over kantpixels.
For hver kantpixel undersøger jeg hver position i parameterrummet for et
match. Hvis match så øger jeg akumulatoren med 1.
Til sidst ser jeg på akumulatorpositioner med værdier over en grænse og tror
på at de tilsvarende positioner i parameterrummet angiver mine cirkler.

Det kan naturligvis optimeres. Hvis jeg har en max r på mr, så behøver jeg
ikke teste parameterpunkter som er mere end mr fra min pixel i en af de tre
akser. Det gør det hurtigere, men der er meget langt tilbage. I Matlab tager
en test af 512*512 pixels hvis jeg tester centrumpositioner fra 1 til 512
for x og y og radius mellem 10 og 50 flere timer på en amd xp 2.2+ med 512MB
ram.Det kan da ikke være rigtigt?

Jeg overvejer så at opdele mit 3D parameterrum i 8 terninger. Teste centrum
i hver terning mod mine pixels og øge akumulatoren hvis afstanden til
cirklen med den avnendte parameter er mindre end eller lig afstanden til
kanten af terningen. Terninger som har mere end en vis værdi i akumulatoren
bagefter bliver rekursivt opdelt i 8 mindre terninger og samme test kører
igen. Det bør kunne frafiltrere mange ubrugelige parameterpositioner, men er
det en realistisk optimering?
1: Jeg har intetsteds læst den omtalt, så hvis den ikke bruges er der vel en
fejl?
2: Er fejlen at man med bare en moderat mængde støj skal dele samtlige
terninger op i meget stor dybde før man kan springe blokke over?

---

---

Jakob Nielsen <a@b.c> skrev:
> Problemerne kommer imidlertid hvis jeg forsøger at implementere bare en
> simpel 3D cirkeldetektion (x,y,r) for et 512*512 pixel stort bitmap.
> Problemet er hastigheden. Det tager særdeles lang tid, hvilket siger sig
> selv, når man ser på antallet af parametre som bør testes for at få en
> fornuftig opløsning.

Nu kendte jeg ikke til området før jeg læste lidt om det på internettet - så
derfor må du hænge mig op på det jeg siger, men jeg vil da lige forsøge,
hvis det kan hjælpe.

I stedet for at teste hver pixel i dit bitmap kunne du måske implementere en
form for kant-detektion på billedet først. Denne detektion vil resultere i
en liste med punkter, nemlig de punkter der ligger i kanten af en figur på
den oprindelige bitmap. Hvordan denne præcist implementeres ved jeg ikke,
men jeg ved det kan lade sig gøre.

Herefter har du kun et lille antal punkter at tjekke (medmindre din
oprindelige bitmap da er meget kompleks). Megen støj skulle også gerne være
fjernet ved denne kant-detektion.

For et givent punkt vil det tilsvare til følgende graf i et hough-rum (er
jeg korrekt?):

f(x) = r * sin(x + t) , r i R, t i [0, pi[, hvor r er punktets afstand fra
(0, 0) og t er vinklen.

Du vil for den liste af punkter kunne opstille alle grafer og finde
skæringspunkterne. Disse skæringspunkter kan du evt. plotte ind i på en ny
bitmap og her har du så en form for hough-transformation af dit billede.
Husk at der kan ligge flere punkter inden for én pixel af din bitmap - det
kommer an på opløsningen - i så fald skal de selvfølgelig akkumeleres. Dvs.
hver pixel angiver antallet af punkter der ligger i pixlens interval.
Husk også at teoretisk set er en speciel situation, hvor skæringen vil være
alle x i [0, pi[ - når to grafer ligger oven i hinanden. Men det vil ikke
være tilfældet eftersom du ikke tjekker to ens punkter fra den oprindelige
bitmap (medmindre der er en fejl i dit program!) og (r, t) findes unikt for
et givent punkt.

Det vil formentlig virke for detektion af rette linier, da de her vil
optræde som punkter på den nye bitmap, men om man også kan få det til at
virke for cirkler ved jeg ikke (kunne ikke lige finde noget om det emne på
nettet). Forskellen fra den bitmap du opnår ved denne metode og den anden,
som du selv har benyttet, er at kun skæringspunkterne er plottede og ikke
hele grafen.

Håber du kunne følge mig.

Jeg ville gerne teste det, men jeg kan altså ikke finde ud af at løse
følgende ligning (surt nok), hvilket er nødvendig:
k * sin(x + t1) = sin(x + t2) , k i R, t1,t2 i [0, pi[, x i [0, 2*pi[

Mvh.
Bjarke

---

Det er lige gået op for mig at det jeg skrev om hvis kun kan bruges til
detektion af rette linier. Men måske du alligevel kan få nogle idéer du kan
overføre til din cirkel-detektion.

Mvh.
Bjarke

---

> I stedet for at teste hver pixel i dit bitmap kunne du måske implementere
en
> form for kant-detektion på billedet først. Denne detektion vil resultere i
> en liste med punkter, nemlig de punkter der ligger i kanten af en figur på
> den oprindelige bitmap. Hvordan denne præcist implementeres ved jeg ikke,
> men jeg ved det kan lade sig gøre.

Ja, det kan det. Jeg citerer lige fra oprindelige indlæg "Nu gør jeg det at
jeg beregner kanter i mit billede. Jeg beregner det som et
binært bitmap over kantpixels.", så jeg er da enig
Det er også nødvendigt hvis man søger cirklerne som cirkelbuerne og ikke som
udfyldte flader.

> Du vil for den liste af punkter kunne opstille alle grafer og finde
> skæringspunkterne. Disse skæringspunkter kan du evt. plotte ind i på en ny
> bitmap og her har du så en form for hough-transformation af dit billede.

Problemet er dog at man ikke nødvendigvis søger præcise skæringer, da disse
måske slet ikke forekommer. Man søger istedet høje koncentrationer af
krydsninger i et givent område.

> Husk at der kan ligge flere punkter inden for én pixel af din bitmap - det
> kommer an på opløsningen - i så fald skal de selvfølgelig akkumeleres.
Dvs.
> hver pixel angiver antallet af punkter der ligger i pixlens interval.

Man har kun ens bitmap at arbejde med. Hvordan formen af den underlæggende
struktur er, det kan man ikke udtale sig om. Den akumulering foregik jo
oprindeligt i kameraet og gav evt. et gråtonebillede.

Jeg tror problemet i din metode er at du vil løse eksakte ligninger, hvilket
forudsætter total opløsning i det oprindelige billede. Alene kantdetektionen
kan give problemer der, da den virkelige kant som sådan kan ligge mellem to
pixels. Hvis du kun beregner præcise skæringer, så vil du misse de fleste
faktiske cirkler.

Endelig er der problemet at en pixel ikke repræsenteres ved een cirkel i
parameterrummet - den repræsenteres som sådan af uendeligt mange cirkler.
Det er nok der du glider lidt af. Hvis du definerer et parameterrum for
cx,cy,r og sætter både cx og cy til [0..511] og r til [1..100] og kun
beregner for heltal, så ender du på omkring 26 milioner cirkler. Bemærk at
hvert punkt i parameterrummet er en cirkel. Hvert punkt definerer et centrum
og en radius.
Givet en pixel i dit billede skal du altså finde samtlige cirkler (punkter)
i parameterrummet som opfylder at (x-cx)^2+(y-cy)^2-r^2=0.
Disse punkter beskriver en spids kegle fra cx=x,cy=y,r=0 og ud i rummet
langs voksende r.
Hvis du beregner det diskret, som jeg beskrev lidt tidligere, og tester for
de 26 milioner cirkler, så kan du se hvilke af punkterne i parameterrummet,
der beskriver cirkler hvor (x-cx)^2+(y-cy)^2-r^2 er tæt nok på nul til at du
kalder det et match. For hver pixel beregner du altså hvilke cirkler de
kunne ligge på. Cirkler hvor mange punkter føler sig hjemme, er nok de
virkelige cirkler.

Regner du på det ved at løse ligningerne, så er problemet at hver pixel kan
beskrives ved uendeligt mange cirkler. For hver pixel skal du altså beregne
uendeligt mange cirkler og beregne skæringenen mellem disse uendeligt mange
cirkler og hver af de uendeligt mange cirkler hver af de andre pixels har.

Jeg tror ikke din metode vil virke, men takker alligevel for dit input. Vil
også give det en tanke mere om mængden af cirkler kan beregnes sådan. Tror
det dog ikke. Bare tag to pixels i 2d-billedet. For hver pixel kan du nu
tegne vilkårligt mange cirkler som skærer din pixel. Du vil derfor ende ud
med vilkårligt mange skæringer mellem alle cirklerne som skærer hver af de
to punkter.Sagt anderledes. Givet de to pixels og et tredje 2d punkt kan jeg
komme med to cirkler som hver skærer en af de to pixels og det tredje punkt.
Altså skærer de to cirkler (i det generelle tilfælde) hinanden i det tredje
punkt. Altså kan ethvert punkt fungerer som skæringmellem to cirkler som
passer med pixels - der er skæringer i hele parameterrummet.

---

Jakob Nielsen <a@b.c> skrev:
> Ja, det kan det. Jeg citerer lige fra oprindelige indlæg "Nu gør jeg det
> at
> jeg beregner kanter i mit billede. Jeg beregner det som et
> binært bitmap over kantpixels.", så jeg er da enig
> Det er også nødvendigt hvis man søger cirklerne som cirkelbuerne og ikke
> som
> udfyldte flader.

Ja, nu du siger det. Det skrev du godt nok også. Så langt så godt

Nu har jeg læst lidt mere om Hough transformationer og er blevet lidt
klogere. Det er jo egentlig mere simpelt end jeg før troede.

> Problemet er dog at man ikke nødvendigvis søger præcise skæringer, da
> disse
> måske slet ikke forekommer. Man søger istedet høje koncentrationer af
> krydsninger i et givent område.

Hvad mener du her med krysninger?

Jeg kan godt se der er en forskel på en bitmap, hvor hele kurven for et
givent punkt er med, men de højeste koncentrationer vil vel også være at
finde de steder hvor kurverne rent faktisk skærer. Og da det netop er de
højeste koncentrationer man vil finde gør det ingen forskel i denne
sammenhæng. Ja, det jeg vil gøre er at beregne skæringer. Men måske er det
alligevel en dårlig idé rent tidsmæssigt. Læs nedenfor.

[klip]
> Givet en pixel i dit billede skal du altså finde samtlige cirkler
> (punkter)
> i parameterrummet som opfylder at (x-cx)^2+(y-cy)^2-r^2=0.
> Disse punkter beskriver en spids kegle fra cx=x,cy=y,r=0 og ud i rummet
> langs voksende r.
[klip]

Ja, for hver kantpixel i dit billede er der en tilsvarende spids kegle. Alle
disse kegler skærer hinanden i parabelbuer. Disse parabelbuer vil ligeledes
skære hinanden i punkter. Det kan indses intuitivt ved at tænke på at der er
uendeligt mange cirkler der går igennem to givne punkter (som du også selv
har sagt), men kun én cirkel, der netop skærer tre givne punkter.

Hvis du finder skæringer mellem dine pababelbuer og akkumulerer dem ind i en
3-dimensionel bitmap, vil jeg mene at du har dine cirkler ved de højeste
koncentrationer. Spørgsmålet er dog kørselstid - og her er din metode vist
alligevel bedre over et vist antal hundrede kantpixler, da antallet af
skæringspunkter i min metode ikke kun stiger liniært som funktion af antal
kantpixler. Din metode derimod er liniær - sådan som jeg har forstået den.

> Jeg tror ikke din metode vil virke, men takker alligevel for dit input.
> Vil
> også give det en tanke mere om mængden af cirkler kan beregnes sådan. Tror
> det dog ikke. Bare tag to pixels i 2d-billedet. For hver pixel kan du nu
> tegne vilkårligt mange cirkler som skærer din pixel. Du vil derfor ende ud
> med vilkårligt mange skæringer mellem alle cirklerne som skærer hver af de
> to punkter.

Ja, mængden af cirkler der går gennem to punkter vil ligge på parabelbuen
(skæringsmængden af keglerne) i dit hough-rum.

> Sagt anderledes. Givet de to pixels og et tredje 2d punkt kan jeg
> komme med to cirkler som hver skærer en af de to pixels og det tredje
> punkt.
> Altså skærer de to cirkler (i det generelle tilfælde) hinanden i det
> tredje
> punkt. Altså kan ethvert punkt fungerer som skæringmellem to cirkler som
> passer med pixels - der er skæringer i hele parameterrummet.

Den forstod jeg ikke lige :-/

Min metode sagt på en anden måde: Givet tre pixler har du præcis én cirkel
der vil skære disse. Alle kombinationer af tre pixler i mængden af
kantpixler vil du altså kunne finde centrum for alle cirkler der er mulighed
for. Plotter du centrum ind i en bitmap vil du kunne finde dem med højest
koncentrationer. At finde centrum for cirklen der skærer tre punkter er
noget geometri jeg ikke på stående fod kan huske. Det er noget med den ind-
eller omskrevne cirkel af en trekant.

Mvh.
Bjarke