7.7.1 Run-Length Coding Representations and Operations

Chapter Contents (Back)
Representation, Runlength Code. Run Length Code. Interval Code. Line Adjacency Graph. Image Compression.

Capon, J.,
A Probabilistic Model for Run-Length Coding of Pictures,
IT(5), No. 4, December 1959, pp. 157-163. BibRef 5912

Limb, J.O., Sutherland, I.G.,
Run-Length Coding of Television Signals,
PIEEE(53), No. 2, February 1965, pp. 169-170. See also Source-Receiver Encoding of Television Signals. BibRef 6502

Golomb, S.W.,
Run-Length Encodings,
IT(12), No. 7, July 1966, pp. 399-401. Run length code descriptions. BibRef 6607

Gray, K.G., Simpson, R.S.,
Upper Bound on Compression Ratio for Run-Length Encoding,
PIEEE(60), No. 1, January 1972, pp. 148. BibRef 7201

Coueignoux, P.,
A Posteriori Scaling of Run Length Encoded Polygons,
CGIP(17), No. 1, September 1981, pp. 84-89.
WWW Link. BibRef 8109

Kim, J.K., Kim, K.H., Kim, N.C.,
Conditional Run-Length Coding for Multilevel Graphics Image,
PIEEE(70), 1982, pp. 1238-1240. BibRef 8200

Tanaka, H., Leon-Garcia, A.,
Efficient Run-Lenght Encodings,
IT(28), 1982, pp. 443-457. BibRef 8200

Fujisawa, H.[Hiromichi], Endo, H.[Hirohide], Komatsu, H.[Hitoshi],
Multilevel signal compression method,
US_Patent4,476,495, Oct 9, 1984
WWW Link. run-length applied to image coding BibRef 8410

Song, I., Ann, S.,
An Upper Bound on Run-Length Coding Entropy,
PIEEE(73), 1985, pp. 1141-1142. BibRef 8500

Knockaert, L.,
Comment on 'An Upper Bound on Run-Length Coding Entropy',
PIEEE(74), 1986, pp. 1284-1285. BibRef 8600

Merrill, R.D.,
Representation of Contours and Regions for Efficient Computer Search,
CACM(16), No. 2, February 1973, pp. 69-82. Run Length Code.
WWW Link. The representation is an augmented list of edge points. The augmentation helps determine the starting points in runs. BibRef 7302

Agrawala, A.K., and Kulkarni, A.V.,
A Sequential Approach to the Extraction of Shape Features,
CGIP(6), No. 6, December 1977, pp. 538-557.
WWW Link. Run Length Code. Region extraction based on runlength encoding of each scan line, fairly fast operation. Find the perimeter, size, holes, assumes many possible objects using a sequential extraction procedure; the necks are found by locating short internal lengths using a limited brute force search that only updates for each line. Good overview of the basic techniques. BibRef 7712

Agrawala, A.K.[Ashok K.], Kulkarni, A.V.[Ashok V.], Paul, Jr., E.H.[Edwin H.],
System for extracting shape features from an image,
US_Patent4,183,013, 01/08/1980.
HTML Version. BibRef 8001

Kulkarni, A.V.,
Sequential Shape Feature Extraction from Line Drawings,
PRIP78(230-237). BibRef 7800

Pavlidis, T.,
A Minimum Storage Boundary Tracing Algorithm and Its Application to Automatic Inspection,
SMC(8), No. 1, January 1978, pp. 66-69. Discusses the Line Adjacency Graph and how to use it to generate boundaries from regions. BibRef 7801

Cederberg, R.L.T.,
Chain-Link Coding and Segmentation for Raster Scan Devices,
CGIP(10), No. 3, July 1979, pp. 224-234.
WWW Link. BibRef 7907
An Iterative Algorithm for Angle Detection on Digital Curves,
ICPR78(576-578). Chain code in a sequential manner. BibRef

Cederberg, R.L.T.,
Shrinking of RC-Coded Binary Patterns,
ICPR80(1019-1022). BibRef 8000

Ellis, Jr., J.R.,
Distribution of Run Lengths over Scanned Rectangles,
CGIP(15), No. 3, March 1981, pp. 246-264.
WWW Link. BibRef 8103

Grant, G., and Reid, A.F.,
An Efficient Algorithm for Boundary Tracing and Feature Extraction,
CGIP(17), No. 3, November 1981, pp. 225-237.
WWW Link. Generation of several property values by analysis of the lines. BibRef 8111

Capson, D.W.,
An Improved Algorithm for the Sequential Extraction of Boundaries from a Raster Scan,
CVGIP(28), No. 1, October 1984, pp. 109-125.
WWW Link. (McMaster Univ), Turns a raster stored binary image into lists of the contours in the image. There seems to be a problem when the region is one pixel wide. The cause for this is not clear, but was confirmed. BibRef 8410

Cahill, III, B.M.[Benjamin M.], Hedden, J.R.[Jeffrey R.],
Manipulation of run-length encoded images,
US_Patent4,792,981, Dec 20, 1988
WWW Link. BibRef 8812

Kim, S.D., Lee, J.H., and Kim, J.K.,
A New Chain-Coding Algorithm for Binary Images Using Run-Length Codes,
CVGIP(41), No. 1, January 1988, pp. 114-128.
WWW Link. Specify the type of run code for each one using a 3X2 mask, then generate the chain-code using the run type. (No reference to Capson.) BibRef 8801

Piper, J.,
Efficient Implementation of Skeletonisation Using Interval Coding,
PRL(3), December 1985, pp. 389-397. BibRef 8512
Interval skeletons,
This group has several papers on interval coding techniques with most operations covered somewhere. BibRef

