# FETNet: Feature Erasing and Transferring Network for Scene Text Removal

Guangtao Lyu  Kun Liu  Anna Zhu  Seiichi Uchida  Brian Kenji Iwana  School of
Computer Science and Artificial Intelligence, Wuhan University of Technology,
Wuhan, China  Human Interface Laboratory, Kyushu University, Fukuoka, Japan

###### Abstract

The scene text removal (STR) task aims to remove text regions and recover the
background smoothly in images for private information protection. Most
existing STR methods adopt encoder-decoder-based CNNs, with direct copies of
the features in the skip connections. However, the encoded features contain
both text texture and structure information. The insufficient utilization of
text features hampers the performance of background reconstruction in text
removal regions. To tackle these problems, we propose a novel Feature Erasing
and Transferring (FET) mechanism to reconfigure the encoded features for STR
in this paper. In FET, a Feature Erasing Module (FEM) is designed to erase
text features. An attention module is responsible for generating the feature
similarity guidance. The Feature Transferring Module (FTM) is introduced to
transfer the corresponding features in different layers based on the attention
guidance. With this mechanism, a one-stage, end-to-end trainable network
called FETNet is constructed for scene text removal. In addition, to
facilitate research on both scene text removal and segmentation tasks, we
introduce a novel dataset, Flickr-ST, with multi-category annotations. A
sufficient number of experiments and ablation studies are conducted on the
public datasets and Flickr-ST. Our proposed method achieves state-of-the-art
performance using most metrics, with remarkably higher quality scene text
removal results. The source code of our work is available at:
https://github.com/GuangtaoLyu/FETNet.

###### keywords:

Scene text removal , Text segmentation , One-stage , Self-attention

††journal: Pattern Recognition

##  1 Introduction

Natural scene images contain quite a lot of sensitive and private information,
such as names, addresses, and cellphone numbers. The developed OCR technics
[1] can extract those texts automatically and easily. To prevent the leakage
of private text information in images being used illegally, the scene text
removal [2] (STR) task has been proposed recently.

STR aims to automatically erase text regions and fill them with background
information in natural images. Recently, it has attracted significant
attention in the computer vision community due to its valuable applications in
privacy protection [3], visual translation [4], information reconstruction,
[5] and image editing [6].

Figure 1: Comparison of three kinds of STR frameworks and our proposed FETNet.
The one-stage based FETNet reconfigures features in skip-connections by using
text guidance. It takes the advantage of lightweight characteristics of the
one-stage STR model and the controllable characteristics of multi-stage STR
models.

Generally, the existing STR research can be classified into three categories:
one-stage, two-stage, and iterative-based methods, as displayed in Fig.1. One-
stage models [2, 7] are built on single encoder-decoder architectures with the
scene text image as input and directly outputting the text-removed result.
These models are usually lightweight and run fast. However, since they learn
both text detection and inpainting implicitly within a single network, the
text localization mechanism is weakened and makes the text erasing process
uncontrollable.

Two-stage STR methods adopt two or more encoder-decoders. They detect scene
text in the first step and the inpaint the detected region as a part of the
background in the second step [8, 9]. Alternatively, some two-stage methods
[10, 11] use a coarse-to-fine strategy to obtain coarse removal results in the
first stage and refine the removal performance in the second stage. Iterative-
based STR methods [12] also use text detection results as image inpainting
masks but perform multi-stage text erasure in an iterative way [13]. Those
methods are limited due to high reliability on text detection or coarse
removal results front-end. Compared to the one-stage approach, they are
inefficient and complex since all networks in different stages need to be
trained. The above analysis makes us rethink the STR task: is it possible to
adapt the architecture of the one-stage STR method since it is efficient,
meanwhile integrating text controlling process to overcome its drawback?

In this paper, we propose an encoder-decoder-based convolutional neural
network (CNN) called Feature Erasing and Transferring Network (FETNet), which
uses text segmentation as guidance and fuses it for background inpainting in a
single network. It belongs to the one-stage STR category. The encoder is
shared by text segmentation and background inpainting sub-tasks, and the
intermediate text segmentation result is reused in the decoder for text
removal, forcing the two sub-tasks to cooperate with each other and also
making the network training to be end-to-end.

The key idea of our FETNet is to utilize and process the different features
extracted in different CNN layers for STR. CNNs for text segmentation generate
different features in different layers [2] (i.e., low-level features in
shallow layers and high-level semantics in deep layers). In other words, the
features from the shared encoder contain spatial text information in shallow
layers and structural text information in deeper layers. Therefore, we design
the Feature Erasing and Transferring (FET) mechanism containing three modules
to process different information in each layer.

One key point is how to remove the various text information in the feature
spaces. We propose to use Feature Erasing Modules (FEM), which is the first
module in FET to remove text information. The STR task requires the text
regions to be covered by smooth background. Therefore, the second key point is
how to reconstruct the features in text regions and force the features to be
similar to text-surrounded background features. To solve it, the Attention
Modules (AM) and the Feature Transfer Modules (FTM) are sequentially used in
FET to obtain background feature similarity, and then transfer the similar
features. The FET mechanism is inserted between the encoder and decoder. We
expect that if text information is successfully erased and refilled by
background features, the output images after deconvolutions contain no text
and only background features [14, 15].

We conducted experiments on three datasets: the SCUT-EnsText [11], SCUT-Syn
[7], and Flickr-ST datasets [2]. Among them, the SCUT-EnsText dataset only
contains text-removed ground truth (GT) and text bounding boxes in images,
which may not be precise when recovering background textures around the text.
SCUT-Syn is a synthetic dataset with fake scene texts attached randomly in the
images, which cannot reflect the real scenes. The Flickr-ST dataset is a scene
text dataset [2] with pixel-level character segmentation and category labels.
To better utilize it for the STR task, we carefully erase each character and
inpainting its background for all 3,004 images. This dataset can also be used
for scene text detection, text recognition, text segmentation, etc.

The experimental results on the three datasets demonstrate that FETNet can
outperform previous state-of-the-art (SOTA) STR methods both qualitatively and
quantitatively. In addition, the proposed FET mechanism can plug in other two-
stage STR models for performance enhancement.

We summarize the contributions of this work as follows: (1) We propose a novel
FETNet which could remove scene text near-completely in images. It fully
utilizes CNN features through a designed Feature Erasing and Transferring
(FET) mechanism, which could erase and reconfigure text features through three
cascaded modules. This mechanism can be plugged into other two-stage STR
models for performance enhancement. (2) Our method is formulated in a one-
stage way and is trained in an end-to-end manner. It uses the intermediate
text segmentation features as guidance to control the feature erasing regions
in the decoder, which overcomes the drawback of one-stage STR methods and
realizes computationally efficient STR. (3) We introduce a novel Flickr-ST
dataset with multi-category careful annotations, which can benefit our work
and various scene text-related research. (4) Our FETNet achieves remarkable
quantitative and qualitative results on public synthetic and real scene
datasets. Ablation studies illustrate the proposed architecture and its
components play important roles in scene text removal.

##  2 Related Works

Scene Text Segmentation. Scene text segmentation aims to detect text at the
pixel level, i.e., extracting all text pixels of an image. Traditional methods
used thresholding-based [16] and edge detection-based [17] image processing
techniques for text segmentation on document images. However, they have
performed unsatisfactorily on scene text images due to the varying text
appearances and complex arrangements. Other approaches employed machine
learning algorithms, e.g., Markov Random Field (MRF) [18] and Conditional
random field (CRF) [19] to bipartite scene text images. But, they missed a lot
of text regions and detected false positives in complex backgrounds. Maximally
Stable External Regions (MSER) [20] applied both low and middle-level features
to extract text candidates with text-specific features to improve the
segmentation performance. But, it cannot be trained end-to-end and the
features were hand-crafted.

In recent years, deep learning-based text segmentation methods [2, 21, 22, 23]
were proposed and showed great superiority. Tang et al. [2] first proposed a
CNN-based coarse-to-fine pixel-level text segmentation model. SMANet [21]
adopted the encoder-decoder structure from PSPNet [24] and designed a multi-
scale attention module for text segmentation. TextRNet [22] was a text-
specific network that adapted to the unique text properties. Wang et al. [23]
proposed a mutually guided network to produce polygon-level mask and pixel-
level text mask in two branches and trained it semi-supervised.

Image Inpainting. Traditional image inpainting methods adopted diffusion
techniques [25] or patch-matching [26, 27], to fill in the missing regions by
neighborhood appearances or similarity patches. However, they are unable to
generate semantic content.

Deep learning-based inpainting approaches have recently been proposed, which
can generate meaningful content for filling in the missing regions. Context
Encoder [28] was a pioneering work, which utilized adversarial learning for
feature extraction and reconstruction. Afterward, many researchers [14, 29]
adopted attention mechanisms for generating the missing content, e.g., CAM
[14], KCA [29], etc.

In addition, several studies [30, 31] modified the regular convolution
operations to overcome the weakness of the vanilla convolution, e.g., partial
convolution [30], gated convolution [31], etc., for image inpainting.

Text Removal. Text removal studies can be classified into three categories:
one-stage, two-stage, and iterative-based methods.

One-stage STR methods treat the task as an image translation problem. For
instance, the well-known Pix2Pix [32] uses patch-GAN to learn the mapping from
input to output and can be applied for scene text removal. Similarly, Scene
Text Eraser (STE) [2] provided an STR baseline by constructing an encoder-
decoder architecture for erasing text in patches of images. But, only using
patches extracted from single-scaled sliding-windows lost the global context
information, failing for large text region removal. EnsNet [7] adopted cGAN
[32] with several designed loss functions and a novel lateral connection to
further enhance the STR performance.

Two-stage STR methods either adopt text detection-to-image inpainting flow or
coarse-to-fine pipeline. MTRNet [8] applied a text-awareness auxiliary mask
for a Pix2Pix-based model, which can focus on the task of text inpainting.
However, the implicit text region guidance may cause excessive erasure to non-
text regions. To overcome this problem, Tang et al. [33] adopted a pixel-level
mask of text stroke in the second stage to explicitly guide text inpainting.
EraseNet [11] used a coarse-to-fine procedure, decomposing scene text image to
text segmentation and coarse text removal heads in the coarse stage and then
refining the coarse results in the second stage. Differently, MTRNet++ [34]
and Cho et al. [10] constructed the refinement network inputting both the
coarse output and text mask from the first erasure stage. CTRNet [35]
developed a Local-global Content Modeling (LGCM) block to provide both low-
level and high-level contextual guidance, which could effectively enhance the
performance of texture restoration for complex backgrounds. Bian et al. [36]
proposed a cascaded GAN-based model by decoupling text removal into text
stroke detection and stroke removal.

Iterative STR models performed the erasure several times. PERT [13] used
balanced multi-stage erasure with several progressive erasing with explicit
text region guidance. PSSTRNet [37] proposed a new mask update module to
obtain increasingly accurate text masks and adopted an adaptive fusion
strategy to take full advantage of the results of different iterations. Our
method belonged to the one-stage category but utilized text segmentation
information to make the erasure controllability.

##  3 Proposed Method

###  3.1 Overall pipeline

Figure 2:  The overall architecture of FETNet.

