Dynamic measurement precision assessment has been achieved for a differential circle measurement application. Differential circle diameter measurement, in image analysis, typically requires fitting a circle model that optimizes for image distortions, defects or occlusions. The differential task occurs when precise measurements of diameter change are required given object size variation with time. An automated system was designed to provide diameter measurements and associated measurement precision of images of a fuel droplet undergoing combustion in zero gravity for the FLEX-2 dataset. An image gradient-based, least-squares boundary point fitting method to a circle or ellipse model is used for diameter measurement. The presence of soot aggregates poses significant challenges for diameter measurements when it occludes part of the droplet boundary. The precision of the diameter measurements depends upon the image quality. Using synthetic image simulations that model the soot behavior, we developed a model based on image quality measures that assesses the measurement precision for each individual diameter measurement. Thus, diameter measurements with precision assessments were made available for follow-up scientific analysis. The algorithm's success rate for measurable runs was 98%. In cases of limited occlusion, a measurement precision of ±0.2 pixels for the FLEX-2 dataset was achieved.

This paper describes a framework for establishing a reference airway tree segmentation, which was used to quantitatively evaluate fifteen different airway tree extraction algorithms in a standardized manner. Because of the sheer difficulty involved in manually constructing a complete reference standard from scratch, we propose to construct the reference using results from all algorithms that are to be evaluated. We start by subdividing each segmented airway tree into its individual branch segments. Each branch segment is then visually scored by trained observers to determine whether or not it is a correctly segmented part of the airway tree. Finally, the reference airway trees are constructed by taking the union of all correctly extracted branch segments. Fifteen airway tree extraction algorithms from different research groups are evaluated on a diverse set of twenty chest computed tomography (CT) scans of subjects ranging from healthy volunteers to patients with severe pathologies, scanned at different sites, with different CT scanner brands, models, and scanning protocols. Three performance measures covering different aspects of segmentation quality were computed for all participating algorithms. Results from the evaluation showed that no single algorithm could extract more than an average of 74% of the total length of all branches in the reference standard, indicating substantial differences between the algorithms. A fusion scheme that obtained superior results is presented, demonstrating that there is complementary information provided by the different algorithms and there is still room for further improvements in airway segmentation algorithms.

The pulmonary nodule is the most common manifestation of lung cancer, the most deadly of all cancers. Most small pulmonary nodules are benign, however, and currently the growth rate of the nodule provides for one of the most accurate noninvasive methods of determining malignancy. In this paper, we present methods for measuring the change in nodule size from two computed tomography image scans recorded at different times; from this size change the growth rate may be established. The impact of partial voxels for small nodules is evaluated and isotropic resampling is shown to improve measurement accuracy. Methods for nodule location and sizing, pleural segmentation, adaptive thresholding, image registration, and knowledge-based shape matching are presented. The latter three techniques provide for a significant improvement in volume change measurement accuracy by considering both image scans simultaneously. Improvements in segmentation are evaluated by measuring volume changes in benign or slow growing nodules. In the analysis of 50 nodules, the variance in percent volume change was reduced from 11.54% to 9.35% (p = 0.03) through the use of registration, adaptive thresholding, and knowledge-based shape matching.

Small pulmonary nodules are a common radiographic finding that presents an important diagnostic challenge in contemporary medicine. While pulmonary nodules are the major radiographic indicator of lung cancer, they may also be signs of a variety of benign conditions. Measurement of nodule growth rate over time has been shown to be the most promising tool in distinguishing malignant from nonmalignant pulmonary nodules. In this paper, we describe three-dimensional (3-D) methods for the segmentation, analysis, and characterization of small pulmonary nodules imaged using computed tomography (CT). Methods for the isotropic resampling of anisotropic CT data are discussed. 3-D intensity and morphology-based segmentation algorithms are discussed for several classes of nodules. New models and methods for volumetric growth characterization based on longitudinal CT studies are developed. The results of segmentation and growth characterization methods based on in vivo studies are described. The methods presented are promising in their ability to distinguish malignant from nonmalignant pulmonary nodules and represent the first such system in clinical use.

Dynamic fault reconfiguration in an MIMD environment with a multistage interconnection network is considered. The near neighbor class of problems, which involve fundamental parallel processing algorithms such as partial differential equations and low level image processing algorithms, are chosen as the target application in such an environment. It is shown that dynamic fault reconfiguration can be achieved efficiently without any additional or modified hardware in case of (permanently) faulty processors. Two types of multistage networks are considered: general multistage networks (such as Benes networks) and the Omega network. The communication time of the system with faulty processors is minimized by rearranging the order in which the fault-free processors communicate with each other. For any number of faults, a reconfigured system with a general multistage network is shown to require an increase from four to five data transfers for each iteration of the near neighbor problem. For the Omega network, many faults can be handled by six data transfers, but in some cases up to 10 data transfers are necessary. In order to minimize the computation time of the system with faults, the data points of faulty processors are distributed equally and in parallel among the remaining processors. The technique used for parallel data distribution is called Uniform Data Distribution.

