Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1998-04-17
2001-09-04
Chang, Jon (Department: 2623)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C345S440000, C345S474000
Reexamination Certificate
active
06285794
ABSTRACT:
BACKGROUND
The emergence of multimedia computing is driving a need for digitally transmitting and receiving high quality motion video. The high quality motion video consists of high resolution images, each of which requires a large amount of space in a system memory or on a data storage device. Additionally, about 30 of these high resolution images need to be processed and displayed per second in order for a viewer to experience an illusion of motion. As a transfer of large, uncompressed streams of video data is time consuming and costly, data compression is typically used to reduce the amount of data transferred per image.
In motion video, much of the image data remains constant from one frame to another frame. Therefore, video data may be compressed by first describing a reference frame and then describing subsequent frames in terms of changes from the reference frame. Standards from an organization called Motion Pictures Experts Group (MPEG) have evolved to support high quality, full motion video. One primary operation performed in MPEG is block matching. A motion vector describing the offset between the current frame and a best match block is then computed. The motion vector is subsequently sent back to a host processor. Through the motion vector, MPEG allows a plurality of images to be compressed, along with code for performing a decompression.
In this light, the decompression process is analogous to an operation known as morphing. The morphing operation changes one picture into another by creating a smooth transitional link between the two pictures. The process preserves features associated with each image by mapping the features from a source image to corresponding features in a destination image. In one version of the conventional morphing process, given two pictures and correspondences between them, the morphing process produces a movie using the two pictures. Further, in a copending application, filed by Todor Georgiev on Apr. 17, 1998 and entitled “MULTI-IMAGE MORPHING”, hereby incorporated by reference, multiple images may be morphed together to create a plurality of morphing movies.
SUMMARY
A computer-implemented method for compressing a movie having a sequence of frames is disclosed. The method generates a compressed movie in terms of a few pictures in the original movie and correspondences among the pictures by: enumerating a pixel level frame to frame correspondence, representing the original frame sequence as a multi-image morph, extracting feature vectors describing principle changes from one frame to another frame, and performing a multi-image morphing as an “uncompressing” operation.
Implementations of the invention include the following. The correspondence generating step processes the frames using an optical flow method. The feature extracting step uses a principal components method. Further, if the movie has an original frame rate, the invention may resample the movie at a different frame rate. Moreover, the invention supports the editing of gestures and motions of a character in the movie. The method also allows the multi-image morphing to generate motion blur. The method also compensates for vibrations by discarding certain basis vectors or principal components.
Advantages of the invention include the following. A high movie compression rate is achieved. Moreover, the gestures and motions of characters in the movie may be edited.
REFERENCES:
patent: 5065447 (1991-11-01), Barnsley et al.
patent: 5387937 (1995-02-01), Dorricott et al.
patent: 5467413 (1995-11-01), Barrett
patent: 5613048 (1997-03-01), Chen et al.
patent: 5745668 (1998-04-01), Poggio et al.
patent: 5802220 (1998-09-01), Black et al.
patent: 5974159 (1999-10-01), Lubin et al.
patent: 6008820 (1999-12-01), Chauvin et al.
Gonzalez et al., Digital Image Processing, Sep. 1993, p. 148-156.*
T.Georgiev et al., “Morphing Between Multiple Images,” S.Illinois Univ. at Cardbondale dept. of Comp. Science, Technical Report, pp. 17, Apr. 17, 1997.
T.Georgiev, “Morphing Between Multiple Images: Theory and Applications,” Thesis, S.Illinois Univ. at Cardbondale Dept. of Comp. Science, pp. 45, Jun. 1997.
T. Georgiev, “Movie Compression and Motion Editing by Multi-Image Morphing,” available at www.graphics.lcs.mit.edu/~mcmillan/BRWorkshop/RegPost.html, Mar. 1998.
Seungyong Lee et al., “Polymorph: Morphing Among Multiple Images,” IEEE, 60-73, 1998.
Jain et al., “Algorithms for Clustering Data,” Prentice hall, Englewood Cliffs, NJ, 24-36, 1988.
Turk et al., “Eigenfaces for Recognition,” Massachusetts Institute of Technology, Journal of Cognitive Neuroscience vol.3,No. 1, 72-86, 1991.
Devijver et al., “Pattern Recognition: a Statistical Approach,” Prentice Hall International, 301-341, 1982.
George Wolberg, “Digital Image Warping,” IEEE Computer Society, 41-65, 1990.
Klaus et al., “Robot Vision,” The MIT Electrical Engineering and Computer Science Series, 279-95, 1986.
Johnson et al., “Applied Multivariate Statistical Analysis,” University of Wisconsin-Madison, Prentice-Hall, Inc., 361-388, 1982.
Beymer et al., “Example Based Image Analysis and Synthesis,” Massachusetts Institute of Technology Artificial Intelligence Laboratory, Memo No. 1431, Paper No.80, 21 pgs., Nov. 1993.
Seitz et al., “View Mrophing,” Department of Computer Sciences University of Wisconsin-Madison, 10 pgs., 1986.
“Motion Field & Optical Flow,” Motion Field 12, 279-295.
Wolberg, “Spatial Transformations,” Chapter 3, 41-65, 1990.
Georgiev Todor
Wainer Michael
Adobe Systems Incorporated
Chang Jon
Fish & Richardson P.C.
Johnson Timothy M.
LandOfFree
Compression and editing of movies by multi-image morphing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression and editing of movies by multi-image morphing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression and editing of movies by multi-image morphing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460518