Back

Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding

Marco BevilacquaAline RoumyChristine GuillemotMarie-line Alberi Morel

article2012BMVC2,940 citations

Proposes a low-complexity single-pass super-resolution method combining centered luminance features with nonnegative neighbor embedding to achieve reconstruction quality on par with complex multi-pass approaches at significantly reduced runtime.

Listen

Single-image super-resolution aims to produce a high-resolution image from one low-resolution input, a task that supports clearer visuals in imaging applications where only limited data is available. The paper develops a fast, one-pass method that avoids the repeated processing steps required by some earlier techniques.

The work evaluates an example-based approach that learns mappings between low- and high-resolution image patches stored in an external dictionary. For each low-resolution input patch, the algorithm locates nearest neighbors in the dictionary, computes combination weights, and applies those same weights to the matching high-resolution patches. It tests centered luminance values as patch features and replaces a standard constrained least-squares weight calculation with a nonnegative least-squares version to reduce overfitting. Experiments compare the resulting method against prior one-pass and multi-pass algorithms on standard test images at magnification factors of 2, 3, and 4, measuring both reconstruction quality via peak signal-to-noise ratio and running time.

The nonnegative weight formulation combined with centered luminance features produced steadily rising quality scores as more neighbors were considered, whereas earlier weight calculations showed sharp drops. The new algorithm delivered higher peak signal-to-noise ratio values than the original neighbor-embedding method and a kernel ridge regression approach, while matching the quality of a slower multi-pass technique. Running times were substantially lower, often by factors of five to twenty, because the method performs only a single pass and can use a prebuilt dictionary. External training proved essential for maintaining adequate dictionary size at larger scale factors.

These outcomes indicate that high-quality super-resolution is achievable without iterative refinement or expensive feature computations, lowering barriers to practical deployment where processing speed and memory matter. The gains in efficiency come with no apparent loss in output fidelity on the tested cases.

Further gains may come from testing alternative neighbor-search metrics. Results rest on a small set of images and fixed dictionary construction choices; broader validation across varied content and larger dictionaries would strengthen confidence before widespread use.

Bell LaboratoriesINRIAefficient algorithmlow resolutionlow-complexitySingle-Image Super-ResolutionNonnegative Neighbor EmbeddingLow-Complexity
Bevilacqua et al (2012).pdf
  • Paper: Image Super-Resolution Using Deep Convolutional Networks, Chao Dong et al. (2014). This paper directly extends the source's pursuit of single-image super-resolution by replacing the traditional patch dictionary and nonnegative embedding pipeline with a fully optimized deep convolutional network.
  • Paper: Learning a Deep Convolutional Network for Image Super-Resolution, Chao Dong et al. (2014). Building upon the example-based and sparse-coding foundations discussed in the source, this work demonstrates how to reformulate the entire super-resolution pipeline into an end-to-end convolutional architecture.
Cover for Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding

Abstract

Single-image super-resolution (SR) is the problem of generating a single high resolution (HR) image, given one low resolution (LR) image as input. In this paper we propose a low-complexity and yet efficient algorithm that reconstruct the HR image in one pass (instead, e.g. of 7 passes for a magnification factor of 4 in [3]). The proposed algorithm falls into the family of example-based SR. Taking inspiration from machine learning, it aims at learning the mapping from the LR image(s) to the HR image by using a dictionary: the learning process is performed locally, by trying to infer the HR details through the use of small “examples”. For general SR purposes the examples used are patches (sub-windows of image); the dictionary is formed by pairs of LR and HR patches.

Topics

efficient algorithmlow resolutionlow-complexitymachine learningreference imagedigital imageimage resolution

Keywords

Single-Image Super-ResolutionNonnegative Neighbor EmbeddingLow-ComplexityCentered LuminanceNNLSExternal DictionaryPatch ReconstructionK Nearest Neighbor SearchFeature SpacePSNR

