Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
1998-12-17
2001-06-26
Johns, Andrew W. (Department: 2621)
Image analysis
Applications
Motion or velocity measuring
Reexamination Certificate
active
06252975
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a conversion of dynamic video data to a representative compilation of static frames comprising selected important information within the dynamic video. Such a compilation not only consumes a smaller memory space but can provide a convenient index into the dynamic video. More specifically, the present invention relates to the real time selection of key static frames from a portion of the dynamic video comprising a global motion by the limiting of the data processing to only significant interest points of the video.
BACKGROUND OF THE PRESENT INVENTION
Dynamic to static conversion of video data includes representing the dynamic media (video, animations) with a number of still images which carry selected important information within the dynamic media. For example, in the case of a video consisting of a pure pan or zoom sequence (i.e., global motion), the efficient representation may contain the beginning, middle and end frames of the pan or zoom. In the case of a commercial video consisting of short clips of different products manufactured by a company, the efficient representation may contain a single image from each product shown in the video. Although, it would be easy for an operator to find these images if the operator watched the whole video, such an editorial distillation is very time consuming. Accordingly, there is a substantial need for a method and system which can analyze dynamic media information in real time for purposes of selecting key frames acceptably representative of the dynamic media.
The subject invention is thus more particularly applicable to an improved real time selection method for a plurality of key frames from scenes comprising global motion within the dynamic video.
The key problem in selection of the key frames is to estimate the global motion between frames. Time domain global motion estimation techniques can be classified into three groups, feature correspondence methods, optical flow methods and direct methods. Feature correspondence requires a number of point correspondences among two or three frames to be known or estimated a priori. The motion parameters are computed from these correspondences. The other two methods do not require determination of distinct feature points, but instead utilize the optical flow constraint in between two corresponding views. The optical flow methods consist of two steps: the estimation of the optical flow field, and recovering the motion parameters using this estimated optical flow. On the other hand, direct methods utilize only the spatio-temporal image intensity gradients to estimate the motion. Many motion estimators in each of these categories have been proposed in the literature; however, all of these methods have some drawbacks and are exclusively designed for off-line computations. (J. Bergen, P. Hurt, R. Hingorani and S. Peleg, “A Three-Frame Algorithm for Estimating Two-Component Image Motion”, IEEE Trans. Pattern Analy. Machine Intell, vol. 14, no.9, pp. 886-896, September 1992.)
The amount of data involved for identifying the particular values for all the pixel locations in a dynamic video makes any of the above prior art methods impractical for computing real time motion estimations for assessing representative static key frames for a dynamic video. Accordingly, there is also a need for a method that can reduce the necessary computation so that it can be done in real time and thereby avoid the disadvantages of delayed off-line computations.
The present invention contemplates a new and improved method and system which overcomes the above referenced problems and others to provide a new method for identification of a global motion in a dynamic video wherein the underlying computations can be accomplished in real time for the generation of a plurality of key static frames representative of the global motion portion of the video.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, there is provided a method of real time converting a dynamic video to a set of static key frames representative of a global motion portion of the dynamic video comprising the steps of digitizing the dynamic video into a temporal sequence of static image frames, designating significant parts of the frames to comprise interest points; identifying a global motion by tracking interest point motion trajectories with real time computing of changes to the interest points and selecting from the frames including the global motion, key frames comprising a set of static frames representative of the dynamic video. The significant parts preferably comprise those parts or edges of an image frame within the video that include areas of high gradient. The interest points subject to computation are further reduced by partitioning the frames within a distribution grid and selecting only one interest point within each grid cell. Thus, by merely computing the differences in the minimized interest points, i.e., at a reduced number of pixels, the computation time can be minimized and expedited for real time processing of the dynamic video into a set of static frames.
In accordance with another aspect of the present invention, the identifying global motion comprises estimating a constant intensity of the interest points along a motion trajectory in a predetermined time period. The estimating includes representing the motion trajectory with a plurality of affine parameters from a selected optical flow equation. Changes in the affine parameters are compared with a preselected threshold for purposes of assessing whether or not the global motion is occurring. When global motion is detected, the key frames are selected by capturing the frames at a predetermined rate during the time period of the global motion.
One benefit obtained by use of the present invention is the ability to contemporaneously compare, with the receiving of the stream of video data, pixel values of the interest points, for real time selection of the key frames.
Another benefit obtained by the present invention is the method of selecting interest points from all of the available pixels in a frame to facilitate the real time computation by limiting the interest points to areas of preselected significance, such as those having a high gradient that signify edge portions, like a black-to-white transition. The interest points are further limited by dividing the frame into a grid and selecting only a single interest point for each grid cell. By assessing changes in the value of interest points with a conventional processing operator for estimating error, interest points distributed throughout the entire frame can be monitored for purposes of identifying the global motion.
Other benefits and advantages for the subject new method and system will become apparent to those skilled in the art upon a reading and understanding of the specification.
REFERENCES:
patent: 5557684 (1996-09-01), Wang et al.
patent: 5767922 (1998-06-01), Zabih et al.
patent: 5784115 (1998-07-01), Bozdagi
patent: 5923365 (1999-07-01), Tamir et al.
patent: 5943445 (1999-08-01), Dufaux
patent: 6037988 (2000-03-01), Gu et al.
patent: 0 690 413 (1996-01-01), None
V. Kobla, et al., “Archiving, indexing, and retrieval of video in the compressed domain”, Proceedings of the SPIE—The International Society for Optical Engineering, vol. 2916, pp. 78-89 (1996).
A.M. Ferman, et al., “Object-based indexing of MPEG-4 compressed video”, Proceedings of the SPIE—The International Society for Optical Engineering, vol. 3024, pt. 2, pp. 953-963 (1997).
W. Zhou et al, “Real-time content-based processing of multicast video”, Conference Record of the 32nd Asilomar Conference on Signals, Systems, and Computers, vol. 1, pp. 882-886 (IEEE, Piscataway, NJ, 1998).
T.S. Huang, et al., “Human facial motion modeling, analysis, and synthesis for video compression”, Proceedings of the SPIE—The International Society for Optical Engineering vol. 1605, pp. 234-241 (1991).
F. Quek, R. Bryll, “Vector Coherence Mapping: A Parallelizable Approach to Image Flow Computation”, Proceedings/Inte
Bozdagi Gozde
Bryll Robert
Fay Sharpe Fagan Minnich & McKee LLP
Johns Andrew W.
Nakhjavan Shervin
Xerox Corporation
LandOfFree
Method and system for real time feature based motion... 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 and system for real time feature based motion..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for real time feature based motion... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2518590