Mise en œuvre de l'espace d'échelle

Dans les domaines de la vision par ordinateur , de l'analyse d'images et du traitement du signal , la notion de représentation de l'espace d'échelle est utilisée pour traiter des données de mesure à plusieurs échelles, et notamment pour améliorer ou supprimer des caractéristiques d'image sur différentes plages d'échelle (voir l'article sur l'espace d'échelle ). Un type particulier de représentation de l'espace d'échelle est fourni par l'espace d'échelle gaussien, où les données d'image en N dimensions sont soumises à un lissage par convolution gaussienne . La majeure partie de la théorie de l'espace d'échelle gaussien traite d'images continues, alors que la mise en œuvre de cette théorie devra faire face au fait que la plupart des données de mesure sont discrètes. Par conséquent, le problème théorique se pose de savoir comment discrétiser la théorie continue tout en préservant ou en approchant correctement les propriétés théoriques souhaitables qui conduisent au choix du noyau gaussien (voir l'article sur les axiomes de l'espace d'échelle ). Cet article décrit les approches de base pour cela qui ont été développées dans la littérature, voir également pour un traitement approfondi concernant le sujet de l'approximation de l'opération de lissage gaussien et des calculs de dérivées gaussiennes dans la théorie de l'espace d'échelle.

Représentation gaussienne de l' espace d'échelle d'un signal continu à N dimensions,

est obtenu en convoluant f _C avec un noyau gaussien de dimension N :

Autrement dit:

Cependant, pour la mise en œuvre , cette définition n'est pas pratique, car elle est continue. Lors de l'application du concept d'espace d'échelle à un signal discret f _D , différentes approches peuvent être adoptées. Cet article est un bref résumé de certaines des méthodes les plus fréquemment utilisées.

Utilisation de la propriété de séparabilité du noyau gaussien

l' opération de convolution N -dimensionnelle peut être décomposée en un ensemble d'étapes de lissage séparables avec un noyau gaussien unidimensionnel G le long de chaque dimension

où

et l'écart type de la gaussienne σ est lié au paramètre d'échelle t selon t = σ ² .

Dans tout ce qui suit, la séparabilité sera supposée, même lorsque le noyau n'est pas exactement gaussien, car la séparation des dimensions est le moyen le plus pratique de mettre en œuvre un lissage multidimensionnel, en particulier à des échelles plus grandes. Par conséquent, le reste de l'article se concentre sur le cas unidimensionnel.

Lors de la mise en œuvre pratique de l'étape de lissage unidimensionnel, l'approche probablement la plus simple consiste à convoluer le signal discret f _D avec un noyau gaussien échantillonné :

où

(avec t = σ ² ) qui à son tour est tronqué aux extrémités pour donner un filtre à réponse impulsionnelle finie

