Detection of photo regions in digital images

• US 5,546,474 A
• Filed: 12/21/1993
• Issued: 08/13/1996
• Est. Priority Date: 12/21/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Zuniga, Oscar A.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): DEL ROSSO, GERARD DOMNICK
• Application Number:
  US08/171,551
• Time in Patent Office: 966 Days
• Field of Search: 382/9, 382/18, 382/51, 382/48, 358/453, 358/462
• US Class Current: 382/176
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06T 7/45 using co-occurrence matrix computation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/162 Quantising the image signal
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

A method for classifying regions in a digital image as either photo regions or non-photo regions is presented. A digital image is divided into regions and each region is divided into a plurality of cells. Each cell comprises a group of pixels represented by one or more digital bits. Features of a cell such as its graylevel spread, or the moment of inertia of its co-occurrence matrix, are used to determine the likelihood that the cell is a photo cell or a non-photo cell. Based on this likelihood, the cell is classified as either a photo cell, a non-photo cell, or is unclassified. Classified cell is used in conjunction with unclassified cells to grow regions that can be characterized as photo regions or non-photo regions. Once a region is classified as a photo region or a non-photo region a decision is made regarding the number of bits per pixel needed to adequately represent that region.

Claims

1. A method for classifying a region in a digital image as either a photo region or a non-photo region, wherein each region comprises a plurality of cells, the method comprising the steps of:

(a) extracting one or more features about each of said plurality of cells, wherein said one or more features indicate a likelihood that said cell is a photo cell, including the step of;

(I) determining a moment of inertia about a main diagonal of a co-occurrence matrix of said cell, including the steps of;

(1) constructing a co-occurrence matrix for each of said cells, said co-occurrence matrix having elements representing a number of times a pixel having a first graylevel is adjacent to a pixel having a second graylevel, and

(2) determining a moment of inertia of said co-occurrence matrix, said moment of inertia indicating an amount of graylevel transitions;

(b) determining whether each of said cells is likely to be a photo cell based on said one or more features extracted in step (a);

(c) labeling each of said cells as either a photo cell or a non-photo cell, or an unclassified cell, said classification based on the result of said step (b); and

(d) growing region as either photo regions or non-photo regions using said cells.

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

(e) after said steps (a) through (d), assigning a number of bits per pixel to each region based on the classification of each region.

3. The method of claim 2, further comprising a step of:

(f) after said step (e), determining a threshold level for each said non-photo region; and

(g) after said step (f), converting each said non-photo region to a one-bit-per-pixel format.

4. The method of claim 1, wherein each pixel is represented by one of a plurality of graylevels and wherein said step (a) of feature extraction further comprises the step of:

(ii) constructing a graylevel histogram indicating the number of pixels in each of said plurality of cells that are in each graylevel.

5. The method of claim 4, wherein said step (a) of feature extraction further comprises the step of:

(iii) before said step (a)(ii), quantizing the digital image to convert the number of bits used to represent each pixel.

6. The method of claim 5, wherein said quantizing step (a)(iii) is performed using non-uniform quantization to match human eye response.

7. The method of claim 4, wherein said one or more features extracted during said step (a) of feature extraction is a graylevel spread for said cell, and further wherein said step (a) of determining a graylevel spread for said cell further comprises the step of:

(iii) determining a graylevel spread for each of said plurality of cells, including the steps of;

(1) determining which graylevels of said graylevel histogram represent peaks, and which graylevels represent valleys;

(2) determining a subpopulation for each peak of said graylevel histogram;

(3) determining a probability of each subpopulation;

(4) determining a spread of each subpopulation;

(5) determining a separation indication of each subpopulation; and

(6) determining said graylevel spread of said graylevel histogram using said probability of each subpopulation, said spread of each subpopulation, and said separation indication of each subpopulation.

8. The method of claim 7, wherein said graylevel histogram comprises M elements defined by histo[K], K=0, . . . , M, and said step (a)(iii)(1) of determining said peaks comprises the step of:

a) determining whether;

space="preserve" listing-type="equation">histo[K-1]<

histo[K]>

histo[K+1];

and

space="preserve" listing-type="equation">2histo[K]-histo[K-1]-histo[K+1]>

histo[K]/10.

9. The method of claim 7, wherein said graylevel histogram comprises M elements defined by histo[K], K=0, . . . , M, and said step (a)(iii)(1) of determining said peaks comprises the step of:

a) determining whether;

space="preserve" listing-type="equation">histo[K-1]<

histo[K]>

histo[K+2];

where

space="preserve" listing-type="equation">histo[K]=histo[K+1];

and

space="preserve" listing-type="equation">2histo[k]-histo[K-1]-histo[K+1]>

histo[K]/10.

