Je vais d'abord passer en revue quelques liens et ressources générales, puis essayer de décrire l'idée générale de l'algorithme.
GRAINES implémentations:
Vous avez vu évidemment déjà la documentation here. Un exemple d'utilisation de l'implémentation SEEDS d'OpenCV peut être trouvé ici: Itseez/opencv_contrib/modules/ximgproc/samples/seeds.cpp, et permet d'adapter le nombre de superpixels, le nombre de niveaux et d'autres paramètres en direct - donc après avoir lu l'idée derrière SEEDS, vous devriez essayer l'exemple. La mise en œuvre originale, ainsi qu'une mise en œuvre révisée (partie de ma thèse de baccalauréat), peut être trouvé sur GitHub: davidstutz/superpixels-revisited/lib_seeds et davidstutz/seeds-revised. Les implémentations devraient être assez comparables, cependant.
Publication et d'autres ressources:
Le document a été publié sur arXiv: arxiv.org/abs/1309.3848. Une description un peu plus courte (qui peut être plus facile à suivre) est disponible sur mon site Web: davidstutz.de/efficient-high-quality-superpixels-seeds-revised. La description de l'algorithme fournie devrait être facile à suivre et, dans le meilleur des cas, permettre d'implémenter SEEDS (voir la section "Algorithme" de l'article). Une description plus précise peut également être trouvée dans mon bachelor thesis, en particulier dans la section 3.1.
Description générale:
Notez que cette description est basée sur les deux l'article mentionné ci-dessus et ma thèse de baccalauréat. Les deux offrent une description mathématique concise.
Etant donné une image avec une largeur et une hauteur W
H
, GRAINE commence par le regroupement des pixels en blocs de taille w x h
. Ces blocs sont en outre disposés en groupes de 2 x 2
. Ce schéma est répété pour les niveaux L
(c'est le paramètre du nombre de niveaux). Donc, au niveau l
, vous avez des blocs de taille
w*2^(l - 1) x h*2^(l - 1).
Le nombre de superpixels est déterminé par les blocs au niveau L
, à savoir laisser w_L
et h_L
indiqueraient la largeur et la hauteur des blocs au niveau L
, le nombre de superpixels est
S = W/w_L * H/h_L
où nous utilisons des divisions entières.
La segmentation initiale du superpixel qui est maintenant raffinée itérativement en échangeant des blocs de pixels et des pixels individuels entre des superpixels voisins.A cette fin, les histogrammes de couleur des superpixels et de tous les blocs sont calculés (les histogrammes sont déterminés par le paramètre nombre de bins dans l'implémentation). Cela peut être fait efficacement en voyant que l'histogramme d'un superpixel est juste la somme des histogrammes des blocs 2 x 2
qu'il contient, et l'histogramme de l'un de ces blocs est la somme des histogrammes des blocs sous-jacents 2 x 2
(et ainsi sur). Alors laissez h_i
être l'histogramme d'un bloc de pixels appartenant au superpixel j
, et h_j
l'histogramme de ce superpixel. Ensuite, la similitude du bloc j
au superpixel j
est calculée par l'intersection de l'histogramme h_i
et h_j
(voir l'une des ressources ci-dessus pour l'équation). De même, la similitude d'un pixel et d'un superpixel est soit la distance euclidienne de la couleur du pixel à la couleur moyenne du superpixel (c'est l'option la plus performante), soit la probabilité de la couleur du pixel du superpixel entrée de l'histogramme du superpixel à la couleur du pixel). Dans ce contexte, l'algorithme peut se résumer comme suit:
initialize block hierarchy and the initial superpixel segmentation
for l = L - 1 to 1 // go through all levels
// for level l = L these are the initial superpixels
for each block in level l
initialize the color histogram of this block
// as described this is done using the histograms of the level below
// now we start exchanging blocks between superpixels
for l = L - 1 to 1
for each block at level l
if the block lies at the border to a superpixel it does not belong to
compute the histogram intersection with both superpixels
assign the block to the superpixel with the highest intersection
// now we exchange individual pixels between superpixels
for all pixels
if the pixel lies at the border to a superpixel it does not belong to
compute the Euclidean distance of the pixel to both superpixel's mean color
assign the pixel to the closest superpixel
Dans la pratique, les mises à jour des blocs et des mises à jour de pixels sont plus que les itérées (ce qui est le nombre d'itérations paramètres), et souvent deux fois plus d'itérations par niveau est fait (qui est le paramètre double étape). Dans la segmentation d'origine, le nombre de superpixels est calculé à partir de w
, h
, L
et la taille de l'image. Dans OpenCV, en utilisant les équations ci-dessus, w
et h
est calculé à partir du nombre souhaité de superpixels et du nombre de niveaux (qui sont déterminés par les paramètres correspondants).
Un paramètre reste flou: le précédent essaie d'appliquer des limites lisses. En pratique, cela se fait en considérant le voisinage 3 x 3
autour d'un pixel qui va être mis à jour. Si la plupart des pixels de ce voisinage appartiennent au superpixel j
, le pixel à mettre à jour est également plus susceptible d'appartenir au superpixel j
(et vice versa). La mise en œuvre d'OpenCV ainsi que ma mise en œuvre (SEEDS révisée), permettent d'envisager des quartiers plus larges k x k
avec k in {0,...,5}
dans le cas d'OpenCV.