GISdevelopment.net ---> AARS ---> ACRS 1990 ---> Poster Session Q

Research on the application of relaxation technology to the extraction of linear feature from satellite image

Cui Min-jun Fang, You-ching
Nanjing Forestry University

kou Wen-zheng
Institute of Forestry Inventory, Planning & Designing,
Ministry of Forestry China


Abstract
Based on the non-linear relax model in the relaxation theory, this article deals with the enhancement of linear features in use of contextual information. I order to extract continuous line curve with the width of one pixel, from the remote sensing satellite image, it makes it possible to extract the visible linear feature from the image and to reproduce the discontinuous linear objects covered by closed forests and terrain shadows.

Introduction
To import linear features for geographical information system by means of extracting linear feature from satellite image, in order to display highways, railways, forest roads, bridges, brooks, trees arranged in rows, the linear ring geological structure, faults and cracks etc not only can avoid large quantity of digitising and most part of field work, but also quicken the production of new map.

In recent years, in the field of remote sensing image processing, most of the research of extraction of linear feature focus on the design, research and application of local detector, that is, to use the difference of spectrum between certain pixel and its vicinity. This kind of detection can only be applied in small fields. Besides, the image processed by this method contains much noise and becomes mote complicated, les continuous for linear feature. The limitation of l0ocal detector will be no doubt lead to wrong interpretation on a larger scale.

The information of remote sensing image is involved in the change of spectrum and also in space change of energy. Whether certain point lies in line, it not only on the degree of spectrum difference between itself and its neighbour pixel, but also relates to their position, background and the information of vicinity. The main form of spatial informations in digital pattern recognition are contextual information and neighbourhood information.

If the context is regarded as a spatial change consisting of a group of pixels connected each other in the scene. Thus the field of any pixel can be related to other pixel or its group of the whole scene which means that the usage of neighbour hood structure information not only can reduce the fallibility in linear feature extraction, but also make it possible to extract the different linear feature individually which have the same spectrum characteristics according to their neighbourhood structures.

One of the limitation the contextual analysis is that the extracted linear feature will also unavoidably produce noise and non-continuous features, because the contextual measure needs to be restore the continuity of the learn features the non-continuous lines have to be contected on basis of direction information and more other spatial knowledge. This article is based on on-linear detector to extracted linear features by means of probabilistic relaxation theory in order to get linear feature image with less noise. Of course, the extracted feature still has discontinuously line which demands further on the method of thinning and linking, so as to realize the extraction with choice of difference linear features in accordance with length.

To apply relaxation technology tot eh extraction of linear features takes great advantage of attributes of neighborhood in the object attribute judgment. That is, to adjust continuously the reliable degree of sorts of attributes and when the adjustment become stable, the results is used to judge the object attribute more rationally.

Establishment of relaxation model
To a hazy object group in science, we often we often use the relationship among objects to reduce and eliminate the in distinction. Relaxation is a process to reduce the distinction of the probabilistic label of object using the relationship between their compatibility.

Relaxation processing goes ahead with the help of object labels. Under the suitable definition of compatibility relationship between objects labels, when relation is in use, some labels are strengthened, other are weakened, in the convenience of establishment model of the following labels are drawn.

If a=[a1,a2,a3…………….an) represents object group A=[l1, l2, l3,………. lm} represents label group with certain explanation to objects. In terms of application of curve enhancement, object group represents every image point, the label meaning certain explanation of point represents parts of a curve with certain direction or not. Every probability Pi(l) is corresponding to each label, and they satisfy the following conditions :


Eq.1

where Pi(l) represents the probability estimate of object ai with labe l..Li with label represents the label group of object ai

Two ways are used in the application of neighbour information. They are the choice of neighbour field structure and adjustment to the result of detection. Besides setting up neighbour relationship on object group, the relaxation process can also change the probability estimate by means of iteration.

Depending on compatibility coefficients, Rosenfield's article in 1976 explained the following adjustment of probability with specific deduction and discussion.


Eq.2

Where qik (l) represents adjustment of probability Pik (l) to probability Pik+1 (l). It is defined as neighbour label probability weight's sum regarding compatibility coefficients as weight.

That is :


Eq.3

where coefficient dij represents weight coefficient when object ai influences on object aj and it satisfied Sdij =1

Generally speaking the final probability distribution of label collections not only depends on the initial probability distribution, but also depends on the compatibility coefficient of labels. Relaxation process goes with iteration by the aid of above means until label probability reaches certain limitation.

The limitation of probability is one which represents clear signal, the limitation of probability is 0 which represents indistinctabel signal. In common conditions, the final probability should belong strictly to district (0,1).

Method
Relaxation process is conducted the co-influence of pixel in neighbour field. It makes the lines on one direction extended corresponding to another direction weakened. Similarly, nonlinear liable is strengthen by the non-label in the neighbour field and weakened by suitable linear label. It takes relaxation iteration a few times to be weakened. The points on longer curve may get higher label probability, while others get non-label probability.

