Masato Churiki

Ikuko Shimizu

Rita Zrour
email: zrour@sic.univ-poitiers.fr

Hugues Talbot
email: h.talbot@esiee.fr

Yukiko Kenmochi
email: y.kenmochi@esiee.fr

Akihiro Sugimoto
email: sugimoto@nii.ac.jp

DIGITAL LINE AND PLANE RECOGNITION USING COMBINATORIAL OPTIMIZATION BY MULTIRESOLUTIONAL REPRESENTATION

Line and plane recognition is one of the essential tasks in the field of computer vision. While methods for digital plane recognition based on digital geometry can detect the global optimal solution, they require enormous computation time. In this paper, we propose a digital line/plane recognition method using multiresolutional representation as mixed integer linear programming problems which requires much less computation time than the conventional method. Our method reduces both the outliers of points and the search space of the line/plane parameters at low resolutions. Experimental results show that the computation time was reduced significantly by our method.

INTRODUCTION

Line recognition in 2D space and plane recognition in 3D space are the essential tasks in computer vision and are applied [START_REF] Forsyth | Computer Vision -A Modern Approach[END_REF] in object recognition [START_REF] Faugeras | The representation, recognition, and locating of 3-d objects[END_REF], image segmentation [START_REF] Köster | Mir: An approach to robust clustering -application to range image segmentation[END_REF], and parameter estimation [START_REF] Hartley | Multiple view geometry in computer vision[END_REF]. Therefore, many conventional methods for line/plane recognition are proposed. For example, there are methods based on the least squares [START_REF] Kanatani | Statistical Optimization for Geometric Computation:Theory and Practice[END_REF], M-estimator [START_REF] Huber | Finite sample breakdown of mand pestimators[END_REF], Hough transformation [START_REF] Duda | Use of the hough transformation to detect lines and curves in pictures[END_REF], RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF], LMedS [START_REF] Rousseeuw | Least median of squares regression[END_REF] and so on.

On the other hand, line/plane recognition in digital geometry is also an active research topic [START_REF] Coeurjolly | Computational aspects of digital plane and hyperplane recognition[END_REF], [START_REF] Stojmenović | Digitization schemes and the recognition of digital straight lines, hyperplanes and flats in arbitrary dimensions[END_REF], [START_REF] Gerard | An elementary digital plane recognition algorithm[END_REF], [START_REF] Gérard | A fast and elementary algorithm for digital plane recognition[END_REF], [START_REF] Debled-Rennesson | Linear segmentation of discrete curves into blurred segments[END_REF], [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF]. In digital geometry, a line in 2D space and a plane in 3D space are defined as sets of points between two parallel lines/planes [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF], as shown in Figure 1. There are many methods for determining whether a given set of points is a digital line/plane or not [START_REF] Coeurjolly | Computational aspects of digital plane and hyperplane recognition[END_REF], [START_REF] Stojmenović | Digitization schemes and the recognition of digital straight lines, hyperplanes and flats in arbitrary dimensions[END_REF], [START_REF] Gerard | An elementary digital plane recognition algorithm[END_REF], [START_REF] Gérard | A fast and elementary algorithm for digital plane recognition[END_REF], and for estimating the minimum thickness of the digital line/plane assuming that a given set of points belongs to one digital plane [START_REF] Debled-Rennesson | Linear segmentation of discrete curves into blurred segments[END_REF], [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF]. These methods assume that a given set of points does not contain outliers.

Recently, a method which is applicable for a set of points containing outliers is proposed [START_REF] Zrour | Combinatorial optimization for robust digital line and plane detection[END_REF]. In this method, the optimal subset of points is selected among the all possible combinations of subsets. The optimal subsets contains the maximum number of points which belongs to one digital line/plane. This method is formalized line/plane recognition problem by a mixed integer linear programming problem and can deal with the outliers. However, the computation time is much longer as the number of outliers increases.

