Determining a rectangular box encompassing a digital picture within a digital image

• US 6,049,636 A
• Filed: 06/27/1997
• Issued: 04/11/2000
• Est. Priority Date: 06/27/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Xiaoli
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US08/885,298
• Time in Patent Office: 1,019 Days
• Field of Search: 382/289, 382/282, 382/283, 382/291, 382/177, 382/176, 382/286, 382/170, 382/293, 345/424, 345/438, 345/440, 345/441, 345/443
• US Class Current: 382/289
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: H04N 1/3878 Skew detection or correction

Abstract

An invention for determining a rectangular bounding box encompassing a photograph or object(s) represented within a digital image is disclosed. The rectangular bounding box is determined irrespective of the device used to acquire the digital image. First a set of contrast points is derived; these contrast points representing changes in the characteristics of a pixel from that of a traversed neighbor. After ordering the contrast points according to their radial angle around a central reference point, a list of lines is generated by selecting two points separated by q positions in the ordered list of contrast points. If the four lines generated the most often roughly form a rectangle, then they correspond to the sides of the rectangular bounding box. Else, the line with the highest count is used as a base side of the rectangular bounding box. The slopes of the other sides are readily calculated as they are either perpendicular and parallel to base side, and their positions are then determined with reference to the other lines in the list. Once the rectangular bounding box has been determined, the digital photograph is extracted, or a high-resolution scan is performed and the digital photograph is readily extracted from this new high-resolution image based on the corresponding position and size of the rectangular bounding box.

Claims

1. In a computer system, a method for automatically determining a rectangular bounding box of an object represented in a digital image without user interaction, the rectangular bounding box having a base side and three other sides, the digital image having a contrast point, the method comprising the steps of:

processing the digital image to determine a set of the contrast points for locating pixels corresponding to a perimeter of the object;

deriving a set of lines from the set of the contrast points for locating the base side and the three other sides of the rectangular bounding box;

determining a position and a slope of the base side corresponding to a first line from the set of lines, a largest number of the contrast points from the set of the contrast points being located on the first line; and

determining the three other sides of the rectangular bounding box based on the position and the slope of the first line.

2. The method of claim 1, wherein the three other sides of the rectangular bounding box correspond with a second, third and fourth lines from the set of lines, wherein the first, second, third and fourth lines having as many contrast points located on them as any other line in the set of lines.

3. The method of claim 1, wherein the object comprises a photograph.

4. The method of claim 1, wherein the digital image is acquired from one of a plurality of possible devices, and the steps of claim 1 are device independent.

5. The method of claim 1, further comprising the step of:

adjusting the sides of the rectangular bounding box so that a minimum percentage of the points in the set of contrast points are contained within the rectangular bounding box.

6. The method of claim 5, wherein the minimum percentage is eighty percent.

7. The method of claim 1 further comprising the step of scanning the object to create the digital image, wherein the digital image contains noise.

8. The method of claim 7, wherein the object is rectangular in shape, and the orientation of the object is skewed in comparison to one or more sides of a scanning surface, whereby an area corresponding to the rectangular bounding box is extracted from the digital image to produce a second, non-skewed digital image.

9. The method of claim 1, wherein the digital image comprises a matrix, and the step of processing the digital image to determine the set of the contrast points comprises sequencing through the digital image starting at (1) the first pixel in the matrix of pixels for (i) each column and (ii) each row, and (2) the last pixel in the matrix of pixels for (i) each column and (ii) each row, and traversing the respective column or row until locating the contrast point or an end of the matrix.

10. The method of claim 1, wherein the step of deriving the set of lines, comprises the steps of:

removing duplicate contrast points from the list of the contrast points;

calculating a central reference point based on the set of the contrast points;

determining a radial angle for each of the contrast points based on its location with respect to a reference coordinate system whose origin is the central reference point;

ordering the list of contrast points by the radial angle of each of the contrast points;

deriving a new line for an every two points separated by a separation number of elements; and

adding the new line to the set of lines.

11. The method of claim 10, wherein the separation number is 10.

14. The method of claim 13 further comprising a scanner, and the method of claim 11 further comprising the step of scanning the object to create the digital image, wherein the digital image contains noise.

