44
Eric Andres et Philippe Carré David Helbert DART - Discrete Analytical Ridgelet Transform Laboratoire IRCOM-SIC

DART - Discrete Analytical Ridgelet Transform

  • Upload
    snowy

  • View
    45

  • Download
    0

Embed Size (px)

DESCRIPTION

DART - Discrete Analytical Ridgelet Transform. Laboratoire IRCOM-SIC. Eric Andres et Philippe Carré David Helbert. Sommaire. Introduction Contexte DART 2D Exemple d’application 2D DART 3D Exemples d’applications Conclusion. Introduction. - PowerPoint PPT Presentation

Citation preview

Page 1: DART - Discrete Analytical Ridgelet Transform

Eric Andres et Philippe Carré

David Helbert

DART - Discrete Analytical Ridgelet Transform

Laboratoire IRCOM-SIC

Page 2: DART - Discrete Analytical Ridgelet Transform

Sommaire

IntroductionContexteDART 2DExemple d’application 2DDART 3DExemples d’applicationsConclusion

Page 3: DART - Discrete Analytical Ridgelet Transform

Introduction

Une nouvelle implantation de la transformée Ridgelet avec des droites discrètes analytiques est proposée : DART

But de la transformation Ridgelet : permettre une analyse « optimale » des ruptures linéaires dans une image.

Problème : peu d’implantations discrètes, pas forcément efficaces ou simples à mettre en œuvre.

Notre but : Proposer une transformation ridgelet aisée à implanter et inversible (à propriétés contrôlées).

Un des domaines d’applications privilégié semble être le débruitage

Page 4: DART - Discrete Analytical Ridgelet Transform

Contexte : transformationTransformation d’un signal nD : changement de base permettant d’obtenir une autre représentation des données (démarche non structurelle)

1. Définition de fonctions (formes) constituant la base

2. Mesures de ressemblances entre les données et les fonctions de bases Transformée (produit scalaire)

Fourier

But de la nouvelle représentation

Extraire d’une façon optimale l’information présente dans les données

Page 5: DART - Discrete Analytical Ridgelet Transform

Contexte : continue vs. discret

Transformation continue

Fonctions de base continues Discrétisation de l’intégrale

Application aux données discrètes •Non respect des propriétés de la base

•Complexité algorithme

•Opération adjointe absente

Transformation discrete

Fonctions de base discrètes

•Représentation orthogonale

•Algorithme rapide

•Opération adjointe parfaite

Page 6: DART - Discrete Analytical Ridgelet Transform

Contexte : ondelette

-20 0 20-0.05

0

0.05

0.1

Fréquence : 0.15, Longueur : 21

-20 0 20-0.05

0

0.05

0.1

Fréquence : 0.05, Longueur : 61

Idée•Définir des fonctions de bases localisées spatialement et associées à

une fréquence d ’oscilation précise

•Adapter la taille des fenêtres en fonction de la fréquence étudiée

Construction de bases discrètes orthogonales avec reconstruction

Page 7: DART - Discrete Analytical Ridgelet Transform

Sommaire

IntroductionContexteDART 2DExemple d’application 2DDART 3DExemples d’applicationsConclusion

Page 8: DART - Discrete Analytical Ridgelet Transform

Définition de la transformation Ridgelet 2D

Signal Représentation ondelettes

Contrairement à Fourier, les ondelettes sont très efficaces pour représenter / analyser des singularités ponctuelles

Mais nettement moins efficace pour représenter des singularités linéaires

Page 9: DART - Discrete Analytical Ridgelet Transform

[Candès98]

bord

ImageDomaine de

Radon

Point

Transformée ondelette

Transformée de Radon

Domaine des

RidgeletsDomaine de

Radon

Idée : en 2D, les points et les droites sont liées via la transformation de Radon

La transformation Ridgelet a été créé spécifiquement pour représenter efficacement les arêtes dans une image.

Définition de la transformation Ridgelet 2D

