Tags: , view all tags

-- SamPreston - 28 Dec 2007

A Review of Vessel Extraction Techniques and Algorithms

Cemil Kirbas and Francis Quek

January 2003

A Review of Vessel Extraction Techniques and Algorithms

Introduction

Imaging Modalities

Other Segmentation Surveys

[8, 9, 10, 11, 12]

Pattern Recognition Techniques

Pattern recognition techniques deal with the automatic detection or classification of objects or features. In our context, pattern recognition techniques are involved in automatic detection of vessel structures and vessel features.

Multiscale Approaches

Multiscale approaches segment vessels at varying image resolutions. Advantages of this technique include increased processing speed, since an initial 'coarse' segmentation can be done with a lower-resolution image, and greater robustness, since difficult constrictions and branches can be segmented at a higher resolution after obvious structures are segmented at lower resolution, giving some a priori knowledge of the structure to the higher-resolution segmentation. This is related to scale space (need to add reference)

[13] Matching branchpoints in three orthogonal views
[14] Multiresolution analysis based on wavelet transform
[15, 16, 17]

Skeleton-Based (Centerline Detection) Approaches

Skeleton-based approaches generally use a thresholding step followed by either a connectivity description step or a 'thinning' step to extract centerlines, or a graph-based extraction method (info on graph-based extraction?)

[2] Thresholding and connectivity based on [18]
[19] Thresholding and thinning
[20] Thresholding and stenosis / aneurysm detection
[21] Graph-description based extraction followed by concave / convex segment location using curvature
[22] Theoretical review of 3D reconstruction algorithm from X-ray projection images, segmentation of centerline from projection images followed by iterative 3D surface reconstruction from projection images
[23] 3D skeletonization method (5-step method, good results?)
[25, 26, 27, 28, 29, 30, 1, 17]

Ridge-Based Approaches

Ridge-based approaches look at n-D greyscale images as hightfields in (n+1)-D space. For a 2D greyscale image, this would be a 3D heightfield based on image intensity. Assuming that vessels are the brightest (or darkest) portions of images, the ridges of this heightfield correspond to centerlines of vessels ([31]), and can therefore be considered a special case of skeleton-based approach.

General info on ridge-based approaches [32, 33]
Bullitt and Aylward [32, 33, 34, 35, 36, 37], 'cores' method [38]
[6] - basic ridge-based technique?
[39]

Region Growing Approaches

Starting from a set of 'seed points', region-growing techniques add pixels to the segmentation set based on some predefined criteria, such as value similarity or spatial proximity ([40]). Downsides to region growing techniques include the necessity of user-defined seed points and the likelihood of over-segmentation, requiring a post-processing step to eliminate.

[41] thresholding and region growing
[29] segmentation based on temporal, spatial, and structural constraints employing region-growing as the initial segmentation step
[1] complex method, but good results?
[30] Ordered Region Growing -- represents image as an acyclic graph, results in minimal dependence on seed location. Automatic pruning is performed based on branch length.
[42] suite of applications developed by Higgins et al
[43]

Differential-Geometry Based Approaches

Differential geometry based approaches treat images at hypersurfaces, and extract salient features based on gradient and curvature properties of this surface. Crest points (local maxima of the maximum curvature) can be used to find 'Crest Lines' corresponding to centerlines of vessels, and curvature information can be used to detect tubular objects. Since these features are invariant under affine transformations, they are also used extensively in image registration [44, 45, 46].

[47, 48] Good introductions to differential geometry
[49] Direct Anisotropic Diffusion (DAD) - based on (more general method of) [50], method using differentiation of the diffusion in the direction of the gradient, minimum and maximum curvatures. DAD reduces noise without introducing blurring.
[26, 27] Multidimensional vessel extraction method using surface curvature and crest lines
[17] extraction of thin nets? using a multiscale approach using differential geometry features of the image. Same work applied to other domains: [51, 52, 53, 54]
[55, 21]

Matching Filters Approaches

Matching filters approaches involve convolving an image with multiple matched filters. For vessel extraction, this usually means convolving the image with a set of filters to detect vessels of different orientations. A CCA or thinning post-processing step is usually required.

[7] 3D multiscale line enhancement filter to segment curvilinear structures using second-derivative information
[24] multiple oriented linear filters designed for efficiency and cross-validated so as not to enhance non-vessel structures. Thresholding with hysteresis [56] is then used for segmentation.
[57] automated tortuosity measurement based on [58], and followed by a linear classifier algorithm from [59]
[60] background intensity equalization used as preprocessing step
[25] Uses ideas from visual perception modeling stating that relevant parts of noisy scenes are usually grouped together
[61] combines local and region-based properties, use Matched Filter Response [58]
[62] Orientation Space Filtering used to detect X- and T-junctions
[63, 64, 16, 4, 5]

Mathematical Morphology Schemes

Morphology schemes use the ideas of object forms or shapes by using Morphological Operators (MO) which apply Structuring Elements to images. They are typically applied to binary images, but can be extended for greyscale use. Dilation and erosion are the two major morphological operators. The two major segmentation methods related to morphological operators are 'top hat' and 'watershed' operations [65]

Good introductions to morphological operators [66, 40]
[67] nonsmoothing approach which does not assume a constant background
[28] pure MO technique using top-hat and watershed methods to extract edges and centerlines of vessels
[43] Uses MO and region growing to segment large vessels. Author also implemented multiphase analysis process (MRAP)[68], region splitting approach (RSBA)[69], and morphological thresholding (ROSE)[70]
[55] MO with model of undesirable features that could be mistaken for vessels
[70] fairly limited technique using 8 MOs

3D Reconstruction of Vessels

[13, 2, 20, 21, 22]

Model-Based Approaches

Model based approaches use a preexisting vessel model to extract vasculature

Deformable Models

General Info

[8] A survey on deformable models in medical image analysis
[71] Book chapter on segmentation using deformable models
[72] Book chapter on segmentation containing a section on deformable models

Parametric Deformable Models - Active Contours (Snakes)

Deformable models use parametric curves to describe object contours. These curves deform under internal and external forces. Original paper [73] describes active contours or 'snakes' as a generalization of matching a deformable model via energy minimization. Usually seed points or seed regions must be specified by a user. Automatic snake initialization is an ongoing research topic [74, 75]

[3] 3D snakes are used to reconstruct catheter paths from projection images. B-spline representation is used for snakes, and an energy minimization approach is used.
[76] deformable models used in tracking the aorta during cardiac cycle to study compliance, which is a measure of elasticity. Segmentation is performed using a priori knowledge of the shape of the aorta, then the segmentation is refined using a Geometrically Deformable Model and Simulated Annealing.
[77] segmentation using cine-phase information (multiple timesteps) using info from previous frames as seeds for snakes
[78] combination of stochastic (simulated annealing) and probabilistic relaxation (iterated conditional method) techniques with adaptive snakes. Parts are similar to [79]
[80] Multiscale dynamic programming heuristic for detecting, tracking, and matching deformable contours
[4] Orientation-specific filters with B-spline dynamic snakes
[81] Affine Cell Decomposition-based strategy for extraction of complex structures from medical image volumes. Topologically-deformable ACD-based models (T-snakes and T-surfaces) are used to embed deformable models in an ACD framework, allowing deformable models to overcome some traditional limitations (topological invariance) and extract more complex structures.
[5] matching filters with b-spline snake model
[83] extension of traditional snake methods to overcome initialization, parameter setting, and external energy problems -- probably worth looking at
[84] use of Geometrically Deformable Templates to add a shape-based constraint to snake models
[85] computer vision-based approach; 3D contour model based on 3D Fourier shape descriptors, constraints inferred from epipolar geometry.
[86] Probabilistic principal component analysis technique (PPCAT) with 'statistical snakes' to track non-rigid elongated structures. A 'liklihood map' is created from a training set of object profiles using the PPCAT, and the statistical snake learns and tracks image features during growth.
[87] Use of global circular cross-section model with local deformation model to segment the aorta over a series of MR cine phase-contrast images using frame-to-frame coherence constraints
[88, 70, 89, 90, 91, 92]

