11institutetext: Department of Computer Science and Engineering
Graphic Era Deemed to be University, Dehradun India 248002
11email<EMAIL_ADDRESS>
# VBSF-TLD: Validation-Based Approach for Soft Computing-Inspired Transfer
Learning in Drone Detection

Jaskaran Singh 11 0000-0001-9285-2048

###### Abstract

With the increasing utilization of Internet of Things (IoT)-enabled drones in
diverse applications like photography, delivery, and surveillance, concerns
regarding privacy and security have become more prominent. Drones have the
ability to capture sensitive information, compromise privacy, and pose
security risks. As a result, the demand for advanced technology to automate
drone detection has become crucial. This paper presents a project on a
transfer-based drone detection scheme, which forms an integral part of a
computer vision-based module and leverages transfer learning to enhance
performance. By harnessing the knowledge of pre-trained models from a related
domain, transfer learning enables improved results even with limited training
data. To evaluate the scheme’s performance, we conducted tests on benchmark
datasets, including the Drone-vs-Bird Dataset and the UAVDT dataset. Notably,
the scheme’s effectiveness is highlighted by its IOU-based validation results,
demonstrating the potential of deep learning-based technology in automating
drone detection in critical areas such as airports, military bases, and other
high-security zones.

###### Keywords:

Deep Learning (DL) Soft Computing Transfer Learning Drone Detection
Validation.

##  1 Introduction

The advancement of advanced drone technology has brought about a significant
revolution in the field of aerial technology, making it more accessible and
affordable for a wider range of consumers [1], [2]. However, along with these
advancements, certain challenges, particularly pertaining to privacy concerns,
have arisen. A typical drone comprises several key components, including the
frame, propellers, brushless motors, flight control board, RF transmitter and
receiver modules, camera unit, and rechargeable battery [3]. In order to
facilitate communication between drones and users via the Internet, an
architecture known as the Internet of Drones (IoD), or IoT-enabled drones, has
been developed [4]. The availability of low-cost IoT-enabled drones equipped
with advanced sensors and cameras has made it easier for individuals to
capture and transmit images and videos without the knowledge or consent of
others [5]. Consequently, concerns have been raised regarding the potential
misuse of drones, particularly in sensitive areas such as law enforcement,
where privacy holds paramount importance.

Machine Learning is a paradigm that involves the creation of algorithms and
models allowing computers to learn from data and make predictions or decisions
without explicit programming. By utilizing training and learning from past
data, computers can enhance their performance. This field encompasses the
development of mathematical models and algorithms capable of analyzing
intricate data patterns, extracting valuable insights, and making predictions
or taking actions based on these patterns. Machine Learning heavily relies on
statistical techniques and computational algorithms to enable computers to
continually learn and improve from data [6][7].

Computer vision is a subset of machine learning that deals with training
machines using advanced algorithms and techniques to find patterns in visual
images and videos. It uses visual clues to extract meaningful information from
images and make decisions, detect objects, perform feature extraction, and
interpretation. Computer vision is widely used in various industries and
domains, including medical imaging for disease identification and treatment,
autonomous vehicles, automated object detection modules, surveillance systems,
augmented reality, and facial recognition systems [8][9][10]. It is a rapidly
emerging field that continues to evolve with the development of new pre-
trained models, deep learning techniques, and the availability of large-scale
visual datasets.

###  1.1 Motivation of this work

In recent years, the utilization of drones in illegal settings has
significantly increased, exploiting the lack of stringent regulations and
unrestricted usage. This presents a formidable challenge for multinational
corporations and private owners who must address the detection of these
unauthorized drone activities as a matter of utmost importance. Currently, the
prevailing approach involves hiring private security personnel, but this
manual process is both costly and often ineffective.
To tackle this challenge, there is a pressing need to automate the detection
process through the utilization of AI algorithms and advanced camera systems.
However, a significant gap exists in implementing deep learning software onto
existing cameras and empowering them with the capability to accurately track
and differentiate drones from other aerial objects in real-time. Bridging this
gap would yield more efficient detection methods and facilitate the
development of a detection-based alert system that seamlessly integrates into
a centralized security framework.

###  1.2 Research Contributions

The research contributions of this paper are given below:

  1. 1.

In this paper we have proposed a validation based, soft computing inspired
drone detection scheme VBSF-TLD.

  2. 2.

A generalised algorithm for the proposed VBSF-TLD scheme has been envisioned
and formulated.

  3. 3.

The practical effectiveness of the proposed VBSF-TLD scheme has been conducted
on a curated dataset collected from benchmark resources.

  4. 4.

The loss, accuracy, ROC curves and performance metrics of the VBSF-TLD scheme
has been calculated to measure its detection capability.

##  2 Related Work

In the present era, extensive research is being conducted to explore the use
of computer vision libraries in the detection of moving objects during live
feed deployment stages. This chapter reviews some of the significant existing
work in this field, including state-of-the-art papers and datasets used for
evaluating performance metrics. While a considerable amount of work has been
done on the detection of drones using non-visual extraction methods such as
radars and artificial neural networks [11][12][13], relatively less emphasis
has been placed on visually identifying drones in images using machine
learning techniques with learned features. Firstly, all the papers reviewed in
this chapter have either employed their own extracted data or utilized one of
the three publicly available datasets. One of these datasets is the Drone vs
Bird Dataset [14], which presents a challenge in differentiating drones from
birds. It consists of five videos comprising a total of 2727 frames with a
resolution of 1920 × 1080 pixels. Another dataset, the UAV Project UAV dataset
[15], aims to address the scarcity of comprehensive UAV datasets. It is
derived from 10 hours of raw videos, encompassing 80000 frames annotated with
bounding boxes. This dataset stands out for its meticulousness and
comprehensiveness, as it does not contain any synthetic data. Lastly, to
differentiate drones from airplanes, several papers have utilized an airplane
dataset [16]. This dataset consists of 10,200 images featuring 102 different
variants of aircraft. Each image is labeled and annotated, making it a
valuable resource for researchers working on drone detection.

Samadzadegan et al. [17] propose a deep learning approach for efficient drone
detection and recognition. They utilize the CSPDarknet53 feature extraction
network and employ the Intersection over Union (IoU) loss function to
differentiate between drones and birds. Their method successfully detects and
distinguishes between two types of drones, while accurately differentiating
them from birds. Al-Qubaydhi et al. [18] implement an optimized version of
YOLO (YOLOv5) to detect drones in videos with varying contrasts, including low
contrast scenarios. Their dataset comprises drone images with diverse
backgrounds, such as water, buildings, trees, and humans.

Wang et al. [19] present a fast and cost-effective drone detection system
using video images from static cameras. They employ temporal median background
subtraction to identify moving objects in the video and extract global Fourier
descriptors and local HOG features. These features are then used in an SVM
classifier for classification and recognition. Xun et al. [20] develop a drone
surveillance system using the YOLOv3 model with pre-trained weights. The model
is trained on a custom dataset and validated in real-time using an NVIDIA
Jetson TX2 computing device.

Shi et al. [21] propose a drone detection framework that utilizes three models
- YOLOv4, YOLOv3, and SSD (Single-Shot-Detector) - with a CSPDarknet53
backbone network structure for real-time drone detection. These models are
trained and tested on an augmented dataset that includes internet-collected
images as well as their own collected images. A state-of-the-art paper [22]
introduces the use of a CNN model combined with a Harr feature cascade
classifier for drone detection. The research sets a benchmark in this
subdomain by training the network covertly with separate drone identification
and detection modules. The achieved identification accuracy is 91.6%, while
the detection accuracy reaches 89% over a manually gathered dataset. The Adam
optimizer is employed in training the network.

##  3 Proposed Methodology

###  3.1 Proposed system process flow

The proposed workflow, as illustrated in Algorithm 1 and the architecture
given in Figure2, outlines the steps involved in creating an alarm detection
system for identifying drones in the airspace. The system utilizes various
components, including a CCTV camera connected to a computing server, an
AlexNet Background Subtractor, a GAN-based Super Resolution Module, and a
Transfer Learning Drone Detection Model (FastRCNN ). The desired output is a
reliable drone detection system that triggers an alert when drones are
detected.

Figure 1: Process Flow of Proposed VBSF-TLD Scheme. Algorithm 1 Drone
Detection System

Input: A CCTV camera that is connected to a compting server,
An AlexNet Background Subtractor,
A GAN Based Super Resolution Module,
A Transfer Learning Drone Detection Model (FastRCNN)
Output: An alarm detection system, that detects drones in the air space

1: Set the system to run for a total duration of 30 minutes.

2: for $i=1$ to $10$ do

3: Set the current time as the starting time.

4: while current time is less than 10 minutes after the starting time do

5: Extract image frames from the installed CCTV camera.

6: Calculate the brightness of the extracted image using the alpha channel.

7: if brightness is below the threshold then

8: Apply night vision grayscale conversion to the image.

9: Apply image super-resolution using a GAN-based enhancing technique.

10: Perform denoising and dehazing on the image to increase object clarity.

11: Apply pretrained UNET object detection and background subtraction module
to remove the background and retain the foreground objects.

12: Use the transfer learning-based CNN model (FastRCNN) to detect drones.

13: Validate the results by performing Intersection over Union (IoU)
validation with the subsequent frame.

14: if detection is consistent then

15: Trigger the IoT-based Alert System for drone detection.

16: else

17: Move to the next frame.

18: end if

19: else

20: Skip to the next frame.

21: end if

22: Update the current time.

23: end while

24: Wait for 30 minutes before starting the loop again.

25: end for

###  3.2 Data Collection and Augmentation

For the data acquisition part, we collected samples of aerial objects from
available datasets, as well as custom-collected videos from various sources
such as documentaries, vlogs, and movies. We collected two broad types of
videos. The first type consists of videos in which drones and quadcopters are
being flown, with the camera remaining static to mimic the type of camera that
will be present in our project. The second type includes various videos of
aerial objects like birds and airplanes, which will help the model better
differentiate drones from other aerial objects. Our dataset includes
references from papers [14][15][16].

Using frame extraction , we obtained 650 frames of drone footage and 800
frames of normal aerial objects from the existing dataset in a usable format.
In addition to this, we curated our dataset by employing web scraping
techniques and searching for images in blogs, reviews, Kaggle datasets, and
manually collecting videos and images from various sources, including
documentary blogs, movies, and commercials, over a period of one month. We
then carefully screened and performed a manual annotation process on this new
data, resulting in the creation of our proprietary dataset. This dataset
consists of over 2800 samples, including 1350 samples of drones and
quadcopters, and 1450 samples of real objects. Our dataset is highly diverse,
including drones and quadcopters from multiple brands, homemade variations,
and commercial drone delivery vehicles, as well as airplanes, birds,
helicopters, and balloons as representative objects.

Finally, we performed thorough data augmentation to enhance training and
generate new data. This involved modifying the images by removing noise, haze,
rain, and fog. We also adjusted the brightness and varied the light
conditions. Furthermore, we applied filtering techniques to enhance or remove
specific color bands. Custom cropping of the images was performed to select
specific regions, and flipping, rotating, and scaling techniques were applied
to account for drone positioning and create variations in the dataset.

Figure 2: Results of Data Augmentation: (Left) Original Image, (Right)
Augmented Image

###  3.3 ESRGAN-based Super Resolution Module

