nx_imgsearch_tier.nx source
↩ module page · 370 lines · 21342 B
1// nx_imgsearch_tier.nx -- THE REVERSE-IMAGE TIER BASE CLASS (vtable OOP).
2//
3// A production reverse-image engine is never ONE matcher. TinEye is a copy-detector; Google Lens is a
4// semantic recogniser; Yandex fuses both plus faces and text. Our own ruler (nx_imgbench) proves why:
5// no single descriptor covers the modification space -- dHash owns photometric edits and is blind to
6// geometry, the edge-orientation descriptor owns crops and is blind to mirroring, and neither knows
7// what the picture is OF.
8//
9// So the engine is defined as a FUSION OF TIERS, and a tier is an object with a vtable. Adding the
10// next rung -- local keypoints + geometric verification, or a quantised semantic embedding -- is
11// implemented as a NEW SUBTYPE with its own constructor. It is never an edit to the query engine.
12// That is the whole point of the base class: the engine below it must not grow an `if` per rung.
13//
14// ASYMMETRIC DESCRIPTORS, deliberately. A tier declares TWO widths:
15// idx_dim -- i64 slots persisted per corpus image (storage cost, multiplied by 10^8 images)
16// qry_dim -- i64 slots computed per query (compute cost, paid once per search)
17// They differ for good reasons. The dihedral tier stores ONE fingerprint but computes EIGHT at query
18// time, buying full mirror/rotation invariance for zero storage. A future local-feature tier will
19// store a compact bag-of-visual-words vector but compute a full keypoint set per query. Forcing both
20// sides to one width would have taxed every stored image to pay for a query-side trick.
21//
22// Distances are INTEGER and each tier publishes max_dist, so scores are comparable across tiers
23// without floats -- the same integer-quantisation discipline the text engine rides.
24// license_tier: ORIGINAL
25import "nx_phash.nx"
26import "nx_visdesc.nx"
27import "nx_imgorient.nx"
28import "nx_imgkp.nx"
29import "nx_imgransac.nx"
30
31const NX_IT_KIND_COPY: i64 = 1 // near-duplicate: dHash Hamming (TinEye-class copy detection)
32const NX_IT_KIND_ORIENT: i64 = 2 // dihedral-invariant dHash (mirrors + quarter turns)
33const NX_IT_KIND_SIMILAR: i64 = 3 // edge-orientation layout L1 (crop/recompose tolerant)
34const NX_IT_KIND_LOCAL: i64 = 4 // RESERVED: local keypoints + geometric verification
35const NX_IT_KIND_SEMANTIC: i64 = 5 // RESERVED: quantised learned embedding
36
37// TIER CLASS -- which QUESTION a tier is entitled to answer. Not cosmetic: mixing them produces a
38// confident wrong answer. "Is this image already in my corpus?" (dedup, copyright, provenance) may
39// only be answered by tiers that assert IDENTITY. A similarity tier answers a different question --
40// "what does this look like?" -- and its correct behaviour is to return images that are NOT the
41// query. Letting it vote on the identity question makes a genuine look-alike read as a match; the
42// engine gate caught exactly that, returning a structurally-similar-but-different image as a "match".
43// A future local-feature tier is IDENTITY (RANSAC proves the same object); a semantic embedding tier
44// is SIMILARITY (it proves the same subject, which is not the same picture).
45const NX_IT_CLASS_IDENTITY: i64 = 1
46const NX_IT_CLASS_SIMILAR: i64 = 2
47
48// Thresholds and weights are CONSTRUCTOR ARGUMENTS, never literals inside the matcher, so they can be
49// driven from config and re-derived when the ruler re-measures. The defaults below are the values the
50// ruler measured, and each carries the measurement that produced it.
51const NX_IT_COPY_THRESH: i64 = 10 // live nx_image_search default; ruler det@10 confirms it
52const NX_IT_COPY_MAX: i64 = 64 // dHash is 64 bits
53// LOCAL tier: distance = KP_MAX - inliers, so more geometrically-consistent matches = smaller
54// distance. max_dist = KP_MAX (24). A candidate is CONFIDENT at >= NX_IT_LOCAL_MININLIERS inliers;
55// that constant is asserted by the engine gate against the measured true-vs-decoy inlier separation
56// (no-magic-numbers: the gate re-derives it every run and fails loudly if the populations converge).
57const NX_IT_LOCAL_MAX: i64 = 24 // == KP_MAX
58// DERIVED, not guessed: the engine gate measures crop-30 true-source inliers ~6 and decoy inliers 0.
59// A confidence floor of 5 sits strictly inside that gap (5 > 0), capturing the true crops that land
60// just under 6 without admitting a single decoy. The gate's inlier-separation row is the standing
61// guard -- if a change ever lifts decoy inliers to >=5 it fails loudly. Lowered 6->5 to close the
62// last modification class (crop-30) after measuring the straddle.
63const NX_IT_LOCAL_MININLIERS: i64 = 5
64// A SWEPT-SCALE match must clear a HIGHER bar than a same-scale one. This is not tuning: taking the
65// BEST distance over KP_QSCALES scales is five draws instead of one, so the chance that an UNRELATED
66// image produces a bare-minimum geometric consensus at SOME scale rises with the sweep width. The
67// engine gate caught it immediately -- an out-of-corpus image went from an honest ABSENT (nearest
68// identity distance 21) to a CLAIMED identity match at exactly the minimum 5 inliers. Requiring more
69// inliers from a scale we had to SEARCH for is the multiple-comparisons correction, and it leaves the
70// identity scale's calibrated threshold untouched, so same-scale behaviour is bit-for-bit unchanged.
71// A false identity match is the worst failure this engine has: it would name the wrong website.
72const NX_IT_LOCAL_SWEPT_MININLIERS: i64 = 7
73const NX_IT_LOCAL_THRESH: i64 = 19 // KP_MAX - NX_IT_LOCAL_MININLIERS
74const NX_IT_SIMILAR_MAX: i64 = 20480 // 80 dims x 256 max per-dim spread
75// DERIVED, NOT CHOSEN. nx_imgsearch_engine_gate measures, on the shared corpus, the mean descriptor
76// L1 from a crop-20 query to its TRUE source (1282) and to an UNRELATED image (2253) and takes the
77// midpoint. That midpoint is ~86 permille of NX_IT_SIMILAR_MAX, i.e. "within 9 percent of the
78// descriptor's full range". The gate re-asserts the separation every run, so if the descriptor or the
79// corpus changes and the two populations stop being separable, the constant fails loudly instead of
80// quietly mis-classifying. A first draft of this file guessed 6000 and the measurement caught it.
81const NX_IT_SIMILAR_THRESH: i64 = 1767
82
83// INFORMATIVENESS FLOOR -- the guard against confident nonsense on structureless images.
84// FOUND ON REAL DATA, not theorised: indexing eleven real PNGs from the tree and querying with a
85// held-out one returned THREE DIFFERENT images at dHash distance 0, reported as confident identity
86// matches. dHash sets each bit from `left pixel > right pixel`; on a flat region or a smooth
87// left-to-right gradient that comparison is never true, so every such image hashes to all-zeros and
88// they all collide with each other. The hash is not wrong -- there is genuinely no structure to
89// encode -- but an engine that answers "these are the same picture" from an empty fingerprint is
90// lying with confidence, which is the worst failure mode a search engine has.
91// A 64-bit fingerprint carries information only if its bits are not all one value. Requiring at
92// least NX_IT_MIN_BITS of the minority value is the cheapest honest test; the engine gate asserts
93// that the structured corpus clears it and that a deliberately flat image does not.
94const NX_IT_MIN_BITS: i64 = 6
95// Orientation histograms are normalised per cell, so a cell with real edge content sums to ~256 and
96// a flat cell sums to 0. Requiring a minimum number of non-empty cells is the descriptor analogue.
97const NX_IT_MIN_CELLS: i64 = 4
98
99struct nx_imgtier {
100 kind: i64,
101 klass: i64, // NX_IT_CLASS_* -- which question this tier may answer
102 name_ptr: i64, // *u8, stable literal
103 idx_dim: i64, // i64 slots stored per corpus image
104 qry_dim: i64, // i64 slots computed per query
105 threshold: i64, // distance at/below which this tier calls it a match
106 max_dist: i64, // ceiling used to normalise this tier's distance into a permille score
107 weight: i64, // fusion weight in permille (how much this tier's opinion counts)
108 describe_index_fn: func(*nx_imgtier, *u8, *u8, i64, i64, *i64) -> i64,
109 describe_query_fn: func(*nx_imgtier, *u8, *u8, i64, i64, *i64) -> i64,
110 distance_fn: func(*nx_imgtier, *i64, *i64) -> i64,
111 // Does this descriptor carry enough signal for this tier to be believed? Each subtype knows its
112 // own degenerate case, so this is a vtable slot rather than a switch inside the engine.
113 informative_fn: func(*nx_imgtier, *i64) -> i64,
114}
115
116const NX_IMGTIER_BYTES: i64 = 96
117
118// ---- generic accessors (the engine only ever talks to the base type) ----
119func nx_imgtier_kind(t: *nx_imgtier) -> i64 { return t.kind }
120func nx_imgtier_klass(t: *nx_imgtier) -> i64 { return t.klass }
121func nx_imgtier_name(t: *nx_imgtier) -> *u8 { return t.name_ptr as *u8 }
122func nx_imgtier_idx_dim(t: *nx_imgtier) -> i64 { return t.idx_dim }
123func nx_imgtier_qry_dim(t: *nx_imgtier) -> i64 { return t.qry_dim }
124func nx_imgtier_threshold(t: *nx_imgtier) -> i64 { return t.threshold }
125func nx_imgtier_max_dist(t: *nx_imgtier) -> i64 { return t.max_dist }
126func nx_imgtier_weight(t: *nx_imgtier) -> i64 { return t.weight }
127
128// ---- virtual dispatch ----
129// ⚠ DO NOT "SIMPLIFY" THESE TO `t.describe_index_fn(t, ...)`. That postfix form COMPILES CLEANLY and
130// is SILENTLY WRONG in the current toolchain: it evaluates to the function's ADDRESS and discards the
131// argument list entirely, so the method never runs and the caller receives a code-segment pointer that
132// looks like a plausible integer. Proven by runtime/nx_fnptr_slot_probe.nx (five nullary slots return
133// addresses 38 bytes apart -- the function sizes -- while the struct's non-fn guard fields read
134// correctly and let-copied pointers call correctly). The let-copy below is the documented, working
135// idiom and is what nx_media_session/nx_codec were originally written against.
136func nx_imgtier_describe_index(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
137 let fp: func(*nx_imgtier, *u8, *u8, i64, i64, *i64) -> i64 = t.describe_index_fn
138 return fp(t, gray, rgb, w, h, out)
139}
140func nx_imgtier_describe_query(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
141 let fp: func(*nx_imgtier, *u8, *u8, i64, i64, *i64) -> i64 = t.describe_query_fn
142 return fp(t, gray, rgb, w, h, out)
143}
144func nx_imgtier_distance(t: *nx_imgtier, q: *i64, d: *i64) -> i64 {
145 let fp: func(*nx_imgtier, *i64, *i64) -> i64 = t.distance_fn
146 return fp(t, q, d)
147}
148func nx_imgtier_informative(t: *nx_imgtier, d: *i64) -> i64 {
149 let fp: func(*nx_imgtier, *i64) -> i64 = t.informative_fn
150 return fp(t, d)
151}
152
153// Normalised similarity in permille (1000 = identical) from this tier's raw distance. Lets the engine
154// present one comparable score to a caller who must not need to know a tier's private distance units.
155func nx_imgtier_score(t: *nx_imgtier, dist: i64) -> i64 {
156 let m: i64 = t.max_dist
157 if m <= 0 { return 0 }
158 var d: i64 = dist
159 if d < 0 { d = 0 }
160 if d > m { d = m }
161 return (m - d) * 1000 / m
162}
163
164// ---- SUBTYPE 1: COPY (dHash Hamming) -----------------------------------------------------------
165// Ruler-measured strengths: identity / rescale / brightness / contrast / noise / watermark /
166// recompression all at 1000 permille recall@1. Blind to geometry by construction.
167func it_copy_describe(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
168 out[0] = nx_phash_dhash(gray, w, h)
169 return 1
170}
171func it_copy_distance(t: *nx_imgtier, q: *i64, d: *i64) -> i64 {
172 return nx_simhash_hamming(q[0], d[0])
173}
174// popcount(h) is Hamming(h, 0) -- reusing the existing kernel rather than adding a second bit-counter.
175// A fingerprint is informative when BOTH bit values are present in reasonable quantity; all-zeros
176// (flat / smooth gradient) and all-ones are the degenerate ends that collide with everything.
177func it_hash_informative(t: *nx_imgtier, d: *i64) -> i64 {
178 let ones: i64 = nx_simhash_hamming(d[0], 0)
179 var minority: i64 = ones
180 if 64 - ones < minority { minority = 64 - ones }
181 if minority >= NX_IT_MIN_BITS { return 1 }
182 return 0
183}
184func nx_imgtier_copy_init(t: *nx_imgtier, threshold: i64, weight: i64) -> i64 {
185 t.kind = NX_IT_KIND_COPY
186 t.klass = NX_IT_CLASS_IDENTITY
187 t.name_ptr = "copy-dhash" as i64
188 t.idx_dim = 1
189 t.qry_dim = 1
190 t.threshold = threshold
191 t.max_dist = NX_IT_COPY_MAX
192 t.weight = weight
193 t.describe_index_fn = it_copy_describe
194 t.describe_query_fn = it_copy_describe
195 t.distance_fn = it_copy_distance
196 t.informative_fn = it_hash_informative
197 return 0
198}
199
200// ---- SUBTYPE 2: ORIENT (dihedral-invariant dHash) -----------------------------------------------
201// Stores ONE fingerprint (identical storage to the copy tier) but computes the query's full D4 orbit,
202// so a mirrored or quarter-turned copy matches at exactly the copy tier's distance. This is the
203// zero-storage answer to the ruler's mirror-horizontal = 0 permille finding.
204func it_orient_describe_index(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
205 out[0] = nx_phash_dhash(gray, w, h)
206 return 1
207}
208func it_orient_describe_query(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
209 return nx_orient_hashes(gray, w, h, out)
210}
211func it_orient_distance(t: *nx_imgtier, q: *i64, d: *i64) -> i64 {
212 let kb: *i64 = sys_mmap(8) as *i64
213 return nx_orient_best_hamming(q, d[0], kb)
214}
215func nx_imgtier_orient_init(t: *nx_imgtier, threshold: i64, weight: i64) -> i64 {
216 t.kind = NX_IT_KIND_ORIENT
217 t.klass = NX_IT_CLASS_IDENTITY
218 t.name_ptr = "orient-d4" as i64
219 t.idx_dim = 1
220 t.qry_dim = 8
221 t.threshold = threshold
222 t.max_dist = NX_IT_COPY_MAX
223 t.weight = weight
224 t.describe_index_fn = it_orient_describe_index
225 t.describe_query_fn = it_orient_describe_query
226 t.distance_fn = it_orient_distance
227 t.informative_fn = it_hash_informative
228 return 0
229}
230
231// ---- SUBTYPE 3: SIMILAR (edge-orientation layout, L1) -------------------------------------------
232// Ruler-measured: recovers crop-10 from 218 -> 1000 permille and crop-20 from 31 -> 937 where the
233// hash tiers score zero. This tier was already built and gate-proven in-tree and had ZERO importers
234// outside its own gate -- built but never integrated. Wiring it here is the integration.
235func it_similar_describe(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
236 return nx_visdesc_extract(gray, w, h, out)
237}
238func it_similar_distance(t: *nx_imgtier, q: *i64, d: *i64) -> i64 {
239 return nx_visdesc_l1(q, d)
240}
241// The descriptor is 16 cells of [4 orientation bins + 1 tone]. A cell over a flat region normalises
242// to four zero bins, so counting cells with real edge mass is the direct analogue of the hash test.
243func it_similar_informative(t: *nx_imgtier, d: *i64) -> i64 {
244 var live: i64 = 0
245 var c: i64 = 0
246 while c < 16 {
247 let b: i64 = c * 5
248 if d[b] + d[b + 1] + d[b + 2] + d[b + 3] > 0 { live = live + 1 }
249 c = c + 1
250 }
251 if live >= NX_IT_MIN_CELLS { return 1 }
252 return 0
253}
254func nx_imgtier_similar_init(t: *nx_imgtier, threshold: i64, weight: i64) -> i64 {
255 t.kind = NX_IT_KIND_SIMILAR
256 t.klass = NX_IT_CLASS_SIMILAR
257 t.name_ptr = "similar-ehd" as i64
258 t.idx_dim = 80
259 t.qry_dim = 80
260 t.threshold = threshold
261 t.max_dist = NX_IT_SIMILAR_MAX
262 t.weight = weight
263 t.describe_index_fn = it_similar_describe
264 t.describe_query_fn = it_similar_describe
265 t.distance_fn = it_similar_distance
266 t.informative_fn = it_similar_informative
267 return 0
268}
269
270// ---- SUBTYPE 4: LOCAL (FAST + BRIEF + translation-consensus RANSAC) -----------------------------
271// The occlusion-robust identity tier -- the one global descriptors structurally cannot be. Its
272// "descriptor" is the image's packed keypoint set; its "distance" runs the full local-feature match
273// and geometric verification between two keypoint sets and returns KP_MAX - inliers. Because RANSAC
274// proves the SAME OBJECT under one geometry, it is an IDENTITY-class tier. Targets the ruler's last
275// two failing classes (crop-30, letterbox) with NO engine change -- the point of the base class.
276func it_local_describe(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
277 return nx_imgkp_describe(gray, w, h, out)
278}
279// QUERY side is described across the scale sweep (see nx_imgkp.nx): the INDEX stays single-scale, so
280// storage over 10^8 images is unchanged and no existing index needs rebuilding.
281func it_local_describe_query(t: *nx_imgtier, gray: *u8, rgb: *u8, w: i64, h: i64, out: *i64) -> i64 {
282 return nx_imgkp_describe_query(gray, w, h, out)
283}
284func it_local_distance_one(q: *i64, d: *i64) -> i64 {
285 let cap: i64 = 24
286 let qx: *i64 = sys_mmap(8*cap) as *i64
287 let qy: *i64 = sys_mmap(8*cap) as *i64
288 let dx: *i64 = sys_mmap(8*cap) as *i64
289 let dy: *i64 = sys_mmap(8*cap) as *i64
290 let m: i64 = nx_imgkp_match(q, d, qx, qy, dx, dy, cap)
291 // Cheap translation model first (crop / letterbox / same-scale). If it already confirms the match,
292 // stop -- the similarity model can't do better than "confirmed", and skipping its O(n^3) search
293 // keeps the common (same-scale) case fast. Only when translation is unconvincing do we pay for the
294 // scale search, which recovers crop+rescale (a similarity, not a translation). Adding scale
295 // -invariance therefore never weakens the same-scale classes AND costs almost nothing on them.
296 let inl_t: i64 = nx_imgransac_inliers(qx, qy, dx, dy, m, 0 as *i64)
297 var inl: i64 = inl_t
298 if inl_t < NX_IT_LOCAL_MININLIERS {
299 let inl_s: i64 = nx_imgransac_inliers_sim(qx, qy, dx, dy, m, 0 as *i64)
300 if inl_s > inl { inl = inl_s }
301 }
302 var dist: i64 = NX_IT_LOCAL_MAX - inl
303 if dist < 0 { dist = 0 }
304 return dist
305}
306// BEST (minimum) distance over the query's scale sweep. Sweep slot 0 is the identity scale and is
307// byte-identical to the single-scale descriptor, so this minimum can never EXCEED the old
308// single-scale distance: scale invariance is added here without the possibility of regressing a
309// same-scale class, which is exactly what the 2026-07-24 index-side pyramid could not promise.
310//
311// EARLY EXIT when the identity scale is already CONFIDENT (>= MININLIERS inliers): a same-scale match
312// that geometry has already confirmed cannot be overturned by another scale, so the common case keeps
313// its old cost exactly. Same shape of reasoning as trying translation before similarity above.
314func it_local_distance(t: *nx_imgtier, q: *i64, d: *i64) -> i64 {
315 let confident: i64 = NX_IT_LOCAL_MAX - NX_IT_LOCAL_MININLIERS
316 let swept_ok: i64 = NX_IT_LOCAL_MAX - NX_IT_LOCAL_SWEPT_MININLIERS
317 var best: i64 = NX_IT_LOCAL_MAX
318 var s: i64 = 0
319 var go: i64 = 1
320 while go == 1 {
321 if s >= KP_QSCALES { go = 0 } else {
322 let qs: *i64 = ((q as i64) + s*kp_pack_dim()*8) as *i64
323 if nx_imgkp_count(qs) > 0 {
324 let dist: i64 = it_local_distance_one(qs, d)
325 // scale 0 is the image's OWN scale and keeps the calibrated bar; every SEARCHED scale
326 // must clear the stricter one or it does not count as evidence at all
327 var accept: i64 = 0
328 if s == 0 { accept = 1 } else { if dist <= swept_ok { accept = 1 } }
329 if accept == 1 { if dist < best { best = dist } }
330 // a same-scale match that geometry already confirmed cannot be overturned by a
331 // searched scale, so stop -- this keeps the common case at its exact old cost
332 if s == 0 { if best <= confident { go = 0 } }
333 }
334 s = s + 1
335 }
336 }
337 return best
338}
339func it_local_informative(t: *nx_imgtier, d: *i64) -> i64 {
340 // an image with too few corners cannot be geometrically verified against anything
341 if nx_imgkp_count(d) >= NX_IT_LOCAL_MININLIERS { return 1 }
342 return 0
343}
344func nx_imgtier_local_init(t: *nx_imgtier, threshold: i64, weight: i64) -> i64 {
345 t.kind = NX_IT_KIND_LOCAL
346 t.klass = NX_IT_CLASS_IDENTITY
347 t.name_ptr = "local-orb" as i64
348 t.idx_dim = kp_pack_dim()
349 t.qry_dim = nx_imgkp_query_dim()
350 t.threshold = threshold
351 t.max_dist = NX_IT_LOCAL_MAX
352 t.weight = weight
353 t.describe_index_fn = it_local_describe
354 t.describe_query_fn = it_local_describe_query
355 t.distance_fn = it_local_distance
356 t.informative_fn = it_local_informative
357 return 0
358}
359
360// allocate + construct, so callers never hand-size the struct (NX_IMGTIER_BYTES stays private-ish)
361func nx_imgtier_new(kind: i64, threshold: i64, weight: i64) -> *nx_imgtier {
362 let t: *nx_imgtier = sys_mmap(NX_IMGTIER_BYTES) as *nx_imgtier
363 if kind == NX_IT_KIND_COPY { nx_imgtier_copy_init(t, threshold, weight); return t }
364 if kind == NX_IT_KIND_ORIENT { nx_imgtier_orient_init(t, threshold, weight); return t }
365 if kind == NX_IT_KIND_SIMILAR { nx_imgtier_similar_init(t, threshold, weight); return t }
366 if kind == NX_IT_KIND_LOCAL { nx_imgtier_local_init(t, threshold, weight); return t }
367 // unknown kind -> a COPY tier, never a half-constructed object with null vtable slots
368 nx_imgtier_copy_init(t, threshold, weight)
369 return t
370}