System and method for automatic segmentation and identification of repeating objects from an audio stream

[0001] This application claims the benefit of a previously filed provisional patent application Ser. No. 60/319,290 filed on Jun. 1, 2002.

[0002] 1. Technical Field

[0003] The invention is related to identification of repeating objects or music in an audio stream, and in particular, to a system and method for jointly segmenting and identifying repeating objects from one or more broadcast audio streams.

[0004] 2. Related Art

[0005] There are many existing schemes for identifying audio objects such as particular advertisements, station jingles, or songs embedded in an audio stream. For example, several such audio identification schemes are referred to as “audio fingerprinting” schemes. Typically, audio fingerprinting schemes take a known audio object, and reduce that object to a set of parameters, such as, for example, frequency content, energy level, etc. These parameters, or “fingerprints,” are then stored in a database of known objects. Sampled portions of the streaming audio are then compared to the fingerprints in the database for identification purposes.

[0006] Consequently, such schemes typically rely on a comparison of the audio stream to a large database of previously identified audio objects. In operation, such schemes often sample the audio stream over a desired period using some sort of sliding window arrangement, and compare the sampled data to the database in order to identify potential matches. In this manner, individual objects in the audio stream can be identified. This identification information is typically used for any of a number of purposes, including segmentation of the audio stream into discrete objects, or generation of play lists or the like for cataloging the audio stream, or gathering statistics on the stream. However, as the size of the fingerprint database increases, it becomes increasingly computationally expensive to identify matching audio objects in the audio stream.

[0007] Further, many existing audio identification schemes require accurate registration at the beginning and end of the audio object being identified. Consequently, such schemes tend to work poorly in real world environments such as broadcast radio stations, where songs are often foreshortened, cross-faded with other songs at the beginning and endpoints, or corrupted by voiceovers, station identifiers, or other noise.

[0008] Therefore, what is needed is a computationally efficient system and method for identifying and segmenting audio objects, such as songs, station identifiers, jingles, advertisements, emergency broadcast signals, etc., from an audio stream such as a broadcast radio or television signal. Further, such a system and method should be robust in real-world type environments where the endpoints of audio objects are unknown, corrupted, or otherwise noisy.

[0009] A “repeating object extractor” as described herein automatically segments and identifies audio objects such as songs, station identifiers, jingles, advertisements, emergency broadcast signals, etc., in an audio stream comprised of repeating and non-repeating audio objects. Unlike conventional schemes, instead of trying to segment the audio stream into audio objects first, and then attempting to identify the segments, the repeating object extractor performs a joint segmentation and identification of the stream. This joint segmentation and identification provides a computationally efficient technique identifying and segmenting audio objects in an audio stream, even in an environment where the endpoints of audio objects are unknown or corrupted by voiceovers, cross-fading, or other noise.

[0010] In general, an audio stream is captured using conventional methods from an audio or audio/video broadcast via radio, television, the Internet, or other network, then either saved to a computer readable medium, or buffered for a period of time, typically several minutes or longer, sufficient to allow for semi real-time identification of repeating objects within the audio stream. The audio stream, either buffered or read from a stored location is then processed in segments, or windows. While discrete windows can be used, the use of overlapping or sliding windows to segment the audio stream for analysis provides better results. In either case, when processing a segment of the audio stream, it is assumed that the segment represents a part of one of the entries in a preexisting database of audio objects.

[0011] The segment is first filtered or processed to provide a vector of at least one representative parameter for characterizing the segment. Note that this vector of parameters continues to evolve as a function of time. In particular, so long as the computed parameters are approximately constant, it is assumed that contiguous windows of the audio stream represent a part of the same audio object. Conversely, discontinuities in the computed parameters are assumed to correspond to approximate audio object boundaries. As a result, the vector of characteristic parameters represents one or more contiguous segments of the audio stream.

[0012] A first comparison pass against the database then serves to eliminate as many of the entries as possible from further consideration, while returning other audio objects which represent potential matches. Once this has been done, more complex comparison methods are used to check the segment or segments against each of the possible matching entries in the database. Consequently, the approach described herein represents an easy-to-hard refinement approach to narrow the search of the database.

[0013] In particular, in processing the audio stream a set of at least one filter, which produces representative information about the window or data currently being processed, is applied to the audio stream. Thus, given a number of filters, an output vector including elements for each filter is produced for one or more contiguous windows of the audio stream. In other words, given one or more windows of the audio stream, the set of at least one filter produces a vector of outputs comprised of characteristic information which represents the audio data in those windows. This output vector is then used to identify potential audio object matches.

[0014] As is well known to those skilled in the art, there are a large number of conventional frequency, time, and energy-based techniques for comparing the similarity of audio objects. For example, the elements representing the output vector for song-type audio objects includes, but is not limited to, information, such as, for example, beats per minute (BPM), energy occupancy of various frequency bands, zero-crossings, etc., as estimated or calculated over each current window.

[0015] Once the output vector has been computed, it is passed to the database to determine whether any existing entries are possible matches. When potentially matching entries are located in the database, more detailed information regarding each potentially matching entry is provided for further comparison and analysis in order to help make a positive identification and segmentation of a portion of the audio stream. In particular, when the initial search identifies possible candidates that approximately match the output vector, a more detailed “match vector” of information for each possibly matching audio object is returned for a comparison to the target portion of the audio stream. This match vector contains information such as, for example, a low-dimension version of the audio object, its duration, and other pertinent quantities, such as, for example, title and artist information.

