# Adaptive Fusion Affinity Graph with Noise-free Online Low-rank
Representation for Natural Image Segmentation

Yang Zhang, Moyun Liu, Huiming Zhang, Guodong Sun, and Jingwu He Y. Zhang and
G. Sun are with the School of Mechanical Engineering, Hubei University of
Technology, Wuhan 430068, China (e-mail<EMAIL_ADDRESS>sgdeagle@163.com).M. Liu is with the School of Mechanical Science and
Engineering, Huazhong University of Science and Technology, Wuhan 430074,
China (email: lmomoy8@gmail.com).Y. Zhang, H. Zhang, and J. He are with the
National Key Laboratory for Novel Software Technology, Nanjing University,
Nanjing 210023, China (email<EMAIL_ADDRESS>hejw005@gmail.com).

###### Abstract

Affinity graph-based segmentation methods have become a major trend in
computer vision. The performance of these methods rely on the constructed
affinity graph, with particular emphasis on the neighborhood topology and
pairwise affinities among superpixels. Due to the advantages of assimilating
different graphs, a multi-scale fusion graph has a better performance than a
single graph with single-scale. However, these methods ignore the noise from
images which influence the accuracy of pairwise similarities. Multi-scale
combinatorial grouping and graph fusion also generate a higher computational
complexity. In this paper, we propose an adaptive fusion affinity graph (AFA-
graph) with noise-free low-rank representation in an online manner for natural
image segmentation. An input image is first over-segmented into superpixels at
different scales and then filtered by the proposed improved kernel density
estimation method. Moreover, we select global nodes of these superpixels on
the basis of their subspace-preserving presentation, which reveals the feature
distribution of superpixels exactly. To reduce time complexity while improving
performance, a sparse representation of global nodes based on noise-free
online low-rank representation is used to obtain a global graph at each scale.
The global graph is finally used to update a local graph which is built upon
all superpixels at each scale. Experimental results on the BSD300, BSD500,
MSRC, SBD, and PASCAL VOC show the effectiveness of AFA-graph in comparison
with state-of-the-art approaches. The code is available at
https://github.com/Yangzhangcst/AFA-graph.

###### Index Terms:

Graph, image segmentation, superpixels, sparse subspace clustering, low-rank
representation, affinity propagation

##  I Introduction

As a fundamental and challenging task in computer vision, image segmentation
is a process of decomposing an image into independent regions, which plays an
important role in many high-level applications [1]. Unsupervised methods
receive much attention because they require no prior knowledge. In the
literature, many unsupervised segmentation methods have been intensively
studied [2]. Some representative works of them rely on constructing a reliable
affinity graph for the representation of image content, such as the adjacency-
graph [3], $\ell$0-graph [4], and global/local affinity graph (GL-graph) [5].

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

Figure 1: Comparison results by different graph-based segmentation methods.
(a) Input image. (b-e) Superpixels generated by over-segmenting the image at
different scales. (f-i) Segmentation results by adjacency-graph [3],
$\ell_{0}$-graph [4], GL-graph [5], and our AFA-graph, respectively. Although
superpixels features are extremely complex and vary greatly at different
scales, our method enforces the global structure and preserves more local
information simultaneously.

Clearly, for these affinity graph-based methods, the segmentation performance
significantly depends on the effectiveness of the constructed affinity graph,
with particular emphasis on the neighborhood topology and pairwise affinities
between nodes (i.e., pixels or superpixels). For example, adjacency-graph [3]
of coherent superpixels is applied to aggregate cues for segmentation.
However, it has not enough ability to collect global grouping cues when the
objects occupy a large of areas in the image. $\ell_{0}$-graph [4] uses sparse
representation, which enables it to capture global grouping cues, but it has
tendency to create isolated regions. As shown in Fig. 1, GL-graph [5] is
proposed to combine the adjacency-graph and the $\ell_{0}$-graph according to
superpixel areas at different scales, leading to a better result than only
using a single graph. The superpixels are simply divided into three parts:
small, medium, and large sized according to their area in GL-graph [5].
However, there still exist three difficulties to be solved: i) these affinity
graph-based methods ignore the noise in images and features, which can
influence the accuracy of pairwise similarities and further hinder the
affinity propagation; ii) due to the extreme complexity of superpixel features
and the wide variation at different scales, the combination principles of
different graphs are unreliable and often rely on empiricism; iii) multi-scale
combinatorial grouping with graph construction are obliged to generate
additional calculations, incurring a higher computational complexity.

To solve these problems, an _adaptive fusion affinity graph_ (AFA-graph) is
proposed to segment natural images. The proposed AFA-graph combines the local
and global nodes of superpixels at different scales based on affinity
propagation. The superpixels are obtained by over-segmenting an input image at
different scales, and then filtered by an improved kernel density estimation
method. We use affinity propagation clustering to select global nodes of these
superpixels according to their subspace-preserving representation. Moreover,
the noise-free online low-rank representation (NOLRR) is used to obtain a
NOLRR-graph at each scale via a sparse representation of mLab features of the
global nodes. All superpixels at each scale are used to build an adjacency-
graph, which are further updated by the NOLRR-graph. We introduce a bipartite
graph to map the relationship between the original image pixels and
superpixels, and to enable propagation of grouping cues across superpixels at
different scales. Intensive experiments are conducted on five public datasets,
namely BSD300, BSD500, MSRC, SBD, and PASCAL VOC with four metrics, including
PRI, VoI, GCE, and BDE for quantitative comparisons. The experimental results
show the effectiveness of our AFA-graph compared with the state-of-the-art
methods.

This work makes the following contributions.

  * •

We explore the impact of noise on pairwise similarity and affinity propagation
between superpixels.

  * •

We construct an AFA-graph to combine different graphs with the sparsity and a
high discriminating power for natural image segmentation.

  * •

We propose a novel NOLRR-graph to improve segmentation performance while
reducing the time complexity.

  * •

Extensive quantitative and qualitative experiments show that our AFA-graph
outperforms recent methods on five benchmark datasets.

A preliminary conference version of this paper can be referred to adaptive
affinity graph with subspace pursuit (AASP-graph) [6]. Compared with AASP-
graph [6], this study contains: i) an adaptive fusion affinity graph named as
AFA-graph is proposed to segment natural images with online low-rank
representation; ii) we propose a novel global node selection strategy
containing subspace-preserving representation and affinity propagation
clustering. As a new algorithmic enhancement, the strategy further perfects
global node selection and improves the segmentation performance; iii) we
propose a NOLRR-graph to improve segmentation accuracy and reduce
computational complexity; iv) we perform extensive experiments to validate the
effectiveness of global node selection strategy and the NOLRR-graph. More
extra experiments on five datasets and theoretical analyses are also added to
verify the robustness of AFA-graph. The official code is available at
https://github.com/Yangzhangcst/AFA-graph.

The rest of this paper is organized as follows. Related works are reviewed in
Section II. The proposed AFA-graph for natural image segmentation is presented
in Section III. Experimental results are reported in Section IV, and the paper
is concluded in Section V.

##  II Related Works

The unsupervised methods segment images without any human intervention. As we
focus on unsupervised image segmentation in this paper, a review of related
methods is introduced in this section. A more detailed review of the image
segmentation process can be found in [1].

The essence of image segmentation can be regarded as a clustering problem,
which groups the pixels into local homogenous regions. Some clustering-based
methods such as $k$-means, mean-shift (MS) [7], fusion of clustering results
(FCR) [8], correlation clustering (Corr-Cluster) [9], higher-order correlation
clustering (HO-CC) [10], deviation-sparse fuzzy c-means (DSFCM) [11],
membership scaling fuzzy c-means (MSFCM) [12], FRFCM [13], automatic fuzzy
clustering (AFC) [14], robust self-sparse fuzzy clustering (RSFFC) [15] and
superpixel-based fast fuzzy c-means (SFFCM) [16] are the typical examples. In
particular, subspace clustering [17, 18] has extensively established in
computer vision. Many subspace clustering algorithms aim to obtain a
structured representation to fit the underlying data, such as sparse subspace
clustering [19] and LRR [20]. Both of them utilize the idea of self-
expressiveness which expresses each sample as a linear combination of the
remaining [17]. However, such approaches can be computationally expensive with
high memory cost. One of the most popular ways to alleviate the computational
complexity is online implementation [18, 21].

Besides clustering-based methods, graph-based methods can be regarded as image
perceptual grouping and organization methods which have become one of the most
popular image segmentation methods. Graph-based methods are based on the
fusion of the feature and spatial information, such as normalized cut (Ncut)
[22], Felzenszwalb-Huttenlocher (FH) graph-based method [23], $\ell_{0}$-graph
[4], iterative ensemble Ncut [24], multi-scale Ncut (MNcut) [25], GL-graph
[5], region adjacency graph (RAG) [26], and AASP-graph [6], etc. More
recently, Kim et al. [27] proposed a multi-layer sparsely connected graph to
effectively combine local grouping cues, and then applied semi-supervised
learning to define the relevance scores between all pairs of these graph nodes
as the affinities of the graph. Wang et al. [28] introduced the normalized
tree partitioning and the average tree partitioning to optimize normalized and
average cut over a tree for image segmentation. Saglam and Baykan [29] used
Prim’s sequential representation of the minimum spanning tree for image
segmentation. Especially, Li et al. [2] proposed a region adjacency cracking
method to adaptively loosen the color labeling constraints.

Furthermore, a heuristic four-color labeling algorithm was used to establish a
uniform appearance of those regions with global consistency. In this method,
affinity propagation clustering [30] is applied to crack the adjacent
constraint, which is suitable for the task with unknown regional
characteristic distribution. Affinity propagation can adaptively determine the
clusters based on the relationship of the given regions. The GL-graph [5] is
built over superpixels to capture both short- and long-range grouping cues,
and thereby enabling propagation of grouping cues between superpixels of
different scales based on a bipartite graph [3]. It can be noticed that the
combination of the global graph and the local graph over superpixels can
obtain a better segmentation result.

##  III FRAMEWORK

In this section, we first introduce the overview of our proposed AFA-graph.
Then, we show the global nodes selection. Finally, we present the process of
NOLRR-graph construction in details.

Figure 2: The overall framework of image segmentation based on the proposed
AFA-graph. After over-segmenting an input image as the SAS [3], we obtain
superpixels at $k$ different scales. Global nodes of superpixels are sorted
out through subspace-preserving representation (SPR) and affinity propagation
clustering (APC) and then build a NOLRR-graph at each scale. The adjacency-
graph is constructed by all superpixels and it is updated by the NOLRR-graph
at each scale. The updated graphs are fused to obtain the final result through
Tcut [3].

###  III-A Overview

The overall framework of the proposed AFA-graph for natural image segmentation
is shown in Fig. 2. The proposed approach primarily consists of three
components: superpixel representation, adaptive affinity graph construction,
and fusion graph partition. For graph-based segmentation, approximating each
superpixel in the feature space into a linear combination of other superpixels
are regarded as neighbors, and their affinities are calculated from the
corresponding representation error [5]. Let
$\textbf{\emph{S}}_{k}=\\{s\\}^{N}_{i=1}$ be the superpixels of an input image
_I_ at scale $k$, where $N$ is the number of superpixels. Formally, such an
approximation can be written as:

$\textbf{\emph{d}}_{j}=\textbf{\emph{D}}\textbf{\emph{c}}_{j},\quad c_{jj}=0,$
(1)

where $\textbf{\emph{d}}_{j}\in\mathbb{R}^{n}$ is a matrix representation of
superpixels over the dictionary D, and
$\textbf{\emph{c}}_{j}\in\mathbb{R}^{N}$ is the sparse representation of
superpixels. The constraint $c_{jj}=0$ prevents the self-representation of
$\textbf{\emph{d}}_{j}$.

As for all superpixels at each scale, every superpixel is connected to its
adjacent superpixels denoted as local graph. Let $\textbf{\emph{M}}_{A}$ be
the matrix-representation of its adjacent neighbors, we attempt to represent
its feature $\textbf{\emph{f}}_{i}$ as a linear combination of elements in
$\textbf{\emph{M}}_{A}$. In practice, we solve the following problem:

$\displaystyle\textbf{\emph{c}}^{\prime\prime}_{i}=\mathop{\arg\min}_{\textbf{\emph{c}}^{\prime}_{i}}||\textbf{\emph{f}}_{i}-\textbf{\emph{M}}_{A}\textbf{\emph{c}}^{\prime}_{i}||_{2}.$
(2)

The affinities coefficient $A_{i,j}$ of the adjacency-graph A between
superpixels $s_{i}$ and $s_{j}$ are calculated as $A_{i,j}=1$, if $i$ is equal
to $j$; $A_{i,j}=1-(r_{i,j}+r_{j,i})/2$, otherwise; where
$r_{i,j}=||\textbf{\emph{f}}_{i}-\textbf{\emph{c}}^{\prime\prime}_{i,j}\textbf{\emph{f}}_{j}||^{2}_{2}$.
To combine different graph, the proposed NOLRR-graph W is replaced by the
adjacency-graph A at global nodes to obtain the updated adjacency-graph
$\textbf{\emph{A}}^{\prime}$ at a certain scale. To map the relationships
between pixels and superpixels and enable propagation of grouping cues across
superpixels at different scales, a bipartite graph is built to describe the
relationships of pixels to superpixels and superpixels to superpixels. In this
case, the bipartite graph is unbalanced, which can be solved by Tcut [3] to
obtain the final segmentation result.

