Fitting spherical objects in 3D point cloud using the geometrical constraints

5

FITTING SPHERICAL OBJECTS IN

3D POINT CLOUD USING

THE GEOMETRICAL CONSTRAINTS

Le Van Hung^1,2, Vu Hai¹, Nguyen Thi Thuy³, Le Thi Lan¹, Tran Thi

Thanh Hai¹

Abstract

Estimating parameters of a primitive shape from a 3-D point cloud usually meets dif-

ficulties due to noises of data require a huge amount of computational time. The real point

cloud of objects in the 3D environment have many noise and may be obscured when they are

captured from Kinect version 1. In this paper, we utilize and analyse of spherical estimation

steps from the point cloud data in Schnabel et al. [1]. From this, we propose a geometrical

constraint to search ’good’ samples for estimating spherical model and then apply to a new

robust estimator named GCSAC (Geometrical Constraint SAmple Consensus). The proposed

GCSAC algorithm takes into account geometrical constraints to construct qualified samples.

Instead of randomly drawing minimal subset sample, we observe that explicit geometrical

constraint of spherical model could drive sampling procedures. At each iteration of GCSAC,

the minimal subset sample is selected by two criteria (1) They ensure consistency with the

estimated model via a roughly inlier ratio evaluation; (2) The samples satisfy geometrical

constraints of the interested objects. Based on the qualified samples, model estimation and

verification procedures of a robust estimator are deployed in GCSAC. Comparing with the

common robust estimators of RANSAC family (RANSAC, PROSAC, MLESAC, MSAC, LO-

RANSAC and NAPSAC), GCSAC overperforms in term of both precisions of the estimated

model and computational time. The implementations and evaluation datasets of the proposed

method are made publicly available.

Ước lượng các tham số của một cấu trúc hình học cơ bản (hình cầu, hình trụ, hình nón

... ) từ một tập đám mây điểm 3-D thu từ cảm biến Kinect thường gặp các khó khăn do

dữ liệu có nhiễu và đòi hỏi thời gian tính toán lớn. Trong bài báo này, chúng tôi đề xuất

thuật toán ước lượng đối tượng hình cầu với ý tưởng chính là tìm ra các mẫu “tốt” cho việc

ước lượng mô hình hình cầu nhằm giảm thời gian tính toán cũng như tăng độ chính xác

của mô hình dự đoán. Thuật toán đề xuất có tên GCSAC (Geometrical Constraints Samples

Consensus - Ràng buộc hình học và sự đồng thuận của các mẫu) được xây dựng dựa trên

thuật toán ước lượng mạnh RANSAC (RANdom SAmple Consensus). GCSAC sử dụng các

phân tích hình học của Schnabel et al. [1] để xác định bộ tham số cho một hình cầu. Thay vì

chọn tập mẫu ngẫu nhiên như trong thuật toán RANSAC, trong GCSAC, chúng tôi đề xuất

một ràng buộc về hình học để lựa chọn các mẫu “tốt” có đủ điều kiện cho dự đoán mô hình.

Sử dụng trên các mẫu có chất lượng, mô hình sẽ được “dự đoán” và “kiểm chứng” trong

GCSAC như đối với các bộ ước lượng RANSAC. Tại mỗi lần lặp lại của GCSAC, tập hợp

mẫu nhỏ nhất được lựa chọn theo hai tiêu chí: (1) Đảm bảo tính nhất quán với mô hình ước

lượng thông qua một đánh giá tỷ lệ số mẫu inlier; (2) Các mẫu phải thỏa mãn ràng buộc hình

1

2

International Research Institute MICA, HUST - CNRS/UMI-2954 - GRENOBLE INP, Vietnam, Tan Trao

University, ³Vietnam National University of Agriculture

Chuyên san Công nghệ thông tin và Truyền thông - Số 11 (04-2018)

học đã đề xuất trong quá trình ước lượng. GCSAC được so sánh với các bộ ước lượng mạnh

khác là các biến thể của RANSAC (RANSAC, PROSAC, MLESAC, MSAC, LO-RANSAC

và NAPSAC). Kết quả đánh giá cho thấy GCSAC hoạt động tốt hơn về cả độ chính xác của

