System and method for automatically detecting and extracting objects in digital image data

• US 7,162,084 B2
• Filed: 01/29/2003
• Issued: 01/09/2007
• Est. Priority Date: 01/29/2003
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Herley, Cormac
• Primary Examiner(s): Tran; Phuoc
• Application Number:
  US10/354,500
• Publication Number:
  US 20040146198A1
• Time in Patent Office: 1,441 Days
• Field of Search: 382/173, 382/174, 382/190, 382/203, 382/286, 382/289, 382/291
• US Class Current: 382/173
• 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/00681 Detecting the presence, position or size of a sheet or correcting its position before scanning H04N1/047 takes precedence; mode signalling H04N1/333; skew detection or correction in image signals H04N1/3878
• CPC Class Codes: H04N 1/00702 Position
• CPC Class Codes: H04N 1/00708 Size or dimensions
• CPC Class Codes: H04N 1/00721 Orientation
• CPC Class Codes: H04N 1/00737 using the scanning elements as detectors
• CPC Class Codes: H04N 1/00748 Detecting edges, e.g. of a stationary sheet
• CPC Class Codes: H04N 1/2038 lying in the same plane

Abstract

An object detection and extraction system and method for processing digital image data. The system and method segregates objects contained within a single image and allows those objects to be considered as an individual object. In general, the object detection and extraction method takes an image containing one or more objects of know shape (such as rectangular objects) and finds the number of objects along with their size, orientation and position. In particular, the object detection and extraction method includes classifying each pixel in an image containing one or more objects to obtain pixel classification data, defining an image function to process the pixel classification data, and dividing the image into sub-images based on disparities or gaps in the image function. Each of the sub-images is processed to determine a size and an orientation for the each of the objects. The object detection and extraction system uses the above method.

Claims

1. A method for detecting and extracting objects in an image, comprising:

classifying each pixel within the image to obtain a pixel classification data;

defining an image function to process the pixel classification data;

dividing the image into sub-images based on disparities in the image function; and

processing the sub-images to determine a size, an orientation and a position for each of the objects.

2. The method as set forth in claim 1, further comprising classifying each pixel as one of:

(a) a data pixel;

(b) a background pixel.

3. The method as set forth in claim 1, wherein the image function is calculated in different directions.

4. The method as set forth in claim 1, wherein the image is a scanned image and the objects are rectangular objects.

5. The method as set forth in claim 1, further comprising repeating the classification of pixels, calculation the image function, and dividing of the image until one or more of the following occurs:

(a) the image contains a single object;

(b) the image can no longer be divided.

6. The method as set forth in claim 5, further comprising determining that the image can no longer be divided by finding no disparities the image function.

7. The method as set forth in claim 2, further comprising:

defining the image function as the sum of data pixels in a certain direction;

calculating the image function in a first direction to generate a first data set; and

calculating the image function in a second direction to generate a second data set.

8. The method as set forth in claim 7, further comprising defining the first direction and the second direction as orthogonal.

9. The method as set forth in claim 7, further comprising searching for disparities in the image function in the first direction and the image function in the second direction.

10. The method as set forth in claim 9, further comprising defining a data disparity line as the region where the number of data pixels in the image function are less as compared to surrounding regions.

11. A process for determining a size, an orientation and a position of rectangular objects in a two-dimensional image, comprising:

defining an image function having a recognizable characteristic when used on a single rectangular object;

calculating the image function in two different directions of the two-dimensional image;

using the image function to determine the size, the orientation and the position of the rectangular objects in the two-dimensional image.

12. The process of claim 11, wherein the recognizable characteristic is approximately a trapezoidal shape.

13. The process of claim 11, further comprising calculating the image function along rows and along columns of the two-dimensional image.

14. The process of claim 11, wherein the image function is the sum of data pixels along each of the two different directions.

15. The process of claim 11, further comprising searching for gaps in the image function.

16. The process of claim 15, further comprising:

determining that gaps are present in the image function; and

dividing the image into sub-images based on the gaps.