As shown in Fig.2, the pipeline of our model consists of two parts: a
generator $G$ and a discriminator $D$. In $G$, one simple encoder-decoder
structure [15] is constructed, consisting of five residual convolutional
layers in the encoder and five residual convolutional (3$\times$3) layers in
the decoder, respectively. Following the resnet backbone architecture design,
the first to fifth layers of the encoder has kernel sizes of 7, 5, 3, 3, and 3
respectively. And the output feature maps of them have the size of
$1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16}$ of the input image,
respectively. In $D$, a four-layer CNN is designed to judge images as real or
fake globally and locally.

Since one-stage STR methods lack explicit text region guidance, we extend a
branch for text segmentation. In the CNN, the color, edge, and texture
features are extracted in shallow layers, and the deep layers contain more
structured semantic features (as shown in Fig.8). The text segmentation
results only contain the pixel-level text location but no texture. Therefore,
we only extract features from the last three layers in the encoder for text
segmentation. Three additional deconvolution layers are built to connect the
encoders as a U-Net structure, followed by a sigmoid function to obtain the
text confidence map $C_{t}$. $C_{t}$ is unsampled or downsampled to different
scales according to the different feature sizes.

The FET mechanism is designed and inserted between the encoder and decoder to
reconfigure the texture and structure features through text feature deletion
and background feature filling. It works in two different ways, i.e., texture
FET (FETt) and structure FET (FETs), in different layers. Since the encoder
jointly learns the structure and texture features of text and background,
directly concatenating those features [11] in skip-connections will involve
text information. This will cause unclean text removal results. Additionally,
the text in the shallow layers of CNNs has more local and texture information,
and they contain more abstract and structural information channel-wisely in
deep layers. Therefore, we reconfigure the features from the last two layers
in the encoder as structure features. Meanwhile, we reorganize the first
three-layer features as texture features. FETt and FETs are responsible for
these two types of features, respectively. Both are comprised of FEM, FTM, and
one attention module, reorganizing the features in different ways.

The structure features from the last layer and the texture features from the
first three layers are reorganized through the FETs and FETt, respectively.
Then, they are concatenated as the initial global features in the decoder.
Instead of using normal skip-connections to maintain background information,
we insert the FET into it. The features from each encoder layer go through FET
and are then concatenated with corresponding deconvolutional decoder features.
The final output is the text removal images. In the following subsections, we
present the details of the FETt and FETs and introduce the loss functions for
training this one-stage FETNet.

###  3.2 Texture FET mechanism

As shown in Fig.3(a), FETt contains a texture feature erasing module (FEMt), a
spatial attention module (SAM), and a texture feature transferring module
(FTMt). The FEMt is designed to remove text features from the shallow layers
with the guidance of $C_{t}$. In order to refill corresponding correct
background features in erased regions, a spatial attention operation is
implemented to get feature similarity in each position. Then, the FTMt is used
to transfer the correct background texture features to text regions. By using
the three modules successively, FETt can substitute the text features with
consistent background features.

The input to FEMt is aggregated features from different layers. We use multi-
scale aggregation [38] to aggregate texture features $f_{at}$ through resizing
and transforming the CNN feature maps
$f_{s}$$\in$${\rm\mathbb{R}}^{w_{s}\times h_{s}\times c_{s}}$ from three
shallow layers to the same size and concatenating them accordingly. The
aggregated texture features $f_{at}$ are then input to FEMt to get text erased
feature $f_{e}$ as in Eq. (1), where $\odot$ refers to Hadamard product.

$f_{e}=(1-C_{t})\odot f_{at}.$ (1)

In SAM, three soft gating convolutions [31] expressed in Eq. (2) are used to
fill the erased feature with rough features which are dynamically selected
from other channels and spatial locations:

$\displaystyle f_{g}=W_{g}\ast[f_{e},C_{t}],$ (2) $\displaystyle
f_{d}=W_{f}\ast[f_{e},C_{t}],$
$\displaystyle\bar{f}_{e}=\phi(f_{d})\odot\sigma(f_{g}),$

where $\ast$ represents the convolution operation and [$\cdot$,$\cdot$]
denotes concatenation. $f_{g}$$\in$${\rm\mathbb{R}}^{w_{e}\times h_{e}\times
1}$ is the gating features and becomes gating values between zeros and ones
after sigmoid function $\sigma$. $f_{d}$$\in$${\rm\mathbb{R}}^{w_{e}\times
h_{e}\times c_{e}}$ is transformed features fusing text information. $\phi$
can be any activation function. We select the ReLU function for our method.
$\bar{f}_{e}$ is the coarse filling features. $W_{g}$ and $W_{f}$ are two
different trainable convolutional filters.

Figure 3:  The texture FET mechanism (a) and the structure FET mechanism (b).

Directly using $\bar{f_{e}}$ will generate very blur results. Therefore, it is
only represented as coarse features. The spatial attention searches for
possible textures in the background and uses them to replace the textures in
regions with a high probability of being text. We measure the cosine
similarity between features in each pair of locations as Eq.(3).

$\bar{S}_{(x_{i},y_{i}),(x_{j},y_{j})}=\left\langle\frac{\bar{f_{e}}(x_{i},y_{i})}{\|\bar{f_{e}}(x_{i},y_{i})\|},\frac{\bar{f_{e}}(x_{j},y_{j})}{\|\bar{f_{e}}(x_{j},y_{j})\|}\right\rangle.$
(3)

Therefore, we could get a smooth attention map
$S$$\in$${\rm\mathbb{R}}^{w_{e}h_{e}\times w_{e}h_{e}}$. However, the
attention of high probability text position may also focus on other text
positions. Our goal is to transfer background features onto only the erased
text regions, so spatial background concurrency probability should also be
considered. The background concurrency attention
$S_{t}$$\in$${\rm\mathbb{R}}^{w_{e}h_{e}\times w_{e}h_{e}}$ is written as Eq.
(4), where $\otimes$ is the Kronecker product.

$S_{t}=(1-C_{t})\otimes(1-C_{t})^{T}\odot S.$ (4)

$S_{t}$ is reshaped to $w_{e}$$\times$ $h_{e}$$\times$$w_{e}$$h_{e}$, and
Softmax function is performed on each channel respectively. The output of
($i\times w_{e}$+$j$)th channel denoting as Softmaxc($S_{t}$)i,j represents
the global background attention weights for position ($i$, $j$).

Then, FTMt calculates the transferred texture features $f_{t}$($i$,$j$) for
each position ($i$, $j$) as Eq. (5). We expect only background features to be
transferred to erased text regions. The features of the other background
regions should not be changed. So, we update the transferred texture features
considering the text probability as in Eq. (6).

$f_{t}(i,j)=\sum(\mathrm{Softmax}_{c}(S_{t})_{i,j}\odot f_{e}).$ (5)
$f_{t}^{t}=C_{t}\odot f_{t}+f_{e}.$ (6)

For the layer-wise texture features $f_{s}$ transferring in skip-connections,
we do not recompute spatial attention but share the rescaled attention weights
Softmaxc($S_{t}$) as the similarity guidance. Features in each of the first
three layers go through FEMt to get $f_{e}$, and then FTMt to get $f_{t}^{t}$.

###  3.3 Structure FET mechanism

Similarly, FETs contains a FEMs, FTMs, and a channel attention module (CAM).
The purpose of this mechanism is to enhance the structure features of the
background but suppress the structure features of texts. Since features in
each channel of deep layers contain more global information, we follow the
squeeze and excitation operation [39] to get the background attention of each
channel. The features flowing in FETs are displayed in Fig.3(b).

For features $f_{s}$ in layer $s_{th}$ $\in$[4,5], FEMs first erases the text
features by element-wise multiplication with 1-$C_{t}$ as Eq. (1). Then,
squeeze and excitation operation is employed for feature $f_{e}$, to get the
channel attention $S_{c}$$\in$${\rm\mathbb{R}}^{1\times 1\times c_{s}}$ in
CAM, as written in Eq. (7). $F_{sq}$ is to squeeze features, which is achieved
by using global average pooling to generate channel-wise statistics. $F_{ex}$
is used to excite channel attention by forming two fully-connected layers and
a sigmoid function. The scores in $S_{c}$ express the importance of background
structure features in the corresponding channels.

Finally, FTMs implements channel-wise multiplication between the channel
attention score $S_{s}$ and the original features $f_{s}$ to output the
transferred structure features $f_{t}^{s}$.

$S_{c}=F_{ex}(F_{sq}((f_{e})))$ (7) $f_{t}^{s}=S_{c}\odot f_{s}.$ (8)

###  3.4 Loss functions

We introduce several loss functions for FETNet learning, including pixel
reconstruction loss, perceptual loss, style loss, and relativistic average LS
adversarial loss. Given the input scene text image $I_{i}$, text-removed GT
$I_{gt}$ and the binary text GT mask $M_{gt}$ (0 for non-text regions and 1
for text regions in $M_{gt}$), the STR output from FETNet is denoted as
$I_{o}$ and text segmentation results as $M_{o}$. $M_{o}$ is obtained by
thresholding on $C_{t}$.

Pixel Reconstruction Loss. First, we impose a reconstruction constraint that
forces both backgrounds and removed text regions to approach the real GT
$I_{gt}$, using a standard autoencoder L1 loss:

$L_{rec}=||(1-M_{gt})\odot(I_{o}-I_{gt})||_{1}+\lambda_{t}||M_{gt}\odot(I_{o}-I_{gt})||_{1},$
(9)

where $\lambda_{t}$ is set to 5, which emphasizes the learning importance of
text removed regions.

Perceptual Loss. To capture the high-level semantics and simulate human
perception of images quality, we utilize the perceptual loss [40]:

$\begin{split}L_{p}=\sum_{i}\frac{1}{N_{i}}||\Phi_{i}(I_{o})-\Phi_{i}(I_{gt})||_{1}+\sum_{i}\frac{1}{N_{i}}||\Phi_{i}(I_{c})-\Phi_{i}(I_{gt})||_{1},\end{split}$
(10) $I_{c}=I_{i}\odot(1-M_{gt})+I_{o}\odot M_{gt},$ (11)

where $\Phi_{i}$ is the activation map of the $i$-th layer of the VGG-16
backbone. $I_{c}$ is the composted image with background of original input
$I_{i}$ and text removed regions of $I_{o}$.

Style Loss. We compute the style loss [41] as in Eq.(12), where
$G_{i}$($\Phi$) is the Gram matrix constructed from the selected activation
maps.

$\begin{split}L_{s}=||G_{i}(\Phi(I_{o}))-G_{i}(\Phi(I_{gt}))||_{1}+||G_{i}(\Phi(I_{o}))-G_{i}(\Phi(I_{gt}))||_{1}.\end{split}$
(12)

Segmentation Loss. For learning of text segmentation module, we use dice loss
[42] as Eq. (13), which considers the contour similarity between the
prediction results in $M_{o}$ and GT $M_{gt}$.

$L_{seg}=1-\frac{2\sum_{x,y}(M_{o}(x,y)\times
M_{gt}(x,y))}{\sum_{x,y}(M_{o}(x,y)^{2}+M_{gt}(x,y)^{2})}.$ (13)

Adversarial Loss. We utilize the global and local discriminators [31] for
perception enhancement. The adversarial loss of $G$ and $D$ is defined as
Eq.(14) and Eq.(15), respectively.

$L_{G}^{adv}=-\mathbb{E}[\mathrm{log}D(G(I_{i}))],$ (14)
$L_{D}^{adv}=\mathbb{E}[\mathrm{log}D(I_{gt})]+\mathbb{E}[\mathrm{log}(1-D(G(I_{i})))].$
(15)

