United States Patent [19]
`[45] Date of Patent: May 23, 1995
`Sarver
`
`[11] Patent Number:
`
`5,413,714
`
`I|||||l||||I|||l|l|||||||I|||||||||||||||l||l||||l||||l||||lI||l|||||ll|||l
`Us005413714A
`
`[54] M]i.'I'I-IOD AND APPARATUS FOR
`VARIABLE BLOCK SIZE INTERPOLATIVE
`CODING OF INIAGES
`
`[75]
`
`Inventor:
`
`Edwin J. Server, Pearland, Tex.
`
`['73] Assignee: Eyesys Laboratories, Inc., Houston,
`Tex.
`
`[21] App]. No.: 44,401
`
`[22] Filed:
`
`Apr. 3, 1993
`
`GIJSF 15/42
`Int. Cl.‘
`[51]
`364/413.13; 364/413.18
`[52] U.S. Cl.
`[58] Field ofsearch .................... .. 364/413.16, 413.18,
`364/413.13, 413.15; 351/212, 221
`
`[56]
`
`Referene Cfited
`U.S. PATENT DOCUMENTS
`
`4,669,466 6/ 1987 L’Esp-eranoe
`4,692,003 9/198'? Adachi et al.
`4,721,379
`1/1988 L’ESperance
`5,307,096 4/1994 Baroth et al.
`
`364/413.13
`351./212
`351/212
`351/212
`
`
`
`..... ..
`
`Primary Examfm-zr—Dona1d E. McEl11eny, Jr.
`Attorney, Agent. or Fr'rm—ArnoId, White &. Durkee
`
`[57]
`
`ABSTRACT
`
`The method and apparatus of the .present invention
`presents an apparatus and-method for block adaptive
`image compression. The method and apparatus of the
`present invention reduces data storage and transmission
`requirements by sending a subset of the entire pixel data
`set existing in an image pixel data set. The pixels that are
`stored are referred to as primary pixels. The remaining
`pixels that are not transmitted or stored are referred to
`as secondary pixels. These secondary pixels are esti-
`mated from the primary pixels. A high fidelity image
`can be reproduced utilizing only the primary pixels.
`The method and apparatus of the present inventions
`estimates the secondary pixel values from the primary
`pixel values by predicting that a secondary pixel will
`look like the surrounding primary pixels, or by interpo-
`lating a value for the secondary pixels by summing the
`surrounding primary pixels and averaging them to ob-
`tain a value for the secondary pixel.
`
`18 Claims, 14 Drawing Sheets
`
`Microfiche Appendix Included
`(31 Microfiche, 1 Pages)
`
`110
`
`1
`
`Google Inc.
`(3000 1024
`IPR of US Pat. No. ?,974,339
`
`

`
`U.S. Patent
`
`May 23, 1995
`
`Sheet 1 of 14
`
`5,418,714
`
`

`
`U.S. Patent
`
`May 23, 1995
`
`Sheet 2 of 14
`
`5,418,714
`
`FIGURE 1B
`
`
`
`

`
`U.S. Patent
`
`May 23, 1995
`
`Sheet 3 of 14
`
`5,418,714
`
`

`
`U.S. Patent
`
`May 23, 1995
`
`Sheet 4 of 14
`
`5,418,714
`
`C0-C2__.__:..._
`
`C9-C2—--—....
`
`

`
`U.S. Patent
`
`May 23, 1995
`
`Sheet 5 of 14'
`
`5,418,714
`
`
`
`0
`
`FIGURE 6
`
`

`
`5,418,714
`
`I
`
`I___%%
`ll
`
`=5=8
`
`B0DUD00
`
`7.“554.321..U..
`UUUUUnu
`654324|0
`
`
`
`
`

`
`

`
`____ a
`
`
`00000
`
`2386422864286
`3&2222&JJJJmDflmmD
`
`3nu9.2M._flW.3342136MZn...
`.JJJJ&flfl.fl
`
`UDB00UD0DDnun.
`
`rEa------=s
`
`u__r-I-I----I3%9
`
`HHJ
`
`7F
`
`A
`
`M_____%/////fla
`----m.
`
`A
`
`H
`
`
`
`
`
`

`
`

`
`US. Patent
`
`May 23, 1995
`
`Sheet 10 of 14
`
`5,418,714
`
`8 X 8 BLOCK
`
`
`xxy -ZEZEEE
`3.11
`an
`1.0 E
`Eflflfl
`45
`55
`so
`a 15
`40E33
`339333
`13“H
`35B3
`
`47
`
`41
`
`15
`
`32
`
`s
`
`24
`
`12
`
`13
`
`7
`
`1
`
`21
`
`11
`
`2
`
`1o
`
`27
`
`14
`
`2.2
`
`4.1
`
`IEEEEE
`
`
`1.4
`
`
`
`
`
`4x4 BLOCK
`
`2x2 BLOCK
`
`-113 -2
`
`
`
`2
`
`3
`
`1
`
`FIGURE 8
`
`7
`
`3
`
`9
`
`4
`
`5
`
`1
`
`5
`
`11
`
`
`
`Iflflfll HI“
`HIKE II
`HIKE '"_"
`
`IIHE
`
`
`
`

`
`U.S. Patent
`
`May 23, 1995
`
`Sheet 11 of 14
`
`5,418,714
`
`1st stack: 256,256,8 '
`
`HGURE9
`
`
`
`HGURE10
`
`

`
`US.‘ Patent
`
`May 23, 1995
`
`Sheet 12 of 14
`
`5,418,714
`
`Imagie
`'
`
`Eye
`
`. Quantizer
`Selection
`
`Com ression
`_
`atso
`
`FIGURE 11A
`
`13
`
`

`
`US. Patent
`
`May 23, 1995
`
`Sheet 13 of 14
`
`5,418,714
`
`Image
`
`Quantizer
`compre_ssion
`PSNR
`Selection
`Ratio
`(€53)
`Lake n
`E
`
`Vegetables
`
`FIGURE 11B
`
`

`
`U.S. Patent
`
`May 23, 1995
`
`Sheet 14 of 14
`
`5,418,714
`
`
`
`cu)tn):0):
`
`

