Electronic data encoding and recognition system

• US 5,019,899 A
• Filed: 11/01/1988
• Issued: 05/28/1991
• Est. Priority Date: 11/01/1988
• Status: Expired due to Term

• Current Assignee: Arbitron Inc. (MOOD Media Corporation)
• Original Assignee: Control Data Corporation (Ceridian HCM Holding, Inc.)
• Inventors: Tomkoski, Walter III, Chein, Wen S., Symanski, Chris P., Des Rioux, Philippe, Boles, Glenn M., Schober, Gary W.
• Primary Examiner(s): Ng, Jin F.
• Assistant Examiner(s): Chan, Wing F.
• Application Number:
  US07/265,831
• Time in Patent Office: 938 Days
• Field of Search: 358/84, 358/139, 455/2, 455/67, 379/92
• US Class Current: 725/22
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: H04H 60/59 of video recognising characters or patterns in general G06F18/00, G06V20/00
• CPC Class Codes: H04N 21/458 Scheduling content for creating a personalised stream, e.g. by combining a locally stored advertisement with an incoming stream; Updating operations, e.g. for OS modules ; time-related management operations arrangements for replacing or switching information during the broadcast or during the distribution H04H20/10
• CPC Class Codes: H04N 21/812 involving advertisement data advertising per se G06Q30/02
• CPC Class Codes: H04N 7/162 Authorising the user terminal, e.g. by paying; Registering the use of a subscription channel, e.g. billing

Abstract

The disclosure relates to an apparatus and method for creating digital signatures from frames of selected video segments such as TV commercials by a digitizing, compression and selection process which produces a multi-digit signature from each frame. The signatures are stored in a memory database. In the recognition mode broadcast video transmissions are similarly digitized frame by frame to generate signatures which are then compared with the signatures in the database to find matches. The system cycles efficiently through the database testing for signature matches and then totalizing the signature matches to determine occurrences of a match between a transmitted segment or commercial and a stored segment or commercial. The system also includes signature generating and comparison circuits which permit wide variations in the quality of the input video signals form a variety of different media sources such as off-air, videotape or camera inputs while maintaining accurate recognition.

Claims

1. Apparatus for continuous pattern recognition of broadcast video segments comprising

first means for digitally parametizing all of the pixels in all of the frames of video segments to be recognized to form multi-bit digital signatures therefrom related to the luminance of each pixel in each frame in accordance with a set of predetermined rules,

said first means including a memory in which the digitally parametized pixels are all stored as digital words and in a TV frame orientation of a plurality of lines corresponding to the frame from which they were derived, said first means also including means for processing substantially all of said parametized pixels to form a digital signature,

memory means coupled to said first means for storing said signatures as a database, there being groups of stored signatures for each segment to be recognized,

means for monitoring a broadcast video transmission,

means for receiving said broadcast video transmission and digitally parametizing all of the pixels in all of the frames of said video transmission to form a multi-bit digital test signature from each frame of said broadcast signal in accordance with said set of predetermined rules, and

means for coupling said test signatures to said database and comparing each of said test signatures separately with every signature in all of the groups of signatures in said database whereby a match of a test signature and a stored signature occurs if the number of digital bits matched is equal to or greater than a predetermined number.

2. Apparatus for continuous pattern recognition of broadcast video segments comprising

first means for digitally parametizing all of the pixels in all of the frames of video segments to be recognized and arraying all of the digitized pixels in a memory in a frame pattern and processing substantially all of said digitized pixels to form multi-bit digital signatures therefrom related to the luminance of each pixel in each frame in accordance with a set of predetermined rules,

memory means coupled to said first means for storing said signatures as a database, there being groups of stored signatures for each segment to be recognized,

means for monitoring a broadcast video transmission,

means for receiving said broadcast video transmission and digitally parametizing all of the pixels in all of the frames of said video transmission to form a multi-bit digital test signature from each frame of said broadcast signal in accordance with said set of predetermined rules, and