###  III-B Superpixel representation

Superpixel is an irregular pixel block composed of adjacent pixels with
similar features. It is usually used as a preprocessing segmentation step.
Various visual patterns of a natural image can be captured through superpixels
generated by different methods with different parameters. Like the GL-graph
[5], an input image is over-segmented into superpixels using the same
parameters as in SAS [3]. And then, the color features of each superpixel are
characterized by using mean value in the CIE L*a*b* space (mLab).

In general, all natural images contain noise, which influences the accuracy of
pairwise similarities and further hinders the affinity propagation. The
disturbance of the noise to a natural image is reflected in its statistical
features. And the mLab can be regarded as a special statistical feature
(histogram) of the image. As pointed out by [31], a peak in the histogram
corresponds to a relatively more homogeneous region in the image. The mLab of
an image can be estimated in a robust state such that an estimated feature is
less sensitive to local peculiarities.

To reduce the noise, we introduce an improved kernel density estimation (IKDE)
method to estimate the mLab of natural images, and the histogram is smoothed
by single exponential smoothing.

$\textbf{\emph{f}}_{t}^{in}=\alpha\textbf{\emph{f}}_{t}+(1-\alpha)\textbf{\emph{f}}_{t-1}^{in}$
(3)

where $\alpha\in(0,1]$ is an exponential factor. $\textbf{\emph{f}}^{in}_{t}$
is the original features at time period $t$, and $\textbf{\emph{f}}_{t}$ is
the features smoothed by IKDE. As shown in Fig. 3, the essential shape of mLab
features is preserved throughout this process. The IKDE can improve the
reliability of features as explained in subsection IV-B.

(a)

(b)

Figure 3: Illustration of the IKDE with exponential smoothing method. (a)
Original values of the superpixels in Lab color space. (b) Smoothed values of
the superpixels processed by the IKDE.

###  III-C Global Node Selection

It is shown in [17] that superpixels from different groups can be well
approximated by a union of low dimensional subspaces. One way to achieve this
goal is to use the sparse subspace clustering [19] which separates superpixels
into groups such that each group contains only superpixels from the same
subspace. Therefore, global nodes can be classified according to their
subspace-preserving representation (SPR) which is the affiliation
$\textbf{\emph{c}}_{j}$ of superpixels with subspace. It is proved that the
sparsest solution of $\textbf{\emph{c}}_{j}$ measured in the sense of
$\ell_{0}$-norm is unique, and it conveys the most meaningful information of
superpixels [32]. So, the sparse solution can be regarded as follows:

$\textbf{\emph{c}}_{j}^{*}=\mathop{\arg\min}_{\textbf{\emph{c}}_{j}}\|\textbf{\emph{c}}_{j}\|_{0}\quad
s.t.\ \textbf{\emph{f}}_{j}=\textbf{\emph{F}}\textbf{\emph{c}}_{j},\
c_{jj}=0,$ (4)

where $\|\cdot\|_{0}$ represents the $\ell$0-norm which counts the number of
nonzero values in a vector, and $\textbf{\emph{F}}=[\
\emph{{f}}_{1},...,\textbf{\emph{f}}_{N}]\in\mathbb{R}^{n\times N}$ is the
smoothed feature matrix.

Hence, the orthogonal matching pursuit (OMP) [17] method is applied to seek an
approximation of the sparsest solution.

$\textbf{\emph{c}}_{j}^{*}=\mathop{\arg\min}_{\textbf{\emph{c}}_{j}}\|\textbf{\emph{f}}_{j}-\textbf{\emph{F}}\textbf{\emph{c}}_{j}\|_{2}^{2}\quad
s.t.\ \|\textbf{\emph{c}}_{j}\|_{0}\leq\psi,\ c_{jj}=0,$ (5)

where the parameter $\psi$ is the maximal number of coefficients for each
input smoothed feature $\textbf{\emph{f}}_{j}$, which controls the sparsity of
the solution. The solution $\textbf{\emph{c}}_{j}^{*}\in\mathbb{R}^{N}$ (the
_j_ -th column of $\textbf{\emph{C}}^{*}\in\mathbb{R}^{N\times N}$) is
computed by
OMP$(\textbf{\emph{F}}_{-j},\textbf{\emph{f}}_{j})\in\mathbb{R}^{N-1}$ with a
zero inserted in its _j_ -th entry, where $\textbf{\emph{F}}_{-j}$ is the
smoothed feature matrix with the _j_ -th column removed. To better illustrate
the relationship between features and SPR of superpixels, we show superpixels
generated by over-segmenting two images at different scales and compare the
SPR of superpixels computed by mLab with the areas of superpixels in Fig. 4.
It can be seen that the influence of superpixels across different scales on
the SPR is smaller than that of the area in the same image. Therefore, the SPR
can better represent superpixels compared with the area.

In Fig. 4, the features of superpixels are various at different scales. The
global nodes cannot be easily defined in natural images. To address this
issue, we propose a novel similarity between any two superpixels and apply
affinity propagation clustering (APC) [30] with the similarity matrix to find
global nodes. As shown in Fig. 5, the proposed similarity $S_{i,j}$ between
two superpixels $s_{i}$ and $s_{j}$ is defined as a combination of the
Euclidean distance $d^{E}_{ij}$ and the geodesic distance along the
probability density function of their feature histogram.

$S_{i,j}=-\Big{(}|d^{E}_{ij}|^{e}+|\sum_{x=i}^{j-1}d^{E}(x,x+1)|^{g}\Big{)}^{1/2},\
j>i.$ (6)

where $e$ and $g$ are the hyper-parameters which are setting as $e=3$ and
$g=5$, respectively. It can be noticed that APC is very suitable for the task
that we know nothing about the feature distribution of the superpixels
beforehand. After $\textbf{\emph{c}}_{j}^{*}$ is computed, the classification
of the superpixels is obtained by applying spectral clustering to the affinity
matrix
$\textbf{\emph{M}}_{sp}=|\textbf{\emph{C}}^{*}|+|{\textbf{\emph{C}}^{*}}^{\mathsf{T}}|$
with the clustering number provided by the APC. The procedure of global node
selection is summarized in Algorithm 1. We will give a more detailed
discussion about the reliability of SPR and APC in Section IV-B.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 4: The _Superpixels_ (top left) generated by over-segmenting the input
images at different scales with their _SPR_ (top right) computed by mLab
features and their _Areas_ (bottom). From left to right, the number of
superpixels in the image decreases gradually. The change of superpixels has
less effect on SPR than on areas in the same image.

(a)

(b)

Figure 5: Illustration of the similarity $S_{i,j}$ between two superpixels
$s_{i}$ and $s_{j}$. (a) Visualization results of mLab features. (b) Euclidean
distance along the probability density function of the mLab feature histogram.

###  III-D NOLRR-graph Construction

To capture long-range grouping cues, we utilize Eq. (1) to approximate each
global node from others in mLab features. As an alternative, we choose low-
rank minimization to approximate each global node from others in mLab
features. LRR is a significant method for segmenting data that are generated
from a subspace union [20, 33]. Both SSC and LRR utilize the idea of
expressing each sample as a linear combination of the remaining. So, it solves
the following problem:

$\mathop{\min}_{\textbf{\emph{C}}}{\dfrac{\lambda_{1}}{2}}{\|\textbf{\emph{F}}-\textbf{\emph{Y}}\textbf{\emph{C}}\|}_{F}^{2}+{\|\textbf{\emph{C}}\|}_{*},$
(7)

where $\textbf{\emph{C}}\in{\mathbb{R}}^{N\times N}$ is the coefficient matrix
of a representation of $\textbf{\emph{Y}}\in{\mathbb{R}}^{n\times N}$ over
itself. Typically, Y is chosen as the F itself. $\lambda_{1}$ is a tunable
parameters which can be set according to the properties of norms.
${\|\textbf{\emph{C}}\|}_{*}$ is the nuclear norm of matrix.
$\|\cdot\|_{F}^{2}$ represents the squared Frobenius norm.

However, solving LRR is a challenge in terms of time complexity and memory
cost. To remedy this issue, one potential way to solve this problem is an
online manner namely noise-free online LRR (NOLRR). The matrix
${\|\textbf{\emph{C}}\|}_{*}$ can be denoted:

$\|\textbf{\emph{C}}\|_{*}=\mathop{\min}_{\textbf{\emph{U}},\textbf{\emph{V}},\textbf{\emph{C}}=\textbf{\emph{U}}\textbf{\emph{V}}^{\mathsf{T}}}\dfrac{1}{2}\Big{(}\|\textbf{\emph{U}}\|_{F}^{2}+\|\textbf{\emph{V}}\|_{F}^{2}\Big{)},$
(8)

where $\textbf{\emph{U}}\in{\mathbb{R}}^{N\times d}$ and
$\textbf{\emph{V}}\in{\mathbb{R}}^{N\times d}$. To decouple the rows of U, we
use an auxiliary matrix $\textbf{\emph{D}}=\textbf{\emph{Y}}\textbf{\emph{U}}$
and approximate the term F with
$\textbf{\emph{D}}\textbf{\emph{V}}^{\mathsf{T}}$. The matrix D is regarded as
a basis dictionary of the data, V with being the coefficients. So we obtain a
_regularized_ version of LRR and solve the following problem:

$\begin{split}\mathop{\min}_{\textbf{\emph{D,U,V}}}{\dfrac{\lambda_{1}}{2}}{\|\textbf{\emph{F}}-\textbf{\emph{D}}\textbf{\emph{V}}^{\mathsf{T}}\|}_{F}^{2}+\dfrac{1}{2}\Big{(}\|\textbf{\emph{U}}\|_{F}^{2}&+\|\textbf{\emph{V}}\|_{F}^{2}\Big{)}\\\
&+{\dfrac{\lambda_{2}}{2}}\|\textbf{\emph{D}}-\textbf{\emph{Y}}\textbf{\emph{U}}\|_{F}^{2}.\end{split}$
(9)

Let $\textbf{\emph{f}}_{i}$, $\textbf{\emph{y}}_{i}$, $\textbf{\emph{u}}_{i}$,
and $\textbf{\emph{v}}_{i}$, be the $i$-th column of matrices F, Y,
$\textbf{\emph{U}}^{\mathsf{T}}$, and $\textbf{\emph{V}}^{\mathsf{T}}$,
respectively. Solving Eq. (9) indeed minimizes the following empirical cost
function,

$f_{N}(\textbf{\emph{D}})\triangleq\frac{1}{N}\sum\limits_{i=1}^{N}{\ell_{1}}(\textbf{\emph{f}}_{i},\textbf{\emph{D}})+\frac{1}{N}\sum\limits_{i=1}^{N}{\ell_{2}}(\textbf{\emph{y}}_{i},\textbf{\emph{D}}),$
(10)

where the loss function ${\ell_{1}}$, ${\ell_{2}}$ are defined as

${\ell_{1}}(\textbf{\emph{f}}_{i},\textbf{\emph{D}})=\mathop{\min}_{\textbf{\emph{v}}}{\hat{\ell_{1}}}(\textbf{\emph{f}}_{i},\textbf{\emph{D}},\textbf{\emph{v}}),$
(11)
${\ell_{2}}(\textbf{\emph{y}}_{i},\textbf{\emph{D}})=\mathop{\min}_{\textbf{\emph{u}}}{\hat{\ell_{2}}}(\textbf{\emph{y}}_{i},\textbf{\emph{D}},\textbf{\emph{M}}_{i-1},\textbf{\emph{u}}),$
(12)

that is

${\hat{\ell_{1}}}(\textbf{\emph{f}}_{i},\textbf{\emph{D}},\textbf{\emph{v}})\triangleq\frac{\lambda_{1}}{2}{\|\textbf{\emph{f}}_{i}-\textbf{\emph{D}}\textbf{\emph{v}}\|}_{2}^{2}+\frac{1}{2}{\|\textbf{\emph{v}}\|}_{2}^{2},$
(13)
${\hat{\ell_{2}}}(\textbf{\emph{y}}_{i},\textbf{\emph{D}},\textbf{\emph{M}}_{i-1},\textbf{\emph{u}})\\!\triangleq\\!\frac{1}{2}{\|\textbf{\emph{u}}\|}_{2}^{2}+\frac{\lambda_{2}}{2}{\|\textbf{\emph{D}}-\textbf{\emph{M}}_{i-1}-\textbf{\emph{y}}_{i}\textbf{\emph{u}}^{\mathsf{T}}\|}_{F}^{2},$
(14)

where

$\textbf{\emph{M}}_{i-1}=\sum\limits_{j=1}^{i-1}\textbf{\emph{y}}_{j}\textbf{\emph{u}}_{j}^{\mathsf{T}}.$
(15)

In the $t$-th time instance, the objective function for updating the basis D
is defined as

