A case against Kruppa's equations for camera self-calibration

We consider the self-calibration problem for perspective cameras and especially the classical Kruppa equation approach. It is known that for several common types of camera motion, self-calibration is degenerate, which manifests itself through the existence of ambiguous solutions. The author previously (1997, 1999) studied these critical motion sequences and showed their importance for practical applications. Here, we reveal a type of camera motion that is not critical for the generic self-calibration problem, but for which the Kruppa equation approach fails. This is the case if the optical centers of all cameras lie on a sphere and if the optical axes pass through the sphere's center, a very natural situation for 3D object modeling from images. Results of simulated experiments demonstrate the instability of numerical self-calibration algorithms in near-degenerate configurations.     

Dynamic Polygon Visibility Ordering for Head-Slaved Viewing in Virtual Environments

This paper presents an approach to visibility called the Viewpoint Movement Space (VpMS) algorithm which supports the concept of dynamic polygon visibility orderings for head-slaved viewing in virtual environments (VE). The central idea of the approach is that the visibility, in terms of back-to-front polygon visibility ordering, does not change dramatically as the viewpoint moves. Moreover, it is possible to construct a partition of the space into cells, where for each cell the ordering is invariant. As the viewpoint moves across a cell boundary typically only a small and predictable change is made to the visibility ordering. The cost to perform this operation represents a notable reduction when compared with the cost of resolving the visibility information from the BSP tree where the classification of the viewpoint with every node plane has to be performed. The paper demonstrates how the subdivision into such cells can represent the basic source for an acceleration of the rendering process. We also discuss how the same supportive data structure can be exploited to solve other tasks in the graphics pipeline.     

A Unified Approach to Conic Visibility

{In this paper we present linear time algorithms for computing the shortest path tree from a point and the weak visibility polygon of an arc inside a triangulated curved polygon. We also present a linear time algorithm for computing the planar subdivision (in the parametric space) of the set of rays emanating from a fixed arc, such that each face of the subdivision corresponds to rays hitting the same arc of the polygon. Although these results, which involve nontrivial generalizations of known results for rectilinear polygons, may have some interest in its own right, the main result of this paper is a linear time algorithm for computing the conic (circular, elliptic, parabolic, and hyperbolic) visibility polygon of a point inside a simple polygon. The main advantage of our technique over previous results on circular visibility is that it provides a simple, unified approach to conic visibility. Finally, we present a linear time algorithm for computing the planar subdivision, in the parametric space, of two-parametric families of conic rays emanating from a fixed point, such that each face of the subdivision corresponds to conic rays hitting the same edge of the polygon. All these algorithms are asymptotically optimal.} Received August 21, 1997; revised December 27, 1998.     

Epipolar geometry of opti-acoustic stereo imaging

Optical and acoustic cameras are suitable imaging systems to inspect underwater structures, both in regular maintenance and security operations. Despite high resolution, optical systems have limited visibility range when deployed in turbid waters. In contrast, the new generation of high-frequency (MHz) acoustic cameras can provide images with enhanced target details in highly turbid waters, though their range is reduced by one to two orders of magnitude compared to traditional low-/midfrequency (10s-100s KHz) sonar systems. It is conceivable that an effective inspection strategy is the deployment of both optical and acoustic cameras on a submersible platform, to enable target imaging in a range of turbidity conditions. Under this scenario and where visibility allows, registration of the images from both cameras arranged in binocular stereo configuration provides valuable scene information that cannot be readily recovered from each sensor alone. We explore and derive the constraint equations for the epipolar geometry and stereo triangulation in utilizing these two sensing modalities with different projection models. Theoretical results supported by computer simulations show that an opti-acoustic stereo imaging system outperforms a traditional binocular vision with optical cameras, particularly for increasing target distance and (or) turbidity.     

A Parallel Algorithm for the Visibility of a Simple Polygon Using Scan Operations

