[Python] Algoritme for å finne første pixel-"match" (småtregt)

[slacky]

Hei, har nå endelig klart å pusle sammen en enkel algoritme for å søke etter en farge på et bilde (printscreen), og returnere koordinatene (x,y). Dette søket starter i sentrum av bildet, og jobber seg utover til ytterste hjørne (i en spiral form). Men, jeg finner den litt treg (fungerer bra ellers). Så jeg ønsker å høre om noen har et tips eller to som kan forbedre den noen hakk? Forbedring på ~.0002 ms for hver gjentakelse blir mye når du jobber med ~1.7millioner pikseler.

 

Bruker PIL-, og Colormath-modulen.

 

Oppdatert kode:

'''hex=fargen, X=fra.X, Y=fra.Y, W=til.X, H=til.Y, tol=toleranse(1-MAX)'''
def FindSpiral(hex, X, Y, W, H, tol=1):
image = ImageGrab.grab() #printscreen - PIL
r,g,b = hex_to_rgb(hex)
lab = rgb_to_lab(r, g, b) #Lab-avstand er rimelig likt det mennesklige syn.
sx,sy,dx,dy = 0,0,0,-1
WX,HY = (W+X)/2, (H+Y)/2
pix = image.load()

for i in xrange(max((W-X), (H-Y))**2):
	if (-WX < sx <= WX) and (-HY < sy <= HY):
		px = pix[WX+sx, HY+sy]
		px = rgb_to_lab(px[0],px[1],px[2])
		if max(map(lambda a,b: abs(a-b), px, lab)) < tol:
			return WX+sx, HY+sy

	if sx == sy or (sx < 0 and sx == -sy) or (sx > 0 and sx == 1-sy):
		dx, dy = -dy, dx
	sx, sy = sx+dx, sy+dy

'''Hex-color to RGB-color'''  
def hex_to_rgb(hex):
col = (hex[0:2], hex[2:4], hex[4:6])
return [int(x, 16) for x in col]

'''RGB-color to Lab-color'''
@memoize	  
def rgb_to_lab(R,G,B):
rgb = RGBColor(R,G,B)
lab = rgb.convert_to('lab', debug=False)
return lab.lab_l, lab.lab_a, lab.lab_b

 

Enkel forklaring av koden:

Den jobber seg fra sentrum av bildet i en "spiralform". Koden produserer et enkelt koordinatsystem som skal loopes gjennom.

X,Y,W,H er verdier for hvor på bildet/printscreen vi skal søke. Ved oppløsning på 1680*1050 får vi følgende for å søke hele skjermen: FindSpiral(hex, 0, 0, 1679, 1049, 1)

 

Bruksområde:

Brukes der jeg må finne den nermeste pixelen ut i fra sentrum. Jeg har en annen enklere variant hvor jeg søker X-start -> X-end, for å så hoppe ned en piksel (Y) etc...

Endret 24. desember 2012 av warpie

[etse]

vil anbefale deg å bruke "xrange()" i stede for "range()" da den gir bedre ytelse, når du bare skal iterere over den.

[Yumekui]

getpixel og putpixel er tregere enn pixel access objects, tror jeg.

 

import Image, ImageGrab, ImageColor

img = ImageGrab.grab()
pix = img.load()

print pix[x, y] # --> Gir deg RGB fargen på pixel x, y (der 0, 0 er øverst i venstre hjørne)

pix[x, y] = (R, G, B) # --> Setter pixelen (x, y) til fargen RGB.

 

 

Altså...

 

pix = image.load()
px = pix[(W+X)/2+sx, (H+Y)/2+sy)]

 

Om jeg ikke tar helt feil.

Endret 27. januar 2012 av Yumekui

[Yumekui]

getpixel er flere ganger tregere, virker det som:

 

get: 2.50294000068

pix: 0.464855100377

pix: 0.465179360931

get: 2.49706574862

 

get: 2.50418606577

pix: 0.497823889724

pix: 0.467758880466

get: 2.58900549748

 

get: 2.5628074678

pix: 0.475493222916

pix: 0.472476756536

