Methods and apparatus for inferring orientation of lines of text
First Claim
1. A method practiced in image analysis apparatus including at least processing means and memory means of automatically determining the orientation of a line of entities in an image representation representing an image, the image representation being stored in the memory means and the method comprising the steps performed in the processing means of:
- making a graph representation in the memory means which represents a graph in which the entities are connected with edges, said graph representation further specifying an area of each of the entities;
modifying the graph representation to represent a minimum spanning tree of the graph the; and
determining, based on the area of the entities and each of a plurality of edges in the minimum spanning tree, a dominant orientation of the edges of the minimum spanning tree and determining the orientation of the line from the dominant orientation.
5 Assignments
0 Petitions
Accused Products
Abstract
The techniques for determining the orientation of lines in images disclosed herein take as their starting point an apparently universal typesetting convention: that symbols are generally closer to other symbols in the line to which they belong than they are to symbols in other lines. The techniques make a graph by connecting symbols in an image of a block of text with edges (lines) and then determine the predominant orientation of the shortest edges. Because the symbols in a line are closer to each other than to symbols in other lines, the predominant orientation of the shortest edges will be the same as the orientation of the lines. An advantageous mode of obtaining the shortest edges is to construct a Euclidean minimum spanning tree from the graph. A Euclidean minimum spanning tree of a graph contains all the nodes (symbols) of the original graph but connects the nodes with the shortest possible set of edges. The edges which predominate in the Euclidean minimum spanning tree are the shortest edges. Which edges predominate is determined by means of a histogram.
87 Citations
26 Claims
-
1. A method practiced in image analysis apparatus including at least processing means and memory means of automatically determining the orientation of a line of entities in an image representation representing an image, the image representation being stored in the memory means and the method comprising the steps performed in the processing means of:
-
making a graph representation in the memory means which represents a graph in which the entities are connected with edges, said graph representation further specifying an area of each of the entities;
modifying the graph representation to represent a minimum spanning tree of the graph the; anddetermining, based on the area of the entities and each of a plurality of edges in the minimum spanning tree, a dominant orientation of the edges of the minimum spanning tree and determining the orientation of the line from the dominant orientation. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method practiced in image analysis apparatus including at least processing means and memory means of automatically determining the orientation of a line of entities in an image representation representing an image, the image representation being stored in the memory means and the method comprising the steps performed in the processing means of:
-
making a graph representation in the memory means which represents a minimum spanning tree in which the entities are connected with edges such that a very high percentage of the entities are connected to fewer than four of the next nearest entities in the image, said graph representation further specifying an area of each of the entities; and determining, based on the area of the entities and each of a plurality of edges in the minimum spanning tree, a dominant orientation of the edges of the minimum spanning tree and determining the orientation of the line from the dominant orientation. - View Dependent Claims (25, 26)
-
-
17. Image analysis apparatus which is implemented in a computer system which includes processor means and memory means and which includes means for determining the orientation of a line of entities in an image representation representing the image, the image representation being stored in the memory means and the means for determining the orientation of the line of entities comprising:
-
means implemented using the processor means for making a graph representation in the memory means representing a graph in which the entities are connected with edges, said graph representation further specifying an area of each of the entities; means implemented using the processor means for modifying the graph representation to represent a minimum spanning tree of the graph; and means implemented using the processor means for determining, based on the area of the entities and each of a plurality of edges in the minimum spanning tree, a dominant orientation of the edges of the minimum spanning tree and determining the orientation of the line from the dominant orientation. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24)
-
Specification