Composed image retrieval (CIR) is the task of retrieving a target image specified by a query image and a relative text that describes a semantic modification to the query image. Existing methods in CIR struggle to accurately represent the image and the text modification, resulting in subpar performance. To address this limitation, we introduce a CIR framework, ConText-CIR, trained with a Text Concept-Consistency loss that encourages the representations of noun phrases in the text modification to better attend to the relevant parts of the query image. To support training with this loss function, we also propose a synthetic data generation pipeline that creates training data from existing CIR datasets or unlabeled images. We show that these components together enable stronger performance on CIR tasks, setting a new state-of-the-art in composed image retrieval in both the supervised and zero-shot settings on multiple benchmark datasets, including CIRR and CIRCO. Source code, model checkpoints, and our new datasets are available at https://github.com/mvrl/ConText-CIR.

Massive-scale pretraining has made vision-language models increasingly popular for image-to-image and text-to-image retrieval across a broad collection of domains. However, these models do not perform well when used for challenging retrieval tasks, such as instance retrieval in very large-scale image collections. Recent work has shown that linear transformations of VLM features trained for instance retrieval can improve performance by emphasizing subspaces that relate to the domain of interest. In this paper, we explore a more extreme version of this specialization by learning to map a given query to a query-specific feature space transformation. Because this transformation is linear, it can be applied with minimal computational cost to millions of image embeddings, making it effective for large-scale retrieval or re-ranking. Results show that this method consistently outperforms state-of-the-art alternatives, including those that require many orders of magnitude more computation at query time.

Large scale field-phenotyping approaches have the potential to solve important questions about the relationship of plant genotype to plant phenotype. Computational approaches to measuring the phenotype (the observable plant features) are required to address the problem at a large scale, but machine learning approaches to extract phenotypes from sensor data have been hampered by limited access to (a) sufficiently large, organized multi-sensor datasets, (b) field trials that have a large scale and significant number of genotypes, (c) full genetic sequencing of those phenotypes, and (d) datasets sufficiently organized so that algorithm centered researchers can directly address the real biological problems. To address this, we present SGxP, a novel benchmark dataset from a large-scale field trial consisting of the complete genotype of over 300 sorghum varieties, and time sequences of imagery from several field plots growing each variety, taken with RGB and laser 3D scanner imaging. To lower the barrier to entry and facilitate further developments, we provide a set of well organized, multi-sensor imagery and corresponding genomic data. We implement baseline deep learning based phenotyping approaches to create baseline results for individual sensors and multi-sensor fusion for detecting genetic mutations with known impacts. We also provide and support an open-ended challenge by identifying thousands of genetic mutations whose phenotypic impacts are currently unknown. A web interface for machine learning researchers and practitioners to share approaches, visualizations and hypotheses supports engagement with plant biologists to further the understanding of the sorghum genotype x phenotype relationship. The full dataset, leaderboard (including baseline results) and discussion forums can be found at http://sorghumsnpbenchmark.com.

A large amount of high-dimensional and heterogeneous data appear in practical applications, which are often published to third parties for data analysis, recommendations, targeted advertising, and reliable predictions. However, publishing these data may disclose personal sensitive information, resulting in an increasing concern on privacy violations. Privacy-preserving data publishing has received considerable attention in recent years. Unfortunately, the differentially private publication of high dimensional data remains a challenging problem. In this paper, we propose a differentially private high-dimensional data publication mechanism (DP2-Pub) that runs in two phases: a Markov-blanket-based attribute clustering phase and an invariant post randomization (PRAM) phase. Specifically, splitting attributes into several low-dimensional clusters with high intra-cluster cohesion and low inter-cluster coupling helps obtain a reasonable allocation of privacy budget, while a double-perturbation mechanism satisfying local differential privacy facilitates an invariant PRAM to ensure no loss of statistical information and thus significantly preserves data utility. We also extend our DP2-Pub mechanism to the scenario with a semi-honest server which satisfies local differential privacy. We conduct extensive experiments on four real-world datasets and the experimental results demonstrate that our mechanism can significantly improve the data utility of the published data while satisfying differential privacy.

Transformer architectures have shown promise for a wide range of computer vision tasks, including image embedding. As was the case with convolutional neural networks and other models, explainability of the predictions is a key concern, but visualization approaches tend to be architecture-specific. In this paper, we introduce a new method for producing interpretable visualizations that, given a pair of images encoded with a Transformer, show which regions contributed to their similarity. Additionally, for the task of image retrieval, we compare the performance of Transformer and ResNet models of similar capacity and show that while they have similar performance in aggregate, the retrieved results and the visual explanations for those results are quite different. Code is available at https://github.com/vidarlab/xformer-paired-viz.

User response prediction, which aims to predict the probability that a user will provide a predefined positive response in a given context such as clicking on an ad or purchasing an item, is crucial to many industrial applications such as online advertising, recommender systems, and search ranking. For these tasks and many other machine learning tasks, an indispensable part of success is feature engineering, where cross features are a significant type of feature transformations. However, due to the high dimensionality and super sparsity of the data collected in these tasks, handcrafting cross features is inevitably time expensive. Prior studies in predicting user response leveraged the feature interactions by enhancing feature vectors with products of features to model second-order or high-order cross features, either explicitly or implicitly. However, these existing methods can be hindered by not learning sufficient cross features due to model architecture limitations or modeling all high-order feature interactions with equal weights. Different features should contribute differently to the prediction, and not all cross features are with the same prediction power.

