CN1272740C

CN1272740C - Multi-resolution image data management system and method based on wavelet-like transform and sparse data coding

Info

Publication number: CN1272740C
Application number: CNB018203647A
Authority: CN
Inventors: C·K·崔; H·－Y·高; L·钟
Original assignee: Picsurf Inc
Current assignee: Qualcomm Technologies Inc
Priority date: 2000-10-12
Filing date: 2001-10-11
Publication date: 2006-08-30
Anticipated expiration: 2021-10-11
Also published as: CN1479907A; US20050053301A1; JP2007110753A; EP1332465A1; US20060072838A1; EP1332465A4; JP2004514311A; JP4707681B2; US6978049B2; WO2002031756A1; US6549674B1; US7206451B2; AU2002213135A1; JP2007159154A; US6807308B2; US20030123744A1; JP4511788B2

Abstract

An image processing system processes tiles in a predefined order (168). A wavelet transform uses short filters applied to image boundaries to generate edge coefficients. Long filters are used to image data at interior locations to generate non-edge coefficients (172). Both filters are applied only to image data within the title and only to transform coefficients within the earlier sets of transformed data. A corresponding decoder is provided at the client (180).

Description

Multi-resolution image data management system and method based on wavelet-like transform and sparse data coding

Invention field

Present invention relates in general to treatment of picture, compression, transmission and storage in computer system, personal digital assistant, digital camera and miscellaneous equipment, particularly a kind of image management system and method, wherein can and under multiple resolution, watch by any specific window size, and can be printed, prune or operate through digitally coded image.

Background technology

Image can be by multiple stage resolution ratio storage.The coded image of low class resolution ratio is less, therefore, compares with high-resolution, can be with less bandwidth transmission, with less space storage.When image is stored as multiple resolution, preferably view data is separated into orderly one group of set or son file, wherein each additional son file provides the required additional data of resolution that improves image from a level to next level.In addition, when improving image resolution ratio, the image data amount in each son file roughly is directly proportional with relevant resolution increase with the specific factor (for example 4).For example, if each stage resolution ratio is adjacent level and differs 4 times of (as: level 0:32 * 32, level 1:64 * 64, level 2:128 * 128, Deng), then the coded image data amount of each stage resolution ratio should be substantially equal to next higher class resolution ratio the coded image data amount 25%.From another viewpoint, the data volume that is used for from the first order to the next stage improving the son file of image resolution ratio is to approximate three times of data volume in the son file of the first order greatly ideally.

As everyone knows, the wavelet compression of image produces some stage resolution ratios automatically.Especially, if to image effect N " layer " wavelet transformation, then produce the data of N+1 stage resolution ratio, wherein the last LL sub-band of data comprises the lowest resolution level, and all sub-band data constitute the highest resolution level together.For simplicity, " layer " of wavelet transformation will be called " level " sometimes.On each Spatial Dimension, each stage resolution ratio is adjacent level and differs factor 2.We can be designated as minimum thumbnail stage resolution ratio 0 grade, and the highest resolution level is designated as the N level, and this is the resolution of final or primary image.

A first aspect of the present invention is based on two kinds of observations.First kind is traditional during with most of special-purpose data compression and coding method when using, and the data volume in the N level that is produced by wavelet compression is often successively decreased with geometric series.For example, the data volume of 0 class resolution ratio normally 1 class resolution ratio data volume 80%, and ideally, it should be 25% of 1 a class resolution ratio data volume.As a result, the data that comprise of the data of 0 class resolution ratio are significantly more than showing 0 grade of amount that image is required.In other words, 0 grade of data provide 0 grade of low resolution show unnecessary high-quality, therefore, the information required with the image that shows 0 class resolution ratio only is provided is compared, the obtainable compressibility of institute is lower.

Second kind of viewpoint is that the low resolution image data coefficient quantization is that full resolution shows, rather than low resolution shows, represents because these data coefficient not only are used to produce the low resolution of image, and the high-resolution that also is used to produce image is represented.

According to this first aspect of the present invention, as mentioned above, preferably the subarray of each stage resolution ratio or the image data amount in the son file roughly are proportional to the associated resolution of this stage resolution ratio increases.

A second aspect of the present invention is based on following viewpoint, that is: wavelet transformation acts on the border of the sheet of image or piece, with sheet in the image of avoiding regenerating or block boundary illusion traditionally.Wavelet transformation can be implemented as FI R (finite impulse response (FIR)) wave filter with persistence length." length " expression is used to generate the data sample number of each coefficient.Wavelet transformation is generally about the center symmetry, and when the edge of the wave filter of realizing wavelet transformation at sheet or piece, and half of wave filter or almost half will extend in the adjacent sheet or piece usually.As a result, usually in the process of a sheet of wavelet image, must not only in storer, keep the part of adjacent sheet, also must in storer, keep the border coefficient of the adjacent sheet of every grade of wavelet transformation.Like this, avoid burst effect (being also referred to as sheet boundary effect or illusion or boundary artefacts) to increase execution usually to the computing machine of the wavelet transformation of image or the memory requirement of equipment, also can increase the complicacy of conversion program, because need to follow the tracks of adjacent sheet or the data boundary of piece and the memory location of coefficient.According to a second aspect of the invention, preferably have a kind of small echo or wavelet-like transform, it can only act on the data of processed image block, and will the data of this change action in adjacent block, also can not produce tangible boundary artefacts.Such conversion will reduce memory requirement, and wavelet compression that can simplified image.

Well-known in the prior art, digital picture can once be compressed a part, rather than once compression is whole, thereby reduces memory requirement.For example, the dct transform that is used for the JPEG compression of image and coding is used for the sheet of 8 * 8 pixels traditionally.But a known problem of image being carried out fragment process is that burst produces the sheet boundary effect of not expecting.The boundary effect of DCT burst is considered to acceptable in jpeg image, because sheet is small-sized, makes that the burst effect is more not obvious to human eye.

But, when using small echo or wavelet-like transform rather than dct transform, very little sheet, impracticable as 8 * 8 pixels.Wavelet-like transform has been proved to be than dct transform provides advantage more obvious data compression, therefore, if only utilize the working storage of moderate just can avoid the burst effect, preferably uses wavelet-like transform.

Therefore, a kind of image processing system and method preferably are provided, and it is by using the sheet of modest size, as the wavelet-like transform of the sheet of 64 * 64 or 32 * 32 or 64 * 32 pixels, utilize an amount of working storage to handle image, avoid producing burst (sheet border) effect of not expecting simultaneously.

A third aspect of the present invention is based on following viewpoint, that is, the optimum quantization level that is applied to wavelet coefficient is not only different between each varitron wave band, and is also different between the zones of different of image.Especially, comprise the image-region on many " features " (its feature is level or perpendicular line or border normally) than the more difficult compression in the zone that comprises less feature.That is, do not causing under the situation about reducing from the image-region quality of packed data regeneration, the intensive image-region of feature can not be compressed as the more not intensive image-region of feature like this.Therefore, preferably provide a kind of compression of images and coded system, its quantification program is used the wavelet coefficient in the intensive zone of less quantization factor quantization characteristic, and uses bigger quantization factor quantification to have the wavelet coefficient in the zone of less feature.

Summary of the invention

Put it briefly, the present invention is a kind of image processing system and method, is used for the conversion that gang is predetermined, as wavelet-like transform, is applied to the view data of image, to produce the changing image data; Also be used for data compression method is applied to this changing image data, to produce image file.This image processing system and method are carried out burst to the image that captures, and handle these sheets by predefined procedure.Sheet is the view data non-overlapping portions.Every picture data are applied to this view data sheet by the transform layer that will be scheduled to family and obtain handling, thereby produce continuous transformation series manifold.In a preferred embodiment, described transform layer is the continuous application of same clan wavelet decomposition conversion, comprises the boundary filter and the inside wave filter that is applied to the data in the data array interior zone of the data that are applied to processed data array boundary.

The transformation series manifold of being handled by each transform layer comprises fringing coefficient that is positioned at transformation series manifold outer boundary place and the non-fringing coefficient that is positioned at transformation series manifold interior location place.The transformation series manifold comprises last transformation series manifold and the one or more transformation series manifold of elder generation that is produced by last transform layer.

Used transformed filter comprises one or more edge transition wave filters, and it is applied to the view data of sheet boundary and is positioned at each coefficient of the close boundary of transformation series manifold of elder generation, to produce fringing coefficient; Also comprise one or more inner wave filters, it is applied to the view data at sheet interior location place and the coefficient at the transformation series manifold interior location place of elder generation, to produce non-fringing coefficient.The filtering support of edge transition wave filter is shorter than inner transformation wave filter, and edge transition wave filter and inner transformation wave filter all are view data and the conversion coefficients in the mapping ensemble of elder generation that only is applied in the sheet.

Boundary filter comprises a short and low spatial filter, and the view data on the most close sheet of its weighting border and the most close each conversion coefficient than the transformation series manifold border of elder generation do not have the image of boundary artefacts thereby can regenerate from conversion coefficient.

The preferably asymmetric boundary filter of at least some transformed filters extends first length to the border of each sheet, to extending second long length away from the direction on sheet border, but is no more than the border of sheet.

In a preferred embodiment, the inner transformation wave filter comprises a center-filter, is used for producing near the center of processed data array or center 2-4 high pass and 2-4 low-pass coefficients.This center-filter is as filter switch.Use two kinds of multi-form inside wave filters in the side that this center-filter is different.For example, in a side of center-filter, the center of inner wave filter may be positioned at the even data position, then may be positioned at the odd data position at opposite side.

Image processing system and method can also comprise image reconstruction circuit or program, are used for subsequently to image file application data decompression method and inverse transformation the reconstructed image that is adapted at showing on the scanner back with generation.

In a second aspect of the present invention, the conversion coefficient collection is corresponding to the spatial frequency sub-band of image.These sub-bands are according to the transform layer grouping that produces them.For one or more corresponding sub-band groups, produce one or more parameters of each image sheet, the closeness of characteristics of image in this sheet of its value representation.Each image sheet is included into a class in one group of predetermined class by the value according to these one or more parameters.According to the classification of sheet, select one group of quantization factor of this sheet, use the conversion coefficient scaling transformation of selected quantization factor then, to produce a quantization transform coefficient collection of this sheet with this sheet.

In a third aspect of the present invention, quantized transform coefficients is encoded.When the coefficient of every group of spatial frequency sub-band of coding, the most important set of bitplanes of these coefficients is stored in first bit stream, and least important set of bitplanes is stored in second bit stream.From another viewpoint, the code coefficient part (being used for one group of sub-band) that its value surpasses predetermined threshold is stored in first bit stream, and remaining code coefficient partly is stored in second bit stream.When according to the specified resolution level during, only decoded and be used for this image of reconstruct corresponding to the bit stream of this specified resolution level from the image file reconstructed image.For some stage resolution ratios, no one or more bit streams will comprise least part and parcel (that is, bit plane) of sub-band, and this sub-band is included in the bit stream that is used at this stage resolution ratio reconstructed image than part and parcel.

The accompanying drawing summary

By following detailed description of being done in conjunction with the accompanying drawings and claims, other purpose of the present invention and feature will be clearer.In the accompanying drawing:

Fig. 1 is the block diagram of Distributed Computer System, comprises a webserver and a plurality of client computer, is used for multi-resolution image is distributed to client computer;

Fig. 2 is the block diagram of computer system according to an embodiment of the invention;

Fig. 3 A simplifies to illustrate and original image is transformed to the changing image array and with the process of this changing image array boil down to compressed image file; Fig. 3 B illustrates the mapping of spatial alternation sub-band to the NQS sub-band, is used for the transcoding, coding transform coefficient;

Fig. 4 is a representation of concept of representing the coded data of an image, is organized as the multi-resolution representation (that is, according to multiple stage resolution ratio) that helps image;

Fig. 5 A, 5B, 5C, 5D and 5E illustrate the image store data structure;

Fig. 6 is the high level flow chart that can use image processing process of the present invention;

Fig. 7 A, 7B and 7C illustrate forward and reverse class wavelet data conversion process with figure;

Fig. 8 illustrates by array of image data is used the spatial frequency sub-band that multilayer is decomposed the wavelet coefficient that small echo or wavelet-like transform produced;

Fig. 9 illustrates the process flow diagram of the block sort method of the quantization factor that is used to select an image block;

