The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008
J(Q.)= £ k(x, y)dxdy
J is a region integral , all the information inside region Q is
used, so it much more “global” than boundary-based modelling,
but it has a weak point: Sensitivity to initial segmentation.
There is an effort to integrate boundary-based with region-
based approaches. Pair wise similarities or dissimilarities
between points are also introduced into cost functions. Graph
partitioning methods (GPM) is one of the popular tools for
minimizing pair wise similarity based cost functions. A general
advantage of GPM is its global minimization techniques, which
are desirable for the segmentation problem.
In this paper, we introduce novel weighted Graph partitioning
methods. Main contributions of this paper include:
Introduction of a new variation cost functions which are based
on weighted pair wise similarities. Weight changes according to
the pointers’ positions. Different kind of similarity can be
defined for different images.
An efficient computing strategy is proposed. The hybrid
boundary-based modelling and region-based modelling method
frameworks for pair wise similarity based cost functions
requires excessive memory size and CPU computing ability,
and naive implementations are not practical even on high end
workstations. We introduce novel pre-segmentation methods for
efficient implementation of the curve evolution techniques that
are derived for the minimization of pair wise dissimilarity based
cost functions.
2. WEIGHTED GRAPH PARTITIONING ACTIVE
CONTOURS
2.1 Graph Partitioning Active Contours
This insight of graph theoretic is as following. Assume is a
representation of an undirected graph, where V are the vertices
and E are the edges between these vertices. V corresponds to
pixels in an image or small regions (set of connected pixels).
co(u,v) is a function of the dissimilarity between nodes u and
Suppose V is divided into two disjoint sets, A and B ,
Theorem: Let N be the outward normal of the curve C. The
curve evolution equation that corresponds to the steepest
descent minimization of (2) is:
dX_
dt
N
(3)
JJ co(X, p)dp - JJ co(X,p)dp
fi„(C(0) R iM (C(/))
Where X is point on the contour C ,
R m (C(t)) andR 0Ul (C(t)) are the regions inside and outside of
the contour C .
2.2 Weighted Graph Partitioning Active Contours
In GPAC model, the contributions of the pixels in the different
regions are all the same. We will extend the model to suppose
the condition in which the pixels in the different regions have
different contribution in the cost function. For example, in some
images with blur boundary, there is very little difference
between the pixels at the different side of boundary, so the
dissimilarities between the pixels at the different side of
boundary have little contribution to the cost function.
Further more, region-based models are sensitive to initial
segmentation and have little local properties. In order to
enhance the model’s local properties, we introduce dissimilarity
weight into GPAC according to the pixels’ positions. With
dissimilarity weight, pixels at different regions have different
contributions to the cost function. We refer this novel model as
Weighted Graph Partitioning Active Contours(WGPAC).
In the definition of (1), dissimilarity function unction co(u,v) is
a function independent of time t, and the (2) is also based the
fact that co(u,v) is independent of t . In WGPAC, we add
weight function f(u., v) to co(u, v), so the cost function is:
II JJ / ( w > V ) T)w(u, v)dudv
R,„ R m ,
Let W(u, v) — f (u, v)co(u, v) , then (4) becomes:
E = || ||W(u,v)dudv
HereW(u,v) is symmetric function .In order to minimize (5),
We introduce Heave function and Dirac function:
(f>0)
{.<!><o)
Suppose C(t) is the active contour and f is its level set
function, the integration of function f(p) in the region inside
|| f(p)dp= jjf(p)H(<f>(p))dp (7)
Similarly, the integration of function f (p) in the region
outside C(t) is:
