Modèles Génériques de Représentation et Traitement … · A. Manzanera - Séminaire LRDE 2012 1/50 Modèles Génériques de Représentation et raitementT des Images Antoine Manzanera

A. Manzanera - Séminaire LRDE 2012 1 / 50

Modèles Génériques de Représentation etTraitement des Images

Antoine ManzaneraENSTA-ParisTech

LRDE - 9 Mai 2012


Introduction

Contexte et Historique


L'objectif global de notre recherche est la conception de systèmesde vision embarqués e�caces et génériques. Nous nous intéressonsdepuis longtemps au calcul parallèle, avec un ancrage historique fortpour le calcul cellulaire (rétines programmables).

I SIMD synchrone / SPMDasynchrone

I Arithmétique bit-série

I Morphologie Mathématique

I Estimation Σ-∆


Introduction



I Limitations des rétinesprogrammables aubas/moyen niveau

I Contraintes liées à laconception et fabrication desASICs

I Multiplication des modèles etstructures de données entraitement d'images

I Prévalence des systèmes surétagères (COTS)

Aujourd'hui notre recherche est plus largement orientée vers lesalgorithmes de vision polyvalents sur systèmes distribuéshétérogènes.


Introduction

Vue générale du modèle

Modèle de traitement et de représentation


Introduction

Vue générale du modèle

IntroductionContexte et HistoriqueVue générale du modèleTravaux apparentés

Local jetsL'espace LJCodages et structures de données

Traitement d'ImageFiltrage NL-meansFlot optiqueDétection de mouvement

Représentations visuellesSingularités et modes de l'espace des caractéristiquesLocal jets et transformées de Hough densesModèles Implicites de Forme denses

Conclusions


Introduction

Travaux apparentés

Travaux apparentés

Manifold Image Processing

Les données projetées forment une variété dans l'espace descaractéristiques [Peyré 09]. Un traitement consiste à transformercette variété, puis à la rétro-projeter dans l'espace image.

Espace d'échelles et dérivées

La décomposition en dérivées multi-échelles est fondéebiologiquement [Koenderink 87] et mathématiquement par lathéorie des espaces d'échelles [Lindeberg 98].

Bancs de �ltres et dictionnairesCertaines modélisations visuelles pour les textures (p. ex. textons)ou objets (p.ex sacs de mots visuels) combinent bancs de �ltres etquanti�cation [Freeman 91], [Rubner 99].


Introduction

Travaux apparentés

Travaux apparentés

Plus Proche VoisinLes espaces de caractéristiques sont en général creux et béné�cientde structures telles que les Kd-trees pour réaliser e�cacement desopérations de voisinage [Arya and Mount 07].

Espaces d'accumulation

Les techniques d'accumulation dans un espace de paramètres(transformées de Hough) forment un ensemble de méthodes dedétection adaptées à la représentation par ensemble decaractéristiques [O'Gorman 76], [Valenti 08].


Local jets





Conclusions


Local jets

L'espace LJ

Dérivées gaussiennes multi-échelles

Notre espace de caractéristique est l'ensemble des dérivées gaussiennes

multi-échelles (r : ordre de dérivation, S : ensemble des échelles).

Projection dans l'espace Local Jet

x 7→ x = (aσij fσij (x))i+j≤r ;σ∈S

Dérivées gaussiennesmulti-échelles

f σij = f ? ∂i+jGσ

∂x i1∂x

j2

Local jet normalisé

aσij = σi+j

i+j+1

I Gσ est la fonction gaussienne 2d de variance σ2.

I σi+j est la normalisation scale space [Lindeberg 98].

I i + j + 1 est le nombre de dérivées d'ordre (i + j).


Local jets

L'espace LJ

Dérivées gaussiennes multi-échelles

f 1.000

f 1.010

f 1.001

f 1.020

f 1.011

f 1.002

f 4.000

f 4.010

f 4.001

f 4.020

f 4.011

f 4.002


Local jets

L'espace LJ

Le descripteur Local jet

L'utilisation du local jet comme vecteur descripteur dans unemesure de distance peut être interprété en termes d'approximationde la géométrie locale à partir de la formule de Taylor :

Original LJ ordre 0 LJ ordre 1 LJ ordre 2


Local jets

L'espace LJ

Distances usuelles

Distance mono-échelledσf (x, y) =

∑i+j≤r

(f σij (x)− f σij (y))2

Distance omni-échellesDSf (x, y) =

