Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1997-11-13
2001-07-24
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240220
Reexamination Certificate
active
06266375
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of encoding of digital images. More particularly, the present invention relates to the quantization of pixels of digital images.
BACKGROUND
The need to compress digital image data, whether static or dynamic images (i.e., video images) has dramatically increased. In particular, digital video data creates among the largest amounts of data utilized. For example, a single 8.5×11 inch, 24-bit color image at 100 dots-per-inch, is made up of over 22 million pixels of data. Data compression is utilized in multimedia computer systems, as well as in digital video devices (i.e., digital video camcorders, DVD) players, and digital still image cameras) to reduce memory requirements. The popularity of these digital devices has increased dramatically. In addition, compression is used to transmit digital broadcasts such as direct satellite broadcasts and High Definition Television (HDTV).
Typically, digital image data is transmitted or stored in a compressed format and decompressed prior to the display of the image. Examples of widely used compression techniques are those that comply with MPEG, MPEG-2 (Moving Pictures Expert Group), DV and JPEG point Photographic Experts Group) standards.
Given digital image data to be compressed, an encoder follows an ordered set of steps called an encoding process. The encoding process is not standardized, and typically varies as encoders of different complexities can be used in different applications. Many encoding processes (including those that comply with MPEG, MPEG-2, DV or JPEG standards) utilize quantization procedures to reduce storage requirements of digital image data and regulate its output bandwidth.
The process of quantization typically begins with the selection of a quantization table from a set of quantization tables. Each quantization table contains a set of quantization steps. The actual quantization process itself is well known and will not be discussed in detail herein. However, as a result of the quantization process, the size of image data representing the unquantized image is reduced. Furthermore, the size of the quantized data can be varied according to the quantization table selected. For example, the smaller the magnitude of a table's quantization steps, the greater the size of the quantized data used to represent the unquantized digital image. Similarly, the larger the magnitude of a table's quantization steps, the smaller the size of the quantized data used to represent the unquantized digital image. In other words, if a smaller image data size is required, quantization steps of larger magnitudes are used. Analogously, if a larger image data size is desired, quantization steps of smaller magnitude are utilized. For further information, see
Introduction To Data Compression,
Sayood, 1996, pages 169-254.
A problem with conventional quantization table selection techniques is when delays are introduced by the encoder when selecting a quantization table to utilize. For example, bursty delay may cause time latency. In addition, a constant delay by the encoder may cause the encoder to fail in real-time encoding.
A number of different searching techniques can be used to locate a quantization table, including linear and binary searching techniques. A linear search simply starts at a first location in a list of quantization tables and searches sequentially until the object of interest, i.e., a quantization table, is located. The amount of time required to perform a linear search is proportional to the size of a list. In contrast, a binary search technique assumes that the collection of elements has been ordered. An object at the center of the tree (identified as a root node) is selected and the relationship of that object to the object being sought is determined. If the object precedes or follows the object being sought, the results are used to bisect the search range and recursively continue the process. The amount of time required to perform a binary search is proportional to the height of the tree.
Although each of these searching techniques are useful, each has advantages and drawbacks. For example, a linear searching technique is fast when the object of interest is located near the starting point in the list since only a small number of comparisons need to be performed to locate it. However, in a worst case, when the object of interest is at the end of the list, the entire list must be traversed before the object is located. Additionally, although binary searching techniques typically provide an efficient method for searching large databases of objects (since the search space is cut in half during each iteration), such techniques are not as efficient when the object of interest is located close to the starting point of the search. In sum, the sole use of either searching technique to locate a quantization table containing quantization steps of desired magnitude can introduce delays into a digital device's data transmission rate. For the foregoing reason, there is a need for a methodology to rapidly locate a quantization table containing quantization steps of a desired magnitude.
SUMMARY
The disclosed method and apparatus of the invention provide hybrid searching techniques that minimize the time required for determining a quantization table used in an encoding process.
A neighborhood of tables, which is a subset of a set of quantization tables is defined. During a quantization table search process, a next table to be examined is selected using a first search methodology if a previously examined table is in vicinity of the neighborhood of tables and using a second search methodology if the previously examined table is not in the vicinity of the neighborhood of tables.
In one embodiment, the first searching methodology is defined as a linear searching technique and the second search methodology is defined as a binary searching technique.
Other objects, features and advantages of the invention will be apparent from the accompanying drawings and from the detailed description that follows.
REFERENCES:
patent: 5398069 (1995-03-01), Huang et al.
patent: 5404168 (1995-04-01), Yamada et al.
patent: 5436985 (1995-07-01), Li
patent: 5444488 (1995-08-01), Goubault et al.
patent: 5450132 (1995-09-01), Harris et al.
patent: 5943446 (1999-08-01), Pulsipher et al.
Chang Ching-Fang
Lee Chuen-Chien
Yanagihara Naofumi
Blakely , Sokoloff, Taylor & Zafman LLP
Kelley Chris
Sony Corporation
LandOfFree
Method and apparatus for selecting a quantization table for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for selecting a quantization table for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for selecting a quantization table for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2484667