Pattern Spotting and Image Retrieval in Historical Documents using Deep Hashing

An algorithm based on SS [12] was used for the object recognition task in the offline phase. However, this strategy presents difficulties when applied to images of historical documents. It generates several invalid regions, detecting antiquity stains, page edges, ink smudges, and other characteristics that do not represent objects of interest. Therefore, to minimize this problem, the SS algorithm was applied with only one scale variation using the Felzenszwalb and Huttenlocher algorithm [3], and only with the CTSF combination to measure the similarity of the regions. Despite considerably reducing the number of candidate regions compared to the method used in [13], several of the detected areas still represent invalid images. Thus, it was necessary to implement an algorithm that performs post-processing in the regions returned by SS.

The objective of filtering invalid regions is to exclude areas representing spots, background, page’s edges, and very small or too large regions between the $x$ and $y$ axes. For filtering based on the regions’ texture, a filter based on Gaussian derivation was used to highlight the edges in the image, which calculates the intensity of gradients in the image and reduces the potential edges to 1-pixel curves by removing non-maximum pixels from the gradient magnitude. Finally, the edge pixels are kept or removed using hysteresis thresholds on the magnitude of the gradient. As a result, we obtain a binary image with the object edges highlighted.

Specific manipulations are performed on the binary images. First, the mean of the pixel values of the image is computed. Then, a minimum average of $\alpha$ is established as a parameter, so the image is immediately excluded if the number of points is less than $\alpha$. However, some invalid images may still be undetected only with the mean threshold. Therefore, a second step handles this problem by segmenting the image into eight sectors and averaging each sector individually. Then, an image is also excluded if more than 50% of the sectors had an average lower than $\alpha$. The pseudo-code of the invalid candidate region filter is shown in Algorithm 1. Such a filter reduces up to 1/5 the number of candidate regions returned by the SS without any training on the context images. Training was avoided so as not to affect the generalization of the proposed method if used on another image database. Fig. 3 shows some examples of filtered invalid regions.

Finally, features are extracted from the valid candidate regions and stored to be used in the online phase. As described in the next section, two CNN architectures were evaluated as base of the feature extractors.

A siamese neural network (SNN) is used to compute the similarity between the query and image candidates. SNN is a neural network architecture that combines two identical networks with the same configuration, parameters, and weights. Two images are used as input to the network to calculate their similarity. As a first approach, two CNN architectures were evaluated as alternatives to composing our SNN. The architectures used were the VGG19 [10] and ResNet50V2 [6]. We chose these two architectures for their tried-and-true feature extraction abilities and their convenient availability in the deep learning framework in which the experiments were performed.

VGG19 [10] is a CNN with 19 layers. This CNN is designed for applications in large-scale image classification and consists of five convolutional blocks interleaved with five max-pooling layers. Through some experiments in this work, it was possible to see great potential in applying this network as a feature extractor. Using the outputs of each block and concatenating them into a feature vector, we observed that some color and shape characteristics were well evidenced in the final result. We also evaluated the combination of pairs of blocks to find the best result.

ResNet50V2 is a residual deep network and emerged as a family of extremely deep architectures, having good precision and convergence [5]. The base of ResNet50V2 is inspired by the philosophy of VGG [10] networks. The convolutional layers use a 3$\times$3 filter and follow these rules: (i) for the same output feature map size; the layers have the same number of filters; and (ii) if the feature map size is reduced by half, the number of filters is doubled to preserve the per-layer complexity. Thus, ResNet50V2 has 50 convolution layers, max-pooling and average-pooling layers.

To apply the transfer learning concept, both VGG19 and ResNet50V2 were pre-trained in a supervised way on the ImageNet dataset [9], with 1.28 million training samples and 50 thousand validation samples organized into 1000 classes, containing images from different contexts and objects. Several models of SNNs were built to establish a comparison between the two architectures and variations in the architectures themselves.

Pairs of images generated from the ImageNet dataset were used to train the SNNs. The images are resized to 224$\times$224 pixels using bilinear interpolation, as shown in Fig. 4. Overall, 250,000 pairs were generated, where 150,000 are negative pairs, and 100,000 are positive pairs, following the ratio of 1.5$\times$ more negative pair images proposed by [8].

The two images were used as input of the SNNs of the experiment. The Euclidean distance was calculated with the resulting feature maps to find the similarity. After the calculation, the distance measurement was normalized by a dense layer using sigmoid activation, as shown in Fig. 5. Finally, the loss function used to train the network was the contrastive loss, proposed in [4].

For feature extraction with ResNet50V2, two variants of the network model were built. The first uses the last convolutional layer flatten, with 100,352 features, and the second uses the global average pooling layer, with 2048 features. The model using the convolutional layer was called ResNet Conv and the model using the global average pooling layer was called ResNet GAPool.