Figure 10 A and 10B illustrate the process flow diagram of program of the conversion coefficient of the image block that is used to encode;

Figure 11 A, 11B and 11C illustrate the coding method that is called maximum bit-depth (MaxbitDepth) value in a preferred embodiment, and it is illustrated in the desired figure place of transcoding, coding transform coefficient in each piece of coded image and the sub-piece;

Figure 12 is the high level flow chart that can use compressed image restructuring procedure of the present invention;

Figure 13 A and 13B illustrate the conversion coefficient that is used for decoded picture and are used for from the process flow diagram of the program of these coefficient reconstructed images;

Figure 14 is the block diagram of a digital camera, has wherein realized one or more aspect of the present invention;

Figure 15 is a conceptual flow chart, and the expression client computer is downloaded a little image, then image is amplified, and forwards the new part of image then to.

Preferred embodiment

In the presents, term " small echo " and " class small echo " can exchange use.Be similar to the spatial frequency feature of traditional wavelet transformation on the spatial frequency features, in general of wavelet-like transform, and inverse transformation nondestructively, but wave filter is shorter, and its counting yield is better.

The present invention can realize in handling the plurality of devices of image, comprises from high-end workstation and server also can realizing in specific specialized equipment, as digital camera to the various computing systems of low side client computer.

Be used to encode and the system of the multi-resolution image that distributes

Fig. 1 illustrates a Distributed Computer System, comprise a webserver 140 and a plurality of client computer 120, be used for by such as the global communication network 110 of the Internet or any other suitable communication network such as LAN (Local Area Network) or intranet image 190 to client computer distribution multiresolution.The multi-resolution image file that picture coding workstation1 50 is prepared by webserver distribution.In certain embodiments, the picture coding task that the webserver 140 also can carries out image coding work station 150.

Typical customer equipment 120 should be personal digital assistant, personal computer, workstation or the computer-controlled equipment that is exclusively used in particular task.Network interface or other communication interface 128 that customer equipment 120 preferably includes CPU (central processing unit) 122, storer 124 (comprising high-speed random access memory and nonvolatile memory such as magnetic disk memory) and is used for by communication network 110 customer equipment being connected to the webserver.Storer 124 typically should storage operating system 132, browser application or other application 134 with the aid of pictures, picture decoding module 180 and the multi-resolution image file 190 of coding according to the present invention.In a preferred embodiment, browser application 134 comprises or is coupled to a Java ^TM(trade mark of Sun Microsystem company) virtual machine be used to carry out the Java language program, and the picture decoding module is embodied as Java ^TMProgram, it arrives customer equipment with image file 190 dynamic download, thereby browser can be used to watch by the decoded picture file.

Network interface or other communication interface 148 that the webserver 140 preferably includes CPU (central processing unit) 142, storer 144 (comprising high-speed random access memory and nonvolatile memory such as magnetic disk memory) and is used for by communication network 110 webserver being connected to customer equipment and picture coding workstation1 50.Storer 144 typically should be stored http (HTML (Hypertext Markup Language)) server module 146, is used to respond the http request, comprises the request of multi-resolution image file 190.The webserver 140 can also select to comprise the image processing module 168 that has coded program 172, and being used for picture coding is multi-resolution image.

Computer system

With reference to figure 2, the general-purpose computing system that Flame Image Process workstation1 50 can service routineization realizes.When webserver carries out image processing task, this figure can also represent the webserver.Computer system 150 can comprise:

One or more data processing units (CPU) 152;

Storer 154, it typically comprises high-speed random access memory and nonvolatile memory;

User interface 156 comprises display device 157, as CRT or LCD escope;

Network or other communication interface 158 are used for and other computing machine and miscellaneous equipment communication;

FPDP 160 is used for for example receiving image and sending image (such image transfer also can be finished by network interface 158 certainly) to digital camera from digital camera; With

One or more communication buses 161 are used for CPU 152, storer 154, user interface 156, network interface 158 and FPDP 160 are connected to each other.

Storer 154 stored programmes and the data of this computer system typically comprise:

Operating system 162 is used to the system service that provides basic;

File system 164, it can be the part of operating system;

Application program 166, as be used for watching user class program with the application drawing picture;

Image processing module 168 is used to carry out various image processing functions, comprises those functions as theme of the present invention;

Image file 190 is represented various images; And

Intermediate images data array 192 is used for the intermediate result that produces in Flame Image Process and image regeneration process.

Image processing module 168 can comprise an image coding module 170 and picture decoding module 180.Image coding module 170 produces multi-resolution image file 190, and its details is discussed below.Image coding module 170 can comprise:

Coding control program 172, the process of its control compression and coded image (with 189 beginnings of original image array, this array can obtain by the image of the another kind of image file format of decoding);

One category wavelet transformation program 174 is used for the class wavelet filter is applied to represent the view data of an image;

Piece sorting process 176 is used to determine to be applied to the quantization factor of each piece (or wave band) of the conversion coefficient of image;

Quantification program 178 is used to quantize the conversion coefficient of an image; And

Sparse data coded program 179 is also referred to as the entropy coding program, is used to the quantization transform coefficient of encoding and being produced by quantification program 178.

The image of the storage area conversion in one group of ephemeral data array 192 of the program in the image processing module 168 and other ephemeral data.

Picture decoding module 180 can comprise:

Decoding control program 182 is used for the process of an image file of control decoding (or part of image file) and regeneration by the represented image of the data of image file;

Sparse data decoding program 184, the quantization transform coefficient through coding that is used for being stored in image file is decoded as corresponding quantitative conversion coefficient array;

Go quantification program 186, be used to one group of conversion coefficient of a sheet of quantization means image; With

One category inverse wavelet transform program 188, a group an of sheet that is used for class small echo inverse filter is applied to presentation video goes quantized transform coefficients, with this picture of regenerating.

Image capturing and processing general introduction

With reference to figure 3, the raw image data 200 that obtains from the image capturing mechanism (Figure 14) of digital camera or from image analyzer or miscellaneous equipment is by " to the view data burst " and processed.More specifically, raw image data is used as the ARRAY PROCESSING of sheet 202, and each sheet has pre-sizing, as 32 * 32 or 64 * 64 (i.e. 64 row, 64 row).In other embodiments, can use other sheet size, as 32 * 32 or 16 * 32 or 128 * 128 or 64 * 128.Sheet is the view data non-overlapping portions.With abundant sheet to cover pending whole original image, even some sheets stretch out the edge of original image.The extension of sheet copy with the data boundary value in the wavelet transformation process is filled, and perhaps fills with invalid data.The position of sheet is determined with respect to the initial point in the upper left corner of image, the Y position of first expression sheet (or the pixel in the sheet or coefficient) of coordinate, the X position of second expression sheet (or the pixel in the sheet or coefficient).Therefore, the sheet of position 0,128 is positioned at the top of image, and its initial point is positioned at the 128th pixel place of lastrow pixel.

Small echo or the conversion of class wavelet decomposition are applied successively to each sheet of image, and the raw image data in the sheet is converted to the transformation series manifold.When wavelet-like transform is when being applied to the one-dimensional transform of two-dimensional array of view data, this conversion at first in one direction (as, horizontal direction) is applied to view data, to produce the middle coefficient collection, then this conversion on other direction (as, vertical direction) is applied to this middle coefficient collection, to produce final coefficient set.Final coefficient set is the result who the conversion of class wavelet decomposition all is applied in the horizontal and vertical directions view data.

Sheet is to handle according to predetermined raster scan order.For example, the sheet in the top row be from an end (as, left end) to the other end (as, right-hand member) handle, handle back to back next line sheet then, also processed up to the sheet of the bottom line of raw image data.

The conversion coefficient of each sheet produces by the continuous application wavelet-like transform.The original two-dimensional array of raw image data is at first used the wavelet decomposition conversion produce four groups of coefficients, be expressed as LL, HL1, LH1 and HH1.Each of wavelet decomposition conversion subsequently used the LL that only is applied to be produced by the back wavelet transformation and organized coefficient, and produces four groups of new coefficients, is expressed as LL, HLx, LHx and HHx, and wherein x represents wavelet transformation " layer " or iteration.After last wavelet decomposition conversion iteration, only surplus next LL group.The coefficient sum that produces equals the data sample number in the raw data array.By each conversion iteration produce not on the same group coefficient be sometimes referred to as " layer ".Wavelet transformation number of plies that image produced is the function of initial pictures resolution normally.For the sheet of 64 * 64 or 32 * 32 sizes, 5 wavelet transformation layers of general execution produce 16 spatial frequency sub-band data: LL ₅, HL ₅, LH ₅, HH ₅, HL ₄, LH ₄, HH ₄, HL ₃, LH ₃, HH ₃, HL ₂, LH ₂, HH ₂, HL ₁, LH ₁, HH ₁The conversion number of plies between different the realization may be different, depend on the size of used sheet and available amount of computational resources.For bigger sheet, may use additional transform layer, thereby produce additional data sub-band.The conversion number of plies of carrying out is many more, will produce good more data compression usually, and its cost is the computing time that increases, but also may produce the sheet edge illusion of increase.

The spatial frequency sub-band is by following grouping.Sub-band group 0 is corresponding to LL _NSub-band, wherein N represents to act on the conversion number of plies of image (or image sheet).Each other sub-band group i comprises three sub-band: LH _i, HL _iAnd HH _iBelow will illustrate, when the conversion coefficient of a sheet of coding, separate coding from the coefficient of every group of sub-band and other coefficient of organizing sub-band.In a preferred embodiment, produce a pair of bit stream, to represent the coefficient in every group of sub-band.A bit stream is represented the most important bit plane of the coefficient in this group sub-band, and another bit stream represent this group sub-band coefficient remaining, least important bit plane.

The wavelet coefficient that is produced by the application class wavelet transformation preferably coefficient (by quantizer 178) in each sub-band of the sheet by removing conversion with corresponding quantization value (being also referred to as quantization factor) quantizes.In a preferred embodiment, specify an independently quantization factor for each sub-band.More specifically, as described below, block classifier 176 produces one or more values, represents the feature closeness in each image sheet, and according to these one or more values, selects a quantization factor table, is used for quantizing the coefficient of the different sub-bands of this sheet.

Encoded by sparse data scrambler 179 by the quantization parameter that quantizer 178 produces, to produce a group coding subimage son file 210 of each image sheet.

Wavelet-like transform used in the preferred embodiment is discussed in more detail below.Be used to carry out the circuit and the U.S. Patent No. 5 of the wavelet-like transform of the preferred embodiment, 909, wavelet transformation and data-measuring method that 518 " System andMethod for Performing Wavelet and Inverse Wavelet LikeTransformation of Digital Data Using Only Add and Bit ShiftArithmetic Operation " (be used for only using adding with shifting algorithm and operate the small echo of combine digital data and the system and method for reverse wavelet-like transform) describe are closely similar, and this patent is hereby incorporated by reference.

The sparse data coding method of preferred embodiment is called nested secondary split (NQS), is discussed in more detail below.This sparse data coding method is a U.S. Patent No. 5,949, the improvement version of the NQS sparse data coding method that 911 " Systemand Method for Scalable Coding of Sparse Data Sets " (system and methods that are used for the scalable coding of sparse data collection) are described, this patent is hereby incorporated by reference.

Fig. 3 B illustrates the mapping from the spatial frequency sub-band to the NQS sub-band that is used for the transcoding, coding transform coefficient.Especially, in a preferred embodiment, seven spatial frequency sub-band (LL ₅, HL ₅, LH ₅, HH ₅, HL ₄, LH ₄And HH ₄) be mapped to single NQS sub-band (sub-band 0), with the coefficient in these sub-bands of encoding.In other words, the coefficient in these seven spatial frequency sub-bands is handled as single top layer piece, to carry out the NQS coding.In a preferred embodiment,

NQS sub-band

0,1,2 and 3 is as four top layer NQS block encodings, and its most important bit plane is stored in the bit stream of the lowest resolution level of representing described image.

Image resolution ratio level and subimage