get: 2.65985067916

 

get: 2.61343044285

pix: 0.534203930758

pix: 0.514342396914

get: 2.59152867387

 

get: 2.52907287162

pix: 0.501371591479

pix: 0.492399616253

get: 2.55136559304

 

(...)

 

 

 

#Forøvrig 1680x1050 pixler

import Image, ImageColor, ImageGrab
import time

for i in range(10):
   img = ImageGrab.grab()
   pix = img.load()


   t = time.clock()
   for h in range(img.size[1]):
       for w in range(img.size[0]):
           img.getpixel((w, h))
   print "get:",time.clock()-t


   t = time.clock()
   for h in range(img.size[1]):
       for w in range(img.size[0]):
           pix[w, h]
   print "pix:",time.clock()-t


   """Og i motsatt rekkefolge for mest mulig likhet"""
   img = ImageGrab.grab()
   pix = img.load()

   t = time.clock()
   for h in range(img.size[1]):
       for w in range(img.size[0]):
           pix[w, h]
   print "pix:",time.clock()-t    


   t = time.clock()
   for h in range(img.size[1]):
       for w in range(img.size[0]):
           img.getpixel((w, h))
   print "get:",time.clock()-t

   print ""

 

 

 

Jeg er ikke helt sikker på hvordan måten du søker igjennom bildet på fungerer, men uansett - Du vet kanskje dette, men hvis det du leter etter er litt større enn 1 piksel (det dekker en 2x2 eller 3x3 rute av pixler, for eksempel), kan du unngå å søke igjennom alle pikslene;

 

Dersom du leter etter en grønn boks som du vet aldri er mindre enn 3x3 piksler, kan du sjekke kun hver tredje piksel (i x og y retning hver for seg), og likevel være sikker på å finne boksen (pikslene du sjekker er markert med rødt):

 

 

Her finner du boksen etter å ha sjekket 25 piksler, mot langt flere hadde du sjekket hver piksel (inkludert de grå).

Endret 27. januar 2012 av Yumekui

[slacky]

getpixel og putpixel er tregere enn pixel access objects, tror jeg.

...

Ser sannelig slik ut! Skal teste det ut. Ett flott tips!

Jeg søker nok etter en enkelt pixel.

Her har du et eksempel på hvordan den fungerer (krever 3.party modul: win32api)

import win32api, time

'''~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|| Basic spiral mouse movement!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'''            
def MouseSpiral(X,Y,W,H):
   sx,sy = 0,0
   dx,dy = 0,-1
   WX,HY = (W+X)/2, (H+Y)/2
   for i in range(max((W-X), (H-Y))**2):
       if (-WX < sx <= WX) and (-HY < sy <= HY):
           win32api.SetCursorPos((WX+sx,HY+sy))
           print(sx,sy)
           time.sleep(0.004)

       if sx == sy or (sx < 0 and sx == -sy) or (sx > 0 and sx == 1-sy):
           dx, dy = -dy, dx
       sx, sy = sx+dx, sy+dy

MouseSpiral(0,0,50,50)

 

Har en egen formel for å enkelt søke gjennom X og Y... Hvor jeg da søker bare EN og EN px (nødvendig).. Har lagt til det meste som kan være nødvendig i et "macroprogram". Er ikke ferdig med OCR, eller bildegjenkjenning (subimage i printscreen/image)

'''~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|| Search: Part of the screen _WITHOUT_ tolerance
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'''
def FindIn(hex, X, Y, W, H):
   r,g,b = hex_to_rgb(hex)
   image = ImageGrab.grab()
   pix = image.load()
   for x in xrange(X, W):
       for y in xrange(Y,H):
           px = pix[(x, y)]
           if px[0] == r and px[1] == g and px[2] == b:
               return x, y

 

vil anbefale deg å bruke "xrange()" i stede for "range()" da den gir bedre ytelse, når du bare skal iterere over den.

Jeg leser at det skal være en liten forskjell på disse, så det skal testes:)

Endret 28. januar 2012 av warpie

[ChristianAa]

