Wavelet transform system, method and computer program product

Wavelet transform system, method and computer program product

[001] Technical Field

[002] The present invention relates to data compression, especially the use of wavelets to compress data.

[003] Background Technology

[004] The video "codec" (compressor/decompressor) is used to balance image quality, processor requirements (ie, cost/power consumption), and compression rate (ie, the resulting data rate) Reduce the data rate required for the data communication stream. The currently available compression methods provide different ranges of trade-offs, resulting in a variety of codec formats, each of which is optimized to meet the needs of a specific application.

[005] Prior Art FIG. 1 shows an example 100 of the trade-offs between various compression algorithms currently available. As shown in the figure, these compression algorithms include a wavelet-based codec 102 and a DCT-based codec 104 formed by various MPEG video distributions.

[006] 2D and 3D wavelets are currently available methods of coding and decoding algorithms based on DCT. Because of wavelet's desirable image quality and flexible compression rate, it has always received high attention, prompting the JPEG committee to adopt the wavelet algorithm as its JPEG2000 still image standard. Unfortunately, most wavelet devices use very complex algorithms related to DCT selection that require a lot of processing power. In addition, wavelets have a unique and complex problem of temporary compression, which makes 3D wavelets particularly difficult.

[007] For these reasons, Wavelet has never provided a large-capacity industry standard codec that is superior to MPEG, and therefore, it has only been adopted by some specific application fields. Therefore, there is a need for a commercially viable 3D wavelet device that is segmented for the three main markets and optimized for low power and low cost.

[008] For example, small cameras have gained more and more widespread use and have significant advantages in digitally processing signals. For example, in some countries, the fastest growing part of the cellular phone market is phones with the ability to edit images and video clips. Most digital cameras have video clip editing features. In the mobile wireless handset market, the transmission of these still images and short video clips requires greater capacity from the device's battery. Existing video coding standards and digital signal processors have higher requirements for batteries.

[009] Another new application is a personal video recorder (PVR) that allows viewers to pause the live TV broadcast and watch the programmed TV program afterwards. These devices use digital hard disk storage to record video and require video compression of the analog video signal from the cable. In order to provide features such as picture-in-picture and video while watching, these units require multiple video compression encoders.

[010] Another growing application area is digital video cameras (DVR) for surveillance and security video. Compression coding is also needed to store the input video of each channel. In order to use the convenient and flexible digital network transmission architecture, the video signal must be digitized in the camera. Even with the old multiplexed recording architecture, multiple channel compression encoders are required.

[011] Of course, there are many other markets that can benefit from commercially available 3D wavelet implementations optimized for low power and low cost.

[012] Experience has shown that an image considered as a function on a 2-dimensional plane can be well established as a polynomial model. Most points are smooth, and only some points are relatively isolated points and line (edge) specificity. A 3D domain can be used to similarly model video clips. For most images and videos, the RMS (root mean square) margin generated from linear polynomial models is around 5%, while for quadratic polynomial models it is around 2%.

[013] A common scheme for approximately simulating these functions (images and videos) includes the following steps:

[014] 1) The function is reversibly transformed so that the transformed coefficients can be divided into "subbands",

[015] 2) Quantify all sub-bands except the "low-pass" sub-band (ie, reduce the accuracy of all sub-bands except the "low-pass" sub-band),

[016] 3) Use inverse transformation on the quantized coefficients to reconstruct a function that approximates the original function.

[017] A good solution uses a transformation that projects the low-level polynomial content of the function to the non-quantized "low-pass" subband. This scheme preferably also produces zero or very small values in other sub-bands. Therefore, the subsequent quantization of the non-low-pass subbands will not significantly change the transformation of the function modeled with a sufficiently low-level polynomial, and the approximate reconstruction of the original function will also be very good.

[018] The realism of the realization makes the value in the transformed function only depend on the value in the small neighborhood of some points in the original function domain, which is the best. This is one of the purposes of 8×8 blocks in the JPEG and MPEG standards. In these regulations, the neighborhoods are coincident or disjoint, and the image domain is divided into multiple disjoint neighborhoods with distinct boundaries. At these boundaries, the approximation obtained from quantization may not be good (the well-known "Gibbs effect" in the discrete Fourier transform), resulting in significant "blocking" artifacts in reconstructed and approximated images.

[019] As a kind of transform with the attribute of small neighborhood, wavelet transform has received a lot of attention despite having overlapping neighborhoods. Compared with the DCT of JPEG/MPEG, some wavelet transforms do a better job in projecting the function to the low-pass sub-band. In addition, some wavelet transforms (which do not need to be the same wavelet transform) require less computational intensity. However, neighborhood overlap brings important implementation issues in terms of data processing, memory utilization, and storage bandwidth. It can still be used for "blocking" domains, restoring their boundaries and approximate results near those boundaries.

[020] The problem in domain boundary transformation is that the neighborhood centered on a boundary point is not in the domain block to which the boundary point belongs. As specifically incorporated in various JPEG and MPEG standards, the usual method for this problem is to symmetrically reflect the domain value in the block that crosses the boundary to establish "effective" values and effective functions in the required neighborhood.

[021] Unless this effective function is a constant in the neighborhood, it will have a tip or inflection point resulting from a discontinuous first derivative. This discontinuity cannot be well modeled by low-level polynomials, and thus is reflected in the large non-low-pass subband coefficients after quantization. Larger quantization errors result in increased approximation errors on the boundary.

[022] One of the transformations specified in FPEG 2000 standard 1) is the reversible 5-3 transformation shown in equations #1.1 and 1.2.

[023] Equations #1.1 and 1.2

[024]

Equation 1.1

[025]

Equation 1.2

[026] Since these equations are integer-to-integer mapping tables and are easy to solve to obtain Y, this transformation is reversible, and the inverse transformation strictly generates the input Y bit by bit. See equations #2.1 and 2.2.

[027] Equations 2.1 and 2.2

[028]

Equation 2.1

[029]

Equation 2.2

[030] It can be clearly seen from these equations: Y2n+1 is the estimated value of the negative half of the second derivative of (2n+1); and, if the first-order polynomial can be used in (2n+1), it is good Ground approximates the function, then Y2n+1 is approximately zero.

[031] floor brackets

The purpose of adding the internal constants is to remove any DC bias from the estimated value. The uncorrected bias in the wavelet easily leads to oscillation errors in the reconstructed data, which manifests as fixed pattern noise such as horizontal or vertical stripes. There are several possible methods for estimating and correcting the bias voltage, one of which is selected in the JPEG2000 standard.

[032] If the correct boundary of the image is at point 2N-1, equation #1.1 cannot be calculated because the required value X2N is not available. JPEG 2000 needs to deal with this situation by using a positive symmetric expansion function, thus using X2N=X2N-2. Substitute it into equation #1.1 to get equation #1.1ext.

[033] Equation #1.1ext

[034]

[035] <math> <mrow> <mo>=</mo> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo> -</mo> <mn>1</mn> </mrow> </msub> <mo>-</mo> <msub> <mi>X</mi> <mrow> <mn>2</mn > <mi>N</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub> </mrow> </math>

[036] Equation 1.1ext

[037] This produces an estimated value Y2N-1 of the first derivative that is opposite to the estimated value of half the negative of the second derivative of the internal point. In addition, it can be clearly seen that only by using three distinct points instead of two points, an estimate of the second derivative can be obtained. Since only these points are available for the inverse step, it is necessary to limit the two points required in the ascending term to X with even exponents. The closest candidate index is 2N-4.

[038] In particular, it can be seen in equations #1.2 and 2.1 that the FPEG-2000 formula of the 5-3 wavelet filter includes the addition of the constant 1 or 2 in the calculation, as well as other restrictions. When the maximum speed and efficiency of calculations are achieved, these additions and other limitations may require a large portion of the total computational burden and cause significant performance degradation.

[039] Summary of the Invention

[040] A system, method, and computer program product for compressing data are provided. First, receive an interpolation formula. Use this interpolation formula to compress the data. In use, when the required data value is difficult to obtain, it is determined whether the interpolation formula requires at least one data value. If this is the case, perform an extrapolation operation to generate the required data value that is difficult to obtain.

[041] In an embodiment, the interpolation formula may be a component of the wavelet filter. As another option, you can choose to replace the wavelet filter with a polyphase filter.

[042] In another embodiment, multiple data values may be divided into multiple variation ranges. Thus, by using only the data values within a variation range, the amount of calculation involved in the interpolation formula can be reduced.

[043] In yet another embodiment, data values can be quantified. In this embodiment, the amount of calculation related to entropy coding can be reduced by reducing the amount of data values. The amount of data value can be reduced in the process of quantization operation involving data value.

[044] In yet another embodiment, the amount of calculation related to reconstructing data values to a predetermined data range can be reduced. This amount of calculation can be reduced by performing only a single cut operation.

[045] In an embodiment, the wavelet filter includes an interpolation formula, including:

[046]

[047] In an embodiment, the wavelet filter includes an interpolation formula, including:

[048] Y2N+1=(X2N+1+)-(X2N+)

[049] In an embodiment, the wavelet filter includes an interpolation formula, including:

[050]

[051] In an embodiment, the wavelet filter includes an interpolation formula, including:

[052]

[053] In an embodiment, the wavelet filter includes an interpolation formula, including:

[054]

[055] In one embodiment, the wavelet filter includes an interpolation formula: including

[056]

[057] In an embodiment, the wavelet filter includes an interpolation formula: including

[058]

[059] In an embodiment, the wavelet filter includes an interpolation formula, including:

[060] (X2N+1+)=Y2N+1+(X2N+)

[061] Another system and method for compressing data is provided. First, receive the data in a separate device. This separate device is used to encode this data to generate first compressed data in the first format. In addition, the separate device is used to convert the code of the first compressed data to generate second compressed data in a second format.

[062] In one embodiment, encoding may occur in real time. In addition, transcoding can be done offline.

