Bilderkennung (Rechtecke)

[Robert S. (razer)]

Hallo an alle,

Ich bin kompletter anfänger im Bereich Bilderkennung. Ich suche gerade 
nach Algorithmen die, die mir ein Bild nach Rechtecken durchsuchen. Und 
zwar habe ich ein Foto einer Matrix (siehe Anhang, die Anzahl der felder 
ist jedoch beliebig),

In manchen Feldern kann jedoch etwas drinnen stehen. Ich möchte das Bild 
analysieren und den Bereich jedes Sub-Rechteck erkennen. Jeder Bereich 
wird dann weiter analysiert, ob und wenn ja was im Rechteck steht.

Könnt ihr mir Tipps geben welche Algorthmen dahinter stehen bzw. 
Schlagwörter mit denen ich mich in die Materie einlesen kann?

Danke im Voraus!

Grüße an alle
Robert

[Marcus B. (raketenfred)]

was weißt du genau über das rechteck

nur, dass es 4 seiten hat und jeweils einen rechten winkel??

jenach matrix kann man ja gucken (mit bruteforce, ggbf optimiert) wo man 
ein rechteck hat- also ob von 0|0 bis 10|10 ein recht eck ist

mit ein bisschen gehirn schmalz sollte das recht leicht machbar sein

such erst nach linien und probier dann ein bisschen aus

so schwer ist das gar nicht!

die matrix schätze ich kennt nur 1/0

[Marcus B. (raketenfred)]

E-Mail Benachrichtigung vergessen-.-