In this paper, we propose an extension of a digital line/plane recognition method as mixed integer linear programming problems using multiresolutional representation (Figure 2). Our method reduces both the outliers of points and the search space of the line/plane parameters at low resolutions. The reduction of the search space of the parameters is made possible by adding the constraints to the MILP problem at the higher resolutions. The reduction of points is done by deciding whether points belongs to the estimated line at lower resolutions or not.

DIGITAL LINES AND DIGITAL PLANES

In the Euclidian space R n (n = 2, 3), a line L and a plane P are defined as:

L = {(x, y) ∈ R 2 : ax + y + b = 0}, (1)
P = {(x, y, z) ∈ R 3 : ax + by + z + c = 0}, (2)
where a, b, c ∈ R.

On the other hand, we consider the digital model in digital geometry. A point in digital geometry has integer coordinates. Let Z be the set of integers. Z 2 denotes the set of grid points whose coordinates are all integers in the 2D Euclidean space R 2 . In the digital space Z n (n = 2, 3), a

D(L) = {(x, y) ∈ Z 2 : 0 ≤ ax + y + b ≤ ω}, (3) D(P) = {(x, y, z) ∈ Z 3 : 0 ≤ ax + by + z + c ≤ ω}, (4)
where a, b, c, ω ∈ R. A digital line D(L) is a set of grid points between two parallel lines ax + y + b = 0 and ax + y + b = ω. The distance between two lines along the y axis is ω and the y axis is called principal axis. When the principal axis is the x axis, x in Equation (3) is replaced with y. Similarly, a digital plane D(P) is a set of grid points between two parallel planes ax + by + z + c = 0 and ax + by + z + c = ω. The distance between two planes along the z axis is ω and the z axis is called principal axis. When the principal axis is the x axis, x in Equation ( 4) is replaced with z. When the principal axis is the y axis, y in Equation ( 4) is replaced with z.

FORMULATION OF LINE/PLANE RECOGNITION AS MIXED INTEGER LINEAR PROGRAMMING PROBLEMS

About mixed integer linear programming problems

An optimization problem that maximizes (or minimizes) a linear objective function subject to linear equality and linear inequality constraints is called linear programming (LP) problem. In other words, for a given matrix A and vectors b, c, it is a problem for obtaining a vector x that maximizes (or minimizes) c x subject to constraints Ax≥b and x≥ 0.

Especially, if the elements of x are all required to be integers, then the problem is called integer linear programming (ILP) problem. If only some elements of x are required to be integers, then the problem is called mixed integer linear programming (MILP) problem. The linear programming problem was solvable in polynomial time, but (mixed) integer linear programming problems were generally NP-hard. The performance of the solvers are, however, improving spectacularly in the recent years due to high-performance computers and algorithms [START_REF] Johnson | Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition[END_REF].

Formulation as mixed integer linear programming problems

Firstly we consider a digital line recognition. Let N be the number of points and p i (i = 1, . . . , N ) be a binary variable such that p i = 0 if a point (x i , y i ) satisfies the linear inequalities of a digital line; otherwise, p i = 1. Then, a problem for obtaining a line that has the maximum number of inliers (i.e. the minimum number of outliers) is expressed as a mixed integer linear programming problem: minimize

∑ i=1,...,N p i (5) subject to -M p i ≤ ax i + y i + b ≤ M p i + ω for all i = 1, . . . , N (6) p i ∈ {0, 1} (7)
where M is a large number constant.

In the case that a point

(x i , y i ) is inlier, p i = 0 then Equation (6) becomes 0 ≤ ax i + y i + b ≤ ω (8)
that is equivalent to Equation (3). In the case that a point (x i , y i ) is outlier, p i = 1 then Equation ( 6) becomes

-∞ ≤ ax i + y i + b ≤ ∞. ( 9
)
The technique like this is called big-M method.

Concerning digital plane recognition, let N be the number of elements of points set and p i (i = 1, . . . , N ) be a binary variable such that p i = 0 if a point (x i , y i , z i ) satisfies the linear inequalities of a digital line; otherwise, p i = 1. Then, a problem that obtains a plane that has the maximum number of inliers (i.e. the minimum number of outliers) is expressed as a mixed integer linear programming problem: minimize

