Chapter 16SEGMENTATION USINGCLUSTERING METHODSAn attractive broad view of vision is that it is an inference problem: we have somemeasurements, and we wish to determine what caused them, using a mode. Thereare crucial features that distinguish vision from many other inference problems:firstly, there is an awful lot of data, and secondly, we don’t know which of thesedata items come from objects — and so help with solving the inference problem— and which do not. For example, it is very difficult to tell whether a pixel lieson the dalmation in figure 16.1 simply by looking at the pixel. This problem canbe addressed by working with a compact representation of the “interesting” imagedata that emphasizes the properties that make it “interesting”. Obtaining thisrepresentation is known as segmentation.It’s hard to see that there could be a comprehensive theory of segmentation,not least because what is interesting and what is not depends on the application.There is certainly no comprehensive theory of segmentation at time of writing, andthe term is used in different ways in different quarters. In this chapter we describesegmentation processes that have no probabilistic interpretation. In the followingchapter, we deal with more complex probabilistic algorithms.Segmentation is a broad term, covering a wide variety of problems and of tech-niques. We have collected a representative set of ideas in this chapter and in chap-ter ??. These methods deal with different kinds of data set: some are intended forimages, some are intended for video sequences and some are intended to be appliedto tokens — placeholders that indicate the presence of an interesting pattern, saya spot or a dot or an edge point (figure 16.1). While superficially these methodsmay seem quite different, there is a strong similarity amongst them1.Eachmethodattempts to obtain a compact representation of its data set using some form ofmodel of similarity (in some cases, one has to look quite hard to spot the model).One natural view of segmentation is that we are attempting to determine whichcomponents of a data set naturally “belong together”. This is a problem known asclustering; there is a wide literature. Generally, we can cluster in two ways:1Which is why they appear together!433Normalized Graph Cuts: Pages 16 - 34434 Segmentation using Clustering Methods Chapter 16Figure 16.1. As the image of a dalmation on a shadowed background indicates, animportant component of vision involves organising image information into meaningful as-semblies. The human vision system seems to be able to do so surprisingly well. The blobsthat form the dalmation appear to be assembled “because they form a dalmation,” hardlya satisfactory explanation, and one that begs difficult computational questions. This pro-cess of organisation can be applied to many different kinds of input. figure from Marr,Vision, page101, in the fervent hope that permission will be granted• Partitioning: here we have a large data set, and carve it up according tosome notion of the association between items inside the set. We would liketo decompose it into pieces that are “good” according to our model. Forexample, we might:– decompose an image into regions which have coherent colour and textureinside them;– take a video sequence and decompose it into shots — segments of videoshowing about the same stuff from about the same viewpoint;– decompose a video sequence into motion blobs, consisting of regions thathave coherent colour, texture and motion.• Grouping: here we have a set of distinct data items, and wish to collect setsof data items that “make sense” together according to our model. Effects likeSection 16.1. Human vision: Grouping and Gestalt 435occlusion mean that image components that belong to the same object areoften separated. Examples of grouping include:– collecting together tokens that, taken together, forming an interestingobject (as in collecting the spots in figure 16.1);– collecting together tokens that seem to be moving together .16.1 Human vision: Grouping and GestaltEarly psychophysics studied the extent to which a stimulus needed to be changedto obtain a change in response. For example, Webers’ law attempts to capturethe relationship between the intensity of a stimulus and its perceived brightnessfor very simple stimuli. The Gestalt school of psychologists rejected this approach,and emphasized grouping as an important part of understanding human vision. Acommon experience of segmentation is the way that an image can resolve itselfinto a figure — typically, the significant, important object — and a ground —the background on which the figure lies. However, as figure 16.2 illustrates, whatis figure and what is ground can be profoundly ambiguous, meaning that a richertheory is required.Figure 16.2. One view of segmentation is that it determines which component of theimage forms the figure, and which the ground. The figure on the left illustrates one formof ambiguity that results from this view; the white circle can be seen as figure on the blacktriangular ground, or as ground where the figure is a black triangle with a circular wholein it — the ground is then a white square. On the right, another ambiguity: if the figureis black, then the image shows a vase, but if it is white, the image shows a pair of faces.figure from Gordon, Theories of Visual Perception, page 65,66 in the fervent hope thatpermission will be grantedThe Gestalt school used the notion of a gestalt — a whole or a group — andof its gestaltqualit¨at — the set of internal relationships that makes it a whole436 Segmentation using Clustering Methods Chapter 16Figure 16.3. The famous Muller-Lyer illusion; the horizontal lines are in fact the samelength, though that belonging to the upper figure looks longer. Clearly, this effect arisesfrom some property of the relationships that form the whole (the gestaltqualit¨at), ratherthan from properties of each separate segment. figure from Gordon, Theories of VisualPerception, page 71 in the fervent hope that permission will be granted(e.g. figure 16.3) as central components in their ideas. Their work was charac-terised by attempts to write down a series of rules by which image elements wouldbe associated together and interpreted as a group. There were also attempts to con-struct algorithms, which are of purely historical interest (see[?]for an introductoryaccount