Geometric Deformable Models and Front Propagation Methods

This section contains the Level Set Method of Osher and Sethian [94] and related methods.

[74, 93] Propagating interfaces under a curvature dependent speed function to model anatomical shapes
[94] Level-Set Method
[95] Fast Marching Method
[96] Good book on Level Set and Fast Marching Methods
[97, 98] Wave propagation and traceback method for extracting vasculature. Wave propagation method discussed in [99]

Parametric Models

Parametric models, as the name implies, models vasculature parametrically -- generally as a series of overlapping ellipsoids, though some techniques use a circular approximation [100]. These methods generally only model healthy vessels, but some work has gone into modeling irregular vessel geometries [101].

[101] reconstruction of vascular structures from two XRA images using Simulated Annealing and an elliptical model for initial segmentation.
[100] uses 'intensity profile amplitude' information to estimate diameter of vessels, and is sensitive to changes in small vessel diameters in cases containing noise and blur.
[102] multiscale model to extract and reconstruct 3D vessels using a cylindrical model and differential geometry techniques involving the Hessian matrix. Based on previous work in [103, 104, 105, 106, 38, 107, 108, 109, 110]. Newer related work in [111].
[112] Pattern classification approach in which vessels are modeled as a stack of overlapping ellipsoids whose parameters are found using the normalized first and second order moments. Centers of ellipsoids are estimated using extended Hough Transform algorithm in 3D. Radial Basis Function described in [113].

Template Matching

Template matching tries to recognize an a priori structure model (template) in an image. The template can be viewed as context, so these methods can also be categorized as contextual methods using a top-down approach. In extracting vasculature, the template is generally a series of nodes and connected segments. Stochastic deformation using a Hidden Markov Model is used in [114, 115], and dynamic programming is used in the recognition process in [114]

[114] extraction of vessels from unsubtracted digital angiograms
[15] multi-resolution technique based on octree representation of MRA. Also categorized under multiscale approaches
[115] method for 3D reconstruction from biplane angiogram images. Uses 'Deformable Template Matcher' to extract vessels with known structure without any preprocessing.
[116] 'Winding number image' [117] is used to topologically classify singular points (paramagnetic markers) to support MR-guided vascular interventions by locating intravascular devices.

Generalized Cylinders Model

Actually a parametric method, generalized cylinders are described separately due to the amount of work on this specific technique. [118, 119] introduce Generalized Cylinders to vision applications. They generally consist of a space curve (axis) and a cross-section function which is 'swept' along the axis. The cross section is usually an ellipse and the axis is usually a spline. Frenet-Serret formulation can also be used [120], as well as 'Extruded Generalized Cylinders' [91].

[124] uses generalized cylinders as well as a Finite-Element mesh-like component to represent fine details of the structures.
[125] semi-automated multi-scale Hessian-based approach for determining position, orientation, and diameter of stenoses.
[126] Hybrid model for vessel representation storing symbolic information such as branching and irregularities as well as volume and surface information. Reconstruction is achieved using Discrete Medial Axis (DMAT) [127].
[128] Object based method for reconstructing arterial trees from projection images. By incorporating a priori knowledge of vessel structure, the reconstruction problem is reformulated as an object estimation problem.
[91] 'Extruded Generalized Cylinder' model, overcomes limitations of spline models such as unintuitive twisting behavior and problems with locally straight splines.
[129, 16]

3D Reconstruction of Vessels

[101, 102, 121, 126, 128, 3]

Tracking-Based Approaches

Tracking-based approaches start from a user-specified position within a vessel, and apply local operators and rules to iteratively add to the 'vessel' region. Centerlines and edges are found by looking at the plane perpendicular to the tracking direction.

