Abstract Traditional explainability methods use 2D visualization techniques such as saliency maps. However, when applied to video data, subject and camera motion produce unstable, flickering maps that cannot be temporally aggregated in meaningful ways. This limitation is critical in medical and veterinary settings, which demand biologically grounded explanations intuitive for experts. One such domain is equine pain assessment. Horses are particularly challenging in the context of pain as they are known to hide pain signals in human presence. This leads to increased interest in automation of equine pain recognition which is explainable, i.e., highlighting informative facial and postural cues. However, current explainability approaches are inadequate for providing temporally consistent and clinically interpretable explanations. To address this gap, we present SHIC-XE, an explainability framework that leverages dense 2D-3D correspondence methods to address fundamental viewpoint-dependency limitations for dynamic scenes. Building upon the existing SHIC correspondence framework, our approach projects neural network attention onto canonical 3D surface prototypes, enabling anatomically-consistent, pose-invariant explanations across temporal sequences. Our primary contribution is establishing quantitative metrics for spatially-consistent explainability evaluation, transforming subjective visualization assessment into statistically analyzable measurements. Unlike existing approaches requiring n separate classifiers for n anatomical regions, our unified correspondence mapping maintains constant architectural complexity while achieving comparable classification performance. We provide a preliminary validation of the framework on equine pain recognition as a challenging testbed, achieving video-level F1 scores of 0.67, 0.80, and 0.70 across three datasets under leave-one-subject-out validation. Our systematic evaluation against expert pain ratings by facial region, using a validated equine pain scale, reveals significant correlations between model attention and expert pain scoring, (ears: r = 0.30, $${\varvec{p}} \varvec{<} {\textbf {0.001}}$$ p < 0.001 ; cheek muscles: r = 0.25, $${\varvec{p}} \varvec{<} {\textbf {0.01}}$$ p < 0.01 ; eyes: r = −0.19, $${\textbf {p}} \varvec{<} {\textbf {0.05}}$$ p < 0.05 ) providing the first quantitative validation of explainability methods against domain expertise in this context. This finding challenges widespread literature claims of clinical relevance based solely on qualitative saliency inspection, establishing a methodological framework for rigorous explainability validation. The correspondence-based approach generalizes beyond the demonstrated application to any domain requiring spatial consistency between 2D observations and 3D structural models, providing a foundational methodology for next-generation explainable AI systems.

Archaeology is an intriguing domain for computer vision. It suffers not only from shortage in (labeled) data, but also from highly-challenging data, which is often extremely abraded and damaged. This paper proposes a novel semi-supervised model for classification and retrieval of images of archaeological artifacts. This model utilizes unique data that exists in the domain—manual drawings made by special artists. These are used during training to implicitly transfer the domain knowledge from the drawings to their corresponding images, improving their classification results. We show that while learning how to classify, our model also learns how to generate drawings of the artifacts, an important documentation task, which is currently performed manually. Last but not least, we collected a new dataset of stamp-seals of the Southern Levant. Our code1and dataset2are publicly available.

Abstract The field of animal affective computing is rapidly emerging, and analysis of facial expressions is a crucial aspect. One of the most significant challenges that researchers in the field currently face is the scarcity of high-quality, comprehensive datasets that allow the development of models for facial expressions analysis. One of the possible approaches is the utilisation of facial landmarks, which has been shown for humans and animals. In this paper we present a novel dataset of cat facial images annotated with bounding boxes and 48 facial landmarks grounded in cat facial anatomy. We also introduce a landmark detection convolution neural network-based model which uses a magnifying ensemble method. Our model shows excellent performance on cat faces and is generalizable to human and other animals facial landmark detection.

With the rapid evolution of technology, computers and their users’ workspaces have become an essential part of our life in general. Today, many people use computers both for work and for personal needs, spending long hours sitting at a desk in front of a computer screen, changing their pose slightly from time to time. This phenomenon impacts people’s health negatively, adversely affecting their musculoskeletal and ocular systems. To mitigate these risks, several different ergonomic solutions have been suggested. This study proposes, demonstrates, and evaluates a technological solution that automatically adjusts the computer screen position and orientation to its user’s current pose, using a simple RGB camera and robotic arm. The automatic adjustment will reduce the physical load on users and better fit their changing poses. The user’s pose is extracted from images continuously acquired by the system’s camera. The most suitable screen position is calculated according to the user’s pose and ergonomic guidelines. Thereafter, the robotic arm adjusts the screen accordingly. The evaluation was done through a user study with 35 users who rated both the idea and the prototype system itself highly.

