Abstract This work is concerned with camera pose estimation from correspondences of 3D 2D lines, i. e. with the Perspective-n-Line (PnL) problem. We focus on large line sets, which can be efficiently solved by methods using linear formulation of PnL. We propose a novel method “DLT-Combined-Lines” based on the Direct Linear Transformation (DLT) algorithm, which benefits from a new combination of two existing DLT methods for pose estimation. The method represents 2D structure by lines, and 3D structure by both points and lines. The redundant 3D information reduces the minimum required line correspondences to 5. A cornerstone of the method is a combined projection matrix estimated by the DLT algorithm. It contains multiple estimates of camera rotation and translation, which can be recovered after enforcing constraints of the matrix. Multiplicity of the estimates is exploited to improve the accuracy of the proposed method. For large line sets (10 and more), the method is comparable to the state-of-the-art in accuracy of orientation estimation. It achieves state-of-the-art accuracy in estimation of camera position and it yields the smallest reprojection error under strong image noise. The method achieves top-3 results on real world data. The proposed method is also highly computationally effective, estimating the pose of 1000 lines in 12 ms on a desktop computer.
The RPnL algorithm was later modified by @cite_3 into the Accurate Subset based PnL () algorithm, which acts more accurately on small line sets. However, it is very sensitive to outliers, limiting its performance on real-world data. This algorithm is compared to other state-of-the-art methods in . A drawback of both RPnL and ASPnL is that their computational time increases strongly for higher number of lines -- from 8 ,ms , ,10 lines to 630 -- 880 ,ms , ,1000 lines.
@cite_3
2473967151
We propose a non-iterative solution for the Perspective-n-Line (PnL) problem, which can efficiently and accurately estimate the camera pose for both small number and large number of line correspondences. By selecting a rotation axis in the camera framework, the reference lines are divided into triplets to form a sixteenth order cost function, and then the optimum is retrieved from the roots of the derivative of the cost function by evaluating the orthogonal errors and the reprojected errors of the local minima. The final pose estimation is normalized by a 3D alignment approach. The advantages of the proposed method are as follows: (1) it stably retrieves the optimum of the solution with very little computational complexity and high accuracy; (2) small line sets can be robustly handled to achieve highly accurate results and; (3) large line sets can be efficiently handled because it is O(n). In this paper we deal with the camera pose estimation problem from a set of 2D 3D line correspondences, which is also known as PnL (Perspective-n-Line) problem. We carry out our study by comparing PnL with the well-studied PnP (Perspective-n-Point) problem, and our contributions are three-fold: (1) We provide a complete 3D configuration analysis for P3L, which includes the well-known P3P problem as well as several existing analyses as special cases. (2) By exploring the similarity between PnL and PnP, we propose a new subset-based PnL approach as well as a series of linear-formulation-based PnL approaches inspired by their PnP counterparts. (3) The proposed linear-formulation-based methods can be easily extended to deal with the line and point features simultaneously. We propose a linear-time line segment detector that gives accurate results, a controlled number of false detections, and requires no parameter tuning. This algorithm is tested and compared to state-of-the-art algorithms on a wide set of natural images. We address the model-to-image registration problem with line features in the following two ways. (a) We present a robust solution to simultaneously recover the camera pose and the three-dimensional-to-two-dimensional line correspondences. With weak pose priors, our approach progressively verifies the pose guesses with a Kalman filter by using a subset of recursively found match hypotheses. Experiments show our method is robust to occlusions and clutter. (b) We propose a new line feature based pose estimation algorithm, which iteratively optimizes the objective function in the object space. Experiments show that the algorithm has strong robustness to noise and outliers and that it can attain very accurate results efficiently. Random Forests (RFs) are frequently used in many computer vision and machine learning applications. Their popularity is mainly driven by their high computational efficiency during both training and evaluation while achieving state-of-the-art results. However, in most applications RFs are used off-line. This limits their usability for many practical problems, for instance, when training data arrives sequentially or the underlying distribution is continuously changing. In this paper, we propose a novel on-line random forest algorithm. We combine ideas from on-line bagging, extremely randomized forests and propose an on-line decision tree growing procedure. Additionally, we add a temporal weighting scheme for adaptively discarding some trees based on their out-of-bag-error in given time intervals and consequently growing of new trees. The experiments on common machine learning data sets show that our algorithm converges to the performance of the off-line RF. Additionally, we conduct experiments for visual tracking, where we demonstrate real-time state-of-the-art performance on well-known scenarios and show good performance in case of occlusions and appearance changes where we outperform trackers based on on-line boosting. Finally, we demonstrate the usability of on-line RFs on the task of interactive real-time segmentation. Support vector ordinal regression (SVOR) is a popular method to tackle ordinal regression problems. However, until now there were no effective algorithms proposed to address incremental SVOR learning due to the complicated formulations of SVOR. Recently, an interesting accurate on-line algorithm was proposed for training @math -support vector classification ( @math -SVC), which can handle a quadratic formulation with a pair of equality constraints. In this paper, we first present a modified SVOR formulation based on a sum-of-margins strategy. The formulation has multiple constraints, and each constraint includes a mixture of an equality and an inequality. Then, we extend the accurate on-line @math -SVC algorithm to the modified formulation, and propose an effective incremental SVOR algorithm. The algorithm can handle a quadratic formulation with multiple constraints, where each constraint is constituted of an equality and an inequality. More importantly, it tackles the conflicts between the equality and inequality constraints. We also provide the finite convergence analysis for the algorithm. Numerical experiments on the several benchmark and real-world data sets show that the incremental algorithm can converge to the optimal solution in a finite number of steps, and is faster than the existing batch and incremental SVOR algorithms. Meanwhile, the modified formulation has better accuracy than the existing incremental SVOR algorithm, and is as accurate as the sum-of-margins based formulation of Shashua and Levin. Traditional structure from motion is hard in indoor environments with only a few detectable point features. These environments, however, have other useful characteristics: they often contain severable visible lines, and their layout typically conforms to a Manhattan world geometry. We introduce a new algorithm to cluster visible lines in a Manhattan world, seen from two different viewpoints, into coplanar bundles. This algorithm is based on the notion of “characteristic line”, which is an invariant of a set of parallel coplanar lines. Finding coplanar sets of lines becomes a problem of clustering characteristic lines, which can be accomplished using a modified mean shift procedure. The algorithm is computationally light and produces good results in real world situations. We introduce an algorithm for word-level text spotting that is able to accurately and reliably determine the bounding regions of individual words of text "in the wild". Our system is formed by the cascade of two convolutional neural networks. The first network is fully convolutional and is in charge of detecting areas containing text. This results in a very reliable but possibly inaccurate segmentation of the input image. The second network (inspired by the popular YOLO architecture) analyzes each segment produced in the first stage, and predicts oriented rectangular regions containing individual words. No post-processing (e.g. text line grouping) is necessary. With execution time of 450 ms for a 1000-by-560 image on a Titan X GPU, our system achieves the highest score to date among published algorithms on the ICDAR 2015 Incidental Scene Text dataset benchmark. Large lighting variation challenges all visual odometry methods, even with RGB-D cameras. Here we propose a line segment-based RGB-D indoor odometry algorithm robust to lighting variation. We know line segments are abundant indoors and less sensitive to lighting change than point features. However, depth data are often noisy, corrupted or even missing for line segments which are often found on object boundaries where significant depth discontinuities occur. Our algorithm samples depth data along line segments, and uses a random sample consensus approach to identify correct depth and estimate 3D line segments. We analyze 3D line segment uncertainties and estimate camera motion by minimizing the Mahalanobis distance. In experiments we compare our method with two state-of-the-art methods including a keypoint-based approach and a dense visual odometry algorithm, under both constant and varying lighting. Our method demonstrates superior robustness to lighting change by outperforming the competing methods on 6 out of 8 long indoor sequences under varying lighting. Meanwhile our method also achieves improved accuracy even under constant lighting when tested using public data. Correspondences between 3D lines and their 2D images captured by a camera are often used to determine position and orientation of the camera in space. In this work, we propose a novel algebraic algorithm to estimate the camera pose. We parameterize 3D lines using Plucker coordinates that allow linear projection of the lines into the image. A line projection matrix is estimated using Linear Least Squares and the camera pose is then extracted from the matrix. An algebraic approach to handle mismatched line correspondences is also included. The proposed algorithm is an order of magnitude faster yet comparably accurate and robust to the state-of-the-art, it does not require initialization, and it yields only one solution. The described method requires at least 9 lines and is particularly suitable for scenarios with 25 and more lines, as also shown in the results. Abstract In this paper, we study the 1-dimensional on-line bin packing problem. A list of pieces, each of size between zero and unity are to be packed, in order of their arrival, into a minimum number of unit-capacity bins. We present a new linear-time algorithm, the Modified Harmonic Algorithm and show, by a novel use of weighting functions, that it has an asymptotic worst-case performance ratio less than 3 2 + 1 9 + 1 222 = 1.(615) ∗ . We show that for a large class of linear-time on-line algorithms including the Modified Harmonic Algorithm, the performance ratio is at least 3 2 + 1 9 = 1.61 ∗ . Then we show how to successively construct classes of improved linear-time on-line algorithms. For any algorithm in any of these classes, the performance ratio is at least 3 2 + 1 12 = 1.583 ∗ . We present an improved algorithm called Modified Harmonic-2 with performance ratio 1.612 … and present an approach to construct linear-time on-line algorithms with better performance ratios. The analysis of Modified Harmonic-2 is omitted because it is very similar to that of Modified Harmonic, but it is substantially more complicated. Our results extend to orthogonal packings in two dimensions. Estimation of camera pose from an image of n points or lines with known correspondence is a thoroughly studied problem in computer vision. Most solutions are iterative and depend on nonlinear optimization of some geometric constraint, either on the world coordinates or on the projections to the image plane. For real-time applications, we are interested in linear or closed-form solutions free of initialization. We present a general framework which allows for a novel set of linear solutions to the pose estimation problem for both n points and n lines. We then analyze the sensitivity of our solutions to image noise and show that the sensitivity analysis can be used as a conservative predictor of error for our algorithms. We present a number of simulations which compare our results to two other recent linear algorithms, as well as to iterative approaches. We conclude with tests on real imagery in an augmented reality setup. We present a novel on-line approach for extrinsic robot-camera calibration, a process often referred to as hand-eye calibration, that uses object pose estimates from a real-time model-based tracking approach. While off-line calibration has seen much progress recently due to the incorporation of bundle adjustment techniques, on-line calibration still remains a largely open problem. Since we update the calibration in each frame, the improvements can be incorporated immediately in the pose estimation itself to facilitate object tracking. Our method does not require the camera to observe the robot or to have markers at certain fixed locations on the robot. To comply with a limited computational budget, it maintains a fixed size configuration set of samples. This set is updated each frame in order to maximize an observability criterion. We show that a set of size 20 is sufficient in real-world scenarios with static and actuated cameras. With this set size, only 100 microseconds are required to update the calibration in each frame, and we typically achieve accurate robot-camera calibration in 10 to 20 seconds. Together, these characteristics enable the incorporation of calibration in normal task execution. This paper presents a robust and efficient method for license plate detection with the purpose of accurately localizing vehicle license plates from complex scenes in real time. A simple yet effective image downscaling method is first proposed to substantially accelerate license plate localization without sacrificing detection performance compared with that achieved using the original image. Furthermore, a novel line density filter approach is proposed to extract candidate regions, thereby significantly reducing the area to be analyzed for license plate localization. Moreover, a cascaded license plate classifier based on linear support vector machines using color saliency features is introduced to identify the true license plate from among the candidate regions. For performance evaluation, a data set consisting of 3977 images captured from diverse scenes under different conditions is also presented. Extensive experiments on the widely used Caltech license plate data set and our newly introduced data set demonstrate that the proposed approach substantially outperforms state-of-the-art methods in terms of both detection accuracy and run-time efficiency, increasing the detection ratio from 91.09 to 96.62 while decreasing the run time from 672 to 42 ms for processing an image with a resolution of @math . The executable code and our collected data set are publicly available. Motivated by the desire to cope with data imprecision Loffler (2009) [31], we study methods for taking advantage of preliminary information about point sets in order to speed up the computation of certain structures associated with them. In particular, we study the following problem: given a set L of n lines in the plane, we wish to preprocess L such that later, upon receiving a set P of n points, each of which lies on a distinct line of L, we can construct the convex hull of P efficiently. We show that in quadratic time and space it is possible to construct a data structure on L that enables us to compute the convex hull of any such point set P in O([email protected](n)log^@?n) expected time. If we further assume that the points are ''oblivious'' with respect to the data structure, the running time improves to O([email protected](n)). The same result holds when L is a set of line segments (in general position). We present several extensions, including a trade-off between space and query time and an output-sensitive algorithm. We also study the ''dual problem'' where we show how to efficiently compute the (= We describe algorithms for the problem of minimum distortion embeddings of finite metric spaces into the real line (or a finite subset of the line). The time complexities of our algorithms are parametrized by the values of the minimum distortion, a#x03B4;, and the spread, a#x0394;, of the point set we are embedding. We consider the problem of finding the minimum distortion bijection between two finite subsets of the Euclidean line. This problem was known to have an exact polynomial time solution when a#x03B4; is below a specific small constant, and hard to approximate within a factor of a#x03B4;1 -- a#x03B5;, when a#x03B4; is polynomially large. Let D be the largest adjacent pair distance, a value potentially much smaller than a#x0394;. Then we provide a a#x03B4;O(a#x03B4;2 log2 D) n O(1) time exact algorithm for this problem, which in particular yields a quasipolynomial running time for constant a#x03B4;, and polynomial D. For the more general problem of embedding any finite metric space (X, dX) into a finite subset of the line, Y, we provide a a#x03B4;O(a#x03B4;2) (mn)O(1) time O(1)-approximation algorithm (where |X|=n and |Y|=m), which runs in polynomial time provided a#x03B4; is a constant and a#x03B4; is polynomial. This in turn allows us to get a a#x03B4;O(a#x03B4;2) (n)O(1) time O(1)-approximation algorithm for embedding (X, dX) into the continuous real line. We present a physics-based illumination estimation approach explicitly designed to handle natural images under ambient light. Existing physics-based color constancy methods are theoretically perfect but do not handle real-world images well because the majority of these methods assume a single illuminant. Therefore, specular pixels selected using existing methods produce estimated dichromatic lines that are thick or curvilinear in the presence of ambient light, thus generating significant errors. Based on the Phong reflection model, we show that a group of specular pixels on a uniformly colored object, although they are subject to intensity thresholding, produce a unique dichromatic line length depending on the geometry of each image path. Assuming that the longest dichromatic line is the most desirable when estimating the chromaticity of an illuminant, ambient-robust specular pixels are also found on the same path on which the longest dichromatic line segment is generated. Therefore, we propose a method to find the optimal image path in which the specular pixels produce the longest dichromatic line. Even though the number of collected specular pixels is reduced using the proposed method, they are proven to be more accurate when determining the illuminant chromaticity even in the existing methods. Experiments with an established benchmark data set and a self-produced image set find that the proposed method is better able to locate the illuminant chromaticity compared with the state-of-the-art color constancy methods. In this paper, we propose a visual place recognition algorithm which uses only straight line features in challenging outdoor environments. Compared to point features used in most existing place recognition methods, line features are easily found in man-made environments and more robust to environmental changes such as illumination, viewing direction, or occlusion. Candidate matches are found using a vocabulary tree and their geometric consistency is verified by a motion estimation algorithm using line segments. The proposed algorithm operates in real-time, and it is tested with a challenging real-world dataset with more than 10,000 database images acquired in urban driving scenarios. The Hough transform is a popular technique used in the field of image processing and computer vision. With a Hough transform technique, not only the normal angle and distance of a line but also the line-segment’s length and midpoint (centroid) can be extracted by analysing the voting distribution around a peak in the Hough space. In this paper, a method based on minimum-entropy analysis is proposed to extract the set of parameters of a line segment. In each column around a peak in Hough space, the voting values specify probabilistic distributions. The corresponding entropies and statistical means are computed. The line-segment’s normal angle and length are simultaneously computed by fitting a quadratic polynomial curve to the voting entropies. The line-segment’s midpoint and normal distance are computed by fitting and interpolating a linear curve to the voting means. The proposed method is tested on simulated images for detection accuracy by providing comparative results. Experimental results on real-world images verify the method as well. The proposed method for line-segment detection is both accurate and robust in the presence of quantization error, background noise, or pixel disturbances. A method for the determination of camera location from two-dimensional (2-D) to three-dimensional (3-D) straight line or point correspondences is presented. With this method, the computations of the rotation matrix and the translation vector of the camera are separable. First, the rotation matrix is found by a linear algorithm using eight or more line correspondences, or by a nonlinear algorithm using three or more line correspondences, where the line correspondences are either given or derived from point correspondences. Then, the translation vector is obtained by solving a set of linear equations based on three or more line correspondences, or two or more point correspondences. Eight 2-D to 3-D line correspondences or six 2-D to 3-D point correspondences are needed for the linear approach; three 2-D to 3-D line or point correspondences for the nonlinear approach. Good results can be obtained in the presence of noise if more than the minimum required number of correspondences are used. >