A web interface to image-based concurrent markup using image maps

ABSTRACT

Image-based electronic editions (IBEEs) encode manuscripts using markup based on digitized images of the manuscript page. Due to the complex nature of editorial annotations, the resulting markup rarely forms a hierarchical structure---that is, ranges often overlap. To support web-based access to these editions, it is desirable to synchronize the display of markup and related satellite data with the corresponding portions of the image. This goal can be supported by image maps, which associate regions of an image with hyperlinks and actions. These links allow the user to view and manage editorial information and multimedia content associated with the markup.

In this paper we present an efficient algorithm for constructing a mapping from overlapping or intersecting markup to regions of an image. This mapping satisfies four properties: (1) Regions are located near the corresponding text. (2) Regions corresponding to nested markup elements are themselves nested. (3) Regions corresponding to intersecting markup elements themselves intersect. (4) If region R contains a collection C of other regions, then R is strictly larger than the union of the regions in C.

The fourth property above ensures spatial separation of the regions corresponding to nested markup. An image map satisfying these properties provides a convenient and intuitive linking between image coordinates and the corresponding markup ranges.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: D. Barnard et al. Hierarchical Encoding of Text: Technical problem and SGML Solutions. Computers and the Humanities 29/3 (1995) 211--231.
• 3: Marshall Bern, Triangulations, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 4: T. Bray, J. Paoli, C. M. Sperberg-McQueen and E. Maler, eds. Extensible Markup Language (XML) 1.0 (3rd Edition). W3C Recommendation, February 2004. http://www.w3.org/TR/REC-xml/
• 5: A. Dekhtyar, I. E. Iacob, J. W. Jaromczyk, K. Kiernan, and D. C. Porter. Database Support for Image-based Electronic Editions. Proceedings of the International Workshop on Multimedia Information Systems, College Park, Maryland, August 2004.
• 6: R.L.S. Drysdale and D.T. Lee. Generalized Voronoi diagrams in the plane. Proceedings of the 16 Annual Allerton Conf. Commun. Control Comput., 833--842, 1978.
• 7: P. Durusau and M.B. O'Donnel. Declaring Trees: The Future of the Evolution of Markup? Proc. Conf. on Extreme Markup Languages, 2002.
• 8: Geometry and topology for mesh generation, Cambridge University Press, New York, NY, 2001
• 9: Mark L. Farman , Joshua W. Gilkerson , Jerzy W. Jaromczyk , Chuck Staben, RepeatAssembler: A Package for Annotation of Full-Length Repetitive DNA Sequences in Fungal Genomes, Proceedings of the 2004 IEEE Computational Systems Bioinformatics Conference (CSB'04), p.464-467, August 16-19, 2004 [doi>10.1109/CSB.2004.146]
• 10: Steven Fortune, Voronoi diagrams and Delaunay triangulations, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 11: T. Imai and K. Sugihara. A failure-free algorithm for constructing Voronoi diagrams of line segments. Transaction of the Information Processing Society of Japan. Vol. 35, No. 10, 1966--1977, 1994.
• 12: Information Processing---Text and Office Systems---Standard Generalized Markup Language (SGML). Geneva: International Organization for Standardization (ISO), October 1986.
• 13: J. W. Jaromczyk and N. Moore. Geometric data structures for multihierarchical XML tagging of manuscripts. Proc. 18th European Workshop on Computational Geometry, Seville, Spain, March 2004.
• 14: J. W. Jaromczyk and N. Moore. Geometric data structures for multihierarchical XML tagging of manuscripts. University of Kentucky Technical Report TR 404-04, May 2004.
• 15: J. W. Jaromczyk, M. Kowaluk and N. Moore. On Visualization of Complex Image-Based Markup. International Conference on Computer Vision and Graphics, Warsaw, Poland, September 22--24, 2004.
• 16: K. Kiernan, J. W. Jaromczyk, A. Dekhtyar, D. C. Porter et al. The ARCHway Project: Architecture for Research in Computing for Humanities through Research, Teaching, and Learning. To be published in Literary and Linguistic Computing, 2004.
• 17: D. Kirkpatrick, Efficient computation of continuous skeletons. Proc. 20th Ann. IEEE Symp. Foundations of Computer Science. 18--27, 1979
• 18: National Center for Supercomputing Applications (NCSA). NCSA Mosaic History. University of Illinois, 2002. http://www.ncsa.uiuc.edu/Divisions/PublicAffairs/MosaicHistory/history.html
• 19: S. Pemberton, D. Austin et al, eds. XHTML 1.0, The Extensible HyperText Markup Language (Second Edition) W3C Recommendation, August 2002. http://www.w3.org/TR/xhtml1/
• 20: D. Raggett. HTML 3.2 Reference Specification. W3C Recommendation, January 1997. http://www.w3.org/TR/REC-html32
• 21: D. Raggett, A. Le Hors and I. Jacobs, eds. HTML 4.01 Specification. W3C Recommendation, December 1999. http://www.w3.org/TR/html4/
• 22: A. Renear, E. Mylonas and D. Durand. Refining our Notion of What Text Really Is: The Problem of Overlapping Hierarchies. In Research in Humanities Computing, eds. N. Ide and S. Hockey. Oxford: Oxford University Press, 1993.
• 23: C. M. Sperberg-McQueen and L. Burnard. Multiple Hierarchies. In Guidelines for Electronic Text Encoding and Interchange, XML-compatible edition, ch. 31. TEI Consortium, 2001. http://www.tei-c.org/P4X/
• 24: C. M. Sperberg-McQueen and C. Huitfeldt. GODDAG: A Data Structure for Overlapping Hierarchies. Paper presented at Principles of Digital Document Processing, Munich, Germany, September 2000.
• 25: J. Tennison and W. Piez. The Layered Markup and Annotation Language (LMAL). Proc. Conf. on Extreme Markup Languages, 2002.
• 26: Edward Tufte, Envisioning information, Graphics Press, Cheshire, CT, 1990
• 27: B. Wilson. Historical Information: HTML Support History. Index DOT Html: The Advanced HTML Reference. October 2003. http://www.blooberry.com/indexdot/html/index.html
• 28: L. Wood, V. Apparao, et. al, eds. Document Object Model (DOM) Level 1 Specification W3C Recommendation, October 1998. http://www.w3.org/TR/DOM-Level-1/
• 29: C. Yap. An o(n log n) algorithm for the voronoi diagram of a set of simple curve segments. Discrete & Computational Geometry, 2:365--393, 1987.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: Navigation

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: User issues

General Terms:
Algorithms, Human Factors

Keywords:
client-side image maps, computational geometry, concurrent markup, image-based electronic editions, voronoi diagram