System and method for converting wavelet and computer program product

(Field of invention) The present invention relates to data compression, and more particularly to data compression using a wavelet.

(Background of invention) Video "codecs" (compressors / decompressors) are required for data communication streams by balancing image quality, processor requirements (eg, cost / power consumption), and compression ratios (ie, the data rates produced). Used to reduce the data rate. Currently available compression methods offer different ranges of trade-offs and generate profiles for multiple codecs, each profile being optimized to meet specific application requirements.

Figure 1 shows example 100 of the trade-offs between the various compression algorithms currently available in the prior art. As shown in the figure, such compression algorithms include a wavelet-based codec 102 and a DCT (Discrete Cosine Transform) -based codec 104 that includes various MPEG video distribution profiles.

2D and 3D wavelets are the current alternative to DCT-based codec algorithms. Wavelet has received a great deal of attention due to its good image quality and flexible compression ratio, and has urged the JPEG Commission to adopt the Wavelet algorithm in the JPEG-2000 still image standard. Unfortunately, most wavelet implementations use very complex algorithms and require enormous processing power compared to the alternative DCT. In addition to this, wavelets pose a unique challenge to time compression, making 3D wavelets particularly difficult.

For these reasons, wavelets have never had the advantage of competing with the costly, industrial standard codecs that are used in large numbers like MPEG, and have therefore only been adopted for crevice (niche) applications. Therefore, there is a need to achieve a commercially viable 3D wavelet optimized for low power and low cost, focusing on three major market areas.

For example, small camcorders are more widely used and the advantages of handling video camera signals digitally are obvious. For example, the fastest growth of the cellular (mobile) phone market in some countries is due to phones with image and video clip capabilities. Most digital still cameras have a video clip function. In the mobile radiotelephone (handset) market, the transmission of these still images and short video clips requires even more battery capacity of the device. Existing video coding standards and digital signal processors place an additional burden on batteries.

Another new use is a personal video recorder (PVR) that allows viewers to pause and time-shift (stagger) live TV broadcasts. These devices record video using digital hard disk storage and require video compression of analog video from the cable. In order to provide these features as picture-in-picture (child screen, dual screen), recording while viewing, these devices require multiple video compression encoders (encoders).

Another growing area of application is digital video recorders (DVRs) for surveillance and security video. Again, compression coding is required for each channel of the input video to be stored. In order to take advantage of the convenient and flexible (flexible) network transmission architecture, the video must be compressed in the camera. Earlier multiplexing recorder architectures also require multiple channel compression encoders.

Of course, there are a huge number of other markets that will benefit from the commercially viable realization of 3D wavelets optimized for low power and low cost.

The image is well modeled as a polynomial with most points smooth and some relatively isolated singularities and singular lines (edges, edges) when considered as a function on a two-dimensional square. Is where experience teaches. Video clips are similarly modeled in the 3D domain. For most images and videos, the residuals from the linear polynomial model RMS (Root Mean Square) are around 5%, and for the quadratic polynomial model around 2%.

Commonly used methods for approximating these functions (images and videos) include the following steps: 1) The step of reversibly transforming this function so that the converted coefficients can be divided into "sub-bands". 2) The step of quantizing (ie, reducing accuracy) all subbands except the "lowpass" subband. 3) The step of applying an inverse transformation to the quantized coefficients, thereby reconstructing the approximation of the original function.

A good method is to use a transformation that projects the contents of the low-order polynomial of the function into an unquantized "lowpass" subband. Ideally, such a scheme also produces zero or very small values within the other subbands. Therefore, the subsequent non-lowpass subband quantization does not significantly change the transformation of the function well modeled by a sufficiently low-order polynomial, and the reconstruction that approximates the original function is very good. It will be something like that.

The truth of the realization is that it is highly desirable that the values in the transformed function depend only on the values in the small neighborhood of some points in the original function domain. This is one of the purposes of 8x8 blocks in the JPEG and MPEG standards. In these specifications, the neighborhoods of the regions either match (overlap) or do not intersect, dividing the image region into separate chunks of neighborhood, each with a separate boundary. The approximations that result from quantization tend to be less severe at these boundaries (the well-known "Gibbs effect" in the discrete Fourier transform), and the "blocking" artifacts (distortions) that are noticeable in the reconstructed approximation image. Image) is produced.

The wavelet transform has overlapping neighborhoods, but is attracting a great deal of attention as a transformation class with small-region neighborhood characteristics. Some wavelet transforms do better work of projecting functions primarily into the lowpass subband compared to the JPEG / MPEG DCT. In addition, some wavelet transforms (not necessarily the same as some above) have significantly lower computational densities. However, duplication in the vicinity of the area imposes major realization problems in the areas of data handling, memory utilization and memory bandwidth. It is still useful to "block" the regions and return to the problem of approximations at and near the boundaries of the regions.

The transformation at the boundary of a region introduces the problem that the neighborhood of the region created at the boundary does not exist in the region block to which this boundary belongs. The traditional approach to this problem, embodied in various JPEG and MPEG standards, is to make the region values within the block a symmetric reflection image of the boundary, creating "virtual" values and virtual functions in the required neighborhood. It is to be.

If this virtual function is generally not a constant on the neighborhood, it has a destination or crease on the boundary generated from a discontinuous first derivative. This discontinuity is not well modeled by low-order polynomials, thus resulting in the reflected image being a non-lowpass subband coefficient that remains large after quantization. This larger quantization error increases the approximation error at the boundary.

One of the conversions specified in the JPEG-2000 standard 1) is the reversible 5-3 conversion shown in the following equations 1.1 and 1.2.<maths num="1"><img file="JP2010141922A_D0001.tif" /></maths>

Since these equations are integer-integer mappings and can be solved in the opposite direction to the container for Y, this transformation is reversible and produces the input Y bit by bit exactly back (see equation below).<maths num="2"><img file="JP2010141922A_D0002.tif" /></maths>

Obviously from these equations, Y_{2n + 1}Is an estimate of half the negative value of the quadratic derivative at (2n + 1) (half the value of the quadratic derivative minus a minus), and the function is good at (2n + 1) by the linear polynomial. If it is close to, Y_{2n + 1}Is about 0.

The purpose of adding constants in square brackets ([]) in the above equation is to remove any DC bias from the estimate. The uncorrected bias in the wavelet tends to cause an oscillating error in the reconstructed data, which is seen as a fixed pattern of noise. There are several possibilities for bias estimation and correction, and the JPEG-2000 standard selects one of these.

If the right border of the image is at point 2N-1, the required value X_2NCannot be calculated in Equation 1.1 because is not available. The JPEG-2000 standard extends the function to the symmetric positive side for this case, and X_2N= X_2N-2Request to respond by using. If this substitution is made for Equation 1.1, it becomes as follows.<maths num="3"><img file="JP2010141922A_D0003.tif" /></maths>

This formula is Y_2N-1Is generated, which is the estimate of the first derivative with respect to the estimate of the negative value of half of the above second derivative, which is the inner point. Moreover, it is clear that estimates of the quadratic derivative can only be obtained by using three distinct points instead of just two. It is necessary to limit the two points required for the lift term of X with an even index, because these two points are the only ones available for the opposite step. The closest candidate index is 2N-4.

The JPEG-2000 formulation of the 5-3 wavelet filter includes the addition of constants 1 or 2 during the calculation, and other restrictions, especially as seen in equations 1.2 and 2.1. When implemented for maximum computational speed and efficiency, these additions and other limitations require the overall computational load to be very fragmented, which can result in significant performance degradation.

