National Semiconductor Corporation

Xiaonong Ran

Michael A Van Scherrenburg

Chang Y Choo

Hak-Leong Ng

Micheal Van Scherrenburg

Christine A Porter

Mohammad R Motamedi

An encoding process is configurable to trade calculational complexity for bit rate while maintaining code format and image quality. A software encoder which implements the encoding process monitors bandwidth and processor utilization and when either is overtaxed, adjusts complexity to compensate. If further adjustment is required, encoded image quality is changed. Changing the search process or search window size used during searches for predictive blocks or changing a threshold which is compared to inter-code length before determining whether to calculate an intra-code changes complexity. An intra-coding method subtracts a base which depends on codes representing neighboring blocks from coefficients for a current block to determine a difference which is often small and easily compressed. Additionally, restricting a quadtree structure for one color component to a sub-tree of a quadtree structure for another other color component improves compression efficiency and reduces coding complexity.

Quadtree-structured coding of color images and intra-coded images

A hashing-based vector quantization process partitions a codebook into buckets. A hashing function determines the locations of buckets in the codebook and is selected so that buckets containing similar codevectors start near each other in the codebook. One hashing function forms an index from the most significant bits of components of a vector. During encoding, the hashing function generates an index from an input vector, and a search for a codevector matching the image vector begins in a bucket indicated by the index. In one embodiment, the codebook contains flag fields to indicate the starts of buckets and pointer fields to create linked lists of codevectors which form the buckets. Codevectors are compared to the input vector by determining the mean squared error of the difference between the codevector and the input vector. A search is complete when the search finds a codevector having a difference with a MSE less than a threshold. Search time is reduced because each search begins in a bucket likely to contain a codevector matching the image vector.

Hashing-based vector quantization

Two dimensional data structures are represented by quadtree codes with embedded Walsh transform coefficients. The quadtree code permits both variable block size inherent in quadtrees, and the calculational simplicity of Walsh transform descriptions of nearly uniform blocks of data. Construction of the quadtree is calculationally simple for implementation in a digital system which does a bottom-up determination of the quadtree because Walsh transform coefficients and a measure of the distortion can be recursively calculated using only Walsh transform coefficients from the previous level in the quadtree. Uniform step size quantization, which is optimal for variable length coding and generalized gaussian distributions, permits fast encoding and decoding of quadtree code.

Quadtree-structured walsh transform coding

A communication system and protocol uses retransmission techniques for video transmission on mobile/wireless channels. The system partitions frames of a moving image into frame segments, and combines a sequence of frame segments to form a sub-sequence of the moving image. The sub-sequences are treated as separate images which are separately encoded and transmitted to a receiver and then are combined to reassemble the moving image. A sender transmits to the receiver data packets, each data packet representing all or part of a digital code for a frame segment. The receiver requests retransmission of data packets containing detectable errors, indicates in a status buffer which digital codes have been received and whether the digital codes are intra or inter codes, and displays a frame only after all required data packets have been received without detectable errors. The segmented frames limit occasional failures to accurately retransmit data to individual sub-sequences, so that the failure to accurately transmit data is compensated for by subsequent transmission an intra coded digital code for a frame segment.

Video coding using segmented frames and retransmission to overcome

A hierarchial search for moving image encoding determines a motion vector by comparing a target block to sets of blocks selected according to the results of previous comparisons. Typically, each set of blocks includes a central block and four blocks offset on x and y axes. Blocks most similar to the target block provide co-ordinates of a center block in a next stage of the search. The hierarchial search searches regions indicated by previous comparisons to be similar to the target block and thereby reduces the number of comparisons and the search time required to find a motion vector. A motion estimation circuit for the hierarchial search includes: five processing elements which compare the target block to five blocks; a first memory that asserts a target block pixel value to the processing elements; a second memory that asserts five search window pixel values to the processing elements. The processing elements operate in parallel, and an address generator selects the five search window pixel values according to output from the processing elements. The second memory contains three parts. One part is loaded with new data while the processing elements search data from the other two parts. Each part contains nine memory modules, each having an independently addressable data port.

Motion estimation using a hierarchical search

A variable length coding process encodes a string of symbol values using arithmetic coding models selected according to the syntax of the string. The arithmetic coding models are optimized for each separate symbol in the string to provide efficient coding that provides a shorter average code length than is provided with arithmetic coding using a single model. In an embodiment for moving image coding, two sets of arithmetic coding models, one for intra frames and one for inter frames, are used for a series symbols representing DCT blocks. The model used for a symbol depends of the symbol's value and order in the series.

Syntax-based arithmetic coding for low bit rate videophone

A video compression system in accordance with the present invention may use a frame buffer which is only a fraction of the size of a full frame buffer. A subsampler connected to an input of the frame buffer performs 4 to 1 subsampling on the video data to be stored in the frame buffer. This allows the frame buffer to be one-fourth the size of a full frame buffer. The subsampling may even be 9 to 1, 16 to 1, or another ratio, for a concomitant decrease in frame buffer size. An upsampler is connected to the output of the frame buffer for providing interpolated and filtered values between the subsamples. Novel methods of filtering and interpolating performed by the upsampler are described. A new motion estimation technique is also described herein which directly detects the number of bits required to be transmitted to convey the difference between the predicted video data and the current video data, where a fewer number of bits used to convey the difference corresponds to better motion estimation. The search criterion for the best estimate of movement of a block is the minimum number of bits for conveying this difference.

Subsampled frame storage technique for reduced memory size

A new motion estimation technique is described herein which directly detects the number of bits required to be transmitted to convey the difference between the predicted video data and the current video data, where a fewer number of bits used to convey the difference corresponds to better motion estimation. The search criterion for the best estimate of movement of a block is the minimum number of bits for conveying this difference instead of minimizing the mean squared error (MSE) or mean average difference (MAD). Thus, complex calculations involving MSD or MAD are avoided. The motion estimator of the preferred embodiment uses a look-up table to convert motion compensated difference signals for a block of pels into the number of bits required to be transmitted to convey the difference signals. When it has been determined that a certain estimated displacement of a block would require the fewest number of bits to be transmitted, that displacement is selected as the best estimate, and the corresponding motion vector is transmitted along with a motion compensated difference signal containing the fewest number of bits.

Motion estimation with bit rate criterion

A coder/decoder selects one of a set of look-up tables for encoding/decoding a symbol. Each look-up table contains boundary values that result from an arithmetic coding model partitioning a first interval. A second interval contains an arithmetic code. During encoding, look-up table entries for a symbol value are converted to the scale of the second interval. The scaled values indicate a smaller interval containing the arithmetic code. Code bits are generated when most significant bits of upper and lower scaled values are equal. During decoding, a code word, which is a part of an arithmetic code, is normalized from the scale of the second interval to the scale for a look-up table and then compared to entries of the look-up table. When a segment containing the code word is identified, a decoded symbol value is known. A scaling circuit converts boundary values for the segment to the scale of the second interval then changes the second interval. Identical most significant bits in the boundary values are shifted out of a register to prevent overflow during encoding/decoding. To increase the effective size of the register, the next to most significant bit can be removed while a counter counts the number of bits removed.

Growing community of inventors

Cupertino, CA, United States of America

Xiaonong Ran