Engineering Mechanical

Int J Adv Manuf Technol (****) **: *** ***

DOI **.1007/s00170-003-1695-x

O R I GI N A L A R T IC L E

Y. Lee S. Park Y. Jun W. C. Choi

A robust approach to edge detection of scanned point data

Received: 21 October 2002 / Accepted: 24 February 2003 / Published online: 16 December 2003

Springer-Verlag London Limited 2003

Abstract In reverse engineering, segmentation is used to Keywords Reverse engineering Edge detection

divide a point data set into subsequent regions according Cost criteria Region-growing

to its shape. It is vital for interpretation of discrete

scanned data since surface reconstruction can be

accomplished one-by-one on a given region. Edge

detection is crucial to the segmentation process. The 1 Introduction

level of edge detection depends on the complexity of the

part, and it determines the eventual success or failure of Many products, from household appliances to auto-

the reverse engineering (RE) process. This paper pro- mobiles, contain separate and distinct regions. In reverse

poses a novel approach to the edge detection of 3D engineering, segmentation is a step to divide a point data

points based on a region growing technique. The pro- set into subsequent regions according to its shape. It is

posed algorithm consists of two parts. First, polygonal vital for interpretation of discrete scanned data since

meshes are generated to the scanned point data using the surface reconstruction can be accomplished one-by-one

Delaunay triangulation algorithm. Second, the normal on a given region. Edge detection is crucial for the seg-

vector and the area of a polygonal mesh are checked to mentation process.

nd boundary meshes using cost criteria (angle criterion Edges can be classi ed into two basic types: a sharp

and area criterion) based upon a region growing tech- edge and a smooth edge. The former corresponds to

nique. The region growing technique aggregates meshes points or meshes where a normal vector changes its

into a region until the area of aggregated meshes reaches direction abruptly, while the latter corresponds to points

an area threshold from a series of seed meshes. The where a normal vector direction changes gradually, as

proposed edge detection method is found to be e ective shown in Fig. 1.

when compared with other methods. Approaches to edge detection fall into two main

categories: edge-based [1, 2, 3, 4, 5, 6, 7, 8] and face-

based approaches [9, 10]. In the edge-based method,

Y. Lee discontinuous edge points are rst detected from the raw

Department of Mechanical Engineering,

scanned points and then used to guide the segmentation

Korea University, 1, 5-ka Anam-dong,

process. Sarkar and Meng [3] used traditional image

Sungbuk-ku, Seoul 136-701, Korea

processing techniques for edge detection. Canny [1]

S. Park proposed an edge detector by computing the derivative

Systems Technology Division,

in the estimated gradient direction at each datum. The

Korea Institute of Science and Technology (KIST),

surface edges were detected by a zero-crossing edge

PO Box 131, Cheongryang, Seoul, Korea

E-mail: *******@****.**.** detection method [4] that is based on the Laplacian

Tel.: +822-***-****

operator. However, this method may not be e ective

Fax: +822-***-****

with noisy data. A principal curvature method [8] was

Y. Jun widely used in edge detection. This method assumes that

Department of Mechanical Engineering,

a triangle mesh approximates a smooth surface with the

Sejong University, 98 Gunja-dong,

vertices as sampled surface points. It yields a good result

Gwangjin-gu, Seoul 143-747, Korea

for regular meshes, but it may not be e ective in large,

W. C. Choi

rounded meshes or irregular meshes. In this research, the

Department of Mechanical Engineering,

comparison between the principal curvature method and

Korea University, 1, 5-ka Anam-dong,

the proposed method is given in Sect. 4.

Sungbuk-ku, Seoul 136-701, Korea

264

Fig. 2 Region growing

Fig. 1 Two types of edges: a Sharp edge. b Smooth edge

The face-based method divides point data into con- This paper is composed as follows. Section 2 sum-

nected regions of points according to geometric prop- marizes overall research methodology on the poly-

erties such as normals, curvatures, etc. Typically, the gon-based RE procedure. In Sect. 3, detailed steps of

regions are enlarged around seed points. Besl and Jain the proposed edge-detection algorithm are described.

