For Schleifen reduzieren / beschleunigen?

TheGrudge

Hi,

ich habe hier ein Programm, das Bilder miteinander vergleicht (deren Fingerabdrücke) und einen Score berechnet, um zu erkennen, wie ähnlich sich die Bilder sind.
Bei einer kleinen Bildermenge ist das alles kein Problem, 2000-3000 Bilder werden in knapp 30 Sekunden abgehandelt.

Nun habe ich aber eine andere Testkollektion mit 50.000 Bildern. Hier dauert mir das Suchen nach doppelten / ähnlichen Bildern viel zu lange.

Ich versuche nun die For-Schleifen zu reduzieren, im Moment habe ich
50.000*50.000*3*40 = 3 *10^11 Schleifendurchläufe, die sind in ungefähr 20 Minuten abgehandelt.

Ich habe schon ein wenig optimiert und konnte den ursprünglichen Algorithmus von 75 Minuten bei der kleinen Bildermenge (2500) auf wie gesagt 30 Sekunden drücken, aber nun weiß ich nicht, wie ich es noch beschleunigen könnte.

Damit ich doppelte und ähnliche Bilder finden kann, muss ich leider jedes Bild mit jedem vergleichen, daran führt kein Weg vorbei.

In diesem Fall wären das also 50.000^2 Schleifendurchläufe. Der Rest der obigen Rechnung (*3*40) sind die Kanäle der Bilder (3) und die Anzahl der Koeffizienten (40), diese kann ich leider auch nicht verringern.

Meine Frage ist nun, ob ich vielleicht die Schleifen an sich irgendwie aufteilen oder beschleunigen kann?
Wie gesagt ich denke nicht das ich die Anzahl verringern kann, aber gibt es vielleicht irgendwelche Techniken in C++, welche die Verarbeitung ein wenig beschleunigen können?

theta

Ev. parallisierung mit einer Threading library (z.B. OpenMP, ...).
Simon

Dravere

TheGrudge schrieb:

Damit ich doppelte und ähnliche Bilder finden kann, muss ich leider jedes Bild mit jedem vergleichen, daran führt kein Weg vorbei.

Bist du sicher? Sobald ein Bild ein wenig mehr passt als ein anderes, hat man eine Art von Sortierkriterium. Mit diesem Kriterium kann man einen Sortieralgorithmus bauen, welcher schneller laufen sollte.
Ein Sortierkriterium muss nicht unbedingt ein dimensional sein, dass heisst, da können mehrere Parameter dazugehören. Dadurch gibt es dann eine Art von räumlicher Einordnung.

Hier eine Auflistung von Sortieralgorithmen:
http://de.wikipedia.org/wiki/Sortieralgorithmen

TheGrudge schrieb:

Wie gesagt ich denke nicht das ich die Anzahl verringern kann, aber gibt es vielleicht irgendwelche Techniken in C++, welche die Verarbeitung ein wenig beschleunigen können?

Hast du dem Kompiler mitgeteilt, dass er optimieren soll? Zum Teil kann man bei der Optimierungen noch weitere Feineinstellungen machen, welche du aber bei der Dokumentation zum Kompiler nachschlagen solltest.

Grüssli

TheGrudge

Hmm ja wäre eine Möglichkeit.
Ich hatte auch schon mal daran gedacht, einmal die ganze Geschichte zu berechnen und das in einer Tabelle in der Datenbank hinterlegen.

Aber
1. hat das man Sqlite3 gesprengt
2. Muss ich dann bei jeder Bildänderung den Fingerprint UND diese gigantische Cachetabelle updaten.

Vielleicht gehe ich einfach den Weg des geringsten Widerstands und baue eine exclude Funktion in das Programm ein, so das man bestimmte Bildpfade einfach auslassen kann. Somit reduziert sich die Anzahl der Schleifen ja auch.

(Achso bei dem Programm handelt es sich um digiKam (www.digikam.org), eine Bildverwaltungs-Software.)

Wenn man Fotos in der Datenbank hinterlegt, kann man ja nachher eventuell ausschließen, wo keine doppelten / ähnlichen Fotos vorkommen können.
Dennoch wäre es natürlich schöner, einfach die komplette Datenbank zu durchsuchen, gerade wenn man ähnliche Fotos sucht.

TheGrudge

Dravere schrieb:

Hast du dem Kompiler mitgeteilt, dass er optimieren soll? Zum Teil kann man bei der Optimierungen noch weitere Feineinstellungen machen, welche du aber bei der Dokumentation zum Kompiler nachschlagen solltest.

