Structure from Motion: Beyond the Epipolar Constraint

The classic approach to structure from motion entails a clear separation between motion estimation and structure estimation and between two-dimensional (2D) and three-dimensional (3D) information. For the recovery of the rigid transformation between different views only 2D image measurements are used. To have available enough information, most existing techniques are based on the intermediate computation of optical flow which, however, poses a problem at the locations of depth discontinuities. If we knew where depth discontinuities were, we could (using a multitude of approaches based on smoothness constraints) accurately estimate flow values for image patches corresponding to smooth scene patches; but to know the discontinuities requires solving the structure from motion problem first. This paper introduces a novel approach to structure from motion which addresses the processes of smoothing, 3D motion and structure estimation in a synergistic manner. It provides an algorithm for estimating the transformation between two views obtained by either a calibrated or uncalibrated camera. The results of the estimation are then utilized to perform a reconstruction of the scene from a short sequence of images.The technique is based on constraints on image derivatives which involve the 3D motion and shape of the scene, leading to a geometric and statistical estimation problem. The interaction between 3D motion and shape allows us to estimate the 3D motion while at the same time segmenting the scene. If we use a wrong 3D motion estimate to compute depth, we obtain a distorted version of the depth function. The distortion, however, is such that the worse the motion estimate, the more likely we are to obtain depth estimates that vary locally more than the correct ones. Since local variability of depth is due either to the existence of a discontinuity or to a wrong 3D motion estimate, being able to differentiate between these two cases provides the correct motion, which yields the least varying estimated depth as well as the image locations of scene discontinuities. We analyze the new constraints, show their relationship to the minimization of the epipolar constraint, and present experimental results using real image sequences that indicate the robustness of the method.     

Efficient Fourier-Based Approach for Detecting Orientations and Occlusions in Epipolar Plane Images for 3D Scene Modeling

This paper presents a Fourier-based approach for automatically constructing a 3D panoramic model of a natural scene from a video sequence. The video sequences could be captured by an unstabilized camera mounted on a moving platform on a common road surface. As the input of the algorithms, seamles panoramic view images (PVIs) and epipolar plane images (EPIs) are generated after image stabilization if the camera is unstabilized. A novel panoramic EPI analysis method is proposed that combines the advantages of both PVIs and EPIs efficiently in three important steps: locus orientation detection in the Fourier frequency domain, motion boundary localization in the spatio-temporal domain, and occlusion/resolution recovery only at motion boundaries. The Fourier energy-based approaches in literature were usually for low-level local motion analysis and are therefore not accurate for 3D reconstruction and are also computationally expensive. Our panoramic EPI analysis approach is both accurate and efficient for 3D reconstruction. Examples of layered panoramic representations for large-scale 3D scenes from real world video sequences are given.     

CLSS: An Intelligent Crane Lorry Scheduling System

Companies that provide crane-lorry services are faced with the daily need to perform vehicle and driver allocation and scheduling. Many companies still do this manually due to the lack of suitable technologies. This manual approach is both time consuming and inaccurate and most probably will not lead to an optimized plan that can reduce operational costs. In this paper, we describe the design of a system called Crane Lorry Scheduling System (CLSS) that we have developed for the largest crane lorry company in Hong Kong. A crane lorry company is a company that provides lorries with different types of mounted crane equipment and drivers to service different types of moving and lifting jobs. CLSS is a Web-based application that streamlines communication with customers, subcontractors and employees/lorry drivers. We modeled the lorry-assignment problem as a constraint-satisfaction problem (CSP) algorithm, which we call the Crane Lorry Optimizing Engine (CLOE). CLOE was designed to be easily customizable to match the needs and requirements of different crane lorry companies. We experimented with two versions of CLOE, regular CLOE that finds best solutions and X-CLOE that finds optimal solutions. Results from our tests show that CLOE is faster and generates better quality plans than the manual approach.     

Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems

