برنامه ریزی پویا در تشخیص مرز موازی با کاربرد برای تقسیم بندی اینتیمای رسانه اولتراسوند

Segmentation of carotid artery intima-media in longitudinal ultrasound images for measuring its thickness to predict cardiovascular diseases can be simplified as detecting two nearly parallel boundaries within a certain distance range, when plaque with irregular shapes is not considered. In this paper, we improve the implementation of two dynamic programming (DP) based approaches to parallel boundary detection, dual dynamic programming (DDP) and piecewise linear dual dynamic programming (PL-DDP). Then, a novel DP based approach, dual line detection (DLD), which translates the original 2-D curve position to a 4-D parameter space representing two line segments in a local image segment, is proposed to solve the problem while maintaining efficiency and rotation invariance. To apply the DLD to ultrasound intima-media segmentation, it is imbedded in a framework that employs an edge map obtained from multiplication of the responses of two edge detectors with different scales and a coupled snake model that simultaneously deforms the two contours for maintaining parallelism. The experimental results on synthetic images and carotid arteries of clinical ultrasound images indicate improved performance of the proposed DLD compared to DDP and PL-DDP, with respect to accuracy and efficiency.

Boundary detection in longitudinal ultrasound carotid artery images has focused on automatic and accurate intima-media segmentation in the far wall for measurement of the thickness, which has been demonstrated to be an independent risk factor for cardiovascular disease (Bots et al., 1997, Lamont et al., 2000, O’Leary et al., 1999 and Poredos, 2004). Fig. 1 illustrates three examples in which the intima-media complex (IMC) is a double-layered structure that features bright and dark bands enclosed by dark lumen above and bright adventitia below, whose boundary is defined by two parallel interfaces, the lumen-intima (LI) (upper boundary) and the media-adventitia (MA) (lower boundary). This is not an easy task because of the intrinsic variability of the intima-media structure and the extrinsic interference from the ultrasound machine. For anatomical variability, the thickness range demands consideration of all possible thicknesses while the boundary curve complicates an analytic representation. For common artifacts generated from the ultrasound machine, the interferences can be mainly categorized by strong noise in the lumen region and missing boundary in the intima layer (see Fig. 1). When plaque with significant local thickening exists, the situation could become more complex because its shape can differ greatly from the intima-media with a small thickness. Therefore, in this paper, we consider only intima-media with two nearly parallel boundaries as most of the previously proposed intima-media segmentation methods did ( Cheng and Jiang, 2008, Destrempes et al., 2009, Loizou et al., 2007 and Xu et al., 2012). Full-size image (50 K) Fig. 1. Illustration of the intima-media in ultrasound carotid artery images, in which the IMC is a double-layered structure enclosed by dark lumen above and bright adventitia below. The left column shows original ROI images while the right column shows manually delineated boundary contours. Figure options 1.1. Previous research There are a variety of segmentation algorithms proposed in this field, which were recently reviewed by Molinari et al. (Molinari et al., 2010). The employed techniques include dynamic programming (DP) (Cheng and Jiang, 2008, Liang et al., 2000 and Wendelhag et al., 1997), active contour model (Cheng et al., 2002, Loizou et al., 2007 and Xu et al., 2012), stochastic optimization. (Destrempes et al., 2009) and spline fitting (Rocha et al., 2010 and Rocha et al., 2011), among which the most natural algorithm regarding such tasks could be single dynamic programming (SDP) (Liang et al., 2000), as defined by minimizing the following cost function equation(1) View the MathML sourceCSDP(y1,y2,…,yN)=κ∑n=2N|yn-1-yn|-∑n=1Nf(n,yn) Turn MathJax on where y n, n = 1, 2, …, N is the y -coordinate of the boundary point in the n th column, f(x,y):Ω→R+f(x,y):Ω→R+ is an edge map that has large values near the boundary, Ω = {(x, y)∣1 ⩽ x ⩽ N, 1 ⩽ y ⩽ M} is the image plane of size N × M (let the origin of the coordinate system be the top left corner), and κ is a parameter that controls the smoothness of the detected boundary. The key of DP is to write (1) in a recursion form so that a cost map containing minimal intermediate costs can be constructed through forward recursion, and then, the optimal solution can be found through back tracing ( Amini et al., 1990). Because the cost map has the same size of the image plane, in which each intermediate cost is computed by considering all the costs in the previous column, the time complexity of forward recursion is O(NM2). The back tracing traces back from the minimal cost of the last column to the first column in O(N) to find the optimal path. SDP is a simple approach for detecting one side boundary; thus, it was applied to intima-media segmentation quite early (Liang et al., 2000 and Wendelhag et al., 1997). Because the boundary of intima-media can be defined by two nearly parallel interfaces without the presence of plaque, a more ideal approach for such a problem could consider two boundaries simultaneously in the cost function, which was later proposed as dual dynamic programming (DDP) (Cheng and Jiang, 2008). The DDP has been demonstrated to be superior to SDP by imposing a hard constraint relating to the distance range and a soft constraint relating to its variation, except that the large computational cost requires O(NM2) even through a fast implementation that considers only neighboring costs in the forward recursion ( Cheng and Jiang, 2008). There has been other research conducted for similar tasks, in which piecewise linear dual dynamic programming (PL-DDP) was proposed for spine boundary detection (Wei et al., 2001a and Wei et al., 2001b). The PL-DDP partitions the image plane into several equal-width non-overlapping segments, in each of which two line segments controlled by their endpoints are used to approximate the local boundaries. Because the curve smoothness of PL-DDP is controlled by the hard constraints of the angles between adjacent line segments, the method benefits from having a rotation-invariant nature. However, due to the dimension of the cost map, the solution employed in (Wei et al., 2001a and Wei et al., 2001b) has a very large computational cost, O(NM4). Although piecewise linear approximation is not accurate for intima-media segmentation, further refinement based on an active contour model can be applied thereafter. Further generalization includes extending the DP based detection of two parallel boundaries to multiple paths. For example, reference (Sun and Appleton, 2005) constrained the smoothness of the path through hard constraints that forced the path points in adjacent columns to be within a certain range. Similar to DDP, multiple hard constraints relating to the properties between paths, such as the order and distance as well as the heuristic constraints that use local maxima in the edge map, were proposed to reduce the computational cost. A specific application of this generalization to detecting two boundaries of membrane was proposed later, which adopted a polar transform of the original image for the following DP (Sun et al., 2009). The above DP methods have two characteristics that we need to mention here. First, except for PL-DDP, the curve smoothness is defined by the vertical distance between two adjacent boundary points (first order derivative), which is not rotation invariant. Thus, it is possible that a slanting boundary demands a small curve smoothness to maintain the slope of the two ends while a horizontal boundary demands a large curve smoothness to overcome noise. This leads to a complicated training procedure for choosing the optimal parameters (Cheng and Jiang, 2008 and Liang et al., 2000), which might not be successfully applied to all the situations. Second, because the DP searches the whole image plane to detect the boundaries, the computational cost achieves O(NM2) for DDP and O(NM4) for PL-DDP. We will show, in Section 2, that they could achieve O(NM) complexity via fast implementations. However, it is still not a trivial task when the image becomes large. 1.2. Our contribution In this paper, we propose a novel algorithm that avoids the above shortcomings for parallel boundary detection and validate the method in the context of ultrasound LI and MA boundary tracing. The boundary curve is divided into several parts, each of which is approximated using a line segment that can be defined by two parameters using a polar representation. The endpoints of the adjacent parts are linked via minimization of their vertical distance. Geometric constraints such as the distance and the angle between the two line segments are also incorporated naturally. Several remarks can be made about this representation. First, in each segment, because of the polar representation of the line, the hard constraints can be imposed in a rotation-invariant way. Second, when the length of a part is small enough to equal the width of a single column, the algorithm degrades to a DP which is similar to DDP. Third, when the length of the part is large enough to equal the width of the image plane, the algorithm degrades to line detection which is similar to finding peaks in the parameter space of the Hough transform. Hence, it benefits from the robustness of both the Hough transform and DP. Moreover, it overcomes the weakness of the Hough transform that requires a very high dimensional parameter space for complex curves and the inconsistent curve smoothness measure of the above DP. Finally, because the algorithm operates on the edge points instead of on the whole image plane, apart from the thresholding procedure to determine the edge points, the remaining part could achieve linear time complexity O(N). The remainder of this paper is organized as follows. Section 2 reviews the previous DDP and PL-DDP, for which we suggest that, under certain hard constraints, the complexity of the solution can be reduced to O(NM). Section 3 introduces the theoretical model of the proposed dual line detection (DLD) for parallel boundary detection and a fast solution that requires only O(N). Section 4 proposes a framework to imbed the DLD for ultrasound intima-media segmentation, which includes three steps, as illustrated in Fig. 2. Then, after a description of data acquisition and algorithm implementation in Section 5, Section 6 presents and discusses comparative results on these methods. The final Section gives conclusive remarks. Full-size image (75 K) Fig. 2. Overview of the proposed intima-media segmentation approach.