<p>(Disclosure of Invention) The present invention provides systems, methods, and computer programs for compressing data. First, we receive the interpolation formula. Data is compressed using these interpolation formulas. In use, the interpolation formula determines if it requires at least one unobtainable data value. If required, perform extrapolation operations to generate the required unavailable data values.</p><p> In one preferred example, the interpolation formula can be a component of the wavelet filter. As another option (optional), the wavelet filter can be selectively replaced with a polyphase filter.</p><p> In another preferred example, a plurality of data values can be segmented (divided) into a plurality of spans (intervals). As a result, the amount of calculation related to the interpolation interpolation formula can be reduced by using the data values within only one of these spans.</p><p> In yet another preferred example, the data value can be quantized. In such a preferred example, the amount of calculation related to entropy encoding can be reduced by reducing the number of data values. The quantity of data values can be reduced during the quantization operations associated with these data values.</p><p> In yet another embodiment, the amount of computation associated with reconstructing the data value into a predetermined data range can be reduced. Such operations can be reduced by performing only a single clip operation.</p><p> In one preferred example, the wavelet filter comprises an interpolation formula that includes:<maths num="4"><img file="JP2010141922A_D0004.tif" /></maths> In one preferred example, the wavelet filter comprises an interpolation formula that includes: Y_{2N + 1}= (X_{2N + 1}+1/2)-(X_2N+1/2) In one preferred example, the wavelet filter comprises an interpolation formula that includes:<maths num="5"><img file="JP2010141922A_D0005.tif" /></maths> In one preferred example, the wavelet filter comprises an interpolation formula that includes:<maths num="6"><img file="JP2010141922A_D0006.tif" /></maths> In one preferred example, the wavelet filter comprises an interpolation formula that includes:<maths num="7"><img file="JP2010141922A_D0007.tif" /></maths> In one preferred example, the wavelet filter comprises an interpolation formula that includes:<maths num="8"><img file="JP2010141922A_D0008.tif" /></maths> In one preferred example, the wavelet filter comprises an interpolation formula that includes:<maths num="9"><img file="JP2010141922A_D0009.tif" /></maths> In one preferred example, the wavelet filter comprises an interpolation formula that includes: (X_{2N + 1}+1/2) = Y_{2N + 1}+ (X_2N+1/2) </p><p> The present invention provides other systems and methods for compressing data. First, the data is received by a single device. Such data is encoded using the single device to generate first compressed data in the first format. Further, the first compressed data is code-converted (transcoded) by using the single device to generate the second compressed data in the second format.</p><p> In one preferred example, the coding can be done in real time. Further, the code conversion can be performed offline (processed collectively later).</p><p> In another preferred example, the first compressed data is code-converted to generate second compressed data in a second format adapted to match the capacity of the communication network coupled to the single device.</p><p> As an option, coding can be performed using the first encoder. Further, the code conversion can be executed by using the decoder (decoder) and the second encoder.</p><p> In addition, the first format can include a wavelet-based format. In addition, the second format can include a DCT-based format. In one particular preferred example, the second format can include an MPEG format.</p><p> The present invention provides a system and method for compressing data utilizing multiple encoders on a single integrated circuit. First, the data is received by the single integrated circuit. Next, the data is encoded using a plurality of encoders built in the single integrated circuit.</p><p> In one preferred example, the data can be encoded using a plurality of channels on the single integrated circuit. In addition, these data can be encoded in a wavelet-based format.</p><p> The present invention provides other single module systems and methods for compressing data. During use, it utilizes a single module to receive photons. After that, this single module is used to output compressed data representing these photons.</p><p> Alternatively, the compressed data can be encoded in a wavelet-based format. In addition, the conversion operations associated with this coding can be performed in analog. The single module can further include an image sensor (imager).</p>

<figref num="1">It is a figure which shows the example of the trade-off between various compression algorithms currently available.</figref><figref num="2">It is a figure which shows the framework which compresses / decompresses data by one Example of this invention.</figref><figref num="3">It is a figure which shows the method of compressing / decompressing data by one Example of this invention.</figref><figref num="4">It is a figure which shows the data structure of the object which executes the method of FIG.</figref><figref num="5">It is a figure which shows the method of compressing / decompressing data by one Example of this invention.</figref><figref num="6">It is a figure which shows the system which compresses data by one Example of this invention.</figref><figref num="7">It is a figure which shows the system which compresses data by using a plurality of encoders on a single integrated circuit.</figref>

(Explanation of preferred examples) FIG. 2 shows a framework (framework) 200 for compressing / decompressing data according to the present invention. The framework 200 includes a coder (encoder) unit 201 and a decoder (decoder) unit 203, which together form a "codec". The coder unit 201 includes a conversion module 202, a quantizer 204, and an entropy encoder (encoder) 206 that compresses the data to be stored in the file 208. In order to decompress such a file 208, the decoder unit 203 decompresses the inverse conversion module 214, the dequantizer 212, and the entropy decoder 210 that decompresses the data (for example, in the case of video data, for viewing). including.

In use, the transformation module 202 performs a reversible transformation of multiple pixels (in the case of video data) for the purpose of inverse correlation (decrelation, decoration), which transformation is a linear transformation. Often. Next, the quantizer 204 quantizes the conversion value, and then the entropy encoder 206 functions to entropy-encode the quantized conversion coefficient.

FIG. 3 shows a method 300 for compressing / decompressing data according to the present invention. In one embodiment, this method 300 can be performed in a manner in which the conversion module 202 performs a reversible conversion in relation to the conversion module 202 of FIG. However, method 300 can be realized in relation to what is desired.

In operation 302, an interpolation interpolation formula for compressing data is received (for example, it is identified and acquired from a memory or the like). In the context of this embodiment, the data is any compressible data. Further, the interpolation formula can include any formula using interpolation (eg, wavelet filter, etc.).

In operation 304, it is determined whether the interpolation interpolation formula requires at least one data value, where the required data value is not available. Such data values can include any subset of the data described above. The availability of required data values can mean that these required data values are absent, out of range, and so on.

It then performs extrapolation operations to generate the necessary and unobtainable data values. In operation 306, the extrapolation formula includes any formula that uses extrapolation. This method extends data compression.

FIG. 4 shows the data structure 400 for which method 300 is executed. As shown in the figure, during the transformation, the "best fit" 401 can be achieved by the interpolation formula 403 involving multiple data values 402 (operation 302 of method 300 in FIG. 3). See). If one of the data values 402 is found to be unavailable (see 404), then the extrapolation interpolation formula can be used to generate these unavailable data values. Optional details regarding the preferred implementation of one of the above techniques are described in detail below with reference to FIG.

FIG. 5 shows a method 500 for compressing / decompressing data according to the present invention. As an option, this method 500 can be performed in a manner in which the conversion module 202 performs a reversible conversion in connection with the conversion module 202 of FIG. However, method 500 can be realized in relation to what is desired.

Method 500 provides a technique for generating edge filters for wavelet filters. First, in operation 502, the wavelet method is analyzed to determine the local derivative that the wavelet filter approximates. Next, in operation 504, the degree of the polynomial used for extrapolation is selected based on the characteristics of the wavelet filter and the number of available samples. Next, the extrapolation interpolation formula for each wavelet filter is derived using the degree of the selected polynomial (see operation 506). Further, in operation 508, the extrapolation interpolation formula is used together with the samples available in each case to derive a wavelet case of a specific edge.

An optional method for solving the coefficients using a Vandermonde matrix is described in Appendix A. In addition, additional and optional information and related information regarding suitable extrapolation formulas will be described in detail below.

Y_2N-1Can be fitted from the left side to a quadratic polynomial to approximate from the left side. Approximating the negative value of half of the quadratic derivative in 2N-1 using the available values is as in Equation 1.1R. One of the possible determinations of this extrapolated quadratic equation is given in Appendix A.<maths num="10"><img file="JP2010141922A_D0010.tif" /></maths>

When the point is at the far right, the threshold 1.1R can be used instead of Equation 1.1 (see Background of the Invention). In the above equation, multiplication by 3 can be achieved by (bit) shift and (1) addition. Dividing by 3 is more time-consuming. In this case, the rightmost index is 2N-1, Y by Equation 1.2_2N-2There is no problem in calculating (see Background of the Invention). If the index of the rightmost point is an even number (for example, 2N), there is no problem with Equation 1.1, but there is a missing value in Equation 1.2. The purpose here is only the odd index Y calculated earlier, Y in this case₁And Y₃Is to subtract the estimated value of Y from the even number of X using. This estimate requested at index 2N can be obtained by linear extrapolation as described above. The appropriate formula is given by Equation 1.2R:<maths num="11"><img file="JP2010141922A_D0011.tif" /></maths>

The corresponding situation also applies to the left boundary. An edge filter is applied that performs the required extrapolation from the right side (inside) rather than from the left side. In this case, the appropriate filter is expressed by the following equations 1.1L and 1.2L.<maths num="12"><img file="JP2010141922A_D0012.tif" /></maths>

The inverse transformation filter for these extrapolated boundary filters can be obtained in the same way as the original filter, i.e. by inverse substitution. This inverse transformation boundary filter can be used in place of the standard filter in exactly the same situation as using a forward boundary filter. Such a filter is expressed by the following equations 2.1Rinv, 2.2Rinv, 2.1Linv, and 2.2Linv.<maths num="13"><img file="JP2010141922A_D0013.tif" /></maths><maths num="14"><img file="JP2010141922A_D0014.tif" /></maths>

Thus, one embodiment can utilize a reformulation of the 5-3 filter that avoids the additional steps of the prior art while preserving the visual properties of the filter (eg, Equations 3.1, 3.1R, 3.2: , See 3.2L).<maths num="15"><img file="JP2010141922A_D0015.tif" /></maths>

In these formulas, certain coefficients are calculated with a 1/2 offset or bias to avoid the additions mentioned above. In this formulation, it seems that there are many additions of 1/2, but in the actual calculation, it is not necessary to add these. Equations 3.1 and 3.1R show that the effects of the 1/2 addition are offset, so it is not necessary to apply these additions to the input data. Instead, the term in parentheses (Y)₀+ 1/2) etc. can be understood as the name of the quantity to be actually calculated and stored as a coefficient and passed to the next level of the wavelet transform pyramid.

Just as in the previous case, the JPEG-2000 inverse filter can be reformulated as Equations 4.2, 4.2L, 4.1, 4.1R:<maths num="16"><img file="JP2010141922A_D0016.tif" /></maths>

As can be seen here, the value obtained as the input for the reverse calculation is the same term generated by the forward calculation in equations 3.1-3.2L, and the correction by 1/2 needs to be explicitly calculated. Is not at all.

