Method and system for detecting text in raster images

• US 8,588,529 B2
• Filed: 08/15/2011
• Issued: 11/19/2013
• Est. Priority Date: 08/15/2011
• Status: Active Grant

• Current Assignee: Cimpress Schweiz GmbH (Cimpress Plc)
• Original Assignee: Vistaprint Schweiz GmbH (Cimpress Plc)
• Inventors: Nykyforov, Vyacheslav
• Primary Examiner(s): Werner, Brian P
• Application Number:
  US13/210,184
• Publication Number:
  US 20130044945A1
• Time in Patent Office: 827 Days
• Field of Search: None
• US Class Current: 382/187
• CPC Class Codes: G06V 20/62 Text, e.g. of license plates, overlay texts or captions on TV images
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1823 using vector-coding

Abstract

Systems, methods, and applications for detection text in a raster image include converting a raster image into a vector representation of the image, identifying pairs of shapes of similar size and within a predefined distance of one another, forming shape graphs from the identified shape pairs, identifying chains of shapes from the formed shape graphs, determining characteristic chain lines associated with the identified chains of shapes, straightening the identified chains of shapes into a straight line based on the corresponding chain lines associated with the respective identified chains of shapes, and classifying the straightened identified chains as text or non-text using an automatic text classifier.

Claims

1. A method for detecting text in raster images, the method comprising the steps of:

converting a raster image into a vector representation of the image;

identifying pairs of shapes of similar size and within a predefined distance of one another;

forming shape graphs from the identified shape pairs;

identifying chains of shapes from the formed shape graphs;

determining characteristic chain lines associated with the identified chains of shapes;

straightening the identified chains of shapes into a straight line based on the corresponding chain lines associated with the respective identified chains of shapes; and

classifying the straightened identified chains as text or non-text using an automatic text classifier.

2. The method of claim 1, wherein the vector representation of the image is a colorized vector representation of the image.

3. The method of claim 1, wherein the step of converting the raster image into a vector representation of the image comprises:

receiving the raster image;

converting the received raster image into a color-reduced raster image;

vectorizing the color-reduced raster image to generate the colorized representation of the raster image.

4. The method of claim 3, wherein the step for converting the received raster image into a color-reduced raster image comprises down-sampling the received raster image to a reduced set of discrete colors.

5. The method of claim 3, wherein the step for converting the received raster image into a color-reduced raster image comprises setting corresponding pixel colors of pixels in the received raster image to a nearest color in a predetermined reduced set of discrete colors.

6. The method of claim 3, wherein the step for converting the received raster image into a color-reduced raster image comprises applying an Octree color quantization algorithm to the received raster image to generate a down-sampled version of the received raster image having pixels corresponding only to a reduced set of discrete colors.

7. The method of claim 3, wherein the step for converting the received raster image into a color-reduced raster image comprises applying Median Cut color quantization algorithm to the received raster image to generate a down-sampled version of the received raster image having pixels corresponding only to a reduced set of discrete colors.

8. The method of claim 3, wherein the vectorizing step comprises:

decomposing the color-reduced image into separate bi-color planes; and

vectorizing each bi-color plane.

9. The method of claim 8, wherein the step for identifying pairs of shapes of similar size and within a predefined distance of one another comprises:

identifying two shapes of the same color in the vector image, finding the centers of masses of the identified two shapes, classifying the identified two shapes as a shape pair if a straight line connecting the centers of mass does not intersect any other shape in the vector image and a ratio between a length of a first one of the two shapes to the length of a second one of the two shapes is within a predetermined range, and the length of the connecting straight line is less than or equal to the predefined distance.

10. The method of claim 9, where in the ratio is determined based on a shape length taken as the length of the shape orthogonal to the connecting straight line.

11. The method of claim 1, wherein the step of identifying chains of shapes comprises:

representing the shapes of a same color as a shape graph, each shape graph having a connecting line between the centers of mass of two shapes so long as the connecting line does not cross over any additional shapes of the same color, wherein each shape is considered a vertex in the shape graph and each connecting line between two centers of mass is considered an edge in the shape graph;

generating graph configurations by selectively including or not including various edges in the shape graph;

for each graph configuration, eliminating the graph configuration if any vertex in the graph configuration is connecting to more than one other vertex, and calculating a graph configuration energy based on a length of the a chain defined by the graph, a variance in shape height, and curvature of the chain, and selecting one or more of the graph configurations having a minimized chain energy as a respective potential text candidate.

12. The method of claim 1, wherein the characteristic lines associated with an identified chain correspond to curvature of the identified chain and comprise at least a center line and a first line equidistant from the center line on one side of the center line and a second line equidistant from the center line on the opposite side of the center line;

and

wherein the step of straightening the identified chains comprises;