Visualization tools like t-SNE and UMAP give insight into the high-dimensional structure of datasets. When there are related datasets (such as the high-dimensional representations of image data created by two different Deep Learning architectures), roughly aligning those visualizations helps to highlight both the similarities and differences. In this paper we propose a method to align multiple low dimensional UMAP visualizations by adding an alignment term to the UMAP loss function. We provide an automated procedure to find a weight for this term that encourages the alignment but only minimally changes the fidelity of the underlying embedding.

Deep metric learning seeks to define an embedding where semantically similar images are embedded to nearby locations, and semantically dissimilar images are embedded to distant locations. Substantial work has focused on loss functions and strategies to learn these embeddings by pushing images from the same class as close together in the embedding space as possible. In this paper, we propose an alternative, loosened embedding strategy that requires the embedding function only map each training image to the most similar examples from the same class, an approach we call "Easy Positive" mining. We provide a collection of experiments and visualizations that highlight that this Easy Positive mining leads to embed-dings that are more flexible and generalize better to new unseen data. This simple mining strategy yields recall performance that exceeds state of the art approaches (including those with complicated loss functions and ensemble methods) on image retrieval datasets including CUB, Stanford Online Products, In-Shop Clothes and Hotels-50K. Code is available at: https://github.com/littleredxh/EasyPositiveHardNegative.

Recognizing a hotel from an image of a hotel room is important for human trafficking investigations. Images directly link victims to places and can help verify where victims have been trafficked, and where their traffickers might move them or others in the future. Recognizing the hotel from images is challenging because of low image quality, uncommon camera perspectives, large occlusions (often the victim), and the similarity of objects (e.g., furniture, art, bedding) across different hotel rooms. To support efforts towards this hotel recognition task, we have curated a dataset of over 1 million annotated hotel room images from 50,000 hotels. These images include professionally captured photographs from travel websites and crowd-sourced images from a mobile application, which are more similar to the types of images analyzed in real-world investigations. We present a baseline approach based on a standard network architecture and a collection of data-augmentation approaches tuned to this problem domain.

For convolutional neural network models that optimize an image embedding, we propose a method to highlight the regions of images that contribute most to pairwise similarity. This work is a corollary to the visualization tools developed for classification networks, but applicable to the problem domains better suited to similarity learning. The visualization shows how similarity networks that are fine-tuned learn to focus on different features. We also generalize our approach to embedding networks that use different pooling strategies and provide a simple mechanism to support image similarity searches on objects or sub-regions in the query image.

Anomaly detection is the well-studied task of identifying when data is atypical in some way with respect to its source. In this work, by contrast, we are interested in finding possible descriptions of what may be causing anomalies. We propose a new task, attaching semantics drawn from metadata to a portion of the anomalous examples from some data source. Such a partial description of the anomalous data in terms of the meta-data is useful both because it may help to explain what causes the identified anomalies, and also because it may help to identify the truly unusual examples that defy such simple categorization. This is especially significant when the data set is too large for a human analyst to inspect the anomalies manually. The challenge is that anomalies are, by definition, relatively rare, and so we are seeking to learn a precise characterization of a rare event. We examine algorithms for this task in a webcam domain, generating human-understandable explanations for a pixellevel characterization of anomalies. We find that using a recently proposed algorithm that prioritizes precision over recall, it is possible to attach good descriptions to a moderate fraction of the anomalies in webcam data so long as the data set is fairly large.

We propose Deep Feature Interpolation (DFI), a new datadriven baseline for automatic high-resolution image transformation. As the name suggests, DFI relies only on simple linear interpolation of deep convolutional features from pre-trained convnets. We show that despite its simplicity, DFI can perform high-level semantic transformations like “make older/younger”, “make bespectacled”, “add smile”, among others, surprisingly well-sometimes even matching or outperforming the state-of-the-art. This is particularly unexpected as DFI requires no specialized network architecture or even any deep network to be trained for these tasks. DFI therefore can be used as a new baseline to evaluate more complex algorithms and provides a practical answer to the question of which image transformation tasks are still challenging after the advent of deep learning.

We consider the problem of camera pose estimation for a scenario where the camera may have continuous and unknown changes in its focal length. Understanding frame by frame changes in camera focal length is vital to accurately estimating camera pose and vital to accurately rendering virtual objects in a scene with the correct perspective. However, most approaches to camera calibration require geometric constraints from many frames or the observation of a 3D calibration object - both of which may not be feasible in augmented reality settings. This paper introduces a calibration object based on a flat lenticular array that creates a color coded light-field whose observed color changes depending on the angle from which it is viewed. We derive an approach to estimate the focal length of the camera and the relative pose of an object from a single image. We characterize the performance of camera calibration across various focal lengths and camera models, and we demonstrate the advantages of the focal length estimation in rendering a virtual object in a video with constant zooming.

