Radial histogram matching

• US 10,423,858 B2
• Filed: 07/21/2014
• Issued: 09/24/2019
• Est. Priority Date: 07/21/2014
• Status: Active Grant

• Current Assignee: Ent Services Development Corporation LP (DXC Technology Company)
• Original Assignee: Ent Services Development Corporation LP (DXC Technology Company)
• Inventors: Miller, Joseph
• Primary Examiner(s): Roz, Mark
• Application Number:
  US15/305,990
• Publication Number:
  US 20170124425A1
• Time in Patent Office: 1,891 Days
• Field of Search: None
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching

Abstract

An example radial histogram matching system may generate a target radial histogram by identifying pixels in an input digital image that are determined to be on, traversing each of the pixels in the input digital image one time to determine how many of the pixels that are turned on are contained in each sector of a circle and assigning to each elements of the target radial histogram the number of on pixels in that element. The system may also compare the target radial histogram to each of an initial and a sequence of rotated radial histograms to determine a match score for each of the comparisons, and identify an offset rotation between a baseline pattern digital image and the input digital image based on the match scores.

Claims

1. A non-transitory storage device including machine instructions that, when executed by a processing resource, cause the processing resource to:

identify pixels, in a baseline pattern digital image and in an input digital image, that are determined to be on based on a value of a respective pixel meeting a pre-defined threshold criterion;

traverse each of the pixels in the baseline pattern digital image and in the input digital image one time to determine how many of the pixels that are on are contained in each of 360 sectors of a circle, wherein each sector subtends a degree of angle, and wherein the 360 sectors comprise the whole circle;

assign to each of 360 elements of an initial radial histogram, and to each of 360 elements of a target radial histogram, the number of on pixels in that element;

determine a range of the initial radial histogram as a difference between a maximum number of pixels and a minimum number of pixels counted in the 360 elements of the initial radial histogram;

determine a range of the target radial histogram as a difference between a maximum number of pixels and a minimum number of pixels counted in the 360 elements of the target radial histogram;

determine 360 match scores, where each match score is determined by comparing the target radial histogram to a different one of the initial radial histogram and 359 rotated radial histograms, wherein the rotated radial histograms are generated based on the initial radial histogram, and wherein the comparisons take into account a scaling factor based on a ratio of the range of the initial radial histogram and the range of the target radial histogram; and

identify, based on the match scores, an offset rotation between the baseline pattern digital image and the input digital image.

2. The non-transitory storage device of claim 1, wherein a pixel that is on is counted in only one sector.

3. The non-transitory storage device of claim 1, wherein the machine instructions, when executed by the processing resources, further cause the processing resource to:

determine a maximum number of pixels counted in the 360 elements of the initial radial histogram;

determine a minimum number of pixels counted in the 360 elements of the initial radial histogram;

determine a maximum number of pixels counted in the 360 elements of the target radial histogram; and

determine a minimum number of pixels counted in the 360 elements of the target radial histogram.

4. The non-transitory storage device of claim 1, wherein the machine instructions, when executed by the processing resources, further cause the processing resource to generate 359 rotated radial histograms from the initial radial histogram by shifting the values of the initial radial histogram a number of elements based on the sequence position of each rotated radial histogram and further cause the processing resource to determine a 2-dimensional translation offset between the baseline pattern digital image and the input digital image based on the match scores.

5. The non-transitory storage device of claim 1, wherein the comparisons between of the target radial histogram to each of the initial radial histogram and the 359 rotated radial histograms are performed concurrently.

6. A non-transitory storage device including machine instructions that, when executed by a processing resource, cause the processing resource to:

identify pixels, in a baseline pattern digital image and in an input digital image, that are determined to be on based on a value of a respective pixel meeting a pre-defined threshold criterion;

traverse each of the pixels in the baseline pattern digital image and in the input digital image one time to determine how many of the pixels that are on are contained in each of N of sectors a circle, wherein N>

1, wherein each sector subtends a degree of angle, and wherein the N sectors comprise the whole circle;

assign to each of N elements of an initial radial histogram, and to each of N elements of a target radial histogram, the number of on pixels in that element;

