11.08.2025, 06:36
Sprache ändern
Registrieren
Anmelden
Du bist nicht angemeldet.
elbarto`
God
dynamisch muster in matrix finden (python)
Donnerstag, 28. Mai 2009, 16:10
ich habe eine matrix die 8x8 zeichen groß ist und mit beliebigen werten gefüllt ist, also so:
nun geht es darum bestimmte muster in dieser matrix zu finden z.b. so etwas
(alle x den gleichen wert, #? sind beliebige werte, eins der y = x)
erklärung dazu:
es soll also ein muster gefunden werden wo die werte auf x gleich sind. als ausgabe wäre die position von ? am besten, und eins der y muss =x sein
die muster sind unterschiedlich groß, können auch z.b. 4x2 groß sein
also es würde z.b. auf so etwas zutreffen:
die sache mit dem y ist nicht so wichtig, das kann ich auch danach noch abfragen
aber wie finde ich so ein muster über mehrere zeilen/spalten?
ich denke das müsste gehen indem ich alles in eine zeile schreibe und dann per regexp abfrage, zwischen x und y koordinaten kann ich dann ja unterscheiden indem ich per m[8*y+x] darauf zugreife und die koordinaten kann ich bestimmen indem ich die position durch 8 teile und der rest is dann der x wert.
allerdings ist mir nicht klar wie ich die regexp pattern so verändere das ich alle positionen ordentlich abfrage und das ganze für unterschiedlich große muster
ich hoffe mir kann da jemand helfen
hab den selben thread auch im python forum: http://www.python-forum.de/topic-19028.html
|
Quellcode |
1 2 3 4 5 6 7 8 |
######## ######## ######## ######## ######## ######## ######## ######## |
nun geht es darum bestimmte muster in dieser matrix zu finden z.b. so etwas
|
|
Quellcode |
1 2 3 4 |
##y# xx?y ##x# ##x# |
(alle x den gleichen wert, #? sind beliebige werte, eins der y = x)
erklärung dazu:
es soll also ein muster gefunden werden wo die werte auf x gleich sind. als ausgabe wäre die position von ? am besten, und eins der y muss =x sein
die muster sind unterschiedlich groß, können auch z.b. 4x2 groß sein
also es würde z.b. auf so etwas zutreffen:
|
|
Quellcode |
1 2 3 4 |
##1# 11?# ##1# ##1# |
die sache mit dem y ist nicht so wichtig, das kann ich auch danach noch abfragen
aber wie finde ich so ein muster über mehrere zeilen/spalten?
ich denke das müsste gehen indem ich alles in eine zeile schreibe und dann per regexp abfrage, zwischen x und y koordinaten kann ich dann ja unterscheiden indem ich per m[8*y+x] darauf zugreife und die koordinaten kann ich bestimmen indem ich die position durch 8 teile und der rest is dann der x wert.
allerdings ist mir nicht klar wie ich die regexp pattern so verändere das ich alle positionen ordentlich abfrage und das ganze für unterschiedlich große muster
ich hoffe mir kann da jemand helfen
hab den selben thread auch im python forum: http://www.python-forum.de/topic-19028.html
Quutamo
Full Member
Montag, 1. Juni 2009, 01:48
hallo,
Ich würde es so machen.
Du führst zwei boolische variablen pro matrix element ein. (X und Y)
X ist inizialisiert mit 1;
Y ist inizialisiert mit 0;
diese dienen als markierung.
Zusätzlich noch die variable tmp und past welche den typ des elementes haben.
Wenn X des vorgänger true ist, dann prüfe ob TMP == wert von aktuellen element falls ja verknüpfe das Y des vorgängers mit OR true sonst mit false.
Wenn past und das aktuelle elemente gleich sind verknüpst du das X des nachfolgers AND mit true sonst mit false. setze TMP:=past. setze past auf aktuelles element.
rücke eine element weiter(wenn es aus dem definitionsbereich fällt, am anfang der nächsten spalte beginnen) beginne so lange von neuen bis alle elemente untersucht wurden.
Transponiere (zeilen und spalten, vertauschen [bzw. bei mehr dimensionen verschieben, die wegfallende dimension wird dabei zur ersten]) die matrix und spiegle die aktuelle dimension, vorsicht mit den koordinaten dabei (man kann sich das so vorstellen, eine normale transponation ist die matrix gespiegelt um von der oben linken zur unteren rechten ecke, wir wollen aber das es von der rechten oberen zur linken unteren ecke gespiegelt ist). beginne so oft von neuen bis alle dimensionen abgearbeitet wurden, also praktisch zweimal durch gelaufen bist. (also in der regel 2, falls du nicht ganz was spezielles baun willst.
alle elemente mit X==true && Y==true
sind das ergebnis.
weiß net ob ich nen denkfehler drinnen habe oder sontst was. Es ist schon echt spät.
Natürlich musst du noch einbaun ob du überhaupt in definitionsbereich bleibst bei den indizes.
Man kann diesen algorithmus auch noch optimieren in den du dir beim ersten durchgang die position der kanidaten speicherst und nur mehr von diesen aus "parst".
Die komplexität des algorithmus müsste O(spalten*zeilen) betragen, habe dies aber nicht nachgewiesen. Sondern ist nur eine überlegung.
Ich möchte noch ergänzen das Mustererkennung eine hochkomplexe (und angeblich auch schwierger studien zweig) angelegenheit ist. Also nehme ich an das du mit meinen algorithmus nicht weit kommst wenn du ihn wirklich auf hochauflösende "bilder" anwenden willst. Aber dann solltest du doch lieber einschlägige literatur dazu lesen.
Ich würde es so machen.
Du führst zwei boolische variablen pro matrix element ein. (X und Y)
X ist inizialisiert mit 1;
Y ist inizialisiert mit 0;
diese dienen als markierung.
Zusätzlich noch die variable tmp und past welche den typ des elementes haben.
Wenn X des vorgänger true ist, dann prüfe ob TMP == wert von aktuellen element falls ja verknüpfe das Y des vorgängers mit OR true sonst mit false.
Wenn past und das aktuelle elemente gleich sind verknüpst du das X des nachfolgers AND mit true sonst mit false. setze TMP:=past. setze past auf aktuelles element.
rücke eine element weiter(wenn es aus dem definitionsbereich fällt, am anfang der nächsten spalte beginnen) beginne so lange von neuen bis alle elemente untersucht wurden.
Transponiere (zeilen und spalten, vertauschen [bzw. bei mehr dimensionen verschieben, die wegfallende dimension wird dabei zur ersten]) die matrix und spiegle die aktuelle dimension, vorsicht mit den koordinaten dabei (man kann sich das so vorstellen, eine normale transponation ist die matrix gespiegelt um von der oben linken zur unteren rechten ecke, wir wollen aber das es von der rechten oberen zur linken unteren ecke gespiegelt ist). beginne so oft von neuen bis alle dimensionen abgearbeitet wurden, also praktisch zweimal durch gelaufen bist. (also in der regel 2, falls du nicht ganz was spezielles baun willst
.alle elemente mit X==true && Y==true
sind das ergebnis.
weiß net ob ich nen denkfehler drinnen habe oder sontst was. Es ist schon echt spät.
Natürlich musst du noch einbaun ob du überhaupt in definitionsbereich bleibst bei den indizes.
Man kann diesen algorithmus auch noch optimieren in den du dir beim ersten durchgang die position der kanidaten speicherst und nur mehr von diesen aus "parst".
Die komplexität des algorithmus müsste O(spalten*zeilen) betragen, habe dies aber nicht nachgewiesen. Sondern ist nur eine überlegung.
Ich möchte noch ergänzen das Mustererkennung eine hochkomplexe (und angeblich auch schwierger studien zweig) angelegenheit ist. Also nehme ich an das du mit meinen algorithmus nicht weit kommst wenn du ihn wirklich auf hochauflösende "bilder" anwenden willst. Aber dann solltest du doch lieber einschlägige literatur dazu lesen.
elbarto`
God
Montag, 1. Juni 2009, 23:22
danke für deine bemühungen, allerdings hab ich das mitlerweile schon gelöst 
als basis dient das was mir der eine da im python forum geschrieben hat, daraus is dann letztendlich das geworden:
geht bestimmt noch irgendwie schöner, aber erfüllt seinen zweck
ich übergebe halt zwei listen, die eine enthält alle werte die überein stimmen müssen, die andere halt die wo nur einer übereinstimmen muss
die beiden listen erzeuge ich halt vorher indem ich alle "?", "x" und "y" in meinem muster suche, und dann die koordinaten von "?" als basis benutze für die "x" und "y" werte benutze, also ich das einfach abziehe
als basis dient das was mir der eine da im python forum geschrieben hat, daraus is dann letztendlich das geworden:
|
|
Quellcode |
1 2 3 4 5 6 7 8 9 10 11 |
def search(self, lx, ly):
m = self.data
for y in range(2, len(m)-2)[::-1]:
for x in range(2, len(m[0])-2)[::-1]:
a = m[y + lx[0][1]][x + lx[0][0]]
vy = [m[y + j][x + i] for i, j in ly]
if (all(a == m[y + j][x + i] for i, j in lx[1:]) and (a in vy)):
sw = map(operator.add, (x, y), ly[vy.index(a)])
ds = ['0','z']
if m[y][x] not in ds and m[sw[1]][sw[0]] not in ds:
return (x-2, y-2),map(operator.sub, tuple(sw), (2,2))
|
geht bestimmt noch irgendwie schöner, aber erfüllt seinen zweck
ich übergebe halt zwei listen, die eine enthält alle werte die überein stimmen müssen, die andere halt die wo nur einer übereinstimmen muss
die beiden listen erzeuge ich halt vorher indem ich alle "?", "x" und "y" in meinem muster suche, und dann die koordinaten von "?" als basis benutze für die "x" und "y" werte benutze, also ich das einfach abziehe
Quutamo
Full Member
Dienstag, 2. Juni 2009, 02:11
hallo,
Keine sorge. Ich habe das hauptsächlich für mich gepostet
. So etwas fasziniert mich einfach und da ich alles was ich nicht niederschreibe nach paar tagen schon wieder vergessen habe dachte ich poste es auch gleich hier. So lange es funktioniert und das Ergbnis in akzeptabler Zeit vorhanden ist, wer will da mehr?
Was mich interessieren würde, wofür brauchst du das denn?
Achja, ich bin schon froh das mir mal jemand normal zurückschreibt und nicht gleich indirekt beleidigend wird, was hier in diesen forum anscheinend geduldet wird.
lg,
Quutamo
Keine sorge. Ich habe das hauptsächlich für mich gepostet
. So etwas fasziniert mich einfach und da ich alles was ich nicht niederschreibe nach paar tagen schon wieder vergessen habe dachte ich poste es auch gleich hier. So lange es funktioniert und das Ergbnis in akzeptabler Zeit vorhanden ist, wer will da mehr?Was mich interessieren würde, wofür brauchst du das denn?
Achja, ich bin schon froh das mir mal jemand normal zurückschreibt und nicht gleich indirekt beleidigend wird, was hier in diesen forum anscheinend geduldet wird.
lg,
Quutamo
Ähnliche Themen
-
Software, allgemein »-
Ein Paar Fragen zu Visual Basic
(4. März 2008, 18:19)
-
- Software, allgemein »
-
Python und SQL, Hilfe gesucht
(21. Mai 2006, 10:55)
-
- Software, allgemein »
-
python/sql: datenbank dynamisch erweitern ?
(15. März 2006, 15:54)