The total loss for training the generator in FETNet is the weighted
combination of the losses mentioned above:

$\begin{split}L_{total}=L_{rec}+\lambda_{s}L_{s}+\lambda_{p}L_{p}+\lambda_{m}L_{seg}+\lambda_{g}L_{G}^{adv}.\end{split}$
(16)

In experiments, we set $\lambda_{s}$, $\lambda_{p}$, $\lambda_{m}$ and
$\lambda_{g}$ to 60, 0.05, 1.5, 0.05 respectively, basing on the their effect
for training the model [30, 7].

##  4 Datasets

Flickr-ST. The Flickr-ST dataset is a real-world dataset [2] including 3,004
images with 2,204 images for training and 800 images for testing. The scene
text in Flickr-ST has arbitrary orientations and shapes. Some examples are
shown in Fig.4(a). It provides five types of annotations, text removed images
(in Fig.4(b)), pixel-level text masks (in Fig.4(c)), character instance
segmentation labels, category labels, and character-level bounding box
labels(in Fig.4(d) and (e)). The word-level scene text regions can be
calculated implicitly from those labels. To the best of our knowledge, Flickr-
ST is the only dataset with such comprehensive annotations for scene text
related tasks.

The character-level segmentation labels, bounding box labels, and category
labels are stored in .png and .xml file formation for each image as shown in
Fig.4(d) and (e) respectively. In the .png file, each character in the
corresponding original scene text image is annotated with distinguished color.
Each line in the .xml file contains nine numbers and one string. The numbers
represent the RGB value and bounding box coordinates of the labeled character
in the .png file. The string denotes the character class. Additionally, the
blank line interval represents the end of a word-level text. Thus, it is very
simple to obtain the GT of word-level regions.

There are some non-readable or too-small characters that are very difficult to
label. We consider them as do-not-care characters. Therefore, they are labeled
by quadrilateral regions in .png file and have no corresponding character
class in .xml file.

Text-removed images are generated from original images with scene text erased
and filled with a visually plausible background to maintain the consistency of
erased text regions and their surrounding texture. All the filling and erasing
operations are constructed using Adobe Photoshop. We mainly use Spot Heading
Brush and Pattern Stamp functions. Then, we merge the text-removed image and
the corresponding text image with the text masks to modify the background area
as little as possible.

Pixel-level text mask is a binary image to distinguish text and non-text. We
ignore some text effects like shadow and decoration during labeling.

Figure 4: Changeling examples and the corresponding annotations of the Flickr-
ST dataset. (a) text image (b) text-removed image (c) pixel-level text mask
(d) character-wise pixel-level mask (e) part of character-wise bounding
polygons

SCUT-Syn. This synthetic dataset only includes English text instances, with
8,000 images for training and 800 images for testing. The details for
generating and using these synthetic text images can be found in [43].

SCUT-EnsText. It contains 2,749 training images and 813 test images which are
collected in real scenes with diverse text included. More descriptions about
this dataset refer to the work [11].

Evaluation Metrics. A text detector CRAFT [44] is employed to detect text on
the output STR images by measuring the precision, recall, and F-score. The
lower their values, the better text removal performance. Six image-level
evaluation metrics are also adopted for measurement of the generated STR
images with GT images, i.e., Peak Signal to Noise Ratio (PSNR), Mean Square
Error (MSE), Mean Structural Similarity (MSSIM), Average Gray-level Error
(AGE), percentage of Error Pixels (pEPs), and percentage of Clustered Error
Pixels (pCEPS) [7]. A higher MSSIM and PSNR, and a lower AGE, pEPs, pCEPS, and
MSE indicate better results.

##  5 Experiments and Results

###  5.1 Implementation details

We train FETNet on the training sets of SCUT-EnsText, SCUT-Syn, and Flickr-ST
and evaluate them on their corresponding testing sets. The masks are generated
by subtracting the input images and the corresponding STR GT, i.e., text
removal images. We follow [11] to apply data augmentation during training. The
model is optimized using the Adam algorithm. The initial learning rate of the
generator is set to 0.001, and the discriminator is 0.002. Following the
training procedures of GAN, we alternately train the generator and
discriminator for 500 epochs in a single NVIDIA GPU with a batch size of 6 and
input image size of 256$\times$256.

###  5.2 Ablation study

####  5.2.1 The effect of different components in FETNet

Table 1: Ablation study results of different modules effect on SCUT-Syn.

Method | PSNR $\uparrow$ | MSSIM $\uparrow$ | MSE $\downarrow$ | AGE $\downarrow$ | pEPs $\downarrow$ | pCEPs $\downarrow$
---|---|---|---|---|---|---
\- FEM | 34.23 | 96.24 | 0.0010 | 3.0373 | 0.0175 | 0.0074
\- FTM | 37.07 | 97.29 | 0.0004 | 2.3667 | 0.0063 | 0.0014
\- Simlarity | 37.95 | 96.92 | 0.0002 | 1.3293 | 0.0067 | 0.0011
\+ Output Mask | 36.21 | 96.62 | 0.0006 | 2.5429 | 0.0107 | 0.0038
Full model | 39.14 | 97.97 | 0.0002 | 1.2608 | 0.0046 | 0.0008

In this section, we verify the effect of different components of FETNet on the
SCUT-Syn dataset. In total, we set five comparison experiments as follows:
removing FEM ($-$FEM), removing FTM ($-$FTM), removing the similarity
computation of FETt mechanism ($-$Similarity), using thresholded text mask
instead of text probability (+output mask), and full model. All experiments
are trained exactly the same. The qualitative results are visualized in Fig.5.
Since the SCUT-Syn dataset has no accurate text localization GT, we only
provide the quantitative results of the six image-level evaluation metrics as
in Tab.1.

We observe that the performance decreases the most if removing all the FEM
parts in FETNet, which demonstrates the importance of the FEM module in
FETNet. It assists in erasing text features and avoids inducing them again
during background reconstruction. Without FEM, the removal results in Fig.5(b)
contains some original text color in the erased text regions. The same problem
exists for removing the FTM module in FETNet. When we remove the similarity
module, there are a lot of small bits of text left over in the output. The
text regions on complex background are not fixed well, as displayed on the
dark green circle region in Fig.5(d).

Using the 0/1 mask instead of the text confidence map, the model becomes a
two-stage network, which first generates the mask and reconstructs the
background through image inpainting. While using a text confidence map in
FETNet makes the tasks nonindependent. The text removal-related losses can
also be backpropagated to update the parameters in the text segmentation
module. That results in more accurate text segmentation and better text
removal results, as reflected in Fig.5(f). The above results illustrate the
effectiveness of each module in FETNet.

Figure 5: Ablation study on different models. (a) Input image. (b)(c)(d)(e)(f)
show the STR results by removing FEM, removing FTM, removing Similarity, using
generated mask instead of a text confidence map, and the full model. (g) is
the STR GT.

####  5.2.2 The effect of various FET structures

For evaluating the influence of the FETt and FETs, we build five models with
different FET structures as follows: removing all FETt ($-$FETt), removing all
FETs($-$FETs), only using FETt in all the layers (all FETt), only using FETs
in all the layers (all FETs), and our proposed model (Full model). The
quantitative results are shown in Tab.2.

We can observe that the performance decreases more when we remove all the
structure FET or the texture FET in the models compared with the performance
of models using all FETt or FETs structures. It demonstrates the importance of
both structure and texture FET in our method. On the other side, the model
without FETt gets the worst result, but the model with all FETt gets the
result only second to that of the full model. It illustrates that texture FET
is more important than structural FET. Since there are convolution parameters
in FETt, the model size with all FETt is bigger than others. However, the FETs
module has no parameters, so the -FETt model has nearly the same size as all
FETs model. About the inferring time, FETt module costs more time than FETs as
the similarity is computed spatially in FETt. Considering the performance,
model size, and speed comprehensively, our proposed full model has a good
tradeoff among all these factors.

Table 2: Performance of different structured models on SCUT-EnsText and SCUT-
Syn.

dataset | SCUT-EnsText | SCUT-Syn |  |
---|---|---|---|---
Method | PSNR $\uparrow$ | MSSIM $\uparrow$ | MSE $\downarrow$ | AGE $\downarrow$ | pEPs $\downarrow$ | pCEPs $\downarrow$ | PSNR $\uparrow$ | MSSIM $\uparrow$ | MSE $\downarrow$ | AGE $\downarrow$ | pEPs $\downarrow$ | pCEPs $\downarrow$ | Parameters $\downarrow$ | Infer. Time $\downarrow$
\- FETt | 32.47 | 95.39 | 0.0017 | 2.0661 | 0.0187 | 0.0095 | 37.10 | 96.57 | 0.0003 | 1.4309 | 0.0083 | 0.0016 | 7.05M | 2ms
\- FETs | 32.53 | 95.49 | 0.0017 | 2.0569 | 0.0185 | 0.0095 | 37.15 | 96.57 | 0.0003 | 1.4157 | 0.0086 | 0.0016 | 8.49M | 4.26ms
all FETs | 33.72 | 96.13 | 0.0016 | 1.9136 | 0.0173 | 0.0080 | 37.23 | 96.65 | 0.0003 | 1.4138 | 0.0080 | 0.0015 | 7.06M | 3.39ms
all FETt | 33.81 | 96.21 | 0.0016 | 1.8949 | 0.0171 | 0.0077 | 37.52 | 96.73 | 0.0003 | 1.3931 | 0.0077 | 0.0014 | 8.72M | 4.73ms
Full model | 34.53 | 97.01 | 0.0013 | 1.7539 | 0.0137 | 0.0080 | 39.14 | 97.97 | 0.0002 | 1.2608 | 0.0046 | 0.0008 | 8.53M | 4.62ms

###  5.3 Comparison with state-of-the-art approaches

We compare our FETNet with the baseline fully convolutional network (FCN)
[45], three SOTA one-stage methods: Pix2pix [32], STE [2], and EnsNet [7], and
the two SOTA two-stage approach EraseNet [11] and MTRNet++ [34] on SCUT-
EnsText, SCUT-Syn dataset, and Flickr-ST dataset. The FCN-based method is
similar to STE but with the input of full image instead of image patches. It
is compared as a baseline model. We retrain all the models with the original
setting as officially reported but set the input image to 256$\times$256\.
Especially, Precision (P), Recall (R), and F-score (F) are measured on
rescaled 512$\times$512 images by text detector CRAFT [44], since this text
detector is very sensitive to small text and cannot detect text in very small-
sized images.

Table 3: Comparison with SOTA methods and proposed method on SCUT-EnsText and
Flickr-ST. R: Recall; P: Precision; F: F-score.

