connected_components.cpp
Go to the documentation of this file.
2 
3 connected_components::connected_components (valarray<int> m, int rows, int cols, bool zeroAsBg) : rows(rows), cols(cols), zeroAsBg(zeroAsBg)
4 {
5  image.resize(rows*cols);
6  image.assign(begin(m), end(m));
7 
8  label2d.resize(rows*cols);
9 }
10 
12 {
13  // label first
14  vector<int> label = labeling();
15  vector<int> stat(next_label+1);
16  for (int i=0; i<image.size(); i++) {
17  stat[label[i]]++;
18  }
19 
20  // label 0 will be mapped to 0
21  stat[0] = 0;
22 
23  // whether 0 is background or not
24  int j = 1;
25  for (int i=1; i<stat.size(); i++) {
26  if (stat[i] != 0)
27  stat[i] = j++;
28  }
29 
30  next_label= j-1;
31  int locIDX=0;
32  for (int i=0; i<label.size(); ++i) {
33  label[i] = stat[label[i]];
34  }
35 
36  copy(label.begin(), label.end(), begin(label2d));
37 
38  return label2d;
39 }
40 
42 {
43  return next_label;
44 }
45 
47 {
48  vector<int> rst(cols*rows);
49  vector<int> parent(cols*rows);
50  vector<int> labels(cols*rows);
51 
52  // region label starts from 1;
53  // this is required as union-find data structure
54  int next_region = 1;
55  for (int y = 0; y < rows; ++y ) {
56  for (int x = 0; x < cols; ++x ) {
57  if (image[y*cols+x] == 0 && zeroAsBg)
58  continue;
59 
60  int k = 0;
61  bool connected = false;
62 
63  // if connected to the left
64  if (x > 0 && image[y*cols+x-1] == image[y*cols+x]) {
65  k = rst[y*cols+x-1];
66  connected = true;
67  }
68 
69  // if connected upwards
70  if (y > 0 && image[(y-1)*cols+x] == image[y*cols+x] && (!connected || image[(y-1)*cols+x] < k)) {
71  k = rst[(y-1)*cols+x];
72  connected = true;
73  }
74 
75  // not connected
76  if (!connected) {
77  k = next_region;
78  next_region++;
79  }
80 
81  // set label
82  rst[y*cols+x] = k;
83 
84  // if connected, but with different label, then do union
85  if (x > 0 && image[y*cols+x-1] == image[y*cols+x] && rst[y*cols+x-1] != k)
86  uf_union(k, rst[y*cols+x-1], parent);
87  if (y > 0 && image[(y-1)*cols+x] == image[y*cols+x] && rst[(y-1)*cols+x] != k)
88  uf_union(k, rst[(y-1)*cols+x], parent);
89  }
90  }
91 
92  // begin the second pass, assign the new labels
93  // if 0 is reserved for background, then the first available label is 1
94  next_label = 1;
95  for (int i=0; i<cols*rows; i++) {
96  if (image[i] != 0 || !zeroAsBg) {
97  rst[i] = uf_find(rst[i], parent, labels);
98  // The labels are from 1, if label 0 should be considered, then
99  // all the label should minus 1
100  if (!zeroAsBg)
101  rst[i]--;
102  }
103  }
104 
105  // record the max label
106  next_label--;
107  if (!zeroAsBg)
108  next_label--;
109 
110  return rst;
111 }
112 
113 void connected_components::uf_union (int x, int y, vector<int>& parent)
114 {
115  while ( parent[x]>0 )
116  x = parent[x];
117  while ( parent[y]>0 )
118  y = parent[y];
119  if ( x != y ) {
120  if (x<y)
121  parent[x] = y;
122  else parent[y] = x;
123  }
124 }
125 
126 int connected_components::uf_find (int x, vector<int> parent, vector<int>& label)
127 {
128  while (parent[x] > 0) {
129  x = parent[x];
130  }
131  if (label[x] == 0) {
132  label[x] = next_label;
133  ++next_label;
134  }
135  return label[x];
136 }
137 
139 {
142 
143  for (int i=0; i<label2d.size(); ++i) {
144  if (label2d[i] == robotsLabel) {
145  BinaryRobot[i] = 1;
146  BinaryNonRobot[i] = 0;
147  }
148  else if (label2d[i] != 0) {
149  BinaryRobot[i] = 0;
150  BinaryNonRobot[i] = 1;
151  }
152  }
153 }
154 
156 {
157  valarray<float> Region(rows*cols);
158 
159  vector<float> f(max(rows, cols));
160  vector<float> d(f.size());
161  vector<int> v(f.size());
162  vector<float> z(f.size() + 1);
163 
164  for (int x=0; x<cols; x++) {
165  for (int y=0; y<rows; y++) {
166  if (RobotR)
167  f[y] = BinaryRobot[y*cols+x] == 0 ? numeric_limits<float>::max() : 0;
168  else
169  f[y] = BinaryNonRobot[y*cols+x] == 0 ? numeric_limits<float>::max() : 0;
170  }
171 
172  DT1D(f, d, v, z);
173  for (int y = 0; y < rows; y++) {
174  Region[y*cols+x] = d[y];
175  }
176  }
177 
178  float maxV=0, minV=numeric_limits<float>::max();
179  for (int y = 0; y < rows; y++) {
180  DT1D(getVector(Region,y), d, v, z);
181 
182  for (int x = 0; x < cols; x++) {
183  Region[y*cols+x] = (float) sqrt(d[x]);
184  if (maxV < Region[y*cols+x]) {maxV = Region[y*cols+x];}
185  if (minV > Region[y*cols+x]) {minV = Region[y*cols+x];}
186  }
187  }
188 
189 
190  //Normalization
191  for (int y = 0; y < rows; y++) {
192  for (int x = 0; x < cols; x++) {
193  if (RobotR)
194  Region[y*cols+x] = (Region[y*cols+x] - minV) * (1/(maxV-minV)) +1;
195  else
196  Region[y*cols+x] = (Region[y*cols+x] - minV) * (1/(maxV-minV));
197  }
198  }
199 
200  return Region;
201 }
202 
203 void connected_components::DT1D(vector<float> f, vector<float>& d, vector<int>& v , vector<float>& z)
204 {
205  int k = 0;
206  v[0] = 0;
207  z[0] = -numeric_limits<float>::max();
208  z[1] = numeric_limits<float>::max();
209 
210  for (int q = 1; q < f.size(); q++) {
211  float s = ((f[q] + q * q) - (f[v[k]] + v[k] * v[k])) / (2 * q - 2 * v[k]);
212 
213  while (s <= z[k]) {
214  k--;
215  s = ((f[q] + q * q) - (f[v[k]] + v[k] * v[k])) / (2 * q - 2 * v[k]);
216  }
217  k++;
218  v[k] = q;
219  z[k] = s;
220  z[k + 1] = numeric_limits<float>::max();
221  }
222 
223  k = 0;
224  for (int q = 0; q < f.size(); q++) {
225  while (z[k + 1] < q) {k++;}
226 
227  d[q] = (q - v[k]) * (q - v[k]) + f[v[k]];
228  }
229 }
230 
231 vector<float> connected_components::getVector (valarray<float> A, int row)
232 {
233  valarray<float> col = A[slice(row*cols, cols, 1)];
234  return vector<float>(begin(col), end(col));
235 }
d
valarray< int > BinaryRobot
Binary array of the label assigned to a robot.
int next_label
The current label ID.
vector< int > image
The image to perform the labeling on.
void uf_union(int x, int y, vector< int > &parent)
Combine two labels.
connected_components(valarray< int > m, int rows, int cols, bool zeroAsBg)
Constructor that initializes the private member variables.
f
int getMaxLabel()
Get the max label of the labeling process which is in the range [0,max_label].
void constructBinaryImages(int robotsLabel)
Create binary arrays of connected labels.
XmlRpcServer s
vector< float > getVector(valarray< float > A, int row)
Get a slice of an array.
vector< int > labeling()
Label the connected components.
int cols
Number of columns of the image.
valarray< float > NormalizedEuclideanDistanceBinary(bool RobotR)
Calculate the normalized euclidean distance transform of a binary image with foreground pixels set to...
valarray< int > compactLabeling()
Rearrange the labels to make the label numbers consecutive.
int rows
Number of rows of the image.
valarray< int > label2d
Array of labels.
bool zeroAsBg
Whether 0 should be considered or not.
valarray< int > BinaryNonRobot
Binary array of the labels not assigned to a robot.
int uf_find(int x, vector< int > parent, vector< int > &label)
Return the root label (starts from 1 because label array is initialized to 0 at first). The label array records the new label for every root.
void DT1D(vector< float > f, vector< float > &d, vector< int > &v, vector< float > &z)
DT1D.


area_division
Author(s): Micha Sende
autogenerated on Tue Jan 19 2021 03:30:02