Method and apparatus for image classification and halftone detection

• US 6,185,335 B1
• Filed: 07/07/1998
• Issued: 02/06/2001
• Est. Priority Date: 07/07/1998
• Status: Expired due to Term

• Current Assignee: Electronics For Imaging Incorporated
• Original Assignee: Electronics For Imaging Incorporated
• Inventors: Karidi, Ron J., Nordstrom, Niklas
• Primary Examiner(s): LEE, TOMMY D
• Application Number:
  US09/111,047
• Time in Patent Office: 945 Days
• Field of Search: 382/162, 382/168, 382/170, 382/172, 382/224, 382/229, 358/455, 358/456, 358/462, 358/534
• US Class Current: 382/224
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

A method and apparatus for image classification includes a first embodiment, in which halftone detection is performed based on the size of a boundary set between a class of light pixels and a class of dark pixels, and further based upon image information contained within each single image plane (i.e within one color plane). This embodiment of the invention is based upon the distinctive property of images that halftone areas within the image have larger boundary sets than non-halftone areas within the image. A second, equally preferred embodiment of the invention provides a cross color difference correlation technique that is used to detect halftone pixels.

Claims

1. A method for image classification and halftone detection, comprising:

selecting a subject pixel;

separating neighbor pixels about the subject pixel into light and dark classes in a first neighborhood;

measuring a size of a boundary set between the light and dark classes in a second neighborhood;

determining if the boundary size is less than a first threshold, wherein the subject pixel is not a halftone pixel; and

determining if the boundary size is equal to or greater than the first threshold, wherein the subject pixel is a halftone pixel, and wherein descreening techniques may optionally be applied to the subject pixel.

2. The method of claim 1, wherein said first threshold is adaptively determined.

3. The method of claim 2, further comprising the steps of:

counting the number of vertical class changes and horizontal class changes which occur in said second neighborhood;

denoting the percentage of light pixels in said second neighborhood as p;

denoting the percentage of dark pixels as q;

determining the type of said subject pixel by comparing the actual number of class changes counted to a probability based estimate to determine a ratio therebetween; and

declaring said subject pixel a halftone pixel if said ratio is higher than a second threshold;

wherein said subject pixel is otherwise not a halftone pixel.

4. The method of claim 1, wherein the light/dark separation is performed using any of a histogram technique and a weighted support technique.

5. The method of claim 4, wherein a second threshold is set using said histogram technique, the method further comprising:

computing a histogram of values in the first neighborhood;

analyzing the histogram; and

determining the threshold.

6. The method of claim 5, further comprising the steps of:

finding a right peak area and left peak area in said histogram;

setting said first threshold to a median if said right peak area and said left peak area intersect, otherwise setting said first threshold to the end of the larger of said right peak area and said left peak area.

7. The method of claim 4, wherein a second threshold is set using the weighted support technique, the method further comprising:

setting;

threshold=(avg_d+avg_l)/2;

wherein;

center=intensity of the subject pixel;

cnt_d=number of pixels within the second neighborhood that are darker than the subject pixel;

cnt_l=number of pixels within the second neighborhood that are lighter than the subject pixel;

avg_d=average of intensities that are darker than the subject pixel;

avg_l=average of intensities that are lighter than the subject pixel;

avg=average of intensities in the second neighborhood; and

dev=standard deviation of intensities in the second neighborhood.

8. The method of claim 7, further comprising the steps of:

setting;

D1=(center-avg_d)/(avg_l-center)≦

½

D2=center<

threshold−

8

D3=cnt_d/cnt_l≦

⅓

D4=cnt_d/cnt_l≦

½

D5=center<

50

D6=cnt_d<

cnt_l

and

L1=(avg_l-center)/(avg-avg__d)≧

½

L2=center>

threshold+8

L3=cnt_l/cnt_d≦

⅓

L4=cnt_l/cnt_d≦

½

L5=cint>

200

L6=cnt_l<

cnt_d

 

wherein;

D_support=5*D1+4*D2+3*D3+2(D4+D5)+D6;

 

and

L_support=5*L1+4*L2+3*L3+2(L4+L5)+L6 and;

wherein said center pixel is light if (D_support<

L_support);

said center pixel is light if (D_support=L_support); and

(cnt_L<

cnt_D) and otherwise said center pixel is dark.

9. The method of claim 8, wherein a model is introduced for a two class population distribution, comprising the steps of:

performing 2*WL(WL−

1) exclusive OR, in a window measuring WL×

