Optimierung Bildvergleichs Algorithmus

Shadow992 · 11/25/2015, 21:33

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:

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;
}

Der Ansatz oben beschrieben sähe also in Pseudo-Code etwa so aus:

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);
        }
    }

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:

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:

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?

P.S. Partikel-Schwarm-Optimierungs-Code:

Spoiler

PHP Code:



float Image::findSimilarImageApproximately(int x, int y,int w, int h,Image& checkImage, int accuracy, int agentsUsed, int iterations,int &bestX, int &bestY)
{
    int widthToCheck=checkImage.width;
    int heightToCheck=checkImage.height;
    if(checkImage.histogramHeight!=checkImage.height || checkImage.histogramWidth!=checkImage.width)
    {
        checkImage.calcHistogram(accuracy,0,0,widthToCheck,heightToCheck);
    }

    std::vector<Agent> agents;
    agents.resize(agentsUsed);

    for(int i=0;i<agentsUsed;i++)
    {
        float r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
        agents[i].x=x+w*r;
        r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
        agents[i].y=y+h*r;
    }

    std::vector<int> bestSwarmX(16,0);
    std::vector<int> bestSwarmY(16,0);
    std::vector<float> bestSwarmFitness(16,1000000000000);

    int xMaxSpeed=10;
    int yMaxSpeed=10;


    int currSwamrIdx=0;
    for(;iterations>0;iterations--)
    {
        for(int i=0;i<agentsUsed;i++)
        {
            currSwamrIdx=i%16;

            // update vectors
            float r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
            agents[i].xSpeed+=2.0*r *((float)(bestSwarmX[currSwamrIdx]-x));
            r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
            agents[i].xSpeed+=2.0*r *((float)(agents[i].bestX-x));
            r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
            agents[i].ySpeed+=2.0*r *((float)(bestSwarmY[currSwamrIdx]-y));
            r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
            agents[i].ySpeed+=2.0*r *((float)(agents[i].bestY-y));

            // calculate fitness
            calcHistogram(accuracy,agents[i].x,agents[i].y,widthToCheck,heightToCheck);
            agents[i].currFitness=checkHistogramDifferences(checkImage);

            if(bestSwarmFitness[currSwamrIdx]>agents[i].currFitness)
            {
                bestSwarmFitness[currSwamrIdx]=agents[i].currFitness;
                bestSwarmX[currSwamrIdx]=agents[i].x;
                bestSwarmY[currSwamrIdx]=agents[i].y;
            }

            if(agents[i].bestFitness>agents[i].currFitness)
            {
                agents[i].bestFitness=agents[i].currFitness;
                agents[i].bestY=agents[i].y;
                agents[i].bestX=agents[i].x;
            }

            // if particles' verctors got too big we have to limit them (so our particle will not move too far and overjump good solutions)
            if(agents[i].ySpeed>yMaxSpeed)
                agents[i].ySpeed=yMaxSpeed;
            if(agents[i].ySpeed<-yMaxSpeed)
                agents[i].ySpeed=-yMaxSpeed;

            if(agents[i].xSpeed>xMaxSpeed)
                agents[i].xSpeed=xMaxSpeed;
            if(agents[i].xSpeed<-xMaxSpeed)
                agents[i].xSpeed=-xMaxSpeed;

            // Add our vectors to current position
            agents[i].x+=agents[i].xSpeed;
            agents[i].y+=agents[i].ySpeed;


            // If agent/particle wants to move out of boundaries, just capture him and move him into boundaries
            if(agents[i].x>=w)
                agents[i].x=w-2;

            if(agents[i].y>=h)
                agents[i].y=h-2;

            if(agents[i].x<x)
                agents[i].x=x+1;

            if(agents[i].y<y)
                agents[i].y=y+1;
        }

        if(iterations%64)
        {
            // Group Subswarms new
            for(int j=0;j<8;j++)
            {
                int ran1=rand()%16;
                int ran2=rand()%16;

                float tmpFit=bestSwarmFitness[ran1];
                int tmpX=bestSwarmX[ran1];
                int tmpY=bestSwarmY[ran1];

                bestSwarmFitness[ran1]=bestSwarmFitness[ran2];
                bestSwarmX[ran1]=bestSwarmX[ran2];
                bestSwarmY[ran1]=bestSwarmY[ran2];

                bestSwarmFitness[ran2]=tmpFit;
                bestSwarmX[ran2]=tmpX;
                bestSwarmY[ran2]=tmpY;
            }

        }

        // Make maximum step smaller with more iterations
        if(iterations<(iterations>>4))
        {
            xMaxSpeed=2;
            yMaxSpeed=2;
        }
        if(iterations<(iterations>>3))
        {
            xMaxSpeed=4;
            yMaxSpeed=4;
        }
        else if(iterations<(iterations>>1))
        {
            xMaxSpeed=8;
            yMaxSpeed=8;
        }
    }
    float bestFitness=10000;

    for(int i=0;i<bestSwarmFitness.size();i++)
    {
        if(bestFitness>bestSwarmFitness[i])
        {
            bestFitness=bestSwarmFitness[i];
            bestX=bestSwarmX[i];
            bestY=bestSwarmY[i];
        }
    }

    return bestFitness;
}

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.

