`nx_imgorient.nx` source

↩ module page · 169 lines · 7328 B
1// nx_imgorient.nx -- DIHEDRAL (D4) ORIENTATION-INVARIANT perceptual matching.
2//
3// MEASURED MOTIVATION (nx_imgbench, 2026-07-23): the live reverse-image client scores
4//   mirror-horizontal  recall@1 =    0 permille
5//   rotate-90          recall@1 =   31 permille
6//   rotate-180         recall@1 =   31 permille
7// and det@10 = ZERO for all three -- i.e. a horizontally mirrored copy of an indexed image is, to the
8// production engine, a completely different picture. Mirroring is not exotic: it is what every meme
9// repost, every "flipped to dodge copyright detection" upload, and every front-camera selfie does.
10//
11// THE FIX, and why it is nearly free: the eight rigid symmetries of the square (identity, three
12// rotations, and those four composed with a mirror) form the dihedral group D4. Because D4 is a GROUP,
13// the orbit {g.A : g in D4} of an image A is IDENTICAL to the orbit of any dihedral variant of A --
14// applying h to a rotated copy just re-labels which element of the same eight you land on. Therefore:
15//   * the MULTISET of the eight orientation fingerprints is a dihedral INVARIANT of the image, and
16//   * min-of-eight is a CANONICAL FORM: canonical(A) == canonical(g.A) for every g, exactly, always.
17// No training, no floats, no index change, no extra storage -- pure integer algebra over the existing
18// nx_phash dHash. Eight extra 9x8 downscales per image is nothing.
19//
20// TWO SERVING MODES, deliberately both offered (they trade different things):
21//   canonical  -- store min-of-8, one probe per query. Cheapest; loses WHICH orientation matched and
22//                 very slightly raises collision odds (eight images now share one bucket key).
23//   query-side -- store the plain dHash unchanged, compute the query's eight and probe eight times.
24//                 Zero information lost, zero index migration, reports the matching orientation.
25//                 Costs eight index probes, which a sublinear index (nx_phash_index BK-tree) absorbs.
26//
27// INDEPENDENCE NOTE (rigor, deliberate): the geometric transforms here are implemented from scratch
28// rather than imported from nx_imgxform. nx_imgxform is the ADVERSARY that the ruler attacks us with;
29// this file is the DEFENCE. Sharing one implementation would let a single indexing bug cancel itself
30// out and score as a pass -- the defence must be able to disagree with the attack.
31//
32// genealogy_id: dihedral_group_d4 (classical) over krawetz_2011 dHash
33// license_tier: ORIGINAL
34import "nx_phash.nx"
35
36const OR_COUNT: i64 = 8      // |D4|
37
38const OR_IDENT:  i64 = 0
39const OR_ROT90:  i64 = 1
40const OR_ROT180: i64 = 2
41const OR_ROT270: i64 = 3
42const OR_FLIPH:  i64 = 4
43const OR_TRANSP: i64 = 5
44const OR_FLIPV:  i64 = 6
45const OR_ANTIT:  i64 = 7
46
47func nx_orient_count() -> i64 { return OR_COUNT }
48
49func nx_orient_name(k: i64) -> *u8 {
50    if k == OR_IDENT  { return "identity" as *u8 }
51    if k == OR_ROT90  { return "rot90" as *u8 }
52    if k == OR_ROT180 { return "rot180" as *u8 }
53    if k == OR_ROT270 { return "rot270" as *u8 }
54    if k == OR_FLIPH  { return "mirror-h" as *u8 }
55    if k == OR_TRANSP { return "transpose" as *u8 }
56    if k == OR_FLIPV  { return "mirror-v" as *u8 }
57    if k == OR_ANTIT  { return "anti-transpose" as *u8 }
58    return "?" as *u8
59}
60
61// does orientation k swap the width and height? (the four that involve a quarter turn)
62func or_swaps_dims(k: i64) -> i64 {
63    if k == OR_ROT90  { return 1 }
64    if k == OR_ROT270 { return 1 }
65    if k == OR_TRANSP { return 1 }
66    if k == OR_ANTIT  { return 1 }
67    return 0
68}
69
70// output dimensions of orientation k applied to a w x h image
71func nx_orient_dims(k: i64, w: i64, h: i64, outwh: *i64) -> i64 {
72    if or_swaps_dims(k) == 1 { outwh[0] = h; outwh[1] = w } else { outwh[0] = w; outwh[1] = h }
73    return 0
74}
75
76// apply orientation k, returning a fresh buffer; outwh receives the new dimensions.
77// Source coordinate for destination (x,y) is derived directly from the group element -- no
78// composition of primitive flips, so an error in one element cannot propagate to the others.
79func nx_orient_apply(k: i64, gray: *u8, w: i64, h: i64, outwh: *i64) -> *u8 {
80    nx_orient_dims(k, w, h, outwh)
81    let nw: i64 = outwh[0]
82    let nh: i64 = outwh[1]
83    let out: *u8 = sys_mmap(nw * nh)
84    var y: i64 = 0
85    while y < nh {
86        var x: i64 = 0
87        while x < nw {
88            var sx: i64 = 0
89            var sy: i64 = 0
90            if k == OR_IDENT  { sx = x;         sy = y }
91            if k == OR_ROT90  { sx = y;         sy = h - 1 - x }
92            if k == OR_ROT180 { sx = w - 1 - x; sy = h - 1 - y }
93            if k == OR_ROT270 { sx = w - 1 - y; sy = x }
94            if k == OR_FLIPH  { sx = w - 1 - x; sy = y }
95            if k == OR_TRANSP { sx = y;         sy = x }
96            if k == OR_FLIPV  { sx = x;         sy = h - 1 - y }
97            if k == OR_ANTIT  { sx = w - 1 - y; sy = h - 1 - x }
98            out[y * nw + x] = gray[sy * w + sx]
99            x = x + 1
100        }
101        y = y + 1
102    }
103    return out
104}
105
106// the eight orientation fingerprints of one image, written to out8[0..8). Returns OR_COUNT.
107func nx_orient_hashes(gray: *u8, w: i64, h: i64, out8: *i64) -> i64 {
108    let wh: *i64 = sys_mmap(16) as *i64
109    var k: i64 = 0
110    while k < OR_COUNT {
111        let g: *u8 = nx_orient_apply(k, gray, w, h, wh)
112        out8[k] = nx_phash_dhash(g, wh[0], wh[1])
113        k = k + 1
114    }
115    return OR_COUNT
116}
117
118// UNSIGNED less-than on i64 bit patterns. dHash fills all 64 bits, so a fingerprint with bit 63 set
119// reads as negative; a signed compare would pick a different orbit representative depending on which
120// variant happened to set the top bit, and the canonical form would NOT be invariant. This is the
121// subtle bug the canonical-invariance gate row exists to catch.
122func or_ult(a: i64, b: i64) -> i64 {
123    let sa: i64 = (a >> 63) & 1
124    let sb: i64 = (b >> 63) & 1
125    if sa != sb { if sa == 0 { return 1 } return 0 }
126    if a < b { return 1 }
127    return 0
128}
129
130// CANONICAL FORM: the unsigned-minimum of the eight orientation fingerprints. Equal for an image and
131// every dihedral variant of it, by the group-orbit argument in the header.
132func nx_orient_canonical(gray: *u8, w: i64, h: i64) -> i64 {
133    let h8: *i64 = sys_mmap(8 * OR_COUNT) as *i64
134    nx_orient_hashes(gray, w, h, h8)
135    var best: i64 = h8[0]
136    var k: i64 = 1
137    while k < OR_COUNT {
138        if or_ult(h8[k], best) == 1 { best = h8[k] }
139        k = k + 1
140    }
141    return best
142}
143
144// canonical form of a set of fingerprints already computed (no image needed)
145func nx_orient_canonical_of(h8: *i64) -> i64 {
146    var best: i64 = h8[0]
147    var k: i64 = 1
148    while k < OR_COUNT {
149        if or_ult(h8[k], best) == 1 { best = h8[k] }
150        k = k + 1
151    }
152    return best
153}
154
155// QUERY-SIDE MODE: best Hamming distance from any of the query's eight orientations to `target`.
156// out_k[0] receives WHICH orientation won, so the caller can tell the user "this is the mirrored
157// version" instead of silently pretending the match was upright.
158func nx_orient_best_hamming(q8: *i64, target: i64, out_k: *i64) -> i64 {
159    var best: i64 = 65
160    var bk: i64 = 0
161    var k: i64 = 0
162    while k < OR_COUNT {
163        let d: i64 = nx_simhash_hamming(q8[k], target)
164        if d < best { best = d; bk = k }
165        k = k + 1
166    }
167    out_k[0] = bk
168    return best
169}
nx_imgorient.nx source

`nx_imgorient.nx` source
