Method and system for classifying image elements

• US 20020136460A1
• Filed: 01/24/2002
• Published: 09/26/2002
• Est. Priority Date: 02/01/2001
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.), AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Haffner, Patrick Guy, Bottou, Leon
• Granted Patent: US 6,901,169 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06V 2201/01 Solutions for problems related to non-uniform document background
• CPC Class Codes: H04N 19/20 using video object coding

Abstract

A method, system, and machine-readable medium for classifying an image element as one of a plurality of categories, including assigning the image element based on a ratio between an unoccluded perimeter of the image element and an occluded perimeter of the image element and coding the image element according to a coding scheme associated with the category to which the image element is classified. Exemplary applications include image compression, where categories include image foreground and background layers.

Claims

1. A method of classifying an image element, comprising:

classifying the image element as one of a plurality of categories based on a ratio between an unoccluded perimeter of the image element and an occluded perimeter of the image element; and

coding the image element according to a coding scheme associated with the one of the plurality of categories.

2. The method of claim 1, wherein the plurality of categories comprises a foreground layer and a background layer.

3. The method of claim 1, wherein the unoccluded perimeter is calculated to be:

4. The method of claim 1, wherein the occluded perimeter is calculated to be:

R−

2L,

where R is a sum of perimeters of each horizontal scan line of the image element and L is a sum of lengths of contact segments between each horizontal scan line and the next horizontal scan line of the image element.

5. The method of claim 1, further comprising:

determining occluded portions of the image element; and

removing said occluded portions to determine a shape of the image element.

6. The method of claim 1, wherein the ratio is calculated to be:

7. The method of claim 6, wherein the color difference is calculated to be the largest of color differences between the image element and the at least one adjacent image element.

8. The method of claim 6, wherein the color difference is calculated to be an average of color differences between a predetermined number of the at least one adjacent image element and the image element.

9. The method of claim 1, wherein the image element is classified as the one of the plurality of categories if the ratio exceeds a predetermined threshold and the image element is classified as another of the plurality of categories otherwise.

10. A method of classifying an image element, comprising:

determining portions of the image element that intersect with a foreground layer and a background layer;

identifying the intersecting portions as occluded portions of the image element;

removing said occluded portions to determine a shape of the image element;

calculating an unoccluded perimeter and an occluded perimeter of the image element;

classifying the image element as one of a plurality of categories based on a ratio between the unoccluded perimeter of the image element and the occluded perimeter of the image element; and

coding the image element according to a coding scheme associated with the one of the plurality of categories.

11. The method of claim 10, wherein the unoccluded perimeter is calculated to be:

12. The method of claim 10, wherein the occluded perimeter is calculated to be:

R−

2L,

where R is a sum of perimeters of each horizontal scan line of the image element and L is a sum of lengths of contact segments between each horizontal scan line and the next horizontal scan line of the image element.

13. The method of claim 10, wherein the ratio is calculated to be:

15. The method of claim 14, further comprising:

coding the image element according to a coding scheme associated with the one of the plurality of categories.

16. The method of claim 15, wherein the coding schemes associated with the plurality of categories are each image compression schemes, the compression scheme of the background layer realizing a coded output with a relatively higher compression ratio and image loss than the compression scheme of the foreground layer.

17. The method of claim 14, wherein the unoccluded perimeter is calculated to be:

18. The method of claim 14, wherein the occluded perimeter is calculated to be:

R−

2L,

where R is a sum of perimeters of each horizontal scan line of the image element and L is a sum of lengths of contact segments between each horizontal scan line and the next horizontal scan line of the image element.

19. The method of claim 14, wherein the ratio is calculated to be:

14. A method of classifying image elements generated from an electronic image, each image element having a perimeter, the method comprising:

initializing each of a foreground layer and a background layer to be empty; and

iteratively, classifying the image elements as one of the foreground layer and the background layer,

wherein, for an i_th image element, the method comprises;

determining an amount of the image element that is unoccluded by other image elements previously classified as belonging to the foreground layer and the background layer, and

when a ratio of the unoccluded perimeter to the occluded perimeter of the image element exceeds a predetermined threshold, classifying the image element as belonging to the foreground layer and, otherwise, to the background layer.

20. A method of coding an image element, comprising:

determining whether a ratio between an unoccluded perimeter of the image element and an occluded perimeter of the image element is above a threshold value;

if the ratio is above the threshold value, classifying the image element as belonging to a foreground layer;

if the ratio is below or equal to the threshold value, classifying the image element as belonging to a background layer; and

coding the image element based on whether the image element is classified as belonging to the foreground layer or the background layer.

21. The method of claim 20, wherein the unoccluded perimeter is calculated to be:

22. The method of claim 20, wherein the occluded perimeter is calculated to be:

R−

2L,

where R is a sum of perimeters of each horizontal scan line of the image element and L is a sum of lengths of contact segments between each horizontal scan line and the next horizontal scan line of the image element.

23. The method of claim 20, wherein the ratio is calculated to be:

25. The system of claim 24, wherein the plurality of categories comprises a foreground layer and a background layer.

26. The system of claim 24, further comprising:

means for coding the image element according to a coding scheme associated with the one of the plurality of categories.

28. The system of claim 27, wherein the plurality of categories comprises a foreground layer and a background layer.

29. The system of claim 27, the processor further configured to code the image element according to a coding scheme associated with the one of the plurality of categories.

24. A system of classifying image elements, comprising:

means for generating an image element; and

means for classifying the image element as one of a plurality of categories based on a ratio between an unoccluded perimeter of the image element and an occluded perimeter of the image element.

27. A system of classifying image elements, comprising:

a memory device having embodied therein at least one image element; and

a processor in communication with the memory device, the processor configured to classify the image element to one of a plurality of categories based on a ratio between an unoccluded perimeter of the image element and an occluded perimeter of the image element.

30. A machine-readable medium containing program instructions for execution by a processor, that when executed by the processor, cause the processor to assign an image element to one of a plurality of categories based on a ratio between an unoccluded perimeter of the image element and an occluded perimeter of the image element.

31. The machine-readable medium of claim 30, wherein the plurality of categories includes a foreground layer and a background layer.

32. The machine-readable medium of claim 30, the processor further configured to code the image element according to a coding scheme associated with the one of the plurality of categories.

33. The machine-readable medium of claim 32, wherein the coding schemes associated with the plurality of categories are each image compression schemes, the compression scheme of the background layer realizing a coded output with a relatively higher compression ratio and image loss than the compression scheme of the foreground layer.

34. The machine-readable medium of claim 30, wherein the unoccluded perimeter is calculated to be:

35. The machine-readable medium of claim 30, wherein the occluded perimeter is calculated to be:

R−

2L,

where R is a sum of perimeters of each horizontal scan line of the image element and L is a sum of lengths of contact segments between each horizontal scan line and the next horizontal scan line of the image element.

36. The machine-readable medium of claim 30, further configured to:

determine occluded portions of the image element; and

remove the occluded portions to determine a shape of the image element.

37. The machine-readable medium of claim 30, wherein the ratio is calculated to be:

38. The machine-readable medium of claim 37, wherein the color difference is calculated to be a largest of color differences between the image element and the at least one adjacent image element.

39. The machine-readable medium of claim 37, wherein the color difference is calculated to be an average of color differences between a predetermined number of the at least one adjacent image element and the image element.

40. The machine-readable medium of claim 30, wherein the image element is assigned to the one of the plurality of categories if the ratio exceeds a predetermined threshold and, otherwise, to another of the plurality of categories.