HK1087550B - Message reconstruction from partial detection - Google Patents

Description

Message reconstruction from partial detection results

Background

The present invention relates to a method and system for accurately detecting encoded data included in audio media data.

There is a great interest in the coding of audio signals used in audience measurement. In order to evaluate what the audience is listening to at a particular time, the environment of a listener of the audio signal is monitored at regular time intervals. If the detected audio signal contains an identification code, the message can be quickly identified.

Based on the receipt of the identified messages, the popularity or popularity of various broadcast programs may be assessed. It is therefore very important to determine exactly which encoded audio signals are received.

However, the acoustic properties of different audio environments may vary greatly. As a result, the rate at which audio signals are successfully received and identified in different environments may vary widely. For example, certain environments are quite harmful for accurately detecting encoded messages because of the large amount of noise or interference. There may also be circumstances in which the encoded message may not be detected because the code is missing. In these cases, only a portion of the identification code may be received.

Therefore, what is desired is a system with reduced sensitivity to acoustic environments that can detect codes in as many different environments as possible, regardless of detrimental acoustic conditions.

It would also be desirable to have a system that accurately recognizes the detection of an encoded message even if only a portion of the message is received or detected.

Summary of The Invention

For the purposes of this application, the following terms and definitions will apply:

the term "data" as used herein refers to any indicia, signals, marks, symbols, fields, groups of symbols, representations, and any other physical form or forms representing information, whether permanent or temporary, whether visible, audible, acoustic, electric, magnetic, electromagnetic or other representation;

as used herein, "audio media data" refers to any data representing or constituting audible sound, and which may be accessed over the air or over cable, satellite, network, internet (including the internet), distributed on storage media, or otherwise;

the term "message symbol" as used herein refers to a data unit selected from a predetermined symbol group for constituting a part of a message contained in data included in audio media data;

the term "continuous stream of encoded messages" as used herein refers to encoded messages arranged in a predetermined temporal or spatial order, whether the order is continuous or intermittent;

the term "processor" as used herein refers to processing devices, apparatus, programs, circuits, systems and subsystems, either implemented in hardware, software, or both, and including individual units and groups of units;

the term "generating" as used herein with respect to data refers to maintaining existing data for further processing and deriving new data from pre-existing data;

the terms "first," "second," and "additional" are used to distinguish one element, group, data, object or thing from another, and are not used to denote relative positions or arrangements in time.

According to one aspect of the invention, a method is provided for detecting data included in audio media data as a continuous stream of encoded messages. The method comprises the following steps: detecting predetermined message data representing predetermined messages of a continuous stream of encoded messages; generating message detection quality data (merit data) representing a specified accuracy of the detected predetermined message data when correctly representing the information content of the predetermined message; and confirming correct detection of the predetermined message based on the message detection quality data.

According to another aspect of the invention, a system for detecting data included in audio media data as a continuous stream of encoded messages is provided. The system comprises: detecting means for detecting predetermined message data representing predetermined messages of the continuous stream of encoded messages; quality data generating means for generating message detection quality data representing a specified accuracy of the detected predetermined message data when correctly representing the information content of the predetermined message; and confirming means for confirming correct detection of the predetermined message based on the message detection quality data.

The present invention, together with further features and advantages thereof, will become apparent from the following detailed description considered in conjunction with the accompanying drawings.

Brief Description of Drawings

FIG. 1 is a functional block diagram illustrating a system according to one embodiment of the present invention.

Fig. 2 is a block diagram illustrating an embodiment of the system of fig. 1.

Fig. 3 is a flow chart showing one mode of operation of the system of fig. 1 and 2.

Fig. 4 is a flowchart showing completion of one process of fig. 3.

Fig. 5 to 8 are diagrams showing a continuous stream of encoded messages.

Fig. 9 is a diagram showing an advantageous format of messages included in a continuous stream of encoded messages.

Detailed description of certain advantageous embodiments

