Multiple codec-imager system and method

RELATED APPLICATION(S)

[0001] The present application claims priority from a first provisional application filed Apr. 19, 2002 under serial No. 60/374,061, and a second provisional application filed Jun. 21, 2002 under serial No. 60/390,380, which are each incorporated herein by reference in their entirety.

FIELD OF THE INVENTION

[0002] The present invention relates to data compression, and more particularly to compressing data utilizing wavelets.

BACKGROUND OF THE INVENTION

[0003] Video “codecs” (compressor/decompressor) are used to reduce the data rate required for data communication streams by balancing between image quality, processor requirements (i.e. cost/power consumption), and compression ratio (i.e. resulting data rate). The currently available compression approaches offer a different range of trade-offs, and spawn a plurality of codec profiles, where each profile is optimized to meet the needs of a particular application.

[0004] 2D and 3D wavelets are current alternatives to the DCT-based codec algorithms carried out by MPEG video distribution profiles. Wavelets have been highly regarded due to their pleasing image quality and flexible compression ratios, prompting the JPEG committee to adopt a wavelet algorithm for its JPEG2000 still image standard. Unfortunately, most wavelet implementations use very complex algorithms, requiring a great deal of processing power, relative to DCT alternatives. In addition, wavelets present unique challenges for temporal compression, making 3D wavelets particularly difficult.

[0005] For these reasons, wavelets have never offered a cost-competitive advantage over high volume industry standard codecs like MPEG, and have therefore only been adopted for niche applications. There is thus a need for a commercially viable implementation of 3D wavelets that is optimized for low power and low cost.

[0006] Digital image compression and digital video compression are commercially important processes that can be performed either by a program running on a general-purpose computer processor (including a DSP: digital signal processor), or by dedicated hardware such as an ASIC: Application Specific Integrated Circuit.

[0007] Digital video compression methods implemented in dedicated hardware are commercially available (from Sony and others). However, the standard compression methods MPEG-1, MPEG-2, MPEG-4, JPEG, Motion-JPEG, and JPEG-2000 have thus far required so much dedicated circuitry that it has been found practical to implement only one compression or decompression process in a single ASIC.

DISCLOSURE OF THE INVENTION

[0008] A system and method are provided for compressing data utilizing multiple encoders on a single integrated circuit. Initially, data is received in a single integrated circuit. The data is then encoded utilizing a plurality of encoders incorporated on the single integrated circuit.

[0009] In one embodiment, data may be encoded utilizing multiple channels on the single integrated circuit. Moreover, the data may be encoded into a wavelet-based format.

[0010] Another single module system and method are provided for compressing data. In use, photons are received utilizing a single module. Thereafter, compressed data representative of the photons is outputted utilizing the single module.

[0011] As an option, the compressed data may be encoded into a wavelet-based format. Moreover, the transform operations associated with the encoding may be carried out in analog. The single module may further include an imager.

BRIEF DESCRIPTION OF THE DRAWINGS

[0012]FIG. 1 illustrates a system for compressing data utilizing multiple encoders on a single integrated circuit.

[0013]FIG. 2 illustrates a framework for compressing/decompressing data, in accordance with one embodiment.

[0014]FIG. 3 illustrates a method for compressing/decompressing data, in accordance with one embodiment.

[0015]FIG. 4 shows a data structure on which the method of FIG. 3 is carried out.

[0016]FIG. 5 illustrates a method for compressing/decompressing data, in accordance with one embodiment.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0017]FIG. 1 illustrates a system <b>100</b> for compressing data utilizing multiple encoders <b>102</b> on a single integrated circuit <b>104</b> (i.e. ASIC). As shown, a first encoder is embodied on the single integrated circuit <b>104</b> for encoding a first set of data. Moreover, a second encoder is embodied on the same single integrated circuit <b>104</b> as the first encoder for encoding a second set of data. Of course, more encoders may be embodied on the single integrated circuit <b>104</b> for similar purposes.

[0018] In use, data is received in the single integrated circuit. The data is then encoded utilizing a plurality of encoders incorporated on the single integrated circuit.

[0019] In one embodiment, data may be encoded utilizing multiple channels on the single integrated circuit. Moreover, the data may be encoded into a wavelet-based format.

