Patent ID: 8428363

Claim:
A method for segmenting an image into superpixels, comprising the steps of: constructing a graph with vertices connected by edges, wherein each vertex corresponds to a pixel in the image, and each edge is associated with a weight indicating a similarity of the corresponding pixels; selecting a subset of edges in the graph to segment the graph into subgraphs, wherein the selecting maximizes an objective function, wherein the objective function is submodular and includes an entropy rate of a random walk on the graph to produce homogeneous superpixels and a balancing term including an entropy component of distribution of membership of segments maximizing a number of segments of similar sizes and a number of connected subgraphs component minimizing a number of segments; and adding the edge with a maximum gain to the graph until a number of subgraphs is equal to a threshold, and repeating the selecting and adding steps if the number of subgraphs is below the threshold, wherein the steps are performed in a processor.