# Hybrid Multihead Attentive Unet-3D for Brain Tumor Segmentation

Muhammad Ansab Butt  Absaar Ul Jabbar Muhammad Ansab Butt is with the
University of Engineering and Technology, Lahore, Pakistan
(e-mail:engransab4@gmail.com). Absaar Ul Jabbar is with the School of
Interdisciplinary Engineering and Sciences, National University of Sciences
and Technology, Islamabad, Pakistan (e-mail<EMAIL_ADDRESS>absaar468@gmail.com).

###### Abstract

Brain tumor segmentation is a critical task in medical image analysis, aiding
in the diagnosis and treatment planning of brain tumor patients. The
importance of automated and accurate brain tumor segmentation cannot be
overstated. It enables medical professionals to precisely delineate tumor
regions, assess tumor growth or regression, and plan targeted treatments.
Various deep learning-based techniques proposed in the literature have made
significant progress in this field, however, they still face limitations in
terms of accuracy due to the complex and variable nature of brain tumor
morphology. In this research paper, we propose a novel Hybrid Multihead
Attentive U-Net architecture, to address the challenges in accurate brain
tumor segmentation, and to capture complex spatial relationships and subtle
tumor boundaries. The U-Net architecture has proven effective in capturing
contextual information and feature representations, while attention mechanisms
enhance the model’s ability to focus on informative regions and refine the
segmentation boundaries. By integrating these two components, our proposed
architecture improves accuracy in brain tumor segmentation. We test our
proposed model on the BraTS 2020 benchmark dataset and compare its performance
with the state-of-the-art well-known SegNet, FCN-8s, and Dense121 U-Net
architectures. The results show that our proposed model outperforms the others
in terms of the evaluated performance metrics.

Multi-scale attention, BraTS, Medical Imaging, Image segmentation, Magnetic
resonance imaging (MRI)

##  1 Introduction

Brain tumor segmentation plays a vital role in the diagnosis, treatment
planning, and monitoring of brain tumors. Accurate and automated segmentation
of tumor regions from medical images assists in quantitative analysis,
clinical decision-making, and improving patient outcomes. In recent years,
deep learning-based approaches have revolutionized medical image segmentation,
providing robust and precise tumor delineation. Among these approaches, the 3D
U-Net [24] [7] [5] [2] [4] architecture has demonstrated remarkable success
due to its ability to capture both local and global contextual information.
Furthermore, the incorporation of multihead attention mechanisms enhances the
model’s ability to focus on relevant features, leading to improved
segmentation accuracy.

Multihead attention (MHA) is a key component in modern neural network
architectures, particularly in the field of Natural Language Processing (NLP).
It enables neural networks to focus on different parts of the input sequence
simultaneously and captures multiple perspectives or representations by
splitting the input into multiple ”heads” and applying attention mechanisms
independently. MHA enhances the modeling of long-range dependencies, improves
representation learning by capturing diverse information, enables
parallelization for efficient computation, and enhances robustness to noise
and variations. While the effectiveness and versatility of MHA have been
successfully demonstrated in various NLP applications, such as machine
translation, text summarization, sentiment analysis [21], question answering
[35], and language generation, its exploration in the context of segmentation
tasks has been relatively limited until recent times.

###  1.1 Motivation

The incorporation of multihead attention mechanisms in segmentation algorithms
can enhance their ability to focus on relevant features, leading to improved
segmentation accuracy. Here, we introduce a novel approach that combines the
power of MHA with the widely used 3D U-Net architecture for accurate brain
tumor segmentation. By leveraging MHA’s ability to capture diverse and fine-
grained information, we aim to enhance the segmentation performance and
address the challenges associated with brain tumor analysis, such as handling
diverse tumor types, sizes, and imaging modalities. Our proposed approach
holds great promise in improving the accuracy and reliability of brain tumor
segmentation, paving the way for more advanced and effective medical imaging
applications. By achieving accurate tumor segmentation, we aim to provide
clinicians with a reliable tool for tumor characterization, treatment
planning, and monitoring of tumor progression.

###  1.2 Objectives

The main objectives of this research study are:

  * •

To develop a 3D U-Net model with a multihead attention mechanism for accurate
and automated brain tumor segmentation.

  * •

To evaluate the performance of the proposed model on BraTS 2020 brain tumor
dataset, considering different tumor types and imaging modalities.

  * •

To investigate the impact of different hyperparameter values on the
performance of the proposed model.

  * •

To compare the performance of the proposed model with state-of-the-art
segmentation methods such as SegNet, FCN-8s, and Dense121 U-Net architectures.

  * •

To analyze the interpretability and generalizability of the proposed model by
visualizing and assessing its segmentation results.

###  1.3 Contributions

  * •

A novel 3D U-Net architecture with multihead attention tailored specifically
for brain tumor segmentation, enabling accurate tumor delineation.

  * •

Extensive experiments and evaluations on benchmark brain tumor dataset BraTS
2020 demonstrate the proposed model’s effectiveness and robustness.

  * •

Comprehensive analysis of various factors influencing the model’s performance,
providing insights into optimizing the segmentation process.

  * •

Performance comparison of the proposed model with the state-of-the-art
segmentation methods.

  * •

In-depth visualization and interpretation of the segmentation results, aiding
clinicians in understanding and validating the model’s performance.

###  1.4 Practical Applications

The accurate segmentation of brain tumors using advanced deep learning models,
such as the 3D U-Net architecture with multihead attention, holds significant
practical implications in various fields, including brain telemetry and brain
transplantation.

In the context of brain telemetry, the ability to accurately segment brain
tumors is crucial for understanding the spatial extent and location of the
tumor. This information is vital for the placement and positioning of brain
telemetry devices, such as Neuralink’s brain chips [23]. Accurate tumor
segmentation allows for precise targeting of specific regions of interest,
enhancing the effectiveness of brain telemetry for monitoring brain activity
and collecting data. Additionally, the segmentation of brain tumors enables
the identification of critical structures and functional areas adjacent to the
tumor, ensuring their preservation during the implantation of brain chips.

From the perspective of tumor surgery, accurate tumor segmentation plays a
crucial role in surgical planning. Surgeons need to visualize and understand
the tumor’s extent and location to perform precise and successful
neurosurgical procedures. Accurate segmentation helps in identifying tumor
boundaries and differentiating between tumor sub-regions, such as the core,
active tumor, and edema. This information guides surgeons in determining the
optimal resection margins and ensuring complete removal of the tumor while
preserving healthy brain tissue. Furthermore, post-surgery monitoring of tumor
progression and treatment response heavily relies on accurate and reliable
segmentation of tumor regions.

Therefore, the application of advanced deep learning techniques, such as the
3D U-Net architecture with multihead attention, in brain tumor segmentation
can contribute to the success and advancement of practical applications such
as brain telemetry and neurosurgery. These techniques can enable precise and
accurate delineation of tumor regions, facilitating optimal surgical planning,
patient-specific treatment strategies, and improved post-operative monitoring.

##  2 Literature Review

Brain tumor segmentation poses significant challenges in medical image
analysis. The task gets complicated due to tumor heterogeneity, where tumors
exhibit diverse characteristics in shape, size, texture, and intensity. To
address these challenges a lot of research is being carried out to develop
more accurate and efficient brain segmentation methods. The MICCAI Brain Tumor
Segmentation (BraTS) Challenge has introduced the Multimodal Brain Tumor Image
Segmentation Benchmark datasets [18] [29], to facilitate the evaluation of
segmentation methods.

###  2.1 Traditional Approaches for Brain Tumor Segmentation

Traditional image segmentation approaches have employed techniques like
thresholding, region growing, and mathematical morphology [9] [10]. However,
these techniques suffer from several limitations when applied to brain tumor
segmentation.

The thresholding technique, for instance, relies heavily on intensity values
to distinguish tumor regions from the surrounding healthy tissue. However,
brain tumor images often exhibit significant intensity variations due to
factors such as image artifacts, diverse tumor appearances, and heterogeneous
tissue characteristics, making it challenging to set appropriate thresholds.

Similarly, region growing and mathematical morphology methods often focus on
local image information and may not effectively capture the spatial context of
the tumor. This limitation can result in fragmented segmentations or the
inclusion of non-tumor regions within the segmented area.

Moreover, these segmentation methods are sensitive to noise and artifacts,
leading to false positive or false negative tumor detections. Brain tumor
images can suffer from inherent noise and imaging artifacts, such as partial
volume effects, and motion artifacts, which can affect the accuracy of these
methods.

