nx_imgransac.nx source
↩ module page · 101 lines · 5546 B
1// nx_imgransac.nx -- GEOMETRIC VERIFICATION by translation consensus (integer RANSAC).
2//
3// Descriptor matching alone is not identity -- two images can share a handful of similar-looking
4// local patches by chance. What makes it identity is that the matched points AGREE ON ONE GEOMETRY:
5// if this is really the same picture, every true correspondence is explained by a single consistent
6// coordinate transform, and the chance matches are not. Counting how many matches obey one transform
7// (the INLIERS) is the signal; that inlier count is what separates "some patches rhymed" from "this
8// is the same image, cropped".
9//
10// TRANSLATION MODEL, and why it is the RIGHT one for the classes we target rather than a shortcut:
11// nx_imgxform's crop is a sub-window COPY (pixels unchanged, coordinate origin shifted) and its
12// letterbox is a border PAD (pixels unchanged, coordinate origin shifted the other way). Both map an
13// original point (x,y) to a transformed point (x+dx, y+dy) under ONE offset. So the maximal set of
14// matches sharing an offset (within a pixel tolerance) is exactly the inlier set, and finding it is a
15// 2-DOF consensus -- no float, no matrix, no iteration count to tune. Rotation and scale need the
16// affine/similarity extension (filed); the dihedral tier already owns the rotation axis globally.
17//
18// This is a genuine RANSAC in the Fischler-Bolles sense: each match is a minimal hypothesis (one
19// point pair determines the translation), and we score every hypothesis by its consensus set. With
20// n <= KP_MAX matches the O(n^2) all-pairs evaluation is exhaustive, so it finds the global best
21// consensus deterministically -- no random sampling, no seed, bit-reproducible.
22// genealogy_id: fischler_bolles_1981_ransac (translation consensus). license_tier: ORIGINAL
23import "syscalls.nx"
24
25const RANSAC_TOL: i64 = 2 // pixel tolerance for a match to count as an inlier of a hypothesis
26
27func rn_abs(v: i64) -> i64 { if v < 0 { return 0 - v } return v }
28
29// Return the size of the largest consensus set under a single translation, and (if out_off != 0) the
30// winning (dx,dy) offset in out_off[0],out_off[1]. n = number of matched pairs.
31func nx_imgransac_inliers(qx: *i64, qy: *i64, dx: *i64, dy: *i64, n: i64, out_off: *i64) -> i64 {
32 if n <= 0 { if out_off != (0 as *i64) { out_off[0] = 0; out_off[1] = 0 } return 0 }
33 var best: i64 = 0
34 var boffx: i64 = 0
35 var boffy: i64 = 0
36 var h: i64 = 0
37 while h < n {
38 let ox: i64 = dx[h] - qx[h]
39 let oy: i64 = dy[h] - qy[h]
40 var cnt: i64 = 0
41 var k: i64 = 0
42 while k < n {
43 let kx: i64 = dx[k] - qx[k]
44 let ky: i64 = dy[k] - qy[k]
45 if rn_abs(kx - ox) <= RANSAC_TOL { if rn_abs(ky - oy) <= RANSAC_TOL { cnt = cnt + 1 } }
46 k = k + 1
47 }
48 if cnt > best { best = cnt; boffx = ox; boffy = oy }
49 h = h + 1
50 }
51 if out_off != (0 as *i64) { out_off[0] = boffx; out_off[1] = boffy }
52 return best
53}
54
55// SIMILARITY consensus (translation + uniform SCALE): the model d = s*q + t, for matching a query to a
56// corpus copy that has been cropped AND rescaled (the real-web thumbnail). Pure translation cannot
57// verify a scale change, so a cropped-and-resized copy scores zero on the translation model above; this
58// recovers it. Integer fixed-point (scale in units of 1/256), no float, no sqrt: scale is estimated
59// from the ratio of L1 spans of a MINIMAL pair, which for a uniform scale is exact enough for a
60// tolerance vote. Each pair (a,b) is a minimal hypothesis (2 point-pairs fix s and t); we score its
61// consensus set and keep the best -- a genuine RANSAC, exhaustive over pairs (n<=KP_MAX so O(n^3) is
62// bounded), hence deterministic with no random sampling.
63const RANSAC_SIM_TOL: i64 = 4 // base-pixel tolerance (scale amplifies error, so > translation tol)
64const RANSAC_SIM_MINSPAN: i64 = 8 // minimal L1 span of the reference pair (small spans -> unstable s)
65const RANSAC_SIM_SMIN: i64 = 128 // 0.5x in 1/256 units -- reject implausible scale estimates
66const RANSAC_SIM_SMAX: i64 = 768 // 3.0x
67
68func nx_imgransac_inliers_sim(qx: *i64, qy: *i64, dx: *i64, dy: *i64, n: i64, out_scale256: *i64) -> i64 {
69 if n <= 0 { if out_scale256 != (0 as *i64) { out_scale256[0] = 256 } return 0 }
70 var best: i64 = 0
71 var bests: i64 = 256
72 var a: i64 = 0
73 while a < n {
74 var b: i64 = a + 1
75 while b < n {
76 let lq: i64 = rn_abs(qx[b]-qx[a]) + rn_abs(qy[b]-qy[a])
77 let ld: i64 = rn_abs(dx[b]-dx[a]) + rn_abs(dy[b]-dy[a])
78 if lq >= RANSAC_SIM_MINSPAN {
79 let s: i64 = (ld * 256) / lq
80 if s >= RANSAC_SIM_SMIN { if s <= RANSAC_SIM_SMAX {
81 // t = d_a - s*q_a (in 1/256 units)
82 let tx: i64 = dx[a] * 256 - s * qx[a]
83 let ty: i64 = dy[a] * 256 - s * qy[a]
84 var cnt: i64 = 0
85 var k: i64 = 0
86 while k < n {
87 let px: i64 = (s * qx[k] + tx) / 256
88 let py: i64 = (s * qy[k] + ty) / 256
89 if rn_abs(px - dx[k]) <= RANSAC_SIM_TOL { if rn_abs(py - dy[k]) <= RANSAC_SIM_TOL { cnt = cnt + 1 } }
90 k = k + 1
91 }
92 if cnt > best { best = cnt; bests = s }
93 } }
94 }
95 b = b + 1
96 }
97 a = a + 1
98 }
99 if out_scale256 != (0 as *i64) { out_scale256[0] = bests }
100 return best
101}