`
`1
`
`5,418,714
`
`2
`related to the patent application Ser. No. 07/973,045,
`entitled “A Method and Apparatus for Obtaining Kora-
`tometric Data,” by E, Sarver, H. D‘Souza, S. Woo, D.
`Engler, and K. Carbonari, filed on Nov. 6, 1992, and
`assigned to EyeSys, Inc. herein incorporated by refer-
`ence,
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to data com-
`pression and more specifically to adaptive compression
`and encoding of image data.
`BACKGROUND OF THE INVENTION
`
`Image compression is desirable in image data process-
`ing due to the size of the images. A typical image can
`include over 250,000 bytes of data. Thus, it would re-
`quire a great deal of disk space to store several of these
`images in their uncompressed state. Data transfer is
`slow as well for such large data files. Thus it is desirable
`to reduce the amount of data to a minimum to save disk
`space and reduce data transfer time.
`Typically, it: most compression algorithms that are
`based on block sizes, a single block size is utilized for the
`entire image. A single block size is undesirable in some
`cases. For example, in some images, large portions of
`the image picture elements (pixels) may be of approxi-
`mately the same intensity, forming a homogeneous re-
`gion within the image. In this case a large block size is
`desirable. A single intensity value can be assigned to the
`entire hotuogenons pixel region. The block can be as
`large as the homogenous region without loss of accu-
`racy or efficiency in the data representation.
`Many images, however. are not composed of large
`homogeneous regions. When the image data is not ho-
`mogeneous, a smaller block size is desirable. For exam-
`ple, when the image has a large quantity of detail, such
`as an image of trees or grass, or at a hair line, smaller
`blocks are desirable. In these nonhomogeneous regions,
`it is not practical to represent large areas of the image
`with a single pixel value. Thus it is desirable to utilize a
`large number of aller blocks to define the detail pres-
`ent in the nonhomogeneous regions. Thus there is a
`need for a block size that varies in accordance with the
`amount of detail encountered in the image.
`SUMMARY OF THE INVENTION
`
`The method and apparatus of the present invention
`presents an apparatus and method for block adaptive
`image compression. The method and apparatus of the
`present invention reduces data storage and transmission
`requirements by sending a subset of the entire pixel data
`set existing in an image pixel data set. The pixels that are
`stored are referred to as primary pixels. The remaining
`pixels that are not transmitted or stored are referred to
`as secondary pixels. These secondary pixels are esti-
`mated from the primary pixels. A high fidelity image
`can be reproduced utilizing only the primary pixels.
`The method and apparatus of the present inventions
`estimates the secondary pixel values from the primary
`pixel values by predicting that a secondary pixel will
`look like the surrounding primary pixels, or by interpo-
`lating a value for the secondary pixels by summing the
`surrounding primary pixels and averaging them to ob-
`tain a value for the secondary pixel.
`The present invention provides a method and appara-
`tus for analyzing cornml imagery data to diagnosis
`corneal conditions; measuring a physical characteristic
`
`METHOD AND APPARATUS FOR VARIABLE
`BLOCK SIZE INTERPOLATIVE CODING OF
`FMAGES
`
`SOFTWARE MICROFICHE APPENDIX
`
`A microfiche software appendix consisting of 1 fiche
`comprising 31 frames is included.
`TRADEMARK NOTIFICATION
`
`EyeSys, Corneal Analysis System (CAS) and EyeSys
`Laboratories are trademarks utilized by ByeSys Labo-
`ratories, Inc. of Houston, Tex. Federal registration of
`these trademarks is pending.
`COPYRIGHT NOTIFICATION
`
`Pursuant to 37 CFR 1.71 (d) the following copyright
`notice is provided: A portion of the disclosure of this
`patent document contains material which is subject to
`copyright protection. The copyright owner has no ob-
`jection to the facsimile reproduction by anyone of the
`patent document or the patent disclosure, as it appears
`in the Patent and Trademark Office patent file or re-
`cords, but otherwise reserves all copyright rights what-
`soever.
`
`CROSS REFERENCE TO RELATED PATENT
`APPLICATIONS
`
`This patent application is related to U.S. Ser. No.
`08/044,654 filed concurrently herewith, entitled a
`“Method and Apparatus for Lossless Compression of
`Correlated Data Utilizing Delta Coding with Condi-
`tional Runlengths” by Edwin J. Sarver, and assigned to
`E.yeSys Laboratories, Inc., which is herein incorpo-
`rated by reference. This patent application is also re-
`lated to U.S. Ser. No. 07/607,640 filed Oct. 29, 1990 ,
`abandoned, entitled a “M1lIti-functional Corneal Analy-
`sis System” by Wakil, D’Sou2.a, Baumgartner, and Car-
`bonari and assigned to Eyesys Laboratories,
`Inc.,
`which is herein incorporated by reference. This patent
`application is also related to U.S. Ser. No. 07/817,868,
`entitled “A Contact Lens Sculpturing Device” by
`Waldl, D’Souza, Baumgartner, and Carbonari and as-
`signed to EyeSys Laboratories, Inc. (abandoned divi-
`sional application of abandoned Ser. No. 607,640 filed
`Jan, 7, 1992) which is herein incorporated by reference;
`U.S. Ser. No. 07/818,659, entitled “A Method of Using
`A Placido” by Wakfl, D’Souza, Baumgartner, and Car-
`bonari and assigned to EyeSys Laboratories, Inc. (aban-
`doned divisional application of abandoned Ser. No.
`607,640 filed Jan. 7, 1992) which is herein incorporated
`by reference; and abandoned U.S. Ser. No. 07/319,364,
`and "A I-‘lacido Apparatus” by Wakil, D'Souza, Baum-
`gartner, and Carbonari and assigned to Eyesys Labora-
`tories, Inc. (abandoned divisional application of aban-
`doned Ser. No. 607,640 filed Jan. 7, 1992) which is
`herein incorporated by reference.
`This patent application is also related to the patent
`application entitled, “VIDEO T0 PRINTER INTER-
`FACE METHOD AND APPARATUS” by Edwin J.
`Sarver, Henry M. D’Souza, and Steven Woo, Ser. No.
`07/866,675, filed on Apr. 10, 1992. This patent applica-
`tion is also related to the design patent application Ser.
`No. 07/867,795 entitled “DESIGN FOR AN ABSO-
`LUTE DIOPTRIC SCALE REPRESENTATIO ”
`filed on Apr. 10, 1992 by Edwin J. Sawer and assigned
`to EyeSys Laboratories, Inc. which is herein incorpo-
`rated by reference; and this patent application is also
`
`10
`
`15
`
`20
`
`30
`
`45
`
`51'}
`
`60
`
`16
`
`

`
`3
`of a cornea; convening ‘the measured physical corneal
`characteristic to a digital image comprising a series of
`digital values; storing in a processor memory the digital
`values representing the physical characteristics of the
`cornea; selecting a region of digital values less than or
`equal to all of the digital values; determining a predic-
`tion error for the selected digital values; determining
`whether the prediction error exceeds a threshold value;
`selecting a different region of digital values when the
`prediction error exceeds the threshold; and analyzing
`the digital representation of the corneal imagery data.
`The present invention further provides a method and
`apparatus for adapting the number of bits utilized to
`represent
`the prediction error; adapting a quantize:
`width in accordance with the characteristics of the
`region; adapting a set of interpolation coefficients in
`accordance with the characteristics of the region.
`The present invention provides a method and appara-
`tus wherein the shape of region of pixels is adapted
`when the prediction error exceeds the threshold and the
`size region of pixels is adapted when the prediction
`exceeds the threshold wherein the region of pixels is a
`block of pixels wherein the block of pixels is subdivided
`into polygons when the prediction error exceeds the
`threshold.
`The present invention further provides a method and
`apparatus for compressing; for determining which sec-
`ondary pixel in a region of pixels is farthest away from
`a primary pixel; determining whether a value for the
`secondary pixel exceeds a threshold; and adapting the
`region of pixels if the threshold is exceeded.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A is an example of a preferred hardware '-m -
`bodiment of the present invention.
`FIG. 1B is a graph showing axis rotation in linear
`space in the present example of a preferred embodi-
`ment.
`
`FIG. 2 is an example of block division and pixel pre-
`diction in the present example of a preferred embodi-
`ment.
`
`FIG. 3 is an example of block division and pixel pre-
`diction in the present example of 3 preferred embodi-
`ment.
`
`FIG. 4 is an example adaptive coefficient generation
`in the present example of a preferred embodiment.
`FIG. 5 is an example of a preferred embodiment of
`pixel prediction utilizing a plurality of border pixels.
`FIG. 6 is a graph of the expected pixel error envelope
`in the present example of a preferred embodiment.
`FIG. 7A—1G are representative histograms collected
`for a series of images which illustrates the occurrence of
`block sizes for different quantize: selections in the pres-
`ent example of a preferred embodiment.
`FIG. 8 is an illustration depicting the preferred pixel
`scanning order in the present example of a preferred
`embodiment.
`FIG. 9 is an illustration depicting error calculation
`and pixel block adaption in the present example of a
`preferred embodiment.
`FIG. 10 is an example of the preferred thresholds for
`several quantizer selections in the present example of a
`preferred embodiment.
`FIGS. 11A and 11B are a table depicting the Signal to
`Noise Ratios (SNR) and Compression Ratio values for
`the USC benchmark images in the present example of a
`preferred embodiment.
`
`17
`
`5,418,714
`
`4
`FIGS. 12A—l2C illustrates the transformation of the
`red, green and blue (RGB) components into YIQ space
`in the present example of a preferred embodiment.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`The present invention will be further clarified by a
`consideration of the following examples, which are
`intended to be exemplary of the invention and the use of
`the invention and are not intended to limit the scope of
`the invention.
`In the preferred embodiment, the block size is adap-
`tively seiected based on the characteristics of the image
`pixel data. Large blocks are used for homogeneous data.
`Smaller blocks are utilized for detailed data. An image
`is broken down into smaller and smaller sections until
`the error for any pixel in the block is less than a prede-
`termined threshold, Te. The method and apparatus
`provides a technique that utilizes historical tendencies
`and interpolation of primary pixel data to predict the
`values for subsequent pixel data sets.
`Thus, the prediction technique is both causal and
`noncausal. Causal pixel prediction utilizes the historic
`tendencies of the image data to predict the values for
`other pixel data. Noncausal prediction utilizes the pri-
`mary pixels surrounding a. secondary pixel to estimate a
`value for the secondary pixel. Noncausal prediction is
`essentially an interpolation methodology.
`Causal prediction is useful in a homogeneous image
`region such as in a region of pixels existing on the side
`of a wedge. For example, when sampling pixel data in
`an uphill or downhill direction on the wedge surface,
`the pixel values have the same tendency. Thus, the
`method and apparatus of the preferred embodiment
`predicts that an unknown pixel value will continue the
`trend established by the surrounding pixels. The pixel
`data tendency is based on the historical values for the
`surrounding pixel data. Noncausal pixel prediction, or
`interpolation, utilizes the primary pixel data. surround-
`ing a secondary pixel to estimate the secondary pixel’s
`value.
`
`The pixel data encoder and reconstructor utilize the
`same prediction technique. Thus, rather than storing
`and transferring an entire pixel data set, only the predic-
`tion errors are stored and transferred. This technique
`reduces the amount of data, thus reducing data storage
`capacity and transmission bandwidth requirements.
`The method and apparatus of the present invention is
`adaptable to variations in pixel region activity. Large
`block sizes with few data bits are utilized to encode
`
`pixel estimation errors in the homogeneous regions of
`pixel data where most of the data has the same value.
`Smaller blocks are utilized for nonhomogeneous re-
`gions which manifest a large quantity of detail. Corre-
`spondingly, a larger number of bits are utilized to en-
`code the pixel estimation errors in the nonhomogeneous
`regions of an image. Thus, the block size and number of
`bits utilized to represent the prediction error are vari-
`able in accordance with the characteristics of the image
`data in a particular region,
`A threshold, To is provided to control the compres-
`sion rate and corresponding reconstruction error. As Te
`is allowed to increase, more error is tolerated, and the
`allowable data compression rate increases, There is a
`tradeoff, however, between the achievable data com-
`pression rate and the perceived image quality. If a high
`quality image is not necessary for image reconstruction
`and display, Te can be large and significant data com-
`
`5
`
`10
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`
`5,418,714
`
`5
`pression is attainable. However, if high fidelity image
`reconstruction is desired, for example with an image
`containing fine detail, To should be small and the
`achievable compression rate reduced.
`'I‘he user may
`select Te, thereby selecting the amount of error intro-
`duced into an pixel data set by controlling the thresh-
`olds. As explained above, the perceived image quality is
`inversely proportional to the allowed error threshold,
`To.
`
`The present invention presents a simple and effective
`image compression scheme. The preferred embodiment
`is implemented on a data processor with memory stor-
`age existing in the Eye-Sys Corneal Analysis System
`(CAS)TM manufactured by EyeSys Laboratories, Inc.
`of Houston, Tex. In the preferred embodiment, the
`method and apparatus of the present invention is used to
`compress corneal eye images in the EyeSys Corneal
`Analysis System(CAS) TM where compression rates of
`3:1 to 40:1 are routinely obtained.
`The corneal images are derived from 21 Charge Cou-
`pled Device camera and compressed before storing
`them in system memory. The preferred method and
`apparatus also yields good image quality on a set of
`benchmark images from the University" of Southern
`California data set, which is the benchmark generally
`utilized for comparing compressed images.
`In interpolatlve image compression a. subset of pixels
`is selected for transmission and storage. See, A. N. Ne-
`travali and B. G. Haskell, Digital Pictures Representa-
`tion and Compression, Plenum Press, N.Y., 1988. Inter-
`polative image compression entails interpolating pixels
`within a subset of the entire pixel data set to encode and
`reconstruct the entire data set, and is well known in the
`art.
`
`As an example, a brute force technique for perform-
`ing interpolatlve image compression is to select every
`other pixel in each row and column for transmission and
`storage. The missing pixels are reconstructed by inter-
`polating the four pixels surrounding each missing pixel
`to estimate a value for the missing pixel. For example,
`the even pixels in each row and column, numbered: 0, 2,
`4, etc., referred to as primary pixels, can be selected for
`transmission and storage. The odd numbered pixel val-
`ues, numbered: 1, 3, 5, etc., referred to as secondary
`pixels, can be estimated by interpolating between the
`four primary pixel values surrounding each odd num-
`bered secondary pixel. Therefore, there is no need to
`transmit or store the secondary pixel values.
`This simple technique, achieves a 4 to 1 data com-
`pression rate, as only the even numbered primary pixels
`are transmitted and stored. A secondary pixel value can
`be estimated by a performing a simple summation of
`each of the four adjacent primary pixel values and di-
`viding the sum by four. Secondary pixels located at the
`boundaries of the pixel region do not have four adjacent
`pixels. Thus, these boundary pixels can be estimated by
`taking one-half of the summation of the two adjacent
`primary pixels.
`There are additional techniques which can be utilized
`to arrive at noncausal predictive values. One of these
`techniques is edge strength comparison. This technique
`selects stronger edges in estimating the missing second-
`ary pixel values. An edge falling between two adjacent
`pixels is stronger or sharper than an edge diagonally
`traversing a pixel. Thus, the two pixels with the stron-
`ger edges will be utilized in interpolation to estimate a
`value for the mismng secondary pixel. Edge strength
`determination is a nonlinear adaption technique which
`
`6
`facilitates preservation of sharp edges existing in the
`image data.
`Edge preservation is important in the preferred em-
`bodiment. In the preferred embodiment, a concentric
`set of Placido rings is reflected off of a patient’s cornea.
`A Charge Coupled Device camera captures the image
`of the cornea and the reflected Placido rings. The image
`data comprises a corneal image with an embedded set of
`concentric rings generated by the reflection of the Pla-
`cido rings off of the corneal surface.
`A perfectly spherical cornea reflects a perfectly con-
`centric set of Placido rings. An uonspherical corneal
`reflects a nonconcentric set of Placido rings. The non-
`spherical characteristics of the cornea can be deter-
`mined by examining the degree of perturbation away
`from concentric for the reflected Placido rings. An
`edge detector is utilized to find the edges of the rings
`and compute their location.
`The edges of the reflected rings are utilized to deter-
`mine the topography of the cornea. The Eyesys Cor-
`neal Analysis System (CA3) of the preferred embodi-
`ment utilizes the resulting corneal topography to diag-
`nose problems with the eye. Thus,
`it is desirable to
`maintain sharp edges during data compression to facili-
`tate processing of the Placido rings. Therefore, it is
`desirable to utilize primary pixels with strong edges,
`such as those pixels aligned with an edge, thus helping
`to preserve the edges of the Placido ring for edge detec-
`tion and processing. The strength of a pixel edge is
`determined by computing the differential or size of the
`step gradient between pixels, which is proportional to
`the edge strength. The stronger edge pixels are prefera-
`bly selected for primary pixels utilized_ for interpolation.
`The primary pixel data set may be further com-
`pressed to achieve a compression ratio higher than four
`to one. Primary pixels are highly correlated, therefore,
`they may be compressed utilizing a common compres-
`sion technique such as Pulse Code Modulation (PCM)
`or quantization, Differential Pulse Code Modulation
`(DPCM) by determining and storing only the differ-
`ences between the sequential pixel values, vector quan-
`tization by finding vectors to represent primary pixels,
`or transform coding (TC) to transform the pixels into
`another space which decorrelates the correlation be-
`tween the pixels into the fewest possible coefficients.
`Only the primary pixels need be transmitted or
`stored. The remaining secondary pixels, which are not
`included in the primary pixel data set, are reconstructed
`by interpolation of the primary pixels at the reconstruc-
`tor. Thus, the secondary pixels which are necessary to
`reconstruct the image, are not transmitted because they
`can be recreated by interpolation of the primary pixel
`data set. A residual error block is formed by subtracting
`the predicted primary pixels and the interpolated block
`of secondary pixels from the original image block. The
`residual error block can be determined for each block
`size utilized. This residual error block may be further
`compressed using Transform Coding, which is well
`known in the art. (See, for example, B. G. Haskell,
`“lnterpolative, Predictive and Pyramid Transform Cod-
`ing of Color Images”, Proceedings of IEEE ICASSP
`88, pp. 785-787, April 1988), or vector quantization
`(see, e.g., H. M. Hang and B. G. Haskell, “Interpolative
`Vector Quantization of Color Images”, IEEE Trans, on
`Comm., vol. 36, no. 4, pp. 465-470, April 1988).
`Interpolative image compression schemes are useful
`in both interframe and intraframe applications in the
`preferred embodiment. Thus, the method and apparattls
`
`5
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`65
`
`18
`
`

`
`5,418,714
`
`5
`
`I0
`
`15
`
`20
`
`'
`
`25
`
`30
`
`35
`
`7
`of the present invention works well across a single im-
`age, or across a time sequence of images such as anima-
`tion or video frames. Decorrelation is useful to repre-
`sent the image with the smallest dynamic range re-
`quired. The method and apparatus of the present inven-
`tion decorrelates pixels in the temporal domain as well.
`Referring now to FIG. 1A, a hardware embodiment
`for the example of a preferred embodiment is illustrated.
`FIG.
`IA illustrates a Corneal Analysis System(-
`CA5) TM , manufactured by EyeSys Laboratories, Inc.,
`2776 Bingle, Houston, Tex., (713) 465-1921. The Cor-
`neal Analysis System comprises a corneal image analy-
`sis viewing monitor 100, a backlit, conical placido pro-
`jector 1llJ, a computer with associated memory and
`hardware devices 120, a stand 130, a keyboard 140, a
`movable placido/CCD camera stand 150, ajoystick 160
`for positioning the placido relative to a patient’s cor-
`neas, and a patient positioning head rest 170. In the
`present example of a preferred embodiment, a physician
`utilizes the method and apparatus of the present inven-
`tion in conjunction with the Corneal Analysis System(-
`CAS) TM or an equivalent system. The physician cap-
`tures an image of the patient’s cornea by positioning the
`patient in front of the placido projector/CCD camera
`110. The CAS takes a picture of the placido reflected
`off of the cornea. The CAS digitizes the image and
`stores in computer memory 120. The image is com-
`pressed and then stored in computer memory 120 for
`diagnosis at a later time, transmitted over a network to
`another CAS or some other system for diagnosis at a
`remote location, or displayed for immediate diagnosis
`on diagnostic display screen 100.
`For example, in a two dimensional example, as shown
`in FIG. 113, by rotating the axes in linear space with a
`two by two matrix, it can be shown that most of the
`signal energy is contained in one dimension. Thus a one
`dimensional representation can be used to represent all
`of the data points. Very little signal energy is required in
`the other dimension and is thus negligible in the repre-
`sentation. Rotation can be performed for a plurality of 40
`dimensions until the signal energy is so small that it is
`negligible and is no longer necessary to accurately rep-
`resent the image. Thus, as shown in FIG. 1B, to repre-
`sent a pattern or random vector in two space, by rotat-
`ing the axes by an angle theta, the values can be repre-
`sented along a single axis rotated by the angle theta. The
`axis can then berotated back to its origina.1 position
`through an angle theta without significant loss of fidel-
`ity in the data representation. Moreover, this technique
`can be extended to N dimensions.
`
`8
`pixels from neighboring blocks to predict a pixel value
`for the current block under consideration. Neighboring
`blocks contain primary pixels 200, 210, and 220, which
`have already been computed. The present embodiment
`forms a linear combination of neighboring pixels utiliz-
`ing equation 1, shown below.
`The preferred embodiment determines coefficients
`c0, cl, and c2. Assuming that the image is highly corre-
`lated,
`the minimum-mean-squared predictor, from a
`statistical point of view, will set coeilicients ct] and c2
`equal to 1, and coefficient cl equal to -1. Assuming
`that these are the values for the coefficients, no multipli-
`cations are required. The coefficient based computation
`requires only addition and subtraction to determine the
`predicted pixel value. Thus the calculations are faster
`and easier to implement.
`The preferred embodiment is considerably faster than
`predicting a pixel based optimal least-squares coeffici-
`ents. A linear system of coefficients will have a matrix
`which is positive, semi-definite, but a solution that may
`not be useful. In the degenerate case, assuming that the
`image is highly correlated, the technique of the pre-
`ferred embodiment enables the system to overcome the
`few cases in which the coefficients are not useful. As-
`suming that the least-squares prediction is desired, a
`deterministic system of normal equations exists which
`will always have a solution, except where the matrix is
`singular. The few degenerate cases will remain where
`the coefficients are not useful, but assuming that the
`coefficients are 1, -1, and l, the technique yields a
`useful solution which is 90% as efficient as an optimal
`technique, without having to deal with degenerate
`cases.
`
`In the preferred embodiment, the method and appara-
`tus of the present invention can interpolate the remain-
`ing M><M—l pixels of the block using the predicted
`pixels from neighboring blocks, as shown in FIG. 3.
`Once the primary pixels are determined, an interior
`Secondary pixel 240 can be determined. As discussed
`above, secondary pixels can be determined by linear
`interpolation or by assigning coefficients and solving
`optimal equations to determine optimal prediction coef-
`ficients, as utilized in adaptive DPCM prediction of the
`primary pixels. Equations 2 and 3 are used in the inter-
`polation, which is a linear interpolation of the pixel
`values.
`The residual error for the block is computed and
`compared to a threshold value, Te. The interpolated
`pixels are then subtracted from the original image block
`and the computed difference for each pixel compared
`with a threshold value, Te. If the difference between the
`interpolated pixel value and the original pixel value,
`referred to as a residual error, is greater than Te, the
`block size is changed. In one example of the preferred
`embodiment,
`the image block is divided into four
`smaller blocks and the process of interpolation and
`residual error calculation repeats for each subbloclc
`The most general case is to allow the blocks to be subdi-
`vided into rectangular regions.
`Alternatively, the blocks can be subdivided into arbi-
`trary contours. The contours selected are represented
`by contour codes. The contours may be selected to be
`coextensive with homogeneous regions. If a block is
`subdivided until it reaches the minimum block size of
`
`IX 1, i.e. a single pixel, but the residual error still ex-
`ceeds the threshold, Te, the pixel value is explicitly
`encoded and provided to the reconstructor since no
`further block reduction is possible. Explicit encoding is
`
`45
`
`50
`
`In the preferred embodiment, an improved compres-
`sion technique, which yields good image reconstruction
`results in compression rates in the range of 1.0 bit per
`pixel. The preferred embodiment combines adaptive
`prediction and interpolation methods followed by
`adaptive Hufiman coding. The preferred embodiment
`also employs variable block sizes to provide additional
`adaptability. The combination of methods used in the
`preferred embodiment is refereed to as Block Adaptive
`Interpolative Coding (BAIC). The preferred embodi-
`ment provides a simple technique for achieving good
`results and reasonable data rates. The simple technique
`makes it easy to implement and maintain in software.
`The simple implementation lends itself to a reduced-
`complexity, less-costly implementation in hardware as
`well.
`Turning now to FIG. 2, for example, BAIC can di-
`vide au image into MXM pixel blocks and use selected
`
`55
`
`65
`
`19
`
`

`
`5,418,714
`
`9
`common in an image with a high degree of detail. such
`as scenes containing imagery of grass and trees.
`In the preferred embodiment, the method and appara-
`tus of the present invention starts with 8X8 block of
`pixels and attempts to encode the pixels. If there are
`pixels in the block that exceed the predefined threshold,
`Te,
`the preferred method and apparatus repeatedly
`subdivides the region until the error is reduced below
`Te or the block size is reduced to 1x1 and the pixel is
`encoded directly. The user may indirectly set
`the
`threshold, Te. The initial block size and threshold are
`set by the Corneal Analysis System processor. The user
`can override the
`selection by selecting a quantizer
`style ranging from zero—six. A selection of zero repre-
`sents no compression. Thus the pixels are directly en-
`coded. A selection of one represents a small block size,
`for example 2x2, and a small threshold, Te, so that a
`high fidelity image can be reconstructed which looks
`very much like the original image. At a quantizcr selec-
`tion of six, 21 large SX8 block is utilized, and the thresh-
`old, Te is large. In this case wider quantizers are utilized
`capable of achieving compressions on the order of 30 to
`1.
`
`Turning now to FIG. 4, in the preferred embodiment,
`coding of the primary pixels is adaptive in the sense that
`the prediction coefficients, ci, may be recalculated and
`transmitted for each image or image region. For exam-
`ple, on a row by row basis, as shown in FIG. 4, row 0
`has coefiicients c[Lc2, which are used for the first row.
`On the second row, the data has a different characteris-
`tic and another set of coefficients is utilized. Thus, the
`coefficients vary in accordance with the characteristics
`of the data. For example, in an image of the horizon, the
`upper rows