Method and system for fast detection of lines in medical images

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, 3×3 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.

What is claimed is:  
     
         1 . 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.    
     
     
         2 . 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.  
     
     
         3 . The method of  claim 2 , wherein said second order difference operators are 3×3 kernels.  
     
     
         4 . The method of  claim 3 , said step of filtering said digital image array comprising the steps of: 
 selecting a single-peaked filter kernel; and    convolving said digital mammogram image with said single-peaked filter kernel.    
     
     
         5 . 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 mammogram image with said single-peaked filter kernel comprises the steps of convolving said digital mammogram image with said first one dimensional kernel and said second one dimensional kernel.  
     
     
         6 . The method of  claim 5 , wherein said single-peaked filter kernel is a Gaussian.  
     
     
         7 . The method of  claim 6 , 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 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.    
     
     
         8 . 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.    
     
     
         9 . 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 mammogram image.    
     
     
         10 . The method of  claim 9 , wherein said second order difference operators are 3×3 kernels.  
     
     
         11 . The method of  claim 10 , wherein said first one dimensional kernel and said second one dimensional kernel are single-peaked functions each having an odd number of elements.  
     
     
         12 . The method of  claim 11 , wherein said first one dimensional kernel and said second one dimensional kernel are Gaussians.  
     
     
         13 . 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;    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.    
     
     
         14 . The method of  claim 13 , wherein said first, second, and third second order difference operators each comprise a 3×3 matrix.  
     
     
         15 . The method of  claim 14 , wherein said first second order difference operator comprises the difference between a horizontal second order difference operator and a vertical difference operator.  
     
     
         16 . The method of  claim 15 , wherein said second order difference operator comprises the difference between a first diagonal second order difference operator and a second diagonal second order difference operator.  
     
     
         17 . The method of  claim 16 , wherein said third second order difference operator is a Laplacian.  
     
     
         18 . The method of  claim 17 , wherein said first predetermined scalar function comprises the arctangent of the quotient of said corresponding pixel value in said second resulting array divided by said corresponding pixel value in said first resulting array.  
     
     
         19 . The method of  claim 18 , 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.  
     
     
         20 . The method of  claim 19 , 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.  
     
     
         21 . 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.    
     
     
         22 . 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.  
     
     
         23 . The computer-readable medium of  claim 22 , wherein said second order difference operators are 3×3 kernels.  
     
     
         24 . The computer-readable medium of  claim 23 , 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 mammogram image with a single-peaked filter kernel.  
     
     
         25 . The computer-readable medium of  claim 23 , 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 mammogram 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.  
     
     
         26 . The computer-readable medium of  claim 25 , wherein said separable single-peaked filter kernel is a Gaussian.  
     
     
         27 . 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 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.    
     
     
         28 . The method of  claim 27 , wherein said first, second, and third second order difference operators each comprise a 3×3 matrix.  
     
     
         29 . The method of  claim 28 , wherein said first second order difference operator comprises the difference between a horizontal second order difference operator and a vertical difference operator.  
     
     
         30 . The method of  claim 29 , 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.  
     
     
         31 . The method of  claim 30 , wherein said third second order difference operator is a Laplacian.  
     
     
         32 . The method of  claim 31 , wherein said first predetermined scalar function comprises the arctangent of the quotient of said corresponding pixel value in said second resulting array divided by said corresponding pixel value in said first resulting array.  
     
     
         33 . The method of  claim 32 , 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.