CGVert. CGVert. Was gehört alles zu einer Kante? • Wie findet man alle Pixel die zu einer Kante gehören? Was gehört alles zu einer Kante? • Kantenfilter liefern Kanten-Pixel – Die analytische Beschreibung der zur Kante gehörenden Geraden? Sobel X ax+by+c=0 ? Laplace Sobel Y 1/8 0 -1/8 2/8 0 -2/8 0 0 0 1/8 0 -1/8 -1/8 -2/8 -1/8 1/8 2/8 1/8 • Probleme – Welche Pixel gehören zu einer Kante? 0 1 0 1 -4 1 0 1 0 ? – Kanten können Lücken haben • Verdeckung, zu wenig Kontrast, ... 08.11.2006 CGVert. FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 1 08.11.2006 CGVert. Der Sobelfilter (Wiederholung) • An schrägen Kanten sx und sy FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 2 Hough-Transformation • Algorithmus um Pixel zusammenzufassen, die zu einer Kante gehören – Je vertikaler, desto mehr sx – Bestimmt parametrische Darstellung der Kante – Je horizontaler, desto mehr sy • Gerade, keine Strecke • Berücksichtigt (durch Verdeckung, Rauschen, zu wenig Kontrast, ... entstandene) Lücken • Globales Verfahren • Kanten-Richtung: r=(sx,sy) – Zeigt senkrecht zur Kante zur helleren Seite (Helligkeitsgradient) – beschreibt Intensität (Kontrast) der Kante – Kanten müssen eine Mindestlänge haben • Erweiterbar auf andere parametrisierbare geometrische Formen – Hessesche Normalform einer Geraden: • lässt sich mittels sx und sy bestimmen: – Kreise, Ellipsen sy – Kugeln, Ellipsoide sx • p ist Abstand zum Ursprung 08.11.2006 FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 3 08.11.2006 FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 4 CGVert. CGVert. Hough-Transformation • Grundlegende Idee (Paul V. C. Hough 1962) Hough-Transformation für Geraden • Gerade entspricht dem Punkt – Suche unbekannte Parameter einer parametrisierten Kurve im Bild-Raum im Hough-Raum – Parametrisierungen • Geraden: Hesse´sche Normalform • Kreise: Mittelpunktsform Bild-Raum Hough-Raum Hough-Transformation • ... – Parameter definieren Parameterraum (Hough-Raum) y • Wird auch (Hough-)Akkumulator genannt – Für jedes Pixel auf einer Kante d d • Bestimme alle möglichen Kurven (Geraden, Kreise, ...) durch das Pixel – Diese beschreiben Kurven im Parameterraum x – Im Parameterraum (Akkumulator) entstehen (akkumulieren sich) hohe Werte an den Stellen, die den gesuchten Kurven im Bild entsprechen 08.11.2006 CGVert. FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 5 CGVert. Hough-Transformation für Geraden FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke Hough-Transformation für Geraden – Die Gerade steht senkrecht auf (0,0)-(x0,y0) Bild-Raum Hough-Raum Hough-Transformation y y d FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke Hough-Raum Hough-Transformation x 08.11.2006 6 • Abstand d maximal, wenn (x0,y0) Lot von (0,0) auf Gerade ist • Geradenbüschel durch einen Punkt im Bild-Raum wird auf sinusförmige Kurve im Hough-Raum abgebildet Bild-Raum 08.11.2006 d x 7 08.11.2006 FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 8 CGVert. CGVert. Hough-Transformation für Geraden Diskretisierung des Hough-Raums • Bildgröße (width, height) • Winkel • Bilder von Punkten auf einer Geraden bilden Häufungspunkte im Hough-Raum – Periodisch: Bild-Raum Hough-Raum (255,0) führt zu d=-d – Abhängig von Bildgröße: Hough-Transformation – Schneller (Zweierpotenz) • Distanz d y d=-dmax (0,0) d d=0 HoughRaum – Optimaler Wertebereich: Ursprung in Bildmitte x d=dmax (0, 2dmax) (255, 2dmax) (0,0) 08.11.2006 CGVert. FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 9 Behandlung der Hough-Raum-Ränder • wrap around: entspricht (0,-d) Index 0 Index 2dmax d=-dmax Index 2dmax d=dmax 08.11.2006 Hough-Transformation (Implementierung) • Durchführung der Hough-Transformation Index -1 Index 255 d=0 HoughRaum def addToHoughAccumulator(im, houghAccu, x, y): iw2, ih2, hh2 = im.width/2, im.height/2, houghAccu.height/2 for alphaIndex in range(NR_OF_ANGLES): alpha = alphaIndex*pi/NR_OF_ANGLES d = (x-w2)*cos(alpha) + (y-h2)*sin(alpha) dIndex = hh2 + int(d) houghAccu[alphaIndex][dIndex] += 1 d=dmax FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke – Diskretisiere Hough-Raum (Akkumulator) def makeHoughTransformation(im, houghAccu, sobelThreshold): for y in range(im.height): for x in range(im.width): sobelX, sobelY = calcSobel(im) sobelLength = sqrt(sobelX**2+sobelY**2) if sobelLength > sobelThreshold: addToHoughAccumulator(im, houghAccu, x, y) d=-dmax HoughRaum d=0 10 – Schwellwert für Kante: – Index (-1, i) entspricht (255, 2dmax-i) Index 256 CGVert. FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke • Berechne für jedes Pixel sobelX, sobelY – Index (256, i) entspricht (0, 2dmax-i) Index 0 08.11.2006 11 08.11.2006 FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 12 CGVert. CGVert. Hough-Transformation (Linien-Extraktion) Gradientenbasierte Optimierung • Richtung des Sobelvektors (Gradient) gibt (in etwa) die Richtung der Geraden an • Extraktion der Linien aus dem Hough-Akkumulator – Nehme alle Parameter als Linien • deren Akkumulatorwert über einem Schwellwert liegen und • Anstatt alle Winkel, nur Winkel-Bereich aktualisieren: • die größer sind als alle Akkumulatorwerte in vorgegebener Umgebung • Probleme – Viele Parameter 08.11.2006 CGVert. x • Vorteile Eingabe (Bildraum) – Viel schneller, da nur noch 2*angleUncertainty+1 Einträge pro Pixel (anstall z.B. 256) Ausgabe (Bildraum) FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke – Geraden unterschiedlicher Orientierung stören sich nicht mehr im Houghraum 13 • Intervall durchlaufen 14 Gradientenbasierte Optimierung def addToHoughAccumulator(im, houghAccu, x, y, sobelX, sobelY): iw2, ih2, hh2 = im.width/2, im.height/2, houghAccu.height/2 sobelAngle = atan2(sobelY, sobelX) alphaLo = int(sobelAngle/pi*NR_OF_ANGLES) alphaLo -= angleUncertainty if alphaLo<0 : alphaLo += NR_OF_ANGLES if alphaLo<0 : alphaLo += NR_OF_ANGLES alphaHi = alphaLo + 2*angleUncertainty + 1 if alphaHi > NR_OF_ANGLES: alphaHi -= NR_OF_ANGLES alphaIndex = alphaLo while alphaIndex!=alphaHi: if alphaIndex==NR_OF_ANGLES : alphaIndex = 0 alpha = alphaIndex*pi/NR_OF_ANGLES d = (x-w2)*cos(alpha) + (y-h2)*sin(alpha) dIndex = hh2 + int(d) houghAccu[alphaIndex][dIndex] += 1 alphaIndex += 1 • Intervall in periodischem Raum (normalisiert [0,N-1]) in range(lo, hi+1): // period N = i % N ip<0: ip += N do something with ip • Intervall durchlaufen in periodischen Räumen (optimiert) n = hi - lo // period N lo = lo % N; if lo<0: lo+=N hi = lo+n+1; if hi>N: hi-=N i = lo while i!=hi: if i==N: i=0 // do something with i i += 1 FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke • Optimierte Hough-Transformation for i in range(lo, hi+1): // do something with i 08.11.2006 08.11.2006 CGVert. Intervalle in periodischen Räumen for i ip if // Sobel X Houghraum • sobelThreshold • Umkreis für lokales Minmum Sobel Y (x,y) – Sehr langsam • Diskretisierung des Parameterraums y 15 08.11.2006 FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 16 CGVert. Hough-Transformation Optimierungen • in 256 Schritten diskretisieren (Achtung Periodizität) CGVert. Hough-Transformation für Kreise • Kreis in Mittelpunktsform • Im Hough-Raum: Mittelpunkt (xc,yc) und Radius r • d in Bezug auf Bildmitte um Hough-Raum klein zu halten – (xc,yc) hat gleiche (oder etwas größere) Dimension wie Bild – r in Intervall zulässiger Radien • Nur Winkel, die ungefähr der Richtung des Sobel-Vektors entsprechen im Hough-Raum erhöhen Bild-Raum (x,y) 3D-Hough-Raum (xc,yc,r) Hough-Transformation • Look Up Tabellen verwenden y yc – sin, cos für diskretisierte Winkel r – Sobel-Betrag – Diskretisiertes & normalisiertes Winkel-Intervall x 08.11.2006 CGVert. FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 17 CGVert. Hough-Transformation für Kreise def makeHoughTransformation(im, houghAccu, sobelThreshold): for y in range(im.height): for x in range(im.width): sobelX, sobelY = calcSobel(im) sobelLength = sqrt(sobelX**2+sobelY**2) if sobelLength > sobelThreshold: addToCircleHoughAccumulator(im, houghAccu, x, y) 18 Ausnutzen der Sobel-Richtung – 2(rmax-rmin+1) Einträge statt 4r2max def addToCircleHoughAccumulator(houghAccu, x, sobelLength = sqrt(sobelX**2 + sobelY**2) for r in range(RMIN, RMAX) // along normal xc = x + r*float(sobelX)/sobelLength // yc = y + r*float(sobelY)/sobelLength // houghAccu[xc][yc][r] += 1 // against normal (respect clipping) xc = x - r*float(sobelX)/sobelLength // yc = y - r*float(sobelY)/sobelLength // houghAccu[xc][yc][r] += 1 – Laufe durch (xc,yc), berechne r, erhöhe houghAcuu[xc][yc][r] def addToCircleHoughAccumulator(im, houghAccu, x, y): for dy in range(-RMAX,RMAX) for dx in range(-RMAX,RMAX): r = sqrt(dx*dx + dy*dy) houghAccu[x+dx][y+dy][r] += 1 – Extrem langsam und speicherintensiv da 3D Hough-Raum FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke • Sobel-Vektor (sx,sy) zeigt in (entgegen) Richtung Mittelpunkt Sobel Y • Gehe entlang/entgegen der (x,y) y x Richtung des Sobel-Vektors x Sobel X xx Pixel und erhöhe den dortigen Hough-Raum • Implementierung 08.11.2006 08.11.2006 xc 19 08.11.2006 x y, sobelX, sobelY): boundaries !!! boundaries !!! boundaries !!! boundaries !!! FH-Wiesbaden --- Medieninformatik --- WS 06/07 --- Prof. Dr. Ulrich Schwanecke 20
© Copyright 2024 ExpyDoc
