Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1999-06-04
2002-06-04
Boudreau, Leo (Department: 2621)
Image analysis
Pattern recognition
Feature extraction
C382S181000, C382S203000, C382S236000, C382S241000, C382S242000, C382S243000, C382S256000, C382S260000, C382S266000, C348S252000, C348S625000, C358S532000, C375S240090, C375S240120
Reexamination Certificate
active
06400846
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to ordering image spaces, and more particularly, to segmenting video objects.
BACKGROUND OF THE INVENTION
Older video standards, such as ISO MPEG-1 and MPEG-2, are relatively low-level specifications primarily dealing with temporal and spatial compression of video signals. With these standards, one can achieve high compression ratios over a wide range of applications. Newer video coding standards, such as MPEG-4, see “Information Technology—Generic coding of audio/visual objects,” ISO/IEC FDIS 14496-2 (MPEG4 Visual), November 1998, allow arbitrary-shaped objects to be encoded and decoded as separate video object planes (VOP). These emerging standards are intended to enable multimedia applications, such as interactive video, where natural and synthetic materials are integrated, and where access is universal. For example, one might want to “cut-and-paste” a moving figure or object from one video to another. In order to identify the object, the video must first be “segmented.” Given the amount of video, both archived and newly acquired, it is desirable for the segmentation process to be either fully automatic or semi-automatic.
In the semi-automatic case, one may provide a segmentation for the first image. The problem then becomes one of object tracking. In the automatic case, the problem is to first identify the object, then to track the object. In either case, the segmentation process should attempt to minimize the input needed by the user, obviously, no input is optimal.
With VOPs, each image of a video sequence is segmented into arbitrarily shaped image regions. Each VOP describes a video object in terms of, for example, shape, motion, and texture. The exact method of producing VOP's from the source imagery is not defined by the standards. It is assumed that “natural” objects are represented by shape information, in addition to the usual luminance and chrominance components. Shape data can be provided as a segmentation mask, or as a gray scale alpha plane to represent multiple overlaid objects. Because video objects vary extensively with respect to low-level features, such as, optical flow, color, and intensity, VOP segmentation is a very difficult problem.
A number of segmentation methods are known. Region-based segmentation methods include mesh-based, motion model-based, and split-and-merge. Because these methods rely on spatial features, such as luminance, they may produce false contours, and in some cases, foreground objects may be merged into the background. More recently, morphological spatio-temporal segmentation has been used. There, information from both the spatial (luminance) and temporal (motion) domains are tracked using vectors. This complex method might erroneously assign a spatial region to a temporal region, and the method is difficult to apply to a video sequence including more than one object.
The most recent standardization effort taken on by the MPEG committee is that of MPEG-7, formally called “Multimedia Content Description Interface,” see “MPEG-7 Context, Objectives and Technical Roadmap,” ISO/IEC N2729, March 1999. Essentially, this standard plans to develop a set of descriptors that can be used to describe various types of multimedia information. This description is associated with the content itself and allows for fast and efficient searching of material that is of interest to the user. It is important to note that this standard is not meant to replace previous coding standards, rather, it builds on other standard representations, especially MPEG-4 since the multimedia content can be decomposed into different objects and each object can be assigned a unique set of descriptors. Also, the standard is independent of the format in which the content is stored. MPEG-7 descriptors can be attached to compressed or uncompressed data.
Descriptors for multimedia content can be used in a number of ways, see for example “MPEG-7 Applications,” ISO/IEC N2728, March 1999. Most interesting, for the purpose of the description below, are database search and retrieval applications. In the most general case, the user specifies some attributes of the desired object. These attributes may. include descriptors that describe the texture, motion and shape of a particular object.
The problem of shape representation is not a new problem, but it is a very difficult one. There are many methods that already exist, some of which are based on geometric properties of the closed contour, while others are based on some type of decomposition of the 2D binary signal. As listed in “Description of Core Experiment for Motion/Shape,” ISO/IEC N2690, March 1999, a number of proposals have already been made to the MPEG committee. The proposals based on contour include curvature scale space and normalized contour; the ones based on decomposition include wavelet-based contour description, zernlike moments, and multi-layer eigenvector.
All shape descriptors are required to be scale and rotation invariant. Most importantly, the effectiveness of a shape descriptor is judged on its performance in similarity-based retrieval. Therefore, a compact descriptor that is able to capture the structural information of the shape, yet be robust to noise within the boundary is expected to yield the most favorable results.
SUMMARY OF THE INVENTION
The invention provides a method for determining a surface of an object in a video sequence of images. The method begins by estimating a boundary of the object in each image of the sequence using motion information of adjacent images of the sequence. Then, portions of each image of the sequence are ordered to produce a sequence of ordered images. The ordering can use Voronoi ordering. The ordered portions are exterior to the estimated object boundary.
Edges in each ordered image are filtered using the motion information, and each ordered image of the sequence is searched to locate the filtered edges to form a new boundary outside the estimated boundary. The filtering and searching are repeated, while projecting the new object boundaries over the sequence of images, until the new object boundaries converges to a surface of the object.
The surface of the object, i.e., the smooth projection of the boundaries in sequence, can be used to segment the object from the video. The same methodology can also be used for segmenting multiple objects.
REFERENCES:
patent: 4771469 (1988-09-01), Wittenburg
patent: 5023920 (1991-06-01), Breu
patent: 5710833 (1998-01-01), Moghaddam et al.
patent: 5717463 (1998-02-01), Brailean et al.
patent: 5873081 (1999-02-01), Harel
patent: 6002803 (1999-12-01), Qian et al.
patent: 6133921 (2000-10-01), Turkiyyah et al.
Ogniewicz, et al. “Voronoi Skeletons: Theory and Applications”, IEEE, pp. 63-69, 1992.*
Ilg, et al, “The Application of Voronoi Skeletons to Perceptual Grouping”, IEEE, pp. 382-385, 1992.*
Ogniewicz “Skeleton-Space: a Multiscale Shape Description Combining Region and Boundary Information”, pp. 746-751, 1994.
Kung Sun-Yuan
Lin I-Jong
Sun Huifang
Vetro Anthony
Boudreau Leo
Brinkman Dirk
Curtin Andrew
Mariam Daniel G.
Mitsubishi Electric Research Laboratories Inc.
LandOfFree
Method for ordering image spaces to search for object surfaces does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for ordering image spaces to search for object surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for ordering image spaces to search for object surfaces will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2911274