US Patent 7570811 Segmenting an image via a graph

A method is described for segmenting an image of pixels into a number of fields. A graph is constructed for representing the image. First, separating elements are constructed that are oblong areas of adjacent pixels having a background property indicative of a background of the image. Then vertices of the graph are defined based on intersections of separating elements that are substantially oriented in different separation directions, in particular horizontal and vertical direction, and edges of the graph are defined between the vertices corresponding to the separating elements. Finally, the edges of the graph are interpreted as lines that separate the fields.