# A Deep Retinal Image Quality Assessment Network with Salient Structure
Priors

Ziwen Xu  Beiji Zou  Qing Liu  School of Computer Science and Engineering,
Central South University

###### Abstract

Retinal image quality assessment is an essential prerequisite for diagnosis of
retinal diseases. Its goal is to identify retinal images in which anatomic
structures and lesions attracting ophthalmologists’ attention most are
exhibited clearly and definitely while reject poor quality fundus images.
Motivated by this, we mimic the way that ophthalmologists assess the quality
of retinal images and propose a method termed SalStructuIQA. First, two
salient structures for automated retinal quality assessment. One is the large-
size salient structures including optic disc region and exudates in large-
size. The other is the tiny-size salient structures which mainly include
vessels. Then we incorporate the proposed two salient structure priors with
deep convolutional neural network (CNN) to shift the focus of CNN to salient
structures. Accordingly, we develop two CNN architectures: Dual-branch
SalStructIQA and Single-branch SalStructIQA. Dual-branch SalStructIQA contains
two CNN branches and one is guided by large-size salient structures while the
other is guided by tiny-size salient structures. Single-branch SalStructIQA
contains one CNN branch, which is guided by the concatenation of salient
structures in both large-size and tiny-size. Experimental results on Eye-
Quality dataset show that our proposed Dual-branch SalStructIQA outperforms
the state-of-the-art methods for retinal image quality assessment and Single-
branch SalStructIQA is much light-weight comparing with state-of-the-art deep
retinal image quality assessment methods and still achieves competitive
performances.

###### keywords:

Retinal image quality assessment, Convolutional neural network, Optic disc,
Vessels

key

##  1 Introduction

Retinal images are the most common modality used in the diagnosis of retinal
diseases such as diabetic retinopathy, age-related macular degeneration and
glaucoma etc. High quality retinal images make the salient structures, such as
optic disc, vessels, and lesions etc clearly visible, which help
ophthalmologists make correct clinical decisions efficiently. On the contrary,
low quality images may disturb the judgments. For example, in over-exposed
retinal images, the brightness and the range of colours are limited and the
contrasts between target regions (such as vessels and lesions etc.) and the
background are low, which may confuse the ophthalmologists when accessing the
fundus. Furthermore, for computer-aided retinal image analysis systems, low
quality retinal images would be a catastrophe. According to [1], approximately
$25\%$ of the retinal images are not suitable for diagnosis due to their poor
quality. Thus retinal image quality assessment (Retinal-IQA) is desired. In
clinical, it is performed by a trained optometrist manually, which heavily
depends on the operator’s experience and is time-consuming. To improve the
efficiency of retinal image acquisition, automated Retinal-IQA becomes
necessary.

The goal of image quality assessment (IQA) is to grade images in terms of
quality measures. Generally, IQA methods can be categorized into three groups
based on the presence of reference images: full-reference (FR), reduced-
reference (RR) and no-reference (NR) [2]. Within the context of Retina-IQA,
retinal reference images are absent, thus the task of Retinal-IQA belongs to
NR-IQA. It is always formulated as either a two-class, i.e., ‘Good’ and
‘Reject’ [3] or three-class [4] (i.e. ‘Good’ , ‘Usable/Acceptable’ and
‘Reject’) classification task. As two-class classification is too rigorous and
retinal images with a few artifacts can still be usable for ophthalmologists,
the prevalence of Retina-IQA is dominated by three-class Retina-IQA methods.

Early Retinal-IQA methods grade the image quality via solving the problems of
how to measure the similarity to good quality retinal images or how to
characterise quality distortions. In [5, 6], template matching is adopted for
Retinal-IQA, in which intensity histogram and intensity-gradient histogram are
calculated from a set of good quality retinal images as templates. In [7, 8],
quality distortions are characterised by colour and illumination distortion,
focus fluctuation and contrast sensitivity, with which a classifier is trained
for retinal image quality grading. Although those methods are simple and
intuitive, both templates based on histograms and features manually designed
for quality distortions are insufficient to encode quality measures with high
discriminative ability, which limits the performances of Retinal-IQA.

Driven by the successes achieved by deep convolutional neural networks (CNNs)
in the field of computer vision, Retinal-IQA methods have updated to modern
CNNs-based. In [3], Inception v3 [9] pre-trained on natural scene image
dataset ImageNet [10] is fine-tuned in an end-to-end way for Retinal-IQA,
which takes colour retinal images as input. To make use of both deep features
and hand-crafted features, [11] proposed a two-stage learning method. In
detail, deep features are learned in the first stage via fine-tuning an
AlexNet [12]. With the deep features and hand-crafted features based on a
saliency map, a SVM is trained for quality classification in the second stage.
To further exploit powerful representation for Retinal-IQA, complex frameworks
are proposed. Fu et al. propose a framework, called Multiple Colour-space
Fusion Network (MCF-Net) [4], in which three parallel CNN branches are unified
in one framework to learn complementary informative contexts from three
different colour-spaces, i.e. RGB, HSV and Lab colour space, for Retinal-IQA.
In [13], Shen et al. claim that auxiliary tasks contribute to Retina-IQA and
propose a multi-task framework, named MFIQA. MFIQA [13] consists of a ResNet50
[14] for optic disc and macular detection, a VGG16 [15] for refinement of
optic disc and macular location and two encoders to encode the global retinal
images in Cartesian coordinate system and the local optic disc windows in
polar coordinate system for images quality classification and three relevant
classification tasks, i.e., artifact, clarity and field definition. It is
further improved by introducing domain invariance and interpretability in
[16]. Although learning multiple CNN branches jointly like [4] and multiple
CNNs independently like [13, 16] exploit rich features and facilitate
classification, the parameters to be optimised rapidly multiply. Furthermore,
in [13, 16], learning auxiliary tasks requires extra annotated data, which are
always expensive.

Figure 1: Examples for retinal images with different quality grades. From left
to right, the quality grade is ‘Good’, ‘Usable’ and ‘Reject’, respectively.

Going back to the basics, the goal of capturing retinal images by fundus
camera is to assist ophthalmologists to assess anatomic structures on fundus
in a non-invasion manner. From the view of saliency detection, those anatomic
structures such as optic disc in large size and vessels in tiny size attract
most of attention of ophthalmologists. Thus a good quality retinal image is
required to exhibit those salient structures clearly and definitely. To
intuitively illustrate this, we show three examples from Eye-Quality dataset
[4] in Fig. 1. They are graded as ‘Good’, ‘Usable’ and ‘Reject’ respectively.
Obviously, for good quality retinal image as shown in the left column in Fig.
1, the optic disc region and vessels are clearly visible. For usable quality
retinal image as shown in middle column in Fig. 1, the optic disc region and
most of the vessels are clearly visible except for vessel extending to the
boundary of field of view which are distorted by slight uneven illumination.
For retinal image labelled as ‘Reject’, due to the serious uneven
illumination, the optic disc region and vessels are difficult to be
distinguished.

Based on above observation, we argue that the clarity of salient structures in
both large-size and tiny-size significantly contribute to the image quality
assessment. Usually, more clarity that salient structures in retinal images
are implies higher quality that retinal images have. To this end, we propose
to incorporate the salient structure priors with deep CNN, named SalStructIQA.
Fig. 2 illustrates the flowchart of our proposed SalStructureIQA. It involves
three components: (1) large-size salient structure detector which aims to
detect salient structures in large-size such as optic disc region, large-size
hard exudates and soft exudates etc., (2) tiny-size salient structure detector
which aims to detect vessels, (3) a deep classification network which takes
the retinal image together with the salient structures as input for deep
feature learning and quality classification. Accordingly, we develop two deep
CNN architectures to incorporate salient structure priors with the CNNs. One
contains two parallel CNN branches for deep feature learning, which learns
deep features from retinal image with large-size salient structures and
retinal image with tiny-size salient structures separately, then fuses the
features for quality assessmentenforce. We term it as Dual-branch
SalStructIQA. The other only contains a single CNN branch which first fuses
the retinal image and salient structures via concatenation, then learns deep
features for quality classification. We term it as Single-branch SalStructIQA.
We demonstrate the effectiveness of our proposed priors and two CNN
architectures on public dataset Eye-Quality [4]. And experimental results show
that our method outperforms the state-of-the-arts.

In summary, the contributions of this paper can be summarized as follows:

  * 1.

We propose two salient structure priors in both large-size and tiny-size for
retinal image quality assessment. They enable the CNN to pay more attention to
informative regions with high contrast to background and learn discriminative
features, which further facilitate to retinal image quality assessment.

  * 2.

We propose two ways to incorporate our proposed salient structures with deep
CNN and develop two deep CNN architectures termed Dual-branch SalStructIQA and
Single-branch SalStructIQA for retinal image quality assessment. Experimental
results on Eye-Quality [4] show that the Single-branch one is able to achieve
competitive performances comparing with the state-of-the-arts but the scale of
parameters to be optimised is much less. The Dual-branch one outperforms the
state-of-the-arts as well as the Single-branch.

Figure 2: The flowchart of our proposed SalStructIQA.

The remainder of this paper is organized as follows. Section 2 reviews related
works on Natural-IQA and Retinal-IQA. Section 3 details our proposed quality
assessment method. Section 4 gives the experimental results and analysis and
Section 5 concludes this paper.

##  2 Related work

Following the evolution of natural scene image quality assessment (Natural-
IQA), retinal image quality assessment methods are developed from the two-step
framework with hand-crafted features to the end-to-end framework based on CNN
in general. As retinal image quality assessment is closely relative to natural
scene image quality assessment, in this section, we first review previous
works on Natural-IQA briefly, then elaborate preceding Retinal-IQA methods.

###  2.1 Natural-IQA

Based on the type of extracted features, Natural-IQA methods can be briefly
classified into two groups: hand-crafted feature based methods and CNN-based
methods. The hand-crafted based approaches mainly focus on designing effective
hand-crafted features while the CNN-based methods automatically learn image
features by designing deep network.

Hand-crafted feature based methods. These methods usually assume that pristine
natural images possess potential statistic regularities and these regulations
will be changed with the emergence of distortion [17]. For example, [17]
proposes a two-stage framework called DIIVINE for quality assessment, which
consists of distortion classification and distortion-specific quality
estimation. BLINDS-II [18] utilizes DCT coefficients to model statistics of
images, and then combines the estimated parameters of the model with Bayesian
approach for quality score prediction. BRISQUE [19] adopts local normalization
brightness coefficients for image quality. To better improve the performance,
a new NBIQA [20] simultaneously considers the features from both the spatial
and transform domains. Although NBIQA [20] performs better, it is also
relatively time-consuming due to the complexity of extracted features. In
addition, [21] designs a joint NSS model based on joint log-contrast
statistics for Natural-IQA, which utilizes two natural image properties, i.e.,
the non-Gaussian statistics and image correlations across spatial and
direction. As a whole, the hand-crafted feature based methods heavily rely on
the artificial features design, which is too complex to achieve efficient and
appropriate features.

CNN-based methods. Due to the remarkable achievements of CNN in image
classification tasks, researchers have introduced the deep learning method
into Natural-IQA. In [22], the CNN only containing one convolutional layer is
proposed for Natural-IQA. To better characterize features, [23] proposes a
multi-task end-to-end optimized network for quality prediction called MEON.
Similar to DIIVINE [17], MEON focuses on two sub-task, distortion
identification and quality prediction. In [24, 25], rank learning is adopted
for Natural-IQA. In rankIQA [25], the traditional image processing method is
firstly utilized to generate ranked images which are then used to train a
siamese network for ranking. Subsequently, the branch of trained network is
fine-tuned on IQA dataset for predicting the absolute quality score. In dipIQ
[24], a large number of quality-discriminable image pairs are used to train a
RankNet [26], generating an inferred image quality. However, the above CNN-
based methods ignore the salient structures attracting human attention, which
have been demonstrated to be important for image quality assessment [27, 28,
29]. [27] proposes a two-stream network for Natural-IQA, which includes an
image stream focusing on gray information and a structure stream focusing on
image gradient details. Considering that image saliency can present image
structure to some extent, [28] proposes a saliency-guided Natural-IQA network
called SGDNet, which is trained with saliency ground truth and quality label.
Similar to approach [30], SGDNet regards the saliency map as local weighted
function. Specifically, the predicted saliency map is fused with original
features in the form of spatial attention mask, perceptually consistent to
quality prediction. [29] proposes a deep feature importance awareness method
to evaluate image quality named DFIA. They integrate the Squeeze-and-
Excitation (SE) block [31] into deep IQA network, which emphasizes the deep
features of image distortion and salient objects related to IQA.

###  2.2 Retinal-IQA

