In this cl1apter, we introduce three nonstandard image coding tecl1niques: vector quantization (VQ)
`(Nasrabadi arid King, 1988) , fractal coding (Barn.sley and Hurd, 1993; Fisher, 1994; Jacquin , 1993),
`and n1odel-based coding (Li et al., 1994).
`
`9.1
`
`INTRODUCTION
`
`The VQ, fractal coding, and n1odel-based coding tecl1niques have not yet been adopted as an jmage
`coding standard . However, due to their unique features tl1ese techniques may find some specia l
`application s. Vector quanti zation is an effectiv·e technique for performing data compressio n. Tl1e(cid:173)
`oretically, vector quantization is always better than scalar quantization because it fufly exploits th.e
`correlatio11 between components within the vector. The optimal coding performance will be obtained
`when the dimension of the vector approacl1es infinity, a11d then tl1e correlation between all com(cid:173)
`ponent s is expl oited for compression. Another very attractive feature of image vector quantization
`is that its decoding procedure is very sin1ple i11ce it only co11sists of table look-up_s. However, there
`are two n1aj or problen1s vvith image VQ techniques. The first is that the complexity of vector
`quanti zation exponentially increases with tl1e increasing dimensionality of vectors·. Tl1erefore, for
`vector quanti zation it is in1portanl to soJve tl1e proble111 of how to design a practical coding syste111
`which can pro\1idc a reasonable performance under a given cornplexity constraint. The second
`major problen1 o·f image VQ is the need for a codebook, \Vhich causes se\1eral problems in practical
`application such as generating a universal codebook for a large number of images, scaling the
`codebook to fit the bit rate requirement, and so on. Recently, the lattice VQ schemes l1ave been
`proposed to addre ss tl1ese problems (Li, 1997) .
`Fractal theory has a lor1g history. Fractal-based techniques l1ave been used in s-everal areas of
`digital image proce ssi11g such as image segmentation, in1age sy11thesis, and con1puter graph ics, but
`only in recent years have they been extended to the applications of i·mage compression (Jacquin,
`1993). A fractal is a geometric form wl1ict1 l1as tl1e unique feature of l1aving extren1ely high visual
`self-similar irregular details wt1ile containi.ng very lo\v information content. Several n1ethods for
`image compressio r1 have bee.n developed based on different characteristics of fractals. One n1ethod
`is based on Iterated Function Systen1s (/ FS) proposed by Barnsley ( 1988). Tt1is metl1od uses the
`setl·-similar and self-affine property of fractals. Suct1 a syster11 consists of sets of transforn1ations
`including translatio n, rotation, and scalir1g. On the encoder side of a fractal image codjng system,
`a set of fractals is generated from the input in1age. These fractals can be used to recor1struct the
`image at tJ1e decoder side. Since these fractals are represented by very co1npact fractal transfor1J1a(cid:173)
`(1Qns, they require very small amounts of data to be expressed and stored as forn1ulas. Tl1erefore,
`the ihfor111ation needed to be transmitted is very s111all. Tl1e seoond fractal in1age codjn.g method
`is based on tlie fractal dimensio.n (Lu, I 993; Jang and Rajala, 1990). Fractal dimension is a good
`representation of the roughness of image surfaces. In this 111etl1od, tl1e image is first segmented
`usi11g the fractal dimension and tl1en tl1e resultant unif7orn1 segn1ents can be efficiently coded using
`the properties o·f the hu1nan visual system. Another fr,1ctal image coding sche111e is based on fractal
`geornetry, which is used to measure tl1e length of a curve wilh a yardstick (Walach, 1989). The
`details of these codi11g methods will be discussed i11 Sect.ion 9.3.
`The basic id·ea of ·1n0del-based cod.ing is to reconstruct an image \.Vith· a set o·f model paran1eters.
`The model parameters are then encoded and transmitted lo the decoder. At the deeoder tl1e decoded
`
`18.5
`
`IPR2021-00827
`Unified EX1008 Page 211
`
`

`

`186
`
`Image and Video Compr ession for Multimedia Engineering
`
`Training·Set of
`Images
`
`Input
`Image
`
`Vector
`Formation
`
`Training S·et
`Generation
`
`Codebook
`Generation
`
`Codebook
`
`l11dex of
`Codew ord
`
`Vector
`Formation
`
`Quantizer
`
`FIGURE 9.1 Principle of image vector quantization. Th e dashed lines corre pond to tr aining set generalion,
`codebook generation, and transmission (if it is necessary).
`
`model parameters are used to reconstruct the image vvith the san1e rnodel used at the encoder.
`Therefore, the key techniques in the n1odel-based coding are in1age modeling, image analysis, and
`image synthesis.
`
`9.2 VECTOR QUANTIZATION
`
`9.2.1
`
`BASIC PRINCIPLE OF VECTOR QUANTIZATION
`
`An N-Jevel vector quantizer, Q, is mapping from a K-dimensional vector set { V}, into a finite
`codebook, \¥ = { lV 1, w2, ••• , l-vN}:
`
`Q: V ~ W
`
`(9 .1)
`
`In other words., it assigns an input vector, v, to a representative vector (codeword), l-V from a
`eodebook, W. The ve.ctor quantizer, Q, is completely described by the codebook, W = { l-V1, ~v2, ·· . ,
`}>VJV}, together with the disjoint partition, R = {r1, ,· 2, •. • , ,·N}, where
`
`•
`
`r; = { v: Q(v) = l>V; }
`
`(9.2)
`
`and lV and v are k-dimensional vectors. The partition should identically minimize the quantization
`error (Gersho, 1982). A block diagram of the various steps involved in i·mage vector quantization
`is de,picted in Figure 9. I.
`The nrst step in image vector q.uantization is the image f onnation. The image data are first
`partitioneo into a set of vectors. A large number of vectors from various images are then used to
`fo,rm a training set. The training set i~ used to generate a codebook, no11i1ally using an iterative
`clustering algorithm. The quantization or coding step involves searching eacl1 input vector for tile
`closest codeword in the code,book. Then the corresponding index of the selected codeword is coded
`and transmitted to the decoder. At the d.ecoder, the index is decoded and converted to the corre(cid:173)
`sponding vector with the same codeooo.k as at the encoder by look-up table. Thus, the design
`decisions in implementing image vector quantization include ( 1) vector for111ation; (2) training set
`generation; (3) eodebook generation; and (4) quantization.
`
`9.2.1.1 Vector Formation
`
`The first s,tep of ve.etar quantization is ·vector formation; that is, the decomposition of th·e im.ages
`into a set of vectors. Many different decompositions ba~e been proposed; exam,p1es include the
`
`IPR2021-00827
`Unified EX1008 Page 212
`
`

`

`Nonstandard Image Cod ing
`
`187
`
`intensity values of a spatially contiguous block of pi.xels (Gersho and Ramaniuthi, 1982; Baker
`and Gray, 1983); tl1ese same intensity v~1]ues, but now normalized by tl1e mean and variance of the
`block (Murakami et al., l 982); the transforn1ed coefficients of the block pixels (Li and Zhang,
`1995); and the adaptive linear f)redictive coding coefficients for a block of pixels (Sun, 1984).
`Basically, the ,1pproacl1es of vector forn1ation can be classified into two categories: direct spatial
`or temporal, and feature extractior1. Direct spatial or temporal is a simple &pproach to for111ing
`,,ectors from the intensity values of a spatial or temporal contiguous block of pixels in an image
`or an image equence. A nur11be1· of ir11age vector quantizaton schemes have been investigated with
`this method. Tl1e other mett1od is feature extraction. An image feature is a distinguishing primitive
`cl1aracteristic. S0n1e features are n,1tural in tl1e sense that they are defined by the visual appearance
`of an image , while t'he other so-called artificial features result from specific manipulations or
`measure n1er1ts of in1c1ges or image . equences. In vector formation, it is well known that the image
`data in a spat ial domain car, be converted lo a different domain so that subsequent quantization
`and joint entropy encod ing can be more efficient. For this purpose, son1e features of image data,
`such as transformed coefficients and block n1eans can be extracted and vector quantized. The
`practical significa11ce of feature extraction is that it ·can result in tl1e reduct·ion of vector size,
`consequently reducing the complexity of coding procedure.
`
`9.2.1.2
`
`Training Set Generation
`
`An optin1al vector quantizer should ideally 1natch the statistics of tl1e input vector source. Ho\vever,
`if the statistics of an input vector source are unknovvn, a training set representative of the expected
`input vector source can be used to design the vector quantizer. If the expected vector source has a
`large variance, ther1 a large trair1ing set is needed. To alleviate the implen1entation complexity
`caused by a large training set t.he input vector so.urce can be divided into .subsets. For example, in
`(Gers ho, 1982) the single input source is d.ivided into ''edge'' and ''shade'' vectors, (ind tl1e11 the
`sepa rate trainir1g sets are used to generate tl1e separate codebooks. Tl1ose separate codebooks are
`then concatenated into a fir1al codebook. In otl1er n1etl1ods, small local input sources corresponding
`to portions of the ir11age are used as the traini11g sets, tl1us the codebook can better n1alch the local
`statistics. However, the code book needs to be updated to track the changes in local statistics of the
`input sources. This 1nay increase the cor11plexity and reduce the codi11g efficiency. Practically, in
`most codjng sys tems a set of typical images is selected as the training set and used to generate the
`codebook. The coding per·formance can then be ir1sured for the images with the training set, or for
`those not in the training se l but witl1 statistics similar Lo those in the training set.
`
`9.2.1.3 Codebook Generation
`
`The key step in cor1ventional in1age vector quantization is the developn1ent of a good codeboo k.
`The optimal codebook, using the n1ean squared error (MSE) criterion, must satisfy two necessary
`conditions (Gersl10, J 9·82). First, the ir1put vector source is partitioned into a predecid·ed nun1ber
`of region s with tl1e 1ninimum dista11ce rule. The nun1ber of regions is decided by the requirement
`of the bit rate, or compression ratio and coding perfor·mance. Second, the codeword or the repre(cid:173)
`sentative vector of this region is tl1e mean value, or the statistical center, of the vectors \Vitl1in the
`region. Under the~e two cor1ditions, a generalized Lloyd clustering algorithm prop.osed by Linde.
`B·uzo, and Gray ( 1980)
`tl1e so-called LBG algorithm
`has been extensively used to generate
`the codebook. The clustering algorithn1 is an iterative process, minirnizing a performance inde-x
`calculated fro,n the distances between the sample vectors and their cluster centers. Tt1e LBG
`clustering algoritl1m can only ge11erate a co:debook w.ith a local optin1um, wh.ioh depends on tl1e
`initial cluster seeds . Two basic procedures have been used to obtain the initial codeboo k or cluster
`seeds. In the first approacl,, t11e starting point in,1olves" finding a sn1all codebook \Vith only two
`code,vords, and then recursively splitting the codeboo·k until tl1e required nurnbe-r of codewords is
`
`IPR2021-00827
`Unified EX1008 Page 213
`
`

`

`188
`
`Image and Video Compression for Multimedia Engineering
`
`obtained. This approach is referred to as binary splitting. The seco 11d procedure starts \vith initial
`seeds for the required number of codewords, these seeds being generated by preprocessi ng the
`training sets. To address the problem of a local optimum, Equitz ( 1989) propo sed a new clustering
`algorithm, the pairwise nearest neighbor (PNN) algorithm . The PNN algori thm begins \vith a
`separate cluster for each vector in tl1e training set and n1erges togetl1er l wo clusters at a tirne until
`the desired codebook size is obtained. At the begi11ning of tl1e clustering process, eac l1 cluster
`contains only one vector. In the following process the two closest vector s in the training set are
`merged to their statistical mean value, in such a way th.e error incurred by replaci .ng tl1ese two
`vectors \vith a single codeword is minimized . The PNN algorithm significan tly reduces computa(cid:173)
`tional complexity without sacrificing performance. This algorjthm can also be used as ,in initial
`codebook generato .r for tl1e LBG algorithm.
`
`9.2.1.4 Quantizati .on.
`
`Quantization in the context of a vector quantization involves selecting a code\vord in the codebook
`for each input vector. The optin1al quanti·zation, in turn, in1plies tl1at for each i11put \1ector, i,, tl1e
`closest codeword, iv;, is found as sho\vn in Figure 9.2. The measuren1ent criterion co uld be mean
`squared error , absolute error, or other distortion 1neasures.
`A full-se ·arch quantization is an exhaustive search pro·ces.s over the en lire codebook for finding
`the closest codeword, as sho\vn in Figure 9.3(a). It is optin1al for the given codeboo k, but fhe
`co·mputation is more e.xpen,sive. An alternative approach is a tree-sea rct, qua11tization, wl1ere the
`searc .h is carried out based on a hierarchical partition . A bi.nary tree earcl1 is show n in Figure 9 .3(b ).
`A tree search is much faster than a full search , but it is clear that the tree sea rch. is suboptimal for
`the given cod'ebook an.d require s m.ore memory for the codebook.
`
`Codebook
`
`Input vector
`.
`V
`
`Index k
`
`Quantiution
`
`FIGURE 9 .. 2 Principle of vector quantization.
`
`(a)
`
`(b.)
`
`FIGURE 9.3
`
`(a~ Full search quantization; (b) binary 1ree search quantization.
`
`IPR2021-00827
`Unified EX1008 Page 214
`
`

`

`Nonstandard Im-age Coding
`
`189
`
`9.2.2
`
`SEVERAL
`
`IMAGE CODING SCHEMES WITH VECTOR QUANTIZATION
`
`In this section, we arc gojng to preser1t several image coding schernes usjng vector quantization
`\vhich include res idual vector quantization, classified vector quantization, transfonn domain vector
`quantization, predictive vector quan,tization, and block truncation coding (BTC) which can be seen
`as ,1 binary vector quantiz atio11.
`
`9.2.2.1
`
`Residual VQ
`
`In L~1e conventional in1age vector quar1tization, the vectors are fom1ed by spatially partitioning the
`image data into blocks of 8 x 8 or 4 x 4 pix~ls. In the original spatial domain the statistics of
`vectors n1ay be ,videly spread in lhe n1ultidimensional vector space. This causes difficulty in
`generating the codeboo k witl1 a finite size and limits the coding perfor r11ance. Residual VQ is
`proposed to alleviate this problem. In resi,dual VQ, the mean O'f tl1e block is extracted and coded
`separately. The vectors are forn1ed by subtracting the block mean from the original pixel values.
`This scheme can be f urlher n1odified by cor1sidering tl1e variance of tl1e blocks. The original blocks
`are converted to the vector5 with zero mean ar1d unit standard deviation with the following con(cid:173)
`version fon11ula (ML1raka111i et al., 1982):
`
`!· -I
`
`111. = _!_ ~ S
`I K ~ J
`i=O
`
`(9.3)
`
`(9 .4)
`
`(9.5)
`
`where I'll; is the mean value of ith block, a,. is lt1e ,,ariance of ith block, si is the pixel value of pixel
`j U = 0, .. . , K-1) in the ith block, K is the total nun1ber of pixels in the block, and J.J is tl1e norn1alized
`value of pixel j. The new vector X; is now f orn1ed by xi U = 0, I, ... , k-1 ):
`
`(9.6)
`
`With the above norn1alization the probabilily function P(X) of input vector X is approximately
`sin1ilar for image data from different scenes. Therefore, it is easy to generate a codebook for the
`new vector set. The problem witl1 this method is tl1at the n1ean and variance values of blocks have
`to be coded separately. This increases the overhead and lin1its tl1e coding efficiency. Several methods
`have been proposed to improve tl1e coding efficiency. One of tl1ese methods is to use predictive
`co·ding to code the block n1ean values. T,l1e mean value of the current bloc.k can be predicted by
`one of the previously coded neighbors. In such a ,vay, tl1e coding_ efficien.cy increases as the use
`of i nterblock correlation.
`
`9.2. ,2.2 Classified VQ
`
`In image vector quantization, the codebook is usually generated using trainir1g set under constraint
`of minimtz-ing the mean squared error. Tl1is in1plies tl1at the code\vord is the statistical mean of the
`
`IPR2021-00827
`Unified EX1008 Page 215
`
`

`

`•
`
`190
`
`lrnage and Video Compres sior, fo r Mult imed ia Engineering
`
`region. During quantization, each input vector is replaced by its closes t codeword. Tl1erefore, tl1e
`coded images usually suf'fer from edge distortion at very low b·it rates, si11ce edges are sn1oothed
`by the operation of averaging W·itl1 the s111all-sized codebook. To overcon1e this problem , \ve can
`classify t11e training vector set into edge vectors and shade \1ectors (Gersl10, 1982). Two separate
`codebooks can tl1en be ge11erated \vitl1 tt1e two types of training sets. Eacl1 i 11pu L vector can be
`coded by the appropriate codeword in tl1e codebook. However, tl1e edge vectors can be further
`classified into n1any types according to their location and a,1gul ar orientation. The classified VQ
`can be extended into a system wl1icl1 conla·ins n1a11y sub-codebooks , each repre enting a t)1pe of
`edge. However, tl1is would increase the con1plexity of tl1e systern and would be l1nrd to implement
`in prac.tical applications.
`
`9.2.2.3 Transform Domain VQ
`Vecto·r quantization can be perf onn ed in tl1e transf orrn dorn,1in. A spalial block or 4. x 4 or 8 x 8
`pixels is first transfom1ed to the 4 x 4 or 8 x 8 tra11sfor111ed coefficients. Tl1ere are seve ral ways to
`fom1 vectors witl1 transfor111ed. coefficients. 111 the first 1netl1od, a nun1ber of !1igJ1-orde.r coe fficients
`can be discarded since most of tl1e energy is usually conlained in Lhe lo\v-order coe fficients for
`most blocks. This reduces the VQ computatio11al co111plex i ty at the expe11 e o f c.1 sn1al l increase in
`distortion . However , for some acti\1e blocks, th·e edge inforn1atio11 is contained in tl1e high frequen(cid:173)
`cies, or high-order coefficients. Serious subjective distortion wi 11 be caused by d isct1rd i ng l1igh
`frequencies. In the second method, the transfom1ed coefficie11ts ~ire divided into several bands and
`each band is used to f or1n its corresponding vector set. This method is eq u i \ralen t to the classified
`VQ in spatial domain. An adaptive schen1e is tl1er1 developed by usir1g two kjnd s of vector fo11nation
`methods. The first metl1od is used for the b]ocks conlaining the mode rate i11tensi ty variation and
`the second n1ethod is used for the blocks \Vith higl1 spatial activities. However, the complexity
`increases as .more codebooks are needed in this kind of adaptive coding system.
`
`9.2.2.4 Predictive VQ
`
`The vectors are usually formed by the spatially consecutive blocks . Tl1e consec utive vectors are
`then highly statistically dependent. Therefore, better coding performance can be achieved if the
`correlation between vectors is exploited. Several predi.otive VQ scl1e1nes have bee n propo sed to
`address this problem. One 'kind of predictive VQ is finite state VQ (Foster et al., 1985) . The fi nite(cid:173)
`state VQ is similar to a trellis cod·er. In the finite state VQ, tl1e codebook co11sists of a set of sub(cid:173)
`codebooks. A state variable is then used to specify which sub-codebook should be selected for
`coding the input vector. The infor1nation ·about the state variable must be inferred fron1 the received
`sequence of state symbols and initial state such as in a trellis. coder. Theref ore, no side informa tion
`or no o·verhead need be transmitted to the decoder. The new encoder state is a function of the
`previous encoder state an.d the selectep sub-codebook. This pem1its the decoder to track tl1e encoder
`state if t,he initial con9itiqn is known. The finite-state VQ needs additional memory to store tl1e
`previo .us state, but it takes advantage of correlation between su.ccessive input vectors by choosing
`the appropriate codebook for the given past history. It should be noted that the mini1num distortion
`selection rule of conventional VQ is not neces.sary optimum for finiLe-state VQ for a giv.en decoder
`since a low-distortion codeword may lead to a bad state a.nd hence to poor long-term behavior.
`Th·erefore, the key design issue of finite-state VQ is to find a good next-state t·u11ction.
`Another predictive VQ was proposed by Hang and Woods (1985). In this system, tl1e input
`vector is formed in such a way that tl1e curre.nt pixel i~ as the first elem~nt of the vector a11d the
`.
`previous inputs as tlie rem·aining elements in tl1e vector. The sy~tem is like a mapping or a recursive
`filter which is used to p.redict the next pixel. The 1napping is implemented by a vect0r quantizer
`lo0k-~p table and pr<>vides the preclictive errors.,.
`
`.
`
`IPR2021-00827
`Unified EX1008 Page 216
`
`

`

`Nonstandarcl lrn age Cocf i 11g
`
`9.2.2.5 Block Truncation Coding
`
`191
`
`In tl1e block truncati on code (BTC) (Delp and Mitcl1ell, 1979), an image js first divided into 4 x 4
`blocks. Eacl1 block is ll1en coded i11dividt1ally. The pixels in e.ach block are first converted into two(cid:173)
`level signals by using the first two 111or11ents of the block:
`
`rz = 111 + a
`
`b = 11i- a
`
`q
`N-q
`
`N-l
`
`CJ
`
`(9.7)
`
`\Vhere ni is the rnea11 value or tl1e bloc.k cr is Lh.e standard deviation of the block, N is the number
`of total pixels in tl1e block, and q is the nur11ber of pixels which are greater ir1 value thar1 ,n.
`Tl1erefore, eac l1 block can be described by tl1e values of block n1ean, varia11ce, and a binary-bit
`plane whict1 indicates wl1etl1er the pixels have values above or below the block n1ean. Tl1e binary(cid:173)
`bit pla11e ca11 be see 11 as a binary vector quar1tizer. lf tt1e n1ean and variance of tl1e block are
`quantized to 8. bits, tl1cn 2 bits per pixel is ncl1ieved for blocks of 4 x 4 pixels. Tl1e convenliona l
`BTC sche111e can be 111odified to increa e the coding efficiency. For example, the block mean can
`be cocJed by a DPCM code r wl1ich exploits tl1e interblock correlation. Tl1e bit plane can be code·d
`\Vith an entropy coder 011 Lhe pattern · (Udpikar and Raina, 1987).
`
`9.2.3
`
`LATIICE VQ FOR IMAGE CODING
`
`In cOn\1entional image vector quantization schemes, tl1ere are several issues, 'vvhi·ch cause s_ome
`difficulties for tl1e practica 'I UJ)plication of i111age vector quantization. The first problern is l.he
`limitati on of vector dirr1ension. Ir l1as been indicated that tl1e coding perfor111ance of vector quan(cid:173)
`Lization increases as tl1e vector din1cnsion while tl1e coding complexity expone11tially increases at
`the san1e ti111e as tl1e increasing vector dimensior1. Therefore, in practice only a srna ll ve.ctor
`dimen sion is possible under tl1e con1plex,ity cor1strai11t. Ar1otl1er important issue ir1 VQ is the need
`for a codebook. Mu ch research effort has gone into findi11g 110w to ge11erate a codeboo k. Ho\vever,
`in practical appljcat ions there is a,1otl1er problem 0f 110\v to scale the ·codebook for vt1rious rate(cid:173)
`distortion requiren1ents. Tl1e codebook ger1erated by LBG-like algorithms witl1 a training set is
`usualJy on ly suitable for a specified bit rate arid does 11ot l1ave tl1e fle~ibility of codebook scalabil.ity.
`For examp le, a codebook ger1erated for an image \-Vitl1 sn1all resolution may not be suitable for
`in1ages witl1 high reso lution. E\,en for tl1e same spatial resolutio11, different bit rates \vould require
`different codebooks. Additior1ally, the VQ needs a table to specify tl1e codebook and, oo.11sequeritly,
`tl1e con1plexity of sloring and searct1ing is too l1igl1 to have a very large table. This furtl1er lin1its
`the coding perfonn ance of image VQ.
`These problems become rnajor obstacles for i1nplen1enting in1age VQ. Rece11tly, an algoritl1n1
`of lattice VQ has been proposed to address tl1ese problen1s (Li et al., 1997) .. Lattice VQ does not
`have the above problem s. Tl1e codebook for lattice VQ is sin1ply a collection of la.ttic.e points
`uniforn1ly distributed over the vector space. Scalability can be acl1ieved by scaling the cell size
`associated with every lattice point ju st like i11 tl1e scalar quantizer by scali11g the quantizatjon step.
`The basic concept of tl1e lattice can be found in (Con\\ray and Slone, 199 l ). A typical lattice VQ
`scheme is ·sf1own in Figure 9.4. There are l\VO steps i11\10J,,ed ir1 tl1e image lattice VQ. The first step
`is to find tl1e closest lattice point for tl1e i11put .vector. Tl1e second step is to label the lattice point,
`i.e., mapping a lattice point to an index. Since lattice VQ does need a codebook, the index assignment
`is based 011 a lattice labeling algo.ritl1m instead of a look-up table such as in conventional VQ.
`Therefore, the key issue of lattice VQ is to develop an efficient lattice-labeling algorithn1. Witl1 this
`
`IPR2021-00827
`Unified EX1008 Page 217
`
`

`

