7.3.8 Fast, Parallel, Multiresolution Techniques for the Computation of Skeletons

Chapter Contents (Back)
Fast Algorithms. Skeletons. Parallel Algorithms.

Triendl, E.E.[Ernst E.],
Skeletonization of Noisy Hand-Drawn Symbols Using Parallel Operations,
PR(2), No. 3, September 1970, pp. 215-226.
WWW Link. BibRef 7009

Stefanelli, S., and Rosenfeld, A.,
Some Parallel Thinning Algorithms for Digital Pictures,
JACM(18), No. 2, April, 1971, pp. 255-264. An early parallel implementation. See also Connectivity in Digital Pictures. See also Thinning Algorithms for Gray-Scale Pictures. BibRef 7104

Arcelli, C., Cordella, L.P., and Levialdi, S.,
Parallel Thinning of Binary Pictures,
Electronic Letters(11), No. 7, 1975, pp. 148-149. BibRef 7500

Arcelli, C., Cordella, L.P., and Levialdi, S.,
A Grassfire Transformation for Binary Digital Pictures,
ICPR74(152-154). BibRef 7400

Rao, C.V.K.[C. V. Kameswara], Prasada, B., Sarma, K.R.,
A parallel shrinking algorithm for binary patterns,
CGIP(5), No. 2, June 1976, pp. 265-270.
WWW Link. BibRef 7606

Wu, A.Y., Bhaskar, S.K., and Rosenfeld, A.,
Computation of Geometric Properties from the Medial Axis Transform in O(n log n) Time,
CVGIP(34), No. 1, April 1986, pp. 76-92.
WWW Link. BibRef 8604

Wu, A.[Angela], Bhaskar, S.K., Rosenfeld, A.[Azriel],
Parallel Computation of Geometric Properties from the Medial Axis Transform,
CVGIP(41), No. 3, March 1988, pp. 323-332.
WWW Link. BibRef 8803

Nitzan, D., and Agin, G.J.,
Fast Methods for Finding Object Outlines,
CGIP(9), No. 1, 1979, pp. 22-39.
WWW Link. **Move somewhere else** Intersections of polyhedra, use chamfer image to find the center, get the wire frame model. BibRef 7900

Tsao, Y.F., and Fu, K.S.,
A Parallel Thinning Algorithm for 3D Pictures,
CGIP(17), No. 4, December 1981, pp. 315-331.
WWW Link. BibRef 8112
Earlier:
A 3D Parallel Skeletonwise Thinning Algorithm Pictures,
PRIP82(678-683). BibRef
Earlier:
Parallel Thinning Operations for Digital Binary Images,
PRIP81(150-155). BibRef

Hilditch, C.J.,
Comparison of Thinning Algorithms on a Parallel Processor,
IVC(1), No. 3, August 1983, pp. 115-132.
WWW Link. BibRef 8308

Bourbakis, N.G.,
A Parallel-Symmetric Thinning Algorithm,
PR(22), No. 4, 1989, pp. 387-396.
WWW Link. BibRef 8900

Steffensen, N., Bourbakis, N.G.,
A method for parallel skeletonization of images,
ICIP95(II: 109-112).
IEEE DOI 9510
BibRef

Hall, R.W.,
Comments on 'A Parallel-Symmetric Thinning Algorithm' by Bourbakis,
PR(25), No. 4, April 1992, pp. 439-441.
WWW Link. BibRef 9204

Zhang, T.Y., and Suen, C.Y.,
A Fast Parallel Algorithm for Thinning Digital Patterns,
CACM(27), No. 3, March 1984, pp. 236-240. Extract the skeleton (MAT). BibRef 8403