Landscape reconstructions and deep maps are two major approaches in cultural heritage studies. In general, they require the use of historical visual sources such as maps, graphic artworks, and photographs presenting areal scenes, from which one can extract spatial information. However, photographs, the most accurate and reliable source for scenery reconstruction, are available only from the second half of the 19th century onward. Thus, for earlier periods one can rely only on old artworks. Nevertheless, the accuracy and inclusiveness of old artworks are often questionable and must be verified carefully.In this paper, we use GIScience methods with computer-vision capabilities to interrogate old engravings and drawings as well as to develop a new approach for extracting spatial information from these scenic artworks. We have inspected four old depictions of Jerusalem and Tiberias (Israel) created between the 17th and 19th centuries. Using visibility analysis and a RANSAC algorithm we identified the locations of the artists when they drew the artworks and evaluated the accuracy of their final products. Finally, we re-projected 3D map digitized features onto the drawing canvases, thus embedding features not originally drawn. These were then identified, enabling potential extraction of the spatial information they may reflect.Video abstract is available at: https://youtu.be/dmt74VKsfF8

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.

Correctly matching feature points in a pair of images is an important preprocessing step for many computer vision applications. In this paper we propose an efficient method for estimating the number of correct matches without explicitly computing them. To this end, we propose to analyze the set of matches using the spatial order of the features, as projected to the x-axis of the image. The set of features in each image is thus represented by a sequence, and analyzed using the Kendall and Spearman Footrule distance metrics between permutations. This result is interesting in its own right. Moreover, we demonstrate three useful applications of our method: (i) a new halting condition for RANSAC based epipolar geometry estimation methods, (ii) discarding spatially unrelated image pairs in the Structure-from-Motion pipeline, and (iii) computing the probability that a given match is correct based on the rank of the features within the sequences. Our experiments on a large number of synthetic and real data demonstrate the effectiveness of our method. For example, the running time of the image matching stage in the Structure-from-Motion pipeline may be reduced by about 90 percent while preserving about 85 percent of the image pairs with spatial overlap.

Stroke is one of the most common adult injuries, with 6.5 million stroke survivors in the US alone. We use a novel motion capture system together with machine learning tools to evaluate the standard stroke rehabilitation scale, the Fugl-Meyer Assessment (FMA). FMA involves the patient performing specific motor actions. A medical professional rates the performance and provides an FMA score. We have developed a multi depth-camera system using off the shelf consumer depth cameras. Its novelty is in its ability to perform synchronization, data integration and most importantly, calibration on the fly automatically without the need of a professional operator. The camera system tracks the subject's body and outputs a stream of skeleton representations, which allows to evaluate the patients's motor performance. Using a multi camera system rather than a single camera allows capturing motion on all sides of the patient body, as required by the FMA. The system was evaluated in a pilot study at a major hospital. Applying machine learning techniques on the skeleton streams, the system was able to correctly asses FMA scores on 2 of the standard motions with close to 100% success rate. This serves as a proof of concept for the feasibility of creating a full FMA home based assessment tool.

The authors introduce a novel marker‐less multi‐camera setup that allows easy synchronisation between 3D cameras as well as a novel pose estimation method that is calculated on the fly based on the human body being tracked, and thus requires no calibration session nor special calibration equipment. They show high accuracy in both calibration and data merging and is on par with equipment‐based calibration. They deduce several insights and practical guidelines for the camera setup and for the preferred data merging methods. Finally, they present a test case that computerises the Fugl‐Meyer stroke rehabilitation protocol using the authors’ multi‐sensor capture system. They conducted a Helsinki‐approved research in a hospital in which they collected data on stroke patients and healthy subjects using their multi‐camera system. Spatio‐temporal features were extracted from the acquired data and machine learning‐based evaluations were applied. Results showed that patients and healthy subjects can be correctly classified at a rate of above 90%. Furthermore, they show that the most significant features in the classification are strongly correlated with the Fugl‐Meyer guidelines. This demonstrates the feasibility of a low‐cost, flexible and non‐invasive motion capture system that can potentially be operated in a home setting.

