Systems and methods for reducing data density in large datasets

• US 10,192,138 B2
• Filed: 04/15/2016
• Issued: 01/29/2019
• Est. Priority Date: 05/27/2010
• Status: Active Grant

• Current Assignee: Inscape Data, Inc. (VIZIO, Inc.)
• Original Assignee: Inscape Data, Inc. (VIZIO, Inc.)
• Inventors: Neumeier, Zeev
• Primary Examiner(s): Desire, Gregory M
• Application Number:
  US15/099,842
• Publication Number:
  US 20160307043A1
• Time in Patent Office: 1,019 Days
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching
• CPC Class Codes: G06V 20/47 Detecting features for summarising video content
• CPC Class Codes: G06V 40/172 Classification, e.g. identification

Abstract

Techniques and systems are provided for identifying unknown content. For example, a number of vectors out of a plurality of vectors projected from an origin point can be determined that are between a reference data point and an unknown data point. The number of vectors can be used to estimate an angle between a first vector (from the origin point to a reference data point) and a second vector (from the origin point to an unknown data point). A distance between the reference data point and the unknown data point can then be determined. Using the determined distance, candidate data points can be determined from a set of reference data points. The candidate data points can be analyzed to identify the unknown data point.

Claims

1. A system, comprising:

one or more processors;

one or more non-transitory machine-readable storage media containing instructions which when executed on the one or more processors, cause the one or more processors to perform operations including;

obtaining a plurality of reference video data points;

determining a length of a first vector from an origin point to a reference video data point of the plurality of reference video data points;

obtaining an unknown video data point associated with video content being presented by a display;

determining a length of a second vector from the origin point to the unknown video data point;

projecting a plurality of vectors from the origin point;

determining a number of the plurality of vectors between the reference video data point and the unknown video data point;

estimating an angle between the first vector and the second vector, wherein the angle is estimated using the number of the plurality of vectors;

determining a distance between the reference video data point and the unknown video data point, wherein the distance is determined using the estimated angle and the determined lengths of the first vector and the second vector;

identifying one or more candidate video data points from the plurality of reference video data points, wherein a candidate video data point is a candidate for matching the unknown video data point, and wherein the one or more candidate video data points are determined based on determined distances between one or more reference video data points and the unknown video data point; and

identifying the video content being presented by the display, wherein the video content being presented by the display is identified by comparing the unknown video data point with the one or more candidate video data points.

2. The system of claim 1, wherein the plurality of reference video data points include video data extracted from one or more video frames.

3. The system of claim 1, wherein the plurality of vectors are pseudo-randomly generated.

4. The system of claim 1, wherein determining the number of the plurality of vectors between the reference video data point and the unknown video data point includes:

determining whether each vector of the plurality of vectors is to an algebraic right or to an algebraic left of the first vector of the reference video data point;

determining whether each vector of the plurality of vectors is to the algebraic right or to the algebraic left of the second vector of the unknown video data point; and

determining the number of the plurality of vectors between the reference video data point and the unknown video data point, wherein the number of the plurality of vectors includes vectors to the algebraic left of the first vector and to the algebraic right of the second vector or vectors to the algebraic right of the first vector and to the algebraic left of the second vector.

5. The system of claim 4, wherein the reference video data point is discarded after the length of the first vector of the reference video data point is determined and after each vector of the plurality of vectors is determined to be to the algebraic right or to the algebraic left of the first vector.

6. The system of claim 5, further comprising instructions which when executed on the one or more processors, cause the one or more processors to perform operations including:

storing a first binary value for each vector that is determined to be to the algebraic right of the first vector of the reference video data point; and

storing a second binary value for each vector that is determined to be to the algebraic left of the first vector of the reference video data point.

7. The system of claim 5, further comprising instructions which when executed on the one or more processors, cause the one or more processors to perform operations including:

storing a first binary value for each vector that is determined to be to the algebraic right of the second vector of the unknown video data point; and

storing a second binary value for each vector that is determined to be to the algebraic left of the second vector of the unknown video data point.

8. The system of claim 1, wherein estimating the angle between the first vector of the reference video data point and the second vector of the unknown video data point includes multiplying a constant by a ratio, wherein the ratio includes the number of the plurality of vectors between the reference video data point and the unknown video data point divided by a total number of the plurality of vectors.

9. The system of claim 1, wherein determining the distance between the reference video data point and the unknown video data point includes performing a Pythagorean identity calculation using the estimated angle and the determined lengths of the first vector and the second vector.

10. The system of claim 1, wherein identifying the video content being presented by the display includes determining a match between the unknown video data point and a candidate video data point, wherein the match is an approximate match based on the candidate video data point being a closest video data point of the one or more candidate video data points to the unknown video data point.