This paper attempts to solve a problem, parallel boundary detection, which emerges in medical imaging applications such as boundary detection on carotid arteries in ultrasound images or the detection of spines in X-ray images. We improved the implementation of two previous methods, DDP and PL-DDP, to render them able to solve the problem in O(NM) complexity. Then, a novel DP based approach, LDLD with rotation invariance and approximately linear time complexity O(N), was proposed to approximate the boundaries using piecewise linear representation. We also embedded the LDLD into a framework for segmentation of intima-media in ultrasound images and validated the method through comparing it with DDP and PL-DDP on a dataset of 200 ROIs. To conclude this paper, we present some final remarks: 1. The cost function of LDLD is very similar to that of DDP and PL-DDP. All of them attempt to find two curves that pass through strong edges as many as possible while satisfying certain hard constraints; however, the form of the solution is quite different so that the edge direction can be used to reduce the computational cost. Moreover, because of the auxiliary edge directions in our solution, the algorithm can selectively detect boundaries of objects with desired patterns. 2. The robustness and accuracy of LDLD rely on an initial piecewise linear approximation and a subsequent snake refinement. The two steps could be a requirement of difficult medical imaging applications according to our experiments. The DDP may directly detect the two side boundaries accurately through imposing further constraints, e.g., a second order derivative, but this could add more parameters for training, and the speed would be hampered. 3. The proposed method is intended only for segmenting nearly parallel boundaries, which may limit its use for plaque. However, because plaque tends to grow into irregular shapes that are difficult to model analytically, few papers have focused on this topic. Actually, according to Fig. 13, we included some pathological cases with IMT > 1 mm, which may be identified as plaque by some clinicians. Although the method in this paper shows an improved accuracy and efficiency to some extent, it also brings some hidden parameters for tuning. This is a drawback of our method, but we think it is acceptable in clinical applications and, in practice, the selection of parameters is somewhat robust according to Section 6.3. 4. Finally, the LDLD can be extended in several aspects, e.g., changing the linkage from the soft constraint to a hard constraint, detecting two circular parallel boundaries via a polar transform of the original image. Although we apply the proposed LDLD only to intima-media segmentation in this paper, extension to other types of boundaries with edge directions pointing to different sides is intrinsic.