We present Spectron, a novel approach to adapting pre-trained large language models (LLMs) to perform spoken question answering (QA) and speech continuation. By endowing the LLM with a pre-trained speech encoder, our model becomes able to take speech inputs and generate speech outputs. The entire system is trained end-to-end and operates directly on spectrograms, simplifying our architecture. Key to our approach is a training objective that jointly supervises speech recognition, text continuation, and speech synthesis using only paired speech-text pairs, enabling a `cross-modal' chain-of-thought within a single decoding pass. Our method surpasses existing spoken language models in speaker preservation and semantic coherence. Furthermore, the proposed model improves upon direct initialization in retaining the knowledge of the original LLM as demonstrated through spoken QA datasets. We release our audio samples and spoken QA dataset via our website.

The pursuit of high perceptual quality in image restoration has driven the development of revolutionary generative models, capable of producing results often visually indistinguishable from real data. However, as their perceptual quality continues to improve, these models also exhibit a growing tendency to generate hallucinations – realistic-looking details that do not exist in the ground truth images. Hallucinations in these models create uncertainty about their reliability, raising major concerns about their practical application. This paper investigates this phenomenon through the lens of information theory, revealing a fundamental tradeoff between uncertainty and perception. We rigorously analyze the relationship between these two factors, proving that the global minimal uncertainty in generative models grows in tandem with perception. In particular, we define the inherent uncertainty of the restoration problem and show that attaining perfect perceptual quality entails at least twice this uncertainty. Additionally, we establish a relation between distortion, uncertainty and perception, through which we prove the aforementioned uncertainly-perception tradeoff induces the well-known perception-distortion tradeoff. We demonstrate our theoretical findings through experiments with super-resolution and inpainting algorithms. This work uncovers fundamental limitations of generative models in achieving both high perceptual quality and reliable predictions for image restoration. Thus, we aim to raise awareness among practitioners about this inherent tradeoff, empowering them to make informed decisions and potentially prioritize safety over perceptual performance.

Temporal action segmentation relates to high-level video understanding, commonly formulated as frame-wise classification of untrimmed videos into predefined actions. Fully-supervised deep-learning approaches require dense video annotations which are time and money consuming. Furthermore, the temporal boundaries between consecutive actions typically are not well-defined, leading to inherent ambiguity and interrater disagreement. A promising approach to remedy these limitations is timestamp supervision, requiring only one labeled frame per action instance in a training video. In this work, we reformulate the task of temporal segmentation as a graph segmentation problem with weakly-labeled vertices. We introduce an efficient segmentation method based on random walks on graphs, obtained by solving a sparse system of linear equations. Furthermore, the proposed technique can be employed in any one or combination of the following forms: (1) as a standalone solution for generating dense pseudo-labels from timestamps; (2) as a training loss; (3) as a smoothing mechanism given intermediate predictions. Extensive experiments with three datasets (50Salads, Breakfast, GTEA) show that our method competes with state-of-the-art, and allows the identification of regions of uncertainty around action boundaries.

Uncertainty quantification for inverse problems in imaging has drawn much attention lately. Existing approaches towards this task define uncertainty regions based on probable values per pixel, while ignoring spatial correlations within the image, resulting in an exaggerated volume of uncertainty. In this paper, we propose PUQ (Principal Uncertainty Quantification) - a novel definition and corresponding analysis of uncertainty regions that takes into account spatial relationships within the image, thus providing reduced volume regions. Using recent advancements in generative models, we derive uncertainty intervals around principal components of the empirical posterior distribution, forming an ambiguity region that guarantees the inclusion of true unseen values with a user-defined confidence probability. To improve computational efficiency and interpretability, we also guarantee the recovery of true unseen values using only a few principal directions, resulting in more informative uncertainty regions. Our approach is verified through experiments on image colorization, super-resolution, and inpainting; its effectiveness is shown through comparison to baseline methods, demonstrating significantly tighter uncertainty regions.

Solid tumors are characterized by complex interactions between the tumor, the immune system and the microenvironment. These interactions and intra-tumor variations have both diagnostic and prognostic significance and implications. However, quantifying the underlying processes in patient samples requires expensive and complicated molecular experiments. In contrast, H&E staining is typically performed as part of the routine standard process, and is very cheap. Here we present HIPI (H&E Image Interpretation and Protein Expression Inference) for predicting cell marker expression from tumor H&E images. We process paired H&E and CyCIF images taken from serial sections of colorectal cancers to train our model. We show that our model accurately predicts the spatial distribution of several important cell markers, on both held-out tumor regions as well as new tumor samples taken from different patients. Moreover, using only the tissue image morphology, HIPI is able to colocalize the interactions between different cell types, further demonstrating its potential clinical significance.

Detection and segmentation of surgical instruments is an important problem for laparoscopic surgery. Accurate pixel-wise instrument segmentation is a useful intermediate task for the development of computer-assisted surgery systems, such as pose estimation, surgical phase estimation, enhanced image fusion, video retrieval and others. In this paper we describe a deep learning-based approach to instrument segmentation, which addresses the binary segmentation problem in which every pixel in an image is labeled as instrument or background. The key novelty of our approach relates to the use of training data which is inexpensive and fast to acquire. First, our approach relies on weak annotations provided as bounding boxes of the instruments, which are much faster and cheaper to obtain than a dense pixel-level annotations. Second, to further improve the system’s accuracy we propose a novel approach to generate synthetic training images. Our approach achieves state-of-the-art results, outperforming previously proposed methods for automatic instrument segmentation, based only on weak annotations.

In recent years there has been increasing interest in leveraging denoisers for solving general inverse problems. Two leading frameworks are regularization-by-denoising (RED) and plug-and-play priors (PnP) which incorporate explicit likelihood functions with priors induced by denoising algorithms. RED and PnP have shown state-of-the-art performance in diverse imaging tasks when powerful denoisersare used, such as convolutional neural networks (CNNs). However, the study of their convergence remains an active line of research. Recent works derive the convergence of RED and PnP methods by treating CNN denoisers as approximations for maximum a posteriori (MAP) or minimum mean square error (MMSE) estimators. Yet, state-of-the-art denoisers cannot be interpreted as either MAPor MMSE estimators, since they typically do not exhibit symmetric Jacobians. Furthermore, obtaining stable inverse algorithms often requires controlling the Lipschitz constant of CNN denoisers during training. Precisely enforcing this constraint is impractical, hence, convergence cannot be completely guaranteed. In this work, we introduce image denoisers derived as the gradients of smooth scalar-valued deep neural networks, acting as potentials. This ensures two things: (1) the proposed denoisers display symmetric Jacobians, allowing for MAP and MMSE estimators interpretation; (2) the denoisers may be integrated into RED and PnP schemes with backtracking step size, removing the need for enforcing their Lipschitz constant. To show the latter, we develop a simple inversion method that utilizes the proposed denoisers. We theoretically establish its convergence to stationary points of an underlying objective function consisting of the learned potentials. We numerically validate our method through various imaging experiments, showing improved results compared to standard RED and PnP methods, and with additional provable stability.

Colonoscopy is tool of choice for preventing Colorectal Cancer, by detecting and removing polyps before they become cancerous. However, colonoscopy is hampered by the fact that endoscopists routinely miss 22-28% of polyps. While some of these missed polyps appear in the endoscopist's field of view, others are missed simply because of substandard coverage of the procedure, i.e. not all of the colon is seen. This paper attempts to rectify the problem of substandard coverage in colonoscopy through the introduction of the C2D2 (Colonoscopy Coverage Deficiency via Depth) algorithm which detects deficient coverage, and can thereby alert the endoscopist to revisit a given area. More specifically, C2D2 consists of two separate algorithms: the first performs depth estimation of the colon given an ordinary RGB video stream; while the second computes coverage given these depth estimates. Rather than compute coverage for the entire colon, our algorithm computes coverage locally, on a segment-by-segment basis; C2D2 can then indicate in real-time whether a particular area of the colon has suffered from deficient coverage, and if so the endoscopist can return to that area. Our coverage algorithm is the first such algorithm to be evaluated in a large-scale way; while our depth estimation technique is the first calibration-free unsupervised method applied to colonoscopies. The C2D2 algorithm achieves state of the art results in the detection of deficient coverage. On synthetic sequences with ground truth, it is 2.4 times more accurate than human experts; while on real sequences, C2D2 achieves a 93.0% agreement with experts.

This paper presents a vision-based indoor positioning system of a small robotic vehicle utilizing knowledge of the building floorplan. Using images taken by a monocular camera rigidly mounted onto the deck of the vehicle, the localization system obtains initial geometry of the environment and camera motion by running Structure from Motion. The localization system resolves the scale ambiguity present in the data by associating planar structures in the 3D point cloud with walls of the building. In order to extract the planes, we developed a Scale Invariant Planar RANSAC (SIPR) algorithm which handles situations of scale ambiguity in the point cloud data. Our Wall Plane Fusion algorithm forms correspondences between walls and computed planes, and the best such correspondence is used as an external constraint to the Bundle Adjustment algorithm which is run on the Structure from Motion data. A necessary condition for providing a global positioning solution is that one wall be in view. This paper provides results in both simulated and real-world scenarios.

Sparse and redundant representations, where signals are modeled as a combination of a few atoms from an overcomplete dictionary, is increasingly used in many image processing applications, such as denoising, super resolution, and classification. One common problem is learning a "good" dictionary for different tasks. In the classification task the aim is to learn a dictionary that also takes training labels into account, and indeed there exist several approaches to this problem. One well-known technique is D-KSVD, which jointly learns a dictionary and a linear classifier using the K-SVD algorithm. LC-KSVD is a recent variation intended to further improve on this idea by adding an explicit label consistency term to the optimization problem, so that different classes are represented by different dictionary atoms. In this work we prove that, under identical initialization conditions, LC-KSVD with uniform atom allocation is in fact a reformulation of D-KSVD: given the regularization parameters of LC-KSVD, we give a closed-form expression for the equivalent D-KSVD regularization parameter, assuming the LC-KSVD's initialization scheme is used. We confirm this by reproducing several of the original LC-KSVD experiments.

Bundle Adjustment is the current state of the art method for solving the simultaneous localization and mapping problem. This problem is important for the localization of robots, and most acute for flying robots that cannot rely on ground odometry. The solution requires additional information to resolve scale, and most implementations either assume that relatively accurate pose information exists, or utilize GPS and IMU sensors. This paper presents an alternative approach that incorporates Digital Terrain Model constraints into the Bundle Adjustment algorithm, enabling the correct resolution of scale even in the absence of additional information. It is shown, in multiple test scenarios, that this algorithm provides estimations that do not diverge with time and that exceed, in accuracy, the resolution of the underlying sampled terrain.

A methodology for integrating multiple cues for tracking was proposed in several papers. These papers claim that, unlike other methodologies, conditional independence of the cues is not assumed. This brief communication 1) refutes this claim and 2) points out other major problems in the methodology.

We propose two solutions for both nearest neighbors and range search problems. For the nearest neighbors problem, we propose a c-approximate solution for the restricted version of the decision problem with bounded radius which is then reduced to the nearest neighbors by a known reduction. For range searching we propose a scheme that learns the parameters in a learning stage adopting them to the case of a set of points with low intrinsic dimension that are embedded in high dimensional space (common scenario for image point descriptors). We compare our algorithms to the best known methods for these problems, i.e. LSH, ANN and FLANN. We show analytically and experimentally that we can do better for moderate approximation factor. Our algorithms are trivial to parallelize. In the experiments conducted, running on couple of million images, our algorithms show meaningful speed-ups when compared with the above mentioned methods.

We revisit the problem of specific object recognition using color distributions. In some applications--such as specific person identification--it is highly likely that the color distributions will be multimodal and hence contain a special structure. Although the color distribution changes under different lighting conditions, some aspects of its structure turn out to be invariants. We refer to this structure as an intradistribution structure, and show that it is invariant under a wide range of imaging conditions while being discriminative enough to be practical. Our signature uses shape context descriptors to represent the intradistribution structure. Assuming the widely used diagonal model, we validate that our signature is invariant under certain illumination changes. Experimentally, we use color information as the only cue to obtain good recognition performance on publicly available databases covering both indoor and outdoor conditions. Combining our approach with the complementary covariance descriptor, we demonstrate results exceeding the state-of-the-art performance on the challenging VIPeR and CAVIAR4REID databases.

This paper considers the problem of recognizing activities as they occur in surveillance video. Activities are high-level nonatomic semantic concepts which may have complex temporal structure. Activities are not easily identifiable using image features, but rather by the recognition of their composing events. Unfortunately, these composing events may only be observed up to a particular certainty. This paper describes particle filter Petri Net (PFPN), an activity recognition process that combines uncertain event observations to determine the likelihood that a particular activity is taking place in a video sequence. Our paper is based on previous study in which activities are specified as Petri Nets. The stochastic PFPN framework proposed in this paper improves over existing deterministic approaches to activity recognition by enabling the certainty reasoning required for coping with inherent ambiguity in both low-level video processing and activity definition. Furthermore, the PFPN approach reduces the dependence on a duration model and enables the creation of holistic activity models. Often when activity recognition frameworks are proposed they are strongly paired with a particular methodology for low-level video processing and event recognition. Each proposed approach is then applied to a nonstandard dataset. In our experiments, we provide an empirical comparison of our approach with leading activity recognition approaches across several datasets, using a constant event recognition as input. Our results illustrate the tradeoff between deterministic and stochastic activity recognition approaches. Furthermore, our experiments suggest that the holistic PFPN approach is more robust for activity recognition in the surveillance video domain than competing approaches.

It is quite common that multiple human observers attend to a single static interest point. This is known as a mutual awareness event (MAWE). A preferred way to monitor these situations is with a camera that captures the human observers while using existing face detection and head pose estimation algorithms. The current work studies the underlying geometric constraints of MAWEs and reformulates them in terms of image measurements. The constraints are then used in a method that 1) detects whether such an interest point does exist, 2) determines where it is located, 3) identifies who was attending to it, and 4) reports where and when each observer was while attending to it. The method is also applied on another interesting event when a single moving human observer fixates on a single static interest point. The method can deal with the general case of an uncalibrated camera in a general environment. This is in contrast to other work on similar problems that inherently assumes a known environment or a calibrated camera. The method was tested on about 75 images from various scenes and robustly detects MAWEs and estimates their related attributes. Most of the images were found by searching the Internet.

This paper addresses the problem of distributed cooperative navigation. A new graph-based method is developed for on-demand calculation of the required correlation terms, considering a general multi-robot measurement model. These correlation terms are necessary for the consistent EKF-based data fusion when several statistically-dependent sources of information are used. The measurement model relates between the navigation information transmitted by any number of robots and the actual readings taken by the available onboard sensors. The transmitted information is not necessarily of the current time instant, but may actually belong to some time instant from the past. Experiment results and a theoretical example of the developed method are presented considering a three-view measurement, formulated upon receiving three images of the same scene, captured by different robots at different a priori unknown time instances.

A novel vision-based navigation algorithm is proposed. The gray levels of two images, together with a Digital Terrain Map (DTM), are directly utilized to define constraints on the navigation parameters. The feasibility of the algorithm is examined both under a simulated environment and using real flight data.

In this paper, we propose the surveillance event recognition framework using Petri Nets (SERF-PN) for recognition of event occurrences in video. The Petri Net (PN) formalism allows a robust way to express semantic knowledge about the event domain as well as efficient algorithms for recognizing events as they occur in a particular video sequence. The major novelties of this paper are extensions to both the modeling and the recognition capacities of the Object PN paradigm. The first contribution of this paper is the extension of the PN representational capacities by introducing stochastic timed transitions to allow modeling of events which have some variance in duration. These stochastic timed transitions sample the duration of the condition from a parametrized distribution. The parameters of this distribution can be specified manually or learned from available video data. A second representational novelty is the use of a single PN to represent the entire event domain, as opposed to previous approaches which have utilized several networks, one for each event of interest. A third contribution of this paper is the capacity to probabilistically predict future events by constructing a discrete time Markov chain model of transitions between states. The experiments section of the paper thoroughly evaluates the application of the SERF-PN framework in the event domains of surveillance and traffic monitoring and provides comparison to other approaches using the CAVIAR dataset , a standard dataset for video analysis applications.

This paper presents a framework for hierarchical 3D articulated human body-part tracking and action classification. We introduce a Hierarchical Annealing Particle Filter (H-APF) algorithm, which applies nonlinear dimensionality reduction of the high di-mensional data space to the low dimensional latent spaces combined with the dynamic motion model and the Hierarchical Human Body Model. The improved annealing ap-proach is used for the propagation between different body models and sequential frames. The tracking algorithm generates trajectories in the latent spaces, which provide low di-mensional representations of body poses, observed during the motion. These trajectories are used to classify human motions. The tracking and classification algorithms were checked on HumanEvaI, HumanEvaII, and other datasets, involving more complicated motion types and transitions and proved to be effective and robust. The comparison to other methods and the error calculations are provided. 1

This paper presents an automatic system for morphological screening of the bladder cells. This system is intended to increase efficiency of the subsequent fluorescence in situ hybridization examination by limiting the number of suspicious cells. The system works in two major phases. The first phase is slide scanning. The second stage includes cells detection and morphological analysis. Both stages refine their results using supervised classification algorithm. The developed method was tested on nine microscopical slides, containing more than 12000 manually labeled cells. The results provided by the system were compared to the ground truth labeled by a human expert.

In this paper we propose a new method that addresses the problem of tracking the bitmap (silhouette) of an object in a video under very general conditions. We assume a general target, possibly non rigid, with no prior information except initialization. The target, as well as the background, may change its appearance over time and the camera may move arbitrarily. The proposed algorithm fuses different visual cues by means of a conditional random field. The target's bitmap is estimated every frame by incorporating temporal color similarity, spatial color continuity and spatial motion continuity into an energy function that is minimized via min-cut. The spatial motion continuity is incorporated in the energy function in multiple image resolutions by a novel multi-scale energy term. Experiments demonstrate the robustness of our method and its advantage over other algorithms.

We consider curve evolution based on comparing distributions of features, and its applications for scene segmentation. In the first part, we promote using cross-bin metrics such as the Earth Mover's Distance (EMD), instead of standard bin-wise metrics as the Bhattacharyya or Kullback-Leibler metrics. To derive flow equations for minimizing functionals involving the EMD, we employ a tractable expression for calculating EMD between one-dimensional distributions. We then apply the derived flows to various examples of single image segmentation, and to scene analysis using video data. In the latter, we consider the problem of segmenting a scene to spatial regions in which different activities occur. We use a nonparametric local representation of the regions by considering multiple one-dimensional histograms of normalized spatiotemporal derivatives. We then obtain semisupervised segmentation of regions using the flows derived in the first part of the paper. Our results are demonstrated on challenging surveillance scenes, and compare favorably with state-of-the-art results using parametric representations by dynamic systems or mixtures of them.

Kernel-based trackers aggregate image features within the support of a kernel (a mask) regardless of their spatial structure. These trackers spatially fit the kernel (usually in location and in scale) such that a function of the aggregate is optimized. We propose a kernel-based visual tracker that exploits the constancy of color and the presence of color edges along the target boundary. The tracker estimates the best affinity of a spatially aligned pair of kernels, one of which is color-related and the other of which is object boundary-related. In a sense, this work extends previous kernel-based trackers by incorporating the object boundary cue into the tracking process and by allowing the kernels to be affinely transformed instead of only translated and isotropically scaled. These two extensions make for more precise target localization. A more accurately localized target also facilitates safer updating of its reference color model, further enhancing the tracker's robustness. The improved tracking is demonstrated for several challenging image sequences.

Resolution of different types of loops in handwritten script presents a difficult task and is an important step in many classic word recognition systems, writer modeling, and signature verification. When processing a handwritten script, a great deal of ambiguity occurs when strokes overlap, merge, or intersect. This paper presents a novel loop modeling and contour-based handwriting analysis that improves loop investigation. We show excellent results on various loop resolution scenarios, including axial loop understanding and collapsed loop recovery. We demonstrate our approach for loop investigation on several realistic data sets of static binary images and compare with the ground truth of the genuine online signal.

In this paper, we address the problem of fully automated decomposition of hyperspectral images for transmission light microscopy. The hyperspectral images are decomposed into spectrally homogeneous compounds. The resulting compounds are described by their spectral characteristics and optical density. We present the multiplicative physical model of image formation in transmission light microscopy, justify reduction of a hyperspectral image decomposition problem to a blind source separation problem, and provide method for hyperspectral restoration of separated compounds. In our approach, dimensionality reduction using principal component analysis (PCA) is followed by a blind source separation (BSS) algorithm. The BSS method is based on sparsifying transformation of observed images and relative Newton optimization procedure. The presented method was verified on hyperspectral images of biological tissues. The method was compared to the existing approach based on nonnegative matrix factorization. Experiments showed that the presented method is faster and better separates the biological compounds from imaging artifacts. The results obtained in this work may be used for improving automatic microscope hardware calibration and computer-aided diagnostics.

Understanding video events, i.e., the translation of low-level content in video sequences into high-level semantic concepts, is a research topic that has received much interest in recent years. Important applications of this paper include smart surveillance systems, semantic video database indexing, and interactive systems. This technology can be applied to several video domains including airport terminal, parking lot, traffic, subway stations, aerial surveillance, and sign language data. In this paper, we identify the two main components of the event understanding process: abstraction and event modeling. Abstraction is the process of molding the data into informative units to be used as input to the event model. Due to space restrictions, we will limit the discussion on the topic of abstraction. See the study byLaveeetal.(Understanding video events: A survey of methods for automatic interpretation of semantic occurrences in video, Technion-Israel Inst. Technol., Haifa, Israel, Tech. Rep. CIS-2009-06, 2009) for a more complete discussion. Event modeling is devoted to describing events of interest formally and enabling recognition of these events as they occur in the video sequence. Event modeling can be further decomposed in the categories of pattern-recognition methods, state event models, and semantic event models. In this survey, we discuss this proposed taxonomy of the literature, offer a unifying terminology, and discuss popular event modeling formalisms (e.g., hidden Markov model) and their use in video event understanding using extensive examples from the literature. Finally, we consider the application domain of video event understanding in light of the proposed taxonomy, and propose future directions for research in this field.

We present a novel algorithm for detection of certain types of unusual events. The algorithm is based on multiple local monitors which collect low-level statistics. Each local monitor produces an alert if its current measurement is unusual, and these alerts are integrated to a final decision regarding the existence of an unusual event. Our algorithm satisfies a set of requirements that are critical for successful deployment of any large-scale surveillance system. In particular it requires a minimal setup (taking only a few minutes) and is fully automatic afterwards. Since it is not based on objects' tracks, it is robust and works well in crowded scenes where tracking-based algorithms are likely to fail. The algorithm is effective as soon as sufficient low-level observations representing the routine activity have been collected, which usually happens after a few minutes. Our algorithm runs in realtime. It was tested on a variety of real-life crowded scenes. A ground-truth was extracted for these scenes, with respect to which detection and false-alarm rates are reported.

This paper addresses the problem of visual tracking under very general conditions: a possibly non-rigid target whose appearance may drastically change over time; general camera motion; a 3D scene; and no a priori information except initialization. This is in contrast to the vast majority of trackers which rely on some limited model in which, for example, the target's appearance is known a priori or restricted, the scene is planar, or a pan tilt zoom camera is used. Their goal is to achieve speed and robustness, but their limited context may cause them to fail in the more general case. The proposed tracker works by approximating, in each frame, a PDF (probability distribution function) of the target's bitmap and then estimating the maximum a posteriori bitmap. The PDF is marginalized over all possible motions per pixel, thus avoiding the stage in which optical flow is determined. This is an advantage over other general-context trackers that do not use the motion cue at all or rely on the error-prone calculation of optical flow. Using a Gibbs distribution with respect to the first-order neighborhood system yields a bitmap PDF whose maximization may be transformed into that of a quadratic pseudo-Boolean function, the maximum of which is approximated via a reduction to a maximum-flow problem. Many experiments were conducted to demonstrate that the tracker is able to track under the aforementioned general context.

Kernel-based trackers aggregate image features within the support of a kernel (a mask) regardless of their spatial structure. These trackers spatially fit the kernel (usually in location and in scale) such that a function of the aggregate is optimized. We propose a kernel-based visual tracker that exploits the constancy of color and the presence of color edges along the target boundary. The tracker estimates the best affinity of a spatially aligned pair of kernels, one of which is color-related and the other of which is object boundary-related. In a sense, this work extends previous kernel-based trackers by incorporating the object boundary cue into the tracking process and by allowing the kernels to be affinely transformed instead of only translated and isotropically scaled. These two extensions make for more precise target localization. Moreover, a more accurately localized target facilitates safer updating of its reference color model, further enhancing the tracker's robustness. The improved tracking is demonstrated for several challenging image sequences.

Many vision-based navigation systems are restricted to the use of only a limited number of landmarks when computing the camera pose. This limitation is due to the overhead of detecting and tracking these landmarks along the image sequence. A new algorithm is proposed for subset selection from the available landmarks. This algorithm searches for the subset that yields minimal uncertainty for the obtained pose parameters. Navigation tasks have different types of goals: moving along a path, photographing an object for a long period of time, etc. The significance of the various pose parameters differs for different navigation tasks. Therefore, a requirements matrix is constructed from a supplied severity function, which defines the relative importance of each parameter. This knowledge can then be used to search for the subset that minimizes the uncertainty of the important parameters, possibly at the cost of greater uncertainty in others. It is shown that the task-oriented landmark selection problem can be defined as an integer-programming problem for which a very good approximation can be obtained. The problem is then translated into a semi-definite programming representation which can be rapidly solved. The feasibility and performance of the proposed algorithm is studied through simulations and lab experimentation.

This paper presents a cognitive-motivated approach for classification of 3D objects according to the functional paradigm. We hypothesize that classification can be achieved through simulation of actions meant to verify whether a candidate object fulfills a certain functionality. This paper presents ABSV: Agent Based Simulated Vision, a novel approach that tries to imitate the way humans perform certain classification tasks. ABSV can determine the category of a candidate object by verifying certain functional properties that the object should possess. Unlike conventional functional approaches, it uses virtual environment to simulate the interaction between the object and various examination agents to expose those functionalities. To demonstrate our approach we have implemented it for the recognition of several object categories. We achieved promising classification results using both complete CAD models and real 3D scanned data generated from a single view point. We believe that the concepts introduced in ABSV will influence significantly the design of robot classification systems. 1

We present a novel algorithm (which we call "Frag- Track") for tracking an object in a video sequence. The template object is represented by multiple image fragments or patches. The patches are arbitrary and are not based on an object model (in contrast with traditional use of modelbased parts e.g. limbs and torso in human tracking). Every patch votes on the possible positions and scales of the object in the current frame, by comparing its histogram with the corresponding image patch histogram. We then minimize a robust statistic in order to combine the vote maps of the multiple patches. A key tool enabling the application of our algorithm to tracking is the integral histogram data structure [18]. Its use allows to extract histograms of multiple rectangular regions in the image in a very efficient manner. Our algorithm overcomes several difficulties which cannot be handled by traditional histogram-based algorithms [8, 6]. First, by robustly combining multiple patch votes, we are able to handle partial occlusions or pose change. Second, the geometric relations between the template patches allow us to take into account the spatial distribution of the pixel intensities - information which is lost in traditional histogram-based algorithms. Third, as noted by [18], tracking large targets has the same computational cost as tracking small targets. We present extensive experimental results on challenging sequences, which demonstrate the robust tracking achieved by our algorithm (even with the use of only gray-scale (noncolor) information).

Standard practices in background modeling learn a separate model for every pixel in the image. However, in dynamic scenes the connection between an observation and the place where it was observed is much less important and is usually random. For example, a wave observed in an ocean scene could easily have been observed at another place in the image. Moreover, during a limited learning period, we cannot expect to observe at every pixel all the possible background behaviors. We therefore develop in this paper a background model in which observations are decoupled from the place in the image where they were observed. A single non-parametric model is used to describe the dynamic region of the scene, aggregating the observations from the whole region. Using high-order features, we demonstrate the feasibility of our approach on challenging ocean scenes using only grayscale information.

The aim of the presented system is simplification of the daily pathological routine of prostatic cancer diagnostics. The system combines telepathology with computer-aided diagnostics algorithms. To the best of our knowledge, this is the first approach proposing such a comprehensive method. Our system is designed to accumulate knowledge in learning process during diagnostics. Our system targets image acquisition and interpretation stages. The image acquisition subsystem solves various problems related to microscopical slide digitization like biomedical image registration, data representation, and processing. The interpretation subsystem bases on Gabor filter texture features as well as on color features. A support vector machine classifier together with feature selection is used for computer-aided diagnostics. The experimental validation of the system bases on a database of more than three thousand samples.During the experimental evaluation, the system exhibited successful interaction with a pathologist.

We propose a novel scheme for fusion between two types of modalities to support function-based classification. While the first modality targets functional classification from sounds registered at impact, the second one aims classification of objects in 3D images. Using audio one can answer functional questions such as what is the material the analyzed objects are built of, if the objects are full or hollow, if they are heavy, and if they are rigidly linked to their supports. Audio based signatures are used to label parts of the object under analysis. Different parts of any object can be partitioned in generic multi-level hierarchical descriptions of functional components. Functionality, in the visual modality reasoning scheme, is derived from a large set of geometric attributes and relationships between object parts. These geometric properties represent labeling signatures to the primitive and functional parts of the analyzed classes. The fusion between both of the modalities relies on a shared cooperation among audio and visual signatures of the functional and primitive parts. The scheme does not require a-priori knowledge about any class. We tested the proposed scheme on a database of about one thousand different 3D objects. The results show high accuracy in classification

In this paper we present a novel method for visual scanning and target tracking by means of independent pan-tilt cameras which mimic the chameleon visual system. We present a systematic and optimization-based approach to the problem, from the high-level to the low-level control. In particular, in the first part we develop a new algorithm for scanning the sphere using multiple cameras. The algorithm combines information about the environment and a model of target movement, to perform optimal scanning by means of stochastic dynamic programming. In the second part we develop a model-based control strategy for target tracking. A switching optimal control strategy based on smooth pursuit and saccades is designed by means of explicit model predictive control (MPC) theory. We simulated and experimentally validated our theory on a robotic chameleon head composed of two independent pan-tilt cameras. The resulting scanning pattern and target tracking has a remarkable resemblance to the one seen in nature by chameleons

An algorithm for pose and motion estimation using corresponding features in omnidirectional images and a digital terrain map is proposed. In previous paper, such algorithm for regular camera was considered. Using a digital terrain (or digital elevation) map (DTM/DEM) as a global reference enables recovering the absolute position and orientation of the camera. In order to do this, the DTM is used to formulate a constraint between corresponding features in two consecutive frames. In this paper, these constraints are extended to handle non-central projection, as is the case with many omnidirectional systems. The utilization of omnidirectional data is shown to improve the robustness and accuracy of the navigation algorithm. The feasibility of this algorithm is established through lab experimentation with two kinds of omnidirectional acquisition systems. The first one is polydioptric cameras while the second is catadioptric camera

Many vision-based navigation systems are restricted to use only a limited number of landmarks when computing the camera pose. This limitation is due to the overhead of detecting and tracking these landmarks along the image sequence. A new algorithm is proposed for subset selection from the available landmarks. This algorithm searches for the subset that yields minimal uncertainty for the obtained pose parameters. Navigation tasks have different types of goals: moving along a path, photographing an object for a long period of time etc. The significance of the various pose parameters differs for different navigation tasks. Therefore, a requirements matrix is constructed from a supplied severity function, which defines the relative importance of each parameter. This knowledge can then be used to search for the subset that minimizes the uncertainty of the important parameters, possibly at the cost of greater uncertainty in others. It is shown that the task-oriented landmark selection problem can be defined as an integer-programming problem for which a very good approximation can be obtained. The problem is then translated into a semi-definite programming representation which can be rapidly solved. The feasibility and performance of the proposed algorithm is studied through simulations and lab experimentation

This paper offers a path planning algorithm based on splines. The sought path avoids the obstacles, and is smooth and short. Smoothing is used as an integral part of the algorithm, and not only as a final improvement to a path found by other methods. In order to avoid a very difficult optimization over all the path's points, it is modeled by a sequence of splines defined by a gradually increasing number of knots

A novel algorithm for pose and motion estimation using corresponding features and a Digital Terrain Map is proposed. Using a Digital Terrain (or Digital Elevation) Map (DTM/DEM) as a global reference enables the elimination of the ambiguity present in vision-based algorithms for motion recovery. As a consequence, the absolute position and orientation of a camera can be recovered with respect to the external reference frame. In order to do this, the DTM is used to formulate a constraint between corresponding features in two consecutive frames. Explicit reconstruction of the 3D world is not required. When considering a number of feature points, the resulting constraints can be solved using nonlinear optimization in terms of position, orientation, and motion. Such a procedure requires an initial guess of these parameters, which can be obtained from dead-reckoning or any other source. The feasibility of the algorithm is established through extensive experimentation. Performance is compared with a state-of-the-art alternative algorithm, which intermediately reconstructs the 3D structure and then registers it to the DTM. A clear advantage for the novel algorithm is demonstrated in variety of scenarios.

This paper presents a method to globally segment volumetric images into regions that contain convex or concave (elliptic) iso-surfaces, planar or cylindrical (parabolic) iso-surfaces, and volumetric regions with saddle-like (hyperbolic) iso-surfaces, regardless of the value of the iso-surface level. The proposed scheme relies on a novel approach to globally compute, bound, and analyze the Gaussian and mean curvatures of an entire volumetric data set, using a trivariate B-spline volumetric representation. This scheme derives a new differential scalar field for a given volumetric scalar field, which could easily be adapted to other differential properties. Moreover, this scheme can set the basis for more precise and accurate segmentation of data sets targeting the identification of primitive parts. Since the proposed scheme employs piecewise continuous functions, it is precise and insensitive to aliasing.

In microscopy, regions of interest are usually much smaller than the whole slide area. Various microscopy related medical applications, such as telepathology and computer aided diagnosis, are liable to benefit greatly from microscope auto positioning on previously defined regions of interest. In this paper, we present a method for image-based auto positioning on a microscope slide. The method is based on localization of a microscopic query image using a previously acquired slide map. It uses geometric hashing, a highly efficient technique drawn from the object recognition field. The algorithm exhibits high tolerance to possible variations in visual appearance due to slide rotations, scaling and illumination changes. Experimental results indicate high reliability of the algorithm.

In this paper, we present a novel method to extract stroke order independent information from online data. This information, which we term pseudo-online, conveys relevant information on the offline representation of the word. Based on this information, a combination of classification decisions from online and pseudo-online cursive word recognizers is performed to improve the recognition of online cursive words. One of the most valuable aspects of this approach with respect to similar methods that combine online and offline classifiers for word recognition is that the pseudo-online representation is similar to the online signal and, hence, word recognition is based on a single engine. Results demonstrate that the pseudo-online representation is useful as the combination of classifiers perform better than those based solely on pure online information.

The behavior of white and red blood cells, platelets, and circulating injected particles is one of the most studied areas of physiology. Most methods used to analyze the circulatory patterns of cells are time consuming. We describe a system named CellTrack, designed for fully automated tracking of circulating cells and micro-particles and retrieval of their behavioral characteristics. The task of automated blood cell tracking in vessels from in vivo video is particularly challenging because of the blood cells' nonrigid shapes, the instability inherent in in vivo videos, the abundance of moving objects and their frequent superposition. To tackle this, the CellTrack system operates on two levels: first, a global processing module extracts vessel borders and center lines based on color and temporal patterns. This enables the computation of the approximate direction of the blood flow in each vessel. Second, a local processing module extracts the locations and velocities of circulating cells. This is performed by artificial neural network classifiers that are designed to detect specific types of blood cells and micro-particles. The motion correspondence problem is then resolved by a novel algorithm that incorporates both the local and the global information. The system has been tested on a series of in vivo color video recordings of rat mesentery. Our results show that the synergy between the global and local information enables CellTrack to overcome many of the difficulties inherent in tracking methods that rely solely on local information. A comparison was made between manual measurements and the automatically extracted measurements of leukocytes and fluorescent microspheres circulatory velocities. This comparison revealed an accuracy of 97%. CellTrack also enabled a much larger volume of sampling in a fraction of time compared to the manual measurements. All these results suggest that our method can in fact constitute a reliable replacement for manual extraction of blood flow characteristics from in vivo videos.

In microscopy, regions of interest are usually much smaller than the whole slide area. Various microscopy related medical applications are liable to benefit greatly from microscope auto positioning in previously defined regions of interest. In this paper we present a method for image-based auto positioning on a microscope slide. The method is based on localization of a microscopic query image using a previously acquired slide map. It uses geometric hashing, a highly efficient technique drawn from the object recognition field. The algorithm exhibits high tolerance to possible variations in visual appearance due to slide rotations, scaling and illumination changes. Experimental results indicate high reliability of the algorithm. 1

This paper presents a scheme to globally compute, bound, and analyze the Gaussian and mean curvatures of an entire volumetric data set, using a trivariate B-spline volumetric representation. The proposed scheme is not only precise and insensitive to aliasing, but also provides a method to globally segment the images into volumetric regions that contain convex or concave {elliptic) iso-surfaces, planar or cylindrical (parabolic) iso-surfaces, and volumetric regions with saddle-like (hyperbolic) iso-surfaces, regardless of the value of the iso-surface level. This scheme, which derives a new differential scalar field for a given scalar field, could easily be adapted to other differential properties.

The task of segmenting cell nuclei in microscope images is a classical image analysis problem. The accurate nuclei segmentation may contribute to development of successful system which automate the analysis of microscope images for pathology detection. In this article we describe a method for semi-supervised training of fuzzy logic engine. The fuzzy logic engine is applied to connect a set of parameters proven to be important for nucleus segmentation. In addition each parameter for itself is detected using a set of fuzzy logic rules. We present results of nuclei segmentation using fuzzy logic set of rules.

Much work has been done in the field of visual object tracking, yielding a wide range of trackers, including ones aimed for multiple objects. In many cases, there may be a coupling between simultaneously tracked objects, e.g., the locations of some person's eyes. In such cases, tracking each object independently, or using any multitarget tracker ignoring this coupling, will be suboptimal. This paper addresses these cases and takes advantage of the coupling between the tracked objects to enhance the tracking performance. An analytically justified, probabilistic framework for cooperating between the individual trackers is suggested. The framework is fairly general, allowing to cooperate between any two trackers which output a probability density function of the tracked state, even when the objects are tracked in different state spaces. The framework is successfully tested on two different kinds of trackers, showing the benefit gained from the coupling exploitation.

A novel algorithm for pose estimation using feature correspondences and Digital Terrain Map (DTM) is proposed. A constraint is formulated by using corresponding features from two consecutive frames together with the information provided by the elevation map. The proposed constraint is nonlinear and is solved by using a simple numerical method. The proposed approach does not require an intermediate explicit reconstruction of the 3D world. The feasibility of the algorithm is studied using both synthetic data of a virtual terrain and experimental data obtained from a terrain model and a robotic camera.

Bug algorithms are a class of popular algorithms for autonomous robot navigation in unknown environments with local information. Very natural, with low memory requirements, Bug strategies do not yet allow any competitive analysis. The bound on the robot's path changes from scene to scene depending on the obstacles, even though a new obstacle may not alter the length of the shortest path. We propose a new competitive algorithm, CautiousBug, whose competitive factor has an order of O(d/sup m-1/), where d is the length of the optimal path from starting point S to a target point T. m = 2/sup #Min-1/ and #Min denote the number of the distance function isolated local minima points in the given environment. Simulations were performed to study the average competitive factor of the algorithm.

We describe a system for detection and classification of moving targets. The system’s change detection and tracking modules are based on background adaptation, with the help of information about targets obtained from preceding time steps. The classification module performs a hybrid classification that combines motion and appearance features. The system is able to perform real-time detection, tracking and classification of targets in outdoor settings. Experiments demonstrate that the proposed hybrid classifier architecture improves classification significantly, thereby permitting real-time discrimination among a considerable number of classes, some of which are quite similar.

Estimating intrinsic geometric properties of a surface from a polygonal mesh obtained from range data is an important stage of numerous algorithms in computer and robot vision, computer graphics, geometric modeling, industrial and biomedical engineering. This work considers different computational schemes for local estimation of intrinsic curvature geometric properties. Five different algorithms and their modifications were tested on triangular meshes that represent tessellations of synthetic geometric models. The results were compared with the analytically computed values of the Gaussian and mean curvatures of the non-uniform rational B-spline (NURBs) surfaces, these meshes originated from. This work manifests the best algorithms suited for that indeed different algorithms should be employed to compute the Gaussian and mean curvatures.

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.

This paper presents a method for image based robot navigation under the full perspective model. The robot navigates through unknown indoor environments. A target image is taken from an unconstrained position in the environment and given to the robot. The robot starts at an arbitrary position and navigates to the position at which the target image was taken. The approach is based on using images of the environment taken by the robot at different positions along the path and comparing them with a target image. No extraction of 3D models of the scene is needed. The robot finds automatically an image which shows part of the environment shown in the target image. It then moves on the floor, takes pictures with its camera, finds corresponding features in the current and target image, and uses them to extract the motion parameters to the target location. All these steps are performed automatically. This paper describes experimental results performed with a Nomad XR4000 mobile robot These experiments show the feasibility and the significant benefits of our approach.

The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types. Finally, we present empirical results of applying our scheduling algorithm to the Latin Square problem.

An automatic cortical gray matter segmentation from a three-dimensional (3-D) brain images [magnetic resonance (MR) or computed tomography] is a well known problem in medical image processing. In this paper, we first formulate it as a geometric variational problem for propagation of two coupled bounding surfaces. An efficient numerical scheme is then used to implement the geodesic active surface model. Experimental results of cortex segmentation on real 3-D MR data are provided.

Keyword-based search engines are in widespread use today as a popular means for Web-based information retrieval. Although such systems seem deceptively simple, a considerable amount of skill is required in order to satisfy non-trivial information needs. This paper presents a new conceptual paradigm for performing search in context, that largely automates the search process, providing even non-professional users with highly relevant results. This paradigm is implemented in practice in the IntelliZap system, where search is initiated from a text query marked by the user in a document she views, and is guided by the text surrounding the marked query in that document ("the context"). The context-driven information retrieval process involves semantic keyword extraction and clustering to automatically generate new, augmented queries. The latter are submitted to a host of general and domain-specific search engines. Search results are then semantically reranked, using context. Experimental results testify that using context to guide search, effectively offers even inexperienced users an advanced search tool on the Web.

We address the problem of rating or comparing navigation algorithms, or more generally navigation packages. For a given environment a navigation package consists of a motion planner and a sensor to be used during navigation. The ability to rate or measure a navigation package is important in order to address issues like sensor customization for an environment and choice of a motion planner in an environment. We develop a framework under which we can rate a given navigation package. Based on the navigation package, a partially observable Markov decision process (POMDP) is defined. Next an optimal policy to be used in this POMDP is searched for. The performance achieved under the resulting policy serves to measure the navigation package. The paper presents the motivations for solving the problem, the model we use and the framework which we have developed.

In a companion paper (see Proceedings of ICRA 2001) we developed a framework for rating or comparing navigation packages. For a given environment a navigation package consists of a motion planner and a sensor to be used during navigation. The ability to rate or measure a navigation package is important in order to address issues like sensor customization for an environment and choice of a motion planner in an environment. In this paper we present the algorithm which we use in order to rate a given navigation package. Under the framework which was presented previously, a partially observable Markov decision process is defined. The algorithm searches for an optimal policy to be employed in this decision process. We briefly review the problem and framework, develop the algorithm and present experimental results.

Article Share on Placing search in context: the concept revisited Authors: Lev Finkelstein Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, Israel Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, IsraelView Profile , Evgeniy Gabrilovich Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, Israel Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, IsraelView Profile , Yossi Matias Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, Israel Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, IsraelView Profile , Ehud Rivlin Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, Israel Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, IsraelView Profile , Zach Solan Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, Israel Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, IsraelView Profile , Gadi Wolfman Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, Israel Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, IsraelView Profile , Eytan Ruppin Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, Israel Zapper Technologies Inc., 3 Azrieli Center, Tel Aviv 67023, IsraelView Profile Authors Info & Claims WWW '01: Proceedings of the 10th international conference on World Wide WebMay 2001 Pages 406–414https://doi.org/10.1145/371920.372094Online:01 April 2001Publication History 319citation2,268DownloadsMetricsTotal Citations319Total Downloads2,268Last 12 Months193Last 6 weeks26 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 SiteGet Access

We address the problem of rejecting false matches of points between two perspective views. The two views are taken from two arbitrary, unknown positions and orientations. We present an algorithm for identification of the false matches between the views. The algorithm exploits the possibility of rotating one of the images to achieve some common behavior of the correct matches. Those matches that deviate from this common behavior turn out to be false matches. Our algorithm does not, in any way, use the image characteristics of the matched features. In particular, it avoids problems that cause the false matches in the first place. The algorithm works even in cases where the percentage of false matches is as high as 85 percent. The algorithm may be run as a post-processing step on output from any point matching algorithm. Use of the algorithm may significantly improve the ratio of correct matches to incorrect matches. We present the algorithm, identify the conditions under which it works, and present results of the test.

We use an unconditionally stable numerical scheme to implement a fast version of the geodesic active contour model. The proposed scheme is useful for object segmentation in images, like tracking moving objects in a sequence of images. The method is based on the Weickert-Romeney-Viergever (additive operator splitting) AOS scheme. It is applied at small regions, motivated by the Adalsteinsson-Sethian level set narrow band approach, and uses Sethian's (1996) fast marching method for re-initialization. Experimental results demonstrate the power of the new method for tracking in color movies.

It has been recognized that robust motion planners should take into account the varying performance of localization sensors across the configuration space. Although a number of works have shown the benefits of using such a performance map, the work on actual computation of such a performance map has been limited and has addressed mostly range sensors. Since vision is an important sensor for localization, it is important to have performance maps of vision sensors. We present a method for computing the performance map of a vision-based sensor. We compute the map and show that it accurately describes the actual performance of the sensor, both on synthetic and real images. The method we use involves evaluating closed form formulas and hence is very fast. Using the performance map computed by this method for motion planning and for devising sensing strategies will contribute to more robust navigation algorithms.

We address the problem of rejecting false matches of points between two perspective views. Even the best algorithms for image matching make some mistakes and output some false matches. We present an algorithm for identification of the false matches between the views. The algorithm exploits the possibility of rotating one of the images to achieve some common behaviour of the correct matches. Those matches that deviate from this common behaviour turn out to be false matches. The statistical tool we use is the mean shift mode estimator. Our algorithm does not use in any way the image characteristics of the matched features. In particular it avoids problems that cause the false matches in the first place. The algorithm may be run as a post processing step on output from any point matching algorithm. Use of the algorithm may significantly improve the ratio of correct matches to incorrect matches. On real images our algorithm has improved the percentage of correct matches from an initial 20%-30% to a final 70%-80%. For robust estimation algorithms which are later employed, this is a very desirable quality since it reduces significantly their computational cost. We present the algorithm, identify the conditions under which it works, and present results of testing it on both synthetic and real images.

Vision is an important sensor used for mobile robot navigation. One approach to localization which is based on vision is to compute camera egomotion with respect to base images. What characterizes this method of localization is that its performance varies greatly in different positions. Active navigation is an approach to path and sensing planning which is designed to address varying performance of a sensor across the configuration space. We describe how to integrate a vision-based localization sensor with active navigation. We explain the localization process, how its performance varies across the configuration space, and the use of this variation by active navigation.

If we histogram the normal flow vectors in images of a scene viewed by a moving observer, we can use the time-varying histogram to derive qualitative information about the observer's motion-for example, whether it is (primarily) translational or rotational, and whether the direction of translation or axis of rotation is (roughly) parallel or perpendicular to the camera axis. This is illustrated using flow histogram obtained from a variety of real image sequences.

The navigational tasks of computing time-to-impact and controlling movements within a specific range are addressed. By using specially designed lenses various components of these procedures, consisting of mathematical transformations, can be provided at image acquisition time, and therefore speed up execution time. This study discusses the optical implementation of different correlators based on the Fourier transform and Mellin transform. In addition, the fractional versions of these correlators are defined and analyzed. Based on the experimental results it can be concluded that the optical implementation of transformations can indeed play a significant role in speeding up execution time in respect to the above mentioned navigational tasks.

Recently it has been recognized that robust motion planners should take into account the varying performance of localization sensors across the configuration space. Although a number of works have shown the benefits of using such a performance map, the work on actual computation of such a performance map has been limited and has addressed mostly range sensors. Since vision is an important sensor for localization, it is important to have performance maps of vision sensors. In this paper we compute the performance map of a vision-based sensor. We show that the computed map accurately describes the actual performance of the sensor, both on synthetic and real images. The method we present involves evaluating closed form formulas and hence is very fast. Using the performance map computed by this method for motion planning and for devising sensing strategies will contribute to more robust navigation algorithms.

Skew detection via principal components is proposed as an effective method for images which contain other parts than text. It is shown that the negative of the image leads to much more robust results, and that the computation time involved is still practical.

Fixation is shown to be a visual routine which reduces dead-reckoning errors accumulated by an autonomous guided vehicle (AGV). By fixating on a landmark as the vehicle moves one can improve the navigation accuracy even if the scene coordinates of the landmark are unknown. In contrast with previous methods which assume that the coordinates of the landmark are known, our method enables any point of the observed scene to be selected as a landmark, and not just pre-measured points. Moreover, in contrast with other methods, in fixation only one point needs to be tracked. This disposes of the need to be able to identify which of the landmarks is currently being tracked, through a matching algorithm or by other means. Thus the incorporation of fixation into the navigation process does not involve long computation times and may be done while the vehicle is continuously moving. In addition to the basic method, we suggest an "emergency procedure" for obtaining absolute position once the vehicle gets lost. We support our findings with both experimental and simulation results.

In a previous paper (1998) we presented a method for image-based navigation by which a robot can navigate to desired positions and orientations in 3D space specified by single images taken from these positions. In this paper we further investigate the method and develop robust algorithms for navigation assuming the perspective projection model. In particular, we develop a tracking algorithm that exploits our knowledge of the motion performed by the robot at every step. This algorithm allows us to maintain correspondences between frames and eliminate false correspondences. We combine this tracking algorithm with an iterative optimization procedure to accurately recover the displacement of the robot from the target. Our method for navigation is attractive since it does not require a 3D model of the environment. We demonstrate the robustness of our method by applying it to a six degree of freedom robot arm.

Presents a globally convergent range-sensor based navigation algorithm in three-dimensions, called 3D Bug. The 3D Bug algorithm navigates a point robot in a three-dimensional unknown environment using position and range sensors. The algorithm strives to process the sensory data in the most reactive way possible, without sacrificing the global convergence guarantee. Moreover, unlike previous reactive-like algorithms, 3D Bug uses three-dimensional range data and plans three-dimensional motion throughout the navigation process. The algorithm alternates between two modes of motion. During motion towards the target, which is the first motion mode of the algorithm, the robot follows the locally shortest path in a purely reactive fashion. During traversal of an obstacle surface, which is the second mode of motion, the robot incrementally constructs a reduced data structure of an obstacle, while performing local shortcuts based on range data. We resent preliminary simulation results of the algorithm, which show that 3D Bug generates paths that resemble the globally shortest path in simple scenarios. Moreover, the algorithm generates reasonably short paths even in concave, room-like environments.

We present a geometric interpretation of the problem of motion recovery from three weak-perspective images. Our interpretation is based on reducing the problem of estimating the motion to a problem of finding triangles on a sphere whose angles are known. Using this geometric interpretation, a simple method to completely recover the motion parameters using three images is developed. The results of running the algorithm on real images are presented. In addition, we describe which of the various motion parameters can be recovered already from two images.

This paper deals with the problem of determining the position and orientation of an autonomous guided vehicle (AGV) by fusing odometry with the information provided by a vision system. The main idea is to exploit the ability of pointing a camera in different directions, to fixate on a point of the environment while the AGV is moving. By fixating on a landmark, one can improve the navigation accuracy even if the scene coordinates of the landmark are unknown. This is a major improvement over previous methods which assume that the coordinates of the landmark are known, since any point of the observed scene can be selected as a landmark, and not just pre-measured points. This work argues that fixation is basically a simpler procedure than previously mentioned methods. The simplification comes from the fact that only one point needs to be tracked as opposed to multiple points in other methods. This disposes of the need to be able to identify which of the landmarks is currently being tracked, through a matching algorithm or by other means. We support our findings with both experimental and simulation results.

The visual robustness of biological systems is in part due to their ability to actively integrate (fuse) information from a number of visual cues. In addition to active integration, the perception-action nature of biological vision demands event-driven behavioral composition. Providing mechanical vision systems with similar capabilities therefore requires tools and techniques for cue integration and behavioral composition. In this paper, we address two issues. First, we present a unified approach for handling both active integration and behavioral composition. The approach combines a theoretical framework that handles uncertainty using a voting scheme with a set of behaviors that are committed to achieving a specific goal through common effort and a well-known process composition model. Secondly, we address the issue of integration in the active vision activity of smooth pursuit. We have experimented with the fusion of four smooth pursuit techniques (blob tracking, edge tracking, template matching and image differencing). We discuss each technique, highlighting their strengths and weaknesses, and then show that fusing the techniques according to our formal framework improves system tracking behavior.

We introduce a novel method for visual homing. Using this method a robot can be sent to desired positions and orientations in 3-D space specified by single images taken from these positions. Our method determines the path of the robot on-line. The starting position of the robot is not constrained, and a 3-D model of the environment is not required. The method is based on recovering the epipolar geometry relating the current image taken by the robot and the target image. Using the epipolar geometry, most of the parameters which specify the differences in position and orientation of the camera between the two images are recovered. However, since not all of the parameters can be recovered from two images, we have developed specific methods to bypass these missing parameters and resolve the ambiguities that exist. We present two homing algorithms for two standard projection models, weak and full perspective. We have performed simulations and real experiments which demonstrate the robustness of the method and that the algorithms always converge to the target pose.

Many types of common objects, such as tools and vehicles, usually move in simple ways when they are wielded or driven. The natural axes of the object tend to remain aligned with the local trihedron defined by the object's trajectory. Based on this observation we use a model called Frenet-Serret motion which corresponds to the motion of a moving trihedron along a space curve. Knowing how the Frenet-Serret frame is changing relative to the observer gives us essential information for understanding the object's motion. This is illustrated here for four examples, involving tools (a wrench and a saw) and vehicles (an accelerating van, a turning taxi).

We describe a new invariant-based data model for image databases under our approach for shape-based retrieval. The data model relies on contours description of the image shape, and emphasizes the use of invariants. Efficient indexing is based on geometric invariant features, while semi-local multi-valued invariant signatures are used for ranking the answers. The advantages of the proposed approach are its ability to retrieve images in situations in which part of the shape is missing (i.e., in case of occlusion or sketch queries), its ability to handle images distorted by different viewpoint transformations, and its ability to flexibly answer queries based on logical or shape descriptions (query by example), or on a combination of both. The approach also handles sketch based queries. We implemented our data model in an object oriented database system with a SQL-like user interface. The paper presents experimental results demonstrating the effectiveness of the proposed approach.

Presents a method for recognizing mechanisms and describing their behaviours from image sequences showing their relations. It uses a simple and expressive language for describing the behaviour of fixed-axes mechanisms. The language symbolically captures the important aspects of the kinematics and the simple dynamics of the mechanism. We show how this language combined with a vision system can automatically identify mechanisms and their behaviours from a sequence of images.

In this paper we present a new active vision technique called zoom tracking. Zoom tracking is the continuous adjustment of a camera's focal length, to keep a constant-sized image of an object moving along the camera's optical axis. Two methods for performing zoom tracking are presented: a closed-loop visual feedback algorithm based on optical flow, and use of depth information obtained from an autofocus camera's range sensor. We show that the image stability provided by zoom tracking improves the performance of algorithms that are scale variant, such as correlation-based trackers. While zoom tracking cannot totally compensate an object's motion, due to the effect of perspective distortion, an analysis of this distortion provides a quantitative estimate of the performance of zoom tracking.

A general paradigm for recognizing 3D objects is offered, and applied to some geometric primitives (spheres, cylinders, cones, and tori). The assumption is that a curve on the surface was measured with high accuracy (for instance, by a sensory robot). Differential invariants of the curve in one method and differential properties of curves and surfaces in the other are then used to recognize the surface. The motivation is twofold: the output of some devices is not surface range data, but such curves. So, surface invariants, which may be simpler in some cases, cannot always be obtained. Also, a considerable speedup is obtained by using curve data, as opposed to surface data which usually contains a much higher number of points.

We address the problem of practical manipulation planning for rearrangement tasks of many movable objects. We study a special case of the rearrangement task, where the only allowed manipulation is pushing. We search for algorithms that can provide practical planning time for most common scenarios. We present a hierarchical classification of manipulation problems into several classes, each characterized by properties of the plans that can solve it. Such a classification allows one to consider each class individually, to analyze and exploit properties of each class, and to suggest individual planning methods accordingly. Following this classification, we suggest algorithms for two of the defined classes. Both items have been tested in a simulated environment, with up to 32 movable objects and 66 combined DOF. We present the simulations results as well as some experimental results using a real platform.

We formulate and address the problem of planning a pushing manipulation by a mobile robot which tries to rearrange several movable objects in its work space. We present an algorithm which, when given a set of goal configurations, plans a pushing path to the "cheapest" goal or announces that no such path exists. Our method provides detailed manipulation plans, including any intermediate motion of the pusher while changing contact configuration with the pushed movables. Given a pushing problem, a pushing path is found using a two-phase procedure: a context sensitive back propagation of a cost function which maps the configuration space, and a gradient descent phase which builds the pushing path. Both phases are based on a dynamic neighborhood filter which constrains each step to consider only admissible neighboring configurations. This admissibility mechanism provides a primary tool for expressing the special characteristics of the pushing manipulation. It also allows for a full integration of any geometrical constraints imposed by the pushing robot, the pushed movables and the environment. We prove optimality and completeness of our algorithm and give some experimental results in different scenarios.

Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions of Euclidean space (e.g. a planar region containing polygonal obstacles). In this paper, we define a version of the motion-planning problem in which the robots move simultaneously. We establish conditions under which a team of robots having a particular configuration can move from any start location to any goal destination in a graph-structured space. We show that, for a group of robots that maintain a fixed formation, we can find the "shortest" path in polynomial time, and we give faster algorithms for special kinds of environments.

The purpose of a document is to facilitate the transfer of information from its author to its readers. It is the author's job to design the document so that the information it contains can be interpreted accurately and efficiently. To do this, the author can make use of a set of stylistic tools. In this paper, we introduce the concept of document functionality, which attempts to describe the roles of documents and their components in the process of transferring information. A functional description of a document provides insight into the type of the document, into its intended uses, and into strategies for automatic document interpretation and retrieval. To demonstrate these ideas, we define a taxonomy of functional document components and show how functional descriptions can be used to reverse-engineer the intentions of the author, to navigate in document space, and to provide important contextual information to aid in interpretation.

The purpose of this paper is twofold: we first present a novel architecture for real-time active vision systems, and then enhance the architecture with a unified approach to fault tolerance. Our system is designed modularly in order to enable the flexible addition of hardware and software redundancy and also to allow reconfiguration when and where needed. This gives us the ability to handle faults in the context of active vision.

We present DistBug, a new navigation algorithm for mobile robots which exploits range data. The algorithm belongs to the Bug family, which combines local planning with global information that guarantees convergence. Most Bug-type algorithms use contact sensors and consist of two reactive modes of motion: moving toward the target between obstacles and following obstacle boundaries, DistBug uses range data in a new "leaving condition" which allows the robot to abandon obstacle boundaries as soon as global convergence is guaranteed, based on the free range in the direction of the target. The leaving condition is tested directly on the sensor readings, thus making the algorithm simple to implement. To further improve performance, local information is utilized for choosing the boundary following direction, and a search manager is introduced for bounding the search area. The simulation results indicate a significant advantage of DistBug relative to the classical Bug2 algorithm. The algorithm was implemented and tested on a real robot, demonstrating the usefulness and applicability of our approach.

Foveated vision and two-mode tracking, as inspired by the human oculomotor system, are often used in active vision system. The purpose of this paper is to provide answers to the following basic questions which arise from implementations. First, is it beneficial to have foveated vision and what is the optimal size of the foveal window? Second, is there a need for two control mechanisms (smooth pursuit and saccade) for improved performance and how can one efficiently switch between them? In order to do so, a setup is proposed in which these strategies can be evaluated in a systematic manner. It is shown that the fovea appears as a compromise between the tightness of the tracking specifications and computational constraints. Introducing a model for the later and postulating some a priori knowledge of the target behavior, it is possible to compute the size of the fovea in an optimal way. As a by-product, "smooth-pursuit" can be defined in a natural way, and the use of a two-mode tracking scheme is justified. The second mode, i.e. "saccadic control", aims at re-centering the target on the fovea so that the smooth pursuit controller can continue to operate. It is shown that a control strategy can indeed be defined so that this objective can be met under appropriate operating conditions.

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".

The active vision paradigm couples perception and action at several different levels. The effective use of active vision in complex robotic tasks requires that these levels operate both independently and cooperatively, reliably and in real-time. In this paper, we present a system for real-time active vision with fault tolerance. The system provides a vocabulary of active vision routines along with the means for composing the routines into continuously running perception-action processes. A novel architecture which enables the integration of the perceptive capabilities of real-time active vision with the active capabilities of other robotic devices is presented. We then enhance the architecture with a unified approach to fault tolerance and present results from experiments and simulations.

Formulates and addresses the problem of planning a pushing manipulation by a mobile robot which tries to rearrange several movable objects in its work space. The authors present an algorithm which, when given a set of goal configurations, plans a pushing path to the "cheapest" goal or announces that no such path exists. The pushing path is found using a two phase procedure: context sensitive back propagation of a cost function, and a pushing path restoration phase. The latter is based on a gradient descent procedure which considers, at each step, only admissible neighboring configurations. The admissibility mechanism provides a primary tool for expressing the unique characteristics of the pushing manipulation. It also allows a full integration of any geometrical constraints imposed by the pushing robot and the pushed objects. The authors have proved the algorithm to be optimal and (resolution-) complete and give some simulation results in different scenarios, as well as some experimental results using a real platform.

Rearrangement of objects by pushing is a basic manipulation task. The authors (1995) presented a resolution-complete algorithm that plans optimal pushing manipulations for rearrangement tasks but operates in high time and space complexity. In this paper the authors address the issue of practical planning for the same kind of problems. Rather than using a classical heuristic method, the authors propose an alternative approach. The authors present a hierarchical classification of the pushing problems domain into several classes, each characterized by properties of the plans that can solve it. Such a classification allows the authors to consider each class individually, analyze and exploit properties of each class, and suggest individual planning methods. Algorithms for two of the defined classes are presented. Both algorithms were tested in a simulated environment, with up to 32 movable objects and 66 combined DOF. Some of these simulations are presented here.

In this paper, we present an agent architecture/active vision research tool called the Active Vision Shell (AV-shell). The AV-shell can be viewed as a programming framework for expressing perception and action routines in the context of situated robotics. The AV-shelf is a powerful interactive C-shell style interface providing many capabilities important in an agent architecture such as the ability to combine perceptive capabilities of active vision with capabilities provided by other robotic devices, the ability to interact with a wide variety of active vision devices, a set of image routines and the ability to compose the routines into continuously running perception action processes. Finally, we present an application example of AV-shell.

We present TangentBug, a new range-sensor based navigation algorithm for two degrees-of-freedom mobile robots. The algorithm combines local reactive planning with globally convergent behaviour. For the local planning, TangentBug uses the range data to compute a locally shortest path based on a novel structure, termed the local tangent graph (LTG). The robot uses the LTG for choosing the locally optimal direction while moving towards the target. The robot also uses the LTG in its other motion mode, where it follows an obstacle boundary. In this mode the robot uses the LTG for making local short-cuts and testing a leaving condition which allows the robot to resume its motion towards the target. We analyze the convergence and performance properties of TangentBug. We also present simulation results, showing that TangentBug consistently performs better than the classical VisBug algorithm. Moreover, TangentBug produces paths that in simple environments approach the globally optimal path as the sensor's maximal detection range increases.

In order for a robot to operate autonomously in its environment, it must be able to perceive its environment and take actions based on these perceptions. Recognizing the functionalities of objects is an important component of this ability. In this paper, we look into a new area of functionality recognition: determining the function of an object from its motion. Given a sequence of images of a known object performing some function, we attempt to determine what that function is. We show that the motion of an object, when combined with information about the object and its normal uses, provides us with strong constraints on possible functions that the object might be performing.

A sensory based algorithm DistBug, that is guaranteed to reach the target in an unknown environment or report that the target is unreachable, is presented. The algorithm is reactive in the sense that it relies on range data to make local decisions, and does not create a world model. The algorithm consists of two behaviors (modes of motion): straight motion between obstacles and obstacle boundary following. Simulation results as well as experiments with a real robot are presented. The condition for leaving obstacle boundary is based on the free range in the direction to the target. This condition allows the robot to leave the obstacle as soon as the local conditions guarantee global convergence. Range data is utilized for choosing the turning direction when the robot approaches an obstacle. A criterion for reversing the boundary following direction when it seems to be the wrong direction is also introduced. As a direct result of these local decisions, a significant improvement in the performance was achieved.

Geometric invariants are shape descriptors that remain unchanged under geometric transformations such as projection or changing the viewpoint. A new method of obtaining local projective and affine invariants is developed and implemented for real images. Being local, the Invariants are much less sensitive to occlusion than global invariants. The invariants' computation is based on a canonical method. This consists of defining a canonical coordinate system by the intrinsic properties of the shape, independently of the given coordinate system. Since this canonical system is independent of the original one, it is invariant and all quantities defined in it are invariant. The method was applied without the use of a curve parameter. This was achieved by fitting an implicit polynomial to an arbitrary curve in a vicinity of each curve point. Several configurations are treated: a general curve without any correspondence and curves with known correspondences of one or two feature points or lines. Experimental results for different 2D objects in 3D space are presented.>

We present an approach to function-based object recognition that reasons about the functionality of an object's initiative parts. We extend the popular "recognition by parts" shape recognition framework to support "recognition, by functional parts", by combining a set of functional primitives and their relations with a set of abstract volumetric shape primitives and their relations. Previous approaches have relied on more global object features, often ignoring the problem of object segmentation, and thereby restricting themselves to range images of unoccluded scenes. We show how these shape primitives and relations can be easily recovered from superquadric ellipsoids which, in turn, can be recovered from either range or intensity images of occluded scenes. Furthermore, the proposed framework supports both unexpected (bottom-up) object recognition and expected (top-down) object recognition. We demonstrate the approach on, a simple domain by recognizing a restricted class of hand-tools from 2-D images.>

This paper describes the integration of 2D stimulus-driven robot localization and positioning with a token-based correspondence method in a practical robot navigation system. The approach allows for modular acquisition and update of world knowledge for navigation, and robustness of navigation to low-level errors. No special marking of the world is necessary, so the robot may operate in quite general environments. Tests in a real industrial environment confirm the potential of the method.

A method is presented for finding semi-local projective and affine invariants. The method consists of defining a canonical coordinate system using intrinsic properties of the shape, independently of the given coordinate system. Since this canonical system is independent of the original one, it is invariant and all quantities defined in it are invariant. The method is applied to find local invariants of a general curve with known correspondences of one or two feature points or lines.>

A method for localization, the act of recognizing the environment, is presented. The method is based on representing the scene as a set of 2-D views and predicting the appearances of novel views by linear combinations of the model views. The method accurately approximates the appearance of scenes under weak perspective projection. Analysis of this projection as well as experimental results demonstrate that in many cases this approximation is sufficient to accurately describe the scene. When weak perspective approximation is invalid, either a larger number of models can be acquired or an iterative solution to account for the perspective distortions can be used. The method has several advantages over other approaches. It uses relatively rich representations; the representations are 2-D rather than 3-D; and localization can be done from only a single 2-D view.>

The problem of logo recognition is of great interest in the document domain, especially for databases, because of its potential for identifying the source of the document and its generality as a recognition problem. By recognizing the logo, one obtains semantic information about the document, which may be useful in deciding whether or not to analyze the textual components. A multi-level stages approach to logo recognition which uses global invariants to prune the database and local affine invariants to obtain a more refined match is presented. An invariant signature which can be used for matching under a variety of transformations is obtained. The authors provide a method of computing Euclidean invariants and show how to extend them to capture similarity, affine, and projective invariants when necessary. They implement feature detection, feature extraction, and local invariant algorithms and successfully demonstrate the approach on a small database.>

Studies the problem of object recognition by considering it in the context of an agent operating in an environment, where the agent's intentions translate into a set of behaviors. In this context, an object can fulfil a function; if the agent recognizes this, it has in effect recognized the object. To perform this type of recognition one needs on one hand a definition of the desired function, and on the other the means of determining whether the object can fulfil that function. To illustrate this approach the authors describe the visual recognition abilities that might be needed by an autonomous cleaning robot.>

Hypertext users often suffer from the “lost in hyperspace” problem: disorientation from too many jumps while traversing a complex network. One solution to this problem is improved authoring to create more comprehensible structures. This paper proposes several authoring tools, based on hypertext structure analysis. In many hypertext systems authors are encouraged to create hierarchical structures, but when writing, the hierarchy is lost because of the inclusion of cross-reference links. The first part of this paper looks at ways of recovering lost hierarchies and finding new ones, offering authors different views of the same hypertext. The second part helps authors by identifying properties of the hypertext document. Multiple metrics are developed including compactness and stratum . Compactness indicates the intrinsic connectedness of the hypertext, and stratum reveals to what degree the hypertext is organized so that some nodes must be read before others. Several existing hypertexts are used to illustrate the benefits of each technique. The collection of techniques provides a multifaceted view of the hypertext, which should allow authors to reduce undesired structural complexity and create documents that readers can traverse more easily.