[0016] For each match vector a cross-correlation of the low-dimension version of the audio object is performed with the appropriate portion of audio from the audio stream. A high correlation denotes a match, with the peak of the correlation providing alignment information, that, when considered with the audio object duration information, allows for a more exact determination of the likely boundaries of the audio object in the stream.

[0017] In one embodiment, the match vector for each possible match is compared against the target segment or segments of the audio stream in order of decreasing probability of match until a match is identified. Performing comparisons in decreasing probability of match serves to decrease overall computation time and thus increases overall system efficiency. Several factors are used in assigning a probability of match. For example, higher probabilities are assigned to those match vectors that correspond to closer matches to output vector in the aforementioned initial comparison. In addition, in another embodiment, prior information, such as the most recently identified audio objects from the same audio stream, is used to modify match vector probabilities. For example, if a song of one genre was the most recently identified, it is more probable that a song of the same genre is being played. Consequently, a higher probability will be assigned to possible song matches of the same genre than to possible song matches of different genres.

[0018] In one embodiment, once a positive match has been found, the search terminates, the segmentation is completed, and the audio object is stored along with its meta-data. Alternately, the starting and ending points of the audio object within the audio stream is stored in a file or database so that the audio object can be accessed as desired, or so that statistics regarding audio object play can be maintained.

[0019] If an identified audio object has already been stored it need not be stored again. However, if the existing stored copy is imperfect, for example being cropped or marred in some way, such as by crossfading, voiceovers, or other noise, the newly identified copy is stored in its place if it is better. Alternately, in another embodiment, each copy, or pointers to the location of each copy in the audio stream are stored individually. In still another embodiment, two or more copies of an audio object are combined to produce an improved version of the audio object. For example, if a stored copy of a particular song is cropped (e.g., missing some seconds at the beginning and end) and there is a voiceover on part of it, a second copy of the song is used in one embodiment to produce an improved version of the song using conventional audio processing techniques.

[0020] In addition to the just described benefits, other advantages of the system and method for automatically identifying and segmenting audio objects in an audio stream will become apparent from the detailed description which follows hereinafter when taken in conjunction with the accompanying drawing figures.

[0025] In the following description of the preferred embodiments of the present invention, reference is made to the accompanying drawings, which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention.

[0026] FIG. 1 illustrates an example of a suitable computing system environment 100 on which the invention may be implemented. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100.

[0027] The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held, laptop or mobile computer or communications devices such as cell phones and PDA's, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

[0028] The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices. With reference to FIG. 1, an exemplary system for implementing the invention includes a general-purpose computing device in the form of a computer 110.

[0029] Components of computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The system bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

[0030] Computer 110 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data.

[0031] Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computer 110. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media.

[0032] Note that the term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media.

[0033] The system memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS), containing the basic routines that help to transfer information between elements within computer 110, such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120. By way of example, and not limitation, FIG. 1 illustrates operating system 134, application programs 135, other program modules 136, and program data 137.

[0034] The computer 110 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, FIG. 1 illustrates a hard disk drive 141 that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive 151 that reads from or writes to a removable, nonvolatile magnetic disk 152, and an optical disk drive 155 that reads from or writes to a removable, nonvolatile optical disk 156 such as a CD ROM or other optical media.

[0035] Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive 141 is typically connected to the system bus 121 through a non-removable memory interface such as interface 140, and magnetic disk drive 151 and optical disk drive 155 are typically connected to the system bus 121 by a removable memory interface, such as interface 150.

[0036] The drives and their associated computer storage media discussed above and illustrated in FIG. 1, provide storage of computer readable instructions, data structures, program modules and other data for the computer 110. In FIG. 1, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146, and program data 147. Note that these components can either be the same as or different from operating system 134, application programs 135, other program modules 136, and program data 137. Operating system 144, application programs 145, other program modules 146, and program data 147 are given different numbers here to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer 110 through input devices such as a keyboard 162 and pointing device 161, commonly referred to as a mouse, trackball or touch pad.

[0037] Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, radio receiver, or a television or broadcast video receiver, or the like. These and other input devices are often connected to the processing unit 120 through a user input interface 160 that is coupled to the system bus 121, but may be connected by other interface and bus structures, such as, for example, a parallel port, game port or a universal serial bus (USB). A monitor 191 or other type of display device is also connected to the system bus 121 via an interface, such as a video interface 190. In addition to the monitor, computers may also include other peripheral output devices such as speakers 197 and printer 196, which may be connected through an output peripheral interface 195.

[0038] The computer 110 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. The remote computer 180 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer 110, although only a memory storage device 181 has been illustrated in FIG. 1. The logical connections depicted in FIG. 1 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

[0039] When used in a LAN networking environment, the computer 110 is connected to the LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet. The modem 172, which may be internal or external, may be connected to the system bus 121 via the user input interface 160, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer 110, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 1 illustrates remote application programs 185 as residing on memory device 181. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

[0040] The exemplary operating environment having now been discussed, the remaining part of this description will be devoted to a discussion of the program modules and processes embodying a system and method for automatically identifying and segmenting audio objects such as songs, station identifiers, jingles, advertisements, emergency broadcast signals, etc., in an audio stream.

[0041] A “repeating object extractor” as described herein automatically jointly segments and identifies audio objects such as songs, station identifiers, jingles, advertisements, emergency broadcast signals, etc., in an audio stream comprised of repeating and non-repeating audio objects. Unlike conventional schemes, instead of trying to segment the audio stream into audio objects first, and then attempting to identify the segments, the repeating object extractor performs a joint segmentation and identification of the stream.

