[go: up one dir, main page]

WO1995008161A1 - Algorithmes de domaine de puissance pour la decompression fractale d'images - Google Patents

Algorithmes de domaine de puissance pour la decompression fractale d'images Download PDF

Info

Publication number
WO1995008161A1
WO1995008161A1 PCT/GB1994/002000 GB9402000W WO9508161A1 WO 1995008161 A1 WO1995008161 A1 WO 1995008161A1 GB 9402000 W GB9402000 W GB 9402000W WO 9508161 A1 WO9508161 A1 WO 9508161A1
Authority
WO
WIPO (PCT)
Prior art keywords
image
node
pixel
tree
level
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/GB1994/002000
Other languages
English (en)
Inventor
Abbas Edalat
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Imperial College of London
Original Assignee
Imperial College of London
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Imperial College of London filed Critical Imperial College of London
Priority to AU76199/94A priority Critical patent/AU7619994A/en
Publication of WO1995008161A1 publication Critical patent/WO1995008161A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/001—Model-based coding, e.g. wire frame

Definitions

  • the present invention relates to image decompression, and particularly to the decompression of images stored in Iterated Function System (IFS) format, either with or without probabilities.
  • IFS Iterated Function System
  • IFS format Brief details of IFS format, and how it is currently used as a convenient format in which to store compressed images are given in section 1 below.
  • the two known algorithms which are commonly used for decompressing an image stored in IFS format, the random iteration algorithm and the greyscale photocopy algorithm are both relatively slow.
  • both operate by iterative processes, and it is normally impossible to decide in advance how many iterations will be required to produce a reasonable decompressed image at a particular resolution.
  • the number of iterations to be used is either decided arbitrarily in advance, or (when the decompression is being carried out interactively) the user simply watches the image building up on a computer screen and stops the process when the image appears subjectively acceptable. Neither of these is of course ideal.
  • the number of iterations is indeterminate, it is not possible to provide an analytical complexity analysis to determine how long it will take each of the prior art algorithms to decompress a given image to a particular resolution.
  • a method of decompressing a compressed image stored in IFS format having N maps f 1 ... f N . the image to be decompressed to a resolution corresponding to a pixel size q comprising:
  • nodes f 1 X 0 ... f N X 0 to produce a second-level series of nodes f l f l x 0 ...
  • nodes are defined as leaf nodes
  • clauses (c) to (g) are separate steps which will necessarily be carried out sequentially.
  • each pixel of the decompressed image can be calculated immediately that the first leaf node corresponding to that pixel has been found. That is the case with the Plotkin power domain algorithm, in which the IFS generates a black and white image.
  • an individual pixel will be set to white (if the ground is black) or black (if the ground is white) immediately that a leaf node is located which corresponds to that particular pixel. That particular pixel may then be output or stored (step (g) in Claim 1) immediately, without waiting for the entire tree to be built up.
  • the tree will not necessarily be built up by applying clauses (c) to (e) strictly sequentially.
  • the tree is searched branch by branch, rather than level by level, with each branch being followed until it results in a leaf node.
  • the algorithm may then back-up the tree to the next closest branching point, and follow the branch on from there until it reaches the next leaf node.
  • the tree may be sequentially searched by this method until all leaf nodes have been found.
  • the tree is searched level by level; in other words the first level of nodes is built up from the root point, and each node on that level is checked to see whether it is a leaf node.
  • the algorithm then proceeds sequentially through all of the nodes on the first level, constructing branches from each of those nodes to the nodes on the second level. As the second level nodes are being built up, the algorithm systematically checks whether each newly created node is a leaf node.
  • the algorithm which constructs the tree does not form any additional nodes onto those nodes which have been identified as leaf nodes.
  • the tree may be conveniently searched by a recursive algorithm, for example an algorithm having a recursively-defined procedure which takes as input a given node and produces as output all those next-level nodes which hang from the input node.
  • a recursive algorithm for example an algorithm having a recursively-defined procedure which takes as input a given node and produces as output all those next-level nodes which hang from the input node.
  • the decompressed image may be in black and white, with each pixel in the decompressed being white if one or more of the leaf nodes corresponds to that pixel, and black otherwise; or vice versa.
  • Such an image would normally be produced from a compressed image stored in IFS format without probabilities.
  • a black and white image may be obtained from an IFS image with probabilities, simply by ignoring the probabilities. That will represent the support of the coloured or greyscale image.
  • An image stored in IFS format with probabilities may be decoded as a greyscale image or as a coloured image (with suitable mapping).
  • each node in the tree has a node weight associated with it, each node weight being the product of the probabilities corresponding to all of the maps that make up the said node.
  • the initial or root node corresponds to the unit square, and that is given weight 1. All of the nodes at any particular level have a cumulative weight of 1.
  • the colour or density of each pixel in the decompressed image may be a function of the sum of the node weights of all the leaf nodes corresponding to the said pixel.
  • the maximum size of the parallelogram corresponding to each individual node may be determined by calculating, for example, the maximum length that the side of the parallelogram can take.
  • the maximum size is determined according to the contractivity of the various transformations making up the parallelogram.
  • the maximum size of the parallelogram may be taken as the product of the contractivities of the transformations which make up the corresponding node.
  • the repeated mappings may be applied to a single point on or within the parallelogram. Since each parallelogram must eventually shrink to the size of a single pixel, it can be guaranteed that applying the transformations repeatedly to a single point within the parallelogram will ensure that the position of that point eventually converges to the same pixel.
  • a convenient choice for the root point is the centre of the area A, within which the image is to be reconstructed. Because of the nature of the transformations, each transformation applied to the central point Xo will map that point to the exact centre of the parallelogram which results from applying that pa ⁇ icular mapping to A.
  • the area A is taken to be the unit square, by suitable scaling if necessary (ie the area A may be rescaled to the unit square between (a) and (b) of Claim 1).
  • the individual pixel size may then be taken as 1/r, where r is the screen resolution at which the decompressed image is to be plotted. Alternatively, one could of course equivalently take the pixel size to be one unit square, in which case the area A would have side r.
  • each of the maps f 1 ...f N are applied to the same point X 0 .
  • fractal image compression In fractal image compression, one seeks to encode and decode a colour or a greyscale digitised image on the computer screen.
  • a colour map a colour or a greyscale image can be presented by assigning a number to each pixel indicating its brightness or intensity. We can think of this number as the weight of the pixel. Any section of the image will then have a total weight equal to the sum of the weights of its pixels. It is technically convenient to rescale the weights of pixels so that the screen as a whole, consisting of say r x r pixels (where r is the resolution of the screen), has unit weight in total. In this way, we say that the image is represented by a normalised measure on the screen, which we can regard as the unit square.
  • any normalised measure on the screen i.e any distribution of weights on pixels which add up to one corresponds to an image.
  • the encoding of an image is achieved by doing a self-tiling of the image using a family of weighted afl ⁇ ne transformations of the plane. We will describe this in more detail in section 1.3.
  • An affine transformation of the plane is a combination of a rotation, a rescaling, a sheer and a translation in the plane.
  • Any affine transformation f : R 2 ⁇ R 2 of the plane has the form
  • the matrix is the linear part of the transformation; it is the combination of a rotation, a rescaling and a sheer.
  • the vector is the linear part of the transformation; it is the combination of a rotation, a rescaling and a sheer.
  • An affine transformation is contracting if there is a number s with 0 ⁇ s ⁇ 1 such that the distance between any two points (x 1 , y 1 ) and (x 2 ,y 2 ) on the plane is contracted by at least a factor s, i.e.
  • an IFS with probabilities determines a unique normalised measure, i.e. a unique image on the plane, called the invariant measure of the IFS. Therefore, we can say that the IFS encodes this measure or image.
  • the existence and uniqueness of the invariant measure is shown in [Bar88, page 336].
  • the IFS with probabilities with the code given in the table above determines the image of a fern shown in Figure 1. The picture on the left is the actual greyscale image, whereas the picture on the right gives the support of the image in white.
  • the greyscale photo copy algorithm is equipped with an operator M, called the Markov operator, which given any image ⁇ as input produces a new image M( ⁇ ) as output.
  • M is a digitised image, i.e. for each pixel z kl (l ⁇ k, l ⁇ ⁇ ) we have ⁇ (z kl ) ⁇ 0 with ,
  • f i -1 ( z kl ) is the set of all pixels which are mapped to z kl by f i .
  • the algorithm starts with an initial digitised image ⁇ and repeatedly applies M until a convergence to an image takes place. This limiting image is then the required image: It is the digitised approximation to ⁇ *. In most practical embodiments, the initial image is taken to be a uniformly grey image.
  • the random iteration algorithm generates the image corresponding to an IFS with probabilities
  • the random iteration algorithm To use the random iteration algorithm one has to fix a number n of iterations in advance, which for each IFS with probabiUties is found by trial and error for any given resolution of the screen. Furthermore, the selection of the integer i from 1,2, . .. , N with probability p i is quite time consuming as it takes about log 2 N computational steps. Last but not least, the algorithm, as it is random, may fail, during the n iterations specified, to visit some of the pixels which have non-zero ⁇ * value, i.e. which in fact lie on the support of the original image.
  • Each term p i ⁇ o f i -1 in the above sum represents a copy of the original image transformed by the map /, and attenuated in brightness by the factor p i . Therefore the above equation represents a self-tiling, or a collage, of ⁇ . Therefore, one proceeds by first assuming all probabiUties are zero except p l . Then h and p i are chosen such that P 1 ⁇ o f 1 -1 approximates a part of the image ⁇ . Next p 2 is allowed to be non-zero, and f 2 and p 2 are chosen so that p 1 ⁇ o f 1 -1 -+ p 2 ⁇ o f 2 -1 approximates a larger part of the image.
  • Figure 2 shows a fern (to be considered as a black and white image) on the left, a collage of four tiles with the following IFS code in the middle, and the decompressed image on the right.
  • Figure 1 shows an image created from an IFS with probabiUties. along with the corresponding support:
  • Figure 2 shows an image to be encoded, the tiling for an IFS code, and the corresponding decompressed image
  • Figure 3 illustrates in schematic form a tree which is produced by the algorithm of the present invention
  • Figure 4 represents a branch of the tree of Figure 3.
  • the probabilistic power domain algorithm generates the invariant measure of an IFS with probabilities, i.e. it decodes an image. It is therefore an alternative to the greyscale photo copy algorithm and the random iteration algorithm described in the last section.
  • the root of the tree is the unit square X on depth zero.
  • each of the parallelogram in the tree a weight.
  • the unit square X is given weight one. This weight is distributed among the parallelograms on the next level by giving each f i X weight p i .
  • the weight p t is then redistributed among the children of f i X by giving f i f j X weight p i p j . Note that
  • Each branch of the tree eventually shrinks to a pixel.
  • n [- log r/ logs] + 1, where [a] is the greatest integer less than or equal to a, all parallelograms on level n have already shrunk to pixels, i.e.
  • ⁇ * is computed.
  • the value ⁇ * ⁇ z) for a pixel z is given simply by the sum of the weights of all the leaves which are represented by z.
  • the algorithm therefore traverses the finite tree in some specified way in order to find the leaves and their weights. Then, for each pixel the weights of the leaves represented by that pixel are summed up to give the total weight of each pixel, which determines the normaU ed measure ⁇ " .
  • Figure 5 illustrates more graphically what is happening at each branch of the tree.
  • the individual mappings (three in this case) are applied to create the three large parallelograms f 1 X, f 2 X and f 3 X.
  • Each of the three mappings is then applied again to each of the three parallelograms.
  • the repeated operation is shown only for the mapping f 1 .
  • Applying the mapping f 1 to the three parallelograms f 1 X, f 2 X and f 3 X produces the three smaller parallelograms f 1 f 1 X, f 1 f 2 X and f 1 f 3 X.
  • the procedure is repeated, down every branch, until every parallelogram has shrunk to the size of a single pixel.
  • T x r array of real numbers ⁇ * (z kl ) gives the weights assigned to the pixels z kl for 1 ⁇ k,l ⁇ ⁇ . It will be appreciated that the algorithm does not make use of the positions of the parallelograms at all: merely the positions of their central points, and the bounds on the length of their sides.
  • the probabilistic power domain algorithm by efficiently traversing the finite tree, uses the least number of computations to make the best possible digitised approximation to the invariant measure of an IFS with probabiUties.
  • [a] is the greatest integer less than or equal to a.
  • a simple calculation shows that at each stage of computation 10 arithmetic operations have to be performed. It follows that the total number of computations performed by the algorithm before it stops is between 10(N + N 2 + . . . + N h ) and 10( ⁇ ' + N 2 + . . . + ⁇ " 1' ), i.e between and .
  • the probabiUstic power domain algorithm Since one cannot have a complexity analysis for the greyscale photo copy algorithm and the random iteration algorithm (as in both cases one has to specify the number of iterations by trial and error), we cannot make a direct analytical comparison between the probabiUstic power domain algorithm and the other two. However, on all inputs we have tried, the probabiUstic power domain algorithm is, often up to several times, faster than the random iteration algorithm in producing a good quality image.
  • An IFS ⁇ f i ,f i , . . . , f N generates a black and white image which is in fact the support of the invariant measure of (f 1 , , f 2 , . . . , f N ; p 1 ,p 2 , . . . , P N ) for any set of probabilities P i assigned to the maps f i .
  • This black and white image can be obtained using the photo copy algorithm [BH93].
  • the Plotkin power domain algorithm decodes an IFS to give a black and white image. The same tree given in the section 2 is used. This time however there are no weights assigned to the nodes. The algorithm simply determines the leaves of the tree and plots the corresponding pixels on the screen. Again the algorithm terminates without needing to specify a number of iterations.
  • a pixel forms part of the image if that pixel corresponds to at least one of the leaf nodes in the tree. Accordingly, the pixel can be plotted immediately that a leaf node is reached.
  • the pseudo-code for the Plotkin power domain algorithm is similar to that set out at section 2.2.1 above, except that all reference to node weights is omitted.
  • the pixel may be plotted at the Une currently devoted to calculating the total pixel weight, so that the final plotting step (step 3) may be omitted.
  • Both the probabiUstic power domain algorithm and the Plotkin power domain algorithm share a number of advantages: they terminate in finite time on any digitised screen without the necessity of fixing the number of iterations in advance; there is a simple complexity analysis (given in section 2.3 above); and the algorithms produce good quality images normally several times faster than in the prior art.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Image Processing (AREA)

