Image-based feature detection using edge vectors

• US 9,412,176 B2
• Filed: 05/06/2015
• Issued: 08/09/2016
• Est. Priority Date: 05/06/2014
• Status: Active Grant

• Current Assignee: Nant Holdings IP, LLC (NantWorks, LLC)
• Original Assignee: Nant Holdings IP, LLC (NantWorks, LLC)
• Inventors: Song, Bing, Witchey, Nicholas J.
• Primary Examiner(s): Liu, Li
• Application Number:
  US14/705,866
• Publication Number:
  US 20150324998A1
• Time in Patent Office: 461 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 2207/10004 Still image; Photographic image
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/10116 X-ray image
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 3/40 Scaling of whole images or parts thereof, e.g. expanding or contracting
• CPC Class Codes: G06T 3/403 Edge-driven scaling; Edge-based scaling
• CPC Class Codes: G06T 5/40 using histogram techniques
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/758 : Involving statistics of pixels or of feature values, e.g. histogram matching
• CPC Class Codes: G06V 20/64 : Three-dimensional objects

Abstract

Techniques are provided in which a plurality of edges are detected within a digital image. An anchor point located along an edge of the plurality of edges is selected. An analysis grid associated with the anchor point is generated, the analysis grid including a plurality of cells. An anchor point normal vector comprising a normal vector of the edge at the anchor point is calculated. Edge pixel normal vectors comprising normal vectors of the edge at locations along the edge within the cells of the analysis grid are calculated. A histogram of similarity is generated for each of one or more cells of the analysis grid, each histogram of similarity being based on a similarity measure between each of the edge pixel normal vectors within a cell and the anchor point normal vector, and a descriptor is generated for the analysis grid based on the histograms of similarity.

Claims

1. A method of generating an edge-based feature descriptor for a digital image at a feature detection device, the method comprising:

detecting, by the feature detection device, a plurality of edges within the digital image;

selecting, by the feature detection device, an anchor point located along an edge of the plurality of edges;

generating, by the feature detection device, an analysis grid associated with the anchor point, the analysis grid including a plurality of cells;

calculating, by the feature detection device, an anchor point normal vector comprising a normal vector of the edge at the anchor point;

calculating, by the feature detection device, one or more edge pixel normal vectors comprising normal vectors of the edge at one or more locations along the edge within the cells of the analysis grid;

generating, by the feature detection device, a histogram of similarity for each of one or more cells of the analysis grid, each histogram of similarity being based on a similarity measure between each of the edge pixel normal vectors within a cell and the anchor point normal vector; and

generating, by the feature detection device, a descriptor for the analysis grid based on the histograms of similarity.

2. The method of claim 1, wherein the digital image is one of a video frame of a video stream and a rendered image.

3. The method of claim 1, wherein the plurality of edges is detected based on one of tensor voting and a Canny edge detection algorithm.

4. The method of claim 1, further comprising eliminating at least one degenerate edge from the plurality of edges.

5. The method of claim 1, further comprising:

scaling the digital image by a scaling factor; and

detecting the plurality of edges within the scaled digital image.

6. The method of claim 5, wherein the scaling factor is at least 1.5.

7. The method of claim 5, wherein the scaling factor is at least 2.0.

8. The method of claim 1, wherein the anchor point is a feature corresponding to at least one of a scale-invariant feature transform (SIFT), Fast Retina Keypoint (FREAK), Histograms of Oriented Gradient (HOG), Speeded Up Robust Features (SURF), DAISY, Binary Robust Invariant Scalable Keypoints (BRISK), FAST, Binary Robust Independent Elementary Features (BRIEF), Harris Corners, Edges, Gradient Location and Orientation Histogram (GLOH), Energy of image Gradient (EOG) or Transform Invariant Low-rank Textures (TILT) feature.

9. The method of claim 1, wherein the anchor point comprises a detected corner of the edge.

10. The method of claim 1, wherein the analysis grid has a geometric center at the anchor point.

11. The method of claim 1, wherein the analysis grid includes one of a polar grid, a radial polar grid or a rectilinear grid.

12. The method of claim 11, wherein the analysis grid is oriented based on the anchor point normal vector.

13. The method of claim 1, wherein the analysis grid comprises at least five cells.

14. The method of claim 1, wherein the analysis grid comprises at least nine cells.

