John P. Eakins, A. Jean E. Brown, Jon Riley and Richard Mulholland
Institute of Image Data Research, University of Northumbria at Newcastle-upon-Tyne

Evaluating a Shape Retrieval System for Watermark Images

Keywords: watermarks, CBIR - Content-Based Image Retrieval

The Conservation Unit and Institute of Image Data Research have been working on a collaborative project involving the design and implementation of shape retrieval system for digital images of historic watermarks from works of art on paper. This database, The Northumbria Watermarks Archive, will be published on the web and aims to provide a freely accessible and highly valuable research tool for art and paper historians, forensic scientists and paper conservators. It is intended to draw together and cross-reference existing records in addition to being the starting point for a progressive and interactive collation of new and related information. In addition to the provision of identification information for watermarks and paper, the archive will include extensive data on paper technology, paper history, working methods of artists, artists' materials and preservation/conservation issues. The archive will have the unique facility to retrieve watermark images based solely or in part on similarity of shape through the implementation of content-based image retrieval (CBIR) software written at the University specifically for the purpose (see: http://iidr.unn.ac.uk/shrew). This paper discusses the advantages of CBIR in the context of watermarks, and the results of an initial evaluation of the software.

The Watermark

A watermark is formed by the attachment of a wire design to the mesh surface of the papermakers' mould. During paper production the paper pulp is scooped from a vat onto the surface of the mould and the excess water is allowed to drain away through the mesh. The wire watermark, which sits proud of the mesh, reduces the density of fibres deposited on that area of the mould, and when the finished sheet is viewed with transmitted light, the area where the wire had been present is thinner and appears lighter than the remainder of the sheet. The papermaker's mould is a handcrafted piece of equipment that lacks the uniformity and precision that would be provided by a machine. It provides each sheet of paper with unique characteristics. This 'fingerprint' can provide the opportunity for highly accurate identification of paper type, properties, and sometimes the date and location of its production. This information in turn can be used to gather a greater understanding of ways in which papers have been used during the working life of artists, printers, writers, publishers etc.

Watermarks have been used in Western papermaking since the late thirteenth century, serving as a mark of quality and identification for the papermill or papermaker that made the sheet. The majority of watermarks created represented the papermakers' name in text or monogram, or the name or emblem of the company. Exported paper commonly bore either the arms of the city that produced the paper or symbols associated with the country of import (Brittania watermarks are commonly found on Dutch paper imported to England). Other watermarks designated the dimensions (foolscap, eagle) of the sheet, or were specifically commissioned to identify a client. As watermarks would be varied at certain intervals, theoretically it is possible to identify the origin and approximate date of a sheet of paper. As watermarks were formed in the manufacture of paper, they were difficult to counterfeit. Therefore, since the 18th century, they have been used as a security device for banknotes and official documents. Over the centuries many hundreds of thousands of watermarks have been designed and used by papermills throughout the world.

Early watermarks were formed into simple shapes (the letter 'P', crosses, circles, crescents etc.). However, as the technology for drawing thinner wire was developed, more complex designs and emblems were possible. Modern electrotyping and die-casting has enabled the production of photo-realistic watermarks commonly seen on today's banknotes and official documents. The position of early watermarks was almost always in the centre or in the centre of one half of the sheet.

Watermark Research

Watermarks have the potential to provide conservators, paper and art historians, forensic scientists and criminologists with a greater insight into the history and properties of works of art on paper, documents, books, currency, music manuscripts etc. However, successful research into watermarks (filigranology) is reliant on the availability of relevant and accurate reference material that can be easily accessed. In order to be of value to all disciplines, reference collections should provide accurate images of the watermarks, which have been carefully recorded to exact scale. Additionally:

• If non-photographic/radiographic techniques are employed, important details such as sewing marks, chain and laid lines, the relative position of countermarks should be included.
• The collection should be structured around an accepted standardised indexing system.
• It should adopt an accepted standard classification system for the description of images that is clear and unambiguous.
• The information should be presented in a logical, clearly indexed, manner to enable the relevant information to be found quickly and easily.
• It should provide reliable information related to the source of paper and date and location of production, artist usage, preservation information, and the source and accuracy of that information which should be easily cross-referenced with other collections.
• The collection should be universally accessible across disciplines ranging from art history to criminology in a format that is widely and easily available.
• It should incorporate watermarks from as many collections as possible so as to increase the likelihood of finding a successful match to a query image.

Techniques for Recording Watermarks

It is important that the details of a watermark design are recorded with great accuracy, since similarity of design or shape can never be relied upon for accurate identification. Dated watermarks for example would appear to present a clear indication of the date that the paper was produced and therefore, by association, a reliable method for the dating of historic object. However, papermakers did not tend to change the watermarks on their moulds unless they became worn or damaged (in England it is possible that dates were changed regularly after 1794¹ ) and certain moulds may have been used up to 50 years after the original date was attached, and the artist may have kept the paper in stock for a number of years before use. Additionally, popular watermarks may have been copied or imitated several times, either illegally due to the significance of quality associated with the mark,² or through sub-commission of particular orders where moulds would be lent to another mill. Under these circumstances, the main design will often appear similar or even identical, but there will be significant differences in the details such as sewing marks,³ the spacing and relative position of chain and laid lines. It is therefore critical that as much detail regarding the location of a watermark design as possible is carefully recorded if the research is to be viable.

Watermark Reference Collections

A comprehensive reference collection of watermarks that satisfies all of the criteria required for successful research is not currently available. The majority of watermark research is carried out utilising a number of published reference volumes that represent the extensive collections of certain filigranologists.⁴ A large amount of watermark research is in the form of unpublished reports within institutions, and there are a number of archives on the web.

Printed Publications

The task of identifying an unknown watermark is generally carried out using one of the published volumes containing large collections of watermark images and associated information. Unfortunately, these are often difficult to access since they are expensive to buy, out of print or available only in specialist libraries. Furthermore:

• The amount of related information in many of the reference collections is limited and the accuracy of the information contained has been questioned by contemporary researchers. ⁵
• Lack of adequate indexing means that users generally resort to a sequential search for similar watermark designs, which is time consuming and leads to inaccurate conclusions.
• It is impossible to cross-reference between volumes as they use differing and often arbitrary classification schemes.
• The majority of watermarks have been recorded using drawing and tracing methods. These often omit important details and lack the necessary accuracy required for serious research for reasons mentioned above. Furthermore, watermarks recorded by tracing (Briquet, Churchill, Heawood), Dylux paper (Gravell) and transmitted light are often incomplete due to difficulties in obtaining a clear image when the watermark has been partially or totally obscured by media.
• Many of the images have been cropped/reduced for publication without providing any indication of the change in scale.

Specialist Research & Internal Reports

Many institutions in the past have carried out studies of watermarks and paper. The majority of conservation studios keep records of watermarks found in paper objects during examination before treatment. Access and exchange of these findings is not always simple or feasible, due to the location of the research and the variety of ways that it may have been documented. Occasionally studies are published⁶, and these often present interesting conclusions. The majority of recorded watermarks however, are not published or accessible and represent a much-underused resource.

Web-based Archives

Current work to document watermarks on the Web tends to be restricted to particular collections (For example: The Digital Watermark and Ornament Catalogue⁷, The Thomas L Gravell Watermark Archive⁸, and The Archive of Papers and Watermarks in Greek Manuscripts / The Watermark Initiative⁹ ). The principal means of indexing these images has typically been according to certain arbitrary classification descriptors based on a local standard or those given by Briquet, Heawood and other early filigranologists. These descriptors are often unexpected or illogical and are rarely intuitive to those outside paper and watermark research. The Watermark Initiative and Archive of Papers in Greek Manuscripts have pioneered watermark research on the web by utilising the standards of the International Association of Paper Historians (IPH) for the registration of papers with and without watermarks, and are in the process of implementing a distributed database system for watermark archives. However, the majority of these archives continue to use textual search terms in order to retrieve images that are often abstract in shape and difficult to describe.

Content-Based Image Retrieval (CBIR)

Content-based image retrieval is the selection of images from a database via features automatically extracted from the images themselves. CBIR allows users to retrieve images from a collection on the basis of colour, texture or shape, either singly or in combination. It has potential and actual application in engineering, medical imaging, design, journalism, criminology, and more recently museology and art history.¹⁰

Shape is the most obvious requirement for searching at a primitive level. A number of features characteristic of object shape (independent of size and orientation) are identified with each stored image. Queries are answered by extracting the same shape features for the query image and retrieving those stored images whose features closely match the query. These features may include both global features (e.g. aspect ratio, circularity) and local features (eg. sets of boundary segments). The majority of CBIR systems are queried through sample images. The user selects an image from a given database, CBIR is performed, and images are retrieved which closely resemble the query in order of similarity.