In this way, the total number of arithmetic operations performed during the calculation of the wavelet transform is reduced.

(Optional features) Additional and optional features and techniques that can be used in connection with the systems and methods of Figures 2-5 are described below. Strictly speaking, these optional features are for illustrative purposes only and are not limited. Furthermore, these features can be realized independently of the systems and methods shown in FIGS. 2 to 5 above.

General behavior features In use, the transform module (eg, transform module 202 in Figure 2) can utilize a wavelet pyramid that acts as a filter bank that separates the image into subbands, each of which is about 1 Covers octaves (ie, factor 2). Each octave may have three sub-bands that correspond to horizontal, vertical, and checkerboard shapes. In one embodiment, the pyramid can generally be 3-5 levels deep to cover the same number of octaves. If the original image is even a little smooth, the wavelet coefficient will decrease rapidly. The image may have a 2/3 Holder coefficient, which roughly means that the image has 2/3 of the derivative. If the wavelet coefficients are arranged in ascending order of absolute value, these absolute values will be N.^-SWhere N is the position in the column and S is the smoothness of the image.

After forming the wavelet pyramid, the wavelet coefficient is scaled (enlarged / reduced, quantized) by a quantizer (for example, the quantizer 204 in Fig. 2) to view the viewing conditions and the human visual contrast sensitivity curve (CSF: Contrast). The result is consistent with the Sensitivity Curve). By considering the characteristics of the human visual system (HVS), the number of bits used to encode the chroma (saturation, saturation) subband can be significantly reduced.

The use of traditional arithmetic encoders (coders) can be avoided in order to provide feasible fast algorithms with minimal required silicon space. For example, as mentioned above, multipliers can be avoided because they are very expensive in the silicon domain. Moreover, such algorithms can have very good "fast paths" for each individual execution element.

The codec can use two interlaced video frame image groups (GOPs), edge filters for boundaries, intermediate field image compression, and block compression structures. Specific features of the realization for a small single chip can be as shown in Table 1 below. (table 1) One realization can use short wavelet bases, which are especially suitable for those who focus on natural scene images quantized to match the HVS. This realization can be achieved by addition and shift (shifting digits). The Mallat pyramid generated by applying 5 horizontal filters and 3 vertical filters for each field can be used. This produces filters with dynamic coefficients, which are the two coefficients in the lowpass filter and the two, four or six coefficients (12 wavelet subs) in the wavelet filter. Produces a band). The modified edge filter can be used near the boundaries of the block and the image, which allows the actual image values to be used. The resulting video pyramid has virtually zero columns, as well as virtually non-zero columns. Therefore, coding can be performed efficiently by table lookup (table lookup). -Another solution can use moving image compression with a 3D wavelet pyramid instead of the motion compensation search used in the MPEG-like method. Time-wise conversion compression can be applied to a 4-field GOP. A two-level time-malar pyramid can be used as a tensor product with a spatial pyramid. A linear edge filter can be used at the dense level and a modified Haar filter at the coarse level to generate four time subbands. Each of these time subbands is compressed. -The processing can be reduced to the processing of a block consisting of eight scanning lines, each of which has 32 pixels. This helps reduce the amount of RAM required to a value that allows the RAM to be placed inside the ASIC itself. This reduces the number of chips and makes it easy to meet RAM bandwidth requirements. The compression process can be performed on a stripe-by-stripe basis (two passes per stripe). Yet another embodiment can use the quantization of the wavelet coefficients to achieve further improvements in compression. The denominator of quantization is a power of 2, which can be achieved by shifting. Quantization can be a process of assigning a scaling coefficient to each subband, and the scaling coefficient is converted into an integer by multiplying the scaling coefficient corresponding to each coefficient in the subband.

Another option is to selectively replace the wavelet filter with a polyphase filter. In one embodiment, such replacement can be performed in the conversion module of the data compression / decompression system (eg, conversion module 202 and / or inverse conversion module 214 in FIG. 2). Of course, these features can be realized independently of the various other features described herein. More suitable information about this optional feature is described below.

In this embodiment, in the design of a video compression codec, a conventional [for example, Finite Impulse Response (FIR)] information discard or smoothing filter can be combined with a wavelet information storage filter. The FIR filter can be distinguished from the wavelet filter in that the FIR filter is used alone, whereas the wavelet filter is always complementary. Moreover, the FIR filters in the wavelet transform do not necessarily have a relationship with each other as a polyphase filter bank.

Video compression can be performed in a three-step process, sometimes adding other steps, but the three main steps are transformation, quantization, and entry coding, as described above. .. These operations usually only discard information during quantization, as is commonly done. In fact, if this operation is omitted, a lossless compression method can be used. However, lossless compression is limited to compression ratios that are much smaller than lossy compression, and lossless compression is information that makes no visual difference in the results of decoding using the human visual system, or Discard information that can ignore visual differences.

One class of visual information that can be lost in acceptable results is fine information. Most conversion processes used for video compression can discard fine information through quantization steps, but these conversion processes have lower efficiency or lower visual fidelity than the realization of a direct lowpass filter. Perform the conversion.

One way to achieve a smoothing filter is by using a FIR structure. An alternative way to implement a smoothing filter is by using an Infinite Impulse Response (IIR) structure.

When changing the size of an image or data sequence, a Polyphase Filter Bank (PFB) consisting of related FIR filters can be used. Such a method processes an image by removing some detail and producing a corresponding smaller image for further processing.

A polyphase filter bank can include a set of FIR filters that share the same band or frequency selection characteristics but produce pixels interpolated at different positions on or between samples.

For example, a polyphase filter bank can be used to reduce an image (ie, a frame of video) to 2/3 of its original width. The polymorphic filter bank calculates interpolated pixels in the middle of each of the original pixels, calculates the pixels smoothed to the original position, and 1 for every 3 pixels of the resulting pixel flow (pixel stream). This is done by retaining only the pixels.

This method allows the calculation of unretained pixels to be omitted, resulting in a more efficient method of reducing the size of the image. This process can easily be extended to other rational, partial resizing. In this way, the polyphase filter bank can smoothly remove small amounts of microscopic parts and scale the image with a factor of less than 1. This coefficient can be greater than 1/2.

The present invention combines the benefits of smooth detail removal with the image quality of wavelet transform coding by using a polymorphic filter as the first step in a wavelet-based image compression process. By using this combination, the advantage of using a multi-phase bank filter is to remove smooth, high-quality, artifact-free minute parts and the bits needed to represent these fine parts. Can be added to the well-known advantages of fast and efficient computation and high image quality by using the wavelet transform as the basis for image and video compression.

In the first embodiment of the method of the invention, the polymorphic filter bank is first applied in one direction, usually the horizontal direction of the image, and then the wavelet transform is performed prior to the quantization and coding in the conventional method. Can be applied to images.

In the second embodiment of the method of the present invention, the polymorphic filter can be applied in this direction before the first wavelet operation in a particular direction, but it can also be done after the wavelet operation in the other direction.

In yet another embodiment, for each of several directions, a polymorphic filter can be applied in this direction before the first wavelet operation in this direction, but it can also be done after the wavelet operation in the other direction. possible.

The method of the present invention, which applies a lossless filtering step prior to at least some wavelet or DCT transform steps, has several advantages. For example, filters such as FIR design or polyphase design, not limited to wavelet-like functions, can be designed for higher quality and fewer artifacts. Wavelet filters can be designed in pairs that divide the information into two parts without discarding the information.

Applying a conversion operation before and after the conversion operation performs the conversion operation on less data, thus reducing the operation time and reducing the intermediate storage capacity during the operation. It means that you can. Since conversion is generally an expensive part of the compression process, this reduction results in a significant improvement in speed and efficiency throughout the compression process.

Square wavelet transform using pile As yet another operation, the amount of calculation related to entropy coding is reduced by reducing the amount of data. In one embodiment, these reductions are made in the quantizer of a data compression / decompression system (see quantizer 204 in Figure 2). Of course, these features can be realized independently of the various other features described herein. More suitable information about this optional feature is provided below.

In this embodiment, the pile is used as an operation in the decoding operation, so that the pile can be immediately used in the operation of the subsequent steps. Further information on the pile can be found in Appendix B.

Providing what is called a sparse representation of matrix data is well known in certain computational fields. A normal matrix is represented as a complete array of numbers that are matrix elements and is referred to as a "dense" representation. Some program packages store, transform, and manipulate "lean matrices", where 0 entries are not explicitly represented one by one, but implicitly. One of these "lean" representations is zero-run (zero column length) coding, which represents zeros by the number of zeros that occur together. This number itself can be zero (when two nonzero values are adjacent), one (single zero value), or greater.

However, if the video data is not a matrix, matrix operations (ie, multiplication, inverse matrix calculation, eigendecomposition, etc.) are usually not applied to this video data. The basic principles of lean matrix operations can be taken out and transferred to video conversion.

