Method and apparatus for bit-shuffling video data

[0002] This application claims priority from application Ser. No. 09/425,487, filed on Oct. 22, 1999, which claims priority from application Ser. No. 09/263,961, filed on Mar. 5, 1999, which claims priority from application Ser. No. 60/077,376, filed on Mar. 9, 1998, all of which are incorporated herein by reference in their entireties for all purposes.

[0003] The present invention relates to the field of image processing. More specifically, the present invention relates to methods and apparatus for storing a bitstream of digitized video data. Moreover, the present invention is capable of performing such storage using standard dynamic random-access memory (DRAM). This technique is especially suited to digital video applications, where such shuffling is done in order to maintain acceptable image quality. This implementation is suitable for widely-used image compression standards that integrate various algorithms into a compression system, such as the standards specified in the Digital Video Standard (the DV-SD standard, or “Blue Book”), which is included herein by reference in its entirety.

[0004] The DV-SD digital video standard outlines the breakdown of a video frame into superblocks and further, into macroblocks (and yet further, into blocks). This is shown in FIGS. 1, 2, 3, and 4. The data is received on a frame-by-frame basis. This data is stored in a frame buffer memory. Compressed video data is transferred in a staggered order, in order to avoid picture degradation. This is done by processing and transmitting the compressed video data in an out-of-order sequence, sending superblock from varied locations in the picture. Thus, if noise is encountered, it appears at several different locations in the picture, rather than clumped together in one area. The former is much more difficult for the human eye to detect, and so picture quality is improved, from a subjective viewpoint.

[0005] To simplify the reading and writing of such data, a memory system would normally have enough storage to hold two (or more) frames, and write one while the other was being written. However, due to the size of the video frames and the storage schemes that may be employed, the data for a single video frame requires an odd amount of storage space. One possible solution is to use special purpose memory chips. Such chips would have the proper amount of storage space and addressing to allow whole video frames to be dealt with. Unfortunately, such a solution is expensive. Moreover, such a solution is likely incompatible with other such solutions.

[0006] Alternatively, enough standard memory (e.g., DRAM memory) could be used to store two (or more) frames. However, this would result in a large amount of wasted space. While this might be more economical than the use of specialized memories, it would nonetheless cost more than necessary.

[0007] What is therefore required is a technique which allows the use of standard memory (e.g., DRAM memory) that uses a minimal amount of-memory while providing the requisite processing throughput.

[0008] The present invention solves the problems associated with the prior art by providing methods and apparatus for efficiently and accurately compressing video data.

[0009] In one embodiment, a circuit is disclosed for processing audio and video data utilizing conventional DRAMs.

[0010] These and other embodiments of the present invention, as well as its advantages and features are described in more detail in conjunction with the text below and attached figures.

[0011] FIG. 1 illustrates a block diagram of an NTSC video frame divided into superblock, and the division of the superblocks into macroblocks;

[0012] FIG. 2 illustrates a block diagram of an PAL video frame divided into superblock, and the division of the superblocks into macroblocks;

[0013] FIG. 3 illustrates a block diagram of the three types of NTSC superblocks, and their division into macroblocks;

[0014] FIG. 4 illustrates a block diagram of a PAL superblock, and its division into macroblocks;

[0015] FIG. 5 illustrates a block diagram an audio/video coding/decoding apparatus according to the present invention;

[0016] FIG. 6 illustrates a flow diagram illustrating the steps performed by a bit-shuffling circuit according to the present invention;

[0017] FIG. 7 illustrates a table showing the order superblocks are loaded in the present invention when compressing video using a 4:1:1 compression scheme;

[0018] FIG. 8 illustrates a table showing the order superblocks are loaded in the present invention when compressing video using a 4:2:0 compression scheme;

[0019] FIG. 9 illustrates a table showing the order superblocks are loaded in the present invention when decompressing video using a 4:1:1 decompression scheme;

[0020] FIG. 10 illustrates a table showing the order superblocks are loaded in the present invention when decompressing video using a 4:2:0 decompression scheme;

[0021] FIG. 11A illustrates a table showing the storage scheme for data representing digitized NTSC video frames for superblocks in rows 0 and 2, according to the present invention;

[0022] FIG. 11B illustrates a table showing the storage scheme for data representing digitized NTSC video frames for superblocks in rows 1 and 3, according to the present invention;

[0023] FIG. 11C illustrates a table showing the storage scheme for data representing digitized NTSC video frames for superblocks in row 4, according to the present invention; and

[0024] FIG. 11D illustrates a table showing the storage scheme for data representing digitized PAL video frames for any superblock therein, according to the present invention.

[0025] A solution to the problems with the prior art is to use apparatus and methods such as that of the present invention. The present invention allows the use of standard DRAM memory while avoiding unused portions thereof. FIG. 5 illustrates a system in which a bit shuffling circuit of the present invention might be used. An audio/video processor 100 is shown if FIG. 5 as receiving both audio data 110 and video data 120. Audio data 110 is transferred to and received from an audio interface and bit shuffling circuit 125, while video data 120 is transferred to and received from a video interface and bit shuffling circuit 130. Both circuits 125 and 130 transfer data to a DRAM memory 135 in order for the bit shuffling circuitry to properly access the data stored therein. Subsequently, the shuffled audio data is passed to an audio processor 140, while shuffled video data is passed to a video processor 145. Processed audio and video data is then sent to a muxing and subcoding circuit 150, which multiplexes the audio and video data to an interface circuit 155. Interface circuit 155 communicates this data to a host system (not shown), and receives data from the host system for decoding by audio/video processor 100 in a process that is the reverse of that previously described.