[0042] Audio objects in an audio stream, such as a radio broadcast, are often corrupted by voice-overs at the beginning and/or end point of each object. Further, such objects are frequently foreshortened, i.e., they are not played completely from the beginning or all the way to the end. Additionally, such objects are often intentionally distorted. For example, audio broadcast via a radio station is often processed using compressors, equalizers, or any of a number of other time/frequency effects. Further, audio objects, such as music or a song, broadcast on a typical radio station are often cross-faded with the preceding and following music or songs, thereby obscuring the audio object start and end points, and adding distortion or noise to the object. Such manipulation of the audio stream is well known to those skilled in the art. Finally, it should be noted that any or all of such corruptions or distortions can occur either individually or in combination.

[0043] The joint segmentation and identification of audio objects, as described herein, provides a computationally efficient technique for jointly identifying and segmenting audio objects in an audio stream, even in an environment where the endpoints of audio objects are unknown or corrupted by voiceovers, cross-fading, or other noise.

[0044] The system and method described herein for automatically identifying and segmenting songs, music, and other audio objects in an audio stream provides many advantages, including, for example, the ability to automatically identify audio objects in one or more audio streams, the ability to store either all identified audio objects, or to store only desirable audio objects or content from the audio stream, the ability to identify targeted audio objects for special processing, the ability to de-noise, or otherwise clear up any multiply detected audio object, or the ability to select or reject specific audio objects for listening, saving, or special processing.

[0045] In general, an audio stream is first captured using conventional methods from an audio or audio/video broadcast via radio, television, the Internet, or other network. Once captured, the audio stream is then either saved to a computer readable medium, or buffered for a period of time, typically several minutes or longer, sufficient to allow for semi real-time identification of audio objects within the audio stream. The audio stream, either buffered or read from a stored location, is then processed in segments, or windows. While discrete windows can be used, the use of overlapping or sliding windows to segment the audio stream for analysis tends to provide better identification results. In either case, when processing a segment of the audio stream, it is assumed that the segment represents a part of one of the entries in a preexisting database of audio objects.

[0046] Each segment of the audio stream is filtered or processed to provide a vector of at least one representative parameter for characterizing the segment. Note that this vector of parameters continues to evolve as a function of time. In one embodiment, so long as the computed parameters are approximately constant, it is assumed that contiguous windows of the audio stream represent a part of the same audio object. Conversely, discontinuities in the computed parameters are assumed to correspond to approximate audio object boundaries. As a result, the vector of characteristic parameters, i.e., the “output vector,” represents one or more contiguous segments of the audio stream.

[0047] A first comparison pass, or query, against the database then serves to eliminate as many of the entries as possible from further consideration, while returning other audio objects that represent potential matches to the output vector. Once this has been done, more complex comparison methods are used to check the segment or segments against each of the possible matching entries in the database. Consequently, the approach described herein represents an easy-to-hard refinement approach to narrow the search of the database.

[0048] As noted above, the object database contains parametric information for characterizing each known audio object. Further, also as noted above, this parametric information is used to identify potential audio object matches. In addition, the object database contains more detailed information for each known audio object for use in making detailed comparisons between each potential match and the audio windows or segments from the audio stream that are being analyzed.

[0049] As discussed below in Section 2.3, the parametric information includes elements representing the output vector. For example, assuming that the audio object represents a song, then the parametric information includes elements such as, for example, beats per minute (BPM), energy occupancy of various frequency bands, zero-crossings, etc., as estimated or calculated over each current window. Also as discussed in Section 2.4, the detailed information comprises a “match vector” G_i, which contains information such as, for example, a low-dimension version of the audio object, its duration, and other pertinent quantities, such as title and artist information.

[0050] Given each of these information types, i.e., parametric and detailed, the database performs some or all of the functions discussed below in accordance with the alternate embodiments described herein. First, the database receives an output vector, F_j for the portion of the audio stream currently being analyzed and determines which audio objects are possible matches. Second, in response to receipt of the output vector F_j, the database provides vectors G_i for each potential match to allow for joint identification and segmentation of the audio object from the audio stream. Third, in further embodiments, the database maintains popularity statistics such as how often particular audio objects are identified or played, the times that particular objects were played, etc. Further, in one embodiment, the G_i vectors are provided in order of decreasing likelihood, with the most popular or probable audio objects being provided first for the detailed comparison.

[0051] In alternate embodiments, for each known or previously identified audio object, the parametric information and the more detailed information, i.e., the match vector, are separated into one or more separate databases, which in further alternate embodiments reside either on a local client computer, or on a remote server computer that is accessible via conventional network or Internet protocols. The use of separate databases provides several advantages. For example, separate databases for different music genres are maintained in one embodiment, thereby reducing search and comparison times when interested in particular genres.

[0052] Further, the use of remote databases comprised of parametric and detailed information for very large numbers of audio objects is useful for identifying audio objects when local storage of such databases would be prohibitive due to space constraints. In addition, use of such a remote database provides a central database that needs only be updated once for use by multiple clients rather than individually for each client. Remote database queries involving interaction between clients and servers is well known to those skilled in the art, and will not be addressed here. In addition, for clarity of discussion, a single database will be referred to throughout this discussion as including both the parametric information for each known object, and the detailed information for object comparisons.

[0053] In view of the preceding discussion, it is clear that interaction with the database can take several forms. For example, in one embodiment, the entire database is located on a remote server that is accessible to one or more clients using conventional communications protocols. In another embodiment, at least part of the database is located locally on a client computer, and whenever an audio object cannot be identified locally, a query to a remote database is made. In a related embodiment, the match vectors, G_i, are added to the local database whenever they are fetched from one or more remote databases, thereby augmenting the local database. Note that in this case, the parametric information for audio objects that are identified in the audio stream is either provided from the remote database and stored locally, or it is computed directly from the identified audio objects and stored locally for later use in identifying other repeat copies of the audio objects. In still another related embodiment, periodic updates are fetched from one or more remote databases to augment the usefulness of the local database.