[9] used a polynomial-based region growing approach. Examples are given and discussed in Sect. 4. Finally,

The approach is suitable for surfaces with sharp edges Sect. 5 presents conclusions and some suggestions for

and curvature discontinuity regions, but it is not good future research.

for free-form surfaces. In general, face-based approaches

are more robust to noise than edge-based approaches.

However, the determination of an appropriate criterion

2 Polygon-based RE techniques

is not straightforward since the edge detection resulting

from region growing could be sensitive to the chosen

In this section, the overall procedure of the polygon-

threshold value.

based RE is brie y reviewed. As shown in Fig. 3, the

In order to complement the two methods, a hybrid

rst step is to obtain geometric information about a part

approach adopts a combination of face- and edge-based

shape. Over the years, many 3D scanners have been

considerations. Park and Jun [11] proposed segmenta-

developed to scan the surfaces of a target part, pro-

tion for primitive analytic surfaces based upon the hy-

ducing a point cloud, which as a whole de ne the surface

brid method.

shapes. In general, an initially scanned point set is very

The edge detection method proposed in this paper

large and normally contains many redundant points.

uses the hybrid approach described by Park and Jun

For RE e ciency, the redundant points need to be re-

[12]. The region growing technique and boundary-mesh

moved by sampling. The second step of the polygon-

detection are typical characteristics of the face-based

based RE process is a triangulation process. A Delaunay

and edge-based approach, respectively. In the rst step

of edge detection, in order to determine the boundaries

of subsequent regions, the system generates polygonal

meshes from the scanned input points and computes a

cost value for each edge from the generated meshes as a

reference value. The cost value of each polygonal mesh is

calculated by the area and the normal vector. Obviously,

it makes sense to use a high cost value to detect

boundary meshes. The basic concept behind detecting

them is to select all the meshes whose cost value is higher

than a certain threshold (cost criterion). The next step in

edge detection is the region growing process. A polyg-

onal mesh is aggregated into a sub-region until the area

of the sub-region reaches the user-de ned area thresh-

old, as shown in Fig. 2.

In this paper, proper cost values for prismatic parts

and free-form surfaces are proposed. Furthermore, the

e ciency of the proposed method is compared with that

of the principal curvature method. Finally, the rela-

tionship between the threshold value for the cost crite-

rion for edge detection and the polygon mesh size is

analysed. Fig. 3 Flowchart of polygon-based RE

265

triangulation [13] method is applied to construct

polygonal meshes from the scanned point set. The basic

concept of the triangulation algorithm is to ll the

convex hull of the scanned points with triangles, such

that: 1. the vertices of the triangles are those of the

scanned points, and 2. the circumscribing circle of any

triangle does not contain any other points inside the

circle. The point data set may contain several separate

and distinct regions. In order to make the surface

reconstruction process more e cient, the data set needs

to be divided into regions. Hence, the next step is to

detect the boundary meshes from the geometric infor-

mation of the generated polygonal meshes, because the Fig. 4 Disjointed edge curves in the corner

detected boundary meshes can be used as a bridge be-

tween the scanned point data and the corresponding

surface. Then, region growing is performed on the me-

shes by comparing the normal of the seed mesh and the

normal of the last mesh. A detailed polygon-based edge-

detection algorithm is discussed in depth in Sect. 3.

Finally, the segmentation process with the result of the

edge detection divides the point set into several con-

stituent regions. Each segmented mesh is reconstructed

into an appropriate surface according to geometric

algorithms.

3 Edge-detection algorithm

The basic idea of the proposed mesh detection is based

on the computation of an angle di erence between two

normal vectors of two neighbouring meshes. All the

meshes where the angle change in the normal vector is

Fig. 5 Boundary polygonal meshes (shaded)

beyond a certain tolerance are regarded as boundary

meshes. In a traditional point-oriented approach, dis-

The cost value of each polygonal mesh needs to be

crete boundary points are detected and attached to each

computed to determine the boundaries of distinctive

other to form a continuous loop. However, in practise,

regions. In practise, if the scanned model contains only

they are unlikely to be closed at the corner where several

several prismatic shapes rather than free-formed shapes,

