Let A and B be two square matrices respectively of area N × N and M × M defined on the same alphabet Σ. For each position ( i , j ) in A, ACSM finds the largest square sub-matrix exactly matching a square sub-matrix at some position ( h , k ) in B. An exact match implies checking all elements in the two sub-matrices and verifying if they are identical at the corresponding positions. The area of the largest common square sub-matrices is progressively summed. Finally, the average area is computed as the similarity value between A and B.

The ACSM similarity measure is defined as follows: (1) S α ( A , B ) = ∑ i = 1 N ∑ j = 1 N W ( i , j ) N 2 , W ( i , j ) ⩾ α , where W ( i , j ) is the area of the largest square sub-matrix at position ( i , j ) in A exactly matching a square sub-matrix at some position ( h , k ) in B, and α is a parameter setting the minimum allowed area of the square sub-matrices to be considered.

The ACSM similarity measure varies between 0 (any match occurs between A and B) and ∑ i = 1 N ∑ j = 1 N min { i , j } 2 N 2 (when A and B are identical). In this last case, for each position ( i , j ) in A, the area of the largest square sub-matrix exactly matching inside B is the maximal area min { i , j } 2 (Amelio and Pizzuti, 2013).

Let A ( i , j ) k be the square sub-matrix of area k × k and bottom-right corner at position ( i , j ) in A. The procedure for computing the ACSM similarity measure is reported in Algorithm 1.

The algorithm iterates over A (steps 2–4). For each position ( i , j ) in A, it finds the largest square sub-matrix of area bigger than or equal to α exactly matching inside B (steps 6–12). It is accomplished starting from the square sub-matrix of maximal area min { i , j } 2 at position ( i , j ) in A (step 5). Its exact match is verified with a sub-matrix in B, provided that its area is bigger than or equal to α (steps 6–7). If a match occurs, the largest common square sub-matrix at ( i , j ) is found (step 8). Otherwise, the square sub-matrix of smaller area at ( i , j ) is considered to match inside B, provided that its area is bigger than or equal to α (step 10). Increasingly smaller square sub-matrices are verified at ( i , j ) until an exact match inside B is found or the area of the sub-matrix is smaller than α. If an exact match is not found at ( i , j ), the contribution of that position to the similarity measure is zero (steps 13–15). The routine of match M ( A ( i , j ) d , B ) at step 7 verifies if the square sub-matrix A ( i , j ) d has an exact match with some square sub-matrix in B. The area of the largest common square sub-matrices at the different positions in A is progressively summed (step 16). At the end, this value is averaged on the area of A (step 20), and the ACSM similarity measure is returned as output (step 21).

Figure 1 shows two matrices A and B of size N = M = 5 with elements in the alphabet Σ = { 1 , 2 , 3 }.

Figure 2 shows the extraction of the largest common square sub-matrix at position ( 5 , 4 ) in A ( A ( 5 , 4 ) 2 of area 2 × 2, in red). The maximal square sub-matrix at position ( 5 , 4 ) is A ( 5 , 4 ) 4 of area min { 5 , 4 } 2 = 4 × 4 (in cyan). The smaller square sub-matrix of area 3 × 3 at position ( 5 , 4 ) is A ( 5 , 4 ) 3 (in blue). It is visible that A ( 5 , 4 ) 4 neither A ( 5 , 4 ) 3 exactly match inside B.

Let α be equal to 4. Figure 3 shows the set of the largest square sub-matrices of A exactly matching at some position inside B. Some positions of A are not considered, because of the α value. For example, at position ( 4 , 3 ) in A the largest square sub-matrix exactly matching inside B is A ( 4 , 3 ) 1 = | 2 | of area 1 × 1. Because its area is smaller than α = 4, it is disregarded.

At the end, the ACSM similarity measure is computed from the area of the largest common square sub-matrices: (2) S 4 ( A , B ) = W tot N 2 = 4 × 9 + 9 25 = 1.8.

