Chain code

Last updated

A chain code is a lossless compression based image segmentation method for binary images based upon tracing image contours. The basic principle of chain coding, like other contour codings, is to separately encode each connected component, or "blob", in the image.

Contents

For each such region, a point on the boundary is selected and its coordinates are transmitted. The encoder then moves along the boundary of the region and, at each step, transmits a symbol representing the direction of this movement.

This continues until the encoder returns to the starting position, at which point the blob has been completely described, and encoding continues with the next blob in the image.

This encoding method is particularly effective for images consisting of a reasonably small number of large connected components.

Variations

Some popular chain codes include:

In particular, FCCE, VCC, 3OT and DFCCE can be transformed from one to another [12]

Abstract Cell Coordinate Oriented Crack Code Abstract Cell Coordinate Oriented Crack Code.png
Abstract Cell Coordinate Oriented Crack Code

A related blob encoding method is crack code. [13] Algorithms exist to convert between chain code, crack code, and run-length encoding.

A new trend of chain codes involve the utilization of biological behaviors. This started by the work of Mouring et al. [6] who developed an algorithm that takes advantage of the pheromone of ants to track image information. An ant releases a pheromone when they find a piece of food. Other ants use the pheromone to track the food. In their algorithm, an image is transferred into a virtual environment that consists of food and paths according to the distribution of the pixels in the original image. Then, ants are distributed and their job is to move around while releasing pheromone when they encounter food items. This helps other ants identify information, and therefore, encode information.

In use

Recently, the combination of move-to-front transform and adaptive run-length encoding accomplished efficient compression of the popular chain codes. [14] Chain codes also can be used to obtain high levels of compression for image documents, outperforming standards such as DjVu and JBIG2. [11] [10] [9] [8] [7] [6] [15]

See also

Related Research Articles

In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information. Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.

<span class="mw-page-title-main">Lossy compression</span> Data compression approach that reduces data size while discarding or changing some of it

In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size for storing, handling, and transmitting content. The different versions of the photo of the cat on this page show how higher degrees of approximation create coarser images as more details are removed. This is opposed to lossless data compression which does not degrade the data. The amount of data reduction possible using lossy compression is much higher than using lossless techniques.

Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates.

The Burrows–Wheeler transform rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding. More importantly, the transformation is reversible, without needing to store any additional data except the position of the first original character. The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation. The Burrows–Wheeler transform is an algorithm used to prepare data for use with data compression techniques such as bzip2. It was invented by Michael Burrows and David Wheeler in 1994 while Burrows was working at DEC Systems Research Center in Palo Alto, California. It is based on a previously unpublished transformation discovered by Wheeler in 1983. The algorithm can be implemented efficiently using a suffix array thus reaching linear time complexity.

<span class="mw-page-title-main">Image compression</span> Reduction of image size to save storage and transmission costs

Image compression is a type of data compression applied to digital images, to reduce their cost for storage or transmission. Algorithms may take advantage of visual perception and the statistical properties of image data to provide superior results compared with generic data compression methods which are used for other digital data.

Transform coding is a type of data compression for "natural" data like audio signals or photographic images. The transformation is typically lossless on its own but is used to enable better quantization, which then results in a lower quality copy of the original input.

<span class="mw-page-title-main">Fractal compression</span> Compression method for digital images

Fractal compression is a lossy compression method for digital images, based on fractals. The method is best suited for textures and natural images, relying on the fact that parts of an image often resemble other parts of the same image. Fractal algorithms convert these parts into mathematical data called "fractal codes" which are used to recreate the encoded image.

<span class="mw-page-title-main">JPEG 2000</span> Image compression standard and coding system

JPEG 2000 (JP2) is an image compression standard and coding system. It was developed from 1997 to 2000 by a Joint Photographic Experts Group committee chaired by Touradj Ebrahimi, with the intention of superseding their original JPEG standard, which is based on a discrete cosine transform (DCT), with a newly designed, wavelet-based method. The standardized filename extension is .jp2 for ISO/IEC 15444-1 conforming files and .jpx for the extended part-2 specifications, published as ISO/IEC 15444-2. The registered MIME types are defined in RFC 3745. For ISO/IEC 15444-1 it is image/jp2.

<span class="mw-page-title-main">Swarm behaviour</span> Collective behaviour of a large number of (usually) self-propelled entities of similar size

