In this study, we investigate the challenge of detecting smart mobile evaders initially located inside a predefined planar circular region from which they try to escape without being detected by a line formation of sweeping agents. We propose spiral sweeping protocols designed to successfully carry out the task by setting specific conditions on both the speed and trajectory of the sweeping formation. These protocols are crafted to ensure that evaders, constrained by a set speed limit, cannot elude the formation’s agents. At first, the focus is on containing these evaders within a designated area. Achieving this is contingent upon certain geometric and dynamic prerequisites, which determine the minimum speed threshold for the sweepers. If the sweepers’ speed surpasses this lower bound, they are not only capable of confinement but also of complete detection, suggesting that with the right strategy, they can detect every smart evader. We present two new spiral line formation search protocols tailored for the detection of smart evaders, overcoming existing gaps in search methodologies. In addition, we conduct a comprehensive analysis comparing previously designed circular line formation sweep protocols with our newly devised protocols. Our comparative study is based on two key metrics: the duration required to detect all evaders and the minimal critical speed essential for a successful search. By evaluating these different strategies, we prove that our proposed protocols achieve a critical speed that is only slightly larger than the theoretical lower bound and that the total search time required is considerably shorter compared with previous approaches.

Dimensionality reduction is a fundamental task that aims to simplify complex data by reducing its feature dimensionality while preserving essential patterns, with core applications in data analysis and visualisation. To preserve the underlying data structure, multi-dimensional scaling (MDS) methods focus on preserving pairwise dissimilarities, such as distances. They optimise the embedding to have pairwise distances as close as possible to the data dissimilarities. However, the current standard is limited to embedding data in Riemannian manifolds. Motivated by the lack of asymmetry in the Riemannian metric of the embedding space, this paper extends the MDS problem to a natural asymmetric generalisation of Riemannian manifolds called Finsler manifolds. Inspired by Euclidean space, we define a canonical Finsler space for embedding asymmetric data. Due to its simplicity with respect to geodesics, data representation in this space is both intuitive and simple to analyse. We demonstrate that our generalisation benefits from the same theoretical convergence guarantees. We reveal the effectiveness of our Finsler embedding across various types of non-symmetric data, highlighting its value in applications such as data visualisation, dimensionality reduction, directed graph embedding, and link prediction.

We investigate the algorithmic problem of uniformly dispersing a swarm of robots in an unknown, gridlike environment. In this setting, our goal is to study the relationships between performance metrics and robot capabilities. We introduce a formal model comparing dispersion algorithms based on makespan, traveled distance, energy consumption, sensing, communication, and memory. Using this framework, we classify uniform dispersion algorithms according to their capability requirements and performance. We prove that while makespan and travel can be minimized in all environments, energy cannot, if the swarm's sensing range is bounded. In contrast, we show that energy can be minimized by “ant-like” robots in synchronous settings and asymptotically minimized in asynchronous settings, provided the environment is topologically simply connected, by using our “Find-Corner Depth-First Search” (FCDFS) algorithm. Our theoretical and experimental results show that FCDFS significantly outperforms known algorithms. Our findings reveal key limitations in designing swarm robotics systems for unknown environments, emphasizing the role of topology in energy-efficient dispersion.

Suppose in a given planar region, there are smart mobile evaders and we want to detect them using sweeping agents. We assume that the agents have line sensors of equal length. We propose procedures for designing cooperative sweeping processes that ensure successful completion of the task, thereby deriving conditions on the sweeping velocity of the agents and their paths. Successful completion of the task means that evaders with a known limit on their velocity cannot escape detection by the sweeping agents. A simpler task for the sweeping swarm is the confinement of the evaders to their initial domain. The feasibility of completing these tasks depends on geometric and dynamic constraints that impose a lower bound on the velocity the sweeping agent must have. This critical velocity is derived to ensure the achievement of the confinement task. Increasing the velocity above the lower bound enables the agents to complete the search task as well. We present results on the total search time for two types of novel pincer-movement search processes, circular and spiral, for any even number of sweeping agents. The proposed spiral process allows detection of all evaders while sweeping at velocities that approach the theoretical lower bound.

Holographic representations of data enable distributed storage with progressive refinement when the stored packets of data are made available in any arbitrary order. In this paper, we propose and test patch-based transform coding holographic sensing of image data. Our proposal is optimized for progressive recovery under random order of retrieval of the stored data. The coding of the image patches relies on the design of distributed projections ensuring best image recovery, in terms of the $\ell_2$ norm, at each retrieval stage. The performance depends only on the number of data packets that have been retrieved thus far. Several possible options to enhance the quality of the recovery while changing the size and number of data packets are discussed and tested. This leads us to examine several interesting bit-allocation and rate-distortion trade-offs, highlighted for a set of natural images with ensemble estimated statistical properties.

In this work we propose a method for optimizing the lossy compression for a network of diverse reconstruction systems. We focus on adapting a standard image compression method to a set of candidate displays, presenting the decompressed signals to viewers. Each display is modeled as a linear operator applied after decompression, and its probability to serve a network user. We formulate a complicated operational rate-distortion optimization trading-off the network's expected mean-squared reconstruction error and the compression bit-cost. Using the alternating direction method of multipliers (ADMM) we develop an iterative procedure where the network structure is separated from the compression method, enabling the reliance on standard compression techniques. We present experimental results showing our method to be the best approach for adjusting high bit-rate image compression (using the state-of-the-art HEVC standard) to a set of displays modeled as blur degradations.