n order to further enhance the quality of the training dataset, we utilized an
Enhanced Super-Resolution Generative Adversarial Network (ESRGAN). This
advanced technique improved the dataset by augmenting the images and
effectively eliminating any existing noise, resulting in remarkable
improvements in clarity and overall quality. ESRGAN builds upon the ResNet-
style architecture of SRGAN, but with a notable enhancement: it replaces the
residual block with the Residual-in-Residual Dense Block. Through an
adversarial training process, ESRGAN incorporates both a generator network and
a discriminator network. The generator network’s objective is to generate
high-resolution representations of low-resolution input images that closely
resemble the original low-resolution images. Simultaneously, the discriminator
network is trained to distinguish between artificially generated high-
resolution images and genuine high-resolution photographs. As the training
progresses iteratively, the discriminator network becomes increasingly adept
at recognizing the generated images, while the generator network learns to
produce higher quality and more realistic high-resolution images. Our findings
indicate that ESRGAN surpasses Super Resolution GAN (SRGAN) in terms of both
accuracy and time complexity, establishing it as a significantly superior
approach.

###  3.4 Background Subtraction Module

To perform background subtraction of drone images a pre-trained U-Net [23]
model was used. Initially, the U-Net model was loaded and pre-trained weights
were downloaded, leveraging the transfer learning paradigm to reduce training
time. The U-Net architecture consists of an encoder and a decoder. The encoder
gradually downsampled the input image to capture image-level features, while
the decoder gradually upsampled the features to generate a segmentation mask.
This segmentation mask could then be overlapped with the original image to
remove the background. Subsequently, a dataset of drone images was collected
and labelled as either foreground or background, where the background
represented areas of the image without the drone. The U-Net model was fine-
tuned on this labelled dataset using a Stochastic Gradient Descent optimizer
and a binary cross-entropy loss function, for the updating of model weights.
Once the model was trained, it was employed to perform background subtraction
on new drone images. Each image was passed through the model, and the
foreground pixels were extracted. The resulting foreground pixels represented
the drone, while the remaining background pixels corresponded to the scene
behind the drone, as indicated by the generated segmentation mask. This
segmentation assists in the effective tracking and monitoring of the drone’s
movements.

###  3.5 FastRCNN-based Object Detection Model

We utilized the FastRCNN [24] model, a highly effective approach for object
detection, in the development of our object detection model. The FastRCNN
model employs selective search to generate object proposals. These proposals
are then fed into a pre-trained convolutional neural network, specifically
VGG19, to extract features. The extracted features are used for classifying
the proposals into either a drone or a non-drone object. Here, we froze all
layers except the last two. This freezing prevents these layers from being
updated during the training process, allowing the model to retain the
knowledge captured by the pre-trained convolutional neural network. Finally,
we added a dense layer for binary sigmoid-based classification. This
additional layer enables the model to assign a probability score to each
input, indicating the likelihood of it being a drone or a non-drone object.
The sigmoid activation function ensures that the output falls within the range
of 0 to 1, representing the probability of being a drone. To optimize the
performance of our FastRCNN model for drone detection, we employed various
techniques. Firstly, we fine-tuned the model on our drone dataset by adjusting
hyperparameters, including learning rate and regularization parameters. To
mitigate the risk of overfitting, which occurs when the model performs well on
training data but poorly on new data, we incorporated additional dropout and
batch normalization layers. Dropout randomly drops out some neurons during
training, acting as a form of regularization. Batch normalization normalizes
the input to each layer, promoting stable gradient flow and faster training.
We experimented with different dropout rates and batch normalization
parameters to identify the optimal combination that reduced overfitting and
improved the model’s validation accuracy.

###  3.6 Intersection over Union Validation Module

To validate our results, we implemented a dedicated section aimed at assessing
the accuracy of the bounding box predictions generated by our tracking
algorithm. This section served as an external module, separate from the
training process, focusing solely on evaluating the performance of our
algorithm. To measure accuracy, we used the concept of the area of
intersection, which calculates the overlap between the predicted bounding box
and the ground truth bounding box. By calculating the ratio of the
intersection area to the union area, known as the Intersection over Union
(IoU), we obtained a measure of accuracy.

To determine a threshold for successful detection, we set it at 90%. If the
IoU value for a specific frame exceeded this threshold, it indicated a highly
accurate prediction with a significant overlap between the predicted and
ground truth bounding boxes. On the other hand, if the IoU value fell below
the threshold, it suggested a less accurate prediction with limited overlap or
a potential false positive. We chose the 90% threshold based on our
application’s specific requirements, aiming to balance between false positives
and false negatives.

To evaluate the algorithm’s performance, we analyzed the percentage of frames
where the predicted bounding boxes met or exceeded the 90% IoU threshold. This
allowed us to determine the overall accuracy and reliability of the tracking
algorithm. Additionally, we visually inspected the overlap between the
predicted and ground truth bounding boxes in these frames to verify the
correctness of the detections. This visual inspection provided further
assurance and qualitative assessment of the algorithm’s ability to accurately
track the drone’s bounding box.

###  3.7 Soft Computing-Inspired Particle Swarm Optimization

The research paper presents a novel approach for drone detection, leveraging a
soft computing-inspired optimization function based on Particle Swarm
Optimization (PSO) [25]. Traditional approaches often struggle with the
uncertainties and complexities inherent in drone detection tasks. To address
this, the proposed method incorporates PSO, a nature-inspired optimization
algorithm that mimics the collective behavior of a swarm of particles. By
integrating the PSO optimizer into the FastRCNN model, the loss function is
dynamically optimized, allowing the model to adaptively adjust its parameters
during training. The soft computing-inspired loss function considers the
localization accuracy, object confidence, and class probabilities, aiming to
enhance the model’s performance in detecting drones accurately. The PSO
algorithm works principally on these equations:

Updation of Particle Velocity:

$v_{ij}(t+1)=\omega\cdot v_{ij}(t)+c_{1}\cdot
r_{1}\cdot(pbest_{ij}(t)-x_{ij}(t))+c_{2}\cdot
r_{2}\cdot(gbest_{j}(t)-x_{ij}(t))$ (1)

where $v_{ij}(t+1)$ is the updated velocity of particle $i$ in dimension $j$
at time $t+1$, $\omega$ is the inertia weight, $v_{ij}(t)$ is the current
velocity of particle $i$ in dimension $j$ at time $t$, $c_{1}$ and $c_{2}$ are
the cognitive and social acceleration coefficients, respectively, $r_{1}$ and
$r_{2}$ are random numbers between 0 and 1, $pbest_{ij}(t)$ is the best
position found by particle $i$ in dimension $j$ up to time $t$, and
$gbest_{j}(t)$ is the best position found globally in dimension $j$ up to time
$t$.

Updation of Particle Position:

$x_{ij}(t+1)=x_{ij}(t)+v_{ij}(t+1)$ (2)

where $x_{ij}(t+1)$ is the updated position of particle $i$ in dimension $j$
at time $t+1$, and $v_{ij}(t+1)$ is the updated velocity of particle $i$ in
dimension $j$ at time $t+1$.

These equations are the main update rules of Particle Swarm Optimization,
where each particle’s velocity is updated based on its previous velocity, the
best position it has achieved (pbest), and the best position achieved globally
(gbest). The updated velocity is then used to update the particle’s position,
allowing it to effeciently explore the search space.

##  4 Practical Implementation

This section provides practical implementation details for the proposed VBSF-
TLD, including information on the hardware and software employed. Our hardware
setup consisted of a processor featuring 2 X Intel(R) Xeon(R) with a clock
speed of 2.20GHz, along with 12 GB of RAM and a Nvidia Tesla T4 GPU. The
training was conducted on the Google Colab platform, utilizing the Ubuntu
18.04.5 LTS platform for simulation purposes.

For the implementation of our scheme, we utilized Python 3.8 as the
programming language, along with the Tensorflow library with Keras API. The
model was trained and validated on the collected dataset, which was
partitioned accordingly. We employed K4 cross-validation, dividing the dataset
into four equal folds. Each fold was used to train and test the model,
resulting in an average accuracy assessment. To compile the model, we utilized
the PSO (Particle Swarm Optimization) optimizer and binary cross-entropy loss
function, training the model for 50 epochs. Throughout the training process,
we closely monitored various performance metrics, including accuracy, loss,
and validation accuracy, ensuring that the model was learning effectively
without overfitting to the training data.

Table 1 presents a summary of the performance metrics attained by the proposed
VBSF-TLD, including accuracy, recall, precision, and F1-score.

Table 1: Performance of the proposed VBSF-TLD Scheme Accuracy |  Precision |  Recall |  F1-Score
---|---|---|---
91.36% |  89.39% |  92.58% |  90.96%

Figure 3 illustrates the accuracy, while Figure4 visualizes the loss during
the training and validation process, facilitating a clear comprehension of the
VBSF-TLD drone detection scheme.

Figure 3: Accuracy curve of the proposed VBSF-TLD Figure 4: Loss curve of the
proposed VBSF-TLD

##  5 Conclusion

In this paper, we have presented a novel approach for detecting drones using
transfer learning and background subtraction techniques, which is automated
and cost-effective. Our results demonstrate the effectiveness of this approach
in achieving accurate and precise drone detection. The proposed model
incorporates rigorous processing techniques, including a GAN-based approach
and background subtraction, eliminating the need for specialized hardware.
This capability allows us to enhance image quality, removing moving noise
caused by varying atmospheric conditions in practical scenarios, without
requiring substantial investments in cameras and filters. By leveraging these
advantages, we believe that our proposed Validation-Based Approach for Soft
Computing-Inspired Transfer Learning in Drone Detection Scheme (VBSF-TLD)
holds significant potential for enhancing security and safety against
unauthorized drone flights in various day-to-day applications.

In future, we would like to extend proposed VBSF-TLD by incorporating advanced
machine learning techniques such as ensemble deep learning and reinforcement
learning. This will further enhance the accuracy and efficiency of our
approach, enabling even more robust drone detection in diverse environments.

