Ich arbeite an einem Seitenprojekt, das ein Quellbild akzeptiert und dann ein Fotomosaik mit einer Reihe von verfügbaren Thumbnail-Bildern erstellt. Ich habe eine Implementierung, die OK funktioniert (siehe unten), aber ich stehe gegen "große O" Probleme, die versuchen, die Anzahl der verfügbaren Bilder für Ersatz zu erhöhen.Algorithmus zur Reduzierung der Anzahl von Vergleichen zur Berechnung der Chi-Quadrat-Distanz zwischen Histogrammen?
Der Prozess, den ich zur Zeit bin mit ist die folgende:
- ich Bilder zu 1000x1000
- Scale-up das Quellbild für alle verfügbaren Ersatz 4 Eimer RGB-Farb Histogramme vorbestellt berechnet erstellen 20x20 "Kacheln" aus dem skalierten Quellbild und 4 Bucket-RGB-Histogramme für jede Kachel erstellen
- Für jede Kachel die Chi-Quadrat-Distanz für jedes der verfügbaren Ersatzbilder berechnen
- Für jede Fliese, wählen Sie das Ersatzbild mit dem kleinsten Chi-Quadrat-Abstand
So konkret das Problem, das ich in als die Anzahl der verfügbaren Ersatzbilder erhöht sich die Anzahl der Vergleiche exponentiell wächst renne. Ich teste gerade mit 25.000 verfügbaren Ersatzbildern und es dauert fast 10 Minuten, um das endgültige Bild über 4 Kerne auf meinem Laptop zu erzeugen.
Meine Frage ist, gibt es einen Ansatz, den ich verwenden kann, um zu vermeiden, dass die Anzahl der Entfernungsberechnungen exponentiell wächst?
Eine Idee, die ich hatte, war die Berechnung der Abstände zwischen den einzelnen "Kacheln", sie in einige N Gruppen zu trennen, ein durchschnittliches Histogramm innerhalb der Gruppe zu finden und dann die nächsten K verfügbaren Bilder zum durchschnittlichen Histogramm zu finden. Von dort würde ich zurückgehen und die besten Übereinstimmungen für die Kacheln in jeder Gruppe berechnen, aber von einer kleineren Quelle der K nächsten Bilder.
Irgendwelche Gedanken darüber, was eine gute "Projektion" zu schätzen wäre wäre? Ich hatte dies ursprünglich implementiert, indem ich die (r, g, b) -Werte der Thumbnails gemittelt und die euklidischen Abstände zwischen den Kacheln und Thumbnails minimiert hatte, aber das Ergebnis war merklich schlechter als die Chi-Quadrat-Abstände der Histogramme. –
@AshishDatta Die Idee ist es, die Durchschnittswerte (r, g, b) zu verwenden, um Kandidaten zu eliminieren, die wahrscheinlich nicht gut zueinander passen. Auf diese Weise vergeuden Sie keine Zeit mit der Berechnung des Chi-Quadrat-Werts einer schwarzen Kachel gegen eine weiße Kachel. Es kann sich lohnen, eine Abweichung über eine Kachel zu berechnen.Wenn Sie beispielsweise feststellen können, dass die Zielkachel eine geringe Varianz aufweist und meist rot ist, können Sie wahrscheinlich nur aus diesen beiden Kriterien einen guten Kandidaten finden. Mit hoher Varianz möchten Sie wahrscheinlich eine Reihe von Kandidaten ausprobieren. –
Mal sehen. Durchschnittliches R, G, B kann gut arbeiten. Sie können auch die Durchschnittswerte für jeden Quadranten hinzufügen. Je mehr Projektionen Sie hinzufügen, desto langsamer werden die Dinge. Fügen Sie genug hinzu und Sie erstellen Ihren aktuellen Algorithmus neu. Auch ich warf "Best 50" als Vermutung aus. Je größer du das machst, desto wahrscheinlicher ist es, die beste Antwort zu erhalten. – btilly