[0020] Many applications for video compression would be better served by an ASIC containing multiple coding or decoding stages. An example is the category of Personal Video Recorders (PVR) or Digital Video Recorders (DVR), such as the products of TiVo and Replay TV, wherein the processes of compression and decompression must be performed simultaneously. Another example is video surveillance recorders, wherein many video signals from cameras must be multiplexed, compressed, and recorded together.

[0021] Putting several compression circuits on a single ASIC, or a combination of compression and decompression circuits on a single ASIC, offers both direct and indirect advantages. Direct advantages include reduced package count, reduced pin count, reduced power consumption, and reduced circuit board area. All of these contribute to reduced product cost.

[0022] Indirect advantages include the possibility to incorporate video selection and multiplexing circuitry on the same chip, further reducing the pin count and board area.

[0023] There are now video compression methods, for example the algorithms described during reference to FIGS. <b>2</b>-<b>5</b> developed by Droplet Technology, Inc.(R), that require far less circuitry to implement than the conventional and standard compression methods. Due to their superior design, multiple instances of these advanced compression methods may now be integrated onto a single ASIC or other integrated circuit.

[0024] Another single module system and method for compressing data are further provided. In use, photons are received utilizing a single module. Thereafter, compressed data representative of the photons is outputted utilizing the single module.

[0025] As an option, the compressed data may be encoded into a wavelet-based format. Moreover, the transform operations associated with the encoding may be carried out in analog. The single module may further include an imager.

[0026] The present embodiment may be implemented for building imager arrays—CMOS or CCD cameras or other devices—to facilitate the whole process of capturing and delivering compressed digital video.

[0027] Directly digitized images and video take lots of bits; it is common to compress images and video for storage, transmission, and other uses. Several basic methods of compression are known, and very many specific variants of these. A general method can be characterized by a three-stage process: transform, quantize, and entropy-code.

[0028] The intent of the transform stage in a video compressor is to gather the energy or information of the source picture into as compact a form as possible by taking advantage of local similarities and patterns in the picture or sequence. The present embodiment works well on “typical” inputs and ignores their failure to compress “random” or “pathological” inputs.

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

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

[0031] A wavelet transform comprises the repeated application of wavelet filter pairs to a set of data, either in one dimension or in more than one. For image compression, one may use a 2-D wavelet transform (horizontal and vertical); for video one may use a 3-D wavelet transform (horizontal, vertical, and temporal).

[0032] A wavelet filter pair processes an image (or a section of an image) to produce two images, each typically half the size of the input, that can generally be regarded as “low-pass” or average or blurred, for one, and “high-pass” or detail or edges, for the other. The full information in the input picture is retained, and the original can be reconstructed exactly (in many cases), from the transformed image pair. A wavelet filter pair generally processes an image in one dimension, either horizontally, vertically, or temporally (across a time sequence of frames). The full wavelet transform is composed of a series of these steps applied in several dimensions successively. In general, not all of the results of earlier steps are subjected to later steps; the high-pass image is sometimes kept without further filtering.

[0033] A camera has at its heart an imager device: something that responds to and records varying intensities and colors of light for later display and other uses. Common imager devices for digital still cameras and video cameras today are CCDs and CMOS arrays. Both accumulate an electric charge in response to light at each pixel; they differ in the way they transfer and read out the amount of charge.

[0034] CMOS (“complimentary metal-oxide semiconductor”) imagers are the newer technology, and can be made less expensively than CCDs. A key advantage of CMOS imagers is that the processing of the imager chip resembles the processing of digital logic chips rather closely. This makes it easier to include control and other functions on the same chip. Both kinds of chip, however, are necessarily built from analog circuits at the lowest level to measure the analog charge or voltage or current that represents the amount of light seen.

[0035] CMOS imagers are very similar in structure to DRAMs (“dynamic random-access memories”), and transfer the charge that represents the light seen in a pixel to the edge of the array along a grid of metal traces that cross the array. This readout method is standard practice for memory chips and is well developed in the industry.

[0036] CCD imagers, while an older technology, are well developed and offer lower noise and better sensitivity. CCDs (“charge-coupled devices”) transfer the charge that represents the light seen in a pixel to the edge of the array by passing it from cell to cell in bucket-brigade fashion.

[0037] A CMOS imager or CCD imager differs from a digital memory device in that the charge transferred to the edge of the array represents not just a “0” or “1” bit value, but a range of brightness values. Thus an analog-to-digital conversion is required. Preceding this conversion, the signal is amplified; it is often subjected to other processing to cancel out errors and variability in the chip fabrication and operation. A common processing step is “correlated double sampling”, in which a dark sample is taken and stored as a measure of the leakage current for this part of the circuit, and subtracted from the image sample to reduce noise patterns.