mô hình ước lượng và thời gian tính toán. Việc thực hiện đánh giá của phương pháp đề xuất

đã được công bố trong cộng đồng nghiên cứu.

Index terms

Robust Estimator; Primitive Shape Estimation; RANSAC and RANSAC Variations; Qual-

ity of Samples; Point Cloud data.

1. Introduction

STIMATING parameters of a primitive shape using robust estimators is a funda-

mental research in the fields of robotic and computer vision. To build the aiding

E

system for visually impaired people or robot control system for object grasping then

objects detection, pose estimation of object in the 3D environment are the important

steps. Therein, the object detection that using the primitive shapes detection from the

point cloud data of objects is a method. Currently, many robust estimators have been pro-

posed such as Hough Transform [2], RANSAC [3], RANSAC variations (e.g., MLESAC

[4], PROSAC [5], LO-RANSAC [6], etc). RANSAC is a efficient iteration algorithm

that is proposed by Fischler et al. [3] since 1981. Originally, a RANSAC paradigm

draws randomly a Minimal Sample Set (MSS) from a point cloud data without any

assumptions. As a result, RANSAC must run a relatively large number of iterations to

find an optimal solution before stopping criterion. To improve performances, RANSAC-

based methods [7] focus on either a better hypothesis from random samples or higher

quality of the samples satisfying the estimated model. In this paper, we tackle a new

sampling procedure which utilizes geometrical constraints to qualify a MSS. The MSS

consisting of good samples is expected to generate better hypotheses, and as result, the

better-estimated models are achievable. We examine the proposed method with fitting

a sphere.

In the proposed robust estimator, a MSS is a stack consisting of samples which

ensure two criteria: (1) The selected samples must ensure being consistent with the

estimated model via a roughly inlier ratio evaluation; (2) The samples satisfy geometrical

constraints of the interested objects (e.g., sphere constraints). The proposed constraints

come from the explicit geometrical properties of the interested shapes. The good samples

of the current stack are highly expected to generate a consensus set which quickly reaches

to the maximal inlier ratio. Consequently, the number of iterations could be adaptively

updated (as the termination manner of the adaptive RANSAC [8]). In GCSAC, we utilize

the maximum log-likelihood of MLESAC algorithm to evaluate the estimated model.

Finally, the effectiveness of the proposed method is confirmed by fitting results of a

spherical object. The evaluations compare the performances of the proposed method and

common RANSACs as original RANSAC, PROSAC, MLESAC, MSAC [4], LO-SAC,

6

Tạp chí Khoa học và Kỹ thuật - Học viện KTQS - Số 190 (04-2018)

NAPSAC [9]. The implementations of the proposed method and evaluation datasets are

made publicly available.

2. Related work

For a general introduction and performances of RANSAC family, readers can refer

to good surveys in [10], [7]. In the context of this research, we briefly survey related

works which are categorized into two topics. First, efficient schemes on the selection of

minimal subset of samples for RANSAC-based robust estimators; and second, techniques

for estimating a primitive shape, that focus into the fitting a spherical.

For the first topic, because the original RANSAC is very general with a straightfor-

ward implementation, it always requires considerable computational time. Many RANSAC

variants have been proposed with further optimization for a minimal sample set (MSS)

selection. Progressive Sample Consensus or PROSAC [5] orders quality of samples

through a similarity function of two corresponding points in the context of finding good

matching features between a pair of images. In PROSAC algorithm, the most promising

hypotheses are attempted earlier, therefore drawing the samples is implemented in

a more meaningful order. However, PROSAC faces critical issues for defining the

similarity function. LO-RANSAC [6] and its fixed version LO⁺-RANSAC [11] add local

optimization steps within RANSAC to improve accuracy. To speed up the computation,

adaptive RANSAC [8] probes the data via the consensus sets in order to adaptively

determine the number of selected samples. The algorithm is immediately terminated

when a smaller number of iterations has been obtained. With the proposed method, the

good samples are expected to generate the best model as fast as possible. Therefore,

the termination condition of the adaptive RANSAC [8] should be explored. Recently,

USAC [12] introduces a new frame-work for a robust estimator. In the USAC frame-

work, some strategies such as the sample check (Stage 1b) or the model check (Stage

2b), before and after model estimation, respectively, are similar to our ideas in this work.

