LI et al.: STRUCTURED SPARSE ERROR CODING FOR FR WITH OCCLUSION 1891
II. ERROR STRUCTURE
In this section, we explore the structure of the error from
two aspects: the structure of the error support built on a new
graph model, and the structure of the error distribution under
robust error metric.
A. Morphological Graph Model for Error Support Structure
1) Morphological Graph Model: We first study the intrinsic
error structure from the cognitive style of the visual system
of human beings. Why could human beings recognize a facial
occlusion accurately and rapidly? Our visual experience indi-
cates that we recognize the occlusion according to its region
shape or profile even without knowing what the occlusion is
and where it lies. Mathematical morphology shows that the
shape can be described by boundaries, skeleton, or the convex
hull [27, Chap. 9]. In this work, we try to describe occlusion
shape by its boundary, which means the interrelationships
between image pixels should be well modeled. While the
error support s
i
can be used to indicate if an image pixel
y
i
is occluded, s
i
cannot be used to infer if the image pixels
around y
i
are occluded. Inspired by the work of [25], Zhou
et al. [9] suggest to model the error support s using a graph
G =
(
V, E
)
. Here, V =
{
1,...,m
}
denotes the vertex set
of m pixels of y ∈ R
m
and each vertex i ∈ V is labeled by
s
i
; E = E
(
r
)
=
(
i, j
)
|i, j ∈ V,
c
i
− c
j
2
≤ r
denotes the
edges connecting neighboring pixels, where r is the maximum
edge length and c
i
= [c
i1
, c
i2
]
T
is the coordinate vector of
the vertex i
4
. Thus, the occlusion probabilities of the image
pixels around y
i
can be inferred from s
i
according to the edges
connected with vertex i. Clearly, the graph G defined above
cannot describe the occlusion shape. Since the occlusion on
an image corresponds to the subgraph with vertices labeled
by s
i
= 1, we then consider how to represent the shape of a
subgraph.
Let L
G
denote the label set of the graph G. Then,
G can be divided into several subgraphs by L
G
: G =
{
G
k
|G
k
=
(
V
k
, E
k
)
, k ∈ L
G
}
,whereV
k
=
{
i|i ∈ V, s
i
= k
}
and E
k
=
{
(
i, j
)
|i, j ∈ V
k
,
(
i, j
)
∈ E
}
. Since the shape can
be described by boundaries, we incorporate the boundary set
B of all subgraphs into the classical graph model to form a
new graph model G =
(
V, E, B
)
, dubbed the morphological
graph. Before defining the boundary B, we first introduce
two special vertex sets to describe the relationships between
vertices: the outside vertex set and the related vertex set. The
outside vertex set v
o
i
of the vertex i consists of the vertices
which are connected but have different labels with the vertex
i: v
o
i
=
j|
(
i, j
)
∈ E, s
i
= s
j
.Therelated vertex set v
o
ij
of
the vertices i and j consists of the vertex pairs which are
connected by the edge but belong to v
o
i
and v
o
j
, respectively:
v
o
ij
=
k, l|
(
k, l
)
∈ E, k ∈ v
o
i
, l ∈ v
o
j
. We then define the
boundary set B of the morphological graph G as following:
Definition 1: The boundary set B of the morphologi-
cal graph G =
(
V, E, B
)
is the set of the boundaries
of all subgraphs of G =
(
V, E
)
: B =
{
B
k
|k ∈ L
G
}
,
where B
k
is the boundary of G
k
. B
k
is also a graph
4
We use the same spatial coordinate convention as [27, Sec. 2.4.2].
B
k
=
¯
V
k
,
¯
E
k
,where
¯
V
k
=
i|i ∈ V
k
,v
o
i
=∅
and
¯
E
k
=
(
i, j
)
|i, j ∈
¯
V
k
,v
o
ij
=∅
.
Section B of the supplementary appendix explores in detail
how to detect the subgraph boundaries for a given graph
G and how the maximum edge length r of G affects its
discriminability. Since subgraphs with r = 1seemstohave
better discriminability than r = 2, we choose r = 1inthe
following work. In the next subsection, we will show how to
use the morphological graph to describe the priori information
of the error support s.
2) Priori Probability for Error Support: We now consider
how to build the prior probability p
(
s
)
of the error support
s on the morphological graph G =
(
V, E, B
)
.In[9],p
(
s
)
is
built on the graph G =
(
V, E
)
using the classical Ising model:
p
(
s
)
∝ exp
⎛
⎝
λ
E
(i, j)∈E
s
i
s
j
+ λ
V
i∈V
s
i
⎞
⎠
, (2)
where the smooth cost λ
E
(
i, j)∈E
s
i
s
j
(λ
E
≥ 0) describes
the continuity of the occlusion, and the data cost λ
V
i∈V
s
i
(λ
V
≥ 0) gives the priori assumptions about the locations of
the erroneous pixels. Comparing with G, G is equipped with
an additional graph B. Since the vertices in B are sensitive
to the change of the subgraphs (occlusions), we try to weaken
the influence of these vertices in the Ising model (2). Then,
we have the priori probability p
(
s
)
of the error support s on
G (see Section C of the supplementary appendix for a proof):
p(s) ∝ exp
⎛
⎝
λ
E
(i, j)∈E
s
i
s
j
+ λ
V
i∈V
s
i
− λ
B
i∈
¯
V
1
s
i
⎞
⎠
. (3)
Note that the boundary cost λ
B
i∈
¯
V
1
s
i
= λ
B
¯
V
1
actually
reflects the regularity of the occlusion boundary. Actually, for
∀G ∈ G
1
and ∀
(
i, j
)
∈
¯
E
k
,wehave
c
i
− c
j
2
≤
√
2, and
¯
R
k
=
(
i, j)∈
¯
E
k
c
i
− c
j
2
≈
¯
E
k
≈
¯
V
k
.
Although we weaken the influence of the vertices on the
graph boundaries in (3), it does not mean that they are not
important. On the contrary, they are very important in the
quality assessment model of Section III-B3.
B. Exponential Probabilitic Model for Error Distribution
Structure
When there are occlusions, Yang et al. [11], [19] indicate
that the error ˆe may be far from any specific distribution.
Nevertheless, with the assumption that the unoccluded region
of the test image y can be approximated sufficiently by the cor-
responding regions of the training samples, if the error support
s is known and the error ˆe is coded and measured in a specific
way, we argue that ˆe might follow a specific distribution. The
details about the error coding and error metric are discussed
in Section D of the supplementary appendix. In this work,
we pay attention to the local error metric LEM
y
i
, ˆy
i
h
(
0
)
− h
y
i
−ˆy
i
, where h
(
x
)
= exp
(
−
|
x
|
/σ
)
,andthe
dilation invariance metric DIM
y
i
, ˆy
i
log
y
i
/ ˆy
i
.By
combining LEM and DIM together, we form a new error