[0038] The analog processing is done in a differential amplifier, a circuit that responds primarily to the difference between its inputs rather than to the absolute size of either one.

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

[0040] Because one can choose to do the analog-to-digital sooner or later in the chain, he or she has the option of doing some stages of the overall processing either in analog or in digital form.

[0041] The wavelet filter pair that is a step of a wavelet consists, in some implementations, of a very simple set of additions and subtractions of adjacent and nearby pixel values. For instance, useful filter pair, called the “Haar Wavelet”, is just the sum and difference as follows in Equations #1.1, and 1.2.

Equations #1.1, and 1.2

<i>L</i>_n<i>=X</i>_2n<i>+X</i>_2n+1  eq 1.1

<i>H</i>_n<i>=X</i>_2n<i>−X</i>_2n+1  eq 1.2

[0042] This generates one sample of the “High” transformed image and one sample of the “Low” transformed image from the same two samples of the input image “X”.

[0043] Other wavelet filters are possible and are used; some are very complex, but some are as simple as doing a few Haar steps, summing them together, and scaling them by constant amounts.

[0044] For instance, one of the transforms specified in the JPEG 2000 standard [1] is the reversible 5-3 transform. See Equations #1.1J, and 1.2J. <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>Equations</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>#1</mi><mo></mo><mi>.1</mi><mo></mo><mi>J</mi></mrow><mo>,</mo><mrow><mi>and</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>1.2</mn><mo></mo><mi>J</mi></mrow></mrow><mo></mo><mstyle><mtext /></mstyle><mo></mo><mrow><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>-</mo><mrow><mo>⌊</mo><mfrac><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>2</mn></mrow></msub></mrow><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>1.1</mn><mo></mo><mi>J</mi></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>Y</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>=</mo><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><mrow><mo>⌊</mo><mfrac><mrow><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mn>2</mn></mrow><mn>4</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>1.2</mn><mo></mo><mi>J</mi></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00001.TIF" id="EMI-M00001" he="53.04285" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00001" attachment-type="nb" file="US20030197629A1-20031023-M00001.NB" /></attachments></maths>

[0045] As one can see, the entire wavelet filter pair takes 5 add/subtract operations and two scaling operations; in the continuous analog domain the floor operations disappear.

[0046] It turns out that summing analog values together is easily and naturally accomplished by differential amplifiers (for either addition or subtraction), and that scaling by a constant amount is the easiest operation of all for an analog signal, requiring only a resistor or two.

[0047] In contrast, summing values in the digital domain requires an adder logic circuit for each bit plus a carry chain; scaling by some special constant amounts is easy but general scaling is not cheap in digital logic.

[0048] Because CMOS and CCD imagers are presently built using differential amplifiers to amplify and subtract noise from the pixel samples on the chip, it is fairly easy to do some simple processing steps on the chip before digital-to-analog conversion. Doing these steps adds some analog circuitry to the chip, but it can be a small amount of circuitry.

[0049] It turns out in some implementations of the wavelet transform, including those one prefers, that the first step computed is the most expensive. This is because each of the first several steps reduces the amount of image to be processed by later stages; one does not necessarily further process the “high pass” image output by each filter stage. Thus implementing the first step or first few steps in analog, before doing analog-to-digital conversion, can reduce the digital processing significantly, since only the “low pass” image must be digitally processed. The benefit can be taken either by reducing the amount of digital circuitry, thus reducing the chip area it occupies, or by running the digital circuitry slower, thus reducing its power consumption and heat generation.

[0050] The transform stage of image or video compression can be done using a DCT; this process transforms an image into a spectrum, whose successive samples represent the content of a range of spatial frequencies in the image. Some implementations of DCT use Haar steps, and these could benefit from being done in analog as well.

[0051] Usually in wavelet transforms, one can compute a horizontal filter pair as the first step. This seems convenient for the analog filtering as well. One can do two horizontal steps before doing the first vertical filter step, and this would also be convenient in analog.