However, USAC does not really deploy an estimator for primitive shape(s) from a point

cloud. A recent work [13] proposes to use geometric verification within a RANSAC

frame-work. The authors deployed several check procedures such as sample relative

configuration check based on the epipolar geometry. Rather than the "check" procedures,

our strategies anticipate achieving the best model as soon as possible. Therefore, the

number of iterations is significantly reduced thanks to the results of the search for good

sample process. The RANSAC-based algorithm used in the method of Chen et al. [14]

and Aiger et al. [15] for registering of partially overlapping range images and partial

surfaces of a 3D object.

For primitive shape estimation from 3-D point clouds, readers can refer to a survey on

feature-based techniques [16]. Some fitting techniques, for instance, multiscale super-

quadric fitting in [17], Hough transform in [18], are commonly used. Marco et al.

[19], Anas et al. [20] used the 3D Hough Transform to estimate, extract sphere from

point cloud data. However, the robust estimators (e.g., RANSAC family [7]) are always

7

Chuyên san Công nghệ thông tin và Truyền thông - Số 11 (04-2018)

preferred techniques. Original RANSAC [3] demonstrates itself robust performances in

estimating cylinders from range data. The authors in [21] and [1] formulate primitive

shapes (e.g., line, plane, cylinder, sphere, cone) using two to seven parameters such

as a cylinder has seven parameters, a sphere has four parameters, a cone has seven

parameters, etc. Schnabel et al. [1] defines primitive shapes through some samples and

their normal vectors. In this study, geometrical analysis of a sphere in [1] is adopted

for defining criteria of the qualified samples as well as for estimating parameters of the

interested model from a 3-D point cloud.

3. Proposed method

3.1. Overview of the proposed robust estimator - GCSAC

To estimate parameters of a primitive shape, all of RANSAC variations in the RANSAC

family [7] (RANSAC, MLESAC, PROSAC, MSAC, LOSAC, NAPSAC, .etc) imple-

mented some steps as follows: drawing randomly a Minimal Sample Set (MSS)(RANSAC,

MLESAC, MSAC) or semi-random (PROSAC) or using constraints of the sample’s

distribution (NAPSAC); estimating the model; evaluating the model and choosing the

best model. This scheme is repeated K iterations. All of them are shown in the top

panel of Fig. 1.

In this study, abilities of the proposed robust estimator (GCSAC) will be consolidated

with a sphere. An overview of GCSAC algorithms is shown in the button panel of Fig.

1. Following sections will explain the details of GCSAC’s implementations.

The proposed GCSAC constructs a MSS by the random sampling and sampling

using geometrical constraints of each primitive shape estimation, the aim of it is the

generating the consensus of samples to be easy. To do this, a low inlier threshold is pre-

determined. After only (few) random sampling iterations, the candidates of good samples

could be achieved. Once initial MSS is established, its samples will be updated by the

qualified one (or good sample) so that the geometrical constraints of the interested object

is satisfied. The estimated model is evaluated according to Maximum Log-likelihood

criteria as MLESAC [4]. The final step is to determine the termination condition, which

is adopted from the adaptive RANSAC algorithm [8]. Once the higher inlier ratio is

obtained, the criterion termination K for determining the number of sample selection

is updated by:

log(1 − p)

K =

(1)

log(1 − w^m)

where p is the probability to find a model describing the data, m is the minimal number

of samples to estimate a model, w is percentage of inliers in the point cloud. While

p often to set a fixed value (e.g., p = 0.99 as a conservative probability), K therefore

depends on w and m. The algorithm terminates as soon as the number of iterations of

current estimation is less than that has already been performed.

8

Tạp chí Khoa học và Kỹ thuật - Học viện KTQS - Số 190 (04-2018)

Update the

number of

iterations K

adaptively

(Eq. 2)

Random or Semi-

random or using

constraint for

sampling a

Model evaluation

M Update thevia

No

Geometrical

parameters

estimation M

Estimated

model

Terminate

?

A point

cloud

(inlier ratio, Negative

Log Likelihood, cost

function); best model

Yes

minimal subset

RANSAC Iteration

A point cloud (U_n)

Draw m random points P

Update U^*by searching

samples, explained in Sec.3.3

