An Evacuation Route Model for Disaster A ected Areas

Abstract

Natural disasters such as earthquake severely damage buildings and introduce obstacles to people trying to evacuate an a ected area. Detecting and analyzing the severity of damage to an a ected area is a challenge. This paper proposes a novel model for classifying damaged buildings and supporting people's evacuation from natural disaster a ected areas using satellite images. The model integrates image segmentation and classi cation with a shortest path algorithm. First, buildings are detected from pre-disaster satellite images using the proposed Segmentation model. Second, post-disaster images are classi ed based on the severity of the damage using the proposed Classi cation model. Finally, the shortest and safest evacuation route to a rescue shelter is detected using the Dijkstra's algorithm. Results show that the Route Detection model dynamically adapts to new and updated satellite images. The Segmentation model shows an F1 score 5% better than the Building Footprint Extraction model and the Classi cation model shows F1 scores 8% and 10% better than the VGG16 and VGG19 respectively. The Evacuation Route model is useful to disaster management teams and trapped people for planning safe evacuation routes out of the a ected area.

Keywords

• Natural Disaster Management
• Image Processing
• Deep Learning
• Shortest Path Algorithm

-

Natural disasters arise out of the weakness in the biological and geophysical processes of the earth and can result in damage to the a ected areas such as buildings and roads [ 16 ]. To lessen the impact of a natural disaster, governments employ disaster management techniques such as the management of resources and responsibilities for dealing with all humanitarian aspects of emergencies, in particular preparedness, response and evacuation of people.

Current models and systems that are used for assisting in disaster management are mostly based on the processing and semantic analysis of real-time data extracted from social networks [ 16 ]. Data from these sources are unreliable and scarce due to the disruption to network connectivity as a result of the natural disaster [ 13 ].

Satellite images can assist in real-time with the detection of disaster a ected areas. Moreover, they may assist in de ning an evacuation route that takes into account the damage to the existing infrastructure [ 2 ]. The challenge is to detect damaged and undamaged buildings in these images.

The aim of this research is to investigate to what extent can machine learning segment and classify satellite images in order to detect an evacuation route from a disaster a ected area to a rescue shelter.

The major contribution of this paper is an innovative model to detect and classify the severity of damage on satellite images of a disaster a ected area, and recommend the safest and shortest evacuation route to a rescue shelter. The evacuation route model is comprised of three models namely, Segmentation, Classi cation and Route Detection. The Segmentation model uses the U-Net model [ 14 ] to detect buildings in the satellite images. The Classi cation model uses the ResNet50 model [ 9 ] to classify the buildings on the disaster a ected area based on the severity of the damage in icted to them. Finally, the Route Detection model uses the Dijkstra's algorithm [ 4 ] to nd the shortest and safest evacuation route to a rescue shelter.

The proposed evacuation route model can assist with the post-disaster response of rescue teams by detecting safe evacuation route that can guide people to a rescue shelter in a shorter time. The building detection accuracy of the Segmentation model is compared with the Building Footprint Extraction model [ 12 ]. The Classi cation model is compared with the VGG network [ 15 ]. The Route Detection model is not compared to any other model, but is included in order to demonstrate its adaptiveness in a dynamic disaster environment.

This paper discusses related work in Section 2 with a focus on machine learning approaches to natural disaster management and image processing. Section 3 describes in detail the proposed evacuation route model. Section 4 evaluates the performance of the components of the evacuation route model against existing state-of-the-art models. Finally, Section 5 concludes and discusses some directions for future work. 2

Related Work

Natural disaster causes huge damage to society. An e cient and complete natural disaster management system comprised of analysis, planning and response stages may support minimizing fatalities and infrastructure losses [ 5 ].

Many approaches based on data processing have been proposed to support natural disaster management [ 16 ]. Due to the physical extent and unfavourable geography of disaster a ected areas, satellite images have played a vital role in providing an in-depth knowledge of these areas by capturing a wide range of features on the ground surface.