11. The system of claim 1, wherein the reference video data point is discarded after the length of the first vector of the reference video data point is determined.

12. A method of identifying video content, comprising:

obtaining a plurality of reference video data points;

determining a length of a first vector from an origin point to a reference video data point of the plurality of reference video data points;

obtaining an unknown video data point associated with video content being presented by a display;

determining a length of a second vector from the origin point to the unknown video data point;

projecting a plurality of vectors from the origin point;

determining a number of the plurality of vectors between the reference video data point and the unknown video data point;

estimating an angle between the first vector and the second vector, wherein the angle is estimated using the number of the plurality of vectors;

determining a distance between the reference video data point and the unknown video data point, wherein the distance is determined using the estimated angle and the determined lengths of the first vector and the second vector;

identifying one or more candidate video data points from the plurality of reference video data points, wherein a candidate video data point is a candidate for matching the unknown video data point, and wherein the one or more candidate video data points are determined based on determined distances between one or more reference video data points and the unknown video data point; and

identifying the video content being presented by the display, wherein the video content being presented by the display is identified by comparing the unknown video data point with the one or more candidate video data points.

13. The method of claim 12, wherein determining the number of the plurality of vectors between the reference video data point and the unknown video data point includes:

determining whether each vector of the plurality of vectors is to an algebraic right or to an algebraic left of the first vector of the reference video data point;

determining whether each vector of the plurality of vectors is to the algebraic right or to the algebraic left of the second vector of the unknown video data point; and

determining the number of the plurality of vectors between the reference video data point and the unknown video data point, wherein the number of the plurality of vectors includes vectors to the algebraic left of the first vector and to the algebraic right of the second vector or vectors to the algebraic right of the first vector and to the algebraic left of the second vector.

14. The method of claim 13, wherein the reference video data point is discarded after the length of the first vector of the reference video data point is determined and after each vector of the plurality of vectors is determined to be to the algebraic right or to the algebraic left of the first vector.

15. The method of claim 14, further comprising:

storing a first binary value for each vector that is determined to be to the algebraic right of the first vector of the reference video data point; and

storing a second binary value for each vector that is determined to be to the algebraic left of the first vector of the reference video data point.

16. The method of claim 14, further comprising:

storing a first binary value for each vector that is determined to be to the algebraic right of the second vector of the unknown video data point; and

storing a second binary value for each vector that is determined to be to the algebraic left of the second vector of the unknown video data point.

17. The method of claim 12, wherein estimating the angle between the first vector of the reference video data point and the second vector of the unknown video data point includes multiplying a constant by a ratio, wherein the ratio includes the number of the plurality of vectors between the reference video data point and the unknown video data point divided by a total number of the plurality of vectors.

18. The method of claim 12, wherein determining the distance between the reference video data point and the unknown video data point includes performing a Pythagorean identity calculation using the estimated angle and the determined lengths of the first vector and the second vector.

19. The method of claim 12, wherein identifying the video content being presented by the display includes determining a match between the unknown video data point and a candidate video data point, wherein the match is an approximate match based on the candidate video data point being a closest video data point of the one or more candidate video data points to the unknown video data point.

20. The method of claim 12, wherein the reference video data point is discarded after the length of the first vector of the reference video data point is determined.

21. A method of identifying one or more unknown data points, comprising:

obtaining a plurality of reference data points;

determining a length of a first vector from an origin point to a reference data point of the plurality of reference data points;

obtaining an unknown data point associated with content being presented by a display;

determining a length of a second vector from the origin point to the unknown data point;

projecting a plurality of vectors from the origin point;

removing a number of bits associated with the reference data point of the plurality of reference data points from memory;

determining a number of the plurality of vectors between the reference data point and the unknown data point;

estimating an angle between the first vector and the second vector, wherein the angle is estimated using the number of the plurality of vectors; and

determining a distance between the first vector associated with the reference data point of the plurality of reference data points and the unknown data point, wherein the distance is determined using the estimated angle and the determined lengths of the first vector and the second vector;

identifying one or more candidate data points from the first vector associated with the reference data point of the plurality of reference data points, wherein a candidate data point is a candidate for matching the unknown data point, and wherein the one or more candidate data points are determined based on determined distances between the first vector associated with the reference data point of the plurality of reference data points and the unknown data point; and

identifying the unknown data point by comparing the unknown data point with the one or more candidate data points.

22. The method of claim 21, determining a match between the unknown data point and a candidate data point, wherein the match is an approximate match based on the candidate data point being a closest data point of the one or more candidate data points to the unknown data point.