System and method for scaling combined video and computer generated imagery

[0002] The present invention relates to the field of digital video format conversion. More specifically, the present invention relates to universal format conversion architecture which processes combined video and computer generated imagery.

[0003] Today, in the digital television (DTV) post production environment, the use of video and computer generated imagery (CGI) of different formats has become commonplace. Format conversion of high quality, real time video raster CGI is becoming an integral part of the routine operation for efficient DTV content creation and delivery. Most existing video/graphics workstations rely on the CPU and its graphic-subsystem to perform image interpolation in software. When these software systems are used, incoming materials need to be rendered in a suitable format before image editing or composition can take place. A more productive alternative may be to use a dedicated hardware format converter (FC).

[0004] Due to the distinct signal characteristics (e.g., the bandwidth) of live video and CGI, however, a format converter optimized for scaling video is not necessarily suitable for CGI. Performance compromises such as image aliasing, ringing and blurring artifacts usually have to be made within a single interpolator design. To overcome the performance barrier constrained by one interpolator, there is a need for a new FC architecture for simultaneous video and CGI scaling.

[0005] In the advent of DTV age, the DTV transmission formats specified by ATSC have been adopted by all the major US TV networks. One TV network however, may be in favor of one DTV format while another network may prefer a different one. Multiple DTV formats will continue to complicate video post-production process since video/graphics workstations must be designed to work with multiple input and output formats. Therefore, format conversion is inevitable in DTV post-production and a practical solution must be found. While some high-end video/graphics workstations offer “resolution independence” by using software image interpolation, this results in a trade-off between operational speed and system resources allocation for image scaling tasks. To be more productive, a dedicated image-scaling hardware engine that operates efficiently with any mix of DTV-format sources is needed. This is particularly important for post processing companies wishing to serve a broad range of clients who will be working in a variety of standards. In addition, the ability to mix formats allows free use of all program assets, including both traditional video and computer generated imagery (CGI).

[0006] The distinctly different signal characteristics of traditional video and CGI are desirably taken into consideration in the design of a format converter. a Conventional wisdom is that all CGIs which have bandwidths that reach the Nyquist limit (ie., 0.5 cycle/pixel) are desirably passed through an anti-aliasing filter before they are scaled just to avoid ringing artifacts. Unnecessary antialiasing filtering for CGI image components, however, may cause image blurring which may diminish the visual appeal of these image components. On the other hand, it is desirable to maintain the bandwidth of CGI image components so that they may be properly displayed on digital display devices such as Plasma Display Panels (PDP) and Digital Light Processing (DLP) video projectors since these devices are capable of displaying CGI to its 0.5 cycle/pixel bandwidth limit. Because digital displays have 100% modulation transfer functions (MTFs), a graphics artist now has an opportunity to show off his artwork in the way that he intended to display it. There is a need for an architecture that can scale any CGI without trading graphics sharpness for other scaling artifacts (such as ringing) reduction.

[0007] The present invention provides a simple and effective means for a universal format conversion for use with images containing mixed video and computer generated imagery. A first intermediate scaled image is generated using a first interpolator. The first intermediate scaled image is then processed through an edge extractor to produce a scaled edge image. Next, a second intermediate scaled image is generated using a second interpolator. Then the scaled edge image is added to the second intermediate scaled image to produce a converted image.

[0008] In one embodiment a new format conversion architecture is based on dual FCs with the interpolators residing in the two FCs having complementary characteristics.

[0009] The invention is best understood from the following detailed description when read in connection with the accompanying drawings. Included in the drawings are the following figures:

[0010] FIG. 1ais a graph of amplitude versus frequency, which shows the filter kernel of a bilinear interpolation.

[0011] FIG. 1bis a graph of amplitude versus frequency, which shows the frequency response characteristic of the bilinear interpolation kernel shown in FIG. 1a.

[0012] FIG. 2ais a graph of amplitude versus frequency, which shows two exemplary filter kernels for two Kaiser windowed sinc function.

[0013] FIG. 2bis a graph of amplitude versus frequency, which shows the frequency responses of the kaiser windowed sinc functions shown in FIG. 2a.