Lu, H.Y., and Wang, P.S.P.,
A Comment on 'A Fast Parallel Algorithm for Thinning Digital Patterns',
CACM(29), No. 3, March 1986, pp. 239-242. BibRef 8603
And:
An Improved Fast Parallel Thinning Algorithm for Digital Patterns,
CVPR85(364-367). (National Taiwan Univ. and Northeastern Univ.), Faster than earlier ones with usually the same results. MAT. Fast version of Zhang and Suen ( See also Fast Parallel Algorithm for Thinning Digital Patterns, A. ) and Stefanelli and Rosenfeld ( See also Some Parallel Thinning Algorithms for Digital Pictures. ). BibRef

Chen, Y.S., Yuan-Ze, Hsu, W.H.,
Parallel Thinning Algorithm for Binary Digital Patterns,
HPRCV92(II, Chapter 7). BibRef 9200

Chen, Y.S., and Hsu, W.H.,
A Systematic Approach for Designing 2-Subcycle and Pseudo 1-Subcycle Parallel Thinning Algorithms,
PR(22), No. 3, 1989, pp. 267-282. BibRef 8900
Earlier:
A 1-Subcycle Parallel Thinning Algorithm for Producing Perfect 8-Curves and Obtaining Isotropic Skeleton of an L-Shape Pattern,
CVPR89(208-215).
IEEE DOI BibRef

Chen, Y.S.,
Comments on: A Systematic Approach for Designing 2-Subcycle and Pseudo 1-Subcycle Parallel Thinning Algorithms,
PR(25), No. 12, December 1992, pp. 1545-1546.
WWW Link. 0401
BibRef

Chen, Y.S., Hsu, W.H.,
A Modified Fast Parallel Algorithm for Thinning Digital Patterns,
PRL(7), 1988, pp. 99-106. BibRef 8800

Chen, Y.S.[Yung-Sheng],
Hidden Deletable Pixel Detection Using Vector Analysis in Parallel Thinning to Obtain Bias-Reduced Skeletons,
CVIU(71), No. 3, September 1998, pp. 294-311.
DOI Link BibRef 9809
Earlier:
The Use of Hidden Deletable Pixel Detection to Obtain Bias-Reduced Skeletons in Parallel Thinning,
ICPR96(II: 91-95).
IEEE DOI 9608
(Yuan-Ze Inst. of Technology, ROC) BibRef

Arcelli, C., and Sanniti di Baja, G.[Gabriella],
A One-Pass Two-Operation Process to Detect the Skeletal Pixels on the 4-Distance Transform,
PAMI(11), No. 4, April 1989, pp. 411-414.
IEEE DOI (CNR Naples, Italy) Compute the skeleton in one raster scan of the image where 4-Distance (distance from a border) is given for each point. BibRef 8904

Arcelli, C., and Sanniti di Baja, G.[Gabriella],
A Width-Independent Fast Thinning Algorithm,
PAMI(7), No. 4, July 1985, pp. 463-474. (CNR Naples, Italy) Another fast method. BibRef 8507

Arcelli, C., Sanniti di Baja, G.,
An Approach to Figure Decomposition Using Width Information,
CVGIP(26), No. 1, April 1984, pp. 61-72.
WWW Link. BibRef 8404

Holt, C.M., Stewart, A., Clint, M., and Perrott, R.H.,
An Improved Parallel Thinning Algorithm,
CACM(30), No. 2, February 1987, pp. 156-160. Simply a variation on the other algorithms. Probably a good place to start for a good implementation of MAT. BibRef 8702

Beffert, H.[Helmut], and Shinghal, R.[Rajjan],
Skeletonizing Binary Patterns on the Homogeneous Multiprocessor,
PRAI(3), No. 2, 1989, pp. 207-217. BibRef 8900

Milgram, M., and de Saint Pierre, T.,
Boundary Detection and Skeletonization with a Massively Parallel Architecture,
PAMI(12), No. 1, January 1990, pp. 74-78.
IEEE DOI BibRef 9001

Chen, C.S., and Tsai, W.H.,
A New Fast One-Pass Thinning Algorithm and Its Parallel Hardware Implementation,
PRL(11), 1990, pp. 471-477. BibRef 9000

