Note: Descriptions are shown in the official language in which they were submitted.
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
TITLE: Methods and Systems for Arranging and Searching a Database of
Media Content
Recordings
BACKGROUND
[0001] Media content identification from environmental samples is a
valuable and
interesting information service. User-initiated or passively-initiated content
identification of
media samples has presented opportunities for users to connect to target
content of interest
including music and advertisements.
[0002] Content identification systems for various data types, such as
audio or video, use
many different methods. A client device may capture a media sample recording
of a media
stream (such as radio), and may then request a server to perform a search of
media recordings
(also known as media tracks) for a match to identify the media stream. For
example, the
sample recording may be passed to a content identification server module,
which can perform
content identification of the sample and return a result of the identification
to the client device.
A recognition result may then be displayed to a user on the client device or
used for various
follow-on services, such as purchasing or referencing related information.
Other applications
for content identification include broadcast monitoring, for example.
[0003] Existing procedures for ingesting target content into a database
index for
automatic content identification include acquiring a catalog of content from a
content provider
or indexing a database from a content owner. Furthermore, existing sources of
information to
return to a user in a content identification query are obtained from a catalog
of content prepared
in advance.
1
CA 02905385 2017-01-05
SUMMARY
[0004] Certain exemplary embodiments can provide a method comprising:
receiving a
sample of media content; performing, by a computing device, a content
recognition of the
sample of media content using a data structure including a concatenation of
representations for
each of a plurality of media content recordings; and determining an
identification of the sample
of media content based on a mapping between a sound identifier for a
respective media content
recording and a global position in the data structure that corresponds to a
given representation
of the respective media content recording that matches a portion of the sample
of media
content.
[0005] Certain exemplary embodiments can provide a non-transitory
computer readable
medium having stored therein instructions, that when executed by a computing
device, cause
the computing device to perform functions comprising: receiving a sample of
media content;
performing a content recognition of the sample of media content using a data
structure
including a concatenation of representations for each of a plurality of media
content recordings;
and determining an identification of the sample of media content based on a
mapping between
a sound identifier for a respective media content recording and a global
position in the data
structure that corresponds to a given representation of the respective media
content recording
that matches a portion of the sample of media content.
[0006] Certain exemplary embodiments can provide a system comprising: at
least one
processor; and data storage configured to store instructions that when
executed by the at least
one processor cause the system to perform functions comprising: receiving a
sample of media
content; performing a content recognition of the sample of media content using
a data structure
including a concatenation of representations for each of a plurality of media
content recordings;
and determining an identification of the sample of media content based on a
mapping between
a sound identifier for a respective media content recording and a global
position in the data
structure that corresponds to a given representation of the respective media
content recording
that matches a portion of the sample of media content.
2
CA 02905385 2017-01-05
100101
The foregoing summary is illustrative only and is not intended to be in any
way
limiting. In addition to the illustrative aspects, embodiments, and features
described above,
further aspects, embodiments, and features will become apparent by reference
to the figures
and the following detailed description.
3
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
BRIEF DESCRIPTION OF THE FIGURES
[0011] Figure 1 illustrates one example of a system for identifying
content within a data
stream and for determining information associated with the identified content.
[0012] Figure 2 shows a flowchart of an example method for performing
content
recognitions.
[0013] Figure 3 illustrates a diagram of an example method to form a
concatenation of
representations of media content recordings.
[0014] Figure 4 shows a flowchart of an example method for providing a
database of
concatenated media content recordings.
[0015] Figure 5 shows a flowchart of an example method for performing a
content
recognition of a received sample of media content.
[0016] Figure 6 is a diagram that conceptually illustrates performing a
content
recognition.
4
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
DETAILED DESCRIPTION
[0017] In the following detailed description, reference is made to the
accompanying
figures, which form a part hereof In the figures, similar symbols typically
identify similar
components, unless context dictates otherwise. The illustrative embodiments
described in the
detailed description, figures, and claims are not meant to be limiting. Other
embodiments may
be utilized, and other changes may be made, without departing from the spirit
or scope of the
subject matter presented herein. It will be readily understood that the
aspects of the present
disclosure, as generally described herein, and illustrated in the figures, can
be arranged,
substituted, combined, separated, and designed in a wide variety of different
configurations, all
of which are explicitly contemplated herein.
[0018] Referring now to the figures, Figure 1 illustrates one example of
a system for
identifying content within a data stream and for determining information
associated with the
identified content. While Figure 1 illustrates a system that has a given
configuration, the
components within the system may be arranged in other manners. The system
includes a media
or data rendering source 102 that renders and presents content from a media
stream in any
known manner. The media stream may be stored on the media rendering source 102
or
received from external sources, such as an analog or digital broadcast. In one
example, the
media rendering source 102 may be a radio station or a television content
provider that
broadcasts media streams (e.g., audio and/or video) and/or other information.
The media
rendering source 102 may also be any type of device that plays or audio or
video media in a
recorded or live format. In an alternate example, the media rendering source
102 may include a
live performance as a source of audio and/or a source of video, for example.
The media
rendering source 102 may render or present the media stream through a
graphical display, audio
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
speakers, a MIDI musical instrument, an animatronic puppet, etc., or any other
kind of
presentation provided by the media rendering source 102, for example.
[0019] A client device 104 receives a rendering of the media stream from
the media
rendering source 102 through an input interface 106. In one example, the input
interface 106
may include antenna, in which case the media rendering source 102 may
broadcast the media
stream wirelessly to the client device 104. However, depending on a form of
the media stream,
the media rendering source 102 may render the media using wireless or wired
communication
techniques. In other examples, the input interface 106 can include any of a
microphone, video
camera, vibration sensor, radio receiver, network interface, etc. The input
interface 106 may be
preprogrammed to capture media samples continuously without user intervention,
such as to
record all audio received and store recordings in a buffer 108. The buffer 108
may store a
number of recordings, or may store recordings for a limited time, such that
the client device
104 may record and store recordings in predetermined intervals, for example,
or in a way so
that a history of a certain length backwards in time is available for
analysis. In other examples,
capturing of the media sample may be caused or triggered by a user activating
a button or other
application to trigger the sample capture.
[0020] The client device 104 can be implemented as a portion of a small-
form factor
portable (or mobile) electronic device such as a cell phone, a wireless cell
phone, a personal
data assistant (PDA), tablet computer, a personal media player device, a
wireless web-watch
device, a personal headset device, an application specific device, or a hybrid
device that include
any of the above functions. The client device 104 can also be implemented as a
personal
computer including both laptop computer and non-laptop computer
configurations. The client
device 104 can also be a component of a larger device or system as well.
6
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
[0021] The client device 104 further includes a position identification
module 110 and a
content identification module 112. The position identification module 110 is
configured to
receive a media sample from the buffer 108 and to identify a corresponding
estimated time
position (Ts) indicating a time offset of the media sample into the rendered
media stream (or
into a segment of the rendered media stream) based on the media sample that is
being captured
at that moment. The time position (Ts) may also, in some examples, be an
elapsed amount of
time from a beginning of the media stream. For example, the media stream may
be a radio
broadcast, and the time position (Ts) may correspond to an elapsed amount of
time of a song
being rendered.
[0022] The content identification module 112 is configured to receive the
media sample
from the buffer 108 and to perform a content identification on the received
media sample. The
content identification identifies a media stream, or identifies information
about or related to the
media sample. The content identification module 112 may be configured to
receive samples of
environmental audio, identify a content of the audio sample, and provide
information about the
content, including the track name, artist, album, artwork, biography,
discography, concert
tickets, etc. In this regard, the content identification module 112 includes a
media search
engine 114 and may include or be coupled to a database 116 that indexes
reference media
streams, for example, to compare the received media sample with the stored
information so as
to identify tracks within the received media sample. The database 116 may
store content
patterns that include information to identify pieces of content. The content
patterns may
include media recordings such as music, advertisements, jingles, movies,
documentaries,
television and radio programs. Each recording may be identified by a unique
identifier (e.g.,
sound ID). Alternatively, the database 116 may not necessarily store audio or
video files for
7
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
each recording, since the sound IDs can be used to retrieve audio files from
elsewhere. The
database 116 may yet additionally or alternatively store representations for
multiple media
content recordings as a single data file where all media content recordings
are concatenated end
to end to conceptually form a single media content recording, for example. The
database 116
may include other information (in addition to or rather than media
recordings), such as
reference signature files including a temporally mapped collection of features
describing
content of a media recording that has a temporal dimension corresponding to a
timeline of the
media recording, and each feature may be a description of the content in a
vicinity of each
mapped timepoint. For more examples, the reader is referred to U.S. Patent No.
6,990,453, by
Wang and Smith, which is hereby entirely incorporated by reference.
[0023] The database 116 may also include information associated with
stored content
patterns, such as metadata that indicates information about the content
pattern like an artist
name, a length of song, lyrics of the song, time indices for lines or words of
the lyrics, album
artwork, or any other identifying or related information to the file. Metadata
may also
comprise data and hyperlinks to other related content and services, including
recommendations,
ads, offers to preview, bookmark, and buy musical recordings, videos, concert
tickets, and
bonus content; as well as to facilitate browsing, exploring, discovering
related content on the
world wide web.
[0024] The system in Figure 1 further includes a network 118 to which the
client device
104 may be coupled via a wireless or wired link. A server 120 is provided
coupled to the
network 118, and the server 120 includes a position identification module 122
and a content
identification module 124. Although Figure 1 illustrates the server 120 to
include both the
position identification module 122 and the content identification module 124,
either of the
8
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
position identification module 122 and/or the content identification module
124 may be
separate entities apart from the server 120, for example. In addition, the
position identification
module 122 and/or the content identification module 124 may be on a remote
server connected
to the server 120 over the network 118, for example.
[0025] The server 120 may be configured to index target media content
rendered by the
media rendering source 102. For example, the content identification module 124
includes a
media search engine 126 and may include or be coupled to a database 128 that
indexes
reference or known media streams, for example, to compare the rendered media
content with
the stored information so as to identify content within the rendered media
content. The
database 128 (similar to database 116 in the client device 104) may
additionally or alternatively
store multiple media content recordings as a single data file where all the
media content
recordings are concatenated end to end to conceptually form a single media
content recording.
A content recognition can then be performed by compared rendered media content
with the data
file to identify matching content using a single search. Once content within
the media stream
have been identified, identities or other information may be indexed in the
database 128.
[0026] In some examples, the client device 104 may capture a media sample
and may
send the media sample over the network 118 to the server 120 to determine an
identity of
content in the media sample. In response to a content identification query
received from the
client device 104, the server 120 may identify a media recoding from which the
media sample
was obtained based on comparison to indexed recordings in the database 128.
The server 120
may then return information identifying the media recording, and other
associated information
to the client device 104.
[0027] Figure 2 shows a flowchart of an example method 200 for performing
content
9
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
recognitions. Method 200 shown in Figure 2 presents an embodiment of a method
that, for
example, could be used with the system shown in Figure 1, for example, and may
be performed
by a computing device (or components of a computing device) such as a client
device or a
server or may be performed by components of both a client device and a server.
Method 200
may include one or more operations, functions, or actions as illustrated by
one or more of
blocks 202-204. Although the blocks are illustrated in a sequential order,
these blocks may also
be performed in parallel, and/or in a different order than those described
herein. Also, the
various blocks may be combined into fewer blocks, divided into additional
blocks, and/or
removed based upon the desired implementation.
[0028] It should be understood that for this and other processes and
methods disclosed
herein, flowcharts show functionality and operation of one possible
implementation of present
embodiments. In this regard, each block may represent a module, a segment, or
a portion of
program code, which includes one or more instructions executable by a
processor for
implementing specific logical functions or steps in the process. The program
code may be
stored on any type of computer readable medium or data storage, for example,
such as a storage
device including a disk or hard drive. The computer readable medium may
include non-
transitory computer readable medium or memory, for example, such as computer-
readable
media that stores data for short periods of time like register memory,
processor cache and
Random Access Memory (RAM). The computer readable medium may also include non-
transitory media, such as secondary or persistent long term storage, like read
only memory
(ROM), optical or magnetic disks, compact-disc read only memory (CD-ROM), for
example.
The computer readable media may also be any other volatile or non-volatile
storage systems.
The computer readable medium may be considered a tangible computer readable
storage
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
medium, for example.
[0029] In addition, each block in Figure 2 may represent circuitry that
is wired to
perform the specific logical functions in the process. Alternative
implementations are included
within the scope of the example embodiments of the present disclosure in which
functions may
be executed out of order from that shown or discussed, including substantially
concurrent or in
reverse order, depending on the functionality involved, as would be understood
by those
reasonably skilled in the art.
[0030] At block 202, the method 200 includes receiving a sample of media
content. As
one example, a computing device may receive the sample of media content from
an ambient
environment of the computing device, such as via a microphone, receiver, etc.,
and may record
and store the sample. In another example, the computing device may receive the
sample of
media content from another computing device (e.g., one computing device
records the sample
and sends the sample to a server).
[0031] At block 204, the method 200 includes performing a content
recognition of the
sample of media content using a data file including a concatenation of
representations for each
of a plurality of media content recordings. The concatenation may include a
plurality of
respective representations (e.g., fingerprints or set of fingerprints) per
media content recording
and arranged in sequential time order per media content recording in the data
file. A
representation for a given media content recording may include a set of
fingerprints determined
or extracted at respective landmark positions within the given media content
recording, and
each fingerprint corresponds to a global position within the data file. The
data file also may
have associated identifiers per groupings of representations (e.g., per sets
of fingerprints) for
each of the plurality of media content recordings. In an example where the
media content
11
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
recordings include songs, the identifiers may include any of a title of a
song, an artist, genre,
etc.
[0032] In one example, the content recognition can be performed by
determining a
representation in the data file that matches to a portion of the sample of
media content, and then
to identify a mapping between the matching portion in the data file and an
identifier for a
respective media content recording. The mapping may be between a global
position of the
representation in the data file and the identifier.
[0033] Thus, within examples, the content recognition may be performed by
identifying
within the data file a substantially matching representation to a respective
representation of the
sample of media content, and then determining a global position in the data
file corresponding
to the substantially matching representation. The representations for each of
the plurality of
media content recordings in the data file have associated global starting
positions within the
data file so as to segment a global timeline of the data file according to the
plurality of media
content recordings. A global starting position in the data file associated
with the substantially
matching representation at the determined global position can also be
identified. The method
200 may also include determining a local position within a given media content
recording
corresponding to the sample of media content based on the global position and
the global
starting position.
[0034] Within examples, using the method 200, a large database of media
recordings
may be searched using a single bucket (instead of separate buckets indexed by
a sound ID) to
obtain enhanced recognition performance with simplified data processing
structures. Existing
search techniques may process search data by separating matching data into
different buckets,
and each bucket corresponds to a distinct target object. Within examples
herein, it may be
12
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
more efficient not to distribute data into separate buckets, but rather to
process un-separated
data in a single bulk operation. By performing a single search operation of a
received sample
of media content into a database for content recognition, overhead processing
due to
distribution and tracking of bucket indices and iterating over buckets may be
removed. Thus,
within examples, a method of aggregating searches in which one bulk operation
carried out on
a single concatenated media content recording may be more efficient than a
number of small
operations.
Example Database Setup
[0035] In some examples, a reference database of media content recordings
to use to
identify unknown media content may include a concatenation of representations
of all known
media content recordings into a single concatenated media recording file that
has a single
concatenated timeline, in which associated identifiers may not be directly
referenced in the file.
Each media content recording can be represented as being located along the
concatenated
timeline at a given position, and boundaries of the recordings can be stored
to translate an
identified position in the file to an identifier.
[0036] The representations of the media content recordings may be any
number or type
of data. As one example, the representations may include a set of fingerprints
for each media
content recording.
[0037] Figure 3 illustrates a diagram of an example method to form a
concatenation of
representations of media content recordings. Generally, media content can be
identified by
computing characteristics or fingerprints of a media sample and comparing the
fingerprints to
13
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
previously identified fingerprints of reference media files. Particular
locations within the
sample at which fingerprints are computed may depend on reproducible points in
the sample.
Such reproducibly computable locations are referred to as "landmarks." One
landmarking
technique, known as Power Norm, is to calculate an instantaneous power at many
time points
in the recording and to select local maxima. One way of doing this is to
calculate an envelope
by rectifying and filtering a waveform directly. Figure 3 illustrates a media
content recording
being input to a fingerprint extractor 302 (or fingerprint generator) that is
configured to
determine fingerprints of the media content recording. An example plot of dB
(magnitude) of a
sample vs. time is shown, and the plot illustrates a number of identified
landmark positions (Li
to L8). Once the landmarks have been determined, the fingerprint extractor 302
is configured
to compute a fingerprint at or near each landmark time point in the recording.
The fingerprint
is generally a value or set of values that summarizes a set of features in the
recording at or near
the landmark time point. In one example, each fingerprint is a single
numerical value that is a
hashed function of multiple features. Other examples of fingerprints include
spectral slice
fingerprints, multi-slice fingerprints, LPC coefficients, cepstral
coefficients, and frequency
components of spectrogram peaks.
[0038] The fingerprint extractor 302 may generate a set of fingerprints
each with a
corresponding landmark and provide the fingerprint/landmark pairs for each
media content
recording to a database 304 for storage. The fingerprints are then represented
in the database
304 as key-value pairs where the key is the fingerprint and the value is a
corresponding
landmark. A value may also have an associated sound ID within the database
304, for
example. Media recordings can be indexed with sound ID from 0 to N-1, where N
is a number
of media recordings.
14
CA 02905385 2015-09-10
WO 2014/150746
PCT/US2014/024117
[0039] A concatenator 306 may retrieve the fingerprint/landmark pairs for
each media
content recording and maintain the fingerprints per recording in time order
based on the
landmarks for that recording so as to create a time ordered fingerprint set
for each recording.
The concatenator 306 then joins the fingerprint sets for all recordings end to
end into a single
data file 308 that has a conceptual timeline or global time.
[0040] A mapping can be created between each sound ID and a corresponding
global
position in the data file 308. In addition, a list of global starting
positions for each original
media recording within the concatenated media recording data file is stored to
create a reverse
mapping from each global position to a corresponding local position in an
original media
recording indexed by a sound ID. The global starting positions thus segment
the global
timeline according to the original media recordings.
[0041] Thus, to determine a local position of a sample of media within
the global
timeline, a global position in the timeline as well as a global start position
of the media
recording is determined according to Equation 1.
local position = global position - global start position[sound ID]
Equation (1)
Thus, to determine a local position of a sample of media within the global
timeline, a global
position in the timeline as well as a global start position of the media
recording is determined
according to Equation 1. As an example, to map from a global position to a
sound ID and local
position, the global start positions are searched for an interval containing
the global position,
i.e., find a sound ID where:
global start position[sound ID] =< global position < global start
position[sound ID+l]
Equation (2)
[0042] A mapping can be created between each sound ID and a corresponding
global
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
position in the data file 308. In addition, a list of global starting
positions for each original
media recording within the concatenated media recording data file is stored to
create a reverse
mapping from each global position to a corresponding local position in an
original media
recording indexed by a sound ID. The global starting positions thus segment
the global
timeline according to the original media recordings.
[0043] Thus, within examples, the data file 308 conceptually represents a
K-V database
where each key K is a fingerprint and the value V comprises a global position
corresponding to
a landmark position of the fingerprint. In some examples, a buffer (e.g.,
blank space of several
seconds worth of timeline) may be inserted between adjacent recordings to
provide for distinct
boundaries between recordings, and to make it less ambiguous which recording
is a match
during a search process.
[0044] Figure 4 shows a flowchart of an example method 400 for providing
a database
of concatenated media content recordings. Method 400 shown in Figure 4
presents an
embodiment of a method that, for example, could be used with the system shown
in Figure 1,
for example, and may be performed by a computing device (or components of a
computing
device) such as a client device or a server or may be performed by components
of both a client
device and a server.
[0045] At block 402, the method 400 includes receiving media content
recordings.
Media content recordings may include a number of songs, television programs,
or any type of
audio and/or video recordings.
[0046] At block 404, the method 400 includes determining a representation
for each
media content recording. In one example, fingerprints of a respective media
content recording
16
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
can be determined at respective positions within the respective media content
recording, and
the representation can be defined as the fingerprints. The representation may
include additional
or alternative information describing the media content recording such as any
type of
characteristic of the media content recording.
[0047] At block 406, the method 400 includes concatenating the
representation for each
media content recording as a data file. The data file has a concatenated or
global timeline, and
a given media content recording is represented as being located within the
data file along the
concatenated timeline at a given position or global position. In some
examples, a buffer is
provided between adjacent representations of media content recordings within
the data file.
[0048] At block 408, the method 400 includes storing a mapping between an
identifier
for a respective media content recording and a global position in the data
file that corresponds
to the representation of the respective media content recording. The global
position may thus
correspond to a sound identifier of the given media content recording and a
local landmark
position of the fingerprint within the given media content recording.
[0049] In some examples, the method 400 also includes storing a list of
global starting
positions for media content recordings within the concatenated data file to
segment a global
timeline of the data file according to the media content recordings.
Additionally, a list of
boundaries between each representation of media content recording within the
concatenated
data file can be stored as well.
Example Search Methods
[0050] Within examples, a sample of media content is received, and a
content
17
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
recognition is performed by searching for matching content within the data
file of concatenated
media recordings. Any number of content identification matching methods may be
used
depending on a type of content being identified. As an example, for images and
video content
identification, an example video identification algorithm is described in
Oostveen, J., et al.,
"Feature Extraction and a Database Strategy for Video Fingerprinting", Lecture
Notes in
Computer Science, 2314, (Mar. 11, 2002), 117-128, the entire contents of which
are herein
incorporated by reference. For example, a position of the video sample into a
video can be
derived by determining which video frame was identified. To identify the video
frame, frames
of the media sample can be divided into a grid of rows and columns, and for
each block of the
grid, a mean of the luminance values of pixels is computed. A spatial filter
can be applied to
the computed mean luminance values to derive fingerprint bits for each block
of the grid. The
fingerprint bits can be used to uniquely identify the frame, and can be
compared or matched to
fingerprint bits of a database that includes known media. Based on which frame
the media
sample included, a position into the video (e.g., time offset) can be
determined.
[0051] As another example, for media or audio content identification
(e.g., music),
various content identification methods are known for performing computational
content
identifications of media samples and features of media samples using a
database of known
media. The following U.S. Patents and publications describe possible examples
for media
recognition techniques, and each is entirely incorporated herein by reference,
as if fully set
forth in this description: Kenyon et al, U.S. Patent No. 4,843,562; Kenyon,
U.S. Patent No.
4,450,531; Haitsma et al, U.S. Patent Application Publication No.
2008/0263360; Wang and
Culbert, U.S. Patent No. 7,627,477; Wang, Avery, U.S. Patent Application
Publication No.
2007/0143777; Wang and Smith, U.S. Patent No. 6,990,453; Blum, et al, U.S.
Patent No.
18
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
5,918,223; Master, et al, U.S. Patent Application Publication No.
2010/0145708.
[0052] As one example, fingerprints of a received sample of media content
can be
matched to fingerprints of known media content by generating correspondences
between
equivalent fingerprints in the concatenated data file to locate a media
recording that has a
largest number of linearly related correspondences, or whose relative
locations of characteristic
fingerprints most closely match the relative locations of the same
fingerprints of the recording.
[0053] Figure 5 shows a flowchart of an example method 500 for performing
a content
recognition of a received sample of media content. Method 500 shown in Figure
5 presents an
embodiment of a method that, for example, could be used with the system shown
in Figure 1,
for example, and may be performed by a computing device (or components of a
computing
device) such as a client device or a server or may be performed by components
of both a client
device and a server.
[0054] At block 502, the method 500 includes determining fingerprints in
the data file
that substantially match to one or more fingerprints of the sample of media
content.
Fingerprints of the received sample of media content are created by processing
a query media
sample into a set of sample landmark and fingerprint pairs. The sample
fingerprints are then
used to retrieve matching KV pairs in the KV data file of concatenated media
content, where
the key K is a fingerprint and the value V is the payload, which in this case
is a concatenated
global position value.
[0055] At block 504, the method 500 includes pairing corresponding global
positions of
the substantially matching fingerprints with corresponding respective landmark
positions of the
one or more fingerprints in the sample of media content to provide global
position-landmark
19
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
position pairs. Thus, a retrieved global position value is paired with the
sample landmark
value. A time offset between the two positions may then be determined, for
each global
position-landmark position pair, by subtracting the global position value from
the sample
landmark value for matching fingerprints. Instead of storing the time offset
pair differences
(generated by subtracting corresponding time offsets from matching sample
versus reference
fingerprints) into many buckets where each bucket corresponds to a sound ID
index, all time
offset differences can be stored in a single bucket.
[0056] At block 506, the method 500 includes sorting the global position-
landmark
position pairs. In other examples, the method 500 may include sorting the time
offset
differences generated from the global position-landmark position pairs. As one
example, a radix
sorting method may be used. Radix sorting algorithms are known in the art and
discussed in D.
E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching,
Reading,
Mass.: Addison-Wesley, 1998, herein incorporated by reference. For instance,
the radix sort
includes a non-comparison linear-time sort that sorts data with integer keys
by grouping keys
by the individual digits which share the same significant position and value.
In an example, if
the time offset pair differences are contained within a 32-bit number, then
the radix sort method
may be conveniently implemented using commodity computational hardware and
algorithms.
For a large scale sorting of the entire set of time offset differences into
one bucket, the radix
sort may be economically advantageous over standard sorts on many small
buckets, for
example using conventional quicksort or heapsort methods. Following the sort,
the time offset
differences will be organized in order of ascending global position.
[0057] At block 508, the method 500 includes determining clusters of the
global
position-landmark position pairs that are substantially linearly related (or
have some associated
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
temporal correspondence). As one example, to verify if there is a match, a
histogram scan can
be performed to search for a significant peak in the sorted time offset
difference data (e.g.,
number of data points occurring within a predetermined window width or number
of points in a
histogram bin). A presence of a peak in the number of points above a threshold
within a
window or bin can be interpreted as evidence for a match. Each occurrence of a
significant
peak in the long concatenated timeline of time offset differences indicates a
candidate match,
and candidate matches may be further processed individually to ascertain
whether the
candidates matches are exact, possibly using a different algorithm to verify a
match. As one
example, the time offset differences may be filtered using a predetermined
window width of a
few milliseconds.
[0058] At block 510, the method 500 includes identifying a matching media
content
recording to the sample of media content as a media content recording having a
cluster with a
largest number of global position-landmark position pairs that are
substantially linearly related.
Thus, the candidate match that has the most time offset differences within a
predetermined
window width can be deemed the winning matching file, for example.
[0059] In some examples, a buffer (e.g., blank space of several seconds
worth of
timeline) may be inserted between adjacent recordings in the concatenated data
file to make it
less ambiguous which media content recording was a match in case a sample
offset into a
particular song was negative, e.g., if the sample started before the song
started then an offset
mapping would put the recognized offset point in the previous song of the
concatenated data
file.
[0060] In some examples, the method 500 may further include determining a
sound
identifier of the matching media content recording based on the corresponding
global position
21
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
of the substantially matching fingerprints in the data file. For example,
global positions of
representations of the given media content recording in the data file can be
associated or
mapped to respective sound identifiers, and the mapping may be referenced when
a winning
global position is identified.
[0061] Figure 6 is a diagram that conceptually illustrates performing a
content
recognition. Initially, fingerprint and landmark pairs (Fa', F2/L2, ..., FAO
can be
determined and the fingerprints can be used to find matching fingerprints
within the
concatenated data file of known media content recordings. Global positions
within the data file
can be paired with landmarks in the sample for matching fingerprints. A
scatter plot of
landmarks of the sample and global positions of the known reference files can
be determined
After generating a scatter plot, clusters of landmark pairs having linear
correspondences can be
identified, and the clusters can be scored according to the number of pairs
that are linearly
related. A linear correspondence may occur when a statistically significant
number of
corresponding sample locations and reference file locations can be described
with a linear
equation, within an allowed tolerance, for example. An X-intercept of the
linear equation may
be a global time offset of the beginning of a matching media recording, and
may be used for
position detection, as well as for content identification. The file of the
cluster with the highest
statistically significant score, i.e., with the largest number of linearly
related landmark pairs, is
the winning file, and may be deemed the matching media file. In one example,
to generate a
score for a reference file, a histogram of offset values can be generated. The
offset values may
be differences between landmark time positions and the global positions where
a fingerprint
matches. Figure 6 illustrates an example histogram of offset values. The
reference file may be
given a score that is related to the number of points in a peak of the
histogram (e.g., score = 28
22
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
in Figure 6). The entire concatenated data file may be processed in this
manner using a single
bulk operation to determine histogram peaks and a score for each peak, and the
media content
recording corresponding to the global position resulting in the highest score
may be determined
to be a match to the sample.
[0062] In other examples, as additions or alternative to using a
histogram, the Hough
transform or RANSAC algorithms may be used to determine or detect a linear or
temporal
correspondence between time differences.
[0063] In some example, multiple simultaneous searches of the
concatenated data file
may be performed to determine a content recognition for multiple samples at
the same time.
For example, the time offset pair differences between landmarks and global
positions for
matching fingerprints, per sample, can be augmented by adding extra bits to
the representation
to indicate a sub-search index. For data representations of the time
differences of up to 30 bits,
an extra 2 high bits may be added to make the data representation an even 32
bits. The extra 2
bits may then index up to 4 separate searches. In general, if k extra most
significant bits
(MSBs) are added to the data representation, then 2'1 sub-searches may be
represented.
[0064] Instead of performing a number of independent sequential sample
identifications, each search may be processed with time offset pair
differences put into the
single bucket, and augmented with a unique identifier using the upper k MSBs.
The single
bucket may thus be filled with data for up to 2'1( searches over a large
number of songs, and
thus, buckets for many songs and sessions can be collapsed into one. A single
sort operation
can be performed to sort all the augmented time differences in the bucket. A
histogram peak
scan is carried out, as before, and the peaks are determined, and locations of
the peaks may be
interpreted as follows: the upper k bits of a peak indicate which sub-search
the peak belongs to,
23
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
and the lower bits indicate which song the sample matched.
[0065] Using examples described herein, a content recognition of a
received sample of
media content can be performed using a single array of data representing all
known reference
media content. Reference to media content identifiers can be removed from the
searching
process, and determined based on mappings to positions in the single array of
data. A single or
bulk global sort can be performed for simpler and more efficient sorting so
that rather than
minimizing an amount of material to sort (per sort), an amount of material is
maximized. In
some instances, a number of items searched can be increased by batching
multiple queries,
using bits to index batch entry, and a single sort then accomplishes
separation of batches. A
histogram scan or other peak determination methods can be performed to
identify a winning
match on a continuous timeline, and a media content identifier is retrieved
after histogram
searching by using reverse lookup, e.g. a binary search on an offset table.
[0066] It should be understood that arrangements described herein are for
purposes of
example only. As such, those skilled in the art will appreciate that other
arrangements and
other elements (e.g. machines, interfaces, functions, orders, and groupings of
functions, etc.)
can be used instead, and some elements may be omitted altogether according to
the desired
results. Further, many of the elements that are described are functional
entities that may be
implemented as discrete or distributed components or in conjunction with other
components, in
any suitable combination and location, or other structural elements described
as independent
structures may be combined.
[0067] While various aspects and embodiments have been disclosed herein,
other
aspects and embodiments will be apparent to those skilled in the art. The
various aspects and
embodiments disclosed herein are for purposes of illustration and are not
intended to be limiting,
24
CA 02905385 2015-09-10
WO 2014/150746 PCT/US2014/024117
with the true scope being indicated by the following claims, along with the
full scope of
equivalents to which such claims are entitled. It is also to be understood
that the terminology
used herein is for the purpose of describing particular embodiments only, and
is not intended to
be limiting.