In this paper a novel registration algorithm between 3D point clouds is presented. It exploits the fact that current 3D point descriptors (e.g., RoPS) are accompanied by local reference frames(LRF). LRFs of corresponding points are used to estimate the relative rotation between the point clouds. Thus, inlier matches will generate a cluster of rotation matrices. The size and shape of this cluster is unknown. We therefore develop a mean shift clustering algorithm for noisy rotation matrices. It finds the mode of the distribution to estimate the relative rotation. It is then used for estimating the translation vectors from the matched points. Here again mean shift is used for finding the translation component. The algorithm has been tested on different types of sources of 3D data (3D scanner, Lidar, and Structure from Motion(SfM)) of small scanned objects and urban scenes. In all these cases, the algorithm performed well outperforming state of the art algorithms in accuracy and in speed.

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.

A smart context-aware mobile guide may provide the visitor with personalized relevant information from the vast amount of content available at the museum, adapted for his or her personal needs. Earlier studies relied on using sensors for location-awareness and interest detection. This work explores the potential of mobile eye-tracking and vision technology in enhancing the museum visit experience. We report here on satisfactory preliminary results from examining the performance of a mobile eye tracker in a realistic setting.

Correctly matching feature points in a pair of images is an important preprocessing step for many computer vision applications. In this paper we propose an efficient method for estimating the number of correct matches without explicitly computing them. In addition, our method estimates the region of overlap between the images. To this end, we propose to analyze the set of matches using the spatial order of the features, as projected to the x-axis of the image. The set of features in each image is thus represented by a sequence. This reduces the analysis of the matching problem to the analysis of the permutation between the sequences. Using the Kendall distance metric between permutations and natural assumptions on the distribution of the correct and incorrect matches, we show how to estimate the abovementioned values. We demonstrate the usefulness of our method in two applications: (i) a new halting condition for RANSAC based epipolar geometry estimation methods that considerably reduce the running time, and (ii) discarding spatially unrelated image pairs in the Structure-from-Motion pipeline. Furthermore, our analysis can be used to compute the probability that a given match is correct based on the estimated number of correct matches and the rank of the features within the sequences. Our experiments on a large number of synthetic and real data demonstrate the effectiveness of our method. For example, the running time of the image matching stage in the Structure-from-Motion pipeline may be reduced by about 99% while preserving about 80% of the correctly matched feature points.

Vehicle localization and autonomous navigation consist of accurately positioning a vehicle in a lane. This paper presents topological localization methods by matching the visual cues from the on-board monocular camera images and the preprocessed database. We propose two methods for vehicle localization. The first exploits the 3D information of the sparse visual cues from the database. The relative vehicle rotation and translation are extracted using SOREPP method which is able to handle challenging scenarios with extremely low inlier fractions. The translation length is selected among multiple triangulation candidates. In order to select the best candidate, we suggest a robust soft-threshold estimation method which is not prone to local maxima even when the inliers' fragment is very small. The other method seeks for a refined test vehicle position estimation using a soft-threshold on Sampson distances and Cross-ratio measurements given a current noisy vehicle pose and several near-by database images. This method does not require any 3D knowledge for operation. The main challenge our optimization algorithm addresses is due to the camera and scene configurations. The database images and the test image are all taken from positions which are approximately co-linear. In addition, the scene points visible in all these images are almost co-linear with the camera positions. In this configuration, standard localization algorithms will exhibit difficulties in obtaining accurate results. The novel algorithm we present here is able to overcome this problem. The suggested localization methods are initialized by a rough position estimation thus require a regular vehicle GPS on-board. A monocular camera is required for the topological localization. We evaluate the proposed methods on real data from the KITTI database with the RTK-GPS output as ground truth.

A nonparametric unsupervised method for analyzing changes in complex datasets is proposed. It is based on the mean shift clustering algorithm. Mean shift is used to cluster the old and new datasets and compare the results in a nonparametric manner. Each point from the new dataset naturally belongs to a cluster of points from its dataset. The method is also able to find to which cluster the point belongs in the old dataset and use this information to report qualitative differences between that dataset and the new one. Changes in local cluster distribution are also reported. The report can then be used to try to understand the underlying reasons which caused the changes in the distributions. On the basis of this method, a transductive transfer learning method for automatically labeling data from the new dataset is also proposed. This labeled data is used, in addition to the old training set, to train a classifier better suited to the new dataset. The algorithm has been implemented and tested on simulated and real (a stereo image pair) datasets. Its performance was also compared with several state-of-the-art methods.

