An Algebraic Approach to Camera Self-Calibration

This paper describes a new self-calibration method for a single camera undergoing general motions. It has the following main contributions. First, we establish new constraints which relate the intrinsic parameters of the camera to the rotational part of the motions. This derivation is purely algebraic. We propose an algorithm which simultaneously solves for camera calibration and the rotational part of motions. Second, we provide a comparison between the developed method and a Kruppa equation-based method. Extensive experiments on both synthetic and real image data show the reliability and outperformance of the proposed method. The practical contribution of the method is its interesting convergence property compared with that of the Kruppa equations method.     

Practical Algorithms for Deciding Path Ordering Constraint Satisfaction

We introduce new algorithms for deciding the satisfiability of constraints for the full recursive path ordering with status (RPO), and hence as well for other path orderings like LPO, MPO, KNS and RDO, and for all possible total precedences and signatures. The techniques are based on a new notion of solved form, where fundamental properties of orderings like transitivity and monotonicity are taken into account. Apart from simplicity and elegance from the theoretical point of view, the main contribution of these algorithms is on efficiency in practice. Since guessing is minimized, and, in particular, no linear orderings between the subterms are guessed, a practical improvement in performance of several orders of magnitude over previous algorithms is obtained, as shown by our experiments.     

A Monadic Second-Order Definition of the Structure of Convex Hypergraphs

We consider finite hypergraphs with hyperedges defined as sets of vertices of unbounded cardinality. Each such hypergraph has a unique modular decomposition, which is a tree, the nodes of which correspond to certain subhypergraphs (induced by certain sets of vertices called strong modules) of the considered hypergraph. One can define this decomposition by monadic second-order (MS) logical formulas. Such a hypergraph is convex if the vertices are linearly ordered in such a way that the hyperedges form intervals. Our main result says that the unique linear order witnessing the convexity of a prime hypergraph (i.e., of one, the modular decomposition of which is trivial) can be defined in MS logic. As a consequence, we obtain that if a set of bipartite graphs that correspond (in the usual way) to convex hypergraphs has a decidable monadic second-order theory (which means that one can decide whether a given MS formula is satisfied in some graph of the set) then it has bounded clique-width. This yields a new case of validity of a conjecture which is still open.     

Test Sets for the Universal and Existential Closure of Regular Tree Languages

Finite test sets are a useful tool for deciding the membership problem for the universal closure of a given tree language, that is, for deciding whether a term has all its ground instances in the given language. A uniform test set for the universal closure must serve the following purpose: In order to decide membership of a term, it is sufficient to check whether all its test set instances belong to the underlying language. A possible application, and our main motivation, is ground reducibility, an essential concept for many approaches to inductive reasoning. Ground reducibility modulo some rewrite system is membership in the universal closure of the set of reducible ground terms. Here, test sets always exist, and several algorithmic approaches are known. The resulting sets, however, are often unnecessarily large. In this paper we consider regular languages and linear closure operators. We prove that universal as well as existential closure, defined analogously, preserve regularity. By relating test sets to tree automata and to appropriate congruence relations, we show how to characterize, how to compute, and how to minimize ground and non-ground test sets. In particular, optimal solutions now replace previous ad hoc approximations for the ground reducibility problem.     

Constructive Hypervolume Modeling

This paper deals with modeling point sets with attributes. A point set in a geometric space of an arbitrary dimension is a geometric model of a real/abstract object or process under consideration. An attribute is a mathematical model of an object property of arbitrary nature (material, photometric, physical, statistical, etc.) defined at any point of the point set. We provide a brief survey of different modeling techniques related to point sets with attributes. It spans such different areas as solid modeling, heterogeneous objects modeling, scalar fields or “implicit surface” modeling and volume graphics. Then, on the basis of this survey we formulate requirements to a general model of hypervolumes (multidimensional point sets with multiple attributes). A general hypervolume model and its components such as objects, operations, and relations are introduced and discussed. A function representation (FRep) is used as the basic model for the point set geometry and attributes represented independently using real-valued scalar functions of several variables. Each function defining the geometry or an attribute is evaluated at the given point by a procedure traversing a constructive tree structure with primitives in the leaves and operations in the nodes of the tree. This reflects the constructive nature of the symmetric approach to modeling geometry and associated attributes in multidimensional space. To demonstrate a particular application of the proposed general model, we consider in detail the problem of texturing, introduce a model of constructive hypervolume texture, and then discuss its implementation, as well as the special modeling language we used for modeling hypervolume objects.     

