Discussion :

[fran_ls95]

Bonjour à tous,

Je suis actuellement en licence mécanique et j'ai un sujet de traitement d'image à réaliser. Mes connaissances en traitement d'images sont limités, même si je me suis renseigné sur les différents cours présent sur ce forum ainsi qu’ailleurs.

Mon problème est le suivant: Je dois déterminer un noyau permettant de calculer le Laplacien d'une image et le raisonnement doit être basé les différences finies. Cependant je ne connais que mon point de départ qui est la formule des différences finies
et dont je ne sais pas comment l'exploitée ainsi que mon point d'arrivée (Noyau).

Merci d'avance pour votre aide !


Base sur laquelle je m'appuis:

[BeanzMaster]

Bonjour

tu peux passer par un noyau de convolution -->produit de convolution
cf cette discussion et celle-la

Je te conseil également de lire cet excellent article

A+

Jérôme

[fran_ls95]

@BeanzMaster

Déja merci de ta réponse et de ton aide !

J'ai déja eu connaissance des liens que tu m'as cité dans ton post précèdent. En effet j'ai un peu ces dernières semaines, écumé les différents sujets qui abordent le traitement d'image, dans le but de répondre à ma problématique.

Je suis arrivé au constant, que soit les différents sujets ne sont pas assez explicite dans leur approche mathématiques, soit mon bagage mathématiques n'est pas assez solide pour en comprendre les cheminement et aboutissants. J'ai une préférence pour la deuxième options.

J'essaierai par la suite, si je trouve la réponse à ma problématique, de la retranscrire sur ce post.

A bientôt

François

[wiwaxia]

Bonjour,

... j'ai un peu ces dernières semaines, écumé les différents sujets qui abordent le traitement d'image, dans le but de répondre à ma problématique ... / ... les différents sujets ne sont pas assez explicite dans leur approche mathématiques,

Pour obtenir les expressions approchées des produits de convolution, il suffit de faire intervenir le développement de Taylor-Mac Laurin au 4me ordre dans le cas d'une fonction de deux variables, au voisinage du point central (0, 0) que l'on prendra pour origine.
La difficulté réside dans la lourdeur de l'expression, qui contraint à l'emploi d'une notation condensée pour les diverses dérivées partielles (premières, secondes, tierces et quartes); avec les conventions:

D_mn = (∂^m+nU(0, 0)/∂x^m∂yⁿ) , D_m0 = ∂^mU(0, 0)/∂x^m , D_0n = ∂ⁿU(0, 0)/∂yⁿ ,

il vient pour une fonction U(x, y) 4 fois dérivable au voisinage de l'origine:

U(x, y) = U(0, 0) + D₁₀.x + D₀₁.y + (1/2!)(D₂₀.x² + 2D₁₁.xy + D₀₂.y²) + ...
... + (1/3!)(D₃₀.x³ + 3D₂₁.x²y + 3D₁₂.xy² + D₀₃.y³) + ...
... + (1/4!)(D₄₀.x⁴ + 4D₃₁.x³y + 6D₂₂.x²y² + 4D₁₃.xy³ + D₀₄.y⁴) + r⁴ε(r, x/r, y/r)

Le document que tu cites

donne du laplacien une présentation simple mais très claire; il intervient deux matrices élémentaires:

pour lesquelles les combinaisons linéaires correspondantes conduisent à la valeur locale en (0, 0) du laplacien de la fonction U(x, y):

ΔU = (∂²U/∂x²) + (∂²U/∂y²) .

On considère en effet les valeurs locales de la fonction U(x, y) aux noeuds d'un réseau dont le pas (h) correspond à l'arête d'un pixel, et dont les coordonnées valent (0) ou (± h):

On obtient ainsi
a) à partir de la première matrice (M₁) la somme:

S₁ = -4U(0, 0) + U(h, 0) + U(-h, 0) + U(0, h) + U(0, -h)

dont le calcul à l'aide du développement donné plus haut conduit à l'expression:

S₁ ~ h².(D₂₀ + D₀₂) + (h⁴/12)(D₄₀ + D₀₄)

