However, regions that straddle a tile border might be split up or lost if the fragments do not meet the segmentation algorithm's minimum size requirements.
The connectivity information inherent to graphs allows performing independent work on parts of the original image, and reconnecting them to yield an exact result as if processing had occurred globally.
A simple and comparatively space-efficient variant of this is a grid graph, whereby each pixel is connected to its neighbors in the four cardinal directions.
The final step calls for encoding pixel similarity information in edge weights, so that the original image is no longer needed.
A minimum spanning tree (MST) is a minimum-weight, cycle-free subset of a graph's edges such that all nodes are connected.
In 2017, Saglam and Baykan used Prim's sequential representation of minimum spanning tree and proposed a new cutting criterion for image segmentation.