5. Maximally Occurring Common Subgraph Matching

This chapter describes a robust framework to solve image co-segmentation where the common object is not present in all the images in the set. The co-segmentation problem for N images considers the very general setting that only an unknown M (\(\le N\)) number of images contain the co-segmentable common object(s). This problem, in general, requires solving \(\mathcal {O}(N 2^{N-1})\) MCS matching steps. A computationally efficient method is described in this chapter that requires only \(\mathcal {O}(N)\) matching steps. This is achieved by performing maximally occurring common subgraph matching (MOCS) of the images in the set. The first step is to obtain a coarse co-segmentation of images using superpixel clustering that gives the common object partially. Then a ‘latent class graph’ (LCG) is constructed by combining the graphical representations of the partial object in all constituent images. Next the LCG is used for performing region growing on the graphs of individual images to obtain the common object completely. The co-segmentation method requires only \(\mathcal {O}(N)\) image matching operations, instead of \(\mathcal {O}(N 2^{N-1})\), and yet ensures globally consistent matching across images.