Simply put, a pile consists of an array of pairs, each pair giving the address (or offset) of the normal data of a nonzero item (item) along with the value of that item. These addresses or offsets are in a sorted order, so look at the pile and take into account the non-zero elements in their entire dataset. By performing the operation, the entire data can be examined from corner to corner.

A pile is a computer that processes data in parallel using the same operation performed on several data items at once (that is: SIMD processor (Single Instruction stream-Multiple Data stream Processor)). Specially designed to be efficiently feasible on relatively expensive computers that process)) and control condition transitions. These processors are commonly used to handle video and audio and are sometimes referred to as "media processors."

Some operation needs to be performed on the two datasets, and when both datasets are sparse, there are considerations that were not made when the data was densely represented. That is, "when will the data items match each other?"

In operations on two datasets represented as piles, the basic operation for identifying matching data items is called "match and merge". When examining two piles, the address from each pile and the address to which this output value is assigned immediately after the output value is generated can be obtained for each operation after the start. To find the next address that can generate and assign a value, we can find the smaller of the two addresses represented by the two input piles. If both piles agree on this address, there are data items available from each pile, and these two values can be manipulated to produce the desired result. You can then proceed to the next item on both piles.

If the next address in the two piles is different, there is a non-zero value in one pile (dataset) but zero in the other dataset (implicitly represented by the pile). There are values, and one value and zero can be operated on to produce a certain value. Alternatively, if the input is 0 and the operation being performed produces 0, then no value is generated. In either case, you can proceed to the next item only for piles with the smaller address.

Place the resulting value in a place, either in a dense array (by always explicitly writing a 0 when advancing more than one address) or in the output pile.

As mentioned above, the wavelet transform is the iterative application of a wavelet filter pair to a set of data, which may be one-dimensional or two-dimensional or more. For video compression, 2D wavelet transforms (horizontal and vertical) or 3D wavelet transforms (horizontal, vertical, and time) can be used.

The intent of the conversion stage in the video compressor is to collect the energy or information of the original image and make it as small as possible by utilizing local similarities and patterns in the image or image sequence (column). It is in. No compressor can compress all possible inputs as much as possible, but design the compressors to work well for "general" inputs, and these compressors are "random" or Failure to compress "pathological" input can be ignored.

If the conversion works well and the image information is well collected into a small number of conversion coefficients, most of the remaining coefficients will be zero.

As mentioned above, quantizing the results is also a step in the video compressor. At this stage, calculated values close to 0 are represented by 0. Rather than quantizing the final transform result, or quantizing the coefficients calculated in addition to the quantization of the final transform result, or rather than quantizing the coefficients calculated during the wavelet transform calculation. It may be desirable to quantize.

Therefore, we may get many 0s in some wavelet coefficient data, which can happen while we need to do more operations on the data.

In addition to this, when decoding to display a compressed image or video, from the significant entropy-encoded coefficients towards a fully filled (valued) display image. Can do the work of. The first decoding step, the general output of decoding the entropy code, is a set of significant coefficients with a large number of insignificant coefficients that can be considered to be 0 by default.

When this happens, it is worth converting dense data with many zeros into a sparse representation, which can be done by piled the data as described above. The pile representation is similar to the zero-run representation, but usually stores the address or offset rather than the run length (run length: address difference). This allows for both high-speed processing to create the pile and later extend the pile to a dense representation.

In the case of decoding, it is more natural to construct the pile directly in the entropy decoder rather than in a dense format.

The wavelet transform process results in some cases where it undergoes a pile process, which are shown in Table 2 below. (Table 2) Extension, pile both bands Extension, pile one band Extension and input are piled, and output is dense Compression, input is dense and output is piled

Consider one example: decoding a compressed video frame, where the coding process produces a large number of coefficients that are quantized to zero. The first step of decompression undoes the nonzero coefficient entropy or bit coding and gives the value of each value in the frame and its position. This is just information expressed in piles, and rather than immediately extending this information to a dense representation by putting explicit values in all the zeros in between, we use piles to store this information. Is very convenient.

At this stage, there are coefficients that can be manipulated by the inverse wavelet transform. The final result of the inverse transformation is an image that is stretched and ready to display, and this image is only partially grained.

The first stage of the inverse wavelet transform (as well as each stage) is a filter operation that takes data from two regions or "bandwidths" of coefficient data and combines these data into an intermediate band. Intermediate bandwidth is used at a further stage in the same process. In this first stage, the data for both bands is sparse and is represented by a pile. The output at this stage can also be piled up and does not need to be set to zero. The operations in Table 3 below are for the "bandwidth" pile P.₁And P₂The result is generated in the form of a new pile R, and the filter calculation step W (p, q) is executed on the coefficient pairs from the two bands. (Table 3) while not both EOF (P₁), EOF (P₂) { I₁= 0; I₂= 0; guard (P₁.index P₂.index, Pile_Read (P₁, I₁)); guard (P₁.index P₂.index, Pile_Read (P₂, I₂)); Conditional_Append (R, true, W (I)₁, I₂));}; Destroy_Pile (P₁); Destroy_Pile (P₂);

The above operations can be expanded for parallel operations as shown in Appendix B.

The time required to calculate the wavelet transform can be reduced by using the sparse representation, pile, for intermediate results with many zero values. Such methods improve the performance and computational efficiency of wavelet-based image and video compression products.

Conversion range limit Yet another option is to reduce the amount of computation associated with reconstructing data values into a predetermined data range. Such operations can be reduced by performing only a single clip operation. In one embodiment, these reductions are made within the dequantization module of the data compression / decompression system (see dequantizer 212 in Figure 2). Of course, these features can be realized independently of the various other features described herein. More suitable information about this optional feature is described below.

In digital image compression and digital video compression methods, an image (or frame) is represented as an array of numbers, where each number represents the brightness of the area or the amount of a particular color (eg, red) within this area. These areas are referred to as pixels, and the above numerical values are referred to as sample values or component values.

Image compression or video compression is done in a wide variety of different ways. As mentioned above, many of these methods involve transformation operations as steps, transforming an array of samples representing an image into different arrays of numbers called coefficients through a series of arithmetic operations. The numbers include image information, but the individual numbers do not correspond to the brightness or color of a small area. The transformation contains the same image information, but this information is distributed over these numbers in a favorable manner for further computation of the compression method.

When reproducing an image or frame compressed by such a method, the compressed data must be decompressed. This usually involves taking an array of coefficients and calculating the inverse transformation to produce an array of samples.

Image or frame samples are typically represented by small size (digits), usually 8-binary bit integers. These 8-bit numbers can only represent 256 different values, and in these applications these values are generally considered to be integers in the range 0-255 [0, 255].

Many standards and operating conditions impose a more constrained range than this range. For example, the sample values of the pixel components (Y, U, V) in CCIR-601 (ITU-R BT. 601-4) digital video are in the range smaller than [0, 255]. In particular, the effective range of the brightness Y component in the lighted part of the screen is specified to be within [16, 235], and the range of chroma (chromaticity) U, V is within [16, 240]. It is specified to be. Values outside these ranges have meanings other than brightness and represent, for example, sync events.

Image and video compression methods can be divided into two categories: lossless and lossy. Lossless compression works in such a way that decompression produces exactly the same values provided for compression. For these methods, there is no range problem because the output occupies the same range of numbers as the input.

However, lossy compression only produces an decompressed output that is supposed to approximate the original input and does not match bit by bit. Taking advantage of this freedom of changing the image slightly, the lossy method can obtain a much larger compression ratio.

In the stretched portion of the lossy compression method, the calculated sample is not guaranteed to be identical to the corresponding original sample and therefore is not guaranteed to occupy the same range of values. Therefore, in order to satisfy the range condition of the image standard, it is necessary to include a step of limiting or clipping the calculated value to the specified range.

Here's an easy way to perform this clipping step: For each calculated sample s, test (determine) whether s&gt; max (maximum), and if so, s. Set s = max to test if s &lt;min (minimum), and if so, set s = min.

Another way to perform this step is to use the MAX and MIN operators found on one computing platform, and again two operations can be applied to each sample. Both of these methods, and many others, are more expensive to calculate than simple arithmetic operations such as addition and subtraction.

This process is an important part of the calculation in the stretch method, as it can be performed separately for all sample values (all pixels) in the image or frame. It should be noted that usually sufficient, both of the above tests have not been performed on almost all calculated samples that are within the required range, and therefore both tests must be calculated.

The conversion operations described above generally have the following characteristics: One of the resulting coefficients represents the level of brightness of the entire frame or the main part of the frame (blocks in MPEG technology). This coefficient is called the DC coefficient. Due to the way the transformation is calculated, changing the DC coefficient will change the values of all samples in the frame or block in the same way, i.e. in proportion to the changes made. Thus, for example, just before calculating the inverse transformation, the value of any sample in the block can be increased by the same amount by adding a constant appropriately selected for the block to the DC coefficient.

Computational (computer) engines that perform compression methods generally have arithmetic instructions with saturation characteristics, and when the result is calculated, the result is the representation range of the container ([0, 255] for 8-bit quantities). If so, clip the result to within this range. For example, if you give a saturation subtraction instruction a value of 4 and 9, the result (4-9 =) -5 will be clipped and the result 0 will be returned instead. Similarly, the saturation addition instruction returns a result of 255 for 250 + 10.

