Exhibit 2008
`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-00449
`1
`
`

`

`.
`
`O.
`
`
`
`.m.mN_+2<:o_2¢Oh_mZ<W_._..
`
`
`
`
`
`S.
`
`.Mm.S2N.:9.PL
`e.
`
`..L
`
`aChS
`
`m9o
`
`owmfifilrw
`
`1mN.o
`
`
`
`o.M moqmopmm_$.m_>z_v_oo._muc<mo5mm>_mH.EDG.6.,mmvw.mmmm5om.
`
`sEo.._mz<Emmwfizqsomo
`
`
`
`
`
`
`
`2
`
`
`

`

`
`
`U. S. Patent Oct. 6,1987
`
`U.S.PatentOct.6,1987
`
`gmmmmbnaaaanagag”aaaaHananaaaanaaamnaawayawayawayawayawayHanaAoaaanaaaanaaaana5aaaaAcanan.2anZZanan0%3%ém3%ammm.Hg.”ammm
`
`
`
`
`
`
`
`
`
`
`
`3naaaaaan.mummy
`
`Han.5ananyaanya.
`)2...,n)g)5)”)a)5)F
`
`Sheet 2 of 3
`
`694
`4,698,689
`9869
`
`00HEEM9((((
`gag“gymgmawn”F
`anyanynunnananyannnnnnnnnnnaananannaW.
`
`
`
`
`(8)nWanWamn3.
`
`(7)
`
`(8)
`
`5
`
`(6)
`
`
`
`
`
`r
`
`3
`
`

`

`U. S. Patent Oct. 6,1987 ‘
`
`Sheet3 of3
`Sheet3 of3
`
`4,698,689
`4,698,689
`
`
`
` U.S.PatentOct.6,1987%
`
`
`
`4
`
`

`

`1
`
`PROGRESSIVE IMAGE TRANSMISSION
`
`BACKGROUND OF THE INVENTION
`
`4,698,689
`
`5
`
`I0
`
`20
`
`This invention relates to the transmission of pictorial
`image data. More particularly, it is concerned with the
`progressive transmission and reconstruction of coded
`images in which an approximate image is reconstructed
`based upon partial information and details are added as
`additional information becomes available.
`The progressive transmission and reconstruction of
`coded images allows an approximate image based upon
`partially received information to be constructed to
`which additional details are added as additional infor-
`mation becomes available. This procedure has various 15
`applications in the field of image communications, such
`as for interactive picture retrieving, variable-rate video
`conferencing, and the quick display of freeze-frame
`image transmission. One relatively simple scheme pro-
`posed by Knowlton U.S. Pat. No. 4,222,076 issued Sept.
`9, 1980, deals with spatial domain data for the progres-
`sive transmission of gray-scale pictures. This approach
`has the advantages of simplicity in implementation and
`no coding distortion in the final reconstructed image.
`However, due to the nature of successive picture subdi- 25
`vision introduced by this method, the number of accu-
`mulated bits of information increases exponentially with
`each interation.
`Other schemes that deal with transform domain data
`have been described in articles by Takikawa “Fast Pro-
`gressive Reconstruction of A Transformed Image,”
`IEEE Trans. Inform. Theory, vol. IT-30, pp. 111-117,
`January 1984 and Ngan “Image Display Techniques
`Using the Cosine Transform,” IEEE Trans. Acoust.,
`Speech, Signal Processing, vol. ASSP-32, No. 1, pp.
`173-177, February 1984. _Transform image coding is
`well known for its compression efficiency. Its nature
`renders it also suitable for efficient progressive trans-
`mission and reconstruction since low frequency trans-
`form coefficients contain most of the energy of image 40
`signals. Thus, a small subset of the transform coeffici-
`ents is good enough for reconstructing a rough version
`of the whole image, while the remainder of the trans-
`form coefficients allow the receiver to add details to the
`initially reconstructed picture as they are received. In
`one such scheme the transform coefficients of each
`block of image data are considered as arranged in a
`square lattice and are sent and received in a zig—zag
`pattern in order from the large through the small vari-
`ance values. This scheme is described in an article of 50
`Tescher and Cox “An Adaptive Transform Coding
`Algorithm,” ICC Conference Records, pp. 47.20-24,
`1976. Although the zig—zag technique provides better
`compression efficiency than other proposed transform
`domain schemes, it is desirable to further improve the 55
`efficiency with which image data can be transmitted,
`particularly during the first few iterations.
`
`30
`
`35
`
`45
`
`SUMMARY OF THE INVENTION
`
`The improved method of progressively transmitting 60
`an image in accordance with the present invention com-
`prises dividing an image into a predetermined array of
`zones of picture elements. A predetermined spatial do-
`main-to-transform domain transformation is performed
`on the picture elements of each zone to provide trans— 65
`form coefficients thereof. Signals containing data repre-
`senting transform coefficients in different degrees of
`detail are produced and transmitted for each zone dur-
`
`2
`ing the first of a plurality of transmission sequences.
`Signals containing data on transform coefficients which
`when combined with the data transmitted during pre-
`ceding sequences provide cumulative data representing
`the transform coefficients of the zone in increasingly
`finer detail are produced and transmitted for each zone
`during subsequent sequences of the plurality of sequen-
`ces.
`
`In reconstructing the image, the signals containing
`data representing transform coefficients in different
`degrees of detail transmitted during the’ first transmis-
`sion sequence and the signals containing data on trans-
`form coefficients transmitted during subsequent sequen-
`ces are received. The signals containing data on trans-
`form coefficients transmitted during each transmission
`sequence subsequent to the first are combined with
`corresponding signals transmitted during preceding
`transmission sequences including the first to provide
`cumulative signals containing data on transform coeffi-
`cients for each zone. The inverse of the predetermined
`spatial domain-to-transform domain transformation is
`performed on the cumulative signals containing data on
`transform coefficients for each zone after selected trans-
`mission sequences to provide reconstituted image data
`for each picture element of each zone. The reconsti-
`tuted image data is of finer detail after later transmission
`sequences in the plurality.
`A system in accordance with the present invention
`for progressively transmitting an image comprises
`means for dividing an image into a predetermined array
`of zones of picture elements and transform means for
`performing a predetermined spatial domain-to-trans-
`form domain transformation of the picture elements of
`each zone to provide transform coefficients thereof.
`The system includes means for producing and transmit-
`ting for each zone during the first of a plurality of trans-
`mission sequences signals containing data representing
`transform coefficients in different degrees of detail, and
`means for producing and transmitting for each zone
`during each subsequent sequence of said plurality of
`sequences signals containing data on transform coeffici-
`ents which when combined with data transmitted dur-
`ing preceding sequences provide cumulative data repre-
`senting the transform coefficients of the zone in increas-
`ingly finer detail.
`For reconstructing the image the system comprises
`receiver means for receiving for each zone said signals
`containing data representing transform coefficients in
`different degrees of detail transmitted during said first
`of said plurality of transmission sequences and said sig-
`nals containing data on transform coefficients transmit-
`ted during each subsequent sequence of said plurality of
`transmission sequences. Means are included for combin-
`ing signals containing data on transform coefficients
`transmitted during each transmission sequence subse-
`quent to the first with corresponding signals transmitted
`during preceding transmission sequences including the
`first to provide cumulative signals containing data on
`transform coefficients for each zone. Inverse transform
`means are also included for performing the inverse of
`said predetermined spatial domain-to-transform domain
`transformation of cumulative signals containing data on
`transform coefficients for each zone after selected trans-
`mission sequences to provide reconstituted image data
`for each picture element of each zone, the reconstituted
`image data being of finer detail after later transmission
`sequences in the plurality.
`
`5
`
`