Convolutional Neural Network (CNN) has been used to extract the required features of disaster a ected areas, such as damaged buildings, roadways, water canals, from satellite images [ 6 ]. Amit and Aoki [ 1 ] propose a model that uses CNN to e ciently extract these features. Their model shows promising results for detecting landslides and oods. Doshi, Basu and Pang [ 6 ] propose a changedetection framework that uses CNN to detect buildings and roads from satellite images, and prediction mask to detect the damaged areas in those images. Although these models detect natural disasters, they do not provide speci c information to support directly in the rescue resources allocation. Chaudhuri and Bose [ 3 ] tackle this issue by using deep learning methods for identifying survivors in debris, thus providing more precise and useful information that contributes directly with the allocation of rescue teams tasks.

In addition to correctly detect and classify disaster-related features from satellite images, deep learning techniques face a challenge to perform this task in small datasets. Pasquali, Iannelli and Dell'Acqua [ 12 ] use the U-Net model for detecting buildings in a small satellite images dataset and their model shows a high classi cation accuracy.

Khodaverdizahraee, Rastiveis and Jouybari [ 10 ] propose a method that uses pre- and post-disaster satellite images to extract and classify disaster-related features. The model shows a 92% accuracy in classifying damaged buildings, but it is computationally intensive due to the need to process and compare the preand post-disaster images.

The limitation of Khodaverdizahraee, Rastiveis and Jouybari's [ 10 ] model can be overcome using an e ective feature extraction technique to detect damage and undamaged structures from satellite images. He, Zang and Ren [ 9 ] propose CNN based ResNet50 model that overcomes this limitation using a dense combination of convolution and max-pooling layer to produce accurate image classi cation.

The previously described models are focused on detecting disaster-related features from satellite images. Although important, they do not provide further insights into supporting rescue teams and trapped people in disaster a ected areas. Post-disaster response tasks can be enhanced, for example, by providing evacuation routes to rescue teams and trapped people in these areas. Bi et al. [ 2 ] propose a model consisting of an autoencoder method and reinforcement learning to nd global optimum evacuation route. The autoencoder technique reduces the data and the Markov Decision Process (MDP) predicts the best evacuation route. MDP, however, is not e ective in real-time situations because it requires many evaluation parameters to solve the problem. To reduce the complexity, Mirahadi and McCabe [ 11 ] propose an evacuation path detection model using the Dijkstra's algorithm. The integration of the Dijkstra's algorithm with strategy planning enables the model to provide dynamic path detection based on realtime data monitoring.

In conclusion, the monitoring of disaster a ected areas can improve the postdisaster response. Satellite images capture the required features from the ground surface and support monitoring post-disaster response tasks [ 6 ]. Only monitoring, however, is not su cient to e ectively support rescue teams and people a ected by the disaster, thus further insights are desirable. Several works approach each of these aspects separately, the proposed evacuation route model detailed in the next section integrates all these aspects.

Evacuation Route Model

The design of the proposed evacuation route model is illustrated in Figure 1. The proposed model combines three models namely the Segmentation, Classi cation and Route Detection model. The Segmentation model pre-processes and segments satellite images of the pre-disaster areas in order to detect buildings. Section 3.1 discusses the Segmentation model. The Classi cation model categorizes the buildings in the post-disaster images based on the severity of damage caused by the natural disaster. The Classi cation model is further discussed in Section 3.2. The Route Detection model identi es the shortest and safest route to a rescue shelter. The Route Detection model is further discussed in Section 3.3. The Segmentation model identi es the buildings from the satellite images by classifying each pixel into either a building or a background. Prior to image segmentation, the satellite images are pre-processed using image centering, data normalization and augmentation techniques. In image centering the mean pixel value of the dataset is computed and subtracted from each of the pixels value. These centered images are then normalized to a value in the range of 0-1, and the random ip and crop of image is performed for augmenting the images.

The U-Net model [ 14 ] is used for image segmentation because it has been shown accurate in identifying objects even in small image datasets. The U-Net model is used to classify every pixel of the images and detect the buildings. In the U-Net the contracting path is implemented using multiple 3 3 convolutions followed by recti ed linear unit (ReLU) activation function. At every step of contraction, down sampling is performed and the feature channel is doubled using the 2 2 max-pooling layer. The expansive path performs up sampling and halves the number of feature channel using 2 2 convolutions at every step. This path also contains concatenation of feature map from contraction path and two 3 3 convolutions followed by ReLU at each step. Finally, 1 1 convolution is used for output the feature mapping.