$g_{t}(\textbf{\emph{D}})\\!\triangleq\\!\frac{1}{t}\Big{(}\\!\sum\limits_{i=1}^{t}\\!{\hat{\ell_{1}}}(\textbf{\emph{f}}_{i},\textbf{\emph{D}},\textbf{\emph{v}}_{i})+\\!\sum\limits_{i=1}^{t}\\!\frac{1}{2}{\|\textbf{\emph{u}}_{i}\|}_{2}^{2}+\frac{\lambda_{2}}{2}{\|\textbf{\emph{D}}-\textbf{\emph{M}}_{t}\|}_{F}^{2}\Big{)}.$
(16)

This is a surrogate function of the empirical cost function
$f_{t}(\textbf{\emph{D}})$ defined in Eq. (10), namely it provides an upper
bound for $f_{t}(\textbf{\emph{D}}):g_{t}(\textbf{\emph{D}})\geqslant
f_{t}(\textbf{\emph{D}})$. Expanding the first term, $\textbf{\emph{D}}_{t}$
is given by:

$\begin{split}\textbf{\emph{D}}_{t}=\mathop{\arg\min}_{\textbf{\emph{D}}}{\dfrac{1}{t}}\Big{[}\dfrac{1}{2}\mathop{\mathrm{Tr}}&(\textbf{\emph{D}}^{\mathsf{T}}\textbf{\emph{D}}(\lambda_{1}\textbf{\emph{A}}_{t}+\lambda_{2}\textbf{\emph{I}}_{d})\\\
&-\mathop{\mathrm{Tr}}(\textbf{\emph{D}}^{\mathsf{T}}(\lambda_{1}\textbf{\emph{B}}_{t}+\lambda_{2}\textbf{\emph{M}}_{t}))\Big{]},\end{split}$
(17)

where
$\textbf{\emph{A}}_{t}=\sum_{i=1}^{t}\textbf{\emph{v}}_{i}\textbf{\emph{v}}_{i}^{\mathsf{T}}$
and
$\textbf{\emph{B}}_{t}=\sum_{i=1}^{t}\textbf{\emph{f}}_{i}\textbf{\emph{v}}_{i}^{\mathsf{T}}$.
In practice, a block coordinate descent approach [21] can be applied to
minimize over D.

Usually, a potential way to construct a graph is collecting all the
$\textbf{\emph{u}}_{i}$ and $\textbf{\emph{v}}_{i}$ to compute the
representation matrix
$\textbf{\emph{C}}=\textbf{\emph{U}}\textbf{\emph{V}}^{\mathsf{T}}$. So the
NOLRR-graph is built as
$\emph{{W}}=(|\textbf{\emph{C}}|+|{\textbf{\emph{C}}}|^{\mathsf{T}})/2$. The
above NOLRR reduces the memory cost from _O_($N^{2}$) to _O_($nd$) with $d$
being estimated rank ($d<n\ll N$) and makes it an appealing solution for large
scale data. The time complexity of the update on accumulation matrices is
_O_($nd$) and that of $\textbf{\emph{D}}_{t}$ is _O_($nd^{2}$). The procedure
of NOLRR-graph construction is summarized in Algorithm 2. The NOLRR-graph can
improve the performance of natural image segmentation as explained in Section
IV-B.

Algorithm 1 Global node selection

0: Feature $\textbf{\emph{F}}\in\mathbb{R}^{n\times N}$, $e$, $g$, $\psi=3$,
$\tau=10^{-6}$ ;

1: Compute $\textbf{\emph{c}}_{j}^{*}$ from
OMP$(\textbf{\emph{F}}_{-j},\textbf{\emph{f}}_{j})$;

2: Set
$\textbf{\emph{C}}^{*}=[\textbf{\emph{c}}_{1}^{*},...,\textbf{\emph{c}}_{N}^{*}]$
and
$\textbf{\emph{M}}_{sp}=|\textbf{\emph{C}}^{*}|+|{\textbf{\emph{C}}^{*}}^{\mathsf{T}}|$;

3: Compute classification from $\textbf{\emph{M}}_{sp}$ by spectral clustering
with the clustering number provided by the APC.

3: Global nodes.

Algorithm 2 NOLRR-graph construction

0: Feature $\textbf{\emph{F}}\in\mathbb{R}^{n\times N}$; parameter $d$;

1: Initialize $\lambda_{1}=1$, $\lambda_{2}^{ini}=1/\sqrt{n}$, basis
dictionary $\textbf{\emph{D}}_{0}\in\mathbb{R}^{n\times d}$, zero matrices
$\textbf{\emph{A}}_{0}\in\mathbb{R}^{d\times d}$,
$\textbf{\emph{B}}_{0}\in\mathbb{R}^{n\times d}$,
$\textbf{\emph{M}}_{0}\in\mathbb{R}^{n\times d}$,
$\textbf{\emph{U}}\in\mathbb{R}^{N\times d}$,
$\textbf{\emph{V}}\in\mathbb{R}^{N\times d}$.

2: for $t=1$ to $N$ do

3: Access the $t$-th atom $\textbf{\emph{f}}_{t}$ and compute
$\lambda_{2}=\sqrt{t}\times\lambda_{2}^{ini}$;

4: Compute the coefficients $\textbf{\emph{v}}_{t}$ and
$\textbf{\emph{u}}_{t}$ using Eq. (11) and Eq. (12), respectively;

5: Update the accumulation matrices
$\textbf{\emph{A}}_{t}\leftarrow\textbf{\emph{A}}_{t-1}+\textbf{\emph{v}}_{t}\textbf{\emph{v}}_{t}^{\mathsf{T}}$,
$\textbf{\emph{B}}_{t}\leftarrow\textbf{\emph{B}}_{t-1}+\textbf{\emph{f}}_{t}\textbf{\emph{v}}_{t}^{\mathsf{T}}$,
$\textbf{\emph{M}}_{t}\leftarrow\textbf{\emph{M}}_{t-1}+\textbf{\emph{f}}_{t}\textbf{\emph{v}}_{t}^{\mathsf{T}}$;

6: Update the basis dictionary using Eq. (17);

7: Update the matrices
$\textbf{\emph{U}}_{t,:}\leftarrow\textbf{\emph{u}}_{t}$,
$\textbf{\emph{V}}_{t,:}\leftarrow\textbf{\emph{v}}_{t}$;

8: end for

9: Compute the matrix
$\textbf{\emph{C}}=\textbf{\emph{U}}\textbf{\emph{V}}^{\mathsf{T}}$ and the
NOLRR-graph
$\emph{{W}}=(|\textbf{\emph{C}}|+|{\textbf{\emph{C}}}|^{\mathsf{T}})/2$.

9: NOLRR-graph W.

##  IV EXPERIMENTS AND ANALYSIS

To verify the performance of the proposed AFA-graph, we first introduce the
experimental setup, and then show the results of our approach and its
variations. Moreover, the results of our method are presented compared with
the state-of-the-art methods on different datasets. Finally, we show time
complexity analysis of our AFA-graph.

###  IV-A Experimental Setup

####  IV-A1 Databases

All experiments are carried out on the following publicly available databases:
Berkeley Segmentation Database (BSD) [34] and Microsoft Research Cambridge
(MSRC) database [35], Stanford Background Dataset (SBD) [36], and PASCAL
visual object classes 2012 (VOC) dataset [37].

  * •

BSD300: The BSD300 includes 300 natural images and the ground truth data (each
one has about 5 human annotations). Each image has a fixed size of
481$\times$321 pixels.

  * •

BSD500: As an improved version of BSD300 dataset, the BSD500 contains 500
natural images. Each image is annotated by 5 different people on average.

  * •

MSRC: The MSRC contains 591 images and 23 object classes with accurate pixel-
wise labeled images. The performance is evaluated using the clean ground-truth
object instance labeling of [38].

  * •

SBD: The SBD contains 715 images of urban and rural scenes with 8 classes.
Each image is approximately 240$\times$320 pixels and contains at least one
foreground object. The ‘layers’, ‘regions’, and ‘surfaces’ are all used as
groundtruth.

  * •

PASCAL VOC: The segmentation challenge of PASCAL VOC12 includes 2913 images
(1416 images in train set and 1449 images in val set) with annotated objects
of 20 categories. Following the standard setting, we use val set to test the
final performance.

####  IV-A2 Metrics

To evaluate our method, there are four standard measurements: the
probabilistic rand index (PRI) [39], the variation of information (VoI) [40],
the global consistency error (GCE) [34], and the boundary displacement error
(BDE) [41]. The closer the segmentation result is to the ground truth, the
higher the PRI is, and the smaller the other three measures (VoI, GCE, and
BDE) are. All experiments are conducted under the PC condition of 3.40GHz of
Intel Xeon E5-2643 v4 processor, 64G RAM, Ubuntu 16.04 OS and Matlab 2018a.

###  IV-B Performance analysis for framework

####  IV-B1 Influence of parameter $\alpha$ in IKDE

To analyze the robustness of our AFA-graph, we first explore the influence of
exponential factor $\alpha$ in IKDE. As shown in Figs. 6(a)-(d), we report the
indexes of PRI, VoI, GCE, and BDE for different $\alpha$ under a range of
corruptions on BSD300 dataset. From Fig. 6, we can find that the best
performance is obtained when parameter $\alpha=1$. The index of PRI is highest
and other three indexes are closed to the best results.

(a)

(b)

(c)

(d)

Figure 6: Examine the influence of $\alpha$ in IKDE on BSD300 dataset. To
accurately describe the influence of $\alpha$ on performance, the values of
four indexes retain four decimal places. (a) PRI. (b) VoI. (c) GCE. (d) BDE.

####  IV-B2 Influence of parameters $e$ and $g$ in APC

To analyze the robustness of our AFA-graph, we then explore the influence of
parameters $e$ and $g$ in APC. We report the results for different $e$ and $g$
under a range of corruptions on BSD300 dataset as shown in Figs. 7(a)-(d).
From the results, we can find that the best performance is obtained when
parameter $e=3$ and $g=5$. Our method has good robustness to the variety of
parameters $e$ and $g$.

(a)

(b)

(c)

(d)

Figure 7: Examine the influence of $e$ and $g$ in APC on BSD300 dataset. (a)
PRI. (b) VoI. (c) GCE. (d) BDE. Our method has good robustness to the variety
of parameter.

####  IV-B3 Influence of parameter $d$ in NOLRR

To analyze the robustness of our AFA-graph, we also explore the influence of
the selected rank $d$ in the proposed NOLRR (Algorithm 2). In Figs. 8(a)-(d),
our proposed NOLRR also has good robustness to the variety of parameter. The
index of PRI is highest and other three indexes are closed to the best
results. So, the best performance is obtained when parameter $d=50$.

(a)

(b)

(c)

(d)

Figure 8: Examine the influence of $d$ in NOLRR on BSD300 dataset. To
accurately describe the influence of $d$ on performance, the values of four
indexes retain four decimal places. (a) PRI. (b) VoI. (c) GCE. (d) BDE. Our
method has good robustness to the variety of parameter.

####  IV-B4 Denoise methods

As suggested, we have conducted experiments to explore the influence of noise
to accuracy. The results on BSD300 are listed in Table I. The Gaussian means
that we perform Gaussian filtering on images or features as done by SFFCM
[16]. The size of filter is [5, 5], and the value for sigma is set as 1. The
Bilateral means that we perform shiftable bilateral filtering on images or
features as done by CCP [42]. The size of filter is [5, 5], and the width of
both spatial and range Gaussian are set as 5. For IKDE, the values of $\alpha$
is an exponential factor is set to 1. We can observe that IKDE can achieve the
best results on all metrics. In Fig. 9, the results also show that the
performance of filtering on images is worse than filtering on features. In
this case, filtering on images may influence the neighborhood topology between
pixels which is the core of a constructed affinity graph.

TABLE I: Quantitative results of the proposed framework with different denoising methods on BSD300 dataset. We perform Gaussian, bilateral, and our IKDE filtering on images or features. Methods | Images | Features | PRI $\uparrow$ | VoI $\downarrow$ | GCE $\downarrow$ | BDE $\downarrow$
---|---|---|---|---|---|---
Gaussian | $\surd$ |  | 0.81 | 2.22 | 0.24 | 18.56
Gaussian |  | $\surd$ | 0.84 | 1.76 | 0.20 | 15.71
Bilateral | $\surd$ |  | 0.81 | 2.20 | 0.24 | 19.17
Bilateral |  | $\surd$ | 0.84 | 1.68 | 0.18 | 15.26
IKDE | $\surd$ |  | 0.81 | 2.22 | 0.25 | 19.17
IKDE |  | $\surd$ | 0.84 | 1.67 | 0.19 | 14.72
TABLE II: Quantitative results of the proposed NOLRR-graph with different basic graphs using mLab features on BSD300 dataset. A-graph means adjacency-graph. Methods | IKDE | PRI $\uparrow$ | VoI $\downarrow$ | GCE $\downarrow$ | BDE $\downarrow$
---|---|---|---|---|---
A-graph |  | 0.83 | 1.75 | 0.18 | 15.02
A-graph | $\surd$ | 0.83 | 1.75 | 0.18 | 14.94
NOLRR-graph |  | 0.81 | 2.32 | 0.25 | 17.57
NOLRR-graph | $\surd$ | 0.81 | 2.34 | 0.24 | 17.42
A- + NOLRR-graph |  | 0.84 | 1.68 | 0.19 | 14.74
A- + NOLRR-graph | $\surd$ | 0.84 | 1.67 | 0.19 | 14.72

Figure 9: Visual comparison on BSD300 dataset obtained by our AFA-graph. From
left to right, input images, the results of AFA-graph w/o IKDE, IKDE on images
and IKDE on features are presented. The results of AFA-graph with IKDE on
features are much better, in particular often more accurate.

####  IV-B5 Graphs

To verify the proposed AFA-graph with other graph construction, we list the
performance of different graphs in Table II. The setting of scale $k$ is the
same as adjacency-graph [3]. To achieve the optimal performance of these
graphs, we follow the procedure stated in [3] and [5] to manually select the
best group in Tcut [3] ranking from 1 to 40. In adjacency-graph, the standard
deviation of the Gaussian kernel function is defined as 20. We construct the
NOLRR-graph, and the parameter $d$ is set to 50. Our method is highly
efficient and adaptive to the combination of local graph (adjacency-graph) and
global graph (NOLRR-graph). It achieves the best performances in comparison
with the adjacency-graph and NOLRR-graph. As shown in Fig. 10, adjacency-graph
only considers the local structure easily leading to wrong segmentation when
the objects cover a large part of images. Our proposed NOLRR-graph often
produces a dense graph, which cannot satisfy the sparsity of the desired
graph. Our AFA-graph combines different affinity graphs with assimilating the
advantages of two graphs to further improve the segmentation performance.

Figure 10: Visual comparison on BSD300 dataset obtained by different affinity
graphs. From left to right, input superpixels, A-graph with the segmentation
results, NOLRR-graph with the results, and our AFA-graph (A- + NOLRR-graph)
with the results are presented. Our AFA-graph combines different affinity
graphs with assimilating the advantages of two graphs to further improve the
segmentation performance.

####  IV-B6 Different modules

To see how AFA-graph is affected by different modules, we report the scores of
combinations of different modules using in the baseline. The baseline easily
combines adjacency-graph and NOLRR-graph by element-wise sum operation. The
Area means the node selection method from GL-graph[5]. The SPR and APC are
utilized to select global nodes. Especially if the baseline does not select
APC, we will use _k_ -means with $k=2$ for fair comparison. The results of
different modules using in the baseline are shown in Table III. The results
show that the segmentation performance of APC with SPR is better than area and
_k_ -means. Therefore, the SPR can better represent superpixels compared with
the area. Obviously, our method is suitable for the selection of global nodes
when we know nothing about the feature distribution of the superpixels
beforehand.

TABLE III: Quantitative comparison for different methods using in our AFA-graph on BSD300 dataset. The baseline easily combines adjacency-graph and NOLRR-graph by element-wise sum operation. Methods | PRI $\uparrow$ | VoI $\downarrow$ | GCE $\downarrow$ | BDE $\downarrow$
---|---|---|---|---
Baseline | 0.80 | 2.46 | 0.26 | 15.96
Baseline+IKDE | 0.80 | 2.40 | 0.27 | 15.60
Baseline+IKDE+Area | 0.84 | 1.69 | 0.21 | 14.95
Baseline+IKDE+_k_ -means | 0.84 | 1.69 | 0.19 | 15.01
Baseline+IKDE+_k_ -means+SPR | 0.84 | 1.68 | 0.19 | 14.94
Baseline+IKDE+APC+SPR | 0.84 | 1.67 | 0.19 | 14.72
TABLE IV: Quantitative results of the proposed framework with state-of-the-art approaches on BSD300 dataset. We directly take their evaluations reported in publications for fair comparison. The ’C’ in class means clustering-based methods. The ’G’ in category means graph-based methods. Methods | Class | $\textrm{PRI}\uparrow$ | $\textrm{VoI}\downarrow$ | $\textrm{GCE}\downarrow$ | $\textrm{BDE}\downarrow$
---|---|---|---|---|---
FCM [16] | C | 0.74 | 2.87 | 0.41 | 13.78
FRFCM [13] | C | 0.75 | 2.62 | 0.36 | 12.87
MS [7] | C | 0.76 | 2.48 | 0.26 | 9.70
SFFCM [16] | C | 0.78 | 2.02 | 0.26 | 12.90
FCR [8] | C | 0.79 | 2.30 | 0.21 | 8.99
H_+R_Better [2] | C | 0.81 | 1.83 | 0.21 | 12.16
Corr-Cluster [9] | C | 0.81 | 1.83 | – | 11.19
HO-CC [10] | C | 0.81 | 1.74 | – | 10.38
FH [23] | G | 0.71 | 3.39 | 0.17 | 16.67
Ncut [22] | G | 0.72 | 2.91 | 0.22 | 17.15
MNCut [25] | G | 0.76 | 2.47 | 0.19 | 15.10
LFPA [27] | G | 0.81 | 1.85 | 0.18 | 12.21
SAS [3] | G | 0.83 | 1.68 | 0.18 | 11.29
$\ell_{0}$-Graph [4] | G | 0.84 | 1.99 | 0.23 | 11.19
GL-Graph [5] | G | 0.84 | 1.80 | 0.19 | 10.66
AASP-Graph [6] | G | 0.84 | 1.65 | 0.17 | 14.64
AFA-Graph (Gaussian) | G | 0.84 | 1.76 | 0.20 | 15.71
AFA-Graph (Bilateral) | G | 0.84 | 1.68 | 0.18 | 15.26
AFA-Graph (IKDE) | G | 0.84 | 1.65 | 0.18 | 15.00
TABLE V: Quantitative results of the proposed framework with state-of-the-art approaches on BSD500 dataset. We directly take their evaluations reported in publications for fair comparison. Methods | Class | $\textrm{PRI}\uparrow$ | $\textrm{VoI}\downarrow$ | $\textrm{GCE}\downarrow$ | $\textrm{BDE}\downarrow$
---|---|---|---|---|---
DSFCM [11] | C | 0.74 | 2.90 | 0.41 | –
FCM [16] | C | 0.74 | 2.88 | 0.40 | 13.48
MSFCM [12] | C | 0.74 | 2.85 | 0.40 | –
FRFCM [13] | C | 0.76 | 2.67 | 0.37 | 12.35
HS [43] | C | 0.76 | 2.39 | 0.26 | 14.03
HO-CC [10] | C | 0.83 | 1.79 | – | 9.77
AFC [14] | C | 0.76 | 2.05 | 0.22 | 12.95
RSFFC [15] | C | 0.78 | 2.12 | 0.28 | –
SFFCM [16] | C | 0.78 | 2.06 | 0.26 | 12.80
MS [7] | C | 0.79 | 1.85 | 0.26 | –
MNCut [25] | G | 0.76 | 2.33 | – | –
FH [23] | G | 0.79 | 2.16 | – | –
SAS [3] | G | 0.80 | 1.92 | – | –
RAG [26] | G | 0.81 | 1.98 | – | –
$\ell_{0}$-Graph [4] | G | 0.84 | 2.08 | 0.23 | 11.07
AASP-Graph [6] | G | 0.84 | 1.71 | 0.18 | 13.78
AFA-Graph (Gaussian) | G | 0.83 | 1.80 | 0.20 | 15.18
AFA-Graph (Bilateral) | G | 0.84 | 1.72 | 0.19 | 14.41
AFA-Graph (IKDE) | G | 0.84 | 1.70 | 0.19 | 14.14

###  IV-C Comparison with state-of-the-art methods

We also report quantitative comparisons with the state-of-the-art methods. The
comparison results on BSD300, BSD500, MSRC, SBD, and PASCAL VOC datasets are
shown in Table IV to Table VIII, respectively. We directly take their
evaluations reported in publications for fair comparison. It can be noticed
that our AFA-graph has a better performance compared with the state-of-the-art
methods. We attribute this to adaptive combination of different graphs, which
helps to accurately separate the foreground and background.

Our method follows a similar, but not identical strategy as the SAS,
$\ell_{0}$-graph, and GL-graph. Instead of using only adjacent neighborhoods
of superpixels in SAS and $\ell_{0}$ affinity graph of superpixels in
$\ell_{0}$-graph algorithm, we build an AFA-graph by combining NOLRR-graph and
adjacency-graph, which allows the constructed graph to have the
characteristics of a long-range neighborhood topology, with the sparsity and
high discriminating power. The main differences between GL-graph and our
method are global node selection and graph construction. In GL-graph, the
superpixels are simply divided into three parts: small, medium, and large
sized according to their area. For small and large sets, all superpixels
connect to their adjacent neighbors, while for medium set, the superpixels are
used to build a $\ell_{0}$-graph. However, according to the analysis of SPR
and area revealed in Section III-C, the area does not accurately reflect the
distribution of global nodes in superpixels. In our method, the adjacency-
graph of all superpixels is updated by the NOLRR-graph, which is built through
NOLRR with the global nodes selected by the SPR and APC.

Figure 11 shows various segmentation results obtained with SAS,
$\ell_{0}$-graph, GL-graph, and our AFA-graph. The results of other three
methods are the best results reported by the authors. It can be seen that our
method can achieve a desirable result with less tuning for the group $k_{T}$
in Tcut (for ostrich, the group $k_{T}=2$), because the method takes into
account the global information exactly. Especially, compared with the other
three methods, our method obtains an accurate segmentation even in the
difficult cases where: i) the detected object is highly textured, and the
background may be highly unstructured, such as coral, surfer, and skier; ii)
objects of the same type appear in a large and fractured area of the image,
such as ostrich, zebras, and racecars. However, the BDE of our method is
unsatisfied. As shown in Fig. 12, our method can not obtain accurate and clear
boundaries, when the detected object is too tiny and its texture is easily to
be confused with background. The main reason is that our AFA-graph only uses
pixel color information, which fails to capture enough contour and texture
cues of segmenting images.

