# A Graph-Based Representation of Wastewater Maps

Ikram El Miqdadi, Fatima Abouzid, Salem Benferhat, Nanée Chahinian, Carole Delenne

► To cite this version:

Ikram El Miqdadi, Fatima Abouzid, Salem Benferhat, Nanée Chahinian, Carole Delenne. A Graph-Based Representation of Wastewater Maps. IEEE BigData 2024 - 2024 IEEE International Conference on Big Data, Dec 2024, Washington DC, United States. hal-04844749

HAL Id: hal-04844749

https://hal.science/hal-04844749v1

Submitted on 18 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Graph-Based Representation of Wastewater Maps

Ikram El Miqdadi*, Fatima Abouzid, Salem Benferhat, Nanée Chahinian, Carole Delenne, Hicham Ghennioui, Jamal Kharroubi

December 17, 2024

## Abstract

This paper presents a method for the automatic extraction of the structure of wastewater networks from geographical maps, as well as their representation in the form of graphs. The approach consists first in detecting the different important elementary elements composing a wastewater network, such as the manholes, their identifiers (using optical character recognition, OCR), and the wastewater pipes that connect them. Detecting these elementary elements is a first difficult problem, despite many existing tools, mainly due to the quality of the wastewater network maps used. However, the challenge addressed by this paper is how to select the relevant detected elementary elements, and put them together to finally extract the wastewater network. One of the main contributions of this paper is to propose an efficient algorithm to solve these selection and assignment problems (e.g., manhole identifiers to manholes represented by circles). We also deal with the situation of isolated nodes to have the most connected clusters possible. The experimental results conducted on real maps data show very interesting results despite the low quality of the maps.

## 1 Introduction

As the fields of computer vision and artificial intelligence continue to advance, the importance of accurate and efficient detection of objects and text in images has become increasingly crucial in many applications. In the literature, a great deal of research has been carried out in these areas, exploring fundamental and recent methodologies that contribute to improving elementary object and text detection capabilities (e.g., [Sun et al. (2024) Sun, Sun, and Chen]). In this introduction, we will briefly review some of these methodologies.

The automatic recognition and detection of objects in images remains a complex task, still raising many challenges. Advances in object detection have been

<footnote>*Ikram El Miqdadi and Fatima Abouzid contributed equally to this work.</footnote>
at the heart of computer vision research, with methodologies and techniques constantly evolving to improve accuracy and efficiency. Traditional methods initiated this process by extracting manual features and using classical machine learning techniques. However, the advent of deep learning has revolutionized object detection in images, achieving high levels of accuracy and efficiency. Despite this, the application of deep learning models requires access to large, high-quality training datasets, which can represent a major obstacle when these datasets are not readily available.

One of the basic techniques in computer vision for object detection is template matching, which is particularly useful for detecting simple shapes such as circles. In this context, Marjia Sultana et al. [Sultana et al.(2020)Sultana, Ahmed, Chakraborty, Khatun, Hasan, and Uddin] conducted a comparative study of two object detection methods: template matching and Histogram of Oriented Gradient (HOG) [Zhang et al.(2020)Zhang, Zhou, Li, Li, and Lou, Zhou et al.(2020)Zhou, Gao, Zhang, and Lou]. Their findings indicate that template matching is simple to use but only works effectively if the template picture is precisely cropped from the original. On the other hand, the HOG-based method is more complex to implement, but it achieves superior results in terms of both detection accuracy and processing time.

Algorithms based on the Hough transform principle remain powerful techniques in computer vision, widely used to detect various geometric shapes such as circles and lines in images. A great deal of research and tools continue to be proposed, notably to optimize these algorithms or to detect a wider range of geometric shapes [Beltrametti et al.(2021)Beltrametti, Campi, Massone, and Torrente]. An example of recent work on the use of the Hough transform is presented in [Adeniyi et al.(2024)Adeniyi, Omolewa, and Adeniyi], where the authors propose a fast and accurate method for correcting position errors using positions obtained from a support vessel, thanks to the circular Hough transform. Although the results are promising, the method requires adjustment of the algorithm parameters to improve detection accuracy. Circle detection is an important topic in many fields. This is particularly true in the context of this work, where we are working on maps that represent wastewater networks. Sewer manholes are often represented by colored circles. In addition to circles, lines are another crucial shape to detect in images, and the Hough transform for line detection is a common algorithm widely used in image processing to identify straight lines in an image. For example, in [Javeed et al.(2023)Javeed, Ghaffar, Ashraf, Zubair, Metwally, Tag-Eldin, Bocchetta, Javed, and Jiang] the authors use the idea of track line detection through enhanced canny edge detection using a fast Hough transform. In the context of this paper, line detection is important as they represent wastewater pipes.