(a) Pre-disaster input image

(b) Segmented output image The Classi cation model is responsible for classifying the buildings in a postdisaster image into four categories namely, no-damage, minor-damage, majordamage and destroyed. First a random data transformation task is carried out to create multiple images of the input images by performing a vertical ip, horizontal ip and image rescaling. The Classi cation model uses the ResNet50 model to perform the image classi cation because the deeper neural network outperforms in case of a classi cation task [ 9 ]. The ResNet50 is implemented using the transfer learning technique by integrating a pre-trained convolution base with a 3-convolution layer followed by the ReLU activation function and (a) Post-disaster input image (b) Classi ed features max-pooling layer. The dense structure of the Classi cation model has shown to be e ective in classifying disaster a ected areas.

Figure 3 illustrates a post-disaster satellite image (Figure 3a) being provided as input to the Classi cation model and the output is a classi ed image (Figure 3b). The classi ed buildings in the image are represented as green, yellow, blue and red polygons, which correspond to no-damage, minor-damage, majordamage and destroyed respectively. 3.3

Route Detection Model

The Route Detection model nds the safest and shortest route between an origin location and a rescue shelter avoiding the disaster a ected areas. For each segmented and classi ed satellite image generated by the Segmentation and Classi cation models, the Route Detection model receives as input their centroid, latitude, longitude, type and count of damaged buildings. The damaged buildings are plotted on the map in the form of circle, where the diameter of the circle represents the number of buildings a ected by the disaster. The red circle represents destroyed buildings in that speci c area, yellow is used for major-damage buildings, blue for minor-damage buildings and green for no-damage buildings. A hospital within a 5km radius of center of the disaster a ected area is identi ed as the rescue shelter.

Given an origin location, all the available routes from the origin to the rescue shelter is given as input to the route detection algorithm. The algorithm determines the safest and shortest route to the destination using the Dijkstra's algorithm. The pseudo-code of the route detection algorithm is shown in PseudoAlgorithm 1. Algorithm 1 Route detection algorithm

This route detection algorithm checks if the current co-ordinate lies in a disaster a ected area and if it does, then it will backpropagate to the previous point and nd another route from the previous co-ordinate to the rescue shelter. The available safe co-ordinates of multiple routes is compared and the one with shortest distance is selected by the model.

Evaluation

This section shows the results of three experiments used to evaluate the performance of the Segmentation and Classi cation models, and the adaptability of the Route Detection model. 4.1

Experiment 1: Segmentation Model Evaluation

Experiment 1 aims to compare the Segmentation model described in Section 3.1 with the Building Footprint Extraction model proposed by Pasquali, Iannelli and Dell'Acqua [ 12 ].

The models are evaluated using the xBD dataset [ 7 ] composed of 7464 annotated satellite images. The dataset is divided into train and test datasets using 80:20 split ratio with random data shu ing.

Both models use the U-Net model, but they di er with respect to the parameter settings. Table 1 shows the parameter values that di er between the Segmentation and Building Footprint Extraction models.

The performance evaluation of these models is based on the F1 score and Intersection Over Union (IOU) metrics. The F1 score is used to determine the accuracy of the model in identifying the buildings and background in the satellite images. The IOU metric is used to quantify the percent of overlap between the bounding polygon of the building and the identi ed mask.

The results in Table 2 show that the Segmentation model is 5% more accurate in distinguishing between the building and background classes than the Building Footprint Extraction model (column F1 Score); and that the Segmentation model has a 5% greater overlap between the bounding polygon of the building and the identi ed mask than the Building Footprint Extraction model (column IOU).

The IOU presented in Table 2 is an average of the IOUs obtained from 1866 satellite images (test dataset), thus the Wilcoxon Rank Sum test [ 8 ] is used to

Model