Knowls

  1. Knowl 1 — Non-negative Neighbor Embedding Algorithm for Single-Image Super-Resolution

    algorithm

    The non-negative neighbor embedding (NNLS-NE) algorithm reconstructs a high-resolution (HR) image from a single low-resolution (LR) image in a single pass using an offline-trained external dictionary of corresponding LR and HR patch pairs.

    Input: Low-resolution input image ILR\mathbf{I}_{LR}, external dictionary of patch pairs (Xd,Yd)(\mathbf{X}_d, \mathbf{Y}_d) where Xd={xjd}j=1Nd\mathbf{X}_d = \{\mathbf{x}_j^d\}_{j=1}^{N_d} and Yd={yjd}j=1Nd\mathbf{Y}_d = \{\mathbf{y}_j^d\}_{j=1}^{N_d}, number of neighbors KK
    Output: High-resolution reconstructed image IHR\mathbf{I}_{HR}
    Divide ILR\mathbf{I}_{LR} into overlapping patches {Pi}i=1Nt\{\mathbf{P}_i\}_{i=1}^{N_t}
    for each patch Pi\mathbf{P}_i in ILR\mathbf{I}_{LR} do
        Extract LR feature vector xti\mathbf{x}_t^i by computing centered pixel luminance values (subtracting the patch mean luminance)
        Find the KK nearest neighbors of xti\mathbf{x}_t^i in Xd\mathbf{X}_d using Euclidean distance, forming neighbor matrix Xdi=[xd,1i,…,xd,Ki]\mathbf{X}_d^i = [\mathbf{x}_{d,1}^i, \dots, \mathbf{x}_{d,K}^i]
        Compute non-negative reconstruction weights by solving:
            wi=arg⁡min⁡w≥0∥xti−Xdiw∥22\mathbf{w}^i = \arg\min_{\mathbf{w} \ge 0} \|\mathbf{x}_t^i - \mathbf{X}_d^i \mathbf{w}\|_2^2
        Retrieve the KK corresponding HR dictionary patches Ydi=[yd,1i,…,yd,Ki]\mathbf{Y}_d^i = [\mathbf{y}_{d,1}^i, \dots, \mathbf{y}_{d,K}^i]
        Reconstruct the HR feature patch: yti=Ydiwi\mathbf{y}_t^i = \mathbf{Y}_d^i \mathbf{w}^i
        Add back the patch mean luminance to obtain reconstructed patch Qi\mathbf{Q}_i
    end for
    Merge overlapping HR patches {Qi}\{\mathbf{Q}_i\} by averaging overlapping pixel values to form IHR\mathbf{I}_{HR}
    return IHR\mathbf{I}_{HR}

  2. Knowl 2 — Non-negative Least Squares Weight Formulation for Neighbor Embedding

    equation

    In Neighbor Embedding (NE) super-resolution, each input low-resolution (LR) patch feature vector xti∈RD\mathbf{x}_t^i \in \mathbb{R}^{D} is approximated as a linear combination of its KK nearest dictionary neighbors Xdi=[xd,1i,…,xd,Ki]∈RD×K\mathbf{X}_d^i = [\mathbf{x}_{d,1}^i, \dots, \mathbf{x}_{d,K}^i] \in \mathbb{R}^{D \times K}. The reconstruction weight vector wi∈RK\mathbf{w}^i \in \mathbb{R}^K is obtained by solving the non-negative least squares (NNLS) optimization problem:

    wi=arg⁡min⁡w∈RK∥xti−Xdiw∥22s.t.w≥0\mathbf{w}^i = \arg\min_{\mathbf{w} \in \mathbb{R}^K} \|\mathbf{x}_t^i - \mathbf{X}_d^i \mathbf{w}\|_2^2 \quad \text{s.t.} \quad \mathbf{w} \ge 0

    where w≥0\mathbf{w} \ge 0 enforces non-negativity component-wise (wk≥0w_k \ge 0 for all k∈{1,…,K}k \in \{1, \dots, K\}).

    This formulation relaxes the sum-to-one equality constraint used in standard NE (1Tw=1\mathbf{1}^T \mathbf{w} = 1) while preventing negative coefficients, eliminating overfitting to the LR patch space.

  3. Knowl 3 — Centered Luminance Patch Representation for Low-Complexity Super-Resolution

    model/method

    Image patches are represented using centered luminance values, defined as the raw luminance pixel values of the patch minus the patch's mean luminance value.

    This representation provides two primary benefits:

    1. Low computational complexity: Only one scalar value per pixel is computed and stored, avoiding the costly calculation of multi-directional gradient features.
    2. Space consistency: The feature representation is identical in structure and dimension between the low-resolution and high-resolution patch spaces, allowing direct weight transfer from LR neighbor combinations to HR reconstructions.

  4. Knowl 4 — Overfitting in Sum-to-One Constrained Least Squares vs Monotonic Robustness of Non-Negative LS

    empirical result

    When solving neighbor embedding weights with a sum-to-one least squares constraint (SUM1-LS: 1Tw=1\mathbf{1}^T \mathbf{w} = 1), reconstruction quality (measured by PSNR) suffers a sharp drop as the neighborhood size KK increases. This occurs because unconstrained or sum-to-one LS allows large opposing positive and negative weights that overfit the LR patch data, resulting in poor high-resolution patch generation.

    Under non-negative least squares (NNLS: w≥0\mathbf{w} \ge 0), this degradation is resolved: the reconstruction PSNR increases monotonically with KK and stabilizes at higher values. Furthermore, when combined with NNLS, centered luminance patch features consistently outperform gradient-based features across varying neighbor counts KK.

  5. Knowl 5 — PSNR and Runtime Performance Across Magnification Factors

    data/table

    The single-pass Non-negative Neighbor Embedding (NNLS-NE) algorithm was evaluated on test images (bird, head, woman) across magnification scale factors of 2, 3, and 4 against the single-pass NE method of Chang et al. (2004) and the multi-pass internal self-similarity method of Glasner et al. (2009).

    Image Scale Our algorithm Chang et al. Glasner et al.
    PSNR (dB) Time (s) PSNR (dB) Time (s) PSNR (dB) Time (s)
    bird 2 34.69 18 32.94 110 34.42 406
    head 2 32.88 18 32.34 145 32.68 367
    woman 2 30.91 15 29.43 114 30.61 410
    bird 3 31.37 9 29.71 47 32.16 281
    head 3 31.46 12 30.82 68 31.69 370
    woman 3 27.98 12 26.45 37 28.79 248
    bird 4 28.99 6 27.37 21 30.07 475
    head 4 30.26 6 29.57 26 30.86 379
    woman 4 25.66 5 24.25 17 26.79 401

    At scale factor 2, the proposed algorithm achieves the highest PSNR across all test images while reducing execution time by a factor of 6 to 8 relative to Chang et al. and 20 to 27 relative to Glasner et al. At scales 3 and 4, it substantially outperforms the single-pass baseline of Chang et al. in PSNR (by up to 1.66 dB) and attains reconstruction quality comparable to the multi-pass Glasner et al. approach while running 20 to 80 times faster (5–12 seconds compared to 248–475 seconds).

  6. Knowl 6 — External Dictionary Training for Single-Step Magnification

    model/method

    The single-pass super-resolution framework relies on an externally trained dictionary rather than an internal "self-pyramid" derived from the input image itself.

    Internal dictionaries derived from a single image suffer from limited patch diversity and sample sparsity when attempting single-step magnification at large scale factors (e.g., 4×4\times), which previously necessitated multi-pass iterative scaling (e.g., 7 passes). Using an external dictionary allows offline compilation of large-scale, rich LR-HR patch correspondences, enabling direct single-step upscaling at arbitrary magnification factors with low online computational time.

