## Abstract

Surfaces govern functional behaviours of geometrical products, especially high-precision and high-added-value products. Compared with the mean line-based filters, morphological filters, evolved from the traditional E-system, are relevant to functional performance of surfaces. The conventional implementation of morphological filters based on image-processing does not work for state-of-the-art surfaces, for example, freeform surfaces. A set of novel geometric computation theory is developed by applying the alpha shape to the computation. Divide and conquer optimization is employed to speed up the computational performance of the alpha-shape method and reduce memory usage. To release the dependence of the alpha-shape method on the Delaunay triangulation, a set of definitions and propositions for the search of contact points is presented and mathematically proved based on alpha shape theory, which are applicable to both circular and horizontal flat structuring elements. The developed methods are verified through experimentation.

## 1. Introduction

The surface of a geometrical component is an interface limiting the body of the component and separating it from the surrounding medium. It governs the functional behaviours of the product, whether that be a mechanical, tribological, hydrodynamic, optical, thermal, chemical or biological property, all of which are of tremendous importance to product performance [1,2]. Many emerging products and devices are based on achieving surfaces with special functionalities. Manufactured items such as micro- and nanometre-scale transistors, microelectromechanical systems and nanoelectromechanical systems, microfluidic devices, optics components with freeform geometry and structured surface products are clear evidence of products where the surface plays the functional role [3].

Surfaces and their measurement provide a link between the manufacture of these engineering components and their use [4]. On the one hand, it can help to control the manufacturing process: monitor changes in the surface texture and indicate changes in the manufacturing process such as machine tool vibration and tool wear [5,6]. On the other hand, it can help with functional prediction: characterize geometrical features that will directly impact on tribology and physical properties of the whole system [7–9], for instance the friction of two contact surfaces and the optical fatigue of one reflecting surface.

The early use of surface measurement was mainly to control the manufacturing process. The surface texture is a fingerprint of the process stages of a manufacturing process. The effects of process and machine tool are always present in the surface textures. The former is called the roughness and the latter the waviness. Also, in addition to roughness and waviness, even longer wavelength can be introduced into the surface geometry by weight deflection or long-term thermal effects [10]. Filtration techniques are the means by which roughness, waviness and form components of the surface texture are extracted from the measured data for further characterization. By separating the surface profile into various bands, it is possible to map the frequency spectrum of each band to the manufacturing process that generated it [11]. Filtration techniques are also widely used in dimensional metrology to suppress the noises in the measured data to achieve a more stable dataset.

The 1950s saw two attempts to separate the waviness from the profile so that the roughness could be characterized. One was graphical, simulating electrical filters in the metre circuit [12]. The raw profile was divided into segments of equal length, and in each segment a mean line was drawn that captured the slope of the profile in that segment. The roughness profile was obtained by considering the deviation from the mean line. Thus, it was designated the mean line system (M-system). The other was mechanically simulating the contact of a converse surface, e.g. a shaft, with the face of the anvil of a micrometre gauge [13]. It appeared as a large circle rolling across over the profile from above and was entitled the envelope system (E-system).

The E-system based the reference line upon an envelope generated by the centre of a rolling circle and shifted to the average height of the profile [14]. The difficulty appeared in building practical instruments as two elements are needed: a spherical skid to approximate the ‘enveloping circle’ and a needle-shaped stylus moving in a diametric hole of the skid to measure the roughness as deviation with respect to the ‘generated envelope’. The advantage of the E-system was claimed to be that it is more physically significant in that many engineering properties of a surface that are determined by its peaks [15]. However, the standing objection was that the choice of the rolling circle radius is as arbitrary as the choice of cut-off in the M-system and no practical instruments using mechanical filtering could be made at that time. The discussion about the reference systems lasted for at least one decade between 1955 and 1966 [16]. Around 1960, with the advent of digital processing techniques, the M-system became pre-eminent and was improved by the 2RC digital filter and phase-corrected digital filter. Later the Gaussian filter, with better performance, was chosen as the standardized filter for separating differing wavelengths.