[0054] Finally, in still another embodiment, one or more local or remote databases maintain parametric information and at least partial match vectors, G_i, for unidentified audio objects. While unidentified audio objects can not be positively identified using this information, the information is still useful for identifying repeat instances of an audio object. As noted above, where more then one copy of an audio object such as a song is available, the multiple copies can be used for determining and storing a better copy, correcting imperfections in one or more copies of the audio object, or simply keeping statistics on the number of occurrences and time of play for the unidentified repeat objects.

[0055] Further, in a related embodiment, any audio which can not be automatically identified is stored on a computer readable medium. In this embodiment, a user interface for accessing and manually identifying the unidentified audio is provided. This user interface allows a user to manually segment portions of the audio stream, and provide any additional detailed information available to the user such as audio object title and artist information. In addition, once manually segmented by the user, the duration of the audio object is easily computed from the manually segmented object by simply determining the length of the segmented audio data. Given this information, the manually identified audio object is then treated the same as an automatically identified object. Further, the parametric and detailed information for characterizing the manually identified audio object is then made available to the object database for use in future automatic identifications of repeat instances of the manually identified audio object.

[0056] Once the audio stream has been sampled and filtered as described above, parametric information for characterizing the current window or windows of the audio stream is computed and used in a database query or search to identify potential object matches with previously identified probable objects. The purpose of the database query is simply to determine whether a portion of the audio stream comprising one or more segments or windows of the audio stream is approximately the same as a known or previously identified audio object.

[0057] In particular, processing the audio stream begins by applying a set of at least one filter to the current window of the stored or buffered audio stream. This set of filters provides a suite of algorithms for targeting particular aspects of the audio stream for producing representative information about the window or segment currently being processed. In other words, given K filters, there is vector of representative outputs F_j=(f_j0, f_j1, f_j2, . . . , f_jK−1), for the j^th window of the audio stream. Thus, for any given window or group of contiguous windows of the audio stream, the set of at least one filter produces a vector of outputs comprised of characteristic information that represents the audio data for that portion of the audio stream. This output vector is then used to identify potential audio object matches by checking the database for potential matches.

[0058] As noted above, the aforementioned suite of algorithms for targeting particular aspects of the audio stream employs one or more filters or algorithms for computing parametric information useful for identifying audio objects in the audio stream. This parametric information includes parameters that are useful for identifying particular audio objects, and thus, the type of parametric information computed is dependent upon the type of audio object being sought. As is well known to those skilled in the art, there are a large number of conventional frequency, time, and energy-based techniques that are useful for comparing the similarity of audio objects. For example, the elements representing the output vector for a song-type audio object includes, but is not limited to, information, such as, for example, beats per minute (BPM), energy occupancy of various frequency bands, zero-crossings, etc., as estimated or calculated over each current window or segment.

[0059] There are various ways of computing an approximate BPM. For example, in a working example of the repeating object extractor, the audio stream is filtered and down-sampled to produce a lower dimension version of the original stream. In a tested embodiment, filtering the audio stream to produce a stream that contains only information in the range of 0-220 Hz was found to produce good BPM results. However, it should be appreciated that any frequency range can be examined depending upon what information is to be extracted from the audio stream. Once the stream has been filtered and down-sampled, a search is then performed for dominant peaks in the low rate stream using autocorrelation of windows of approximately 10-seconds at a time, with one or more of the largest peaks being retained as BPM data for use in the initial comparison to audio objects in the database. Note that in one embodiment, spurious BPM numbers are eliminated using median filtering.

[0060] As noted above, once computed, the output vector is passed to the database to determine which, if any, entries are possible matches. For example, when identifying songs in an audio stream, assuming element f_j0 represents BPM, and that for the current window f_j0=112.7 and has been approximately constant (i.e., f_j−10=f_j−20= . . . =112.7) for a period of 3.4 minutes, than all songs in the database that do not have approximately this BPM, for at least that measured duration, are not considered to be potential matches. Conversely, those entries that do have a BPM of approximately 112.7, for at approximately 3.4 minutes, are considered to be potential matches, and are returned for further comparison as described in detail below. Similarly, when the output vector, F_j, contains other elements, i.e., energy occupancy of various frequency bands, zero-crossings, etc., each of these elements is used to further thin the list of possible or potential matches. It is also possible that F_j consists of elements that do not have simple physical interpretations.

[0061] Note that in alternate embodiments, the number of potential matches returned by the database query is limited to a desired maximum in order to reduce system overhead. Further, a similarity threshold for comparison of current window or segment of the audio stream with objects in the database is adjustable via a user interface in order to either increase or decrease the likelihood of identifying potential matches. This serves to either limit or increase the number of possible matches returned from the database. In yet another related embodiment, those objects found to repeat more frequently within an audio stream are weighted more heavily so that they are more likely to be identified as a potential match than those objects that repeat less frequently. In still another embodiment, if too many potential matches are returned by the database search, then the similarity threshold is increased so that fewer potential matches are returned.

[0062] In another embodiment, if the search for potential matches in the database provide potential match which is sufficiently close to the output vector, F_j, then that potential match will be considered to be an actual match, and the more detailed comparison to the other potential matches will not be performed.

