## 3 Topological Map Representation
### Topological Map Reading  
The reading of the topological map means that the map file is parsed first, and then the obstacle occupied information and topological information are restored. The reading process takes two steps: reading the yaml file and the ppm image.  
Here, to explain the contents of the yaml file, the file contains the following main parts:  
* Image file path: Refers to the saved path of the ppm image file.
* Resolution: Refers to the resolution of the map, and is used to represent the scale of a pixel in the real world, with a unit (meters/pixel).
* Origin: Refers to the two-dimensional (2D) pose of the lower left pixel in the map, as (x, y, yaw), with yaw as the counter-clockwise rotation (yaw = 0 means no rotation). The yaw is ignored in this paper.
* Free thresh: Pixels with an occupancy probability less than this threshold are considered completely free.
* Occupied thresh: Pixels with an occupancy probability greater than this threshold are considered completely occupied.
* Mode: The way the file is saved, which can be one of three values: trinary, scale, or raw. Trinary is the default.
* Number of topological vertices.  
Topological information: A series of lists that contain the pixel coordinates of topological vertices, adjacent vertices, and other information (such as semantic information; this is empty in the paper).  
In the map representation method proposed in this paper, the metric map is a two-dimensional map, so the map coordinates, pixel coordinates, initial points, and other relationships can be shown in Figure 4 below. In the image, different color regions represent different topological regions, and dark color regions are more likely to be occupied.  
Traditionally, the origin of the pixel coordinate system is in the upper left corner of the picture, while the origin of the map coordinate system is in the center of the picture, and the pixel coordinates of the center can be calculated by the origin point. Then, with the help of the resolution of the map, all the pixels can be restored to grid cells.  
In the first place, the pixel coordinates of the pixel points in the picture need to be converted into map coordinates by the map coordinates of the lower left pixel, and the specific conversion formula is as shown in Equation (9):  
\[\left\{\begin{array}{c}x_{\text{map}}=x_{\text{origin}}+x_{\text{pixel}}* res\\ y_{\text{map}}{=y_{\text{origin}}}+h_{\text{map}}*res-y_{\text{pixel}}*res \end{array}\right. \tag{9}\]  
where \((x_{\text{pixel}},y_{\text{pixel}})\) is the pixel coordinate, \((x_{\text{map}},y_{\text{map}})\) is the map coordinate, \(res\) is the map resolution, and h\({}_{\text{map}}\) is the height of the map.  
At the same time, the RGB image information in the ppm image file needs to be converted into two parameters in the conical space model, and the conversion formula is shown in Equation (10).  
\[\begin{array}{c}V\leftarrow\max(R,G,B)\\ OM\leftarrow\left\{\begin{array}{cc}\frac{V-\min(R,G,B)}{V}&\text{if }V\
eq 0\\ 0&\text{otherwise}\end{array}\right.\\ TM\leftarrow\left\{\begin{array}{cc}\frac{60(G-B)}{V-\min(R,G,B)}&\text{if }V=R\\ \frac{120+60(B-R)}{V-\min(R,G,B)}&\text{if }V=G\\ \frac{240+60(R-G)}{V-\min(R,G,B)}&\text{if }V=B\end{array}\right.\end{array} \tag{10}\]  
where if \(TM<0\), then \(TM=TM+360\). After the above calculation, the final range of the three values is: \(0\leq V\leq 1,0\leq OM\leq 1,0\leq TM\leq 360\).  
Afterwards, the topological information can be obtained from the parameter TM, and the topological map is established. In addition, the occupied information of the point is read from the parameter OM, and the metric map is established. In this way, the topological information and occupied information can be completely recovered.  
Figure 4: Relations between coordinate systems in the picture in ppm format.