.SkyneT. · 11/26/2015, 02:31

Was spricht dagegen einen der Algorithmen von

nachzuprogrammieren?
Diese waren bei mir bisher sehr performant und genau.

(Deinen Code habe ich nur überflogen, falls dort schon einer dieser Algorithmen verwendet wird, vergiss das hier einfach

)

Shadow992 · 11/26/2015, 10:59

Quote:

Originally Posted by .SkyneT.

Was spricht dagegen einen der Algorithmen von nachzuprogrammieren?
Diese waren bei mir bisher sehr performant und genau.

(Deinen Code habe ich nur überflogen, falls dort schon einer dieser Algorithmen verwendet wird, vergiss das hier einfach )

Es ist nicht ganz Template-Matching, sondern eher irgendwas zwischen PixelSearch und TemplateMatching.
Vom Aufwand her, wären die vorgestellten Methoden aber genau so "schwer" wie meine jetzige Lösung (ohne PSO).
Das heißt auch das wird zu langsam sein, da der Aufwand von beiden Methoden (sowohl Template als auch Histogramm) O(n²*m²) (wenn man sagt dass die Bilder beide Quadratisch sind, dann entspricht n=Breite/Höhe Bild1 und m=Breite/Höhe Bild2) ist und es damit immer noch zu langsam wäre. Vielleicht würde es auf Grund von weniger Berechnungen auf 10sec runterbekommen, aber die angestrebten 100ms sinds halt bei weitem noch nicht.

OpenCV dürfte das selbst rasend schnell machen, weill OpenCV die Grafikkarte benutzt und man damit rund 500 Pixel gleichzeitig berechnen kann. Die Grafikkarte wollte ich aber eigentlich nicht benutzen, weil es dann am Ende wieder Grafikkarten-Konflikte gibt, Versionskonflikte, usw.
Außerdem ist es recht witzlos eine Library zu haben, die nur Methoden von anderen Libraries called.

MrDami123 · 11/26/2015, 12:28

Könnte man springen? Wenn x% Übereinstimmung kann xpx weiter nicht xx% Übereinstimmung sein, je nach Größe. Dann wenn xx% Übereinstimmung die genauste Position lokalisieren, nach oben, unten, rechts, links % Zunahme beachten anstatt alles durchzuscannen.
Dann 'besuchten' Bereich mit % speichern und weiter berechnen, ob etwas mit xx% noch nicht gefunden wurde.
Alternativ auch Bereich die bis zu xx% nicht übereinstimmen können direkt überspringen.