Several image registration methods, based on the scaled-invariant feature transform (SIFT) technique, have appeared recently in the remote sensing literature. All of these methods attempt to overcome problems encountered by SIFT in multimodal remotely sensed imagery, in terms of the quality of its feature correspondences. The deterministic method presented in this letter exploits the fact that each SIFT feature is associated with a scale, orientation, and position to perform mode seeking (in transformation space) to eliminate outlying corresponding key points (i.e, features) and improve the overall match obtained. We also present an exhaustive empirical study on a variety of test cases, which demonstrates that our method is highly accurate and rather fast. The algorithm is capable of automatically detecting whether it succeeded or failed.

Algorithms for the estimation of epipolar geometry from a pair of images have been very successful in dealing with challenging wide baseline images. In this paper the problem of scenes with repeated structures is addressed, dealing with the common case where the overlap between the images consists mainly of facades of a building. These facades may contain many repeated structures that can not be matched locally, causing state-of-the-art algorithms to fail. Assuming that the repeated structures lie on a planar surface in an ordered fashion the goal is to match them. Our algorithm first rectifies the images such that the facade is fronto-parallel. It then clusters similar features in each of the two images and matches the clusters. From them a set of hypothesized homographies of the facade is generated, using local groups of features. For each homography the epipole is recovered, yielding a fundamental matrix. For the best solution, it then decides whether the fundamental matrix has been recovered reliably and, if not, returns only the homography. The algorithm has been tested on a large number of challenging image pairs of buildings from the benchmark ZuBuD database, outperforming several state-of-the-art algorithms.

This paper extends to surfaces the multi-scale approach of edge detection on images. The common practice for detecting curves on surfaces requires the user to first select the scale of the features, apply an appropriate smoothing, and detect the edges on the smoothed surface. This approach suffers from two drawbacks. First, it relies on a hidden assumption that all the features on the surface are of the same scale. Second, manual user intervention is required. In this paper, we propose a general framework for automatically detecting the optimal scale for each point on the surface. We smooth the surface at each point according to this optimal scale and run the curve detection algorithm on the resulting surface. Our multi-scale algorithm solves the two disadvantages of the single-scale approach mentioned above. We demonstrate how to realize our approach on two commonly-used special cases: ridges & valleys and relief edges. In each case, the optimal scale is found in accordance with the mathematical definition of the curve.

Several image registration methods, based on the scaled-invariant feature transform (SIFT) technique, have appeared recently in the remote sensing literature. All of these methods attempt to overcome problems encountered by SIFT in multi-modal remotely sensed imagery, in terms of the quality of its feature correspondences. The method presented in this paper performs mode seeking (in transformation space) to eliminate outlying corresponding key-points (i.e., features) and improve the overall match obtained. Preliminary experimental results seem to indicate that our method achieves high accuracy and is rather fast in a variety of test cases.

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 automatic reconstruction of a 3D relief from a line drawing on top of a given base object. Reconstruction is challenging due to four reasons-the sparsity of the strokes, their ambiguity, their large number, and their inter-relations. Our approach is able to reconstruct a model from a complex drawing that consists of many inter-related strokes. Rather than viewing the inter-dependencies as a problem, we show how they can be exploited to automatically generate a good initial interpretation of the line drawing. Then, given a base and an interpretation, we propose an algorithm for reconstructing a consistent surface. The strength of our approach is demonstrated in the reconstruction of archaeological artifacts from drawings. These drawings are highly challenging, since artists created very complex and detailed descriptions of artifacts regardless of any considerations concerning their future use for shape reconstruction.

