Segmentation of moving objects in image sequence: A review

Segmentation of objects in image sequences is very important in many aspects of multimedia applications. In second-generation image/video coding, images are segmented into objects to achieve efficient compression by coding the contour and texture separately. As the purpose is to achieve high compression performance, the objects segmented may not be semantically meaningful to human observers. The more recent applications, such as content-based image/video retrieval and image/video composition, require that the segmented objects be semantically meaningful. Indeed, the recent multimedia standard MPEG-4 specifies that a video is composed of meaningful video objects. Although many segmentation techniques have been proposed in the literature, fully automatic segmentation tools for general applications are currently not achievable. This paper provides a review of this important and challenging area of segmentation of moving objects. We describe common approaches including temporal segmentation, spatial segmentation, and the combination of temporal-spatial segmentation. As an example, a complete segmentation scheme, which is an informative part of MPEG-4, is summarized.     

Image segmentation on a 2D array by a directed split and mergeprocedure

A 2D array implementation of image segmentation by a directed split and merge procedure is proposed. Parallelism is realized on two levels: one within the split and merge operations, where more than one merge (or split) may proceed concurrently, and the second between the split and merge operations, where several splits may be performed in parallel with merges. Both the split and merge operations are based on nearest neighbor communications between the processing elements (PEs), and facilitating low communication costs. The basic arithmetic operations required to perform split and merge are comparison and addition, allowing a simple structure of the PE as well as a hardwired control. A local of 512 bytes is sufficient to hold the interim data associated with each PE. A prototype PE has been constructed using 3 μm double-metal CMOS technology. Scaling up to 0.8 μm, it is possible to incorporate 32 PEs on a 5 cm² chip. With sufficiently large PE window sizes, image segmentation can be achieved in linear time     

Image sequence coding using quadtree-based block-matching motioncompensation and classified vector quantisation

The authors propose a new image sequence coding algorithm based on two crucial methods: quadtree segmentation and classified vector quantisation (CVQ). Overall coding rates are efficiently lowered by quadtree segmentation while visual quality is well preserved by a CVQ method. A moving-block extraction technique is employed to greatly improve the coding efficiency in the interframe coding mode. A quadtree efficiently segments the stationary background regions of interframe differential signals with various large-sized blocks, and the moving regions are extracted from the smallest blocks of 4×4 size during the growth of the quadtree. These moving regions are motion-compensated using a block-matching method based on 4×4 blocks and the residual signals of the motion-compensated moving regions are coded by CVQ. The stationary regions are simply replenished from the previous frame. The proposed coding scheme is effective for coding the sequential signals of video telephony or video conferencing at low bit rates     

Fractal image compression with region-based functionality

Region-based functionality offered by the MPEG-4 video compression standard is also appealing for still images, for example to permit object-based queries of a still-image database. A popular method for still-image compression is fractal coding. However, traditional fractal image coding uses rectangular range and domain blocks. Although new schemes have been proposed that merge small blocks into irregular shapes, the merging process does not, in general, produce semantically-meaningful regions. We propose a new approach to fractal image coding that permits region-based functionalities; images are coded region by region according to a previously-computed segmentation map. We use rectangular range and domain blocks, but divide boundary blocks into segments belonging to different regions. Since this prevents the use of standard dissimilarity measure, we propose a new measure adapted to segment shape. We propose two approaches: one in the spatial and one in the transform domain. While providing additional functionality, the proposed methods perform similarly to other tested methods in terms of PSNR but often result in images that are subjectively better. Due to the limited domain-block codebook size, the new methods are faster than other fractal coding methods tested. The results are very encouraging and show the potential of this approach for various internet and still-image database applications.     

Design and Analysis of an Efficient Evolutionary Image Segmentation Algorithm

