Image analysis – Applications
Reexamination Certificate
1999-11-01
2003-10-14
Chang, Jon (Department: 2623)
Image analysis
Applications
C382S170000, C382S218000, C725S019000
Reexamination Certificate
active
06633651
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to video processing and more particularly to a method and apparatus for the automatic recognition of video sequences.
BACKGROUND OF THE INVENTION
The reliable automatic recognition of video sequences has application in a number of areas. One application, for example, is the recognition of video commercials. Marketing executives, for example, may wish to know when and how often a particular commercial has been broadcast.
Clearly, one possibility would be to store an entire video sequence and continually compare broadcast signals with a library of stored sequences. This solution is not very practical since it would require a prohibitive amount of memory and processing power to implement.
EP 283570 teaches the use of digital signatures to match video sequences. However, such signatures, for example, representing the time between black scenes or color changes are insufficient to permit fast and accurate matching of complex video sequences.
EP 367585 describes a method of video recognition that involves creating digital signatures for all the frames in a sequence. This method involves an undue amount of processing power.
An object of the invention is to alleviate this problem and provide a practical method of recognizing a predetermined video sequence that is reasonably accurate yet at the same time requires an acceptable amount of processing power.
SUMMARY OF THE INVENTION
According to the present invention there is provided a method of detecting video sequences comprising the steps of receiving an incoming video stream consisting of sequences of successive frames, creating on-the-fly digital signatures in accordance with a predetermined algorithm, comparing said digital signatures with a plurality of stored digital signatures created in accordance with said predetermined algorithm, and identifying a candidate sequence of said incoming video stream as corresponding to said stored sequence in the event of a positive match of said digital signatures in accordance with predetermined criteria, characterized in that selected special frames of predetermined type are identified in said sequences, unique digital signatures are created for said special frames, said unique digital signatures being uniquely dependent on the individual characteristics of said special frames, said digital signatures of said special frames of a sequence collectively form a signature file for the sequence, and the digital signatures of the special frames are matched with the digital signatures of frames of the same type in stored signature files to identify a candidate sequence.
The video sequence is in digital form, either as a result of analog-to-digital conversion of an analog broadcast signal or the signal being in digital format.
A video stream is composed of a sequence of frames, each being consisting of a grid of pixels. Pixel values can be represented, for instance, by their red, green, and blue components, or by hue, luminance and saturation. In a preferred embodiment, the digital signature is derived from the pixel values of the frames intelligently selected from those forming a video sequence.
The digital signature can be created from a live or recorded video sequence. It can be stored in a file, which can, for example, contain the duration of the sequence, the number of hue or luminance categories considered, and for each selected frame in the sequence, a histogram representing the percentage of pixels in the defined categories, and scene information taken from a SmartFrame™ encoder, as described in our U.S. Pat. No. 6,415,000, entitled METHOD OF PROCESSING A VIDEO STREAM, which is herein incorporated by reference. This encoder extracts information relating the difference in pixel values pairs of frame in a sequence.
The processing engine can then compare one or more stored signatures to a candidate live or recorded video stream to find a match. The candidate signature is created in the same manner as the stored signatures, except that in the case of the candidate sequence, the signature is created “on-the-fly”, i.e. on a real-time basis. The candidate signature is a moving signature. This means that it is created from successive overlapping groups of frames.
The processing engine must continually slot the stored signature in time with the target video stream and generate an alert when there is a positive match. A signature must be re-slotted when it is determined that the target stream stops following or matching it. This operation is performed using a slider routine to be described in detail below.
It should be noted that the stored video signature frame size and sample rate do not have to match the video frame size and sample rate of the candidate sequence, which may, for example, be a broadcast signal. The video signature matching will tolerate varying broadcast quality.
In order to reduce the amount of required processing and memory power, the signature file preferably only contains the signatures or histograms of a limited number of frames in a video sequence. These frames are preferably frames having a particular significance, namely “cuts” which represent sudden changes in scene, “time-outs”, which are frames which occur after a predetermined period of time in the sequence when no “cuts” have been detected, and “start-frames”, which are simply the first frame in a particular sequence. For example, if the signature file is to be created for a particular commercial, first a histogram is taken for the first frame in the sequence and this is stored as the first signature in the signature file. The system then waits for the first frame corresponding to a cut, and stores this as the next signature unless a certain time, say two seconds, has elapsed without a cut occurring, in which case the signature of the next frame is taken and this is tagged as a “time-out” frame. This is to ensure that histograms are stored even when a sequence does not include cuts.
The present invention can offer a high percentage hit rate and a low percentage false hit rate.
The invention also provides an apparatus for detecting video sequences comprising means for receiving an incoming video stream consisting of sequences of successive frames, means for creating on-the-fly digital signatures in accordance with a predetermined algorithm, means for comparing said digital signatures with a plurality of stored digital signatures created in accordance with said predetermined algorithm, and means for identifying a candidate sequence of said incoming video stream as corresponding to said stored sequence in the event of a positive match of said digital signatures in accordance with predetermined criteria, characterized in that said means for creating on-the-fly digital signatures selects special frames of predetermined type in said sequences and creates unique digital signatures for said special frames, said unique digital signatures being uniquely dependent on the individual characteristics of said special frames, and said digital signatures of said special frames of a sequence collectively forming a signature file for the sequence, and said means for identifying a candidate sequence matches the digital signatures of the special frames with the digital signatures of frames of the same type in stored signature files to identify the candidate sequence.
The invention can be implemented in an IBM compatible personal computer equipped, for example, with a Pentium microprocessor and a commercial video card.
REFERENCES:
patent: 4230990 (1980-10-01), Lert et al.
patent: 4697209 (1987-09-01), Kiewit et al.
patent: 4739398 (1988-04-01), Thomas et al.
patent: 5019899 (1991-05-01), Boles et al.
patent: 5404160 (1995-04-01), Schober et al.
patent: 5436653 (1995-07-01), Ellis et al.
Kenyon et al. “High Capacity Real Time Broadcast Monitoring.” IEEE Int. Conf. on Systems, Man and Cybernetics: Decision Aiding for Complex Systems, vol. 1, Oct. 1991, pp. 147-152.
Hirzalla Nael
MacLean Roger
Menard Robert
Streatch Paul
(Marks & Clerk)
Chang Jon
March Networks Corporation
LandOfFree
Method and apparatus for recognizing video sequences 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 apparatus for recognizing video sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for recognizing video sequences will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173112