Archives de catégorie : [:en]algorithms[:fr]algorithmes

Axe 6 : Algorithme d’optimisation : méthodes déterministes et stochastiques

En géométrie de l’information, les données statistiques prennent leurs valeurs dans des ensembles munis d’une structure de variété riemannienne, de dimension finie ou infinie. Les estimateurs de quantités relatives à ces données sont des moyennes, des médianes, ou plus généralement des p-moyennes de ces données. Des algorithmes stochastiques pour trouver ces p-moyennes sont très utiles pour toutes les applications pratiques qui ont été développés dans les publications citées ci-dessous. On peut en particulier citer des applications au traitement des signaux radar stationnaires. Un enjeu très important est de pouvoir considérer des signaux non stationnaires. Pour cela il faut pouvoir travailler sur des espaces de chemins dans des variétés riemanniennes, et développer une bonne notion de métrique, de distance, et de moyenne pour ces chemins.

Des nouveaux algorithmes stochastiques de type Robbins-Monro sont également proposés afin d’estimer plus efficacement les paramètres inconnus de modèles de déformation. Ces procédures d’estimation sont mises en oeuvre sur des données réelle d’ECG afin de détecter des problèmes d’arythmie cardiaque.

Les méthodes proximales ont connu un très grand succès en traitement d’images pour proposer des algorithmes efficaces pour calculer les solutions des problèmes considérées. Un thème majeur de l’équipe est l’étude de la convergence de tels algorithmes, de leur vitesse, et de leur robustesse aux erreurs.

Estimation non paramétrique du bruit

Afin de fournir un algorithme de débruitage automatique, nous avons développé une méthode automatique d’estimation du bruit dans une image, basée sur la détection non paramétrique des zones homogènes. Les régions homogènes de l’image sont détectées à l’aide du coefficient de corrélation de rang de Kendall [1]. Evalué sur des séquences de pixels voisins, il permet de mesurer la dépendance entre voisins et donc la présence de structure au sein d’un bloc de l’image.
Ce test est non paramétrique, donc la performance du détecteur est indépendante de la distribution statistique du bruit. Une fois les zones homogènes détectées, la fonction de niveau de bruit, c’est-à-dire la fonction reliant la variance du bruit à l’intensité sous-jacente de l’image, est estimée sous forme d’un polynôme du second degré à l’aide de la minimisation de l’erreur \ell^1 des statistiques issues de ces régions homogènes.

Codes Matlab pour l’estimation de bruit

Publications associées :

– C. Sutour, C.-A. Deledalle et J.-F. Aujol. Estimation of the noise level function based on a non-parametric detection of homogeneous image regions. Submitted to Siam Journal on Imaging Sciences, 2015.

– C. Sutour, C.-A. Deledalle et J.-F. Aujol. Estimation du niveau de bruit par la détection non paramétrique de zones homogènes. Submitted to Gretsi, 2015.

Références

[1] Buades, A., Coll, B., and Morel, J.-M. (2005). A review of image denoising algorithms, with a new one. Multiscale Modeling and Simulation, 4(2): 490–530.

Régularisation adaptative des NL-means

L’algorithme de débruitage mis en place repose sur une régularisation adaptative de l’algorithme des NL-means [1]. Le modèle proposé est le suivant :

(1)   \begin{align*} u_{\text{TVNL}} &= \underset{u \in \mathbb{R}^N}{\operatorname{argmin}} \sum_{i \in \Omega} \lambda_i \left(u_i-u^{\text{NL}}_i\right)^2 + \text{TV}(u),\\ \lambda_i &= \gamma \left(\frac{\sigma_{\text{residual}}(i)}{\sigma_{\text{noise}}(i)}\right)^{-1} = \gamma \Big(\sum_j w_{i,j}^2\Big)^{-1/2}. \end{align*}

où u_{\NL} est la solution obtenue par l’algorithme de NL-means, TV désigne la variation totale de l’image et w_{i,j} est le poids qui mesure la similarité entre le patch d’indice i et le patch d’indice j dans l’algorithme des NL-means. Le rapport \left(\frac{\sigma_{\text{residual}}(i)}{\sigma_{\text{noise}}(i)}\right)^{-1} traduit la réduction de la variance du bruit assurée par les NL-means. Cette formulation permet de régulariser localement et de façon adaptative la solution u_{\NL} obtenue par les NL-means, en se basant sur un indice de confiance \lambda_i qui traduit la qualité du débruitage effectué par les NL-means.

Ce modèle s’adapte aux différentes statistiques de bruit de la famille exponentielle (Gaussien, Poisson, multiplicatif…). Il est également adapté au débruitage vidéo grâce à l’utilisation de patchs 3D combinée à une régularisation TV spatio-temporelle.

Codes Matlab pour RNL

Résultats et comparaisons de débruitage de vidéos avec R-NL

Publications asosciées :
– C. Sutour, C.-A. Deledalle et J.-F. Aujol. Adaptive regularization of the NL-means : Application to image and video denoising. IEEE Transactions on image processing, vol. 23(8) : 3506-3521, 2014.

– C. Sutour, J.-F. Aujol, C.-A. Deledalle et J.-P. Domenger. Adaptive regularization of the NL-means for video denoising. International Conference on Image Processing (ICIP), pages 2704–2708. IEEE, 2014.

– C. Sutour, J.-F. Aujol et C.-A. Deledalle. TV-NL : Une coopération entre les NL-means et les méthodes variationnelles. Gretsi, 2013.

Références

