We describe a robust method for the recovery of the depth map (or height map) from a gradient map (or normal map) of a scene, such as would be obtained by photometric stereo or interferometry. Our method allows for uncertain or missing samples, which are often present in experimentally measured gradient maps, and also for sharp discontinuities in the scene’s depth, e.g. along object silhouette edges. By using a multi-scale approach, our integration algorithm achieves linear time and memory costs. A key feature of our method is the allowance for a given weight map that flags unreliable or missing gradient samples. We also describe several integration methods from the literature that are commonly used for this task. Based on theoretical analysis and tests with various synthetic and measured gradient maps, we argue that our algorithm is as accurate as the best existing methods, handling incomplete data and discontinuities, and is more efficient in time and memory usage, especially for large gradient maps.

In this work we introduced SnooperTrack, an algorithm for the automatic detection and tracking of text objects - such as store names, traffic signs, license plates, and advertisements - in videos of out door scenes. The purpose is to improve the performances of text detection process in still images by taking advantage of the temporal coherence in videos. We first propose an efficient tracking algorithm using particle filtering framework with original region descriptors. The second contribution is our strategy to merge tracked regions and new detections. We also propose an improved version of our previously published text detection algorithm in still images. Tests indicate that SnooperTrack is fast, robust, enable false positive suppression, and achieved great performances in complex videos of outdoor scenes.

In this paper, we describe a data structure and an algorithm to accelerate the table lookup step in example-based multiimage photometric stereo. In that step, one must find a pixel of a reference object, of known shape and color, whose appearance under m different illumination fields is similar to that of a given scene pixel. This search reduces to finding the closest match to a given m-vector in a table with a thousand or more m-vectors. Our method is faster than previously known solutions for this problem but, unlike some of them, is exact, i.e., always yields the best matching entry in the table, and does not assume point-like sources. Our solution exploits the fact that the table is in fact a fairly flat 2-D manifold in m-dimensional space so that the search can be efficiently solved with a uniform 2-D grid structure.

We describe a robust method to recover the depth coordinate from a normal or slope map of a scene, obtained e.g. through photometric stereo or interferometry. The key feature of our method is the fast solution of the Poisson-like integration equations by a multi-scale iterative technique. The method accepts a weight map that can be used to exclude regions where the slope information is missing or untrusted, and to allow the integration of height maps with linear discontinuities (such as along object silhouettes) which are not recorded in the slope maps. Except for pathological cases, the memory and time costs of our method are typically proportional to the number of pixels N. Tests show that our method is as accurate as the best weighted slope integrators, but substantially more efficient in time and space.

We describe a robust and accurate algorithm, nicknamed AffTrack, to track selected features of a rigid 3D object in a video recording, given a canonical image of each feature and its position on the object. AffTrack uses a synergistic combination of a multiscale feature finder and a flexible camera calibrator. This synergy between the two modules allows, AffTrack to recover features after occlusions of arbitrary duration. Compared to other solutions to this problem, AffTrack can handle videos with variable zoom, and variable lens distortion, does not require a complete geometric model of the object, and does not require the selection of key frames. Tests indicate that AffTrack is more robust and accurate than the popular object trackers include in H. Kato's ARToolKit and in the OpenCV library.

Abstract We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation information given by affine arithmetic. As an application, we show how to compute approximate distance fields for parametric curves. ACM CSS: I.3.3 Computer Graphics—Curve, surface, solid, and object representations, G.1.2 Numerical Analysis—Approximation of surfaces and contours, G.1.0 Numerical Analysis—Interval arithmetic

We describe an efficient procedure for reassembling unknown two-dimensional objects that have been broken or torn into a large number of irregular fragments, a problem that often arises in archaeology, art restoration, forensics, and other disciplines. The procedure compares the curvature-encoded fragment outlines, at progressively increasing scales of resolution, using an incremental dynamic programming sequence-matching algorithm. The total cost gets reduced by a factor proportional to the mean number of samples per segment, which makes the method viable for problems of practical size (thousands of fragments). The performance of our method is illustrated with an artificial but realistic example.

We develop exact algorithms for geometric operations on general circles and circular arcs on the sphere, using integer homogeneous coordinates. The algorithms include testing a point against a circle, computing the intersection of two circles, and ordering three arcs out of the same point. These operations allow robust manipulation of maps on the sphere, providing a reliable framework for GIS, robotics, and other geometric applications.

It has been conjectured that every configuration C of convex objects in 3-space with disjoint interiors can be taken apart by translation with two hands: that is, some proper subset of C can be translated to infinity without disturbing its complement. We show that the conjecture holds for five or fewer objects and give a counterexample with six objects. We extend the counterexample to a configuration that cannot be taken apart with two hands using arbitrary isometries (rigid motions).

The ZZ-buffer is a simple acceleration scheme for ray tracing that can be applied to a wide variety of scenes, including those with small features, textured and transparent surfaces, shadows and penumbrae, and depth-of-field effects. In this paper, we describe how the ZZ-buffer algorithm can be adapted to the rendering of scenes defined by constructive solid geometry operations.

