nx_segmenter_classical.nx source
↩ module page · 412 lines · 14005 B
1// nx_segmenter_classical.nx -- classical-CV connected-component segmenter.
2//
3// CAPABILITY_COMPLETENESS: PARTIAL
4// MISSING_CAPABILITIES:
5// - face landmark detection (eye / nose / mouth keypoints):
6// queued (needs trained classifier or Haar cascade);
7// blocks per-region phrasing like "blob 0 is the face"
8// - hand-specific segmentation (palm + fingers separated from
9// wrist): nx_segmenter_classical returns generic skin blobs;
10// downstream nx_hand_skeleton (queued) would post-process
11// - anatomical region naming (wrist / inside-elbow / etc.):
12// queued; needs pose estimator or landmark detector
13//
14// COVERED:
15// - Generic binary-mask connected-component labeling
16// (4-connectivity, union-find for label merging in 2 passes)
17// - Per-blob bounding box + pixel count
18// - Skin-mask integration: caller may use nx_color_skin_mask
19// output as input, or any other binary mask
20// - Sealed-enum blob-classification by shape proxies (queued
21// as v2; v1 returns just geometry)
22//
23// This primitive unblocks region-based tier-axis graders by
24// providing the SEGMENTATION INPUT they need. After this ships,
25// the v0 composer can promote axes from PENDING_SEGMENTATION to
26// OK for any region the grader can be invoked with explicit
27// bounding-box bounds (vein-signal in a wrist bbox; subsurface
28// in a fingertip bbox; etc.).
29//
30// genealogy_id: rosenfeld_1966_connected_components
31// lineage_id: nx_segmenter_classical_v1
32
33// nx_safety_envelope:
34// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
35// sil_target: SIL1
36// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
37// verdict: NOT_YET_EVALUATED
38
39import "nx_syscalls.nx"
40import "nx_runtime.nx"
41import "nx_tier.nx"
42const NX_MAGIC_1048576: i64 = 1048576
43
44// ===== bounds =====================================================
45
46const NX_SEG_MAX_DIM: nx_int = 8192
47const NX_SEG_MAX_BLOBS: nx_int = 65536
48const NX_SEG_MIN_BLOB_PIXELS: nx_int = 4 // drop noise specks
49
50// ===== blob struct ================================================
51
52struct NxSegBlob {
53 label: nx_int,
54 x0: nx_int,
55 y0: nx_int,
56 x1: nx_int, // exclusive
57 y1: nx_int, // exclusive
58 pixel_count: nx_int,
59}
60
61const NX_SEG_BLOB_BYTES: nx_size = 56
62
63// ===== top-level result ===========================================
64
65struct NxSegResult {
66 n_blobs: nx_int,
67 blobs: *NxSegBlob,
68 width: nx_int,
69 height: nx_int,
70 label_map: *nx_int, // per-pixel root label; 0 = background
71 error_code: nx_int,
72}
73
74const NX_SEG_RESULT_BYTES: nx_size = 48
75
76// ===== error codes ================================================
77
78const NX_SEG_OK: nx_int = 0
79const NX_SEG_ERR_BAD_DIM: nx_int = 1
80const NX_SEG_ERR_OVERFLOW: nx_int = 2
81
82// ===== union-find helpers =========================================
83
84func _seg_find_root(parent: *nx_int, x: nx_int) -> nx_int {
85 var cur: nx_int = x
86 var safety: nx_int = 0
87 let MAX_DEPTH: nx_int = NX_MAGIC_1048576
88 while safety < MAX_DEPTH {
89 let p: nx_int = parent[cur]
90 if p == cur { return cur }
91 cur = p
92 safety = safety + 1
93 }
94 return cur
95}
96
97func _seg_union(parent: *nx_int, a: nx_int, b: nx_int) -> nx_int {
98 let ra: nx_int = _seg_find_root(parent, a)
99 let rb: nx_int = _seg_find_root(parent, b)
100 if ra == rb { return ra }
101 // Smaller label becomes root (canonical for stable IDs).
102 if ra < rb {
103 parent[rb] = ra
104 return ra
105 }
106 parent[ra] = rb
107 return rb
108}
109
110// ===== two-pass connected-components labeling =====================
111//
112// Input: binary mask (0 = background, !=0 = foreground), w x h.
113// Output: label_map with root labels (0 = background, 1.. = blobs)
114// + per-blob bbox + pixel count.
115
116func nx_segmenter_connected(
117 mask: *nx_int, w: nx_int, h: nx_int) -> *NxSegResult {
118
119 let r_ptr: *u8 = sys_mmap(NX_SEG_RESULT_BYTES)
120 let r: *NxSegResult = r_ptr as *NxSegResult
121 r.error_code = NX_SEG_OK
122 r.n_blobs = 0
123 r.blobs = 0 as *NxSegBlob
124 r.label_map = 0 as *nx_int
125
126 if w <= 0 { r.error_code = NX_SEG_ERR_BAD_DIM; return r }
127 if h <= 0 { r.error_code = NX_SEG_ERR_BAD_DIM; return r }
128 if w > NX_SEG_MAX_DIM { r.error_code = NX_SEG_ERR_BAD_DIM; return r }
129 if h > NX_SEG_MAX_DIM { r.error_code = NX_SEG_ERR_BAD_DIM; return r }
130
131 let n_pixels: nx_int = w * h
132 let label_map_bytes: nx_size = (n_pixels as nx_size) * 8
133 let label_map: *nx_int = (sys_mmap(label_map_bytes)) as *nx_int
134 var p: nx_int = 0
135 while p < n_pixels {
136 label_map[p] = 0
137 p = p + 1
138 }
139
140 // Parent table for union-find. Cap at MAX_BLOBS labels (way
141 // larger than needed for most images).
142 let parent_bytes: nx_size = (NX_SEG_MAX_BLOBS as nx_size) * 8
143 let parent: *nx_int = (sys_mmap(parent_bytes)) as *nx_int
144 parent[0] = 0
145 var next_label: nx_int = 1
146
147 // Pass 1: scan top-to-bottom left-to-right; check N + W neighbors.
148 var y: nx_int = 0
149 while y < h {
150 var x: nx_int = 0
151 while x < w {
152 let idx: nx_int = y * w + x
153 if mask[idx] != 0 {
154 var west: nx_int = 0
155 var north: nx_int = 0
156 if x > 0 { west = label_map[idx - 1] }
157 if y > 0 { north = label_map[idx - w] }
158 if west == 0 {
159 if north == 0 {
160 // New label.
161 if next_label >= NX_SEG_MAX_BLOBS {
162 r.error_code = NX_SEG_ERR_OVERFLOW
163 return r
164 }
165 parent[next_label] = next_label
166 label_map[idx] = next_label
167 next_label = next_label + 1
168 } else {
169 label_map[idx] = north
170 }
171 } else {
172 if north == 0 {
173 label_map[idx] = west
174 } else {
175 // Both neighbors labeled; union + assign smaller.
176 let chosen: nx_int = _seg_union(parent, west, north)
177 label_map[idx] = chosen
178 }
179 }
180 }
181 x = x + 1
182 }
183 y = y + 1
184 }
185
186 // Pass 2: resolve every pixel to its root label.
187 var q: nx_int = 0
188 while q < n_pixels {
189 if label_map[q] != 0 {
190 label_map[q] = _seg_find_root(parent, label_map[q])
191 }
192 q = q + 1
193 }
194
195 // Compact root labels to dense 1..N + compute per-blob bbox.
196 let remap_bytes: nx_size = (next_label as nx_size) * 8
197 let remap: *nx_int = (sys_mmap(remap_bytes)) as *nx_int
198 var ri: nx_int = 0
199 while ri < next_label {
200 remap[ri] = 0
201 ri = ri + 1
202 }
203 // First scan: count roots + assign new compact IDs.
204 var n_roots: nx_int = 0
205 var qi: nx_int = 1
206 while qi < next_label {
207 let root: nx_int = _seg_find_root(parent, qi)
208 if root == qi {
209 n_roots = n_roots + 1
210 remap[qi] = n_roots
211 }
212 qi = qi + 1
213 }
214 // Propagate remap to non-root labels.
215 var qj: nx_int = 1
216 while qj < next_label {
217 if remap[qj] == 0 {
218 let root2: nx_int = _seg_find_root(parent, qj)
219 remap[qj] = remap[root2]
220 }
221 qj = qj + 1
222 }
223
224 // Allocate blob array + initialize.
225 let blob_bytes: nx_size = ((n_roots + 1) as nx_size) * NX_SEG_BLOB_BYTES
226 let blobs: *NxSegBlob = (sys_mmap(blob_bytes)) as *NxSegBlob
227 var bi: nx_int = 0
228 while bi <= n_roots {
229 let bp: *NxSegBlob =
230 (blobs as *u8 + (bi as nx_size) * NX_SEG_BLOB_BYTES) as *NxSegBlob
231 bp.label = bi
232 bp.x0 = w
233 bp.y0 = h
234 bp.x1 = 0
235 bp.y1 = 0
236 bp.pixel_count = 0
237 bi = bi + 1
238 }
239
240 // Update bboxes by scanning label_map (also remap labels in-place).
241 var py: nx_int = 0
242 while py < h {
243 var px: nx_int = 0
244 while px < w {
245 let idx2: nx_int = py * w + px
246 let raw: nx_int = label_map[idx2]
247 if raw != 0 {
248 let new_id: nx_int = remap[raw]
249 label_map[idx2] = new_id
250 let blob: *NxSegBlob =
251 (blobs as *u8 + (new_id as nx_size) * NX_SEG_BLOB_BYTES) as *NxSegBlob
252 if px < blob.x0 { blob.x0 = px }
253 if py < blob.y0 { blob.y0 = py }
254 if (px + 1) > blob.x1 { blob.x1 = px + 1 }
255 if (py + 1) > blob.y1 { blob.y1 = py + 1 }
256 blob.pixel_count = blob.pixel_count + 1
257 }
258 px = px + 1
259 }
260 py = py + 1
261 }
262
263 // Filter out blobs with pixel_count < MIN_BLOB_PIXELS. We
264 // mark them as label=0 in the blob array but keep them present
265 // so caller can iterate; or we compact. For simplicity: compact.
266 let final_blobs: *NxSegBlob = (sys_mmap(blob_bytes)) as *NxSegBlob
267 var n_final: nx_int = 0
268 var bk: nx_int = 1
269 while bk <= n_roots {
270 let bp_src: *NxSegBlob =
271 (blobs as *u8 + (bk as nx_size) * NX_SEG_BLOB_BYTES) as *NxSegBlob
272 if bp_src.pixel_count >= NX_SEG_MIN_BLOB_PIXELS {
273 n_final = n_final + 1
274 let bp_dst: *NxSegBlob =
275 (final_blobs as *u8 + (n_final as nx_size) * NX_SEG_BLOB_BYTES) as *NxSegBlob
276 bp_dst.label = n_final
277 bp_dst.x0 = bp_src.x0
278 bp_dst.y0 = bp_src.y0
279 bp_dst.x1 = bp_src.x1
280 bp_dst.y1 = bp_src.y1
281 bp_dst.pixel_count = bp_src.pixel_count
282 }
283 bk = bk + 1
284 }
285
286 r.n_blobs = n_final
287 r.blobs = final_blobs
288 r.width = w
289 r.height = h
290 r.label_map = label_map
291 return r
292}
293
294// ===== find largest blob =========================================
295
296func nx_segmenter_largest_blob(r: *NxSegResult) -> *NxSegBlob {
297 if r.n_blobs <= 0 { return 0 as *NxSegBlob }
298 var best_idx: nx_int = 1
299 var best_size: nx_int = 0
300 var i: nx_int = 1
301 while i <= r.n_blobs {
302 let b: *NxSegBlob =
303 (r.blobs as *u8 + (i as nx_size) * NX_SEG_BLOB_BYTES) as *NxSegBlob
304 if b.pixel_count > best_size {
305 best_size = b.pixel_count
306 best_idx = i
307 }
308 i = i + 1
309 }
310 return (r.blobs as *u8 + (best_idx as nx_size) * NX_SEG_BLOB_BYTES) as *NxSegBlob
311}
312
313// ===== self-test ==================================================
314
315func _seg_zero(buf: *nx_int, n: nx_int) -> nx_int {
316 var i: nx_int = 0
317 while i < n {
318 buf[i] = 0
319 i = i + 1
320 }
321 return 0
322}
323
324func _seg_fill_rect(mask: *nx_int, w: nx_int,
325 x0: nx_int, y0: nx_int, x1: nx_int, y1: nx_int) -> nx_int {
326 var y: nx_int = y0
327 while y < y1 {
328 var x: nx_int = x0
329 while x < x1 {
330 mask[y * w + x] = 1
331 x = x + 1
332 }
333 y = y + 1
334 }
335 return 0
336}
337
338func main() -> nx_int {
339 // ---- empty mask -> 0 blobs ----
340 let m_empty: *nx_int = (sys_mmap(800)) as *nx_int
341 _seg_zero(m_empty, 100)
342 let r_empty: *NxSegResult = nx_segmenter_connected(m_empty, 10, 10)
343 if r_empty == (0 as *NxSegResult) { return 1 }
344 if r_empty.error_code != NX_SEG_OK { return 2 }
345 if r_empty.n_blobs != 0 { return 3 }
346
347 // ---- one square blob 5x5 ----
348 let m_one: *nx_int = (sys_mmap(800)) as *nx_int
349 _seg_zero(m_one, 100)
350 _seg_fill_rect(m_one, 10, 2, 2, 7, 7)
351 let r_one: *NxSegResult = nx_segmenter_connected(m_one, 10, 10)
352 if r_one.n_blobs != 1 { return 10 }
353 let b0: *NxSegBlob =
354 (r_one.blobs as *u8 + (1 as nx_size) * NX_SEG_BLOB_BYTES) as *NxSegBlob
355 if b0.x0 != 2 { return 11 }
356 if b0.y0 != 2 { return 12 }
357 if b0.x1 != 7 { return 13 }
358 if b0.y1 != 7 { return 14 }
359 if b0.pixel_count != 25 { return 15 }
360
361 // ---- two separate blobs ----
362 let m_two: *nx_int = (sys_mmap(800)) as *nx_int
363 _seg_zero(m_two, 100)
364 _seg_fill_rect(m_two, 10, 0, 0, 3, 3) // 3x3 at top-left
365 _seg_fill_rect(m_two, 10, 6, 6, 9, 9) // 3x3 at bottom-right
366 let r_two: *NxSegResult = nx_segmenter_connected(m_two, 10, 10)
367 if r_two.n_blobs != 2 { return 20 }
368
369 // ---- U-shape requires union-find label merge ----
370 //
371 // XXX
372 // X X
373 // XXX
374 //
375 // This forms a single connected component via the bottom row.
376 let m_u: *nx_int = (sys_mmap(800)) as *nx_int
377 _seg_zero(m_u, 100)
378 // Top row
379 _seg_fill_rect(m_u, 10, 2, 2, 5, 3)
380 // Sides
381 _seg_fill_rect(m_u, 10, 2, 3, 3, 5)
382 _seg_fill_rect(m_u, 10, 4, 3, 5, 5)
383 // Bottom row
384 _seg_fill_rect(m_u, 10, 2, 4, 5, 5)
385 let r_u: *NxSegResult = nx_segmenter_connected(m_u, 10, 10)
386 if r_u.n_blobs != 1 { return 30 }
387
388 // ---- noise speck (1 pixel) below MIN_BLOB_PIXELS = 4 is dropped ----
389 let m_noise: *nx_int = (sys_mmap(800)) as *nx_int
390 _seg_zero(m_noise, 100)
391 m_noise[5 * 10 + 5] = 1 // single pixel
392 _seg_fill_rect(m_noise, 10, 0, 0, 3, 3) // real 9-pixel blob
393 let r_noise: *NxSegResult = nx_segmenter_connected(m_noise, 10, 10)
394 if r_noise.n_blobs != 1 { return 40 } // single pixel dropped
395
396 // ---- largest blob helper ----
397 let m_largest: *nx_int = (sys_mmap(800)) as *nx_int
398 _seg_zero(m_largest, 100)
399 _seg_fill_rect(m_largest, 10, 0, 0, 2, 2) // small 4-pixel
400 _seg_fill_rect(m_largest, 10, 5, 5, 9, 9) // larger 16-pixel
401 let r_largest: *NxSegResult = nx_segmenter_connected(m_largest, 10, 10)
402 if r_largest.n_blobs != 2 { return 50 }
403 let big: *NxSegBlob = nx_segmenter_largest_blob(r_largest)
404 if big.pixel_count != 16 { return 51 }
405 if big.x0 != 5 { return 52 }
406
407 // ---- BAD_DIM rejection ----
408 let r_bad: *NxSegResult = nx_segmenter_connected(m_empty, 0, 10)
409 if r_bad.error_code != NX_SEG_ERR_BAD_DIM { return 60 }
410
411 return 0
412}