Oder je nach Leistung mehrere threads gleichzeitig durchlaufen lassen, von verschiedenen Positionen, die sich gegenseitig Infos austauschen?

Shadow992 · 11/26/2015, 13:47

Quote:

Originally Posted by MrDami123

Könnte man springen? Wenn x% Übereinstimmung kann xpx weiter nicht xx% Übereinstimmung sein, je nach Größe. Dann wenn xx% Übereinstimmung die genauste Position lokalisieren, nach oben, unten, rechts, links % Zunahme beachten anstatt alles durchzuscannen.
Dann 'besuchten' Bereich mit % speichern und weiter berechnen, ob etwas mit xx% noch nicht gefunden wurde.
Alternativ auch Bereich die bis zu xx% nicht übereinstimmen können direkt überspringen.

Oder je nach Leistung mehrere threads gleichzeitig durchlaufen lassen, von verschiedenen Positionen, die sich gegenseitig Infos austauschen?

@Multithreading:
Diese "Optimierung" ist leider schon voll ausgeschöpft, weil ich rund 10 solche Bilder gleichzeitig (in verschiedenen Threads) suchen lasse.

@Springen
Ich kann in dem Bild rumspringen wie ich will.
Tatsächlich gefällt mir deine idee auch enorm gut.
Den zweiten Teil werde ich wohl ziemlich genau so übernehmen (also das mit % Änderung beobachten und in die Richtung weitersuchen).
Der erste Teil hingegen hat ein kleines Problem:
Ich müsste einen Wert festlegen ab welchem mein Bild nicht mehr "ähnlich" genug ist.
Wenn ich diesen Wert fest in meine Methode integriere, dann gibt es aber das Problem, dass ich nicht mehr dem Benutzer der Library überlassen kann, ab wann er eine Übereinstimmung für genug hält.
Manche wollen 90% Übereinstimmung, Anderen reicht 40%.
Aber auch den Parameter zu übergeben finde ich nicht optimal, damit wäre die Lib zwar wieder anpassbarer, aber wenn man die Funktion etwas anders benutzen will und gar keinen Plan hat was für Werte man zu erwarten hat, bietet auch das Probleme.
Ein mögliches Anwendungsgebiet, wäre eine Art "Suche" in X-Bildern, wobei man am Ende das Bild mit der höchten Übereinstimmung haben möchte (selbst wenn es nur 10% sind).

Du hast mich jedoch auf eine sehr gute Idee gebracht, ich werde sie hier nur kurz skizzieren, weil ich bisher noch 0 Zeilen dazu implementiert habe:

Ich weiß, dass Evolutionäre Algorithmen sehr stabil gegnüber lokalen Minima/Maxima sind. Bisher wusste ich nur nicht, wie ich die Evolutionären Algorithmen für mein Problem benutzen kann.
Dein Post hat mir dann aber einen Wink mit dem Zaunpfahl gegeben (bisher alles ungetestet und nur im Kopf zusammengedacht):

Initialisierung:
- Erzeuge X (wahrscheinlich irgendwo zwischen 50 und 200) Individuen, die du zufällig auf dem Bild verteilst und berechne deren Fitness.

Fitnessberechnung:
- Die Berechnung der Fitness passiert ja über "checkHistogramDifferences", je größer die Unterschiede, desto schlechter die Fitness.

Selektionsphase (eine der 3 Möglichkeiten werde ich nehmen, vermutlich Option 3):
1. Bestenselaktion (nur die Y besten Individue überleben)
2. Rangselektion (jedes Individuum hat eine gewisse Chance zu überleben)
3. Kombination aus beidem (die besten Z Individuen überleben immer und der Rest wird nach Wahrscheinlichkeit ausgewählt)

Mutationsphase:
1. Mit 90% Wahrscheinlichkeit: Bewege die Individuen zufällig ein paar Pixel (1px-4px) um ihre aktuelle x,y-Position
2. Mit 10% Wahrscheinlichkeit: Vertausche x und y Koordinate