Coverage note — No substantial contributed material was omitted from the paper.

References

  1. 1.Tak-Ming Chan, Junping Zhang, Jian Pu, and Hua Huang. Neighbor embedding based super-resolution algorithm through edge detection and feature selection. Pattern Recognition Letters, 4 2009.
  2. 2.Hong Chang, Dit-Yan Yeung, and Yimin Xiong. Super-Resolution Through Neighbor Embedding. In 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, 2004.
  3. 3.Daniel Glasner, Shai Bagon, and Michal Irani. Super-Resolution from a Single Image. In 2009 IEEE 12th International Conference on Computer Vision (ICCV), 10 2009.
  4. 4.Yi Tang, Pingkun Yan, Yuan Yuan, and Xuelong Li. Single-image super-resolution via local learning. International Journal of Machine Learning and Cybernetics, 2011.

Citation

MLA
Bevilacqua, M., et al. “Low-Complexity Single-Image Super-Resolution Based on Nonnegative Neighbor Embedding”. Procedings of the British Machine Vision Conference 2012, 2012, pp. 135.1–.10, https://doi.org/10.5244/C.26.135.
APA
Bevilacqua, M., Roumy, A., Guillemot, C., & Morel, M.-. line A. (2012). Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding. Procedings of the British Machine Vision Conference 2012, 135.1–135.10. https://doi.org/10.5244/C.26.135
Chicago
Bevilacqua, M., A. Roumy, C. Guillemot, and M.-. line A. Morel. 2012. “Low-Complexity Single-Image Super-Resolution Based on Nonnegative Neighbor Embedding”. Procedings of the British Machine Vision Conference 2012, 135.1–.10. https://doi.org/10.5244/C.26.135.
Harvard
Bevilacqua, M. et al. (2012) “Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding”, Procedings of the British Machine Vision Conference 2012. British Machine Vision Association, pp. 135.1–135.10. Available at: https://doi.org/10.5244/C.26.135.
Vancouver
1. Bevilacqua M, Roumy A, Guillemot C, Morel M-line A (2012) Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding. In: Procedings of the British Machine Vision Conference 2012. British Machine Vision Association, pp 135.1–135.10

BibTeX

@inproceedings{Bevilacqua_2012, series={BMVC 2012}, title={Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding}, url={http://dx.doi.org/10.5244/C.26.135}, DOI={10.5244/c.26.135}, booktitle={Procedings of the British Machine Vision Conference 2012}, publisher={British Machine Vision Association}, author={Bevilacqua, Marco and Roumy, Aline and Guillemot, Christine and Morel, Marie-line Alberi}, year={2012}, pages={135.1–135.10}, collection={BMVC 2012} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF