Un algorithme de complexité linéaire pour le calcul de l'arbre des formes

Authors

Edwin Carlinet, Sébastien Crozet, Thierry Géraud

Where

Actes du congrès Reconnaissance des Formes, ImageApprentissage et Perception (RFIAP)

Place

Marne-la-Vallée, France

Type

inproceedings

Projects

Olena

Keywords

Image

Date

2018-05-04

Abstract

L'arbre des formes (AdF) est une représentation morpho- logique hiérarchique de l'image qui traduit l'inclusion des ses lignes de niveaux. Il se caractérise par son invariance à certains changement de l'image, ce qui fait de lui un outil idéal pour le développement d'applications de reconnaissance des formes. Dans cet article, nous proposons une méthode pour transformer sa construction en un calcul de Max-tree. Ce dernier a été largement étudié au cours des dernières années et des algorithmes efficaces (dont certains parallèles) existent déjà. Nous proposons également une optimisation qui permet d'accélérer son calcul dans le cas classique des images 2D. Il en découle un algorithme simple, efficace, s'exécutant linéairement en fonction du nombre de pixels, avec une faible empreinte mémoireet qui surpasse les algorithmes à l'état de l'art.

Documents

• Paper

Software

Source code for linear time ToS and benchmark reproduction is available here:

https://gitlab.lrde.epita.fr/olena/pylene-apps/tree/master/carlinet.2017.icip

Bibtex (lrde.bib)

@InProceedings{	  carlinet.18.rfiap,
  author	= {Edwin Carlinet and S\'ebastien Crozet and Thierry G\'eraud},
  title		= {Un algorithme de complexit\'e lin\'eaire pour le calcul de
		  l'arbre des formes},
  booktitle	= {Actes du congr\`es Reconnaissance des Formes, Image,
		  Apprentissage et Perception (RFIAP)},
  year		= {2018},
  month		= jun,
  address	= {Marne-la-Vall\'ee, France},
  category	= {national},
  abstract	= {L'arbre des formes (AdF) est une repr\'esentation morpho-
		  logique hi\'erarchique de l'image qui traduit l'inclusion
		  des ses lignes de niveaux. Il se caract\'erise par son
		  invariance \`a certains changement de l'image, ce qui fait
		  de lui un outil id\'eal pour le d\'eveloppement
		  d'applications de reconnaissance des formes. Dans cet
		  article, nous proposons une m\'ethode pour transformer sa
		  construction en un calcul de Max-tree. Ce dernier a \'et\'e
		  largement \'etudi\'e au cours des derni\`eres ann\'ees et
		  des algorithmes efficaces (dont certains parall\`eles)
		  existent d\'ej\`a. Nous proposons \'egalement une
		  optimisation qui permet d'acc\'el\'erer son calcul dans le
		  cas classique des images 2D. Il en d\'ecoule un algorithme
		  simple, efficace, s'ex\'ecutant lin\'eairement en fonction
		  du nombre de pixels, avec une faible empreinte m\'emoire,
		  et qui surpasse les algorithmes \`a l'\'etat de l'art.}
}