Dateset | Method | Image-level Evaluation | Detection-Eval(%)
---|---|---|---
PSNR $\uparrow$ | MSSIM $\uparrow$ | MSE $\downarrow$ | AGE $\downarrow$ | pEPs $\downarrow$ | pCEPs $\downarrow$ | P $\downarrow$ | R $\downarrow$ | F $\downarrow$
SCUT-EnsText | Original Images | - | - | - | - | - | - | 79.8 | 69.7 | 74.4
FCN(baseline) | 18.16 | 47.24 | 0.0211 | 20.9734 | 0.3115 | 0.1338 | 1.33 | 31.37 | 2.55
Pix2pix[32] | 26.75 | 88.93 | 0.0033 | 5.842 | 0.048 | 0.0172 | 71.3 | 36.5 | 48.3
STE[2] | 20.60 | 84.11 | 0.0233 | 14.4795 | 0.1304 | 0.0868 | 52.3 | 14.1 | 22.2
EnsNet[7] | 29.54 | 92.74 | 0.0024 | 4.1600 | 0.2121 | 0.0544 | 68.7 | 32.8 | 44.4
MTRNet++[34] | 27.34 | 95.20 | 0.0033 | 8.9480 | 0.0953 | 0.0619 | 56.1 | 3.6 | 6.8
EraseNet(official report)[11] | 32.30 | 95.42 | 0.0015 | 3.0174 | 0.0160 | 0.0090 | 53.2 | 4.6 | 8.5
EraseNet(retrained) | 31.72 | 91.72 | 0.0015 | 2.5476 | 0.0724 | 0.0508 | 65.6 | 12.9 | 21.5
| FETNet (Ours) | 34.53 | 97.01 | 0.0013 | 1.7539 | 0.0137 | 0.0080 | 51.3 | 5.8 | 10.5
Flickr-ST | Original Images | - | - | - | - | - | - | 84.4 | 73.8 | 78.8
FCN(baseline)[45] | 17.22 | 43.22 | 0.0237 | 22.8852 | 0.3399 | 0.1430 | 2.18 | 38.37 | 4.12
Pix2pix[32] | 24.95 | 86.81 | 0.0059 | 7.0942 | 0.0630 | 0.0316 | 45.7 | 12.8 | 20.0
STE[2] | 25.28 | 88.57 | 0.0055 | 7.6071 | 0.0569 | 0.0277 | 54.0 | 7.9 | 13.8
MTRNet++[34] | 26.19 | 94.37 | 0.0042 | 10.2778 | 0.1199 | 0.0777 | 71.2 | 3.3 | 6.4
EnsNet[7] | 29.14 | 92.21 | 0.0034 | 4.1160 | 0.0311 | 0.0158 | 70.9 | 17.2 | 27.7
EraseNet[11] | 27.87 | 89.70 | 0.0035 | 5.4443 | 0.0311 | 0.0140 | 62.3 | 5.7 | 10.4
| FETNet (Ours) | 33.61 | 95.99 | 0.0022 | 1.9542 | 0.0190 | 0.0108 | 59.0 | 2.6 | 5.0

Qualitative Comparison. Qualitative comparison results are displayed in Fig.6
and 7. Compared with one-stage STR methods, we can see that STE causes a lot
of visual artifacts such as color discrepancy, blurriness, etc. Some non-text
regions are also erased, reflecting the uncontrollability of its text removal
process. On the contrary, our proposed method adopts an attention mechanism to
reconfigure text features and utilizes text segmentation as guidance.
Therefore, it can overcome these drawbacks.

Compared with other SOTA approaches on SCUT-EnsText, our method is able to
remove most scene text and recover the background well. Particularly, it
performs better for removing small numbers and cursive text. We can see that
other methods fail to remove small text in the first and second columns of
Fig.6, but we can correctly segment those text and remove them. The STR
results of our model have significantly fewer noticeable inconsistencies and
artifacts, such as color discrepancy and blurriness, as shown in the 5th and
6th columns in Fig.6. This indicates our model can generate more semantically
plausible and elegant results.

The same results can be observed on the Flickr-ST dataset in Fig.7. The scene
text in the Flickr-ST dataset appears to be more complicated. For instance,
illumination reflection in the image of the first column, text-like background
objects in the second column, and more complex background textures in the
third and fourth columns. Compared to other SOTA approaches, our proposed
FETNet can erase those text clearer and also recover the complex background
information better.

Figure 6: Comparison results with other SOTA methods on the SCUT-EnsText and
SCUT-Syn datasets. Figure 7: Comparison results with other SOTA methods on the
Flickr-ST dataset.

Quantitative Comparison. Quantitative comparison results of real scene data
and synthetic data are given in Tab.3 and Tab.4, respectively. We can see that
the proposed FETNet surpasses the existing SOTA methods on most evaluation
metrics on the three datasets. Additionally, FETNet is a one-stage,
lightweight, and end-to-end network, which only has 8.53M trainable parameters
and an inference speed of 4.62 ms per image, as indicated in Tab.4. We can see
that the one-stage STR methods run faster than the two-stage ones. They also
have much smaller model sizes. The one-stage model, STE [2], generates many
1024 channel feature maps and inputs small patches of images iteratively. So,
its size is large and has a high computational cost. With the guidance of the
text region mask and the coarse STR results, the two-stage models are able to
achieve better STR performance both on inpainting and text detection metrics,
but their inferring time is slower, i.e. MTRNet++. Our model absorbs the
advantages of one-stage and two-stage models. The overall comparison results
demonstrate the superiority of FETNet for the STR task.

Overall, the qualitative and quantitative results indicate that our method can
produce excellent text removal and background restoration results on both real
scenes and synthetic text images.

Table 4: Comparison with SOTA methods and proposed method on SCUT-Syn.

Method | Category | PSNR $\uparrow$ | MSSIM $\uparrow$ | MSE $\downarrow$ | AGE $\downarrow$ | pEPs $\downarrow$ | pCEPs $\downarrow$ | Parameters$\downarrow$ | Infer. Time$\downarrow$
---|---|---|---|---|---|---|---|---|---
FCN(Baseline)[45] | one-stage | 18.98 | 53.27 | 0.0196 | 19.3350 | 0.2777 | 0.1225 | 18.13M | 2.23ms
Pix2pix | one-stage | 25.16 | 87.63 | 0.0038 | 6.8725 | 0.0664 | 0.0300 | 54.4M | 2.96ms
STE | one-stage | 24.02 | 89.49 | 0.0123 | 10.0018 | 0.0728 | 0.0464 | 89.16M | 18.45ms
EnsNet | one-stage | 37.36 | 96.44 | 0.0021 | 1.73 | 0.0069 | 0.0020 | 12.4M | 5.10ms
MTRNet++ (official report) | two-stage | 34.55 | 98.45 | 0.0004 | - | - | - | 18.7M | -
MTRNet++ (retrained) | two-stage | 34.28 | 96.78 | 0.0004 | 2.6337 | 0.0059 | 0.0008 | 18.7M | 30.2ms
EraseNet(official report) | two-stage | 38.32 | 97.67 | 0.0002 | 1.5982 | 0.0048 | 0.0004 | 19.74M | 8.67ms
EraseNet(retrained) | two-stage | 37.43 | 97.57 | 0.0003 | 1.5615 | 0.0264 | 0.0140 | 19.74M | 8.67ms
FETNet(Ours) | one-stage | 39.14 | 97.97 | 0.0002 | 1.2608 | 0.0046 | 0.0008 | 8.53M | 4.62ms

###  5.4 Inserting FET for two-stage network

The FET mechanism can be used as a drop-in module inserted in the skip-
connection structure for other two-stage STR networks, which utilize text
masks and are built on encoder-decoder architecture. We next investigate the
effect of inserting FET in the coarse detection stage of EraseNet. The FETt
blocks are inserted in the first three CNN layers and FETt in the last two
layers as our FETNet design. Both the original EraseNet and FET-inserted one
are trained in the same condition on the SCUT-Syn dataset.

The test results are given in Tab.5. By inserting our FET blocks, the EraseNet
can get higher PSNR, MSSIM, and lower MSE, AGE, pEPs, pCEPs. The better
performance demonstrates the effectiveness of our proposed FET mechanism.

Table 5: The performance of inserting FET to EraseNet on SCUT-Syn.

Method y | PSNR $\uparrow$ | MSSIM $\uparrow$ | MSE $\downarrow$ | AGE $\downarrow$ | pEPs $\downarrow$ | pCEPs $\downarrow$
---|---|---|---|---|---|---
EraseNet | 37.43 | 97.57 | 0.0003 | 1.5615 | 0.0264 | 0.0140
FET+EraseNet | 38.15 | 98.01 | 0.0002 | 1.0865 | 0.0124 | 0.0060

###  5.5 Interpretability

To further understand the working mechanism of FET, we observe the original
CNN features in the second layer and fourth layer of the encoder and their
corresponding output features after using FETt and FETs respectively. The
visualization results of example texture and structure features are displayed
in Fig.8(b) and (c) by using the input image in (a). We can see that
highlighted features in text regions are removed and can be refilled in by the
surrounding background features, as displayed in Fig.8(b), which proves the
effectiveness of our proposed FETt.

FETs revises features based on channel attention. If the original channel
feature contains text structure, it is decreased after using FETs as shown in
the first two columns of Fig.8(c). While if the original channel contains
important background structures, the corresponding channel features output
from FETs are maintained or enhanced, as shown in the last two columns of
Fig.8(c). These observations illustrate that FETs is able to select background
structure but suppress text structure features channel-wisely.

Figure 8: Visualizations of features revised by the FET mechanism. (a) lists
the input image, generated mask, STR results, and GT. (b) Features input(1st
row) and output(2nd row) of FETt. (c) Features input(1st row) and output(2nd
row) of FETs.

##  6 Limitation

Even though our method achieves great performance on scene text removal tasks,
it still has some limitations. If the text blends in the background, as shown
in the top row of Fig.9, where the central characters “R” and “G” are formed
by the background textures, it will be difficult to distinguish them between
text and non-text. The incorrect segmented text map results in limited text
removal performance. When the text has complex text effects, e.g., shadows,
the removal results are also unsatisfactory. For failure example in the bottom
of Fig.9, the large-size text is stereoscopic and has shadows, making the
incorrect segmentation of text. The components of segmented text are very big.
However, filling in the large holes in the image inpainting task is very
challenging [29]. Therefore, our model still has room for improvement in more
accurate artistic text extraction and considering using image inpainting
strategies for filling in large holes.

Figure 9: Some failure cases of our method for STR.

##  7 Conclusion

This paper presents a lightweight one-stage network, called FETNet, for scene
text removal in images. It is based on an encoder-decoder structure with
inserted FET blocks. The FET block contains three modules: FEM, SAM/CAM, and
FTM, for text feature erasing, background feature exploring, and transferring
correct background features to text regions, respectively, with the text
probability guidance generated from the text segmentation branch. Therefore,
the decoder can generate better text removal results using these reconfigured
features. The experiments show that our FETNet significantly outperforms the
existing state-of-the-art STR methods. Furthermore, we show that the FET
mechanism can be inserted into other two-stage methods for performance
enhancement. Additionally, we modified the Flickr-ST dataset, which can
benefit multiple STR-related researches, e.g., Scene text detection,
segmentation, recognition, and removal. In the future, we will fuse the
knowledge of natural language processing into our work to better remove scene
text with private information in the images.

##  8 Acknowledgement

This work is supported by the Open Project Program of the National Laboratory
of Pattern Recognition (NLPR) (No.202200049).

