Methods and apparatus for locating and identifying text labels in digital images

• US 6,826,305 B2
• Filed: 03/27/2001
• Issued: 11/30/2004
• Est. Priority Date: 03/27/2001
• Status: Expired due to Term

• Current Assignee: NCR Voyix Corporation
• Original Assignee: NCR Corporation
• Inventors: Zhu, Jie
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Alavi, Amir
• Application Number:
  US09/818,379
• Publication Number:
  US 20020141641A1
• Time in Patent Office: 1,344 Days
• Field of Search: 382/101, 382/102, 382/159, 382/168, 382/170, 382/171, 382/172, 382/173-174, 382/189, 382/176, 382/218, 382/305, 382/321, 707/500, 707/530, 707/517, 707/518, 707/519, 707/520, 707/521
• US Class Current: 382/172
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables

Abstract

Techniques for identifying labels appearing in images are described. A digital image is analyzed to identify individual components. Each of the individual components is analyzed to determine whether or not it is a text component by comparing it against criteria such as size, aspect ratio, and proximity to other components. Each component identified as a text component is compared against criteria such as size in order to identify it as a label or not. Location coordinates of each label are stored in association with the label and optical character recognition is performed on the labels. Once the labels are identified, each image can be used as an online catalog page. For example, an image may be used to construct a web page containing pictures of available products with each label serving as a hypertext link to retrieve further information about the product or to enter an order for the product. Automatically identifying labels simplifies the conversion of preexisting paper catalog pages to online catalog pages or similar digitized images.

Claims

1. A method of text label identification comprising the steps of:

identifying individual components of a digital image;

examining each component to determine whether or not the component is a text component and identifying each text component, including the substeps of

excluding very large components from consideration;

examining selected characteristics of each component remaining under consideration to determine whether they fall within limits established for the characteristics and excluding components for which the selected characteristics fall outside of the limits;

excluding components which are too small and too far away from other components to be text; and

designating the remaining components as text;

wherein establishing the limits for each characteristic includes the substeps of

creating a histogram for the characteristic;

identifying a dominant peak of the histogram;

locating a lower limit at a valley below the dominant peak; and

locating an upper limit at a valley above the dominant peak;

performing connected component analysis on each text component to produce grouped text components; and

comparing each grouped text component against predetermined criteria to determine whether the grouped text component is a label and identifying each grouped text component meeting the criteria as a label.

2. The method of claim 1 further comprising a step of noting location coordinates of each label and storing the location coordinates in association with the label.

3. The method of claim 2 further comprising performing optical character recognition on each label.

4. The method of claim 3 wherein the predetermined criteria against which each grouped text component is compared includes size criteria to determine if the grouped text component is the correct size to be a label.

5. The method of claim 4 wherein the step of identifying the individual components of the image comprises:

performing connected component analysis on each component;

comparing each component against a size criterion to identify whether or not a component is a small component;

performing a merge on all small components to merge each group of small components meeting specified criteria into a merged components; and

identifying each individual and merged component as an individual component.

6. The method of claim 1 wherein the step of creating the histogram is followed by a step of smoothing the histogram using a Gaussian kernel.

7. The method of claim 6 wherein the step of smoothing the histogram is followed by a step of choosing a realistic range in which to search for the dominant peak.

8. The method of claim 7 wherein the step of examining each grouped text component comprises comparing the component against predetermined size criteria and designating as a label each component meeting the size criteria.

9. The method of claim 1 wherein the limits are predetermined constants.

10. A label identification system comprising:

digital storage for storing digital images;

a processor for processing each of the images to identify labels appearing on each image, the processor being operative to identify each individual component of the image, to identify each of the individual components as a text component or a non text component by

excluding very large components from consideration;

examining selected characteristics of each component remaining under consideration to determine whether they fall within limits established for the characteristics and excluding components for which the selected characteristics fall outside of the limits;

excluding components which are too small and too far away from other components to be text; and

designating the remaining components as text;

wherein the processor establishes the limits for each characteristic by

creating a histogram for the characteristic;

identifying a dominant peak of the histogram;

locating a lower limit at a valley below the dominant peak; and

locating an upper limit at a valley above the dominant peak; and

wherein the processor further identifies each text component as a label or a non-label.

11. The label identification system of claim 10 further comprising a scanner to capture images for storage as digital images.

12. The label identification system of claim 11 wherein the processor is further operative to store location coordinates for each label in association with the label.

13. The label identification system of claim 12 wherein the processor is further operative to perform optical character recognition on each label.

14. A method of text label identification comprising the steps of:

identifying individual components of a digital image, including the substeps of

performing connected component analysis on each component;

comparing each component against a size criterion to identity whether or not a component is a small component;

performing a merge on all small components to merge each group of small components meeting specified criteria into a merged components; and

identifying each individual and merged component as an individual component;

examining each component to determine whether or not the component is a text component and identifying each text component, including the substeps of

excluding very large components from consideration;

examining selected characteristics of each component remaining under consideration to determine whether they fall within limits established for the characteristics and excluding components for which the selected characteristics fall outside of the limits;

excluding components which are too small and too far away from other components to be text; and

designating the remaining components as text;

wherein establishing the limits for each characteristic includes the substeps of

creating a histogram for the characteristic;

identifying a dominant peak of the histogram;

locating a lower limit at a valley below the dominant peak; and

locating an upper limit at a valley above the dominant peak;

performing connected component analysis on each text component to produce grouped text components;

comparing each grouped text component against predetermined criteria to determine whether the grouped text component is a label and identifying each grouped text component meeting the criteria as a label;

wherein the predetermined criteria against which each grouped text component is compared includes size criteria to determine if the grouped text component is the correct size to be a label;

noting location coordinates of each label and storing the location coordinates in association with the label; and

performing optical character recognition on each label.