The time complexity of Algorithm 1 is dominated by the exact match procedure M ( A ( i , j ) d , B ), searching for the exact correspondence of the sub-matrix A ( i , j ) d inside B. It can take O ( M 2 ) time, which is independent from the area of the sub-matrix (Crochemore et al., 1995). In the worst case, for each position ( i , j ) in A (for a total of N 2 positions), a maximum of N sub-matrices can be matched inside B (because of the d parameter). Consequently, the brute-force approach takes O ( M 2 N 3 ) time, which can be further reduced to O ( M 2 N 2 log 2 N ) performing a binary search on d (Amelio and Pizzuti, 2013). Although a generalized suffix-tree based solution can be applied on the two matrices, reducing the time complexity to O ( M 2 + N 2 ), the construction of the trie takes O ( M 2 ( log 2 M + log 2 | Σ | ) + N 2 ( log 2 N + log 2 | Σ | ) ), which can be quite demanding for large matrices (Amelio and Pizzuti, 2016). Also, the trie data structure is memory-allocated, requiring an extra space of O ( M 2 + N 2 ) (Giancarlo, 1995).

To overcome the current limitations, the A-ACSM similarity measure, an approximate variant of the ACSM similarity measure has been introduced, which omits a portion of elements at regular intervals in the matching process of the sub-matrices (Amelio, 2016). Accordingly, row and column offsets Δ r and Δ c determine the size of the interval, which is the distance between the elements to match in the sub-matrices. Although a generalized suffix-tree based solution is not used, the A-ACSM method obtains a lower execution time than Algorithm 1 of ACSM. However, the main limitation of A-ACSM is the size of the interval, which should be appropriately set in order to avoid information loss in measuring the similarity.

Accordingly, a similarity evaluation which is more efficient than Algorithm 1 and requires any element omission in matching the sub-matrices is still an unsolved problem, and it is the object of our investigation.

In Eq. (1), the term W ( i , j ) is substituted by W ‾ ( i , j ), which is the area of the largest square sub-matrix at position ( i , j ) in A bigger than or equal to α exactly matching a square sub-matrix at the same position ( i , j ) in B. It is worth noting that W ‾ ( i , j ) can be different from W ( i , j ), because the two largest square sub-matrices at position ( i , j ) in A matching: (i) at the same position ( i , j ) in B, and (ii) at some (other) position ( h , k ) in B, can be different.

Accordingly, the eACSM similarity measure is defined as follows: (3) S ‾ α ( A , B ) = ∑ i = 1 N ∑ j = 1 N W ‾ ( i , j ) N 2 , W ‾ ( i , j ) ⩾ α .

The procedure for computing the eACSM similarity measure is shown in Algorithm 2.

The routine M ( A ( i , j ) d , B ) at step 7 of Algorithm 1 is substituted by the routine of single match SM ( A ( i , j ) d , B ( i , j ) d ). In particular, it computes the exact match between the square sub-matrix A ( i , j ) d of area d × d at position ( i , j ) in A and the square sub-matrix B ( i , j ) d of area d × d at the same position ( i , j ) in B. Hence, the match of A ( i , j ) d is no more searched at every position inside B. The total area of the largest common square sub-matrices at the same positions in A and B is denoted as W ‾ tot .

It is worth noting that the eACSM similarity value can be lower than the ACSM similarity value. In fact, matching the sub-matrices in A and B at the same positions is a stricter constraint in the similarity computation than matching at different positions. Nonetheless, like in the ACSM similarity measure, the eACSM similarity measure ranges in the interval [0, ∑ i = 1 N ∑ j = 1 N min { i , j } 2 N 2 ]. This value can be easily normalized dividing by the maximum value.

The substitution of the match routine M in Algorithm 1 with the single match routine SM noticeably reduces the time complexity of the procedure.

Although using a generalized suffix tree takes O ( M 2 + N 2 ) time (Amelio and Pizzuti, 2016), the new method has the advantage to not require the construction and allocation of the tree index. Hence, it is more efficient in this sense.

