Patent ID: 7697756

Claim:
An image segmentation device comprising: a memory device storing an image of interest and a plurality of instructions for segmenting the image of interest; and a graphics processing unit for receiving the image of interest and executing the plurality of instructions to perform a method comprising, specifying a plurality of seed points in the image of interest; determining a graph of nodes representing the image, wherein each node corresponds to a pixel of the image and neighboring edge weights between neighboring nodes represent differences in image intensities between neighboring pixels, wherein determining the graph comprises determining a Laplacian matrix having five diagonal bands, wherein four secondary bands hold the edge weights and a main band is a sum of the four secondary bands and storing the Laplacian matrix of edge weights as a texture representation having a plurality of channels; determining a vector texture of vector data representing different potential labels of the nodes, the vector data for each label is determined by matrix-vector multiplication of the secondary diagonals, the main band, and a sample vector for each node from the first texture; determining a probability that a node of the graph belongs to each potential label, wherein the probabilities are determined for each node in parallel as a conjugate gradient vector of the vector texture; assigning each node a most probable label based on the probabilities; and outputting a segmentation of the image of interest according to label assignments to the nodes, wherein the segmentation differentiates portions of the image of interest.