The light field, or plenoptic function, is a mathematical construct that models the location and direction of light to describe the complete visual appearance of a scene. The light field provides a unifying construct to describe cameras and displays. Explicitly manipulating the light field is an approach to changing the world to make it easier to understand. One way to create light fields is with materials like lenticular arrays, whose color appearance can be made to vary by viewing angle. These Chromo-coded light fields use color to create additional geometric cues, making it cheaper, faster and more accurate to measure object pose. For high-end applications like augmented reality, the color-cues make it possible to accurately measure pose of small objects to project digital content. This poster offers demonstrations of a few augmented reality applications made possible by chromo-coded light fields.

Understanding the pose of an object is fundamental to a variety of visual tasks, from trajectory estimation of UAVs to object tracking for augmented reality. Fiducial markers are visual targets designed to simplify this process by being easy to detect, recognize, and track. They are often based on features that are partially invariant to lighting, pose and scale. Here we explore the opposite approach and design passive calibration patterns that explicitly change appearance as a function of pose. We propose a new, simple fiducial marker made with a small lenticular array, which changes its apparent color based on the angle at which it is viewed. This allows full six degree-of-freedom pose estimation with just two markers and an optimization that fully decouples the estimate of rotation from translation. We derive the geometric constraints that these fiducial markers provide, and show improved pose estimation performance over standard markers through experiments with a physical prototype for form factors that are not well supported by standard markers (such as long skinny objects). In addition, we experimentally evaluate heuristics and optimizations that give robustness to real-world lighting variations.

Many vision and augmented reality applications require knowing the rotation of the camera relative to an object or scene. In this paper we propose to create a structured light field designed explicitly to simplify the estimation of camera rotation. The light field is created using a lenticular sheet with a color coded backplane pattern, creating a light field where the observed color depends on the direction of the light. We show that a picture taken within such a light field gives linear constraints on the K-1R matrix that defines the camera calibration and rotation. In this work we derive an optimization that uses these constraints to rapidly estimate rotation, demonstrate a physical prototype and characterize its sensitivity to errors in the camera focal length and camera color sensitivity.

Satellite imagery of cloud cover is extremely important for understanding and predicting weather. We demonstrate how this imagery can be constructed "from the ground up" without requiring expensive geo-stationary satellites. This is accomplished through a novel approach to approximate continental-scale cloud maps using only ground-level imagery from publicly-available webcams. We collected a year's worth of satellite data and simultaneously-captured, geo-located outdoor webcam images from 4388 sparsely distributed cameras across the continental USA. The satellite data is used to train a dynamic model of cloud motion alongside 4388 regression models (one for each camera) to relate ground-level webcam data to the satellite data at the camera's location. This novel application of large-scale computer vision to meteorology and remote sensing is enabled by a smoothed, hierarchically-regularized dynamic texture model whose system dynamics are driven to remain consistent with measurements from the geo-located webcams. We show that our hierarchical model is better able to incorporate sparse webcam measurements resulting in more accurate cloud maps in comparison to a standard dynamic textures implementation. Finally, we demonstrate that our model can be successfully applied to other natural image sequences from the DynTex database, suggesting a broader applicability of our method.

Many computer vision applications rely on matching features of a query image to reference data sets, but little work has explored how quickly data sets become out of date. In this paper we measure feature matching performance across 5 years of time-lapse data from 20 static cameras to empirically study how feature matching is affected by changing sunlight direction, seasons, weather, and the structural changes over time in outdoor settings. We identify several trends that may be relevant in real world applications: (1) features are much more likely to match within a few days of the reference data, (2) weather and sun-direction have a large effect on feature matching, and (3) there is a slow decay over time due to physical changes in a scene, but this decay is much smaller than effects of lighting direction and weather. These trends are consistent across standard choices for feature detection (DoG, MSER) and feature description (SIFT, SURF, and DAISY). Across all choices, analysis of the feature detection and matching pipeline highlights that performance decay is mostly due to failures in key point detection rather than feature description.

In outdoor images, cast shadows define 3D constraints between the sun, the points casting a shadow, and the surfaces onto which shadows are cast. This cast shadow structure provides a powerful cue for 3D reconstruction, but requires that shadows be tracked over time, and this is difficult as shadows have minimal texture. Thus, we develop a shadow tracking system that enforces geometric consistency for each track and then combines thousands of tracking results to create a 3D model of scene geometry. We demonstrate reconstruction results on a variety of outdoor scenes, including some that show the 3D structure of occluders never directly observed by the camera.

Shadows encode a powerful geometric cue: if one pixel casts a shadow onto another, then the two pixels are colinear with the lighting direction. Given many images over many lighting directions, this constraint can be leveraged to recover the depth of a scene from a single viewpoint. For outdoor scenes with solar illumination, we term this the episolar constraint, which provides a convex optimization to solve for the sparse depth of a scene from shadow correspondences, a method to reduce the search space when finding shadow correspondences, and a method to geometrically calibrate a camera using shadow constraints. Our method constructs a dense network of nonlocal constraints which complements recent work on outdoor photometric stereo and cloud based cues for 3D. We demonstrate results across a variety of time-lapse sequences from web cams "in the wild".