Abstract

Un procédé de décompression d'une image couleur ou à échelle de gris stockée en format de systèmes de Fonctions Itératives (IFS) à probabilités consiste à appliquer tour-à-tour chaque transformation au carré unitaire afin de produire une série de parallélogrammes dont chacun est contenu dans le carré unitaire. Chaque transformation est ensuite appliquée à chacun des parallélogrammes pour produire un second niveau de prallélogrammes qui seront tous plus petits que les parallélogrammes parents et qui seront contenus dans ces derniers. Le procédé est répété jusuq'à ce que les parallélogrammes soient réduits à la taille d'un unique pixel. La couleur ou l'intensité de chaque pixel de l'image décomprimée peut alors être calculée en fonction du nombre de parallélogrammes qui ont subi une réduction jusqu'à ce pixel particulier, et qui ont été pondérés selon un facteur de pondération de parallélogrammes. On peut traiter les images en blanc et noir en ne prenant pas en compte les probabilités.
PCT/GB1994/002000 1993-09-17 1994-09-14 Algorithmes de domaine de puissance pour la decompression fractale d'images Ceased WO1995008161A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU76199/94A AU7619994A (en) 1993-09-17 1994-09-14 Power domain algorithms for fractal image decompression

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
GB9319314.2 1993-09-17
GB939319314A GB9319314D0 (en) 1993-09-17 1993-09-17 Power domain algorithms for fractal image decompression

Publications (1)

Publication Number Publication Date
WO1995008161A1 true WO1995008161A1 (fr) 1995-03-23

Family

ID=10742177

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/GB1994/002000 Ceased WO1995008161A1 (fr) 1993-09-17 1994-09-14 Algorithmes de domaine de puissance pour la decompression fractale d'images

Country Status (3)

Country Link
AU (1) AU7619994A (fr)
GB (1) GB9319314D0 (fr)
WO (1) WO1995008161A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE19641157A1 (de) * 1996-10-07 1998-04-16 Thomson Brandt Gmbh Verfahren zur Überprüfung der Konvergenz bei der fraktalen Bildcodierung

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
EDALAT A: "Dynamical systems, Measures and Fractals via Domain Theory", THEORY AND FORMAL METHODS 1993, 1993, pages 82 - 99 *
EDALAT A: "Power Domain Algorithms for Fractal Image Decompression", DEPARTMENT OF COMPUTING, IMPERIAL COLLEGE, vol. 93/44, 1993, LONDON, pages 1 - 12 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE19641157A1 (de) * 1996-10-07 1998-04-16 Thomson Brandt Gmbh Verfahren zur Überprüfung der Konvergenz bei der fraktalen Bildcodierung
US5978516A (en) * 1996-10-07 1999-11-02 Deutsche Thomson-Brandt Gmbh Method for checking convergence in fractal image coding