`192
`
`Image and Video Compression for Mu,ltimedia Engineering
`
`Latµcc VQ Encoding
`
`Input
`
`Vector ·•
`
`Find a closest
`Codeword C;
`
`-
`
`Extract index
`•
`I
`(Lattice Labeling)
`
`I
`I
`
`I
`
`Index i
`
`Cbaaoel
`
`Outp ut
`
`tor
`Vee
`
`Lattice V Q dec.oding
`
`Map back to
`C·
`I,
`(Lattice d~labelin~)
`
`4
`
`Index i
`
`I
`
`I
`I
`
`FIGURE 9.4 Block diagrain of lattice VQ.
`
`y
`
`•
`•
`
`•
`•
`
`X
`
`FIGURE 9.5 Labeling a two-dimen sional lattice.
`
`~gorithm the closest lattice point and its correspo.nding index within a finite boundary can be
`obtained by a calculation at the encoder for each input vector.
`At the decoder, 'the index is converted to the lattice point by the same labeling algorithm. The
`vector is then reconstructed with the lattice point. The efficiency o·f a labeling algorithm for lattice
`VQ is measured by how many bits are needed to represent the indices of the lattice points \Vithin
`a finite boundary. We use a two-dimensional lattice to e·xplain the lattice labeling efficiency. A two(cid:173)
`dimensional lattice is shown in Figure 9.5.
`In f'igor.e 9.5, th.ere are seven lattice points. One method used to· label these seven 2-D· lattice
`p.oints is to use their coordinates (x,y) to label each point. If we label x and y separately, we need
`two bits to label three values .of x and three bits to labe] a possible five v.a]ues of y, and need a tQtal
`of five bits. It is clear that three bits are sufficient to label sev·en lattice points. Therefore, different
`labelin.g algerithms may have different labeling efficiency. Several algorithms bav.e been developed
`for multidimensional lattice labeling. In (C.onway, 1983 ), the labeling method assigns an index to
`every lattice point within a Voronoi boundary whe.re the shape of the boundary is the same as the
`shape of Voronoi ceJls. Apparently, for different dimension, th.e bo·un.daries have different shapes.
`In the algorithm proposed in (Laroia, 1993), the same method is used to assign an index to each
`lattice point. Since the boµndaries are defined by the labeling algorithm, this algorithm might not
`aehieMe a 100% labeling eftic,iency for a prespeeified boundary such as a pyramid boundary. _The
`algorithm propo§ed by .Fisclier (1986) can assign an inde~ to every lattice point within a prespecifie.?
`Ryramid bounaary and acliiev,es a 100% labeling efficiency, but this algorithm can, only b.e used
`.for the; zn lanice. ln ,a rec.ently proposed algerithm (Wang et al., 1998), the techn.ical breakthrough
`was o.btained. In thi.s algorithm a labeling m~thod was. developed for Construction-A. and
`aonstroetio:n-B lattiees ~Conw,ay, 198'3), whicnis very useful for VQ with proper vector aimens1o~s,
`such as li, and achieves 100% effiejtncy,. Addi'tioha,lly, these algorithms are used for labeling lattice
`
`IPR2021-00827
`Unified EX1008 Page 218
`
`

`