A low-cost method of clipping pixel component values in many compression methods is described below, which derives from decoding to the appropriate limits. This example executes one of the two clips with saturation arithmetic calculations by biasing the partial values and leaving only one of the MAX / MIN operators. The required range is [llim (lower limit), ulim (upper limit)] = [16, A more detailed example of 240] is shown in Table 4 below. (Table 4) 1. Bias the DC coefficients within each block, which offsets each part by a negative value -16 (generalized representation is -llim) after all conversion filters. Cost: One arithmetic operation per image or block. 2. Make sure that the final arithmetic step of the inverse transformation is saturated (clip) to 0. Cost: No cost for most computing engines. Apply the (split) MAX operation (the operation that maximizes to 224) by 3.224 (generalized expression is ulim-llim). Cost: One MAX operation per sample. 4. Use ADD 16 (generalized expression llim) (the operation of adding 16) to remove the bias. This bias removal does not need to be performed by a saturation arithmetic operation, as there can be no overflow due to the previous MAX operation. Cost: One ADD (addition) operation per sample.

As is clear here, the required range-limited calculation costs are from 2 MAX / MIN (maximization / minimization) operations per sample to 1 ADD (addition) operation per block and 1 MAX (1 time). It is reduced to (maximize) operation and one simple ADD (addition) operation.

On some computational engines, such as the EQUATOR MAP-CA processor, the savings from using this method can be much greater than immediately apparent from the above description. On these engines, several samples can be combined into words for simultaneous computation. However, these split operations are limited to specific parts of the processor and can be a source of performance limitation in compression applications. On such an engine, it is very important that the ADD operation in step 4 above cannot overflow. In step 4, it is not necessary to use the spatially divided ADD operation, but it is possible to perform the operation on several samples at once as if they were divided by using the normal ADD operation. This normal operation can be performed using the part of the processor that is not so heavily loaded and can be duplicated or concurrently executed with other necessary division operations, resulting in a large amount of inverse conversion calculation time. Can save money.

FIG. 6 shows a system 600 that compresses data according to an embodiment of the present invention. As an option, the system 600 can be implemented in connection with what has been described above. But, of course, the system 600 can be realized in relation to any desire.

The system 600 comprises an encoder 602 embodied on a single device 604, which encodes the data to produce first compressed data in first format. Further, the transcoder 606 is embodied on the same single device 604 as the encoder 602, and the transcoder 606 transcodes the first compressed data to generate the second compressed data in the second format.

During use, the data is received on a single device 604. Such data is encoded using a single device 604 to produce first compressed data in first format. Further, the first compressed data is code-converted using a single device 604 to generate the second compressed data in the second format.

In one embodiment, the coding can be done in real time. Further, the code conversion can be performed offline. In another embodiment, the first compressed data is code-translated to generate the second compressed data in the second format adapted to match the capacity of the communication network coupled to the single device 604.

As an option, the first decoder can be used to perform the coding. Further, as shown in FIG. 6, the code conversion can be performed by using the decoder and the second encoder.

In addition, the first format can include wavelet-based formats. In addition, the second format can include DCT-based formats. In one particular embodiment, the second format can include an MPEG format. More suitable information about additional and optional features is provided below.

As mentioned above, there are several modes of communication using image and video sequences. In addition to direct real-time viewing, an image or video sequence can be captured and transmitted at a later time, after which the time may be delayed immediately after capture or to an earlier time. ..

In addition, reception of the video sequence can be done in real-time mode, where the video is watched but not remembered, as if watching television, or in other modes where the sequence is remembered for later viewing.

These various options, in addition to other combinations, are incorporated into three usage scenarios. These three scenarios are as follows. 1. The videophone or picturephone (videophone) mentioned above, in which both the transmitter and receiver operate in real time. This operation requires all of the compression, coding, and decompression to be performed in real time at the rate at which the video is captured, and the transmission channel must carry the full rate (maximum speed) of the compressed video. 2. Stream operation that captures and stores video in the source or network for real-time viewing on the receiver. This operation requires real-time decoding, but allows the sequence to be processed prior to transmission. This mode requires at least a network-to-receiver transmission channel to carry the full rate of compressed video . In addition to this, for most transmission channels, the receiver must temporarily store (buffer) some amount of sequences to maintain smooth playback in the presence of fluctuations in transmission rate (speed). It doesn't become. 3. A message or file transfer mode in which the source captures and stores the video, transmits it to the receiver in non-real time, and stores it in the receiver for later playback. This mode allows operation on transmission channels where the full rate of real-time video is uncarryable, and allows the recipient to repeatedly play, pause, or otherwise control the viewing experience. To enable.

Images or videos that have been captured and compressed into one format can be converted to other compressed formats. This operation is called code conversion (transcoding). In the worst case, this operation is done by decompressing the input format into a complete image or video and then compressing it into the desired output format. For many format pairs, there may be cheaper and more available methods than this worst case method.

In many networks, such as cell phone networks, different users may prefer or need different formats for images or videos. This can happen even if all users stick to the MPEG-4 standard, for example, because these standards offer many choices for profile, size, and other parameters. Because. For this and other reasons, it may be desirable for the transmitter and receiver to negotiate the format to be used in a particular transmission. In the simplest case, each device provides a list of formats that it can handle, and both select one that is acceptable to each other from the intersection of both lists. There are more complex forms of such negotiation, but the general effect is the same, with the sender knowing only the format to be transmitted after the connection is initiated.

When code conversion is required as part of the connection, the code conversion can be performed either at the source device or at an intermediate location. Some networks can provide code conversion services as part of their network operation to provide intercommunication between devices with completely different capabilities. This helps keep the complexity of the mobile device and therefore the cost low.

Since the video data rate (speed) and the transmission channel rate described above are different, it may be advantageous to operate in the next new mode. The device captures the video and compresses the video in real time using the less complex compression method described below to store the compressed video sequence. Later, the device can code translate this video sequence into a format acceptable to the recipient or network. This allows for low power operation, long battery life, and simpler in-device circuitry, along with full compatibility with network format standards.

The optional advantage of this behavioral style is flexibility, and the choice of real-time compression does not limit the range of receivers with which the device can communicate directly. As mentioned above, the transmission format can be negotiated at the time of the transfer call. In this way, the device can support a wider range of formats, because the device does not need to have its own wide-optimized real-time realization.

Another optional advantage of the behavioral styles mentioned above is that the code conversion does not have to operate at the speed of video capture, but can be matched to the speed of the transmission network, which is often much lower than this speed. Is. Lower speed code conversions can be performed on smaller circuits that consume less power than standard real-time processors consume. Therefore, the power consumption of the entire device, the battery life of the device, the complexity, and the cost are reduced.

Yet another alternative advantage of this style of behavior is that image and video transmission can be carried from high-cost hours, such as daytime phone charges, to lower-cost times, such as nighttime charges (or nighttime charges). With the current cell phone billing system, it can be postponed until (even free time).

The transmission may be at a lower cost at other times due to factors other than the time zone. For example, cell phones are charged lower when they return to their home area (our service area) than when they are "roaming (calls in another company's service area)".

The postponed transmission described above does not necessarily require the use of a device to perform any postponed operation. The transmission can be automatically scheduled by the device based on the information that the device has about the transmission rate and the transmission schedule. Therefore, the convenience of the user is maintained.

Of course, some messages are more urgent to be recognized than others, and users can easily specify whether or not to postpone transmission and when to postpone it.

When transferring images and videos in non-real time, the device user may want to make a call, receive a call, or be disconnected for some other reason while the transfer is in progress. There can be. It is well known in the field of computer networks to provide information that allows the resumption of interrupted transfers without having to retransmit the already well-transferred portion of the information.

Such interruptable transfers allow both intentional interruptions such as making calls and unintentional interruptions such as loss of connection.

The receiver does not have to have the capacity to store the entire video sequence. The source device for code conversion can make transmissions to streaming mode receivers, including receivers that are much simpler and much less capable than transmitters. This allows advanced code conversion devices to be incorporated into existing device networks.

Standard image and video formats provide error detection, error correction, and burst error control. By transcribing to these standard formats, the device can take full advantage of standard error recovery features while using low complexity and low power capture and compression methods.

The idea of capturing a signal of interest using low-complexity real-time processing and later transcribing it into a format more suitable for transmission, storage, and further processing is the idea of non-image and video signals, non-wireless transmission, and It can also be applied to devices other than mobile personal terminals. For example, military intelligence sensing, infrared remote sensing, sonar, spectroscopic telescopes, radio telescope signals, SETI (Searching for Interstellar Communications) channels, biochemical measurements, seismic signals, and many others are the basis for this. The method can be used.

Figure 7 shows a system 700 that uses multiple encoders 702 on a single integrated circuit 704 (eg, an ASIC) to compress data. As an option, the system 700 can be implemented in relation to the concepts described above. But, of course, the system 700 can be implemented in relation to whatever is desired.

