Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The impact of Canada/U.S. free trade on the B.C. food processing and beverage sector Lapointe, Bernard 1988

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1988_A6_7 K79.pdf [ 9.25MB ]
Metadata
JSON: 831-1.0097694.json
JSON-LD: 831-1.0097694-ld.json
RDF/XML (Pretty): 831-1.0097694-rdf.xml
RDF/JSON: 831-1.0097694-rdf.json
Turtle: 831-1.0097694-turtle.txt
N-Triples: 831-1.0097694-rdf-ntriples.txt
Original Record: 831-1.0097694-source.json
Full Text
831-1.0097694-fulltext.txt
Citation
831-1.0097694.ris

Full Text

R e p l i c a t i o n P a t t e r n s f o r Polygon F i l l A l g o r i t h m s by MICHAEL WALTER KREYKENBOHM B . S c , The U n i v e r s i t y of B r i t i s h Columbia, 1984 . A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept t h i s t h e s i s as conforming to the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA October 1988 @ Mi c h a e l Walter Kreykenbohm, 198 8 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Computer Science The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date October 10, 1988 DE-6(3/81) A b s t r a c t T h i s t h e s i s d e s c r i b e s and compares s e v e r a l methods f o r p r o d u c i n g b i l e v e l p a t t e r n s to simulate grey l e v e l v a l u e s f o r use i n polygon r e g i o n s as generated f o r computer g r a p h i c s . Random d i s t r i b u t i o n , o r dered d i t h e r , and e r r o r d i f f u s i o n methods are shown t o be v i s u a l l y i n f e r i o r f o r many grey l e v e l s t o the proposed maxmin a l g o r i t h m f o r p r o d u c i n g p a t t e r n s f o r polygon area f i l l i n g p rocedures. Through even s p a t i a l arrangement of the p i x e l s and t a k i n g i n t o c o n s i d e r a t i o n the edges of the p a t t e r n , the number of a r t i f a c t s i s decreased and the accuracy i n small subregions of the p a t t e r n i s improved, e s p e c i a l l y at low grey l e v e l s where most p a t t e r n generators degrade. At these lower l e v e l s , the maxmin a l g o r i t h m can produce p l e a s i n g p a t t e r n s i f g i v e n s u f f i c i e n t f l e x i b i l i t y through e n l a r g e d g r i d s i z e s . At h i g h e r grey l e v e l s , the p r o x i m i t y of p i x e l s does not leave s u f f i c i e n t room t o e l i m i n a t e a l l a r t i f a c t s , but by v a r y i n g the c r i t e r i a o f the a l g o r i t h m , the p a t t e r n s s t i l l appear more p l e a s i n g than other methods. i i Table of Contents A b s t r a c t i i Table of Contents i i i L i s t of F i g u r e s i v 1. I n t r o d u c t i o n 1 2. Randomly Generated P a t t e r n s 3 3. Ordered D i t h e r Rendering Technique f o r P a t t e r n Generation 5 4. E r r o r C o r r e c t i n g Techniques f o r P a t t e r n Generation 8 5. M u l t i l e v e l Method t o Minimize L o c a l E r r o r s 16 6. D i s t r i b u t i n g the P i x e l s by Maximizing the Minimum D i s t a n c e 21 7. P a t t e r n S i z e 33 8. C o n c l u s i o n 38 9. References 40 10. Appendix A 41 i i i L i s t of F i g u r e s 1. Randomly generated p a t t e r n s f o r 8, 25 and 41% grey l e v e l s 3 2. R e p l i c a t i o n o f randomly generated p a t t e r n s 3 3. Ordered d i t h e r p a t t e r n s f o r 8, 25 and 41% grey l e v e l s 6 4. R e p l i c a t i o n o f ordered d i t h e r p a t t e r n s 6 5. R e p l i c a t i o n o f ordered d i t h e r p a t t e r n s i n increments o f 1/64 and 1/256 7 6. E r r o r d i f f u s i o n image across the complete set of grey l e v e l s i n increments of 1/64 and 1/256 10 7. E r r o r d i f f u s i o n image across i n d i v i d u a l grey l e v e l s i n increments o f 1/64 and 1/256 12 8. E r r o r d i f f u s i o n p a t t e r n s f o r 8, 25 and 41% grey l e v e l s 13 9. R e p l i c a t i o n o f e r r o r d i f f u s i o n p a t t e r n s 13 10. A l g o r i t h m f o r m u l t i l e v e l p i x e l grouping w i t h f i x e d p o s i t i o n d i s t r i b u t i o n (ordered d i t h e r ) 15-19 11. A l g o r i t h m f o r maxmin d i s t r i b u t i o n 23-26 12. Maxmin p a t t e r n s f o r 8, 12.5, 19, 25, 33 and 41% grey l e v e l s 27 13. R e p l i c a t i o n o f maxmin p a t t e r n s 28 14. Complete maxmin p a t t e r n s with c o r r e c t i o n s near 50% i n increments o f 1/256 and 1/64 29 15. Improved 41% grey l e v e l f o r the maxmin a l g o r i t h m 31 16. Number of c a l c u l a t i o n s f o r s p e c i f i c grey l e v e l s u s i n g the maxmin a l g o r i t h m 32 17. The h a l f t o n e p a t t e r n s f o r grey l e v e l s 0/16 to 15/16 b e f o r e and a f t e r b l e n d i n g w i t h a' maxmin p a t t e r n of 0.5 36 18. H a l f t o n e p a t t e r n s blended u s i n g maxmin p a t t e r n s t o i n c r e a s e the number of grey l e v e l s from 16 to 256 37 xv 1. I n t r o d u c t i o n With the i n c r e a s i n g a v a i l a b i l i t y of b i l e v e l p r i n t e r s , the d e s i r e t o improve the r e p r e s e n t a t i o n of grey l e v e l images u s i n g b l a c k and white dots a r i s e s n a t u r a l l y . Although many b i l e v e l r e n d e r i n g t e c h n i q u e s produce p l e a s i n g b i l e v e l images f o r p i c t u r e data, they do not p r o v i d e the best r e s u l t s f o r computer-generated images c o n t a i n i n g r e g i o n s of constant grey l e v e l s . T h i s t h e s i s i s concerned w i t h computer generated p o l y g o n a l images wi t h grey s c a l e r e g i o n s . The method proposed generates a p a t t e r n of b l a c k and white p i x e l s f o r a g i v e n grey l e v e l . T h i s p a t t e r n i s more p l e a s i n g then other methods d i s c u s s e d s i n c e the p i x e l s are most evenly d i s t r i b u t e d across the s u r f a c e , thereby e l i m i n a t i n g some . a r t i f a c t s (groups of p i x e l s making up h o r i z o n t a l , v e r t i c a l and d i a g o n a l l i n e s ) and making the p a t t e r n more a c c u r a t e ( c l o s e r t o the d e s i r e d grey l e v e l at a l l small subregions of the surface) . Since the a l g o r i t h m i s very computational i n t e n s i v e , t h i s paper uses the method t o c r e a t e s m a l l p a t t e r n s (8 x 8 or 16 x 16) which can be r e p l i c a t e d t o f i l l the s u r f a c e . In t h i s way, the grey p a t t e r n s are generated f i r s t and the a c t u a l output procedure f o r a l l s u r f a c e s needs to s t o r e o n l y the s i n g l e p a t t e r n s f o r each grey l e v e l . and use an i n e x p e n s i v e a l g o r i t h m to generate the output. One disadvantage t h a t becomes obvious i s the g e n e r a t i o n of s m a l l areas (e.g. l i n e s ) . I f the s u r f a c e i s s m a l l , then l i k e most a l g o r i t h m s , i t s t r u e grey l e v e l can not be generated s i n c e the o b j e c t does not 1 c o n t a i n enough p i x e l s from the p a t t e r n . T h i s i s why the p r o j e c t i s r e s t r i c t e d t o polygon images and does not d e a l w i t h images of connected tones as used i n image p r o c e s s i n g . F i r s t , t h r e e methods of g e n e r a t i n g a b i l e v e l f i l l p a t t e r n f o r constant grey l e v e l s namely, random d i s t r i b u t i o n , ordered d i t h e r , and e r r o r d i f f u s i o n , are examined f o r t h e i r accuracy at low grey l e v e l r e g i o n s and f o r the number of a r t i f a c t s t h a t they produce. Then, a new method to maximize the s p a t i a l d i s t a n c e s between p i x e l s i s proposed. The r e s u l t s of the new method are shown t o be v i s u a l l y b e t t e r than the t h r e e methods of p i x e l d i s t r i b u t i o n f o r many l e v e l s of grey, s i n c e the p i x e l s cover the area more evenly and fewer h o r i z o n t a l and v e r t i c a l s u b s t r u c t u r e s are present, e s p e c i a l l y at low grey l e v e l s . The image i s p e r c e i v e d as a more even grey w i t h l e s s t e x t u r e and fewer a r t i f a c t s , even on p r i n t e r s t e n d i n g to emphasize such f e a t u r e s . 2 2. Randomly Generated P a t t e r n s To b e s t approximate a grey l e v e l image, the percentage of the p a t t e r n covered by p i x e l s must match as c l o s e l y as p o s s i b l e t o the grey l e v e l d e s i r e d . The p i x e l s can be p l a c e d i n any order, but the s i m p l e s t method i s t o use a random number genera t o r t o s p e c i f y the p o s i t i o n i n the p a t t e r n m a t r i x . By i n s u r i n g t h a t a p o i n t i s not set twice, the c o r r e c t number of p i x e l s w i l l appear i n the f i n a l p a t t e r n . - 1 - - - - - -1 - - - 1 - - -- - 1 - 1 - - -1 - - 1 - 1 - -1 - - - 1 - - -- - - 1 1 1 - -1 - 1 1 - - - 1 - 1 - 1 - - 1 -- - 1 - - - - 1 - 1 1 - - 1 - -1 - 1 1 1 - - -- - 1 - 1 1 - 1 1 - 1 - 1 - - 1 1 - - - - - - 1 - - - - 1 1 1 1 !% grey l e v e l 25% grey l e v e l 41% grey l e v e l F i g u r e 1. Randomly generated p a t t e r n s f o r 8, 25 and 41% grey l e v e l s '*V+V*Y •ft+VAV*;'* If, « 45 to* 'leie'ie'ie'i ft'*!*' V*sV*S> *,tr,>n "tti'ikik •*v*v*v !% grey l e v e l 25% grey l e v e l 41% grey l e v e l F i g u r e 2. R e p l i c a t i o n o f randomly generated p a t t e r n s As can be seen i n F i g u r e s 1 and 2 where a 1 r e p r e s e n t s a set output p i x e l , u s i n g a random number generator w i l l seldom g i v e a p a t t e r n t h a t i s e q u a l l y d i s t r i b u t e d . Most p a t t e r n s w i l l c o n t a i n c l u s t e r s o f b l a c k or white c a u s i n g the image t o look 'coarse', w i t h d i s t i n c t p a t t e r n s which are d i f f i c u l t t o b l e n d v i s u a l l y . In a d d i t i o n , s m a l l e r subregions o f the p a t t e r n q u i c k l y demonstrate 3 h i g h v a r i a n c e s i n the observed grey e s p e c i a l l y at low l e v e l s of grey ( l e s s than 12%). 4 3. Ordered D i t h e r Rendering Technique f o r P a t t e r n Generation The most commonly used p a t t e r n g e n e r a t i o n method p r o v i d i n g f a i r p i x e l p o s i t i o n i n g i s the ordered d i t h e r a l g o r i t h m i ^ 2 , 3 # I n ordered d i t h e r , the d e c i s i o n t o set a p i x e l i s based on the c u r r e n t p i x e l ' s grey l e v e l i , 0 <= i <= 1, and a d i t h e r matrix n x n. In the d i t h e r matrix, each i n t e g e r from 0 t o n 2 - l i s p r e s e n t e x a c t l y once. A p i x e l i s set i f i t s p o s i t i o n corresponds t o a d i t h e r matrix e n t r y t h a t i s l e s s than n 2 x i . Thus t o generate a p a t t e r n f o r a f i x e d grey l e v e l , a l l e n t r i e s l e s s than n 2 x i are s e t . Consider the f o l l o w i n g matrix D o : 1 o 32 8 40 2 34 10 42 | I 48 16 56 24 50 18 58 26| | 12 44 4 36 14 46 6 38 | D 8= 160 28 52 20 62 30 54 22 | 1 3 35 11 43 1 33 9 41 1 151 19 59 27 49 17 57 25 | 1 15 47 7 39 13 45 5 37 | 163 31 55 23 61 29 53 21 | D3 i s d e r i v e d by • t a k i n g the 2 x 2 matrix D2, D 2 = 10 21 13 1 1 , r e p l i c a t i n g each c e l l i n t o a box of 2 by 2 c e l l s , and 2 2 x D2 t o y i e l d D 4, and then r e p e a t i n g the process by 2-3 x D2 t o a f u r t h e r e n l a r g e d box. As demonstrated i n F i g u r e s 3, 4 and 5, the c o n s i s t e n t o r d e r i n g f o r a l l c e l l s causes ordered d i t h e r t o have d i a g o n a l , v e r t i c a l and h o r i z o n t a l s u b s t r u c t u r e s e x h i b i t e d as c h a r a c t e r i s t i c t e x t u r e which may be emphasized by an output d e v i c e w i t h non-equally spaced, o v e r l a p p i n g , or u n d e r f i l l e d p i x e l s , e s p e c i a l l y at low l e v e l g r e y s. 5 ] _ _ ] _ _ ] _ _ ! _ ] _ _ ! _ ] _ _ ] _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ! _ ] _ _ ] _ _ _ _ _ ! _ _ _ _ _ ] _ _ ! _ ] _ _ ] _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ! _ _ _ ! _ _ _ ]__!_]__]__ ! _ ] _ _ ! _ ] _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ! _ _ _ ! _ ] _ _ _ _ _ _ _ _ _ ! _ ! _ ! _ ! _ ! _ ! _ ] _ _ ! _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ! _ _ _ ! 8% grey l e v e l 25% grey l e v e l 41% grey l e v e l F i g u r e 3. Ordered d i t h e r p a t t e r n s f o r 8, 25 and 41% grey l e v e l s 8% grey l e v e l 25% grey l e v e l 41% grey l e v e l F i g u r e 4. R e p l i c a t i o n of ordered d i t h e r p a t t e r n s 6 a) The f i r s t 16 p a t t e r n s f o r ordered d i t h e r w i t h a 16 by 16 g r i d p a t t e r n (increments of 1/256) b) A l l 64 p a t t e r n s f o r ordered d i t h e r with an 8 by 8 g r i d p a t t e r n (increments of 1/64) F i g u r e 5. R e p l i c a t i o n of ordered d i t h e r p a t t e r n s i n increments of 1/256 and 1/64 4. E r r o r C o r r e c t i n g Techniques f o r P a t t e r n Generation E r r o r c o r r e c t i n g techniques attempt to s e l e c t the p i x e l p o s i t i o n s such t h a t the e r r o r i n an image of v a r y i n g grey l e v e l s i s minimized l o c a l l y (small regions) and g l o b a l l y (throughout the image). The e r r o r b e i n g minimized i s the d i f f e r e n c e between the output p i x e l v a l u e (0 or 1) and an input r a t i o n a l number (between 0 and 1). By b e g i n n i n g with a matrix c o n t a i n i n g the d e s i r e d grey l e v e l s i , 0<=i<=l, at each p i x e l , and u s i n g a r a s t e r scan a l g o r i t h m ( s t a r t i n g i n the l e f t upper corner and p r o c e s s e d row by row), the e r r o r at a g i v e n p o i n t can be computed and d i s t r i b u t e d t o unprocessed neighbors. I f an output v a l u e i s l e s s than the a s s o c i a t e d i n p u t v a l u e , a p o s i t i v e d i f f e r e n c e i s added to the s u r r o u n d i n g p i x e l s t o make them seem of a h i g h e r grey l e v e l and more l i k e l y t o be s e t . In t h i s way, the e r r o r s w i l l be reduced over a l a r g e r e g i o n and the generated output image w i l l approximate the input grey l e v e l image. One e r r o r c o r r e c t i n g method developed by F l o y d and S t e i n b e r g 4/5,6,7 ^ s known as e r r o r d i f f u s i o n . Each input i s compared t o a f i x e d t h r e s h o l d of 0.5 and a s s i g n e d an output value of 0 or 1 a c c o r d i n g l y . The r e s u l t i n g e r r o r i s d i s t r i b u t e d by the f o l l o w i n g m a t r i x to p o i n t s not yet processed: xxx 7/16 3/16 5/16 1/16 (xxx i s the c u r r e n t p o i n t ) The updated v a l u e s at subsequent p o i n t s are used to decide t h e i r output v a l u e s w i t h t h e i r e r r o r s passed forward. 8 Although e r r o r d i f f u s i o n approximates a grey l e v e l very c l o s e l y f o r a continuous tone image as demonstrated i n F i g u r e 6, i t has some disadvantages when u s i n g i t t o generate p a t t e r n s f o r constant grey l e v e l s . Since each p o i n t passes 100% (7/16 + 3/16 + 5/16 + 1/16) of i t s e r r o r t o i t s nearest neighbors, which a l s o pass on 100% of t h e i r e r r o r , the e f f e c t o f one p i x e l can propagate a r b i t r a r i l y f a r i n the matr i x . T h i s i s i l l u s t r a t e d i n p a r t by the f o l l o w i n g matrix D: .00 .00 .00 .00 xxx .44 .19 .08 .04 .02 .01 .00 .00 .00 .00 .19 .48 .44 .30 .17 .10 .05 .03 .01 .00 .00 .04 .16 .32 .36 .31 .23 .15 .09 .05 .03 .00 .01 .04 .13 .23 .29 .29 .25 .19 . 13 .09 .05 .00 .01 .04 .11 .18 .24 .26 .24 .20 .16 .11 .08 . 00 .01 .04 .09 .15 .20 .23 .23 .21 .18 . 14 . 10 .00 .01 .04 .07 .12 .17 .20 .21 .21 .18 .15 .12 .00 .01 .03 .06 .10 . 14 .18 .20 .20 .19 .16 .14 .00 .01 .03 .05 .08 .12 .15 .18 .19 .18 .17 .15 .00 . 01 .02 .04 .07 .10 .13 .16 .17 .18 .17 .15 .00 .01 . 02 .04 .06 .09 .12 . 14 .16 . 17 .16 .15 . 00 .01 .02 .03 .05 .08 . 10 .13 .14 .16 .16 . 15 .00 .01 .01 .03 .04 .07 .09 .11 .13 .14 .15 .15 ... D (50, 32) = .07 (xxx i s the c u r r e n t p o i n t : D(0,4)) Assuming t h a t a l l p o i n t s a f t e r the c u r r e n t p o i n t have an output v a l u e o f 0, t h i s matrix shows the e r r o r d i s t r i b u t e d t o the subsequent p o i n t s (within two d i g i t s ) . I f any p o i n t i s changed t o have an output v a l u e o f 1, the r e s u l t i n g e r r o r d i s t r i b u t i o n would have the matrix s u b t r a c t e d from a l l subsequent p o i n t s . As above, any p o i n t has an e f f e c t o f 7% t o the p o i n t 50 rows and 32 columns l a t e r , and a s m a l l e r e f f e c t on almost a l l subsequent p o i n t s . Should the e x t r a e r r o r cause a output o f 1 i n s t e a d of 0, the i n i t i a l p o i n t c o u l d a f f e c t a p o i n t l o c a t e d 100 rows, 64 columns from the o r i g i n a l by -7%. 9 a) E r r o r d i f f u s i o n a cross an image of grey l e v e l boxes of 1/256 t o 16/256 (increments of 1/256) b) E r r o r d i f f u s i o n a cross an image of grey l e v e l boxes of 1/64 to 64/64 (increments of 1/64) F i g u r e 6. E r r o r d i f f u s i o n a l g o r i t h m a c r o s s the complete set of grey l e v e l s i n increments of 1/256 and 1/64 10 Due t o t h i s propagation, a p a r t i c u l a r p i x e l may be i n f l u e n c e d by a l l p r e v i o u s p i x e l s . For a constant grey l e v e l , the output o f a p i x e l at a p o i n t (x,y) f a r removed i s decided upon by the r e s u l t of the f o l l o w i n g e q u a t i o n (since the pr o p a g a t i o n i s both l e f t and r i g h t of the matrix, the y component i s a l lowed t o be n e g a t i v e ) : E(x,y) = d +i -D(0,5)P(x,y-l) -D (0, 6) P (x, y-2) -D (0, y) P (x, 0) - D ( l , 3 ) P ( x - l , y + l ) - D ( l , 4 ) P ( x - l , y ) -D (1, y) P (x-1, 0) -D(x,4-y)P(0,2y) -D(x,3-y)P(0,2y-l)-...-D(x,y+3)P(0,0) i f E(x,y) < 0.5 then P(x,y) = 0 => 0.5 then P (x,y) = 1 where: d = sum of a l l p o i n t s i n matrix D() i = the f i x e d grey l e v e l x = row number of d i s t a n t p o i n t y = column number of d i s t a n t p o i n t D() are the matrix elements as shown above E() are the input v a l u e s f o r the e r r o r d i f f u s i o n method P() i s the p i x e l output image (0s and Is) The d i s t r i b u t i o n of e r r o r s t o an i n f i n i t e number of subsequent p o i n t s r a r e l y causes the e r r o r d i s t r i b u t i o n a l g o r i t h m to s e t t l e on a f i x e d p a t t e r n , even when the number of c o e f f i c i e n t s c o n t r i b u t i n g i n D i s g r e a t l y reduced by damped e r r o r d i s t r i b u t i o n ^. A s l i g h t change i n any of the p r e v i o u s p i x e l s w i l l r e s u l t i n a d i f f e r e n t p a t t e r n . In F i g u r e 7, the surrounding e r r o r e f f e c t s have been e l i m i n a t e d t o demonstrate the changing e f f e c t w i t h i n a grey l e v e l . These e f f e c t s are t o t a l l y due to the i n f l u e n c e o f the surrounding grey l e v e l c e l l s and t h e i r e r r o r p r o p a g a t i o n . 11 a) E r r o r d i f f u s i o n across i n d i v i d u a l images of constant grey l e v e l s from 1/256 to 16/256 (increments of 1/256) b) E r r o r d i f f u s i o n across i n d i v i d u a l images of constant grey l e v e l s from 1/64 to 64/64 (increments of 1/64) F i g u r e 7. E r r o r d i f f u s i o n a l g o r i t h m a c r o s s i n d i v i d u a l grey l e v e l s i n increments of 1/256 and 1/64 12 A r b i t r a r i l y p i c k i n g a subpattern from a e r r o r d i f f u s i o n of a l a r g e area o f constant grey l e v e l i s much si m p l e r then s o l v i n g f o r a l l P(x,y) i n the above equation but can p r o v i d e a s i m i l a r r e s u l t . To a v o i d e f f e c t s from n o n c o n t r i b u t i n g p o i n t s o u t s i d e the borders, the p a t t e r n must be chosen at a s i g n i f i c a n t d i s t a n c e from a l l edges. Some grey l e v e l s r e q u i r e v i s u a l l y s e l e c t i n g a s u i t a b l e p a t t e r n t o a v o i d banding which may occur from the top corn e r s due t o changing e x t e r i o r c o n d i t i o n s . To a v o i d the problems a s s o c i a t e d w i t h edges, the f o l l o w i n g p a t t e r n s were s e l e c t e d from a f i e l d 640 x 148, at (300,140). _ ! _ ! _ ] _ _ ] _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ] _ _ _ ] _ _ ! _ _ _ _ _ _ _ _ _ - - 1 - 1 - 1 - 1 - 1 - 1 - 1 - -_ _ _ 1 - - _ _ _ _ _ _ _ _ ! _ ] _ _ _ ] _ _ ! __!_____ _!_!_!_! __!_!__! _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ! _ _ ! _ ! _ _ _ _ _ _ _ _ _ _ ! _ ! _ ! _ ] _ _ _ ! _ ! _ _ ! _ _ _ ! _ _ _ ! _ _ _ _ _ _ _ _ ] _ _ ! _ _ ] _ _ ] _ 8% grey l e v e l 25% grey l e v e l 41% grey l e v e l F i g u r e 8. E r r o r d i f f u s i o n p a t t e r n s f o r 8, 25 and 41% grey l e v e l s 8% grey l e v e l 25% grey l e v e l 41% g r e y . l e v e l F i g u r e 9. R e p l i c a t i o n o f e r r o r d i f f u s i o n p a t t e r n s 13 To get the p a t t e r n s e x h i b i t e d i n F i g u r e s 8 and 9 w i t h the c o r r e c t number of p i x e l s set f o r the d e s i r e d grey l e v e l , the window of the p a t t e r n needed to be a d j u s t e d s e v e r a l times. The 8% grey l e v e l e s p e c i a l l y showed a v a r i a n c e of up to two p i x e l s (3%) . Other e f f e c t s more c l e a r l y observed on a l a r g e p a t t e r n s i z e (64 x 64) demonstrate the d i f f i c u l t i e s o f u s i n g an e r r o r d i f f u s i o n method on a constant grey l e v e l image. The e r r o r has t o b u i l d up b e f o r e i t can c o r r e c t l y approximate the d e s i r e d grey l e v e l . So at many areas i n the output p a t t e r n , waves ( p a r a l l e l l i n e g r o u p i n g s ) , lumps ( c l o s e l y grouped p i x e l s ) and h o l e s ( s p a r s e l y grouped p i x e l s ) appear, adding ' n o i s e ' to the image and r e d u c i n g the c o n t i n u i t y p e r c e i v e d . As i n the 25% grey l e v e l , r e g u l a r p a t t e r n s do occur at c e r t a i n r a t i o n a l numbers, eg., 1/2, 1/3, 2/3,' 1/4, and 3/4. The e r r o r c a n c e l l a t i o n s o c c u r r i n g i n the d i s t r i b u t i o n c o n t r i b u t e so s t r o n g l y t o t h e i r formation t h a t they cause the s u r r o u n d i n g grey l e v e l s ( + /- 2% t o 5%) to show s i m i l a r s t r i a t i o n s . Fawcett and Schrack 7 used a p a t t e r n i n h i b i t o r t o c o r r e c t f o r t h i s b ehavior of the e r r o r d i f f u s i o n method. In t h i s p r o j e c t , i t has been found t h a t removing such p a t t e r n s cause a ' c o a r s e r ' , l e s s even p a t t e r n t o appear. 14 E r r o r d i f f u s i o n , s i n c e i t i s designed t o be a p p l i e d across a complete image, has s e v e r a l disadvantages f o r g e n e r a t i n g p a t t e r n s . Since the e r r o r i s passed forward, i t i s l i k e l y t h a t the image w i l l not r e p l i c a t e n i c e l y without minor adjustment. In a d d i t i o n , e r r o r d i f f u s i o n guarantees t h a t on average the image w i l l have the c o r r e c t grey l e v e l , but at a p a r t i c u l a r subregion the grey may be s e v e r a l p i x e l s l e s s then r e q u i r e d . T h i s occurs more s t r o n g l y i n lower grey l e v e l s i n the form o f wave l i n e s . 15 5. M u l t i l e v e l Method to Minimize L o c a l E r r o r s To c r e a t e a b i t p a t t e r n t h a t c l o s e l y resembles the d e s i r e d grey l e v e l i n very s m a l l r e g i o n s , a m u l t i l e v e l method has been developed t o d i s t r i b u t e p i x e l s i n t o v a r i o u s subboxes. To i l l u s t r a t e and e x p l a i n the a l g o r i t h m , f o l l o w i n g i s an example of the p r o c e s s u s i n g a grey l e v e l of 3 3 % . To r e p r e s e n t a c c u r a t e l y the d e s i r e d grey l e v e l , every s u b - s e c t i o n of the p a t t e r n must be no more than one p i x e l from the d e s i r e d l e v e l . Each group of 2 x 2 p i x e l s must c o n t a i n e i t h e r one or two p i x e l s , s i n c e each f o u r p i x e l s should have, on the average, 1.32 p i x e l s set (33% x 4 = 1.32) . In a d d i t i o n , each group of 4 x 4 p i x e l s must, c o n t a i n f i v e or s i x p i x e l s (33% x 16 = 5.28) . In the m u l t i l e v e l method, each 4 x 4 box i s s u b d i v i d e d i n t o f o u r boxes of 2 x 2. To be c o n s i s t e n t , t h r e e of the 2 x 2 boxes must c o n t a i n one p i x e l each and the f o u r t h box must c o n t a i n two p i x e l s , f o r a t o t a l of f i v e as r e q u i r e d i n the 4 x 4 box. L e v e l 3: the o r i g i n a l 8 x 8 grey p a t t e r n w i t h each e n t r y r e p r e s e n t i n g one p i x e l I . 3 3 . 3 3 . 3 3 33 . 3 3 33 . 3 3 . 3 3 I . 3 3 . 3 3 . 3 3 33 . 3 3 33 . 3 3 . 3 3 1 . 3 3 . 3 3 . 3 3 33 . 3 3 33 . 3 3 . 3 3 I . 3 3 . 3 3 . 3 3 33 . 3 3 # 33 . 3 3 . 3 3 1 . 3 3 . 3 3 . 3 3 33 . 3 3 33 . 3 3 . 3 3 I . 3 3 . 3 3 . 3 3 # 33 . 3 3 33 . 3 3 . 3 3 I . 3 3 . 3 3 . 3 3 # 33 . 3 3 33 . 3 3 . 3 3 I . 3 3 . 3 3 . 3 3 • 33 . 3 3 • 33 . 3 3 . 3 3 L e v e l 2 : Grouped i n t o 2 x 2 c e l l s : 1 1 . 32 1. 32 1. 32 1. 32 | 1 1 . 32 1. 32 1. 32 1. 32 | 11. 32 1. 32 1. 32 1. 32 | 11. 32 1. 32 1. 32 1. 32 | (each m a t r i x element r e p r e s e n t s one c e l l w i t h the sum of f o u r p i x e l s from.the p r e v i o u s l e v e l ) 16 At t h i s p o i n t each box must have at l e a s t one p i x e l each. On the 4 x 4 l e v e l and l a t e r l e v e l s , the m u l t i l e v e l method only c o n s i d e r s the f r a c t i o n a l remainder to decide i f more p i x e l s are needed t o approximate the grey l e v e l b e t t e r . L e v e l 1: Grouped f r a c t i o n from 2 x 2 i n t o 4 x 4 boxes: (.32 x 4) 11.28 1.281 11.28 1.281 (one e x t r a p i x e l i s t o be p l a c e d i n t o each of f o u r 2 x 2 boxes) The p r o c e s s i s r epeated t o l e v e l 0 : 1 x 1 box: (.28 x 4) I 1.12 | (one e x t r a p i x e l i s to be p l a c e d i n t o one of the 4 x 4 boxes) To improve the accuracy of the p a t t e r n , the number of p i x e l s s h o u l d be incremented by one at l e v e l 0 i f the f r a c t i o n i s more than 0.5. The p i x e l s can be d i s t r i b u t e d by p l a c i n g at most one p i x e l i n each box of the p r e c e d i n g l e v e l . For a simple d i t h e r type p a t t e r n , the p o i n t s would be a s s i g n e d i n the f o l l o w i n g o r d e r : II 4| 13 2| T h i s r e s u l t s i n l e v e l 0 p a s s i n g one p i x e l to the box i n the upper l e f t of l e v e l 1: P i x e l s d i s t r i b u t e d at l e v e l 0 to l e v e l 1: HI P i x e l s d i s t r i b u t e d at l e v e l 1 t o l e v e l 2: |2 1| H II 17 P i x e l s d i s t r i b u t e d at l e v e l 2 t o l e v e l 3: |2 1 2 1| |1 2 1 1| |2 1 2 1| II 1 1 1| P i x e l s d i s t r i b u t e d at l e v e l 3 (the f i n a l p a t t e r n ) : 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 . 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 /* Program t o d i s t r i b u t e p i x e l s i n m u l t i l e v e l f a s h i o n Import Parameters: grey = d e s i r e d grey l e v e l (0.33 f o r above r e s u l t s ) l e v e l s = the number of l e v e l s t o group ( 2 * * l e v e l s i s g r i d width) maxwidth i s the h i g h e s t v a l u e on the l a r g e s t g r i d ( 2 * * l e v e l s - l ) (maxwidth i s the a c t u a l width - 1) Export Parameters: */ i n t e g e r p [ 0 . . l e v e l s , 0..maxwidth, 0..maxwidth]; /* f r a c r e t u r n s the f r a c t i o n a l p a r t of a r a t i o n a l number */ f l o a t f r a c ( x ) ; /* i n i t i a l i z e o r i g i n a l p i c t u r e grey l e v e l */ width = 1 « ( l e v e l s ) -1; f o r i:=0 t o width do f o r j:=0 t o width do p [ l e v e l s , i , j ] = grey; /* move the f r a c t i o n up t o l e v e l 0 */ f o r k:= l e v e l s - 1 downto 0 do { width := l « k -1; f o r i:= 0 t o width do f o r j:= 0 t o width do { t := f r a c ( p [ k + l , i * 2 , j*2]) ; t += f r a c ( p [ k + 1 , i * 2 + l , j * 2 ] ) ; t += f r a c ( p [ k + 1 , i * 2 , j * 2 + l ] ) ; t += f r a c ( p [ k + l , i * 2 + l , j * 2 + l ] ) ; 18 • p [ k , i , j ] := t ; } } /* a d j u s t l e v e l 0 so the image best approximates the d e s i r e d grey l e v e l */ i f ( f r a c ( p [ 0 , 0 , 0 ] ) > 0.5) then p[0,0,0] += 1; /* D i s t r i b u t e the p i x e l s u s i n g f i x e d p o s i t i o n d i s t r i b u t i o n */ f o r k:=0 t o l e v e l s - 1 do { width = l « k -1; f o r i:=0 t o width do f o r j:=0 t o width do f o r m:=l to p [ k , i , j ] do s w i t c h (m) { case 1: p[k+1,i*2,j*2] += 1; break; case 2: p[k+1,i*2+l,j*2+l] += 1; break; case 3: p[k+1,i*2,j*2+l] += 1; break; case 4: p[k+1,i*2+l,j*2] += 1; } } /* end of program */ F i g u r e 10. A l g o r i t h m f o r m u l t i l e v e l p i x e l grouping w i t h f i x e d p o s i t i o n d i s t r i b u t i o n (ordered d i t h e r ) The r e s u l t of the a l g o r i t h m i n F i g u r e 10, which i s the same as ordered d i t h e r due to the d i s t r i b u t i n g order, shows t h a t r e g a r d l e s s of the order i n which the p i x e l s are a s s i g n e d from lower l e v e l s t o h i g h e r l e v e l s the number of p i x e l s i n each box i s as c l o s e as p o s s i b l e to the d e s i r e d grey l e v e l . S e v e r a l d i s t r i b u t i o n methods have been t r i e d , w i t h a v a r i e t y of r e s u l t i n g p a t t e r n s . As shown above, a f i x e d p o s i t i o n type a l g o r i t h m r e s u l t s i n a d i t h e r p a t t e r n c o n t a i n i n g s t r o n g h o r i z o n t a l , v e r t i c a l and d i a g o n a l p a t t e r n s e a s i l y p e r c e i v e d as t e x t u r e s . Using a random d i s t r i b u t i o n removes these f e a t u r e s but 19 adds lumps (groups of b l a c k p i x e l s ) r e n d e r i n g the image v i s u a l l y ' c o a r s e r ' . Attempts t o i n c l u d e e r r o r d i f f u s i o n type c o n s t r a i n t s ( e i t h e r p a s s i n g e r r o r s box by box or c o n s t r a i n i n g the normal e r r o r d i f f u s i o n ) showed a c o m p e t i t i o n between the c o n s t r a i n t s and the e r r o r d i s t r i b u t i o n , r e s u l t i n g i n an o f f s e t d i t h e r arrangement at low percentages or an o f f s e t e r r o r d i f f u s i o n p a t t e r n c l o s e r to a 50% grey l e v e l . 20 6. D i s t r i b u t i n g the P i x e l s by Maximizing the Minimum D i s t a n c e To d i s t r i b u t e the p o i n t s e f f e c t i v e l y , the p i x e l s should be spaced t o f i l l the p a t t e r n plane i n some optimum f a s h i o n . L i k e r e p e l l i n g atoms i n a vacuum, the optimum p a t t e r n would have the p i x e l s as f a r apart as p o s s i b l e . I f two p i x e l s are to be d i s t r i b u t e d i n a 4 x 4 area, then the p i x e l s should be p l a c e d such t h a t movement of e i t h e r w i l l r e s u l t i n a s h o r t e r minimum d i s t a n c e between the two. By u s i n g wraparound d i s t a n c e s (the s h o r t e s t d i s t a n c e when each edge of the p a t t e r n i s j o i n e d t o the o p p o s i t e edge), the r e s u l t i n g placement becomes i d e a l f o r p a t t e r n r e p l i c a t i o n . Since each p i x e l must f a l l on an i n t e g e r p o s i t i o n i n the matrix, the minimum d i s t a n c e may occur between s e v e r a l p i x e l s . The a l g o r i t h m must maximize the s h o r t e s t d i s t a n c e and minimize the number of occurrences of t h a t d i s t a n c e . To enumerate a l l p o s s i b l e p a t t e r n s and c a l c u l a t e t h e i r d i s t a n c e s can be time consuming. But by u s i n g the above m u l t i l e v e l method to c o n t r o l the placement of p i x e l s and a l o c a l p e r t u r b a t i o n method t o move the p i x e l s i n each box, the c a l c u l a t i o n s are reduced c o n s i d e r a b l y from: 64 ! (64-n)! n! t o : 4 n i f n <= x (Since t h e r e i s l e s s than 1 p i x e l per box, each p i x e l can move to 4 pl a c e s ) g(n-x) 4(2x-n) i f n < = s 2 x ( F o r boxes wi t h 2 p i x e l s , t h e r e are 6 combinations per p a i r ) where n i s the number of p i x e l s , and x i s the g r i d area / 4 (e.g. x = 16, (64 / 4) f o r an 8 x 8 g r i d ) . 21 Any number of p i x e l s can be used, but the a l g o r i t h m becomes i n e f f e c t i v e when a p a t t e r n has many occurrences o f the same minimum d i s t a n c e or the number of p i x e l s i s l a r g e . To reduce the l a t t e r problem, grey l e v e l s i , i > 0 . 5 , s h o u l d be c r e a t e d by g e n e r a t i n g the p a t t e r n f o r 1-i and i n v e r t i n g the r e s u l t s . To improve the former problem, grey l e v e l s near 0 . 5 should be computed by removing p i x e l s from a checkerboard p a t t e r n as d e s c r i b e d l a t e r . U sing a d d i t i o n a l c o n s t r a i n i n g f a c t o r s , the a c t u a l number of c a l c u l a t i o n s can be reduced f u r t h e r . I n s i s t i n g t h a t one p i x e l always remains i n the upper l e f t hand box reduces the work by a f a c t o r o f f o u r . T h i s has no e f f e c t on the r e s u l t i n g p a t t e r n , s i n c e the placement of p i x e l s i s determined at each l e v e l and a l l l e v e l s have the p i x e l s w e l l spread a p a r t . An a d d i t i o n a l method f o r r e d u c i n g the average number of c a l c u l a t i o n s r e q u i r e s c r e a t i n g a 'good guess' p a t t e r n and u s i n g i t t o e l i m i n a t e as many output p a t t e r n s as p o s s i b l e . The guess i s c r e a t e d i n the same way the l o c a l p e r t u r b a t i o n s a re. The p i x e l s are i n s e r t e d i n t o a c h a i n (an ordered l i s t o f the p i x e l s t o be used i n the pat t e r n ) and moved i n a box as f o l l o w s (as i n the ordered d i t h e r ) : II 4| 13 2| The s m a l l e s t d i s t a n c e i n the f i r s t 'guess' becomes the f i r s t minimum. The l a s t p i x e l i n the c h a i n i s p e r t u r b e d s u c c e s s i v e l y t o a l l other p o s i t i o n s , p o s s i b l y r e s u l t i n g i n a b e t t e r minimum. 22 When the l a s t p i x e l can no lon g e r be moved, the cha i n i s shortened by one and the p r e v i o u s p i x e l i s moved. A l l f o l l o w i n g p i x e l s are r e s e t t o t h e i r i n i t i a l p o s i t i o n and c a l c u l a t i o n s of the s e p a r a t i n g d i s t a n c e s c o n t i n u e . By r e t a i n i n g the minimum d i s t a n c e at each p i x e l t o p r e v i o u s p i x e l s , the guess can be used t o decide when c a l c u l a t i n g and p e r t u r b i n g the c h a i n beyond the c u r r e n t p o i n t y i e l d s no improvement over the c u r r e n t minimum. /* Program t o d i s t r i b u t e p i x e l s by maximizing the minimum d i s t a n c e Import Parameters: grey = d e s i r e d grey l e v e l (0.33 f o r above r e s u l t s ) l e v e l s = the number of l e v e l s t o group (2** l e v e l s i s g r i d width) maxwidth i s the width of the l a r g e s t g r i d ( 2 * * l e v e l s -1) maxp i s the maximum number of p i x e l s allowed i n an image L o c a l Parameters: px,py d e f i n e the p i x e l s i n x,y c o o r d i n a t e s p i , p j d e f i n e the l e f t upper corner o f the box f o r each p i x e l , pos i s the l o c a t i o n w i t h i n the box, pnd i s the number of p i x e l s r e q u i r e d a f t e r the c u r r e n t one i n the same box, cmin i s the l i s t o f minimum d i s t a n c e s f o r one p o i n t t o a l l p r e c e d i n g p o i n t s cent i s the counts f o r the minimums tmax i s the maximum d i s t a n c e at each p o i n t */ i n t e g e r px[maxp],py[maxp],cent[maxp][compares]; i n t e g e r pi[maxp],pj[maxp],pos[maxp],pnd[maxp]; f l o a t cmin[maxp][compares],tmax[maxp]; /* To p r e s e r v e the best p a t t e r n so f a r (and the r e s u l t ) : hx,hy are the 'px','py' c o o r d i n a t e s o f a l l the p i x e l s hmin i s the 'cmin' f o r the best guess hent i s the 'cent' f o r the best guess htmax i s the 'tmax' f o r the best guess */ f l o a t hmin[compares],htmax; i n t e g e r hx[maxp],hy[maxp],hent[compares]; /* f r a c r e t u r n s the f r a c t i o n a l p a r t o f a r a t i o n a l number */ f l o a t f r a c ( x ) ; 23 /* */ / * P r o c e d u r e t o b u i l d m u l t i l e v e l d i s t r i b u t i o n l e v e l s a n d o u t p u t r e s u l t i n g p i x e l i m a g e * / p r o c e d u r e m a x m i n ( ) { / * i n i t i a l i z e o r i g i n a l p i c t u r e g r e y l e v e l u s i n g s h o r t e n e d f o r m o f M u l t i l e v e l g r o u p i n g * / w i d t h = 1 « l e v e l s - 1 ; f o r i : = 0 t o w i d t h d o f o r j : = 0 t o w i d t h d o p [ l e v e l s , i , j ] : = 0 ; / * F i n d t h e n u m b e r o f p i x e l s f o r d i s t r i b u t i o n a t e a c h l e v e l * / a c c u m : = g r e y ; f o r k : = l e v e l s - 1 d o w n t o 0 d o { w i d t h : = l « k - 1 ; a c c u m : = 4 . 0 * a c c u m ; t : = i n t ( a c c u m ) ; a c c u m = a c c u m - t ; f o r i : = 0 t o w i d t h d o f o r j : = 0 t o w i d t h d o { p [ k , i , j ] : = t ; } } / * a d j u s t l e v e l 0 s o t h e i m a g e b e s t a p p r o x i m a t e s t h e d e s i r e d g r e y l e v e l * / i f ( f r a c ( a c c u m ) > 0 . 5 ) t h e n P [ 0 , 0 , 0 ] += 1 ; / * D i s t r i b u t e t h e p i x e l s m a x i m i z i n g t h e m i n i m u m d i s t a n c e * / f o r k : = 0 t o l e v e l s { w i d t h : = l « k - 1 ; d i s t ( k , w i d t h , e n t ) ; f o r i : = 0 t o e n t d o p [ k + l , h x [ i ] , h y [ i ] ] += 1 ; } / * s a v e t h e p a t t e r n o n a n o u t p u t d e v i c e * / o u t p u t ( p ) ; } / * e n d M a i n p r o c e d u r e * / 2 4 /* */ / * d i s t r i b u t e p i x e l s t h r o u g h o u t a l e v e l * / p r o c e d u r e d i s t ( k , w i d t h , e n t ) { / * m a k e i n i t i a l g u e s s a n d b u i l d c h a i n f o r p e r t u r b a t i o n s * / e n t : = - 1 ; / * n u m b e r o f p o i n t s t o b e u s e d * / f o r i : = 0 t o w i d t h d o f o r j : = 0 t o w i d t h d o { n : = p [ k , i , j ] ; f o r m : = 0 t o n - 1 d o { e n t += 1 ; p i [ e n t ] : = i * 2 ; p j [ c n t ] : = j * 2 ; p o s [ e n t ] : = m ; p n d [ c n t ] : = n - l - m ; / * c a l c u l a t e t h e x , y p o s i t i o n i n t h e g r i d * / s e t x y p n t ( e n t ) ; / * c a l c u l a t e w r a p a r o u n d l e n g t h f r o m p r e v i o u s p o i n t s * / l e n p n t ( e n t , w i d t h * 2 ) ; } } m a x m i s ( e n t ) ' ; / * s e t t h e " g o o d " g u e s s * / m c n t : = e n t ; i f ( e n t < 2 ) t h e n r e t u r n ; / * w h i l e t h e r e a r e s o m e p e r t u r b a t i o n s p o s s i b l e * / w h i l e ( e n t > 0) d o { / * m o v e t h e c u r r e n t p o i n t * / p o s [ e n t ] += 1 ; / * a d j u s t t h e x , y c o o r d i n a t e s , i f p o s i t i o n i s v a l i d * / i f ( s e t x y p n t ( e n t ) ) t h e n { / * c o m p u t e t h e l e n g t h w i t h w r a p a r o u n d s i z e o f w i d t h * 2 * / l e n p n t ( e n t , w i d t h * 2 ) ; 2 5 /* r e s e t a l l f u r t h e r p o i n t s (while reasonable) */ w h i l e ( cmppnt(ent) and ent <= mcnt) do { ent += 1; /* make sure p o i n t s do not o v e r l a p */ i f ( p i [ c n t - l ] = p i [ e n t ] and p j [ c n t - l ] = p j [ e n t ] ) then pos[ent] := pos[ent-1] + 1; e l s e pos[ent] := 0; s e t x y p n t ( e n t ) ; l e n p n t ( e n t , w i d t h * 2 ) ; } /* I f a l l p i x e l s are p o s i t i o n e d , then t h i s i s the next guess */ i f (ent > mcnt)) then maxmis(ent); } e l s e ent -= 1; } } /* end D i s t r i b u t i n g procedure */ F i g u r e 11. A l g o r i t h m f o r maxmin d i s t r i b u t i o n The program shown i n F i g u r e 11 r e q u i r e s the procedures ( f u n c t i o n s ) maxmis, cmppnt, setxypnt, and l e n p n t . The procedure maxmis s t o r e s the c u r r e n t 'good guess' and a s s o c i a t e d maximums f o r cmppnt. Cmppnt compares the c u r r e n t chain's maximum with the 'good guess' maximum and r e t u r n s a v a l u e o f t r u e i f the c u r r e n t c h a i n i s b e t t e r than the c u r r e n t b e s t . Setxypnt c o n v e r t s the c u r r e n t p o i n t ' s p o s i t i o n i n t o x and y matrix c o o r d i n a t e s f o r lenpnt and r e t u r n s a va l u e o f t r u e i f the p o s i t i o n i n g i s v a l i d . F i n a l l y , lenpnt computes the minimum wraparound l e n g t h f o r the c u r r e n t c h a i n by computing the l e n g t h f o r the c u r r e n t p o i n t and u s i n g the p r e v i o u s p o i n t ' s l e n g t h s . 26 S e v e r a l v a r i a t i o n s have been t r i e d . By v a r y i n g cmppnt and maxmis, the comparison c r i t e r i a can be changed t o i n c l u d e more minimum d i s t a n c e s , a maximum d e v i a t i o n f a c t o r or a more g l o b a l comparison t o p r o v i d e a judgment on t o t a l l y e q u i v a l e n t p a t t e r n s . The a s s o c i a t i o n between the p o s i t i o n i n a box and the x,y co o r d i n a t e s can be a d j u s t e d i n setxypnt y i e l d i n g a d i f f e r e n t s e a r c h . Lenpnt can be v a r i e d t o p e n a l i z e p i x e l s l y i n g i n s p e c i f i c o r i e n t a t i o n s thereby o f f s e t t i n g the p i x e l p o s i t i o n i n g . Such v a r i a t i o n s o f adding more c o n s t r a i n t s or u s i n g a d i f f e r e n t i n s e r t i o n p a t t e r n d i d not s i g n i f i c a n t l y improve the p a t t e r n s , but v a r i e d the work r e q u i r e d t o f i n d p a t t e r n s . The p a t t e r n s i n F i g u r e 12, 13, and 14 r e s u l t e d from u s i n g two minima and counts f o r comparison and u s i n g the above i n s e r t i o n p a t t e r n (these are i n c l u d e d i n Appendix A as p a r t of the program s o u r c e ) . ] _ _ _ _ _ _ _ _ ] _ _ _ _ ! _ _ _ _ _ _ _ _ _ _ _ _ _ ! _ _ _ ! _ _ ! _ _ _ ! _ _ ___!____ !___!___ !_!_!_!_ _ _ _ _ _ _ ! _ _ _ ! _ _ _ ! _ _ ! _ ! _ _ _ ] _ _ _ _ _ _ _ _ _ ! _ _ _ ] _ _ _ _ ! _ ! _ ! _ ! _ _ ! _ _ _ _ _ _ _ _ ! _ _ _ ! _ _ ] _ _ _ _ ! _ _ _ _ _ _ ! _ _ _ ! _ _ _ ! _ _ _ ! _ ] _ _ ! _ ! _ _ _ _ _ _ _ _ _ _ _ ] _ _ _ _ ] _ _ _ _ _ ! _ ! _ ] _ 8% grey l e v e l 25% grey l e v e l 41% grey l e v e l ! _ _ _ _ _ _ _ ] _ _ _ _ ! _ _ _ _ ! _ _ ! _ _ ! _ _ _ _ _ ! _ _ _ _ ! _ _ _ ! _ _ _ ] _ _ _ _ ! _ _ _ ! _ _ _ _ _ ! _ _ _ ! _ _ _ ! _ _ ! _ ! _ _ _ _ _ _ _ _ _ ] _ _ _ _ _ _ _ _ _ _ ! _ _ ] _ _ _ ] _ _ _ _ _ ! _ _ _ _ _ ! _ _ _ ! _ _ _ _ ! _ _ ! _ _ ! _ _ _ _ _ _ ! _ _ _ ! _ _ _ _ ! _ _ ! _ _ ! _ _ _ _ _ _ ! _ _ _ ! _ _ _ ! _ _ _ ! _ _ ! _ _ _ _ _ ! _ _ _ _ _ _ _ _ _ _ _ _ ! _ _ ] _ _ _ ] _ _ 12.5 % grey l e v e l 19 % grey l e v e l 33 % grey l e v e l F i g u r e 12. Maxmin p a t t e r n s f o r 8, 12.5, 19, 25, 33 and 41% grey l e v e l s 27 grey l e v e l 25% grey l e v e l t*t*t*±.*t*± 1 < ! 1 ' < t t h t t h h lit! HTr sUpit i s t t » th t i iUtUh * * * * ' b h 41% grey l e v e l : iSmwiiS!;.';!1 , 5% grey l e v e l 19% grey l e v e l F i g u r e 13. R e p l i c a t i o n of 33% grey l e v e l maxmin p a t t e r n s 28 : a) The f i r s t 16 p a t t e r n s f o r the maxmin a l g o r i t h m w i t h a 16 by 16 g r i d p a t t e r n (increments of 1/256). wmmm b) A l l 64 p a t t e r n s f o r the maxmin a l g o r i t h m w i t h an 8 by 8 g r i d p a t t e r n (increments o f 1/64). F i g u r e 14. Complete maxmin p a t t e r n s with c o r r e c t i o n s near 50% i n increments of 1/256 and 1/64. 29 Other p a t t e r n s , s i m i l a r t o the 19% grey l e v e l , e x h i b i t small r e g i o n s which r e q u i r e manual adjustment. T h i s occurs when the d i s t a n c e s between p o i n t s can not be improved o v e r a l l but some p o i n t s can s t i l l be moved to improve the appearance of the p a t t e r n . For example, moving the p i x e l s at (3,5) and (7,3) to (4,5) and (8,3) r e s p e c t i v e l y i n the 19% grey l e v e l o f ' F i g u r e 12, w i l l not change the o v e r a l l d i s t a n c e s between p i x e l s , but w i l l v i s u a l l y remove the rows without set p i x e l s . Lower l e v e l p a t t e r n s can be improved by i n c r e a s i n g the g r i d s i z e t o a l l o w the maxmin a l g o r i t h m s u f f i c i e n t f l e x i b i l i t y i n p i x e l placement. As seen i n F i g u r e 14, the minimum va l u e o f 0.0156 (1/64) f o r the 8 x 8 p a t t e r n s et ( p a t t e r n 1 i n F i g u r e 14b) i s improved by producing the p a t t e r n f o r a 16 x 16 g r i d (4/256, p a t t e r n 4 i n F i g u r e 14a). P a t t e r n s near the 50% grey l e v e l demonstrate a d e s i r e t o remain i n a checkerboard p a t t e r n , r e d u c i n g the e f f e c t i v e n e s s of the maxmin s o l u t i o n s i n c e the minimum d i s t a n c e i s always 1.414 (the square r o o t o f two). The p a t t e r n t h a t i s bes t f o r these grey l e v e l s i s one wit h the ho l e s i n the checkerboard e q u a l l y spaced. T h i s i s s o l v e d at reduced computational work by s o l v i n g a p a t t e r n f o r (.50-i)*2, but wit h the lenpnt procedure a d j u s t e d t o o f f s e t a widthwise compression of the p a t t e r n . By manually uncompressing the p o i n t s and removing the set p o i n t s i n the checkerboard c o r r e s p o n d i n g t o the set p o i n t s i n the generated p a t t e r n , the improved p a t t e r n i n F i g u r e 15 i s generated. 30 - - 1 - 1 - 1 -- 1 - 1 - 1 - 1 1 - 1 - - - 1 -- - - 1 - 1 - 1 1 - 1 - 1 - - -- 1 - 1 - 1 - 1 1 - - - 1 - 1 -- 1 - 1 - - - 1 41% grey l e v e l 41% grey l e v e l F i g u r e 15. Improved 41% grey l e v e l f o r the maxmin a l g o r i t h m F i g u r e 16 demonstrates the work r e q u i r e d t o generate the p a t t e r n s . Each row shows the d e s i r e d grey l e v e l , the number of p i x e l s t h a t b e s t r e p r e s e n t the grey l e v e l , the number of comparisons at each l e v e l (the number of times cmppnt i s executed), the number of 'good guesses' d i s c o v e r e d at each l e v e l (the number of times maxmis i s executed), and the number of v a r i a t i o n s f o r p i x e l placement u s i n g the m u l t i l e v e l c o n s t r a i n t . V a r i a t i o n s i n the number of comparisons and minimums, although p r i m a r i l y due t o the number of p i x e l s t o be p l a c e d , are a l s o a f f e c t e d by the number of ' s i m i l a r ' minimums which e x i s t . As the c h a i n i s b u i l t and compared t o the 'good' guess, the ' s i m i l a r ' p a t t e r n c o n t i n u e s t o improve v i s u a l l y u n t i l the c h a i n i s n e a r l y complete. The p a t t e r n i s then found t o be m a r g i n a l l y b e t t e r or the same and t e s t i n g c ontinues w i t h the long chain, thereby p r e v e n t i n g the process from e l i m i n a t i n g many combinations. 31 L e v e l | P i x e l s | C o m p a r i s o n s | M i n i m u m s | C o m b i n a t i o n s 8 x 8 g r i d , 4% 1 3 | 5 , 1 9 , 1 9 | 2 , 2 , 2 | 6 4 8% 1 5 | 0 , 5 0 , 2 0 0 | 0 , 2 , 7 | 1 0 2 4 1 2 . 5 % 1 8 1 0 , 3 7 , 7 5 6 | 0 , 1 , 2 | 6 5 5 3 6 1 9 % 1 . 1 2 | 0 , 7 4 9 , 3 4 1 9 8 | 0 , 2 , 1 4 | 1 . 7 X 1 0 0 7 2 5 % 1 1 6 | 0 , o , 1 6 8 4 8 | o , 0 , 3 | 1 . 3 X 1 0 0 9 3 3 % 1 2 1 1 0 , 1 0 7 , 3 6 2 8 9 4 | 0 , 2 , 7 | 3 . 3 X 1 0 1 0 4 1 % 1 2 6 | 1 2 , 1 6 1 6 , 5 0 8 1 1 1 , 1 , 1 * 1 1 . 1 X 1 0 1 1 4 7 % 1 3 0 1 1 2 , 1 1 4 , 5 7 8 I 1 , 1 , 1 * | 1 . 2 X 1 0 1 2 1 6 x 1 6 g r i d , l O ^ 2 8% 1 2 0 | 0 , 3 9 , 1 6 3 8 6 2 , | o , 4 , 2 0 , | 1 . 1 X 1 1 2 7 0 4 2 6 3 | 6 5 | 1 0 1 * 1 2 . 5 % 1 3 2 | 0 , 0 , 1 7 1 , | 0 , 0 , 1 , 1 1 . 8 X 1 1 7 9 2 7 6 1 | 3 1 1 0 4 9 5 0 % 1 1 2 8 | 0 , 0 , 0 , 7 0 3 | o , 0 , 0 , 1 * | 6 . 3 X N o t e : 0 s a p p e a r i n g i n t h e C o m p a r i s o n s a n d M i n i m u m s c o l u m n s i n d i c a t e t h a t n o p i x e l s n e e d e d t o b e d i s t r i b u t e d . I s a p p e a r i n g i n t h e M i n i m u m s c o l u m n i n d i c a t e t h a t t h e o r i g i n a l ' g u e s s ' h a d t h e b e s t p i x e l a r r a n g e m e n t . * F o r p a t t e r n s n e a r 5 0 % t h e b e s t p a t t e r n i s t h e s a m e a s f o r 5 0 % w i t h a f e w e q u a l l y s p a c e d m i s s i n g p i x e l s . F i g u r e 1 6 . N u m b e r o f c a l c u l a t i o n s f o r s p e c i f i c g r e y l e v e l s u s i n g t h e m a x m i n a l g o r i t h m 3 2 7. Using the Maxmin P a t t e r n s The ordered d i t h e r , e r r o r d i f f u s i o n , and maxmin algorit h m s p r o v i d e f a i r r e s u l t s t o be used i n a p a t t e r n r e p l i c a t i o n program. As shown above, however, the maxmin a l g o r i t h m p r o v i d e s much improvement over the other two methods f o r an 8 x 8 and 16 x 16 g r i d . An i n c r e a s e i n the number of p i x e l s causes a geometric i n c r e a s e i n the computational e f f o r t r e q u i r e d whereas the ordered d i t h e r and e r r o r d i f f u s i o n methods r e q u i r e a l i n e a r i n c r e a s e i n work, r e n d e r i n g them more a c c e p t a b l e f o r p a t t e r n s r e q u i r i n g l a r g e r numbers o f p i x e l s (32 x 32 and l a r g e r r e s o l u t i o n s ) . I f the p i c t u r e i s t o be a computer-generated image wi t h p e r c e i v e d even s p a c i n g between grey l e v e l s , the above-mentioned problem becomes l e s s s i g n i f i c a n t . Most v i s u a l sensory d e v i c e s , i n c l u d i n g eyes and video cameras, p e r c e i v e i l l u m i n a t i o n on a l o g a r i t h m i c s c a l e 3,9_ To a d j u s t the output so as t o produce a l i n e a r l y p e r c e i v e d s c a l e , the p i x e l d e n s i t y must be compensated ^,9, Compensating f o r a p r i n t e r i s most e f f e c t i v e l y a c h ieved by b u i l d i n g a t a b l e t o map t r u e output v a l u e s to intended output v a l u e s and u s i n g i t to determine the grey l e v e l p a t t e r n r e q u i r e d . For example, i f the p r i n t e d p a t t e r n f o r 25% i s viewed by a v i d e o camera as 35%, 33 then the compensation t a b l e would map the 35% d e s i r e d value to a 25% r e q u i r e d output, i . e . , t o p r i n t a grey l e v e l to be perceived as 35%, a 25% p a t t e r n would need to be generated. This needs to be done f o r a l l output p a t t e r n s t o provide a complete mapping of a l l grey l e v e l s . By u s i n g a compensation t a b l e , the range of p e r c e i v e d grey l e v e l s can be increased, but only f o r l a r g e r g r i d s i z e s when the number of p i x e l s i s s m a l l . In the black r e g i o n , s t a r t i n g at approximately 50% d e n s i t y , the s a t u r a t i o n of black p i x e l s hides s u b s t a n t i a l increases i n the number of p i x e l s from p e r c e p t i o n . This i s e s p e c i a l l y n o t i c e a b l e on some p r i n t e r s which e x h i b i t o v e r l a p p i n g p i x e l s , they can have f u l l s a t u r a t i o n of the paper at the s m a l l e s t p i x e l s c a l e . Conversely, i n the near-white region near 0%, an i n t r o d u c t i o n of one more p i x e l i s r e a d i l y perceived as a d i f f e r e n t grey l e v e l ( e s p e c i a l l y w i t h the maxmin a l g o r i t h m ) . I n c r e a s i n g from white t o black, small increases i n the number of p i x e l s e v e n t u a l l y become unperceivable on a l a r g e r g r i d . This occurs at any r a t e depending on the s p e c i f i c p r i n t e r c h a r a c t e r i s t i c s and s c a l e of p i x e l s (some p r i n t e r s have a v a r i e t y of p i x e l s i z e s ) . To complete the compensation t a b l e , the variances i n s c a l e i n the white region must be expanded the most and the number of p a t t e r n s i n t h i s region must be enlarged. Since near-white contains few p i x e l s , the maxmin procedure can e f f i c i e n t l y f i n d a good p a t t e r n on a l a r g e r g r i d of 16 x 16. E r r o r d i f f u s i o n , on the other hand, b u i l d s wave type a r t i f a c t s at these lower grey 34 l e v e l s a n d t h u s i s n o t s u i t a b l e . A s t h e g r e y l e v e l i n c r e a s e s f r o m w h i t e , t h e e f f e c t o f o n e a d d i t i o n a l p i x e l i n a r e g i o n 1 6 x 1 6 b e c o m e s l e s s v i s i b l e a n d e v e n t u a l l y u n d i s c e r n i b l e n e a r t h e 1 6 % g r e y l e v e l . I f l o s s i n a c c u r a c y i s n o t a s i m p o r t a n t , t h e n a m a x m i n p a t t e r n o f 8 x 8 i s a c c e p t a b l e . T o i n c r e a s e t h e r e s o l u t i o n o f t h e p a t t e r n a b o v e t h i s p o i n t b e c o m e s i n e f f e c t i v e w i t h m a x m i n d u e t o t h e g e o m e t r i c i n c r e a s e i n c o s t . F o r a 1 6 x 1 6 g r i d , 1 2 . 5 % ( 3 2 p i x e l s ) i s n e a r t h e l i m i t o f a c c e p t a b l e p e r f o r m a n c e . S o m e n e w e r p r i n t e r s ( i . e . l a s e r p r i n t e r s ) a l r e a d y c o n t a i n s o m e m e t h o d o f e l e c t r o n i c h a l f t o n i n g b y a f o n t o f c l u s t e r e d p i x e l s f o r v a r i o u s g r e y l e v e l s w h i c h i s a l r e a d y c o m p e n s a t e d t o g i v e a l i n e a r a p p e a r a n c e . U n l i k e o t h e r c o n v e n t i o n a l p r i n t e r s ( i . e . d o t m a t r i x o r i n k j e t p r i n t e r s ) , a t t h e s m a l l e s t s c a l e t h e p i x e l s m u s t b e c l u s t e r e d t o g e t h e r t o a l l o w t h e p r i n t e r t o s u p p l y s u f f i c i e n t i n k t o b e t r a n s f e r r e d t o t h e o u t p u t m e d i u m . U s i n g a w e l l d i s t r i b u t e d p a t t e r n l i k e m a x m i n m a y o f t e n r e s u l t i n n o i n k b e i n g t r a n s f e r r e d t o t h e p r i n t e d p a g e . T h e a l r e a d y e x i s t i n g h a l f t o n e s a p p l y t o a s i n g l e p i x e l a n d o n l y p r o v i d e a l i m i t e d r a n g e o f g r e y l e v e l s . B y u s i n g t h e a l r e a d y e x i s t i n g h a l f t o n i n g , a n d h a v i n g m a x m i n s p r e a d t h e f r a c t i o n a l e r r o r t o r a i s e s o m e o f t h e v a l u e s i n t h e o u t p u t , a m o r e a c c u r a t e a n d e v e n p o l y g o n r e g i o n c a n b e g e n e r a t e d . T h i s i s d o n e b y c o m p u t i n g t h e f r a c t i o n b e t w e e n t h e v a l u e o f t h e g r e y l e v e l ( i . e . g l = . 1 6 7 ) t h a t c a n b e p r o d u c e d b e l o w t h e d e s i r e d g r e y l e v e l a n d t h e g r e y l e v e l ( i . e . g h = . 2 2 1 ) a b o v e t h e d e s i r e d g r e y l e v e l a n d c o m p u t i n g t h e r a t i o o f t h e d i s t a n c e s b e t w e e n t h e d e s i r e d g r e y l e v e l ( i . e . g d = . 1 9 4 ) a n d 3 5 t h e s e : g = (gd - g l ) / ( g h - gl) ( i . e . g=(. 194-.167)/(.221-.167) = .5 = 50%). Then the polygon would c o n t a i n the low grey l e v e l (gl) everywhere but where the maxmin p a t t e r n f o r g ( i . e . 50%) has an on b i t , these p o i n t s would be the h i g h grey l e v e l (gh) as demonstrated i n F i g u r e 17. a) The 16 s o l i d grey l e v e l s (0/16 to 15/16) as generated by a l a s e r p r i n t e r b) The 16 s o l i d grey l e v e l s (0/16 to 15/16) w i t h the the maxmin p a t t e r n f o r 0.5 used t o b l e n d the grey l e v e l s i n between F i g u r e 17. The h a l f t o n e p a t t e r n s f o r grey l e v e l s 0/16 to 15/16 b e f o r e and a f t e r b l e n d i n g w i t h a maxmin p a t t e r n f o r 0.5 36 As demonstrated i n F i g u r e 18, some d i f f i c u l t i e s i n p r i n t i n g mixed grey l e v e l s occur on c u r r e n t p r i n t e r s . In F i g u r e 18, the p r i n t e r may do some r e d i s t r i b u t i o n of v a l u e s t o ma i n t a i n the d e s i r e d l e v e l o f grey while compensating f o r p r i n t d i f f i c u t i e s . Even w i t h t h i s compensation, each row s t i l l m a i n t a i n s the d e s i r e d c o n t i n u i t y from one grey l e v e l t o the next. T h i s i s e a s i l y seen by examining each row i n d i v i d u a l l y . The row w i l l appear t o be the same tone or a g r a d u a l l y darkening tone as c h a r a c t e r i z e d by the maxmin p a t t e r n s used. a) The maxmin p a t t e r n s used t o b l e n d a c r o s s each row i n b) b) Rows of blended grey l e v e l s u s i n g maxmin p a t t e r n s (the f i r s t and l a s t grey p a t t e r n on each row i s the unblended h a l f t o n e ) F i g u r e 18. H a l f t o n e p a t t e r n s blended u s i n g maxmin p a t t e r n s to i n c r e a s e the number of grey l e v e l s from 16 t o 256 8 C o n c l u s i o n By i n c r e a s i n g the s p a t i a l s e p a r a t i o n between the p i x e l s , the maxmin method e x h i b i t s a v i s u a l evenness i n the grey of a p a t t e r n f o r r e p l i c a t i o n . The a l g o r i t h m presented, although c o m p u t a t i o n a l l y expensive f o r l a r g e r numbers of p i x e l s , f i n d s a p a t t e r n w i t h the maximum minimum d i s t a n c e between p i x e l s . To reduce s i g n i f i c a n t l y the number of p o s s i b l e p i x e l combinations, the a l g o r i t h m uses a m u l t i l e v e l l o c a l i z i n g parameter t o ensure t h a t each s m a l l r e g i o n o f the image i s as c l o s e as p o s s i b l e t o the d e s i r e d grey l e v e l , and a 'good' guess c r i t e r i a t o e l i m i n a t e many u n d e s i r a b l e combinations. The maxmin a l g o r i t h m produces many p a t t e r n s which are shown to be v i s u a l l y b e t t e r than ordered d i t h e r , e r r o r d i f f u s i o n and random d i s t r i b u t i o n f o r r e p l i c a t i o n i n area f i l l a l g o r i t h m s e s p e c i a l l y at lower l e v e l s of grey where the maxmin a l g o r i t h m i s even b e t t e r then a f u l l e r r o r d i f f u s i o n a c r o s s the complete image. Compared t o e r r o r d i f f u s i o n and ordered d i t h e r , 1 maxmin demonstrates a d e f i n i t e improvement by gua r a n t e e i n g the maximum minimum d i s t a n c e between p i x e l s . By u s i n g wraparound c a l c u l a t i o n s t o compute the l e n g t h between p i x e l s , maxmin a l s o ensures t h a t the r e s u l t i n g p a t t e r n w i l l have good r e p l i c a t i o n p r o p e r t i e s and minimize the number of a r t i f a c t s i n t r o d u c e d by the r e p l i c a t i o n procedure i t s e l f . Maxmin does e x h i b i t some a r t i f a c t s . These a r t i f a c t s may appear as a box l i k e s t r u c t u r e s i m i l a r t o a d i t h e r of the same grey l e v e l or l i k e p a r a l l e l d i a g o n a l l i n e s when p i x e l d e n s i t y i s 38 near 35%. These a r t i f a c t s e x i s t because the maximum minimum d i s t a n c e always l i e s along a d i a g o n a l , and when the p i x e l s a t u r a t i o n i s too great, the program w i l l f i n d the p a t t e r n t h a t spaces the d i a g o n a l l i n e s or boxes apart as f a r as p o s s i b l e . These p a t t e r n s are d i f f i c u l t t o o f f s e t manually s i n c e they a l r e a d y e x h i b i t the maximum minimum d i s t a n c e and a d j u s t i n g the p i x e l s would normally decrease the minimum d i s t a n c e . To improve these p a t t e r n s , e i t h e r the g r i d s i z e must be i n c r e a s e d t o allow more f l e x i b i l i t y at low grey l e v e l s as shown i n F i g u r e 14a and F i g u r e 14b, or a d i f f e r e n t c r i t e r i a must be used i n c o n j u n c t i o n w i t h the maxmin a l g o r i t h m as e x h i b i t e d f o r p a t t e r n s near 50% ( i . e . maximize the minimum d i s t a n c e between m i s s i n g p i x e l s i n a checker board p a t t e r n ) . The improvements i n the p a t t e r n s do have e x t r a c o s t s . There i s a need f o r more memory f o r the p i x e l p o s i t i o n s , w i t h the main c o n s t r a i n i n g f a c t o r b e i n g the computational work which r i s e s g e o m e t r i c a l l y t o an i n c r e a s e i n the number of p i x e l s . Although many grey l e v e l s have good p a t t e r n s t h a t are q u i c k l y found, e l i m i n a t i n g much of the work, i t i s not easy t o p r e d i c t which p a t t e r n s w i l l converge r a p i d l y . 39 9. References B. E. Bayer, "An Optimum Method f o r Two-Level R e n d i t i o n of Continuous-Tone P i c t u r e s , " Proc. IEEE I n t . Conf. Commun., Conference Record 26(1:1973), pp. 11-15. C. N. J u d i c e , J.F. J a r v i s , and W. H. Ninke, "Using Ordered D i t h e r t o D i s p l a y Continuous Tone P i c t u r e s on a Plasma P a n e l , " Proc. SID 15(1974), pp. 161-169. J.D. F o l e y and A. Van Dam, Fundamentals of I n t e r a c t i v e  Computer Graphics, Addison Wesley, 1982, pp. 594-602. R. W. F l o y d and L. S t e i n b e r g , "An A d a p t i v e A l g o r i t h m f o r S p a t i a l G r e y s c a l e , " Proc. Soc. I n f . D i s p l a y 17(2:1976), pp. 75-77. J . F. J a r v i s , C. N. J u d i c e , and W. H. Ninke, "A Survey of Techniques f o r the D i s p l a y of Continuous Tone P i c t u r e s on B i l e v e l D i s p l a y s , " Comput. Graph. Image P r o c e s s . 5(1976), pp. 13-40. C. B i l l o t e t - H o f f m a n n and 0. Bryngdahl, "On the E r r o r D i f f u s i o n Technique f o r E l e c t r o n i c H a l f t o n i n g , " Proc. SID 24 (3:1983), pp. 253-258. G.S. Fawcett and G.F. Schrack, " H a l f t o n i n g Techniques Using E r r o r C o r r e c t i o n , " Proc. SID 27 (4:1986), pp. 305-308. E. Catmull, "A T u t o r i a l on Compensation T a b l e s " , Computer Graphics (ACM SIGGRAPH) • 13 (2: August 1979), pp. 1-7. D. G. H e i s s , " C a l i b r a t i n g the Photographic Reproduction of Col o u r D i g i t a l Images," M.Sc. T h e s i s , U.B.C. ( A p r i l : 1 9 8 5 ) . 40 10. Appendix A; The Program t o generate maxmin p a t t e r n s F o l l o w i n g i s a copy of the C source code f o r the maxmin a l g o r i t h m . As the language C may vary from i n s t a l l a t i o n t o i n s t a l l a t i o n , t h i s v e r s i o n may need some m o d i f i c a t i o n s . I t c u r r e n t l y runs on the U.B.C. csgrads SUN w o r k s t a t i o n s , U.B.C. g e n e r a l computer, an IBM AT compatible and an ATARI 1040ST with minor m o d i f i c a t i o n s . 41 /* _ */ /* Maxmin.c : F i n d a p i x e l p a t t e r n w i t h the p i x e l s s e p a r a t e d as much as p o s s i b l e */ /* _ */ /* Include s t a n d a r d system input /output and s t r i n g d e c l a r a t i o n s */ #include <stdio.h> #include <string.h> /* l e v e l s i s the number of l e v e l s t o d i s t r i b u t e the p i x e l s through */ #define l e v e l s 5 /* compares i s the number of minimum d i s t a n c e s r e t a i n e d f o r comparing */ #define compares 2 /* maxp i s the maximum number of p i x e l s t o be c o n s i d e r e d ( f o r d e c l a r a t i o n s ) */ t d e f i n e maxp 128 /* WRITE_BINARY i s the operands f o r an fop e n ( ) , t h i s i s s p e c i f i c t o the computer */ #define WRITE_BINARY "wi" /* To get and f r e e e x t r a memory, some computers use other f u n c t i o n s */ #define M a l l o c ( a ) malloc(a) #define Mfree(a) f r e e ( a ) char * m a l l o c ( ) ; /* cntmin, cntcmp are g l o b a l v a r i a b l e s t o count the number of comparisons and minimums l o c a t e d */ i n t cntmin = 0,cntcmp = 0; /* For the memory b l o c k s r e q u i r e d f o r the l e v e l s , width s p e c i f i e s the s i z e o f a l e v e l , s t a r t s p e c i f i e s the o f f s e t t o the f i r s t byte, memp i s the address of the memory wit h a l l the l e v e l s */ i n t w i d t h [ l e v e l s ] ; l o n g s t a r t [ l e v e l s ] ; s h o r t *memp; /* Output f i l e i d e n t i f i e r */ FILE *outfdub; i n t maxx; /* px,py d e f i n e the p i x e l s i n x,y c o o r d i n a t e s p i , p j d e f i n e the l e f t upper corner o f the box f o r each p i x e l , pos i s the l o c a t i o n w i t h i n the box, 42 pnd i s the number of pi x e l s required aft e r the current one i n the same box, cmin i s the l i s t of minimum distances for one point to a l l preceding points cent i s the counts for the minimums tmax i s the maximum distance at each point */ i n t px[maxp],py[maxp],cent[maxp][compares]; i n t pi[maxp],pj[maxp],pos[maxp],pnd[maxp]; f l o a t cmin[maxp][compares],tmax[maxp]; /* To preserve the best pattern so far (and the r e s u l t ) : hx,hy are the 'px','py' coordinates of a l l the pi x e l s hmin i s the 'cmin' for the best guess hent i s the 'cent' for the best guess htmax i s the 'tmax' for the best guess */ f l o a t hmin[compares],htmax; in t hx[maxp],hy[maxp],hent[compares]; /* ovaluep i s the o r i g i n a l input value, valuep i s the modified value for which maxmin solves */ f l o a t ovaluep,valuep; /* used to output the pix e l s i n a packed form: cury i s used to detect a change i n the scan row, bi t c n t counts the pi x e l s used i n the current byte, outbyte i s the output byte, f l i p o u t indicates i f the image i s to be f l i p p e d for i>50% */ in t cury=0-l,bitcnt = 0; char outbyte = 0; in t f l i p o u t ; /* */ /* Get the desired input from the user or command l i n e */ /* _ */ getval(argc,argv) i n t argc; char *argv[]; { i f (argc <=1) { printfC'What percentage of grey dots?"); scanf("%f",&valuep); } else sscanf(argv[l],"%f",&valuep); i f (valuep > 1.0) valuep = 1.0; f l i p o u t = 1; ovaluep = valuep; 43 i f (valuep > .5) { f l i p o u t = 0; valuep = 1.0 - valuep; } return; } /* */ /* Open the output f i l e f i l e name i s of the form pat####.dat where #### represents the o r i g i n a l input grey-l e v e l */ /* */ openout () { char t l [15],t2[15]; s p r i n t f ( t l , " % 7 f " , o v a l u e p ) ; strcpy(t2,"pat0000.dat\0") ; strncpy(t2 + 3,tl,1) ; strncpy(t2 + 4,11 + 2, 3) ; outfdub = fopen(t2,WRITE_BINARY) ; fwrite(&maxx,sizeof(int),1,outfdub); /* */ /* Set an x,y p i x e l to the value of point, x,y must be i n sequence for a row by row scan */ /* */ setpnt(x,y,point) in t x,y,point; { int b i t r e ; /* On a new scan, output the byte from the previous scan */ i f (cury >= 0 && y != cury && b i t c n t > 0) { fwrite(Soutbyte,1,1,outfdub); outbyte = b i t c n t =0; } /* Add the new p i x e l to the accumulating byte */ b i t r e = 1 « (7-bitcnt); i f (point == flipout) outbyte = outbyte I b i t r e ; bitcnt++; /* When a byte i s f u l l , output i t */ i f (bitcnt >= 8 ) { fwrite(&outbyte,1,1,outfdub); outbyte = b i t c n t = 0; } 44 } cury /* */ /* Set up memory f o r m u l t i l e v e l p i x e l d i s t r i b u t i o n */ /* */ makemem() { i n t i , k ; long j ; j = 0; f o r (i=0;i<levels;i++) { s t a r t [ i ] = j ; k = (l « i ) ; w i d t h [ i ] = k; j += (long) k * k; } memp = (short *) M a l l o c ( j * s i z e o f ( s h o r t ) ) ; /* */ /* Return the number of p i x e l s t o be set i n the sub c e l l at x,y i n l e v e l 1 */ /* */ i n t g p ( x , y , l ) i n t x , y , l ; { s h o r t *k; i n t t ; k = memp + ( s t a r t [ 1 ] + (long) width[1] * y + x ) ; t= ( i n t ) * k ; r e t u r n ( t ) ; /* */ /* Set the v a l u e at a p a r t i c u l a r x,y p o i n t of l e v e l 1 to the v a l u e p */ /* */ pp(x,y,l,p) i n t x , y , l , p ; { s h o r t *k; k = memp + ( s t a r t [ 1 ] + (long) width[1] * y + x) ; *k = ( s h o r t ) p ; r e t u r n ; 45 /* /* Increment the number of p i x e l s r e q u i r e d at and x,y p o i n t o f l e v e l 1 by one */ /* inc(x,y,1) i n t x , y , l ; { i n t t ; t = gp (x, y, 1) ; pp(x,y,1,(t+1)); } /* /* C o n t r o l l i n g procedure (main) /* main(argc,argv) i n t argc; char * a r g v [ ] ; { i n t i , j , k, t ; i n t ent; f l o a t accum; makemem(); g e t v a l ( a r g c , a r g v ) ; /* Reset the v a l u e s o f the h i g h e s t l e v e l t o zero */ maxx = 1<< ( l e v e l s - 1 ) ; f o r (i=0;i<maxx;i++) for(j=0;j<maxx;j++) p p ( i , j , ( l e v e l s - 1 ) , 0 ) ; /* On a l l lower l e v e l s s et the number of p i x e l s t o be d i s t r i b u t e d */ accum = valuep; f o r (k=levels-2;k>=0;k—) { maxx = l « k ; accum =4.0 * accum; t = ( i n t ) accum; accum = accum - ( f l o a t ) t ; for(i=0;i<maxx;i++) f o r (j=0;j<maxx;j++) p p ( j , i , k , t ) ; } /* t o best approximate the grey l e v e l s , the number of p i x e l s i s incremented i f more than 1/2 a p i x e l i s needed */ i f (accum > 0.5) i n c (0,0,0); maxx = 1<<(levels-1); p r i n t f ( " F o r grey l e v e l : % f (%f)\n",valuep,1.0-valuep); p r i n t f ( " O n a p a t t e r n %d * %d,\n",maxx,maxx); /* D i s t r i b u t e the p i x e l s from one l a y e r t o the next */ f o r (k=0;k<levels-l;k++) { maxx = l«k; p r i n t f ( " at l e v e l : %d\n",k); dist(k,maxx,Sent); p r i n t f C dots set ( r e s e t ) : %d\n", cnt + 1) ; f o r (i=0;i<=cnt;i++) i n c (hx[i] ,hy [ i ] ,k+l) ; } /* Output the p i x e l s and count the number tha t are set */ k = l e v e l s - 1 ; maxx = l«k; ent =0; openout(); f o r (i=0;i<maxx;i++) f o r (j=0;j<maxx;j++) i f ( g p ( j , i , k ) != 0) { s e t p n t ( j , i , 1) ; cnt++; } e l s e setpnt ( j , i , 0 ) ; setpnt(10000,10000,0); f c l o s e ( o u t f d u b ) ; p r i n t f ( " R e s u l t i n g grey i s : %d / %d = %f\n\n", ent, (maxx*maxx), ( f l o a t ) ent/ ((float)maxx*maxx) ); /* Free the used memory */ Mfree(memp); } /* */ /* D i s t r i b u t e the p i x e l s on a p a r t i c u l a r l e v e l */ /* */ d i s t (k, maxx, cn) i n t k,maxx,*cn; { i n t i , j , ent,mcnt,n,m; ent = -1; /* number of p o i n t s set so f a r */ 47 cntcmp = cntmin = 0; /* Set the i n i t i a l p o i n t s of a l l p i x e l s i n each box i n the order used by setxypnt, and compute the minimum d i s t a n c e s as the c h a i n i s b u i l t */ f o r (i=0;i<maxx;i++) f o r (j=0;j<maxx;j++) { n = gp ( i , j , k) ; f o r ( m=0; m<n && ent <maxp ;m++) { ent ++; p i [ e n t ] = i * 2 ; p j [ c n t ] = j * 2 ; pos[ent] = m; pnd[ent] = n-l-m; s e t x y p n t ( e n t ) ; lenpnt(ent,0.0,maxx*2); } } i f (ent >= maxp) { pr i n t f ( " n u m b e r of p o i n t s r e q u i r e d i s g r e a t e r then a v a i l a b l e memory\n"); p r i n t f ( " r e s u l t s w i l l be i n a p p r o p r i a t e \ n " ) ; r e t u r n ; } /* T h i s f i r s t setup i s the i n i t i a l good guess */ m i n i s ( e n t ) ; *cn = mcnt = ent; i f (ent < 1) r e t u r n ; /* While t h e r e are p i x e l s t h a t can be moved */ wh i l e (cnt> 0) { /* move the l a s t one i n the c h a i n */ pos[ent]++; /* i f the move was v a l i d */ i f ( s e t x y p n t ( e n t ) ) { /* Compute the new le n g t h s from a l l p r e c e d i n g p o i n t s */ lenpnt(ent,hmin[0],maxx*2); 48 /* For a l l p o i n t s a f t e r the c u r r e n t moved one, r e s e t them to the i n i t i a l p o s i t i o n and compute t h e i r new l e n g t h s , as l o n g as the c h a i n b e i n g b u i l t remains b e t t e r than the good guess */ w h i l e (cmppnt (ent) && ent < mcnt) { cnt++; /* i f s e v e r a l p i x e l s belong i n the same box, set t h e i r p o s i t i o n s i n c o n s e c u t i v e o r d e r i n g */ i f ( p i [ c n t - l ] == p i [ e n t ] && p j [ c n t - 1 ] == p j [ e n t ] ) pos [ent], = pos [cnt-1] +1; e l s e /* the f i r s t p i x e l of each box goes i n the upper l e f t corner */ pos[ent] = 0; /* Compute the new x,y and l e n g t h s */ s e t x y p n t ( e n t ) ; lenpnt(cnt,hmin[0],maxx*2); } i f (cmppnt(ent)) minis ( e n t ) ; } e l s e ent — ; } p r i n t f ( " T h e number of compares = %d, minimums = %d\n", cntcmp,cntmin); } /* */ /* Set the minimum f o r the p a t t e r n and save p a t t e r n */ /* _ */ m i n i s ( e n t ) i n t ent; { i n t i ; cntmin++; f o r (i=0;i<=cnt;i++) { h x [ i ] = p x [ i ] ; h y [ i ] = p y [ i ] ; } f o r (i=0;i<compares;i++) { hmin[i] = cmin[ent] [i ] ; h c n t [ i ] = c e n t [ e n t ] [i ] ; } htmax = tmax[cnt]; 49 /* */ /* compare the c u r r e n t v a l u e t o the minimum and r e t u r n -1 i f the new val u e i s b e t t e r than the l a s t minimum */ /* */ i n t cmppnt(ent) i n t ent; { i n t i ; cntcmp++; f o r (i=0;i<compares ;i++) /* i f the new minimum at the c u r r e n t p o i n t i s l e s s than the o v e r a l l minimum of the c u r r e n t guess, abort the c u r r e n t c h a i n */ i f ( c m i n [ e n t ] [ i ] < hmin[i]) r e t u r n 0; e l s e i f ( c m i n [ e n t ] [ i ] == h m i n f i ] ) i f ( c e n t [ e n t ] [ i ] > h c n t [ i ] ) r e t u r n 0; /* i f the new minimum at the c u r r e n t p o i n t i s b e t t e r than the o v e r a l l minimum of the c u r r e n t guess, c o n t i n u e */ e l s e i f ( c e n t [ e n t ] [ i ] < h c n t [ i ] ) r e t u r n -1; e l s e ; e l s e r e t u r n -1; /* In case o f t i e , use the maximum d i s t a n c e as t i e breaker */ i f (tmax[ent] >= htmax ) r e t u r n 0; r e t u r n (-1); } /* */ /* compute the l a s t p o i n t ' s new x,y p o s i t i o n , and r e t u r n 0 (FALSE) i f the move was i l l e g a l */ /* */ i n t setxypnt (ent) i n t ent; { /* I f more p i x e l s are to be set i n t h i s box, and t h e r e i s no space, then t h i s p o s i t i o n i s i n v a l i d */ i f (pos[ent] + pnd[cnt] >= 4) r e t u r n (0) ; 50 /* Otherwise set the x,y co o r d i n a t e s i n a d i t h e r o r d e r i n g */ swi t c h (pos [ent]) { case 0: px[ent] = p i [ e n t ] / py[ent] = p j [ent] r break; case 1: px[ent] = p i [ e n t ] + 1; py[ent] = p j [ e n t ] +1; break; case 2: px[ent] = p i [ e n t ] py[ent] = p j [ e n t ] +1; break; case 3: px[ent] = p i [ e n t ] +1; py[ent] = p j [ e n t ] } r e t u r n -1; /* */ /* F i n d the minimum len g t h s between t h i s p o i n t and a l l p r e v i o u s p o i n t s and use the minimums from the p r e v i o u s p o i n t i n the c h a i n */ /* */ lenpnt(ent,min,maxx) i n t ent,maxx; f l o a t min; { i n t i , j , k , m i , m j ; f l o a t d , t ; /* I f no p r e v i o u s p o i n t s i n the c h a i n , s e t the minimum h i g h */ i f (ent == 0) { f o r (i=0;i<compares;i++) { c m i n [ c n t ] [ i ] = 1000000; cent [ent] [ i ] = 0; tmax[cnt] = 0; } r e t u r n ; } /* Otherwise copy the p r e v i o u s minimums */ f o r (i=0;i<compares;i++) { c m i n [ c n t ] [ i ] = c m i n [ c n t - 1 ] [ i ] ; c e n t [ e n t ] [ i ] = cent[cnt-1] [ i ] ; } t = 10000; tmax[cnt] = tmax[cnt-1]; 51 / * A n d c o m p u t e t h e n e w d i s t a n c e s * / f o r ( i = c n t - l ; i > = 0 && c m i n [ e n t ] [ 0 ] > = m i n ; i — ) { m i = a b s ( p x [ c n t ] - p x [ i ] ) ; m j = a b s ( p y [ c n t ] - p y [ i ] ) ; / * U s e w r a p a r o u n d d i s t a n c e s * / i f ( m i > m a x x / 2 ) m i = m a x x - m i ; i f ( m j > m a x x / 2 ) m j = m a x x - m j ; d = ( f l o a t ) ( m i * m i + m j * m j ) ; i f ( d < t ) t = d ; / * r e m e m b e r t h e n e w m i n i m u m s * / f o r ( j = c o m p a r e s - l ; j > = 0 && d < c m i n [ e n t ] [ j ] ; j — ) ; i f ( d == c m i n [ c n t ] [ j ] ) c e n t [ e n t ] [ j ] ++ ; e l s e i f ( j < c o m p a r e s - 1 ) { f o r ( k = c o m p a r e s - 2 ; k > j ; k - - ) { c m i n [ e n t ] [ k + 1 ] = c m i n [ e n t ] [ k ] ; c e n t [ e n t ] [ k + 1 ] = c e n t [ e n t ] [ k ] ; } c m i n [ e n t ] [ j + 1 ] = d ; c e n t [ e n t ] [ j + 1 ] = 1 ; } ( t > t m a x [ e n t ] ) t m a x [ e n t ] = t ; } i f 5 2 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0097694/manifest

Comment

Related Items