Ji, L., and Piper, J.,
Fast Homotopy-Preserving Skeletons Using Mathematical Morphology,
PAMI(14), No. 6, June 1992, pp. 653-664.
IEEE DOI BibRef 9206

Ji, L.,
Multi-resolution skeletons without explicit image smoothing,

Ji, L., Piper, J., and Tang, J.Y.,
Erosion and Dilation of Binary Images by Arbitrary Structuring Elements Using Interval Coding,
PRL(9), No. 3, March 1989, pp. 201-209. Efficient implementation of morphological operations using interval coding techniques. BibRef 8903

Piper, J., and Rutovitz, D.,
Data Structures for Image Processing in a C Language and Unix Environment,
PRL(3), No. 2, 1985, pp. 119-129. BibRef 8500

Rutovitz, D.,
Efficient Processing of 2-D Images,
IAP(229-253), 1989. BibRef 8900

Pham, D.T., Abdollahi, M.,
Image compression using polylines,
PR(21), No. 6, 1988, pp. 631-637.
WWW Link. 0309
Expand on run length coding. Data compression is achieved because only the x-coordinates (or the difference in x-coordinates) and the grey levels of points at the ends of the line segments that make up the polylines are stored, rather than the grey levels of all the pixels. BibRef

Chaudhuri, B.B., Chandrashekhar, S.,
Neighboring Direction Runlength Coding: An Efficient Contour Coding Scheme,
SMC(20), 1990, pp. 916-921. BibRef 9000

Roye, J.M.[John M.],
Method and apparatus for simplifying runlength data from scanning of images,
US_Patent4,821,336, 04/11/1989.
HTML Version. BibRef 8904

Kumaran, M., Umbaugh, S.E.,
A Dynamic Window-Based Runlength Coding Algorithm Applied to Gray-Level Images,
GMIP(57), No. 4, July 1995, pp. 267-282. BibRef 9507

Miyatake, T.[Takafumi], Matsushima, H.[Hitoshi], Ejiri, M.[Masakazu],
Contour Representation of Binary Images Using Run-type Direction Codes,
MVA(9), No. 4, 1997, pp. 193-200.
HTML Version. Contour Tracing. Only the White/Black or Black/White transistion points are used as input. BibRef 9700

Chung, K.L., Yan, W.M.,
Vectorizations of Randomized Matching for Run-Length Coded Strings,
PRL(18), No. 1, January 1997, pp. 63-72. 9704

Quek, F.K.H.[Francis K.H.],
An algorithm for the rapid computation of boundaries of run-length encoded regions,
PR(33), No. 10, October 2000, pp. 1637-1649.
WWW Link. 0006

Yuen, H., Hanzo, L.,
Block-Run Run-Length Coding of Handwriting and Bilevel Graphics-Based on Quadtree Segmentation,
PRL(18), No. 2, February 1997, pp. 187-191. 9704

Shen, X.Q., Spann, M.,
3D Region Representation Based on Run-Lengths: Operations and Efficiency,
PR(31), No. 5, May 1998, pp. 575-585.
WWW Link. 9805
Not just 2d regions. BibRef

Modayil, J., Cheng, H., Li, X.B.,
Improved Piecewise Approximation Algorithm for Image Compression,
PR(31), No. 8, August 1998, pp. 1179-1190.
WWW Link. 9807

Berghorn, W., Boskamp, T., Lang, M., Peitgen, H.O.,
Fast variable run-length coding for embedded progressive wavelet-based image compression,
IP(10), No. 12, December 2001, pp. 1781-1790.

Berghorn, W., Boskamp, T., Lang, M.[Markus], Peitgen, H.O.,
Context conditioning and run-length coding for hybrid, embedded progressive image coding,
IP(10), No. 12, December 2001, pp. 1791-1800.

Tu, C.J.[Cheng-Jie], Liang, J.[Jie], Tran, T.D.,
Adaptive runlength coding,
SPLetters(10), No. 3, March 2003, pp. 61-64.
IEEE Top Reference. 0301
Earlier: ICIP02(II: 665-668).

Nielsen, B.[Birgitte], Albregtsen, F.[Fritz], Danielsen, H.E.[Havard E.],
Low Dimensional Adaptive Texture Feature Vectors From Class Distance and Class Difference Matrices,
MedImg(23), No. 1, January 2004, pp. 73-84.
IEEE Abstract. 0403
Earlier: A2, A1, A3:
Adaptive Gray Level Run Length Features from Class Distance Matrices,
ICPR00(Vol III: 738-741).

Bailey, D.G.,
Chain coding streamed images through crack run-length encoding,

Liu, Y.K.[Yong-Kui], Žalik, B.[Borut], Wang, P.J.[Peng-Jie], Podgorelec, D.[David],
Directional difference chain codes with quasi-lossless compression and run-length encoding,
SP:IC(27), No. 9, October 2012, pp. 973-984.
Elsevier DOI 1210
Directional difference; Chain code; Contour; Data compression; Compressed directional; Difference chain code BibRef

Žalik, B.[Borut], Lukac, N.[Niko],
Chain code lossless compression using move-to-front transform and adaptive run-length encoding,
SP:IC(29), No. 1, 2014, pp. 96-106.
Elsevier DOI 1402
Chain code BibRef

Chapter on 2-D Feature Analysis, Extraction and Representations, Shape, Skeletons, Texture continues in
Voronoi Diagrams, Delaunay Triangulation, 2-D Meshes .

Last update:Mar 13, 2017 at 16:25:24