In this work, we recover the 3D shape of mirrors, sunglasses, and stainless steel implements. A computer monitor displays several images of parallel stripes, each image at a different angle. Reflections of these stripes in a mirroring surface are captured by the camera. For every image point, the direction of the displayed stripes and their reflections in the image are related by a 1D homography matrix, computed with a robust version of the statistically accurate heteroscedastic approach. By focusing on a sparse set of image points for which monitor-image correspondence is computed, the depth and the local shape may be estimated from these homographies. The depth estimation relies on statistically correct minimization and provides accurate, reliable results. Even for the image points where the depth estimation process is inherently unstable, we are able to characterize this instability and develop an algorithm to detect and correct it. After correcting the instability, dense surface recovery of mirroring objects is performed using constrained interpolation, which does not simply interpolate the surface depth values but also uses the locally computed 1D homographies to solve for the depth, the correspondence, and the local surface shape. The method was implemented and the shape of several objects was densely recovered at submillimeter accuracy.

No abstract available.

Edge detection in images has been a fundamental problem in computer vision from its early days. Edge detection on surfaces, on the other hand, has received much less attention. The most common edges on surfaces are ridges and valleys, used for processing range images in computer vision, as well as for non-photo realistic rendering in computer graphics. We propose a new type of edges on surfaces, termed relief edges. Intuitively, the surface can be considered as an unknown smooth manifold, on top of which a local height image is placed. Relief edges are the edges of this local image. We show how to compute these edges from the local differential geometric surface properties, by fitting a local edge model to the surface. We also show how the underlying manifold and the local images can be roughly approximated and exploited in the edge detection process. Last but not least, we demonstrate the application of relief edges to artifact illustration in archaeology.

We present a new method for recovering the 3D shape of a featureless smooth surface from three or more calibrated images illuminated by different light sources (three of them are independent). This method is unique in its ability to handle images taken from unconstrained perspective viewpoints and unconstrained illumination directions. The correspondence between such images is hard to compute and no other known method can handle this problem locally from a small number of images. Our method combines geometric and photometric information in order to recover dense correspondence between the images and accurately computes the 3D shape. Only a single pass starting at one point and local computation are used. This is in contrast to methods that use the occluding contours recovered from many images to initialize and constrain an optimization process. The output of our method can be used to initialize such processes. In the special case of fixed viewpoint, the proposed method becomes a new perspective photometric stereo algorithm. Nevertheless, the introduction of the multiview setup, self-occlusions, and regions close to the occluding boundaries are better handled, and the method is more robust to noise than photometric stereo. Experimental results are presented for simulated and real images.

Augmented reality is concerned with combining real-world data, such as images, with artifcial data. Texture replacement is one such task. It is the process of painting a new texture over an existing textured image patch, such that depth cues are maintained. This paper proposes a general and automatic approach for performing texture replacement, which is based on multiview stereo techniques that produce depth information at every pixel. The use of several images allows us to address the inherent limitation of previous studies, which are constrained to specifc texture classes, such as textureless or near-regular textures. To be able to handle general textures, a modifed dense correspondence estimation algorithm is designed and presented.

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.

The estimation of the epipolar geometry is especially difficult when the putative correspondences include a low percentage of inlier correspondences and/or a large subset of the inliers is consistent with a degenerate configuration of the epipolar geometry that is totally incorrect. This work presents the Balanced Exploration and Exploitation Model Search (BEEM) algorithm that works very well especially for these difficult scenes. The algorithm handles these two problems in a unified manner. It includes the following main features: (1) Balanced use of three search techniques: global random exploration, local exploration near the current best solution and local exploitation to improve the quality of the model. (2) Exploits available prior information to accelerate the search process. (3) Uses the best found model to guide the search process, escape from degenerate models and to define an efficient stopping criterion. (4) Presents a simple and efficient method to estimate the epipolar geometry from two SIFT correspondences. (5) Uses the locality-sensitive hashing (LSH) approximate nearest neighbor algorithm for fast putative correspondences generation. The resulting algorithm when tested on real images with or without degenerate configurations gives quality estimations and achieves significant speedups compared to the state of the art algorithms.

Curves on objects can convey the inherent features of the shape. This paper defines a new class of view-independent curves, denoteddemarcating curves.In a nutshell, demarcating curves are the loci of the "strongest" inflections on the surface. Due to their appealing capabilities to extract and emphasize 3D textures, they are applied to artifact illustration in archaeology, where they can serve as a worthy alternative to the expensive, time-consuming, and biased manual depiction currently used.