[0063] In general, once the potential matches to the portion of the audio stream currently being analyzed have been returned by the database, a more detailed comparison between the current portion of the audio stream and one or more of the potential matches are performed to more positively identify the current portion of the audio stream. In general, this detailed comparison involves performing a cross-correlation of the current portion of the audio stream with one or more of the potentially matching audio objects returned from the object database. This detailed comparison is described in further detail below. At this point, if the current portion of the audio stream is found to match one of the potential matches, it is identified and the extents of the audio object within the audio stream are determined based on the cross-correlation and an alignment of the current portion of the audio stream with the matching audio object, along with the duration data provided by the match vector. Once the extents of the audio object have been determined, the audio object is simply extracted from the audio stream and saved to an individual file as noted above. Alternately, once the extents of the audio object are known, the position of the audio object within the stream is saved to the database.

[0064] In particular, when the initial search, i.e., the initial object comparisons, identifies possible candidates that approximately match the output vector, a vector G_i is returned for each possible match in the database. This “match vector,” G_i contains information such as, for example, a low-dimension version of the audio object, the duration of the audio object, and other pertinent quantities such as title and artist information. Note that both F_j (the output vector), and G_i (the match vector), are generally small vectors in comparison with the size of an audio object, even when the audio object is stored in a compressed format.

[0065] For each match vector, G_i, a cross-correlation of the low-dimension version of the audio object is performed with the appropriate section of audio from the audio stream which has been filtered or otherwise processed to provide a corresponding low-dimension version of that portion of the audio stream. Note that in one embodiment, a cross-correlation between full-dimension versions of the known audio object and the current portion of the audio stream is performed. However, using full-dimension versions for comparison of the audio objects to the audio stream tends to provide less reliable results, especially where the audio stream has been corrupted by noise. In either case, a high correlation denotes a match, and provides alignment information, that, when considered with the audio object duration information, allows for a more exact determination of the boundaries of the audio object in the stream. Once a match is identified, and the boundaries determined, in alternate embodiments, the object or object location is stored, and statistics regarding play of the audio object are maintained.

[0066] In one embodiment, each G_i is compared against the target portion of the audio stream in order of decreasing probability of match until a match is identified. Thus, prior information, such as the most recently identified audio objects from the same audio stream, is used to decrease the computation required. For example if a song of one genre was the most recently identified it is more probable that a song of the same genre is currently being played. Consequently, a higher probability will be assigned to possible song matches of the same genre than to possible song matches of different genres. Similarly, if an advertisement was just identified in the audio stream, it is more probable that the next contiguous segment of the audio stream is also an advertisement.

[0067] In another embodiment, once a positive match has been found, the search terminates, the segmentation is completed, and the audio object is stored along with its meta-data. Alternately, the starting and ending points of the audio object within the audio stream is stored in a file or database so that the audio object can be accessed as desired. If an identified audio object has already been stored it need not be stored again. However, if the existing stored copy is imperfect, for example being cropped or marred in some way, such as by crossfading, voiceovers, or other noise, the newly identified copy is stored in place of the previously stored audio object, if it is determined to be a better, clearer, or more complete copy. Alternately, in still another embodiment, each copy, or pointers to the location of each copy in the audio stream are stored individually.

[0068] In still another embodiment, two or more copies of an audio object are combined to produce an improved version of the object. For example, if a stored copy of object S is cropped (missing some seconds at beginning and end) and there is a voiceover on part of it, a second copy S′ can be used to produce an improved version S_improved=f(S, S′) where f(.) involves some audio processing. The initial determination that S is imperfect is readily done by comparing it with S′. For example, it is difficult to determine whether a voiceover is a part of the song or not based merely on examining the audio data of S, but a comparison with another version of the song, i.e., S′, reveals parts that are not common to both. These parts are assumed to be noise or corruption such as voiceovers or crossfading.

[0069] In a further embodiment, if the detailed comparison shows that the current portion of the audio stream does not match any of the potential matches, it is identified as part of a new audio object in the database, and its position within the stream and parametric information is saved to the database as noted above. Alternately, as noted above, this unidentified audio is also made available to a user via a user interface for manual segmentation and identification. Note also that the extents of any such unknown or unidentified audio can be determined by identifying audio objects existing on either side of the unidentified audio within the stream. However, in still another embodiment, if the current window or segment is not identified, a new database search is made using a lower similarity threshold to identify additional audio objects for comparison. Again, if the current window or segment is identified, it is treated as described above; otherwise, it is added to the database as a new audio object, also as described above.

[0070] In one embodiment the vector G_i is a low dimension version of the database object computed using the Bark spectra decomposition (also known as critical bands). This decomposition is well known to those skilled in the art. This decomposes the signal into a number of different bands. Since they occupy narrow frequency ranges the individual bands can be sampled at much lower rates than the signal they represent. The vector G_i can consist of sampled versions of one or more of these bands. For example, in one embodiment the vector G_i consists of a sampled version of Bark band 7 which is centered at 840 Hz.

[0071] In another embodiment determining that the target portion of the audio stream matches an element in the database is done by calculating the cross-correlation of G_i (the low dimension version of the database object) with the low dimension version of the target portion of the audio stream. A peak in the cross correlation generally implies that two waveforms are approximately equal for at least a portion of their lengths. As is well know to those skilled in the art there are various techniques to avoid accepting spurious peaks. For example, if a particular local maximum of the cross-correlation is a candidate peak, we may require that the value at the peak is more than a threshold number of standard deviations higher than the mean in a window of values surrounding (but not necessarily including) the peak.