Evolutionary image segmentation algorithms have a number of advantages such as continuous contour, non-oversegmentation, and non-thresholds. However, most of the evolutionary image segmentation algorithms suffer from long computation time because the number of encoding parameters is large. In this paper, design and analysis of an efficient evolutionary image segmentation algorithm EISA are proposed. EISA uses a K-means algorithm to split an image into many homogeneous regions, and then uses an intelligent genetic algorithm IGA associated with an effective chromosome encoding method to merge the regions automatically such that the objective of the desired segmentation can be effectively achieved, where IGA is superior to conventional genetic algorithms in solving large parameter optimization problems. High performance of EISA is illustrated in terms of both the evaluation performance and computation time, compared with some current segmentation methods. It is empirically shown that EISA is robust and efficient using nature images with various characteristics.     

Improvement of region-based motion estimation by considering uncovered regions

In natural video sequences, object movement causes regions to be covered or uncovered. Conventional algorithms for region-based motion estimation do not take uncovered regions into full account. Uncovered regions seriously decrease the accuracy of motion estimation. This paper presents an algorithm for increasing the motion estimation accuracy. This algorithm detects uncovered regions and uses them to improve image segmentation and motion estimation. Experimental results show that the presented algorithm is effective in reducing the displaced frame difference, without introducing any extra information for coding applications.     

An automatic algorithm for semantic object generation and temporal tracking

Automatic semantic video object extraction is an important step for providing content-based video coding, indexing and retrieval. However, it is very difficult to design a generic semantic video object extraction technique, which can provide variant semantic video objects by using the same function. Since the presence and absence of persons in an image sequence provide important clues about video content, automatic face detection and human being generation are very attractive for content-based video database applications. For this reason, we propose a novel face detection and semantic human object generation algorithm. The homogeneous image regions with accurate boundaries are first obtained by integrating the results of color edge detection and region growing procedures. The human faces are detected from these homogeneous image regions by using skin color segmentation and facial filters. These detected faces are then used as object seed for semantic human object generation. The correspondences of the detected faces and semantic human objects along time axis are further exploited by a contour-based temporal tracking procedure.     

Motion-based region growing segmentation of image sequences

This paper proposes a motion-based region growing segmentation scheme for the object-based video coding, which segments an image into homogeneous regions characterized by a coherent motion. It adopts a block matching algorithm to estimate motion vectors and uses morphological tools such as open-close by reconstruction and the region-growing version of the watershed algorithm for spatial segmentation to improve the temporal segmentation. In order to determine the reliable motion vectors, this paper also proposes a change detection algorithm and a multi-candidate pro- screening motion estimation method. Preliminary simulation results demonstrate that the proposed scheme is feasible. The main advantage of the scheme is its low computational load.     

基于自适应预处理的图像分割方法

为了防止分水岭算法过分割问题,该文提出了一种基于自适应预处理的图像分割算法。该方法在分水岭算法的基础上,首先结合像素点亮度特征和空间分布特性应用自适应方法对梯度图像进行预处理。通过考察各像素点邻域中像素分类后的分布情况,来判断考察点是处于区域中心还是处于边界,并据此对考察点的梯度值进行调节。然后在预处理后的梯度图像上选定标记,将预处理后的梯度图像中大于200个像素的连通区域标定为标记。最后用分水岭分割方法对带标记的参考图像进行分割。试验结果表明,该分割方法具有良好的分割效果。     

MPEG-4视频对象分割技术

随着MPEG-4,MPEG-7的研究发展,其基于内容的编码和面向对象的存取和操纵技术日益得到人们的重视。基于对象的视频图像分割是实现MPEG-4基于内容的编码和交互功能的关键。视频图像分割方法分为自动分割法和半自动分割法两种。结合视频分割的发展趋势,深入介绍了基于对象的视频分割的主要技术及国内外的最新研究算法,包括数学形态学算法以及活动轮廓模型(蛇模型)在该领域的应用,并分析了当前视频分割技术尚存在的问题和研究前景。     

基于HMT模型层间映射的图像邻域去噪算法

本文提出了一种以图像分割为基础的图像去噪算法.本文算法根据图像自身的性质,利用脉冲耦合神经网络模型自适应地将小波分解后的低频图像分割成不同的区域,并且利用简化的HMT层间模型在离散和平稳小波分别处理的情况下,将得到的连通区域邻域映射到各个不同的高频子带上.进一步结合固定的窗口,作为邻域去噪算法中的邻域.实验结果表明,该方法在降低了图像噪声的同时又尽可能地保留了图像的边缘信息,是一种有效的去噪方法.     

