A Branch-and-Bound Technique for Nano-Structure Image Segmentation

Abstract

Images of nano-structures are often noisy. On the other hand, in many settings there is quite a lot of model knowledge regarding the observed structures. This paper proposes a method for segmenting an image using a geometric model of the the observed structure. The resulting segmentation is guaranteed to be globally optimal, for an explicitly specified score function. This property provides a great deal of robustness to the algorithm. The algorithm presented explores a pre-defined space of segmentations using a branch-and-bound algorithm. It eliminates those parts of the space that are provably poor and explores in further detail the more promising parts of the space. An example of a segmentation that can be obtained in this way is a straight line segmentation of an image into 2 regions that minimizes the intensity variation within the regions. Results showing extraction of specific nano-structures are presented. A trivial variation on the algorithm can find a maximum a-posteriori probability estimate of the segmentation when there exists an a-priori distribution over the segmentations and the objective function is interpreted as the likelihood of the image given the segmentation.