Pyramid of Arclength Descriptor for Generating Collage of Shapes

摘要

This paper tackles a challenging 2D collage generation problem,rnfocusing on shapes: we aim to fill a given region by packing irregularrnand reasonably-sized shapes with minimized gaps and overlaps.rnTo achieve this nontrivial problem, we first have to analyzernthe boundary of individual shapes and then couple the shapes withrnpartially-matched boundary to reduce gaps and overlaps in the collages.rnSecond, the search space in identifying a good coupling ofrnshapes is highly enormous, since arranging a shape in a collage involvesrna position, an orientation, and a scale factor. Yet, this matchingrnstep needs to be performed for every single shape when wernpack it into a collage. Existing shape descriptors are simply infeasiblernfor computation in a reasonable amount of time. To overcomernthis, we present a brand new, scale- and rotation-invariant 2D shaperndescriptor, namely pyramid of arclength descriptor (PAD). Its formulationrnis locally supported, scalable, and yet simple to constructrnand compute. These properties make PAD efficient for performingrnthe partial-shape matching. Hence, we can prune away mostrnsearch space with simple calculation, and efficiently identify candidaternshapes. We evaluate our method using a large variety of shapesrnwith different types and contours. Convincing collage results inrnterms of visual quality and time performance are obtained.