Segmentation of urban areas using road networks

1 Segmentation of urban areas using road networks microsoft Research Technical Report MSR-TR-2012-65 Nicholas Jing YuanMicrosoft Research ZhengMicrosoft Research XieMicrosoft Research analysis is fundamental and crucial in many geospatial-related applications and research themes, such as trajectory analy-sis, human mobility study and urban planning. In this paper, wereport on an image-processing-based approach to segment urban ar-eas into regions by road networks . Here, each segmented region isbounded by the high-level road segments, covering some neighbor-hoods and low-level streets. Typically, road segments are classifiedinto different levels ( , highways and expressways are usuallyhigh-level roads), providing us with a more natural and semanticsegmentation of urban spaces than the grid-based partition show that through simple morphological operators, an urbanroad network can be efficiently segmented into regions.

2 In addi-tion, we present a case study in trajectory mining to demonstratethe usability of the proposed Segmentation and Subject [Database Management]: spatial databases and GIS, TermsAlgorithms1. INTRODUCTIONIn many geospatial-related applications, such as trip planning[18], urban planning/ urban computing[6][25] and traffic analysis [24][15],an urban area is often segmented into sub-regions for in-depth anal-ysis or complexity reduction. Intuitively, a digital map can be seg-mented into equal-sized grids, where each grid is a rectangle, asshown in Figure 2(a). While the grid-based approach offers simplic-ity in implementation, it has deficiencies as well: The segmentedgrids do not have semantic meanings, thus the results of the analysisbased on these grids do not provide us with a natural understanding,with respect to the road , the road segments of a road network are categorizes in-to different levels according to their functions, , Figure 1 presentsthe road network of Beijing with Level-0,1,2 road segments.

3 Here,the Level-0 and Level-1 road segments (red-colored) are freewaysand city expressways in Beijing, and Level-2 road segments (blue-colored) are urban arterial roads. These main roads naturally seg-ment the urban area into sub-regions with varying sizes and shapes. This technical report details the process of map Segmentation uti-lized in our previous papers[15],[25] and [23]0 5 km1 Figure 1: Level 0,1,2- road segments in the urban area of BeijingIntrinsically, this Segmentation is more natural than grid-based seg-mentation due to the following reasons: First, people live in theseroads-segmented regions and POIs (points of interests) fall in theseregions instead of the main roads.

4 Second, the road -segmented re-gions as the origin and destination of a trip are the root cause ofhuman mobility. In short, people travel among the a Geographical Information System (GIS), there are two ma-jor models to represent spatial data:vector-based model andraster-based model. Vector-based model uses geometric primitives such aspoints, lines and polygons to represent spatial objects referenced byCartesian coordinates, while raster-based model quantizes an areainto small discrete grid-cells (cuboids for the 3D spatial objects)indexing all the spatial objects. For example, the vector model ofBeijing road network (shown in Figure 1) stores aroad segmentas apolyline (polygone for a circuit road ), where a polyline is consist ofa sequence of shape points, represented by coordinates.

5 A road seg-mentris associated with a direction symbol ( ) and two termi-nal points ( , ). ,rcan only be traveled , otherwise, people can start from both terminal points, , Instead, the raster model rasterizes theroad network into grid-cells, where each road segment is represent-ed by a sequence of cell-IDs. Figure 3(a) and Figure 3(a) reveal aportion of the Beijing road network stored with vector model andraster model(726 726 grid-cells) of the two models have advantages and disadvantages de-pending on the specific applications. For instance, vector-basedmethod is more powerful for precisely finding shortest-paths, where-as it requires intensive computation when performing topologicalanalysis, such as the problem of map simplification [10], which(a) Grid-based(b) Hierarchy-based(c) Morphology-basedFigure 2: Different map Segmentation methods(a) Vector model(b) Raster model (726 726)Figure 3: A portion of Beijing road network printed from vec-tor and raster modelsis proved to be NP-complete [9].

6 On the other hand, raster-basedmodel is more computational efficient and succinct for territorialanalysis, but the accuracy is limited by the number of cells used fordiscretizing the road our method, we choose the raster-based model to representthe road network and utilize morphological image processing tech-niques to address the task of map Segmentation . Specifically, araster-based map is regarded as a binary image ( , 0 stands forroad segments and 1 stands for blank space). In order to remove theunnecessary details, such as the lanes of a road and the overpass-es, we first perform adilationoperation to thicken the roads.

7 As aresult, we can fill the small holes and smooth out the unnecessarydetails. Second, we obtain the skeleton of the road networks by per-forming athinningoperation. This operation recovers the size of aregion which was reduced by the dilation operation, while keep-ing the connectivity between regions. The last step is to perform aconnected component labeling (CCL) that finds individual regionsby clustering 1 -labeled grids. We detail the above operations inSection 3 and provide a case study in Section RELATED WORKGrid-based map Segmentation is extensively used in geospatial-related analysis. Krumm and Horvitz [13] predict the drivers des-tination by mapping the historical trips into grid-cells and learningthe destination probabilities with respect to each cell.

8 Powell et al.[18] propose an approach to suggest the most profit grid for taxidrivers by constructing aspatio-temporal profitability mapwith agrid-based Segmentation , where the probabilities are calculated bythe historical data. Compared with grid-based Segmentation , oursolution considering the high-level roads as the boundary are morenatural for studying the human mobility on a map, as described inSection et al. [11] propose a novel road network partition ap-proach based on the road hierarchy. Specifically, the road networksare first divided into areas by high level roads, then the partition pro-cess is recursively performed for each area .

9 The partition processis implemented by finding the strongly connected components afterthe removal of the intersection nodes connected to high level road -s as well as the terminals of high level road segments 2(b) presents the results of this approach for a portion ofBeijing road network . However, this method does not work in ourscenario since 1) our desired region bounded by high level road seg-ments may contain several strongly connected components, and 2)we aim to segment the whole area instead of just the road nodesinto regions, , we need a mapping from any locations represent-ed by latitudes and longitudes (within the bounding box of the roadnetwork) to the region operators are widely used in Geographical informa-tion systems as well as image processing.

10 Saradjian and Amini [20]employs mathematical morphology for map simplification from re-mote sensing images by extracting skeletons from the image andconvert the structure into vectors. Similar works are presented in[16],[17] and [8]. Different from the above methods which arebased on remote sensing images, we aim to segment the urban arearepresented by vector-based model into regions, instead of simpli-fying the map or extracting structures from the MAP SEGMENTATIONWe display the vector-based road network in a plane by perform-ing map projection [22], which transforms the surface of a shpere( , the Earth) into a 2D plane (We use Mercator projection in ourapproach [1, 4]).