Page 10: DART - Discrete Analytical Ridgelet Transform

Les coefficients ridgelet sont donnés par une transformation ondelette 1D des projections de Radon

Définition de la transformation Ridgelet 2D

Page 11: DART - Discrete Analytical Ridgelet Transform

La transformée de Radon

Définir les lignes radiales

passant par l’origine de

l’image

Transformée de Fourier

2D de l’image

Transformée de Fourier 1D

inverse le long des lignes

Somme des pixels le long d’un ensemble de lignes

Définition de la transformation Ridgelet 2D

Stratégie classique Stratégie de Fourier

Page 12: DART - Discrete Analytical Ridgelet Transform

1. Calcul de la transformée de Radon discrète : Difficile à

réaliser.

2. Appliquer une transformée discrète en ondelettes sur chaque

projection : facile à implanter, stable et inversible avec les

bancs de filtres.

Stratégie pour la transformation Ridgelet 2D discrète

Page 13: DART - Discrete Analytical Ridgelet Transform

Stratégie de Lausanne

[Do&Vetterli2001][Do&Vetterli2001]

Somme des pixels le long d’un ensemble de lignes

Décomposition du domaine Décomposition du domaine de Fourier 3D en 3 cônesde Fourier 3D en 3 cônes

Stratégie de Stanford

Conversion de la grille cartésienne en une grille Conversion de la grille cartésienne en une grille pseudo-polairepseudo-polaire

[Averbuch Coifman Donoho Israeli Waldén2000][Averbuch Coifman Donoho Israeli Waldén2000]

iFFT 1D le long des lignes définies dans le domaine de Fourier

Page 14: DART - Discrete Analytical Ridgelet Transform

Sommaire

IntroductionContexteDART 2DExemple d’application 2DDART 3DExemples d’applicationsConclusion

Page 15: DART - Discrete Analytical Ridgelet Transform

Stratégie de Poitiers

Stratégie de calcul de la DART 2D :

Coefficients de Fourier

iFFT

FFT 2D Définition des

droites discrètes

Projection de l’image

Extraction des coefficients de Fourier

Transformée ondelette 1D le long des projections

Ridgelet

[Carré&Andres2002][Carré&Andres2002]Extraction des coefficients de Fourier

Page 16: DART - Discrete Analytical Ridgelet Transform

16

Transformation de Radon analytique discrète

DART : Stratégie de Fourier pour la transformation de Radon

Droites L[p,q] sont définies à l’aide de géométrie analytique discrète

Nous avons besoin d’une droite discrète avec : • une symétrie centrale, • formant une « bonne » approximation de la

droite euclidienne.

0

0

f1

f2

Domaine de FourierDomaine de Fourier

Page 17: DART - Discrete Analytical Ridgelet Transform

17

Les droites analytiques discrètes que nous avons utilisées sont définies par :

avec [p,q] la direction de projection de Radon et , une fonction de (p,q), l’épaisseur arithmétique

Droites naïves fermées (8-connexes)

Droites supercouvertures (4-connexes)

Droites pythagoriciennes fermées (8-connexes)

Transformation de Radon analytique discrète

Page 18: DART - Discrete Analytical Ridgelet Transform

0

0

Nous avons besoin d’un ensemble de directions [p,q] qui permettent une représentation complète (une couverture du domaine de Fourier)

Transformation de Radon analytique discrète

Page 19: DART - Discrete Analytical Ridgelet Transform

Le facteur de redondance varie avec l’épaisseur arithmétique de la droite

(par exemple 2.05 pour les droites naïves fermées et 3.05 pour les droites supercouvertures)

Naïf Supercouverture

Transformation de Radon analytique discrète

Page 20: DART - Discrete Analytical Ridgelet Transform

Coefficients de Fourier

iFFT 1D

FFT 2D

Définition des

droites discrètes

Projection de l’image

Ridgelet

DART Inverse

Coeffs ridgelets modifiés

Traitements (débruitage)