Wu, R.Y., and Tsai, W.H.,
A New One-Pass Parallel Thinning Algorithm for Binary Images,
PRL(13), 1992, pp. 715-723. BibRef 9200

Kim, S.K.,
Optimal Parallel Algorithms for Region Labeling and Medial Axis Transform of Binary Images,
SIAM_JDM(4), No. 3, 1991, pp. 385-396. BibRef 9100

Gauch, J.M., and Pizer, S.M.,
Multiresolution Analysis of Ridges and Valleys in Grey-Scale Images,
PAMI(15), No. 6, June 1993, pp. 635-646.
IEEE DOI BibRef 9306

Stewart, A.,
A One-Pass Thinning Algorithm With Interference Guards,
PRL(15), No. 8, August 1994, pp. 825-832. BibRef 9408

Chin, R.T., Wan, H.K.[Hong-Khoon], Stover, D.L., and Iverson, R.D.,
A One-Pass Thinning Algorithm and Its Parallel Implementation,
CVGIP(40), No. 1, October 1987, pp. 30-40.
WWW Link. A 1 pass technique based on 1X4 and 4X1 templates rather than the usual 3X3. BibRef 8710

Gokmen, M., and Hall, R.W.,
Parallel Shrinking Algorithms Using 2-Subfields Approaches,
CVGIP(52), No. 2, November 1990, pp. 191-209.
WWW Link. BibRef 9011

Hall, R.W., Kuecuek, S.,
Parallel 3D Shrinking Algorithms Using Subfields Notions,
ICPR92(I:395-398).
IEEE DOI BibRef 9200

Jenq, J.F., and Sahni, S.,
Serial and Parallel Algorithms for the Medial Axis Transform,
PAMI(14), No. 12, December 1992, pp. 1218-1224.
IEEE DOI BibRef 9212

Ammann, C.J., and Sartori-Angus, A.G.,
Fast Thinning Algorithm for Binary Images,
IVC(3), No. 2, May 1985, pp. 71-79.
WWW Link. BibRef 8505

Sinha, R.M.K.,
Comments on 'Fast Thinning Algorithm for Binary Images',
IVC(4), No. 1, February 1986, pp. 57-58.
WWW Link. BibRef 8602

Guo, Z., and Hall, R.W.,
Fast Fully Parallel Thinning Algorithms,
CVGIP(55), No. 3, May 1992, pp. 317-328.
WWW Link. BibRef 9205

Guo, Z., and Hall, R.W.,
Parallel Thinning with Two-Subiteration Algorithms,
CACM(32), No. 3, March 1989, pp. 359-373. BibRef 8903

Hall, R.W.,
Fast Parallel Thinning Algorithms: Parallel Speed and Connectivity Preservation,
CACM(32), No. 1, January 1989, pp. 124-131. Evaluation of See also Improved Parallel Thinning Algorithm, An. with an improvement. Parallel speed compared with See also Fast Parallel Algorithm for Thinning Digital Patterns, A. (and as modified by See also Comment on A Fast Parallel Algorithm for Thinning Digital Patterns, A. ). BibRef 8901

Hall, R.W.,
Optimally Small Operator Supports for Fully Parallel Thinning Algorithms,
PAMI(15), No. 8, August 1993, pp. 828-833.
IEEE DOI See the above papers. BibRef 9308

Evers, C.,
Fast Thinning Algorithms for Large Binary Images,
VF91(249-258). Algorithms suitable for very large binary images requireing one (or 2) pass through the image. BibRef 9100

Kalles, D., and Morris, D.T.,
A Novel Fast and Reliable Thinning Algorithm,
IVC(11), No. 9, November 1993, pp. 588-603.
WWW Link. BibRef 9311

Kresch, R., Malah, D.,
Morphological Reduction of Skeleton Redundancy,
SP(38), No. 1, July 1994, pp. 143-151. BibRef 9407

Kresch, R., Malah, D.,
Skeleton-based Morphological Coding of Binary Images,
IP(7), No. 10, October 1998, pp. 1387-1399.
IEEE DOI BibRef 9810