means for coupling said test signatures to said database and comparing each of said test signatures separately with every signature in all of the groups of signatures in said database whereby a match of a test signature and a stored signature occurs if the number of digital bits matched is equal to or greater than a predetermined number and a match of a broadcast segment with a stored segment occurs when the number of signatures in a group in the database which are matched by test signatures from a broadcast signal is equal to or greater than a predetermined number.

3. The method of creating a digital signature from a frame of a TV transmission comprising the steps of

forming a digital work of every pixel in a frame of a TV transmission and storing all of said digital words of a frame in a memory, each digital word representing the luminance of the pixel,

arraying all of the digital words in the frame into rows and columns of groups of digital words in said memory, said groups being arrayed over the entire frame and being uniformly spaced from each other and representing geometric areas of light and dark spots, and

comparing each group of digital words with another group of digital words, the two groups being compared preferably having considerably different picture content in said frame,

each comparison producing a digital bit with the total number of bits of the frame representing the digital signature of the frame.

4. The method defined in claim 3 where each said group comprises a rectangular array of 16 by 16 digital words.

5. The method defined in claim 4 wherein there are 64 of said groups of digital words called super pixels and the comparisons of one group with another group produce 32 bits which comprise the relative luminance and geometric features represented by the signature of the frame, and

said resulting signature being tolerant of signal transmission and reception quality variations.

6. The method defined in claim 4 wherein there are 64 sets of said groups of digital words and each is compared with a group specially positioned on said frame so that the ares of the frame of significance are compared, the comparison process producing 32 bits which comprise the signature of said frame.

7. The method defined in claim 5 wherein said 64 groups of digital words are arranged in rows and columns with uniform spacing between them to provide maximum entropy.

8. The method defined in claim 5 wherein said 64 groups of digital words cover substantially the entire area of a frame.

9. The method of analyzing and comparing two video transmissions to determine whether selected transmissions are present, comprising the steps of

receiving a first video transmission comprising a plurality of frames of information,

creating a first digital signature from each frame of said first video transmission,

selecting a plurality of said first digital signatures which provide maximum information about said first video transmission and storing said plurality of first digital signatures in an electronic database memory,

receiving a second video transmission comprising a plurality of frames of information,

creating a second digital signature from each frame of said second video transmission,

comparing each second digital signature with each of the first signatures in said memory to find first signatures which match each second signature,

wherein said second video transmission matches the first video transmission when a predetermined number of signatures stored in said memory match a number of signatures in said second video transmission.

10. The method defined in claim 9 wherein a first signature is compared with a second signature by the digital bits of one being compared with the digital bits of the other to determine the number of digital bits which do not match.

11. The method defined in claim 10 wherein each signature comprises 32 bits and the signatures are compared eight-bit segments at a time from each, each comparison of eight-bits producing a number of bits which are different and the comparison of all eight-bit segments of said signatures producing a total number of bits which are different, the two signatures matching when the total number of different bits is equal to or less than a predetermined number.

12. The method defined in claim 9 wherein said first video transmission is formed into a plurality of groups of first signatures, each group representing a TV commercial.

13. The method defined in claim 12 wherein all of said signatures are formed by the same method.

14. The method defined in claim 9 wherein each step of forming a digital signature includes digitizing every pixel of every frame of information.

15. A method of creating a digital signature from a defined length of electrical signal information comprising the steps of

receiving a length of electrical signal information made up of a plurality of discrete signal areas each having a unique electrical characteristic, each such signal area comprising a pixel of information,

forming a digital word from every pixel in said length of electrical information, each digital word representing said electrical characteristic of said pixel from which it was formed,

storing each of said digital words in a memory both serially in a line and in a plurality of lines representing the form of a frame of a TV picture,

arraying said digital words in groups with the groups having uniform spacing between them, and

electronically averaging and comparing pairs of said groups of digital words and forming a super pixel from each comparison, each super pixel having a digital bit value and all of the super pixel bits formed comprising the digital signature of said length of electrical information.