Four variants of the network were built for the feature extraction with the VGG19 architecture. As previously explained, the use of VGG19 block outputs is very sensitive to color and texture variations, something beneficial for the representation of features. To test which blocks have a better extraction, models were made using the concatenation of all blocks and the concatenation of pairs of these blocks. The first one using all blocks was called VGG19 Blocks, containing 1472 features. The second one using blocks 4 and 5 was called VGG19 Block4-5, with 1024 features. The third one using blocks 2 and 3 was called VGG19 Block2-3, with 384 features. Moreover, the last one using blocks 2 and 5 was called VGG19 Block2-5, containing 640 features.

With the creation of the models, they were used to construct the SNNs and trained with the pairs of positive and negative images. After training, the six models extracted features from all candidate images and their values stored in separate files. It is important to emphasize that the features were represented by floating-point values with 32 bits until that moment, representing a high storage cost.

To mitigate such a storage problem, deep hashing was also applied. The primary purpose of deep hashing is to transform the feature map with floating-point values into a more compact feature map using a binary code representation.

Hashing is one of the most used methods due to its efficiency in terms of computation and storage. It aims to convert the original high-dimensional features into low-dimensional hash codes so that the hash codes of similar objects are as close as possible and the hash codes of different objects are as diverse as possible. The purpose of the hashing algorithm is to map the features of the original space into a Hamming space, which leads us to compact hash codes composed of 0 and 1 values. As a result, hash encoding is very efficient in binary computation and storage, such as depicted in [7].

The models previously built with deep learning were used in our hashing solution, thus composing deep hashing. A new layer was added at the end of each network. This layer consisted of transforming floating-point values into binary values, characterizing a discretization process. The construction of this layer was done using a discretization layer, which maps each element in a continuous interval. This algorithm was used considering a margin of value 1.

With the inclusion of this layer in each of the extractors of the SNNs, they were trained using the same process based on pairs of negative and positive images. However, the Hamming distance was the similarity calculation used for the hash codes. After training, the six models with hashing were used to extract the features of the candidate images, thus completing the offline phase.

With the process of the offline phase completed, it is possible to use the system in the online phase. The online phase consists of extracting features from the query and comparing them with the entire list of candidates built in the offline phase. The features represented by floating-point values were compared using the Euclidean distance, while for the binary code features, the comparison was made with the Hamming distance, which consists of the sum of the absolute difference between each feature. However, when dealing with binary values, or values of only one bit, it is also possible to apply the XOR operation between the elements. In this operation, when comparing equal values, it returns 1, and with different values, it returns 0. The XOR operation can be done faster on the processor since it is a native bitwise operation. After comparing all the elements, a sum of all the results is made, as denoted in Equation (1).

After the calculation, the results for each query were ordered for both the Euclidean and Hamming distances. Then, the lists of Top $n$ candidates were generated to evaluate the models.

The database used to carry out the experiments was DocExplore, proposed in [1] which consists of 1500 images of historical documents dating from the 10th to the 16th century. The original documents were extracted from the DocExplore project and are in possession of the Municipal Library of Rouen, France. All images were scanned at 600dpi resolution, resulting in dimensions ranging from 3000 pixels to 4000 pixels. Due to computational cost and storage, the images were compressed with a maximum of 1024 pixels in each dimension and 72dpi. The database provides 1447 unique queries, and their sizes range from 20$\times$11 pixels to 1307$\times$319 pixels.

The application of the SS algorithm in the DocExplore database was done with the diversification strategies combining the color element, texture, size, and fill, resulting in 976,486 candidate regions of objects. Through some experimentation, the value 0.06 was established for the $\alpha$ parameter of the invalid region filter function. After applying the invalid region filter, the number of candidate regions was dropped to 786,718, representing a decrease of 19.4%.

The number of candidate regions found by the algorithm used in Wiggers et al. [13] was 36,159,870, approximately 46 times bigger than the result found in our work. This high number of candidate regions also represents a higher storage cost and processing time since the query must be compared with all the candidates.

For the training of the SNN models, the 250,000 pairs of images generated from the ImageNet database were used with a holdout of 70% for training and 30% for validation. Thus, the training set had 105,000 negative pairs and 70,000 positive pairs. The validation set had 45,000 negative pairs and 30,000 positive pairs. The training of all models were done with 25 epochs.