Figure 11: Visual comparison on BSD300 dataset obtained with the adjacency-graph [3] , $\ell_{0}$-graph [4], GL-graph [4], and our AFA-graph. Two columns of the comparison results are shown here. From left to right, input images, the results of the SAS, $\ell_{0}$-graph, GL-graph, and AFA-graph are presented. The results of AFA-graph are visually better, in particular often more accurate. TABLE VI: Quantitative results of the proposed framework with state-of-the-art approaches on MSRC dataset. We directly take their evaluations reported in publications for fair comparison. Methods | Class | $\textrm{PRI}\uparrow$ | $\textrm{VoI}\downarrow$ | $\textrm{GCE}\downarrow$ | $\textrm{BDE}\downarrow$
---|---|---|---|---|---
MSFCM [12] | C | 0.68 | 1.80 | 0.30 | –
DSFCM [11] | C | 0.69 | 1.91 | 0.32 | –
FCM [16] | C | 0.70 | 1.93 | 0.32 | 12.67
FRFCM [13] | C | 0.71 | 1.79 | 0.30 | 12.23
SFFCM [16] | C | 0.73 | 1.58 | 0.25 | 12.49
RSFFC [15] | C | 0.75 | 1.51 | 0.24 | –
Corr-Cluster [9] | C | 0.77 | 1.65 | – | 9.19
HO-CC [10] | C | 0.78 | 1.59 | – | 9.04
Supervised-NCut [9] | G | 0.60 | 3.10 | – | 13.50
MNCut [25] | G | 0.63 | 2.77 | – | 11.94
SAS [3] | G | 0.80 | 1.39 | – | –
$\ell_{0}$-Graph [4] | G | 0.82 | 1.29 | 0.15 | 9.36
AASP-Graph [6] | G | 0.82 | 1.32 | 0.14 | 13.38
AFA-Graph (Gaussian) | G | 0.80 | 1.38 | 0.15 | 15.85
AFA-Graph (Bilateral) | G | 0.81 | 1.32 | 0.14 | 13.92
AFA-Graph (IKDE) | G | 0.82 | 1.29 | 0.14 | 13.37

###  IV-D Time complexity analysis

Our method includes steps of over-segmentation, feature extraction, global
node selection, NOLRR-graph construction, and Tcut. The time complexity of OMP
[17] global node selection and NOLRR-graph construction are analyzed in
Section III-C and Section III-D, respectively. The time complexity of Tcut is
$O(k_{T}|N|^{3/2})$ with a small constant. Using an aforementioned computer,
our method takes totally 7.61 seconds to segment an image with size
481$\times$321 from BSD300 on average, where 5.11 seconds for generating
superpixels, 0.56 seconds for global node selection, 1.12 seconds for building
adaptive affinity graph, as well as only 0.82 seconds for the bipartite graph
construction and partitioning with Tcut. The average running times (ARTs) of
methods are obtained on aforementioned computer. The ART of the proposed AFA-
graph is close to SAS and slight faster than GL-graph and our previous AASP-
graph. Note that the AFA-graph is more efficient than GL-graph and AASP-graph
in regard to adaptive node selection and their graph construction. In
contrast, $\ell_{0}$-graph, MNcut, GL-graph, and Ncut usually take more than
20, 30, 100, and 150 seconds, respectively. The main reason is that extracting
different features cost too much time.