As shown in the figure, a first encoder that encodes a first set of data is embodied on a single integrated circuit 704. Further, the second encoder that encodes the second set of data is embodied on the same single integrated circuit 704 as the first encoder. Of course, for the same purpose, a larger number of encoders can be embodied on the single integrated circuit 704.

During use, the data is received on a single integrated circuit 704. This data is then encoded using a plurality of encoders 702 built into the single integrated circuit 704.

In one embodiment, multiple channels on a single integrated circuit 704 can be utilized to encode the data. In addition, the data can be encoded in wavelet format.

Many video compression applications are better done by multiple coding or decoding stages, including ASICs. Examples are the categories of personal video recorders (PVRs) or digital video recorders (DVRs), such as TiVo® and replay TV products. The compression and decompression processes must be performed at the same time. Another example is a video surveillance recorder, where a large number of video signals from a camera must be coupled, multiplexed, compressed, and recorded.

Placing several compression circuits on a single ASIC, or a combination of compression and extension circuits on a single ASIC, offers both direct and indirect advantages. The direct advantages are reduced package count, reduced pin count, reduced power consumption, and reduced circuit board area. All of these contribute to reducing product costs.

The indirect advantage includes the ability to incorporate the video selection circuit and the multiplexing circuit on the same chip, further reducing the number of pins and board area.

There is a video compression method, for example, the algorithms developed by Droplet Technology, Inc.® and described with reference to Figures 2-5, which have the circuits required to implement them. , Much less than traditional standard compression methods. Multiple examples of these advanced compression methods can be integrated on a single ASIC or on other integrated circuits due to their excellent design.

Other single module systems and methods for compressing data are provided. During use, it utilizes a single module to receive photons. After that, the compressed data expressing these photons is output using this single module.

The option is to encode the compressed data in wavelet format. In addition, the conversion operations related to coding are performed in analog. The single module can further include an image sensor (imager).

This embodiment can be implemented to configure an imaging array-CMOS or CCD camera or other device to facilitate the entire process of capturing and transmitting compressed digital video.

Directly digitized images and videos occupy a large number of bits and generally compress images and videos for storage, transmission, and other uses. Several basic compression methods, and a large number of these variants are known. The general method is characterized by a three-step process: transformation, quantization, and entropy coding.

The intent of the conversion stage in a video compressor is to collect the energy or information of the original image and make it as small as possible by utilizing local similarities and patterns in the image or image sequence. This example works well for "general" inputs and ignores uncompressed "random" or "pathological" inputs.

Many image and video compression methods, such as JPEG [1], MPEG-2 [2], and MPEG-4 [4], use the Discrete Cosine Transform (DCT) as the conversion stage.

Some newer image and video compression methods, such as JPEG-2000 [3] and MPEG-4 texture [4], use various wavelet transforms as the conversion stage.

The wavelet transform consists of iteratively applying a wavelet filter pair to a set of data, which may be one-dimensional or two-dimensional or more. 2-D wavelet transforms (horizontal and vertical) can be used for image compression, and 3-D wavelet transforms (horizontal, vertical, and time) can be used for video compression.

A wavelet filter pair processes an image (or part of an image) to produce two images, each of which is half the size of the input image, one of which is "lowpass". Or it can be thought of as "average" or "blurring", and the other can be thought of as "highpass" or "details" or "edge". The complete information of the input image is preserved and the original image can be accurately reconstructed from the converted image pair (often). Wavelet filter pairs generally process an image in one dimension, which is either horizontal, vertical, and time (over a time series of frames). The complete wavelet transform consists of a series of steps that are sequentially applied to several dimensions. In general, not all the results of the previous step are passed on to the subsequent steps, and high-pass images may be preserved without further filtering.

The camera has an imaging device at its heart, which records it for later display and other uses in response to changing brightness and color of light. Common imaging devices for today's digital still cameras and camcorders are CCD and CMOS arrays. The method in which both of them accumulate electric charges in response to light for each pixel and transfer and read out the amount of the electric charges is different between them.

CMOS (Complementary Metal-Oxide Semiconductor) imaging devices are a newer technology and can be manufactured at a lower cost than CCD. A key advantage of CMOS imaging devices is that the processing of the imaging chip is fairly close to that of a digital logic chip. This makes it easier to include control and other functions on the same chip. However, both types of chips will necessarily consist of the lowest level of analog circuitry to measure the analog charge or voltage or current that represents the visible amount of light.

CMOS imaging devices are very similar in structure to DRAM (Dynamic Random-Access Memory), a metal trace that traverses an array to represent the light visible in a pixel. Transfer to the edge of the array along the (line) grid. This reading method is a standard practice for memory chips and is well developed in the industry.

CCD imaging devices are an older technology, but are well developed to provide lower noise and better sensitivity. CCDs (Charge-Coupled Devices) transfer the charge that represents the light visible to a pixel to the edge of the array by passing it from cell to cell like a bucket relay.

A CMOS or CCD imaging device is a digital memory device in that the charge transferred to the edge of the array represents not only a "0" or "1" bit value, but also a range of brightness values. different. Therefore, an analog-to-digital converter is required. In proceeding with this conversion, the signal is often amplified and subject to other processing to counteract errors and variations in chip manufacturing and operation. A common processing step is "correlated double sampling", where a dark sample is taken and stored as a measure of leakage current for this circuit portion, and this dark sample is subtracted from the image sample. Reduce noise patterns.

The analog processing is done within the differential amplifier, which is primarily a circuit that responds to the difference between the inputs rather than the absolute value of either input.

At some point in the processing chain between the capture of light and the stored digital image, the signal must be converted from an analog (charge, voltage, or current) representation to a digital representation.

Since you can choose to perform the analog-to-digital conversion earlier or later in the chain, you have the option of performing some steps in the entire process in analog or digital format. ..

A wavelet filter pair, which is a step of a wavelet, consists of a very simple set of addition and subtraction of adjacent pixel values and neighboring pixel values in some realizations. For example, the only useful filter pair called "Harr Wevelet" is the sum and difference of the following equations 1.1H and 1.2H. L_n= X_2n+ X_{2n + 1} Equation 1.1H L_n= X_2n-X_{2n + 1} Equation 1.2H

The above equation generates one sample of the "High" converted image and one sample of the "Low" converted image from the same two samples of the input image "X".

Other wavelet filters are also possible and used, some are very complex, but some are simple enough to perform a few Harr steps, summing up these Harr steps, Scale (enlarge / reduce) with a certain amount.

For example, one of the conversions specified in the JPEG-2000 standard [1] is the reversible 5-3 conversion described in Equations 1.1 and 1.2.

As can be seen in the equation, the entire wavelet filter pair performs 5 addition / subtraction operations and 2 scaling operations, and the floor operation disappears in the continuous analog region.

It is easy to sum up analog values, which is naturally achieved by differential amplifiers (both for addition and subtraction), and scaling by constant quantity is the simplest of all operations on analog signals. Yes, it turns out that it only needs one or two registers.

In contrast, summing values in the digital domain requires a bit-by-bit add logic circuit and a chain of carry (carry), which is easy to scale by a certain fixed quantity, but is common. Scaling is not cheap in digital logic circuits.

Since CMOS and CCD imaging devices currently use differential amplifiers to amplify and subtract noise from pixel samples on the chip, some simple processing steps are required before the analog-to-digital conversion. It's fairly easy to run on a chip. Performing these steps will add some analog circuitry to the chip, but can be a small amount of circuitry.

For some implementations of the wavelet transform, including the preferred ones, the first step of the operation has proved to be the most expensive. This is because each of the first steps reduces the amount of image to be processed in the subsequent stages and does not necessarily further process the "highpass" image output by each filter stage. Therefore, by implementing the first step or the first few steps before performing the analog-to-digital conversion, the digital processing can be significantly reduced, because it must be processed digitally. Is only a "low pass" image. This advantage is either to reduce the chip area occupied by the digital circuit by reducing the amount of the digital circuit, or to operate the digital circuit at a lower speed to reduce its power consumption and heat generation. It can be useful for digital appliances.

The conversion stage for image or video compression can be performed using the DCT, which transforms the image into a spectrum, and a sequential sample of this spectrum represents the content of a range of spatial frequencies within the image. .. Some implementations of the DCT use Haar steps, which can also benefit from doing them in analog.

Wavelet transforms can usually be calculated with a horizontal filter pair as the first step. This is also considered to be convenient for analog filtering. Two horizontal steps can be performed before the first vertical filter step, which is also convenient in analog.

The vertical filter step requires the presence of vertically adjacent pixels at the same time. In the conventional raster-ordered image scanning (horizontal lines are sequentially scanned from the upper left to the lower right), such pixels appear at large times (line times). However, in a chip image sensor such as a CMOS image sensor, it is reasonable to consider reorganizing the scan order so that several lines appear together, and then the vertical filter steps are also analog. The execution can be achieved before or after the first horizontal filter step.

Imaging chips that capture color images typically place a color filter in front of each pixel, limiting this pixel to one of a red, green, or blue response. These filters are placed in a pattern where all three colors are sampled adjacently throughout the image.

