Experiment: Circular center/range encoding for tiles instead of min/dist

[jotoft]

Idea

Replace the current linear min/dist tile encoding with a circular center/range encoding that treats pixel values as points on a circle (0-255 wrapping).

Current Approach (min/dist)

Each 4×4 tile stores:

• min: minimum pixel value
• dist: max - min
• indices: each pixel stored as pixel - min using ceil(log2(dist + 1)) bits

Proposed Approach (center/range)

Each 4×4 tile stores:

• center: center of the smallest circular arc containing all values
• range: width of that arc
• indices: each pixel stored as circular offset using ceil(log2(range + 1)) bits

Why This Could Be Better

Circular range is always ≤ linear dist:

Pixels	Linear (min/dist)	Circular (center/range)
[100, 105, 110, 115]	dist=15, 4 bits	range=15, 4 bits (equal)
[250, 255, 0, 5]	dist=255, 8 bits	range=11, 4 bits (better!)
[128, 130, 126, 132]	dist=6, 3 bits	range=6, 3 bits (equal)

For values that wrap around 0/255, circular encoding can significantly reduce bits needed.

Algorithm

Encoding (find optimal center)

fn find_circular_range(pixels: &[u8; 16]) -> (u8, u8) {
    // Sort unique values
    let mut sorted: Vec<u8> = pixels.iter().copied().collect();
    sorted.sort();
    sorted.dedup();
    
    if sorted.len() == 1 {
        return (sorted[0], 0);
    }
    
    // Find largest gap between consecutive values (circularly)
    let mut max_gap = 0u16;
    let mut gap_end = sorted[0];
    
    for i in 0..sorted.len() {
        let next = if i + 1 < sorted.len() { 
            sorted[i + 1] 
        } else { 
            sorted[0].wrapping_add(256 - sorted[sorted.len() - 1]) // wrap
        };
        let gap = next.wrapping_sub(sorted[i]) as u16;
        if gap > max_gap {
            max_gap = gap;
            gap_end = next;
        }
    }
    
    // Range starts at gap_end, spans 256 - max_gap
    let range = (256 - max_gap) as u8;
    let start = gap_end;
    let center = start.wrapping_add(range / 2);
    
    (center, range)
}

Decoding

fn decode_pixel(center: u8, range: u8, index: u8) -> u8 {
    let start = center.wrapping_sub(range / 2);
    start.wrapping_add(index)
}

Testing Plan

1. Implement both encodings side-by-side
2. Run on test corpus of grayscale images
3. Measure:
   • Total bits saved across all tiles
   • Percentage of tiles where circular is better
   • Compression ratio improvement
4. Benchmark encoding/decoding speed difference

Expected Outcomes

• Best case: Images with high pixel values near 255 (bright regions with noise) could see meaningful improvement
• Typical case: Most natural images won't wrap, so equal performance
• Worst case: Equal to current (never worse)

Considerations

• Format change: Would require new format version if adopted
• Compatibility: Could be opt-in via a flag bit in the header
• Complexity: Slightly more complex encode/decode, but O(1) operations

Questions to Answer

1. How often do real-world tiles benefit from circular encoding?
2. Is the improvement significant enough to justify format change?
3. Any edge cases where the algorithm breaks down?

[jotoft]

Additional Use Cases

Beyond the 0/255 wraparound edge case, circular encoding would also help with:

High contrast edges

Tiles spanning bright/dark boundaries where values cluster at both extremes:

Tile at specular highlight / shadow edge:
┌─────────────────────┐
│  5   3   250  252   │
│  2   4   255  251   │
│  1   0   253  254   │
│  3   2   250  255   │
└─────────────────────┘

Linear:   min=0, max=255, dist=255 → 8 bits  
Circular: values cluster around 0/255 → range≈11 → 4 bits

This is actually common in:

• Specular highlights next to shadows
• Text/graphics (black on white)
• High contrast scenes (sun glare, night photography)

Multi-channel workflows

When using helpers to compress RGB/Bayer/RGB-IR as separate grayscale channels, some channels may have different value distributions. Circular encoding gives you potential improvement on specific channels at no cost to others.

Rationale

Even if the improvement is marginal in average case, the argument is:

• Never worse than linear encoding
• Negligible compute cost (few extra arithmetic ops)
• Same metadata size (still 2 bytes per tile)

It's a strict improvement with essentially no downside beyond code complexity.

[jotoft]

Quick note: Probably better with using min as base and let dist be able to wrap around 255->0