Distributed Cosegmentation via Submodular Optimizationon Anisotropic DiffusionGunhee Kim1Eric P. Xing1Li Fei-Fei2Takeo Kanade11School of Computer Science, Carnegie Mellon University2Computer Science Department, Stanford University{gunhee,epxing,tk}@cs.cmu.edu [email protected] saliency of regions or objects in an image canbe significantly boosted if they recur in multiple images.Leveraging this idea, cosegmentation jointly segments com-mon regions from multiple images. In this paper, we pro-pose CoSand, a distributed cosegmentation approach fora highly variable large-scale image collection. The seg-mentation task is modeled by temperature maximization onanisotropic heat diffusion, of which the temperature max-imization with finite K heat sources corresponds to a K-way segmentation that maximizes the segmentation confi-dence of every pixel in an image. We show that our methodtakes advantage of a strong theoretic property in that thetemperature under linear anisotropic diffusion is a submod-ular function; therefore, a greedy algorithm guarantees atleast a constant factor approximation to the optimal solu-tion for temperature maximization. Our theoretic result issuccessfully applied to scalable cosegmentation as well asdiversity ranking and single-image segmentation. We evalu-ate CoSand on MSRC and ImageNet datasets, and show itscompetence both in competitive performance over previouswork, and in much superior scalability.1. IntroductionCosegmentation refers to a procedure that simultane-ously segments common regions from multiple images[6, 7, 13, 15]; leveraging an intuition that the saliency ofregions or objects in an image can be significantly boostedif they recur in multiple images. Cosegmentation has a widepotential in web-scale applications. For example, it canguide an interactive image editing by suggesting popularregions in the image database [1, 13], or summarize per-sonal photo collections by automatically segmenting highlyco-occurring object instances such as persons or dogs [7].Despite of the promising appeal of cosegmentation, veryfew algorithms are applicable to web-scale applications,which require cosegmentation to be not only scalable butalso adaptable to heterogeneous images with high vari-ability in content and complexity. In this paper, we ad-dress these problems with a new cosegmentation frame-work, which builds on a solid theoretical ground of submod-ular optimization, and is readily applicable to large-scaleimage collection with high variability. Our approach is eas-ily parallelizable; most computations occur independentlyon individual images, and then an integration step quicklymerges all outputs from individual images into a coherentcosegmentation result. We quantitatively show that our ap-proach outperforms state-of-the-arts methods [6, 7] on theMSRC datasets [17]. We also evaluate the scalability of ourmethod on the challenging ImageNet [4]. The magnitude ofthe dataset sizes in our experiments exceeds those of previ-ous work by orders of magnitude.The compelling performance and scalability of our ap-proach stem from a novel optimization formulation onthe anisotropic diffusion (which inspires the name ofour algorithm, CoSand, standing for Co-Segmentation viaanisotropic diffusion). The optimization problem underly-ing CoSand can be summarized in a single sentence as fol-lows; Given a system under heat diffusion and finite K heatsources, where should one place all the sources in order tomaximize the temperature of the system? In terms of imagesegmentation, the optimization corresponds to finding theK segment centers that maximize the segmentation confi-dence of every pixel in the image1. (e.g. the ideal segmen-tation is that every pixel has confidence one to be clusteredwith one of K segment centers). This idea is extended to thecosegmentation problem by constraining the source place-ments in multiple images to be coupled. This diffusion the-oretic optimization framework takes advantage of a strongtheoretical property that inspires an efficient computational1We use the following terminological correspondences between tem-perature maximization and image segmentation: temperature ≡ segmenta-tion confidence, heat sources ≡ segment centers, conductance or diffusivity≡ similarity between feature vectors of pixels.algorithm. We prove in our paper that, the temperature,which is to be optimized in our problem, is a submodularfunction if the system is under linear anisotropic diffusion.A well-known beneficial property of submodular functionsis that one can achieve at least a constant factor of the opti-mal solution by a simple greedy algorithm, which iterativelychooses K locations that maximize marginal temperaturegain. Such a greedy solution is particularly promising forcosegmentation tasks on large-scale image collections.1.1. Relations to Previous workSubmodular optimization: In recent years, submodularoptimization has emerged as a useful optimization tool in avariety of machine learning problems such as active learn-ing, structure learning, clustering, and ranking [8, 9]. Thesubmodular function is characterized as a diminishing re-turn property that states that, the marginal gain of addingan element to a smaller subset of S is higher than that ofadding it to a larger subset of S. Some typical submodularfunctions explored in machine learning include a cut func-tion in a graph and the entropy and the information gain ofGaussian random variables [8].To the best of our knowledge, our work is the first toaddress submodular optimization on diffusion in physics2.Cosegmentation: Cosegmentation is the problem ofjointly segmenting each of M images into K different re-gions [6, 7, 11, 13, 15]. Table 1 summarizes the compar-ison of our work and other unsupervised cosegmentationmethods. In summary, our approach is unique in termsof M and K. Most previous work has dealt with binaryfigure-ground segmentation (K=2) of small sized imagesets (mostly M=2 but M≤30 in [7]). On the other hand,our algorithm is able to perform segmentation of a large-scale dataset with any arbitrary K. We tested with M≥103images in our experiments, but a more scalable setup is alsoapplicable. The optimization methods for cosegmentationin most previous work, except [7], are based on the graph-cut algorithm. Hence, it is not straightforward for them tobe extended to arbitrary K-way cuts. In theory, the methodof [7] can perform cosegmentation with K>2, but it was notevaluated in