US 5,835,160 AGrant
Sampling Rate Conversion Using Digital Differential Analyzers
Issue Date:1998-11-10
•20 Claims
•5 Drawing Sheets
Abstract
Magnification/reduction is achieved by a single FIR filter under the control of a Digital Differential Analyzer (DDA) as would be used to simulate a perfectly straight line on a two-dimensional raster. The single FIR filter combines the processes of interpolation, filter, and decimation. The DDA is programmed with the desired magnification/reduction ratio and provides signals that control shifting of input samples into the FIR filter and selection of FIR coefficients for the FIR filter.
Metadata
Assignee
- Oak Technology, Inc.
Inventors
- Chih-Kang Chen
- Anil Sawe
- David Tran
Application Information
Application Number:US 6957951
Filing Date:1996-08-12
Priority Date:1996-08-12
Art Unit:271
Classifications
IPC:
H04N 701
Field of Search:
348347364581;582;458;459;578;704;240;561;443;562;568;576127-129;130-131724.19;724.2
Patent Drawings (5 sheets)
Description
Statement of Related Applications
This application claims priority from U.S. Provisional application no. 60/020,455, filed Sep. 13, 1995.
Background of the Invention
The present invention relates generally to a system for sampling rate conversion and particularly to a system that resamples by way of interpolation, filtering, and decimation.
During display of a video image sequence, it is often desirable to magnify or reduce an original video frame size or viewing area size on screen. For example, in multimedia systems it is desirable to allow users to change the size of multiple video images from time to time. Magnification and reduction capabilities also find application in picture-in-picture features in consumer televisions.
Often, original video images to be reduced or enlarged are available in digital form, having been received from television or direct satellite broadcast, decoded from MPEG (Moving Picture Expert Group) and JPEG (Joint Photographic Expert Group) standards coded bitstream, or downloaded from CD ROMs. One way to achieve magnification or reduction of digitized video images is to use the techniques of interpolation, linear filtering and decimation of image.
A video system capable of displaying digital video images typically displays a fixed number of pixels per scan line and a fixed number of scan lines per image. The spacing between pixels on a scan line is also fixed. To magnify (or reduce) an image for display is equivalent to increasing (or decreasing) the number of pixels or samples that represent the image so that an increased (or decreased) display area is obtained on the video monitor. Thus magnification or reduction can be implemented as a sampling rate conversion process applied to each video scan line. A general mathematical scheme of sampling rate conversion is disclosed in Ronald E. Crochiere and Lawrence R. Rabiner "Multirate Digital Signal Processing," Prentice-Hall, 1983, the contents of which are herein expressly incorporated by reference for all purposes.
To realize such a sampling rate conversion scheme, the necessary interpolation and decimation factors must first be determined. For an input signal x(n) with sampling period T.sub.in (or sampling frequency F.sub.in) and a resampled output signal y(n) with sampling period T.sub.out (or sampling frequency F.sub.out), the following ratio is formulated, ##EQU1## where L and M are integers and are referred to as the interpolation factor and decimation factor, respectively. For L>M, the output signal y(n) achieves an increased sampling rate and hence an increased number of samples or pixels per scan line. The visible effect is a magnified video image when displayed because more pixels occupy more physical space on screen. For L<M, the opposite effect is obtained.
To implement magnification/reduction in this way, three functional blocks are typically used: an interpolator, a low-pass filter, and finally a decimator. The interpolator first places L-1 zero-valued samples between successive samples in x(n). This operation increases the sampling rate of the signal x(n) by a factor of L and creates L-1 folds of spectral images in the frequency domain of the interpolated signal. The low-pass filter is then employed to filter out these spectral images while retaining the component at the baseband. Finally, the filtered signal is decimated with a factor of M, that is, the decimator outputs every M-th sample to form the output signal y(m). Mathematically, the sampling rate conversion process is expressed as ##EQU2## where {h(n)} represents the low-pass filter.
However, a magnification/reduction system that incorporates a distinct interpolator, low-pass filter, and decimator is complex and costly to implement, requiring extensive VLSI surface area. A P-tap FIR implementation of the low-pass filter, necessarily operates at L times the input sample rate and thus requires L*P operations per input sample. What is needed is a more efficient magnification/reduction scheme suitable for VLSI implementation.
Summary of the Invention
In accordance with the invention, magnification/reduction is achieved by a single FIR filter under the control of a Digital Differential Analyzer (DDA) as would be used to simulate a perfectly straight slope line on a two-dimensional raster. The single FIR filter combines the processes of interpolation, filtering, and decimation. The DDA is programmed with the desired magnification/reduction ratio and provides signals that control shifting of input samples into the FIR filter and selection of FIR coefficients for the FIR filter. In one embodiment, a prefilter and decimator are provided for optionally preprocessing the input so that an overall reduction in computation is provided by magnification within the FIR filter itself.
In one embodiment suitable for use with color digital video systems, a first FIR filter controlled by a first DDA applies magnification/reduction to a luminance signal, Y, and a second FIR controlled by a second DDA applies magnification/reduction to an interleaved combination of two chrominance signals, C.sub.b and C.sub.r. The two chrominance signals are processed separately within the second FIR.
In accordance with one aspect of the invention, a DDA adapted for use in magnification/reduction includes a ratio register, an adder, and a status register. A magnification reduction ratio M/L is stored in the ratio register with L being restricted to being a power of two. This ratio is summed by the adder into the status register after every calculation of an output sample by the FIR filter. The status register thus tracks the output sample position as compared to the input sample position. The necessary width of these registers depends on the expected cumulative error across a single scan line, since the DDA is typically reset upon completion of a particular scan line.
In one particular embodiment, the status register has twelve bits 11! through 0! with 11! being the most significant bit and 0! being the least significant bit with a decimal point implied between bits 10! and 9!. For an interpolation factor, L=4, bits 9-8! are used to select from among four sets of FIR coefficients for the FIR filter for each calculation of an output sample. For other values of L which are powers of two, log.sub.2 L bits beginning with bit 9! would be used for this purpose. For magnification, a toggling of bit 10! is the signal to shift a new sample or pixel into the FIR. For reduction, bits 11-10! indicate how many samples or pixels are to be shifted into the FIR after the calculation of each output sample. This control of the input shifting achieves the necessary interpolation by L. Decimation by M is achieved since the output sample position is incremented by the magnification/reduction ratio.
The invention will be better understood by reference to the following detailed description in connection with the accompanying drawings.
Brief Description of the Drawings
FIG. 1 is a block diagram of the sampling rate conversion system according to one embodiment of the present invention.
FIG. 2 is a detailed diagram of a DDA controller responsible for controlling other functional blocks in the sampling rate conversion system of FIG. 1 in accordance with one embodiment of the present invention.
FIG. 3 is a detailed diagram of a luminance filter for resampling a luminance signal in accordance with one embodiment of the present invention.
FIG. 4 is a detailed diagram of a chrominance filter for resampling chrominance signals in accordance with one embodiment of the present invention.
FIG. 5 is a detailed diagram of a status register within the DDA controller of FIG. 2 indicating the significance of the various bits.
Description of the Specific Embodiments
The preferred embodiment of the sampling rate conversion system of the present invention is directed toward processing of video image signals in order to achieve an image magnification or reduction effect. Sampling rate conversion could be achieved in other contexts as well in accordance with the present invention.
FIG. 1 is a block diagram of a sampling rate conversion system 1 according to one embodiment of the present invention. There are two inputs 10 and 11 to the system, one for a luminance signal component Y (or Y pixel) and one for two chrominance signal components Cb and Cr (or simply Cb pixel and Cr pixel). At the chrominance input 11, the Cb and Cr pixels are interleaved and together have a sampling rate the same as the Y pixel at the luminance input 10.
The luminance signal and interleaved chrominance signal are resampled separately. Each signal is fed through a buffer 12, a switch 13, then depending on the setting of switch 13 through a prefilter 16 and a decimator-by-K 17 or alternatively directly to luminance filter 19 or chrominance filter 20. The FIR coefficients of luminance filter 19 and chrominance filter 20 are stored in FIR coefficient storage 18. The luminance signal is resampled within luminance filter 19 under the control of a luminance DDA (Digital Differential Analyzer) 21. The chrominance signal is resampled within chrominance filter 20 under the control of a chrominance DDA 21.
Buffers 12 may be implemented using either RAMs (random-access-memory) or FIFO (first-in-first-out) memories. The switches 13 enable activation of a preprocessing stage that includes prefilter 16 and decimator-by-K 17. Prefilter 16 is an FIR low-pass filter whose coefficients are selected in accordance with factor K to eliminate spectral aliasing at the output of decimator-by-K 17 by reducing the bandwidth of the input signal by a factor of K. By including these blocks in the signal path, image reduction can be achieved even though luminance filter 19 and chrominance filter 20 operate to perform image magnification.
Luminance filter 19 and chrominance filter 20 are responsible for the operations of interpolation, FIR filtering, and decimation inherent in resampling. Luminance filter 19 operates on the Y signal and chrominance filter 20 operates on both the Cb and Cr signals. Since each of the Cb and Cr signals have an effective sample rate that is half that of the Y signal, chrominance filter 20, clocked at the same speed as luminance filter 19, alternately processes the Cb and CR sample streams in a time-multiplexed fashion.
The FIR coefficients used by the luminance and chrominance filters 19 and 20 are stored in FIR coefficient storage device 18. Storage device 18 can be implemented using RAM or similar electronic devices. As will be explained below, the FIR coefficients are grouped into sets within storage device 18 with each set being independently selectable by the luminance DDA and chrominance DDA controllers 21. The resampled luminance and chrominance signals exit from the output of filters 19 and 20 respectively.
The operation of DDA controllers 21 is critical to achieving the resampling operation within luminance filter 19 and chrominance filter 20. FIG. 2 is a detailed diagram of one of DDA controllers 21. An input 30 is used to program a desired magnification/reduction ratio. This ratio is stored in a ratio register 31. In the preferred embodiment, the ratio register is eleven bits wide, 10..0!, where bit 10! denotes the MSB and bit 0! denotes the LSB with a decimal point being placed between bits 10! and 9!.
The magnification/reduction ratio can be expressed as: ##EQU3## This ratio is computed and rounded off to a 10-bit binary fraction plus 1-bit integer number prior to storage in ratio register 31. The following cases are possible:
Ratio<1: sampling rate increase or image magnification
Ratio=1: no change to sampling rate or image copy
Ratio>1: sampling rate decrease or image reduction
For the preferred embodiment, Ratio<2 is constrained to be less than 2 due to the configuration of ratio register 31.
The output of ratio register 31 represents a first input to a 12-bit adder 32. The output of 12-bit adder 32 is stored in a 12-bit status register 33. The output of status register 33 is an input to a decode logic unit 35 for control signal generation and at the same time it is connected to the other input of the 12-bit adder 32 through a feedback path 34. Decode logic unit 35 decodes the bit information from the status register 33 to generate two signals. One signal selects a particular group of FIR coefficients for retrieval to the filter controlled by the DDA. The other signal controls shifting of pixels into the filter.
Both the 12-bit adder 32 and 12-bit status register 33 have bit fields labeled 11..0! with bits being aligned for "add" operation by 12-bit adder 32. A decimal point is implied between bit 10! and bit 9! for adder 32 and status register 33.
The width of registers 31 and 33 and adder 32 is chosen so that rounding error accumulated in status register 33 does not effect resampling operation. In the preferred embodiment, status register 33 is cleared after every scan line, thus limiting accumulation of error. With a maximum of 720 pixels per input scan line and a maximum of 1,024 pixels per output scan line, the 11 bit width of ratio register 31 and 12 bit width of status register 33, which give a maximum accumulation error of (1,024*2.sup.-11)*T.sub.out, have been found to be sufficient.
FIG. 3 is a detailed diagram of luminance filter 19 for resampling a luminance signal in accordance with one embodiment of the present invention. Eight FIR coefficients are loaded through an input 40 to 4 pairs of coefficient registers 41, labeled C0 through C7. The particular group of FIR coefficients loaded will depend on the output of DDA controller 21. The luminance samples or pixels from buffer 12 are loaded through an input 43 to eight shift registers 44, labeled Y.sub.0 through Y.sub.7. The eight shift registers 44 are connected in a cascaded fashion, that is, the output of Y.sub.7 is connected to the input of Y.sub.6 and so on. Each shift register preferably comprises an 8-bit flip-flop. The outputs of each pair of registers 41 and the corresponding two shift registers are connected to the inputs of a multiplier 42. Thus, there are four multipliers 42. The outputs of the four multipliers are fed to a 5-input adder 45. The fifth input of the 5-input adder is fed from its own output 46. Output of 5-input adder 45 also serves as the output for the resampled luminance signal. The luminance filter completes a sum of eight multiply-and-accumulates, e.g. an 8-point convolution ##EQU4## and send the result to output 46 at a throughput of one sample every two cycles. The loading of pixels into shift register 44 via input 43 and selection of coefficients for loading into registers 41 via input 40 is controlled by luminance DDA controller 21.
The internal operation of chrominance filter 20 is similar to that of luminance filter 19 except it computes separate 8-point convolutions for chrominance signals Cb and Cr. FIG. 4 is a detailed diagram of chrominance filter 20 for resampling chrominance signals in accordance with one embodiment of the present invention. Four pairs of coefficient registers 51, labeled B0 through B7, are loaded with coefficients from FIR coefficient storage 18. Unlike luminance filter 19, chrominance filter 20 contains an additional set of 8 shift registers to handle Cb and Cr separately. Chrominance Cb pixels are loaded via an input 53 to a shift register set 54, labeled U0 through U.sub.7 and Cr pixels are loaded from input 55 into a shift register set 56, labeled V.sub.0 through V.sub.7. Four multipliers 52 and a 5-input adder 57 are shared for computing the output Cb and Cr signals, that is, the two 8-point convolutions ##EQU5## for chrominance Cb signal and ##EQU6## for chrominance Cr signal. As with luminance filter 19, a throughput of two cycles is maintained for performing both convolutions. The resulting Cb and Cr output samples are computed alternately and interleaved to an output 58.
In operation, DDA controllers 21 control selection of FIR coefficients and input of pixels for luminance filter 19 and chrominance filter 20. If the distance between successive input samples or pixels on the scan line is understood to be unity, the contents of status register 33 can be understood to represent a position of the current output sample. The value of the bits to the right of the decimal point indicate the distance between the current output pixel and the input pixel immediately to the left. For the first output pixel, status register 33 contains zero, indicating the first input pixel is copied to the first output pixel. For each succeeding output pixel, status register 33 is incremented once with the contents of ratio register 31. For the case of image magnification, the contents of ratio register 31 are less than one. For the case of image reduction, the contents of ratio register 31 are greater than one but less than two.
Thus, the timing of each DDA controller is synchronized to the generation of new output pixels. After a new output pixel is generated, the number of pixels, if any to be shifted into the filter must be determined. For the case of image magnification, a toggling of the LSB to the left of the decimal point indicates that a single pixel is to be shifted in. In the preferred embodiment, this refers to bit 10!.
For the case of image reduction, the bits to the left of the decimal point indicate the number of pixels to be shifted in to the filter after calculation of an output pixel. These bits to the left of the decimal point are reset before every update to the status register. In the preferred embodiment, these are bits 11..10!.
The proper FIR coefficients to be applied will depend on the alignment of the output pixel to be calculated relative to the input pixels. Lowpass filtering is implicitly applied to the interpolated input stream, that is the input pixels with L-1 zeroes interspersed between each input pixel to eliminate spectral folding. However, coefficients that currently align with zeroes in this interpolated input stream are not needed and are deleted from the coefficient set for computational efficiency. The coefficients that are needed thus will vary depending on the alignment of the output sample to be calculated in relation to this interpolated input stream. Since there are L possible alignments, L coefficient sets are required.
The needed coefficient set is identified by the log.sub.2 L bits to the right of the decimal point in the status register. The DDA controller addresses FIR coefficient storage 18 to provide these coefficients to the appropriate filter prior to the calculation of each output sample. In the preferred embodiment, L=4 and bits 9..8! identify the coefficient set to be selected. FIG. 5 is a detailed diagram of status register 33 indicating the significance of the various bits. The operation of the luminance DDA controller is similar to that of the chrominance DDA controller. The chrominance DDA controller runs at half speed since the input sample rates for the Cb and Cr signals are half that for the Y signal.
In an alternate mode that can be selected by use of switch 13, image reduction is processed by the luminance and chrominance filters 19 and 20 and their associated DDA controllers 21 as image magnification. In this alternate mode, prefilter 16 and decimator-by-K 17 are included in the input path for the luminance and chrominance signals. Prefilter 16 is preferably a 3-tap FIR filter and decimator 17 preferably has K=2 sending every other pixel to the luminance and chrominance filters 19 and 20. Thus, the sampling rate into the luminance and chrominance filters is reduced by a factor of 2 from the inputs 10 and 11. As the result, the overall reduction ratio becomes ##EQU7## Since the input sampling rate is thus limited to be no greater than twice the output sampling rate, Ratio for this mode of operation is less than unity. When this mode is used, the luminance and chrominance filters always perform sampling rate upconversion whether image magnification or reduction is required. The advantage of this is that the filters only need to operate in magnification mode, eliminating the need for shifting in two input pixels for one output pixel during image reduction. Prefilter 17 may be modified to have more taps in order to minimize spectral aliasing.
Thus, the present invention permits resampling within a single FIR filter without the need for a separate interpolator and decimator. Thus, needed VLSI surface area is minimized while maintaining computational efficiency.
While the above is a complete description of the preferred embodiments of the invention, various alternatives, modifications, and equivalents may be used. It should be evident that the present invention is equally applicable by making appropriate modifications to the embodiments described above. Therefore, the above description should not be taken as limiting the scope of the invention which is defined by the metes and bounds of the appended claims.
Claims
What is claimed is:
1. A sampling rate conversion system comprising: an FIR filter that receives a discrete signal to be resampled via a first input and FIR coefficient data via a second input and provides a filtered output; an electronic memory device coupled to said FIR filter that stores said FIR coefficient data; and a DDA controller coupled to said FIR filter and said electronic memory device that receives a desired magnification/reduction ratio, M/L, wherein L and M are integers, and that coordinates shifting of said discrete signal into said FIR filter with selection of coefficients from said electronic memory device so that said filter output achieves said desired magnification/reduction ratio, said DDA controller including a ratio register that stores said magnification/reduction ratio and provides said ratio as an output, an adder that adds a first adder input to a second adder input to provide an adder output, wherein said first adder input is coupled to said output of said ratio register; a status register that receives said adder output as an input and provides said second adder input as an output, wherein said ratio register is summed into said status register by said adder after every calculation by said FIR filter of a sample of said filtered output; and a decoder circuit that receives said output of said status register as an input and provides 1) an input shift control signal to said FIR filter to control shifting of input samples into said FIR filter, and 2) a coefficient selection signal to said electronic memory device to select a group of FIR coefficients to be loaded into said FIR filter, wherein a current value of said status register represents an alignment between said a current output pixel and a nearest input pixel to the left.
2. The sampling rate conversion system of claim 1 wherein said coefficient selection signal selects from among L sets of coefficients stored in said electronic memory device depending on a value of log.sub.2 L preselected bits to the right of an implied decimal point in said status register.
3. The sampling rate conversion system of claim 1 wherein for a sampling rate increase said input shift control signal operates to shift a pixel into said FIR filter when a least significant bit to the left of an implied decimal point of said status register toggles.
4. The sampling rate conversion system of claim 1 wherein for a sampling rate decrease said input shift control signal operates to shift as many pixels as are indicated by bits to the left of an implied decimal point of said status register.
5. The sampling rate conversion system of claim 1 wherein said status register has 12 bits, 0-11 with being the least significant bit, 11 being the most significant bit with an implied decimal point between bits 10 and 9, said predetermined bits consisting of log.sub.2 L contiguous bits with 9 being the highest of said predetermined bits.
6. The sampling rate conversion system of claim 1 further comprising: a decimator having an output coupled to said input of said FIR filter; and a prefilter having an output coupled to an input of said decimator.
7. The sampling rate conversion system of claim 1 wherein said discrete signal comprises a luminance signal of a digital video system.
8. The sampling rate conversion system of claim 1 wherein said discrete signal comprises interleaved first and second chrominance signals of a digital video system and said FIR filter processes said first and second chrominance signals separately.
9. A sampling rate conversion system comprising: an FIR filter that receives a discrete signal to be resampled via a first input and FIR coefficient data via a second input and provides a filtered output; an electronic memory device coupled to said FIR filter that stores said FIR coefficient data; and a DDA controller coupled to said FIR filter and said electronic memory, said DDA controller including a ratio register that stores said magnification/reduction ratio and provides said ratio as an output; an adder that adds a first adder input to a second adder input to provide an adder output, wherein said first adder input is coupled to said output of said ratio register; a status register that receives said adder output as an input and provides said second adder input as an output, wherein said ratio register is summed into said status register by said adder after every calculation by said FIR filter of a sample of said filtered output; and a decoder circuit that receives said output of said status register as an input and provides, wherein a current value of said status register represents an alignment between said a current output pixel and a nearest input pixel to the left.
10. The sampling rate conversion system of claim 9 wherein said status register has 12 bits, 0-11 with 0 being the least significant bit, 11 being the most significant bit with an implied decimal point between bits 10 and 9, said predetermined bits consisting of log.sub.2 L contiguous bits with 9 being the highest of said predetermined bits.
11. The sampling rate conversion system of claim 9 further comprising a decimator having an output coupled to said input of said FIR filter; and a prefilter having an output coupled to an input of said decimator.
12. The sampling rate conversion system of claim 9 wherein said discrete signal comprises a luminance signal of a digital video system.
13. The sampling rate conversion system of claim 10 wherein said decoder circuit that receives said output of said status register as an input and provides an input shift control signal to said FIR filter to control shifting of input samples into said FIR filter, and a coefficient selection signal to said electronic memory device to select a group of FIR coefficients to be loaded into said FIR filter, wherein a current value of said status register represents an alignment between said a current output pixel and a nearest input pixel to the left wherein said coefficient selection signal selects from among L sets of coefficients stored in said electronic memory device depending on a value of log.sub.2 L preselected bits to the right of an implied decimal point in said status register.
14. The sampling rate conversion system of claim 9 wherein for a sampling rate increase said input shift control signal operates to shift a pixel into said FIR filter when a least significant bit to the left of an implied decimal point of said status register toggles.
15. The sampling rate conversion system of claim 9 wherein for a sampling rate decrease said input shift control signal operates to shift as many pixels as are indicated by bits to the left of an implied decimal point of said status register.
16. The sampling rate conversion system of claim 9 wherein said discrete signal comprises interleaved first and second chrominance signals of a digital video system and said FIR filter processes said first and second chrominance signals separately.
17. A sampling rate conversion system comprising: an FIR filter that receives a discrete signal comprising a luminance signal and interleaved first and second chrominance signals of a digital video system; an electronic memory device coupled to said FIR filter that stores said FIR coefficient data, with said FIR filter processing said first and second chrominance signals separately, to be resampled via a first input and FIR coefficient data via a second input and provides a filtered output; and a DDA controller coupled to said FIR filter and said electronic memory, said DDA controller including a ratio register that stores said magnification/reduction ratio and provides said ratio as an output; an adder that adds a first adder input to a second adder input to provide an adder output, wherein said first adder input is coupled to said output of said ratio register; a status register that receives said adder output as an input and provides said second adder input as an output, wherein said ratio register is summed into said status register by said adder after every calculation by said FIR filter of a sample of said filtered output; and a decoder circuit that receives said output of said status register as an input and provides, wherein a current value of said status register represents an alignment between said a current output pixel and a nearest input pixel to the left, wherein said status register has 12 bits, 0-11 with 0 being the least significant bit, 11 being the most significant bit with an implied decimal point between bits 10 and 9, said predetermined bits consisting of log.sub.2 L contiguous bits with 9 being the highest of said predetermined bits.
18. The sampling rate conversion system of claim 17 wherein said decoder circuit that receives said output of said status register as an input and provides an input shift control signal to said FIR filter to control shifting of input samples into said FIR filter, and a coefficient selection signal to said electronic memory device to select a group of FIR coefficients to be loaded into said FIR filter, wherein a current value of said status register represents an alignment between said a current output pixel and a nearest input pixel to the left wherein said coefficient selection signal selects from among L sets of coefficients stored in said electronic memory device depending on a value of log.sub.2 L preselected bits to the right of an implied decimal point in said status register.
19. The sampling rate conversion system of claim 18 wherein for a sampling rate increase said input shift control signal operates to shift a pixel into said FIR filter when a least significant bit to the left of an implied decimal point of said status register toggles.
20. The sampling rate conversion system of claim 19 further comprising a decimator having an output coupled to said input of said FIR filter; and a prefilter having an output coupled to an input of said decimator.
Patent Citations (7)
Non-Patent Literature (1)
- James D. Foley et al., "Computer Graphics, Principles and Practise," Second Edition, Addison-Wesley Publishing Co., Basic Raster Graphics Algorithms for Drawing 2D Primitives, pp. 72 to pp. 74.