Furthermore, many traditional methods require manual parameter tuning to adapt
to different image characteristics and tumor types. This process can be time-
consuming and subjective, as the optimal parameters may vary depending on the
specific dataset and user expertise. Brain tumor diagnosis often involves the
integration of multiple imaging modalities, such as MRI, CT, and PET scans.
Traditional segmentation methods struggle to handle the inherent challenges of
multimodal imaging, such as intensity variations, registration issues, and
different contrasts.

To overcome the limitations, more advanced and sophisticated techniques, such
as deep learning-based approaches, have emerged in recent years, offering
improved accuracy, robustness, and adaptability in brain tumor segmentation.

###  2.2 Deep Learning for Brain Tumor Segmentation

The emergence of deep learning techniques has revolutionized medical image
segmentation, including brain tumor segmentation. Convolutional Neural
Networks (CNNs) have demonstrated remarkable success in capturing complex and
hierarchical image features, leading to improved segmentation accuracy.

Many researchers have used a CNN-based approach specifically for brain tumor
segmentation using MRI images [6] [28] [21]. They employed a 2D CNN with a
patch-based approach to handle large images. By dividing the input images into
smaller patches, the CNN could effectively capture local information and learn
discriminative features. The patch-based approach also helped mitigate memory
constraints associated with processing large 3D medical images. [31] proposed
a technique based on the fusion of deep semantics and edge information in
multimodal MRI.

However, the 2D CNN approach lacks full utilization of 3D information and
spatial context, limiting its accuracy in capturing complex tumor variations
and shapes. It also exhibits increased computational complexity compared to 3D
approaches, requiring longer processing times.

[14] introduced an efficient multi-scale 3D CNN with fully connected CRF for
accurate brain lesion segmentation. Similarly, [13] introduced brain tumor
segmentation using multi-cascaded convolutional neural networks and
conditional random field. In another study [30], a 3D fully connected
convolutional neural network with an atrous-convolution feature pyramid was
introduced for brain tumor segmentation via MRI images. [27] introduced an
Adversarial network with multi-scale 1-1 loss for medical image segmentation.

The above-mentioned models incorporated multi-scale processing to capture both
local and global contextual information, enabling more accurate segmentation.
The fully connected CRF further refined the segmentation results by
considering spatial dependencies between neighboring voxels. This approach
significantly improved brain lesion segmentation accuracy compared to
traditional methods.

These studies showcased the potential of CNNs in automating the brain tumor
segmentation process and achieving higher accuracy compared to traditional
methods. The ability of CNNs to learn discriminative features directly from
the data, combined with their ability to capture both local and global
information, has made them a powerful tool in the field of medical image
analysis. By leveraging the large amounts of labeled data available in brain
tumor datasets, CNN-based approaches have been able to learn intricate
patterns and variations, enabling robust and accurate segmentation.

However, despite the success of CNNs, challenges remain in handling class
imbalance, limited training data, and addressing the interpretability of the
learned features. Researchers continue to explore novel architectures, data
augmentation techniques, and regularization strategies to overcome these
challenges and further improve the performance of deep learning models for
brain tumor segmentation.

###  2.3 The U-Net Architecture for Biomedical Image Segmentation

The U-Net architecture, proposed by [22], has gained widespread adoption in
biomedical image segmentation tasks, including brain tumor segmentation[11]
[15], segmentation of skin lesions [17] etc. The U-Net architecture is
renowned for capturing local and global contextual information, enabling
precise and accurate segmentation.

The U-Net architecture consists of a contracting path and an expanding path,
forming a U-shaped network structure. The contracting path, also known as the
encoder, captures contextual information by progressively reducing the spatial
dimensions of the input image. It consists of a series of convolutional and
pooling layers that learn hierarchical representations of the input data. Each
convolutional layer is typically followed by batch normalization and
activation functions, such as ReLU, to introduce non-linearity and enhance
feature extraction.

To enable precise localization, skip connections are introduced in the U-Net
architecture [19]. These connections establish direct connections between the
corresponding encoding and decoding layers. By merging the feature maps from
the contracting path with the upsampled feature maps from the expanding path,
the model can fuse both low-level and high-level features. This mechanism
enables the U-Net architecture to capture fine-grained details while
preserving important contextual information, leading to improved segmentation
accuracy.

Various studies have presented an automated design methodology for U-Net
models in biomedical image segmentation [20][1]. They introduced an
optimization framework that automates the process of selecting the model
architecture, including the number of layers and filters. This methodology
streamlines the design process and ensures the effectiveness and flexibility
of U-Net models in various biomedical image segmentation tasks.

The U-Net architecture has demonstrated remarkable performance in various
biomedical segmentation tasks, including brain tumor segmentation. Its ability
to capture both local and global information, coupled with the fusion of low-
level and high-level features, has made it a popular choice among researchers.
However, further advancements in U-Net-based models continue to be explored,
including the integration of attention mechanisms and additional architectural
modifications, to further enhance its segmentation accuracy and robustness.

###  2.4 Transformers in Brain Tumor Segmentation

Transformers, originally introduced by [25] for natural language processing
tasks, have gained significant attention in various computer vision
applications, including medical image segmentation. Transformers are based on
the self-attention mechanism, allowing them to capture global dependencies and
long-range interactions in the input data. In recent years, researchers have
explored the application of Transformers in brain tumor segmentation,
leveraging their ability to model complex relationships within medical images.

The traditional U-Net architecture with skip connections has been the go-to
choice for brain tumor segmentation. However, the inherent limitations of
U-Net in capturing global context and long-range dependencies have led to the
exploration of Transformer-based models. Transformers excel in modeling
relationships between different image regions, enabling more accurate and
precise segmentation.

One approach is to replace the encoder part of the U-Net architecture with
transformer layers. [12] proposed the U-NetR architecture, which replaces the
convolutional layers in the U-Net encoder with Transformer encoder layers. The
self-attention mechanism in transformers allows the model to capture global
context and dependencies effectively, enabling accurate tumor segmentation.
The skip connections are preserved, allowing the fusion of low-level and high-
level features for precise localization. Experimental results have shown that
U-NetR achieves competitive performance compared to traditional U-Net models
while capturing long-range dependencies.

Another approach is to combine both convolutional and Transformer layers in a
hybrid architecture. [16] introduced a hybrid model called Trans U-Net, which
integrates the U-Net architecture with self-attention modules inspired by
Transformers. In Trans U-Net, the self-attention modules capture global
dependencies, while the U-Net like structure captures local features. The
hybrid architecture leverages the complementary strengths of both
convolutional and Transformer layers, resulting in improved segmentation
performance.

The use of Transformers in brain tumor segmentation introduces new
possibilities for capturing long-range dependencies and modeling complex
interactions within medical images. By exploiting the self-attention
mechanism, Transformers offer the potential for more accurate and robust
segmentation results. However, due to the high computational requirements of
Transformers, their application in medical imaging tasks often requires
efficient implementations and model optimization techniques.

Further research and exploration are needed to investigate the effectiveness
of different Transformer architectures, attention mechanisms, and fusion
strategies in brain tumor segmentation. Additionally, incorporating
Transformers into multi-modal segmentation frameworks and addressing the
challenges of limited training data in medical imaging are important avenues
for future investigation.

Our proposed architecture, referred to as U-net 3D with Multihead Attention
(U-Net 3D+MHA), builds upon the well-known U-Net architecture while
incorporating the power of multihead attention (MHA). In U-Net 3D+MHA, we
introduce MHA modules that enable the model to capture long-range dependencies
and better exploit the spatial relationships within the 3D input volume. By
applying attention mechanisms independently on multiple heads, our
architecture can attend to different parts of the input simultaneously,
capturing diverse and fine-grained information. This enhanced modeling of
interdependencies and the ability to capture long-range dependencies can
significantly improve the accuracy of brain tumor segmentation. By
incorporating MHA, the model can effectively capture intricate spatial
relationships and diverse features, leading to more precise tumor
segmentation.

##  3 Methodology

In this section, the methodology adopted for this research work has been
highlighted. Subsection 3.1 discusses the data visualisation techniques
employed to gain insights into the BraTS 2020 dataset used for brain tumor
segmentation and classification tasks. Prior to model training, the BraTS 2020
data underwent preprocessing steps to ensure optimal input for the models,
which is described in section 3.2. The preprocessing included skull stripping,
bias correction, intensity normalization, and image resampling to a consistent
voxel size. Subsection 3.3 describes the architecture of our proposed hybrid
multihead attentive U-Net 3D model.

