US5546474A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Detection of photo regions in digital images
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-12-21
•
Granted: 1996-08-13
•
Expires: 2013-12-21
Abstract
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.
Inventors
- 👤 Oscar A. Zuniga
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:16
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/40062; G; G06; G06T; G06T7/00; G06T7/10; G06T7/11; G06T7/187; G06T7/40; G06T7/41; G06T7/45; G06V; G06V30/00; G06V30/10; G06V30/16; G06V30/162; G06V30/40; G06V30/41; G06V30/413; G06T2207/00; G06T2207/10; G06T2207/10004; G06T2207/10008; G06T2207/30; G06T2207/30176
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
211 words
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.
Claim 2
Independent Claim
211 words
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.
Claim 3
Dependent Claim
34 words
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.
Claim 4
Dependent Claim
39 words
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.
Claim 5
Dependent Claim
52 words
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.
Claim 6
Dependent Claim
37 words
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.
Claim 7
Dependent Claim
20 words
The method of claim 5, wherein said quantizing step (a)(iii) is performed using non-uniform quantization to match human eye response.
Claim 8
Dependent Claim
137 words
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.
Claim 9
Dependent Claim
39 words
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: histo[K-1]<histo[K]>histo[K+1]; and 2histo[K]-histo[K-1]-histo[K+1]>histo[K]/10.
Claim 10
Dependent Claim
42 words
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: histo[K-1]<histo[K]>histo[K+2]; where histo[K]=histo[K+1]; and 2histo[k]-histo[K-1]-histo[K+1]>histo[K]/10. 10.
Claim 11
Dependent Claim
58 words
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##
Claim 12
Dependent Claim
43 words
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.
Claim 13
Dependent Claim
102 words
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.
Claim 14
Independent Claim
282 words
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.
Claim 15
Independent Claim
282 words
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.
Claim 16
Dependent Claim
45 words
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.
Claim 17
Dependent Claim
40 words
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: histo[K-1]<histo[K]>histo[K+1]; and 2histo[K]-histo[K-1]-histo[K+1]>histo[K]/10. 16.
Claim 18
Dependent Claim
41 words
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: histo[K-1]<histo[K]>histo[K+2]; where histo[K]=histo[K+1]; and 2histo[k]-histo[K-1]-histo[K+1]>histo[K]/10.
Claim 19
Dependent Claim
58 words
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##
Claim 20
Dependent Claim
44 words
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.
Claim 21
Dependent Claim
102 words
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.
References Cited (Backward Citations)
US4577235A
Cited
US4668995A
Cited
US4817169A
Cited
US5073953A
Cited
US5067163A
Cited
US5131049A
Cited
US5179599A
Cited
US5327262A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-13 | 2000-02-12 | 2000-08-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-13 | 2004-02-12 | 2004-08-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-13 | 2008-02-12 | 2008-08-13 | $7700.00 | Window Closed / Lapsed |