Content identification using fingerprint matching

A method of identifying media content, the media content including a plurality of media frames, comprising the steps of:

• obtaining query fingerprint data from the plurality of media frames, the query fingerprint data being characteristic of the media content;
• obtaining, at a Viterbi sequence detector from a reference content database, reference fingerprint data corresponding to the query fingerprint data from a plurality of reference frames, the reference fingerprint data being characteristic of reference content associated with the plurality of reference frames, at least some of the plurality of reference frames being associated with at least one of a plurality of reference frame sequences;
• and
• identifying, on a per-frame basis by the Viterbi sequence detector, at least one reference frame sequence from among the plurality of reference frame sequences using a hidden Markov model that includes a set of states, a set of observation outputs, a set of initial probabilities for the set of states, a set of transition probabilities for the set of states, and a set of observation probabilities for the set of observation outputs, the identified reference frame sequence including one or more reference frames that match one or more of the respective media frames, the set of observation outputs corresponding to the respective media frames, the set of states corresponding to the reference frames that match the respective media frames, the set of states including an undefined reference frame, and the set of transition probabilities for the set of states including one or more transition probabilities for the undefined reference frame;
• and
• defining the set of transition probabilities for the set of states such that
• if i=Yu and j=Yu′, then ai,j=puu′,
• if i=Yu and j=Mf, then ai,j=puk,
• if i=Mf and j=Yu, then ai,j=pku,
• if i=Mf, j=Ng, and M≠N, then ai,j=pMN, and
• if i=Mf and j=Mg, then ai,j=trans(f,g),
• wherein (1) “ai,j” corresponds to one of the respective transition probabilities, (2) “i” corresponds to a first match between a reference frame and a media frame at a time step, t, (3) “j” corresponds to a second match between a reference frame and a media frame at a time step, t+1, (4) “M” corresponds to a first predetermined reference content identifier, (5) “N” corresponds to a second predetermined reference content identifier, the second predetermined reference content identifier, N, being different from the first predetermined reference content identifier, M, (6) “f” corresponds to a first reference frame index, (7) “g” corresponds to a second reference frame index, the second reference frame index, g, being different from the first reference frame index, f, (8) “Yu” corresponds to an undefined reference frame having an undefined reference content identifier, Y, and an undefined reference frame index, u, (9) “Yu′” corresponds to an undefined reference frame having an undefined reference content identifier, Y, and an undefined reference frame index, u′, (10) “puu′” corresponds to a first transition probability from one undefined reference frame, Yu, to another undefined reference frame, Yu′, (11) “puk” corresponds to a second transition probability from the undefined reference frame, Yu, to a first defined reference frame, Mf, (12) “pku,” corresponds to a third transition probability from the first defined reference frame, Mf, to the undefined reference frame, Yu, (13) “pMN” corresponds to a fourth transition probability from the first predetermined reference content identifier, M, to the second predetermined reference content identifier, N, and (14) “trans(f, g)” corresponds to a fifth transition probability from the first reference frame index, f, to the second reference frame index, g, each of the first reference frame index, f, and the second reference frame index, g, being associated with the same reference content identifier, M.

A system for identifying media content, the media content including a plurality of media frames, comprising:

• a fingerprint extractor operative to extract query fingerprint data from the plurality of media frames, the query fingerprint data being characteristic of the media content;
• and
• a confidence value generator operative:
• to obtain, from a reference content database, reference fingerprint data corresponding to the query fingerprint data from a plurality of reference frames, the reference fingerprint data being characteristic of reference content associated with the plurality of reference frames;
• to obtain, for each of at least some of the plurality of reference frames, a frame confidence value as an exponential function of a distance between the reference frame and a corresponding one of the plurality of media frames, the frame confidence value being indicative of how well the reference frame matches the corresponding one of the plurality of media frames, the at least some of the plurality of reference frames being associated with at least one of a plurality of reference frame sequences;
• and
• to obtain, for at least one of the plurality of reference frame sequences, a sequence confidence value based at least on the frame confidence value for each of at least some of the plurality of reference frames associated with the reference frame sequence.

A system for identifying media content, the media content including a plurality of media frames, comprising:

• a fingerprint extractor operative to extract query fingerprint data from the plurality of media frames, the query fingerprint data being characteristic of the media content;
• and
• a Viterbi sequence detector operative:
• to obtain, from a reference content database, reference fingerprint data corresponding to the query fingerprint data from a plurality of reference frames, the reference fingerprint data being characteristic of reference content associated with the plurality of reference frames, at least some of the plurality of reference frames being associated with at least one of a plurality of reference frame sequences;
• and
• to identify, on a per-frame basis, at least one reference frame sequence from among the plurality of reference frame sequences using a hidden Markov model that includes a set of states, a set of observation outputs, a set of initial probabilities for the set of states, a set of transition probabilities for the set of states, and a set of observation probabilities for the set of observation outputs, the identified reference frame sequence including one or more reference frames that match one or more of the respective media frames,
• wherein the set of observation outputs corresponds to the respective media frames,
• wherein the set of states corresponds to the reference frames that match the respective media frames,
• wherein the set of states includes an undefined reference frame,
• wherein the set of transition probabilities for the set of states includes one or more transition probabilities for the undefined reference frame, and
• wherein the set of transition probabilities for the set of states is defined such that
• if i=Yu and j=Yu′, then ai,j=puu′,
• if i=Yu and j=Mf, then ai,j=puk,
• if i=Mf and j=Yu, then ai,j=pku,
• if i=Mf, j=Ng, and M≠N, then ai,j=pMN, and
• if i=Mf and j=Mg, then ai,j=trans(f,g),
• wherein (1) “ai,j” corresponds to one of the respective transition probabilities, (2) “i” corresponds to a first match between a reference frame and a media frame at a time step, t, (3) “j” corresponds to a second match between a reference frame and a media frame at a time step, t+1, (4) “M” corresponds to a first predetermined reference content identifier, (5) “N” corresponds to a second predetermined reference content identifier, the second predetermined reference content identifier, N, being different from the first predetermined reference content identifier, M, (6) “f” corresponds to a first reference frame index, (7) “g” corresponds to a second reference frame index, the second reference frame index, g, being different from the first reference frame index, f, (8) “Yu” corresponds to an undefined reference frame having an undefined reference content identifier, Y, and an undefined reference frame index, u, (9) “Yu′” corresponds to an undefined reference frame having an undefined reference content identifier, Y, and an undefined reference frame index, u′, (10) “puu′” corresponds to a first transition probability from one undefined reference frame, Yu, to another undefined reference frame, Yu′, (11) “puk” corresponds to a second transition probability from the undefined reference frame, Yu, to a first defined reference frame, Mf, (12) “pku,” corresponds to a third transition probability from the first defined reference frame, Mf, to the undefined reference frame, Yu, (13) “pMN” corresponds to a fourth transition probability from the first predetermined reference content identifier, M, to the second predetermined reference content identifier, N, and (14) “trans(f, g)” corresponds to a fifth transition probability from the first reference frame index, f, to the second reference frame index, g, each of the first reference frame index, f, and the second reference frame index, g, being associated with the same reference content identifier, M.