Let A and B be the same two matrices depicted in Fig. 1. The largest square sub-matrix at position ( 3 , 4 ) in A exactly matching at the same position ( 3 , 4 ) in B is A ( 3 , 4 ) 2 = B ( 3 , 4 ) 2 of area 2 × 2, in red. The sub-matrix of maximal area at position ( 3 , 4 ) is A ( 3 , 4 ) 3 of area min { 3 , 4 } 2 = 3 × 3 (in blue). It can be observed that A ( 3 , 4 ) 3 does not match at the same position ( 3 , 4 ) in B.

Figure 5 shows the set of the largest square sub-matrices of A exactly matching at the same positions inside B when α is set to 4. Some positions of A are not considered in the similarity computation, because of the α value. For example, at position ( 2 , 3 ) in A, the largest square sub-matrix exactly matching at the same position ( 2 , 3 ) in B is A ( 2 , 3 ) 1 = | 3 | of area 1 × 1. Because its area is smaller than α = 4, it is discarded.

It can be observed that the sub-matrices A ( 2 , 5 ) 2 and A ( 4 , 2 ) 2 (see Fig. 3) are no more included in the set of the largest common square sub-matrices. This is because A ( 2 , 5 ) 2 and A ( 4 , 2 ) 2 do not match at the same positions ( 2 , 5 ) and ( 4 , 2 ) in B, but they match at position ( 5 , 5 ) in B.

Finally, the eACSM similarity measure can be computed from the area of the largest common square sub-matrices as follows: (4) S ‾ 4 ( A , B ) = W ‾ tot N 2 = 4 × 7 + 9 25 = 1.48.

Let I D be an image dataset where the images are categorized in different semantic classes. Also, let Q be a query image not included in I D and belonging to one of the semantic classes. The aim is to retrieve from I D the top K most (less) (dis)similar images to Q which are also relevant. Images belonging to the same semantic class of Q are considered relevant. In order to evaluate the retrieval accuracy, we employ the well-known retrieval precision measure (Tourassi et al., 2007), which is defined as follows: (5) retrieval precision = RI K , where RI is the number of relevant retrieved images and K is the number of retrieved images. In order to compute the retrieval precision, the (dis)similarity between the query image Q and each image in I D is computed. Then, the images are sorted in increasing or decreasing order according to the obtained (dis)similarity values. At the end, the relevant images among the top K retrieved images are selected, and their number RI is computed.

Because the retrieval precision is dependent on the selected query image, for a given value of K, we compute this measure for different query images. At the end, we average over the different query images and return the average retrieval precision for the evaluation. Hence, for each value of K = 1 , … , N, where N ≪ | I D |, we compute the average retrieval precision for the top K retrieved images.

Also, we evaluate the temporal performances of the (dis)similarity measure by computing the Average Time per Query ( ATQ), which is the execution time (in seconds) required for computing the (dis)similarity between a query image Q and each image in I D averaged over the different query images. Basically, we introduce the ATQ as follows: (6) ATQ = 1 | Q | ∑ Q ∈ Q T Q , where Q is the set of considered query images, and T Q is the total execution time required for computing the (dis)similarity between the current query image Q and all images in I D .

We perform the evaluation on a randomly selected subset of images from the MNIST dataset.1¹

http://cis.jhu.edu/sachin/digit/digit.html.

From the original dataset, we randomly select for the experiment 100 images for each semantic class, in order to obtain a subset of 1000 images with 10 semantic classes. Then, we randomly select 7 query images from the original dataset, not included in the subset of 1000 images and belonging to 4 out of 10 semantic classes. Each image is of area 28 × 28 in bitmap format (.bmp).

Figure 6 shows sample images from the MNIST dataset.

Also, we perform a second evaluation on a randomly selected subset of images from the NIST Special 19 dataset.2²

https://www.nist.gov/srd/nist-special-database-19.

