Segmentation of a multi-column document

Abstract

A method for detecting a logical structure of an image of a document. The method includes identifying objects in the image of the document, constructing a graph dividing the identified objects in the image of the document, detecting an optimal path through the graph to locate regions in the image of the document, and dividing the image of the document into the regions based at least in part on the detected optimal path.

What is claimed: 
     
         1 . A method for detecting a logical structure of an image of a document, the method comprising:
 identifying objects in the image of the document;   constructing a division graph of the identified objects in the image of the document;   detecting at least one optimal path through the division graph to locate regions in the image of the document; and   dividing the image of the document into the regions based at least in part on the detected optimal path.   
     
     
         2 . The method of  claim 1 , wherein constructing the division graph is performed based on constructing an area diagram for the identified objects. 
     
     
         3 . The method of  claim 1 , further comprising constructing an adjacency graph based on the division graph, wherein constructing the adjacency graph comprises:
 assigning graph vertices corresponding to the identified objects;   identifying pairs of adjacent objects corresponding to pairs of objects divided by at least one edge in the division graph; and   joining each pair of adjacent objects by an edge of the adjacency graph.   
     
     
         4 . The method of  claim 2 , wherein constructing the division graph further comprises:
 identifying graph vertices and graph edges on the area diagram; and   creating a minimal graph relative to the identified graph vertices and graph edges.   
     
     
         5 . The method of  claim 1 , wherein detecting the optimal path further comprises assigning weight values to edges of the division graph, wherein the weight values are based upon analyzing mutual characteristics of at least one pair of identified objects. 
     
     
         6 . The method of  claim 5 , further comprising summing the assigned weight values to determine a total weight value for paths in the division graph, wherein the at least one optimal path is a path with the best total weight value. 
     
     
         7 . The method of  claim 1 , wherein detecting the at least one optimal path comprises:
 constructing at least one sub-graph of the division graph;   identifying connected components in the sub-graph;   constructing at least one path relative to the identified connected components; and   filtering the at least one path.   
     
     
         8 . The method of  claim 1 , wherein detecting the optimal path further comprises correcting the at least one optimal path by adding one or more patches. 
     
     
         9 . The method of  claim 3 , wherein dividing the image of the document into regions further comprises:
 removing at least one graph edge from the adjacency graph corresponding to the at least one optimal path;   identifying connected components in the adjacency graph;   constructing regions relative to the connected components in the adjacency graph; and   dividing the image of the document in the constructed regions.   
     
     
         10 . A system to detect a logical structure of an image of a document, the system comprising:
 a memory configured to store processor-executable instructions; and   a processor operatively coupled to the memory, wherein the processor is configured to:
 identify objects in the image of the document; 
 construct a division graph of the identified objects in the image of the document; 
 detect at least one optimal path through the division graph to locate regions in the image of the document; and 
 divide the image of the document into the regions based at least in part on the detected optimal path. 
   
     
     
         11 . The system of  claim 10 , wherein the processor is further configured to construct an area diagram for the identified objects. 
     
     
         12 . The system of  claim 10 , wherein the processor is further configured to:
 construct an adjacency graph based on the division graph, wherein, to construct the adjacency graph, the processor is further configured to:
 assign graph vertices corresponding to the identified objects; 
 identify pairs of adjacent objects corresponding to pairs of objects divided by at least one edge in the division graph; and 
 join each pair of the adjacent objects by an edge of the adjacency graph. 
   
     
     
         13 . The system of  claim 11 , wherein the processor is further configured to identify graph vertices and graph edges on the area diagram. 
     
     
         14 . The system of  claim 10 , wherein the processor is further configured to assign weight values to edges of the division graph, wherein the weight values are based upon analyzing mutual characteristics of at least one pair of identified objects. 
     
     
         15 . The system of  claim 14 , wherein the processor is further configured to sum the assigned weight values to determine a total weight value for paths in the division graph, wherein the at least one optimal path is a path with the best total weight value. 
     
     
         16 . The system of  claim 10 , wherein the processor is further configured to:
 construct at least one sub-graph of the division graph;   identify connected components in the sub-graph;   construct at least one path relative to the identified connected components; and   filter the at least one path.   
     
     
         17 . The system of  claim 10 , wherein the processor is further configured to correct the at least one optimal path by adding one or more patches. 
     
     
         18 . The system of  claim 12 , wherein the processor is further configured to:
 remove at least one graph edge from the adjacency graph corresponding to the at least one optimal path;   identify connected components in the adjacency graph;   construct regions relative to the connected components in the adjacency graph; and   divide the image of the document in the constructed regions.   
     
     
         19 . A non-transitory computer-readable storage medium having computer-readable instructions stored therein, the instructions being executable by a processor of a computing system, wherein the instructions comprise:
 instructions to identify objects in the image of the document;   instructions to construct a division graph of the identified objects in the image of the document;   instructions to detect an optimal path through the division graph to locate regions in the image of the document; and   instructions to divide the image of the document into the regions based at least in part on the detected optimal path.   
     
     
         20 . The non-transitory computer-readable storage medium of  claim 19 , further comprising:
 instructions to construct an area diagram for the identified objects.   
     
     
         21 . The non-transitory computer-readable storage medium of  claim 19 , further comprising:
 instructions to construct an adjacency graph based on the division graph, wherein constructing the adjacency graph further comprises:
 instructions to assign graph vertices corresponding to the identified objects; 
 instructions to identify pairs of adjacent objects corresponding to pairs of objects divided by at least one edge in the division graph; and 
 instructions to join each pair of adjacent objects by an edge of the adjacency graph. 
   
     
     
         22 . The non-transitory computer-readable storage medium of  claim 20 , further comprising:
 instructions to identify graph vertices and graph edges on the area diagram; and   instructions to create a minimal graph based on the identified graph vertices and graph edges.   
     
     
         23 . The non-transitory computer-readable storage medium of  claim 19 , further comprising instructions to assign weight values to edges of the division graph, wherein the weight values are based upon analyzing mutual characteristics of at least one pair of identified objects. 
     
     
         24 . The non-transitory computer-readable storage medium of  claim 23 , further comprising instructions to sum the assigned weight values to determine a total weight value for paths in the division graph, wherein the at least one optimal path is a path with the best total weight value. 
     
     
         25 . The non-transitory computer-readable storage medium of  claim 19 , further comprising:
 instructions to construct at least one sub-graph of the division graph;   instructions to identify connected components in the sub-graph;   instructions to construct at least one path relative to the identified connected components; and   instructions to filter the at least one path.   
     
     
         26 . The non-transitory computer-readable storage medium of  claim 19 , further comprising:
 instructions to correct the at least one optimal path by adding one or more patches.   
     
     
         27 . The non-transitory computer-readable storage medium of  claim 21 , further comprising:
 instructions to remove at least one graph edge from the adjacency graph corresponding to the at least one optimal path;   instructions to identify connected components in the adjacency graph;   instructions to construct regions relative to the connected components in the adjacency graph; and   instructions to divide the image of the document in the constructed regions.