## References

  * [1] N. Nguyen, T. Nguyen, V. Tran, T. Tran, T. Ngo, T. Nguyen, M. Hoai, Dictionary-guided scene text recognition, in: CVPR, 2021.
  * [2] T. Nakamura, A. Zhu, K. Yanai, S. Uchida, Scene text eraser, in: ICDAR, 2017.
  * [3] K. Inai, M. Palsson, V. Frinken, Y. Feng, S. Uchida, Selective concealment of characters for privacy protection, in: ICPR, 2014.
  * [4] A. Singh, G. Pang, M. Toh, J. Huang, T. Hassner, Textocr: Towards large-scale end-to-end reasoning for arbitrary-shaped scene text, in: CVPR, 2021.
  * [5] S. Liu, L. Jin, F. Miao, Textual restoration of occluded tibetan document pages based on side-enhanced u-net, Journal of Electronic Imaging 29 (6) (2020).
  * [6] Q. Yang, H. Jin, J. Huang, W. Lin, Swaptext: Image based texts transfer in scenes, in: CVPR, 2020.
  * [7] S. Zhang, Y. Liu, L. Jin, Y. Huang, S. Lai, Ensnet: Ensconce text in the wild, in: AAAI, 2019.
  * [8] O. Tursun, Z. Rui, S. Denman, S. Sridharan, C. Fookes, Mtrnet: A generic scene text eraser, in: ICDAR, 2019.
  * [9] J. Zdenek, H. Nakayama, Erasing scene text with weak supervision, in: WACV, 2020\.
  * [10] J. Cho, S. Yun, D. Han, B. Heo, J. Y. Choi, Detecting and removing text in the wild, IEEE Access 9 (2021) 123313–123323.
  * [11] C. Liu, Y. Liu, L. Jin, S. Zhang, Y. Wang, Erasenet: End-to-end text removal in the wild, IEEE Transactions on Image Processing 29 (2020) 8760–8775.
  * [12] Z. Tang, T. Miyazaki, Y. Sugaya, S. Omachi, Stroke-based scene text erasing using synthetic data, CoRR abs/2104.11493 (2021).
  * [13] J. Li, F. He, L. Zhang, B. Du, D. Tao, Progressive reconstruction of visual structure for image inpainting, in: ICCV, 2019.
  * [14] J. Yu, Z. Lin, J. Yang, X. Shen, X. Lu, T. S. Huang, Generative image inpainting with contextual attention, in: CVPR, 2018.
  * [15] H. Liu, B. Jiang, Y. Song, W. Huang, C. Yang, Rethinking image inpainting via a mutual encoder-decoder with feature equalizations, in: ECCV, 2020.
  * [16] N. Nobile, C. Y. Suen, Text Segmentation for Document Recognition, Springer London, London, 2014, pp. 257–290.
  * [17] X. Liu, J. Samarabandu, Multiscale edge-based text extraction from complex images, in: ICME, 2013.
  * [18] Y. Wang, C. Shi, B. Xiao, C. Wang, MRF based text binarization in complex images using stroke feature, in: ICDAR, 2015.
  * [19] M. Li, R. Bai, R. Wang, R. Xiao, Conditional random field for text segmentation from images with complex background, Pattern Recognition Letters 31 (14) (2010) 2295–2308.
  * [20] S. Tian, S. Lu, B. Su, C. L. Tan, Scene text segmentation with multi-level maximally stable extremal regions, in: ICPR, 2014.
  * [21] S. Bonechi, M. Bianchini, F. Scarselli, P. Andreini, Weak supervision for generating pixel level annotations in scene text segmentation, Pattern Recognition Letters 138 (2020) 1–7.
  * [22] X. Xu, Z. Zhang, Z. Wang, B. Price, H. Shi, Rethinking text segmentation: A novel dataset and a text-specific refinement approach, in: CVPR, 2021.
  * [23] C. Wang, S. Zhao, L. Zhu, K. Luo, Y. Guo, J. Wang, S. Liu, Semi-supervised pixel-level scene text segmentation by mutually guided network, IEEE Transactions on Image Processing 30 (2021) 8212–8221.
  * [24] H. Zhao, J. Shi, X. Qi, X. Wang, J. Jia, Pyramid scene parsing network, in: CVPR, 2017.
  * [25] C. Ballester, M. Bertalmio, V. Caselles, G. Sapiro, J. Verdera, Filling-in by joint interpolation of vector fields and gray levels, IEEE Transactions on Image Processing 10 (8) (2001) 1200–1211.
  * [26] A. Criminisi, P. Perez, K. Toyama, Region filling and object removal by exemplar-based image inpainting, IEEE Transactions on Image Processing 13 (9) (2004) 1200–1212.
  * [27] C. Barnes, Patchmatch:a randomized correspon-dence algorithm for structural image editing, 2009.
  * [28] D. Pathak, P. Krahenbuhl, J. Donahue, T. Darrell, A. A. Efros, Context encoders: Feature learning by inpainting, in: CVPR, 2016.
  * [29] J. Li, N. Wang, L. Zhang, B. Du, D. Tao, Recurrent feature reasoning for image inpainting, in: CVPR, 2020.
  * [30] G. Liu, F. A. Reda, K. J. Shih, T. C. Wang, A. Tao, B. Catanzaro, Image inpainting for irregular holes using partial convolutions, in: ECCV, 2018.
  * [31] J. Yu, Z. Lin, J. Yang, X. Shen, T. Huang, Free-form image inpainting with gated convolution, in: ICCV, 2019.
  * [32] P. Isola, J. Y. Zhu, T. Zhou, A. A. Efros, Image-to-image translation with conditional adversarial networks, in: CVPR, 2017.
  * [33] Z. Tang, T. Miyazaki, Y. Sugaya, S. Omachi, Stroke-based scene text erasing using synthetic data for training, IEEE Transactions on Image Processing 30 (2021) 9306–9320.
  * [34] O. Tursun, S. Denman, R. Zeng, S. Sivapalan, S. Sridharan, C. Fookes, Mtrnet++: One-stage mask-based scene text eraser, Computer Vision and Image Understanding 201 (2020) 103066.
  * [35] C. Liu, L. Jin, Y. Liu, C. Luo, B. Chen, F. Guo, K. Ding, Don’t forget me: Accurate background recovery for text removal via modeling local-global context, in: ECCV, 2022.
  * [36] X. Bian, C. Wang, W. Quan, J. Ye, X. Zhang, D.-M. Yan, Scene text removal via cascaded text stroke detection and erasing, Computational Visual Media 8 (2) (2022) 273–287.
  * [37] G. Lyu, A. Zhu, Psstrnet: Progressive segmentation-guided scene text removal network, in: ICME, 2022.
  * [38] Y. F, V. Koltun, Multi-scale context aggregation by dilated convolutions, in: ICLR, 2016.
  * [39] H. Jie, S. Li, S. Gang, Squeeze-and-excitation networks, in: CVPR, 2018.
  * [40] J. Johnson, A. Alahi, L. Fei-Fei, Perceptual losses for real-time style transfer and super-resolution, in: ECCV, 2016.
  * [41] L. A. Gatys, A. S. Ecker, M. Bethge, Image style transfer using convolutional neural networks, in: CVPR, 2016.
  * [42] F. Milletari, N. Navab, S. Ahmadi, V-net, Fully convolutional neural networks for volumetric medical image segmentation, in: 3DV, 2016.
  * [43] A. Gupta, A. Vedaldi, A. Zisserman, Synthetic data for text localisation in natural images, in: CVPR, 2016.
  * [44] Y. Baek, B. Lee, D. Han, S. Yun, H. Lee, Character region awareness for text detection, in: CVPR, 2019.
  * [45] J. Long, E. Shelhamer, T. Darrell, Fully convolutional networks for semantic segmentation, in: CVPR, 2015.


# The open question of time fractional PDEs: needs to store all data