A multiresolution image segmentation technique based on pyramidalsegmentation and fuzzy clustering

In this paper, an unsupervised image segmentation technique is presented, which combines pyramidal image segmentation with the fuzzy c-means clustering algorithm. Each layer of the pyramid is split into a number of regions by a root labeling technique, and then fuzzy c-means is used to merge the regions of the layer with the highest image resolution. A cluster validity functional is used to find the optimal number of objects automatically. Segmentation of a number of synthetic as well as clinical images is illustrated and two fully automatic segmentation approaches are evaluated, which determine the left ventricular volume (LV) in 140 cardiovascular magnetic resonance (MR) images. First fuzzy c-means is applied without pyramids. In the second approach the regions generated by pyramidal segmentation are merged by fuzzy c-means. The correlation coefficients of manually and automatically defined LV lumen of all 140 and 20 end-diastolic images were equal to 0.86 and 0.79, respectively, when images were segmented with fuzzy c-means alone. These coefficients increased to 0.90 and 0.93 when the pyramidal segmentation was combined with fuzzy c-means. This method can be applied to any dimensional representation and at any resolution level of an image series. The evaluation study shows good performance in detecting LV lumen in MR images.     

Spatio-temporal segmentation of image sequences for object-oriented low bit-rate image coding

This paper describes a new method of segmentation of time-varying image sequences whose goal is object-oriented image coding. The segmentation represents a partition of each frame of the sequence into a set of regions which are homogeneous with regard to motion criterion. The region borders correspond to spatial contours of objects in the frame. Each spatio-temporal region is characterized by its temporal component, which is a model-dependent vector of motion parameters, and a structural component representing the polygonal approximation of the spatial contour of the region.

The construction of spatio-temporal segmentation includes two phases: the initialization step and temporal tracking. The initialization step is based on the spatial segmentation of the first frame of the sequence. Then homogeneous spatial regions are merged through motion estimation in accordance with a motion-based criterion. The temporal tracking consists of the projection of the segmentation along the time axis, and its adjustment. Special attention is paid to the processing of occlusions.

A predictive coding scheme is proposed which is based on the temporal coherence of the segmentation. This scheme is promising for a low bit-rate image compression.

The results for teleconference and TV sequences show the high visual quality of reconstructed only by prediction images. Moreover, the bit-rates for motion coding are very low: from 0.002 to 0.007 bit/pixel for teleconference sequence and from 0.004 to 0.021 bit/pixel for complex TV sequence. A scheme for encoding of the structural information is proposed which requires 0.083 – 0.17 bit per pixel depending on the content of the sequence.     

基于区域相似性与相异性的数字图像分割方法

针对数字图像数据量大、内容复杂、特征度量困难的特点,提出了一种综合区域相似性和相异性的基于图模型的分割方法.使用颜色方差作为距离度量,依靠区域邻接图和最近邻区域图来完成数字图像的快速区域合并分割.在合并过程中,通过合并区域的最小合并代价和最大合并代价变化,调整合并顺序,从策略上保证了分割区域的同质性和区域间的相异性.实验结果表明,该方法可以较好地解决图像的误分割现象.     

Image indexing and retrieval using expressive fuzzy description logics

The effective management and exploitation of multimedia documents requires the extraction of the underlying semantics. Multimedia analysis algorithms can produce fairly rich, though imprecise information about a multimedia document which most of the times remains unexploited. In this paper we propose a methodology for semantic indexing and retrieval of images, based on techniques of image segmentation and classification combined with fuzzy reasoning. In the proposed knowledge-assisted analysis architecture a segmentation algorithm firstly generates a set of over-segmented regions. After that, a region classification process is employed to assign semantic labels using a confidence degree and simultaneously merge regions based on their semantic similarity. This information comprises the assertional component of a fuzzy knowledge base which is used for the refinement of mistakenly classified regions and also for the extraction of rich implicit knowledge used for global image classification. This knowledge about images is stored in a semantic repository permitting image retrieval and ranking. This research was supported by the European Commission under contract FP6-027026 K-SPACE.     

