This paper presents a novel two-phase stereo matching algorithm using the random walks framework. At first, a set of reliable matching pixels is extracted with prior matrices defined on the penalties of different disparity configurations and Laplacian matrices defined on the neighbourhood information of pixels. Following this, using the reliable set as seeds, the disparities of unreliable regions are determined by solving a Dirichlet problem. The variance of illumination across different images is taken into account when building the prior matrices and the Laplacian matrices, which improves the accuracy of the resulting disparity maps. Even though random walks have been used in other applications, our work is the first application of random walks in stereo matching. The proposed algorithm demonstrates good performance using the Middlebury stereo datasets.

Summary form only given. This paper presents a framework to effectively compress sets of images in a lossless manner. An image set is represented as a graph and its minimum spanning tree is computed to decide which images and differences to encode. The Centroid scheme and the previous MST scheme can both be represented as a spanning tree in our graph. Thus, the scheme is guaranteed to be no worse than these previous schemes. In fact, the framework provides the best lossless compression for all schemes that consider interimage redundancy between two images in a set. Experimental results show that the new MST method always produces the best result regardless of the properties of the image sets. In some cases, the first-order entropy of the image set using our scheme results in a 29% improvement over the traditional scheme of compressing each image individually.

Summary form only given. This paper presents an algorithm for organizing and compressing groups of similar images using a minimum spanning tree (MST). Called IsMST, it supports content based image retrieval (CBIR) and facilitates better compression performance that is attained using JPEG2000 on each image individually. Preliminary experimental results show that the gains in compression and accuracy of the data organization of the data sets using IsMST are encouraging.

In this paper, we present a method to combine a grammatical model that encodes a priori shape information with the ziplock snakes presented by Neuenschwander et al. A competing mechanism is adopted to take advantage of the shape models without inducing excessive computation. The resulting model-based ziplock snakes have many advantages over the original model: they can accurately locate contour features, produce more refined results, and deal with multiple contours, missing image cues, and noise.

This paper presents a vehicle detection algorithm. We compute fuzzy integrals based on the evidence gathered. We have carried out extensive experiments. For all vehicles in the images, including the ones partially occluded and cut off at the image boundary, we are able to achieve a detection rate of 80% comparing with only 13% in our previous systems. For the vehicles that are almost completely visible, the detection rate was 90%.

Active contour models, or snakes, are effective and robust in contour extraction. In most papers on snakes, an initialization close to the desired contour is assumed to be provided, which is inappropriate in many cases. The ziplock snake model presented by Neuenschwander et al. (1997), however, needs only two user-supplied endpoints. The optimization process for a ziplock snake starts from the two endpoints and progresses towards the center of the snake. In this paper, we present a method to combine a grammatical model that encodes a priori shape information with the ziplock snakes. A competing mechanism is adopted to take advantage of the shape models without inducing excessive computation. The resulting model-based ziplock snakes have many advantages over the original model: They can accurately locate contour features, produce more refined results, and deal with multiple contours, missing image cues and noise.

The original snake models require a close initialization which in many situations are difficult to acquire. The balloon model presented by Cohen et al. to solve this problem suffers from the difficulty of choosing a constant inflating force due to variable internal shrinking forces and non-constant boundary intensity levels. Xu et al., on the other hand, proposed to use a pressure force to exactly offset the shrinking forces. The resulting model achieves better stability in terms of parameter insensitivity by sacrificing smoothness constraints, thus it would go through even small gaps on a boundary. We instead propose to compute an adaptive inflating force locally for each snaxel so that it is just enough to overcome the image force. A new smoothness constraint which can maintain smoothness without any shrinking side-effects is also presented, along with a new way to resample a balloon without significantly reducing its tension. The combined model is sensitive to weak and incomplete boundaries, and yet able to overcome noise edges. Experimental results are reported to support our statements.

