Computer Science
Run Length Encoding
Run Length Encoding (RLE) is a simple form of data compression that represents consecutive identical data values as a single value and a count. It is commonly used to compress images, audio, and other types of data. RLE is efficient for data with long runs of the same value, but less effective for data with frequent value changes.
Written by Perlego with AI-assistance
Related key terms
1 of 5
7 Key excerpts on "Run Length Encoding"
eBook - PDFComputer Networks ISE
A Systems Approach
- Larry L. Peterson, Bruce S. Davie(Authors)
- 2007(Publication Date)
- Morgan Kaufmann(Publisher)
Of course, when talking about lossy compression algorithms, processing resources are not the only factor. Depending on the exact application, users are willing to make very different trade-offs between bandwidth (or delay) and extent of information loss due to compression. For example, a radiologist reading a mammogram is unlikely to tolerate 7.2 Data Compression 559 any significant loss of image quality and might well tolerate a delay of several hours in retrieving an image over a network. By contrast, it has become quite clear that many people will tolerate questionable audio quality in exchange for free global telephone calls (not to mention the ability to talk on the phone while driving). 7.2.1 Lossless Compression Algorithms We begin by introducing three lossless compression algorithms. We do not describe these algorithms in much detail—we just give the essential idea—since it is the lossy algorithms used to compress image and video data that are of the greatest utility in today’s network environment. We do comment, though, on how well these lossless algorithms work on digital imagery. Some of the ideas exploited by these lossless techniques show up again in later sections when we consider the lossy algorithms that are used to compress images. Run Length Encoding Run Length Encoding (RLE) is a compression technique with a brute-force simplicity. The idea is to replace consecutive occurrences of a given symbol with only one copy of the symbol, plus a count of how many times that symbol occurs—hence the name “run length.” For example, the string AAABBCDDDD would be encoded as 3A2B1C4D. RLE can be used to compress digital imagery by comparing adjacent pixel values and then encoding only the changes. For images that have large homogeneous regions, this technique is quite effective. For example, it is not uncommon that RLE can achieve compression ratios on the order of 8-to-1 for scanned text images.
eBook - PDF- Gerald Friedland, Ramesh Jain(Authors)
- 2014(Publication Date)
- Cambridge University Press(Publisher)
In addition to introducing the concept of compression, this exam-ple demonstrates a practical method that computer scientists often use to compress data with large areas of the same values. Suppose we have a black-and-white image. The black pixels are encoded with 1 and the white pixels are encoded with 0. It looks like this: 0000000000000000 0000011111100000 125 Information Content and Entropy 0000100000110000 0000100011010000 0000100110010000 0000111000010000 0000011111100000 0000000000000000 As is, the bitmap representation would take 16 x 8 = 128 zeros and ones. Let’s assume we want to cut the number of zeros and ones. Observe that many zeros and ones appear in a row. We could represent these charac-ters only by the number of consecutive zeros and ones starting with the zeros. The result would be: 21 6 9 1 5 2 8 1 3 2 1 1 8 1 2 2 2 1 8 6 21 The highest number represented is twenty-one. So we could represent each of the numbers in the row with five bits: 101010011001001 and so on. We need twenty-one numbers in this encoding, so we can represent the digit in one hundred five bits, sav-ing twenty-three bits. Of course, we would have to represent a bitmap containing more than two colors – say, sixteen – slightly differently. Consider the following one-line example: RRRRRGGGBBBBBRRRRGB Using a variant of the concept of representation, we would get: 5R3G5B4R1G1B This method – called run-length encoding , or RLE – is used in many image formats, such as Windows BMP and TIFF, and, in a slightly modified version, on CD-ROMs because it is especially effective in representing data with large areas of the same values. Several unan-swered questions remain, however. For example: Is RLE the best way to compress the example cited earlier? • Would applying RLE to the file again further compress the bitmap? • What is the minimum amount of space needed to represent this image? • Answering these questions requires a more in-depth discussion of the topic.
eBook - PDF- Kenny A. Hunt(Author)
- 2016(Publication Date)
- A K Peters/CRC Press(Publisher)
The JPEG technique achieved a compression ratio of 99 . 4% while the PNG approach delivered a 33 . 1% com-pression ratio. It should be noted that JPEG can be controlled so as to provide much higher quality results but with a corresponding loss of compression. 10.2 Run Length Coding Run Length Encoding is a lossless encoding scheme in which a sequence of same-colored pixels is stored as a single value rather than recording each pixel individ-ually. Consider, for example, a binary image in which each pixel is represented by a single bit that is either 0 (black) or 1 (white). One row of the image may contain the 32-pixel sequence 11111111110001111111111111111111 This row contains three runs: 10 white pixels followed by 3 black followed by 19 white. This information can be completely encoded by the three byte sequence { 10, 3, 19 } by assuming that the data begins with white runs. The original representation consumes 32 bits of memory while the run length-encoded repre-sentation consumes 24 bits of memory if we assume that 8-bit bytes are used for each run. This results in a compression ratio of 4:3 and a savings ratio of S r = ( N 1 -N 2 ) N 1 = (32 -24) 32 = 8 32 = 25% . Figure 10.3 illustrates how Run Length Encoding can represent binary image data. In the illustration, one row of an image of the character R is encoded. The row contains a total of 88 bits (11 bytes) and five runs. This information is losslessly encoded with the 5-byte sequence { 20, 7, 22, 18, 21 } , which consumes 260 10. Image Compression R 20 7 22 18 21 Figure 10.3. Run Length Encoding. a total of 40 bits and results in a compression ratio of 11:5 and a savings ratio of S r ’ 54% . Listing 10.1 gives an algorithm for Run Length Encoding binary images where the encoder assumes that the first run encoded on each row is composed of white pixels.
- Roberto Togneri, Christopher J.S deSilva(Authors)
- 2003(Publication Date)
- Chapman and Hall/CRC(Publisher)
This is an example of lossless compression , where no information is lost in the coding and decoding. When images are compressed, it may be permissible for the decompressed image not to have exactly the same pixel values as the original image, provided the difference is not perceptible to the eye. In this case, some form of lossy compression may be acceptable. This involves a loss of information between the coding and decoding processes. 4.3 Run-length Coding Run-length coding is a simple and effective means of compressing data in which it is frequently the case that the same character occurs many times in succession. This may be true of some types of image data, but it is not generally true for text, where it is rare for a letter of the alphabet to occur more than twice in succession. To compress a sequence, one simply replaces a repeated character with one instance of the character followed by a count of the number of times it occurs. For example, the sequence could be replaced by 174 Fundamentals of Information Theory and Coding Design reducing the number of characters from 24 to 16. To decompress the sequence, each combination of a character and a count is replaced by the appropriate number of characters. Protocols need to be established to distinguish between the characters and the counts in the compressed data. While the basic idea of run-length coding is very simple, complex protocols can be developed for particular purposes. The standard for fac-simile transmission developed by the International Telephone and Telegraph Con-sultative Committee (CCITT) (now the International Telecommunications Union) [4] involves such protocols. 4.4 The CCITT Standard for Facsimile Transmission Facsimile machines have revolutionised the way in which people do business. Send-ing faxes now accounts for a major part of the traffic on telephone lines.
- Alasdair McAndrew(Author)
- 2015(Publication Date)
- Chapman and Hall/CRC(Publisher)
7 which is a significant improvement over 3 bits per pixel, and very close to the theoretical minimum of 2.6508 given by the entropy. Huffman codes are uniquely decodable , in that a string can be decoded in only one way. For example, consider the string 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 to be decoded with the Huffman code generated above. There is no code word 1, or 11, so we may take the first three bits 110 as being the code for gray value 3. Notice also that no other code word begins with this string. For the next few bits, 1110 is a code word; no other begins with this string, and no other smaller string is a codeword. So we can decode this string as gray level 4. Continuing in this way we obtain: 1 1 0 | {z } 3 1 1 1 0 | {z } 4 0 0 | {z } 0 0 0 | {z } 0 1 0 | {z } 1 0 1 | {z } 2 1 1 1 1 0 | {z } 5 406 A Computational Introduction to Digital Image Processing, Second Edition as the decoding for this string. For more information about Huffman coding, and its limitations and generalizations, see [13, 37]. 14.3 Run Length Encoding Run Length Encoding (RLE) is based on a simple idea: to encode strings of zeros and ones by the number of repetitions in each string. RLE has become a standard in facsimile transmission. For a binary image, there are many different implementations of RLE; one method is to encode each line separately, starting with the number of 0’s. So the following binary image: 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 would be encoded as (123)(231)(0321)(141)(33)(0132) Another method [49] is to encode each row as a list of pairs of numbers; the first number in each pair given the starting position of a run of 1’s, and the second number its length. So the above binary image would have the encoding (22)(33)(1361)(24)(43)(1152) Grayscale images can be encoded by breaking them up into their bit planes ; these were discussed in Chapter 3.
eBook - PDF- Sudhakar Radhakrishnan, Muhammad Sarfraz, Sudhakar Radhakrishnan, Muhammad Sarfraz(Authors)
- 2020(Publication Date)
- IntechOpen(Publisher)
The RLE is used Figure 2. Basic digital classification image file format. 195 The DICOM Image Compression and Patient Data Integration using Run Length and Huffman … DOI: http://dx.doi.org/10.5772/intechopen.89143 for medical image compression in hybrid approach, where gray scale value gives certain interesting fact about the distribution in image. The background pixels of all the medical image are low values, and they differ by +3 or À 3. The RLE is based on dynamic array implementation, no need to process whole image [8]. The paper served that the number of repeated zero count which is represented as “ RUN ” and Sr. no. File format Extension Bit depth Compression type Compression performance Name of supported free image viewer Gray Color 1 BMP bmp 1,4,8 1,4,8,24 Lossless Very low IrfanView, XnView, Osiris, ImageJ 2 DICOM dcm 8, 16 8, 24, 48 Lossless Low IrfanView, XnView, Osiris, ImageJ 3 GIF gif 1, 4, 8 1, 4, 8 Lossless Medium IrfanView, XnView, Osiris, ImageJ 4 JPEG jpg 8 24 Lossy Average IrfanView, XnView, Osiris, ImageJ 5 JPEG 2000 Jp2 8, 16 24, 48 Lossless High IrfanView, XnView 6 PNG png 1, 4, 8, 16 1, 4, 8, 24, 48 Lossless High IrfanView, XnView 7 TIFF tiff 8, 16 8, 24, 48 Lossless or lossy Very high IrfanView, XnView Table 1. Summary of raster (bitmap) image file format. Sr. no.
eBook - PDF- L.N. Kanal, E.S. Gelsema(Authors)
- 2012(Publication Date)
- North Holland(Publisher)
It must be as large as the largest number of data that can be expected in a given application. A hardware Run Length Encoding diagram for binary images, which has been realized at our laboratory, can be found in [ 9] . We note that, according to the previous definition of run length en-coding, the encoded data do not contain explicit information about the object number they belong to. Object oriented Run Length Encoding is more complex and requires an additional pass to link or rearrange the different runs belonging to one and the same object. 2. Calculation of projections Projections are one-dimensional arrays in which the i-th element corresponds to a particular feature of the i-th row (or column) in the image. Possible features are the coordinate of the first object pixel along each line, the coordinate of the last object pixel, the number of object pixels, the sum of gray level values and the number of background-to-object transitions. An early hardware processor for the calculation of profiles has been described in [ 10] . It has been built for the automatic inspection of 354 P. Suetens and A. Oosterlinck reed switches and is still in use. More than 35 features are detected and controlled for each switch within 1 second. Recently, a new prototype has been built at our laboratory. The sys-tem has a modular configuration and consists of: - an 8 bit ADC card to convert the camera signal into digital format. - 1 or more preprocessors directly connected to the VME bus (double Eurocard format). Each preprocessor transforms the camera image in-to a binary image by means of a programmable threshold (video look-up table) and extracts a number of features from the image (projec-tions) in real time. These projections are stored in RAM on the preprocessor card. - MC 68000 based microcomputer. - Pascal written system and utility software. - 3 RS-232 interfaces and 8 parallel input and 8 parallel output lines, high voltage or TTL compatible.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
