EXISTING TECHNIQUES OF VISUAL PROCESSING - Video Object Extraction and Representation: Theory and Applications - page 31

Figure 2.3. Limits of Spatial Correlation of Intensity: a) the original image of a
lit sphere. Although the sphere is a single object, because of the lighting, b) the
clustering of image intensities and c) edge detection values suggest multiple objects.
Identification of object boundaries is clearly not all visual.
ations that we use. In Fig. 2.2c, the region-based representation maps
the regions to nodes and the boundaries between regions to edges; in
Fig. 2.2d, boundary-based representation maps boundaries to edges and
boundary junctions to nodes. The form of solution depends upon the
graphical mapping. For region-based problems, the solution becomes a
matter of finding connected components, involving algorithms such as
clique finding, independent set and graph coloring algorithms. For a
boundary-based representation, the operations are a matter of a find-
ing closed path, such as Depth First Search, and minimum cut [Cormen
et al., 1990]. Regardless of formulation, both problems are computation-
ally difficult, since path-finding such as Hamiltonian Path and clustering
problems such as clique finding are both NP-complete [Garey and John-
son, 1979]. However, the algorithmic design space is determined by the
choice of region-based or boundary-based representation. In our own
work, the video object segmentation problem has the same duality and
the same issues, mentioned above, also apply.
USING SPATIAL INTENSITY PATTERNS:
CLUSTERING / EDGE DETECTION
The two processes, clustering and edge detection, are two techniques
that derive object features from spatial intensity patterns. Spatial cor-
relation of intensity is our most precise and robust feature in our video
sequence, strongly supported in image processing and in the biology of
our own human visual system. Like the problem representation, this
type of image processing also has a dual form. Using the correlation of
intensity and locality to infer to which video object the pixel belongs, we
can locally cluster pixels into regions that belong to the same video ob-
ject. Assuming the pixel clustering is correct, we need only to determine
the video object membership of these regions. The dual of the cluster-