US5892843A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Title, caption and photo extraction from scanned document images
Assignee: Panasonic Holdings Corp
•
Filing: 1997-01-21
•
Granted: 1999-04-06
•
Expires: 2017-01-21
Abstract
Abstract The bitmap image data is analyzed by connected component extraction to identify components or connected components that represent either individual characters or letters, or regions of a nontext image. The connected components are classified as text or nontext based on geometric attributes such as the number of holes, arcs and line ends comprising each component. A nearest-neighbor analysis then identifies which text components represent lines or strings of text and each line or string is further analyzed to determine its vertical or horizontal orientation. Thereafter, separate vertical and horizontal font height filters are used to identify those text strings that are the most likely candidates. For the most likely title candidates a bounding box is defined which can be associated with or overlaid upon the original bitmap data to select the title region for further processing or display. Captions and photographs can also be located.
Inventors
- 👤 Jiangying Zhou
- 👤 Daniel P. Lopresti
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 04:16
CPC Classifications
G; G06; G06V; G06V30/00; G06V30/40
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
299 words
A computer-implemented method of delineating titles within image data, comprising the steps of: storing the image data in a buffer; performing connected component extraction upon the stored image data to identify a plurality of connected components and to generate a first data structure for storing a data objects corresponding to said connected components; for each data object stored in said first data structure, identifying at least a first attribute reflecting the shape of the corresponding connected component and a second attribute reflecting a geometric property of the corresponding connected component and storing said first and second attributes in association with said first data structure; analyzing at least said first attributes to identify which data objects correspond to image data representing text; performing a nearest-neighbor analysis using geometric distance among said data objects to construct at least one nearest-neighbor graph of linked data objects that corresponds to image data representing at least a portion of at least one line of text; analyzing said second attributes to determine an average geometric property of the connected components that correspond to image data representing text; for each nearest-neighbor graph corresponding to image data that represents at least one line of text, comparing the stored second attributes of the data objects associated with each graph with said average geometric property; selecting as title candidates those nearest-neighbor graphs in which the component data objects have second attributes substantially different from than said average geometric property; defining a bounding box for each of said title candidates and merging said bounding boxes of title candidates corresponding to at least one line of text to define at least one merged bounding box; and associating said merged bounding box with said stored image data, whereby said merged bounding box delineates portions of said stored image data that represent titles.
Claim 2
Dependent Claim
299 words
A computer-implemented method of delineating titles within image data, comprising the steps of: storing the image data in a buffer; performing connected component extraction upon the stored image data to identify a plurality of connected components and to generate a first data structure for storing a data objects corresponding to said connected components; for each data object stored in said first data structure, identifying at least a first attribute reflecting the shape of the corresponding connected component and a second attribute reflecting a geometric property of the corresponding connected component and storing said first and second attributes in association with said first data structure; analyzing at least said first attributes to identify which data objects correspond to image data representing text; performing a nearest-neighbor analysis using geometric distance among said data objects to construct at least one nearest-neighbor graph of linked data objects that corresponds to image data representing at least a portion of at least one line of text; analyzing said second attributes to determine an average geometric property of the connected components that correspond to image data representing text; for each nearest-neighbor graph corresponding to image data that represents at least one line of text, comparing the stored second attributes of the data objects associated with each graph with said average geometric property; selecting as title candidates those nearest-neighbor graphs in which the component data objects have second attributes substantially different from than said average geometric property; defining a bounding box for each of said title candidates and merging said bounding boxes of title candidates corresponding to at least one line of text to define at least one merged bounding box; and associating said merged bounding box with said stored image data, whereby said merged bounding box delineates portions of said stored image data that represent titles.
Claim 3
Dependent Claim
11 words
The method of claim 1 wherein said geometric property is size.
Claim 4
Dependent Claim
28 words
The method of claim 1 further comprising analyzing said nearest-neighbor graphs corresponding to image data that represents at least one line of text to determine the spatial orientation.
Claim 5
Dependent Claim
35 words
The method of claim 1 further comprising designating said nearest-neighbor graphs corresponding to image data that represents at least one line of text as being either generally horizontally oriented text or generally vertically oriented text.
Claim 6
Dependent Claim
36 words
The method of claim 4 wherein said designating is performed by comparing said nearest-neighbor graphs corresponding to image data that represents at least one line of text to predefined data representing a forty-five (45) degree incline.
Claim 7
Dependent Claim
123 words
The method of claim 4 further comprising separately determining: (a) the horizontal average font size of connected components corresponding to image data representing generally horizontally oriented text and (b) the vertical average font size of connected components corresponding to image data representing generally vertically oriented text; and using said separately determined average font sizes to select as title candidates: (a) those nearest neighbor graphs corresponding to image data representing generally horizontally oriented lines of text in which the component data objects have size attributes greater than said horizontal average font size; and (b) those nearest-neighbor graphs corresponding to image data representing generally vertically oriented lines of text in which the component data objects have size attributes greater than said vertical average font size.
Claim 8
Dependent Claim
16 words
The method of claim 1 wherein said image data is single bit data representing monochrome values.
Claim 9
Dependent Claim
15 words
The method of claim 1 wherein said image data is multi-bit data representing gray-scale values.
Claim 10
Dependent Claim
15 words
The method of claim 1 wherein said image data is multi-bit data representing color values.
Claim 11
Dependent Claim
42 words
The method of claim 1 wherein said first geometric attribute is selected from the group consisting of: number of black pixels, number of white pixels, number of holes, number of stroke ends, number of stroke upturned arcs, number of stroke downturned arcs.
Claim 12
Dependent Claim
17 words
The method of claim 1 wherein said second attribute defines a bounding box around the connected component.
Claim 13
Dependent Claim
27 words
The method of claim 1 wherein said second attribute defines a rectangular bounding box around the connected component characterized by upper, lower, left and right bounding lines.
Claim 14
Dependent Claim
24 words
The method of claim 1 further comprising analyzing said first and second attributes to identify which data objects correspond to image data representing text.
Claim 15
Dependent Claim
51 words
The method of claim 1 wherein said first attribute corresponds to the number of image pixels of a predefined color and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by comparing the first attribute to a predetermined threshold.
Claim 16
Dependent Claim
59 words
The method of claim 1 wherein said first attribute corresponds to the number of black image pixels and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if the first attribute is below a predetermined threshold value.
Claim 17
Dependent Claim
59 words
The method of claim 1 wherein said first attribute corresponds to a bounding box enclosing the connected component having a height and width, and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by comparing at least one of said height and width to a predetermined threshold.
Claim 18
Dependent Claim
70 words
The method of claim 1 wherein said first attribute corresponds to a bounding box enclosing the connected component having a height and width and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if at least one of said height and width is above a predetermined threshold value.
Claim 19
Dependent Claim
56 words
The method of claim 1 wherein said first attribute corresponds to an average stroke width and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if said first attribute is above a predetermined threshold.
Claim 20
Dependent Claim
46 words
The method of claim 18 wherein said connected component extraction is performed by segmenting said stored image data into segments containing black pixels and wherein said average stroke width is calculated as the ratio of the number of black pixels to the number of black segments.
Claim 21
Dependent Claim
67 words
The method of claim 1 wherein said first attribute corresponds to a bounding box enclosing the connected component having a height and width and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if the ratio of width to height is above a predetermined threshold.
Claim 22
Dependent Claim
68 words
The method of claim 1 wherein said first attribute corresponds to a bounding box enclosing the connected component having a height and width and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if at the ratio of height to width is above a predetermined threshold.
Claim 23
Dependent Claim
62 words
The method of claim 1 wherein said first attribute corresponds to the number of white pixels in the connected component and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if the first attribute is above a predetermined threshold value.
Claim 24
Dependent Claim
62 words
The method of claim 1 wherein said first attribute corresponds to the number of line ends in the connected component and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if the first attribute is above a predetermined threshold value.
Claim 25
Dependent Claim
96 words
The method of claim 1 wherein said first attribute corresponds to a bounding box enclosing the connected component having a size determined by the box's height and width and further corresponds to the number of black image pixels within the connected component, and wherein said step of analyzing said first attributes to identify which data objects correspond to image data representing text is performed by declaring that the image data does not represent text if the ratio of the number of black image pixels to the size of said bounding box is below a predetermined threshold.
Claim 26
Dependent Claim
32 words
The method of claim 1 further comprising extracting a title from said image data by copying a subset of said stored image data delineated by said bounding box to a storage buffer.
Claim 27
Dependent Claim
41 words
The method of claim 1 further comprising extracting a title from said image data by performing optical character recognition on a subset of said stored image data delineated by said bounding box to generate text data corresponding to the delineated title.
Claim 28
Dependent Claim
33 words
The method of claim 1 further comprising using said bounding box to generate text data corresponding to the delineated title and using said text data as an index associated with said image data.
Claim 29
Dependent Claim
34 words
The method of claim 1 further comprising using said bounding box to generate text data corresponding to the delineated title and using said text data as a computer-searchable keyword associated with said image data.
Claim 30
Dependent Claim
34 words
The method of claim 1 further comprising for each data object stored in said first data structure, identifying a plurality of second attributes, each reflecting a different geometric property of the corresponding connected component.
Claim 31
Dependent Claim
36 words
The method of claim 29 further comprising analyzing said second attributes in a predetermined sequential order to select as title candidates those nearest-neighbor graphs in which the component data objects have attributes that meet predefined characteristics.
Claim 32
Dependent Claim
33 words
The method of claim 29 further comprising analyzing said second attributes substantially concurrently to select as title candidates those nearest-neighbor graphs in which the component data objects have attributes that meet predefined characteristics.
Claim 33
Independent Claim
216 words
A method of delineating photographic regions within image data, comprising the steps of: storing the image data in a buffer; performing connected component extraction upon the stored image data to identify a plurality of connected components and to generate a first data structure for storing data objects corresponding to said connected components; for each data object stored in said first data structure, identifying at least a first attribute reflecting the height-to-width ratio of the corresponding connected component and storing said first attribute in association with said first data structure; analyzing at least said first attributes to identify which data objects correspond to image data representing possible photographic regions by defining a bounding box for each of said connected components and selecting as photographic region candidates those connected components having bounding boxes greater than a predetermined threshold size; further analyzing said first attributes of said photographic region candidates to select as photographic regions those candidates having first attributes that bear a first relationship with a predetermined threshold; merging said bounding boxes of said selected photographic regions whose respective bounding boxes overlap to define at least one merged bounding box; and associating said merged bounding box with said stored image data, whereby said merged bounding box delineates portions of said stored image data that represent said photographic regions.
Claim 34
Independent Claim
216 words
A method of delineating photographic regions within image data, comprising the steps of: storing the image data in a buffer; performing connected component extraction upon the stored image data to identify a plurality of connected components and to generate a first data structure for storing data objects corresponding to said connected components; for each data object stored in said first data structure, identifying at least a first attribute reflecting the height-to-width ratio of the corresponding connected component and storing said first attribute in association with said first data structure; analyzing at least said first attributes to identify which data objects correspond to image data representing possible photographic regions by defining a bounding box for each of said connected components and selecting as photographic region candidates those connected components having bounding boxes greater than a predetermined threshold size; further analyzing said first attributes of said photographic region candidates to select as photographic regions those candidates having first attributes that bear a first relationship with a predetermined threshold; merging said bounding boxes of said selected photographic regions whose respective bounding boxes overlap to define at least one merged bounding box; and associating said merged bounding box with said stored image data, whereby said merged bounding box delineates portions of said stored image data that represent said photographic regions.
Claim 35
Dependent Claim
17 words
The method of claim 32 wherein said first attribute umber of black pixels in said connected component.
Claim 36
Dependent Claim
29 words
The method of claim 32 wherein said first attribute represents the ratio of the number of black pixels to the size of the bounding box of said connected component.
Claim 37
Dependent Claim
19 words
The method of claim 32 wherein said first attribute represents the number of white pixels in said connected component.
Claim 38
Dependent Claim
21 words
The method of claim 32 wherein said first attribute represents the number of upward and downward ends in said connected component.
References Cited (Backward Citations)
US4503556A
Cited
US4741046A
Cited
US4750209A
Cited
US4893188A
Cited
US5001767A
Cited
US5703962A
Cited
US5351314A
Cited
US5757957A
Cited
US5555362A
Cited
US5680479A
Cited
US5848184A
Cited
US5751849A
Cited
US5748865A
Cited
US5588072A
Cited
US5699453A
Cited
US5774579A
Cited
US5848191A
Cited
US5767978A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-04-05 | 2002-10-05 | 2003-04-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-04-05 | 2006-10-05 | 2007-04-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-04-05 | 2010-10-05 | 2011-04-06 | $7700.00 | Window Closed / Lapsed |