Retinal-IQA is an important task for the diagnosis of retinal diseases.
However, Natural-IQA methods may not perform well in Retinal-IQA. More
specifically, the hand-crafted based methods for Natural-IQA mainly rely on a
hypothesis that pristine natural images present certain statistic regularities
which will be disturbed by distortions. However, the statistics of natural
images are not consistent with those of retinal images. In addition, several
CNN-based methods for Natural-IQA usually assign the global quality score for
all image patches cropped from the same image, resulting the label noise
problem. This strategy is also not suitable for Retinal-IQA. Therefore, it is
essential to design effective methods for Retinal-IQA. Similar to Natural-IQA,
the current researches in Retinal-IQA can be roughly grouped to two
categories: hand-crafted based methods and CNN-based methods.

Hand-crafted based methods. Early methods such as [5, 6] for Retinal-IQA
pursue a template for good quality images and grade the image quality via
template matching while [32, 7] extract statistical characteristics such as
focus, lumination and contrast features etc. and train a classifier for image
quality assessment. Based on the assumption that the more vessels the better
retinal image quality, [33] first calculates the area of vessels to define
image clarity, in which matched filtering and region segmentation algorithm
are applied to segment the vessel structures. In [34], Kohler et al. assume
that patches located on vessel edges are more sensitive to image blur and
noise, and propose to use the variance of vessels in patches to discriminate
good retinal images from poor quality retinal images. In [35], retinal image
quality is graded by comparing the vessel clarity and contrast between the
macular area and background. From the perspective of human visual system (HVS)
characteristics, [8] proposes to apply HVS features, including multi-channel
sensation, just noticeable blur, and the contrast sensitivity measure, to
estimate quality. However, the limitation of these hand-crafted features may
still lead to performance bottlenecks.

CNN-based methods. Motivated by the success of CNN in computer vision tasks,
CNN has been introduced to Retinal-IQA. Several methods for Retinal-IQA are
either training a shallow classification CNN network from scratch [36] or
fine-tuning existing classification networks, such as AlexNet [12], ResNet
[14] and Xception [37], from pre-trained models [3, 38, 39]. To make use of
the complementary of different colour spaces, Fu et al. [4] propose a multiple
colour-space fusion network, in which multiple parallel CNN branches are used
to learn features from different colour-spaces. Although [4] is able to
capture richer information such that the classification performances are
improved significantly, the scale of parameters rapidly multiply. Instead, Yu
et al. [11] propose to combine salient maps produced by [40] and deep features
extracted by Alexnet [12] and train an SVM for retinal image quality
assessment. In [13], Shen et al. claim that auxiliary tasks contribute to
Retinal-IQA and propose a multi-task framework named MFIQA, in which a
ResNet50 [14] is trained for the detection of optic disc and macular and a
VGG16 [15] is trained for refinement of optic disc and macular location and
two encoders are used to encode the entire retinal images in Cartesian
coordinate system and the local optic disc windows in polar coordinates
systems for images quality classification. Additionally, three relevant
classification tasks, i.e., artifact, clarity and field definition are
proposed to assist the learning of quality assessment. To further improve the
performances, domain invariance and interpretability are introduced in [16].
Learning auxiliary tasks do facilitate Retinal-IQA, but requires extra
annotated data, which are expensive.

##  3 Methodology

The purpose of photographing for retina fundus is to provide an invasive way
for ophthalmologist to assess the fundus. Commonly ophthalmologists pay more
attention to informative structures. Among them, two kinds of informative
structures attract most attentions from ophthalmologists: structures in large-
size such as OD and large-size hard exudates and soft exudates etc. and
structures in tiny-size, i.e., vessels. Whether these salient structures are
clearly and definitely exhibited plays an important role in determining
whether retinal images have good quality for ophthalmologists. To mimic the
quality assessment procedure of ophthalmologists, we propose a deep retinal
image quality assessment method termed SalStructIQA, which first detects two
kinds of salient structures, then incorporates them with deep CNN for quality
grading. Fig 2 illustrates the flowchart of our proposed SalStructIQA. It
consists of three components: large-size salient structure detector, tiny-size
salient structure detector and deep CNN classifier. In the following, we will
detail each of them.

###  3.1 Large-size salient structure detector

Within the context of retinal images, large-size structures mainly consists of
OD and large-size exudates etc. They are in bright yellow. In good quality
retinal images, those structures are easy to be recognised. On the contrast,
in poor quality retinal images, those structures are difficult to be
recognised. The major reason is that the contrasts of those large-size salient
structures in different quality images are different. Particularly, for good
quality retinal images, large-size structures naturally have high contrast to
their surrounding regions as images are usually captured with even
illumination. For poor retinal images, they are usually captured with uneven
illumination. Defect regions with strong illumination exhibit high contrast
while the contrasts of those bright yellow structures with weak illumination
are suppressed. To this end, we propose to detect large-size salient
structures via contrast for retinal image quality assessment. It is estimated
by Difference of Gaussian (DoG) operator, which can be expressed as:

$\begin{array}[]{ll}DoG(x,y,\sigma,\rho)&=\frac{1}{2\pi}\left[\frac{1}{\sigma^{2}}\mathrm{e}^{-\frac{x^{2}+y^{2}}{\sigma^{2}}}-\frac{1}{(\sigma/\rho)^{2}}\mathrm{e}^{-\frac{x^{2}+y^{2}}{(\sigma/\rho)^{2}}}\right]\\\
&=G(x,y,\sigma)-G(x,y,\sigma/\rho)\end{array}\;,$ (1)

where $\sigma$ is the standard deviation of Gaussian and $\rho$ is a constant
which is larger than 1. From the view of frequency domain, the DoG operator is
a band-pass filter and $\rho$ is the bandpass width. Considering that the
salient structures are diverse in scale, we propose to combine multiple DoGs
with $K$ different bandpass widths for contrast estimation:

$\begin{array}[]{ll}MultiDoG(x,y)&=\sum_{k=1}^{K}\left\\{DoG(x,y,\sigma_{k},\rho^{k-1})-DoG(x,y,\sigma_{k},\rho^{k})\right\\}\\\
&=G(x,y,\sigma)-G(x,y,\sigma/\rho^{K})\end{array}\;,$ (2)

Figure 3: Examples for the probability map of large-size salient structures
and the masks of detected large-size salient structures.

Here we directly set $\sigma$ be a large constant to maintain most of the
frequency and filter out the high frequency noises. Thus the first item in Eq.
(2) is approximated to a low-pass filter with a large cut-off frequency. For
computational simplicity, we follow [40] and use a $5\times 5$ Gaussian filter
to approximate it in spatial domain. For the second item in Eq. (2), we set
$K$ be infinity, thus it is approximated to a low-pass filter at zero
frequency. More specifically, with the colour retinal image
$\mathbf{I}\in\mathcal{R}^{H\times W\times 3}$ in RGB colour space, we first
transform it into Lab colour space as Lab is designed to approximate human
vision. We denote the Lab image as $\mathbf{I}^{Lab}$. Then in spatial domain,
we estimate the contrast via:

$\mathbf{R}_{contrast}(x,y)=||\mathbf{I_{\mu}}^{Lab}-\mathbf{I}_{lp}^{Lab}(x,y)||_{2}\;,$
(3)

where $\mathbf{I_{\mu}}$ is the global mean vector of $\mathbf{I}^{Lab}$,
$\mathbf{I}_{lp}^{Lab}(x,y)$ is the corresponding filter response at location
$(x,y)$ with the $5\times 5$ Gaussian filter, and $||\cdot||_{2}$ is the
Euclidean distance. Finally, we rescale the contrast map into $[0,1]$ via max-
normalisation, and obtain the probability map of large-size salient structures
denoted by $\mathbf{P}_{LS}$:

$\mathbf{P}_{LS}(x,y)=\frac{\mathbf{R}_{contrast}(x,y)}{\max_{(x,y)\in\mathcal{R}^{H\times
W}}\\{\mathbf{R}_{contrast}(x,y)\\}}\;.$ (4)

By thresholding $\mathbf{P}_{LS}$, we obtain the mask of detected large-size
salient structures, and we denote it as $\mathbf{M}_{LS}$.

Fig. 3 illustrates three retinal images from Eye-Quality dataset [4], their
corresponding probability map $\mathbf{P}_{LS}$ of large-size salient
structures and binarized results. From top to bottom, retinal images are
graded as ‘Good’, ‘Usable’ and ‘Reject’ by experts respectively. Obviously,
their detection results of large-size salient structures are significantly
different: (1) in retinal image graded as ‘Good’, large-size salient
structures are well highlighted in $\mathbf{P}_{LS}$; (2) in retinal image
graded as ‘Reject’, defects are well highlighted in $\mathbf{P}_{LS}$ while
the salient structures are suppressed; (3) in retinal image graded as
‘Usable’, although slight detect is highlighted in $\mathbf{P}_{LS}$, its
adverse effect is weak and the salient structure is still well highlighted.
These imply that the detection results of large-size salient structures do
contribute to image quality grading.

###  3.2 Tiny-size salient structure detector

Vessels are important structures in retinal image. Their abnormal morphology
is a significant manifestation for eye diseases such as diabetic retinopathy
and age related macular degeneration. Although they are in tiny size, they are
salient for ophthalmologists. Thus we propose to detect those tiny-size
salient structures for retina image quality assessment.

Figure 4: Examples for the standardized line response maps and masks of
detected tiny-size salient structures.

Here we directly adopt multi-scale line detector [41] as our tiny-size salient
structure detector due to its simplicity. Multi-scale line detector [41]
treats the vessels as line-shaped and assumes that there are high intensity
contrasts between pixels along vessel line and rest pixels among multi-scale
windows. As the vessels is darker than the background in the gray channel
$\mathbf{I}^{Gray}$ of a retinal image, the multi-scale line detector is
performed on its inverted gray channel to highlight the vessels. For a pixel
at location $(x,y)$, the multi-scale line detector measures the line response
by:

$\mathbf{R}_{line}(x,y)=\frac{1}{|S|}\left(\sum_{s\in{S}}\max_{\theta\in\Theta}\left(Avg(L_{x,y}^{s,\theta})-Avg(\Omega^{s}_{x,y})\right)\right)\;,$
(5)

where $S$ is the set of window size, and $|S|$ is the cardinality of set $S$,
$\Theta$ is the set of line direction, and $\Omega^{s}_{x,y}$ is the local
window of size $s\times s$ centred on $(x,y)$, and $L_{x,y}^{s,\theta}$ is the
pixel set of line along direction $\theta$ passing location $(x,y)$ in
$\Omega^{s}_{x,y}$, and $Avg(\cdot)$ is an average function. We follow the
setting of multi-scale line director [41] and set $S=\\{1,3,5,7\\}$ and
$\Theta=\\{0^{\circ},15^{\circ},30^{\circ},\cdots,165^{\circ}\\}$. Since the
contrast of vessels to other structures such as lesions is apparent in the
original inverted gray image, multi-scale line detector [41] also utilizes the
information of the inverted gray channel to enhance the line response:

$\mathbf{R}_{line}^{\prime}(x,y)=\frac{1}{|S|+1}\left(\sum_{s\in{S}}\max_{\theta\in\Theta}\left(Avg(L_{x,y}^{s,\theta})-Avg(\Omega^{s}_{x,y})\right)+\left(1-\mathbf{I}^{Gray}(x,y)\right)\right)\;.$
(6)

Finally, we follow [41] and standardize the enhanced line response map
$\mathbf{R}_{line}^{\prime}$ via $Z-$score standardization. We denote the
standardized line response map as $\mathbf{R}_{line}^{{}^{\prime\prime}}$. By
thresholding the $\mathbf{R}_{line}^{{}^{\prime\prime}}$ with threshold value
$0.56$, we obtain the mask of detected tiny-size salient structures and denote
it as $\mathbf{M}_{TS}$.

Figure 5: The cumulative distributions of tiny-size salient structures of each
class.

Fig. 4 shows three examples of retinal images, the results of tiny-size
salient structure detection. Obviously, the tiny-size salient structures in
good quality retinal image are well detected by our proposed tiny-size salient
structure detector. Most of the tiny-size salient structures in retinal image
graded as ‘Usable’ quality are detected by our proposed detector. On the
contrary, few tiny-size salient structures in retinal image graded as ‘Reject’
quality are detected by our proposed detector. These indicate that the density
of detected tiny-size salient structures is an important cue for the quality
classification of retinal images. To better illustrate this, we provide a
statistic analysis on the training set of Eye-Quality [4]. For each retinal
image, we account the number of pixels which are detected as tiny-size salient
structures and denote it as $|\mathbf{M}_{TS}|$. Then for each quality level,
we separately plot the cumulative distribution of $\mathbf{M}_{TS}$. As shown
in Fig. 5, there are 70% images in class of ‘Reject’ whose $|\mathbf{M}_{TS}|$
is less than 1513 while the percentage in class of ‘Usable’ is 31.82%. This
implies that it is easy to discriminate the class of ‘Reject’ and ‘Usable’
according to $|\mathbf{M}_{TS}|$. There are 70% images in class ‘Usable’ whose
$|\mathbf{M}_{TS}|$ is less than 2160 while the percentage in class of ‘Good’
is 23.44%. This implies that it is easy to discriminate the class of ‘Usable’
and ‘Good’ according to $|\mathbf{M}_{TS}|$.