In summary, there are four main reasons why our AFA-graph has high
performance: i) we propose IKDE to estimate the mLab of natural images to
reduce the noise; ii) the combination of SPR and APC can select the global
nodes, accurately mining the feature distribution of superpixels; iii) the
NOLRR-graph is proposed to reduce time complexity while improving segmentation
accuracy; iv) our AFA-graph combines adjacency-graph and NOLRR-graph with
assimilating the advantages of two graphs.

TABLE VII: Quantitative results of the proposed framework with state-of-the-art approaches on SBD dataset. Methods | Class | $\textrm{PRI}\uparrow$ | $\textrm{VoI}\downarrow$ | $\textrm{GCE}\downarrow$ | $\textrm{BDE}\downarrow$
---|---|---|---|---|---
SFFCM [16] | C | 0.66 | 1.89 | 0.22 | 16.44
$\ell_{0}$-Graph [4] | G | 0.80 | 1.97 | 0.20 | 9.96
AASP-Graph [6] | G | 0.81 | 1.78 | 0.17 | 10.61
SAS [3] | G | 0.81 | 1.78 | 0.17 | 10.52
AFA-Graph (Gaussian) | G | 0.80 | 1.78 | 0.20 | 11.11
AFA-Graph (Bilateral) | G | 0.81 | 1.75 | 0.18 | 10.67
AFA-Graph (IKDE) | G | 0.81 | 1.75 | 0.18 | 10.33
TABLE VIII: Quantitative results of the proposed framework with state-of-the-art approaches on PASCAL VOC dataset. Methods | Class | $\textrm{PRI}\uparrow$ | $\textrm{VoI}\downarrow$ | $\textrm{GCE}\downarrow$ | $\textrm{BDE}\downarrow$
---|---|---|---|---|---
SFFCM [16] | C | 0.61 | 1.38 | 0.21 | 37.69
AASP-Graph [6] | G | 0.58 | 1.83 | 0.18 | 41.94
SAS [3] | G | 0.61 | 1.65 | 0.17 | 39.13
$\ell_{0}$-Graph [4] | G | 0.61 | 1.59 | 0.17 | 38.73
AFA-Graph (Gaussian) | G | 0.61 | 1.61 | 0.17 | 35.42
AFA-Graph (Bilateral) | G | 0.62 | 1.56 | 0.16 | 34.14
AFA-Graph (IKDE) | G | 0.62 | 1.55 | 0.16 | 34.47
Figure 12: False results by AFA-graph. Our AFA-graph only uses pixel color
information, which fails to capture enough contour and texture cues of
segmenting images.

##  V CONCLUSION

In this paper, an AFA-graph is proposed to obtain good results for natural
image segmentation. The method uses superpixels of different scales as
segmentation primitive. To reduce the noise, we then introduce an IKDE method
to estimate the mLab features of superpixels. Besides, the SPR and APC are
applied to select global sets, which are used to build a NOLRR-graph to update
an adjacency-graph of superpixels at each scale. Experimental results show the
good performance and high efficiency of the proposed AFA-graph. We also
compare our AFA-graph with the state-of-the-art methods, and our AFA-graph
achieves competitive results on five benchmark datasets namely BSD300, BSD500,
MSRC, SBD, and PASCAL VOC.

In the future, we plan to extend the proposed framework to include more
discriminating feature such as texture, shape, and priors to obtain better
results. And we will explore the combination of graph and deep unsupervised
learning to improve image segmentation performance.

## References

  * [1] H. Zhu, F. Meng, J. Cai, and S. Lu, “Beyond pixels: A comprehensive survey from bottom-up to semantic image segmentation and cosegmentation,” _Journal of Visual Communication and Image Representation_ , vol. 34, pp. 12–27, 2016.
  * [2] K. Li, W. Tao, X. Liu, and L. Liu, “Iterative image segmentation with feature driven heuristic four-color labeling,” _Pattern Recognition_ , vol. 76, pp. 69–79, 2018.
  * [3] Z. Li, X. Wu, and S. Chang, “Segmentation using superpixels: A bipartite graph partitioning approach,” in _IEEE Conference on Computer Vision and Pattern Recognition_ , 2012, pp. 789–796.
  * [4] X. Wang, H. Li, C. Bichot, S. Masnou, and L. Chen, “A graph-cut approach to image segmentation using an affinity graph based on $\ell_{0}$-sparse representation of features,” in _IEEE International Conference on Image Processing_ , 2013, pp. 4019–4023.
  * [5] X. Wang, Y. Tang, S. Masnou, and L. Chen, “A global/local affinity graph for image segmentation,” _IEEE Transactions on Image Processing_ , vol. 24, no. 4, pp. 1399–1411, 2015.
  * [6] Y. Zhang, H. Zhang, Y. Guo, K. Lin, and J. He, “An adaptive affinity graph with subspace pursuit for natural image segmentation,” in _IEEE International Conference on Multimedia and Expo_ , 2019, pp. 802–807.
  * [7] D. Comaniciu and P. Meer, “Mean shift: A robust approach toward feature space analysis,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 24, no. 5, pp. 603–619, 2002.
  * [8] M. Mignotte, “Segmentation by fusion of histogram-based$k$-means clusters in different color spaces,” _IEEE Transactions on Image Processing_ , vol. 17, no. 5, pp. 780–787, 2008.
  * [9] S. Kim, S. Nowozin, P. Kohli, and C.-D. Yoo, “Task-specific image partitioning.” _IEEE Transactions on Image Processing_ , vol. 22, no. 2, pp. 488–500, 2013.
  * [10] S. Kim, C.-D. Yoo, S. Nowozin, and P. Kohli, “Image segmentation using higher-order correlation clustering,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 36, no. 9, pp. 1761–1774, 2014.
  * [11] Y. Zhang, X. Bai, R. Fan, and Z. Wang, “Deviation-sparse fuzzy c-means with neighbor information constraint,” _IEEE Transactions on Fuzzy Systems_ , vol. 27, no. 1, pp. 185–199, 2019.
  * [12] S. Zhou, D. Li, Z. Zhang, and R. Ping, “A new membership scaling fuzzy c-means clustering algorithm,” _IEEE Transactions on Fuzzy Systems_ , 2020.
  * [13] T. Lei, X. Jia, Y. Zhang, L. He, H. Meng, and A. K. Nandi, “Significantly fast and robust fuzzy c-means clustering algorithm based on morphological reconstruction and membership filtering,” _IEEE Transactions on Fuzzy Systems_ , vol. 26, no. 5, pp. 3027–3041, 2018.
  * [14] T. Lei, P. Liu, X. Jia, X. Zhang, H. Meng, and A. K. Nandi, “Automatic fuzzy clustering framework for image segmentation,” _IEEE Transactions on Fuzzy Systems_ , vol. 28, no. 9, pp. 2078–2092, 2020.
  * [15] X. Jia, T. Lei, X. Du, S. Liu, H. Meng, and A. K. Nandi, “Robust self-sparse fuzzy clustering for image segmentation,” _IEEE Access_ , vol. 8, pp. 146 182–146 195, 2020.
  * [16] T. Lei, X. Jia, Y. Zhang, S. Liu, H. Meng, and A.-K. Nandi, “Superpixel-based fast fuzzy c-means clustering for color image segmentation,” _IEEE Transactions on Fuzzy Systems_ , vol. 27, no. 9, pp. 1753–1766, 2019.
  * [17] C. You, D. Robinson, and R. Vidal, “Scalable sparse subspace clustering by orthogonal matching pursuit,” in _IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 3918–3927.
  * [18] J. Feng, H. Xu, and S. Yan, “Online robust PCA via stochastic optimization,” in _Advances in Neural Information Processing Systems_ , 2013, pp. 404–412.
  * [19] E. Elhamifar and R. Vidal, “Sparse subspace clustering: Algorithm, theory, and applications,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 11, pp. 2765–2781, 2013.
  * [20] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma, “Robust recovery of subspace structures by low-rank representation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 1, pp. 171–184, 2013.
  * [21] J. Shen, P. Li, and H. Xu, “Online low-rank subspace clustering by basis dictionary pursuit,” in _International Conference on Machine Learning_ , 2016, pp. 622–631.
  * [22] J. Shi and J. Malik, “Normalized cuts and image segmentation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 22, no. 8, pp. 888–905, 2000.
  * [23] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” _International Journal of Computer Vision_ , vol. 59, no. 2, pp. 167–181, 2004.
  * [24] H. Li and Z. Hong, “Iterative ensemble normalized cuts,” _Pattern Recognition_ , vol. 52, pp. 274–286, 2016.
  * [25] T. Cour, F. Benezit, and J. Shi, “Spectral segmentation with multiscale graph decomposition,” in _IEEE Conference on Computer Vision and Pattern Recognition_ , 2005, pp. 1124–1131.
  * [26] H. Cho, S. Kang, and Y. H. Kim, “Image segmentation using linked mean-shift vectors and global/local attributes,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 27, no. 10, pp. 2132–2140, 2017\.
  * [27] T. H. Kim, K. M. Lee, and U. L. Sang, “Learning full pairwise affinities for spectral segmentation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 7, pp. 1690–1703, 2013.
  * [28] J. Wang, H. Jiang, Y. Jia, X. Hua, C. Zhang, and L. Quan, “Regularized tree partitioning and its application to unsupervised image segmentation.” _IEEE Transactions on Image Processing_ , vol. 23, no. 4, pp. 1909–1922, 2014\.
  * [29] A. Saglam and N.-A. Baykan, “Sequential image segmentation based on minimum spanning tree representation,” _Pattern Recognition Letter_ , vol. 87, pp. 155–162, 2017.
  * [30] B.-J. Frey and D. Dueck, “Clustering by passing messages between data points,” _Science_ , vol. 315, no. 5814, pp. 972–976, 2007.
  * [31] B. Foster, U. Bagci, Z. Xu, B. Dey, B. Luna, W. Bishai, S. Jain, and D.-J. Mollura, “Segmentation of PET images for computer-aided functional quantification of tuberculosis in small animal models.” _IEEE Transactions on Biomedical Engineering_ , vol. 61, no. 3, pp. 711–724, 2014.
  * [32] M. Elad, _Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing_. Springer-Verlag, 2010.
  * [33] T. Lu, Z. Xiong, Y. Wan, and W. Yang, “Face hallucination via locality-constrained low-rank representation,” in _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2016, pp. 1746–1750.
  * [34] D. Martin, C. Fowlkes, D. Tal, and J. Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” in _IEEE International Conference on Computer Vision_ , 2001, pp. 416–423.
  * [35] J. Shotton, J. Winn, C. Rother, and A. Criminisi, “Textonboost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation,” in _European Conference on Computer Vision_ , 2006, pp. 1–5.
  * [36] S. Gould, R. Fulton, and D. Koller, “Decomposing a scene into geometric and semantically consistent regions,” in _IEEE International Conference on Computer Vision_ , 2009, pp. 1–8.
  * [37] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman, “The pascal visual object classes (voc) challenge,” _International Journal of Computer Vision_ , vol. 88, no. 2, pp. 303–338, 2010.
  * [38] T. Malisiewicz and A. A. Efros, “Improving spatial support for objects via multiple segmentations,” in _British Machine Vision Conference_ , 2007.
  * [39] R. Unnikrishnan, C. Pantofaru, and M. Hebert, “Toward objective evaluation of image segmentation algorithms,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 29, no. 6, pp. 929–944, 2007.
  * [40] M. Meilă, “Comparing clusterings—an information based distance,” _Journal of Multivariate Analysis_ , vol. 98, no. 5, pp. 873–895, 2007.
  * [41] J. Freixenet, X. Muñoz, D. Raba, J. Martí, and X. Cufí, “Yet another survey on image segmentation: Region and boundary information integration,” in _European Conference on Computer Vision_ , 2002, pp. 408–422.
  * [42] X. Fu, C. Wang, C. Chen, C. Wang, and C.-J. Kuo, “Robust image segmentation using contour-guided color palettes,” in _IEEE International Conference on Computer Vision_ , 2015, pp. 1618–1625.
  * [43] C. Wu, L. Zhang, H. Zhang, and H. Yan, “Superpixel based hierarchical segmentation for color image,” _IEICE TRANSACTIONS on Information and Systems_ , vol. E103-D, no. 10, pp. 2246–2249, 2020.


††thanks: These authors contributed equally to this work††thanks: These
authors contributed equally to this work††thanks: These authors contributed
equally to this work

# Electrical switching of ferro-rotational order in nano-thick 1T-TaS2
crystals