The Gaussian filter, although a good general filter, is not applicable for all functional aspects of a surface, for example in contact phenomena, where the E-system method is more relevant. The advent of fast practical computers, which can be used in association with measurement instruments, had virtually eliminated the need for any hardware implementation for the E-system [17]. Furthermore, there was growing evidence showing that the E-system method can give better results in functional prediction of surface finish in the analysis of mating surfaces, such as contact, friction, wear, lubrication and failure mechanism [18]. With the M-system, there is little correlation between the standardized surface roughness parameters and functional requirements, while the E-system that depends on geometrical characteristics of the workpiece is more relevant [19]. In this aspect, the logic of the E-system was sounder as against the M-system. Both the M-system and the E-system approaches have their benefits and limitations. Arguing that one is better than the other without any concrete proof from the application area is not convincing [20]. In fact, rather than competing with each other, the M-system and the E-system are complementary to each other, contributing to a better solution to surface evaluation.

In the last two decades, more advanced filtration techniques have emerged as a result of urgent need for the analysis of surfaces with complex geometry and high precision produced by modern manufacturing technologies. The M-system was greatly enriched by incorporating advanced mathematical theories. The enhanced toolbox now contains the robust Gaussian regression filter [21,22], the spline filter [23] and the robust spline filter [24,25]. More recently, a method of Gaussian filtering for freeform surface was developed by solving the diffusion equation which overcomes geometrical distortion in the presence of non-zero Gaussian curvature [26].

Meanwhile, the E-system also experienced significant improvements. By introducing mathematical morphology, morphological filters emerged as the superset of the early envelope filter but offering more tools and capabilities [27]. The basic variation of morphological filters includes the closing filter and the opening filter. They could be combined to achieve superimposed effects, referred to as alternating symmetrical filters. Scale–space techniques further developed morphological filtering techniques, which provide a multi-scale analysis of surface textures [28]. Even though morphological filters are generally accepted and regarded as the complement to mean line-based filters, they are not universally adopted owing to limitations caused by their current implementation and lack of capabilities demanded by the analysis of modern functional surfaces, especially freeform surfaces.

Freeform surfaces are continuous surfaces having no translational and rotational symmetry [29,30]. For freeform surfaces, the description data might be specified by coordinates in two or three dimensions, rather than regular surface height. Responding to all these requirements, novel methods based on the geometric computation have been developed with an aim of supporting morphological filtering on freeform surfaces. Alpha-shape theory provides the theoretical basis of geometrically computing morphological envelopes. Furthermore, the contact points on component surfaces are highly addressed for they play a critical role in determining morphological envelopes. The paper mainly exhibits the geometric computation theory for morphological filtering on freeform surfaces. Applications are also added to further illustrate the capability and feasibility of the proposed computation theory.

## 2. Morphological operations and morphological filters

### (a) Morphology operations on sets

Mathematical morphology is a mathematical discipline established by two French researchers Jorge Matheron and Jean Serra in the 1960s. An overview of their work is given in Serra [31]. The central idea of mathematical morphology is to examine the geometrical structure of an image by probing it with the structuring element. Four basic morphological operations, namely dilation, erosion, opening and closing, form the foundation of mathematical morphology.

Dilation combines two sets using the vector addition of set elements. The dilation of *A* by *B* is defined as
2.1where ⊕ is the vector addition and is the reflection of *B* through the origin of *B*.

Erosion is the morphological dual to dilation. It combines two sets using the vector subtraction of set elements. The erosion of *A* by *B* is
2.2where
2.3and is the complementation of *A*.

Both opening and closing use combinations of dilation and erosion operations in pairs. The opening of *A* by *B* is obtained by applying the erosion followed by the dilation with the common set element B,
2.4

Closing is the morphological dual to opening. The closing of *A* by *B* is given by applying the dilation followed by the erosion:
2.5

### (b) Morphological filters for surface metrology

Morphological filters in surface metrology are based on mathematical morphology. The profile and surface are treated as functions on and , respectively [27]. They are carried out by performing morphological operations on the input profile/surface with circular or horizontal flat structuring elements [32].

As figure 1 illustrates, the dilation of the surface profile with a disc structuring element is the locus of the centre of the disc as it rolls over the profile from the above [28]. Dual to the dilation, the erosion is obtained by rolling the disc over the profile from the below (figure 2). Closing is the combination of two operations, first a dilation followed by an erosion. Opening is morphological dual to closing, given by applying an erosion followed by a dilation. In fact, the closing and opening envelopes are the upper and lower boundary of the discs, respectively. In particular, the E-system is a dilation envelope with a circular structuring element offset by the disc/ball radius.