The Institute for Image Data Research (IIDR) has considerable experience in the application of CBIR to trademark images. ¹¹ Whilst there are obvious stylistic differences between modern trademark images and historical watermarks, their similarities from an image processing point of view are quite striking. Both are monochrome images made up of a number of individual components, and both rely on shape elements (rather than colour or texture) to give them visual impact and distinctiveness.

Digital images of watermarks, however, differ from those of trademarks in several important ways:

• Trademarks are generally black and white (binary level) images. Watermark images tend to be greyscale (8-bit) images.
• Scale and orientation has little importance in trademark images. However, they are important to the successful identification of watermarks.
• Watermark images are encountered in a variety of very different formats (tracings, radiographic images, rubbings, photographs etc.)
• Watermark images often suffer from considerable interference due to background noise. This can be due to the chain and laid lines found in the paper, inconsistencies in paper density, or from the presence of a design on the paper surface.

The Northumbria Watermark Archive has been created at the University of Northumbria in order to test the feasibility of applying CBIR and its functionality to a database of watermark images. Based on prior research into trademark retrieval, the CBIR system, SHREW (SHape REtrieval of Watermarks) has been developed by the Institute for Image Data Research specifically for images of watermarks. SHREW is a modular system, which processes the digital watermark images by extracting the most important shape features and storing them in a database. Any new watermark can then be matched against those stored in the database, and the images most similar to the query shape will then be retrieved in rank order. The stages in the processing of the watermark images are as follows:

• Resizing: Before the original images are processed the contrast is stretched and they are re-sized to a standard 512 x 512 pixel image
• Image clean up: Extracting the initial shape from a typical watermark image can be problematic, due to the background noise and uneven image intensity distribution. A large proportion of the images are poor quality. Drawing heavily on the Institute's experience in shape description, various image-processing techniques are carried out in order to enhance the watermark.
• Segmentation: The watermark image shape is segmented in order to isolate the watermark so that edge detection and shape extraction can be performed.
• Extraction: Potentially useful shapes are then extracted from the segmented image.
• Assignment of measures: The shapes are assigned various shape measures and further processing is carried out in order to remove unwanted shapes and close broken lines.
• Construction of shape database: The remaining shape measures are then added to the database.

Content Based Image Retrieval of Watermark Images

For the purpose of the project, two formats have been selected to represent the complexity and variation of original watermark images. A large collection of digital images of tracings (from the collection of the Conservation Unit) and electron radiographs (donated to the project from the Koninklijke Bibliotheek, Netherlands) were used.

Tracings

For the purpose of extracting shape, tracings represent the easier of the two formats as they can be converted into simple binary level images with ease as demonstrated by the examples shown in Fig. 1. Tracings contain no background noise, and in the majority of cases no interference occurs from the vertical chain lines and horizontal laid lines present in the paper. These are either unrecorded, or simply suggested outside of the actual watermark shape. However, setting in place standard processing routines for a database is complicated by the fact that the tracings require processing in a different manner to the radiographs.

Fig. 1. Typical traced images.

Segmentation

To begin the segmentation process, watermark shape is enhanced by thresholding the image. This involves the selection of a grey level value between 0 and 255 via a histogram. Any pixels with a greater intensity than this value are assigned a value of 255. Pixels with a lesser value are assigned a value of 0. This produces a simple binary image in preparation for boundary extraction.

Morphology

Segmentation problems were encountered in many traced images due to the presence of incomplete lines produced either by inaccurate tracing, or by areas of the original watermark being obscured by media, precluding tracing of the entire shape. To address these issues, morphological techniques are applied to the shape in order to 'complete' the broken lines, demonstrated in Fig. 2.

Fig. 2. Typical segmentation using morphological techniques to join broken lines.

Boundary Extraction

After the morphological techniques have been applied, extraction of the shape boundaries takes place. A Laplacian filter is applied to the image. This serves to identify changes in pixel intensity, displaying single pixel lines around each shape region identified. Each of the pixel points on these lines are then removed from the image and stored as the co-ordinates of the individual shape. Fig. 3 shows a number of examples of successful boundary extraction for watermark tracings. The coloured boundaries in the examples below are assigned to different nest levels. Nest level 0 is the outer boundary shown in red. The next internal level is shown in blue and identifies the boundaries directly contained inside the outer red boundary. Any boundaries contained within the blue boundaries are coloured green, and so on.

Fig. 3. Examples of successful boundary extraction.

