<< [NCHC TDW TaskForce] -- Tiled Display Wall >>

Fang-Pang Lin, Wen-Pinn Fang and Wei-Fone Tsai

National Center for High-Performance Computing, Taiwan

National Chiao-Tung University, Taiwan

Abstract In this paper, the problem of identifying a boundary pattern, given a set of scattered data points, is addressed. The solution procedure is also referred to as data warehousing. The boundary pattern is extracted from the scattered point dataset by using r-regular shape. In the solution procedure, a robust and effective Delaunay triangulation method is developed, following the works of Bowyer, to enable meshing over large-scale point datasets and further employment of r-regular shape criteria for the triangulated domain. The procedure is practically applied to a dataset from surveyed profiles of watercourses, which combines different datasets from various databases, with points unconnected and scattered around as a result. The boundary pattern is effectively recognized from our solution procedure of r-regular shape. If the computational domain is of concern, it requires further introduction of gradients to recover the full connectivity of the boundary from the initial boundary pattern.

:: Keywords Data warehousing, r-regular shape,Delaunay triangulation,Boundary pattern

1. INTRODUCTION
Watercourses are usually surveyed in a sequence of profiles, i.e. cross sections measured in high water level along riverbed from one riverbank to the other.
00The work is based on our practical applications for three-dimensional flow simulation over a long flow section, which requires to assembly several surveyed datasets from different databases. These datasets are not necessary acquired in a sequential order due to difficulties encountered in practical field survey, which also tend to omit or lost data in some occasions and to over-sample in others. Our data warehousing [1] is to restructure and to “clean” the data into a reduced regular dataset, which still has sufficient accuracy to represent the geometry. The approach allows us to deal with large scale dataset. We develop a procedure to extract the required geometric point dataset from the databases. The restructure of the data is based on an approach of r-regular shape proposed by Attali [2] to find the pattern of the data, which involves Delaunay triangulation [3,4,5]. The pattern is then used to form a closed boundary, either in 2D or 3D. The clean procedure is accomplished by removing those points that outside the boundary and by reducing the points set according to local gradients over the triangulated mesh. The point set with the closed boundary can now be further meshed for various applications. The applications, apart from the flow simulation, may include advanced visualization, Geographic Information System etc. Our approach is not limited only to the watercourses but also extendable to watershed or general terrain data. It can be useful for supporting water resource management and related environmental issues.
In the following sections, the Delaunay triangulation is first described by the duality of the Voronoi diagram. The property of Voronoi diagram is the basic to construct the r-regular shape. The r-regular shape is then introduced in more details. There are 3 test cases for the our approach. The final one is a practical application to the surveyed geometry of the watercourses mentioned above.

2. DATA WAREHOUSING AND MESHING
Data warehousing in terms of r-regular shape is explained in more details in this section. We first describe Voronoi diagram, which in duality constructs Delaunay triangulation. The procedure for the Delaunay triangulation is based on the previous work of the first author. The detail of the procedure is referenced. The r-regular shape uses the circles that forms Voronoi diagram to identify the boundary patterns.

Delaunay Triangulation

The Delaunay triangulation was first proposed by Delaunay [6], who use the duality of the Voronoi diagram to construct triangular mesh. The method bears his name due to its success in practical applications. To understand how the procedure of Delaunay triangluation does, one has to investigate how the Voronoi diagram constructed. The Voronoi diagram is a domain partition associated with the problem that give a set S of n points in space find the locus of points that are closer to a point than to any other point of S. To express the method in a more rigorous manner, consider a pair of points

and

The set of points closer to

than to

is just the half-plane containing

that is defined by the perpendicular bisector

. This half plan is denoted as

. The locus of points closer to

than to any other point, which is then denoted as

, has the form

is the Voronoi polygon associated with

. For each point in the set S. The space can then be partitioned into a convex net so that each of the original n points belongs to a unique Voronoi polygon. The result is a partition of n regions, which is referred to as the Voronoi diagram. The Delaunay triangulation is simply accomplished by constructing its duality the Voronoi diagram [7].

From the definition of the Voronoi diagram some interesting properties that characterize the Voronoi diagram can be derived. For details of these properties we referred to [8]. The most important amongst them are as the following:

Every nearest neighbor of

defines an edge of the Voronoi polygon

The straight-line duality of the Voronoi diagram is a triangulation of S.

The first property shows a straight-line duality between the edge of the Voronoi polygon

and its neighbor

and the corresponding segment

, which results in the second property that the triangulation problem can be solved in dual by constructing a Voronoi diagram. The triangulation using the duality of Voronoi diagram is known as the Delaunay triangulation. It has to be noted that the second property may fail, i.e. the triangulation is not unique. If certain subsets of four or more points are co-circular in two dimensions, or five or more points co-sphere in three dimensions. If such degeneracy has encountered special treatment has to be carefully devised. In practice the procedure for Delaunay triangulation that we followed is from the work of Bowyer [9] and his followers [10,11]. The procedure has proved effective and robust.

r-regular shape

The method is developed in the interest of building a mesh induced by the proximity relationships of the points scattered on a surface. The method is appeal to a large class of problems that associates with pattern recognition, computer vision, and graphics. The initial data is a set of points with no structured, which samples a surface. These points can be measured directly on the boundary of an object using 3D sensor or laser range scanning systems. They can also result form the segmentation of a 3D volumetric image. Starting from this mere set of points only known by their coordinates.

