Several approaches for optical flow estimation use partial differential equations to model changes in image brightness throughout time. A commonly used equation is the so-called optical flow constraint (OFC), which assumes that the image brightness is stationary with respect to time. More recently, a different constraint referred to as the extended optical flow constraint (EOFC) has been introduced, which also contains the divergence of the flow field of image brightness. There is no agreement in the literature about which of these constraints provides the best estimation of the velocity field. Two new solutions for optical flow computation are proposed, which are based on an approximation of the constraint equations. The two techniques have been used with both EOFC and OFC constraint equations. Results achieved by using these solutions have been compared with several well-known computational methods for optical flow estimation in different motion conditions. Estimation errors have also been measured and compared for different types of motion.

Presents a new covariant basis, dubbed the quasi-orthogonal Q-spline basis, for the space of n-degree periodic uniform splines with k knots. This basis is obtained analogously to the B-spline basis by scaling and periodically translating a single spline function of bounded support. The construction hinges on an important theorem involving the asymptotic behavior (in the dimension) of the inverse of banded Toeplitz matrices. The authors show that the Gram matrix for this basis is nearly diagonal, hence, the name "quasi-orthogonal". The new basis is applied to the problem of approximating closed digital curves in 2D images by least-squares fitting. Since the new spline basis is almost orthogonal, the least-squares solution can be approximated by decimating a convolution between a resolution-dependent kernel and the given data. The approximating curve is expressed as a linear combination of the new spline functions and new "control points". Another convolution maps these control points to the classical B-spline control points. A generalization of the result has relevance to the solution of regularized fitting problems.

Different constraint equations have been proposed in the literature for the derivation of optical flow. Despite of the large number of papers dealing with computational techniques to estimate optical flow, only a few authors have investigated conditions under which these constraints exactly model the velocity field, that is, the perspective projection on the image plane of the true 3-D velocity. These conditions are analyzed under different hypotheses, and the departures of the constraint equations in modeling the velocity field are derived for different motion conditions. Experiments are also presented giving measures of these departures and of the induced errors in the estimation of the velocity field.

The paper presents a new approach to least-squares spline fitting of curves. A new approximately orthogonal basis, the Q-spline basis, for n-degree uniform spline space is developed. Using the Q-spline basis, it is shown that least squares spline fitting can be approximated via a single fixed sized inner product for each control point. Another convolution maps these Q-spline control points to the classical B-spline control points. Tight error bounds on the approximation induced errors are derived. Finally a procedure for discrete least squares spline fitting via convolution is presented along with several examples. A generalization of the result has relevance to the solution of regularized fitting problems.>

A conformal mapping-based face representation is presented. This face representation technique combined with an eigenface-based method extends and improves the results obtained with other eigenface algorithms.

We present a method for elastic pattern matching that we apply to segmentation-free OCR. We use a number of digit models (templates) that are allowed to undergo elastic deformation while trying to adapt to the digit image they are exposed to. Each template must satisfy two competing requirements: (1) it must match the image as much as possible and (2) it must keep its elastic deformation energy as little as possible. These two requirements can be expressed in the form of a variational problem, whose solution gives the optimal deformation for a template.

This paper consists of two parts. In the first part, two new algorithms for deadlock- and livelock-free wormhole routing in the torus network are presented. The first algorithm, called Channels, is for the n-dimensional torus network. This technique is fully-adaptive minimal, that is, all paths with a minimal number of hops from source to destination are available for routing, and needs only five virtual channels per bidirectional link, the lowest channel requirement known in the literature for fully-adaptive minimal worm-hole routing. In addition, this result also yields the lowest buffer requirement known in the literature for packet-switched fully-adaptive minimal routing. The second algorithm, called 4-Classes, is for the bidimensional torus network. This technique is fully-adaptive minimal and requires only eight virtual channels per bidirectional link. Also, it allows for a highly parallel implementation of its associated routing node. In the second part of this paper, four worm-hole routing techniques for the two-dimensional torus are experimentally evaluated using a dynamic message injection model and different traffic patterns and message lengths.>