Swarm behaviour, or swarming, is a collective behaviour exhibited by entities, particularly animals, of similar size which aggregate together, perhaps milling about the same spot or perhaps moving en masse or migrating in some direction. It is a highly interdisciplinary topic.

Prediction by partial matching (PPM) is an adaptive statistical data compression technique based on context modeling and prediction. PPM models use a set of previous symbols in the uncompressed symbol stream to predict the next symbol in the stream. PPM algorithms can also be used to cluster data into predicted groupings in cluster analysis.

<span class="mw-page-title-main">Ant colony optimization algorithms</span> Optimization algorithm

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

Grammar-based codes or Grammar-based compression are compression algorithms based on the idea of constructing a context-free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms. To compress a data sequence , a grammar-based code transforms into a context-free grammar . The problem of finding a smallest grammar for an input sequence is known to be NP-hard, so many grammar-transform algorithms are proposed from theoretical and practical viewpoints. Generally, the produced grammar is further compressed by statistical encoders like arithmetic coding.

Lossless JPEG is a 1993 addition to JPEG standard by the Joint Photographic Experts Group to enable lossless compression. However, the term may also be used to refer to all lossless compression schemes developed by the group, including JPEG 2000 and JPEG-LS.

Context-adaptive binary arithmetic coding (CABAC) is a form of entropy encoding used in the H.264/MPEG-4 AVC and High Efficiency Video Coding (HEVC) standards. It is a lossless compression technique, although the video coding standards in which it is used are typically for lossy compression applications. CABAC is notable for providing much better compression than most other entropy encoding algorithms used in video encoding, and it is one of the key elements that provides the H.264/AVC encoding scheme with better compression capability than its predecessors.

A video coding format is a content representation format for storage or transmission of digital video content. It typically uses a standardized video compression algorithm, most commonly based on discrete cosine transform (DCT) coding and motion compensation. A specific software, firmware, or hardware implementation capable of compression or decompression to/from a specific video coding format is called a video codec.

<span class="mw-page-title-main">Nasir Ahmed (engineer)</span> Indian-American electrical engineer and computer scientist

Nasir Ahmed is an Indian-American electrical engineer and computer scientist. He is Professor Emeritus of Electrical and Computer Engineering at University of New Mexico (UNM). He is best known for inventing the discrete cosine transform (DCT) in the early 1970s. The DCT is the most widely used data compression transformation, the basis for most digital media standards and commonly used in digital signal processing. He also described the discrete sine transform (DST), which is related to the DCT.

<span class="mw-page-title-main">Audio coding format</span> Digitally coded format for audio signals

An audio coding format is a content representation format for storage or transmission of digital audio. Examples of audio coding formats include MP3, AAC, Vorbis, FLAC, and Opus. A specific software or hardware implementation capable of audio compression and decompression to/from a specific audio coding format is called an audio codec; an example of an audio codec is LAME, which is one of several different codecs which implements encoding and decoding audio in the MP3 audio coding format in software.

Display Stream Compression (DSC) is a VESA-developed video compression algorithm designed to enable increased display resolutions and frame rates over existing physical interfaces, and make devices smaller and lighter, with longer battery life. It is a low-latency algorithm based on delta PCM coding and YCGCO-R color space.

JPEG XT is an image compression standard which specifies backward-compatible extensions of the base JPEG standard.

JPEG XS is an interoperable, visually lossless, low-latency and lightweight image and video coding system used in professional applications. Applications of the standard include streaming high quality content for virtual reality, drones, autonomous vehicles using cameras, gaming, and broadcasting. In this respect, JPEG XS is unique, being the first ISO codec ever designed for this specific purpose. JPEG XS, built on core technology from both intoPIX and Fraunhofer IIS, is formally standardized as ISO/IEC 21122 by the Joint Photographic Experts Group with the first edition published in 2019. Although not official, the XS acronym was chosen to highlight the eXtra Small and eXtra Speed characteristics of the codec. Today, the JPEG committee is still actively working on further improvements to XS, with the second edition scheduled for publication and initial efforts being launched towards a third edition.