16. The method defined in claim 15 wherein the pairs of groups which are averaged and compared are relatively remote from each other and having different characteristic values.

17. The method defined in claim 15 and including the step of providing an average value for each group of digital words before said comparisons are made.

18. The method of analyzing and comparing video transmissions to determine whether selected transmissions are present, comprising the steps of

receiving a first video transmission comprising a plurality of frames of information,

creating a first digital signature from each frame of said first video transmission,

selecting a plurality of said first digital signatures which provide maximum information about said first video transmission and storing said plurality of first digital signatures in a first group in an electronic database memory,

receiving a second video transmission comprising a plurality of frames of information,

creating a second digital signature from each frame of said second video transmission,

selecting a plurality of said second digital signatures which provide maximum information about said second video transmission and storing said plurality of second digital signatures in a second group in said electronic database memory,

receiving a third video transmission to be analyzed to determine whether it is present in said database, said third video transmission comprising a plurality of frames of information,

creating a test digital signature from each frame of said third video transmission, and

comparing each test signature with each of the signatures in said database memory to find stored signatures which match each test signature, the match of a predetermined number of test signatures with a number of signatures in a group of stored signatures constituting a match of said third transmission with the video transmission represented by the group of stored signatures which has been matched.

36. The method defined in claim 18 wherein each group of signatures in said database includes a firs signature, a second signature, a third signature and a fourth signature,

each test signature being compared with the first signature of each group to see if there is a match and then with each second signature of each group to see if there is a match and then with each third signature of each group to see if there is a match and then with each fourth signature to see if there is a match,

each test signature matching a signature in said groups when the non-matching digital bits between them is less than a predetermined number, and

each third video transmission including a portion which is present in said database memory when a predetermined number of test signatures match a number of signatures in any one of said groups.

19. Apparatus for continuous pattern recognition of broadcast video segments comprising

means for digitally parametizing frames of video segments to be recognized and forming multi-bit digital signatures therefrom related to the luminance of each pixel in a frame in accordance with a set of predetermined rules,

means for storing said signatures in a database memory, there being groups of stored signatures for each segment to be recognized,

means for monitoring a broadcast signal,

means for digitally parametizing frames of said monitored signal to form a multi-bit digital test signature from each frame in accordance with said set of predetermined rules, and

means for comparing each of said test signatures separately with every signature in said database whereby a match of a test signature and a stored signature occurs if the number of digital bits matched is equal to or greater than a predetermined number,

a match of a broadcast segment with a stored segment occurring when the number of signatures in a group in the database which are matched by test signatures from a broadcast signal is equal to or greater than a predetermined number.

20. The apparatus defined in claim 19 wherein said means for comparing comprises a first storage means for holding a stored signature and a second storage means for holding a test signature,

an Exclusive-OR gate means coupled to said first and second storage means for detecting the number of digital bits of said signatures which do not match, and means coupled to said OR gate means for recognizing whether said number of bits is equal to or less than a predetermined number to represent a match between said signatures.

21. The apparatus defined in claim 20 wherein said last named means includes adding means for adding the number or digital bits which do not match and providing an output signal to indicate a match of signatures.

22. The apparatus defined in claim 21 wherein said output signal is coupled to scorecard means for keeping track of stored signatures which are matched and steering the test procedure through said database from signature to signature.

23. A method for creating a digital signature from a frame of a video signal comprising the steps of

receiving a frame of video information made up of a plurality of lines of video information, each line of video information being made up of discrete signal areas each having a luminance level, each such signal area being called a pixel,

forming a digital word of every pixel in every line of said frame of video information, each digital word representing the luminance of the pixel from which it was formed,

storing said digital words in a memory in a pattern to form a memory frame corresponding to the frame pattern of the corresponding pixels in said frame of video information,