Spatial relations between objects are widely used in content-based image retrieval. This paper presents an algorithm for matching spatial relations using dynamic bintree (DB-tree). A DB-tree is balanced and has no coordinates. Its leaf nodes contain the images objects, and the internal nodes and the tree structure indicate the spatial relations among image objects. The time complexity of our matching algorithm is O(n lg m+n), where n and m are the number of objects in a query image and a database image. We have compared the DB-tree data structure and the matching algorithm with other schemes, such as 2D-strings. For applications like "Campus Event" image retrieval, the theoretical analysis and experimental results show that the DB-tree approach out-performs 2D-strings in several aspects.

Segmentation of ultrasound images is difficult due to the existence of speckle noise. Erroneous edges from speckle noise are not only abundant but also have large magnitude due to the multiplicative nature of speckle noise. Moreover, boundary edges are usually incomplete, being missing or weak at some places. We propose a system to address these problems in two steps. First, based on the observation that boundaries in ultrasound images have the appearance of straight or gently curving line segments, we adopt Sha'ahsua and Ullman's (1988) saliency map method to reduce speckle noise and enhance edges. Then we use a new snake model, which we call a systolic snake, to perform a multi-level feature search. The systolic snake can not only overcome local minima, but also effectively use both strong and weak image information. Furthermore, the system can be used in an automatic system since, unlike other snake models, ours does not need a close initialization The resulting system is tested on some ultrasound loin images and results are promising.

Image compression schemes consist of compression and decompression phases. Often, the decompression phase includes mechanisms for improving the quality of the resulting image. Quadtree compression is one such type of compression. Reconstructed quadtree images can be blocky because of the nature of the compression method, unless additional processing, generally smoothing, is performed. We propose improvements over the reconstruction method described by Shusterman and Feder. The improvements consist of the introduction of a simpler and more effective 2 x 2 reconstruction filter to replace the suggested 3 x 3 filter, and the addition of a reconstruction threshold to preserve image edges. This method is compared experimentally to the original algorithm and also to JPEG compression in terms of complexity and resulting image quality.

Many lossy compression algorithms have been proposed that perform well for low bit rates, but are computationally intense. On the other hand, there are many simple algorithms that perform poorly at high compression ratios. An algorithm that incorporates both computational simplicity and acceptable performance at low bit rates would have many potential applications. In wireless communications, for example, where computing power and transmission speed are important factors, the time required to compress and send image data would need to be reduced significantly. A low bit rate compression algorithm that is conceptually simple as well as computationally efficient is presented in this paper. Theoretically, it can be shown to be computationally superior to JPEG in the compression phase, and comparable in the decompression phase. In practice, the quality of the results, as measured by the PSNR, is found to be better than JPEG results at bit rates lower than about 0.2-0.3 bpp depending on the input image.

Proposes a simple, yet general and powerful, region-growing framework for image segmentation. The region-growing process is guided by regional feature analysis; no parameter tuning or a priori knowledge about the image is required. To decide if two regions should be merged, instead of comparing the difference of region feature means with a predefined threshold, the authors adaptively assess region homogeneity from region feature distributions. This results in an algorithm that is robust with respect to various image characteristics. The merge criterion also minimizes the number of merge rejections and results in a fast region-growing process that is amenable to parallelization.

In parallel matrix manipulation operations, some data patterns need to be accessed in one memory cycle without conflict. Investigating the frequently used data patterns, we propose a powerful skewing scheme which allows most frequently used data patterns of N elements, including rows, columns, diagonals, blocks with various shapes, points scattered over various blocks, and chessboards with various shapes, to be accessed in one memory cycle. We also propose simple methods to combine different skewing schemes into a single parallel storage system such that all the frequently used data patterns of N elements (the above patterns plus folded lines, two-pairs, and column-pairs) can be accessed in one memory cycle. The storage sytem uses N memory modules where N is any (even or odd) power of two. Address generation in the system need only exclusive-or operations and can be completed in constant time. The storage scheme allows different sized matrices to be processed efficiently on large scale systems by using the skewing scheme designed according to the size of the system, i.e. address generation mechanism is independent of the size of the matrices to be processed. Data alignment requirements (connecting each memory module to a proper processor) can be easily realized on a general-purpose interconnecting network, such as a hypercube.