Optimal Deterministic Protocols for Mobile Robots on a Grid

This paper studies a system of m robots operating in a set of n work locations connected by aisles in a × grid, where m≤n. From time to time the robots need to move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse a grid edge at the same time; (2) a robot's sensory capability is limited to detecting the presence of another robot at a neighboring node. We present a deterministic protocol that, for any small constant ε>0, allows m≤(1-ε)n robots to visit their target locations in O( ) time, where each robot visits no more than d≤n targets and no target is visited by more than one robot. We also prove a lower bound showing that our protocol is optimal. Prior to this paper, no optimal protocols were known for d>1. For d=1, optimal protocols were known only for m≤ , while for general m≤n only a suboptimal randomized protocol was known.     

Building Detection from Multiple Aerial Images in Dense Urban Areas

In this paper we present a novel approach for building detection from multiple aerial images in dense urban areas. The approach is based on accurate surface reconstruction, followed by extraction of building façades that are used as a main cue for building detection. For the façade detection, a simple but nevertheless flexible and robust algorithm is proposed. It is based on the observation that building façades correspond to the accumulation of 3D data, available from different views, in object space. Knowledge-driven thresholding of 3D data accumulators followed by Hough transform-based segment detection results in the extraction of façade positions. Three-dimensional planar regions resulting from surface reconstruction procedure and bounded by the extracted façades are detected as building hypotheses through testing a set of spatial criteria. Then, a set of verification criteria is proposed for the hypothesis confirmation.     

Rollback-Dependency Trackability: A Minimal Characterization and Its Protocol

Considering a checkpoint and communication pattern, the rollback-dependency trackability (RDT) property stipulates that there is no hidden dependency between local checkpoints. In other words, if there is a dependency between two checkpoints due to a noncausal sequence of messages (Z-path), then there exists a causal sequence of messages (C-path) that doubles the noncausal one and that establishes the same dependency.This paper introduces the notion of RDT-compliance. A property defined on Z-paths is RDT-compliant if the causal doubling of Z-paths having this property is sufficient to ensure RDT. Based on this notion, the paper provides examples of such properties. Moreover, these properties are visible, i.e., they can be tested on the fly. One of these properties is shown to be minimal with respect to visible and RDT-compliant properties. In other words, this property defines a minimal visible set of Z-paths that have to be doubled for the RDT property to be satisfied.Then, a family of communication-induced checkpointing protocols that ensure on-the-fly RDT properties is considered. Assuming processes take local checkpoints independently (called basic checkpoints), protocols of this family direct them to take on-the-fly additional local checkpoints (called forced checkpoints) in order that the resulting checkpoint and communication pattern satisfies the RDT property. The second contribution of this paper is a new communication-induced checkpointing protocol . This protocol, based on a condition derived from the previous characterization, tracks a minimal set of Z-paths and breaks those not perceived as being doubled. Finally, a set of communication-induced checkpointing protocols are derived from . Each of these derivations considers a particular weakening of the general condition used by . It is interesting to note that some of these derivations produce communication-induced checkpointing protocols that have already been proposed in the literature.     

Working with ARMs: Complexity Results on Atomic Representations of Herbrand Models

An atomic representation of a Herbrand model (ARM) is a finite set of (not necessarily ground) atoms over a given Herbrand universe. Each ARM represents a possibly infinite Herbrand interpretation. This concept has emerged independently in different branches of computer science as a natural and useful generalization of the concept of finite Herbrand interpretation. It was shown that several recursively decidable problems on finite Herbrand models (or interpretations) remain decidable on ARMs.The following problems are essential when working with ARMs: Deciding the equivalence of two ARMs, deciding subsumption between ARMs, and evaluating clauses over ARMs. These problems were shown to be decidable, but their computational complexity has remained obscure so far. The previously published decision algorithms require exponential space. In this paper, we prove that all mentioned problems are coNP-complete.     