In recent years, constraint satisfaction techniques have been successfully applied to disjunctive scheduling problems, i.e., scheduling problems where each resource can execute at most one activity at a time. Less significant and less generally applicable results have been obtained in the area of cumulative scheduling. Multiple constraint propagation algorithms have been developed for cumulative resources but they tend to be less uniformly effective than their disjunctive counterparts. Different problems in the cumulative scheduling class seem to have different characteristics that make them either easy or hard to solve with a given technique. The aim of this paper is to investigate one particular dimension along which problems differ. Within the cumulative scheduling class, we distinguish between highly disjunctive and highly cumulative problems: a problem is highly disjunctive when many pairs of activities cannot execute in parallel, e.g., because many activities require more than half of the capacity of a resource; on the contrary, a problem is highly cumulative if many activities can effectively execute in parallel. New constraint propagation and problem decomposition techniques are introduced with this distinction in mind. This includes an O(n²) edge-finding algorithm for cumulative resources (where n is the number of activities requiring the same resource) and a problem decomposition scheme which applies well to highly disjunctive project scheduling problems. Experimental results confirm that the impact of these techniques varies from highly disjunctive to highly cumulative problems. In the end, we also propose a refined version of the edge-finding algorithm for cumulative resources which, despite its worst case complexity in O(n³) , performs very well on highly cumulative instances.     

Compression of stereoscopic images using pyramid and prune DCT encoding

This paper details a compression system for stereoscopic (3-D) images that takes advantage of the disparity compensation effect by heavily compressing one image and a lightly compressing the other. Two methods were tried for the creation of the heavily compressed image: Lossy Pyramid coding and Pruned Discrete Cosine Transform (PDCT) with Variable Length Coding VLC. Both versions of the program used a lightly quantized PDCT image for the clear image.A detailed explanation of the algorithms, the effect of compression level, and the effect of compression method on stereoscopic perception is presented. A method of creating a pseudo 3-D image from a single image is also discussed.     

Guided Genetic Algorithm and its Application to Radio Link Frequency Assignment Problems

The Guided Genetic Algorithm (GCA) is a hybrid of Genetic Algorithm and Guided Local Search, a meta–heuristic search algorithm. As the search progresses, GGA modifies both the fitness function and fitness template of candidate solutions based on feedback from constraints. The fitness template is then used to bias crossover and mutation. The Radio Link Frequency Assignment Problem (RLFAP) is a class of problem that has practical relevance to both military and civil applications. In this paper, we show how GGA can be applied to the RLFAP. We focus on an abstraction of a real life military application that involves the assigning of frequencies to radio links. GGA was tested on a set of eleven benchmark problems provided by the French military. This set of problems has been studied intensively by a number of prominent groups in Europe. It covers a variety of needs in military applications, including the satisfaction of constraints, finding optimal solutions that satisfy all the constraints and optimization of some objective functions whenever no solution exist (partial constraint satisfaction). Not only do these benchmark problems vary in problem nature, they are reasonably large for military applications (up to 916 variables, and up to 5548 constraints). This makes them a serious challenge to the generality, reliability as well as efficiency of algorithms. We show in this paper that GGA is capable of producing excellent results reliably in the whole set of benchmark problems.     

A General Framework for the Selection of World Coordinate Systems in Perspective and Catadioptric Imaging Applications

An imaging system with a single effective viewpoint is called a central projection system. The conventional perspective camera is an example of central projection system. A catadioptric realization of omnidirectional vision combines reflective surfaces with lenses. Catadioptric systems with an unique projection center are also examples of central projection systems. Whenever an image is acquired, points in 3D space are mapped into points in the 2D image plane. The image formation process represents a transformation from ³ to ², and mathematical models can be used to describe it. This paper discusses the definition of world coordinate systems that simplify the modeling of general central projection imaging. We show that an adequate choice of the world coordinate reference system can be highly advantageous. Such a choice does not imply that new information will be available in the images. Instead the geometric transformations will be represented in a common and more compact framework, while simultaneously enabling newer insights. The first part of the paper focuses on static imaging systems that include both perspective cameras and catadioptric systems. A systematic approach to select the world reference frame is presented. In particular we derive coordinate systems that satisfy two differential constraints (the compactness and the decoupling constraints). These coordinate systems have several advantages for the representation of the transformations between the 3D world and the image plane. The second part of the paper applies the derived mathematical framework to active tracking of moving targets. In applications of visual control of motion the relationship between motion in the scene and image motion must be established. In the case of active tracking of moving targets these relationships become more complex due to camera motion. Suitable world coordinate reference systems are defined for three distinct situations: perspective camera with planar translation motion, perspective camera with pan and tilt rotation motion, and catadioptric imaging system rotating around an axis going through the effective viewpoint and the camera center. Position and velocity equations relating image motion, camera motion and target 3D motion are derived and discussed. Control laws to perform active tracking of moving targets using visual information are established.     