Fig. 1 is a functional block diagram illustrating an advantageous embodiment of a system 30 for detecting data included in audio media data as a continuous stream of encoded messages. In some embodiments, the continuous stream of encoded messages includes data useful in audience measurement, advertisement verification, royalty calculation, and the like. Such data typically includes an identification of a program, advertisement, file, song, network, station, or channel, or other aspect that describes or is otherwise related to the media audio data, such that it characterizes the audio media data. In some embodiments, the continuous stream of encoded messages includes symbols arranged chronologically in the audio media data.

The system 30 comprises an audio media data input 2 for detecting data comprised in the audio media data as a continuous stream of encoded messages. The audio media data input means 2 may be a single device fixed at the source to be monitored or a plurality of devices fixed at a plurality of sources to be monitored. Alternatively, the audio media data input 2 may be a portable monitoring device that may be carried by an individual for monitoring multiple sources as the individual moves.

In case the audio media data is sound data, the audio media data input means 2 is typically a microphone with an input, which receives the audio media data in the form of sound energy, and which is used to transduce the sound energy into electrical data. In the case of monitoring audio media data in the form of light energy, the audio media data input 2 takes the form of a light sensitive device, such as a photodiode. The audio media data input 2 may also take the form of a magnetic pickup for detecting a magnetic field associated with a speaker, a capacitive pickup for detecting an electric field, or an antenna for detecting electromagnetic energy. In other embodiments, the audio media data input 2 takes the form of an electrical connection to a monitoring device. The monitoring device may be a television, radio, cable converter, satellite television system, game console system, VCR, DVD player, portable player, computer, web appliance, or the like. In still other embodiments, the audio media data input 2 is embodied in monitoring software running on a computer or other rendering system for collecting media data.

The symbol sequence estimation subsystem 4 receives input data from the audio media data input 2. The symbol sequence estimation subsystem 4 processes the input data to detect the presence of symbols that may represent encoded messages included in the audio media data as a continuous stream of encoded messages. For example, symbols may be detected according to any of the techniques disclosed in the following patents: U.S. Pat. No.5,764,763 to Jensen et al, U.S. Pat. No.5450,490 to Jensen et al, U.S. Pat. No.5,579,124 to Aijala et al, U.S. Pat. No.5,581,800 to Fardeau et al, U.S. Pat. No.5,319,735 to Preuss et al, U.S. Pat. No.6,175,627 to Petrovich et al, U.S. Pat. No.5,828,325 to Wosewicz et al, U.S. Pat. No.6,154,484 to Lee et al, U.S. Pat. No.5,945,932 to Smith et al, PCT patent application WO 00/04662 to Srinivasan, WO98/26529 to Lu et al, WO 96/27264 to Lu et al, WO 99/59275 to Lu et al, and U.S. patent application No.09/318,045 to Neuhauser et al, all of which are incorporated herein by reference.

A storage means 6 is optionally provided to store data. It may be desirable to store the data generated by the symbol sequence estimation subsystem 4 for later use. In addition, optional data transfer means 8 is provided for transferring data from the symbol sequence estimation subsystem 4 to a remote location, such as a central monitoring station 10, having an accompanying information base 12, if desired. The data generated by the symbol sequence estimation subsystem 4 may be transmitted to the central monitoring station 10 as a continuous or serial data stream. Alternatively, the data generated by the symbol sequence estimation subsystem 4 may be stored in the storage means 6 for time-shifted communication with the central monitoring station 10. The information base 12 accessible by the central monitoring station 10 may be utilized, for example, to generate identification data for the audio media data based on the information content of the received message.

Fig. 2 is a block diagram of an advantageous embodiment 100 of the display system 30. The system 100 includes an audio media data input 2 for data, which may include audio media data having a continuous stream of encoded messages therein. The audio media data input device 2 may take any of the forms described above in connection with fig. 1.

To detect the continuous stream of messages included in the received data, the system 100 includes a message processor 14 for processing the received data in the same manner as the subsystem 4 of fig. 1, the message processor 14 being described more fully below in connection with fig. 3.

