Moin, nehmen wir einen binären Rastercode, wie zum Beispiel einen QR-Code. Zumindest unter bestimmten Umständen ist es möglich, so zu codieren, dass jeder beliebige (rechteckige) Ausschnitt mit einer gewissen Mindestgröße eindeutig ist, also im Muster nicht nochmal vorkommt. Hat das ganze einen Namen? Unter welchen Begriffen findet man was dazu? Wie erstellt man so ein Muster? Als Beispiel (0 schwarz, 1 weiß) das Muster: 10001 11001 11011 10011 10010 Wenn man jetzt zum Beispiel den 3x3-Ausschnitt 001 011 011 bekommt, ist eindeutig bestimmbar, dass dessen obere linke Ecke in der zweiten Zeile und dritten Spalte des Ausgangsmusters liegt. Das gilt entsprechend für jeden anderen 3x3-Ausschnitt. Allerdings ist das Erstellen größerer Muster nicht trivial, weil sich die Ausschnitte überlappen können.
Dussel schrieb: > Hat das ganze einen Namen? Unter welchen Begriffen > findet man was dazu? Meine Antwort passt nicht zu 100%, aber ich würde mal im Umfeld "Pseudozufallszahlen", "Korrelationssignale", "Korrelationsfolgen", "Korrelationsarrays" suchen. Folgen bzw. Arrays ohne sich wiederholende Teilmuster sind i.d.R. gute Kandidaten für Signale mit einer guten Autokorrelationsfunktion.
Dussel schrieb: > Hat das ganze einen Namen? > Unter welchen Begriffen findet man was dazu? > Wie erstellt man so ein Muster? ? Redundanz? Selbstähnlichkeit? ?scharfes Hingucken? Faltung?
Grummler schrieb: > Dussel schrieb: > >> Hat das ganze einen Namen? Unter welchen Begriffen >> findet man was dazu? > > Meine Antwort passt nicht zu 100%, aber ich würde mal > im Umfeld "Pseudozufallszahlen", "Korrelationssignale", > "Korrelationsfolgen", "Korrelationsarrays" suchen. > > Folgen bzw. Arrays ohne sich wiederholende Teilmuster > sind i.d.R. gute Kandidaten für Signale mit einer > guten Autokorrelationsfunktion. Pseudozufall habe ich direkt verworfen, weil das ja mit der gesuchten Eigenschaft nichts zu tun hat (das Muster kann grundsätzlich auch total vorhersehbar sein), aber Korrelation ist ein interessanter Gedanke. Badende Pythia schrieb: > Redundanz? Selbstähnlichkeit? > ?scharfes Hingucken? Faltung? Faltung eventuell im Bezug auf die Korrelation, aber die anderen Vorschläge? Vom Gefühl her haben die wenig mit der Fragestellung zu tun. Fabian schrieb: > Hammingdistanz? Ja, die Hammingdistanz der Ausschnitte zueinander müssen paarweise größer als 0 sein. Danke für die Vorschläge. Vielleicht kennt ja noch jemand einen Begriff dazu. Auch im eindimensionalen würde das schon eventuell etwas bringen.
Dussel schrieb: > Badende Pythia schrieb: >> Redundanz? Selbstähnlichkeit? >> ?scharfes Hingucken? Faltung? > Faltung eventuell im Bezug auf die Korrelation, aber die anderen > Vorschläge? Vom Gefühl her haben die wenig mit der Fragestellung zu tun. Na wenn dein Gefühl Dich nicht weiter führt, mußt Du halt den Verstand einschalten. Redundanz meint hier, das die selbe Information/Muster mehrmals vorkommt, also gerade das Gegenteil des von dir geschilderten Falles. Du suchst also einen QR-Code ohne diese Redundanz. Redundanz, also mehrmaliges Vorkommen, bedeudet auch abschnittsweise "Selbstähnlichkeit", die man eben durch Faltung, oder auch (Auto-) Korrelation ermittelt. https://www.spektrum.de/lexikon/biologie/autokorrelation/6405 Ein Indiz für geringe Redundanz ist hohe Komprimierungsrate. Du könntest also eine Huffmann-Codierung über den QR-Code laufen lassen um zu schauen, ob das ganze im geforderten Sinne frei von Duplikaten ist. Mglw. ist der von dir gesuchte Algo für QR-Codes ohne Wiederholung ähnlich dem Huffman-Tree aus der Komprimierung. Nur das eben kein Pfad vom Stamm zu den Blättern gleich gewählt wird: https://commons.wikimedia.org/wiki/File:Huffman_tree_2.svg https://en.wikipedia.org/wiki/Huffman_coding
"Maximum Length Sequence" geht zumindest in die gesuchte Richtung.
Badende Pythia schrieb: > Redundanz meint hier, das die selbe Information/Muster mehrmals > vorkommt, […] > Redundanz, also mehrmaliges Vorkommen, Ok, in dem Sinne könnte es passen. Ich dachte an Redundanz im allgemeinen Sinn. Badende Pythia schrieb: > Ein Indiz für geringe Redundanz ist hohe Komprimierungsrate. Ist es nicht umegekehrt? Bei hoher Redundanz kann viel weggelassen werden, was zu einer hohen Komprimierungsrate führt. Allgemein ist das größere Problem auch nicht das Prüfen eines Musters auf die geforderte Eigenschaft, sondern das Erzeugen des Musters. Tom schrieb: > Maximum Length Sequence Das könnte auch ein Ansatz sein. Vielen Dank für die Vorschläge.
Ich vermute mal, es geht um absolute Positionierung in der Ebene (z.B. ne Maus, die ausgibt, wo sie sich auf dem Mauspad befindet). Keine Ahnung, ob es dafür einen Namen gibt. Aber ein interessantes Problem, wenn der Ausschnitt klein ist (wenn er, bezogen auf die möglichen Positionen, groß ist, reicht schon ein Rauschmuster). Für ein 5x5 Feld reicht ein 2x2 Ausschnitt, um alle möglichen Positionen eindeutig zu markieren (5x5 ergibt 4x4=16 mögliche Positionen, ein 2x2 Ausschnitt ermöglicht 2^(2*2)=16 Kodierungen, passt exakt). Gibt es überhaupt Lösungen? Ein QnD-Programm (brute force) zeigt, es gibt sogar 800 Lösungen (hätt ich nicht erwartet). Eine davon:
1 | 10101 |
2 | 00111 |
3 | 11001 |
4 | 11000 |
5 | 10101 |
Ich vermute, dass es einen (rekursiven) Algorithmus gibt, um zumindest eine Untermenge aller Lösungen, auch für größere Felder generieren zu können. Bleibt dem Leser überlassen ;-)
foobar schrieb: > Ich vermute mal, es geht um absolute Positionierung in der Ebene Richtig. :-) foobar schrieb: > Aber ein interessantes Problem, > wenn der Ausschnitt klein ist (wenn er, bezogen auf die möglichen > Positionen, groß ist, reicht schon ein Rauschmuster). Genau, aber meine Mathekenntnisse (im Sinne von Beweisen und sowas) sind zu gering. Da es aber interessant ist, könnte ich mir vorstellen, dass sich jemand schonmal mit sowas beschäftigt hat. foobar schrieb: > Für ein 5x5 Feld reicht ein 2x2 Ausschnitt, um alle möglichen Positionen > eindeutig zu markieren (5x5 ergibt 4x4=16 mögliche Positionen, ein 2x2 > Ausschnitt ermöglicht 2^(2*2)=16 Kodierungen, passt exakt). Das ist die Frage. Können alle 16 Codierungen benutzt werden, ohne dass es Doppelungen gibt? Es könnte ja auch sein, dass eine Untergrenze gibt, die wegen der notwendigen Überlappung die nutzbaren Codierungen einschränkt. Wenn sich die Ausschnitte nicht überlappen könnten, wäre es in der Tat trivial. foobar schrieb: > Ein QnD-Programm (brute force) zeigt, es gibt sogar > 800 Lösungen (hätt ich nicht erwartet). 2^(5*5) ist mehr als 33 Millionen. Das heißt, nur 0,0024 % der möglichen Muster erfüllen die Bedingung. So gesehen sind 800 mögliche Lösungen sogar sehr wenig.
Auf die Schnelle war mir Gestern der Algorithmenbereich "Pattern Matching" eingefallen, den ja "jeder" auch als String-Matching etc. kennt. Ich hatte mal ein Buch zu diesem Thema ausgeliehen, in dem im hinteren Teil auch 2D-Bereichsverfahren vorgestellt wurden, die gar nicht mal so kompliziert waren (Erkennen von Mustern als auch Erstellen von Automaten aus vorgegebenen Mustern). Vlt. hift das ja. Da aber JEDER Ausschnitt einer best. Grösse nur einmal vorkommen darf, müssten ja viele Automaten erstellt und angewendet werden. Hm, klingt aber sehr aufwendig? Ein anderer Ansatz: Du fängst mit einem beliebigen Muster der Grösse k,k in (i,j)=(0,0) an. Eine Bewegung nach Rechts (i=>i+1) bzw. nach Unten (j=>j+1) bewirkt ja das Schiften der Bits nach Links bzw. nach Oben plus das Ergänzen um k Bits Rechts bzw. Unten. Eine diagonale Bewegung (i=>i+1, j=>j+1) ergibt sich damit als Bewegung nach Links und dann nach Unten oder erst nach Unten und dann nach Rechts. Beide Folgen müssen dann dasselbe Muster erzeugen. Durch einfache Überlegung/Skizze wird schnell klar, dass damit nur 2*k+1 Bits als Freiheit für eine konsistente Diagonalbewegung gegeben sind. Daraus ergeben sich aber noch lange nicht, wie die Bits zu setzen sind, es ist aber ein doch sehr einfaches Verfahren. Als Ansatz zum Ausfüllen der gesamten Fläche würde ich hier wegen der Breite (= Anzahl neuzusetzender Bits) eher Tiefen- als Breitensuche verwenden. Je Schritt muss dann das aktuelle Muster mit den schon gegebenen Mustern verglichen und bei Ungleichheit entsprechend abgespeichert und den Tiefensuchpfad fortsetzen bzw. bei Gleichheit den Tiefensuchpfad zurückgesetzt werden. Zum Abspeichern würde ich eine Graphenstruktur wählen. Hast du dann per Tiefensuche einen "Gewinner" gefunden, dann kannst du im nächsten Versuch so weit im Graph zurückgehen, bis eine Stelle gefunden ist, in der beim Bitsetzen noch Wahlfreiheit besteht. Setze ein Bit neu und schreite mit der Tiefensuche fort etc. So bekommt man alle Muster. Ah, und noch eine Erkenntnis: Hast du eine minimale Mustergrösse festgelegt und einen QR-Code/oÄ gefunden, dann sich Vergleiche mit grösseren Mustern überfüssig, nicht aber mit kleineren! Aber ich denke mal, dass die Bestimmung der min. Mustergrösse nur über ein wie z.B. Oben vorgestelltes Verfahren bestimmen lässt.
Sigi schrieb: > Da aber JEDER Ausschnitt einer best. Grösse nur einmal > vorkommen darf, müssten ja viele Automaten erstellt und > angewendet werden. Hm, klingt aber sehr aufwendig? Ich hatte gehofft, dass es einen einfachen Algorithmus gibt, aber ich denke inzwischen, dass es den nicht gibt. Sigi schrieb: > Daraus ergeben sich aber noch lange nicht, > wie die Bits zu setzen sind, es ist aber ein doch sehr > einfaches Verfahren. Vielleicht einfach, durch die erforderliche Suche trotzdem rechenzeitintensiv. Die Überlegungen sind interssant. Danke.
Angehängte Dateien:
-
deBruijn_256-256-4-4.png
1,3 KB
Hallo, am ehesten passt wohl ein 2-dimensionaler deBruijn-Torus. Das gewünschte Muster könnte man dann "deBruijn-Rechteck" nennen. Der Torus erfüllt mehr Bedingungen als das Rechteckt; jeder dB-Torus ist also auch ein dB-Rechteck, aber nicht unbedingt umgekehrt. https://en.wikipedia.org/wiki/De_Bruijn_torus Um aus dem Rechteck einen (topologischen 2-)Torus zu erhalten, verklebt man untere mit oberer Kante des Rechtecks sowie linke Kante mit der rechten. Ein (X,Y;x,y) dB-Torus ist dann ein X×Y 2-Torus, in dem jedes x×y Teil-Rechteck höchstens 1× vorkommt. Zum Beispiel ist ein (4,4;2,2) dB-Torus:
1 | 0100 |
2 | 0111 |
3 | 1110 |
4 | 0010 |
es gibt 2^(2·2) = 16 Teil-Rechtecke, und alle sind verschieden. Die Eigenschaft, ein (X,X;x,x) dB-Toris zu sein, ist invariant unter Invertierung, sowie unter Spiegelungen und 90°-Rotatonen sofern diese den Torus auf sich selbst abbilden. Auf Wikipedia ist die SVG-Grafik eines (256,256;4,4) dB-Torus. Das SVG hab ich mal in ein 256×256 PNG umgewandelt (und gesestet, dass es sich wirklich um einen solchen dB-Torus handelt). Grafik anbei.
Johann L. schrieb: > Auf Wikipedia ist die SVG-Grafik eines (256,256;4,4) dB-Torus. Das SVG > hab ich mal in ein 256×256 PNG umgewandelt (und gesestet, dass es sich > wirklich um einen solchen dB-Torus handelt). Grafik anbei. ...falls man direkten Zugriff auf die Pixel-Werte haben möchte ohne aufwändige Grafik-Libs zu nutzen, kann man PNG zum Beispiel nach PBM umwandeln mit
1 | > convert xxx.png -compress none yyy.pbm |
Das resultierende PBM ist eine reine Textdatei (zu lange, um sie hier zu posten). "convert" ist Teil von ImageMagick: https://imagemagick.org/ Hier die Matrix als Text: https://pastebin.com/tkiNzrdL
:
Bearbeitet durch User
Artikel zur Konstruktion hab ich keine gefunden, zumindest keine frei einsehbaren. Allerdings gibt es ein Projekt auf Github, das Python-Scripte zur Konstruktion hat; insbesondere auch das Verfahren von Shiu, auf dem die obige Grafik basiert: https://github.com/man4/debruijn-torus
de Bruijn Array/Torus ist zumindest ein guter Suchbegriff für das Problem des TO. Unter anderem findet man "Coding Schemes for Two-Dimensional Position Sensing"[1]. Allen ist aber gemein, dass sie sehr mathematisch gehalten sind - da jeder Author sich seine eigene mathematische DSL[2] bastelt, ist das Lesen echt mühsam. [1] https://hplabs.itcs.hp.com/techreports/92/HPL-92-19.pdf [2] Domain Specific Language
Dussel schrieb: > Wie erstellt man so ein Muster? Johann L. schrieb: > Allerdings gibt es ein Projekt auf Github, das Python-Scripte > zur Konstruktion hat Ich denke mal, wenn Dir quadratische Ausschnitte bis zur Mindestgröße 6 * 6 ausreichen, dann ist das von Johann L. gefundene GitHub-Projekt schon alles was Du brauchst, denn das liefert Dir Beispiel-Skripte, um ein 4096 * 8192 Raster, das alle möglichen 5 * 5 Muster genau einmal enthält sowie auch eines mit allen möglichen 6 * 6 Mustern (ergibt dann ein Raster aus 262144 * 262144 Punkten und wird 8GiB groß) zu erzeugen. Das Beispiel-Skript ließe sich auch einfach für 7*7 Muster aufbohren, falls Du noch größere Raster haben willst und mal eben 64TiB auf der Platte frei hast. Für noch größeres bräuchtest Du dann aber so richtig viel Platz: das Raster für 8*8 Muster hätte 4294967296² Punkte und käme auf gigantische 2EiB (2.30584*10^18 Byte), womit auch die meisten gängigen Dateisysteme (ntfs wie auch ext4) überfordert wären; zfs wäre noch im Rennen. ;) Nachdem Deine Anforderungen schwächer sind als die eines de Bruijn Arrays (Dir reicht ja daß, jedes Muster max. einmal enthalten ist statt genau einmal), kannst Du auch beliebige, kleinere Ausschnitte des jeweiligen de Bruijn Arrays (für 4*4, 5*5 oder 6*6 Muster) nehmen. Zumindest für rechteckige Muster der Größe n * (n-1) sollten sich die Beispielskripte auch recht einfach anpassen lassen, denn die werden, wenn ich das richtig gesehen habe, ohnehin immer als Zwischenschritt erzeugt, um von n*n auf (n+1)*(n+1) zu kommen. Dussel schrieb: > foobar schrieb: >> Ich vermute mal, es geht um absolute Positionierung in der >> Ebene > Richtig. :-) In dem Fall solltest Du Dir vielleicht mal folgendes Paper anschauen: https://link.springer.com/article/10.1134/S1990478919020091 Das beschäftigt sich lt. Abstract mit der Erstellung von de Bruijn Arrays, bei denen sich die Position eines gegebenen Musters im Array leicht ermitteln läßt. Denn bei Mustern größer 4*4 wird wahrscheinlich eine naive brute-force Suche doch schnell langweilig werden.
Vielen Dank für die vielen zusätzlichen Informationen. De-Bruin-Array(s) sieht/sehen ja in dem Zusammenhang interessant aus. Insbesondere geht es ja sogar noch weiter, was bei der Rotationsinvarianz auch nützlich ist. mIstA schrieb: > Nachdem Deine Anforderungen schwächer sind als die eines de Bruijn > Arrays (Dir reicht ja daß, jedes Muster max. einmal enthalten ist statt > genau einmal) mIstA schrieb: > Das beschäftigt sich lt. Abstract mit der Erstellung von de Bruijn > Arrays, bei denen sich die Position eines gegebenen Musters im Array > leicht ermitteln läßt. > Denn bei Mustern größer 4*4 wird wahrscheinlich eine naive brute-force > Suche doch schnell langweilig werden. Das ist halt immer die Frage, gibt es sowas oder ist man da von der Komplexität schnell aus P (Äquivalenz) raus. Ich werde das mal durchlesen.
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.