∑i+j≤r ,σ∈S

(f σij (x)− f σij (y))2

Semi-distance trans-échellesdSf (x, y) = min

(σ1,σ2)∈S2

∑i+j≤r

(f σ1ij (x)− f σ2ij (y))2


Local jets

L'espace LJ

Exemples de cartes de similarités

Pixel référence Mono-échelle Omni-échelles Trans-échelles


Local jets

L'espace LJ

Catégorisation géométrique locale

Un descripteurréduit peut êtreobtenu encatégorisant lelocal jet. Voir[Crosier 10].


Local jets

Codages et structures de données

Projection des données et représentation

I Les données images sont projetées dans l'espace descaractéristiques.

I Les vecteurs de caractéristiques sont collectés dans un arbre derecherche.

I Chaque vecteur de caractéristiques est associé à un pixel dansl'espace image.


Local jets

Codages et structures de données

Quanti�cation de l'espace de caractéristiques

I La taille de l'espace de caractéristiques peut être réduit parquanti�cation vectorielle.

I Chaque mot du dictionnaire est associé à un ensemble depixels dans l'espace image.


Traitement d'Image





Conclusions


Traitement d'Image

Filtrage NL-means

NL-means dans l'espace des caractéristiques

Le �ltre NL-means calcule une moyenne pondérée de la valeur dechaque pixel, où les poids sont fonctions de la similarité locale. Icion utilise simplement une distance dans l'espace LJ...

ω(u, v) = e− ||u−v||

2

h2

avec :||.|| une norme dans l'espace des caractéristiques.h un paramètre de décroissance.et on calcule la moyenne dans un voisinage de x dans l'espaceimage (Limited Range),ou dans un voisinage de x dans l'espace des caractéristiques(Unlimited range).


Traitement d'Image

Filtrage NL-means

Limited Range LJ-NL-Means