- les termes de rang impair (en x, y, x³, x²y ... etc), entre autres, disparaissent systématiquement;
a) à partir de la seconde (M₂) la somme:

S₂ = -4U(0, 0) + U(h, h) + U(h, -h) + U(-h, -h) + U(-h, h)

qui donne cette fois:

S₂ ~ 2h².(D₂₀ + D₀₂) + (h⁴/6)(D₄₀ + D₀₄ + 6D₂₂) ;

Soit finalement, compte tenu de ce que h vaut 1:

S₁ ~ ΔU + (1/12)(D₄₀ + D₀₄) ,
S₂ ~ 2.ΔU + (1/6)(D₄₀ + D₀₄ + 6D₂₂) .

Plus généralement, toute combinaison linéaire des deux matrices (M₁, M₂) donne aussi une valeur approchée proportionnelle au laplacien, à l'exception toutefois du cas très particulier:

M° = M₂ - 2.M₁

auquel correspond la somme:

S° = S₂ - 2*S₁ = D₂₂ = ∂⁴U(0, 0)/∂x²∂y² .

Calculs à vérifier.

[wiwaxia]

Par curiosité, j'ai regardé ce que donnait le traitement d'un portrait en noir et blanc.

Les transformées obtenues apparaissent assez semblables dans le cas des deux premières matrices (M₁, M₂):

Le résultat est nettement plus flou dans celui de la dernière matrice (M₀), qui ne représente plus un laplacien:

Les sommes d'indices de couleur calculées sont encadrées par deux bornes de signes opposés:

Gmin <= g <= Gmax ,

dont la valeur dépend de de l'image initiale.
Les valeurs proches de la partie centrale (g ~ 0 , points verts) sont très largement majoritaires.
Les points rouges (g ~ Gmax) et bleus (g ~ Gmin), très rares, ne peuvent être aperçus qu'en éliminant tous les autres.

[wiwaxia]

La sélection des valeurs extrêmes de (g): (g > Lim1) ou (g < Lim2) confirme la forte concentration des valeurs autour de zéro; il faut, pour qu'un dessin lisible apparaisse, s'en tenir à des frontières relativement basses:

# Lim1 = 0.1 * Gmax (points rouges) ,
# Lim2 = 0.1 * Gmin (points bleus) ;

Il n'apparaît pas de couleurs séparées, mais une teinte unique intermédiaire (violette); les points de couleurs opposées sont donc regroupés d'une manière très resserrée, ce que l'on observe sans difficulté par agrandissement des images.

Voici les images résultant d'une petite modification du programme, et correspondant aux mêmes matrices (M₁, M₂) et (M₀).

M₁_
M₂_

M₀_

[BeanzMaster]

Salut intéressant comme d'hab

En appliquant les filtres j'obtient (à l'oeil) des résultats un peu différents (et qui me semble être bon). Qu'elle en est la cause à ton avis ?









Merci

A+

[wiwaxia]

Bonjour,

... En appliquant les filtres j'obtiens (à l'oeil) des résultats un peu différents (et qui me semblent être bons). Qu'elle en est la cause à ton avis ? ...

Que les résultats soient "bons", ce n'est peut-être pas le critère le mieux approprié parce qu'une discussion peut s'engager sur des points de vue différents:
a) L'algorithme de synthèse est-il correct ? Aucun doute là-dessus.
b) Les bords de l'image ressortent-ils suffisamment contrastés ? C'est l'aspect graphique en principe recherché, qui s'apprécie d'un simple coup d'oeil.
c) S'agit-il d'une belle image ? C'est l'aspect esthétique, incontournable dans le cas d'un portrait (et a fortiori dans le cas d'un très beau visage).

Il intervient de plus un facteur inconnu en ce qui concerne la traduction graphique du calcul du laplacien: la luminance des pixels clairs est-elle fonction croissante de la combinaison linéaire (g) calculée ?

# par exemple: Pixel(i, j) = (m, m, m) avec m = Round(255*g/Gmax)

Ou n'a-t-on retenu que les valeurs suffisamment élevées pour le tracé des points ?