arraying said digital words in groups in said memory with the groups being arrayed in rows and columns over substantially said entire memory frame, with substantially uniform spacing between adjacent groups, and

electrically averaging groups of said digital words to form super pixels and then comparing pairs of said super pixels, each such comparison forming a digital bit and all the bits thus formed comprising a digital signature of said frame.

24. The method defined in claim 23 wherein the pairs of groups which are averaged and compared are relatively remote from each other and have different characteristic values.

25. Apparatus for recognition and identification of segments of TV transmissions comprising

first means for receiving a plurality of segments of TV transmissions and forming multi-bit digital signatures from each frame of each segment thereof and selecting a group of signatures for each said segment,

a memory in which all of said groups of signatures are stored as a database,

second means for receiving real time TV transmissions which may contain one or more of said segments and forming multi-bit digital test signatures from each frame thereof,

an address generator coupled to said memory database for addressing each group of signatures therein sequentially and for addressing each signature in each group sequentially,

third means known as a bit difference counter including:

a first holding register having an input and an output, its input being coupled to said database and adapted to receive stored signatures therefrom one at a time,

a second holding register having an input and an output, its input being coupled to said source of test signatures, to receive test signatures therefrom,

the outputs of said first and second holding registers being coupled to fourth means for comparing a database signature with a test signature to determine the number of digital bits in each which do not match and thereby to determine database and test signatures which match, and

fifth means coupled to the output of said third means for registering the number of test signatures which match signatures in a group of database signatures, the match of a predetermined number of test signatures with signatures in a group in said database signifying the match of a stored TV transmission with a real time TV transmission.

26. The apparatus defined in claim 25 wherein said first and second holding registers are coupled to an Exclusived-OR gate as means for comparing the digital bits of said database signature and said test signature and providing an output representing the number of bits which are different, and

said fourth means comprises a comparator for receiving said number of bits which are different and a threshold number representing an acceptable number for said number of bits, said comparator providing an output representing a match of signatures when said number of bits is equal to or less than said threshold number.

27. The apparatus defined in claim 26 wherein said first and second storage means receive equal portions of said storage and test signatures at a time and the number of bits are added to provide a total number as said portions are processed.

28. The apparatus defined in claim 26 wherein said fourth means includes

gate means for comparing the bits of a database signature with the bits of a test signature,

accumulator means coupled to the output of said gate means for accumulating the total number of bits which are different between said database signature and said test signature, and

a comparator circuit coupled to said accumulator means receiving said total number and a threshold number and comparing said total number and said threshold number to determined whether there is a match.

29. The apparatus defined in claim 28 wherein said accumulator means includes means for converting a number of bits to a digital number.

30. The apparatus defined in claim 25 wherein said address generator is adapted to address sequentially first the first signature in each group of signatures and then the second signature in each group of signatures and then the third signature in each group of signatures and so on until all of the signatures in the database have been compared with a test signature.

31. The apparatus defined in claim 25 wherein said address generator includes a first counter coupled to said address generator for selecting a group of commercials to be compared with a test signature and a second counter coupled to said database for selecting a particular signature in a group of signatures, and

sequencing means, called a scorecard circuit, coupled to said address generator for cycling the comparing of a test signature with each of the signatures in said database and each of the groups of commercials.

32. The apparatus defined in claim 31 wherein said sequencing means cycles said address generator through said groups of signatures sequentially and sequentially through the signatures in each group.

33. The circuit defined in claim 31 wherein said scorecard circuit includes a first memory having a portion for each group of signatures in said database memory,

a second memory including means for keeping track of signature matches, and

a control circuit for receiving a match signal from said bit difference accumulator and coupled to said second memory,

said first and second memory being coupled to said address generator to take part in causing the cycling through said signatures in said database memory.

34. The apparatus defined in claim 33 wherein said second memory includes means for providing an output signal when a test segment matches a group of signatures in said database memory.

35. The apparatus defined in claim 34 and including a host computer which receives said output signal and provides identification of the matched group of signatures.