nx_scale.nx source
↩ module page · 229 lines · 7837 B
1// nx_scale.nx -- multi-scale image pyramids (V6 of vision rollout).
2//
3// Burt+Adelson 1983 image pyramid: cascade of downsampled blurred
4// images. Each level halves spatial dimensions.
5//
6// G_0 = original
7// G_{n+1} = downsample(gauss_blur(G_n))
8//
9// Difference-of-Gaussians (DoG) approximates Laplacian-of-Gaussian
10// without computing second derivatives. DoG extrema = scale-invariant
11// blob centers (the heart of SIFT, Lowe 2004).
12//
13// What this unlocks:
14// + scale-invariant analysis: feature found at any size
15// + distant-vs-near object discrimination
16// + face / eye / object detection at unknown scale
17// + multi-resolution salience (objects pop at characteristic scale)
18// + image-quality (high-freq energy at level 0 vs blurred)
19//
20// All i64. 5-tap binomial filter [1, 4, 6, 4, 1] / 16 = >> 4.
21// Separable horizontal+vertical pass.
22//
23// genealogy_id: burt_adelson_1983_pyramid + lowe_2004_sift_dog
24// + crowley_1981_dog_blob
25// lineage_id: gaussian_pyramid + dog_blob_detection
26// axioms: NX_AX_LINEAR_FILTER_COMMUTES (separable convolution)
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "syscalls.nx"
35import "nx_image.nx"
36
37// Max 5 levels: a 64x64 image yields 64/32/16/8/4 -- adequate for
38// most photography. Larger pyramids would extend the struct.
39const NX_SCALE_MAX_LEVELS: i64 = 5
40
41struct GaussPyramid {
42 n_levels: i64,
43 l0: *Image,
44 l1: *Image,
45 l2: *Image,
46 l3: *Image,
47 l4: *Image,
48}
49
50func nx_scale_pyramid_get(p: *GaussPyramid, level: i64) -> *Image {
51 if level == 0 { return p.l0 }
52 if level == 1 { return p.l1 }
53 if level == 2 { return p.l2 }
54 if level == 3 { return p.l3 }
55 if level == 4 { return p.l4 }
56 return 0 as *Image
57}
58
59// ===== Gaussian blur (5-tap binomial, separable) =======================
60//
61// Kernel: [1, 4, 6, 4, 1] / 16, applied horizontally then vertically.
62// Out-of-bounds pixels read as 0 (border ringing acceptable for now;
63// reflective boundary would be a refinement).
64
65func nx_scale_gauss_blur(src: *Image) -> *Image {
66 let w: i64 = src.width
67 let h: i64 = src.height
68 let tmp: *Image = nx_image_alloc(w, h, 1)
69 var y: i64 = 0
70 while y < h {
71 var x: i64 = 0
72 while x < w {
73 let p0: i64 = nx_image_get(src, x - 2, y, 0)
74 let p1: i64 = nx_image_get(src, x - 1, y, 0)
75 let p2: i64 = nx_image_get(src, x, y, 0)
76 let p3: i64 = nx_image_get(src, x + 1, y, 0)
77 let p4: i64 = nx_image_get(src, x + 2, y, 0)
78 let v: i64 = (p0 + 4 * p1 + 6 * p2 + 4 * p3 + p4) >> 4
79 nx_image_set(tmp, x, y, 0, v)
80 x = x + 1
81 }
82 y = y + 1
83 }
84 let dst: *Image = nx_image_alloc(w, h, 1)
85 var y2: i64 = 0
86 while y2 < h {
87 var x2: i64 = 0
88 while x2 < w {
89 let p0: i64 = nx_image_get(tmp, x2, y2 - 2, 0)
90 let p1: i64 = nx_image_get(tmp, x2, y2 - 1, 0)
91 let p2: i64 = nx_image_get(tmp, x2, y2, 0)
92 let p3: i64 = nx_image_get(tmp, x2, y2 + 1, 0)
93 let p4: i64 = nx_image_get(tmp, x2, y2 + 2, 0)
94 let v: i64 = (p0 + 4 * p1 + 6 * p2 + 4 * p3 + p4) >> 4
95 nx_image_set(dst, x2, y2, 0, v)
96 x2 = x2 + 1
97 }
98 y2 = y2 + 1
99 }
100 return dst
101}
102
103// ===== Downsample 2x ====================================================
104//
105// Take every other pixel. Anti-aliasing handled by prior Gaussian blur.
106
107func nx_scale_downsample_2x(src: *Image) -> *Image {
108 let w2: i64 = src.width / 2
109 let h2: i64 = src.height / 2
110 let dst: *Image = nx_image_alloc(w2, h2, 1)
111 var y: i64 = 0
112 while y < h2 {
113 var x: i64 = 0
114 while x < w2 {
115 nx_image_set(dst, x, y, 0, nx_image_get(src, 2 * x, 2 * y, 0))
116 x = x + 1
117 }
118 y = y + 1
119 }
120 return dst
121}
122
123// Blur + downsample. This is the canonical pyramid "step down".
124func nx_scale_pyramid_down(src: *Image) -> *Image {
125 let blurred: *Image = nx_scale_gauss_blur(src)
126 return nx_scale_downsample_2x(blurred)
127}
128
129// ===== Gaussian pyramid construction ====================================
130
131func nx_scale_gauss_pyramid(src: *Image, n_levels: i64) -> *GaussPyramid {
132 var n: i64 = n_levels
133 if n < 1 { n = 1 }
134 if n > NX_SCALE_MAX_LEVELS { n = NX_SCALE_MAX_LEVELS }
135 let p: *GaussPyramid = (sys_mmap(48)) as *GaussPyramid
136 p.n_levels = n
137 p.l0 = src
138 p.l1 = 0 as *Image
139 p.l2 = 0 as *Image
140 p.l3 = 0 as *Image
141 p.l4 = 0 as *Image
142 if n >= 2 { p.l1 = nx_scale_pyramid_down(p.l0) }
143 if n >= 3 { p.l2 = nx_scale_pyramid_down(p.l1) }
144 if n >= 4 { p.l3 = nx_scale_pyramid_down(p.l2) }
145 if n >= 5 { p.l4 = nx_scale_pyramid_down(p.l3) }
146 return p
147}
148
149// ===== Difference of Gaussians (DoG) ===================================
150//
151// DoG approximates the Laplacian-of-Gaussian operator and is the
152// blob-detection operator used in SIFT keypoints. We compute the
153// difference between two Gaussian-smoothed versions of the same
154// image, then threshold extrema in (x, y) space.
155//
156// Returns a signed image where positive = bright blobs, negative = dark.
157
158func nx_scale_dog(img: *Image) -> *ImageS64 {
159 let g1: *Image = nx_scale_gauss_blur(img)
160 let g2: *Image = nx_scale_gauss_blur(g1)
161 let dog: *ImageS64 = nx_image_s64_alloc(img.width, img.height)
162 var y: i64 = 0
163 while y < img.height {
164 var x: i64 = 0
165 while x < img.width {
166 let v: i64 = nx_image_get(g1, x, y, 0) - nx_image_get(g2, x, y, 0)
167 nx_image_s64_set(dog, x, y, v)
168 x = x + 1
169 }
170 y = y + 1
171 }
172 return dog
173}
174
175// Find local extrema (3x3 neighborhood) in DoG with |response| >= threshold.
176// out_x, out_y, out_strength: arrays of length max_blobs.
177// Returns number of blobs found.
178
179func nx_scale_dog_extrema(dog: *ImageS64, threshold: i64,
180 max_blobs: i64,
181 out_x: *i64, out_y: *i64,
182 out_strength: *i64) -> i64 {
183 var found: i64 = 0
184 let w: i64 = dog.width
185 let h: i64 = dog.height
186 var y: i64 = 1
187 while y < h - 1 {
188 var x: i64 = 1
189 while x < w - 1 {
190 let v: i64 = nx_image_s64_get(dog, x, y)
191 var av: i64 = v
192 if av < 0 { av = -av }
193 if av >= threshold {
194 // 3x3 extremum check
195 var is_max: i64 = 1
196 var is_min: i64 = 1
197 var dy: i64 = -1
198 while dy <= 1 {
199 var dx: i64 = -1
200 while dx <= 1 {
201 var is_center: i64 = 0
202 if dx == 0 { if dy == 0 { is_center = 1 } }
203 if is_center == 0 {
204 let nv: i64 = nx_image_s64_get(dog, x + dx, y + dy)
205 if nv >= v { is_max = 0 }
206 if nv <= v { is_min = 0 }
207 }
208 dx = dx + 1
209 }
210 dy = dy + 1
211 }
212 var is_extremum: i64 = 0
213 if is_max == 1 { is_extremum = 1 }
214 if is_min == 1 { is_extremum = 1 }
215 if is_extremum == 1 {
216 if found < max_blobs {
217 out_x[found] = x
218 out_y[found] = y
219 out_strength[found] = v
220 found = found + 1
221 }
222 }
223 }
224 x = x + 1
225 }
226 y = y + 1
227 }
228 return found
229}