8-bit Computer Graphic Systems | My Assignment Tutor

Optimized Algorithms for Displaying 16-bit Gray Scale Imageson 8-bit Computer Graphic SystemsThurman Gillespy IIIMost personal computers contain 8-bit graphic displayhardware, whereas most medical gray scale imagesare stored at 16-bit per pixel integers. To displaymedical gray scale images on such computers, the16-bit image data must be remapped into 8-bit grayscale images. This report presents the algorithms andcomputer code that allow very rapid 16-bit to 8-bitimage data transformation. These algorithms are helpfui in allowing personal computers with at least theperformance of a Macintosh II (Apple Computer, Cupertino, CAl computer to function as Iow-end picturearchiving communication systems or personal workstations.Copyright 9 1993by W.B. Saunders CompanyKEY WORDS: window width, window level, personalcomputer, Macintosh, workstation.M OST represented DIGITAL as radiographic 16-bit (2 byte) images integers areper pixel element. The actual dynamic range ofthe image data usually varŸ from 9 to 12 bits,depending on the imaging modality. When suchimages ate displayed on imaging consoles ofpicture archiving communication systems(PACS)/teleradiology workstations, a windowand level control is usually provided to allowvisualization of the full-image dataset. Thisfunction is usually implemented with specialgraphic hardware that allows window and levelsettings to be applied in real time. However,most personal computers and some low-endPACS/teleradiology workstations have standard 8-bit graphic systems. To display 16-bitimages on 8-bit graphic systems, at least twosteps are required: First, the 16-bit image datamust be remapped to an 8-bit representationusing user selected window and level settings.Second, the 8-bit data must be translated intodifferent colors of gray scales (most commonlyin hardware using a lookup table) before beingprojected onto the display monitor. The firststep is performed in software and is usuallycomputationally expensive. The second step isperformed quite rapidly, usually in real time.This report presents algorithms and C programming Ianguage examples that optimize the remapping of l£ image data into an 8-bitcolor/gray scale representation.DIRECT CALCULATION TRANSFORMATIONThe 16-bit to 8-bit transformation requiresthat an 8-bit value be substituted for each 16-bitvalue in the image dataset (Fig 1). Typically thisis n o t a one to one transformation; often imagevalues less than a certain number are clipped toblack (in gray scale images), and images valuesgreater than a certain number are clipped towhite. Two parameters are usually chosen thatdetermine the slope and end points of thistransformation function: the window and level(also known as the window width and windowlevel). From Fig 1, the following definitions arederived:window = x2 – xi (Equation 1)level = xl + (window/2) (Equation 2)xl = level – (window/2) (Equation 3)The equation for a line on an x,y-coordinatesystem is defined as:y = (m * x) + b (Equation 4)For the present discussion, y is the 8-bit grayscale/color value of interest, x is the known16-bit image data value, m is the slope of theline, and bis the y-intercept. Thus from Equation 4 the following formulas can be derived:rn = Av/ Ax (Equation 5)rn = GRAYSCALES /window (Equation 6)where GRAYSCALES is the difference betweenthe lowest and highest gray scale value (usually255 Gy).Furthermore, ifx = xl, then y = 0 (Fig 1).Thus, substituting for Equation 4 we find thefollowing:0 = (m * xl) + b (Equation 7)b = – ( m * xl) (Equation 8)b = – (GRA YSCALES/window)9xl (substituting Equation 6) (Equation 9)From the Department of Radiology, University of Washington, Seattle, WA.Address reprint requests to Thurman Gillespy HI, MD,Department of Radiotogy, SB-05, University of Washington,Seatth’, WA 98195.Copyright 9 1993 by WB. Saunders Company0897-1889/93/0601-0003503.00/0JournalofD/gitallmaging, Vol 6, No 1 (February), 1993: pp 25-29 2526 THURMAN GILLESPYIIIThus, given the values for window, level, andGRAYSCALES, the 16-bit data can be remapped into 8-bit data as follows:[Code 1]#deline RSIZE /* size of image data, in pixels, definedas rows x columns of the image matrix* unsigned shortsrc/RSIZE]; /* array of l £imagedata*/unsigned charimg[RSIZE]; /* arrav of 8-bitremapped image data */i, window, level, temp;shortshortfloatb;/* y-intercept, as defined Oz Eq 8 */m ; / * slope, as defined in Eq 9*/ lo; 0 = 0; i < RSlZE; i+ +) It e m p = ( m * s r c [ i ] ) +b; / * y = ( m . x ) + b * /if (temp > 255 )temp = 255 ;else ir (temp < O)tenW = O;img[i] = temp;Although many refinements on the above algorithm are possible, this approach is unavoidablycomputationally expensive when performed onthe data sets that are commonly encountered inmedical imaging.LOOKUP TABLE TRANSFORMATIONA better approach is to consider the x-axis ofFig 1 to representan array, where each positionon the x-axis is an element of the array, and they-value (color/gray scale value) is the value ofthat element (Fig 2). The calculation of this250u~ D~>200 150g~100OO0x~/500// IJX21000 1500 200016-bit Image Data2500Fig 1, The transformation of 16-bit image data into 8-bitgray scale values.Fig 2. The lut[] array. Compare X1 and)(2 with Fig 1.array is as follows:[Code 2]#define RRANGE / * the absohae difference betweenthe smallest and largest imagedata vah~e */unsigned char lut [RRANGE];for (i = O. i < RRANGE; i + + ) {temp = (en * i) + b;if (temp > 255 )tetnp = 255 ;etse ir (temp < O)tenW = O:lutli] = temp;Further refinements in the calculation of lut[]are possible, but are not essential to the presentdiscussion. The array lut[] now contains ahordered set of integers (cast as unsigned chars)from (and usually including) black (0) to white(255) (Fig 2). The 16-bit to 8-bit transformationcan now be performed by using the 16-bit imagedata value of each pixel as the index for lut[] toobtain the 8-bit value of interest, as fotlows:[Code 3]for (i = O; i < RS1ZE; i+ +)img[i] = lut[sre[i]];This is a common programming algorithm knownas a lookup rabie. Code 3 can profitably berewritten using pointers a n d a do… whiIe loopas in the following code:[Code 4] unsigned citarunsigned shortt = RStZE;*ip = intg;*sp = src; do {*ip++ = *(lut + *sp++):} while (–i);ALGORtTFIMS FOR 16-BIT GRAY SCALE IMAGE$ 27This algorithm is very fast because the onlycalculations required are a counter decrement,twa poinler address increments, and memorytransfers, A furlher slight improvement is possibte by “‘uncoi[[ng” the Ioop:[Code.SIi = RSIZE/16:*lp++ = *(lut + *so++); *ii)++ = *(lut + *~p++);*lp++ = *(lut + *si)++); *ii)++ = *(lut + *so++);*lp++ = *(lut + *st)++): *lp++ = *(lut + *sp++);*lp++ = *(lut + *sp++): *lp++ = *(h~t + *~p++);*lp++ = *(lut + *sp++); *ip++ = *(lut + *sp++);*ip++ = *(h~t + *sp++); *ip++ = *(lut + *sp++);* l p + + = *(lut + *sp++); ~’ip++ = *(lut + *sp++);*lp++ = *(lut + *sp++); *ip++ = *(tut + *sp++):}w~ile(- -i).FURTHER OPTIMIZATIONWhereas the above algorithm is a significantimprovement, ir still requires up to RRANGEnumber of floating point and integer calculations to calculate a new lut [] for a new windowand/or level setting. These calculations are apotential performance bottleneck if nearly instantaneous window and leve[ adjustments aredesired. For fu~ther optimization, consider thefollowing proposilions to be true: (t) Continuous adlustment of the window setting is notrequired, le, preset window settings ate clinicafly acceptable (and in fact have been used onmany clinical systems in the past). (2) However,continuous of nearly continuous adjustment ofthe level setting is desirable. (3) The maximumrange of level settings required is the differencebetween those settings necessary to convert theimage from complete black to complete white(this range is not always needed, but is themaximum Iba! woulcl be required). (4) Furlhermore, consider that f o r a given window, achange in the level setting only “shifts” thevalues in lut [] to different positions within thearray (Fig 3).The following data structure is then suggested:/Code 61unsigned char baseL UT[ ];This array has 3 regions (Fig 4): (1) The firstregion is RRANGE elements long. ElementbaseLUT [RRANGE – 1], hereafter labeled W1,is fixed. For computed tomographie ~mages,~,o / /:~ a0o> 9I 1 / .~ ‘ L _ ~ Level ~Hi~ #’2 J10091soi00 500 1000 1500 2000 250016-bit Image DataFi 9 3. Different levelsettings.RJ91 can be set to 4,096 (12-bit dynamicrange). (2) The region from W1 to W2 is as largeas the current window setting; it contains anordered set of integers that progresses fromblack to white. It is initially set to MAX_WIND_SIZE (the largest window setting possible) elements long. Whereas the array position W1 isfixed, W2 will vary depending on the size of thecurrent window. (3) The region from W2 toEND is at least RRANGE elements long, and atmost RRANGE + MAX_W1ND_SIZE elementslong (ie, when wtndow = 0).The baseLUT[] array performs the sametransformation function as lut[] above, but isconstructed and initia[ized differently. At prograto startup, baseLUT[] is allocated (2*RRANGE) + MAX_WIND_SIZE elements. Theelements from baseLUT[O] to baseLUT-[W1 – 1] are set to black (0), and the elementsfrom baseLUT[W1] to baseLUT[END] ate setto white (255).F~g4. The barseeLU7″[]arrey,28 THURMAN GILLESPY II[Next, an array of unsigned char arrays isinitialized using predefined window settings,where each subarray is defined from a predefined list ofwindow settings. However, unlikelut[] above, each array contains at most onewhite and black gray scale value: the “flat” orclipped portions of the transformation curve onFig 1 are not included.[Code 71#define NUM_OF_WINDS /* number of windowsettings * /short rnyWinds [NUM OF_WINDS]={100, 200, . . . . 2000};/* arrav of definedwindow settings */unsigned char * myWind Array[NUM_OF_WINDS];/* array of unsigned char arrays, defined ~ornmyWinds[ ] */for (i = O;i < NUM_OF WINDS; i+ +)myWindArray[i] = makeLUT(myWinds[i]);makeLUTO is a function defined as follows:[Code 8]unsigned char * makeLUT(short); /* protoO’pe */unsigned char * rnakeL UT(short window){ shortfloati;m = – (GRA YSCA LES / window);/* see Eq. £ * /lut[window/:unsigned char /* note that b = 0 */i = O;while (i < window)lut[i + +/ = rn * i:return (lut);Finally, a global pointer is used to set thecurrentlevel setting (Fig 5):[Code91unsigned char *gLevel;gLevell ~ l i i[o1 Wl w2 ZNDFig 5, ThegLeve/pointer,Table 1. Algorithm Performance MacintoshCentra]Computer ModelIIr[ci, no cacheIlci, 32k cacheQuadra 700ProcessingUnit16 MHz 6802025 MHz 6803025 MHz 6803025 MHz 68040Time (s)0.510.410.310.17% Time67656350 NOTE: Includes total time to change level control with mouse,calculate new level setting, remap new 8-bit gray scale imagefrom 16-bit image data, update display. Times recorded usingprofiler option in Think C. The “uncoiled'” version of thealgorithm was used (code 5), which was 10% to 20% faster thanthe standard version (code 4), depending on specific Macintoshconfiguration.*The percent of the total time spent in the subroutineperforming the 16-bit to 8 bit transformation.Once a window setting is selected, the corresponding unsigned char array in myWindArr[] iscopied to baseLUT[], starting at position W1.To set or change the level setting, the gLevelpointer is set to the appropriate position withinbaseLUT[].[Code 10]xi = tevel – (window/2);gLevel = &baseL UT[14/1 – xl];The design of baseLUT[] allows continuouslevel settings with only a change to the gLevelpointer address. Furthermore, the array designallows level settings to be selected that set theimage from complete black (&baseLUT[O])tocomplete white (&baseLUT[W1 + window]).This algorithm also permits the use of nonlinearlookup tables with no performance penalty.IMPLEMENTATIONUsing the algoritbms above, window and leveladjustments might be performed as the following loop:(1) Store the old selector position (mouse,trackball, dial, etc).(2) Get the current selector position.(3) Calculate the difference between the oldand new selector positions.(4) If the difference is not zero, use thedifference to calculate a new window and/orlevel setting, else repeat loop.(5) If the window setting has changed, copythe appropriate array from myWindArray[] tobaseLUT[]. If the level has changed, calculatexl, then change the address of the gLevelpointer witbin baseLUT[].ALGORITHMS FOR 16-BIT GRAY SCALE IMAGES 29(6) Remap the 16-bit data into 8-bit datausing the portion of baseLUT[] pointed to bygLevel.(7) Update the displayed image using therevised 8-bit data.The optimized algorithms described abovehave been implemented in a sample applicationon the Macintosh (Apple Computer, Cupertino,CA) platform using Think C 5.02 (SymantecCorp, Cupertino, CA). On a Macintosh II classcomputer, the algorithms allow very rapid window and level adjustments (Table 1). On aMacintosh Quadra computer, the window andlevel adjustments are performed almost instantaneously. As expected, algorithm performanceis strongly influenced by microprocessor performance.CONCLUStONSThe algorithms described above allow nearlyreal time window and level adjustment of 16-bitgray scale images on computer systems thatcontain standard 8-bit graphic hardware. Therefore, personal computers with at least the performance of a Macintosh II computer may performadequately as personal/low-end PACS workstations without the additional expense of specialgraphic hardware.


Leave a Reply

Your email address will not be published.