[0052] Vertical filter steps require the simultaneous presence of vertically adjacent pixels. In the conventional image scanning raster order, such pixels appear widely separated in time (a line time apart). However, in chip imagers such as CMOS imagers, it is reasonable to consider rearranging the scan order so that several lines appear together, and then it is feasible to do a vertical filter step in analog as well, either before or after the first horizontal filter step.

[0053] Imager chips that capture color images typically place a color filter in front of each pixel, restricting it to one of red, green, or blue response. These filters are arranged in a pattern so that all three colors are sampled adjacently everywhere in the image.

[0054] Digital video standards, however, prefer an arrangement of components other than RGB. The most widely used is YUV, or YC_bC_r, in which the Y component represents black-and-white brightness or “luma” and the U and V components represent color differences between blue or red and luma. The reason for this representation is that human visual response allows lower resolution in the C components, thus allowing smaller digital representations of images. The YUV representation is convenient for compression as well. Color imager chips sometimes provide circuitry to do the operation of transforming RGB pixel values into YUV values, either analog (before conversion) or digital (after conversion).

[0055] One can combine color conversion with wavelet filter steps in any of several ways. For instance, the analog color conversion can precede the first analog wavelet filter step; in this case the wavelet filters work on full-bandwidth Y component and on half-bandwidth U and V components. Alternatively, the wavelet filters can be applied to the R, G, and B components from the imager array first, followed by color conversion to YUV; in this case the filters work on three full-bandwidth component signals.

[0056] In another arrangement, one can omit the conventional color conversion step altogether and provide RGB components to the wavelet transform. There are versions of the wavelet transform that accomplish conversion to YUV as part of their operation. In this arrangement, the analog circuitry that does the color conversion is replaced by the analog circuitry that does the first wavelet steps, for no net increase in analog circuitry, reduced digital circuitry, and a very clean interface with the digital wavelet compression processing.

[0057] It has thus been shown how to make a compressed digital video capture subsystem more efficient by incorporating analog computation of the initial wavelet filter step or steps. This can be done for monochrome imagers, and can be combined in several ways with the color conversion stage of color digital imagers. This method improves the performance and computational efficiency of wavelet-based image compression and video compression products.

[0058] More information regarding an optional framework <b>200</b> in which the present embodiment may be implemented will now be set forth.

[0059]FIG. 2 illustrates a framework <b>200</b> for compressing/decompressing data, in accordance with one embodiment. Included in this framework <b>200</b> are a coder portion <b>201</b> and a decoder portion <b>203</b>, which together form a “codec.” The coder portion <b>201</b> includes a transform module <b>202</b>, a quantizer <b>204</b>, and an entropy encoder <b>206</b> for compressing data for storage in a file <b>208</b>. To carry out decompression of such file <b>208</b>, the decoder portion <b>203</b> includes a reverse transform module <b>214</b>, a de-quantizer <b>212</b>, and an entropy decoder <b>210</b> for decompressing data for use (i.e. viewing in the case of video data, etc).

[0060] In use, the transform module <b>202</b> carries out a reversible transform, often linear, of a plurality of pixels (in the case of video data) for the purpose of de-correlation. Next, the quantizer <b>204</b> effects the quantization of the transform values, after which the entropy encoder <b>206</b> is responsible for entropy coding of the quantized transform coefficients.

[0061]FIG. 3 illustrates a method <b>300</b> for compressing/decompressing data, in accordance with one embodiment. In one embodiment, the present method <b>300</b> may be carried out in the context of the transform module <b>202</b> of FIG. 2 and the manner in which it carries out a reversible transform. It should be noted, however, that the method <b>300</b> may be implemented in any desired context.

[0062] In operation <b>302</b>, an interpolation formula is received (i.e. identified, retrieved from memory, etc.) for compressing data. In the context of the present description, the data may refer to any data capable of being compressed. Moreover, the interpolation formula may include any formula employing interpolation (i.e. a wavelet filter, etc.).

[0063] In operation <b>304</b>, it is determined whether at least one data value is required by the interpolation formula, where the required data value is unavailable. Such data value may include any subset of the aforementioned data. By being unavailable, the required data value may be non-existent, out of range, etc.

[0064] Thereafter, an extrapolation operation is performed to generate the required unavailable data value. See operation <b>306</b>. The extrapolation formula may include any formula employing extrapolation. By this scheme, the compression of the data is enhanced.