###  3.1 Data Visualisation

This section plays a crucial role in providing a comprehensive understanding
of the characteristics of brain tumor images and masks. By employing various
visualization techniques, valuable insights into the effectiveness of our
proposed Hybrid Multihead Attentive U-Net architecture for brain tumor
segmentation are gained. The visualization process involves loading the
training dataset, focusing on specific patients, and utilizing the NeuroLearn
library for visualization tasks. Different representations of the MRI images
and masks, including anatomical structure, functional brain activity, spatial
distribution, and localized tumor region are shown in Fig.1. These
visualizations serve as a foundation for further analysis and development,
enabling a deeper understanding of the intricacies of brain tumor segmentation
and validating the potential of our proposed architecture.

Figure 1: Visualization of Brain Tumor Segmentation using NeuroLearn
Library.The figure showcases different visualizations of the input medical
images and corresponding segmentation masks from the BraTS 202020 dataset.
These multiple rows in the figure highlight the representation of a FLAIR
image in different masks i.e. epi, anat and roi.

The Figure 1 shows different visualisations of input medical images and
corresponding segmentation masks, which allows for a comprehensive analysis of
the brain tumor image, its anatomical structure, functional representation,
spatial distribution, and the localized tumor regions. Such visualizations are
crucial for gaining insights into the characteristics of brain tumors and
informing subsequent steps in the segmentation process.

###  3.2 Data preprocessing

The data preprocessing stage is a crucial step in preparing the dataset for
subsequent analysis and model training. The preprocessing approach adopted in
this study is illustrated in Fig. 2. Various preprocessing tasks are performed
on the BRATS 2020 dataset, including loading the T2, T1CE, FLAIR, and mask
images using the nibabel library. The T2, T1CE, and FLAIR volumes are
normalized using the MinMaxScaler from the scikit-learn library to ensure
consistent intensity ranges across different images. The mask volume is
converted to an unsigned integer format, and mask values of 4 are reassigned
to 3. The T2, T1CE, and FLAIR volumes are combined into a single 4-channel
image, and both the image and mask are cropped to a size divisible by 64 [8]
for compatibility with subsequent patch extraction.

The T1 image was not stacked with the other images, as it had no information
regarding the tumor and would only contribute to scaling up the size of the
dataset, thus increasing training time and computational cost.

The preprocessing stage also ensures the ratio of non-zero label volumes in
the mask and saves the image and corresponding mask as numpy arrays if the
ratio exceeds 1%. Finally, the resulting dimensions of the images and masks
are printed for verification. These preprocessing steps are essential in
preparing the dataset for brain tumor segmentation and classification tasks.

Figure 2: Data preprocessing workflow, step by step approach from data loading
to saving the new dataset as numpy volumes.

###  3.3 The U-Net 3D with multihead attention

The proposed U-Net 3D + MHA architecture for brain segmentation is shown in
Fig. 3. The model takes input images of size 128x128x128 pixels with three
channels representing different imaging modalities. The model follows a 3D
U-Net architecture, which is widely used for medical image segmentation tasks.
It consists of an encoding path and a decoding path. In the encoding path, the
input image undergoes a series of operations to extract hierarchical features.
Convolutional blocks with increasing filter sizes are applied, followed by
max-pooling layers to downsample the feature maps and capture contextual
information.

In the middle of the network, a convolutional block with a large number of
filters is employed to capture high-level features while preserving spatial
information. This helps in accurately localizing tumor regions.

The decoding path involves upsampling operations to restore the resolution of
the feature maps. Multi-head attention modules are incorporated at each
decoding stage to fuse features from the corresponding encoding layers. These
attention modules utilize 1x1x1 convolutions to reduce dimensionality,
followed by convolutional blocks to refine the features.

The final output of the model, as shown in Fig.3 is obtained through a 1x1x1
convolutional layer with softmax activation, which produces a segmentation map
with multiple classes, including tumor regions. This map helps delineate the
tumor boundaries and assists in subsequent analysis and treatment planning.

The overall architecture is implemented using TensorFlow and Keras, popular
deep learning frameworks for medical image analysis. By passing a
128x128x128x3 input image through the model, it generates a corresponding
segmentation map that highlights the tumor regions, aiding in the accurate
identification and analysis of brain tumors.

Figure 3: U-Net 3D + MHA architecture for brain tumor segmentation. It
features an encoding and decoding path with multihead attention modules to
define features and a softmax layer to produce a segmentation map highlighting
different tumor regions. Implemented using TensorFlow and Keras, the model
accurately identifies and analyzes brain tumors from 128x128x128 pixel input
images with three channels.

##  4 Hyperparameter optimisation

In this section, the results of hyperparameter optimization experiments are
presented. The learning rate and batch size are varied to determine their
impact on the model’s overall training and validation accuracies along with
their respective losses.

Under the batch size of 8 and 16, 4 tests were run at learning rates of
$10^{-2}$, and $10^{-3}$ to evaluate the effect of changing these parameters
on training and validation accuracies and their respective losses.

$0$$10$$20$$30$$40$$50$$0.2$$0.4$$0.6$$0.8$$1$EpochsAccuracy$0.2$$0.4$$0.6$$0.8$$1$Loss | $0$$10$$20$$30$$40$$50$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsAccuracy$0.2$$0.4$$0.6$$0.8$$1$Loss
---|---
$0$$10$$20$$30$$40$$50$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsAccuracy$0.2$$0.4$$0.6$$0.8$$1$Loss | $0$$10$$20$$30$$40$$50$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsAccuracy$0.2$$0.4$$0.6$$0.8$$1$Loss
Figure 4: Comparison of the training and validation accuracies with respective
losses at LR=0.001 with a batch size of 16 at 50 epochs.

Figure 4 shows the model’s progress over multiple epochs, with each epoch
reporting the training and validation losses and accuracies. The model starts
with a higher loss and lower accuracy, but as training progresses, the loss
decreases and the accuracy improves for both training and validation datasets.
This indicates that the model is learning to segment brain tumors more
effectively over time. The best epoch appears to be around epoch 20, as it
exhibits the lowest validation loss and the highest validation accuracy,
precision, sensitivity, and dice coefficients. However, after epoch 20, the
model starts to show signs of overfitting, with increasing validation loss and
fluctuations in the validation metrics.

$0$$10$$20$$30$$40$$50$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsAccuracyTraining
AccuracyValidation Accuracy$0.2$$0.4$$0.6$$0.8$$1$LossValidation LossTraining
Loss Figure 5: Comparison of the training and validation accuracies with
respective losses at LR=0.001 with a batch size of 8 at 50 epochs.

In Fig. 5, the results of the proposed model are presented at a learning rate
of 10*-3 and a batch size of 8. It was observed that the training accuracy
increased gradually with each epoch, indicating the model’s ability to
effectively learn from the data. The training loss also showed a decreasing
trend, implying that the model’s predictions progressively converged towards
the ground truth. For the validation set, the highest accuracy and lowest loss
were achieved at epoch 43.

$0$$10$$20$$30$$40$$50$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsAccuracyTraining
AccuracyValidation Accuracy$0.2$$0.4$$0.6$$0.8$$1$LossValidation LossTraining
Loss Figure 6: Comparison of the training and validation accuracies with
respective losses at LR=0.01 with a batch size of 16 at 50 epochs.

The Fig. 6 represents the training results of the deep learning model, using a
batch size of 16 and a learning rate of 0.01. As the training progressed, the
loss steadily decreased, indicating that the model was learning from the data.
The accuracy and other evaluation metrics consistently improved over time,
showing the model’s ability to effectively segment and classify brain tumor
regions. The validation loss and evaluation metrics on the validation set also
demonstrated similar trends, indicating that the model was generalizing well
to unseen data.

Table 1: Performance Metrics for U-Net architecture with Multihead Attention at 50 epochs with a batch size of 8 Learning_Rate | Train_acc | Val_acc | Train_loss | Val_loss
---|---|---|---|---
0.01 | 0.9598 | 0.9476 | 0.1223 | 0.2969
0.001 | 0.9616 | 0.9307 | 0.1131 | 0.2972