[32] 'intensity ridges' are used to approximate the medial axes
[132] 'Fuzzy C-Means' clustering algorithm used to classify pixels into 'vessel' and 'non-vessel' starting from optic nerve in retinal images
[133] Image is processed in 'blocks' using first-order predictive scheme for stable tracking
[134] Maximum-likelihood estimate of adjacent pixels used in tracking narrow blood vessels using the 'direction field' based on centerline directions
[135, 136] interactive interpretation of neurovascular XRA images. Involves user in segmentation, bringing in context and focusing attention.
[137] recursive sequential tracking using morphological tools
[130] Method tracking edges and branches, followed by a sequential tracking step
[138] Syntactic pattern recognition scheme to diagnose vascular abnormalities (normal, widening, narrowing, abnormal)
[139] computer vision techniques for extracting spinal cord contours, fairly basic
[131] Uses graph theory to track two edges simultaneously, as well as some a priori knowledge of vessel shape and size. Heuristic described in [140].
[39] extraction of vessels from retinal images by suppressing pixels not meeting a set of requirements followed by a 'patching and cleaning' phase
[141, 142] 2D tracking technique using 'extrapolation update' scheme
[143] interactive 2D vessel extraction algorithm using watersheds and a merging algorithm to create initial segmentations, then an interactive phase in which the user selects presegmented vessel regions
[144] semiautomated manual 2D segmentation using splines to define regions
[145] matched filters approach using a priori knowledge of vessel structure
[146] tracks vessels between user-defined bifurcations from two x-ray viewpoints

Artificial Intelligence-Based Approaches

Artificial intelligence-based approaches use expert system style knowledge of vessels during segmentation.

[148] Adapts low-level image processing algorithms to the needs of an application based on high-level natural language terms
[147] Knowledge-based system for extraction of blood vessels based on 11 rules
[68] 'ANGY', a rule-based expert system using low-level and high-level knowledge for segmentation of coronary vessels
[63] Uses a bayesian network trained on sample images for final classification step of retinal images
[149] knowledge-based approach using fuzzy set theory to represent the knowledge. Segments aorta and renal arteries
[150] Thresholding-based approach in which pixels are classified as artery, background, or unknown, and where the threshold is adaptively changed by a learning algorithm to classify 'unknown' pixels based on line and consistency measurements around pixels. Compared to techniques in [151, 152]

Neural Network-Based Approaches

Neural nets are comprised of a set of basic 'nodes', each node taking a number of inputs and generating an output. Each node is 'weighted', and through either supervised or unsupervised learning the weights are modified to generate desired outputs based on inputs. Information on neural networks can be found in [153, 154, 155, 156].

[157] A parallel version of [158, 159], the work reconstructs 3D vessels from biplane angiograms. A standard vessel tracking procedure is implemented, as well as an adaptive version.
[160] back-propagation network is used to label pixels as vessel or non-vessel. Image pixels are fed directly into the network as input. The algorithm is compared to two others, a Bayesian maximum likelihood algorithm and iterative ternary classification algorithm [150].
[89] Combination of neural-network based approach with knowledge-guided snakes to extract left-ventricular boundaries.
[161] Combination of neural-network segmentation with manual segmentation of computed tomography angiography image volumes. Initial segmentation sections can be edited by a user, followed by a connectivity step producing the final segmentation.
[157, 161] have information about 3D reconstruction of vessels.

Miscellaneous Tube-Like Object Detection Approaches

[162] Faster version of a Hough transform to locate round objects
[163] Extraction of tubular objects from range images by looking for conic profiles along scan lines.
[164] Ribbon-snake approach to extracting roads from 2D images
[92] Detection of stents in angiographic images. A training set is constructed from various projections and deformations of a 3D wireframe model of the stent. The training set is used to create a Gaussian density estimate using Principal Component Analysis. A maximum likelihood estimate is then constructed, and a 2D snake procedure is used for refinement.
[64] High-level constraints and user feedback used to segment pipelines in industrial applications
[16] generalized cylinders approach to detect tubular objects in 2D intensity images. Local and global recognition occurs in succeeding steps. Algorithm is applied to extraction of tree roots.
[90] Tracking of tubular objects implemented to track DNA molecules. Geometric properties are used to find and track objects, and for each object high and low level constraints are used to find object boundaries.