[0072] In yet another embodiment the extents of the found object is determined by aligning two or more copies of repeating objects. For example, once a match has been found (by detecting a peak in the cross-correlation) the low dimension version of the target portion of the audio stream and G_i (which is a low dimension version of a database entry) are aligned. The amount by which they are misaligned is determined by the position of the cross-correlation peak. One of the low dimension versions is then normalized so that their values approximately coincide. That is, if the target portion of audio is S, and it has been determined from the cross-correlation that G_i and S match with offset o, then S(t), where t is the temporal position within the audio stream, is compared with G_i(t+o). However a normalization may be necessary before S(t) is approximately equal to G_i(t+o). Next the beginning point of the object is determined by finding the smallest t_b such that S(t) is approximately equal to G_i(t+o) for t>t_b. Similarly the endpoint of the object is determined by finding the largest t_e such that S(t) is approximately equal to G_i(t+o) for t<t_e. Once this is done S(t) is approximately equal to G_i(t+o) for t_b<t<t_e and t_b and t_e can be regarded as the approximate endpoints of the object. In some instances it may be necessary to filter the low dimension versions before determining the endpoints.

[0073] In one embodiment, determining that S(t) is approximately equal to G_i(t+o) for t>t_b is done by a bisection method. A location to is found where S(t₀) and G_i(t₀+o) are approximately equal, and t₁ where S(t₁) and G_i(t₁+o) are not equal, where t₁<t₀. The beginning of the object is then determined by comparing small sections of S(t) and G_i(t+o) for the various values of t determined by the bisection algorithm. The end of the object is determined by first finding to where S(t₀) and G_i(t₀+o) are approximately equal, and t₂ where S(t₂) and G_i(t₂+o) are not equal, where t₂>t₀. Finally, the endpoint of the object is then determined by comparing sections of S(t) and G_i(t+o) for the various values of t determined by the bisection algorithm.

[0074] In still another embodiment, determining that S(t) is approximately equal to G_i(t+o) for t>t_b is done by finding to where S(t₀) and G_i(t₀+o) are approximately equal, and then decreasing t from to until S(t) and G_i(t+o) are no longer approximately equal. Rather than deciding that S(t) and G_i(t+o) are no longer approximately equal when their absolute difference exceeds some threshold at a single value of t, it is generally more robust to make that decision when their absolute difference has exceeded some threshold for a certain minimum range of values, or where the accumulated absolute difference exceeds some threshold. Similarly the endpoint is determined by increasing t from t₀ until S(t) and G_i(t+o) are no longer approximately equal.

[0075] The general system diagram of FIG. 2 illustrates the processes described above. In particular, the system diagram of FIG. 2 illustrates interrelationships between program modules for implementing a “repeating object extractor” for automatically identifying and segmenting songs, music, and other audio objects in an audio stream. It should be noted that the boxes and interconnections between boxes that are represented by broken or dashed lines in FIG. 2 represent alternate embodiments of the invention, and that any or all of these alternate embodiments, as described below, may be used in combination with other alternate embodiments that are described throughout this document.

[0076] In particular, as illustrated by FIG. 2, a system and method for automatically identifying and segmenting songs, music, and other audio objects in an audio stream begins by using an audio capture module 200 for capturing one or more audio streams containing audio information. The audio stream 205 is captured using any of a number of conventional techniques, such as, for example, an audio capture device connected to a computer for capturing a radio, television, Internet or other network audio broadcast stream. Such audio stream capture techniques are well known to those skilled in the art, and will not described herein. Once captured, the audio stream 205 is stored in a computer file or database, or buffered in an audio buffer 210 for a period of time, typically several minutes or longer, sufficient to allow for identification and segmentation of the audio stream as described above. In one embodiment, the audio stream 205 is also compressed by a compression module 215 using conventional audio compression techniques such as, for example, MPEG-3 compression.

[0077] An audio stream processing module 220 then begins examining the audio stream, either stored or buffered, 205 or 210, respectively. In particular, starting with the beginning of the audio stream, the audio stream processing module 220 begins providing segments or windows of the audio stream to a characterization module 225 for computing the parametric information comprising the output vector, F_j, as described above. In one embodiment, the length of each window or segment is adjustable. However, windows or segments on the order of about 20 seconds are typically used. In one embodiment so long as the output vector, F_j, is approximately constant from one segment to the next, it is assumed that contiguous segments or windows of the audio stream belong to the same audio object. As soon as a discontinuity is observed in the output vector, F_j, it is assumed that an audio object boundary or endpoint has been crossed, and the values of the output vector, F_j, prior to observing the discontinuity, are passed to a database query module 230 which then queries the object database 235 in order to identify potential matches to the portion of the audio stream being examined.

[0078] Note that exact matches are not required, or even expected, in order to identify potential matches during the database query. In fact, in one embodiment, a similarity threshold for performing this initial search for potential matches is used. This similarity threshold, or “detection threshold”, can be set to be any desired percentage match between one or more features of the output vector F_j, and the parametric information characterizing each of the potential matches. In another embodiment, if either no potential matches, or too few potential matches are identified, then the detection threshold is lowered in order to increase the number of potential matches identified by the database query module 230. Conversely, in still another embodiment, if too many potential matches are identified, then the detection threshold is raised so as to limit the number of comparisons performed. Further, in a related embodiment, if the percentage match between the output vector, F_j and the parametric information for characterizing any of the potential matches is sufficiently high, then that potential match will be considered to be an actual match, and the more detailed comparison to the other potential matches (i.e. module 240, as described below) will not be performed.

