Repräsentative Farben eines Bildes ermitteln...

[kahst]

Hallo Leute!

Ein Image Retrieval System, an dem ich arbeite, soll eine Funktion haben, mit der man die n repäsentativen Farben eines Bildes (dh. aus dem Farbraum des Bildes) ermitteln kann. (sprich: das Bild wird auf n Farben reduziert, sieht aber hinterher noch fast genauso aus wie vorher)

Das Problem bei den gängigen Farbräumen (RGB CMYK HLS HSV usw) ist, dass sie mindestens 3 Dimensionen haben.

Es gibt auch nicht besonders viele Verfahren, die in der Literatur dazu genannt werden. Das häufigste ist der MedianCut-Algorithmus. Allerdings ist es recht aufwändig (meiner Meinung nach) so ein Verfahren zu implementieren.

Kennt jemand vllt. ein Paket für Python, in dem sowas schon drin ist (bei der PIL ist es leider nicht dabei - zumindest nicht, dass ich wüsste)?

Event. gibt es ja auch ein Paket mit Mathe-Funktionen, sind ja alles Vektoren...

Ich hab schon das Netz abgegrast, bisher aber ohne Erfolg. Wär schön, wenn mir jemand helfen könnte.

[shakebox]

keine große Ahnung, aber mir kommt bei der Thematik eigentlich sofort das GIF-Format in den Sinn. Da man da ja auch die Farbtiefe reduziert, sind da Algorithmen drin die ne optimierte, reduzierte Farbpalette erstellen und dann das Bild noch dithern.

Entweder kannst Du direkt sowas nutzen, wenn Du als Ergebnis tatsächlich ein Bild haben willst. Oder aber Du nutzt das Stichwort mal als Suchbegriff, um evtl. so an gute Literatur zu kommen.

[kahst]

Daran hab ich auch schon gedacht. Allerdings nimmt PIL für GIFs meiner Meinung nach das "P" Format, also 256 Farben. Allerdings brauch ich so Größenordnungen um 4-6 Farben. Gibt es denn in PIL die Möglichkeit eine Palette automatisch (also sprich: repräsentativ) auf 5 Farben zu reduzieren?

Edit: Oder besser gefragt, gibt es eine Möglichkeit mit PIL ein Bild im "P" Modus zu speichern und PIL sucht sich dann automatisch die 256 besten Farben? Oder kann der "P" Modus nur entweder Farbe oder Helligkeit oder Sättigung?

[rayo]

Hi

Mit einem Neuronalen Netz könntest du sowas auch erledigen.

Hier hat es ein Beispieltool, jedoch fest auf 256 Werte beschränkt.
http://www.htw-dresden.de/~iwe/Belege/2 ... index.html

Sonst hat es eventuell noch hier was:
http://www.it.fht-esslingen.de/~schmidt ... de172.html

Gruss

[kahst]

Danke für deine Hilfe. Die beiden Seiten kenn ich leider schon. Ich hab mir die Doku zu den neuronalen Netzen durchgelesen, aber nicht wirklich kapiert, was da genau gemacht wird.

darum wärs ja schön wenns sowas für python geben würde. Ich hatte glaub ich auch mal noch ein anderes Paket gefunden, ganz ähnlich dem von PIL, bei dem Farbquantisierung dabei war. Das war sogar auf python.org (war ein link von google), wenn ich mich nicht irre. Aber ich finds nicht mehr...

[rayo]

Für das neuronale Netz kannst du unter dem Begriff "Kohonen Feature Map" oder SOM weiterstöbern.

Allgemein kannst du unter Vector quantization weiter suchen, da jede Farbe von einem Pixel als Vektor angesehen werden kann.

Vielleicht hilfts dir ja.

Würde mich ja gerne damit ein wenig auseinandersetzen, da ich Information Retrival und Neuronale Netze als Unterrichtsmodule habe, jedoch geht das Semester noch 1 Woche und wir müssen unsere Projektarbeit abschliessen.

Gruss

[kahst]

hmmm...dann werd ich wohl nochmal die neuronalen Netze unter die Lupe nehmen. Danke für die Links.