determine a range of the initial radial histogram as a difference between a maximum number of pixels and a minimum number of pixels counted in the N elements of the initial radial histogram;

determine a range of the target radial histogram as a difference between a maximum number of pixels and a minimum number of pixels counted in the N elements of the target radial histogram;

determine N match scores, where each match score is determined by comparing the target radial histogram to a different one of the initial radial histogram and N−

1 rotated radial histograms, wherein the rotated radial histograms are generated based on the initial radial histogram, and wherein the comparisons take into account a scaling factor based on a ratio of the range of the initial radial histogram and the range of the target radial histogram; and

identify, based on the match scores, an offset rotation between the baseline pattern digital image and the input digital image.

7. The non-transitory storage device of claim 6, wherein a pixel that is on is counted in only one sector.

8. The non-transitory storage device of claim 6, wherein the machine instructions, when executed by the processing resources, further cause the processing resource to:

determine a maximum number of pixels counted in the N elements of the initial radial histogram;

determine a minimum number of pixels counted in the N elements of the initial radial histogram;

determine a maximum number of pixels counted in the N elements of the target radial histogram; and

determine a minimum number of pixels counted in the N elements of the target radial histogram.

9. The non-transitory storage device of claim 6, wherein the machine instructions, when executed by the processing resources, further cause the processing resource to generate N−

1 rotated radial histograms from the initial radial histogram by shifting the values of the initial radial histogram a number of elements based on the sequence position of each rotated radial histogram and further cause the processing resource to determine a 2-dimensional translation offset between the baseline pattern digital image and the input digital image based on the match scores.

10. The non-transitory storage device of claim 6, wherein the comparisons between of the target radial histogram to each of the initial radial histogram and the N−

1 rotated radial histograms are performed concurrently.

11. A system comprising:

a processing resource; and

a non-transitory storage device including machine instructions that, when executed by the processing resource, cause the processing resource to;

identify pixels, in a baseline pattern digital image and in an input digital image, that are determined to be on based on a value of a respective pixel meeting a pre-defined threshold criterion;

traverse each of the pixels in the baseline pattern digital image and in the input digital image one time to determine how many of the pixels that are on are contained in each of N of sectors a circle, wherein N>

1, wherein each sector subtends a degree of angle, and wherein the N sectors comprise the whole circle;

assign to each of N elements of an initial radial histogram, and to each of N elements of a target radial histogram, the number of on pixels in that element;

determine a range of the initial radial histogram as a difference between a maximum number of pixels and a minimum number of pixels counted in the N elements of the initial radial histogram;

determine a range of the target radial histogram as a difference between a maximum number of pixels and a minimum number of pixels counted in the N elements of the target radial histogram;

determine N match scores, where each match score is determined by comparing the target radial histogram to a different one of the initial radial histogram and N−

1 rotated radial histograms, wherein the rotated radial histograms are generated based on the initial radial histogram, and wherein the comparisons take into account a scaling factor based on a ratio of the range of the initial radial histogram and the range of the target radial histogram; and

identify, based on the match scores, an offset rotation between the baseline pattern digital image and the input digital image.

12. The system of claim 11, wherein a pixel that is on is counted in only one sector.

13. The system of claim 11, wherein the machine instructions, when executed by the processing resources, further cause the processing resource to:

determine a maximum number of pixels counted in the N elements of the initial radial histogram;

determine a minimum number of pixels counted in the N elements of the initial radial histogram;

determine a maximum number of pixels counted in the N elements of the target radial histogram; and

determine a minimum number of pixels counted in the N elements of the target radial histogram.

14. The system of claim 11, wherein the machine instructions, when executed by the processing resources, further cause the processing resource to generate N−

1 rotated radial histograms from the initial radial histogram by shifting the values of the initial radial histogram a number of elements based on the sequence position of each rotated radial histogram and further cause the processing resource to determine a 2-dimensional translation offset between the baseline pattern digital image and the input digital image based on the match scores.

15. The system of claim 11, wherein the comparisons between of the target radial histogram to each of the initial radial histogram and the N−

1 rotated radial histograms are performed concurrently.