die kann man nicht per edit :(

[Chris L. (kingkernel)]

wie willst du das machen? Mit webcam und PC oder per FPGA?
Such mal nach neuronalen Netzen, das ist das, was du suchst.

[Michael H. (mah)]

sieh Dich mal da um:

http://opencv.willowgarage.com/wiki/

-Michael

[... ... ... (Gast)]

http://www.kreissl.info/bilderkennung.php
http://de.wikipedia.org/wiki/Bilderkennung
http://de.wikipedia.org/wiki/OpenCV

[Martin (Gast)]

Hough!

Das ist ein weites Gebiet mein Bruder. Beginne hier:

http://www.physik.uni-osnabrueck.de/nonlinop/Hough/LineHough.html

[Zwie B. (zwieblum)]

Suchst du vielleicht nach so was? x.png ist das Ausgangsbild, y-png ist 
das Ergebnis. Funktioniert mit OpenCV.

[Robert S. (razer)]

Hallo,

Christian L. schrieb:
> wie willst du das machen? Mit webcam und PC oder per FPGA?

Die Hardware ist eine Embedded Plattform mit Android als OS. Ich werde 
derzeit jedoch am PC unter Java entwickeln und dann nach Android 
Portieren.

Michael Haberler schrieb:
> sieh Dich mal da um:
>
> http://opencv.willowgarage.com/wiki/

Danke für den Tipp. Das schaut schonmal sehr gut aus. Es gibt sogar 
Portierungen nach Android - wobei hier nicht alle Funktionalitäten 
gegeben sind. Ich denke jedoch es ist machbar.

Ich weiß das ist keine triviale Thematik - ich will jedoch auch an der 
Aufgabe lernen.

Zwie Blum schrieb:
> Suchst du vielleicht nach so was? x.png ist das Ausgangsbild, y-png ist
> das Ergebnis. Funktioniert mit OpenCV.

Das schaut schonmal super aus. Kannst du mir sagen wie du das gemacht 
hast?

Danke schonmal für die Tipps!

Robert

[Zwie B. (zwieblum)]

Im Groben: Gauss auf Bild anwenden, Radius ~ Kasterldurchmesser. Das 
schaut dann aus wie ein Eierkarton. Lokale Minima/Maxima suchen, das 
gibt die Mittelpunkte der Kasterl. Daraus das Raster erzeugen.

[peter (Gast)]

Robert S. schrieb:
> Könnt ihr mir Tipps geben welche Algorthmen dahinter stehen bzw.
> Schlagwörter mit denen ich mich in die Materie einlesen kann?

Hi ...

Also ich hab mal mit der Hough tranformation in Matlab linien detektiert 
wobei dies natürlich auch mit Rechtecken möglich ist ... ist ein sehr 
einfach zu realisierender Algorithmus

lg Peter

[Robert S. (razer)]

Hallo,

Ich habe heute ein bisschen mit OpenCV, bzw auch mit deren Samples 
gespielt (siehe Anhang). Das Ausgansbild ist wirklich kein ideales - der 
Algorithmus muss aber damit zurechtkommen. Ich hab hier einfach mal ein 
Suduko (kommt meinem Bild ganz nahe fotografiert).

Ich finde das Ergebnis (das modifizierte Bild jetzt) ist gar nicht mal 
so schlecht. Wie kann ich das noch besser optimieren um alle Rechtecke 
zu erkenen?


Hier mal mein Code den ich aus einem Sample-Programm modifiziert habe.

//Convert to grayscale image
  dst = cvCreateImage( cvSize( img->width, img->height ), IPL_DEPTH_8U, 1 );
  cvCvtColor( img, dst, CV_RGB2GRAY );

  //Normalize Brigthness
  IplImage *hist = cvCreateImage( cvSize( img->width, img->height ), IPL_DEPTH_8U, 1 );
  cvEqualizeHist(dst, hist);

  //Detect edges
  IplImage *canny = cvCreateImage( cvSize( img->width, img->height ), IPL_DEPTH_8U, 1 );
  cvCanny( hist, canny, 0, 250, 5 );

  //only for shwing the result
  IplImage *color = cvCreateImage( cvSize( img->width, img->height ), IPL_DEPTH_8U, 3 );
  cvCvtColor( canny, color, CV_GRAY2RGB );

  CvSeq* contours;
  CvSeq* result;
    double s, t;
    // create empty sequence that will contain points -
    // 4 points per square (the square's vertices)
    CvSeq* squares = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvPoint), storage );

  cvFindContours( canny, storage, &contours, sizeof(CvContour),
                CV_RETR_LIST, CV_CHAIN_APPROX_SIMPLE, cvPoint(0,0) );
            
    // test each contour
    while( contours )
    {
        // approximate contour with accuracy proportional
        // to the contour perimeter
        result = cvApproxPoly( contours, sizeof(CvContour), storage,
            CV_POLY_APPROX_DP, cvContourPerimeter(contours)*0.02, 0 );
        // square contours should have 4 vertices after approximation
        // relatively large area (to filter out noisy contours)
        // and be convex.
        // Note: absolute value of an area is used because
        // area may be positive or negative - in accordance with the
        // contour orientation
        if( result->total == 4 &&
            fabs(cvContourArea(result,CV_WHOLE_SEQ)) > 1000 &&
            cvCheckContourConvexity(result) )
        {
            s = 0;
            
            for(int i = 0; i < 5; i++ )
            {
                // find minimum angle between joint
                // edges (maximum of cosine)
                if( i >= 2 )
                {
                    t = fabs(angle(
                    (CvPoint*)cvGetSeqElem( result, i ),
                    (CvPoint*)cvGetSeqElem( result, i-2 ),
                    (CvPoint*)cvGetSeqElem( result, i-1 )));
                    s = s > t ? s : t;
                }
            }
            
            // if cosines of all angles are small
            // (all angles are ~90 degree) then write quandrange
            // vertices to resultant sequence 
            if( s < 0.3 )
                for(int i = 0; i < 4; i++ )
                    cvSeqPush( squares,
                        (CvPoint*)cvGetSeqElem( result, i ));
        }
        
        // take the next contour
        contours = contours->h_next;
    }

Danke im Voraus
Grüße Robert

[Zwie B. (zwieblum)]

Mach' mal als erstes den hintergrund weg, geht mit "Local Enhance" oder 
was artverwandtem. Im Gimp gibt's z.B. "Differenz der 
Normalverteilungen". Dann Schwellwert auf das Ergebnis.

[Zwie B. (zwieblum)]

Da funktioniert das Erkennen dann schon viel besser ...

[Strubi (Gast)]

Nur ein paar Bemerkungen:

- Die Hough-Transformation faellt eher unter "brute force". Sollte ein 
cleverer, recheneffektiver Algorithmus vermeiden. (Auf einem FPGA saehe 
es anders aus)
- Zusammenhaengende Objekte kriegt man mit einem schnellen 
Fill-Algorithmus indiziert (wenn ueberhaupt noetig, wenn sonst keine 
Objekte auf dem Bild sind, kann das wegfallen)
- Davon erstellt man gleichzeitig per Objekt eine "Boundary Box", also 
die aeussersten Punkte in einem gerade umfassenden Viereck, oder sogar 
Achteck.
- Ecken lassen sich mit einem Corner-Algorithmus gut auffinden 
(Evaluierung der Pixel-Umgebung in Kreis-Sektoren).
- Die Felder der Matrizen lassen sich mit einem schnellen Bresenham 
-Algo abscannen/tracen. Damit kennt man dann die Anzahl Felder.
- Der Rest ist Geometrie, um die Ansicht der Matrix, die ja 
perspektivisch schief sein kann, zu normalisieren.

Benutze obige Methoden fuer einen 2D-Barcode-Algorithmus und kriege auf 
einer 480 MHz CPU etwa 3-6 fps unter Linux, die Detektionsrate ist 
ziemlich gut, schwierig wirds nur, wenn die Lichtverhaeltnisse fliessend 
sind, dann klappts mit dem Threshold im ersten Pass nicht so gut (er 
muss sauber zwischen dunkel/Vordergrund und hell/Hintergrund 
unterscheiden koennen).

Weiss nicht, wie weit/gut die diversen freien Toolboxen das 
unterstuetzen.
Mit dem Bresenham-Tracer kann man auch alternative wueste Sachen machen, 
wenn man in etwa weiss, wonach man sucht..also z.b. um alternierende 
Pattern in einer gewissen Richtung zu finde, oder man eine Linie 
zwischen zwei Punkten vermutet. Da gibt es eigentlich nichts 
schnelleres.

Gruesse,

- Strubi

[Robert S. (razer)]

Zwie Blum schrieb:
> Mach' mal als erstes den hintergrund weg, geht mit "Local Enhance" oder
> was artverwandtem.

Dazu habe ich anscheinend in OpenCV noch nicht das richtige gefunden. 
Ich dachte cvEqualizeHist() sorgt für den Effekt - tut es aber nicht.

Zwie Blum schrieb:
> Im Gimp gibt's z.B. "Differenz der
> Normalverteilungen". Dann Schwellwert auf das Ergebnis.

Hab bei mir jetzt die englische Version installiert. Dort ist 
"Difference of Gaussians" bei den Kantenfiltern vorhanden - hast du das 
gemeint? Für die Kanten hab ich ja jetzt den Canny (weil in OpenCV 
vorhanden).

Etwas anderes passendes habe ich jetzt nicht gefunden. Kennst du was aus 
OpenCV?

Strubi schrieb:
> - Zusammenhaengende Objekte kriegt man mit einem schnellen
> Fill-Algorithmus indiziert (wenn ueberhaupt noetig, wenn sonst keine
> Objekte auf dem Bild sind, kann das wegfallen)
> - Davon erstellt man gleichzeitig per Objekt eine "Boundary Box", also
> die aeussersten Punkte in einem gerade umfassenden Viereck, oder sogar
> Achteck.
> - Ecken lassen sich mit einem Corner-Algorithmus gut auffinden
> (Evaluierung der Pixel-Umgebung in Kreis-Sektoren).

Bei einem "guten" Bild funktioniert der oben gepostete Algorithmus von 
OpenCV sehr gut. Einzig einen Flächenschwellwert muss ich da auf jeden 
Fall einbauen, um nicht größere "zusammengebaute" Rechtecke - hier wäre 
fast FloodFill sogar besser, oder?

Strubi schrieb:
> - Die Felder der Matrizen lassen sich mit einem schnellen Bresenham
> -Algo abscannen/tracen. Damit kennt man dann die Anzahl Felder.

Was meinst du damit genau? Ich kenne Bresenham als Algorithmus zum 
zeichnen (Linie/Kreis).

