A new parallel algorithm for the linear quadtree coding scheme, named Two-Dimensional Template-based En coding (2DTE), is designed in this study. The proposed parallel algorithm is implemented on a 32-node nCUBE 2 supercomputer system. There are three pro cessing stages in the proposed parallel algorithm, in cluding data allocation, 2DTE coding scheme, and data merging. The proposed parallel algorithm is expected to render a speedup effect that is approximately pro portional to the number of processors, as compared with the result derived by a single-processor system.
Get full access to this article
View all access options for this article.
References
1.
Abel, D.J.1984. A tree structure for large quadtrees. Comput. Vision, Graphics Image Process. 27: 19-31.
2.
Bhaskar, S.K., Rosenfeld, Z., and Wu, A.1988. Parallel processing of regions represented by linear quadtrees . Comput. Vis. Graph. Image Process., 42: 371-380.
3.
Chang, H.K.C., and Tso, C.K.1992. Two-dimensional template-based encoding for quadtree representation . In J. Vandewalle, R. Boite, and M. Moonen (Eds.), Proceedings of the Sixth European Signal Processing Conference . Amsterdam: Elsevier Science Publisher Co., pp. 627-631.
4.
Dyer, C.R.1982. The space efficiency of quadtrees. Comput. Graphics Image Process.19:335-348.
5.
Dyer, C.R., Rosenfeld, A., and Samet, H.1980. Region representation: boundary codes from quadtrees. Comm. ACM23:171-179.
6.
Gahegan, M.N.1989. An efficient use of quadtrees in a geographic information system. Int. J. Geo-graph. Inf. Syst.3:201-214.
7.
Gargantini, I.1982a. An effective way to represent quadtrees. Comm. ACM25(12):905-910.
8.
Gargantini, I.1982b. Translation, rotation, and superposition of linear quadtree . Int. J. Marc-Machine Studies18(3):253-263.
9.
Hung, Y., and Rosenfeld, A.1989. Parallel processing of linear quadtrees on a mesh-connected computer. J. Parallel and DistributedComputing7(1):1-27.
10.
Hunter, G.M., and Steiglitz, K.1979. Operations on images using quadtrees. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-1, 1(2):145-153.
11.
Klinger, A., and Dyer, C.R.1976. Experiments on picture representation using regular decomposition . Comput. Graphics Image Process.5:68-105.
12.
Klinger, A., and Rhodes, M.L.1979. Organization and access of image data by areas. IEEE Trans. Pattern Anal. Mach. Intell., PAMI-1, 1(1):50-60.
13.
Mason, D.C.1990. Linear quadtree algorithms for transputer array. IEE Proceedings, Pt. E137(1): 114-128.
14.
Mei, G.G., and Liu, W.1986. Parallel processing for quadtree problems. In Proceedings of the International Conference on Parallel Processing . Illinois: IEEE Computer Society , pp. 452-454.
15.
Morton, G.M.1966. A computer oriented geodetic data base, and a new technique in file sequencing. Ottawa: IBM Canada Ltd. Unpublished report.
16.
Nandy, S.K., Moona, R., and Rajagopalan, S.1988. Linear quadtree algorithms on the hypercube. In Proceedings of the International Conference on Parallel Processing . Pennsylvania: IEEE Computer Society , pp. 227-229.
17.
Rosenfeld, A., Samet, H., Shaffer, H.C., and Webber, R.E.1984. Use of hierarchical data structures in geographical information systems. In D. F. Marble, K. E. Brassel, D. J. Peuquet , and H. Kishomoto (Eds.) In Proceedings of the International Symposium on Spatial Data Handling . Department of Geography, University of Zurich-Irchel , Switzerland: pp. 392-411.
18.
Samet, H.1980. Region representation: quadtrees from boundary codes. Comm. ACM23(3):163-170.
19.
Samet, H.1981. An algorithm for converting rasters to quadtrees. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-3, 3(11):93-95.
20.
Samet, H.1984. The quadtree and related hierarchical data structures . ACM Comput. Surveys16(2): 187-260.
21.
Samet, H.1989. The design and analysis of spatial data structure. Reading, Mass.: Addison-Wesley.
22.
Shaffer, C.A., and Samet, H.1987. Optimal quadtree construction algorithms. Comput. Vision, Graph. & Image Process.37:402-419.
23.
Tanimoto, S., and Pavlidis, T.1975. A hierarchical data structure for picture processing. Comput. Graphics Image Process.4: 104-119.
24.
Wang, F.1991. Relational-linear quadtree approach for two-dimensional spatial representation and manipulation. IEEE Trans. Knowledge and Data Engineering3(1): 118-122.
25.
Yang, S.N., and Lee, R.R.1992. Efficient parallel neighbor finding algorithms for quadtrees on hypercubes. In W. T. Chen (Ed.) Proceedings of the 1992 International Conference on Parallel and Distributed Systems. Taiwan: Dept. of Computer Science, National Tsing Hua University, pp. 449-455.