∑ i=1,...,N p i (10) subject to -M p i ≤ ax i + by i + z i + b ≤ M p i + ω for all i = 1, . . . , N (11) p i ∈ {0, 1} (12)
We consider that the width ω is 1 for easy description. Any width is also available.

APPLYING MULTIRESOLUTIONAL REPRESENTATION

Multiresolutional representation by downsampling

Although optimizing solvers of MILP problems functions faster, solving it takes enormous amount of time [START_REF] Zrour | Combinatorial optimization for robust digital line and plane detection[END_REF]. In particular, if a ratio of outliers increases we cannot solve by practical time. So, in this paper we use multiresolutional representation to reduce computation time. For simplification, we will explain only the 2D case hereafter, in this section, since the 3D case is easily treated as its extention.

To use multiresolutional representation, downsampling is defined as follows. Firstly, a point (x i , y i ) exists at low resolution when any point of (2x i , 2y i ), (2x i +1, 2y i ), (2x i , 2y i + 1), (2x i + 1, 2y i + 1) exist at high resolution, for the representation at resolution 1/2 of original resolution like Figure 3. By this definition, an image at a low resolution is calculated uniquely. To iterate k times downsampling we obtain a points set of resolution 2 -k .

Reflection to higher resolution

In our method, we reduce computation time by reflecting a recognition result of digital line/plane at low resolution to recognition at high resolution. Precisely, reduction of points and of search space of parameters of line/plane is performed as explained in the following.

Reduction of points

We recognize a digital line/plane from points that may be inliers at high resolution using parameters of a digital line/plane at low resolution. Then computation time will be reduced drastically because of reduction of points that may be outliers.

We use the points such that their corresponding points at lower resolution were inliers.

If outliers are scattered all over the area, the number of points will decrease by reducing resolution, but the number of outliers will not. As a result, the ratio of the numbers of outliers to the number of all points will be higher.

Reduction of the search space of parameters

In the previous section, we showed how to reduce computation time by decreasing the number of points. We will aim to further reduce the computation time by reduction of a search space of parameters. Concerning 2D space, a digital line at low resolution is equal to a line of triple width at high resolution. For instance, in Figure 4 (a) if a red digital line is recognized, points can exist within the pink area. Even at higher resolution, points should lie within the pink area. So any red digital line like in Figure 4 (b) is recognized at its resolution. Therefore if (x i , y i ) is inlier at low resolution, parameters a, b are supposed to satisfy the following inequality:

-2 ≤ ax i + y i + b ≤ 3. ( 13
)
We can add it as a constraint of a mixed integer linear programming problem.

Use of connectivity

Our proposed method attempts to minimize the computational time by using multiresolutional representation and the reduction of resolution which diminishes outliers. However, when several lines/planes exist densely, reducing the resolution may fill up the empty areas and lines/planes may disappear. This can be resolved by not reducing the resolution significantly, which will result in increase of computational time by contrast. Thus, in dealing with large amount of points, as in the actual data, we do not take into consideration the connectivity of points.

Algorithm

Since a principle axis is unknown, mixed integer linear programming problems of all axes must be solved at initial resolution. Then onwards, digital line/plane recognition is Using the strategy above, our digital line/plane recognition algorithm is obtained as shown in Figure 6.

EXPERIMENTAL RESULTS

To evaluate the proposed method, we use the synthetic data and the real data in our experiments. The following results for the computation time shown below contains the time for loading data and displaying the results.

Digital line recognition for the synthetic data

We compare the results of the synthetic data by the proposed method and the conventional method [START_REF] Zrour | Combinatorial optimization for robust digital line and plane detection[END_REF] which has only one resolution. In this experiment, the SCIP Version 1.10 1 was used as the solver of the MILP.

