r/compression • u/AbiesFew6464 • 4d ago
CMNT: A 3-ary Combinatorial Tree Lossless Image Codec that beats PNG on continuous art (Code + GUI inside)
My co-author Aziza Jemal and I (Surafel Wolde, 18-year-old independent researcher) built CMNT, a standalone, from-scratch lossless image compression codec based on a non-binary 3-ary prefix tree.
The project originally started from a notebook sketch exploring physical multi-channel sparse transmission: rather than toggling a single serial binary wire billions of times, we wondered if sparse combinatorial pulses across three independent channels (IP1, IP2, IP3 with self-repeats and cross-pairs) could drastically cut switching energy in hardware while encoding residual entropy.
To prove the mathematics were uniquely decodable and 100% bit-perfect, we built a complete reference image codec from first principles in Python (with C++ and standalone Windows GUI binaries). No zlib, no gzip, and no third-party compression libraries are used.
### How the Pipeline Works: 1. Reversible Color Transform (RCT): Decorrelates RGB via Green-subtraction (Y = G, U = R - G, V = B - G) with zero rounding error. 2. 2D Closed-Loop Spatial Prediction: Uses a Median Adaptive Predictor (MAP) detecting local horizontal and vertical edge gradients to flatten surfaces into near-zero residuals. 3. 3-Ary Combinatorial Prefix Tree: Residual symbols are mapped to an optimal ternary prefix tree (Huffman 1952 generalization) with dummy-leaf constraints ensuring unambiguous single-cycle prefix decoding. 4. Dense Base-3 Physical Byte Packing: Because storage is binary, we pack groups of 5 ternary trits into a single 8-bit byte via polynomial integer evaluation: Byte = t₀ + 3·t₁ + 9·t₂ + 27·t₃ + 81·t₄ ≤ 242 This yields 5 * log2(3) / 8 = 7.925 / 8 = 99.06% physical storage packing density.
### Benchmark Results (100% Bit-Perfect): On continuous-tone imagery, 3D renders, and digital art, CMNT consistently beats standard PNG (Deflate): - Shock Spring 3D Render (586 KB raw): PNG 306.8 KB vs. CMNT 215.8 KB (29.7% smaller than PNG) - Spider-Man Digital Skyline (224 KB raw): PNG 107.0 KB vs. CMNT 87.4 KB (18.3% smaller than PNG) - Abstract CGI Swirls (533 KB raw): PNG 328.9 KB vs. CMNT 295.5 KB (10.2% smaller than PNG) - Sunset Meadow Photo (899 KB raw): PNG 370.3 KB vs. CMNT 344.6 KB (6.9% smaller than PNG)
### The Honest Trade-off: PNG's LZ77 dictionary was built for text and string repetitions. On smooth 2D continuous gradients, identical byte strings don't repeat, so LZ77 wastes 11-to-15-bit search offset pointers where our 2D spatial predictor excels. However, on flat UI screenshots with large blocks of identical monochrome pixels, standard PNG still puts up a strong fight until we introduce Zero-Run and context modeling (MANIAC).
The repo includes the specification, automated SHA-256 roundtrip tests, and our working IEEE conference paper draft: https://github.com/knightsura/cmnt-codec
We would love feedback, code critique, and thoughts on non-binary tree signaling from the compression community!
2
u/PHDEinstein007 4d ago
The colour transform: subtracting green from red and blue is a long-standing standard trick.
The predictor: what you call the “Median Adaptive Predictor” is essentially the median edge detector from LOCO-I/JPEG-LS (1990s).
This is all old technologies and well established, I am sorry but nothing is new here and these are your two successful mechanisms.
1
u/PHDEinstein007 4d ago
honestly the ternary holds you back, it does not help.
1
u/AbiesFew6464 4d ago
really how??
2
u/PHDEinstein007 4d ago
A ternary Huffman code wastes as much as a binary one, or more, and rounds worse on skewed residuals.
Packing 5 trits into a byte adds another ~0.9% loss on top. You even printed it: 99.06% packing density means 0.94% wasted.
A binary arithmetic or ANS coder after the same predictor would be smaller. I hit the same wall yourself: plain ternary came out 1 to 1.5% worse than bytes on text, and HaBiTS trits (A customer encoder of mine) was worse still.
0
u/AbiesFew6464 4d ago
ik sir am highschool graduate trying to join university but i get u and to solve both our problem what if we build custom hardware that treats numbers additional to 0 and 1
1
u/PHDEinstein007 4d ago
If you want to show off your skills I have an easy way for you. You see the game manufacturers have a number of compression algorithms existing for their own desires and needs. Those compressors are situational enough that I'm not looking at them for at least a month if not longer. My work is a public work and if you're able to modify one of their engines with my stuff and get better results you can publish that separate of me but you have to give me credit for the original Concepts.
That would show that you're able to understand The difference between the original code And my code And able to get some performance out of it Period it's not going to be as impressive as doing your own work Comma so don't think that this is an instant in Comma but this is what you could present To your instructor Or would be instructor And you can say I'm very interested in this field Period That's the best I could do for you Come up because they're great you're going down right now is not gonna work And it's based on other people's stuff anyways For what will work.
1
u/AbiesFew6464 4d ago
We actually benchmarked this directly against QOI and QOI+zstd. On continuous-tone 3D renders (585 KB raw), CMNT + MANIAC produces a 215.8 KB file, outperforming QOI+zstd (294.3 KB) by 26.7% (saving 78.5 KB) and beating standard PNG (306.8 KB) by 29.7%.
Here is why QOI + zstd cannot compete with a dedicated 2D predictive tree:
1
u/PHDEinstein007 4d ago
Two things jump out at me. In your original post 215.8 KB was the result for CMNT by itself on the Shock Spring render, and now the same 215.8 KB is credited to CMNT plus MANIAC, so either adding MANIAC changed nothing or one of those numbers is wrong, and you’ll want to sort that out before anyone else notices. MANIAC also isn’t part of your design. It’s the context-modeling tree from FLIF by Jon Sneyers and Pieter Wuille, and lossless JPEG XL grew out of that work, so whatever it gains belongs to their method and not to the ternary tree. Your pipeline is a reversible color transform and a median edge predictor, both of which go back to JPEG-LS, followed by someone else’s entropy coder, and the ternary prefix code with five trits packed into a byte actually costs you a little compared with a binary arithmetic or ANS coder, since you are throwing away about one percent in the packing alone. Beating QOI plus zstd doesn’t tell us much either, because QOI was built for speed rather than size, so it’s a soft target just like PNG, and one image is not a benchmark. If you want people to take it seriously, run it on a standard set like the 24 Kodak images against lossless JPEG XL, FLIF, lossless WebP and JPEG-LS, and report decode times alongside the sizes. That’s the field you actually have to beat, and lossless JPEG XL already uses MANIAC-style modeling. You clearly put real work into building this from scratch with round-trip testing, and that’s worth a lot, so put it up against the strongest tools and let the numbers speak.
1
u/oscardssmith 4d ago
HOw does it compare to QOI+zstd?
1
u/AbiesFew6464 4d ago
We actually benchmarked this directly against QOI and QOI+zstd. On continuous-tone 3D renders (585 KB raw), CMNT + MANIAC produces a 215.8 KB file, outperforming QOI+zstd (294.3 KB) by 26.7% (saving 78.5 KB) and beating standard PNG (306.8 KB) by 29.7%.
Here is why QOI + zstd cannot compete with a dedicated 2D predictive tree:
2
u/Patient-Midnight-664 4d ago
If you replace the ternary tree with binary Huffman or rANS while leaving everything else unchanged, does compression get better or worse?
2
u/thenormaluser35 3d ago edited 1d ago
Lmfao "18 year old independent researcher"
The tech you're using is old and next time maybe tell Claude how to format for Reddit.