Rekombinationsphase:
1. Mit 25% Wahrscheinlichkeit: Erzeuge ein komplett neues zufälliges Individuum
2. Mit 25% Wahrscheinlichkeit: Nehme den Mittelpunkt der Strecke von zwei Individuen und erzeuge aus diesem Punkt ein neues Individuum
3. Mit 50% Wahrscheinlichkeit: Erzeuge ein neues Individuum, welches in der Umgebung von einem bestehenden Individuum landet (Umgebung irgendwo Größe 30-60px Radius)

MrDami123 · 11/26/2015, 15:21

Initialisierung:
Anstatt zufällige Positionen anzusteuern, wäre es doch besser die Individuen so zu erzeugen, dass eine mögliche Übereinstimmung immer zu einen %-anteil erkannt wird. Schließlich möchte man ja alles finden also auch mehr als eine Übereinstimmung.
Die Individuen haben die Größe der gesuchten Übereinstimmung.

Dabei ist die nicht überprüfte Stelle zwischen den Individuen nicht größer als die gesuchte Übereinstimmung. Eine Übereinstimmung kann somit auch auf bis zu vier Individuen erkannt werden.

Fitnessberechnung:
Jedes Individuum wird einmal gecheckt und alle mit einem % überleben.

Erkennung:
Das Individuum nährt sich nun dem Optimum.

Könnte man das so machen?

Shadow992 · 11/26/2015, 16:13

Quote:

Originally Posted by MrDami123

Initialisierung:
Anstatt zufällige Positionen anzusteuern, wäre es doch besser die Individuen so zu erzeugen, dass eine mögliche Übereinstimmung immer zu einen %-anteil erkannt wird. Schließlich möchte man ja alles finden also auch mehr als eine Übereinstimmung.
Die Individuen haben die Größe der gesuchten Übereinstimmung.

Dabei ist die nicht überprüfte Stelle zwischen den Individuen nicht größer als die gesuchte Übereinstimmung. Eine Übereinstimmung kann somit auch auf bis zu vier Individuen erkannt werden.

Fitnessberechnung:
Jedes Individuum wird einmal gecheckt und alle mit einem % überleben.

Erkennung:
Das Individuum nährt sich nun dem Optimum.

Könnte man das so machen?

Tatsächlich ist es für das Funktionieren der Evolutionären Algorithmen sehr wichtig einen gewissen Zufall zu besitzen (damit sie sich nicht an lokalen Optima aufhängen).
Deine Idee werde ich aber auch mit einbauen, nur wahrscheinlich etwas anders.
Das Problem was wir bei dieser Methode haben sieht man sehr schön an deinem Bild.

Gehen wir davon aus, dass ein Individuum zu 90% in einem Bereich liegt der sich extrem stark vom vorgegebenen Bild unterscheidet (sagen wir 10% übereinstimmung).
Nur 10% des Bildes stimmen zu mehr als 90% mit dem gegebenen Bild überein (z.B. weil nur eine Ecke reinragt).
Damit ergäbe sich eine Gesamtähnlichkeit von:

Quote:

0.9*0.1+0.1*0.9=0.18

Das ist natürlich eher ein "Ausnahmefall", der Durchschnittsfall dürfte so aussehen:
50% stimmen zu 30% überein und die restlichen 50% stimmen zu 60% überein.
Das heißt unser Bild scheint nicht an dieser Position zu sein, aber etwas, dass eine gewisse Ähnlichkeit hat (was ja auch gut ist, wenn wir keinen relativ perfekten Match finden).
Die Gesamtähnlichkeit wäre dann für den Durchschnittsfall:

Quote:

0.5*0.3+0.5*0.6=0.45