Lastly, Figure 7 shows the training and validation accuracies, losses, and
other metrics over multiple epochs. At the beginning of training, both
training and validation accuracies and dice coefficients are relatively low,
while the losses are high. Overfitting can be observed in this Figure 7, as
the training accuracy and dice coefficients continue to improve over time,
while the validation accuracy starts to plateau and even slightly decline
after a certain point. Additionally, the validation loss initially decreases,
but then it starts to increase again, which is another indication of
overfitting. The best epoch selection can be based on the point where the
validation accuracy is highest and the validation loss is at its lowest. In
this case, the best epoch would be around epoch 25-30, where the validation
accuracy and dice coefficients reach their peaks, and the validation loss is
minimized. After that point, the model starts overfitting, as indicated by the
decreasing validation accuracy and increasing validation loss.

$0$$10$$20$$30$$40$$50$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsAccuracyTraining AccuracyValidation Accuracy$0.2$$0.4$$0.6$$0.8$$1$LossValidation LossTraining Loss Figure 7: Comparison of the training and validation accuracies with respective losses at LR=0.001 with a batch size of 16 at 50 epochs. Table 2: Performance Metrics for U-Net architecture with Multihead Attention at 50 epochs with a batch size of 16 Learning_Rate | Train_acc | Val_acc | Train_loss | Val_loss
---|---|---|---|---
0.01 | 0.9522 | 0.9502 | 0.1631 | 0.3499
0.001 | 0.9580 | 0.9317 | 0.1346 | 0.2855

From Tables 1 and 2, it can be concluded that there’s not much variation in
accuracies and losses for both the training and validation sets, but we
generally saw our model overfitting after 25 epochs, and the best way to cater
such problem is to train the model till the point where validation loss is
minimum and validation accuracy is the highest, for that the concept of early
stopping can be utilized here for better and efficient performance of the
model.

##  5 Results and Discussion

In this section, the results of the proposed U-Net 3D architecture with
multihead attention for brain tumor segmentation using MRI scans are
described. The results are summarized in the following sub-sections. The
performance metrics used to evaluate our model’s performance on the BraTS 2020
dataset are defined as follows.

###  5.1 Performance Metrics

  * •

Loss: The loss function quantifies the dissimilarity between the predicted
segmentation and the ground truth. It measures the model’s ability to minimize
the difference between the predicted and actual pixel values. In our
experiments, we used the binary cross-entropy loss defined as:

$\text{Loss}=-\frac{1}{N}\sum_{i=1}^{N}\left(y_{i}\log(p_{i})+(1-y_{i})\log(1-p_{i})\right)$
(1)

where $N$ is the total number of pixels, $y_{i}$ is the ground truth label (0
or 1) for pixel $i$, and $p_{i}$ is the predicted probability of pixel $i$
belonging to the positive class.

  * •

Accuracy: Accuracy measures the proportion of correctly classified pixels out
of the total number of pixels. It is defined as:

$\text{Accuracy}=\frac{\text{TP}+\text{TN}}{\text{TP}+\text{TN}+\text{FP}+\text{FN}}$
(2)

where TP represents the true positive, TN represents the true negative, FP
represents the false positive, and FN represents the false negative.

  * •

Mean Intersection over Union (IOU): IOU, also known as the Jaccard Index,
measures the overlap between the predicted segmentation and the ground truth.
It is defined as the ratio of the intersection to the union of the predicted
and ground truth masks:

$\text{IOU}=\frac{\text{Intersection}}{\text{Union}}$ (3)

  * •

Dice Coefficient: The Dice Coefficient is another metric that quantifies the
similarity between the predicted and ground truth masks. It is defined as:

$\text{Dice}=\frac{2\times\text{Intersection}}{\text{Prediction}+\text{Ground
Truth}}$ (4)

  * •

Precision: Precision measures the proportion of correctly predicted positive
pixels out of all the pixels predicted as positive. It is defined as:

$\text{Precision}=\frac{\text{TP}}{\text{TP}+\text{FP}}$ (5)

  * •

Sensitivity: Sensitivity, also known as recall or true positive rate, measures
the proportion of correctly predicted positive pixels out of all the actual
positive pixels. It is defined as:

$\text{Sensitivity}=\frac{\text{TP}}{\text{TP}+\text{FN}}$ (6)

  * •

Specificity: Specificity measures the proportion of correctly predicted
negative pixels out of all the actual negative pixels. It is defined as:

$\text{Specificity}=\frac{\text{TN}}{\text{TN}+\text{FP}}$ (7)

###  5.2 Experimental Setup

The model was traned using deep learning architectures based on U-Net with
multihead attention. The networks were trained on an HPC server with the
following configuration: 2 x 32-core AMD EPYC 7452 Processors, 384 GB RAM, 1 x
NVIDIA V100 GPU (32 GB). Adam optimizer with a learning rate of 0.001 and a
batch size of 8 were used to generalise model’s performance at 25 epochs. The
model was evaluated using various metrics to assess its performance on the
BraTS 2020 dataset.

###  5.3 Discussion

Upon analyzing the training log for 60 epochs, the proposed system based on
the U-Net architecture with multihead attention, achieved DSC values of
1.0000, 1.0000, and 1.0000 for the edema, necrotic, and enhancing regions,
respectively in Fig. 8. These results demonstrate the model’s ability to
accurately and effectively capture the spatial extent of each class.

$0$$5$$10$$15$$20$$25$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsDSC Edema, Necrotic,
EnhancingDSC_NecroticDSC_EdemaDSC_Enhancing Figure 8: Class Specific DSC
accuracies at LR=0.001, batch size=8, till 25 epochs

Table 3 presents the performance metrics obtained by evaluating the U-Net
architecture with Multihead Attention for 60 epochs on three distinct classes:
Edema, Necrotic, and Enhancing. These metrics serve as quantitative measures
to assess the effectiveness of the proposed model in segmenting brain tumor
regions accurately.

Table 3: Performance Metrics for U-Net architecture with Multihead Attention at 25 epochs Metrics | Value
---|---
DSC Accuracy | 0.9932
Precision | 0.9558
Sensitivity | 0.9443
Specificity | 0.9853
DSC Loss | 0.2343

Precision measures the proportion of correctly predicted positive samples out
of the total predicted positive samples. The U-Net architecture with Multihead
Attention achieved impressive Precision value of 0.9558 overall. This value
indicate a low rate of false positive predictions.

Sensitivity, also known as the True Positive Rate or Recall, quantifies the
model’s ability to correctly identify positive samples from the ground truth.
The U-Net architecture with Multihead Attention demonstrated high Sensitivity
value of 0.9443 for all the three classes. This result indicates a low rate of
false negatives, suggesting the model’s effectiveness in capturing the
majority of positive samples.

Specificity measures the model’s ability to correctly identify negative
samples from the ground truth. The U-Net architecture with Multihead Attention
achieved notable Specificity value of 0.9853. This value implies a low rate of
false positives for negative samples.

Finally, DSC Loss represents the dissimilarity between the predicted and
ground truth segmentations. The U-Net architecture with Multihead Attention
achieved low DSC Loss value of 0.2343. This values demonstrates the model’s
ability to minimize the discrepancy between the predicted and ground truth
segmentations.

$0$$5$$10$$15$$20$$25$$0$$0.2$$0.4$$0.6$$0.8$$1$EpochsPerformance MetricsDSC
AccuracyPrecisionSensitivitySpecificity Figure 9: Performance metrics of the
model at LR=0.001, with a batch size of 8 till 25 epochs

Overall, the results presented in Fig. 9 highlight the efficacy of the U-Net
architecture with Multihead Attention in accurately segmenting brain tumor
regions. The high values of DSC Accuracy, Precision, Sensitivity, and
Specificity, along with the low DSC Loss values, substantiate the model’s
capability to capture both the spatial extent and fine details of the tumor
classes. These findings emphasize the potential of the proposed approach in
improving tumor segmentation and aiding in clinical decision-making.

Overall, the experimental results indicate that U-Net architecture with
multihead attention generally outperforms many great architectures for brain
tumor segmentation across all three classes. The plots provide valuable
insights into the performance of the model and can help in making informed
decisions when choosing a model for brain tumor segmentation tasks.

However, it is important to consider other factors beyond DSC accuracies when
evaluating the performance of the models. For example, the computational
complexity, training time, and model interpretability are also essential
aspects to consider. The U-Net architecture with multihead attention, provides
certain benefits in terms of interpretability and capturing temporal
dependencies in the MRI scans. On the other hand,it also offers better
scalability and efficiency for larger datasets.

In conclusion, our architecture demonstrated strong performance in brain tumor
segmentation, achieving high DSC accuracies for the individual tumor regions.

###  5.4 Comparison with some state of the art Architectures