Many information systems employ lossy compression as a crucial intermediate stage among other processing components. While the important distortion is defined by the system's input and output signals, the compression usually ignores the system structure, therefore, leading to an overall suboptimal rate-distortion performance. In this paper we propose a compression methodology for an operational rate-distortion optimization considering a known system layout, modeled using linear operators and noise. Using the alternating direction method of multipliers (ADMM) technique, we show that the design of the new globally-optimized compression reduces to a standard compression of a “system adjusted” signal. Essentially, the proposed framework leverages standard compression techniques to address practical settings of the remote source coding problem. We further explain the main ideas of our method by theoretically studying the case of a cyclo-stationary Gaussian signal. We present experimental results for coding of one-dimensional signals and for video compression using the HEVC standard, showing significant gains by the adjustment to an acquisition-rendering system.

In imaging systems, following acquisition, an image/ video is transmitted or stored and eventually presented to human observers using different and often imperfect display devices. While the resulting quality of the output image may severely be affected by the display, this degradation is usually ignored in the preceding compression. In this paper we model the sub-optimality of the display device as a known degradation operator applied on the decompressed image/video. We assume the use of a standard compression path, and augment it with a suitable pre-processing procedure, providing a compressed signal intended to compensate the degradation without any post-filtering. Our approach originates from an intricate rate-distortion problem, optimizing the modifications to the input image/video for reaching best end-to-end performance. We address this seemingly computationally intractable problem using the alternating direction method of multipliers (ADMM) approach, leading to a procedure in which a standard compression technique is iteratively applied. We demonstrate the proposed method for adjusting HEVC image/video compression to compensate post-decompression visual effects due to a common type of displays. Particularly, we use our method to reduce motion-blur perceived while viewing video on LCD devices. The experiments establish our method as a leading approach for preprocessing high bit-rate compression to counterbalance a postdecompression degradation.

In this paper, we propose a novel algorithm for tracing object boundaries automatically based on a model called “point flow” in image induced vector fields. An ordinary differential equation describes the movement of points under the action of an image-induced vector field and generates induced trajectories. The trajectories of the flows allow to find and integrate edges and determine object boundaries. We tested our method on real image dataset. Compared with the other classical edge detection and integration models, our point flow method is better at providing precise and continuous curves. The experimental results clearly exhibit the robustness and effectiveness of the proposed method.

The introduction of consumer RGB-D scanners set off a major boost in 3D computer vision research. Yet, the precision of existing depth scanners is not accurate enough to recover fine details of a scanned object. While modern shading based depth refinement methods have been proven to work well with Lambertian objects, they break down in the presence of specularities. We present a novel shape from shading framework that addresses this issue and enhances both diffuse and specular objects' depth profiles. We take advantage of the built-in monochromatic IR projector and IR images of the RGB-D scanners and present a lighting model that accounts for the specular regions in the input image. Using this model, we reconstruct the depth map in real-time. Both quantitative tests and visual evaluations prove that the proposed method produces state of the art depth reconstruction results.

In this paper we propose a method for solving various imaging inverse problems via complexity regularization that leverages existing image compression techniques. Lossy compression has already been proposed in the past for Gaussian denoising - the simplest inverse problem. However, extending this approach to more complicated inverse problems (e.g., deblurring, inpainting, etc.) seemed to result in intractable optimization tasks. In this work we address this difficulty by decomposing the complicated optimization problem via the Half Quadratic Splitting approach, resulting in a sequential solution of a simpler l2-regularized inverse problem followed by a rate-distortion optimization, replaced by an efficient compression technique. In addition, we suggest an improved complexity regularizer that quantifies the average block-complexity in the restored signal, which in turn, extends our algorithm to rely on averaging multiple decompressed images obtained from compression of shifted images. We demonstrate the proposed scheme for inpainting of corrupted images, using leading image compression techniques such as JPEG2000 and HEVC.

In this paper, we propose a novel postprocessing technique for compression-artifact reduction. Our approach is based on posing this task as an inverse problem, with a regularization that leverages on existing state-of-the-art image denoising algorithms. We rely on the recently proposed Plug-and-Play Prior framework, suggesting the solution of general inverse problems via alternating direction method of multipliers, leading to a sequence of Gaussian denoising steps. A key feature in our scheme is a linearization of the compression-decompression process, so as to get a formulation that can be optimized. In addition, we supply a thorough analysis of this linear approximation for several basic compression procedures. The proposed method is suitable for diverse compression techniques that rely on transform coding. In particular, we demonstrate impressive gains in image quality for several leading compression methods-JPEG, JPEG2000, and HEVC.

The popularity of low-cost RGB-D scanners is increasing on a daily basis. Nevertheless, existing scanners often cannot capture subtle details in the environment. We present a novel method to enhance the depth map by fusing the intensity and depth information to create more detailed range profiles. The lighting model we use can handle natural scene illumination. It is integrated in a shape from shading like technique to improve the visual fidelity of the reconstructed object. Unlike previous efforts in this domain, the detailed geometry is calculated directly, without the need to explicitly find and integrate surface normals. In addition, the proposed method operates four orders of magnitude faster than the state of the art. Qualitative and quantitative visual and statistical evidence support the improvement in the depth obtained by the suggested method.

Two complementary approaches have been extensively used in signal and image processing leading to novel results, the sparse representation methodology and the variational strategy. Recently, a new sparsity based model has been proposed, the cosparse analysis framework, which may potentially help in bridging sparse approximation based methods to the traditional total-variation minimization. Based on this, we introduce a sparsity based framework for solving overparameterized variational problems. The latter has been used to improve the estimation of optical flow and also for general denoising of signals and images. However, the recovery of the space varying parameters involved was not adequately addressed by traditional variational methods. We first demonstrate the efficiency of the new framework for one dimensional signals in recovering a piecewise linear and polynomial function. Then, we illustrate how the new technique can be used for denoising and segmentation of images.