[063] In another embodiment, the first compressed data can be transcoded to produce second compressed data in a second format, so that the second compressed data is suitable to match the capabilities of the communication network coupled to the separate device.

[064] As an option, the first encoder may be used for encoding. In addition, a decoder and a second encoder can be used for transcoding.

[065] In addition, the first format may include a wavelet-based format. In addition, the second format may include a DCT-based format. In a particular embodiment, the second format may include the MPEG format.

[066] Another system and method for compressing data using multiple encoders on a single integrated circuit is provided. First, the data is received in a separate integrated circuit. Then, the data is encoded using multiple encoders combined on the single integrated circuit.

[067] In one embodiment, multiple channels on a single integrated circuit may be utilized to encode data. In addition, the data can be encoded into a wavelet-based format.

[068] Yet another separate module system and method for compressing data is provided. In use, a single module is used to receive photons. Then, a separate module is used to output compressed data representing photons.

[069] As an option, the compressed data can be encoded into a wavelet-based format. In addition, transformation operations related to encoding can be performed in an analog manner. The separate module may further include an imager.

[070] Brief Description of the Drawings

[071] Prior Art Figure 1 shows an example of the trade-offs between various compression algorithms currently available;

[072] FIG. 2 shows a framework for compressing/decompressing data according to an embodiment;

[073] FIG. 3 shows a method for compressing/decompressing data according to an embodiment;

[074] FIG. 4 shows a data structure on which the method of FIG. 3 is executed;

[075] FIG. 5 shows a method of compressing/decompressing data according to an embodiment;

[076] FIG. 6 shows a system for compressing data according to an embodiment; and

[077] FIG. 7 shows a system that uses multiple encoders on a single integrated circuit to compress data.

[078] Specific embodiments

[079] FIG. 2 shows a framework 200 for compressing/decompressing data according to an embodiment. The framework 200 includes an encoder part 201 and a decoder part 203, which together constitute a "codec". The encoder part 201 includes a transform module 202 for compressing data to be stored in a file 208, a quantizer 204, and an entropy encoder 206. In order to perform decompression of the file 208, the decoder section 203 includes an inverse transform module 214 for decompressing the data for use (ie, in the case of video data, for viewing, etc.), a dequantizer 212, and an entropy decoder 210.

[080] In use, the transformation module 202 is decorrelating, and performs reversible transformation on multiple pixels (in the case of video data), and this reversible transformation is usually linear. Next, the quantizer 204 implements quantization of the transform value, and then, the entropy encoder 206 is responsible for entropy encoding of the quantized transform coefficient.

[081] FIG. 3 shows a method 300 of compressing/decompressing data according to an embodiment. In an embodiment, the method 300 may be performed in the device environment of the transformation module 202 in FIG. 2 in a manner that it performs a reversible transformation. However, it should be noted that the method 300 can be implemented in any desired device environment.

[082] In operation 302, an interpolation formula for compressed data is received (ie, recognized and retrieved from memory, etc.). In the context of this specification, the data can be any data that can be compressed. In addition, the interpolation formula may include any formula using an interpolation method (ie, wavelet filter).

[083] In operation 304, in a case where the required data value is difficult to obtain, it is determined whether the interpolation formula requires at least one data value. Such data values can include any subset of the aforementioned data. Because it is difficult to obtain, the required data value may not exist, out of range, and so on.

[084] Then, an extrapolation operation is performed to generate the required data value that is difficult to obtain. See operation 306. The extrapolation formula can include any formula that uses extrapolation. Through this scheme, the data compression is enhanced.

[085] FIG. 4 shows a data structure 400 on which the method 300 is executed. As shown in the figure, in the transformation process, a "best fit" 401 involving multiple data values 402 can be obtained through an interpolation formula. Note operation 302 of method 300 of FIG. 3. If it is determined that one of the data values 402 is difficult to obtain (see 404), then an extrapolation formula can be used to generate this difficult data value. More optional details regarding an example of the above-mentioned technique are explained below with reference to FIG. 5.

[086] FIG. 5 shows a method 500 of compressing/decompressing data according to an embodiment. As an option, the method 500 can be performed in the environment of the transformation module 202 in FIG. 2 in a way that it performs a reversible transformation. However, it should be noted that the method 500 can be implemented in any desired environment.

[087] Method 500 provides a technique for generating edge filters used as wavelet filter pairs. First, in operation 502, the wavelet scheme is analyzed to determine the partial derivative of the wavelet filter approximation. Next, in operation 504, according to the characteristics of the wavelet filter and some available samples, the order of the polynomial used for the extrapolation is selected. Then, use the selected polynomial order to derive the extrapolation formula of each wavelet filter. See operation 506. In operation 508, a specific edge wavelet case is derived using an extrapolation formula with available samples in each case.

[088] See Annex A for an alternative method of solving coefficients using the Vandermonde matrix. In addition, the additional optional information and related information about the example extrapolation formula are explained in more detail below.

[089] In order to approximate Y2N-1 from the left, a quadratic polynomial is adapted from the left. Approximately calculate the negative value of half of the second derivative at 2N-1 using the available values, resulting in equation #1.1R. See Annex A for a way to determine this extrapolation of a second-degree polynomial.

[090] Equation #1.1R

[091]

Equation 1.1R

[092] When the point is the rightmost one, equation #1.1R can be used instead of equation 1.1 (see the background art section). The obvious multiplication by 3 can be done by shifting and adding. Dividing by 3 is more complicated. For the case where the rightmost index is 2N-1, it is not a problem to calculate Y2N-2 using equation #1.2 (see the background art section). In the case where the exponent of the rightmost point is an even number (ie, 2N), there is no problem with equation #1.1, but equation #1.2 involves missing values. The purpose here is to use only the odd-numbered exponent Y calculated in the previous related example, namely Y1 and Y3, to subtract the estimated value of Y from the even-numbered X. As mentioned above, this required estimated value at exponent 2N can be obtained by linear extrapolation. Equation #1.2R gives the appropriate formula.

[093] Equation #1.2R

[094]

Equation 1.2R

[095] The corresponding situation applies to the left boundary. A similar edge filter is used, but the required extrapolation is performed from the right (inside) instead of from the left. In this case, equations #1.1.L and 1.2.L represent suitable filters.

[096] Equation #1.1.L and 1.2.L

[097]

Equation 1.1.L

[098]

Equation 1.2.L

[099] Through back substitution, the inverse transform filter of the original transform filter of these extrapolated boundary filters can be obtained. It is possible to use the inverse transform boundary filter instead of the standard filter in the same environment as the forward boundary filter. Equations #2.1.Rinv, 2.2.Rinv, 2.1.L.inv, and 2.2.L.inv represent these filters.

[100] Equation #2.1.Rinv, 2.2.Rinv, 2.1.L.inv, and 2.2.L.inv

[101]

Equation 2.1. Rinv

[102]

Equation 2.2. Rinv

[103]

Equation 2.1.L.inv

[104]

Equation 2.2.L.inv

[105] Therefore, an embodiment can use the reformulation of the 5-3 filter, thereby avoiding the additional steps of the prior art, while retaining the actual properties of the filter. For example, see equation #3.1, 3.1R, 3.2, 3.2L.

[106] Equation #3.1, 3.1R, 3.2, 3.2L

[107]

Equation 3.1

[108] Y2N+1=(X2N+1+)-(X2N+) Equation 3.1R

[109]

Equation 3.2

[110]

Equation 3.2L

[111] In the formation equation, a 1/2 offset or bias is used to calculate specific coefficients in order to avoid the above addition. It should be noted that although there are many 1/2 additions in the formation equations, there is no need to actually perform these additions in the calculations. In equations #3.1 and 3.1R, you can see that the 1/2 addition effect is canceled, so there is no need to apply them to the input data. The term (Y0+) in parentheses can be regarded as the name of a quantity that is actually calculated, stored as a coefficient, and passed to the next level of the wavelet transform pyramid.

[112] As in the above case, the JPEG-2000 inverse filter formula can be reconstructed in the following equations #4.2, 4.2L, 4.1, 4.1R.

[113] Equation #4.2, 4.2L, 4.1, 4.1R

[114]

Equation 4.2

[115]

Equation 4.2L

[116]

Equation 4.1

[117] (X2N+1+)=Y2N+1+(X2N+)

[118] Equation 4.1R

[119] It can be seen from this that the value used as the input to the inverse calculation is the same term as that produced in the forward calculation in equations #3.1 to 3.2L, and does not require a correction of 1/2 for the actual calculation.

[120] In this way, the total amount of arithmetic operations performed in the wavelet transform calculation is reduced.

[121] Optional features

[122] The following describes additional optional features and techniques that can be used in the context of the systems and methods of Figures 2-5. It should be noted that the additional features proposed are for illustrative purposes only, and cannot be construed as limitations in any way. In addition, these features can be implemented independently of the systems and methods of Figures 2-5 above.

[123] General optional features

[124] In use, the transform module (ie, for example, see the transform module 202 in FIG. 2) can use the wavelet pyramid, which serves to segment the image into approximately covering an octave (ie, the coefficient 2 ) The role of the sub-band filter bank. In each octave band, there are three subbands corresponding to the horizontal, vertical, and grid characteristics. In one embodiment, the pyramid can generally be three to five layers deep, covering the same number of octaves. If the original image is completely smooth, the amplitude of the wavelet coefficients decreases rapidly. The image can have a Holder coefficient of 2/3, which roughly indicates that the image has a derivative of 2/3. If you arrange the wavelet coefficients in descending order of absolute value, you can see that these absolute values decrease like Ns, where N is the position in the sequence and s is the smoothness of the image.

[125] After forming the wavelet pyramid, the wavelet coefficients can be scaled (quantized) by a quantizer (ie, for example, the quantizer 204 of FIG. 2, etc.) to obtain the contrast sensitivity curve (CSF) with viewing conditions and human vision Consistent results. By explaining the characteristics of the human visual system (HVS), the number of bits used to encode the chrominance subband can be greatly reduced.

