  In many professional fields, such as medicine, remote sensing and sciences,
users often demand image compression methods to be mathematically lossless. But
lossless image coding has a rather low compression ratio (around 2:1 for
natural images). The only known technique to achieve significant compression
while meeting the stringent fidelity requirements is the methodology of
$\ell_\infty$-constrained coding that was developed and standardized in
nineties. We make a major progress in $\ell_\infty$-constrained image coding
after two decades, by developing a novel CNN-based soft
$\ell_\infty$-constrained decoding method. The new method repairs compression
defects by using a restoration CNN called the $\ell_\infty\mbox{-SDNet}$ to map
a conventionally decoded image to the latent image. A unique strength of the
$\ell_\infty\mbox{-SDNet}$ is its ability to enforce a tight error bound on a
per pixel basis. As such, no small distinctive structures of the original image
can be dropped or distorted, even if they are statistical outliers that are
otherwise sacrificed by mainstream CNN restoration methods. More importantly,
this research ushers in a new image compression system of
$\ell_\infty$-constrained encoding and deep soft decoding
($\ell_\infty\mbox{-ED}^2$). The $\ell_\infty \mbox{-ED}^2$ approach beats the
best of existing lossy image compression methods (e.g., BPG, WebP, etc.) not
only in $\ell_\infty$ but also in $\ell_2$ error metric and perceptual quality,
for bit rates near the threshold of perceptually transparent reconstruction.
Operationally, the new compression system is practical, with a low-complexity
real-time encoder and a cascade decoder consisting of a fast initial decoder
and an optional CNN soft decoder.