Da das der Durchschnittsfall ist, dürften wir rund 75% solcher Werte zu sehen bekommen.
Behalten wir jetzt nur 50% der besten Individuen (was ein recht üblicher Wert ist), schmeißen wir unseren Ausnahmefall mit 0.18 Haus hoch (und eigentlich immer) raus.

Anschließend werden wir uns hauptsächlich auf die 45% Gemeinsamkeit stürzen und sie vielleicht auf 60% verbessern.
Spätestens ab dann wird es praktisch unmöglich Ausnahmefälle ausreichend genau anzuschauen, um die beste Lösung zu finden.
Wir würden also wieder in etlichen lokalen Optima stecken bleiben und hätten zwar ein recht gutes Ergebnis, das wäre jedoch ähnlich gut/schlecht wie das der Partikel-Schwarm-Optimierung.

Daher wäre eine Rangselektion für diese Methode am besten geeignet, trotzdem kann es passieren, dass eine derartig schlechte Lösung rausfliegt.
Konzentriert man sich jetzt wieder nur auf die guten Lösungen, dann gibt es wieder relativ viele lokale Optima, zwar nicht so viele wie mit der Bestenselektion, aber immer noch genug.
Deswegen ist es wichtig, wenn man derartige Lösungen rausschmeißt ihnen auch wieder eine gewisse Chance fürs reinkommen zu geben.
Völlig nutzlos ist es jedoch nicht und kann helfen die Performance zu verbessern.

Von daher würde ich rein vom Nachdenken her meine bisherige Rekombination in etwa wie folgt anpassen:

Rekombinationsphase:
1. Mit 20% Wahrscheinlichkeit: Erzeuge ein komplett neues zufälliges Individuum
2. Mit 20% Wahrscheinlichkeit: Nehme den Mittelpunkt der Strecke von zwei Individuen und erzeuge aus diesem Punkt ein neues Individuum
3. Mit 40% Wahrscheinlichkeit: Erzeuge ein neues Individuum, welches in der Umgebung von einem bestehenden Individuum landet (Umgebung irgendwo Größe 30-60px Radius)
4. Mit 20% Wahrscheinlichkeit: Nehme den Mittelpunkt der Strecke von zwei Individuen, die nahe beieinander liegen, und erzeuge aus diesem Punkt ein neues Individuum

Wobei man schauen müsste wie einfach/schnell man die "Nähe" von zwei Individuen prüfen kann und ob sich der zusätzliche Berechnungsaufwand lohnt oder ob man die benutzte Zeit dafür lieber in ein paar Individuen/Iterationen stecken sollte.
Dazu kann ich aber gar nichts sagen, rein intuitiv denke ich macht das keinen großen Unterschied, aber es ist trotzdem ausprobierenswert.

MrDami123 · 11/26/2015, 18:37

hmmm... sagen wir mal man erzeugt die Individuen wie in meinem Beispiel, damit man die gesamte Fläche sicher abdeckt und dabei möglichst wenig Individuen erzeugt.

Als nächstes würde ich mittels xpx Annäherung(oben,unten,rechts,links) ermitteln wollen, welche Individuen auf die gleiche Übereinstimmung zeigen und alle bis auf eine fallen lassen.
Da die freie Fläche zwischen den erzeugten Individuen nicht groß genug ist, als das sich dort eine Übereinstimmung verstecken könnte, reicht das ein Individuum mit beliebigem % auf eine Übereinstimmung zeigt.

Nun nährt man sich der Übereinstimmung wieder (o,u,r,l) mit xpx und ermittelt in welche Richtung es geht und wie viel % man mit wie viel px bekommt. Aus dem % und px berechnet man nun einen möglichen Sprung aufs Optimum.
(Man muss hier keine zweite Näherung durchführen und kann die Werte vom vorherigen Schritt nehmen - nur als Erklärung)
Dann kalibriert man sich auf Optimum.

(Ein Individuum kann auch auf zwei oder mehrere zeigen und muss dann vermehrt werden.)

