G
tfP v
GEODETSKI VESTNIK | letn. / Vol. 60 | št. / No. 1 |
ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK
THE RELIABILITY OF RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT
9
| 60/1|
Tilen Urbančič, Anja Vrečko, Klemen Kregar
UDK: 528.2
Klasifikacija prispevka po COBISS.SI: 1.01 Prispelo: 14. 10. 2015 Sprejeto: 3. 3. 2016
DOI: 10.15292/geodetski-vestnik.2016.01.69-97
SCIENTIFIC ARTICLE Received: 14. 10. 2015 Accepted: 3. 3. 2016
_ IZVLEČEK
Postopek RANSAC (RANdom SAmple Cosensus) uporabljamo za identifikacijo točk iz oblaka točk, ki pripadajo nekemu geometrijsko opisljivemu telesu. Včasih je dovolj, da takšne točke poiščemo, pogosteje pa nas zanimajo parametri geometrijskega objekta in natančnost njihove določitve. V literaturi kakovosti rezultatov postopka RANSAC navadno ne preverjajo. Ocena natančnosti parametrov geometrijskih teles temelji na stohastičnem modelu izravnave, v katerem pa so uporabljeni le inlierji (točke, ki jih je RANSAC vrnil kot rezultat). Ali so bile s postopkom določene prave točke, pa v tej oceni ni upoštevano. Rezultat metode RANSAC temelji na naključno izbranem vzorcu minimalnega števila točk, ki je potrebno za določitev geometrijskega telesa. Ob več ponovitvah postopek ne bo vrnil enakega rezultata. V članku predstavljamo analizo zanesljivosti postopka RANSAC. Isti oblak točk smo z metodo RANSAC procesirali stokrat in vsakokrat izravnali geometrijsko obliko. Standardni odklon rezultatov stotih ponovitev primerjamo s kvadratnim korenom povprečja varianc posameznih rezultatov. Analizo smo izvedli na primeru krogle, stožca in ravnine. Predlagamo, naj se pri uporabi metode RANSAC postopek vedno vsaj nekajkrat ponovi. Tako zagotovimo parametre geometrijskih oblik bolj zanesljivo, natančnost parametrov pa ocenimo bolj realistično.
KLJUČNE BESEDE
ABSTRACT _
The RANSAC (RANdom SAmple Consensus) is often used to identify points belonging to the objects whose shape can be modeled with geometric primitives. These points, called inliers, are of great interest in some applications but often the goal is also to estimate the parameters of geometric shape and their accuracies. The quality of RANSAC results is rarely analysed. The accuracies of estimated parameters are usually calculated based only on the residuals of inliers, selected by RANSAC, from a mathematical model. However, the analysis does not indicate if the right points were selected. The result of RANSAC depends on the random selection of the minimum number of points that uniquely describe a mathematical model; in the case of multiple repetitions of the method, the results are not necessarily the same. This paper presents an analysis of RANSAC reliability based on repeating the selection of points from the point cloud by RANSAC one hundred times. A standard deviation of one hundredparameter values is used to estimate the parameters' accuracies. An analysis is made for three different examples of geometric objects: a sphere, a cone, and a plane. Finally, we suggest repeating the algorithm several times and checking the consistency of the results to obtain a more reliable estimation of parameters and their accuracies.
KEY WORDS
RANSAC, zanesljivost, oblak točk, geometrijska oblika RANSAC, reliability, point cloud, geometric object
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 69 |
| 60/1 |
GEODETSKI VESTNIK
^ 1 INTRODUCTION
^ Laser scanning and image matching applied to aerial imagery are increasingly used for fast data acquisi-g tion. The result is a set of points with known coordinates also called a 'point cloud'. In dealing with such ^ data two difficulties often appear:
g — it is not explicitly known the part of which object from the real world the specific point represents, and
g — the coordinates of the measured points are determined with lower precision as obtained by traditional geodetic surveying techniques. As well, the accuracy of the specific point coordinates is in general not known.
Both difficulties can also be solved by a RANSAC (RANdom SAmple Consensus) method, and will be described later on. RANSAC was developed by Fischer and Bolles (1981) as a method for the robust estimation of parameters in a mathematical model. They used it in photogrammetry to estimate the parameters of the exterior orientation of a camera based on a known image and the object coordinates of control points. RANSAC was also used to improve the robustness of other procedures, e.g. the estimation of transformation parameters between coordinate systems (Brown and Lowe, 2002; Barnea and Filin, 2007) or the registration of satellite images (Kim and Im, 2003). Robustness and speed of RANSAC were also improved with different adaptations for use in the field of computer vision (e.g. Torr and Zis-§ serman, 2000; Matas and Chum, 2004; Nister, 2003; Tordoff and Murray, 2005).
RANSAC was also used for the segmentation of point clouds obtained by laser scanning technology. Here are only a few examples: Tittmann et al. (2011) used this method to identify points representing trees, by modeling the shape of the crowns with paraboloids. Tarsha-Kurdi et al. (2007) used RANSAC to identify points belonging to a roof. By comparing the results with results of a Hough transformation it was observed that RANSAC performance was faster and of higher quality. Van der Sande et al. (2010) checked the relative accuracy of airborne scans based on the points representing a roof identified by RANSAC. Li et al. (2011) used the method for planar segmentation of buildings. Theiler and Schindler (2012) used RANSAC for segmentation of a point cloud into planes. These were then used for the automatic registration of point clouds acquired by terrestrial laser scanning. Thus, the use of artificial targets could be avoided. Similarly, Huang et al. (2012) used the method to detect planes and a cylinder for the automatic registration of point clouds without an artificial target.
In the field of classic geodetic networks reliability is designated as resistance of mathematical model against gross errors. However, when dealing with research methods, reliability is defined as quality of results in terms of repeatability or consistency (Trochim, 2015). Spichal (1990) also describes reliability as admissible degree of random errors in research results.
Even though RANSAC is used in many applications not many researchers studied the quality of its performance. In this article we present an analysis of the reliability of original RANSAC (Fischler and Bolles, 1981). In various examples we show how different results can be obtained when the method is used repeatedly on the same data set. Experiments are based on three basic geometric objects: sphere, cone and plane. In the procedures of laser scanning former two bodies are useful for the determination of the characteristic points. Characteristic points are needed for registration of point clouds or calibration of laser scanners. While plane have no characteristic point it can come very handy for the segmentation of point clouds.
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 70 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 
| 60/1 |
Second section describes the tools which are used in the study: the RANSAC algorithm, mathematical	^ models of geometric objects, least square estimation of parameters, and their accuracies. The accuracy of i= '
the parameters is estimated in two different ways: i) from the residuals of points from the models and ii)	§
as the standard deviation of parameters' values from multiple repetitions. This is followed by the analysis	£ of the reliability of the RANSAC with which the coordinates of characteristic points from the scans of ¡¡L
spheres and cones can be estimated. RANSAC is then used to detect points which represent a plane in	5
a simulated point cloud. In the last section the influence of data characteristics and input parameters on	5 the reliability of RANSAC are discussed. Some suggestions for practical use and quality estimation of S RANSAC are given in the conclusion.
2 METHODS
2.1 Description of the RANSAC algorithm
RANSAC is used to find points of a point cloud representing objects (or their parts) that can be modeled as geometrical objects. The basic idea behind RANSAC is that the optimal parameters are those describing the mathematical model which covers the greatest amount of points. Firstly, the minimal subset of points needed to uniquely determine a geometrical object is selected randomly from the point cloud. Secondly, the parameters of the model are determined for this subset. The residuals of other points in the s point cloud from model are computed. The points in a point cloud are classified as inliers, if respective ^ residuals are smaller than a given threshold and as outliers, if respective residual are greater respectively. The procedure is repeated until the desired number of points is classified as inliers or until a desired confidence level is reached. According to the number of inliers in each repetition the best model is chosen. The algorithm is described in mathematical notation below (Fischler and Bolles, 1981).
The input data for the algorithm are:
m — the number of points needed to uniquely determine the parameters of a chosen mathematical model,
t — the threshold, points within it are considered inliers, w — the expected percentage of inliers in a point cloud,
p — the confidence level (probability that only inliers will be randomly chosen in at least one of the
repetitions), S — the data, a point cloud. The algorithm:
1.	Determine a number of iterations N (see section. 2.2).
2.	For k = 1, ..., N
—	randomly pick m points from S ^ Sk
—	determine the parameters of the mathematical model Mk from Sk
—	S* = {s|s 6 S \ Sk A^k (s)< t}
3.	S' = {Sk I SJ = max Si}
klll kh k=1,...,nh k|1
Where Sk(s) are residuals of points in S from the mathematical model M. The result of the algorithm is a set S*. Set S' is the one of S' which contains the maximal number of points.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 71 |
| 60/1 |
GEODETSKI VESTNIK
2.2 Determine a number of iterations
Parameter N represents the number of iterations needed to ensure (with a certain level of confidence) that at least one of the subsets Sk contains only inliers. Nis calculated from the minimum number m of points that uniquely define the model and the expected percentage of inliers in the point cloud w. The probability that all points in Sk are inliers is then wm while 1 - wm is the probability that at least one of the points in subset Sk is an outlier. The probability that in N iterations at least one subset includes an outlier, is (1 — wm) N. Thus, the probability that the algorithm never selects only inliers is (Fischler and Bolles, 1981):
1 — p = (1 — wm)N	(1)
By increasing the number of iterations N the risk level 1 — p limits toward zero. Usually the confidence level is chosen and a percentage of inliers m is estimated, so the parameter N can be calculated from the equation (1) as:
N = _ log ° — P)
log 0 — uT )
More about the influence of the RANSAC input parameters can be found in Urbancic et al. (2014).
== 2.3 Functionalmodelsofgeometricalobjects
A plane, a sphere, and a cone are geometrical objects used in this paper. The procedures chosen to determine the parameters for these three objects types based on a minimal number of needed points are described in this section. Furthermore, it is also defined how the residuals of other points in a point cloud from the model are computed.
2.3.1 A plane
Equation of a plane can be written as:
ax + by + cz — d = 0	(3)
where, a, b, c and d are the parameters of a plane; x, y and z are the coordinates of a point on a plane.
Three points on a plane are needed m = 3 to uniquely determine the parameters of the plane, although equation (3) contains four unknown parameters. The parameters of a plane can be determined in two steps: in first parameters, a, b, c and then parameter d. Parameter d can be eliminated from equation (3) by substracting all the coordinates its average. By doing so, the plane through three chosen points is translated to pass through the origin of a coordinate system. This translation does not influence the orientation of the plane in the coordinate system, thus parameters, a, b and c do not change.
The coordinates of the three points reduced to the center of gravity are written as rows in a matrix M3x3. The parameters, a, b and c are parameters of an eigenvector, corresponding to a minimal eigenvalue of the matrix M. Parameter d can be determined by fixing parameters, a, b and c, the coordinates of one of the points (not reduced to the center of gravity) into equation (3).
The perpendicular distances of all points to the plane are computed as lengths of orthogonal projections of position vectors of points onto the normal vector of the plane:
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 72 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK | 60/1 |
S = [x. ~ y ~ yc z, ~ z)[a b c]T	(4) ^
where, x ,yc and z c are coordinates of the center of gravity. All points for which |S.| < t are accepted as inliers in the RANSAC algorithm (see section 2.1).
2.3.2	A sphere
The equation of a sphere can be written as:
X - x) + (y. -yc)2 + (z. - z)2 - r 2 = 0	(5) 1
Coordinates of four non-coplanar points from the sphere surface are needed to uniquely determine 4 parameters: the coordinates of a sphere center (x,y, zj and radius r. Different procedures can be used to determine the parameters (Franaszek et al., 2009). Sphere parameters can be determined by introducing new variables a, ¡, y and s in equation (5)
x2 +y2+z2 - ax - ¡y - yz + s= 0	(6)
Variables a, ¡, y and s are determined by solving the four equation of a set of four given points with coordinates (x., y., z.). Parameters of the sphere are obtained by equations:
x =a, y =1 , z =y , r2=(a)2+3+{l\-s	(7) t
c 2 Jc 2 c 2 L 2) L 2 J L 2 J
Distances d. of every point in a point cloud to the center can be computed with the known coordinates of the sphere's center. The orthogonal distance between a point and the sphere surface is then S. = d. - r. All points for which |S| < t are accepted as inliers in the RANSAC algorithm (see section 2.1).
2.3.3	A cone
The equation of an upright cone can be written as:
x- x0)2 + (ys-y0)2 - (k • z5 + h)2 = 0	(8)
where xs,ys and zs are coordinates of points laying on the cone; x0 and y0 are coordinates of the intersection of the cone axis with the plane z = 0; k is a coefficient of a line R = f(z) = k • zs + h; h is a radius of the intersection of the cone and the plane z = 0.
To generalize the equation (8) for the situations of an upright cone, the orientation of the cone axis can be described by rotations around the x and y axes of the coordinate system for angles C0x and a , respectively. A cone is symmetrical with respect to the vertical axis. The rotation between the point cloud coordinate system (x, y, z) and the cone coordinate system (xs, ys, zs) shown in Figure 1 can be described as:
(9)
where the rotation matrix is R = R R .
my mx
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 73 |
x s		x
ys	=R	y
_ Zs _		z
| 60/1 |
GEODETSKI VESTNIK
Figure 1: Point cloud coordinate system (x,y,z) and cone coordinate system (xs,yS,zs). When equation (9) is put into equation (8) the following relation can be written: (rnx + r12y + r z-x0)2 + (r2]x + r22y + r23 z-y0)2 - (k(r x + r32y + r33 z) + u)2 = 0
(10)
where r. are functions of angles CO and CO , as elements of the matrix R. The parameters to be estimated
j	&	x	y	r
are: the coordinates of the cone apex, the orientation of the cone axis, and the angle between the base and cone surfaces. A cone can be uniquely determined by six points lying on the lateral surface of the cone. If these are given, a system of six equations of the form (10) with six unknowns can be solved to obtain the parameters of the cone.
Once the parameters are estimated, the orthogonal residuals of points in a point cloud from the lateral surface of the cone are calculated as:
8. = sin(0.) d.
(11)
where is an angle between the surface of the cone and the line connecting the apex of the cone and a point. All points for which |5.| < t are accepted as inliers in the RANSAC algorithm (see section 2.1).
2.4 Least square approximation of geometric objects
The result of the RANSAC algorithm is a set of points S* (see section 2.1). However, a user's ultimate goal is usually to determine the parameters of the selected geometric object model based on the set of points. To obtain the parameters of the geometric model the adjustment of the Gauss-Helmert model is used. Mathematical models for plane, sphere, and cone are given with equations. (3), (5), and (10), respectively. The models represent the relation between observations (coordinates of points in) and unknowns (parameters of geometric objects).
The model is linearized by deriving the mathematical model equation with respect to observations and unknowns. The functional model of adjustment is written in matrix form as:
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 74 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 
| 60/1 |
Av+BA = f	(12)
where: A - the coefficient matrix for the observations; v - observations residuals; B - the coefficient matrix	g
for the parameters; A - unknown parameters (corrections of the approximate values of the parameters);	8 and f - the condition equation constant terms.
The unknown parameter vector A is obtained by solving equation (12) according to the least square	== principle:
A = (Br(AAr)-1B)-1(Br(AAr)-1f)	(13)	^
The stochastic properties of the estimated parameters are described by variance-covariance matrix of estimated unknowns:
Saa = ^(BW)-1B)-1	(14)
where c20 is the reference variance. Details of the procedure can be found in Kuang (1996) as well as in Grigillo and Stopar (2003).
2.5 Analysis of the RANSAC reliability
The accuracies of parameters obtained through equation (14) are based on residuals of points S* from s a mathematical model of geometrical object. However, an influence of random sampling in the second ^ step of the RANSAC method on estimated values of parameters is not taken into account.
The analysis of reliability (repeatability) is based on one hundred independent repetitions of RANSAC algorithm runs and a parameters estimation for three different point clouds. In all repetitions we used the the input data, as well as the same values of input parameters. This is how we obtain hundred sets of object parameters with corresponding accuracy estimation calculated by equation (14).
Standard deviations ct^, ct^ and cr^ are used as a measure of accuracy of estimated parameters x(g),y(g) and z(g) for least square estimations based on set of points S* obtained from SAA(g) (14) for g = 1, ..., 100 repetitions.
As a measure of accuracy of estimated parameters for single repetition, <7^, (Tg, and CTgi (marked red and italic in Table 1) are defined as the root of average of g variances , CT and ct^ .
The accuracy of a hundred repetitions is calculated as the standard deviation of the p = 1, ..., 100 estimations of parameters and designated as o\, CT7 and ct.. It is marked blue and underline in Table 1.
Both measures for a numerical example are shown in Table 1 to clarify the difference between them.
In the analysis of the RANSAC reliability of a generated point cloud it was known which points belong to the plane, therefore we are able to perform the check if it was correctly identified as an inlier or an outlier. Type 1 errors is the number of points which are determined to be inliers, but do not belong to the plane. On the other hand, type 2 errors is the number of points which are not determined as an inlier, but do belong to the plane.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 75 |
| 60/1 |	GEODETSKI VESTNIK
Table 1: A numerical example of accuracy estimation based on single and on a hundred repetitions.
	Repetition		Parameters			Accuracies	
a:		* [m]	y [m]	z [m]	CT [mm]	CTy [mm]	CTz [mm]
i	1	-1.177220	4.039860	-0.272920	0.039	0.016	0.040
	2	-1.177620	4.040020	-0.272880	0.038	0.018	0.039
	3	-1.177240	4.040080	-0.272950	0.039	0.022	0.039
1							
Ke	100	-1.177200	4.040040	-0.272980	0.040	0.027	0.040
	mean	X	y	z	CT	CT	CT
		-1.177445	4.040202	-0.272933	0.040	0.030	0.041
	st. dev.	CT_ [mm]	CT„ [mm]	CT [mm]			
		0.172	0.333	0.063			
In the analysis of the RANSAC reliability of a generated point cloud it was known which points belong to the plane, therefore we are able to perform the check if it was correctly identified as an inlier or an outlier. Type 1 errors ex is the number of points which are determined to be inliers, but do not belong to the plane. On the other hand, type 2 errors e2 is the number of points which are not determined as N an inlier, but do belong to the plane.
3 RESULTS
In the procedures of self-calibration (Lichti, 2010) we need to measure identical points from different scanner stations. While TLS technology does not allow the measuring of a specific point, we have to signalize the (control) points with objects with known geometry. It is possible to determine characteristic point coordinates of such an object accurately enough.
When scanning objects from multiple scanner positions it is necessary to merge single scans into a common point cloud. This procedure is called 'registration' and is carried out using a similarity transformation of coordinates obtained by single scans into a common reference coordinate system. To determine transformation parameters between coordinate systems of single scans we need to know the coordinates of at least three identical points in both coordinate systems. These points are called 'tie points'. Usage of geometric objects for tie points determination was shown in the study by Barbarella and Fiani (2013).
We propose usage of a sphere or cone for control or tie points signalization. These two geometric models allow quality characteristic point extraction in all three dimensions.
3.1 Plane
A plane can not be used for the determination of characteristic point due to its shape, however it can well be used for segmentation. Segmentation is procedure for dividing point cloud into smaller groups of points, where points belonging to specific group are similar in some way. Such similarity can be belonging to common plane.
Our first test was oriented to extracting the points belonging to the plane from a synthetic point cloud. Points laying on the plane are simulated with a parameters a = 2, b = 4, c = —3, d = 3, and
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 76 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK | 60/1 |
a normally distributed noise with a standard deviation of 5 cm was added. Points that do not lie on the plane and are evenly distributed around the space are added. Ten repetitions of segmentation with RANSAC are performed with changing the percentage of inliers w. In each repetition the true values of the parameters t, w, and the confidence level of 99% are used. The results of the estimated plane parameters and their standard deviations (estimated accuracies) are given in Table 2 and in Figure 2.
Table 2: Results of RANSAC method on simulated planes.
t [cm]	w	p	N	i	e1	e2
5	10 (2.4%) 99%	317391 32/410 = 7.8%	30	8
5	20 (4.8%) 99%	42647 34/420 = 8.1%	17	3
5	30 (7.0%) 99%	13559 44/430 = 12.2%	14	0
5	40 (9.1%) 99%	6128 49/440 = 11.1%	15	6
5	75 (15.8%) 99%
1168 80/475 = 16.8%	13	8
5 100 (20.0%) 99%	574 110/500 = 22.0%	13	3
5	150 (27.3%)	99%	225	139/550 = 33.5%	11	22
5	200 (33.3%)	99%	123	191/600 = 31.8%	11	20
5	300 (42.9%)	99%	57	236/700 = 33.7%	8	72
5	400 (50.0%)	99%	35	282/800 = 35.3%	11	129
Figure 2: View on results of the RANSAC method on an artificial point cloud from two different perspectives. The first set of data from Table 2 was used. Red - points on generated plane, Blue - points that do not belong to the generated plane, black "+" - points, recognized by RANSAC as points on the plane.
To estimate the RANSAC reliability the calculation of the plane parameters with the input parameters t = 5 cm, w = 50%, and p = 99% was repeated one hundred times. Like for the sphere and for the cone we observe the differences between the parameters accuracy of single repetition and a hundred repetitions. The results for the plane are given in Table 3 and Figure 3.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 77 |
| 60/1 |	GEODETSKI VESTNIK
Table 3: Accuracy comparison for single repetition and a hundred repetitions of RANSAC - plane.
	generated	single repetition	a hundred repetitions
	[m]	parameter and accuracy [m]	parameter and accuracy [m]
a	2.000	a = 1.931 a = 0.018	a = 2.009 a = 0.079
b	4.000	b = 4.192 ah = 0.021	b = 3.998 ah = 0.154
c	-3.000	c = -2.971 a = 0.034	c = -2.985 a = 0.110
d	3.000	d = 3.050 ad = 0.015	d = 3.004 ad = 0.111
Figure 3: Uncertainty of the plane determination with the RANSAC method. Black - points that lie on the searched plane, red - points on the plane with added normally distributed noise, gray, transparent planes - planes that we got at a hundred repetitions of the RANSAC method on red points.
3.2 A sphere
The simpler geometric models for characteristic point determination is a sphere, since it is completely defined by only four parameters. Still, when extracting center coordinates of a scanned sphere we face some limitations:
(i)	From a single scan station we cannot capture more than half of the sphere's surface.
(ii)	Only a part of the laser beam is reflected from the edges of sphere (viewed from scanner) and it causes data artefacts (Hebert and Krotkov, 1992).
(iii)	In the section of the sphere surface perpendicular to the laser scanner direction, the echo intensity may be too strong for the sensor, which causes gross error in the measured distance.
(iv)	The scanner's field view is normally rectangular, which means that besides the sphere there are also some surrounding points captured.
RANSAC is used here to remove points that do not belong to the model of the sphere.
Our analysis was carried out on five point clouds of scanned spheres. Five spheres i.e. V1, V16, V17, V19, and V3 with a radius of 3.5 cm were scanned with the Riegl VZ-400 terrestrial laser scanner. The instrument provides single point accuracy of 5 mm and precision of 3 mm at the distance of 100 m.
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 52 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 
| 60/1 |
The laser beam diameter at the exit is 7 mm and divergence 0.35 mrad (Riegl, 2014). Spheres were scanned at a distance of 30 m with a 1x1 mm resolution. All five point clouds contain errors due to already mentioned reasons (ii), (iii), and (iv). For all point clouds, input parameters were set to t = 2 mm, w = 50%, andp = 99% (see section 2.1). To achieve the required confidence levelp, 72 random samples are needed. Table 4 displays the estimation accuracy of sphere parameters for single repetition and a hundred repetitions of RANSAC (see section 2.5).
Table 4: Accuracy comparison for single repetition and a hundred repetitions of RANSAC - spheres.
		sing	le repetition [mm]			a hundred repetitions [mm]				
Spheres:	V1	V16	V17	V19	V3	V1	V16	V17	V19	V3
<Jx	0.14	0.13	0.10	0.14	0.24	9.37	0.52	2.48	9.15	38.59
a y	0.05	0.05	0.04	0.05	0.07	2.33	0.16	0.95	4.01	6.96
az	0.05	0.04	0.04	0.05	0.05	1.76	0.11	1.02	1.58	2.53
ar	0.11	0.10	0.07	0.11	0.22	7.89	0.39	1.92	8.24	25.72
Each of the spheres V1, V16, V17, and V19 is represented in Figure 4 with: a point cloud (black), an adjusted sphere (blue), standard error ellipsoids for the sphere center — for single repetition (black) and a hundred repetitions (red). Error ellipsoids in Figure 4 relate to the accuracy from Table 4, and are plotted in a scale of 10000:1, according to the point cloud.
Figure 4: Point clouds, adjusted spheres, and both standard error ellipsoids for spheres a) VI, b) V16, c) V17, and d) V19. (Single repetition error ellipsoids are barely visible).
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 53 |
| 60/1 |	GEODETSKI VESTNIK
Sphere V3 is special case where estimated coordinates of centers and radius of sphere V3 are rather varying between single repetitions. Three typical cases of the results for sphere V3 are shown in Figure 5.
Figure 5: Point clouds (red) and adjusted sphere V3.
3.3 A cone
In the second experiment, cones were examined. The cone apex represents the cone's characteristic point. Cone apex coordinates were calculated according to the procedure in section 2.3.3.
Table 5: Accuracy comparison for single repetition and a hundred repetitions of RANSAC - cones.
single repetition [mm]					a hundred repetitions[mm]			
Cone steepness[°]	20	30	45	60	20	30	45	60
a	0.12	0.08	0.05	0.02	1.75	0.46	0.30	0.11
a	0.12	0.09	0.05	0.02	1.73	0.56	0.32	0.10
a	0.06	0.03	0.04	0.03	0.18	0.13	0.16	0.20
a)	b)
Figure 6: Point clouds (black), adjusted cone (blue), standard error ellipsoids for the cone apex - for single repetition (black) and a hundred repetitions (red) for cones with different angles: a) 20°, b) 30°, c) 45°, in d) 60°.
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 80 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK
|60/1 |
To test the proposed method of finding the cone model we use part of the data from scanned test field. ^ Scanning is executed with the terrestrial laser scanner Riegel VZ-400 at a distance of 6.4 m, and with i= approximately 2x2 mm resolution. The test field consists of four cone models with 5 cm radius of the ¡^ base and different angles between the base and the lateral surface: 20°, 30°, 45°, and 60°. The following £ parameters are used for the calculation: t = 2 mm, w = 35%, and p = 95%. Table 5 displays the average accuracy of the cone apex coordinates for single repetition and the dispersion of the cone apex coordinates 5 determined from a hundred repetitions.
The graphical results of the cone apex coordinates determination in the test field are shown in Figure 6. The points and the calculated cone model are shown after adjustment of mathematical model using only inliers of the RANSAC algorithm solution. Error ellipsoids in Figure 6 relate to the accuracy from Table 5, and are plotted in a scale of 50000:1, according to the point cloud.
4 DISCUSSION
Some general conclusions about RANSAC performance can be made, based on the experiment, as described in section. 3.2.1, where the true values of the expected percentage of inliers in a point cloud w and the threshold t were known apriori:
—	greater confidence levelp and greater percentage of inliers w imply longer computational time. Equation (2) describes the relation;
—	at a lower percentage of inliers, we noticed a higher proportion of type 1 errors and for higher percentage of inliers there may be higher probability of type 2 error.
Based on a hundred repetitions, the plane parameters are determined more accurately than based on single repetition. Similar to the sphere and cone, the parameters estimation from a hundred repetitions is much more dispersed than might be inferred from the accuracies of estimated parameters based on single repetition.
Our primary interest was the accuracy estimation of characteristic points coordinates. Accuracy estimations based on single repetition (RANSAC and least square adjustment) are rather optimistic. The estimation is based on residuals between points and the mathematical model, and as such directly related to the chosen value of parameter t. Smaller t implies that points fit better to the surface and accuracy of estimated coordinates is better. Accuracy estimation on the basis of adjustment does not say much about the reliability of RANSAC. It is not known whether right points were selected as inliers from a point cloud. With multiple repetitions of procedure on the same point cloud at least three times lower accuracy was obtained for the sphere, as well as for the cone.
In the case of sphere V3 RANSAC algorithm was not able to find points belonging to the actual sphere in every repetition (Figure 5). The possibility of making such mistakes can be reduced by preliminary data processing (e.g. intensity filtering), or by including known parameters into the procedure (e.g. sphere radius or cone slope)
Size and orientation of standard error ellipsoids may differ significantly for different geometrical objects. Error ellipsoid orientation for spheres depends on scanners position. The largest semi axis of an ellipsoid always faces towards the scanner station, since it is possible to scan only a part of the surface facing toward
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
81
| 60/1 |
GEODETSKI VESTNIK
^	the scanner. For the cones, however, the orientation of error ellipsoids depends on cone geometry as
i=	well as on relative scanner - cone position. For the pointiest cone (60°), the largest semi axis of ellipsoid
p	points is in the direction of the cone axis, while for other cones error ellipsoids are flattened in the plane
£	orthogonal to cone axes (Figure 7). Standard error ellipsoids are plotted in a scale of 50000:1 according f^ to the point cloud which is plotted in meters.
y [m]
Figure 7: Standard error ellipsoids of RANSAC for cone models. Scanner position is in point (0, 0, 0)
^ To conclude, the model parameters adjusted from a RANSAC processed point cloud may be inaccurate. Parameters accuracies estimated through adjustment are overestimated. The problem ofwrong parameters can be resolved quite simply by repeating the procedure a few times and check the consistency of the obtained results. For accuracy estimation we can say that: actual accuracy depends on the shape of geometric object and accuracy of measured points themselves; and actual accuracy of estimated parameters is lower than accuracy obtained through adjustment of RANSAC processed points.
Precisions and standard ellipsoids in the article are always related to RANSAC procedure solely. Point clouds in scanners own coordinate system was used. When applying RANSAC in practice, errors caused by registration and georeferencing would additionally affect achieved accuracies significantly.
RANSAC is a method with a lot of advantages, and is highly resistant to gross errors in the point cloud. The method can be used for quite large number of tasks and applications. However, the RANSAC method is based on randomness so we have to be aware of the fact that it is not possible to obtain identical results if RANSAC is repeated on the same input data. One of our goals regarding this article is to point out that a reasonable amount of caution is necessary when using RANSAC, especially in cases when results of high accuracy are needed.
Acknowledgements
We would like to thank the European Social Fund for founding the PhD study of first and last author and DFG Consulting for the terrestrial laser scanning. The work is partially founded by Slovenian Research Agency.
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 82 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 
| 60/1 |
References:
Barbarella, M., Flanl, M. (2013). Monitoring of Large Landslide by Terestrlal Laser Scanning Techniques: Field Data Collection and Processing. European Journal of Remote Sensing, 46, 126-151. DOI: http://dx.doi.org/10.5721/EuJRS20134608 Barnea, S., Filin, S. (2007). Registration of Terrestrial Laser Scans via Image-based Features. ISPRS Workshop on Laser Scanning 2007 and SilviLaser 2007,Volume XXXVI, Part 3/W52, Espoo, Finska, 32-37. Brown, M., Lowe, D. (2002). Invariant Features from Interest Point Groups. Proceedings of the British Machine Vision Conference, 656-665. DOI: http://dx.doi. org/10.5244/C.16.23 Fischler, A. M., Bolles, C. R. (1981). Random Sample Consensum: A Paradigm for Model fitting with Application to Image Analysis and Automated Cartography. Communication of the ACM, 24(6), 381-395. DOI: http://dx.doi. org/10.1145/358669.358692 Franaszek, M., Cheok, G. S., Saidi, K. S., Witzgall, C. (2009). Fitting Spheres to Range Data from 3-D Imaging Systems. IEEE Transaction on Instrumentation and Measurement, 58(10), 3544-3553. DOI: http://dx.doi.org/10.1109/ TIM.2009.2018011
Grigillo, D., Stopar, B. (2003). Metode odkrivanja grobih pogreškov v geodetskih opazovanjih = Methods of Gross Error Detection in Geodetic Observations. Geodetski vestnik, 47(4), 387-403. Hebert, M., Krotkov, E. (1992). 3D Measurements From Imaging Laser Radars: How Good are They? Image and vision computing, 10(3), 170-178. DOI: http:// dx.doi.org/10.1016/0262-8856(92)90068-E Huang, T., Zhang, D., Li, G., Jiang, M. (2012). Registration Method for Terrestrial Lidar Point Clouds Using Geometric Features. Optical Engineering, 51(2), 021114. DOI: http://dx.doi.org/10.1117/1.OE.51.2.021114 Kim,T., Im,Y. (2003). Automatic Satellite Image Registration by Combination ofStereo Matching and Random Sample Consensus. IEEETransactions on Geoscence and Remote Sensing, 41(5), 1111-1117. DOI: http://dx.doi.org/10.1109/TGRS.2003.811994 Kregar, K., Ambrožič, T., Kogoj, D., Vezočnik, R., Marjetič, A. (2015) Determining the inclination of tall chimneys using the TPS and TLS approach. Measurement, 75, 354-363. DOI: http://dx.doi.org/10.1016/j.measurement.2015.08.006 Kuang, S. (1996). Geodetic Network Analysis and Optimal Design: Concepts and
Applications. Ann Arbor Press Inc. Li, Y., Ma, H., Wu, J. (2011). Planar Segmentation and Topological Reconstruction for Urban Buildings with Lidar Point Clouds, Proceedings of SPIE 8286, International Symposium on Lidar and Radar Mapping 2011: Technologies and Applications. DOI: http://dx.doi.org/10.1117/12.912838 Lichti, D. D. (2010) A Review of Geometric Models and Self-Calibration Methods
for Terrestrial Laser Scanners. Boletim De Ciencias Geodesicas, 16(1), 3-19. Marjetič, A., Ambrožič, T., Kogoj, D. (2011). Določitev nevertikalnosti visokih dimnikov =Determination of the Nonverticality of High Chimney. Geodetski vestnik, 55(4), 701-712. DOI: http://dx.doi.org/10.15292/geodetski-vestnik.2011.04.701-712
Matas, J., Chum, O. (2004). Rendomized RANSAC with Td,d test. Image and Vision Computing, 22(10), 837-842. DOI: http://dx.doi.Org/10.1016/j. imavis.2004.02.009
Nister, D. (2003). Preemptive RANSAC for live structure and motion estimation. Computer Vision, Proceedings, Ninth IEEE International Conference on, 1, 199-206. DOI: http://dx.doi.org/10.1109/ICCV.2003.1238341
Riegl (2014). Riegl VZ-400. http://www.riegl.com/uploads/tx_ pxpriegldownloads/10_DataSheet_VZ-400_2014-09-19.pdf, dostop 21. 2. 2016.
Seemkooei, A. A. (2001). Strategy for Designing Geodetic Network with High Reliability and Geometrical Strength. Journal of Surveying Engineering, 127(3), 104-117. DOI: http://dx.doi.org/10.1061/(ASCE)0733-9453(2001)127:3(104)
Splichal S. (1990). Analiza besedil. Metodološki zvezki 6, Ljubljana: FDV.
Tarsha-Kurdi, F., Landes, T., Grussenmeyer, P. (2007). Hough-transform and Extended Ransac Algorithms for Automatic Detection of 3D Building Roof Planes from Lidar Data. ISPRS Workshop on Laser Scanning 2007 and SilviLaser 2007, Volume XXXVI, Part 3/W52, 407-412.
Theiler, P. W., Schindler, K. (2012). Automatic Registration of Terrestrial Laser Scanner Point Clouds Using Natural Planar Surfaces. ISPRS Annals of Photogrammetry, Remote Sensing and Spatial Information Sciences, I-3, 173-178. DOI: http:// dx.doi.org/10.5194/isprsannals-I-3-173-2012
Tittmann, P., Shafii, S., Hartsough, B., Hamann, B. (2011).Tree Detection, Delineation, and Measurement from Lidar Point Clouds Using Ransac. In SilviLaser 2011 - 11th International Conference on LiDAR Applications for Assessing Forest Ecosystems: Applications for Assessing Forest Ecosystems, 583-595.
Tordoff, B. J., Murray, D. W. (2005). Guided-MLESAC: faster image transform estimation by using matching priors. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(10), 1523-1535. DOI: http://dx.doi.org/10.1109/ TPAMI.2005.199.
Torr, P. H. S., Zisserman, A. (2000). MLESAC: A new robust estimator with application to estimating image geometry. Journal of Computer Vision and Image Understanding, 78(1), 138-156. DOI: http://dx.doi.org/10.1006/ cviu.1999.0832
Trochim, W. M. K. (2015). Research Methods Knowledge Base. Cornell: Department of Policy Analysis and Management at Cornell University. http://www. socialresearchmethods.net/kb/reliable.php, dostop 21. 10. 2015.
Urbančič, T., Kosmatin Fras, M., Stopar, B., Koler, B. (2014). The influence of the input parameters selection on the RANSAC results. International Journal of Simulation Modelling, 13(2), 159-170. DOI: http://dx.doi.org/10.2507/IJSIMM13(2)3.258
Van der Sande, C., Soudarissanane, S., Khoshelham, K. (2010). Assessment of Relative Accuracy of AHN-2 Laser Scanning Data Using Planar Features. Sensors, 10(9), 8198-8214. DOI: http://dx.doi.org/10.3390/s100908198
Urbančič T., Vrečko A., Kregar K. (2016). The reliability of RANSAC method when estimating the parameters of geometric object. Zanesljivost metode RANSAC pri oceni parametrov geometrijskih oblik. Geodetski vestnik, 60 (1): 69-97. DOI: 10.15292/geodetski-vestnik.2016.01.69-97
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 83 |
| 60/1 |
GEODETSKI VESTNIK
g ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV I GEOMETRIJSKIH OBLIK
I OSNOVNE INFORMACIJE O ČLANKU: GLEJ STRAN 69
1 UVOD
V geodeziji se za zajem prostorskih podatkov vse pogosteje uporabljata lasersko skeniranje in metoda slikovnega ujemanja. Tak zajem podatkov je samodejen in neselektiven. Rezultat je množica točk z znanimi koordinatami. Imenujemo jo oblak točk. Pri obravnavi takšnih podatkov se pojavljata dve težavi, ki otežujeta ali celo onemogočata samodejno obdelavo podatkov ter njihovo uporabo v geodeziji:
— koordinate točk so določene s slabšo natančnostjo kot pri izmeri s klasičnimi geodetskimi tehnikami (na primer polarno tahimetričo izmero), natančnost je tudi težko določljiva ter 5T — za posamezno točko v oblaku točk ni eksplicitno znano, del katerega objekta iz realnega sveta predstavlja.
Obe težavi lahko rešujemo z metodo RANSAC (angl. RANdom SAmple Consensus). Metodo sta za robustno oceno parametrov matematičnega modela razvila Fischler in Bolles (1981). Uporabila sta jo za določitev parametrov zunanje orientacije fotogrametričnega posnetka na podlagi znanih modelnih in slikovnih koordinat oslonilnih točk. RANSAC je bil na primer uporabljen za izboljšanje ocene transformacijskih parametrov med koordinatnima sistemoma (Brown in Lowe, 2002; Barnea in Filin, 2007) in registracijo satelitskih posnetkov (Kim in Im, 2003), ter predvsem za večjo robustnost delovanja drugih algoritmov. Tudi robustnost in hitrost same metode RANSAC so z različnimi prilagoditvami izboljšali predvsem za uporabo na področju računalniškega vida (na primer Torr in Zisserman, 2000; Matas in Chum,2004; Nister, 2003; Tordoff in Murray, 2005).
Na področju obdelave lidarskih podatkov se RANSAC pogosto uporablja za segmentacijo oblakov točk. Omenimo le nekatere primere: Tittmann in sod. (2011) so metodo uporabili za prepoznavanje točk na drevesih, tako da so oblike krošenj modelirali s paraboloidi. Tarsha-Kurdi in sod. (2007) so jo uporabili za prepoznavanje točk, ki pripadajo streham. S primerjavo rezultatov z rezultati Houghove transformacije so ugotovili, da so bile točke, ki predstavljajo strehe, z metodo RANSAC določene hitreje in bolj kakovostno. Na podlagi točk, ki predstavljajo strehe in so jih iz oblaka točk prepoznali z metodo RANSAC, so Van der Sande in sod. (2010) izvedli kontrolo relativne natančnosti aerolaserskega skeni-ranja. Li in sod. (2011) so metodo uporabili za segmentacijo zgradb. Theiler in Schindler (2012) sta jo uporabila pri segmentaciji oblaka točk na ravnine, ki so se uporabljale za samodejno registracijo oblakov točk terestričnega laserskega skeniranja brez uporabe umetnih tarč. Podobno so Huang in sod. (2012) metodo uporabili za prepoznavanje ravnin in valja za potrebe samodejne registracije oblakov točk brez uporabe umetnih tarč.
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 84 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 
| 60/1 |
Zanesljivost v geodeziji navadno opisujemo kot odpornost matematičnega modela proti grobim po-	^
greškom (Seemkooei, 2001). Sicer zanesljivost pri uporabi raziskovalnih metod razumemo kot kakovost	i= '
rezultatov teh orodij v smislu ponovljivosti oziroma konsistentnosti (Trochim, 2015). Spichal (1990)	p opisuje zanesljivost kot dopustno stopnjo slučajnih pogreškov v rezultatih raziskovanja.
V	naši raziskavi predstavljamo analizo zanesljivosti izvorne metode RANSAC (Fischler in Bolles, 1981), ¡f tako da na različnih primerih pokažemo, kako se razlikujejo rezultati, ki jih dobimo, če metodo upora- 'ii bimo večkrat na istih podatkih.
Poskusi temeljijo na treh osnovnih geometrijskih oblikah: krogli, stožcu in ravnini. V postopkih laserskega skeniranja se obe telesi uporabljata za določitev karakterističnih točk, ki jih uporabljamo za vezne točke pri registraciji ali kot tarče pri kalibraciji laserskih skenerjev. Ravnine ne moremo uporabljati za določanje karakteristične točke, nepogrešljiva pa je pri postopkih segmentacije oblakov točk.
V	članku najprej opišemo orodja, ki jih bomo v raziskavi uporabili. To so: algoritem RANSAC, geometrijski modeli, določitev parametrov geometrijskih oblik z izravnavo po metodi najmanjših kvadratov in določitev natančnosti teh parametrov. Natančnost parametrov enkrat določimo s postopkom izravnave, drugič pa kot standardni odklon rezultatov mnogih ponovitev postopka.
V	nadaljevanju preverjamo ponovljivost postopka za določitev koordinat karakterističnih točk iz ske-nogramov krogel in stožcev. Nato iz umetno generiranih podatkov z metodo RANSAC prepoznavamo ravnino in opazujemo zanesljivost prepoznavanja.
V	razpravi poskušamo utemeljiti rezultate in navesti razloge. Sklenemo z nekaj napotki za praktično uporabo metode RANSAC pri obdelavi oblakov točk.
2 METODE
2.1 Opis algoritma RANSAC
Z algoritmom RANSAC iz oblaka točk poiščemo tiste točke, ki pripadajo objektom (ali delom objektov), ki jih lahko opišemo z matematičnimi izrazi. Take točke bomo v nadaljevanju imenovali inlierji. Algoritem RANSAC temelji na ideji, da optimalni parametri modela opišejo model, ki vključuje največ točk. Izvedemo ga tako, da parametre nekega modela geometrijske oblike določimo na podlagi točk , ki jih iz oblaka točk izberemo naključno. Nato preštejemo, koliko preostalih točk oblaka pripada tako določenemu modelu, pri čemer upoštevamo izbran prag dovoljenega odstopanja od modela. Postopek ponavljamo, dokler ne dosežemo želene stopnje zaupanja (Fischler in Bolles, 1981).
Vhodni podatki za algoritem so:
m — najmanjše število potrebnih točk za določitev modela, t — prag, s katerim so določene točke, ki še pripadajo modelu, w — pričakovani delež inlierjev v oblaku točk,
p — stopnja zaupanja (verjetnost, da v vsaj enem od poskusov naključno izberemo samo inlierje), S — podatki oziroma oblak točk.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 85 |
| 60/1 |
GEODETSKI VESTNIK
^ Algoritem:
^ 1. določi število ponovitev (glej poglavje 2.2); 1 2. za k = 1, ... , N
—	naključno vzorči m točk iz S ^ Sk
—	iz Sk določi parametre matematičnega modela Mk
—	S* = {s\s 6 S\ Sk A^k (s)< i}
3. S' = {S* 11 S || = ^m3^ |S p
kjer je 5,(s) oddaljenost točk iz S od matematičnega modela M. Rezultat algoritma je množica S*. To je tista izmed množic S', ki vsebuje največ točk.
2.2 Določitev števila ponovitev N
Parameter N pomeni število iteracij, ki glede na izbrano stopnjo zaupanja p zagotavljajo, da v vsaj eni od ponovitev določimo parametre modela samo iz inlierjev. Izračunan je iz najmanjšega števila točk m, ki enolično določajo model, ter predvidenega deleža inlierjev w v množici točk S. Tako je W verjetnost, da so vse točke v podmnožici Sk inlierji. Iz tega sledi, da je 1 — Wm verjetnost, da je vsaj ena od točk iz podmnožice Sk outlier. Pri N ponovitvah je (1 — wm)N verjetnost, da je vsaj v eni od ponovitev v množici Sk prisoten outlier. Torej je verjetnost, da algoritem nikoli ne izbere samo inlierjev, enaka (Fischler in Bolles, 1981):
1 — p = (1 — wm)N.	(1)
Z večanjem števila ponovitev N lahko stopnjo tveganja 1 — p poljubno zmanjšamo. Ob želeni stopnji zaupanja in predpostavki o vrednosti w dobimo parameter N kot rezultat logaritmiranja enačbe (1):
N = Jog(^I.	(2)
log (1 — u>m )
Več o vplivu izbora vhodnih parametrov na rezultate pri iskanju modelov krogle in stožca z algoritmom RANSAC lahko preberemo v Urbančič in sod. (2014).
2.3 Matematični modeli geometrijskih oblik
V prispevku obravnavamo tri geometrijske oblike (ravnino, kroglo in stožec). Za vse tri je treba določiti parametre modela ob minimalnem številu znanih točk m ter odstopanj ostalih točk od modela.
2.3.1 Ravnina
Splošno enačbo ravnine zapišemo kot:
ax + by + cz — d = 0,	(3)
kjer so a, b, c in d parametri ravnine; x, y in z pa koordinate točke, ki leži na ravnini.
V enačbi imamo štiri neznanke, za določitev ravnine pa so nujne tri točke (m = 3). Parametre ravnine določimo v dveh korakih: najprej določimo parametre a, b in c, nato pa še parameter d. Parameter d iz
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 86 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK | 60/1 |
enačbe (3) eliminiramo tako, da koordinatam vseh treh točk odštejemo njihovo povprečje. S tem izhodišče ^ koordinatnega sistema postavimo na ravnino. Ker s premikom nismo vplivali na naklon ravnine, bodo i= ' parametri a, b in c, ki določajo smer normale na ravnino, ostali nespremenjeni.
Koordinate, reducirane na težišče, zapišemo kot vrstice v matriko M3x3. Parametri a, b in c so komponente s lastnega vektorja, ki pripada najmanjši lastni vrednosti matrike M. Parameter d določimo tako, da v |T enačbo (3) vstavimo parametre a, b in c ter koordinate ene od treh izbranih točk.
Pravokotne oddaljenosti vseh točk v oblaku točk S od določene ravnine izračunamo kot dolžino pravo- § kotnih projekcij krajevnih vektorjev točk na normalo ravnine:
S = [Xi ~ xc Ji - Jc z. - z][a b c]T,	(4)
kjer so xc, yc in zc koordinate težišča oblaka točk. Pri metodi RANSAC za ravnino kot inlierje obravnavamo točke, za katere velja |S| < t (glej poglavje 2.1).
2.3.2	Krogla
Splošno enačbo krogle zapišemo kot:
(x, - Xc)2 + (j,-Jc)2 + (z, - z)2 - r 2 = 0.	(5)
Za enolično določitev krogle potrebujemo štiri točke, ki ležijo na njeni površini in ne ležijo v isti ravnini. Iščemo štiri parametre krogle: koordinate središča krogle (x ,y, z') in radij r. Določitve parametrov se lahko lotimo na različne načine (Franaszek in sod., 2009). Lahko uvedemo nove spremenljivke a, ¡, y in sv enačbo (5):
x2 +y2+z2 - ax-¡y- yz + s= 0,	(6)
kjer spremenljivke in določimo z rešitvijo štirih enačb za štiri dane točke s koordinatami x,y , z.. Parametre krogle nato izračunamo z naslednjimi enačbami:
x =a, j =1 , z =l , r2=(a)2+{£\+{L\-s.	(7)
c 2 Jc 2 c 2 L 2 J L 2 J L 2 J
Ko poznamo koordinate središča krogle, lahko izračunamo oddaljenost di vseh točk oblaka od nje. Pravokotna oddaljenost točk od površja krogle je S. = d - r. Pri metodi RANSAC za kroglo kot inlierje obravnavamo točke, za katere velja |S| < t (glej poglavje 2.1).
2.3.3	Stožec
Enačbo pokončnega stožca zapišemo kot:
(xS-x0)2 + (yS-y0)2 - (k • zS+£)2 = 0,	(8)
kjer so xS,ys in zS koordinate točk na plašču stožca; x0 iny0 sta položaja presečišča osi stožca z ravnino z = 0; k je naklonski koeficient linearne funkcije R=f(z) = k • zs + h; pa polmer stožca na višini z = 0.
Stožec definirajo koordinate vrha stožca, orientacija stožca v prostoru ter kot med osnovno ploskvijo in plaščem stožca. V splošnem je lahko stožec v prostoru poljubno orientiran, zato enačbo zapišemo tako,
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 87 |
| 60/1 |
GEODETSKI VESTNIK
da bo omogočala splošno rešitev. Usmerjenost osi stožca lahko opišemo z zasuki modela stožca v kartezičnem koordinatnem sistemu okoli koordinatnih osi x in y za kota cox in co . Stožec je glede na svojo os simetričen, zato zasuk okoli koordinatne osi ni smiseln. Uporabimo skupno rotacijsko matriko, ki jo dobimo z množenjem rotacijskih matrik R in R v naslednjem vrstnem redu R = R R . Z uporabo skupne rotacijske matrike lahko zapišemo povezavo med koordinatnim sistemom stožca (x,y, zS) in zunanjim koordinatnim sistemom (x,y, z), prikazanim na sliki 1 kot (Marjetič in sod., 2011):
(9)
xs		x
y	= R	y
_ Zs _		z
Slika 1: Koordinatni sistem oblaka točk (x,y,z) in koordinatni sistem stožca (xS, yS,zS).
Če enačbo (9) vstavimo v enačbo (8), dobimo naslednjo povezavo med točkami in parametri stožca, ki je lahko poljubno orientiran:
(r11x + r12y + r13 z - x0)2 + (r2]x + r22y + r23 z - y0)2 - (k(r x + r32y + r33 z) + u)2 = 0,
(10)
kjer so r.. elementi rotacijske matrike R, ki so izraženi kot funkcije kotov cox in co . Stožec določa šest točk, zato parametre stožca določimo z rešitvijo sistema šestih enačb, za šest točk, zapisanih v obliki (10).
Z znanimi parametri stožca lahko določimo pravokotne oddaljenosti S. vseh točk od modela:
S. = sin(^) d,,	(11)
kjer je kot med plaščem stožca in smerjo od vrha stožca proti točki ter d. razdalja med vrhom stožca in točko. Pri metodi RANSAC za stožec kot inlierje obravnavamo točke, za katere velja |S.| < t (glej poglavje 2.1).
2.4 Izravnava parametrov izbranih geometrijskih oblik
Rezultat algoritma RANSAC je množica točk S*, ki pripadajo najboljšemu modelu izbrane geometrijske oblike. Uporabnikov končni cilj pa je običajno določitev parametrov modela izbrane geometrijske oblike
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 88 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 
| 60/1 |
na podlagi točk, ki so rezultat algoritma RANSAC. Za rešitev uporabimo splošni model izravnave po	^
metodi najmanjših kvadratov. Matematični modeli za ravnino, kroglo in stožec so podani v enačbah (3),	¡¡i'
(5) in (10). Modeli predstavljajo soodvisnost med opazovanji (v našem prispevku so to koordinate točk,	^
ki ležijo na geometrijski obliki) in neznankami (v našem prispevku so to parametri geometrijske oblike).	£
Model lineariziramo z odvajanjem po opazovanjih in neznankah ter ga v matrični obliki zapišemo kot: ¡f Av+BA = f,	(12) g
kjer so: A — matrika koeficientov opazovanj, v — popravki opazovanj, B — matrika koeficientov parametrov, == A — popravki približnih vrednosti neznank in f — vektor odstopanj opazovanj od matematičnega modela.
Iskane vrednosti popravkov približnih vrednosti neznank A dobimo z rešitvijo sistema enačb (12) po metodi najmanjših kvadratov:
A = (Br(AAr)-1B)-1(Br(AAr)-1f).	(13)
Stohastične lastnosti izravnanih parametrov opisuje matrika:
Saa = ^(BW)-1B)"1,	(14)
kjer je cr20 referenčna varianca aposteriori. Podrobnosti o izravnavi najdemo tudi v Kuang (1996) ter Grigillo in Stopar (2003).
2.5 Analiza zanesljivosti metode RANSAC
Natančnosti izravnanih parametrov, ki jih izračunamo z enačbo (14), so določene na podlagi odstopanj točk v množici S* od matematičnega modela. Tako ne ocenimo vpliva naključnega vzorčenja v drugem koraku metode RANSAC na določitev parametrov.
Ob ponovitvi metode z istimi podatki in pri istih nastavitvah vhodnih parametrov rezultat ne bo nujno enak. Ta vpliv smo analizirali tako, da smo za vsak oblak točk metodo RANSAC in izravnavo parametrov oblik izvedli stokrat. Tako smo pridobili sto koordinat karakteristične točke s pripadajočimi ocenami natančnosti.
Analiza zanesljivosti oziroma ponovljivosti metode RANSAC temelji na rezultatih stotih neodvisnih ponovitev izračuna parametrov iskanih geometrijskih oblik. Vrednosti vhodnih parametrov so v vseh ponovitvah enake.
Za merilo natančnosti parametrov x(g), y(g) in z(g), ocenjenih iz množice točk S* za g = 1, ..., 100 ponovitev, uporabimo standardne odklone CTx(g), ct^ in ct^, ki so rezultat izravnave po metodi najmanjših kvadratov (matrika SAA(^).
Kot merilo natančnosti ocenjenih parametrov posamezne ponovitve ct^, ct^ in (Tg, (v preglednici 1 so zapisane poševno in pobarvane z rdečo) uporabimo kvadratni koren srednje vrednosti stotih varianc
a-2 <j2 in a2
x(g) y(g) z(g
Za sto ponovitev natančnost izračunamo kot standardne odklone stokrat izračunanih parametrov. Označimo jih z ct, ct in oz, v preglednici 1 so zapisani podčrtani z modro barvo. V preglednici 1 smo za pojasnitev razlik med obema meriloma prikazali praktičen primer izračuna.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 89 |
| 60/1 |
GEODETSKI VESTNIK
Preglednica 1: Numeričen primer izračuna ocen natančnosti za posamezno in sto ponovitev.
		Parametri			Natančnosti	
	* [m]	y [m]	z [m]	7 [mm]	7y [mm]	7z [mm]
1	-1,17722	4,03986	-0,27292	0,039	0,016	0,040
2	-1,17762 4,04002 -0,27288	0,038	0,018	0,039
3	-1,17724 4,04008 -0,27295	0,039	0,022	0,039
100	-1,17720 4,04004 -0,27298	0,040	0,027	0,040
	-1,17745	4,04020	-0,27293	0,040	0,030 0,041
St. odklon	7. [mm]	77 [mm]	7-z [mm]		
	0,172	0,333	0,063		
Pri obravnavi generiranega oblaka točk je bilo znano, katere točke pripadajo ravnini, zato smo za posamezno točko lahko preverili, ali je bila z metodo RANSAC pravilno določena kot inlier oziroma outlier. Tako smo lahko določili delež napak prvega in drugega reda. Napaka prvega reda ex je število točk, ki jih RANSAC določi kot inlierje, pa ravnini ne pripadajo. Nasprotno je napaka drugega reda e2 število točk, ki jih RANSAC ne določi kot inlierje, pa ravnini pripadajo.
3 REZULTATI
Pri postopkih samokalibracije terestričnega laserskega skenerja (Lichti, 2010) s skenerjem izmerimo položaje identičnih točk z različnih stojišč. Tehnologija TLS ne omogoča merjenja položaja poljubne točke, zato jih signaliziramo s tarčami v obliki geometrijskih teles. Take tarče omogočajo dovolj kakovostno določitev karakterističnih točk iz oblaka točk.
Pri terestričnem laserskem skeniranju objekta z več stojišč je treba oblake točk združiti v enoten oblak točk. Tako združitev oblakov točk imenujemo registracija. Postopek registracije izvedemo s podobno-stno transformacijo oblakov točk v skupni koordinatni sistem. Za določitev parametrov transformacije moramo poznati koordinate vsaj treh identičnih točk v izhodiščnem in ciljnem koordinatnem sistemu. Te točke imenujemo vezne točke. Uporabo veznih točk, materializiranih z geometrijskimi oblikami, sta na praktičnem primeru prikazala Barbarella in Fiani (2013).
Za določitev veznih ali kontrolnih točk predlagamo uporabo geometrijskih oblik krogle in stožca, saj omogočata kakovostno določitev koordinat karakteristične točke v vseh treh dimenzijah.
3.1 Ravnina
Ravnine zaradi njene oblike ne moremo uporabljati za določitev karakteristčnih točk, zelo uporabna pa je pri postopkih segmentacije. Segmentacija pomeni razdelitev oblaka točk na več manjših delov, pri čemer točke teh delov (segmentov) povezujejo skupne lastnosti. Tipična takšna lastnost je pripadnost skupni ravnini.
Točke, ki pripadajo ravnini, smo najprej iskali v umetno generiranem oblaku točk. Simulirali smo točke na ravnini s parametri a = 2, b = 4, c = —3, d = 3, ki pa smo jim dodali normalno porazdeljen šum s
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 64 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 	| 60/1 |
standardno deviacijo 5 centimetrov. Oblaku točk ravnine smo nato dodali točke, ki ne ležijo na ravnini in so enakomerno razporejene po prostoru. Izvedli smo deset ponovitev, pri tem pa spreminjali delež inlierjev w. V algoritem smo vsakokrat vnesli znane (prave) vrednosti parametrov t in w in zahtevali 99-odstotno stopnjo zaupanja. Rezultati algoritma, kjer vidimo tudi delež najdenim inlierjev i, so podani v preglednici 2 in na sliki 2.
Preglednica 2: Rezultati metode RANSAC na simuliranih ravninah t [cm]	w	p	N	i	e	e2
5	10 (2,4 %) 99 %	317391 32/410 = 7,8 %	30	8
5 20 (4,8 %) 99 %	42647 34/420 = 8,1 %	17	3
5	30 (7,0 %) 99 %	13559 44/430 = 12,2 %	14	0
5 40 (9,1 %) 99 %	6128 49/440 = 11,1 %	15	6
5 75 (15,8 %) 99 %
1168 80/475 = 16,8 %	13	8
5 100 (20,0 %) 99 %	574 110/500 = 22,0 %	13	3
5 150 (27,3 %) 99 %
225 139/550 = 33,5 %	11	22
5 200 (33,3 %) 99 %	123 191/600 = 31,8 %	11	20
5 300 (42,9 %) 99 %
57 236/700 = 33,7 %	8	72
5 400 (50,0 %) 99 %	35 282/800 = 35,3 %	11	129
Slika 2: Prikaz rezultatov metode RANSAC na generiranem oblaku točk iz dveh različnih perspektiv. Uporabljen je bil prvi niz podatkov iz preglednice 2. Rdeče točke - točke na generirani ravnini; modre točke - točke, ki ne pripadajo generirani ravnini; črni zanki + - točke, ki jih je kot točke na ravnini prepoznala metoda RANSAC.
Za oceno zanesljivosti algoritma smo izračun pri vhodnih podatkih t = 5 cm, w = 50% in p = 99% ponovili stokrat in tako kot pri krogli ter stožcu opazovali razliko med natančnostjo parametrov posamezne in vseh ponovitev. Rezultati ocenjenih parametrov in njihovih standardnih deviacij (ocena natančnosti) so v preglednici 3 in na sliki 3.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 65-97 |	| 89 |
| 60/1 |	GEODETSKI VESTNIK
Preglednica 3: Primerjava natančnosti iz posamezne in stotih ponovitev - ravnina
	Generirani	Posamezna ponovitev	Sto ponovitev
	[m]	parameter in natančnost [m]	parameter in natančnost [m]
a	2,000	a = 1,931 o = 0,018	a = 2,009 o = 0,079
b	4,000	b = 4,192 o = 0,021 b	b = 3,998 o = 0,154 b
c	-3,000	c = -2,971 o = 0,034	c = -2,985 o = 0,110
d	3,000	d = 3,050 od = 0,015	d = 3,004 od = 0,111
Slika 3: Prikaz različnih ravnin, določenih na podlagi rezultatov stotih ponovitev metode RANSAC. Črne točke - točke, ki ležijo na iskani ravnini; rdeče točke - točke na ravnini, ki jim je dodan normalno porazdeljen šum; sive, prosojne ravnine -ravnine, ki smo jih dobili v sto ponovitvah metode RANSAC na rdečih točkah.
3.2 Krogla
Najbolj enostaven model za določitev karakteristične točke je krogla. Pri izvrednotenju središča krogle iz skeniranega oblaka točk pa naletimo na nekatere omejitve:
(i)	z enega stojišča lahko skeniramo največ polovico površine krogle;
(ii)	na robovih krogle (gledano s stojišča skenerja) se od krogle odbije le del laserskega žarka, kar povzroči podatkovne artefakte (Hebert in Krotkov, 1992);
(iii)	na površino krogle, ki je pravokotna na vpadli laserski žarek, je lahko intenziteta odboja prevelika, to pa lahko povzroči grobi pogrešek merjene dolžine;
(iv)	območje skeniranja je pravokotno okno, kar pomeni, da poleg točk krogle vedno zajamemo več ali manj okoliških točk, ki ne pripadajo krogli.
Z metodo RANSAC lahko iz oblaka točk odstranimo točke, ki ne pripadajo modelu krogle.
Analizo smo izvedli na skeniranih oblakih točk petih krogel. Krogle z enakimi radiji so bile skeni-rane z instrumentom Riegl VZ-400. Instrument omogoča skeniranje točke na razdalji 100 metrov z natančnostjo 3 milimetre in točnostjo 5 milimetrov, laserski žarek ima pri izhodu premer žarka 7 milimetrov ter divergenco 0,35 mrad (Riegl, 2014). Krogle so skenirane z razdalje ~ 30 metrov z ločljivostjo približno 1x1 milimeter. Vseh pet skeniranih oblakov točk vsebuje pogrešene točke zaradi zgoraj naštetih razlogov (ii), (iii) in (iv). Za vseh pet krogel smo vhodne parametre nastavili na
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 66 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 
| 60/1 |
t = 2 mm, w = 50 % in p = 99 %. Za želeno stopnjo zaupanja moramo naključni vzorec štirih točk iz vsakega oblaka izbrati 72-krat. V preglednici 4 so ocenjene natančnosti posamezne in stotih ponovitev postopka (poglavje 2.5).
Preglednica 4: Primerjava natančnosti iz posamezne in stotih ponovitev - krogla
Posamezna ponovitev [mm]						Sto ponovitev [mm]				
Krogle	V16	V1	V17	V19	V3	V16	V1	V17	V19	V3
CT	0,13	0,14	0,10	0,14	0,24	0,52	9,37	2,48	9,15	38,59
ct y	0,05	0,05	0,04	0,05	0,07	0,16	2,33	0,95	4,01	6,96
<Jz	0,04	0,05	0,04	0,05	0,05	0,11	1,76	1,02	1,58	2,53
	0,10	0,11	0,07	0,11	0,22	0,39	7,89	1,92	8,24	25,72
Za vsako od krogel V16, V1, V17 in V19 smo na sliki 4 prikazali: oblak točk (črna), izravnano kroglo (modra) ter standardna elipsoida pogreškov za središče krogle — posameznaponovitev (črna) in sto ponovitev (rdeča).
Slika 4: Oblaki točk, izravnane krogle ter oba standardna elipsoida pogreškov za krogle V16, VI, V17 in V19. (Standardni elipsoid ene ponovitve je zelo majhen.)
Krogla V3 je poseben primer, pri katerem so središča krogle zavzemala zelo različne vrednosti, ki jih lahko prikažemo s tremi tipičnimi primeri. Prikazani so na sliki 5.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 67-97 |	| 89 |
| 60/1 |	GEODETSKI VESTNIK
3.3 Stožec
Pri stožcu je karakteristična točka vrh stožca. Koordinate vrha stožca smo izračunali po postopku v poglavju 2.3.3.
Preglednica 5: Primerjava natančnosti iz posamezne in stotih ponovitev - stožec.
Posamezna ponovitev [mm]					Sto ponovitev [mm]			
Strmina stožca[°]	20	30	45	60	20	30	45	60
a	0,12	0,08	0,05	0,02	1,75	0,46	0,30	0,11
a	0,12	0,09	0,05	0,02	1,73	0,56	0,32	0,10
az	0,06	0,03	0,04	0,03	0,18	0,13	0,16	0,20
a)	b)
Slika 6: Prikaz oblakov točk, izravnanega stožca in obeh standardnih elipsoidov pogreškov: a) 20°, b) 30°, c) 45° in d) 60°.
Za preizkus predlagane metode iskanja modela stožca bomo uporabili del podatkov skeniranega testnega polja. Testno polje vključuje štiri modele stožcev z radiji osnovne ploskve 5,0 centimetra ter različnimi koti med osnovno ploskvijo in plaščem stožca: 20 30 45° in 60 Skeniranje je bilo opravljeno s tere-
Tilen Urbancic, Anja Vrecko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
| 68 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK
| 60/1 |
stričnim laserskim skenerjem Riegl VZ-400 z razdalje 6,4 metra z ločljivostjo približno 2x2 milimetra.	^
Pri izračunu smo uporabili naslednje parametre: t = 2 mm, w = 35 % in p = 95 %. V preglednici 5 so	i=
predstavljene povprečne natančnosti določitve koordinat vrha stožca za posamezno ponovitev in razprše-	¡g nost koordinat vrha stožca, določenih iz stotih ponovitev.
Grafični prikaz rezultatov določitve koordinat vrha stožca na obravnavanem testnem polju je na sliki 6.	=
Prikazane so točke ter izračunan model stožca po izravnavi matematičnega modela iz vseh inlierjev za	'¿i
eno od rešitev algoritma RANSAC. Izrisana elipsoda se nanašata na natančnosti iz preglednice 5 in sta	g v merilu 50.000 : 1.
4 RAZPRAVA
Na podlagi analize rezultatov obdelave generiranega oblaka točk (poglavje 3.3), kjer smo vnaprej poznali prave parametre ravnine, delež inlierjev w in šum na točke ravnine t, lahko razberemo nekaj splošnih značilnosti metode RANSAC:
—	večji p in večji w pomenita več iteracij ^ več računskega časa. Razmerje je opisano v enačbi (2);
—	pri manjšem deležu inlierjev je bilo več točk z napako tipa 1, pri večanju deleža inlierjev pa se poveča verjetnost za napako tipa 2.
Parametri ravnine so na podlagi stotih ponovitev določeni bolj točno kot na podlagi posamezne ponovitve. Podobno kot pri krogli in stožcu se je pokazalo, da so ocene parametrov iz stotih ponovitev veliko bolj razpršene, kot bi lahko sklepali iz ocene natančnosti parametrov na podlagi posamezne ponovitve.
Pri določitvi koordinat karakteristične točke nas je najbolj zanimala kakovost te določitve. Ocene natančnosti koordinat karakteristične točke na podlagi posamezne ponovitve metode RANSAC so zelo optimistične. Ta ocena je določena na podlagi odstopanj točk, izbranih z metodo RANSAC, od matematičnega modela in je tako neposredno povezana z izbranim pragom t; manjši kot je t, bolj se bodo izbrane točke prilegale modelu in boljša bo ocenjena natančnost določitve koordinat. Ta mera sicer ne pove ničesar o zanesljivosti metode RANSAC, saj ne vemo, ali so bile iz oblaka točk izbrane prave točke. Ob večkratni ponovitvi metode RANSAC ob istih vhodnih podatkih smo, tako za kroglo kot za stožec, dobili vsaj trikrat večjo razpršenost vseh treh koordinat karakteristične točke kot pri posamezni ponovitvi.
Z metodo RANSAC za kroglo V3 ni uspelo v vseh ponovitvah določiti točk, ki so pripadale dejanski krogli, ampak je več točk pripadalo mnogo večji krogli (slika 5). Možnost za tako napako lahko zmanjšamo s predhodno obdelavo podatkov (na primer s filtriranjem po intenziteti) ali če predhodno poznamo katerega od parametrov (na primer radij krogle ali naklon stožca).
Glede na natančnost skeniranja oziroma natančnost določitve koordinat točk z nastavitvijo praga t v določenih primerih močno posežemo v končni rezultat. Velikost in orientacija standardnih elipsoidov pogreškov sta zelo različna. Orientacija elipsoidov pri krogli je odvisna od položaja skenerja glede na kroglo, največja polos elipsoida je usmerjena v smeri proti skenerju. Pri modelih stožca je pri stožcu z največjim kotom med osnovno ploskvijo in plaščem (60°) razpršenost večja v smeri osi stožca, medtem ko je pri ostalih stožcih razpršenost večja v ravnini, ki je vzporedna z osnovno ploskvijo. Orientiranost
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
95
|60/1|
GEODETSKI VESTNIK
elipsoidov je odvisna tako od geometrije skeniranega stožca kot od relativnega položaja skenerja glede stožec. Položaj skenerja na sliki 7 predstavlja točka (0,0,0). Standardni elipsoidi so glede na oblak točk, ki je prikazan v metrih, izrisani v merilu 50.000 : 1.
Slika 7: Standardni elipsoidi zanesljivosti metode RANSAC za modele stožcev.
Kadar nas torej zanimajo vrednosti in natančnosti parametrov modela, ki jih določimo z izravnavo z metodo RANSAC določenih točk, ni dovolj, da upoštevamo samo natančnosti določitve parametrov, določene z izravnavo. Naši rezultati so pokazali, da je tako določena natančnost vedno precenjena, saj ne upošteva (ne)zanesljivosti metode RANSAC. Z nekajkratno ponovitvijo postopka, ki je v praksi ni težko izvesti, saj RANSAC ni procesno ali časovno potraten, lahko preverimo, ali so rezultati iz različnih ponovitev med seboj konsistentni. Glede ocenjevanja natančnosti parametrov pa lahko povemo, da je dejanska natančnost izvrednotenih parametrov odvisna od oblike geometrijskega telesa in opazovanj samih (torej od konkretnega primera).
Pomembno se nam zdi poudariti, da se vse natančnosti in elipsoidi pogreškov pri obravnavi krogel in stožcev nanašajo na vrednotenje postopka RANSAC, saj smo uporabili oblake točk v koordinatnem sistemu skenerja. Pri uporabi metode RANSAC v praksi bi na natančnost dobljenih parametrov močno vplivali tudi natančnosti koordinat oslonilnih točk, instrumentalni pogreški in pogreški okolja, zato ne bi mogli doseči natančnosti v tem velikostnem razredu.
Postopek RANSAC je zelo robusten. Uporabljamo ga lahko pri mnogo različnih nalogah, zavedati pa se moramo, da temelji na naključju in zato pri ponovitvi postopka ne moremo dobiti identičnih rezultatov. Predvsem želimo poudariti, da je pri uporabi metode RANSAC nujna določena stopnja previdnosti, še posebno, ko potrebujemo rezultate visoke točnosti ali natančnosti.
Zahvala:
Prispevek je nastal v okviru doktorskega študija avtorjev, ki sta ga sofinancirala Evropski socialni sklad ter Javna agencija za raziskovalno dejavnost Republike SLovenije. Za opravljeno terestično lasersko skeniranje se avtroji prispevka zahvaljujemo podjetju DFG Consulting.
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
96 | RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |
GEODETSKI VESTNIK 	| 60/1 |
Literatura in viri:
Glej literaturo na strani 83.
Urbančič T., Vrečko A., Kregar K. (2016). The reliability of RANSAC method when estimating the parameters of geometric object. Zanesljivost metode RANSAC pri oceni parametrov geometrijskih oblik. Geodetski vestnik, 60 (1): 69-97. DOI: 10.15292/geodetski-vestnik.2016.01.69-97
asist. Tilen Urbančič, univ. dipl. inž. geod.
Univerza v Ljubljani, Fakulteta za gradbeništvo in geodezijo Jamova cesta 2, SI-1000 Ljubljana, Slovenija e-naslov: tilen.urbancic@fgg.uni-lj.si
asist. Anja Vrečko, univ. dipl. inž. geod.
Tomšičeva ulica 50, SI-2310 Slovenska Bistrica e-naslov: vrecko.anja@gmail.com
asist. Klemen Kregar, univ. dipl. inž. geod.
Univerza v Ljubljani, Fakulteta za gradbeništvo in geodezijo Jamova cesta 2, SI-1000 Ljubljana, Slovenija e-naslov: klemen.kregar@fgg.uni-lj.si
Tilen Urbančič, Anja Vrečko, Klemen Kregar | ZANESLJIVOST METODE RANSAC PRI OCENI PARAMETROV GEOMETRIJSKIH OBLIK | THE RELIABILITY OF
RANSAC METHOD WHEN ESTIMATING THE PARAMETERS OF GEOMETRIC OBJECT | 69-97 |	| 89 |