Store according to multiple stage resolution ratio 0-N with reference to 4, one images of figure, the stage resolution ratio that is adjacent of each stage resolution ratio differs factor 4 usually.In other words, if the quantity of information that the highest resolution representation of image (stage resolution ratio N) comprises is X, then second high resolving power represents that the quantity of information that method N-1 comprises is X/4, and the 3rd high resolving power represents that the quantity of information that method comprises is X/16.The resolution progression of storing in the image file will depend on the size of highest resolution representation of image and the minimum resolution that the thumbnail image can be accepted in the lowest resolution level.For example, if complete or highest resolution image is the high-resolution picture with 16 mega pixels (as image of 4096 * 4096 pixels), then 7 stage resolution ratios should be suitable: 4096 * 4096,2048 * 2048,1024 * 1024,512 * 512,256 * 256,128 * 128,64 * 64.

But as shown in Figure 4, a feature of the present invention or aspect are when multi-resolution image has more than 3 or 4 stage resolution ratios, and this image is encoded and is stored in a plurality of " primary image " file, and each file comprises the data of 2-4 stage resolution ratio.Alternatively, all primary images can be stored in the single file, and each base image is stored in this image file interior different base image son files or son file data structure.

Each base image file (or son file) comprises reconstruct " base image " and the required data of 1 to 3 number of sub images (lower-resolution stages).For example, in example shown in Figure 4, image is stored in three files, the image of three stage resolution ratios of first file storage, comprise highest resolution and two lower resolution, the image of second other three stage resolution ratio of file storage (fourth, fifth and six high resolving power levels), the image of two lowest resolution levels of the 3rd file storage, one has 8 stage resolution ratios.Usually, each follow-up file is approximately 2 for a short time than next bigger file ^2XThe factor, wherein X is the resolution progression in the big file.For example, if first file has three stage resolution ratios, then next file is usually than the little factor 64 (2 of this document ⁶).

As a result, represent that the image file of one group of lower-resolution stages will be more much smaller than the image file that comprises the full resolution image data, and therefore can be transferred to client computer quickly.For example, the user of client computer can check one group of little image with lowest resolution level (as 32 * 32 or 64 * 64) earlier, require client computer only to check three minimum image files, it will typically comprise about 0.024% data of highest resolution image file.When user request when high-resolution is watched image, client computer can receive second bigger image file, comprises the data of 64 times of lowest resolution image files.This second file may comprise three stage resolution ratios (as, 512 * 512,256 * 256,128 * 128), this may be enough concerning the user.When the user needs more high resolving power, will send the highest resolution file.According to the environment of this system of use, the supplier of image can collect additional expense and allow to download more high-resolution image file.

Should be noted that many image files are not squares, but rectangle, and the square-shaped image size of using in the above-mentioned example should not thought limitation of the scope of the invention.Although the elementary cell of the information of being handled by image processing module is a sheet, 64 * 64 or 32 * 32 pel array normally, any specific image can comprise the array of any size of such sheet.In addition, image is unnecessary to be the even-multiple of sheet size, because no matter whether suitable, edge piece all will be clipped.

The image of specified resolution level is appointed as " thumbnail " image can depends on the customer equipment that image sends to.For example, the thumbnail of issuing personal digital assistant with small displays very or mobile phone can be more much smaller (for example than the thumbnail of issuing personal computer, 1/16th), issuing the thumbnail with big high-resolution screen can be more much bigger than the thumbnail of issuing the personal computer with common size and sharpness.When image is used for different customer equipment potentially, produce additional primary image, make every kind of equipment can both at first receive the thumbnail image of suitable size.

When image during at first by client device requests, this customer equipment can its to the request of thumbnail image in its window size of explanation, perhaps server can judge that customer equipment watch the size of window by inquiry customer equipment before downloading the thumbnail image to customer equipment.As a result, every kind of customer equipment receives the minimum resolution thumbnail that is fit to this equipment.

The image file data structure

With reference to figure 5A-5E, after whole sheets of image all were transformed, compress and encode, the coded image data of generation was stored as image file 190.Image file 190 comprises title data 194 and a basic image data structure sequence, is sometimes referred to as primary image son file 196.Each primary image son file 196 generally includes the data that are used at two or more stage resolution ratio display images.In addition, each primary image is supported different stage resolution ratio scopes.A plurality of primary images and their subimages separately provide the gamut stage resolution ratio of image together, as shown in Figure 4.Although the stage resolution ratio phase non-overlapping copies of supporting by primary image in a preferred embodiment, but in optional embodiment, may be overlapping by the stage resolution ratio that a primary image file is supported with the stage resolution ratio of supporting by (same initial full resolution image) another primary image file.

In a preferred embodiment, each image file 190 is webpages of a html file or similar form, covers small routine 199 (as Java ^TMSmall routine) link 198, as object tag or small routine label, when this document downloaded to client computer, small routine 199 was called automatically.The small routine 199 that a title 194 and a selected primary image 196 embed as input, it shows to picture decoding and on the display of user's personal digital assistant or computing machine.The operation of small routine is transparent to the user, and the user only sees the image that shows on its graphoscope.Alternatively, this small routine can provide an options menu to the user, comprise the image son file that comprises in the image file obtainable stage resolution ratio, additional primary image son file and other option that can obtain from server, as the image cut option.

In an optional embodiment, client workstation comprises an application, uses as inserting, and is used for file layout decoding of the present invention and display image.In addition, each image file 210 has the related data type of using corresponding to this insertion.Image file 210 is downloaded with the webpage of html (HTML) or similar form, and this webpage comprises embedded tags or the object tag of pointing to this image file.As a result, when webpage was downloaded to client workstation, this insertion was used and is called and carry out by client computer automatically.As a result, image file is with regard to decoded and demonstration, and the operation of inserting application is to user transparent.

Image file 190-A shown in Fig. 5 A represents to store a kind of possible mode of multi-resolution image, is particularly suitable for storing on server multi-resolution image.In client computer, the image file 190-B shown in Fig. 5 B can only comprise a primary image 196.In addition, the client version of image file 190 can comprise the link 201 of pointing to the image file 190-A on the server.Link 201 is used to make the user of client computer can download other primary image (other stage resolution ratio) of same image.Alternatively, link 201 is Java ^TM(trade mark of Sun Microsystem) script is used for comprising from web server requests the image file of any high-resolution primary image.Will pay if obtain the image file of high-resolution, then this script is with the invoking server program, to obtain request user's expense.

In another optional embodiment, multi-resolution image can be stored as one group of independently primary image file 190-B on server, and each file has the form shown in Fig. 5 B.The benefit of making like this provides needn't revise the image file 190-B that just can download to client computer.

With reference to figure 5A, the title 194 of image file comprises the information that the different primary image son file of visit 196 is required.Especially, in a preferred embodiment, title 194 storages:

The identifier of the image file in the server or URL;

The parameter value of the primary image Ziwen number of packages (in the embodiment of each primary image file storage in a unique file, being the primary image number of files perhaps) in expression this document;

The size of each basic image data structure; With

Point to the offset pointer (in the embodiment of each primary image file storage in a unique file, being the pointer that points to each primary image file perhaps) of each basic image data structure.

Each primary image son file 196 has the sequence of a title 204 and a bit stream 206.These bit streams are expressed as 1a, 1b, until N, wherein N is the resolution progression that described primary image is supported.The meaning of label " 1a " etc. is in following explanation.Information in each bit stream 206 is discussed in more detail below.The title data 204 of each primary image son file comprises the territory of representing following meaning:

The size of primary image son file (that is the storage space that occupies by the primary image son file);

Be used for the size of the sheet of primary image burst (as, the number of lines and columns of pixel), wherein each sheet is transformed respectively and encodes, and is as described below;

Color Channel component for these primary image son file storages;

Be used to decompose primary image transformed filter (as, transformed filter on the same group can not be used for different images);

Spatial frequency wavelet hop count (that is, every of primary image) for this primary image coding;

Count by the stage resolution ratio (being also referred to as subimage) that primary image is supported;

Be primary image bitstream encoded number (that is, every of primary image); With

The information of each bit stream.

The information of each bit stream in the primary image son file can comprise:

Point to bit stream, to indicate the offset pointer of its position of (or in primary image son file) in image file;

The size of bit stream (how many data are arranged in the bit stream);

The scope of the spatial frequency sub-band that comprises in the bit stream;

Color Channel number in the bit stream;

The scope of the bit plane that comprises in the bit stream, how the bit plane of the coefficient in its expression sub-band is divided into important, inessential and possible medium pith; With

Point to the offset pointer table of the sheet 208 in the bit stream.

Each bit stream 206 comprises the sequence of a sheet subarray 208, and each sheet subarray comprises i bit stream of the relevant sheet of image.Bit stream 206 also comprises title 209 alternatively, has to be used to ignore by the territory of primary image title 204 for the parameter of primary image formulation.When image file comprised clip image, the group of the sheet subarray 208 that comprises in the image file is limited to those need represent this clip image.

In a preferred embodiment, image file title 194 also comprises the parameter on expression " clip image border ".This helps only to comprise the local copies of image file of data of the cutting out section of image, and is very useful when client computer is used for dwindling of carries out image or amplifieroperation.For example, the user may only ask the sub-fraction of entire image, but resolution is very high.In this case, have only the sheet of the required image of the cutting out section of display image will be included in the image file of the client computer that sends to the user, the clip image boundary information is used for passing on this information to the program that shows this image on client computer.Two class image cut information are provided by image file title 194: be applied to the shearing of entire image file and be applied to any further shearing of concrete subimage.For example, when client computer at first received image, it may receive only the lowest resolution subimage of specific primary image, and this subimage generally is not sheared (comparing with full images).When client computer during with specific high-resolution enlarged image a part of, the required data slice of the image section that has only generation to watch on client computer will be sent to client computer, thereby new shear parameters will be added on the title of the image file of storage (or buffer memory) in the client computer, instruct according to the image amplification of client computer with indication to download to the subimage level of client computer or the shearing border of subimage.

The table of the offset pointer of the sheet that comprises in the primary image title of each bit stream of sensing primary image is also amplifying and is dwindling in the process and use.Especially, with reference to Figure 15, when image file during for the first time by client computer or device downloads (240), higher bit stream may vacancy, thereby the offset pointer table will initially comprise invalid value.When user's enlarged image of customer equipment, if desired, various data of more senior bit stream are downloaded to customer equipment (242), and the offset pointer table that points to sheet upgrades, and are downloaded to the sheet of client computer to reflect its data.When client computer during further with that amplify or higher stage resolution ratio full views watching image, if desired, the information of accessory plate is sent to client computer, shearing information in the image file title 194 and the offset information in the primary image title are updated once more, with the sheet of the data that are reflected as the storage of each bit stream.

With reference to figure 5A-5E, the feasible any part of retrieving files fast of information in image file and the primary image son file title, this makes that computing machine or miscellaneous equipment can be in the beginning or the endings of any part of stage resolution ratio positioning image arbitrarily, and any other parts content that needn't decoded picture file 190.This is at intercepting image file 190, to produce than the file of low image quality version or the file of clip image version, for example is used for by communication network when another computing machine or equipment send, and is very useful.

Hereinafter, term " subimage " and " difference subspace image " will use with respect to bit stream 206.Generally, any subimage of primary image will comprise from bit stream 1a to last concrete bit stream such as whole bit streams of bit stream 3.The continuous bit stream of this group constitutes with the required data of specified resolution level reconstructed image, is called subimage herein." difference subspace image " comprises image resolution ratio brought up to the required added bit of next subimage level stream from a number of sub images level.For example, bit stream 1c, 2b and 3 can be called a difference subspace image together, because these bit streams comprise the required data of double resolution of the subimage that will produce from bit stream 1a-2a.

With reference to figure 5C, the coded data 190-C of expression primary image is at first by " sheet order " storage.Image file 190-C comprises title 222 and one group of sheet son file 220.With reference to figure 5D, every son file 220 comprises title 224, and expression be used to the to encode quantization table of this sheet also comprises the offset pointer and the out of Memory that point to the bit stream in the son file.The sheet son file 220 of each sheet also comprises one group of bit stream subarray 226.Every bit stream subarray 226 comprises coded data, represents the most important bit plane of relevant group of NQS sub-band (see figure 3) of this sheet, least important bit plane or medium bit plane.Express the example of bit plane down to the mapping of bit stream subarray:

NQS wavelet segment number resolution	0-3	4，5，6	7，8，9
NQS wavelet segment number resolution	0-3	4，5，6	7，8，9	16×16	S
32×32	S+MS	S		16×16	S
32×32	S+MS	S		64×64	S+MS+IS	S+IS	All

