Patent Document ID: 9483715
Application ID: 14669518
Patent Status: 1

Claim One:
1. A classifying device for classifying each pixel forming image data into one of N labels, where N>2, which are ordered from 0 to N−1, the classifying device comprising: a processor configured to assign each pixel with one of the N labels (i) by using a graph that includes k layers, where k=N−1, which are set between a vertex s and a vertex t and each of which layers is a boundary between the labels, vertices w α v , where α=1,. .. , k, which are set on each layer α, where α=1,. .. , k, and which vertices correspond to locations v of individual pixels of the image, and edges each connecting two of the vertices w α v , the vertex t, and the vertex s, and (ii) by determining edges to be cut among the edges by a graph cut operation, wherein the processor is configured to execute the following instructions, which comprise: setting, for each i-th layer i that is the boundary between a label i−1 and a label i of the N labels, a binary graph including edges each connecting two of the vertices w i v , the vertex s corresponding to a virtual label 0, and the vertex t corresponding to a virtual label 1, wherein the virtual label 1 indicates that a label that is equal to or higher than i is assigned to the location v corresponding to the vertex w i v on the layer i, and the virtual label 0 indicates that a label that is equal to or lower than i−1 is assigned to the location v corresponding to the vertex w i v on the layer i; setting an energy for each edge of the binary graph for each layer depending on which of the virtual label 0 and the virtual label 1 each vertex belongs to; assigning one of the virtual label 0 and the virtual label 1 to each vertex w i v on each layer by determining edges to be cut among the edges of the binary graph of the layer by performing a graph cut operation on the entire graph including the binary graphs for the individual layers with the energies set therefor, and determining which of the N labels the pixel at each location v belongs to depending on which of the virtual label 0 and the virtual label 1 is assigned to each vertex w i v , where i=1,. .. , k, on the first to the k-th layers, which corresponds to the same location v, wherein the binary graph includes an edge that connects two vertices w i v on the same layer i to each other, an edge (s,w i v ) that connects the vertex s to each vertex w i v , and an edge (w i v ,t) that connects each vertex w i v to the vertex t, wherein the processor determines, for each vertex w i v , that the label 0 is assigned to the pixel corresponding to the vertex w i v if all the vertices w i v corresponding to the same location v on all the layers belong to the virtual label 0, that the label N−1 is assigned to the pixel corresponding to the vertex w i v if all the vertices w i v corresponding to the same location v on all the layers i belong to the virtual label 1, and that the pixel corresponding to the vertex w i v belongs to a class p if the vertices w i v corresponding to the same location v on the first to the p-th layers belong to the virtual label 0 and the vertices w i v corresponding to the same location v on the p+1-th to the N−1-th layers belong to the virtual label 1, and wherein the processor sets a fourth- or higher order energy, which is determined depending on whether or not all of arbitrary four or more vertices on the same layer belong to the virtual label 0 or the virtual label 1, for each of edges that connect the four vertices w i v to the vertex s or the vertex t via a virtual vertex v i for each layer.