Real-time image resizing and rotation with line buffers

[0002] The present invention generally relates to digital image processing, and more particularly to resizing and rotation of digital images.

[0003] An example programmable logic device (PLD) is the field programmable gate array (FPGA), first introduced by Xilinx, Inc., in 1985. PLDs such as FPGAs are becoming increasingly popular for use in electronics systems. For example, multimedia communications systems employ FPGAs in large measure for their re-programmability. In general, the use of FPGAs continues to grow at a rapid rate because they permit relatively short design cycles, reduce costs through logic consolidation, and offer flexibility in their re-programmability.

[0004] Advances in semiconductor process technology are delivering FPGAs having logic densities in the range of a million system gates and having operating speeds in excess of 200 MHz. These powerful devices are capable of and have been used to implement digital signal processing (DSP) algorithms which are inherently parallel and normally require multiple DSP microprocessors in order to accommodate the high data rates. It is feasible to implement such algorithms on a single FPGA because such devices offer a programmable architecture.

[0005] Image resizing typically involves fractional re-sampling, which can lead to prohibitively large implementations and result in compromises in range and resolution. Polyphase decimators and polyphase interpolators are generally employed for fractional re-sampling, depending on whether an image is being reduced (decimator) or enlarged (interpolator).

[0006] In many two-dimensional resizing implementations, an intermediate buffer is disposed between horizontal and vertical filter elements. The structure has considerable memory requirements because the size of the intermediate buffer is doubled relative to the image size to support continuous operation.

[0007] Image rotation also involves re-sampling, but is performed on non-integer points. For example, with a center point of an image defined, a single parameter • specifies the transformation. The equations below provide the coordinate transformation in terms of rotation of the coordinate axis.

[0008] S_x=D_xcos (•)+D_ysin (•)

[0009] S_y=−D_xsin (•)+Dcos (•)

[0010] where S and D represent source and destination coordinates, respectively.

[0011] In an implementation having linear addressing through the destination image, the first step in the rotation algorithm is computation of the source values S_xand S_y. From these values, the neighborhood of pixels is known for the filter operation. The location of the destination pixels in the source pixel matrix also gives the weighting factors for bilinear or bicubic interpolation. The pixel value is then calculated with the weighting factors and pixel values in the neighborhood. The process repeats by incrementing the D_xvalue and continuing in a raster out format. One drawback of this process is the non-uniform addressing of the source pixels. Essentially, the input memory design must have four times the bandwidth (or 16 for bicubic) because there is no sharing of source pixels between destination pixel operations.

[0012] Given the speed and flexibility of FPGAs, it would be desirable to implement image resize and rotation circuitry on an FPGA. However, memory bandwidth and frame latency issues must be factored into any solution.

[0013] The invention provides circuit arrangements and methods for real-time image resizing and image rotation. In various embodiments, line buffers are used for storage of lines of pixel values for both resizing and rotation. A first one of the line buffers receives input pixel values, and the line buffers are coupled in a chain such that line buffer i receives pixel values from line buffer i−1. The lines of pixel values are moved from line buffer i to line buffer i+1 as the pixel values are processed for resizing or rotation.

[0014] The line buffers offer improved performance in real-time image resizing by eliminating the need to re-read sample values from a memory. The line buffers further eliminate the need for the added memory of a double buffering approach and introduce no frame latency. For image rotation, the line buffers allows the source pixels to be shared and linearly addressed in generating destination pixels. This greatly reduces the memory requirements for a given bandwidth requirement.

[0015] It will be appreciated that various other embodiments are set forth in the Detailed Description and Claims which follow.

[0016] Various aspects and advantages of the invention will become apparent upon review of the following detailed description and upon reference to the drawings in which:

[0017] FIG. 1 is a functional block diagram of a circuit arrangement for real-time resizing of a digital image in accordance with one embodiment of the invention;

[0018] FIG. 2 is a functional block diagram of an example line buffer;

[0019] FIG. 3 is a functional block diagram of an example vertical filter component;

[0020] FIG. 4 is a functional block diagram of an example horizontal filter component; and

[0021] FIG. 5 is a functional block diagram of a circuit arrangement for real-time rotation of a digital image in accordance with one embodiment of the invention.

[0022] FIG. 1 is a functional block diagram of a circuit arrangement for real-time resizing of a digital image in accordance with one embodiment of the invention. Circuit arrangement 100 inputs a single row and performs the vertical filtering with the “Q” sequencer changing on a row basis. Depending on the vertical down-sample rate, throw-away lines are possible. Similarly, repeated lines are needed when up-sampling.