Figure 6: The proposed deep CNN architectures incorporating with our proposed
large-size salient structures and tiny-size salient structures.

###  3.3 Network Architectures

To incorporate two salient structure priors with convolutional neural network
for retinal image quality grading, we implement a deep network, named
SalStructIQA network. For these two priors, they can be separately
concatenated with the RGB retinal image forming two tensors with four channels
as shown in Fig. 6(a) or jointly concatenated with the RGB retinal image
forming one tensor with five channels as shown in Fig. 6(b). This derives two
versions of SalStructIQA: Dual-branch SalStructIQA and Single-branch
SalStructIQA. In what follows, the RGB retinal image is denoted as
$\mathbf{I}\in\mathcal{R}^{H\times W\times 3}$, and the masks of large-size
salient structures and tiny-size salient structures are denoted as
$\mathbf{M}_{LS}\in\mathcal{R}^{H\times W}$ and
$\mathbf{M}_{TS}\in\mathcal{R}^{H\times W}$.

Dual-Branch SalStructIQA Network. In this architecture, there are two parallel
branches of CNN equipped with a global average pooling layer(GAP) for feature
learning, as shown in Fig. 6(a) . One branch takes the combination of
$\mathbf{I}$ and $\mathbf{M}_{LS}$ as input and produces a feature vector
denoted as $\mathbf{f}_{LS}$. The other branch takes the combination of
$\mathbf{I}$ and $\mathbf{M}_{TS}$ as input and produces a feature vector
denoted as $\mathbf{f}_{TS}$. Then these two feature vectors are concatenated
and fed into a full connection (FC) layer to predict the quality grade:

$\hat{y}=\mathrm{softmax}\left(\mathbf{w}^{T}[\mathbf{f}_{LS},\mathbf{f}_{TS}]+\mathbf{b}\right)\;,$
(7)

where $\mathbf{w}$ and $\mathbf{b}$ are weights and bias to be learned in FC
layer. Parameters in both parallel CNN backbones and FC layers are learned in
an end-to-end way and cross-entropy loss is used in training phase.

One thing worth noting is that arbitrary existing CNN backbones such as
VGGNet, ResNet and DenseNet etc. can be used for feature learning in each
branch in Fig. 6(a) after revising the first dimension of convolution kernel
in the first convolutional layer to four. In our experiments, performances of
two famous backbones, i.e., ResNet-50 and DenseNet-121 are reported.

Single-Branch SalStructIQA Network. The architecture is shown in Fig. 6(b). It
consists of one CNN branch together with a GAP for feature learning and a FC
layer for classification. This architecture takes
$[\mathbf{I},\mathbf{f}_{LS},\mathbf{f}_{TS}]$ as an input and predicts the
quality grade. Same to dual-branch one, the network can be trained in an end-
to-end way and cross-entropy loss is used in training phase.

##  4 Experimental results

The proposed SalStructIQA method is first evaluated and compared with the
state-of-the-art image quality assessment methods on the public dataset Eye-
Quality [4]. Eye-Quality [4] collects 28,792 retinal images from Kaggle and
each retinal image is re-annotated with three grades ‘Good’, ‘Usable’ and
‘Reject’. The image size ranges from $211\times 320$ to $3456\times 5184$.
Those images are divided into into two subsets: 12,543 for training and 16,249
for testing. Then extensive ablation study on Eye-Quality [4] is conducted.
Following [4], average accuracy ($Acc$), precision ($P$), recall ($R$) and
F-score ($F_{score}=2\times P\times R/(P+R)$) are used as evaluation metrics.

###  4.1 Data augmentation and experimental setup

Data preprocessing and augmentation. With the retinal images, we follow [4]
and first crop the field of view (FoV) via Hough Circle Transform, then we pad
short side with zeros such that the width and height of the cropped FoV
regions are equal length. Finally, we rescale padded regions to $224\times
224$. The masks of large-sized salient structures $\mathbf{M}_{LS}$ and tiny-
sized salient structures $\mathbf{M}_{TS}$ are detected from rescaled images.
To increase the diversity of training data, we use vertical flipping,
horizontal flipping and random rotation to augment the training data.

Experimental setup. Parameters in backbone network are initialized with the
pre-trained models on ImageNet [10]. Parameters associated with full
connection layers are initialized with Gaussian distribution with zero mean
and standard deviation 0.001. We adopt stochastic gradient descent to optimize
the network with initial learning rate of $0.01$. We train the model 20 epochs
and reduce the learning rate to 0.001 after 10 epochs.

Table 1:  Comparisons of the proposed methods and state-of-the-arts on Eye-Quality [4] Methods |  | $Acc$ | $P$ | $R$ | $F_{score}$ | $Param$
---|---|---|---|---|---|---
Natural-IQA |  BRISQUE[19] | 0.7692 | 0.7608 | 0.7095 | 0.7112 | -
|  NBIQA[20] | 0.7917 | 0.7641 | 0.7509 | 0.7441 | -
|  TS-CNN [27] | 0.7926 | 0.7976 | 0.7446 | 0.7481 | 1.44M
Retinal-IQA |  HVS-based* [8] | - | 0.7404 | 0.6945 | 0.6991 | -
|  MR-CNN* [39] | 0.8843 | 0.8697 | 0.8700 | 0.8694 | 101.80M
|  DenseNet121-MCF* [4] | - | 0.8645 | 0.8497 | 0.8551 | 28.26M
|  DenseNet121-MCF [4] | 0.8722 | 0.8563 | 0.8482 | 0.8506 | 28.26M
|  DenseNet121-RGB* [4] | - | 0.8194 | 0.8114 | 0.8152 | 6.96M
|  DenseNet121-RGB [4] | 0.8568 | 0.8481 | 0.8239 | 0.8315 | 6.96M
| Single-branch SalStructIQA | 0.8847 | 0.8715 | 0.8645 | 0.8662 | 6.96M
| Dual-branch SalStructIQA | 0.8897 | 0.8748 | 0.8721 | 0.8723 | 13.92M

###  4.2 Comparisons with State-of-the-arts

We compare our SalStructIQA with six image quality assessment methods: BRISQUE
[19], NBIQA [20] and TS-CNN [27], HVS-based method [8], DenseNet121-MCF [4]
and Multivariate-Regression CNN (MR-CNN) [39]. The first three methods are
designed for Natural-IQA, among which BRISQUE [19] and NBIQA [20] are hand-
crafted feature based and TS-CNN [27] is deep feature based. Their results are
obtained by adapting the codes from authors to Retinal-IQA task with Eye-
Quality dataset [4]. In detail, those three Natural-IQA methods aim to regress
the quality scores of natural images while Retinal-IQA in this paper aims to
classify the quality of retinal images into three classes. Thus to make those
Natural-IQA methods adapt to Retinal-IQA, regression is replaced with
classification. Particularly, in the implementations of BRISQUE [19] and NBIQA
[20], we directly predict retinal image quality label instead of regressing
the quality score. They are implemented by Matlab 2014A on the platform of a
PC with an i5 CPU and 16 GB RAM. In the implementation of TS-CNN [27], the
regression layer with one-dimensional output is replaced with a classification
layer with three-dimensional outputs and the loss is replaced by multi-class
cross-entropy loss. The last three methods are specifically designed for
Retinal-IQA, among which HVS-based method [8] is hand-crafted feature based
and DenseNet121-MCF [4] and MR-CNN [39] are deep feature based. The results of
HVS-based method [8] and DenseNet121-MCF [4] are from [4]. For fair
comparison, the $Acc$ results of HVS-based method [8] and DenseNet121-MCF [4]
are not given here because they do not report their corrected result. The
results of MR-CNN [39] are directly taken from the original paper. We also
reproduce the results of DenseNet121-MCF [4] and DenseNet121-RGB [4].

Table. 1 reports the performances comparing with state-of-the-arts. Results
from the original papers or reproduced by others are marked with * while those
without any mark are reproduced by ours. Our reproduction of previous methods
and implementation of our methods are conducted with three independent trails
and the average performances are reported. From Table. 1, we have following
observations.

  * 1.

Comparing with hand-crafted feature based methods, i.e. BRISQUE [19], NBIQA
[20] and HVS-based method [8], deep feature based methods achieve better
performances on Retinal-IQA. The possible reason is that deep features are
more powerful than hand-crafted features.

  * 2.

For deep feature based methods, Retinal-IQA methods significantly outperforms
Natural-IQA methods, i.e. TS-CNN [27].

  * 3.

Comparing with deep features based Retina-IQA method MR-CNN* [39], our Single-
branch SalStructIQA achieves 88.47% in $Acc$ which slightly outperforms MR-
CNN* [39] by 0.04%. In terms of $F_{score}$, our Single-branch SalStructIQA
achieves 86.62%, which is slightly inferior to MR-CNN* [39] by 0.31%. One
thing worth to mention is that the parameters of our Single-branch
SalStructIQA are approximately $1/15$ of MR-CNN* [39].

  * 4.

Comparing with DenseNet121-MCF* [4], our Single-branch SalStructIQA
outperforms it by 1.11% in $F_{score}$. Additionally, our Single-branch
SalStructIQA is much lighter than DenseNet121-MCF* [4], whose parameter scale
is approximately $1/4$ of DenseNet121-MCF* [4]. Comparing with
DenseNet121-RGB* [4], ours Single-branch SalStructIQA significantly
outperforms it with the same parameter scale.

  * 5.

Comparing with the Single-branch one, our Dual-branch SalStructSal further
improves the performances consistently while the parameter scale is double.
Comparing with both Natural-IQA methods and Retinal-IQA methods listed in
Table. 1, our Dual-branch SalStructIQA achieves best performances.

Figure 7: Confusion matrices of BRISQUE [19], NBIQA [20], TS-CNN[27],
DenseNet121-MCF [4], our Single-branch SalStructIQA and Dual-branch
SalStructIQA.

We also report the confusion matrices of methods BRISQUE [19], NBIQA [20], TS-
CNN[27], DenseNet121-MCF [4], our Single-branch SalStructIQA and Dual-branch
SalStructIQA in Fig. 7. For brevity, we report the confusion matrices of those
methods according to the trail achieving best $F_{score}$. From confusion
matrices we have following observations:

  * 1.

Natural-IQA methods BRISQUE [19], NBIQA [20] and TS-CNN[27] work well in
classifying retinal images with ‘Good’ quality. But they tend to wrongly
classify retinal images graded as ‘Usable’ into ‘Good’ and ‘Reject’ and
classify retinal images graded as ‘Reject’ into ‘Good’ and ‘Usable’.

  * 2.

Comparing with Natural-IQA methods, DenseNet121-MCF [4] improves the
classification accuracy of retinal images graded as ‘Usable’.

  * 3.

Comparing with Natural-IQA methods, both our Single-branch method and Dual-
branch method achieve higher classification accuracies of retinal images
graded as ‘Usable’ and ‘Reject’ significantly. Comparing with DenseNet121-MCF
[4], ours method performs better in classification on retinal images graded as
‘Reject’, which is more important than correctly identifying the retinal
images graded as ‘Usable’ and ‘Good’ in clinical.

Table 2: The influences of backbone networks and our proposed salient structure priors.  Model | Backbone | $Acc$ | $P$ | $R$ | $F_{score}$
---|---|---|---|---|---
Baseline | ResNet50 | 0.8809 | 0.8670 | 0.8616 | 0.8609
+LS | ResNet50 | 0.8834 | 0.8626 | 0.8703 | 0.8642
+TS | ResNet50 | 0.8833 | 0.8663 | 0.8661 | 0.8646
+LS+TS (Single-branch) | ResNet50 | 0.8840 | 0.8656 | 0.8680 | 0.8657
+LS+TS (Dual-branch) | ResNet50 | 0.8857 | 0.8694 | 0.8708 | 0.8695
Baseline | DenseNet121 | 0.8834 | 0.8711 | 0.8624 | 0.8641
\+ LS | DenseNet121 | 0.8851 | 0.8706 | 0.8661 | 0.8672
+TS | DenseNet121 | 0.9229 | 0.8843 | 0.8631 | 0.8653
+LS+TS (Single-branch) | DenseNet121 | 0.8847 | 0.8715 | 0.8645 | 0.8662
+LS+TS (Dual-branch) | DenseNet121 | 0.8897 | 0.8748 | 0.8721 | 0.8723

###  4.3 Ablation Study