10.

10. The method of claim 7, wherein said graylevel histogram comprises M elements defined by histo[K], K=0, . . . , M, said peaks at a graylevel K are defined by peak[K], and two valleys adjacent to peak[K] are defined by val[K] and val[K+1], wherein said step (a)(iii)(3) for determining a probability of each subpopulation is given by:

##EQU11##

11. The method of claim 4, wherein said step (d) for growing regions as either non-photo regions or photo regions comprises the steps of:

(i) growing non-photo regions;

(ii) after said step (d)(i) for growing non-photo regions, classifying all other regions as photo regions.

12. The method of claim 1, wherein for each of said cells labelled as non-photo cells, said step (d)(i) for growing non-photo regions comprises the steps of:

(1) determining whether the difference between the graylevel of a bright peak of said graylevel histogram of said non-photo cell and the graylevel of a bright peak of said graylevel histogram of a neighboring unclassified cell is larger than one graylevel; and

(2) classifying said neighboring cell as a non-photo cell when said difference is not larger than one graylevel;

(3) classifying a combination of said non-photo cell and said neighboring cell as a non-photo region.

13. A method for classifying a region in a digital image as either a photo region or a non-photo region, wherein each region comprises a plurality of cells, each of said plurality of cells comprising pixels, each of said pixels represented by one of a plurality of graylevels, the method comprising the steps of:

(a) extracting one or more features about each of said plurality of cells, wherein said one or more features indicate a likelihood that said cell is a photo cell, and further wherein said one or more features include a graylevel spread for said cell, including the step of;

(i) constructing a graylevel histogram indicating the number of pixels in each of said plurality of cells that are in each graylevel, and

(ii) determining a graylevel spread for each of said plurality of cells, including the steps of;

(1) determining which graylevels of said graylevel histogram represent peak, and which graylevels represent valleys,

(2) determining a subpopulation for each peak of said graylevel histogram,

(3) determining a probability of each subpopulation,

(4) determining a spread of each population,

(5) determining a separation indication of each subpopulation, and

(6) determining said graylevel spread of said graylevel histogram using said probability of each subpopulation, said spread of each subpopulation, and said separation indication of each subpopulation;

(b) determining whether each of said cells is likely to be a photo cell based on said one or more features extracted in step (a);

(c) labeling each of said cells as either a photo cell, a non-photo cell, or an unclassified cell, said classification based on the result of step (b); and

(d) growing regions as either photo regions or non-photo regions using said cells.

14. The method of claim 13, wherein said step (a) of feature extraction further comprises the step of:

(iii) before said step (a)(ii), quantizing the digital image to convert the number of bits used to represent each pixel using non-uniform quantization to match human eye response.

15. The method of claim 13, wherein said graylevel histogram comprises M elements defined by histo[K], K=0, . . . , M, and said step (a)(ii)(1) of determining said peaks comprises the step of:

a) determining whether;

space="preserve" listing-type="equation">histo[K-1]<

histo[K]>

histo[K+1];

and

space="preserve" listing-type="equation">2histo[K]-histo[K-1]-histo[K+1]>

histo[K]/10.

16.

16. The method of claim 13, wherein said graylevel histogram comprises M elements defined by histo[K], K=0, . . . , M, and said step (a)(ii)(1) of determining said peaks comprises the step of:

a) determining whether;

space="preserve" listing-type="equation">histo[K-1]<

histo[K]>

histo[K+2];

where

space="preserve" listing-type="equation">histo[K]=histo[K+1];

and

space="preserve" listing-type="equation">2histo[k]-histo[K-1]-histo[K+1]>

histo[K]/10.

17. The method of claim 13, wherein said graylevel histogram comprises M elements defined by histo[K], K=0, . . . , M, said peaks at a graylevel K are defined by peak[K], and two valleys adjacent to peak[K] are defined by val[K] and val[K+1], wherein said step (a)(ii)(3) for determining a probability of each subpopulation is given by:

##EQU12##

18. The method of claim 13, wherein said step (d) for growing regions as either non-photo regions or photo regions comprises the steps of:

(i) growing non-photo regions; and

(ii) after said step (d)(i) for growing non-photo regions, classifying all other regions as photo regions.

19. The method of claim 18, wherein for each of said cells labelled as non-photo cells, said step (d)(i) for growing non-photo regions comprises the steps of:

(1) determining whether the difference between the graylevel of a bright peak of said graylevel histogram of said non-photo cell and the graylevel of a bright peak of said graylevel histogram of a neighboring unclassified cell is larger than one graylevel;

(2) classifying said neighboring cell as a non-photo cell when said difference is not larger than one graylevel; and

(3) classifying a combination of said non-photo cell and said neighboring cell as a non-photo region.