GISdevelopment.net ---> AARS ---> ACRS 1990 ---> Digital Image Processing A new method for edge detection from N-dimensional digital image Meng Qingzhang Electronic Engineering Dept. Tsinghua University Shi Jiuhao Research Institute of Petroleum Exploration and Development China Abstract A n-dimensional digital image can be represented by a fitted hypersurface. Some significant in-formation of the image can be then obtained through studying the characteristics of the hyper the greytone value the 2nd -class Legendre polynomial is selected as the orthogonal basis function. And the coefficients are derived by minimizing the total squared estimation error. Theoretically, a conclusion is that all of the operators for edge detection cab be generalized from these coefficients. The obviousness of an edge is tested by the F-distribution variables for the hypersurface gradients and Laplacians, and the direction at an edge point is coded in [ O, 2p] in a defined sampling interval. For calculating the coefficients a recursive model is designed. The experimental results are obtained from processing a 3-bands airborne image. Introduction There have been a lot of edge detection theories and algorithms in digital image processing books and papers. Most of them are based on the principle of Zero-crossing points from D. Marr's theory about human visual mechanism for extracting the edge information from images. Practically, the methods can be divided into two classes. One is based on the picture greytone features and another is based on the spatial gradient and Laplacian features of the picture. For the first, the thresholding techniques are usually used directly, and for the second, the operator techniques are used. They are usually successful for 2-dimensional edge and line extraction. In multiband and multitime images such as those acquired by Landsat and SPOT, however, different objects respond in different bands. It is hence advantageous to use the information from all of the bands and times of the same scene in edge and lineament detection. In 1981, Morgenthaler and Rosenfeld generalized the Prewitt operators to n-dimensions by fitting a hyoperquadric surface. However, the noise is not introduced into the formulation. In 1982, Chittineni developed the multidimensional edge and line detection theory by fitting a hyper surface to noisy picture function in the neighborhood of an image point using basis functions. Also in Chittineni's paper, the statistical tests are devised for the detection of significant edges and lines and the properties of the operators are studied for rotational invariance. It is the purpose of this paper to generalize the Sobel operators to n-dimensionals by fitting an adjusted hyperquadric surface. The noise is introduced into the formulation here. And also, the directions of the edges which are detected by the hypersurface fitting are quantified in a defined intervals from zero to 2. It is very useful for lineament detection in applications such as geological exploration. Furthermore, experimental results are presented. Hypersurface fitting to picutre function and operators Let R be a hyperrectangular region and x=(x1,…..xn) be a point in n-dimensional space, We can generally choose the coordinate system by putting the center point p0 of the region R at the origin. Let f(x) be the digital picture function over R, and f' (x) be an estimation of f(x). The f'(x) can be defined as: Eq. II-1 Where {si (x) 0 < i < N} are a set of n-dimensional basis functions defined over the R and {a} are a set of coefficients. The total squared estimation error e2 is: Eq. II-2 Using the orthogonal properties of the basis functions, the coefficients {a} that minimize the e2 can be obtained as: Eq. II-3 Let the picture function f(x) can be written: Eq. II-4 where n(x) is noise term and is assumed to be independent Gaucian from pixel with zero mean and variance s2 . From (II-3) and (II-4) we have Eq. II-5 and the conclusions are: the estimated ai are unbaised , normally distributive and independent. Eq. II-6 Eq. II-7 Let the set of n-dimensional basis functions {Si(X) 0 < i < N} can be constructed using one dimensional discrete 2nd-class Legendre orthogonal polynomials Pil(x) as follows: P10 (xi) = 1, P11 (xi) = xi, P12= (x1) = x2i - m12 / m10 P13 (xi) = x3i - xim14 / m12 ..............(II-8) where m12 = Sxki is the kth moment of xi over the domain Xi. From the equations (II-3) and (II-8) , the coefficients a 's, that minimize the sum of squares for errors, are given in the following: Eq. II-9 If the size of R is defined as 3x3x3, the (II-9) can be written as the format of convolutions of the f(x1, x2, x3) with following operators: Eq. II-10 From (II-10) the operators can be divided into two groups which are named directional gradient opertators (Prewitt) and directional Laplacian operators (Pratt and Hall). If the size of R is changed, the relationship between the coefficients and the operators can be generalized similarly. When the coefficients are calculated the e2 and F can be derived . If F is large in a given confidence, then a hypotheses, H: {ai}=0, is rejected. It means that the coefficients which represent the gradients and Laplacians are significant. In other words, the significance of the edge information at the currently being studied point can be detected. Practically the R is a sliding window. So the convolution acts on all of the pixels. Relationships between hypoersureface fitting and sobel operators Usually, the nearest points of P0 are more important for studying P0. In this consideration, additional lines can be fitted to each one-dimensional picture functions in n-dimensional space, For example, the fitted lines can be written as: fi(xi) = a0 + aixi .................(III-1) i=1, ...,n Then the e2 can be written as: Eq. III-2 Where fi = f(0,...,xi,..., 0). Take the example of n=3, then we get: Eq. III-3 In operator format, the equation (III-3) can be written similarly to (III-10): Eq. III-4 From the equation (III-4), we see that the weight matrixes are just 3-dimensional Sobel operators for edge detection. So other type edge detection operators can be also generalized from the corresponding hypersurface fitting formulation. Discussions about the statistical test One of the advantages of the hypersurface fitting method for edge detection is that the statistical test can be used for determining the edge significance. It is much better than directly thresholding the results of the convolution by using the edge detection operators. To decide the edge significance at the being studied point, the coefficients and the e2 of the fitted hypersurface are both examined in the statically variable F. Theoretically, { ai1} and {ai2} are large, they show that the picture function varies significantly. In this case, we say that the edge exsits at the being studied point. Otherwise, this point should be considered as in a homogeneous which no edge exists. In other side, e2 represents the accuracy of the hypersurface fitting to the picture function. If e2 is large, then the fitting accuracy is not confident so that the edges detected in this case are not exact. That is why the F-distribution statistical variables of equation (II-7) is used to test and decide the edge significance. The edges finally detected are from those points at which the e2 is smaller and {ail} are significant. Edge direction coding Another advantage of the hypersurface fitting is that the gradient components at P0 in all of the coordinate system axes are calculated at one time. For those points at which the edges are considered as significant the gradient components in the directions of row and column of the being studied image are examined also. From these two components the edge direction at P0 can be got by calculating the value of [gradient (column)/gradient (row) ±p/2. Practically in application such as geological lineament structure extraction, the edge direction are quantified in a given format from zero to 2p. These quantified angle intervals can be coded. So, the output of the hypersurface fitting for edge detection is an edge direction coded image. This kind of data is very useful for geological structure information extraction. Experimental results An example is presented in this section applying the theory of hypersurface fitting for the processing of a 3-bands false color airborne image. Figure 1 is the original falles color image with the size of 512x512. Figure 2 is the thinned result of edges detected by applying the methods described above. The size of R is 7x7x3. The threshold is determined at 95 percent confidence level for statistical test. The edge direction is quantified into 16 domains with the equal intervals of p/8. The angle which falls in a domain is coded. In fact, Figure 2 is thinned from the image which combines 16 edge direction coded images. Another example is for geological structure extraction, which is presented in reference [4]. Fig. 1 The original false color airborne image with the size of 512 X 512 Fig. 2 The edge information united by 16 edge direction coded image References Rosenfeld, A., and Kak, A., "Digital Picture Processing," Academic Press, New York, 1976. Morgemthaler, D.C., and Rosenfeld, A., "Multidimensional Edge Detection by Hypersurface Fitting," IEEE Trans. Pattern Analysis and Machine Intelligence, V. PAMI-6, July 1981, pp: 482-486 Chittineni, C.B. "Multidimensional edge and line detection by hypersurface fitting using basis functions," 1982 Machine Processing of Remotely Sensed Data Symposium 245-254. Q. Z., Meng, " A new method for geological lineament detection from remote sensing imagery," Chines Remote Sensing Geology , 1987-4.