Person re-identification (PRID) from side-mounted rectilinear-lens cameras is a well-studied problem. On the other hand, PRID from overhead fisheye cameras is new and largely unstudied, primarily due to the lack of suitable image datasets. To fill this void, we introduce the “Fisheye Re-IDentification Dataset with Annotations” (FRIDA)1, with 240k+ bounding-box annotations of people, captured by 3 time-synchronized, ceiling-mounted fisheye cameras in a large indoor space. Due to a field-of-view overlap, PRID in this case differs from a typical PRID problem, which we discuss in depth. We also evaluate the performance of 10 state-of-the-art PRID algorithms on FRIDA. We show that for 6 CNN-based algorithms, training on FRIDA boosts the performance by up to 11.64% points in mAP compared to training on a common rectilinear-camera PRID dataset.1vip. bu.edu/frida

Owing to their large field of view, overhead fisheye cameras are becoming a surveillance modality of choice for large indoor spaces. However, traditional people detection and tracking algorithms developed for side-mounted, rectilinear-lens cameras do not work well on images from overhead fisheye cameras due to their viewpoint and unique optics. While several people-detection algorithms have been recently developed for such cameras, they have all been tested on datasets consisting of "staged" recordings with a limited variety of people, scenes and challenges. Clearly, the performance of these algorithms "in the wild", i.e., on recordings with real-world challenges, remains un-known. In this paper, we introduce a new benchmark dataset of in-the-Wild Events for People Detection and Tracking from Overhead Fisheye cameras (WEPDTOF)1. The dataset features 14 YouTube videos captured in a wide range of scenes, 188 distinct person identities consistently labeled across time, and real-world challenges such as extreme occlusions and camouflage. Also, we propose 3 spatiotemporal extensions2of a state-of-the-art people-detection algorithm to enhance the coherence of detections across time. Compared to top-performing algorithms, that are purely spatial, the new algorithms offer a significant performance improvement on the new dataset. Finally, we compare the people tracking performance of these algorithms on WEPDTOF.

Person re-identification using rectilinear cameras has been thoroughly researched to date. However, the topic has received little attention for fisheye cameras and the few developed methods are appearance-based. We propose a geometry-based approach to re-identification for overhead fisheye cameras with overlapping fields of view. The main idea is that a person visible in two camera views is uniquely located in the view of one camera given their height and location in the other camera’s view. We develop a height-dependent mathematical relationship between these locations using the unified spherical model for omnidirectional cameras. We also propose a new fisheye-camera calibration method and a novel automated approach to calibration-data collection. Finally, we propose four re-identification algorithms that leverage geometric constraints and demonstrate their excellent accuracy, which vastly exceeds that of a state-of-the-art appearance-based method, on a fisheye-camera dataset we collected.

This paper presents the outcomes of the PETS2021 challenge held in conjunction with AVSS2021 and sponsored by the EU FOLDOUT project. The challenge comprises the publication of a novel video surveillance dataset on through-foliage detection, the defined challenges addressing person detection and tracking in fragmented occlusion scenarios, and quantitative and qualitative performance evaluation of challenge results submitted by six worldwide participants. The results show that while several detection and tracking methods achieve overall good results, through-foliage detection and tracking remains a challenging task for surveillance systems especially as it serves as the input to behaviour (threat) recognition.

Background subtraction is a basic task in computer vision and video processing often applied as a pre-processing step for object tracking, people recognition, etc. Recently, a number of successful background-subtraction algorithms have been proposed, however nearly all of the top-performing ones are supervised. Crucially, their success relies upon the availability of some annotated frames of the test video during training. Consequently, their performance on completely "unseen" videos is undocumented in the literature. In this work, we propose a new, supervised, background-subtraction algorithm for unseen videos (BSUV-Net) based on a fully-convolutional neural network. The input to our network consists of the current frame and two background frames captured at different time scales along with their semantic segmentation maps. In order to reduce the chance of overfitting, we also introduce a new data-augmentation technique which mitigates the impact of illumination difference between the background frames and the current frame. On the CDNet-2014 dataset, BSUV-Net outperforms stateof-the-art algorithms evaluated on unseen videos in terms of several metrics including F-measure, recall and precision.

We propose two supervised methods for people counting using an overhead fisheye camera. As opposed to standard cameras, fisheye cameras offer a large field of view and, when mounted overhead, reduce occlusions. However, methods developed for standard cameras perform poorly on fisheye images since they do not account for the radial image geometry. Furthermore, no large-scale fisheye-image datasets with radially-aligned bounding box annotations are available for training. We adapt YOLOv3 trained on standard images for people counting in fisheye images. In one method, YOLOv3 is applied to 24 rotated, overlapping windows and the results are post-processed to produce a people count. In another method, YOLOv3 is applied to windows of interest extracted by background subtraction. For evaluation, we collected and annotated an indoor fisheye-image dataset that we make public. Experiments on this dataset show that our methods reduce the people counting MAE of two natural benchmarks by over 60%.

We propose and study a data-driven approach to indoor occupant localization using a network of single-pixel light sensors and modulated LED light sources. Locations are estimated by processing sensor data using a simple convolutional neural network (CNN). Unlike previous model-based methods, the proposed approach does not require knowledge of room dimensions, locations of LEDs and sensors, and assumptions about material properties and object heights. We quantitatively validate the performance of our approach in simulated and real-world environments in private and public scenarios. In Unity3D simulations, compared to the best-performing benchmark method, our approach reduces the average localization error by 47.69% in private scenarios and by 46.99% in public scenarios. Similarly, in a real testbed the error is reduced by 36.54% and 11.46% in private and public scenarios respectively.

The ability to train on a large dataset of labeled samples is critical to the success of deep learning in many domains. In this paper, we focus on motor vehicle classification and localization from a single video frame and introduce the "MIOvision Traffic Camera Dataset" (MIO-TCD) in this context. MIO-TCD is the largest dataset for motorized traffic analysis to date. It includes 11 traffic object classes such as cars, trucks, buses, motorcycles, bicycles, pedestrians. It contains 786,702 annotated images acquired at different times of the day and different periods of the year by hundreds of traffic surveillance cameras deployed across Canada and the United States. The dataset consists of two parts: a "localization dataset", containing 137,743 full video frames with bounding boxes around traffic objects, and a "classification dataset", containing 648,959 crops of traffic objects from the 11 classes. We also report results from the 2017 CVPR MIO-TCD Challenge, that leveraged this dataset, and compare them with results for state-of-the-art deep learning architectures. These results demonstrate the viability of deep learning methods for vehicle localization and classification from a single video frame in real-life traffic scenarios. The topperforming methods achieve both accuracy and Kappa score above 96% on the classification dataset and mean-average precision of 77% on the localization dataset. We also identify scenarios in which state-of-the-art methods still fail and we suggest avenues to address these challenges. Both the dataset and detailed results are publicly available on-line [1].

We propose a system for indoor localization using intensity-controllable LED light fixtures and light sensors mounted on the ceiling. While providing accurate location estimates, our approach preserves user privacy and is robust to ambient light conditions. We develop a LASSO algorithm and a localized ridge regression algorithm for locating a single object. In synthetic experiments, our localized ridge regression algorithm achieves an average localization error ranging from 0.24in to 1.39in, for different object sizes, in a 7×12-foot room. The localized ridge regression algorithm also shows the ability to locate multiple objects in experiments with a real-world occupancy scenario.

Deep convolutional neural networks (ConvNets) have been recently shown to attain state-of-the-art performance for action recognition on standard-resolution videos. However, less attention has been paid to recognition performance at extremely low resolutions (eLR) (e.g., 16 12 pixels). Reliable action recognition using eLR cameras would address privacy concerns in various application environments such as private homes, hospitals, nursing/rehabilitation facilities, etc. In this paper, we propose a semi-coupled, filter-sharing network that leverages high-resolution (HR) videos during training in order to assist an eLR ConvNet. We also study methods for fusing spatial and temporal ConvNets customized for eLR videos in order to take advantage of appearance and motion information. Our method outperforms state-of-the-art methods at extremely low resolutions on IXMAS (93:7%) and HMDB (29:2%) datasets.

