Title of Invention

DIGITAL IMAGES

Abstract

A rate control means for rate allocation in JPEG2000 processing apparatus is disclosed. The rate control means includes means to receive various parameters from the tier-1 coder and means to calculate R−D slope, means for composing a bucket elements, means for comparing the RD slope of each bucket elements with the threshold slope of each bucket, and selecting the bucket into which the current elements is to be added; means for accepting the selected bucket number and generating an address for storing the current bucket elements; means for keeping a count of, number of elements in each bucket and the sum of the differential byte count of each elements in that bucket; for all buckets; means for including the bucket elements and means for keeping the record of number of coding passes and number of bytes to be included for each code block, during and after the rate control.

Full Text

FORM - 2 THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003 PROVISIONAL Specification (See section 10 and rule 13) DIGITAL IMAGES TATA CONSULTANCY SERVICES LTD., an Indian Company of Bombay House, 24, Sir Homi Mody Street, Mumbai 400 001, Maharashtra, India, THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION. Field of invention: The invention relates to digital images. Particularly, the invention relates to compression of digital images. More particularly, the invention relates to JPEG2000 standard for efficient compression of digital images. Background of the invention: Introduction: A digital image or "bitmap" consists of a grid of dots or "pixels" with each pixel defined by a numeric value that gives its color. The number of different colors in a digital image is given by the number of bits assigned to each pixel. The common "color resolutions" are 1 bit per pixel for solid black-and-white nonrealistic images, 8 bits per pixel for grayscale images, nonrealistic color images and coarse realistic images, 24 bits per pixel for "photographic quality" of realistic images and 48 bits per pixel is used for ultrahigh quality images. An image stored in an uncompressed file format, such as the popular BMP format, usually occupies huge memory space. An image with a pixel resolution of 640 by 480 pixels and 24-bit color resolution will take up 640 * 480 * 24/8 = 921,600 bytes in an uncompressed format. Therefore compression of still image files has become a necessity. The increased use of digitized images, particularly on the Internet, has led to the need to compress such images to allow economical storage and fast data transfer. 2 In the field of digital image compression, many different techniques have been utilized, such as the JPEG (Joint Photographic Experts Group) standard, Wavelet Transform Compression, Fractal Image Compression, Vector Quantization and the like. In particular, the method known as JPEG and the recent update known as JPEG2000 have become industry standards. In the basic JPEG method, an image is transformed into a luminance/chrominance color representation conventionally denoted as YUV or YCbCr, where Y is a primary color or luminance component and U and V or Cb and Cr are secondary color components. By averaging together groups of pixels, the number of secondary components stored is reduced. The pixel values for each component are grouped into blocks and each block is transformed by a discrete cosine transform (DCT). In each block, the resulting DCT coefficients are quantized, that is divided by a predetermined quantization coefficient and rounded to integers. The quantized coefficients are encoded based on conditional probability by Huffman or arithmetic coding algorithms known in the art. A normal interchange JPEG file includes the compression parameters, including the quantization tables and encoding tables, in the file headers so a decompression program can reverse the process. The major problems in JPEG compression include a moderate compression ratio, a block effect, and poor progressive image quality. JPEG 2000 standard is designed to overcome some of the drawbacks of JPEG standard. JPEG2000 standard is an ISO/IEC standard (ISO/IEC 15444-1:2004) for efficient image compression of digital images. In JPEG 2000 standard, the whole image is divided into one or more image tile components; each of these image tile components are then 2-D discrete 3 wavelet transformed using 2-D discrete wavelet transformation. The transform coefficients of each image tile component are then grouped into sub-bands, these sub-bands are further partitioned into rectangular code blocks, each of the code blocks is entropy encoded. The uncompressed RAW image, which is input sample data, is fed to a pre-processor. The preprocessor block has an encoder. The encoder transforms the range of the input sample data to a nominal dynamic range so that it is approximately centered about zero. If the input sample data is +/ -, then it is assumed they are centered at zero. Otherwise, the absolute sample values in each component are level shifted (DC offset) by subtracting a fixed value from each sample to make its value symmetric around zero. Then the discrete wavelet transform (DWT) is applied in each tile to decompose it into a number of wavelet sub-bands at different levels and resolutions. DWT is an important process to generate resolution-salable (resolution-scalable) bit streams and decompose the spatial correlation. The output of this stage is a set of transformed coefficients. These transformed coefficients are then quantized. Quantization is used only in lossy compression. The wavelet coefficients in each sub-band are scalar quantized. The quantization step size is calculated based on the dynamic range of the sub band values and constants defined in the standard. The purpose of quantization is to reduce the precision of the sub band coefficients so that fewer bits will be needed to encode the transformed coefficients. The encoding phase is divided into two steps Tier-1 and Tier-2 coding. The Tier-1 coding is responsible for compressing the coefficient data into a byte stream. The Tier-2 coding consists of Rate Control and Packeting, which is 4 responsible for trimming and organizing this byte stream into a JPEG2000 compliant File format. Rate control is an important feature provided by JPEG2000 standard. This feature allows an encoder to compress a given image file to a specified target file size, ensuring that this size limit is not exceeded and maximum visual information is packed within. This requires computation of what information is more important visually and what is less, what is to be included in the given file size and what is to be truncated. The standard rate control scheme used in JPEG2000 calculates the slope as below: RD Slope = (22b x Rlvl_synw2 x Band-synw2 x NMSE_redc) / AR Where, RD Slope: is the ratio of Distortion and rate b : is the bit plane number to which the current truncation point belongs Rlvl_synw: is a value of synthesis weight for the selected wavelet filter depending on the current resolution level to which the code block belongs. Band_synw: is a value of synthesis weight for the selected wavelet filter depending on the current sub-band to which the code block belongs. NMSE_redc: is a coefficient value computed based on information content in each coding pass and gives an estimate of mean squared error that would result if this coding pass is not included. 5 AR : is the difference in byte count from previous truncation point of code block up to current truncation point for the code block. This is followed by the Newton- Raphson iterative method to find the best-fit element. All the elements are sorted based on their slopes and then checked if including half of them exceeds the specified limit or not. If it does, then one fourth of these elements are taken and same check is performed, else three fourth of these elements are taken and the check is performed. This process is repeated until it finds the best fit. This computation is called Rate-Distortion Analysis and is handled in the last stage of the encoder namely packeting. Tier-2 coder operates on the compressed information of every block to arrange their contributions in each quality layer, in a process referred to as packetization. Packeting involves assembling of the final Code-stream in a standard defined file format, which complies with any standard JPEG2000 qualified decoder. Conventionally, rate distortion is computed for all independent data blocks. It then uses an iterative method for computing a threshold and including the required information and checking for the target file size limit. The disadvantage of this method is that it drastically increases the computation effort and the time required, thereby making it almost impossible for hardware implementation. 6 An object of the present invention is to overcome the disadvantages of conventional method of digital image compression described before. Another object of this invention is to provide a non-iterative, computationally efficient and hardware friendly system for rate allocation for digital image compression. Another object of this invention is to reduce the time required for digital image compression. Summary of the invention: According to this invention, there is provided a system of rate allocation in a standard JPEG2000 processing apparatus, the said apparatus consisting of: (i) a preprocessing block, for receiving uncompressed RAW image, having an encoder which transforms the range of the input sample data into a nominal dynamic range so that it is approximately centered about zero, if the input sample data is +/- it is assumed they are centered at zero, otherwise, the absolute sample values in each component are level shifted (DC offset) by subtracting a fixed value from each sample to make its value symmetric around zero; (ii) a forward wavelet transforming block for decomposing each tile into a number of wavelet sub-bands at different levels and resolutions and producing a set of transformed coefficients; (iii) a quantization block for calculating quantization step size based on the dynamic range of the sub band values and constants defined in the standard 7 and reducing precision of sub band coefficients in order to have fewer bits to encode the transformed coefficients; (iv) a tier-1 coder block for compressing the coefficient data into a byte stream; (v) a tier-2 coder means for trimming and organizing this byte stream into a JPEG2000 compliant File format, the said means comprising: (a) a rate control means comprising: (i) a means adapted to receive resolution level number, sub band number, bit plane number, coding pass number and byte count signal from the tier-1 coder, for calculating R-D slope, wherein, the Resolution level number providing information about which resolution level the current code block belongs, the Sub band number providing information about which band the current code block belongs, the Bit plane number providing . information on current bit plane, the byte count providing the number of the current compressed byte for the current code block and coding pass number providing information on current coding pass that is a part of process; for computing the R-D slope and storing it at the end of a given coding pass, which is to be performed for each truncation point of a code block; (ii) a means adapted to receive byte count, resolution level no, sub band no and code block no signal for sending the signal as input to the address translator; (iii) a means for translating addresses from logical memory to physical memory by generating addresses for both the code block data memory and the code block auxiliary info memory, enabling efficient utilization of memory; 8 (iv) a means for rate allocation adapted to accept as input a computed RD slope, end of coding pass, coding pass no, byte count, resolution level no, sub band no and code block no and the logical address of the truncation point of the current code block under process, said means comprising: (i) a means for comparing the slope of each code stream with threshold slope of the bucket; (ii) a means adapted to keep an account of the byte count of each bucket and the number of truncation points in each bucket; (iii) a means for comparing the total size limit with the cumulative bucket byte count and accordingly decides as to which bucket, when included, would exceed the specified size limit; (b) a packeting module means for assembling and producing the final code stream depending on the data and information received from the ■ rate control block. In accordance with one preferred embodiment of this invention the rate control means calculates the slope in the following manner: RD Slope = (22b x CSF (i)) / R Where, RD Slope : is the ratio of Distortion and rate b : is the bit plane number to which the current truncation point belongs CSF : is a look up table with coefficients that depend on filter type, sub-band type and resolution level 9 R : is the absolute byte count from starting of code block up to current truncation point for the current code block. In accordance with another preferred embodiment of this invention an address translator translates addresses from logical memory to physical memory in the following manner: Logical address: Resolution Level Number (0 - 7) represented using 3 bits Sub band Number (0-3) represented using 2 bits Code block Number (0 - 64) represented using 6 bits Byte count (0 -1008) represented using 10 bits Physical address: Base address: Resolution 3 bits Subband 2 bits Code block 6 bits 10 bits all zero Code block Auxiliary Info: Base address + value from 0 to 16 (represented using 10 bits) Code block data: Base address + 16 + Byte count (represented using 10 bits) Other aspects and advantages of the present invention will become apparent upon reading the following detailed description and upon reference to the drawings, which are illustrative only and in anyway do not limit the scope of the invention. 10 Brief Description of the accompanying drawings: In the accompanying drawings: Figure 1 illustrates the block diagram of a JPEG2000 encoder; Figure 2 illustrates the internal block diagram of the tier-2 coding system for achieving rate control; Figure 3 illustrates the internal block diagram of the rate allocator; and Figure 4 illustrates the state diagram of the entire operation of the rate allocator. Detailed description of the accompanying drawings: The invention will now be explained with reference to the figures 1 to 4 of the accompanying drawings. Figure 1 illustrates the block diagram of a JPEG2000 encoder. The JPEG2000 encoder consists of: (i) a preprocessing block, for receiving uncompressed RAW image, having an encoder which transforms the range of the input sample data into a nominal dynamic range so that it is approximately centered about zero, if the input sample data is +/- it is assumed they are centered at zero, otherwise, the absolute sample values in each component are level shifted (DC offset) by subtracting a fixed value from each sample to make its value symmetric around zero; (ii) a forward wavelet transforming block for decomposing each tile into a number of wavelet sub-bands at different levels and resolutions and producing a set of transformed coefficients; 11 (iii) a quantization block for calculating quantization step size based on the dynamic range of the sub band values and constants defined in the standard and reducing precision of sub band coefficients in order to have fewer bits to encode the transformed coefficients; (iv) a tier-1 coder block for compressing the coefficient data into a byte stream; (v) a tier-2 coder means for trimming and organizing this byte stream into a JPEG2000 compliant File format, the tier-2 coder comprises: (a) a rate control means; and (b) a packeting module means for assembling and producing the final code stream depending on the data and information received from the rate control block. Figure 2 illustrates the internal block diagram of the tier-2 coding system for achieving rate control. The tier-2 coding system comprises: (i) a rate control means comprises: (i) a means adapted to receive resolution level number, sub band number, bit plane number, coding pass number and byte count signal from the tier-1 coder, for calculating R-D slope, wherein, the Resolution level number providing information about which resolution level the current code block belongs, the Sub band number providing information about which band the current code block belongs, the Bit plane number providing information on current bit plane, the byte count providing the number of the current compressed byte for the current code block and coding pass number providing information on current coding pass that is under process; as shown in figure 3, for computing the R-D slope and storing it at the end of a 12 given coding pass, which is to be performed for each truncation point of a code block; (ii) a means adapted to receive byte count, resolution level number, sub band number and code block number signal for sending the signal as input to the address translator; (iii) a means for translating addresses from logical memory to physical memory by generating addresses for both the code block data memory and the code block auxiliary info memory, enabling efficient utilization of memory; (iv) a means for rate allocation adapted to accept as input a computed RD slope, end of coding pass, coding pass number, byte count, resolution level number, sub band number and code block number and the logical address of the truncation point of the current code block under process, (ii) a packeting module means for assembling and producing the final code stream depending on the data and information received from the rate control block. Figure 3 illustrates the internal block diagram of the rate allocator. The rate allocator comprises: (a) a means for comparing the slope of each code stream with threshold slope of the bucket; (b) a means adapted to keep an account of the byte count of each bucket and the number of truncation points in each bucket; (c) a means for comparing the total size limit with the cumulative bucket byte count and accordingly decides as to which bucket, when included, would exceed the specified size limit; 13 The rate control means calculates the slope in the following manner: RD Slope = (22b x CSF (i)) / R Where, RD Slope : is the ratio of Distortion and rate b : is the bit plane number to which the current truncation point belongs CSF : is a look up table with coefficients that depend on filter type, sub-band type and resolution level R : is the absolute byte count from starting of code block up to current truncation point for the current code block. The means for comparing the slope of each code stream with threshold slope of the bucket is a bucket selection comparator, if the slope is greater than the threshold value it allocates that truncation point to the corresponding bucket, otherwise it goes for comparison with the next bucket. The means for comparing the total size limit with the cumulative bucket byte count is an allocator and sorter, if the byte size of all the buckets added is less than the size limit, these buckets are then blindly included and if the inclusion of a bucket exceeds size limit, then the bucket is sorted and the elements from it are included until the desired file size is obtained. Figure 4 illustrates the state diagram of the entire operation of the rate allocator. The states and the steps performed in each state are given below: 14 State SI: Wait State 1. Waits while a code block is being processed by Bit plane coder. 2. The state exits when the end of a coding pass is reached. State S2: Capture State 1. Capture the current value of the RD slope 2. Capture the logical address of the code block truncation point including the current coding pass number. State S3: Bucketing State 1. Compare the current RD slope with threshold value of each bucket 2. Store the bucket element in the selected bucket 3. Increment the Bucket element count 4. Increment the Bucket byte count 5. Check if all code blocks are completed State S4: Initialization State 1. Initialize current bucket number n = 1 2. Total bytes = 0 3. Get current Byte limit 4. Initialize all code block lengths = 0 State S5: Find bucket to be sorted State 1. Cut off bucket = Total bytes + Bucket byte count (n) > Byte limit 2. Check cut off bucket value 15 State S6: Add Bucket without Sorting State 1. For each element of the bucket n a. Add bytes corresponding to current truncation point of code block to its length b. Update corresponding number of coding passes included. 2. n++ State S7: Add Bucket with Sorting State 1. For each element of the bucket n starting from top a. Perform bubble sort for current element using RD Slope value b. Check if (Total bytes + bytes to be added c. If Yes then i. Add bytes corresponding to current truncation point of code block to its length ii. Update corresponding number of coding passes included. d. Else i. Break and go to S8 State S8; Completed State Signal Packeting Module to start forming Code stream While considerable emphasis has been placed herein on the various components of the preferred embodiment, it will be appreciated that many alterations can be made and that many modifications can be made in the preferred embodiment without departing from the principles of the invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the 16 art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation. Dated this 16™ day of March, 2006. 17

Documents:

382-MUM-2006-ABSTRACT(18-12-2013).pdf

382-MUM-2006-ABSTRACT(19-2-2013).pdf

382-mum-2006-abstract(9-3-2007).pdf

382-mum-2006-claims(9-3-2007).pdf

382-MUM-2006-CLAIMS(AMENDED)-(18-12-2013).pdf

382-MUM-2006-CLAIMS(AMENDED)-(19-2-2013).pdf

382-MUM-2006-CORRESPONDENCE(20-2-2013).pdf

382-mum-2006-correspondence(25-4-2008).pdf

382-mum-2006-description (provisional).pdf

382-mum-2006-description(complete)-(9-3-2007).pdf

382-mum-2006-drawing(9-3-2007).pdf

382-mum-2006-drawings.pdf

382-mum-2006-form 18(25-4-2008).pdf

382-mum-2006-form 2(9-3-2007).pdf

382-MUM-2006-FORM 2(TITLE PAGE)-(18-12-2013).pdf

382-MUM-2006-FORM 2(TITLE PAGE)-(19-2-2013).pdf

382-mum-2006-form 2(title page)-(complete)-(9-3-2007).pdf

382-mum-2006-form 2(title page)-(provisional)-(17-3-2006).pdf

382-MUM-2006-FORM 26(20-2-2013).pdf

382-mum-2006-form 3(16-5-2007).pdf

382-mum-2006-form 5(9-3-2007).pdf

382-mum-2006-form-1.pdf

382-mum-2006-form-2.doc

382-mum-2006-form-26.pdf

382-mum-2006-form-3.pdf

382-mum-2006-forn-2.pdf

382-MUM-2006-MARKED COPY(18-12-2013).pdf

382-MUM-2006-MARKED COPY(19-2-2013).pdf

382-MUM-2006-POWER OF ATTORNEY(18-12-2013).pdf

382-MUM-2006-REPLY TO EXAMINATION REPORT(19-2-2013).pdf

382-MUM-2006-REPLY TO HEARING(18-12-2013).pdf

382-MUM-2006-SPECIFICATION(AMENDED)-(18-12-2013).pdf

382-MUM-2006-SPECIFICATION(AMENDED)-(19-2-2013).pdf

382-MUM-2006-US DOCUMENT(19-2-2013).pdf

abstract1.jpg