“Jigsaw image mosaics”

This paper introduces a new kind of mosaic, called Jigsaw Image Mosaic (JIM), where image tiles of arbitrary shape are used to compose the final picture. The generation of a Jigsaw Image Mosaic is a solution to the following problem: given an arbitrarily-shaped container image and a set of arbitrarily-shaped image tiles, fill the container as compactly as possible with tiles of similar color to the container taken from the input set while optionally deforming them slightly to achieve a more visually-pleasing effect. We approach the problem by defining a mosaic as the tile configuration that minimizes a mosaicing energy function. We introduce a general energy-based framework for mosaicing problems that extends some of the existing algorithms such as Photomosaics and Simulated Decorative Mosaics. We also present a fast algorithm to solve the mosaicing problem at an acceptable computational cost. We demonstrate the use of our method by applying it to a wide range of container images and tiles.

1. AMINI, A. A. 1990. Using Dynamic Programming for Solving Variational Problems in Vision. IEEE Trans. on PAMI, Vol. 12, no 9, pp. 855-867, Sept. 1990. Google Scholar
2. ARAD, N., DYN, N., REISFELD, D., AND YESHURUN, Y. 1994. Image warping by Radial Basis Functions: Application to Facial Expressions. Computer Vision, Graphics, and Image Processing. GMIP, 56 (2), 161-172, 1994. Google Scholar
3. ARKIN, M., CHEW, P., HUTTENLOCHER, D. P., KADEM, K., AND MITCHELL, J. S. B. 1991. An Efficiently Computable Metric for Comparing Polygonal Shapes. IEEE Trans. on PAMI, Vol. 13, No. 3, 209-216, Mar. 1991. Google Scholar
4. DOWSLAND, K. A. AND DOWSLAND, W. B. 1992. Packing Problems. European Journal of Operational Research, 56:2 – 14, 1992.Google Scholar
5. DOWSLAND, K. A. AND DOWSLAND, W. B. 1995. Solution Approaches to Irregular Nesting Problems. European Journal of Operational Research, 84:506-521, 1995.Google Scholar
6. FINKELSTEIN, A. AND RANGE, M. 1998. Image Mosaics. In Roger D. Hersch, Jacques André, and Heather Brown, Ed., Artistic Imaging and Digital Typography, LNCS, No. 1375, Heidelberg: Springer-Verlag 1998. Google Scholar
7. HAEBERLI, P. 1990. Paint by Numbers. In Computer Graphics (Proceedings of ACM SIGGRAPH 90), 24(4), ACM, 207-214. Google Scholar
8. HAUSNER, A. 2001. Simulating Decorative Mossaics. In Proceedings of ACM SIGGRAPH 2001, ACM Press / ACM SIGGRAPH, New York, E. Fiume, Ed., Computer Graphics Proceedings, Annual Conference Series, ACM, 573-580. Google Scholar
9. KAPLAN, C.S. AND SALESIN, D. H. 2000. Escherization. In Proceedings of ACM SIGGRAPH 2000, ACM Press / ACM SIGGRAPH, New York, K. Akeley, Ed., Computer Graphics Proceedings, Annual Conference Series, ACM, 499-510. Google Scholar
10. KASS, M., WITKIN, A., AND TERZOPOULOS, D. 1987. Snakes: Active Contour Models, International Journal of Computer Vision, 1:321-331, 1987.Google Scholar
11. LLOYD, S. 1982. Least Square Quantization in PCM. IEEE Transactions on Information Theory, 28(1982): 129-137.Google Scholar
12. MILENKOVIC, V. J. 1999. Rotational Polygon Containment and Minimum Enclosure using only Robust 2D Constructions, Computational Geometry, 13(1):3-19, 1999. Google Scholar
13. MILENKOVIC, V. J. AND DANIELS, K. 1999. Translational Polygon Containment and Minimal Enclosure using Mathematical Programming. Transactions in Operational Research, 6:525-554, 1999.Google Scholar
14. MOORE, M. P. AND WILHELMS, J. 1988. Collision Detection and Response for Computer Animation, In Computer Graphics (Proceedings of ACM SIGGRAPH 88), 22(4), ACM, 289-298. Google Scholar
15. RUSSELL, S AND NORVIG, P. 1994. Artificial Intelligence: A Modern Approach, Prentice Hall, 1994. Google Scholar
16. SILVERS, R AND HAWLEY, M. 1997. Photomosaics, New York: Henry Holt, 1997. Google Scholar
17. STRAND, C. 1999. Hello, Fruit Face! : The Paintings of Guiseppe Arcimboldo, Prestel, 1999.Google Scholar
18. WOLFSON, H. J. AND RIGOUTSOS, I. 1997. Geometric Hashing: An Overview. IEEE Computational Science and Engineering, Vol. 4, No. 4, pp. 10-21. Google Scholar