Ferreira, A.[Afonso], Ubeda, S.[Stephane],
Ultra-Fast Parallel Contour Tracing, With Application To Thinning,
PR(27), No. 7, July 1994, pp. 867-878.
WWW Link. BibRef 9407

Ferreira, A.[Afonso], Ubeda, S.[Stephane],
Computing the Medial Axis Transform in Parallel with Eight Scan Operations,
PAMI(21), No. 3, March 1999, pp. 277-282.
IEEE DOI BibRef 9903
Earlier:
Parallel Complexity of the Medial Axis Transform,
ICIP95(II: 105-108).
IEEE DOI 9510
Block based MAT. The MAT using optimal blocks, not optimal distance. BibRef

Datta, A., Parui, S.K.,
A Robust Parallel Thinning Algorithm For Binary Images,
PR(27), No. 9, September 1994, pp. 1181-1192.
WWW Link. BibRef 9409

Shih, F.Y., Wong, W.T.,
Fully Parallel Thinning With Tolerance To Boundary Noise,
PR(27), No. 12, December 1994, pp. 1677-1695.
WWW Link. BibRef 9412

Shih, F.Y., Wong, W.T.,
A New Single-Pass Algorithm for Extracting the Mid-Crack Codes of Multiple Regions,
JVCIR(3), No. 3, September 1992, pp. 217-224. BibRef 9209

Shih, F.Y., Wong, W.T.,
A New Safe-Point Thinning Algorithm Based on the Mid-Crack Code Tracing,
SMC(25), No. 2, February 1995, pp. 370-378. BibRef 9502

Shi, H.C., Ritter, G.X.,
A New Parallel Binary Image Shrinking Algorithm,
IP(4), No. 2, February 1995, pp. 224-226.
IEEE DOI BibRef 9502

Haralick, R.M.,
Performance Characterization in Image Analysis: Thinning, a Case in Point,
PRL(13), No. 1, January 1992, pp. 5-12. Evaluation, Thinning. Performance. See also Performance Characterization in Computer Vision. BibRef 9201

Jaisimha, M.Y., Haralick, R.M., Dori, D.,
Quantitative Performance Evaluation of Thinning Algorithms Under Noisy Conditions,
CVPR94(678-683).
IEEE DOI Evaluation, Thinning. BibRef 9400

Haralick, R.M., Jaisimha, M.Y., Dori, D.,
A Methodology for the Characterization of the Performance of Thinning Algorithms,
ICDAR93(282-286) BibRef 9300

Sossa, J.H.,
An Improved Parallel Algorithm for Thinning Digital Patterns,
PRL(10), 1989, pp. 77-80. BibRef 8900

Eckhardt, U.,
A Note on Rutovitz' Method for Parallel Thinning,
PRL(8), 1988, pp. 35-38. BibRef 8800

Zhang, Y.Y., and Wang, P.S.P.,
Analysis and Design of Parallel Thinning Algorithms: A Generic Approach,
PRAI(9), 1995, pp. 735-752. BibRef 9500

Zhang, Y.Y., Wang, P.S.P.,
A Modified Parallel Thinning Algorithm,
ICPR88(II: 1023-1025).
IEEE DOI BibRef 8800

Zhang, Y.Y.,
Redundancy Of Parallel Thinning,
PRL(18), No. 1, January 1997, pp. 27-35. 9704
BibRef

Zhang, Y.Y., Wang, P.S.P.,
A Parallel Thinning Algorithm with Two-Subiteration That Generates One-Pixel-Wide Skeletons,
ICPR96(IV: 457-461).
IEEE DOI 9608
(Northeastern Univ., USA) BibRef

Kong, T.Y.[T. Yung],
On Boundaries and Boundary Crack-Codes of Multidimensional Digital Images,
MDSG94(71) BibRef 9400

