Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1995 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Fractal Image Compression

Theory and Application

herausgegeben von: Yuval Fisher

Verlag: Springer New York

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

What is "Fractal Image Compression," anyway? You will have to read the book to find out everything about it, and if you read the book, you really will find out almost everything that is currently known about it. In a sentence or two: fractal image compression is a method, or class of methods, that allows images to be stored on computers in much less memory than standard ways of storing images. The "fractal" part means that the methods have something to do with fractals, complicated looking sets that arise out of simple algorithms. This book contains a collection of articles on fractal image compression. Beginners will find simple explanations, working C code, and exercises to check their progress. Mathematicians will find a rigorous and detailed development of the subject. Non-mathematicians will find a parallel intuitive discussion that explains what is behind all the "theorem-proofs." Finally, researchers - even researchers in fractal image compression - will find new and exciting results, both theoretical and applied. Here is a brief synopsis of each chapter: Chapter 1 contains a simple introduction aimed at the lay reader. It uses almost no math but explains all the main concepts of a fractal encoding/decoding scheme, so that the interested reader can write his or her own code. Chapter 2 has a rigorous mathematical description of iterated function systems and their gen­ eralizations for image encoding. An informal presentation of the material is made in parallel in the chapter using sans serif font.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Introduction
Abstract
A picture may be worth a thousand words, but it requires far more computer memory to store. Images are stored on computers as collections of bits representing pixels, or points forming the picture elements. (A bit is a binary unit of information which can answer one “yes” or “no” question.) Since the human eye can process large amounts of information, many pixels—some 8 million bits’ worth—are required to store even moderate-quality images. These bits provide the “yes” or “no” answers to 8 million questions that determine what the image looks like, though the questions are not the “is it bigger than a bread-box?” variety but a more mundane “what color is this or that pixel?”
Y. Fisher
Chapter 2. Mathematical Background
Abstract
Hutchinson [36] introduced the theory of iterated function systems (a term coined by M. Barnsley) to model collections of contractive transformations in a metric space as dynamical systems. His idea was to use the Contractive Mapping Fixed-Point Theorem to show the existence and uniqueness of fractal sets that arise as fixed points of such systems. It was Barnsley’s observation, however, that led to the idea of using iterated function systems (IFS’s) to encode images. He noted that many fractals that can be very compactly specified by iterated function systems have a “natural” appearance. Given an IFS, it is easy to generate the fractal that it defines, but Barnsley posed the opposite question: given an image, is it possible to find an IFS that defines it?
Y. Fisher
Chapter 3. Fractal Image Compression with Quadtrees
Abstract
This chapter describes a quadtree-based fractal encoding scheme. The scheme is an extension of the one presented in [45] and is similar to that discussed in [26], [27], and in Chapters 7, 8, and 9. While the results are not optimal, this scheme serves as a reference point for other fractal schemes. It is also a “typical” fractal scheme and a good first step for those wishing to implement their own. The code used to generate the results presented in this chapter is given in Appendix A, along with a detailed explanation of its inner workings.
Y. Fisher
Chapter 4. Archetype Classification in an Iterated Transformation Image Compression Algorithm
Abstract
Determining a good set of transformations that encode an image well is time consuming because for each range an extensive search through the candidate domains is required ([47]). The purpose of classification is to reduce the number of domains that have to be checked in order to find an acceptable covering. References [11] and [44] use a classification scheme based on the idea that by orienting blocks in a canonical form (based on brightness), and then subdividing these primary classes further by the location of strong edges, it should be possible to find good coverings with minimal computation. In fact, this type of classification method performs quite well. In this chapter, a different classification method using archetypes is presented (see [11]). The method for generating a set of archetypes is described, and the archetypes are then used to classify ranges and domains in an iterated transformation image compression encoder. Fidelity versus encoding time data are presented, and compared with a more conventional classification scheme.
R. D. Boss, E. W. Jacobs
Chapter 5. Hierarchical Interpretation of Fractal Image Coding and Its Applications
Abstract
Many interesting features associated with iterated function systems and standard fractals seem to fade away as the fractal coding of images evolves. For example, the property of self- similarity at different resolutions, inherent to fractals, does not show up in a simple form in the image coding problem. In this chapter we will demonstrate a hierarchical model for the fractal encoding of images, and we will use it to show that the properties of self-similarity at different resolutions, and the related notion of fractal dimension, exist in fractal coding of images. Moreover, applications of these properties will be given.
Z. Baharav, D. Malah, E. Karnin
Chapter 6. Fractal Encoding with HV Partitions
Abstract
In this chapter we describe a way to partition images that gives significantly better results. The method, which we call fractal encoding with HV partitioning, also includes several optimizations in the storage of the transformations, the coding, and the decompression algorithm. The partitioning method used to generate the ranges is based on rectangles. A rectangular portion of the image is subdivided, either horizontally or vertically, to yield two new rectangles. The main advantage of this method over the quadtree method is clear: the ranges are selected adaptively,1 with partitions that can correspond to image edges (at least horizontal and vertical ones). This strength also leads to the main drawback: since the domain size is a multiple of the range size, the large number of range sizes leads to a large number of domains and thus to a large number of domain-range comparisons. Also, there are many ways to select the location of the partition, and we will only describe our final implementation. Our search through all the possible implementations was neither systematic nor complete, and it is clear that further work could yield improvements. Nevertheless, this method gives results better than any similar method of which we are aware.
Y. Fisher, S. Menlove
Chapter 7. A Discrete Framework for Fractal Signal Modeling
Abstract
In this chapter we present a description, used in the following three chapters, of fractal signal modeling in a discrete domain setting using linear algebra. We derive Collage Theorems, and we show how the contractivity factors of a certain class of affine operators are derived. A least squares approach for finding the optimal collage is outlined for a broad class of non-linear operators, including the affine case.
L. Lundheim
Chapter 8. A Class of Fractal Image Coders with Fast Decoder Convergence
Abstract
In this chapter we introduce a class of fractal image coders which have the remarkable property of giving exact decoder convergence in the lowest possible number of iterations (which is image independent). The class is related to that introduced by Jacquin [45,46,47,48], employing simple affine mappings working in a blockwise manner. The resulting decoder can be implemented in a pyramid-based fashion, yielding a computationally very efficient structure. Also, a coder offering non-iterative decoding and direct attractor optimization in the encoder is included as a special case. Other benefits of the proposed coder class include more optimal quantization and an improved Collage Theorem.
G. E. Øien, S. Lepsøy
Chapter 9. Fast Attractor Image Encoding by Adaptive Codebook Clustering
Abstract
In attractor image compression systems, the encoders are often computationally intensive. An attractor encoder involves comparisons between two sets of blocks, called range blocks and domain blocks. The most basic type of encoder compares these sets exhaustively in the sense that every possible pair of range and domain domain blocks is examined. Unless the complexity of this task can be reduced, attractor coding may be excluded from many applications. This problem is recognized, and previous publications have presented strategies to overcome it.
S. Lepsøy, G. E. Øien
Chaprer 10. Orthogonal Basis IFS
Abstract
The accurate coding of a range block is dependent upon there being a domain block which is self-similar in the library. As we have seen, this is normally true. However, while coding an image a range block will occasionally be encountered for which no suitable domain block can be found. Normally this situation would result in some reduction of the reconstructed signal quality in the location where the domain block resides. With more complex signals, this can happen more frequently.
G. Vines
Chapter 11. A Convergence Model
Abstract
Irrespective of the underlying model, most fractal compression methods, including most of those discussed in this book, use the following approach: A contractive map τ : F→F is sought on a complete metric space F of all possible images. The Contractive Mapping Fixed-Point Theorem then implies that |τ| = lim n →∞ τon exists and is unique. The transformation τ then serves as an encoding of the image | τ |. The difficulty lies in finding τ and, when the goal is image compression, specifying it compactly.
B. Bielefeld, Y. Fisher
Chapter 12. Least-Squares Block Coding by Fractal Functions
Abstract
The image coding scheme described in this chapter represents an attempt to achieve image compression using, as closely as possible, the “classical” theory of strictly self-similar fractals. Image compression is achieved by establishing a partition of an image into adjoining rectangular blocks, and coding each block individually by an iterated function system together with a type of fractal function. The method differs from other fractal compression techniques in that an image is regarded as an assembly of essentially independent blocks, so that any block will have the same code regardless of the rest of the image. In this respect the method is necessarily inferior to others when encoding an entire image, but the work is of interest since it provides a nearly optimal code for a single block, which may be obtained in linear time. Moreover, this work has the theoretical interest of being the only direct solution to an inverse problem in fractal geometry yet known.
F. Dudbridge
Chapter 13. Inference Algorithms for WFA and Image Compression
Abstract
In this chapter we will survey the encoding (inference) and decoding algorithms for weighted finite automata developed in [41] and [42], and their application to image-data compression.
K. Culik II, J. Kari
Appendix A. Sample Code
Abstract
This appendix contains the sample code that was used in to generate the results of Chapter 3. Before the actual code listing, we present a UNIX style manual page describing the use of the code, its peculiarities, and its shortcomings. The code itself consists of some 1500 lines of vanilla C. The C language has been both praised and derided: the good thing about C, goes the saying, is that it is so portable, but its main drawback is its lack of portability. This code has been compiled on several standard UNIX workstations, but no guarantee of any type is made about its compilability, freedom from bugs, or even its ability to compress images. After the code listings, we present a detailed line-by-line explanation of how the code works.
Y. Fisher
Appendix B. Exercises
Abstract
This appendix contains exercises that are meant to complement the main text in various places, and so the page on which an exercise is mentioned is listed at the end of each.
Y. Fisher
Appendix C. Projects
Abstract
This appendix contains “projects,” that is, potential further work, both theoretical and applied. The projects consist of various suggestions and algorithms of varying value and difficulty which may (or may not) extend the ideas presented in this book. Like the exercises, these end with the pages numbers from which they are referred (when there is a reference). If you, gentle and ambitious reader, actually work out any of these problems, I would be interested in seeing your results.
Y. Fisher
Appendix D. Comparison of Results
Abstract
In this appendix we briefly compare the results in this book with other results, such as wavelets, JPEG, and Iterated Systems, Inc. software. Some of these comparisons appear also in [29]. The results should be taken with a grain, or more aptly a large mountain, of salt for the reasons listed below.
Y. Fisher
Backmatter
Metadaten
Titel
Fractal Image Compression
herausgegeben von
Yuval Fisher
Copyright-Jahr
1995
Verlag
Springer New York
Electronic ISBN
978-1-4612-2472-3
Print ISBN
978-1-4612-7552-7
DOI
https://doi.org/10.1007/978-1-4612-2472-3