Polygonal Segmentation and Refinement of Aerial Digital Surface Maps
At the Video and Image Processing Laboratory (VIP Lab) we are engaged in automated 3D Model Generation for Urban Environments. A Digital Surface Map (DSM) is constructed by projecting laser scan points, taken from an airplane, to the ground (xy plane) and coding the depth of the scan point by a gray value. Figure 1 shows the schematic of an airplane flying over a city and figure 2 shows the DSM of the north UC Berkeley campus
Figure 1: Aerial Scanning of a city
Figure 2: Digital Surface Map of noth UC Berkeley campus
The DSM can be depth segmented using a flood-filling algorithm to give figure 3. In this figure the ground is coded as gray color and every other color corresponds to some depth value.
Figure 3: Depth Segmented DSM
The aerial data is very noisy and low resolution. A 3D model using the raw DSM is shown in figure 4
Figure 4: 3D model using raw DSM
Note that the building facades are jagged instead of being straight - this is because of the jaggedness in the building contours of the DSM. The jaggedness in the building facades adversely affecting their texture mapping. Also the roof tops are not planar and pointed cone like structures are prevalent in figure 4 and these correspond to the noisy data points (outliers) in the DSM. Our goal in this project is to fit polygons to the building contours in the DSM, to straighten the contours and to refine the DSM so that the resulting 3D model is more realistic and visually pleasing.
A flowchart giving an overview of the data processing steps is shown below:
Figure 5: Overview of the data processing steps
We start by applying an operation CloseImage to the image in which for each pixel (x,y) in the image we take a 3x3 window centered at this pixel and construct a histogram of color values. We exclude the center pixel (x,y) in constructing the histogram. If the most commonly occurring color has votes > 4 we replace the color of the center pixel (x,y) with the most commonly occurring color. This is illustrated in figure 6.
Figure 6: The CloseImage Operation
Figure 7 shows close up of a region in the raw DSM and the result after 3 iterations of CloseImage
Figure 7: DSM after 3 iterations of CloseImage
After applying 3 iterations of CloseImage we start tracing contours of buildings and fitting polygons to them. A pixel (x,y) is defined as a boundary point if (1) it is not gray and (2) in the 3x3 window centered at the pixel there is at least one pixel that has color not equal to color of (x,y). We need an auxiliary array A that tells whether a pixel is a boundary pixel or not. A(x,y) = 0 means we don't know whether (x,y) is a boundary pixel or not. A(x,y) = -1 means (x,y) is not a boundary pixel. A(x,y) = 1 means (x,y) is a boundary pixel. We initialize A to 0 and keep updating it as the status of pixels becomes known. Contour Tracing is done using the Radial Sweep algorithm. A good tutorial can be found at http://www.cs.mcgill.ca/~aghnei. As we trace the contour we change A(x,y) of the contour pixels from 0 to 1. The algorithm terminates upon encountering 3 consecutive boundary pixels that have already been marked before i.e. for which A(x,y) is 1. There are a few cases when the algorithm fails. This is illustrated in figure 8.
Figure 8: A case when Radial Sweep fails
In such cases we use another algorithm called MarkBdry. Figure 9 shows the order in which Radial Sweep would check points for boundary pixels. The current point is labeled Current and the previous boundary point in the sequence is labeled prev. Instead of using the ordering in Figure 9 MarkBdry uses the ordering shown in Figure 10.
Figure 9: ordering in Radial Sweep Figure 10: ordering in MarkBdry
Thus MarkBdry tries to keep going in the same direction. Also we try to avoid points that have already been marked before - thus if A(x,y) = 1 for point 1 but A(x,y) = 0 for point 2 and point 2 is a boundary point we insert 2 in the contour sequence instead of 1. The stopping criterion for MarkBdry is same as that for Radial Sweep. Figure 11 shows the contour traced by MarkBdry.
Figure 11: Contour traced by MarkBdry
It is important to note that MarkBdry also fails in some cases - thus we combine Radial Sweep and MarkBdry
After the contour of a polygon is traced and we find that it has less than 16 pixels (corresponding to a small area) we remove the polygon from the image and replace it with ground. Figure 12 shows the flowchart for doing this
Figure 12: Removing small polygons from the DSM
If the contour has more than 40 pixels we fit a polygon to it using the Douglas-Peucker-Ramer algorithm. A good interactive demo can be found at http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/guirlyn/iterEndpoints/frames.html. This is followed by scan converting lines and refining pixel values near the polygonal boundary. First we have to determine the interior and exterior of the polygon. Figure 13 explains how this is done - we count the number of polygon pixels to the left and right of the polygon boundary - the side having higher count is the interior of the polygon.
Figure 13: Finding interior and exterior of polygon
Once we have found the interior and exterior we change the color of all non polygon pixels in the interior to the color of polygon and remove polygon pixels lying in the exterior of the segmented polygon. Figure 14 shows the result.
Figure 14: Refining pixel values near the boundary of the polygon
Figure 15 shows the segmented and refined DSM using above data processing techniques.
Figure 15: Segmented and Refined DSM
Figure 16 shows 3D Model using the segmented and refined DSM
Figure 16: 3D Model using Refined DSM
Acknowledgements: Christian Fruh