We present a method for the recovery of partially occluded 3-D geometric primitives from range images which might also include nonprimitive objects. The method uses a technique for estimating the principal curvatures and Darboux frame from range images. After estimating the principal curvatures and the Darboux frames from the entire scene, a search for the known patterns of these features in geometric primitives is performed. If a specific pattern is identified, then the presence of the corresponding primitive is confirmed by using these local features. The features are also used to recover the primitive's characteristics. The suggested application is very efficient since it combines the segmentation, classification, and fitting processes, which are part of any recovery process, in a single process, which advances monotonously through the recovery procedure. We view the problem as a robust statistics problem, and we therefore use techniques from that field. A mean-shift-based algorithm is used for the robust estimation of shape parameters, such as recognizing which types of shapes in the scene exist and, after that, full recovery of planes, spheres, and cylinders. A random-sample-consensus-based algorithm is used for robust model estimation for the more complex primitives, such as cones and tori. As a result of these algorithms, a set of proposed primitives is found. This set contains superfluous models which cannot be detected at this stage. To deal with this problem, a minimum-description-length method has been developed, which selects a subset of models that best describes the scene. The method has been tested on series of real complex cluttered scenes, yielding accurate and robust recoveries of primitives.

In this work we recover the 3D shape of mirroring objects such as mirrors, sunglasses, and stainless steel objects. A computer monitor displays several images of parallel stripes, each image at a different angle. Reflections of these stripes in a mirroring surface are captured by the camera. For every image point, the directions of the displayed stripes and their reflections in the image are related by a 1D homography which can be computed robustly and using the statistically accurate heteroscedastic model, without monitor-image correspondence, which is generally required by other techniques. Focusing on a small set of image points for which monitor-image correspondence is computed, the depth and the local shape may be calculated relying on this homography. This is done by an optimization process which is related to the one proposed by Savarese, Chen and Perona, but is different and more stable. Then dense surface recovery is performed using constrained interpolation, which does not simply interpolate the surface depth values, but rather solves for the depth, the correspondence, and the local surface shape, simultaneously at each interpolated point. Consistency with the ID homography is thus required. The proposed method as well as the method described in [A. Ripsman and M. Jenkin, IEEE Int. Symposium on Computational Intelligence (2001)] are inherently unstable on a small part of the surface. We propose a method to detect these instabilities and correct them. The method was implemented and the shapes of a mirror, sunglasses, and a stainless steel ashtray were recovered at sub-millimeter accuracy.

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.

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

Image matching is an essential task in many computer vision applications. It is obvious that thorough utilization of all available information is critical for the success of matching algorithms. However most popular matching methods do not incorporate effectively photometric data. Some algorithms are based on geometric, color invariant features, thus completely neglecting available photometric information. Others assume that color does not differ significantly in the two images; that assumption may be wrong when the images are not taken at the same time, for example when a recently taken image is compared with a database. This paper introduces a method for using color information in image matching tasks. Initially the images are segmented using an off-the-shelf segmentation process (EDISON). No assumptions are made on the quality of the segmentation. Then the algorithm employs a model for natural illumination change to define the probability of two segments to originate from the same surface. When additional information is supplied (for example suspected corresponding point features in both images), the probabilities are updated. We show that the probabilities can easily be utilized in any existing image matching system. We propose a technique to make use of them in a SIFT-based algorithm. The technique’s capabilities are demonstrated on real images, where it causes a significant improvement in comparison with the original SIFT results in the percentage of correct matches found.

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.

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

Abstract The triangle‐to‐triangle intersection test is a basic component of all collision detection data structures and algorithms. This paper presents a fast method for testing whether two triangles embedded in three dimensions intersect. Our technique solves the basic sets of linear equations associated with the problem and exploits the strong relations between these sets to speed up their solution. Moreover, unlike previous techniques, with very little additional cost, the exact intersection coordinates can be determined. Finally, our technique uses general principles that can be applied to similar problems such as rectangle‐to‐rectangle intersection tests, and generally to problems where several equation sets are strongly related. We show that our algorithm saves about 20% of the mathematical operations used by the best previous triangle‐to‐triangle intersection algorithm. Our experiments also show that it runs 18.9% faster than the fastest previous algorithm on average for typical scenarios of collision detection (on Pentium 4). Copyright © 2006 John Wiley & Sons, Ltd.