General Convergence Results for Linear Discriminant Updates

The problem of learning linear-discriminant concepts can be solved by various mistake-driven update procedures, including the Winnow family of algorithms and the well-known Perceptron algorithm. In this paper we define the general class of quasi-additive algorithms, which includes Perceptron and Winnow as special cases. We give a single proof of convergence that covers a broad subset of algorithms in this class, including both Perceptron and Winnow, but also many new algorithms. Our proof hinges on analyzing a generic measure of progress construction that gives insight as to when and how such algorithms converge.Our measure of progress construction also permits us to obtain good mistake bounds for individual algorithms. We apply our unified analysis to new algorithms as well as existing algorithms. When applied to known algorithms, our method automatically produces close variants of existing proofs (recovering similar bounds)—thus showing that, in a certain sense, these seemingly diverse results are fundamentally isomorphic. However, we also demonstrate that the unifying principles are more broadly applicable, and analyze a new class of algorithms that smoothly interpolate between the additive-update behavior of Perceptron and the multiplicative-update behavior of Winnow.     

Surface representation for the graphical display of structured data

In many applications one has a set of discrete points at which some variable such as pressure or velocity is measured. In order to graphically represent and display such data (say, as contours of constant pressure), the discrete data must be represented by a smooth function. This continuous surface can then be evaluated at any point for graphical display. Sometimes data are arbitrarily located except that they occur along non-intersecting lines, an example occurring in wind tunnel tests where data are recorded at plug taps on an aircraft body. An algorithm is developed for this type of structured data problem and illustrated by means of color computer graphics.     

Baseline Detection and Localization for Invisible Omnidirectional Cameras

Two key problems for camera networks that observe wide areas with many distributed cameras are self-localization and camera identification. Although there are many methods for localizing the cameras, one of the easiest and most desired methods is to estimate camera positions by having the cameras observe each other; hence the term self-localization. If the cameras have a wide viewing field, e.g. an omnidirectional camera, and can observe each other, baseline distances between pairs of cameras and relative locations can be determined. However, if the projection of a camera is relatively small on the image of other cameras and is not readily visible, the baselines cannot be detected. In this paper, a method is proposed to determine the baselines and relative locations of these invisible cameras. The method consists of two processes executed simultaneously: (a) to statistically detect the baselines among the cameras, and (b) to localize the cameras by using information from (a) and propagating triangle constraints. Process (b) works for the localization in the case where the cameras are observed each other, and it does not require complete observation among the cameras. However, if many cameras cannot be observed each other because of the poor image resolution, it dose not work. The baseline detection by process (a) solves the problem. This methodology is described in detail and results are provided for several scenarios.     

Design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems

This paper describes a unified variational theory for design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems for shape, nonshape, material and mechanical properties selection, as well as control problems. The concept of an adjoint system, the principle of virtual work and a Lagrangian-Eulerian formulation to describe the deformations and the design variations are used to develop a unified view point. A general formula for design sensitivity analysis is derived and interpreted for usual performance functionals. Analytical examples are utilized to demonstrate the use of the theory and give insights for application to more complex problems that must be treated numerically.Derivatives The comma notation for partial derivatives is used, i.e. G,_u = G/u. An upper dot represents material time derivative, i.e. ü = ²u/t². A prime implies derivative with respect to the time measured in the reference time-domain, i.e. u = du/d.     

EigenTracking: Robust Matching and Tracking of Articulated Objects Using a View-Based Representation