We consider the problem of estimating the current satellite cloud map from a collection of broadly distributed, ground-based webcams. The approach uses historical, geo-referenced satellite imagery to learn a mapping between the satellite image and the ground imagery. We explore representational choices for inferring the cloud status based on the ground-level imagery and consider several alternatives for spatially interpolating these sparse measurements to give a complete map. Proof of concept results show that this gives plausible estimates of satellite imagery.

We describe algorithms that use cloud shadows as a form of stochastically structured light to support 3D scene geometry estimation. Taking video captured from a static outdoor camera as input, we use the relationship of the time series of intensity values between pairs of pixels as the primary input to our algorithms. We describe two cues that relate the 3D distance between a pair of points to the pair of intensity time series. The first cue results from the fact that two pixels that are nearby in the world are more likely to be under a cloud at the same time than two distant points. We describe methods for using this cue to estimate focal length and scene structure. The second cue is based on the motion of cloud shadows across the scene; this cue results in a set of linear constraints on scene structure. These constraints have an inherent ambiguity, which we show how to overcome by combining the cloud motion cue with the spatial cue. We evaluate our method on several time lapses of real outdoor scenes.

A global network of webcams offers unique viewpoints from tens of thousands of locations. Understanding the geographic context of this imagery is vital in using these cameras for quantitative environmental monitoring or surveillance applications. We derive robust geo-calibration constraints that allow users to geo-register static or pan-tilt-zoom cameras by specifying a few corresponding points, and describe our Web interface suitable for novices. We discuss design decisions that support our scalable, publicly accessible Web service that allows webcam textures to be displayed live on 3D geographic models. Finally, we demonstrate several multimedia applications for geo-calibrated cameras.

We introduce the Longterm Observation of Scenes (with Tracks) dataset. This dataset comprises videos taken from streaming outdoor webcams, capturing the same half hour, each day, for over a year. LOST contains rich metadata, including geolocation, day-by-day weather annotation, object detections, and tracking results. We believe that sharing this dataset opens opportunities for computer vision research involving very long-term outdoor surveillance, robust anomaly detection, and scene analysis methods based on trajectories. Efficient analysis of changes in behavior in a scene at very long time scale requires features that summarize large amounts of trajectory data in an economical way. We describe a trajectory clustering algorithm and aggregate statistics about these exemplars through time and show that these statistics exhibit strong correlations with external meta-data, such as weather signals and day of the week.

Crowd-sourcing tools such as Mechanical Turk are popular for annotation of large scale image data sets. Typically, these annotations consist of bounding boxes or coarse outlines of objects, in order to keep the interface as simple as possible and to respect browser constraints. However, as most browsers now contain functionality to quickly process images and render shapes to the browser through JavaScript, better annotations can feasibly be generated through the browser given an easy-to-use interface. In this paper, we develop a suite of annotation tools for high-fidelity object contouring and 3D pose working within the limitation that, to be accessible to most Mechanical Turk users, the tools must be available through browsers with no plug-ins or extra downloads. We show comparative results exploring the annotation accuracy relative to existing annotation tools.

We characterize a class of videos consisting of very small but potentially complicated motions. We find that in these scenes, linear appearance variations have a direct relationship to scene motions. We show how to interpret appearance variations captured through a PCA decomposition of the image set as a scene-specific non-parametric motion basis. We propose fast, robust tools for dense flow estimates that are effective in scenes with small motions and potentially large image noise. We show example results in a variety of applications, including motion segmentation and long-term point tracking.

In surveillance and environmental monitoring applications, it is common to have millions of images of a particular scene. While there exist tools to find particular events, anomalies, human actions and behaviors, there has been little investigation of tools which allow more exploratory searches in the data. This paper proposes modifications to PCA that enable users to quickly recompute low-rank decompositions for select spatial and temporal subsets of the data. This process returns decompositions orders of magnitude faster than general PCA and are close to optimal in terms of reconstruction error. We show examples of real exploratory data analysis across several applications, including an interactive web application.

We consider the problem of geo-locating static cameras from long-term time-lapse imagery. This problem has received significant attention recently, with most methods making strong assumptions on the geometric structure of the scene. We explore a simple, robust cue that relates overall image intensity to the zenith angle of the sun (which need not be visible). We characterize the accuracy of geolocation based on this cue as a function of different models of the zenith-intensity relationship and the amount of imagery available. We evaluate our algorithm on a dataset of more than 60 million images captured from outdoor webcams located around the globe. We find that using our algorithm with images sampled every 30 minutes, yields localization errors of less than 100 km for the majority of cameras.

We explore the use of clouds as a form of structured lighting to capture the 3D structure of outdoor scenes observed over time from a static camera. We derive two cues that relate 3D distances to changes in pixel intensity due to clouds shadows. The first cue is primarily spatial, works with low frame-rate time lapses, and supports estimating focal length and scene structure, up to a scale ambiguity. The second cue depends on cloud motion and has a more complex, but still linear, ambiguity. We describe a method that uses the spatial cue to estimate a depth map and a method that combines both cues. Results on time lapses of several outdoor scenes show that these cues enable estimating scene geometry and camera focal length.