References

  1. ↑ Freeman, Herbert (June 1961). "On the Encoding of Arbitrary Geometric Configurations". IRE Transactions on Electronic Computers . EC-10 (2): 260–268. doi:10.1109/TEC.1961.5219197.
  2. ↑ Liu, Yong Kui; Žalik, Borut (April 2005). "An efficient chain code with Huffman coding". Pattern Recognition . 38 (4): 553–557. Bibcode:2005PatRe..38..553K. doi:10.1016/j.patcog.2004.08.017.
  3. ↑ Bribiesca, Ernesto (February 1999). "A new chain code". Pattern Recognition . 32 (2): 235–251. Bibcode:1999PatRe..32..235B. doi:10.1016/S0031-3203(98)00132-0.
  4. ↑ Sanchez-Cruz, Hermilo; Rodríguez-Dagnino, Ramón M. (September 2005). "Compressing bilevel images by means of a three-bit chain code". Optical Engineering . 44 (9). 097004. Bibcode:2005OptEn..44i7004S. doi:10.1117/1.2052793.
  5. ↑ Žalik, Borut; Mongus, Domen; Liu, Yong-Kui; Lukač, Niko (July 2016). "Unsigned Manhattan chain code". Journal of Visual Communication and Image Representation . 38: 186–194. doi:10.1016/j.jvcir.2016.03.001.
  6. 1 2 3 Mouring, Matthew; Dhou, Khaldoon; Hadzikadic, Mirsad (2018). "A Novel Algorithm for Bi-Level Image Coding and Lossless Compression based on Virtual Ant Colonies". Proceedings of the 3rd International Conference on Complexity, Future Information Systems and Risk. COMPLEXIS 2018. Vol. 1. pp. 72–78. doi:10.5220/0006688400720078 . Retrieved 2022-07-06.
  7. 1 2 Dhou, Khaldoon (January 2020). "A new chain coding mechanism for compression stimulated by a virtual environment of a predator–prey ecosystem". Future Generation Computer Systems . 102: 650–669. doi:10.1016/j.future.2019.08.021. S2CID   202783274.
  8. 1 2 Dhou, Khaldoon (2018). A Novel Agent-Based Modeling Approach for Image Coding and Lossless Compression Based on the Wolf-Sheep Predation Model. ICCS 2018. Computational Science – ICCS 2018. LNCS. Vol. 10861. pp. 117–128. doi:10.1007/978-3-319-93701-4_9.
  9. 1 2 Dhou, Khaldoon; Cruzen, Christopher (May 2021). "A highly efficient chain code for compression using an agent-based modeling simulation of territories in biological beavers". Future Generation Computer Systems . 118: 1–13. doi:10.1016/j.future.2020.12.016. S2CID   232023010.
  10. 1 2 Dhou, Khaldoon; Cruzen, Christopher (December 2019). "An Innovative Chain Coding Technique for Compression Based on the Concept of Biological Reproduction: An Agent-Based Modeling Approach". IEEE Internet of Things Journal . 6 (6): 9308–9315. doi:10.1109/JIOT.2019.2912984. S2CID   150025529.
  11. 1 2 Dhou, Khaldoon (June 2019). "An innovative design of a hybrid chain coding algorithm for bi-level image compression using an agent-based modeling approach". Applied Soft Computing. 79: 94–110. doi:10.1016/j.asoc.2019.03.024. S2CID   126831246.
  12. ↑ Sanchez-Cruz, Hermilo; Lopez-Valdez, Hiram H. (January 2014). "Equivalence of chain codes". Journal of Electronic Imaging . 23 (1). 013031. Bibcode:2014JEI....23a3031S. doi:10.1117/1.JEI.23.1.013031. S2CID   41897871.
  13. ↑ Rosenfeld, Azriel; Kak, Avinash C. (1982). "Chapter 11 - Representation". Digital Picture Processing. Vol. 2 (2nd ed.). Academic Press. p. 220. Bibcode:1982dpp..book.....R. doi:10.1016/B978-0-12-597302-1.50010-4. ISBN   0-12-597302-0. ISBN   0-12-597301-2 , 0-12-597302-0
  14. ↑ Žalik, Borut; Lukač, Niko (January 2014). "Chain code lossless compression using move-to-front transform and adaptive run-length encoding". Signal Processing: Image Communication. 29 (1): 96–106. doi:10.1016/j.image.2013.09.002.
  15. ↑ Rodríguez-Díaz, Mario A.; Sánchez-Cruz, Hermilo (July 2014). "Refined fixed double pass binary object classification for document image compression". Digital Signal Processing . 30: 114–130. doi:10.1016/j.dsp.2014.03.007.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.