## References

  * [1] Wulfovich, S., Rivas, H., and Matabuena, P. Drones in healthcare. Digital Health: Scaling Healthcare to the World, 159-168, 2018.
  * [2] Floreano, Dario, and Robert J. Wood. ”Science, technology and the future of small autonomous drones.” nature 521.7553, 2015.
  * [3] Boccadoro, P., Striccoli, D. and Grieco, L.A. An extensive survey on the Internet of Drones. Ad Hoc Networks, 122, 2021.
  * [4] Internet of drones security: Derhab, A., Cheikhrouhou, O., Allouch, A., Koubaa, A., Qureshi, B., Ferrag, M.A., Maglaras, L. and Khan, F.A. Internet of Drones Security: Taxonomies, Open Issues, and Future Directions. Vehicular Communications, p.100552, 2022.
  * [5] Cavoukian, Ann. Privacy and drones: Unmanned aerial vehicles. Ontario: Information and Privacy Commissioner of Ontario, Canada, 2012.
  * [6] Bishop, Christopher M., and Nasser M. Nasrabadi. Pattern recognition and machine learning. Vol. 4. No. 4. New York: Springer, 2006.
  * [7] Jordan, Michael I., and Tom M. Mitchell. ”Machine learning: Trends, perspectives, and prospects.” Science 349.6245, 2015.
  * [8] Gao, J., Yang, Y., Lin, P., and Park, D. S. Computer vision in healthcare applications. Journal of healthcare engineering, 2018.
  * [9] Cazzato D, Cimarelli C, Sanchez-Lopez JL, Voos H, Leo M. A Survey of Computer Vision Methods for 2D Object Detection from Unmanned Aerial Vehicles. Journal of Imaging, 2020.
  * [10] Jindal, Vishesh, Shailendra Narayan Singh, and Soumya Suvra Khan. ”Facial Recognition with Computer Vision.” Machine Intelligence and Data Science Applications: Proceedings of MIDAS 2021. Singapore: Springer Nature Singapore, 2022. 313-330.
  * [11] N.M. Jahangir and C. Baker, ”Robust detection of micro-UAS drones with L-band 3-D holographic radar,” in Proc. IEEE Sensor Signal Process. Defence (SSPD), Sep. 2016, pp. 1–5.
  * [12] B. Torvik, K. E. Olsen, and H. Griffiths, ”Classification of birds and UAVs based on radar polarimetry,” IEEE Geosci. Remote Sens. Lett., vol. 13, no. 9, pp. 1305–1309, Sep. 2016.
  * [13] D. S. Zrnić and A. V. Ryzhkov, ”Observations of insects and birds with a polarimetric radar,” IEEE Trans. Geosci. Remote Sens., vol. 36, no. 2, pp. 661–668, Mar. 1998.
  * [14] A. Coluccia et al., ”Drone-vs-Bird Detection Challenge at IEEE AVSS2021,” 2021 17th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), 2021,pp. 1-8.
  * [15] D. Du, Y. Qi, H.g Yu, Y. Yang, K. Duan, G. Li, W.g Zhang, Q. Huang, Q. Tian, ” The Unmanned Aerial Vehicle Benchmark: Object Detection and Tracking”, European Conference on Computer Vision (ECCV), 2018.
  * [16] S. Maji, J. Kannala, E. Rahtu, M. Blaschko, A. Vedaldi, (2013). Fine-Grained Visual Classification of Aircraft [Techreport].
  * [17] F. Samadzadegan, F. Dadrass Javan, F. Ashtari Mahini, M. Gholamshahi, Detection and recognition of drones based on a deep convolutional neural network using visible imagery, Aerospace 9, 31, 2022.
  * [18] N. Al-Qubaydhi, A. Alenezi, T. Alanazi, A. Senyor, N. Alanezi, B. Alotaibi, M. Alotaibi, A. Razaque, A. A. Abdelhamid, A. Alotaibi, Detection of unauthorized unmanned aerial vehicles using yolov5 and transfer learning, Electronics 11, 2669, 2022.
  * [19] Z. Wang, L. Qi, Y. Tie, Y. Ding, Y. Bai, Drone detection based on fd-hog descriptor, in: 2018 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2018.
  * [20] D. T. Wei Xun, Y. L. Lim, S. Srigrarom, Drone detection using yolov3 with transfer learning on nvidia jetson tx2, in: 2021 Second International Symposium on Instrumentation, Control, Artificial Intelligence, and Robotics (ICA-SYMP), 2021.
  * [21] Q. Shi, J. Li, Objects detection of uav for anti-uav based on yolov4, in: 2020 IEEE 2nd International Conference on Civil Aviation Safety and Information Technology (ICCASIT, 2020.
  * [22] D. Lee, W. G. La, and H. Kim, “Drone detection and identification system using artificial intelligence,” in Proc. Int. Conf. Inf. Commun. Technol. Converg. (ICTC), Oct. 2018.
  * [23] O. Ronneberger, F. Philipp, and T. Brox. ”U-net: Convolutional networks for biomedical image segmentation.” Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18. Springer International Publishing, 2015.
  * [24] R. Girshick, ”Fast R-CNN,” 2015 IEEE International Conference on Computer Vision (ICCV), Santiago, Chile, pp. 1440-1448, doi: 10.1109/ICCV.2015.169, 2015.
  * [25] Kennedy, James, and Russell Eberhart. ”Particle swarm optimization.” Proceedings of ICNN’95-international conference on neural networks. Vol. 4. IEEE, 1995.


# An Approach to Intelligent Pneumonia Detection and Integration

Bonaventure F. P. Dossou
Jacobs University Bremen
<EMAIL_ADDRESS>
Alena Iureva
Jacobs University Bremen
<EMAIL_ADDRESS>
Sayali R. Rajhans
Jacobs University Bremen
<EMAIL_ADDRESS>
Vamsi Sai Pidikiti
Jacobs University Bremen
<EMAIL_ADDRESS>
###### Abstract

Each year, over 2.5 million people, most of them in developed countries, die
from pneumonia [1]. Since many studies have proved pneumonia is successfully
treatable when timely and correctly diagnosed, many of diagnosis aids have
been developed, with AI-based methods achieving high accuracies [2]. However,
currently, the usage of AI in pneumonia detection is limited, in particular,
due to challenges in generalizing a locally achieved result. In this report,
we propose a roadmap for creating and integrating a system that attempts to
solve this challenge. We also address various technical, legal, ethical, and
logistical issues, with a blueprint of possible solutions.

##  1 Motivation

According to the World Health Organization (WHO), pneumonia is a treatable
disease that causes millions of people to die from lack of access to its
prevention and treatment, including over 800 thousand children under five
every year. The problem is perpetuated by mistakes in diagnosis, causing
interventions to be too late and leading to death. Caused by bacteria or
viruses, pneumonia is worse for populations harmed by pollution and can be
prevented by vaccination or treated with antibiotics [3]. One of the most
popular ways to detect pneumonia is Chest X-ray (CXR); others include blood
tests, pulse oximetry, and Chest CT scans [4].

The technological progress and the need to address the shortage of medical
opportunities in some geographical regions have recently given growth to
various telehealth solutions, including teleradiology. Besides, AI is
increasingly being used hand-in-hand with telehealth technologies to reduce
the workload on healthcare workers. The tasks that it attempts to perform
include patient monitoring, intelligent assistance, diagnostics, remote
collaboration, and self-diagnosis tools, including health trackers [5]. By
2017, 86% of major healthcare companies used some AI in their operations, thus
reducing operational costs by 10% [6].

In general, studies suggest that AI-based diagnosis systems, in particular,
could assist clinicians by achieving fast, reliable data interpretation,
improve and streamline workflow for health systems, achieving faster and
seamless processing [7], reduce medical errors ([7], [8]), help confirm a
diagnosis or clarify it [9]. Besides, certain implementations can empower
patients by providing them more in-depth but understandable information about
their health.

While there have been some progress in automated pneumonia diagnosis by CXR
using Deep Convolutional Neural Networks (CNNs), as we will describe in
section 3.2, there are multiple challenges to tackle before the resulting
models become genuinely production-ready. Some of them are related to
computational power, but the most considerable technical challenge is
insufficient data — often caused by the fact that experimental systems are
often developed and tested within single hospital’s walls. To build a
diagnosis system applicable at scale, one needs a dataset diverse by
geography, demographic characteristics, scanner brand, and other variables
[10]. Therefore, we find it appropriate to try and address this issue in this
work.

Ultimately, if successfully implemented, an automated pneumonia diagnosis
system could save many lives by saving radiologists’ time. CXR is a relatively
cheap and fast diagnostic method, with rising demand, yet two-thirds of the
world population do not have access to radiologists [11]. Nevertheless, even
the remaining third gets 1.44 billion CXRs annually [12]. Therefore, it is
clear that even a 10% improvement in CXR reporting speed, let alone expansion
of the access, could add up to tens and hundreds of thousands of saved lives
annually.

##  2 Background and Related Work

As there is by now much research dedicated to AI-based pneumonia detection by
CXR, let’s take a look at a few examples.

  * •

Rajpurkar et. al., in their paper ”CheXNet: Radiologist-Level Pneumonia
Detection on Chest X-Rays with Deep Learning”, using the ChestX-ray14 dataset
released by (Wang et al., 2017) which contains 112,120 frontal-view X-ray
images of 30,805 unique patients, achieved AUC of 76,80% with a F1-Score of
43.50%. Their model performed better than the models proposed respectively by
(Wang et al., 2017) and (Yao et al., 2017) [13].

  * •

Researchers from India compared different combinations of CNNs as feature
extractors and simple ML models as classifiers on a set of 112k CXR images
resized to 224x224 and found the combination of DenseNet-169 + Support Vector
Machine (SVM) to be the best within the scope of their study, achieving AUC of
80% [14].

Overall, a systematic literature review on intelligent pneumonia detection
methods [15], points that CXRs are often subject to complex preprocessing,
including morphological operation, edge detection, and Gaussian filters. The
resulting features are used in classification via Neural Networks (NNs), SVM,
Random Forest Classifier (RFC) or another model or classifier. As for NNs
architectures, many, including VGGNet ([13], [14], [16]), AlexNet, LeNet,
GoogleNet [16], ResNet ([14], [16]), DenseNet, and Xception [14], were tried,
with decent results. But it worths emphasizing that models with too many
layers may be impractical due to excessive computation time. Performance
metrics include accuracy, precision, recall, F1 score, and AUC [15], yet for
medical applications, recall is often the most critical metric due to the dire
consequences of false negatives in diagnostics [2].

##  3 Methodology

###  3.1 Application architecture

For the sake of applicability in under-served areas, the solution has to
fulfill the following requirements:

  * •

Can function under low network speeds efficiently, even for dial-up (up to 56
kbit/s), which can still be the case in rural areas of some countries [17].

  * •

Can function autonomously if the internet connection is off

  * •

Does not require extensive network usage on the client-side to reduce costs

  * •

Is fast enough to reduce the time spent to evaluate a CXR (which usually takes
up to 15 minutes) [18].

  * •

Can provide the system (server-side) with an ongoing supply of additional data
to increase performance

Figure 1:  Application Architecture and Workflow Diagram

The Figure 1 presents the workflow diagram of the application. Here are some
key factors it worths knowing:

  * •

The client interacts with the user (presumably a radiologist/technician) in a
simple (and single) way: the user uploads a CXR and receives the probability
of the picture indicating pneumonia and the model’s binary verdict. The user
will also be able to mark whether the diagnosis was confirmed or not to gather
the data.

  * •

The CXR is preprocessed on the client, thus reducing the picture size to
4-16KB, uploadable on a server within a few seconds even with dial-up,
assuming 8-bit color depth grayscale 128x128 image.

  * •

Usually, a prediction request is sent to the server. Because the response is
two numbers with labels, its size is negligible in comparison to headers. If
the request was unsuccessful or the internet connection is not available,
prediction happens locally, and the preprocessed picture is put to the picture
cache to send later.

  * •

While neural networks can be large, for example being 240MB for AlexNet, the
combination of Pruning, Quantization, and Huffman encoding can reduce these
numbers by 30-50x depending on the specific architecture and weights while
speeding up 3-4x layerwise and retaining accuracy [19]. This finding means
that AlexNet would reduce to 6.9MB, downloadable in 16 minutes at 56 Kbit/sec
(long, but bearable) — and because we initially propose a simpler model, the
actual time would be even less.

  * •

The full (uncompressed) network would run on the server, and the compressed
version of the most recent network could be downloaded for autonomous
processing. The update will only happen if the hash sum of the client’s
current model is different from the hash sum of the newest model.

  * •

The overall weekly network usage, assuming 100 scans a day, a weekly update,
1-kilobyte headers, and 5MB compressed NN size, would be up to
100*(17+1)*7+5*1024=17720KB, or under 18MB, making it doable even for remote
rural areas in developing countries.

  * •

The processed pictures in the database would be split into already used in the
model, and the update batch material, and a public and private section. The
section can be chosen depending on the specific contractor preferences
regarding sharing the anonymized personal data. The public section is to form
publicly available datasets for comparison of AI solutions, while private only
for model training.

  * •

Once in a while, the model would be subject to a transfer learning process
with new data and replace the older model if the newer one performs better.

###  3.2 Data Processing, Model’s Architecture and Training

For the model’s creation, we illustrate the process with a particular Kaggle
dataset of 5856 images [20].

####  3.2.1 Data Processing

Each picture of the dataset is a grayscale picture with resolution 1152x760.
To every image, we apply the gamma correction, resulting in correcting the
brightness of input image. This is done by using a non linear transformation
between the input values and the mapped output values:

$O=(\frac{I}{255})^{\gamma}\times 255$

Figure 2:  Transformation of a chest X-ray from a patient suffering from
Pneumonia, with $\gamma=2.8$

Figure 3:  Transformation of a chest X-ray from a patient suffering from
Pneumonia, with $\gamma=2.4$

Figure 4:  Transformation of a chest X-ray from a patient suffering from
Pneumonia, with $\gamma=2.1$

where $O$ is the output image and $I$, the input image. Performing the Gamma
correction, help our model to perform better. Figures 2, 3 and 4 show an
example of the gamma correction, with $\gamma=2.8,\gamma=2.4$, and
$\gamma=2.1$. In practise, the larger $\gamma$, the dimmer is the picture.
Lower values of $\gamma$ make images brighter and doesn’t improve the
performance of our model. Further, for ease of processing, every image has
been to 128x128. Along the tensor of training features, the scale the raw
pixel intensities has been mapped to the range [0, 1]. As far as the training
labels are concerned, $Normal$ has been mapped to 0 and $Pneumonia$ to 1.

####  3.2.2 Undersampling and Oversampling

During the testing phase of our model, we have notice that the model almost
perfectly classifies $Pneumonia$ but fails at classifying $Normal$ and
predicts it in majority as $Pneumonia$. The dataset contains 5232 unique
pictures, with only 25,75% (1349) pictures of $Normal$. The gap is huge, and
hence the model tends to more likely predict everything as $Pneumonia$. To
overcome this barrier, we have oversampled the minority class $Normal$ and
undersampled the majority class $Pneumonia$. Oversampling is defined as adding
more copies of the minority class, along the dataset. Undersampled is defined
as the opposite of oversampling. To perform $oversampling$ and
$undersampling$, We have splitted our general data into test and train sets.
Otherwise, the exact same observations could be present both in the test and
train sets. This will make our model to memorize specific samples, and then
cause overfitting and poor generalization to the test data.

####  3.2.3 Data Augmentation

Because there are so few samples initially, it is reasonable to perform data
augmentation. This has been done using the ImageDataGenerator object of the
deep learning framework Keras, with the parameters stated in Table 1,
resulting in 40992 training samples.

Parameters |  Values
---|---
rotation_range |  30
width_shift range |  0.2
height_shift range |  0.2
shear_range |  0.2
zoom_range |  0.2
horizontal_flip |  True
vertical_flip |  True
fill_mode |  nearest
Table 1:  Parameters of the ImageDataGenerator object for Data Augmentation

####  3.2.4 Model’s Architecture and Training

We opted for a very simple CNNs model, with relatively small number of layers.
As future work and improvement, exploring Unet [21] could be an option. The
architecture of our model is described in Picture 5. For the training, we set
the batch size to 64, the learning rate to 0.001 and the training epochs,
initially at 500. For the loss function, we choose categorical entropy as the
loss function, and as optimizer, we opted tried Stochastic Gradient Descent
(SGD) and Adam, with a decay parameter set to 0.9. A callback has been also
implemented, to evaluate the model after each epoch so that the weights are
only saved when the current epoch’s validation loss, is less than the
validation loss of the previous one, with patience parameter set to 100.
Finally, to judge the performance, we use Accuracy, F1 and Recall metrics.

Figure 5:  Model’s Architecture Figure 6:  Model’s Confusion Matrix

##  4 Initial Results and Findings

Our best result is achieved with Adam as optimizer, with an accuraccy of
prediction of 91,04%, and AUC of 88,04%, on our test dataset, made of 624
unique samples. The Table 2 presents the classification report of our model.
The Figure 7 presents the confusion of the classification task, performed by
our model. We can from the confusion matrix, notice that the Pneumonia has
been almost perfectly detected. Its is however not completely the case for
$Normal$, for which the model has predicted 79% of the samples correctly. This
means that there is still headroom for improvements and perfection.

We want to end this section of our findings and results by sharing pairs of
inputs and outputs (Figures 7 and 8), with the heatmaps, indicating the parts
of the inputs that helped our model to classify correctly.

Figure 7:  Heatmap Activations for $Normal$ class Detection

Figure 8:  Heatmap Activations for $Pneumonia$ class Detection

| Precision | Recall | F1-Score | Support
---|---|---|---|---
Normal | 95 | 79 | 86 | 234
Pneumonia | 88 | 97 | 93 | 390
accuracy |  |  | 90 | 624
macro avg | 92 | 88 | 89 | 624
weighted avg | 91 | 90 | 90 | 624

Table 2: Classification Report of our Model

##  5 Technical challenges

####  5.0.1 Diversity of data

As mentioned previously, to achieve broad applicability, the data should be
diverse and representative in many respects. Under-representation of samples
may cause the system to be less accurate for some patients, leading to
increase in misdiagnosis. Diversity includes the hospital source, geographic
location, demographic characteristics of patients like age, sex, ethnicity,
income level, the X-ray scanner brand, and many others [10]. To remedy this
issue, one has to solve the problem of acquisition — complicated by data
collection issues below. The representation problem is partially solved by
selective oversampling and data augmentation, particularly by representative
data collection strategies.

To help track and improve data diversity, the solution’s database can be
augmented by diversity variables listed above for every CXR. Another
improvement may be made by extracting a diverse subset from a large dataset
for another iteration of model training [22].

Nevertheless, this challenge is never fully resolved, and significant
improvements are only possible with increasing, possibly international reach
and big data collection and cannot be fully tackled from day one based on a
small set of open-source datasets.

####  5.0.2 Intrinsic ML biases

A lot of subtle mistakes are made by ML engineers every day throughout their
work, which can be unnoticeable initially but make a considerable difference
large-scale. These include dataset shift, unintended discriminatory bias, or
accidental fitting of confounders [23]. Biases entering models by mistake or
due to sloppy design affect the right to equal treatment regardless of
protected characteristics and tend to affect economically vulnerable
populations significantly [24].

Similarly, as scientific papers are subject to peer review and code of
software engineers to code review, open-sourcing most parts of the system can
provide some oversight and reduce the risks. Commentary from independent
experts should be welcome, and an opportunity for comparison to other AI
models can increase the competition even further. An input of vulnerable and
affected populations can also help discover problems previously unseen.

####  5.0.3 Performance metrics clarity

In our setup, the more meaningful metrics in the clinical setting are
different from metrics that we use to optimize the model. An essential task in
medicine is reducing false negatives or improving recall, while false
positives are not that crucial. However, the easiest way to get a recall of 1
is to always detect pneumonia, yet such a model is useless. Because of that,
more holistic measures are typically used, such as the F1 score.

The one thing that can be done quickly is outputting recall and precision for
a current version of the model to the user. Another thing that acknowledges
that precision should not be zero could be a weighted modification of the F1
score, where recall is given more weight. Precision should be decent, but
recall must be high.

####  5.0.4 Privacy and security issues

Any technical solution should include robust security measures, yet it is even
more accurate for those dealing with sensitive medical data. One should be
careful with AI so that the model does not get tampered with via replacement
in MiTM attacks or a newer concept of data diet attacks. Failure of defense
from cyber attacks severely violates patients’ right to privacy, and the risks
increase along with AI usage [24].

There is no easy way to tackle any of it. However, the bare minimum should be
complex measures, including risk assessment, security protocols followed by
involved parties, extensive testing and static analysis during software
development, regular pen-testing, encryption, and security-driven network
management. Besides, data collection from unconfirmed sources should not be
permitted.

####  5.0.5 AI systems comparison transparency

As stated before, it is vital to compare different intelligent systems, yet it
is currently complicated due to the unavailability of data and often different
input formats. With time, given that there are incentives to open-source
datasets and perform independent comparison studies, transparency may
increase, but it is hardly possible to influence the process throughout just
one project significantly.

####  5.0.6 Modern AI’s subject matter unawareness

The use of AI in diagnosis is currently limited due to the models’ general
unawareness of human anatomy and physiology. This fact means it lacks expert
knowledge to make a final decision, making it vital to have a human expert in
using it as a tool [10]. Therefore, it cannot reason on whether the diagnosis
makes sense. While the first steps in knowledge networks are being done,
increasing the system’s independence is beyond this report’s scope.

##  6 Legal and ethical challenges

###  6.1 Data access and privacy regulations

To remedy some of the existing privacy and human rights, extensive personal
data regulations are being developed, EU’s GDPR [25] being one of the most
known legislations. While these laws define a baseline for privacy
preservation, most often, the delineated guidelines are too complex to
implement all at once, especially for a data-intensive product.

For the international targeting, especially considering that we are proposing
the solution most beneficial for developing countries, many of them emerging
democracies with weaker data protections, a reasonable way may be to create a
roadmap of adoption based on a gradual increase of protections [26] and
working on compliance to more robust guidelines for targeting the new
geographic area. At the same time, as possible, storing data primarily in
locations providing more data protections is preferable to avoid problematic
trans-border data transfers. While this approach may seem ethically dubious,
in some cases, the need to ensure numerous people’s survival and health may
temporarily outweigh privacy concerns.

###  6.2 Lobbying for implementation or adoption

To make an impact, widespread collaboration with healthcare officials and non-
profit organizations is necessary. These players make decisions based on many
potential impact points, weighing cost and benefit across many axes.
Therefore, to accelerate the system’s widespread adoption, a convincing case
should be made that the system is significantly beneficial.

It can be done based on the fact that at a small scale, it is possible to
crowdfund or score a grant and implement the solution on an experimental
basis. The further analysis of such experiments will build a ground for
broader adoption in case of success, provided that a clear plan exists. The
analysis may include monetary evaluation, labor analysis, patient outcomes
monitoring, and an overview of intended and unintended consequences.

###  6.3 Implications of AI-caused medical errors

Bias may be discriminative, but medical errors leading to deaths have another
magnitude of responsibility [23]. Depending on how liability is determined,
the whole developer team may be held liable for a fatal mistake. Besides,
accountability is hard to achieve for AI, as the specific decision algorithms
are often unobvious — yet any error essentially violates the right to
effective treatment and, in some cases, right to life [24].

At the project level, higher transparency and participation of medical
specialists can reduce the risks. Risk prevention principles should also be
developed and followed, and all parties informed of intrinsic AI shortcomings.
These measures are far from enough, but more efficient measures should be
implemented on the global, systemic level.

##  7 Implementation challenges

Following the intuition that the more usable the product is, the more it is
used, it is known that usability explains up to 70% of the variance in
purchasing decisions [27]. To facilitate the solution’s broader outreach, it
is essential to wrap it into acceptable UX practices. The interface should be
intuitive and straightforward, and small-cohort interviews with radiologists
and technicians should be conducted in every location to improve the
experience. In our case, good UX is incredibly vital, as it may help reduce
human errors and directly lead to saved lives.

###  7.1 The issue of trust

Lack of trust both among medical professionals and patients may hinder the
adoption of AI-based solutions directly and via the influence of government
decisions [23]. Despite the widespread concerns over lost jobs due to
automation, majorities of people in selected developed countries, like India,
Mexico, and Brazil, keep a high level of trust in both technology in general
[28] and AI in particular [29]. Still, as more affluent countries tend to be
less trusting, we can expect more distrust as countries develop economically.

Moreover, it’s one thing to trust abstract technology and another to trust its
specific application. Concerns may be raised by old-school doctors and
managers and those concerned whether such usage may violate any religious and
spiritual principles. Therefore, it is essential to increase transparency, be
honest about impacts, and educate the system’s direct users to increase trust.
The trust issues in decision-makers can also be overcome via demonstration of
significant material benefits.

###  7.2 Material resources and skills availability

Finally, some locations which would benefit most from our solution currently
lack resources to access it. This may mean lack of internet connection [30],
computers [31], or even electricity [32]. Besides, the staff may not have any
computer skills, which may also hinder progress.

While some usage training may be appropriate, it should not be challenging, so
the user experience should be optimized for maximum simplicity. For this
reason, and also should the unconnected field use be the goal, a dedicated
battery-powered device as a client may be appropriate rather than a computer.
It could also have a possibility of radio transmission to the reception points
to compensate for the lack of internet or use satellite infrastructure,
similarly to GPS devices.

##  8 Acknowledgements

This paper derives from our Big Data Semester project, led and supervised by
the Prof. Dr. Adalbert F.X. Wilhelm. 111 https://www.jacobs-
university.de/directory/wilhelm

##  9 Conclusion

In our work, we show how AI could shape the future of Pneumonia Detection. We
presented our model, performing the detection with 91,04% of prediction’s
accuracy that could be used for early detection. However, as any other
technology, AI is a multiplier for human ingenuity not a replacement for it.
Therefore, in our paper, we also addressed various technical, legal, ethical,
and logistical issues, with a blueprint of possible solutions, to ensure
fairness and availability of the technology for everyone.

## References

  * [1] Our World in Data.  https://ourworldindata.org/pneumonia
  * [2] Kaushik, V. Nayyar, Anand. Kataria, Gaurav. Jain, Rachna.  2020\.  Pneumonia Detection Using Convolutional Neural Networks (CNNs).  471-483. 10.1007/978-981-15-3369-3_36.
  * [3] World Health Organization.  https://www.who.int/health-topics/pneumonia
  * [4] National Heart, Lung and Blood Institute.  https://www.nhlbi.nih.gov/health-topics/pneumonia.
  * [5] Pacis, Danica Mitch M., et al.  2018\.  Trends in Telemedicine Utilizing Artificial Intelligence.  p. 040009. DOI.org (Crossref), doi:10.1063/1.5023979.
  * [6] Healthcare IT News.  https://www.healthcareitnews.com/news/86-healthcare-companies-use-some-form-ai.
  * [7] Topol, Eric J.  High-Performance Medicine: The Convergence of Human and Artificial Intelligence  Nature Medicine, vol. 25, no. 1, Jan. 2019, pp. 44–56. DOI.org (Crossref), doi:10.1038/s41591-018-0300-7.y.
  * [8] Stanford News.  Stanford algorithm can diagnose pneumonia better than radiologists.  https://news.stanford.edu/2017/11/15/algorithm-outperforms-radiologists-diagnosing-pneumonia/
  * [9] Stanford Medicine News.  Artificial intelligence rivals radiologists in screening X-rays for certain diseases.  https://med.stanford.edu/news/all-news/2018/11/ai-outperformed-radiologists-in-screening-x-rays-for-certain-diseases.html.
  * [10] Science.  Artificial intelligence could revolutionize medical care. But don’t trust it to read your x-ray just yet.  https://www.sciencemag.org/news/2019/06/artificial-intelligence-could-revolutionize-medical-care-don-t-trust-it-read-your-x-ray
  * [11] Pan American Health Organization.  World Radiography Day: Two-Thirds of the World’s Population has no Access to Diagnostic Imaging.  https://www.paho.org/hq/index.php?option=com_content&view=article&id=7410:2012-dia-radiografia-dos-tercios-poblacion-mundial-no-tiene-acceso-diagnostico-imagen&Itemid=1926&lang=en
  * [12] Kieran Murphy.  HOW DATA WILL IMPROVE HEALTHCARE WITHOUT ADDING STAFF OR BEDS.  https://www.wipo.int/edocs/pubdocs/en/wipo_pub_gii_2019-chapter8.pdf
  * [13] Pranav R., Jeremy I., Kaylie Z., Brandon Y., Hershel M., Tony D., Daisy D., Aarti B., Robyn L. B., Curtis L., Katie S., Matthew P. L., Andrew Y. Ng.  2017\.  CheXNet: Radiologist-Level Pneumonia Detection on Chest X-Rays with Deep Learning.  https://arxiv.org/abs/1711.05225.
  * [14] D. Varshni, K. Thakral, L. Agarwal, R. Nijhawan and A. Mittal.  2019\.  Pneumonia Detection Using CNN based Feature Extraction.  IEEE International Conference on Electrical, Computer and Communication Technologies (ICECCT), Coimbatore, India, 2019, pp. 1-7, doi: 10.1109/ICECCT.2019.8869364.
  * [15] Khan, W. Zaki, N. Ali, L.  2020\.  Intelligent Pneumonia Identification from Chest X-Rays: A Systematic Literature Review.  Cold Spring Harbor Laboratory. https://doi.org/10.1101/2020.07.09.20150342
  * [16] Militante, S. V., and B. G. Sibbaluca.  Pneumonia Detection Using Convolutional Neural Networks.  International Journal of Scientific & Technology Research 9, no. 04 (2020): 1332-1337.
  * [17] Internet Users in India (2020 – 21) Statistics  https://nanocms.in/internet-users-in-india/.
  * [18] X-ray (Radiography) - Chest  https://www.radiologyinfo.org/en/info.cfm?pg=chestrad.
  * [19] Han, Song, et al.  2016\.  Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding.  http://arxiv.org/abs/1510.00149.
  * [20] Kaggle.  Chest X-Ray Images (Pneumonia).  https://www.kaggle.com/paultimothymooney/chest-xray-pneumonia
  * [21] Ronneberger, O., Fischer, P., Brox, T.  2015\.  U-Net: Convolutional Networks for Biomedical Image Segmentation.  In Lecture Notes in Computer Science (pp. 234–241). Springer International Publishing.  https://doi.org/10.1007/978-3-319-24574-4_28
  * [22] MIT News. Data Diversity  https://news.mit.edu/2016/variety-subsets-large-data-sets-machine-learning-1216.
  * [23] Kelly, C.J., Karthikesalingam, A., Suleyman, M. et al.  Key challenges for delivering clinical impact with artificial intelligence.  BMC Med 17, 195 (2019).  https://doi.org/10.1186/s12916-019-1426-2.
  * [24] Rodrigues, R.  2020\.  Legal and human rights issues of AI: gaps, challenges and vulnerabilities. Journal of Responsible Technology, 100005.  https://doi.org/10.1016/j.jrt.2020.100005.
  * [25] General Data Protection Regulation. GDPR.  https://gdpr-info.eu.
  * [26] CNIL.  https://www.cnil.fr/en/data-protection-around-the-world.
  * [27] UX Collective.  How usability impacts profit  https://uxdesign.cc/the-conversion-usability-framework-3e2068edebbc.
  * [28] Special Report: Trust in Technology.  https://www.edelman.com/sites/g/files/aatuss191/files/2020-02/2020%20Edelman20Trust%20Barometer%20Tech%20Sector%20Report_1.pdf.
  * [29] Statista. Trust in artificial intelligence  https://www.statista.com/statistics/948531/trust-artificial-intelligence-country/.
  * [30] Our world in data.  https://ourworldindata.org/internet
  * [31] Statista. Worldwide Households With Computer.  https://www.statista.com/statistics/748551/worldwide-households-with-computer/.
  * [32] Our world in data.  https://ourworldindata.org/energy-access.


# On the Pythagorean Holes of Certain Graphs

Johan Kok  Tshwane Metropolitan Police Department
City of Tshwane, Republic of South Africa
E-mail<EMAIL_ADDRESS>N. K. Sudev Department of Mathematics
Vidya Academy of Science & Technology
Thalakkottukara, Thrissur - 680501, India.
E-mail<EMAIL_ADDRESS>K. P. Chithra Naduvath Mana, Nandikkara
Thrissur - 680301, India.
E-mail<EMAIL_ADDRESS>
###### Abstract

A primitive hole of a graph $G$ is a cycle of length $3$ in $G$. The number of
primitive holes in a given graph $G$ is called the primitive hole number of
that graph $G$. The primitive degree of a vertex $v$ of a given graph $G$ is
the number of primitive holes incident on the vertex $v$. In this paper, we
introduce the notion of Pythagorean holes of graphs and initiate some
interesting results on Pythagorean holes in general as well as results in
respect of set-graphs and Jaco graphs.

Key Words: Set-graphs, Jaco Graphs, primitive hole, Pythagorean hole,
graphical embodiment of a Pythagorean triple.

Mathematics Subject Classification: 05C07, 05C20, 05C38.

##  1 Introduction

For general notations and concepts in graph theory, we refer to [1], [5] and
[10]. All graphs mentioned in this paper are simple, connected undirected and
finite, unless mentioned otherwise. Note that in the construction of a graph
through steps and if the meaning of degree is clear at a step, the degree of a
vertex $v$ will be denoted $d(v)$. If we refer to degree in the context of a
graph $G$, we will denote it as $d_{G}(v)$.

A hole of a simple connected graph $G$ is a chordless cycle $C_{n}$ , where
$n\in N$, in $G$. A primitive hole of a graph $G$ (see [6]) is a cycle of
length $3$ in $G$. The number of primitive holes in a given graph $G$ is
called the primitive hole number of $G$ and is denoted by $h(G)$.

The primitive degree (see [6]) of a vertex $v$ of a given graph $G$ is the
number of primitive holes incident on the vertex $v$ and the primitive degree
of the vertex $v$ in the graph $G$ is denoted by $d^{p}_{G}(v)$.

The notion of a set-graph has been introduced in [7] as follows.

######  Definition 1.1.

[7] Let $A^{(n)}=\\{a_{1},a_{2},a_{3},\ldots,a_{n}\\},n\in\mathbb{N}$ be a
non-empty set and the $i$-th $s$-element subset of $A^{(n)}$ be denoted by
$A_{s,i}^{(n)}$. Now consider
$\mathcal{S}=\\{A_{s,i}^{(n)}:A_{s,i}^{(n)}\subseteq
A^{(n)},A_{s,i}^{(n)}\neq\emptyset\\}$. The set-graph corresponding to set
$A^{(n)}$, denoted $G_{A^{(n)}}$, is defined to be the graph with
$V(G_{A^{(n)}})=\\{v_{s,i}:A_{s,i}^{(n)}\in\mathcal{S}\\}$ and
$E(G_{A^{(n)}})=\\{v_{s,i}v_{t,j}:~{}A_{s,i}^{(n)}\cap
A_{t,j}^{(n)}\neq\emptyset\\}$, where $s\neq t~{}\text{or}~{}i\neq j$.

The set $A^{(n)}\neq\emptyset$ and if $|A^{(n)}|$ is a singleton, then
$G_{A^{(n)}}$ to be the trivial graph. Hence, we need to consider non-empty,
non-singleton sets for the studies on set-graphs.

It is proved in [7] that any set-graph $G$ has odd number of vertices. An
important property on set-graphs is that the the vertices of a set-graph $G$,
corresponding to the sets of equal cardinality, have the same degree. Also,
the vertices in a set-graph $G$, corresponding to the singleton subsets of
$A^{(n)}$, are pairwise non-adjacent in $G$.

The following is a relevant result on the minimal and maximal degree of
vertices in a set-graph and their relation.

######  Theorem 1.2.

[7] For any vertex $v$ of a set-graph $G=G_{A^{(n)}}$, $2^{n-1}-1\leq
d_{G}(v)\leq 2^{n}-2$. That is, $\Delta(G)=2\,\delta(G)$.

It has also been proved in [7] that there exists a unique vertex $v$ in a set-
graph $G_{A^{(n)}}$ having the highest possible degree. Another relevant
result reported in the Corrigendum to [7] is the following.

######  Theorem 1.3.

A set-graph $G_{A^{(n)}},n\geq 2$ contains exactly $2n-2$ largest complete
subgraphs (cliques) $K_{2^{n-1}}$.

In this paper, we propose a new parameter called the number of Pythagorean
holes of a graph. Further to some general results, we also discuss this
parameter in respect of set-graphs and Jaco graphs.

##  2 Pythagorean Holes of Graphs

By a Pythagorean triple of positive integers, we mean an ordered triple
$(a,b,c)$, where $a<b<c$, such that $a^{2}+b^{2}=c^{2}$. Also, if $(a,b,c)$ is
a Pythagorean triple of positive integers, then for any (positive) integer
$k$, the triple $(ka,kb,kc)$ is also a Pythagorean triple. That is, we have
$(ka)^{2}+(kb)^{2}=(kc)^{2}$.

Some results in this paper are Pythagorean triple specific and can be
generalised to general ordered triples of positive integers. Some results
could be generalised to other ordered triples satisfying other number
theoretic conditions as well but for now, our interest lies in the notion of
Pythagorean holes in respect of a Pythagorean triple. Using the concepts of
Pythagorean triples, we now introduce the notion of Pythagorean holes of a
given graph $G$ as follows.

######  Definition 2.1.

Let $G$ be a non-empty finite graph and let the three vertices
$v_{i},v_{j},v_{k}$ in $V(G)$ induce primitive hole in $G$. This primitive
hole is said to be a Pythagorean hole if
$(d_{G}(v_{i}),d_{G}(v_{j}),d_{G}(v_{k}))$ are Pythagorean triple. That is, if
$d^{2}_{G}(v_{i})+d^{2}_{G}(v_{j})=d^{2}_{G}(v_{k})$. Let us denote the number
of Pythagorean holes of a graph $G$ by $h^{p}(G)$.

We can easily construct a graph with a Pythagorean hole as follows. Let
$(n_{1},n_{2},n_{3})$ be a Pythagorean triple. Draw a triangle, say $C_{3}$,
on the vertices $v_{1},v_{2},v_{3}$. We extend this triangle to a graph $G$
where $d_{G}(v_{i})=n_{i};~{}1\leq i\leq 3$ as follows. Attach $n_{1}-2$
pendant vertex to the vertex $v_{1}$, attach $n_{2}-2$ pendant vertices to the
vertex $v_{2}$ and add $n_{3}-2$ pendant vertices to $v_{3}$ to obtain a new
graph graph $G$. Here, $G$ is a unicyclic graph on $n_{1}+n_{2}+n_{3}-3$
vertices and edges each and has one primitive hole. Therefore, the triangle
$v_{1}v_{2}v_{3}v_{1}$ is a Pythagorean hole in $G$.

By a minimal graph with respect to a given property, we mean a graph with
minimum order and size satisfying that property. In view of this concept we
introduce the following notion.

######  Definition 2.2.

A graphical embodiment of a given Pythagorean triple is the minimal graph that
consists of a Pythagorean hole with respect to that Pythagorean triple.

Clearly, the graph $G$ mentioned above is not the graphical embodiment of the
Pythagorean triple $(n_{1},n_{2},n_{3})$. Verifying the existence of a
graphical embodiment to a given Pythagorean triple is an interesting question
that leads to the following theorem.

######  Theorem 2.3.

There exists a unique graphical embodiment for every Pythagorean triple of
positive integers.

###### Proof.

Let $(n_{1},n_{2},n_{3})$ be a Pythagorean triple of positive integers such
that $n_{1}<n_{2}<n_{3}$. First, draw a triangle on vertices
$v_{1},v_{2},v_{3}$. Now, plot $n_{1}-2$ vertices and attach them to the
vertex $v_{1}$ so that $d(v_{1})=n_{1}$. Now, attach the $n_{1}-2$ vertices to
$v_{2}$ and $v_{3}$ also. At this step, $d(v_{2})=d(v_{3})=n_{1}$. Now, the
$n_{2}-n_{1}$ additional edges are required to be incident on the vertex
$v_{2}$. Hence, plot new $n_{2}-n_{1}$ vertices and attach them to $v_{2}$ and
$v_{3}$. Now, $d(v_{2})=n_{2}$, as required. But, here $d(v_{3})=n_{2}$ and
additionally $n_{3}-n_{2}$ edges are to be incident on $v_{3}$. Hence, create
new $n_{3}-n_{2}$ vertices attach them to $v_{3}$ so that $d(v_{3})=n_{3}$. In
the resultant graph $G$, $d_{G}(v_{1})^{2}+d_{G}(v_{2})^{2}=d_{G}(v_{3})^{2}$.
Hence, the triangle $v_{1}v_{2}v_{3}v_{1}$ is a Pythagorean hole in $G$.
Clearly, this graph is the smallest graph with a Pythagorean hole
corresponding to the given Pythagorean triple. Any graph other than $G$ will
have more vertices than $G$. Hence, $G$ is a unique graphical embodiment of
the given Pythagorean triple. ∎

The graph $G$ in Figure 1 is an example for a graph containing a Pythagorean
hole corresponding to a Pythagorean triple $(3,4,5)$. The graph $G$ has the
minimum number of vertices (that is, $6$ vertices) required to contain a
Pythagorean hole.

Figure 1: The graphical embodiment of the Pythagorean triple $(3,4,5)$.

From figure 1, it can be noted that the graphical embodiment of the
Pythagorean triple of $(3,4,5)$ has two Pythagorean holes. The uniqueness of
the Pythagorean hole in a graphical embodiment of a given Pythagorean triple,
other than triple $(3,4,5)$, is established in the following theorem.

######  Theorem 2.4.

The graphical embodiment of any Pythagorean triple of positive integers
$(n_{1},n_{2},n_{3})\neq(3,4,5)$, consists of a unique Pythagorean hole in it.

###### Proof.

Let $(n_{1},n_{2},n_{3})\neq(3,4,5)$ be a Pythagorean triple of positive
integers and let $G$ be a graphical embodiment of this triple obtained as
explained in Theorem 2.3. Let $v_{1}v_{2}v_{3}v_{1}$ be a Pythagorean hole in
$G$ such that
$d_{G}(v_{1})=n_{1},d_{G}(v_{2})=n_{2}~{}\text{and}~{}d_{G}(v_{3})=n_{3}$.

It is to be noted that all new vertices that are adjacent to $v_{1}$ in $G$
will be adjacent to both $v_{2}$ and $v_{3}$ also and hence are of degree $3$.
Similarly, all new vertices that are adjacent to $v_{2}$ is adjacent to
$v_{3}$ also. Therefore, the degree of the vertices that are adjacent to
$v_{2}$, but not to $v_{1}$, is $2$ and the degree of the vertices that are
adjacent only to $v_{3}$ is $1$. Also, no two of these new vertices are
mutually adjacent. Hence, for any three vertices $v_{i},v_{j},v_{k}$, other
than $v_{1},v_{2},v_{3}$, do not satisfy the condition
$d_{G}(v_{i})^{2}+d_{G}(v_{j})^{2}=d_{G}(v_{k})^{2}$. Therefore, the triangle
$v_{1}v_{2}v_{3}$ is the unique Pythagorean hole in $G$. ∎

As stated earlier both Theorem 2.3 and Theorem 2.4 can be generalised to other
triples with other number theoretic properties.The characteristics of the
graphical embodiment of a Pythagorean triple seems to be much promising in
this context. The size and order of the graphical embodiment are determined in
the following result.

######  Theorem 2.5.

Let $G$ be the graphical embodiment of a given Pythagorean triple
$(n_{1},n_{2},n_{3})$, with usual notations. Then,

  1. (i)

the order (the number of vertices) of $G$ is one greater than the highest
number in the corresponding Pythagorean triple.

  2. (ii)

the size (the number of edges) of $G$ is three less than the sum of numbers in
the corresponding Pythagorean triple.

###### Proof.

Let $G$ be a graphical embodiment of a Pythagorean triple
$(n_{1},n_{2},n_{3})$. Let $v_{1},v_{2},v_{3}$ be the vertices with
$d_{G}(v_{1})=n_{1},d_{G}(v_{2})=n_{2},~{}\text{and}~{}d_{G}(v_{3})=n_{3}$. As
explained in Theorem 2.3, $n_{1}-2$ vertices are attached to
$v_{1},v_{2},~{}\text{and}~{}v_{3}$, further $n_{2}-n_{1}$ vertices are
attached to $v_{2}~{}\text{and}~{}v_{3}$ and $n_{3}-n_{2}$ pendant vertices
are attached to $v+3$. Then,

  1. (i)

The number of vertices in $G$ is
$|V(G)|=3+n_{1}-2+n_{2}-n_{1}+n_{3}-n_{2}=n_{3}+1$. That is, the order of the
graphical embodiment is one greater than the highest number in the
corresponding Pythagorean triple.

  2. (ii)

Let $V_{1}$ be the set of all newly introduced vertices which are adjacent to
all three vertices $v_{1},v_{2},~{}\text{and}~{}v_{3}$. Therefore, for all
vertices $x$ in $V_{1}$, we have $d_{G}(x)=3$. Therefore, $\sum\limits_{x\in
V_{1}}d_{G}(x)=3(n_{1}-2)$. Similarly, let $V_{2}$ be the set of new vertices
which are adjacent to $v_{2},~{}\text{and}~{}v_{3}$. For all vertices $y$ in
$V_{2}$, we have $d_{G}(y)=3$. Therefore, $\sum\limits_{y\in
V_{2}}d_{G}(y)=2(n_{2}-n_{1})$. Also, let $V_{3}$ be the set of new vertices
that are adjacent to $v_{3}$ only. Here, for all vertex $z$ in $V_{3}$, we
have $d_{G}(z)=1$ and hence $\sum\limits_{z\in V_{3}}d_{G}(z)=(n_{3}-n_{2})$.

Therefore, $\sum\limits_{v\in
V(G)}d_{G}(v)=n_{1}+n_{2}+n_{3}+3(n_{1}-2)+2(n_{2}-n_{1})+(n_{3}-n_{2})=2(n_{1}+n_{2}+n_{3}-3)$.
Since for any connected graph $G$, $|E(G)|=\frac{1}{2}\sum\limits_{v\in
V(G)}d_{G}(v)$, we have $|E(G)|=n_{1}+n_{2}+n_{3}-3$. That is, the size of $G$
is three less than the sum of numbers in the Pythagorean triple.

This completes the proof. ∎

######  Theorem 2.6.

The primitive hole number of the graphical embodiment $G$ of a Pythagorean
triple is $h(G)=2n_{1}+n_{2}-5$.

###### Proof.

Let $G$ be a graphical embodiment of a Pythagorean triple
$(n_{1},n_{2},n_{3})$. Let $v_{1},v_{2},v_{3}$ be the vertices with
$d_{G}(v_{1})=n_{1},d_{G}(v_{2})=n_{2},~{}\text{and}~{}d_{G}(v_{3})=n_{3}$. As
explained in Theorem 2.3, $n_{1}-2$ vertices are attached to $v_{1},v_{2}$ and
$v_{3}$, further $n_{2}-n_{1}$ vertices are attached to
$v_{2}~{}\text{and}~{}v_{3}$ and $n_{3}-n_{2}$ pendant vertices are attached
to $v+3$. Let $V_{1},V_{2},V_{3}$ be the set of vertices as explained in the
previous theorem.

Then, every vertex in $V_{1}$ forms a triangle with any two vertices among
$v_{1},v_{2}$ and $v_{3}$. Hence each vertex in $V_{1}$ corresponds to three
triangles in $G$. Therefore, the total number of such triangles is
$3(n_{1}-2)$. Similarly, every vertex in $V_{2}$, being adjacent only to
$v_{2}$ and $v_{3}$, forms a triangle in $G$ and no vertex in $V_{3}$ is a
part of a triangle in $G$, Therefore, the total number of triangles in $G$ is
$h(G)=1+3(n_{1}-2)+(n_{2}-n_{1})=2n_{1}+n_{2}-5$. This completes the proof. ∎

The following theorem discusses certain parameters of the graphical
embodiments of the given Pythagorean triples.

######  Theorem 2.7.

Let $G$ be the embodiment of a Pythagorean triple $(n_{1},n_{2},n_{3})$. Then
we have

  1. (i)

the chromatic number of $G$ is $\chi(G)=4$.

  2. (ii)

the independence number of $G$ is two less than the highest number in the
Pythagorean triple. That is, $\alpha(G)=n_{3}-2$.

  3. (iii)

the covering number of $G$ is $\beta(G)=3$.

  4. (iv)

the domination number of $G$ is $\gamma(G)=1$.

###### Proof.

Let $G$ be a graphical embodiment of a Pythagorean triple
$(n_{1},n_{2},n_{3})$ in which $v_{1},v_{2},v_{3}$ are the vertices with
$d_{G}(v_{1})=n_{1},d_{G}(v_{2})=n_{2},~{}\text{and}~{}d_{G}(v_{3})=n_{3}$.
Let $V_{1}$ be the set of all new vertices that are attached to $v_{1},v_{2}$,
and $v_{3}$, $V_{2}$ be the set of all new vertices that are attached to
$v_{2}$, and $v_{3}$ and $V_{3}$ be the set of new vertices that are attached
only to $v_{3}$. Then,

  1. (i)

Color $v_{1}$ by the color $c_{1}$, $v_{2}$ by the color $c_{2}$ and $v_{3}$
by the color $c_{3}$. Since all vertices in the set $V_{1}$ and are adjacent
to the above three colors can not be used for coloring the vertices of
$V_{1}$. Since no two vertices in $V_{1}$ are mutually adjacent in $G$, all
vertices in $V_{1}$ can be colored using a fourth color $c_{4}$. Since all
vertices in $V_{2}$ are mutually non-adjacent in $G$ and are not adjacent to
the vertex $v_{1}$, we can use the color $c_{1}$ for coloring all the vertices
in $V_{2}$. Since all the vertices in $V_{3}$ are adjacent to $v_{3}$ only and
are pairwise non-adjacent in $G$, we can color them using either the color
$c_{1}$ or the color $c_{2}$. Therefore, the minimal proper coloring of $G$
contains for colors. That is, $\chi(G)=4$.

  2. (ii)

All the newly introduced vertices in $V_{1},V_{2}$ and $V_{3}$ are mutually
non-adjacent and hence $V_{1}\cup V_{2}\cup V_{3}$ is the maximal independent
set in $G$. Therefore, $\alpha(G)=n_{1}-2+n_{2}-n_{1}+n_{3}-n_{2}=n_{3}-2$.

  3. (iii)

The relation between the independence number and the covering number of a
connected graph is $\alpha(G)+\beta(G)=|V(G)|$. By Theorem 2.5,
$|V(G)|=n_{3}+1$ and by previous result, $\alpha(G)=n_{3}-2$. Therefore, the
covering number of $G$ is $n_{3}+1-(n_{3}-2)=3$.

  4. (iv)

Clearly, the vertex $v_{3}$ is adjacent to all other vertices in the graphical
embodiment $G$, we have $\gamma(G)=1$.

This completes the proof. ∎

It is noted from Theorem 2.7, the chromatic number, covering number and
domination number of the graphical embodiment of any Pythagorean triple are
always the same.

An immediate consequence of the general Pythagorean property is that the
vertices of Pythagorean holes can be mapped onto interesting Euclidean
geometric objects which we can construct along the sides of a right angled
triangle or along the surfaces of the corresponding right angled prism.

######  Illustration 1.

For real $x$, let $d_{G}(v_{1})=+\sqrt{(\frac{a}{2})^{2}-x^{2}}$,
$d_{G}(v_{2})=+\sqrt{(\frac{b}{2})^{2}-x^{2}}$ and
$d_{G}(v_{3})=+\sqrt{(\frac{c}{2})^{2}-x^{2}}$, where $(a,b,c)$ is a
Pythagorean triple of positive integers. Then,

$\displaystyle
d^{2}_{G}(v_{1})=\int\limits_{-\frac{a}{2}}^{\frac{a}{2}}\sqrt{(\frac{a}{2})^{2}-x^{2}}dx=\frac{1}{2}\pi(\frac{a}{2})^{2}=\frac{1}{8}\pi
a^{2}$ $\displaystyle
d^{2}_{G}(v_{2})=\int\limits_{-\frac{b}{2}}^{\frac{b}{2}}\sqrt{(\frac{b}{2})^{2}-x^{2}}dx=\frac{1}{2}\pi(\frac{b}{2})^{2}=\frac{1}{8}\pi
b^{2}$ $\displaystyle
d^{2}_{G}(v_{3})=\int\limits_{-\frac{c}{2}}^{\frac{c}{2}}\sqrt{(\frac{c}{2})^{2}-x^{2}}dx=\frac{1}{2}\pi(\frac{c}{2})^{2}=\frac{1}{8}\pi
c^{2}.$

Since $\frac{1}{8}\pi$ is a constant, we have

$d^{2}_{G}(v_{1})+d^{2}_{G}(v_{2})=\frac{1}{8}\pi(a^{2}+b^{2})=\frac{1}{8}\pi
c^{2}=d^{2}_{G}(v_{3}).$

That is, the Pythagorean property holds for the triple
$(d_{G}(v_{1}),d_{G}(v_{2}),d_{G}(v_{3}))$. Geometrically it means that the
area of the semi-circle with length of hypotenuse as its diameter is equal to
the sum of the respective areas of the semi-circles with lengths of the other
two sides of a right angled triangle as the diameters.

######  Illustration 2.

For an arbitrary real number $x$, let $d_{G}(v_{1})=x+bc$, $d_{G}(v_{2})=x+ac$
and $d_{G}(v_{3})=x+2ab$, where $(a,b,c)$ is a Pythagorean triple of positive
integers. Then,

$\displaystyle d^{2}_{G}(v_{1})=\int_{0}^{a}(x+bc)dx=\frac{1}{2}a^{2}+abc,$
$\displaystyle d^{2}_{G}(v_{2})=\int_{0}^{b}(x+ac)dx=\frac{1}{2}b^{2}+abc,$
$\displaystyle d^{2}_{G}(v_{3})=\int_{0}^{c}(x+2ab)dx=\frac{1}{2}c^{2}+2abc.$

Since $\frac{1}{2}a^{2}+abc+\frac{1}{2}b^{2}+abc=\frac{1}{2}c^{2}+2abc$, it
implies geometrically that the area under the straight line
$f(x)=x+2ab,x\in\mathbb{R}$ between the limits $x=0$ and $x=c$ is equal to the
sum of the respective areas under the straight lines
$f(x)=x+bc,x\in\mathbb{R}$ between the limits $x=0$ and $x=a$ and
$f(x)=x+ac,x\in\mathbb{R}$ between the limits $x=0$ and $x=b$ in respect of a
right angled triangle.

Clearly, we can find many such mappings and it would be worthy to find the
applications of these mappings.

##  3 On Pythagorean Holes of Set-Graphs

The following result is on the degree sequence of set-graphs.

######  Lemma 3.1.

Consider the degree sequence $(d_{1},d_{2},d_{3},\ldots,d_{r})$ of the set-
graph $G_{A^{(n)}}$. Then, for any triple $(d_{i},d_{j},d_{k})$, where
$d_{i}<d_{j}<d_{k}$, in that degree sequence, $d_{i}+d_{j}>d_{k}$.

###### Proof.

Recall the theorem that for any set-graph $G=G_{A^{(n)}}$,
$2\delta(G)=\Delta(G)$. There fore, Since,
$d_{i}+d_{j}>2\delta(G)=\Delta(G)\geq d_{k}$, the result holds for the new
vertices of degree $2^{n}+d_{i}$ or $2^{n}-1$ as well. ∎

######  Theorem 3.2.

A set-graph has no Pythagorean holes.

###### Proof.

Note that for any Pythagorean triple $(a,b,c)$ with $a<b<c$ is either $a,b,c$
are all even, or only one of $a,b$ is even by taking modulo $4$ (see [3]). But
for any set-graph $G=G_{A^{(n)}}$, we have $\Delta(G)$ is always even and is
the only vertex having even degree. Therefore, no set-graph can have a
Pythagorean hole. ∎

##  4 Pythagorean holes of Jaco graphs

######  Definition 4.1.

The notion of the infinite Jaco graph (order 1) was introduced in [8] as a
directed graph with $V(J_{\infty}(1))=\\{v_{i}|i\in\mathbb{N}\\}$,
$E(J_{\infty}(1))\subseteq\\{(v_{i},v_{j})|i,j\in\mathbb{N},i<j\\}$ and
$(v_{i},v_{j})\in E(J_{\infty}(1))$ if and only if $2i-d^{-}(v_{i})\geq j$. We
denote a finite Jaco graph by $J_{n}(1)$ and its underlying graph by
$J^{\ast}_{n}(1)$. In both instances we will refer to a Jaco graph and
distinguish the context by the notation $J_{n}(1)$ or $J^{\ast}_{n}(1)$.

The primitive hole number of the underlying graph of a Jaco graph has been
determined in the following theorem (see [6]).

######  Theorem 4.2.

[6] Let $J^{\ast}_{n}(1)$ be the underlying graph of a finite Jaco Graph
$J_{n}(1)$ with Jaconian vertex $v_{i}$, where $n$ is a positive integer
greater than or equal to $4$. Then,
$h(J^{\ast}_{n+1}(1))=h(J^{\ast}_{n}(1))+\sum\limits_{j=1}^{(n-i)-1}(n-i)-j$.

It can be noted that the smallest Jaco graph having a Pythagorean hole is
$J^{\ast}_{8}(1)$.

######  Theorem 4.3.

For any primitive hole of the Jaco graph $J^{\ast}_{n}(1),n\in\mathbb{N}$ on
the vertices $v_{i},v_{j},v_{k}$ with $i<j<k$ we have a primitive hole on the
vertices $v_{li},v_{lj},v_{lk}$ in $J^{\ast}_{n\geq lk}(1),l\in\mathbb{N}$ if
the edge $v_{li}v_{lk}$ exists.

###### Proof.

For any primitive hole of the Jaco graph $J^{\ast}_{n}(1),n\in\mathbb{N}$ on
the vertices $v_{i},v_{j},v_{k}$ with $i<j<k$ the edge $v_{i}v_{k}$ exists
hence $k\leq i+d^{+}_{J_{n}(1)}(v_{i})$. So $lk\leq
l(i+d^{+}_{J_{n}(1)}(v_{i}))=li+ld^{+}_{J_{n}(1)}(v_{i})$. Assume that the
edge $v_{li}v_{lk}$ exists. Then, the subgraph induced by vertices
$v_{i},v_{i+1},v_{i+2},...v_{j},v_{j+1},v_{j+2},...,v_{k}$ is a complete graph
the same holds for the vertex $v_{j}$. That is, edges $v_{li}v_{lj}$ and
$v_{lj}v_{lk}$ exists. ∎

It is known that there are $16$ primitive Pythagorean triples $(a,b,c)$ with
$c\leq 100$. These, in ascending order of $c$ are: $t_{1}=(3,4,5)$;
$(5,12,13)$; $(8,15,17)$; $(7,24,25)$; $t_{2}=(20,21,29)$; $(12,35,37)$;
$(9,40,41)$; $t_{3}=(28,45,53)$; $(11,60,61)$; $(16,63,65)$; $(33,56,65)$;
$t_{4}=(48,55,73)$; $(13,84,85)$; $(36,77,85)$; $(39,80,89)$;
$t_{5}=(65,72,97)$.

From the definition of Jaco graphs, it easily follows that the Pythagorean
triples labeled $t_{i}$; $1\leq i\leq 5$ are applicable to the Pythagorean
holes found in Jaco graphs. We shall refer to these Pythagorean triples as
type i; $i\in\mathbb{N}$. With regards to Theorem 4.3, we shall refer to
$lt_{i}=(a_{i}l,b_{i}l,c_{i}l)$ as type $i$ as well. The number of Pythagorean
holes of type $i$ in a graph will be denoted $h^{p}_{t_{i}}(G)$.

Other Pythagorean triples generated by Euclid formula which are not of a
specific primitive type offer some additional Pythagorean holes in Jaco
graphs. Let us denote these additional types as $e_{i};i\in\mathbb{N}$.

The following results will hold for type $1$, $t_{1}=(3,4,5)$.

######  Corollary 4.4.

The Jaco graph $J^{\ast}_{n}(1)$, where $n=5k+d^{+}_{J_{\infty}(1)}(v_{5k})$,
has $h_{t_{1}}^{p}(J_{n}^{\ast}(1))=k$ Pythagorean holes, if
$3k+d^{+}_{J_{\infty}(1)}(v_{3k})\geq 5k$.

###### Proof.

The result follows from Theorem 4.3. ∎

######  Corollary 4.5.

The Jaco graphs $J^{\ast}_{n}(1),8\leq n\leq 15$ are the only Jaco graphs with
a unique Pythagorean hole.

###### Proof.

Since $2\times 5=10$ and $d_{J^{\ast}_{16}(1)}(v_{10})=10$ whilst
$d_{J^{\ast}_{n}(1)}(v_{10})<10$, for $n\leq 15$, the Jaco graph
$J^{\ast}_{16}(1)$ has two Pythagorean holes because,
$d^{2}_{J^{\ast}_{16}(1)}(v_{3})+d^{2}_{J^{\ast}_{16}(1)}(v_{4})=d^{2}_{J^{\ast}_{16}(1)}(v_{5})$
and
$d^{2}_{J^{\ast}_{16}(1)}(v_{6})+d^{2}_{J^{\ast}_{16}(1)}(v_{8})=d^{2}_{J^{\ast}_{16}(1)}(v_{10})$.
All other Jaco graphs $J^{\ast}_{n}(1)$, for $n\geq 16$, will have at least
two Pythagorean holes. Since Jaco graphs $J^{\ast}_{n,1\leq n\leq 7}(1)$ have
no Pythagorasian hole, the result follows. ∎

######  Theorem 4.6.

The Jaco graph $J^{\ast}_{n}(1),n\geq 8$ has
$h^{p}_{t_{1}}(J^{\ast}_{n}(1))=k$ Pythagorean holes for
$5k+d^{+}_{J_{\infty}(1)}(v_{5k})\leq
n<5(k+1)+d^{+}_{J_{\infty}(1)}(v_{5(k+1)})$, alternatively
$h_{t_{i}}^{p}(J^{\ast}_{n}(1))=\lfloor\frac{n}{8}\rfloor$.

###### Proof.

A direct consequence of Theorem 4.3 and Corollary 4.4. ∎

The adapted Fisher Table, $J_{\infty}(1),35\geq n\in\mathbb{N}$ depicts the
values $h(J^{\ast}_{n}(1))$ and $h_{t_{1}}^{p}(J^{\ast}_{n}(1))$.

$\phi(v_{i})\rightarrow i\in{\mathbb{N}}$ | $d^{-}(v_{i})=\nu(\mathbb{H}_{i-1})$ | $d^{+}(v_{i})=i-d^{-}(v_{i})$ | $h(J^{\ast}_{i}(1))$ | $h_{t_{1}}^{p}(J^{\ast}_{n}(1))$
---|---|---|---|---
1=$f_{2}$ | 0 | 1 | 0 | 0
2=$f_{3}$ | 1 | 1 | 0 | 0
3=$f_{4}$ | 1 | 2 | 0 | 0
4 | 1 | 3 | 0 | 0
5=$f_{5}$ | 2 | 3 | 1 | 0
6 | 2 | 4 | 2 | 0
7 | 3 | 4 | 5 | 0
8=$f_{6}$ | 3 | 5 | 8 | 1
9 | 3 | 6 | 11 | 1
10 | 4 | 6 | 17 | 1
11 | 4 | 7 | 23 | 1
12 | 4 | 8 | 29 | 1
13=$f_{7}$ | 5 | 8 | 39 | 1
14 | 5 | 9 | 49 | 1
15 | 6 | 9 | 64 | 1
16 | 6 | 10 | 79 | 2
17 | 6 | 11 | 94 | 2
18 | 7 | 11 | 115 | 2
19 | 7 | 12 | 136 | 2
20 | 8 | 12 | 164 | 2
21=$f_{8}$ | 8 | 13 | 192 | 2
22 | 8 | 14 | 220 | 2
23 | 9 | 14 | 256 | 2
24 | 9 | 15 | 292 | 3
25 | 9 | 16 | 328 | 3
26 | 10 | 16 | 373 | 3
27 | 10 | 17 | 418 | 3
28 | 11 | 17 | 473 | 3
29 | 11 | 18 | 528 | 3
30 | 11 | 19 | 583 | 3
31 | 12 | 19 | 649 | 3
32 | 12 | 20 | 715 | 4
33 | 12 | 21 | 781 | 4
34=$f_{9}$ | 13 | 21 | 859 | 4
35 | 13 | 22 | 937 | 4

It can be seen that Pythagorean holes are generally scares within Jaco graphs
compared to the number of primitive holes. But since the graph in figure 1 can
be extended endlessly through edge-joints to produce a graph $H$ with
$h^{p}(H)=h(H)$, the inequality $h^{p}(G)\leq h(G)$ holds. To construct the
adapted Fisher table an improvement to Theorem 4.2 is required.

######  Theorem 4.7.

For the underlying graph $J^{\ast}_{n}(1)$ of a finite Jaco Graph
$J_{n}(1),n\in\mathbb{N},n\geq 4$ we have the recursion formula
$h(J^{\ast}_{n+1}(1))=h(J^{\ast}_{n}(1))+\sum\limits_{i=1}^{d^{-}_{J_{\infty}(1)}(v_{n+1})-1}i$.

###### Proof.

Consider the Jaco graph $J^{\ast}_{n}(1)$ with $h(J^{\ast}_{n}(1))=k$. By
extending from $J_{n}(1)$ to $J_{n+1}(1)$ a total of
$d^{-}_{J_{\infty}(1)}(v_{n+1})$ arcs are added together with the vertex
$v_{n+1}$. In the Jaco graph $J^{\ast}_{n+1}(1)$ vertex $v_{n+1}$ is a vertex
of the new underlying Hope graph, $\mathbb{H}(J^{\ast}_{n+1}(1))$. Hence, with
$v_{n+1}$ a common vertex to all, exactly
$\sum\limits_{i=1}^{d^{-}_{J_{\infty}(1)}(v_{n+1})-1}i$, additional primitive
holes are added. Hence, we have the result
$h(J^{\ast}_{n+1}(1))=h(J^{\ast}_{n}(1))+\sum\limits_{i=1}^{d^{-}_{J_{\infty}(1)}(v_{n+1})-1}i$.
∎

The following results is a direct consequence of Theorem 4.3 and Theorem 4.6.

######  Theorem 4.8.

Consider the distinct Pythagorean triples
$t_{i},t_{j},\ldots,t_{k},e_{r},e_{s},\ldots e_{x}$ and no triple is a
multiple of another, with the form $(a_{\alpha},b_{\alpha},c_{\alpha})$ and
$(a_{\beta},b_{\beta},c_{\beta})$ and
$c=max\\{c_{i},...,c_{k},c_{r},...,c_{x}\\}$. Then,
$h^{p}(J^{\ast}_{c+d^{+}(v_{c})}(1))=\sum\limits_{t_{l}}h^{p}_{t_{l}}(J^{\ast}_{c+d^{+}(v_{c})}(1))+\sum\limits_{e_{m}}h^{p}_{e_{m}}(J^{\ast}_{c+d^{+}(v_{c})}(1))$,
for all $l=i,j,\ldots,k$ and $m=r,s\dots,x$.

The following results is a direct consequence of Theorem 4.3 and Corollary
4.4.

######  Corollary 4.9.

Let $t_{i}$ (or $e_{m}$) denotes a Pythagorean triple
$(a_{\alpha},b_{\alpha},c_{\alpha})$, then
$h^{p}_{t_{i}}(J_{n}^{\ast}(1))=\lfloor\frac{n}{c_{\alpha}+d^{+}(v_{c_{\alpha})}}\rfloor$
or
$h^{p}_{e_{m}}(J_{n}^{\ast}(1))=\lfloor\frac{n}{c_{\alpha}+d^{+}(v_{c_{\alpha})}}\rfloor$.

##  5 Conclusion and Scope for Further Studies

We have discussed particular types of holes called Pythagorean holes of given
graphs studied the existence thereof in certain graphs, particularly in set-
graphs and Jaco graphs.

As all graphs do not contain Pythagorean holes, the study on the
characteristics and structural properties of graphs containing Pythagorean
holes arouses much interest. The questions regarding the number of Pythagorean
holes in a given graph is a parameter that needs to be studied further.

We proved that the graphical embodiment of all Pythagorean triples, except for
$(3,4,5)$, contain exactly one Pythagorean hole. But, some graphs may contain
more than one Pythagorean hole. The study on the graphs or graph classes
containing more than one Pythagorean classes corresponding to one or more
Pythagorean triples demands further investigation. Another interesting related
area for further research is to construct the graphical embodiments of other
triples and general $n$-tuples and study their characteristics.

The study seems to be promising as it can be extended to certain standard
graph classes and certain graphs that are associated with the given graphs.
More problems in this area are still open and hence there is a wide scope for
further studies.

It was illustrated that the vertices of a Pythagorean hole hole can be mapped
onto Euclidean geometric objects. An imaginative prospect is that these
theoretical applications can perhaps find real application in nano technology.
It is proposed that this avenue deserves further research.

## References

  * [1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, London, 1976.
  * [2] G. Chartrand and L. Lesniak, Graphs and Digraphs, CRC Press, 2000.
  * [3] K. Conrad, Pythagorean Triples, www.math.uconn.edu/~kconrad/blurbs/ugradnumthy/pythagtriple.pdf
  * [4] J. T. Gross and J. Yellen, Graph Theory and its Applications, CRC Press, 2006.
  * [5] F. Harary, Graph Theory, Addison-Wesley, 1994.
  * [6] J. Kok and N. K. Sudev, A Study on Primitive Holes of Certain Graphs, International Journal of Scientific and Engineering Research, 6(3)(2015), 631-635.
  * [7] J. Kok and N. K. Sudev, A Study on Set-Graphs, to appear in International Journal of Computer Applications.
  * [8] J. Kok, P. Fisher, B. Wilkens, M. Mabula and V. Mukungunugwa, Characteristics of Finite Jaco Graphs, $J_{n}(1),n\in\mathbb{N},n\geq 4$, pre-print, arXiv: 1404.0484v1.
  * [9] K. H. Rosen, Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.
  * [10] D. B. West, Introduction to Graph Theory, Pearson Education Inc., 2001.