Allowing content-based functionalities in segmentation-based coding schemes

This paper deals with the use of the segmentation tools and principles presented in [10] and [13] for allowing content-based functionalities. In this framework, means for supervised selection of objects in the scene are proposed. In addition, a technique for object tracking in the context of segmentation-based video coding is presented. The technique is independent of the type of segmentation approach used in the coding scheme. The algorithm relies on a double partition of the image that yields spatially homogeneous regions. This double partition permits to obtain the position and shape of the previous object in the current image while computing the projected partition. In order to demonstrate the potentialities of this algorithm, it is applied in a specific coding scheme so that content-based functionalities, such as selective coding, are allowed.     

Jointly Optimal Region-Classified Adaptive Vector Quantization for Very Low Bit Rate Video Coding

In this paper, a video coding algorithm suitable for the very low bit rate video coding system is presented. It takes advantage of the prior knowledge of the image type to segment the image to different regions, then codes each region with different coding criterion and method according to the different importance. An adaptive region-classified vector quantization strategy is exploited in this algorithm also. With segmentation of the frame and high correlation between frames, better codebooks of vector quantization are constructed to improve the quality. According to the simulation results, acceptable quality at about 10 kbits per second can be obtained for the typical test sequences.     

A Region-Based Representation of Images in MARS

We study the problem of representing images within a multimedia Database Management System (DBMS), in order to support fast retrieval operations without compromising storage efficiency. To achieve this goal, we propose new image coding techniques which combine a wavelet representation, embedded coding of the wavelet coefficients, and segmentation of image-domain regions in the wavelet domain. A bitstream is generated in which each image region is encoded independently of other regions, without having to explicitly store information describing the regions. Simulation results show that our proposed algorithms achieve coding performance which compares favorably, both perceptually and objectively, to that achieved using state-of-the-art image/video coding techniques while additionally providing region-based support.     

Blind tone mapped image quality assessment with image segmentation and visual perception

With tone mapping, high dynamic range (HDR) image contents can be displayed on low dynamic range (LDR) display devices, in which some important visual information may be distorted. Thus, the tone mapped image (TMI) quality assessment is one of important issues in HDR image/video processing fields. Considering the difference of visual distortion degrees between the flat and complex regions in TMI, and considering that high-quality TMI should preserve as much information as possible of its original HDR image especially in the high/low luminance regions, this paper proposes a new blind TMI quality assessment method with image segmentation and visual perception. First, we design different features to describe the distortion of TMI’s different regions with two kinds of TMI segmentation. Then, considering that there lacks an efficient algorithm to quantify the importance of features, a feature clustering scheme is designed to eliminate the poor effect feature components in the extracted features to improve the effectiveness of the selected features. Finally, considering the diversity of tone mapping operator (TMO), which may cause global and local distortion of TMI, some other global features are also combined. At last, a final feature vector is formed to synthetically describe the distortion in TMI and used to blindly predict the TMI’s quality. Experimental results in the public ESPL-LIVE HDR database show that the Pearson linear correlation coefficient and Spearman rank order correlation coefficient of the proposed method reach 0.8302 and 0.7887, respectively, which is superior to the state-of-the-art blind TMI quality assessment methods, and it means that the proposed method is highly consistent with human visual perception.     

Video and image applications on narrowband and broadband isdn

Two major ISDN applications which will undoubtedly affect world-wide telecommunications in the coming decade are discussed. They are: (1) video transmission and (2) image transmission. Brief reviews of videophone chronicle and the current video coding technologies are presented. The application of videophones using p × 64 (CCITT coding algorithm up to 1·5 Mb/s) and the DCT (discrete cosine transform) algorithm for narrowband ISDN are discussed. Broadcast TV quality DS3-45 MB/s video codecs are also briefly discussed as a probable videophone system in the broadband ISDN era. The explosive growth of facsimile services is reviewed, and the progress of image coding technologies and their standards are covered. The prospects of high resolution image transfer systems with ISDN are addressed.