Bild / "am ähnlichsten pixel" Suchoptimierung?

Beantworten Sie meine eigene Frage.

Kurze Antwort: Ich konnte den Alphakanal löschen, also habe ich beschlossen, Bildpyramiden zu verwenden (siehe Pyramide und Gaußsche Pyramide im Netz). Es gab eine enorme Geschwindigkeitsverbesserung.

Lange Antwort:

Mein erstes Ziel war die Textur-Synthese. Alpha wurde zum Erzeugen von Pixeln verwendet, die noch nicht gefüllt waren, und B repräsentierte einen Teil des bereits erzeugten Bildes. (D.h. A war ein Mustermuster und B wurde ein Bild erzeugt)

Nach ein wenig Recherche habe ich festgestellt, dass es entweder keine schnelle Möglichkeit gibt, im N-dimensionalen Raum zu suchen (zum Beispiel ist 3x3 Pixel im Grunde ein 24-Komponenten-Vektor, ausgenommen 7x7 Pixel) 144-Komponente sein, Suche nach einem solchen Bereich wird 24-dimensionale oder 144-dimensionale Suche). Nun, es gibt Wege (zum Beispiel Papier genannt " I-COLLIDE: ein interaktives und genaues Kollisionserkennungssystem für große Skalierungsumgebungen "verwendet 3 sortierte Arrays (die jeweils nach verschiedenen Dimensionen sortiert sind), um die 3-dimensionale Suche durchzuführen), aber sie funktionieren offensichtlich besser für Floats und eine geringere Anzahl von Dimensionen.

Der Vorschlag, Bewegungserkennung zu verwenden, war nicht sinnvoll, weil Bewegungserkennung (wie es scheint) davon ausgeht, dass Pixel bewegte Objekte darstellen (in meinem Fall nicht), und zumindest einige Optimierungen davon abhängen.

Am Ende habe ich ein Papier namens " Fast Texture Synthesis mit baumstrukturierter Vektorquantisierung "(Li-Yi Wei, Marc Levoy, Universität Stanford), die eine Technik verwendet, die auf einem Algorithmus basiert, der dem von mir verwendeten ähnlich ist. Das zu durchsuchende Bild wird mehrmals verkleinert (ähnlich wie bei der Erzeugung von Mip-Maps), wobei die Suche zuerst auf der niedrigsten Ebene und dann auf der nächsten Ebene durchgeführt wird. Es ist möglicherweise nicht der beste Weg, um tatsächliche Bildsuche für andere Anwendungen zu tun, aber es ist perfekt für meine Zwecke. Das Papier ist relativ alt, aber es funktioniert für mich.

Das gleiche Papier erwähnt einige Techniken, um die Suche noch weiter zu beschleunigen. Einer von ihnen ist "Tree-strukturierte Vektor-Quantisierung (TSVQ)", obwohl ich nicht mehr Informationen darüber geben kann (habe es nicht überprüft - aktuelle Textur-Generator funktioniert mit akzeptabler Geschwindigkeit auf meiner Hardware, so werde ich wahrscheinlich nicht schauen in weitere Optimierungen).

Sie sollten sich die Bewegungsschätzung ansehen, die bei der Videocodierung verwendet wird, um den Ort eines Blocks in einem zuvor codierten Bild zu finden, das dem zu codierenden Block am ähnlichsten ist.

(HINWEIS: Ich habe nicht genug Reputation, um zwei Links zu veröffentlichen, also musst du in Wikipedia nach Bewegungsschätzung suchen).

Einige einfache Block-Matching-Algorithmen finden Sie hier . Diese arbeiten, indem sie nur eine Teilmenge von Punkten im Suchbereich analysieren.

Wenn Sie den spezifischen Punkt finden möchten, der Ihre Abgleichfunktion minimiert, müssen Sie eine vollständige Suche durchführen. Full-Search-Beschleunigung wird normalerweise durch vorzeitige Beendigung erreicht - Beenden der Bewertung eines Punktes, wenn es bereits unmöglich ist, das vorherige beste Ergebnis zu verbessern.

Eine vorzeitige Beendigung ist auch nützlich, wenn nur eine Teilmenge von Suchpunkten untersucht wird, obwohl die Beschleunigung nicht so groß ist wie bei der vollständigen Suche.

Sie können versuchen, eine ungefähre Lösung zu finden: Patch-Match

  

In diesem Whitepaper werden interaktive Bildbearbeitungstools vorgestellt, die einen neuen randomisierten Algorithmus verwenden, um schnell die nächsten Übereinstimmungen zwischen benachbarten Bildern zu finden. Frühere Recherchen in den Bereichen Grafik und Bildverarbeitung nutzten die Suche nach dem nächsten Nachbarn, um eine Vielzahl hochwertiger digitaler Bildbearbeitungswerkzeuge bereitzustellen. Die Kosten der Berechnung eines Feldes solcher Übereinstimmungen für ein gesamtes Bild sind jedoch früheren Bemühungen zur Bereitstellung einer interaktiven Leistung entgangen. Unser Algorithmus bietet erhebliche Leistungsverbesserungen gegenüber dem Stand der Technik (20-100x) und ermöglicht seinen Einsatz in interaktiven Bearbeitungswerkzeugen.

Eine mögliche Beschleunigung könnte darin bestehen, binäre Operatoren zu verwenden. Zum Beispiel könnten Sie durch A XOR B für nachfolgende überlappende Regionen von A marschieren. Die resultierende Region, deren Werte 0 am nächsten kommen, wäre der Teil von A, der B am ähnlichsten ist. Wenn Sie die Alphamaske berücksichtigen mussten, nehmen Sie an Die Alpha-Maske von A ist alles 1s und enthält sie in der XOR- 32 Bits pro Pixel anstelle von 24.

Ich würde in Betracht ziehen, den frühen Unterschied in die innere Schleife zu verschieben, so dass er kurz vor der inneren Schleife kurzgeschlossen werden kann, wenn der Fehler bereits zu groß ist. Ihr Trading-ifs für einige schwere Mathematik. Der Pixel-Skalierungswert für den Fehler könnte auch eine Multiplikation statt einer Division sein (geringfügig bei neuen Maschinen).

Jede Möglichkeit, mehrere Pixel gleichzeitig zu lesen oder parallel zu verarbeiten?

Beim Threading könnten Sie Threads für jede externe Schleife für die Schleifeniteration starten (indem Sie die Anzahl der Threads auflösen, die Sie verwenden möchten), damit Ihre CPUs effizienter arbeiten können. Das Synchronisieren des maximalen Fehlers wäre das einzige Problem - was erreicht werden könnte, indem die Fehler in einer externen Tabelle gespeichert und am Ende verglichen werden, um Speicherkonflikte zu vermeiden.

Caching Ihrer Strukturen, um loszuwerden - & gt; 's kann helfen, aber der Compiler macht das normalerweise für Sie.

Nur ein paar Gedanken zu Beginn. Sieht immer noch ...

PDiff ist ein Open-Source-Bilddifferenz-Tool, das vielleicht einige hilfreiche Techniken für Sie hat.