It is obviously revealed that the closing filter suppresses the valleys on the profile which are smaller than the disc radius in size, meanwhile the peaks remain unchanged. On the contrary, the opening filter suppresses the peaks on the profile which are smaller than the disc radius in size, while it retains the valleys. The combining effects of the closing and opening filter lead to alternating symmetrical filters, by which both peaks and valleys are suppressed.

### (c) Conventional computation method and limitations

The traditional implementation of morphological filters was based on morphological operations in image processing where sampled points are treated as pixels in an image. Figure 3 presents a basic method to compute the dilation operation with the disc structuring element for profile data [33]. The disc ordinates are computed from the disc centre to the two ends with the same sampling interval to the measured profile. These ordinates are placed to overlap the profile ordinates with the disc centre locating at the target profile point. The ordinate where the mapping pair of the profile ordinate and the disc ordinate gives the maximum value in height determines the height of the disc centre. This procedure is repeated for all the profile ordinates to obtain the whole dilation envelope. The erosion envelope can be obtained by first flipping the original profile followed by flipped its dilation envelope. In the case of areal data, the disc is replaced by the ball, on which the ball ordinates are calculated on the hemisphere.

This supporting algorithm, although easy in implementation, has a couple of limitations which restrict the prevalence of morphological filters. They are restricted to ‘planar surfaces’, namely height fields embedded in the Euclidean spaces , and therefore unsuitable for freeform surfaces. Even with planar surfaces data, it is not robust against rotation in space. Another shortcoming lies in the destructive end effects for surfaces in the presence of significant form component, which is notable when the structuring element of a large size is used. As a result, the filtration will be badly distorted in the boundary regions.

A further issue regarding existing methods is their inaccuracy in capturing the contact points of the measured surface with the structuring element. The detection of contact points is dependent on the numerical comparison between the original data and the closing or the opening envelope. This is limited by the accuracy of the algorithm and sensitivity to the round-off errors in the calculation. This situation is even compounded by sampling the structuring element discretely.

Besides the limitations mentioned earlier, morphological filters also suffer from two practical issues raised in the use of the traditional computation method. For areal surface datasets with a large number of measured points, the method is extremely time-consuming. Even using the current available commercial surface analysis software, e.g. the Mountain map (Digital Surf), the performance is far from satisfactory. Also the size of the structuring element is restricted from growing big owing to the fact that the computational time is in exponential proportion to the size of structuring element. For another, image-processing-based methods treat the data as uniformly distributed pixels and unsuited to non-uniform sampled data. This further limits their usage in the field of dimensional metrology where adaptive sampling is allowed.

Except for the image-processing-based approach, there are a few other computation methods, which cannot yet fully overcome the aforementioned deficiencies [17,34,35]. In particular, Scott [34] developed an efficient algorithm for morphological profile filters on the basis of motif combination. However, it is hard to extend this idea to areal data.

## 3. The alpha-shape method for morphological filters

To overcome the limitations of the traditional computation method, a totally different method has been developed, where measured surfaces are no longer treated as greyscale images but three-dimensional point clouds [36]. Geometric computation techniques are adopted to solve the morphological envelope of the point cloud. The alpha shape, a ubiquitous geometric structure in the field of surface reconstruction, is closely related to morphological envelopes and can be used for their computation.

### (a) Alpha-shape theory

The alpha shape was introduced by Edelsbrunner in the 1980s, aiming to describe the specific ‘shape’ of a finite point set with a real parameter controlling the desired level of details [37]. Given a planar point set, a circular disc of radius *α* is rolled around both inside and outside (figure 4); this will generate an object with arcs and points. The boundary of the resulted object is called the alpha hull. If the round faces of the object are straightened by line segments, it generates another geometrical structure, the alpha shape.

In the context of the alpha shape, the disc used in the above example is called the alpha ball. It is formally defined as an open ball of radius *α*. Given a point set , a certain alpha ball *b* is empty if . With this, a *k*-simplex *σ*_{T} is said to be *α*-exposed if there exists an empty alpha ball *b* with *T*=∂*b*∩*X* (|*T*|=*k*+1), where ∂b is the surface of the sphere (for *d*=3) or the circle (for *d*=2) bounding *b*, respectively.

