US6404908B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for fast detection of lines in medical images
Assignee: Hologic Inc
•
Filing: 1998-05-28
•
Granted: 2002-06-11
•
Expires: 2018-05-28
Abstract
Abstract A method an apparatus for detecting lines in medical images is disclosed, wherein a direction image array and a line image array are formed by filtering a digital image with a single-peaked filter, convolving the resultant array with second order difference operators oriented along the horizontal, vertical, and diagonal axes, and computing the direction image arrays and line image arrays as direct scalar functions of the results of the second order difference operations. Advantageously, line detection based on the use of four line operator functions along the horizontal, vertical, and diagonal directions in accordance with the preferred embodiments actually results in fewer computations than line detection based on the use of three line operator functions. In particular, because of the special symmetries involved, 3x3 second order difference operators may be effectively used. Moreover, the number of computations associated with the second order difference operations may be achieved with simple register shifts, additions, and subtractions, yielding an overall line detection process that is significantly less computationally intensive than prior art algorithms. Also according to a preferred embodiment, computational complexity is reduced by selecting a separable single-peaked filter, and sequentially convolving the digital image with the component kernels of the separable single-peaked filter.
Inventors
- 👤 Alexander C. Schneider
- 👤 Jimmy R. Roehrig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 21:51
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/10; G06T7/12; G06V; G06V10/00; G06V10/40; G06V10/44; G06V10/443; G06T2207/00; G06T2207/10; G06T2207/10116; G06T2207/30; G06T2207/30004; G06T2207/30068
Claims Analysis
Total Claims: 71
Claim 1
Independent Claim
88 words
A method for detecting lines in a digital image, comprising the steps of: filtering said digital image to produce a filtered image array; convolving said filtered image array with a plurality of second order difference operators designed to extract second order directional derivative information from said filtered image array in a predetermined set of directions; processing information resulting from said step of convolving to produce a line image; wherein said predetermined set of directions is selected to correspond to an aspect ratio of said second order difference operators.
Claim 2
Independent Claim
88 words
A method for detecting lines in a digital image, comprising the steps of: filtering said digital image to produce a filtered image array; convolving said filtered image array with a plurality of second order difference operators designed to extract second order directional derivative information from said filtered image array in a predetermined set of directions; processing information resulting from said step of convolving to produce a line image; wherein said predetermined set of directions is selected to correspond to an aspect ratio of said second order difference operators.
Claim 3
Dependent Claim
32 words
The method of claim 1 , wherein said second order difference operators are square kernels, and wherein said predetermined set of directions includes the directions of 0, 45, 90, and 135 degrees.
Claim 4
Dependent Claim
15 words
The method of claim 2 , wherein said second order difference operators are 3×3 kernels.
Claim 5
Dependent Claim
33 words
The method of claim 1 , said step of filtering said digital image array comprising the steps of: selecting a single-peaked filter kernel; and convolving said digital image with said single-peaked filter kernel.
Claim 6
Dependent Claim
64 words
The method of claim 4 , wherein said single-peaked filter kernel is a separable function comprising the convolution of a first one dimensional kernel and a second one dimensional kernel, and wherein said step of convolving said digital image with said single-peaked filter kernel comprises the steps of convolving said digital image with said first one dimensional kernel and said second one dimensional kernel.
Claim 7
Dependent Claim
14 words
The method of claim 4 , wherein said single-peaked filter kernel is a Gaussian.
Claim 8
Dependent Claim
98 words
The method of claim 1 , wherein said step of convolving said filtered image array comprises the steps of: convolving said filtered image array with 3×3 second order difference operators designed to extract second order derivative information along the 45 degree and 135 degree directions; and subsequent to said step of convolving said filtered image array with 3×3 second order difference operators designed to extract second order derivative information along the 45 degree and 135 degree directions, multiplying the results of said step by a constant correction factor to accommodate for more widely spaced sampling along the diagonals.
Claim 9
Independent Claim
146 words
A method for detecting lines in a digital image, comprising the steps of: selecting a spatial scale parameter, said spatial scale parameter corresponding to a desired range of line widths for detection; convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel each having a size related to said spatial scale parameter; producing a line image based on second-order spatial derivatives of said filtered image array; wherein said line image is produced from said digital image using a number of computations that is substantially proportional to the spatial scale parameter such that, as the spatial scale parameter is increased, said number of computations increases at a rate that is less than the rate of increase of the square of the spatial scale parameter.
Claim 10
Independent Claim
146 words
A method for detecting lines in a digital image, comprising the steps of: selecting a spatial scale parameter, said spatial scale parameter corresponding to a desired range of line widths for detection; convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel each having a size related to said spatial scale parameter; producing a line image based on second-order spatial derivatives of said filtered image array; wherein said line image is produced from said digital image using a number of computations that is substantially proportional to the spatial scale parameter such that, as the spatial scale parameter is increased, said number of computations increases at a rate that is less than the rate of increase of the square of the spatial scale parameter.
Claim 11
Dependent Claim
89 words
The method of claim 8 , said step of producing a line image based on second-order spatial derivatives of said filtered image array further comprising the steps of: convolving said filtered image array with a plurality of second order difference operators designed to extract second order directional derivative information from said filtered image array in a predetermined set of directions; and processing information resulting from said step of convolving to produce a line image; wherein said predetermined set of directions includes directions along the diagonals of the digital image.
Claim 12
Dependent Claim
15 words
The method of claim 9 , wherein said second order difference operators are 3×3 kernels.
Claim 13
Dependent Claim
21 words
The method of claim 8 , wherein said first one dimensional kernel and said second one dimensional kernel are single-peaked functions.
Claim 14
Dependent Claim
20 words
The method of claim 8 , wherein said first one dimensional kernel and said second one dimensional kernel are Gaussians.
Claim 15
Independent Claim
187 words
A method for detecting lines in a digital image, comprising the steps of: selecting a spatial scale parameter, said spatial scale parameter corresponding to a desired range of line widths for detection; convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel derived from a separable two dimensional kernel, and said first one dimensional kernel and said second one dimensional kernel each having a size related to said spatial scale parameter; separately convolving said filtered image array with a first, second, and third second order difference operator to produce a first, second, and third resulting array, respectively; computing a direction image array comprising, at each pixel, a first predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; computing a line intensity function array comprising, at each pixel, a second predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; and computing a line image array using information in said line intensity function array.
Claim 16
Independent Claim
187 words
A method for detecting lines in a digital image, comprising the steps of: selecting a spatial scale parameter, said spatial scale parameter corresponding to a desired range of line widths for detection; convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel derived from a separable two dimensional kernel, and said first one dimensional kernel and said second one dimensional kernel each having a size related to said spatial scale parameter; separately convolving said filtered image array with a first, second, and third second order difference operator to produce a first, second, and third resulting array, respectively; computing a direction image array comprising, at each pixel, a first predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; computing a line intensity function array comprising, at each pixel, a second predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; and computing a line image array using information in said line intensity function array.
Claim 17
Dependent Claim
21 words
The method of claim 13 , wherein said first, second, and third second order difference operators each comprise a 3×3 matrix.
Claim 18
Dependent Claim
28 words
The method of claim 13 , wherein said first second order difference operator comprises the difference between a horizontal second order difference operator and a vertical difference operator.
Claim 19
Dependent Claim
32 words
The method of claim 13 , wherein said second second order difference operator comprises the difference between a first diagonal second order difference operator and a second diagonal second order difference operator.
Claim 20
Dependent Claim
16 words
The method of claim 13 , wherein said third second order difference operator is a Laplacian.
Claim 21
Dependent Claim
40 words
The method of claim 13 , wherein said first predetermined scalar function comprises the arc tangent of the quotient of said corresponding pixel value in said second resulting array divided by said corresponding pixel value in said first resulting array.
Claim 22
Dependent Claim
57 words
The method of claim 13 , wherein said second predetermined scalar function comprises the sum of two times the corresponding pixel value in said third resulting array plus the square root of the sum of the squares of the corresponding pixel value in said first resulting array and the corresponding pixel value in said second resulting array.
Claim 23
Dependent Claim
41 words
The method of claim 1 , wherein said step of computing a line image array using information in said line intensity function array comprises the step of using a modified thresholding process based on a histogram of said line intensity function.
Claim 24
Dependent Claim
110 words
A computer-readable medium which can be used for directing an apparatus to detect lines in a digital image, comprising: means for directing said apparatus to filter said image to produce a filtered array; means for directing said apparatus to convolve said filtered image array with a plurality of second order difference operators designed to extract second order directional derivative information from said filtered image array in a predetermined set of directions; means for directing said apparatus to process information resulting from said step of convolving to produce a line image; wherein said predetermined set of directions is selected to correspond to an aspect ratio of said second order difference operators.
Claim 25
Dependent Claim
110 words
A computer-readable medium which can be used for directing an apparatus to detect lines in a digital image, comprising: means for directing said apparatus to filter said image to produce a filtered array; means for directing said apparatus to convolve said filtered image array with a plurality of second order difference operators designed to extract second order directional derivative information from said filtered image array in a predetermined set of directions; means for directing said apparatus to process information resulting from said step of convolving to produce a line image; wherein said predetermined set of directions is selected to correspond to an aspect ratio of said second order difference operators.
Claim 26
Dependent Claim
33 words
The computer-readable medium of claim 21 , wherein said second order difference operators are square kernels, and wherein said predetermined set of directions includes the directions of 0, 45, 90, and 135 degrees.
Claim 27
Dependent Claim
16 words
The computer-readable medium of claim 2 , wherein said second order difference operators are 3×3 kernels.
Claim 28
Dependent Claim
39 words
The computer-readable medium of claim 21 , said means for directing said apparatus to filter said image to produce a filtered array further comprising means for directing said apparatus to convolve said digital image with a single-peaked filter kernel.
Claim 29
Dependent Claim
65 words
The computer-readable medium of claim 21 said means for directing said apparatus to filter said image to produce a filtered array further comprising means for directing said apparatus to convolve said digital image with a separable single-peaked filter kernel by successively convolving said digital image with a first one dimensional component kernel and a second one dimensional component kernel of said separable single-peaked filter kernel.
Claim 30
Dependent Claim
16 words
The computer-readable medium of claim 25 , wherein said separable single-peaked filter kernel is a Gaussian.
Claim 31
Independent Claim
208 words
An apparatus for detecting lines in digital images, said apparatus comprising: a first memory for storing a digital image; a first convolution device capable of convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel derived from a separable two dimensional kernel, and said first one dimensional kernel and said second one dimensional kernel each having a size related to the size of lines being detected; a second convolution device capable of separately convolving said filtered image array with a first, a second, and a third second order difference operator to produce a first, second, and third resulting array, respectively; a first processing device capable of computing a direction image array comprising, at each pixel, a first predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; a second processing device capable of computing a line intensity function array comprising, at each pixel, a second predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; and a third processing device capable of computing a line image array using information in said line intensity function array.
Claim 32
Independent Claim
208 words
An apparatus for detecting lines in digital images, said apparatus comprising: a first memory for storing a digital image; a first convolution device capable of convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel derived from a separable two dimensional kernel, and said first one dimensional kernel and said second one dimensional kernel each having a size related to the size of lines being detected; a second convolution device capable of separately convolving said filtered image array with a first, a second, and a third second order difference operator to produce a first, second, and third resulting array, respectively; a first processing device capable of computing a direction image array comprising, at each pixel, a first predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; a second processing device capable of computing a line intensity function array comprising, at each pixel, a second predetermined scalar function of corresponding pixel values in said first, second, and third resulting arrays; and a third processing device capable of computing a line image array using information in said line intensity function array.
Claim 33
Dependent Claim
21 words
The apparatus of claim 27 , wherein said first, second, and third second order difference operators each comprise a 3×3 matrix.
Claim 34
Dependent Claim
27 words
The apparatus of claim 27 wherein said first second order difference operator comprises the difference between a horizontal second order difference operator and a vertical difference operator.
Claim 35
Dependent Claim
32 words
The apparatus of claim 27 , wherein said second second order difference operator comprises the difference between a first diagonal second order difference operator and a second diagonal second order difference operator.
Claim 36
Dependent Claim
16 words
The apparatus of claim 27 , wherein said third second order difference operator is a Laplacian.
Claim 37
Dependent Claim
40 words
The apparatus of claim 27 , wherein said first predetermined scalar function comprises the arc tangent of the quotient of said corresponding pixel value in said second resulting array divided by said corresponding pixel value in said first resulting array.
Claim 38
Dependent Claim
57 words
The apparatus of claim 27 , wherein said second predetermined scalar function comprises the sum of two times the corresponding pixel value in said third resulting array plus the square root of the sum of the squares of the corresponding pixel value in said first resulting array and the corresponding pixel value in said second resulting array.
Claim 39
Dependent Claim
21 words
The method of claim 1 , wherein said second order difference operators contain elements with magnitudes of 0, 1, and 2.
Claim 40
Dependent Claim
66 words
The method of claim 1 , wherein said step of convolving said filtered image array with a plurality of second order difference operators comprises the steps of: producing a doubled filtered image array through register shifts; subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions.
Claim 41
Dependent Claim
58 words
The method of claim 8 , wherein said step of producing a line image based on second-order spatial derivatives of said filtered image array further comprises the steps of: extracting second order directional derivative information from said filtered image array in a predetermined set of directions; and processing said second order directional information to produce a line image.
Claim 42
Dependent Claim
23 words
The method of claim 8 , wherein said first one-dimensional kernel and said second one-dimensional kernel each have an odd number of elements.
Claim 43
Dependent Claim
19 words
The method of claim 9 , wherein the predetermined set of directions includes 0, 45, 90 and 135 degrees.
Claim 44
Dependent Claim
21 words
The method of claim 9 , wherein said second order difference operators contain elements with magnitudes of 0, 1, and 2.
Claim 45
Dependent Claim
66 words
The method of claim 9 , wherein said step of convolving said filtered image array with a plurality of second order difference operators comprises the steps of: producing a doubled filtered image array through register shifts; subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions.
Claim 46
Dependent Claim
25 words
The method of claim 13 , wherein said first, second and third second order difference operators contain elements with magnitudes of 0, 1, and 2.
Claim 47
Dependent Claim
69 words
The method of claim 13 , wherein said step of separately convolving said filtered image array with a first, second and third second order difference operator comprises the steps of: producing a doubled filtered image array through register shifts; subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions.
Claim 48
Dependent Claim
25 words
The computer readable medium of claim 21 , wherein said plurality of second order difference operators contain elements with magnitudes of 0, 1, and 2.
Claim 49
Dependent Claim
72 words
The computer readable of claim 21 , wherein said means for directing said apparatus to convolve said filtered image array comprises: means for directing said apparatus to produce a doubled filtered image array through register shifts; means for directing said apparatus to subtract elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions.
Claim 50
Dependent Claim
25 words
The apparatus of claim 27 , wherein said first, second and third second order difference operators contain elements with magnitudes of 0, 1, and 2.
Claim 51
Dependent Claim
54 words
The apparatus of claim 27 , wherein said second convolution device is further capable of: producing a doubled filtered image array through register shifts; subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions.
Claim 52
Independent Claim
124 words
A method for detecting lines in a digital image, comprising the steps of: selecting a spatial scale parameter, said spatial scale parameter corresponding to a desired range of line widths for detection; convolving said digital image with a filter to produce a filtered image array, said filter having a size related to said spatial scale parameter; producing a doubled filtered image array through register shifts; and subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions; producing a line image based on second-order spatial derivatives of said filtered image array; and processing information resulting from said step of convolving to produce the line image.
Claim 53
Independent Claim
124 words
A method for detecting lines in a digital image, comprising the steps of: selecting a spatial scale parameter, said spatial scale parameter corresponding to a desired range of line widths for detection; convolving said digital image with a filter to produce a filtered image array, said filter having a size related to said spatial scale parameter; producing a doubled filtered image array through register shifts; and subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions; producing a line image based on second-order spatial derivatives of said filtered image array; and processing information resulting from said step of convolving to produce the line image.
Claim 54
Dependent Claim
22 words
The method of claim 47 , wherein said predetermined set of directions includes the directions of 0, 45, 90 and 135 degrees.
Claim 55
Dependent Claim
15 words
The method of claim 47 , wherein said second order difference operators are square kernels.
Claim 56
Dependent Claim
15 words
The method of claim 47 , wherein said second order difference operators are 3×3 kernels.
Claim 57
Dependent Claim
41 words
The method of claim 47 , said step of convolving said digital image with a filter to produce a filtered image array, comprising the steps of: selecting a single-peaked filter kernel; and convolving said digital image with said single-peaked filter kernel.
Claim 58
Dependent Claim
64 words
The method of claim 51 , wherein said single-peaked filter kernel is a separable function comprising the convolution of a first one dimensional kernel and a second one dimensional kernel, and wherein said step of convolving said digital image with said single-peaked filter kernel comprises the steps of convolving said digital image with said first one dimensional kernel and said second one dimensional kernel.
Claim 59
Dependent Claim
14 words
The method of claim 51 , wherein said single-peaked filter kernel is a Gaussian.
Claim 60
Dependent Claim
77 words
The method of claim 47 , wherein said step of subtracting elements in the filtered image array from the doubled filtered image array comprising the steps of: subtracting elements in the filtered image array from the doubled image array to produce a plurality of first subtracted arrays subtracting elements in the filtered image array from the plurality of first-subtracted arrays to extract second order derivative information from said filtered image array in a predetermined set of directions.
Claim 61
Dependent Claim
121 words
A computer-readable medium which can be used for directing an apparatus to detect lines in a digital image, comprising: means for directing said apparatus to filter said image to produce a filtered array; means for directing said apparatus to produce a doubled filtered array through register shifts; and means for directing said apparatus to subtract elements in the filtered array from the doubled filtered array to extract second order derivative information from said filtered array in a predetermined set of directions; and means for directing said apparatus to process information resulting from said step of subtracting to produce a line image; wherein said predetermined set of directions is selected to correspond to an aspect ratio of said second order difference operators.
Claim 62
Dependent Claim
121 words
A computer-readable medium which can be used for directing an apparatus to detect lines in a digital image, comprising: means for directing said apparatus to filter said image to produce a filtered array; means for directing said apparatus to produce a doubled filtered array through register shifts; and means for directing said apparatus to subtract elements in the filtered array from the doubled filtered array to extract second order derivative information from said filtered array in a predetermined set of directions; and means for directing said apparatus to process information resulting from said step of subtracting to produce a line image; wherein said predetermined set of directions is selected to correspond to an aspect ratio of said second order difference operators.
Claim 63
Dependent Claim
23 words
The computer-readable medium of claim 55 , wherein said predetermined set of directions includes the directions of 0, 45, 90 and 135 degrees.
Claim 64
Dependent Claim
39 words
The computer-readable medium of claim 55 , said means for directing said apparatus to filter said image to produce a filtered array further comprising means for directing said apparatus to convolve said digital image with a single-peaked filter kernel.
Claim 65
Dependent Claim
66 words
The computer-readable medium of claim 55 , said means for directing said apparatus to filter said image to produce a filtered array further comprising means for directing said apparatus to convolve said digital image with a separable single-peaked filter kernel by successively convolving said digital image with a first one dimensional component kernel and a second one dimensional component kernel of said separable single-peaked filter kernel.
Claim 66
Dependent Claim
16 words
The computer-readable medium of claim 55 , wherein said separable single-peaked filter kernel is a Gaussian.
Claim 67
Independent Claim
184 words
An apparatus for detecting lines in digital images, said apparatus comprising: a first memory for storing a digital image; a first convolution device capable of convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel each having a size related to the size of lines being detected; a first register shifting device capable of shifting said digital image to produce a doubled filtered image array; a first subtracting device capable of subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions; a first processing device capable of computing a direction image array comprising, at each pixel, a first predetermined scalar function; a second processing device capable of computing a line intensity function array comprising, at each pixel, a second predetermined scalar; and a third processing device capable of computing a line image array using information in said line intensity function array.
Claim 68
Independent Claim
184 words
An apparatus for detecting lines in digital images, said apparatus comprising: a first memory for storing a digital image; a first convolution device capable of convolving said digital image with a first one dimensional kernel and a second one dimensional kernel to produce a filtered image array, said first one dimensional kernel and said second one dimensional kernel each having a size related to the size of lines being detected; a first register shifting device capable of shifting said digital image to produce a doubled filtered image array; a first subtracting device capable of subtracting elements in the filtered image array from the doubled filtered image array to extract second order derivative information from said filtered image array in a predetermined set of directions; a first processing device capable of computing a direction image array comprising, at each pixel, a first predetermined scalar function; a second processing device capable of computing a line intensity function array comprising, at each pixel, a second predetermined scalar; and a third processing device capable of computing a line image array using information in said line intensity function array.
Claim 69
Dependent Claim
22 words
The apparatus of claim 60 , wherein said predetermined set of directions includes the directions of 0, 45, 90 and 135 degrees.
Claim 70
Dependent Claim
26 words
The apparatus of claim 60 , wherein said first and second one dimensional kernel are each a one dimensional component kernel of a single-peaked filter kernel.
Claim 71
Dependent Claim
15 words
The apparatus of claim 62 , wherein said separable single-peaked filter kernel is a Gaussian.
References Cited (Backward Citations)
US4851984A
Cited
US5537485A
Cited
US5661820A
Cited
US5825910A
Cited
US5627907A
Cited
US5838815A
Cited
US5579360A
Cited
US5799100A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-06-10 | 2005-12-10 | 2006-06-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-06-10 | 2009-12-10 | 2010-06-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-06-10 | 2013-12-10 | 2014-06-11 | $7700.00 | Window Closed / Lapsed |