[0065]FIG. 4 shows a data structure <b>400</b> on which the method <b>300</b> is carried out. As shown, during the transformation, a “best fit” <b>401</b> may be achieved by an interpolation formula <b>403</b> involving a plurality of data values <b>402</b>. Note operation <b>302</b> of the method <b>300</b> of FIG. 3. If it is determined that one of the data values <b>402</b> is unavailable (see <b>404</b>), an extrapolation formula may be used to generate such unavailable data value. More optional details regarding one exemplary implementation of the foregoing technique will be set forth in greater detail during reference to FIG. 5.

[0066]FIG. 5 illustrates a method <b>500</b> for compressing/decompressing data, in accordance with one embodiment. As an option, the present method <b>500</b> may be carried out in the context of the transform module <b>202</b> of FIG. 2 and the manner in which it carries out a reversible transform. It should be noted, however, that the method <b>500</b> may be implemented in any desired context.

[0067] The method <b>500</b> provides a technique for generating edge filters for a wavelet filter pair. Initally, in operation <b>502</b>, a wavelet scheme is analyzed to determine local derivatives that a wavelet filter approximates. Next, in operation <b>504</b>, a polynomial order is chosen to use for extrapolation based on characteristics of the wavelet filter and a numbers of available samples. Next, extrapolation formulas are derived for each wavelet filter using the chosen polynomial order. See operation <b>506</b>. Still yet, in operation <b>508</b>, specific edge wavelet cases are derived utlizing the extrapolation formulas with the available samples in each case.

[0068] See Appendix A for an optional method of using Vandermonde type matrices to solve for the coefficients. Moreover, additional optional information regarding exemplary extrapolation formulas and related information will now be set forth in greater detail.

[0069] To approximate Y_2N−1from the left, one may fit a quadratic polynomial from the left. Approximating the negative of half the 2nd derivative at 2N−1 using the available values yields Equation # 1.1.R. See Appendix A for one possible determination of this extrapolating quadratic. <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>Equation</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>#1</mi><mo></mo><mrow><mi>.1</mi><mo>.</mo><mi>R</mi></mrow></mrow><mo></mo><mstyle><mtext /></mstyle><mo></mo><mrow><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><mrow><mo>-</mo><mfrac><mn>1</mn><mn>3</mn></mfrac></mrow><mo></mo><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub><mo>-</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>2</mn></mrow></msub></mrow><mo>-</mo><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>4</mn></mrow></msub><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>1.1</mn><mo>.</mo><mi>R</mi></mrow></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00002.TIF" id="EMI-M00002" he="29.9943" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00002" attachment-type="nb" file="US20030197629A1-20031023-M00002.NB" /></attachments></maths>

[0070] Equation # 1.1.R may be used in place of Equation #1.1 J when point one is right-most. The apparent multiply by 3 can be accomplished with a shift and add. The division by 3 is trickier. For this case where the right-most index is 2N−1, there is no problem calculating Y2N-2 by means of Equation #1.2J. In the case where the index of the right-most point is even (say 2N), there is no problem with Equation #1.1J, but Equation #1.2J involves missing values. Here the object is to subtact an estimate of Y from the even X using just the previously calculated odd indexed Y s, Y₁and Y₃in the case in point. This required estimate at index 2N can be obtained by linear extrapolation, as noted above. The appropriate formula is given by Equation #1.2.R. <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>Equation</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>#1</mi><mo></mo><mrow><mi>.2</mi><mo>.</mo><mi>R</mi></mrow></mrow><mo></mo><mstyle><mtext /></mstyle><mo></mo><mrow><msub><mi>Y</mi><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow></msub><mo>=</mo><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow></msub><mo>+</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub></mrow><mo>-</mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>3</mn></mrow></msub><mo>+</mo><mn>2</mn></mrow><mn>4</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>1.2</mn><mo>.</mo><mi>R</mi></mrow></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00003.TIF" id="EMI-M00003" he="29.9943" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00003" attachment-type="nb" file="US20030197629A1-20031023-M00003.NB" /></attachments></maths>