Tab. I shows the experimental results for the IR problem using the ResNet50V2 and VGG19 architectures applied to the set of candidate images returned by SS. The AlexNet network was also tested, the same architecture used by Wiggers et al.  [13]. AlexNet was trained following the same steps described in Wiggers et al.  [13] and applied to the same set of candidate images as ResNet50V2 and VGG19. The top 100, 300, 500, 700, and 1000 best results were evaluated for the IR task. In this task, the best result was in the top 1000 of VGG19 Block4-5 with an mAP of 53.21%, surpassing by 10.4 percentage points the result of AlexNet and by 14.6 percentage points the result of Wiggers et al.  [13], which used selective search with 36,159,870 candidate images. These results depict that a filtered SS and returning a smaller number of candidates can positively influence the image retrieval result.

For testing the models using deep hashing, the two best networks of each of the ResNet50V2 and VGG19 architectures were chosen. The experimental protocol used was the same, only changing the similarity calculation for the Hamming distance. Tab. II shows the results for networks using deep hashing (H).

Now comparing the experimental results against state-of-the-art approaches, we observe that the method proposed by En et al.  [2] outperforms the VGG19 Block4-5 and VGG19 Block4-5 Hashing methods by 4.8 and 9.4 percentage points, respectively. However, an advantage of the methods proposed in this work is that at no time do they use information from the DocExplore database to refine their results. In Tab. III we can visualize the main results of state-of-the-art in comparison with the best results of this work.

For the PS task, the mAP was evaluated taking into account an IoU $\geq$ 0.5 and with the 100, 300, 500, 700, and 1000 best similarity results.

Tab. IV shows the experimental results for the PS problem. As in the image retrieval, the two best networks of each of the ResNet50V2 and VGG19 architectures were chosen for testing the models using deep hashing.

Tab. V shows the results for networks using deep hashing (H). Contrary to some expectations, the network using the VGG19 Block4-5 performed better in binary code than in floating-point values.

With En et al.  [2] and Wiggers et al.  [13], it was observed that multiple candidate images often contained only part of the query or overlapped with other candidate images, thus reducing system performance. To alleviate the aforementioned problem, a post-processing step was proposed to use a union of these retained candidate images to discover rectangular regions as a way to improve the performance of the Pattern Spotting task. Thus, the first 3000 candidates were selected, and the union step was applied, assuming an IoU of 0.85. If two images had an IoU measurement greater than 0.85, the image with the smallest distance was kept, and the other was excluded. After the union, the first 100, 300, 500, 700, and 1000 were considered to feed the evaluation system. For all results, an improvement in mAP was observed after post-processing (PP).

In comparison with the results against state-of-the-art methods, we have that the ResNet Conv PP method surpasses the one proposed by Wiggers et al.  [13] PP at 2.56 percentage points. In Tab. VII we can visualize the main results of state of art compared to the models presented in this paper.

Fig. 6 shows the qualitative results of the images returned for the search of five queries using the VGG19 Block4-5 Hashing feature map, with 1024 dimensions. These results are promising, considering that most of the Top 5 images are similar to those used in the searches and the feature extractor used was based on deep hashing.

Tab. VIII shows the average time required for query search and the amount of storage needed to save the feature maps of all candidates in the offline phase. Time is averaged over 50 different queries. The storage space considers only the feature map’s size, without any additional structure to facilitate indexing and storage.

The results show that the models using the VGG19 architecture were better in the Image Retrieval task, where it is necessary to find only the first best occurrence of the query on the page. However, for the Pattern Spotting task, where it is required to compose a list of similar images and locate them on the page, the models using the ResNet50V2 architecture achieved a better result.

The significant improvement presented in this work was reducing the computational effort applied to solve the problem. While in [13], the candidate regions were more than 36 million, the proposed method achieved approximately 780 thousand candidate regions. Consequently, it was possible to optimize the results and the processing time both in the IR task and in the PS task, as observed in Tables VII, III and VIII. While the method proposed by Wiggers et al. [13] needed more than 580 seconds to search for a query, the proposed method performs the same search in a maximum of 45 seconds while achieving superior results.

Another advantage was the application of deep hashing. Even transforming the characteristics to binary values, the result was not so harmed when we take into account that in the method proposed by Wiggers et al. [13], the search for a query could take 200 times longer than Hashing methods. In addition to the search time, the cost in terms of storage was also significantly reduced. In the method proposed by Wiggers et al. [13], more than 550 GB would be needed, while in the approach using VGG19 with Hashing, this number is no more than 0.09 GB.

It was possible to notice that in some cases, the transformation of the characteristics to the binary domain can increase the result, as observed in the VGG19 Block4-5 model where we had an improvement of almost 2 percentage points. Regarding query search time, converting to binary code reduced the time by approximately 30% for methods using VGG19. In terms of storage, we migrated from a structure of floating-point values with 32 bits and started to use only 1 bit, reducing the overall storage cost by 32 times.