The problem of automatic robust estimation of the epipolar geometry in cases where the correspondences are contaminated with a high percentage of outliers is addressed. This situation often occurs when the images have undergone a significant deformation, either due to large rotation or wide baseline of the cameras. An accelerated algorithm for the identification of the false matches between the views is presented. The algorithm generates a set of weak motion models (WMMs). Each WMM roughly approximates the motion of correspondences from one image to the other. The algorithm represents the distribution of the median of the geometric distances of a correspondence to the WMMs as a mixture model of outlier correspondences and inlier correspondences. The algorithm generates an outlier correspondence sample from the data. This sample is used to estimate the outlier rate and to estimate the outlier pdf. Using these two pdfs the probability that each correspondence is an inlier is estimated. These probabilities enable to guide the sampling. In the RANSAC process this guided sampling accelerates the search process. The resulting algorithm when tested on real images achieves a speedup of between one or two orders of magnitude.

Robust regression techniques are used today in many computer vision algorithms. Chen and Meer recently presented a new robust regression technique named the projection based M-estimator. Unlike other methods in the RANSAC family of techniques, where performance depends on a user supplied scale parameter, in the pbM-estimator technique this scale parameter is estimated automatically from the data using kernel smoothing density estimation. In this work we improve the performance of the pbM-estimator by changing its cost function. Replacing the cost function of the pbM-estimator with the changed one yields the modified pbM-estimator. The cost function of the modified pbM-estimator is more stable relative to the scale parameter and is also a better classifier. Thus we get a more robust and effective technique. A new general method to estimate the runtime of robust regression algorithms is proposed. Using it we show, that the modified pbM-estimator runs 2 -3 times faster than the pbM-estimator. Experimental results of fundamental matrix estimation are presented demonstrating the correctness of the proposed analysis method and the advantages of the modified pbM-estimator.

Feature space analysis is the main module in many computer vision tasks. The most popular technique, k-means clustering, however, has two inherent limitations: the clusters are constrained to be spherically symmetric and their number has to be known a priori. In nonparametric clustering methods, like the one based on mean shift, these limitations are eliminated but the amount of computation becomes prohibitively large as the dimension of the space increases. We exploit a recently proposed approximation technique, locality-sensitive hashing (LSH), to reduce the computational complexity of adaptive mean shift. In our implementation of LSH the optimal parameters of the data structure are determined by a pilot learning procedure, and the partitions are data driven. As an application, the performance of mode and k-means based textons are compared in a texture classification study.

The introduction of the joint image manifold allows to treat the problem of recovering camera motion and epipolar geometry as the problem of fitting a manifold to the data measured in a stereo pair. The manifold has a singularity and boundary, therefore care must be taken when fitting it. This paper reviews the notion of joint image manifold, and how previous motion recovery methods can be viewed in its context, and then offers a new fitting method, which improves upon previous results, especially when the extent of the data and/or the motion are small.

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.

Principal curvatures and the local Darboux frame are natural tools to be used during processes which involve extraction of geometric properties from three-dimensional (3-D) range data. As second-order features their estimations are highly sensitive to noise and therefore, until recent years, it was almost impractical to extract reliable results from real 3-D data. Since the use of more accurate 3-D range imaging equipment has become more popular, as well as the use of polyhedral meshes to approximate surfaces, evaluation of existing algorithms for curvature estimation is again relevant. The work presented here, makes some subtle but very important modifications to two such algorithms, originally suggested by Taubin (1995) and Chen and Schmitt (1992). The algorithms have been adjusted to deal with real discrete noisy range data, given as a cloud of sampled points, lying on surfaces of free-form objects. The results of this linear time (and space) complexity implementation were evaluated in a series of tests on synthetic and real input. We also present one of many possible uses for these extracted features in an efficient and robust application for the recovery of 3-D geometric primitives from range data of complex scenes. The application combines the segmentation, classification and fitting processes in a single process which advances monotonously through the recovery procedure. It is also very robust and does not use any least-squares fittings. The conclusion of this study is that with current scanning technology and the algorithms presented here, reliable estimates of the principal curvatures and Darboux frame can be extracted from real data and used in a large variety of tasks.

