Finding a feasible point that satisfies a set of constraints is a common task in scientific computing: examples are the linear feasibility problem and the convex feasibility problem. Finitely convergent sequential algorithms can be used for solving such problems; an example of such an algorithm is ART3, which is defined in such a way that its control is cyclic in the sense that during its execution it repeatedly cycles through the given constraints. Previously we found a variant of ART3 whose control is no longer cyclic, but which is still finitely convergent and in practice it usually converges faster than ART3 does. In this paper we propose a general methodology for automatic transformation of finitely convergent sequential algorithms in such a way that (i) finite convergence is retained and (ii) the speed of convergence is improved. The first of these two properties is proven by mathematical theorems, the second is illustrated by applying the algorithms to a practical problem.

As electron microscopy advances toward imaging larger specimens at higher resolutions, the effect of variable defocus in image formation becomes more pronounced. This variation in defocus along the direction of electron propagation results in each layer within the specimen (perpendicular to the direction of the electron beam) being blurred by a slightly different contrast transfer function (CTF). Using distance-dependent properties of the 3D Fourier coefficients of the projection data (in the case of 2D projections collected about a single axis of rotation perpendicular to the direction of electron travel), each coefficient can be corrected using a CTF which incorporates the appropriate defocus. This paper presents a simulation of image formation with variable blur, together with a Fourier-based correction of the blur in a distance-dependent fashion.

A new algorithm for three-dimensional reconstruction of two-dimensional crystals from projections is presented, and its applicability to biological macromolecules imaged using transmission electron microscopy (TEM) is investigated. Its main departures from the traditional approach is that it works in real space, rather than in Fourier space, and it is iterative. This has the advantage of making it convenient to introduce additional constraints (such as the support of the function to be reconstructed, which may be known from alternative measurements) and has the potential of more accurately modeling the TEM image formation process. Phantom experiments indicate the superiority of the new approach even without the introduction of constraints in addition to the projection data.

Discrete tomography (DT) deals with the reconstruction of a function from its projections, when the function has a known discrete range. The knowledge of the discrete range, possibly together with some prior information, can significantly reduce the number of projections required for a high-quality reconstruction. The reconstruction methods used in DT applications are usually based on some formulation as an optimization problem. This paper presents methods and results of DT based on problems of angiography, emission tomography, and electron microscopy (EM).

In this paper, we identify and describe the key ideas, concepts and software related to Medical Imaging that emerged from our research group, which is commonly known by the acronym MIPG, denoting Medical Image Processing Group. For the purpose of our presentation, we consider the entire discipline of Medical Imaging to consist of the areas of acquisition, postprocessing, evaluation, and application. We are indeed fortunate to be able to discuss seminal research from our group in each of these areas. In Section II, we identify relevant moments of inception and describe our past contributions. Our achievements, current activities, and future directions are summarized in Section III, Section IV, and Section V, respectively; the keys to our success are listed in Section V.

Fuzzy connectedness has been effectively used to segment out an object in a badly corrupted image. We generalize the approach by providing a definition which is shown to always determine a simultaneous segmentation of multiple objects. For any set of seed points, the segmentation is uniquely determined by the definition. An algorithm for finding this segmentation is presented and its output is illustrated. The algorithm is fast as compared to other segmentation algorithms in current use. We also report on an evaluation of the accuracy and robustness of the algorithm based on experiments in which several users were repeatedly asked to identify the seed points for the algorithm in a number of images.

True three-dimensional (3-D) volume reconstruction from fully 3-D data in positron emission tomography (PET) has only a limited clinical use because of its large computational burden. Fourier rebinning (FORE) of the fully 3-D data into a set of 2-D sinogram data decomposes the 3-D reconstruction process into multiple 2-D reconstructions of decoupled 2-D image slices, thus substantially decreasing the computational burden even in the case when the 2-D reconstructions are performed by an iterative reconstruction algorithm. On the other hand, the approximations involved in the rebinning combined with the decoupling of the image slices cause a certain reduction of image quality, especially when the signal-to-noise ratio of the data is low. We propose a 2.5-D Simultaneous Multislice Reconstruction approach, based on the series expansion principle, where the volume is represented by the superposition of 3-D spherically symmetric bell-shaped basis functions. It takes advantage of the time reduction due to the use of the FORE (2-D) data, instead of the original fully 3-D data, but at the same time uses a 3-D iterative reconstruction approach with 3-D basis functions. The same general approach can be applied to any reconstruction algorithm belonging to the class of series expansion methods (iterative or noniterative) using 3-D basis functions that span multiple slices, and can be used for any multislice sinogram or list mode data whether obtained by a special rebinning scheme or acquired directly by a PET scanner in the 2-D mode using septa. Our studies confirm that the proposed 2.5-D approach provides a considerable improvement in reconstruction quality, as compared to the standard 2-D reconstruction approach, while the reconstruction time is of the same order as that of the 2-D approach and is clinically practical even on a general-purpose computer.