n

Reset U^*= Ø

n

Estimate model M_ifrom P

Compute inlier ratio w_i

Estimate model M_ifrom P

Compute Negative Log-

No

likelihood -L

w_i≥ w_t

Yes

No

-L < L_t

Adding selected points to U^*

n

Yes

Update model M_iand

re-compute K

Meet

termination

criteria ?

Yes

No

Estimated parameters

Fig. 1. Top panel: Over view of RANSAC-based algorithm. Bottom panel: A diagram of the GCSAC’s

implementations.

Details of the GCSAC’s implementation are given in Fig. 1. Obviously, the criteria

which define the good samples are the most important. Based on the idea of adaptive

RANSAC [8] to probe initial samples, GCSAC starts from roughly select of initial good

samples. At each iteration, we assume that the worst case of inlier ratio w_t= 0.1(10%)

is determined, to initialize the stack U_n^∗, where U_n^∗is used to store m − 1 kept points

and its inlier ratio w_i. A consensus set, therefore containing more than 10% of the

data is easily found. A model is estimated from m random samples. As estimating a

sphere is m = 2 [1]. After that, U_n^∗is reset. m samples and the inlier ratio w_iof the

estimated model is stored into U_n^∗if w_iis equal to or greater than w_t. And then, the

MSS utilizes m − 1 kept good samples. The remaining m^thsample will be replaced

9

Chuyên san Công nghệ thông tin và Truyền thông - Số 11 (04-2018)

p₂

n₂

I_sp

pa

n₂

pa

n₂

n₁

pb

n₁

pb

p₁

p₂

p₁

Estimated

sphere

pa

n₁

I_sp

n₂

p₁

p₂

pb

p₂

Fig. 2. Estimating parameters of a sphere from 3-D points. Red points are inlier points. In this figure,

p₁, p₂is two selected samples for estimating a sphere (two gray points), they are outlier points.

Therefore, the estimated sphere is wrong of centroid and radius (see green sphere (d)). The sub-figures

are illustrated in different view-points to clearly observe normal vectors for the geometrical analysis.

by a better one which best satisfies the geometrical constraints of the interested shape.

The good samples which satisfy the geometrical principles of a primitive shape are

explained in Section 3-B. If none of the iterations find out that satisfies w_i≥ w_t, the

estimation algorithm degrades to the original MLESAC. The inlier ratio of the iteration

depends on the threshold T, which chooses an optimal T value is out of the scope of

this research.

3.2. Geometrical analyses and constraints for qualifying good samples

The geometrical model of a spherical object can be presented by four geometrical

parameters [1]. In following sections, the principles of 3-D sphere are explained. Based

on this geometrical analysis, the related constraints are given to select good samples.

3.2.1. Geometrical analysis for a spherical object: A sphere is determined by the

following parameters: a centroid point which is denoted as I_sp(x₀, y₀, z₀); its radius R_sp.

To estimate sphere’s parameters, Schnabel et al. [1] propose to use two points (p₁, p₂)

with their corresponding normal vectors (n₁, n₂) (see Fig. 2(a)). The centroid I_sp(a pink

point Fig. 2(c)) is a middle point of the shortest line (a green line of Fig. 2(b)) which

segments two lines given by (p₁, n₁) and (p₂, n₂). Identifying two lines pa = p₁+t∗n₁

and pb = p₂+ t ∗ n₂are shown in Fig. 2(b). t is the parameter of two lines pa, pb

formulations. The radius R_spis determined by averaging the distance of I_spto p₁and

I_spto p₂. The estimated sphere is shown in Fig. 2(d).

The proposed geometrical constraints for fitting spherical objects: As above

10

Tạp chí Khoa học và Kỹ thuật - Học viện KTQS - Số 190 (04-2018)

denoted, a sphere is estimated from two points (p₁, p₂) and their normal vectors (n₁, n₂).

In GCSAC, once stack U^∗consisting of initial good samples is specified, we store p₁

and search p₂in U_nand ⁿdifference p₁(p₂∈ {U_n\ p₁}). We observe that to generate

a sphere, the triangle (p₁I_spp₂) should be an isosceles, as shown in Fig. 2(e). This

observation could be formulated by:

