United States Patent [19]
`Jacobs et al.
`
`US005862262A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,862,262
`Jan. 19, 1999
`
`-
`
`-
`
`- -
`
`- -
`
`-
`
`-
`
`ABSTRACT
`[57]
`A method of encoding a digital image using adaptive par
`titioning in an iterated transformation image compression
`system is provided. A set of ranges R is initialized to include
`at least two uncovered ranges. A set of domains D is
`initialized to include only one member which is the entire
`image area.
`For each uncovered range in the set R: A transformation is
`generated for each ... in the set of domains. Each
`domain is transformed into corresponding transformed
`images to map onto each uncovered range in the set R. Each
`domain’s transformation is optimized and is indicative of a
`domain’s corresponding optimized transformation image for
`[21] Appl. No.: 859,782
`an associated uncovered range. Each optimized transforma
`[22] Filed:
`Mar. 30, 1992
`tion image is compared with the associated uncovered range
`
`[51] Int. Cl." … G06K 9/36 to provide error data as a function of the difference ther
`[52] U.S. Cl. ........................... 382/249; 348/397; 348/438
`ebetween. The associated uncovered range is redefined as a
`[58] Field of Search ........................ 382/56, 14; 358/426,
`covered range when the error data for the associated uncov
`358/430, 433, 133, 135, 136
`ered range is within predefined limits. The covered range is
`then added to the set of domains D. The associated uncov
`References Cited
`ered range is partitioned into a plurality of non-overlapping
`image areas. Partitioning is based upon the features of the
`image bounded by the associated uncovered range and takes
`place when the error data for the associated uncovered range
`exceeds the predefined limits. Each of the non-overlapping
`image areas is added to the set R of uncovered ranges and
`the associated uncovered range is added to the set of
`domains D.
`
`[54] METHOD OF ENCODING A DIGITAL
`IN AN ITERATED TRANSFORMATION
`SYSTEM
`
`IMAGE USING ADAPTIVE PARTITIONING
`
`[75] Inventors: Everett W. Jacobs; Roger D. Boss,
`both of San Diego; Yuval Fisher, La
`Jolla, all of Calif.
`e
`e
`-
`[73] Assignee: The United States of America as
`represented by the Secretary of the
`Navy, Washington, D.C.
`
`[56]
`
`U.S. PATENT DOCUMENTS
`4,365,273 12/1982 Yamada et al. ........................... 382/56
`4,409,623 10/1983 Kobayashi et al.
`... 358/433
`4,831,659
`5/1989 Miyaoka et al. .......................... 382/56
`4,941,193 7/1990 Barnsley et al. .
`5,065,447 11/1991 Barnsley et al. .......................... 382/56
`OTHER PUBLICATIONS
`Jacquin, “Fractal Image Coding Based on a Theory of
`Iterated Contractive Image Transforms” Oct. 1990 pp.
`227—239.
`Wu et al., “Image Coding by Adaptive Tree—Structured
`Segmentation” 1991 pp. 73–82 DCC '91.
`Primary Examiner—Leo Boudreau
`Assistant Examiner—Chris Kelley
`Attorney, Agent, or Firm—Harvey Fendelman; Michael A.
`Kagan; Peter A. Lipovsky
`
`The steps of generating, transforming, optimizing, compar
`ing, redefining, partitioning and adding are repeated to select
`a set of covered ranges, domains and corresponding opti
`mized transformations. The set of covered ranges form a
`non-overlapping tiling of the image and some iterate of the
`set of selected transformations is contractive. Information
`that identifies the set of covered ranges, domains and cor
`responding optimized transformations is stored compactly in
`an addressable memory.
`9 Claims, 3 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`PARTITIDN
`Rt INTD
`n PIECES
`
`ADD NEW RANGES
`TD LIST []F RI's
`
`trox * (nox *n
`
`
`
`371 ->
`
`PRUCESS TH
`CALCljLATE
`ERRER §
`
`FDR D,
`[IFTIMIZE
`Wu J AND
`TRANSFIRM
`
`
`
`Google Inc.
`GOOG 1036
`IPR2016-00212
`
`0001
`
`

`
`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 1 of 3
`
`5,862,262
`
`
`OOI ----
`_^
`
`| |
`
`€0?20]?OI| + – – – – –
`
`
`
`F--- – — — — — — — — — — —–
`
`
`
`CIEZI LIÐICI
`
`350kWWI
`
`
`
`
`
`0002
`
`

`
`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 2 of 3
`
`5,862,262
`
`D1
`
`R2
`
`12
`
`2T
`
`14 .
`2
`FIG. 30.
`
`D2
`D3
`
`R3
`FIG. 3b
`
`R4 R5
`
`... iii. I
`Z_ Am
`
`FIG. 3C
`
`De? R.
`FIG. 3d
`
`| || ||
`| | |
`Am "ºam
`2
`
`
`
`R12 | ||
`£32.
`Z.
`* 13
`FIG. 39
`
`0003
`
`

`
`U.S. Patent
`
`Jan. 19, 1999
`
`Sheet 3 of 3
`
`5,862,262
`
`T18IV-le-HOOV,
`
`NDI LI LèJºd
`
`EICH U DINI ??!
`SEO
`
`0004
`
`

`
`5,862,262
`
`1
`METHOD OF ENCODING A DIGITAL
`IMAGE USING ADAPTIVE PARTITIONING
`IN AN ITERATED TRANSFORMATION
`SYSTEM
`
`2
`transformation must be optimized in terms of position, size
`and intensity. If the transformation cannot be optimized
`within the specified error bound for a given set of ranges and
`domains, predefined subdivisions of the ranges are selected.
`The search for an optimized transformation then continues
`using these subdivisions. One method of predefining the
`subdivisions is known as quad-tree partitioning which
`divides a square sized range in a fixed way. Essentially, the
`range is subdivided into four equally sized squares without
`considering any of the image’s features.
`Thus, the need exists for a method of adaptively parti
`tioning the image in an iterated transformation system based
`upon the features of the image. Accordingly, it is an object
`of the present invention to provide a method of encoding a
`digital image in an iterated transformation system by using
`adaptive partitioning in determining suitable ranges and
`domains to encode the image. Another object of the present
`invention is to provide a method of encoding a digital image
`in an iterated transformation system that adjusts to the
`features of the image during its partitioning process.
`SUMMARY OF THE INVENTION
`In accordance with the present invention, a method of
`encoding a digital image using adaptive partitioning in an
`iterated transformation image compression system is pro
`vided. The digital image is represented by an array of pixels
`defining an entire image area. Each pixel is defined by a
`three-dimensional vector identifying the position of the pixel
`in the array and an intensity level of the pixel. A set of ranges
`R is initialized to include at least two uncovered ranges.
`Each uncovered range is a section of the entire image area
`such that the union of the uncovered ranges tile the entire
`image. A set of domains D is initialized to include only one
`member which is the entire image area. For each uncovered
`range in the set R, a transformation is generated for each
`domain in the set of domains. The transformation comprises
`a 3×3 matrix identifying positional scaling coefficients and
`an intensity scaling coefficient, and a 3×1 vector identifying
`positional offset coefficients and an intensity offset coeffi
`cient. Each domain is transformed into corresponding trans
`formed images scaled in size and intensity, based upon each
`domain’s transformation, to map onto each uncovered range
`in the set R. For each uncovered range in the set R, each
`domain’s transformation is optimized in terms of the inten
`sity scaling and offset coefficients. An optimized transfor
`mation is indicative of a domain’s corresponding optimized
`transformation image for an associated uncovered range. For
`each uncovered range in the set R, each optimized transfor
`mation image is compared with the associated uncovered
`range to provide error data as a function of the difference
`therebetween. For each uncovered range in the set R, the
`associated uncovered range is redefined as a covered range
`when the error data for the associated uncovered range is
`within predefined limits. The covered range is then added to
`the set of domains D. For each uncovered range in the set R,
`the associated uncovered range is partitioned into a plurality
`of non-overlapping image areas. Partitioning is based upon
`the features of the image bounded by the associated uncov
`ered range and takes place when the error data for the
`associated uncovered range exceeds the predefined limits.
`For each uncovered range in the set R, each of the non
`overlapping image areas is added to the set R of uncovered
`ranges. The associated uncovered range is added to the set
`of domains D. The steps of generating, transforming,
`optimizing, comparing, redefining, partitioning and adding
`are repeated to select a set of covered ranges, domains and
`corresponding optimized transformations. The set of cov
`
`10
`
`15
`
`40
`
`STATEMENT OF GOVERNMENT INTEREST
`The invention described herein may be manufactured and
`used by or for the Government of the United States for
`governmental purposes without the payment of any royalties
`thereon or therefor.
`This patent application is copending with our related
`patent application entitled “Method of Encoding a Digital
`Image Using Iterated Image Transformations to Form an
`Eventually Contractive Map” filed on the same date as
`subject patent application.
`FIELD OF THE INVENTION
`The present invention relates to the field of digital image
`compression, and more particularly to a method of encoding
`a digital image using adaptive partitioning in an iterated
`transformation system.
`BACKGROUND OF THE INVENTION
`Advances in computer hardware and software technology
`have brought about increasing uses of digital imagery.
`However, the amount of memory necessary to store a large
`number of high resolution digital images is significant.
`Furthermore, the time and bandwidth necessary to transmit
`the images is unacceptable for many applications.
`Accordingly, there has been considerable interest in the field
`of digital image compression.
`The basic elements of a digital image compression system
`are shown schematically in FIG. 1, and are referenced by
`those elements contained within dotted line box 100. A
`35
`digitized image is processed by an encoder 101 to reduce the
`amount of information required to reproduce the image. This
`information is then typically stored as compressed data in a
`memory 102. When the image is to be reconstructed, the
`information stored in memory 102 is passed through a
`decoder 103.
`The goal of a good compression method implemented by
`encoder 101 is to attain a high compression ratio with
`minimal loss in fidelity. One of the latest approaches to the
`image compression problem has been put forth by Arnaud
`Jacquin in a paper entitled “Fractal Image Coding Based on
`a Theory of Iterated Contractive Image Transformations”,
`appearing in The International Society for Optical Engineer
`ing Proceedings Volume 1360, Visual Communications and
`Image Processing, October 1990, pp. 227—239.
`As is known in the art, fractal image generation is based
`on the iteration of simple deterministic mathematical pro
`cedures that can generate images with infinitely intricate
`geometries (i.e. fractal images). However, to use these
`fractal procedures in digital image compression, the inverse
`problem of constraining the fractal complexity to match the
`given complexity of a real-world image must be solved. The
`“iterated transformation” method of Jacquin constructs, for
`each original image, a set of transformations which form a
`map that encodes the original image. Each transformation
`maps a portion of the image (known as a domain) to another
`portion of the image (known as a range). The
`transformations, when iterated, produce a sequence of
`images which converge to a fractal approximation of the
`original image.
`In order for a transformation to map onto some portion of
`the original image within a specified error bound, the
`
`45
`
`50
`
`55
`
`60
`
`65
`
`0005
`
`

`
`5,862,262
`
`3
`ered ranges form a non-overlapping tiling of the image and
`some iterate of the set of selected transformations is con
`tractive. Information that identifies the set of covered ranges,
`domains and corresponding optimized transformations is
`stored compactly in an addressable memory.
`
`DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a schematic of the basic elements of a digital
`image compression system;
`FIG. 2 is a graphical representation of the mapping
`process according to the present invention;
`FIGS. 3(a)–3(g) depict a simple image that is encoded by
`the method of the present invention;
`FIG. 5 is a schematic configuration of an apparatus for
`carrying out the method of the present invention; and
`FIG. 6 is a more detailed schematic configuration of the
`encoder of FIG. 5.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`A digital image is defined by an array of individual pixels.
`Each pixel has its own level of brightness which, for
`monochrome images, has many possible gray levels, not just
`black or white. Thus, this type of image can be thought of
`as a three-dimensional object where each pixel has (x,y)
`positional coordinates and an intensity value coordinate z.
`As is known in the field of image compression, collections
`of these pixels can contain redundant information. Thus,
`image compression techniques remove such redundant
`information from an image (i.e., encode an image) in such
`a way that, after storage or transmission, the redundant
`information can be put back into the image (i.e., decode an
`image) resulting in a facsimile, or an approximation of the
`original collection of pixels.
`The goal of fractal image encoding is to store an image as
`the fixed point of a map W:F->F from a complete metric
`space of images F, to itself. The space F can be taken to be
`any reasonable image model (collections of pixels), such as
`the space of bounded measurable functions on the unit
`square, etc. In this model, f(x,y) or z represents the gray
`level of a pixel at the point (x,y) in the image. The mapping
`W, or some iterate of W, is a contraction to insure rapid
`convergence to a fixed point upon iteration from any initial
`image. The goal is to construct the mapping W with a fixed
`point “close” (based on a suitable metric) to a given image
`that is to be encoded, and such that the map W can be stored
`compactly. Let I=[0,1] and I" be the m-fold Cartesian
`product of I with itself. Let F be the space consisting of all
`graphs of real Lebesgue measurable functions Z=f(x,y) with
`(x,y,f(x,y))e?’. A simple metric that can be used to measure
`fidelity is the sup metric 8,
`
`Other metrics, such as the rms metric 5,
`
`have more complicated contractivity requirements. The rms
`metric is particularly useful since it can be easily minimized
`by performing standard regression of the algorithmic param
`eters. In the remainder of this description, the metric will be
`specified when relevant.
`Since a typical digital image may be divided into a
`plurality of collections of pixels containing redundant
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`information, the map W is constructed from local transfor
`mations wº. Each local transformation w, is a transformation
`that maps one image area containing pixels (or domain D.)
`from the image onto another image area containing pixels
`(or range R.) from the image. Arriving at the best set of
`domains for a particular image is the goal of the present
`invention. Here, the “best” set is one which achieves a
`desired level of compression at the highest achievable level
`of fidelity, or a desired level of fidelity at the highest
`achievable level of compression.
`As a first step in an iterated transformation encoding
`method, the digital image is defined as a plurality of data
`points having (x,y,z) coordinates that are stored in a com
`puter memory. According to the principles of the iterated
`transformation process, domains (i.e., a domain D, being a
`section of the image area containing a collection of pixels)
`are mapped onto ranges (i.e., a range R, being a section of
`the image area containing a collection of pixels) according
`to the parameters of the local transformations. Thus, for a
`range R, a domain D, and corresponding local transforma
`tion w, are sought that will minimize the error between the
`image over R, and the transformation of the image over Dr.
`By adhering to the principles of the iterated transformation
`process, a set of transformations (and corresponding
`domains) are obtained that, when iterated from any initial
`starting point, will converge to a fixed point that approxi
`mates the desired image. The set of ranges, domains and
`transformations therefore encode the image. Thus, to store
`or transmit the image, only information defining the ranges,
`domains and transformations need be stored or transmitted.
`From the ranges, domains and transformations, an approxi
`mation to the original image can be constructed (decoded).
`If the ranges, domains and transformations can be defined
`more compactly than the original image, then image com
`pression is attained.
`A graphical representation of the above described map
`ping process is shown in FIG. 2 where the x,y,z coordinate
`system is used to define a domain D, which is a subset of the
`area that comprises the entire image area 10. As is evident
`from FIG. 2, D, is a portion of the image area 10 which
`contains pixels at various levels of gray as indicated by the
`z component thereof. A transformation w, is chosen such that
`the domain D, can map onto a range R, which is another
`subset of the image area 10.
`Thus, the overall transformation map W is defined as
`
`i = 1
`
`The transformations wi, . . . ,w, (i.e., the map W) must tile
`the image. This means that each D, defines a part of the
`image to which w, is restricted. When w, is applied to this
`part, the result maps onto a range R. The R, must be
`non-overlapping and the union of the Rº's must cover the
`image. Given W, it is easy to find the image that it encodes.
`Simply begin with any image fo and successively compute
`W(fo), W(W(fo)), . . . until the images converge to [W].
`However, the converse is considerably more difficult for a
`given image f, i.e., how can a mapping W be found such that
`[W]=f/ Essentially, an image feF is sought such that Ö(f,f)
`is minimal with f-|W. Given equation (3), it is reasonable
`to seek domains D1, . . . ,D, and corresponding transforma
`tion w1, . . . ,w, such that
`
`0006
`
`

`
`5,862,262
`
`w;(f)
`
`(4)
`
`Equation (4) says that the transformations w;, when applied
`to f, should result in f. The local transformations wi(f), . . .
`,w,(f) are said to cover the image f. Equality of equation (4)
`would imply that f=|W. Being able to exactly cover f with
`parts of itself is not likely, so the best possible cover is
`sought with the hope that W and f will not look too
`different, i.e., that Ö([W],f), the error using an appropriate
`metric, is small.
`Thus, the encoding process can be summarized as fol
`lows: For each range R, a transformation w, restricted to a
`domain D, is sought such that the error (measured by an
`appropriate metric) between the result of applying w, to the
`image, and the part of the image over R, is minimized. This
`is called “covering” the range. The map W is specified by the
`transformations w; and their corresponding domains Dr. The
`w,’s must tile the image, and must be chosen such that some
`iterate of W is contractive.
`A form for the transformations w;, which is convenient for
`encoding a gray scale image is,
`
`10
`
`15
`
`20
`
`jº.
`e;
`y | + || Ji
`2.
`©i
`
`Here, contractivity refers to contractivity in the z direction.
`In the present invention, choosing a set D of all possible
`domains from which the D.’s are chosen, and a set R of all
`possible ranges from which the Rº's are chosen, is accom
`plished by adaptive partitioning based on features of the
`image to be encoded. Accordingly, “adaptive partitioning” in
`the present invention is adaptive in a more general way than
`methods such as the aforementioned quad-tree partitioning.
`A general description of the adaptive partitioning according
`to the present invention will now be presented.
`The goal in choosing R and D is to have domains that
`cover ranges well. Therefore, it would be advantageous to
`partition the image such that this goal is likely to be
`achieved. In the prior art quad-tree type partitioning, select
`ing one of the predefined subdivisions occurs when good
`coverings cannot be found, but the positions of the subdi
`visions are not adaptive. A current range square is simply
`divided into four equally sized squares without considering
`the features of the image. In the adaptive partitioning
`process of the present invention, subdividing occurs when
`good coverings cannot be found, but the subdivision posi
`tions are chosen based on the features of the image. Divi
`sions are made so that the features of the newly created
`
`45
`
`50
`
`55
`
`60
`
`65
`
`b; O
`jº.
`(t;
`di 0
`w; y | = | c.
`2.
`0 0 si
`where, for each pixel in
`a, b, c, and d, are positional scaling coefficients for
`transforming the position of the pixel;
`s, is the intensity scaling coefficient for transforming the
`gray level of the pixel;
`e; and f, are positional offset coefficients for the pixel; and
`o, is an intensity offset coefficient for the pixel.
`The only restriction on the transformations is that the map W
`(or some iterate of W) must be contractive. This could be
`assured under the metric of equation (1) by requiring that,
`for all w,
`
`(5)
`
`25
`
`30
`
`35
`
`40
`
`6
`ranges are such that there will be domains which can
`efficiently cover them. For this to be possible, the domains
`must also be adaptively defined. This is facilitated in the
`present invention by having D defined by the identical
`partitioning that defines R. This is a fundamental change
`from the prior art where D is a predefined set.
`Partitioning in the present invention is performed concur
`rently with the process of selecting transformations that
`encode the image. Accordingly, the encoding process of the
`present invention could simply begin with one domain
`encompassing the entire image area and a few (e.g., two)
`ranges, the union of which is the entire image area. If a
`transformation cannot be found to map the one domain onto
`one of the ranges, the range is subdivided. Specifically, the
`range is subdivided into a few (e.g., two) sections, where the
`positions of the subdivisions are adaptive to the content of
`the image. Thus, the larger range is replaced with smaller
`ranges. The set of possible domains is increased by the large
`(just subdivided) range. If a transformation is found that
`covers the range, the covered range is added to the set of
`domains. Thus, by defining the ranges and the domains by
`the same partition, the information required to define the
`map that encodes the image is reduced.
`In the present invention, choosing the location of the
`partitions is done such that both ranges and domains are
`created in a way that the domains are likely to cover the
`ranges efficiently (i.e., the domain set D contains fewer
`members and still results in good coverings). Furthermore,
`because the ranges are efficiently covered by the domains,
`fewer ranges are required to fully cover the image. Thus,
`even though such an adaptive partitioning method must store
`more information per domain and range (i.e., per
`transformation) than simpler quad-tree partitioning, the
`reduction in the number of transformations can reduce the
`total amount of information which must be stored.
`The partitioning of the image describes the geometry of
`the ranges and domains thereby partially defining the map
`W, and therefore must be stored as part of the encoded
`image. Storing the partitioning information compactly is
`simple and is well known in the art. It may be stored as a
`sequence of information denoting the orientation of the
`partitions, and an offset value that determines the position of
`the partitions at each step. As the rectangles get smaller,
`fewer bits are required to store the offset so that the memory
`cost decreases as more rectangles are added. Naturally, to
`define the w;’s, it is also necessary to store information
`identifying the symmetry operation (i.e., the positional
`coefficients) used in transforming the domains onto the
`ranges, the intensity scale coefficient and the intensity offset
`coefficient. The above described encoding procedure may be
`carried out to achieve: 1) the best attainable fidelity (defined
`by the error metric) for a predetermined target compression,
`2) the best attainable compression for a predetermined target
`fidelity, or 3) a balance between the two.
`As an example of a method of partitioning, the image can
`be subdivided so that edge-like features in the image,
`indicative of changes in intensity level, tend to run diago
`nally through (or along the edges of) ranges and domains. A
`specific example of this type of partitioning, called
`HV-partitioning, is described further hereinbelow.
`The HV-partitioning scheme derives its name from the
`horizontal and vertical partitions that it makes. Unlike the
`quad-tree methods which divide a square in a fixed fashion,
`HV-partitioning provides for variable partitioning of rect
`angles. Each partitioning step consists of partitioning a
`rectangle either horizontally or vertically into two rect
`angles. When a rectangle that contains a horizontal or
`vertical edge is partitioned, the partition occurs along the
`
`0007
`
`

