Die Ausführung des optimalen Flutfüllens auf einem Raster unter der Bedingung, dass nur nicht überlappende Quadrate erlaubt sind.

Question

Ich muss ein Gitter optimieren, indem ich die Anzahl der "Elemente" darin nehme und so weit wie möglich minimiere. Wenn ich von Element spreche, meine ich einen Abschnitt innerhalb dieses Rasters. Hier ist im Wesentlichen, wie "Eingabe" visuell aussehen könnte:

Die erste Lösung, die mir einfällt, wäre ein Flutfüllalgorithmus, jedoch habe ich eine Einschränkung: Alle Elemente müssen 4 Seiten haben, alle Elemente müssen also rechteckig sein.

Mein erster, begrenzter Ansatz bestand einfach darin, durch das Eingabegitter Element für Element zu iterieren und zu überprüfen, ob das zuletzt neu erstellte Element die gleiche Farbe hatte und die gleiche Transparenz wie das Element aufwies, das erstellt werden sollte - wenn dies der Fall war, wurde anstelle des Erstellens des neuen Elements einfach das letzte Element neu dimensioniert, um um 1 Block weiter nach unten zu reichen.

Hier ist ein Pseudo-Code-Beispiel dessen, was ich tue:

Element-Ausgabearray();
Element letztes_element = null;

for (int x = 0; x < rasterbreite; x++) {
    for (int y = 0; y < rasterhöhe; y++) {
        Farbe aktuelle_eingabefarbe = eingabegitter(x, y);

        if (letztes_element && letztes_element.x === x && letztes_element.farbe === aktuelle_eingabefarbe) {
            letztes_element.span_y++;
        } else {
            letztes_element = element_erstellen(
                x,                   // element.x      (die x-Koordinate des links oben im Gitter befindlichen Elements)
                y,                   // element.y      (die y-Koordinate des links oben im Gitter befindlichen Elements)
                1,                   // element.span_x (die Anzahl der Elemente, die auf der x-Achse überspannt werden)
                1,                   // element.span_y (die Anzahl der Elemente, die auf der y-Achse überspannt werden)
                aktuelle_eingabefarbe   // element.farbe
            );

            ausgabearray.anhängen(letztes_element);
        }
    }
}

Als Ergebnis erhalte ich dies (vorausgesetzt, ich gebe das vorherige Raster ein):

Also habe ich in diesem speziellen Fall die Anzahl der Elemente von 64 auf 20 reduziert.

Das ist gut, aber meine "Eingabegitter" sind normalerweise nicht 8x8. Ein Beispiel für ein realistischeres Eingabegitter führt vor der Optimierung zu 10201 Elementen (mit meiner derzeitigen Methode) und nachher zu 957.

Da diese Methode offensichtlich stark von der Struktur des Gitters selbst abhängt, können diese Zahlen stark variieren. Mein Ziel ist es, die Elemente für jedes gegebene Eingabegitter so weit wie möglich zu minimieren.

Derzeit gehe ich es von einer Richtung aus an (vertikale Optimierung), aber ich würde es auch gerne horizontal optimieren. Ein Ergebnis einer solchen Operation muss nicht perfekt sein, aber hier ist, wie ich mir das optimale Endgitter für das erste Eingabegitter vorstelle:

In diesem Fall wird die Anzahl der Elemente von 20 auf nur 14 reduziert - was bei meinen größeren Gittern sehr hilfreich sein könnte.

Ich scheine einfach nicht daran zu denken, einen Füllalgorithmus in einer Weise zu nutzen, die es mir ermöglicht, für jeden Platz in dem Eingabegitter zu berücksichtigen und alle resultierenden Elemente rechteckig / 4-seitig zu halten.

Ich dachte, ich könnte es wahrscheinlich erzwingen, und obwohl die CPU-Auslastung / Geschwindigkeit nicht das größte Anliegen ist, muss ich dies auf sehr großen Gittern mit Tausenden von Elementen ausführen, also Ressourcen verschwenden, um etwas auf so großer Skala zu erzwingen, ist einfach nicht realistisch - denke ich.

Answer 1

Gareth Rees hat eine sehr gute Antwort auf diese Frage veröffentlicht, die David Eppsteins Antwort bei Math Overflow erweitert und mehrere Autoren zitiert. In einem Satz besteht der Algorithmus, der optimale Lösungen liefert, darin, zunächst einen maximal nicht überschneidenden Satz von Linien zwischen konkaven Ecken zu ziehen (in polynomieller Zeit mit dem maximal unabhängigen Satz in einem bipartiten Graphen zu finden) und dann diese Schnitte gierig zu verlängern, so dass die verbleibenden Flächen Rechtecke sind.

Das Finden eines maximalen unabhängigen Satzes in einem bipartiten Graphen erfordert einen maximalen Matching-Algorithmus. Wenn dies zu viel Arbeit ist, dann ist allein der gierige Schritt, bei dem von jeder konkaven Ecke ein vertikaler Schnitt gemacht wird, eine 2-Approximation.

Answer 2

Je nach Anwendung können Sie dies möglicherweise mit Wavelets lösen. Denken Sie an Ihr 2D-Array als Graustufenbild, das Ziel ist es, es zu komprimieren, indem Sie es in rechteckige Funktionen zerlegen (z. B. Haar-Wavelets) und dann die Funktionen verwerfen, die zur Darstellung feiner Details verwendet wurden. Angesichts der von Ihnen bisher gezeigten Daten (dh keine Geräusche oder Texturen) müssen Sie nach der Durchführung der Wavelet-Transformation tatsächlich nichts verwerfen.

In Python können Sie http://www.pybytes.com/pywavelets/ verwenden,

import pywt
import numpy as np
import matplotlib.pyplot as plt
import Image

img = Image.open('Desktop/b12nI.png')

plt.imshow(img, cmap='gray')

Führen Sie eine diskrete Wavelet-Transformation der einzigen Ebene durch:

coeffs = pywt.dwt2(img, 'haar')
cA, (cH, cV, cD) = coeffs

Der cA enthält die Haar-Wavelet-Koeffizienten, die für die Approximation verwendet werden. Die Approximation ist auf Ihre Daten genau, wir können dies überprüfen, indem wir die inverse Transformation der Approximationskoeffizienten durchführen:

recon = pywt.idwt2(coeffs,'haar')
np.max(np.abs(recon - img))

ergibt 1,4210854715202004e-14

Zum Vergleich, wenn wir versuchen würden, Rauschen mit Haar-Wavelets zu approximieren:

noise = np.random.randn(512,512)
cA, (cH, cV, cD) = pywt.dwt2(noise, 'haar')
recon = pywt.idwt2(coeffs,'haar')
np.max(np.abs(noise-recon))

ergibt: 213,31090340487393

Berechnungsmäßig sind Wavelet-Transformationen O(n).

Java-Code für Wavelet-Transformationen finden Sie hier: https://en.wikipedia.org/wiki/Discrete_wavelet_transform

Weitere Informationen: http://gtwavelet.bme.gatech.edu/wp/kidsA.pdf