sh_p= arg _{p ∈}m_{Uin_{\p }}{(|| p₁I_sp|| − || p₂I_sp||)}

(2)

2

n

1

The geometrical constraints in Eq. (2) means that if sh_pis close to 0 then the triangle

p₁I_spp₂is nearly isosceles one.

4. Experimental result

4.1. Dataset

The proposed method is warped by C++ programs using a PCL 1.7 library on a PC

with Core i5 processor and 8G RAM. The program runs sequentially as a single thread.

We have evaluated performances of GCSAC on synthesized datasets of the cylinder,

sphere and cone. Each dataset consists of six different subsets. Characteristics of each

subset are described in Table 1. Major differences could be σ of the normal distribution

for generating outlier/inlier data; or the spatial distribution of inliers.

For the sphere dataset (’first sphere’), they are denoted from dC₁to dC₆. In each

subset dC_i, inlier ratio is increased by a step of 5% from 15 to 80 %. Therefore, there are

fourteen point clouds. They are denoted dS₁to dS₁₄. They have the maximal distance

to true sphere 0.025 (or 2.5cm). Outliers are generated randomly in the limitation as

Tab. 1. A point cloud dS_iconsists of 3000 points. These point clouds are generated

from the curved surface of a true sphere: x²+ y²+ z²= 1. We also generate random

points outside the surface of the sphere as outliers.

Moreover, we also evaluated on a real datasets. This is the dataset of two balls in

four scenes, each scene has been included 500 frames and each frame has a ball on the

table. It named ’second sphere’. The setup of our experiment implemented a similar as

[22] and is illustrated in Fig. 3.

To separate the data of a ball on the table, we have to implement some steps as below.

First is the table plane detection that used the method in [23]. After that, the original

coordinate is rotated and translated that the y-axis is parallel with the normal vector of

the table plane as Fig. 3. The point cloud data of balls is separated with the point cloud

data of the table plane. It is illustrated in Fig. 5.

4.2. Evaluation Measurements

Let notate a ground-truth of model M_t(x_t, y_t, z_t, r_t) and the estimated one

M_e(x_e, y_e, z_e, r_e) where (x_t, y_t, z_t), (x_e, y_e, z_e) are the coordinates of the center points,

11

Chuyên san Công nghệ thông tin và Truyền thông - Số 11 (04-2018)

Fig. 3. Illustrating of our setup to collect the dataset

Set2: center(0,0,0)

Set1: center(0,0,0)

Set3: center(0,0,0)

Occluded object

A haft of object

Fig. 4. Point clouds of dC₁, dC₂, dC₃of the ’second sphere’ dataset (the synthesized data) in case of

50% inlier ratio. The red points are inliers, whereas blue points are outliers.

Table plane

detection and

separating a ball

Point cloud data

on the table

of a ball

Point cloud data of a scene

Fig. 5. Illustrating the separating the point cloud data of a ball in the scene.

r_t, r_eare the radius. To evaluate the performance of the proposed method, we use

following measurements:

- Let denote the relative error E_wof the estimated inlier ratio. The smaller E_wis,

12

Tạp chí Khoa học và Kỹ thuật - Học viện KTQS - Số 190 (04-2018)

Table 1. The characteristics of the generated sphere dataset (synthesized dataset)

Characteristics of the generalized data

Dataset

Spatial distribution

of inliers

Spread of

outliers

Radius

dC1, dC4

dC2, dC5

dC3, dC6

1

Around of a sphere

one half of a sphere [-3, 3], [-4, 4]

[-3, 3], [-4, 4]

the better the algorithm is.

|w − w_gt|

E_w=

× 100

(3)

w_gt

where w_gtis the defined inlier ratio of ground-truth; w is the inlier ratio of the

estimated model.

#inliers

#number of samples

w =

(4)

- The total distance errors S_d[24] is calculated by summation of distances from any

point p_jto the estimated model M_e. S_dis defined by:

N

X

S_d=

d(p_j, M_e)

(5)

j=1

- The processing time t_pis measured in milliseconds (ms). The smaller t_pis the

faster the algorithm is.

- The relative error of the estimated center (only for synthesized datasets) E_dis

Euclidean distance of the estimated center E_eand the truth one E_t. It is defined

by:

E_d= |E_e− E_t|

(6)

- The relative error of the estimated radius E_ris different of the estimated radius r_e

and the truth one r_t. It is defined by:

|r_e− r_t|

E_r=

× 100%

(7)

r_t

The proposed method (GCSAC) is compared with six common ones in RANSAC family.

They are original RANSAC, PROSAC, MLESAC, MSAC, NAPSAC, LO-RANSAC. For

setting the parameters, we fixed thresholds of the estimators with T = 0.05 (or 5cm),

w_t= 0.1, s_r= 3 (cm). T is a distance threshold to set a data point to be inlier or outlier.

s_ris the radius of a sphere when using NAPSAC algorithm. For the fair evaluations, T

is set equally for all seven fitting methods.

13

Chuyên san Công nghệ thông tin và Truyền thông - Số 11 (04-2018)

4.3. The evaluation results

The performances of each method of the synthesized datasets are reported in Tab. 2.

For whole three datasets, GCSAC obtains the highest accuracy and lowest computational

time. More generally, even using same criteria as MLESAC, the proposed GCSAC

obtains better estimated model as shown by E_wmeasurements. The experimental results

also confirmed the proposed constraints are working well with different primitive shapes.

Although E_wof the sphere dataset is high (E_w= 19.44%), this result is still better than

the result of the compared methods. Among the compared RANSACs, it is interesting

that original RANSAC generally give stable results for estimating a sphere. However,

original RANSAC requires a high computational time. The proposed GSSAC estimates

the models slightly better than the original RANSAC.

RANSAC

PROSAC

MLESAC

MSAC

LOSAC

NAPSAC

GCSAC

Fig. 6. Illustrating the fitting sphere of GCSAC and some RANSAC variations on the synthesized

datasets, which have 15% inlier ratio. Red points are inlier points, blue points are outlier points. The

estimated sphere is a green sphere.

Table 2. The average evaluation results of synthesized datasets. The synthesized datasets were repeated

50 times for statistically representative results.

Dataset/

Method

Measure RANSAC PROSAC MLESAC MSAC

LOSAC NAPSAC GCSAC

23.63 57.76 19.44

E_w(%)

S_d

t_p(ms)

E_d(cm)

E_r(%)

23.01

31.53

85.65

33.43

3801.95 3803.62 3774.77 3804.27 3558.06 3904.22 3452.88

’first

sphere’

10.68

0.05

2.92

23.45 1728.21

9.46

0.08

5.15

31.57

0.21

2.96

0.97

63.60

6.48

0.05

2.61

0.07

4.12

1.71

203.60

17.52

Table 3 also shown the fitting results of GCSAC method are more accurate than

RANSAC variations. The results on the ’second sphere’ are high on all of the methods

14

Tạp chí Khoa học và Kỹ thuật - Học viện KTQS - Số 190 (04-2018)

Table 3. The average evaluation results on the ’second sphere’ datasets. The real datasets were

repeated 20 times for statistically representative results.

Dataset/

Method

Measure

RANSAC PROSAC MLESAC MSAC

LOSAC NAPSAC GCSAC

w(%)

S_d

t_p(ms)

E_r(%)

99.77

29.60

3.44

99.98

26.62

3.43

99.83

29.38

4.17

99.80

29.37

2.97

99.78

28.77

7.82

98.20

35.55

4.11

100.00

11.31

2.93

’second

sphere’

30.56

26.55

30.36

30.38

31.05

33.72

14.08

Fig. 7. Results of ball and cone fittings. The point cloud data of a ball is red points; the estimated

spherical is marked as green points.

such as the result of GCSAC when using the w measure is 100%, it is illustrated in

Fig. 7(a). Due to the ball data has a small noise ratio and the threshold T to determine

inlier points is large (0.05(5cm)). While the radius of a ball is 5cm to 7cm. All of the

results shown, the performance of GCSAC is better than the RANSAC variations when

implements estimating primitive shapes on the point cloud data, that has low inlier ratio

(less than 50%). They were also shown, can use to the GCSAC algorithm for detecting,

finding spherical objects in the real scenario. As a visually impaired person come to a

sharing room or a kitchen to find a ball on the floor.

5. Conclusions

In this paper, we proposed GCSAC that is a new RANSAC-based robust estimator

