Method and system for automatically inscribing noisy objects in scanned image data within a minimum area rectangle
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
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.
-
Specification