In this research, we compared the performance of our proposed U-Net
architecture with multihead attention against several state-of-the-art models
in medical image segmentation. Table 4 presents a comprehensive comparison of
our models with the selected architectures in terms of these evaluation
metrics. The goal of medical image segmentation is to accurately identify and
delineate different regions of interest within medical images, such as tumors
or abnormalities. Accurate segmentation plays a crucial role in medical
diagnosis and treatment planning. We evaluated the models using various
metrics, including accuracy, mean intersection over union (IOU), dice
coefficient, precision, sensitivity, and specificity.

The U-Net architecture with multihead attention achieved an accuracy of 95.19%
and a dice coefficient of 0.9932 on the training set. On the validation set,
it achieved an accuracy of 95.09% and a dice coefficient of 0.9950. For the
class-specific dice coefficients, the U-Net architecture obtained 1.0000 for
necrotic regions, 1.0000 for edema regions, and 1.0000 for enhancing regions.

Table 4: Comparison with the State of the Art Image Segmentation Architectures
on BraTS 2020 Dataset

Architecture | Validation Accuracy (%) | Dice Coefficient | Dice Coefficient | Dice Coefficient | Dice Coefficient
---|---|---|---|---|---
|  |  | (Necrotic) | (Edema) | (Enhancing)
U-Net with multihead attention | 95.19 | 0.9950 | 1.0000 | 1.0000 | 1.0000
Dense121 U-Net[8] | 94.78 | 0.9324 | 0.959 | 0.943 | 0.892
FCN-8s[26] | 93.85 | 0.9102 | 0.9964 | 0.9943 | 0.9972
SegNet [3] | 92.71 | 0.8821 | 0.8632 | 0.9147 | 0.8354

As shown in table 4, Comparing our models with the state-of-the-art
architectures, we found that our U-Net architecture outperformed FCN-8s [26],
SegNet[3], and DenseNet in terms of accuracy, dice coefficient, and class-
specific dice coefficients. It achieved higher accuracy and dice coefficient
values compared to FCN-8s and SegNet. Dense121 U-Net[8], which combines the
DenseNet backbone with the U-Net architecture, achieved an accuracy of 94.78%
and a dice coefficient of 0.9324 on the training set. On the validation set,
it achieved an accuracy of 94.85% and a dice coefficient of 0.9085. For the
class-specific dice coefficients, Dense121 Unet obtained 0.9965 for necrotic
regions, 0.9958 for edema regions, and 0.9959 for enhancing regions.

In conclusion, our U-Net architecture with multihead attention, demonstrated
promising results compared to state-of-the-art models in medical image
segmentation. This architectures provide accurate segmentation for various
regions of interest in medical images, including necrotic, edema, and
enhancing regions.

###  5.5 Segmentation Results

In this section, the segmentation results obtained by applying the model to
the test data are showcased. The segmentation results provide insights into
the accuracy and performance of our model in identifying and segmenting brain
tumor regions.

The predicted segmentation results were evaluated using the test dataset,
consisting of brain tumor images. The ground truth segmentations by expert
neuro-radiologists were available for comparison, allowing for the assessment
of the model’s performance.

The segmentation results were analyzed based on several metrics, including
precision, recall, and the Dice coefficient. These metrics provide
quantitative measures of the model’s accuracy in capturing the tumor regions
and aligning them with the ground truth segmentations.

As it can be seen in Fig. 10, a visual analysis of the segmentation results
was also performed to assess the qualitative performance of the model. The
predicted tumor regions were overlaid onto the original brain images, allowing
for visual comparison with the ground truth segmentations. This qualitative
evaluation provides insights into the model’s ability to accurately delineate
tumor boundaries and capture tumor heterogeneity.

The segmentation results demonstrate the efficacy of our proposed model in
accurately segmenting brain tumor regions. The combination of quantitative
evaluation metrics and visual analysis provides a comprehensive assessment of
the model’s performance and highlights its potential in assisting medical
professionals in the diagnosis and treatment planning of brain tumors.

Figure 10: This figure shows Segmentation results obtained by the model on
test data, showcasing accurate identification and delineation of brain tumor
regions. The predicted tumor regions are overlaid onto the original brain
images for visual comparison with the ground truth segmentations. The results
demonstrate the effectiveness of the model in capturing tumor boundaries and
aiding in brain tumor analysis.

##  6 Conclusion

In conclusion, the Hybrid Multihead Attentive U-Net architecture has shown
great promise in the task of brain tumor segmentation. Through extensive
experimentation and analysis, we have demonstrated the impact of
hyperparameter optimization on the performance of the model. The results
obtained highlight the importance of fine-tuning parameters such as learning
rate, number of epochs, and steps per epoch to achieve optimal segmentation
accuracy while minimizing training time.

The Hybrid Multihead Attentive U-Net architecture leverages the U-Net’s
ability to capture contextual information and the attention mechanisms’
capability to selectively focus on relevant features. This combination enables
the model to effectively delineate tumor boundaries and enhance the accuracy
of segmentation. The attention mechanism helps the model to prioritize
important regions and suppress irrelevant information, resulting in more
precise tumor segmentation.

The experiments conducted on various hyperparameters revealed valuable
insights. Adjusting the learning rate played a critical role in achieving
accurate segmentations. Fine-tuning the learning rate allowed the model to
converge efficiently and avoid overshooting or getting stuck in sub-optimal
solutions. Additionally, the number of epochs had a significant impact on the
performance of the model.

It was observed that too few epochs resulted in underfitting, whereas
excessive epochs led to overfitting. Identifying the optimal number of epochs
is crucial to balance model complexity and generalization.

Furthermore, the steps per epoch parameter influenced the model’s convergence
and training time. By carefully selecting the number of steps per epoch, we
can ensure that the model sufficiently learns from the data without
unnecessary computations. This parameter optimization helped in achieving
better accuracy while reducing the overall training time.

The proposed architecture and hyperparameter optimization techniques have
significant implications in the field of medical imaging, particularly in
brain tumor segmentation. Accurate segmentation plays a vital role in clinical
decision-making, treatment planning, and monitoring disease progression. By
automating the segmentation process, the Hybrid Multihead Attentive U-Net
architecture can assist medical professionals in efficiently and accurately
identifying tumor regions, facilitating timely intervention and personalized
treatment strategies.

Moreover, the application of this technique extends beyond tumor segmentation.
The Hybrid Multihead Attentive U-Net architecture can also be leveraged in
medical techniques like brain transplantation. Preoperative planning for brain
transplantation requires precise identification and localization of the donor
and recipient brain regions. By employing the proposed architecture, accurate
segmentation of brain structures can be achieved, aiding in surgical planning
and ensuring successful transplantation.

In summary, the Hybrid Multihead Attentive U-Net architecture has demonstrated
its effectiveness in brain tumor segmentation. The hyperparameter optimization
experiments have shed light on the importance of parameter fine-tuning to
achieve optimal performance. With its potential applications in medical
imaging and procedures like brain transplantation, this technique opens new
avenues for advancements in healthcare and improved patient outcomes. Further
research and validation on larger datasets and in clinical settings will be
valuable to validate and refine the proposed architecture for real-world
deployment.

## Acknowledgements

Thanks to the School of Interdisciplinary Engineering Sciences(SINES), NUST,
for providing us the computing fascilities to successfully complete the
simulations and carry out the research successfully.