We present the applications of the geometry of digital spaces to three processes frequently used in medical imaging; namely segmentation, boundary tracking and display.

Finitary 1-simply connected digital spaces are discrete analogs of the important simply connected spaces in classical topology (i.e., connected spaces in which every loop can be continuously pulled to a point without leaving the space). Loosely speaking, 1-simply connected digital spaces are graphs in which there are no holes larger than a triangle. Many spaces previously studied in digital topology and geometry are instances of this concept. Boundaries in pictures defined over finitary 1-simply connected digital spaces have some desirable general properties; for example, they partition the space into a connected interior and a connected exterior. There is a “one-size-fits-all” algorithm which, given a picture over a finitary 1-simply connected digital space and a boundary face, will return the set of all faces in that boundary, provided only that this set is finite; the proof of correctness of this algorithm is an immediate consequence of the general properties of such spaces.

An algorithm is presented for tracking boundaries in three-dimensional binary images based on rhombic dodecahedral voxels. The algorithm produces a list of all the rhombic voxel faces in such a boundary.

Early development of digital topology concentrated on tessellations of the plane into square-shaped pixels, each one of which had a 1 or a 0 assigned to it. It became quickly apparent that in order to avoid some “paradoxes” one needs to consider adjacencies in addition to that provided by the edge-adjacency. The customary choice became the use of a pair of adjacencies; one for the 1-pixels and another for the 0-pixels. While this approach can be treated in a mathematically rigorous fashion, it nevertheless remains attractive to consider those digital spaces in which a single adjacency sufficies to usefully define connectivity. This not only makes the resulting mathematics more elegant, but it also brings the subject nearer to classical graph theory and its enormous wealth of results. This is what motivated us to search for an appropriate new concept. Jordan curves have an interior and an exterior which between them contain all the points not on the curve and both of which are connected, but are disconnected from each other. Generalization to surfaces in digital spaces is useful when displaying (only the exterior of a surface is visible from any direction) or analyzing (the interior volume is well defined). Boundaries in digital spaces may or may not be Jordan, but are “guaranteed” to be Jordan in spaces we call strong Jordan graphs. In this paper we define such a notion of a strong Jordan graph. We show that some previously studied classes (such as those of 1-simply connected digital spaces and of bridged graphs) are subclasses of strong Jordan graphs. We also define Jordan graphs, as those digital spaces in which finite boundaries are guaranteed to be Jordan and show that there are Jordan graphs which are not strong Jordan graphs. (Strong) Jordan graphs are characterized by the existence of “cuts” in associated graphs, by the acyclic nature of the adjacency graphs of binary pictures, and also by the connectedness of the immediate interiors (or exteriors) of certain types of surfaces. The surfaces of the last category include the so-called minimally near-Jordan surfaces, which are shown to be of some interest. Finally, we tie some of these notions to standard notions of graph theory, such as the notion of a separating set. Our overall conclusion is that those digital spaces which are Jordan graphs have some very desirable properties which make their use advantageous whenever the underlying situation allows us to use them.

When comparing reconstruction algorithms, differences in figures of performance merit that are too small to be of any practical relevance may still be statistically significant. We formalize the notion of "relevance" and propose an evaluation methodology in which statistical significance is retained for relevant improvements, but not for irrelevant ones.

The purpose of this work is to evaluate the estimation of projection data in fully 3D PET reconstruction. The estimation is carried out to reduce the effect of the noise prior to the application of a reconstruction algorithm and it is based on a non-linear operator that takes into account the Poisson nature of the noise. The evaluation is statistical, based on a set of 3D phantoms and on numerical observers for some typical medical tasks such as total uptake in regions of interest and detectability of hot and cold spots. Our work demonstrates that, for the studied tasks, the projection data estimation is an efficacious approach to fully 3D PET reconstruction.

