Message reconstruction from partial detection

nwa wmn ϊν ιηηκ

MESSAGE RECONSTRUCTION FROM PARTIAL DETECTION 9671/18 WO 03/024016 PCT/US02/27323 -1 -

Title Of Invention

Message Reconstruction From Partial Detection

Background Of The Invention [0001] The present invention relates to methods and systems foraccurately detecting encoded data included in audio media data.

[0002] There is considerable interest in encoding audio signals for usein audience measurement. In order to estimate what an audience is listeningto at a particular time, a listener’s environment Is monitored for audio signalsat regular intervals. If the detected audio signals contain an identificationcode, the message may then be quickly identified.

[0003] Based upon the receipt of identified messages, the rating orpopularity of various broadcasts may be estimated. Therefore, it is veryimportant to accurately determine which encoded audio signals have beenreceived.

[0004] However, the acoustic characteristics of differing audioenvironments may vary greatly. As a result, rates for successfully receivingand identifying audio signals in the differing environments can varysignificantly. Some environments for instance, may be quite hostile to theaccurate detection of encoded messages because there is a large amount ofnoise or interference. There may also be circumstances in which theencoded message may not be detected because of a dropout in the code. Inthese cases, only a portion of the identification code may be received. WO 03/024016 PCT/US02/27323 -2- [0005] Therefore, a system is desired with reduced sensitivity to theacoustic environment, which can detect a code in as many differingcircumstances as possible despite hostile acoustic conditions.

[0006] A system is also desired that can accurately identify thedetection of an encoded message, even if only a portion of the message hasbeen received or detected.

Summary Of The Invention [0007] For this application the following terms and definitions shall apply: [0008] The term “data” as used herein means any indicia, signals,marks, symbols, domains, symbol sets, representations, and any otherphysical form or forms representing information, whether permanent ortemporary, whether visible, audible, acoustic, electric, magnetic,electromagnetic or otherwise manifested; [0009] The term “audio media data” as used herein means any datarepresenting or constituting audible sounds and which is widely accessiblewhether over-the-air, or via cable, satellite, network, internetwork (includingthe internet), distributed on storage media, or otherwise; [0010] The term "message symbol” as used herein means a unit ofdata selected from a predefined symbol set to constitute part of a messagecontained in data included in audio media data; [ooii] The term “continuing stream of encoded messages" meansencoded messages arranged in a predetermined time or spatial sequence,whether the sequence is continuous or interrupted; WO 03/024016 PCT/US02/27323 -3- [0012] The term “processor" as used herein means processingdevices, apparatus, programs, circuits, systems and subsystems, whetherimplemented in hardware, software or both, and includes both individual unitsand groups of units; [0013] The term “produce" as used herein with respect to data meansto retain existing data for further processing as well as to derive new databased on pre-existing data, and: [0014] The terms “first", “second" and “further” are used todistinguish one element, set, data, object or thing from another, and are notused to designate relative position or arrangement in time.

[0016] In accordance with one aspect of the invention, a method is provided for detecting data included in audio media data as a continuingstream of encoded messages. The method comprises detectingpredetermined message data representing a predetermined message of thecontinuing stream of encoded messages; producing message detection meritdata representing an assigned accuracy of the detected predeterminedmessage data as correctly representing an information content of thepredetermined message; and confirming correct detection of thepredetermined message based on the message detection merit data.

[0016] In accordance with another aspect of the present invention, asystem is provided for detecting data included in audio media data as acontinuing stream of encoded messages. The system comprises detectingmeans for detecting predetermined message data representing apredetermined message of the continuing stream of encoded messages; meritdata producing means for producing message detection merit datarepresenting an assigned accuracy of the detected predetermined messagedata as correctly representing an information content of the predetermined WO 03/024016 PCT/US02/27323 -4- message; and confirming means for confirming correct detection of thepredetermined message based on the message detection merit data.

[0017] The invention and its particular features and advantages willbecome more apparent from the following detailed description considered withreference to the accompanying drawings.

Brief Description Of The Drawings [0018] FIGURE 1 is a functional block diagram illustrating a system inaccordance with one embodiment ofthe present invention. ·<· [0019] FIGURE 2 is a block diagram illustrating an embodiment of thesystem of Figure 1.

[0020] FIGURE 3 is a flow diagram illustrating one mode of operationof the systems of Figures 1 and 2.