This paper describes an approach for tracking rigid and articulated objects using a view-based representation. The approach builds on and extends work on eigenspace representations, robust estimation techniques, and parameterized optical flow estimation. First, we note that the least-squares image reconstruction of standard eigenspace techniques has a number of problems and we reformulate the reconstruction problem as one of robust estimation. Second we define a subspace constancy assumption that allows us to exploit techniques for parameterized optical flow estimation to simultaneously solve for the view of an object and the affine transformation between the eigenspace and the image. To account for large affine transformations between the eigenspace and the image we define a multi-scale eigenspace representation and a coarse-to-fine matching strategy. Finally, we use these techniques to track objects over long image sequences in which the objects simultaneously undergo both affine image motions and changes of view. In particular we use this EigenTracking technique to track and recognize the gestures of a moving hand.     

Characterization of desirable properties of general database decompositions

The classical theory of acyclicity of universal relational schemata identifies a set of desirable properties of such schemata, and then shows that all of these properties are equivalent to one another, and in turn equivalent to certain acyclicity characterizations of a hypergraph underlying the schema. The desirable properties include the simplicity of constraints, the correctness of certain efficient query evaluation algorithms, and the complexity of maintaining the integrity of a decomposed database. The principal result of this paper is to show that the essence of this result may be extended to a much more general setting; namely, that in which database schemata are just sets and database mappings just functions. Rather than identifying a single desirability class, our work shows that there are several, all of which collapse to a common group when restricted to the universal relational setting. Particularly, the classical notions of pairwise consistency implies global consistency and hypergraph acyclicity are not equivalent in the general case, but rather are independent of each other, and may be considered separately or in combination, to yield varying strengths of desirability.     

Cockpit cognition: Education,the military and cognitive engineering

The goals of public education, as well as conceptions of human intelligence and learning, are undergoing a transformation through the application of military-sponsored information technologies and information processing models of human thought. Recent emphases in education on thinking skills, learning strategies, and computer-based technologies are the latest episodes in the postwar military agenda to engineer intelligent components, human and artificial, for the optimal performance of complex technological systems. Public education serves increasingly as a human factors laboratory and production site for this military enterprise, whose high performance technologies and command and control paradigms have also played central roles in the emergence of the information economy.Our final hope is to develop the brain as a natural resource ... Human intelligence will be the weapon of the future.Luis Alberto MachadoThis paper will also appear, under the title Mental Material inCyborg Worlds: The Military Information Society, eds. Les Levidow and Kevin Robins, London: Free Association Press, (in press).     

Driving saccade to pursuit using image motion

Within the context of active vision, scant attention has been paid to the execution of motion saccades—rapid re-adjustments of the direction of gaze to attend to moving objects. In this paper we first develop a methodology for, and give real-time demonstrations of, the use of motion detection and segmentation processes to initiate capture saccades towards a moving object. The saccade is driven by both position and velocity of the moving target under the assumption of constant target velocity, using prediction to overcome the delay introduced by visual processing. We next demonstrate the use of a first order approximation to the segmented motion field to compute bounds on the time-to-contact in the presence of looming motion. If the bound falls below a safe limit, a panic saccade is fired, moving the camera away from the approaching object. We then describe the use of image motion to realize smooth pursuit, tracking using velocity information alone, where the camera is moved so as to null a single constant image motion fitted within a central image region. Finally, we glue together capture saccades with smooth pursuit, thus effecting changes in both what is being attended to and how it is being attended to. To couple the different visual activities of waiting, saccading, pursuing and panicking, we use a finite state machine which provides inherent robustness outside of visual processing and provides a means of making repeated exploration. We demonstrate in repeated trials that the transition from saccadic motion to tracking is more likely to succeed using position and velocity control, than when using position alone.     

Solving Various Weighted Matching Problems with Constraints