Shape recovery based on shading variations of a lighted object was recently revisited with improvements that allow for the photometric stereo approach to serve as a competitive alternative for other shape reconstruction methods. However, most efforts of using photometric stereo tend to ignore some factors that are relevant in practical applications. The approach we consider tackles the photometric stereo reconstruction in the case of near-field imaging which means that both camera and light sources are close to the imaged object. The known challenges that characterize the problem involve perspective viewing geometry, attenuation of light and possibly missing regions. Here, we pay special attention to the question of how to faithfully model these aspects and by the same token design an efficient and robust numerical solver. We present a well-posed mathematical representation that integrates the above assumptions into a single coherent model. The surface reconstruction in our near-field scenario can then be executed efficiently in linear time. The merging strategy of the irradiance equations provided for each light source allows us to consider a characteristic expansion model which enables the direct computation of the surface. We evaluate several types of light attenuation models with nonuniform albedo and noise on synthetic data using four virtual sources. We also demonstrate the proposed method on surface reconstruction of real data using three images, each one taken with a different light source.

Shape from shading and photometric stereo are two fundamental problems in computer vision aimed at reconstructing surface depth given either a single image taken under a known light source or multiple images taken under different illuminations from the same viewing angle. Whereas the former uses partial differential equation techniques to solve the image irradiance equation, the latter can be expressed as a linear system of equations in surface derivatives when three or more images are given. Therefore, it seems that current photometric stereo techniques do not extract all possible depth information from each image by itself. Extending our previous results on this problem, we consider the more realistic perspective projection of surfaces during the photographic process. Under this assumption, there is a unique weak solution (Lipschitz continuous) to the problem at hand, solving the well-known convex/concave ambiguity of the shape from shading problem. The main contribution of this paper is based on a new differential approach for multi-image photometric stereo. Most of the existing works on this topic do not directly address this problem. The common approach is to estimate the gradient field of the surface by minimizing some functional and integrate it afterwards to find the depth and hence the geometry of the object. Our new differential approach allows us to solve the problem directly, while dealing with images having missing parts. The mathematical well-posedness of the new formulation allows a fast numerical algorithm based on a combination of fast marching and fast sweeping methods.

Shape recovery of an object based on shading variations resulting from different light sources has recently been reconsidered. Improvements have been made that allow for the photometric stereo approach to serve as a competitive alternative to other shape reconstruction methods. However, most photometric stereo methods tend to ignore factors that are relevant in practical applications. The setup considered in this paper tackles photometric stereo reconstruction in the case of a specific near-field imaging. This means that both the camera and the light sources are close to the imaged object, where close can be loosely considered as a setup having similar distances between lights, camera, and object. The known challenges that characterize the problem involve perspective viewing geometry, point light sources, and images that may include shadowed regions. Here, we pay special attention to the question of how to faithfully model these aspects and at the same time design an efficient and robust numerical solver. We present a mathematical formulation that integrates the above assumptions into a single coherent model based on quasi-linear PDEs. The well-posedness is proved showing uniqueness of a weak (i.e., Lipschitz continuous) solution. The surface reconstruction in our near-field scenario can then be executed efficiently in linear time. The merging strategy of the irradiance equations provided for each light source allows us to consider a characteristic expansion model which enables the direct computation of the surface. We evaluate several types of light attenuation models with a nonuniform albedo and noise on synthetic data. We also demonstrate the proposed method on surface reconstruction of real data using three images, each one taken with a different light source by a working prototype. We demonstrate the accuracy of the proposed method compared to other methods that ignore the near-field setup and assume distant, parallel beam light sources.

Reconstruction of 3D objects Based on images is useful in many applications. One of the methods Based on multi-image data is the Photometric Stereo technique relying on several photographs of the observed object from the same point of view, each one taken under a different illumination condition. The common approach is to estimate the gradient field of the surface by minimizing a functional, integrating the distance from the camera and thereby obtaining the geometry of the observed object. We propose an alternative method that consists of a novel differential approach for multi-image Photometric Stereo and permits a direct solution of a novel PDE Based model without going through the gradient field while naturally dealing with shadowed regions. The mathematical well-posed ness of the problem in terms of numerical stability yields a fast algorithm that efficiently converges, even for pictures of sizes in the order of several mega pixels affected by noise.

An isomorphism between two graphs is a connectivity preserving bijective mapping between their sets of vertices. Finding isomorphisms between graphs, or between a graph and itself (automorphisms), is of great importance in applied sciences. The inherent computational complexity of this problem is as yet unknown. Here, we introduce an efficient method to compute such mappings using heat kernels associated with the graph Laplacian. While the problem is combinatorial in nature, in practice we experience polynomial runtime in the number of vertices. As we demonstrate, the proposed method can handle a variety of graphs and is competitive with state-of-the-art packages on various important examples.

A simple method to generate a 2-D binary grid pattern, which allows for absolute and accurate self-location in a finite planar region, is proposed. The pattern encodes position information in a local way so that reading a small number of its black or white pixels at any place provides sufficient data from which the location can be decoded both efficiently and robustly.