However, the digital video standard prefers component arrangements other than RGB. The most widely used are YUV or YC_{b b}C_rHere, the Y component expresses the brightness or "luminance" of black and white, and the U and V components express the color difference between blue or red and the brightness, respectively. The reason for this representation is that the human visual response has lower resolution in the C component, thus allowing a digital representation of smaller images. The YUV representation is also convenient for compression. Some color imaging chips provide a circuit that converts RGB pixel values into YUV values in either analog (before conversion) or digital (after conversion).

The color transform and wavelet filter step can be combined in one of several ways. For example, the analog color transform can be preceded by the first analog wavelet filter step, in which case the wavelet filter acts on the entire band of the Y component and half the band of the U and V components. Alternatively, the wavelet filter is first applied to the R, G, and B components from the imaging array, followed by a color conversion to YUV, in which case the filter is in full band of the three component signals. Acts on.

In other configurations, all conventional color conversion steps are omitted and the RGB component is supplied to the wavelet transform. There is a version of the wavelet transform that achieves the conversion to YUV as part of its operation. In this configuration, the analog circuit that performs the color conversion is replaced with the analog circuit that performs the first wavelet conversion, the digital circuit is reduced without increasing the net of the analog circuit, and the interface with the digital wavelet compression process is greatly improved. To clarify.

Thus, a method has been shown to make the subsystem that captures compressed digital video more efficient by including the analog operation of the first wavelet filter step. This can also be done for monochrome images, and in some ways can be combined with the color conversion stage of a color digital image sensor. This method improves the performance and computational efficiency of wavelet-based image and video compression products.

Although various examples have been described above, it is clear that these are provided only as examples and are not limited. Therefore, the scope of the preferred examples of the present invention should not be limited by any of the preferred examples described above, but only by the claims and their equivalents.

(Appendix A) 3 values [X_2N-1 X_2N-2 X_2N-4], And requires three coefficients for the following quadratic equations.<maths num="17"><img file="JP2010141922A_D0017.tif" /></maths> Half the negative value of the quadratic derivative is-(1/2) 2a₂So the important thing is a₂Only. In this case, the quadratic equation is more easily found as in the following equation.<maths num="18"><img file="JP2010141922A_D0018.tif" /></maths> Three linear equations with a Vandermonde type coefficient matrix can be solved as follows.<maths num="19"><img file="JP2010141922A_D0019.tif" /></maths> Here, the negative value of half of the quadratic derivative is as follows.<maths num="20"><img file="JP2010141922A_D0020.tif" /></maths>

(Appendix B) Introduction to the pile Parallel processors have high processing speeds (eg, "if", "for", "while" statements) when the required algorithm has narrow data widths, serial data dependencies, or frequent control statements (eg, "if", "for", "while" statements). Difficult to program for (throughput). This example overcomes these three problems alone or in combination. Entropy encoding applications are an important class of applications that have all three of these problems.

Parallel processing There are three types of parallelization that can be used advantageously in the processor: 1) The first type is supported by multiple functional units, and processing proceeds simultaneously within each functional unit. The superscala processor architecture and VLIW (Very Long Instruction Word: 128-bit or more instruction length parallel processing) processor architecture make it possible to issue instructions to each of several functional units in the same cycle. In general, latency or completion time varies between one type of functional unit and another. The simplest function (eg bitwise AND) usually completes in one cycle, while the floating point addition function requires three or more cycles. The second type of parallelism is supported by pipelined individual functions. For example, floating point addition takes three cycles to complete and can be achieved with three consecutive sub-functions, each sub-function taking one cycle. By providing a pipeline register between the sub-functions, the first sub-function of the second floating-point addition can be started on the same cycle as the cycle in which the first floating-point addition started the second sub-function. it can. By this means, even if each floating point addition takes 3 cycles to complete, the floating point addition can be started and ended in all the cycles. 3) The third type of parallelism available is to assign field divisions of different words to different instants of the same calculation. For example, a 32-bit word on a 32-bit processor is divided into four field compartments, each of which is 8-bit. All four values can be processed with the same single instruction if the data item is small enough to fit in 8 bits. During each single cycle, the number of data items that is equal to the product of the number of field divisions multiplied by the number of functional unit starts can be processed.

Loop unrolling There is a conventional common way of programming multiple and / or pipelined functional units, finding many examples of the same calculation and performing the corresponding operations from each example together. These examples can be generated by loop unrolling techniques or by other sources of the same calculation. Loop unrolling is a generally applicable technique, but specific examples can help you learn its benefits. For example, consider the following program A). for i = 0: 1: 255, {S (i)}; Here, the field S (i) is a sequence of operations that depends on i {S₁(i); S₂(i); S₃(i); S₄(i); S₅(i);} And if j i, the operation S (i) is completely independent of the operation S (j). Operation S₁(i); S₂(i); S₃(i); S₄(i); S₅It cannot be assumed that (i); are independent of each other, and conversely, the dependence of one operation on the next prohibits sorting (of the operation). It can also be assumed that these same dependencies require that the next operation not be started until the previous operation is completed. If each (pipelined) operation requires two cycles to complete (even if the pipelined execution unit produces new results in each cycle), then the above five operation columns are complete. Requires 10 cycles. In addition to this, loop branching is generally done by programming tools S₄(i) and S₅If (i) cannot overlap with the branch delay, it requires 3 cycles per loop. If the branch delays can be duplicated, program A) requires 256/4 × 10 = 640 cycles to complete, and if the branch delays cannot be duplicated, program A) requires 256/4 × 13 = 832 cycles to complete. Next program B) for n = 0: 4: 255, {S (n); S (n + 1); S (n + 2); S (n + 3);}; Is completely equivalent to program A). The loop has been "unrolled" four times. This reduces expensive control flow changes by a factor of four. More importantly, this program provides the opportunity to sort each of the four constructive operations S (i). Therefore, programs A) and B) are equivalent to the following program C). for n = 0: 4: 255, {S₁(n); S₂(n); S₃(n); S₄(n); S₅(n); S₁(n + 1); S₂(n + 1); S₃(n + 1); S₄(n + 1); S₅(n + 1); S₁(n + 2); S₂(n + 2); S₃(n + 2); S₄(n + 2); S₅(n + 2); S₁(n + 3); S₂(n + 3); S₃(n + 3); S₄(n + 3); S₅(n + 3); }; With the above assumptions about dependence and independence (independence), the following equivalent program D) can be created. for n = 0: 4: 255, {S₁(n); S₁(n + 1); S₁(n + 2); S₁(n + 3); S₂(n); S₂(n + 1); S₂(n + 2); S₂(n + 3); S₃(n); S₃(n + 1); S₃(n + 2); S₃(n + 3); S₄(n); S₄(n + 1); S₄(n + 3); S₄(n + 3); S₅(n); S₅(n + 1); S₅(n + 3); S₅(n + 3); }; In the first cycle, S₁(n); S₁(n + 1); can be issued, and in the second cycle, S₁(n + 2); S₁(n + 3); can be issued. At the beginning of the third cycle, S₁(n); S₁Complete (n + 1); (2 cycles have passed), so S₂(n); S₂(n + 1); can be issued. Therefore, program D) proceeds as follows: In each subsequent cycle, the following two operations can be issued, and the entire program can be executed in the same 10 cycles. Program D) runs in less than a quarter of the time of program A). The most parallel processors inevitably have conditional branch instructions, which require a delay of several cycles between the instruction itself and the point at which the branch actually takes place. Other instructions can be executed during this delay period. As long as the branching conditions are well known in advance and the compiler or other programming tool supports the execution of the instruction during the delay period, the cost of this branch is as low as the opportunity to issue a single instruction. .. This technique can also be applied to program A) because the branching condition (i = 255) is known at the top of the loop. Excessive unrolling goes against productivity. First, once all publishing opportunities (as in Program D) are taken advantage of, there is no further speedup due to additional unrolling. Second, each turn of the unrolled loop generally requires additional registers to hold state for a particular turn. The number of registers required is directly proportional to the number of unrolled turns. If the total number of registers required exceeds the number available, some registers must be "leaked" into the cache and returned at the next loop turn. If the unrolling of the loop does not eventually speed up, the instructions that need to be issued to support this spill and reload will increase the time of the program. There is an optimal value for the number of times these loops are unrolled.

Unrolling a loop with exception handling Now consider the following program A'). For I = 0: 1: 255, {S (i); if C (i) then T (I (i))}; Here, C (i) is an exception condition that is rarely true (for example, 1/64) and depends only on S (i), and T (I (i)) is, for example, 1024 operations (operations,). It is a long exception handling of the instruction). I (i) is the information calculated by S (i) and is necessary for exception handling. For example, T (I (i)) supposes that each loop turn in program A) adds an average of 16 operations, which exceeds the 4 operations of the body of the loop. Such rare but long exception handling is a common problem in programs. A method of dealing with this issue without compromising the benefits of unrolling is described below.

