## 2 Navigable Graph of an Environment
### Grid Map Segmentation  
Many studies have explored environmental segmentation, and most have sought to construct topological maps by extracting the nodes and edges of empty areas defined using various metrics by reference to a generalized Voronoi graph (GVG) [26; 27; 28]. Using the positions of nodes, the environment can be easily segmented so that each grid cell is assigned to the nearest node; cells assigned to the same node are in the same segment. Other studies have focused more on dividing a grid map [29]. RoomSegis a watershed, grid map segmentation method used to guide autonomous cleaning robots in large environments and is a practical end-to-end implementation even if the grid map is noisy [30]. It is possible to divide a consecutive, local sonar grid map into two regions via cell decomposition and the normalized graph cut method and incrementally segment the environment to construct a connected graph [31; 32].  
A watershed algorithm that is easily implemented and that yields reliable segmentation results is applied to the grid map segmentation in this paper. We engage in hierarchical path-planning using a navigable graph of segmented local grid maps; we do not engage in grid map segmentation per se. The watershed transform detects catchment basins in a grayscale image by considering the image as a topographic relief; the height of each pixel is proportional to its gray level [33]. As the grid map is considered a black (occupied)-and-white (empty) binary image, it must be converted to impart various intensities to empty cells. A distance transform operator is used to calculate the distance to the closest boundary (an occupied cell) from each empty cell. Figure 1(a) shows a grid map image of a public benchmark environment [34], and the grid map image is obtained by constructing a grid map using laser measurements and converting it to a binary image. Figure 1(b) shows the normalized distance transform image computed using the Euclidean distance metric.  
Figure 2: _Cont._Use of the basic watershed segmentation algorithm can cause over-segmentation. Figure 2c shows the segmentation result of the distance transform image of Figure 2b, computed using the basic watershed algorithm. To overcome this problem, a marker-controlled, watershed segmentation algorithm has been developed [33; 35]. This uses markers to indicate initial segment information, thus the number and approximate positions of objects or foregrounds that can be definitely distinguished from backgrounds. Markers are computed using morphological operations such as erosion and dilation. Prior to the watershed application to the grid map, the definite background pixels (occupied cells) are easily recognized from the grid map image; this is not the case for other gray-scale images. When path-planning, we are interested in safe navigable areas (empty cells) and calculate the distance transforms for all such cells. The pixels lying further from occupied cells are considered as definitive foreground segments. The empty cells that exceed the threshold value of the normalized distance transform serve as marker regions. Markers are labeled using the connected components labeling (CCL) algorithm (which assigns unique labels to all pixels in each connected segment). Figure 2d shows the labeled markers; these are combined with the empty cell information of Figure 2e. The marker-controlled watershed algorithm gradually grows regions and decides the segment to which each non-labeled empty cell belongs. Marker-controlled segmentation is shown in Figure 3a.  
Figure 2: Grid map segmentation using the watershed algorithm: (**a**) The grid map image. (**b**) The normalized distance transform. (**c**) Over-segmentation after application of the basic watershed algorithm. (**d**) Markers labeled using the connected component labeling algorithm; the different colors indicate different labels. (**e**) Predetermined markers for marker-controlled watershed segmentation; the white areas are undetermined.