Sparse and redundant representation modeling of data assumes an ability to describe signals as linear combinations of a few atoms from a pre-specified dictionary. As such, the choice of the dictionary that sparsifies the signals is crucial for the success of this model. In general, the choice of a proper dictionary can be done using one of two ways: i) building a sparsifying dictionary based on a mathematical model of the data, or ii) learning a dictionary to perform best on a training set. In this paper we describe the evolution of these two paradigms. As manifestations of the first approach, we cover topics such as wavelets, wavelet packets, contourlets, and curvelets, all aiming to exploit 1-D and 2-D mathematical models for constructing effective dictionaries for signals and images. Dictionary learning takes a different route, attaching the dictionary to a set of examples it is supposed to serve. From the seminal work of Field and Olshausen, through the MOD, the K-SVD, the Generalized PCA and others, this paper surveys the various options such training has to offer, up to the most recent contributions and structures.

We consider an underdetermined linear system of equations Ax = b with non-negative entries in A and b, and seek a non-negative solution x. We generalize known equivalence results for the basis pursuit, for an arbitrary matrix A, and an arbitrary monotone element-wise concave penally replacing the lscr1-norm in the objective function. This result is then used to show that if there exists a sufficiently sparse solution to Ax = b, x > 0, it is necessarily unique.

An underdetermined linear system of equationsAx=bwith nonnegativity constraintxges 0 is considered. It is shown that for matricesAwith a row-span intersecting the positive orthant, if this problem admits a sufficiently sparse solution, it is necessarily unique. The bound on the required sparsity depends on a coherence property of the matrixA. This coherence measure can be improved by applying a conditioning stage onA, thereby strengthening the claimed result. The obtained uniqueness theorem relies on an extended theoretical analysis of the lscr0- lscr1equivalence developed here as well, considering a matrixAwith arbitrary column norms, and an arbitrary monotone element-wise concave penalty replacing the lscr1-norm objective function. Finally, from a numerical point of view, a greedy algorithm-a variant of the matching pursuit-is presented, such that it is guaranteed to find this sparse solution. It is further shown how this algorithm can benefit from well-designed conditioning ofA.

In this paper, we consider the problem of boundary fill of a 4 or 8-connected region in a graphic device having a color image frame-buffer memory. We provide an algorithm that solves the problem in a time linear in the number of pixels in the region and requiring only constant memory space in addition to the frame-buffer memory itself. We map this problem to a boundary fill problem in a general graph, and solve it using a novel depth first search-based algorithm.

Spatial de-interlacing is an essential part of motion adaptive de-interlacing used for reconstructing missing lines in cases of fast motion detection. Common spatial de-interlacing algorithms often produce artifacts in the output image, especially along edges with flat horizontal angles. In this paper we introduce a new method for spatial de-interlacing based on the dynamic time warping (DTW) procedure. The DTW algorithm finds an alignment between two original consecutive lines, and then, the missing line between them is reconstructed based on this alignment. This method preserves the smoothness of the original image edges and produces a high quality progressive image.

Several recent works considered multi agents robotics in static environments. In this work we examine ways of operating in dynamic environments, in which changes may take place regardless of the agents' activity. The work focuses on a dynamic variant of the known Cooperative Cleaners problem (described and analyzed in [I.A. Wagner et al., (1997)]). This problem assumes a grid, part of which is "dirty", when the "dirty" part is a connected region of the grid. On this dirty region several agents move, each having the ability to "clean" the place it is located in. The dynamic variant of the problem involves a deterministic evolution of the environment, simulating a spreading contamination, or fire. A cleaning protocol for the problem is presented, as well as several analytic bounds for it. In addition, the work contains simulative results for the proposed protocol.

In this paper, we propose a set of human perceptual cues used jointly to automatically detect image orientation. The cues used are: orientation of faces, position of the sky, brighter regions, and textured objects, and symmetry. We combine these cues in a Bayesian framework, and the photo acquiring model has been considered carefully as the prior knowledge of the image orientation. Results on more than a thousand different images provide a compelling argument that our approach is a viable one.

Inspired by the abilities of both the praying mantis and the pigeon to judge distance by use of motion-based visually mediated odometry, we create miniature models for depth estimation that are similar to the head movements of these animals. We develop mathematical models of the praying mantis and pigeon visual behavior and describe our implementation and experimental environment. We investigate structure from motion problems when images are taken from a camera whose focal point is translating the first case is reminiscent of a praying mantis peering its head left and right, apparently to obtain depth perception, hence the moniker "mantis head camera." In the second case this motion is reminiscent of a pigeon bobbing its head back and forth, also apparently to obtain depth perception, hence the moniker " pigeon head camera." We present the performance of the mantis head camera and pigeon head camera models and provide experimental results of the algorithms. We provide the comparison of the definitiveness of the results obtained by both models. The precision of our mathematical model and its implementation is consistent with the experimental facts obtained from various biological experiments.

The most popular lossy image compression method used on the Internet is the JPEG standard. JPEG's good compression performance and low computational and memory complexity make it an attractive method for natural image compression. Nevertheless, as we go to low bit rates that imply lower quality, JPEG introduces disturbing artifacts. It is known that, at low bit rates, a down-sampled image, when JPEG compressed, visually beats the high resolution image compressed via JPEG to be represented by the same number of bits. Motivated by this idea, we show how down-sampling an image to a low resolution, then using JPEG at the lower resolution, and subsequently interpolating the result to the original resolution can improve the overall PSNR performance of the compression process. We give an analytical model and a numerical analysis of the down-sampling, compression and up-sampling process, that makes explicit the possible quality/compression trade-offs. We show that the image auto-correlation can provide a good estimate for establishing the down-sampling factor that achieves optimal performance. Given a specific budget of bits, we determine the down-sampling factor necessary to get the best possible recovered image in terms of PSNR.