This paper describes a parallel algorithm for computing the visible portion of a simple planar polygon with N vertices from a given point on or inside the polygon. The algorithm accomplishes this in O(k log N) time using O(N/log N) processors, where k is the link-diameter of the polygon in consideration. The link-diameter of a polygon is the maximum number of straight line segments needed to connect any two points within the polygon, where all line segments lie completely within the polygon. The algorithm can also be used to compute the visible portion of the plane given a point outside of the polygon. Except in this case, the parameter k in the asymptotic bounds would be the link diameter of a different polygon. The algorithm is optimal for sets of polygons that have a constant link diameter. It is a rather simple algorithm, and has a very small run time constant, making it fast and practical to implement. The interprocessor communication needed involves only local neighbor communication and scan operations (i.e., parallel prefix operations). Thus the algorithm can be implemented not only on an EREW PRAM, but also on a variety of other more practical machine architectures, such as hypercubes, trees, butterflies, and shuffle exchange networks. The algorithm was implemented on the Connection Machine as well as the MasPar MP- 1, and various performance tests were conducted.     

Radial Multi-focal Tensors

The 1D radial camera maps all points on a plane, containing the principal axis, onto the radial line which is the intersection of that plane and the image plane. It is a sufficiently general model to express both central and non-central cameras, since the only assumption it makes is of known center of distortion. In this paper, we study the multi-focal tensors arising out of 1D radial cameras. There exist no two-view constraints (like the fundamental matrix) for 1D radial cameras. However, the 3-view and 4-view cases are interesting. For the 4-view case we have the radial quadrifocal tensor, which has 15 d.o.f and 2 internal constraints. For the 3-view case, we have the radial trifocal tensor, which has 7 d.o.f and no internal constraints. Under the assumption of a purely rotating central camera, this can be used to do a non-parametric estimation of the radial distortion of a 1D camera. Even in the case of a non-rotating camera it can be used to do parametric estimation, assuming a planar scene. Finally we examine the mixed trifocal tensor, which models the case of two 1D radial cameras and one standard pin-hole camera. Of the above radial multifocal tensors, only the radial trifocal tensor is useful practically, since it doesn’t require any knowledge of the scene and is extremely robust. We demonstrate results based on real-images for this.     

Methods for Volumetric Reconstruction of Visual Scenes

In this paper, we present methods for 3D volumetric reconstruction of visual scenes photographed by multiple calibrated cameras placed at arbitrary viewpoints. Our goal is to generate a 3D model that can be rendered to synthesize new photo-realistic views of the scene. We improve upon existing voxel coloring/space carving approaches by introducing new ways to compute visibility and photo-consistency, as well as model infinitely large scenes. In particular, we describe a visibility approach that uses all possible color information from the photographs during reconstruction, photo-consistency measures that are more robust and/or require less manual intervention, and a volumetric warping method for application of these reconstruction methods to large-scale scenes.     

Online polygon search by a seven-state boundary 1-searcher

Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region. In this paper, we consider a special case of this problem, called boundary search, where the searcher is allowed to move only along the boundary of the polygon. We concentrate on a single searcher with one flashlight (called a 1-searcher), but it is known that a single boundary 1-searcher has the same searching power as a single boundary searcher with 360/spl deg/ vision. Our main result is that the movement of the searcher can be controlled by a finite-state machine having only seven states. This automaton has no built-in information about the input polygon and, for any given polygon P, if P can be searched by a boundary searcher at all, then this automaton will successfully search P, no matter where on the boundary of P it is initially placed. All information about P is acquired by the automaton online, as it searches P. We also show that if P can be searched by a boundary searcher, then our automaton searches it by circling its boundary less than three times.     

3D model reconstruction with common hand-held cameras

A 3D model reconstruction workflow with hand-held cameras is developed. The exterior and interior orientation models combined with the state-of-the-art structure from motion and multi-view stereo techniques are applied to extract dense point cloud and reconstruct 3D model from digital images. An overview of the presented 3D model reconstruction methods is given. The whole procedure including tie point extraction, relative orientation, bundle block adjustment, dense point production and 3D model reconstruction is all reviewed in brief. Among them, we focus on bundle block adjustment procedure; the mathematical and technical details of bundle block adjustment are introduced and discussed. Finally, four scenes of images collected by hand-held cameras are tested in this paper. The preliminary results have shown that sub-pixel (<1 pixel) accuracy can be achieved with the proposed exterior–interior orientation models and satisfactory 3D models can be reconstructed using images collected by hand-held cameras. This work can be applied in indoor navigation, crime scene reconstruction, heritage reservation and other applications in geosciences.     

