[GO] Implemented image segmentation in python (Union-Find)

Previous article was interesting because I had a little bit of image processing, so this time I read the paper and tried to implement simple image processing. (It looks like the image below.)

src	dst

The paper I read this time is relatively old (2004) and the implementation itself did not seem to be so difficult, so I tried it. (However, it is not as good as the result published in the paper ...)

The source code for this time is posted on github. https://github.com/aratakokubun/GraphBasedSegmentationWithUnionFind.git

Overview of image processing

This time, we implemented the image area division process, which is the brightness. As a condition for combining, the boundaries (Edge) with neighboring pixels are judged in ascending order, and the areas are combined one after another.

algorithm

Do 1-5 below to get a list of independent Components as a result. This Component is the area where the pixels are combined.

1. Extract all the edges of each pixel within 8 neighborhoods (grid) or within a certain distance (nearest-neighbor). In the initial state, all pixels are not combined, and each element is treated as a Component.
2. For each pixel, calculate the value used as the basis for coupling.
   For example, in this case, the luminance value (luminance) is used, and pixels having similar luminances are combined as the same region.
3. Measure the difference (diff) of each extracted Edge and sort in ascending order of diff value.
4. Repeat step 5 in ascending order of Edge
5. If the value of Edge is smaller than the internal difference (MInt) of the Components on both sides of the boundary, the two Components are combined into one Component.
   

• This step will be described in detail in Edge connection conditions.

Edge join condition

Regarding the combination in step 5, the difference diff of Edge and the internal difference Mint of two Components C1 and C2 are combined under the following conditions.

diff <= MInt(C1, C2)

The internal difference Mint of two Components is defined as follows.

MInt(C1, C2) = min(Int(C1)+τ(C1), Int(C2)+τ(C2))

The internal difference Int of each Component takes the maximum value of the boundary ever bound to the Component. If Component is a 1-pixel element, it will be 0. (However, this statement is not strictly correct, so see Reference 1 for more information.)

In addition, τ is a boundary value function according to the size of Component, and is defined as follows.

τ(C) = k/|C|

k is a constant parameter, and the larger k, the easier it is for Edge to join and the resulting Component to be larger.

Techniques for speeding up

An algorithm called Union-Find is used to speed up the process.
Union-Find considers subsets of S that are relatively prime to the set S. In the image area division process this time, the set S corresponds to an image that is a set of pixels, and the subset corresponds to a Component. This is called DisjointSet, and the union and find operations are defined as follows.

• union(C1, C2) Subsets C1 and C2 are merged into C1. (This corresponds to the process in step 5 of combining Components.)
• find(a) Gets the subset to which element a (pixel) belongs.

At the time of this union processing, the representative element of each Component is defined one by one, and the link is made from each element of the combined side (C2) to the representative element of the connecting side (C1). By doing so, you can easily implement the process with one array.
In addition, Uion-Find by Tree can be used for even higher speeds.

The implementation method is not described in detail here, but please refer to Reference 2 for a fairly detailed explanation of Union-Find. In addition, Reference 3 also explains the amount of calculation, so please refer to it as well.

result

The result implemented by python this time is as follows. The top 40 with the largest area size are colored instead of all areas.

src	dst

The source code for this time is posted on github. https://github.com/aratakokubun/GraphBasedSegmentationWithUnionFind.git

References

1. Efficient Graph-Based Image Segmentation
   http://cs.brown.edu/~pff/papers/seg-ijcv.pdf
2. Implementation of Union Find
   http://www.geocities.jp/m_hiroi/light/pyalgo61.html
3. Disjoint-Set Data Structures
   http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/lecture-notes/MIT6_046JS12_lec16.pdf