Hundred-Kilobyte Lookup Tables for Efficient Single-Image Super-Resolution

1 Introduction

Single image super-resolution (SISR) is a long-standing problem in computer vision that involves generating a highresolution (HR) image from a low-resolution (LR) image. The goal is to recover high-frequency details that are lost in a downsampled image. Classical non-deep-learning methods can be divided into two main categories: interpolation and sparse coding. Interpolation approaches [Keys, 1981; Kirkland and Kirkland, 2010], such as bicubic interpolation, are simple and computationally efficient. They involve upsampling the LR image using a fixed kernel, e.g., a bicubic filter. However, they often suffer from limited generalizability and produce blurry images. Sparse-coding approaches [Timofte et al., 2013; Timofte et al., 2015], on the other hand, can achieve better results than the former but are computationally expensive and require hand-crafted features.

Like many other problems in computer vision, deep learning has revolutionized SISR. The mapping between LR and HR images can be learned directly from data, often resulting in super-resolved images of much better quality than classical methods. However, deep neural networks (DNNs) require a large number of floating-point operations, resulting in a high power budget. Recently, researchers have explored new schemes that combine lookup tables (LUT) with deep-learning SISR [Jo and Kim, 2021; Li et al., 2022; Ma et al., 2022]. Specifically, this approach pre-computes all possible input-output pairs of a deep SR network and stores them into an LUT for retrieval, thus skipping expensive computation during inference. As a result, LUT-based methods achieve inference speeds comparable to interpolation methods [Jo and Kim, 2021], but produce results with a learningbased quality. Moreover, LUT-based approaches are agnostic to software and hardware platforms, making them much more versatile than DNNs which require dedicated software and hardware support. Nonetheless, recent LUT-based SR schemes [Li et al., 2022; Ma et al., 2022] mainly focus on improving performance by enlarging the receptive field (RF), while overlooking the memory constraints. This contradicts the trending edge AI that often runs on edge devices strained by limited resources, e.g., the popular Ultra96 FPGA board has < 1MB on-chip memory. In fact, existing LUT-based schemes generally require multi-megabyte LUTs where offchip storage is inevitable. In addition, existing LUT-based approaches may still require expensive interpolation and/or floating-point operations, resulting in higher peak memory and energy costs. This highlights the challenge as well as the need for significant LUT size reduction and better architecture design to address the storage and power issues, while upkeeping performance.

To this end, this work systematically explores the relationship between the number of input pixels, RF, and SR performance. Our study leads to the design of a family of models called Hundred-Kilobyte Look-up Tables (HKLUTs) which offer a compelling balance between memory and performance. To eliminate the time-consuming and energy-intensive interpolation, a two-branch architecture as in SPLUT [Ma et al., 2022] is employed. Yet instead of its symmetric branches [Ma et al., 2022], we exploit the idea of effective receptive field (ERF) [Luo et al., 2016] in different branches and reveal a larger RF is only required for the mostsignificant-bit (MSB) branch representing contextual semantic information, whereas a much smaller RF is sufficient for processing the least-significant-bit (LSB) branch.

This key insight leads to an innovative asymmetric parallel structure, which largely reduces the storage space by nearly half without sacrificing performance. Next, we extend our model to multistage by cascading LUTs to enlarge the RF. Our proposed architecture, in contrast to prior works, allows information exchange between two branches during stage transition, resulting in an uncompromising performance. Moreover, we are the first to utilize progressive upsampling on LUT-based approaches, which further reduces the LUT size by half while improving the final performance. Compared to other state-of-the-art (SOTA) LUTbased schemes, HKLUTs deliver competitive performance while being > 10⇥ smaller in size (cf. Fig. 1). The main contributions of this paper are threefold:

• We systematically study the relationship between RF, the number of input pixels, and performance in the SR task, leading to our design of extra lightweight LUTs.
• We investigate the ERFs of two branches and propose an asymmetric parallel structure to reduce storage by ⇡ 2⇥ without sacrificing performance.
• A novel multistage architecture is proposed which adopts a progressive upsampling strategy and enables the communication between the two branches during stage transition. This leads to an improved performance together with another 2⇥ reduction in size.

By seamlessly integrating the above techniques, HKLUTs constitute the smallest LUT-based SISR schemes in the literature offering a highly competitive performance.

