Method and system for identifying extended contours within digital images

• US 10,387,744 B2
• Filed: 06/28/2016
• Issued: 08/20/2019
• Est. Priority Date: 06/22/2016
• Status: Active Grant

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Production LLC (ABBYY Software)
• Inventors: Zagaynov, Ivan Germanovich, Loginov, Vasily Vasilyevich, Lobastov, Stepan Yurievich
• Primary Examiner(s): Wu, Jingge
• Application Number:
  US15/195,726
• Publication Number:
  US 20170372166A1
• Time in Patent Office: 1,148 Days
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 3/4015 Image demosaicing, e.g. colour filter arrays [CFA] or Bayer patterns
• 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/469 Contour-based spatial representations, e.g. vector-coding
• CPC Class Codes: G06V 10/473 using gradient analysis
• 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/507 Summing image-intensity values; Histogram projection analysis
• CPC Class Codes: G06V 10/56 relating to colour

Abstract

The current document is directed to automated methods and systems, controlled by various constraints and parameters, that identify contours in digital images, including curved contours. Certain of these parameters constrain contour identification to those contours in which the local curvature of a contour does not exceed a threshold local curvature and to those contours orthogonal to intensity gradients of at least threshold magnitudes. The currently described methods and systems identify seed points within a digital image, extend line segments from the seed points as an initial contour coincident with the seed point, and then iteratively extend the initial contour by adding line segments to one or both ends of the contour. The identified contours are selectively combined and filtered in order to identify a set of relevant contours for use in subsequent image-processing tasks.

Claims

1. An image-processing subsystem comprising:

one or more memories; and

one or more processors, coupled to the one or more memories, to;

receive a digital image,

identify seed pixels within the digital image coincident with intensity edges, and

for each of the seed pixels,

construct an incipient contour line segment that includes the respective seed pixel, wherein to construct the incipient contour line segment that includes the respective seed pixel, the processor to;

determine a contour direction for the incipient contour line segment;

construct a first vector with a tail coincident with the seed pixel, an orientation direction equal to the determined contour direction, and a length equal to a value of a segment parameter; and

include a segment with endpoints coincident with the tail and a head of the first vector as a first segment in a multi-segment contour,

iteratively extend both ends of the incipient contour line segment along an intensity edge to generate an extended contour line segment, and

store the extended contour line segment in the one or more memories.

2. The image-processing subsystem of claim 1 wherein to identify the seed pixels with the digital image coincident with the intensity edges, the processor to:

employ multiple parameter values that control contour identification comprising;

a segment length L;

a maximum segment inclination α

;

a number of histogram bins h;

a minimum histogram-bin value B; and

a contour radius Re.

3. The image-processing subsystem of claim 1 wherein to identify the seed pixels within the digital image coincident with intensity edges further comprises the processor to:

compress the received digital image to produce one or more compressed digital images for which the difference, in pixels, between the height and width of each compressed digital image is less than a threshold number of pixels;

smooth each compressed digital image;

generate a gradient map for each smoothed, compressed digital image; and

identify seed pixels using the generated gradient map.

4. The image-processing subsystem of claim 3 wherein to smooth each compressed digital image further comprises the processor to apply a smoothing operation to the compressed digital image, the smoothing operation selected from among:

median filtering;

convolution with a Gaussian kernel; and

convolution with an averaging kernel.

5. The image-processing subsystem of claim 3 wherein to generate a gradient map for each smoothed, compressed digital image further comprises the processor to:

allocate a gradient map in memory;

for each pixel of the smoothed, compressed digital image,

for each of three color channels,

compute a gradient magnitude for the pixel;

select the color channel for which the computed gradient magnitude is greatest; and

place indications of the gradient magnitude and gradient orientation for the selected color channel into a corresponding cell or element of the gradient map.

6. The image-processing subsystem of claim 5 wherein to compute a gradient magnitude for the pixel further comprises the processor to:

convolve a G_x, kernel with a color channel of the smoothed, compressed digital image to generate a horizontal-gradient-component map;

convolve a G_y kernel with the color channel of the smoothed, compressed digital image to generate a vertical-gradient-component map; and

compute the gradient magnitude as the square root of the sum of the value stored in the horizontal-gradient-component map for the pixel and the value stored in the vertical-gradient-component map for the pixel.

7. The image-processing subsystem of claim 5 wherein to place the gradient orientation for the selected color channel into a corresponding cell or element of the gradient map further comprises the processor to:

compute the gradient orientation by applying the atan 2 function to the value stored in the vertical-gradient-component map for the pixel and the value stored in the horizontal-gradient-component map for the pixel.

8. The image-processing subsystem of claim 3 wherein to identify seed pixels using the generated gradient map further comprises, the processor to:

convolve the gradient-magnitude values of the generated gradient map with a non-maximum-suppression kernel to generate an intermediate point map; and

apply a thresholding operator to the intermediate point map to generate a point map that contains seed pixels having the largest-valued gradient magnitudes.

9. The image-processing subsystem of claim 8 wherein to identify seed pixels using the generated gradient map further comprises, the processor to:

sort the identified seed pixels in descending order by gradient magnitude.

10. The image-processing subsystem of claim 1 wherein to determine a contour direction for the incipient contour line segment further comprises, the processor to:

for each of multiple candidate directions,

construct a first vector with a tail coincident with the seed pixel, an orientation direction equal to the candidate direction, and a length equal to the value of a segment parameter,