`

`3
`
`4,698,689
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`In the drawings:
`FIG. 1 is a block diagram representing apparatus for
`progressively transmitting and reconstructing an image
`in accordance with the present invention;
`FIGS. 2A and 2B illustrate a set of exemplary bit
`assignment matrices useful
`in explaining the present
`invention;
`FIG. 3 is an exemplary standard deviation matrix
`from which the bit assignment matrices of FIGS. 2A
`_and 2B are designed;
`FIG. 4 illustrates stages in the progressive recon-
`struction of an image in accordance with the present
`invention; and
`FIG. 5 illustrates corresponding stages in the pro-
`gressive reconstruction of an image in accordance with
`prior art techniques.
`For a better understanding of the present invention,
`together with other and further objects, advantages,
`and capabilities thereof, reference is made to the follow-
`ing disclosure and appended claims in connection with
`the above-described drawings.
`
`DETAILED DESCRIPTION
`General
`
`FIG. 1 is a block diagram representing a system for
`the progressive transmission and reconstruction of im-
`ages in accordance with the present invention. The
`system includes a scanner 10 for scanning an image in
`two directions and producing information on each pic-
`ture element (pixel) of the image. This information is
`placed in storage 11 in digital format to be appropriately
`addressed by zones, or blocks, of pixel data correspond-
`ing to predetermined portions of the image area.
`Each block of data is transformed by a two-dimen-
`"sional spatial domain-to—transform domain transforma-
`tion function in a two-dimensional transform 12. One
`form of two-dimensional transformation which has been
`found particularly suitable is the discrete cosine trans-
`formation as described in an article by Ahmed, Natara-
`jan, and Rao “Discrete Cosine Transform,” IEEE
`Transaction on Comput., Vol. C-23, pp. 90-93, January
`1974. The transformation produces a set of transform
`coefficients for each block which are quantized in a
`block quantizer 13.
`The block quantizer 13 quantizes each transform
`coefficient of a block in varying degrees of precision for
`each of several iterations to produce a series of sets of
`quantized values. That is, on each succeeding iteration,
`a greater number of bits are assigned to represent the
`values of the coefficients of different ones of the coeffi-
`cients. The total number of bits assigned to the quan-
`tized values increases by the same amount for each
`iteration. That is, on the first iteration values for several
`of the coefficients of the set are expressed in different
`numbers of bits which add to a total number of bits for
`the set. On each subsequent iteration that same number
`of bits is added and the total number reassigned to pro-
`. vide image data on the values of the coefficients in
`greater detail. For each iteration the bits added to each
`set are transmitted during a transmission sequence by a
`transmitter 14 and conducted over a suitable transmis-
`sion channel to a receiver 20.
`'
`The receiver 20 receives the information during each
`transmission sequence for each iteration on each block
`and stores the bits in storage 21. After each iteration, or
`transmission sequence, the data available on the trans-
`
`l0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`form coefficients for each block is increased by the
`amount being sent, thus providing greater information
`on the image details. This data is accumulated in storage
`21 by combining the bits received during each transmis-
`sion sequence with those previously received.
`At any stage in the sequence of iterations, the accu-
`mulated bits representing the transform coefficients of
`each set may be removed from storage 21 and processed
`in a block dequantizer 22 to re-establish the transform
`coefficient values to the extent of precision possible
`with the accumulated data available. This information is
`subjected to the inverse of the previous spatial domain-
`to-transform domain transformation in an inverse trans-
`form 23 to produce reconstituted image data in the
`spatial domain. This data is placed in storage 24 and is
`available for display on a display 25. The display repro-
`duces the image data in greater detail upon subsequent
`iterations or transmission sequences. Thus, the transmit-
`ted image is progressively reconstructed in successively
`finer detail during successive transmission sequences,
`and transmission may be stopped after any transmission
`sequence up to transmission of final detail.
`DESIGN OF BIT ASSIGNMENT MAPS
`
`In a progressive transmission and reconstruction sys-
`tem where AB; bits of the total for an image are trans-
`mitted at the i-th step of progression, the number of
`accumulated information bits at the i-th step of progres-
`sion 1S
`
`In a practical system it is preferred that the number of
`information bits transmitted at each iteration be fixed,
`i.e., AB,~= AB for any i. Therefore, the number of accu-
`mulated information bits can be rewritten as B,-=1‘-AB.
`For the present discussion nonadaptive spatial domain-
`to-transform domain coding with a zonal bit assignment
`scheme in which the number of information bits allo-
`cated is the same from block to block is employed. The
`scheme may be extended to adaptive transform coding
`if desired in accordance with the teachings in an article
`by Ngan “Adaptive Transform Coding of Video Sig-
`nals,” IEEE Proc. part F, vol. 129, no. 1, pp. 28-40,
`February 1982. The image is partitioned into L blocks
`for transform coding. Information bits allocated to each
`block are AB/L bits/iteration. If the block size is NXN
`pixels,
`the incremental bit rate for each iteration is
`AB/(L-N2)=Ar bits/pixel-iteration, and the accumu-
`lated bit rate is i~Ar at the i-th iteration.
`In order to minimize distortion in the reconstructed
`image,
`
`f f [u(kJ) — u.(k./)l2
`
`is minimized for all i’s where fi(k,l) is the original pixel
`value and u,(k,l) is the reconstructed pixel value at the
`i-th iteration at pixel location (k,1). In zonal transform
`coding minimization of the equation is obtained by de-
`signing an optimal bit assignment matrix, also called bit
`assignment map, for the transform coefficients of the
`blocks. One method to design the bit assignment map
`for a given bit rate is based upon rate-distortion theory
`as discussed by Davisson “Rate Distortion Theory and
`Applications,” Proc. IEEE, vol. 60, pp. 800-808, 1972.
`
`6
`
`

`

`4,698,689
`
`5
`The rate-distortion theoretic approach assumes that the
`transform coefficients are independently Gaussian dis-
`tributed and allocates a number of bits to a coefficient
`according to its standard deviation. The optimally as-
`signed number of bits for each coefficient
`is then
`rounded to its nearest integer and the negative values
`are set to zero. Let b,(k,l) and b,~+1(k,l) be the numbers
`of bits allocated to the transform coefficient at (k,l) in
`the i-th and (i+1)th iterations, respectively. The num-
`ber of bits, Ab,-+1(k,l), corresponding to the incremental
`information Ab,-+1(k,l) to be sent for the coefficient at
`(k,l) in the (i+1)th iteration is
`
`N7i+l(k-0=bi+l(k:0—bi(/\'~0- -
`
`The bit assignment rule based upon rate-distortion the-
`ory guarantees Ab,-+1(k,l) to be always nonnegative.
`
`Bit Assignment Maps of FIGS. 2A and 2B
`
`An example of bit assignment maps and correspond-
`ing incremental bit assignment maps designed for an
`image with the standard deviation matrix shown in the
`table of FIG. 3 at the incremental bit rate of 1 bit/pixel-
`iteration is shown in FIGS. 2A and 2B. FIG. 2A(1)-(8)
`indicate the number of bits assigned to each quantized
`transform coefficient of a block to provide a series of
`sets of quantized transform coefficients. FIG. 2B(1)—(8)
`indicates the assignment of bits added on each iteration
`to generate the sets of FIG. 2A(1)—(8), respectively.
`The data corresponding to each of the incremental bit
`assignment maps of FIG. 2B(1)—(8) is transmitted dur-
`ing each of a plurality of transmission sequences.
`The sequence of bits allocated to leach transform
`coefficient can be read from the maps at its correspond-
`ing location. For example, the bit assignment sequence
`is “51110000” for the DC term (0,0) and “311l1100” for
`the AC term at (0,1). See FIG. 2B(1)—(8). The total
`number of bits assigned to each transform coefficient is
`8 in order to match the resolution of the input image.
`' See FIG. 2A(8). The scheme can be viewed as slicing
`the full bit assignment map into layers of incremental bit
`assignment maps and sending the information corre-
`sponding to a slice of the full bit assignment map at each
`iteration or transmission sequence. As shown in FIG.
`2B(1) there are 8 coefficients transmitted, at various
`degrees of precisions, in the first iteration.
`When the incremental bit rate is reduced, the total
`number of incremental bit assignment maps is increased.
`The overhead information corresponding to those maps
`may be large if the incremental bit rate is very small. In
`any event, there is no need to send the incremental maps
`as side information, since both the transmitter and re-
`ceiver can design the same maps based upon the stan-
`dard deviations of transform coefficients that are trans-
`mitted beforehand, a modest amount'of side informa-
`tion.
`
`Embedded Quantization
`The progressive image transmission and reconstruc-
`tion scheme described above requires the quantizer and
`the dequantizer to operate so as to make progressively
`finer reconstructions based upon the already received
`information combined with the additional information
`received at each iteration. In the example illustrated by
`the bit assignment matrices of FIGS. 2A and 2B, 5 bits
`are allocated to.the DC component (0,0) in the first
`iteration (FIG. 2B(1)) and one additional bit in each of
`the next three iterations (FIGS. 2B(2), (3), and (4)).
`Therefore, the DC term is initially quantized by a 5-bit
`
`6
`quantizer (FIG. 2A(1)); quantization is refined to 6 bits
`in the second iteration (FIG. 2A(2)), to 7 bits in the
`third iteration (FIG. 2A(3)), and so forth. Let y,- and
`y,-+1 be the binary representations of the b,- and b,-+1-bit
`quantizer outputs corresponding to a transform coeffici-
`ent x respectively; then y,-+1 should be able to be repre-
`sented as (y,-, Ay,-+1) so that the previous output symbol
`is embedded within the current output symbol. Conse-
`quently, a finer reconstruction value x,-+1 can be ob-
`tained from the already received y,- and the additional
`information Ay,-+1 in the (i+ l)th iteration.
`An embedded quantization scheme is achieved by
`aligning the thresholds (the value which determines
`whether a 0 or a 1 will be the assigned digit) of succeed-
`ing levels of quantization. In designing the particular
`thresholds, and the reconstructed values to be assigned
`to each 0 or a 1 upon dequantization, a particular quan-
`tizer is chosen as the reference and the values are deter-
`
`mined with regard to the mean-squared quantization
`error. In addition, since the DC transform coefficient
`has a Gaussian distribution and the other coefficients,
`the AC coefficients, a Laplacian distribution,
`the
`thresholds and reconstructed levels for DC and AC
`coefficients are different. Tables 1 and 2 give suitable
`threshold and reconstructed levels having threshold
`aligned quantization for a Gaussian distributed value
`and a Laplacian distributed value, respectively, quan-
`tized from 1 to 8 bits. Only the positive levels are shown
`in Tables 1 and 2, the negative levels being symmetric
`therewith. Thus, the values of the transform coefficients
`quantized at each iteration- (FIG. 2A(l)-(8)) in accor-
`dance with the threshold levels of Tables 1 and 2 and
`reconstructed as received data is accumulated in accor-
`dance with the reconstructed levels of Tables 1 and 2
`provides an embedded quantizing scheme for accumu-
`lating information over a sequence of iterations.
`TABLE 1
`
`Threshold aligned nonuniform quantizer: Gaussian source
`Threshold levels for 1 bit
`0.0000
`Threshold levels for 2 bits
`0.0000,l.0993
`Threshold levels for 3 bits
`0.0000,0.5224,l.0993.l.8435
`Threshold levels for 4 bits
`0.0000,0.2582,0.5224,0.7996,l.0993,1.437l,1.8435,2.4008
`Threshold levels for 5 bits
`0.0000,0.l288,0.2582,0.3892,0.S224,0.6589,0.7996,0.9459,
`l.0993,l.2622,l.4371,1.6290,l.8435.2.0945.2.4008,2.8843
`Threshold levels for 6 bits
`0.0000,0.0643,0.l288,0.l934,02582,0.3235,0.3892,0.4555,
`0.5224,0.5902,0.6589,0.7286,0.7996,0.87l9,0.9459,l.02l6,
`l.O993,1.1794,l.2622,l.3479,l.4371,l.5307,l.6290,1.7329,
`1.8435,1.9639,2.0945,2.2389,2.4008,2.6l66,2.8843,3.3159,
`Threshold levels for 7 bits
`0.0000,0.0322,0.0643,0.0965,0. l288,0.l6l0,0.1934,0.2257,
`0.2582,0.2908,0.3235,0.3S63,0.3892,0.4222,0.4555,0.4888,
`0.5224,0.5562,0.5902,0.6244,0.6589,0.6936,0.7286,0.7639,
`0.7996,0.8356,0.87l9,0.9087,0.9459,0.9835,1.02l6,l.0602.
`l.0993,l.1391,1.1794,l.2204,l.2622,l.3047,l.3479,l.392l,
`1.4371,l.4834,l.5307,1.5792,l.6290,l.6802,l.7329,l.7873,
`1.8435,1.9025,1.9639,2.0277,2.0945,2.l648,2.2389,2.3l73,
`2.4008,2.5038,2.6166,2.7422,2.8843,3.0759,3.3l59,3.7087
`Threshold levels for 8 bits
`0.0000,0.0l61,0.0322,0.0482,0.0643,0.0804,0.0965,0.1 126,
`0.l288,0.l449,0.l6l0,0.1772,0.l934,0.2095,0.2257,0.2420,
`0.2582.0.2745,0.2908,0307l,0.3235,0.3398,0.3563,0.3727,
`0.3892,0.4057,0.4222,0.4388,0.4555,0.4721,0.4888,0.5056,
`0.5224,0.5393,0.5562,0.5732,0.5902,0.6073,0.6244,0.64l 6,
`0.6589,0.6762,0.6936,0.7l l l,0.7286,0.7462,0.7639,0.78l 7,
`0.7996,0.8 l 75,0.8356,0.8537,0.87 l 9,0.8903,0.9087,0.9272,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`7
`
`

`

`4,698,689
`
`8
`
`7
`TABLE 1-continued
`
`Threshold aligned nonuniform quantizer: Gaussian source
`0.9459,0.9646.0.9835,1.0025.1.02l6,1.0408.1.0602.1.0797,
`l.0993,1.1 191.1.1391,1.1592.l.1794.1.l999.1.2204.l.2412,
`1.2622,1.2833.1.3047,1.3262,l.3479.l.3699.1.3921.1.4145,
`1.437l,l.4601,1.4834,1.5069.1.5307.1.5548.l.5792.1.6040.
`1.6290,].6544.1.6802,1.7064.1.7329.1.7599.l.7873.1.8152.
`l.8435,l.8728,1.9025,1.9329.1.9639.1.9955,2.0277.2.0607.
`20945.2.1292,2.1648,12013,2.2389,2.2775.2.3l73.2.3584,
`2.4008.2.4512.2.5038,2.5589.2.6166,2.6777.2.7422.2.8109,
`2.8843.2.9755,3.0759,3.1882,3.3l59,3.4896,3.7087,4.07l2
`Reconstruction levels for 1 bits
`0.7980
`Reconstruction levels for 2 bits
`0.4968,l.6052
`Reconstruction levels for 3 bits
`0.2553,0.7887.l.4060,2.2354
`Reconstruction levels for 4 bits
`0.1284,0.3880,0.6568,0.9423,l.2562,1.6180.2.0690.2.7326
`Reconstruction levels for 5 bits
`00643.0.1932,0.3232.0.455l.0.5897.0.7280..0.8712.1.0206.
`1.l781.l.3462,l.5284,1.7296.1.9588,2.2303..2.5928.3.1757
`Reconstruction levels for 6 bits
`0.0322,0.0965.0.1610,0.2257,0.2907.0.3562,0.4222,0.4887.
`0.5561 ,O.6243.0.6935.0.7638,0.8354,0.9085.0.9832. 1 .0599.
`1.1387,1.2201.1.3043.1.3916.1.4828.1.5786.l.6795.1.7864.
`1.9014,2.0263,2.1629,2.3148,2.4990,2.7342.3.0536,3.5782
`Reconstruction levels for 7 bits
`0.0161 .0.0482,0.0804.0. 1 126.0.1449,0.1772.0.2095.0.2420.
`0.2745,0.307I,0.3398,0.3727.0.4057.0.4388,0.4721.0.5056,
`0.5392,0.5731.0.6072.0.64l6,0.6762,0.7110,0.7462.0.7817.
`0.8175.0.8536,0.8902,0.9272,0.9646. l.0024,l.0407.1.0796.
`1.1190,l.1591.1.l998.1.2411,1.2832,l.3261,l.3698.1.4144,
`1.4600,1.5068.1.5547,].6038,1.6543,l.7062,1.7597.1.8150.
`1.8725.1.9326.1.9931,2.0604.2.1288.2.2008,2.2769.2.3577.
`2.4502.2.5575.2.6759,2.8085.2.9710.3.1807,3.4687,3.9487
`Reconstruction levels for 8 bits
`0.0080.0.024l,0.0402,0.0563.0.0724,0.0885.0.1046.0.1207.
`0.l368,0.1529,0.1691.0.1853,0.2014,0.2176,0.2339.0.2501.
`0.2664,0.2826.0.2989.0.3153.0.3317.0.3480,0.3645,0.3809,
`0.3974,0.4l40.0.4305.0.4471.0.4638,0.4805.0.4972,0.5140.
`O.5308,0.5477,0.5647.0.5816,0.5987.0.6158,0.6330,0.6S02.
`0.6675.0.6849,0.7023,0.7198.0.7374.0.7S50,0.7728.0.7906,
`0.8085,0.8265,0.8446.0.8628.0.8811,0.8994.0.9179.0.9365.
`0.9552.0.9740.0.9929,1.0120,1.0312.1.0504,1.0699.1.0894,
`l.1092,1.1290,1.1491.l.1693.1.1896.l.2101.1.2308,1.25l6,
`1.2727,1.2939.1.3154.1.3370,1.3589.1.3809.1.4-032,1.4258.
`1.4486,1.4717.1.4951,1.5187,l.5427.1.5670,1.5915.1.6l64.
`1.6416,1.6672.l.6932.l.7196.l.7463,1.7735,1.8011.1.8292,
`1.8580,1.8875,1.9176,l.9482.1.9795,2.0114,2.044l.2.0774,
`2.1117,2.1468.2.1828.2.2198.2.2579,2.2971.2.3375,2.3792.
`2.4255.2.4770,2.5307.2.5870.2.6463.2.7090.2.7755.2.8-163,
`
`2.9279,3.0231,3.1287,3.24-76.3.3942,3.5849.3.8489,4.2935/
`
`20
`
`30
`
`45
`
`
`
`TABLE 2-continued
`Threshold aligned nonuniform quantizer: Laplacian source
`0.9l98,0.9684,1.0l82,1.0692.1.l215.1.1750,l.2300.1.2864.
`1.3444.1.4041,].4656,1.5290,l.5942,1.66l6,1.7312,1.8031,
`1.8776.1.9552,2.0358.2.1196.22063,2.2978.2.3929.2.49Z6,
`2.5971.2.7090,2.8271.2.9523.3.0852,3.2277,3.3805,3.5453,
`3.7240,3.954-0.4.2121.4.5074.4.8509,5.3390.5.9777,7. 1046
`Threshold levels for 8 bits
`0.0000,0.0l56,0.0313,0.0471,0.0631,0.0791.0.0953,0.1 1 16.
`0.1281.0.l446.0.l613.0.1782,0.1951,0.2122,0.2295.0.2469,
`0.2644,0.282l,0.2999,0.3l79,0.3360.0.3543.0.3728,0.3914.
`0.4l02,0.429l.0.4482.0.4675,0.4870.0.5066,0.5265.0.5465,
`O.5667,05871,0.6078,0.6286,0.6496,0.6709,0.06923,0.7140,
`0.7359.0.7580,0.7804,0.8030.0.8259,0.8490,0.8723,0.8959,
`0.9198.0.9440,0.9684,0.9932,1.0182,1.0436.1.0692,1.0952,
`1.1215,].148l.1.1750,1.2023.1.2300.1.2580,l.2864.1.3l52,
`1.3444,1.3741,1.4042,1.4347,1.4656.1.497l.1.5290,l.5613,
`1.5942.1.6276.1.6616.1.6961.1.7312.1.7668.1.803l,1.8400,
`1.8776.l.9l61.1.9552,1.995l.2.0358.2.0773.2.1196,2.1627,
`2.2068,2.25 1 8,2.2978.2.3448.2.3929,2.4422.2.4926,2.5442.
`2.5971,2.6523,2.7090.2.7672,2.8271.2.8888,2.9523,3.0l77.
`10852.3.1553.3.2277,3.3028.3.3805,3.4613.3.5453,3.6328,
`3.7240.3.8359,3.9540,4.0791.4.212l.4.3546.4.5074,4.6722,
`4.8509,5.0809,5.3390,5.6343,5.9777.6.4659,7.l046.8.2314
`Reconstruction levels for 1 bit
`0.7071
`Reconstruction levels for 2 bits
`0.4710.2.0515
`Reconstruction levels for 3 bits
`0.2459.0.8857.l.7948,3.3042
`Reconstruction levels for 4 bits
`0.1240,0.4048.0.7287.1.1110,1.5778,2.1773,3.0169.4.43] 1
`Reconstruction levels for 5 bits
`0.062 1 ,0. 194-1,0.3348,0.4855,0.6479,0.8239,1.0158, 1.2271 ,
`1.4620.l.7265,2.0295,2.384l,2.8133,3.3572.4.1438,5.5580
`Reconstruction levels for 6 bits
`0.031 l,0.0951,0.161 1,0.2292,0.2996,0.3724,0.4479.0.5261,
`0.6073,0.69l9.0.7799.0.8718,0.9679.1.0686,1.1743,1.2857,
`1.4033.1.5280,1.6605,1.8019.1.9537,2.1 l78.2.29S8.2.4901.
`2.7059,2.9483.3.2226,3.5384,3.9402,4.484l.5.2706,6.6848
`Reconstruction levels for 7 bits
`0.0155,0.0471.0.0791,0.1 1 16.0.1446.0.‘l781,0.2122,0.2468,
`0.2820.0.3178,0.3542,0.3913.0.4290.0.4674,0.5065,0.5464.
`0.5870,0.6285,0.6707.0.7139,0.7579,0.8029,0.8488.0.8958,
`0.9438,0.9930,1.0434,1.0950,1.1479.l.2022,1.2578,1.3150,
`1.3739,1.4344,1.4968,1.5611.1.6274.l.6958,1.7665,1.8397.
`1.9157,1.9947,2.0768,2.1623,2.2513.2.3443,2.44l6,2.5435,
`2.6516.2.7664-,2.8878.3.0167,3.1541,3.30l4,3.4597,3.6309,
`3.8328,4.0752.4.3495.4.6653,5.0671.5.6109,6.3975.7.8117
`Reconstruction levels for 8 bits
`0.0078,0.0234,0.0392,0.0551.0.071 1,0.0872.0.1035,0.1 198.
`0.1363.0.1530,0.1697.0.1866.0.2037.0.2208.0.2381.0.2556,
`0.2732.0.2910.0.3089.0.3269.0.3451,0.3635.0.3820.0.4-007,
`0.4196.0.4386.0.4578,0.4772,0.4-968.0.5165,0.5364,0.556S,
`0.5769,0.5974.0.6181,0.6390,0.6602.0.6815.0.7031.0.7249.
`0.7469,0.7692.0.7916.0.8144.0.8373.0.8606.0.8840,0.9078,
`0.9318,0.9561,0.9807.1.0056,1.0308.1.0563.1.082l.1.1082.
`1.1347.1.1615,1.1886.l.2161.1.2439.1.272l.1.3007,1.3297.
`l.359l,1.3890.l.4-193.1.4500.1.4812,l.5129.1.5450,1.5777.
`1.6108,].6445,1.6787,1.7135,1.7489.1.7848,l.8214,1.8587,
`1.8967,1.9355,1.9750,2.0153.2.0563,2.0982,2.1409.2.1845,
`2.2290.2.2746.2.3211.2.3686,2.4173.2.467I,2.5181.2.5703,
`2.6243.2.6803.2.7377.2.7967,2.8575.2.9200.2.9845,3.0509,
`3.1197.3.1909,3.2646,3.3409,3.4202.3.5025.3.5881.3.6774,
`3.7785,3.8933,4.0147,4.1436.428I0.4.4283,4.5866,4.7578,
`
`4.9596.5.2021,5.4764.5.7922,6. 1939.6.7378,7.5243,8.9385
`
`Simulation Results
`
`FIGS. 4 and 5 are simulations illustrating the progres-
`sive transmission and reconstruction schemes in accor-
`dance with the present invention and in accordance
`with the zig-zag scanning approach as described for
`example in the above-mentioned article by Tescher and
`Cox. In each example the original image data consists of
`512 X 512 pixels with 8 bits per pixel. Each zone or
`block is 16X 16 pixels. In the system in accordance with
`
`TABLE 2
`50
`Threshold aligned nonuniform quantizer: Laplacian source
`Threshold levels for 1 bit
`0.0000
`Threshold levels for 2 bits
`0.0000.1.3444
`Threshold levels for 3 bits
`0.0000,0.5667,l.3444,2.597l
`Threshold levels'for 1 bits
`0.0000,0.264-4.0.5667.0.9198,1.3444.l.8776,2.597l,3.7240
`Threshold levels for 5 bits
`0.0000,0.128l,0.2644,0.4102.0.5667.0.7359,0.9198,1.1215,
`1.3444.1.5942.1.8776,2.2068.2.5971,3.0852,3.7240.4.8509
`Threshold levels for 6 bits
`0.0000.0.0631,0.1281,0.1951,0.2644,0.3360,0.4102.0.4870,
`0.5667,0.6496,0.7359,0.8259.0.9l98,1.0182,1.1215.1.2300.
`1.3444.1.4656,1.5942,1.7312.1.8776,20358,2.2068,2.3929.
`2.5971.2.8271,3.0852,3.3805,3.7240,4.2121,4.8509.5.9777
`Threshold levels for 7 bits
`0.0000,0.0313,0.0631,0.0953,0.1281.0.1613.0.1951,0.2295.
`0.264-4.0.2999,0.3360.0.3728,0.4102,0.4482,0.4870.0.5265.
`0.5667,0.6078,0.6496,0.6923.0.7359.0.7804,0.8259,0.8723,
`
`60
`
`65
`
`°
`
`8
`
`

`

`s
`
`4,698,689
`
`5
`
`45
`
`50
`
`9
`the present invention the bit assignment maps were
`designed based upon rate-distortion theory. In quantiz-
`ing the bits for the prior art zig-zag scanning scheme, an
`8-bit nonuniform quantizer in accordance with the
`teachings "in an article by Max “Quantization for Mini-
`mum Distortion” IEEE Transaction-Information The-
`ory, vol IT-6, pp 7-12, March 1960 was employed.
`The series of pictures in FIGS. 4 and 5 show the
`corresponding reconstructed images with data content
`of 1/32, 1/16, ,1,, §, §, 1,and2bits/pixel. These pictures 10
`simulate transmission and reception of data at a 1/32
`bit/pixel iteration for the first, second, fourth, eighth,
`sixteenth, thirty-second, and sixty-fourth iteration, re-
`spectively.
`As can be seen from FIGS. 4 and 5 during the earlier 15
`iterations the system in accordance with the present
`invention provides reconstructed images of finer detail
`and therefore superior picture quality than does the
`zig-zag scanning approach. After an accumulated data
`of the order of 1 bit/pixel (i=32), both systems produce 20
`good images and the difference in picture quality be-
`comes almost indistinguishable. Eventually, upon con-
`tinuing the transmission and reconstruction, both
`schemes employ the accumulated data of 8 bits/pixel
`and assign the full 8 bits to each transform coefficient. 25
`At this stage the quality of the quantizing and dequan-
`tizing scheme determines the superior picture quality.
`Thus, the progressive transmission and reconstruc-
`tion scheme for transformed images in accordance with
`the present invention is more efficient in delivering 30
`image quality than the zig-zag scanning approach. The
`reconstructed images from the two systems show differ-
`ent characteristics;
`those from the zig-zag scanning
`approach appear smoother, whereas those produced in
`accordance with the present invention contain more 35
`detail. Subjective comparison indicates that the ap-
`proach in accordance with the present invention is A
`p more than twice as efficient as the zig-zag approach in
`delivering the details of an image at low bit rates.
`1 While there has been shown and described what is 40
`considered a preferred embodiment of the present in-
`vention, it will be obvious to those skilled in the art that
`various changes and modifications may be made therein
`without departing from the invention as defined by the
`appended claims.
`.
`What is claimed is:
`l. The method of progressively transmitting an image
`comprising
`dividing an image into a predetermined array of zones
`of picture elements;
`performing a predetermined spatial domain-to-trans-
`form domain transformation of the picture ele-
`merits of each zone to provide a set of transform
`coefficients thereof;
`producing and transmitting for each zone during the 55
`first of a plurality of transmission sequences signals
`containing data representing several of the trans-
`form coefficients of the set in different degrees of
`detail; and
`V
`producing and transmitting for each zone during each 60
`subsequent sequence of said plurality of sequences
`signals containing data on several of the transform
`coefficients of'the set which when combined with
`data transmitted during preceding sequences pro-
`vide cumulative data representing the set of trans- 65
`form coefficients of the zone in different degrees of
`increasingly finer detail.
`2. The method in accordance with claim 1 wherein
`
`,
`
`I
`,_,
`'
`,
`
`
`10
`each of said zones represents an image area of uni-
`form size and shape having an equal number of
`picture elements.
`3. The method in accordance with claim 2 wherein
`said predetermined spatial domain-to-transform do-
`main transformation is a discrete cosine transfor-
`mation.
`4. The method of progressively transmitting an image
`comprising
`dividing an image into a predetermined array of
`blocks of picture elements;
`performing a predetermined spatial domain-to-trans-
`form domain transformation in two dimensions of
`the picture elements of each block to provide trans-
`form coefficients thereof;
`quantizing transform coefficie