Also Published As

Publication number Publication date
AU7619994A (en) 1995-04-03
GB9319314D0 (en) 1993-11-03

Similar Documents

Publication Publication Date Title
US6144773A (en) Wavelet-based data compression
US7230616B2 (en) Bi-level iso-surface compression
KR100233972B1 (ko) 기하학적 모델을 압축 및 압축해제하는 컴퓨터 시스템과 압축 및압축해제
AU632333B2 (en) Method and apparatus for processing digital data
US5764807A (en) Data compression using set partitioning in hierarchical trees
JP3378257B2 (ja) 希薄データセットをネスト状分割コード化するシステム及び方法
US6009435A (en) Progressive compression of clustered multi-resolution polygonal models
Guéziec et al. A framework for streaming geometry in VRML
Culik et al. Digital images and formal languages
JPH11502043A (ja) フラクタル変換を使用するデジタルデータの圧縮伸張方法および装置
WO1996031975A1 (fr) Procede et systeme de representation d'un ensemble de donnees avec fonction de transformation de donnees et masque de donnees
US5717787A (en) Method for data compression by associating complex numbers with files of data values
Albert et al. Digital image compression
US6714687B2 (en) Image encoding/decoding method, apparatus thereof and recording medium in which program therefor is recorded
Saupe et al. A guided tour of the fractal image compression literature
Fisher et al. Fractal image compression for mass storage applications
WO1995008161A1 (fr) Algorithmes de domaine de puissance pour la decompression fractale d'images
JP3286213B2 (ja) 幾何モデルを圧縮し圧縮解除する方法及びシステム
Jacobs et al. Fractal-Based Image Compression, II
Abdollahi et al. Lossless image compression using list update algorithms
Kopp Lossless wavelet based image compression with adaptive 2D decomposition
Lewiner et al. Simplicial Isosurface Compression.
Chong et al. Parallel implementation and analysis of adaptive transform coding
Wong et al. Fractal-based image coding with polyphase decomposition
JP2693557B2 (ja) 符号化装置

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AM AT AU BB BG BR BY CA CH CN CZ DE DK EE ES FI GB GE HU JP KE KG KP KR KZ LK LR LT LU LV MD MG MN MW NL NO NZ PL PT RO RU SD SE SI SK TJ TT UA US UZ VN

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): KE MW SD AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE BF BJ CF CG CI CM GA GN ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: CA

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642