Grüße Robert

[Zwie B. (zwieblum)]

Tja, OpenCV ist nett, aber halt auch nur eine Toolbox. Ist nicht immer 
alles drinnen, was man braucht. Aber es ist alles drinnen, um ein 
Werkeug zu bauen, das macht was du brauchst - und da liegt die Kunst bei 
der Bldverarbeitung :-)

"Difference of Gaussians" ist genau das Ding. Sehr einfaches Konzept, 
sehr brauchbar.

Was machst du mit den Kanten, wenn du sie hast (Hab' mal das Kantenbild 
aangehängt)? Probier' mal die Skelettlinie zu finden, die ist 
interessanter.

Hast du Literatur? Gonzales/Woods: "Digital Image Processing", 
Sonka/Hlavac/Boyle: "Image Processing, Analysis, and Machine Vision" 
würd' ich die beide als Gutenachtlektüre empfehlen. Jähne, "Digitale 
Bildverarbeitung" geht auch zur Not.

[Strubi (Gast)]

Robert S. schrieb:
> Was meinst du damit genau? Ich kenne Bresenham als Algorithmus zum
> zeichnen (Linie/Kreis).

Hi Robert,

ist auch genau derselbe Algorithmus, nur anstatt dass Du ein Pixel 
setzt, liest du es. So kannst du entlang eines Vektors Pixel abtasten 
und z.B. in diesem Fall die Kastenlaenge bestimmen. Das wird natuerlich 
tricky, wenn du mehr perspektivische Verzerrung erlaubst.

Gruesse,

- Strubi

[SilentPro (Gast)]

Hi,

also komplizierte Lösungen über Kanten finden (siehe zahlreiche Versuche 
mit angehängten Grafiken) sind hier absoluter "overkill".
Damit macht man das Bild komplizierter zu interpretieren als es vorher 
war, weil die Linen nicht mehr gefüllt sind und Unterbrechungen 
bekommen.

Bresenham ist ein guter Ansatz, um eine effektive Lösung auszuarbeiten.
Als erstes würde ich aber hier mit der Hough-Transformation anfangen!
Die Methode ist in ihrer Basis-Variante unglaublich einfach und dabei 
hocheffektiv um gerade Linien zu finden. Für Echtzeiterkennung wäre das 
allein wohl kaum geeignet, obwohl es ja auch optimierte Varianten gibt.

Man sollte also erstmal mittels Hough-Transf. die waagrechten und 
senkrechten Linien finden und daraus dann ein Netz mit parallelen Linien 
generieren, dass man noch an die Vorlage anpasst, um die Inhalte der 
einzelnen Boxen exakt zu loklisieren.
Wenn das gut klappt, kann man es optimieren, indem man die 
Hough-Transformation nur auf einen Teil des Netzes anwendet (eine Ecke 
mit je 2-3 Kästchen in x- und y-Richtung), damit die ersten beiden 
waagrechten und senkrechten Begrenzungslinien als Vektoren bestimmt und 
danach per individuellem Bresenham-Scan/Trace die parallen 
Begrenzungslinien auffindet.

Die Hough-Transformation ist halt extrem anspruchslos, was das 
Ausgangsbild angeht (Kontrast, Lücken, Linenbreite), solange die Linien 
recht gerade sind. Wichtig wäre nur die evtl. breiten Spots 
zusammenzufassen bzw. das Zentrum zu bestimmen, um je eine Gerade und 
keine Schar von Geraden zu erhalten.

So könnte man also auch mit einem schlechten Ausgangsbild mit 
zusätzlichen Inhalten in den Kästchen und beliebigem Hintergrund, sowie 
perspektivischen Verzerrungen die Umrandungen sicher bestimmen.
Nur bei Verzerrungen, die die Linien zu Kurven werden lässt, wird's 
irgendwann schwierig; ansonsten sollte es "relativ trivial" sein!

[m8art (Gast)]

Hallo,

@razer
Ich bin auch interessiert an einer Android OpenCV Portierung. Könntest 
du mir bitte verraten welche Portierung du verwendest und welches 
Beispiel du verwendet hast?

Danke!

mfg
Markus