for fitting the primitive shapes from point clouds. The key idea of GCSAC is the

combination of ensuring consistency with the estimated model via a roughly inlier ratio

evaluation and geometrical constraints of the interested shapes that help to select good

samples for estimating a model. Our proposed method is examined with common shapes

(e.g., a sphere). The experimental results confirmed on the synthesized, real datasets

that it works well even the point clouds with low inlier ratio. The results of the GCSAC

algorithm compared to the RANSAC variations in the RANSAC family. In the future, we

15

Chuyên san Công nghệ thông tin và Truyền thông - Số 11 (04-2018)

continue to validate GCSAC on other geometrical structures and evaluate the proposed

method with the real scenario of detecting multiple objects.

Acknowledgment

This research is funded by Vietnam National Foundation for Science and Technology

Development (NAFOSTED) under grant number 102.01-2017.315

References

[1] R. Schnabel, R. Wahl, and R. Klein. Efficient ransac for point-cloud shape detection. Computer Graphics

Forum, 26(2):214–226, 2007.

[2] B. Dorit, J.E. Kai Lingemann, and N. Andreas. Real-Time Table Plane Detection Using Accelerometer

Information And Organized Point Cloud Data From Kinect Sensor. Journal of Computer Science and

Cybernetics, pages pp, 243–258, 2016.

[3] M. A. Fischler and R.C. Bolles. Random sample consensus: A paradigm for model fitting with applications

to image analysisand automated cartography. Communications of the ACM, 24(6):pp, 381–395, 1981.

[4] Philip H. S. Torr and A. Zisserman. Mlesac: A new robust estimator with application to estimating image

geometry. Computer Vision and Image Understanding, 78(1):pp, 138–156, 2000.

[5] O. Chum and J. Matas. Matching with prosac progressive sample consensus. In Procedings of the IEEE

Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), pages pp, 220–226,

2005.

[6] O. Chum, J. Matas, and J. Kittler. Locally optimized ransac. In DAGM-Symposium, volume 2781 of Lecture

Notes in Computer Science, pages pp, 236–243. Springer, 2003.

[7] S. Choi, T. Kim, and W. Yu. Performance evaluation of ransac family. In Procedings of the British Machine

Vision Conference 2009, pages pp, 1–12. British Machine Vision Association, 2009.

[8] R.I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press,

ISBN: 0521540518, second edition, 2004.

[9] D.R. Myatt, P.H.S. Torr, S.J. Nasuto, J.M Bishop, and R. Craddock. Napsac: high noise, high dimensional

robust estimation. In Procedings of the British Machine Vision Conference (BMVC’02), pages pp, 458–467,

2002.

[10] R. Raguram, JM. Frahm, and M. Pollefeys. A comparative analysis of ransac techniques leading to adaptive real-

time random sample consensus. In Procedings of the European Conference on Computer Vision. (ECCV’08),

pages pp, 500–513, 2008.

[11] K. Lebeda, J. Matas, and O. Chum. Fixing the locally optimized ransac. In Proceedings of the British Machine

Vision Conference 2012., pages pp, 3–7, 2012.

[12] R. Raguram, O. Chum, M. Pollefeys, J. Matas, and J. M. Frahm. Usac: A universal framework for random

sample consensus. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):pp, 2022–2038,

Aug 2013.

[13] M. Kohei, U. Yusuke, S. Shigeyuki, and S. Shinichi. Geometric verification using semi-2d constraints for 3d

object retrieval. In Proceedings of the International Conference on Pattern Recognition (ICPR) 2012., pages

pp, 2339–2344, 2016.

[14] C.S. Chen, Y.P. Hung, and J.B. Cheng. RANSAC-based DARCES: a new approach to fast automatic registration

of partially overlapping range images. IEEE Transactions on Pattern Analysis and Machine Intelligence,

21(11):pp, 1229 –1234, 1999.

[15] Aiger D., N. J. Mitra, and D. Cohen-Or. 4-points congruent sets for robust surface registration. ACM

Transactions on Graphics, 27(3), 2008.

[16] K. Alhamzi and M Elmogy. 3d object recognition based on image features : A survey. International Journal