We propose an approach to indoor occupant localization using a network of single-pixel, visible-light sensors. In addition to preserving privacy, our approach vastly reduces data transmission rate and is agnostic to eavesdropping. We develop two purely data-driven localization algorithms and study their performance using a network of 6 such sensors. In one algorithm, we divide the monitored floor area (2.37m×2.72m) into a 3×3 grid of cells and classify location of a single person as belonging to one of the 9 cells using a support vector machine classifier. In the second algorithm, we estimate person's coordinates using support vector regression. In cross-validation tests in public (e.g., conference room) and private (e.g., home) scenarios, we obtain 67–72% correct classification rate for cells and 0.31–0.35m mean absolute distance error within the monitored space. Given the simplicity of sensors and processing, these are encouraging results and can lead to useful applications today.

Hoarding is a complex and impairing psychiatric disorder and a public health problem. Traditionally it is assessed through observation and interview, but recently a new method has been proposed where living quarters of an individual are visually compared with a set of template images ranked according to the “Clutter Image Rating” (CIR) scale from 1 to 9. However, such an assessment is time-consuming, subjective, and weak in repeatability. We propose an automatic method for classifying hoarding images according to the CIR scale. Since clutter in living quarters (e.g., piles of boxes, newspapers, clothing) corresponds to “busy” areas with lots of edges in captured images, we use the histogram-of-gradients (HOG) descriptor to characterize images and estimate the CIR value using two methods: regression and classification. In 4-fold cross-validation on 620 images that we harvested from the internet, both methods result in mean-absolute CIR error of about 1.2. Given the simplicity of our method, this is an encouraging result as it approximates ratings by trained professionals who admit assigning CIR values within ± 1 CIR point.

A smart room of the future is expected to facilitate intelligent interaction with its occupants while respecting their privacy. Although standard video cameras can be used to learn where the occupants are and what they do, they raise privacy concerns. While this can be mitigated by severely reducing camera resolution, it will also impact the utility of the camera network. This work investigates and quantifies the tradeoff between camera resolution and action recognition accuracy. Rather than building a physical testbed to carry out this study, we use a graphics engine to simulate a room with 5 cameras, and to animate avatars using skeletal movements of real users captured by a Kinect v2 camera. We study resolutions from 100×100 pixels down to 1×1 using a state-of-the-art action recognition method at higher resolutions and we propose a new approach at ultra-low resolutions. In extensive simulations, we conclude that on a dataset of 12 individuals performing 4 actions our algorithm applied to single-pixel data performs very close to the state-of-the-art method applied to 100×100 data, suggesting that reliable action recognition can be achieved without compromising occupant's identity.

Although there has been a significant proliferation of 3D displays in the last decade, the availability of 3D content is still scant compared to the volume of 2D data. To fill this gap, automatic 2D to 3D conversion algorithms are needed. In this paper, we present an automatic approach, inspired by machine learning principles, for estimating the depth of a 2D image. The depth of a query image is inferred from a dataset of color and depth images by searching this repository for images that are photometrically similar to the query. We measure the photometric similarity between two images by comparing their GIST descriptors. Since not all regions in the query image require the same visual attention, we give more weight in the GIST-descriptor comparison to regions with high saliency. Subsequently, we fuse the depths of the most similar images and adaptively filter the result to obtain a depth estimate. Our experimental results indicate that the proposed algorithm outperforms other state-of-the-art approaches on the commonly-used Kinect-NYU dataset.

Depth-sensors, such as the Kinect, have predominately been used as a gesture recognition device. Recent works, however, have proposed using these sensors for user authentication using biometric modalities such as: face, speech, gait and gesture. The last of these modalities - gestures, used in the context of full-body and hand-based gestures, is relatively new but has shown promising authentication performance. In this paper, we focus on hand-based gestures that are performed in-air. We present a novel approach to user authentication from such gestures by leveraging a temporal hierarchy of depth-aware silhouette covariances. Further, we investigate the usefulness of shape and depth information in this modality, as well as the importance of hand movement when performing a gesture. By exploiting both shape and depth information our method attains an average 1.92% Equal Error Rate (EER) on a dataset of 21 users across 4 predefined hand-gestures. Our method consistently outperforms related methods on this dataset.

Since its release, the Kinect has been successfully used in gesture recognition. Recent work has extended Kinect's use towards biometric user authentication based on face, speech, gait, and gestures. Our work expands on the last of these modalities - gestures, which have yielded promising authentication results in prior work. This paper aims to gain insight into how authentication methods that are based on silhouette features compare against those that are based on skeletal features in terms of trade-offs between authentication performance and robustness against some real-world degradations. On a dataset of 40 users that contains two types of degradations namely, user-memory and personal-effects (heavy coats, bags, etc.), we found that for user-defined gestures, skeletal features outperform silhouettes on average by 4.89% in terms of the Equal Error Rate (EER).

User authentication based on biometrics such as fingerprint, iris, face, speech or gait has been around for many years. Recently, intentional user gestures have been shown to be a promising modality for user authentication. However, it is unclear how much of the performance can be attributed to pure biometric information that a user has no control over, such as individual limb lengths, and how much to the gesture dynamics, that a user can fully control. A related question is: How easy is it to copy these dynamics? In this paper, we propose a framework to decompose a gesture into three components: initial posture, limb proportions, and gesture dynamics. We then study the impact of each component and various component combinations on the performance of gesture-based user authentication using a dataset of 36 users performing 3 gestures of varying complexity. We also study spoof attacks using the same dataset and show, somewhat surprisingly, that amateurs are unable to copy gestures with sufficient accuracy so as to significantly degrade the overall authentication performance even when they are trained on users that they are closest to. While training certainly improves an attacker's ability to copy gesture dynamics, it seems that the unique limb proportions (which cannot be altered) and the initial posture (which amateurs attackers fail to pay attention to), more than make up for the loss due to compromised dynamics (which can always be renewed).

Change detection is one of the most commonly encountered low-level tasks in computer vision and video processing. A plethora of algorithms have been developed to date, yet no widely accepted, realistic, large-scale video data set exists for benchmarking different methods. Presented here is a unique change detection video data set consisting of nearly 90 000 frames in 31 video sequences representing six categories selected to cover a wide range of challenges in two modalities (color and thermal infrared). A distinguishing characteristic of this benchmark video data set is that each frame is meticulously annotated by hand for ground-truth foreground, background, and shadow area boundaries-an effort that goes much beyond a simple binary label denoting the presence of change. This enables objective and precise quantitative comparison and ranking of video-based change detection algorithms. This paper discusses various aspects of the new data set, quantitative performance metrics used, and comparative results for over two dozen change detection algorithms. It draws important conclusions on solved and remaining issues in change detection, and describes future challenges for the scientific community. The data set, evaluation tools, and algorithm rankings are available to the public on a website and will be updated with feedback from academia and industry in the future.

The rapid decrease in the dimensions of integrated circuits has necessitated corresponding higher-resolution methods for defect imaging. Current state of the art, defect imaging systems are reaching the limits of their resolution. In this work, we are proposing a new overcomplete dictionary based sparse signal imaging framework to improve the resolution and localization in confocal microscopy systems for backside optical integrated circuit defect imaging. The domain of integrated circuit imaging is particularly suitable for the application of overcomplete dictionaries in an image reconstruction framework because the images are highly structured, containing predictable building blocks derivable from the corresponding computer aided design layouts. This structure provides a strong and natural a-priori dictionary for scene reconstruction. This dictionary prior is coupled with a physically-based observation model to create enhanced scene reconstructions. The approach is described and results on simulated data are provided.