In this table, all different in each NQS sub-band corresponding to the bit plane of S, MS and IS.These bit plane scopes illustrate in the title of primary image son file.For example, for NQS sub-band 0-3, S may be corresponding to bit plane 16-7, and MS may be corresponding to bit plane 6-4, and IS may be corresponding to bit plane 3-0; And for NQS sub-band 4-6, S may be corresponding to bit plane 16-5, and IS may be corresponding to bit plane 4-0.

Bit stream 1a, 1b and 1c comprise the coded data of most important, the medium important and least important bit plane of representing

NQS sub-band

0,1,2 and 3 respectively.Bit stream 2a and 2b comprise the coded data of the most important and least important bit plane of representing

NQS sub-band

4,5 and 6 respectively, and it is corresponding to LH ₂, HL ₂And HH ₂ Sub-band.Bit stream 3 comprises expression and corresponds respectively to LH ₁, HL ₁And HH ₁The

NQS sub-band

7,8 of sub-band and 9 the whole bit planes of coded data.

Sheet son file 220 can be considered to " temporarily " file, because the sheet data of coding are reassembled as the file layout shown in Fig. 5 A from the file layout shown in Fig. 5 C and the 5D subsequently.

Fig. 5 E illustrates an object lesson of primary image son file 196, is expressed as 196A.This primary image son file comprises 12 bit streams 206, is used to produce primary image and two low resolution subimages.Primary image utilizes five layers of wavelet transformation to carry out conversion, produces 16 spatial frequency sub-band data, and these data have been encoded and have been organized as three number of sub images, comprise primary image.The subimage number is arbitrarily to a certain extent, because the sub-band that is produced by 5 transform layers can be used for producing nearly 6 number of sub images.But using this primary image son file to produce very little subimage is not very efficient in storage space aspect utilizing, and therefore, preferably utilizes less primary image son file to produce less subimage usually.

Among Fig. 5 E, primary image is handled with 5 transform layers, but the data that produce just are organized as 3 number of sub images levels, rather than 6.In fact, with sub-band LL ₂The last three layers of conversion that are converted to 10 sub-bands (LL5, LH5, HL5, HH5, LH4, HL4, HH4, LH3, HL3, HH3) are not to be used to produce extra subimage level, and just are used to produce better data compression.

Shown in Fig. 5 E, when 5 transform layers of view data were mapped to 3 number of sub images, bitstream data array 206 was as follows to the mapping of subimage:

Subimage 0, the lowermost level subimage, corresponding to bit stream subarray 206-1a, it comprises the most important bit plane (seeing Fig. 3 B) of NQS sub-band 0-3;

Subimage 1 is corresponding to bit stream 206-1a, 206-1b and 206-2a; With

Subimage 2, primary image is corresponding to the whole bit streams 206 in the primary image son file.

During more subimage (subimage level), the first subimage 206-1a will comprise less spatial frequency sub-band in transform layer is mapped to than example shown in Fig. 5 E.

A kind of sparse data coding techniques conversion coefficient of every group of sub-band of every that is used to encode makes and only just can represent that with data seldom major part comprises the data array of null value.Usually, the null value that the upper frequency of the quantized image data of conversion part (that is, sub-band) comprises is more than nonzero value, and the absolute value of most of nonzero value is less.Therefore, many higher level bit plane will comprise nonzero value seldom.

The small wave converting method of burst

With reference to figure 6, when an image was caught by image capture device, the process that produces image file began (step 250).If the image variable size is then judged the line number and the columns (step 252) of the sheet that the size of the image caught and overlay image data are required.If the image constant magnitude, then step 252 does not need.

Then, by in the horizontal direction with vertical direction on to each sheet application class wavelet decomposition conversion in the image, all sheets are handled by predefined procedure, for example press raster scan order, then the conversion coefficient that produces is quantized, use sparse data compression and coded program at last quantized transform coefficients encode (step 254).The coded data of each sheet is stored in temporary file or the son file, for example presses the form shown in Fig. 5 D.

After the whole sheets in the image were all processed, the multi-resolution image file that comprises all coded slice was stored in (step 256) in the nonvolatile memory.More specifically, the coded slice data from temporary file are written in the output bit flow file according to form shown in resolution opposite order and Fig. 5 A." resolution opposite order " means when image file is stored hereof that the lowest resolution bit stream is storage earlier, is time lowest resolution bit stream then, and the rest may be inferred.

The class wavelet decomposition that is used for step 254 is described in more detail with reference to figure 7A, 7B and 7C below.Quantification and sparse data coding step also are discussed in more detail below.

Initial pictures is processed, encode and be stored as the multi-resolution image file after, usually comprise 2-4 stage resolution ratio, if an above primary image will be included in (257) in the image file, original image is by down-sampling and anti-distortion (anti-aliased), to produce new primary image (258), all little factor 2 of its each dimension ^X, wherein X is the subimage progression in the previous multi-resolution image file that produces.Like this, new primary image will be than subimage minimum, lowest resolution of primary image a little factor 4.Then according to new primary image being handled, to produce additional but much smaller coding multiresolution primary image is added on the image file with the same mode of previous primary image.If initial primary image has sufficiently high resolution, can take turns down-sampling and anti-distortion the 3rd primary image that forms by carrying out second, the 3rd coding multiresolution primary image file can be stored in the image file.Last coding primary image may comprise less subimage level than other primary image, in certain embodiments, may only comprise a stage resolution ratio, and in this case, in fact image file is exactly a thumbnail image file.

In an optional embodiment, each coding primary image is stored in independently in the image file, and these image files interlink by being stored in the information in the image file title or linking by html (or class html).

In a preferred embodiment, following employing wave filter is an one dimension FIR wave filter, at first is applied to the row of image, is applied to row then, or opposite.For example, if image will carry out down-sampling (is to reduce the factor 16 for resolution) with the factor 4 on each dimension, then this FIR wave filter can have following filter coefficient:

Wave filter A=(3-3-4-4 10 10 29 29 29 29 10 10-4-4-3-3) 1/128.

These example embodiment once are applied to one group of 14 sample, to produce a down-sampled values, and 4 samples that are shifted then, and then use.Repeat this process, up to producing L/4 down-sampled values, wherein L is initial sample number (that is a pixel value).At the edge of array of image data, mirror image data is used to extend beyond the filter coefficient at view data edge.For example, on the left side of array (or top margin), preceding 6 coefficients are applied to the mirror image data value, and 4 " 29/128 " coefficients are applied to preceding 4 pixels in the filtered row (or row), and last 6 coefficients are applied to following 6 pixels in this row (or row).

If, then use above-mentioned wave filter and come then, to use second wave filter and come with another factor 2 further down-sampled images data with factor 4 down-samplings with image of factor 8 down-samplings.In a preferred embodiment, this second wave filter is the FIR wave filter, has following filter coefficient:

Wave filter B=(3-4 10 29 29 10-4-3) 1/64.

Alternatively, can use longer wave filter to realize by wave filter factor 8 down-samplings.

Downsampling filter described above has following feature: they are low-pass filters, and cutoff frequency lays respectively at 1/4th and half place of Nyquist (Nyquist) frequency; Each filter coefficient is defined by a simple fraction, and wherein, molecule is an integer, and denominator is 2 a positive integer doubly (that is, 2 ^NThe number of form, wherein N is a positive integer).The result of these filter characteristic makes can carry out down-sampling very efficiently, protects the spatial frequency feature of image simultaneously, avoids distortion effect.

Although the downsampling filter filter applies can influence the concrete down-sampling pixel value that produces in the order (that is, Row Column or opposite) of array of image data, and is little to the influence of pixel value.In other embodiments of the invention, can use other downsampling filter.

Use the class wavelet decomposition of edge, inside and central transformation wave filter

Fig. 7 A-7C simply illustrates set of diagrams as data X ₀-X _2n-1Carry out the class wavelet decomposition to produce one group of coefficient L ₀-L _N-1And H ₀-H _N-1Process, the low spatial frequency component of L coefficient presentation video data wherein, and the high spatial frequency component of H coefficient presentation video data.

In a preferred embodiment, applied wavelet-like transform is actually two wave filters.First wave filter T1 is called boundary filter, is used for producing preceding two and latter two coefficient of the conversion coefficient row or column that is produced.Second wave filter T2 is called inner wave filter, is used for producing all other coefficients of the conversion coefficient row or column that is produced.Boundary filter T1 is short wave filter, be used for the data of conversion sheet or block edge, and inner wave filter T2 is long wave filter, is used for the data of conversion away from sheet or block edge.Boundary filter and inner wave filter are all without the data of sheet or piece outside.As a result, compare with prior art systems, it is less that wavelet-like transform of the present invention is applied to the desired working storage of array of image data.Equally, compare, be used to realize that the complicacy of the circuit of wavelet-like transform of the present invention and/or software is also lower with prior art systems.

In a preferred embodiment, boundary filter comprises first very short wave filter (its " support " cover 2-4 data value), is used to produce at first and last coefficient, also comprises second wave filter, is used to produce second and second and arrives best coefficient.The wave filter support of second boundary filter extends beyond 3-6 data value, and is therefore longer than first boundary filter, but shorter than inner wave filter T2.The inside wave filter that produces other coefficient has the wave filter support of 7 above data values.Boundary filter especially for producing at first and first boundary filter of last high spatial frequency coefficient value is designed to minimize the edge illusion, and does not use any data in adjacent sheet or the piece.In other words, boundary filter of the present invention is designed to guarantee the accurate reconstruct of the rim value of processed data array, and it can minimize the edge illusion again when the image that regeneration is shown by this tabulation of these data.

In a preferred embodiment, the class wavelet decomposition conversion that is applied to data array comprises the 1st layer of wavelet-like transform, and its wavelet-like transform that uses when carrying out the conversion of 2-N layer is different.Especially, the 1st layer of wavelet-like transform uses short wave filter, and be shorter than the wave filter support of the wave filter that is used for the 2-N layer.One of the 1st layer of reason of using different wavelet-like transforms (that is one group of transformed filter) is by using short wave filter to minimize boundary artefacts to the 1st layer.The Another reason that the 1st layer of use is different from the wavelet-like transform (that is one group of transformed filter) of other layer is the round-off error that minimizes owing to adding that a large amount of standard values are introduced.Round-off error takes place when mainly filtering raw image data in the 1st layer of conversion process, causes sometimes from the picture quality of coded image data regeneration obviously to descend.

List the formula of the wavelet-like transform that is used for preferred embodiment below:

The 1st layer of positive sense-class wavelet transformation:

T1 and T2 positive-going transition (low frequency):

Y _k＝X _2k-X _2k-1 k＝0，1，...，n-1

L_{k} = X_{2 k - 1} + [\frac{Y_{k + 1}}{2}] = \frac{X_{2 k} + X_{2 k + 1} + 1}{2} k = 0,1, . . ., n - 1

T1 positive-going transition (boundary filter-high frequency):

H_{0} = Y_{0} + [\frac{- L_{0} + L_{1} + 1}{2}]

H_{1} = Y_{1} + [\frac{- L_{0} + L_{2} + 2}{4}]

H_{n - 2} = Y_{n - 2} + [\frac{- L_{n - 3} + L_{n - 1} + 2}{4}]

H_{n - 1} = Y_{n - 1} + [\frac{- L_{n - 2} + L_{n - 1} + 1}{2}]

T2 positive-going transition (inner wave filter-high frequency):

H_{k} = Y_{k} + [\frac{3 L_{k - 2} - 22 L_{k - 1} + 22 L_{k + 1} - 3 L_{k + 2} + 32}{64}] k = 2, . . ., n - 3

The 1st layer of reverse wavelet-like transform

T1 reciprocal transformation (boundary filter-high frequency):

Y_{0} {= H}_{0} + [\frac{- L_{0} + L_{1} + 1}{2}]

Y_{1} {= H}_{1} + [\frac{- L_{0} + L_{2} + 2}{4}]

Y_{n - 2} = H_{n - 2} - [\frac{- L_{n - 3} + L_{n - 1} + 2}{4}]

Y_{n - 1} = H_{n - 1} - [\frac{- L_{n - 2} + L_{n - 1} + 1}{2}]

T2 reciprocal transformation (inner wave filter):

Y_{k} = H_{k} - [\frac{3 L_{k - 2} - 22 L_{k - 1} + 22 L_{k + 1} - 3 L_{k + 2} + 32}{64}] k = 2, . . ., n - 3

