formen in einer zahlen matrix erkennen

Das Forum fĂĽr Programmierer und Systemadmins. Von Shell-, Perl- und PHP-Scripts bis zur objektorientierten Programmierung mit C++.

formen in einer zahlen matrix erkennen

Beitragvon Basti » Mi 23 Apr, 2003 13:50

also, im prinzip ist die problemstellung recht einfach:
ich habe eine zahlen-matrix bestehnd aus 1ern und 0ern sagen wir mal 10x5 also dann so:

0001111001
0001001001
0010001001
1001001000
0001111000

formen wie zb quadrate, t-stĂĽcke, kreuze und L-stĂĽcke stellen kein problem dar, diese zu erkennen.
000
111 < beispiel fĂĽr t-stĂĽck
010
schwierig wirds dann bei "geschlossenen" flächen, wie jetzt im obigen beispiel.
kann ich das irgendwie berechnen??
oder eine art rekursiven algorithmus entwickeln, der die matrix abcheckt?
ich denke man bräuchte so eine art läufer, der eine geht linksrum, der andere rechts und wenn sie sich irgendwie treffen, ist die fläche zu.....
aber wie?
Basti
 

RE: formen in einer zahlen matrix erkennen

Beitragvon mad » Mi 23 Apr, 2003 23:48

hm .. imho musst du hier die fragestellung bisserl konkretisieren,
aber ich geb mal trotzdem meinen senf dazu ..

a) ganz bestimme vorher festgelegte bitmuster _wiedererkennen_

einfach irgendwas mit nem hash ueber das gesamte bitmuster und dann mit ner liste
von hash-summen vergleichen, fertig ... funkt halt nur fuer "exakte" formen ..


oder b) "brute force" ...

eine moeglichkeit um nen kreis zu erkennen waer wohl irgendwas in der art von ...
such dir einen "1"er als anker .. und folge den "1"ern in der nachbarschaft ...
bis entweder keine "1"er mehr da sind oder du wieder bei der ausgangsposition (x,y)
angelangt bist (hm .. klingt irgendwie nach "problem des handlungsreisenden")

merk dir am weg die winkelsummen ..

wennst dann 360 grad hast und die x,y-position des aktuellen bits gleich der ausgangspostition ist, dann wirds wohl was kreisaehnliches gewesen sein ..
wenns jedoch "1"er maessig nicht mehr weitergeht, und du nicht bei der ausgangs-
position bist, is es wohl eher keine geschlossene form ..

oder aber auch nicht ... ausnahmefaelle gaebs da ja auch zuhauf .. ganz zu schweigen von "rauschen" im bild und so.. oije .. na ich weiss nicht ob die idee
so gut war .. .. is schon zu spaet fuer sowas .. ;-)


am besten funkt imho c)

sprich vorher festgelegte formen aus beliebigen bitmustern wiedererkennen
(mit abweichungen von der idealform) .. also klassische image-recognition
mit bisserl fuzzi-logic.

is nicht ganz trivial .. aber schreit halt foermlich nach "neuronale netze" ..
im speziellen zb selbstorganisierende karten (maps) bzw. kohonen-netze.

such mal in google danach bzw. wirf mal einen blick in die
comp.ai.neural-nets FAQ, da wirst diesbezueglich recht schnell fuendig
(was theorie, literatur und bsp.-code angeht) ..

und nach ein bisserl "training" funken die dann auch ganz gut ..
zumindest was einfache formen angeht (schwarz/weiss/line-art)

hth,
mad.
mad
 


ZurĂĽck zu PROGRAMMIER FORUM

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 36 Gäste