The Kinect has primarily been used as a gesture-driven device for motion-based controls. To date, Kinect-based research has predominantly focused on improving tracking and gesture recognition across a wide base of users. In this paper, we propose to use the Kinect for biometrics; rather than accommodating a wide range of users we exploit each user's uniqueness in terms of gestures. Unlike pure biometrics, such as iris scanners, face detectors, and fingerprint recognition which depend on irrevocable biometric data, the Kinect can provide additional revocable gesture information. We propose a dynamic time-warping (DTW) based framework applied to the Kinect's skeletal information for user access control. Our approach is validated in two scenarios: user identification, and user authentication on a dataset of 20 individuals performing 8 unique gestures. We obtain an overall 4.14%, and 1.89% Equal Error Rate (EER) in user identification, and user authentication, respectively, for a gesture and consistently outperform related work on this dataset. Given the natural noise present in the real-time depth sensor this yields promising results.

We propose a general framework for fast and accurate recognition of actions in video using empirical covariance matrices of features. A dense set of spatio-temporal feature vectors are computed from video to provide a localized description of the action, and subsequently aggregated in an empirical covariance matrix to compactly represent the action. Two supervised learning methods for action recognition are developed using feature covariance matrices. Common to both methods is the transformation of the classification problem in the closed convex cone of covariance matrices into an equivalent problem in the vector space of symmetric matrices via the matrix logarithm. The first method applies nearest-neighbor classification using a suitable Riemannian metric for covariance matrices. The second method approximates the logarithm of a query covariance matrix by a sparse linear combination of the logarithms of training covariance matrices. The action label is then determined from the sparse coefficients. Both methods achieve state-of-the-art classification performance on several datasets, and are robust to action variability, viewpoint changes, and low object resolution. The proposed framework is conceptually simple and has low storage and computational requirements making it attractive for real-time implementation.

Despite a significant growth in the last few years, the availability of 3D content is still dwarfed by that of its 2D counterpart. To close this gap, many 2D-to-3D image and video conversion methods have been proposed. Methods involving human operators have been most successful but also time-consuming and costly. Automatic methods, which typically make use of a deterministic 3D scene model, have not yet achieved the same level of quality for they rely on assumptions that are often violated in practice. In this paper, we propose a new class of methods that are based on the radically different approach of learning the 2D-to-3D conversion from examples. We develop two types of methods. The first is based on learning a point mapping from local image/video attributes, such as color, spatial position, and, in the case of video, motion at each pixel, to scene-depth at that pixel using a regression type idea. The second method is based on globally estimating the entire depth map of a query image directly from a repository of 3D images ( image+depth pairs or stereopairs) using a nearest-neighbor regression type idea. We demonstrate both the efficacy and the computational efficiency of our methods on numerous 2D images and discuss their drawbacks and benefits. Although far from perfect, our results demonstrate that repositories of 3D content can be used for effective 2D-to-3D image conversion. An extension to video is immediate by enforcing temporal continuity of computed depth maps.

The monitoring of coastal environments is of great interest to biologists and environmental protection organizations with video cameras being the dominant sensing modality. However, it is recognized that video analysis of maritime scenes is very challenging on account of background animation (water reflections, waves) and very large field of view. We propose a practical approach to the detection of three salient events, namely boats, motor vehicles and people appearing close to the shoreline, and their subsequent summarization. Our approach consists of three fundamental steps: region-of-interest (ROI) localization by means of behavior subtraction, ROI validation by means of feature-covariance-based object recognition, and event summarization by means of video condensation. The goal is to distill hours of video data down to a few short segments containing only salient events, thus allowing human operators to expeditiously study a coastal scene. We demonstrate the effectiveness of our approach on long videos taken at Great Point, Nantucket, Massachusetts.

Video cameras are extensively used in modern surveillance systems to detect, track, and recognize, objects, people, and anomalies. Their use in user authentication, however, has been limited primarily to close-range face recognition systems. In this paper, we explore user authentication based on gestures captured by a video camera. Unlike pure biometrics, such as fingerprints, iris scans, and faces, gesture-based authentication combines irrevocable biometric information, such as the shapes and relative sizes of body parts, with voluntary movements which can be revoked. Our authentication method applies the empirical feature covariance matrix framework that has previously been used for tracking, face localization, and action recognition, to features extracted from body silhouettes. We have tested the performance of our algorithm in both user classification and user authentication on a database of 20 individuals performing 8 different gestures. We have obtained a 93-99% Correct Classification Rate (CCR) for user classification and a 5-6% Equal Error Rate (EER) for user authentication on single gestures from this dataset. This is a very encouraging result suggesting that gesture-based user authentication may be feasible in scenarios with a limited number of users.

Searching for images on-line using keywords returns results that are often difficult to interpret. This becomes even more complicated if one attempts to compare image search output for several keywords with a common theme. We focus on the latter problem and propose a method to efficiently compare sets of images in order to find representative images, one from each set, that are coherent in certain sense. However, the search for an optimal set of representative images is very complex even for as few as 10 sets of 20 images each since all possible combinations of 10 images need to be considered. Therefore, we formulate our problem as the Generalized Traveling Salesman Problem (GTSP) and propose an efficient approximation algorithm to solve it. Our approximate GTSP algorithm is faster than other well-known approximations and is also more likely to reach the exact solution for large-scale inputs. We present a number of experimental results using the proposed algorithm and conclude that it can be a useful, almost real-time tool for on-line search.

Background subtraction has been a driving engine for many computer vision and video analytics tasks. Although its many variants exist, they all share the underlying assumption that photometric scene properties are either static or exhibit temporal stationarity. While this works in many applications, the model fails when one is interested in discovering changes in scene dynamics instead of changes in scene's photometric properties; the detection of unusual pedestrian or motor traffic patterns are but two examples. We propose a new model and computational framework that assume the dynamics of a scene, not its photometry, to be stationary, i.e., a dynamic background serves as the reference for the dynamics of an observed scene. Central to our approach is the concept of an event, which we define as short-term scene dynamics captured over a time window at a specific spatial location in the camera field of view. Unlike in our earlier work, we compute events by time-aggregating vector object descriptors that can combine multiple features, such as object size, direction of movement, speed, etc. We characterize events probabilistically, but use low-memory, low-complexity surrogates in a practical implementation. Using these surrogates amounts to behavior subtraction, a new algorithm for effective and efficient temporal anomaly detection and localization. Behavior subtraction is resilient to spurious background motion, such as due to camera jitter, and is content-blind, i.e., it works equally well on humans, cars, animals, and other objects in both uncluttered and highly cluttered scenes. Clearly, treating video as a collection of events rather than colored pixels opens new possibilities for video analytics.

We propose a novel framework for automatic saliency estimation in natural images. We consider saliency to be an anomaly with respect to a given context that can be global or local. In the case of global context, we estimate saliency in the whole image relative to a large dictionary of images. Unlike in some prior methods, this dictionary is not annotated, i.e., saliency is assumed unknown. In the case of local context, we partition the image into patches and estimate saliency in each patch relative to a large dictionary of un-annotated patches from the rest of the image. We propose a unified framework that applies to both cases in three steps. First, given an input (image or patch) we extract k nearest neighbors from the dictionary. Then, we geometrically warp each neighbor to match the input. Finally, we derive the saliency map from the mean absolute error between the input and all its warped neighbors. This algorithm is not only easy to implement but also outperforms state-of-the-art methods.

A novel approach to action recognition in video based on the analysis of optical flow is presented. Properties of optical flow useful for action recognition are captured using only the empirical covariance matrix of a bag of features such as flow velocity, gradient, and divergence. The feature covariance matrix is a low-dimensional representation of video dynamics that belongs to a Riemannian manifold. The Riemannian manifold of covariance matrices is transformed into the vector space of symmetric matrices under the matrix logarithm mapping. The log-covariance matrix of a test action segment is approximated by a sparse linear combination of the log-covariance matrices of training action segments using a linear program and the coefficients of the sparse linear representation are used to recognize actions. This approach based on the unique blend of a logcovariance-descriptor and a sparse linear representation is tested on the Weizmann and KTH datasets. The proposed approach attains leave-one-out cross validation scores of 94.4% correct classification rate for the Weizmann dataset and 98.5% for the KTH dataset. Furthermore, the method is computationally efficient and easy to implement.

