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.
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.
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.
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.
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.svghttps://en.wikipedia.org/wiki/Huffman_coding
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 ;-)
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.
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.
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.
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.
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.
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.
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).
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:
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.
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 77 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 88 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 44, 55 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 nn auf (n+1)(n+1) zu kommen.
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.
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)
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.