Chen, Y.J., Horng, S.J.,
Medial Axis Transform on Mesh Connected Computers with Hyperbus Broadcasting,
Computing(59), No. 2, 1997, pp. 95-114. 9710
BibRef

Saha, P.K., Chaudhuri, B.B., Dutta, D., Majumder, D.D.,
A New Shape-Preserving Parallel Thinning Algorithm for 3D Digital Images,
PR(30), No. 12, December 1997, pp. 1939-1955.
WWW Link. 9805
BibRef

Ahmed, M., Ward, R.K.,
Fast One Pass Knowledge Based System for Thinning,
JEI(7), No. 1, January 1998, pp. 111-116. 9807
BibRef

Zhou, X.L.[Xin-Lun], Wei, J.[Jian], Li, F.[Feng], Woo, P.Y.[Peng-Yung],
A new algorithm for parallel thinning and its hardware realization,
IJIST(10), No. 4, 1999, pp. 318-322. BibRef 9900

Borgefors, G.[Gunilla], Ramella, G.[Giuliana], Sanniti di Baja, G.[Gabriella],
Shape and topology preserving multi-valued image pyramids for multi-resolution skeletonization,
PRL(22), No. 6-7, May 2001, pp. 741-751.
Elsevier DOI 0105
See also Using resolution pyramids for watershed image segmentation. BibRef

Saha, P.K.[Punam K.], Borgefors, G.[Gunilla], Sanniti di Baja, G.[Gabriella],
A survey on skeletonization algorithms and their applications,
PRL(76), No. 1, 2016, pp. 3-12.
Elsevier DOI 1605
Survey, Skeletonization. Skeletonization BibRef

Rao, S.V., Mukhopadhyay, A.[Asish],
Fast algorithms for computing -skeletons and their relatives,
PR(34), No. 11, November 2001, pp. 2163-2172.
WWW Link. 0108
BibRef

Pan, Y.[Yi], Li, Y.M.[Ya-Min], Li, J.[Jie], Li, K.Q.[Ke-Qin], Zheng, S.Q.[Si Qing],
Efficient parallel algorithms for distance maps of 2-d binary images using an optical bus,
SMC-A(32), No. 2, March 2002, pp. 228-236.
IEEE Top Reference. 0207
BibRef

Rockett, P.I.,
An Improved Rotation-Invariant Thinning Algorithm,
PAMI(27), No. 10, October 2005, pp. 1671-1674.
IEEE DOI 0509
Analyze Ahmed and Ward: See also Fast One Pass Knowledge Based System for Thinning. show errors for 2 pixels lines and show how to fix it. BibRef


Kwon, J.S., Gi, J.W., Kang, E.K.,
An Enhanced Thinning Algorithm Using Parallel Processing,
ICIP01(III: 752-755).
IEEE DOI 0108
BibRef

Romero, F.[Francisco], Ros, L.[Lluis], Thomas, F.[Federico],
Fast Skeletonization of Spatially Encoded Objects,
ICPR00(Vol III: 510-513).
IEEE DOI 0009
BibRef

Xu, M.[Ming], Pycock, D.[David],
Multiscale medial axis through a complete set of optimal scale ridges,
ICIP99(IV:390-394).
IEEE DOI BibRef 9900
Earlier:
The Multiscale Medial Response of Grey-level Images,
BMVC98(xx-yy). boundary Confidence Voting BibRef

Bernard, T.M., Manzanera, A.,
Improved low complexity fully parallel thinning algorithm,
CIAP99(215-220).
IEEE DOI 9909
BibRef

Xia, F.[Franck],
Parallel thinning algorithm based on the wave propagation's model,
CAIP95(932-937).
Springer DOI 9509
BibRef

Frucci, M., Marcelli, A.,
Parallel skeletonization by directional information,
ICIP94(I: 681-685).
IEEE DOI 9411
BibRef

Chapter on 2-D Feature Analysis, Extraction and Representations, Shape, Skeletons, Texture continues in
Symmetries in Two Dimensions .


Last update:Nov 18, 2017 at 20:56:18