Action recognition is an important but challenging problem in video analytics with a number of solutions proposed to date. However, even if a reliable model for action representation is identified and an accurate metric for comparing actions is developed, it is still unclear to how many video frames should the representation and comparison apply. In this paper, we develop a method to detect when actions change, i.e., the temporal boundaries of actions, without classifying the actions. We use a silhouette-based framework for action representation and comparison, both centered around dimensionality reduction using covariance descriptors. We use a nonparametric statistical framework to learn the distribution of the distance between covariance descriptors and detect action changes as covariance-distance outliers. Experimental results on ground-truth data show 1.64% false negative error and 0.19% false positive error, while those for surveillance video agree 100% with manual annotations.

The eight papers in this special section span across theoretical and practical considerations of various aspects of distributed camera networks, including adaptive sensing, distributed processing, efficient communications, and versatile implementations.

Background subtraction is a powerful mechanism for detecting change in a sequence of images that finds many applications. The most successful background subtraction methods apply probabilistic models to background intensities evolving in time; nonparametric and mixture-of-Gaussians models are but two examples. The main difficulty in designing a robust background subtraction algorithm is the selection of a detection threshold. In this paper, we adapt this threshold to varying video statistics by means of two statistical models. In addition to a nonparametric background model, we introduce a foreground model based on small spatial neighborhood to improve discrimination sensitivity. We also apply a Markov model to change labels to improve spatial coherence of the detections. The proposed methodology is applicable to other background models as well.

Efficient browsing of long video sequences is a key tool in visual surveillance, e.g., for postevent video forensics, but can also be used for fast review of motion pictures and home videos. While frame skipping (fixed or adaptive) is straightforward to implement, its performance is quite limited. Although more efficient techniques have been developed, such as video summarization and video montage, they lose either the temporal or semantic context of events. A recently proposed method called video synopsis deals with some of these issues but involves multiple processing stages and is fairly complex. Video condensation, that we propose here, is novel in the way information is removed from the space-time video volume, is conceptually simple and relatively easy to implement. We introduce the concept of a video ribbon inspired by that of a seam recently proposed for image resizing. We recursively carve ribbons out by minimizing an activity-aware cost function using dynamic programming. The ribbon model we develop is flexible and permits an easy adjustment of the compromise between temporal condensation ratio and anachronism of events. We also propose sliding-window ribbon carving to handle streaming video and demonstrate the method's efficiency on motor and pedestrian traffic data.

We consider a change detection problem in video surveillance applications and propose busy-idle rates, meaningful and easy to compute features, to characterize the behavior profile of a given pixel. We describe the geometry independence property of these features, and use them to model the typical behavior that is observed in training sequences. Using a small number of samples for each pixel we generate behavior clusters, wherein pixels with similar behavior profiles fall into the same cluster. We then generate probabilistic models corresponding to behavior clusters, and use these models to perform abnormal behavior detection.

Fast and accurate motion detection in the presence of camera jitter is known to be a difficult problem. Existing statistical methods often produce abundant false positives since jitter-induced motion is difficult to differentiate from scene-induced motion. Although frame alignment by means of camera motion compensation can help resolve such ambiguities, the additional steps of motion estimation and compensation increase the complexity of the overall algorithm. In this paper, we address camera jitter by applying background subtraction to scene dynamics instead of scene photometry. In our method, an object is assumed moving if its dynamical behavior is different from the average dynamics observed in a reference sequence. Our method is conceptually simple, fast, requires little memory, and is easy to train, even on videos containing moving objects. It has been tested and performs well on indoor and outdoor sequences with strong camera jitter.

Visual surveillance applications such as object identification, object tracking, and anomaly detection require reliable motion detection as an initial processing step. Such a detection is often accomplished by means of background subtraction which can be as simple as thresholding of intensity difference between movement-free background and current frame. However, more effective background subtraction methods employ probabilistic modeling of the background followed by probability thresholding. In this case, the balance between false positives and false negatives (misses) is controlled by a threshold that needs to be adjusted heuristically depending on object sparsity. In this paper, we propose a different detection method that is based on false discovery rate control, a multiple-comparison procedure that applies thresholding in significance-score rather than probability space. The proposed approach allows explicit control of false positives and automatically adapts to object sparsity. The new method offers a qualitative improvement in real scenarios as well as a measurable performance gain over non-adaptive techniques when tested on synthetic sequences.

Optical flow can be reliably estimated between areas visible in two images, but not in occlusion areas. If optical flow is needed in the whole image domain, one approach is to use additional views of the same scene. If such views are unavailable, an often-used alternative is to extrapolate optical flow in occlusion areas. Since the location of such areas is usually unknown prior to optical flow estimation, this is usually performed in three steps. First, occlusion-ignorant optical flow is estimated, then occlusion areas are identified using the estimated (unreliable) optical flow, and, finally, the optical flow is corrected using the computed occlusion areas. This approach, however, does not permit interaction between optical flow and occlusion estimates. In this paper, we permit such interaction by proposing a variational formulation that jointly computes optical flow, implicitly detects occlusions and extrapolates optical flow in occlusion areas. The extrapolation mechanism is based on anisotropic diffusion and uses the underlying image gradient to preserve structure, such as optical flow discontinuities. Our results show significant improvements in the computed optical flow fields over other approaches, both qualitatively and quantitatively.

Most statistical background subtraction techniques are based on the analysis of temporal color/intensity distribution. However, learning statistics on a series of time frames can be problematic, especially when no frame absent of moving objects is available or when the available memory is not sufficient to store the series of frames needed for learning. In this letter, we propose a spatial variation to the traditional temporal framework. The proposed framework allows statistical motion detection with methods trained on one background frame instead of a series of frames as is usually the case. Our framework includes two spatial background subtraction approaches suitable for different applications. The first approach is meant for scenes having a nonstatic background due to noise, camera jitter or animation in the scene (e.g.,waving trees, fluttering leaves). This approach models each pixel with two PDFs: one unimodal PDF and one multimodal PDF, both trained on one background frame. In this way, the method can handle backgrounds with static and nonstatic areas. The second spatial approach is designed to use as little processing time and memory as possible. Based on the assumption that neighboring pixels often share similar temporal distribution, this second approach models the background with one global mixture of Gaussians.

Disparity estimation belongs to the most important, but difficult, problems in image processing and computer vision. Its importance stems from a wide range of applications, while its difficulty is related to ill-posedness. To date, numerous disparity estimation algorithms have been developed. In this paper, we consider a particular case of disparity estimation based on two views and a known alpha channel partitioning each view into foreground and background. The main idea is to use this partitioning in order to enhance disparity estimation in the foreground object close to its boundary. We propose a block-based disparity model with two alpha-channel constraints: a photometric one, disabling invalid intensity/color matches, and a geometric one, preventing disparity smoothing between foreground and background. We incorporate these constraints into a Bayesian framework using the maximum a posteriori probability criterion. We experimentally demonstrate improvements in the estimated disparities at foreground object boundaries, and show examples of image relighting using these disparities

The dramatic proliferation of visual displays, from cell phones, through video iPods, PDAs, and notebooks, to high-quality HDTV screens, has raised the demand for a video compression scheme capable of decoding a "once-encoded" video at a range of supported video resolutions and with high quality. A promising solution to this problem has been recently proposed in the form of wavelet video coding based on motion-compensated temporal filtering (MCTF); scalability is naturally supported while efficiency is comparable to state-of-the-art hybrid coders. However, although rate (quality) and temporal scalability are natural in mainstream "t+2D" wavelet video coders, spatial scalability suffers from drift problems. In the light of the recently proposed "2D+t+2D" modification, which targets spatial scalability performance, we present a framework for the modeling of spatially-scalable motion that is well matched to this new structure. We propose a motion estimation scheme in which motion fields at different spatial scales are jointly estimated and coded. In addition, at lower spatial resolutions, we extend the block-wise constant motion model to a higher-order model based on cubic splines, effectively creating a "mixture motion model" that combines different models at different supported spatial scales. This advanced spatial modeling of motion significantly improves the coding efficiency of motion at low resolutions and leads to an excellent overall compression performance; spatial scalability performance of the proposed scheme approaches that of a non-scalable coder.