Storage means 16 is provided for storing message information data including detected symbols of the message, as well as information content representative of the message, and message detection quality data representative of a specified accuracy of the message information data or a likelihood of data correctness, all generated by message processor 14. The message information data and the message detection quality data may be used later to confirm detection of the predetermined message. A communication device 18 is provided to transmit data from the message processor 14 to the central monitoring station 10 with its accompanying information base 12. The data communicated by the communication device 18 includes acknowledged or unacknowledged message information data, with or without message detection quality data communicated from the message processor 14 at the detection time, as a continuous or continuous stream of data. Alternatively, the data transmitted by the communication device 18 includes acknowledged or unacknowledged message information data with or without message detection quality data transmitted from the storage means 16.

Fig. 3 shows one mode of operation of systems 30 and 100 for detecting message a of a continuous stream of encoded messages included in audio media data, where each message includes a plurality of message symbols. At step 34, a sequence of symbols is examined from the message stream to detect the presence of a message having a predetermined format (labeled herein as "message a" for convenience). The symbol sequence may be selected for examination in any of a number of different ways. In one embodiment, each set of S sequential symbols or data potentially capable of corresponding thereto is examined at step 34, depending on the length or duration of the data. In another embodiment, a set of S sequential symbols or data corresponding thereto may be selected based on previous detection of one or more other messages in the sequence. In yet another embodiment, detection of symbols characterizing known positions in the message symbol sequence, such as synchronization symbols, is used to select the data to be pinged at step 34.

Since message a has a predetermined format, systems 30 and 100 can rely not only on the detection of individual symbols, but also on the message format in determining whether the message is fully detected when step 34 is performed. For example, if message A consists of S sequential symbols X₁，X₂，...，X_SComposition of, wherein X_iIs a synchronization symbol, step 34 may be at the synchronization symbol S_iIs executed under the condition that has been detected. The positions of the remaining symbols are then known and their presence or absence determined.

If all the symbols of message A have been detected, the symbol sequence in message A is assigned the highest message detection quality data value M_MAXRepresenting the maximum likelihood that message A is detected, and message information data stored and/or as information content representing message A, with or without data M_MAXGround is passed to step 46 for further processing.

If it is determined at step 40 that not all of the symbols of message a have been detected, but that those detected symbols constitute a qualified subset of message a, the system generates message information data representing the apparent information content of message a, whether partially or fully, and that the qualified subset message a is subject to validation processing at steps 42 and 44.

A decision 40 is made as to the detected symbols constituting a qualified subset of the message a according to a predetermined qualification rule. Since message a satisfies the given rule at step 40, system 30 or 100 assigns message detection quality data M to message a to indicate that its likelihood of correct detection is less than 100%, but still high enough to make it possible to consider message a as detected as being confirmed.

In one embodiment, the detection of at least a predetermined minimum number of symbols of message a constitutes an eligibility rule. In another embodiment, the detection of an uninterrupted sequence of symbols having at least a predetermined minimum length is used as an eligibility criterion. In yet another embodiment, the detection of one or more predetermined synchronization symbols of message a, together with a predetermined number of message information symbols, is used as an eligibility rule.

In yet another embodiment, a combination of two or more of the above-described qualification rules is employed, and the satisfaction of any of several qualification rules or sets of rules justify the detected subset of symbols being qualified for validation at steps 42 and 44. The process of step 40 is shown in fig. 4 as being performed by applying two eligibility rules or criteria, wherein either of the two eligibility rules or criteria is satisfied to qualify the detected subset of symbols. At step 50, a first set of rules or criteria is applied to the subset of symbols. If the subset of symbols satisfies these rules or criteria, message A is assigned message detection quality data M_iAnd the process proceeds to step 42. If not, the process proceeds to step 54 where a second set of rules or criteria is applied to the subset of symbols. If the subset of symbols satisfies the second set of rules or criteria, message A is assigned message detection quality data M even if the first set of rules or criteria is not satisfied_jIs different from M_iIn any event, the subset of symbols is deemed eligible for validation and processing proceeds to step 42.

At step 42, system 30 or 100 determines whether one or more detected messages B of the message stream are qualified to confirm detection of message a represented by the qualified subset of symbols.

