Suche nach Connected Component Labeling Algorithmus Implementierung

Question

Ich bin auf der Suche nach einem optimierten 4-Connectivity oder 8-Connectivity Connected Component Labeling-Quellcode in MATLAB oder C++. Ich sah viele Implementierungen von Connected Component Labelling (4-Connectivity) in MATLAB.

Einer der Implementierungen, die schneller arbeitet, ist die rekursive Implementierung hier erklärt: http://www.mathworks.com/matlabcentral/fileexchange/38010-connected-component-labeling-like-bwlabel

MATLAB verfügt über eine integrierte in bwlabeln oder bwlabel, die weit mehr optimiert. Sie behaupten, Union-Find-Methode von Zwei-Pass-Algorithmus, beschrieben in Sedgewicks Algorithmen in C, Addison-Wesley. Es ist jedoch schwer, einen Quellcode davon zu finden. Hat jemand eine Vorstellung davon? Ein optimierter Code wird wirklich benötigt.

Answer 1

Sie können tatsächlich arbeiten, indem Sie das Bild in Scanline-Reihenfolge scannen und wenn Sie eine Komponente erfüllen, füllen Sie es aus.

Sie finden zwei effiziente (und sehr ähnlich) Algorithmen in Graphics GEMS 1:

• A SEED Füllalgorithmus, Paul S. Heckbert

• eine Region in einem Bildspeicher FÜLLEN, Ken Fishkin

und mit ein wenig Aufwand einige Implementierungen. (Die Papiere geben Pascal-ähnlichen Code, der leicht zu übersetzen ist.)

Sie laufen in linearer Zeit, verwenden einen expliziten Stapel und erfordern keine Union-Suche.