In this paper, we propose a light and fast pixel-based statistical motion detection method based on a background subtraction procedure. The statistical representation of the background relies on its spatial color distributions herein modeled by a mixture of Gaussians. The Gaussian parameters are obtained after segmenting one reference frame with an unsupervised Bayesian approach whose parameter estimation step is ensured by the K-means and the iterated conditional estimation (ICE) algorithms. Since the motion detection function only depends on a global mixture of M Gaussians, only a few bits per pixel need to be stored in memory. Our method achieves real-time performances, especially when look up tables are used to store pre-calculated data. Results have been obtained on synthetic and real video sequences and compared with other statistical methods.

A new type of three-dimensional (3-D) display recently introduced on the market holds great promise for the future of 3-D visualization, communication, and entertainment. This so-called automultiscopic display can deliver multiple views without glasses, thus allowing a limited "look-around" (correct motion-parallax). Central to this technology is the process of multiplexing several views into a single viewable image. This multiplexing is a complex process involving irregular subsampling of the original views. If not preceded by low-pass filtering, it results in aliasing that leads to texture as well as depth distortions. In order to eliminate this aliasing, we propose to model the multiplexing process with lattices, find their parameters and then design optimal anti-alias filters. To this effect, we use multidimensional sampling theory and basic optimization tools. We derive optimal anti-alias filters for a specific automultiscopic monitor using three models: the orthogonal lattice, the nonorthogonal lattice, and the union of shifted lattices. In the first case, the resulting separable low-pass filter offers significant aliasing reduction that is further improved by hexagonal-passband low-pass filter for the nonorthogonal lattice model. A more accurate model is obtained using union of shifted lattices, but due to the complex nature of repeated spectra, practical filters designed in this case offer no additional improvement. We also describe a practical method to design finite-precision, low-complexity filters that can be implemented using modern graphics cards.

We address the issue of image sequence analysis jointly in space and time. While typical approaches to such an analysis consider two image frames at a time, we propose to perform this analysis jointly over multiple frames. We concentrate on spatiotemporal segmentation of image sequences and on analysis of occlusion effects therein. The segmentation process is three-dimensional (3-D); we search for a volume carved out by each moving object in the image sequence domain, or "object tunnel," a new space-time concept. We pose the problem in variational framework by using only motion information (no intensity edges). The resulting formulation can be viewed as volume competition, a 3-D generalization of region competition. We parameterize the unknown surface to be estimated, but rather than using an active-surface approach, we embed it into a higher dimensional function and apply the level-set methodology. We first develop simple models for the detection of moving objects over static background; no motion models are needed. Then, in order to improve segmentation accuracy, we incorporate motion models for objects and background. We further extend the method by including explicit models for occluded and newly exposed areas that lead to "occlusion volumes," another new space-time concept. Since, in this case, multiple volumes are sought, we apply a multiphase variant of the level-set method. We present various experimental results for synthetic and natural image sequences.

Motion-compensated temporal filtering implemented using lifting is an effective and efficient temporal decomposition tool that facilitates video compression competitive with the current standards. As recently shown, however, in order that a lifting-based motion-compensated discrete wavelet transform indeed implements the intended filtering along motion trajectories, motion transformation must be invertible and motion composition between frames must be well-defined. A departure from these conditions results in the application of sub-optimal subband decomposition filters which, in turn, degrades coding performance, even if prediction-step energy is minimized during motion estimation. We study the impact of motion field invertibility error on the coding performance of an MCTF/DWT video coder. We propose two new motion field inversion methods and compare them to previously reported inversion techniques. We also compare coding results for all inversion algorithms with those of coding based on triangular meshes that are inherently invertible. Our results show that a significant improvement in coding performance is possible with more accurate motion field inversion.

The knowledge of occlusions and newly-exposed areas, a natural consequence of changing object juxtaposition in a 3D scene, can be effectively used to improve video coding efficiency, video rate conversion quality and view interpolation fidelity. Although various occlusion estimation methods have been proposed to date, most of them are not robust or are computationally complex. In this paper, we study two simple, well-known occlusion estimation methods, one based on a photometric mismatch between two frames of an image sequence, while the other based on a geometric mismatch. We demonstrate their weaknesses and propose a new geometric method that exhibits good robustness to noise in the data while maintaining low computational complexity.

This paper presents a novel approach to the reconstruction of images from nonuniformly spaced samples. This problem is often encountered in digital image processing applications. Nonrecursive video coding with motion compensation, spatiotemporal interpolation of video sequences, and generation of new views in multicamera systems are three possible applications. We propose a new reconstruction algorithm based on a spline model for images. We use regularization, since this is an ill-posed inverse problem. We minimize a cost function composed of two terms: one related to the approximation error and the other related to the smoothness of the modeling function. All the processing is carried out in the space of spline coefficients; this space is discrete, although the problem itself is of a continuous nature. The coefficients of regularization and approximation filters are computed exactly by using the explicit expressions of B-spline functions in the time domain. The regularization is carried out locally, while the computation of the regularization factor accounts for the structure of the nonuniform sampling grid. The linear system of equations obtained is solved iteratively. Our results show a very good performance in motion-compensated interpolation applications.

Motion compensation has been widely used in both DCT- and wavelet-based video coders for years. The recent success of the temporal wavelet transform based on motion-compensated lifting suggests that a high-performance, scalable wavelet video coder may soon outperform the best DCT-based coders. However, motion-compensated lifting does not implement exactly its transversal equivalent unless certain conditions on motion are satisfied. We review those conditions, and we discuss their importance. We derive a new class of temporal transforms, the so-called 1-N transversal or (N,0) lifting transforms, that are particularly interesting if those conditions on motion are not satisfied. We compare experimentally the 1-3 and 5-3 motion compensated wavelet transforms for the ubiquitous block-motion model used in all video compression standards. For this model, the 1-3 transform outperforms the 5-3 transform due to the need to transmit additional motion information in the latter case. This interesting result, however, does not extend to motion models satisfying the transversal/lifting equivalence conditions.

Discrete wavelet transforms, implemented using lifting along motion trajectories, are effective and efficient temporal decomposition tools that facilitate video compression competitive with the current standards. As recently shown, however, in order that a lifting-based motion-compensated wavelet transform be equivalent to its transversal (standard) implementation, motion transformation must be invertible and motion composition between frames must be well-defined. In this paper, we discuss various mesh-based motion models that satisfy requirements of invertibility and composition, and thus are suitable for use in motion-compensated lifting-based wavelet transforms. We propose a new mesh configuration that preserves regularity of the mesh structure but provides better motion compensation compared to previously-reported mesh topologies, particularly in the proximity of image boundaries. Our results show that an improvement in motion compensation and overall compression performance is possible with only a fractional increase in motion overhead bit-rate.

Spatial segmentation of image sequences is usually computed based on motion between two frames. Some recent approaches extend this to joint segmentation in space-time; the resulting 3D segmentation (in x-y-t space) can be interpreted as a volume "carved out" by a moving object in the image sequence domain, or the so-called "object tunnel". We extend this concept to explicit modeling of occlusion events in the x-y-t space. In addition to the modeling of object evolution, we also model occluded and newly-exposed areas in the background and in the object by means of an "occlusion volume", a new space-time concept. We propose a variational formulation of the problem that we solve using the multiphase level set method. We show experimental results for synthetic and natural image sequences.

Lifting-based implementations of various discrete wavelet transforms applied in the temporal direction under motion compensation have recently become a very powerful tool in video compression research. We present in this paper a theoretical analysis of motion compensation in both transversal and lifted implementations of such transforms. We derive conditions for perfect reconstruction in the case of motion-compensated transversal discrete wavelet transform. We also derive conditions on motion transformation assuring that a motion-compensated lifting scheme is exactly equivalent to its transversal counterpart. In general, these conditions require that motion transformation allow composition and be invertible. Unfortunately, many motion models do not obey these properties, thus inducing subband decomposition errors (prior to compression). We propose an alternative approach to motion compensation in the case of Haar transform. This new approach poses no constraints on motion; motion-compensated lifted Haar transform exactly implements its transversal implementation, and the latter obeys perfect reconstruction, both regardless of motion transformation used. This new approach, however, does not extend to the 5/3 or any higher-order discrete wavelet transform.