This thesis introduces Epsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The algorithms in this framework produce exact solutions for perturbed versions of their input and return a bound on the size of these implicit perturbations. The thesis begins with a formal description of the Epsilon Geometry framework. It introduces the notions of an epsilon predicate, a geometric predicate that can be satisfied by a perturbed version of its arguments; and a critical distance, the size of the perturbation required to make an epsilon predicate true. It also introduces epsilon and delta boxes, the implementations of these mathematical concepts as computer programs. The thesis describes some general rules for turning mathematical lemmas about epsilon predicates and critical distances into implementations of epsilon and delta boxes. Next, it presents a basic set of two-dimensional geometric predicates that are used for all of the algorithms in the sequel. The second half of the thesis examines how Epsilon Geometry can be applied to various geometric objects and algorithms in the plane. It defines the notions of an $\varepsilon$-convex polygon, a polygon that can be made convex by perturbing each of its vertices by $\varepsilon$ or less; and a ($-\varepsilon)$-convex polygon, a polygon that remains convex even if its vertices are all displaced in arbitrary directions by a distance of $\varepsilon$ or less. The thesis develops robust algorithms for testing point inclusion in both kinds of polygons, and for testing a polygon's degree of convexity. Finally, the thesis investigates the existence of approximate hulls for sets of points. It proves that for every point set there exists a ($-\varepsilon$)-convex polygon H such that every point of the set is at most 4$\varepsilon$ away from H, and it describes robust algorithms for computing such hulls.

In this note we give two methods for generating images of (approximations to) fractals and fractal-like sets: iterated Kronecker products and iterated matrix-valued homomorphisms. In contrast to the well-known methods for vector displays, the methods generate rectangular arrays of intensity levels which are particularly suited to display on raster devices with bitmap capabilities. The methods also give efficient parallel algorithms for computing n × n images, which require O(log n) operations per pixel.

Oriented projective geometry is a model for geometric computation that combines the elegance of classical projective geometry with the ability to talk about oriented lines and planes, signed angles, line segments, convex figures, and many other concepts that cannot be defined within the classical version. Classical projective geometry is the implicit framework of many geometric computations, since it underlies the well-known homogeneous coordinate representation. It is argued here that oriented projective geometry — and its analytic model, based on signed homogeneous coordinates — provide a better foundation for computational geometry than their classical counterparts.

Given n linear inequalities in three variables, we show how to construct a corresponding spherical subdivision using great circle arcs in time O( n log n ) and space O( n ). This subdivision in turn allows us to compute the point in space satisfying all inequalities and maximizing any desired linear objective function in time O (log n ).

Point location, often known in graphics as “hit detection,” is one of the fundamental problems of computational geometry. In a point location query we want to identify which of a given collection of geometric objects contains a particular point. Let $\mathcal{S}$ denote a subdivision of the Euclidean plane into monotone regions by a straight-line graph of m edges. In this paper we exhibit a substantial refinement of the technique of Lee and Preparata [SIAM J. Comput., 6 (1977), pp. 594–606] for locating a point in $\mathcal{S}$ based on separating chains. The new data structure, called a layered dag, can be built in $O(m)$ time, uses $O(m)$ storage, and makes possible point location in $O(\log m)$ time. Unlike previous structures that attain these optimal bounds, the layered dag can be implemented in a simple and practical way, and is extensible to subdivisions with edges more general than straight-line segments.

The following problem is discussed: given n points in the plane (the sites) and an arbitrary query point q , find the site that is closest to q . This problem can be solved by constructing the Voronoi diagram of the griven sites and then locating the query point inone of its regions. Two algorithms are given, one that constructs the Voronoi diagram in O ( n log n ) time, and another that inserts a new sit on O(n) time. Both are based on the use of the Voronoi dual, or Delaunay triangulation, and are simple enough to be of practical value. the simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. The topology is represented by a new data structure for generalized diagrams, that is, embeddings of graphs in two-dimensional manifolds. This structure represents simultaneously an embedding, its dual, and its mirror image. Furthermore, just two operators are sufficients for building and modifying arbitrary diagrams.

We discuss the following problem: given n points in the plane (the “sites”), and an arbitrary query point q, find the site that is closest to q. This problem can be solved by constructing the Voronoi diagram of the given sites, and then locating the query point in one of its regions. We give two algorithms, one that constructs the Voronoi diagram in O(n lg n) time, and another that inserts a new site in O(n) time. Both are based on the use of the Voronoi dual, the Delaunay triangulation, and are simple enough to be of practical value. The simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem, and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. The topology is represented by a new data structure for generalized diagrams, that is embeddings of graphs in two-dimensional manifolds. This structure represents simultaneously an embedding, its dual, and its mirror-image. Furthermore, just two operators are sufficient for building and modifying arbitrary diagrams.

In this paper we propose that bitmaps, or raster images, should be given full citizen status in the world of computer science. We introduce a calculus of bitmap operations and MUMBLE, a programming language appropriate for describing bitmap computations. We illustrate the use of MUMBLE by several interesting graphical applications. We also discuss the structure of BOP, an efficient implementation of the bitmap calculus that is the underpinning of our system.

ManipulationThis paper proposes that bitmaps, or raster images, should be given full citizenship in the world of computer science.We introduce a calculus of bitmap operations and MUMBLE, a programming language appropriate for describing bitmap computations.We illustrate the use of MUMBLE by several interesting graphical applications.We also discuss the structure of BOP, an efficient implementation of the bitmap calculus that is the underpinning of our system.