`
`(12) United States Patent
`Molgaard et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7.656,561 B2
`Feb. 2, 2010
`
`(54) IMAGE COMPRESSION FOR RAPID
`HIGH-QUALITY IMAGING
`(75) Inventors: Claus Molgaard, Naerum (DK);
`Thomas Alexander Rogon, Virum
`(DK); Thomas Andersen, Glumso (DK)
`(73) Assignee: Phase One A/S, Frederiksberg (DK)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 685 days.
`(21) Appl. No.: 10/865,748
`
`(22) Filed:
`
`Jun. 14, 2004
`
`(65)
`
`Prior Publication Data
`US 2005/0276496 A1
`Dec. 15, 2005
`
`Foreign Application Priority Data
`(30)
`May 31, 2004 (DK) ............................... 2004 OO846
`
`(51) Int. Cl.
`(2006.01)
`H04N I/4I
`(52) U.S. Cl. ............................ 358/426.01: 358/426.13;
`382/232: 382/244
`(58) Field of Classification Search ................. 382/162,
`382/166, 232, 233,238,239, 244, 245, 246,
`382/248,250; 358/426.01, 426.13, 426.14,
`358/539
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`4,958,235 A * 9/1990 Sims et al. .................. 358/402
`5,553,200 A
`9, 1996 Accad ........................ 358/19
`6,097.838 A
`8/2000 Klassen et al.
`6,614.483 Bl
`9, 2003 Lee et al.
`6,694,061 B1* 2/2004 Acharya ..................... 382/251
`6,744,929 B1
`6, 2004 Okada
`
`2002fOO41761 A1
`2002/0044778 A1
`2003,0222996 A1
`2004/OOO8896 A1
`
`4/2002 Glotzbach et al.
`4/2002 Suzuki
`12/2003 Pate
`1/2004 Suzuki
`
`FOREIGN PATENT DOCUMENTS
`
`DE
`
`10254 192 A1
`
`9, 2003
`
`(Continued)
`OTHER PUBLICATIONS
`S. Battiato et al.; Coding Techniques for CFA Data Images; Proceed
`ings of the 12th International Conf. on Image Analysis and Process
`ing: 2003: IEEE.
`Toi et al., A Subband Coding Techniqui for Image Compression in
`Single CCDE Cameras With Bayer Color Filter Arrays; IEEE Trans
`actions on Consumer Electr; vol. 45, Feb. 1999.
`(Continued)
`Primary Examiner Thomas D Lee
`(74) Attorney, Agent, or Firm Volentine & Whitt, P.L.L.C.
`(57)
`ABSTRACT
`
`Lossless, near-lossless, and lossy compression and decom
`pression of digital image data, whereby the image data can be
`compressed and decompressed on-the-fly with no need for
`external RAM resources for temporary data storage while
`compressing/decompressing image data. Implementing the
`algorithm only requires a very limited amount of silicon and
`yields very high performance in relation to very low power
`consumption. The described implementation is optimized for
`raw image data from a sensor with a Bayer filter pattern but
`can be used on data from image sensors with ay color filter.
`The compression algorithm contains a line indexing forma
`tion which enables very fast Subsampling of an already com
`pressed image and the possibility to decompress only parts of
`an image—this improves performance and reduces the need
`for temporary RAM storage greatly when Zooming and in
`postprocessing.
`
`10 Claims, 7 Drawing Sheets
`
`Lossess compression
`
`
`
`APPLE v. RED.COM
`
`Page 1 of 18
`
`Apple Ex. 1006
`
`
`
`US 7,656,561 B2
`Page 2
`
`FOREIGN PATENT DOCUMENTS
`O 469836 A2
`7, 1991
`1173 005 A2 12/2000
`2000244935
`11, 1999
`WOOOf75859 A1 12/2000
`
`EP
`EP
`JP
`WO
`
`OTHER PUBLICATIONS
`Koh et al.; New Efficient Methods of Image Compression in Digital
`Cameras With Color Filter Array; IEEE Transactions on Consumer
`Electronics, vol. 49, No. 4, Nov. 2003.
`* cited by examiner
`
`APPLE v. RED.COM
`
`Page 2 of 18
`
`Apple Ex. 1006
`
`
`
`U.S. Patent
`
`Feb. 2, 2010
`
`Sheet 1 of 7
`
`US 7,656,561 B2
`
`
`
`
`
`RAW image data
`
`Image
`Calibration
`
`
`
`Image
`interpolation and
`enhancement
`
`Discrete COSine
`transformation
`
`Quantizer
`
`Quantization
`matrix
`
`Entropy encoder
`
`Coding table
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig. 1 (PRIOR ART)
`
`APPLE v. RED.COM
`
`Page 3 of 18
`
`Apple Ex. 1006
`
`
`
`U.S. Patent
`
`Feb. 2, 2010
`
`Sheet 2 of 7
`
`US 7,656,561 B2
`
`Lossless compression
`
`
`
`RAW image data
`
`Black reference
`ill---
`Black calibration - buffer
`
`
`
`
`
`
`
`
`Preconditioning
`
`Info about:
`ISO
`Integration time
`Noise level
`Gain
`
`Encoding
`Schemes
`
`Stream generation
`
`Line byte Count
`
`Separate index
`table
`
`
`
`
`
`
`
`
`
`
`
`Storage or transmission
`
`Fig. 2A
`
`APPLE v. RED.COM
`
`Page 4 of 18
`
`Apple Ex. 1006
`
`
`
`U.S. Patent
`
`Feb. 2, 2010
`
`Sheet 3 of 7
`
`US 7.656,561 B2
`
`Near-lossless compression
`
`RAW image data
`
`Black calibration H
`Black reference
`buffer
`
`info about:
`SO
`"Sit,ge
`Gain
`
`
`
`Preconditioning
`
`Gamma correction
`
`Bit reduction
`
`Clustering
`
`Prediction
`
`Encoding
`schemes
`
`Stream generation
`
`Line byte count
`
`Separate index
`table
`
`
`
`Storage or transmission
`
`Fig. 2B
`
`APPLE v. RED.COM
`
`Page 5 of 18
`
`Apple Ex. 1006
`
`
`
`U.S. Patent
`
`Feb. 2, 2010
`
`Sheet 4 of 7
`
`US 7.656,561 B2
`
`12
`
`
`
`
`
`
`
`
`
`Image
`SenSO
`
`
`
`SenSOr
`Temp.
`sensor settings
`
`
`
`
`
`11
`
`
`
`
`
`15
`
`
`
`
`
`
`
`Storage
`and/or
`transmission
`
`
`
`Fig. 3
`
`Analog
`amplifier
`
`13
`
`14
`
`1.O
`
`
`
`
`
`
`
`Compression
`section
`
`Calibration block
`
`Preconditioning block
`
`Bit-reduction block
`
`Prediction block
`Processor
`
`Encoding block
`Processor
`
`
`
`Indexing block
`
`APPLE v. RED.COM
`
`Page 6 of 18
`
`Apple Ex. 1006
`
`
`
`U.S. Patent
`
`Feb. 2, 2010
`
`Sheet 5 of 7
`
`US 7,656,561 B2
`
`CD
`D
`CD
`-
`C
`()
`O
`O
`
`D
`
`c)
`h
`
`O
`O
`
`O)
`()
`C
`()
`s
`C
`()
`C
`O
`
`Pixel Value
`Fig. 4
`
`Pixel value
`Fig. 5
`
`Pixel value
`Fig. 6
`
`APPLE v. RED.COM
`
`Page 7 of 18
`
`Apple Ex. 1006
`
`
`
`U.S. Patent
`
`Feb. 2, 2010
`
`Sheet 6 of 7
`
`US 7,656,561 B2
`
`Pixel values
`Fig. 7
`
`Fig. 8
`
`R G R
`
`G
`
`R G
`
`R
`
`G
`
`
`
`
`
`APPLE v. RED.COM
`
`Page 8 of 18
`
`Apple Ex. 1006
`
`
`
`U.S. Patent
`
`Feb. 2, 2010
`
`Sheet 7 Of 7
`
`US 7.656,561 B2
`
`
`
`Image Sensor array
`
`Fig. 10
`
`APPLE v. RED.COM
`
`Page 9 of 18
`
`Apple Ex. 1006
`
`
`
`US 7,656,561 B2
`
`1.
`IMAGE COMPRESSION FOR RAPID
`HIGH-QUALITY IMAGING
`
`FIELD OF INVENTION
`
`The present invention relates to lossless or reversible, near
`lossless, and lossy compression and decompression of digital
`image data. In particular, the invention relates to (de).com
`pressing image data on-the-fly with no need for external
`RAM (Random Access Memory) resources for temporary
`data storage.
`
`BACKGROUND OF THE INVENTION
`
`Image resolution is ever increasing and so are the accom
`panying frame rates. All in all this results in increasing
`demands to system bandwidths, transporting media band
`width as well as storage capacity of both temporary storage
`(e.g. RAM) and permanent storage (e.g. HDD (Hard Disc
`Drive)). The strains on all these function blocks will be
`reduced if image data is compressed. Historically memory
`and permanent storage media bandwidths have not been
`increasing as rapidly as data processing means, which indi
`cates that using on-the-fly image compression will yield
`much higher system performance than just adopting techno
`logical improvements in memory and permanent storage
`bandwidths. The higher performance can also be traded in for
`lower system costs, as less memory and permanent storage is
`required. Along with this, lower performance memory and
`storage means can be used. Another benefit, particular in
`portable products, is the ability to reduce power consumption
`as the power needed for the image compression can be much
`less than that required by additional memory and additional
`permanent Storage.
`Prior solutions based on industry standards like JPEG
`(Joint Photographic Experts Group), require a lot of silicon to
`be implemented in hardware and are often too slow when
`implemented in Software—this is particular the case if the
`bit-depth of pixels increase from the traditional 8 bits per
`color to e.g. 16 bits per color. Today the higher bit-depths are
`a natural thing in high-end digital imaging. This improves the
`colorfidelity and enables more advanced image processing to
`be applied in order to obtain more satisfactory results than
`previously accepted. If JPEG or similar compression algo
`rithms are used, the RAW image data must be fully calibrated,
`interpolated, and enhanced prior to the compression itself,
`this is outlined in the block diagram of FIG.1. This increases
`the complexity and cost of the system and reduces the ability
`to generate high-quality images, as a lot of image enhance
`ment is required for optimum results, sometimes in combi
`nation with user interaction. Vast amounts of processing
`resources are normally not present in portable devices like
`digital cameras. Accordingly, improvements are needed in the
`processing of image data.
`EP 1 173 005 describes a method for compressing raw
`color image data by mapping different color planes into
`square sections and compressing these independently. The
`decompressed file must then be re-mapped to restore the
`original pattern of the color image data.
`U.S. Pat. No. 6,614.483 describes a method for providing a
`simple lossy image compression. The method compresses
`image data in a lossy manner by dividing down pixel values
`by a loss factor and thereby creating an evenly distributed
`linear loss in the pool of image data. From an image-quality
`point of view, it is a disadvantage that this approach will
`increase the amount of digital noise in the darker areas of the
`resulting decompressed image as presented on either paperor
`
`2
`a computer monitor. The reason being that image processing
`for preparing data for a more appropriate appearance requires
`multiplying image data with a gamma function.
`In U.S. Pat. No. 6,614.483, the described algorithm also
`needs data to be handled by a color extraction unit prior to the
`actual compression. This color extraction unit performs a
`very simple pixel interpolation to generate red, green, and
`blue values for each pixel. This instantly reduces the possi
`bility of generating a high quality image at a later stage.
`The variable length (VL) encoding described in U.S. Pat.
`No. 6,614.483 is based on a combination of 1s complement
`VL encoding with leading “Zero” and “one' detection. This
`form of encoding works well with image data with low color
`bit-depth (e.g. 8 bits), but often yields poor results when used
`with image data with high color bit-depth (e.g. 16 bits) and a
`relatively high amount of entropy, which are all characteris
`tics for high-quality imaging.
`Another limitation of the implementation described in U.S.
`Pat. No. 6,614.483 is that it requires an external or internal
`buffer to hold at least two adjacent lines of image data to be
`able to do simple color interpolation. With high resolution
`image sensors, the required amount oftemporary storage can
`be quite high and thereby increase system cost if the buffer is
`implemented together with the block that carries out the com
`pression itself. Using cheaper external storage (e.g. Dynamic
`RAM, DRAM) will often be unacceptable from a perfor
`mance point of view.
`
`SUMMARY OF THE INVENTION
`
`The invention provides on-the-fly compression and
`decompression of digital image data. The invention requires
`no external RAM resources for temporary data storage while
`compressing or decompressing image data. In the present
`context, on-the-fly means that data is processed, here com
`pressed or decompressed, at the same rate as it is input to the
`relevant section.
`In high quality digital imaging, an important feature is to
`get the recorded data stored or transmitted as fast as possible
`to make the camera ready for the next exposure as fast as
`possible.
`It is an object of the present invention to provide a method
`and an apparatus for performing fast on-the-fly compression
`of image data to generate Small compressed image data files
`which can be stored and/or transmitted cheaply and effi
`ciently.
`The professional photographer requires total control of the
`processing of image data, since different processing tools are
`preferred for different jobs. Image data which have not been
`processed prior to compression, e.g. by color interpolation,
`give Smaller image data files which can be compressed and
`stored or transmitted faster.
`It is another object of the present invention to provide a
`method and an apparatus for compressing raw image data in
`order to reduce the size of the compressed image data files.
`The method and apparatus may include the feature of cali
`brating the raw data for inherent noise and artifacts of the
`CaCa.
`Lossy compression gives even Smaller compressed image
`data files, and allows for even faster and cheaper handling of
`files. but also deteriorates the quality of the decompressed
`image. In the present invention, near-lossless compression is
`implemented using a gamma function to provide a compres
`sion that is visually lossless as it only affects image data in the
`same manner as the later image postprocessing, e.g. in rela
`tion to presenting recorded images on a monitor or a printout.
`Such postprocessing always applies a gamma curve to con
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`APPLE v. RED.COM
`
`Page 10 of 18
`
`Apple Ex. 1006
`
`
`
`US 7,656,561 B2
`
`10
`
`15
`
`3
`Vert the linear response of the image sensor to a more loga
`rithmic response which is used to ensure that the final result
`looks correct when displayed on a monitor or another output
`device such as a printer. By deliberately reducing bits whose
`significance will later be Suppressed in presenting the image,
`no noticeable loss is introduced, such reduction is called
`near-lossless. The process simply removes data which would
`anyway later be removed by the final image enhancement
`processing prior to presentation. In the present invention, the
`gamma curve has a built in bit reduction function which
`preserves maximum amount of information for the lower
`values whereas higher values will contain larger errors. This
`is not visible in the final image as the same kind of bit
`reduction is always applied to the final processed image.
`It is still another object of the present invention to provide
`a method and an apparatus for performing a near-lossless
`compression of image data by performing a gamma correc
`tion and a bit reduction prior to compression. A correspond
`ing inverse gamma correction is to be performed when
`decompressing the data.
`In predicting pixel values, one is often left with the choice
`between prediction accuracy and speed. Advanced prediction
`algorithms can give less prediction errors and thereby
`increase the compression rate, as fewer errors need to be
`encoded and stored. Simpler prediction routines are faster
`with poorer predictions, especially for image data with much
`variation, resulting in Smaller compression rates. According
`to the invention, speed has a high priority since image data is
`compressed on-the-fly. The inventors of the present invention
`have realized that an efficient statistical encoding routine can
`compensate for the poorer predictions of a simple prediction
`routine, thereby increasing the compression speed without
`significant reduction in compression rate.
`Hence, it is yet another object of the present invention to
`provide a method and an apparatus applying a simple, fast
`prediction routine and an improved encoding routine adapted
`to efficiently encode the larger prediction errors of the simple
`prediction routine.
`In order to fulfill the above objects, the present invention
`provides, in a first aspect, a method for lossless on-the-fly
`compression of raw digital image data from an image sensor,
`the method comprising:
`receiving information relating to at least sensor integration
`time, sensor temperature and analog and digital gain of
`45
`image data, if applied;
`receiving raw digital image data comprising a plurality of
`pixel values in one or more color planes from the image
`Sensor,
`adjusting a pixel value distribution of the received raw
`image data to precondition the data for compression by
`applying again to the pixel values, the gain being at least
`partly determined by the received information:
`providing two or more prediction routines for predicting
`pixel values for pixels in clusters of neighboring pixels
`using other pixel values in the cluster;
`Selecting, using the received information, a cluster size and
`an appropriate prediction routine for the image data or
`for each cluster;
`generating pixel prediction errors by, for each cluster and
`each color plane,
`predicting pixel values using the selected prediction rou
`tine, the pixel prediction error being derived from the
`difference between the predicted pixel value and the
`preconditioned pixel value,
`evaluating an entropy figure for the each cluster;
`
`55
`
`4
`providing two or more statistical encoding schemes, each
`determining codes and corresponding code lengths for
`pixel prediction errors of a cluster;
`encoding the pixel prediction errors of each cluster by, for
`each color plane,
`using the entropy figure and the received information to
`determine and select an appropriate statistical encod
`ing scheme for the color plane of the cluster, and
`encoding the pixel prediction errors and the entropy of
`the cluster according to the selected Statistical encod
`ing scheme; and
`evaluating a length of the bit-stream corresponding to each
`line of the image, and appending the length to the bit
`stream corresponding to the line and/or storing the
`length in an index table.
`Preferably, the method further comprises processing the
`image data to compensate for inherent noise and errors of the
`image sensor prior to generating pixel prediction errors.
`Preferably, the entropy figure of a cluster is evaluated to
`reflect the difference between maximum and minimum pixel
`values in the cluster and a variation of pixel values in the
`cluster. To make the prediction simpler and faster, the clusters
`used in predicting pixel values are preferably fixed-size, one
`dimensional cluster, Such as having a fixed size of 8x1 pixels.
`In a second aspect, the invention provide a method for
`near-lossless on-the-fly compression of raw digital image
`data from an image sensor, the method comprising:
`receiving information relating to at least sensor integration
`time, sensor temperature and analog gain of image data,
`if applied, from the image sensor,
`receiving raw digital image data comprising a plurality of
`pixel values in one or more color planes from the image
`Sensor,
`adjusting a pixel value distribution of the received raw
`image data to precondition the data for compression by
`applying again to the pixel values, the gain being at least
`partly determined by the received information:
`gamma correcting the pixel values of the image data;
`reducing one or more of the least significant bits of the
`gamma corrected pixel values;
`generating pixel prediction errors by, for each color plane,
`predicting pixel values for pixels inclusters of neighbor
`ing pixels using other pixel values in the cluster, the pixel
`prediction error being derived from the difference
`between the predicted pixel value and the precondi
`tioned pixel value,
`encoding the pixel prediction errors of each cluster
`evaluating a length of the bit-stream corresponding to each
`line of the image, and appending the length with the
`bit-stream corresponding to the line and storing the
`length in an index table.
`The unique feature of gamma correcting the image data
`prior to bit-reduction and compression naturally requires that
`a reverse gamma correction be carried out before presenting
`the data with normal techniques, as that typically also
`involves a gamma correction. Hence, according to a third
`aspect, the invention provides a method for decompressing
`image data, the method comprising:
`decoding encoded pixel prediction errors using one or
`more statistical encoding schemes applied at compres
`sion;
`calculating pixel values using the decoded pixel prediction
`errors and a prediction routine applied at compression;
`and
`performing a reverse gamma correction of the calculated
`pixel values.
`
`25
`
`30
`
`35
`
`40
`
`50
`
`60
`
`65
`
`APPLE v. RED.COM
`
`Page 11 of 18
`
`Apple Ex. 1006
`
`
`
`US 7,656,561 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`5
`High quality image files are typically extremely large, typi
`cally several hundred megabytes. With the presently available
`computing power, processing of the entire image may there
`fore be a heavy and time-consuming burden. Therefore, the
`present invention provides the possibility to retrieve only
`specific parts of a compressed image for post-processing,
`thereby significantly reducing the file-size and the processing
`burden. Hence, the method for decompressing preferably
`comprises, prior to the decoding:
`providing indexed compressed image data where the
`indexed parts are suitable for Subsampling, Zooming,
`panning, and cropping; and
`using an embedded line index table or a separate line index
`table to identify indexed parts selected for decompres
`sion.
`The methods according to the first and second aspects may
`be implemented in either software or hardware. According to
`a fourth and fifth aspect, the methods are implemented in
`Software, and the invention provides electronic storage media
`storing software for use by a digital image processor in com
`pressing digital image data from an image sensor, the Soft
`ware being executed by the digital image processor in per
`forming the method steps of the first or the second aspect.
`According to a third aspect, the methods are implemented
`in hardware, and the invention provides an image compres
`sion section for compressing digital image data, the section
`being connected to a digital imaging apparatus to receive
`information relating to at least a sensor integration time, a
`sensor temperature and analog gain of image data, if applied,
`and raw digital image data comprising a plurality of pixel
`values in one or more color planes, the compression section
`holding gamma correction data, at least two prediction rou
`tines for predicting pixel values for pixels inclusters of neigh
`boring pixels using other pixel values in the cluster, and at
`least two statistical encoding schemes each determining
`codes and corresponding code lengths for pixel prediction
`errors of a cluster, the compression section comprising:
`a preconditioning block connected to receive the raw digi
`tal image data and to adjust a pixel value distribution of
`the received data to precondition the data for compres
`40
`sion by applying again to the pixel values, the gain being
`at least partly determined by the received information;
`a bit-reduction block to perform a gamma correction of the
`pixel values according to the gamma correction data and
`reducing the number of bits for each gamma corrected
`pixel value;
`a prediction block connected to receive the preconditioned
`data to generate pixel prediction errors using a selected
`prediction routine, the prediction block comprising pro
`cessing means for, for each cluster and each color plane,
`predicting pixel values using the selected prediction rou
`tine, the pixel prediction error being derived from the
`difference between the predicted pixel value and the
`preconditioned pixel value,
`evaluating an entropy figure for each cluster;
`an encoding block to encode the pixel prediction errors of
`each cluster, the encoding block comprising processing
`means for, for each cluster and each color plane, encod
`ing the pixel prediction errors and the entropy of the
`cluster using a selected Statistical encoding scheme; and
`an indexing block to evaluate a length of the bit-stream
`corresponding to each line of the image, and appending
`the length with the bit-stream corresponding to the line
`and storing the length in an index table in a memory.
`The method may be carried out by an algorithm imple
`mented in Software and/or hardware. Implementing the algo
`rithm in hardware only requires a very limited amount of
`
`50
`
`45
`
`55
`
`60
`
`65
`
`6
`silicon and yields very high performance in terms of process
`ing speed particular when seen in relation to the very low
`power consumption.
`The compression algorithm contains a line indexing format
`which enables very fast Subsampling of an already com
`pressed image. Line indexing is used to enable rapid subsam
`pling of compressed image. It also improves error correction
`since an error in the compressed stream of data will only
`affect one line. The line indexing can be embedded in the
`compressed stream as well as in a separate file. Placing the
`indexing file in a separate file improves performance if the
`compressed file must be subsampled or Zoomed into straight
`from a slow media like a HDD, flash based media or the like.
`If the indexing file is only embedded within the compressed
`stream it is necessary to read the entire compressed file into
`memory in order to extract the indexing information. As the
`indexing file is very small compared to a the size of a com
`pressed high resolution image, it is a small penalty to pay in
`terms of extra required storage space, compared to the per
`formance benefits gained when working with the compressed
`files. The line-indexing format makes it possible to only
`decompress the parts of an image which of interest. This
`improves performance and reduces the need for temporary
`RAM storage greatly when Zooming and doing other kinds of
`postprocessing with compressed image data.
`Raw image data means data containing only pixel values
`that have been read out from the image sensor. The data may
`be amplified and converted, but no new pixel values have been
`added to the data e.g. by color interpolation. The data may
`contain several values for each pixel if more than one value
`can be read out from pixels of the sensor. One type of image
`sensors (e.g. Foveon X3) may read out three values from each
`pixel corresponding to different wavelength intervals of the
`incident light. Since it is an object to get the data transmitted
`and stored as fast as possible there is no need for generating
`more data, and the present invention preferably operates with
`raw data. The compression algorithm may however be
`applied to interpolated data as well.
`As described previously, the invention preferably applies a
`fast and simplified prediction scenario. According to a pre
`ferred embodiment, one feature of the routine is that small,
`fixed-size, one-dimensional clusters are used in the prediction
`scenarios, e.g. a 1x8 cluster. This increases speed but may
`give rise to more and larger prediction errors, which is com
`pensated for by an efficient adaptive statistical encoding.
`The compression algorithm is adaptive as it uses informa
`tion about image sensor integration time, temperature, and
`gain to adjust the statistical encoder to optimum performance
`as well as adjusting the preprocessing gamma curve.
`In relation to the disadvantages of U.S. Pat. No. 6,614.483.
`the present invention provides the following advantages:
`A novel solution involving an adjustable loss-introducing
`stage for avoiding visual degradation of image data
`which have been compressed and decompressed.
`A compression algorithm without need for specific color
`extraction and interpolation prior to compression since
`the prediction is line based and utilizes the fact that every
`second pixel in a line will have the same color filter. The
`predictor or any other stage does not need to keep track
`of the position of the specific color filters—this results in
`a more efficient algorithm which yields higher perfor
`mance when implemented in Software and a smaller
`silicon footprint as well as higher performance when
`implemented in an ASIC/FPGA (Application Specific
`Integrated Circuit/Field Programmable Gate Array).
`
`APPLE v. RED.COM
`
`Page 12 of 18
`
`Apple Ex. 1006
`
`
`
`7
`The lossless and near-lossless nature of the present
`invention allows for high-quality image processing at a
`later stage.
`A line based compression scenario which reduces the need
`for external or internal buffer for temporary storage and
`thereby reduce cost and increase performance.
`The algorithm can easily be implemented in a way that
`makes it very suitable for image sensors with multiple out
`puts—the Small silicon footprint enables easy use of parallel
`image compression. Multiple image outputs may also be
`Supported by customizing the algorithm for a certain amount
`of input-channels.
`The lossless compression ratios which can be achieved
`with the present algorithm are almost as good as the ones
`which can be achieved with state-of-the-art arithmetic com
`15
`pression techniques—butata fraction of the complexity com
`pared to state-of-the-art arithmetic compression.
`
`10
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention will now be described with reference
`to the accompanying figures, where
`FIG. 1 shows the prior art.
`FIGS. 2A and B show block diagrams of two modes of the
`compression algorithm according to the invention.
`FIG. 3 shows an embodiment of a digital imaging system
`used to implement the method and algorithm according to the
`invention.
`FIG. 4 shows a histogram for ISO 100 raw image data.
`FIG. 5 shows a histogram for ISO1600 raw image data.
`FIG. 6 shows a histogram for gained ISO1600 raw image
`data.
`FIG. 7 shows an example of a gamma curve.
`FIG. 8 shows an 8x1-pixel cluster.
`FIG. 9 shows an 8x8-pixel cluster.
`FIG. 10 shows an example of a multiple output image
`SSO.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`The invention provides a digital imaging system having a
`compression section implementing an algorithm for lossless
`or near-lossless compressing high-quality image data. Corre
`sponding block diagrams of the algorithm are shown in FIGS.
`2A and B. The algorithm contains a novel structure which
`enables very fast on-the-fly compression of image data. The
`digital imaging system can be a digital camera back for a
`portable digital camera controlled by a camera operation
`system.
`In the following, an embodiment of the part of the image
`system related to the compression of images is described in
`relation to FIG. 3. The compression section 10 is positioned
`close to an image sensor 12, receiving data directly from the
`sensor 12 through analog amplifier 13 and analog-to-digital
`converter (ADC) 14. The compression section comprises a
`number of blocks and processors for performing various
`operations in relation to the compression, and is connected to
`a memory 11 holding routines, tables etc. to be used by the
`various blocks. The memory 11 may also be embodied by
`Smaller memories in connection to each block. The compres
`sion section directs the compressed image data file to a unit 15
`for storing or transmitting the file. The compression algo
`rithm implemented by the compression section 10 performs
`the compression according to a number of settings and
`parameters of the image sensor which affect the noise and
`statistics of the image data. This can be the integration time
`(or exposure/shutter time), sensor temperature, ISO setting
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,656,561 B2
`
`8
`and an applied analog gain of image data. Therefore, embodi
`ment shown in FIG. 3 include a unit 16 which keeps track of
`the settings of the image sensor as defined by the user and/or
`the camera operation system. Typically, the unit 16 forms part
`of the operation processor of the camera. The system also has
`a temperature sensor 17, this can also be controlled by the
`camera operation system. This information related to the
`image sensor is fed to the compression section and is used to
`predict the general noise level and statistics of the image data.
`The compression section 10 comprises a number of blocks
`corresponding to different stages of the algorithm. The com
`pression section and the block can be implemented by hard
`ware or software. The highest performance can be achieved
`by implementing the algorithm hardware (e.g. ASIC, FPGA)
`or software (using a processor Such as DSP Digital Signal
`Processor)) which does not require external RAM capacity to
`be used. The algorithm is made to easily fit into a parallel
`processing architecture, as this will yield the highest perfor
`mance. Alternatively, the algorithm can be implemented in
`Software stored on an electronic storage medium included in
`compression section 10 for use by a digital image processor
`included in compression section 10. The software can be
`executed by the digital image processor to perform the algo
`rithm.
`As shown in FIG. 3, the compression section 10 is opti
`mized to handle raw image data coming straight from the
`analog-digital converter 14 in a digital imaging front-end.
`Image sensor 14 can have any configuration of color filter
`pattern, e.g. a Bayer pattern. Some image s