Spatial video segmentation is usually performed based on motion between two frames. Some recent approaches extend this to joint segmentation in space-time; the resulting 3-D segmentation can be interpreted as a volume "carved out" by a moving object in the image sequence domain, or the so-called "object tunnel". In this paper, we extend this concept to explicit modeling of occlusion events in space-time. In addition to the modeling of object evolution, we also explicitly model occluded and newly-exposed areas in the background by means of "occlusion volume", a new space-time concept. A voxel belongs to occlusion volume if its intensity is consistent with past intensities along its motion trajectory but inconsistent with future intensities (reversed for "exposed volume"). We propose a variational formulation of the problem that we solve using the multiphase level set method. We show encouraging experimental results for synthetic and natural image sequences.

In this paper, we propose a new variational formulation for simultaneous multiple motion segmentation and occlusion detection in an image sequence. For the representation of segmented regions, we use the multiphase level set method proposed by Vese and Chan. This method allows an efficient representation of up to 2^L regions with L level-set functions. Moreover, by construction, it enforces a domain partition with no gaps and overlaps. This is unlike previous variational approaches to multiple motion segmentation, where additional constraints were needed. The variational framework we propose can incorporate an arbitrary number of motion transformations as well as occlusion areas. In order to minimize the resulting energy, we developed a two-step algorithm. In the first step, we use a feature-based method to estimate the motions present in the image sequence. In the second step, based on the extracted motion information, we iteratively evolve all level set functions in the gradient descent direction to find the final segmentation. We have tested the above algorithm on both synthetic- and natural-motion data with very promising results. We show here segmentation results for two real video sequences.

The reconstruction of a regularly-sampled image from irregularly-spaced samples is a stumbling block in various video processing tasks. In the past, we have developed a POCS-based (projection onto convex sets) reconstruction method that applies two operators sequentially: bandwidth limitation and sample substitution. Although the method works well, we have observed an interesting paradox: wide-band filtering results in better-looking images, but lower PSNR values, than narrow-band filtering (increased blur). This can be explained by a too-short impulse response of the wide-band filter unable to "fill-in" the missing samples in sparsely populated areas. In this paper, we propose an improved version of our algorithm where linear shift-invariant (LSI) filtering is replaced by linear shift-variant (LSV) filtering. The LSV filtering is implemented as a parallel bank of LSI filters, each with different bandwidth (impulse response). We demonstrate experimentally a significant reduction of the reconstruction error due to the new LSV filtering.

Segmentation of motion in an image sequence is one of the most challenging problems in image processing, while at the same time one that finds numerous applications. To date, a wealth of approaches to motion segmentation have been proposed. Many of them suffer from the local nature of the models used. Global models, such as those based on Markov random fields, perform, in general, better. In this paper, we propose a new approach to motion segmentation that is based on a global model. The novelty of the approach is twofold. First, inspired by recent work of other researchers we formulate the problem as that of region competition, but we solve it using the level set methodology. The key features of a level set representation, as compared to active contours, often used in this context, are its ability to handle variations in the topology of the segmentation and its numerical stability. The second novelty of the paper is the formulation in which, unlike in many other motion segmentation algorithms, we do not use intensity boundaries as an accessory; the segmentation is purely based on motion. This permits accurate estimation of motion boundaries of an object even when its intensity boundaries are hardly visible. Since occasionally intensity boundaries may prove beneficial, we extend the formulation to account for the coincidence of motion and intensity boundaries. In addition, we generalize the approach to multiple motions. We discuss possible discretizations of the evolution (PDE) equations and we give details of an initialization scheme so that the results could be duplicated. We show numerous experimental results for various formulations on natural images with either synthetic or natural motion.

We study properties of the discrete cosine transform (DCT) when applied to an image sequence formed by uniformly translating a still image. The Fourier transform (FT) applied to such a sequence has non-zero content only on a spatio-temporal frequency plane orthogonal to the direction of motion. We derive an equivalent spectrum for the DCT case. The spectrum function is more complicated than in the FT case and cannot be easily interpreted analytically. However, its numerical evaluation demonstrates that spectral occupancy in the DCT domain is limited to a narrow band around a plane similar to one in the FT case with two important differences: the plane is subject to folding, and the DCT coefficient amplitude is strongly attenuated for larger temporal "frequencies". We verify the theoretical derivations experimentally on images. The obtained result opens an interesting possibility for the computation of constant-velocity motion in the DCT domain. We demonstrate some preliminary results of motion estimation in the 3D DCT domain by identifying directions of spectral occupancy with respect to transform coefficients.

We address the issue of joint space-time segmentation of image sequences. Typical approaches to such segmentation consider two image frames at a time, and perform tracking of individual segments across time. We propose to perform this segmentation jointly over multiple frames. This leads to a 3D segmentation, i.e., a search for a volume "carved out" by a moving object in the (3D) image sequence domain. We pose the problem in a Bayesian framework and use the MAP criterion. Under suitable structural and segmentation/motion models we convert MAP estimation to a functional minimization. The resulting problem can be viewed as volume competition, a 3D generalization of region competition. We parameterize the unknown surface to be estimated, but rather than solving for it using an active-surface approach, we embed it into a higher-dimensional function and use the level-set methodology. We show experimental results for the simpler case of object motion against a still background although, given suitable models, the general formulation can handle complex motion too.

We are concerned with the reconstruction of a regularly-sampled image based on irregularly-spaced samples thereof. We propose a new iterative method based on a cubic spline representation of the image. An objective function taking into account the similarity to the known samples and the regularity of the function is minimized in order to obtain a good approximation. We apply the developed algorithm to motion-compensated image interpolation. Under motion compensation, the resulting sampling grids are irregular and require irregular/regular interpolation. We show experimental results on real-world images and we compare our results with other methods proposed in the literature.

Region-based functionality offered by the MPEG-4 video compression standard is also appealing for still images, for example to permit object-based queries of a still-image database. A popular method for still-image compression is fractal coding. However, traditional fractal image coding uses rectangular range and domain blocks. Although new schemes have been proposed that merge small blocks into irregular shapes, the merging process does not, in general, produce semantically-meaningful regions. We propose a new approach to fractal image coding that permits region-based functionalities; images are coded region by region according to a previously-computed segmentation map. We use rectangular range and domain blocks, but divide boundary blocks into segments belonging to different regions. Since this prevents the use of standard dissimilarity measure, we propose a new measure adapted to segment shape. We propose two approaches: one in the spatial and one in the transform domain. While providing additional functionality, the proposed methods perform similarly to other tested methods in terms of PSNR but often result in images that are subjectively better. Due to the limited domain-block codebook size, the new methods are faster than other fractal coding methods tested. The results are very encouraging and show the potential of this approach for various internet and still-image database applications.

We address the problem of fast computation of level set partial differential equations (PDEs) in the context of motion segmentation. Although several fast level set computation algorithms are known, some of them, such as the fast marching method, are not applicable to the video segmentation problem since the front being computed does not advance monotonically. We study narrow-banding, pyramidal and a pyramidal/narrow-banding schemes that leads to a 70-fold time gain over the single-resolution scheme. 1.

This paper presents a new approach to the tracking of regions in an image sequence. Unlike most other methods, the proposed approach can handle topology changes, i.e., regions may split or merge. This flexibility is naturally embedded into a partial differential equation that solves a minimum description length (MDL) estimation problem. The basic estimation criterion consists of only two terms: the description length of the region shape mismatch and the description length of the region itself, but we show possible extensions to this basic formulation. We minimize the MDL criterion using the level set methodology that inherently accounts for topology changes. We show results for natural data with natural as well as synthetic motion.

