Implémentation de la segmentation d'image en python (Union-Find)

Article précédent était intéressant parce que j'avais un peu de traitement d'image, donc cette fois j'ai lu l'article et essayé d'implémenter un traitement d'image simple. (Cela ressemble à l'image ci-dessous.)

src	dst

Le papier que j'ai lu cette fois est relativement ancien (2004) et la mise en œuvre elle-même ne semblait pas si difficile, alors je l'ai essayé. (Cependant, ce n'est pas aussi bon que le résultat publié dans le journal ...)

Le code source de cette heure est publié sur github. https://github.com/aratakokubun/GraphBasedSegmentationWithUnionFind.git

Vue d'ensemble du traitement d'image

Cette fois, nous avons mis en œuvre le processus de division de la zone d'image, qui est la luminosité. Comme condition de combinaison, les limites (Edge) avec les pixels voisins sont jugées par ordre croissant et les zones sont combinées les unes après les autres.

algorithme

Faites 1-5 ci-dessous pour obtenir une liste des composants indépendants en conséquence. Ce composant est la zone où les pixels sont combinés.

1. Extrayez les 8 bords de chaque pixel ou des bords à une certaine distance (voisin le plus proche). Dans l'état initial, tous les pixels ne sont pas combinés et chaque élément est traité comme un composant.
2. Pour chaque pixel, calculez la valeur utilisée comme base du couplage.
   Par exemple, dans ce cas, la valeur de luminosité (luminance) est utilisée, et les pixels ayant une luminosité similaire sont combinés dans la même région.
3. Mesurez la différence (diff) de chaque arête extraite et triez par ordre croissant de valeur de diff.
4. Répétez l'étape 5 dans l'ordre croissant d'Edge
5. Si la valeur de Edge est inférieure à la différence interne (MInt) des composants des deux côtés de la limite, combinez les deux composants en un seul composant.
   

• Cette étape sera décrite en détail dans les conditions de connexion Edge.

Condition de jointure de bord

Concernant la combinaison à l'étape 5, la différence diff d'Edge et la différence interne Mint de deux Composants C1 et C2 sont combinées dans les conditions suivantes.

diff <= MInt(C1, C2)

La différence interne menthe de deux composants est définie comme suit.

MInt(C1, C2) = min(Int(C1)+τ(C1), Int(C2)+τ(C2))

La différence interne Int de chaque composant prend la valeur maximale des limites jamais liées au composant. Si Component est un élément de 1 pixel, ce sera 0. (Cependant, cette description n'est pas strictement correcte, donc si vous voulez en savoir plus, veuillez vous référer à la référence 1.)

De plus, τ est une fonction de valeur limite en fonction de la taille du composant et est définie comme suit.

τ(C) = k/|C|

k est un paramètre constant, et plus k est grand, plus il est facile pour Edge de se joindre et le composant résultant sera plus grand.

Techniques pour accélérer

Un algorithme appelé Union-Find est utilisé pour accélérer le processus.
Union-Find considère les sous-ensembles de S qui sont mutuellement exclusifs à l'ensemble S. Dans le processus de division de la zone d'image cette fois, l'ensemble S correspond à l'image qui est l'ensemble des pixels, et le sous-ensemble correspond au Composant. Cela s'appelle Disjoint Set, et les opérations d'union et de recherche sont définies comme suit.

• union(C1, C2) Les sous-ensembles C1 et C2 sont fusionnés en C1. (Cela correspond au processus de l'étape 5 de la jonction de composants.)
• find(a) Obtient le sous-ensemble auquel appartient l'élément a (pixel).

Lors de ce traitement d'union, l'élément représentatif de chaque Composant est défini un par un, et le lien est fait de chaque élément du côté combiné (C2) à l'élément représentatif du côté de connexion (C1). Cela facilite la mise en œuvre du traitement avec un seul tableau.
De plus, une accélération supplémentaire est possible en utilisant Uion-Find by Tree.

La méthode de mise en œuvre n'est pas décrite en détail ici, mais veuillez vous reporter à la référence 2 pour une explication assez détaillée de Union-Find. En outre, la référence 3 explique également le montant du calcul, veuillez donc vous y référer également.

résultat

Le résultat implémenté en python cette fois est le suivant. Les 40 premiers avec la plus grande superficie sont colorés au lieu de tous les domaines.

src	dst

Le code source de cette heure est publié sur github. https://github.com/aratakokubun/GraphBasedSegmentationWithUnionFind.git

Les références

1. Efficient Graph-Based Image Segmentation
   http://cs.brown.edu/~pff/papers/seg-ijcv.pdf
2. Mise en œuvre de Union Find
   http://www.geocities.jp/m_hiroi/light/pyalgo61.html
3. Disjoint-Set Data Structures
   http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec16.pdf