measure.label2 source code

1 module measure.label2;
2 import measure.types;
3 
4 import std.stdio;
5 import std.array;
6 import std.algorithm.iteration;
7 import std.algorithm;
8 import std.typecons;
9 
10 /* The algorithm is based on:
11  * https://stackoverflow.com/questions/14465297/connected-component-labelling
12  */
13 private
14 {
15     alias UnionFun4Conn = void function(int x, int y);
16     Mat2D!ubyte input;
17     size_t w, h;
18     uint[] component;
19 }
20 
21 private void doUnion(uint a, uint b)
22 {
23     while (component[a] != a)
24         a = component[a];
25     while (component[b] != b)
26         b = component[b];
27     component[b] = a;
28 }
29 
30 private void unionCoords(int x, int y, int x2, int y2)
31 {
32     if (y2 < h && x2 < w && input[x, y] && input[x2, y2])
33         doUnion(cast(uint)(x*h + y), cast(uint)(x2*h + y2));
34 }
35 
36 private void conn8Fun(int x, int y)
37 {
38     unionCoords(x, y, x+1, y);
39     unionCoords(x, y, x, y+1);
40     unionCoords(x, y, x+1, y+1);
41 }
42 
43 private void conn4Fun(int x, int y)
44 {
45     unionCoords(x, y, x+1, y);
46     unionCoords(x, y, x, y+1);
47 }
48 
49 XYList[] bwlabel2(Mat2D!ubyte img, bool conn8 = true)
50 {
51     // gives coordinates of connected components
52     XYList[] coords;
53     
54     input = img;
55     
56     h = img.width;
57     w = img.height;
58     
59     component = new uint[w*h];
60     
61     UnionFun4Conn uFun;
62     if(conn8)
63         uFun = &conn8Fun;
64     else
65         uFun = &conn4Fun;
66     
67     for (int i = 0; i < w*h; i++)
68         component[i] = i;
69     for (int x = 0; x < w; x++)
70     for (int y = 0; y < h; y++)
71         uFun(x, y);
72     
73     XYList[uint] pmap;
74     
75     for (int x = 0; x < w; x++)
76     {
77         for (int y = 0; y < h; y++)
78         {
79             if (input[x, y] == 0)
80             {
81                 continue;
82             }
83             uint c = cast(uint)(x*h + y);
84             while (component[c] != c) c = component[c];
85             
86             if(c !in pmap)
87             {
88                 XYList tmp;
89                 tmp.xs ~= y;
90                 tmp.ys ~= x;
91                 pmap[c] = tmp;
92             }else{
93                 pmap[c].xs ~= y;
94                 pmap[c].ys ~= x;
95             }
96 
97             
98         }
99     }
100     
101     foreach(key; pmap.keys)
102     {
103         coords ~= pmap[key];
104     }
105     
106     return coords;
107 }