Skew detection and correction of a document image representation

• US 5,452,374 A
• Filed: 04/06/1992
• Issued: 09/19/1995
• Est. Priority Date: 04/06/1992
• Status: Expired due to Term

• Current Assignee: Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Cullen, John F., Ejiri, Koichi
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US07/863,948
• Time in Patent Office: 1,261 Days
• Field of Search: 382/46, 382/61, 382/44, 395/137, 395/141, 340/727
• US Class Current: 382/293
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1478 of characters or characters lines
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

In a character recognition system, a method and apparatus for correcting the skew of a document image. Skew correction is typically performed during segmentation of the document image into text and non-text parts. Skew correction generally involves skew angle determination and correction of the document image based on the skew angle. A skew angle is determined through the steps of: providing a set of associated rectangles representing the document image, identifying a column edge associated with the set of associated rectangles, comparing rectangles from the set of associated rectangles to identify those that are in the same column and suitably far apart, calculating a tangential angle between the rectangles identified and identifying the most common tangential angle as the skew angle. Once the skew angle is determined, correction of the document image is made by constructing real skewed rectangles from corresponding extracted rectangles and rotating each of the real skewed rectangles around an origin coordinate for a distance based on the skew angle.

Claims

1. A document segmentation system for determining text and non-text portions of a document image, said document segmentation system having a skew corrector, said skew corrector comprised of:

a memory storing said document image; and

a processor, being coupled to said memory, said processor including,

a rectangle extractor coupled to said memory and providing output to said memory, said rectangle extractor providing as output a plurality of rectangles representing said document image, each of said plurality of rectangles representing a portion of said document image,

a skew angle detector coupled to said memory, said skew angle detector detecting a skew angle using a column edge C_e and at least a first rectangle and a second rectangle of said plurality of rectangles, said skew angle detector detecting said column edge C_e from at least said first rectangle and said second rectangle, said first rectangle and said second rectangle being in a common column corresponding to said column edge C_e, said skew angle being an angle between said first rectangle and said second rectangle, and

a rectangle corrector coupled to said skew angle detector and said memory, said rectangle corrector correcting the skew of all of said plurality of rectangles.

2. The skew corrector of claim 1 wherein said skew angle detector is further comprised of:

a rectangle buffer receiving and storing a predetermined number of rectangles from said memory;

a column edge detector coupled to said rectangle buffer, said column edge detector determining a column edge associated with rectangles in said rectangle buffer;

a rectangle identifier coupled to said column edge detector and said rectangle buffer, said rectangle identifier determining that said first rectangle and said second rectangle are in said common column and are a predetermined distance apart;

a tangential angle processor coupled to said rectangle identifier, said tangential angle processor generating a plurality of tangential angles, a tangential angle being generated using said first rectangle and said second rectangle; and

a peak angle detector coupled to said tangential angle processor, said peak angle detector identifying a tangential angle that is most common and outputting said tangential angle as said skew angle.

3. The skew corrector as recited in claim 2 wherein said rectangle corrector is further comprised of:

a real skewed rectangle constructor coupled to said memory and said peak angle detector, said real skewed rectangle constructor constructing a real skewed rectangle from a corresponding rectangle in said memory; and

a transformer coupled to said real skewed rectangle constructor, said transformer rotating said real skewed rectangle an angle corresponding to said skew angle and outputting a skew corrected rectangle.

4. An apparatus for identifying a skew angle of a document, said document represented as one or more objects, said apparatus comprising:

a object buffer for storing a subset of said one or more objects;

a processor, being coupled to said object buffer, including, column edge identifier coupled to said object buffer, said column edge identifier for identifying a column edge for said objects in said object buffer,

object identifier coupled to said column edge identifier and said object buffer, said object identifier for identifying, and providing as output, objects in said object buffer that are in a column defined by said column edge and that are a predetermined distance apart,

tangential angle generator coupled to said object identifier, said tangential angle generator for calculating and providing as output a plurality of tangential angles, a tangential angle generated using a first object and a second object, and

tangential angle counter coupled to said tangential angle generator, said tangential angle counter for counting tangential angles and identifying a most common tangential angle as said skew angle.

5. An apparatus for correcting the skew of a document image, said apparatus comprising:

a) a memory storing said document image, said document image defining a column, said document image including a first object and a second object, each of said objects representing a different portion of said column, and

b) a processor being coupled to said memory, said processor accessing said document image, said processor including

a column detector detecting that said first object and said second object are in said column,

a column edge generator being coupled to said column detector, said column edge generator generating a column edge corresponding to said column,

a skew angle generator being coupled to said column edge generator, said skew angle generator generating a skew angle, said skew angle being an angle between said first object and said second object, and

a skew corrector coupled to said skew angle generator, said skew corrector rotating said first object and said second object by said skew angle.

6. A document segmentation system having skew correction of document images, said document segmentation system comprising:

a memory storing a skewed document image, said skewed document image including a plurality of polygons, each polygon representing a portion of said skewed document image; and

a processor, being coupled to said memory, accessing said skewed document image, said processor determining pairs of polygons of said plurality of polygons, wherein each pair of said pairs of polygons includes only polygons in a common column, said processor determining a plurality of angles between said pairs of polygons, said processor determining said skew angle from said image and said skew angle.