Gan Liu  Tianyu Qiu  Kuanyu He  National Laboratory of Solid State
Microstructures and Department of Physics, Nanjing University, Nanjing 210093,
China  Yizhou Liu  Department of Condensed Matter Physics, Weizmann Institute
of Science, Rehovot 7610001, Israel  Dongjing Lin  National Laboratory of
Solid State Microstructures and Department of Physics, Nanjing University,
Nanjing 210093, China  Zhen Ma  National Laboratory of Solid State
Microstructures and Department of Physics, Nanjing University, Nanjing 210093,
China  Institute for Advanced Materials, Hubei Normal University, Huangshi
435002, China  State Key Laboratory of Surface Physics and Department of
Physics, Fudan University, Shanghai 200433, China  Zhentao Huang  National
Laboratory of Solid State Microstructures and Department of Physics, Nanjing
University, Nanjing 210093, China  Wenna Tang  Jie Xu  National Laboratory of
Solid State Microstructures and Department of Physics, Nanjing University,
Nanjing 210093, China  Kenji Watanabe  Research Center for Functional
Materials, National Institute for Materials Science, 1-1 Namiki, Tsukuba
305-0044, Japan  Takashi Taniguchi  International Center for Materials
Nanoarchitectonics, National Institute for Materials Science, 1-1 Namiki,
Tsukuba 305-0044, Japan  Libo Gao  Jinsheng Wen  Jun-Ming Liu  National
Laboratory of Solid State Microstructures and Department of Physics, Nanjing
University, Nanjing 210093, China  Collaborative Innovation Center of Advanced
Microstructures, Nanjing University, Nanjing 210093, China  Binghai Yan
<EMAIL_ADDRESS>Department of Condensed Matter Physics, Weizmann
Institute of Science, Rehovot 7610001, Israel  Xiaoxiang Xi<EMAIL_ADDRESS>National Laboratory of Solid State Microstructures and Department of Physics,
Nanjing University, Nanjing 210093, China  Collaborative Innovation Center of
Advanced Microstructures, Nanjing University, Nanjing 210093, China

Abstract

Hysteretic switching of domain states is a salient character of all ferroic
materials and the foundation for their multifunctional applications. Ferro-
rotational order is emerging as a new type of ferroic order featuring
structural rotations, but its controlled switching remains elusive due to its
invariance under both time reversal and spatial inversion. Here, we
demonstrate electrical switching of ferro-rotational domain states in
nanometer-thick 1T-TaS2 crystals in its charge-density-wave phases. Cooling
from the high-symmetry phase to the ferro-rotational phase under an external
electric field induces domain state switching and domain wall formation,
realized in a simple two-terminal configuration using a volt-scale voltage.
Although the electric field does not couple with the order due to symmetry
mismatch, it drives domain wall propagation to give rise to reversible,
durable, and nonvolatile isothermal state switching at room temperature. These
results pave the path for manipulation of the ferro-rotational order and its
nanoelectronic applications.

Main

Ferroic orders arise from symmetry-breaking phase transitions, finding
applications in wide-ranging advanced technologies [1]. Symmetry therefore
provides a powerful guide to the identification of conjugate fields that
couple with and even switch the orders — a prerequisite for utilizing the
associated multi-stable domain states [2]. This principle is well applicable
to three out of the four types of ferroics with a vector order parameter [2]:
ferromagnets (ferroelectrics) feature time-reversal (spatial-inversion)
symmetry breaking spontaneous magnetization (electric polarization) that is
switchable by a magnetic (electric) field, whereas the ferro-toroidal order
breaks both symmetries and can be switched using composite magnetic and
electric fields [3, 4, 5]. The remaining type — the ferro-rotational (also
known as ferroaxial) order — stands out, as it is both time-reversal and
spatial-inversion invariant, hence insensitive to electromagnetic fields [2,
6]. The lack of external fields that hysteretically switch the ferro-
rotational order casts doubts on its ferroic nature [7] and limits its
potential applications.

Ferro-rotational order is attracting growing interest as a new type of ferroic
order induced by rotational structural transitions [8, 9, 10, 6, 2, 11, 12,
13, 14, 15]. It possesses an axial-vector order parameter that distinguishes
its domain states[6]. Coupled with magnetism, it can give rise to multiferroic
properties [9, 10]. Similar order has been observed in nanoscale
ferroelectrics with electric toroidal moments [16, 17]. Recent advances have
enabled detection of the ferro-rotational order and domain imaging in a
variety of materials, using second harmonic generation and linear electro-
gyration [18, 11, 12, 13, 14]. Here we focus on a pure ferro-rotational
material candidate, 1T-TaS2, which does not couple with other types of ferroic
orders. The van der Waals layered dichalcogenide 1T-TaS2 is a prototypical
charge-density-wave (CDW) system exhibiting rich phase diagrams and high
tunability [19, 20, 21, 22, 23, 24, 25, 26, 27]. In the CDW phases, the
distorted lattice features star-of-David (SD) clusters formed by 13 Ta atoms
(Fig. 1a), essential for the insulating state [28]. Tiling of SD clusters
leads to degenerate configurations, $\alpha$ and $\beta$, with the
superlattice rotated counterclockwise and clockwise, respectively, relative to
the atomic lattice [29, 30]. The structure is planar chiral [31, 18], breaking
the vertical mirror symmetry that relates the two configurations. This
peculiar feature, largely overlooked in the past decades, has come to the fore
in the pursuit of chiral CDWs [32, 33, 34, 35, 36] and is susceptible to
optical [31] or electrical [37] pulses. Recently, the planar-chiral phase was
recognized to be ferro-rotational in nature [12], hosting two domain states
corresponding to $\alpha$ and $\beta$. However, hysteretic switching between
the domain states, which is a generic hallmark of all ferroics [1], remains
elusive.

In this Article, using helicity-resolved Raman spectroscopy and imaging, we
demonstrate unexpected remarkable macroscopic switching of the structural
rotation in nanometer-thick 1T-TaS2 via a linear electric field. Although the
distorted lattice induced by the CDW transition preserves global inversion
symmetry and precludes coupling with an external electric field, the local
electric dipoles at the domain wall induced by the CDW distortion can respond
to the field, which in turn alters the local distortion. This leads to the
expansion of one type of domain at the expense of the other, and hence the
state switching. Our results open a new perspective to domain state switching,
emphasizing domain wall propagation as the key driving force, which can be
triggered by external fields that do not necessarily couple with the order
itself. The switchable ferro-rotational order hosts applications in non-
volatile memories and optoelectronics. Since 1T-TaS2 is known to harbor
electron correlation and superconductivity, the switchable planar-chiral
lattice offers a new approach to engineer novel states, especially at the
domain wall. It also provides a platform to explore tunable nonreciprocal
effects [2, 15].

Detection of ferro-rotational order

Upon cooling, bulk 1T-TaS2 undergoes successive CDW transitions, entering an
incommensurate phase (ICCDW) at around 550 K, a nearly-commensurate phase
(NCCDW) at 350 K, and a commensurate phase (CCDW) at 180 K [29]. Close packing
of SD clusters corresponds to the CCDW phase (Fig. 1b inset), leading to a
long-range ferro-rotational order. The NCCDW phase consists of hexagonal
patches of such distortions with coherent planar chirality, separated by
diffuse discommensurations (Fig. 1c inset) [38, 30, 39, 40], whereas in the
ICCDW phase SD clusters are absent. Therefore ferro-rotational order is
retained in the former but vanishes in the latter.

Planar chiral crystals are endowed with Raman tensors with off-diagonal
components, giving rise to an interesting helicity-resolved Raman response
that enables efficient discrimination of the two configurations [36]. Since
ferro-rotational materials must also be planar chiral (Supplementary Note 1),
this establishes helicity-resolved Raman scattering as a new probe of ferro-
rotational order. Figures 1b and 1c compare the Raman spectra
$I_{\sigma^{+}\sigma^{-}}$ and $I_{\sigma^{-}\sigma^{+}}$ for two samples with
opposite planar chirality, where $\sigma^{i}\sigma^{s}$ $(i,s=+,-)$ denotes
helicities for the incident and scattered photons. Each sample shows nonzero
differential spectra $\Delta I\equiv
I_{\sigma^{+}\sigma^{-}}-I_{\sigma^{-}\sigma^{+}}$ in the CCDW and NCCDW
phases for the $E_{g}$ phonons [36], whereas $\Delta I=0$ in the achiral ICCDW
phase (Supplementary Fig. 1). Moreover, the two states are related by $(\Delta
I)_{\alpha}=-(\Delta I)_{\beta}$. While the correspondence between the domain
states and Raman response is yet to be determined, we assume that the $\alpha$
($\beta$) state corresponds to positive (negative) $\Delta I_{\mathrm{int}}$,
the differential spectrum integrated over 15–150 cm-1.

We tested dozens of bulk flakes with dimensions up to tens of microns and
found most of them monodomain. This is distinct from other types of ferroics,
in which multiple domains coexist to compensate surface fields and minimize
surface energy [41]. Ideally, cooling from the ICCDW phase to the NCCDW phase
should realize the two states with equal probability. Instead, we found
predetermined domain state for a given homogeneous sample probably due to
extrinsic factors [31], which remained unaltered by thermal cycling. On one
rare sample, the two types of domains were seen to coexist, visualized by
Raman mapping in the NCCDW phase (Fig. 1d). Thermal cycling to the ICCDW phase
and back to the NCCDW phase left only $\beta$ domain (Fig. 1e), unchanged in
subsequent cycles (Supplementary Fig. 2), because domain wall formation costs
energy and is thermodynamically unstable. The planar chirality is preserved
from bulk to atomically thin samples (Supplementary Fig. 3), suggesting that
layer stacking forms a coherent domain state along the out-of-plane direction,
allowing layer packing to accommodate the protruded or suppressed regions of
the sulfur sub-layers [28, 39, 35].

Field-cooled poling

The removal of coexisting domain states by thermal cycling indicates a small
energy barrier between them, comparable to $k_{\mathrm{B}}T_{\mathrm{c}}$,
where $k_{\mathrm{B}}$ is the Boltzmann constant and $T_{\mathrm{c}}$ the
transition temperature between the NCCDW and ICCDW phases. This enables
controlled switching between the two states, as discovered here, achievable by
the remarkably simple application of a DC voltage. We found two switching
pathways, as illustrated in Fig. 2a.

We first demonstrate Pathway 1 for chirality switching. In analogy with
ferroelectrics, we call this field-cooled poling, entailing cooling the sample
from the high-symmetry to the low-symmetry phase under an external electric
field. Figure 2b shows the optical image of a two-terminal device, which was
initially in the $\alpha$ state (Fig. 2c). By maintaining a voltage while
cooling from 360 K in the ICCDW phase (Supplementary Figs. 4 and 5), the state
switched to $\beta$ when the voltage reached $-4.5$ V and alternated between
$\alpha$ and $\beta$ for $V=\pm 4.5$ V. The $\beta$ state was verified to be
metastable since the $\alpha$ state was initially favored. Figures 2d and 2e
show the Raman mapping results at 4.5 V and $-4.5$ V, respectively. Each of
the three regions separated by the electrodes was homogeneous. When Region 2
switched state at $-4.5$ V, Region 3 followed concomitantly, whereas Region 1
did not. Similar results were obtained in multiple devices (see another
example in Supplementary Fig. 6), demonstrating controlled switching of the
ferro-rotational order and domain-wall formation in close proximity to the
electrodes. The tendency of the system to adopt a monodomain state implies
strong interaction between contiguous regions, compromising the
reproducibility of the switching. This can be mitigated by placing the
electrodes on the perimeter of the flake or by separating unwanted regions.

Isothermal electrical switching

Once a domain wall is introduced, isothermal switching of the ferro-rotational
order can be achieved following Pathway 2. Figure 3a shows the device image
for a 17.6 nm sample. Figure 3b shows Raman mapping of the target region, with
the DC voltage applied in the shown order at 300 K and revoked for each
measurement. The sample was in the $\beta$ state at 1 V. As the voltage
decreased, the state switching initiated at the lower electrode and progressed
upwards, until the entire region transformed to the $\alpha$ state at $-1$ V.
The switching is therefore a result of domain wall motion. When the state
switching completed, the domain wall was pushed to the immediate vicinity of
one electrode, instead of being annihilated. Its shape changed as it swept
across the channel, indicating that the seemingly sideways propagation
entailed wall reconstruction.

Figure 3c shows the voltage dependence of $\Delta I_{\mathrm{int}}$ at a given
location, measured at 270 K and 300 K. Abrupt switching above a critical bias
$V_{\mathrm{c}}$ is revealed, and $|V_{\mathrm{c}}|$ is higher at lower
temperature. This trend was confirmed at more temperatures (Supplementary Fig.
7), with $V_{\mathrm{c}}$ summarized in Fig. 3d, which reflects a decreasing
domain wall mobility at lower temperature. Voltages exceeding large
$|V_{\mathrm{c}}|$ induce significant Joule heating, which in turn lowers the
threshold voltage, complicating the switching at low temperature
(Supplementary Fig. 7). The temperature dependent $V_{\mathrm{c}}$ suggests
that state switching can also be triggered by controlling temperature at fixed
voltage. This is shown in Fig. 3e for $\pm 0.6$ V. The state only switches
upon warming and does not reverse when cooled back. Indeed, the nonvolatility
of the switched state is borne out in the electric hysteresis in Fig. 3c,
showing retention of the switched state after voltage removal. The switching
is also highly durable. Figure 3f demonstrates repeated cycles of direct
voltage change between $\pm 1$ V at room temperature, successfully triggering
state switching without any sign of fatigue (200 cycles tested). These results
suggest applications in optoelectronics and nonvolatile memories.

