Improved Data Structures for Fast Region Merging Segmentation Using a Mumford-Shah Energy Functional

One of the more successful approaches to image segmentation involves formulating the problem as the minimisation of a Mumford-Shah functional and then applying region merging algorithms to approximate the minimiser. Moreover, it can be proved mathematically that such segmentations have desirable properties, and further, fast implementations are available. In this paper, we describe improvements to one such algorithm, the full lambda-schedule segmentation algorithm (FLSA). The FLSA maintains a list of merge costs (as measured by the Mumford-Shah functional) for all relevant pairs of neighbouring regions and at each step selects the best pair to merge from the list. This is done quickly and efficiently through the use sophisticated data structures. We present significant improvements to those data structures which further simplify the maintenance of the merge cost list. The new algorithm makes use of a new list, the edge list, which allows the regions neighbouring a newly merged pair to be searched more efficiently. Owing to a change in the way "multiple boundaries\´\´ are handled, the new segmentations may differ slightly from the old ones but we argue that they are equally valid. We refer to the new algorithm as the FLSA Edge List (FLSA-EL) algorithm.