[126] In order to provide fast algorithms that can be implemented in the smallest silicon area requirements, traditional arithmetic encoders can be avoided. For example, as described above, multiplication operations that take up a large silicon area can be avoided. In addition, this algorithm can have a good "quick path" of the various elements running.

[127] The codec can use a group of pictures (GOP) of two overlapping video frames, boundary edge filters, midfield image compression and block compression structures. The realization of a small single chip can be as shown in Table 1 below.

[128] Table 1

[129] An implementation can use short wavelet bases (2-6 wavelets), which are particularly suitable for natural scene images dedicated to quantization to match HVS. It can be realized by adding and shifting. For each scene, the Mallat pyramid obtained from using five filters in the horizontal direction and three filters in the vertical direction can be used. This produces a filter with dual-valued coefficients, two coefficients in a low-pass filter, two, four, or six coefficients in a wavelet filter (resulting in twelve wavelet subbands). Near the block and image boundaries, improved edge filters can be used to take advantage of actual image values. The resulting video pyramid can have a series of zeros, and a series of non-zeros. Therefore, it can be efficiently coded through the look-up table.

[130] Another solution can use motion image compression through 3D wavelet pyramid, instead of motion compensation search in methods such as MPEG. The transformation compression in the time direction can be applied to the GOP of the four scenes. The two-level time pyramid can be used as a tensor product with the space pyramid. It is possible to use a linear edge filter in the precision stage and an improved Haar filter in the coarse stage, resulting in four temporal subbands. Compress each of these time subbands.

[131] Processing that can be broken down into blocks of 8 scan lines, each scan line has 32 pixels. This helps reduce RAM requirements to the point where RAM can be placed in the ASIC itself. This reduces the number of chips and simplifies the satisfaction of RAM bandwidth requirements. The compression process can be performed stripe by stripe (two channels per stripe). A "stripe" is 8 pixels high and the entire width of the picture.

[132] In another embodiment, the quantization of wavelet coefficients can be used to obtain a further improvement in compression. The denominator of the quantization is a power of 2, making it possible to achieve by shifting. Quantization may refer to a process of assigning a scale factor to each sub-band, multiplying each coefficient in the sub-band by a corresponding scale factor, and fixing the scaling coefficient to an integer.

[133] Combination filter

[134] As another option, the wavelet filter can be selectively replaced with a polyphase filter. In one embodiment, this substitution may occur in the transform module of the data compression/decompression system (ie, see the transform module 202 and/or the inverse transform module 214 of FIG. 2). Of course, this feature can be implemented independently of the various other features described herein. The following explains more sample information about this optional feature.

[135] In this embodiment, in the design of the video compression codec, conventional (ie, finite impulse response (FIR)) information abandonment or the use of a smoothing filter can be combined with a wavelet information retention filter. The difference between the FIR filter and the wavelet filter is that the conventional FIR filter is used alone, while the wavelet filter always appears in the form of complementary duality. In addition, the FIR filters in the wavelet transform do not have to be related to each other like the polyphase filter bank.

[136] Video compression can be performed in a three-step process; sometimes other steps can be added, but, as mentioned earlier, the three main phases are: transformation, quantization, and entropy coding. As in normal practice, these operations generally only discard information during the quantification process. In fact, if you delete this operation, you can get a lossless compression method. However, lossless compression is limited to a smaller compression rate than lossy compression. Lossy compression uses the human visual system and discards information that cannot cause visual differences or negligible visual differences in the decoding results.

[137] One type of visual information that is sometimes discarded with acceptable results is the tiny details of the image. Although most of the transformation processes used in video compression can discard minute details through the quantization step, when they do so, they are less efficient than direct low-pass filters and have lower visual fidelity.

[138] One way to implement a smoothing filter is to use the FIR structure. An alternative way to implement a smoothing filter is to use an infinite impulse response (IIR) structure.

[139] When you want to change the size of an image or data sequence, you can use a polyphase filter bank (PFB) composed of related FIR filters. This method processes the image by discarding some details and producing a relatively smaller image for further processing.

[140] A polyphase filter bank includes a set of FIR filters that share the same bandwidth, or frequency selective properties, but produce pixels inserted at different positions on or between the original samples.

[141] For example, a polyphase filter bank can be used to reduce one image (ie, one frame of video) to 2/3 of its original width. It calculates the pixels that are inserted midway between each original pixel, calculates the pixels that are smooth at the original position, and then reserves one every two pixels in the generated pixel stream to reduce the width of the image.

[142] In this way, it is possible to omit the calculation of unreserved pixels, resulting in a more effective method of reducing the image size. This process can easily be generalized to other rational number fraction changes. In this way, the polyphase filter bank can smoothly discard a small amount of minute details, and reduce the image with a factor of less than one (1). The factor can be greater than 1/2.

[143] This embodiment uses a polyphase filter as the first stage of the wavelet-based image compression process to combine the advantages of smooth detail abandonment with the image quality of wavelet transform coding. By using this combination, the smallest details from the use of polyphase filter banks and the smooth, high-quality, and unmanned advantages of the bits required to represent them can be added to those from the use of wavelet transform as image and video compression. Known advantages of basic fast and efficient calculations and high visual quality.

[144] In the first embodiment of the method, you can first use a polyphase filter bank on the image in one direction, generally the horizontal direction, and then, before quantizing and entropy coding in the usual way, transform the wavelet Apply to the image.

[145] In the second embodiment of the method, the polyphase filter may be applied in a specific direction before the first wavelet operation in that direction, but it may also be applied after the wavelet operation in other directions.

[146] In yet another embodiment, a polyphase filter may be applied in each of several directions before the first wavelet operation, but after wavelet operations in other directions, the polyphase filter may be applied in that direction.

[147] This method of applying a lossy filtering step before at least some wavelet or DCT transform stages has several advantages. For example, it is possible to design filters that are not limited to working in a wavelet manner, such as FIR or polyphase design, in order to obtain higher quality and smaller human factors. The wavelet filter can be designed as a dual form that splits the information into two parts without giving up the information.

[148] Applying a lossy filter before the transformation operation rather than after it means that the transformation calculation can be operated on less data, which takes less time and requires less intermediate storage during the calculation. Since transformation generally accounts for a considerable part of the compression process, this reduction results in a significant increase in the speed and efficiency of the entire compression process.

[149] Sparse wavelet transform using heap

[150] As yet another option, the amount of calculation related to entropy coding can be reduced by reducing the amount of data values. In one embodiment, this reduction may occur in the quantizer of the data compression/decompression system (ie, see quantizer 204 in Figure 2). Of course, this feature can be implemented independently of the various other features described herein. The following explains more sample information about this optional feature.

[151] In this embodiment, the heap can be used as an operation in the decoding operation, so that it is ready to be used in the subsequent steps of the calculation. You can see more information about the heap from Appendix B.

[152] Provides so-called sparse representation of matrix data, which is known in the field of scientific computing. The ordinary matrix is represented as a complete array of numbers as matrix elements; this is called a "dense" representation. Some packages store, transform, and operate on "sparse matrices." In sparse matrices, zero items are not explicitly represented one by one, but implicitly represented. One such "sparse" representation is zero-run coding, in which the count of zeros that appear together represents zero. The count itself can be zero (when two non-zero values are adjacent), 1 (an isolated zero value), or greater.

[153] However, if the video data is not a matrix, then it is generally impossible to perform matrix operations on them (ie, multiplication, inversion, eigenvalue decomposition, etc.). The basic principles of sparse matrix calculation can be extracted and transformed into video transformation.

[154] Simply put, a heap is composed of an array of pairs; each pair gives the address (or offset) of a non-zero item in the ordinary data and the value of the item. The addresses or offsets are sorted, so that by traversing the heap and taking into account the location of the non-zero elements in the complete data set, the entire data set can be traversed from one end to the other.

[155] The heap is specially designed so that it can be efficiently implemented on a computer (ie, SIMD processor) that uses the same operation to immediately perform data processing on several data items in parallel, and makes the conditional transfer of control more expensive On your computer. These processors are used together to process video and audio, and are sometimes referred to as "media processors."

[156] When it is necessary to perform certain operations on two sparse data sets, there is a problem that does not occur when the data is represented densely. That is, "When do data items coincide with each other?"

[157] When operating on two data sets represented as heaps, the basic operation of identifying overlapping data sets is called "match and merge". When a person traverses two piles, he or she can obtain an address from each pile and the address for which the output value has just been generated for each operation after he or she starts. In order to find the next address for which a value can be generated, the minimum value of the two addresses represented by the input heap can be found. If the addresses of the two heaps are the same, then each heap has an available data item, and operations can be performed on the two values to produce the desired result. Then, you can move on to the next item in the two stacks.

[158] If the next address in the two heaps is different, then there is a non-zero value in one heap (a data set) and a zero in the other data set (implied by the heap) Value; then the one value and zero can be operated on to produce a value. Alternatively, if performing operation one when an input is zero produces zero, then no value is produced. In either case, it is possible to advance to the next item only on the heap with the smallest address.

[159] Place the resulting value in the output location, in a dense array (by writing a zero that appears whenever the address is advanced by more than one address) or in the output heap.

[160] As mentioned above, wavelet transform includes one-dimensional or multi-dimensional, and wavelet filter pairs are repeatedly used for a set of data. For video compression, 2-D wavelet transform (horizontal and vertical) or 3-D wavelet transform (horizontal, vertical, and time) can be used.

[161] The intent of the transformation stage in a video compressor is to concentrate the energy or information of the source picture into a form as compact as possible by taking advantage of the local similarities and graphics in the picture or sequence. No compressor can compress all possible inputs; compressors can be designed to work well on "typical" inputs, and ignore them and cannot compress "random" or "pathological" inputs.

[162] When the transform works normally and the picture information is concentrated into a few transform coefficients, there are many zeros between the remaining coefficients.

[163] As mentioned above, the quantization result is also a stage of the video compressor. In this stage, zero is used to represent the calculated value close to zero. Sometimes it is desirable to quantize the calculated coefficients in the calculation process of wavelet transform, instead of or additionally quantify the final transform result.