This paper consists of two parts. In the first one, two new algorithms for wormhole routing on the hypercube network are presented. These techniques are adaptive and are ensured to be deadlock- and livelock-free. These properties are guaranteed by using a small number of resources in the routing node. The first algorithm is adaptive and nonminimal and will be referred to as Nonminimal. In this technique, some moderate derouting is allowed in order to alleviate the potential congestion arising from highly structured communication patterns. The second algorithm, dubbed Subcubes, is adaptive and minimal, and is based on partitioning the hypercube into subcubes of smaller dimension; This technique requires only two virtual channels per physical link of the node. In the second part of the paper, a wide variety of techniques for wormhole routing in the hypercube are evaluated from an algorithmic point of view. Five partially adaptive algorithms are considered: the Hanging algorithm, the Zenith algorithm, the Hanging-Order algorithm, the Nonminimal algorithm; and the Subcubes algorithm. One oblivious algorithm, the Dimension-Order, or E-Cube routing algorithm, is also used. Finally, a Fully Adaptive Minimal algorithm is tried. A simple node model was designed and adapted to all the algorithms.>

This paper deals with the problem of packet-switched routing in parallel machines. Several new routing algorithms for different interconnection networks are presented. While the new techniques apply to a wide variety of networks, routing algorithms will be shown for the hypercube, the two-dimensional mesh, and the shuffle-exchange. Although the new techniques are designed for packet routing, they can be used alternatively for virtual cut-through routing models. The techniques presented for hypercubes and meshes are fully-adaptive and minimal. A fully-adaptive and minimal routing is one in which all possible minimal paths between a source and a destination are of potential use at the time a message is injected into the network. Minimal paths followed by messages ultimately depend on the local congestion encountered in each node of the network. All of the new techniques are completely free of deadlock situations.>

Highly parallel systems play a central role in the future of computing. This role is increasing rapidly as the costs involved in improving semiconductor circuit speed and density become higher. The two major hurdles that prevent massive parallelism from becoming mainstream are the relatively slow progress of interconnection networks compared to that of uniprocessor technology and the immature status of parallel software. The paper gives a brief summary of some of the recent advances in the field of highly parallel computing, with an emphasis on message routing architectures.>

This paper consists of two parts. In the first part, a new algorithm for deadlock- and livelock-free routing for the n-dimensional torus network is presented. This algo- rithm, called *-Channels, is fully-adaptive minimal, i.e. all paths with a minimal number of hops from source to destination are available for routing. *-Channels works for messages of unknown size, thus yielding new rout- ing techniques for both packet-switched and worm-hole models. *.Channels differs radically from the packetswitched fully-adaptive minimal methods presented in SPAA '91 by Pifarr6, Gravano, Felperin, and Sanz [PGFS91]. In particular, the packet-based techniques in [PGFS91] do not work for worm-hole routing as dead- lock situations can be constructed.

Article Free Access Share on Fully-adaptive routing: packet switching performance and wormhole algorithms Authors: S. A. Felperin CRAAG IBM Argentina, ESLAI CRAAG IBM Argentina, ESLAIView Profile , L. Gravano CRAAG IBM Argentina, ESLAI CRAAG IBM Argentina, ESLAIView Profile , G. D. Pifarré CRAAG IBM Argentina, ESLAI CRAAG IBM Argentina, ESLAIView Profile , J. L. C. Sanz IBM Almaden Research Center, CRAAG IBM Argentina IBM Almaden Research Center, CRAAG IBM ArgentinaView Profile Authors Info & Claims Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on SupercomputingAugust 1991 Pages 654–663https://doi.org/10.1145/125826.126141Published:01 August 1991Publication History 22citation327DownloadsMetricsTotal Citations22Total Downloads327Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks Authors: Gustavo D. Pifarré ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, CaliforniaView Profile , Luis Gravano ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, CaliforniaView Profile , Sergio A. Felperin ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, California ESLAI, Escuela Superior Latino Americana de Informática, CC 3193, (1000) Buenos Aires, Argentina. and Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina. and Computer Science Dept., IBM Almadeu Research Center, San, José, CaliforniaView Profile , Jorge L. C. Sanz Computer Science Dept., IBM Almaden Research Center, San, José, California., Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, Argentina Computer Science Dept., IBM Almaden Research Center, San, José, California., Computer Research and Advanced Applications Group, IBM, Argentina, Ing. E. Butti 275, (1300) Buenos Aires, ArgentinaView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 278–290https://doi.org/10.1145/113379.113405Published:01 June 1991Publication History 24citation298DownloadsMetricsTotal Citations24Total Downloads298Last 12 Months5Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A survey of some packet-switched routing methods for massively parallel computers is presented. Some of the techniques are applicable to both shared-memory and message-passing architectures. These routing methods are compared in terms of their efficiency in supporting programming models, efficiency in mapping to parallel machines, and practicality. Among the outlined methods, three nonadaptive techniques and some adaptive routing algorithms are discussed.>