# par les instructions du type:si (Abs(g)>Seuil) alors Pixel(i, j) = (255, 255, 255) sinon Pixel(i, j) = (0, 0, 0) ...

L'examen des images très agrandies conduit à retenir la première hypothèse, sans exclure une possibilité d'écrêtage:

# Pixel(i, j) = (m, m, m) avec m = Round(K*g) et si (m>255) alors m= 255
_{(ce baragouin est vraiment affreux)}

et l'on doit de plus supposer, pour que la comparaison des 4 images soit possible, que le même facteur de proportionnalité (K) intervient dans leur calcul; toi seul peux apporter sur ce point un complément d'information.

Les matrices carrées d'ordre 3 utilisées ici sont des matrices symétriques à éléments réels, centrosymétriques et à somme nulle (étendue à tous leurs éléments); elles constituent un espace vectoriel de dimension deux, et résultent toutes de la combinaison linéaire:

Les sommes auxquelles elles conduisent s'expriment en fonction des mêmes coefficients (en raison de la linéarité du produit matriciel):

S(a, b) = a*S₁ + b*S₂, avec S₁ ~ ΔU et S₂ ~ 2*ΔU ,
d'où: S(a, b) = (a + 2*b)*ΔU .

Les images successivement produites correspondent aux coefficients suivants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
                                (a + 2*b)
Image I      a = -1    b =  0      -1
Image II     a = -1    b = -1      -3
Image III    a =  1    b =  0       1
Image IV     a =  0    b =  1       2

Seule compte la valeur absolue |a + 2*b| du coefficient affectant la valeur locale du laplacien; il se confirme ainsi
a) que les images (I) et (III) sont d'aspect équivalent, et présentent le plus faible contraste; et
b) que la seconde présente au contraire le plus fort contraste, puisqu'elle correspond au coefficient le plus élevé (3).

Quitte à se limiter à une matrice (3x3), je préfèrerais pour ma part la combinaison

M(2, 1) = 2*M₁ + M₂

dont les deux termes présentent une contribution égale au laplacien:

S(2, 1) = 2*ΔU + 2*ΔU = 4*ΔU .

PS: on retrouve au passage le mouton noir mentionné en fin du message #04 dans le cas particulier où l'on a:

a + 2*b = 0 ;

les calculs ne conduisent plus alors à la valeur locale du laplacien.

[wiwaxia]

L'aspect de l'image obtenue dépend fortement du tri imposé aux valeurs calculées (g), lorsque l'on envisage une sélection partielle des pixels.

Prenons l'exemple d'une partition de l'ensemble des valeurs calculées, établie sur les frontières établies à partir de la moyenne et de l'écart-type:

{ Gmoyen - Sigma , Gmoyen - Sigma/2 , Gmoyen , Gmoyen + Sigma/2 , Gmoyen + Sigma }

et qui, dans le cas d'une distribution gaussienne, conduisent à des effectifs à peu près identiques (~ 1/6 , soit 17 %).

On a obtenu, à partir d'une image initiale de dimensions réduites (360x293) et en utilisant la matrice (M(2, 1)) précédemment définie, les résultats suivants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
# Nombre total de pixels calculés: Nt = 104178 ; Gmin = -4371 ; Gmax = 4083 ; Gmoy = -11.744; Gsigma = 587.102
Nombres respectifs dans les domaines successifs:     / Loi normale
g < M - S              N1 =  7833      7.52 %          15.87 %
M - S < g < M - S/2    N2 =  4224      4.05 %          14.98 %
M - S/2 < g < M        N3 = 32263     30.97 %          19.15 %
M < g < M + S/2        N4 = 47745     45.83 %          19.15 %
M + S/2 < M < M + S    N5 =  4277      4.11 %          14.98 %
M + S < g              N6 =  7836      7.52 %          15.87 %

Les proportions obtenues sont très éloignées de celles prévues par la loi normale; on observe:
a) une surabondance considérable des valeurs proches de la moyenne (M - S/2 < g < M + S/2), dont l'effectif est doublé par rapport à ce que prévoit une distribution gaussienne;
b) une raréfaction prononcée des valeurs intermédiaires vérifiant

(M - S < g < M - S/2) ou (M + S/2 < g < M + S)

par rapport au valeurs extrêmes définies par (g < M - S) ou (M + S < g),
ces dernières apparaissant presque deux fois plus nombreuses.

Les écarts séparant les divers effectifs sont immédiatement confirmés par les densités des images correspondantes, délibérément affectées des mêmes couleurs (pixels bleus sur fond blanc).
On remarque de plus que seules les valeurs extrêmes font apparaître les contours.

_
_
_

Un histogramme plus fin construit sur un domaine plus étendu, par exemple [M - 2S; M + 2S], permettrait peut-être de repérer les éventuels minimums de densité de probabilité, s'ils existent.

[wiwaxia]

Il n'est pas facile de trouver des références sur le développement en série de Taylor-Mac Laurin.

La meilleure de trouve sur un site francophone (ce qui ne gâte rien), par ailleurs d'excellente qualité; voici l'expression recherchée:

dans laquelle il suffit de poser: a = b = 0 , h = x , k = y
pour retrouver la formule déjà utilisée.

Ce lien conduit à un article contenant (p 3, 4) le début du développement symbolique, avec une notation plus proche de celle employée auparavant:

Autre document, où la formule est un peu mieux explicitée ...

... mais où chacun s'aperçoit que l'auteur s'est emmêlé les pinceaux: il faut évidemment lire en entrée de l'expression:

f(x, y) = ...

La dérivée d'ordre nul qui apparaît ensuite n'est autre que la fonction elle-même, dont on retient la valeur en (x₀, y₀):

(∂⁰f/∂⁰x∂⁰y) = f_{(x = x0, y - y0)} .

Le vénérable Manuel des Fonctions Mathématiques d'Abramowitz & Stegun contient quelques expressions du laplacien à partir d'un nombre fini de points du plan (p 883 à 885):
Abramowitz and Stegun, Handbook of Mathematical Functions.

[wiwaxia]

Reprenons le développement de U(x, y) en série de Taylor jusqu'au sixième ordre, au voisinage de l'origine (0, 0):

U(x, y) = U(0, 0) + D₁₀.x + D₀₁.y + (1/2!)(D₂₀.x² + 2D₁₁.xy + D₀₂.y²) + ...
... + (1/3!)(D₃₀.x³ + 3D₂₁.x²y + 3D₁₂.xy² + D₀₃.y³) + ...
... + (1/4!)(D₄₀.x⁴ + 4D₃₁.x³y + 6D₂₂.x²y² + 4D₁₃.xy³ + D₀₄.y⁴) + ...
... + (1/5!)(D₅₀.x⁵ + 5D₄₁.x⁴y + 10D₃₂.x³y² + 10D₂₃.x²y³ +5D₁₄.xy⁴ + D₀₅.y⁵) + ...
... + (1/6!)(D₆₀.x⁶ + 6D₅₁.x⁵y + 15D₄₂.x⁴y² + 20D₃₃.x³y³ + 15D₂₄.x²y⁴ +6D₁₅.xy⁵ + D₀₆.y⁶) + ...

# Si l'on veut sélectionner les dérivées de rang pair dans l'expression approchée d'une somme au voisinage d'un point donné (x₀, y₀), il faut combiner des termes correspondant à des décalages opposés des arguments (x, y) afin d'éliminer les termes de rang impair;
on obtient par exemple: U(x₀ + h, y₀) + U(x₀ - h, y₀) - 2U(x₀, y₀) ~ h²(∂²U/∂x²)
et symétriquement: U(x₀, y₀ + h) + U(x₀, y₀ - h) - 2U(x₀, y₀) ~ h²(∂²U/∂y²) ,
ce qui conduit naturellement à une expression du laplacien:

U(x₀ + h, y₀) + U(x₀ - h, y₀) + U(x₀, y₀ + h) + U(x₀, y₀ - h) - 4U(x₀, y₀) ~ h²((∂²U/∂x²) + (∂²U/∂y²)) = h².ΔU .