We further look into the influences of different backbone networks and our two
proposed salient structures, i.e., large-size salient structures and tiny-size
salient structures. To this end, ablation study is first conducted. Two
prevalent backbone networks ResNet50 [14] and DenseNet121 [42] are chosen. For
each backbone network, we separately train four models: the baseline model
which is trained with $\mathbf{I}\in\mathcal{R}^{H\times W\times 3}$, the
model denoted as ‘+LS’ which is trained with
$[\mathbf{I},\mathbf{M}_{LS}]\in\mathcal{R}^{H\times W\times 4}$, the model
denoted as ‘+TS’ which is trained with
$[\mathbf{I},\mathbf{M}_{TS}]\in\mathcal{R}^{H\times W\times 4}$ and the model
denoted as ‘+LS+TS (Single-branch)’ which is trained with
$[\mathbf{I},\mathbf{M}_{LS},\mathbf{M}_{TS}]\in\mathcal{R}^{H\times W\times
5}$. As mentioned before, $\mathbf{I}$, $\mathbf{M}_{LS}$ and
$\mathbf{M}_{LS}$ are the RGB retinal image, the mask of large-size salient
structures and the mask of tiny-size salient structures respectively. The
performances are reported in Table 2. The performances of Dual-branch
SalStructureIQA are also listed. Obviously, DenseNet121 [42] outperforms
ResNet50 [14] in Retinal-IQA. Moreover, from Table. 2 we can see that (1)
combining RGB retinal image with either large-size salient structures or tiny-
size salient structures is able to improve the performances of Retinal-IQA,
(2) our Dual-branch SalStructIQA achieves superior performances than the
Single-branch one which indicates that separately learning features from
$[\mathbf{I},\mathbf{M}_{LS}]$ and $[\mathbf{I},\mathbf{M}_{TS}]$ works better
than learning features from $[\mathbf{I},\mathbf{M}_{LS},\mathbf{M}_{TS}]$.

Figure 8: Examples of gradient-weighted class activation maps of different
models generated according to [43]. These three retinal images are mis-
classified by DenseNet121-RGB [4] but correctly classified by our Single-
branch SalStructIQA and Dual-branch SalStructIQA. Obviously, with salient
structures, the models tend to learn discriminate information from salient
regions for image quality assessment.

Additionally, we show three examples of gradient-weighted class activation
maps of three models, i.e., DenseNet121-RGB [4], our Single-branch
SalStructIQA and Dual-branch SalStructIQA in Fig. 8. Those gradient-weighted
activation maps are generated according to [43]. As our Dual-branch
SalStructIQA contains two branches, i.e., the large-size salient structure
branch and the tiny-size salient structure branch, thus for each input there
are two class activation maps as listed in the last two columns in Fig. 8.
With regard to these three examples graded as ‘Good’, ‘Usable’ and ‘Reject’
from top to bottom, DenseNet121-RGB [4] wrongly classifies them into ‘Usable’,
‘Good’ and ‘Usable’ while our two SalStructIQA models are able to correctly
classify them. Gradient-weighted class activation maps of DenseNet121-RGB [4]
(the second column in Fig. 8) indicate that DenseNet121-RGB may fail to
capture the most informative information for classification. On the contrary,
our two models are able to capture the most informative information. As shown
in the third column in Fig. 8, for the classification of images graded as
‘Good’ and ‘Usable’, our Single-branch SalStructIQA are able to capture
informative information from optic disc and vessels. For the classification of
image graded as ‘Reject’, our Single-branch SalStructIQA are able to capture
distinct information from the distortion regions, i.e. partial optic disc
region and region with uneven illumination. As shown in the fourth and fifth
columns in Fig. 8, the large-size salient structure branch in our Dual-branch
SalStructIQA is able to capture informative information from optic disc region
for the classification of ‘Good’ and ‘Usable’ images and from the distorted
bright region for the classification of ‘Reject’ image. The tiny-size salient
structure branch is guided to focus on the vessels for Retinal-IQA. Comparing
with DenseNet121-RGB [4] without considering the salient structures in retinal
images, the ways that our proposed two models with salient structures for
Retinal-IQA are much more consistent to that ophthalmologists perform quality
assessment.

##  5 Conclusion

In this paper, we propose two salient structures priors, i.e., large-size
salient structures and tiny-size salient structures for retinal image quality
assessment. They are incorporated with deep CNN such that the CNN is guided to
learn informative information from those salient structures for quality
grading. Correspondingly, two CNN architectures termed Dual-branch
SalStructIQA and Single-branch SalStructIQA are developed. The former uses the
two priors to separately guide the learning of two CNN branches and is able to
achieve superior performances than the state-of-the-arts on Eye-Quality [4].
The latter concatenates two priors into one branch to guide the single branch
CNN which is much light-weight compared with state-of-the-arts but still able
to achieve competitive performances on Eye-Quality [4]. We visualize the class
activation maps of both architectures which shows that our proposed methods
grade the quality of retinal images in a similar way to ophthalmologists.

##  6 Acknowledgment

This work is supported by the National Key Research and Development Program of
China (No. 2018AAA0102102); and the National Natural Science Foundation of
China (No. 62006249).

## References

  * MacGillivray et al. [2015] T. J. MacGillivray, J. R. Cameron, Q. Zhang, A. El-Medany, C. Mulholland, Z. Sheng, B. Dhillon, F. N. Doubal, P. J. Foster, E. Trucco, et al.,  Suitability of uk biobank retinal images for automatic analysis of morphometric properties of the vasculature,  PLoS One 10 (2015) e0127914.
  * Wang and Bovik [2006] Z. Wang, A. C. Bovik,  Modern image quality assessment,  Synthesis Lectures on Image, Video, and Multimedia Processing 2 (2006) 1–156.
  * Zago et al. [2018] G. T. Zago, R. V. Andreão, B. Dorizzi, E. O. T. Salles,  Retinal image quality assessment using deep learning,  Computers in biology and medicine 103 (2018) 64–70.
  * Fu et al. [2019] H. Fu, B. Wang, J. Shen, S. Cui, Y. Xu, J. Liu, L. Shao,  Evaluation of retinal image quality assessment networks in different color-spaces,  in: International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer, 2019, pp. 48–56.
  * Lee and Wang [1999] S. C. Lee, Y. Wang,  Automatic retinal image quality assessment and enhancement,  in: Medical Imaging 1999: Image Processing, volume 3661, International Society for Optics and Photonics, 1999, pp. 1581–1590.
  * Lalonde et al. [2001] M. Lalonde, L. Gagnon, M.-C. Boucher, et al.,  Automatic visual quality assessment in optical fundus images,  in: Proceedings of vision interface, volume 32, 2001, pp. 259–264.
  * Dias et al. [2014] J. M. P. Dias, C. M. Oliveira, L. A. da Silva Cruz,  Retinal image quality assessment using generic image quality indicators,  Information Fusion 19 (2014) 73–90.
  * Wang et al. [2015] S. Wang, K. Jin, H. Lu, C. Cheng, J. Ye, D. Qian,  Human visual system-based fundus image quality assessment of portable fundus camera photographs,  IEEE transactions on medical imaging 35 (2015) 1046–1055.
  * Szegedy et al. [2016] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, Z. Wojna,  Rethinking the inception architecture for computer vision,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 2818–2826.
  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, L. Fei-Fei,  Imagenet: A large-scale hierarchical image database,  in: 2009 IEEE conference on computer vision and pattern recognition, Ieee, 2009, pp. 248–255.
  * Yu et al. [2017] F. Yu, J. Sun, A. Li, J. Cheng, C. Wan, J. Liu,  Image quality classification for dr screening using deep learning,  in: 2017 39th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), IEEE, 2017, pp. 664–667.
  * Krizhevsky et al. [2012] A. Krizhevsky, I. Sutskever, G. E. Hinton,  Imagenet classification with deep convolutional neural networks,  in: Advances in neural information processing systems, 2012, pp. 1097–1105.
  * Shen et al. [2018] Y. Shen, R. Fang, B. Sheng, L. Dai, H. Li, J. Qin, Q. Wu, W. Jia,  Multi-task fundus image quality assessment via transfer learning and landmarks detection,  in: International Workshop on Machine Learning in Medical Imaging, Springer, 2018, pp. 28–36.
  * He et al. [2016] K. He, X. Zhang, S. Ren, J. Sun,  Deep residual learning for image recognition,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * Simonyan and Zisserman [2014] K. Simonyan, A. Zisserman,  Very deep convolutional networks for large-scale image recognition,  arXiv preprint arXiv:1409.1556 (2014).
  * Shen et al. [2020] Y. Shen, B. Sheng, R. Fang, H. Li, L. Dai, S. Stolte, J. Qin, W. Jia, D. Shen,  Domain-invariant interpretable fundus image quality assessment,  Medical Image Analysis 61 (2020) 101654.
  * Moorthy and Bovik [2011] A. K. Moorthy, A. C. Bovik,  Blind image quality assessment: From natural scene statistics to perceptual quality,  IEEE transactions on Image Processing 20 (2011) 3350–3364.
  * Saad et al. [2012] M. A. Saad, A. C. Bovik, C. Charrier,  Blind image quality assessment: A natural scene statistics approach in the dct domain,  IEEE Transactions on Image Processing 21 (2012) 3339–3352.
  * Mittal et al. [2012] A. Mittal, A. K. Moorthy, A. C. Bovik,  No-reference image quality assessment in the spatial domain,  IEEE Transactions on image processing 21 (2012) 4695–4708.
  * Ou et al. [2019] F.-Z. Ou, Y.-G. Wang, G. Zhu,  A novel blind image quality assessment method based on refined natural scene statistics,  in: 2019 IEEE International Conference on Image Processing (ICIP), 2019.
  * Li et al. [2019] Q. Li, W. Lin, K. Gu, Y. Zhang, Y. Fang,  Blind image quality assessment based on joint log-contrast statistics,  Neurocomputing 331 (2019) 189–198.
  * Kang et al. [2014] L. Kang, P. Ye, Y. Li, D. Doermann,  Convolutional neural networks for no-reference image quality assessment,  in: 2014 IEEE Conference on Computer Vision and Pattern Recognition, 2014.
  * Ma et al. [2017a] K. Ma, W. Liu, K. Zhang, Z. Duanmu, Z. Wang, W. Zuo,  End-to-end blind image quality assessment using deep neural networks,  IEEE Transactions on Image Processing 27 (2017a) 1202–1213.
  * Ma et al. [2017b] K. Ma, W. Liu, T. Liu, Z. Wang, D. Tao,  dipiq: Blind image quality assessment by learning-to-rank discriminable image pairs,  IEEE Transactions on Image Processing 26 (2017b) 3951–3964.
  * Liu et al. [2017] X. Liu, J. van de Weijer, A. D. Bagdanov,  Rankiqa: Learning from rankings for no-reference image quality assessment,  in: Proceedings of the IEEE International Conference on Computer Vision, 2017, pp. 1040–1049.
  * Burges et al. [2005] C. J. C. Burges, T. Shaked, E. Renshaw, A. Lazier, G. N. Hullender,  Learning to rank using gradient descent,  in: Machine Learning, Proceedings of the Twenty-Second International Conference (ICML 2005), Bonn, Germany, August 7-11, 2005, 2005.
  * Yan et al. [2018] Q. Yan, D. Gong, Y. Zhang,  Two-stream convolutional networks for blind image quality assessment,  IEEE Transactions on Image Processing 28 (2018) 2200–2211.
  * Yang et al. [2019] S. Yang, Q. Jiang, W. Lin, Y. Wang,  Sgdnet: An end-to-end saliency-guided deep neural network for no-reference image quality assessment,  in: Proceedings of the 27th ACM International Conference on Multimedia, 2019, pp. 1383–1391.
  * Yang et al. [2020] X. Yang, F. Li, H. Liu,  Deep feature importance awareness based no-reference image quality prediction,  Neurocomputing (2020).
  * Jia and Zhang [2018] S. Jia, Y. Zhang,  Saliency-based deep convolutional neural network for no-reference image quality assessment,  Multimedia Tools and Applications 77 (2018) 14859–14872.
  * Hu et al. [2018] J. Hu, L. Shen, G. Sun,  Squeeze-and-excitation networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 7132–7141.
  * Davis et al. [2009] H. Davis, S. Russell, E. Barriga, M. Abramoff, P. Soliz,  Vision-based, real-time retinal image quality assessment,  in: 2009 22nd IEEE International Symposium on Computer-Based Medical Systems, IEEE, 2009, pp. 1–6.
  * Usher et al. [2003] D. Usher, M. Himaga, M. Dumskyj, J. Boyce,  Automated assessment of digital fundus image quality using detected vessel area,  in: Proceedings of Medical Image Understanding and Analysis, Citeseer, 2003, pp. 81–84.
  * Köhler et al. [2013] T. Köhler, A. Budai, M. F. Kraus, J. Odstrčilik, G. Michelson, J. Hornegger,  Automatic no-reference quality assessment for retinal fundus images using vessel segmentation,  in: Proceedings of the 26th IEEE international symposium on computer-based medical systems, IEEE, 2013, pp. 95–100.
  * Hunter et al. [2011] A. Hunter, J. A. Lowell, M. Habib, B. Ryder, A. Basu, D. Steel,  An automated retinal image quality grading algorithm,  in: 2011 Annual International Conference of the IEEE Engineering in Medicine and Biology Society, IEEE, 2011, pp. 5955–5958.
  * Tennakoon et al. [2016] R. Tennakoon, D. Mahapatra, P. Roy, S. Sedai, R. Garnavi,  Image quality classification for dr screening using convolutional neural networks (2016).
  * Chollet [2017] F. Chollet,  Xception: Deep learning with depthwise separable convolutions,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 1251–1258.
  * Saha et al. [2018] S. K. Saha, B. Fernando, J. Cuadros, D. Xiao, Y. Kanagasingam,  Automated quality assessment of colour fundus images for diabetic retinopathy screening in telemedicine,  Journal of digital imaging 31 (2018) 869–878.
  * Raj et al. [2020] A. Raj, N. A. Shah, A. K. Tiwari, M. G. Martini,  Multivariate regression-based convolutional neural network model for fundus image quality assessment,  IEEE Access 8 (2020) 57810–57821.
  * Achanta et al. [2009] R. Achanta, S. Hemami, F. Estrada, S. Susstrunk,  Frequency-tuned salient region detection,  in: 2009 IEEE conference on computer vision and pattern recognition, IEEE, 2009, pp. 1597–1604.
  * Nguyen et al. [2013] U. T. Nguyen, A. Bhuiyan, L. A. Park, K. Ramamohanarao,  An effective retinal blood vessel segmentation method using multi-scale line detection,  Pattern recognition 46 (2013) 703–715.
  * Huang et al. [2017] G. Huang, Z. Liu, L. Van Der Maaten, K. Q. Weinberger,  Densely connected convolutional networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 4700–4708.
  * Selvaraju et al. [2017] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, D. Batra,  Grad-cam: Visual explanations from deep networks via gradient-based localization,  in: Proceedings of the IEEE international conference on computer vision, 2017, pp. 618–626.


