Hallo zusammen,
momentan sitze ich an einer Library, die ganz simple "ImageSearch"-Sachen können soll. Das heißt ich gebe der Library ein Bild im RGB-Bitmap-Format, die Library parsed dieses Bild, indem sie es in seine Bestandteile zerlegt und Meta-Informationen speichert (ala Höhe/Breite/Farbmasken/etc.).
Anschließend kann man der Library ein zweites Bild geben und dann soll das zweite Bild in dem ersten Bild (welches normalerweise viel größer ist) gefunden werden.
Das exakte Finde klappt einwandfrei (auch performancetechnisch).
Bisher ist implementiert:
ImageSearch, PixelSearch, allerlei Helferfunktionen (wie preprocessPicture, getPixel, etc.)
Sowohl ImageSearch als auch PixelSearch laufen (wie bereits erwähnt) super von der Geschwindigkeit.
Jetzt will ich aber noch eine 3. Methode hinzufügen, ich habe sie "FindSimilarImage" genannt. Diese Methode sucht in dem Hauptbild nach einem Bereich, der einem zweitem gegebenen Bild sehr ähnlich ist.
Ähnlich ist das Bild und der Bereich für mich, wenn folgende Anforderungen erfüllt werden:
- Die Größe der Objekte stimmt ganz grob überein
- Die benutzten Farben stimmen ungefähr überein
Mehr prüfe ich gar nicht und möchte ich auch nicht wirklich prüfen lassen.
Es ist also relativ einfach (vom Gefühl her), aber irgendwie auch nicht.
Mein momentaner Ansatz sieht wie folgt aus (Konkreter Code folgt weiter unten):
1. Erstelle ein 3D-Histogramm des kleinen Bildes, mit einer Größe von 8 bins pro Farbkanals (also insgesamt 8*8*8=512 bins)
2. currentX=0, currentY=0
3. Berechne für Pixel currentX, currentY des großen Bildes die angrenzende Region und berechne das Histogramm dieser Region
4. Vergleiche das Histogramm des Bereiches (vom großen Bild) mit dem des kleinen Bildes, mit Hilfe der Hellinger Distanz.
5. Gehe zum nächsten Pixel (und springe zu Punkt 3, solange wie Pixel verfügbar sind)
Die Genauigkeit dieses Verfahrens ist sogar besser als ich erwartet hatte, für meinen konkreten Anwendungsfall habe ich 0% false positive und ich erkenne rund 95% der Bilder, die auch für mich als Mensch "ähnlich" sind.
Das große Problem an der ganzen Sache ist die Performance.
Ich brauche für das Suchen einer 30x30 Region in einem 1680x1050 (=Screenshot) Bild 15 Sekunden.
Angestrebte Zeit wäre aber um die 100ms (je weniger desto besser) gewesen.
Jeden Pixel anzuschauen, ist also nicht die Lösung und selbst wenn ich nur jeden 3. Pixel anschauen brauche ich immer noch 5 Sekunden. Bei jedem 30. Pixel wären es immer noch 500ms und zusätzlich würde ich etliche ähnliche Bilder "verpassen".
Pseudo/C++ Code von diese Methode sieht wie folgt aus:
Der Ansatz oben beschrieben sähe also in Pseudo-Code etwa so aus:
Deshalb habe ich einmal meine tiefsten KI-Kentnisse ausgepackt und eine Partikelschwarmoptimierung draufgehauen.
Am Anfang war die Begeisterung groß, die benötigte Zeit lag irgendwo bei 50-100ms (je nachdem wie genau man es wollte) und es wurden beim ersten Test auch etliche Bilder als gut erkannt (bisschen mehr als 80%). Die 80% sind zwar nicht perfekt, aber wäre gerade so noch verschmerzbar.
Beim zweiten Bild kam dann aber die Ernüchterung:
Ein großes Problem, welches ich da sehr früh gemerkt habe war, dass meine Partikel verdammt häufig in lokalen Optima stecken bleiben. Wieso sie das tun, ist auch sehr schnell klar. Es gibt einfach 1000+ mögliche lokale Optima bei meiner Bildersuche und meine Partikel haben kaum eine Chance aus den lokalen Optima auszubrechen, weil wenn ein Bildbereich ungefähr mit dem gesuchten Bild übereinstimmt, dann ist sehr sehr unwahrscheinlich, dass in der Nähe von dem ähnlichen Bereich sich irgendwo ein neues Optimum befindet. Das heißt zwischen den Optimas liegen extrem große Spitzen von schlechten Lösungen, welche die Partikel ungern überwinden, weil es dort ja wieder schlechter wird.
Will man sich das anschaulich klar machen, dürfte das in etwa so aussehen, wobei die große "Spitze" im Bild mein gesuchtes Optimum ist und der Rest nur lokale Optima sind:
[Only registered and activated users can see links. Click Here To Register...]
Ein zusätzliches Problem ist, dass meine Partikel sich nur um das Optimum herumfliegen, es jedoch nicht (mit 500 Iterationen und 120 Partikeln) erreichen. Das heißt sagen wir die perfekte Ähnlichkeit in Prozent ausgedrückt wären 80%, meine Partikel nähern sich den 80% aber nur bis auf rund 70% (manchmal sogar noch weniger) an. Das finde ich sehr schade und ich weiß nicht wieso.
Daher habe ich 3 Fragen, die relativ unabhängig voneinander sind:
Ich möchte keinerlei (wirklich keinerlei!) externe Libaries benutzen. Das heißt weder OpenCV, noch irgendwelche Image-Manipulation-Libs noch sonstiges. Alles was im C++11 Standard jedoch vorkommt benutze ich sehr gerne.
momentan sitze ich an einer Library, die ganz simple "ImageSearch"-Sachen können soll. Das heißt ich gebe der Library ein Bild im RGB-Bitmap-Format, die Library parsed dieses Bild, indem sie es in seine Bestandteile zerlegt und Meta-Informationen speichert (ala Höhe/Breite/Farbmasken/etc.).
Anschließend kann man der Library ein zweites Bild geben und dann soll das zweite Bild in dem ersten Bild (welches normalerweise viel größer ist) gefunden werden.
Das exakte Finde klappt einwandfrei (auch performancetechnisch).
Bisher ist implementiert:
ImageSearch, PixelSearch, allerlei Helferfunktionen (wie preprocessPicture, getPixel, etc.)
Sowohl ImageSearch als auch PixelSearch laufen (wie bereits erwähnt) super von der Geschwindigkeit.
Jetzt will ich aber noch eine 3. Methode hinzufügen, ich habe sie "FindSimilarImage" genannt. Diese Methode sucht in dem Hauptbild nach einem Bereich, der einem zweitem gegebenen Bild sehr ähnlich ist.
Ähnlich ist das Bild und der Bereich für mich, wenn folgende Anforderungen erfüllt werden:
- Die Größe der Objekte stimmt ganz grob überein
- Die benutzten Farben stimmen ungefähr überein
Mehr prüfe ich gar nicht und möchte ich auch nicht wirklich prüfen lassen.
Es ist also relativ einfach (vom Gefühl her), aber irgendwie auch nicht.
Mein momentaner Ansatz sieht wie folgt aus (Konkreter Code folgt weiter unten):
1. Erstelle ein 3D-Histogramm des kleinen Bildes, mit einer Größe von 8 bins pro Farbkanals (also insgesamt 8*8*8=512 bins)
2. currentX=0, currentY=0
3. Berechne für Pixel currentX, currentY des großen Bildes die angrenzende Region und berechne das Histogramm dieser Region
4. Vergleiche das Histogramm des Bereiches (vom großen Bild) mit dem des kleinen Bildes, mit Hilfe der Hellinger Distanz.
5. Gehe zum nächsten Pixel (und springe zu Punkt 3, solange wie Pixel verfügbar sind)
Die Genauigkeit dieses Verfahrens ist sogar besser als ich erwartet hatte, für meinen konkreten Anwendungsfall habe ich 0% false positive und ich erkenne rund 95% der Bilder, die auch für mich als Mensch "ähnlich" sind.
Das große Problem an der ganzen Sache ist die Performance.
Ich brauche für das Suchen einer 30x30 Region in einem 1680x1050 (=Screenshot) Bild 15 Sekunden.
Angestrebte Zeit wäre aber um die 100ms (je weniger desto besser) gewesen.
Jeden Pixel anzuschauen, ist also nicht die Lösung und selbst wenn ich nur jeden 3. Pixel anschauen brauche ich immer noch 5 Sekunden. Bei jedem 30. Pixel wären es immer noch 500ms und zusätzlich würde ich etliche ähnliche Bilder "verpassen".
Pseudo/C++ Code von diese Methode sieht wie folgt aus:
PHP Code:
void Image::calcHistogram(int accuracy,int xStart, int yStart, int w, int h)
{
// histogram ist ein std::vector
histogram.resize(sizeOfHistogram);
int toShift=8-histogramAccuracy;
int blueShift=histogramAccuracy+histogramAccuracy;
for(int y=yStart;y<yStart+h;y++)
{
for(int x=xStart;x<xStart+w;x++)
{
// Berechne in welchen bin die Farbe des Pixels einzuordnen ist
Pixel* p=getPixel(x,y);
int redBins=p->color.red>>toShift;
int greenBins=(p->color.green>>toShift)<<histogramAccuracy;
int blueBins=(p->color.blue>>toShift)<<blueShift;
histogram[redBins + greenBins + blueBins]++;
}
}
float sampledPixels=w*h;
// Teile der Hellinger Distanz hier rein verlagert, damit es an anderen Stellen schneller geht
for(int i=0;i<sizeOfHistogram;i++)
{
if(histogram[i]!=0)
{
histogram[i]=sqrt(histogram[i]/sampledPixels);
}
}
}
float Image::checkHistogramDifferences(Image& checkImage)
{
int sizeOfHistogram=((1<<histogramAccuracy)<<histogramAccuracy)<<histogramAccuracy;
// use Hellinger distance to calculate differences of 2 given datasets
float differences=0.0;
for(int i=0;i<sizeOfHistogram;i++)
{
float squareRootDif=histogram[i] - checkImage.histogram[i];
squareRootDif*=squareRootDif;
differences+=squareRootDif;
}
differences=sqrt(differences)/SQUARE_OF_2;
return differences;
}
PHP Code:
for(int y=0;y<height;y++)
{
for(int x=0;x<width+w;x++)
{
calcHistogram(accuracy,x,y,widthOfSmallImage,heightOfSmallImage);
currSolution=checkHistogramDifferences(checkImage);
updateOldSolutionIfBetter(currSolution);
}
}
Am Anfang war die Begeisterung groß, die benötigte Zeit lag irgendwo bei 50-100ms (je nachdem wie genau man es wollte) und es wurden beim ersten Test auch etliche Bilder als gut erkannt (bisschen mehr als 80%). Die 80% sind zwar nicht perfekt, aber wäre gerade so noch verschmerzbar.
Beim zweiten Bild kam dann aber die Ernüchterung:
Ein großes Problem, welches ich da sehr früh gemerkt habe war, dass meine Partikel verdammt häufig in lokalen Optima stecken bleiben. Wieso sie das tun, ist auch sehr schnell klar. Es gibt einfach 1000+ mögliche lokale Optima bei meiner Bildersuche und meine Partikel haben kaum eine Chance aus den lokalen Optima auszubrechen, weil wenn ein Bildbereich ungefähr mit dem gesuchten Bild übereinstimmt, dann ist sehr sehr unwahrscheinlich, dass in der Nähe von dem ähnlichen Bereich sich irgendwo ein neues Optimum befindet. Das heißt zwischen den Optimas liegen extrem große Spitzen von schlechten Lösungen, welche die Partikel ungern überwinden, weil es dort ja wieder schlechter wird.
Will man sich das anschaulich klar machen, dürfte das in etwa so aussehen, wobei die große "Spitze" im Bild mein gesuchtes Optimum ist und der Rest nur lokale Optima sind:
[Only registered and activated users can see links. Click Here To Register...]
Ein zusätzliches Problem ist, dass meine Partikel sich nur um das Optimum herumfliegen, es jedoch nicht (mit 500 Iterationen und 120 Partikeln) erreichen. Das heißt sagen wir die perfekte Ähnlichkeit in Prozent ausgedrückt wären 80%, meine Partikel nähern sich den 80% aber nur bis auf rund 70% (manchmal sogar noch weniger) an. Das finde ich sehr schade und ich weiß nicht wieso.
Daher habe ich 3 Fragen, die relativ unabhängig voneinander sind:
P.S. Partikel-Schwarm-Optimierungs-Code:Quote:
1. Kennt ihr andere Optimierungsalgorithmen, die mit solchen Suchen in sehr zerklüfteten Landschaften besser klarkommen?
2. Kennt ihr eine (von der Performance-Seite aus gesehen!) einfache Möglichkeit mein Partikelschwarm aus den lokalen Optima raus zu manövrieren (Bisher getestet, jedoch ohne nennenswerten Erfolg: Multi-Schwarm-System und Neugruppieren der Schwärme (DMS-PSO))?
3. Kennt ihr andere Methoden, die genau so leicht wie Histogram zu implementieren sind, ungefähr genau so präzise sind, aber dafür deutlich schneller ablaufen?
Ich möchte keinerlei (wirklich keinerlei!) externe Libaries benutzen. Das heißt weder OpenCV, noch irgendwelche Image-Manipulation-Libs noch sonstiges. Alles was im C++11 Standard jedoch vorkommt benutze ich sehr gerne.