We extract an image subset corresponding to the only alphabet letters. Basically, we retrieve the relevant images corresponding to the class (letter of the alphabet) of the query image, independently from the writer and the field origin. Accordingly, we use the categorization of the segmented images by class. In this way, the retrieval task is more complex because of the different writing styles and field information.

From the original dataset, we randomly select a subset of 30 segmented images from 7 classes, for a total of 210 images. Also, we randomly extract a set of 5 query images not included in the subset of 210 images, each belonging to one of the 7 classes. Each image is resized to 28 × 28 pixels and converted in bitmap (.bmp) format.

Figure 7 shows sample images from the NIST Special 19 dataset.

Because the Common Submatrix approaches derive from the notion of shared information, which has roots in information theory (Ulitsky et al., 2006), we compare eACSM with other four information-theoretic dissimilarity measures usually adopted in image processing (Tourassi et al., 2007): (i) Joint entropy, (ii) Kullback–Leibler divergence, (iii) Jensen–Shannon divergence, and (iv) Arithmetic-geometric mean divergence.

The Joint entropy ( JE) is the entropy of the joint histogram of two images A and B. If the two images are similar, their joint entropy is low in comparison with the sum of their individual entropies. Consequently, JE is considered a distance measure: (7) JE = − ∑ a ∑ b p A B ( a , b ) log 2 [ p A B ( a , b ) ] .

The Kullback–Leibler divergence ( KL) measures the distance between the probability distribution of one image a ( x ) and the probability distribution of the second image b ( x ) (approximated as the image histograms). KL quantifies the average efficiency of adopting the histogram of one image for codifying the histogram of the second one. Consequently, the more similar the two images are, the lower is the KL value: (8) KL ( b | | a ) = ∑ x b ( x ) log 2 b ( x ) a ( x ) .

The Jensen–Shannon divergence ( JD) is a more stable version of KL to noise and variations in histogram binning. Also, it is a symmetric measure and limited between 0 and 2: (9) JD ( a , b ) = ∑ x ( b ( x ) log 2 b ( x ) a ( x ) + b ( x ) + a ( x ) log 2 a ( x ) a ( x ) + b ( x ) ) .

The Arithmetic-Geometric Mean divergence ( AGM) quantifies the KL divergence between the arithmetic and geometric means of the probability distributions a ( x ) and b ( x ) of the two images: (10) AGM ( a , b ) = ∑ x a ( x ) + b ( x ) 2 log a ( x ) + b ( x ) 2 a ( x ) b ( x ) .

We use the image histograms for approximating the marginal probability distributions of the single images and the joint probability distributions. Accordingly, we set the number of bins of the histograms equal to 256, which is a sufficient number for obtaining a good approximation.

Finally, we compare the eACSM similarity measure with the baseline ACSM similarity measure and its approximate variant A-ACSM. Hence, we set the α parameter of all methods to 5, which revealed the best performances in a similar experiment (Amelio and Pizzuti, 2016). In A-ACSM, we set the parameters of row and column offsets Δ r and Δ c respectively to 1 and 4, which experimentally obtained the highest accuracy (Amelio, 2016).

While the retrieval precision values obtained by eACSM are competitive with those obtained by ACSM and A-ACSM in both the subsets of images from the MNIST and NIST datasets, the temporal performances of eACSM are much better than the other two methods.

In particular, Table 6 reports the ATQ taken by eACSM, ACSM and A-ACSM on the two datasets. Graphical results are depicted in Fig. 9.

It is worth noting that, for the subset of images from the MNIST dataset, the ATQ of eACSM is around 7 times lower than A-ACSM, and around 6 times lower than ACSM. For the subset of images from the NIST dataset, we can observe that the ATQ of eACSM is around 270 times lower than A-ACSM, and around 350 times lower than ACSM. It indicates that eACSM is much more scalable than ACSM and A-ACSM to be employed for larger datasets. Also, eACSM is the most efficient method to be used for retrieving relevant handwritten character images from a larger dataset.