Gibbs distributions, which have been very successfully used in statistical mechanics, have also been applied in image processing as assumed prior distributions in Bayesian (MAP) image restoration or reconstruction. When used in this context, the appropriateness of the Gibbs distribution has been judged by the success of the resulting image processing method; little attention has been paid to whether the Gibbs distribution indeed models the images that occur in the particular application area, in the sense that a randomly selected image from the distribution is likely to share the essential properties of those images. Indeed, many of the proposed Gibbs distributions do nothing but enforce smoothness; random samples from such distributions are likely to be uniformly smooth and thus probably atypical for any application area. In this paper we investigate the possibility of finding Gibbs distributions which truly model certain properties of images and look at the potential usefulness of using such image-modeling distributions as priors in Bayesian image processing. Specifically, we construct a Gibbs distribution which models an image that consists of piecewise homogeneous regions. The proposed model incorporates not only the information about the smoothness within regions in the image, but also the continuity of boundary structures which exist between regions. It is demonstrated that by sampling the Gibbs distribution which arises from the model we obtain images with piecewise homogeneous regions resembling the global features of the image that we intend to model; hence such a Gibbs distribution is indeed "image-modeling." Objective assessment of the model is accomplished by performing a goodness-of-fit test based on a χ2 statistic computed by considering the corresponding local conditional distributions. Issues related to the selection of model parameters from the given data image are addressed. Importantly, the most essential parameter of the image model (related to the regularization parameter associated with the penalty function in many image restoration and reconstruction methods) is estimated in the process of constructing the image model. Comparative results are presented of the outcome of using our model and an alternative model as the prior in some image restoration problems in which noisy synthetic images were considered.

Algebraic reconstruction techniques (ART) are iterative procedures for recovering objects from their projections. It is claimed that by a careful adjustment of the order in which the collected data are accessed during the reconstruction procedure and of the so-called relaxation parameters that are to be chosen in an algebraic reconstruction technique, ART can produce high-quality reconstructions with excellent computational efficiency. This is demonstrated by an example based on a particular (but realistic) medical imaging task, showing that ART can match the performance of the standard expectation-maximization approach for maximizing likelihood (from the point of view of that particular medical task), but at an order of magnitude less computational cost.

We introduce a mathematical framework suitable for a general theory of surfaces, objects, and their borders and boundaries in multidimensional discrete spaces. Our motivation comes from practical applications, where objects and their boundaries need to be identified in multidimensional data sets with the further aim of displaying them on a computer screen. Our definitions are biased toward such applications. In particular, we desire to characterize surfaces with a well-determined inside and outside and to define object borders and boundaries so that they will indeed be surfaces of this type. Furthermore, we make our presentation general enough to incorporate many of the reasonable but ad hoc ways that notions of “object,” “border,” and “boundary” may be defined in digital geometry. Some basic theorems are proven, showing that the framework is appropriate for the mathematical treatment of the intuitive notion of a “surface with a connected inside and a connected outside” (a Jordan surface) in the discrete multidimensional environment.

In previous publications we proposed, in the area of Positron Emission Tomography (PET), the use of a Maximum A posteriori Probability (MAP) optimization criterion with a particular normal prior which enforces smoothness on the resulting reconstructions. Two iterative algorithms were previously proposed to optimize this functional: one was known to converge to the desired reconstruction but was slow, while for the other it was found experimentally that, although it always appeared to converge an order of magnitude faster than the first one on examples realistic for PET, it could be made to diverge on artificial examples. In this paper we present an algorithm which is as fast as the second of these previously proposed algorithms, but it shares with the first the desirable property that it is guaranteed to converge to the reconstruction which is optimal according to our MAP criterion. We demonstrate the behavior of the algorithm on a variety of examples.

The authors make use of a real data set containing 9-D measurements of fine needle aspirates of a patient's breast for the purpose of classifying a tumor's malignancy for which early stopping in the generation of the separating hyperplanes is not appropriate. They compare a piecewise-linear classification method with classification based on a single linear separator. A precise methodology for comparing the relative efficacy of two classification methods for a particular task is described and is applied to the comparison on the breast cancer data of the relative performances of the two versions of the piecewise-linear classifier and the classification based on an optimal linear separator. It is found that for this data set, the piecewise-linear classifier that uses all the hyperplanes needed to separate the training set outperforms the other two methods and that these differences in performance are significant at the 0.001 level. There is no statistically significant difference between the performance of the other two methods. The authors discuss the relevance of these results for this and other applications.>