[1] Buades, A., Coll, B., and Morel, J.-M. (2005). A review of image denoising algorithms, with a new one. Multiscale Modeling and Simulation, 4(2): 490–530.

Colorisation d’images

La colorisation est un enjeu important pour la restauration des documents anciens par exemple, mais également pour l’industrie du divertissement. Les méthodes se divisent en deux catégories, les méthodes manuelles et les méthodes dites basée-exemple pour lesquelles l’utilisateur fournit une image en couleur qui sert de source d’information. La comparaison des textures permet d’extraire la couleur. Il faut ensuite régulariser, ce que l’on effectue dans notre cas par la minimisation d’une fonctionnelle non convexe. Proposer un modèle raisonnable pour la colorisation ainsi qu’un algorithme efficace pour minimiser la fonctionnelle proposée a constitué l’essentiel du début de la thèse.

Néanmoins, les méthodes basée-exemple présentent une difficulté qui est la recherche d’une image source pertinente. Il est difficile de trouver l’image source pertinente pour une colorisation donnée, et la méthode échoue fréquemment, il suffit par exemple qu’une couleur ne soit pas présente dans l’image source, ou encore d’avoir deux parties lisses ou des textures similaires devant exprimer une couleur différente. Afin d’éviter ces écueils, nous avons proposé une méthode de colorisation dite collaborative, qui se présente comme une méthode interactive dans laquelle l’utilisateur tiens un rôle de superviseur du résultat. Il a la possibilité d’intégrer des points de couleurs dans le résultat là où le résultat ne lui semble pas satisfaisant. Cette nouvelle information est intégrée dans le processus en exploitant la non convexité du modèle.

Illustration de Colorisation

Stein Unbiased GrAdient estimator of the Risk

Les algorithmes de régularisation variationnelle résolvant des problèmes inverses mal posés impliquent généralement des opérateurs qui dépendent d’un ensemble de paramètres continus. Lorsque ces opérateurs bénéficient d’une certaine régularité (locale), ces paramètres peuvent être sélectionnés en utilisant l’estimateur non-biasé de Stein (SURE). Bien que cette sélection est généralement effectuée par une recherche exhaustive, nous abordons dans ce travail le problème de l’utilisation du SURE pour l’optimisation efficace d’une collection de paramètres continus du modèle. Lorsque l’on considère des regularizations non lisses, comme la norme l1 populaire correspondant au seuillage doux, le SURE est une fonction discontinue de paramètres qui empêchent l’utilisation de techniques d’optimisation de descente de gradient. Au lieu de cela, nous nous concentrons sur une approximation du SURE sur la base de différences finies comme proposé dans (Ramani et al., 2008). Sous des hypothèses modérées sur l’estimateur, nous montrons que cette approximation est une fonction faiblement différentiables des paramètres et que son gradient faible (SUGAR), fournit asymptotiquement (par rapport à la dimension de données) une estimation non biaisée du gradient du risque. En outre, dans le cas particulier de seuillage doux, SUGAR est avéré être aussi un estimateur consistent. Le SUGAR peut alors être utilisé comme une base pour effectuer une optimisation de type quasi-Newton. Le calcul de SUGAR repose sur la forme explicite de la différenciation (faible) de la fonction non-lisse. Nous fournissons son expression pour une large classe de méthodes proximales itératives et appliquons notre stratégie à des régularisations impliquant des pénalités convexes non lisse. Des illustrations sur divers problèmes de restauration d’image et de complétion de matrices sont donnés.

Publications et codes sources associés :

Charles-Alban Deledalle, Samuel Vaiter, Gabriel Peyré and Jalal Fadili
Stein Unbiased GrAdient estimator of the Risk (SUGAR) for multiple parameter selection,
Technical report HAL, hal-00987295 (HAL)

MATLAB source codes available from GitHub.

Recalage multi-modal basé contours

Afin d’effectuer la fusion multi-modale entre les images obtenues à partir d’un intensificateur de lumière (LI) et IR (images infra-rouge), fournissant ainsi des informations multi-sources pour le pilote, il est nécessaire d’effectuer le recalage entre les deux modalités. Elles reflètent des propriétés différentes de la scène, de sorte que la méthode choisie est basée sur l’information géométrique et les bords de chaque image.

Le but est de trouver la transformation T ^ * qui transfère l’image IL dans le cadre de référence de l’image IR en minimisant l’énergie suivante:

(1)   \begin{align*} T^* &= \underset{T}{\operatorname{argmax}} \; C(T)\\ \text{with} \quad C(T) &= - \int_{\Omega} \vert \nabla I_L(T(X)) \cdot \nabla I_R(X)\vert \mathrm dX \end{align*}

Cette mesure est basée sur les contours de chaque image, et elle prend en compte les contours des deux modalitites, ce qui la rend insensible aux valeurs aberrantes.
Grâce à un schéma d’optimisation à base de descente de gradient, il est possible d’évaluer rapidement la transformation optimale entre les deux modalités.

Résultats de recalage sur des données réelles

Related papers:
C. Sutour, J.-F. Aujol, C.-A. Deledalle et B.D. De-Senneville. Edge-based multi-modal registration and application for night vision devices. Journal of Mathematical Imaging and Vision, pages 1–20, 2015.

NL-SAR: Non-Local framework for (Pol)(In)SAR denoising

Logiciel ouvert distribué sous licence CeCILL pour l’estimation adaptative et non-locale d’images (Pol)(In)SAR (réduction de speckle). Interface disponible en ligne de commande, IDL, Matlab, Python et en tant que bibliothèque dynamique C. Plug in pour PolSARpro disponible.

Téléchargement ici