Parallel algorithms on SIMD (single-instruction stream multiple-data stream) machines for hierarchical clustering and cluster validity computation are proposed. The machine model uses a parallel memory system and an alignment network to facilitate parallel access to both pattern matrix and proximity matrix. For a problem with N patterns, the number of memory accesses is reduced from O(N/sup 3/) on a sequential machine to O(N/sup 2/) on an SIMD machine with N PEs.>

Several parallel algorithms and parallel architectures have been developed for partitional clustering. Hierarchical clustering algorithms are also widely used in exploratory pattern analysis and unsupervised learning. The author proposes parallel algorithms on single-instruction/multiple-data (SIMD) machines for hierarchical clustering, which require intensive computation and large memory storage. The machine model includes a parallel memory system and an alignment network, to facilitate parallel access of both pattern matrix and proximity matrix. Since clustering algorithms tend to generate clusters even when applied to random data, clustering-tendency and cluster-validity studies are usually performed. The author proposes a parallel algorithm to compute one type of cluster validity measure global fit of hierarchy for quantitative data. For a problem with N patterns, considering validity study as well as clustering, the number of memory accesses is reduced from O(/sup 3/) on a sequential machine to O(N/sup 2/) on a SIMD machine with N processing elements (PEs). More general algorithms for different numbers of PEs are also given.>

Several parallel convolution algorithms for array processors with N/sup 2/ processing elements (PEs) connected by mesh, hypercube, and shuffle-exchange topologies, respectively, are presented. The computation time complexity is the same for array processors with different interconnection networks. The communication time complexity, however, varies from network to network, and is the main focus. It is shown that by using inter-PE communication networks efficiently, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the overall time complexity (including computation and communication) of algorithms is reduced to O(M/sup 2/).>

This correspondence presents several parallel algorithms for image template matching on an SIMD array processor with a hypercube interconnection network. For an N by N image and an M by M window, the time complexity is reduced from O(N2M2) for the serial algorithm to O(M2/K2 + M * log2 N/K + log2 N * log2 K) for the N2K2-PE system (1 ¿ K ¿ M), or to O(N2M2/L2) for the L2-PE system (L ¿ N). With efficient use of the inter-PE communication network, each PE requires only a small local memory, many unnecessary data transmissions are eliminated, and the time complexity is greatly reduced.

The hypergeometric distribution is a widely used arithmetic function and is fundamental to many statistical sampling and statistical pattern recognition problems. Computation of the cumulative hypergeometric distribution function, H(a), is extremely time-consuming. As a result, many approximation algorithms have been proposed to evaluate the cumulative hypergeometric distribution. This paper describes a two-level pipeline architecture for computing H(a) with computation complexity reduced to c+a, where c is a constant. The main part of the design is a type of recurrence computation. A modular and systematic approach is suggested to implement the recurrence formula. The computation complexity of the proposed architecture is also compared with various other known methods. The highly regular structure of the design can lead to efficient VLSI implementation.

This paper formulates the problem encountered in the first stage of two-stage, binary template matching as a set of hypotheses to be tested, including a hypothesis of ``no object.'' Two new statistics R and G are proposed, based on a likelihood ratio, and are compared to the sum of absolute differences and a correlation measure by analytical approximations and Monte Carlo experiments. Statistical power and a measure of sensitivity to the true location of the object are the criteria. Parameters are the numbers of 1's in object and image, subtemplate size, and parameters reflecting intensity distortion between template and object. One of the proposed statistics R is much more computationally intensive than the other G. Although R is more powerful than G and the other statistics, G is generally more sensitive to the true object location. Statistic G is also more powerful than the sum of absolute differences and correlation. All statistics are robust to incomplete knowledge of distortion parameters. Experiments on Landsat images confirm the sensitivity of G and recommend it for application in the first stage.