Identification of lines in a heat map

• US 9,619,908 B1
• Filed: 03/24/2014
• Issued: 04/11/2017
• Est. Priority Date: 03/24/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zuczek, Pawel
• Primary Examiner(s): Lewis, Cheryl
• Application Number:
  US14/223,640
• Time in Patent Office: 1,114 Days
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

Systems and methods are provided for identifying lines in a heat map representative of overlap between two data sets. In an aspect, a method includes generating a heat map comprising a plurality of data points that represent similarities between a first data set and a second data set. The method further includes identifying areas of the heat map within a region of the heat map comprising a potential match line, identifying short lines formed via subsets of the data points respectively contained within the areas, merging the short lines to form a long line, determining degrees of continuity along the long line, and identifying a portion of the long line associated with a degree of continuity above a continuity threshold.

Claims

1. A method, comprising:

employing a processor to execute computer executable instructions stored on a non-transitory computer readable medium to perform the following acts;

generating a heat map representative of similarities between two media items, the heat map comprising a plurality of data points corresponding to difference values between fingerprints associated with points in time in a first media item with respect to fingerprints associated with points in time in a second media item;

identifying areas of the heat map within a region of the heat map comprising a potential match line;

identifying short lines formed via subsets of the data points respectively contained within the areas;

merging the short lines to form a long line;

determining degrees of continuity along the long line;

identifying a portion of the long line associated with a degree of continuity above a continuity threshold; and

identifying data points included in the portion of the long line associated with the degree of continuity above the continuity threshold as representative of a match between portions of the first and second media items.

2. The method of claim 1, wherein the identifying the short lines comprises performing a Hough transform for each of the subsets of the data points.

3. The method of claim 1, further comprising:

filtering the short lines to identify a filtered subset of the short lines based on at least one of, an angle of a short line or a degree of contrast between a short line and an area around the short line, wherein the merging the short lines to form the long line comprises merging the filtered subset of the short lines.

4. The method of claim 1, further comprising:

analyzing respective data points included in the subsets of the data points constituting respective short lines based on at least one of;

intensity of a data point relative to background intensity, density of a data point relative to background density, or complexity of an area around a data point; and

filtering the short lines to identify a filtered subset of the short lines based on the analyzing, wherein the merging the short lines to form the long line comprises merging the filtered subset of the short lines.

5. The method of claim 1, further comprising:

filtering the short lines to identify a filtered subset of the short lines based on respective strengths of the short lines, wherein strength of a short line is a function of intensity of the short line relative to background intensity, density of the short line relative to background density and complexity of an area around the short line, wherein the merging the short lines to form the long line comprises merging the filtered subset of the short lines.

6. The method of claim 1, wherein the merging the short lines to form the long line comprises merging to the short lines to close gaps between the short lines.

7. The method of claim 1, wherein the determining the degrees of continuity along the long line comprises:

generating continuity curves for the long line based on heat associated with respective data points of the long line, wherein the continuity curves increases as a function of high heat and decreases as a function of low heat.

8. The method of claim 7, wherein the identifying the portion of the long line associated with the degree of continuity above the continuity threshold comprises identifying an area of the continuity curve associated with values above a threshold value for a consistent duration above a threshold duration.

9. The method of claim 1, wherein the difference values comprise Hamming or Jaccard distances between respective fingerprints.

10. A system, comprising:

a memory that stores computer executable components;

a processor that executes at least the following computer executable components stored in the memory;

a heat map component configured to generate a heat map representative of similarities between two media items, the heat map comprising a plurality of data points corresponding to difference values between fingerprints associated with points in time in a first media item with respect to fingerprints associated with points in time in a second media item; and

an analysis component configured to identify areas of the heat map within a region of the heat map comprising a potential match line, identify short lines respectively formed via data points within the areas, merge the short lines to form a long line, determine degrees of continuity along the long line, identify a portion of the long line associated with a degree of continuity above a continuity threshold, and identify data points included in the portion of the long line associated with the degree of continuity above the continuity threshold as representative of a match between portions of the first and second media items.

11. The system of claim 10, wherein the analysis component identifies the short lines using respective Hough transforms for the data points within the areas.

12. The system of claim 10, wherein the analysis component further filters the short lines to identify a filtered subset of the short lines based on at least one of, an angle of a short line or a degree of contrast between a short line and an area around the short line, and wherein the analysis component merges the filtered subset of the short lines to form the long line.

13. The system of claim 10, wherein the analysis component further filters the short lines to a filtered subset of short lines based on analysis of respective data points forming the short lines, wherein the analysis is based on at least one of:

intensity of a data point relative to background intensity, density of a data point relative to background density, or complexity of an area around a data point, and filters short lines to identify a filtered subset of the short lines based on the analyzing, and wherein the analysis component merges the filtered subset of the short lines to form the long line.

14. The system of claim 10, wherein the analysis component further filters the short lines to a filtered subset of short lines based on respective strengths of the short lines, wherein strength of a short line is a function of intensity of the short line relative to background intensity, density of the short line relative to background density and complexity of an area around the short line, and wherein the analysis component merges the filtered subset of the short lines to form the long line.

15. The system of claim 10, wherein the analysis component determines the degree of continuity along the long line by generating a continuity curve for along the long line as a function of heat associated with respective areas of the long line, wherein the continuity curves increases as a function of high heat and decreases as a function of low heat.

16. The system of claim 15, wherein analysis component identifies the portion of the long line associated with the degree of continuity above the continuity threshold based on areas of the continuity curves having values higher than the threshold value, and wherein the analysis component associates a high confidence level with the portion of the long line as comprising the subset of the data points representative of matches between data included in the first and second data sets.

17. A non-transitory computer-readable storage medium comprising computer-readable instructions that, in response to execution, cause a computing system having a processor to perform operations, comprising:

generating a heat map representative of similarities between two media items, the heat map comprising a plurality of data points corresponding to difference values between fingerprints associated with points in time in a first media item with respect to fingerprints associated with points in time in a second media item;

identifying areas of the heat map within a region of the heat map comprising a potential match line;

identifying short lines formed via subsets of the data points respectively contained within the areas;

merging the short lines to a form long line;

determining degrees of continuity along the long line;

identifying a portion of the long line associated with a degree of continuity above a continuity threshold; and

identifying data points included in the portion of the long line associated with the degree of continuity above the continuity threshold as representative of a match between portions of the first and second media items.