Spatial Gems by Krumm John;Züfle Andreas;Shahabi Cyrus;

Author:Krumm, John;Züfle, Andreas;Shahabi, Cyrus;
Language: eng
Format: epub
Publisher: Morgan & Claypool Publishers
Published: 2024-02-15T00:00:00+00:00

6.2.1Orthogonal Lines Detection

This step takes the marked raster as input and produces all the orthogonal lines that comprise all the polygons. The lines are grouped in rings, that is, a circular linked list of vertices, as shown in Figure 6.1. The key observation is that each vertex on the polygon connects a horizontal edge to a vertical edge. Thus, to find all vertices, we need to locate the parts of the image where a horizontal edge meets a vertical edge. Then, we should connect these vertices in the correct order to create a closed polygon. The problem becomes particularly challenging when dealing with many polygons and high-resolution satellite images where a group of a few pixels could form one ring. In such a situation, the naive image-tracing algorithm needs to track many small polygons, which complicates the algorithm. Therefore, this gem intends to deliver a lightweight algorithm that efficiently finds all polygon segments as orthogonal lines on the high-resolution image through a single scan.

In order to overcome the issue of tracking all orthogonal lines, we observe that a vertex can be detected by checking the window where the vertex is at the center. This is sufficient to detect that a horizontal and vertical edge meet. Figure 6.1 illustrates an example window. This step simply runs a sliding window over the entire raster to create all the vertices and arrange them in the correct order, as further detailed below. The sliding window starts from the top-left and slides over each row from left to right.

Since a window contains only four pixels, and each pixel can either be marked or unmarked, there are a total of 16 possible cases that can happen. If we handle all of them correctly, then we know that we have all possible cases covered. Figure 6.2 illustrates all 16 cases. For formalization, we identify these cases by assigning a bit position to each of the four pixels, as shown in the figure. We can immediately see that cases 0, 3, 5, 10, 12, and 15 do not result in any detected vertices. Cases 1, 2, 4, 7, 8, 11, 13, and 14 each result in creating one vertex at the center of the window. Cases 6 and 9 are special cases that result in two coinciding vertices, both at the center. We chose to create these two vertices to ensure that we create nonintersecting and nonoverlapping polygons. If our goal is to only find the location of the vertices without caring about their connection and order, then it is enough to scan all windows and emit a vertex for each of the above cases. However, we also want to connect them in the correct order, which we describe below.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.