[0071] A corresponding situation applies at the left boundary. Similar edge filters apply with the required extrapolations from the right (interior) rather than from the left. In this case, the appropriate filters are represented by Equations #1.1.L and 1.2.L. <maths id="MATH-US-00004" num="4"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>Equations</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>#1</mi><mo></mo><mrow><mi>.1</mi><mo>.</mo><mi>L</mi></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>and</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>1.2</mn><mo>.</mo><mi>L</mi></mrow></mrow><mo></mo><mstyle><mtext /></mstyle><mo></mo><mrow><msub><mi>Y</mi><mn>0</mn></msub><mo>=</mo><mrow><mrow><mo>-</mo><mfrac><mn>1</mn><mn>3</mn></mfrac></mrow><mo></mo><mrow><mo>(</mo><mrow><msub><mi>X</mi><mn>0</mn></msub><mo>-</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>X</mi><mn>1</mn></msub></mrow><mo>-</mo><msub><mi>X</mi><mn>3</mn></msub><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>1.1</mn><mo>.</mo><mi>L</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>Y</mi><mn>0</mn></msub><mo>=</mo><mrow><msub><mi>X</mi><mn>0</mn></msub><mo>+</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>Y</mi><mn>1</mn></msub></mrow><mo>-</mo><msub><mi>Y</mi><mn>3</mn></msub><mo>+</mo><mn>2</mn></mrow><mn>4</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>1.2</mn><mo>.</mo><mi>L</mi></mrow></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00004.TIF" id="EMI-M00004" he="53.04285" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00004" attachment-type="nb" file="US20030197629A1-20031023-M00004.NB" /></attachments></maths>

[0072] The reverse transform fiters can be obtained for these extrapolating boundary filters as for the original ones, namely by back substitution. The inverse transform boundary filters may be used in place of the standard filters in exactly the same circumstances as the forward boundary filters are used. Such filters are represented by Equations #2.1.Rinv, 2.2.Rinv, 2.1.L.inv, and 2.2.L.inv. <maths id="MATH-US-00005" num="5"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>Equations</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>#2</mi><mo></mo><mrow><mi>.1</mi><mo>.</mo><mi>Rinv</mi></mrow></mrow><mo>,</mo><mrow><mn>2.2</mn><mo>.</mo><mi>Rinv</mi></mrow><mo>,</mo><mrow><mn>2.1</mn><mo>.</mo><mi>L</mi><mo>.</mo><mi>inv</mi></mrow><mo>,</mo><mrow><mn>2.2</mn><mo>.</mo><mi>L</mi><mo>.</mo><mi>inv</mi></mrow></mrow><mo></mo><mstyle><mtext /></mstyle><mo></mo><mrow><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><mrow><mrow><mo>-</mo><mn>3</mn></mrow><mo></mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub></mrow><mo>+</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>2</mn></mrow></msub></mrow><mo>-</mo><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>4</mn></mrow></msub><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>2.1</mn><mo>.</mo><mi>R</mi></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>inv</mi></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow></msub><mo>=</mo><mrow><msub><mi>Y</mi><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow></msub><mo>-</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub></mrow><mo>-</mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>N</mi></mrow><mo>-</mo><mn>3</mn></mrow></msub><mo>+</mo><mn>2</mn></mrow><mn>4</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>2.2</mn><mo>.</mo><mi>R</mi></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>inv</mi></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>X</mi><mn>0</mn></msub><mo>=</mo><mrow><mrow><mrow><mo>-</mo><mn>3</mn></mrow><mo></mo><msub><mi>Y</mi><mn>0</mn></msub></mrow><mo>+</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>X</mi><mn>1</mn></msub></mrow><mo>-</mo><msub><mi>X</mi><mn>3</mn></msub><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>2.1</mn><mo>.</mo><mi>L</mi></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>inv</mi></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>X</mi><mn>0</mn></msub><mo>=</mo><mrow><msub><mi>Y</mi><mn>0</mn></msub><mo>-</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mn>3</mn><mo></mo><msub><mi>Y</mi><mn>1</mn></msub></mrow><mo>-</mo><msub><mi>Y</mi><mn>3</mn></msub><mo>+</mo><mn>2</mn></mrow><mn>4</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mn>2.2</mn><mo>.</mo><mi>L</mi></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>inv</mi></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00005.TIF" id="EMI-M00005" he="99.13995" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00005" attachment-type="nb" file="US20030197629A1-20031023-M00005.NB" /></attachments></maths>