Asynchromus problems are those which may be decomposed into a set of independenr sub-tasks which are suitable for concurrent execution. Th function paraIIeIism of these problems cannot normally be direcrly expressed using the data-parallel programming model. In this paper, data distribution strategies have been explored which allow an asynchronous problem to be implemented which function-parallelism in a data-parallel environment. When a problem can be implemented using both function-parallelism and data-parallelism, there are tradeoffs in using either approach. We have investigated the optimal balance between function-parallelism and data-parallelism for an asynchronous problem.

Dynamic load balancing strategies for minimizing the execution time of single applications running in parallel on multicomputer systems are discussed. Dynamic load balancing (DLB) is essential for the efficient use of highly parallel systems when solving non-uniform problems with unpredictable load estimates. With the evolution of more highly parallel systems, centralized DLB approaches which make use of a high degree of knowledge become less feasible due to the load balancing communication overhead. Five DLB strategies are presented which illustrate the tradeoff between 1) knowledge - the accuracy of each balancing decision, and 2) overhead - the amount of added processing and communication incurred by the balancing process. All five strategies have been implemented on an Inter iPSC/2 hypercube.>

The effective utilization of a cluster of workstations for the implementation of a scientific application requires a highly flexible software environment. The characteristics of such an environment are considered and two novel data distribution aspects of this environment are explored. The performance of a distributed memory multicomputer, such as a workstation cluster, is very sensitive to the strategy used to distribute data to the processors. A performance prediction scheme is presented which could be incorporated into a compiler to determine the best data distribution for a given program and system. For heterogeneous systems a data distribution strategy has been developed which takes into account the different capabilities of the processors. A number of experiments have been conducted on workstation clusters to demonstrate these software techniques.>

Regular meshes are frequently used for modeling physical phenomena on both serial and parallel computers. One advantage of regular meshes is that efficient discretization schemes can be implemented in a straightforward manner. However, geometrically-complex objects, such as aircraft, cannot be easily described using a single regular mesh. Multiple interacting regular meshes are frequently used to describe complex geometries. Each mesh models a subregion of the physical domain. The meshes, or subdomains, can be processed in parallel, with periodic updates carried out to move information between the coupled meshes. In many cases, there are a relatively small number (one to a few dozen) subdomains, so that each subdomain may also be partitioned among several processors.

The recognition of objects from imagery in a manner that is independent of scale, position and orientation may be achieved by characterizing an object with a set of extracted invariant features. Several different recognition techniques have been demonstrated that utilize moments to generate such invariant features. These techniques are derived from general moment theory which is widely used throughout statistics and mechanics. In this paper, basic Cartesian moment theory is reviewed and its application to object recognition and image analysis is presented. The geometric properties of low-order moments are discussed along with the definition of several moment-space linear geometric transforms. Finally, significant research in moment-based object recognition is reviewed.

Abstract The Paragon project is directed toward the identification and exploration of programming methodologies to be used for the development of large-scale scientific applications on modern parallel computers. The Paragon environment consists of a set of data-parallel programming constructs and a flexible run-time environment. Among the salient features of Paragon are a data-parallel programming paradigm that is applicable to a wide variety of high-performance architectures, a practical abstraction of data distribution through the shape construct, and support for a powerful style of programming using communication structures. In this paper, programming with communication structures is considered and the performance of Paragon is characterized both for primitive operations and for several applications.

Nonuniform problems are characterized by a behavior that is data dependent and cannot be determined at compile time. Currently, no formal methods for implementation or evaluation exist for this class of algorithms. This paper presents an implementation of the region growing problem, which is representative of one class of nonuniform problems, on a highly parallel SIMD computer. The region growing paradigm for image segmentation groups neighboring pixels into regions depending upon a predetermined homogeneity criteria. Our algorithm is based upon a parallel merging paradigm, which involves the selection of the best of all merge possibilities for all regions concurrently. A key requirement of any parallel region growing scheme is the ability to concurrently compute functions on irregular shaped regions. A set of general primitive functions for region growing is defined and techniques for implementing these functions on an SIMD processor are developed. These techniques make use of an embedded tree data structure to represent regions. The results of implementing a parallel split-and-merge region growing algorithm on the Massively Parallel Processor are discussed. A comparison is made to an MIMD implementation of the algorithm on the Intel iPSC/2 hypercube. The SIMD approach is shown to be efficient primarily for images involving large numbers of regions.

Recent results in precision measurements using computer vision are presented. An edge operator based on two-dimensional spatial moments is given. The operator can be implemented for virtually any size of window and has been shown to locate edges in digitized images to a twentieth of a pixel. This accuracy is unaffected by additive or multiplicative changes to the data values. The precision is achieved by correcting for many of the deterministic errors caused by nonideal edge profiles using a lookup table to correct the original estimates of edge orientation and location. This table is generated using a synthesized edge which is located at various subpixel locations and various orientations. The operator is extended to accommodate nonideal edge profiles and rectangularly sampled pixels. The technique is applied to the measurement of imaged machined metal parts. Theoretical and experimental noise analyses show that the operator has relatively small bias in the presence of noise.>