`Nonstandard Image Coding
`
`193
`
`points with 16 d.in1e11~ions and pro~ide minimum distortion. These algorithms were developed
`based on the relat1onsl11p between lattices and linear block codes. Construction-A and Construction(cid:173)
`B are the two simplest ways to construct a lattice from a binary linear block code C = (n, k, d),
`where n, k, and d are the lengLl1, the dimension, and the minimu,m distance of the code, respectively.
`A Construction-A lattice is defined as:
`
`A = C+2zn
`
`//
`
`(9 .8)
`
`~vhere zn i s tl1e ti-dimensional cubic lattice and C is a binary linear block code. There are two ste·ps
`1nvolved for labeling a Construction-A lattice. Tl1e first is to order the lattice points according to
`tl1e binary linear block code C, and then to order lhe lattice points associated with a particular
`nonzero binary codewo.rd. For the lattice points ass.ociated with a nonzero binary code\vord, two
`sub-lattices are considered separately. One sub-lattice consists of a.II the dimensions that have a
`''O'' component in tl1e binary codeword and the other consists of all the dimensions that have a ''1 ''
`con1ponent in the binary codeword. The first sub-lattice is considered as a 2Z lattice. while tl1e
`second is considered as a translated 2Z lattice. Therefore, tl1e labeling problem is reduced to labeling
`the Z lattice at the final stage.
`A ConstrL1ction-B lattice is defir1ed as:
`
`where D,, is an ,z-dirnensional Construction-A lattice with tl1e definition as:
`
`A =C+2D
`
`ii
`
`II
`
`= (11,1z -1 , 2) + 2zn
`
`D
`
`11
`
`(9.9)
`
`(9.10)
`
`and C is a bi11ary doubly eve.n ti near block code. When ,i is equal to 16, tl1e binary even linear
`block code. associated with A16 is C = ( 16, 5, 8). The method for labeling a Construction-B lattice
`is sin1ilar to the method for labeling a Construction-A lattice \Vith two minor dift'erences. The first
`difference is that for any vector )t = c + 2x, .,t E Z 0
`, if) ' is a Construction-A lattice point; and x E
`D,,, if )' is a Construction -B lattice point. Tl1e second difference is that C is a binary dou.bly even
`linear block code for Construction-B lattices while it is not necessarily doubly even t·or Construc(cid:173)
`tion-A lattices. In tl1e implement ation of these lattice poir1t labeling algorithn1s, the encoding· and
`decoding functions for lattice VQ l1ave been developed in (Li et al., 1997). For a given input vector,
`an index repre senting the closest lattice point will be found by the e11coding function, and for an
`input index the reconstru cted vector will be generated by the decoding .function. In summary, the
`idea of lattice VQ for i111age coding is an important achi·evement i.n eli·n1inating the need for a
`codebook for image VQ. The development of efficient algorithms for lattice point labeling makes
`lattice VQ feasible t'or i.mage coding.
`
`9.3 FRACTAL IMAG 'E CODING
`
`9.3.1 MATHE.MATICAL FOUNDATION
`
`•
`
`A fractal is a geometric fonn whose irregular details can be represented by some objects with
`dJfferent scale and angle, whicl1 can be described by a set of transfor1nations such as affine
`transformations. Additi_onally, the objects used. to represent the image's · irregular details l1av.e son1e
`form of self-similarity and these objects can be us·ed to represent an image in a sin1ple recursive
`way. An exainple of fractals is the Von Koch curve as shown in Figure 9.6. The fractals can be
`us~d to gen~rate ar1 image. The fractal in1age codi11g that is based on iterated fu11ction systems
`
`IPR2021-00827
`Unified EX1008 Page 219
`
`

`