15. The method of claim 14, wherein the three other sides of the rectangular bounding box correspond with a second, third and fourth lines from the set of lines, wherein the first, second, third and fourth lines having as many contrast points located on them as any other line in the set of lines.

16. The method of claim 15, wherein the object comprises a rectangular photograph, and the orientation of the rectangular photograph is skewed in comparison to one or more sides of a scanning surface, whereby an area corresponding to the rectangular bounding box is extracted from the digital image to produce a second, non-skewed digital image.

12. In a computer system, a method for automatically determining a rectangular bounding box of an object represented in a digital image without user interaction, the rectangular bounding box having a base side and three other sides, the digital image having a contrast point, the method comprising the steps of:

(a) processing the digital image to determine a set of the contrast points for locating pixels corresponding to a perimeter of the object;

(b) deriving a set of lines from the set of the contrast points for locating the base side and the three other sides of the rectangular bounding box, including the steps of;

(i) removing duplicate contrast points from the list of the contrast points,

(ii) calculating a central reference point based on the set of the contrast points,

(iii) determining a radial angle for each of the contrast points based on its location with respect to a reference coordinate system whose origin is the central reference point,

(iv) ordering the list of contrast points by the radial angle of each of the contrast points,

(v) deriving a new line for an every two points separated by a separation number of elements, and

(vi) adding the new line to the set of lines;

(c) determining a position and a slope of the base side corresponding to a first line from the set of lines, a largest number of the contrast points from the set of the contrast points being located on the first line;

(d) determining the three other sides of the rectangular bounding box based on the position and the slope of the first line; and

(e) adjusting the sides of the rectangular bounding box so that a minimum percentage of the points in the set of contrast points are contained within the rectangular bounding box.

13. The method of claim 12, wherein the digital image comprises a matrix, and the step of processing the digital image to determine the set of the contrast points comprises sequencing through the digital image starting at (1) the first pixel in the matrix of pixels for (i) each column and (ii) each row, and (2) the last pixel in the matrix of pixels for (i) each column and (ii) each row, and traversing the respective column or row until locating the contrast point or an end of the matrix.

17. A computer-readable medium having computer-executable instructions for performing steps, comprising:

processing a digital image to determine a set of contrast points for locating pixels corresponding to a perimeter of an object represented in the digital image;

deriving a set of lines from the set of contrast points for locating a base side and three other sides of a rectangular bounding box;

determining a position and a slope of the base side corresponding to a first line from the set of lines, a largest number of the contrast points from the set of contrast points being located on the first line; and

determining the three other sides of the rectangular bounding box based on the position and the slope of the first line.

18. The computer-readable medium of claim 17, wherein the three other sides of the rectangular bounding box correspond with a second, third and fourth lines from the set of lines, wherein the first, second, third and fourth lines having as many contrast points located on them as any other line in the set of lines.

19. The computer-readable medium of claim 17 having further the computer-executable step of controlling a scanner to create the digital image.

20. The computer-readable medium of claim 17 having further the computer-executable step of extracting an area corresponding to the rectangular bounding box from the digital image to produce a second digital image.

21. In a computer system, a method for automatically determining a rectangular bounding box of an object represented in a digital image without user interaction, the rectangular bounding box having a base side and three other sides, the digital image having a contrast point, the method comprising the steps of:

processing the digital image to determine a set of the contrast points for locating pixels corresponding to a perimeter of the object;

deriving a set of lines from the set of the contrast points for locating the base side and the three other sides of the rectangular bounding box, whereby each line is associated with a weight; and

determining the positions and slopes of the base side and the three other sides of the rectangular bounding box based on four lines from the set of lines which have the greatest weights associated with them.

22. The method according to claim 21, wherein the step of deriving a set of lines from the set of the contrast points comprises the steps of:

removing duplicate contrast points from the list of the contrast points;

calculating a central reference point based on the set of the contrast points;

determining a radial angle for each of the contrast points based on its location with respect to a reference coordinate system whose origin is the central reference point;

ordering the list of contrast points by the radial angle of each of the contrast points;

deriving a new line for every two points separated by a separation number of elements;

adding the new line to the set of lines; and

associating with each line in the set of lines a weight corresponding to the number of lines in the set of lines having substantially the same slope.