Patent EP0621553A2 successfully refreshed from Google Patents.
EP0621553A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Methods and apparatus for inferring orientation of lines of text
Assignee: AT&T Inc
•
Filing: 1994-04-13
•
Granted: —
•
Expires: 2014-04-13
Abstract
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.
Inventors
- 👤 David Jack Ittner
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-04 23:55
CPC Classifications
H; H04; H04M; H04M3/00; H04M3/42; H04M3/50; H04M3/53; H04M3/5307; G; G06; G06V; G06V30/00; G06V30/10; G06V30/14; G06V30/146; G06V30/1463
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
55 words
A method of determining the orientation of a line of entities in an image characterized by the steps of: connecting the entities with edges to make a graph; computing a minimum spanning tree of the graph; and determining the orientation of the line from a dominant orientation of the edges of the minimum spanning tree.
Claim 2
Dependent Claim
33 words
The method set forth in claim 1 further characterized in that: the step of connecting the entities comprises the steps of reducing the entities to points; and connecting the points with the edges.
Claim 3
Dependent Claim
24 words
The method set forth in claim 1 further characterized by the step of: filtering very large and very small entities before making the graph.
Claim 4
Dependent Claim
29 words
The method set forth in claim 1 further characterized in that: the step of determining the orientation of the line determines whether the orientation is vertical, horizontal, or uncertain.
Claim 5
Dependent Claim
42 words
The method set forth in claim 1, 2, 3, or 4 further characterized in that: the step of connecting the entities includes the step of labelling the edges according to the distance in the image of the entities connected by the edges.
Claim 6
Dependent Claim
75 words
The method set forth in claim 1, 2, 3, or 4 further characterized in that: the step of determining the orientation of the line includes the steps of: making a histogram which has bins for ranges of the orientations of the edges of the minimum spanning tree and specifies for each bin at least the number of the edges having orientations for that bin's range; and determining the orientation of the line from the histogram.
Claim 7
Dependent Claim
45 words
The method set forth in claim 6 further characterized in that: the step of making the histogram includes the step of modifying the contribution of each edge to the bin for the edge's orientation according to the area of the entities connected by the edge.
Claim 8
Dependent Claim
32 words
The method set forth in claim 6 further characterized in that: the step of determining the orientation of the line includes the step of sharpening peaks and damping noise in the histogram.
Claim 9
Dependent Claim
44 words
The method set forth in claim 8 further characterized in that: the step of sharpening peaks and damping noise includes the step of defining the energy at histogram bin b i as (b as where h is the number of bins in the histogram.
Claim 10
Dependent Claim
52 words
The method set forth in claim 9 further characterized in that: the step of determining the orientation of the line further includes the step of determining that the orientation is uncertain unless there is an orientation for which the percentage of the total energy in the histogram is above a predetermined threshold.
Claim 11
Dependent Claim
22 words
The method set forth in claim 1, 2, 3, or 4 further characterized in that: the entities are characters of a script.
Claim 12
Dependent Claim
17 words
The method set forth in claim 11 further characterized in that: the characters have multiple connected components.
Claim 13
Dependent Claim
28 words
The method set forth in claim 11 further characterized in that: the steps of the method are practiced in a system which assigns each character a digital code.
Claim 14
Dependent Claim
23 words
The method set forth in claim 13 further characterized in that: the system further converts the digital codes representing the characters into speech.
Claim 15
Dependent Claim
25 words
The method set forth in claim 11 further characterized in that: the method does not require a predetermined orientation of the characters to the line.
Claim 16
Independent Claim
53 words
A method of determining the orientation of a line of symbols having multiple connected components, the method characterized by the steps of: joining the connected components with edges to make a graph; determining the orientation of the edges; and determining the orientation of the line of symbols from the orientation of the edges.
Claim 17
Dependent Claim
76 words
Image analysis apparatus having means (813) for determining the orientation of a line of entities in the image, the means for determining the orientation of the line of entities characterized by: means (817) for connecting the entities with edges to make a graph; means (819) for computing a minimum spanning tree of the graph; and means (821) for determining the orientation of the line from a dominant orientation of the edges of the minimum spanning tree.
Claim 18
Dependent Claim
36 words
The apparatus set forth in claim 17 wherein the means for determining the orientation of a line of entities further characterized by: means (815) for filtering very large and very small entities before making the graph.
Claim 19
Dependent Claim
29 words
The apparatus set forth in claim 17 further characterized in that: the means for determining the orientation of the line determines whether the orientation is vertical, horizontal, or uncertain.
Claim 20
Dependent Claim
22 words
The apparatus set forth in claim 17, 18, or 19 further characterized in that: the entities are characters (202) of a script.
Claim 21
Dependent Claim
17 words
The apparatus set forth in claim 20 further characterized in that: the characters have multiple connected components.
Claim 22
Dependent Claim
25 words
The apparatus set forth in claim 20 further characterized in that: the apparatus is part of a system which assigns each character a digital code.
Claim 23
Dependent Claim
23 words
The apparatus set forth in claim 22 further characterized in that: the system further converts the digital codes representing the characters into speech.
Claim 24
Dependent Claim
25 words
The apparatus set forth in claim 20 further characterized in that: the apparatus does not require a predetermined orientation of the characters to the line.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.