determine an average magnitude of the projections of the gradients of the pixels coincident with the first vector, and

determine a histogram of the gradients of the pixels coincident with the first vector;

select, as a final contour direction, the candidate direction for which average magnitude of the projections has a greatest value; and

when the final contour direction coincides with a detectable intensity edge in the received digital image,

select, as the contour direction, the final contour direction.

11. The image-processing subsystem of claim 10 wherein the final contour direction coincides with a detectable intensity edge in the received digital image when the final contour direction is perpendicular to direction corresponding to a maximum-valued histogram bin or a histogram bin immediately adjacent to the maximum-valued histogram bin and when the average magnitude of the projections of the gradients of the pixels coincident with the first vector is greater than a threshold value.

12. The image-processing subsystem of claim 1 wherein to iteratively extend both ends of the incipient contour line segment along an intensity edge to generate the extended contour line segment further comprises, the processor to:

iteratively

for each end of the contour line segment,

when the end of the contour line segment is not terminated,

attempt to determine a direction of the intensity edge at the end of the contour line segment,

when a direction of the intensity edge is determined, construct a vector at the end of the contour line segment in the determined intensity-edge direction, and

otherwise terminate the end of the contour line segment,

until both ends of the contour line segment are terminated.

13. The image-processing subsystem of claim 12 wherein the direction of the intensity edge at the end of the contour line segment is constrained to be inclined by no more than an angle a to either side of a direction of the contour line segment at the end of the contour line segment.

14. The image-processing subsystem of claim 13 wherein the direction of the contour line segment at the end of the contour line segment is determined as:

a direction of the segment coincident with the end of the contour line segment; and

a direction determined by a least-squares approximation based on a final number of segments at the end of the contour line segment.

15. The image-processing subsystem of claim 1 further comprising, the processor to:

follow identification of contours in each smoothed and compressed image,

combine pairs of contours representing two portions of a common intensity edge separated by a gap of less than a threshold length; and

merge contours identified in multiple smoothed and compressed images.

16. A method comprising:

receiving, by a processor, a digital image, the processor coupled to one or more memories;

identifying, by the processor, seed pixels within the digital image coincident with intensity edges; and

for each of multiple seed pixels,

constructing, by the processor, an incipient contour line segment that includes the respective seed pixel, wherein constructing of the incipient contour line segment that includes the respective seed pixel further comprises;

determining a contour direction for the incipient contour line segment;

constructing a first vector with a tail coincident with the seed pixel, an orientation direction equal to the determined contour direction, and a length equal to a value of a segment parameter; and

including a segment with endpoints coincident with the tail and a head of a first vector as the first segment in a multi-segment contour,

iteratively extending, by the processor, both ends of the incipient contour line segment along an intensity edge to generate an extended contour line segment, and

storing, by the processor, the extended contour line segment in the one or more memories.

17. The method of claim 16 wherein identifying seed pixels within the digital image coincident with intensity edges further comprises:

compressing the received digital image to produce one or more compressed digital images for which the difference, in pixels, between the height and width of each compressed digital image is less than a threshold number of pixels;

smoothing each compressed digital image;

generating a gradient map for each smoothed, compressed digital image; and

identifying seed pixels using the generated gradient map.

18. The method of claim 17 wherein generating a gradient map for each smoothed, compressed digital image further comprises:

allocating a gradient map in memory;

for each pixel of the smoothed, compressed digital image,

for each of three color channels,

computing a gradient magnitude for the pixel;

selecting the color channel for which the computed gradient magnitude is greatest; and

placing indications of the gradient magnitude and gradient orientation for the selected color channel into a corresponding cell or element of the gradient map.

19. The method of claim 17 wherein identifying seed pixels using the generated gradient map further comprises:

convolving the gradient-magnitude values of the generated gradient map with a non-maximum-suppression kernel to generate an intermediate point map; and

applying a thresholding operator to the intermediate point map to generate a point map that contains seed pixels having the largest-valued gradient magnitudes.

20. The method of claim 16 wherein determining a contour direction for the incipient contour line segment further comprises:

constructing a first vector with a tail coincident with the seed pixel, an orientation direction equal to the candidate direction, and a length equal to the value of a segment parameter,

determining an average magnitude of the projections of the gradients of the pixels coincident with the first vector, and

determining a histogram of the gradients of the pixels coincident with the first vector;

selecting, as a final contour direction, the candidate direction for which average magnitude of the projections has a greatest value; and

when the final contour direction coincides with a detectable intensity edge in the received digital image,

selecting, as the contour direction, the final contour direction.

21. Non-transitory computer-readable media having recorded thereon instructions, that when executed by one or more computer processors coupled to one or more memories, perform operations comprising:

receiving a digital image;

identifying seed pixels within the digital image coincident with intensity edges; and

for each of the seed pixels,

constructing an incipient contour line segment that includes the respective seed pixel, wherein constructing of the incipient contour line segment that includes the respective seed pixel further comprises;

determining a contour direction for the incipient contour line segment;

constructing a first vector with a tail coincident with the seed pixel, an orientation direction equal to the determined contour direction, and a length equal to a value of a segment parameter; and

including a segment with endpoints coincident with the tail and a head of the first vector as a first segment in a multi-segment contour,

iteratively extending both ends of the incipient contour line segment along an intensity edge to generate an extended contour line segment, and

storing the extended contour line segment in the one or more memories.