This paper presents algorithms for implementing an important image processing operation, the Hough transform, on a mesh connected computer (MCC). The MCC consists of an $N \times N$ array of processors, each of which holds a single pixel of the image. The MCC operates in a Single Instruction Stream, Multiple Data Stream (SIMD) mode, which is in agreement with the hardware constraints found in existing meshes. Five algorithms for computing the Hough transform are presented. These algorithms use a number of different techniques, and they have varying time complexities and architectural requirements. The most notable algorithm presented computes any P angles of the Hough transform in $O(N + P)$ time and uses only a constant amount of memory per processor. Because the Hough transform is a particular case of the discrete Radon transform, all of the algorithms will be presented for computing the Radon transform of gray-level images.

Two parallel algorithms are presented for the problem of labeling the connected components of a binary image. The machine model is an SIMD two-dimensional mesh-connected computer consisting of an N*N array of processing elements, each containing a single pixel of an N*N image. Both new algorithms use a local shrinking operation defined by S. Levialdi (1972) and have time complexities of O(N log N) bit operations, making them the fastest local algorithms for the problem. Compared to other approaches with similar or better asymptotic time complexities, this local approach greatly simplifies the algorithms and reduces the constants of proportionality by nearly two orders of magnitude, making them the first practical algorithms for the problem. The two algorithms differ in the amount of memory required per processing element; the first uses O(N) bits, while the second uses a novel compression scheme to reduce the requirement to O(log N) bits.>