pour M choisi suffisamment grand (voir fonction d'erreur ) tel que

Un choix courant consiste à définir M sur une constante C fois l'écart type du noyau gaussien

où C est souvent choisi entre 3 et 6.

L'utilisation du noyau gaussien échantillonné peut cependant entraîner des problèmes de mise en œuvre, en particulier lors du calcul de dérivées d'ordre supérieur à des échelles plus fines en appliquant des dérivées échantillonnées de noyaux gaussiens. Lorsque la précision et la robustesse sont des critères de conception primordiaux, des approches de mise en œuvre alternatives doivent donc être envisagées.

Pour de petites valeurs de ε (10 ⁻⁶ à 10 ⁻⁸ ), les erreurs introduites par la troncature de la gaussienne sont généralement négligeables. Pour des valeurs plus élevées de ε, cependant, il existe de nombreuses alternatives plus efficaces qu'une fonction de fenêtre rectangulaire . Par exemple, pour un nombre donné de points, une fenêtre de Hamming , une fenêtre de Blackman ou une fenêtre de Kaiser endommagera moins les propriétés spectrales et autres de la gaussienne qu'une simple troncature. Malgré cela, comme le noyau gaussien décroît rapidement aux extrémités, la principale recommandation est toujours d'utiliser une valeur de ε suffisamment petite pour que les effets de troncature ne soient plus importants.

Une approche plus raffinée consiste à convoluer le signal original avec le noyau gaussien discret T ( n , t )

où

et désigne les fonctions de Bessel modifiées d'ordre entier, n . C'est la contrepartie discrète de la gaussienne continue en ce sens qu'elle est la solution de l' équation de diffusion discrète (espace discret, temps continu), tout comme la gaussienne continue est la solution de l'équation de diffusion continue.

Ce filtre peut être tronqué dans le domaine spatial comme pour la gaussienne échantillonnée

ou peut être implémenté dans le domaine de Fourier en utilisant une expression sous forme fermée pour sa transformée de Fourier en temps discret :

Avec cette approche du domaine fréquentiel, les propriétés de l'espace d'échelle sont transférées exactement au domaine discret, ou avec une excellente approximation en utilisant une extension périodique et une transformée de Fourier discrète suffisamment longue pour approximer la transformée de Fourier à temps discret du signal en cours de lissage. De plus, les approximations des dérivées d'ordre supérieur peuvent être calculées de manière simple (et en préservant les propriétés de l'espace d'échelle) en appliquant des opérateurs de différence centrale à faible support à la représentation de l'espace d'échelle discret .

Comme pour la gaussienne échantillonnée, une troncature simple de la réponse impulsionnelle infinie sera dans la plupart des cas une approximation suffisante pour les petites valeurs de ε, tandis que pour les valeurs plus grandes de ε, il est préférable d'utiliser soit une décomposition de la gaussienne discrète en une cascade de filtres binomiaux généralisés, soit de construire un noyau approximatif fini en multipliant par une fonction fenêtre . Si ε a été choisi trop grand de sorte que les effets de l'erreur de troncature commencent à apparaître (par exemple sous forme d'extrema parasites ou de réponses parasites à des opérateurs dérivés d'ordre supérieur), alors les options sont de diminuer la valeur de ε de sorte qu'un noyau fini plus grand soit utilisé, avec une coupure où le support est très petit, ou d'utiliser une fenêtre effilée.

L'efficacité de calcul étant souvent importante, des filtres récursifs d'ordre faible sont souvent utilisés pour le lissage de l'espace d'échelle. Par exemple, Young et van Vliet utilisent un filtre récursif du troisième ordre avec un pôle réel et une paire de pôles complexes, appliqués en avant et en arrière pour réaliser une approximation symétrique du sixième ordre de la gaussienne avec une faible complexité de calcul pour toute échelle de lissage.

En relâchant quelques axiomes, Lindeberg a conclu que de bons filtres de lissage seraient des « séquences de fréquences de Pólya normalisées », une famille de noyaux discrets qui inclut tous les filtres avec des pôles réels à 0 < Z < 1 et/ou Z > 1, ainsi qu'avec des zéros réels à Z < 0. Pour la symétrie, qui conduit à une homogénéité directionnelle approximative, ces filtres doivent être en outre restreints à des paires de pôles et de zéros qui conduisent à des filtres à phase nulle.

Pour correspondre à la courbure de la fonction de transfert à fréquence nulle de la gaussienne discrète, qui assure une propriété de semi-groupe approximative de t additif , deux pôles à

peut être appliqué vers l'avant et vers l'arrière, pour la symétrie et la stabilité. Ce filtre est l'implémentation la plus simple d'un noyau de séquence de fréquences Pólya normalisé qui fonctionne pour n'importe quelle échelle de lissage, mais il n'est pas une aussi excellente approximation de la gaussienne que le filtre de Young et van Vliet, qui n'est pas une séquence de fréquences Pólya normalisée, en raison de ses pôles complexes.

La fonction de transfert, H ₁ , d'un filtre récursif à paires de pôles symétriques est étroitement liée à la transformée de Fourier à temps discret du noyau gaussien discret via l'approximation du premier ordre de l'exponentielle :

où le paramètre t est ici lié à la position du pôle stable Z = p via :

De plus, de tels filtres avec N paires de pôles, comme les deux paires de pôles illustrées dans cette section, constituent une approximation encore meilleure de l'exponentielle :

où les positions des pôles stables sont ajustées en résolvant :

Les réponses impulsionnelles de ces filtres ne sont pas très proches de la réponse gaussienne, sauf si plus de deux paires de pôles sont utilisées. Cependant, même avec seulement une ou deux paires de pôles par échelle, un signal lissé successivement à des échelles croissantes sera très proche d'un signal lissé gaussien. La propriété de semi-groupe est mal approximée lorsque trop peu de paires de pôles sont utilisées.

Les axiomes d'échelle-espace qui sont toujours satisfaits par ces filtres sont :

• linéarité
• invariance par décalage (décalages entiers)
• non-création d'extrema locaux (passages à zéro) en une dimension
• non-amélioration des extrema locaux dans un nombre quelconque de dimensions
• positivité
• normalisation

Les conditions suivantes ne sont satisfaites qu'approximativement, l'approximation étant meilleure pour un plus grand nombre de paires de pôles :

• existence d'un générateur infinitésimal A (le générateur infinitésimal de la gaussienne discrète, ou un filtre l'approximant, mappe approximativement une réponse de filtre récursif sur une réponse de t infinitésimale plus grande )
• la structure du semi-groupe avec la propriété de lissage en cascade associée (cette propriété est approximée en considérant que les noyaux sont équivalents lorsqu'ils ont la même valeur t , même s'ils ne sont pas tout à fait égaux)
• symétrie de rotation
• invariance d'échelle

Cette méthode de filtrage récursif et ses variantes pour calculer à la fois le lissage gaussien et les dérivées gaussiennes ont été décrites par plusieurs auteurs. Tan et al. ont analysé et comparé certaines de ces approches et ont souligné que les filtres de Young et van Vliet sont une cascade (multiplication) de filtres avant et arrière, tandis que les filtres de Deriche et de Jin et al. sont des sommes de filtres avant et arrière.