In order to use (2), (3) to accomplish linear enhancement it is necessary to solve the problems like to choice of detector, the estimation of initial probability and the definition of compatibility coefficient among objects. It goes as following :
  1. Choose detector: There are three kinds of local detector applied to the extraction of linear feature : linear detector, semi-linear detector and non-linear detector. The extraction of linear feature from remote sensing image, which aims at using gray of pixel, should use non-linear detector, becomes it is fit for the detector of points with the following two characters: a. The gray of the point should be higher than that of it two neighbour points on the same vertical direction of this point shoul have the features as shown in (fig. 1).


    fig.1. non-linear detector

    As for non-linear detector, when condition |b| - |lUc|>Td (defined threshold) is given, e can judge that there exists line in district B non-linear detector divides the whole district into sorts of small districts which can all satisfy the following conditions.

    When {|B2|>A2|} and {|B2|>|C2|}, we judge that line exists in district B.

    Linear detector demands the gray along the lien direction bigger the average gray of all the pixels involved in the two small neighbour fields.

    And so it obviously responds to both noise and border. Semi-linear detector compares the two neighbour small fields seperately and only reflects the noise of single point : while non linear detector reflects neither noise nor border and sometimes the extracted linear feature is interrupted.

  2. Estimation of initial probablit: As non-linear reflects neither noise nor border, and its function is more distinguished at the choice of threshold, the application of contextual information may carry out the connection of local discontinuity.

    Now we beging the estimation of the initial probability of non linear detector as direction number k-=8 is chosen (with reference to Fig2 and Fig 3).


    Fig. 2. linear feature detector model on vertical direction


    Fig. 3. linear feature detector model on 8 different direction

    The initial probability estimation of certain point is defined according to different import values of eight detectors on different directions. To explain accurately, we suppose mk (x,y) represent point (x,y)'s import value of detector on qk direction, P(q)(x,y) (lk) represent point (x,y) is initial probability with label lk. After we multiply detector value with certain coefficient, then to be standardized, the following initial probability is gained.


    Eq.4 & 5.

    To add smaller constant to the above formula can ensure every initial probability not to the zero and non-linear label probability not to be 1, so that the input of changing coefficient


    makes the result more reliable.
Definition of compatibility coefficient
Relaxation process is to reduce the indistinction of the probability label of objects. Compatibility coefficient plays a key role in the process. Although it does not have a clear definition yet, but people still give it some kinds of explanation. The following compatibility coefficient is defined on the common information of the point labels in the neighbourhood. This way is comparatively objective and fit for the feature of compatibility coefficient. If two labels have strong positive relation, they have more common information and vice versa.

If the probability estimation of certain point with label is defined as :


Eq.6

then its united probability corresponding to point (x,y) + (x+i, y+j) with label l' is:


Eq.7

where n represents the number of pixels contained in the window, P(x,y)(l), stands for the initial probability of point (x,y) with label (x,y) has conditional probability with label.


Eq.8

We all know the information quantity can be regarded as a statistical measure of measuring unstability.

If accident A which carrys probability happened, then the information quantity we get is :

I(A)=-logP(A) …………………………………………(9)

Obviously, it a takes place definitely, that is P(A) -= 1, then I(A) which reflects unstable quantity should be 0; on the contrary, when P(A) is near 0, I(A) should be infinite.

The same, under the premise that B takes place, when we know A had taken place, the information quantity we get is :

I(A/B) = - log P (A/B) …………………………………………(10)

From formulas (9), (10) we know the information quantity of accident B, offers to accident A.

I(A;B) = I(A) - I(A/B) = log P(A/B) / P(A) …………………………………………(11)

If the correlation between A ad B is relatively weak, P(A/B) is near I, or I(A/B) is near zero, then B's occurrence offers more information to occurrence of A, that is I(A;B) enlarged. Otherwise, if A and b is anti-related, P(A/B) is near 0, then I(A;B) becomes smaller.

Generally speaking, to substitute (6), (8) into (11) the compatibility coefficient needed in the process of Relaxation can be deduced.


Eq.12

Test of relaxation technology in the extraction of linear feature from Sattelite Image
We try our experiments on image processing machine Mode-75 with VAX-11/750 as host machine for MSS, TM, SPOT images for different resolutions. The extracted linear feature is totally identical to the original image. The following is the summary of calculating step and program designed for extraction method.
  1. Pre-processing of image

    1. Image-extending, to distinguish linear feature
    2. Smooth noise with 22 pattern

  2. choose local nor-linear and threshold to extract rough liner features
  3. Estimate the initial probability according to linear probability model.
  4. Choose the model of compatibility coefficient to calculate compatibility coefficient.
  5. Revise label probability with relaxation model.
  6. Give constant E, after iteration of 1r times, calculate the number of pixel n which satisfies and percent P=N/pixels.
  7. If rate P>Pr (defined value), or the iteration times 1> the given 1max turn to step (5), or end iteration.

TM image 512 * 512 * 3
Shows the initial probability distribution image estimated on
non-linear detector and image after step of
eight-time's iteration processing

Conclusion
  1. As for relaxation label processing, the final probability distribution of label group not only depends on the initial probability estimation, but also depends on compatibility coefficient. This process is fit for the enhancement of linear features.

  2. Whether there exists line in certain point depends decisively on its textural information around.

  3. Rough estimation is needed for initial probability distribution. To get accurate estimation, we can reduce iteration times, but the least iteration times depends on the output of detector and the needed maximum textural circle for correct explanation of an object.

  4. Relaxation process is controllable by probability revising calculating method. It disappears only after eight iteration, which proves the effective textural circle used for object explanation is no big, and too many times f iteration will widen the curve.

  5. Use local iteration to enhance linear detection, that is to detect locally on new linear feature image on the basis of previous detected result.

  6. With the adding of iteration times, the effective texture around point becomes big. Although it enhances the linear feature on the original image, it also shorten the feature and widen the existing discontinuity.

  7. In the relaxation proceeding, compatibility coefficient instead of all the individual value is used.

  8. Some extracted linear features have more noise lonely linear feature and discontinuous line or thick, short line. This make it necessary to further the research on the connecting, thinning and tracing algorithm in the future.
References
  • Rosenfeld A., Scene Labeling by Relaxation Operations, IEEE Trans on SYS, Man, and cybernetics, Vol. SMC-6, No.6, 1976. pp420, 433.
  • Rosen field A. ,Digital picture processing, Second Edition Vol.1-2 1982.