Ja habe ich auch schon probiert, war nicht sonderlich erfolgreich.
Danke für den Link, mal schauen ob ich da eventuell was passendes finden kann.
Aber eigentlich denke ich schon, das ich jedes mit jedem vergleichen muss.

Der Algorithmus ist dazu da, eine Auflistung zurückzugeben, mit Bildern die sich ähnlich sind.
Ein Rückgabewert wäre quasi folgendes:

1 - 2 10 789
2 - 7 8 1908
3 - 12
200 - 102 45 66 4 567 33

Sprich ich bekomme einen Index und die dazugehörigen Bilder, die diesem Bild ähnlich sind.
Um sowas aber festzustellen, muss ich doch jedes mit jedem vergleichen, oder nicht?

Naja werde mal den Link durchforsten

volkard

TheGrudge schrieb:

Damit ich doppelte und ähnliche Bilder finden kann, muss ich leider jedes Bild mit jedem vergleichen, daran führt kein Weg vorbei.

ok. aber wäre es eine gute idee, die bilder erstmal um faktor 100 zu verkleinern und auf den verkleinerten bildern immer einen hundermal schnelleren vorvergleich zu machen, und nur ernsthaft zu vergleichen, wenn der vorvergleich nicht total daneben lag?

Shade Of Mine

TheGrudge schrieb:

Um sowas aber festzustellen, muss ich doch jedes mit jedem vergleichen, oder nicht?

Nicht unbedingt. Wenn A unähnlich zu B ist, und B ähnlich zu C musst du uU die ähnlichkeit A zu C garnicht testen. Dazu brauchst du aber eine Datenbank oder etwas ähnliches.

Parallelisierung bietet sich hier aber an, da der vergleich 2er Bilder keine seiteneffekte hat. du kannst also perfekt parallelisieren.

ansonsten wirkt cachen auch wunder.

TheGrudge

Sowas mache ich ja schon

Wenn A 90% ähnlich ist mit C, dann prüfe ich C gar nicht gegen A (die Rechnung ist ein wenig grob im ersten Post).
Da man aber meist kaum Bilder hat, die 90% Ähnlichkeit aufweisen (90% ist sehr hoch, da muss zum Beispiel eine Person schon den Kopf genauso geneigt haben, wie im Referenz Bild, eventuell schielt sie nach links oder hat das eine Auge zu, dann dürfte das noch 90% Ähnlichkeit werden).

Wenn du eine Datenbank von einem professionellen Studiofotographen nimmst, der nur Portrait-Serien macht, dann ist mein Algorithmus schnell durch Aber bei normalen "Knipser"-Datenbanken sieht das anders aus. Da habe ich vielleicht am Ende 100 ähnliche Bilder, die restlichen 49.900 Bilder sind aber unähnlich. Somit kann ich dann auch leider keine großartige Optimierung durch Auslassen von Checks hervorrufen.

TheGrudge

Shade Of Mine schrieb:

Nicht unbedingt. Wenn A unähnlich zu B ist, und B ähnlich zu C musst du uU die ähnlichkeit A zu C garnicht testen. Dazu brauchst du aber eine Datenbank oder etwas ähnliches.

Hmm das muss ich nochmal genauer prüfen, könnte sogar klappen. Aber ich glaube sowas habe ich schon mal versucht, mit dem Ergebnis, das keine ähnlichen Bilder mehr geliefert wurden.
Muss das Ganze nochmal überdenken...

Edit: Ok im Grunde könnte das es noch ein wenig beschleunigen, aber wie gesagt dann brauche ich viele ähnliche Bilder, oder sehe ich das falsch? Wenn ich nur 1% ähnliche Bilder in der 50.000er Datenbank habe, dann kann das doch auch nicht viel reduzieren. Oder doch?

TheGrudge

Ich merke gerade das ich ein wichtiges Kriterium vergessen habe. Ich optimiere bis jetzt folgendermaßen (also stimmt die Rechnung oben gar nicht):

Bei jedem Schleifendurchlauf reduziere ich die Anzahl der zu prüfenden Bilder um 1.