[0023] Resizing circuitry 100 includes multiple line buffers 102-1-102-n for buffering lines of image data, with output values from each of the line buffers being input to vertical filter 104. Each line buffer stores one row of sample (pixel) values for an image. The output value from the vertical filter is input to horizontal filter 106. Resized image samples are output from the horizontal filter. Resize control logic 107 controls sequencing of input sample values to the line buffers, reading sample values from the line buffers, controlling operation of the vertical and horizontal filters, and indicating when resized image samples are valid.

[0024] Corresponding sample values are read in parallel from the line buffers 102-1-102-n and input to vertical filter 104. When a value from a line buffer is read and input to vertical filter 104, the same value is input and written to the appropriate location in the next line buffer in the chain. For example, when the first value is read from line buffer 102-1 and input to the vertical filter on line 110, the same first value is also written to the corresponding position in line buffer 102-2, which at the same time is providing a first value on line 112 to the vertical filter and to line buffer 102-3.

[0025] By shifting a row of image samples from one line buffer to the next, the structure offers improved performance in real-time image resizing by eliminating the need to re-read sample values from memory. In addition, the line buffers eliminate the need for the added memory of the double buffering approach. Furthermore, there is no frame latency in the current arrangement.

[0026] In one embodiment, vertical filter 104 and horizontal filter 106 are implemented using conventional logic. For example, the vertical filter includes an array of multipliers (not shown), with each multiplier receiving an input sample value input from one of the line buffers and a coefficient. The output values from the multipliers are input to an adder tree (not shown). The output data from the vertical filter are input to the horizontal filter, which includes a series of delay elements, an array of multipliers, and an adder tree. Those skilled in the art will appreciate that in other embodiments, vertical and horizontal filters can be specially constructed to satisfy application requirements.

[0027] FIG. 2 is a functional block diagram of an example line buffer 102. In one embodiment, the line buffer is implemented in an field programmable gate array (FPGA) configured with a block RAM. Those skilled in the art will appreciate that in other embodiments, other programmable logic devices (PLDs) or ASICs could be used to implement one or more line buffers.

[0028] Line buffer 102 includes block RAM 152, which functions as a dual port RAM that is controlled by write counter 154 and read counter 156. In the present application, block RAM refers in one embodiment to RAM implemented on FPGA, for example, the block RAM supported in FPGAs from Xilinx.

[0029] The write counter and read counter increment address values (WADD and RADD) that are provided to write address and read address ports of the block RAM. The write compare circuit 158 and read compare circuit 160 compare the WADD and RADD values from the counters with selected address thresholds. When the WADD value reaches the corresponding threshold, the write compare circuit 158 signals the write counter with the WEQ signal. Similarly, when the RADD value reaches the corresponding threshold, the read compare circuit 160 signals the read counter with the REQ signal. Active WEQ and write reset (WRST) signals to the write counter reset the write counter, and active REQ and read reset (RRST) signals reset the read counter. The write counter and writes to the block RAM are clocked by the write clock (WCLK), and the read counter and reads from the block RAM are clocked by the read clock (RCLK).

[0030] The write counter is enabled with the WE signal, which in an example video application is the horizontal synchronization signal. The read counter is enabled by the RE signal and is one address ahead of the write counter.

[0031] FIG. 3 is a functional block diagram of an example vertical filter 104. Those skilled in the art will recognize vertical filter 104 as a FIR filter. Vertical filter 104 includes an array of multipliers 202-1-202-m coupled to one or more coefficient block RAMs 204. The number of multipliers is equal to the number of vertical taps in the filter and determined by resize factors and image quality assessment. Each multiplier inputs a sample value from a line buffer and a coefficient selected from the block RAM 204. The output values from the multipliers are input to adder tree 206, which provides an input value to the horizontal filter 106.

[0032] The coefficient block RAM(s) provide different sets of coefficients for different resizing requirements. For example, if the resizing involves down-sampling by an odd number, different sets of coefficients are used depending on which line is in process. Coefficient selection control 208 reads the appropriate coefficients from block RAM 204 for input to the multipliers 202-1-202-m.

[0033] FIG. 4 is a functional block diagram of an example horizontal filter component. Those skilled in the art will recognize horizontal filter 106 as a multi-rate one-dimensional FIR filter in which coefficients change on a pixel-by-pixel basis.