[0026] FIG. 6 illustrates the steps preformed in decoding a video bit stream received as video data 120. The process begins by receiving the first frame of video data, which is shown in FIG. 6 as step 600 where a superblock of the first frame of video data is received. At step 610 this superblock is stored in an unused area of DRAM memory 135. The process loops as step 620 until an entire frame has been received. At this point the process bifurcates. At step 630, reception of the next video frame is begun. At step 640 a superblock from the current frame of video data is received. At step 650 this superblock is stored in an area of DRAM memory 135 that is currently unused. At step 660, completion of the current frame's reception is determined. If the current frame is finished being received reception of the next frame is begun at step 630, once again. Simultaneously, the now-loaded video frame is processed. Processing begins at step 670, where the completely received video frame is read into video processor 145 for decompression. This process begins at step 680, where a superblock from the frame being processed is loaded into video processor 145 thus clearing that superblock's memory locations for use in receiving a superblock from a subsequent video frame. At step 690, completion of processing for the previous video frame is determined. At step 695, should the previous frame complete processing, it is determined whether the previous frame just processed was the last frame received. If this is the case the process completes.

[0027] Because a standard DRAM memory could be able to store only a single full video frame, and indeed this is desirable for reasons of cost, a method and apparatus capable of dealing with video frames on a superblock-level is required. Such a method and apparatus are provided by the present invention. In order to allow a second video frame to be loaded, the present invention loads superblocks into areas of memory where the superblocks of a proceeding video frame that have now been processed were now stored. In essence, the present invention fills the holes created by the processing of superblocks in a preceding video frame with the superblocks of a subsequent video frame. While this creates efficiency in the use of memory space, it necessitates a complex process of loading and unloading of data.

[0028] Such a process concerns itself with the ordering and location of the loading and unloading of superblocks within DRAM memory 135. Such orderings are illustrated in FIGS. 7 and 8 (compression), and FIGS. 9 and 10 (decompression). Thus, following the order illustrated in these figures, data may by loaded and unloaded continuously from a standard DRAM memory (e.g. 8 MB memory for either NTSC or PAL video formats). The FIGS. 11A, 11B, 11C, and 11D illustrate the storage of the three types of NTSC superblocks and one type of PAL superblock according to the present invention. These figures show the DRAM page numbers corresponding to the various superblocks. By using such addressing scheme, the storage of superblocks can efficiently take advantage of DRAM memory capable of fast-page mode operation.

[0029] The present invention provides several benefits. First, standard DRAM chips may be employed. This avoids the extra expense of specialized video RAM (VRAM) chips, static graphics RAM (SGRAM) chips, or other such memory solutions. The use of custom application specific memory (ASM) chips is also avoided. The use of standard DRAM chips also implies that the compatibility problems normally associated with such proprietary solutions are avoided. The present invention also provides picture quality meeting the digital video standard, while maintaining the necessary throughput rate.

[0030] The techniques of the present invention are therefore readily implemented in an integrated circuit to allow the efficient compression and decompression of digitally encoded images, while employing standard DRAM chips. The techniques of the present invention comply with the Digital Video Standard (the “Blue Book”, or DV-SD standard). These techniques can also be of use in systems implementing other standards, such as the International Standards Organization's (ISO) Joint Photographic Experts Group (JPEG) standard, ISO DIS 10918-1, and is JPEG-compliant, as set forth in ISO DIS 10918-2. These standards are included by reference herein, in their entirety. Moreover, the techniques of the present invention can be understood in the framework of a JPEG image compression/decompression system, such as that outline in “JPEG Still Image Data Compression Standard” by W. B. Pennebaker and J. L. Mitchell, which is also included by reference herein, in its entirety.

[0031] As will be understood by those with ordinary skill in the art, the present invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. For example, the techniques of the present invention can also be applied to other compression systems such as the standards specified by Motion Picture Experts Group (MPEG), or MPEGII. These standards are included by reference herein, in their entirety and for all purposes.

[0032] Alternately, the techniques of the present invention can be implemented in a computer system. For example, the systems of FIG. 5 can be implemented on a peripheral component interconnect (PCI) card. The PCI card can be installed onto the PCI bus of a personal computer. Also, other bus technologies such as NUBUS, ISA, EISA, Universal Serial Bus (USB), 1394 bus, and Accelerated Graphics Port (AGP) can also be utilized. Also, the techniques of the present invention can be implemented by utilizing the available routines and features such as caching, new instruction sets, and single instruction multiple data (SIMD) tools which are provided by Intel® Corporation's MMX™ technology, Advance Micro Device,® Inc.'s 3DNow!™ technology, and their equivalents. Additionally, even though the techniques of the present invention(such as specified in appendix B) have been discussed with respect to DCT transformation other types of transformations can also be utilized such as wavelet transform and vector quantization (VQ). Accordingly, for an understanding of the scope of the invention, reference should be made to the appended claims.

[0033] Also, having fully described certain features of the preferred embodiments of the present invention, many other equivalent or alternative techniques of implementing bit-shuffling according to the present invention will be apparent to those skilled in the art. Other signal processing applications that employ such bit streams may benefit from the present invention. Also, the implementation shown in the figures is but one of many possible architectures which may be designed to take advantage of the method of the present invention. These equivalents and alternatives, and others, are intended to be included within the scope of the present invention.