[164] So there may be many zeros in some wavelet coefficient data, and this may happen when more calculations are needed on the data.

[165] In addition, when a person decodes a compressed image or video to display it, he or she can recover a completely filled image for display from the entropy coding significant coefficients. The typical output of the first decoding step, entropy code decoding, is a set of significant coefficients with a large number of invalid coefficients that default to zero.

[166] When this happens, it is very valuable to convert dense data with many zeros into a sparse representation; this can be done by stacking the data as described above. The heap represents a representation of a series of zeros, but addresses or offsets are often stored instead of the series length (the difference in addresses). This makes it possible to process both faster to build up the heap and later expand the heap into a dense representation.

[167] In the case of decoding, the data is not in dense form, and it is more natural to construct the heap directly in the entropy decoder.

[168] There are several situations in the wavelet transform process that are easily affected by the stacking process. Note the following Table 2:

[169] Table 2

[170] Decompression, two bands stacked

[171] Decompression, one with stacking

[172] Decompression, input stacking and output dense

[173] Compression, dense input and stacked output

[174] Consider an example: decoding a compressed video frame, where the encoding process has caused many coefficients to be quantized to zero. The first stage of decompression cancels the entropy coding or bit coding of non-zero coefficients, and gives the value and the position of each value in the frame. This happens to be the information represented in a heap, and it is easy to store it in a heap, rather than immediately expanding it into a dense representation by explicitly filling all interval zero values.

[175] At this stage, the coefficients to be calculated in the inverse wavelet transform have been prepared. The end result of the inverse transform is a decompressed image ready for display; it is rarely sparse.

[176] (Like every stage) The first stage of the inverse wavelet transform is to extract data from two regions or "bands" of the coefficient data, and then combine them into a middle band filter calculation, the middle band will be in the same Used in later stages of the process. In this first stage, the data of the two bands are sparse and represented in the heap. A person can also produce the output of this stage in a heap, so that he or she does not need to fill in zeros. The calculations of Table 3 below are performed on the "band" stacks P1 and P2, its results are generated in the new stack R, and the filter calculation step W(p, q) is performed on the coefficient pairs from the two bands.

[177] Table 3

[178] while not both EOF(P1), EOP(P2) {

[179] I1=0; I2=0;

[180] guard(P1.indexP2.index, Pile_Read(P1, I1));

[181] guard(P1.indexP2.index, Pile_Read(P2, I2));

[182] Conditional_Append(R, true, W(I1, I2)); };

[183] Destroy_Pile(P1); Destroy_Pile(P2);

[184] It should be noted that the above calculations can still be expanded for parallel operation, as shown in Appendix B.

[185] By using the sparse representation, heap, as an intermediate result with many zero values, the time spent in calculating the wavelet transform can be reduced. This method improves the performance and computational efficiency of wavelet-based image compression and video compression products.

[186] Transformation range limit

[187] As yet another option, it is possible to reduce the amount of calculations associated with reconstructing data values into a predetermined data range. This calculation can be reduced by performing only a single cut operation. In one embodiment, this reduction may occur in the dequantizer module of the data compression/decompression system (ie, see the dequantizer 212 of FIG. 2). Of course, this feature can be implemented independently of the various other features described herein. The following explains more sample information about this optional feature.

[188] In digital image compression and digital video compression methods, an image (or frame) is represented as an array of numbers, each number representing the brightness of a zone, or the amount of a specific color (for example, red) in a zone. These areas are called pixels, and the numbers are called samples or composition values.

[189] Image compression or video compression is done using many different methods. As mentioned above, many of these methods include transformation calculations as a single step: through a sequence of arithmetic operations, the sample array representing the image is transformed into a different array of numbers called coefficients. The coefficients contain information about the image, but they are not uniform. One individually corresponds to the brightness or color of the cell. Although the transform contains the same image information, this information is distributed among the numbers in a way that facilitates the further calculation of the compression method.

[190] When images or frames compressed by this method are to be played back, they must be decompressed along with the compressed data. This usually involves, as a single step, the calculation using a coefficient array and generating an inverse transform of the sample array.

[191] The sample of an image or frame is usually represented by a short-length integer, generally represented by 8 binary bits. An 8-bit number can only represent 256 different values, and in these applications, these values are generally considered as an integer range from zero to 255 (including zero and 255) [0, 255].

[192] Many standards and operating conditions set stricter ranges than this. For example, in CCIR-601 (ITU-R BT.601-4), the pixel component (Y, U, V) sampling value is specified to a range smaller than [0, 255]. More specifically, the effective range of the lumen Y component in the illuminated part of the screen is specified to be within [16, 235], and the range of chromaticity components U, V is limited to the range of [16, 240]. Values outside these ranges may have meanings other than brightness, for example, to indicate synchronization events.

[193] Image and video compression methods can be divided into two categories, lossless and lossy compression. The way of operation of the lossless compression method is to generate the exact same value from the decompression as the value used for the compression. For these methods, since the output occupies the same digital range as the input, there is no range problem.

[194] However, lossy compression produces only expected approximations to the original input, rather than a decompressed output that matches each bit. By using this degree of freedom to slightly change the image, the lossy method can produce a greater compression ratio.

[195] In the decompression part of the lossy compression method, there is no guarantee that the calculated sample is the same as the corresponding original sample, and therefore, it is not guaranteed to occupy the same value range. Therefore, in order to satisfy the range condition of the image standard, it is necessary to include the step of limiting or clipping the calculated value to the specified range.

[196] The straightforward way to perform this tailoring step is as follows: For each calculated sample s, test whether s>max (maximum value), if so, set s=max; test whether s<min (minimum value), if Yes, then set s=min.

[197] Another way to perform this step uses the MAX and MIN operators found on a certain computing platform; then two operations are performed on each sample. The two methods shown, and many others, perform more calculations than simple arithmetic operations such as addition and subtraction.

[198] Since this processing can be performed independently for each sample value (each pixel) in an image or frame, it is an important part of the calculation in the decompression method. It should be noted that for almost all calculated samples that are within the required range under normal circumstances, both tests will fail. Therefore, both tests must be calculated.

[199] The aforementioned transform calculation usually has the following properties: one of the generated coefficients represents the total brightness of the entire frame or an effective part of the frame (a block in MPEG terminology). This coefficient is called "DC coefficient". Due to the way the transform is calculated, changing the DC coefficient will change the value of all samples in its frame or block in the same way, in proportion to the selection made. Therefore, for example, the value of each sample in the block can be increased by the same amount by adding a suitably selected constant to the DC coefficient of the block just before the calculation of the inverse transform.

[200] The calculation engine on which the compression method is executed usually has arithmetic instructions with saturation properties: when calculating a result, if it exceeds the representative range of its container (for 8-bit quantities, it is [0,255]), Then cut down the results to be within this range. For example, if a saturated subtraction instruction is given to the values 4 and 9, then the result (4-9=)-5 must be cut to replace the result (4-9=)-5, and the result 0 is returned. Similarly, the saturated addition instruction 250+10 will produce the result 255.

[201] In the following, among many compression methods, low-cost methods for cropping pixel component values obtained from decoding to an appropriate limit will be explained. In this embodiment, by adding a deviation value to the partial value, only one of the MAX/MIN operators is left, and one of the two clipping using saturation arithmetic is performed. Refer to an example in detail, when the required range is [llim, ulim]=[16, 240], see Table 4.

[202] Table 4

[203] 1. The deviation is added to the DC coefficients in each block, which results in each part after the transform filter

[204] Offset minus 16 (normal, -llim).

[205] Cost: One arithmetic operation per block or frame.

[206] 2. Ensure that the final arithmetic step of the inverse transformation is at zero saturation (cutting).

[207] Cost: Not necessary on most computing engines.

[208] 3. Interval 224 (normal, ulim-llim), apply MAX operation.

[209] Cost: One MAX operation per sample.

[210] 4. Use ADD (plus) 16 (general, llim) to eliminate deviation. Since it was just before MAX,

[211] So it cannot overflow. In saturation arithmetic, it does not need to be performed.

[212] Cost: ADD once per sample.

[213] It can now be seen that the calculation cost of the necessary range limit can be reduced from two MAX/MIM operations per sample to one ADD per block, one MAX per sample, and one simple ADD per sample.

[214] On some computing engines, such as the EQUATOR MAP-CA processor, the savings obtained using this method are far greater than the savings seen above. On these engines, several samples can be combined in one word and operated simultaneously. However, these block operations are limited to certain parts of the processor, and can be the limit resource of performance in compression applications. On such an engine, the fact that the ADD in step 4 above cannot overflow is of great significance. Step 4 does not need to use a specific partition ADD, but a normal ADD can be used to perform operations on several samples immediately like partitions. This ordinary operation uses a part of the processor that is not heavily loaded, and can be overflowed or executed at the same time as other necessary partition operations, resulting in a significant time saving in calculating the inverse transform.

[215] FIG. 6 shows a system 600 for compressing data according to an embodiment. As an option, the system 600 can be implemented in the environment of the aforementioned concepts presented above. However, of course, the system 600 can be implemented in any desired environment.

[216] The system 600 includes an encoder 602 included on a separate device 604 for encoding data to generate first compressed data in a first format. In addition, the transcoder 606 is included on the same separate device 604 as the encoder 602 for transcoding the first compressed data to generate second compressed data in a second format.

[217] In use, data is received in a separate device 604. This data is encoded by a separate device 604 to generate second compressed data in the first format. In addition, a separate device 604 is used to transcode the first compressed data to generate second compressed data in a second format.

[218] In one embodiment, encoding can be done in real time. In addition, transcoding can be done offline. In another embodiment, the first compressed data may be transcoded to generate second compressed data in a second format, so that the second compressed data can be adapted to match the capabilities of the communication network coupled to the separate device 604.

[219] As an option, the encoding can be performed using the first encoder. In addition, transcoding can be performed using a decoder and a second encoder, as shown in FIG. 6.

