Source: https://patents.google.com/patent/US9015742B2/en
Timestamp: 2018-06-20 22:11:41
Document Index: 17042291

Matched Legal Cases: ['Application No. 2', 'Application No. 2', 'Application No. 2', 'Application No. 03754665', 'Application No. 03754665', 'Application No. 03754665', 'Application No. 03754665']

US9015742B2 - Digital video signature apparatus and methods for use with video program identification systems - Google Patents
US9015742B2
US9015742B2 US14141716 US201314141716A US9015742B2 US 9015742 B2 US9015742 B2 US 9015742B2 US 14141716 US14141716 US 14141716 US 201314141716 A US201314141716 A US 201314141716A US 9015742 B2 US9015742 B2 US 9015742B2
US14141716
US20140115619A1 (en )
In patent is a continuation and claims priority to U.S. application Ser. No. 13/211,906, now U.S. Pat. No. 8,683,503, filed Aug. 17, 2011, entitled “Digital Video Signature Apparatus and Methods for Use With Video Program Identification Systems,” which is a continuation of U.S. application Ser. No. 12/845,660, now U.S. Pat. No. 8,020,180, filed Jul. 28, 2010, which is a continuation of U.S. application Ser. No. 11/372,582, now U.S. Pat. No. 7,793,318, filed Mar. 10, 2006, which is a continuation of International Application Serial Number PCT/US03/29219, filed Sep. 12, 2003, all of which are hereby incorporated by reference in their entireties.
The data acquisition unit 206 (FIG. 2) receives a compressed digital video frame or image from the demodulator 202 (block 500). As described above, the compressed video frames or images received by the data acquisition unit 206 are compressed using the well-known MPEG standard. However, any other compression standards or techniques yielding scaled image information (e.g., downscaled images) for the frames or images could be used instead.
The information representative of the image (i.e., the downscaled image containing selected pixel information), from which padding has been removed, may optionally be weighted (block 510). The processor 402 may weigh the downscaled image information (e.g., by multiplying each of the pixel values by a number ranging from zero to one) to improve the robustness of the signature generation process. For example, the processor 402 may weigh the pixel values associated with the center portions of an image or frame more heavily (e.g., using a multiplier closer to one) than those portions of the image or frame that are closer to the periphery of the image or frame. Weighting the central portion of an image more heavily than the peripheral portions of an image may significantly reduce or eliminate signature generation errors that may otherwise result in the event an image has been cropped at its periphery from its original form. In other words, cropping a portion of an image that is given little, if any, weight during the signature generation process will have little, if any, effect on the accuracy of the signature generation process.
S=(ΔX g ,ΔY g ,ΔX b ,ΔY b ,ΔX y,Δy ,ΔX bght ,ΔY bght) Equation 3
FIG. 13 depicts an example frame or image 1300 that contains three identical elliptical shapes 1302, 1304 and 1306, all of which are composed of the same component (e.g., a single color). As depicted by the dashed lines, the image 1300 has been sub-divided into four quadrants labeled Q0, Q1, Q2 and Q3. The centroid for the overall image 1300 is located at the “+” designated by the reference numeral 1306 and the centroids for the quadrants Q0, Q1, Q2 and Q3 are designated by the “+” signs designated by respective reference numerals 1308, 1310, 1312 and 1314, respectively.
Thus, when an image is partitioned or sub-divided into four sub-images, regions or areas, each image component (e.g., a color or brightness component) may be represented using five centroids (i.e., five horizontal and vertical coordinate pairs or ten values), one of which corresponds to the overall image and the remaining four of which correspond to the four sub-images or regions. For an image containing red, green, blue, yellow and brightness components, a set containing a total of twenty-five centroids (i.e., twenty five horizontal and vertical coordinate pairs or fifty values) may be used to form a signature for the image or frame. An example of such a signature can be represented as depicted in Table 4 below.
X=−100
As a result, signatures formed using centroids for these kinds of images will typically not be sufficiently unique to identify differences between, for example, an image containing one text block in a given location and another image containing a different text block in the same or a different location. In these cases, the image values may be inverted (i.e., the image may be inverted so that the foreground (e.g., textual information) is relatively light and the background is relatively dark) so that the foreground has a much more significant effect on the centroid of the image. The pixel values associated with the inverted image are then used to generate the centroid(s) and, thus, the signature for the image(s). However, when using Equations 1 and 2 described above to calculate the centroid values, the centroid values may be negated (i.e., multiplied by −1) to indicate that the centroid values correspond to an inverted image.
Sequence # REFERENCE SIGNATURE SEQUENCES
On the other hand, if the video program was already stored in the database but was associated with a different sequence, the operator may update the reference information to include possible signature sequences for that video program (block 1420). In some cases, multiple signature sequences may be needed to represent a single video program that can be conveyed to the demodulator 202 using somewhat different encoding at a broadcast station (not shown). An efficient manner to store and search multiple signature sequences for a single video program is to represent the sequence of signature positions for which multiple signatures are possible using a logical OR data structure. For example, a reference sequence of signatures may be expressed as [SA][SB|SN][SG][SF|SK], where the “|” means OR. Thus, continuing the example, the signature sequences [SA][SB][SG][SF], [SA][SN][SG][SK], [SA][SB][SG][SK] and [SA][SN][SG][SF] are all matches to the reference sequence of signatures and, thus, are all associated with the same video program. Storing reference signature information using the above-described OR-based data structure can significantly reduce the amount of memory needed to maintain a library of reference signatures and can substantially reduce the amount of time needed to search such a library of reference signatures for matching signatures. The activities associated with blocks 1418 and 1420 may be performed at, for example, the central facility 216 (FIG. 2).
an intra-coded block extractor to extract intra-coded macro blocks from a video frame associated with the video program;
a signature generator to form a signature for the scaled image based on a first centroid associated with a first image component of the scaled image and a second centroid associated with a second image component of the scaled image, the first centroid defined by first coordinates within the scaled image and the second centroid defined by second coordinates relative to the first centroid coordinates.
2. A system as defined in claim 1, further comprising a frame scanner to:
scan a plurality of video frames associated with the video program;
determine a number of intra-coded macro blocks in the video frames of the plurality of video frames; and
select a video frame from the plurality of video frames based on the number of intra-coded macro blocks in the selected video frame, and
the intra-coded block extractor to extract the intra-coded macro blocks from the selected video frame.
3. A system as defined in claim 2, wherein the plurality of video frames are compressed using a video compression standard.
4. A system as defined in claim 1, wherein the intra-coded extractor is to extract only intra-coded macro blocks from the video frame.
5. A system as defined in claim 1, wherein the image component corresponds with an image color component.
6. A system as defined in claim 1, wherein the image component corresponds with a brightness component.
7. A system as defined in claim 1, wherein the first centroid is associated with an image color and the first coordinates correspond with a first position within a first sub-image of the scaled image, and the second centroid is associated with the image color and the second coordinates correspond with a second position within a second sub-image of the scaled image.
8. A method of generating a signature associated with a video program, comprising:
extracting intra-coded macro blocks from a video frame associated with the video program;
defining a first centroid corresponding with a first image component of the scaled image by first coordinates within the scaled image;
defining a second centroid corresponding with a second image component of the scaled image by second coordinates relative to the first centroid coordinates; and
forming a signature for the scaled image based on the first centroid and the second centroid.
scanning a plurality of video frames associated with the video program;
determining a number of intra-coded macro blocks in the video frames of the plurality of video frames; and
selecting a video frame from the plurality of video frames based on the number of intra-coded macro blocks in the selected video frame,
wherein extracting the scaled image from the intra-coded macro blocks further comprises extracting the intra-coded macro blocks from the selected video frame.
10. A method as defined in claim 9, wherein the plurality of video frames are compressed using a video compression standard.
11. A method as defined in claim 8, further comprising extracting only intra-coded macro blocks from the video frame.
12. A method as defined in claim 8, wherein the image component corresponds with an image color component.
13. A method as defined in claim 8, wherein the image component corresponds with a brightness component.
14. A method as defined in claim 8, wherein the first centroid is associated with an image color and the first coordinates correspond with a first position within a first sub-image of the scaled image, and the second centroid is associated with the image color and the second coordinates correspond with a second position within a second sub-image of the scaled image.
extract intra-coded macro blocks from a video frame associated with a video program;
define a first centroid that corresponds with a first image component of the scaled image by first coordinates within the scaled image;
define a second centroid that corresponds with a second image component of the scaled image by second coordinates relative to the first centroid coordinates; and
form a signature for the scaled image based on the first centroid and the second centroid, the signature associated with the video program.
16. A computer readable storage device or storage disc as defined in claim 15, wherein the instructions further cause the processor to:
select a video frame from the plurality of video frames based on the number of intra-coded macro blocks in the selected video frame.
17. A computer readable storage device or storage disc as defined in claim 16, wherein the plurality of video frames are compressed using a video compression standard.
18. A computer readable storage device or storage disc as defined in claim 15, wherein the instructions further cause the processor to extract only intra-coded macro blocks from the video frame.
19. A computer readable storage device or storage disc as defined in claim 15, wherein the image component corresponds with at least one of an image color component or a brightness component.
20. A computer readable storage device or storage disc as defined in claim 15, wherein the first centroid is associated with an image color and the first coordinates correspond with a first position within a first sub-image of the scaled image, and the second centroid is associated with the image color and the second coordinates correspond with a second position within a second sub-image of the scaled image.
US14141716 2003-09-12 2013-12-27 Digital video signature apparatus and methods for use with video program identification systems Active US9015742B2 (en)
US20140115619A1 true US20140115619A1 (en) 2014-04-24
US9015742B2 true US9015742B2 (en) 2015-04-21
"MPEG Video Compression Technique," retrieved from , retrieved on Apr. 3, 2006 (9 pages).
"MPEG Video Compression Technique," retrieved from <http://rnvs.informatik.tu-chemnitz.de/˜jan/MPEG/HTML/mpeg—tech.html>, retrieved on Apr. 3, 2006 (9 pages).
"What is CIE 1976 (L* a* b*) colour space?" retrieved from , retrieved on Apr. 3, 2006 (2 pages).
"What is CIE 1976 (L* a* b*) colour space?" retrieved from <http://www.colourware.co.uk/cpfaq/q3-21.htm>, retrieved on Apr. 3, 2006 (2 pages).
Adobe, "CIELAB," retrieved from , retrieved on Mar. 17, 2003 (2 pages).
Adobe, "CIELAB," retrieved from <http://www.adobe.com/support/techguides/color/colormodels/cielab.html>, retrieved on Mar. 17, 2003 (2 pages).
Adobe, "The RGB (CMY) Color Model," retrieved from , retrieved on Mar. 17, 2003 (6 pages).
Adobe, "The RGB (CMY) Color Model," retrieved from <http://www.adobe.com/support/techguides/color/colormodels/rgbcmy.html>, retrieved on Mar. 17, 2003 (6 pages).
AOLs, "CIELAB Color Conversion," retrieved from , retrieved on Mar. 17, 2003 (1 page).
AOLs, "CIELAB Color Conversion," retrieved from <http://www.aols.com/colorite/cielabcolorconv.html>, retrieved on Mar. 17, 2003 (1 page).
Bailey, Chris, "MPEG Video Encoding Techniques," retrieved from , retrieved on Apr. 3, 2006 (10 pages).
Bailey, Chris, "MPEG Video Encoding Techniques," retrieved from <http://www.ecs.soton.ac.uk/˜cpb/oldsite/work/ug/mpeg—report/mpeg.html>, retrieved on Apr. 3, 2006 (10 pages).
Bodoni Systems Ltd, "What is CIELab?," retrieved from , retrieved on Mar. 17, 2003 (1 page).
Bodoni Systems Ltd, "What is CIELab?," retrieved from <http://www.bodoni.co.uk/colourcielab.html>, retrieved on Mar. 17, 2003 (1 page).
Canadian Intellectual Property Office, "Notice of Allowance," in connection with corresponding Canadian Patent Application No. 2,540,575, mailed May 1, 2013 (1 page).
Canadian Intellectual Property Office, "Office Action," in connection with corresponding Canadian Patent Application No. 2,540,575, mailed Jan. 31, 2011 (3 pages).
Canadian Intellectual Property Office, "Office Action," issued in connection with corresponding Canadian Patent Application No. 2,540,575, mailed Apr. 16, 2012 (4 pages).
European Patent Office, "Decision to Refuse a European Patent Application," issued in connection with corresponding European Patent Application No. 03754665.2, mailed Feb. 11, 2013 (17 pages).
European Patent Office, "Office Action," in connection with corresponding European Patent Application No. 03754665.2, mailed Apr. 15, 2011 (6 pages).
European Patent Office, "Office Action," issued in connection with corresponding European Patent Application No. 03754665.2, mailed Feb. 1, 2012 (6 pages).
European Patent Office, "Supplementary European Search Report," issued in connection with corresponding European Patent Application No. 03754665.2, mailed Dec. 6, 2010 (5 pages).
Haitsma et al.,"Robust Audio Hashing for Content Identification," In Content-Based Multimedia Indexing (CBMI), 2001 (8 pages).
Instituto Mexicano De La Propiedad Industrial, "Office Action," issued in connection with corresponding Mexican Patent Application No. PA/a/2006/002837, mailed Dec. 7, 2009 (3 pages).
International Preliminary Examining Authority, "International Preliminary Examination Report," issued in connection with corresponding International Patent Application No. PCT/US2003/029219, Feb. 23, 2007 (18 pages).
International Preliminary Examining Authority, "Written Opinion," issued in connection with corresponding International Patent Application No. PCT/US03/29219, mailed Jul. 8, 2005 (4 pages).
International Preliminary Examining Authority, "Written Opinion," issued in connection with corresponding International Patent Application No. PCT/US2003/29219, mailed Jan. 27, 2006 (5 pages).
International Searching Authority, "International Search Report," issued in connection with corresponding International Patent Application No. PCT/US2003/29219, mailed Jan. 27, 2004 (5 pages).
Lee et al., "Robust Algorithm for Scene Analysis on Compressed Video," IEEE, 1999 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Aug. 22-24, 1999 (4 pages).
Mohan, Rakesh, "Video Sequence Matching," IEEE, International Conference on Acoustics, Speech and Signal Processing, vol. 6, May 12-15, 1998 (4 pages).
Schneider et al., "A Robust Content Based Digital Signature for Image Authentication," IEEE, vol. 3, International Conference on Image Processing, Sep. 16-19, 1996 (4 pages).
Tudor, P. N., "MPEG-2 Video Compression." Electronics & Communication Engineering Journal 7, No. 6 (1995), pp. 257-264, retrieved from , retrieved on Mar. 28, 2006 (15 pages).
Tudor, P. N., "MPEG-2 Video Compression." Electronics & Communication Engineering Journal 7, No. 6 (1995), pp. 257-264, retrieved from <http://www.bbc.co.uk/rd/pubs/papers/paper—14/paper—14.shtml>, retrieved on Mar. 28, 2006 (15 pages).
United States Patent and Trademark Office, "Non-Final Office Action," issued in connection with corresponding U.S. Appl. No. 11/372,582, mailed Oct. 7, 2009 (8 pages).
United States Patent and Trademark Office, "Non-Final Office Action," issued in connection with corresponding U.S. Appl. No. 12/845,660, mailed Jan. 25, 2011 (6 pages).
United States Patent and Trademark Office, "Non-Final Office Action," issued in connection with corresponding U.S. Appl. No. 13/211,906, mailed Jun. 27, 2013 (5 pages).
United States Patent and Trademark Office, "Notice of Allowance," issued in connection with corresponding U.S. Appl. No. 11/372,582, mailed May 20, 2010 (6 pages).
United States Patent and Trademark Office, "Notice of Allowance," issued in connection with corresponding U.S. Appl. No. 12/845,660, mailed May 11, 2011 (7 pages).
United States Patent and Trademark Office, "Notice of Allowance," issued in connection with corresponding U.S. Appl. No. 13/211,906, mailed Oct. 23, 2013 (9 pages).
United States Patent and Trademark Office, "Restriction Requirement," issued in connection with corresponding U.S. Appl. No. 11/372,582, mailed Jul. 7, 2009 (6 pages).
Free format text: CHANGE OF NAME;ASSIGNOR:NIELSEN MEDIA RESEARCH, INC;REEL/FRAME:032160/0965
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:DENG, KEVIN;REEL/FRAME:032137/0741
Free format text: MERGER;ASSIGNOR:NIELSEN MEDIA RESEARCH, LLC;REEL/FRAME:032138/0722