Aux échelles fines, l'approche de filtrage récursif ainsi que d'autres approches séparables ne garantissent pas de donner la meilleure approximation possible de la symétrie de rotation, de sorte que les implémentations non séparables pour les images 2D peuvent être considérées comme une alternative.

Lors du calcul simultané de plusieurs dérivées dans le N-jet , le lissage discret de l'espace d'échelle avec l'analogue discret du noyau gaussien, ou avec une approximation de filtre récursif, suivi d'opérateurs de petite différence de support, peut être à la fois plus rapide et plus précis que le calcul d'approximations récursives de chaque opérateur dérivé.

Pour les petites échelles, un filtre FIR d'ordre faible peut être un meilleur filtre de lissage qu'un filtre récursif. Le filtre symétrique à 3 noyaux [ t /2, 1- t , t /2] , pour t ≤ 0,5 lisse à une échelle de t en utilisant une paire de zéros réels à Z < 0, et se rapproche de la gaussienne discrète dans la limite de t petit. En fait, avec t infinitésimal , soit ce filtre à deux zéros, soit le filtre à deux pôles avec des pôles à Z = t /2 et Z = 2/ t peut être utilisé comme générateur infinitésimal pour les noyaux gaussiens discrets décrits ci-dessus.

Les zéros du filtre FIR peuvent être combinés avec les pôles du filtre récursif pour créer un filtre de lissage général de haute qualité. Par exemple, si le processus de lissage consiste à appliquer toujours un filtre biquadratique (deux pôles, deux zéros) vers l'avant puis vers l'arrière sur chaque ligne de données (et sur chaque colonne dans le cas 2D), les pôles et les zéros peuvent chacun effectuer une partie du lissage. Les zéros se limitent à t = 0,5 par paire (zéros à Z = –1), donc pour les grandes échelles, les pôles effectuent la majeure partie du travail. À des échelles plus fines, la combinaison constitue une excellente approximation de la gaussienne discrète si les pôles et les zéros effectuent chacun environ la moitié du lissage. Les valeurs t pour chaque partie du lissage (pôles, zéros, applications multiples vers l'avant et vers l'arrière, etc.) sont additives, conformément à la propriété de semi-groupe approximatif.

La fonction de transfert du filtre FIR est étroitement liée à la DTFT de la Gaussienne discrète, tout comme l'était celle du filtre récursif. Pour une seule paire de zéros, la fonction de transfert est

où le paramètre t est ici lié aux positions zéro Z = z via :

et nous exigeons que t ≤ 0,5 pour maintenir la fonction de transfert non négative.

De plus, de tels filtres avec N paires de zéros constituent une approximation encore meilleure de l'exponentielle et s'étendent à des valeurs plus élevées de t :

où les positions zéro stables sont ajustées en résolvant :

Ces filtres FIR et pôle-zéro sont des noyaux d'espace d'échelle valides, satisfaisant les mêmes axiomes que les filtres récursifs tous pôles.

En ce qui concerne le sujet de la sélection automatique d'échelle basée sur des dérivées normalisées, les approximations pyramidales sont fréquemment utilisées pour obtenir des performances en temps réel. La pertinence d'approximer les opérations d'espace d'échelle au sein d'une pyramide provient du fait que le lissage en cascade répété avec des noyaux binomiaux généralisés conduit à des noyaux de lissage équivalents qui, dans des conditions raisonnables, se rapprochent de la gaussienne. De plus, les noyaux binomiaux (ou plus généralement la classe des noyaux binomiaux généralisés) peuvent être montrés comme constituant la classe unique de noyaux à support fini qui garantissent la non-création d'extrema locaux ou de passages à zéro avec une échelle croissante (voir l'article sur les approches multi-échelles pour plus de détails). Des précautions particulières peuvent cependant être nécessaires pour éviter les artefacts de discrétisation.

Pour les noyaux unidimensionnels, il existe une théorie bien développée des approches multi-échelles , concernant les filtres qui ne créent pas de nouveaux extrema locaux ou de nouveaux passages à zéro avec des échelles croissantes. Pour les signaux continus, les filtres avec des pôles réels dans le plan s appartiennent à cette classe, tandis que pour les signaux discrets, les filtres récursifs et FIR décrits ci-dessus satisfont à ces critères. Combinés à l'exigence stricte d'une structure de semi-groupe continue, la gaussienne continue et la gaussienne discrète constituent le choix unique pour les signaux continus et discrets.

Il existe de nombreuses autres techniques de traitement de signaux multi-échelles, de traitement d'images et de compression de données, utilisant des ondelettes et une variété d'autres noyaux, qui n'exploitent pas ou ne nécessitent pas les mêmes exigences que les descriptions d'espace d'échelle ; c'est-à-dire qu'elles ne dépendent pas d'une échelle plus grossière ne générant pas un nouvel extremum qui n'était pas présent à une échelle plus fine (en 1D) ou de la non-amélioration des extremums locaux entre les niveaux d'échelle adjacents (dans un nombre quelconque de dimensions).