Color-based object detection is another technique for identifying and locating objects in images. This technique makes sense when objects in videos or images are of the same color. The method is therefore based on the principle that objects of interest have distinct color characteristics that can be differentiated from the background or other objects. For example, a detection algorithm based on color, depth, and shape is proposed by G Lin, Y Tang, X Zou et al. [Lin
et al.(2020)Lin, Tang, Zou, Xiong, and Fang] to detect spherical or cylindrical fruit on plants in natural environments and thus guide harvesting robots to pick them automatically.

Another type of information to be extracted from images concerns textual data, often rich in semantic information [Chen et al.(2021)Chen, Jin, Zhu, Luo, and Wang]. In recent years, a great deal of research has used artificial intelligence and machine learning tools to automate the analysis of handwritten documents, images, and various document formats. These methods aim to convert these documents into data that can be easily analyzed, modified and consulted. This process includes text detection and recognition, commonly known as optical character recognition (OCR) [Olejniczak and Śulc(2022)]. In this paper, the text on the maps is a valuable source of information for reconstructing wastewater networks. However, not all textual data is relevant to our application. It is therefore essential to detect and filter these texts to retain only information relevant to the wastewater network. More specifically, the textual data we are seeking to extract are the labels or tags associated with each circle (representing a sewer manhole) in the graph. To achieve this objective, we are using OCR, a method commonly used in automated document processing, to identify text on maps.

The use of OCRs is vast, covering a wide range of applications. In this context, Alan Jiju et al. [Jiju et al.(2021)Jiju, Tuscano, and Badgujar] use OCR, in particular the Tesseract OCR engine, to extract data from printed invoices for everyday use. They integrate the OpenCV Python library to pre-process the input data, effectively filtering out unnecessary noise. They then apply the Tesseract method to automatically recognize and extract written text from invoices. Their methodology proves highly accurate when tested on a diverse range of invoice input images.

Another very common application of OCR is that used in toll plazas for automatic detection and recognition of license plates. For example, in [Vedhaviyassh et al.(2022)Vedhaviyassh, Sudhan, Saranya, Safa, and Arun], the authors employ YOLOv5, a variant of the You Only Look Once (YOLO) family, for object detection. They then implement OCR techniques, in particular Tesseract OCR and EasyOCR, for character recognition and extraction from license plates. They use a dataset from GitHub to train and evaluate the proposed model. The results (with EasyOCR PyTorch based on deep learning technologies) achieve an accuracy of detection results of over 95%.

In this paper, we are interested in extracting wastewater network objects from images and then representing them in the form of a graph. More precisely, the input of our work is a map of wastewater networks. The goal is to extract the main components of wastewater networks, namely: sewer manholes (represented as colored circles in the maps), manhole identifiers (in the form of regular text expressions), wastewater network pipes (represented as lines), and finally the direction of water flow (represented by very small arrows in the maps). The approach adopted in this paper involves detecting each component independently. It is therefore crucial to efficiently construct the optimal sewer network from these components. **One of the main contributions** of this work
lies in the use of efficient assignment algorithms to assign identifiers to manholes and link these manholes to the ends of sewer pipes, to reconstruct a global graph representing the sewer network. It is important to note that extracting the various components of the network from images and representing them in a graph is a challenging task. The difficulties arise not only from the poor image quality and the small size of the objects to be detected but also from the noise present in the images. Furthermore, associating the extracted components accurately is an additional layer of complexity, requiring meticulous analysis and robust methods to ensure precise identification and connection of these components.

The following section presents the general context of this work and the dataset used in this paper. Section 3 describes the methodology used in this study to first detect the different elements associated with a wastewater network and then to construct the associated graph. Section 4 discusses the experimental results and section 5 concludes the paper.

## 2 General Context and Dataset Description

In recent years, computer vision has made impressive progress, revolutionizing various sectors such as healthcare and autonomous driving. These advances are largely due to the rise of sophisticated algorithms, the massive amounts of available training data, and the increase in computing power, allowing machines to process and analyze visual data with unparalleled accuracy. However, some challenges remain, such as detecting small objects in images, a task that is still complex due to low resolution, occlusion, and background noise.

