nx_integral.nx source
↩ module page · 61 lines · 2260 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}