FFT 1D

iFFT 2D

Remise en place des coeffs de Fourier

Extraction des coefficients de Fourier

Transformée ondelette 1D le long des projections

Page 21: DART - Discrete Analytical Ridgelet Transform

SommaireIntroductionContexteDART 2DExemple d’application 2DDART 3DExemples d’applicationsConclusion

Page 22: DART - Discrete Analytical Ridgelet Transform

Pourquoi la DART est performante en débruitage

La transformée Ridgelet code efficacement les contours rectilignes

Droite discrète 1

Droite discrète 2

Pixels couverts par les deux

droites discrètes

Domaine de Fourier 2D couverts par deux droites analytiques discrètes

La DART est une transformée redondante

Répétition des informations dans le domaine des Ridgelets

Page 23: DART - Discrete Analytical Ridgelet Transform

Stratégie pour le débruitageStratégie pour le débruitage

• Seuillage des coefficients Ridgelet• Calcul de la DART inverse.

Le seuillage utilise une décomposition en ondelettes non-décimée

La variance du bruit est estimée par la valeur médiane absolue des coefficients de la première échelle

d ’ondelette pour chaque projection radiale

Paramètre de DonohoParamètre de Donoho

Page 24: DART - Discrete Analytical Ridgelet Transform

24

Influence de l’épaisseur analytique sur le débruitage

(a) (b) (SNR=15 dB)

naïve pythagoricienne supercouverture

Page 25: DART - Discrete Analytical Ridgelet Transform

Image Femme + bruit (=60)

NoisyNoisy Fwt : ondelettes orthoFwt : ondelettes ortho Uwt : ondelettes redondUwt : ondelettes redond

EPFLEPFL DARTDART LDARTLDART

Page 26: DART - Discrete Analytical Ridgelet Transform

Image Maison + bruit (=70)

NoisyNoisy Classical WaveletClassical Wavelet Undecimated WaveletUndecimated Wavelet

EPFLEPFL DARTDART LDARTLDART

Page 27: DART - Discrete Analytical Ridgelet Transform

DART pas efficace pour toutes les applications

Reconstruction partielle d ’une image artificielle à partir des 512 plus grands coefficients

OndeletteOndelette EPFLEPFL DARTDART

La redondance de la DART n’est pas un avantage ici

Page 28: DART - Discrete Analytical Ridgelet Transform

SommaireIntroductionContexteDART 2DExemple d’application 2DDART 3DExemples d’applicationsConclusion

Page 29: DART - Discrete Analytical Ridgelet Transform

Définition de la DART 3D

La transformée Radon 3D de s est définie par :

321321321 sinsincoscoscos,,,,3

dxdxdxtxxxxxxstRR

s

La transformée de Radon 3D

Définir les lignes radiales passant par l’origine de l’image

Transformée de Fourier 3D de

l’image

Transformée de Fourier 1D

inverse le long des lignes