3D Articulated Models and Multiview Tracking with Physical Forces

We present a method for automatically estimating the motion of an articulated object filmed by two or more fixed cameras. We focus our work on the case where the quality of the images is poor, and where only an approximation of a geometric model of the tracked object is available. Our technique uses physical forces applied to each rigid part of a kinematic 3D model of the object we are tracking. These forces guide the minimization of the differences between the pose of the 3D model and the pose of the real object in the video images. We use a fast recursive algorithm to solve the dynamical equations of motion of any 3D articulated model. We explain the key parts of our algorithms: how relevant information is extracted from the images, how the forces are created, and how the dynamical equations of motion are solved. A study of what kind of information should be extracted in the images and of when our algorithms fail is also presented. Finally we present some results about the tracking of a person. We also show the application of our method to the tracking of a hand in sequences of images, showing that the kind of information to extract from the images depends on their quality and of the configuration of the cameras.     

A Generic Integrated Line Detection Algorithm and Its Object–Process Specification

A generic integrated line detection algorithm (GILDA) is presented and demonstrated. GILDA is based on the generic graphics recognition approach, which abstracts the graphics recognition as a stepwise recovery of the multiple components of the graphic objects and is specified by the object–process methodology. We define 12 classes of lines which appear in engineering drawings and use them to construct a class inheritance hierarchy. The hierarchy highly abstracts the line features that are relevant to the line detection process. Based on the “Hypothesis and Test” paradigm, lines are detected by a stepwise extension to both ends of a selected first key component. In each extension cycle, one new component which best meets the current line's shape and style constraints is appended to the line. Different line classes are detected by controlling the line attribute values. As we show in the experiments, the algorithm demonstrates high performance on clear synthetic drawings as well as on noisy, complex, real-world drawings.     

Formative Processes with Applications to the Decision Problem in Set Theory: I. Powerset and Singleton Operators

This paper introduces formative processes, composed by transitive partitions. Given a family of sets, a formative process ending in the Venn partition Σ of is shown to exist. Sufficient criteria are also singled out for a transitive partition to model (via a function from set variables to unions of sets in the partition) all set-literals modeled by Σ. On the basis of such criteria a procedure is designed that mimics a given formative process by another where sets have finite rank bounded by C(|Σ|), with C a specific computable function. As a by-product, one of the core results on decidability in computable set theory is rediscovered, namely the one that regards the satisfiability of unquantified set-theoretic formulae involving Boolean operators, the singleton-former, and the powerset operator. The method described (which is able to exhibit a set-solution when the answer is affirmative) can be extended to solve the satisfiability problem for broader fragments of set theory.     

Efficient Computation of the Euclidean Distance Transform

We present a simple algorithm for the Euclidean distance transform of a binary image that runs more efficiently than other algorithms in the literature. We show that our algorithm runs in optimal time for many architectures and has optimal cost for the RAM and EREW PRAM.     

Cooperative Stereo–Motion: Matching and Reconstruction

One of the most interesting goals of computer vision is the 3D structure recovery of scenes. Traditionally, two cues are used: structure from motion and structure from stereo, two subfields with complementary sets of assumptions and techniques. This paper introduces a new general framework of cooperation between stereo and motion. This framework combines the advantages of both cues: (i) easy correspondence from motion and (ii) accurate 3D reconstruction from stereo. First, we show how the stereo matching can be recovered from motion correspondences using only geometric constraints. Second, we propose a method of 3D reconstruction of both binocular and monocular features using all stereo pairs in the case of a calibrated stereo rig. Third, we perform an analysis of the performance of the proposed framework as well as a comparison with an affine method. Experiments involving real and synthetic stereo pairs indicate that rich and reliable information can be derived from the proposed framework. They also indicate that robust 3D reconstruction can be obtained even with short image sequences.     