X_{2 k + 1} = L_{k} - [\frac{Y_{k} + 1}{2}] k = 0,1, . . ., n - 1

X _2k＝Y _k+X _2k+1 k＝0，1，…，n-1

Positive sense-class wavelet transformation: 2-N layer

The formula of preferred embodiment of the positive sense-class wavelet decomposition conversion of conversion stage 2-N (that is, except that level whole 1) is shown below.Note the width that " 2n " expression is measured with data sample by the data of this conversion process; " n " is assumed to be positive integer.Boundary filter T ₁By H ₀, H _N-1, L ₀And L _N-1Formulate, its wave filter support is shorter than inner wave filter T2.

In an optional embodiment, same class wavelet decomposition conversion is used for all layers.For example, the class wavelet decomposition transformed filter that is used for the 2-N layer shown here also can be used for the 1st layer of decomposition (that is, being used for the filtering raw image data).

H_{0} = X_{1} - [\frac{X_{0} + X_{2} + 1}{2}]

(boundary filter)

H_{k} = X_{2 k + 1} - [\frac{9 (X_{2 k} + X_{2 k + 2}) - X_{2 k - 2} - X_{2 k + 4} + 8}{16}] k = 1, . . ., n / 2 - 3

H_{\frac{n}{2} - 2} = X_{n - 3} - [\frac{X_{n - 4} + X_{n - 2} + 1}{2}]

(center-filter)

H_{\frac{n}{2} - 1} = X_{n - 1} - [\frac{{11 X}_{n - 2} + 5 X_{n + 1} + 8}{16}]

(center-filter)

H_{n \frac{}{2}} = X_{n} - [\frac{5 X_{n - 2} + 11 X_{n + 1} + 8}{16}]

(center-filter)

H_{n \frac{}{2} + 1} = X_{n + 2} - [\frac{X_{n + 1} + X_{n + 3} + 1}{2}]

(center-filter)

H_{k} = X_{2 k} - [\frac{9 (X_{2 k - 1} + X_{2 k + 1}) - X_{2 k - 3} - X_{2 k + 3} + 8}{16}] k = n / 2 + 2, . . ., n - 2

H_{n - 1} = X_{2 n - 2} - [\frac{X_{2 n - 3} + X_{2 n - 1} + 1}{2}]

(boundary filter)

L_{0} = X_{0} + [\frac{H_{0} + 2}{4}] = \frac{7 X_{0} + 2 X_{1} - X_{2} + 3}{8}

(boundary filter)

L_{1} = X_{2} + [\frac{H_{0} + H_{1} + 2}{4}]

(boundary filter)

L_{k} = X_{2 k} + [\frac{5 (H_{k - 1} + H_{k}) - H_{k - 2} - H_{k + 1} + 8}{16}] k = 1, . . ., n / 2 - 3

L_{\frac{n}{2} - 2} = X_{n - 4} + [\frac{H_{\frac{n}{2} - 3} + H_{\frac{n}{2} - 2} + 2}{4}]

(center-filter)

L_{\frac{n}{2} - 1} = X_{n - 2} + [\frac{2 H_{\frac{n}{2} - 2} + 2 H_{\frac{n}{2} - 1} + H_{n \frac{}{2}} + 4}{8}]

(center-filter)

L_{n \frac{}{2}} = X_{n + 1} + [\frac{2 H_{n \frac{}{2} + 1} + 2 H_{n \frac{}{2}} + H_{\frac{n}{2} - 1} + 4}{8}]

(center-filter)

L_{n \frac{}{2} + 1} = X_{n + 3} + [\frac{H_{n \frac{}{2} + 1} + H_{n \frac{}{2} + 2} + 2}{4}]

(center-filter)

H_{k} = X_{2 k} - [\frac{9 (X_{2 k - 1} + X_{2 k + 1}) - X_{2 k - 3} - X_{2 k + 3} + 8}{16}] k = n / 2 + 2, . . ., n - 3

L_{n - 2} = X_{2 n - 3} + [\frac{H_{n - 2} + H_{n - 1} + 2}{4}]

(boundary filter)

L_{n - 1} = X_{2 n - 1} + [\frac{H_{n - 1} + 2}{4}] = \frac{7 X_{2 n - 1} + 2 X_{2 n - 2} - X_{2 n - 3} + 3}{8}

(boundary filter)

The citation form of above-mentioned decomposition transform formula has only when n equals 10 at least just to be used.When n less than 10 the time, some formula that are used for the project between edge and the middle project are omitted, because the coefficient that will produce is very little, do not need these formula.For example, when n=8, two formula that are used to produce Lk will be left in the basket.

The attribute specification of transformed filter

Note, produce L ₀And L _N-1Edge transition wave filter T1 have just in time the wave filter supports of three input samples at the edge of input data array, and be weighted, make 70% of these coefficients be attributable to the rim value X of filtered data array boundary ₀Or X _2n-1The increasing the weight of of edge input data (that is, the sample of close array boundary) makes that image can be from conversion coefficient reconstruct, and do not have the sheet boundary artefacts basically, although when the conversion coefficient of generation sheet, edge and inner wave filter only are applied to the data of sheet inside.Produce L ₀And L _N-1The 1st layer of edge transition wave filter T1 be weighted to and make 50% rim value X of these coefficient values owing to filtered data array boundary _2n-1

In a preferred embodiment, the inner transformation wave filter is not to use with uniform way in whole filtered data array inside.In addition, inner wave filter comprises a center-filter, be used for the center of filtered data array or near 4 high passes of generation and 4 low-pass coefficients.In other embodiments, this center-filter can produce few to 2 low passes and 2 high-pass coefficients.This center-filter is used for conversion between the inner wave filter left side and the right (or bottom and upper segment) part.Conversion between two kinds of forms of inner wave filter is called " filtering switching " herein.Half of inner wave filter do not comprise center-filter, is the center with the data or the coefficient positions of even-numbered, and on second half the data that are centered close to the odd data position of inner wave filter.(certainly, the even number of array and odd data position can exchange).Although above formula places array center with center-filter, center-filter can be positioned at the data array optional position, as long as the transitions smooth between boundary filter and the inner wave filter.Certainly, must define the reciprocal transformation wave filter, make on the position identical, to have reverse center-filter with the positive-going transition wave filter.

The small data array transformation for mula of 2-N layer

When n=4, the conversion that carry out can be expressed as:

(X ₀，X ₁，X ₂，X ₃，X ₄，X ₅，X ₆，X ₇)→(L ₀，L ₁，L ₂，L ₃；H ₀，H ₁，H ₂，H ₃)

And above-mentioned general transformation for mula collection is reduced to as follows:

H_{0} = X_{1} - [\frac{X_{0} + X_{2} + 1}{2}]

H_{1} = X_{3} - [\frac{11 X_{2} + 5 X_{5} + 8}{16}]

H_{2} = X_{4} - [\frac{5 X_{2} + 11 X_{5} + 8}{16}]

H_{3} = X_{6} - [\frac{X_{5} + X_{7} + 1}{2}]

L_{0} = X_{0} + [\frac{H_{0} + 2}{4}]

L_{1} = X_{2} + [\frac{2 H_{0} + 2 H_{1} - X_{2} + 4}{8}]

L_{2} = X_{5} + [\frac{2 H_{3} + 2 H_{2} - H_{1} + 4}{8}]

L_{3} = X_{7} + [\frac{H_{3} + 2}{4}]

When n=2, the conversion that carry out can be expressed as:

(X ₀，X ₁，X ₂，X ₃)→(L ₀，L ₁；H ₀，H ₁)

H_{0} = X_{1} - [\frac{X_{0} + X_{3} + 1}{2}]

H_{1} = X_{2} - [\frac{X_{0} + X_{3} + 1}{2}]

L_{0} = X_{0} + [\frac{H_{0} + 2}{4}]

L_{1} = X_{3} + [\frac{H_{1} + 2}{4}]

Reverse wavelet-like transform: 2-N layer

The reverse wavelet-like transform of the 2-N transform layer that uses in the preferred embodiment (that is, except that the 1st layer whole) is shown below.The citation form of above-mentioned transformation for mula has only when n equals 10 at least just to be used.When n less than 10 the time, some formula that are used for the project between edge and the middle project are omitted, because the coefficient that will produce is very little, do not need these formula.

X_{0} = L_{0} - [\frac{H_{0} + 2}{4}]

X_{2} = L_{1} - [\frac{H_{0} + H_{1} + 2}{4}]

X_{2 k} = L_{k} - [\frac{5 (H_{k - 1} + H_{k}) - H_{k - 2} - H_{k + 1} + 8}{16}]

k = 2, . . ., \frac{n}{2} - 3

X_{n - 4} = L_{\frac{n}{2} - 2} - [\frac{H_{\frac{n}{2} - 3} + H_{\frac{n}{2} - 2} + 2}{4}]

X_{2 k + 1} = L_{k} - [\frac{5 (H_{k} + H_{k + 1}) - H_{k - 1} - H_{k + 2} + 8}{16}]

k = \frac{n}{2} + 2, . . ., n - 3

X_{n - 2} = L_{\frac{n}{2} - 1} - [\frac{2 H_{\frac{n}{2} - 2} + 2 H_{\frac{n}{2} - 1} - H_{n \frac{}{2}} + 4}{8}]

X_{n + 1} = L_{\frac{n}{2}} - [\frac{2 H_{n \frac{}{2} + 1} + 2 H_{\frac{n}{2}} - H_{\frac{n}{2} - 1} + 4}{8}]

X_{n + 3} = L_{n \frac{}{2} + 1} - [\frac{H_{n \frac{}{2} + 1} + H_{n \frac{}{2} + 2} - 2}{4}]

X_{2 n - 3} = L_{n - 2} - [\frac{H_{n - 2} + H_{n - 1} + 2}{4}]

X_{2 n - 1} = L_{n - 1} - [\frac{H_{n - 1} + 2}{4}]

X_{1} = H_{0} + [\frac{X_{0} + X_{2} + 1}{2}]

X_{2 k + 1} = H_{k} - [\frac{9 (X_{2 k} + X_{2 k + 2}) - X_{2 k - 2} - X_{2 k + 4} + 8}{16}]

k = 1, . . ., \frac{n}{2} - 3

X_{n - 3} = H_{\frac{n}{2} - 2} + [\frac{X_{n - 4} + X_{n - 2} + 1}{2}]

X_{n - 1} = H_{\frac{n}{2} - 1} + [\frac{11 X_{n - 2} + 5 X_{n + 1} + 8}{16}]

X_{n} = H_{n \frac{}{2}} + [\frac{5 X_{n - 2} + 11 X_{n + 1} + 8}{16}]

X_{n + 2} = H_{n \frac{}{2} + 1} + [\frac{X_{n + 1} + X_{n + 3} + 1}{2}]

X_{2 k} = H_{k} + [\frac{9 (X_{2 k - 1} + X_{2 k + 1}) - X_{2 k - 3} - X_{2 k + 3} + 8}{16}]

k = \frac{n}{2} + 2, . . ., n - 2

X_{2 n - 2} = H_{n - 1} + [\frac{X_{2 n - 3} + X_{2 n - 1} + 1}{2}]

When n=8, above-mentioned general reciprocal transformation formulary is reduced to as follows:

X_{0} = L_{0} - [\frac{H_{0} + 2}{4}]

X_{2} = L_{1} - [\frac{H_{0} + H_{1} + 2}{4}]

X_{4} = L_{2} - [\frac{H_{1} + H_{2} + 2}{4}]

X_{6} = L_{3} - [\frac{2 H_{2} + 2 H_{3} - H_{4} + 4}{8}]

X_{9} = L_{4} - [\frac{2 H_{5} + 2 H_{4} - H_{3} + 4}{8}]

X_{11} = L_{5} - [\frac{H_{5} + H_{6} + 2}{4}]

X_{13} = L_{6} - [\frac{H_{6} + H_{7} + 2}{4}]

X_{15} = L_{7} - [\frac{H_{7} + 2}{4}]

X_{1} = H_{0} + [\frac{X_{0} + X_{2} + 1}{2}]

X_{3} = H_{1} + [\frac{9 (X_{2} + X_{4}) - X_{0} - X_{6} + 8}{16}]

X_{5} = H_{2} + [\frac{X_{4} + X_{6} + 1}{2}]

X_{7} = H_{3} + [\frac{11 X_{6} + 5 X_{9} + 8}{16}]