[0079] In another embodiment, every segment of the audio stream, 205 or 210, is used by the database query module 230 to query the object database 235. In this embodiment, as soon as the output vector, F_j, is computed for each segment by the characterization module 225, the output vector, F_j, is provided to the database query module 230 for querying the object database 235 to locate potential matches as described above. However, this embodiment is computationally more expensive, as more database queries are performed than the aforementioned embodiment where the output vector, F_j, represents multiple segments or windows of the audio stream 205 or 210. In addition, while still useful, because shorter portions of the audio stream 205 or 210 are used in this embodiment, it is more likely that erroneous or incorrect matches will be identified, and testing them will require additional computation.

[0080] Once one or more potential matches have been identified, the match vector, G_i, as described above, is returned from the object database 235 for each potential match. A detailed comparison module 240 then uses the match vector, G_i, to perform a detailed comparison between the portion of the audio stream being analyzed and one or more of the potentially matching objects. This detailed comparison includes either a direct comparison of the current portions of the audio stream and the potential matches, or a comparison between a lower-dimensional version of the current portion of the audio stream and the potential matches. As discussed above, this comparison typically involves a search for peaks in a cross-correlation between the current portion of the audio stream and a version of at least one audio object representing a potential match.

[0081] Next, once the detailed comparison module 240 has identified a match to the portion of the audio stream being analyzed, the detailed comparison module continues by aligning the portion of the audio stream being analyzed to the matching audio object using the cross-correlation peaks. The detailed comparison module then uses the duration information provided by the match vector, G_i, to identify the nominal extents of the identified audio object. In one embodiment, these extents are saved as endpoint information to the object database 235. In addition, in another embodiment, the occurrence of a match is also saved to the object database 235 for use in tracking statistical information for identified audio objects as described above. In an alternate embodiment, any identified audio objects 245 are stored to a computer readable medium for later use. Note that in a related embodiment, the stored identified audio objects 245 are compressed using the compression module 215.

[0082] In one embodiment, whenever any portion of the audio stream, 205 or 210, cannot be identified, those unidentified audio portions 250 are saved to a computer readable medium for later manual browsing, classification, or identification via a user interface module 255. In another embodiment, this user interface module 255 also provides for access to the stored identified audio objects 245, as well as allowing a user to manually identify or compare unknown or unidentified audio portions 250 to identified audio objects 245.

[0083] Finally, in still another embodiment, as described above, where two or more copies of an audio object such as a song have been identified, an audio object improvement module 260 is used to combine one or more versions of the audio object to produce an improved version of the audio object.

[0084] The processes described above are repeated, with the portion of the audio stream, 205 or 210, which is being analyzed by the characterization module 225 being incremented, such as, for example, by using a sliding window, or by moving the beginning of the window to the computed endpoint of the last identified audio object. These processes continue until such time as the entire audio stream has been examined, or until a user terminates the examination via the user interface module 255.

[0085] As noted above, the program modules described in Section 2.6 with reference to FIG. 2, and in view of the detailed description provided in Section 2, are employed in a “repeating object extractor” for automatically identifying and segmenting songs, music, and other audio objects in an audio stream. This process is depicted in the flow diagram of FIG. 3. It should be noted that the boxes and interconnections between boxes that are represented by broken or dashed lines in FIG. 3 represent alternate embodiments of the present invention, and that any or all of these alternate embodiments, as described below, may be used in combination.

[0086] Referring now to FIG. 3 in combination with FIG. 2, the process can be generally described as a repeating object extractor that locates, identifies and segments audio objects such as songs, music, station identifiers, jingles, and advertisements from an audio stream. In particular, as illustrated by FIG. 3, a system and method for automatically identifying and segmenting audio objects in an audio stream begins by capturing 300 an audio stream 205. The audio stream 205 is captured using any of a number of conventional techniques, such as, for example, an audio capture device connected to a computer for capturing a radio, television, Internet or other network audio broadcast stream. Such audio stream capture techniques are well known to those skilled in the art, and will not described herein. Once captured, the audio stream 205 is stored in a computer file or database, or buffered 210 for a period of time, usually several minutes, sufficient to allow for identification and segmentation of the audio stream as described above. In one embodiment, the audio stream 205 is compressed 305 using conventional audio compression techniques.

[0087] Once the audio stream has been captured or buffered, 205 or 210, respectively, parametric information describing the audio stream is computed 310. In particular, starting with the beginning of the audio stream 205 or 210, segments or windows of the audio stream are analyzed using a set of K filters to generate a vector of representative outputs F_j, as described above. As noted above, while the length of each window or segment is adjustable, windows or segments on the order of about 20 seconds are typically used in cases where the audio stream, 205 or 210, represents songs or music.

[0088] In one embodiment, so long as the output vector, F_j, is approximately constant 315 from one segment to the next, it is assumed that contiguous segments or windows of the audio stream belong to the same audio object and the window or segment is incremented 320 and F_j is recomputed 310 for the additional segment. Incrementing of the windows or segments continues until either the end of the audio stream, 205 or 210, is reached 325, or until a user terminates the operation. In other words, the portion of the audio stream, 205 or 210, for which F_j is being computed 310, grows as a function of time so long as F_j is approximately constant 315. As soon as a discontinuity is observed in the output vector, F_j, it is assumed that an audio object boundary or endpoint has been crossed. At this point, the values of the output vector, F_j, prior to observing the discontinuity, are used to query 330 the object database 235 in order to identify potential matches 335 to the portion of the audio stream being examined.

