Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Parallelization of image similarity analysis
Keywords:
Parallel Algorithms, Image similarity analysis, Pattern recognition, Wavelet Transform, Parallel architecturesAbstract
The algorithmical architecture and structure is presented for the parallelization of image similarity analysis, based on obtaining multiple digital signatures for each image, in which each "signature" is composed by the most representative coefficients of the wavelet transform of the corresponding image area. In the present paper, image representation by wavelet transform coefficients is analyzed, as well as the convenience/necessity of using multiple coefficients for the study of similarity of images which may have transferred components, with change of sizes, color or texture. The complexity of the involved computation justifies parallelization, and the suggested solution constitutes a combination of a multiprocessors "pipelining", being each of them an homogeneous parallel architecture which obtains signature coefficients (wavelet). Partial reusability of computations for successive signatures makes these architectures pipelining compulsory.
Downloads
Download data is not yet available.
References
[1] Akl S, “The Design and Analysis of Parallel Algorithms”, Prentice-Hall, Inc., 1989.
[2] Akl S, “Parallel Computation. Models and Methods”, Prentice-Hall, Inc., 1997.
[3] Beckmann N., Kriegel H., Schneider R., Seeger B., “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles”, Proceedings of the ACM SIGMOD, Atlantic City 1990. Pags. 322-331.
[4] Brinch Hansen, P., “Studies in computational science: Parallel Programming Paradigms”, Prentice-Hall, Inc., 1995.
[5] Castro L., Castro S., “Wavelets y sus Aplicaciones”, En los proceedings del 1er. Congreso Argentino de Ciencias de la Computación, Argentina 1995. Pags. 195-204.
[6] Chandi K. M., Misra J., “Parallel Program Design. A Foundation”, Addisson Wesley, 1988.
[7] Cody Mac A., “The Fast Wavelet Transform, Beyond Fourier Transform”, Dr. Dobb's Journal. April 1992. Pags. 16-28.
[8] De Giusti L., Tarrío D., Naiouf M., De Giusti A., “ Eficiencia y escalabilidad en algoritmos parallelos de cálculo del costo mínimo de caminos en grafos ”. En los anales del Congreso de las Nuevas Tecnologías Informática 2000. Cuba 2000.
[9] Fournier N. Castro G., “Algoritmo de Compresión de Imágenes Fijas Utilizando la Transformada de Wavelet”, Tesina de Grado Lic. en informática U.N.L.P. 1997.
[10] González R., Woods R., “Tratamiento digital de imágenes”, Addison-Wesley/Diaz de Santos, 1996.
[11] Hwang K., “Advanced Computer Architecture: Parallelism, Scalability, Programability”, McGraw-Hill, 1993.
[12] Colección de "IEEE Transactions on Parallel and Distributed Systems", IEEE.
[13] Kumar V., Grama A., Gupta A., Karypis G., “Introduction to Parallel Computing. Desing and Analysis of Algorithms”, Benjamin/Cummings, 1994.
[14] F. T. Leighton, “Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes”, Morgan Kaufmann Publishers, 1992.
[15] Massopust P., “Fractal Functions, Fractal Surfaces, and Wavelets”, Academic Press 1994.
[16] Miller R., Stout Q. F., “Algorithmic Techniques for Networks of Processors”, CRC Handbook of Algorithms and Theory of Computation, M. J. Atallah, ed, 1998.
[17] Naiouf M.,Tarrío D., De Giusti L., De Giusti A., “ Análisis de tiempo y eficiencia en cálculo parallelo del costo mínimo de caminos en grafos”. En los anales del III Workshop Chileno en Sistemas Distribuidos y Parallelismo (WCSDP). Talca (Chile) 1999.
[18] Natsev A., Rastogi R., Shim K., “WALRUS: A Similarity Retrieval Algorithm for Image Databases”, Proceedings of the ACM SIGMOD 1999 Philadelphia. Pags. 395-405.
[19] Nigam M., Sahni S., “Sorting n2 Numbers on n × n Meshes”, IEEE Transactions on Parallel and Distributed Systems, Vol. 6, No. 12: Diciembre 1995, Pags. 1221-1225
[20] "Transputer Architecture and Overview. Transpurer Technical Specifications. ", Computer System Architects,1990.
[21] Zhang T., Ramakrishnan R., Livny M., “BIRCH: An Efficient Data Clustering Method for Very Large Databases”, Proceedings of the ACM SIGMOD Conference on Management of Data. Pags. 103-114, Montreal, Canada, Junio 1996
[2] Akl S, “Parallel Computation. Models and Methods”, Prentice-Hall, Inc., 1997.
[3] Beckmann N., Kriegel H., Schneider R., Seeger B., “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles”, Proceedings of the ACM SIGMOD, Atlantic City 1990. Pags. 322-331.
[4] Brinch Hansen, P., “Studies in computational science: Parallel Programming Paradigms”, Prentice-Hall, Inc., 1995.
[5] Castro L., Castro S., “Wavelets y sus Aplicaciones”, En los proceedings del 1er. Congreso Argentino de Ciencias de la Computación, Argentina 1995. Pags. 195-204.
[6] Chandi K. M., Misra J., “Parallel Program Design. A Foundation”, Addisson Wesley, 1988.
[7] Cody Mac A., “The Fast Wavelet Transform, Beyond Fourier Transform”, Dr. Dobb's Journal. April 1992. Pags. 16-28.
[8] De Giusti L., Tarrío D., Naiouf M., De Giusti A., “ Eficiencia y escalabilidad en algoritmos parallelos de cálculo del costo mínimo de caminos en grafos ”. En los anales del Congreso de las Nuevas Tecnologías Informática 2000. Cuba 2000.
[9] Fournier N. Castro G., “Algoritmo de Compresión de Imágenes Fijas Utilizando la Transformada de Wavelet”, Tesina de Grado Lic. en informática U.N.L.P. 1997.
[10] González R., Woods R., “Tratamiento digital de imágenes”, Addison-Wesley/Diaz de Santos, 1996.
[11] Hwang K., “Advanced Computer Architecture: Parallelism, Scalability, Programability”, McGraw-Hill, 1993.
[12] Colección de "IEEE Transactions on Parallel and Distributed Systems", IEEE.
[13] Kumar V., Grama A., Gupta A., Karypis G., “Introduction to Parallel Computing. Desing and Analysis of Algorithms”, Benjamin/Cummings, 1994.
[14] F. T. Leighton, “Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes”, Morgan Kaufmann Publishers, 1992.
[15] Massopust P., “Fractal Functions, Fractal Surfaces, and Wavelets”, Academic Press 1994.
[16] Miller R., Stout Q. F., “Algorithmic Techniques for Networks of Processors”, CRC Handbook of Algorithms and Theory of Computation, M. J. Atallah, ed, 1998.
[17] Naiouf M.,Tarrío D., De Giusti L., De Giusti A., “ Análisis de tiempo y eficiencia en cálculo parallelo del costo mínimo de caminos en grafos”. En los anales del III Workshop Chileno en Sistemas Distribuidos y Parallelismo (WCSDP). Talca (Chile) 1999.
[18] Natsev A., Rastogi R., Shim K., “WALRUS: A Similarity Retrieval Algorithm for Image Databases”, Proceedings of the ACM SIGMOD 1999 Philadelphia. Pags. 395-405.
[19] Nigam M., Sahni S., “Sorting n2 Numbers on n × n Meshes”, IEEE Transactions on Parallel and Distributed Systems, Vol. 6, No. 12: Diciembre 1995, Pags. 1221-1225
[20] "Transputer Architecture and Overview. Transpurer Technical Specifications. ", Computer System Architects,1990.
[21] Zhang T., Ramakrishnan R., Livny M., “BIRCH: An Efficient Data Clustering Method for Very Large Databases”, Proceedings of the ACM SIGMOD Conference on Management of Data. Pags. 103-114, Montreal, Canada, Junio 1996
Downloads
Published
2001-10-01
How to Cite
Naiouf, M., Tarrío, D. F., De Giusti, A. E., & De Giusti, L. C. (2001). Parallelization of image similarity analysis. Journal of Computer Science and Technology, 1(05), 11 p. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/983
Issue
Section
Original Articles