Mapping Simple Polygons: How Robots Benefit from Looking Back

We consider the problem of mapping an initially unknown polygon of size n with a simple robot that moves inside the polygon along straight lines between the vertices. The robot sees distant vertices in counter-clockwise order and is able to recognize the vertex among them which it came from in its last move, i.e. the robot can look back. Other than that the robot has no means of distinguishing distant vertices. We assume that an upper bound on n is known to the robot beforehand and show that it can always uniquely reconstruct the visibility graph of the polygon. Additionally, we show that multiple identical and deterministic robots can always solve the weak rendezvous problem in which the robots need to position themselves such that all of them are mutually visible to each other. Our results are tight in the sense that the strong rendezvous problem, where robots need to gather at a vertex, cannot be solved in general, and, without knowing a bound beforehand, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known.     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。     

Lazy Visibility Evaluation for Exact Soft Shadows

This paper presents a novel approach to compute high quality and noise‐free soft shadows using exact visibility computations. This work relies on a theoretical framework allowing to group lines according to the geometry they intersect. From this study, we derive a new algorithm encoding lazily the visibility from a polygon. Contrary to previous works on from‐polygon visibility, our approach is very robust and straightforward to implement. We apply this algorithm to solve exactly and efficiently the visibility of an area light source from any point in a scene. As a consequence, results are not sensitive to noise, contrary to soft shadows methods based on area light source sampling. We demonstrate the reliability of our approach on different scenes and configurations.     

OPTIMAL MESH ALGORITHMS FOR PROXIMITY AND VISIBILITY PROBLEMS IN SIMPLE POLYGONS*

We present optimal parallel algorithms that run in time on mesh-connected computer for a number of fundamental problems concerning proximity and visibility in a simple polygon. These include computing shortest paths, shortest path trees, shortest path partitions, all-farthest neighbors, the visibility polygon of a point, the weak visibility polygon of an edge, and the ray shooting problem.     

Pattern flattening for orthotropic materials

In many applications it is necessary to define good-fitting 2D flattened patterns for user-defined regions of a larger 3D surface. This paper describes the major stages involved in pattern flattening and illustrates the process with examples. In generating 2D patterns, some distortion is inevitably involved if the target 3D surface is not developable. For situations where distortion is required, it can be quantified in terms of the energy that must be imparted to the 2D flattening in localised areas so that it takes-up the original 3D region of the surface. An orthotropic strain model is adopted to convert the strain values to energy values. Starting with a bi-parametric definition of a large 3D surface, an arbitrary defined region is specified by the user in terms of a contiguous series of cubic curves lying on the bi-parametric plane. To extract the 3D region, a polygon list is generated to represent the surface. The triangulation process is based on a ‘marching front’ algorithm. A process is described which then flattens this polygon list and performs an energy minimisation analysis every time the process attempts to flatten an over-constrained triangle. Further consideration is made of seam insertion in the 3D surface definition and of adaptively modifying the triangulation process so that more triangles are used in areas of high-energy concentration. Examples are also presented to illustrate the sensitivity of the strain profiles to the fabric grain direction when the pattern is applied to the 3D surface.     

Shape from shading for the digitization of curved documents

Document digitization is faster and more affordable using digital cameras than scanners. On the other hand, if we aim at extending the basic digital camera functionalities for such a purpose, post-processings will be of first importance, at least to improve the text legibility. In this paper, we address the specific problem of the virtual flattening of curved documents, as for example the pages of an opened book lying on its spine. In order to compute the document shape, we use the shape from shading technique and discuss why, in some cases, it is more suitable than other 3D single-view reconstruction techniques. We extend the seminal work by Wada et al. (Proceedings of the IAPR Workshop on machine vision and applications, Tokyo, Japan, pp. 591–594, 1992) and consecutive papers, reformulating the problem in terms of perspective shape from shading. Finally, we design a complete post-processing algorithm and test it on real images. Even if the documents are much curved, it is shown that the restored images are almost identical to scanned images of the flattened documents.     