### Definition 3.1

For , the alpha hull of *X*, denoted by *H*_{α}(*X*), is defined as the complement of the union of all empty alpha balls. ∂*S*_{α}(*X*), the boundary of the alpha shape of the point set *X*, consists of all *k*-simplices of *X* for 0≤*k*<*d* which are *α*-exposed
3.1

The computation of the alpha shape is based on the Delaunay triangulation. Given a point set , the Delaunay triangulation is a triangulation *DT*(*X*) such that no point in *X* is inside the circumsphere of any *d*-simplices *σ*_{T} with *T*⊂*X*. The relationship between the Delaunay triangulation and the alpha shape is that the boundary of the alpha shape ∂*S*_{α} is a subset of the Delaunay triangulation of *X*, i.e.
3.2

In order to further extract the simplices of ∂*S*_{α}(*X*) from *DT*(*X*), another concept, the alpha complex *C*_{α}(*X*), was developed. Set *ρ*_{T} the radius of the smallest circumsphere *b*_{T} of *σ*_{T}. For *k*=3, *b*_{T} is the circumsphere; for *k*=2, *b*_{T} is the great circle; and for *k*=1, the two points in *T* are antipodal on *b*_{T}. For a given point set , the alpha complex *C*_{α}(*X*) is the following simplicial sub-complex of *DT*(*X*).

A simplex *σ*_{T}∈*DT*(*X*) (|*T*|=*k*+1, 0≤*k*≤*d*) is in *C*_{α}(*X*), if

—

*ρ*_{T}<*α*and*ρ*_{T}-ball is empty, or—

*σ*_{T}is a face of other simplex in*C*_{α}(*X*).

The relationship between the alpha complex and the alpha shape is that the boundary of the alpha complex makes up the boundary of the alpha shape, i.e. 3.3

### (b) Link between alpha hull and morphological envelopes

