Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo


Unsupported browser: Your browser does not meet modern web standards. See how it scores »

{ action.text }

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. Felzen­szwalb’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.

0 comments about this story. Start the discussion »

Tagged: Computing

Reprints and Permissions | Send feedback to the editor

From the Archives


Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me