This paper studies the resolution of (augmented) weighted matching problems within a constraint programming (CP) framework. The first contribution of the paper is a set of techniques that improves substantially the performance of branch-and-bound algorithms based on constraint propagation and the second contribution is the introduction of weighted matching as a global constraint ( WeightedMatching), that can be propagated using specialized incremental algorithms from Operations Research. We first compare programming techniques that use constraint propagation with specialized algorithms from Operations Research, such as the Busaker and Gowen flow algorithm or the Hungarian method. Although CP is shown not to be competitive with specialized polynomial algorithms for pure matching problems, the situation is different as soon as the problems are modified with additional constraints. Using the previously mentioned set of techniques, a simpler branch-and-bound algorithm based on constraint propagation can outperform a complex specialized algorithm. These techniques have been applied with success to the Traveling Salesman Problems [5], which can be seen as an augmented matching problem. We also show that an incremental version of the Hungarian method can be used to propagate a WeightedMatching constraint. This is an extension to the weighted case of the work of Régin [19], which we show to bring significant improvements on a timetabling example.     

A Comparison of Two Approaches to Ranking Algorithms Used to Compute Hill Slopes

The calculation of slope (downhill gradient) for a point in a digital elevation model (DEM) is a common procedure in the hydrological, environmental and remote sensing sciences. The most commonly used slope calculation algorithms employed on DEM topography data make use of a three-by-three search window or kernel centered on the grid point (grid cell) in question in order to calculate the slope at that point. A comparison of eight such slope calculation algorithms has been carried out using an artificial DEM, consisting of a smooth synthetic test surface with various amounts of added Gaussian noise. Morrison's Surface III, a trigonometrically defined surface, was used as the synthetic test surface. Residual slope grids were calculated by subtracting the slope grids produced by the algorithms on test from true/reference slope grids derived by analytic partial differentiation of the synthetic surface. The resulting residual slope grids were used to calculate root-mean-square (RMS) residual error estimates that were used to rank the slope algorithms from best (lowest value of RMS residual error) to worst (largest value of RMS residual error). Fleming and Hoffers method gave the best results for slope estimation when values of added Gaussian noise were very small compared to the mean smooth elevation difference (MSED) measured within three-by-three elevation point windows on the synthetic surface. Horns method (used in ArcInfo GRID) performed better than Fleming and Hoffers as a slope estimator when the noise amplitude was very much larger than the MSED. For the large noise amplitude situation the best overall performing method was that of Sharpnack and Akin. The popular Maximum Downward Gradient Method (MDG) performed poorly coming close to last in the rankings, for both situations, as did the Simple Method. A nonogram was produced in terms of standard deviation of the Gaussian noise and MSED values that gave the locus of the trade-off point between Fleming and Hoffers and Horns methods.     

Pushing Convertible Constraints in Frequent Itemset Mining

Recent work has highlighted the importance of the constraint-based mining paradigm in the context of frequent itemsets, associations, correlations, sequential patterns, and many other interesting patterns in large databases. Constraint pushing techniques have been developed for mining frequent patterns and associations with antimonotonic, monotonic, and succinct constraints. In this paper, we study constraints which cannot be handled with existing theory and techniques in frequent pattern mining. For example, avg(S)v, median(S)v, sum(S)v (S can contain items of arbitrary values, {<, <, , } and v is a real number.) are customarily regarded as tough constraints in that they cannot be pushed inside an algorithm such as Apriori. We develop a notion of convertible constraints and systematically analyze, classify, and characterize this class. We also develop techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining. Results from our detailed experiments show the effectiveness of the techniques developed.     

Expert Estimation of Web-Development Projects: Are Software Professionals in Technical Roles More Optimistic Than Those in Non-Technical Roles?

Estimating the effort required to complete web-development projects involves input from people in both technical (e.g., programming), and non-technical (e.g., user interaction design) roles. This paper examines how the employees' role and type of competence may affect their estimation strategy and performance. An analysis of actual web-development project data and results from an experiment suggest that people with technical competence provided less realistic project effort estimates than those with less technical competence. This means that more knowledge about how to implement a requirement specification does not always lead to better estimation performance. We discuss, amongst others, two possible reasons for this observation: (1) Technical competence induces a bottom-up, construction-based estimation strategy, while lack of this competence induces a more outside view of the project, using a top-down estimation strategy. An outside view may encourage greater use of the history of previous projects and reduce the bias towards over-optimism. (2) Software professionals in technical roles perceive that they are evaluated as more skilled when providing low effort estimates. A consequence of our findings is that the choice of estimation strategy, estimation evaluation criteria and feedback are important aspects to consider when seeking to improve estimation accuracy.