Característiques(image features)

Felipe LumbrerasDept. Ciències de la Computació / Centre de Visió per Computador

Universitat Autònoma de Barcelonahttp://www.cvc.uab.es/shared/teach/a102784/

Característiques

Porció d’informació que permet resoldre una tasca.

"interesting" part of an image (Wikipedia)

• dos tipus de característiques:– Globals: propietats globals o una part d’ella que la descriuen

• Nivell de gris mitjà, color mitjà, principals colors, histograma, histograma color.

– Locals: part d’una imatge, detectable i amb entitat pròpia• punts, contorns, regions

Característiques

• de Global a Local

– Global

– Segment d’imatges (objectes)

– Mostreig (sliding window)

– Local

Característiques locals

• Què són– Porció d’una imatge que difereix del seu entorn. Associada a un canvi en

alguna propietat: intensitat, color, textura.– Poden ser:

• punts (corners, interest points), • contorns o parts (edges, ridges) o • petites regions (blobs)

• Cóm les trobem – Amb algorisme de Detecció/Extracció de característiques

• Localització/Descripció– Localització: posició més o menys precisa.– Descripció: mesures que es prenen al voltant de la característica que

permeten distingir-la o comparar-la amb d’altres.Depenent de l’aplicació prevaldrà més una o l’altra o totes dues.

Característiques locals

• Perquè les fem servirS’han usat amb èxit en moltes disciplines i aplicacions:

– Elements amb significació pròpia dins del context de l’aplicació: • Contorns relacionats amb carreteres en imatges aèries.

• Taques com a impureses en control de qualitat.

– Donen un conjunt limitat, ben localitzat i individualment identificable de punts d'ancoratge• Seguiment (tracking)

• Reconstrucció 3D

• Mosaics

– Poden ser usades com a una representació robusta de la imatge• Reconeixement d’objectes

• Classificació d’escenes

• Anàlisi de textures

• Cerca d’imatges

Característiques locals• Propietats (ideals):

– Repetibilitat: per imatges del mateix objecte o escena amb diferents condicions de captura, les característiques que trobem en una imatges han d'aparèixer en alt nombre en d’altres• Invariància: que no es vegin afectades o poc afectades per transformacions (intensitat,

geometria)• Robustesa: que no es vegin molt afectades per soroll, discretització, compressió,

desenfocament, ...

– Diferenciació/Informació: suficientment variada per poder distingir-la d’altres i posar-la en correspondència

– Localització: com a característiques locals han de estar lligades a punts molt concrets amb poca incertesa

– Quantitat: el nombre suficient per la tasca i la mida dels objectes implicats– Precisió: localització, escala i forma precisa– Eficiència: càlcul ràpid

• Escala: factor important a tenir en compte per obtenir robustesa, invariància i precisió. Permet treballar amb imatges adquirides de forma diferent, a diferents distàncies.

Propietats

Puntuals

Punts (cantonades)

Regió planano hi ha canvis en totes les direccions

Contornno hi ha canvis en la direcció del contorn

Cantonadacanvis significatius a totes les direccions

Detectors de cantonades

• Detector de HarrisProposat al 1988. Basat en l’anàlisi del tensor estructural 2D (matriu de derivades segones, second moment matrix).

• Detector de SUSAN Smallest Univalue Segment Assimilating Nucleus. Utilitza un enfoc morfològic (conjunts).

• Harris-LaplaceComença amb un Harris. Després determina la millor escala mitjançant el laplacià.

• Harris-AffineComença amb un Harris-Laplace. Després estima la forma afí (encaixa una el·lipse ), normalitza la forma afí (la converteix en un cercle). Torna a detectar punts en la imatge normalitzada.

Detector de Harris

intensitatintensitats

traslladadesfinestra

ofunció finestra w(u,v) =

gaussiana1 dins , 0 fora

• En una cantonada la intensitat canvia significativament en moltes direccions = Examinarem els canvis de intensitat deguts a translacions en una finestra local (SSD: sum of squared differences S).

Detector de Harris

La intensitat traslladada s’aproxima per una expansió de Taylor

Per tant

Que podem escriure en format matricial com

On A es el tensor estructural 2D

Detector de Harris

Canviem el problema d’examinar els canvis d’intensitat deguts a translacions per analitzar el comportament de la matriu A

→ Anàlisi dels valors propis1, 2 valors propis de A

Detector de Harris

1

2

“Cantonada”1 i 2 grans,1 ~ 2;S creix en totes direccions

1 i 2 petits;

S és quasi constant en totes direccions

“Contorn”1 >> 2

“Contorn”2 >> 1

“Pla”regió

Classificació dels punts de la imatge basat en els valors propis de A :

Detector de Harris

Funció de resposta de les cantonades ( R ):

R = det(A) - k (trace A)2

R = 12 - k (1 + 2 )2

on k es un valor constant (empíric) , k = [0.04,0.06]

Detector de Harris

1

2

“Cantonada”

“Contorn”