An elementary proof of a basic uncertainty principle concerning pairs of representations of R/sup N/ vectors in different orthonormal bases is provided. The result, slightly stronger than stated before, has a direct impact on the uniqueness property of the sparse representation of such vectors using pairs of orthonormal bases as overcomplete dictionaries. The main contribution in this paper is the improvement of an important result due to Donoho and Huo (2001) concerning the replacement of the l/sub 0/ optimization problem by a linear programming (LP) minimization when searching for the unique sparse representation.

The problem of binarization of gray level images acquired under nonuniform illumination is reconsidered. Yanowitz and Bruckstein (1989) proposed to use an adaptive threshold surface, determined by interpolation of the image gray levels at points where the image gradient is high. The rationale is that a high image gradient indicates probable object edges, and there the image values are between the object and background gray levels. The threshold surface was determined by successive overrelaxation as the solution of the Laplace equation. This work proposes a different method to determine an adaptive threshold surface. In this new method, inspired by multiresolution approximation, the threshold surface is constructed with considerably lower computational complexity and is smooth, yielding faster image binarizations and better visual performance.

An elementary proof of a basic uncertainty principle concerning pairs of representations of /spl Rscr//sup N/ vectors in different orthonormal bases is provided. The result, slightly stronger than stated before, has a direct impact on the uniqueness property of the sparse representation of such vectors using pairs of orthonormal bases as overcomplete dictionaries. The main contribution in this paper is the improvement of an important result due to Donoho and Huo (1999) concerning the replacement of the l/sub 0/ optimization problem by a linear programming minimization when searching for the unique sparse representation.

Lossy transform compression of images is very successful and widespread. The JPEG standard uses the discrete cosine transform on blocks of the image and a bit allocation process that takes advantage of the uneven energy distribution in the transform domain. For most images 10:1 compression ratios can be achieved with no visible degradations. Suppose however that multiple versions of the compressed image exist in a distributed environment such as the Internet, and several of them could be made available upon request. The classical approach would provide no improvement in the image quality if more than one version of the compressed image became available. In this paper we propose a method, based on multiple description scalar quantization, that yields decompressed image quality improving with the number of compressed versions available.

Qjidaa and Radouane (1999) presented a method for robust line fitting and experimentally compared it to other methods, including a method suggested by us. The results attributed by Qjidaa and Radouane to our algorithm are incorrect. We apply our algorithm to the data used by Qjidaa and Radouane and demonstrate its robustness and accuracy.

Given a graph G(V,E), we consider the problem of deciding whether G is Hamiltonian, that is, whether or not there is a simple cycle in E spanning all vertices in V. This problem is known to be NP-complete, hence cannot be solved in time polynomial in |V| unless P=NP. The problem is a special case of the Travelling Salesperson Problem (TSP), that was extensively studied in the literature, and has recently been attacked by various ant-colony methods. We address the Hamiltonian cycle problem using a new ant-inspired approach, based on repeated covering of the graph. Our method is based on a process in which an ant traverses the graph by moving from vertex to vertex along the edges while leaving traces in the vertices, and deciding on the next step according to the level of traces in the surrounding neighborhood. We show that Hamiltonian cycles are limit cycles of the process, and investigate the average time needed by our ant process to recognize a Hamiltonian graph, on the basis of simulations made over large samples of random graphs with varying density of edges.

We investigate how a given fixed number of points should be located in space so that the pose of a camera viewing them from unknown locations can be estimated with the greatest accuracy. We show that optimum solutions are obtained when the points form concentric complete regular polyhedra. For the case of optimal configurations, we provide a worst-case error analysis and use it to analyze the effects of weak perspective approximation to true perspective viewing. Comprehensive computer simulations validate the theoretical results.

We investigate the ability of a group of robots, that communicate by leaving traces, to perform the task of cleaning the floor of an un-mapped building, or any task that requires the traversal of an unknown region. More specifically, we consider robots which leave chemical odour traces that evaporate with time, and are able to evaluate the strength of smell at every point they reach, with some measurement error. Our abstract model is a decentralized multi-agent adaptive system with a shared memory, moving on a graph whose vertices are the floor-tiles. We describe three methods of covering a graph in a distributed fashion, using smell traces that gradually vanish with time, and show that they all result in eventual task completion, two of them in a time polynomial in the number of tiles. Our algorithms can complete the traversal of the graph even if some of the agents die or the graph changes during the execution, as long as the graph stays connected. Another advantage of our agent interaction processes is the ability of agents to use noisy information at the cost of longer cover time.

Several unconventional ideas for viewer/camera pose estimation are discussed. The methods proposed so far advocate the use of advanced image processing for identification and precise location of calibration objects in the images acquired and base pose recovery on the identification of the viewing dependent deformations of these objects. We propose to more fully exploit the freedom in the design of "space fiducials" or calibration objects showing that we can build objects whose images directly encode, in easily identifiable gray-level/color or temporal patterns, the pose of their viewer. We also show how to construct high-precision fiducials, which can determine a viewing direction quite accurately when it is known to lie within a relatively narrow range.

We propose a new approach to skew-symmetry detection, based on the theory of invariant signatures for planar objects. Invariant signatures associated to object boundaries are generalizations of the curvature versus arclength description of curves, invariant under geometric transformations more complex than the Euclidean ones. We show that symmetries of objects, and hence of closed boundaries, translate into simple structures in the invariant signature functions and are therefore, in principle, readily detectable.