## References

  * [1] Nagwa M Aboelenein, Piao Songhao, Anis Koubaa, Alam Noor, and Ahmed Afifi.  Httu-net: Hybrid two track u-net for automatic brain tumor segmentation.  IEEE Access, 8:101406–101415, 2020.
  * [2] Parvez Ahmad, Saqib Qamar, Linlin Shen, and Adnan Saeed.  Context aware 3d unet for brain tumor segmentation.  In Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries: 6th International Workshop, BrainLes 2020, Held in Conjunction with MICCAI 2020, Lima, Peru, October 4, 2020, Revised Selected Papers, Part I 6, pages 207–218. Springer, 2021.
  * [3] Salma Alqazzaz, Xianfang Sun, Xin Yang, and Len Nokes.  Automated brain tumor segmentation on multi-modal mr image using segnet.  Computational Visual Media, 5:209–219, 2019.
  * [4] Ujjwal Baid, Sanjay Talbar, Swapnil Rane, Sudeep Gupta, Meenakshi H Thakur, Aliasgar Moiyadi, Nilesh Sable, Mayuresh Akolkar, and Abhishek Mahajan.  A novel approach for fully automatic intra-tumor segmentation with 3d u-net architecture for gliomas.  Frontiers in computational neuroscience, 14:10, 2020.
  * [5] Laura Mora Ballestar and Veronica Vilaplana.  Mri brain tumor segmentation and uncertainty estimation using 3d-unet architectures.  In International MICCAI Brainlesion Workshop, pages 376–390. Springer, 2020.
  * [6] Jose Bernal, Kaisar Kushibar, Daniel S Asfaw, Sergi Valverde, Arnau Oliver, Robert Martí, and Xavier Lladó.  Deep convolutional neural networks for brain image analysis on magnetic resonance imaging: a review.  Artificial intelligence in medicine, 95:64–81, 2019.
  * [7] Jie Chang, Xiaoci Zhang, Minquan Ye, Daobin Huang, Peipei Wang, and Chuanwen Yao.  Brain tumor segmentation based on 3d unet with multi-class focal loss.  In 2018 11th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics (CISP-BMEI), pages 1–5. IEEE, 2018.
  * [8] Necip Cinar, Alper Ozcan, and Mehmet Kaya.  A hybrid densenet121-unet model for brain tumor segmentation from mr images.  Biomedical Signal Processing and Control, 76:103647, 2022.
  * [9] T. S. Deepthi Murthy and G. Sadashivappa.  Brain tumor segmentation using thresholding, morphological operations and extraction of features of tumor.  In 2014 International Conference on Advances in Electronics Computers and Communications, pages 1–6, 2014.
  * [10] Wankai Deng, Wei Xiao, He Deng, and Jianguo Liu.  Mri brain tumor segmentation with region growing method based on the gradients and variances along and inside of the boundary curve.  In 2010 3rd International Conference on Biomedical Engineering and Informatics, volume 1, pages 393–396, 2010.
  * [11] Michał Futrega, Alexandre Milesi, Michał Marcinkiewicz, and Pablo Ribalta.  Optimized u-net for brain tumor segmentation.  In International MICCAI Brainlesion Workshop, pages 15–29. Springer, 2021.
  * [12] Ali Hatamizadeh, Vishwesh Nath, Yucheng Tang, Dong Yang, Holger R Roth, and Daguang Xu.  Swin unetr: Swin transformers for semantic segmentation of brain tumors in mri images.  In International MICCAI Brainlesion Workshop, pages 272–284. Springer, 2021.
  * [13] Kai Hu, Qinghai Gan, Yuan Zhang, Shuhua Deng, Fen Xiao, Wei Huang, Chunhong Cao, and Xieping Gao.  Brain tumor segmentation using multi-cascaded convolutional neural networks and conditional random field.  IEEE Access, 7:92615–92629, 2019.
  * [14] Konstantinos Kamnitsas, Christian Ledig, Virginia FJ Newcombe, Joanna P Simpson, Andrew D Kane, David K Menon, Daniel Rueckert, and Ben Glocker.  Efficient multi-scale 3d cnn with fully connected crf for accurate brain lesion segmentation.  Medical image analysis, 36:61–78, 2017.
  * [15] Adel Kermi, Issam Mahmoudi, and Mohamed Tarek Khadir.  Deep convolutional neural networks using u-net for automatic brain tumor segmentation in multimodal mri volumes.  In Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries: 4th International Workshop, BrainLes 2018, Held in Conjunction with MICCAI 2018, Granada, Spain, September 16, 2018, Revised Selected Papers, Part II 4, pages 37–48. Springer, 2019.
  * [16] Jianwei Lin, Jiatai Lin, Cheng Lu, Hao Chen, Huan Lin, Bingchao Zhao, Zhenwei Shi, Bingjiang Qiu, Xipeng Pan, Zeyan Xu, et al.  Ckd-transbts: clinical knowledge-driven hybrid transformer with modality-correlated cross-attention for brain tumor segmentation.  IEEE transactions on medical imaging, 2023.
  * [17] Lina Liu, Lichao Mou, Xiao Xiang Zhu, and Mrinal Mandal.  Skin lesion segmentation based on improved u-net.  In 2019 IEEE Canadian conference of electrical and computer engineering (CCECE), pages 1–4. IEEE, 2019.
  * [18] Bjoern H Menze, Andras Jakab, Stefan Bauer, Jayashree Kalpathy-Cramer, Keyvan Farahani, Justin Kirby, Yuliya Burren, Nicole Porz, Johannes Slotboom, Roland Wiest, et al.  The multimodal brain tumor image segmentation benchmark (brats).  IEEE transactions on medical imaging, 34(10):1993–2024, 2014.
  * [19] Mehreen Mubashar, Hazrat Ali, Christer Grönlund, and Shoaib Azmat.  R2u++: a multiscale recurrent residual u-net with dense skip connections for medical image segmentation.  Neural Computing and Applications, 34(20):17723–17739, 2022.
  * [20] Mehrdad Noori, Ali Bahri, and Karim Mohammadi.  Attention-guided version of 2d unet for automatic brain tumor segmentation.  In 2019 9th international conference on computer and knowledge engineering (ICCKE), pages 269–275. IEEE, 2019.
  * [21] Kameswara Rao Pedada, Bhujanga Rao, Kiran Kumar Patro, Jaya Prakash Allam, Mona M Jamjoom, and Nagwan Abdel Samee.  A novel approach for brain tumour detection using deep learning based technique.  Biomedical Signal Processing and Control, 82:104549, 2023.
  * [22] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18, pages 234–241. Springer, 2015.
  * [23] Kurt E Schlageter, Peter Molnar, Gregory D Lapin, and Dennis R Groothuis.  Microvessel organization and structure in experimental brain tumors: microvessel populations with distinctive structural and functional properties.  Microvascular research, 58(3):312–328, 1999.
  * [24] Hoo-Chang Shin, Holger R. Roth, Mingchen Gao, Le Lu, Ziyue Xu, Isabella Nogues, Jianhua Yao, Daniel Mollura, and Ronald M. Summers.  Deep convolutional neural networks for computer-aided detection: Cnn architectures, dataset characteristics and transfer learning.  IEEE Transactions on Medical Imaging, 35(5):1285–1298, 2016.
  * [25] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [26] Yabiao Wang, Zeyu Sun, Chang Liu, Wenbo Peng, and Juhua Zhang.  Mri image segmentation by fully convolutional networks.  In 2016 IEEE International Conference on Mechatronics and Automation, pages 1697–1702. IEEE, 2016.
  * [27] Yuan Xue, Tao Xu, Han Zhang, L Rodney Long, and Xiaolei Huang.  Segan: Adversarial network with multi-scale l 1 loss for medical image segmentation.  Neuroinformatics, 16:383–392, 2018.
  * [28] Wenlu Zhang, Rongjian Li, Houtao Deng, Li Wang, Weili Lin, Shuiwang Ji, and Dinggang Shen.  Deep convolutional neural networks for multi-modality isointense infant brain image segmentation.  NeuroImage, 108:214–224, 2015.
  * [29] Liya Zhao and Kebin Jia.  Deep feature learning with discrimination mechanism for brain tumor segmentation and diagnosis.  In 2015 international conference on intelligent information hiding and multimedia signal processing (IIH-MSP), pages 306–309. IEEE, 2015.
  * [30] Zexun Zhou, Zhongshi He, and Yuanyuan Jia.  Afpnet: A 3d fully convolutional neural network with atrous-convolution feature pyramid for brain tumor segmentation via mri images.  Neurocomputing, 402:235–244, 2020.
  * [31] Zhiqin Zhu, Xianyu He, Guanqiu Qi, Yuanyuan Li, Baisen Cong, and Yu Liu.  Brain tumor segmentation based on the fusion of deep semantics and edge information in multimodal mri.  Information Fusion, 91:376–387, 2023.


# Rederiving the Upper Bound for Halving Edges using Cardano’s Formula

Pintu Chauhan  Manjish Pal  Napendra Solanki  Department of Computer Science,
NIT-Meghalaya,
Shillong, India<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper we rederive an old upper bound on the number of halving edges
present in the halving graph of an arbitrary set of $n$ points in 2-dimensions
which are placed in general position. We provide a different analysis of an
identity discovered by Andrejak et al, to rederive this upper bound of
$O(n^{4/3})$. In the original paper of Andrejak et al. the proof is based on a
naive analysis whereas in this paper we obtain the same upper bound by
tightening the analysis thereby opening a new door to derive these upper
bounds using the identity. Our analysis is based on a result of Cardano for
finding the roots of a cubic equation. We believe that our technique has the
potential to derive improved bounds on the number of halving edges.