[220] The first format may also include a wavelet-based format. In addition, the second format may include a DCT-based format. In a specific embodiment, the second format may include an MPEG format. The following explains more example information about additional optional features.

[221] As mentioned above, there are several communication modes that utilize image and video sequences. In addition to viewing directly in real time, a person can capture an image or video sequence and send it at a later time immediately after the capture or delayed to a more favorable time.

[222] In addition, the reception of the video sequence can be done in a real-time mode where the video is watched like watching TV without storing the video, or in another mode where the sequence is stored for later viewing.

[223] In addition to other combinations, these different options are combined into three use cases. The three situations are:

[224] 1. The above-mentioned video phone or picture phone operation, in which both the transmitter and the receiver operate in real time. This requires all compression, encoding, and decoding to be performed in real time at the speed of video capture, and the transmission channel needs to carry full-rate compressed video.

[225] 2. Streaming operation, in the streaming operation, the video is captured and stored in the source or network in real time, and watched on the receiver. This requires real-time decoding, but allows a period of time to process the sequence before transmission. This mode requires at least a transmission channel from the network to the receiver to carry full-rate compressed video. In addition, for most transmission channels, the receiver must buffer a certain number of sequences in order to maintain smooth playback when the transmission rate changes.

[226] 3. Messaging or File-transfer (messaging or file-transfer) mode, in this mode, the video is captured and stored in the source, non-real-time transmitted to the receiver, and stored in the receiver for later playback. This mode allows operation on transmission channels that cannot carry full-rate real-time video, and allows the receiver to replay, pause, and control the experience.

[227] Images or videos captured and compressed in one format can be converted to another format. This operation is called transcoding. In the worst case, this is done by decompressing the input format into a full frame or video and then compressing it in the desired output format. For many format pairs, a cheaper method than this worst-case method can be used.

[228] In many networks, such as the International Cellular Telephone Network, different users may prefer or require images or videos in different formats. For example, even though the MPEG-4 standard provides a variety of options for shapes, sizes, speeds, and other parameters, all users support the standard, and this is the case. For this and other reasons, it is sometimes desirable for the sending and receiving devices to be able to negotiate which format to use in a particular transmission. In the simplest case, each device provides a list of formats that it can handle, and selects a commonly acceptable format from the intersection of the lists. There are more complex forms of negotiation, but the overall effect is the same: the sender only knows the format sent after the connection has started.

[229] When transcoding is required as part of the connection, it can be performed on the originating device or at an intermediate location. Some networks can provide transcoding services as part of network operations to provide mutual communication between devices with completely different native capabilities. This will help maintain complexity, so the cost of mobile units is lower.

[230] Due to the above-mentioned complete difference between the video data rate and the transmission channel rate, it may be advantageous to operate in the new mode described below. The device captures video, compresses it in real time using the low-complexity compression method described below, and stores the compressed video sequence. Then, at a later time, the device can convert the video sequence code into a format acceptable to the recipient or the network. This allows low-power operation, long battery life, and simpler circuitry in the device, while taking into account full compatibility with network format standards.

[231] One advantage of this type of operation is flexibility: 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 when the call is transferred. Since the devices do not need each to have a broadly optimized real-time implementation, the devices can support a wider range of formats in this way.

[232] Another advantage of the above type of operation is that transcoding does not need to operate at the speed of video capture, but can match the speed of the usually very low transmission network. The lower speed code conversion operation can be performed in a circuit that is smaller and consumes less power than the standard real-time compression uses. Therefore, the overall power consumption, battery life, complexity, and cost of the device are reduced.

[233] Another advantage of this type of operation is the ability to postpone the transmission of images and videos from the high cost of daytime phone prices to the lower cost of the evening price (or the current cellular phone pricing plan, or even free) time.

[234] Due to factors other than time, transmission has a lower price at other times. For example, a cellular phone has a lower cost when returning to its home location than when it is "roaming."

[235] The aforementioned postponed transmission does not require any postponement action by the user of the device. The device can automatically determine the transmission time based on the information it has about costs and schedules. Therefore, user convenience is preserved.

[236] Of course, it is felt that some messages have a higher urgency than others; the user can easily specify whether to postpone the transmission and for how long.

[237] When sending images and video in non-real time, the user of the device may make a call while the transmission is in progress, or when an incoming call is about to arrive, or when the connection is about to be disconnected for some other reason. Everyone in the field of computer networking knows that the provision of information that enables the interrupted transmission to be resumed without having to resend the part of the information that has been successfully transmitted.

[238] This interruptible transmission can allow for deliberate interruptions such as putting a call on hold and accidental interruptions such as disconnection.

[239] The receiving device does not need to have the ability to store the entire video sequence. The converted code source device can be sent to a streaming receiver, including receivers that are simpler and less capable than the transmitter. This makes it easy to use advanced transcoding devices into the network of existing devices.

[240] Standard image and video formats provide error detection, error correction, and burst error control methods. By transcoding to these standard formats, the device can make full use of standard error recovery features while using low-complexity and low-power capture compression methods.

[241] The idea of using low-complexity real-time processing to capture the signal of interest and then transcoding it into a format more suitable for transmission at a later time can be applied to signals other than images and videos, and other than wireless transmission Other purposes, and devices other than mobile personal devices. Example e.g., military intelligent sensing, infrared sensing, telescope spectrum signal radio telescope, the SETI channel, biochemical measurement, the seismic signals, and many other applications can benefit from this basic scheme.

[242] FIG. 7 shows a system 700 that uses multiple encoders 702 on a single integrated circuit 704 (ie, ASIC) to compress data. As an option, the system 700 can be implemented in the environment of the above-mentioned concept. Of course, the system 700 can also be implemented in any desired environment.

[243] As shown in the figure, the first encoder is combined on a single integrated circuit 704 for encoding the first group of signals. In addition, the second encoder is combined on the same single integrated circuit 704 as the first encoder for encoding the second set of data. Of course, for similar purposes, more encoders can be combined on a single integrated circuit 704.

[244] In use, data is received in a separate integrated circuit. Then, multiple encoders combined on a single integrated circuit are used to encode the data.

[245] In one embodiment, multiple channels on a single integrated circuit can be used to encode data. In addition, the data can be encoded into a wavelet-based format.

[246] Many video compression applications are better served by ASIC services that include multiple encoding or decoding stages. An example is the category of personal video recorders (PVR) or digital video recorders (DVR), for example, TiVo and Replay TV products, in which compression and decompression must be performed at the same time. Another example is a video surveillance recorder, where many video signals from the camera must be multiplexed, compressed, and recorded together.

[247] Placing several compression circuits on a single ASIC, or combining compression and decompression circuits on a single ASIC, provides direct and indirect advantages. Direct advantages include reduced package count, reduced pin count, reduced power consumption, and reduced circuit board area. All these advantages have contributed to reducing product costs.

[248] Indirect advantages include the ability to combine the video part and the multiplexing circuit on the same chip, further reducing the number of pins and circuit board area.

[249] There are a variety of compression methods that require much less circuitry than conventional and standard compression methods to achieve, for example, the algorithm developed by Droplet Technology, Inc. TM described with reference to Figure 2-5. Due to their superior design, multiple examples of this advanced compression method can now be integrated into a single ASIC or other integrated circuit.

[250] Further provides another separate module system and method for compressing data. In use, a single module is used to receive photons. Then, a separate module is used to output compressed data representing photons.

[251] As an option, the compressed data can be encoded into a wavelet-based format. In addition, transformation operations related to encoding can be performed by analog methods. The separate module may further include an imager.

[252] This embodiment can be used to construct an imager array, namely a CMOS or CCD camera or other device, to help the entire process of capturing and transmitting compressed digital video.

[253] Directly digitized images and videos occupy many bits; this is common in compressing images and videos for storage, transmission, and other purposes. Several basic compression methods are known, and many specialized improvements of these methods. The general method can use three-stage processing to express its characteristics: transformation, quantization, and entropy coding.

[254] The intent of the transformation stage in a video compressor is to concentrate the energy or information of the source picture into a form as compact as possible by taking advantage of the local similarities and graphics in the picture or sequence. This embodiment is very effective for "typical" inputs, and ignoring them cannot compress "random" or "pathological" inputs.

[255] Many image compression and video compression methods, such as JPEG [1], MPEG-2 [2] and MPEG-4 [4], use discrete cosine transform (DCT) as the transformation stage.

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

[257] Wavelet transform involves the repeated use of wavelet filter pairs for a set of data in one or more dimensions. For image compression, 2-D wavelet transform (horizontal and vertical) can be used; for video, 3-D wavelet transform (horizontal, vertical, and time) can be used.

[258] The wavelet filter processes the image (or part of the image) to produce two images, each image is generally half the input size, one can be regarded as "low pass" or average or blurred, and the other One is "Qualcomm" or detailed or edge. All the information in the input picture is maintained, and (in many cases) the original picture can be completely reconstructed from the transformed image pair. A wavelet filter pair generally processes images in one dimension, that is, horizontal, vertical, or time (a time series across frames). The full wavelet transform is composed of a series of these steps used continuously in several dimensions. Generally, not all results of the earlier steps are subject to the processing of later steps; sometimes the high-pass image is maintained without further filtering.

[259] The camera has an imager device in its heart: a device that responds to and records the changing intensity and color of light for later display and other purposes. The common imaging devices of today's digital still cameras and video cameras are CCD and CMOS. Both of these imaging devices accumulate charge corresponding to light in each pixel; their difference lies in the way they transfer and read out the amount of charge.

[260] CMOS ("Complementary Metal Oxide Semiconductor") imagers are a newer technology and can be manufactured cheaper than CCDs. A key advantage of CMOS imagers is that the processing of the imager chip is very similar to that of digital logic chips. This makes it easier to include control and other functions on the same chip. However, both chips must be built with analog circuits at the lowest level to measure analog charge or voltage or current that represents the amount of light seen.