Ainsi apparaît la nécessité d'associer dans une même somme, en plus du terme central (U(x₀, y₀)), 4 termes correspondant à des combinaisons symétriques des arguments, soit:

S₁ = U(x₀ + h, y₀) + U(x₀ - h, y₀) + U(x₀, y₀ + h) + U(x₀, y₀ - h) - 4U(x₀, y₀) ~ h².ΔU ,
S₂ = U(x₀ + h, y₀ + h) + U(x₀ - h, y₀ + h) + U(x₀ + h, y₀ - h) + U(x₀ - h, y₀ - h) - 4U(x₀, y₀) ~ 2h².ΔU ,

le nombre de termes étant porté à 8 lorsque l'on impose aux variables des décalages différents:

S₃ = U(x₀ + h, y₀ + h') + U(x₀ - h, y₀ + h') + U(x₀ + h, y₀ - h') + U(x₀ - h, y₀ - h') + U(x₀ + h', y₀ + h) + U(x₀ - h', y₀ + h) + U(x₀ + h', y₀ - h) + U(x₀ - h', y₀ - h) ...
... - 8U(x₀, y₀) ~ 2(h² + h'²).ΔU

C'est pourquoi l'on est amené à envisager pour les filtres des matrices carrées d'ordre impair, présentant un centre de symétrie (repéré par le couple (0, 0)) et pour lesquelles la somme étendue à tous les éléments est nulle:

Σ_x=-n⁺ⁿ(Σ_y=-n⁺ⁿm_x,y) = 0 (pour une matrice d'ordre 2n + 1).

ces tableaux sont dotés de nombreux éléments de symétrie, parmi lesquels:
a) les deux médianes: m_{-x, y} = m_{x, y} , m_{x, -y} = m_{x, y};
b) les deux diagonales: m_{y, x} = m_{x, y} , m_{-y, -x} = m_{x, y};
c) le centre: m_-x,-y = m_{x, y} .
Remarque: l'axe (y'y) est ici orienté vers le haut, comme pour la matrice du corps des images au format Bitmap, de sorte que la diagonale principale (d'équation y = x) est ascendante; tandis qu'en mathématiques l'indexation des lignes progresse vers le bas, ce qui conduit à une diagonale principale orientée dans la même direction.
On est en présence d'une matrice symétrique au sens strict, parce qu'elle est égale à sa transposée (m_{y, x} = m_{x, y}).

# Les matrices carrées d'ordre 5 s'expriment par une combinaison linéaire de 5 matrices élémentaires de même dimension:

M(a, b, c, d, e) = a.M₁₀+ b.M₂₀+ c.M₁₁ + d.M₂₂ + e.M₂₁ ,
avec s = 4(a + b + c + d + 2.e) ;

[wiwaxia]

1°) Aux matrices (M₁₀, M₂₀) correspondent respectivement les sommes:

S₁₀ = h².ΔU + (h⁴/12)(D₄₀ + D₀₄) + (h⁶/360)(D₆₀ + D₀₆) ,
S₂₀ = 4h².ΔU + (16h⁴/12)(D₄₀ + D₀₄) + (64h⁶/360)(D₆₀ + D₀₆) ,

dont les expressions ne diffèrent que par la valeur du pas (h' = 2h).
On se débarrasse aisément du terme d'ordre (4) par la combinaison linéaire:

S_a = 16S₁₀ - S₂₀ = 12h².ΔU - (2h⁶/15)(D₆₀ + D₀₆) ,

qui correspond à la matrice M_a = 16.M₁₀ - M₂₀ .

2°) Aux matrices (M₁₁, M₂₂) correspondent pareillement les sommes:

S₁₁ = 2h².ΔU + (h⁴/12)(2D₄₀ + 3D₂₂ + 2D₀₄) + (h⁶/180)(D₆₀ + 15D₄₂ + 15D₂₄ + D₆₀) ,
S₂₂ = 8h².ΔU + (16h⁴/12)(2D₄₀ + 3D₂₂ + 2D₀₄) + (64h⁶/180)(D₆₀ + 15D₄₂ + 15D₂₄ + D₆₀) ,

