Ernie Deel is an independent computer programmer and consultant with a background in engineering, CAD, and computer applications in a technical environment. He can be reached via CompuServe at 72627,3026.
Introduction
Mother said there would be days like this. We were traveling south in our sailboat on the Neuse River in North Carolina. It started to rain, then it poured. The temperature was in the upper 30s, and a 25-knot wind screamed its warning of worse to come. We were a teensy bit lost and needed to find a particular buoy with numbers that, at a distance, appear about as large as the letters in this sentence. As darkness approached, the waterproof seals on the binoculars decided to give up their struggle against rain and salt water, fogging the lenses and causing us to wonder what on earth had made us leave our house and warm fireplace to head south for the winter using this particular mode of travel. I half jokingly attempted to beam us up to the Enterprise, but alas, Scotty wasn't listening.
We may not have a transporter on board, but fortunately, we own a global positioning system (GPS) that can pinpoint our location to within 10 meters (100 meters when the signal is scrambled by the military to foil its use by our enemies, which of course also foils its use by us). Thanks to the GPS, we were never actually lost, but we still needed to sight that buoy to avoid a dangerous shoal--going aground 100 meters off course is little better than hitting land two miles out of the way. Isn't that always the case? Technology enhances, but never replaces, the simple tools that led to the technology in the first place. Despite our GPS, finding that buoy would mean the difference between arriving in port and spending the night outside in the rain--not an attractive prospect. As you can imagine, searching for tiny, unlit, red-and-green markers (some are only about three feet tall) in a driving rainstorm with fogged binoculars tests the limits of the brain's pattern-recognition capabilities.
Eventually, we found our marker and rounded the jetty into the harbor of a town with the unusual name of Oriental. I "fixed" the binoculars by disassembling them, managing in the process to crack one lens and partially defog the other. At least now we had a monocular we could use to continue to the next town, where we would purchase a new pair.
Speaking of pattern recognition, I received the following article from Ernie F. Deel on a data-compression technique that uses pattern-recognition analysis to achieve fast results and efficient compression ratios. I wish someone would build pattern-recognition algorithms into navigational instruments. Maybe then, during the next storm, I could retire below, have a cup of tea, and let the boat find the darn buoys.
Generic block coding is a data-encoding technique for subdividing a data stream into multiple smaller blocks, which are then analyzed and encoded independently. The technique is adaptable to many purposes, but is ideally suited for compressing graphical images. Two of the most powerful image-compression schemes currently available--JPEG and fractal compression--both use block coding along with sophisticated data analysis and modeling.
The algorithm presented here demonstrates basic block-coding techniques along with some relatively simple data analysis and modeling. The code uses the method to create tools for image compression and decompression. Images compressed with this algorithm are comparable in size to images stored in the popular GIF format.
Adaptive block coding (ABC) analyzes individual data blocks to identify predefined data patterns. Compression is achieved if a block contains a pattern that can be identified and encoded in fewer bytes than the original data. By using the most efficient, best-fit data pattern to encode each block, the algorithm adapts to changing conditions within the data stream, maximizing the compression level. Block size, number, and type of data patterns, as well as the encoding methods, can all be modified to experiment with new patterns or to better adapt the algorithm to a specific type of data.
For work with graphical images, a data block is a set of pixel-color values from a small 2-D section of the image. As I will show later, however, block-encoding techniques are not limited to graphical 2-D images. 1-D block coding can be used to further compress the 2-D output.
I originally developed ABC encoding for an application where partial-screen, photo-type images were to be captured from video-camera displays and incorporated into a database. The images were to be mixed with text from the database. Color was not essential; therefore, I used VGA mode 12h (640x480 resolution) with 16 gray-scale shades. Contrary to conventional wisdom, this mode can display good-quality gray-scale photographs. The mode's high resolution also allows excellent-quality text to be included with the image. The basic algorithm presented here is limited to use with either color or gray-scale images in mode 12h, but it can be adapted to work with other modes.
For the initial compression phase, the algorithm divides the image data into 2-D, 8x8 pixel blocks. For each input block, three data items are generated:
by Tom Swan
The Algorithm
2-D Coding
Separate arrays hold these three items, which can be stored in a disk file. Adding a file header and the image color palette completes the ABC disk-file structure; see Figure 1. To facilitate image decompression and reconstruction, the file header also contains the size in pixels of the original image and the size in bytes of each of the five sections of the disk file.
Six predefined 2-D block-data patterns are used. In addition, a block code of 0 is used for blocks lacking a defined pattern that can be efficiently encoded. Based upon my experience with actual images, a very small percentage of blocks fall into that category. Other data patterns are easily added to those listed here. Example 1(a) shows a text representation of the horizontal block-code pattern.
The numbers in the example indicate the row-oriented sequence in which the pixel block is analyzed for the existence of uniformly colored pixel groups. The program builds a binary pattern descriptor by assigning the preceding pixel a code of zero for each pixel having the same color value. Unequal pixels are coded as 1. A complete pattern descriptor for an 8x8 pixel block therefore takes eight bytes.
For each pixel encoded as 1, the program writes to the array a coefficient corresponding to the color of the pixel. To reconstruct the original block, color coefficients are either read from the array or duplicated as dictated by the pattern descriptor. Essentially, this is a binary-coded form of run-length encoding. In photo-type images, very short runs of uniformly colored pixels are common and can be efficiently encoded. The block patterns in Examples 1(b) through 1(d) show variations on this theme using different analysis and encoding sequences.
Example 1(b) is the same as Example 1(a), but it examines the data stream using a vertical, column-oriented analysis. Example 1(c), on the other hand, analyzes the input data in a zigzag pattern.
The zigzag-block code efficiently encodes blocks dithered with pixels of alternating colors. "Dithering" is a technique used in graphics software to create apparent colors. For example, a simple dithering scheme might alternate red and yellow pixels to create the appearance of orange. Dithering is also heavily used by analog-to-digital converters such as scanners and video-capture cards. Signal fluctuations, round-off errors, and other phenomena within the hardware and software can also produce a dithering effect.
The block code in Example 1(d) is similar to that in Example 1(c), but the zigzag path begins at the upper right. Sometimes, simply analyzing the data in the other direction can produce more efficient compression.
The numbers in the block code of Example 1(e) represent actual hexadecimal color values. At first glance, there doesn't appear to be a consistent pattern, but by counting like-colored pixels, you find that 26 out of 64 pixels have the color value 0A, called prime color. The pattern can be encoded using a simple binary code. For example, following a horizontal row-oriented path similar to Example 1(a), every prime-colored pixel is encoded as 0. Nonprime colored pixels are encoded as 1. Only the prime-color coefficient and the color values for nonprime pixels are written to the output.
As in the preceding pattern, Example 1(f) represents actual pixel-color values. Again, no pattern is obviously consistent. Upon close inspection, though, all the pixels evidently have one of four color values: 03, 05, 07, or 09. Since only four different colors are present, the colors in this block can be encoded using only two bits instead of the usual four required to encode the full set of 16 colors. Each of the four colors is assigned a 2-bit code. The pattern descriptor then becomes a simple listing of 2-bit codes that describe color values of pixels in a row-oriented fashion. The four-color coefficients are output in the same sequence as the 2-bit codes, cutting the size of the block almost in half.
Additional block codes reflect actual numbers of colors found within the image block. Table 1 lists the bits per pixel used to encode the colors within the pattern descriptor. Block codes 14 and 15 are not used.
For each pixel block, the program calculates the final encoded block size for each of the six basic patterns. Encoded block size is measured in terms of the equivalent number of noncompressed pixels. This provides a consistent method of comparing different patterns, including the nonencoded pattern, 0. The most efficient, best-fit pattern is obviously the one that provides the smallest encoded-block size. Thanks to the simplicity of the data patterns, compression is relatively fast even with this simple, brute-force analysis.
After the 2-D compression phase, the data has lost any possible geometric interpretation. It can now only be viewed as a one-dimensional sequence of bytes. For reasons that are not clear to me, a significant number of short runs of bytes typically occurs in each of the three output arrays. To take advantage of this redundancy, I created a one-dimensional block-encoding algorithm that accepts as input one of the 2-D data arrays. If any additional compression is possible, the input array is returned in compressed format; otherwise, the array is returned unchanged.
The 1-D block-encoding algorithm closely parallels the 2-D block-encoding algorithm. The input data stream is first subdivided into 1-D blocks of 16 bytes each. Each block is then analyzed for the presence of a simple pattern. As in the 2-D case, the following three items are written to the output for each block:
Again, a binary pattern descriptor is used. Similar to several of the 2-D patterns, a byte that repeats the preceding byte is coded as 0; unequal bytes are coded as 1. Only the nonrepeating bytes are stored. The original block is reconstructed by either reading bytes from a byte-coefficient array or duplicating the previous byte as dictated by the pattern descriptor. Figure 2 shows an example of a data block encoded according to the 1-D algorithm. As with the 2-D prime-color pattern, the idea here is to encode the most common (prime) character/byte found within the block (0A, in this case).
Following compression, the data array is composed of three different sections, closely paralleling the segmentation of the 2-D output. To facilitate decompression, the first two bytes in the array indicate the total number of 1-D blocks. A decompression program can use that information to determine whether or not a section has been compressed by 1-D coding.
Figure 3 illustrates the output array after 1-D compression. The first two bytes in each section of the array indicate the total length of the section. Based upon my experience with actual images, the 1-D compression phase typically improves the overall compression ratio by about 10 percent or more.
The included ABC source code demonstrates both the use and development of reusable software components with Microsoft's MS-DOS Basic. The source code will also run with minimal changes under Visual Basic for Windows. I used components from Crescent Software's Graphics Workshop to build the ABC compression and decompression modules.
The program COMP.BAS is the ABC compression-subroutine module, while DECOMP.BAS contains the ABC decompression subroutine; both programs are available electronically; see "Availability," page 3. PCX2ABC.BAS in Listing One (page 148) demonstrates how to use the compression module. The program displays a PCX image, simulating video-camera output. The image is captured from the screen, compressed, and stored in a disk file. Listing Two (SHOWABC.BAS, page 148) demonstrates ABC decompression. The program simply redisplays compressed files produced by PCX2ABC.
The modules take advantage of Basic's built-in memory management to allocate dynamic storage arrays. As implemented, the sample programs' arrays are limited to 64K; therefore, it may not be possible to compress some larger images with the programs listed here. Basic fully supports the use of huge arrays (>64K), but I didn't need that capability for my application. If available storage is exceeded, the compression module returns a negative number for compressed image size.
Listings Three (COMP.DCL, page 149) and Four (DECOMP.DCL, page 149) contain function prototype declarations for COMP.BAS and DECOMP.BAS. These files must be included in programs that use the compression and decompression modules.
(c) zigzag-left block code; (d) zigzag-right block code; (e) prime-color block code; (f) variable-length block code.
(a) 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 (b) 01 09 17 25 33 41 49 57 02 10 18 26 34 42 50 58 03 11 19 27 35 43 51 59 04 12 20 28 36 44 52 60 05 13 21 29 37 45 53 61 06 14 22 30 38 46 54 62 07 15 23 31 39 47 55 63 08 16 24 32 40 48 56 64 (c) 01 02 06 07 15 16 28 29 03 05 08 14 17 27 30 43 04 09 13 18 26 31 42 44 10 12 19 25 32 41 45 54 11 20 24 33 40 46 53 55 21 23 34 39 47 52 56 61 22 35 38 48 51 57 60 62 36 37 49 50 58 59 63 64 (d) 29 28 16 15 07 06 02 01 43 30 27 17 14 08 05 03 44 42 31 26 18 13 09 04 54 45 41 32 25 19 12 10 55 53 46 40 33 24 20 11 61 56 52 47 39 34 23 21 62 60 57 51 48 38 35 22 64 63 59 58 50 49 37 36 (e) 05 0A 09 0A 05 07 0A 09 0A 05 0A 07 0A 03 07 0A 03 0A 03 0A 09 05 0A 07 0A 03 09 0A 03 0A 07 09 07 05 0A 03 09 0A 05 0A 0A 09 07 05 0A 03 0A 05 05 0A 0A 05 0A 07 03 09 0A 03 07 0A 07 0A 09 0A (f) 05 07 09 03 05 07 03 09 09 05 03 07 07 03 07 05 03 09 03 05 09 05 09 07 05 03 09 07 03 05 07 09 07 05 03 03 09 07 05 03 03 09 07 05 03 05 03 05 05 05 03 05 09 07 03 09 09 03 07 03 07 05 09 07
Code Colors Bits/Pixel
6 1 0
7 2 1
8 3 2
9 4 2
10 5 3
11 6 3
12 7 3
13 8 3
'*** BASIC Adaptive Block Coded (ABC) Image Compression
'*** (c)1993, E.F.Deel, CIS 72627,3026
'*** PCX2ABC.BAS - Compression Demo Module, displays PCX to simulate video
'*** camera output, captures image from screen, compresses & stores.
'*** Link with compression module, COMP.BAS
'*** NOTE: VGA is required and assumed
DEFINT A-Z
'--- Include declarations for compression module
'$INCLUDE: 'COMP.DCL'
'--- BASIC DOS/BIOS Interrupt routine
DECLARE SUB InterruptX (IntNumber, Registers AS ANY)
'--- External assembler components from Graphics WorkShop by
' Crescent Software, used to display PCX and work with palette
DECLARE SUB SetPaletteEGA (BYVAL PalReg%, BYVAL Value%)
DECLARE SUB SetPalTripleVGA (BYVAL PalReg%, BYVAL Red%, BYVAL Green%,
BYVAL Blue%)
DECLARE SUB DispPCXVE (BYVAL Display%)
DECLARE FUNCTION OpenPCXFile% (Filename$, Header$)
'--- BASIC sub-program to handle palette and display PCX
DECLARE SUB ShowPCX (Filein$, XSize, YSize)
'--- Share compression statistics among modules (optional)
COMMON noc, hrc, vrc, pcc, zlc, zrc, vlc, bct&, pct&, plt&, GPDat%()
TYPE RegType
AX AS INTEGER
BX AS INTEGER
CX AS INTEGER
DX AS INTEGER
BP AS INTEGER
SI AS INTEGER
DI AS INTEGER
FL AS INTEGER
DS AS INTEGER
ES AS INTEGER
SS AS INTEGER
SP AS INTEGER
BusyFlag AS INTEGER
Address AS INTEGER
Segment AS INTEGER
ProcAdr AS INTEGER
ProcSeg AS INTEGER
IntNum AS INTEGER
END TYPE
DIM SHARED Registers AS RegType
Filein$ = COMMAND$
IF LEN(Filein$) = 0 THEN
CLS
PRINT "SYNTAX: PCX2ABC Filename.PCX [-]"
PRINT " - = Use lossy preprocessor"
PRINT " Output written to Filename.ABC"
END 1
END IF
x = INSTR(Filein$, "-")
IF x THEN
Lossy = -1
Filein$ = LEFT$(Filein$, x - 1)
END IF
FileOut$ = Filein$
x = INSTR(FileOut$, ".")
IF x THEN FileOut$ = LEFT$(FileOut$, x - 1)
FileOut$ = FileOut$ + ".ABC"
CALL ShowPCX(Filein$, XSize, YSize)
CALL Compress(0, 0, XSize, YSize, Lossy, rsize&, csize&)
IF csize& < 0 THEN
Registers.AX = &H3 'switch to text mode
CALL InterruptX(&H10, Registers)
PRINT "ERROR! Out of memory."
END 1
END IF
CALL SaveABC(FileOut$, XSize, YSize)
Registers.AX = &H3 'switch to text mode
CALL InterruptX(&H10, Registers)
'--- Print compression statistics
PRINT "Raw image size = "; rsize&; "bytes ("; XSize; "X "; YSize; "pixels)"
PRINT "Compressed image = "; csize&; "bytes"
PRINT "Compression Ratio = 0."; csize& * 100 \ rsize&
PRINT
PRINT "Pattern #Blks"
PRINT "--------------------"
PRINT "None = "; noc
PRINT "Horiz. Run = "; hrc
PRINT "Vert. Run = "; vrc
PRINT "Prime Color = "; pcc
PRINT "ZigZag Left = "; zlc
PRINT "ZigZag Right = "; zrc
PRINT "Vari. Length = "; vlc
PRINT
END 0 '-------------- End Program -----------
SUB ShowPCX (Filein$, XSize, YSize)
Hdr$ = SPACE$(68 + 768)
IF NOT OpenPCXFile(Filein$, Hdr$) THEN
PRINT "File Not Found"
END 1
END IF
XMin = CVI(MID$(Hdr$, 5, 2))
YMin = CVI(MID$(Hdr$, 7, 2))
XMax = CVI(MID$(Hdr$, 9, 2))
YMax = CVI(MID$(Hdr$, 11, 2))
XSize = XMax - XMin + 1
YSize = YMax - YMin + 1
NumPlanes = ASC(MID$(Hdr$, 66, 1))
PixelBits = ASC(MID$(Hdr$, 4, 1))
IF (NumPlanes < 2) OR (PixelBits = 2) OR (PixelBits = 8) THEN
PRINT "PCX must be 640x480x16"
END 1
END IF
Registers.AX = &H12 'Switch to graphics
CALL InterruptX(&H10, Registers)
i = 17
FOR k = 0 TO 15
CALL SetPaletteEGA(k, k)
t$ = MID$(Hdr$, i, 1)
r = ASC(t$) \ 4
i = i + 1
t$ = MID$(Hdr$, i, 1)
g = ASC(t$) \ 4
i = i + 1
t$ = MID$(Hdr$, i, 1)
b = ASC(t$) \ 4
i = i + 1
CALL SetPalTripleVGA(k, r, g, b)
NEXT
CALL DispPCXVE(0)
END SUB
'*** BASIC Adaptive Block Coded (ABC) Image Compression '*** (c)1993, E.F.Deel, CIS 72627,3026 '*** SHOWABC.BAS - Demo De-Compression Module, re-displays '*** compressed images from disk. '*** Link with de-compression module, DECOMP.BAS DEFINT A-Z DECLARE SUB InterruptX (IntNumber, Registers AS ANY) '$INCLUDE: 'DECOMP.DCL' TYPE RegType AX AS INTEGER BX AS INTEGER CX AS INTEGER DX AS INTEGER BP AS INTEGER SI AS INTEGER DI AS INTEGER FL AS INTEGER DS AS INTEGER ES AS INTEGER SS AS INTEGER SP AS INTEGER BusyFlag AS INTEGER Address AS INTEGER Segment AS INTEGER ProcAdr AS INTEGER ProcSeg AS INTEGER IntNum AS INTEGER END TYPE DIM Registers AS RegType FileIn$ = COMMAND$ IF LEN(FileIn$) = 0 THEN CLS PRINT "SYNTAX: ShowABC Filename" END 1 END IF Registers.AX = &H12 'Switch to graphics CALL InterruptX(&H10, Registers) CALL DeCompress(FileIn$, 0, 0, OK) 'Decompress & display file IF OK THEN DO: LOOP UNTIL LEN(INKEY$) 'wait for keypress Registers.AX = &H3 'switch to text CALL InterruptX(&H10, Registers) END 0 ELSE Registers.AX = &H3 'switch to text CALL InterruptX(&H10, Registers) PRINT "ERROR! Invalid file/file not found." END 1 END IF END
'*** ABC Compression Module Declarations
'--- External components from Graphics WorkShop by Crescent Software
DECLARE SUB GMove4VE (BYVAL FromCol%, BYVAL FromLine%, BYVAL Cols%,
BYVAL Lines%, BYVAL DestSegment%, BYVAL Direction%)
DECLARE SUB LineBF2VE (BYVAL x1%, BYVAL y1%, BYVAL x2%, BYVAL y2%,
BYVAL LineColor%)
DECLARE SUB GetPalTripleVGA (BYVAL PalReg%, Red%, Green%, Blue%)
'--- BASIC Compression/Decompression SubRoutines
DECLARE SUB Compress (BYVAL X%, BYVAL Y%, BYVAL XSize%, BYVAL YSize%,
BYVAL Lossy%, rsize&, csize&)
DECLARE SUB ShrinkArray (BYVAL Segment%, BYVAL Addr%, nobytes&, noblks%)
'--- BASIC File Output Routine
DECLARE SUB SaveABC(Filename$, XSize, YSize)
'--- Internal BASIC Block File Read/Write Routines
DECLARE SUB BlkGet ALIAS "B$GET3" (BYVAL FileNum%, BYVAL Segment%,
BYVAL Addr%, BYVAL Bytes%)
DECLARE SUB BlkPut ALIAS "B$PUT3" (BYVAL FileNum%, BYVAL Segment%,
BYVAL Addr%, BYVAL Bytes%)
'*** ABC De-Compression Module Declarations
'--- External assembler "components" from Graphics WorkShop
DECLARE SUB GMove4VE (BYVAL FromCol%, BYVAL FromLine%, BYVAL Cols%,
BYVAL Lines%, BYVAL DestSegment%, BYVAL Direction%)
DECLARE SUB SetPaletteEGA (BYVAL PalReg%, BYVAL Value%)
DECLARE SUB SetPalTripleVGA (BYVAL PalReg%, BYVAL Red%, BYVAL Green%,
BYVAL Blue%)
'--- External assembler component by Doug Herr
' Displays pixel block taken from a BASIC integer array
DECLARE SUB PutI(BYVAL segment%, BYVAL Addr%, BYVAL x%, BYVAL y%,
BYVAL wide%, BYVAL high%)
'--- Internal BASIC Block File Access Routines
DECLARE SUB BlkGet ALIAS "B$GET3" (BYVAL Filenum%, BYVAL Segment%,
BYVAL Addr%, BYVAL Bytes%)
DECLARE SUB BlkPut ALIAS "B$PUT3" (BYVAL Filenum%, BYVAL Segment%,
BYVAL Addr%, BYVAL Bytes%)
'--- BASIC Compression/Decompression Routines
DECLARE SUB DeCompress (FileIn$, BYVAL X%, BYVAL Y%, OK%)
DECLARE SUB ExpandArray (BYVAL inseg%, BYVAL inptr%, bytesz&, NoBlk%)
Copyright © 1994, Dr. Dobb's Journal