[261] The CMOS imager is very similar in structure to DRAM ("Dynamic Random Access Memory") and transfers the charge representing the amount of light seen in the pixel to the edge of the array along a grid of metal traces across the array . This readout method is a standard practice for memory chips and is widely used in the industry.

[262] Although the CCD imager is an older technology, it is widely used and provides lower noise and better sensitivity. A CCD ("Charge Coupled Device") transfers the charge representing the light seen in the pixel from one cell to another in a bucket-brigade manner, and transfers it to the edge of the array.

[263] The difference between a CMOS imager or a CCE imager and a digital storage device is that the charge transferred to the edge of the array not only represents a "0" or "1" bit, but also represents a range of brightness values. Therefore, analog/digital conversion is required. Before this conversion, the signal is amplified; it is often subjected to other processing to eliminate errors and variability in chip manufacturing and operation. A common step is "correlated double sampling". In "correlated double sampling", dark samples are extracted and stored as the measured value of the leakage current of this part of the circuit, and subtracted from the image samples by Reduce the noise figure.

[264] The analog processing is performed in a differential amplifier, which is a circuit that mainly responds to the difference between its inputs, rather than the absolute magnitude of either of the two.

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

[266] Since a person can choose to perform A/D conversion earlier or later in the processing chain, he or she has the freedom of choice to perform certain stages of the overall processing in analog or digital form.

[267] In some devices, the wavelet filter pair as a step of the wavelet consists of a very simple set of addition and subtraction of adjacent and nearby pixel values. For example, the available filter pair called "Haar wavelet" is just the sum and difference in the following equations #1.1H and 1.2H.

[268] Equation #1.1H and 1.2H

[269] Ln=X2n+X2n+1 Equation 1.1H

[270] Hn=X2n-X2n+1 Equation 1.2H

[271] This produces a "high" transformed image and a "low" transformed image from the same two samples of the input image "X".

[272] Other wavelet filters can also be used; some are quite complex, but some are as simple as taking several Haar steps, adding them together, and scaling them with constants.

[273] For example, one of the transformations specified in the JPEG 2000 standard [1] is the reversible 5-3 transformation proposed in the previous equations #1.1 and 1.2.

[274] It can be seen that the entire wavelet filter pair performs 5 addition/subtraction operations and two scaling operations; in the continuous analog domain, there is no floor operation.

[275] This in turn makes it possible to easily and naturally complete the addition of analog values through a differential amplifier (for addition or subtraction), and scaling with constants becomes the easiest operation among all operations on analog signals, requiring only one Two resistors.

[276] On the contrary, the sum of values in the digital domain requires an adder logic circuit for each bit, plus a carry chain; it is easier to scale with some specific constants, but it is generally not cheap to scale in digital logic circuits.

[277] Since CMOS and CCD imagers are now built with differential amplifiers to amplify and subtract noise from pixel sampling on the chip, it is easy to perform certain processing steps on the chip before the digital/analog conversion. These steps need to add some analog circuits on the chip, but it can be a small number of circuits.

[278] This in turn causes that in some devices of wavelet transform, including those preferred devices, the first step of calculation is the most expensive. This is because each of the first few steps reduces the amount of images to be processed in later stages; there is no need to further process the "high-pass" images output by each filter stage. Therefore, performing the first step or the first few steps in the simulation before the analog-to-digital conversion can significantly reduce the digital processing, because only the "low-pass" image must be digitally processed. Benefits can be obtained by reducing the number of digital circuits, thereby reducing the chip area it occupies, or by running digital circuits slower, thereby reducing power consumption and heat generation of the device.

[279] DCT can be used to perform the transformation stage of image or video compression; this process transforms the image into a spectrum, and the continuous sampling of the spectrum represents the content of a certain range of spatial frequencies in the image. Some implementations of DCT use Haar steps, and these steps can also be performed in an analog way to benefit.

[280] In wavelet transform, a horizontal filter pair can usually be calculated as the first step. This also seems to facilitate simulation filtering. Before performing the first vertical filter step, two horizontal steps can be performed, and it is also more convenient in an analog manner.

[281] The vertical filter step requires the presence of vertically adjacent pixels at the same time. In the conventional image scanning raster sequence, the time interval (line time interval) at which these pixels appear is large. However, in chip imagers such as CMOS imagers, consider rearranging the scan order so that several lines appear together, and the vertical filter step can also be performed in an analog manner before or after the first horizontal filter step. Is reasonable.

[282] The imager chip that captures color images generally places a color filter before each pixel, limiting its response to one of red, green, or blue. These filters are arranged in a pattern so that all three colors can be sampled adjacently everywhere in the image.

[283] However, digital video standards prefer to use permutations other than RGB components. More widely used is YUV, or YCbCr, where the Y component represents black and white brightness or "lumens", and the U and V components represent the color difference between blue or red and lumens. The reason for this method of representation is that the human visual response allows a lower definition in the C component, thus allowing a smaller digital representation of the image. YUV stands for easy compression too. The color image chip sometimes provides a circuit to perform an operation that converts RGB pixel values into YUV values either analog (before conversion) or digital (after conversion).

[284] The color conversion and wavelet filter steps can be combined in any of several ways. For example, the analog color conversion can precede the first analog wavelet filter step; in this case, the wavelet filter works on the full-bandwidth Y component, or half-bandwidth U and V components. Alternatively, a wavelet filter can be applied to the R, G, and B components, first from the imager array, and then color converted to YUV; in this case, the filter operates on the three full-bandwidth component signals.

[285] In another arrangement, the usual color conversion step can be completely eliminated, and the RGB components can be supplied to the wavelet transform. There are several wavelet transform versions that complete the conversion to YUV as part of their operations. In this arrangement, in order not to increase the number of analog circuits, reduce the number of digital circuits, and clean the connection with the digital wavelet compression process, the analog circuit for performing the first wavelet step is used instead of the analog circuit for color conversion.

[286] Therefore, it shows how to make the compressed digital video capture subsystem more effective by combining the analog calculation of the initial wavelet filter step. This can be done for monochrome imagers and can be combined with the color conversion stage of color digital imagers in several ways. This method improves the performance and computational efficiency of wavelet-based image compression and video compression products.

[287] Although various embodiments have been described above, it should be understood that they are only presented by way of illustration and are not intended to limit the present invention. Therefore, the width and scope of the preferred embodiments are not limited by any of the above-mentioned exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.

[288] Appendix A

[289] For the quadratic equation, there can be three data values [X2N-1 X2N-2 X2N-4], and three coefficients are required;

[290] <math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>a</mi> <mn>0</mn> </msub> </mtd> <mtd> <msub> <mi>a</mi> <mn>1</mn> </msub> </mtd> <mtd> <msub> <mi>a</ mi> <mn>2</mn> </msub> </mtd> </mtr> </mtable> </mfenced> <mfenced open='[' close=']'> <mtable> <mtr> < mtd> <msup> <mi>x</mi> <mn>0</mn> </msup> </mtd> </mtr> <mtr> <mtd> <msup> <mi>x</mi> <mn>1</mn> </msup> </mtd> </mtr> <mtr> <mtd> <msup> <mi>x</mi> <mn>2</mn> </msup></mtd> </mtr> </mtable> </mfenced> <mo>=</mo> <msub> <mi>a</mi> <mn>0</mn> </msub> <mo>+</mo> <msub> <mi>a</mi> <mn>1</mn> </msub> <mi>x</mi> <mo>+</mo> <msub> <mi>a</mi> <mn>2</mn> </msub > <msup> <mi>x</mi> <mn>2</mn> </msup> </mrow> </math>

[291] The negative half of the second derivative may be

So maybe only interested in a2. In this case, it is simpler to find the quadratic equation:

[292] <math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mover> <mi>a</mi> <mo>~< /mo> </mover> <mn>0</mn> </msub> </mtd> <mtd> <msub> <mover> <mi>a</mi> <mo>~</mo> </ mover> <mn>1</mn> </msub> </mtd> <mtd> <msub> <mover> <mi>a</mi> <mo>~</mo> </mover> <mn> 2</mn> </msub> </mtd> </mtr> </mtable> </mfenced> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msup> <mrow> <mo>(</mo> <mi>x</mi> <mo>-</mo> <mn>2</mn> <mi>N</mi> <mo>)</mo> </mrow> <mn>0</mn> </msup> </mtd> </mtr> <mtr> <mtd> <msup> <mrow> <mo>(</mo> <mi>x</mi> <mo>-</mo> <mn>2</mn> <mi>N</ mi> <mo>)</mo> </mrow> <mn>1</mn> </msup> </mtd> </mtr> <mtr> <mtd> <msup> <mrow> <mo>( </mo> <mi>x</mi> <mo>-</mo> <mn>2</mn> <mi>N</mi> <mo>)</mo> </mrow> <mn >2</mn> </msup> </mtd> </mtr> </mtable> </mfenced> <mo>=</mo> <msub> <mover> <mi>a</mi> <mo >~</mo> </mover> <mn>0</mn> </msub> <mo>+</mo> <msub> <mover> <mi>a</mi> <mo>~</ mo> </mover> <mn>1</mn> </msub><mrow> <mo>(</mo> <mi>x</mi> <mo>-</mo> <mn>2</mn> <mi>N</mi> <mo>)</mo> </mrow> <mo>+</mo> <msub> <mover> <mi>a</mi> <mo>~</mo> </mover> <mn>2</mn> </msub> <msup> <mrow> <mo>(</mo> <mi>x</mi> <mo>-</mo> <mn>2 </mn> <mi>N</mi> <mo>)</mo> </mrow> <mn>2</mn> </msup> </mrow> </math>

[293] Because of:

[294] <math> <mrow> <msub> <mi>a</mi> <mn>2</mn> </msub> <mo>=</mo> <msub> <mover> <mi>a </mi> <mo>~</mo> </mover> <mn>2</mn> </msub> </mrow> </math>

[295] Three linear equations with Vandermonde type coefficient matrices can be solved.