15. The method of claim 1, wherein the anchor point normal vector is one of a Harris matrix eigenvector or a geometric normal vector orthogonal to the edge at a pixel coordinate of the anchor point.

16. The method of claim 1, wherein each of the edge pixel normal vectors is one of a Harris matrix eigenvector or a geometric normal vector orthogonal to the edge at a pixel coordinate.

17. The method of claim 1, wherein the similarity measure is based on one of a relative angle or a dot product between each of the edge pixel normal vectors within a cell and the anchor point normal vector.

18. The method of claim 1, wherein the similarity measure is based on a comparison between a magnitude of each of the edge pixel normal vectors within a cell and a magnitude of the anchor point normal vector.

19. The method of claim 18, wherein the magnitude of each of the edge pixel normal vectors within a cell and the magnitude of the anchor point normal vector are based on a non-orientation based measurement.

20. The method of claim 1, wherein the similarity measure is based on one or more weighting factors.

21. The method of claim 20, wherein the one or more weighting factors are based on one of a Euclidean distance and a Gaussian weight.

22. The method of claim 1, wherein each histogram of similarity includes a plurality of bins.

23. The method of claim 22, wherein each histogram of similarity includes at least four bins.

24. The method of claim 22, wherein each histogram of similarity includes at least 16 bins.

25. The method of claim 22, wherein bin values for the plurality of bins are normalized based on a maximum bin value.

26. The method of claim 25, wherein bin values for the plurality of bins range between 0 and 255.

27. The method of claim 1, wherein generating the descriptor includes concatenating data from the histograms of similarity for one or more of the cells of the analysis grid.

28. The method of claim 27, further comprising determining a concatenation order for the data from the histograms of similarity.

29. The method of claim 28, wherein the concatenation order is based on an orientation of the cells of the analysis grid relative to the anchor point normal vector.

30. The method of claim 1, wherein the descriptor is a multi-dimensional vector having a number of dimensions based on a number of cells in the analysis grid.

31. The method of claim 1, wherein the descriptor is a multi-dimensional vector having a number of dimensions based on a total number of bins in the histograms of similarity for the analysis grid.

32. The method of claim 1, further comprising selecting a plurality of anchor points located along the edge, wherein the anchor points are equidistant along the edge with respect to each other.

33. The method of claim 1, further comprising selecting a plurality of anchor points located along the edge in accordance with at least one of a determined distribution of analysis grids along the edge, a determined amount of analysis grids per unit area, a determined amount of analysis grids per unit volume, a selected object model, or depth field information associated with the digital image.

34. The method of claim 1, further comprising facilitating an image-based object recognition search using the descriptor for the analysis grid.

35. A system for generating an edge-based feature descriptor for a digital image, the system comprising:

a processor;

a memory device; and

a feature detector executable on the processor according to software instructions stored in the memory device, the feature detector being configured to;

detect a plurality of edges within the digital image;

select an anchor point located along an edge of the plurality of edges;

generate an analysis grid associated with the anchor point, the analysis grid including a plurality of cells;

calculate an anchor point normal vector comprising a normal vector of the edge at the anchor point;

calculate one or more edge pixel normal vectors comprising normal vectors of the edge at one or more locations along the edge within the cells of the analysis grid;

generate a histogram of similarity for each of one or more cells of the analysis grid, each histogram of similarity being based on a similarity measure between each of the edge pixel normal vectors within a cell and the anchor point normal vector; and

generate a descriptor for the analysis grid based on the histograms of similarity.

36. A computer program product embedded in a non-transitory computer readable medium comprising instructions executable by a computer processor to generate an edge-based feature descriptor for a digital image, the instructions being executable by a computer processor to execute processing comprising:

detecting a plurality of edges within the digital image;

selecting an anchor point located along an edge of the plurality of edges;

generating an analysis grid associated with the anchor point, the analysis grid including a plurality of cells;

calculating an anchor point normal vector comprising a normal vector of the edge at the anchor point;

calculating one or more edge pixel normal vectors comprising normal vectors of the edge at one or more locations along the edge within the cells of the analysis grid;

generating a histogram of similarity for each of one or more cells of the analysis grid, each histogram of similarity being based on a similarity measure between each of the edge pixel normal vectors within a cell and the anchor point normal vector; and

generating a descriptor for the analysis grid based on the histograms of similarity.