Les poids (dans l'espace LJ)sont calculés dans un voisinagede x dans l'espace image :

Limited range NL-means

f NLLR (x) =1

ζ(x)

∑y∈N (x)

f (y)ω(x, y)


Traitement d'Image

Filtrage NL-means

Unlimited Range LJ-NL-Means

Les poids (dans l'espace LJ)sont calculés dans un voisinagede x dans l'espace LJ :

Unlimited range NL-means

f NLUR (x) =1

ξ(x)

∑u∈W(x)

f (u)ω(x,u)


Traitement d'Image

Filtrage NL-means

Débruitage de Vidéo par Local jet NL-Means

Exemple : Filtrage

Local-Jet-NL-Means dans

un voisinage espace-temps

limité (couleur, ordre 2,

une seule échelle).


Traitement d'Image

Flot optique

Mouvement apparent dans l'espace des caractéristiques

Dans ce modèlel'estimation du �uxoptique s'exprimesimplement par unerecherche du plus prochevoisin dans l'espace descaractéristiques :

u(ft−1, ft , x) = arg minv∈Fft−1

dF (xft , v)


Traitement d'Image

Flot optique

In�nite range optical �ow

+ Simplicité conceptuelle+ Régularisation spatiale implicite+ Pas de limitation sur la vitesse- Complexité combinatoire


Traitement d'Image

Flot optique

Flux optique temps-réel par plus proche voisin dans l'espaceLG sur GPU

Un �ux optique dense et sans régularisation spatiale explicite peutêtre obtenu en implantant une version à portée limitée sur GPU :


Traitement d'Image

Détection de mouvement

Echantillonnage et consensus dans l'espace LJ

I On modélise le fondstatique (background) enéchantillonnant les valeursde chaque pixel dansl'espace du local jet.

I Les objets mobiles(Foreground) sontclassi�és selon unconsensus (vote).

I Le modèle de fondstatique est mis à jour enconséquence.


Traitement d'Image

Détection de mouvement

Résultats de la détection d'objets mobiles

I Espace des caractéristiques : Local jet d'ordre 2, une seule échelle ,3 couleurs.

I Quanti�cation vectorielle : dictionnaire de 3 000 mots.

I Nombre d'échantillons : M = 20.


Représentations visuelles





Conclusions



Singularités et modes de l'espace des caractéristiques

Singularités de l'espace des caractéristiques

La détection des points isolés de l'espace des caractéristiques : fusionner

la détection des points d'intérêt et le calcul des descripteurs associés.

Voir aussi [Kervrann 08].



Singularités et modes de l'espace des caractéristiques

Modes de l'espace des caractéristiques

Les modes (clusters) de l'espace des caractéristiques (voir [Burman 09]),

rétro-projetés dans l'espace image, correspondent aux grandes zones

homogènes, long contours rectilignes, ou éléments de texture régulière.



Local jets et transformées de Hough denses

Distribution relative au dictionnaire

La distribution des mots du dictionnaire est déjà une représentation

possible pour une image ou une catégorie visuelle. Voir par exemple

[Rubner 99].





Les dérivées multi-échelles quanti�ées peuvent être utilisées avecpro�t pour indexer un espace de paramètres dans une technique dedétection de formes paramétrées fondée sur l'accumulation (vote)dans l'espace des paramètres.

Argument du gradient Courbure de l'isophote Local jet quanti�é

(σ = 2) (σ = 2) (Ordre 2, 5 échelles)




Dérivées partielles et transformées de Hough 1-to-1

Approches traditionnelles

I éparses : Seules quelques points (contours, points clefs)votent.

I 1-to-many : Chaque point de l'espace image voteuniformément sur une surface de dimension n dans l'espacedes paramètres.

I many-to-1 : Chaque n-uplet de points de l'espace image votepour un unique point de l'espace des paramètres.




Dérivées partielles et transformées de Hough 1-to-1

TH fondée sur les dérivées partielles

I denses : Tous les points de l'espace image votent...

I censitaires : ...mais les votes sont pondérés !

I 1-to-1 : Chaque point de l'espace image vote pour un point del'espace des paramètres.




Transformées 1-to-1 : ordre 1

A l'ordre 1, la direction du gradient dé�nit la direction del'isophote, et donc l'équation de la droite éventuelle. Le poids duvote est le module du gradient.

gradient et droite poids du vote principaux votes





20 meilleures droites transformée (θ, ρ) 1-to-1





A l'ordre 2, la direction du gradient et la courbure de l'isophotedé�nissent le rayon et le centre du cercle osculateur à la courbeisophote et donc l'équation du cercle éventuel. Le poids du vote estla norme de Frobénius de la matrice hessienne.

gradient, courbure positive gradient, courbure négative poids du vote principaux votes





10 meilleures cercles transformée (x, y, ρ) 1-to-1 (coupe ρ = 19)



Modèles Implicites de Forme denses

Représentation des objets par R-Tables

Les approches existantes de transformées de Hough généraliséessont éparses : elles opèrent sur un ensemble de pointscaractéristiques (contours, points d'intérêt) [Leibe 04].

R-Table : {i , {~δji }j}i




R-Tables denses indexées par dérivées

Dans l'approche dense, les index i de la R-Table sont des dérivéesmultiéchelles quanti�ées, disponibles en tout point.

(o = 1;σ = 1.0) (o = 2;σ = 1.0) (o = 1;σ = 2.0) (o = 2;σ = 2.0)

R-Table pondérée : {i , {~δji , ωji }j}i




Transformée dense généralisée

Détection : pour tout point x, soitl(x) la mesure quanti�ée. Pourtoutes les occurences j de laR-Table associées à l(x), faire :

H(x + δjl(x))+ = ωj

l(x)


Conclusions





Conclusions


Conclusions

Conclusion

I GENERICITEI Le modèle comprend de nombreux opérateurs de traitement...I ...et recouvre les di�érents niveaux d'analyse.

I INTERET/INNOVATIONI Uni�cation des NL-Means, �ltres bilatéraux et autres...I Calcul du �ot optique par plus proche voisin.I Point d'intérêt par saillance statistique du descripteur.I Transformée de Hough dense et régulière.

I EFFICACITEI Réduction du descripteur d'apparence (Traitements).I Vote direct à partir de l'index du descripteur (Hough).


Conclusions

Travaux en cours / à faire

I EVALUATIONI Etude comparative.I Etude paramétrique.

I ACCELERATIONI Optimiser la taille du descripteur.I Régulariser et paralléliser la recherche du PPV.

I DETECTION ET RECONNAISSANCEI Modèles d'objets : généralisation et optimisation des R-Tables

denses.I Méthodes cumulatives : estimation de l'ego-mouvement,

détection des plans principaux.


Conclusions

Bibliographie (Pour en savoir plus)

[Manzanera 10] A. MANZANERALocal Jet Based Similarity for NL-Means FilteringInt. Conf. on Pattern Recognition 2668-2671 (2010)

[Manzanera 11] A. MANZANERALocal Jet Feature Space Framework for Image Processing andRepresentationInt. Conf. on Signal Image Technology and Internet Based Systems261-268 (2011)

[Manzanera 12] A. MANZANERADense Hough transforms on gray level images using multi-scalederivativesWorking document, ENSTA-ParisTech (2012)


Conclusions

Bibliographie (Concepts et modèles)

[Peyré 09] G. PEYREManifold Models for Signals and ImagesComputer Vision and Image Understanding 113(2), 249-260. (2009)

[Lindeberg 98] T. LINDEBERGFeature detection with automatic scale selectionInternational Journal of Computer Vision 30(2), 77-116. (1998)

[Koenderink 87] J.J. KOENDERINK and A.J. VAN DOORNRepresentation of Local Geometry in the Visual SystemBiological Cybernetics 55, 367-375. (1987)


Conclusions

Bibliographie (Bancs de �ltres et Codebooks)

[Freeman 91] W.T. FREEMAN and E.H. ADELSONThe design and use of Steerable FiltersIEEE Trans. on Pattern Analysis and Machine Intelligence 13(9),891-906. (1991)

[Crosier 10] M. CROSIER and L.D. GRIFFINUsing Basic Image Features for Texture Classi�cationInternational Journal of Computer Vision 88(3), 447-460. (2010)

[Rubner 99] Y. RUBNER and C. TOMASITexture-Based Image Retrieval Without SegmentationIEEE International Conference on Computer Vision, Kerkyra,Greece 1018-1024. (1999)


Conclusions

Bibliographie (Outils)

[Mount 97] D.M. MOUNT and S. ARYAANN: A Library for Approximate Nearest Neighbor SearchingCGC Workshop on Computational Geometry (1997)http://www.cs.umd.edu/~mount/ANN/

[Burman 09] P. BURMAN and W. POLONIKMultivariate mode hunting: Data analytic tools with measures ofsigni�canceJournal of Multivariate Analysis 100(6), 1198-1218. (2009)

[Van Vliet 98] L.J. VAN VLIET, I.T. YOUNG and P.W.VERBEEKRecursive Gaussian derivative �ltersProc. Int. Conf. on Pattern Recognition vol. 1, 509-514. (1998)

http://www.cs.umd.edu/~mount/ANN/


Conclusions

Bibliographie (NL-Means)

[Buades 05] A. BUADES, B. COLL and J.M. MORELA non-local algorithm for image denoisingProc. IEEE Conf. on Computer Vision and Pattern Recognition vol.2, 60-65. (2005)

[Orchard 08] J. ORCHARD, M. EBRAHIMI and A. WONGE�cient Non-Local Means Denoising using the SVDProc. Int. Conf. on Image Processing 1732-1735. (2008)

[Kervrann 08] C. KERVRANN and J. BOULANGERLocal adaptivity to variable smoothness for exemplar-based imagedenoising and representationInternational Journal of Computer Vision 79(1), 45-69. (2008)


Conclusions

Bibliographie (Détection de mouvement)

[Barnich 09] O. BARNICH and M. VAN DROGENBROECKViBe: a powerful random technique to estimate the background invideo sequencesInternational Conference on Acoustics, Speech, and SignalProcessing 945-948. (2009)

[Wang 07] H. WANG and D. SUTERA consensus-based method for tracking: Modelling backgroundscenario and foreground appearancePattern Recognition 40(3), 1091-1105. (2007)

[Kim 04] K. KIM, T.H. CHALIDABHONGSE, D. HARDWOODand L. DAVISBackground modeling and subtraction by codebook constructionProc. Int. Conf. on Image Processing 3061-3064. (2004)


Conclusions

Bibliographie (Transformées de Hough)

[O'Gorman 76] F. O'GORMAN AND B. CLOWESFinding picture edges through collinearity of feature pointsIEEE Trans. on Computers C-25 449-456 (1976)

[Leibe 04] B. LEIBE, A. LEONARDIS and B. SCHIELECombined object categorization and segmentation with an implicitshape modelECCV Workshop on Statistical Learning in Computer Vision (2004)

[Valenti 08] R. VALENTI and T. GEVERSAccurate eye center location and tracking using isophote curvatureInt. Conf. on Computer Vision and Pattern Recognition (2008)

Documents

Modèles Génériques de Représentation et Traitement … · A. Manzanera - Séminaire LRDE 2012 1/50 Modèles Génériques de Représentation et raitementT des Images Antoine Manzanera