A complete system has been developed to utilize histological serial sections for two- and three-dimensional image reconstructions. Eighty to 120 sections are digitized using a personal computing system augmented with a imaging board and CCD camera. The image files are transmitted to a VAX computer for processing and image reconstruction, and the processed images are transmitted back to the personal computer for display and recording using a film recorder or PostScript printer. The software developed for the system allows serial sections to be placed into proper registration in a 256(3) array, 256 grey levels. Autoradiographs of the sections are obtained in the presence of appropriate standards which are used to recalibrate grey levels to represent linearly the radioactivity of each pixel in the sections and scale the values to allow maximum use of the grey scale. Starting from coronally sectioned material the system has been used to analyse and reconstruct rat nasal turbinates. In two dimensions horizontal and sagittal sections have been obtained while in three dimensions back-to-front and surface-rendered images have been constructed. Useful rendering of differential metabolic activity within an organ of complex geometry has been obtained, and there appears to be no reason why the system cannot be used for any material for which serial sectioning is appropriate.

We discuss the recently published claim of V. A. Kovalevsky that the topology of cellular complexes is the only appropriate topology for image analysis. In some sense we confirm this claim and even generalize it from the finite domain to an infinite one. We prove some results which can be interpreted to show that the class of partially ordered sets is strictly equivalent to a class of topological spaces which is certainly powerful enough to handle all of image analysis. However, such equivalence does not carry over when the partially ordered sets are complemented with a dimension function so as to form cellular complexes. In fact, it remains unclear whether the subclass of cellular complexes which use the assignment of dimension which is standard in image analysis is indeed powerful enough to encompass all problems of image analysis.

Computer graphic tools are presented which will enable a clinical physician to visualize, manipulate, and quantitate the three-dimensional internal structures of patients. Objects and their surfaces in digitized three-dimensional space are defined and the state of the art in three-dimensional boundary tracking is described. Generalizations, conjectures, and open problems are discussed.>

The development of image processing algorithms for time-varying imagery and computerized tomography data calls for generalization of the concepts of adjacency, connectivity, boundary, etc., to three and four-dimensional discrete spaces. This paper defines these basic concepts in unified terminology and presents algorithms for a boundary detection task in multidimensional space. The performance of these algorithms is discussed with respect to theoretical maximum complexity, and is illustrated with simulated computerized tomography data.

In many three-dimensional imaging applications the three-dimensional scene is represented by a three-dimensional array of volume elements, or voxels for short. A subset Q of the voxels is specified by some property. The objects in the scene are then defined as subsets of Q formed by voxels which are “connected” in some appropriate sense. It is often of interest to detect and display the surface of an object in the scene, specified say by one of the voxels in it.

Conventional radiographic imaging techniques are not adequate for determination of the true, dynamic changes in shape and dimensions of the intact working heart, lungs and circulation which are required for accurate quantitative determination of the structure and function of these organ systems. This paper describes a computerized method for obtaining images of the dynamic spatial distribution of x-ray attenuation throughout multiple parallel cross-sectional planes bisecting the intact thorax, with 1-mm spatial resolution and 60-per-second temporal resolution, and for generating time delay video and cine displays of the spatial and temporal sequences of these cross-sectional images. Operator-interactive computer programs facilitate the dynamic display of reconstructed cross sections of the heart and lungs, with or without dynamic background subtraction, and permit calculation and display of any desired single or spatially related set of coronal, sagittal or obliquely oriented sections. Such displays permit viewing of the temporal and spatial distribution of contraction, expansion, and perfusion of these organs over their full anatomic extent in various orientations and in variable time-base modes ranging from stop-action to real-time. The results achieved with this computerized system for three-dimensional reconstruction and display of moving organs, particularly the heart, lungs, and circulation, demonstrate the potential for providing greatly improved techniques for investigation of the relationships of the dynamic three-dimensional anatomy and blood-tissue exchange properties of moving organ systems to their regional and integrated function, and ultimately for providing powerful new clinical diagnostic methods for elucidation of abnormalities of the heart, lungs and circulation in man.

In most attempts to make precise the concept of a computable function, or decidable predicate, over a field F, it is considered necessary that the elements of F should be in some sense effectively describable, and hence that F itself should be countable. This is the attitude taken in the study of computable fields (see Rabin1).

The uniform halting problem (UH) can be stated as follows: Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID). An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [4, p. 118]) we assume that in an ID the tape must be blank except for some finite number of squares. If we remove this restriction the UH becomes the immortality problem (IP).

The uniform halting problem (UH) can be stated as follows. Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID). An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky [3, p. 118]) we assume that in an ID the tape must be blank except for some finite numbers of squares. If we remove this restriction the UH becomes the immortality problem (IP). The UH should not be confused with the initialised uniform halting problem (whether or not a TM has an immortal ID when started in a specified state) which can easily be shown to be undecidable (see e.g. Minsky [3, p. 151]).