edge curves meet as shown in Fig. 4, so that edge points

the boundary-mesh detection can be accomplished by

cannot be used for the boundary perimeter of regions.

just comparing the normal vectors of two neighbouring

However, in this approach, polygonal meshes are used

polygonal meshes, as shown in Fig. 6.

to connect disjointed boundary curves in order to close

From the given set of polygonal meshes, the angle

the boundaries at the corner. The boundary meshes are

di erence between the normal vectors of two consecu-

de ned, as all the meshes that contain edge points. All of

tive meshes is calculated. Then, by examining the set of

the boundary meshes are detected and then marked as

di erence angles, mesh boundaries can be readily sear-

the boundaries as shown in Fig. 5.

ched by comparison with a user-de ned angle threshold.

In order to perform boundary-mesh detection, a cost

However, the main limitation of the above method is

value needs to be de ned for the polygon model. The

that it can hardly detect smooth edges in rounded areas

cost value is de ned as a certain tolerance that deter-

because the normal vectors of the adjacent meshes

mines whether or not the meshes are boundary meshes.

Fig. 6 Prismatic part edge

detection. a Model with

polygonal mesh. b Normal

computation. c Mesh

boundaries based upon normals

266

Fig. 7 Rounded boundary meshes

change gradually (Fig. 7). It is assumed that h is the

angle di erence between two consecutive normal vectors

in the rounded area. If there are too many polygonal

meshes, h can be less than the angle threshold in the

rounded area. Hence, the rounded boundary is unlikely

to be detected because the angle di erence between

normal vectors of two neighbouring meshes may be very

small. In order to overcome this problem, the area of

polygonal meshes is also considered. Polygonal meshes

are aggregated until the sum reaches an area threshold

which is de ned by the user. Therefore, the angle dif-

ference is computed from the normal vectors of each

seed mesh and last mesh, which is then merged into an

aggregation. The seed meshes with region aggregation

are iteratively selected from the whole meshes until no

more meshes join. Then a new aggregation starts using

the next available seed mesh.

The cost criteria is de ned as

hc Angle difference between the normal vectors of the

seed mesh and the last mesh in an aggregation.

Area of aggregated meshes so far. This value is the

Sc

relative value of the average area of the whole

meshes (Savg).

Two typical characteristics of the angle and area

thresholds are possible as follows (Fig. 8). One case is if

the area (S2) of the mesh neighbouring a seed mesh is

larger than Savg, then only the angle threshold is con-

sidered, as shown in Fig. 8a. The di erence angle h is

computed from two normals, N1 and N2. Then, the angle

di erence is compared with the angle threshold (hc)

to determine whether or not the mesh is on the boundary.

The other case occurs if S2 is smaller than Savg, the

region growing process starts from a seed mesh, as in

step 1, shown in Fig. 8b. The next mesh is searched

for by comparing the normal vectors of the current

mesh and its adjacent meshes. Then the mesh to be

aggregated is a neighbouring mesh which has a max-

Fig. 8 Two cases of edge detection. a Case 1: angle threshold.

imum angle di erence. The mesh is aggregated into a

b Case 2: angle and area threshold

region until the sum of the mesh areas exceeds a user-

de ned area threshold (Sc). When the cumulative area

of meshes is larger than Sc, the angle di erence be- di erence between these two normal vectors exceeds a

tween the normal vectors of the seed mesh and the user-de ned angle threshold (hc), all the aggregated

current mesh is compared (step 2 in Fig. 8b). If the meshes become boundary meshes. Then, the line of

267

the boundary meshes is regarded as the boundary

edge. The process continues until no more mesh is

available. The algorithm of edge detection is shown in

Fig. 9.

4 Examples and analysis

The proposed edge-detection algorithm was imple-

mented using Visual C++ 6.0 and OpenGL. To vali-

date the edge detection methodology, three parts were

selected as shown in Table 1.

EzScan [14], a scanning device by Solutionix, Inc.,

was used to scan the part. The scanned point sets are

shown in Figs. 10a, 11a, 12a, and 13a. Fig. 10a shows

the point clouds of the transmission model. The model is