A method for identifying unoccluded three-dimensional objects from arbitrary viewing angles is presented. The technique uses synthetically generated range data in a model-based feature vector classification scheme. Fourier descriptors and moments are used for feature vector generation from, respectively, contour imagery, and silhouette or range imagery. A method is developed for generating an exhaustive set of library views and worst-case test views that is based on a polyhedral approximation to a sphere. Analysis of the success of this approach is made with experiments on a six-airplane data set. A model of range data noise is developed, and results are presented for both ideal and noisy lower-resolution image-classification tests. The use of multiple views for object identification is discussed, and results for one-, two-, and three-view tests are presented.>

An object recognition system based on global features and nearest neighbor matching is extended and enhanced using classification quality assessment methodology. For quality assessment, a classification decision is processed at two levels. The first is to reject options that are not contained in the model database. The second is to identify the likelihood of error for classifications of known objects. Both stages are based on empirically determined thresholds of measures that are generated solely from the system's a priori knowledge, exploiting the known characteristics of both physical object space and feature space. Results are presented for a standardized object identification task, with a set of six similar known objects, and four unknown objects. It is shown that objects outside the model database are effectively rejected and that the accuracy of known object identifications is increased by rejecting views of low classification quality.>

A procedure for using moment-based feature vectors to identify a three-dimensional object from a two-dimensional image recorded at an arbitrary viewing angle and range is presented. A moment form called standard moments, rather than the usual moment invariants, is considered. A standard six-airplane experiment was used to compare different techniques. Fourier descriptors and moment invariants were both compared to the present scheme for normalized moments. Various experiments were conducted using mixtures of silhouette and boundary moments and different normalization techniques. Standard moments gave slightly better results than Fourier descriptors for this experiment; both of these techniques were much better than moment invariants.>

The near-neighbor problem is characterized by many iterations of a parallel matrix operation in which each matrix element is recomputed as a function of itself and its immediately adjacent near neighbors. Several highly parallel computer systems have been designed with the near-neighbor class of problems as the target application. As the number of processors in evolving parallel computer systems increases, the capability of fault tolerance to processor failures becomes more important. The authors show how fault tolerance can be efficiently achieved on an MIMD (multiple-instruction, multiple-data-stream) computer system for the near-neighbor problem by task redistribution. The techniques discussed minimize the extra data transfers and/or the extra computation in the system with faulty processors and links.>

Digital processing can be used to restore an image which has been blurred and/or corrupted by noise. This is a very slow process when implemented on a general purpose computer, especially for non-homogeneous problems, where FFT methods cannot be used. This paper describes an algorithm and a processor architecture for restoring an image in parallel, one pixel row at a time. The algorithm can accommodate point-spread functions and object models which are non-causal, non-separable, and non-homogeneous. Some simulation results are presented, although more are contained in [6]. The architecture bears some resemblance to existing "systolic array" designs, but the data input/output is parallel an entire pixel row at a time.

The application of a simulated binary array processor (BAP) to the rapid analysis of a sequence of images has been studied. Several algorithms have been developed which may be implemented on many existing parallel processing machines. The characteristic operations of a BAP are discussed and analyzed. A set of preprocessing algorithms are described which are designed to register two images of TV-type video data in real time. These algorithms illustrate the potential uses of a BAP and their cost is analyzed in detail. The results of applying these algorithms to FLIR data and to noisy optical data are given. An analysis of these algorithms illustrates the importance of an efficient global feature extraction hardware for image understanding applications.

A class of binary array processors (BAP) have evolved over the past 20 years primarily intended for image-processing applications. The advent of large-scale integrated-circuit technology makes the construction of these processors feasible. In this paper three basic instruction types that characterize a BAP are defined and the systematic design of a processor called BASE is described in detail. Two forms of BASE are discussed, a fully parallel version and an add-on unit for a conventional computer. The systematic design has enabled an assembly language with a simple, APL-like syntax to be developed. Several program examples to illustrate features of the processor are given.

Parallel processors with bit-serial processing elements (PE's) usually implement arithmetic functions by a sequence of word-level arithmetic operations; however, basic operations must be specified at the bit level. In this correspondence the possibility of more efficiently implementing a function with a special tailored sequence of bit-serial operations is considered. A general scheme is described for generating efficient programs to implement arbitrary functions on bit-serial-arithmetic processors. This scheme is based on logic design methodology and involves designing a logic network to realize a desired function. The parallel processor is then used to efficiently simulate a set of these networks. Heuristic design algorithms are used to generate the logic networks; several algorithms are described and compared with some benchmark functions. Several efficient PE designs are described and analyzed.