In this paper, a novel algorithm for content-based image retrieval is presented based on the two-dimensional dual tree complex wavelet transform. It includes adaptive selection of the decomposition level consistent with preliminary set retrieval time. Depending on the size of the image queries further adaptation could be applied based on the volume of information contained in the sub-band of approximation coefficients from the wavelet spectrum so the overall retrieval accuracy remains as high as possible without violating the time requirements. Specific to this approach algorithm for image database indexing is also developed. Test results are obtained with the Wang database. The average precision proved to be higher than that of other popular approaches from the practice for 5 of the image categories, reaching 100% for 2 of them. It remains almost equal for other 2 of the testing categories. It is considered to be especially applicable into CBIR systems with critical time requirements variable in different use case scenarios, including preserving cultural heritage, assuring scalability while preserving retrieval accuracy.
Content-based image retrieval (CBIR) using the two-dimensional Dual Tree Complex Wavelet Transform (2D DT-CWT) has been used for a number of years now [1-5]. CBIR systems are now widely used in preserving cultural heritage on a world-wide scale processing images of artifacts, artificially synthesized 3D models and entire sites. In [1] Patil and Talbar tested both the DT-DWT and DT-CWT for image retrieval. They selected fourth level for decomposition with major consideration of the feature size. Further, this approach is developed by Vhanmane and Sangve [2] taking the same features with Grey Level Co-occurrence Matrix (GLCM) over them. Slightly higher retrieval accuracy is achieved. In order to increase the retrieval precision, Patil and Kokare [3] include relevance feedback, provided by the user, and used rotated complex wavelet filters. They found that three iterations are enough to gain saturation of the average retrieval precision of just over 90% from most of the image queries. The performance of both R-DT-DWT and C-DT-DWT is compared to that of 4level Curvelet in [4] for 4th level of decomposition leading to slightly better results for the latter for a portion of tested images. Ciu et al. [5] propose modified DT-CWT with inclusion of hashes for feature generation. Testing database has smaller size in their study and only normalized Hamming distance presents the retrieval efficiency of the algorithm. In each of these studies, no measured or predicted retrieval times are reported, nor how the actual indexing of the database is performed.
In this paper, detailed analysis of the time consumption by the 2D DT-CWT to form feature vectors is presented in the next section, followed by description of two novel algorithms for both database indexing and image retrieval with adaptive selection of the decomposition level given required retrieval time and considering the information stored in the low-frequency sub-bands. In Section 4 experimental results are presented supporting the applicability of the proposed algorithms followed by a conclusion in Section 5. 2
2.1
Maximum Level of Decomposition and Stored Information
Estimation
The coefficients of the two dimensional Dual-Tree Complex Wavelet Transform are
obtained according to [6]:
! !, ! =
!!!! !!!! ! !, ! ! ! − !, ! − ! ,,
! !
! !, !, ! = 2! !!!!! !!!!! ! !, ! ! 2!! − !, 2! ! − ! ,
(
The decomposition structure in l=2 levels is given in Fig. 1 [7]. According to it and
as well as to the invariance to translation [8], which determines that the first level of
the scheme includes filters of a different order (let denote them by (α, β)) from those
in the following levels (let them be (γ, δ)), one pixel for l levels of full decomposition
takes the time:
!! = 10 ! + ! !∗ + 2 ! + ! − 2 !! + 12 ! − 1
! + ! !∗ + 2 ! + ! − 2 !! , (
The time needed for estimating only the approximation coefficients at level l is:
!! = 3 ! + ! !∗ + 2(! + ! − 2)!! + 4 ! − 1
! + ! !∗ + 2 ! + ! − 2 !! . (
LL1L 75° 0 n
LL1R -75° (P-1)/2 (P-1)
(Q-1)/2 -15° -45° where !!!(!) ! and !!!(!) ! are their real and imaginary part. The full decomposition !!(!) !!! !!(!) !!!
!!(!) !!! !!(!) !!! !! = !! = !! = !! = !!.! !(!) !!! !! !!.! !(!) !!! !! !!.! !(!) !!! !! ! !.! !(!) !!! !!
(!) ! ℎ!
!(!) ! ℎ!
(!) ! ℎ!
!(!) ! ℎ! 2! − !! , 2! − !! , 2! − !! , 2! − !! .
!!(!) !!
!!(!) !!
!!(!) = !!!
!!(!) = !!!
!!(!) + !!!! ,
.
!!(!)
+ !!!!
Both low-frequency sub-bands contain complex coefficients represented as:
For l ≥ 2 analogous to (
(!) !!
!!(!) ! = !!!
!!(!) ! + !!!
!!(!) ! + !!!
!!(!) ! + !!! while the total energy of the image is: The portion of information carried by the approximation coefficients then is: ! = !!! !!! !!!!!! !! !, ! .
!!(!).
!! = −!"#! !
(
Similarity Estimation Time Let I1(p,q) and I2(p,q) are two images of equal size p {0,P-1} and q {0,Q-1}. After l levels of decomposition, the area occupied by the approximation coefficients is: ! ∈ !!!!!!!! ! − 1 , !!!!!!!! ! − 1 , ! ∈ !!!!!! ! − 1 , ! − 1 . (13) The feature vectors have the following components:
!(!) = , … , (14) !!! ! !!!!
!!!! ! − 1 , ! − 1 ].
The later are totally in number: !(!) = !!!! !!!! − !!!!!!!! ! ! − !!!!!! ! = !!!"!.
(15) In this study, the Hausdorff distance is selected as a measure between the vectors based on its advantages assuring higher retrieval accuracy [9]. It is found by: !!!(!!),!! !!! !!, !! = max (ℎ!!!,!!( !,! !!! , !,! !!!! ), ℎ!!,!! ! !
! ! !,! !!! , !,! !!! ) , (16) where ℎ!(!!),!! = max!(!) min!(!) !!(!!) − !!(!!)
!! !! the set of !!(!!,)!,! to the set of !!!,!,!for all m and n within the range ! ∈ (!) !! , !!! , ! ∈ !! , ! . The norm of the directional distance is found by using the Euclidean distance. For each point in the feature space all distances to all the other points belonging to I2 are calculated and then the minimal is selected. The process leads to !(!) calculated distances each of which takes 2 multiplications, 1 addition and 1 square root. The minimal value is found by binary search in this case which needs !"#! !(!) comparisons.
For all the other points from I1 all steps are repeated and it consumes time equal to: (17) is the directional Hausdorff distance from = !(!) ! ! 2!∗ + !! + !! + !! + !!, where t> is the time needed to find the maximum among all minimums according to the expression for directional Hausdorff distance. The related distance ℎ!(!!),!! is calculated in analogous fashion where ! (!) = ! (!) . To all these time components a time !!!,!! !!!,!! needed to find the maximum from (16) is added, which is !!!" = 1 comparisons or the global time for similarity estimation based on content between the two images is: !!(!) = 2 !(!) ! ! 2!∗ + !! + !! + !! + !! + !!!". (18) 2.3
Database Indexing Time
Let’s have database comprising of B images, all of PxQ pixels in size. A comparison
based on content similarity takes place between a query and all of them. At selected
level of decomposition l the time needed for calculating all feature vectors according
to (
!!" = !"#!!. !!" = !!! + !"#!(!). (19) (20) The logarithm component relates to the sorting time of the results. Only R of them output as indexes. 3
3.1
Algorithm for Indexing Image Database The steps for feature vectors estimation of the images from the database of the CBIR system using 2D DT-CWT are given in Fig. 3. The aim is to find the level of decomposition lend at which the preserved information (energy) is at least as high as preliminary set one. For all levels, l ≤ lend the feature vectors are found and stored for all B images within the same database.
The algorithm takes as an input the whole content of the database. If necessary, normalization of the size of particular images could be done using the bi-cubic interpolation for better preserving the original shape of objects. Then, the minimum allowed energy of the approximation coefficients is being set and starting from level 1, iteratively, the 2D DT-CWT is applied from the spectrum of which as a result the actual approximation coefficients are extracted (contained in the LL (L - Lowfrequency) sub-bands). They cumulative energy is found and when all images of the database have been passed over, their average energy is also found. For each level of decomposition l the feature vectors of all images are being preserved in a separate record within the database. Then, comes the comparison with the currently registered amount of energy and if it is still higher than the preliminary set threshold, further decomposition takes place one level forward. Once the condition has been met, then the reached level is registered indicating the ending point of indexing the database.
The use of the average energy at each iteration of the indexing process for the whole database assures that any significant deviation caused by particular content leading to more evenly distributed spectrum will not affect the average retrieval accuracy for the entire collection of scenes when ever growing number of queries are passed to the system.
Begin Input of images within the database
Ii ( p, q), i = 1, B Normalizing the size of the images by bi-cubic interpolation p = 0, P −1, q = 0, Q −1
Setting up a minimal allowed energy of the approximation coefficients Еreg Level of decomposition l=1
Applying 2D DT CWT Approximation coefficients extraction
from both LL sub-bands di''(l )
energy Еa(il) i Estimating the average energy of the approximation c~oefficients B for the whole database Е a( l ) = B1 ∑i= 1 E a(il ) Making a record of the feature vectors for level l: ξ m(l,)n,i = [m, n, d m''(,ln),i ]
(l) E a ≤ Ereg
Yes
End Fig. 3. Indexing algorithm
No i=i+1 3.2
Algorithm for CBIR by Set Information Size The algorithm is given in Fig. 4. It includes query I(p, q) size normalization to PxQ pixels – the same as all images from the database. By given time treq for similarity comparison based on content with all B images, the maximum allowed level of decomposition lmax is set. Then, a check follows for the quantity of energy inside the LL sub-bands of the wavelet spectrum and afterwards a comparison with preliminary defined value !!(!). If !!(!!"#) ≥ !!(!), it follows a comparison with the feature vectors at level lmax . Otherwise, feature vectors from upper level l such that the condition for the energy to be satisfied. The estimation of !!(!) is done as the average energy from the whole database of images, at such a level that verification of the retrieval accuracy does not seem to produce considerable increase.
While analyzing the accuracy with the use of different metrics and taking into account the rank R, the resulting values for Precision and Recall could be compared for these metrics. This approach may lead to a selection of a better metric for particular application. 4
The experimental testing of the proposed algorithms is done on a PC compatible
workstation with Intel Core 2 Duo CPU running at 2.4 GHz within Matlab R2008b
environment. Wang database [10] is used containing 1000 RGB raster images with
size 256x384 and 384x256 pixels at 24 bpp. They are equally divided into 10
categories by content. During testing all of them are resized to 256x256 pixels using
bicubic interpolation. Fig. 5 shows the mean value of the energy ratio concentrated in
the sub-band of the approximation coefficients to the total energy of the image by
decomposition levels.
Given the times for executing a multiplication, addition and comparison between two
numbers for the used CPU [11] and using (
Practically applicable from a user point of view (the average home user) with respect to the retrieval time with the used hardware platform is second, third and fourth decomposition level. The average distance estimation time for them, when full validation is made over all 1000 images from the database, is 3.61 sec, 0.27 sec. and 0.10 sec, respectively. The average times at different ratios of the number of requests decomposed to the second, third and fourth levels are shown in Fig. 6. The dependency shown can be used as a calibration curve to find an appropriate relative number of images with low Sl for decomposing to a lower level l for more accurate retrieval when tuning a CBIR system. The overall retrieval accuracy of the proposed algorithm with those of 3 others – RDT DWT, C-DT DWT and 4-level Curvelet [4] is compared by the average precision achieved (Table 2).
For the categories ‘Africa’ and ‘Buses’, for which inferior values of the retrieval accuracy are obtained by giving a lower priority to the retrieval time, it is possible to use coefficients from l = 3 for the formation of the features. According to the calibration curve of Fig. 6 and taking into account the relative number of images in these two categories - 20% of the total size of the database, it follows that the average retrieval time would increase from 0.1 sec. 0.5 sec. It remains within the scope of practical relevance to the end user, which proves the applicability of the proposed approach.
As the data from Table 2 shows, for five of the categories from the database - Dinosaurs, Elephants, Horses, Roses and Nature the proposed algorithm has higher or equal average precision compared to the other 3 algorithms. In particular, the images from the Dinosaurs and Roses groups have lower within-class variability which leads to Average Precision of 100%. For the ‘Social Life’ and Food’ categories, it shows a lower but comparable value with decrease of only 3.25% and 4.5% relative to the 4level Curvelet algorithm. For the rest three categories higher level of decomposition needs to be implemented to overcome the lower resulting precision. The algorithms applicable in their present form are thought to have potential for navigation applications such as those described in [12]. In this paper novel algorithms for image database indexing and content-based retrieval are proposed using the 2D DT-CWT with adaptive selection of the level of decomposition and accounting for the information contained into the approximation coefficients’ sub-bands. The indexing and similarity estimation times are derived for arbitrary level given the size of the images and the size of the database. Having a particular retrieval time set as demand by specific application it is possible to select appropriate level for feature vectors construction and to perform the retrieval. If the required processing time for a given retrieval rank allows retrieval accuracy could be increased by using lower level coefficients from the spectrum containing more information which is applicable for certain image categories hard to be retrieved at higher levels of decomposition. Experimental results support the applicability of the proposed algorithms reaching accuracy levels comparable with the R-DT DWT, C-DT DWT and 4-level Curvelet algorithms where for half of the test database the first outperform them.