2 RelatedWork

The quest for high-quality SR on edge devices has fueled the interest and research of effective and efficient SISR schemes in recent years, broadly categorized into classical, deep learning and LUT-based Approaches.

Classical Approaches. Basic linear interpolation methods [Keys, 1981; Kirkland and Kirkland, 2010], though simple and efficient, are limited in their abilities to adapt to the image content and often result in blurry images. Early example-based work [Timofte et al., 2013; Timofte et al., 2015] learned sparse dictionaries over pixels or patches to build a compact representation between LR and HR pairs. During inference, the HR output is obtained using the precomputed projection matrix with the input features. However, it remains time-consuming for sparse coding models to compute the sparse representations.

Deep Learning Approaches. Deep learning methods have shown promising results in reconstructing image details for accurate super-resolution. Many deep learning SR works have been developed to reduce computational burdens by carefully adjusting the network structures, including, ESPCN [Shi et al., 2016a], CARN [Ahn et al., 2018], RRDB [Wang et al., 2018] and IMDN [Hui et al., 2019]. LapSRN [Lai et al., 2017] and its extension MS-LapSRN [Lai et al., 2018] employ Laplacian Pyramid to generate multi-scale predictions and progressively reconstruct HR images in multiple steps. FMEN [Du et al., 2022] shined in the NTIRE 2022 challenge with its low memory cost and short runtime through the enhanced residual block and high-frequency attention module. Although some models can be executed in real-time on GPUs, it is impractical to deploy them on edge devices with constrained hardware resources.

LUT-based Approaches. While deep learning-based methods can produce impressive results, they often require heavy computations and large storage. To accelerate the inference of DNNs, dedicated software and hardware platforms such as CUDA and GPUs are required. This poses challenges for cost-sensitive and resource-restrictive edge devices such as smartphones and TVs. To address this, SRLUT [Jo and Kim, 2021] fuses DNN and LUT for SR applications by precomputing and caching input-output pairs of a pre-trained SR network into a LUT for retrieval at test time. This approach eliminates expensive computation during DNN inference and achieves similar speed but better SR results than classical approaches. Two independent works around the same time, namely, MuLUT and SPLUT [Li et al., 2022; Ma et al., 2022], propose to expand the RF covered by cascading LUTs. MuLUT proposes the use of multiple complementary LUTs together with the rotation ensemble to solve the intrinsic limitation of a small RF in SRLUT. However, MuLUT preserves the costly interpolation step of SRLUT. On the other hand, SPLUT [Ma et al., 2022] exploits a novel parallel framework where the quantization loss is compensated by using two parallel branches that separately handle the most significant 4 bits and least significant 4 bits. This eliminates the time-consuming interpolation step for a faster inference speed. SPLUT also suggests enlarging the RF through feature aggregation along the horizontal and vertical directions. In addition, the Reconstructed Convolution (RC) module proposed in [Liu et al., 2023] can be transformed into 1D LUTs to efficiently expand the RF, thus improving performance. However, while these methods enhance performance compared to SRLUT, they require more storage space (> 1MB), making them less suitable for edge devices.

3 Development of HKLUT

3.1 Reduced Number of Input Pixels

The storage size of a LUT can be calculated using the formula vn ⇥ r2 , where v, n, and r are the number of quantization levels, number of input pixels, and upscaling factor, respectively. The first term vn determines the number of entries, whereas the second term r2 refers to the length of the output vector of each LUT. It is obvious that reducing the number of input pixels n can result in an exponential reduction in storage space. Previous studies have primarily focused on expanding the RF by utilizing a fixed number of pixels (say, 4) to improve the final performance. SPLUT [Ma et al., 2022] uses feature aggregation to expand the RF, namely, the output feature maps generated from the previous LUT are divided into groups along the channel dimension and then padded horizontally or vertically. The padded feature maps are then added to generate a single-channel feature map, which serves as the input for subsequent LUTs. However, in order to generate multi-channel feature maps, the size of intermediate LUTs grows linearly with the number of output channels. This goes against our primary goal, which is to reduce storage space. Subsequently, we deliberately omit feature aggregation. On the other hand, SRLUT [Jo and Kim, 2021] and MuLUT [Li et al., 2022] employ rotation ensemble to increase the area being covered. The final prediction ˆ yi is computed as follows:

where xi is the LR input, LUTk is the kth LUT, Rj is the jth rotation operation, N is the number of kernels (or LUTs), and Mk is the number of rotation operations for the corresponding kernel. We remark that rotation ensemble, unlike feature aggregation, does not require extra storage.

HDNet 3⇥3

Table 1: Effect of the number of input pixels on PSNR, evaluated on Set5 dataset. "Net" is used to distinguish full-precision CNNs from quantized LUTs.

An important aspect that has been overlooked by previous works is that achieving the same RF is indeed feasible with fewer pixels. To fill in this gap, we design LLUT and HDLUT (named after their input-pixel shapes, cf. Fig. 2) to explore the relationship between the number of input pixels and the final PSNR subject to a prescribed RF size. Specifically, LLUT and HDLUT are designed to completely cover a 3⇥3 area without any overlapping pixels, except for the pivot pixel, using a rotation ensemble. Table 1 shows the PSNR improves with an increasing number of input pixels, which is consistent with the intuition that having more pixels gathers more information, at the cost of a higher storage, viz. a 4-pixel LUT requires megabytes of storage, whereas the performance of the 2-pixel LUT degrades obviously. To balance storage and performance, we devise HDBLUT, which consists of three 3-pixel kernels. Using rotation ensemble, it covers an entire 5 ⇥ 5 RF without any overlap, except for the pivot pixel (Fig. 3). In contrast to SRLUT and MuLUT, which have a 3⇥3 RF with 4 overlapping pixels and a 5⇥5 RF with 11 overlapping pixels, respectively, our designs, HDLUT and HDBLUT, aim to match the same RF with minimal input pixels. This achieves a near-optimal tradeoff between memory footprint and performance (a comparison of the RF of our designs vs others is in the Appendix). Using HDBLUT and HDLUT, along with the asymmetric parallel structure discussed in the sequel, we are able to outperform SRLUT with > 6⇥ less storage.

3.2 Asymmetric Parallel Structure

Previous studies have attempted to reduce the size of LUTs by limiting the number of quantization levels to 17 and using interpolation to recover the quantization loss [Jo and Kim, 2021; Li et al., 2022]. However, the interpolation stage is time-consuming and energy-intensive, hindering the practicality on edge devices. To address this, SPLUT [Ma et al., 2022] proposes a parallel branch structure that avoids the need for interpolation. The structure divides the 8-bit input image into its most and least significant bits, viz. MSB and LSB branches each with 4 bits (viz. 16 levels) of information. The final SR image is obtained by fusing the results of the two branches at the last stage. While this approach gives promising results, it overlooks an important fact, namely, the effective receptive fields (ERFs) of MSB and LSB branches are completely different as they represent different kinds of information. Therefore, using the same sets of LUTs for both MSB and LSB branches might not be an optimal choice.

We trained two identical SRNets, using a 5 ⇥ 5 kernel for both MSB and LSB branches. The results from the two branches are summed and gradients are computed using mean-squared error (MSE) loss. Fig. 4 shows the ERF, in terms of normalized gradients obtained from randomly selected 4 ⇥ 4 regions of the SR result with respect to inputs, using the baby image from the Set5 dataset (cf. Fig. 5) (more demonstrations can be found in the Appendix). Although both MSB and LSB are processed under the same theoretical RF (i.e., 5 ⇥ 5), the results show that the MSB branch, which captures the high-level contextual semantic information, has a larger ERF. On the other hand, a smaller ERF is sufficient for the LSB branch to describe fine details. This observation justifies an asymmetric parallel structure that exploits the differences between MSB and LSB to save storage space. By using a set of 3-pixel LUTs (i.e., HDBLUT) corresponding to CNNs with a 5 ⇥ 5 RF for the MSB branch, and a set of 2-pixel LUTs (i.e., HDLUT) corresponding to CNNs with a 3⇥3 RF for the LSB branch, we can nearly halve the storage space without compromising performance (cf. Table 2).

3.3 Multistage

LUT-based methods [Ma et al., 2022; Li et al., 2022] have demonstrated the efficacy of cascaded stages to enlarge the RF for better performance. SPLUT [Ma et al., 2022] splits the image into the MSB and LSB branches and deals with them separately with uniform quantization until the final addition, which prevents each branch from getting information from the other. MuLUT [Li et al., 2022] utilizes quantization and interpolation to build the connection between stages, which requires later fine-tuning to compensate for the loss of information caused by quantization.