After segmentation, each shape is assigned a set of measures, such as relative size, aspect ratio, circularity etc. The majority of these are added to a database of shape elements, which facilitates the subsequent comparison of images.

Electron-Radiographs

In contrast to the relatively simple traced images, extracting the watermark shape from the radiographic images is immediately problematic. Background interference is produced by the chain and laid lines, which are always recorded in photographic/radiographic techniques. These run vertically and horizontally across the mould and watermark, and at least one chain line will always bisect the watermark. Although the watermark usually stands proud of the chain lines on the mould, the chain lines are often reproduced with similar density to the mark itself. This can cause considerable problems for shape extraction, as the segmentation process will often pick up chain lines as part of the overall watermark shape. Additionally, due to the inherent nature of beta and x-ray emission, radiographs produce both uneven background density and blurring, which can be problematic for shape extraction.

The radiographs taken from the Netherlands archive vary widely in quality. Fig. 4 for example, shows good and poor quality images in terms of potential shape extraction:

Fig. 4. Examples of good and poor quality radiographic images.

The laid lines (running horizontally to the chain lines) can also be responsible for many of the retrieval problems encountered by SHREW, as they also cross the watermark and are often included in the extracted shapes.

Noise Reduction and Image Deconstruction

Before the radiographic images can be segmented, some image processing is required in order to reduce the background noise. Initially, the original is heavily blurred using a median filter, which results in loss of detail and highlights the variations in intensity in the background. The background can then be subtracted from the original image. The application of a kuwahara edge-preserving filter completes the process by blurring the image in a similar manner to the median filter while maintaining the edges of the shape. In the end, as shown in Fig. 5, the watermark shape is more clearly resolved. The image produced can then be used for the segmentation process.

Fig. 5. Deconstruction, Filtering and Segmentation of Unicorn Watermark.

Laid Line Removal

A digital image essentially represents a two-dimensional array of pixel intensities existing in the spatial domain. ¹² Using image-based Fourier filters, it is possible to remove periodic features (such as laid lines) from a digital image. This technique transforms the image from the spatial domain into the frequency domain where it can be filtered, adjusted, and then transformed back again. The horizontal laid lines are removed from the image based on orientation and aspect ratio using this method. The two spots in figure 6 on the vertical axis above and below the central spot represent the laid line frequency. The further away from the centre these are, the higher the laid line frequency.

Fig. 6. Watermark image in the frequency domain.

Fig. 7 demonstrates the application of a Low Pass filter (<40Hz), which removes the laid lines, but adversely affects the watermark detail.

Fig. 7. Filtering of radiograph image. Step 1.

However, the application of a Vertical Band Stop Filter (40-60Hz) removes the laid lines while maintaining the watermark shape clearly as shown below.

Fig. 8. Filtering of radiograph image. Step 2.

After the filtering process, image deconstruction techniques are still required in order to even out the background. As with the traced images, morphological operations are performed in order to connect broken lines.

Segmentation

During segmentation, different regions are obtained from the deconstructed image. As with the tracings, the image is enhanced to produce a simple binary image in preparation for boundary extraction. As there can be in addition of 600 regions in the initial segmented image, the radiographic images take considerably longer to process than the tracings. The majority of these are small, and only an average of 250 regions are retained for further analysis.

Boundary Extraction

After clean-up routines and morphological operations have taken place, the number of boundaries produced is reduced to around 25. Further clean-up operations generally result in a reduction to an average of 11 boundaries, which can then be included in the shape-database for that image. A typical example of the boundary extraction for a unicorn watermark is demonstrated in Fig. 9.

Fig. 9. Boundary Extraction.

Fig. 10 shows a number of successful shape extractions from other watermark images.

Fig. 10. Successful shape extraction from radiographic images.

Evaluating retrieval success: Ground truths

In order to evaluate image retrieval success in CBIR, ground truths are often used. A query image is chosen, and independent researchers are asked to select the most similar images from a database by eye. Image retrieval success is evaluated on how the systems' selection of images compares with those images perceived as similar by the human observer (i.e. the ground truths). As the person used to select the image is assumed to be independent, the choice cannot be influenced by what one might expect the system to retrieve.

For the purposes of testing SHREW, a number of ground truth sets have been selected from an archive of 2000 digital images of watermarks. Amongst these are radiographic images and tracings. For each 'query', the effectiveness of SHREW is then calculated by comparing its ranked set of retrieved watermark images with the corresponding ground truth set. Measures such as normalised precision and recall ¹³ are calculated.

