Searching for Squishy Shapes
Vision algorithm models deformable objects
Context: To locate an object in an image, computer-vision algorithms often use mathematical models of the object’s shape. But finding the boundaries of “deformable” objects, like human organs, is difficult, because the model must account for all of the objects’ potential shape alterations. Algorithms that can pick out the edges of stretched or squashed objects are often inefficient; they require users or other algorithms to provide initial estimates of the objects’ positions and orientations. Pedro Felzenszwalb of the University of Chicago has developed a deformable-shape model that helps locate such objects in images quickly and accurately.
Methods and Results: Felzenszwalb’s algorithm is able to represent any two-dimensional shape that contains no holes. Each shape is modeled by a collection of triangles that approximates the boundary of the undeformed shape. The algorithm assumes that some triangles can be distorted more than others, and that triangle edges at the boundaries of an object tend to coincide with changes in image brightness. To match the model to objects in the image, the algorithm deletes one triangle at a time from the model, transferring the information about its best-fitting deformations and image locations to a neighboring triangle. Once all the triangles are eliminated, the stored information can be used to quickly decide the area in the image that best matches the model. Thus, the algorithm can find the object without searching for every possible location, orientation, or deformation of the model.
Given information about how an object could be represented by triangles, the algorithm finds the object’s boundaries in the image. Given a set of example shapes, the algorithm can also construct a general model for a class of objects, such as hands or leaves.
Why it Matters: Better modeling of deformable shapes increases the range of objects that computers running vision algorithms are able to automatically recognize. Felzenszwalb’s method could thus be important for applications such as medical imaging and surveillance. It is as accurate as the leading methods for finding object boundaries in medical images, but it performs well without initially having to guess the object’s location. Nor does the algorithm require the manual specification of parameters such as the amount of distortion allowed for each part of the shape; instead, it can learn from examples, which makes it easier to use.
Source: Felzenszwalb, P. F. 2005. Representation and detection of deformable shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 27:208–220.