[0021] FIGURE 4 is a flow diagram illustrating an implementation ofone process of Figure 3.

[0022] FIGURES 5 through 8 are graphs illustrating continuingstreams of encoded messages.

[0023] FIGURE 9 is a graph illustrating an advantageous format of amessage included in a continuing stream of encoded messages.

Detailed Description Of Certain Advantageous Embodiments [0024] Figure 1 is a functional block diagram illustrating anadvantageous embodiment of a system 30 for detecting data included inaudio media data as a continuing stream of encoded messages. In certainembodiments, the continuing stream of encoded messages includes data WO 03/024016 PCT/USO2/27323 -5- useful in audience measurement, commercial verification, royalty calculationsand the like. Such data typically includes an identification of a program,commercial, file, song, network, station or channel, or otherwise describessome aspect of the media audio data or other data related thereto, so that itcharacterizes the audio media data. In certain embodiments, the continuingstream of encoded messages is comprised of symbols arranged time-sequentially in the audio media data.

[0026] The system 30 comprises an audio media data input 2 fordetecting data included in audio media data as a continuing stream ofencoded messages. The audio media data input 2 can be either a singledevice, stationary at a source to be monitored, or multiple devices, stationaryat multiple sources to be monitored. Alternatively, the audio media data input2 can be a portable monitoring device that can be carried by an individual tomonitor multiple sources as the individual moves about.

