Segmentation

June 28, 2011

Segmentation is the process of breaking an object into pieces that are distinguishable from each other by some rule. In the case of market segmentation, the object is to divide the market space according to one or more characteristics, such a price or industries served.

Image segmentation has a slightly different goal. The object is to break the image into areas that have similar characteristics to facilitate processing. One such task might be to locate the eyes of people in a photograph for automatic red eye correction. Another might be the machine vision application of counting the teeth on gears on a conveyor belt to reject those with missing teeth (or filtering profiles of individuals with missing teeth on dating sites!).

A very primitive form of segmentation is the Wigner-Seitz Cell that's used in the analysis of crystal symmetry. It's named after the two physicists, Eugene Wigner and Frederick Seitz. It's a way to segment an area populated by points on a regular lattice. The construction is quite simple. You just draw perpendicular lines at the midpoints of the lines that connect nearest-neighbor atoms, as shown in the figure.

Procedure for a Wigner-Seitz segmentation. 1. Draw connecting lines between nearest-neighbors 2. Construct perpendicular lines at the midpoints. 3. Stand back and admire your work. (Via Wikimedia Commons)

Of course, you needn't stop at two dimensions. You can just as easily construct planes at the midpoints in a three-dimensional lattice to get a volumetric cell.

The Wigner-Seitz cell is a type of Voronoi cell in which the points are arranged in a regular lattice. A Voronoi diagram is the logical segmentation of of an area populated by random points, a procedure that's often called a Voronoi tessellation. It was used by René Descartes, the inventor of Cartesian coordinates and the concept of graphing functions, as early as 1644.[1] A Voronoi cell about a point is defined by all points that are closer to that point than any other.

The first important application was by the British physician, John Snow, in his 1854 analysis of a cholera outbreak in Soho, London, England. Snow's Voronoi diagram of well pump placement and illness isolated the source of the infection to a particular public pump at Broad Street. As can be imagined, Voronoi diagrams are useful for analysis in quite a number of diverse subject areas, including wireless network coverage. An example Voronoi diagram appears below.

A Voronoi Tesselation of random points in a plane. (Via Wikimedia Commons)

Areas in a plane segment nicely, but segmenting real three-dimensional objects takes a little more creativity. A team of engineers from Purdue University, led by Karthik Ramani, the Donald W. Feddersen Professor Of Mechanical Engineering who teaches also in the Electrical and Computer Engineering Department, is developing a unique method of object segmentation.[2-3] They presented this method at a poster session last week at the IEEE Computer Vision and Pattern Recognition conference, Colorado Springs, Colorado, which was in session from June 21-23.[2]

The method developed by Ramani, his doctoral students, Yi Fang and Mengtian Sun, and Minhyong Kim, a professor of pure mathematics at the University College, London, uses the physical principle of heat diffusion. The importance of the technique lies in the fact that it can be applied to objects without any preconception of how many segments they may have. The technique uses the principles of finite element analysis (FEA) well known in computer modeling. The object is meshed, and the standard heat flow equations are applied.

An example analysis of a human hand is shown in the figure, below.[3] In segmenting a hand, and identifying the fingertips, it doesn't matter whether the fingers are bent. The heat flow would be nearly the same for the object. Also, objects can be categorized by the histogram of their "temperature" distribution, and this would be robust against orientation or folding of the object. There's a pending patent on this technique. The National Science Foundation provided funding.[3]

Purdue University heat diffusion segmentation of a human hand. (Purdue University image/Karthik Ramani and Yi Fang)

References:

1. Voronoi Diagram page on Wikipedia.
2. Yi Fang, Mengtian Sun and Karthik Ramani, "Heat-Mapping: A Robust Approach Toward Perceptually Consistent Mesh Segmentation," Posters 1B Color and Texture, Document Analysis, Segmentation and Grouping, IEEE Computer Vision and Pattern Recognition conference, June 21, 2011.
3. Emil Venere, "Genius of Einstein, Fourier key to new humanlike computer vision," Purdue University Press Release, June 20, 2011