We discuss a new type of holographic image representations that have advantages in a "distributed" world. We call these representations holographic. Arbitrary portions of a holographic representation enable reconstruction of the whole image, with distortions that decrease gradually with the increase in the size of the portions available. Holographic representations enable progressive refinement in image communication or retrieval tasks, with no restrictions on the order in which the data fragments (sections of the representation) are accessed or become available.

This correspondence deals with the problem of designing planar shapes for subpixel image registration. Basic theoretical considerations are shown to lead to a lower bound on location accuracy. Optimal registration marks achieving this bound are discussed. These optimal designs, however, require very high printing or etching resolution and are inherently very sensitive to variations in the image sampling model (like scaling of grid size and rotation). More robust, optimal and suboptimal "topology-preserving" registration marks are then introduced and analyzed.

This paper presents a new algorithm for planning the time-optimal motion of a robot travelling with limited velocity from a given location to a given destination on a surface in the presence of moving obstacles. Additional constraints such as space variant terrain traversability and fuel economy can be accommodated. A multivalued distance map is defined and applied in computing optimal trajectories. The multivalued distance map incorporates constraints imposed by the moving obstacles, surface topography, and terrain traversability. It is generated by an efficient numerical curve propagation technique.

We discuss holographic image representations. Arbitrary portions of a holographic representation enable reconstruction of the whole image, with distortions that decrease gradually with the increase of the size of the portions available. Holographic representations enable progressive refinement in image communication or retrieval tasks, with no restrictions on the order in which the data fragments (sections of the representation) are accessed or become available.

In this paper we discuss a new approach to invariant signatures for recognizing curves under viewing distortions and partial occlusion. The approach is intended to overcome the ill-posed problem of finding derivatives, on which local invariants usually depend. The basic idea is to use invariant finite differences, with a scale parameter that determines the size of the differencing interval. The scale parameter is allowed to vary so that a "scale space"-like invariant representation of the curve, with larger difference intervals corresponding to larger coarser scales, can be obtained. In this new representation, each traditional local invariant is replaced by a scale-dependent range of invariants. Thus, instead of invariant signature curves we obtain invariant signature surfaces in a 3D invariant "scale space".

A local smoothing operator applied in the reverse direction is used to obtain planar shape enhancement and exaggeration. Inversion of a smoothing operator is an inherently unstable operation. Therefore, a stable numerical scheme simulating the inverse smoothing effect is introduced. Enhancement is obtained for short time spans of evolution. Carrying the evolution further yields shape exaggeration or caricaturization effect. Introducing attraction forces between the evolving shape and the initial one, yields an enhancement process that converges to a steady state. These forces depend on the distance of the evolving curve from the original one and on local properties. Results of applying the unrestrained and restrained evolution on planar shapes, based on a stabilized inverse geometric heat equation, are presented showing enhancement and caricaturization effects.

Evolutions of closed planar polygons are studied in this work. In the first part of the paper, the general theory of linear polygon evolutions is presented, and two specific problems are analyzed. The first one is a polygonal analog of a novel affine-invariant differential curve evolution, for which the convergence of planar curves to ellipses was proved. In the polygon case, convergence to polygonal approximation of ellipses, polygo nal ellipses, is proven. The second one is related to cyclic pursuit problems, and convergence, either to polygonal ellipses or to polygonal circles, is proven. In the second part, two possible polygonal analogues of the well-known Euclidean curve shortening flow are presented. The models follow from geometric considerations. Experimental results show that an arbitrary initial polygon converges to either regular or irregular polygonal approximations of circles when evolving according to the proposed Euclidean flows.

We present a purely geometrical proof that under the weak perspective model, the 3D pose of a 3-point configuration is determined uniquely up to a reflection by its 2D projection.

We present a new algorithm for determining minimal length paths between two regions on a three dimensional surface. The numerical implementation is based on finding equal geodesic distance contours from a given area. These contours are calculated as zero sets of a bivariate function designed to evolve so as to track the equal distance curves on the given surface. The algorithm produces all paths of minimal length between the source and destination areas on the surface given as height values on a rectangular grid.>

Recently researchers in the field of image processing and computer vision started to pay attention to new ways of analyzing and representing two-dimensional, stationary or moving images, via planar curve evolutions. In fact, any image can be viewed as a set of level curves "evolving" with the height parameter. Even such a simple description is quite useful in a variety of situations. We review some of these curve evolution based algorithms.>

A new approach for the reconstruction of a smooth three dimensional object from its two dimensional gray level image is presented. An algorithm based on topological properties of simple smooth surfaces is provided to solve the problem of global reconstruction. Classifying singular points in the shading image as maxima minima and two kinds of saddle points, serves as the key to the solution of the problem. This classification is performed globally with no assumptions on the local behavior of characteristics near singular points. The global reconstruction procedure, being deterministic and using topological properties of the surface performs better than other approaches proposed so far, based on classification of singular points according to the local behavior of characteristics in their neighborhood. The proposed algorithm is simple, easy to implement and works remarkably fast on a parallel machine.

This paper presents a new algorithm for planning the time-optimal motion of a robot traveling with limited velocity from a given location to a given destination on a surface in the presence of moving obstacles. Additional constraints such as space variant terrain traversability and fuel economy can be accommodated. A multilayer distance map is defined and applied in computing optimal trajectories. The multilayer distance map incorporates constraints imposed by the moving obstacles, surface topography and terrain traversability. It is generated by an efficient numerical curve propagation technique.

