4D or dynamic imaging of the thorax has many potential applications [1, 2]. CT and MRI offer sufficient speed to acquire motion information via 4D imaging. However they have different constraints and requirements. For both modalities both prospective and retrospective respiratory gating and tracking techniques have been developed [3, 4]. For pediatric imaging, x-ray radiation becomes a primary concern and MRI remains as the de facto choice. The pediatric subjects we deal with often suffer from extreme malformations of their chest wall, diaphragm, and/or spine, as such patient cooperation needed by some of the gating and tracking techniques are difficult to realize without causing patient discomfort. Moreover, we are interested in the mechanical function of their thorax in its natural form in tidal breathing. Therefore free-breathing MRI acquisition is the ideal modality of imaging for these patients. In our set up, for each coronal (or sagittal) slice position, slice images are acquired at a rate of about 200-300 ms/slice over several natural breathing cycles. This produces typically several thousands of slices which contain both the anatomic and dynamic information. However, it is not trivial to form a consistent and well defined 4D volume from these data. In this paper, we present a novel graph-based combinatorial optimization solution for constructing the best possible 4D scene from such data entirely in the digital domain. Our proposed method is purely image-based and does not need breath holding or any external surrogates or instruments to record respiratory motion or tidal volume. Both adult and children patients’ data are used to illustrate the performance of the proposed method. Experimental results show that the reconstructed 4D scenes are smooth and consistent spatially and temporally, agreeing with known shape and motion of the lungs.
To make Quantitative Radiology a reality in routine radiological practice, computerized automatic anatomy recognition (AAR) becomes essential. Previously, we presented a fuzzy object modeling strategy for AAR. This paper presents several advances in this project including streamlined definition of open-ended anatomic objects, extension to multiple imaging modalities, and demonstration of the same AAR approach on multiple body regions. The AAR approach consists of the following steps: (a) Collecting image data for each population group G and body region <i>B</i>. (b) Delineating in these images the objects in <i>B</i> to be modeled. (c) Building Fuzzy Object Models (FOMs) for <i>B</i>. (d) Recognizing individual objects in a given image of <i>B</i> by using the models. (e) Delineating the recognized objects. (f) Implementing the computationally intensive steps in a graphics processing unit (GPU). Image data are collected for <i>B</i> and <i>G</i> from our existing patient image database. Fuzzy models for the individual objects are built and assembled into a model of <i>B</i> as per a chosen hierarchy of the objects in <i>B</i>. A global recognition strategy is used to determine the pose of the objects within a given image <i>I</i> following the hierarchy. The recognized pose is utilized to delineate the objects, also hierarchically. Based on three body regions tested utilizing both computed tomography (CT) and magnetic resonance (MR) imagery, recognition accuracy for non-sparse objects has been found to be generally sufficient ( 3 to 11 mm or 2-3 voxels) to yield delineation false positive (FP) and true positive (TP) values of < 5% and ≥ 90%, respectively. The sparse objects require further work to improve their recognition accuracy.
We study the problem of automatic delineation of an anatomic object in an image, where the object is solely
identified by its anatomic prior. We form such priors in the form of fuzzy models to facilitate the segmentation of
images acquired via different imaging modalities (like CT, MRI, or PET), in which the recorded image properties
are usually different. Our main interest is in delineating different body organs in medical images for automatic
anatomy recognition (AAR).
The AAR system we are developing consists of three main components: (C1) building body-wide groupwise
fuzzy anatomic models; (C2) recognizing the body organs geographically and then delineating them by employing
the models; (C3) generating quantitative descriptions. This paper focuses on (C2) and presents a unified approach
for model-based segmentation within which several different strategies can be formulated, ranging from modelbased
hard/fuzzy thresholding to model-based graph cut, fuzzy connectedness, and random walker methods and
algorithms. This is an important theoretical advance.
The presented experiments clearly prove, that a fully automatic segmentation system based on the fuzzy
models can indeed provide the reliable segmentations. However, the presented experiments utilize only the
simplest versions of the methodology presented in the theoretical part of the paper. The full experimental
evaluation of the methodology is still a work in progress.
To make Quantitative Radiology a reality in routine radiological practice, computerized automatic anatomy recognition
(AAR) during radiological image reading becomes essential. As part of this larger goal, last year at this conference we
presented a fuzzy strategy for building body-wide group-wise anatomic models. In the present paper, we describe the
further advances made in fuzzy modeling and the algorithms and results achieved for AAR by using the fuzzy models.
The proposed AAR approach consists of three distinct steps: (a) Building fuzzy object models (FOMs) for each
population group G. (b) By using the FOMs to recognize the individual objects in any given patient image I under group
G. (c) To delineate the recognized objects in I. This paper will focus mostly on (b).
FOMs are built hierarchically, the smaller sub-objects forming the offspring of larger parent objects. The hierarchical
pose relationships from the parent to offspring are codified in the FOMs. Several approaches are being explored
currently, grouped under two strategies, both being hierarchical: (ra1) those using search strategies; (ra2) those
strategizing a one-shot approach by which the model pose is directly estimated without searching. Based on 32 patient
CT data sets each from the thorax and abdomen and 25 objects modeled, our analysis indicates that objects do not all
scale uniformly with patient size. Even the simplest among the (ra2) strategies of recognizing the root object and then
placing all other descendants as per the learned parent-to-offspring pose relationship bring the models on an average
within about 18 mm of the true locations.
This paper presents a parallel algorithm for the top of the line among the fuzzy connectedness algorithm family,
namely the iterative relative fuzzy connectedness (IRFC) segmentation method. The algorithm of IRFC, realized
via image foresting transform (IFT), is implemented by using NVIDIA's compute unified device architecture
(CUDA) platform for segmenting large medical image data sets. In the IRFC algorithm, there are two major
computational tasks: (i) computing the fuzzy affinity relations, and (ii) computing the fuzzy connectedness
relations and tracking labels for objects of interest. Both tasks are implemented as CUDA kernels, and a
substantial improvement in speed for both tasks is achieved. Our experiments based on three data sets of small,
medium, and large data size demonstrate the efficiency of the parallel algorithm, which achieves a speed-up
factor of 2.4x, 17.0x, and 42.7x, correspondingly, for the three data sets on the NVIDIA Tesla C1060 over the
implementation of the algorithm in CPU.
We present a general graph-cut segmentation framework GGC, in which the delineated objects returned by the
algorithms optimize the energy functions associated with the ℓ<sub>p</sub> norm, 1 ≤ p ≤ ∞. Two classes of well known
algorithms belong to GGC: the standard graph cut GC (such as the min-cut/max-flow algorithm) and the
relative fuzzy connectedness algorithms RFC (including iterative RFC, IRFC). The norm-based description of
GGC provides more elegant and mathematically better recognized framework of our earlier results from [18, 19].
Moreover, it allows precise theoretical comparison of GGC representable algorithms with the algorithms discussed
in a recent paper  (min-cut/max-flow graph cut, random walker, shortest path/geodesic, Voronoi diagram,
power watershed/shortest path forest), which optimize, via ℓ<sub>p</sub> norms, the intermediate segmentation step, the
labeling of scene voxels, but for which the final object need not optimize the used ℓ<sub>p</sub> energy function. Actually,
the comparison of the GGC representable algorithms with that encompassed in the framework described in 
constitutes the main contribution of this work.
The goal of this paper is a theoretical and experimental comparison of two popular image segmentation algorithms:
fuzzy connectedness (FC) and graph cut (GC). On the theoretical side, our emphasis will be on
describing a common framework in which both of these methods can be expressed. We will give a full analysis
of the framework and describe precisely a place which each of the two methods occupies in it. Within the same
framework, other region based segmentation methods, like watershed, can also be expressed. We will also discuss
in detail the relationship between FC segmentations obtained via image forest transform (IFT) algorithms, as
opposed to FC segmentations obtained by other standard versions of FC algorithms.
We also present an experimental comparison of the performance of FC and GC algorithms. This concentrates
on comparing the actual (as opposed to provable worst scenario) algorithms' running time, as well as influence
of the choice of the seeds on the output.
To make Quantitative Radiology (QR) a reality in routine clinical practice, computerized automatic anatomy recognition
(AAR) becomes essential. As part of this larger goal, we present in this paper a novel fuzzy strategy for building bodywide
group-wise anatomic models. They have the potential to handle uncertainties and variability in anatomy naturally
and to be integrated with the fuzzy connectedness framework for image segmentation. Our approach is to build a family
of models, called the Virtual Quantitative Human, representing normal adult subjects at a chosen resolution of the
population variables (gender, age). Models are represented hierarchically, the descendents representing organs contained
in parent organs. Based on an index of fuzziness of the models, 32 thorax data sets, and 10 organs defined in them, we
found that the hierarchical approach to modeling can effectively handle the non-linear relationships in position, scale,
and orientation that exist among organs in different patients.
Fuzzy connectedness (FC) constitutes an important class of image segmentation schemas. Although affinity
functions represent the core aspect (main variability parameter) of FC algorithms, they have not been studied
systematically in the literature. In this paper, we present a thorough study to fill this gap. Our analysis is
based on the notion of equivalent affinities: if any two equivalent affinities are used in the same FC schema
to produce two versions of the algorithm, then these algorithms are equivalent in the sense that they lead to
identical segmentations. We give a complete characterization of the affinity equivalence and show that many
natural definitions of affinity functions and their parameters used in the literature are redundant in the sense
that different definitions and values of such parameters lead to equivalent affinities. We also show that two main
affinity types - homogeneity based and object feature based - are equivalent, respectively, to the difference
quotient of the intensity function and Rosenfeld's degree of connectivity. In addition, we demonstrate that any
segmentation obtained via relative fuzzy connectedness (RFC) algorithm can be viewed as segmentation obtained
via absolute fuzzy connectedness (AFC) algorithm with an automatic and adaptive threshold detection. We
finish with an analysis of possible ways of combining different component affinities that result in non equivalent
In 2003, Maurer <i>at al</i>.  published a paper describing an algorithm that computes the exact distance transform
in a linear time (with respect to image size) for the rectangular binary images in the k-dimensional space Rk and
distance measured with respect to <i>L</i><sub>p</sub>-metric for 1 ≤ p ≤ ∞, which includes Euclidean distance <i>L</i><sub>2</sub>. In this paper
we discuss this algorithm from theoretical and practical points of view. On the practical side, we concentrate
on its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform,
and experimentally compare implemented algorithms. We also describe the parallelization of these algorithms
and the computation time savings associated with such an implementation. The discussed implementations will
be made available as a part of the CAVASS software system developed and maintained in our group . On the theoretical side, we prove that our version of the signed distance transform algorithm, GBDT, returns, in a linear time, the exact value of the distance from the geometrically defined object boundary. We notice that,
actually, the precise form of the algorithm from  is not well defined for <i>L</i><sub>1</sub> and <i>L</i>∞ metrics and point to our complete proof (not given in ) that all these algorithms work correctly for the Lp-metric with 1 < p < ∞.
In the current vast image segmentation literature, there is a serious lack of methods that would allow theoretical
comparison of the algorithms introduced by using different mathematical methodologies. The main goal of this
article is to introduce a general theoretical framework for image segmentation that would allow such comparison.
The framework is based on the formal definitions designed to answer the following fundamental questions: What
is the relation between an idealized image and its digital representation? What properties a segmentation
algorithm must satisfy to be acknowledged as acceptable? What does it mean that a digital image segmentation
algorithm truly approximates an idealized segmentation model? We use the formulated framework to analyze
the front propagation (FP) level set algorithm of Malladi, Sethian, and Vemuri and compare it with the fuzzy
connectedness family of algorithms. In particular, we prove that the FP algorithm is weakly model-equivalent
with the absolute fuzzy connectedness algorithm of Udupa and Samarasekera used with gradient based afinity.
Experimental evidence of this equivalence is also provided. The presented theoretical framework can be used to
analyze any arbitrary segmentation algorithm. This line of investigation is a subject of our forthcoming work.