Here, we propose a new multistage framework as illustrated in Fig. 5. In each stage, we split the 8-bit input image into MSB and LSB branches for different LUT blocks to extract features and upscale the resolution. The features from both branches are then combined to generate the complete enlarged image. The input and output of each stage are 8-bit images with different resolutions, unless the upscaling factor is 1. This module can be stacked to create cascaded stages, where the latter stage can access information from the two branches of the former stages. Residual connections can be conveniently implemented. The entire flow does not require interpolation, which significantly speeds up inference.

Furthermore, previous works utilize cascaded stages to increase the RF for a better performance, where upsampling is usually done in the last step. It is intuitively difficult to reproduce a high-resolution patch from a few pixels in one single step, especially when the upscaling factor is large. Besides, the storage space of LUT is proportional to the square of the upscaling factor r, we can save half the storage space by dividing the upscaling factor 4⇥ (viz. 4 ⇥ 4 = 16) into two factors 2⇥ (viz. 2 ⇥ 2 + 2 ⇥ 2 = 8). This simple yet previously unexplored progressive upsampling trick gives another booster to our proposed SISR scheme. Table 3 verifies the effectiveness of progressive upsampling in our LUT-based methods, along with further savings in storage.

4 Experiments

4.1 Implementation Details

Datasets and Metrics. We train the proposed HKLUT on the DIV2K dataset [Agustsson and Timofte, 2017], a popular dataset in the SR field. The DIV2K dataset provides 800 training images and 100 validation images with 2K resolution and the corresponding downsampled images. We use the widely adopted Peak Signal-to-Noise Ratio (PSNR) and structural similarity index (SSIM) [Wang et al., 2004] as evaluation metrics. Five well-known datasets: Set5 [Bevilacqua et al., 2012], Set14 [Zeyde et al., 2012], BSDS100 [Martin et al., 2001], Urban100 [Huang et al., 2015] and Manga109 [Matsui et al., 2017] are benchmarked. Following other LUT-based methods, we mainly focus on SR tasks with an upscaling factor of 4. We also report the runtime, theoretical energy cost, and peak memory of generating a 1280 ⇥ 720 HR image from a 640 ⇥ 360 LR image.

Experimental setting. Before converting into LUTs, the network is trained with 800 training images in DIV2K for 200k iterations with a batch size of 16 on Nvidia RTX 3090 GPUs. We utilize the Adam optimizer [Kingma and Ba, 2014] (β1 = 0▷9, β2 = 0▷999 and ✏ = 1e - 8) with the MSE loss to train the HKLUT. The initial learning rate is set to 5 ⇥ 10-4 , which decays to one-tenth after 100k and 150k iterations, respectively. We randomly crop LR images into 48 ⇥ 48 patches as input and enhance the dataset by random rotation and flipping. The runtime is measured on an Intel Core i5-10505 CPU with 16GB RAM, averaged over 10 runs. Baselines. Aligning with prior work, we evaluate HKLUT against several well-recognized SISR methods, such as interpolation-based methods (nearest neighbor [Bevilacqua et al., 2012], bilinear [Kirkland and Kirkland, 2010] and bicubic [Keys, 1981] interpolation), sparse-coding-based methods (ANR [Timofte et al., 2013] and A+ [Timofte et al., 2015]), DNN-based methods (CARN [Du et al., 2022] and RRDB [Wang et al., 2018]), and LUT-based methods (SRLUT [Jo and Kim, 2021], SPLUT [Ma et al., 2022], MuLUT [Li et al., 2022] and RCLUT [Liu et al., 2023]).

4.2 Quantitative Results

Asymmetric Parallel Structure. To demonstrate the effectiveness of our proposed asymmetric parallel structure, we utilize the 2-pixel HDLUT with 3 ⇥ 3 RF and 3-pixel HDBLUT with 5 ⇥ 5 RF to investigate the relationship between RF, LSB, and MSB for the 4⇥ SR. Table 2 shows HDB HDB 5⇥5/5⇥5