F1 Score IOU Building Footprint Extraction Segmentation Model 0.79 0.84 0.68 0.73 test for statistical signi cance of the models' performance. The Null hypothesis states that the IOU of the Segmentation and Building Footprint Extract models is equal, and the alternative hypothesis that the IOU of the Segmentation model is greater than the Building Footprint Extract model. The hypothesis test result rejects the Null hypothesis (p-value = 0:003383 and true location shift > 0:022), thus indicating that the Segmentation model IOU is greater than the Building Footprint Extract model when taking into account any randomness. 4.2

Experiment 2: Classi cation Model Evaluation

Experiment 2 aims to compare the performance of the Classi cation model described in Section 3.2 and the VGG16 and VGG19 models [ 15 ] using precision, recall and F1 Score metrics. The models are evaluated using the post-disaster images in the xBD dataset [ 7 ]. The satellite images are pre-processed to extract buildings polygon image. A total of 54,862 building images of di erent categories, such as no-damage, minor-damage, major-damage and destroyed are generated, and used as input to the Classi cation, VGG16 and VGG19 models.

The VGG16 and VGG19 models are trained using the transfer learning technique. The pre-trained weights of VGG16 and VGG19 models are used as convolution base and then max-pooling layer followed by ReLU activation function is integrated in the network to classify the damaged buildings.

The results in Table 3 show that the Classi cation model based on ResNet50 performs 8% and 10% more accurate in classifying the buildings than the VGG16 and VGG19 models respectively (column F1 Score). The precision and recall values show that the Classi cation model is more accurately classifying the given image into positive and negative classes as compare to VGG16 and VGG19 models. (a) Before disaster data update (b) After disaster data update Experiment 3 evaluates the adaptability of the Route Detection model. First, an origin location is de ned and a hospital within a 5km radius of the center of the disaster area is selected as the rescue shelter (destination). The Route Detection model described in Section 3.3 is used to generate the safest and shortest route to the rescue shelter. Figure 5a shows the output of the Route Detection model (dark green line).

Second, new disaster related data is used to update disaster areas in the map. This update triggers the execution of the Route Detection model that generates another route taking into account the updated disaster areas. Figure 5b shows the new route from the origin location to the rescue shelter when a new disaster area is added to the model (dark green line).

Figures 5a and 5b illustrate the capability of the model to adapt to updated disaster information, such as real-time satellite images. 5

Conclusions and Future Works

