“Data structures for picture processing” by Shapiro

A variety of algorithms have been inventedfor use in picture processing. An important aspect of the algorithms are the data structures employed. A data structure may be chosen to represent a particular structural relationship, to save space, or to allow for fast access to data. This paper surveys four major classes of data structures used in current picture processing research and gives several examples of the use of each type of structure in particular algorithms or systems. The structures surveyed are linear lists, hierarchic structures, graph structures, and recursive structures.

1. Arbib, M. A., and E. M. Riseman, Computational Techniques in Visual Systems: Part I. The Overall Design, Tech. Rep. 76-10, Dept. of Computer and Information Science, U. of Mass., Amherst, Mass., Jul. 1976.
2. Busacker, R. G., and T. L. Saaty, Finite Graphs and Networks: An Introduction with Applications, McGraw-Hill, New York, 1965.
3. Davis, L. S., “Understanding Shape: Angles and Sides,” IEEE Tran. Comput., Vol. 3-26, No. 3, Mar. 1977, pp. 236-242.
4. Davis, L. S., “Shape Matching Using Relaxation Techniques,” Proc. of the IEEE Conf. on Pattern Recognition and Image Processing, Jun. 1977, pp. 191-197.
5. Feng, H. Y., and T. Pavlidis, “The Generation of Polygonal Outlines of Objects from Gray Level Pictures,” IEEE Transactions on Circuits and Systems, Vol. CASS-22, No. 5, May 1975, pp. 427-439.
6. Fischler, M. A., and R. A. Elschlager, “The Representation and Matching of Pictorial Structures,” IEEE Tran. Comput., Vol. C-21, No. 1, Jan. 1973, pp. 67-92.
7.. Freeman, H., “Techniques for the Digital Computer Analysis of Chain-Encoded Arbitrary Plane Curves,” Proc. of the National Electronics Conf., Vol. 17, Oct. 1961, pp. 421-432.
8. Freeman, H., “Computer Processing of LineDrawing Images,” Computing Surveys, Vol. 6, No. 1, Mar. 1974, pp. 57-97.
9. Freeman, H., “Analysis of Line Drawings,” Proc. of the NATO Advanced Study Institute on Image Processing, Jun. 1976.
10. Freeman, H., and L. S. Davis, “A Corner Finding Algorithm for Chain Encoded Curves,” IEEE Tran. on Computers, Mar. 1977, pp. 297-303.
11. Furtado, A. L., “Characterizing Sets of Data Structures by Graph Grammars,” Proc. of the Conf. on Computer Graphics, Pattern Recognition, and Data Structure, May 14-16, 1975, pp. 103-107.
12. Gray, J. C., “Compound Data Structure for Computer-Aided Design-A-Survey,” Proc. of the ACM 22nd National Conf., 1967, MDI Publications, Wayne, Penn., pp. 355-365.
13. Hanson, A. R., and E. M. Riseman, A Progress Report on Visions: Representation and Control of Visual Models, Tech. Rep. 76-9, Dept. of Computer Science, U. of Massl, Amherst, Mass., Jul. 1976.
14. Haralick, R. M., L. S. Davis, A. Rosenfeld, and D. L. Milgram, Reduction Operations for Constraint Satisfaction, TR-560, Comp. Science Center, U. of Md., College Park, Md., Aug. 1977.
15. Haralick, R. M., and L. G. Shapiro, The Consistent Labeling Problem, Center for Research, Inc., U. of K., Lawrence, Ks., Feb. 1978.
16 Haralick, R. M., and L. G. Shapiro, “Decomposition of Polygonal Shapes by Clustering,” Proc. 145 IEEE Conf. on Pattern Recognition and Image Processing, Jun. 6-8, 1977, pp. 183-190.
17. Horowitz, S. L., and T. Pavlidis, “Picture Segmentation by a Tree Traversal Algorithm,” JACM, Vol. 23, No. 2, Apr. 1976, pp. 368-388.
18. IEEE Computer Society, Proc. Workshop on Picture Data Description and Management, Apr. 31-22, 1977.
19. Johnson, T. E., “Sketchpad III, A Computer Program for Drawing in Three-Dimensions,” AFIPS Spring Joint Computer Conf., 1963.
20. Kelly, M. D., “Edge Detection in Pictures by Computer Using Planning,” Machine Intelligence 6, 1971, pp. 379-409.
21. Klinger, A., “Data Structures and Pattern Recognition,” Proc. First Int’l. Joint Conf. on Pattern Recognition, Washington, D. C., IEEE, New York, 1973.
22. Klinger, A., “Regular Decomposition and Picture Structure,” Proc. 1974 Int’l. Conf. SMC, Dallas, Tex., IEEE, N.Y. 1974, pp. 307-310.
23. Klinger, A., and C. Dyer, “Experiments on Picture Representation Using Regular Decomposition,” CGIP, Vol. 5, No. 1, Mar. 1976, pp. 68-105.
24. Klinger, A., K. S. Fu, and T. L. Kunii, Data Structures, Computer Graphics, and Pattern Recognition, Academic Press, N.Y., 1977.
25. Newman, W. M., and R. F. Sproul, Principles of Interactive Computer Graphics, McGraw-Hill, N.Y., 1973.
26. Pavlidis, T., Structural Pattern Recognition, Springer-Verlag, Berlin, 1977.
27. Pavlidis, T., “Segmentation of Pictures and Maps through Functional Approximation,” Computer Graphics and Image Processing 1, 1972, pp. 360-372.
28. Pavlidis, T., “A Minimum Storage Boundary Tracing Algorithm and Its Application to Automatic Inspection,” IEEE Tran. SMC, Jan. 1978.
29. Pavlidis, T., and K. Steiglitz, “The Automatic Counting of Asbestos Fibers in Air Samples,” Proc. Third Int’l Conf. on Pattern Recognition, Nov. 1977.
30. Rosen, C. A., and N. J. Nilsson, Application of Intelligent Automata to Reconnaissance, SRI Project 5953, Dec. 1967.
31. Shapiro, L. G., and R. M. Haralick, “Decomposition of Two-Dimensional Shapes by Clustering,” to appear in IEEE Tran. Comput., 1978.
32. Shapiro, L. G., “ESP: A High-Level Graphics Language,” Proc. Second Annual Conf. on Computer Graphics and Interactive Techniques, Jun. 1975.
33. Shapiro, L. G., and R. J. Bacon, “ESP3: A Language for Pattern Description and a System for Pattern Recognition,” IEEE Tran. S. E., Vol. SE-3, No. 2, Mar. 1977, pp. 169-183.
34. Shapiro, L. G., and R. M. Haralick, “A General Spatial Data Structure,” to be presented at the IEEE Conf. Pattern Recognition and Image Processing, Jun. 1978.
35. Sutherland, L. E., Sketchpad: A Man-Machine System, MIT Tech. Rep. No. 296, 1963.
36. Tanimoto, S., and T. Pavlidis, “A Hierarchical Data Structure for Picture Processing,” Computer Graphics and Image Processing 4, 1975, pp. 104-
119.
37. Tanimoto, S. L., and T. Pavlidis, “The Editing of Picture Segmentations Using Local Analysis of Graphs,” CACM, Vol. 20, No. 4, Apr. 1977, pp. 223-229.
38. Tanimoto, S. L., “An Iconic/Symbolic Data Structuring Scheme,” Pattern Recognition and Artificial Intelligence, Academic Press, N.Y., 1976, pp. 452-471.
39. Warnock, J. E., A Hidden Surface Algorithm for Computer Generated Halftone Pictures, Computer Science Dept., U. of Utah, TR 4-15, Jun. 1969.
(See also Newman and Sproul, 1973.)
40. Weingarten, N., and D. P. Greenberg, “ThreeDimensional Graphic Input Using Recursive Instancing,” Proc. Computer Software and Applications Conf., Nov. 8-11, 1977, pp. 377-383.
41. Williams, Robin, “A Survey of Data Structures for Computer Graphics Systems,” Computing Surveys, Vol. 3, No. 1, Mar. 1971, pp. 1-21.
42. Zahn, C. T., Jr., “Data Structures for Pattern Recognition Algorithms: A Case Study,” Proc. Conf. on Computer Graphics, Pattern Recognition,
and Data Structures, May 14-16, 1975, pp. 191-195.