In some embodiments, message B is selected to be the message immediately following message A in the continuous stream of messages, as shown in FIG. 5. In some other embodiments, message B is selected as the message immediately preceding message a, as shown in fig. 6. In still other embodiments, messages immediately preceding and immediately following message a are both used to validate a subset of eligible message a.

In further embodiments, message B precedes message a to be acknowledged by two or more message intervals, as shown in fig. 7. In still other embodiments, message B is at two or more message intervals after message A to be acknowledged, as shown in FIG. 8. In still other embodiments, two such messages are used to validate a subset of eligible messages a. Various combinations of three or more messages are also used, in still other embodiments, to validate a subset of eligible messages a.

In order to qualify for a confirmation at step 42 of fig. 3, message B must satisfy one or more predetermined criteria. In some embodiments, for a message to qualify for an acknowledgement, all of its symbols must be detected. However, in other embodiments, detection of less than all symbols of a message may still qualify its acknowledgment as long as its message information is reliably established and/or it is only one of several acknowledged messages.

The system 30 or 100 generates message information data representing the apparent information content of message B, whether partial or complete, along with message detection quality data representing its specified accuracy. The message detection quality data for message B for acknowledgement purposes may be but need not be a binary symbol.

If message B proves to qualify for the subset of a, a matching step 44 is performed to confirm the apparent information content of the subset of a. In some embodiments, message B must have the same information content as the apparent content of a subset of a. In other embodiments in which the data is formatted such that a given information content of message B implies a different, but known, information content of message a, the correspondence of the apparent information content of message a with such different, but known, information content may identify a subset of message a.

It will be appreciated from the above that in an embodiment, the validation of the message information data of message a depends on (1) the presence of the qualified subset of message a represented by its message detection merit data, (2) the validation of the eligibility of message a by message B represented by its message detection merit data, and (3) the matching of the message information data of message a with the message information data of message B.

In other embodiments, the message information data of message a is validated only based on its message detection merit data. For example, in the case where multiple symbols of message a necessary to establish its information content have been detected, message a may be considered to be acknowledged based only on message detection quality data indicating a high probability that the message detection quality data is accurate.

Once the qualified subset of message A has been validated at step 44, message detection quality data M, M with or without it_iOr M_jIs stored and/or transmitted for further processing at step 46.

In certain advantageous embodiments, the process of FIG. 3 is modified so that (i) the symbols of messages A and B are detected and (ii) their respective message detection quality data are generated in a monitoring system at the user's location. The monitoring system is either a fixed device or a portable device carried by the audience member. The detected symbols and their respective message detection quality data are either transmitted to the system (which performs steps 40, 42 and 44 of fig. 3) or stored for later transmission to such a system.

Embodiments of the present invention will now be described for use in detecting a continuous stream of encoded messages having a format as disclosed in U.S. patent application No.09/318,045, which is hereby incorporated by reference. As shown in fig. 9, each such message is formatted as two redundant sequences of message information symbols, X, with two synchronization symbols, Sync1 and Sync2, inserted therein. The symbols Sync1 and Sync2 are distinct from each other such that each represents a determinable position within the sequence of message symbols. The message information symbols X are selected from a predetermined group of n symbols, wherein the symbols are arranged in a predetermined order, conveniently denoted by an index i assigned to each symbol, such that i is 1, 2. For example, the predetermined symbol group may have three different symbols, so that n is 3. However, in this exemplary message format, n may be selected to be any positive integer greater than 1. Preferably, but not necessarily, each symbol in a predetermined group of symbols includes frequency components that are uniquely different from the frequency components of all other symbols of the group to facilitate unique detection of each symbol.

The symbols X of the redundant message sequence are arranged such that if the first symbol sequence is m symbols long and each symbol is selected from a symbol group of n unique symbols (each symbol being denoted by the subscript i, i ═ 1, 2.. times., n), then each symbol at a corresponding position within the second symbol sequence is selected as the symbol of the predetermined symbol group [ i + j (mod n)]Where j is a constant integer value, referred to herein as an "offset value". For example, if the predetermined symbol group contains (X)₁，X₂，...，X₇) Seven symbols in order, the first message sequence being X₁X₅X₇And the offset j equals 2, the second sequence is represented by the symbol X₃X₇X₂And (4) forming.