To solve this problem, it is common to compute neighborhood graphs of the data points and to restrict the search for a mesh inside this neighborhood graph. Many neighborhood graphs for which efficient algorithms from computational geometry, or from a broader viewpoint of data clustering, exist have been tried [12]. The popular approaches include the k-nearest neighbor graph and general convex hull method, such as α-hull and α-shapes [13] for complicated geometry. An α-shape is a polytope surrounding the set of points. The parameter α controls the maximum “curvature” of any cavity of the polytope. The choice of the parameter αis heuristic.

Unlike the above approaches, Attali gives a theoretically sound approach in 2D, known as r-regular shape and an extension of heuristic in 3D. The concept of r-regular shapes was first introduced in the field of mathematical morphology [14]. Since the parameter r can be arbitrarily small, r-regular shapes offer a relevant model to represent objects arising in image analysis. r-regular shapes have many elegant geometric properties[2]:

The boundary of an r-regular shape has at each point a tangent and a radius of curvature greater or equal to r.

The boundary of an r-regular shape divides any ball with 2r and center on the boundary in exactly two connected components.

From the previous property, it follows that if ε<2r, a normalized mesh provides a tiling of the surface.

In other words, the normalized mesh retains all the topological properties of the surface. The definition of the normalized mesh is referred to Attali.
In the two-dimensional space, any circle passing through three distinct boundary points has radius greater than r.

These properties can be used to characterize boundary faces of normalized meshes, i.e. triangulated mesh by Delaunay. The result is beautifully simple: In 2D, let X be an r-regular shape and E be a sample of , i.e. the boundary of X, with sampling pathε. If ε< sin(π/8)r, then is the normalized mesh, where is a set of boundary edges with and as shown in the associated Voronoi diagram (Fig .1)

3. RESULTS AND DISCUSSIONS
Three geometrical configurations are considered in this study, which are prescribed spiral point set, condensed regular point set and our target irregular scatter point set collected from different surveyed profiles of watercourses. The results are compared with those calculated from minimum spanning tree (MST), which is the popular method in pattern recognition [15].

Spiral geometry
The first case is a spiral point dataset with 1,000 points (Fig.1). The r-regular shape perfectly reconstructs the spiral shape as the theory suggested. MST is tested in this case as a reference, which reaches the same results. The performance of r-regular shape is slightly better than that of MST.

Figure 1. The pattern of the spiral geometry is recovered by r-regular shape.

Condensed regular point set
The second case is a large condensed regular dataset with 46,520 points (Fig.2). There are four blocks with points regularly distributed. The result from r-regular shape is even more successful. MST failed to reach the similar result as expected. Further it took more 10 folds of CPU time to calculate the result. It has to be noted that the regularity affects the upper bound of for δ. In order to recover the boundary for each block simultaneously, the upper bound is lower by approximately 10% to achieve the required results.

Figure 2. The recognized pattern for a condensed regular point set.

Irregular geometry and scattered point set: Watercourses of Kee-lung River
The final case is the real application of r-regular shape to the surveyed profiles of watercourses in Kee-Lung River in the city of Taipei. The area is interesting to many hydraulic researchers due to its narrowing throat in the mid-section as shown in Fig. 3. After data warehousing by r-regular shape, the pattern is identifiable, that the watercourse is separated into two layers: one is the usual watercourse and the other obviously is the water level when the river is in flooding. Similar problem has encountered as the one does in our second test above that the upper bound has to be retuned again in order to get problem boundary pattern. In Fig 3. (c), the pattern appears to be an agglomeration of small pieces of disconnected line segments perpendicular to the boundary of interest. However, The tuning of the upper bound has trivial improvement to make line segments to be connected. MST is failed again in this case. However we use MST to define the computational boundary of the watercourse after the warehousing. It can also be achieved by applying r-regular shape again to the warehoused data for boundary as shown in Fig. 3. (d). To have complete connectivity on the boundary requires further information of gradients. The efforts are relatively trivial. Therefore, we only demonstrate the final mesh for computation (Fig. 3. (e)).

Figure 3.(a) The surveyed profiles of Kee-Lung River, Taipei are assembly from three datasets from various databases with 8,576 points. (b) Meshing following the Bowyer's Delaunay Triangulation procedure. (c)The pattern found from the approach of the γ-regular shape in the procedure of the data warehousing. The low water level, the inner boundary, and high water level, the outer boundary, can be recognized through the pattern. (d) The reconstruction of outer boundary. (e) Mesh generation from the boundary extracted.

4. CONCLUSIONS
In this study the solution procedure for data warehousing applied to the dataset of surveyed profiles of watercourses is developed. The procedure adopts a special geometry property r-regular shape, which is originally introduced in the study of mathematic morphology. The r-regular shape enables the pattern recognition of scattered data. It is therefore well suited to warehouse the data collected from the field surveys of watercourses and usually from different time spans with different survey teams. In the realization of the procedure a Delaunay triangulation based on Bowyer is adopted. The scatter points are organized and connected through the triangulation. Then Attali's proof of the

principle is applied to the Voronoi diagram of the mesh in order to filter out the characteristics of data set, which is usually the boundary of the given dataset. Our approach shows that the feature of the dataset can be well captured even in a limited points scattered at the place of interest. The performance is also better than the classic data clustering method, such as MST. However, the warehoused data has to be further treated if geometrical modeling and/or computational mesh are of consideration. The future development would be an extension to three dimensions.

Acknowledgement
The authors like to thank supports from National Science Council under the grant NSC90-2212-E-321-002.