Bildbearbeitung Optimierung



  • JoDCode schrieb:

    Danke schon einmal für die Tipps,

    Die Nähe ist zunächst zum Testen simpel gehalten:

    z.B Bild 2 RGB = 225;225;225 und nicht in Bild 1 Vorhanden.
    In Bild 1 RGB[3] 200;200;200, 250;250;250, 190;190;190;

    Bild 2
    RGB1 = 200+200+200 = 600
    RGB2 = 250+250+250 = 750
    RGB3 = 190+190+190 = 570

    Bild 1
    RGB = 225+225+215 = 675

    RGB1 oder RGB2 kommen mit jeweils Abstand von 75 am nähsten heran.
    Es würde also entweder RGB1 oder RGB2 herangenommen, je nach Position im Durchlauf.

    Wenn man mal die Empfindlichkeit des Auges außen vor lässt*, so sollte man doch zumindest die RGB Werte als Vektoren eines 3d Vektorraums auffassen und somit auch das übliche Abstandsmaß verwenden. Also sqrt(dR2+dG2+dB^2) mit dR=R1-R2 und für dG und dB entsprechend. Wobei das sqrt() nichts an der relevanten Information ändert, also kannst du das auch weglassen, übrig bleibt das bekannte Skalarprodukt.

    So, nun brauchst du noch eine gute Suchstruktur. Es bietet sich etwas baumartiges an, z.B. ein kD Tree. Mit einfachen Vergleichen, z.B. R>128, gehst du Ebene für Ebene nach unten, bis nur noch eine begrenzte Menge an Möglichkeiten übrigbleibt. Und bei der verbleibenden Menge suchst du dann eben mittels dem Skalarprodukt den nächsten Nachbarn.

    * die Ähnlichkeit von Farben ist garnicht so einfach zu berechnen, das Farbmodell RGB ist dafür weniger gut geeignet, es gibt hierfür Farbräume von CIE. Das wäre in dem Fall aber Overkill.



  • fsdfsdfsf schrieb:

    So, nun brauchst du noch eine gute Suchstruktur. Es bietet sich etwas baumartiges an, z.B. ein kD Tree. Mit einfachen Vergleichen, z.B. R>128, gehst du Ebene für Ebene nach unten, bis nur noch eine begrenzte Menge an Möglichkeiten übrigbleibt. Und bei der verbleibenden Menge suchst du dann eben mittels dem Skalarprodukt den nächsten Nachbarn.

    Und dann findest du den besten Match nicht, weil er blöderweise schon eine Ebene höher eliminiert wurde.



  • hustbaer schrieb:

    fsdfsdfsf schrieb:

    So, nun brauchst du noch eine gute Suchstruktur. Es bietet sich etwas baumartiges an, z.B. ein kD Tree. Mit einfachen Vergleichen, z.B. R>128, gehst du Ebene für Ebene nach unten, bis nur noch eine begrenzte Menge an Möglichkeiten übrigbleibt. Und bei der verbleibenden Menge suchst du dann eben mittels dem Skalarprodukt den nächsten Nachbarn.

    Und dann findest du den besten Match nicht, weil er blöderweise schon eine Ebene höher eliminiert wurde.

    müsste man mal schauen wie kNN das implementiert, mit k=1.
    damit hab ich bis jetzt gute Erfahrungen gemacht (performancemäßig).



  • Sind ja bloss 16.777 Mio mögliche Farben (@JoDCode: typischerweise verwendet man bei 24 Bit alle möglichen Werte, was dann 256^3 = 16777216 ist, und nicht 255^3 = 16581375). Da könnte man einfach nen 3D-Lookup-Table aufbauen.

    Index = Ausgangsfarbe (Farbe die es zu mappen gilt)
    Wert = Ergebnisfarbe

    Jetzt muss man "nur" noch den Table halbwegs performant aufbauen. Müsste aber mMn. machbar sein.

    Idee 1:
    Erstmal werden alle erlaubten Ergebnisfarben an "ihrer" Position eintragen, die restlichen Zellen bleiben leer.
    Danach iteriert man mehrfach über den gesamten Table.
    Pro Zelle baut man eine Liste der aktuellen Ergebnisfarben der Zelle selbst plus aller nicht-leeren Nachbarzellen. Das können max. 27 Farben sein - also relativ überschaubar. Ist die Liste leer, lässt man die aktuelle Zelle leer, und geht zur nächsten Zelle.
    Ist die Liste nicht leer, sucht man die Farbe mit der geringsten Distanz (zur Ausgangsfarbe der aktuellen Zelle) aus.
    Sobald man in einer Iteration nichts mehr geändert hat, ist man fertig.
    Damit müsste man mit "üblichen" Distanzmetriken mMn. zu einer korrekten Befüllung der Tabelle kommen.

    Idee 2:
    Ähnlich wie (1), nur dass man die Ergebnisfarben nach der Reihe mit "flood fill" in den Table einfügt. Jede Zelle speichert dazu zusätzlich zur Ergebnisfarbe noch die Distanz zwischen der Zelle selbst und der Ergebnisfarbe. (Ist vermutlich schneller als die Distanz bei jedem Vergleich "on the fly" zu berechnen.)
    Als erstes füllt man den ganzen Table mit der ersten Ergebnisfarbe und den Distanzwerten zu dieser Farbe.
    Dann nimmt man sich die nächste Ergebnisfarbe und schreibt sie erstmal an "ihre" Position.
    Dort startet man dann einen "flood fill". Dabei ist die Bedingung einfach dass jede an bereits in diesem Durchgang "gefüllte" Zellen angernzende Zelle ebenfalls gefüllt wird, wenn die Distanz zur aktuellen Ergebnisfarbe geringer ist als die aktuell eingetragene Distanz.
    Am Anfang wird man dabei pro möglicher Ergebnisfarbe grosse Bereiche mit dem "flood fill" überschreiben müssen. Wenn man die Farben möglichst Random einfügt müsste der zu füllende Bereich allerdings recht flott kleiner werden.
    Auch das müsste mMn. mit "üblichen" Distanzmetriken zu einer korrekten Befüllung der Tabelle führen.

    Wobei "mMn." heisst: ich habe das "Gefühl" dass es funktionieren müsste. Bin mir aber nicht 100% sicher. Und speziell bei (1) bin ich mir nicht sicher ob man das nicht noch deutlich vereinfachen kann.

    Bzw. Idee 1 und 2 kombiniert:
    Anfang gleich wie bei (1), nur dass man, statt einen neuen Wert für die aktuelle Zelle zu suchen guckt welche Nachbarzellen man mit der "eigenen" Farbe überschreiben könnte. Fühlt sich auch so an als ob das funktionieren müsste.

    Und wenn man den Table einfacheinmal hat muss man nur noch das Bild durchgehen und pro Pixel einen Lookup machen. Easy.

    Speziell wenn die Anzahl der erlaubten Ergebnisfarben gross ist, und das Bild gross ist, würde ich annehmen dass das deutlich schneller geht als pro Pixel die nächstgelegene Farbe zu suchen. Egal ob Brute-Force oder mit Hilfe einer "schlauen" Datenstruktur.

    Und jetzt bin ich gespannt auf die noch viel schlaueren Lösungen wie man die Tabelle aufbauen könnte die irgendeiner von Euch sicher parat hat 🙂
    (Und/oder die Schwachstellen meiner Ideen!)



  • Es wäre wirklich interessant mehr über die Abstandsnorm zu erfahren, denn wenn diese auf Konzepten wie Helligkeit basiert könnte man weiterhin den Farbraum in 3 Ebenen auftrennen und jede getrennt bearbeiten, wie in meinem ersten Post. Der repräsentiert ja Hustbaers Idee, aber eben nur für eine Grauwert-Plane mit dann nur maximal 256 Farben - und das wird eben trivial zu implementieren.



  • Also, um mal etwas konkreter zu werden.
    Ich habe den vorgeschlagenen Weg über KNN mal probiert mit Matlab. Die Ergebnisse sind nicht so toll - bei 32x24 großen Bildern beträgt die Laufzeit bereits 5sec.
    Als Abstandsmaß wird der Euklidischer Abstand im RGB Raum verwendet.

    function mapColors()
        tic; % Timer
    
        % Bilder einlesen
        I1=imread('1.jpg');
        I2=imread('2.jpg');
    
        % Liste der RGB Werte von I1 erstellen, Nx3, gleiche RGB Werte entfernen
        rgbList1=reshape(I1,[],3);
        [rgbList1Unique,~,~]=unique(rgbList1,'rows');
        rgbList1Unique=double(rgbList1Unique);
    
        % KNN Modell aufbauen
        mdl=fitcknn(rgbList1Unique,1:size(rgbList1Unique,1));
    
        % Liste der RGB Werte von I2 erstellen, Nx3, gleiche RGB Werte entfernen
        rgbList2=reshape(I2,[],3);
        [rgbList2Unique,~,uniqueToList]=unique(rgbList2,'rows');
        rgbList2Unique=double(rgbList2Unique);
    
        % Ergebnis: die gefundenen, nähesten Farben
        rgbListMapped=zeros(size(rgbList2Unique));
    
        % gehe über alle in I2 vorhandenen Farben
        for x=1:size(rgbList2Unique,1)        
            rgbToPredict=rgbList2Unique(x,:);
            idx=predict(mdl,rgbToPredict);
            rgbPredicted=rgbList1Unique(idx,:);
            rgbListMapped(x,:)=rgbPredicted;      
        end
    
        % die gefundenen Farben zurückmappen, sodass ein Bild entsteht
        rgbList2=rgbListMapped(uniqueToList,:);
        I2=reshape(uint8(rgbList2),size(I2));
    
        % Ergebnis rausschreiben
        imwrite(I2,'out.png');
    
        toc; % Timer
    end
    

    Falls jemand Lust hat seinen eigenen Vorschlag zu testen und zu vergleichen, hier die beiden Bilder die ich verwendet habe:
    1.jpg, das Referenzbild: http://imgur.com/g2JXuMW
    2.jpg, das Bild dass die Farben aus dem Referenzbild verwendet: http://imgur.com/6QSj76B

    Zum "schnell mal runtertippen" kann ich Matlab, Octave oder Python (mit numpy und OpenCV) empfehlen.



  • Euklidischer Abstand => Minimierung im R3 => Getrennte Prozessierung der RGB-Planes möglich



  • Ich seh' nicht wie man das getrennt in den RGB-Planes machen sollte. Kannst du das näher beschreiben?



  • Marc++us schrieb:

    Euklidischer Abstand => Minimierung im R3 => Getrennte Prozessierung der RGB-Planes möglich

    du suchst in allen drei Richtungen also den minimalen Abstand zwischen dem neuen Punkt pp und einem der Punkte pip_i aus Bild1, also min(p.xpi.x)min(p.x-p_i.x). Gleiches für die y und z Richtung.
    Nun hast du im besten Fall nur noch drei verbleibende Punkte (bei gleichem Abstand auch mehr). Von diesen berechnest du jetzt d2d^{2} und suchst das Minimum.
    Hab ich das richtig verstanden?

    Wie rechtfertigst du das mathematisch?
    Wenn ich d2=(xx_i)2+(yy_i)2+(zzi)2d^{2}=(x-x\_i)^{2} +(y-y\_i)^{2} +(z-z_i)^{2} minimiere, so berechne ich den Gradienten und setze diesen gleich dem Nullvektor. Ideale Lösung wäre natürlich x=x_i,y=y_i,z=zix=x\_i, y=y\_i, z=z_i. Das tritt aber meistens nicht ein. Stattdessen kann man nur versuchen, möglichst nahe an 0 zu kommen. Notwendige Bedingung für ein Minimum ist nun, dass zumindest in eine Richtung ein Minimum erreicht wird, also dass z.B. (xx_i)2<(xx_j)2(x-x\_i)^{2}<(x-x\_j)^{2} für alle j!=i. Hinreichende Bedingung ist dann, dass d2d^{2} minimal wird.

    Feedback willkommen 😉



  • Ich glaub ich verstehs einfach nicht, aber ... ich frage trotzdem einfach mal nach. Falls die Frage zu doof ist im Falle des Falles einfach ignorieren 😉

    bcvbvcbcvbc schrieb:

    Notwendige Bedingung für ein Minimum ist nun, dass zumindest in eine Richtung ein Minimum erreicht wird, also dass z.B. (xx_i)2<(xx_j)2(x-x\_i)^{2}<(x-x\_j)^{2} für alle j!=i.

    Gibt doch genug Beispiele wo der Punkt mit dem geringsten d2d^{2} weder ein minimales (xxi)2(x-x_i)^{2} noch ein minimales (yyi)2(y-y_i)^{2} noch ein minimales (zzi)2(z-z_i)^{2} hat.

    z.B.
    x=(0,0,0)x = (0,0,0)
    x1=(100,0,0)x_1 = (100,0,0)
    x2=(0,100,0)x_2 = (0,100,0)
    x3=(0,0,100)x_3 = (0,0,100)
    x4=(10,10,10)x_4 = (10,10,10)
    d1d_1, d2d_2 und d3d_3 sind jeweils 100, d4d_4 ist nur ~17,3, somit ist x4x_4 der näheste Punkt. x4x_4 hat aber in keiner Richtung ein Minimum.



  • die Frage ist definitiv nicht zu doof.
    Ich hab nämlich Marcus gefragt, wie er das sauber mathematisch zeigen kann. Meine Ausführungen betrachte bitte nur als Gedankenprotokoll, welches ich mit einem dicken Fragezeichen hier ins Forum zwecks Feedback gepostet habe.

    Hab das einfach mit dem Gradienten hingeschrieben wie aus Schule und Uni bekannt.
    x,y,z sind als Konstanten aufzufassen. x_i, y_i und z_i sind die veränderlichen Größen nach denen wir hier ableiten. Wären x_i, y_i und z_i kontinuierliche Größen, so ist das Ergebnis klar: x_i=x usw.
    Dies ist nicht der Fall, da ja meist kein x_i zu finden ist, welches gleich x ist.
    So ist nun ein x_i zu nehmen, welches den kleinsten Abstand zu x hat.
    Dies mache ich auch für y_i und z_i. Letztlich muss ich aber von denen doch noch die Distanz d^2 ausrechnen.



  • hustbaer schrieb:

    Ich glaub ich verstehs einfach nicht, aber ... ich frage trotzdem einfach mal nach. Falls die Frage zu doof ist im Falle des Falles einfach ignorieren 😉

    bcvbvcbcvbc schrieb:

    Notwendige Bedingung für ein Minimum ist nun, dass zumindest in eine Richtung ein Minimum erreicht wird, also dass z.B. (xx_i)2<(xx_j)2(x-x\_i)^{2}<(x-x\_j)^{2} für alle j!=i.

    Gibt doch genug Beispiele wo der Punkt mit dem geringsten d2d^{2} weder ein minimales (xxi)2(x-x_i)^{2} noch ein minimales (yyi)2(y-y_i)^{2} noch ein minimales (zzi)2(z-z_i)^{2} hat.

    z.B.
    x=(0,0,0)x = (0,0,0)
    x1=(100,0,0)x_1 = (100,0,0)
    x2=(0,100,0)x_2 = (0,100,0)
    x3=(0,0,100)x_3 = (0,0,100)
    x4=(10,10,10)x_4 = (10,10,10)
    d1d_1, d2d_2 und d3d_3 sind jeweils 100, d4d_4 ist nur ~17,3, somit ist x4x_4 der näheste Punkt. x4x_4 hat aber in keiner Richtung ein Minimum.

    jetzt habs ichs erst beim zweiten Mal lesen gesehen (editieren kann ich nicht).
    Du hast recht, mit dem Beispiel widerlegst du das natürlich ganz klar.
    Also ich warte jetzt mal bis uns Marc++us diesbezüglich aufklärt 😉



  • Ah, hatte das für einige Tage aus den Augen verloren.

    Ich dachte, dass wir die Distanz auf jeden Fall auf 0 legen können... dann hätte man in jeder Dimension separat arbeiten können. Aber ich habe mich aus der falschen Seite angenähert, die Distanz wird nur minimal und nicht 0.


Anmelden zum Antworten