Gruppierung in Rechtecke auf einem binären Raster

Question

Ich habe ein binäres Raster, das Texturpixel darstellt, die aktualisiert werden sollen. Die Kosten für das Hochladen dieser Pixel können grob in eine feste (ähnlich einem Header in einem Protokoll) und einen dynamischen Teil aufgeteilt werden, der durch die Upload-Größe bestimmt wird. Beide sind systemabhängig, können aber gemessen werden.

Dies bedeutet, dass die Kosten für jedes Rechteck anfallen, in dem die Fixkosten (der Transferaufwand) immer gleich sind.

Die Kostenfunktion selbst kann von System zu System variieren; In den meisten Fällen wird es am besten durch eine lineare Funktion wie eine Liniengleichung angenähert, z. cost_per_rectangle = fixed_costs + dynamic_costs rectangle_size, oder kurz c = f + s * d. Aber es kann gut sein, dass diese Funktion logarithmisch oder exponentiell wird, wie c = f + s * log (d) oder c = f + s * d^(1 + etwas).

Hier einige reale Welt Messungen sind, aufgetragen in einem linearen und ein y-log-Diagramm mit Größen von 2 bis 1 M, wobei X die Anzahl der Punkte und Y der Zeit in uns ist:

Ich suche nach einem Algorithmus, der Rechtecke berechnen kann, die alle für die Aktualisierung markierten Zellen abdecken und dabei die Gesamtkosten minimieren.

Die Rechtecke können sich überlappen.

Weil die Kosten für die Berechnung dieser Rechtecke die Gesamtkosten ausmachen, suche ich nach einem effizienten, aber nicht perfekten Algorithmus, obwohl es sehr schön wäre, von der perfekten Lösung zu hören und ob sie NP-fähig ist oder nicht .

Im Moment habe ich keine Ahnung, wie ich das am besten angehen soll, nur ein vages Gefühl, dass vielleicht kd-Bäume helfen könnten.

Hier sind einige Bilder von möglichen Ergebnissen für ein Beispiel Raster:

ich mit dem diagonalen Beispiel einige Versuch und Irrtum-Tests haben und gefunden eine optimale Rechteckgröße für das Diagonalbeispiel durch Vergleichen der Upload-Zeiten für alle möglichen Größen.

Answer 1

Angenommen, jemand hat viele Rechtecke über Ihr Bild gezeichnet, wobei Rechtecke in Rechtecke geschachtelt sind, aber keine zwei Rechtecke überlappen. Sie könnten die dynamische Programmierung für Bäume verwenden, um eine Teilmenge von Rechtecken zu bestimmen, die alle Zellen abdeckt, die für die Aktualisierung markiert sind. Stellen Sie sich die Verschachtelung als Baumstruktur vor. Arbeiten Sie von oben nach unten und berechnen Sie die minimalen Kosten für jeden Knoten, um alle Zellen abzudecken, die unter diesem Knoten für die Aktualisierung markiert sind: entweder die Summe der von den Kindern dieses Knotens berechneten Kosten oder die Kosten des zugeordneten einzelnen Rechtecks dieser Knoten - welcher auch immer der kleinste ist. (In der Tat können Sie dieses einzelne Rechteck verkleinern, wenn Zellen nicht in der Nähe ihrer Kanten aktualisiert werden müssen)

Wie erhält man eine gute Baumstruktur? Zwei kommen mir in den Sinn. Eine ist die Quad-Tree-Dekomposition, die rekursiv jedes große Rechteck in vier kleinere teilt und dann diese kleineren zerteilt und so weiter.Der andere wäre, einen minimalen Spannbaum der Zellen zu bilden, die aktualisiert werden müssen, wahrscheinlich unter Verwendung der Manhattan-Distanz, und diese Baumstruktur als Baum von Rechtecken zu verwenden, wobei jeder Knoten ein Rechteck gerade groß genug hat, um die Begrenzungsbox für seine Nachkommen zu sein .