Neuromimetic algorithms, such as the HMAX algorithm, have been very successful in image classification tasks. However, current implementations of these algorithms do not scale well to large datasets. Often, target-specific features or patches are “learned” ahead of time and then correlated with test images during feature extraction. In this paper, we develop a novel method for selecting a single set of universal features that enables classification across a broad range of image classes. Our method trains multiple Random Forest classifiers using a large dictionary of features and then combines them using a majority voting scheme. This enables the selection of the most discriminative patches based on feature importance measures. Experiments demonstrate the viability of this method using HMAX features as well as the tradeoff between the number of universal features, classification performance, and processing time.

Contours are a powerful cue for semantic image understanding. Objects and parts of objects in the image are delineated from their surrounding by closed contours which make up their boundary. In this paper we introduce a new bottom-up visual operator to capture the concept of closed contours, which we call the `Torque' operator. Its computation is inspired by the mechanical definition of torque or moment of force, and applied to image edges. The torque operator takes as input edges and computes over regions of different size a measure of how well the edges are aligned to form a closed, convex contour. We explore fundamental properties of this measure and demonstrate that it can be made a useful tool for visual attention, segmentation, and boundary edge detection by verifying its benefits on these applications.

Contour is an important cue for object recognition. In this paper, built upon the concept of torque in image space, we propose a new contour-related feature to detect and describe local contour information in images. There are two components for our proposed feature: One is a contour patch detector for detecting image patches with interesting information of object contour, which we call the Maximal/Minimal Torque Patch (MTP) detector. The other is a contour patch descriptor for characterizing a contour patch by sampling the torque values, which we call the Multi-scale Torque (MST) descriptor. Experiments for object recognition on the Caltech-101 dataset showed that the proposed contour feature outperforms other contour-related features and is on a par with many other types of features. When combing our descriptor with the complementary SIFT descriptor, impressive recognition results are observed.

Our work addresses pose estimation in a distributed camera framework. We examine how processing cameras can best reach a consensus about the pose of an object when they are each given a model of the object, defined by a set of point coordinates in the object frame of reference. The cameras can only see a subset of the object feature points in the midst of background clutter points, not knowing which image points match with which object points, nor which points are object points or background points. The cameras individually recover a prediction of the object's pose using their knowledge of the model, and then exchange information with their neighbors, performing consensus updates locally to obtain a single estimate consistent across all cameras, without requiring a common centralized processor. Our main contributions are: 1) we present a novel algorithm performing consensus updates in 3-D world coordinates penalized by a 3-D model, and 2) we perform a thorough comparison of our method with other current consensus methods. Our method is consistently the most accurate, and we confirm that the existing consensus method based upon calculating the Karcher mean of rotations is also reliable and fast. Experiments on simulated and real imagery are reported.

Training a classifier for object category recognition using images on the Internet is an attractive approach due to its scalability. However, a big challenge in this approach is that it is difficult to automatically obtain sets of negative samples that are guaranteed to be free of positive samples. In this paper we propose to address this challenge with a Support Vector Data Description (SVDD) classifier. An SVDD classifier does not need negative images in training. It computes a hypersphere around the potentially good images in the feature space and uses this boundary to distinguish images of target visual category from outliers. Evaluation on standard test sets shows that we are able to achieve competitive classification performance using the contaminated training images from the Internet without the need for large datasets of negative examples.

Compared to typical scanners, handheld cameras offer convenient, flexible, portable, and non-contact image capture, which enables many new applications and breathes new life into existing ones. However, camera-captured documents may suffer from distortions caused by non-planar document shape and perspective projection, which lead to failure of current OCR technologies. We present a geometric rectification framework for restoring the frontal-flat view of a document from a single camera-captured image. Our approach estimates 3D document shape from texture flow information obtained directly from the image without requiring additional 3D/metric data or prior camera calibration. Our framework provides a unified solution for both planar and curved documents and can be applied in many, especially mobile, camera-based document analysis applications. Experiments show that our method produces results that are significantly more OCR compatible than the original images.

Local part-based human detectors are capable of handling partial occlusions efficiently and modeling shape articulations flexibly, while global shape template-based human detectors are capable of detecting and segmenting human shapes simultaneously. We describe a Bayesian approach to human detection and segmentation combining local part-based and global template-based schemes. The approach relies on the key ideas of matching a part-template tree to images hierarchically to generate a reliable set of detection hypotheses and optimizing it under a Bayesian MAP framework through global likelihood re-evaluation and fine occlusion analysis. In addition to detection, our approach is able to obtain human shapes and poses simultaneously. We applied the approach to human detection and segmentation in crowded scenes with and without background subtraction. Experimental results show that our approach achieves good performance on images and video sequences with severe occlusion.

An interactive human segmentation approach is described. Given regions of interest provided by users, the approach iteratively estimates segmentation via a generalized EM algorithm. Specifically, it encodes both spatial and color information in a nonparametric kernel density estimator, and incorporates local MRF constraints and global pose inferences to propagate beliefs over image space iteratively to determine a coherent segmentation. This ensures the segmented humans resemble the shapes of human poses. Additionally, a layered occlusion model and a probabilistic occlusion reasoning method are proposed to handle segmentation of multiple humans in occlusion. The approach is tested on a wide variety of images containing single or multiple occluded humans, and the segmentation performance is evaluated quantitatively.

Compared to scanned images, document pictures captured by camera can suffer from distortions due to perspective and page warping. It is necessary to restore a frontal planar view of the page before other OCR techniques can be applied. In this paper we describe a novel approach for flattening a curved document in a single picture captured by an uncalibrated camera. To our knowledge this is the first reported method able to process general curved documents in images without camera calibration. We propose to model the page surface by a developable surface, and exploit the properties (parallelism and equal line spacing) of the printed textual content on the page to recover the surface shape. Experiments show that the output images are much more OCR friendly than the original ones. While our method is designed to work with any general developable surfaces, it can be adapted for typical special cases including planar pages, scans of thick books, and opened books.

We present an object recognition algorithm that uses model and image line features to locate complex objects in high clutter environments. Finding correspondences between model and image features is the main challenge in most object recognition systems. In our approach, corresponding line features are determined by a three-stage process. The first stage generates a large number of approximate pose hypotheses from correspondences of one or two lines in the model and image. Next, the pose hypotheses from the previous stage are quickly ranked by comparing local image neighborhoods to the corresponding local model neighborhoods. Fast nearest neighbor and range search algorithms are used to implement a distance measure that is unaffected by clutter and partial occlusion. The ranking of pose hypotheses is invariant to changes in image scale, orientation, and partially invariant to affine distortion. Finally, a robust pose estimation algorithm is applied for refinement and verification, starting from the few best approximate poses produced by the previous stages. Experiments on real images demonstrate robust recognition of partially occluded objects in very high clutter environments

This paper describes the development of a new document ranking system based on layout similarity. The user has a need represented by a set of "wanted" documents, and the system ranks documents in the collection according to this need. Rather than performing complete document analysis, the system extracts text lines, and models layouts as relationships between pairs of these lines. This paper explores three novel feature sets to support scoring in large document collections. First, pairs of lines are used to form quadrilaterals, which are represented by their turning functions. A non-Euclidean distance is used to measure similarity. Second, the quadrilaterals are represented by 5D Euclidean vectors, and third, each line is represented by a 5D Euclidean vector. We compare the classification performance and computation speed of these three feature sets using a large database of diverse documents including forms, academic papers and handwritten pages in English and Arabic. The approach using quadrilaterals and turning functions produces slightly better results, but the approach using vectors to represent text lines is much faster for large document databases.

We present a new robust line matching algorithm for solving the model-to-image registration problem. Given a model consisting of 3D lines and a cluttered perspective image of this model, the algorithm simultaneously estimates the pose of the model and the correspondences of model lines to image lines. The algorithm combines softassign for determining correspondences and POSIT for determining pose. Integrating these algorithms into a deterministic annealing procedure allows the correspondence and pose to evolve from initially uncertain values to a joint local optimum. This research extends to line features the SoftPOSIT algorithm proposed recently for point features. Lines detected in images are typically more stable than points and are less likely to be produced by clutter and noise, especially in man-made environments. Experiments on synthetic and real imagery with high levels of clutter, occlusion, and noise demonstrate the robustness of the algorithm.

A system for tracking humans and detecting human-object interactions in indoor environments is described. A combination of correlogram and histogram information is used to model object and human color distributions. Humans and objects are detected using a background subtraction algorithm. The models are built on the fly and used to track them on a frame by frame basis. The system is able to detect when people merge into groups and segment them during occlusion. Identities are preserved during the sequence, even if a person enters and leaves the scene. The system is also able to detect when a person deposits or removes an object from the scene. In the first case the models are used to track the object retroactively in time. In the second case the objects are tracked for the rest of the sequence. Experimental results using indoor video sequences are presented.

Mean-shift analysis is a general nonparametric clustering technique based on density estimation for the analysis of complex feature spaces. The algorithm consists of a simple iterative procedure that shifts each of the feature points to the nearest stationary point along the gradient directions of the estimated density function. It has been successfully applied to many applications such as segmentation and tracking. However, despite its promising performance, there are applications for which the algorithm converges too slowly to be practical. We propose and implement an improved version of the mean-shift algorithm using quasiNewton methods to achieve higher convergence rates. Another benefit of our algorithm is its ability to achieve clustering even for very complex and irregular feature-space topography. Experimental results demonstrate the efficiency and effectiveness of our algorithm.

Creating high quality virtual spatial audio over headphones requires real-time head tracking, personalized head-related transfer functions (HRTFs) and customized room response models. While there are expensive solutions to address these issues based on costly head trackers, measured personalized HRTFs and room responses, these are not suitable for widespread or easy deployment and use. We report on the development of a system that uses computer vision to produce customizable models for both the HRTF and the room response, and to achieve head-tracking. The system uses relatively inexpensive cameras and widely available personal computers. Computer-vision based anthropometric measurements of the head, torso, and the external ears are used for HRTF customization. For low-frequency HRTF customization we employ a simple head-and-torso model developed recently [V. R. Algazi et al., 2002]. For high frequency customization we employ measured pinna characteristics as an index into a database of HRTFs [D. N. Zotkin et al., 2002]. For head tracking we employ an online implementation of the POSIT algorithm [D. DeMenthon and L. Davis, 1995] along with active markers to compute head pose in real-time. The system provides an enhanced virtual listening experience at low cost.

This paper describes a novel methodology for implementing video search functions such as retrieval of near-duplicate videos and recognition of actions in surveillance video. Videos are divided into half-second clips whose stacked frames produce 3D space-time volumes of pixels. Pixel regions with consistent color and motion properties are extracted from these 3D volumes by a threshold-free hierarchical space-time segmentation technique. Each region is then described by a high-dimensional point whose components represent the position, motion and, when possible, color of the region. In the indexing phase for a video database, these points are assigned labels that specify their video clip of origin. All the labeled points for all the clips are stored into a single binary tree for e#cient k-nearest neighbor retrieval. The retrieval phase uses video segments as queries. Half-second clips of these queries are again segmented to produce sets of points, and for each point the labels of its nearest neighbors are retrieved. The labels that receive the largest numbers of votes correspond to the database clips that are the most similar to the query video segment. We illustrate this approach for video indexing and retrieval and for action recognition. First, we describe retrieval experiments for dynamic logos, and for video queries that di#er from the indexed broadcasts by the addition of large overlays. Then we describe experiments in which o#ce actions (such as pulling and closing drawers, taking and storing items, picking up and putting down a phone) are recognized. Color information is ignored to insure independence to people's appearance. One of the distinct advantages of using this approach for action recognition is that there is no need for detection or recognition of body pa...

We propose a new hybrid unsupervised/supervised learning scheme that integrates independent component analysis (ICA) with the support vector machine (SVM) approach and apply this new learning scheme to the face detection problem. In low-level feature extraction, ICA produces independent image bases that emphasize edge information in the image data. In high-level classification, SVM classifies the ICA features as a face or non-faces. Our experimental results show that by using ICA features we obtain a larger margin of separation and fewer support vectors than by training SVM directly on the image data. This indicates better generalization performance, which is verified in our experiments.

We describe a method for learning statistical models of images using a second-order hidden Markov mesh model. First, an image can be segmented in a way that best matches its statistical model by an approach related to the dynamic programming used for segmenting Markov chains. Next, given an image segmentation, a statistical model (3D state transition matrix and observation distributions within states) can be estimated. These two steps are repeated until convergence to provide both a segmentation and a statistical model of the image. We propose a statistical distance measure between images based on the similarity of their statistical models, for classification and retrieval tasks.

The paper describes two techniques for detecting dynamic events using the motion vectors obtained from the MPEG video encoding. In the first technique, feature vectors from motion information form a high dimensional curve for a video clip, and curve simplification allows us to browse the clip along portions where interesting events are likely to happen. In the second technique, the camera motion, pan, tilt, and zoom are computed from the motion vectors, and the residual vectors which are not explained by the camera motion are regarded as generated by moving blobs. Events are detected from these moving blobs.

In this paper we present a novel way of creating mosaics from an MPEG video sequence. Two original aspects of our work are that (1) we explicitly compute camera motion between frames and (2) we deduce the camera motion directly from the motion vectors encoded in the MPEG video stream. This enables us to create mosaics more simply and quickly than with other methods. 1 Introduction The mass digitization of video has elevated automated storage and retrieval to a grand challenge. Video sequences can store a vast amount of useful information, but redundancy between individual frames is a problem when analyzing, browsing, or searching video. Presenting the video sequence in a compact manner is a difficult challenge because eliminating redundancy could also eliminate content. The selection of static keyframes to represent a shot sequence is commonly used for indexing as well as for presentation of retrieval results. This technique is insufficient for revealing much of the content in a vide...

Automated classification of digital video is emerging as an important piece of the puzzle in the design of content management systems for digital libraries. The ability to classify videos into various genres such as sports, news, movies, or documentaries increases the efficiency of indexing, browsing, and retrieval of video in large databases. In this paper, we present an automated technique for identifying slow-motion replays directly from the compressed domain of MPEG video. It uses the macroblock, motion, and bit-rate information that is readily accessible from MPEG video with very minimal decoding, leading to enormous gains in processing speeds.

A video sequence can be represented as a trajectory curve in a high dimensional feature space. This video curve can be analyzed by tools similar to those developed for planar curves. In particular, the classic binary curve splitting algorithm has been found to be a useful tool for video analysis. With a splitting condition that checks the dimensionality of the curve segment being split, the video curve can be recursively simplified and represented as a tree structure, and the frames that are found to be junctions between curve segments at different levels of the tree can be used as keyframes to summarize the video sequences at different levels of detail. These keyframes can be combined in various spatial and temporal configurations for browsing purposes. We describe a simple video player that displays the keyframes sequentially and lets the user change the summarization level on the fly with a slider. We also describe an approach to automatically selecting a summarization level that provides a concise and representative set of keyframes.

Digital Elevation Models are considered in relation to their use in a parallel computing environment. In particular, the problem of approximating terrain surface through a Triangulated Irregular Network (TIN) is analysed. A parallel algorithm is presented that builds a TIN based on Delaunay triangulation, by selecting a sparse subset of points from a dense regular grid of sampled data. An implementation of the algorithm on a CM-2 is described and experimental results are shown.

A new method is presented for the computation of the position and orientation of a camera with respect to a known object, using four or more coplanar feature points. Starting under the scaled orthographic projection approximation, this method iteratively refines up to two different pose estimates, and provides associated quality measures. When the distance of the object to the camera is large, or when the accuracy of the feature point extraction is low, both pose estimates are plausible.>

Abstract We propose an algorithm for solving region‐to‐region visibility problems on digital terrain models using data parallel machines. Since global communication is the bottleneck in this kind of algorithm, the algorithm we propose focuses on the reduction of global communication. The algorithm analyses a strip of the source region at a time and sweeps through the source strip by strip. At most four sweeps are needed for the analysis. By exploring the coherence properties in the processor structure, global communication is minimized and complexity is substantially improved. Furthermore, all global write operations are exclusive and concurrency in global read operations is minimized. Since the problem size is usually large, we also designed rules of decomposition to efficiently handle the cases where the required number of processors is greater than available. The algorithm has been implemented on a Connection Machine CM‐2, and results of computational experiments are presented.

A method for solving visibility-based terrain path planning problems using massively parallel hypercube machines is proposed. A typical example is to find a path that is hidden from moving adversaries. This kind of problem can be generalized as a time-varying constrained path planning problem and is proven to be computationally hard. An approximation based on both temporal and, spatial sampling is proposed. Since a 2-D grid cell representation of terrain can be embedded into a hypercube with extra links for fast communication, the method can be very efficient when implemented on hypercube machines. The time complexity is in general O(T*E*log N) using O(N) processors, where T is the number of temporal samples, E is the number of adversary agents, and N is the number of grid cells on the terrain. It is also shown that the method can be applied to several realistic problems with a variety of path optimizations. All algorithms have been implemented on the Connection Machine CM-2 and results of experiments are presented.>

The trajectory planning problem for mobile robots in unknown dynamic workspaces is posed as an optimization problem with optimality criteria the probability of not colliding with the obstacles and the probability of accessing an operational position with respect to a moving target object. The authors study a formal computational framework in which such probabilities can be derived for elementary robot displacements.>

The authors describe a computational framework in which a probabilistic method for noisy sensor-based robotic navigation in dynamic environments can be devised. The aim of the method is to generate an optimal trajectory by considering as optimality criteria the probability of not colliding with the obstacles and the probability of accessing an operational position with respect to a moving target object. A formal framework in which the probability of collision associated with an elementary robot displacement can be calculated is discussed. Estimates on the obstacle kinematic parameters and measures of confidence on these estimates are used to produce the probability of collision associated with any robot displacement. The probability of collision is derived in two steps: a stochastic model is defined in the kinematic state space of the obstacles and collision events are given a simple geometric characterization in this state space.>

In this paper, we propose a method for solving visibility-based terrain path planning problems for groups of vehicles using data parallel machines. The discussion focuses on path planning for two groups of vehicles so that they move in a bounding overwatch manner. Furthermore, the planned paths for the vehicles themselves are subject to intervisibility constraints, configuration constraints, and different terrain traversabilities due to variations in terrain type and slope. A spatial-temporal sampling approach is adopted to discretize the solution space and facilitate fast computation on a data parallel machine. One of the key computations in the planning is the region-to-region visibility analysis, which is computationally expensive but essential to the choice of subgoals to carry out reconnaissance activities. A parallel algorithm for this analysis is developed. By reducing the communication complexity, our algorithm achieves much faster running time than traditional methods. The algorithms are implemented on a Connection Machine CM-2, and the experimental results show that the planning system effectively generates good paths.

Model-based pose estimation techniques that match image and model triangles require large numbers of matching operations in real-world applications. The authors show that by using approximations to perspective, 2D lookup tables can be built for each of the triangles of the models. An approximation called 'weak perspective' has been applied previously to this problem; the authors consider two other perspective approximations: paraperspective and orthoperspective. These approximations produce lower errors for off-center image features than weak perspective.>

An exact method for computing the position of a triangle in space from its image is presented. Also presented is an approximate method based on orthoperspective, an approximation of perspective which produces lower errors for off-center triangle images than scaled orthographic projection. A comparison is made of exact and approximate solutions for the triangle pose. This comparison gives the relative combinations of image and triangle characteristics which are likely to generate the largest errors. Model-based pose estimation techniques which match image and model triangles require large numbers of matching operations in real-world applications. It is shown that the approximate model can be used to build lookup tables for each of the triangles of a model and that they speed up the estimation of an object pose.>

A method is presented for reconstructing a 3-D road from a single image. It finds the images of opposite points of the road. Opposite points are points which face each other on the opposite sides of the road; the images of these points are called matching points. For points chosen from one side of the road image, the algorithm finds all the matching point candidates on the other side, based on local properties of a road. However, these solutions do not necessarily satisfy the global properties of a typical road. A dynamic programming algorithm is applied to reject the candidates which do not fit the global road. A benchmark using synthetic roads is described. It shows that the roads reconstructed by the proposed method match the actual roads better than those reconstructed by two other road reconstruction algorithms. Experiments with 50 road images taken by the autonomous land vehicle (ALV) showed that the method is robust with real-world data and that the reconstructions are fairly consistent with road profiles obtained by fusion between range images and video images.>

A range scanner which calculates ranges by triangulation between the incident angles of laser stripes and the positions of their images on a camera sensor was developed for robotic applications. It uses a solid-state image sensor called Optic RAM instead of a CCD sensor. This sensor chip has three desirable characteristics for the position detection of laser stripes in images: it thresholds the image, detecting only the brighter stripes in binary form; it is an image memory; and pixel values can be addressed randomly in the image. Thus, the design does not require an A/D converter or a frame buffer and is consequently inexpensive. For improved performance, only the image region next to the previous stripe location is searched, and a 64-KB lookup table stored in RAM is indexed by incident laser angles and stripe addresses to output range data. A 128*256 range image is produced in about 20 s. This is reasonably fast considering that this process requires analyzing 256 images. The speed bottleneck is the low sensitivity of the optic RAM chip, which requires a long exposure time per frame (60 ms), corresponding to half the standard video frame rate. Simple calibration methods using planar patterns of parallel lines are presented.>

Creating three-dimensional (3-D) descriptions of road boundaries from single 2-D images of segmented road is a central problem for the autonomous land vehicle (ALV) road-following task. It is shown how heuristic simplifying assumptions can be avoided by using actively scanned laser range data to determine the 3-D space location of features in a 2-D image. An epipolar-plane approach that is commonly used to restrict search spaces in stereo correspondence problems is used to combine data gathered from the ALV's video camera and an ERIM laser range scanner for accurate 3-D descriptions of roads. In addition, various heuristic inverse perspective algorithms are compared with each other and with the video/range scanner fusion approach in terms of accuracy, failure situations, and estimated computational speed. The simplest of these is the flat-earth algorithm where the assumption is made that the vehicle is at all times resting in a level attitude on an infinite flat plane; image points were projected onto this plane. A second approach, the hill-and-dale algorithm, permits the plane's elevation to vary such that image pairs of left and right road edge points define a road of constant width. The zero-bank algorithm imposes a constant-road-width constraint on heuristically extracted image pairs of road edge points and the algorithm seeks image pairs of edge points that correspond to true 'crossword' road edges on curving roads. Graphical output describing the performance of the various algorithms on real-world scenes is presented and discussed.>

A method is presented for reconstructing the 3-D geometry of a road from a single image of the road. This problem has an infinity of solutions unless restrictive hypotheses about geometric characteristics of this road are assumed. The road is modeled as a space ribbon defined by a spine (centerline) and generators (cross-segments) which are horizontal line segments cutting the spine at their midpoint at a normal angle. Properties of two neighboring generators of such a ribbon are examined; if a generator is known, a neighboring generator is completely defined if one of its ends is known. The proposed method uses this property to reconstruct the visible part of the world road, by iteratively finding a series of generators. This method is tested against a simple method which assumes that the ground is flat ("Flat Earth assumption"), and against another method which uses vanishing points.