# Faster queries for longest substring palindrome after block edit

Mitsuru Funakoshi  Department of Informatics, Kyushu University, Japan
<EMAIL_ADDRESS>Yuto Nakashima  Department of Informatics, Kyushu University, Japan
<EMAIL_ADDRESS>Shunsuke Inenaga  Department of Informatics, Kyushu University, Japan
<EMAIL_ADDRESS>Hideo Bannai  Department of Informatics, Kyushu University, Japan
<EMAIL_ADDRESS>Masayuki Takeda  Department of Informatics, Kyushu University, Japan
<EMAIL_ADDRESS>
###### Abstract

_Palindromes_ are important objects in strings which have been extensively
studied from combinatorial, algorithmic, and bioinformatics points of views.
Manacher [J. ACM 1975] proposed a seminal algorithm that computes the longest
substring palindromes (LSPals) of a given string in $O(n)$ time, where $n$ is
the length of the string. In this paper, we consider the problem of finding
the LSPal after the string is _edited_. We present an algorithm that uses
$O(n)$ time and space for preprocessing, and answers the length of the LSPals
in $O(\ell+\log\log n)$ time, after a substring in $T$ is replaced by a string
of arbitrary length $\ell$. This outperforms the query algorithm proposed in
our previous work [CPM 2018] that uses $O(\ell+\log n)$ time for each query.

##  1 Introduction

_Palindromes_ are strings that read the same forward and backward. Finding
palindromic structures in strings has important applications in analysis of
DNA, RNA, and protein sequences, and thus a variety of efficient algorithms
for finding palindromic structures occurring in a given string have been
proposed (e.g., see [3, 18, 12, 15, 19, 14, 10] and references therein).

In this paper, we consider the fundamental problem of finding the _longest
substring palindrome_ (_LSPal_) in a given string $T$. Observe that the
longest substring palindrome is also a maximal (non-extensible) palindrome in
the string, whose center is an integer position if its length is odd, or a
half-integer position if its length is even. Hence, in order to compute the
LSPal of a given string $T$, it suffices to compute all maximal palindromes in
$T$. Manacher [16] gave an elegant $O(n)$-time algorithm to find all maximal
palindromes in a given string of length $n$. Manacher’s algorithm utilizes
symmetry of palindromes and character equality comparisons only, and therefore
works in $O(n)$ time for any alphabet. There is an alternative suffix tree
[21] based algorithm which works in $O(n)$ time in the case of an integer
alphabet of polynomial size in $n$ [13]. Finding the longest substring
palindrome in the streaming model has also been considered [6, 11].

Now we consider the following question: what happens to those palindromes if
the string $T$ is edited? It seems natural to ask this kind of question since
a typical biological sequence can contain some uncertainties such that there
are multiple character possibilities at some positions in the sequence. In our
recent work [9], we initiated this line of research and showed the following
results. Let $n$ be the length of the input string $T$ and $\sigma$ the
alphabet size.

1-ELSPal:

We can preprocess $T$ in $O(n)$ time and space such that later, we can answer
in $O(\log\min\\{\sigma,\log n\\})$ time the longest substring palindrome
after a single character edit operation (insertion, deletion, or
substitution).

$\ell$-ELSPal:

We can preprocess $T$ in $O(n)$ time and space such that later, we can answer
in $O(\ell+\log n)$ time the longest substring palindrome after a block-wise
edit operation, where $\ell$ is the length of the new block that substitutes
the substring in $T$.

In this paper, we further pursue the second variant of the problem
($\ell$-ELSPal) where an existing substring is replaced with a new string
(block) of length $\ell$. We remark that the length $\ell$ of a new block is
arbitrary. The main result of this paper is an $O(\ell+\log\log n)$-time query
algorithm that answers the longest substring palindrome after a block-wise
edit operation, with $O(n)$-time and space preprocessing.

Note that $\ell$-ELSPal is a generalization of $1$-ELSPal, where $\ell=1$ for
insertion and substitution and $\ell=0$ for deletion. Therefore, the result of
this paper achieves $O(\log\log n)$-time query algorithm for $1$-ELSPal. This
is as efficient as the $O(\log\min\\{\sigma,\log n\\})$-time query of [9] when
the alphabet size $\sigma$ is at least $O(\log n)$ (e.g., in the case of an
integer alphabet).

Related work. Amir et al. [1] proposed an algorithm to find the _longest
common factor_ (_LCF_) of two strings, after a single character edit operation
is performed in one of the strings. Their data structure occupies
$O(n\log^{3}n)$ space and uses $O(\log^{3}n)$ query time, where $n$ is the
length of the input strings. Their data structure can be constructed in
$O(n\log^{4}n)$ expected time. Urabe et al. [20] considered the problem of
computing the longest _Lyndon word_ after an edit operation. They showed
$O(\log n)$-time queries for a single character edit operation and
$O(\ell\log\sigma+\log n)$-time queries for a block-wise edit operation, both
using $O(n)$ time and space for preprocessing. We note that in these results
including ours in this current paper, edit operations are given as _queries_
and thus the input string(s) remain static even after each query. This is due
to the fact that changing the data structure dynamically can be too costly in
many cases. It is noteworthy, however, that a dynamic version for the LCF
problem is recently proposed [2].

##  2 Preliminaries

Let $\Sigma$ be the alphabet. An element of $\Sigma^{*}$ is called a string.
The length of a string $T$ is denoted by $|T|$. The empty string $\varepsilon$
is a string of length 0, namely, $|\varepsilon|=0$. For a string $T=xyz$, $x$,
$y$ and $z$ are called a _prefix_ , _substring_ , and _suffix_ of $T$,
respectively. For two strings $X$ and $Y$, let $\mathit{lcp}(X,Y)$ denote the
length of the longest common prefix of $X$ and $Y$.

For a string $T$ and an integer $1\leq i\leq|T|$, $T[i]$ denotes the $i$-th
character of $T$, and for two integers $1\leq i\leq j\leq|T|$, $T[i..j]$
denotes the substring of $T$ that begins at position $i$ and ends at position
$j$. For convenience, let $T[i..j]=\varepsilon$ when $i>j$. An integer $p\geq
1$ is said to be a _period_ of a string $T$ iff $T[i]=T[i+p]$ for all $1\leq
i\leq|T|-p$. If a string $B$ is both a proper prefix and a proper suffix of
another string $T$, then $B$ is called a _border_ of $T$.

For any string $P$, let ${P}^{\mathit{R}}$ denote the reversed string of $P$.
A string $P$ is called a _palindrome_ if $P={P}^{\mathit{R}}$. A non-empty
substring palindrome $T[i..j]$ is said to be a _maximal palindrome_ of $T$ if
$T[i-1]\neq T[j+1]$, $i=1$, or $j=|T|$. For any non-empty substring palindrome
$T[i..j]$ in $T$, $\frac{i+j}{2}$ is called its _center_. It is clear that for
each center $q=1,1.5,\ldots,n-0.5,n$, we can identify the maximal palindrome
$T[i..j]$ whose center is $q$ (namely, $q=\frac{i+j}{2}$). Thus, there are
exactly $2n-1$ maximal palindromes in a string of length $n$ (including empty
ones which occur at center $\frac{i+j}{2}$ when $T[i]\neq T[j]$).

A _rightward longest common extension_ (_rightward LCE_) query on a string $T$
is to compute $\mathit{lcp}(T[i..|T|],T[j..|T|])$ for given two positions
$1\leq i\neq j\leq|T|$. Similarly, a _leftward LCE_ query is to compute
$\mathit{lcp}({T[1..i]}^{\mathit{R}},{T[1..j]}^{\mathit{R}})$. We denote by
$\mathsf{RightLCE}_{T}(i,j)$ and $\mathsf{LeftLCE}_{T}(i,j)$ rightward and
leftward LCE queries for positions $1\leq i\neq j\leq|T|$, respectively. An
_outward LCE_ query is, given two positions $1\leq i<j\leq|T|$, to compute
$\mathit{lcp}({(T[1..i])}^{\mathit{R}},T[j..|T|])$. We denote by
$\mathsf{OutLCE}_{T}(i,j)$ an outward LCE query for positions $i<j$ in the
string $T$.

Manacher [16] showed an elegant online algorithm which computes all maximal
palindromes of a given string $T$ of length $n$ in $O(n)$ time. An alternative
offline approach is to use outward LCE queries for $2n-1$ pairs of positions
in $T$. Using the suffix tree [21] for string $T\${T}^{\mathit{R}}\\#$
enhanced with a lowest common ancestor data structure [4], where $\$$ and
$\\#$ are special characters which do not appear in $T$, each outward LCE
query can be answered in $O(1)$ time. For any integer alphabet of size
polynomial in $n$, preprocessing for this approach takes $O(n)$ time and space
[8, 13].

A palindromic substring $P$ of a string $T$ is called a _longest substring
palindrome_ (_LSPal_) if there are no palindromic substrings of $T$ which are
longer than $P$. Since any LSPal of $T$ is always a maximal palindrome of $T$,
we can find all LSPals and their lengths in $O(n)$ time.

In this paper, we consider the problem of finding an LSPal after a substring
of $T$ is replaced with another string. The problem is formally defined as
follows:

######  Definition 1 (Longest substring palindrome query after block edit).

Preprocess:

A string $T$ of length $n$.

Query input:

An interval $[i,j]\subseteq[1,n]$ and a string $X$ of length $\ell$.

Query output:

(The length of) a longest substring palindrome in the edited string
$T^{\prime}=T[1..i-1]XT[j+1..n]$.

The query in the above problem is called an _$\ell$ -block edit longest
substring palindrome_ query (_$\ell$ -ELSPal_ query in short). In the
following section, we will propose an $O(n)$-time and space preprocessing
scheme such that subsequent $\ell$-ELSPal queries can be answered in
$O(\ell+\log\log n)$ time. We remark that in this problem string edits are
only given as _queries_ , i.e., we do not explicitly rewrite the original
string $T$ into $T^{\prime}$ and $T$ remains unchanged for further queries. We
also remark that in our problem the length $\ell$ of a substring $X$ that
substitutes a given interval (substring) can be arbitrary.

Let $\ell^{\prime}$ be the length of the substring to be replaced, i.e.,
$\ell^{\prime}=j-i+1$. Our block-wise edit operation generalizes character-
wise substitution when $\ell^{\prime}>0$ and $\ell>0$, character-wise
insertion when $\ell^{\prime}=0$ and $\ell>0$, and character-wise deletion
when $\ell^{\prime}>0$ and $\ell=0$.

The following properties of palindromes are useful in our algorithms.

######  Lemma 1.

Any border $B$ of a palindrome $P$ is also a palindrome.

###### Proof.