WL, where WL(WL−

1) exclusive ORs are applied for a vertical boundary and WL(WL−

1) exclusive ORs are applied for a horizontal boundary;

denoting N_compares=2*W(WL−

1), where there is an expected number of class changes that is equal to N_compares*(pq+qp),

where;

p=probability (dark pixel),

and

q=1−

p=probability (light pixel); and

approximating p by DC/WS, q by LC/WS, then the expected size of a boundary which is denoted by Boundary_expected, is N_compares*2pq.

wherein;

W=the width of said second neighborhood to one side;

WL=the length of said second neighborhood, wherein WL is equal to (2*W)+1;

WS=the size of the second neighborhood, which is equal to WL*WL;

N_compares=2*WL*(WL−

1);

VB=the number of pixels that are of a different class than a pixel directly above them;

HB=the number of pixels that are of a different class than a pixel directly to the left of them;

BT=Boundary threshold;

LC=the number of light pixels; and

DC=the number of dark pixels.

10. The method of claim 9, wherein:

Boundary_expected=(2*N_compares) (LC/WS) (DC/WS).

11. The mehtod of claim 10, further comprising the step of:

marking said subject pixel as not halftone if Boundary size=VB+HB<

Boundary_expected*BT;

otherwise marking said subject pixel as half;

wherein an external parameter BT allows a degree of freedom when fitting to a binamial model.

12. The method of claim 10, wherein said subject pixel is not halftone if LC<

W or DC<

W.

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

applying a cross correlation technique to detect halftone pixels.

14. The method of claim 13, comprising the step of:

computing a correlation between an R plane, a G plane, and a B plane inside a square neighborhood of said subject pixel;

wherein a low correlation factor indicates a halftone area having halftone screens that are not the same for all colors.

15. The method of claim 14, further comprising the steps of:

calculating a variational norm within a single component window, wherein Rij=Rij−

R, Gij=Gij_G, Bij=Bij_B;

16. A method for image classification and halftone detection, comprising the steps of:

selecting a subject pixel;

separating neighbor pixels about said subject pixel into light and dark classes in a first neighborhood;

measuring the size of a boundary between said light and dark classes in a second neighborhood;

determining if said boundary size is less than a first threshold, wherein said subject pixel is not a halftone pixel;

determining if said boundary size is equal to or greater than said first threshold, wherein said subject pixel is a halftone pixel, and wherein descreening techniques may optionally be applied to said subject pixel; and

applying a cross correlation technique to detect halftone pixels.

17. An apparatus for image classification and halftone detection, comprising:

a first neighborhood consisting of;

a subject pixel; and

neighbor pixels about said subject pixel;

wherein said neighbor pixels about said subject pixel are separated into light and dark classes in said first neighborhood;

a second neighborhood, wherein the size of a boundary set between said light and dark classes in said second neighborhood is measured;

means for determining if said boundary size is less than a first threshold, wherein said subject pixel is not a halftone pixel;

means for determining if said boundary size is equal to or greater than said first threshold, wherein said subject pixel is a halftone pixel; and

means for optionally applying descreening techniques to said subject pixel.

18. The apparatus of claim 17, wherein said first threshold is adaptively determined.

19. The apparatus of claim 18, further comprising:

means for counting the number of vertical class changes and horizontal class changes which occur in said second neighborhood;

means for denoting the percentage of light pixels in said second neighborhood as p;

means for denoting the percentage of dark pixels as q;

means for determining said first threshold by comparing the actual number of class changes counted to a probability based estimate to determine a ratio therebetween; and

means for declaring said subject pixel a halftone pixel if said ratio is higher than said a second threshold;

wherein said subject pixel is otherwise not a halftone pixel.

20. The apparatus of claim 17, wherein said light/dark separation is performed using any of a histogram technique and a weighted support technique.

21. The apparatus of claim 20, wherein said light/dark separation is performed using said histogram technique, said apparatus further comprising:

means for computing a histogram of values in said first neighborhood;

means for analyzing said histogram;

means for declaring a pixel as darkdarker than a second threshold and declaring said pixel as light if it is lighter than said second threshold; and

means for determining said second threshold.

22. The apparatus of claim 21, further comprising:

means for finding a right peak area and left peak area in said histogram; and

means for setting said first threshold to a median if said right peak area and said left peak area intersect, otherwise setting said first threshold to the end of the larger of said right peak area and said left peak area.

23. The apparatus of claim 17, wherein said dark/light separation is performed using said weighted support technique, said apparatus further comprising:

means for setting;