††footnotetext: Received: xx xxxxx 20xx, Accepted: xx xxxxx 20xx.

###### keywords:

$k$-sets , Halving edges , Graphs Mathematics Subject Classification : 68R05,
68R10, 52C10

##  1 Introduction

Combinatorial Geometry is a field of discrete mathematics which deals with
counting certain discrete structures in geometric spaces. There are several
questions in this field which are very simple to state but finding the true
solution is notoriously hard. One of the most important questions in this
field is the celebrated $k$-set problem. Given a set of $n$ points in
$\mathbb{R}^{d}$, a $k$-set is a subset of the given points which can be
separated by a $(d-1)$-dimensional hyperplane. The question is to find
$f_{d}^{k}(n)$ which is the maximum number of such sets possible for an
arbitrary set of $n$ point in general position. This question remains to be
elusive even in 2 dimensions, the status of which is open for over forty
years. Despite significant efforts put on this problem there is still a big
gap between the upper and lower bounds on $f_{2}^{k}(n)$. In this paper we
focus our study on $f_{2}^{k}(n)$. The special case of $f_{2}^{n/2}(n)$ is
called the _halving number problem_. From the perspective of finding upper
bounds it is very easy to see that $f_{2}^{k}(n)$ is at most $O(n^{k})$. One
can also observe that corresponding to every valid partition of the point set
into $k$ and $n-k$ points there exists a unique line segment joining two
points belonging to the set that divides the point sets into $k-1$ and $n-k-1$
points. This line segment is called a $k$-edge. The _geometric graph_
constructed as such is called the $k$-edge graph. This observation leads us to
conclude that $f_{2}^{k}(n)$ is atmost the number of edges in this graph which
can be atmost $O(n^{2})$. For $k=n/2$, this graph is called the _halving edge
graph_. It is also well known that techniques to prove bounds for
$f_{2}^{n/2}(n)$ can be translated to the general case of $f_{2}^{k}(n)$.

The first non trivial upper bounds for the halving case was obtained by Lovász
[7] and Erdős, Lovász, Simmons and Straus [5] proved the upper bound of
$O(n^{3/2})$ and a lower bound of $O(n\log n)$ in 1970’s. The upper bound was
later improved to $O(n^{3/2}\log^{*}n)$ by Pach, Steiger and Szemerédi [11] in
1992. This was later improved to $O(n^{4/3})$ by Dey [3]. This bound was
rederived by Andrejak, Aronov, Har-Peled, Seidel, Welzl [1] in a paper that
also provided an identity connecting the number of halving edges and the
number of _crossings_ in the halving edge graph in an arbitrary set of $n$
points in the plane. The lower bound was improved by Tóth to
$ne^{\Omega(\sqrt{\log n})}$ [14]. This bound has been further refined
recently by Nivasch to $\Omega(ne^{\sqrt{\ln 4}\sqrt{\ln n}}/\sqrt{\ln n})$
[10]. From the lower bound perspective another line of approach has been
considered by looking into $\gamma$-dense sets. These are sets in which the
ratio of the maximum and minimum interpoint distance is atmost
$\gamma\sqrt{n}$. For dense sets the upper bound can be improved to
$O(n^{7/6})$ [6]. For the $d$-dimensional case the upper and lower bounds are
known using complex techniques in combinatorics and algebraic geometry. It is
known that $f_{d}^{n/2}(n)=O(n^{d-c_{d}})$ [2] where $c_{d}$ is a constant
that goes to zero as $d$ increases. For lower bounds it is known that given a
construction of $\Omega(ng(n))$ halving edges in 2-dimension, one can extend
this construction to $d$-dimensions, achieving a lower bound of
$\Omega(n^{d-1}g(n))$ [8]. There are certain results which are obtained by
looking into special properties of the graph in three and four dimensions [4,
12, 13, 9].

##  2 Preliminaries

In this paper we focus on the properties of the halving edge graph and the
identity proven by Andrejak et al. The _halving graph_ is graph defined by
joining all the pair of points by segments whose corresponding lines partition
the point set into two equal parts i.e. consisting of $(n-2)/2$ points where
$n$ is even. This graph has several interesting properties most notably the
_Lovász Local Lemma_.

###  2.1 Lovász Local Lemma and Antipodality

This result was proven by Lovász in one of the early papers on this problem.
Most of the upper bound results on this problem use this lemma. The lemma
basically says that if we consider any halving edge and rotate the line
corresponding to that segment about one of its end points in both the
directions (clockwise and anticlockwise) then the first point that this
rotating line meets also form a halving edge when connected with the point
about which the rotation is performed. Although this result is a result that
only reveals local properties of the point set, it is helpful in getting some
global properties regarding the halving edge graph. This technique was used by
the proof of Dey to derive the bounds of $O(n^{4/3})$.

###  2.2 Convex Chains and Dey’s Original proof

Dey in his original paper uses the notion of convex chains to derive the bound
of $O(n^{4/3})$. The notion of convex chains is based on using the Lovász
Lemma to derive an equivalence relation that results in the formation of
convex chains. In the paper, Dey proves that the number of convex chains
constructed as such is atmost $O(n)$ and two convex chains cross at most twice
with each other. Thus, creating at most $O(n^{2})$ crossings which after using
the Crossing Number Inequality again implies that the number of edges in the
halving edge graph is atmost $O(n^{4/3})$.

###  2.3 Main Identity

In this section we describe the main identity that is proven by Andrejak et
al. that gives an exact relation between the number of crossings in the
halving edge graph and the degree of nodes in the graph. This identity can be
proven using doing an induction and performing continuous motion on the set of
points.

$\displaystyle\mbox{cr}(G)+\sum_{v}\binom{(d_{v}+1)/2}{2}=\binom{n/2}{2}$

##  3 Obtaining Dey’s Bound using Cardano’s Formula

In this section, we prove some results regarding the halving edge graph which
we use to get a different analysis of the previous identity. Proofs of these
are omitted as they are fairly easy to see.

######  Lemma 3.1.

Let $n_{i}$ be the number of nodes with degree $i$ in a halving edge graph $G$
and $d_{v}$ be the degree of a node $v$, then

$\displaystyle\sum_{v}d_{v}^{2}=\sum_{i}i^{2}n_{i}$

######  Lemma 3.2.

Let $n_{i}$ be the number of nodes with degree $i$ in a halving edge graph $G$
then $n_{i}$ is odd and $n_{i}\leq n_{j}\mbox{ }\forall i\geq j$.

######  Lemma 3.3.

Given an undirected graph $G$, if $d$ is the maximum degree of $G$ then
$d\geq\frac{2m}{n}$.

###  3.1 Cardano’s Formula

Cardano’s formula is a way to find the roots of a cubic polynomial. It was
first published by Cardano in 1545. The formula says that given a cubic
polynomial of the form

$\displaystyle ax^{3}+bx^{2}+cx+d=0$

The solution is given as

$\displaystyle x$ $\displaystyle=$
$\displaystyle\sqrt[3]{\left(\frac{-b^{3}}{27a^{3}}+\frac{bc}{6a^{2}}-\frac{d}{2a}\right)+\sqrt{\left(\frac{-b^{3}}{27a^{3}}+\frac{bc}{6a^{2}}-\frac{d}{2a}\right)^{2}+\left(\frac{c}{3a}-\frac{b^{2}}{9a^{2}}\right)^{3}}}$
$\displaystyle+$
$\displaystyle\sqrt[3]{\left(\frac{-b^{3}}{27a^{3}}+\frac{bc}{6a^{2}}-\frac{d}{2a}\right)-\sqrt{\left(\frac{-b^{3}}{27a^{3}}+\frac{bc}{6a^{2}}-\frac{d}{2a}\right)^{2}+\left(\frac{c}{3a}-\frac{b^{2}}{9a^{2}}\right)^{3}}}-\frac{b}{3a}$

This formula can be simplified as

$\displaystyle x$ $\displaystyle=$
$\displaystyle\\{q+[q^{2}+(r-p^{2})^{3}]^{1/2}\\}^{1/3}+{\\{q-[q^{2}+(r-p^{2})^{3}]^{1/2}\\}^{1/3}}+p$

where

$\displaystyle p=\frac{-b}{3a},q=p^{3}+\frac{(bc-3ad)}{6a^{2}},r=\frac{c}{3a}$

