3836 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 24, NO. 11, NOVEMBER 2015
Fig. 2. An illustration of boundary smoothness measurement. Dash lines
are cluster boundaries. Pink curve indicates the local neighborhood area
for smoothness measurement. (a) Boundary smoothness measurement for a
pixel P. Each pixel is visualized as a polygon and its shape stands for the
pixel’s current cluster assignment. (b) Boundary smoothness measurement for
a superpixel S. Each polygon represents a superpixel and the shape of its
center marker stands for the superpixel’s current cluster assignment.
pixel (i, j) with radius ω as
χ
(i, j)
(i
, j
) =
1ifπ(i
, j
) = π(i, j)
0otherwise
where π(i, j) tells the cluster index that (i, j) belongs to. Then
the edge energy is defined as
E
edge
(C) =
(i, j)∈I
(i
, j
)∈N
ω
(i, j)
χ
(i, j)
(i
, j
). (2)
Figure 2a illustrates the boundary smoothness measurement
on a single pixel. It has been shown in [17] that E
edge
(C)
is proportional to the total length of boundaries in C in the
limit. Finally, the edge-weighted CVT clustering energy can
be defined as
E
ewcvt
(C, W) = E
cvt
(C, W) + λE
edge
(C) (3)
where λ is a weight parameter balancing the clustering energy
and the edge energy. Construction of EWCVTs is equivalent to
solving the minimization problem min
(C,W)
E
ewcvt
(C, W).
An edge-weighted distance function from a pixel (i, j) to
a cluster center (generator) w
k
was derived for the energy
E
ewcvt
as
dist((i, j), w
k
) =
ρ(i, j)u(i, j) −w
k
2
+ 2λ ˜n
k
(i, j)
(4)
where ˜n
k
(i, j) =|N
ω
(i, j)|−n
k
(i, j) − 1 with n
k
(i, j) =
(i
, j
)∈N
ω
(i, j)
π(i
, j
) = k. Based on the above distance
function, some efficient algorithms for constructing EWCVTs
are suggested in [17] based on the K-means type techniques.
We specially note that a cluster C
l
produced by the EWCVT
method may consist of physically disconnected regions in the
image I, i.e., multiple segments.
III. H
IERARCHICAL EDGE-WEIGHTED CENTROIDAL
VORONOI TESSELLATION
The proposed hierarchical method begins with an over-
segmentation on pixels using the a modified EWCVT
algorithm that strictly enforces the simple-connectivity of
superpixels [16]. This oversegmentation is taken as the finest
level of superpixels in the hierarchy. For the higher levels,
Algorithm 1 (Finest Level Superpixel Algorithm)
we merge finer level superpixels with similar color features,
meanwhile preserve superpixel connectivity and enforce the
boundary smoothness of superpixels.
A. Finest Level
At the finest level we deal with the generation of superpixels
directly from the image pixels. Let M
1
be the desired number
of superpixels. Similar to the VCells algorithm proposed
in [16], we first use the classic K-means with the Euclidean
norm on pixel coordinates I, to generate M
1
simply-connected
and quasi-uniformly distributed superpixels on the input
image. We also set ρ ≡ 1 here. Next we apply the VCells
algorithm to the initial superpixel configuration where we
only allow transferring of boundary pixels between neighbor
clusters at each iteration. The whole algorithm is described
in Algorithm 1. If π(i, j) is different from the label of at least
one of its 4 neighbors, i.e., (i ±1, j) or (i, j ±1),wesay(i, j)
is a boundary pixel, and denote B as the set of all boundary
pixels. We remark that each pixel moving between neighbor
clusters in Algorithm 1 will decrease the energy E
ewcvt
, thus
Algorithm 1 guarantees monotonic decreasing of E
ewcvt
along
the iterations till it terminates, see [17] for detailed discussions.
There is no guarantee to preserve the simple-connectivity
property of each segment in the algorithm above. Thus in
the end we perform a filtering step to further enforce the
simple-connectivity of superpixels, which is widely used in
other superpixel algorithms [5], [13], [15], [16] and will be
described in Section III-C.
B. Higher Levels
At a higher level q (q > 1), we already have a superpixel
from the previous level q−1, S =
{
S
m
}
M
q−1
m=1
. Given the desired
剩余11页未读，继续阅读
