Progressive Image Transmission by Refining Sampling Lattice
`
`tKrit Panusopone and :tK. R. Rao
`The University of Texas at Arlington
`Department of Electrical Engineering
`Box 19016, Arlington, TX, 76019
`t panu@ee.uta.edu, :t rao@ee .uta.edu
`
`Abstract
`
`This paper applies nonuniform sampling technique
`to progressive image transmission (PIT) so that it
`can place more attention on vital parts of the image.
`The system first segments an image based on quad-tree
`structure and the Tesulting variable block size data has
`it suitable Mm]Jling lattice under a tolemble loss. With
`this information, transmitter can adjust th e lattice fo r
`each region matched wzth the desired bit rate and en·or.
`Simulation results show that low oveThead and informa(cid:173)
`tion are necessary for each stage of tr-ansmission while
`improved images can be reconstructed at the receiver.
`
`I. Introduction
`
`Digita.l image data can be usually represented as a
`two dimensional matrix. This formation corresponds
`to uniform sampling of an image acquisition system.
`Each element in the matrix which is called a sample
`or a pixel (picture element) contains intensity of its
`associated location in the imagP-. [n this sense, digital
`image is a representation of an analog image by a finite
`amount of data and the closer the samples are, the less
`the approximation error based on the original image.
`Thus, a huge amount of densely positioned samples is
`required for high quality reprodu ction of a digital im(cid:173)
`age. In view of t his shortcoming, various algorithms
`have been proposed to reduce the size of storagp, data
`[1] or to speed up the transmission and for display(cid:173)
`[3]. Thes'~ techniques share the
`ing the digital image
`same goal that is to maintain the highest reproduction
`quality.
`Progressive image transmission (PIT) [5] is one such
`kind of a technique. It is aimed to shorten user time in
`accessing and browsing remote image database. This
`adva.ntage comes from the abili ty of PIT to provide
`information of au image in hierarchical order of impor-
`
`tance and to build a higher quality image upon the
`user's request. Some PIT algorithms have the ability
`to produce an exact version of input image at the last
`stage. The proposed technique can be applied to both
`results. By rearranging transmission order of sampled
`data from the traditional raster scan method, trans(cid:173)
`mitter can successively send samples in such a way that
`it will gradually enhance the reproduction quality and
`approximation error will be distributed evenly through(cid:173)
`out the entire output image. Moreover, the proposed
`system transmits patterns instead of the original infor(cid:173)
`mation except during the first stage so it a lways uses
`a small amount of data in each stage.
`
`2. Efficient Image R epresentation
`
`For uniform sampling, digital image samples liP in
`some arbitrary pattern. Sampling density which is
`mea..~ured from the separation among pixels specifies
`spatial resolution of an image. To avoid aliasing, high
`resolu tion image which has sampling density above
`Nyquist rate is required. This restriction results in
`a lot of redundancy when applying to uniformly sam(cid:173)
`pled images. Natural image is a kind of nonstationary
`signal. Tt. contains both homogeneous regions in back(cid:173)
`ground areas and nonhomogeneous regions in detail ar(cid:173)
`eas. With regular lattice like the one in uniformly sam(cid:173)
`pled irnap;es, uniform sampling places the same number
`of samples over the entire image thereby causing ei(cid:173)
`ther loss of information due to aliasinf!, or redundancy
`of information. ThiR dilemm a can be avoided by us(cid:173)
`ing efficient image representation. This representation
`which first analyzes local characteristir_s of each region
`allocates samples suitable with tl1 e expected amount of
`information i.e. less number of samples in background
`n.nd vice versa.
`Theoretically, sampling density is specified by cutoff
`frequenc.y of da.ta. However , accurate frequency spec(cid:173)
`trum becomes complex for a nonstationary data since
`
`1058-6393/97 $10.00 © 1997 IEEE
`
`1294
`
`Vedanti Systems Limited - Ex. 2011
`Page 1
`
`

`
`82818(1)00(808079
`8181818180008080
`8181818080808080
`8281818181818181
`8281818181818181
`8281818181818181
`828281818(1797978
`80808(17978787776
`Origina.l intensity of
`8x8 pixels region
`
`81
`
`81
`
`81 81 80 80
`
`81 81 81 81
`
`81 81 81 81
`
`8281808080808079
`8181818180808080
`8181818080800080
`8281818181818181
`8231818181818181
`8231818181818181
`8232818180797978
`8080807978787776
`
`76-79 76
`80 79 78 76
`Sam ple for Sample for
`Sample for
`Sample for
`stage 1
`stage 3
`stage 2
`stage 4
`Figure 1. Example of the sampling lattice
`during transmission.
`
`its characteristics change among data. This kind of
`fluctuation refrains regular sampling lattice from opti(cid:173)
`mal result. Irregular lattice, on the other hand, seems
`to be a promising tool for efficient image representa(cid:173)
`tion . It will not have any restriction from sampling
`struct.ure but it will have trouble with lattice forma(cid:173)
`tion. Nonuniform lattice basically moves the prob(cid:173)
`lem from image representation to lattice representa(cid:173)
`tion. This problem is common in any adaptive system.
`We cannot afford to have infinite lattice formations.
`Only some of them are worth appearing in a practical
`system. In this paper, we use lattice which is locally
`regular . By adjusting the size of the area, the lattice
`can also be adjusted. Size of area. has to be controlled
`in an effective way for the efficiency of the system.
`
`Transmitter uses quad-tree parliontioning [4] to an(cid:173)
`alyze and control details in each region of the image.
`Image is successively split based on tree structure un(cid:173)
`til it conforms to the uniformity criterion and becomes
`leaf of the tree. Additionally, the splitting process halts
`when it reaches bottom level of the tree and that region
`is automatically converted to a leaf. If a degree of de(cid:173)
`tail is a criterion , only limited an10unt of information
`is allowed in each leaf unless that leaf is at the bottom
`level. Using leaves in the tree structure, transmitter
`can place samples in a more efficient manner that is
`by giving an equal number of samples to each leaf. In
`this way, all samples will represent th same amount of
`information. In other words, loss will propagate uni(cid:173)
`formly over the image. The system can also control the
`error by adjusting the sample allocation to match with
`the detail within a region.
`
`3. Transmission Algorithm
`
`3.1. Lossless approach
`
`The major attribute of PIT is that it will set up a
`sequence of information for different quality levels of
`images. The proposed technique achieves this function
`by using a distinct sampling lattice for each stage of
`transmission. At the first stage, a crude version of an
`image is tolerable and hence the diluted lattice, say
`one sample for each region, is applied to all leaves. To
`obtain better results in later stages , sampling lattice
`is changed to the denser one. The lattice for the final
`stage of transmission has the same sampling density as
`the original image which means that all samples will be
`sent and the reproduced image will be a replica of the
`input image. Unlike other traditional multiresolution
`techniques, lattice density in the proposed technique is
`globally nonuniform . As mentioned before, this struc(cid:173)
`ture yields less error. Example of sampling lattice for
`8 x 8 pixels region is shown in Fig.l. Task of the re(cid:173)
`ceiving end is adding the received data to the estimated
`value at the right position and then filling the remain(cid:173)
`ing positions by means of linear interpolation.
`A major concern in designing a PIT system is to
`minimize the overhead and eliminate the redundancy
`involved in multitransmission. Only information of
`quad-tree structure is required thereby overhead in(cid:173)
`cluding the transmission is small. To utilize the inher(cid:173)
`ent correlation within a region, the proposed scheme
`exploits prediction for the nontransmitted samples.
`This prediction which is required at both transmitter
`and receiver is hii.Sed on the information within its re(cid:173)
`gion only. Receiver recovers a sample with predicted
`value and the received data, while transmitter always
`sends the error between predicted value and the actual
`value. Error for the previous stage data is always zero
`because the information is already known and there is
`no need to retransmit this error. Since the range of in(cid:173)
`tensities i.e., the difference between the maximum and
`the minimum intensity in the whole area is used as the
`criterion for quad-tree partitioning, the receiver can get
`an idea of the expected intensity when it receives the
`first sample. For example, if the range threshold is
`32, all pixels in that region are guaranteed to have in(cid:173)
`tensities between 68 and 132 (assuming that first data
`is 100) . Transmitter can use shorter length code for
`transmitting the prediction information such as 6 bits
`for the previous case. This procedure yields an exact
`replica at the final stage. To obtain a lower bit rate,
`the lossy version of this technique will be described in
`the next. section.
`
`1295
`
`Vedanti Systems Limited - Ex. 2011
`Page 2
`
`

`
`PSNR
`(dB)
`
`38
`
`36
`
`34
`
`32
`
`28
`
`26
`
`lossless method
`lossy method .fj-
`
`I
`
`,i
`
`_../
`:~---
`
`/i
`~/ ~
`/ i
`30 / j
`
`Figure 2. Block diagram of the proposed
`system.
`
`3.2. Lossy approach
`
`Fewer bits are possible to simplify the procedures
`described in the previous section by lossy approaches.
`Lossy encoder attempts to represent a prioritized se(cid:173)
`quence of data with the smallest size and error. Cotler
`performs well in this system since it will face a more
`specific data. Quad-tree structure separates detail area
`from background . Slightly correlated nodes that il.re
`leaves simply because they are in the bottom level are
`considered to be detail areas. The remaining back(cid:173)
`ground which is highly dependent can be approximated
`without significant distortion and coder can be de(cid:173)
`signed efficiently by concentrating on detail parts. The
`proposed system incorporates this feature in its lossy
`mode . Vector quantization (VQ ) is selected to code
`samples on lattices because it can exploit nonlinear re(cid:173)
`lationship of the main detail well.
`
`Input vector is constructed based on ~.:haracteristics
`of samples in lattice. Several input vectors are set up
`for each area corresponding to lattice density. Predic(cid:173)
`tion process is employed in bar.kground area to uti(cid:173)
`lize its dependent nature as previously described. Ex(cid:173)
`cept the first stage, components of a background in(cid:173)
`put vectors comprise the difference between samples
`in the current lattice and samples in the lower resolu(cid:173)
`tion lat tice. The~e input vectors try to find the addi(cid:173)
`tional detail of the area based on the previous lattice.
`System quantizes these W'ctors with appropriate code(cid:173)
`books and gives an estimated additional detail to form
`the higher density lattice. Prediction technique, how(cid:173)
`ever, is not effective in detail regions where additional
`detail is less correlated wi th the infor ma.t.ion ofth e pre(cid:173)
`vious lattice. Input vectors in this case arc basically a
`group of samples of the higher density lattice.
`
`1
`
`2
`
`3
`Stage
`
`4
`
`5
`
`Figure 3. Comparison performance of Lena
`with the proposed coding system using dif(cid:173)
`ferent approaches.
`
`4. Simulation Results
`
`Structure in Fig.2 has been used to evaluate the per(cid:173)
`formance of the proposed system. Transmitter sends
`information on irregular lattice upon request from re(cid:173)
`<.:eiver. In this experiment, 3 densities of lattice rele(cid:173)
`vant. to the initial configu ration are used to produce a 5
`transmission stages. Configuration of lattice is deter(cid:173)
`mined fro m size of partitioned region after quad-tree
`decomposition. This size depends on its local informa(cid:173)
`t ion in terms of range but: it must cover at least 4 x 4
`pixels . All background leaves have range under the
`predefined thre"hold and occur in variable sizes while
`the remaining 4 x 4 pixel leaves are detail nodes. Pre(cid:173)
`diction technique as previously explained is adopted in
`t he input vector formation to allow a higher compres(cid:173)
`sion ratio. To csto.blish the transmission , tree structure
`overhead (1 bit per node in the tree) is first transmitted
`followed by data of the first stage. Empiric~tl l~tttice of
`each stage is ta bula.ted in Table 1.
`Four different codebooks arc used to quantize input
`vectors in subsequent st.ages. Each code book is trained
`by 6 typical images to code a particular lattice. Table 2
`shows pa.rarneters of codebooks used in this paper. Lin(cid:173)
`ear interpolation specifies the missing samples in the
`original resolution based on information on the current
`lattice
`[2). Test image 'Lena' which has resolution
`512 x 512 pixels with 8 l.>its per pixel is transmitted
`with the proposed method . Results of the transmis(cid:173)
`sion with a threshold of .50 are listed in t erms of PSNR
`(Table 3) . Overhead embedded in trausmis~ ion in this
`
`1296
`
`Vedanti Systems Limited - Ex. 2011
`Page 3
`
`

`
`References
`
`[1] A. K. Jain . Image data compression : A review. Proc.
`IEEE, 69:349-389, March 1981.
`[2] K. Panusopone, F. Cheevasuvit and K. R. Rao. Adap(cid:173)
`tive subsampli ng for image compression . In Conf. Rec.
`of the 29th Asilomar Conference on Circuits, Systems
`and Computers, Pacific Grove, CA, November 1995.
`[3] M. Rabbani and P. W. Jones. Digital Image Compres(cid:173)
`sion Techniqu e.l. SPIE Press, Bellingham, WA, 1991.
`[4] H. Samet. Data structure for quad-tree approximation
`and compression. Commun . A CM, 28:973-993, Septem(cid:173)
`ber 1985.
`[5] K. H. Tzou. Progressive image transmission : A re(cid:173)
`view and comparison of techniques. Optical Engineer(cid:173)
`ing, 26:581-589, July 1987.
`
`(a)
`
`Figure 4. Subjective results of the pro(cid:173)
`posed system at (a) stage 1, (b) stage 2,
`(c) stage 3, (d) stage 4, (e) stage 5.
`
`case is 8765 bits (0.033 bpp). Figure 3 plots the per(cid:173)
`formance of the VQ based lossy system together with
`that of lossless system. Subjective results of 'Lena' are
`demonstrated in Fig. 4. It may be observed that the
`proposed system provides a pleasant quality at the low
`bit rate. It is also worth mentioning that improvement
`in detail area is important and an advance compression
`technique can be used at this process.
`
`T bl 1 L
`a e
`,atttce ensttJes
`d
`Stage Background leaf Detail leaf ·
`l x l
`lxl --
`1
`lxl
`2x2
`2
`2x2
`2x2
`3
`2x2
`4x4
`4
`4x4
`4x4
`5
`
`Table 2 Codebook Parameters
`Stage
`dimension
`codebook size
`256
`3
`2
`1-----·---
`256
`3
`3
`12
`1024
`4
`12
`256
`5
`
`Table 3. Simulation results for Lena image
`Stage Bit Rate PSNR
`(bpp)
`(dB )
`0234
`26.687
`0.304
`28.437
`0.435
`30.585
`0.522
`30.776
`0.653
`31.404
`
`1
`2
`3
`4
`5
`
`5. Conclusions
`
`New transmission system has been developed in this
`paper. It serves the requirements of PIT well because
`it tries to retrieve the vital information in the area first.
`Loss in the reconstruction process is also limited with
`the benefit of quad-tree decomposition. Moreover, this
`scheme can provide a graceful improvement over the
`crude data of the previous stage by using the appro(cid:173)
`priate lattice density. This method is applicable for
`lossless transmission. Prediction based VQ is also em(cid:173)
`ployed in the lossy system for low bit rate compression.
`Results of the proposed system show a good quality of
`reconstructed image at the low hit rate.
`
`1297
`
`Vedanti Systems Limited - Ex. 2011
`Page 4
`
`

`
`(b),(c)
`
`(d),( c)
`
`1298
`
`Vedanti Systems Limited - Ex. 2011
`Page 5