Image analysis – Image compression or coding – Transform coding
Patent
1994-08-26
1998-06-16
Boudreau, Leo
Image analysis
Image compression or coding
Transform coding
358433, G06K 936, G06K 946
Patent
active
057684375
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to methods of fractal coding of data, such as image data or data representative of speech, and to apparatus for carrying out such methods.
2. Description of the Art
It should be understood that the term "data" is used in this specification in a non-limiting sense and is intended to include not only data in the form of binary-coded electrical signals but also any other forms of data or information. Such other forms of data or information may take a physical form other than an electrical signal and may represent any required phenomenon, such as an image, speech, numbers or shape.
Conventionally, an image displayed on a computer screen is stored or transmitted in the form of digital data characterising the position and tone or colour of each pixel of the screen display. A substantial storage capacity is required for such data. If the image is to be displayed at a remote location, the data is transmitted utilizing a suitable carrier this requires a substantial bandwidth to accommodate the data unless a long time is allowed for transmission. In some situations, where the displayed image comprises a regular geometrical shape, the only data which needs to be stored is data characterising an equation defining the geometrical shape and its position in the display. In this case, much less storage capacity is required for the data. Clearly, the latter technique can be used for storage or transmission of an Image only when the image can be suitably characterised by a mathematical equation.
It is already known that more complex images can be coded by the so-called Adaptive Discrete Cosine Transform (ADCT) technique, and this technique is assured of adoption as the JPEG standard for still image compression (G. K. Wallace, "The JPEG Still Picture Compression Standard", Comm. ACM, Vol. 34, No. 4, pp 30-44, 1991).
However, there has also been continuing interest shown in the characterisation of complex images by fractal coding (M. F. Barnsley and S. Demko, "Iterated Function Systems and the Global Construction of Fractals", Proc. Roy. Soc. London, Vol. A399, pp 243-275, 1985).
A fractal is a structure having a high degree of self-similarity in that it is composed of a basic motif which is repeated throughout the structure and which may be considered as being formed by a series of transformations, which may include translation, rotation, reflection, size reduction or skewing, applied to the motif in order to generate successive parts of the structure. In fractal coding of an image, the image is coded by means of a fractal transform which breaks the image down into a series of domain blocks, each of which may be related to another part of the image by an affine map which may then be stored as an equation.
A. E. Jacquin, "A Novel Fractal Block-Coding Technique for Digital Images", Proc. IEEE ICASSP, pp 2225-2228, 1990, discloses a fractal coding technique which treats each image block as a "range block", and utilises a searching process, which is costly in terms of processing time and complexity, to find domain blocks having an affinity with the range blocks. However, this technique relies on good matches being found between the range blocks and the domain blocks, and significant degradation in image quality occurs if good matches are not found.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a novel fractal coding method and apparatus in which coding efficiency is high and substantial compression is obtained while retaining good fidelity. Aspects of the invention include coding an image or other data and storing, transmitting and decoding the data as well as methods, systems and apparatus therefor.
According to the present invention there is provided a method of fractal coding of data, which comprises dividing data into domains, determining a set of transformations relating the domains to the data in such a manner as to minimize the error between the data and an approximation to the data obtained by application of the transf
REFERENCES:
patent: 4837447 (1989-06-01), Pierce et al.
patent: 4941193 (1990-07-01), Barnsley et al.
patent: 5274466 (1993-12-01), Ida et al.
patent: 5321776 (1994-06-01), Shapiro
patent: 5347600 (1994-09-01), Barnsley et al.
Proc. IEEE ICASSP 1990, pp. 2225-2228, Jacquin, A.E. "A novel fractal block-coding technique for digital images" cited in the application p. 2.
Sixth International Conference on Digital Processing of Signals in Commnications, Sep. 1991, Loughborough,UK pp. 235-239, Kaouri, H.A. "Fractal coding of still images" see the whole document.
Proceedings of the Royal Society of London, vol. A399, 1985, London, UK, pp. 243-275, Barnsley, M.F. et al "Iterated function systems and the global construction of fractals" cited in the application pp. 2 & 19.
Monro et al. "Deterministic Rendering of Self-Affine Fractals" IEE Collog. (1990) No. 171: The Application of Fractal Techniques in Image . . . pp. 5/1-5/4.
Freeland et al., "IFS Fractals and the Wavelet Transform," ICASSP Conference, 1990, pp. 2345-2348.
Mazel et al., "Hidden-Variable Fractal Interpolation of Discrete Sequences," ICASSP Conference, Apr. 1991, pp. 3393-3396.
Dudbridge Frank
Monro Donald Martin
Boudreau Leo
Bri Tish Technology Group Ltd.
Mehta Bhavesh
LandOfFree
Fractal coding of data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fractal coding of data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fractal coding of data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1736129