The process of learning the shape of an unknown convex planar object through an adaptive process of simple measurements called line probings, which reveal tangent lines to the object, is considered. A systematic probing strategy is suggested and an upper bound on the number of probings it requires for achieving an approximation with a pre-specified precision to the unknown object is derived. A lower bound on the number of probings required by any strategy for achieving such an approximation is also derived, showing that the gap between the number of probings required by the authors' strategy and the number of probings required by the optimal strategy is a logarithmic factor in the worst case. The proposed approach overcomes deficiencies of the classical geometric probing approach which is based on the polygonality assumption, and thus is not applicable for real robotic tasks.>

A simple online algorithm for partitioning of a digital curve into digital straight-line segments of maximal length is given. The algorithm requires O(N) time and O(1) space and is therefore optimal. Efficient representations of the digital segments are obtained as byproducts. The algorithm also solves a number-theoretical problem concerning nonhomogeneous spectra of numbers.>

The authors describe an algorithm for navigating a polygonal robot, capable of translational motion, in an unknown environment. The environment contains stationary polygonal obstacles and is bounded by polygonal walls, all of which are initially unknown to the robot. The environment is learned during the navigation process by use of a laser range-finding device, and new knowledge is integrated with previously acquired information. A partial map of the environment, containing parts of the obstacles that were seen by the robot and the free space between them, is obtained. The obstacles in the map are transformed into a new set of expanded polygonal obstacles, allowing the robot to be treated as a point, and the navigation problem is reduced to point navigation among unknown polygonal obstacles. A navigation graph is built from the transformed obstacles and used to search for a piecewise linear path to the destination. The algorithm is proved to converge to the desired destination in a finite number of steps provided a path to the destination exists.>

A planar shape distorted by a projective viewing transformation can be recognized under partial occlusion if an invariant description of its boundary is available. Research in this area has provided a theory for invariant boundary descriptions based on an interplay of differential, local, and global invariants. Differential invariants require high-order derivatives. The use of global invariants and point matches on the distorting transformations enables one to reduce the order. Trade-offs between the highest order derivatives required and the quantity of additional information constraining the distorting viewing transformations are made explicit.>

It is customary to represent an analog image in digital form by dividing its support to pixels, and within each pixel to represent the brightness by a quantized scalar i.e., to approximate the 2-D image function by a horizontal planar patch. This paper studies a representation scheme in which the image function is represented within each pixel by an inclined planar patch. If the image function is to be represented by b bits per pixel, a bit allocation trade-off arises, and the optimal allocation of bits to the representation of the average value and of the two slope coefficients within each pixel needs to be determined. Analysis shows that allocating all the bits to represent the average brightness is not always optimal, and bits should be allocated to the representation of the slope coefficients. Similar results were obtained for the 1-D case.>

The problem of fitting a straight line to a planar set of points is reconsidered. A parameter space computational approach capable of fitting one or more lines to a set of points is presented. The suggested algorithm handles errors in both coordinates of the data points, even when the error variances vary between coordinates and among points and can be readily made robust to outliers. The algorithm is quite general and allows line fitting according to several useful optimality criteria to be performed within a single computational framework. It is observed that certain extensions of the Hough transform can be turned to be equivalent to well-known M estimators, thus allowing computationally efficient approximate M estimation.>

The problem of recovering the shape of planar objects from line or finger probings arises in robotics. This problem is addressed under the assumption that composite probings are made. One composite probing comprises several (k) line or finger probings done simultaneously. An investigation is conducted of planar polygon reconstruction from sequences of composite k-probings. For every value of k, a lower bound on the number of k-probings required for reconstruction under any strategy is obtained. Specific strategies which are provably almost optimal are provided.>

The problem of determining the optimal straight path between a planar set of points is considered. Each point contributes to the cost of a path a value that depends on the distance between the path and the point. The cost function, quantifying this dependence, can be arbitrary and may be different for different points. An algorithm to solve this problem using an extension of the Hough transform is described. The range of applications includes straight-line fitting to a set of points in the presence of outliers, navigation, and path planning. The proposed extended Hough transform can be tuned to equivalent to well-known robust least-squares techniques, and allows efficient, approximate M-estimation.>

A variation of the Hough Transform that is aimed at detecting digital lines has been recently suggested. Other Hough algorithms are intended to detect straight lines in the analog pre-image. These approaches arc analyzed and compared in terms of the relation between the achievable resolution and the required number of accumulators, using a definition of resolution that is based on the Geometric Probability measure of straight lines. It is shown that the "analog" approach is greatly superior in high resolution applications, where a "digital " Hough Transform would generally require an infeasibly large number of accumulators. The Hough Transform [2,4] is a well known technique for recognizing predefined features in edge maps. In this paper, the Hough Transform for detecting straight lines is considered. Most Hough algorithms consist of an incrementation stage, in which each edge point "votes " for the parameter-pairs of all possible straight lines on which it can lie, and an exhaustive search for peaks. These correspond to large collinear sets of edge-points. Originally, the slope-intercept (m,b) parametrization of straight lines had been employed in the Hough Transform. It has the advantage that an edge point corresponds to a straight line in the parameter space, thus voting is simple. Its drawback is that the parameter space is unbounded, implying some theoretical and practical difficulties. With normal (p,0) parametrization of straight lines, as suggested by [2], an edge point corresponds to a sinusoid in the parameter space, thus voting is somewhat more complex. The normal parametrization has the advantage that a bounded image leads to a bounded parameter space. Other straight-line parametrizations have also been suggested, see [4,11,17]. In most implementations of the Hough algorithm the parameter space is represented by a rectangular accumulator array, such that each accumulator corresponds to a rectangular, constant size domain in the parameter space. The quantization of the parameter space greatly influences the resolution and detection capabilities of the algorithm, as well as the computational and storage requirements; see