This paper presents a method for the reconstruction of a regularly-sampled image from its irregularly-spaced samples. Such reconstruction is often needed in image processing and coding, for example when using motion compensation. The proposed approach is based on the theory of projections onto convex sets. Two projection operators are used: bandwidth limitation and sample substitution. The approach is similar to some methods presented in the literature in the past, but differs in the implementation. The bandwidth limitation is implemented in the frequency domain on an oversampled grid thus allowing substantial flexibility in spectrum shaping of the reconstructed image. Additionally, a fast Fourier transform algorithm specifically designed for irregularly-sampled images is used to reduce the computational complexity. A number of experimental results on natural images are presented.

We are concerned with the reconstruction of a regularly-sampled image based on irregularly-spaced samples thereof. We propose a new iterative method based on a wavelet representation of the image. For this representation we use a biorthogonal spline wavelet basis implemented on an oversampled grid. We apply the developed algorithm to disparity-compensated stereoscopic image interpolation. Under disparity compensation, the resulting sampling grids are irregular and require the irregular/regular interpolation. We show the experimental results on real-world images and we compare our results with other methods proposed in the literature.

In this paper, we propose an efficient, robust, and fast method for the estimation of global motion from image sequences. The method is generic in that it can accommodate various global motion models, from a simple translation to an eight-parameter perspective model. The algorithm is hierarchical and consists of three stages. In the first stage, a low-pass image pyramid is built. Then, an initial translation is estimated with full-pixel precision at the top of the pyramid using a modified n-step search matching. In the third stage, a gradient descent is executed at each level of the pyramid starting from the initial translation at the coarsest level. Due to the coarse initial estimation and the hierarchical implementation, the method is very fast. To increase robustness to outliers, we replace the usual formulation based on a quadratic error criterion with a truncated quadratic function. We have applied the algorithm to various test sequences within an MPEG-4 coding system. From the experimental results we conclude that global motion estimation provides significant performance gains for video material with camera zoom and/or pan. The gains result from a reduced prediction error and a more compact representation of motion. We also conclude that the robust error criterion can introduce additional performance gains without increasing computational complexity.

Stereoscopic visualization systems based on liquid crystal shutter (LCS) eyewear and cathode-ray tube (CRT) displays provide today the best overall quality of three-dimensional (3-D) images and therefore have a dominant position in commercial as well as professional markets. Due to the CRT and LCS characteristics, however, such systems suffer from perceptual crosstalk ("shadows") at object boundaries that can reduce, and at times inhibit, the ability to perceive depth. In this paper, we propose a method to reduce such crosstalk. We present a simple model for intensity leak, we assess model parameters for a time-sequential LCS/CRT system and we propose a computationally efficient algorithm to eliminate the crosstalk. Since the full crosstalk elimination implies an unacceptable image degradation (reduction of contrast), we study the tradeoff between crosstalk elimination and image contrast. We describe experiments on synthetic and natural stereoscopic images and we discuss informal subjective viewing of processed images. Overall, the viewer response has been very positive; 3-D perception of many objects became either much easier or even effortless. Since the proposed algorithm can be easily implemented in real time (only linear scaling and table look-up are needed), we believe that it can be successfully used today in various stereoscopic applications suffering from image crosstalk. This is particularly true for PC-based 3-D viewing where the algorithm can be executed by the CPU or by an advanced graphics board.

This paper presents a new algorithm for the reconstruction of intermediate views from a pair of still stereoscopic images. The algorithm is designed to address the issue of blur caused by linear filtering often employed in such reconstruction. The proposed algorithm is block-based and to reconstruct the intermediate views employs nonlinear disparity-compensated filtering by means of a winner-take-all strategy. The reconstructed image is modeled as a tiling by fixed-size blocks coming from various positions (disparity compensation) of either the left or right images, while the tiling map itself is modeled by a binary decision field. In addition to that, an observation model relating the left and right images via a disparity field, and a disparity field model are used. All models are probabilistic and are combined into a maximum a posteriori probability criterion. The intermediate intensities, disparities and the binary decision field are estimated jointly using the expectation-maximization algorithm. The new approach is compared experimentally on complex natural images with a reference block-based algorithm employing linear filtering. Although the improvements are localized and often subtle, they demonstrate that a high-quality intermediate view reconstruction for complex scenes is feasible.

The significant effort to provide region-based compression and functionality within the MPEG-4 standard is not paralleled in the still-image compression domain. In this paper, we propose an approach to fractal coding of still images that is truly region-based. Unlike previous fractal compression methods the proposed approach compresses an image region-by-region based on a prior segmentation, very much like in MPEG-4; individual regions can be decoded without full image decoding. The method performs the domain/range block matching in frequency domain using a shape-adaptive discrete cosine transform. Experimental results evaluating the performance of the approach are shown.

Motion segmentation is an important problem in video processing and compression, and in computer vision. It is usually performed by either first estimating a field of motion parameters and then segmenting it, or by applying joint motion estimation and segmentation. Motion segmentation methods often constrain the set of possible solutions by forcing motion discontinuities to coincide with intensity discontinuities. In this paper, we propose an iterative method for joint motion estimation and segmentation that is based on level sets. The motion within individual segments is parametric and the method does not use the intensity discontinuity constraint, but is shown to be accurate for images with both synthetic and natural motion compliant with the assumed motion models.

Region-based approaches to image and video compression have been very actively explored in the last few years. It is widely expected that they will result in rate/quality gains and expanded functionalities. In such approaches, one of the essential problems is the representation of luminance and color in arbitrarily shaped regions. For rectangular blocks extracted from natural images, the discrete cosine transform (DCT) has been found to perform close to the eigentransform. Although for arbitrarily shaped regions orthogonalization-based procedures have been shown to perform very well, their computational complexity and memory requirements are prohibitive for today's technology. Therefore, other approaches are presently investigated, and particular attention is paid to low implementation complexity. In this paper, we propose a new class of orthogonal transforms that self-adapt to arbitrary shapes. The new algorithms are derived from flow graphs of standard fast transform algorithms by a suitable modification of certain butterfly operators. First, we show how to derive a shape-adaptive transform from the discrete Walsh-Hadamard transform (DWHT) flow graph. Then, we discuss modifications needed to arrive at a DCT-based shape adaptive transform. We give implementation details of this transform, and compare its computational complexity with several well-known approaches. We also evaluate the energy compaction performance of the new transform for both synthetic and natural data. We conclude that the proposed DCT-based shape-adaptive transform gives a very beneficial compaction/complexity ratio compared to other well-known approaches. The complexity of the new method does not exceed the complexity of two nonadaptive DCT's on a circumscribing rectangle, and therefore, unlike other tested methods with comparable energy compaction, it is suitable for large regions. This property should prove very valuable in the future when true region-based image/video compression methods are developed.

We propose a new method for the encoding of label images (also known as segmentation maps or alpha planes) that are often used to identify object location in region-based image and video coders. The method is contour-based and lossless with a contour model composed of two parts: a contour graph describing the topology of the contour network and a directional chain code to deal with the geometric part of the label image (internal contour points). The graph-based description of the topology is designed to minimize the cost of encoding the nodes, while the directional chain codes are compressed by arithmetic coding. The approach is flexible since separating the contour network into topological and geometrical parts allows the use of other lossless or lossy methods to encode the geometric part without changing the graph representation. The proposed method has been compared with an arithmetic encoder used in MPEG-4.

This paper presents a supervised algorithm for estimating the unknown nonlinearity undergone by the three color components of an image in the image acquisition process. The algorithm is based on the rank-one hypothesis, which postulates that the linear tristimulus values in a region of uniform surface color lie on a straight line through the origin. An objective function is formulated whose minimization yields the estimate of the unknown nonlinearity. Images corrected with the estimated inverse nonlinearity are shown to exhibit chromatic properties that are much more piecewise constant that in the original image. This property will be very useful in quantization and segmentation applications.