######  Theorem 3.1.

The number of halving edges for an arbirary set of $n$ points is atmost
$O(n^{4/3})$.

###### Proof.

We prove this using a different analysis of the identity proven by Andrejak et
al.

$\displaystyle\mbox{cr}(G)+\sum_{v}\binom{(d_{v}+1)/2}{2}=\binom{n/2}{2}$

In the paper by Andrejak et al, the second term in the identity which is a
positive quantity is ignored to be 0, there by implying the

$\displaystyle\mbox{cr}(G)\leq n^{2}/8-n/8$

from which we can conclude that $\mbox{cr}(G)=O(n^{4/3})$ meeting the bound
obtained by Dey. In this proof we do not ignore the second and write the
identity as an inequality with variable $m$ where $m$ is the number of edges

$\displaystyle\mbox{cr}(G)$ $\displaystyle+$
$\displaystyle\sum_{v}\left(\frac{d^{2}-1}{2}\right)=\frac{n^{2}}{8}-\frac{n}{8}$
$\displaystyle\mbox{cr}(G)$ $\displaystyle=$
$\displaystyle\frac{n^{2}}{8}-\frac{3n}{8}-\sum_{v}\frac{d^{2}}{2}$
$\displaystyle\mbox{cr}(G)$ $\displaystyle=$
$\displaystyle\frac{n^{2}}{8}-\frac{3n}{8}-\sum_{i}\frac{i^{2}n_{i}}{2}$

∎

Let $M=\sum_{i}i^{2}n_{i}$. Because of Lemma 4.2,
$M\geq\sum_{i}^{\alpha}i^{2}n_{\alpha}\geq\alpha^{2}\geq 4m^{2}/n^{2}$ where
$\alpha$ is the maximum degree of the halving edge graphs. Thus applying this
to the identity we get

$\displaystyle\mbox{cr}(G)$ $\displaystyle=$
$\displaystyle\frac{n^{2}}{8}-\frac{3n}{8}-\sum_{i}\frac{i^{2}n_{i}}{2}$
$\displaystyle\mbox{cr}(G)$ $\displaystyle\leq$
$\displaystyle\frac{n^{2}-3n}{8}-\alpha^{2}/2$ $\displaystyle\leq$
$\displaystyle\frac{n^{2}-3n}{8}-\frac{2m^{2}}{n^{2}}$

Thus using the fact that cr($G$) $\geq\frac{m^{3}}{64n^{2}}$, we conclude that

$\displaystyle\frac{m^{3}}{64n^{2}}\leq\frac{n^{2}}{8}-\frac{3n}{8}-\frac{2m^{2}}{n^{2}}\implies\frac{m^{3}}{64n^{2}}+\frac{2m^{2}}{n^{2}}+\left(\frac{n^{2}-3n}{8}\right)\leq
0$

Thus we get a cubic inequality $P(m)\leq 0$ with $m$ as the variable and the
cubic polynomial $P(m)$ as
$\frac{m^{3}}{64n^{2}}+\frac{2m^{2}}{n^{2}}+\left(\frac{n^{2}-3n}{8}\right)$.
Now if we find the roots of this polynomial using the Cardano’s formula then
we get a solution for the value of $m$ which is the number of halving edges in
the halving graph. Applying the Cardano’s formula we get
$p=\frac{-b}{3a}=-\frac{128}{3}$,
$q=p^{3}-\frac{d}{2a}=-\frac{8\cdot(64)^{3}}{27}-\frac{64n^{4}-3n^{3}}{16}$
and $r=0$. Thus we get the root of the polynomial $P(m)$ as

$\displaystyle m$ $\displaystyle=$
$\displaystyle\Bigg{\\{}-\frac{8\cdot(64)^{3}}{27}-\frac{64n^{4}-3n^{3}}{16}+\Bigg{[}\left(-\frac{8\cdot(64)^{3}}{27}-\frac{64n^{4}-3n^{3}}{16}\right)^{2}-\frac{128^{6}}{3^{6}}\Bigg{]}^{1/2}\Bigg{\\}}^{1/3}+$
$\displaystyle\Bigg{\\{}-\frac{8\cdot(64)^{3}}{27}-\frac{64n^{4}-3n^{3}}{16}-\Bigg{[}\left(-\frac{8\cdot(64)^{3}}{27}-\frac{64n^{4}-3n^{3}}{16}\right)^{2}+\frac{128^{6}}{3^{6}}\Bigg{]}^{1/2}\Bigg{\\}}^{1/3}-\frac{128}{3}$

Therefore, if we take the asymptotically dominating terms in the expression
for $m$, we get $m=O(n^{4/3})$, reobtaining the upper bound of Dey.

##  4 Discussion on the Bound of $M$

In this section we discuss the implications of the bound of $M$ in the
analysis of the above identity. According to our analysis we have used a very
crude lower bound on the value of $M$. in the following we discuss how one can
achieve better upper bounds for the number of halving edges using better lower
bounds for $M$.

  * (a)

From lemma 3.2 we observe that $i$ can only be an odd number. Thus a better
lower bound for $M$ could be obtained if we get a better lower bound using
$\sum_{i=\mbox{odd}}i^{2}$ although we can’t use the direct formula of
$\sum_{i=\mbox{odd}}i^{2}$ because some of the terms in this series might be
missing. A better bound on the number of missing terms i.e. number of $i$ such
that $i$ is odd, can be used to get a better lower bound on $M$.

  * (b)

A better bound for $M$ can be obtained if we can get a reasonable estimate on
$n_{i}$. In the current bound we have used a very naive lower bound for
$n_{i}$ as 1 whereas an estimate for $n_{i}$ can give us a better bound.

##  5 Conclusion and Future Work

in this paper we have provided a new analysis of bounding the number of
halving edges in 2-Dimensions, this problems although we old not much
understanding of of the exact bound of halving edges is present. We present a
proof that rederived an old upper bound of $O(n^{4/3})$ our proof is based on
a different analysis of the identity proven by Andrejak et al. our analysis is
interesting because it does not neglect the term in the identity and we use a
result of Cardeno’s to obtained the aforementioned upper bound. This technique
also allows us to apply more rigorous bounds on the neglected term, which may
lead to more complex polynomials equations whose roots might be used. As part
of future work we would like to investigate into deriving more stringent
bounds on that term.

## References

  * [1] A. Andrzejak, B. Aronov, S. Har-Peled, R. Seidel, and E. Welzl, Results on $k$-sets and $j$-facets via continuous motion, ACM Sympos. Comput. Geom. (1998), 192–199.
  * [2] I. Bárány, Z. Füredi, and L. Lovász, On the number of halving planes, Combinatorica 2, 10 (1990), 175–183.
  * [3] T.K Dey, Improved bounds for planar $k$-sets and related problems, Discrete and Computational Geometry, 19 (1998), 373–382.
  * [4] H. Edelsbrunner, P. Valtr and E. Welzl, Cutting dense point sets in half, Discrete and Computational Geometry 27 (1997), 243–255 .
  * [5] P. Erdős, L. Lovász, A. Simmons and E. G. Straus, Dissection graphs of planar point sets, Survey of Combinatorial Theory (1973), 139–149.
  * [6] István Kovács∗ Géza Tóth, Dense point sets with many halving lines, arxiv.org/abs/1704.00229v1 (2017).
  * [7] L. Lovász, On the number of halving lines, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 14 (1971), 107–108.
  * [8] J. Matoušek, Lectures on discrete geometry, Springer-Verlag, New York (2002).
  * [9] J. Matoušek, M. Sharir, S. Smorodinsky, and U. Wagner, $k$-sets in four dimensions, Discrete and Computational Geometry 2, 35 (2006), 177–191.
  * [10] G. Nivasch, An improved, simple construction of many halving edges, Contemporary Mathematics, 453 (2008), 299–305.
  * [11] J. Pach, W. Steiger and E. Szemerèdi: An upper bound on the number of planar k-sets, Discrete and Computational Geometry, 7 (1992), 109–123.
  * [12] M. Sharir, An Improved Bound for $k$-sets in Four Dimensions, Combinatorics, Probability and Computing, 20 (2011), 119–129.
  * [13] M. Sharir, S. Smorodinsky and G. Tardos, An Improved Bound for $k$-sets in Three Dimensions, Discrete and Computational Geometry, 26 (2001), 195–204.
  * [14] G. Tóth, Point sets with many $k$-sets, Discrete and Computational Geometry, 26 (2001), 187–194.