[0034] Horizontal filter 106 includes an array of multipliers 222-1-222-p that receive as input values, delayed values output from the vertical filter (delay elements 224-1-224-p) and coefficient values selected from coefficient block RAM(s) 226. As with the vertical filter 104, the number of multipliers is equal to the number of horizontal taps in the filter and determined by resize factors and image quality assessment. Coefficient selection control 228 reads the appropriate coefficients from block RAM 226 for input to the multipliers 222-1-222-p. The coefficients are selected pixel-by-pixel based on the resize factor and position in the image. The output values from multipliers 222-1-222-p are input to adder tree 230, and the output value from the adder tree is the resized output sample.

[0035] FIG. 5 is a functional block diagram of a circuit arrangement for real-time rotation of a digital image in accordance with one embodiment of the invention. Circuit arrangement 400 linearly addresses pixels in the source image while generating the rotated image. The arrangement of line buffers 402-1-402-4 stores the image to be rotated and allows the source pixels to be shared in generating destination pixels. This greatly reduces the memory requirements for a given bandwidth requirement. Rotation control logic 403 controls sequencing of input sample values to the line buffers, reading sample values from the line buffers, controlling operation of the various elements of the circuit arrangement 400, and indicating when rotated image samples are valid.

[0036] With a center point of an image defined, a single parameter • specifies the transformation. The equations below provide the coordinate transformation in terms of rotation of the coordinate axis.

[0037] S_x=D_xcos (•)+D_ysin (•)

[0038] S_y=−D_xsin (•)+D_ycos (•)

[0039] where S and D represent source and destination coordinates, respectively. By inverting the equations, the destination coordinates are obtained, which can be truncated to find D_xand D_yvalues. The values are reiterated into the equations and used to calculate weighting factors for bicubic interpolation in the neighborhood of the available source pixels.

[0040] For image rotation, re-sampling interpolation is typically limited to 4×4 pixel neighborhoods for reasons of computational complexity. Thus, circuit arrangement 400 includes 4 line buffers 402-1-402-4, each having sample values for 4 pixels. Each of line buffers 402-1-402-4 is implemented in one embodiment with the line buffer arrangement 102 of FIG. 2. The line buffers are filled with sample values in the manner described above for image resizing.

[0041] Where F(p, q) is the nearest neighbor to a pixel to be interpolated (p is the row, and q is the column), a general bicubic (4×4) interpolation neighborhood is used to populate line buffers 402-1-402-4. Line buffer 402-1 stores row (p−1), line buffer 402-2 stores row p, line buffer 402-3 stores row (p+1), and line buffer 402-4 stores row (p+2).

[0042] As described in “Digital Image Processing”, 2^ndedition, William Pratt (John Wiley and Sons), the interpolated pixel can be expressed in the form:

[0043] F(p′,q′)=SUM_m=−1,2(SUM_n=−1,2(F(p+m, q+n)R_c[(m−a)]R_c[−(n−b)]))

[0044] where a and b are the differences between the rows and columns of F(p,q) and F(p′,q′), respectively, and R_cdenotes a bicubic interpolation function such as a cubic B-spline or cubic interpolation function. Bicubic processor 404 computes interpolated pixel values using selected input values from the line buffers and horizontal and vertical parameter values from parameter generator 406. The horizontal parameter value corresponds to the R_c[(m−a)] component, and the vertical parameter value corresponds to the R_c[−(n−b)] component of the function set forth above.

[0045] The angle of rotation is input to index generator 408. The index generator computes the present position in the raster scan and provides the position data to the destination address generator. By inverting the constitutive trigonometric equations the destination coordinates are obtained which can be truncated to find integer D_xand D_yvalues. These values are reiterated into the equation and used to calculate weighting factors for bilinear or bicubic interpolation in the neighborhood of source pixels available. Rastering through the input image with this procedure fills in the resultant rotated image.

[0046] The destination address generator 410 receives an input value from the index generator and computes a destination address. The destination address indicates a pixel position in a raster image for the rotated image sample value from the bicubic processor.

[0047] The destination address is input to the source address generator 412 in order to pass along the distances from destination to source points so that parameters can be calculated. The source address generator determines a location and distance off grid of the new output pixel in the source image. It will be appreciated that the new output value is in the destination image, and “location in the source image” refers to the overlay of the destination grid relative to the source grid during rotation. Values for the location and distance are provided to the parameter generator 406.

[0048] In one embodiment, bicubic processor 404, parameter generator 406, index generator 408, destination address generator 410, and source address generator 412 function in accordance with known techniques for rotating images. In other embodiments, the components can be adapted for application-dependent image rotation requirements. FPGAs are suitable for implementing the image-rotation circuit arrangement 400. Alternatively, the circuit can be implemented as an ASIC.

[0049] It is intended that the specification and illustrated embodiments be considered as examples only, with a true scope and spirit of the invention being indicated by the following claims.