threshold=(avg_d+avg_l)/2;

wherein;

center=intensity of said subject pixel;

cnt_d=number of pixels within said second neighborhood that are darker than said subject pixel;

cnt_l=number of pixels within said second neighborhood that are lighter than said subject pixel;

avg_d=average of intensities that are darker than said subject pixel;

avg_l=average of intensities that are lighter than said subject pixel;

avg=average of intensities in said second neighborhood; and

dev=standard deviation of intensities in said second neighborhood.

24. The apparatus of claim 23, further comprising:

means for setting;

D1=(center-avg_d)/(avg_l-center)≦

½

D2=center<

threshold−

8

D3=cnt_d/cnt_l≦

⅓

D4=cnt_d/cnt_l≦

½

D5=center<

50

D6=cnt_d<

cnt_l

and

L1=(avg_l-center)/(avg-avg_d)≧

½

L2=center>

threshold+8

L3=cnt_l/cnt_d≦

⅓

L4=cnt_l/cnt_d≦

½

L5=cint>

200

L6=cnt_l<

cnt_d

wherein;

D_support=5*D1+4*D2+3*D3+2(D4+D5)+D6;

and

L_support=5*L1+4*L2+3*L3+2(L4+L5)+L6 and;

wherein said center pixel is light if (D_support<

L_support);

said center pixel is light if (D_support=L_support); and

(cnt_L<

cnt_D) and otherwise said center pixel is dark.

25. The apparatus of claim 24, wherein a model is introduced for a two class population distribution, comprising:

means for performing 2*WL(WL−

1) exclusive ORs in a window measuring WL×

WL, where WL(WL−

1) exclusive ORs are applied for a vertical boundary and WL(WL−

1) exclusive ORs are applied for a horizontal boundary;

means for denoting N_compares=2*W*(WL−

1) where there is an expected number of class changes that is equal to N_compares*(pq+qp),

where;

p=probability (dark pixel),

and

q=1−

p=probability (light pixel); and

means for approximating pN DC/WS, qN LC/WS, such that the expected size of a boundary which is denoted by Boundary_expected, is N_compares*2pq;

wherein;

W=the width of said second neighborhood to one side;

WL=the length of said second neighborhood, wherein WL is equal to (2*W)+1;

WS=the size of the second neighborhood, which is equal to WL*WL;

N_compares=2*WL*(WL−

1);

VB=the number of pixels that are of a different class than a pixel directly above them;

HB=the number of pixels that are of a different class than a pixel directly to the left of them;

BT=Boundary threshold;

LC=the number of light pixels; and

DC=the number of dark pixels.

26. The apparatus of claim 25, wherein:

Boundary_expected=(2 *N_compares) (LC/WS) (DC/WS).

27. The apparatus of claim 26, further comprising:

means for marking said subject pixel as not halftone if Boundary size=VB+HB<

Boundary_expected*BT;

otherwise marking said subject pixel as half;

wherein an external parameter BT allows a degree of freedom when fitting to be a binomial model.

28. The apparatus of claim 26, wherein said subject pixel is not halftone if LC<

W or DC<

W.

29. The apparatus of claim 17, further comprising:

means for applying a cross correlation technique to detect halftone pixels.

30. The apparatus of claim 29, further comprising:

means for computing a correlation between an R plane, a G plane, and a B plane inside a square neighborhood of said subject pixel;

wherein a low correlation factor indicates a halftone area having halftone screens that are not the same for all colors.

31. The apparatus of claim 30, further comprising:

means for calculating a variational norm within a single component window, wherein Rij=Rij−

R, Gij=Gij−

G , Bij=Bij−

B;

32. An apparatus for image classification and halftone detection, comprising:

means for selecting a subject pixel;

means for separating neighbor pixels about said subject pixel into light and dark classes in a first neighborhood;

means for measuring the size of a boundary between said light and dark classes in a second neighborhood;

means for determining if said boundary size is less than a first threshold, wherein said subject pixel is not a halftone pixel;

means for determining if said boundary size is equal to or greater than said first threshold, wherein said subject pixel is a halftone pixel, and wherein descreening techniques may optionally be applied to said subject pixel; and

means for applying a cross correlation technique to detect halftone pixels if said boundary size is not equal to or greater than said first threshold;

means for calculating a variational norm within a single component window;

means for calculating correlation factors for said subtext pixel; and

means for comparing said correlation factors with a second threshold, wherein said subject pixel is a halftone pixel if at least one of said correlation factors is less than said second threshold.