17. The process of claim 16, further comprising iteratively processing each sub-image until one of the following:

(a) a sub-image contains a single object;

(b) the sub-image cannot be further divided.

18. The process of claim 17, further comprising determining that the sub-image contains a single object by identifying the recognizable characteristic of the image function.

19. The process of claim 18, wherein the recognizable characteristic for a single rectangular object is a trapezoid.

20. The process of claim 17, further comprising determining that the sub-image cannot be further divided by finding no further gaps in the image function.

21. A method for determining a number, a size, an orientation and a position of rectangular objects contained in an image, comprising:

classifying each pixel within the image as one of;

(a) a data pixel;

(b) a background pixel;

calculating an image function along two or more different directions of the image;

examining the image function to determine whether a disparity is present;

dividing the image into sub-images if a disparity is found;

repeating the calculating, examining and dividing actions for each of the sub-images; and

examining the image and each of the sub-images to determine if the image functions have a recognizable shape.

22. The method as set forth in claim 21, wherein dividing the image further comprises dividing the image along a data disparity line.

23. The method as set forth in claim 21, wherein the image is a scanned image.

24. The method as set forth in claim 21, wherein the image function is a one-dimensional function.

25. The method as set forth in claim 21, wherein calculating an image function further comprises determining a sum of data pixels along each of the different directions.

26. The method as set forth in claim 21, further comprising determining that a sub-image contains a single object based on whether a disparity is found.

27. The method as set forth in claim 26, further comprising using a fitting algorithm to estimate a best fit of a trapezoid to the image function in each of the different directions.

28. The method as set forth in claim 27, further comprising forming an estimate of vertices of the rectangular objects using inflection points of the trapezoid.

29. A method for detecting and segregating rectangular objects in a two-dimensional image, comprising:

defining an image function that sums data pixels contained in the two-dimensional image along two orthogonal directions;

decomposing the two-dimensional image into a plurality of sub-images based gaps in the data pixels until one of the following occurs;

(a) each of the plurality of sub-images contains a single rectangular object;

(b) a sub-image cannot be further decomposed; and

using the image function to find a size, an orientation and a position for each of the single rectangular objects in the plurality of sub-images.

30. The method of claim 29, further comprising determining that a sub-image contains a single rectangular object by recognizing the shape characteristic of the image function of the object.

31. The method of claim 30, wherein the shape characteristic is approximately a trapezoid shape.

32. The method of claim 29, further comprising determining an estimate of vertices of a single rectangular object in a sub-image.

33. The method of claim 32, further comprising determining a best fit of the single rectangular object to contents of the sub-image.

34. The method of claim 33, wherein determining a best fit further comprises determining a rectangular object that minimizes a squared mean between data in the sub-image and a proposed rectangular fit.

35. The method as set forth in claim 29, wherein defining an image function that sums data pixels further comprises:

summing data pixels along each row of the two-dimensional image; and

summing data pixels along each column of the two-dimensional image.

36. An object detection and extraction system for processing digital image data, comprising:

a data pixel detection module that classifies each pixel within the digital image data and defines an image function;

a segmentation module that is capable of dividing the digital image data into smaller sub-images based on disparities in the image function; and

a single object extraction module that processes the sub-images to detect a number, a size, an orientation and a position of objects within the digital image data.

37. The object detection and extraction system as set forth in claim 36, wherein the object within the digital image data have rectangular shape.

38. The object detection and extraction system as set forth in claim 36, wherein the digital image data is a scanned two-dimensional image.

39. The object detection and extraction system as set forth in claim 36, wherein the single object extraction module further comprises a pixel analysis module that classifies pixels within a sub-image as one of:

(a) data pixel;

(b) background pixel.

40. The object detection and extraction system as set forth in claim 39, further comprising a verification module that compares estimated coordinates received from the pixel analysis module to the digital image data.

41. The object detection and extraction system as set forth in claim 36, further comprising an object location output module that outputs coordinates of the objects within the digital image data.