Vector quantization hab ich schon geguckt, es gibt da wohl ein Modul names "scipy" dessen Funktion "cluster" sowas machen soll, allerdings konnte ich dazu keine genaue Erklärung der Funktionsweise finden (oder wie ich es einsetze)

Wie gesagt: am liebsten wäre mir ich müsste es nicht selber implementieren. Wenns ein Mathe Modul gibt, dass das kann wär ich auch schon zu frieden.

[veers]

Einfachere Idee:
Erstelle eine fixe Palette mit 16 Farben.
Für jeden Pixel im Bild, suche die nächste Farbe. Zähle wie oft jede Farbe vorgekommen ist. Die Top 4 davon sind deine Farben.

Ansonsten gibt es zur Farbquantisierung noch einige andere Algorithmen

[kahst]

Erstelle eine fixe Palette mit 16 Farben.
Für jeden Pixel im Bild, suche die nächste Farbe. Zähle wie oft jede Farbe vorgekommen ist. Die Top 4 davon sind deine Farben.

Das ist ja genau das Problem . So einfach funzt das zwar auch, aber ist möglicherweise zu ungenau. Man könnte auch einfach nur die 4 häufigsten Farben nehmen. Hab ich alles schon probiert. Da gehen eben Farben verloren, die relevant, aber nicht am häufigsten sind.

Ich will verhindern einen Farbraum skalar zu verkleinern und dann nur im Histogramm zu gucken, was am häufigsten vorkommt.

Welche Algorithmen zur Farbquantisierung kennst du denn noch? (ausser MedianCut, Popularity und Octree)

[kahst]

also ich habs jetzt wie folgt gemacht:

- jeder Farbwert wird wie ein Vektor behandelt (r,g,b)=>(y,x,z)

- Farbwerte, mit einem Abstand d, der kleiner ist, als eine vorgegebene Toleranz, werden zu einem Wert zusammengefasst (einfach arithmetisches Mittel für jeden Kanal)

- es bleiben k verschiedene Farben übrig (also alle die, bei denen d > Toleranz)

->falls k < n (n=Anzahl der gewünschten Farben), so wird die Toleranz verkleinert und nocheinmal die k Farben berechnet

->falls k > n, so werden die 2 Farben, die den geringsten Abstand d haben, zu einer Farbe zusammengefasst (wieder arith. Mittel) Das geht so lange, bis nur noch n Farben übrig sind.

Ich habs an verschiedenen Bildern ausprobiert, sieht ganz gut aus.

[Karl]

Mich würde mal der Quelltext interessieren Ich lese öfter hier, um ein paar Sachen zu lernen, jetz könnte ich mal sehen, wie man so ein Bild mit Python bearbeitet und so :p Okay, kann man auch selbst nachschaun...

[kahst]

Ok, hier ist mein Quelltext, allerdings ohne Kommentare und alles in einzelnen Funktionen, da es ja für ein größeres Projekt gedacht ist. (Darum ist der Aufruf auch hier und da noch etwas umständlich)

An der ein oder anderen Einstellung kann man auch noch viel feintunen...

Code: Alles auswählen

# -*- coding: cp1252 -*-
import Image
import ImageFilter
from math import *

#Verarbeitungsgröße der Bilder (damits schneller geht):
faktor=8
s_x=int(4*faktor)
s_y=int(3*faktor)

#Anzahl der Farben im Codebuch (die am Ende übrig bleiben):
cb_stufen=7

######################################################################

#Bild öffnen
def oImage(in_file):
    img = Image.open(in_file,"r")
    img=img.resize((s_x,s_y),Image.NEAREST)       
    return img

#Bild speichern
def sImage(in_img,in_path):
    in_img=in_img.resize((400,300))
    if in_img.mode!="RGB":
        in_img=in_img.convert("RGB")
    in_img.save(in_path,"BMP")

#Berechnet den Abstand 2er Vektoren
def calcDist(p,q):
    dist=sqrt( ((p[0]-q[0])**2) + ((p[1]-q[1])**2) + ((p[2]-q[2])**2) )
    #print p,q,dist
    return dist