Compressive-sensing cameras are an important new class of sensors that have different design constraints than standard cameras. Surprisingly, little work has explored the relationship between compressive-sensing measurements and differential image motion. We show that, given modest constraints on the measurements and image motions, we can omit the computationally expensive compressive-sensing reconstruction step and obtain more accurate motion estimates with significantly less computation time. We also formulate a compressive-sensing reconstruction problem that incorporates known image motion and show that this method outperforms the state-of-the-art in compressive-sensing video reconstruction.

Web services supporting deep integration between video data and geographic information systems (GIS) empower a large user base to build on popular tools such as Google Earth and Google Maps. Here we extend web interfaces designed explicitly for novice users to integrate streaming video with 3D GIS, and work to dramatically simplify the task of retexturing 3D scenes from live imagery. We also derive and implement constraints to use corresponding points to calibrate popular pan-tilt-zoom webcams with respect to GIS applications, so that the calibration is automatically updated as web users adjust the camera zoom and view direction. These contributions are demonstrated in a live web application implemented on the Google Earth Plug-in, within which hundreds of users have already geo-registered streaming cameras in hundreds of scenes to create live, updating textures in 3D scenes.

Many wireless sensor networks require sufficient sensing coverage over long periods of time. To conserve energy, a coverage maintenance protocol achieves desired coverage by activating only a subset of nodes, while allowing the others to sleep. Existing coverage maintenance protocols are often designed based on simplistic sensing models that do not capture the stochastic nature of distributed sensing. We propose a new sensing coverage model based on the distributed detection theory, which captures two important characteristics of sensor networks, i.e., probabilistic detection by individual sensors and data fusion among sensors. We then present three coverage maintenance protocols that can meet the specified event detection probability and false alarm rate. The centralized protocol only activates a small number of sensors, but introduces extremely long coverage configuration delay. The Se-Grid protocol reduces the configuration time by dividing the network into separate fusion groups, but increases the number of active sensors due to the lack of collaboration among sensors in different groups. In contrast, by coordinating overlapping fusion groups, the Co-Grid protocol can effectively reduce the number of active sensors and the coverage configuration time. The advantages of Co-Grid have been validated through simulations and benchmark results on Mica2 motes.

There are thousands of outdoor webcams which offer live images freely over the Internet. We report on methods for discovering and organizing this already existing and massively distributed global sensor, and argue that it provides an interesting alternative to satellite imagery for global-scale remote sensing applications. In particular, we characterize the live imaging capabilities that are freely available as of the summer of 2009 in terms of the spatial distribution of the cameras, their update rate, and characteristics of the scene in view. We offer algorithms that exploit the fact that webcams are typically static to simplify the tasks of inferring relevant environmental and weather variables directly from image data. Finally, we show that organizing and exploiting the large, ad-hoc, set of cameras attached to the web can dramatically increase the data available for studying particular problems in phenology.

We propose an information-theoretic clustering framework for density-based clustering and similarity or distance-based clustering with objective functions of clustering performance derived from stochastic complexity and minimum description length (MDL) arguments. Under this framework, the number of clusters and parameters can be determined in a principled way without prior knowledge from users. We show that similarity-based clustering can be viewed as combinatorial optimization on graphs. We propose two clustering algorithms, one of which relies on a minimum arborescence tree algorithm which returns optimal clustering under the proposed MDL objective function for similarity-based clustering. We demonstrate clustering performance on synthetic data.

Modeling the dynamics of heart and lung tissue is challenging because the tissue deforms between data acquisitions. To reconstruct complete volumes, sample data captured at different times and locations must be combined. This paper presents a novel end-to-end, data driven framework for the complete reconstruction of deforming tissue volumes. This framework is a joint optimization over an undeformed tissue volume, a deformation map that describes tissue motion forgiven pose parameters (i.e. breathing and heartbeat), and an estimate of those parameters for each data acquisition. Tissue motion is modeled by deforming a reference volume with a cubic B-spline free form deformation, and we use Isomap to derive initial estimates of the pose of sample data. An iterative method is used to simultaneously solve for the reference volume and deformation map while updating the pose estimates. This same process is demonstrated on 4D CT lung data and heart/lung MR data.

Automating tools for geo-locating and geo-orienting static cameras is a key step in creating a useful global imaging network from cameras attached to the Internet. We present algorithms for partial camera calibration that rely on access to accurately time-stamped images captured over time from cameras that do not move. To support these algorithms we also offer a method of camera viewpoint change detection, or "tamper detection", which determines if a camera has moved in the challenging case when images are only captured every half hour. These algorithms are tested on a subset of the AMOS (Archive of Many Outdoor Scenes) database, and we present preliminary results that highlight the promise of these approaches.

