Source-linked AI summary
Nearest Neighbor Value Interpolation
Olivier Rukundo, Hanqiang Cao
TL;DR
Image interpolation must fill empty locations when enlarging images, while conventional approaches can involve lowpass filtering and nearest-neighbor jaggedness. The paper presents NNV, which selects among four surrounding pixels using proximity to a bilinear-generated value. Tests compare NNV with nearest, bilinear, and bicubic interpolation across image quality, execution time, and PSNR, with reported differences depending on interpolation ratio and visual quality.
Problem
Image interpolation requires estimating values for empty locations, but conventional value-creation operations can involve lowpass filtering, while nearest neighbor produces jagged enlarged pixels.
Method
NNV selects one of four surrounding pixels whose value is nearly equal to the value generated by conventional bilinear interpolation.
Results
The proposed NNV algorithm was evaluated against nearest, bilinear, and bicubic interpolation for image detail quality, execution time, and PSNR at interpolation ratios of 4 and 2.
Takeaways & Limitations
NNV provides an alternative nearest-neighbor interpolation scheme whose reported visual quality, MET, and PSNR vary with the selected interpolation ratio.
Abstract
from arXiv · showhide
This paper presents the nearest neighbor value (NNV) algorithm for high resolution (H.R.) image interpolation. The difference between the proposed algorithm and conventional nearest neighbor algorithm is that the concept applied, to estimate the missing pixel value, is guided by the nearest value rather than the distance. In other words, the proposed concept selects one pixel, among four directly surrounding the empty location, whose value is almost equal to the value generated by the conventional bilinear interpolation algorithm. The proposed method demonstrated higher performances in terms of H.R. when compared to the conventional interpolation algorithms mentioned.
I. INTRODUCTION
Image interpolation enlarges images by increasing their pixel count, but conventional approaches can reduce resolution through lowpass filtering. The paper proposes choosing among four neighboring pixels using a bilinear-generated value as guidance.
- Image interpolation enlarges a small image by increasing the number of pixels comprising it.
- Traditional nearest, bilinear, and bicubic methods differ in image resolution, speed, and assumptions about spatial variability.
- Nearest neighbor interpolation replicates the shortest-distance pixel instead of creating a new value, producing larger pixels and heavy jagged edges.
- The proposed scheme uses the value generated by conventional bilinear interpolation to select the most appropriate one of four neighboring pixels.
II. BACKGROUND
Image interpolation constructs a scaled image from a source image by filling newly created empty locations with estimated pixel values. Different estimation concepts produce different results, with nearest neighbor prioritizing speed and bilinear interpolation producing smoother images.
- Interpolation constructs a new scaled image from a source image by filling empty spaces with appropriate pixel values.
- The selected interpolation ratio determines the size of the constructed image.
- Nearest neighbor fills empty spaces with the value of the nearest neighboring pixel and is useful when speed is the main concern.
- Bilinear interpolation performs linear interpolation in one direction and then again in the other, resulting in smoother images.
III. PROPOSED METHOD
The proposed method examines the four pixels surrounding an empty location and seeks a neighbor whose value is nearly equal to the bilinear interpolated value.
- The method represents the four surrounding neighbors as A, K, P, and G, with E denoting the empty location.
- The selection aims to identify one neighbor whose value is nearly equal to the value yielded by the bilinear interpolator.
B. Absolute differences mode calculation
The method compares absolute differences between four neighbor values and the bilinear value, using mode-based rules before selecting a neighbor or proceeding to a fallback case.
- B. Absolute differences mode calculation: The algorithm calculates the mode from the set of absolute differences J=[V1,V2,V3,V4].
- B. Absolute differences mode calculation: When the mode is also the minimum difference, the algorithm selects the first value from J and assigns its difference from the bilinear value to the empty location.
- B. Absolute differences mode calculation: For values V1=0.2, V2=0.8, V3=0.8, and V4=0.8, the mode 0.8 is not the minimum difference, so the direct mode rule cannot be applied.
- B. Absolute differences mode calculation: If the mode is not the minimum, the method finds values less than or equal to the mode, checks for a mode among the corresponding neighbors, and otherwise performs bilinear interpolation.
- B. Absolute differences mode calculation: The method's implementation follows a defined sequence of processing steps.
A. Neighbors mode calculation
The method compares neighboring values with the bilinear value to identify the neighbor suitable for the empty location.
- A. Neighbors mode calculation: The minimum difference from the bilinear value identifies the most appropriate neighboring pixel.The corresponding neighbor is then found and its value is assigned to the empty location.
- A. Neighbors mode calculation: The selected neighbor is determined after comparing candidate values against the bilinear interpolation result.
- A. Neighbors mode calculation: The chosen neighboring value is assigned directly to the empty location.
C. When there is no ‘absolute differences’ mode
When absolute differences have no mode, the procedure finds the minimum value, resolves ties by indexed selection, and assigns the corresponding neighbor after comparison with the bilinear value.
- C. When there is no ‘absolute differences’ mode: When all elements differ or repeated values do not produce a mode, the procedure finds the minimum value in J.The method applies a minimum operation to continue the selection process.
- C. When there is no ‘absolute differences’ mode: The first minimum is selected using subscripted indexing when multiple values qualify.
- C. When there is no ‘absolute differences’ mode: The neighbor corresponding to the selected minimum is identified from the four absolute differences.
- C. When there is no ‘absolute differences’ mode: The resulting value is assigned to the empty location after the minimum difference from the bilinear value is determined.
G B V4
The proposed scheme takes four neighboring pixels as inputs and produces an interpolated destination value, while PSNR interpretation depends on image similarity.
- G B V4: When two images are identical, MSE equals 0 and PSNR is undefined.
- G B V4: Fig.2 represents four input data values as the neighbors surrounding the empty location.
- G B V4: The destination E denotes the final interpolated value assigned to the empty location.
- G B V4: The scheme aims to reduce image-texture underestimation or overestimation associated with lowpass filtering in linear interpolation.The passage identifies bilinear interpolation in particular as affected by these processes.
IV. EXPERIMENTS AND DISCUSSIONS
The experiments evaluate NNV against conventional interpolation algorithms on grayscale images using image-detail quality, execution time, and PSNR across two interpolation ratios.
- IV. EXPERIMENTS AND DISCUSSIONS: NNV was tested against nearest, bilinear, and bicubic interpolation algorithms.
- IV. EXPERIMENTS AND DISCUSSIONS: The evaluation measured image-detail quality, Matlab-lines Execution Time, and Peak Signal to Noise Ratio.
- IV. EXPERIMENTS AND DISCUSSIONS: The study used four full grayscale images and interpolation ratios n = 4 and n = 2.
- IV. EXPERIMENTS AND DISCUSSIONS: Interpolated images are presented in Figures 4–11, while corresponding MET and PSNR results are reported in Tables 1 and 2.
MSE
The paper compares interpolated grayscale images produced by nearest-neighbor, bilinear, bicubic, and NNV methods at ratios n=4 and n=2, using visual examples and PSNR/MET evaluation.
- MSE : The source set contains 128 x 128 grayscale Cameraman, Girl, House, and Peppers images for interpolation at ratios n=4 and n=2.The ratio n=4 produces 512 x 512 outputs, while n=2 produces 256 x 256 outputs in the illustrated examples.
- MSE : Figures 8–11 show the four images interpolated at n=2, using the same NN, bilinear, bicubic, and NNV ordering.The Cameraman and Peppers examples are explicitly identified as 256 x 256 outputs.
- MSE : The evaluation compares image-detail quality, Matlab-lines execution time, and PSNR against conventional nearest, bilinear, and bicubic interpolation.The experiments use four full grayscale images, with interpolated images shown for both ratios and MET and PSNR reported in tables.
- MSE : The reported visual examples illustrate sharper but jagged nearest-neighbor texture, soft blurred bilinear texture, and smoother bicubic texture under ratio n=4.The paper attributes the bilinear blur to the lowpass filtering process involved in that interpolation algorithm.