[0089] In yet another embodiment, every segment of the audio stream, 205 or 210, is used to query 330 the object database 235. In this embodiment, as soon as the output vector, F_j, is computed 310 for each segment, the output vector, F_j, is provided for querying 330 the object database 235 to locate potential matches as described herein. However, this embodiment is computationally more expensive, as more database queries 330 are performed than with the aforementioned embodiment where the output vector, F_j, represents multiple segments or windows of the audio stream 205 or 210. In addition, while still useful, because shorter portions of the audio stream 205 or 210 are used in this embodiment, it is more likely that erroneous or incorrect matches will be identified.

[0090] In another embodiment, the vector F_j for every segment of the audio stream, or for some subset of segments of the audio stream are added to the database to allow future identification of objects that repeat in the stream, but which are as yet not in the database.

[0091] In either case, as noted above, when querying 330 the object database 235, exact matches are not required, or even expected, in order to identify potential matches. In fact, in one embodiment, if either no potential matches 335, or too few potential matches are identified, then an adjustable similarity threshold is adjusted lower 340 in order to increase the number of potential matches identified by the database query 330. Conversely, in still another embodiment, if too many potential matches 335 are identified, then the similarity threshold is adjusted higher 340 so as to limit the number of detailed comparisons performed as described herein. However, in a related embodiment, in the event that exact, or nearly exact potential matches are identified between the output vector, F_j, and the parametric information for characterizing any of the potential matches, then that potential match will be considered to be an actual match, and the more detailed comparison to the other potential matches (i.e., detailed comparison 355, as described below) will not be performed.

[0092] In one embodiment, those portions of the audio stream for which no potential match is identified 335 are stored 345 in a file or database of unidentified audio data 250. As described herein, this unidentified audio data 250 can then be manually segmented, identified, or processed via a user interface. However, once one or more potential matches have been identified 335, the match vector, G_i, is returned from the object database 235 for each potential match. In another embodiment, these match vectors are sorted 350 in order of probability of match, such that those match vectors having a higher probability of match are compared to the portion of the audio stream being analyzed prior to those match vectors having a lower probability of match.

[0093] Given one or more potentially matching audio objects, a detailed comparison 355 between the current portions of the audio stream, 205 or 210, and one or more of the potentially matching objects is performed using the match vectors, G_i, for each potentially matching object. This detailed comparison 355 includes either a direct comparison of the current portions of the audio stream, 205 or 210, and the potential matches, or a comparison between a lower-dimensional version of the current portion of the audio stream and the potential matches. As discussed above, this comparison 355 typically involves a search for peaks in a cross-correlation between the current portion of the audio stream and a version of at least one audio object representing a potential match.

[0094] When identifying matches, this detailed comparison 355 also aligns the portion of the audio stream being analyzed to the matching audio object using the cross-correlation peaks. This alignment allows the duration information provided by the match vector, G_i, to be used to identify the nominal extents of the identified audio object. Consequently, in one embodiment, once an object match has been identified 358 and its nominal extents determined by the detailed comparison 355, the extents are saved as endpoint information to the object database 235. In another embodiment, the occurrence of a match 358 is also saved to the object database 235 for use in tracking statistical information for identified audio objects as described above. Further, once the nominal extents of the identified audio object are determined during the detailed comparison 355, the identified audio object is extracted from the audio stream and saved 360 to a computer readable file or database 245 for later use. Note that in a related embodiment, the stored identified audio objects 245 are compressed 365 using conventional audio compression techniques.

[0095] Further, in still another embodiment, whenever the detailed comparison 355 fails to identify any portion of the audio stream, 205 or 210, those unidentified audio portions are stored 345 to a computer readable file or database 250 for later manual browsing, classification, segmentation or identification 370 via a user interface. In addition, in still another embodiment, whenever the detailed comparison 355 fails to identify any portion of the audio stream, 205 or 210, the similarity threshold 340 is adjusted, and a new database query 330 is performed in an attempt to identify additional potentially matching audio objects.

[0096] In still another embodiment, as described above, where two or more copies of an audio object such as a song have been identified, the multiple copies of the audio object are processed 375 to combine one or more versions of the audio object to produce an improved version of the audio object. The improved version is then used to replace one or more of the previously saved versions of the audio object 245.

[0097] Finally, as noted above, the aforementioned processes are repeated, while the portion of the audio stream, 205 or 210, which is being examined, is repeatedly incremented 320 until such time as the entire audio stream has been examined 325, or until a user terminates the examination.

[0098] As noted above, audio streams captured for purposes of segmenting and identifying audio objects in the audio stream can be derived from any conventional broadcast source, such as, for example, an audio or audio/video broadcast via radio, television, the Internet, or other network. With respect to a combined audio/video broadcast, as is typical with television-type broadcasts, it should be noted that the audio portion of the combined audio/video broadcast is synchronized with the video portion. In other words, as is well known, the audio portion of an audio/video broadcast coincides with the video portion of the broadcast. Consequently, identifying repeating audio objects within the combined audio/video stream is a convenient and computationally inexpensive way to identify repeating video objects within the audio/video stream.

[0099] In particular, in one embodiment, by first identifying repeating audio objects in the audio stream, identifying the times t_b and t_e at which those audio objects begin and end (i.e., the endpoints of the audio object), and then segmenting the audio/video stream at those times, video objects are also identified and segmented along with the audio objects from the combined audio/video stream. For example, a typical commercial or advertisement is often seen to frequently repeat on any given day on any given television station. Recording the audio/video stream of that television station, then processing the audio portion of the television broadcast will serve to identify the audio portions of those repeating advertisements. Further, because the audio is synchronized with the video portion of the stream, the location of repeating advertisements within the television broadcast can be readily determined in the manner described above. Once the location is identified, such advertisements can be flagged for any special processing desired.

[0100] The foregoing description of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.