“Contorn”

“Pla”regió

• R depèn només dels valors propis de A

• R és gran per les cantonades

• R és negatiu amb magnitud gran pels contorns

• |R| és petit per les regions planes

R > 0

R < 0

R < 0|R| petit

Detector de Harris (algorisme)

• Derivades primeres d’un

punt de la imatge (u,v):

• Per cada punt computar:

• Matriu d’estructura local (M)

[abans anomenada A]

• Suavització amb una

gaussiana (G)

),(),( vux

IvuI x

=

),(),( vuy

IvuI y

=

),(),(),(

),,(),(

),,(),(

2

2

vuIvuIvuC

vuIvuB

vuIvuA

yx

y

x

=

=

=

=

=

BC

CA

III

IIIM

yyx

yxx

2

2

=

=

BC

CA

GBGC

GCGAM

Detector de Harris (algorisme)

• Diagonalitzem

• On 1, 2 són el valors propis de definits per:

• Descriu un punt en funció dels valors propis, mitjançant la funció de resposta de les cantonades

• Una bona cantonada ha de tenir canvis grans d’intensitat en totes direccions, R ha de ser gran i positiu.

=

2

1

0

0

M

( )222 422

1CBBAABA ++−+

( )2

1 2 1 2R k = − +

M

M

Original

Detector de Harris

funció de resposta a cantonades R

Detector de Harris

punts amb resposta alta: R > llindar

Detector de Harris

màxims locals de R

Detector de Harris

Resultat final

Detector de Harris

Detector de Harris (propietats)

• Invariant a Rotació: la resposta R es invariant a rotació.

• Invariància parcial al canvi afí d’intensitat (usem derivades)– Invariància a desplaçaments en intensitat: I → I+b

– Canvi de contrast: I → aI

La el.lipse rota però

la seva forma (valors

propis) resta igual.

R

x (image coordinate)

threshold

R

x (image coordinate)

Detector de Harris-Laplace

• Combina Harris amb un espai escala gaussià.

• Usem finestres gaussianes amb escales prefixades.

• S’escull l’escala que maximitza el LoG en aquest rang.

• Obtenim cantonades i l’escala on millor està representada

Detector de Harris-Affine

• Detecció inicial amb el detector Harris-Laplace

• Estimar la forma afí amb la matriu estructural 2D

• Normalitzar les regions afins a una circular

• Detectar novament posicions i escales en la imatge anterior

• Tornar al punt 2 si els valors propis varien

Segments

Contorns

• Què causa els contorns– Canvi de profunditat

– Canvi en la orientació

– Canvi de reflectància

– Canvi d'il·luminació

Christopher Rasmussen

Segments

• Contorns (edges): – Zones de la imatge on la magnitud del gradient té valors màxims.

• Valls/Crestes (ridges):– Corba que representa un màxim o mínim local

• Models

– Esglaó (contorn)

– Cresta

– Vall

Sudden

step edge

Slanted

step edge

Smooth

step edge

Planar

edge

Roof edgeLine edge

Gradient

• El gradient es el vector que apunta en la direcció de major canvi.

• Podem calcular d’ell la seva magnitud i la seva orientació

• Els contorns estan associats a valors alts de la magnitud del gradient

),(,)()grad( yx IIy

I

x

III =

==

)/arctan(

||22

xy

yx

II

II

=

+=

Suavització/Regularització

• Permet reduir el soroll i controlar l’escala d’anàlisi.

• La derivació amplifica el soroll. Podem suavitzar primer abans de derivar (regularitzar).

• Es pot suavitzar amb una gaussiana que té bones propietats (no amplifica certes freqüències).

• O directament, fer servir per derivar la convolució amb la derivada de la gaussiana.

Detectors de contorns

• Differential gradient operator

– Roberts

– Sobel

– Prewitt

• Laplacian of Gaussian

• Canny

Detectors de contorns

=

−−−

−

−

−

111

000

111

101

101

101

,)( imimimPrewitt

=

−−−

−

−

−

121

000

121

101

202

101

,)( imimimSobel

=

−

− 01

10

10

01,)( imimimRoberts

Sobel

Sobel im im im( ) =

−

−

−

+

− − −

1 0 1

2 0 2

1 0 1

1 2 1

0 0 0

1 2 1

2 2

Original Sobel Original Sobel

Laplacià

• Laplacià

• Aproximació numèrica

• Els creuaments per zero del laplacià donen els contorns de la imatge

2

2

2

22 )()()(

y

I

x

IIIILaplacian

+

===

−

−−

−

=

010

141

010

)( imimLaplacian

Laplacià

• Desavantatge: resultat més sorollós

• Solució: suavitzar amb una gaussiana

• Avantatge: dóna com a resultat contorns tancats

Original LoG Creuaments

Original Laplacià Creuaments

Detector de Canny

• Passos:

1. Calculem el gradient amb les derivades de la gaussiana

2. Apliquem supressió dels píxels no màxims (non-maximal supression)

• Aprimem contorns de varis píxels fins a amplada 1.

3. Unió i binarització• Definim llindars inferior i superior

• Acceptem tots els contorns per sobre del llindar inferior que estan connectats a contorns per sobre del llindar superior

• Matlab: edge(I, ‘canny’)

Detector de Canny2.- Norm of the gradient1.- Original

3.- Thresholding 4.- Thinning (non-maximum suppression)

Detector de Canny

• Escala

• L’elecció de depèn del comportament desitjat:– gran detecta contorns de gran escala

– petita detecta característiques petites

low high original

Agrupació

• Detecció de primitives d’alt nivell a partir de fragments de contorns o conjunt de punts

• Transformada de Hough per a línies (SLHT)

• Transformada de Hough per a cercles (CHT)

• Transformada de Hough generalitzada (GHT)

Transformada de Hough per a línies

• Transforma punts associats a un patró dins un espai de paràmetres on es poden representar d’una forma compacta.

• Exemple per a línies y=ax+b

• Solució: recta → r = x sin + y cos

y b

?

problema: a→

espai imatgex a

espai de paràmetres

→

Straight Line Hough Transform

• Passos:– Detecció de punts característics: seleccionar el píxels depenent de

les seves propietats locals (magnitud del gradient, orientació, ...) que seran transformats.

– Mapejat de la transformació: cada punt característic es mapeja en el espai de paràmetres (array d’acumulació o de votació).

– Detecció de pics: binarització local o global en l’array d’acumulació.

x

y

ri

i

r

180oi

rir = x sin + y cos

peak

→

ExempleInput image

Boundary detection

Hough

space

Result

−r

+r

x

y

Altres Transformades de Hough

• Cercles (CHT): – Espai de votació tridimensional (x,y,r).

– Cada punt vota en aquest espai de vocació en un con

• General (GHT):Definició del model:

– Per un objecte (contorn obert o tancat), definim un centre intern

– Per cada punt del contorn calculem el gradient (direcció del contorn)

– Del centre a cada punt del contorn calculem el radi i l’angle

– Guardem per cada direcció del contorn tots els radi-angle (R-table)

Votació:

– Generem imatge de contorns o partint de contorns. Calculem els gradients d’aquests.

– Per cada punt votem en tots els radi-angle que tinguem associats a aquesta direcció del contorn.

Regions

Regions

• Taques (blobs)

• Regions basades en intensitat

• Maximally Stable Extremal Region (MSER)

• Superpixels

Regions

• MSER– Regions estables, resten sense canvis en un rang de llindars.

• Superpixels– Agrupació compacta de píxels amb algun criteri

Descriptors

Descriptors

• Puntuals– Haar like

– Edge Orientation Histograms (EOH)

– Scale-Invariant Feature Transform (SIFT), SURF, BRISK, FREAK,...

– Histogram of Oriented Gradients (HOG)

– Local Binary Pattern (LBP)

• De forma– Simples: Àrea, Circularitat, Excentricitat, Orientació, Convexitat,

Moments,...

– Angular Radial Transform

– Shape contexts

– Shapemes

– Shape signature

– Boundary moments

– Fourier Descriptors

Haar-like

• Idea: diferència d’intensitat entre regions rectangulars

EOH

• Idea: relació entre les sumes locals de les magnituds del gradient de dues orientacions

SIFT

• Idea: localització en espai escala de DoG i descripció amb histogrames de gradients locals suavitzats.

SIFT

• Característiques invariants, “keypoints”– Estableix un marc invariant

• Màxims/mínims de l’espai escala DoG→ x, y, s• Màxim de la distribució dels gradients locals → q

– Forma vector descripció• Histograma de gradients locals suavitzats• 128 dimensions

• Les característiques SIFT són:– Geomètricament invariants a transformacions de

similaritats,• Bastant robust a canvis afins

– Parcialment invariants a canvis d'il·luminació i a canvis del punt de vista 3D

– Altament distintius

SIFT

• El contingut de la imatge es transforma en coordenades de característiques locals que són invariants a translació, rotació, escala I d’altres paràmetres.

HOG

• Idea: histograma d’orientacions del gradient ponderat per la magnitud del gradient

LBP

• Idea: descriu cada píxel a partir de les diferències locals d’intensitat en el veïnatge

Aplicacions

Brown and Lowe, ICCV 03

• Mosaics

Aplicacions

Quak09

• Cerca en bases de dades d’imatges

Aplicacions

Wojek09

• Detecció de vianants

Bibliografia

• T. Tuytelaars and K. Mikolajczyk. Local Invariant FeatureDetectors: A Survey. Fundations and Trends ® in ComputerGraphics and Vision, Vol. 3, No. 3, (2007) 177-280.

• E. Trucco, A. Verri. Introductory Techniques for 3-D ComputerVision. Prentice Hall (1998). Chap 4 and 5.

• Apunts del Master de Computer Vision:– Josep Lladós

– Marçal Rusiñol

– David Gerónimo