Jichun Li Department of Mathematical Sciences University of Nevada Las Vegas
(jichun.li<EMAIL_ADDRESS>Yangpeng Zhang 11footnotemark: 1
Yangwen Zhang Department of Mathematics Science, Carnegie Mellon University,
Pittsburgh, PA, USA (yangwenz@andrew.cmu.edu).

###### Abstract

It is well known that the nunerical solution of time fractional PDEs at
current stage depends on all preceding time instances. Hence, the storage
requirement grow linearly as the number of the time steps increases, which
poses a significant challenge especially for high-dimensional problems. To the
best of our knowledge, this is still an open question in the time fractional
PDEs. In this paper, we propose an efficient and memory free algorithm to
answer this open question by using incremental SVD. Numercial experiemnts show
that our new algorithm not only memory free, but also more efficient than
standard solvers.

##  1 A time-fractional PDE

In this paper, we consider the following time-fractional parabolic equation
for $u(\bm{x},t)$ :

$\displaystyle\begin{split}\partial_{t}^{\alpha}u(\bm{x},t)-\Delta
u(\bm{x},t)&=f(\bm{x},t),\qquad(\bm{x},t)\in\Omega\times(0,T],\\\
u(\bm{x},t)&=0,\qquad\qquad~{}(\bm{x},t)\in\partial\Omega\times(0,T],\\\
u(\bm{x},0)&=u_{0}(\bm{x}),\qquad~{}\bm{x}\in\Omega,\end{split}$ (1.1)

where $\Omega$ is a bounded convex polygonal domain in
$\mathbb{R}^{d}~{}(d=2,3)$ with a boundary $\partial\Omega$ and $u_{0}$ is a
given function defined on the domain $\Omega$ and $T>0$ is a fixed value. Here
$\partial_{t}^{\alpha}u~{}(0<\alpha<1)$ denotes the left-sided Caputo
fractional derivative of order $\alpha$ with respect to $t$ and it is defined
by

$\partial_{t}^{\alpha}u(\bm{x},t)=\frac{1}{\Gamma(1-\alpha)}\int_{0}^{t}(t-s)^{-\alpha}\frac{\mathrm{d}}{\mathrm{d}s}u(\bm{x},s)\mathrm{d}s,$

where $\Gamma(\cdot)$ is Euler’s Gamma function defined by
$\Gamma(x)=\int_{0}^{\infty}s^{x-1}\mathrm{e}^{-s}\mathrm{~{}d}s$ for $x>0.$

Let $\mathcal{T}_{h}$ be a shape regular and quasiuniform triangulation of
domain $\Omega$ and define a continuous piecewise linear finite element space
$V_{h}$ by

$V_{h}=\left\\{v_{h}\in H_{0}^{1}(\Omega):\left.v_{h}\right|_{K}\text{ is a
linear function, }\forall K\in\mathcal{T}_{h}\right\\}.$

Then the semidiscrete Galerkin scheme for problem (1.1) reads: find
$u_{h}(t)\in V_{h}$ such that

$\left(\partial_{t}^{\alpha}u_{h},\chi\right)+\left(\nabla
u_{h},\nabla\chi\right)=(f,\chi)\quad\forall\chi\in V_{h},t>0.$

For the time discretization, we divide the interval $[0,T]$ into $N$ equally
spaced subintervals with a time step size $\Delta t=T/N$, and $t_{n}=n\Delta
t,n=0,\ldots,N$. Then the $L_{1}$ scheme [5, 4] approximates the Caputo
fractional derivative $\partial_{t}^{\alpha}u\left(\bm{x},t_{n}\right)$ by

$\displaystyle\partial_{t}^{\alpha}u\left(\bm{x},t_{n}\right)$
$\displaystyle=\frac{1}{\Gamma(1-\alpha)}\sum_{j=0}^{n-1}\int_{t_{j}}^{t_{j+1}}\frac{\partial
u(\bm{x},s)}{\partial s}\left(t_{n}-s\right)^{-\alpha}\mathrm{d}s$
$\displaystyle\approx\frac{1}{\Gamma(1-\alpha)}\sum_{j=0}^{n-1}\frac{u\left(\bm{x},t_{j+1}\right)-u\left(\bm{x},t_{j}\right)}{\Delta
t}\int_{t_{j}}^{t_{j+1}}\left(t_{n}-s\right)^{-\alpha}\mathrm{d}s$
$\displaystyle=\sum_{j=0}^{n-1}\beta_{j}\frac{u\left(\bm{x},t_{n-j}\right)-u\left(\bm{x},t_{n-j-1}\right)}{(\Delta
t)^{\alpha}\Gamma(2-\alpha)}=:\bar{\partial}_{\Delta
t}^{\alpha}u\left(t_{n}\right),$

where the weights $\left\\{\beta_{j}\right\\}$ are given by

$\beta_{j}=(j+1)^{1-\alpha}-j^{1-\alpha},\quad j=0,1,\ldots,n-1.$

Then the fully discrete scheme reads: given $u_{h}^{0}=\mathcal{I}_{h}u_{0}\in
V_{h}$ with $c_{\alpha}=\Gamma(2-\alpha)$, find $u_{h}^{n}\in V_{h}$ for
$n=1,2,\ldots,N$ such that

$\displaystyle\beta_{0}\left(u_{h}^{n},v_{h}\right)+c_{\alpha}(\Delta
t)^{\alpha}\left(\nabla u_{h}^{n},\nabla v_{h}\right)$
$\displaystyle=\beta_{n-1}\left(u_{h}^{0},v_{h}\right)+\sum_{j=1}^{n-1}\left(\beta_{j-1}-\beta_{j}\right)\left(u_{h}^{n-j},v_{h}\right)+c_{\alpha}(\Delta
t)^{\alpha}\left(f\left(t_{n}\right),v_{h}\right).$

Here $\mathcal{I}_{h}$ is the standard $L^{2}$ projection from $L^{2}(\Omega)$
into $V_{h}$. The implementationof the scheme is given in Algorithm 1, and we
use $M$ and $A$ to denote the standard mass and stiffness matrices.

Algorithm 1 (Finite element and $L_{1}$ scheme for solving time fractional
heat equation)

Input: $c_{\alpha}$, $\alpha$, $\Delta t$, $M\in\mathbb{R}^{m\times m}$,
$A\in\mathbb{R}^{m\times m}$, $u_{0}$

1:Set $\widetilde{u}_{0}=Mu_{0}$; $\widetilde{A}=M+c_{\alpha}(\Delta
t)^{\alpha}A$; $\bm{\beta}=\texttt{zeros}(m,1)$;
$\widetilde{U}=\texttt{zeros}(m,n)$

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

3: $\bm{\beta}(i)=i^{1-\alpha}-(i-1)^{1-\alpha}$; $\bm{\beta}(1)=1$;

4: Get the load vector at $t_{i}$, denoted by $b_{i}$;

5: $b_{i}=\bm{\beta}(i)\widetilde{u}_{0}+c_{\alpha}(\Delta
t)^{\alpha}b_{i}+\sum_{j=1}^{i-1}(\bm{\beta}(j)-\bm{\beta}(j+1))\widetilde{U}(:,i-j)$;

6: Solve $\widetilde{A}u_{i}=b_{i}$;

7: $\widetilde{U}(:,i)=Mu_{i}$;

8:end for

Output: $u_{m}$

The computational cost of Algorithm 1 is obvious: To compute the numerical
solution at $t_{n}$, the solutions at all preceding time instances are
required, which poses a significant challenge especially for high-dimensional
problems and multi-query applications.

##  2 Incremental SVD

In 2002, Brand [1] proposed an incremental algorithm to find the SVD of a low
rank matrix. However, the algorithm needs to compute thousands or millions of
orthogonal matrices and their multiplications together. Those multiplications
may corrode the orthogonality and many reorthogonalizations are needed in
practice.

Very recently, Zhang [7] improved the incremental SVD and could avoid
computing those large amount orthogonal matrices. Hence, the expensive
reorthogonalizations are not needed. Furtheremore, it is proved that the
modification does not change the accuarcy of the algorithm.

Let us start by introducing some notation needed throughout this work. For
convenience, we adopt the Matlab notation herein. Given a matrix $U$, we use
$U(:,1:r)$ and $U_{r}$ to denote the first $r$ columns of $U$, and
$U(1:r,1:r)$ be the leading principal minor of $U$ of order $r$.

Next, we follow [7] and briefly discuss the incremental SVD algorithm.

###  2.1 Initialization

Assume that the first column of $U$ is nonzero, i.e., $u_{1}\neq 0$, we
initialize the core SVD of $u_{1}$ by setting

$\displaystyle\Sigma=(u_{1}^{\top}u_{1})^{1/2},\quad Q=u_{1}\Sigma^{-1},\quad
R=1.$

The algorithm is shown in Algorithm 2.

Algorithm 2 (Initialize ISVD)

Input: $u_{1}\in\mathbb{R}^{m}$

1:$\Sigma=\left(u_{1}^{\top}u_{1}\right)^{1/2}$; $Q=u_{1}\Sigma^{-1}$; $R=1$;

Output: $Q,\Sigma,R$.

Suppose we already have the rank- $k$ truncated SVD of the first $\ell$
columns of $U$:

$\displaystyle U_{\ell}=Q\Sigma
R^{\top},\quad\textup{with}\;\;Q^{\top}Q=I,\quad
R^{\top}R=I,\quad\Sigma=\operatorname{diag}\left(\sigma_{1},\ldots,\sigma_{k}\right),$
(2.1)

where $\Sigma\in\mathbb{R}^{k\times k}$ is a diagonal matrix with the $k$
(ordered) singular values of $U_{\ell}$ on the diagonal,
$Q\in\mathbb{R}^{m\times k}$ is the matrix containing the corresponding $k$
left singular vectors of $U_{\ell}$, and $R\in\mathbb{R}^{\ell\times k}$ is
the matrix of the corresponding $k$ right singular vectors of $U_{\ell}$.

Since we assume that the matrix $U$ is low rank, then it is reasonable to
anticipate that most vectors of $\\{u_{\ell+1},u_{\ell+2},\ldots,u_{n}\\}$ are
linear dependent or almost linear dependent with the vectors in
$Q\in\mathbb{R}^{m\times k}$. Without loss of generality, we assume that the
next $s$ vectors, $u_{\ell+1}$, $\ldots$, $u_{\ell+s}$, their residuals are
less than the tolerance when project them onto the space spanned by the
columns of $Q$. While the residual of $u_{\ell+s+1}$ is greater than the
tolerance, i.e.,

$\displaystyle\|u_{i}-QQ^{\top}u_{i}\|$ $\displaystyle<\texttt{tol},\qquad
i=\ell+1,\ldots,\ell+s,$ $\displaystyle\|u_{i}-QQ^{\top}u_{i}\|$
$\displaystyle\geq\texttt{tol},\qquad i=\ell+s+1.$

###  2.2 Update the SVD of $U_{\ell+s}$

By (2.1) and the above assumption, we have

$\displaystyle U_{\ell+s}$
$\displaystyle=[U_{\ell}~{}\big{|}~{}u_{\ell+1}~{}\big{|}~{}\ldots~{}\big{|}~{}u_{\ell+s}]$
$\displaystyle=[Q\Sigma
R^{\top}~{}\big{|}~{}u_{\ell+1}~{}\big{|}~{}\ldots~{}\big{|}~{}u_{\ell+s}]$
$\displaystyle\approx[Q\Sigma
R^{\top}~{}\big{|}~{}QQ^{\top}u_{\ell+1}~{}\big{|}~{}\ldots~{}\big{|}~{}QQ^{\top}u_{\ell+s}]$
$\displaystyle=Q\underbrace{[\Sigma~{}\big{|}~{}Q^{\top}u_{\ell+1}~{}\big{|}~{}\ldots~{}\big{|}~{}Q^{\top}u_{\ell+s}]}_{Y}\left[\begin{array}[]{cc}R&0\\\
0&I_{s}\end{array}\right]^{\top}$

We use the Matlab built-in function svd(Y,  ‘econ’) to find the SVD of $Y$
since the matrix $Y$ is always short-and-fat. We let
$Y=Q_{Y}\Sigma_{Y}R_{Y}^{\top}$ and split $R_{Y}$ into
$\left[\begin{array}[]{cc}R_{Y}^{(1)}\\\ R_{Y}^{(2)}\end{array}\right]$, we
then update the SVD of $U_{\ell+s}$ by

$\displaystyle Q\longleftarrow
QQ_{Y},\quad\Sigma\longleftarrow\Sigma_{Y},\quad
R\longleftarrow\left[\begin{array}[]{cc}RR_{Y}^{(1)}\\\
R_{Y}^{(2)}\end{array}\right]\in\mathbb{R}^{k\times(k+s)}.$

###  2.3 Update the SVD of $U_{\ell+s+1}$

The SVD of $U_{\ell+s+1}$ can be constructed by

  * (1)

letting $e=u_{\ell+s+1}-QQ^{\top}u_{\ell+s+1}$ and let $p=\|e\|$ and
$\widetilde{e}=e/p$,

$\displaystyle U_{\ell+s+1}$
$\displaystyle=\left[U_{\ell+s}~{}\big{|}~{}u_{\ell+1}\right]=\left[Q\Sigma
R^{\top}~{}\big{|}~{}p\widetilde{e}+QQ^{\top}u_{\ell+s+1}\right]$
$\displaystyle=\left[Q~{}\big{|}~{}\widetilde{e}\right]\underbrace{\left[\begin{array}[]{cc}\Sigma&Q^{\top}u_{\ell+s+1}\\\
0&p\end{array}\right]}_{\bar{Y}}\left[\begin{array}[]{cc}R&0\\\
0&1\end{array}\right]^{\top},$

  * (2)

finding the full SVD of
$\bar{Y}=\left[\begin{array}[]{cc}\Sigma&Q^{\top}u_{\ell+s+1}\\\
0&p\end{array}\right]$, and let $\bar{Q}\bar{\Sigma}\bar{R}^{\top}$ be the SVD
of $\bar{Y}$, then

  * (3)

updating the SVD of $\left[U_{\ell+s}~{}\big{|}~{}u_{\ell+s+1}\right]$ by

$\displaystyle\left[U_{\ell+s}~{}\big{|}~{}u_{\ell+s+1}\right]=\left(\left[Q~{}\big{|}~{}\widetilde{e}\right]\bar{Q}\right)\bar{\Sigma}\left(\left[\begin{array}[]{cc}R&0\\\
0&1\end{array}\right]\bar{R}\right)^{\top}.$ (2.4)

For many data sets, they may have a large number of nonzero singular values
but most of them are very small. Without truncating those small singular
values, the incremental SVD algorithm maybe keep computing them and hence the
computational cost is huge. Hence, we need to set another truncation if the
last few singular values are less than a tolerance.

######  Lemma 1.

([7, Lemma 5.1]) Assume that
$\Sigma=\textup{{diag}}\left(\sigma_{1},\sigma_{2},\ldots,\sigma_{k}\right)$
with $\sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{k}$, and
$\bar{\Sigma}=\textup{{diag}}\left(\mu_{1},\mu_{2},\ldots,\mu_{k+1}\right)$
with $\mu_{1}\geq\mu_{2}\geq\ldots\geq\mu_{k+1}$. Then we have

$\displaystyle\mu_{k+1}\leq p,$ (2.5a)
$\displaystyle\mu_{k+1}\leq\sigma_{k}\leq\mu_{k}\leq\sigma_{k-1}\leq\ldots\leq\sigma_{1}\leq\mu_{1}.$
(2.5b)

Inequality (2.5a) implies that the last singular value of $\bar{Y}$ can
possibly be very small, no matter how large of $p$. That is to say the
tolerance we set for $p$ can not avoid the algorithm keeping compute very
small singular values. Hence, another truncation is needed if the data has a
large number of very small singular values. Inequality (2.5b) guarantees us
that _only_ the last singular value of $\bar{Y}$ can possibly less than the
tolerance. Hence, we only need to check the last one.

  * (i)

If $\Sigma_{Y}(k+1,k+1)\geq\texttt{tol}\sum_{j=1}^{k+1}\Sigma_{Y}(j,j)$, then

$\displaystyle
Q\longleftarrow\left[Q~{}\big{|}~{}\widetilde{e}\right]Q_{Y}\quad\Sigma\longleftarrow\Sigma_{Y}\quad
R\longleftarrow\left[\begin{array}[]{cc}R&0\\\ 0&1\end{array}\right]R_{Y}.$
(2.8)

  * (ii)

If $\Sigma_{Y}(k+1,k+1)<\texttt{tol}\sum_{j=1}^{k+1}\Sigma_{Y}(j,j)$, then

$\displaystyle
Q\longleftarrow\left[Q~{}\big{|}~{}\widetilde{e}\right]Q_{Y}(:,1:k)\quad\Sigma\longleftarrow\Sigma_{Y}(1:k,1:k)\quad
R\longleftarrow\left[\begin{array}[]{cc}R&0\\\
0&1\end{array}\right]R_{Y}(:,1:k).$ (2.11)

###  2.4 Reorthogonalization

Theoretically, the matrix $\left[Q~{}\big{|}~{}\widetilde{e}\right]Q_{Y}$ is
orthogonal. However, in practice, small numerical errors cause a loss of
orthogonality. Without a reorthogonalization, the decomposition of the
incremental SVD algorithm is not orthogonal. Therefore, the singular values
are not true and truncation is not reliable.

For the reorthogonalization to
$\left[Q~{}\big{|}~{}\widetilde{e}\right]Q_{Y}$, Oxberry et al. [6] performed
QR and Fareed et al. [2] used modified Gram–Schmidt if the inner product
between $\widetilde{e}$ and the first column of $Q$ is larger than some
tolerance. The computational cost can be high if the rank of the matrix is not
extremely low. In [7], Zhang suggests reorthogonalize it recursively: only
apply the Gram-Schmidt to the new adding vector $\widetilde{e}$ since the
matrix $Q$ has already been reorthogonalized in previous steps.

Algorithm 3 (Update ISVD)

Input: $Q\in\mathbb{R}^{m\times k}$, $\Sigma\in\mathbb{R}^{k\times k}$,
$R\in\mathbb{R}^{\ell\times k},u_{\ell+1}\in\mathbb{R}^{m}$, tol, $V$,
$Q_{0}$, $q$

1:Set $d=Q^{\top}u_{\ell+1}$; $e=u_{\ell+1}-Qd$; $p=(e^{\top}e)^{1/2}$;

2:if $p<\texttt{tol}$ then

3: $q=q+1$;

4: Set $V\\{q\\}=d$;

5:else

6: if $q>0$ then

7: Set $Y=\left[\Sigma~{}\big{|}~{}\texttt{cell2mat}(V)\right]$;

8: $[Q_{Y},\Sigma_{Y},R_{Y}]=\texttt{svd(Y,
{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}
`econ'})}$;

9: Set $Q_{0}=Q_{0}Q_{Y}$, $\Sigma=\Sigma_{Y}$,
$\mathcal{R}_{1}=R_{Y}(1:k,:)$, $\mathcal{R}_{2}=R_{Y}(k+1:{\texttt{end}},:)$,
$R=\left[\begin{array}[]{c}R\mathcal{R}_{1}\\\
\mathcal{R}_{2}\end{array}\right]$;

10: Set $d=Q_{Y}^{\top}d$

11: end if

12: Set $e=e/p$;

13: if $|e^{\top}WQ(:,1)|>\texttt{tol}$ then

14: $e=e-Q(Q^{\top}e)$; $p_{1}=(e^{\top}e)^{1/2}$; $e=e/p_{1}$;

15: end if

16: Set $Y=\left[\begin{array}[]{cc}\Sigma&d\\\ 0&p\end{array}\right]$;

17: $[Q_{Y},\Sigma_{Y},R_{Y}]=$ svd $(Y)$;

18: Set $Q_{0}=\left[\begin{array}[]{cc}Q_{0}&0\\\
0&1\end{array}\right]Q_{Y}$;

19: if $\Sigma_{Y}(k+1,k+1)>\texttt{tol}\sum_{j=1}^{k+1}\Sigma_{Y}(j,j)$ then

20: $Q=[Q~{}\big{|}~{}e]Q_{0},\quad\Sigma=\Sigma_{Y}$,
$R=\left[\begin{array}[]{cc}R&0\\\ 0&1\end{array}\right]R_{Y}$,
$Q_{0}=I_{k+1}$;

21: else

22: Set $Q=[Q~{}\big{|}~{}e]Q_{0}(:,1:k)$,
$\Sigma=\Sigma_{Y}(1:k,1:k),\;R=\left[\begin{array}[]{cc}R&0\\\
0&1\end{array}\right]R_{Y}(:,1:k),\;Q_{0}=I_{k}$

23: end if

24: $V=$ []; $q=1$;

25:end if

Output: $Q$, $\Sigma$, $R$, $V$, $Q_{0}$, $q$

######  Remark 1.

Some care should be taken to assemble the matrix $Y$ in line 7 of Algorithm 3.
In Matlab, it is extremely expensive if we update the matrix $V$ by

$\displaystyle V\longleftarrow\left[V~{}\big{|}~{}d\right].$

We save the vector $d$ in a cell array and then use cell2mat to convert it
into a matrix.

###  2.5 Final check and full implementation

We note that the output of Algorithm 3, $V$, may be not empty. This implies
that the output of Algorithm 3 is not the SVD of $U$. Hence we have to update
the SVD for the vectors in $V$. We give the implementation of this step in
Algorithm 4.

Algorithm 4 ( ISVD final check)

Input: $Q\in\mathbb{R}^{m\times k}$, $\Sigma\in\mathbb{R}^{k\times k}$,
$R\in\mathbb{R}^{\ell\times k}$, $V$, $q$

1:if $q>0$ then

2: Set $Y=\left[\Sigma~{}\big{|}~{}\texttt{cell2mat}(V)\right]$;

3: $[Q_{Y},\Sigma_{Y},R_{Y}]=\texttt{svd(Y,
{\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}
`econ'})}$;

4: Set $Q=QQ_{Y}$, $\Sigma=\Sigma_{Y}$, $\mathcal{R}_{1}=R_{Y}(1:k,:)$,
$\mathcal{R}_{2}=R_{Y}(k+1:{\texttt{end}},:)$,
$R=\left[\begin{array}[]{c}R\mathcal{R}_{1}\\\
\mathcal{R}_{2}\end{array}\right]$;

5:end if

Output: $Q$, $\Sigma$, $R$.

Next, we complete the full implementation in Algorithm 5.

Algorithm 5 (Full ISVD)

Input: tol

1:Get $u_{1}$;

2:$[Q,\Sigma,R]$=InitializeISVD($u_{1}$); % Algorithm 2

3:Set $V=$ []; $Q_{0}=1$; $q=0$;

4:for $\ell=2,\ldots,n$ do

5: Get $u_{\ell}$

6:
$[q,V,Q_{0},Q,\Sigma,R]$=UpdateISVD($q,V,Q_{0},Q,\Sigma,R,u_{\ell},\texttt{tol}$);
% Algorithm 3

7:end for

8:$[Q,\Sigma,R]$=ISVDfinalcheck($q,V,Q_{0},Q,\Sigma,R$); % Algorithm 4

Output: $Q$, $\Sigma$, $R$.

##  3 Incremental SVD for the time fractional PDEs

In this section, we shall apply the incremental SVD for the time fractional
heat equation (1.1).

Suppose we have already computed $u_{1}$, $\ldots$, $u_{\ell}$, and have the
rank- $k$ truncated SVD of $U_{\ell}=[u_{1}\mid u_{2}\mid\cdots u_{\ell}]$ by
using the incremental SVD algorithm :

$\displaystyle U_{\ell}=Q\Sigma
R^{\top},\quad\textup{with}\;\;Q^{\top}Q=I,\quad
R^{\top}R=I,\quad\Sigma=\operatorname{diag}\left(\sigma_{1},\ldots,\sigma_{k}\right).$
(3.1)

We do not store the data $\\{u_{i}\\}_{i=1}^{\ell}$, instead, we keep the
matrices $Q\in\mathbb{R}^{n\times k}$, $\Sigma\in\mathbb{R}^{k\times k}$ and
$R\in\mathbb{R}^{\ell\times k}$. Since $k\ll\ell$, then we remedy the memory
issue of the standard method.

To compute $u_{\ell+1}$, we need to extract the data from the matrices $Q$,
$\Sigma$ and $R$, i.e.,

$\displaystyle u_{j}=Q\Sigma R_{j}^{\top},\quad j=1,2,\ldots,\ell,$

and then compute

$\displaystyle Mu_{j}=MQ\Sigma R_{j}^{\top},\quad j=1,2,\ldots,\ell.$

The matrix $MQ$ stays unchanged unless the residual of the new coming data
$u_{\ell+1}$ is greater than the tolerance, when we project it onto the space
spanned by the columns of $Q$.

Algorithm 6 (Solve a fractional PDE with ISVD)

Input: $c_{\alpha}$, $\alpha$, $\Delta t$, $m$, $M\in\mathbb{R}^{m\times m}$,
$A\in\mathbb{R}^{m\times m}$, $u_{0}$, $u_{1}$, tol

1:Set $V=$ []; $Q_{0}=1$; $q=0$; $\widetilde{u}_{0}=Mu_{0}$;
$\widetilde{A}=M+c_{\alpha}(\Delta t)^{\alpha}A$;
$\bm{\beta}=\texttt{zeros}(m,1)$;

2:$[Q,\Sigma,R]$=InitializeISVD($u_{1}$); % Algorithm 2

3:for $i=2$ to $m$ do

4: $\bm{\beta}(i)=i^{1-\alpha}-(i-1)^{1-\alpha}$;

5: Get the load vector at $t_{i}$, denoted by $b_{i}$;

6: if $q==0$ then

7: $\texttt{MQ}=MQ$; $C=\Sigma R^{\top}$

8: $b_{i}=\bm{\beta}(i)\widetilde{u}_{0}+c_{\alpha}(\Delta
t)^{\alpha}b_{i}+\texttt{MQ}\left(\sum_{j=1}^{i-1}(\bm{\beta}(j)-\bm{\beta}(j+1))C(:,i-j)\right)$;

9: Solve $\widetilde{A}u_{i}=b_{i}$;

10:
$[q,V,Q_{0},Q,\Sigma,R]$=UpdateISVD($q,V,Q_{0},Q,\Sigma,R,u_{i},\texttt{tol}$);
% Algorithm 3

11: if $q>0$ then

12: $C=\Sigma R^{\top}$

13: end if

14: else

15: $D=[C\quad\texttt{cell2mat}(V)]$;

16: $b_{i}=\bm{\beta}(i)\widetilde{u}_{0}+c_{\alpha}(\Delta
t)^{\alpha}b_{i}+\texttt{MQ}\left(\sum_{j=1}^{i-1}D(:,i-j)\bm{\beta}(j)\right)$;

17: Solve $\widetilde{A}u_{i}=b_{i}$;

18:
$[q,V,Q_{0},Q,\Sigma,R]$=UpdateISVD($q,V,Q_{0},Q,\Sigma,R,u_{i},\texttt{tol}$);
% Algorithm 3

19: end if

20:end for

21:$[Q,\Sigma,R]$=UpdateISVDcheck($q,V,Q_{0},Q,\Sigma,R$); % Algorithm 4

Input: $Q$, $\Sigma$, $R$

##  4 Numerical experiments

In this section, we test the efficiency of our Algorithm 6.

######  Example 1.

Let $\Omega=(0,1)\times(0,1)$, we consider the equation (1.1) with

$\displaystyle\alpha=0.1,\quad T=1,\quad u_{0}=xy(1-x)(1-y),\quad
f=100\sin(2\pi t(x+y))x(1-x)y(1-y).$

We use the linear finite element for the spatial discretization with different
time steps $\Delta t$, here $h$ is the mesh size (max diameter of the
triangles in the mesh). For the incremental SVD, we take tol $=10^{-12}$ in
Algorithm 6. For solving linear systems, we apply the Matlab built-in solver
backslash ($\backslash$). We report the wall time (seconds) 111All the code
for all examples in the paper has been created by the authors using Matlab
R2020b and has been run on a laptop with MacBook Pro, 2.3 Ghz8-Core Intel Core
i9 with 64GB 2667 Mhz DDR4. We use the Matlab built-in function tic-toc to
denote the real simulation time. of Algorithm 1 and Algorithm 6 in Table 1. We
also compute the $L^{2}$-norm error between the solutions of Algorithm 1 and
Algorithm 6 at the final time $T=1$, we see that the error is close to the
machine error. Furthermore, Algorithm 6 is more efficient than Algorithm 1. In
Table 2, we see that the standard solver has an issue to save the data.
However, our new Algorithm 6 avoids storing the huge data.

$h$ | $1/2^{3}$ | $1/2^{4}$ | $1/2^{5}$ | $1/2^{6}$ | $1/2^{7}$ | $1/2^{8}$ | $1/2^{9}$
---|---|---|---|---|---|---|---
Wall time of Algorithm 1 | 0.3 | 0.6 | 2 | 10 | 36 | 162 | 680
Wall time of Algorithm 6 | 0.4 | 0.8 | 2 | 8 | 36 | 146 | 670
Error | 8E-15 | 2E-14 | 3E-14 | 3E-14 | 3E-14 | 3E-14 | 3E-14
|  |  |  |  |  |  |
Table 1: Example 1 with $\Delta t=10^{-3}$: The wall time and the $L^{2}$-norm error between the solutions of Algorithm 1 and Algorithm 6. $h$ | $1/2^{3}$ | $1/2^{4}$ | $1/2^{5}$ | $1/2^{6}$ | $1/2^{7}$ | $1/2^{8}$ | $1/2^{9}$ | $1/2^{10}$
---|---|---|---|---|---|---|---|---
Wall time of Algorithm 1 | 6 | 17 | 52 | 257 | 700 | 2410 | 9519 | —
Wall time of Algorithm 6 | 11 | 15 | 26 | 83 | 330 | 1405 | 6424 | 25835
Error | 1E-12 | 2E-14 | 3E-14 | 3E-14 | 3E-14 | 3E-14 | 3E-14 | —
|  |  |  |  |  |  |  |
Table 2:  Example 1 with $\Delta t=10^{-4}$: The wall time and the
$L^{2}$-norm error between the solutions of Algorithm 1 and Algorithm 6, —
denotes we have the memory issue.

######  Example 2.

In this example, we use the incremental SVD algorithm to study the time
fractional diffusion-wave equation:

$\displaystyle\partial_{t}^{\alpha}u(\bm{x},t)-\Delta u(\bm{x},t)$
$\displaystyle=f(\bm{x},t),$ $\displaystyle(\bm{x},t)\in\Omega\times(0,T],$
$\displaystyle u(\bm{x},t)$ $\displaystyle=0,$
$\displaystyle(\bm{x},t)\in\partial\Omega\times(0,T],$ $\displaystyle
u(\bm{x},0)$ $\displaystyle=u_{0}(\bm{x}),$ $\displaystyle\bm{x}\in\Omega,$
$\displaystyle u_{t}(\bm{x},0)$ $\displaystyle=v_{0}(\bm{x}),$
$\displaystyle\bm{x}\in\Omega,$

where $\Omega\subset\mathbb{R}^{2}$ is a bounded convex polygonal region with
boundary $\partial\Omega$, $\bm{x}=(x,y)$, $u_{0}(\mathbf{x})$,
$v_{0}(\bm{x})$ and $f(\bm{x},t)$ are given functions, and
$\partial_{t}^{\alpha}u~{}(1<\alpha<2)$ denotes the left-sided Caputo
fractional derivative of order $\alpha$ with respect to $t$ and it is defined
by

$\partial_{t}^{\alpha}u(\mathbf{x},t)=\frac{1}{\Gamma(2-\alpha)}\int_{0}^{t}\frac{\partial^{2}u(\bm{x},s)}{\partial
s^{2}}\frac{\mathrm{d}s}{(t-s)^{\alpha-1}},\quad 1<\alpha<2.$

Let $0=t_{0}<t_{1}<\cdots<t_{N}=T$ be a given partition of the time interval.
Then we have the time step $\Delta t=T/N$, $t_{n}=n\Delta t(n=0,1,\ldots,N)$,
and define $\bar{\partial}_{t}^{\alpha}u^{n+1}$ by

$\displaystyle\frac{\partial^{\alpha}u\left(\bm{x},t_{n+1}\right)}{\partial
t^{\alpha}}$
$\displaystyle=\frac{1}{\Gamma(2-\alpha)}\int_{0}^{t_{n+1}}\frac{\partial^{2}u(\bm{x},\xi)}{\partial
s^{2}}\left(t_{n+1}-s\right)^{1-\alpha}\mathrm{d}s$
$\displaystyle=\frac{1}{\Gamma(2-\alpha)}\sum_{k=0}^{n}\int_{t_{k}}^{t_{k+1}}\frac{\partial^{2}u(\bm{x},s)}{\partial
s^{2}}\left(t_{n+1}-s\right)^{1-\alpha}\mathrm{d}s$
$\displaystyle\approx\frac{1}{\Gamma(2-\alpha)}\sum_{k=0}^{n}\frac{u_{k+1}-2u_{k}+u_{k-1}}{\Delta
t^{2}}\int_{t_{k}}^{t_{k+1}}\left(t_{n+1}-s\right)^{1-\alpha}\mathrm{d}s,$

where $u_{k}=u\left(\bm{x},t_{k}\right),k=0,1,2,\ldots,N$. In the above
equation, the integral is easily obtained as

$\int_{t_{k}}^{t_{k+1}}\left(t_{n+1}-s\right)^{1-\alpha}\mathrm{d}s=\frac{1}{(2-\alpha)}\Delta
t^{2-\alpha}\left[(n-k+1)^{2-\alpha}-(n-k)^{2-\alpha}\right].$

Let $\beta_{k}=(k+1)^{2-\alpha}-k^{2-\alpha}$ and define
$\bar{\partial}_{t}^{\alpha}u_{h}^{n+1}$ by

$\displaystyle\bar{\partial}_{t}^{\alpha}u_{h}^{n+1}=\frac{\Delta
t^{-\alpha}}{\Gamma(3-\alpha)}\sum_{k=0}^{n}\beta_{k}\left[u_{n-k+1}-2u_{n-k}+u_{n-k-1}\right],$

where $u_{h}^{0}=\mathcal{I}_{h}u_{0}$, $u_{h}^{-1}=u_{h}^{0}-\Delta
t\mathcal{I}_{h}v_{0}$. Then the fully discrete scheme reads: given
$u_{h}^{-1},u_{h}^{0}\in V_{h}$, find $u_{h}^{n+1}\in V_{h}$ for
$n=0,1,2,\ldots$ such that

$\displaystyle\left(\bar{\partial}_{t}^{\alpha}u_{h}^{n+1},v_{h}\right)+\left(\nabla
u_{h}^{n+1},\nabla v_{h}\right)=\left(f^{n+1},v_{h}\right),\quad\forall
v_{h}\in V_{h}.$

Next, we consider the above wave equation with

$\displaystyle\Omega=(0,1)^{2},\;\;\alpha=1.5,\;\;u_{0}=xy(1-x)(1-y),\;\;v_{0}=0,\;\;f=1.$

The mesh and the finite element space are the same with Example 1. We report
the wall time (seconds) and errors at the final time $T=1$ in Table 3. Again,
our incremental SVD not only memory free, but also more efficient than the
standard solver.

$h$ | $1/2^{3}$ | $1/2^{4}$ | $1/2^{5}$ | $1/2^{6}$ | $1/2^{7}$ | $1/2^{8}$ | $1/2^{9}$ | $1/2^{10}$
---|---|---|---|---|---|---|---|---
Wall time of Algorithm 1 | 6 | 19 | 77 | 330 | 1002 | 3183 | 13175 | —
Wall time of Algorithm 6 | 24 | 63 | 111 | 293 | 862 | 2645 | 12748 | 60234
Error | 1E-09 | 4E-10 | 4E-10 | 3E-10 | 3E-10 | 3E-10 | 6E-10 | —
|  |  |  |  |  |  |  |
Table 3: Example 2 with $\Delta t=10^{-4}$: The wall time and the $L^{2}$-norm
error between the solutions of Algorithm 1 and Algorithm 6, — denotes we have
the memory issue.

##  5 Conclusion

In this paper, we propose an efficient and memory free algorithm for solving
the time-fractional PDEs by using the incremental SVD algorithm. Although we
only test the fractional heat equation, we beleive this algorithm could be
easily to extend to other time-fractional PDEs such as the Cole-Cole Maxwell’s
equations [4]. Furthermore, we will investigate time-dependent PDEs with
memory effects, since they share the same challenge that a whole past history
of the solution is needed to be stored and used.

## References

  * [1] M. Brand, Incremental singular value decomposition of uncertain data with missing values, in European Conference on Computer Vision, Springer, 2002, pp. 707-720.
  * [2] H. Fareed, J. R. Singler, Y. Zhang, and J. Shen, Incremental proper orthogonal decomposition for PDE simulation data, Comput. Math. Appl., 75 (2018), pp. 1942-1960,
  * [3] J. Li and Y. Huang, Time-Domain Finite Element Methods for Maxwell’s Equations in Metamaterials, Springer Ser. Comput. Math. 43, Springer, New York, 2013.
  * [4] J. Li, Y. Huang and Y. Lin, Developing finite element methods for Maxwell’s equations in a Cole-Cole dispersive medium, SIAM J. Sci. Comput., 33:6 (2011), 3153-3174
  * [5] Y. Lin and C. Xu, Finite difference spectral approximations for the time-fractional diffusion equation, J. Comput. Phys., 225:2 (2007), 1533-1552.
  * [6] G. M. Oxberry, T. Kostova-Vassilevska, W. Arrighi, and K. Chand, Limited-memory adaptive snapshot selection for proper orthogonal decomposition, Internat. J. Numer. Methods Engrg., 109 (2017), pp. 198-217.
  * [7] Y. Zhang, An answer to an open question in the incremental SVD, https://arxiv.org/abs/2204.05398.