Events in surveillance video occur over many time scales, but common approaches to background subtraction and video representation are implicitly based on a single temporal scale. In this work, we derive a set of causal filters which define a temporal scale-space representation for the activity at each pixel. This scale-space can be maintained and continuously updated in real time and, for static cameras viewing dynamic scenes, has several interesting properties. In particular, it directly characterizes interesting temporal features and supports approximate reconstruction of the video history under challenging noise conditions. The temporal scale-space grounds novel approaches to several applications, including a natural visualization tool to summarize recent video behavior in a single image, and a tool to directly report how long the object has been present in a scene without reexamining any video data.

This paper details an empirical study of large image sets taken by static cameras. These images have consistent correlations over the entire image and over time scales of days to months. Simple second-order statistics of such image sets show vastly more structure than exists in generic natural images or video from moving cameras. Using a slight variant to PCA, we can decompose all cameras into comparable components and annotate images with respect to surface orientation, weather, and seasonal change. Experiments are based on a data set from 538 cameras across the United States which have collected more than 17 million images over the the last 6 months.

Wireless sensor networks (WSNs) introduce new challenges to topology control due to the prevalence of lossy links. We propose a new topology control formulation for lossy WSNs that captures the stochastic nature of lossy links and quantifies the worst-case path quality in a network. We develop a novel localized scheme called Configurable Topology Control (CTC). The key feature of CTC is its capability of flexibly configuring the topology of a lossy WSN to achieve desired path quality bounds in a localized fashion. Furthermore, CTC can incorporate different control strategies (per-node/per-link) and optimization criteria. Simulations using a realistic radio model of Mica2 motes show that CTC significantly outperforms a representative traditional topology control algorithm called LMST in terms of both communication performance and energy efficiency. Our results demonstrate the importance of incorporating lossy links of WSNs in the design of topology control algorithms.

A key problem in widely distributed camera networks is locating the cameras. This paper considers three scenarios for camera localization: localizing a camera in an unknown environment, adding a new camera in a region with many other cameras, and localizing a camera by finding correlations with satellite imagery. We find that simple summary statistics (the time course of principal component coefficients) are sufficient to geolocate cameras without determining correspondences between cameras or explicitly reasoning about weather in the scene. We present results from a database of images from 538 cameras collected over the course of a year. We find that for cameras that remain stationary and for which we have accurate image times- tamps, we can localize most cameras to within 50 miles of the known location. In addition, we demonstrate the use of a distributed camera network in the construction a map of weather conditions.

We develop a framework to allow generic object detection algorithms to exploit geometric information commonly available to robot vision systems. Robot systems take pictures with calibrated cameras from known positions and may simultaneously capture depth measurements in the scene. This allows known constraints on the 3D size and position of objects to be translated into constraints on potential locations and scales of objects in the image, eliminating potentially expensive image operations for geometrically infeasible object locations. We show this integration to be very natural in the context of face detection and find that the computational effort of the standard Viola Jones face detector (as implemented in OpenCV) can be reduced by 85 percent with three times fewer false positives.

This article proposes the minimum power configuration (MPC) approach to power management in wireless sensor networks. In contrast to earlier research that treats different radio states (i.e., transmission/reception/idle) in isolation, MPC integrates them in a joint optimization problem that depends on both the set of active nodes and the transmission power. We propose four approximation algorithms with provable performance bounds and two practical routing protocols. Simulations based on realistic radio models show that the MPC approach can conserve more energy than existing minimum power routing and topology control protocols. Furthermore, it can flexibly adapt to network workload and radio platforms.

We develop theory and algorithms to incorporate image manifold constraints in a level set segmentation algorithm. This provides a framework to simultaneously segment every image of data sets that vary due to two degrees of freedom - such as cardiopulmonary MR images which deform due to patient breathing and heartbeats. We derive two formulations: a 4D level set which loosely couples the level set function between neighbors in the 2D image manifold and a multilayer level set function which uses different levels of the level set function to represent shapes that shrink or grow. We characterize the set of shape manifolds that the multilayer level set function can represent, and derive the evolution equations for both frameworks. We offer results of segmenting the left ventricle in cardiopulmonary MRI; by automatically discovering the 2D manifold structure of the image set then simultaneously segmenting every frame. Both extensions improve on frame-by-frame approaches, and a comparison of the results offers insight into their strengths and weaknesses.

An important class of image data sets depict an object undergoing deformation. When there are only a few underlying causes of the deformation, these images have a natural low-dimensional structure which can be parameterized using manifold learning. This paper presents a method to solve for the deformation field as a function of the manifold coordinates-implicitly optimizing the deformation between all pairs of images simultaneously. Additionally, we provide a mechanism to create images for arbitrary coordinates of the manifold, addressing an important limitation of manifold learning algorithms for the case of images related through deformations. We give quantitative results in an artificial image morphing example and illustrate the method by finding the deformations relating all images of a cardiopulmonary MR image sequence.

We address the problem of segmenting multiple similar objects by optimizing a Chan-Vese-like functional with respect to a mixture of level set functions. We solve the variational formulation under this model allowing for similarity transforms. This allows shape priors to be enforced even in the presence of mutual occlusion, lifting the limitation. We show numerical results on example images to demonstrate the promise of our approach.

