Concave-point Based Contour Segmentation

The concave-point based methods in [7] applied to overlapping object segmentation perform the task of contour evidence extraction by combining a contour splitting method with ellipse fitting.

Here, the key feature is to extract the concave points by which the contour points are segmented.

The concave-point based algorithm used in this thesis work is from [7] and includes five specific steps, see Algorithm 6.

The first step is to estimate and generate the contours per each connected object. Either edge

Algorithm 5:Edge-to-Marker Association [9]

Input: binary silhouette imageI, the set of object markersM ={M⁽¹⁾, M⁽²⁾, ..., M⁽ⁿ⁾}.

Output: Indexed contour setC ={C⁽¹⁾, C⁽²⁾, ..., C^(m)}.

Parameters: the divergence weight factorλ, the minimum number of edge pointsρn, the maximum distance from edge points to potential markersρ_d

1. Compute the set of edge pointsE ={e₁, e₂, ..., e_k, ...}.

2. For each the edge pointsek ∈E:

(a) Collect the nearest seedpoints into the search regionM_SR, the points not far thanρ_d (b) Estimate the relevance metric with respect to the marker pointsM_j⁽ⁱ⁾in the search

regionM_SR, Equation 19.

(c) Assigne_kto each marker with the highest degree of relevance and constructCa contour evidence set referenced by marker indices.

3. Discard any marker whose number of assigned edge points is less thanρ_n.

Algorithm 6:Concave-point based contour segmentation [7]

Input: Grayscale imageI

Output: Indexed contour setC ={C⁽¹⁾, C⁽²⁾, ..., C^(m)}.

1. Transform the input image to a binary image silhouetteI_BW and estimate the image smoothed contour point setC ={c₁, c₂, ...}.

2. Determine the contour breaking point setCbreak={cb,1, cb,2, ...}by co-linear point suppression.

3. Determine contour dominant point setC_dom ={c_d,1, c_d,2, ...}by polygonal approximation (Algorithm 7).

4. Segment the obtainedC_dom as per concave pointsC_con ={c_c,1, c_c,2, ...}obtained by Equation 24.

5. Perform contour segment grouping.

detection or image morphology may be used to build up the contour set per each connected object in the image.

The second step is to determine the breaking points C_break = {c_b,1, c_b,2, ...}. Given the image silhouette I_BW and the sequence of extracted contour points C = {c₁, c₂, ...}, the breaking points are determined by co-linear suppression. To be specific, every contour pointci(xi, yi) is examined for co-linearity, while it is compared to the previous and the next successive contour points. c_i(x_i, y_i)is considered a breaking point provided if it is not located on the line connecting ci−1(xi−1, yi−1)andc_i+1(x_i+1, y_i+1).

The third step is to filter the extracted breaking point for the dominant pointsC_dom ={c_d,1, c_d,2, ...}.

Dominant points are the points with extreme local curvature. Technically, the dominant point set C_domis a subset ofC_breakwhose redundant members are eliminated through the process of polyg-onal approximation. The redundant points are detected and discarded by means of break point suppression; a typical approach for polygonal approximation. In this way, the initially defined dominant setC_dom withC_break is pruned by removing redundant points, but preserving a mini-mum error value. That is, the dominant points iteratively are discarded untill the minimini-mum error condition is exceeded.

In polygonal approximation, there are several metrics to measure the error of the approximate model from the discrete true contour model. Here, the sum of the square error (SSD) is adapted

SSD = The steps to find the dominant points are presented in Algorithm 7.

The forth step of Algorithm 6 is involved with extraction of concave points that form the contour segments. The connecting points are resolved through concave points. The dominant point

Algorithm 7:Dominant point estimation [7]

Input: Contour break point setC_break. Output: Contour dominant point setC_dom. Parameters: The distance threshold valueρdist

1. InitializeC_dombyC_break.

2. For eachc_d,i(x_i, y_i)∈C_dom, estimate the distanced_iofc_d,i to the chord connecting cd,i−1(xi−1, yi−1)tocd,i+1(xi+1, yi+1), Equation 23.

3. Eliminate anyc_d,i fromC_domwithd_i less thanρ_dist.

c_d,i ∈C_domis considered to be the connecting point ifc# »d,i−1c_d,i×c# »_d,ic_d,i+1 is positive

C_con ={c_d,i ∈C_dom : c# »d,i−1c_d,i ×c# »_d,ic_d,i+1 >0}. (24) The final step in concave-point contour segmentation is to group the contour segments. The contour segmentsS = {s₁, s₂, ..., s_ns}are divided to the target and the candidate segments and grouped.

The criteria to divide the contour segments are their length and their condition whether they have been grouped or not. Here, the main idea is to distinguish the short and noisy contour segments from the ones containing the potential of being an individual contour segment. In this way, the segment which still is not assigned to any other segments group is considered as a candidate segments_c,i ∈ S_c and the segment whose length is greater than the specific limit is the target segments_t,i ∈S_t.

The contour segment grouping is carried out through the process of ellipse fitting applied to the target, candidate, and joint target-candidate contour segments and eventually examining the goodness of fitted (GoF) ellipse with respect to the actual segments. The main objective is to find the group of contour segments that all together could form a particular ellipse shape object. That is, the candidate segments_c,i is merged into the target segments_t,i, provided that the goodness of ellipse fitted to the joint target-candidate segments are improved compared to the ellipse fitted to the individual target and the candidate segments alone:

GoF(s_t,i ∪s_c,j)≤GoF(s_t,i) + GoF(s_c,j). (25)

The goodness of fit is described as the Average Distance Deviation (ADD) which measures the discrepancy between the fitting curve and the contour segment under the ellipse model in question. For a given contour segment

s_k={c_k,1(x₁, y₁), c_k,2(x₂, y₂), ..., c_k,n(x_n, y_n)} (26) and the corresponding fitted ellipse points

s_k,f ={c_k,f1(x_f1, y_f1), c_k,f2(x_f2, y_f2), ..., c_{k,f n}(x_{f n}, y_{f n})}. (27)

Within the transformed coordinate system

"

Equation 28 can be simplified to

ADD_k= 1

where a, b, (x_eo, y_eo) andθ are the ellipse standard parameters, major axis length, semi-minor axis length, ellipse center point, and the ellipse orientation angle with respect to x axis, respectively. The detailed pseudo code of contour segment grouping is shown in Algorithm 8.

Algorithm 8:Contour segment grouping [7]

Input: Contour segment setS ={s₁, s₂, ..., s_ns}

Output: Grouped contour segmentS_t={s_t,1, s_t,2, ..., s_t,nt}.

1. initialization: Candidate segment setSc← {s;s∈S,|s| ≥6}.

Target segment setSt←S.

2. Perform segment grouping:

i←1

while|S_t| ≥1do j ←1

while|S_c| ≥1do ifs_c,i *s_c,j

computeADD_tofs_t,i by Equation 26 computeADD_cofs_c,j by Equation 26 computeADD_tc ofs_t,i ∪S_c,j by Equation 26

if(ADD_tc<ADD_t+ ADD_c)∧(s_t,i nearest tos_t,i∪s_c,j) s_t,i ←s_t,i∪s_c,j

S_c←S_c\s_c,j ifsc,j ⊂St

S_t←S_t\s_c,j j ←j + 1

i←i+ 1

Eliminates_t,iif the enclosed angle is less than90^◦.