“Pyramid of arclength descriptor for generating collage of shapes”
Conference:
Type(s):
Title:
- Pyramid of arclength descriptor for generating collage of shapes
Session/Category Title: High Resolution
Presenter(s)/Author(s):
Abstract:
This paper tackles a challenging 2D collage generation problem, focusing on shapes: we aim to fill a given region by packing irregular and reasonably-sized shapes with minimized gaps and overlaps. To achieve this nontrivial problem, we first have to analyze the boundary of individual shapes and then couple the shapes with partially-matched boundary to reduce gaps and overlaps in the collages. Second, the search space in identifying a good coupling of shapes is highly enormous, since arranging a shape in a collage involves a position, an orientation, and a scale factor. Yet, this matching step needs to be performed for every single shape when we pack it into a collage. Existing shape descriptors are simply infeasible for computation in a reasonable amount of time. To overcome this, we present a brand new, scale- and rotation-invariant 2D shape descriptor, namely pyramid of arclength descriptor (PAD). Its formulation is locally supported, scalable, and yet simple to construct and compute. These properties make PAD efficient for performing the partial-shape matching. Hence, we can prune away most search space with simple calculation, and efficiently identify candidate shapes. We evaluate our method using a large variety of shapes with different types and contours. Convincing collage results in terms of visual quality and time performance are obtained.
References:
1. Alajlan, N., El Rube, I., Kamel, M. S., and Freeman, G. 2007. Shape retrieval using triangle-area representation and dynamic space warping. Pattern Recognition 40, 7, 1911–1920.
2. Arkin, E. M., Chew, L. P., Huttenlocher, D. P., Kedem, K., and Mitchell, J. S. 1991. An efficiently computable metric for comparing polygonal shapes. IEEE Trans. Pat. Ana. & Mach. Int. 13, 3, 209–216.
3. Belkasim, S. O., Shridhar, M., and Ahmadi, M. 1991. Pattern recognition with moment invariants: A comparative study and new results. Pattern Recognition 24, 12, 1117–1138.
4. Belongie, S., Malik, J., and Puzicha, J. 2002. Shape matching and object recognition using shape contexts. IEEE Trans. Pat. Ana. & Mach. Int. 24, 4, 509–522.
5. Chuang, G.-H., and Kuo, C.-C. 1996. Wavelet descriptor of planar curves: Theory and applications. IEEE Trans. on Image Processing 5, 1, 56–70.
6. Cohen-Or, D., Sorkine, O., Gal, R., Leyvand, T., and Xu, Y.-Q. 2006. Color harmonization. ACM Trans. on Graph (SIGGRAPH) 25, 3, 624–630.
7. Cui, M., Femiani, J., Hu, J., Wonka, P., and Razdan, A. 2009. Curve matching for open 2D curves. Pattern Recognition Letter 30, 1 (Jan.), 1–10.
8. Dalal, K., Klein, A. W., Liu, Y., and Smith, K. 2006. A spectral approach to NPR packing. In Int. Symp. on Non-Photorealistic Animation and Rendering, ACM, 71–78.
9. Donoser, M., Riemenschneider, H., and Bischof, H. 2010. Efficient partial shape matching of outer contours. In Asian Conf. on Comp. Vis. Springer, 281–292.
10. Gal, R., Sorkine, O., Popa, T., Sheffer, A., and Cohen-Or, D. 2007. 3D collage: expressive non-realistic modeling. In Int. Symp. on Non-Photorealistic Animation and Rendering, ACM, 7–14.
11. Garces, E., Agarwala, A., Gutierrez, D., and Hertzmann, A. 2014. A similarity measure for illustration style. ACM Trans. on Graph (SIGGRAPH) 33, 4, 93:1–93:9.
12. Goferman, S., Tal, A., and Zelnik-Manor, L. 2010. Puzzle-like collage. Computer Graphics Forum 29, 2, 459–468. Cross Ref
13. Goldberg, D., Malon, C., and Bern, M. 2004. A global approach to automatic solution of jigsaw puzzles. Computational Geometry: Theory and Applications 28, 2-3 (June), 165–174.
14. Granlund, G. H. 1972. Fourier preprocessing for hand print character recognition. IEEE Trans. on Comp. 100, 2, 195–201.
15. Hamann, B., and Chen, J.-L. 1994. Data point selection for piecewise linear curve approximation. Computer Aided Geometric Design 11, 3, 289–301.
16. Hausner, A. 2001. Simulating decorative mosaics. In Proc. of SIGGRAPH, 573–580.
17. Hong, B.-W., and Soatto, S. 2015. Shape matching using multiscale integral invariants. IEEE Trans. Pat. Ana. & Mach. Int., 1, 151–160. Cross Ref
18. Hu, W., Chen, Z., Pan, H., Yu, Y., Grinspun, E., and Wang, W. 2016. Surface mosaic synthesis with irregular tiles. IEEE Trans. Vis. & Comp. Graphics 22, 3 (Mar.), 1302–1313.
19. Hu, M.-K. 1962. Visual pattern recognition by moment invariants. IRE Trans. on Info. Theory 8, 2, 179–187. Cross Ref
20. Huang, H., Zhang, L., and Zhang, H.-C. 2011. Arcimboldo-like collage using internet images. ACM Trans. on Graph (SIGGRAPH Asia) 30, 6 (Dec.), 155:1–155:8.
21. Huang, Z., Wang, J., Fu, H., and Lau, R. W. 2014. Structured mechanical collage. IEEE Trans. Vis. & Comp. Graphics 20, 7, 1076–1082.
22. Kaplan, C. S., and Salesin, D. H. 2000. Escherization. In Proc. of SIGGRAPH, 499–510.
23. Kaplan, C. S., and Salesin, D. H. 2004. Dihedral escherization. In Proc. of Graphics Interface, Canadian Human-Computer Communications Society, 255–262.
24. Khotanzad, A., and Hong, Y. H. 1990. Invariant image recognition by Zernike moments. IEEE Trans. Pat. Ana. & Mach. Int. 12, 5, 489–497.
25. Kim, J., and Pellacini, F. 2002. Jigsaw image mosaics. In SIGGRAPH 2002, 657–664.
26. Krish, K., and Snyder, W. 2008. A new accumulator-based approach to shape recognition. In Advances in Visual Computing, vol. 5359. 157–169.
27. Lee, S.-M., Abbott, A. L., Clark, N. A., and Araman, P. A. 2006. A shape representation for planar curves by shape signature harmonic embedding. In Proc. IEEE Conf. on Comp. Vis. and Pat. Rec., vol. 2, 1940–1947.
28. Manay, S., Hong, B., Yezzi, A., and Soatto, S. 2004. Integral invariant signatures. In Proc. Euro. Conf. on Comp. Vis., Springer, 87–99.
29. Mokhtarian, F., and Mackworth, A. K. 1992. A theory of multiscale, curvature-based shape representation for planar curves. IEEE Trans. Pat. Ana. & Mach. Int. 14, 8, 789–805.
30. Mokhtarian, F., Abbasi, S., and Kittler, J. 1996. Efficient and robust retrieval by shape content through curvature scale space. In Int. Workshop on Image Databases and Multimedia Search, 35–42.
31. Orchard, J., and Kaplan, C. S. 2008. Cut-out image mosaics. In Int. Symp. on Non-Photorealistic Animation and Rendering, 79–87.
32. Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D. 2002. Shape distributions. ACM Trans. on Graph 21, 4, 807–832.
33. Persoon, E., and Fu, K.-S. 1977. Shape discrimination using Fourier descriptors. IEEE Trans. on Systems, Man and Cybernetics 7, 3, 170–179.
34. Reinert, B., Ritschel, T., and Seidel, H.-P. 2013. Interactive by-example design of artistic packing layouts. ACM Trans. on Graph (SIGGRAPH Asia) 32, 6 (Nov.), 218:1–218:7.
35. Rother, C., Bordeaux, L., Hamadi, Y., and Blake, A. 2006. Autocollage. In ACM Trans. on Graph (SIGGRAPH), 847–852.
36. Sheng, Y., and Shen, L. 1994. Orthogonal Fourier-Mellin moments for invariant pattern recognition. The Journal of the Optical Society of America-A 11, 6, 1748–1757. Cross Ref
37. Sun, J., Ovsjanikov, M., and Guibas, L. 2009. A concise and provably informative multi-scale signature based on heat diffusion. In Computer Graphics Forum, vol. 28, Wiley Online Library, 1383–1392.
38. Tabbone, S., Wendling, L., and Salmon, J.-P. 2006. A new shape descriptor defined on the Radon transform. Comp. Vis. & Image Understanding 102, 1, 42–51.
39. Tangelder, J. W., and Veltkamp, R. C. 2008. A survey of content based 3D shape retrieval methods. Multimedia tools and applications 39, 3, 441–471.
40. Van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. 2011. A survey on shape correspondence. In Computer Graphics Forum, vol. 30, Wiley Online Library, 1681–1707.
41. Veltkamp, R. C., and Hagedoorn, M. 2001. State of the art in shape matching. In Principles of visual information retrieval. Springer, 87–119.
42. Xu, J., and Kaplan, C. S. 2007. Calligraphic packing. In Proc. of Graphics Interface, ACM, 43–50.
43. Yang, M., Kpalma, K., and Ronsin, J. 2008. A survey of shape feature extraction techniques. Pattern Recognition, 43–90.
44. Yao, F.-H., and Shao, G.-F. 2003. A shape and image merging technique to solve jigsaw puzzles. Pattern Recognition Letters 24, 12, 1819–1835.
45. Zhang, D., and Lu, G. 2002. Shape-based image retrieval using generic Fourier descriptor. Signal Processing: Image Communication 17, 10, 825–848. Cross Ref
46. Zou, C., Cao, J., Ranaweera, W., Alhashim, I., Tan, P., Sheffer, A., and Zhang, H. 2016. Legible compact calligrams. ACM Trans. on Graph (SIGGRAPH) 35, 4 (July), 122:1–122:12.