`
`7
`strongest such edge. If a rectangle contains other edges, the
`partition should occur in such a way that the edge intersects
`one of the generated rectangles at its corner, with the other
`rectangle not containing this edge. This tends to result in
`rectangles which either contain no edges, or rectangles that
`have edges which run diagonally across the rectangle.
`As described above, according to the HV-partitioning
`scheme the set D is dynamic and changes before each new
`range rectangle is processed. The change in the set D is that
`the last rectangle processed is added to D. Since this tends
`to create domains with no edges or edges that run diagonally,
`it is likely that choosing domains in this fashion will result
`in domains that cover the ranges well using the transforma
`tion matrix given in equation (5). This is true for the
`following reason.
`The transformation maps a rectangle (i.e., domain) with a
`given size and aspect ratio onto a rectangle (i.e., range) of
`different size and aspect ratio. An edge feature running
`diagonally through a domain rectangle (or along the edge of
`the domain rectangle) will also run diagonally through the
`transformed domain rectangle (or along the edge of the
`transformed domain rectangle). Since the partition is made
`so that the range rectangles also have the most prominent
`edge features running diagonally (or along an edge), the
`likelihood of the image features in the transformed domain
`matching the image features in the range is improved. As a
`result of the improved probability that a given domain will
`cover a range well, the number of domains necessary to
`achieve a good encoding using the HV-partitioning scheme
`is considerably less than the number of domains necessary
`for quad-tree partitioning. In addition, this also means that
`larger ranges are more likely to be covered well, thus
`reducing the number of transformations needed. The reduc
`tion in the number of ranges and domains necessary to
`encode the image compensates for the greater amount of
`memory (per transformation) required to store encoding
`information produced as a result of the HV-partitioning.
`Referring to FIGS. 3(a)–3(g), a description of the present
`invention by means of a tutorial example will now follow.
`FIG.3(a) is a simple image with only two levels of intensity
`(i.e., black and white) which is to be encoded. The “black”
`regions are represented in FIGS. 3a–3g by dotted areas. The
`image contains two edge features 12 and 14 as they will be
`referred to hereinafter. Each “edge feature” is indicative of
`a change in image (i.e., pixel) intensity along some edge of
`an image feature.
`According to the present invention, the entire image area
`is the first range R1 in a set of ranges R. Proceeding
`according to the HV-partitioning scheme described above,
`the image is adaptively subdivided such that the most
`prominent edge feature 12 in the image runs along the edge
`of the subdivision. The resulting two image areas are new
`ranges R2 and Rs as shown in FIG.3(b). Finding the position
`where this edge is located is carried out using methods well
`known in the art. For example, in this image, values of
`adjacent pixels (not shown) in the image could be summed.
`Pixel values would then be summed vertically and horizon
`tally. Edge feature 12 would be detected by computing
`successive differences of the vertical sums. Note that if edge
`feature 12 were a vertical feature, it would be detected by
`computing successive differences of the horizontal sums.
`The image area just subdivided, in this case the entire
`image area or range R1, is added to the set of domains D.
`Since this is the first domain being added to the set D, it is
`designated as D1 as shown in FIG. 3(a). A domain and
`transformation are now sought which cover the uncovered
`ranges (i.e., R2 and Rs). However, the only domain in the set
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,862,262
`
`8
`D is D1, and since it does not cover R2 or Rs well,
`partitioning continues as shown in FIG. 3(c). Here R2
`(which contains no edge features at all) is subdivided in half
`resulting in two new ranges Ra and Rs. As before, the image
`area just subdivided (i.e., R2) is added to the domain set D
`as D2. Since Rs cannot be covered by D1 or D2, it is
`subdivided. In this case, the subdivision is adaptively posi
`tioned such that one of the rectangles resulting from the
`subdivision has no edge feature, and the other rectangle
`resulting from the partition has a diagonal edge-like feature.
`This is illustrated in FIG. 3(d) where it is apparent that edge
`feature 14 runs diagonally through a rectangle. As before,
`the image area just subdivided (i.e., Rs) is added to the
`domain set D as Ds. A domain and transformation are now
`sought to cover the uncovered ranges Ra, Rs, Ra and R7.
`The ranges Ra and Rs can be covered by D2. Therefore,
`Ra and Rs are: 1) marked as covered, 2) added to the domain
`set D as Da and Ds, and 3) information defining the
`transformations and corresponding domain are saved. A
`domain and transformation are now sought that will cover
`the ranges Re and R7. The range R., can also be covered with
`D2, so it is marked as covered and the appropriate informa
`tion is saved. The encoding procedure continues on in a
`similar fashion to partition Re into Rs and Ro (FIG. 3(e)),
`and Rs into Rio and Ru (FIG. 3(f)).
`In FIG. 3(f) it is apparent that Rio can be covered with D2,
`and R11 can be covered with De. Finally, the last necessary
`partition is shown in FIG. 3(g) where Ro is partitioned into
`R12 and R1s. Here it is apparent that R12 can be covered by
`De, and R1s can be covered by D2. The covered ranges Ra,
`Rs, R7, Rio, R11, R12 and R13 tile the image area. The
`transformations and corresponding domains that cover these
`ranges form a contractive map W that encodes the image.
`It is clear that a description of the partitioning of the
`image must be included in defining the map W. Accordingly,
`storing such an adaptive partition requires more memory per
`subdivision than simpler partitioning techniques. However,
`this simple example illustrates how adaptive partitioning can
`result in a small number of subdivisions that define a small
`number of ranges and domains that accurately encode the
`image. Therefore, encodings with good compression and
`fidelity can be attained.
`The above simple example explains the operation of the
`present invention.
`Mapping domains onto ranges is slightly more complex
`using HV-partitioning as compared with quad-tree partition
`ing. In the quad-tree schemes, domains are typically chosen
`to be larger by an integer multiple so that averaging trans
`formed domain pixels onto a range pixel is easy. In the
`HV-partitioning scheme, proper averaging is computation
`ally expensive. One alternative is to simply choose a rep
`resentative domain pixel for each range pixel. Another
`alternative, leading to better results at the expense of com
`putation time, is to average only those domain pixels that
`map wholly within a range pixel, and to ignore those that
`contribute a fraction of their whole value.
`An important consideration which arises in the
`HV-partitioning scheme is contractivity in the xy plane.
`Contractivity in the xy plane means that for any two points
`in the xy plane, the distance between the points measured in
`an appropriate metric is larger before the transformation
`than after. Contractivity of the w;’s in the xy plane is not
`required because
`
`0008
`
`

`
`(7)
`
`10
`
`15
`
`20
`
`30
`
`25
`
`F2 =
`i
`In the HV-partitioning scheme, there are