Real-time Anticipation of Occlusions for Automated Camera Control in Toric Space

Efficient visibility computation is a prominent requirement when designing automated camera control techniques for dynamic 3D environments; computer games, interactive storytelling or 3D media applications all need to track 3D entities while ensuring their visibility and delivering a smooth cinematic experience. Addressing this problem requires to sample a large set of potential camera positions and estimate visibility for each of them, which in practice is intractable despite the efficiency of ray-casting techniques on recent platforms. In this work, we introduce a novel GPU-rendering technique to efficiently compute occlusions of tracked targets in Toric Space coordinates – a parametric space designed for cinematic camera control. We then rely on this occlusion evaluation to derive an anticipation map predicting occlusions for a continuous set of cameras over a user-defined time window. We finally design a camera motion strategy exploiting this anticipation map to minimize the occlusions of tracked entities over time. The key features of our approach are demonstrated through comparison with traditionally used ray-casting on benchmark scenes, and through an integration in multiple game-like 3D scenes with heavy, sparse and dense occluders.     

Recovery of 3D animal motions using cameras and mirrors

We present a system that tracks an articulated body performing 3D movement with occlusions using a combination of cameras and mirrors. By integrating cameras and mirrors we get a simultaneous coverage of almost every point on the target and avoid occlusions. The suggested setup is much simpler and easier to handle compared to the equivalent, camera-based setup. Our tracking algorithm is model-based, and errors in the model are treated using the bundle adjustment procedure. In order to deal with the problem of feature visibility, each feature is set to be valid or invalid based on the model and on its expected appearance; this ensures that the system always tracks a set of distinguishable features. The proposed algorithm was able to track targets in 3D using the Gauss–Newton method to minimize geometric errors. We tested our setup by tracking the chameleon’s eyes. Tracking the eyes of a chameleon can be considered as the estimation of the 3D pose of an articulated body, where the head of the chameleon is considered as a rigid body, and each of the two eyes has additional two degrees of freedom. The algorithm proposed can be easily expanded to cope with more complex objects.     

Introducing the use of depth data for fall detection

Current emergency systems for elderly contain at least one sensor (button or accelerometer), which has to be worn or pressed in case of emergency. If elderly fall and loose their consciousness, they are not able to press the button anymore. Therefore, autonomous systems to detect falls without wearing any devices are needed. This paper presents three different non-invasive technologies: the use of audio, 2D sensors (cameras) and introduces a new technology for fall detection: the Kinect as 3D depth sensor. Our fall detection algorithms using the Kinect are evaluated on 72 video sequences, containing 40 falls and 32 activities of daily living. The evaluation results are compared with State-of-the-Art approaches using 2D sensors or microphones.     

Shortest path between two simple polygons

Consider a collection of mutually disjoint simple polygons in the plane containing a total of n edges. Two of them are specified as a source polygon S and a target polygon T. We present an efficient algorithm for finding a shortest path between S and T avoiding the other polygons. We show that it runs in O(n²) time, using a linear-time algorithm for computing the visibility polygon of a point. This problem is related to a wire routing design of a certain type of LSI for which terminals are of polygonal shape and larger than a wire segment.     

Guarding the walls of an art gallery

P so that each point of P is seen by at least one guard. We introduce and explore the edge-covering problem; the guards are required to observe the edges of P; metaphorically the paintings on the walls of the art gallery, and not necessarily every interior point. We compare minimum edge and interior covers for a given polygon and analyze the bounds and complexity for the edge-covering problem. We also introduce and analyze a restricted edge covering problem, where full visibility of each edge from at least one guard is required. For this problem we present an algorithm that computes a set of regions where a minimum set of guards must be located. The algorithm can also deal with the external visibility of a set of polygons.