#Bestimmt die Größe der Toleranz anhand des genutzen Farbraumes
def calcToleranz(in_img):
    data=list(in_img.getdata())
    max_r=0
    min_r=255
    max_g=0
    min_g=255
    max_b=0
    min_b=255
    for i in range(1,len(data)):
        if data[i][0]>max_r:
            max_r=data[i][0]
        if data[i][0]>min_r:
            max_r=data[i][0]
        if data[i][1]>max_g:
            max_r=data[i][1]
        if data[i][1]>min_g:
            max_r=data[i][1]
        if data[i][2]>max_b:
            max_r=data[i][2]
        if data[i][2]>min_b:
            max_r=data[i][2]
    p=(min_r,min_g,min_b)
    q=(max_r,max_g,max_b)
    dist=calcDist(p,q)
    toleranz=dist/5
    return toleranz        

#Sortiert ähnliche Farben in eine Liste
def sortByColor(in_img,toleranz):
    sortList=[[]]
    data=list(in_img.getdata())
    for x in range(0,in_img.size[0]):
        for y in range(0,in_img.size[1]):
            pos=(y*s_x)+x
            for i in range(0,len(sortList)):
                if len(sortList[i])==0:
                    sortList[i]=([data[pos]])
                    sortList.append([])
                else:
                    if calcDist(sortList[i][0],data[pos])<=toleranz:
                    #if abs(sum(sortList[i][0])-sum(data[pos]))<=toleranz:
                        sortList[i].append(data[pos])
                        break
    if len(sortList[-1])==0:
        del sortList[-1]
    return sortList[:]

#Erzeugt Code Buch mit k Farben
def createRawCB(in_img,in_toleranz,in_stufen):
    cb=[]
    sortList=sortByColor(in_img,in_toleranz)
    #print "Toleranz:",in_toleranz
    #print "Anzahl Farben:",len(sortList)
    for i in range(0,len(sortList)):
        sum_r=sortList[i][0][0]
        sum_g=sortList[i][0][1]
        sum_b=sortList[i][0][2]
        for j in range(1,len(sortList[i])):
            sum_r+=sortList[i][j][0]
            sum_g+=sortList[i][j][1]
            sum_b+=sortList[i][j][2]
        avrg_r=sum_r/len(sortList[i])
        avrg_g=sum_g/len(sortList[i])
        avrg_b=sum_b/len(sortList[i])
        sortList[i][0]=(avrg_r,avrg_g,avrg_b)
        cb.append(sortList[i][0])        
    return cb

#Erhöht oder verringert Anzahl der Farben im Code Buch, bis n erreicht ist
def optimizeCB(in_cb,in_stufen):
    min_dist=-1
    index1=0
    index2=0
    opt_cb=in_cb[:]
    if len(in_cb)>in_stufen:
        for i in range(0,len(in_cb)):
            for j in range(i+1,len(in_cb)):
                dist=calcDist(in_cb[i],in_cb[j])
                if min_dist==-1:
                    min_dist=dist
                else:
                    if dist<min_dist:
                        index1=i
                        index2=j
                        min_dist=dist
        avrg_r=int((in_cb[index1][0]+in_cb[index2][0])/2)
        avrg_g=int((in_cb[index1][1]+in_cb[index2][1])/2)
        avrg_b=int((in_cb[index1][2]+in_cb[index2][2])/2)
        in_cb[index1]=(avrg_r,avrg_g,avrg_b)
        del in_cb[index2]
        opt_cb=optimizeCB(in_cb,in_stufen)    
    return opt_cb
        
#Hauptfunktion zum Erstellen des Code Buches
def createCB(in_img,in_toleranz,in_stufen):
    cb=createRawCB(in_img,in_toleranz,in_stufen)
    if len(cb)>=in_stufen:
        cb=optimizeCB(cb,in_stufen)
    else:
        cb=createCB(in_img,in_toleranz*0.9,in_stufen)
    return cb