Because $P$ is a palindrome, for any $1\leq m\leq|P|$, clearly
$P[1..m]={(P[|P|-m+1..|P|])}^{\mathit{R}}$. Since $B$ is a border of $P$, we
have that $B=P[1..|B|]={(P[|P|-|B|+1..|P|])}^{\mathit{R}}={B}^{\mathit{R}}$. ∎

Let $T$ be a string of length $n$. For each $1\leq i\leq n$, let
$\mathit{MaxPalEnd}_{T}(i)$ denote the set of maximal palindromes of $T$ that
end at position $i$. Let $\mathbf{S}_{i}=s_{1},\ldots,s_{g}$ be the sequence
of lengths of maximal palindromes in $\mathit{MaxPalEnd}_{T}(i)$ sorted in
increasing order, where $g=|\mathit{MaxPalEnd}_{T}(i)|$. Let $d_{j}$ be the
progression difference for $s_{j}$, i.e., $d_{j}=s_{j}-s_{j-1}$ for $2\leq
j\leq g$. For convenience, let $d_{1}=0$. We use the following lemma which is
based on periodic properties of maximal palindromes ending at the same
position.

######  Lemma 2 ([9]).

  1. (i)

For any $1\leq j<g$, $d_{j+1}\geq d_{j}$.

  2. (ii)

For any $1<j<g$, if $d_{j+1}\neq d_{j}$, then $d_{j+1}\geq d_{j}+d_{j-1}$.

  3. (iii)

$\mathbf{S}_{i}$ can be represented by $O(\log i)$ arithmetic progressions,
where each arithmetic progression is a tuple $\langle s,d,t\rangle$
representing the sequence $s,s+d,\ldots,s+(t-1)d$ with common difference $d$.

  4. (iv)

If $t\geq 2$, then the common difference $d$ is a period of every maximal
palindrome which end at position $i$ in $T$ and whose length belongs to the
arithmetic progression $\langle s,d,t\rangle$.

See also Fig. 2 in the next section. Each arithmetic progression $\langle
s,d,t\rangle$ is called a _group_ of maximal palindromes. Similar arguments
hold for the set $\mathit{MaxPalBeg}_{T}(i)$ of maximal palindromes of $T$
that begin at position $i$. For all $1\leq i\leq n$ we can compute
$\mathit{MaxPalEnd}_{T}(i)$ and $\mathit{MaxPalBeg}_{T}(i)$ in total $O(n)$
time: After computing all maximal palindromes of $T$ in $O(n)$ time, we can
bucket sort all the maximal palindromes with their ending positions and with
their beginning positions in $O(n)$ time each.

##  3 Algorithm for $\ell$-ELSPal

Consider to substitute a substring $X$ of length $\ell$ for the substring
$T[i_{b}..i_{e}]$ beginning at position $i_{b}$ and ending at position
$i_{e}$, where $i_{e}-i_{b}+1=\ell^{\prime}$ and $X\neq T[i_{b}..i_{e}]$. Let
$T^{\prime}=T[1..i_{b}-1]XT[i_{e}+1..n]$ be the string after the edit.

In order to compute (the lengths of) maximal palindromes that are affected by
the block-wise edit operation, we need to know the first (leftmost)
mismatching position between $T$ and $T^{\prime}$, and that between
${T}^{\mathit{R}}$ and ${T^{\prime}}^{\mathit{R}}$. Let $h$ and $l$ be the
smallest integers such that $T[h]\neq T^{\prime}[h]$ and
${T}^{\mathit{R}}[l]\neq{T^{\prime}}^{\mathit{R}}[l]$, respectively. If such
$h$ does not exist, then let $h=\min\\{|T|,|T^{\prime}|\\}+1$. Similarly, if
such $l$ does not exist, then let $l=\min\\{|T|,|T^{\prime}|\\}+1$. Let
$j_{1}=\mathit{lcp}(T[i_{b}..n],XT[i_{e}..n])$,
$j_{2}=\mathit{lcp}({(T[1..i_{e}])}^{\mathit{R}},{(T[1..i_{b}]X)}^{\mathit{R}})$,
$p_{b}=i_{b}+j_{1}$, and $p_{e}=i_{e}-j_{2}$. There are two cases: (1) If
$j_{1}=j_{2}=0$, then the first and last characters of $T[i_{b}..i_{e}]$
differ from those of $X$. In this case, we have $i_{b}=h$ and $i_{e}=n-l+1$.
We use these positions $i_{b}$ and $i_{e}$ to compute maximal palindromes
after the block-wise edit. (2) Otherwise, we have $p_{b}=i_{b}+j_{1}=h$ and
$p_{e}=i_{e}-j_{2}=n-l+1$. We use these positions $p_{b}$ and $p_{e}$ to
compute maximal palindromes after the block-wise edit.

In the next subsection, we describe our algorithm for Case (1). Case (2) can
be treated similarly, by replacing $i_{b}$ and $i_{e}$ with $p_{b}$ and
$p_{e}$, respectively. Our algorithm can handle the case where $p_{e}<p_{b}$.
Remark that $p_{b}$ and $p_{e}$ can be computed in $O(\ell)$ time by naïve
character comparisons and a single LCE query each.

We remark that the longest extension of the maximal palindromes in $T$ which
are unchanged or shortened after the block edit can be found $O(1)$ time upon
query, after $O(n)$-time and space preprocessing, using similar techniques to
the $1$-ELSPal queries from our previous work [9]. Also, the longest maximal
palindromes that have centers in the new block can be computed in $O(\ell)$
time after $O(n)$-time and space preprocessing, in a similar way to our
previous algorithm for the $1$-ELSPal [9]. Hence, in this paper we concentrate
on the maximal palindromes of $T$ which get extended after the block edit. The
next observation describes such maximal palindromes.

######  Observation 1 ([9]).

For any $s\in\mathit{MaxPalEnd}_{T}(i_{b}-1)$, the corresponding maximal
palindrome $T[i_{b}-s..i_{b}-1]$ centered at $\frac{2i_{b}-s-1}{2}$ gets
extended in $T^{\prime}$ iff
$\mathsf{OutLCE}_{T^{\prime}}(i_{b}-s-1,i_{b})\geq 1$. Similarly, for any
$s\in\mathit{MaxPalBeg}_{T}(i_{e}+1)$, the corresponding maximal palindrome
$T[i_{e}+1..i_{e}+s]$ centered at $\frac{2i_{e}+s+1}{2}$ gets extended in
$T^{\prime}$ iff $\mathsf{OutLCE}_{T^{\prime}}(i_{e},i_{e}+s+1)\geq 1$.

It follows from Observation 1 that it suffices to compute outward LCE queries
efficiently for all maximal palindromes which end at position $i_{b}-1$ or
begin at position $i_{e}+1$ in the edited string $T^{\prime}$. The following
lemma, which is a generalization of Lemma 21 from [9], shows how to
efficiently compute the extensions of any given maximal palindromes that end
at position $i_{b}-1$. Those that begin at position $i_{e}+1$ can be treated
similarly.

######  Lemma 3.

Let $T$ be a string of length $n$ over an integer alphabet of size
polynomially bounded in $n$. We can preprocess $T$ in $O(n)$ time and space so
that later, given a list of any $f$ maximal palindromes from
$\mathit{MaxPalEnd}_{T}(i_{b}-1)$, we can compute in $O(\ell+f)$ time the
extensions of those $f$ maximal palindromes in the edited string $T^{\prime}$,
where $\ell$ is the length of a new block.

###### Proof.

Let us remark that the maximal palindromes in the list can be given to our
algorithm in any order. Firstly, we compute the extensions of given maximal
palindromes from the list until finding the first maximal palindrome whose
extension $\tau$ is at least one, and let $s^{\prime}$ be the length of this
maximal palindrome. Namely, $s^{\prime}+2\tau$ is the length of the extended
maximal palindrome for $s^{\prime}$, and the preceding maximal palindromes (if
any) were not extended. Let $s$ be the length of the next maximal palindrome
from the list after $s^{\prime}$, and now we are to compute the extension
$\lambda$ for $s$. See also Figure 1.

Figure 1: Illustration for Lemma 3, where solid arrows represent the matches
obtained by naïve character comparisons, and broken arrows represent those
obtained by LCE queries. This figure only shows the case where $s^{\prime}<s$,
but the other case where $s^{\prime}>s$ can be treated similarly.

There are two cases: (1) If $0<\tau<\ell$, then we first compute
$\delta=\mathsf{LeftLCE}_{T}(i_{b}-s-1,i_{b}-s^{\prime}-1)$. We have two sub-
cases: (1-a) If $\delta<\tau$, then $\lambda=\delta$. (1-b) Otherwise
($\delta\geq\tau$), then we know that $\lambda$ is at least as large as
$\tau$. We then compute the remainder of $\lambda$ by naïve character
comparisons. If the character comparison reaches the end of $X$, then the
remainder of $\lambda$ can be computed by
$\mathsf{OutLCE}_{T}(i_{b}-s-\ell-1,i_{e}+1)$. Then we update $\tau$ with
$\lambda$. (2) If $\tau\geq\ell$, then we can compute $\lambda$ by
$\mathsf{LeftLCE}_{T}(i_{b}-s-1,i_{b}-s^{\prime}-1)$, and if this value is at
least $\ell$, then by $\mathsf{OutLCE}_{T}(i_{b}-s-\ell-1,i_{e}+1)$. The
extensions of the following palindromes can also be computed similarly.

The following maximal palindromes from the list after $s$ can be processed
similarly. After processing all the $f$ maximal palindromes in the given list,
the total number of matching character comparisons is at most $\ell$ since
each position of $X$ is involved in at most one matching character comparison.
Also, the total number of mismatching character comparisons is $O(f)$ since
for each given maximal palindrome there is at most one mismatching character
comparison. The total number of LCE queries on the original text $T$ is
$O(f)$, each of which can be answered in $O(1)$ time. Thus, it takes
$O(\ell+f)$ time to compute the length of the $f$ maximal palindromes of
$T^{\prime}$ that are extended after the block edit. ∎

However, there can be $\Omega(n)$ maximal palindromes beginning or ending at
each position of a string of length $n$. In what follows, we show how to
reduce the number of maximal palindromes that need to be considered, by using
periodic structures of maximal palindromes.

Let $\langle s,d,t\rangle$ be an arithmetic progression representing a group
of maximal palindromes ending at position $i_{b}-1$. For each $1\leq j\leq t$,
we will use the convention that $s(j)=s+(j-1)d$, namely $s$ denotes the $j$th
shortest element for $\langle s,d,t\rangle$. For simplicity, let
$Y=T[1..i_{b}-1]$ and $Z=XT[i_{e}+1..n]$. Let $\mathit{Ext}(s_{j})$ denote the
length of the maximal palindrome that is obtained by extending $s_{j}$ in
$YZ$.

######  Lemma 4 ([9]).

For any $\langle s,d,t\rangle\subseteq\mathit{MaxPalEnd}_{T}(i_{b}-1)$, there
exist palindromes $u,v$ and a non-negative integer $p$, such that
$(uv)^{t+p-1}u$ (resp. $(uv)^{p}u$) is the longest (resp. shortest) maximal
palindrome represented by $\langle s,d,t\rangle$ with $|uv|=d$. Let
$\alpha=\mathit{lcp}({(Y[1..|Y|-s_{1}])}^{\mathit{R}},Z)$ and
$\beta=\mathit{lcp}({(Y[1..|Y|-s_{t}])}^{\mathit{R}},Z)$. If there exists
$s_{h}\in\langle s,d,t\rangle$ such that $s_{h}+\alpha=s_{t}+\beta$, then let
$\gamma=\mathit{lcp}({(Y[1..|Y|-s_{h}])}^{\mathit{R}},Z)$. Then, for any
$s_{j}\in\langle s,d,t\rangle\setminus\\{s_{h}\\}$,
$\mathit{Ext}(s_{j})=s_{j}+2\min\\{\alpha,\beta+(t-j)d\\}$. Also, if $s_{h}$
exists, then $\mathit{Ext}(s_{h})=s_{h}+2\gamma\geq\mathit{Ext}(s_{j})$ for
any $j\neq h$.

Figure 2: Example for Lemma 4, where
$Y=\mathtt{accbaaabaaabaaabaaabaaabaaabaa}$ and $Z=\mathtt{abaaabaaabccc}$.
Here $u=\mathtt{a}$ and $v=\mathtt{aba}$. The first five maximal palindromes
$(uv)^{k}u=(\mathtt{aaba})^{k}\mathtt{a}$ with $2\leq k\leq 5$ belong to the
same arithmetic progression (i.e. the same group) with common difference
$|uv|=d=4$. For this group of maximal palindromes, $\alpha=10$, $\beta=2$, and
$\gamma=12$. Notice that the sixth maximal palindrome $uvu=\mathtt{aabaa}$
belongs to another group since the length difference between it and the
seventh one $\mathtt{aa}$ is $3$.

