Pour un binary image, je suis intéressé par un moyen de compter efficacement le nombre de formes individuelles présentes dans l'image. Aussi comme une question adjacente, comment peut-on adapter chaque forme qui est présente dans l'image dans un carré?Qu'est-ce qu'un algorithme efficace pour trouver le nombre de formes dans une image binaire?
Le pseudocode est le bienvenu.
Je ne peux pas répondre à la seconde moitié, mais si la première moitié définit une "forme" comme des pixels contigus d'une certaine couleur, voici ce que je fais. Maintenir un tableau pour l'ensemble de l'image, indiquant quels pixels ont été "vus". (Un bool [,] ferait l'affaire, en C# -speak.)
Ensuite commencez l'itération sur chaque pixel. Si cela a déjà été vu, ignorez-le.
Sinon, si ce n'est pas encore vu et que c'est la couleur "non-shape", marquez-la vue et continuez.
Sinon, il n'a pas été vu et est une forme. A partir d'ici, araignée dans chacune des quatre directions de la boussole. Si vous atteignez un pixel vu, arrêtez-vous et revenez en arrière (cela empêche une boucle infinie de se produire). Si le pixel est la couleur de non-forme, marquez le pixel vu et arrêtez immédiatement. Sinon, le pixel est une couleur de forme. Marquez-le vu et ajoutez-le à toutes les données de «définition de forme» que vous construisez.
Une fois ce processus terminé, vous avez découvert une forme. Rangez-le quelque part et continuez à chercher. Tous les pixels de cette forme doivent maintenant être marqués comme visibles et ne seront plus pris en compte par l'algorithme.
Cet algorithme pour la découverte de forme une fois qu'un pixel de couleur de forme a été localisé est intrinsèquement récursif, et pour les grandes formes, il peut déborder de la pile. Il peut être approprié d'utiliser une implémentation de pile basée sur le tas pour effectuer la recherche de forme entière.
(Si l'on considère assez pixels en diagonale adjacents pour relier deux formes en une seule, il suffit de rechercher tous les huit pixels adjacents au lieu de seulement quatre les horizontalement et et verticalement adjacents.)
Une notion possible de "forme" est les composants connectés. Dans ce cas, un algorithme union-find vous donnera ce que vous voulez: http://en.wikipedia.org/wiki/Connected_Component_Labeling. Si vous voulez aussi les extensions X et Y, union-find peut être étendu pour garder une trace de celles-ci.
Do Blobing des données d'image , vous obtiendrez chaque forme avec tous les pixels et les étendues [RECT de la forme]
Si votre image a une forme à l'intérieur de la forme, puis blobing traitera les deux comme des formes individuelles.
Si vous avez besoin de code envoyez-moi un mail, sera heureux de partager.