In a typical disparity (or motion) estimation algorithm developed for interimage prediction, an interpolation of intensities is applied to one of the two images used. Therefore, nonfiltered intensities of the image being predicted are compared with low-pass-filtered intensities of the other image of the stereo pair. Consequently, noise and detail suppression in the two images are unequal. In this paper we propose to apply the same (balanced) filtering to both images. In addition to image smoothing that helps avoid unreliable intensity matches, a low-pass filter is used to carry out intensity interpolation at the same time; the computation of subpixel attributes is consistent with low-pass filtering of both images unlike arbitrary linear or cubic interpolation applied to one image only. The proposed approach lends itself naturally to a multiresolution implementation, We apply the new approach to stereo disparity estimation based on sliding blocks. Using synthetic and natural data we experimentally compare the new approach with the traditional sliding-block method. For standard stereoscopic images we demonstrate up to 2.4 dB reduction of disparity-compensated prediction error over the traditional sliding-block method.

This paper presents an approach to the segmentation of video sequences that is inspired by Markov random field (MRF) models and is aimed at region-based video compression. Two goals of the segmentation algorithm are considered: to assure a rate-efficient partitioning of video sequences and to provide regions that are meaningful for human observers ("coding for content"). To address both issues we extend our earlier work; we incorporate a segmentation complexity measure to account for the rate allocated to region shape, we use a robust error criterion to reject outliers in the intensity residual and we incorporate a temporal consistency constraint to assure the continuity of segmentation in time. We demonstrate improvements in the segmentation for real videoconferencing sequences.

The goal of this paper is to study the application of two-dimensional (2-D) finite-precision infinite impulse response (IIR) filters to enhanced National Television System Committee (NTSC) coding. It is well-known that suitable twoor three-dimensional (3-D) digital filtering greatly improves the quality of NTSC pictures by suppressing the interference between the luminance Y and the chrominances I, Q. Thus far, 2-D and 3-D finite impulse response (FIR) filters have been used to reduce or eliminate these cross effects. To achieve good performance, however, they require many coefficients. Since, in general, IIR filters need fewer coefficients to approximate a given magnitude response, we investigate the possibility of applying 2-D IIR filters to the NTSC encoding/decoding. We also study the feasibility of using digital filters for NTSC channel filtering; this would permit a digital-only encoder. To design suitable filters, we use a method based on multiple constraint optimization and simulated annealing. We propose a new implementation structure for the IIR filters that differs from the zero-phase FIR structure. We simulate the full NTSC coding chain and compare the resulting images for both filter types.

This paper presents a new temporal interpolation algorithm based on segmentation of images into polygonal regions undergoing affine motion. The goal of this work is to improve upon the block-based interpolation used in MPEG (B-frames). We briefly describe the region-based framework and the temporal linking algorithm that jointly provide the segmentation and motion parameters. We also present various applications of the proposed algorithm to temporal interpolative prediction. We examine one of these schemes in detail, including the special processing of occlusion areas. Results are illustrated by predicted images and using the MSE criterion we compare their quality with other schemes.

Region-based video compression has been a very active research area over the last few years. It has been viewed as a potential alternative to traditional schemes suffering from the "blockiness" of image intensities at very low bit rates. We present a new approach to region-based representation and motion estimation. It is based on the observation that motion boundaries usually coincide with region boundaries. Thus, we first compute an intensity-based image partition and use it as an initial step in a 3-step algorithm: motion estimation for intensity-derived regions, motion-based region fusion and adjustment of region boundaries. We present experimental results for standard QCIF images and compare our method with block matching and dense motion field estimation. We also study the performance loss due to a lossy transmission of partition information.

This paper is concerned with linear transforms for arbitrarily-shaped image segments. In contrast to other techniques described in the literature, the proposed transform is based upon a stochastic model of image covariance within the considered region. Emerging from a separable stationary Markov model proposed for rectangular regions, we derive a non-stationary Markov model with natural boundary conditions. We compute its eigentransform, which is the optimum linear transform under a broad variety of performance measures. For the special case of a rectangular region, the method yields the DCT basis functions. Simulation results for natural imagery are provided.

This paper is concerned with the estimation of trajectories for accelerated motion from image sequences. Unlike in many other approaches, that assume linear trajectories, we propose a quadratic model that incorporates both velocity and acceleration. This model corresponds better to practical applications especially when the estimation is performed over several images, e.g., in motion-compensated processing with extended temporal support. This is due to the fact that over longer time frame and in the presence of acceleration, quadratic trajectory is capable of providing a better intensity match than a simple displacement. The algorithm for the estimation of dense accelerated motion fields is formulated in this paper using regularization and the solution is based on deterministic relaxation implemented over a pyramid of resolutions. Extensive experimental results for test images with synthetic motion are presented.>

In this paper we propose a new approach to motion-compensated filtering of image sequences that contain time-varying illumination. There are two contributions in this paper. First, we propose a new method for the estimation of dense 2-D motion that is robust to time-varying illumination often present in images. We define the structural model that is based on the assumption of intensity gradient constancy along motion trajectories. This is in contrast to the usual hypothesis of the intensity constancy. Secondly, we apply the proposed approach to motion-compensated temporal interpolation. We compare the image reconstruction error obtained using the new approach with the error obtained for standard models.>

The problem of designing finite precision one-dimensional infinite impulse response (IIR) digital filters for video processing is addressed. The design algorithm is based on simultaneous minimization of magnitude, phase, and stability errors in a discrete space of solutions using simulated annealing. It is demonstrated that the approach results in filters characterized by a substantially reduced nonlinearity of the phase response in filter passband, which is critical in any video processing application. To reduce image degradations due to ripples of the filter step response, another error term is introduced into the cost function. It is demonstrated that this additional term permits significant reduction of step response overshoots, and thus the visibility of degradations in a filtered image. The designed IIR filters are compared with their finite impulse response (FIR) counterparts in terms of characteristic parameters as well as distortion visibility in processed images.>

A stochastic approach to the estimation of 2D motion vector fields from time-varying images is presented. The formulation involves the specification of a deterministic structural model along with stochastic observation and motion field models. Two motion models are proposed: a globally smooth model based on vector Markov random fields and a piecewise smooth model derived from coupled vector-binary Markov random fields. Two estimation criteria are studied. In the maximum a posteriori probability (MAP) estimation, the a posteriori probability of motion given data is maximized, whereas in the minimum expected cost (MEC) estimation, the expectation of a certain cost function is minimized. Both algorithms generate sample fields by means of stochastic relaxation implemented via the Gibbs sampler. Two versions are developed: one for a discrete state space and the other for a continuous state space. The MAP estimation is incorporated into a hierarchical environment to deal efficiently with large displacements.>

The problem of designing finite precision one-dimensional infinite impulse response (IIR) filters with prescribed magnitude, phase, and stability constraints is studied. The design problem is formulated as the minimization of a cost function incorporating these conflicting requirements. The first two elements of the cost function express magnitude and group delay errors between the desired and the actual frequency responses of a filter, while the third one is related to its stability margin. This cost function is minimized using simulated annealing based on the Metropolis (1953) algorithm. Examples of several finite wordlength filters designed by the above method are presented and compared with Chebyshev and elliptic filters with rounded coefficients.>

An extension of the Bayesian estimation of 2-D motion in spatiotemporally sampled image sequences is presented by incorporating the color cue into the estimation process. Instead of scalar image intensity, three-component vector representation of color images is used, thus allowing Y-C1-C2, RGB, or other formats. The maximum a posteriori probability estimation is shown to result in a three-term energy minimizationj. A white Gaussian noise model is used for the displaced pel differences of each image component, and a coupled vector-binary Markov random field model is used for displacement and discontinuity fields. The resulting criterion is optimized using the method of discrete state-space simulated annealing. Improvements in the quality of estimated displacement fields due to additional color information are demonstrated through several experimental results.>

Presents a probabilistic formulation for motion estimation in images and a stochastic algorithm for minimization of the associated objective function. It is shown that motion estimation, an ill-posed problem, can be regularized by means of a Bayesian estimation approach. The unknown motion field is modeled as a two-dimensional vector Markov random field with a certain neighbourhood system. The posterior distribution of the motion field given image observations is then a Gibbs distribution. Maximization of this a posteriori probability to obtain the MAP estimate of the motion field is achieved by simulated annealing. Results of the estimation procedure applied to television sequences with natural motion are presented.>