Bin aus den Fingern heraus nicht fähig das zu programmieren, würde mich aber interessieren, welcher Ansatz bei den Tests vielversprechender ist. Finden-Lokalisieren-Algorithmus oder Evolutionärer-Algorithmus.

Shadow992 · 11/26/2015, 19:01

Quote:

Originally Posted by MrDami123

hmmm... sagen wir mal man erzeugt die Individuen wie in meinem Beispiel, damit man die gesamte Fläche sicher abdeckt und dabei möglichst wenig Individuen erzeugt.

Als nächstes würde ich mittels xpx Annäherung(oben,unten,rechts,links) ermitteln wollen, welche Individuen auf die gleiche Übereinstimmung zeigen und alle bis auf eine fallen lassen.
Da die freie Fläche zwischen den erzeugten Individuen nicht groß genug ist, als das sich dort eine Übereinstimmung verstecken könnte, reicht das ein Individuum mit beliebigem % auf eine Übereinstimmung zeigt.

Nun nährt man sich der Übereinstimmung wieder (o,u,r,l) mit xpx und ermittelt in welche Richtung es geht und wie viel % man mit wie viel px bekommt. Aus dem % und px berechnet man nun einen möglichen Sprung aufs Optimum.
(Man muss hier keine zweite Näherung durchführen und kann die Werte vom vorherigen Schritt nehmen - nur als Erklärung)
Dann kalibriert man sich auf Optimum.

(Ein Individuum kann auch auf zwei oder mehrere zeigen und muss dann vermehrt werden.)

Bin aus den Fingern heraus nicht fähig das zu programmieren, würde mich aber interessieren, welcher Ansatz bei den Tests vielversprechender ist. Finden-Lokalisieren-Algorithmus oder Evolutionärer-Algorithmus.

Ich werde einmal beides benchmarken/programmieren.
Nur damit ich deine Idee auch einigermaßen so umsetzen kann wie du meintest. Der Algorithmus sähe ganz grob so aus, oder?

Quote:

1. Erzeuge Individuen, so dass die Freiräume zwischen 2 Individuen etwa der Hälfte der Breite/Höhe des zu suchenden Bildes entspricht
2. Berechne die Fitness von jedem Individuum und schmeiße alle außer das beste Individuum raus
3. Schaue in jeder Richtung von dem überlebenden Individuum und versuche das Individuum Schrittweise zu verbessern, indem man es in die Richtung verschiebt, die am meisten Übereinstimmung verspricht
4. Wiederhole das Ganze solange bis man keine bessere Position mehr gefunden hat

MrDami123 · 11/26/2015, 19:42

Quote:

1. Erzeuge Individuen, so dass die Freiräume zwischen 2 Individuen etwa der Hälfte der Breite/Höhe des zu suchenden Bildes entspricht
2. Berechne die Fitness von jedem Individuum und schmeiße alle außer das beste Individuum raus
3. Schaue in jeder Richtung von dem überlebenden Individuum und versuche das Individuum Schrittweise zu verbessern, indem man es in die Richtung verschiebt, die am meisten Übereinstimmung verspricht
4. Wiederhole das Ganze solange bis man keine bessere Position mehr gefunden hat

1. Erzeuge Individuen, so dass die Freiräume zwischen 2 Individuen etwas kleiner als das zusuchende Bild sind. (Das eine Übereinstimmung erkannt wird - umso weniger umso besser)

2. Berechne die Fitness von jedem Individuum und schmeiße alle außer das beste Individuum raus (falls das zusuchende Bild nur einmal im Bild vorkommt - als test nehmen wir mal 1 zusuchendes bild im bild)

3. Finde die Richtung in x,y indem die Übereinstimmung verbessert wird und speicher um wie viel % es besser wird bei wie viel px schrittweite

4. Mach ein Sprung in px auf das mathematische Optimum also 100%. (z.B. 5px nach unten +7% -> berechnen wie viel px noch fehlen bis 100% und dort das Individuum erzeugen)

