throbber
Exhibit 2008
`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-01897
`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
`
`
`

`
`4,698,689
`
`gag“gymgmawn”F
`anyanynunnananyannnnnnnnnnnaananannaW.
`
`
`
`
`(8)nWanWamn3.
`
`
`
`U.S.PatentOct.6,1987
`
`
`aaaaAcanan.2anZZanan0%3%ém3%ammm.Hg.”ammmgmmmm
`
`
`
`
`bnaaaanagag”aaaaHananaaaanaa
`Han.5ananyaanya.
`)2...,n)g)5)”)a)5)F
`
`
`
`3
`
`

`
`Sheet3 of3
`
`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 coefficients of each block into a
`series of predetermined sets of quantized transform
`coefficients, some of the quantized transform coef-
`ficients of each set representing their correspond-
`ing transform coefficients in di

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket