Identifying one or more objects within an image

• US 7,805,003 B1
• Filed: 11/18/2003
• Issued: 09/28/2010
• Est. Priority Date: 11/18/2003
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Cohen, Scott D., Wilensky, Gregg D.
• Primary Examiner(s): Le; Vu
• Assistant Examiner(s): Allison; Andrae S
• Application Number:
  US10/716,782
• Time in Patent Office: 2,506 Days
• Field of Search: 382/199, 382164-172, 382/103, 382/266, 382/281, 382/203
• US Class Current: 382/173
• 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

Methods and apparatus, including computer program products, implementing techniques for identifying one or more objects within an image. The techniques include receiving an image that includes at least one object; identifying a plurality of edge pixels in the image, an edge pixel being a pixel that borders two contrasting areas of the image, the plurality of edge pixels including both inner edge pixels and outer edge pixels; and finding a substantially connected component correlated with each object, the substantially connected component comprising a set of the edge pixels that are connected by traversing substantially only edge pixels.

Claims

1. A computer-implemented method for identifying multiple objects within an image, the method comprising:

receiving, in a programmable computer system, an image that includes two or more non-overlapping embedded images from an input device coupled to the programmable computer system;

identifying a plurality of edge pixels in the image based on a respective gradient value associated with each of the plurality of edge pixels, wherein the gradient value of each edge pixel satisfies a first threshold value;

identifying one or more non-edge pixels in the image based on a respective gradient value associated with each of the plurality of non-edge pixels, wherein the gradient value of each non-edge pixel satisfies a second threshold value;

selecting an edge pixel from the plurality of edge pixels;

identifying a substantially connected component that includes non-edge pixels and a plurality of substantially connected edge pixels being substantially connected to the selected edge pixel, wherein a number of non-edge pixels in the substantially connected component is based on a level of tolerance for non-edge pixels; and

identifying within the image a bounding area, wherein the bounding area surrounds the substantially connected component.

2. The method of claim 1, wherein identifying a plurality of edge pixels includes computing the respective gradient value for each of a plurality of pixels in the image.

3. The method of claim 2, wherein computing the respective gradient value for each of the plurality of pixels includes, for each pixel, comparing respective pixel colors of a neighborhood of pixels surrounding each pixel.

4. The method of claim 2, wherein computing the respective gradient value for each of the plurality of pixels includes using an image smoothing filter to filter noise from the image.

5. The method of claim 1, further comprising passing the bounding area to a processor that extracts a location of an embedded image from the two or more non-overlapping images.

6. The method of claim 5, further comprising refining the extracted location.

7. The method of claim 6, further comprising using the extracted location to crop the embedded image from the image.

8. The method of claim 1, further comprising splitting the bounding area of the image into a first of the two or more non-overlapping embedded images and a second of the two or more non-overlapping embedded images.

9. The method of claim 1, further comprising merging the bounding area within the image with another bounding area within the image into a single bounding area.

10. The method of claim 1, further comprising:

extracting a location of each of the two or more non-overlapping embedded images from the image; and

using the location to seed a crop operation.

11. The method of claim 10, wherein using the location to seed a crop operation includes:

for each of the two or more non-overlapping embedded images in the image, using the location to define a cropping area; and

cropping all the defined cropping areas in a single cropping operation.

12. The method of claim 11, wherein:

the location specifies an alignment of one of the two or more non overlapping embedded images with respect to the image; and

using the location to define a cropping area includes using the alignment of one of the two or more non overlapping embedded images to define an alignment of the cropping area.

13. The method of claim 11, further comprising:

prior to cropping all the defined cropping areas, adjusting one or more of the defined cropping areas in response to user input.

14. The method of claim 11, further comprising:

prior to cropping all the defined cropping areas, merging two of the defined cropping areas into a single defined cropping area in response to user input.

15. The method of claim 13, wherein adjusting one or more of the defined cropping areas includes splitting a single cropping area into two or more cropping areas.

32. The method of claim 1 further comprising setting the tolerance level based on a user input.

33. The method of claim 1 further comprising automatically determining the tolerance level as a function of a spacing between the objects.

16. A non-transitory computer program product, tangibly stored on a computer-readable medium, for identifying multiple objects within an image, comprising instructions operable to cause a programmable processor to perform operations comprising:

receiving an image that includes two or more non-overlapping embedded images;

identifying a plurality of edge pixels in the image based on a respective gradient value associated with each of the plurality of edge pixels, wherein the gradient value of each edge pixel satisfies a first threshold value;

identifying one or more non-edge pixels in the image based on a respective gradient value associated with each of the plurality of non-edge pixels, wherein the gradient value of each non-edge pixel satisfies a second threshold value;

selecting an edge pixel from the plurality of edge pixels;

identifying a substantially connected component that includes non-edge pixels and a plurality of substantially connected edge pixels being substantially connected to the selected edge pixel, wherein a number of non-edge pixels in the substantially connected component is based on a level of tolerance for non-edge pixels; and

identifying within the image a bounding area, wherein the bounding area surrounds the substantially connected component.

17. The product of claim 16, wherein identifying a plurality of edge pixels includes computing the respective gradient value for each of a plurality of pixels in the image.

18. The product of claim 17, wherein computing the respective gradient value for each of the plurality of pixels includes, for each pixel, comparing respective pixel colors of a neighborhood of pixels surrounding each pixel.

19. The product of claim 17, wherein computing the respective gradient value for each of the plurality of pixels includes using an image smoothing filter to filter noise from the image.

20. The product of claim 16, wherein the operations further comprise passing the bounding area to a processor that extracts a location of an embedded image from the two or more non-overlapping images.

21. The product of claim 20, wherein the operations further comprise refining the extracted location.

22. The product of claim 21, wherein the operations further comprise using the extracted location to crop the embedded image from the image.

23. The product of claim 16, wherein the operations further comprise splitting the bounding area of the image into a first of the two or more non-overlapping embedded images and a second of the two or more non-overlapping embedded images.

24. The product of claim 16, wherein the operations further comprise merging the bounding area within the image with another bounding area within the image into a single bounding area.

25. The product of claim 16, wherein the operations further comprise:

extracting a location of each of the two or more non-overlapping embedded images from the image; and

using the location to seed a crop operation.

26. The product of claim 25, wherein using the location to seed a crop operation includes:

for each of the two or more non-overlapping embedded images in the image, using the location to define a cropping area; and

cropping all the defined cropping areas in a single cropping operation.

27. The product of claim 26, wherein:

the location specifies an alignment of one of the two or more non overlapping embedded images with respect to the image; and

using the location to define a cropping area includes using the alignment of one of the two or more non overlapping embedded images to define an alignment of the cropping area.

28. The product of claim 26, wherein the operations further comprise:

prior to cropping all the defined cropping areas, adjusting one or more of the defined cropping areas in response to user input.

29. The product of claim 26, wherein the operations further comprise:

prior to cropping all the defined cropping areas, merging two of the defined cropping areas into a single defined cropping area in response to user input.

30. The product of claim 28, wherein adjusting one or more of the defined cropping areas includes splitting a single cropping area into two or more cropping areas.

34. The product of claim 16, further comprising instructions operable to cause the programmable processor to set the tolerance level based on a user input.

35. The product of claim 16, further comprising instructions operable to cause the programmable processor to automatically determine the tolerance level as a function of a spacing between the embedded images.

31. A non-transitory computer program product, tangibly stored on a computer-readable medium, for identifying multiple objects within a scanned image, comprising instructions operable to cause a programmable processor to perform operations comprising:

receiving a scanned image that includes multiple non-overlapping embedded images; and

identifying the multiple non-overlapping embedded images by;

(1) generating an edge pixel map of the image based on a respective gradient value associated with each pixel in the scanned image, the edge pixel map identifying each pixel in the scanned image as being an edge pixel or a non-edge pixel, an edge pixel being a pixel having a gradient value satisfying a first threshold value and a non-edge pixel being a pixel satisfying a second threshold value;

(2) scanning the edge pixel map until an edge pixel is found;

(3) identifying a substantially connected component containing the edge pixel, the substantially connected component being a set of edge pixels that are substantially connected by traversing adjacent edge pixels and adjacent non-edge pixels, wherein a number of non-edge pixels in the substantially connected component is based on a level of tolerance for non-edge pixels;

(4) identifying within the image a bounding area surrounding the substantially connected component, and extracting one of the multiple non-overlapping embedded images based on the bounding area;

(5) erasing from the edge pixel map all the pixels that belong to the substantially connected component or that correspond to pixels inside the extracted one of the multiple non-overlapping embedded images; and

(6) repeating steps (2) through (5) until no more edge pixels are found.

36. The product of claim 31, further comprising instructions operable to cause the programmable processor to set the tolerance level based on a user input.

37. The product of claim 31, further comprising instructions operable to cause the programmable processor to automatically determine the tolerance level as a function of a spacing between the embedded images.

38. A system comprising:

a display device;

a machine-readable storage device including a program product; and

one or more processors operable to execute the program product, interact with the display device, and perform operations comprising;

receiving an image that includes two or more non-overlapping embedded images;

identifying a plurality of edge pixels in the image based on a respective gradient value associated with each of the plurality of edge pixels, wherein the gradient value of each edge pixel satisfies a first threshold value;

identifying one or more non-edge pixels in the image based on a respective gradient value associated with each of the plurality of non-edge pixels, wherein the gradient value of each non-edge pixel satisfies a second threshold value;

selecting an edge pixel from the plurality of edge pixels;

identifying a substantially connected component that includes non-edge pixels and a plurality of substantially connected edge pixels being substantially connected to the selected edge pixel, wherein a number of non-edge pixels in the substantially connected component is based on a level of tolerance for non-edge pixels; and

identifying within the image a bounding area, wherein the bounding area surrounds the substantially connected component.

39. The system of claim 38 wherein identifying a plurality of edge pixels includes computing the respective gradient value for each of a plurality of pixels in the image.

40. The system of claim 39 wherein computing the respective gradient value for each of the plurality of pixels includes, for each pixel, comparing respective pixel colors of a neighborhood of pixels surrounding each pixel.

41. The system of claim 39 wherein computing the respective gradient value for each of the plurality of pixels includes using an image smoothing filter to filter noise from the image.

42. The system of claim 38 wherein the one or more processors are operable to perform operations further comprising extracting a location of an embedded image from the two or more non-overlapping images.

43. The system of claim 42 wherein the one or more processors are operable to perform operations further comprising refining the extracted location.

44. The system of claim 38 wherein the one or more processors are operable to perform operations further comprising using the extracted location to crop the embedded image from the image.

45. The system of claim 38 wherein the one or more processors are operable to perform operations further comprising splitting the bounding area of the image into a first of the two or more non-overlapping embedded images and a second of the two or more non-overlapping embedded images.

46. The system of claim 38 wherein the one or more processors are operable to perform operations further comprising merging the bounding area within the image with another bounding area within the image into a single bounding area.

47. The system of claim 38 wherein the one or more processors are operable to perform operations further comprising:

extracting a location of each of the two or more non-overlapping embedded images from the image; and

using the location to seed a crop operation.

48. The system of claim 47 wherein using the location to seed a crop operation includes:

for each of the two or more non-overlapping embedded images in the image, using the location to define a cropping area; and

cropping all the defined cropping areas in a single cropping operation.

49. The system of claim 48 wherein:

the location specifies an alignment of one of the two or more non overlapping embedded images with respect to the image; and

using the location to define a cropping area includes using the alignment of one of the two or more non overlapping embedded images to define an alignment of the cropping area.

50. The system of claim 48 wherein the one or more processors are operable to perform operations further comprising:

prior to cropping all the defined cropping areas, adjusting one or more of the defined cropping areas in response to user input.

51. The system of claim 48 wherein the one or more processors are operable to perform operations further comprising:

prior to cropping all the defined cropping areas, merging two of the defined cropping areas into a single defined cropping area in response to user input.

52. The system of claim 50 wherein adjusting one or more of the defined cropping areas includes splitting a single cropping area into two or more cropping areas.