2⇥2⇥1 112.5KB 475.0ms 30.43/0.861 27.47/0.750 26.79/0.707 24.31/0.713 27.58/0.856

Table 3: Ablating various progressive upsampling strategies. Runtime is measured for outputting a 1280 ⇥ 720 image on a desktop CPU averaged across 10 runs. We refer to models in the lime and blue rows as HKLUT-S and HKLUT-L, respectively.

that using HDLUTs for both branches results in worse performance (29.39dB for Set5). A negligible increase (+0.01dB) in performance is achieved when we replace the LSB branch with the larger-RF HDBLUT, at a cost of over 12 times the growth in model size (200KB vs. 16KB). However, by simply swapping the two branches, i.e., using HDBLUT for MSB and HDLUT for LSB, we obtain a significant boost in performance (+0.58dB) with the same storage and computing. When using HDBLUT for both MSB and LSB branches, we only obtain a marginal increase in PSNR (+0.01dB), at a cost of nearly doubling the storage (384KB vs. 200KB). This validates our conjecture that a 2-pixel LUT is sufficient for the LSB because of the small ERF, while a 3-pixel LUT is necessary for the MSB to capture contextual information such as texture. In short, the proposed asymmetric parallel structure allows for the efficient allocation of resources and saves half of the storage space without sacrificing performance.

Multistage. Table 3 examines various upsampling strategies to demonstrate the effectiveness of progressive upsampling. Following the asymmetric parallel structure, HDBLUT and HDLUT are used for each stage's MSB and LSB branches, respectively. Comparing the 1st and 3rd rows, using an asymmetric parallel structure, 2-stage progressive upsampling (2⇥2) shows a clear advantage in terms of SR performance compared to 1-stage upsampling (4⇥) (30.35dB vs. 29.97dB on Set 5), while requiring only half the storage space (100KB vs. 200KB). The advantage of progressive upsampling becomes even clearer when compared to results on the 2nd row, which corresponds to the same 2-stage but with upsampling in a single step (1 ⇥ 4) (-0.36dB). Our results show that 2 ⇥ 1 ⇥ 2 upsampling achieves the best tradeoff by considering storage, runtime, and performance. We, therefore, refer to models listed on the 3rd and 5th rows as HKLUTS (highlighted in lime) and HKLUT-L (highlighted in blue), respectively.

Performance and Storage In Table 4, we compared our proposed HKLUT with well-recognized SISR approaches such as interpolation, sparse-coding, and CNNs, as well as the latest LUT-based methods. Our approach has a clear advantage in storage, which aligns with the objective of this paper. HKLUT-S, being the smallest parameterized model, only requires 100KB, which is 10⇥ less than the second smallest SRLUT (1.27MB) with a much better performance. Both HKLUT-S and HKLUT-L outperform all classical baselines, including A+, which is significantly larger than HKLUT-S (15.17MB vs. 100KB). Although CNN-based approaches exhibit good performance in terms of PSNR and SSIM, they often require larger storage. For instance, RRDB is 650⇥ larger than our HKLUT-S, making it challenging to deploy on edge devices. Compared to LUT-based approaches, our methods not only require less storage but also achieve comparable performance. HKLUT-L outperforms MuLUT-SDY on the Set5 dataset (30.41dB vs. 30.40dB) with 35⇥ less storage. Despite being 70⇥ smaller, HKLUT-S significantly outperforms SPLUT-M (30.35dB vs. 30.23dB).

Energy & Peak Memory. Following the setting in MuLUT [Li et al., 2022], Fig. 6 shows the theoretical energy costs and peak memory usages of FSRCNN (32.70dB) and several LUT-based methods (31.73dB⇠32.35dB) for generating a 1280 ⇥ 720 image through 2⇥ SR. We estimated the theoretical energy cost using the same protocol as AdderSR [Song et al., 2021], and computed the peak memory usage using memray 1 . For LUT-based approaches, we used their smallest variants. One of the major advantages of LUT-based methods is their ability to drastically reduce energy and memory consumption. Even FSRCNN, the simplest CNN for SISR, consumes 900⇥ and 7▷5⇥ more energy and memory compared to HKLUT. The feature map aggregation module of SPLUT not only instantiates larger LUTs but also requires floating-point operations, resulting in increased energy consumption and peak memory usage. Meanwhile, both SRLUT and MuLUT consume a significant amount of energy for the interpolation operation. In contrast, HKLUT gets rid of energy-intensive interpolation and solely relies on integer operations. Fig. 6 shows that HKLUT exhibits the lowest energy cost and peak memory usage amongst all competitors.