[0014] FIGS. 3ais a graph amplitude versus frequency, which shows two exemplary filter kernels for two raised-cosine functions.

[0015] FIG. 3bis a graph amplitude versus frequency, which shows two exemplary frequency response characteristics for the raised-cosine functions shown in FIG. 3a.

[0016] FIG. 4ais a graph of amplitude versus frequency, which shows an exemplary sampling of an analog waveform of an interpolation kernel, which defines a three-phase filter kernel.

[0017] FIG. 4bis a graph of frequency versus amplitude, which illustrates frequency response characteristics for each of the three phases shown in FIG. 4a.

[0018] FIG. 5 (Prior Art) is an example of a one dimensional 4 tap finite impulse response interpolator with 3 phases.

[0019] FIG. 6 (Prior Art) is an example of a 1-D image scaler architecture.

[0020] FIG. 7 (Prior Art) is an example of a 2-pass 1-D interpolation architecture which may be used for image scaling.

[0021] FIG. 8 is an example of a universal format conversion architecture according to the present invention.

[0022] FIG. 9 (Prior Art) is an example of an original text image which is used for describing the operation of the present invention.

[0023] FIG. 10a(Prior Art) is a text diagram which shows an example of an up-conversion using a single interpolator.

[0024] FIG. 10bis a text diagram which shows an example of an up-conversion using the universal format conversion architecture shown in FIG. 8.

[0025] FIG. 11 (prior art) is an image diagram of a television test pattern.

[0026] FIGS. 12ais an image diagram of the test pattern shown in FIG. 11 up-converted using a single interpolator.

[0027] FIG. 12bis an image diagram of the test pattern shown in FIG. 11 up-converted using the universal format conversion architecture shown in FIG. 8.

[0028] FIGS. 13ais an image diagram of the test pattern shown in FIG. 11 down-converted using a single interpolator.

[0029] FIG. 13bis an image diagram of the test pattern shown in FIG. 11 down-converted using the universal format conversion architecture shown in FIG. 8.

[0030] The heart of a video and CGI format converter is an image scaler that transforms a digital image from one sampling lattice to another by re-sampling the original image in a 2D plane. Before designing an image scaler, it is important to understand the role that an interpolator plays in the image-scaling engine.

[0031] Image scaling for equally spaced data samples can be viewed as a convolution of a discrete interpolation function (or kernel) and the data samples. The numerical accuracy and computational complexity of an image scaler are directly linked to its interpolation kernel. As such, interpolation kernels are the targets of design and analysis in the creation of the interpolation algorithm. There are a number of interpolation kernels used for image scaling applications. The major differences are the tradeoffs among accuracy, efficiency and hardware complexity.

[0032] Bilinear interpolation is a very popular method used extensively by the PC manufacturers primarily for consumer video and graphics applications. In a 1-dimensional case, the output sample is calculated according to a weighted sum of its two neighboring samples, as shown in equation (1) $\begin{array}{cc}y\left(x\right)=\frac{x-x_0}{x_1-x_0}y\left(x_1\right)+\frac{x_1-x}{x_1-x_0}y\left(x_0\right)& \left(1\right)\end{array}$

[0033] where x₀and x₁are the input sampling grid and x is the output sampling grid that lies between x₀and x₁; y( ) is a function value (e.g., image intensity).