Définition de la transformée Ridgelet 3DDéfinition de la transformée Ridgelet 3D

),,()(),,(²

,dttRtbar

R

sba

ondelettefonction et de 3DRadon de ée transformla avec ba,sRs bord

Image 3DDomaine de

Radon

Point

Transformée ondelette

Transformée de Radon 3D

Domaine des

RidgeletsDomaine de Radon

Page 30: DART - Discrete Analytical Ridgelet Transform

La transformée de Radon discrète 3D

1. Calcul de la transformée de Fourier 3D de l'image

3. Calcul de la transformée de Fourier 1D inverse pour chaque droite

Stratégie de calcul de la transformée de Radon discrète 3D :

2. Définition des droites discrètes 3D passant par l'origine pour chaque paramètre angulaire θ et

Page 31: DART - Discrete Analytical Ridgelet Transform

La transformée de Radon discrète 3D

rqprqprqpL ozxoyzoxyrqp ,,,,,,321 ,,,,

2/,,,, 13 pyqxZzyxrqpoxy

2/,,,, 23 qzryZzyxrqpoyz

2/,,,, 33 rxpzZzyxrqpozx

Définition d’une droite analytique discrète 3D

Droite naïve Droite supercouvertureDroite pythagoricienne

Page 32: DART - Discrete Analytical Ridgelet Transform

La transformée de Radon discrète 3DCouverture du volume par les droites

discrètes 3D

=> Domaine de Fourier 3D couvert par des droites supercouvertures

=> Domaine de Fourier 3D non couvert par des droites naïves et pythagoriciennes

Page 33: DART - Discrete Analytical Ridgelet Transform

Autre approche pour la Radon discrète 3D

1. Calcul de la transformée de Fourier 3D de l'image

4. Calcul de la transformée de Fourier 1D inverse pour chaque droite

3. Couvrir le plan par des droites analytiques discrètes 2D passant par l’origine et définies pour chaque paramètre angulaire

2. Définir des plans discrets passant par l’origine pour chaque paramètre angulaire

Page 34: DART - Discrete Analytical Ridgelet Transform

Définition des objets analytiques discrets

Les plans discrets :

Autre approche pour la Radon discrète 3D

x

yz, t

naïf pythagoricien supercouverture

Page 35: DART - Discrete Analytical Ridgelet Transform

Définition des objets analytiques discrets

Les droites discrètes 3D au final :

Autre approche pour la Radon discrète 3D

La projection du plan est pavé de droites 2D

xz

y

Page 36: DART - Discrete Analytical Ridgelet Transform

SommaireIntroductionContexteDART 2DExemple d’application 2DDART 3DExemples d’applicationsConclusion

Page 37: DART - Discrete Analytical Ridgelet Transform

Débruitage d’une image synthétique

Image originale Image bruitée

Image débruitée par une transformée en ondelette

Image débruitée par une DART

SNR=13,45 dB SNR=18,62 dB

SNR=9,62 dB

Page 38: DART - Discrete Analytical Ridgelet Transform

Débruitage d’une Image à Résonance Magnétique (1/2)

Image débruitée par une DART

Image originale Image bruitée

Image débruitée par une transformée ondelette

Page 39: DART - Discrete Analytical Ridgelet Transform

Débruitage d’une Image à Résonance Magnétique (2/2)

Image débruitée par une DART

Image originale Image bruitée

Image débruitée par une transformée en ondelette

Page 40: DART - Discrete Analytical Ridgelet Transform

Débruitage de la vidéo 1 (1/2)

SNR=0.051 dB

Vidéo originale Vidéo bruitée

Page 41: DART - Discrete Analytical Ridgelet Transform

Débruitage de la vidéo 1 (2/2)

SNR=6.17 dB SNR=7.47 dB

Vidéo débruitée par une DART

Vidéo débruitée par une transformée en ondelette redond.

Page 42: DART - Discrete Analytical Ridgelet Transform

Conclusion (1/3)

• La DART est facile à mettre en œuvre

• facile à inverser

• paramétrable avec l ’épaisseur arithmétique

• illustre l’intérêt de la géométrie discrète

• et constitue un bon outil de débruitage en 2D, 3D et ? 4D

Page 43: DART - Discrete Analytical Ridgelet Transform

Conclusion (2/3)Les perspectives

- Droites analytiques discrètes 3D plus fines pour limiter la redondance de la DART et ainsi obtenir de meilleurs résultats en reconstruction partielle

- Droites analytiques discrètes 3D plus épaisses pour augmenter la redondance de la DART et ainsi obtenir de meilleurs résultats en débruitage

- Loi d’interpolation pour pallier la non-couverture du domaine de Fourier par les droites 3D naïves et pythagoriciennes

Page 44: DART - Discrete Analytical Ridgelet Transform

Conclusion (3/3)La DART à fenêtres

DART 3D sur toutes les fenêtres

TraitementDART 3D inverse

sur toutes les fenêtres

Image 3D reconstruite