Measurements using pulsed voltages offer insight into the mobility of the
domain wall. Figure 3g shows that in a 10.0 nm thick sample forming an 8
$\mu$m channel, reproducible switching at 300 K was achieved for pulse
duration longer than $\sim$10 ms, when the peak voltage was set to $\pm 1$ V
(Supplementary Fig. 8). This amounts to a domain wall velocity of
$10^{-4}$–$10^{-3}$ m/s, comparable to that in thin film ferroelectric
Pb(Zr,Ti)O3 measured under similar conditions [42]. Figures 3h and 3i
demonstrate reliable and deterministic switching using different patterns of
voltage pulses.

Intriguingly, the state switching is accompanied by an abrupt small increase
of the sample resistance (Fig. 4a). This is seen for both DC and pulsed
voltage measurements (Supplementary Fig. 9). Figure 4b shows the temperature
dependent resistance when the sample was cooled. The two monodomain states are
degenerate, with close resistance values. The interim state with the domain
wall exhibits a slightly higher resistance at 300 K, consistent with Fig. 4a,
but a crossing occurs at about 220 K, yielding a lower resistance below that
temperature. The Raman mapping results in the insets of Fig. 4b rule out
cooling-induced change of the domain wall. The disparity between the
monodomain and interim states is therefore ascribed to the domain wall. In the
CCDW phase, imperfect SD clusters at the wall weaken the Mott insulating state
[25, 43, 44, 45]. The wall, expected to penetrate the entire sample thickness
because of the interlayer coherence in each domain, may also affect the layer
stacking order and break the interlayer dimerization [46, 25, 47, 48]. Both
factors lower the resistance. In the NCCDW phase, the increased resistance in
the interim state indicates that the state switching not only affects the
hexagonal patches containing closely packed SD clusters, but also extends into
the conducting discommensuration regions [40], and the domain wall is more
insulating than the discommensuration state.

Electrical switching mechanism

The switching of the ferro-rotational order by a simple electric field is
unexpected on symmetry grounds. The CCDW phase has well-defined superlattice
periodicity with the $C_{3i}$ point group. The symmetry of the ferro-
rotational order is $A_{g}$. Any conjugate field must be of the same symmetry
to couple with this order [2], therefore excluding an in-plane electric field
because of its $E_{u}$ symmetry. More complex forms of conjugate field,
involving combinations of electric field, strain, and temperature gradient
(see Supplementary Note 2), may qualify. The NCCDW phase lacks long-range
order, lifting the symmetry requirement. Nonetheless, linear coupling with an
electric field can still be ruled out: Flipping the sample about an axis
containing the electric field changes the domain state as seen by the
observer, but the electric field is invariant in this process. In other words,
an electric field does not differentiate the two domain states.

The electrical switching must then be ascribed to the action of the field on
the domain wall, whose symmetry is much lower than a uniform domain.
Specifically, we propose that the electric field acts upon the local charge
dipoles at the wall to alter the local distortion, leading to the domain wall
motion and state switching. Six S ions surround each Ta ion to form a
symmetric TaS6 octahedron in the undistorted phase. In the NCCDW/CCDW phase,
the SD-type distortion causes off-centering of the Ta ions as well as
displacement of S ions [39], inducing local charge dipoles. Figure 4c shows
the local charge dipole in each octahedron for monolayer 1T-TaS2 obtained from
first-principles calculations, which roughly aligns with the Ta displacement.
Its magnitude is approximately 1 $e\cdot\mathrm{\AA}$ for the outer six
octahedra in the SD cluster and smaller for the inner ones (Supplementary Fig.
10), similar to that in typical ferroelectrics [41, 49]. There is no net
global polarization because the local dipoles within a SD cluster cancel out,
dictated by the centrosymmetric crystal structure. Figure 4d illustrates a
possible form of wall between two different domains [37]. An applied electric
field can couple with the local dipoles and tends to orient them along the
field direction, effectively nudging the ions such that they form a new SD and
expand the domain along the field direction. This is consistent with the fact
that two types of electric hysteresis loops were observed under the same
configuration of the electrical circuit (Fig. 3c and Fig. 4a), as the electric
field does not couple with a particular domain state, but only determines the
propagation direction of the domain wall. The coercive field observed here is
on the order of kV/cm, again similar to that in ferroelectrics [49], pointing
to an analogous effect of the electric field on the domain wall in ferro-
rotational 1T-TaS2 and typical ferroelectrics.

Discussion and conclusion

Our results resemble the domain state switching in thick 1T-TaS2 flakes
induced by femtosecond light pulses [31] in some aspects. Both types of
switching can occur in the NCCDW phase but not in the CCDW phase. In that
work, it was proposed that the NCCDW phase melts to yield a transient ICCDW
phase before a different domain state emerges. Similarly, in our work we find
that entering the ICCDW phase is essential for field-cooled poling of the
domain states. According to electron diffraction, the ICCDW phase is
characterized by disordered distributions of local $\alpha$\- and $\beta$-type
distortions [35]. Electric field can act upon the microscopic domain walls, as
discussed earlier, assisting the growth of one type of domain when cooled into
the NCCDW phase. On the other hand, the naturally formed NCCDW and CCDW phases
are monodomain, which do not couple with electric field. The hysteretic
electrical switching discovered here is distinct from the reversible switching
of planar chiral states in monolayer 1T-NbSe2 nano-islands, achieved by
voltage pulses of the same sign sent through the tip of a scanning tunneling
microscope in the CCDW phase [37]. The reason for the discrepancy in the
switching conditions requires further studies.

In summary, we have demonstrated hysteretic electrical switching of the ferro-
rotational order in 1T-TaS2 by direct visualization of its domains and
observation of domain wall propagation, establishing its ferroic character.
The electric field does not couple with the order but only acts on the domain
wall to trigger its motion. While the key microscopic mechanism for the
switching has been outlined, a complete understanding of the process calls for
further experimental and theoretical investigations. Whether such a mechanism
is universal is an open question. Our methodology is applicable to the
discovery and investigation of more ferro-rotational materials.

## References

  * [1] Wadhawan, V.  _Introduction to Ferroic Materials_ (CRC Press, 2000), 1st edn.
  * [2] Cheong, S.-W., Talbayev, D., Kiryukhin, V. & Saxena, A.  Broken symmetries, non-reciprocity, and multiferroicity.  _npj Quant. Mater._ 3, 19 (2018).
  * [3] Van Aken, B. B., Rivera, J.-P., Schmid, H. & Fiebig, M.  Observation of ferrotoroidic domains.  _Nature_ 449, 702–705 (2007).
  * [4] Spaldin, N. A., Fiebig, M. & Mostovoy, M.  The toroidal moment in condensed-matter physics and its relation to the magnetoelectric effect.  _J. Phys.: Condens. Matter_ 20, 434203 (2008).
  * [5] Zimmermann, A. S., Meier, D. & Fiebig, M.  Ferroic nature of magnetic toroidal order.  _Nat. Commun._ 5, 4796 (2014).
  * [6] Hlinka, J., Privratska, J., Ondrejkovic, P. & Janovec, V.  Symmetry guide to ferroaxial transitions.  _Phys. Rev. Lett._ 116, 177602 (2016).
  * [7] Fiebig, M.  Order! order!!  _Nat. Phys._ 16, 9–10 (2020).
  * [8] Gopalan, V. & Litvin, D. B.  Rotation-reversal symmetries in crystals and handed structures.  _Nat. Mater._ 10, 376–381 (2011).
  * [9] Johnson, R. D. _et al._ Cu3Nb2O8: A multiferroic with chiral coupling to the crystal structure.  _Phys. Rev. Lett._ 107, 137205 (2011).
  * [10] Johnson, R. D. _et al._ Giant improper ferroelectricity in the ferroaxial magnet CaMn7O12.  _Phys. Rev. Lett._ 108, 067201 (2012).
  * [11] Jin, W. _et al._ Observation of a ferro-rotational order coupled with second-order nonlinear optical fields.  _Nat. Phys._ 16, 42–46 (2020).
  * [12] Luo, X. _et al._ Ultrafast modulations and detection of a ferro-rotational charge density wave using time-resolved electric quadrupole second harmonic generation.  _Phys. Rev. Lett._ 127, 126401 (2021).
  * [13] Hayashida, T. _et al._ Visualization of ferroaxial domains in an order-disorder type ferroaxial crystal.  _Nat. Commun._ 11, 4582 (2020).
  * [14] Hayashida, T. _et al._ Phase transition and domain formation in ferroaxial crystals.  _Phys. Rev. Mater._ 5, 124409 (2021).
  * [15] Cheong, S.-W., Lim, S., Du, K. & Huang, F.-T.  Permutable SOS (symmetry operational similarity).  _npj Quant. Mater._ 6, 58 (2021).
  * [16] Naumov, I. I., Bellaiche, L. & Fu, H.  Unusual phase transitions in ferroelectric nanodisks and nanorods.  _Nature_ 432, 737–740 (2004).
  * [17] Damodaran, A. R. _et al._ Phase coexistence and electric-field control of toroidal order in oxide superlattices.  _Nat. Mater._ 16, 1003–1009 (2017).
  * [18] Fichera, B. T. _et al._ Second harmonic generation as a probe of broken mirror symmetry.  _Phys. Rev. B_ 101, 241106 (2020).
  * [19] Sipos, B. _et al._ From Mott state to superconductivity in 1T-TaS2.  _Nat. Mater._ 7, 960–965 (2008).
  * [20] Stojchevska, L. _et al._ Ultrafast switching to a stable hidden quantum state in an electronic crystal.  _Science_ 344, 177–180 (2014).
  * [21] Yoshida, M. _et al._ Controlling charge-density-wave states in nano-thick crystals of 1T-TaS2.  _Sci. Rep._ 4, 7302 (2014).
  * [22] Yu, Y. _et al._ Gate-tunable phase transitions in thin flakes of 1T-TaS2.  _Nat. Nanotechnol._ 10, 270–276 (2015).
  * [23] Yoshida, M., Suzuki, R., Zhang, Y., Nakano, M. & Iwasa, Y.  Memristive phase switching in two-dimensional 1T-TaS2 crystals.  _Sci. Adv._ 1, e1500606 (2015).
  * [24] Cho, D. _et al._ Nanoscale manipulation of the Mott insulating state coupled to charge order in 1T-TaS2.  _Nat. Commun._ 7, 10453 (2016).
  * [25] Ma, L. _et al._ A metallic mosaic phase and the origin of Mott-insulating state in 1T-TaS2.  _Nat. Commun._ 7, 10956 (2016).
  * [26] Vaskivskyi, I. _et al._ Fast electronic resistance switching involving hidden charge density wave states.  _Nat. Commun._ 7, 11442 (2016).
  * [27] Qiao, S. _et al._ Mottness collapse in 1T-TaS2-xSex transition-metal dichalcogenide: An interplay between localized and itinerant orbitals.  _Phys. Rev. X_ 7, 041054 (2017).
  * [28] Fazekas, P. & Tosatti, E.  Charge carrier localization in pure and doped 1T-TaS2.  _Physica B+C_ 99, 183–187 (1980).
  * [29] Wilson, J., Salvo, F. D. & Mahajan, S.  Charge-density waves and superlattices in the metallic layered transition metal dichalcogenides.  _Adv. Phys._ 24, 117–201 (1975).
  * [30] Thomson, R. E., Burk, B., Zettl, A. & Clarke, J.  Scanning tunneling microscopy of the charge-density-wave structure in 1T-TaS2.  _Phys. Rev. B_ 49, 16899–16916 (1994).
  * [31] Zong, A. _et al._ Ultrafast manipulation of mirror domain walls in a charge density wave.  _Sci. Adv._ 4, eaau5501 (2018).
  * [32] Ishioka, J. _et al._ Chiral charge-density waves.  _Phys. Rev. Lett._ 105, 176401 (2010).
  * [33] Xu, S.-Y. _et al._ Spontaneous gyrotropic electronic order in a transition-metal dichalcogenide.  _Nature_ 578, 545–549 (2020).
  * [34] Jiang, Y.-X. _et al._ Unconventional chiral charge order in kagome superconductor KV3Sb5.  _Nat. Mater._ 20, 1353–1357 (2021).
  * [35] Sung, S. H. _et al._ Two-dimensional charge order stabilized in clean polytype heterostructures.  _Nat. Commun._ 13, 413 (2022).
  * [36] Yang, H. F. _et al._ Visualization of chiral electronic structure and anomalous optical response in a material with chiral charge density waves.  _Phys. Rev. Lett._ 129, 156401 (2022).
  * [37] Song, X. _et al._ Atomic-scale visualization of chiral charge density wave superlattices and their reversible switching.  _Nat. Commun._ 13, 1843 (2022).
  * [38] Wu, X. L. & Lieber, C. M.  Hexagonal domain-like charge density wave phase of TaS2 determined by scanning tunneling microscopy.  _Science_ 243, 1703–1705 (1989).
  * [39] Spijkerman, A., de Boer, J. L., Meetsma, A., Wiegers, G. A. & van Smaalen, S.  X-ray crystal-structure refinement of the nearly commensurate phase of 1T-TaS2 in $(3+2)$-dimensional superspace.  _Phys. Rev. B_ 56, 13757–13767 (1997).
  * [40] Park, J. W., Cho, G. Y., Lee, J. & Yeom, H. W.  Emergent honeycomb network of topological excitations in correlated charge density wave.  _Nat. Commun._ 10, 4038 (2019).
  * [41] Catalan, G., Seidel, J., Ramesh, R. & Scott, J. F.  Domain wall nanoelectronics.  _Rev. Mod. Phys._ 84, 119–156 (2012).
  * [42] McGilly, L. J., Yudin, P., Feigl, L., Tagantsev, A. K. & Setter, N.  Controlling domain wall motion in ferroelectric thin films.  _Nat. Nanotechnol._ 10, 145–150 (2015).
  * [43] Cho, D. _et al._ Correlated electronic states at domain walls of a Mott-charge-density-wave insulator 1T-TaS2.  _Nat. Commun._ 8, 392 (2017).
  * [44] Skolimowski, J., Gerasimenko, Y. & Žitko, R.  Mottness collapse without metallization in the domain wall of the triangular-lattice Mott insulator 1T-TaS2.  _Phys. Rev. Lett._ 122, 036802 (2019).
  * [45] Park, J. W., Lee, J. & Yeom, H. W.  Zoology of domain walls in quasi-2D correlated charge density wave of 1T-TaS2.  _npj Quant. Mater._ 6, 32 (2021).
  * [46] Ritschel, T. _et al._ Orbital textures and charge density waves in transition metal dichalcogenides.  _Nat. Phys._ 11, 328–331 (2015).
  * [47] Lee, S.-H., Goh, J. S. & Cho, D.  Origin of the insulating phase and first-order metal-insulator transition in 1T-TaS2.  _Phys. Rev. Lett._ 122, 106404 (2019).
  * [48] Butler, C. J., Yoshida, M., Hanaguri, T. & Iwasa, Y.  Mottness versus unit-cell doubling as the driver of the insulating state in 1T-TaS2.  _Nat. Commun._ 11, 2477 (2020).
  * [49] Dawber, M., Rabe, K. M. & Scott, J. F.  Physics of thin-film ferroelectric oxides.  _Rev. Mod. Phys._ 77, 1083–1130 (2005).
  * [50] Kresse, G. & Furthmüller, J.  Efficient iterative schemes for ab initio total-energy calculations using a plane-wave basis set.  _Phys. Rev. B_ 54, 11169–11186 (1996).
  * [51] Perdew, J. P., Burke, K. & Ernzerhof, M.  Generalized gradient approximation made simple.  _Phys. Rev. Lett._ 77, 3865–3868 (1996).

