Figure 1. HTML source of the document in Figure 3
Cheong S. Ang, M.S.
Peter Brantley, M.A.
Michael D. Doyle, PhD.
Image maps facilitate the interactivity of the WWW by simulating the hotspot mechanism in traditional multimedia applications. This feature allows WWW browser users to access URLs associated with objects within an inline image merely by clicking directly on the image. Much of the current popularity of the Web is related to the ease of use imparted by this functionality.
The currently popular image-mapping implementation (ISMAP) passes the work of decoding the image map to the HTTP server, which is usually already overloaded with requests for documents, and for gateway access to non-HTTP (HyperText Transfer Protocol) [1] servers. This situation interferes with the efficiency of hotspot decoding and doesn't allow realtime decoding of URLs, such as what users encounter when passing the mouse over text-based anchors. Seidman [8] and Doyle [4] both point out that the ISMAP standard also prevents the employment of image mapping on local file systems, which is necessary in order to distribute HTML-based applications on CDROM, where a WWW server is absent. The ISMAP implementation also imposes unnecessary network overhead upon image-map decoding performance [8]. This degraded performance is the major reason for the lack of realtime interactive feedback for users, mentioned above.
Client-side image mapping is not a new concept. Ragget [7] introduced the FIG element in his HTML+ proposal. The FIG and SHAPE elements allow definition of shaped hypertext anchors in the associated image. Hotspot decoding may be performed locally because the polygon information is downloaded as part of the hypertext document. However, complete support for the complicated FIG and SHAPE elements is claimed to need significant additional processing [8]. Furthermore, both elements may not degrade gracefully in the browsers which don't support them.
Although Seidman addressed the issues of processing complexity and graceful degrading in his HTML [8] extension for client-side image mapping, his solution requires an entity definition which may become complex quickly as the complexity of the polygons grows. The polygon map and the associated image in this case are kept as two separate files. Embedding a polygon map of many complex objects in an ASCII HTML document results in a very large file. Large document means increase in both transfer and parsing time.
Eòlas Technologies, Inc. [4] developed and implemented a
client-side image map protocol based upon the MetaMAP® technology,
which encodes object identifiers into image pixel data using a
patented (U.S. patent 4,847,604) approach. This resulted in
an extremely efficient method for encapsulating URL information
with image data and for enabling realtime hotspot decoding.
A disadvantage of this implementation, however, was that use of
the resulting file format is constrained by the MetaMAP®
patent. The Polymap work described in this paper was an attempt
to allow advantages similar to those provided by the MetaMAP®-based
file format, while allowing free use of the Polymap file format
without concerns about patent issues relating to object encoding.
Although the demonstrations of this technology we describe are
based upon the GIF file format, and therefore commercial implementations
may be subject to the Unisys LZW patent, the reader will note
below that the Polymap approach is equally suitable for any of
the several public domain file formats that allow comment fields,
such as PNG or JPEG.
Our solution to the above problems is to include the polygon map data in the image. Many existing standard image data formats (e.g., GIF) have fields for application-specific data and/or comments, and adding data to those fields is legitimate. We utilize the comment field of the GIF 89 format to carry a compressed polygon map. With Polymap implementation, the HTML document does not differ in comparison to a simple inline image definition. Thus in addtion to client-side hotspot decoding and better visual feedbacks, the polymap mechanism provides WWW browsers with the versatility to either perform polygon decoding themselves, or use the conventional image mapping, the ISMAP [6] technique.
Figure 1. HTML source of the document in Figure 3
Creating a Polymap image map is actually far simpler than setting up an image for ISMAP. We have implemented a rudimentary version of the Polymapping toolkit on the MS Windows platform (available soon) which allows polygon vertex specifications by point-and-click, or by freehand contour drawing . The polygon data is compressed using the same compression engine that encodes the image data when the mapped image is saved. Since the Polymap technique does not require a separate map file, this is all a WWW server administrator has to do.
In addition, Polymapping does not interfere with the setup of an ISMAP; the server administrator is free to prepare a mapping file on the server side for Polymap-ignorant browsers.
Figure 2a. Microsoft Windows version of the Polymapping toolkit
(Object List)
Figure 2b. Microsoft Windows version of the Polymapping toolkit
(Image Window), showing outlines around hotspots, as each would
be displayed to the user during image-map decoding
The data in the GIF comment field is saved following a simple format:
GIF comment block indicator 7 /* 7 bytes of flag. 7 is a 1-byte unsigned char */ PMAP1.0 /* Polymap flag. 7 bytes of char */ N /* N bytes of encoded data. N is a 4-byte unsigned integer */ B /* The compression bit size. B is a 1-byte unsigned char */ N bytes of encoded data /* In GIF case, LZW encoded data */ GIF end of block indicator
The decoded data also has a straightforward format. The first unsigned short (2 bytes) designates the number of objects in the Polymap. Immediately following are null-terminated strings of the object names. In WWW Polymap applications, the object names are Universal Resource Locators (URLs) [3], but they may be any set of strings that is meaningful to a particular application. The name strings are followed by one or more blocks of the the following sequence:
0xFFFF
Object number
Polygon number
(x1,y1), (x2,y2),..., (xN,yN)
Enabling Polymap handling in WWW browsers merely requires extending the browsers' GIF reader comment handling routine to appropriately process the above format. There is no restriction on the implementation of the client-side decoding methods. Our browser, an enhanced version of NCSA Mosaic (downloadable from UCSF licensee's download page), deploys the windowing system's polygon and region functions to interactively highlight hotspots as the cursor passes over them. The browser responds to mouse clicks with the same routine the text-based hotspot respond function is using. Hence our browser reuses the hotspot handling codes efficiently, and gives its users a consistent look-and-feel.
In the case of JPEG, another popular Internet image format, although the comment block is written as part of the file header, there are no restrictions on the format and processing of the comment block. However, the standard JPEG DCT (Discrete Cosine Transform) plus arithmetic-coded or Huffman encoding/decoding routines may not be reused because there will not be much sharable code between the lossless and lossy mode [5]. We may resort to several different solutions: (1) include the lossless spatial DPCM coding method, which will increase the size the Polymapping program and the size of the Polymap-enabled WWW browsers; (2) leave the Polygon data uncompressed as if it is a regular string of comment(s); or (3) a compromise between (1) and (2), use a smaller and simpler compressor.
A good way to realize (3) would be to use whichever image compression engine accessible internally by the WWW browser(s). Until another format becomes more prevalent, GIF's LZW encoding is a reasonable choice. The Polymap toolkit and the most common WWW browsers have GIF compression/decompression engines built-in, and the JPEG comment handling routine may invoke the engine when necessary. No extra code is needed.
Figures 2a and Fig 2b show the Polymapping toolkit. New objects are created simply by adding their names through the Polymap Object List dialog box. The user may redo or delete the selected object by a button press. Double-clicking on an object in the object list will pop up a Name Change dialog, which allows the user to change the name of the object. The outline displayed for each object is also color-coded. The color icon beside the Name prompt reveals the color associated with the selected object. Clicking on the color icon will pop up a standard Microsoft Windows-style Color Choice dialog that enables changing the color for the selected object.
Figure 3 shows the Polymap-enabled NCSA Mosaic. Notice that the cursor is on a hotspot, a hot cup of coffee, which is highlighted with the hotspot outline. The URL indicator at the bottom of the image displays the location of the anchor.
Figure 3. Enhanced NCSA Mosaic with a Polymap HTML page
The results of the implementation are very encouraging. Our Polymapping implementation not only provides fast client-side decoding and realtime interactive feedback, but it also improves storage efficiency, setup speed, and network communication efficacy.
The hotspot polygon map of the image shown in Figure 2b would have
consumed at least 2055 bytes of space if it had been stored in
ASCII form (in an ISMAP file or HTML file as polygons1). Encapsulating
the polygon data using the Polymap method yields an overhead of
only 1285 bytes. The ISMAP file is 60% larger (Comparison in Table
1). Furthermore, Polymap storage effiency increases as the data
size increases (sample comparison: Table 1 and Table 2).
Table 1. Polymap and ISMAP Size Consideration for the White
House Image in Figure 2
Table 2. Polymap and ISMAP Size Consideration for the Sun
Microsystem Home Page image in Figure 3
We are currently adopting the geometric primitive specification of ISMAP into Polymap. More efforts will be put into refining the Polymapping toolkit and improving the polygon decoding speed on slower machines. Although our decoding engine only performs a sequential search, the performance is acceptable on machines at as low as 486 PC level. Enhancing the decoding engine with object elimination based on bounding boxes, and possibly use of a hash table will likely speed up the process.
Since there is a striking resemblance between the recently proposed
Portable Network Graphics [2] (PNG) format and GIF in terms of
overall image structure and layout, the Internet and other online
(e.g., CompuServe) communities are shifting their attention from
GIF to PNG. We are also planning on supporting PNG in future implementations
of the Polymap toolkit.
The Polymap protocol provides a solution to the major problems
confronting the ISMAP method of hotspot interaction over the
Web: redundant network access and dependence on the WWW server
to decode local pointer events. Furthermore, because of the simplicity
and efficiency of the implementation of this technique, we expect
that Polymap will find wide acceptance on the Web. Polymap technology
clearly demonstrates the possibility of realizing a complete hypergraphics
multimedia system on the WWW based on the current electronic publishing
infrastructure.
1. Berners-Lee, Tim, Hypertext Transfer Protocol, Internet Draft.
2. Boutell, Thomas, PNG (Portable Network Graphics) Specification, Tenth Draft, URL: http://sunsite.unc.edu/~boutell/png.html
3. Connolly, Daniel W., HTML 2.0 Specification Review Materials, URL: http://www.hal.com/users/connolly/html-spec
4. Doyle, Michael D., MetaMAP®, URL: http://www.eolas.com/metamap/metamap.html
5. Independent JPEG Group, JPEG System Architecture, included in the publicly released JPEG "C" Library, February 18, 1993.
6. NCSA HTTPd Development Team, NCSA Imagemap Tutorial, URL: http://hoohoo.ncsa.uiuc.edu/docs/setup/admin/Imagemap.html
7. Ragget, Dave, HTML+ Discussion Document, URL: http://info.cern.ch/hypertext/WWW/MarkUp/HTMLPlus/htmlplus_1.html
8. Siedman, James L., An HTML Extension to Support Client-Side
Image Maps, URL: http://www.ncsa.uiuc.edu/SDG/IT94/Proceedings/DDay/seidman/seidman.html
Peter Brantley, M.A.
Michael D. Doyle, PhD.