dont les expressions ne diffèrent là encore que par le doublement du pas (h' = 2h).
Le terme d'ordre (4) disparaît par la combinaison linéaire appropriée:

S_b = 16S₁₁ - S₂₂ = 24h².ΔU - (4h⁶/15)(D₆₀ + 15D₄₂ + 15D₂₄ + D₆₀) ,

qui correspond à une nouvelle matrice: M_b = 16.M₁₁ - M₂₂ .

On peut désormais envisager la nouvelle combinaison: M = 2.M_a + M_b ,
dont les deux termes présentent des contributions égales au laplacien:

S = 2.S_a + S_b = 48h².ΔU - (4h⁶/15)(2D₆₀ + 15D₄₂ + 15D₂₄ + 2D₀₆) .

Remarque: des considérations purement formelles conduisent à une autre combinaison: M = 8.M_a + M_b ,
dont la somme admet une expression particulièrement concise: S = 120h².ΔU - (4h⁶/3)Δ³U
mettant en jeu le laplacien cube Δ³U = Δ(Δ²U) = Δ(Δ(ΔU)) = D₆₀ + 3D₄₂ + 3D₂₄ + D₀₆ ;
la matrice est alors: M = ((-1, 0, -8, 0, -1), (0, 16, 128, 16, 0), (-8, 128, -540, 128, -8), (0, 16, 128, 16, 0), (-1, 0, -8, 0, -1))

# Il y a évidemment à ce stade une infinité de combinaisons interdites

M(a, b, c, d, 0),

pour lesquelles la somme correspondante S ~ (a + 4b + 2c+ 8d)h².ΔU = Kh².ΔU
ne représente plus le laplacien (K = 0);
la pire de toutes étant pour l'instant: M' = 2.M_a - M_b

et pour laquelle on a : S = 2.S_a - S_b = 4h⁶.(D₄₂ + D₂₄) .

# Afin de changer d'illustration, j'ai remplacé Audrey Hepburn par un éléphant:

Voici les transformées de cette photographie d'une peinture sur soie à l'aide les matrices (M, M'):

On retrouve le contenu pictural fortement dégradé dans le second cas.
Afin de pouvoir comparer graphiquement des deux résultats, on a fait intervenir la même fonction de couleur dans les deux cas:
a) g > Gmoyen : teinte rouge (r, v, b) = (k, 0, 0);
g <= Gmoyen : teinte bleue (r, v, b) = (0, 0, k);
b) Seuil = 1.40 * (Ecart-type) ;
si Abs(g - Gmoyen) > Seuil alors k = 255 sinon k = Round(K * (g - Gmoyen)⁴) .

Il avait déjà été question d'examiner de plus près l'histogramme des sommes calculées (g) en chaque pixel de l'image; la distribution des valeurs apparaît très dissemblable dans les deux cas présents, d'après le petit nombre de résultats affichés:
# Matrice (M)

# Matrice (M')

La répartition des valeurs apparaît nettement plus étalée et plus dissymétrique dans le premier cas.

[wiwaxia]

Toujours à propos de l'histogramme des valeurs calculées (g): une exploitation résolument dissymétrique de celui-ci, analogue à celle évoquée au message #09, peut conduire à une image de couleur et de contraste arbitraires

Voici ce à quoi conduit la transformation de la photographie d'une sculpture sur marbre, en recourrant à la définition suivante des couleurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Si (g<Gmoyen) alors pixel = (0, 0, 255)
              sinon si (g - Gmoyen>Seuil) alors Pixel = (179, 255, 255)
                                          sinon début
                                                  k = Round(255 * (g/Seuil)^4; r:= k DIV 2;
                                                  Pixel = (r, k, 255) 
                                                fin

Une telle fonction couleur est naturellement ouverte à toutes les variantes: à chacun de suivre son inspiration.

Le paramètre ici en cause est le rapport arbitraire du seuil à d'écart-type Gamma = Seuil / Gsigma ; les cinq valeurs envisagées sont ici:

{ 1.00 , 1.33 , 1.67 , 2.00 , 2.33 }:

_

_

_