X_{8} = H_{4} + [\frac{5 X_{6} + 11 X_{9} + 8}{16}]

X_{10} = H_{5} + [\frac{X_{9} + X_{11} + 1}{2}]

X_{12} = H_{6} + [\frac{9 (X_{11} + X_{13}) - X_{9} - X_{15} + 8}{16}]

X_{14} = H_{7} + [\frac{X_{13} + X_{15} + 1}{2}]

When n=4, the reciprocal transformation that carry out can be expressed as:

(L ₀, L ₁, L ₂, L ₃H ₀, H ₁, H ₂, H ₃) → (X ₀, X ₁, X ₂, X ₃, X ₄, X ₅, X ₆, X ₇) and above-mentioned general reciprocal transformation formulary be reduced to as follows:

X_{0} = L_{0} - [\frac{H_{0} + 2}{4}]

X_{2} = L_{1} - [\frac{2 H_{0} + 2 H_{1} - H_{2} + 4}{8}]

X_{5} = L_{2} - [\frac{2 H_{3} + 2 H_{2} - H_{1} + 4}{8}]

X_{7} = L_{3} - [\frac{H_{3} + 2}{4}]

X_{1} = H_{0} + [\frac{X_{0} + X_{2} + 1}{2}]

X_{3} = H_{1} + [\frac{11 X_{2} + 5 X_{5} + 8}{16}]

X_{4} = H_{2} + [\frac{5 X_{2} + 11 X_{5} + 8}{16}]

X_{6} = H_{3} + [\frac{X_{5} + X_{7} + 1}{2}]

When n=2, the reciprocal transformation that carry out can be expressed as: (L ₀, L ₁H ₀, H ₁) → (X ₀, X ₁, X ₂, X ₃)

And above-mentioned general reciprocal transformation formulary is reduced to as follows:

X_{0} = L_{0} - [\frac{H_{0} + 2}{4}]

X_{3} = L_{1} - [\frac{H_{1} + 2}{4}]

X_{1} = H_{0} + [\frac{X_{0} + X_{3} + 1}{2}]

X_{2} = H_{1} + [\frac{X_{0} + X_{3} + 1}{2}]

In a preferred embodiment, during every layer of reciprocal transformation process, the coefficient of even number position (that is X, _2iValue) must be at coefficient (that is X, of odd positions _2i+1Value) calculates before.

In alternative embodiment, short T1 decomposition transform is used for total data filtering, rather than marginal date.Only use short T1 decomposition transform to shorten computing time, reduced complicacy, but reduced data compression rate, therefore, image file is bigger.Only use short T1 decomposition transform also to shorten to decode and comprise the computing time of the image file that uses image encoded of the present invention,, only use the T1 restructuring transformation of corresponding weak point because in image reconstruction procedure.

The adaptive block mode quantizes

With reference to figure 3, each wavelet coefficient that is produced by the conversion of class wavelet decomposition is quantized:

{\hat{x}}_{q} = sign (x) [(\frac{| x |}{q} + \frac{3}{8})]

Wherein q is a quantization factor, and goes to quantize:

\hat{x} = q {\hat{x}}_{q} .

According to the present invention, use a quantization table to come to specify a quantization factor for the sub-band of each wavelet coefficient, thus the control compression quality.If carry out 5 layers of wavelet transformation (carry out chromatic value 4 layers) of brightness value, 16 brightness value sub-bands arranged in decomposition:

LL ₅，HL ₅，LH ₅，HH ₅，HL ₄，LH ₄，HH ₄，HL ₃，LH ₃，HH ₃，HL ₂，LH ₂，HH ₂，HL ₁，LH ₁，HH ₁

With 13 chromatic value sub-bands:

LL ₄，HL ₄，LH ₄，HH ₄，HL ₃，LH ₃，HH ₃，HL ₂，LH ₂，HH ₂，HL ₁，LH ₁，HH ₁

A possible quantization table is used for brightness value:

q＝(16，16，16，18，18，18，24，24，24，36，46，46，93，300，300，600)

Be used for chromatic value:

q＝(32，50，50，100，100，100，180，200，200，400，720，720，1440)。

But in a preferred embodiment, quantization factor q is the closeness according to characteristics of image in the sheet, and is adaptively selected at each different sheet of image.With reference to figure 8, we are with sub-band LH _k, HL _kAnd HH _kInlet be denoted as u _Ij ^(k), v _Ij ^(k)And w _Ij ^(k)With reference to figure 9, the block classifier module is that each transform layer (for example, k=1,2,3,4,5) of this sheet calculates a chunk classification value:

U_{k} = \underset{ij}{Σ} | u_{ij}^{(k)} |

V_{k} = \underset{ij}{Σ} | v_{ij}^{(k)} |

W_{k} = \frac{1}{2} \underset{ij}{Σ} | w_{ij}^{(k)} |

B _k＝max{U _k，V _k，W _k}

S_{k} = \sqrt{\frac{1}{2} {U_{k}^{} + V_{k}^{} + W_{k}^{2} - \frac{1}{3} (U_{k} + V_{k} + W_{k})}}

Horizontal and vertical lines major part in the original image will be respectively by u _Ij ^(k)And v _Ij ^(k)Expression.If original image (that is, in the sheet by block classifier estimation) comprise many features (as, edge and lines), B then _kOften bigger.Therefore, B _kBe worth greatly more, compressed image and do not produce artifacts of compression will be difficult more.

Use 2 class models, two quantization tables be provided:

Q ₀＝(16，16，16，18，18，18，36，36，36，72，72，72，144，300，300，600)，

Q ₁＝(16，32，32，36，36，36，72，72，72，144，144，144，288，600，600，1200)

Q wherein ₀The piece that is used for " being difficult to " compression, Q ₁The piece that is used for " easily " compression.

According to one or more B _kThe value and the comparison of one or more corresponding threshold, internal sheets (that is, not the sheet on image boundary) is classified as " difficulty " or " easily " separately and compresses.For example, as shown in Figure 9, the B of a sheet ₁Can with first threshold TH1 (as, 65) relatively (step 271).If B ₁Greater than this threshold value, then this sheet is classified as " difficulty " (step 272).In addition, B ₅With the second threshold value TH2 (as, 60) relatively (step 273).If B ₅Greater than this threshold value, then this sheet is classified as " difficulty " (step 274), otherwise, it is categorized as " easily " (step 275).Utilize then by quantizing corresponding to the quantization factor of the quantization table appointment of piece (that is sheet) classification wavelet coefficient with this sheet.

In a preferred embodiment, by comparing B ₁With another high threshold TH1B, for example 85, border piece is classified.B ₁Value is categorized as " being difficult to " compression greater than the border piece of this threshold value, otherwise is categorized as " easily " compression.

In another embodiment, can specify 3 or more piece classification, and can define one group of corresponding threshold.According to B ₁And/or other B _iThe value and the comparison of these threshold values are categorized as a kind of appointment with a sheet, select the corresponding quantitative table then, to determine to be applied to the quantized value of the sub-band in the sheet.If original image comprises many features, then S _kAlso often bigger, therefore, in certain embodiments, use S _kReplace B _kCome the classification chart photo.

Divide the sparse data coding of pith and inessential part

With reference to figure 10A and 10B, produced primary image a sheet conversion coefficient and quantize after, next step is exactly the coefficient of the sheet that produced of coding.Each NQS sub-band is repeated a batch total calculate step 280.Divide by bit plane by the bit stream that each the NQS sub-band of encoding produces, form one group then, be stored in bit stream in the image file, describe with reference to figure 5A-5E as above with formation.

The maximum bit-depth mask

With reference to figure 10A, the maximum bit-depth (286) of the data block in the NQS sub-band that coded program or device are determined to be encoded, this is the required maximum number of digits of any coefficient value in this piece of coding, is called maximum bit-depth herein.The maximum bit-depth value is determined by the required maximum number of digits of absolute value of the arbitrary data values in this piece of calculation code.Especially, maximum bit-depth equals int (log2V)+1, and wherein V is the maximum value of arbitrary element in this piece, the integral part of " int () " expression occurrence.The maximum bit-depth of each top layer piece is stored in the corresponding bit stream (as, the significant bits stream of the sub-band group that its coefficient is encoded).Then, to current block invoking block program (288).The pseudo-code of piece program is expressed and is shown in Table 2.

Each piece comprises 4 sub-pieces (seeing Figure 11 A).Shown in Figure 11 B, the piece program is determined the maximum bit-depth (300) of per 4 sub-pieces of current block.Then, its generation and coding maximum bit-depth mask (301).This mask has 4: m ₁, m ₂, m ₃, m ₄, be set to have only the maximum bit-depth m that equals current block (father's piece) when the maximum bit-depth of corresponding sub-piece respectively ₀The time equal predetermined value (as, 1), otherwise be set to equal 0.The mathematical expression of this mask is as follows:

Mask=(m ₀==m ₁)+(m ₀==m ₂)+(m ₀==m ₃)+(m ₀==m ₄)

Wherein, "+" expression cascade.

For example, mask 1000 expressions have only the maximum bit-depth of sub-piece 1 to equal the maximum bit-depth of current block.The value of mask is always between 1-15.

Huffman (Huffman) table (the seeing Table 1) coding of the most handy 15 marks of maximum bit-depth mask.As seen from the table, only with 3 positions codings, wherein have only the maximum bit-depth of a sub-piece to equal the maximum bit-depth of father's piece corresponding to 4 mask values of the most common mask pattern.

The Huffman table of table 1 coding maximum bit-depth mask

Mask	The Huffman code
Mask	The Huffman code	0001	111
0010	101	0001	111
0010	101	0011	1001
0100	011	0011	1001
0100	011	0101	0010
0110	10000	0101	0010
0110	10000	0111	01001
1000	110	0111	01001
1000	110	1001	01000
1010	0001	1001	01000
1010	0001	1011	00110
1100	0101	1011	00110
1100	0101	1101	00111
1110	0000	1101	00111
1110	0000	1111	10001

Coded sub-blocks maximum bit-depth value

In addition, step 301 comprises the maximum bit-depth m that equals current block for its maximum bit-depth ₀Each subblock coding maximum bit-depth value.For example, shown in Figure 11 A and 11B, if the maximum bit-depth value of current block is

m ₁，m ₂，m ₃，m ₄＝5，0，3，2

The maximum bit-depth value that then needs to be encoded has only m ₂, m ₃And m ₄, because from the maximum bit-depth m of maximum bit-depth mask with the current block of previous storage and coding ₀The known maximum bit-depth value of value m ₁

Should be noted that if m ₀=1, then do not need the maximum bit-depth value of coded sub-blocks, because can know those values fully from the maximum bit-depth mask.

If m ₀Be not equal to 1, then be not equal to m for each ₀M _i, the following coding of program m _iValue:

m _i=0, then to export a string length be m to program ₀-10; With

Otherwise it is m that program is exported a string length ₀-m _i-10, be one 1 at last.

For example, if m ₀=5, and m ₁=0, m then ₁Be encoded as a string 4 0:0000.If m ₀=5, and m ₁=3, m then ₁Being encoded as a string (5-3-1=1) 10, is 1:01 at last.

More than { m ₁, m ₂, m ₃, m ₄}={ 5,0,3, in the example of 2}, the maximum bit-depth value is encoded to:

Mask	m ₂Sub-piece	M ₃Sub-piece	m ₄Sub-piece
Mask	m ₂Sub-piece	M ₃Sub-piece	m ₄Sub-piece	111	0000	01	001

Then, if the coefficient of the NQS sub-band that is encoded will be stored in two or more bit streams, then the coding of the maximum bit-depth of this piece is expressed and is divided into two parts or more, and each part comprises the information content of the bit plane of particular range.In order to explain that we will explain that how maximum bit-depth value and mask and coefficient are divided into two parts, are called pith and inessential part herein easily.Same technology can be used for these values are divided into corresponding to important, medium important and inessential (least important) three bit plane scopes partly.

For each NQS sub-band, do not comprise last group NQS sub-band, the coefficient bits plane is divided into two or three scopes.When having two bit plane scopes, select or a predetermined bit plane threshold value of dividing these two scopes.Be stored in " inessential " bit stream 206 less than " inessential " of this bit plane threshold value part each " coefficient value " (comprising its maximum bit-depth value) and (see Fig. 5 D), other coefficient storage is in the significant bits stream 206 of correspondence.The selection of bit plane scope is normally rule of thumb carried out, but uses different bit plane scope coding great amount of images, selects one group of bit plane scope then, thereby realizes on an average according to the bit stream of the different resolution level particular division to data.For example, described particular division can be that data are approximately equally divided between the bit stream of first stage resolution ratio and second stage resolution ratio.Alternatively, described particular division can require the bit stream of second stage resolution ratio to comprise the data of 4 times of the bit streams of first (lower) stage resolution ratio.

At first, we will illustrate the maximum bit-depth value will be divided into important and inessential part, then, coding is described and divide the coefficient value of smallest blocks.

If the maximum bit-depth m of a piece ₀Less than threshold value, then each of this sub-piece maximum bit-depth mask and maximum bit-depth value is stored in the inessential part of primary image son file.Otherwise the maximum bit-depth mask is stored in the pith, and then, each coded sub-blocks maximum bit-depth value is divided into important and inessential part.This division is following to be carried out: if m _i〉=threshold value, then whole coding maximum bit-depth value m _iBe included in the pith of subimage son file.Otherwise, remove m _i=m ₀Outward, each maximum bit-depth value m _iM at first ₀-threshold value position is stored in the pith of subimage son file, and each m _iOther (if there is) be stored in subimage in the inessential part of file.

If the bit plane of coefficient is divided into three scopes, then selects or predetermined two bit plane threshold values, and use technology same as described above that maximum bit-depth mask and value are distributed in three bit streams.

The coefficient value of coding smallest blocks

Then, if the size of current block (that is, the coefficient value quantity in the current block) is not the minimum number of being scheduled to (302-is not), for example, and 4, then to per 4 sub-piece invoking block programs (303) of current block.This is that recursive program calls.The result of antithetical phrase piece invoking block program, the maximum bit-depth mask of this sub-piece and value are encoded and insert in a pair of bit stream of the sub-band group that is encoded.As the fruit piece is not the minimum dimension of being scheduled to, then to its sub-piece recursive call piece program.

When the piece of predetermined minimum dimension during by the piece routine processes (302-is), the maximum bit-depth value of the maximum bit-depth of this piece and the sub-piece back (301) that is encoded, the coefficient of this piece is encoded, and encoded radio is divided into important and inessential part (304).

Be not equal to each coefficient of 0 and comprise a POS/NEG position, indicating its symbol, and quantity is the additional bit of maximum bit-depth.In addition, except sign bit, the MSB of each non-0 coefficient (most significant bit) is known from the maximum bit-depth value of this coefficient, and as many as 1.Therefore, this MSB does not need coding (or from another viewpoint, it is encoded with the maximum bit-depth value).

For the coefficient of each smallest blocks, if the maximum bit-depth of this coefficient less than threshold value, then whole of this coefficient, comprises its sign bit, in inessential part.Otherwise sign bit is in pith, and if any, the above most significant bit (MSB) of the number of threshold values of least significant bit (LSB) is also included within the pith.In other words, the position of bottom " threshold value " number is assigned in the inessential part.But if maximum bit-depth equals threshold value, the then symbol position still is assigned in the pith, and other position is distributed in the inessential part.

In addition, as mentioned above, because the MSB of the absolute value of each coefficient is known from maximum bit-depth mask and value, does not store this position.Equally, value is that 0 coefficient is not encoded yet, because their value is known fully from the maximum bit-depth value of this coefficient, described maximum bit-depth value is 0.

For example (see Figure 11 C), 4 coefficients of a piece of consideration 31,0 ,-5 ,-2} and a threshold value 3.The value of this piece is shown POS 11111,0 with binary form, and NEG 101, and NEG 10.At first, the MSB of non-0 coefficient of 0 value coefficient is excluded, thereby obtains: POS 111, NEG01, and NEG 0.Then, the least significant bit of number of thresholds (except sign bit) is assigned to inessential part, the remaining pith that is assigned to:

Pith: POS 1, NEG

Inessential part: 111,01, NEG 0.

Pith comprises the most important position of coefficient value 31 and-5, and inessential part comprises whole positions of other and coefficient value-2 of coefficient value 31 and-5.

Table 2

The false code of block encoding program

//Encode MaxbitDepth mi for each subblock i:Determine MaxbitDepth mi for each subblock i=1,2,3,4mask=(m0==m1)+(m0==m2)+(m0==m3)+(m0==m4)//where the“+”in the above equation represents concatenationEncode and store mask using Huffman tableFori=1 to 4{  If mi≠m0{     if mi=0{         output a string of m0 O′s}     else{//mi≠0         output a string of m0-mi O′s,followed by a 1}     }    }//Divide the encoded MaxbitDepth mask and MaxbitDepth between significant and//insignificant portions as follows:<dp n="d36"/>If m0＜threshold{    output the MaxbitDepth mask and MaxbitDepth values to insignificant bitstream}else{    output the MaxbitDepth mask to significant bitstream;    for i=1 to 4{        if mi=m0{output nothing for that mi}        else{           if mi≥threshold{output mi to significant bitstream}           else {              output the first m0-threshold bits of mi to the significant bitstream              and output the remaining bits of mi(if any)in the insignificant              bitstream}           }        }    }//Encode Coefficient values ifblock is of minimum sizeIf size of current block is＞minimum block size{    //coefficient values are denoted as ci    for i=1 to 4{        Call Block(subblock i);        }    else{//size of current block is≤minimum block size        C=number of coefficients in block;//if block size is already known,skip this step        for i=1 to C{            if mi＜threshold{　　            output all bits of ci to insignificant bitstream;　　            }　　        else{　　            output sign(ci)to the significant bitstream;　　            if mi＞threshold{　　                #M=mi-threshold-1;//#M≥0　　                output the #M most significant bits to the significant bitstream;　　                }　　            output all remaining least significant bits of ci to the insignificant bitstream;　　            }　　        }//end of coefficient processing loop　　    }    //end of main else clause　　}        //end of procedureReturn

As mentioned above,, then select or predetermined 2 bit plane threshold values, and use above-mentioned identical technology that the coefficient value of encoding is distributed between 3 bit streams if the bit plane of coefficient will be divided into 3 scopes.

Image reconstruction

Will be to be equal to or less than stage resolution ratio that a primary image in the image file is encoded from this image file reconstructed image, then this image file each bit stream below described stage resolution ratio is all decompressed and go to quantize.Then, the conversion coefficient of reconstruct is carried out reciprocal transformation with form piecewise, thereby with specific stage resolution ratio reconstructed image data.

With reference to Figure 12, image reconstruction procedure is according to an image of view data reconstruct (320) that receives from image file.The program of carries out image reconstruct or the user of equipment, a stage resolution ratio R (322) who is equal to or less than the highest resolution level that comprises in the view data is selected or specifies in the perhaps control program of representative of consumer operation.The title that reads this image data file with the quantity of determining the sheet in the image and arrangement (L, K), and the image reconstruction program out of Memory (323) that may need.Step 324 and 326 is with given stage resolution ratio reconstructed image, and in step 328, the image of reconstruct is shown or is stored in the memory device.Figure 13 A and 13B provide the more detailed view of this program, are used for the data in specific subimage level decoding particular patch.

In a preferred embodiment, as shown in figure 12, the data in the image file relevant with the given resolution level at first are reassembled as the son file that a slice connects a slice, and each slice, thin piece file comprises the bit stream (324) of this sheet.Then, every data processed (326).Read heading message, with the maximum bit-depth of each top layer sub-band piece of determining this sheet, be used to quantize the quantization factor of each subimage sub-band etc.Conversion coefficient with each required NQS sub-band of given resolution level reconstructed image is decoded according to the sub-band order.The details of decode procedure of the coefficient in any one NQS sub-band of decoding will be discussed with reference to figure 13B below.By the quantization factor (the Q table that identifies from the primary image title obtains) of using each sub-band, the desorption coefficient that is obtained is gone to quantize.Then, the quantization parameter that goes that produces is used reciprocal transformation.Note, described in the above from the class small echo reciprocal transformation of removing the quantized transform coefficients reconstructed image.

With reference to figure 13A, for data with a sheet t of specified resolution level decoding, repeat one group of step 340, each NQS sub-band with this sheet of decoding, do not comprise the unwanted NQS sub-band of this given resolution level, do not comprise yet this given resolution level the unwanted any bit stream that comprises the bit plane of desorption coefficient value.With reference to figure 5D and 5E, have only the bit stream of the needed primary image of this given resolution level decoded.Specific top layer piece (corresponding to a NQS sub-band) for decoded sheet, the maximum bit-depth of this top layer piece or definite from the title (if data have been reassembled as chip arrays) of chip arrays, perhaps determine (346) from the data of the initial bits of this sub-band stream, then, call the decoding block program, with the data (348) of decoding current block.

After the data decode of specific sub-band, the decoding conversion coefficient of this sub-band can utilize the corresponding quantization factor to be gone to quantize (350).Alternatively, go to quantize and after all whole coefficients of sub-band are all decoded, to carry out again.

In case whole coefficients of NQS sub-band all go to quantize, and just carry out reciprocal transformation, with the view data as anter t of regeneration specified resolution level.

In an optional embodiment, the step S324 of Figure 12 does not use, and the data in the image file are not reassembled as chip arrays.On the contrary, the sub-band group is handled view data one by one, requires the conversion coefficient of whole sheets of recovery to be added up and storage in the initial reconstitution step.The step 340 of the data of a top layer piece of the particular patch of the specific sub-band group of decoding repeats each sheet.Especially, specific top layer piece for the particular patch of specific sub-band group, the maximum bit-depth of this top layer piece or from the title of this chip arrays is perhaps determined (346) from the initial data of the bit stream of sub-band group, calls the decode data (348) of current block of decoding block program then.

With reference to figure 13B, the maximum bit-depth data in decoding block program (it can be used for the preferred embodiment and the optional embodiment of aforementioned paragraphs) the applicable coded data array of at first decoding are with the maximum bit-depth (360) of each sub-band of determining current block.According to decoded NQS sub-band, the maximum bit-depth data of a piece may also may be segmented in two or three bit streams, as mentioned above in a bit stream, therefore, will be read and decode from the maximum bit-depth the used data bit in the bit stream of all requirements.If the size of current block is not greater than predetermined smallest block size (362-is), then each the sub-piece to current block calls decoding block program (363).This is that recursive program calls.The antithetical phrase piece calls the result of decoding block program, and the maximum bit-depth value of this sub-piece is decoded.If this sub-piece is not the minimum dimension of being scheduled to, then to its sub-piece recursive call decoding block program, the rest may be inferred.

When by the decoding block routine processes during piece of predetermined minimum dimension (362-is), the coefficient of this piece is decoded.According to decoded sub-band group, the desorption coefficient of a piece may also may be segmented in two or three bit streams in a bit stream, as mentioned above, therefore, but will be read and decode from the application data position in the bit stream of all requirements.

With reference to figure 13A, for the whole NQS sub-bands that comprise in the given resolution level, the every quantization transform coefficient of regenerating.After these coefficients are gone to quantize, each sheet is used reciprocal transformation (352), this described.

Use the embodiment of non-level that replaces and vertical conversion

In a further advantageous embodiment, each sheet of image at first by a plurality of (as, 5) the horizontal decomposition transform layer handles, the orthogonal decomposition transform layer processing by similar number then.Ground of equal value, vertical transform layer can be used prior to the horizontal transformation layer.In the hardware of image conversion method of the present invention was realized, this order conversion of transform layer had following advantage: (A) reduce the number of times of data array rotation, or (B) avoid the needs for the role's of switching row and column in the work pattern matrix circuit.When the horizontal transformation carried out subsequently, second horizontal transformation is applied to the most left array of the low frequency coefficient that produced by first horizontal transformation, and the 3rd horizontal transformation is applied to the most left array of the low frequency coefficient that produced by second horizontal transformation, and the rest may be inferred.Like this, the twice of the data in the transform method that second data of using to the N horizontal transformation are exactly level with vertical conversion replaces.But this extra data processing is not brought any additional processing time basically on hardware is realized, because in such realization, horizontal filter is applied to whole row of work pattern matrix simultaneously.

Vertical conversion is applied to the continuous less subarray of work pattern matrix continuously.After view data was by all transform layers (level is with vertical) conversion, the conversion coefficient that above-mentioned quantification and coding step are applied to producing was to finish the picture coding process.