of Computer and Information Technology (ISSN: 2279 – 0764), 03(03):pp, 651–660, 2014.

[17] K. Duncan, S. Sarkar, R. Alqasemi, and R. Dubey. Multiscale superquadric fitting for efficient shape and

pose recovery of unknown objects. In Procedings of the International Conference on Robotics and Automation

(ICRA’2013), 2013.

[18] G. Osselman, B. Gorte, G. Sithole, and T. Rabbani. Recognising structure in laser scanner point clouds. In

International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, pages pp, 33–38,

2004.

[19] C. Marco, V. Roberto, and C. Rita. 3d hough transform for sphere recognition on point clouds. Machine Vision

and Applications, pages pp, 1877–1891, 2014.

16

Tạp chí Khoa học và Kỹ thuật - Học viện KTQS - Số 190 (04-2018)

[20] A. Anas, N. Mark, and C. John. Sphere detection in kinect point clouds via the 3d hough transform. In

International Conference on Computer Analysis of Images and Patterns, 2013.

[21] S. Garcia. Fitting primitive shapes to point clouds for robotic grasping. Master Thesis in Computer Science

(30 ECTS credits) at the School of Electrical Engineering Royal Institute of Technology, 2009.

[22] Le V.H., Vu H., , Nguyen T.T., Le T.L., Tran T.H., Da T.C., and Nguyen H.Q. Geometry-based 3-d object fitting

and localization in grasping aid for visually impaired. In The Sixth International Conference on Communications

and Electronics. IEEE-ICCE, 2016.

[23] Le V.H., M. Vlaminck, Vu H., , Nguyen T.T., Le T.L., Tran T.H., Luong Q.H., P. Veelaert, and P. Wilfried.

Real-Time Table Plane Detection Using Accelerometer Information And Organized Point Cloud Data From

Kinect Sensor. Journal of Computer Science and Cybernetics, pages pp, 243–258, 2016.

[24] P. Faber and R.B. Fisher. A Buyer’s Guide to Euclidean Elliptical Cylindrical and Conical Surface Fitting. In

Procedings of the British Machine Vision Conference 2001, number 1, pages pp, 54.1–54.10, 2001.

Manuscript received 13-07-2017; accepted 21-03-2018.

ꢀ

Le Van Hung received his M.Sc. at Faculty Information Technology- Hanoi National Univer-

sity of Education (2013). He is now an PhD at International Research Institute MICA HUST-

CNRS/UMI - 2954 - INP Grenoble. His research interests include Computer vision, RANSAC

and RANSAC variation and 3D object detection, recognition.

Vu Hai received B.E. degree in Electronic and Telecommunications in 1999 and M.E. in

Information Processing and Communication in 2002, both from Hanoi University of Science

and Technology (HUST). He received Ph.D. in Computer Science from Osaka University, 2009.

He has been a lecturer at MICA International Research Institute since 2012. He is interested

in computer vision techniques for medical imaging, HCI, robotics.

Nguyen Thi Thuy received her BSc. degree in Math & Informatics in 1994, MSc. in Infor-

mation Technology from HUST in 2002, and PhD. in Computer science from Graz University

of Technology, Austria in 2009. She has been a lecturer at Faculty of Information Technology,

Vietnam National University of Agriculture since 1998, head of department of Computer

Science since 2011. Her research interest includes object recognition, visual learning, video

understanding, statistical methods for computer vision and machine learning.

Le Thi Lan graduated in Information Technology HUST, Vietnam. She obtained MS degree in

Signal Processing and Communication from HUST, Vietnam. In 2009, she received her Ph.D.

degree at INRIA Sophia Antipolis, France in video retrieval. She is currently lecturer/researcher

at Computer Vision Department, HUST, Vietnam. Her research interests include computer

vision, content-based indexing and retrieval, video understanding and human-robot interaction.

Tran Thi Thanh Hai graduated in Information Technology from Hanoi University of Science

and Technology in 2001. She received ME. then Ph.D In Imagery Vision Robotic from INPG in

2002 and 2006 respectively. Since 2009, she is lecturer/researcher at Computer Vision group,

International Institute MICA, Hanoi University of Science and Technology. Her main research

interests are visual object recognition, video understanding, human-robot interaction and text

detection for applications in Computer Vision.

17