250 mm wide, 282 mm high and 288 mm deep. Fig. 10b

shows the detected meshes for area threshold

(Sc)=0.5 average area (Savg) and the angle threshold

(hc)=20, while Sc=2 Savg, hc=20 and Sc=2 Savg,

hc=45 in Figs. 10c and 10d, respectively.

Figs. 10b and 10c show the e ect of the area

threshold. It can be seen that the rounded boundary

meshes are detected and that the area threshold has in-

creased. The e ect of the angle di erence threshold is

shown in Figs. 10c and 10d. When the angle threshold

increases, the number of boundary meshes on the

rounded area is reduced.

In this section, a comparison between the proposed

edge detection method and the principal curvature

method [8] is performed. In the principal curvature

method, if the sampling density of the polygon model is

very high, the underlying surface can be approximated

accurately by meshes of circular arcs. The tolerance of

the principal curvature method does not represent a

curvature value but a ratio of total edge points. It ranges

from zero to one. If it is close to one, the number of edge

points is increased. Details of the principal curvature

method can be found in reference [8].

Figures 11a and b show the point clouds and gen-

erated meshes for a mouse, respectively. Figure 11c

shows edge detection results using the principal cur-

vature method. It can be seen that the smooth edges

are not detected well. On the other hand, the edge

detection of the smooth areas yields a good result,

obtained using the proposed method as shown in

Fig. 11d. This example shows that edge detection of the

smooth areas represents better performance for the

proposed edge detection method than for the principal

curvature method.

Table 1 Characteristics of the examples

Transmission Mouse Plate Plate

(Fig. 12) (Fig. 13)

Number of points 155***-***** 521**-*****

Fig. 9 Algorithm of edge detection

Number of faces 306***-***** 102***-*****

Average area (mm) 1.264 0.311 0.116 0.231

268

Fig. 10 Edge detection of

di erent area threshold (Sc) and

angle threshold (hc). a Point

clouds. b Sc=0.5 Savg and

hc=20 . c Sc=2 Savg

and hc=20 . d Sc=2 Savg and

hc=45

Fig. 11 Comparison of two

methods. a Point clouds.

b Triangular mesh. c Principal

curvature (tolerance=0.85).

d Sc=2.5 Savg and hc=10

Figure 12a shows the point clouds of a plate model. proposed method and the principal curvature method.

The size of the model is approximately 86 104 42 mm. They show that the edge detection results are similar to

Figures 12b and c show the detected edges using the each other, since the mesh size is uniform.

269

Fig. 12 Edge detection for a

plate. a Point clouds.

b Principal curvature

(tolerance=0.8). c Sc=2.5 Savg

and hc=10

Fig. 13 Edge detection for a

plate (50% reduction of

Fig. 12). a Point clouds.

b Principal curvature

(tolerance=0.85).

c Sc=2.5 Savg and hc=20

270

the area threshold, but mesh size variation does relate

to the angle threshold.

Table 2 represents proper cost values for prismatic

models and free-form models. These values were deter-

mined empirically through several experiments. The

angle threshold for the transmission model indicates that

a higher value than that of free-form models is desirable.

This means that the number of sharp edges on the

prismatic model is larger than that of free-form models.

Also, the area threshold of the free-form models has a

higher value than that of the prismatic model. Due to a

number of rounding areas, the aggregated mesh area is

large. As a consequence, when comparing edge detection

of the free-form model with that of the prismatic model,

one notes that the area threshold (Sc) is increased and

the angle threshold (hc) is decreased.

Fig. 14 Relationship between the angle threshold and the mesh size 5 Conclusions

of the model

In this paper, a polygon-based edge-detection algo-

rithm for segmentation was proposed. The algorithm

Table 2 Proper cost values of the examples detects part boundaries using angle and area criteria.

Several examples were presented to validate the e -

Prismatic model Free-form model

ciency of the proposed method. Proper cost values for

Transmission Plate Mouse prismatic and free-formed parts are presented. More-

over, the relationship between cost criteria and mesh

hc (degree) 20 10 10

size of the polygon model was analysed. This algorithm

2 Savg 2.5 Savg 2.5 Savg