In this paper, we focus on the processing of data related to the wastewater network, a crucial and rapidly expanding infrastructure system, especially in dense urban cities. The managers of these networks handle various tasks, including the supervision of the collection, treatment and disposal of wastewater. A sewerage network consists of a diverse set of elements such as pipes, pumps, manholes, etc. These networks are carefully designed to ensure the safe and efficient disposal of wastewater from residential, commercial, and industrial sources.

In France, as in other countries, the wastewater network plays a vital role in protecting public health and the environment by preventing the spread of waterborne diseases and reducing pollution of water bodies. Effective management of the wastewater network is essential to ensure the reliable operation of these systems and meet the growing demands of urban populations. Ongoing maintenance, upgrades, and technological investments are required to address aging infrastructure and adapt to population growth and urbanization.

There is a large dataset regarding wastewater networks. These data are diverse and heterogeneous, including GIS (Geographic Information Systems), images, videos, PDFs, and maps. The main focus of this work is on image maps. These maps are only images and do not contain any information about geographic locations. Our goal is to use all the tools of image processing, machine learning, and assignment algorithms to handle this type of data.
The dataset we worked on in this article includes a collection of images illustrating the wastewater plans of one of the regions of the city of Montpellier (southern France). These wastewater networks are represented on geographical maps covering many areas of the Montpellier region. There are 27 images, each corresponding to a specific area. These data are real and they are associated with videos of inspections made in these different areas of the Montpellier region.

Each map in the dataset contains information about the wastewater network of the region under consideration, as well as other elements such as representations of buildings and, for some maps, street names. The wastewater network is represented by a series of colored circles, each labeled with text distinctly. The connections between these circles, which represent wastewater pipes, are indicated by colored lines and colored arrows. The colors used are mainly red and green. More precisely, the red circles on the map symbolize the different inspection manholes within the network. The lines that link these circles depict the pipes or conduits in the circuit. The tiny arrows are used to indicate the direction of the water flow.

Since these maps of wastewater networks are not directly exploitable, our objective is to propose a method capable of automatically extracting the different elements of wastewater networks from maps and organizing them in a structured and exploitable format. This format will simply be an oriented graph. This graph, once built, will be confronted later with other types of data, such as Inspection Television (ITV) videos or geographic information systems associated with the same geographical region of study.

# 3 Methodology

Our approach to extracting the structure of wastewater networks from maps focuses on the independent detection of each network component. This involves i) identifying the colored circles representing the manholes, ii) extracting the associated labels representing the unique identifiers for each manhole, and finally iii) detecting the segments connecting the various circles within the network; segments representing the pipes between the manholes.

For each component of the wastewater network to be detected, we employ several extraction methods combined with various pre-processing techniques to increase the accuracy of the information extracted from the maps. The results of these different approaches will be presented in the next section.

To detect the circles associated with sewer manholes, template matching, the application of the Hough transform, specifically the HoughCircles method, and an approach based on the detection of red circular shapes, as manholes are represented by red circles.

To extract the text labels representing manhole identifiers, we first used OCR technologies including EasyOCR and Tesseract. These methods were evaluated with and without pre-processing, such as image magnification and contrast adjustment to improve label detection. The results obtained were then filtered using pre-defined regular expressions, in order to retain only the text corre-
sponding to the labels on the circles representing manholes.

To detect the pipes connecting the manholes, represented as colored seg-
ments in the image, we use two distinct approaches. The first approach is based
on the Hough transform, in particular, HoughLinesP [Galamhos et al. (1999)Galamhos,
Matas, and Kittler, Matas et al. (2000)Matas, Galambos, and Kittler], for seg-
ment detection. The second method relies on the detection of colored contours
(the color is given as a parameter). In the maps we have analyzed, the colors
used are both green and red. Subsequently, the lines detected by both algorithms
are filtered to retain only those connecting the circles representing manholes.

Having detected the individual components of the sewer network from the
maps, our next step is to link them up and represent them in the form of a graph
containing as much useful information as possible. To do this, we establish
connections between the various components. First, we propose an algorithm
that assigns textual labels (gaze identifiers) to the various gazes. Next, we
propose an algorithm that assigns links between these glances, using the detected
lines to form the edges of the graph.

4 Algorithms and experimental results

In this section, we describe the different methods used to independently extract
the various network components. Next, we present the results obtained by the
most efficient method for each type of object detected. Finally, we present the
process of associating these components to build a graph.

## 4.1 Detecting the structure of wastewater networks and their objects

4.1.1 Circles detection (representing manholes)

1. *Template Matching:*