Hei, har nå endelig klart å pusle sammen en enkel algoritme for å søke etter en farge på et bilde (printscreen), og returnere koordinatene (x,y). Dette søket starter i sentrum av bildet, og jobber seg utover til ytterste hjørne (i en spiral form). Men, jeg finner den litt treg (fungerer bra ellers). Så jeg ønsker å høre om noen har et tips eller to som kan forbedre den noen hakk? Forbedring på ~.0005 ms for hver gjentakelse blir mye når du jobber med ~1.7millioner pikseler.

 

Bruker PIL-, og Colormath-modulen.

'''hex=fargen, X=fra.X, Y=fra.Y, W=til.X, H=til.Y, tol=toleranse(~100)'''
def FindSpiral(hex, X, Y, W, H, tol=1):
   image = ImageGrab.grab() #printscreen - PIL
   r,g,b = hex_to_rgb(hex)
   lab = rgb_to_lab(r, g, b) #Lab-avstand er rimelig likt det mennesklige syn.
   sx,sy = 0,0
   dx,dy = 0,-1
   for i in range(max((W-X), (H-Y))**2):
       if (-(W-X)/2 < sx <= (W-X)/2) and (-(H-Y)/2 < sy <= (H-Y)/2):          
           px = image.getpixel(((W+X)/2+sx, (H+Y)/2+sy))
           px = rgb_to_lab(px[0],px[1],px[2])
           if max(map(lambda a,b: abs(a-b), px, lab)) < tol:
               return (W+X)/2+sx, (H+Y)/2+sy  

       if sx == sy or (sx < 0 and sx == -sy) or (sx > 0 and sx == 1-sy):
           dx, dy = -dy, dx
       sx, sy = sx+dx, sy+dy

'''Hex-color to RGB-color'''   
def hex_to_rgb(hex):
   col = (hex[0:2], hex[2:4], hex[4:6])
   return [int(x, 16) for x in col]

'''RGB-color to Lab-color'''      
def rgb_to_lab(R,G,B):
   rgb = RGBColor(R,G,B)
   lab = rgb.convert_to('lab', debug=False)
   return lab.lab_l, lab.lab_a, lab.lab_b

 

Håper noen har et tips på lur

 

Du kaller rgb.convert_to for hver piksel, jeg kjenner ikke pil særlig godt, men finnes det ikke mulighet til å konvertere hele bildet? Og søke i det konverterte bildet etterpå?

[slacky]

Jeg har tenkt, og erget meg MYE over det der. Uten å gjøre noe videre med det.. Er ikke så mye å finne på det å konvertere forskjellig til Lab-farge. Hadde jeg funnet et vis, så hadde det kansje vært noe å vinne på det. Tid det tok å konvertere: 0.0002 (som vil si jeg kan spare 10-talls sekunder, om konverteringen er raskere).

 

Selv om det skulle nå la seg gjøre å konvertere bildet til Lab-space.. Så går det nok ikke mye fortere. En blir uansett nødt til å loope hele bildet, pixel for pixel (for å konvertere). Alà det jeg alt gjør... TROR jeg.

Endret 4. februar 2012 av warpie

[Matsemann]

Så vidt jeg kan se er W, X, H og Y konstante. Så å regne ut (W-X), (H-Y), (W-X)/2, (H-Y)/2, (W+X)/2 osv. hele tiden virker unødvendig.

[slacky]

Så vidt jeg kan se er W, X, H og Y konstante. Så å regne ut (W-X), (H-Y), (W-X)/2, (H-Y)/2, (W+X)/2 osv. hele tiden virker unødvendig.

Der var det også fikset!

Hadde bare tenkt for meg selv at det ikke spilte noen rolle, sett bort i fra rotete kode, sparte også et noen ms.

(W-X)/2, (H-Y)/2 var bare en "skrivefeil", tenkte ikke over det før du skrev dette. Alt som brukes er (W+X)/2, (H+Y)/2 nå.

 

 

--------

Til nå har dere til nå har dere klart å minke med ~4 sekunder over store områder (1680*1050) hvor fargen var ved ca ved 1x,1y. Dette ca 50 sek. Jeg testet så UTEN å konvertere til Lab, da tok samme søket bare et par sekunder! :/

 