[0026] Where the audio media data is acoustic data, the audio mediadata input 2 typically would be a microphone having an input which receivesaudio media data in the form of acoustic energy and which serves totransduce the acoustic energy to electrical data. Where audio media data inthe form of light energy, is monitored, the audio media data input 2 takes theform of a light-sensitive device, such as a photodiode. The audio media datainput 2 can also take the form of a magnetic pickup for sensing magneticfields associated with a speaker, a capacitive pickup for sensing electric fieldsor an antenna for electromagnetic energy. In still other embodiments, theaudio media data input 2 takes the form of an electrical connection to amonitored device, which may be a television, a radio, a cable converter, asatellite television system, a game playing system, a VCR, a DVD player, aportable player, a computer, a web appliance, or the like. In still furtherembodiments, the audio media data input 2 is embodied in monitoringsoftware running on a computer or other reproduction system to gather mediadata. WO 03/024016 PCT/US02/27323 -6- [002η A symbol sequence evaluation subsystem 4 receives inputdata from audio media data input 2. The symbol sequence evaluationsubsystem 4 processes the input data to detect the presence of symbolswhich may represent encoded messages included in audio media data as acontinuing stream of encoded messages. For example, the symbols may bedetected in accordance with any of the techniques disclosed in U.S. PatentNo. 5,764,763 to Jensen et al., U.S. Patent No. 5,450,490 to Jensen et al.,U.S. Patent No. 5,579,124 to Aijala et al., U.S. Patent No. 5,581,800 toFardeau et al., U.S. Patent No. 5,319,735 to Preuss et al., U.S. Patent No.6,175,627 to Petrovich et al., U.S. Patent No. 5,828,325 to Wolosewicz et al.,U.S. Patent No. 6,154,484 to Lee et al., U.S. Patent No. 5,945,932 to Smith etal., PCT applications WO 00/04662 to Srinivasan, WO 98/26529 to Lu et al.,WO 96/27264 to Lu et al., WO 99/59275 to Lu et al., and U.S. patentapplication No. 09/318,045 to Neuhauser, et al., all of which hereby areincorporated by reference herein.

[0028] A storage device 6 is optionally provided to store data. It maybe desired to store the data produced by the symbol sequence evaluationsubsystem 4 for later use. In addition, an optional data transfer device 8 isprovided, if desired, to transmit data from the symbol sequence evaluationsubsystem 4 to a remote location, such as a central monitoring station 10,which has an accompanying information library 12. The data produced by thesymbol sequence evaluation subsystem 4 may be transferred to the centralmonitoring station 10 as a continuous or a continuing stream of data.Alternatively, the data produced by the symbol sequence evaluationsubsystem 4 may be stored in storage device 6 for time shiftedcommunications with the central monitoring station 10. The information library12 accessible by the central monitoring station 10 may be utilized for instance,to produce identification data for the audio media data based on theinformation content of the received messages. WO 03/024016 PCT/US02/27323 -7- [0029] Figure 2 is a block diagram illustrating an advantageousimplementation 100 of the system 30. The system 100 comprises an audiomedia data input 2 for data, which may include audio media data having acontinuing stream of encoded messages therein. The audio media data input2 may take any of the forms described in connection with Figure 1 above.

[0030] System 100 includes a message processor 14 which serves toprocess the received data in the same manner as subsystem 4 of Figure 1described more fully in connection with Figure 3 below, to detect continuingstreams of messages included in the received data.

[0031] Storage device 16 has been provided to store detectedsymbols which comprise the messages, as well as message information datarepresenting the information content of the messages, and message detectionmerit data representing an assigned accuracy of the message informationdata or a likelihood that it is correct, all produced by the message processor 14. The message information data and the message detection merit datamay later be used to confirm the detection of a predetermined message.Communications device 18 has been provided in order to communicate datafrom the message processor 14 to the central monitoring station 10 with itsaccompanying information library 12. The data communicated bycommunications device 18 includes confirmed or unconfirmed messageinformation data with or without message detection merit data communicatedat the time of detection from message processor 14 as a continuous orcontinuing stream of data. Alternatively, the data communicated bycommunications device 18 includes confirmed or unconfirmed messageinformation data with or without message detection merit data communicatedfrom storage device 16.

[0032] Figure 3 illustrates one mode of operation of the systems 30and 100 to detect a message A of a continuing stream of encoded messagesincluded in audio media data wherein each message comprises a plurality of WO 03/024016 PCT/US02/27323 -8- message symbols. From the stream of messages, a symbol sequence isexamined at 34 to detect the presence of a message in a predeterminedformat, labeled “message A” for convenience herein. The symbol sequencemay be selected for examination in any of a number of different ways. In oneembodiment, each group of S sequential symbols or data which potentiallycould correspond thereto based on the length or duration of the data, isexamined in the step 34. In an alternative embodiment, a group of Ssequential symbols or data which could correspond thereto is selected basedon a prior detection of one or more other messages in the sequence. In afurther embodiment the detection of a symbol characterizing a known positionin a message symbol sequence, such as a synchronization symbol, is used toselect the data to be examined in step 34.

[0033] Since the message A has a predetermined format, in carryingout the step 34 the systems 30 and 100 are able to rely not only on detectionof the individual symbols but also on the message format in determiningwhether a message has been fully detected. If, for example, message A iscomposed of S sequential symbols Xi, X2, ...Xs, of which Xi is asynchronization symbol, the step 34 may be carried out. on the condition thatthe synchronization symbol Si has been detected. Then the positions of theremaining symbols are known and their presence or absence determined.

[0034] If all of the symbols of the message A have been detected, the sequence of symbols in message A are assigned a highest messagedetection merit data value Mmax. representing a maximum likelihood thatmessage A has been detected, and are stored and/or transferred 46 asmessage information data representing an information content of themessage A, with or without the data Mmax, for further processing.

[0035] If not all of the symbols of message A are detected, but thosethat were detected constitute a qualified subset of the message A, determinedat 40, then the system produces message information data representing an WO 03/024016 PCT/US02/27323 -9- apparent information content of message A, whether partial or complete, andthe qualified subset message A is subjected to a confirmation process insteps 42 and 44.

[0036] The determination 40 that the detected symbols constitute aqualified subset of the message A, is made based on predefined qualificationrules. Satisfaction of a given rule in step 40 by message A causes the system30 or 100 to assign message detection merit data M to message A indicatingthat the likelihood of its correct detection is less than 100%, but sufficientlyhigh that message A may be deemed detected subject to confirmation.

[003η In one embodiment, the detection of at least a predeterminedminimum number of the symbols of message A constitutes a qualification rule.In another embodiment, the detection of an uninterrupted sequence ofsymbols having at least a predetermined minimum length serves as aqualification rule. In a further embodiment, the detection of one or morepredetermined synchronization symbols of message A, together with apredetermined number of message information symbols serves as aqualification rule.

[0038] In still other embodiments, combinations of two or more of theforegoing qualification rules are employed, and satisfaction of any of severalqualification rules or sets of rules, qualifies the detected symbol subset forconfirmation in steps 42 and 44. A process for carrying out the step 40 byapplying two qualification rules or criteria is illustrated in Figure 4, whereinsatisfaction of either of the two rules or criteria qualifies the detected symbolsubset. In a step 50, a first set of rules or criteria are applied to the symbolsubset. If the symbol subset satisfies these rules or criteria, the message A isassigned message detection merit data Mi and processing continues to step 42. If not, processing instead continues in a step 54 in which a second set ofrules or criteria are applied to the symbol subset. If the symbol subsetsatisfies the second set of rules or criteria, even if the first set is not satisfied, WO 03/024016 PCT/US02/27323 -10- the message A is assigned message detection merit data Mj, different from Mi,and the symbol subset is nevertheless deemed qualified for confirmation andprocessing continues to step 42.

[0039] In step 42, the system 30 or 100 determines whether one ormore detected messages B of the stream of messages qualify to confirm thedetection of message A represented by the qualified subset of symbols.

[0040] In certain embodiments, the message B is selected as themessage immediately following the message A in the continuing stream ofmessages, as illustrated in Figure 5. in certain other embodiments, themessage B is selected as the message immediately preceding the message Aas illustrated in Figure 6. In still other embodiments, both the message ·immediately preceding the message A and the message immediatelyfollowing message A are used .to confirm a qualified subset of the message A.

[0041] In further embodiments, the message B precedes themessage A to be confirmed by two or more message intervals, as illustratedin Figure 7. In still further embodiments, the message B follows the messageA by two or more message intervals, as illustrated in Figure 8. In yet stillfurther embodiments, both such messages are used to confirm the qualifiedsubset of message A. Various combinations of three or more messages arealso used in still more embodiments to confirm the qualified subset ofmessage A.

[0042] In order to qualify for confirmation in step 42 of Figure 3, themessage or messages B must satisfy one or more predetermined criteria. Incertain embodiments, for a message to quality for confirmation all of itssymbols must be detected. However, in other embodiments, a detection offewer than all of the symbols of a message may still qualify it for confirmation,so long as its message information is reliably established and/or it is only oneof several confirming messages. WO 03/024016 PCT/US02/27323 -11- [0043] The system 30 or 100 produces message information datarepresenting an apparent information content of message B, whether partialor complete, along with message detection merit data representing anassigned accuracy thereof. The message detection merit data of message Bfor confirmation purposes may be simply a binary symbol, but need not be.

[0044] If the message or messages B qualify to confirm the subset ofA, a matching step 44 is carried out in order to confirm the apparentinformation content ofthe subset of A. in certain embodiments, the messageor messages B must possess the same information content as the apparentcontent of the subset of A. In other embodiments in which the data isformatted so that a given information content of the message or messages Bimplies a different, but known information content ofthe message A, thecorrespondence ofthe apparent information content of the message A to suchdifferent but known information content confirms the subset of message A.

[0045] From the foregoing it will be seen that in the embodiment theconfirmation ofthe message information data of message A depends on (1)the existence of a qualified subset of message A, as represented by itsmessage detection merit data, (2) the qualification of message B to confirmmessage A, as represented by its message detection merit data, and (3) amatch of the message information data of message A with that of message B.

[0046] In other embodiments, the message information data ofmessage A is confirmed based only on its message detection merit data. Forexample, where a number of symbols of message A necessary to establish itsinformation content have been detected, message A may be deemedconfirmed based only on message detection merit data indicating a highprobability that the message detection merit data is accurate.

[0047] Once a qualified subset of message A has been confirmed instep 44, data representing its Information content with or without its message WO 03/024016 PCT/USO2/27323 -12- detectlon merit data M, Mi or Mj is stored and/or transferred in step 46 forfurther processing.

[0048] In certain advantageous embodiments, the process of Figure3 is modified, so that both, (i) the symbols of messages A and B are detectedand, (ii) their respective message detection merit data are produced, in amonitoring system at a user location. This monitoring system is either astationary device or a portable device carried by an audience member. Thedetected symbols and their respective message detection merit data areeither communicated to a system which carries out steps 40,42 and 44 ofFigure 3, or else stored for subsequent communication to such a system.

[0049] An embodiment of the invention is now described for use indetecting a continuing stream of encoded messages having a format asdisclosed in US patent application No. 09/318,045 hereby incorporated byreference herein. As illustrated in Figure 9, each such message is formattedas two redundant sequences of message information symbols X having twosynchronization symbols, Sync 1 and Sync 2, interspersed therewith. Thesymbols Sync 1 and Sync 2 are distinct from one another, so that eachrepresents a determinable position within the message symbol sequence.

The message information symbols X are selected from a predeterminedsymbol set of n symbols in which the symbols are arranged in a predefinedsequence, conveniently designated by an index i assigned to each symbolsuch that i = 1,2,.... n. For example, the predefined symbol set may havethree distinct symbols, so that n=3. However, n may be selected as anypositive integer greater than 1 in this exemplary message format. Preferably,but not necessarily, each symbol in the predefined symbol set includesfrequency components that are uniquely different from those of all othersymbols of the set, in order to facilitate the unique detection of each symbol.

[0050] The symbols X of the redundant message sequences arearranged so that if the first symbol sequence is m symbols long, and each WO 03/024016 PCT/US02/27323 -13- symbol is selected from a symbol set of n unique symbols each designated byan index i, i=1,2,.... n, each symbol in a corresponding position within thesecond symbol sequence is selected as the symbol [i + j (mod n)] of thepredefined symbol set, where j is a constant integer value referred to hereinas an “offset”. For example, if the predefined symbol set contains sevensymbols in the order (Xi, X2,.... X7), the first message sequence is X1X5X7,and the offset j=2, then the second sequence is composed of the symbolsX3X7X2.

[0061] An advantageous embodiment of a method for detecting amessage A formatted as in Figure 9 and included in a continuing stream ofmessages, is now described with reference to Figures 3 and 4. In step 34,the symbol sequence of message A is selected based on detection of at leastone of the synchronization symbols Sync 1 and Sync 2. If both of thesynchronization symbols are detected along with all of the messageinformation symbols of both sequences, and each symbol of the secondsequence has the correct offset j with respect to its corresponding symbol inthe first sequence, then message A is deemed detected and assigned ahighest message detection merit data value Mmax· Then the message A isstored and/or transferred in step 46 with or without Mmax.

[0052] However, if any of the symbols of message A is not detectedand/or any of the message information symbols does not have the correctoffset, processing continues in step 40. With reference also to Figure 4, instep 50 of step 40, it is determined whether at least one of the twosynchronization symbols and all of the message information symbols havebeen detected, with all of the latter exhibiting the correct offset. If so, thedetected subset of message A is assigned message detection merit data Miindicating that the likelihood of its correct detection is less than maximum butsufficiently high to warrant confirmation processing. Based on data Mi, theprocessing continues in step 42. WO 03/024016 PCT/US02/27323 -14- [0053] if the symbol subset of message A does not satisfy the first set of criteria in step 50 as described above, it is evaluated under a second set ofcriteria in step 54. Under the second set of criteria, the symbol subset ofmessage A can still qualify for confirmation processing if both synchronizationsymbols have been detected as well as ail but one of the messageinformation symbols. That is, if all symbol detections and offsets are present,except that one of the message information symbols either is absent or fails toexhibit the correct offset, then message A is assigned message detectionmerit data Mj indicating that the likelihood of its correct detection is less thanmaximum but still sufficiently high to warrant confirmation processing.

[0054] in this embodiment, message B preferably, but notexclusively, is selected as in Figure 5 or Figure 6. Message B qualifies in step42 only if its assigned message detection merit data is Mmax- That is,message B qualifies for confirmation only if all of its symbols have beendetected (i.e., both synchronization symbols and all message informationsymbols) and all of its message information symbols have the correct offset.

[0055] If message B thus qualifies based on its message detectionmerit data Mmax, then in step 44 the information content of message B iscompared with the information content or apparent content of message A todetect whether they are the same. If so, the message A is deemed confirmedand its message information content is stored and/or transferred with orwithout its message detection merit data Mi or Mj.

[0056] Although the invention has been described with reference to aparticular arrangement of parts, features and the like, these are not intendedto exhaust all possible arrangements or features, and indeed many othermodification and variation will be ascertainable to those of skill in the art. , crnxan rwzn ατα inia^n pnow pnizn irn nr “jaoa,ρνιη ηχΒ- laoana ma™ nairmaa np’ioz .ZTLWan ™·Ώ3 Πΐρ^ΠΠ ΡΠΊ31? QXn“3 □ιηπη by vr.SB0**3

Atg2)Q9 10:212) 4Q2:CD

<img img-format="tif" img-content="drawing" file="IL159373AD00021.tif" id="idf0001" />

.(mcna navin) cra^’an nwa