Abstract:
A method and an apparatus automatically detect vessels in a diagnostic image. The method according to one embodiment accesses digital image data representing a diagnostic image; detects vessel candidates in the diagnostic image by processing the diagnostic image data, the step of detecting vessel candidates including identifying edge pixel pairs of vessels in a diagnostic image by iteratively adjusting a plurality of constraints relating to a general direction and shape of a vessel for a next iteration of edge pixel pair identification in a diagnostic image; and determines whether the plurality of edge pixel pairs form a vessel using learned features.

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to a digital image processing technique, and more particularly to a method and apparatus for detecting vessels in a diagnostic image. 
   2. Description of the Related Art 
   Medical problems can be diagnosed from mammography images by recognizing and detecting microcalcifications. A key problem with the aforementioned methodology is the large number of false positives (FPs) that occur in vascular regions as the sensitivity of the calcification detection algorithm is increased. An example of an FP is a vascular region mistakenly identified as a microcalcification. Such large number of FPs occurs because the calcification detection algorithm is easily confused by high frequency structure of vessels present in mammography images. An additional challenge to accurate detection and recognition of calcifications is the fact that signals generated by isolated calcifications are similar to signals generated by vessels. Since calcifications located within vessels are benign and therefore of no interest, an automated detection system that identifies calcifications in mammography images must identify vascular regions as well. An automated calcification detection system should therefore contain a module that identifies vascular regions and then rules out vascular FP finds. Additional modules in the automated detection system will identify FPs from other sources. The result is a calcification detection system that operates at high levels of precision and specificity. 
   The techniques currently used to detect and/or enhance the appearance of vascular images in retinal images or arteriograms (DSA) do not work for mammography. The general problem with these approaches is that the edge profiles are not always manifested with a strong contrast against the background. Furthermore, in basing edge detection solely on edge derivatives, one is highly susceptible to noise in images leading to non-robust results. 
   A few publications have studied automated identification of vessel contours. One such technique is described in “Automated Identification of Vessel Contours in Coronary Arteriograms by an Adaptive Tracking Algorithm”,  Ying Sun, IEEE Trans. Med. Imag ., Vol. 8, No. 1 (March 1989). However, with the method described in this work, one will have to manually select a starting point to begin tracking. This makes the detection process semi-automated. Secondly, the use of a matched filter in the above mentioned application to enhance the profile of vessels works only under the assumption of a known structure and scale of vessels, and a low level of image noise. This is unlikely to be the case for mammography images. 
   Another technique is described in “Mapping the Human Retina”,  Section  6, Pinz et al.,  IEEE Trans. Medical Imaging , vol. 17, no. 4, pp. 606-619, 1998. In this publication a retinal map is created from scanning laser ophthalmoscope (SLO) images by finding matching edge pairs of vessels. The search range has constraints such as a minimum and maximum width, opposite gradients, and angle between edge pixel pairs. Best pixel pairs are decided based solely upon gradient. Since vessels present in mammography images have discontinuous edges and exhibit high noise, one needs to use additional constraints in edge detection. 
   SUMMARY OF INVENTION 
   The present invention is directed to a method and an apparatus for automatically detecting vessels in a diagnostic image. According to a first aspect of the present invention, a method of automatically detecting vessels in a diagnostic image comprises: accessing digital image data representing a diagnostic image; and detecting vessel candidates in the diagnostic image by processing the diagnostic image data. The step of detecting vessel candidates includes: identifying edge pixel pairs of vessels in a diagnostic image, by iteratively adjusting a plurality of constraints relating to a general direction and shape of a vessel for a next iteration of edge pixel pair identification in a diagnostic image; and determining whether the plurality of edge pixel pairs form a vessel, using features learned from previous data. 
   According to a second aspect of the present invention, an apparatus for automatically detecting vessels in a diagnostic image comprises: an image data unit for providing digital image data representing a diagnostic image; and a vessel candidate detecting unit for detecting vessel candidates in the diagnostic image by processing the diagnostic image data. The vessel candidate detecting unit detects vessel candidates by identifying edge pixel pairs of vessels in the diagnostic image, by iteratively adjusting a plurality of constraints relating to a general direction and shape of a vessel for a next iteration of edge pixel pair identification in the diagnostic image, and determining whether the plurality of edge pixel pairs form a vessel, using features learned from previous data. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Further aspects and advantages of the present invention will become apparent upon reading the following detailed description in conjunction with the accompanying drawings, in which: 
       FIG. 1  is a block diagram of a system for automatic and dynamic vessel detection according to an embodiment of the present invention; 
       FIG. 2  is a block diagram illustrating in more detail aspects of the image processing unit of the automatic and dynamic vessel detection system illustrated in  FIG. 1  according to an embodiment of the present invention; 
       FIG. 3  is a flow diagram illustrating operations performed by an edge map detector unit to generate an edge map of an image containing vessels according to an embodiment of the present invention; 
       FIG. 4A  illustrates an exemplary image containing vessels; 
       FIG. 4B  illustrates an exemplary result of generating an edge map of an image containing vessels according to the implementation of the present invention illustrated in  FIG. 3 ; 
       FIG. 5  is a flow diagram illustrating operations performed by a support vector machine classifier detection unit on an edge map to identify image candidates that do not contain any vessels according to an embodiment of the present invention; 
       FIG. 6A  illustrates an exemplary edge map containing significant edge structure; 
       FIG. 6B  illustrates an exemplary edge map image not containing significant edge structure according to the implementation of the present invention illustrated in  FIG. 5 ; 
       FIG. 7  is a flow diagram illustrating operations performed by a vessel detection unit according to an embodiment of the present invention; 
       FIG. 8A  is a general flow diagram illustrating a technique for fitting a line to a binary edge map of an image containing vessels according to an embodiment of the present invention; 
       FIG. 8B  illustrates an exemplary result of fitting a line to a binary edge map of an image containing vessels according to an embodiment of the present invention; illustrated in  FIG. 8A ; 
       FIG. 9  is a general flow diagram illustrating a technique for tracking edges of vessels using fitted lines in a binary edge map of an image containing vessels according to an embodiment of the present invention; 
       FIG. 10  is a flow diagram illustrating a technique for finding the best global pixel pair to start tracking of edges of vessels for an image containing vessels according to an embodiment of the present invention; 
       FIG. 11A  illustrates aspects of the operation for finding the best global pixel pair to start tracking of edges for an image containing vessels according to an embodiment of the present invention illustrated in  FIG. 10 ; 
       FIG. 11B  illustrates aspects of the operation for selecting the best global pixel pair to start tracking of edges for an image containing vessels according to an embodiment of the present invention illustrated in  FIG. 10 ; 
       FIG. 12  is a flow diagram illustrating a technique for finding the second best pixel pair adjacent to the best global pixel pair to track the edges of an image containing vessels according to an embodiment of the present invention; 
       FIG. 13  is a flow diagram illustrating a technique for iteratively and dynamically determining the next pairs of pixels that track edges of vessels once the first two pairs are found, without any initial assumptions on the direction and shape of the structure according to an embodiment of the present invention; 
       FIG. 14A-FIG .  14 F illustrate aspects of the operation for iteratively and dynamically determining the next pairs of pixels that track edges once the first two pairs are found, without any initial assumptions on the direction and shape of the structure according to an embodiment of the present invention illustrated in  FIG. 13 ; 
       FIG. 15  is a flow diagram illustrating a technique for deriving a final score from tracked edges of vessels in an image containing vessels according to an embodiment of the present invention; 
       FIG. 16  is a flow diagram illustrating aspects of the classification process for identifying the image as vascular according to an embodiment of the present invention; and 
       FIG. 17A-FIG .  17 B illustrate an exemplary input and output of the vessel detection module according to an embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
   Aspects of the invention are more specifically set forth in the accompanying description with reference to the appended figures.  FIG. 1  is a block diagram of a system for automatically detecting vessels in a diagnostic image according to an embodiment of the present invention. The system  100  illustrated in  FIG. 1  includes the following components: an image input device  20 ; an image processing unit  30 ; a printing unit  40 ; a user input unit  50 ; and a display  60 . Operation of the system in  FIG. 1  will become apparent from the following discussion. 
   The image input device  20  provides digital image data representing a diagnostic image. The image input device  20  may be one or more of any number of devices providing digital image data derived from a radiological film or a digital system. Such an input device may be a scanner for scanning black and white or color images from a film-screen. The input device may be one or more of any number of devices for providing digital data derived from a diagnostic image, e.g., a recording medium (a CD-R, floppy disk, USB drive), or a network connection. The image-processing unit  30  receives digital image data from the image input device  20  and performs automatic detection of vessels in a manner discussed in detail below. A user, e.g., a radiology specialist at a medical facility, may view outputs of image processing unit  30  via display  60  and may input commands to the image processing unit  30  via the user input device  50 . In the embodiment illustrated in  FIG. 1 , the user input device  50  includes a keyboard  52  and a mouse  54 . In addition to performing automatic detection of vessels in accordance with embodiments of the present invention, the image processing unit  30  may perform additional image processing functions in accordance with commands received from the user input device  50 . The printing unit  40  receives the output of the image processing unit  30  and generates a hard copy of the processed image data. In the environment of a medical facility, the printing unit  40  may take various forms, such as a laser printer. In addition or as an alternative to generating a hard copy of the output of the image processing unit  30 , the processed image data may be returned to the patient as an image file, e.g., via a portable recording medium or via a network (not shown). 
     FIG. 2  illustrates details of the image processing unit  30  for performing automatic vessel detection according to an embodiment of the present invention. As shown in  FIG. 2 , the image processing unit  30  according to this embodiment includes: an image memory  32 , which receives digital image data from the image input device  20 ; an edge map detector  34 ; a support vector machine classifier detector  36 ; and a vessel detection module  38 . Although the various components of  FIG. 2  are illustrated as discrete elements, such an illustration is for ease of explanation and it should be recognized that certain operations of the various components may be performed by the same physical device, e.g., by one or more microprocessors. Generally, the arrangement of elements for the image processing unit  30  illustrated in  FIG. 2  performs edge map detection to generate an edge map of a diagnostic image, support vector machine classification to identify edge map regions that do not contain any vessels, and vessel detection to identify all vessels in the diagnostic image. Operation of the components of the image processing unit  30  illustrated in  FIG. 2  will be next described with reference to  FIGS. 3-17 . 
     FIG. 3  is a flow diagram illustrating operations performed by the edge map detector  34  in accordance with an embodiment of the present invention. Initially, the edge map detector unit  34  accesses digital image data from the image memory  32  to process the image under consideration (S 112 ). The edge map detector  34  then divides the digital image into regions of interest (ROIs) centered on candidate microcalcifications (S 114 ). A region of interest is large enough to contain sufficient information to identify vessels, yet small enough so that vessels located inside are piecewise linear. Along with some other sizes, 64-by-64 pixel regions of interest satisfy this requirement. Pixel size and resolution in image data determine optimum size of ROIs. An edge operator is applied to each region of interest. A Sobel mask (S 116 ) may be such an edge operator. A threshold is applied to each region of interest convolved with a Sobel mask (S 118 ). The result of the previous step is a binary edge map generated for each region of interest. Isolated pixels and edges are removed from the binary edge map, because such pixels represent noise in the initial digital image (S 120 ). Along with some other methods, one way to identify isolated edges is to select all edges that contain less than 5 connected edge pixels. The resulting binary edge map (S 122 ) is then input into the support vector machine classifier detector  36 . 
     FIG. 4A  illustrates an exemplary digital image containing vessels, and  FIG. 4B  illustrates an exemplary result of generating the edge map of the image in  FIG. 4A  according to the implementation of the present invention illustrated in  FIG. 3 ; 
     FIG. 5  is a flow diagram illustrating operations performed by the support vector machine classifier detector  36  in accordance with an embodiment of the present invention. The edge map image (S 122 ) is input into the support vector machine classifier detector  36 . The support vector machine classifier detector  36  decides whether each region of interest contains at least one vessel. All connected edges in the edge map image are counted (S 180 ). If the total number of edges is too small or too large, the support vector machine classifier detector  36  decides that the region of interest does not contain vessels. Possible upper and lower bounds for total number of edges in a 64-by-64 pixel region of interest are 1200 and 60. A region of interest that does not contain any vessels is not a vascular false positive and is not further processed by the vessel detection module  38  (S 184 ). If the total number of edges in the edge map lies between the above mentioned lower and upper bounds, the support vector machine classifier detector  36  decides that the region of interest contains significant edge structure and therefore has at least one vessel (S 188 ). Such a region of interest is sent to the vessel detection module  38 . 
     FIG. 6A  illustrates an exemplary image containing significant edge structure, which is sent to the vessel detection module  38 .  FIG. 6B  illustrates an exemplary image without significant edge structure, that is not further processed, according to the implementation of the present invention illustrated in  FIG. 5 ; 
     FIG. 7  is a flow diagram illustrating operations performed by a vessel detection module  38  in accordance with an embodiment of the present invention. A binary edge map of a vascular region of interest is sent from the support vector machine classifier detection unit  36  to the vessel detection unit  38  (S 220 ). A line is fitted to the binary image map in order to estimate directions of vessels inside the edge map (S 222 ). Proximity of the fitted line to center of the region of interest is measured by using a critical distance parameter (S 224 ). Critical distance between a fitted line and center of a region of interest can be roughly estimated as being on the order of magnitude of typical maximum vessel thickness in diagnostic images. If the fitted line in the region of interest is not within critical distance from the center of the region of interest, then no vessel exists that passes through the center of the region of interest. Therefore the region of interest either contains no vessels or contains vessels that do not pass through the candidate microcalcification in the center. Such region of interest is not further processed in the vessel detection module  38  (S 226 ). If the fitted line is within critical distance from the center of the region of interest, the region of interest is sent to the tracking step. The fitted line in the region of interest will be tracked (S 228 ). The outputs of the tracking step are pairs of edges that delineate vessels. A test is performed to decide whether identified vessels pass through the center of the region of interest (S 230 ). If no vessels pass through the center of the region of interest, the region of interest either contains no vessels or contains vessels that do not pass through the center candidate microcalcification. Such region of interest is not further processed in the vessel detection module  38  (S 232 ). If at least one vessel goes through the center of the region of interest, the region of interest is sent to the next step. A final feature vector score for the center-crossing vessel is computed from various characteristics of tracked vessel edges (S 234 ). The feature vector score is then input into a new support vector machine classifier (S 236 ). The support vector machine classifier operates based on a trained ideal threshold value. The training of the support vector machine classifier is done off-line using a number of regions of interest that are either vascular or non-vascular. These regions of interest are manually classified to establish a notion of vascularity or non-vascularity for the support vector machine classifier. The support vector machine classifier is then presented with new example regions that are either vascular or non-vascular, and learns how to establish a threshold and return feature vector scores for example regions to indicate degree of vascularity. When a feature vector score for the center-crossing vessel (S 234 ) is input into the trained support vector machine classifier (S 236 ), the support vector machine classifier compares the feature vector score with the trained ideal threshold value. If the feature vector score for the center-crossing vessel is greater than the threshold value, the region of interest is vascular and therefore a false positive in the context of a calcification detection algorithm. False positives are removed (S 240 ). If the feature vector score for the center-crossing vessel is lower than the threshold value, the region of interest is not vascular. Other modules will then be applied to the non-vascular region of interest to determine if it is indeed a calcification (S 238 ). 
     FIG. 8A  is a general flow diagram illustrating a technique for fitting lines to a binary edge map of an image. Weighting is used to favor edges close to center of a region of interest. For this purpose, a new edge map data structure that holds all of the binary edge points is created, where each edge may be included more than once. The number of times each edge is included is inversely proportional to the distance between the edge and the center of the region of interest. Hence edges close to center of region of interest carry more weight than edges away from center. The technique then maximizes the variance of the edge map data structure across its first principal component using a single valued decomposition (S 270 ). The output is a binary edge map with a fitted line (S 272 ). 
     FIG. 8B  illustrates an exemplary result of fitting a line to a binary edge map of an image containing vessels according to an embodiment of the present invention illustrated in  FIG. 8A ; 
     FIG. 9  is a flow diagram illustrating operations performed by the line-tracking step of the vessel detection module  38 . Given a binary edge map with a fitted line for a region of interest (S 272 ), a search is undertaken in the direction of the fitted line to determine the best global edge pixel pair (S 290 ). Identification of the best global edge pixel pair locates a vessel in the region of interest. The method then iteratively finds edge pixels that delineate the edge walls of vessels using a tracking mechanism. A second edge pair of pixels is found perpendicular to the fitted line using a connectivity constraint placed on this new pair and the best overall edge pixel pair (S 292 ). Once two pairs of edge pixels are identified, the rest of the edge pixel pairs are iteratively found (S 294 ). New edge pixel pairs are found using previous two pairs that were found but skipping the pair before the last found pair. 
     FIG. 10  is a flow diagram illustrating a technique for finding the best global edge pixel pair to start tracking of edges for an image containing vessels according to an embodiment of the present invention. Perpendicular lines to the fitted line are generated at equal intervals (S 320 ) along the fitted line of a binary edge map (S 272 ). Pairs of pixels most likely to be part of vessel edges are searched along each perpendicular line (S 322 ). An individual score value is assigned to each pixel pair found along perpendicular lines (S 324 ). The score tallies positions, gradients and intensities of the two pixels in each pair within the region of interest. The higher the score, the more likely it is that the pixel pair belongs to vessel edges. The pair with the highest score is selected from among all pixel pairs (S 326 ). This pair is the best overall edge pixel pair. 
     FIG. 11A  illustrates aspects of the operation for finding the best global edge pixel pair to start tracking of edges for an image containing vessels according to an embodiment of the present invention illustrated in  FIG. 10 . Equidistant perpendicular lines L 1 , L 2 , L 3  to the fitted line L 0  are generated. 
     FIG. 11B  illustrates aspects of the operation for finding the best global edge pixel pair to start tracking of edges for an image containing vessels according to an embodiment of the present invention illustrated in  FIG. 10 . Pairs of pixels P 1 , P 2 , P 3 , P 4  that are likely to be part of edges are found. The best global edge pixel pair is P 5 . 
     FIG. 12  is a flow diagram illustrating a technique for finding the second best pixel pair adjacent to the best global edge pixel pair to track the edges of an image containing vessels according to an embodiment of the present invention. A search on equally distanced directions perpendicular to the fitted line takes place (S 392 ), while moving away from the best global edge pixel pair in either direction (S 390 ). A connectivity constraint (S 394 ) is placed on the candidate pair and the best global edge pixel pair while searching for the second edge pixel pair. The connectivity constraint is related to the distance between the perpendicular directions to the fitted line and the angle between the best overall edge pixel pair and a candidate pair. Such angle must be less than 90 degrees. The highest connectivity score is awarded to a new pixel pair that makes an angle of 0 degrees with the best global edge pixel pair. The pixel pair with the highest connectivity score becomes the second pair of edge pixels (S 396 ). 
     FIG. 13  is a flow diagram illustrating a technique for iteratively and dynamically determining the next pairs of pixels that track edges once the first two pairs are found according to an embodiment of the present invention. The first two edge pixel pairs found (S 410 ) are used to estimate the tracking direction in search of the next edge pixel pair. Two directional vectors are generated from the first two edge pixel pairs (S 412 ). A search line perpendicular to the average of directional vectors is found using a connectivity constraint (S 414 ). After the third edge pixel pair is found along the search line (S 416 ), the technique iteratively continues. The tracking direction of search for each new edge pixel pair is determined by using the last edge pixel pairs found skipping the pair before the last pair found (S 418 ). The search for edge pixel pairs continues until the fitted line reaches the edges of the region of interest (S 420 ). 
     FIG. 14A-FIG .  14 F illustrate aspects of the operation for iteratively and dynamically determining the next pairs of pixels that track edges once the first two pairs are found, without any initial assumptions on the direction and shape of the structure according to an embodiment of the present invention. The best global pixel pair P 5  and the second pixel pair P 6  adjacent to pair P 5  generate two directional vectors V 1  and V 2 . Following directional vectors V 1  and V 2 , two points M 1  and M 2  are found which define a search line. Points M 1  and M 2  are two pixels or less away from pair P 6 . Points M 1  and M 2  define the search line L 1 . The search line L 10  is not necessarily perpendicular to the vectorial average of vectors V 1  and V 2 . The closest line to L 10  that is also perpendicular to the vectorial average of vectors V 1  and V 2  becomes the new search line L 12 . The pair of pixels on search line L 12  with highest tracking score becomes the next pixel pair P 7  to be part of the tracking operation. The tracking score is a weighted sum of parameters that may include edge characteristics, position, connectivity parameters, gradient magnitudes and angles. New directional vectors V 3  and V 4  are generated from pixel pairs P 7  and P 5 . The process repeats to find the next edge pixel pair P 8  to be part of tracking operation, and so on. 
     FIG. 15  is a flow diagram illustrating a technique for deriving a final score for a region of interest containing vessels according to an embodiment of the present invention. Each individual score (S 490 ) calculated for a pixel pair during the edge tracking operation updates a final feature vector (S 492 ). Additional measures pertinent to the tracking process, such as curvature, length and principal components can be incorporated into the final feature vector. When the edge of the region of interest is reached (S 494 ), the final feature vector is complete with score information from all edge pixel pairs and the final feature vector score for the region of interest is output. 
     FIG. 16  is a flow diagram illustrating aspects of the vessel identification process based on final feature vector score according to an embodiment of the present invention. The final feature vector of the region of interest is input into a support vector machine vessel classifier. The support vector machine vessel classifier returns a prediction value based on the feature vector. If the prediction value is greater than a given threshold (S 510 ), the set of edge pixel pairs that generated the final feature vector score delineate a vessel (S 512 ). The region of interest is therefore vascular. A vascular calcification region is a false positive, and it is removed (S 514 ). If the prediction value is smaller than a given threshold (S 510 ), the pixel pairs that generated the final feature vector score did not in fact belong to a vessel (S 516 ). The vessel detection algorithm stops, and the region of interest must be sent to other modules for further investigation (S 518 ). 
     FIG. 17A-FIG .  17 B illustrate an exemplary output of the vessel detection module  38 , according to an embodiment of the present invention. Continuously updated tracked edges identify the meandering vessel in the image (L 530 ). Lines L 532  and L 534  are tracked edges of vessel L 530 . 
   Although detailed embodiments and implementations of the present invention have been described above, it should be apparent that various modifications are possible without departing from the spirit and scope of the present invention.