Sprich wenn die Schleife zu zweiten Mal durchläuft, prüfe ich nur noch gegen die Bilder 2-50.000. Bei der dritten Schleife 3-50.000 usw.
Denn wenn Bild 1 keine Ähnlichkeiten aufweisen konnte, brauchen alle anderen Bilder auch nicht gegen 1 getestet werden. Ebenso nehme ich alle Ähnlichen zu Bild 1 und speichere sie in einer Map, wenn sie 90% oder mehr Ähnlichkeit aufweisen. Diese Map wird dann vor Schleifeneintritt gegen die aktuelle Schleifen-Zahl geprüft (Schleifenzahl = Key), wobei die Values aus der Überprüfung herausgenommen werden (aber nur temporär, da sie für andere Bilder wieder wichtig sein könnten).
Also ist meine Schleife wohl eher 50.000! * 3 * 40...? Oje, Mathe
Das ist übrigens die Optimierung, die den alten Algorithmus von 75 Minuten auf 30 Sekunden beschleunigte, bei einer kleinen Datenbank.

Dennoch dauert das bei einer großen Bildermenge noch zu lange. Aber ich denke einfach wenn eine Bilderdatenbank wenig Ähnlichkeiten aufweist, komme ich einfach nicht mehr schneller hin.
Da muss ich wohl mit Threads arbeiten.

knivil

50.000*50.000*3*40 = 3 *10^11 ... bei der kleinen Bildermenge (2500) auf wie gesagt 30 Sekunden drücken

Hmm, 2500 auf 50.000 ist also ein Faktor um 400. Also wuerde es etwa 3 Stunden 20 Minuten dauern ... Sind ja auch eine Menge Daten, also auch Ok. Parallelisierung bietet sich hier an. Auch wirst du keine weitere Beschleunigung durch die Optimierung der Schleifen erhalten. Fuer Wunder musst du dich an jemand anderes wenden.

Noch eine Frage: Ist der Score symmetrisch? Wenn ja brachst du nur etwa n*(n-1)/2 Bilder testen.

TheGrudge

Ja wie oben beschrieben, ich habe ja schon Optimierungen vorgenommen.
Also dauert es keine 3 Stunden (das war früher so), sondern nur noch 20 Minuten (oder eventuell auch weniger, so genau habe ich das nicht gemessen).
Da die Scores symetrisch sind, kann ich die Schleifenanzahl bei jedem Durchlauf um 1 reduzieren, und, bei ähnlichen Bildern, eventuell um mehr.

Wie gesagt bei vielen ähnlcihen Bildern ist es sehr schnell.
Ich hatte mal aus Spaß die Hälfte der Bilder verkleinert und um 1° rotiert, und somit eine Datenbank erzeugt, die wirklich in knapp 20 Sekunden durchgelaufen ist, obwohl es ja 50.000 Bilder waren.

Wenn die Bilder aber kaum Ähnlichkeiten aufweisen, werde ich wohl nicht mehr optimieren können.

Ok, danke für eure Antworten. Ich denke ich werde einfach eine Exclude-Funktion einbauen, wenn es einem mal zu lange dauern sollte, kann er Verzeichnisse aus der Suche komplett rausnehmen. Das Ergebnis ist dann zwar nicht ganz akkurat, aber damit muss man wohl leben.

Wenn man alles tot-optimieren könnte, bräuchten wir ja nicht immer schnellere Rechner

zeusosc

Shade Of Mine schrieb:

TheGrudge schrieb:

Um sowas aber festzustellen, muss ich doch jedes mit jedem vergleichen, oder nicht?

Nicht unbedingt. Wenn A unähnlich zu B ist, und B ähnlich zu C musst du uU die ähnlichkeit A zu C garnicht testen. Dazu brauchst du aber eine Datenbank oder etwas ähnliches.

Parallelisierung bietet sich hier aber an, da der vergleich 2er Bilder keine seiteneffekte hat. du kannst also perfekt parallelisieren.

ansonsten wirkt cachen auch wunder.

Joa,..

ich würde die Datenbank als Algebraische Äquivalenzrelation aufbauen,
die eigenschaften der reflexivität, symmetrie und wie im Zitat schon erwähnt die transitivität ausnutzen.

Dabei ist es aber erforderlich, das die Bilder globale, bzw. nach verallgemeinerten erkennungsmerkmalen gescanned werden, die von den anderen Bildern unabhängig sind. Haben ein oder mehrere Bilder gewisse ähnlichkeiten bzgl. eines spezifischen merkmals, kannst Du diese ja in Äquivalenzklassen packen. So muss jedes Bild nur einmal überprüft werden, die relationen untereinander kann dann unabhängig von allen Bildern stattfinden.

Grüüße