An advantageous embodiment of a method for detecting a message a formatted as in fig. 9 and included in a continuous message stream is now described with reference to fig. 3 and 4. In step 34, based on the pair synchronization symbol S_ync1 and S_ync2, the symbol sequence of message a is selected. If the two synchronization symbols and all the message information symbols of the two sequences are detected and each symbol of the second sequence has the correct offset j with respect to its corresponding symbol in the first sequence, the message a is considered to be detected and assigned the highest message detection quality data value M_MAX. Then, at step 46, message A is stored and/or transmitted, whichWith or without M_MAX。

If, however, none of the symbols of message a are detected and/or none of the symbols of the message information have the correct offset value, then the process proceeds to step 40. Referring also to fig. 4, at step 50 of step 40, it is determined whether at least one of the two synchronization symbols and all of the message information symbols have been detected and all of the latter exhibit the correct offset. If so, a subset of detected messages A is assigned message detection quality data M_iIndicating that its likelihood of correct detection is less than the maximum value but high enough to warrant the validation process. According to data M_iThe process proceeds to step 42.

If, as described above, the subset of symbols of message a does not satisfy the first set of criteria at step 50, it is evaluated under the second set of criteria at step 54. Under a second set of criteria, the subset of symbols of message a may still be qualified for the acknowledgement process if two synchronization symbols are detected and all but one of the message information symbols are detected. That is, if all symbol detections and offsets are present (except that one of the message information symbols is not present or cannot exhibit the correct offset), then message A is designated with message detection quality data M_jIndicating that its likelihood of correct detection is less than a maximum value, but still high enough to warrant the validation process.

In this embodiment, message B is preferably (but not exclusively) selected as shown in fig. 5 or shown. Message B is M at step 42 only at its assigned message detection merit data_MAXAnd then certified as acceptable. That is, message B is only qualified if all of its symbols are detected (i.e., both synchronization symbols and all of its message information symbols) and all of its message information symbols have the correct offset.

If message B is thus based on its message detection quality data M_MAXIf it is certified, the information content of message B is compared with the information content or visual representation of message A in step 44The contents of the two are compared to check whether they are the same. If so, the message A is considered to be acknowledged and its message information content is stored and/or transmitted, with or without its message detection quality data M_iOr M_j。

Although the invention has been described with reference to a particular arrangement of parts, features and the like, these are not intended to exhaust all possible arrangements or features, and indeed many other modifications and variations will be apparent to those skilled in the art.

Claims (30)

1. A method for detecting data included in audio media data as a continuous stream of encoded messages, the method comprising:

detecting predetermined message data representing predetermined messages of said continuous stream of encoded messages;

generating message detection quality data representing an accuracy with which the detected predetermined message data represents the information content of the predetermined message, the accuracy representing an eligibility of the detected predetermined message data with respect to the information content of the predetermined message, when the detected predetermined message data satisfies a predetermined eligibility criterion; and

confirming correct detection of the predetermined message based on the message detection quality data.

2. The method of claim 1, wherein detecting the predetermined message data comprises detecting at least some message symbols of the predetermined message.

3. A method as claimed in claim 2, comprising generating message information data representing the information content of the predetermined message in dependence on the at least some message symbols.

4. The method of claim 2, wherein the predetermined message comprises a plurality of chronologically arranged message symbols including the at least some message symbols of the predetermined message.

5. The method of claim 2, wherein detecting the predetermined message data comprises detecting a first synchronization symbol and a second synchronization symbol in the predetermined message.

6. The method of claim 5, wherein the first synchronization symbol and the second synchronization symbol in the predetermined message are separate and different from each other.

7. The method of claim 2, wherein detecting the predetermined message data comprises detecting message symbols in the predetermined message, the message symbols characterizing audio media data.

8. The method of claim 2, wherein detecting the predetermined message data comprises detecting a first message symbol and a second message symbol in the predetermined message.

9. The method of claim 2, wherein the generation of the message detection merit data is based on the reception of synchronization symbols and message symbols in the predetermined message.