Methods

Sample preparation
Bulk TaS2 single crystals were synthesized using the chemical vapor transport
method. Thin flakes were mechanically exfoliated from the bulk crystals on
silicone elastomer polydimethylsiloxane (PDMS) stamps in a glove box filled
with high-purity argon gas, followed by transferring onto SiO2/Si substrates
and encapsulation with thin h-BN before being exposed to air. The flake
thickness was determined by atomic force microscopy.

Device fabrication
For devices used in the electrical switching experiment and electrical
transport measurements, thin TaS2 samples on PDMS were transferred on pre-
patterned Ti/Au electrodes and encapsulated by h-BN. The electrodes were
fabricated by electron-beam lithography on Si substrates with a 300 nm SiO2
layer, followed by electron-beam evaporation of 3 nm Ti and 15 nm Au.

Laser cutting
Sample cutting was realized by a supercontinuum laser coupled with an optical
microscope, enabling simultaneous visualization of the sample and the laser
spot. The laser emits pulses covering the visible to near-infrared spectral
range with a pulse repetition rate of 0.2 MHz. The beam was focused on the
sample by a 40$\times$ objective and the total incident power was greater than
10 mW. The sample was translated slowly using a manual translation stage, such
that the trajectory under laser illumination was burnt due to excessive heat.
A minimum linewidth of 1 $\mu$m was achieved. Successful cutting was indicated
by change of sample color and confirmed by Raman measurements in the burnt
region.

Raman measurements
Raman micro-spectroscopy was performed in the back-scattering geometry using
532 nm laser excitation. The incident light was focused on the sample to a
sub-micron-sized spot using an objective with high numerical aperture, 0.60
for regular measurements or 0.82 for Raman mapping. The scattered light was
directed through Bragg notch filters before being collected by a grating
spectrograph and a liquid-nitrogen-cooled charge-coupled device. The samples
were mounted in a vacuum chamber during data acquisition. Raman mapping was
performed by stepping the sample through a dense grid of coordinates using a
piezoelectric two-dimensional scanner and collecting spectra at each position.

The circularly polarized measurements were performed by using a combination of
two polarizers and one quarter-wave plate, as detailed in Ref. [36].
Specifically, the first polarizer and the quarter-wave plate set the helicity
($\sigma^{+}$ or $\sigma^{-}$) of the incident light. The back-scattered
light, containing both $\sigma^{+}$ and $\sigma^{-}$ components, passes
through the quarter-wave plate again and is converted back to linear
polarization. Setting the second polarizer either parallel with or
perpendicular to the incident polarization therefore selectively probes the
circularly contrarotating ($\sigma^{+}\sigma^{-}$ and $\sigma^{-}\sigma^{+}$)
or the circulary corotating ($\sigma^{+}\sigma^{+}$ and
$\sigma^{-}\sigma^{-}$) channels.

Temperature-dependent Raman and electrical transport measurements
Temperature-dependent Raman and resistance data shown in Supplementary Fig. 3
were measured concomitantly in a Montana Instrument Cryostation. The
temperature sweeping rate was set to a low value of 1.5 K/min because the CDW
phase transitions in TaS2 are sensitive to the cooling/warming rate [23].
Collection of both the Raman spectra (30 s/each) and the sample resistance
were automated by a computer program. Sample drifting and defocusing of the
laser spot were compensated by frequent manual adjustment. The resistance was
measured in a four-probe geometry using the standard lock-in method, with an
excitation current of 1 $\mu$A for the 103.7 nm sample and 0.1 $\mu$A for the
3.1 nm sample. The temperature-dependent two-probe resistance (Fig. 4b and
Supplementary Fig. 9b) was measured using the same technique and cooling rate.

Electrical switching using DC and pulsed voltages
Electrical switching of chirality was triggered by either DC or pulsed
voltages, both in the two-terminal configuration. The devices were connected
to the same external circuit to allow comparison of their characteristics. DC
voltage was supplied by a Keithley 2400 Source Measure Unit, which also
measured the induced current in the circuit, yielding the DC resistance
$R_{\mathrm{DC}}$. Pulsed voltage was generated using a multifunction data
acquisition device from National Instruments. Calibration of the pulse
duration showed a minimum controllable value of $\sim$2 ms (Supplementary Fig.
8). For repeated switching using DC voltage shown in Fig. 3f, the voltage was
held constant while Raman spectra were taken in both $\sigma^{+}\sigma^{-}$
and $\sigma^{-}\sigma^{+}$ channels (30 s/each); the completion of spectra
acquisition triggered the change of voltage. Repeated switching using voltage
pulses was carried out in a similar manner, with the voltage immediately
revoked after one pulse duration and followed by Raman measurements. The
pulsed-voltage dependence of the sample resistance shown in Supplementary Fig.
9a was measured using the lock-in method described above. Resistance was
acquired after the passage of each voltage pulse. Relays were added to the
circuits for electrical switching and for resistance measurement to avoid
crosstalk between the two.

First-principles calculations
The electric charge density before and after distortion of SD type is
calculated by first-principles methods as implemented in Vienna ab-initio
Simulation Packages (VASP) [50]. Perdew-Burke-Ernzerhof (PBE) type
generalized-gradient approximation (GGA) [51] is used for the exchange
correlation functionals. A $5\times 5\times 1$ $k$-mesh is used for
$\sqrt{13}\times\sqrt{13}$ supercell of 1$T$-TaS2. The ground state energy and
charge density data are collected as the total energy difference reaches the
iterative threshold of $10^{-8}$ eV during the self-consistent calculation.
The local charge dipole within the S octahedron surrounding each Ta ion is
calculated as

$\mathbf{p}=4e\mathbf{u}_{\textrm{Ta}}+\sum^{6}_{i=1}\left(-\frac{2e}{3}\right)\mathbf{u}^{i}_{\textrm{S}},$
(1)

where $\mathbf{u}_{\textrm{Ta}}$ and $\mathbf{u}^{i}_{\textrm{S}}$
($i=1,...,6$) represent the displacement vectors of the central Ta ion and the
six surrounding S ions, respectively. Although the calculations were performed
for the CCDW phase, the results are expected to represent the properties of
the hexagonal patches in the NCCDW phase.

Data availability
The data that support the plots in this paper and other findings of this study
are available from the corresponding authors on reasonable request.

Acknowledgements
We thank Junyao Yu and Chao Wang for assistance with the atomic force
microscopy measurements. This work was supported by the National Key Research
and Development Program of China (Grant Nos. 2018YFA0307000, 2017YFA0303201,
and 2021YFA1400400) and the National Natural Science Foundation of China
(Grant Nos. 11774151, 12225407, 12204160, and 12074174). K.W. and T.T.
acknowledge support from JSPS KAKENHI (Grant Nos. 19H05790, 20H00354 and
21H05233) and A3 Foresight by JSPS. B.Y. acknowledges the financial support by
the European Research Council (ERC Consolidator Grant “NonlinearTopo”, No.
815869).

Author contributions
X.X. conceived the project. G.L. and K.H. performed the measurements. T.Q. and
D.L. fabricated the devices. Z.M., Z.H., and J.W. grew the TaS2 crystals. K.W.
and T.T. grew the h-BN crystals. G.L. and X.X. analysed the experimental data.
Y.L. and B.Y. performed the DFT calculations. W.T, J.X., and L.G. performed
atomic force microscopy measurements. X.X., B.Y., G.L., and J.M.L. interpreted
the results. X.X. and B.Y. co-wrote the paper, with comments from all authors.

Competing interests
The authors declare no competing interests.

Fig. 1: Ferro-rotational order in 1T-TaS2 and its helicity-resolved Raman
response. a, Green: schematic of the star-of-David (SD) lattice distortion,
with 12 peripheral Ta atoms displaced towards a central Ta atom to form a
cluster. Two ways of tiling the $ab$-plane with this structural motif form
planar-chiral configurations, $\alpha$ and $\beta$, with the superlattice unit
cell (dashed rhombus) rotated 13.9∘ counterclockwise and clockwise,
respectively, relative to the atomic lattice. b, c, Raman spectra for two bulk
samples with opposite chiral states in the CCDW and NCCDW phases (illustrated
in the insets). The contrast between the $\sigma^{+}\sigma^{-}$ and
$\sigma^{-}\sigma^{+}$ channels (filled colors) distinguishes the planar
chirality. d, e, Raman mapping of the normalized integrated contrast $\Delta
I_{\mathrm{int,norm}}$ for a bulk sample at 300 K, before and after warming to
the ICCDW phase.  Fig. 2: Electrical switching of ferro-rotational order via
thermal cycling involving the ICCDW phase. a, Illustration of two pathways for
electrical switching. b, Optical image of a two-probe device for a 11.1 nm
sample. Three regions are labeled. c, $\Delta I_{\mathrm{int}}$ taken at a
fixed spot in Region 2 as the DC voltage is varied. d, e, Raman mapping of the
region in the black square in b, after applying 4.5 V and $-4.5$ V,
respectively. All data in c–e were taken at 300 K at zero voltage, following
Pathway 1. Fig. 3: Isothermal electrical switching of ferro-rotational order
in the NCCDW phase. a, Optical image of a two-probe device for a 17.6 nm
sample, with the parts outside the electrodes separated by laser cutting. b,
Raman mapping of the marked region in a when the DC voltage was applied
sequentially at 1, $-0.3$, $-0.4$, and $-1$ V at 300 K. c, DC voltage
dependence of $\Delta I_{\mathrm{int}}$ at 270 K (circles) and 300 K
(triangles). The arrows denote directions of voltage sweep. d, Temperature
dependence of the critical voltage. e, Temperature dependence of $\Delta
I_{\mathrm{int}}$ at $\pm 0.6$ V. Filled and open symbols represent warming
and cooling, respectively. f, Repeated state switching using DC voltages. g,
Variation of $\Delta I_{\mathrm{int}}$ when voltage pulses with increasing
pulse duration are applied, measured on a 10.0 nm device following the
sequence indicated by the dashed lines. h, i, State switching using voltage
pulses of 20 ms duration but different sequences of pulse trains. c–i were
obtained with the laser spot at a fixed location. f–i are for 300 K. Fig. 4:
Electrical transport signature of the state switching and electrical switching
mechanism. a, DC voltage dependence of $\Delta I_{\mathrm{int}}$ and DC
resistance at 300 K. b, Resistance measured during cooling for different
states. The insets are Raman mapping results. Dashed lines mark the
electrodes, which are 8 $\mu$m apart. Sample thickness is 11.8 nm. c,
Calculated charge redistribution due to the SD type CDW in monolayer 1T-TaS2.
The red and green colors represent gain and loss of charges, respectively. The
arrows indicate the local charge dipoles around each Ta atom. d, Schematic
showing the formation of a domain wall between the two types of domains.
Arrows represent the displacement of Ta ions in each SD cluster.