misha@nsc.UUCP (04/22/87)
Hello. This subject was probably already discussed but I must have missed it then. I am looking for a general purpose greyscale to greyscale conversion routine. Example: I have a bitmap image with 8 bits per pixel. Now, I have a monochrome TTL monitor which requires 1 bit per pixel. I need to convert the 8-bit-pixel image to 1-bit-pixel image and still be able to distinguish original shapes and lines. If there is a specific algorithm for such a situation it is wellcome. Also, if there is a generic algorithm which can handle arbitrary bits-per-pixel size conversion (i.e.: 7 to 2, 5 to 4, 2 to 6 ???), it is very wellcome. Thanks in advance. -- NAME: Michael Umansky (misha) E-MAIL: sun! ----\ hplabs! --\ pyramid! --+----> nsc!misha decwrl! --/ amdahl! -/ WORK: National Semiconductor Corporation 1135 Kern Avenue Sunnyvale, CA 94086 (408) 721-8109 (work) HOME: 4331 Lincoln Way San Francisco, CA 94122 (415) 564-3921 (home)
dave@viper.UUCP (David Messer) (04/24/87)
In article <4231@nsc.nsc.com> misha@nsc.nsc.com (Michael Umansky) writes: >Hello. >This subject was probably already discussed but I must have missed it then. >I am looking for a general purpose greyscale to greyscale conversion routine. > >Example: > I have a bitmap image with 8 bits per pixel. > Now, I have a monochrome TTL monitor which requires 1 bit per pixel. > I need to convert the 8-bit-pixel image to 1-bit-pixel image and > still be able to distinguish original shapes and lines. > >If there is a specific algorithm for such a situation it is wellcome. >Also, if there is a generic algorithm which can handle arbitrary >bits-per-pixel size conversion (i.e.: 7 to 2, 5 to 4, 2 to 6 ???), >it is very wellcome. One technique that is commonly used for this application is called "dithering". With the dithering technique, a high or low output value is choosen proportional to the amount of the value that lies between the two possible output values. For example, in the eight bit to one bit case, an input value of 128 would produce half "on" pixels and half "off" pixels. For other conversions, dithering may be used after a scaling operation. For instance, to convert eight-bit pixels to three-bit ones, use the most significant three bits to form a base value and dither the remaining five bits to see if you should add one to the result. A subset of dithering functions is the "ordered-dither" functions. One of these uses a recurrence relation to produce a matrix of comparison values which is duplicated over the whole frame by masking the higher bits out of the X and Y coordinates. Here is the generating function: D(1) = 0 4*D(n)+0 | 4*D(n)+2 D(2*n) = --------------------- 4*D(n)+3 | 4*D(n)+1 Thus: D(2) = | 0 2 | D(4) = | 0 8 2 10 | | 3 1 | |12 4 14 6 | | 3 11 1 9 | |15 7 13 5 | And so on. This function has the interesting property that for any given intensity the resulting "on" bits will be as far apart as possible. Here is a subroutine package that I wrote that generates the ordered- dither function from D(1) to D(256). Enjoy. #--------CUT---------CUT---------CUT---------CUT--------# ######################################################### # # # This is a shell archive file. To extract files: # # # # 1) Make a directory for the files. # # 2) Write a file, such as "file.shar", containing # # this archive file into the directory. # # 3) Type "sh file.shar". Do not use csh. # # # ######################################################### # # This archive contains the following files: # dither.h # dither.c # ######################################################### # # echo Extracting dither.h: sed 's/^Z//' >dither.h <<\STUNKYFLUFF Z/*** Z * dither.h [04/11/87] - order dither function defines. Z * Z * Copyright 1987 Lynx Data Systems and David Messer Z * All Rights Reserved. Z * Z * This program may be freely copied or incorporated Z * in another program as long as the intent is not for Z * direct profit and as long as this copyright notice Z * is retained. Z */ Z Z/* Z * Decide which functions to include and what form of them. Z */ Z Z#define D_NONE 0 /* Don't include function */ Z#define D_CALC 1 /* Calculate function each time */ Z#define D_TABLE 2 /* Keep table of function for speed */ Z Z#define D2 D_TABLE Z#define D4 D_TABLE Z#define D8 D_TABLE Z#define D16 D_TABLE Z#define D32 D_TABLE Z#define D64 D_CALC Z#define D128 D_CALC Z#define D256 D_CALC Z Z Z/* Z * External definitions Z */ Z Z#if D256 != D_TABLE && D128 != D_TABLE && D64 != D_TABLE && \ Z D32 != D_TABLE && D16 != D_TABLE && D8 != D_TABLE && \ Z D4 != D_TABLE && D2 != D_TABLE Z# define dithinit() {} Z#endif Zextern unsigned int dither() ; Z Z#define d0( a, b ) (0) Z Z#if D2 != D_NONE Zextern unsigned int d2() ; Z#endif Z Z#if D4 != D_NONE Zextern unsigned int d4() ; Z#endif Z Z#if D8 != D_NONE Zextern unsigned int d8() ; Z#endif Z Z#if D16 != D_NONE Zextern unsigned int d16() ; Z#endif Z Z#if D32 != D_NONE Zextern unsigned int d32() ; Z#endif Z Z#if D64 != D_NONE Zextern unsigned int d64() ; Z#endif Z Z#if D128 != D_NONE Zextern unsigned int d128() ; Z#endif Z Z#if D256 != D_NONE Zextern unsigned int d256() ; Z#endif STUNKYFLUFF set `sum dither.h` if test 39355 != $1 then echo dither.h: Checksum error. Is: $1, should be: 39355. fi # # echo Extracting dither.c: sed 's/^Z//' >dither.c <<\STUNKYFLUFF Z#include "dither.h" Z Z/*** Z * dither.c [04/11/87] - ordered dither computation functions. Z * Z * Copyright 1987 Lynx Data Systems and David Messer Z * All Rights Reserved. Z * Z * This program may be freely copied or incorporated Z * in another program as long as the intent is not for Z * direct profit and as long as this copyright notice Z * is retained. Z */ Z Zunsigned int Zdither( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z register unsigned int i, j ; Z Z i = ((a & 0xF0)<<4) | (a & 0x0F) ; Z i = ((i & 0xC0C)<<2) | (i & 0x303) ; Z i = ((i & 0x2222)<<1) | (i & 0x1111) ; Z Z j = ((b & 0xF0)<<4) | (b & 0x0F) ; Z j = ((j & 0xC0C)<<2) | (j & 0x303) ; Z j = ((j & 0x2222)<<1) | (j & 0x1111) ; Z Z i = (j<<1) | (i ^ j) ; Z i = (i<<8) | ((i>>8) & 0x00FF) ; Z i = ((i<<4) & 0xF0F0) | ((i>>4) & 0x0F0F) ; Z i = ((i<<2) & 0xCCCC) | ((i>>2) & 0x3333) ; Z i = ((i<<1) & 0xAAAA) | ((i>>1) & 0x5555) ; Z Z return( i ) ; Z Z } /* dither */ Z Z Z Z Z#if D256 == D_TABLE || D128 == D_TABLE || D64 == D_TABLE || \ Z D32 == D_TABLE || D16 == D_TABLE || D8 == D_TABLE || \ Z D4 == D_TABLE || D2 == D_TABLE Z Z# if D2 == D_TABLE Zunsigned char d2tab[4] ; Z# endif Z Z# if D4 == D_TABLE Zunsigned char d4tab[16] ; Z# endif Z Z# if D8 == D_TABLE Zunsigned char d8tab[64] ; Z# endif Z Z# if D16 == D_TABLE Zunsigned char d16tab[256] ; Z# endif Z Z# if D32 == D_TABLE Zunsigned int d32tab[1024] ; Z# endif Z Z# if D64 == D_TABLE Zunsigned int d64tab[4096] ; Z# endif Z Z# if D128 == D_TABLE Zunsigned int d128tab[16384] ; Z# endif Z Z# if D256 == D_TABLE Z# ifdef iAPX286 Zunsigned int d256t0[16384] ; Zunsigned int d256t1[16384] ; Zunsigned int d256t2[16384] ; Zunsigned int d256t3[16384] ; Z# else Zunsigned int d256tab[65536] ; Z# endif Z# endif Z Zdithinit() Z{ Z register unsigned int i ; Z Z# if D2 == D_TABLE Z for( i = 0; i < 4; i++ ) { Z d2tab[i] = dither( i>>1, i&0x01 ) >> 14 ; Z } Z# endif Z Z# if D4 == D_TABLE Z for( i = 0; i < 16; i++ ) { Z d4tab[i] = dither( i>>2, i&0x03 ) >> 12 ; Z } Z# endif Z Z# if D8 == D_TABLE Z for( i = 0; i < 64; i++ ) { Z d8tab[i] = dither( i>>3, i&0x07 ) >> 10 ; Z } Z# endif Z Z# if D16 == D_TABLE Z for( i = 0; i < 256; i++ ) { Z d16tab[i] = dither( i>>4, i&0x0F ) >> 8 ; Z } Z# endif Z Z# if D32 == D_TABLE Z for( i = 0; i < 1024; i++ ) { Z d32tab[i] = dither( i>>5, i&0x1F ) >> 6 ; Z } Z# endif Z Z# if D64 == D_TABLE Z for( i = 0; i < 4096; i++ ) { Z d64tab[i] = dither( i>>6, i&0x3F ) >> 4 ; Z } Z# endif Z Z# if D128 == D_TABLE Z for( i = 0; i < 16384; i++ ) { Z d128tab[i] = dither( i>>7, i&0x7F ) >> 2 ; Z } Z# endif Z Z# if D256 == D_TABLE Z for( i = 0; i < 16384; i++ ) { Z# ifdef iAPX286 Z d256t0[i] = dither( i>>8, i&0xFF ) ; Z d256t1[i] = dither( (i>>8) | 0x40, i&0xFF ) ; Z d256t2[i] = dither( (i>>8) | 0x80, i&0xFF ) ; Z d256t3[i] = dither( (i>>8) | 0xC0, i&0xFF ) ; Z# else Z d256tab[i] = dither( i>>8; i&0xFF ) ; Z d256tab[i | 0x4000] = dither( (i>>8) | 0x40, i&0xFF ) ; Z d256tab[i | 0x8000] = dither( (i>>8) | 0x80, i&0xFF ) ; Z d256tab[i | 0xC000] = dither( (i>>8) | 0xC0, i&0xFF ) ; Z# endif Z } Z# endif Z Z } /* dithinit */ Z Z Z#endif Z Z Z Z Z Z#if D2 != D_NONE Z Zunsigned int Zd2( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D2 == D_TABLE Z return( d2tab[ ((a & 0x01)<<1) | (b & 0x01) ] ) ; Z#else Z return( dither( a, b ) >> 14 ) ; Z#endif Z } /* d2 */ Z Z#endif Z Z Z Z Z Z#if D4 != D_NONE Z Zunsigned int Zd4( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D4 == D_TABLE Z return( d4tab[ ((a & 0x03)<<2) | (b & 0x03) ] ) ; Z#else Z return( dither( a, b ) >> 12 ) ; Z#endif Z } /* d4 */ Z Z#endif Z Z Z Z Z Z#if D8 != D_NONE Z Zunsigned int Zd8( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D8 == D_TABLE Z return( d8tab[ ((a & 0x07)<<3) | (b & 0x07) ] ) ; Z#else Z return( dither( a, b ) >> 10 ) ; Z#endif Z } /* d8 */ Z Z#endif Z Z Z Z Z Z#if D16 != D_NONE Z Zunsigned int Zd16( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D16 == D_TABLE Z return( d16tab[ ((a & 0x0F)<<4) | (b & 0x0F) ] ) ; Z#else Z return( dither( a, b ) >> 8 ) ; Z#endif Z } /* d16 */ Z Z#endif Z Z Z Z Z Z#if D32 != D_NONE Z Zunsigned int Zd32( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D32 == D_TABLE Z return( d32tab[ ((a & 0x1F)<<5) | (b & 0x1F) ] ) ; Z#else Z return( dither( a, b ) >> 6 ) ; Z#endif Z } /* d32 */ Z Z#endif Z Z Z Z Z Z#if D64 != D_NONE Z Zunsigned int Zd64( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D64 == D_TABLE Z return( d64tab[ ((a & 0x3F)<<6) | (b & 0x3F) ] ) ; Z#else Z return( dither( a, b ) >> 4 ) ; Z#endif Z } /* d64 */ Z Z#endif Z Z Z Z Z Z#if D128 != D_NONE Z Zunsigned int Zd128( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D128 == D_TABLE Z return( d128tab[ ((a & 0x7F)<<7) | (b & 0x7F) ] ) ; Z#else Z return( dither( a, b ) >> 2 ) ; Z#endif Z } /* d128 */ Z Z#endif Z Z Z Z Z Z#if D256 != D_NONE Z Zunsigned int Zd256( a, b ) Zunsigned int a ; Zunsigned int b ; Z{ Z#if D256 == D_TABLE Z# ifdef iAPX286 Z switch( a & 0xC0 ) { Z case 0x00: Z return( d256t0[ ((a & 0x3F) << 8) | (b & 0xFF) ] ) ; Z case 0x40: Z return( d256t1[ ((a & 0x3F) << 8) | (b & 0xFF) ] ) ; Z case 0x80: Z return( d256t2[ ((a & 0x3F) << 8) | (b & 0xFF) ] ) ; Z case 0xC0: Z return( d256t3[ ((a & 0x3F) << 8) | (b & 0xFF) ] ) ; Z } Z# else Z return( d256tab[ ((a & 0xFF)<<8) | (b & 0xFF) ] ) ; Z# endif Z#else Z return( dither( a, b ) ) ; Z#endif Z } /* d256 */ Z Z#endif STUNKYFLUFF set `sum dither.c` if test 11353 != $1 then echo dither.c: Checksum error. Is: $1, should be: 11353. fi echo ALL DONE BUNKY! exit 0 -- If you can't convince | David Messer - Lynx Data Systems them, confuse them. | -- Harry S. Truman | amdahl \ | ihnp4 --!-- dayton --!viper!dave | rutgers / \ meccts / Copyright 1987 David Messer -- All Rights Reserved This work may be freely copied. Any restrictions on redistribution of this work are prohibited.
curtj@pogo.TEK.COM (Curt Jutzi) (04/24/87)
In article <4231@nsc.nsc.com> misha@nsc.nsc.com (Michael Umansky) writes: >Hello. >Example: > I have a bitmap image with 8 bits per pixel. > Now, I have a monochrome TTL monitor which requires 1 bit per pixel. > I need to convert the 8-bit-pixel image to 1-bit-pixel image and > still be able to distinguish original shapes and lines. > The way I have always seen it done is by taking the (RGB) values and converting them to (YIQ). From this format you take the intensity (I believe that it is "I" component) which should go from 0..255, and use a dithering scheme to approximate the half-tone. The rgb->yiq conversion as well as a simple dithering scheme are both FOLY & VAN DAM _______________________________________________________________________________ Curt Jutzi tektronix!pogo!curtj c/o tektronix (503) 685-3723 del. st. 63-356 P.O. Box 1000 Wilsonville, OR 97070
cram@homxc.UUCP (M.HOWARD) (04/30/87)
In article <3318@pogo.TEK.COM>, curtj@pogo.TEK.COM (Curt Jutzi) writes: > In article <4231@nsc.nsc.com> misha@nsc.nsc.com (Michael Umansky) writes: > >Hello. > >Example: > > I have a bitmap image with 8 bits per pixel. > > Now, I have a monochrome TTL monitor which requires 1 bit per pixel. > > I need to convert the 8-bit-pixel image to 1-bit-pixel image and > > still be able to distinguish original shapes and lines. > > > > The way I have always seen it done is by taking the (RGB) values > and converting them to (YIQ). From this format you take the > intensity (I believe that it is "I" component) which should go > from 0..255, and use a dithering scheme to approximate the > half-tone. Y is the luminance (intensity) component in NTSC color encoding. I (Inphase) and Q (Quadrature) are the chroma components that are encoded on the subcarrier. Y is defined by: Y = .30*Red + .59*Green + .11*Blue Marc W. Howard AT&T Bell Labs, Holmdel NJ ...ihnp4!homxc!cram