As mentioned above, different (normally short) transformed filter can be applied to the coefficient near processed array edges, and long usually transformed filter is applied to the coefficient away from these array edges.Use long transformed filter to provide long wave filter better data compression at the center, and short transformed filter has been eliminated the data of adjacent sheet and the demand of coefficient.

The digital camera structure

With reference to Figure 14, an embodiment according to digital camera system 400 of the present invention is shown.This digital camera system 400 comprises image capture device 402, is fit to catch the mechanism of image as the digital code information array as ccd sensor or any other.Suppose that image capture device comprises an analog to digital conversion (ADC) circuit, being used for the analog image information translation is digital value.

Working storage 404 is random access memory normally, from the receiving digitally encoded image information of image acquisition equipment 402.More at large, its 406 pairs of image of data (that is, image) treatment circuit of being used at camera carries out storing digitally coded image during conversion, compression and the processing.Data processing circuit 406 comprises a hardware logic and a group state machine in one embodiment, is used to carry out one group of predetermined processing operation.

In optional embodiment, data processing circuit 406 can partly or entirely be embodied as quick general purpose microprocessor and one group of software program.But, at least use available technology in 2000, be difficult to enough fast velocity process and storage full resolution image (full-colour image that for example, has 1280 * 840 pixels), camera can be absorbed such as 20 pictures by per second, and this is that some commercial products are desired.If by the software of parallel processing technique or good design, the rapid image that lower powered general image data microprocessor can support digital camera to need is handled, and data processing circuit 106 can use such general purpose microprocessor to realize so.

After data processing circuit 406 processing, each image is stored as " image file " usually in non-volatile memory device 408, and equipment 408 is used " sudden strain of a muscle " usually, and (that is, EEPROM) technology of depositing realizes.Non-volatile memory device 408 preferably is embodied as the activity store card.This allows camera user to pull out a memory card, inserts another, continues then to take pictures.But in certain embodiments, non-volatile memory device 408 is not movable, and in this case, camera has a data access interface 410 usually, makes camera transmit image file mutually with miscellaneous equipment, as general desktop.Digital camera with non-volatile memory device 408 also can comprise data access interface 410.

Digital camera 400 comprises one group of button 412, is used to provide the camera instruction.Except the Image Acquisition button; usually also have several other buttons, the image quality level that is used for selecting the next one to take, the image of roller storage so as on image of camera viewer 414, to watch, deleted image and other function of calling camera from non-volatile memory device 408.Other function like this may comprise using between flashlamp and the computing machine transmits image file.In one embodiment, these buttons are dynamo-electric contact-making switches, and in other embodiments, can be implemented as touchscreen button on user-interface display 416 or the scanner back 414 to the small part button.

User-interface display 416 is embodied as independently LCD display device of (A) and scanner back 414 usually, or the image that (B) shows on the scanner back 414.Menu, user prompt and may be displayed on the user-interface display 416 about the information that is stored in the image in the non-volatile video memory 408 are no matter how this demonstration realizes.

After image is acquired, handles and be stored in the non-volatile memory device 408, relevant image file can be retrieved, from storer 408 so that on scanner back, watch.More specifically, image file is converted back to the data array that is adapted at storage in the frame buffer 418 by the compressed format of its conversion.View data in the frame buffer is presented on the scanner back 414.Date circuit 420 is used to follow the tracks of current date and time, and the date and time that each image of storage is all stamped photographic images stabs.

Also with reference to Figure 14, digital camera 400 preferably includes data processing circuit 406, be used to carry out the predetermined basic operation of a cover, as carrying out conversion is applied to required multiplication of a certain amount of view data and add operation, an and group state machine 430-442, be used for the control data treatment circuit, handle operation to carry out one group of predetermined picture.In one embodiment, the state machine in the digital camera is as follows:

One or more state machines 430 are used for conversion, compression and storage and obtain the image that mechanism receives from image of camera.This image is sometimes referred to as " view finder " image, because the image that processed image is normally seen on the image of camera viewer 414.This group state machine 430 is the initial state machines that are stored in each image file in the non-volatile memory device 408 that produce.Before taking, the quality-class that the user uses the button 412 of camera to come selected digital image to store.In a preferred embodiment, picture coding state machine 430 is realized one or more features of the present invention.

One or more state machines 432 are used to decompress, inverse transformation and show the image file of storage on the scanner back of computing machine.Be stored in the frame buffer 418 of camera by decompression, inverse transformation and the reconstructed image that goes the quantized image data to produce, it can be watched on scanner back 414.

One or more state machines 434 are used for upgrading and showing the counting of the picture number that is stored in non-volatile memory device 408.This picture count preferably is presented on the user-interface display 416.The number percent that this group state machine 434 also will indicate non-volatile memory device 408 not taken by image file usually, or other indication of the ability of the further memory image of camera.If camera does not have independently interface display 416, these memory state information may be displayed on the scanner back 414, as, be superimposed upon on the image that shows in the scanner back 414, or be presented in the zone that is independent of main viewer image on the scanner back 414.

One or more state machines 436, be used to realize " view finder " pattern of camera, the wherein current image of " being seen " by Image Acquisition mechanism 402 is presented on the scanner back 414, makes the user to see to press image to be stored behind the Image Acquisition button.These state machines may carried out suitable repairing step with after improving raw image data, will be transferred to the frame buffer 418 of camera from the image that image acquisition equipment 402 receives.

One or more state machines 438 are used for from non-volatile memory device 408 to external unit such as multi-purpose computer download images.

One or more state machines 440 are used for uploading image from external unit such as multi-purpose computer to non-volatile memory device 408.This makes camera can be used as equipment with the aid of pictures, and the equipment that is used as the image file on the transmission memory card.

Optional embodiment

Generally speaking, when the available work storer is not enough to entire image handled as single, perhaps must be in different environment at product, comprise when working in the low memory environment, perhaps when image need transmit by the low bandwidth communication passage, perhaps when must or preferably provide the image of different resolution level, the present invention will be useful in any such " conserve memory " environment.

In the flow pattern data realized, in the web browser that receives the compressed image that uses the present invention's coding, the subimage of an image may be decoded hastily and be decompressed, because the data of the more senior subimage of other of this image just are received.As a result, one or more lower-resolution stages versions of compressed image may be by reconstruct and demonstration before the data of the highest resolution version that receives (and/or decoding) image by communication port.

In another optional embodiment, can use the conversion that is different from above-mentioned wavelet-like transform.

In optional embodiment, image sheet can be handled according to different order.For example, image sheet can be handled from right to left, rather than from left to right handles.Equally, image sheet can progressively be handled towards top row from bottom line.

The present invention can be implemented as computer program, comprises the computer program in the embeddeding computer readable storage medium storing program for executing.For example, this computer program can comprise program module shown in Figure 2.These program modules can be stored in CD-ROM, disk storage product or any other mechanized data or the program storage product.Software module in the computer program can also be by the internet or by distributing in the electronics mode with carrier-wave transmission computer data signal (wherein embedding described software module).

Although invention has been described with reference to several specific embodiments, above-mentioned explanation is exemplary, is not regarded as limiting of the invention.Those skilled in the art can carry out various modifications and not depart from the spirit and scope of the invention that is defined by claims.

Claims

1. the method for an image data processing array comprises:

The transformed filter of predetermined family is applied to array of image data, thereby produces continuous transformation series array, every group of conversion coefficient comprises the fringing coefficient and the non-fringing coefficient that is positioned at this group conversion coefficient interior location of this group conversion coefficient outer boundary; The transformation series array comprises a last transformation series array and one or more transformation series array of elder generation; With

Described application comprises the view data and the coefficient that is positioned at each more first transformation series array border that short transformed filter is applied to array boundary, to produce fringing coefficient, and will grow filter applies in the view data of array interior location and the coefficient of the transformation series array interior location of elder generation, to produce non-fringing coefficient;

Wherein, the wave filter support of short transformed filter is shorter than long transformed filter, and when generating the transformation series array, short transformed filter and long transformed filter all only are applied to the view data of array inside, and only are applied to the interior conversion coefficient of more first transformation series array of this array.

2. the method for claim 1, its short-and-medium transformed filter comprises the short low spatial frequency wave filter that produces the low spatial frequency coefficient, this short low spatial frequency filter weight is the view data of close array boundary and the conversion coefficient on the most close each more first transformation series array border, thereby can be, and there be the array boundary illusion from the conversion coefficient reproduced picture.

3. the method for claim 2, wherein, the edge transition coefficient on the most close more first transformation series array border of short low spatial frequency filter weight makes by wave filter to be the conversion coefficient that can belong to the most close more first transformation series array border more than 50% of the edge transition coefficient of next transformation series array generation.

4. the process of claim 1 wherein that a plurality of transformed filters are asymmetric boundary filters, extend to first scope of each array boundary, and on direction, extend to second long scope, but do not extend beyond array boundary away from array boundary.

5. the process of claim 1 wherein that transformed filter is small echo or class wavelet decomposition transformed filter.

6. the method for claim 1, wherein, long wave filter comprises a center-filter, be applied to the view data of predetermined array set of locations in the interior location, be used to produce a group switching centre high pass and low pass conversion coefficient, and this long wave filter also comprises the first and second different inside wave filters, wherein, the first inner filter applies is in the array position of predetermined array set of locations first side, and the second inner filter applies is in the array position of the second different side of described predetermined array group.

7. the method for an image data processing array comprises:

According to the sheet of predefined procedure image data processing, these sheets comprise the not lap of view data, thereby produce the view data of handling; With

With the image data storage of handling is data image files;

The processing of every picture data comprises:

The transformed filter of predetermined family is applied to the view data sheet, thereby produces continuous transformation series array, every group of conversion coefficient comprises the fringing coefficient and the non-fringing coefficient that is positioned at this group conversion coefficient interior location of this group conversion coefficient outer boundary; The transformation series array comprises a last transformation series array and one or more transformation series array of elder generation; And

Described application comprises the view data and the coefficient that is positioned at each more first transformation series array border that short transformed filter is applied to the sheet border, to produce fringing coefficient, and will grow filter applies in the view data of sheet interior location and the coefficient of the transformation series array interior location of elder generation, to produce non-fringing coefficient;

Wherein, the wave filter support of short transformed filter is shorter than long transformed filter, and when generating the transformation series array, short transformed filter and long transformed filter all only are applied to the view data of sheet inside, and only are applied to the interior conversion coefficient of more first transformation series array of this sheet.

8. the method for claim 7, wherein every processing comprises:

For at least two corresponding transformation series arrays, produce one or more parameters, the characteristics of image closeness in this sheet of the value representation of these parameters;

According to the value of one or more parameters, sheet is classified as the classification of predetermined group;

According to the classification that sheet is included into, select one group of quantization factor of each respective flap; And

By the conversion coefficient of this this sheet of quantization factor group bi-directional scaling, to produce one group of quantization transform coefficient of this sheet.

9. the method for claim 8 comprises:

In image data file, store a sign, be designated as every selected quantization factor group of view data.

10. the method for an image data processing array comprises:

The transformed filter of predetermined family is applied to array of image data, to produce continuous transformation series array, comprise the first family transformed filter is applied to array of image data, to produce first group of conversion coefficient, with the second family transformed filter is applied to first group of conversion coefficient, to produce second group of conversion coefficient;

Wherein, the wave filter support of first family transformed filter is than the weak point of second family transformed filter.

11. the method for claim 10, wherein, use the first family transformed filter and comprise the view data that the first short transformed filter is applied to the array boundary place, with the view data that the first long transformed filter is applied to the array interior location, and use the second family transformed filter and comprise the coefficient that the second short transformed filter is applied to the fringing coefficient of first group of conversion coefficient boundary and the second long transformed filter is applied to first group of conversion coefficient interior location.

12. the method for claim 10 comprises the second family transformed filter is applied to second group of conversion coefficient, to produce the 3rd group of conversion coefficient and the second family transformed filter is applied to the 3rd group of conversion coefficient, to produce the 4th group of conversion coefficient.

13. the method for claim 12, wherein, use the first family transformed filter and comprise the view data that the first short transformed filter is applied to the array boundary place, with the view data that the first long transformed filter is applied to the array interior location, and use the second family transformed filter and comprise that lacking transformed filter with second is applied to the fringing coefficient of respective sets conversion coefficient boundary, and the second long transformed filter is applied to the coefficient of this respective sets conversion coefficient interior location.