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:
- Voronoi Diagram page on Wikipedia.
- 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.
- Emil Venere, "Genius of Einstein, Fourier key to new humanlike computer vision," Purdue University Press Release, June 20, 2011
Permanent Link to this article