[0073] Thus, one embodiment may utilize a reformulation of the 5-3 filters that avoids the addition steps of the prior art while preserving the visual properties of the filter. See for example, Equations #3.1, 3.1 R, 3.2, 3.2L. <maths id="MATH-US-00006" num="6"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>Equations</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>#3</mi><mo></mo><mi>.1</mi></mrow><mo>,</mo><mrow><mn>3.1</mn><mo></mo><mi>R</mi></mrow><mo>,</mo><mn>3.2</mn><mo>,</mo><mrow><mn>3.2</mn><mo></mo><mi>L</mi></mrow></mrow><mo></mo><mstyle><mtext /></mstyle><mo></mo><mrow><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>-</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>2</mn></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow></mrow><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>3.1</mn></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00006.TIF" id="EMI-M00006" he="29.9943" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00006" attachment-type="nb" file="US20030197629A1-20031023-M00006.NB" /></attachments></maths>  <i>Y</i>_2N+1=(<i>X</i>_2N+1<b>+{fraction (1/2)})−(</b><i>X</i>_2N+½)  eq 3.1R <maths id="MATH-US-00007" num="7"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mo>(</mo><mrow><msub><mi>Y</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mo>⌊</mo><mfrac><mrow><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub></mrow><mn>4</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>3.2</mn></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>(</mo><mrow><msub><mi>Y</mi><mn>0</mn></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mrow><msub><mi>X</mi><mn>0</mn></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mo>⌊</mo><mfrac><msub><mi>Y</mi><mn>1</mn></msub><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>3.2</mn><mo></mo><mi>L</mi></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00007.TIF" id="EMI-M00007" he="40.0869" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00007" attachment-type="nb" file="US20030197629A1-20031023-M00007.NB" /></attachments></maths>

[0074] In such formulation, certain coefficients are computed with an offset or bias of ½, in order to avoid the additions mentioned above. It is to be noted that, although there appear to be many additions of ½ in this formulation, these additions need not actually occur in the computation. In Equations #3.1 and 3.1 R, it can be seen that the effects of the additions of ½ cancel out, so they need not be applied to the input data. Instead, the terms in parentheses (Y₀+½) and the like may be understood as names for the quantities actually calculated and stored as coefficients, passed to the following level of the wavelet transform pyramid.

[0075] Just as in the forward case, the JPEG-2000 inverse filters can be reformulated in the following Equations #4.2, 4.2L, 4.1, 4.1R. <maths id="MATH-US-00008" num="8"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>Equations</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>#4</mi><mo></mo><mi>.2</mi></mrow><mo>,</mo><mrow><mn>4.2</mn><mo></mo><mi>L</mi></mrow><mo>,</mo><mn>4.1</mn><mo>,</mo><mrow><mrow><mn>4.1</mn><mo></mo><mrow><mi>R</mi><mo></mo><mstyle><mtext /></mstyle><mo>(</mo><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mrow><msub><mi>Y</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>-</mo><mrow><mo>⌊</mo><mfrac><mrow><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub></mrow><mn>4</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>4.2</mn></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>(</mo><mrow><msub><mi>X</mi><mn>0</mn></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mrow><msub><mi>Y</mi><mn>0</mn></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>-</mo><mrow><mo>⌊</mo><mfrac><msub><mi>Y</mi><mn>1</mn></msub><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>4.2</mn><mo></mo><mi>L</mi></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>=</mo><mrow><msub><mi>Y</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>+</mo><mrow><mo>⌊</mo><mfrac><mrow><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mo>(</mo><mrow><msub><mi>X</mi><mrow><mrow><mn>2</mn><mo></mo><mi>n</mi></mrow><mo>+</mo><mn>2</mn></mrow></msub><mo>+</mo><mrow><mn>1</mn><mo>/</mo><mn>2</mn></mrow></mrow><mo>)</mo></mrow></mrow><mn>2</mn></mfrac><mo>⌋</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>eq</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>4.1</mn></mrow></mtd></mtr></mtable></math><img file="US20030197629A1-20031023-M00008.TIF" id="EMI-M00008" he="75.1275" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00008" attachment-type="nb" file="US20030197629A1-20031023-M00008.NB" /></attachments></maths>  (<i>X</i>_2N+1+½)=<i>Y</i>_2N+1+(<i>X</i>_2N+½)  eq 4.1R

[0076] As can be seen here, the values taken as input to the inverse computation are the same terms produced by the forward computation in Equations #3.1˜3.2L and the corrections by ½ need never be calculated explicitly.

[0077] In this way, the total number of arithmetic operations performed during the computation of the wavelet transform is reduced.

[0078] While various embodiments have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of a preferred embodiment should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.