Augmenting the generalized hough transform to enable the mining of petroglyphs

ABSTRACT

Rock art is an archaeological term for human-made markings on stone. It is believed that there are millions of petroglyphs in North America alone, and the study of this valued cultural resource has implications even beyond anthropology and history. Surprisingly, although image processing, information retrieval and data mining have had large impacts on many human endeavors, they have had essentially zero impact on the study of rock art. In this work we identify the reasons for this, and introduce a novel distance measure and algorithms which allow efficient and effective data mining of large collections of rock art.

REFERENCES

• 1: von Ahn, L., Maurer, B., McMillen, C., Abraham, D., and Blum, M. 2008. reCAPTCHA: Human-Based Character Recognition via Web Security Measures. Science, September 12, 2008. Pages 1465--1468.
• 2: Luis von Ahn, Games with a Purpose, Computer, v.39 n.6, p.92-94, June 2006 [doi>10.1109/MC.2006.196]
• 3: Aseyev, I. V. 2008. Horseman image on an ostrich eggshell fragment. Archaeology Ethnology&Anthropology of Eurasia 34/2 (2008) 96--99
• 4: Xiang Bai , Longin Jan Latecki, Path Similarity Skeleton Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.30 n.7, p.1282-1292, July 2008 [doi>10.1109/TPAMI.2007.70769]
• 5: Ballard, D. H. 1981. Generalizing the Hough transform to detect arbitrary shapes, Pattern Recognition 13, 111--122.
• 6: Ali Borji , Mandana Hamidi , Fariborz Mahmoudi, Robust Handwritten Character Recognition with Features Inspired by Visual Ventral Stream, Neural Processing Letters, v.28 n.2, p.97-111, October 2008 [doi>10.1007/s11063-008-9084-y]
• 7: Chauvet, Stéphen-Charles. 1935. L'île de Pâques et ses Mystères (Easter Island and its Mysteries). Paris: Éditions Tel.
• 8: Richard O. Duda , Peter E. Hart, Use of the Hough transformation to detect lines and curves in pictures, Communications of the ACM, v.15 n.1, p.11-15, Jan. 1972 [doi>10.1145/361237.361242]
• 9: Grant, C., Baird, J.&Pringle, J. K. 1968. Rock drawings of the coso range. Maturango Museum, China Lake, California.
• 10: Henshilwood, CS., d'Errico, F., Yates, R., Jacobs, Z., Tribolo, C., Duller, GAT., Mercier, N., Sealy, JC., Valladas, H., Watts, I., and Wintle, AG. 2002. Emergence of modern human behavior: middle Stone Age engravings from South Africa. Science 295:1278--1280.
• 11: Hough, P.V.C. 1966. Method and mean for recognizing complex pattern, USA patent 3,069,654.
• 12: Eamonn Keogh , Li Wei , Xiaopeng Xi , Sang-Hee Lee , Michail Vlachos, LB_Keogh supports exact indexing of shapes under rotation invariance with arbitrary representations and distance measures, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: Hossein Khosravi , Ehsanollah Kabir, Introducing a very large dataset of handwritten Farsi digits and a study on their varieties, Pattern Recognition Letters, v.28 n.10, p.1133-1141, July, 2007 [doi>10.1016/j.patrec.2006.12.022]
• 14: McDonald, J. J., Veth, P. M. 2007. Pilbara and Western desert rock art: style graphics in arid landscapes. In: Rock art in the frame of Cultural Heritage of Humankind. Proceedings of the XXII Valcamonica Symposium 2007. pp. 327--334.
• 15: P. M. Merlin , D. J. Farber, A Parallel Mechanism for Detecting Curves in Pictures, IEEE Transactions on Computers, v.24 n.1, p.96-98, January 1975 [doi>10.1109/T-C.1975.224087]
• 16: Mueen, A., Keogh, E., Zhu. Q., Cash, S., Westover, B. 2009. Exact Discovery of Time Series Motifs. SDM 2009.
• 17: Niels, Ralph., Willems, Don.&Vuurpijl, Louis. 2008. The NicIcon database of handwritten icons. ICFHR 2008.
• 18: Jia-Yu Pan , André G. R. Balan , Eric P. Xing , Agma Juci Machado Traina , Christos Faloutsos, Automatic mining of fruit fly embryo images, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150489]
• 19: Pettigrew, J., Nugent, M., McPhee, A.,Wallman, J. 2008. An unexpected, stripe-faced flying fox in ice age tock art of Australia's Kimberley. Journal of Antiquity.
• 20: Powell, J. W. (Editor) 1888. Annual report of the Bureau of American ethnology to the Secretary of the Smithsonian Institution. Bureau of American ethnology, Washington, D.C.
• 21: Takaki, R., Toriwaki, J., Mizuno, S., Izuhara, R., Khudjanazarov, M. and Reutova, M. 2006. Shape analysis of petroglyphs in central Asia. Forma, Vol. 21 (No. 3), pp. 243--258.
• 22: Valladas, H., Clottes, J., Geneste, J-M., Garcia, MA., Arnold, M., Cachier, H., and Tisnérat-Laborde, N. 2001. Palaeolithic paintings: evolution of prehistoric cave art. Nature 413:479.
• 23: Remco C. Veltkamp, Shape Matching: Similarity Measures and Algorithms, Proceedings of the International Conference on Shape Modeling & Applications, p.188, May 07-11, 2001
• 24: Walt, H., David, B., Brayer, J.&Musello, C. 2006. The International Rock Art Database Project. URL: www.cs.unm.edu/~brayer/rock/waltet.html
• 25: Haim J. Wolfson , Isidore Rigoutsos, Geometric Hashing: An Overview, IEEE Computational Science & Engineering, v.4 n.4, p.10-21, October 1997 [doi>10.1109/99.641604]
• 26: Zhang, D. and Lu, G. 2004. Review of shape representation and description techniques. Pattern Recognition, 37(1): 1--19.
• 27: Zhu, Q. 2009. The Petroglyphs Webpage: http://www.cs.ucr.edu/~qzhu/petro.html

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
cultural artifacts, image processing, similarity search