A basic self-similarity of chain codes of digitized straight lines is discussed. This property readily follows from the observation that a discrete straight line remains a discrete straight line when redigitized on any regular subgrid of the original digitization grid. It is shown that many previously discovered and new properties and characterizations of discretized lines follow from this observation.>

An examination of the effects of spatial sampling and image noise on the precision with which the centroids of different geometric shapes can be determined is presented. The concentric ring fiducial-a bull's-eye pattern-is identified as having desirable qualities of high location precision and rotational invariance. The performance of the concentric fiducial, as a function of diameter, number of rings. and ring spacing, has been tested, and these results are shown.>

The number of digital straight lines on an N*N grid is shown. A digital straight line is equivalent to a linear dichotomy of points on a square grid. The result is obtained by determining a way of counting the number of linearly separable dichotomies of points on the plane that are not necessarily in general position. The analysis is easily modified to provide a simple solution to a similar problem considered by C. Berenstein and D. Lavine (1988) on the number of digital straight lines from a fixed starting point.>

Measurement of perimeters of planar shapes from their digitized images is an important task of computer vision systems. A general methodology for the design of simple and accurate parameter estimation algorithms is described. It is based on minimizing the maximum estimation error for digitized straight edges over all orientations. Two perimeter estimators are derived and their performance is tested and digitized circles using computer simulations. The experimental results may be used to predict the performance of the algorithm on shapes with arbitrary contours of continuous curvature. The simulations also show that fast and accurate perimeter estimation is possible, even for objects that are small relative to pixel size.>

The application of gray-scale digitizers to the digitization of binary images of straight-edged silhouettes is considered. A measure of digitization-induced ambiguity is introduced. It is shown that if the gray levels are not quantized and the sampling resolution is sufficiently high, error-free reconstruction of the original binary image from the digitized image is possible. When the total bit-count for the representation of the digitized image is limited, i.e., sampling resolution and quantization accuracy are both finite, error-free reconstruction is usually impossible. The authors' suggested bit allocation policy is then to increase the quantization accuracy as much as possible, once sufficient sampling resolution has been reached.>

The number of different digital straight lines on an N*N square pixel array is studied. The problem is equivalent to finding the number of linear dichotomies of a planar set of N/sup 2/ points of an N*N grid. For any planar set of points, adjacent pairs are defined to be pairs of points from the set such that no other point from the set lie on the line segment between them. A one-to-one correspondence between linear dichotomies and adjacent pairs is proved. Then, the adjacent pairs of points of an N*N grid are counted, and the number of linear dichotomies, as well as the number of digital straight lines, follows. An asymptotic evaluation is proved and an efficient algorithm for finding L(N) for any particular N is given.>

We present a time-domain method for estimating the number and delay times for overlapping signals with a priori known shape, from noisy observations received by a sensor. The method is based on a recently developed eigenstructure technique for multiple direction finding with sensor arrays and exploits the structure of the received signal covariance matrix. The method presented also solves more general problems of signal detection and resolution.

A set of n pattern vectors are given in d-space and classified arbitrarily into two sets. The sets of patterns are said to be linearly separable if there exists a hyperplane that separates them. We ask whether translation of one of these sets in an arbitrary direction helps separability. Sometimes yes and sometimes no, but yes on the average. The average is taken over all classifications of the patterns into two sets. In fact, we prove that the probability of separability increases as the translation increases. Thus, we conclude that if points are drawn equiprobably from densities fo(x) and f1(x) = fo(x + tw) then the probability of linear separability is minimum at t = 0 and increases with t for t > 0.

Redheffer scattering theory is reviewed in a generalized setting as a method to derive recursive solutions of linear two-point boundary value problems (TPBVP) over arbitrarily varying intervals. The results can be used to derive a complete solution for the problem of limited-memory (or sliding-window) estimation, when a usual state-space model for the signal is available. Recursive limited-memory filters are derived for both continuous and discrete time signals.

It is shown that, asymptotically, as the dimensionality of the space increases, the usual sample editing becomes independent. This makes an accurate calculation of performance in a high-dimensional space straightforward. Thus, with high dimensionality, the grouping given by J. Koplowitz and T.A. Brown (1981) is not necessary for determining the risk, and, similarly, the results presented by D.L. Wilson (1972) become very close to exact.

Neural encoders translate information on the time-varying intensity of stimuli into sequences of membrane depolarization spikes. Their output can be considered the realization of a stochastic point process, the overall encoder behaviour being characterized through ensemble-averaged responses to identical stimuli and environmental conditions. A new mathematical model for the coding process is presented and analyzed. The model is an integrate and fire-at-threshold scheme, the stochastic features of its response resulting from random fluctuations in the firing threshold. As a consequence of feedback self-inhibition and threshold control, which is assumed to account for adaptive neutral responses, the model output is a self-exciting point process. An approximate description of the averaged encoder response is obtained by considering an ensemble of identical coding units as a whole, instead of concentrating on output sample-path evolution. This approach overcomes the difficulty inherent in analysing the global behaviour of self-exciting point processes. A conceptual decoding scheme implementing a coding unit in a feedback configuration is also introduced and discussed.

Expressions for the moments of invariant measures corresponding to a class of discrete-time Markov processes are given. The processes under consideration assume values inR^{+}and have stationary transition kernels of exponential type, generalizing the Rayleigh and gamma distributions. The moments of their stationary distributions, obtained by extending a method due to Wold, are given in the form of convergent infinite products of gamma functions.