The alpha hull resembles the morphological opening and closing envelopes, as the alpha ball acts as a spherical structuring element and the input set as the point set. In fact, a theoretical link between the alpha hull and morphological opening and closing operations was found by Worring & Smedulers [38] that the alpha hull is equivalent to the closing of *X* with a generalized ball of radius −1/*α*. Hence from the duality of the closing and the opening, the alpha hull is the complement of the opening of *X*^{c} (complementation of *X*) with the same ball as the structuring element.

### (c) Morphological envelope computation based on the alpha shape

Based on the established relationship between the alpha shape and morphological envelopes, alpha-shape theory is applied to the computation of morphological envelopes. The computation starts with the Delaunay triangulation of the point set that comprises the measured surface.

The Delaunay triangulation results in a series of *k*-simplices *σ* (*k*=2 for profiles, which are triangles; *k*=3 for surfaces, which are tetrahedrons). These *k*-simplices are categorized into two groups: *k*-simplices *σ*_{p} whose circumsphere radius is larger than the radius of the rolling ball *α*, and *k*-simplices *σ*_{np} whose circumsphere radius is no larger than the radius of the rolling ball *α*.

*σ*_{p} consists of two parts: the (*k*−1)-simplices *σ*_{int} interior to *σ*_{p}, and the (*k*−1)-simplices *σ*_{reg} that bounds its super *k*-simplices *σ*_{p}. We called *σ*_{reg} the regular facets. *σ*_{np} comprises three components: the (*k*−1)-simplices *σ*_{ext} out to *C*_{α}, part of the regular facets *σ*^{′}_{reg} shared by both *σ*_{p} and *σ*_{np}, and the (*k*−1)-simplices *σ*_{sing} that are the other part of ∂*C*_{α}. We call *σ*_{sing} the singular facets. *σ*_{sing} differs from *σ*_{reg} in that it does not bound any super *k*-simplices belonging to *C*_{α}. *σ*_{sing} satisfies two conditions as follows:

— The radius of its smallest circumsphere is smaller than

*α*.— The smallest circumsphere is empty.

An explanatory graph is presented in figure 5. The regular facets *σ*_{reg} and the singular facets *σ*_{sing} form the whole boundary of the alpha complex, i.e. the boundary of the alpha shape, as equation (3.4) presents
3.4

Figure 6 illustrates an example of the alpha-shape facets extracted from the Delaunay triangulation of an experimental profile data. With the boundary alpha-shape facets, the morphological envelope can be solved. For each sample point, there is a one-to-one corresponding point on the envelope. These points form a discrete representation of the morphological envelope. Each boundary facet of the alpha shape determines its counterpart on the alpha hull. Owing to the fact that the target envelope is contained in the alpha hull, the sample points are projected onto the alpha hull along the local gradient vector to obtain the envelope coordinates.

The alpha-shape method calculates morphological filters geometrically and has a number of advantages over traditional methods. Firstly, by viewing the measured surface points as the two-/three-dimensional point set, it breaks the constraints of the traditional method which applies only to planar profiles/surfaces. Secondly, alpha-shape theory enables arbitrary size of disc/ball radius. Moreover, the alpha-shape method more suits non-uniform sampled data. The alpha-shape method depends on the Delaunay triangulation, bringing in an additional merit that the triangulation could be re-used for multiple attempts of various disc radii, saving a great deal of computing time because in practice a multitude of trials may be made for choosing an appropriate disc radius.

### (d) Divide and conquer optimization

The alpha-shape method is more competent than traditional algorithms. However, its bottleneck is that the three-dimensional Delaunay triangulation is costly in both computation time and memory for large areal datasets, and it was reported that the data structure of the Delaunay triangulation is not suitable for datasets of millions of points [39]. In practice, measured engineering surfaces usually contain a large quantity of data, especially using fast optical measurement instruments. As a result, the divide and conquer optimization is used to speed up the computation of morphological envelopes and avoid the risk of running out of memory.

In the context of the alpha-shape method, the vertices of boundary facets of the alpha shape are of tremendous importance because they are the surface points in contact with the rolling ball. The morphological envelope of a surface is determined only by these vertices, while not affected by other points.

The basic scheme of the divide and conquer approach is to break a problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems iteratively, and then combine these solutions to create a solution to the original problem [40]. By applying the divide and conquer method, the surface under evaluation is divided into a series of small subsurfaces. Each subsurface is rolled by the ball to generate a set of alpha-shape vertices. Afterwards, the resulted vertices from each subsurface are merged to reconstruct a super set of vertices, which will be treated as the point set for the next iteration. It will be noted that some of the vertices around the joint sections in the previous iteration are removed. By repeating the iterations, the final alpha shape of the original surface can be found and the morphological envelope of the surface is then determined. A demonstration of the divide and conquer procedures is given in figure 7.

## 4. The contact points and their searching procedures

Using the alpha-shape vertices, the divide and conquer optimization reduces the amount of points in the iteration processed by the Delaunay triangulation. However, it is not a fundamental change to the alpha-shape method because the Delaunay triangulation is still required in order to extract the alpha-shape boundary facets. It will be revealed that the Delaunay triangulation is not necessary for searching the boundary facets and an alternative computational method is explored by searching the contact points.

### (a) Redundancy of the Delaunay triangulation

In Edelsbrunner's theory, the alpha shape is extracted from the Delaunay triangulation. In fact, the whole family of alpha shapes can be generated from the Delaunay triangulation, from the point set itself (*α*→0) to the convex hull of the point set (). Therefore, the Delaunay triangulation data could be re-used for multiple attempts of ball radii for the same dataset. It however could be a drawback because the Delaunay triangulation is costly for large areal datasets. Given a single radius, the Delaunay triangulation contains much more information than is necessary to generate the corresponding alpha shape for that radius. Thus in this sense, it is a waste of time and memory to achieve the desired alpha shape with redundant computation.

### (b) Definition of contact points

In physics, the contact points are those points on the surface which are in contact with the moving structuring element. Thus, these points give an indication as to which surface portions in the neighbourhood of these contact points are most likely to be active in the contact phenomenon. From the point of view of mathematical morphology, the contact points are those points on the surface which remain constant before and after morphological closing/opening operations. Based on the mapping between the alpha hull and morphological opening and closing envelopes, the formal mathematical definition of the contact point is given in definition 4.1, using alpha-shape theory:

### Definition 4.1

Given a sampled point set (*d*=2,3) and (*δ*: sampling interval), the contact points *P*(*α*) are those sampled points {*p*_{i}|*p*_{i}∈*X*} that are on the boundary of the alpha hull ∂*H*_{α}(*X*):

### (c) Propositions for searching contact points

### Proposition 4.2

*Given a point set* (*d*=2,3) *and* *if α*_{1}≤*α*_{2}, *then P*(*α*_{2})⊆*P*(*α*_{1}).

### Proof.

*α*_{1}≤*α*_{2}→*H*_{α1}(*X*)⊆*H*_{α2}(*X*) [41]. By definition 4.1, *P*(*α*_{1})={*p*_{i}|*p*_{i}∈*X*,*p*_{i}∈ ∂*H*_{α1}(*X*)}, *P*(*α*_{2})={*p*_{i}|*p*_{i}∈*X*,*p*_{i}∈∂*H*_{α2}(*X*)}. Hence, *H*_{α1}(*X*)⊆*H*_{α2}(*X*) implies *P*(*α*_{2})⊆*P*(*α*_{1}). □

### Proposition 4.3

*Given the point set* (*d*=2,3) *and* . *The convex hull points must all be contact points*.

### Proof.

Let , hence , where Conv(*X*) is the convex hull of *X*. By definition 4.1, *P*(*α*′)={*p*_{i}|*p*_{i}∈*X*,*p*_{i}∈∂*H*_{α′}(*X*)}, then *P*(*α*′)={*p*_{i}|*p*_{i}∈*X*,*p*_{i}∈∂Conv(*X*)}, namely *P*(*α*′) is the convex point set. By proposition 4.2, *α*≤*α*′→*P*(*α*′)⊆*P*(*α*). Thus, the convex hull points must be contained in *P*(*α*). □

Figure 8 presents an example illustrating the boundary facets of the alpha shape of a planar point set regarding to four different disc radii, respectively. The Delaunay triangulation of the point set is presented by triangle mesh and the boundary facets of alpha shape are graphed as bold dotted lines. It can be easily verified that the results presented by four subfigures are consistent with propositions 4.2 and 4.3. For instance, the contact points of figure 8*a* with radius 1 mm are contained in figure 8*b* with radius 0.5 mm, and so forth.

Following the definition of contact points and two associated propositions, another four propositions are proposed with proofs attached for searching contact points. For convenience of explanation, the morphological closing profile filter with the disc structuring element is taken as the objective for demonstration. These propositions however can be easily extended to the opening filter, horizontal flat structuring elements and areal data. In the context of the statement below, *a* and *b* are two known contact points and *r* is the given radius of the ball (disc).

### Proposition 4.4

*If there are points lying above σ*_{ab} (*left/positive side of* , *then the contact point is the furthest point orthogonal to* .

### Proof.

Suppose there exist some points above *σ*_{ab} (figure 9). The furthest point *c* is the convex point for the point set {*a*, *b*, *c*, *p*_{i}}[42]. By proposition 4.3, the convex point must be the contact point. Thus, *c* must be the contact point. □

### Proposition 4.5

*If there are no points lying above σ*_{ab} *and there exist points p*_{i} *in the circular section* *of the ball with radius* , *then the contact point c is the one among the points* {*p*_{i}} *in* , *which satisfies the condition: the circumscribed circle of σ*_{abc} *have the largest radius among the circumscribed circles of* {*σ*_{abpi}}.

### Proof.

First consider the case |*ab*|≤2*r* (figure 10*a*). Here *a*, *b* could determine a unique alpha ball B with radius *r*. As there exist points in the circular section (the shadowed portion in the figure), , thus *σ*_{ab} is not *α*-expose. By definition 3.1, *σ*_{ab}∉∂*H*_{r}(*X*). Let {*ρ*_{i}} be the radii of the circumscribed circles of {*σ*_{abpi}} and *c* the point with . The circumcircle of *σ*_{abc} must be empty, thus . By proposition 4.2, . By definition 4.1, . Thus *c*∈*P*(*r*), *c* is the contact point.

Then consider the other case |*ab*|>2*r* (figure 10*b*). As |*ab*|>2*r*, fit a great circle with radius *α*=1/2|*ab*| passing through the points *a*, *b* with the centre at the middle of *σ*_{ab}. Similar to the previous case, we could prove *c*∈*P*(1/2|*ab*|). Then by proposition 4.2, 1/2|*ab*|>*r*→*P*(1/2|*ab*|)⊆*P*(*r*), thus *c*∈*P*(*r*), *c* is the contact point. □

### Definition 4.6

{*p*_{i}} are points lying below *σ*_{ab} (right/negative side of . *σ*_{abpi} has a unique circumscribed circle with radius *α*. If the centre of the circumscribed circle is on the positive side of *σ*_{ab}, the circle has the positive radius +*α*, otherwise the negative radius −*α*.

See figure 11, {*p*_{1}, *p*, *p*_{2}} are three points below *σ*_{ab}. *σ*_{abp1} has its circumcircle centre *o*_{1} above *σ*_{ab}, thus it has a positive radius. Conversely, the centre of the circumcircle of *σ*_{abp2} lies below *σ*_{ab}, therefore the radius is negative. The critical case is that of *σ*_{abp} which has its circumcircle centre *o* at the centrepoint of *σ*_{ab}. In this case, the radius is taken as positive.

### Proposition 4.7

*If* |*ab*|>2*r and there are no points lying above σ*_{ab} *and also no points in the circular section* *of the alpha ball with radius α*=1/2|*ab*|, *then the contact point is the one c that satisfies the condition: the circumscribed circle of σ*_{abc} *has the largest radius among the circumscribed circles of* {*σ*_{abpi}}.

### Proof.

See figure 12, there is no point in the circular section , thus the centre of circumscribed circles of {*σ*_{abpi}} locates at the negative side of the chord . Thus, their radii are negative. The circumscribed circle with the largest radius (smallest in absolute value) must be empty, thus *c*∈∂*H*_{α}(*S*). *α*>*r*→*c*∈∂*H*_{r}(*S*). By proposition 4.2, we have *c*∈*P*(*r*). □

### Proposition 4.8

*If* |*ab*|≤2*r and there are no points lying above σ*_{ab} *and also no points in the circular section* *of the alpha ball with radius r, then σ*_{ab}∈∂*H*_{r}(*X*).

### Proof.

See figure 13, here *a*, *b* could determine an alpha ball B with radius *r*. If there is no point lying above *σ*_{ab} and no point in the circular section , then ∂*B*∩*X*={*a*,*b*}. Thus *σ*_{ab} is *α*-expose. By definition 3.1, *σ*_{ab}∈∂*H*_{r}(*X*). □

Propositions 4.2–4.5, 4.7 and 4.8 establish the searching order of contact points. They first target convex hull points between two known contact points, which corresponds to rolling a disc with an infinite large radius over the profile. If no convex hull point lies above the evaluating simplex, the contact point is found by computing the signed circumcircle radii. The contact point is the one that has the largest circumcircle radius. This is equivalent to rolling a disc with a radius smaller than the infinite big but larger than the given radius *r*. Finally, if the simplex in evaluation could hold an empty disc with radius *r* by its two ends, namely the disc is in no contact with other sample points except two end points, then the simplex is a boundary facet of the alpha shape. In summary, the algorithm is searching the contact points using discs with radius ranging from the infinite big down to *r*. It should be notified that the above propositions also hold for areal data by replacing the disc with a ball and the circumcircle with a circumsphere.

Although the presented algorithm is specific to circular structuring elements, it is even easier to apply the basic scheme to horizontal flat structuring elements. In that case, the contact point is examined by checking the highest point (say *p*_{2} in {*p*_{1},*p*_{2},*p*_{3}}) between two known contact points (say *a*, *b*). If that point is lower in height than two given contact points (say *p*_{2} is lower than *a*, *b*) and the horizontal distance between the two contact points is smaller than the length of the given horizontal line segment (say |*ab*|<*L*), the searching procedure exits and the envelope height is determined by the lower height of the two contact points.

## 5. Performance comparison

Using the traditional method, the calculation of each envelope coordinate will involve the whole surface data when the size of structuring element is equal and larger than that of the surface, thus its time complexity is *O*(*n*^{2}). The alpha shape depends on the Delaunay triangulation, which has the theoretical time complexity of . The divide and conquer optimization, although still relying on the Delaunay triangulation, can reduce the amount of points being processed in the iteration and require less computation memory. The contact-point-searching method eliminates the dependence of the alpha-shape method on the Delaunay triangulation, having the expected time complexity .

Table 1 presents the results of algorithm running time against increasing amounts of experimental areal data with the same ball radius. The data matrices range from 100×100 up to 1000×1000 points with sampling interval 5 μm. They are applied by the morphological closing filter using a 10 mm ball. The algorithms were implemented by Matlab R2009 and were run on a computer with 3.16 GHz Intel Core Duo CPU and 3 GB RAM. Table 1 evidently shows that the naive algorithm consumes more much time in dealing with large datasets, e.g. more than 12 h for the 1000×1000 dataset. By contrast, the alpha-shape method achieved higher performances. Its efficiency is improved by the divide and conquer optimization. Generally, the contact-point-searching algorithm achieved better results over others. The number of contact points is quite small in comparison with that of the original areal data. For instance, there are only 3189 contact points in the 500×500 dataset. However, it could be noted that its performance on the 1000×1000 dataset is slower than that of the alpha-shape method with the divide and conquer optimization. It is owing to the fact that the bigger the dataset is, the more recursions are required and deep recursion levels will evoke huge additional memory operations for stack maintenance.

## 6. Case studies

Two freeform surface case studies are used to illustrate the capabilities of the proposed computation theory for morphological filters. In figure 14, a saddle surface is presented with a number of tiny bump features on the surface topography. It can also be observed that the surface has several twisted waves superimposed on the topography. Morphological symmetrical filters (closing followed by opening) are applied to this surface with ball radius 0.5 and 2 mm, respectively. Figure 15 illustrates the generated surfaces. It is obvious that bump features are suppressed by the filter in figure 15*a* and wave features are also smoothed in figure 15*b*. By comparing the three surfaces, these topographical features of the surface can be separated and analysed.

In the second example, figure 16 is the surface measured from an optical F-theta lens, which is widely used in laser printers and scanners. F-theta lenses are designed to have a smooth and continuous freeform shape to achieve specific optical functions and have ultraprecision accuracy with submicrometre shape error and nanometre roughness. Using a morphological closing filter with ball radius 2.5 mm, a covering envelope surface is constructed (figure 17*a*). The surface presented in figure 17*b* is the residual surface obtained by subtracting the envelope surface from the original surface. The material defects as well as manufacturing marks possibly produced by the diamond fly-cutting are easy to detect on the residual surface.

## 7. Conclusion and future work

Morphological filters are useful tools in the surface analysis toolbox. Regarded as the complement to the mean line-based filtration techniques, morphological filters are relevant to the functional performance of surfaces, especially contact phenomenon of two mating surfaces. The conventional implementation of morphological filters has several fatal deficiencies that restrict the prevalence of morphological filters.

A full set of geometric computation theory for morphological filters is developed. On the basis of the relationship between the alpha hull and morphological envelopes, alpha-shape theory is applied to the computation of morphological filters. The geometrical computation method brings in prominent capabilities so that the new algorithm works for freeform surfaces and suits non-uniform sampled surfaces, with arbitrary disc/ball radius enabled. The divide and conquer optimization further improved the performance of the alpha-shape method and reduced the memory usage. To release the dependence of the alpha-shape method on the Delaunay triangulation, a set of definitions and propositions for searching contact points is presented and mathematically proved based on alpha-shape theory. The contact-point-searching method is applicable to both circular and horizontal flat structuring elements, bringing in more generality over the alpha-shape method.

Key issues of the future work include further improvement of the alpha-shape algorithm by practical programming and efficient data structures, and further optimization of the contact-point-searching algorithm, which consists of two aspects: (i) improve the performance; recursion should be replaced by iteration to avoid the huge cost of stack manipulations; and (ii) improve the robustness against arbitrary and complex shapes of surfaces.

## Acknowledgements

X.J. gratefully acknowledges the Royal Society under a Wolfson-Royal Society Research Merit Award. The authors gratefully acknowledge the UK's Engineering and Physical Sciences Research Council (EPSRC) funding of the EPSRC Centre for Innovative Manufacturing in Advanced Metrology (grant no. EP/I033424/1) and the European Research Council under its programme ERC-2008-AdG 228117-Surfund.

- Received March 4, 2013.
- Accepted August 1, 2013.

- © 2013 The Author(s) Published by the Royal Society. All rights reserved.