This paper proposes an Evacuation Route model for recommending the safest and shortest evacuation route from a disaster a ected area to a rescue shelter. The Evacuation Route model is composed of three models namely the Segmentation, Classi cation and Route Detection models. The key ndings from the evaluation of the model are: { The Segmentation model is 5% more accurate in correctly identifying the building and background classes compared to the Building Footprint Extraction model. { The Classi cation model is 8% more accurate in classifying buildings damage than the VGG16 model and 10% more accurate than the VGG19 model. { The Route Detection model generates the safest and shortest evacuation route to a shelter and is able to adapt to updated disaster related data.

Overall, the Evacuation Route model is capable of detecting and classifying buildings from the satellite images that are then used to recommend the safest and shortest route to a rescue shelter.

Because the model depends on satellite images to provide accurate routes avoiding disaster areas, the model may not be e ective in post-disaster environments that are too dynamic and satellite images are not made available in the same frequency. Although the model will generate correct routes assuming the information available, these routes may not be up-to-date and cross disaster areas. Thus, the applicability of the model in real situation raises ethical issues concerning responsibility and accountability that requires further investigation.

This work can be extended by training the proposed models using satellite images that includes information of damaged buildings as well as road conditions. In addition, the Evacuation Route model can be evaluated against similar framework instead of the individual components' comparison carried out. Furthermore, this framework can also be integrated to other post-disaster resource allocation systems, for instance, the sectorized disaster a ected area can be used to allocate essential supplies such as food, cloth, medicine,and the Evacuation Route model can be used by rescue teams to safely deliver these essential supplies.

References

1. Amit , S.N.K.B. , Aoki , Y. : Disaster detection from aerial imagery with convolutional neural network . In: 2017 International Electronics Symposium on Knowledge Creation and Intelligent Computing (IES-KCIC) . pp. 239 { 245 . Surabaya ( 2017 ). https://doi.org/10.1109/KCIC. 2017 .8228593

2. Bi , C. , Pan , G. , Yang , L. , Lin , C.C. , Hou , M. , Huang , Y. : Evacuation route recommendation using auto-encoder and Markov decision process . Applied Soft Computing 84 , 105741 ( 2019 ). https://doi.org/10.1016/j.asoc. 2019 .105741

3. Chaudhuri , N. , Bose , I. : Exploring the role of deep neural networks for post-disaster decision support . Decision Support Systems 130 , 113234 ( 2020 ). https://doi.org/10.1016/j.dss. 2019 .113234

4. Dijkstra , E.W.: A note on two problems in connexion with graphs . Numerische Mathematlk 1 , 269 { 271 ( 1959 ). https://doi.org/10.1007/BF01386390

5. Dijkstra , E.W. : Conceptual framework of an intelligent decision support system for smart city disaster management . Applied Sciences 10 ( 2 ), 666 ( 2020 ). https://doi.org/10.3390/app10020666

6. Doshi , J. , Basu , S. , Pang , G. : From satellite imagery to disaster insights . In: Proceedings of the 32nd Conference on Neural Information Processing Systems (NIPS 2018 ). Montreal ( 2018 ), http://arxiv.org/abs/ 1812 .07033

7. Gupta , R. , Hosfelt , R. , Sajeev , S. , Patel , N. , Goodman , B. , Doshi , J. , Heim , E. , Choset , H. , Gaston , M. : Creating xBD: A dataset for assessing building damage from satellite imagery . In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops . pp. 10 { 17 . Montreal ( 2019 )

8. Haynes , W.: Wilcoxon Rank Sum Test, pp. 2354 { 2355 . Springer ( 2013 ). https://doi.org/10.1007/978-1- 4419 -9863-7 1185

9. He , K. , Zhang , X. , Ren , S. , Sun , J.: Deep residual learning for image recognition . In: 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) . pp. 770 { 778 . Las Vegas , NV ( 2016 ). https://doi.org/10.1109/CVPR. 2016 .90

10. Khodaverdizahraee , N. , Rastiveis , H. , Jouybari , A. : Segment-by-segment comparison technique for earthquake-induced building damage map generation using satellite imagery . International Journal of Disaster Risk Reduction 46 , 101505 ( 2020 ). https://doi.org/https://doi.org/10.1016/j.ijdrr. 2020 .101505

11. Mirahadi , F. , McCabe , B.Y. : EvacuSafe: A real-time model for building evacuation based on dijkstra's algorithm . Journal of Building Engineering p. 101687 ( 2020 ). https://doi.org/10.1016/j.jobe. 2020 .101687

12. Pasquali , G. , Iannelli , G.C. , Dell'Aqua , F. : Building footprint extraction from multispectral, spaceborne earth observation datasets using a structurally optimized U-Net convolutional neural network . Remote Sensing 11 ( 23 ), 2803 ( 2019 ). https://doi.org/10.3390/rs11232803

13. Ragini , J.R. , Anand , P.M.R. , Bhaskar , V. : Big data analytics for disaster response and recovery through sentiment analysis . International Journal of Information Management 42 , 13 { 24 ( 2018 ). https://doi.org/10.1016/j.ijinfomgt. 2018 . 05 .004

14. Ronneberger , O. , Fischer , P. , Brox , T.: U-Net: Convolutional networks for biomedical image segmentation . In: Navab, N. , Hornegger , J. , Wells , W. , Frangi , A . (eds.) Medical Image Computing and Computer-Assisted Intervention { MICCAI 2015 . MICCAI 2015, Lecture Notes in Computer Science , vol. 9351 , pp. 81 { 93 . Springer, Cham ( 2015 ). https://doi.org/10.1007/978-3- 319 -24574-4 28

15. Simonyan , K. , Zisserman , A. : Very deep convolutional networks for large-scale image recognition . In: International Conference on Learning Representations ( 2015 ), https://arxiv.org/abs/1409.1556

16. Yu , M. , Yang , C. , Li , Y. : Big data in natural disaster management: A review . GeoSciences 8 ( 5 ), 165 ( 2018 ). https://doi.org/10.3390/geosciences8050165