#Wendet das Code Buch auf das Bild an
def changeImageData(in_img,in_cb):
    minDist=-1
    data=list(in_img.getdata())
    for i in range(0,len(data)):
        minDist=-1
        for j in range(0,len(in_cb)):
            dist=calcDist(data[i],in_cb[j])
            if minDist==-1:
                index=j
                minDist=dist
            else:
                if dist<minDist:
                    index=j
                    minDist=dist
        data[i]=(in_cb[index][0],in_cb[index][1],in_cb[index][2])
    in_img.putdata(data[:])
    return in_img

#####################################################################################

path="image.jpg" #das Bild, das geöffnet wird
img = oImage(path)
print "Erstelle Codebuch..."
cb=createCB(img,calcToleranz(img),cb_stufen)
print "Codebuch",path,":\n",cb
print "Speichere Daten..."
cimg=Image.open(path)
cimg=cimg.resize((160,120))
cimg=changeImageData(cimg,cb)
sImage(cimg,"outpic_"+path+".bmp")
print "...done","\n"

[audax]

Die Performance von dem Ding ist mies, oder?

Als erstes würde ich da alle range() durch xrange() ersetzen...und:
Warum denn

Code: Alles auswählen

    for i in range(1,len(data)):
        if data[i][0]>max_r:
            max_r=data[i][0]
        if data[i][0]>min_r:
            max_r=data[i][0]
        if data[i][1]>max_g:
            max_r=data[i][1]
        if data[i][1]>min_g:
            max_r=data[i][1]
        if data[i][2]>max_b:
            max_r=data[i][2]
        if data[i][2]>min_b:
            max_r=data[i][2]

sowas?
Da ich nicht glaube, dass du absichtlich nur auf max_r zuweist und absichtlich das erste Element überspringst, würde ich es so schreiben:

Code: Alles auswählen

maxima = {'r':0, 'g':0, 'b':0}
minima = {'r':255, 'g':255, 'b':255}
for pixel in data[1:]:
        cur = dict(zip(maxima, pixel))
#       # oder ausführlich:
#        r, g, b = pixel
#        cur = {'r':r, 'g':g, 'b':b}
        for k, v in maxima.iteritems():
            maxima[k] = max(maxima[k], cur[k])
        for k, v in minima.iteritems():
            minima[k] = max(minima[k], cur[k])

Ich versteh auch ehrlich gesagt nicht, warum du so genre mit dem Index direkt Arbeitest Oo

[kahst]

Die Performance von dem Ding ist mies, oder?

Als erstes würde ich da alle range() durch xrange() ersetzen...und:
Warum denn

Code: Alles auswählen

    for i in range(1,len(data)):
        if data[i][0]>max_r:
            max_r=data[i][0]
        if data[i][0]>min_r:
            max_r=data[i][0]
        if data[i][1]>max_g:
            max_r=data[i][1]
        if data[i][1]>min_g:
            max_r=data[i][1]
        if data[i][2]>max_b:
            max_r=data[i][2]
        if data[i][2]>min_b:
            max_r=data[i][2]

sowas?
Da ich nicht glaube, dass du absichtlich nur auf max_r zuweist und absichtlich das erste Element überspringst, würde ich es so schreiben:

Code: Alles auswählen

maxima = {'r':0, 'g':0, 'b':0}
minima = {'r':255, 'g':255, 'b':255}
for pixel in data[1:]:
        cur = dict(zip(maxima, pixel))
#       # oder ausführlich:
#        r, g, b = pixel
#        cur = {'r':r, 'g':g, 'b':b}
        for k, v in maxima.iteritems():
            maxima[k] = max(maxima[k], cur[k])
        for k, v in minima.iteritems():
            minima[k] = max(minima[k], cur[k])

Ich versteh auch ehrlich gesagt nicht, warum du so genre mit dem Index direkt Arbeitest Oo

Hast recht, der Quelltext ist oben ist ein Fehler, den ich hier aus Versehen gepostet habe. Natürlich wird nicht jedesmal auf max_r zugewiesen

Ich nehm so oft index, weil ich sicher aus anderen Sprachen geschädigt bin.

-->das mit dem xrange hab ich noch nicht gehört...hmmm, und das bringt Performance Vorteile?

[BlackJack]

`xrange()` erzeugt im Gegensatz zu `range()` keine Liste, spart also auf jeden Fall schon einmal Speicher.