See Figure 2 for a concrete example of Lemma 4. It follows from Lemma 4 that
it suffices to consider only three maximal palindromes from each group (i.e.
each arithmetic progression). Then using Lemma 3, one can compute the longest
maximal palindrome that gets extended in $O(\ell+\log n)$ time, and this is
exactly how the algorithm from our previous paper [9] works.

To further speed up computation, we take deeper insights into combinatorial
properties of maximal palindromes in $\mathit{MaxPalEnd}_{T}(i_{b}-1)$. Let
$G_{1},\ldots,G_{m}$ be the list of all groups for the maximal palindromes
from $\mathit{MaxPalEnd}_{T}(i_{b}-1)$, which are _sorted in increasing order
of their common difference_. When $m=O(\log\log n)$, $O(\ell+\log\log n)$-time
queries immediately follow from Lemmas 3 and 4. In what follows we consider
the more difficult case where $m=\omega(\log\log n)$. Recall also that
$m=O(\log n)$ always holds.

For each $G_{r}=\langle s_{r},d_{r},t_{r}\rangle$ with $1\leq r\leq m$, let
$\alpha_{r}$, $\beta_{r}$, $\gamma_{r}$, $u_{r}$, and $v_{r}$ be the
corresponding variables used in Lemma 4. If there is only a single element in
$G_{r}$, let $\beta_{r}$ be the length of extension of the palindrome and
$\alpha_{r}=\beta_{r-1}$. For each $G_{r}$, let $S_{r}$ (resp. $L_{r}$) denote
the shortest (resp. longest) maximal palindrome in $G_{r}$, namely,
$|S_{r}|=s_{r}(1)$ and $|L_{r}|=s_{r}(t_{r})$.

Each group $G_{r}$ is said to be of _type-1_ (resp. _type-2_) if
$\alpha_{r}<d_{r}$ (resp. $\alpha_{r}\geq d_{r}$).

Let $k$ ($1\leq k\leq m$) be the unique integer such that $G_{k}$ is the
type-2 group where $d_{k}$ is the largest common difference among all the
type-2 groups. Additionally, let
$G^{\prime}_{k}=G_{k}\cup\\{u_{k}v_{k}u_{k},u_{k}\\}$. Note that $u_{k}$
belongs to one of $G_{1},\ldots,G_{k-1}$, and $u_{k}v_{k}u_{k}$ belongs to
either $G_{k}$ or one of $G_{1},\ldots,G_{k-1}$. In the special case where
$\alpha_{k}=\beta_{k}+td_{k}$, the extensions of $u_{k}$ and $u_{k}v_{k}u_{k}$
can be longer than the extension of the shortest maximal palindrome in $G_{k}$
(see Figure 5 in Appendix for a concrete example). Thus, it is convenient for
us to treat $G^{\prime}_{k}=G_{k}\cup\\{u_{k}v_{k}u_{k},u_{k}\\}$ as if it is
a single group. We also remark that this set $G^{\prime}_{k}$ is defined only
for this specific type-2 group $G_{k}$.

######  Lemma 5.

There is a longest substring palindrome in the edited string $T^{\prime}$ that
is obtained by extending the maximal palindromes in $G_{m}$, $G_{m-1}$, or
$G^{\prime}_{k}$.

###### Proof.

The lemma holds if the two following claims are true:

Claim (1):

The extensions of the maximal palindromes in $G_{1},\ldots,G_{k-1}$, except
for $u_{k}v_{k}u_{k}$ and $u_{k}$, cannot be longer than the extension of the
shortest maximal palindrome in $G_{k}$.

Claim (2)

Suppose both $G_{m}$ and $G_{m-1}$ are of type-1. Then, the extensions of the
maximal palindromes from $G_{k+1},\ldots,G_{m-2}$, which are also of type-1,
cannot be longer than the extensions of the maximal palindromes from $G_{m}$
or $G_{m-1}$.

Proof for Claim (1). Here we consider the case where the maximal palindrome
$u_{k}v_{k}u_{k}$ does not belong to $G_{k}$, which implies that the shortest
maximal palindrome $S_{k}$ in $G_{k}$ is $(u_{k}v_{k})^{2}u_{k}$ (The other
case where $u_{k}v_{k}u_{k}$ belongs to $G_{k}$ can be treated similarly).
Now, $u_{k}v_{k}u_{k}$ belongs to one of $G_{1},\ldots,G_{k-1}$. Consider the
prefix $P=T[1..i_{b}-|u_{k}v_{k}u_{k}|-1]$ of $T$ that immediately precedes
$u_{k}v_{k}u_{k}$. The extension of $u_{k}v_{k}u_{k}$ is obtained by
$\mathit{lcp}({P}^{\mathit{R}},Z)$. Consider the prefix
$P^{\prime}=T[1..i_{b}-|(u_{k}v_{k})^{2}u_{k}|]$ of $T$ that immediately
precedes. It is clear that $P$ is a concatenation of $P^{\prime}$ and
$u_{k}v_{k}$. Similarly, the prefix $T[1..i_{b}-|u_{k}|-1]$ of $T$ that
immediately precedes $u_{k}$ is a concatenation of $P$ and $u_{k}v_{k}$. From
Lemma 4 and the definition of $G^{\prime}_{k}$, it suffices for us to consider
only the three maximal palindromes from $G^{\prime}_{k}$. For any other
maximal palindrome $Q$ from $G_{1},\ldots,G_{k-1}$, assume on the contrary
that $Q$ gets extended by at least $d_{k}$ to the left and to the right. If
$|u_{k}v_{k}|=d_{k}<|Q|<|u_{k}v_{k}u_{k}|$, then there is an internal
occurrence of $u_{k}v_{k}$ inside the prefix $(u_{k}v_{k})^{2}$ of
$(u_{k}v_{k})^{2}u_{k}$. Otherwise ($|u_{k}|<|Q|<|u_{k}v_{k}|=d_{k}$ or
$|Q|<|u_{k}|$), there is an internal occurrence of $u_{k}v_{k}$ inside
$u_{k}v_{k}u_{k}$. Here we only consider the first case but other cases can be
treated similarly. See also Figure 3. This internal occurrence of $u_{k}v_{k}$
is immediately followed by $u_{k}v_{k}w$, where $w$ is a proper prefix of
$u_{k}$ with $1\leq|w|<|u_{k}|$. Namely, $(u_{k}v_{k})^{2}w$ is a proper
suffix of $(u_{k}v_{k})^{2}u$. On the other hand, $(u_{k}v_{k})^{2}w$ is also
a proper prefix of $(u_{k}v_{k})^{2}u_{k}$. Since $(u_{k}v_{k})^{2}u$ is a
palindrome, it now follows from Lemma 1 that $(u_{k}v_{k})^{2}w$ is also a
palindrome. Since $1\leq|w|<|u_{k}|$, we have
$|(u_{k}v_{k})^{2}w|>|u_{k}v_{k}u_{k}|$ (note that this inequality holds also
when $v_{k}$ is the empty string). However this contradicts that
$(u_{k}v_{k})^{2}u_{k}$ belongs to $G_{k}$ with common difference
$d_{k}=|u_{k}v_{k}|$. Thus $Q$ cannot be extended by $d_{k}$ nor more to the
left and to the right. Since $G_{k}$ is of type-2, $\alpha_{k}\geq d_{k}$.
Since $|Q|<|(u_{k}v_{k})^{2}u_{k}|$, the extension of any $Q$ cannot be longer
than the extension for $(u_{k}v_{k})^{2}u_{k}$. This completes the proof for
Claim (1).

Figure 3: Illustration for the proof for Claim (1) of Lemma 5.

Proof for Claim (2). Consider each group $G_{r}=\langle
s_{r},d_{r},t_{r}\rangle$ with $k+1\leq r\leq m-2$. By Lemma 4,
$s_{r}(t_{r})+2\beta_{r}$ and $s_{r}(t-1)+2\alpha_{r}$ are the candidates for
the longest extensions of the maximal palindromes from $G_{r}$. Recall that
both $G_{m-1}$ and $G_{m}$ are of type-1, and that if $G_{r}$ is of type-1
then $G_{r+1}$ is also of type-1. Now the following sub-claim holds:

######  Lemma 6.

$\beta_{r}=\alpha_{r+1}$ for any $k+1\leq r\leq m-2$.

###### Proof.

If $G_{r+1}$ is a singleton, then by definition $\beta_{r}=\alpha_{r+1}$
holds. Now suppose $|G_{r+1}|\geq 2$. Since the shortest maximal palindrome
$S_{r+1}$ from $G_{r+1}$ is either $(u_{z+1}v_{z+1})^{2}u_{z+1}$ or
$u_{z+1}v_{z+1}u_{z+1}$, the longest maximal palindrome $L_{r}$ from $G_{r}$
is either $u_{r+1}v_{r+1}u_{r+1}$ or $u_{r+1}$. The prefix
$T[1..i_{b}-|L_{r}|-1]$ of $T$ that immediately precedes $L_{r}$ contains
$u_{r+1}v_{r+1}$ as a suffix, which alternatively means
${(u_{r+1}v_{r+1})}^{\mathit{R}}$ is a prefix of
${(T[1..i_{b}-|L_{r}|-1])}^{\mathit{R}}$. Moreover, it is clear that the
prefix $T[1..i_{b}-|S_{r+1}|-1]$ of $T$ that immediately precedes $S_{r+1}$
contains $u_{r+1}v_{r+1}$ as a suffix since $|G_{r+1}|\geq 2$. In addition,
$\alpha_{r+1}<d_{r+1}=|u_{r+1}v_{r+1}|$ since $G_{r+1}$ is of type-1. From the
above arguments, we get $\beta_{r}=\alpha_{r+1}$. ∎

Since $\beta_{r}=\alpha_{r+1}$ and $\alpha_{r+1}<d_{r+1}$, we have
$s_{r}(t_{r})+2\beta_{r}<s_{r}(t_{r})+2d_{r+1}$. In addition,
$s_{r}(t_{r}-1)+2\alpha_{r}<s_{r}(t_{r}-1)+2d_{r}=s_{r}(t_{r})+d_{r}$. It now
follows from $d_{r}<d_{r+1}$ that $s_{r}(t_{r})+d_{r}<s_{r}(t_{r})+2d_{r+1}$.
Since the lengths of the maximal palindromes and their common differences are
arranged in increasing order in the groups $G_{k+1},\ldots.G_{m-2}$, we have
that the longest extension from $G_{k+1},\ldots.G_{m-2}$ is shorter than
$s_{m-2}(t_{m-2})+2d_{m-1}$. Since $d_{m-1}<d_{m}$, we have

$s_{m-2}(t_{m-2})+2d_{m-1}<s_{m-2}(t_{m-2})+d_{m-1}+d_{m}\leq
s_{m-1}(t_{m-1})+d_{m}\leq s_{m}=s_{m}(1).$

This means that the longest extended maximal palindrome from the type-1 groups
$G_{k+1}$, $\ldots$, $G_{m-2}$ cannot be longer than the original length of
the maximal palindrome from $G_{m}$ before the extension. This completes the
proof for Claim (2). ∎

It follows from Lemmas 3, 4 and 5 that given $G_{k}$, we can compute in
$O(\ell)$ time the length of the LSPal of $T^{\prime}$ after the block edit.
What remains is how to quickly find $G_{k}$, that has the largest common
difference among all the type-2 groups. Note that a simple linear search from
$G_{m}$ or $G_{1}$ takes $O(\log n)$ time, which is prohibited when
$\ell=o(\log n)$. In what follows, we show how to find $G_{k}$ in
$O(\ell+\log\log n)$ time.

Recall that $T[1..i_{b}-|L_{r-1}|-1]$ which immediately precedes $S_{r}$
contains $u_{r}v_{r}$ as a suffix. Thus, ${(u_{r}v_{r})}^{\mathit{R}}$ is a
prefix of ${(T[1..i_{b}-|L_{r-1}|-1])}^{\mathit{R}}$. We have the following
observation.

######  Observation 2.

Let $W_{1}={(T[1..i_{b}-1])}^{\mathit{R}}$, and
$W_{r}={(T[1..i_{b}-|L_{r-1}|-1])}^{\mathit{R}}$ for $2\leq r\leq m$. Let $W$
be the string such that $\mathit{lcp}(W_{r},Z)$ is the largest for all $1\leq
r\leq m$ (i.e. for all groups $G_{1},\ldots,G_{m}$), namely, $W=\mathop{\rm
arg~{}max}\limits_{1\leq r\leq m}\mathit{lcp}(W_{r},Z)$. Then $G_{k}=G_{x}$
such that

  1. (a)

${(u_{x}v_{x})}^{\mathit{R}}$ is a prefix of $W$,

  2. (b)

$d_{x}\leq\mathit{lcp}(W,Z)$, and

  3. (c)

$d_{x}$ is the largest among all groups that satisfy Conditions (a) and (b).

Due to Observation 2, the first task is to find $W$.

######  Lemma 7.