Attentional Scene Segmentation: Integrating Depth and Motion

We present an approach to attention in active computer vision. The notion of attention plays an important role in biological vision. In recent years, and especially with the emerging interest in active vision, computer vision researchers have been increasingly concerned with attentional mechanisms as well. The basic principles behind these efforts are greatly influenced by psychophysical research. That is the case also in the work presented here, which adapts to the model of Treisman (1985, Comput. Vision Graphics Image Process. Image Understanding31, 156–177), with an early parallel stage with preattentive cues followed by a later serial stage where the cues are integrated. The contributions in our approach are (i) the incorporation of depth information from stereopsis, (ii) the simple implementation of low level modules such as disparity and flow by local phase, and (iii) the cue integration along pursuit and saccade mode that allows us a proper target selection based on nearness and motion. We demonstrate the technique by experiments in which a moving observer selectively masks out different moving objects in real scenes.     

Fuzzy Distance Transform: Theory, Algorithms, and Applications

This paper describes the theory and algorithms of distance transform for fuzzy subsets, called fuzzy distance transform (FDT). The notion of fuzzy distance is formulated by first defining the length of a path on a fuzzy subset and then finding the infimum of the lengths of all paths between two points. The length of a path π in a fuzzy subset of the n-dimensional continuous space ⁿ is defined as the integral of fuzzy membership values along π. Generally, there are infinitely many paths between any two points in a fuzzy subset and it is shown that the shortest one may not exist. The fuzzy distance between two points is defined as the infimum of the lengths of all paths between them. It is demonstrated that, unlike in hard convex sets, the shortest path (when it exists) between two points in a fuzzy convex subset is not necessarily a straight line segment. For any positive number θ≤1, the θ-support of a fuzzy subset is the set of all points in ⁿ with membership values greater than or equal to θ. It is shown that, for any fuzzy subset, for any nonzero θ≤1, fuzzy distance is a metric for the interior of its θ-support. It is also shown that, for any smooth fuzzy subset, fuzzy distance is a metric for the interior of its 0-support (referred to as support). FDT is defined as a process on a fuzzy subset that assigns to a point its fuzzy distance from the complement of the support. The theoretical framework of FDT in continuous space is extended to digital cubic spaces and it is shown that for any fuzzy digital object, fuzzy distance is a metric for the support of the object. A dynamic programming-based algorithm is presented for computing FDT of a fuzzy digital object. It is shown that the algorithm terminates in a finite number of steps and when it does so, it correctly computes FDT. Several potential applications of fuzzy distance transform in medical imaging are presented. Among these are the quantification of blood vessels and trabecular bone thickness in the regime of limited special resolution where these objects become fuzzy.     

Specularities on Surfaces with Tangential Hairs or Grooves

Specularities on surfaces with tangential hairs or grooves are readily observable in nature. Examples of such phenomena are the arched or looped highlights observed on horses and human heads and the linear or curved specularities observed on parts of industrial machinery that have tangential grooves. We investigate the geometry of curvilinear specularities on surfaces of different curvature with tangential hairs or grooves of different orientations under controlled lighting and viewing conditions. First the nature of these specularities is investigated qualitatively. Then specularities on parametric surfaces and hair or groove orientations are calculated for some specific cases. Explicit calculations of specularities on some special surfaces, cylinders, cones, and spheres, are verified by photographs of the reflections. Aspects of the work are applicable to computer graphics and can be utilized for the image interpretation of surface specularities.     

Language-based Performance Prediction for Distributed and Mobile Systems

We present a framework for performance prediction of distributed and mobile systems. We rely on process calculi and their structural operational semantics. The dynamic behaviour is described through transition systems whose transitions are labelled by encodings of their proofs that we then map into stochastic processes. We enhance related works by allowing general continuous distributions resorting to a notion of enabling between transitions. We also discuss how the number of resources available affects the overall model. Finally, we introduce a notion of bisimulation that takes stochastic information into account and prove it to be a congruence. When only exponential distributions are of interest our equivalence induces a lumpable partition on the underlying Markov process.