TY - JOUR T1 - A Fast Bilinear Structure from Motion Algorithm Using a Video Sequence and Inertial Sensors JF - IEEE Transactions on Pattern Analysis and Machine Intelligence Y1 - 2011 A1 - Ramachandran, M. A1 - Veeraraghavan,A. A1 - Chellapa, Rama KW - 3D urban modeling KW - algorithms KW - Artificial intelligence KW - CAMERAS KW - computer vision. KW - Convergence KW - fast bilinear structure KW - Google StreetView research data set KW - Image Interpretation, Computer-Assisted KW - Image reconstruction KW - Image sensors KW - Image sequences KW - Imaging, Three-Dimensional KW - inertial sensors KW - Information Storage and Retrieval KW - Linear systems KW - minimization KW - MOTION KW - motion algorithm KW - Motion estimation KW - multiple view geometry KW - Pattern Recognition, Automated KW - Sensors KW - SfM equations KW - sparse bundle adjustment algorithm KW - structure from motion KW - Three dimensional displays KW - vertical direction KW - Video Recording KW - video sequence KW - video signal processing AB - In this paper, we study the benefits of the availability of a specific form of additional information-the vertical direction (gravity) and the height of the camera, both of which can be conveniently measured using inertial sensors and a monocular video sequence for 3D urban modeling. We show that in the presence of this information, the SfM equations can be rewritten in a bilinear form. This allows us to derive a fast, robust, and scalable SfM algorithm for large scale applications. The SfM algorithm developed in this paper is experimentally demonstrated to have favorable properties compared to the sparse bundle adjustment algorithm. We provide experimental evidence indicating that the proposed algorithm converges in many cases to solutions with lower error than state-of-art implementations of bundle adjustment. We also demonstrate that for the case of large reconstruction problems, the proposed algorithm takes lesser time to reach its solution compared to bundle adjustment. We also present SfM results using our algorithm on the Google StreetView research data set. VL - 33 SN - 0162-8828 CP - 1 M3 - 10.1109/TPAMI.2010.163 ER - TY - JOUR T1 - Robust Height Estimation of Moving Objects From Uncalibrated Videos JF - IEEE Transactions on Image Processing Y1 - 2010 A1 - Jie Shao A1 - Zhou,S. K A1 - Chellapa, Rama KW - algorithms KW - Biometry KW - Calibration KW - EM algorithm KW - geometric properties KW - Geometry KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - Imaging, Three-Dimensional KW - least median of squares KW - least squares approximations KW - MOTION KW - motion information KW - multiframe measurements KW - Pattern Recognition, Automated KW - Reproducibility of results KW - Robbins-Monro stochastic approximation KW - robust height estimation KW - Sensitivity and Specificity KW - Signal Processing, Computer-Assisted KW - stochastic approximation KW - Subtraction Technique KW - tracking data KW - uncalibrated stationary camera KW - uncalibrated videos KW - uncertainty analysis KW - vanishing point KW - video metrology KW - Video Recording KW - video signal processing AB - This paper presents an approach for video metrology. From videos acquired by an uncalibrated stationary camera, we first recover the vanishing line and the vertical point of the scene based upon tracking moving objects that primarily lie on a ground plane. Using geometric properties of moving objects, a probabilistic model is constructed for simultaneously grouping trajectories and estimating vanishing points. Then we apply a single view mensuration algorithm to each of the frames to obtain height measurements. We finally fuse the multiframe measurements using the least median of squares (LMedS) as a robust cost function and the Robbins-Monro stochastic approximation (RMSA) technique. This method enables less human supervision, more flexibility and improved robustness. From the uncertainty analysis, we conclude that the method with auto-calibration is robust in practice. Results are shown based upon realistic tracking data from a variety of scenes. VL - 19 SN - 1057-7149 CP - 8 M3 - 10.1109/TIP.2010.2046368 ER - TY - JOUR T1 - Temporal Summaries: Supporting Temporal Categorical Searching, Aggregation and Comparison JF - IEEE Transactions on Visualization and Computer Graphics Y1 - 2009 A1 - Wang,T. D A1 - Plaisant, Catherine A1 - Shneiderman, Ben A1 - Spring, Neil A1 - Roseman,D. A1 - Marchand,G. A1 - Mukherjee,V. A1 - Smith,M. KW - Aggregates KW - Collaborative work KW - Computational Biology KW - Computer Graphics KW - Data analysis KW - data visualisation KW - Data visualization KW - Databases, Factual KW - Displays KW - Event detection KW - Filters KW - Heparin KW - History KW - Human computer interaction KW - Human-computer interaction KW - HUMANS KW - Information Visualization KW - Interaction design KW - interactive visualization technique KW - Medical Records Systems, Computerized KW - Pattern Recognition, Automated KW - Performance analysis KW - Springs KW - temporal categorical data visualization KW - temporal categorical searching KW - temporal ordering KW - temporal summaries KW - Thrombocytopenia KW - Time factors AB - When analyzing thousands of event histories, analysts often want to see the events as an aggregate to detect insights and generate new hypotheses about the data. An analysis tool must emphasize both the prevalence and the temporal ordering of these events. Additionally, the analysis tool must also support flexible comparisons to allow analysts to gather visual evidence. In a previous work, we introduced align, rank, and filter (ARF) to accentuate temporal ordering. In this paper, we present temporal summaries, an interactive visualization technique that highlights the prevalence of event occurrences. Temporal summaries dynamically aggregate events in multiple granularities (year, month, week, day, hour, etc.) for the purpose of spotting trends over time and comparing several groups of records. They provide affordances for analysts to perform temporal range filters. We demonstrate the applicability of this approach in two extensive case studies with analysts who applied temporal summaries to search, filter, and look for patterns in electronic health records and academic records. VL - 15 SN - 1077-2626 CP - 6 M3 - 10.1109/TVCG.2009.187 ER - TY - JOUR T1 - A 3D shape constraint on video JF - IEEE Transactions on Pattern Analysis and Machine Intelligence Y1 - 2006 A1 - Hui Ji A1 - Fermüller, Cornelia KW - 3D motion estimation KW - algorithms KW - Artificial intelligence KW - CAMERAS KW - decoupling translation from rotation KW - Estimation error KW - Fluid flow measurement KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - Image reconstruction KW - Imaging, Three-Dimensional KW - Information Storage and Retrieval KW - integration of motion fields KW - Layout KW - minimisation KW - Minimization methods KW - Motion estimation KW - multiple motion fields KW - parameter estimation KW - Pattern Recognition, Automated KW - Photography KW - practical constrained minimization KW - SHAPE KW - shape and rotation. KW - shape vectors KW - stability KW - structure estimation KW - surface normals KW - Three-dimensional motion estimation KW - video 3D shape constraint KW - Video Recording KW - video signal processing AB - We propose to combine the information from multiple motion fields by enforcing a constraint on the surface normals (3D shape) of the scene in view. The fact that the shape vectors in the different views are related only by rotation can be formulated as a rank = 3 constraint. This constraint is implemented in an algorithm which solves 3D motion and structure estimation as a practical constrained minimization. Experiments demonstrate its usefulness as a tool in structure from motion providing very accurate estimates of 3D motion. VL - 28 SN - 0162-8828 CP - 6 M3 - 10.1109/TPAMI.2006.109 ER - TY - JOUR T1 - MCMC Data Association and Sparse Factorization Updating for Real Time Multitarget Tracking with Merged and Multiple Measurements JF - IEEE Transactions on Pattern Analysis and Machine Intelligence Y1 - 2006 A1 - Zia Khan A1 - Balch, T. A1 - Dellaert, F. KW - algorithms KW - approximate inference KW - Artificial intelligence KW - auxiliary variable particle filter KW - Computational efficiency KW - continuous state space KW - downdating KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - Inference algorithms KW - Information Storage and Retrieval KW - laser range scanner KW - laser range scanner. KW - Least squares approximation KW - least squares approximations KW - Least squares methods KW - linear least squares KW - Markov chain Monte Carlo KW - Markov processes KW - MCMC data association KW - merged measurements KW - Monte Carlo methods KW - Movement KW - multiple merged measurements KW - multitarget tracking KW - particle filter KW - particle filtering (numerical methods) KW - Particle filters KW - Pattern Recognition, Automated KW - probabilistic model KW - QR factorization KW - Radar tracking KW - Rao-Blackwellized KW - real time multitarget tracking KW - Reproducibility of results KW - Sampling methods KW - Sensitivity and Specificity KW - sensor fusion KW - sparse factorization updating KW - sparse least squares KW - State-space methods KW - Subtraction Technique KW - target tracking KW - updating AB - In several multitarget tracking applications, a target may return more than one measurement per target and interacting targets may return multiple merged measurements between targets. Existing algorithms for tracking and data association, initially applied to radar tracking, do not adequately address these types of measurements. Here, we introduce a probabilistic model for interacting targets that addresses both types of measurements simultaneously. We provide an algorithm for approximate inference in this model using a Markov chain Monte Carlo (MCMC)-based auxiliary variable particle filter. We Rao-Blackwellize the Markov chain to eliminate sampling over the continuous state space of the targets. A major contribution of this work is the use of sparse least squares updating and downdating techniques, which significantly reduce the computational cost per iteration of the Markov chain. Also, when combined with a simple heuristic, they enable the algorithm to correctly focus computation on interacting targets. We include experimental results on a challenging simulation sequence. We test the accuracy of the algorithm using two sensor modalities, video, and laser range data. We also show the algorithm exhibits real time performance on a conventional PC VL - 28 SN - 0162-8828 CP - 12 ER - TY - JOUR T1 - MCMC-based particle filtering for tracking a variable number of interacting targets JF - IEEE Transactions on Pattern Analysis and Machine Intelligence Y1 - 2005 A1 - Zia Khan A1 - Balch, T. A1 - Dellaert, F. KW - algorithms KW - Animals KW - Artificial intelligence KW - Computer simulation KW - Computer vision KW - Filtering KW - filtering theory KW - HUMANS KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - Index Terms- Particle filters KW - Information Storage and Retrieval KW - Insects KW - interacting targets KW - Markov chain Monte Carlo sampling step KW - Markov chain Monte Carlo. KW - Markov chains KW - Markov processes KW - Markov random field motion KW - Markov random fields KW - Models, Biological KW - Models, Statistical KW - Monte Carlo Method KW - Monte Carlo methods KW - MOTION KW - Movement KW - multitarget filter KW - multitarget tracking KW - particle filtering KW - Particle filters KW - Particle tracking KW - Pattern Recognition, Automated KW - Sampling methods KW - Subtraction Technique KW - target tracking KW - Video Recording AB - We describe a particle filter that effectively deals with interacting targets, targets that are influenced by the proximity and/or behavior of other targets. The particle filter includes a Markov random field (MRF) motion prior that helps maintain the identity of targets throughout an interaction, significantly reducing tracker failures. We show that this MRF prior can be easily implemented by including an additional interaction factor in the importance weights of the particle filter. However, the computational requirements of the resulting multitarget filter render it unusable for large numbers of targets. Consequently, we replace the traditional importance sampling step in the particle filter with a novel Markov chain Monte Carlo (MCMC) sampling step to obtain a more efficient MCMC-based multitarget filter. We also show how to extend this MCMC-based filter to address a variable number of interacting targets. Finally, we present both qualitative and quantitative experimental results, demonstrating that the resulting particle filters deal efficiently and effectively with complicated target interactions. VL - 27 SN - 0162-8828 CP - 11 ER - TY - JOUR T1 - Motion segmentation using occlusions JF - IEEE Transactions on Pattern Analysis and Machine Intelligence Y1 - 2005 A1 - Ogale, A. S A1 - Fermüller, Cornelia A1 - Aloimonos, J. KW - 3D motion estimation KW - algorithms KW - Artificial intelligence KW - CAMERAS KW - Computer vision KW - Filling KW - hidden feature removal KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - image motion KW - Image motion analysis KW - Image segmentation KW - Layout KW - MOTION KW - Motion detection KW - Motion estimation KW - motion segmentation KW - Movement KW - Object detection KW - occlusion KW - occlusions KW - optical flow KW - ordinal depth KW - Pattern Recognition, Automated KW - Photography KW - Reproducibility of results KW - segmentation KW - Semiconductor device modeling KW - Sensitivity and Specificity KW - video analysis. KW - Video Recording AB - We examine the key role of occlusions in finding independently moving objects instantaneously in a video obtained by a moving camera with a restricted field of view. In this problem, the image motion is caused by the combined effect of camera motion (egomotion), structure (depth), and the independent motion of scene entities. For a camera with a restricted field of view undergoing a small motion between frames, there exists, in general, a set of 3D camera motions compatible with the observed flow field even if only a small amount of noise is present, leading to ambiguous 3D motion estimates. If separable sets of solutions exist, motion-based clustering can detect one category of moving objects. Even if a single inseparable set of solutions is found, we show that occlusion information can be used to find ordinal depth, which is critical in identifying a new class of moving objects. In order to find ordinal depth, occlusions must not only be known, but they must also be filled (grouped) with optical flow from neighboring regions. We present a novel algorithm for filling occlusions and deducing ordinal depth under general circumstances. Finally, we describe another category of moving objects which is detected using cardinal comparisons between structure from motion and structure estimates from another source (e.g., stereo). VL - 27 SN - 0162-8828 CP - 6 M3 - 10.1109/TPAMI.2005.123 ER - TY - JOUR T1 - Visual tracking and recognition using appearance-adaptive models in particle filters JF - IEEE Transactions on Image Processing Y1 - 2004 A1 - Zhou,Shaohua Kevin A1 - Chellapa, Rama A1 - Moghaddam, B. KW - adaptive filters KW - adaptive noise variance KW - algorithms KW - appearance-adaptive model KW - Artificial intelligence KW - Cluster Analysis KW - Computer Graphics KW - Computer simulation KW - Feedback KW - Filtering KW - first-order linear predictor KW - hidden feature removal KW - HUMANS KW - Image Enhancement KW - Image Interpretation, Computer-Assisted KW - image recognition KW - Information Storage and Retrieval KW - Kinematics KW - Laboratories KW - Male KW - Models, Biological KW - Models, Statistical KW - MOTION KW - Movement KW - Noise robustness KW - Numerical Analysis, Computer-Assisted KW - occlusion analysis KW - Particle filters KW - Particle tracking KW - Pattern Recognition, Automated KW - Predictive models KW - Reproducibility of results KW - robust statistics KW - Sensitivity and Specificity KW - Signal Processing, Computer-Assisted KW - State estimation KW - statistical analysis KW - Subtraction Technique KW - tracking KW - Training data KW - visual recognition KW - visual tracking AB - We present an approach that incorporates appearance-adaptive models in a particle filter to realize robust visual tracking and recognition algorithms. Tracking needs modeling interframe motion and appearance changes, whereas recognition needs modeling appearance changes between frames and gallery images. In conventional tracking algorithms, the appearance model is either fixed or rapidly changing, and the motion model is simply a random walk with fixed noise variance. Also, the number of particles is typically fixed. All these factors make the visual tracker unstable. To stabilize the tracker, we propose the following modifications: an observation model arising from an adaptive appearance model, an adaptive velocity motion model with adaptive noise variance, and an adaptive number of particles. The adaptive-velocity model is derived using a first-order linear predictor based on the appearance difference between the incoming observation and the previous particle configuration. Occlusion analysis is implemented using robust statistics. Experimental results on tracking visual objects in long outdoor and indoor video sequences demonstrate the effectiveness and robustness of our tracking algorithm. We then perform simultaneous tracking and recognition by embedding them in a particle filter. For recognition purposes, we model the appearance changes between frames and gallery images by constructing the intra- and extrapersonal spaces. Accurate recognition is achieved when confronted by pose and view variations. VL - 13 SN - 1057-7149 CP - 11 M3 - 10.1109/TIP.2004.836152 ER -