Nonlinear Prediction of Multidimensional Signals via Deep Regression with Applications to Image Coding

Xi Zhang, Xiaolin Wu

TL;DR

This paper introduces PredNet, a two-stage deep convolutional neural network (DCNN) framework designed to move beyond traditional linear models for predicting image pixels. By leveraging nonlinear regression and a multi-norm training strategy, the authors achieve state-of-the-art results in lossless image coding, significantly reducing prediction entropy while running orders of magnitude faster than previous high-end adaptive predictors.

What Problem Does This Paper Address?

In image processing, "sequential prediction" involves guessing the value of a pixel based on the pixels that came before it (the causal context). Historically, most predictors have been linear. While linear models are mathematically convenient and computationally cheap, they are fundamentally limited: they assume signals are stationary and Gaussian, which real-world images—with their complex textures and sharp edges—are not.

Previous attempts to improve this, such as the MDL-PAR model, used adaptive piecewise autoregression. While MDL-PAR achieved high accuracy, it was a computational nightmare, requiring roughly 8 hours to process a single 512×512 image because it had to solve a complex optimization problem for every single pixel. The authors of this paper aim to break the "linearity limit" using deep learning to capture complex, nonlinear relationships while keeping the processing time practical.

Methods

The authors propose a two-stage framework:

  1. Stage 1: The PredNets. They designed a DCNN called PredNet consisting of a convolutional module (16 residual units) followed by a regression module. To ensure the model is robust, they trained three separate versions of PredNet, each minimizing a different error norm:
  2. $\ell_1$-norm: Good for minimizing entropy (the ultimate goal for compression).
  3. $\ell_2$-norm: The standard least-squares approach.
  4. $\ell_\infty$-norm: Focuses on minimizing the worst-case prediction error.
  5. Stage 2: Refinement Regression. A second-stage network (PredNet-R) takes the predictions from the three Stage 1 models as input. It "fuses" these different perspectives to generate a final, more precise prediction.

Key Technical Detail: The authors use sparse regularization ($\ell_1$-norm on the weights). This allows the network to automatically "discover" which pixels in the surrounding neighborhood are actually relevant for prediction and ignore the "noise" or irrelevant pixels, effectively solving the "causal context" selection problem that plagues linear models.

Datasets

  • Training: The models were trained on millions of patches extracted from three high-resolution public datasets: DIV2K, CLIC, and Flickr2K.
  • Evaluation: Performance was tested on the well-known Kodak lossless image dataset, a standard benchmark in the image compression community.

Key Insights and Ideas

  • Non-linearity is Essential: The paper demonstrates that DCNNs can learn the anisotropic (direction-dependent) dependencies in natural images far better than any fixed or piecewise linear model.
  • Diversity in Loss Functions: By training on $\ell_1, \ell_2,$ and $\ell_\infty$ norms, the authors created a "committee" of predictors. The refinement stage learns how to weigh these different error-minimization strategies depending on the local image content.
  • Learning the Context: Instead of manually defining a "K-closest pixels" template, the DCNN uses its receptive field and sparsity constraints to learn the optimal spatial support for each prediction.
  • Inference vs. Optimization: The biggest "aha" moment is the shift in complexity. While the DCNN is expensive to train (offline), its inference (online) is just a series of matrix multiplications. This shifts the heavy lifting from the user's computer to the training server.

Key Results

  • Better Compression: PredNet-R achieved a self-entropy of 4.25 bits/pixel, outperforming the previous state-of-the-art (MDL-PAR at 4.40) and standard linear predictors (GAP at 4.69).
  • Massive Speedup: PredNet-R performs sequential prediction of a 512×512 image in 30 seconds, compared to the 8 hours required by MDL-PAR. This is a speedup of nearly 1,000x.
  • Cleaner Residuals: Qualitative results (visualized in the paper) show that the "residual images" (the difference between the actual image and the prediction) for PredNet-R contain almost no visible structures, meaning the predictor successfully captured almost all the meaningful information in the original image.

Limitations and Future Work

  • Speed: While 30 seconds is a massive improvement over 8 hours, it is still relatively slow for real-time lossless image coding applications. Further optimization or hardware acceleration would be needed for consumer-grade software.
  • Dimensionality: The current study focuses on 2D images. The authors suggest the framework can be extended to 1D (audio) or 3D (video/volumetric) signals, but those applications were not explored in this specific paper.
  • Lossless Focus: The research is specifically tailored for lossless coding; adapting this high-precision regression for lossy compression (where some error is acceptable) remains a potential future direction.

Summary updated

Abstract

Deep convolutional neural networks (DCNN) have enjoyed great successes in many signal processing applications because they can learn complex, non-linear causal relationships from input to output. In this light, DCNNs are well suited for the task of sequential prediction of multidimensional signals, such as images, and have the potential of improving the performance of traditional linear predictors. In this research we investigate how far DCNNs can push the envelop in terms of prediction precision. We propose, in a case study, a two-stage deep regression DCNN framework for nonlinear prediction of two-dimensional image signals. In the first-stage regression, the proposed deep prediction network (PredNet) takes the causal context as input and emits a prediction of the present pixel. Three PredNets are trained with the regression objectives of minimizing l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> and l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> norms of prediction residuals, respectively. The second-stage regression combines the outputs of the three PredNets to generate an even more precise and robust prediction. The proposed deep regression model is applied to lossless predictive image coding, and it outperforms the state-of-the-art linear predictors by appreciable margin.
BibTeX
@inproceedings{zhang2019nonlinear,
  author = {Xi Zhang and Xiaolin Wu},
  title = {{Nonlinear Prediction of Multidimensional Signals via Deep Regression with Applications to Image Coding}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=g3h6AUgzpe},
}
Figure