nx_integral.nx source
↩ module page · 92 lines · 3771 B
1// nx_integral.nx -- integral image (summed-area table). R-FACE-0: the
2// foundation of fast Haar-feature / Viola-Jones face detection. After an O(N)
3// build, the sum of ANY axis-aligned rectangle is O(1) via four lookups --
4// which is what makes a sliding-window cascade tractable.
5//
6// SAT[y][x] (1-based, with a zero top row + left col) = sum of all pixels
7// strictly above-left. Rectangle [x0..x1] x [y0..y1] inclusive =
8// S = SAT[y1+1][x1+1] - SAT[y0][x1+1] - SAT[y1+1][x0] + SAT[y0][x0].
9// Pure i64. Operates on a 1-channel (grayscale) Image.
10//
11// genealogy_id: crow_1984_summed_area_table + viola_jones_2001 (record-hint)
12// lineage_id: summed_area_table + o1_rectangle_sum
13// nx_safety_envelope:
14// intended_use: "Foundation for Haar features / face detection."
15// verdict: NOT_YET_EVALUATED
16// license_tier: ORIGINAL
17import "syscalls.nx"
18import "nx_image.nx"
19
20struct IntegralImage {
21 data: *i64,
22 w: i64,
23 h: i64,
24}
25const NX_II_BYTES: i64 = 24
26
27// Build the summed-area table of a grayscale image (channel 0).
28func nx_integral_build(gray: *Image) -> *IntegralImage {
29 let w: i64 = gray.width
30 let h: i64 = gray.height
31 let stride: i64 = w + 1
32 let ii: *IntegralImage = sys_mmap(NX_II_BYTES) as *IntegralImage
33 ii.w = w
34 ii.h = h
35 ii.data = sys_mmap((w + 1) * (h + 1) * 8 + 16) as *i64
36 let total: i64 = (w + 1) * (h + 1)
37 var i: i64 = 0
38 while i < total { ii.data[i] = 0; i = i + 1 } // zero top row + left col stay 0
39 var y: i64 = 1
40 while y <= h {
41 var x: i64 = 1
42 while x <= w {
43 let p: i64 = nx_image_get(gray, x - 1, y - 1, 0)
44 ii.data[y * stride + x] = p + ii.data[(y - 1) * stride + x] + ii.data[y * stride + (x - 1)] - ii.data[(y - 1) * stride + (x - 1)]
45 x = x + 1
46 }
47 y = y + 1
48 }
49 return ii
50}
51
52// O(1) inclusive rectangle sum [x0..x1] x [y0..y1].
53func nx_integral_rect_sum(ii: *IntegralImage, x0: i64, y0: i64, x1: i64, y1: i64) -> i64 {
54 let stride: i64 = ii.w + 1
55 let d: *i64 = ii.data
56 let a: i64 = d[(y1 + 1) * stride + (x1 + 1)]
57 let b: i64 = d[y0 * stride + (x1 + 1)]
58 let c: i64 = d[(y1 + 1) * stride + x0]
59 let e: i64 = d[y0 * stride + x0]
60 return a - b - c + e
61}
62
63// Integral tables straight from a raw 8-bit gray plane (no Image struct): the sum table and the sum-of-squares table a
64// variance-normalised Haar window needs (2026-09-16, aesthetictwin AT30). Same 1-based layout as nx_integral_build, so
65// nx_integral_rect_sum reads both. A squared sum fits i64 for any plane the estate decodes (255^2 x 8192^2 < 2^63).
66const NX_II_BYTE: i64 = 255
67func nx_integral_from_plane(gray: *u8, w: i64, h: i64, plane_stride: i64, squared: i64) -> *IntegralImage {
68 let stride: i64 = w + 1
69 let ii: *IntegralImage = sys_mmap(NX_II_BYTES) as *IntegralImage
70 ii.w = w
71 ii.h = h
72 ii.data = sys_mmap((w + 1) * (h + 1) * 8 + 16) as *i64
73 var x0: i64 = 0
74 while x0 <= w { ii.data[x0] = 0; x0 = x0 + 1 }
75 var y: i64 = 1
76 while y <= h {
77 ii.data[y * stride] = 0
78 var rowsum: i64 = 0
79 var x: i64 = 1
80 while x <= w {
81 var p: i64 = (gray[(y - 1) * plane_stride + (x - 1)] as i64) & NX_II_BYTE
82 if squared == 1 { p = p * p }
83 rowsum = rowsum + p
84 ii.data[y * stride + x] = ii.data[(y - 1) * stride + x] + rowsum
85 x = x + 1
86 }
87 y = y + 1
88 }
89 return ii
90}
91func nx_integral_from_gray(gray: *u8, w: i64, h: i64, plane_stride: i64) -> *IntegralImage { return nx_integral_from_plane(gray, w, h, plane_stride, 0) }
92func nx_integral_sq_from_gray(gray: *u8, w: i64, h: i64, plane_stride: i64) -> *IntegralImage { return nx_integral_from_plane(gray, w, h, plane_stride, 1) }