This paper discusses the problem of inserting three-dimensional models into a single image. The main focus of the paper is on the accurate recovery of the camera's parameters, so that 3D models can be inserted in the "correct" position and orientation. An important aspect of this paper is a theoretical and an experimental analysis of the errors. We also implemented a system which "plants" virtual 3D objects in the image, and tested the system on many indoor augmented reality scenes. Our analysis and experiments have shown that errors in the placement of the objects are un-noticeable.

This paper deals with the problem of robot localization from noisy landmark bearings measured by the robot. We present a new localization method which is based on linear constraints, one due to each bearing measurement. This linear system can be solved at low computational cost but yields not very accurate results. Therefore, we transform the system to an equivalent linear system which yields virtually optimal results at a small fraction of the cost of a nonlinear optimization method, which usually achieves the optimal result. Experimental results showing the quality of the results and the low computational cost are presented.

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.

Deals with the problem of robot localization from noisy landmark bearings measured by the robot. We present a localization method which is based on linear constraints, one due to each bearing measurement. This linear system can be solved at low computational cost but yields not very accurate results. We therefore transform the system to an equivalent linear system which yields virtually optimal results at a small fraction of the cost of a nonlinear optimization method which usually achieves the optimal result. Experimental results showing the quality of the results and the low computational cost are presented.

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.

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.

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.

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.

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.

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.

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 computing the aspect graph of a polyhedral object observed by an orthographic camera with limited spatial resolution, such that two image points separated by a distance smaller than a preset threshold cannot be resolved. Under this model, views that would differ under normal orthographic projection may become equivalent, while "accidental" views may occur over finite areas of the view space. We present a catalogue of visual events for polyhedral objects and give an algorithm for computing the aspect graph and enumerating all qualitatively different aspects. The algorithm has been fully implemented and results are presented.

Efficient and robust model-based recognition systems need to be able to estimate reliably and quickly the possible locations of other model features in the image when a match of several model points to image points is given. Errors in the sensed data lead to uncertainty in the computed pose of the object which in turn lead to uncertainty in those positions. We present a very fast and accurate method for estimating these uncertainty regions. Our basic method deals with an initial match of three points and is extended using statistical methods to estimate the uncertainty region using initial matches of any size.

A probabilistic 3D object recognition algorithm is presented. In order to guide the recognition process the probability that match hypotheses between image features and model features are correct is computed. A model is developed which uses the probabilistic peaking effect of measured angles and ratios of lengths by tracing iso angle and iso ratio curves on the viewing sphere. The model also accounts for various types of uncertainty in the input such as incomplete and inexact edge detection. For each match hypothesis the pose of the object and the pose uncertainty which is due to the uncertainty in vertex position are recovered. This is used to find sets of hypotheses which reinforce each other by matching features of the same object with compatible uncertainty subsets. A probabalistic expression is used to rank these hypothesis sets. The hypothesis sets with the highest rank are output. The algorithm has been fully implemented, and tested on real images.>

Following Sugihara, we represent the geometric constraints imposed by the line-drawing of a polyhedron as a set of linear equalities and inequalities. Unlike him, we explicitly take into account the uncertainty in vertex position. This allows us to circumvent the superstrictness of the constraints without deleting any of them. For a given error bound, deciding whether a line-drawing is the correct projection of a polyhedron is reduced to linear programming, and 3D shape recovery is reduced to optimization under linear constraints. Our method can be used for recovering the shape of polyhedral objects whose reflectance can be modelled accurately. We have implemented if for the Lambertian model and the Lambertian model with interreflections. We present results obtained using real images.>

Following the work of K. Sugihara (1984), the authors represent the geometric constraints imposed by the line-drawing of a polyhedron as a set of linear equalities and inequalities. They, however, explicitly take into account the uncertainty in the vertex position. This allows the circumvention of the superstrictness of the constraints without deleting any constraints. For a given error bound, the condition whether a line-drawing is the correct projection of a polyhedron is reduced to linear programing, and the 3D shape recovery is reduced to optimization under linear constraints. The approach has been implemented, and examples are presented.>

Planning is defined as the problem of synthesizing a desired behavior from given basic operations, and learning is defined as the dual problem of analyzing a given behavior to determine the unknown basic operations. Algorithms for solving these problems in the context of invertible operations on finite-state environments are developed. In addition to their obvious artificial intelligence applications, the algorithms can efficiently find the shortest way to solve Rubik's cube, test ping-pong protocols, and solve systems of equations over permutation groups.>