CPU, SMP and GPU implementations of Nohalo level 1, a fast co-convex antialiasing image resampler

ABSTRACT

This article introduces Nohalo level 1 ("Nohalo"), the simplest member of a family of image resamplers which straighten diagonal interfaces without adding noticeable nonlinear artifacts. Nohalo is interpolatory, co-monotone, co-convex, antialiasing, local average preserving, continuous, and exact on linears.

Like many edge-enhancing methods, Nohalo has two main stages: first, nonlinear interpolation is used to create a double-density version of the original image; this double-density image is then resampled with bilinear interpolation. Nohalo is especially suited for GPU computing because the nonlinear slopes can be computed once and stored in a low bit-depth texture without rounding error, because the final bilinear stage can be performed in hardware, and because monotonicity allows full use of the texture's dynamic range. Demand-driven implementations for CPU's and SMPs are more complex, and require extra work to fix bottlenecks. Efficient implementations of the minmod function are key to performance.

Three implementations of Nohalo are presented and bench-marked: a CPU version in C for the graphics library GEGL, an SMP version in C++ for the graphics library VIPS and a GPU version in HLSL for DirectX. The GPU implementation is branch-free thanks to the discovery of a simple formula for the pixel values of the double density image. Branches are eliminated in the demand-driven C/C++ implementations by reflecting, if needed, Nohalo's 12-point stencil with pointer shifts. Overall, Nohalo is not much slower than standard bicubic resamplers.

Compared to twenty-three alternatives in tests involving the re-enlargement of images downsampled with nearest neighbour, Nohalo gets the best PSNRs.

REFERENCES

• 1: GEGL. http://gegl.org.
• 2: Scilab. http://www.scilab.org.
• 3: SIVP--Scilab Image and Video Processing toolbox. http://sivp.sourceforge.net.
• 4: VIPS. http://www.vips.ecs.soton.ac.uk.
• 5: N. Asuni. iNEDI -- tecnica adattativa per l'interpolazione di immagini. Master's thesis, Università degli Studi di Cagliari, 2007.
• 6: S. Battiato, G. Gallo, and F. Stanco. A locally adaptive zooming algorithm for digital images. Image and Vision Comput., 20:805--812, 2002.
• 7: Christian Bienia , Sanjeev Kumar , Jaswinder Pal Singh , Kai Li, The PARSEC benchmark suite: characterization and architectural implications, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454128]
• 8: Y. Cha and S. Kim. The Error-Amended Sharp Edge (EASE) scheme for image zooming. IEEE T. Image Process., 16(6):1496--1505, June 2007.
• 9: M.-J. Chen, C.-H. Huang, and W.-L. Lee. A fast edge-oriented algorithm for image interpolation. Image and Vision Comput., 23(9):791--798, 2005.
• 10: N. A. Dodgson. Image resampling. Technical Report UCAM--CL--TR--261, University of Cambridge Computer Lab., 15 JJ Thomson Avenue, Cambridge CB3 0FD, UK, Aug. 1992.
• 11: F. N. Fritsch and R. E. Carlson. Monotone piecewise cubic interpolation. SIAM J. Numer. Anal., 17(2):238--246, 1980.
• 12: A. Giachetti and N. Asuni. Fast artifacts-free image interpolation. In Proc. of the British Machine Vision Conf. 2008 (Leeds, Sept. 2008), pages 123--132.
• 13: M. Kraus, M. Eissele, and M. Strengert. GPU-based edge-directed image interpolation. In Image Analysis, volume 4522 of LNCS, pages 532--541. Springer, 2007.
• 14: X. Li and M. T. Orchard. New edge-directed interpolation. IEEE T. Image Process., 10(10):1521--1527, 2001.
• 15: K. Martinez and J. Cupitt. VIPS---a highly tuned image processing software architecture. In IEEE International Conf. on Image Process., 2005. ICIP 2005., volume 2, pages 574--577.
• 16: Don P. Mitchell , Arun N. Netravali, Reconstruction filters in computer-graphics, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.221-228, Aug. 1988
• 17: S. C. Park, M. K. Park, and M. G. Kang. Super-resolution image reconstruction: A technical overview. IEEE Signal Process. Mag., 20(3):21--36, 2003.
• 18: Nicolas Robidoux , Adam Turcotte , Minglun Gong , Annie Tousignant, Fast Exact Area Image Upsampling with Natural Biquadratic Histosplines, Proceedings of the 5th international conference on Image Analysis and Recognition, June 25-27, 2008, P=voa de Varzim, Portugal [doi>10.1007/978-3-540-69812-8_9]
• 19: J. Sun, J. Sun, Z. Xu, and H.-Y. Shum. Image super-resolution using gradient profile prior. In IEEE Conf. on Computer Vision and Pattern Recognition, 2008.
• 20: Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli. Image quality assessment: From error visibility to structural similarity. IEEE T. Image Process., 13(4):600--612, Apr. 2004.
• 21: Henry S. Warren, Hacker's Delight, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 22: M. Zhao and G. de Haan. Content adaptive video up-scaling. In S. Vassiliadis, L. Florack, J. Heijnsdijk, and A. van der Steen, editors, Proc. of ASCI 2003, 9th Annual Conf. of the Advanced School for Computing and Imaging, 4--6 June 2003, pages 151--156.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Filtering

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.0 General
          Subjects: Image processing software

General Terms:
Algorithms, Performance

Keywords:
GEGL, GPU, HLSL, SMP, VIPS, abyss policy, antialiasing, arithmetic branching, benchmark, co-convex interpolation, edge enhancement, fast image resampling, minmod limiter, natural and not-a-knot boundary conditions, nonlinear image filtering, quantitative comparison of image enlargement methods, video upsampling, zooming