Greedy geographic routing is an attractive localized routing scheme for wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks (e.g., surveillance or object tracking systems) that provide sensing coverage over a geographic area. Our analysis and simulation results demonstrate that an existing geographic routing algorithm, greedy forwarding (GF), can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under GF. We also propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that achieves path dilation lower than 4.62 in sensing-covered networks as long as the communication range is at least twice the sensing range. Furthermore, we extend GF and BVGF to achieve provable performance bounds in terms of total number of transmissions and reliability in lossy networks.

Manifold learning has become a vital tool in data driven methods for interpretation of video, motion capture, and handwritten character data when they lie on a low dimensional, nonlinear manifold. This work extends manifold learning to classify and parameterize unlabeled data which lie on multiple, intersecting manifolds. This approach significantly increases the domain to which manifold learning methods can be applied, allowing parameterization of example manifolds such as figure eights and intersecting paths which are quite common in natural data sets. This approach introduces several technical contributions which may be of broader interest, including node-weighted multidimensional scaling and a fast algorithm for weighted low-rank approximation for rank-one weight matrices. We show examples for intersecting manifolds of mixed topology and dimension and demonstrations on human motion capture data.

This paper proposes the minimum power configuration (MPC) approach to energy conservation in wireless sensor networks. In sharp contrast to earlier research that treats topology control, power-aware routing, and sleep management in isolation, MPC integrates them as a joint optimization problem in which the power configuration of a network consists of a set of active nodes and the transmission powers of the nodes. We show through analysis that the minimum power configuration of a network is inherently dependent on the data rates of sources. We propose several approximation algorithms with provable performance bounds compared to the optimal solution, and a practical Minimum Power Configuration Protocol (MPCP) that can dynamically (re)configure a network to minimize the energy consumption based on current data rates. Simulations based on realistic radio models of the Mica2 motes show that MPCP can conserve significantly more energy than existing minimum power routing and topology control protocols.

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degree of coverage and connectivity in order to support different applications and environments with diverse requirements. This article presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways. (1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. (2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity within a unified framework; in sharp contrast to several existing approaches that address the two problems in isolation. (3) We integrate CCP with SPAN to provide both coverage and connectivity guarantees. (4) We propose a probabilistic coverage model and extend CCP to provide probabilistic coverage guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations through both geometric analysis and extensive simulations.

This paper considers the geometric constraints to combine structure from motion with a sparse set of depth measurements. The goal is to improve the motion estimation for autonomous navigation, and to increase the fidelity of reconstructed 3D scene models. The system is implemented on an iRobot-B2ir Robot with a video camera and a planar laser range finder which gives relatively accurate depth measurements of a small set of scene points. Using a probabilistic model of scene smoothness, the depth information is used to modify the classical epipolar error function to simultaneously incorporate data from both sensors. We present the results of real-world experiments and experiment with different prior assumptions about the scene structure.

Wireless sensor networks often face the critical challenge of sustaining long-term operation on limited battery energy. Coverage maintenance protocols can effectively prolong network lifetime by maintaining sufficient sensing coverage over a region using a small number of active nodes while scheduling the others to sleep. We present a novel distributed coverage maintenance protocol called the Coordinating Grid (Co-Grid). In contrast to existing coverage maintenance protocols which are based on simpler detection models, Co-Grid adopts a distributed detection model based on data fusion that is more consistent with many distributed sensing applications. Co-Grid organizes the network into coordinating fusion groups located on overlapping virtual grids. Through coordination among neighboring fusion groups, Co-Grid can achieve comparable number of active nodes as a centralized algorithm, while reducing the network (re-)configuration time by orders of magnitude. Co-Grid is especially suitable for large and energy-constrained sensor networks that require quick (re-)configuration in response to node failures and environmental changes. We validate our claims by both theoretical analysis and simulations.

We describe theoretical and experimental results for the extrinsic calibration of sensor platform consisting of a camera and a 2D laser range finder. The calibration is based on observing a planar checkerboard pattern and solving for constraints between the "views" of a planar checkerboard calibration pattern from a camera and laser range finder. We give a direct solution that minimizes an algebraic error from this constraint, and subsequent nonlinear refinement minimizes a re-projection error. To our knowledge, this is the first published calibration tool for this problem. Additionally we show how this constraint can reduce the variance in estimating intrinsic camera parameters.

Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks that provide sensing coverage over a geographic area (e.g., surveillance or object tracking systems). Our geometric analysis and simulation results demonstrate that existing greedy geographic routing algorithms can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under greedy geographic routing algorithms. Furthermore, we propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that allows sensing-covered networks to achieve an asymptotic network dilation lower than 4:62 as long as the communication range is at least twice the sensing range. Our results show that simple greedy geographic routing is an effective routing scheme in many sensing-covered networks.

We illustrate how to consider a network of cameras as a single generalized camera in a framework proposed by Nayar (2001). We derive the discrete structure from motion equations for generalized cameras, and illustrate the corollaries to epipolar geometry. This formal mechanism allows one to use a network of cameras as if they were a single imaging device, even when they do not share a common center of projection. Furthermore, an analysis of structure from motion algorithms for this imaging model gives constraints on the optimal design of panoramic imaging systems constructed from multiple cameras.

Background subtraction is the first step of many video surveillance applications. What is considered background varies by application, and may include regular, systematic, or complex motions. The paper explores the use of several different local spatio-temporal models of a background, defined at each pixel in the image. We present experiments with real image data and conclude that appropriate local representations are sufficient to make background models of complicated real world motions. Empirical studies illustrate, for example, that an optical flow-based model is able to detect emergency vehicles whose motion is different from those typically observed in traffic scenes. We conclude that "different models are appropriate for different scenes", but give criteria by which one can choose which model will be best.

Dimensionality reduction techniques seek to represent a set of images as a set of points in a low dimensional space. Here we explore a video representation that considers a video as two parts - a space of possible images and a trajectory through that space. The non-linear dimensionality reduction technique of Isomap, gives, for many interesting scenes, a very low dimensional representation of the space of possible images. Analysis of the shape of the video trajectory through these image spaces gives new tools for video analysis. Experiments with natural video sequences illustrate methods for the very different tasks of classifying video clips and temporal super-resolution.

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.

This work is motivated by the problem of placing pressure-meters in fluid networks. The problem is formally defined in graph-theoretic terms as follows. Given a graph, find a cotree (complement of a tree) incident upon the minimum number of vertices. We show that this problem is NP-hard and MAX SNP-hard. We design an algorithm with an approximation factor of $2 + \epsilon$ for this problem for any fixed $\epsilon >0$. This approximation bound comes from the analysis of a local search heuristic, a common practical optimization technique that does not often allow formal worst-case analysis. The algorithm is made very efficient by finding restrictive definitions of the local neighborhoods to be searched. We also exhibit a polynomial time approximation scheme for this problem when the input is restricted to planar graphs.

The paper describes an imaging system that has been designed specifically for the purpose of recovering egomotion and structure from video. The system consists of six cameras in a network arranged so that they sample different parts of the visual sphere. This geometric configuration has provable advantages compared to small field of view cameras for the estimation of the system's own motion and consequently the estimation of shape models from the individual cameras. The reason is that inherent ambiguities of confusion between translation and rotation disappear. We provide algorithms for the calibration of the system and 3D motion estimation. The calibration is based on a new geometric constraint that relates the images of lines parallel in space to the rotation between the cameras. The 3D motion estimation uses a constraint relating structure directly to image gradients.

The full-degree spanning tree problem is defined as follows: Given a connected graph G = (V, E), find a spanning tree T to maximize the number of vertices whose degree in T is the same as G (are called vertices of “full” degree). This problem is NP-hard. We present almost-optimal approximation algorithms for it assuming that coR ≠ NP. For the case of general graphs, our approximation factor is . Using Håstad's result on the hardness of an approximating clique, we can show that if there is a polynomial time approximation algorithm for our problem with a factor of O(n1/2−ϵ) then coR = NP. Additionally, we present two algorithms for optimally solving small instances of the general problem and experimental results comparing our algorithm to the optimal solution and the previous heuristic used for this problem. © 2000 John Wiley & Sons, Inc.

We consider a problem central in aerial visual surveillance applications; detection and tracking of small, independently moving objects in long and noisy video sequences. We directly use spatiotemporal image intensity gradient measurements to compute an exact model of background motion. This allows the creation of accurate mosaics over many frames, and the definition of a constraint violation function which acts as an indicator of independent motion. A novel temporal integration method maintains confidence measures over long subsequences without computing the optic flow, requiring object models, or using a Kalman filter. The mosaic acts as a stable feature frame, allowing precise localization of the independently moving objects. We present a statistical analysis of the effects of image noise on the constraint violation measure and find a good match between the predicted probability distribution function and the measured sample frequencies in a test sequence.

The computation of optical flow from image derivatives is biased in regions of non uniform gradient distributions. A least-squares or total least squares approach to computing optic flow from image derivatives even in regions of consistent flow can lead to a systematic bias dependent upon the direction of the optic flow, the distribution of the gradient directions, and the distribution of the image noise. The bias a consistent underestimation of length and a directional error. Similar results hold for various methods of computing optical flow in the spatiotemporal frequency domain. The predicted bias in the optical flow is consistent with psychophysical evidence of human judgment of the velocity of moving plaids, and provides an explanation of the Ouchi illusion. Correction of the bias requires accurate estimates of the noise distribution; the failure of the human visual system to make these corrections illustrates both the difficulty of the task and the feasibility of using this distorted optic flow or undistorted normal flow in tasks requiring higher lever processing.

We consider a problem central in aerial visual surveillance applications-detection and tracking of small, independently moving objects in long and noisy video sequences. We directly use spatiotemporal image intensity gradient measurements to compute an exact model of background motion. This allows the creation of accurate mosaics over many frames and the definition of a constraint violation function which acts as an indication of independent motion. A novel temporal integration method maintains confidence measures over long subsequences without computing the optic flow, requiring object models, or using a Kalman filler. The mosaic acts as a stable feature frame, allowing precise localization of the independently moving objects. We present a statistical analysis of the effects of image noise on the constraint violation measure and find a good match between the predicted probability distribution function and the measured sample frequencies in a test sequence.