Det er vel kansje verdt å forsøke å bruke HSB avstand, forran LAB. RGB til HSB krever ikke avansert matematikk, dermed noe kjappere.

Endret 31. januar 2012 av warpie

[Yumekui]

Kan du forhåndsgenerere en dict med LAB verdier for hver RGB verdi? Det kan kreve en god del memory, men burde gå relativt fort å slå opp LAB verdier for vilkårlige RGB verdier.

 

Er du sikker på at det du leter etter bare kan finnes igjen ved én pixel? Eller består den av flere pixler? De trenger ikke ha samme farge. Du vil mer enn halvere antallet pixler du må igjennom dersom du kan hoppe over annenhver i begge retninger.

 

 

       for y in xrange(Y,H):
           px = pix[(x, y)]
           if px[0] == r and px[1] == g and px[2] == b:
               return x, y

 

Dette kan muligens forenkles til:

 

       for y in xrange(Y,H):
           if pix[x, y] == (r, g, b):
               return x, y

 

Nei?

 

 

Forsøkte å sammenligne spiral med "lesestil" (venstre -> høyre, venstre -> høyre) - Forskjellen var ikke merkbar.

Endret 29. januar 2012 av Yumekui

[slacky]

Kan du forhåndsgenerere en dict med LAB verdier for hver RGB verdi? Det kan kreve en god del memory, men burde gå relativt fort å slå opp LAB verdier for vilkårlige RGB verdier.

 

Er du sikker på at det du leter etter bare kan finnes igjen ved én pixel? Eller består den av flere pixler?

 

Forsøkte å sammenligne spiral med "lesestil" (venstre -> høyre, venstre -> høyre) - Forskjellen var ikke merkbar.

1. Er ikke så glad i å gjøre det så veldig resurskrevende. Men, det burde fungere bra. Vet ikke hvor mye minne det vil kreve, men det kan da ikke være store saken. Kan kjøre noen tester, om jeg finner inspirasjonen.

 

2. Jeg vet at i de fleste tilfellene (ved mitt bruk) så vil det å søke etter 1 pixel gi et bedre resultat. Men jeg kan kansje lage en til funkjson for hurtigsøk. Hvor jeg søker gjennom 2*2. pixler. Dette kan fungere bra for macroer som har med vanlige dataprogram å gjøre, surfing, o.l. Mens, alt med litt "grafikk" på den andre siden blir for detaljert.

 

3. Hva tenker du på da? I mitt bruk handler spiralsøk (fra senter) om at macroen skal finne den FØRSTE fargen, som er nermest senter, det er altså snakk om at fargen finnes FLERE plasser på skjermen. I alle andre tilfeller hvor dette ikke er nødvendig skal ikke denne brukes/trenges ikke denne.

Endret 30. januar 2012 av warpie

[Yumekui]

3. Hva tenker du på da? I mitt bruk handler spiralsøk (fra senter) om at macroen skal finne den FØRSTE fargen, som er nermest senter, det er altså snakk om at fargen finnes FLERE plasser på skjermen. I alle andre tilfeller hvor dette ikke er nødvendig skal ikke denne brukes/trenges ikke denne.

 

Jeg tenkte at spiralsøket kunne være litt mer krevende enn å ta pikslene i tur og orden, men fant ikke særlig forskjell. Det gir uansett mening å bruke spiral om du skal ha den første nærmest sentrum.

Endret 30. januar 2012 av Yumekui

[Terrasque]

Fikk en ide for den to_lab funksjonen..

 

CACHE = {}
def rgb_to_lab(R,G,B):
   if (R, G, B) in CACHE:
       return CACHE[(R, G, B)]
   rgb = RGBColor(R,G,B)
   lab = rgb.convert_to('lab', debug=False)
   result = lab.lab_l, lab.lab_a, lab.lab_b
   CACHE[(R, G, B)] = result
   return result

 

Man kan også lage en generell cache decorator:

 