[296] <math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mover> <mi>a</mi> <mo>~< /mo> </mover> <mn>0</mn> </msub> </mtd> <mtd> <msub> <mover> <mi>a</mi> <mo>~</mo> </ mover> <mn>1</mn> </msub> </mtd> <mtd> <mrow> <msub> <mover> <mi>a</mi> <mo>~</mo> </mover> <mn>2</mn> </msub> </mrow> </mtd> </mtr> </mtable> </mfenced> <mfenced open='[' close=']'> <mtable> <mtr > <mtd> <msup> <mrow> <mo>(</mo> <mo>-</mo> <mn>1</mn> <mo>)</mo> </mrow><mn>0</mn> </msup> </mtd> <mtd> <msup> <mrow> <mo>(</mo> <mo>-</mo> <mn>2</mn> <mo>)</mo> </mrow> <mn>0</mn> </msup > </mtd> <mtd> <msup> <mrow> <mo>(</mo> <mo>-</mo> <mn>4</mn> <mo>)</mo> </mrow> <mn>0</mn> </msup> </mtd> </mtr> <mtr> <mtd> <msup> <mrow> <mo>(</mo> <mo>-</mo> <mn >1</mn> <mo>)</mo> </mrow> <mn>1</mn> </msup> </mtd> <mtd> <msup> <mrow> <mo>(</mo > <mo>-</mo> <mn>2</mn> <mo>)</mo> </mrow> <mn>1</mn> </msup> </mtd> <mtd> <msup > <mrow> <mo>(</mo> <mo>-</mo><mn>4</mn> <mo>)</mo> </mrow> <mn>1</mn> </msup> </mtd> </mtr> <mtr> <mtd> <msup> <mrow> <mo>(</mo> <mo>-</mo> <mn>1</mn> <mo>)</mo> </mrow> <mn >2</mn> </msup> </mtd> <mtd> <msup> <mrow> <mo>(</mo> <mo>-</mo> <mn>2</mn> <mo> )</mo> </mrow> <mn>2</mn> </msup> </mtd> <mtd> <msup> <mrow> <mo>(</mo> <mo>-</mo> <mn>4</mn> <mo>)</mo> </mrow> <mn>2</mn> </msup> </mtd> </mtr> </mtable> </mfenced> <mo >=</mo> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mtd> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub > </mtd> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>4 </mn> </mrow> </msub> </mtd> </mtr> </mtable> </mfenced> </mrow> </math>

[297] <math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mover> <mi>a</mi> <mo>~< /mo> </mover> <mn>0</mn> </msub> </mtd> <mtd> <msub> <mover> <mi>a</mi> <mo>~</mo> </ mover> <mn>1</mn> </msub> </mtd> <mtd> <msub> <mover> <mi>a</mi> <mo>~</mo> </mover> <mn> 2</mn> </msub> </mtd> </mtr> </mtable> </mfenced> <mo>=</mo> <mfenced open='[' close=']'> <mtable> < mtr> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> </mtd> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub > </mtd> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>4 </mn> </mrow> </msub> </mtd> </mtr> </mtable> </mfenced> <mfrac> <mn>1</mn> <mn>6</mn> </mfrac > <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <mn>16</mn> </mtd> <mtd> <mn>12</mn> </mtd> <mtd> <mn>2</mn> </mtd> </mtr> <mtr> <mtd> <mo>-</mo> <mn>12</mn> </mtd> <mtd> <mo >-</mo> <mn>15</mn> </mtd> <mtd> <mo>-</mo> <mn>3</mn> </mtd> </mtr> <mtr> <mtd> <mn>2</mn> </mtd> <mtd> <mn>3</mn> </mtd> <mtd> <mn>1</mn> </mtd> </ mtr> </mtable> </mfenced> </mrow> </math>

[298] The negative half of the second derivative is:

[299] <math> <mrow> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mn>2</mn> <msub > <mi>a</mi> <mn>2</mn> </msub> <mo>=</mo> <mo>-</mo> <mfrac> <mn>1</mn> <mn >2</mn> </mfrac> <mn>2</mn> <msub> <mover> <mi>a</mi> <mo>~</mo> </mover> <mn>2</ mn> </msub> <mo>=</mo> <mo>-</mo> <mfrac> <mn>1</mn> <mn>6</mn> </mfrac> <mfenced open=' ['close=']'> <mtable> <mtr> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo> -</mo> <mn>1</mn> </mrow> </msub> </mtd> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub> </mtd> <mtd> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>4</mn> </mrow> </msub > </mtd> </mtr> </mtable> </mfenced> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <mn>2</mn> </mtd > </mtr> <mtr> <mtd> <mo>-</mo> <mn>3</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> < /mtd> </mtr> </mtable> </mfenced> <mo>=</mo> <mo>-</mo> <mfrac> <mn>2</mn> <mn>6</mn> </mfrac> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <mfrac> <mn>3</mn> <mn>6</mn> </mfrac> <msub> <mi>X</mi> <mrow> <mn>2</mn> <mi>N</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub > <mo>-</mo> <mfrac> <mn>1</mn> <mn>6</mn> </mfrac> <msub> <mi>X</mi> <mrow> <mn>2 </mn> <mi>N</mi> <mo>-</mo> <mn>4</mn> </mrow> </msub> </mrow> </math>

[300] Appendix B

[301] Heap Introduction

[302] When the required algorithm has a narrow data width, serial data dependence, or frequent control statements (for example, "if", "for", "while" statements), it is difficult for high-throughput parallel processors Programming. This embodiment overcomes all these three problems, individually or in combination. Entropy coding applications are an important application class with all three types of problems.

[303] Parallel Processing

[304] There are three types of parallelism that can be used in processors to produce good results.

[305] 1) The first type is supported by multiple functional units and allows processing to be performed simultaneously in each functional unit. The super-scaler processor architecture and the VLIW (Very Long Instruction Word) processor architecture allow instructions to be sent to each of several functional units in the same cycle. In general, the waiting time or completion time of each type of functional unit is different. The simplest functions (for example, bitwise AND) are usually completed in a single cycle, while the floating-point addition function may take 3 or more cycles.

[306] 2) The second type of parallel processing is supported by the pipeline operation of each functional unit. For example, floating-point addition may take 3 cycles to complete, and is implemented in three consecutive sub-functions that each require 1 cycle. By setting the pipeline register between the sub-functions, the second floating-point addition can be started in the first sub-function in the same cycle in which the previous floating-point addition started in the second sub-function. With this measure, a floating-point addition can be started and completed in each cycle, although any single floating-point addition requires 3 cycles to complete.

[307] 3) The third type of parallel processing available is different examples of using different field segments of a word for the same calculation. For example, a 32-bit word can be divided into four 8-bit field segments on a 32-bit processor. If the data item is small enough to fit 8 bits, then all 4 values can be processed with the same single instruction.

[308] In each individual cycle, the number of data items equal to the product of the number of field segments multiplied by the start number of functional units can be processed.

[309] Loop unrolling

[310] There is a customary general method of programming multiple and/or pipelined functional units: find many examples of the same calculation, and perform the corresponding operation from each example together. The paradigm can be generated by loop unrolling techniques or by some other source of the same calculation.

[311] Although loop unrolling is a universal technique, a special example helps to understand its benefits. For example, consider program A)

[312] for i=0:1:255,{S(i)}; where the body S(i) is an operation sequence that depends on i {S1(i); S2(i); S3(i); S4( i); S5(i);}, and the calculation of S(i) is completely independent of the calculation of S(j), ji. It is not necessary to assume that the operations S1(i); S2(i); S3(i); S4(i); S5(i); are independent of each other; instead, it can be assumed that the dependency relationship from one operation to the next is forbidden to restart Sort.

[313] It can also be assumed that these same dependencies need to be completed before the next operation can be started. If each (pipeline) operation requires two cycles to complete (even if the pipeline execution unit can produce a new result each cycle), a sequence of five operations requires 10 cycles to complete. In addition, loop transfer generally requires an additional 3 cycles, unless the programming tool can make S4(i); S5(i); overlap with the transfer delay. If the transfer delay is overlapped, then the program A) needs 256/4*10=640 cycles to complete, if the transfer delay is not overlapped, then 256/4*13=832 cycles are required to complete.

[314] Procedure B)

[315] 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 the number of expensive control flow changes by a factor of four. More importantly, it provides an opportunity to reorder the constituent operations of each of the four S(i). So procedures A) and B) are equivalent to procedure C)

[316] for n=0:4:255, {S1(n); S2(n); S3(n); S4(n); S5(n);

[317] S1(n+1); S2(n+1); S3(n+1); S4(n+1); S5(n+1);

[318] S1(n+2); S2(n+2); S3(n+2); S4(n+2); S5(n+2);

[319] S1(n+3); S2(n+3); S3(n+3); S4(n+3); S5(n+3);

[320] }；

[321] Using the above set of assumptions about dependence and independence, an equivalent program can be established D)

[322] for n=0:4:255, {S1(n); S1(n+1); S1(n+2); S1(n+3);

[323] S2(n); S2(n+1); S2(n+2); S2(n+3);

[324] S3(n); S3(n+1); S3(n+2); S3(n+3);

[325] S4(n); S4(n+1); S4(n+2); S4(n+3);

[326] S5(n); S5(n+1); S5(n+2); S5(n+3);

[327] }; S1(n); S1(n+1); can be released in the first cycle, S1(n+2); S1(n+3); can be released in the second cycle. S1(n); S1(n+1); will be completed at the beginning of the third cycle (two cycles have passed), so that S2(n); S2(n+1); can be issued. In this way, the next two operations can be issued in each subsequent cycle, so that the entire body can be executed in the same 10 cycles. Program D) runs in less than a quarter of the time of program A).

[328] Most parallel processors have conditional branch instructions, which require several delay cycles between the instruction itself and the point where the branch actually occurs. During this delay period, other instructions can be executed. As long as the transfer conditions are known early enough, and the compiler or other programming tool supports the execution of instructions during the delay period, the transfer only takes up an opportunity to issue instructions. This technique can even be applied to program A) when the transition condition (i=255) is known at the beginning of the loop.