Model matching is a computer vision technique widely used in literature.
It involves comparing (or locating) a smaller image, called a reference
model, with different areas of a larger image. This comparison uses var-
ious similarity measures (such as cross-correlation) to identify regions of
the larger image that closely resemble the reference model [Bhoi and Mo-
hanty(2010)].

In this study, the maps we use do not explicitly contain legends. We
therefore had to resort to a screenshot of one of the circles representing
the glances, which will be targeted for detection, using it as a template.
To implement template matching, we used the widely-used OpenCV tool
(with the predefined matchTemplate function) to map the reflex model to
the various map zones.

2. *Hough circle transform:*
The Hough Transform is a powerful technique in computer vision used in image analysis, computer vision, and digital image processing to detect simple shapes, such as lines, circles, and ellipses, in an image (see for more details [Princen et al.(1992)Princen, Illingworth, and Kittler, Kumar et al.(2022)Kumar, Jailia, and Varshney, Matarneh et al.(2023)Matarneh, Elghaish, Al-Ghraibah, Abdellatef, and Edwards]).

The technique converts image pixels into parameter space, where each pixel corresponds to a possible circle center and radius. By collecting votes for circular parameters from edge pixels in the image, the Hough Circle Transform parameter identifies significant peaks in space, indicating the presence of circles.

In our study, we use the Hough transform to detect manholes by treating them as circles. The Hough circle transform is used to identify circles in an image by taking several important inputs. The first input is the image itself, usually in grayscale. The function also requires specification of the detection method, usually by calculating the gradient for standard detection. It adjusts the resolution ratio of the accumulator to the image, allowing flexibility in resolution parameters. It also defines the minimum distance between the centers of detected circles to avoid redundant detections. The function uses Canny's edge detector thresholds to identify edges and an accumulator threshold to determine circle centers. Finally, it defines the radius range of circles to be detected, ensuring accurate identification of circles of different sizes.

### 3. Using color and shape Features:

As already mentioned, color-based object detection represents an effective computer vision approach to identifying objects in images. In the maps we used, which are representative of wastewater network maps, manholes are always represented by colored circles (typically red circles). We therefore used the color parameter as an additional means of identifying manholes in wastewater networks.