def memoize(function):
 memo = {}
 def wrapper(*args):
   if args in memo:
     return memo[args]
   else:
     rv = function(*args)
     memo[args] = rv
     return rv
 return wrapper

 

Den kan da brukes slik:

@memoize
def rgb_to_lab(R,G,B):
   rgb = RGBColor(R,G,B)
   lab = rgb.convert_to('lab', debug=False)
   return lab.lab_l, lab.lab_a, lab.lab_b

 

Den vil bare ta utregningen en gang for hver verdi, og husker resultatet hvis den blir spurt igjen senere om samme.

 

Du kan også se på pypy, som kan være over 500x raskere i noen tilfeller. Men det spørs om nødvendige 3djeparts libs er tilgjengelig der.

 

Man har også numpy, som kan være verdt å se på. Man har også ting som Cython som kan hjelpe på flaskehalser.

 

Edit: Kom på en annen ting.. Hvis du har flere cores å misbruke og python 2.6 eller senere kan du forsøke å splitte bildet opp, og kjøre en process for hver del via multiprocessing modulen.

Endret 30. januar 2012 av Terrasque

[Terrasque]

Kan du forhåndsgenerere en dict med LAB verdier for hver RGB verdi? Det kan kreve en god del memory, men burde gå relativt fort å slå opp LAB verdier for vilkårlige RGB verdier.

 

1. Er ikke så glad i å gjøre det så veldig resurskrevende. Men, det burde fungere bra. Vet ikke hvor mye minne det vil kreve, men det kan da ikke være store saken. Kan kjøre noen tester, om jeg finner inspirasjonen.

 

Ska vi se...

 

1650*1050 = 1 732 500

256^3 = 16 777 216

 

Så det vil ta ~10x mer arbeid å forhåndsgenerere den enn å konvertere alle pikslene i bildet. Man kan forhåndsgenerere den og lagre / loade via cPickle, men spørs hvor mye man egentlig tjener på det.

 

16M verdier, 3 byte for lookup, 3 byte for result (antar jeg?) er minimum 100mb lagring. Siden dicts bruker hash, og touples har struktur padding, så tipper jeg at det i praksis kan være snakk om en 2-3 dobling av det (om du ikke lager egen binary save / load funksjon).

 

Bare det å laste og parse den strukturen inn i minne vil ta en del tid.. Kanskje lage en ekstern lookup prosess som holder det i minne og kommuniserer via f.eks tcp, udp eller sockets? Så spørs det hvor mye overhead det er på det, og om det kanskje koster mer enn rgb_to_lab() gjør i utgangspunktet..

 

Man kunne lagd nettverks-servere som hver får en slice av bildet, og et område å sjekke. Det at de kjører hele tiden kan gjøre det verdt å pregenerere, og pluss at man får brukt nettverks-maskiner også.. Pluss at multi-core enkelt kan brukes med bare å spinne opp X servere på en maskin (en for hver core, og på forskjellig port).

 

 

*cough* ble mye tekst det, og sannsynligvis overkill.. Blir litt for lett opphengt i slikt.. Damn, nå har jeg lyst til å teste ut de forskjellige tingene! *sigh* Må konse på de tingene jeg egentlig skal gjøre. Håper trådstarter gir noen tilbakemeldinger på hvordan det går!

[slacky]

Det ble betydlig endring etter å ta i bruk catching. Fra ~60sek ned til 6 sekunder. Jeg sammenlignet ved å ikke kovnertere til L*a*b nå, da tok det ikke mer en 1.5 sekunder, så jeg tror det kansje er noe mer om kan bli gjort. Men kansje ikke nødvendig

 

Jeg har ofte vurdert å bruke PyPy. Men, har aldri tatt meg til det. Numpy (og Scipy) kan være veldig grei når det kommer til behandling av bilde, men har aldri testet det, har heller ikke satt meg inn i hvordan det fungerer.

[Yumekui]

Jeg har ofte vurdert å bruke PyPy. Men, har aldri tatt meg til det. Numpy (og Scipy) kan være veldig grei når det kommer til behandling av bilde, men har aldri testet det, har heller ikke satt meg inn i hvordan det fungerer.

 

