Method and system for automatically inscribing noisy objects in scanned image data within a minimum area rectangle

• US 7,623,734 B2
• Filed: 09/30/2004
• Issued: 11/24/2009
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Herley, Cormac E.
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): Thirugnanam; Gandhi
• Application Number:
  US10/956,225
• Publication Number:
  US 20060072818A1
• Time in Patent Office: 1,881 Days
• Field of Search: 382/100, 382/135, 382173-174, 382/254, 382/266, 382/269, 382/282, 382/289, 382/286, 382/291, 345418-421, 345/428, 345/581, 345/619, 345/621, 345/622, 345/625, 345/628, 345/666, 345173-174, 345/269, 345/629, 345/441
• US Class Current: 382/286
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

A minimum area rectangle inscription method and system for automatically generating a minimum area rectangle that inscribes and bounds an approximately rectangular object (or “noisy” object) contained within scanned image data. The minimum area rectangle inscription method chooses an interior point located inside the object boundary and determine perimeter points located on the boundary. A convex hull is constructed from at least some of the perimeter points such that each side of the convex hull is convex. Inscribing rectangles, equal in number to the sides of the convex hull, are constructed such that each inscribing rectangle shares a side with the convex hull and circumscribes approximately the entire convex hull. The area of each of the inscribing rectangles is calculated, and the inscribing rectangle having the least amount of area is designated as the minimum area rectangle.

Claims

1. A method for automatically finding a minimum area rectangle to inscribe an object, comprising:

using a processor to compute the following;

inputting scanned image data containing the object that is a noisy object having a deformed rectangular shape that is not perfectly rectangular and is deformed such that it is no longer perfectly rectangular and lacks well-defined edges and corners;

determining a number, N, of points on a perimeter or boundary line of the object that are desired;

finding the N perimeter points by generating an orthogonal coordinate system centered at an interior point that is inside the object and sending out a ray outward from the interior point along a direction until reaching the perimeter or boundary line of the object and designating an intersection of the perimeter and ray as one of the N perimeter points and repeating this process N times in N different directions;

constructing a convex hull from at least some of the N perimeter points located on a boundary of the object, wherein each side of the convex hull is a straight line segment between two of the perimeter points;

constructing an inscribing rectangle at each of side of the convex hull; and

calculating an area of each inscribing rectangle to find an inscribing rectangle having a minimum area to obtain the minimum area rectangle.

2. The method of claim 1, further comprising constructing each inscribing rectangle such that each inscribing rectangle:

(a) shares at least one side with the convex hull; and

(b) inscribes the convex hull.

3. The method of claim 2, wherein the object is located within scanned image data.

4. The method of claim 1, further comprising selecting a large enough value of N so that there is at least one perimeter point located on each side of the object.

5. The method of claim 1, further comprising finding the center of mass of the object and defining the center of mass as the interior point.

6. The method of claim 1, further comprising randomly selecting the interior point.

7. The method of claim 1, further comprising having N evenly-spaced rays.

8. The method of claim 1, further comprising having N randomly-spaced rays.

9. The method of claim 1, further comprising having an angle between the rays given by the formula:

θ

(i)=2π

i/N, for i=0, 1, 2, . . . N−

1

wherein θ

(i) is the angle and N is the number of perimeter points.

10. The method of claim 1, further comprising selecting a plurality of interior points that are located inside the boundary of the object.

11. The method of claim 10, wherein at least some of the plurality of interior points are selected randomly.

12. The method of claim 10, further comprising determining the perimeter points for each of the plurality of interior points.

13. The method of claim 12, further comprising constructing a convex hull for each of the plurality of interior points using the perimeter points corresponding to each of the plurality of interior points by connecting some or all of the perimeter points using with straight lines.

14. The method of claim 13, further comprising:

obtaining a minimum area rectangle for each of the convex hulls; and

comparing the minimum area rectangles and selecting one of the minimum area rectangles having a minimum area.

15. The method of claim 12, further comprising constructing a single convex hull using the perimeter points obtained from the plurality of interior points.

16. The method of claim 15, further comprising obtaining the minimum area rectangle using the convex hull.

17. The method of claim 1, wherein constructing the convex hull further comprises drawing line segments between at least some of the perimeter points to form a convex hull having M sides, wherein M is equal to the number of perimeter points used in constructing the convex hull.

18. The method of claim 17, further comprising determining M by ignoring any of the perimeter points that would cause the convex hull to become concave.

19. The method of claim 1, wherein constructing an inscribing rectangle further comprises:

selecting a side of the convex hull, wherein the selected side is a line segment between two of the perimeter points; and

defining a coordinate system having a first axis that is parallel to the selected side and a second axis that is perpendicular to the first axis.

20. The method of claim 19, further comprising:

finding a first vertex of the convex hull having a maximum value on the first axis;

finding a second vertex of the convex hull having a minimum value on the first axis;

finding a third vertex of the convex hull having a maximum value on the second axis; and

finding a fourth vertex of the convex hull having a minimum value on the second axis.

21. The method of claim 20, wherein calculating the area of the inscribing rectangle further comprises:

subtracting the second vertex from the first vertex to obtain a first result;

subtracting the fourth vertex from the third vertex to obtain a second result; and

multiplying the first result times the second result.

22. The method of claim 1, further comprising checking that the minimum area rectangle contains a majority of the object.

23. A computer-readable storage medium having stored thereon computer-executable instructions that are executable by a general-purpose computing device for performing the steps of:

inputting scanned image data containing the object that is a noisy object having a deformed rectangular shape that is not perfectly rectangular and is deformed such that it is no longer perfectly rectangular and lacks well-defined edges and corners;

determining a number, N, of points on a perimeter or boundary line of the object as that are desired;

finding the N perimeter points by generating an orthogonal coordinate system centered at an interior point that is inside the object and sending out a ray outward from the interior point along a direction until reaching the perimeter or boundary line of the object and designating an intersection of the perimeter and ray as one of the N perimeter points and repeating this process N times in N different directions;

constructing a convex hull from at least some of the N perimeter points located on a boundary of the object, wherein each side of the convex hull is a straight line segment between two of the perimeter points;

constructing an inscribing rectangle at each of side of the convex hull; and

calculating an area of each inscribing rectangle to find an inscribing rectangle having a minimum area to obtain the minimum area rectangle.