An Iterative Approach to Acquire Linear Features under the constraints of their knowledge in Object Space
2.2 Data Preparation
At the beginning, Poly-Morphic feature extraction method [2], will be used in this research to extract relevant junctions and edge pixels in image space. After using non-optima suppression to them, one simple edge-linking algorithm is used to link the adjacent pixels together to form longer edges by considering the pixel connectivity. Since 3-D linear features are our concerns and they should be straight lines in image space. Therefore, Douglas-Peucker algorithm [3] is applied to get 2-D linear segments by considering the pixel collinearity. In this research, each pixel coordinate on 2-D linear segments should be recorded in order to calculate their knowledge in object space. Therefore, the major purpose of Douglas-Peucker algorithm is not for the data generation or reduction.
For deciding the checking priority of those 2-D linear segments, the feature aggregates, including line structures and junction structures, consisting of junctions and line segments are grouped from geometric proximity and collinearity according to their potential to form man-made buildings. For example, a longer linear segment with junctions near both its endpoints could be more possibility from a roof than a single line segment without anything attached to its endpoints. For our method, the former one should have higher priority to be chosen for processing. More details about the classification of feature aggregates was described in [4]. Then both line structures and junction structures together with flanking attributes, i.e. average gray value, on both sides of linear segments are used to develop this iterative approach to match and link linear segments by considering their knowledge in object space.
2.3 Initial screening of possible candidates
This iterative approach will start from higher priority of line structure and is done along the epipolar direction. Since at the beginning we don't know anything about the object knowledge of any linear segment, for each one in left image probably there are many candidates waiting to be chosen in right image. To demand the correctness of results as possible as it can, it is important to give strong constraints for the initial screening of possible candidates in right image. Therefore, object knowledge, geometric and radiometric properties are all considered simultaneously as follows:
From geometric consideration: the initial correspondence of the linear segments between the stereo images must have the junction point along the epipolar direction. This factor is only considered in the first iterative processing procedure. The subsequent three iterative processes don't take this into account. Instead, this part will be replaced by the constraint of height. Plus, their absolute difference of azimuth between the correspondence is within one threshold.
From radiometric consideration: at least one side of the corresponding flanking regions on possible corresponding 2-D linear segments should have similar gray values, i.e. the difference of their mean gray values should be less than a given threshold.
From the object-knowledge consideration:
- Besides the constraint
of the change rate of height, the number of
reliable 3-D edge pieces should be higher than
one threshold. It implies the length of this 3-D
line should be long enough in object space.
- The standard deviation of average change rate of height is smallest among the candidates and less than one threshold. This criterion demands more accurate change rate of height.
Finally, the optimal decision is decided by simple weighting equation:
Where sigma: the sigma of height change rate; dG
L , dG
R: gray difference on the left and right side of line
2.4 Subsequent matching and linking process
After finding the initial correspondence, the process will proceed by matching and linking the next linear segments according to the status of Fig.2. From possible liking candidates. The following constraints in object space will be considered for the optimal liking linear segment.
- For length, the number
of reliable 3-D edge pieces should be higher
than one threshold.
- For "man-made" 3-D
line, the average change rate of height should
be within one certain range.
- For the "same" man-made 3-D linear feature, the absolute value of difference of average change rate on height between linking linear segment and the initial linked linear segment is the smallest among possible candidates and less than one threshold.
The subsequent process proceeds as follows. First, the process will be conducted between the longer linked line segment and the neighboring linear segments of shorter linked linear segments, see Fig.2A and 2B, by the above-mentioned constraints of object knowledge. If the neighboring linear segments could not be found or meet the conditions, the search area formed by the maximum and minimum parallax will be setup.
Then the linear segments in this search area, shadow area in Fig 2a and 2b, will be processed under the same constraints of object knowledge. If the linear segments have the same length, as shown Fig.2C and 2c, only the situation in Fig.2C is processed. The process will repeat over and over until no linear segment could be found and linked. From the constraint on the change rate of height, the process would be applied to handle not only the horizontal lines but also the oblique lines.
Left part means left image and right part shows right image.
Thick and Thin lines: already linked and non-linked 2-D lines
Fig.2: Possible six situations during linking process by using the stereo images based on object knowledge
3.Iterative Approach to Simultaneously Match and Link the Linear Segments
In the iterative approach, Core Algorithm mentioned above is used in each procedure. The iterative processing algorithm is proceeding as follows:
Firstly, this iterative approach will begin from the strongest structures to weaker structure in left image, The strongest structures mean their high possibility to correspond with the imaging of roof boundaries in image space. For example, line structure A in Fig.3 has stronger structure than B ,C and D. That is C and D has the weaker structure in this case.
If the first iterative process succeeds, then not only the object knowledge of 3-D linear segment but also