Runtime. Using the same settings as for calculating energy and peak memory, we compared the runtimes of FSRCNN and LUT-based approaches on both a desktop CPU and the Raspberry Pi 4 Model B. To ensure a fair comparison, we used the official Python code released by the authors, without relying on native mobile implementation or any speedup tricks. We recorded the average runtime of generating a 1280 ⇥ 720 image from a 640 ⇥ 360 image in Table 5. It is clear that the 4-simplex interpolation bottlenecks the inference speed of SRLUT and MuLUT at the final stage. SPLUT and our approaches, featuring parallel branches, exhibit shorter inference times on Raspberry Pi and CPU. Unsurprisingly, HKLUT achieves the fastest inference speed.

4.3 Qualitative Results

Fig. 7 presents a visual comparison between the bicubic interpolation baseline and different LUT-based approaches on images selected from five benchmark datasets. The results clearly demonstrate that LUT-based approaches improve sharpness compared to bicubic interpolation which generates blurry images. The 3rd row (Manga109) shows that the SRLUT approach exhibits severe rippling artifacts around the edges, which may be caused by its limited RF. HKLUT-S produces similar sharpness to MuLUT-SDY-X2 and SPLUT-L, despite being more than 40⇥ and 180⇥ smaller, respectively.

1 Measured with memray (https://github.com/bloomberg/ memray) on a desktop CPU.

5 Ablation Studies

5.1 Ablation on Kernel Shapes

To obtain the HDB kernel for our MSB branch, we conducted an ablation study on kernel shape. Instead of exhausting all possible combinations, we employed softmax during training with an annealing temperature to select the most important pixel per column. After training, we evaluated the binarized kernels. We performed 20 runs with different random seeds using a one-stage model, with the LSB branch fixed as the HD kernel. Each run consisted of 20k (10%) training iterations. Next, we selected the top 3 best-performing candidates with non-overlapping kernels and retrained them from scratch for 200k iterations. Fig. 8 shows the 3 best-performing for MSB branch, where HDB (i.e. (a)) ranks as the best.

5.2 Ablation on LUT Cascading

In previous work [Ma et al., 2022], a series-parallel structure was proposed to remove the need for interpolation. This structure divides an 8-bit image into MSB and LSB parts and processes them separately. The series structure involves cascading LUTs within each branch. Communication between branches only occurs at the end of the model to generate the final SR image by combining information. The output activations of each LUT in intermediate stages are clipped between [-8, 7] and quantized into 16 levels. However, we believe that this approach is counter-intuitive and suboptimal. On the other hand, our method allows communication between branches during stage transition. The output of each stage is clipped between [0, 255] represented in INT8, enabling meaningful results even in intermediate stages. Table 6 demonstrates the superior performance of our approach compared to the multistage structure in SPLUT [Ma et al., 2022] (30.35dB vs. 29.32dB for Set5), both using the 2⇥2 progressive upsampling technique.

6 Conclusion

This paper aims to develop minimalist LUTs for efficient LUT-based SISR. We propose a new class of models called HKLUTs employing kernels with fewer input pixels while retaining the RF, resulting in an exponential reduction in storage without compromising performance. In particular, HKLUT consists of an asymmetric parallel structure that employs big-little kernel patterns to adapt to the underlying characteristics of MSB and LSB branches. A progressive multistage architecture, without expensive interpolation between stages, is devised to reduce storage by half. By seamlessly fusing these innovations, HKLUT models set the first record to attain > 30dB on the Set 5 dataset at merely one-tenth of 1MB storage. Extensive experiments verify that HKLUT is a versatile alternative to previous large LUT-based approaches on resource-constrained devices.

Acknowledgments

This work was supported in part by the Theme-based Research Scheme (TRS) project T45-701/22-R of the Research Grants Council (RGC), Hong Kong Special Administrative Region (HKSAR), and in part by the HKU-TCL Joint Research Centre for Artificial Intelligence.

Contribution Statement

Binxiao Huang and Jason Li contributed equally to this paper.