The video coding standard MPEG-4 is enabling content-based functionalities. It takes advantage of a prior decomposition of sequences into video object planes (VOP's) so that each VOP represents a semantic object. Therefore, the extraction of semantic video objects is crucial initial part. In this paper, we present an efficient region based semi-automatic segmentation system, which combines low level automatic region segmentation with interactive method for defining and tracking high level semantic video objects. The proposed segmentation system extracts accurate object boundaries using gradual region merging and bi-directional temporal boundary refinement. The system comprises of two steps: an initial object extraction step where user input in the starting frame is used to extract a semantic object; and an object tracking step where underlying regions of the semantic object are tracked and grouped through successive frames. Experiments with different types of videos show the efficiency of the proposed system in semantic object extraction.

Homogeneous but distinct visual objects having low-contrast boundaries are usually merged in most of the segmentation algorithms. To alleviate this problem, an efficient image segmentation algorithm based on a bottom-up approach is proposed by using spatial domain information only. For initial image segmentation, we adopt a new marker extraction algorithm conforming to the human visual system. It generates dense markers in visually complex areas and sparse markers in visually homogeneous areas. Then, two region-merging algorithms are successively applied so that homogeneous visual objects can be represented as simple as possible without destroying low-contrast real boundaries among them. The first one is to remove insignificant regions in a proper merging order. And the second one merges only homogeneous regions, based on ternary region classification. The resultant segmentation describes homogeneous visual objects with few regions while preserving semantic object shapes well. Finally, a size-based region decision procedure may be applied to represent complex visual objects simpler, if their precise semantic contents are not necessary. Experimental results show that the proposed image segmentation algorithm represents homogeneous visual objects with a few regions and describes complex visual objects with a marginal number of regions with well-preserved semantic object shapes.

This paper proposes an efficient clustering algorithm for region merging. To speed up the search of the best pair of regions which is merged into one region, dissimilarity values of all possible pairs of regions are stored in a heap. Then the best pair can be found as the element of the root node of the binary tree corresponding to the heap. Since only adjacent pairs of regions are possible to be merged in image segmentation, this constraints of neighboring relations are represented by sorted linked lists. Then we can reduce the computation for updating the dissimilarity values and neighboring relations which are influenced by the merging of the best pair. The proposed algorithm is applied to the segmentations of a monochrome image and range images.