for each shape in an identified chain, finding a bounding box around the shape such that the boundaries of the box in a first dimension touch the first line and the second line and the boundaries of the box in a second dimension touch at least one point on the shape but does not cross over into the shape, determining an angle between a normal line and a horizontal normal line, the normal line taken between the center of mass of the shape and the center line, and the horizontal normal line being a normal line for a horizontal line, and rotating the shape by the determined angle; and

normalizing the identified chain such that the distance between the first line and second line is equal to a predetermined value.

13. The method of claim 1, wherein the classifying step comprises:

Passing each straightened identified chain to a text classifier that is trained with a training data set to distinguish text from non-text chains.

14. The method of claim 13, wherein the text classifier is implemented using an artificial neural network.

15. A text classification system comprising:

one or more processors configured to receive a raster image;

a raster-to-vector converter which converts the raster image into a vector image comprising a vector representation of the received raster image;

a shape pair detection engine which identifies pairs of shapes of similar size and within a predefined distance of one another;

a chain detection system which forms shape graphs from the identified shape pairs and identifies chains of shapes from the formed shape graphs;

a chain line straightening system which determines characteristic chain lines associated with the identified chains of shapes and which straightens the identified chains into a straight line based on the corresponding chain lines associated with the respective identified chains of shapes; and

a text classifier which classifies the straightened identified chains as text or non-text.

16. The text classification system of claim 15, wherein the raster-to-vector converter is configured to receive the raster image, convert the received raster image into a color-reduced raster image, and convert the color-reduced raster image to generate a colorized vector image.

17. The text classification system of claim 16, wherein the raster-to-vector converter is configured to down-sample the received raster image to a reduced set of discrete colors to generate the color-reduced raster image.

18. The text classification system of claim 16, wherein the raster-to-vector converter is configured to set corresponding pixel colors of pixels in the received raster image to a nearest color in a predetermined reduced set of discrete colors to generate the color-reduced raster image.

19. The text classification system of claim 16, wherein the raster-to-vector converter is configured to apply an Octree color quantization algorithm to the received raster image to generate a down-sampled version of the received raster image having pixels corresponding only to a reduced set of discrete colors to thereby generate the color-reduced raster image.

20. The text classification system of claim 16, wherein the raster-to-vector converter is configured to apply a Median Cut color quantization algorithm to the received raster image to generate a down-sampled version of the received raster image having pixels corresponding only to a reduced set of discrete colors to thereby generate the color-reduced raster image.

21. The text classification system of claim 16, wherein the raster-to-vector converter is configured to decompose the color-reduced image into separate bi-color planes and to vectorize each bi-color plane to generate the vector image.

22. The text classification system of claim 21, wherein the shape pair detection engine is configured to identify two shapes of the same color in the vector image, find the centers of masses of the identified two shapes, classifying the identified two shapes as a shape pair if a straight line connecting the centers of mass does not intersect any other shape in the vector image and a ratio between a length of a first one of the two shapes to the length of a second one of the two shapes is within a predetermined range, and the length of the connecting straight line is less than or equal to the predefined distance.

23. The text classification system of claim 22, where in the ratio is determined based on a shape length taken as the length of the shape orthogonal to the connecting straight line.

24. The text classification system of claim 15, wherein the chain detection system comprises a shape graph generator,

the shape graph generator configured to generate one or more respective shape graphs each associated with a different one of the reduced set of discrete colors, each shape graph representing the shapes of a color corresponding to the associated shape graph, each shape graph having a connecting line between the centers of mass of two shapes so long as the connecting line does not cross over any additional shapes of the same color, wherein shapes are vertexes in the shape graph and each connecting line between two centers of mass is considered an edge in the shape graph,

the shape graph generator configured to generate graph configurations by selectively including or not including various edges in the shape graph,

the shape graph generator further configured to, for each graph configuration, eliminate the graph configuration if any vertex in the graph configuration is connecting to more than one other vertex, calculate a graph configuration energy based on a length of the a chain defined by the graph, a variance in shape height, and curvature of the chain, and select one or more of the graph configurations having a minimized chain energy as a respective potential text candidate.

25. The text classification system of claim 15, wherein:

the chain line straightening system is configured to determine characteristic lines associated with an identified chain, the characteristic lines corresponding to curvature of the identified chain and comprising at least a center line and a first line equidistant from the center line on one side of the center line and a second line equidistant from the center line on the opposite side of the center line;

the chain line straightening system;

the chain line straightening system further configured to adjust the rotation of shapes in the chain based on the determined characteristic lines and to normalize the position of the shapes to lie along a straight line.

26. The text classification system of claim 15, wherein the text classifier comprises an artificial neural network which is trained with a training data set to distinguish text from non-text chains.