# Fast Equipartition of Complex 2D Shapes with Minimal Boundaries +
## 5 Methodology  
### SEP-Fast Balanced Clustering  
This Section presents the proposed fast balanced clustering method (_SEP-FBC_) that sub-optimally solves the 2D-SEP in O(\(N\cdot|S|\cdot log(|S|)\)), where \(|S|\) denotes the number of image pixels. The pseudo-code of the proposed _SEP-FBC_ method is given in Algorithm 1. The input of _SEP-FBC_ is the shape \(S\) (e.g., a binary image) and the number of the desired regions \(N\) of equipartition. The output is the segmentation \(R\) according to the constraints of the problem, as defined in Section 3. In the following, we analyze all the steps of the _SEP-FBC_ method. _SEP-FBC_ consists of two stages:  
```
input :\(S,N\) output :\(R\)
1G = shapeToGraph(S) /* Converts S to 8-pixel connectivity graph G */
2C = [ k-means(S,N)) ] /* Estimation of the \(N\)-clusters centroids */
3 foreach\(i\in\{1,\ldots,N\}\)do
4 ifS(C(\(i\))) = 0 then
5C(\(i\)) = get_closest_point(C(\(i\)),S) /* Returns the nearest pixel of S */
6 end if
7\(R_{i}=\emptyset\)
8\(GD_{8}(i)=distances(G,C_{i})\) /* Graph-based distances from \(C_{i}\) */
9
10 end for
11 foreach\(p\in S\)do
12 foreach\(i\in\{1,\ldots,N\}\)do
13\(\widehat{GD}(i,p)=max(\frac{\sqrt{5}}{\sqrt{2}+1}GD_{8}(i,p),|C(i)-p|_{2})\)
14 end for
15\(c=argmin_{i\in\{1,\ldots,N\}}(\widehat{GD}(i,p))\)
16\(R_{c}=R_{c}\cup\{p\}\)
17 end for
18R = correctConnectedComponets(R)
19R = smoothBoundaries(R)
20\(RR=O_{N\times N}\)
21 while\(\sum_{i=1}^{N}||R_{i}|-\frac{|S|}{N}|>2\cdot N+1\)do
22\(c=\operatorname*{argmin}_{i\in\{1,\ldots,N\}}(|R_{i}|-\frac{|S|}{N})\)
23\([R,RR]=areaGrov(R,RR,c)\) /* Grows the smallest region \(c\) */
24
25 end for
```  
**Algorithm 1**The proposed _SEP-FBC_ method  
In the first stage, the hard clustering of the shape pixels is performed (lines 1-16 of Algorithm 1). * Initially, a graph \(G\) of the connected pixels from the 2D image space of shape \(S\) is computed using eight pixel connectivity. This graph is used to approximate the shortest path distance between the shape points of the complete graph (see Appendix A). * Then, an initial estimation of the centroids of the \(N\) clusters (\(C=\{C_{1},\ldots,C_{N}\}\)) is calculated by the k-means++ method [26] (with computational cost \(O(N\cdot|S|)\)) followed by the round operation \([. ]\) to adjust \(C\) to the space of the image coordinates (see line 1 of Algorithm 1). In the case where \(C_{i}\) does not belong in shape S (\(S(C_{i})=0\)),\(C_{i}\) is set to the nearest shape pixel. This is conducted by the _get_closest_point_ procedure (see line 5 of Algorithm 1 and Equation (9)). \[get\_closest\_point(C(i),S)=\operatorname*{argmin}_{p\in S}|C(i)-p|_{2}\] (9) where the centroid \(C_{i}\) corresponds to the region \(R_{i}\). * Furthermore, we initialize each region \(R_{i}=\emptyset,i\in\{1,\dots,N\}\) and compute for each region \(R_{i}\) the vector \(GD_{8}(i,:)\) with all the eight-connectivity graph-based distances between the centroid \(C_{i}\) and the shape points (see lines 7-8 Algorithm 1 and procedure _distances(G,C,i)_) (the computational cost of this process is \(O(N\cdot E\cdot log|S|)=O(N\cdot|S|\cdot log|S|)\) using the Dijkstra algorithm with the Adjacency List and Heap, since it is executed \(N\) times and the number of edges of the graph \(G\) is \(E=O(|S|)\), due to the fact that each node of the graph has a limited number of neighbors (up to eight neighbors)). The initial clustering of shape pixels is performed using an approximation by the combination of the Euclidean distance and \(GD_{8}(. )\) (see line 12 of Algorithm 1) of the graph-based distance of a complete graph of shape \(S\). The use of graph-based distances for clustering provides better image component connectivity for clusters compared with the use of the pure Euclidean distance. This is due to the fact that graph-based distances take into account the component connectivity, while the pure Euclidean distance is directly computed from the pixels' coordinates (see Figure A1b of Appendix A).