Jeg har hatt store problemer med å få PIL til å virke med PyPy (Har ikke fått det til enda).

 

Ellers middels gode erfaringer med PyPy; PyPy har noen bugs som gjør den tregere enn CPython hva angår å legge enorme mengder verdier til sets hurtig (https://bugs.pypy.org/issue927 )

Endret 1. februar 2012 av Yumekui

[Terrasque]

cache kan kanskje gjøres enda mer effektivt ved bare å gjøre en lookup, istedet for to:

 

data = CACHE.get((r, g, b))
if data: 
  return data

 

Du kan også lagre cache fra gang til gang via pickle:

 

import cPickle

CACHE_FILE = "data.pkl"

#I starten av programmet:
try:
 input = open(CACHE_FILE, 'rb')
 CACHE = cPickle.load(input)
 input.close()
except:
 CACHE = {}
 print "Empty cache"


#På slutten av programmet:

output = open(CACHE_FILE, 'wb')
cPickle.dump(CACHE, output, 2)
output.close()

 

Men etterhvert så vil den sannsynligvis bli ganske stor, og det kan fort ta lenger tid å skrive / lese den enn det du sparer inn. På et prosjekt jeg har så kutter det der ned tiden fra over en time til 10 minutter, men det tar ca 20 sekunder å lese inn / lagre pickle objektet (~40mb stor fil).

[Djn]

Jeg har ofte vurdert å bruke PyPy. Men, har aldri tatt meg til det. Numpy (og Scipy) kan være veldig grei når det kommer til behandling av bilde, men har aldri testet det, har heller ikke satt meg inn i hvordan det fungerer.

 

Jeg har hatt store problemer med å få PIL til å virke med PyPy (Har ikke fått det til enda).

 

Ellers middels gode erfaringer med PyPy; PyPy har noen bugs som gjør den tregere enn CPython hva angår å legge enorme mengder verdier til sets hurtig (https://bugs.pypy.org/issue927 )

 

Har du forsøkt å bruke Cython? Det ser ved første øyekast ut som om du kunne spare veldig mye tid ved å slenge på litt typer og slikt - men jeg aner ikke hvordan Cython fungerer på windows, og jeg har aldri forsøkt å kombinere det med PIL.

 

edit: Jeg ser Terrasque allerede nevnte Cython. Uansett - ta det som en anbefaling til.

(Hvis jeg får tid til å teste hvilken effekt det har skal jeg poste resultatene.)

Endret 1. februar 2012 av Djn

[kyrsjo]

Med numpy kan du vektorisere en del ting, og da blir det ~like raskt som C++/Fortran. F.eks. kunne du startet med å konvertere hele bildet til lab i *ett* funksjonskall[1] (funksjonskall er dyre i Python) til C++, og så trekke fra og ta abs() i to kall til.

 

Det pleier ofte å spare MYE tid (dvs. du oppnår c++-hastighet, dog av og til med en suboptimal algoritme) i forhold til ren Python og masse kall...

 

[1] Kanskje mer enn ett dersom du må reimplementere LAB - aner ikke hvordan rgb->lab-"formelen" ser ut.

[Terrasque]

[1] Kanskje mer enn ett dersom du må reimplementere LAB - aner ikke hvordan rgb->lab-"formelen" ser ut.

 

Sjekket det når jeg postet, og etter det jeg fant så var det en haug med matrise oppslag, istedet for en fast formel..

 

Wikipedia ser ut til å støtte opp om det:

There are no simple formulas for conversion between RGB or CMYK values and L*a*b*, because the RGB and CMYK color models are device dependent. The RGB or CMYK values first need to be transformed to a specific absolute color space, such as sRGB or Adobe RGB. This adjustment will be device dependent, but the resulting data from the transform will be device independent, allowing data to be transformed to the CIE 1931 color space and then transformed into L*a*b*.

 

Og det lib'et han bruker for rgb -> lab bruker numpy for det. Og derfor er også pypy utelukket for now

 

Edit : Colormath - utregnings-info

Endret 9. februar 2012 av Terrasque