An important midlevel task for computer vision is addressed. The problem consists of labeling connected components in N/sup 1/2/*N/sup 2/2/ binary images. This task can be solved with parallel computers by using a simple and novel algorithm. The parallel computing model used is a synchronous fine-grained shared-memory model where only one processor can read from or write to the same memory location at a given time. This model is known as the exclusive-read exclusive-write parallel RAM (EREW PRAM). Using this model, the algorithm presented has O(log N) complexity. The algorithm can run on parallel machines other than the EREW PRAM. In particular, it offers an optimal image component labeling algorithm for mesh-connected computers.>

Image representation by sign data in its most general context is considered for the case when f is a two-dimensional signal. The authors study conditions under which f is determined by its sign or, in other words, by its quantization to 1 bit of information. This study is carried out in two different directions. First, theoretical results are presented that set an algebraic condition under which real zero-crossings uniquely specify a band-limited image. An interesting paradigm arising in theoretical computer vision is then posed: are the zero-crossing of f convolved with a Laplacian-of-a-Gaussian at a single channel enough for unambiguously representing f? Second, the problem of the completeness of the representation when the position of the zero-crossings is known only approximately is addressed. It is shown that when sign(f) is sampled, significant ambiguities are introduced in the representation. Experimental results are presented which were obtained from an iterative algorithm devised to reconstruct real images from multiscale sign information.>

The complexity of efficiently programming massively parallel machines is illustrated by presenting a number of algorithms. These algorithms deal with computational geometry, data histogramming, list manipulation, and other problems or operations that arise in computer vision tasks. All of the algorithms presented use a divide-and-conquer strategy, and they all use routines that solve a problem of size M using a machine size N, where M>

The Hopfield neural network is a mathematical model in which each neuron performs a threshold logic function. an important property of the model is that a neural network always converges to a stable state when operating in a serial mode. This property is the basis of potential applications of neural networks such as associative memory devices, computational models, etc. This article reviews some of the known properties of the model and presents some new results regarding its possible applications. the principal contributions which are developed in this article are: (1) Showing that a very large class of mappings are not feasible by neural nets, in particular mappings which contain spheres, e.g., Hamming codes. (2) Showing that the neural network model can be designed to perform a local search algorithm for the Directed Min Cut problem. (3) Exploring the term “capacity of the neural network model” and criticizing some results known in the literature. (4) Showing the limitations of the model for its use as a pattern recognizer by proving that all images with a single black point can be recognized by the network iff the network is fully connected.

Machine vision algorithms and a supporting architecture that were integrated in a fully automated prototype system for disk head inspection are presented. Some specific methods are elaborated on, including the computation of the Hough transform and multicode masks in pipeline architectures, object segmentation in textured backgrounds, and matching of extracted defects with inspection specifications. Extensive experimental results are given.>

The problem of computing image texture features in parallel computers is addressed. It is shown that R. Haralick's texture measures (1973) are amenable to efficient implementation in certain fine-grained architectures. The main operation used to compute these features is the SEND, also called Random Access Write, command. This command is efficiently implemented in a number of computers, such as binary n-cubes, mesh-arrays, and some shared-memory systems. It is shown that the computation of gray-level dependency matrices requires random global communication patterns. This feature and the need for other standard local processing make the classification measures proposed by Haralick and his associates good candidates as benchmarks for parallel computer vision architectures.>

The application of a contrast measure for segmenting images and the relationship of this method to polynomial-based classification are considered. The relevance of the segmentation method is shown by applying the contrast measure to a semiconductor manufacturing inspection problem. The contrast measure is shown to be a particular case of a pixel classification technique based on polynomial decision functions and local texture features. This relationship integrates an important heuristic method with the rigorous theory of decision-theoretic classification.>

Machine vision methods are presented for the analysis of solder balls in integrated circuits. The algorithms are founded on counter fitting using a multiparameter Hough transform and on polynomial-classifier-based pattern recognition. The first method is used to show the complexity of the inspection problem, especially in the presence of high-precision requirements. In this connection, it is shown that subpixel accuracy is not obtainable even under the assumption of a perfect camera system which determines the resolution necessary for the measurement of a given maximum-volume distortion. The second method is carried out by computing a large number of features on the original image after individual solder balls are segmented by a projection technique. This approach can be considered as a control-free image segmentation paradigm, since it does not rely on properly sequencing several image-analysis modules. Further experimentation with a large pool of defective solder balls is necessary to confirm the applicability of these machine vision algorithms to a real-world manufacturing inspection systems. A general image-segmentation architecture is proposed, which enables the computation of the necessary low-level image features as well as pixel classification at video-rate speed.>

An algorithm for object recognition which is based on translation and rotation invariant signatures is presented. The Radon transform is used as a tool for efficient implementation of the algorithm. Good classification results where obtained even with objects having similar shapes.

This paper describes the use of an image contrast measure for producing binary segmentations of images in a certain class of applications. This method is well-suited for fast pipeline implementations, because the contrast measure uses only two local features in the image. To eliminate segmentation noise, we post-process the segmentations using binary morphological operations. This method has been applied to three different microelectronics inspection problems, with consistently good results, and experimental results from each of these applications are presented here. Also, we discuss this technique in terms of the theory of polynomial classifiers.

In this paper, we tackle the problem of recovering an image from its Fourier transform phase quantized to 1 bit, or, equivalently, from the zero crossings of the real part of the Fourier transform. We first present new theoretical results that set an algebraic condition under which real zero crossings uniquely specify a band-limited image. We then show, however, through a large-scale set of experiments, that sampling in the frequency domain presents a major obstacle to good reconstruction resuits due to the information loss produced by the approximated knowledge of the zero crossing locations. We finally show that, by using a "coherent" image model in which the image is complex and the spatial-domain phase is random and highly uncorrelated, we can significantly reduce the effect of this information loss and improve the quality of image reconstruction.

We address the problem of segmenting and analyzing images of solder balls in integrated circuits. Two methods are explored, one based on projections computed along curved contours derived from the geometry of the problem, and the other using a supervised, feature-based polynomial classification method. High accuracy is required for the machine vision solution to be successful, and we have included some considerations concerning sub-pixel accuracy for the computation of the values of parameters determining the two-dimensional solder ball shapes. The classification technique has performed with satisfactory results on available data.

In this correspondence, some image transforms and features such as projections along linear patterns, convex hull approximations, Hough transform for line detection, diameter, moments, and principal components will be considered. Specifically, we present algorithms for computing these features which are suitable for implementation in image analysis pipeline architectures. In particular, random access memories and other dedicated hardware components which may be found in the implementation of classical techniques are not longer needed in our algorithms. The effectiveness of our approach is demonstrated by running some of the new algorithms in conventional short-pipelines for image analysis. In related papers, we have shown a pipeline architecture organization called PPPE (Parallel Pipeline Projection Engine), which unleashes the power of projection-based computer vision, image processing, and computer graphics. In the present correspondence, we deal with just a few of the many algorithms which can be supported in PPPE. These algorithms illustrate the use of the Radon transform as a tool for image analysis.

We compare the performance of three algorithms for polar-to-cartesian interpolation in spotlight mode synthetic aperture radar. The original polar data in this case lies far from the origin in a region of very small angular extent.

In this paper, we deal with the problem of detecting and segmenting objects in textured darkfield digital imagery for automated visual inspection applications. The technique we will follow is based on a sequential application of local operators which serves the purpose of clustering the object and the background gray levels. This procedure can be considered as an extension of average-thresholding type techniques. This algorithm has fast implementations in general purpose image processing pipeline architectures and therefore, it is appealing to real-time computer vision applications. Computational examples showing the effectiveness of the segmentation technique will be discussed.

In this paper, we deal with the problem of retrieving a finite-extent signal from the magnitude of its Fourier transform. We consider the discrete phase retrieval problem as a special case of a more general problem which consists of recovering a real-valued signal x from the magnitude of the output of a linear distortion: |Hx| (j), j=1 ....,n. An important result concerning the conditioning of this problem will be obtained for this general setting by means of algebraic-geometric techniques. In particular, the problems of the existence of a solution for phase retrieval, conditioning of the problem and stability of the (essentially) unique solution will be addressed.

This paper deals with the problem of computing, projections of digital images. The novelty of our contribution is that we present algorithms which are suitable for implementation in general purpose image processing and image analysis pipeline architectures. Also, we propose some new pipeline configurations which achieve a remarkable degree of parallelism in the computation of projection data and in fact, of many other geometrical descriptors of digital images. In particular, random access memories and other dedicated hardware devices are not needed in our algorithms. The effectiveness of our approach and feasibility of the proposed architectures are demonstrated by running our algorithms in commercially available short-pipelines for image processing and analysis. Examples are shown of the use of projection data for machine vision applications.

In this letter we pose and answer the following question: Is a band-limited multidimensional signal uniquely determined by a continuous set of samples whose location is given by the zeroes of a polynomial equation? Applications to the theory of reconstruction of finite-extent objects from a set of generalized projections are discussed including the classical problems of parallel X-ray and diffraction tomography.

Several commercially available image processing systems do not have comparators in their arithmetic processors. This fact makes the computation of local minima/maxima of digital images or pixel-by-pixel minima/maxima between two or more images seem impossible. This letter describes an efficient technique for computing maxima and minima without the use of a hardware comparator. The procedure requires only table look-up and simple arithmetic operations, and therefore can be efficiently implemented in commercially available pipeline image processors.

Motivated by the ability of synthetic aperture radar and related imaging systems to produce images of suprisingly high quality, we consider the problem of reconstructing the magnitude of a complex signalffrom samples of the Fourier transform offlocated in a small region offset from the origin. It is shown that high quality speckle reconstructions are possible so long as the phase offis highly random. In this case the quality of the reconstruction is insensitive to the location of the known Fourier data, and edges at all orientations are reproduced equally well. Computer examples are presented demonstrating these attributes.

Recently, two-step procedures for band-limited signal extrapolation have received a great deal of attention in the engineering community ([1],[2]). In this paper, we show that several two-step procedures with different underlying models can be unified by means of non-iterative algorithms for solving optimization problems in Hilbert spaces. In particular, some modifications of these procedures for noisy data are shown to be particular cases of regularization techniques for integral equations of the first kind. We present a result which gives insight into the meaning of the regularizing parameter. Some numerical examples of applying this result to signal extrapolation are shown. This unification together with those presented for iterative least-squares algorithms ([3]), and the prolate spheroidal expansion ([4]), demonstrate that most of the well-known procedures for band-limited extrapolation can be considered as special cases of standard techniques in integral equations and operator theory.