$W$ can be found in $O(\ell+\log\log n)$ time after $O(n)$-time and space
preprocessing.

###### Proof.

We preprocess $T$ as follows. For each $1\leq i\leq n$, let
$G_{1},\ldots,G_{m}$ be the list of groups that represent the maximal
palindromes ending at position $i$ in $T$. Let
$W_{1}={(T[1..i])}^{\mathit{R}}$ and
$W_{r}={(T[1..i-|L_{r-1}|])}^{\mathit{R}}$ for $2\leq r\leq m$. Let
$\mathcal{A}_{i}$ be the _sparse suffix array_ of size $m=O(\log i)$ such that
$\mathcal{A}_{i}[j]$ stores the $j$th lexicographically smallest string in
$\\{W_{1},\ldots,W_{m}\\}$. We build $\mathcal{A}_{i}$ with the LCP array
$\mathcal{L}_{i}$. Since there are only $2n-1$ maximal palindromes in $T$,
$\mathcal{A}_{i}$ for all positions $1\leq i\leq n$ can easily be constructed
in a total of $O(n)$ time from the full suffix array of $T$. The LCP array
$\mathcal{L}_{i}$ for all $1\leq i\leq n$ can also be computed in $O(n)$ total
time from the LCP array of $T$ enhanced with a range minimum query (RMQ) data
structure [4].

To find $W$, we binary search $\mathcal{A}_{i_{b}-1}$ for $Z[1..\ell]=X$ in a
similar way to pattern matching on the suffix array with the LCP array [17].
This gives us the range of $\mathcal{A}_{i_{b}-1}$ such that the corresponding
strings have the longest common prefix with $X$. Since
$|\mathcal{A}_{i_{b}-1}|=O(\log n)$, this range can be found in
$O(\ell+\log\log n)$ time. If the longest prefix found above is shorter than
$\ell$, then this prefix is $W$. Otherwise, we perform another binary search
on this range for $Z[\ell+1..|Z|]=T[i_{e}+1..n]$, and this gives us $W$. Here
each comparison can be done in $O(1)$ time by an outward LCE query on $T$.
Hence, the longest match for $Z[\ell+1..|Z|]$ in this range can also be found
in $O(\log\log n)$ time. Overall, $W$ can be found in $O(\ell+\log\log n)$
time. ∎

######  Lemma 8.

We can preprocess $T$ in $O(n)$ time and space so that later, given $W$ for a
position in $T$, we can find $G_{k}$ for that position in $O(\log\log n)$
time.

###### Proof.

Let $\mathcal{D}_{i}$ be an array of size $|\mathcal{A}_{i}|$ such that
$\mathcal{D}_{i}[j]$ stores the value of $d_{r}=|u_{r}v_{r}|$, where $W_{r}$
is the lexicographically $j$th smallest string in $\\{W_{1},\ldots,W_{m}\\}$.
Let $\mathcal{R}_{i}$ be an array of size $|\mathcal{A}_{i}|$ where
$\mathcal{R}_{i}[j]$ stores a sorted list of common differences
$d_{r}=|u_{r}v_{r}|$ of groups $G_{r}$, such that $G_{r}$ stores maximal
palindromes ending at position $i$ and ${(u_{r}v_{r})}^{\mathit{R}}$ is a
prefix of the string w.r.t. $\mathcal{A}_{i}[j]$. Clearly, for any $j$,
$\mathcal{D}_{i}[j]\subseteq\mathcal{R}_{i}$. See also Figure 4 for an example
of $\mathcal{R}_{i}$.

Suppose that we have found $W$ by Lemma 7, and let $j$ be the entry of
$\mathcal{A}_{i_{b}-1}$ where the binary search for $X$ terminated. We then
find the largest $d_{x}$ that satisfies Condition (b) of Observation 2, by
binary search on the sorted list of common differences stored at
$\mathcal{R}_{i_{b}-1}[j]$. This takes $O(\log\log n)$ time since the list
stored at each entry of $\mathcal{R}_{i_{b}-1}$ contains at most
$|A_{i_{b}-1}|=O(\log n)$ elements.

We remark however that the total number of elements in $\mathcal{R}_{i}$ is
$O(\log^{2}i)$ since each entry $\mathcal{R}_{i}[j]$ can contain $O(\log i)$
elements. Thus, computing and storing $\mathcal{R}_{i}$ explicitly for all
text positions $1\leq i\leq n$ can take superlinear time and space.

Instead of explicitly storing $\mathcal{R}_{i}$, we use a tree representation
of $\mathcal{R}_{i}$, defined as follows: The tree consists of exactly
$m=|\mathcal{A}_{i}|$ leaves and exactly $m$ non-leaf nodes. Each leaf
corresponds to a distinct entry $j=1,\ldots,m$, and each non-leaf node
corresponds to a value from $\mathcal{D}_{i}$. Each leaf $j$ is contained in a
(sub)tree rooted at a node with $d\in\mathcal{D}_{i}$, iff there is a maximal
interval $[l..l^{\prime}]$ such that $l\leq j\leq l^{\prime}$ and
$\mathcal{L}_{i}[j+1]\geq\mathcal{D}_{i}[j]$. We associate each node with this
maximal interval. Since we have assumed $d_{1}=0$, the root stores $0$ and it
has at most $\sigma$ children. See Figure 4 for illustration.

We can easily construct this tree in time linear in its size
$m=|\mathcal{A}_{i}|$, in a bottom up manner. First, we create leaves for all
entries $j=1,\ldots,m$. Next, we build the tree in a bottom-up manner, by
performing the following operations in decreasing order of
$\mathcal{D}_{i}[j]$.

  1. (1)

Create a new node with $\mathcal{D}_{i}[j]$, and connect this node with the
highest ancestor of leaf $j$.

  2. (2)

We check $j^{\prime}<j$ in decreasing order, and connect the new node with the
highest ancestor of leaf $j^{\prime}$ iff
$\mathcal{L}_{i}[j^{\prime}+1]\geq\mathcal{D}_{i}[j]$. We skip the interval
corresponding to this ancestor, and perform the same procedure until we find
$j^{\prime}$ that does not meet the above condition. We do the same for
$j^{\prime\prime}>j$.

Since each node is associated with its corresponding interval in the LCP
array, it suffices for us to check the conditions
$\mathcal{L}_{i}[j^{\prime}+1]\geq\mathcal{D}_{i}[j]$ and
$\mathcal{L}_{i}[j^{\prime\prime}]\geq\mathcal{D}_{i}[j]$ only at either end
of the intervals that we encounter. Clearly, in the path from the root to leaf
$j$, the values in $\mathcal{R}_{j}[j]$ appear in increasing order. Thus, we
can find the largest $d_{x}$ that satisfies Condition (b) of Observation 2, by
a binary search on the corresponding path in the tree. We augment the tree
with a level ancestor data structure [7, 5], so that each binary search takes
logarithmic time in the tree height, namely $O(\log\log n)$ time. The size of
the tree for position $i$ is clearly bounded by the number of maximal
palindromes ending at position $i$. Thus, the total size and construction time
for the trees for all positions in $T$ is $O(n)$. ∎

$j$ | $W_{\mathcal{A}_{i}[1]},\ldots,W_{\mathcal{A}_{i}[m]}$ | $\mathcal{D}_{i}$ | $\mathcal{L}_{i}$ | $\mathcal{R}_{i}$
---|---|---|---|---
1 | $\mathtt{abaaabaaaaaabaaaba}\cdots$ | 689 | - | 0,1,689
2 | $\mathtt{aabaaabaaaaaabaaab}\cdots$ | 1 | 1 | 0,1
3 | $\mathtt{aaabaaabaaaaaabaaa}\cdots$ | 223 | 2 | 0,1,11,223
4 | $\mathtt{aaabaaabaaaaaabaaa}\cdots$ | 0 | 22 | 0,1,11
5 | $\mathtt{aaabaaabaaaaaabaaa}\cdots$ | 11 | 33 | 0,1,11
6 | $\mathtt{baaabaaaaaabaaabaa}\cdots$ | 4 | 0 | 0,4
7 | $\mathtt{baaaaaabaaabaaaaaa}\cdots$ | 37 | 4 | 0,4,37
8 | $\mathtt{caaabaaabaaaaaabaa}\cdots$ | 82 | 0 | 0,82

Figure 4: Example for $\mathcal{R}_{i}$ (left) and its corresponding tree
(right). The remaining parts of the strings
$W_{\mathcal{A}_{i}[1]},\ldots,W_{\mathcal{A}_{i}[m]}$ are omitted due to lack
of space.

By Lemma 3 and Lemma 8, we can compute in $O(\ell+\log\log n)$ time the length
of the LSPal of $T^{\prime}$ that are extended after the block edit.

Consequently we obtain the following theorem:

######  Theorem 1.

There is an $O(n)$-time and space preprocessing for the $\ell$-ELSPal problem
such that each query can be answered in $O(\ell+\log\log n)$ time, where
$\ell$ denotes the length of the block after edit.

Note that the time complexity for our algorithm is independent of the length
of the original block to edit. Also, the length $\ell$ of a new block is
arbitrary.

## References

  * [1] Amihood Amir, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, and Jakub Radoszewski.  Longest common factor after one edit operation.  In SPIRE 2017, pages 14–26, 2017.
  * [2] Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski.  Longest common factor made fully dynamic.  CoRR, abs/1804.08731, 2018.  URL: http://arxiv.org/abs/1804.08731.
  * [3] Alberto Apostolico, Dany Breslauer, and Zvi Galil.  Parallel detection of all palindromes in a string.  Theoretical Computer Science, 141:163–173, 1995.
  * [4] Michael A. Bender and Martin Farach-Colton.  The LCA problem revisited.  In LATIN 2000, pages 88–94, 2000.
  * [5] Michael A. Bender and Martin Farach-Colton.  The level ancestor problem simplified.  Theor. Comput. Sci., 321(1):5–12, 2004.
  * [6] Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, and Erfan Sadeqi Azer.  Palindrome recognition in the streaming model.  In STACS 2014, pages 149–161, 2014.
  * [7] O. Berkman and U. Vishkin.  Finding level-ancestors in trees.  J. Comput. System Sci., 48(2):214–230, 1994.
  * [8] Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan.  On the sorting-complexity of suffix tree construction.  J. ACM, 47(6):987–1011, 2000.
  * [9] Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Longest substring palindrome after edit.  In CPM 2018, pages 12:1–12:14, 2018.
  * [10] Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea.  Tighter bounds and optimal algorithms for all maximal $\alpha$-gapped repeats and palindromes - finding all maximal $\alpha$-gapped repeats and palindromes in optimal worst case time on integer alphabets.  Theory Comput. Syst., 62(1):162–191, 2018.
  * [11] Pawel Gawrychowski, Oleg Merkurev, Arseny M. Shur, and Przemyslaw Uznanski.  Tight tradeoffs for real-time approximation of longest palindromes in streams.  In CPM 2016, pages 18:1–18:13, 2016.
  * [12] Richard Groult, Élise Prieur, and Gwénaël Richomme.  Counting distinct palindromes in a word in linear time.  Inf. Process. Lett., 110(20):908–912, 2010.
  * [13] Dan Gusfield.  Algorithms on Strings, Trees, and Sequences.  Cambridge University Press, 1997.
  * [14] Roman Kolpakov and Gregory Kucherov.  Searching for gapped palindromes.  Theor. Comput. Sci., 410(51):5365–5373, 2009.
  * [15] Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur.  Finding distinct subpalindromes online.  In PSC 2013, pages 63–69, 2013.
  * [16] Glenn Manacher.  A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string.  Journal of the ACM, 22:346–351, 1975.
  * [17] U. Manber and G. Myers.  Suffix arrays: A new method for on-line string searches.  SIAM Journal on Computing, 22(5):935–948, 1993.
  * [18] W. Matsubara, S. Inenaga, A. Ishino, A. Shinohara, T. Nakamura, and K. Hashimoto.  Efficient algorithms to compute compressed longest common substrings and compressed palindromes.  Theor. Comput. Sci., 410(8–10):900–913, 2009.
  * [19] Alexandre H. L. Porto and Valmir C. Barbosa.  Finding approximate palindromes in strings.  Pattern Recognition, 35:2581–2591, 2002.
  * [20] Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Longest lyndon substring after edit.  In CPM 2018, pages 19:1–19:10, 2018.
  * [21] Peter Weiner.  Linear pattern matching algorithms.  In 14th Annual Symposium on Switching and Automata Theory, pages 1–11, 1973.

##  Appendix A Appendix

###  A.1 Supplimental Figures

Figure 5: Example for $G^{\prime}_{k}=G_{k}\cup\\{u_{k}v_{k}u_{k},u_{k}\\}$,
where the extensions of $u_{k}v_{k}u_{k}$ and $u_{k}$ are longer than the
extensions of any maximal palindromes in $G_{k}$.