The method described in this section is designed to detect colored (in this case red) circular shapes in an image. Firstly, the image is converted from the RGB color space to the HSV color space, which facilitates color representation and manipulation. Next, a range of HSV values specifying the upper and lower limits of the red color spectrum is used. A mask is created to isolate pixels in the image that fall within the specified red color range. To eliminate mask noise, a morphological opening is applied using a predefined kernel size. The contours of the red areas of the processed image are then detected, enabling circular shapes to be identified (For ease of evaluation, the detected circles are colored in a different color, here, green; see (Figure 2).
<figure><img src="image_2.png" /><figcaption>Figure 1: Example of a cropped section from one of the images in the dataset.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: Detection results of circles using color and shape features.</figcaption></figure>

### 4.1.2 On labels detection

In the wastewater network maps we use, manholes have text identifiers that follow a regular expression. Our approach here is therefore to first extract the textual information from the maps, then filter it to keep only those that respect regular expressions. We employed two different OCR technologies, Tesseract OCR and EasyOCR, to extract text from images.

Tesseract OCR is well-known for its capability to detect both printed and handwritten characters across various document types, including PDF files and images in PNG, JPEG, and TIFF formats. A notable advantage of Tesseract is its ability to recognize text in a large number of languages and easily integrate with a wide range of programming languages and frameworks<fnref n="1" />.

EasyOCR is also an OCR library that also supports a large number of languages, making it suitable for different users. Its robustness is attributed to its sophisticated architecture, leveraging deep learning algorithms such as ResNet and VGG which enables EasyOCR to accurately identify text from images and documents <fnref n="2" />.

In our experimental study, we used both methods to extract text from maps, with and without prior pre-processing. The pre-processing steps involved re-sizing the images and increasing their contrast. To restrict ourselves to the textual information representing the manholes' identifiers, the results generated by these OCR techniques are then filtered using regular expressions. Experimental results have shown that EasyOCR with pre-processing gives the best results. These results of applying EasyOCR with pre-processing and filtering with regular expressions are presented in figure 3.

<footnote n="1">¹https://github.com/tesseract-ocr/tesseract</footnote>

<footnote n="2">²https://github.com/JaidedAI/EasyOCR</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 3: Results of applying EasyOCR with preprocessing and RegEx filtering.</figcaption></figure>

4.1.3 Segments detection

1. A color-based approach for detecting segments representing wastewater pipes:

In the detection of manholes, we utilized the red color as a means of identi-
fication. Similarly, in this scenario, we noticed that the lines were marked
with green color. Therefore, we rely on color to isolate and detect these
segments. The utilized method detects and visualizes green lines within
an image. Firstly, the image is converted to the HSV color space to fa-
cilitate better representation and manipulation of colors. Next, specific
lower and upper threshold values are defined for the green color in HSV
format, creating a mask that highlights green pixels. The contours of the
green areas are then identified within the processed image. For each con-
tour detected, extreme coordinates are extracted to draw horizontal and
vertical lines within the contour region. Finally, the original image with
the detected green lines is displayed. This method effectively identifies
and visually represents green lines within the input image (Figure 4).

2. *Using Hough lines algorithm for detecting segments representing wastewater pipes:*

The principle of this method is to first apply contour detection to an
image. Once the contours have been extracted from the source image, we
apply the Hough method for line detection (in the experimental study, we
used the predHoughLinesP method). This method identifies all potential
lines within a specific range of values. This range is determined by manual
tests to establish the optimum minimum and maximum sizes of lines to
be detected.

<figure><img src="image_5.png" /><figcaption>Figure 4: Detection results of segments using the color-based approach.
(Note: The detected segments are highlighted in blue.)</figcaption></figure>
## 4.2 A new algorithm for connecting detected wastewater components

After having independently detected the different objects of the maps composing the wastewater networks, the next step is to connect them and represent them by a graph. To achieve this, we proceed to different assignments, first the labels (identifiers of the manholes) to the circles (representing the manholes), then the circles to the extremities of the pipes (where the pipes are represented by segments). The final output of our work is a graph that represents the wastewater network extracted from the maps. The detected manholes (with their identifiers) are the nodes of the graph while the detected pipes are the edges of the graph.

### 4.2.1 On the assignment of labels to circles

This section proposes an algorithm to perform the task of associating each text extracted from the map (which represents the identifier of a manhole) to its circle (which represents a manhole). This task poses a challenge due to imperfections in label detection, resulting in a greater number of detected circles than labels.

To establish associations between text boxes (representing manhole identifiers) and circles (representing manholes), we calculate the distance between the centers of each text node and each circle node. Determining proximity can involve using different distance measures, such as Euclidean distance or Manhattan distance, to reflect the spatial relationships on the map (the spatial coordinates in the map). In our study, we chose to calculate the distance using the centers of the texts and circles, but other points (of the text box and the circle) could also be considered to measure the distance between a text box and a circle.

Based on this Euclidean distance (between the text center and the circle center), we use an iterative algorithm (see Algorithm 1) with a linear complexity concerning the number of detected circles from the map. This algorithm simply goes through each detected circle and associates it with the nearest text box (to facilitate visual evaluation, we have represented the circles and text box associations by a graph).

Table 1 first presents the results of the evaluation of the circle and text box detection methods performed independently from the maps. The experimental study reveals that the circle detection result is very accurate, consistently identifying the correct number of circles in all tested maps. However, the text detection algorithm has some limitations, as it sometimes misses text boxes, especially in images with a high number of text boxes. This limit affects the algorithm's ability to create accurate associations between circles and text boxes. While some maps show perfect detection and association, others require improvement. Specifically, improvements in text detection and the definition of new distances are needed to reduce missed detection and incorrect associations.

To validate the results of our label-circle association algorithm, we compared it with the well-known Hungarian algorithm [Kuhn(1955), Gabrovšek
<caption>**Algorithm 1** Label-Circle Mapping Algorithm</caption>

Input: text extracted, circles detected
Output: Label-Circle mappings
Begin
G - create Graph
for each circle in circles detected do do
  circle node j- G (add the circle as a node in the graph)
end for
for each circle in text extracted do do
  text node j- G (add the text area as a node in the graph)
end for
for each circle node in G do do
  if Node j- (circle node) then then
    Center circle j- NodePosition(G, circle node)
    Radius circle j- NodeRadius(G, circle node)
    Min distance j- cst (define constant distance)
    Closest text node j- None (variable to store the closest text node)
  if Node j- (text node) then then
    Center text j- NodePosition(G, text node)
    Distance j- (Center text, Center circle)(calculate the distance between the text center and circle center)
    if Distance j Min distance then then
      Min distance j- Distance
      Closest text node j- text node
    end if
  end if
  if Closest text node not None then then
    if Closest text node in text node then then
      (Existing distance, Existing edge) j- Closest text node
    if Min distance j Existing distance then then
      RemoveEdge(G, Existing edge)
      AddEdge(G, circle node, Closest text node)
      Closest text node j- Min distance
    end if
  else
    AddEdge(G)
    Closest text node j- Min distance
  end if
end if
end if
end if
end for
End
<table><caption>Table 1: Performance of the image processing algorithm on different images.</caption><thead><tr><th rowspan="2">Image</th><th colspan="2">Number of Circles</th><th colspan="2">Number of Labels</th><th colspan="2">Number of Segments</th></tr><tr><th>Actual</th><th>Detected</th><th>Actual</th><th>Detected</th><th>Actual</th><th>Detected</th></tr></thead><tbody><tr><td>1</td><td>59</td><td>59</td><td>59</td><td>54</td><td>59</td><td>53</td></tr><tr><td>2</td><td>28</td><td>28</td><td>28</td><td>28</td><td>28</td><td>28</td></tr><tr><td>3</td><td>16</td><td>16</td><td>16</td><td>13</td><td>16</td><td>12</td></tr><tr><td>4</td><td>17</td><td>17</td><td>17</td><td>16</td><td>17</td><td>15</td></tr></tbody></table>

et al.(2020)Gabrovšek, Novak, Povh, Rupnik Poklukar, and Žerovnik, Buzzi et al.(2020)Buzzi, D'Andrea, Fresia, Zhang, and Feng]. This algorithm addresses the problem of matching in bipartite graphs. Typically, we have two types of nodes; for example, nodes representing workers and nodes representing tasks, and weighted links only from worker nodes to task nodes. The aim then is to find an assignment of workers to tasks that is optimal and therefore minimizes the overall cost of the assignment. This problem can be also visualized as a matrix where each cell represents the cost of a particular worker doing a specific job. The Hungarian algorithm always returns an optimal solution with a time complexity of $O(n^3)$.

Our problem is similar in that we have on the one hand a set of nodes representing labels (manhole identifiers) and on the other hand another set of nodes representing manholes (represented by colored circles). The distance between a label and a circle is simply the Euclidean distance between the center of the circle and the center of the label. In our experimental studies, after applying the Hungarian algorithm to our dataset, we observed that the assignment of labels to circles by our algorithm (which is not designed with efficient computational complexity, but with no guarantee of optimality) gives the same results as the Hungarian algorithm on the set of maps processed. Our algorithm, however, has a complexity of $O(n)$, and this is important if we are dealing with maps with a large number of elements (circles, for example).

<figure><img src="image_6.png" /><figcaption>Figure 5: Label-Circle association results.</figcaption></figure>

### 4.2.2 Connecting Circles to Detected Segments

We now handle the problem of matching detected lines with detected circles. Recall that circles (representing manholes), lines or, more precisely, line segments, represent sewage pipes. These two elements are detected independently
using different algorithms. The idea of our algorithm is to filter all the lines detected, retaining only those between the circles. These retained lines are then used to construct the edges of the graph. Put another way, the line filtering algorithm checks whether there is a connecting line between each pair of circles. To do this, the algorithm iterates over each combination of two circles (circle *i* and circle *j*) and examines all the lines detected. For each line, the algorithm calculates the distances between its ends and the centers of the two circles. If these distances are small enough (or close enough), an edge is added between the *i* and *j* circles in the graph.

Although the HoughLinesP line detection method is more abstract and does not consider color constraints, the color-based method yields better results. Figure 6 illustrates the construction of stops using lines detected by the color-based method.

<figure><img src="image_7.png" /><figcaption>Figure 6: Results of applying the filtering and edge construction algorithm to the sets of lines detected by the color-based approach.</figcaption></figure>

### 4.2.3 Handling Isolated Nodes

The results of object detection tools (circles, lines, segments, text labels) are not perfect, especially in the presence of low-quality maps. The use of regular expressions to reduce inaccuracies and the filtering algorithms used enable us to filter the elements detected, keeping only those that are relevant to our context. However, our proposed algorithms do not overcome the problem of non-detected objects, in particular non-detected lines. As a result, the resulting graphs may contain isolated nodes.

The idea in this last section is to focus on isolated nodes only. We assume that each node must be connected to a segment (this is a reasonable assumption, since in reality there are no completely isolated manholes). We then looked for lines that could connect these isolated nodes to other nodes. The principle then is to progressively increase the filtering threshold to accept lines that are more likely to connect these circles, even if they are accompanied by greater uncertainty.

The end result is a graph where the labels above the edges are now attached to uncertainty values. By convention, constructed edges initially have an uncertainty of 0 (or a certainty of 1), whereas for isolated nodes, this degree of uncertainty increases with each iteration. The results after processing isolated nodes are shown in Figure 7. This uncertainty allows us to keep in mind that some detection results are less reliable than others. This approach improves the results by augmenting the number of edges in the graph. However, it occasionally introduces edges not present in the original graph, such as the connection
between circle B5 connection between circle B5 and its neighboring circle near B6 (Figure 7). Nonetheless, the number of correctly added edges exceeds these anomalies.

<figure><img src="image_8.png" /><figcaption>Figure 7: The graph after handling the isolated nodes.</figcaption></figure>

# 5 Conclusion and Perspectives

In this paper, we have developed methods to extract the structure of a wastewater network from maps. The structure of the extracted wastewater network is represented as a graph where the nodes represent the manholes and the edges represent the wastewater pipes. Our method incorporates various algorithms to first independently detect the elements of the network. A key contribution of this paper is the proposal of an efficient algorithm that operates in linear time with respect to the number of manholes, pipes, and network identifiers, facilitating the assignment of these elements. The experimental results show satisfactory results considering the image quality and the network components' characteristics, particularly the size and type of some network elements.

Future work consists of refining our algorithm for assigning labels to circles. Our main goal is to improve the optimality criterion without increasing the computational complexity. The goal is to develop an assignment algorithm with a complexity of ($O(n * \log n)$). This would significantly improve performance, especially when processing large datasets. This optimization represents an important and challenging task in our ongoing research.

We are also working on extracting the geographic coordinates of manholes using the same dataset, which could provide very useful information for augmenting geographic information systems (GIS) on wastewater network data.

# Acknowledgment

This research has received support from the European Union's Horizon research and innovation program under the MSCA (Marie Sklodowska-Curie Actions)-SE (Staff Exchanges) grant agreement 101086252; Call: HORIZON-MSCA-2021-SE-01, Project title: STARWARS (STormwAteR and WastewAteR networkS heterogeneous data AI-driven management). We would like to express our gratitude to "Montpellier Méditerranée Métropole" for having provided us with data essential to this research.
References

[Adeniyi et al.(2024)Adeniyi, Omolewa, and Adeniyi] Tunde Taiwo Adeniyi, Oladele Tinuke Omolewa, and Jide Kehinde Adeniyi. Sclera boundary localization using circular hough transform and a modified run-data based algorithm. *TELKOMNIKA (Telecommunication Computing Electronics and Control)*, 22(3):720-731, 2024.

[Beltrametti et al.(2021)Beltrametti, Campi, Massone, and Torrente] M C Beltrametti, C Campi, A M Massone, and M Torrente. Geometry of the hough transforms with applications to synthetic data. *Math. Comput. Sci.*, 15(4): 553-575, December 2021.

[Bhoi and Mohanty(2010)] Nilamani Bhoi and Mihir Mohanty. Template matching based eye detection in facial image. *International Journal of Computer Applications*, 12, 12 2010. doi: 10.5120/1676-2262.

[Buzzi et al.(2020)Buzzi, D'Andrea, Fresia, Zhang, and Feng] Stefano Buzzi, Carmen D'Andrea, Maria Fresia, Yong-Ping Zhang, and Shulan Feng. Pilot assignment in cell-free massive mimo based on the hungarian algorithm. *IEEE Wireless Communications Letters*, 10(1):34-37, 2020.

[Chen et al.(2021)Chen, Jin, Zhu, Luo, and Wang] Xiaoxue Chen, Lianwen Jin, Yuanzhi Zhu, Canjie Luo, and Tianwei Wang. Text recognition in the wild: A survey. *ACM Computing Surveys (CSUR)*, 54(2):1-35, 2021.

[Gabrovšek et al.(2020)Gabrovšek, Novak, Povh, Rupnik Poklukar, and Žerovnik] Boštjan Gabrovšek, Tina Novak, Janez Povh, Darja Rupnik Poklukar, and Janez Žerovnik. Multiple hungarian method for k-assignment problem. *Mathematics*, 8(11):2050, 2020.

[Galamhos et al.(1999)Galamhos, Matas, and Kittler] C. Galamhos, J. Matas, and J. Kittler. Progressive probabilistic hough transform for line detection. In *Proceedings. 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No PR00149)*, volume 1, pages 554-560 Vol. 1, 1999. doi: 10.1109/CVPR.1999.786993.

[Javeed et al.(2023)Javeed, Ghaffar, Ashraf, Zubair, Metwally, Tag-Eldin, Bocchetta, Javed, and Jiang] Muhammad Awais Javeed, Muhammad Arslan Ghaffar, Muhammad Awais Ashraf, Nimra Zubair, Ahmed Sayed M Metwally, Elsayed M Tag-Eldin, Patrizia Bocchetta, Muhammad Sufyan Javed, and Xingfang Jiang. Lane line detection and object scene segmentation using otsu thresholding and the fast hough transform for intelligent vehicles in complex road conditions. *Electronics*, 12(5):1079, 2023.

[Jiju et al.(2021)Jiju, Tuscano, and Badgujar] Alan Jiju, Shaun Tuscano, and Chetana Badgujar. Ocr text extraction. *International Journal of Engineering and Management Research*, 11:83-86, 04 2021. doi: 10.31033/ijemr.11.2.11.
[Kuhn (1955)] Harold W Kuhn. The hungarian method for the assignment problem. *Naval research logistics quarterly*, 2(1-2):83-97, 1955.

[Kumar et al. (2022) Kumar, Jailia, and Varshney] Sunil Kumar, Manisha Jailia, and Sudeep Varshney. An efficient approach for highway lane detection based on the hough transform and kalman filter. *Innovative infrastructure solutions*, 7(5):290, 2022.

[Lin et al. (2020) Lin, Tang, Zou, Xiong, and Fang] Guichao Lin, Yunchao Tang, Xiangjun Zou, Juntao Xiong, and Yamei Fang. Color-, depth-, and shape-based 3d fruit detection. *Precision Agriculture*, 21:1-17, 2020.

[Matarneh et al. (2023) Matarneh, Elghaish, Al-Ghraibah, Abdellatef, and Edwards] Sandra Matarneh, Faris Elghaish, Amani Al-Ghraibah, Essam Abdellatef, and David John Edwards. An automatic image processing based on hough transform algorithm for pavement crack detection and classification. *Smart and Sustainable Built Environment*, 2023.

[Matas et al. (2000) Matas, Galambos, and Kittler] Jiri Matas, Charles Galambos, and Josef Kittler. Robust detection of lines using the progressive probabilistic hough transform. *Computer vision and image understanding*, 78(1):119-137, 2000.

[Olejniczak and Šulc (2022)] Krzysztof Olejniczak and Milan Šulc. Text detection forgot about document ocr. arXiv preprint arXiv:2210.07903, 2022.

[Princen et al. (1992) Princen, Illingworth, and Kittler] John Princen, John Illingworth, and Josef Kittler. A formal definition of the hough transform: Properties and relationships. *Journal of Mathematical Imaging and Vision*, 1:153-168, 1992.

[Sultana et al. (2020) Sultana, Ahmed, Chakraborty, Khatun, Hasan, and Uddin] Marjia Sultana, Tasniya Ahmed, Partha Chakraborty, Mahmuda Khatun, Md Rakib Hasan, and Mohammad Shorif Uddin. Object detection using template and hog feature matching. *International Journal of Advanced Computer Science and Applications*, 11(7):233-238, 2020.

[Sun et al. (2024) Sun, Sun, and Chen] Yibo Sun, Zhe Sun, and Weitong Chen. The evolution of object detection methods. *Engineering Applications of Artificial Intelligence*, 133:108458, 2024. ISSN 0952-1976.

[Vedhaviyassh et al. (2022) Vedhaviyassh, Sudhan, Saranya, Safa, and Arun] DR Vedhaviyassh, R Sudhan, G Saranya, Mozhgan Safa, and D Arun. Comparative analysis of easyocr and tesseractocr for automatic license plate recognition using deep learning algorithm. In *2022 6th International Conference on Electronics, Communication and Aerospace Technology*, pages 966-971. IEEE, 2022.
[Zhang et al.(2020)Zhang, Zhou, Li, Li, and Lou] Ling Zhang, Wei Zhou, Jingwei Li, Juan Li, and Xin Lou. Histogram of oriented gradients feature extraction without normalization. In *2020 IEEE Asia Pacific conference on circuits and systems (APCCAS)*, pages 252–255. IEEE, 2020.

[Zhou et al.(2020)Zhou, Gao, Zhang, and Lou] Wei Zhou, Shengyu Gao, Ling Zhang, and Xin Lou. Histogram of oriented gradients feature extraction from raw bayer pattern images. *IEEE Transactions on Circuits and Systems II: Express Briefs*, 67(5):946–950, 2020.