It is possible to gain unbiased performance figures for the database by using a selection of query images. Associated with each query image, there are a number of ground truths selected by hand. These images are required to be included in the retrieval results by the SHREW software in order to achieve success. Evaluation of the SHREW software is currently ongoing. Early results are encouraging, but already it is clear that further development of the software will be needed to improve the image clean up routines, to investigate different types of shape and structural features and to cope with cropped/partial watermark images. Currently retrieval for tracing images is considerably more successful than that for radiographs. Fig. 11 shows successful retrieval results for a tracing of a shield watermark. These are shown in order of similarity to the query image on the top left.

Fig. 11. Successful shape retrieval results for traced circular shield watermark.

Fig. 12 shows successful results from a radiographic image (the query image on the top left).

Fig. 12. Successful shape retrieval results for radiographed 'P' watermark.

Conclusion

The retrieval performance for tracings is considerably better than the electron radiographs. This is as expected, since the tracings are more clean from a processing point of view, and do not contain the background noise and interference mentioned above. In the majority of the radiographs, difficulties are encountered in the separation of the watermark shape from its background. This produced irrelevant shapes, impeding subsequent performance.

Further research is required in order to reduce noise in the electron-radiographic images, so that meaningful shapes can be extracted, and CBIR performed more successfully. Continuing research at the University of Northumbria involves the development of the segmentation process, and the merging of processing techniques for both formats, so that similar watermarks can be retrieved irrespective of their method of capture. The SHREW system has been implemented into an SQL database (The Northumbria Watermarks Archive) for publication on the web, and it is hoped that it will facilitate retrieval of information on watermarks, papermaking, paper identification, artists and their materials, conservation and art history.

November 2001

Notes

1. In 1794 an Act (Act 34 George III) was passed allowing no drawback of duty on the paper of exported books unless the paper bore a watermark on or after the date 1794.

2. This is illustrated by the fake Whatman papers produced in France, Germany and Austria during the early 19th century, with the intention to take advantage of the name and reputation of Whatman. Peter Bower states that many of the Austrian forgeries were of poor quality, compared to original Whatman paper, and have yellowed and become brittle on aging. (Bower, P. and Hills, R. (January 1996), "British Watermarks: Forgeries of Whatman Marks", The Quarterly, British Association of Paper Historians, 17, pp. 1-4.

3. When the watermark wire had been formed into a design by the mouldmaker, he sewed it into the laid and chain wires of the mould with finer copper wire. At each point, a small raised area of wire is left which leaves an impression on the paper. Although there are thousands of watermarks with similar designs, the pattern of the sewing dots can easily distinguish one from another.

4. See for example, Briquet, C.M. (1907), Les Filigranes, Geneva; Churchill, W.A. (1935), Watermarks in Paper in Holland, France, England etc. in the Seventeenth and Eighteenth Century and their Interconnections, Paper Publications Society, Amsterdam; Heawood, E. (1950), Watermarks, Mainly of the Seventeenth and Eighteenth Centuries, Paper Publications Society, Hilversum; Gravell, T. and Miller, G. (1979), A Catalogue of American Watermarks 1690-1835, Garland Reference Library of the Humanities, New York.

5. See: Voorn, H. (1960), De Papiermolens in de Provincie Noord-Holand, Haarlem, De Papierwereld.

6. See for example: The Quarterly, Journal of the British Association of Paper Conservators (BAPH), and The Paper Conservator, Journal of the Institute of Paper Conservation (IPC).

7. See http://jefferson.village.virginia.edu/gants/Folio.html (accessed January 2002)

8. See http://128.173.125.124:591/DBs/Gravell/default.html (accessed January 2002)

9. See http://abacus.bates.edu:80/Faculty/wmarchive/ (accessed January 2002)

10. See for example: Ward, A. A, Graham, M. E., Riley, K. J. and Eliot, N. (2001), "Collage and Content-Based Image Retrieval: Collaboration for enhanced services for the London Guildhall Library", Presented at the conference Museums and the Web 2001, Seattle, 15-17 March 2001.

11. Eakins, J. P., Boardman, J. M. and Graham, M. E. (1998), "Similarity retrieval of trade mark images", IEEE Multimedia, 5(2), p.53-63.

12. A digital image can be transformed into the frequency domain without any loss of information. In the frequency domain, the centre of the image is the reference. Pixels that are equidistant from this point contain frequency information in each direction.

13. Salton, G. (1974), The SMART Retrieval System: Experiments in Automatic Document Processing, Prentice-Hall.