Img2Num C++ (Internal Developer Docs) dev
API Documentation
Loading...
Searching...
No Matches
graph.cpp
1#include "internal/graph.h"
2
3#include "internal/bezier.h"
4#include "internal/Pixel.h"
5#include "internal/shared_contours.h"
6
7#include <algorithm>
8#include <cmath>
9#include <cstdlib>
10#include <iterator>
11#include <queue>
12#include <string>
13/*
14 Graph class - manages Node class
15*/
16
17/*
18To quickly search m_nodes (std::vector) for the index of a node id
19create an std::unordered_map of node id - index pairs
20indexing time of std::vector by value is O(N)
21lookup time of std::unordered_map by key is O(log(N))
22*/
23void Graph::hash_node_ids() {
24 for (int32_t i {0}; i < m_nodes->size(); i++) {
25 const int32_t key {m_nodes->at(i)->id()};
26 m_node_ids[key] = i;
27 }
28}
29
30bool Graph::add_edge(int32_t node_id1, int32_t node_id2) {
31 auto end_node_ids {m_node_ids.end()};
32 auto node1_it {m_node_ids.find(node_id1)};
33 auto node2_it {m_node_ids.find(node_id2)};
34
35 if (node1_it == end_node_ids || node2_it == end_node_ids) {
36 return false;
37 }
38
39 const int32_t idx1 {node1_it->second};
40 const int32_t idx2 {node2_it->second};
41
42 m_nodes->at(idx1)->add_edge(m_nodes->at(idx2));
43 m_nodes->at(idx2)->add_edge(m_nodes->at(idx1));
44 return true;
45}
46
47bool Graph::merge_nodes(const Node_ptr& node_to_keep, const Node_ptr& node_to_remove) {
48 auto end_node_ids {m_node_ids.end()};
49 auto node1_it {m_node_ids.find(node_to_keep->id())};
50 auto node2_it {m_node_ids.find(node_to_remove->id())};
51
52 if (node1_it == end_node_ids || node2_it == end_node_ids) {
53 return false;
54 }
55
56 const int32_t idx_k {node1_it->second};
57 const int32_t idx_r {node2_it->second};
58
59 // transfer edges from node_to_remove to node_to_keep
60 for (Node_ptr n : m_nodes->at(idx_r)->edges()) {
61 if (n->id() != node_to_keep->id()) {
62 // prevents self referencing
63 n->remove_edge(node_to_remove);
64 n->add_edge(node_to_keep);
65 node_to_keep->add_edge(n);
66 }
67 }
68
69 node_to_keep->add_pixels(node_to_remove->get_pixels());
70
71 node_to_remove->clear_all();
72
73 return true;
74}
75
76void Graph::clear_unconnected_nodes() {
77 std::vector<Node_ptr>& nodes {*m_nodes};
78
79 nodes.erase(
80 std::remove_if(
81 nodes.begin(), nodes.end(), [](const Node_ptr& n) { return n->area() == 0; }
82 ),
83 nodes.end()
84 );
85
86 hash_node_ids();
87}
88
89void Graph::discover_edges(
90 const std::vector<int32_t>& region_labels, const int32_t width, const int32_t height
91) {
92 // Moore 8-connected neighbourhood
93 constexpr int8_t dirs[8][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1},
94 {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
95
96 int32_t rneigh[8];
97
98 for (int32_t y {0}; y < height; ++y) {
99 for (int32_t x {0}; x < width; ++x) {
100 const int32_t idx {y * width + x};
101 const int32_t rid {region_labels[idx]};
102
103 for (int32_t k {0}; k < 8; ++k) {
104 const int32_t nx {x + dirs[k][0]};
105 const int32_t ny {y + dirs[k][1]};
106
107 if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
108 rneigh[k] = region_labels[ny * width + nx];
109 } else {
110 rneigh[k] = rid; // ignore out-of-bounds
111 }
112 }
113
114 for (int32_t r : rneigh) {
115 if (r != rid) {
116 add_edge(rid, r);
117 }
118 }
119 }
120 }
121}
122
123void Graph::compute_contours() {
124
125 /*
126 Shared-edge mode: build region boundaries on the crack grid so
127 neighbouring contours are exactly coincident along shared edges -- no
128 overlap band, no gaps
129 */
130
131 float eps = 0.25f;
132
133 std::vector<int32_t> labels(static_cast<size_t>(m_width) * m_height, -1);
134 for (const Node_ptr& n : get_nodes()) {
135 if (n->area() == 0)
136 continue;
137 for (auto& p : n->get_pixels())
138 labels[static_cast<size_t>(p.position.y) * m_width + p.position.x] = n->id();
139 }
140
141 auto loops = build_shared_loops(labels, m_width, m_height, eps);
142
143 for (const Node_ptr& n : get_nodes()) {
144 if (n->area() == 0)
145 continue;
146 n->clear_contour();
147 auto it = loops.find(n->id());
148 if (it == loops.end())
149 continue;
150 ImageLib::RGBPixel<uint8_t> c = n->color();
151 ImageLib::RGBAPixel<uint8_t> col {c.red, c.green, c.blue, 255};
152 for (std::vector<QuadBezier>& curve : it->second) {
153 std::vector<Point> anchors; // keep contours[] parallel to curves[]
154 anchors.reserve(curve.size() + 1);
155 for (const QuadBezier& q : curve)
156 anchors.push_back(q.p0);
157 if (!curve.empty())
158 anchors.push_back(curve.back().p2);
159 n->m_contours.contours.push_back(std::move(anchors));
160 n->m_contours.curves.push_back(std::move(curve));
161 n->m_contours.colors.push_back(col);
162 n->m_contours.hierarchy.push_back({-1, -1, -1, -1});
163 n->m_contours.is_hole.push_back(false);
164 }
165 }
166}
167
168namespace {
169
170// 1D squared-distance transform (Felzenszwalb & Huttenlocher): for every q,
171// d[q] = min_p ( (q - p)^2 + f[p] ). O(n).
172void dt_1d(const std::vector<float>& f, std::vector<float>& d, int n) {
173 constexpr float INF = 1e20f;
174 std::vector<int> v(n);
175 std::vector<float> z(n + 1);
176 int k = 0;
177 v[0] = 0;
178 z[0] = -INF;
179 z[1] = INF;
180 for (int q = 1; q < n; ++q) {
181 float s;
182 while (true) {
183 s = ((f[q] + static_cast<float>(q) * q) - (f[v[k]] + static_cast<float>(v[k]) * v[k])) /
184 (2.0f * static_cast<float>(q - v[k]));
185 if (s <= z[k] && k > 0) {
186 --k;
187 } else {
188 break;
189 }
190 }
191 ++k;
192 v[k] = q;
193 z[k] = s;
194 z[k + 1] = INF;
195 }
196 k = 0;
197 for (int q = 0; q < n; ++q) {
198 while (z[k + 1] < static_cast<float>(q))
199 ++k;
200 const float dq = static_cast<float>(q - v[k]);
201 d[q] = dq * dq + f[v[k]];
202 }
203}
204
205// Largest inscribed-disk radius (in pixels) of a region: the maximum over all
206// region pixels of the Euclidean distance to the nearest non-region pixel.
207// Computed with an exact squared Euclidean distance transform, so the result is
208// independent of how long or how curved the region is -- a property that a
209// bounding-box aspect ratio does not have. Thickness ~= 2 * this radius.
210float max_inscribed_radius(const Node_ptr& n) {
211 std::vector<uint8_t> mask;
212 const std::array<int, 4> xywh = n->create_binary_image(mask); // tight bbox
213 const int w = xywh[2];
214 const int h = xywh[3];
215 if (w <= 0 || h <= 0)
216 return 0.0f;
217
218 // Pad by one pixel so the region's boundary against the exterior is treated
219 // as background by the distance transform.
220 const int pw = w + 2;
221 const int ph = h + 2;
222 constexpr float INF = 1e20f;
223
224 std::vector<float> grid(static_cast<size_t>(pw) * ph);
225 for (int y = 0; y < ph; ++y) {
226 for (int x = 0; x < pw; ++x) {
227 const bool inside = x >= 1 && x <= w && y >= 1 && y <= h &&
228 mask[static_cast<size_t>(y - 1) * w + (x - 1)];
229 grid[static_cast<size_t>(y) * pw + x] = inside ? INF : 0.0f;
230 }
231 }
232
233 // Separable two-pass transform: columns first, then rows.
234 std::vector<float> in, out(std::max(pw, ph));
235 in.resize(ph);
236 for (int x = 0; x < pw; ++x) {
237 for (int y = 0; y < ph; ++y)
238 in[y] = grid[static_cast<size_t>(y) * pw + x];
239 dt_1d(in, out, ph);
240 for (int y = 0; y < ph; ++y)
241 grid[static_cast<size_t>(y) * pw + x] = out[y];
242 }
243 in.resize(pw);
244 float max_d2 = 0.0f;
245 for (int y = 0; y < ph; ++y) {
246 for (int x = 0; x < pw; ++x)
247 in[x] = grid[static_cast<size_t>(y) * pw + x];
248 dt_1d(in, out, pw);
249 for (int x = 0; x < pw; ++x)
250 if (out[x] > max_d2)
251 max_d2 = out[x];
252 }
253 return std::sqrt(max_d2);
254}
255
256} // namespace
257
258void Graph::merge_small_area_nodes(const int32_t min_area, const int32_t min_thickness) {
259 // Keep merging while any pass still makes progress. Using "did this pass
260 // merge anything?" as the loop guard (instead of re-testing every node)
261 // also avoids spinning forever on a node that is too small/thin but has no
262 // valid neighbour to merge into.
263 bool merged_any = true;
264 while (merged_any) {
265 merged_any = false;
266
267 for (const Node_ptr& n : get_nodes()) {
268 if (n->area() == 0)
269 continue;
270
271 bool needs_merge = n->area() < static_cast<size_t>(min_area);
272 if (!needs_merge && min_thickness > 0) {
273 // too thin == no inscribed disk of radius min_thickness/2 fits.
274 needs_merge = 2.0f * max_inscribed_radius(n) < static_cast<float>(min_thickness);
275 }
276 if (!needs_merge)
277 continue;
278
279 ImageLib::RGBPixel<uint8_t> col = n->color();
280
281 Node_ptr best_neighbor = nullptr;
282 float best_score = std::numeric_limits<float>::max();
283 for (const Node_ptr& ne : n->edges()) {
284 if (ne->area() > 0) {
285 float cdist = ImageLib::RGBPixel<uint8_t>::colorDistance(ne->color(), col);
286 float score = static_cast<float>(ne->area()) + 10.f * cdist;
287 if (score < best_score) {
288 best_score = score;
289 best_neighbor = ne;
290 }
291 }
292 }
293
294 // no valid neighbor found, skip this node
295 if (!best_neighbor) {
296 continue;
297 }
298
299 if (best_neighbor->area() >= n->area()) {
300 merge_nodes(best_neighbor, n);
301 } else {
302 merge_nodes(n, best_neighbor);
303 }
304 merged_any = true;
305 }
306
307 clear_unconnected_nodes();
308 }
309}