[329] Excessive expansion will produce the opposite result. First, once all publishing opportunities are used (as in Procedure D), the additional expansion will not accelerate further. Secondly, each unfolding cycle round generally requires additional registers to save the state of that particular round. If the total number of required registers exceeds the available number, some registers must be overflowed into the cache and then restored in the next cycle. Instructions that need to be issued to support overflow and reloading lengthen the program time, and ultimately do not speed up when the loop is unrolled. The final conclusion is that there is an optimal number of loop expansions.

[330] Unroll the loop that includes exception handling

[331] Now consider program A')

[332] for i=0:1:255, {S(i); if C(i) then T(I(i))};

[333] where C(i) is a rare and true (for example, one in 64) exception condition that only depends on S(i), and T(I(i)) is some kind of lengthy exception handling, for example, 1024 Operations. I(i) is information calculated by S(i) required for exception handling. To illustrate, let us assume that T(I(i)) adds 16 operations to each cycle in program A) on average, which is more than 4 operations in the main body of the loop. This rare but lengthy exception handling is a common programming problem. How can this problem be dealt with without losing the benefits of deployment?

[334] Protected Order

[335] One measure is through the use of protected instructions, a device that can be used on many processors. The protected instruction specifies a Boolean value as an additional operand, its meaning is that the instruction always occupies the expected functional unit, but if the protection fails, the retention of the result is prohibited.

[336] In the execution of if-then-else, use protection as an if condition. The instructions of the then clause are protected by the if conditions, and the instructions of the else clause are protected by the negation of the if conditions. In either case, both clauses must be executed. The result of the then clause only updates the instances where the protection is true, and the result of the else clause only updates the instances where the protection is false. All instances execute the instructions of the two clauses and tolerate this penalty, which is not the pipeline delay loss required for the condition change in the control flow.

[337] As in procedure A), if the protection is overwhelmingly true, and the else clause is large, then the protected measure will be punished heavily. In this case, all instances are subject to the large else clause penalty, although only a few instances are affected by it.

[338] If you want the operation S to be protected by the condition C, you can program it as follows:

[339] guard(C,S);

[340] First expansion

[341] Program A) can be expanded to program D')

[342] for n=0:4:255, {S1(n); S1(n+1); S1(n+2); S1(n+3); S2(n); S2(n+1) ; S2(n+2); S2(n+3); S3(n); S3(n+1); S3(n+2); S3(n+3); S4(n); S4(n+ 1); S4(n+2); S4(n+3); S5(n); S5(n+1); S5(n+2); S5(n+3); if C(n) then T (I(n)); if C(n+1) then T(I(n+1)); dp n="d35"/> if C(n+2)then T(I(n+2)); if C(n+3)then T(I(n+3)); };

[343] Given the above example parameters, T(I(n)) will not be executed in 77% of the cycle, T(I(n)) will be executed once in 21% of the cycle, and only in 2% of the cycle. T(I(n)) is executed more than once in. Obviously, the operations of inserting T(I(n)), T(I(n+1)), T(I(n+2)) and T(I(n+3)) only get very few benefits.

[344] Heap Handling

[345] A new alternative method is heap processing. A heap is a sequential storage object generally stored in RAM. The intention of the heap is to write successively, and then read successively from the beginning. A variety of methods are defined for heap objects.

[346] In order to practice the heap and its methods in a parallel processing environment, their implementation is required to be several sequential (not transferred to subroutine) code instructions. It is also required that this serial code does not contain branch instructions. The following describes the realization of this method. This realization may make the heap novel and valuable.

[347] 1) Create a heap through the Create_Pile(P) method. This allocates storage area and initializes internal state variables.

[348] 2) The initial method of writing to the heap is Conditional_Append(pile, condition, record). This method adds the record to the pile when and only when the condition is true.

[349] 3) When the heap has been completely written, it is ready to be read by the Rewind_Pile(P) method. This adjusts the internal variables so that reading starts from the record written first.

[350] 4) The method EOF(P) generates a Boolean value indicating whether all records of the heap have been read.

[351] 5) The method Pile_Read(P, record) reads the next sequential record from the pile P.

[352] 6) The method Destroy_Pile(P) discards the heap P by de-allocating all its state variables.

[353] Use heap split condition processing

[354] It is now possible to transform program D') into program E') by means of heap P.

[355] Create_Pile(P); for n=0:4:255, {S1(n); S1(n+1); S1(n+2); S1(n+3); S2(n); S2 (n+1); S2(n+2); S2(n+3); dp n="d36"/> S3(n); S3(n+1); S3(n+2); S3(n+3); S4(n); S4(n+1); S4(n+2); S4(n+3); S5(n ); S5(n+1); S5(n+2); S5(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 EOF(P){ Pile_Read(P,I); T(I); }; Destroy_Pile(P);

[356] Program E') operates by storing the information I required for abnormal calculation T on the heap P. Only the I record corresponding to the abnormal condition C(n) is written, so the number of I records in P (for example, 16) is much less than the number of loops in the original program A) (for example, 256). Then, a separate while loop reads the pile P once and executes all abnormal calculations T. Since P only contains records I where C(n) is true, only these cases are processed.

[357] The second loop is a bit trickier than the first loop, because the number of while loops in the second loop is 16 on average, which is uncertain. Therefore, a while loop is required instead of a for loop. When the EOF method indicates that all records have been read from the heap, the while loop terminates.

[358] As previously asserted and explained below, Conditional_Append method calls can be implemented in sequence and without transfer. This means that the first cycle is still unfolding in an effective way, with few vain release opportunities.

[359] Begin the second loop

[360] The second loop is not unrolled in program E'), and it is still inefficient. However, the program E') can be transformed into the program F') by virtue of the four stacks P1, P2, P3, and P4. The result is that F') unfolds two loops and brings efficiency improvements.

[361] Create_Pile(P1); Create_Pile(P2); Create_Pile(P3); Create_Pile(P4); for n=0:4:255, {S1(n); S1(n+1); S1(n+2 ); S1(n+3); S2(n); S2(n+1); S2(n+2); S2(n+3); S3(n); S3(n+1); S3(n +2); S3(n+3); S4(n); S4(n+1); S4(n+2); S4(n+3); S5(n); S5(n+1); S5 (n+2); S5(n+3); Conditional_Append(P1, C(n), I(n)); Conditional_Append(P2, C(n+1), I(n+1)); Conditional_Append(P3 , C(n+2), I(n+2)); Conditional_Append(P4, C(n+3), I(n+3)); }; Rewind(P1); Rewind(P2); Rewind(P3 ); Rewind(P4); while notall EOP(Pi){ Pile_Read(P1,I1); Pile_Read(P2,I2); Pile_Read(P3,I3); Pile_Read(P4,I4); guard(not EOF(P1),S); T(I1); guard(not EOF(P2) ), S); T(I2); guard(not EOF(P3), S); T(I3); guard(not EOF(P4), S); T(I4); }; Destroy_Pile(P1); Destroy_Pile (P2); Destroy_Pile(P3); Destroy_Pile(P4);

[362] Program F') is a program E') with an expanded second loop. The unfolding is done by dividing the separate pile of program E') into four piles, each of which can be processed independently of each other. Each round of the second loop in program F') processes one record from each of these four heaps. Since each record is processed independently, 3 other T operations can be inserted into each T operation.

[363] The control of the while loop must be improved to loop until all heaps are processed. Moreover, since all heaps are generally not completed in the same cycle, the T in the while loop must be protected. Whenever the number of records in the two heaps is very different from each other, the efficiency is reduced, but there is a high probability that the heap contains a similar number of records (the law of huge quantities).

[364] Of course, this heap technique can be used recursively. If T itself contains a lengthy conditional clause T', then some additional heap can be used to separate T'out of the second loop and unroll the third loop. Many practical applications have several such nested exception clauses.

[365] Implement heap processing

[366] The implementation of heap objects and their methods must be kept simple in order to meet the above implementation standards.

[367] a) Except for Create_Pile and Destroy_Pile, the method implementation must be a few instructions directly inserted into the code.

[368] b) The implementation should not contain transfer instructions.

[369] The main point is that a heap is composed of a linear array allocated in RAM and a pointer, index. The current value of index is the position of the next record to be read or written. The write size of the array, sz, is a pointer whose value is the maximum value of index during the write process of the heap. The EOF method can be implemented as a direct insertion condition (szindex (index)). The pointer base (base) is a value that points to the first position written in the heap. It is set by the Create_Pile method.

[370] The Conditional_Append method copies the record to the heap array starting at the index value. Then, the index is incremented by a calculation amount that is 0 or the size of the record (sz_record). Since the parameter condition has a value of 1 representing true (true) or a value of 0 representing false (false), the index can be calculated as follows without transfer:

[371] index=index+condition*sz_record;

[372] Of course, there are many variations of this calculation, many of which do not include a given specific value multiplied by a variable. It can also be calculated using protection as follows:

[373] guard(condition, index=index+sz_record);

[374] It should be noted that the record is copied to the heap without considering the condition. If the condition is false, the record is overwritten with the next record; if the condition is true, then the current record is written to the next record. This next record may or may not be the record itself covered by the following record. As a result, it is generally best to write to the heap as little as possible, even if this means recalculating some (redundant) data when reading and processing records.

[375] The Rewind method is implemented through sz_index; index=base;. This operation records the amount of data written for the EOF method, and then resets the index to the beginning.

[376] The Pile_Read method copies the next part of the heap (of length sz_record) to I and increments index.

[377] index=index+sz_record;

[378] The Destroy_Pile method deallocates the storage location of Pile.

[379] All these methods (except for Create_Pile and Destroy_Pile) can be implemented with a few direct insert instructions and do not need to be transferred.

[380] Therefore, heap processing allows the unwinding of loops in the presence of transfers, and results in improved performance. This technique particularly allows the parallel execution of lengthy exception clauses. The cost is the need to write and reread the most appropriate amount of data to/from RAM.