5. Gehe Schrittweise bis zum Optimum, wenn nicht schon drauf.

Shadow992 · 11/26/2015, 20:12

Quote:

Originally Posted by MrDami123

1. Erzeuge Individuen, so dass die Freiräume zwischen 2 Individuen etwas kleiner als das zusuchende Bild sind. (Das eine Übereinstimmung erkannt wird - umso weniger umso besser)

2. Berechne die Fitness von jedem Individuum und schmeiße alle außer das beste Individuum raus (falls das zusuchende Bild nur einmal im Bild vorkommt - als test nehmen wir mal 1 zusuchendes bild im bild)

3. Finde die Richtung in x,y indem die Übereinstimmung verbessert wird und speicher um wie viel % es besser wird bei wie viel px schrittweite

4. Mach ein Sprung in px auf das mathematische Optimum also 100%. (z.B. 5px nach unten +7% -> berechnen wie viel px noch fehlen bis 100% und dort das Individuum erzeugen)

5. Gehe Schrittweise bis zum Optimum, wenn nicht schon drauf.

Tatsächlich sieht eine Abwandlung von diesem Algorithmus ziemlich vielversprechend aus.

Ich habe deinen original Ansatz geprüft und dabei einmal bisschen weniger als die Hälfte der Höhe/Breite als Abstand zwischen zwei Individuen genommen, das beste damit gefundene Ergebnis war Ähnlichkeit von 0.3 = 30% (maximal möglich war 70%).
Der Ansatz verhält sich also wie erwartet ziemlich instabil was lokale Optima angeht.

Wenn man den Abstand der Individuen aber so gestaltet, dass sie sich zur Hälfte überlappen, bekommt man ziemlich gute Ergebnisse.
Die Ergebnisse sind zwar nicht perfekt, aber sie finden ein Optimum mit 65% Ähnlichkeit. Noch besser wird das Ganze, wenn man die Individuen zu 3/4 überlappen lässt.
Bei 3/4 Überlappung sieht es nach ersten Tests so aus als würde in 99% der Fälle das globale Optimum gefunden werden.
Auch die benötigte Zeit ist "ok". Es sind rund 200ms. Das ist zwar nicht ganz mein angestrebter Wert, aber mit ein paar Optimierungen könnte man das Ganze sicher noch auf knapp über 100ms drücken.

Bei 1/2 Überlappung braucht es 40ms, was echt verdammt gut ist, dafür ist er leider noch nicht perfekt genug was das Auffinden angeht.
2/3 Überlappung sieht mir nach einem sinnvollen Kompromiss aus, hier braucht der Algorithmus ziemlich genau 100ms und findet in den meisten Fällen das Optimum.

Ich werde jetzt noch die Evolutionären Algorithmen testen und auch ein paar mehr Beispiel anschauen. Der original Ansatz von dir scheint wie die PSO an den lokalen Optima zu scheitern.

Edit:
EA: Schnell für kleine Bilder, die in riesigen Bildern gefunden werden sollen (Such-Bild: bis ca 50x50, Großes Bild ab ca. 2500x2500)
Überlappungsmethode: Sehr gut bei allen "Standard"-Auflösungen (also um die 1680x1050).

Ich werde beide Methode anbieten in meiner Library, einmal für den "Extrem-User", der riesige Bilder analysieren lassen möchte und einmal für den Durchschnittsnutzer, der nur seinen Bildschirm begutachten will.

Danke an alle, vor allem an MrDami123, ohne deinen Ansatz wäre ich nie auf die Überlappungsmethode gekommen. Danke dir

Edit2:
Setzt man den Überlappungswert auf 2.2 kriegt man ca. 80ms für ein 1680*1050 Bild hin und die Erkennungswerte sind weiterhin echt Spitze.

MrDami123 · 11/30/2015, 13:26

Ja super, freut mich das es so gut klappt!