An Efficient Region Merging Algorithm in Raster Space

This work introduces a new region merging algorithm operating in raster space represented by a 4-connected graph. Necessary definitions are introduced first to derive a new merging function formally. An implementation is described after that, which consists of two steps: a determination of the shared trails of the input cycles, and construction of the resulting merged region. The cycles defining the regions are represented by the Freeman crack chain code in four directions. The algorithm works in linear time On, where n is the number of total graph vertices, i.e. pixels. However, the expected time complexity for one merging operation performed by the algorithm is O1