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. 

Paper                
(low resolution)

(PDF, 5.79M)

Paper                 
(high resolution)

(PDF, 48.4M)

Supplementary Material

(PDF, 48.4M)

@article{kwan-2016-pad,
    author   = {Kin Chung Kwan and Lok Tsun Sinn and
               Chu Han and Tien-Tsin Wong and
                Chi-Wing Fu},
    title    = {Pyramid of Arclength Descriptor for
                Generating Collage of Shapes},
    journal  = {ACM Transactions on Graphics
               (SIGGRAPH Asia 2016 issue)},
    month    = {November},
    year     = {2016},
    volume   = {35},
    number   = {6},
    pages    = {229:1--229:12},
}