Sc

is capable of detecting both sharp edges and rounded

edges. The proposed algorithm is superior to the

principal curvature method, especially when mesh size

Figure 13a indicates that the number of points in the

is irregular.

point clouds is reduced by 50% of the original plate

The proposed edge-detection algorithm can be used

model. Due to mesh decimation [15], the mesh size is

not only for segmentation, but also for feature line

irregular and the average mesh size is increased (Ta-

extraction. Further work is needed to analyse the cost

ble 1). The result of the principal curvature method is

criteria for polygon models of noisy data.

poor, as shown in Fig. 13b, but the proposed method

yields a good result as shown in Fig. 13c. This method is

more robust for the mesh size and irregularity. In

References

Fig. 13c, it is apparent that the angle threshold is in-

creased two times as compared to the one in Fig. 12c.

This means that the angle threshold is increased due to 1. Canny J (1986) A computational approach to edge detection.

IEEE Trans Pattern Anal 8(6):679 698

the large mesh size. This example con rms the robust-

2. Ho man R, Jain AK (1987) Segmentation and classi cation of

ness of the method for mesh size and irregularity when range images. IEEE Trans Pattern Anal 9(5):608 620

the proper angle and area thresholds are found. 3. Sarkar B, Meng CH (1991) Smooth-surface approximation and

When the area threshold (Sc=2 Savg) is xed, the reverse engineering. Comput Aided Des 23(9):623 628

4. Chen LC, Lin GCI (1997) A vision-aided reverse engineering

relationship between the variation of the angle thresh-

approach to reconstructing free-from surfaces. Robot Comput

old and the mesh size of the polygon model is shown in Integr Manuf 13(4):323 336

Fig. 14. The reduction ratio means a decrease ratio 5. Milroy MJ, Bradley C, Vickers GW (1997) Segmentation of a

from the original model, as shown in Fig. 14. Thus, as wrap-around model using an active contour. Comput Aided

Des 29(4):299 320

the reduction ratio of the mesh is increased, the num-

6. Yang M, Lee E (1999) Segmentation of measured point data

ber of faces for the original model is reduced and the

using a parametric quadric surface approximation. Comput

mesh size is increased. Due to the large mesh size, the Aided Des 31(7):449 457

di erence on the normal vector is increased. Therefore, 7. Dickinson SJ, Metaxas D, Pentland A (2000) Constrained

the angle threshold is increased. While the reduction recovery of deformable models from range data. In: Proceed-

ings of international workshop visual form, Capri, Italy

ratio of mesh size is increased, the average area (Savg)

8. Girod B, Greiner G, Niemann H (2000) Principles of 3D image

of the total meshes is increased. Therefore, since the analysis and synthesis. Kluwer, Dordrecht, pp 166 180

area threshold is a multiple of Savg, it is not change- 9. Besl PJ, Jain RC (1988) Segmentation through variable-order

able. As a result, variation of mesh size is irrelevant to surface tting. IEEE Trans Pattern Anal 10(2):167 192

271

10. Checchin P, Trassoudaine L, Alizon J (1997) Segmentation of 13. Cignoni P, Montani C, Scopigno R (1998) DeWall: a fast di-

vide and conquer Delaunay triangulation algorithm in Ed.

range images into planar regions. In: Proceedings of interna-

tional conference on recent advances in 3D digital imaging and Comput Aided Des 30(5):333 341

modeling, pp 156 163 14. http://www.solutionix.com/eng/engineering/3dscanners_stan.asp

11. Park S, Jun Y (2000) Face-based reverse engineering approach 15. Schroeder WJ, Zerge JA, Lorensen WE (1992) Decimation of

to primitive analytic surfaces. In: 2000 international CIRP triangle meshes. In: Proceedings of SIGGRAPH 92 computer

design seminar. Haifa, Israel, May 2000, pp 423 428 graphics conference, pp 65 70

12. Park S, Jun Y (2002) Automated segmentation of point data in

a feature-based reverse engineering system. In: Proceedings of

the institution of mechanical engineers, part B, J Eng Manuf

216:445 451

Contact this candidate