Factoring repeated content within and among images

ABSTRACT

We reduce transmission bandwidth and memory space for images by factoring their repeated content. A transform map and a condensed epitome are created such that all image blocks can be reconstructed from transformed epitome patches. The transforms may include affine deformation and color scaling to account for perspective and tonal variations across the image. The factored representation allows efficient random-access through a simple indirection, and can therefore be used for real-time texture mapping without expansion in memory. Our scheme is orthogonal to traditional image compression, in the sense that the epitome is amenable to further compression such as DXT. Moreover it allows a new mode of progressivity, whereby generic features appear before unique detail. Factoring is also effective across a collection of images, particularly in the context of image-based rendering. Eliminating redundant content lets us include textures that are several times as large in the same memory space.

REFERENCES

• 1: Ahuja N., and Todorovic S. 2007. Extracting texels in 2.1D natural textures. ICCV.
• 2: Andrew C. Beers , Maneesh Agrawala , Navin Chaddha, Rendering from compressed textures, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.373-378, August 1996 [doi>10.1145/237170.237276]
• 3: Stephen Brooks , Neil Dodgson, Self-similarity based texture editing, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 4: M. Brown , D. G. Lowe, Recognising Panoramas, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1218, October 13-16, 2003
• 5: Chris Buehler , Michael Bosse , Leonard McMillan , Steven Gortler , Michael Cohen, Unstructured lumigraph rendering, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.425-432, August 2001 [doi>10.1145/383259.383309]
• 6: Shenchang Eric Chen, QuickTime VR: an image-based approach to virtual environment navigation, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.29-38, September 1995 [doi>10.1145/218380.218395]
• 7: Dabov K., Foi A., Katkovnik V., and Egiazarian K. 2007. Image denoising by sparse 3D transform-domain collaborative filtering. IEEE Transactions on Image Processing, 16, 8.
• 8: Yuval Fisher, Fractal image compression: theory and application, Springer-Verlag, London, 1995
• 9: Karlis Freivalds , Ugur Dogrusöz , Paulis Kikusts, Disconnected Graph Layout and the Polyomino Packing Approach, Revised Papers from the 9th International Symposium on Graph Drawing, p.378-391, September 23-26, 2001
• 10: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 11: Hays J., Leordeanu M., Efros A., and Liu Y. 2006. Discovering texture regularity as a higher-order correspondence problem. ECCV.
• 12: Nebojsa Jojic , Brendan J. Frey , Anitha Kannan, Epitomic analysis of appearance and shape, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.34, October 13-16, 2003
• 13: Kannan A., Winn J., and Rother C. 2006. Clustering appearance and shape by learning jigsaws. NIPS.
• 14: Martin Kraus , Thomas Ertl, Adaptive texture maps, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 15: Sylvain Lefebvre , Hugues Hoppe, Parallel controllable texture synthesis, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 16: Marc Levoy , Pat Hanrahan, Light field rendering, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.31-42, August 1996 [doi>10.1145/237170.237199]
• 17: Bruno Lévy , Sylvain Petitjean , Nicolas Ray , Jérome Maillot, Least squares conformal maps for automatic texture atlas generation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 18: Anthony Lobay , D. A. Forsyth, Shape from Texture without Boundaries, International Journal of Computer Vision, v.67 n.1, p.71-91, April 2006 [doi>10.1007/s11263-006-4068-8]
• 19: Yanxi Liu , Wen-Chieh Lin , James Hays, Near-regular texture analysis and manipulation, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 20: Lucas B., and Kanade T. 1981. An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop.
• 21: McCabe D., and Brothers J. 1998. DirectX 6 texture map compression. Game Developer, 42--46.
• 22: Pascal Müller , Gang Zeng , Peter Wonka , Luc Van Gool, Image-based procedural modeling of facades, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 23: Pedro V. Sander , John Snyder , Steven J. Gortler , Hugues Hoppe, Texture mapping progressive meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.409-416, August 2001 [doi>10.1145/383259.383307]
• 24: Shi J., and Tomasi C. 1994. Good features to track. CVPR.
• 25: Noah Snavely , Steven M. Seitz , Richard Szeliski, Photo tourism: exploring photo collections in 3D, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 26: Li-Yi Wei , Jianwei Han , Kun Zhou , Hujun Bao , Baining Guo , Heung-Yeung Shum, Inverse texture synthesis, ACM SIGGRAPH 2008 papers, August 11-15, 2008, Los Angeles, California
• 27: Daniel N. Wood , Daniel I. Azuma , Ken Aldinger , Brian Curless , Tom Duchamp , David H. Salesin , Werner Stuetzle, Surface light fields for 3D photography, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.287-296, July 2000 [doi>10.1145/344779.344925]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.5 Reconstruction
          Subjects: Transform methods
      I.4.6 Segmentation
          Subjects: Edge and feature detection
      I.4.7 Feature Measurement

General Terms:
Algorithms, Design, Theory

Keywords:
image compression, image epitomes, progressive images