The example of the synthetic data is shown in Figure 6. There were two kinds of synthetic data: (A) various numbers of points, 100, 200, 300, 400, and 500 which contains the fixed number of outliers, 10, and (B) the fixed number of points, 200, which contains various number of outliers, 10, 20, 30, 40, and 50.

The computation times are shown in Figure 7 for (A), and in Figure 8 for (B), respectively. The axes for the computation time in both Figure 7 and Figure 8 are shown with the logarithm scale. The computation time was reduced greatly by the use of multiresolutional representation.

Digital plane recognition for the synthetic data

For the 3D synthetic data, an example is shown in Figure 9. There were two kinds of synthetic data: various numbers of points, 10 and 20 which contains the fixed number of outliers, 50, and the fixed number of points, 100, which contains various numbers of outliers, 10, 20, 30, 40, and 50.

The computation times are shown in Figure 10. The computation time was reduced greatly by the use of multiresolutional representation.

Digital line and plane recognition for the real data

The results by our method for the real data are shown. In the experiments shown in this section, lp solve 2 was used 2 http://lpsolve.sourceforge.net/5.5/ as the MILP solver.

The results of 2D line recognition are shown in Figure 11 and for 3D plane recognition is shown in Figure 12. The real datas are premeasured because they has many outliers.

Computation time [s]

Comparison of RANSAC

We recognize digital lines from sets of points using our method and RANSAC and compare their results. The sets are rounded squares of different angles. The most inlier points were the same; however, with RANSAC an optimal solution was not determined when the angle was 45 • while our method succeeded in determining an optimal solution. The results of our method and RANSAC are shown in Figure 13 and 14 respectively.

DISCUSSION

Computation times rose significantly as the number of points and the ratio of the number of outliers to the number of points increased in results of both 2D and 3D. Furthermore, computation time reduced undoubtedly using multiresoultional representation.

If we know the magnitudes of coefficients and their relative relationships, the number of mixed integer linear programming problems which need to be solved can be reduced since the principle axis can be identified. Sloving unnecessary mixed integer linear programming problems is equivalent to recognizings digital lines/planes from a set of points including numerous outliers, which increases computation time. Therefore, if we could determine the relative relationships of the magnitude of coefficients beforehand, significant reduction of computation time can be expected. Initial resolution can be only determined empirically through the number of points and coordinates. If we do not lower the resolution, it takes enormous computation time; however, if we overly lower the resolution, the geometric structure may collapse and the expecting result may not be obtained or it may lead to infeasible solution if worse.

CONCLUSION

In this paper, we proposed a method to reduce a computation time of digital line/plane recognition as mixed integer linear programming problem using multiresolutional representation. Our method reduces both the outliers of points and the search space of the line/plane parameters at low resolution. Experimental results showed that the computation time was greatly reduced by our method. We also confirmed that the proper line/plane can be recognized by our method.

Notice that if the variances of direction of x, y, z are not in the same range, overly lowering resolution will cause problems such as inability to maintain the geometric structure of the axis of a small variances.

Future work will focus on the automatic adjustment of the width of the digital line/plane.

Figure 1 .

 1 Figure 1. A statistical line (left) vs. a digital line (right).

Figure 2 .

 2 Figure 2. Multiresolutional representation of a digital line.

Figure 3 .

 3 Figure 3. A model of downsampling

  Examples of results of recognitions at higher resolutions

Figure 4 .

 4 Figure 4. Relationship between lines of different resolutions

1 foreach 10 returnFigure 5 .

 1105 Figure 5. An algorithm for digital line/plane recognition using combinatorial optimization by multiresolutional representation

Figure 6 .Figure 7 .

 67 Figure 6. example of 2D synthetic data and a recognized line by our method (red: outliers, blue: digital line)

Figure 8 .Figure 9 .

 89 Figure 8. Relation of computation time to number of outliers for digital plane recognition (the number of points is 200)

Figure 10 .Figure 11 .Figure 12 .

 101112 Figure 10. Relation of computation time to the number of points and outliers for digital plane recognition

Figure 13 .Figure 14 .

 1314 Figure 13. Digital line recognition by our method