395 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 Image Retrieval Based on Coefficient Correlation Index A. A.Abdul Latef Department of Computer Science, Collage of Education-Ibn Al -Haithem , University of Baghdad Received in: 12 October 2011, Accepted in: 26February 2012 Abstract Image retrieval is an active research area in image processing, pattern recognition, and computer vision. In this proposed method, there are two techniques to extract the feature vector, the first one is applying the transformed algorithm on the whole image and the second is to divide the image into four blocks and then applying the transform algorithm on each part of the image. In each technique there are three transform algorithm that have been applied (DCT, Walsh Transform, and Kekre’s Wavelet Transform) then finding the similarity and indexing the images, useing the correlation between feature vector of the query image and images in database. The retrieved method depends on higher indexing number. Experimental results have shown better results (higher precision and recall) by applying DCT on the image than the other transform algorithms and the performance improvement if dividing the image into equal four blocks and applying the transformed algorithm into each part. Keywords:CBIR, Feature Extraction, Correlation Coefficient, DCT, Walsh Transform, Kekre’s Wavelet Transform. Introduction Digital images are an increasingly important class of data, especially as computers become more usable with greater memory and communication capacities. As the demand for digital images increases, the need to store and retrieve images in an intuitive and efficient manner arises. Hence, the field of content-based image retrieval (CBIR) focuses on intuitive and efficient methods for retrieving images from databases based solely on the content contained in the images. [1] Every CBIR systems needs functionality for feature extraction of an image viz. shape, color, texture which can represent the uniqueness of the image for the purpose of best match in the database to be searched. The features of the query image are compared with the features of all images in the feature database using various mathematical construct known as similarity measures. These mathematical similarity measuring techniques check the similarity of the features extracted to classify the images in the relevant and irrelevant classes. The research in CBIR needs to be done to explore two aspects first is the better method of feature extraction having maximum components of uniqueness and faster, accurate mathematical models of similarity measures. [2] For feature extraction in CBIR there are mainly two approaches feature extraction in spatial domain and feature extraction in transform domain. The feature extraction in spatial domain includes the CBIR techniques based on histograms, BTC, VQ. The transform domain methods are widely used in image compression, as they give high energy compaction in transformed image. So it is obvious to use images in transformed domain for feature extraction in CBIR. [3] In This proposed algorithm there are two techniques, the first one by applying the transformed algorithm on the whole image to get the feature vector while the second work by 396 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 dividing the image into four blocks and applying the transform on each block. For each technique there are three transformed algorithms are used (DCT, Walsh transform, and Kekre’s wavelet transform) to get the features and then to find the similarity using the correlation between feature vector of the query image and images in database to indexing. Discrete Cosine Transform (DCT): The discrete cosine transform (DCT) is closely related to the discrete Fourier transform. It is a separable linear transformation; that is, the two-dimensional transform is equivalent to a one-dimensional DCT performed along a single dimension followed by a one-dimensional DCT in the other dimension [4]. The definition of the two-dimensional DCT for an input image A and output image B is ….(1) , ……..(2) Where M and N are the row and column size of A, respectively. Walsh Transform The Walsh matrix was proposed by Joseph Leonard Walshin 1923. Each row of a Walsh matrix corresponds to a Walsh function. A Walsh matrix is a square matrix, with dimensions powered of 2. The entries of the matrix are either +1or −1. It has the property that the dot product of any two distinct rows (or columns) is zero. The sequence ordering of the rows of the Walsh matrix can be derived from the ordering of the Hadamard matrix by first applying the bit-reversal permutation and then the Gray code permutation. The Walsh matrix (and Walsh functions) are used in computing the Walsh transform and have applications in the efficient implementation of certain signal processing operations [3]. Walsh transform matrix is defined as a set of N rows, denoted Wj, for j = 0,1, .... , N - 1, which have the following properties: ∑ Wj takes on the values +1 and -1. ∑ Wj[0] = 1 for all j. ∑ Wj x WkT=0, for j not equal to k and Wj xWkT =N, for j=k. ∑ Wj has exactly j zero crossings, for j = 0, 1, .... , N-1. ∑ Each row Wj is even or odd with respect to its mid point The Walsh transform matrix row is the row of the Hadamard matrix specified by the Walsh code index, which must be an integer in the range [0, ... ,N - 1]. For the Walsh code index equal to an integer j, there Hadamard output code has exactly j zero crossings, for j = 0, 1, ..., N - 1. Kekre’s Wavelet Transform Kekre’s Wavelet transform is derived from Kekre’s transform [2, 5]. From NxN Kekre’s transform matrix, we can generate Kekre’s Wavelet transform matrices of size (2N)x(2N), (3N)x(3N),……, (N2)x(N2). For example, from 5x5.Kekre’s transform matrix, we can generate Kekre’s Wavelet transform matrices of size 10x10, 15x15, 20x20 and 25x25. In general MxM Kekre’s Wavelet transform matrix can be generated from NxN Kekre’s 397 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 transform matrix, such that M= N * P where P is any integer between 2 and N that is, 2 ≤ P ≤ N. Kekre’s Wavelet Transform matrix satisfies [K][K]T = [D] Where D is the diagonal matrix this property and hence it is orthogonal [2, 5]. The diagonal matrix value of Kekre’s transform matrix of size NxN can be computed as …………………………..(3) Indexing and Retrieval System 1 .Image Similarity Measure Similarity measurement is a key to CBIR algorithms. The algorithms search image database to find images similar to a given query, so, they should be able to evaluate the amount of similarities between images, [6] one of these algorithm is color correlation index. The correlation r is one of the most common and most useful statistics. A correlation r is a single number that describes the degree of relationship between two variables [6]. The correlation r is a correlation between query image and retrieved images. When A is a query image and B is a retrieved image. There are reduced to the matrices of the same size. The correlation is defined as follows: ……………………………..(4) Here is the average of matrix element A and is the average of matrix element B. .2. Image Retrieval The correlation index between features of query object and database object is used to match and display images. To assess the retrieval effectiveness, we have used the precision and recall as statistical comparison parameters [7] for the proposed CBIR techniques. The standard definitions for these two measures are given by following equations. ……………(5) ……………(6) The Proposed CBIR Method In this proposed method there are two techniques that have been used, the first one by applying the transformed algorithm on the whole image while the second work by dividing the image into four blocks and applying the transform on each block as shown in Figure 1. For each technique there are three transformed algorithms are used (DCT, Walsh transform, and Kekre’s wavelet transform). The First proposed technique This proposed method is obtained using the following steps: 1. Resize the colored images into NxNx3 (for example 128x128x3) 2. Apply transform algorithm on each color red, green, and blue. 398 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 3. Find the correlation index (by using equation (4)) between transform coefficients of red query image and transform coefficient of red database image to get red_index, then find green_index and blue index in the same way. 4. Find final_index using the following equation Final_Index = ….7 5. Repeat from step 3 until index all the images in database. 6. Retrieve the images depending on higher index number. The Second Proposed Technique This proposed method is obtained using following steps 1. Resize the colored image into NxNx3 (for example 128x128x3) 2. Divide the image into four equal square blocks (for example four blocks of size 64x64x3). 3. Apply transform algorithm on each block for red, green, and blue. 4. Find the correlation index (by using equation (4)) between transform coefficient of first red block with the first red block of image in database to get red_index, then find green_index and blue_index in the same way. 5. Find block1_index using the following equation block1_index = ….7 6. Repeat step4, and 5 to get block2_index, block3_index, and block4_index. 7. Take the average of the indexing to find the final index between two images. 8. Repeat from step 4 until index all the images in database. 9. Retrieve the images depending on higher index number. Experimental results The implementation of the proposed CBIR techniques is tested on the image database of 200 images spread across 4 categories, in each category there are 50 images. The categories and distribution of the images with sample is shown in table 1. In the proposed method there are two techniques (as explained above), for each technique used three transform algorithm (DCT, Walsh Transform, and Kekre’s Wavelet Transform). For testing the performance of each proposed CBIR technique, many queries are fired on the database. In each technique for each transform, the average precision and recall values is calculated using eq. 5 and eq. 6 and the results is shown in table 2 and 3. The DCT is giving higher values than the other transforms also the second technique gives better performance than the first one for all the transform algorithms Conclusions In this proposed algorithm used the correlation equation to find the similarity between the coefficient of transformed query image and coefficient of transformed database images. Three transform algorithms have been used (DCT, Walsh transform, Kekre’s wavelet transform). The experimental results (depending on average precision and recall) have shown that the DCT algorithm is perform better than Walsh transform and Kekre’s wavelet transform and the Kekre’s wavelet transform give better result than the Walsh transform. And for all the transformed algorithms the performance improvement if used the second technique. Reference 1.Shijiao, Zand Jun, Y. (2011), A Novel Image Retrieval Approach Based on Integer and Block Color Distribution, Journal of Computational Information Systems, 7, ( 2): 593-598. 399 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 2.Kekre, H. B. and Dhirendra, M. (2011), Sectorization of Full Kekre’s Wavelet Transform for Feature extraction of Color Images, International Journal of Advanced Computer Science and Applications, 2,(2) February. 3.Kekre, H.B. Sudeep, D. and Varun, K. (2011), Amelioration of Walsh Hadamard Texture Patterns based Image Retrieval using HSV Color Space, International Journal of Computer Science and Information Security, 09, 03. 4.Strang G. (1999), The Discrete Cosine Transform”, SIAM Review, 41( 1) 135-147. 5.Kekre, H. B.; Archana, A. and Dipali, S. (2010), Algorithm to Generate Kekre’s Wavelet Transform from Kekre’s Transform”, International Journal of Engineering Science and Technology, 2 (5)756-767. 6.Neetesh, G.; Singh, R.K., and Dey, P., (2011), A New Approach for CBIR Feedback based Image Classifier”, International Journal of Computer Applications (0975 – 8887) , 14, 4. 7.Sanjay, N. T.,and Satishkumar, L. V. (2010), Color Spaces for Transform-based Image Retrieval”, International Journal of Computer Applications (0975 – 8887) 9,12. 400 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 Table(1): samples of images in database Table (2): Average precision and recall for applying transform on the whole color image Average precision and recall category DCT Walsh Kekre’s wavelet transform Elephant 0.72 0.73 0.51 Roses 0.58 0.54 0.82 Horses 0.53 0.5 0.52 Mountains 0.54 0.43 0.5 Table (3): Average precision and recall for applying transform on each block of color image Average precision and recall category DCT Walsh Kekre’s wavelet transform Elephant 0.75 0.75 0.69 Roses 0.8 0.57 0.75 Horses 0.55 0.5 0.61 Mountains 0.65 0.4 0.61 No. of image category 50 Elephants 50 Roses 50 Horses 50 Mountains Sample of image 401 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 402 مجلة إبن الهيثم للعلوم الصرفة و التطبيقية 2012 السنة 25 المجلد 2 العدد Ibn Al-Haitham Journal for Pure and Applied S cience No. 2 Vol. 25 Year 2012 صورة باستخدام الفهرسة المعتمدة على ترابط المعامالت ا ل استرجاع االء عبد الحميد عبد اللطيف جامعة بغداد قسم علوم الحاسبات ،كلية لتربية ابن الهيثم، 2012شباط 26، قبل البحث في 2011ن االول تشري12استلم البحث في الخالصة في استرجاع الصورة هو من مجاالت البحث المهمة في مجال معالجة ألصور واكتشاف ألنمط والرؤية الحاسوبية. هذه الخوارزمية المقترحة هناك تقنيتين الستخراج خصائص ألصورة االولى بتطبيق خوارزمية التحويل على الصورة الكاملة والتقنية االخرى بتقسيم الصورة على اربعة اقسام. وتطبق خوارزمية التطبيق على كل جزء، وفي كل تقنية استعملت ثالث م، وتحويل والش، والتحويل كيكر المويجي).ولفهرسة الصور وٕايجاد التشابه خوارزميات للتحويل (التحويل الجيب تما استعملت معادلة االرتباط بين خصائص الصورة المستفهمة والصور في قاعدة البيانات. تعتمد طريقة االسترجاع على اعلى قيمة للفهرسة. ه نتائج افضل(معدل الدقة واالسترجاع اعلى)اوضحت نتائج التجربة ان تطبيق التحويل الجيب تمام على الصورة ل مقارنة بالخوارزميات االخرى المستعملة في هذا البحث وكذلك ان تقسيم الصورة على اربعة اقسام وتطبيق خوارزمية التحويل على كل جزء يحسن من اداء التقنية. ل االرتباط، التحويل الجيب تمام، تحويل استرجاع الصورة باستخدام المحتوى،استخالص الخواص، معامالكلمات المفتاحية: والش، التحويل كيكر المويجي.