Segmentation as Maximum-Weight Independent Set
Given an ensemble of distinct, low-level segmentations of an image, our goal is to identify visually meaningful" segments in the ensemble. Knowledge about any specific objects and surfaces present in the image is not available. The selection of image regions occupied by objects is formalized as the maximum-weight independent set (MWIS) problem. MWIS is the heaviest subset of mutually non-adjacent nodes of an attributed graph. We construct such a graph from all segments in the ensemble. Then, MWIS selects maximally distinctive segments that together partition the image. A new MWIS algorithm is presented. The algorithm seeks a solution directly in the discrete domain, instead of relaxing MWIS to a continuous problem, as common in previous work. It iteratively finds a candidate discrete solution of the Taylor series expansion of the original MWIS objective function around the previous solution. The algorithm is shown to converge to a maximum. Our empirical evaluation on the benchmark Berkeley segmentation dataset shows that the new algorithm eliminates the need for hand-picking optimal input parameters of the state-of-the-art segmenters, and outperforms their best, manually optimized results."
Code (0)
등록된 구현이 없습니다.
Tasks
SegmentationSimilar Papers 제목 키워드 기반
Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
In this paper, we propose a novel pooling layer for graph neural networks based on maximizing the mutual information between the pooled graph and the input graph. Since the maximum mutual information is difficult to comp…
Combinatorial OptimizationGraph ClassificationGraph Neural NetworkInductive BiasA Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems
Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is …
Approximate Cluster-Based Sparse Document Retrieval with Segmented Maximum Term Weights
This paper revisits cluster-based retrieval that partitions the inverted index into multiple groups and skips the index partially at cluster and document levels during online inference using a learned sparse representati…
Passage RankingRetrievalSegmentationA Secure and Disambiguating Approach for Generative Linguistic Steganography
Segmentation ambiguity in generative linguistic steganography could induce decoding errors. One existing disambiguating way is removing the tokens whose mapping words are the prefixes of others in each candidate pool. Ho…
Linguistic steganographySegmentationSteganalysisBoosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branch-and-reduce paradigm is the de facto st…