`194
`
`Image and Video Cornpr ession for Multirnedia Engineering
`
`Eo
`
`•
`
`•
`
`FIGURE 9.6 Construction of the Yon Koch curve.
`
`(IFS) is tl1e inverse process of image generation \virh fractals. Tl1erefore, tl1e key techn ology of
`fractal image coding is the generation of fractals with an IFS.
`To explain IFS, \Ve start fron1 the contractive affine transfom1ation. A Lwo-din1ensional affine
`transf onnation. A is defin·ed as follows:
`
`•
`
`A
`
`--
`
`X
`
`) '
`
`a
`
`b
`
`,t
`
`+
`
`e
`f
`
`(9 .1 I )
`
`This is a transfom1a.tion which con.sists of a linear transformation followed by a shift or translation,
`and maps points in the Euclidean plane into ·ne\v points in the another Euclidean plane . We define
`that a transformation is contractive if the distance between two points P1 and P2 in the new plane
`is smaller than their distance in the original plane1 i.e.,
`
`(9.12)
`
`where s is a constant and O < s < 1. The contractive transformations have the property ·that when
`tl1e contractive transfo1111ations are repeatedly applied to the points in a plane, these points \viii
`converge to a fi:>eed point. A11 iterated functioti systenz (IFS) is clefi,zed as a collectio11 of corzt,·active
`affine transfon11atia11s. A wel'l-know.n example of IFS contains four t·ollowing transformations:
`
`X
`
`--
`
`a
`
`C
`
`b _.t
`d
`
`) I
`
`+
`
`e
`
`f
`
`i=l,2,3 , 4.
`
`(9.13)
`
`.
`
`This is the IFS of a fer:n leaf, whose parameters -are shown in Table 9 .