[0034] In the spatial domain, bilinear interpolation is equivalent to convolving the input with the interpolation kernel shown in equation (2): $\begin{array}{cc}h\left(x\right)=\{\begin{array}{cc}1-\left|x\right|& 0\le \left|x\right|\le 1\\ 0& \mathrm{otherwise}\end{array}& \left(2\right)\end{array}$

[0035] The waveform and the frequency response characteristics of a bilinear interpolation kernel are shown in FIGS. 1aand 1b, respectively. Although bilinear interpolation is very ecomonic to implement, it is rarely used to process professional quality video signals. It is evident from FIG. 1b, that the bilinear interpolation kernel has significant amounts of spurious stopband high-frequency component leakage which contributes to the aliasing. In addition, the passband is moderately attenuated, resulting in image smoothing. To prevent passband attenuation, the ideal frequency response for an kernel is a boxcar filter specified as equation (3) $\begin{array}{cc}{H}_{\mathrm{ideal}}\left(f\right)=\{\begin{array}{cc}1& 0\le \left|f\right|\le 0.5\\ 0& \mathrm{otherwise}\end{array}& \left(3\right)\end{array}$

[0036] A comprised between a true boxcar interpolation filter and a filter having the frequency response characteristic shown in FIG. 1bis a third order interpolation filter. The motivation for third-order interpolation filtering (e.g., cubic B-spline) is to combine segments generated from polynomials, using a finite amount of support, to match the zero-crossings of a truncated sinc function. This type of kernel provides better interpolation accuracy than a bilinear interpolation kernel and requires only small support in the spatial domain. This allows an interpolation filter having a truncated sinc kernel to produce output samples with little computation. The nonlinear terms in the kernel, however, increase the cost of the hardware relative to a linear interpolation filter. In addition, the truncated sinc interpolation filter has undesired attenuation in the passband that could result in image smoothing.

[0037] Sampling theory has established that the sinc function is the ideal interpolation kernel. It is, however, physically unrealizable since it has infinite support in the spatial domain. In practice, a smoother “roll-off” windowing function with finite support is used to mitigate the ringing artifact as a result of direct sinc function truncation. Among the most popular window functions is the Kaiser window function, which is defined by equation (4): $\begin{array}{cc}k\left(x\right)=\{\begin{array}{cc}\frac{I_0\left(\beta \right)}{I_0\left(\alpha \right)}& \left|x\right|\le \frac{N-1}{2}\\ 0& \mathrm{otherwise}\end{array}& \left(4\right)\end{array}$

[0038] where β is a free parameter defined by equation (5): $\begin{array}{cc}\alpha ={\beta \left[1-{\left(\frac{2x}{N-1}\right)}^2\right]}^{-\frac{1}{2}}& \left(5\right)\end{array}$

[0039] The interpolation kernel is, therefore, the product of the Kaiser window function and the sinc function as set forth in equation (6) $\begin{array}{cc}h\left(x\right)=k\left(x\right)\frac{\sin \left(\pi x\right)}{\pi x}& \left(6\right)\end{array}$

[0040] FIGS. 2aand 2bshow the Kaiser-windowed sinc function with β=5 and 20, respectively. When β is increased, the tail in the spatial domain diminishes quickly. This increase in β translates in the frequency domain a narrower passband and a wider transition band, which may lead to more aliasing artifacts and image blurring. A more gradual transition band, however, produces reduced ringing artifacts near sharp edges. The choice between passband width and transition band width are balanced based on the application. For example, one may opt for a larger β for CGI scaling when edge ringing becomes the dominant artifact, while a smaller β may be suitable for natural video scaling due to the band-limiting characteristics that may be contributed by the video camera.

[0041] It is well known that filters based on windowed sinc functions tend to produce ringing artifacts near edges. Although they offer improvement over directly truncated sinc function, they retain a fairly sharp transition from passband to stopband. Therefore, it is desirable to impose smoothing constraints on the filter response in the frequency domain. When the desirable frequency response is defined to be a smooth function from the passband to the stopband, its impulse response decays much faster and may be truncated without explicit windowing.

[0042] One particular function which exhibits a smooth transition between the passband and the stopband is the raised-cosine function. Its corresponding interpolation kernel is defined by equation (7): $\begin{array}{cc}h\left(x\right)=\sin c\left(x\right)\frac{\cos \mathrm{\pi \gamma }x}{1-{\left(2\gamma x\right)}^2}& \left(7\right)\end{array}$

[0043] Like the sinc function, the raised-cosine function is physically unrealizable. However, the tails of the raised cosine function decay at a rate of 1/x³and diminish more rapidly than the tails of the sinc function. In practice, the raised cosine function can be approximated by truncating the pulse at some integer number (integer multiple of the Nyquist period) depending upon the γ value. It is understood that the parameter γ (known as the roll-off parameter) controls the excess bandwidth varying from 0% to 100% of the minimum bandwidth with respect to that of the sinc function.

[0044] FIGS. 3aand 3bshow a raised-cosine function with 50% excess bandwidth (γ=50%) in comparison with an otherwise very similar Kaiser windowed sinc function with β=30. In this case, the Kaiser windowed function is better for reducing aliasing distortion while raised-cosine function is better for reducing ringing distortion.

[0045] When performing image scaling, it is desirable to weight the input samples with appropriate values taken from the interpolation kernel. To avoid computation of the interpolator's coefficients in real time, it would be sufficient to store different sets of the coefficients in a read only memory (ROM) which can be addressed by a phase selector based on the phase (position lying between two input samples) of an output sample. It is however, desirable to compute sample values that have an arbitrary relationship to the input sample lattice. Thus, to define an ideal interpolator, an infinite number of filter coefficients and phases would be required. A practical solution is to have a large, but finite number of phases available. Therefore, the output sample lattice quantized to the nearest interpolation phase which allows the ROM lookup table to produce the corresponding set of coefficients. It has been shown in that a lookup table of 65 phases adds virtually no mean-square-error to the error that occurs due to image data roundoff.

[0046] FIG. 4ashows an analog interpolator kernel with Kaiser windowed sine function which has been approximated by a 4-tap FIR filter with 3 phases. The 3 coefficient sets organized as dot, (C₀₀, C₀₁, C₀₂, and C₀₃), triangle (C₁₀, C₁₁and C₁₂), and square (C₂₀, C₂₁and C₂₂) shapes correspond to phase 0, 1 and 2, respectively. The frequency spectra after normalization are plotted in FIG. 4b.

[0047] One possible hardware realization of such an interpolator is shown in FIG. 5. The exemplary interpolator shown in FIG. 5 is a four-tap, three phase FIR filter. Input samples are provided to four series-connected delay elements 510. Each of the delay elements is coupled to a coefficient multiplier 512. Each of the multipliers 512 includes a coefficient look-up table memory (not shown) which holds three coefficients, one for each phase. A phase select signal is provided to the interpolator 614 to choose one coefficient set to be applied to one input port of each of the multipliers 512. The output signals of the multipliers 512 are summed by adder 514 to produce the output signal of the filter 614.

[0048] The interpolation filter shown in FIG. 5 is a four-tap, three phase FIR filter. As set forth below, the filter used in one exemplary embodiment of the invention is a 16-tap 128 phase filter. This filter may be implemented using a format conversion filter such as that disclosed in U.S. Pat. No. 5,057,911 entitled SYSTEM AND METHOD FOR CONVERSION OF DIGITAL VIDEO SIGNALS, which is incorporated herein by reference for its teachings on digital interpolation filters.

[0049] In general, a typical 1-D image scaler such as the one shown in FIG. 6, may consist of a front-end Buffer 610, which holds sample values when multiple output samples are formed from the same input samples. The lowpass filter (LPF) 612 is used as an anti-aliasing filter when downsampling. The 1-D interpolator 614 is described above with reference to FIG. 5. Buffer 616 is used to smooth out the output data during down-conversion. The DROP signal is asserted when there are no output samples between two input samples. No ouputs samples are written to Buffer 616 during this period.

[0050] The phase selector 618 provides the phase selection signal to the interpolator 614 and controls the fetching of input samples from the buffer 610 and the storing of output samples into the buffer 616. The phase sequence used for addressing the coefficient lookup tables in the interpolator 614 can be calculated via equation (8): $\begin{array}{cc}{p}_x=\left(x+\frac{A}{B}{N}_p\right)\mathrm{mod}\left(N_p\right)& \left(8\right)\end{array}$

[0051] where x is the current sample position, A and B are the output and input sample intervals, respectively; Np is the total number of phases.

[0052] Although all the interpolation kernels discussed above can be generalized to the 2-D case, image interpolation based on a 2-D kernel is hardware intensive. Alternatively, 2-D interpolation can be acccomplish by performing 1-D interpolation in each dimension. As shown in FIG. 7, the horizontal scan lines are first processed using 1-D interpolator 710. The intermediate result is stored horizontally (i.e. line by line) in a transpose memory 712 and is then read out vertically (i.e. column by column) to be applied to second-pass interpolator which is identical to the first pass. The order of processing is arbitrary since the equivalent 2-D interpolation kernel is separable(e.g., h(x)h(y)).

[0053] As illustrated in Table 2, separable interpolation provides a substantial reduction in computational complexity from O(n²N²) to O(nN²) for an N×N image and an n×n filter kernel.

[0054] The interpolation kernel plays a pivotal role in image scaling. A narrow transition region in the frequency domain is desirable because a sharp cut-off between the passband and the stopband minimizes blurring and aliasing. Unfortunately, the sharp transition also contributes to ringing artifacts. The ringing artifacts are particularly annoying when scaling CGI, such as video with a graphics overlay (e.g., movie credits) or text (e.g., a web page). The goal of reducing ringing artifacts and the goal of reducing blurring and aliasing are mutually incompatible.

[0055] Because it is difficult to design a single interpolator that provides solutions to the problems mentioned above, a better compromise may be achieved by using two interpolators. If the images scaled by the two interpolators are fused properly, the result will be a fused image with better overall performance than could be achieved by a single interpolator of comparable complexity.

[0056] As outlined above, a Kaiser windowed sinc function can be adjusted to have a narrow transition band that is desirable for minimizing aliasing distortion and blurring while a raised-cosine function can be made to have a smooth transition band that is desirable for minimizing ringing distortion. The desirable characteristics of these two filters may be fused using a heuristic. One exemplary heuristic is implemented in the apparatus shown in FIG. 8.

[0057] FIG. 8 is a block diagram of a format conversion system according to the present invention. The interpolators residing in the two FCs are designed to have complementary characteristics so that better performance can be attained through image fusion.

[0058] FIG. 8 can also be used to describe the method for scaling an input image. The method may be implemented as a computer program, which may reside on a carrier such as a disk, diskette, or modulated carrier wave. When the it exemplary method is implemented as a computer program, the input and output images may be stored in respective frame buffers and there would be no need for a separate transpose operation as the data may be stored into, and/or retrieved from the frame buffers either along a column or along a row. Furthermore, the two one-dimensional filters may be combined into a single two-dimensional filter in one or both of the interpolation operations.

[0059] Returning to FIG. 8, the input image is scaled in a first interpolator 800. In the exemplary embodiment of the invention, interpolator 800 is a 2-pass 1-D scaler which uses an interpolation kernel having a frequency response with a relatively sharp cut-off (such as a Kaiser-windowed sinc function with a small β) to generate a first intermediate scaled image.

[0060] The same input image that was processed by the scaler 800 is processed by the scaler 810, which may be, for example, a 2-pass 1-D scaler using an interpolation filter with more gradual roll-off in its transition band (such as a raised-cosine function with a moderate roll-offparameter γ), to generate a second intermediate scaled image.

[0061] A noise-insensitive edge extractor 805 (such as a 2-D 3×3 Marr filter) processes the first intermediate scaled image, provided by the interpolator 800 to separate the high-frequency component of the first intermediate scaled image.

[0062] The rationale for using an interpolator with a relatively sharp transition from its passband to its stopband to form the first intermediate scaled image is to reduce edge softening and aliasing without introducing excessive edge ringing. The 2-D Marr filter that forms the edge extractor 805 is essentially a high-pass filter which has been shown to be robust against spurious signals such as mild ringing. The high frequency output signals of the edge extractor 805 are scaled in amplitude by a gain block 820 to compensate the rolled-off edges provided by the interpolator 810. The resultant output of the step 820 is a ringing-reduced highpass signal of the scaled image and will be used to compensate the output signal provided by scaler 810. Although the gain block 820 is shown as a separate component of the format conversion system in FIG. 8, it is a contemplated that it may be implemented within the edge extractor 805 by an appropriate scaling of the coefficients used to implement the edge extractor.

[0063] The use of an interpolator 810 with smooth transition band is appropriate since it can suppress ringing artifacts to an indiscernible level. The penalty, however, is frequency response attenuation near the passband edge and aliasing. The attenuated frequencies can be largely compensated by the high frequency output signals of gain block 820, as stated above.

[0064] The summing circuit 840 adds the high-frequency components extracted by the edge extractor 805 and gain block 820 to produce the final scaled image. This image has the sharp edges provided by the Kaiser windowed sinc interpolator 800, edge extractor 805 and gain block 820 while having essentially no ringing artifacts due to the signal provided by the raised-cosine interpolator 810.

[0065] Tables 3, 4, and 5 respectively, show the filter information for a raised cosine response based interpolator (γ=50%), for a Kaiser-windowed sinc function interpolator (β=5) and for a 5×5 edge extractor for a gain of k=1. The exemplary interpolation filter has 128 phases, each phase has sixteen coefficients. Although this exemplary embodiment describes a filter having 128 phases, the inventors have determined that good results can also be attained using an interpolation filter with 65 phases, where each phase defines a distinct inter-sample position. Coefficients for such a filter may be obtained, for example by deleting the even-numbered phases as described below in Tables 3 and 4.

[0066] Although the invention has been described thus far in terms of a interpolators based on Kaiser windowed sinc functions and raised-cosine functions, it is contemplated that other types of interpolation functions may be used. For example, a suitable filter may be designed as a generalized frequency domain least square (LS) FIR design that enables frequency-domain weighting of the LS error, any such interpolator can be used as long as the design criteria set forth above are considered. Alternatively, windowed sinc functions with different (or same) windowing functions and/or different parameters can also be used. Ideally, the characteristics of the two interpolators should be complementary. The interpolator preceding the edge extractor is desirably be relatively flat in the passband to protect the high frequency content of the image. This interpolator also desirably has a reasonably sharp cut-off without causing excessive edge ringing. Additionally, the other interpolator desirably has a more gradual roll-off at the band edge so as to minimize ringing artifacts and also has good stopband attenuation so as to minimize aliasing errors.

[0067] FIGS. 9, 10A, and 10b show an original image and two up-converted text images, respectively. All of these images have been contrast enhanced to more clearly show the presence or absence of ringing artifacts. FIG. 10ais obtained using only a Kaiser windowed sinc interpolator (β=5) implemented using a 16-tap 12-bit and 128-phase 1-D FIR filter. Strong ringing artifacts can be seen around each character that interferes with its readability. It is evident that a windowed sinc interpolator alone is unable to produce satisfactory scaling without compromising the result.

[0068] FIG. 10bis produced using the new format conversion architecture shown in FIG. 8 with an identical Kaiser windowed sinc interpolator and a raised-cosine interpolator with 50% roll-off. The scaled text is more pleasant to read with virtually no visible ringing artifacts.

[0069] The disclosed scaling architecture is suitable for traditional video scaling applications, as shown by the up and down-converted TV test patterns in FIGS. 12aand 12b, and FIGS. 13aand 13b, respectively, while FIG. 11 shows the original test pattern. The proposed scaling method produces virtually an identical image to that of a single interpolator and, therefore, no compromise is made for traditional video scaling. The simulations on the test images confirms the effectiveness of the new scaling method when compared with the scaling technique where only one interpolator is used.

[0070] Digital video format conversion allows video post-production facilities to serve a broad range of clients who will be working in a variety of standards in current DTV multi-format broadcasting environment. In addition, format conversion gives post-processing facilities the freedom to utilize any program asset regardless of its origin. Although many video/graphics workstations offer image-scaling capability in software, dedicated hardware solutions will prove to be a more efficient alternative. The present invention uses an efficient 2-pass 1-D interpolation architecture as described above. To eliminate the ringing artifacts found typically in a scaled CGI, the new universal format conversion architecture uses two FCs. The primary difference between the two FCs is that their interpolation kernels are programmed to have complementary frequency response characteristics. Therefore, one interpolator produces less aliasing and blurring while the other produces less ringing. By using an edge extraction technique, the two scaled images are fused into the one that has the best performance for simultaneous video and CGI scaling.

[0071] While this invention has been described with reference to specific embodiments, it is not necessarily limited thereto. Accordingly, the appended claims should be construed to encompass not only those forms and embodiments of the invention specifically described above, but to such other forms and embodiments as may be devised by those skilled in the art without departing from its scope as defined by the appended claims.