Search

The precise three-dimensional (3-D) segmentation of cerebral vessels from magnetic resonance angiography (MRA) images is essential for the detection of cerebrovascular diseases (e.g., occlusion, aneurysm). The complex 3-D structure of cerebral vessels and the low contrast of thin vessels in MRA images make precise segmentation difficult. We present a fast, fully automatic segmentation algorithm based on statistical model analysis and improved curve evolution for extracting the 3-D cerebral vessels from a time-of-flight (TOF) MRA dataset. Cerebral vessels and other tissue (brain tissue, CSF, and bone) in TOF MRA dataset are modeled by Gaussian distribution and combination of Rayleigh with several Gaussian distributions separately. The region distribution combined with gradient information is used in edge-strength of curve evolution as one novel mode. This edge-strength function is able to determine the boundary of thin vessels with low contrast around brain tissue accurately and robustly. Moreover, a fast level set method is developed to implement the curve evolution to assure high efficiency of the cerebrovascular segmentation. Quantitative comparisons with 10 sets of manual segmentation results showed that the average volume sensitivity, the average branch sensitivity, and average mean absolute distance error are 93.6%, 95.98%, and 0.333 mm, respectively. By applying the algorithm to 200 clinical datasets from three hospitals, it is demonstrated that the proposed algorithm can provide good quality segmentation capable of extracting a vessel with a one-voxel diameter in less than 2 min. Its accuracy and speed make this novel algorithm more suitable for a clinical computer-aided diagnosis system.

This paper presents a new algorithmic framework for some basic problems on binary images. Algorithms for binary images such as one of extracting a connected component containing a query pixel and that of connected components labeling play basic roles in image processing. Those algorithms usually use linear work space for efficient implementation. In this paper we propose algorithms for several basic problems on binary images which are efficient in time and space, using space-efficient algorithms for grid graphs. More exactly, some of them run in O ( n log n ) time using O ( 1 ) work space and the others run in O ( n ) or O ( n log n ) time using O ( n ) work space for a binary image of n pixels stored in a read-only array. [ABSTRACT FROM AUTHOR]

We present a new approach, called topological peeling, for traversing a portion AR of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of A[SUBR] in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walk may not be directly applicable. Our topological peeling algorithm takes O(K + nlog(n + r)) time and O(n + r) space, where K is the number of cells in A[SUBR] and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walk by 10-25 1241328n execution time. [ABSTRACT FROM AUTHOR]

This paper presents how the space of spheres and shelling may be used to delete a point from a d-dimensional triangulation efficiently. In dimension two, if k is the degree of the deleted vertex, the complexity is O(k log k), but we notice that this number only applies to low cost operations, while time consuming computations are only done a linear number of times. This algorithm may be viewed as a variation of Heller's algorithm,[sup 1,2] which is popular in the geographic information system community. Unfortunately, Heller algorithm is false, as explained in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we propose new rules of advancing edges for computing the intersection of a pair of convex polygons in the plane. These rules have no ambiguities when extended into the spherical surface, differently from those of O'Rourke et al..[sup 4] Finally, we design a linear-time algorithm for computing the intersection of a pair of spherical convex polygons, and prove its correctness. [ABSTRACT FROM AUTHOR]

The 1-searcher is a mobile guard whose visibility is limited to a ray emanating from his position, where the direction of the ray can be changed continuously with bounded angular rotation speed. Given a polygonal region P with a specified boundary point d, is it possible for a I-searcher to eventually see a mobile intruder that is arbitrarily faster than the searcher within P, before the intruder reaches d? We decide this question in O(n log n)-time for an n-sided polygon. Our main result is a simple characterization of the class of polygons (with a boundary point d) that admits such a search strategy. We also present a simple O(n²)-time algorithm for constructing a search schedule, if one exists. Finally, we compare the search capability of a 1-searcher with that of two guards. [ABSTRACT FROM AUTHOR]

We consider some intersection problems on segments of R[sup 2] in the partially dynamic setting called boundary update, where updates occur at the boundary of a given region. In particular, we maintain a set S of line segments under (boundary) insertions and deletions, such that, given a line segment ℓ either of fixed slope or originating from a fixed point and given a point p∈S∩ℓ, we can efficiently and orderly report all segments intersecting ℓ; insertions/deletions of segments occur at the boundaries of a vertical infinite slab. We provide practical algorithms requiring O(|S|) space, O(log |S|) time per update and O(||) time per query, where k is the number of reported segments. Our results allow both modeling a moving window over a larger data set and answering segment intersection queries at an extra query cost of O(log |S|); also, they provide a methodology for designing access methods to temporal databases as well as a new kind of partially persistent lists. [ABSTRACT FROM AUTHOR]