The problem of obtaining of a minimal polygonal representation of a plane digital curve is treated. Means of a fuzzy clustering method are used. The fuzzy clustering is realized by relations of similarity and dissimilarity that are defined on a planar digital curve.
As a rule the some set of features is extracted in image to analyse and recognize an object in the image. We will distinguish between low- and high-level features in the image. The low-level features are features that may be extracted without information about a special location of certain parts of the image object [14]. In the contrary the information about special location of certain parts of the image object is used to detect high-level features. The edges of image object, the curvature of a curve on the image are the main low-level features in the image. The low-level features are aggregated for receive a compact representation of an image object. As a result we will receive a high-level representation of image object, for example, a curve. The compact curve representation is necessary for image compression, image vectorization etc. In general digital curve Γ depend on a set of parameters so the number of parameters may be equal to the number of points of digital curve. In this case a problem of representation is to find the curve Γ ′ that depends from a smaller set of parameters and saves a main information about the curve Γ . There are many methods of solving of this problem, which may be divided into two groups – the group of approximate methods and the group of interpolative methods. The methods of first group are based on the replacement of digital curve Γ by a such curve of some fixed class that satisfies to some conditions “nearness”. The methods based on the Bezier curves and on the B-spline are the most popular approximate methods of finding the curve representation [15], [13]. The application of those methods requires a prior detection of knots of spline and this task is equal to a general task of a curve representation. The methods of second group assumes the choice of some set of points on Γ and replacement of every part of curve between the two neighbor points by the other curve from some fixed class (for example, class of segments, circles, algebraic curves of some order etc.) in agreement with the defined optimal conditions. The straight-line interpolation is called by polynomial representation of curve. There are two main approaches of solving the task of polynomial representation of curve: heuristic and optimization. The algorithms based on extraction of dominant points, on the using of split-junction procedure for a side of polygon (for example, Douglas-Peucker algorithm), genetic algorithms [6], algorithms of multiple smoothing [24], algorithms on the fuzzy logic [11] etc. are referred to the algorithms of the first approach. These algorithms are rapid but not optimal as a rule. Algorithms of the second approach assume to find such approximate polygonal line which satisfied to a defined optimal condition. The conditions which are considered as an optimal criterion are following: 1) the polygon with fixed number of vertex must have minimal perimeter [23]; 2) the maximal distance between the points of the curve and segments of the polygon must be a minimal [18]; 3) the number of segment of polygon with approximation error must be a minimal [4]; 4) the area of a symmetric difference between the set bounded by a closed curve and set bounded by the polygon must be a minimal [28]; 5) the approximation error of polygon with a fixed length of a segment must be a minimal [21]. Thus the algorithms of second approach solve tasks of nonlinear optimization with boundary conditions. The majority of algorithms mentioned above are suboptimal. Almost all algorithms of finding of compact polygonal representation assumes the preliminary finding of basis set of curve points which must be optimized with a respect to the chosen criteria. The set of points with a high curvature is chosen as a basis set. At this paper we will consider the approach to find polygonal representations of curve with a help of fuzzy clustering methods. The main idea of this approach bases on a fact that the quantitative low-level local features of a curve at the given point may be considered as a degree of membership of this point to polygonal representation. The curve itself is considered as a fuzzy set. Then a problem of finding of a minimal representation of a fuzzy set may be formulated as a solution of a task of a fuzzy clustering. 2
We will considered the plane discrete curve Γ = (gk)kn=−01, gk = xki + ykj. The points gk, k = 0, ..., n − 1 , belongs to ZZ2 and they satisfy to a condition of a connectivity in the initial contour which will be used in an image processing. We will consider the set of points of curve Γ as an ordering set. We want to extract some subset B = {gi1 , ..., gil } of points of a curve Γ that will be a “good” representation of Γ .
The minimal polygonal representations of curve must consist of such points g of curve Γ which have a great information capacity relatively to a given set of features {ωi}i∈I . We will consider only local features: low-level features of curve. We may be consider those features as some functions of points of curve: ωi(g), g ∈ Γ , i ∈ I. It will be assumed that ωi(g) ∈ [0, 1] for all g ∈ Γ , i ∈ I and ωi(g) ≤ ωi(h) , if the point h ∈ Γ is more informative than point g ∈ Γ relatively of feature ωi. The normalized estimation of curvature and the normalized variation of contour length after deletion of point g are by examples of such features functions [2]. The function ωi(g) characterizes the degree of membership of point g to set informative points of curve Γ relatively i-th feature. Therefore the set of informative points of curve Γ relatively i-th feature may be considered as a fuzzy set {(g, ωi(g)), g ∈ Γ } with membership function ωi. If we consider the information capacity of points of curve Γ relatively to the set of features {ωi}i∈I set Γ can be considered in terms of a fuzzy set with membership function ω(g) = T (ωi(g)), where T (·) – t-norm on [0, 1]I [9]. For example, T (ωi) = min ωi or T (ωi) = Qi∈I ωi. In general case we can use some nonnegative i function from feature μΓ (g) = f (ω (g)) as a membership function. Then we may formulated the task of finding of such minimal fuzzy subset B of set Γ for which the set {ω(g)}g∈B will be an optimal representation of {ω(g)}g∈Γ . Let’s specify a statement of problem. Let’s consider α-cut Bα = {g ∈ Γ : ω(g) ≥ α{ of fuzzy set Γ for some fixed value α ∈ [0, 1]. The set Bα is a some representation of a contour Γ . It is necessary to find such value of parameter α ∈ [0, 1] that the representation Bα will be minimal on the one hand and will be optimal on other hand. The finding of minimal representation of a fuzzy set is a task of fuzzy clustering. The main ways to solve a fuzzy clustering task were considered in the works [19],[20], [5], [1] etc. The review of fuzzy clustering methods may be found in [29]. The modern state of problem may is reviewed in [12]. One approach to fuzzy clustering consists to definition of some functionals on the set of all representations, which then are optimized to receive a desired clustering. 3
Let us consider representation Bα of contour Γ , α ∈ [0, 1] with membership function μωα(g) = 0ω, (g)|Bα|, gg ∈∈/ BBαα., We are introduced into consideration so called fuzzy similarity relation r(g, h) on Γ that is reflexive, symmetric fuzzy relation satisfying to inequality |r(g, h) − r(g, e)| ≤ 1 − r(h, e) for all e, g, h ∈ Γ for construction of identifying functional. The last inequality is an equivalent to condition for strongly Δ -transitive relation (respect to t-norm aΔb = max{a + b − 1, 0}) [7]. The equivalence of strongly Δ-similarity (that is reflexive, symmetric, strongly Δ-transitive relation) and Δ-similarity was proved in [7]. The coherent nearness relation [3] is weak. By analogy with E.H.Ruspini we called set Bα by fuzzy r-representation of set Γ if the inequality X r(g, h)μωα(h) ≥ μΓ (g) h∈Γ (1) is holds for all g ∈ Γ . The efficiency of such clustering depends on a fuzzy similarity relation r(g, h). The choice of this relation is defined by classification features. In particular, the function r(g, h) = 1− n−1 Pin=1 ρi(ωi(g), ωi(h)) is the similarity relation, where ωi(g) is an informativity function of the i-th feature of point g, ρi is such metric in R1 that ρi(a, b) ≤ 1 for all a, b ∈ [0, 1]. We will consider the similarity relation r(g, h) = 1− |ω(g) − ω(h)| below. Then (1) take the form |Bα| X (1 − |ω(g) − ω(h)|) ω(h) ≥ ω(g)|Γ |
h∈Bα
for all g ∈ Γ . It is obvious to see that Bα = Γ povided (
max ω(g). g∈Γ \Bα Thus we proved the validity of the following proposition.
Proposition 1. If set Bα is a fuzzy r-representation of set Γ then (3) is correct.
The contrary of this statement may be is not true in general. The algorithm
of finding of minimal representation Bα consists of two steps: 1) to find the set
B(α1) of minimum cardinality for which (3) is valid; 2) to add (if it is necessary)
⌢
the set B(α1) by such points h ∈ Γ \B(α1) that (
Q(p) := X p i=1
(1 − ω(hi))ω(hi) R(p) := |Γ | − X p p i=1 ω(hi)
max
p+1≤j≤|Γ |
ω(gj )
(
X (1 − ω(h))2 ≤ 1 + |B| − h∈B
|Γ | B + 1 and |Γ | max ω(g) ≤ α2|B|2 then B(α1) will be a minimal fuzzy r-representation of g∈Γ a curve Γ .
Proof. Firstly we show that the representation B(α1) formed on the first step of algorithm is a minimal representation for which (3) is satisfied. To show this we consider the set function φ(B) = X (1 − ω(h))ω(h) h∈B , |Γ | |B|
! − X ω(h) , h∈B where B ⊆ Γ such that Ph∈B ω(h) < ||ΓB|| . Let φ(∅) = 0. Let us show that φ is monotone set function. Let Si = Ph∈B ωi(h), δi = |B||+Γi|−1 , i = 1, 2. Then φ(B) = Sδ11−−SS12 . We have ψ(ω(g)) = φ(B ∪ {g}) =
S1 − S2 + ω(g) − ω2(g)
δ2 − S1 − ω(g)
for such every g ∈ Γ \B that ω(g) + Ph∈B ω(h) < |B|Γ|+|1 . Then φ(B ∪ {g}) −
φ(B) = δω2(−gS)−1−ωω2((gg)) + ψ((δS2−1−SS1−2)ω(δ(1g−))δ(2δ+2−ωS(g1))) ≥ 0 such as S1 ≥ S2, δ1 ≥ δ2.
Therefore φ is a monotone set function. In addition ψ (x) is a monotone function on
[0, 1]. Indeed, we have ψ′(x) = x2−2x(δ2−S1)+δ2−S2 . Two cases are possible. At
(δ2−S1−x)2
the first case the minimal value of numerator of derivative ψ′(x) up to x = 1
if δ2 − S1 > 1. In this case we have ψ′(x) ≤ 0 if δ2 ≥ 1 + 2S1 − S2 ⇔ (4). At
the other case 0 ≤ δ2 − S1 ≤ 1 and the minimal value of numerator of
derivative ψ′(x) up to x = δ2 − S1 and ψ′(x) ≥ 0 if δ2 − S2 − (δ2 − S1)2 ≥ 0. The
last inequality is true because δ2 − S2 − (δ2 − S1)2 ≥ δ2 − S1 − (δ2 − S1)2 ≥
0 = (δ2 − S1) (1 − (δ2 − S1)) ≥ 0. Therefore φ is a monotone set function and
φ(B ∪ {g′}) ≥ φ(B ∪ {g′′}) if ω(g′) ≥ ω(g′′). We may get two cases when we
form the set B(α1): 1) Ph∈B(α1) ω(h) < |B|Γ(α1|)| ; 2) there exist such point g ∈ B(α1)
that |B|Γ(α1|)| − ω(g) < Ph∈B(α1)\{g} ω(h) < |B|Γ(α1|)| . The set B(α1) will be by set with
minimal cardinality which satisfied to (3) since the set B(α1) in the first case and
the set B(α1)\{g} in the second case formed from the points h ∈ Γ with maximal
value of feature ω(h). We will show the validity of inequality (
X (1 − |ω(g) − ω(h)|) ω(h) ≥ α X ω(h) ≥ h∈B(α1)
h∈B(α1) α2 B(α1) ≥
|Γ | |Γ | |B(α1)| mg∈aΓx ω(g) ≥ |B(α1)| ω(g).
If we get on the first step of algorithm the set B(α1) for which conditions of proposition aren’t satisfied we must carry out the second step of algorithm. In this case we may to get the set Bα near to minimal in general.
Remark 1. The function rs(g, h) = 1 − |ω(g) − ω(h)|s, s ∈ (0, 1], may be used in the capacity of similarity relation too. This function satisfies to all conditions of similarity relation because the inequality (a + b)s ≤ as + bs is correct for a, b ≥ 0, 0 ≤ s ≤ 1. It is obvious that the inclusion Bα(s1) ⊇ Bα(s2) is correct for minimal rs-representation Bα(s) if 0 < s1 ≤ s2 ≤ 1 because rs1 ≤ rs2 in this case. 4
Other relation may be used in task of fuzzy clustering without similarity relation. For example, the points of minimal polygonal representation must be located far from each other on a curve Γ . We may introduce the fuzzy dissimilarity relation regarding these conditions. This relation must be antireflexive, symmetric fuzzy relation τ (g, h) and obeying to an inequality |τ (g, h) − τ (g, e)| ≤ τ (h, e) for all e, g, h ∈ Γ . Note that definition of fuzzy dissimilarity relation is coordinated with a fuzzy similarity relation that is introduced above. Let f (g) be membership function of point g ∈ Γ to the set of informative points. Again we will call the set Bβ = ng ∈ Γ : μfβ(g) ≥ βo with membership function μfβ(g) by fuzzy τ representation of set Γ if the inequality
X (1 − τ (g, h)) 1 − μfβ(h) ≥ 1 − f (g) h∈Γ (5) is correct for all g ∈ Γ . We will considered that condition (5) is valid if Bβ = ∅ and isn’t valid if Bβ = Γ . Thus the task is to increase maximally the cardinality of Bβ (with decreased β) until (5) remains is valid. The set Bβ of maximum cardinality for which (5) is valid we will call a maximal τ -representation of set Γ and will denote by B¯ β.
We will use the function τ (g, h) = l(g, h) as a dissimilarity relation. Here
l(g, h) is a minimal length of arc of the curve Γ located between the points
g, h ∈ Γ , that normed by length of all curve Γ . We will use also the functions
f (g) = ω(g)|Γ | and μfβ(g) = |Γ \Bβ| 1f (g),, gg ∈∈/ BBββ, as a membership function
of curve Γ and set Bβ correspondingly. Then inequality (5) can be rewritten:
|Γ \ Bβ| X (1 − l(g, h)) (1 − f (h)) ≥ |Γ | (1 − f (g))
(6)
h∈Γ \Bβ
for all g ∈ Γ . Then the new formulation of task about seach of (r, τ )-representation
of curve Γ follows from (
X (1 − |ω(g) − ω(h)|) ω(h) ≥ h∈B |Γ | |B|
ω(g), X (1 − l(g, h)) (1 − ω(h)) ≥
(1 − ω(g)) h∈Γ \B
|Γ | |Γ \ B|
X h∈Γ \B(α1) are holds for all g ∈ Γ . We have a question: in what case does the algorithm give us the minimal (r, τ )-representation of curve Γ ? The next statement follows from proposition 2.
Proposition 3. If after the first step of algorithm we get such representation B(α1) that (4) is true and |Γ | max ωI (g) ≤ α2 B(α1) 2, |Γ | min ωI (g) ≥ |Γ | − g∈Γ g∈Γ 0.5(1 − α) Γ \B(α1) 2 then B(α1) will be a minimal fuzzy (r, τ )-representation of closed digital curve Γ .
Proof. If the conditions of proposition are satisfied, then the set B(α1) will be a minimal fuzzy r-representation as was shown in proposition 2. Now we should proof that the set B(α1) will be fuzzy τ -representation too. To show this, it’s noticed that Ph∈A l (g, h) ≤ 0.5 |A| for closed curve and any point g ∈ Γ , A ∈ 2Γ . Then we have (1 − l (g, h)) (1 − ω(h)) ≥ (1 − α) (1 − l (g, h)) ≥ 0.5(1 − α) Γ \B(α1) ≥
|Γ | Γ \B(α1)
X h∈Γ \B(α1) 1 − min ω(g) .
g∈Γ
The results of the algorithm of a research of minimal polygonal representation of contour are shown in Fig.1. On the Fig.1.a the representation was found by fuzzy clustering method with help of similarity and dissimilarity relations separately. On the Fig.1.b the representation was found by fuzzy clustering method with help of combined using of similarity and dissimilarity relations. We used normalized estimation of curvature in the capacity of feature function ω(g) (see [10]). Note that the quality of algorithm work may be improved if we will use the fuzzy clustering for the few features. 5
In this paper we have considered two clusters in a polygonal representation of a curve. The first cluster consists of points that belong to the polygonal representation. The second cluster consists of points that not belong to the polygonal representation. In case of the crisp clustering distance within one cluster is small, whereas clusters are sparse, so two objects from different clusters are distant. The notion of distance at this paper was replaced by similarity and dissimilarity fuzzy relation. We have received the fuzzy clustering method for polygonal representation. The quality of this representation depends on a similarity and dissimilarity fuzzy relation. 6
This work was supported by the grant 11-07-00591 of RFBR (Russian Foundation for Basic Research). The study was undertaken in the framework of the Programme of Fundamental Studies of the Higher School of Economics in 2011. [9] [10]