10. A method as claimed in claim 1, comprising detecting further predetermined message data representing further predetermined messages of the continuous stream of encoded messages; and generating further message detection quality data representing an accuracy with which said further predetermined message data represents an information content of said further predetermined message, and wherein confirming correct detection of said predetermined message is based on said further predetermined message data and said further message detection quality data.

11. The method of claim 10, wherein confirming correct detection of the predetermined message comprises matching the predetermined message data with the further predetermined message data.

12. The method of claim 10, comprising detecting a message symbol of the predetermined message, wherein the message symbol characterizes audio media data, and detecting a further message symbol in the further predetermined message, wherein the further message symbol in the further predetermined message characterizes audio media data.

13. The method of claim 12, wherein each of the first message symbol of the predetermined message and the first message symbol of the further predetermined message includes a frequency component different from that of the other symbols and represents the same information.

14. The method of claim 10, wherein the message detection merit data and the further message detection merit data represent an accuracy of detection of the predetermined message data and the further predetermined message data, respectively.

15. The method of claim 10, including said generating message information data representing information content of said predetermined message based on predetermined message data; generating further message information data representing the information content of the further predetermined message on the basis of the further predetermined message data, and confirming correct detection of the predetermined message on the basis of the further message information data.

16. A system for detecting data included in audio media data as a continuous stream of encoded messages, comprising:

detecting means for detecting predetermined message data representing predetermined messages of said continuous stream of encoded messages;

quality data generating means for generating message detection quality data representing an accuracy with which the detected predetermined message data represents the information content of the predetermined message when the detected predetermined message data satisfies a predetermined eligibility criterion, the accuracy representing that the detected predetermined message data is eligible for the information content of the predetermined message; and

-confirming means for confirming correct detection of said predetermined message based on said message detection quality data.

17. A system as claimed in claim 16, wherein said detecting means is arranged to detect at least some of the message symbols of said predetermined message.

18. A system as claimed in claim 17, comprising means for generating message information data representing the information content of the predetermined message from the at least some message symbols.

19. The system of claim 17, wherein the predetermined message comprises a plurality of chronologically arranged message symbols including the at least some message symbols of the predetermined message.

20. The system of claim 17, wherein the detecting means is operable to detect a first synchronization symbol and a second synchronization symbol in the predetermined message.

21. The system of claim 20, wherein the first and second synchronization symbols in the predetermined message are separate and different from each other.

22. The system of claim 17, wherein said detecting means is operable to detect a message symbol in said predetermined message, the message symbol being characteristic of audio media data.

23. The system of claim 17, wherein the detecting means is operable to detect a first message symbol and a second message symbol in the predetermined message.

24. A system as claimed in claim 17, wherein said quality data generating means is arranged to generate said message detection quality data in response to receipt of synchronisation symbols and message symbols in said predetermined message.

25. A system as claimed in claim 16, wherein said detecting means is arranged to detect further predetermined message data representing further predetermined messages of the continuous stream of encoded messages; said quality data generating means being arranged to generate further message detection quality data representing the accuracy with which said further predetermined message data represents the information content of said further predetermined message; and wherein said confirming means is arranged to confirm correct detection of said predetermined message based on said further predetermined message data and said further message detection quality data.

26. The system of claim 25, wherein said means for validating matches said predetermined message data with said additional predetermined message data.

27. The system of claim 25, wherein said detecting means is operable to detect a message symbol of said predetermined message, wherein the message symbol characterizes audio media data; and detecting a further message symbol in the further predetermined message, wherein the further message symbol in the further predetermined message characterizes the audio media data.

28. The system of claim 27, wherein each of the first message symbol of the predetermined message and the first message symbol of the further predetermined message includes a frequency component different from that of the other symbols and represents the same information.

29. The system of claim 25, wherein the message detection merit data and the further message detection merit data represent an accuracy of detection of the predetermined message data and the further predetermined message data, respectively.

30. A system according to claim 25, comprising means for generating message information data representing the information content of the predetermined message from the predetermined message data and further message information data representing the information content of the further predetermined message from the further predetermined message data, and the confirming means confirms correct detection of the predetermined message from the further message information data.