Guard command One method is by using guard instructions, which are equipment available on many processors. The guard instruction specifies a Boolean integer as an additional operand, which means that it always occupies the expected functional unit, but the retention of the result is stopped if the guard is lost. In implementing the If-then-else syntax, the guard is interpreted as an if condition. The instruction in the Then clause (closed) is protected by the if condition, and the instruction in the else clause is protected by the negation of the if condition. In either case, execute both clauses. Updated with the result of the then clause only if the guard is true. Updated with the result of the else clause only if the guard is false. In all cases, it executes the instructions in both clauses and accepts these (execution of both clauses) disadvantages rather than the pipeline delay disadvantages (penalties) required by changing conditions in the control flow. This guard method suffers a great disadvantage if the guard is overwhelmingly true and the else clause is large, as in Program A'). In this case, the large else clause suffers the disadvantage of executing the large else clause in all cases, even though it is relevant only in a few cases. If there is an operation S to be guarded by condition C, this can be programmed as follows. Guard (C, S);

First unrolling Program A') can be unrolled into the next program D'). for n = 0: 4: 255, {S₁(n); S₁(n + 1); S₁(n + 2); S₁(n + 3); S₂(n); S₂(n + 1); S₂(n + 2); S₂(n + 3); S₃(n); S₃(n + 1); S₃(n + 2); S₃(n + 3); S₄(n); S₄(n + 1); S₄(n + 3); S₄(n + 3); S₅(n); S₅(n + 1); S₅(n + 3); S₅(n + 3); if C (n) then T (I (n)); if C (n + 1) then T (I (n + 1)); if C (n + 2) then T (I (n + 2)); if C (n + 3) then T (I (n + 3)); }; In the parameters of the above example, 77% of the loop turns do not perform T (I (n)), 21% of the loop turns perform T (I (n)) once, and T (I (I (n)). n)) is executed more than once in only 2% of loop turns. Little can be obtained by swapping the operations T (I (n)), T (I (n + 1)), T (I (n + 2)), and T (I (n + 3)). It is clear that.

Pile processing A new alternative is pile processing. A pile is a continuous storage object (sequential memory object) that is generally stored in RAM. The pile is intended to be written continuously and read continuously from the beginning. Many methods are specified for pile objects. For practical piles and methods of handling piles in a parallel processing environment, pile realization is required to be a small number of instructions in inline code (no return branch to a subroutine). It is also required that this inline code does not contain branch instructions. The realization of such a method will be described below. This possibility of realization makes the pile new and valuable. 1) Pile is created by the method Create_Pile (P). This method allocates storage and initializes internal state variables. 2) The main way to write a pile is Conditional_Append (pile, condition, record). This method adds record (parameter value) to pile called pile only if condition is true. 3) When the pile is completely written, it is ready to be read by the method Rewind_Pile (P). This adjusts the internal variables so that the read starts from the first record written. 4) Method EOF (P) generates a Boolean numerical value indicating whether or not all records in the pile have been read. 5) Method Pile_Read (P, record) reads the next sequential record from pile P. 6) Method Destroy_Pile (P) destroys Pile P by deallocating all state variables of Pile P (in storage).

Divide conditional processing using pile Pile P allows program D') to be converted to program E'). Create_Pile (P); for n = 0: 4: 255, {S₁(n); S₁(n + 1); S₁(n + 2); S₁(n + 3); S₂(n); S₂(n + 1); S₂(n + 2); S₂(n + 3); S₃(n); S₃(n + 1); S₃(n + 2); S₃(n + 3); S₄(n); S₄(n + 1); S₄(n + 3); S₄(n + 3); S₅(n); S₅(n + 1); S₅(n + 3); S₅(n + 3); Conditional_Append (P, C (n), I (n)); Conditional_Append (P, C (n + 1), I (n + 1)); Conditional_Append (P, C (n + 2), I (n + 2)); Conditional_Append (P, C (n + 3), I (n + 3)); }; Rewind (P); While not EOP (P) { Pile_Read (P, I); T (I); }; Destroy_Pile (P); The program E') operates by storing the information I required for the exception operation T on the pile P. Only the records of I corresponding to the exception condition C (n) are written, so the number of records of I in P (eg 16) is much higher than the number of loop turns (eg 256) in the original program A). Few. After that, an independent "while" loop reads through the pile P and performs all exception calculations T. Only if C (n) is true will P contain record I, so only these cases will be processed. The second loop is a bit more cumbersome than the first loop, because the second loop has an average of 16 turns in this example, but it's half-hearted. Therefore, a "while" loop is needed rather than a "for" loop, and the method EOF indicates that it has read all the records from the pile and exits. As described above and below, the method Conditional_Append can be invoked inline and without branching. This means that the first loop has a small number of unproductive issuance opportunities and is still unrolled in an effective way.

Unrolling the second loop The second loop in program E') has not been unrolled and is still inefficient. However, Program E') is a pile P₁, P₂, P₃, P₄Can be converted to the following program F'). The result is that F') unrolls both loops with improved efficiency. Create_Pile (P₁); Create_Pile (P₂); Create_Pile (P₃); Create_Pile (P₄); for n = 0: 4: 255, {S₁(n); S₁(n + 1); S₁(n + 2); S₁(n + 3); S₂(n); S₂(n + 1); S₂(n + 2); S₂(n + 3); S₃(n); S₃(n + 1); S₃(n + 2); S₃(n + 3); S₄(n); S₄(n + 1); S₄(n + 2); S₄(n + 3); S₅(n); S₅(n + 1); S₅(n + 2); S₅(n + 3); Conditional_Append (P₁, C (n), I (n)); Conditional_Append (P₂, C (n + 1), I (n + 1)); Conditional_Append (P₃, C (n + 2), I (n + 2)); Conditional_Append (P₄, C (n + 3), I (n + 3)); }; Rewind (P₁); Rewind (P₂); Rewind (P₃); Rewind (P₄); While not all EOF (P_i) { Pile_Read (P₁, I₁); Pile_Read (P₂, I₂); Pile_Read (P₃, I₃); Pile_Read (P₄, I₄); Guard (not EOF (P)₁), S); T (I)₁); Guard (not EOF (P)₂), S); T (I)₂); Guard (not EOF (P)₃), S); T (I)₃); Guard (not EOF (P)₄), S); T (I)₄); }; Destroy_Pile (P₁); Destroy_Pile (P₂); Destroy_Pile (P₃); Destroy_Pile (P₄); Program F') is program E') that unrolled the second loop. This unrolling is achieved by splitting a single pile of program E') into four piles, each of which can be processed independently of each other. Each turn of the second loop in program F') processes one record from each of these four piles. Since each record is processed independently, the operation of each T can be rearranged with the operation of the other three Ts. Until all piles are processed, the control of the "while" loop must be modified to a "to" loop. And, in general, not all piles complete in the same loop turn, so the operation T in the "while" loop must be guarded. There is always some inefficiency when the number of records in two piles is significantly different from each other, but according to probability theory (law of large numbers), these piles contain similar numbers of records. Of course, this pile-making technique can be applied iteratively. If T itself contains a long conditional clause T', then T'can be split from the second loop with some additional pile to unroll the third loop. .. Many real-world applications have some such nested exception clauses (closed).

Realization of pile processing The implementation of pile objects and their methods must remain simple in order to meet the implementation criteria described above. a) The implementation of the method must be limited to a small number of instructions in inline code, with the exception of Create_Pile and Destroy_Pile. b) This implementation should not include branch instructions. The heart of the pile consists of a linear array allocated in RAM and a pointer "index", where the current value of the pointer is the position of the record to be read or written next. The write size "sz" of this array is a pointer, and its value is the maximum value of the "index" during writing of the pile. Method EOF can be implemented as an inline conditional statement (sz &lt;index). The pointer "base" has a value that indicates the first position to write to the pile. This value is set by the method Create_Pile. Method Conditional_Append copies records into an array of piles starting with the value "index". Then, the "index" is incremented by the calculated amount, and this calculated amount is either 0 or the size of the record (sz_record). Since the parameter "condition" has a value of 1 for true and a value of 0 for false, "index" can be calculated as follows without branching. index = index + condition × sz_record; Of course, there are many variants of this calculation, many of which do not include multiplications given special values for variables. This calculation can also be calculated using the following guards. guard (condition, index = index + sz_record); The record is copied to the pile regardless of "condition". If "condition" is false, this record is overwritten by the next record, and if "condition" is true, the next record is written following the current record. The next record itself may or may not be overwritten by subsequent records. As a result, it is generally best to write as little as possible to the pile, even if some (redundant) data is to be recalculated when reading and processing the record. Method Rewind can be easily realized by sz = index; and index = base ;. This operation records the amount of data written for method EOF and resets "index" to the first value. Method Pile_Read copies the next part of the pile (of length sz_record) to I and increments the "index", as in the following equation: index = index + sz_record; Destroy_Pile releases the storage assigned to the pile. All of these methods (except Create_Pile and Destroy_Pile) can be implemented with a small number of inline instructions and without branching. Thus, pile processing allows loop unrolling, resulting in improved performance in the presence of branches. This technique specifically allows parallel execution of long exception clauses (closed). The cost for this is about the request to write a small amount of data to RAM and read it again.