Parallel Implementation of Texture Based Image Retrieval on The GPU

Published Online July 2013 in MECS (http://www.

Image retrieval as one of the interesting applications of image processing is an appropriate case to be implemented in parallel. Because in this application, images are usually divided into several parts and each part is processed separately and similarly. The main process in image retrieval is to search images from a database based on low-level visual features such as color, texture, and shape. Typically, image retrieval systems extract features in the offline phase and use these features for matching in the online phase. For this, the visual contents of the images in the database are extracted and described by multi-dimensional feature vectors, which are more compressed and easier to process.

Content based image retrieval (CBIR) is a research area, which targets to develop tools for retrieval of visual information using it’s perceptual contents [1] and has been used for the first time by Kato et al. [2] to describe his experiments into automatic retrieval of images from a database.

CBIR uses the visual contents of an image such as color, shape and texture to represent and index the image. Color is one of the most widely used low-level visual features. Lu et al. [3] exploited the color distributions, the mean value and the standard deviation, to represent the global characteristics of the image, and the image bitmap is used to represent the local characteristics of the image for increasing the accuracy of the retrieval system. The most common method for color based image retrieval is the color histogram that describes the global color distribution in an image [4]. The main drawback of color histogram is that it only gives an overall indication of the color content of an image but does not provide information about the spatial distribution of the colors. Therefore two different images with similar color distribution can produce similar histograms. As tigers and cheetahs have same colors but different patterns, also using colour feature alone cannot distinguish between them [5]. As a result, Color features are less developed.

Object shape features can also provide powerful information for image retrieval, because humans can recognize objects solely from their shapes. Shape representation methods include Fourier descriptors, polygonal approximation, invariant moments, B-splines, deformable templates, and curvature scale space [6]. Region-based and boundary-based techniques (also known as contour-based approaches) are two primary methods of the shape description techniques [7]. The region-based methods consider the whole area of the object and often use moment descriptors such as geometrical moments, Zernike moments, pseudo-Zernike moments, and Legendre moments to describe shapes [8]. In fact, in region-based methods, shape descriptors utilize information from both boundaries and interior regions of the shape. This method is global in nature and can be applied to generic shapes, but they fail to distinguish between similar objects. The boundary based shape descriptors tend to be more efficient for handling shapes that are described by their object contours. The most common boundary-based shape descriptors are chain codes, Fourier descriptors, wavelet descriptors, and contour displacement [9]. Shape features are less developed than their color and texture counterparts because of the inherent complexity of representing shapes.

Several literature are reported for the purpose of texture based image retrieval, for example, Zhang et al. [10] extracted the rotation invariant texture feature extraction based on Gabor texture features by a circular shift of the feature elements so that all the images have the same dominant direction. Kokare et al. [11] applied Dual Tree Rotated Complex Wavelet Filter (DT-RCWF) and Dual Tree Complex Wavelet Transform (DT–CWT) for effective rotation invariant texture feature extraction. Pun [12] proposed a texture based image retrieval system using polar transform followed by an adaptive row shift invariant wavelet packet transform. The image retrieval system introduced in Huang et al. [13] is based on the wavelet decomposition and gradient vector. The system uses a coarse feature descriptor and a fine feature descriptor with each image. Both descriptors are extracted from the wavelet coefficients of the original image.

Entropy, standard deviation and local range are approaches for extraction of the texture features in images that can be efficient in image indexing. To extract texture feature, the image is divided into small non-overlapping image blocks. Each image block is processed similar to other image blocks. So in each image block, texture features are calculated independently. In fact, the same instruction is executed by multiple processors using different data streams (SIMD). Consequently these processes can be performed in parallel. To accelerate of texture feature extraction, multicore processors can be useful because of multithreading execution of programs.

Graphical Processors Units (GPUs) play important role to speedup processing of database images matching algorithms because it has more inbuilt execution cores [14]. Many researchers have already been applied GPUs to implement many algorithms in various areas such as image processing, computational geometry, and scientific computation, as well as computer graphics [15-18]. Parallel implementations on GPUs have been applied to various numerical problems [19-21] to reduce the computation time without sacrificing the degree of accuracy.

Compute Unified Device Architecture (CUDA) programming model released by NVIDIA provides a set of minimal extensions to the C programming language that allow the programmer to write kernels executed in parallel on the GPU [22]. In this paper, parallel implementation is performed for texture based image retrieval using CUDA to run on GPU.

The remainder of this paper is organized as follows. Section II, describes the GPU architecture. Section Ш, presents the proposed image retrieval procedure. Section W reports experimental results to evaluate the robustness and retrieval effectiveness of the proposed scheme. Finally, conclusion and future work are provided in Section V.

• II.    GPU ARCHITECTURE

In recent years, GPUs have become increasingly attractive for general purpose parallel computation [23]. Figure 1 illustrates the architecture of a GPU. A GPU has a series of Multiprocessors (MP), and each multiprocessor contains 8 Scalar Processors (SP). The memory bank of a MP can be accessed by all its SPs and a large global memory is shared across all the MPs [24]. CUDA is a parallel computing architecture developed by NVIDIA to implement algorithms in their GPUs. A typical CUDA program consists of a host code and a device code, where CPU and GPU are the host and the device respectively. The host performs the nonparallel computations and passes data to the global memory in the GPU and launches a kernel and data-parallel portions of an application are implemented as kernels. The kernel executes the computations using parallel threads on the SPs. The threads are grouped into blocks and blocks are grouped further into grids. A thread block is a 3, 2 or 1-dimensional group of threads. Threads within a block can cooperate among themselves by sharing data through some shared memory and synchronizing their execution to coordinate memory accesses. Threads in different blocks cannot cooperate. The number of threads per block is constrained by the limited memory resources of a processor core.

Figure 1. The NVIDIA GPU Architecture [24]

Due to the large amount of threads, CUDA introduces the concept of grid, block and thread to manage them. In a grid, blocks are managed in x-, y- and z-directions [25]. The dimensions of a grid are given by the variable gridDim, whose components are gridDim. x, gridDim.y and gridDim. z. The dimensions of a block are given by the variable blockDim, whose components are given as blockDim.x, blockDim.y and blockDim.z. The block index is given by blockIdx, which contains the components of blockIdx.x, blockIdex.y and blockIdx.z. So that threads are managed in a 3D way in a block and the thread index is given by threadIdx (threadIdx. x, threadIdx.y, threadIdx. z).

• III.    THE PROPOSED IMAGE RETRIEVAL PROCEDURE

Figure 2 shows the architecture of image retrieval system. The process of image retrieval consists of two tasks include indexing and retrieval. Features are the representatives of the images. Indexing means characterization of images based on image properties. The percentages of retrieval efficiency fully rely on selection of proper image features [26]. Two main requirements of image retrieval are high retrieval accuracy and less computational complexity. The image retrieval process consists of calculating a feature vector for characterizes some image properties, and stored in the image feature database. The user provides a query image, and the image retrieval system computes the feature vector for it, and compares it with the particular image feature database images. The relevance comparison is done by using some distance measurement technique, and the minimum or permissible distances are the metrics for the matched or similar images [27].

Content based image retrieval is defined as a process that searches and retrieves images from a large database on the features such as color, texture and shape. There are various methods which can be used for retrieval include entropy, standard deviation and local range. To characterize the sub-image and to extract the texture features, entropy, local range and standard deviation measures are used as performance parameters.

Texture = (Entropy + Standard deviation + Local Range)

Entropy is a statistical measure of randomness that can be used to characterize the texture of the input image. The value of entropy can be calculated using (1).

M

ENT = 2 P k log-1" (1) k - 1 P k

Where, ENT, M, and P are entropy, total number of samples, and probability of occurrences respectively. Standard deviation can be calculated using (2).

S -

n

2 ( X i - X )² i - 1

n

X =

2 x i i - 1

n

Where, n is number of elements in the sample. Local range is maximum value of chosen pixel-minimum value of chosen pixel. For texture image, entropy, standard deviation and local range are very compact representation features compared with other texture features. For creation of feature database above procedure is repeated for all the images of the image database and theses feature vectors are stored in feature database. If x and y are two d-dimensional feature vector database image and query image respectively, the Euclidean is calculated using (3).

^dE ⁽ x , У ) =

d

2 ⁽ xi ^- У г ⁾² i = 1

When a query image is submitted for image retrieval, its texture feature is extracted and matching operation is performed between query image features and the image features stored in database, the results closes to the query image is retrieved from the database.

Each Image is two-dimensional space that can be mapped to CUDA threads. There are 16 blocks in grid and also 64 threads in each block. So, for extract color features, each sub-image is mapped to one block and each image-block is processed by one thread. Therefore feature extraction is performed in all image-blocks in parallel by CUDA threads.

• IV.    EXPERIMENTAL RESULTS

The performance of retrieval of the system can be measured in terms of its recall and precision. Recall measures the ability of the system to retrieve all the models that are relevant, while precision measures the ability of the system to retrieve only the models that are relevant [28]. Precision and Recall are defined using (4) and (5).

A

Pr ecision = —

B

Re call = — C

That A is the number of relevant images retrieved, B is the total of images retrieved, and C is the total of relevant images. The average Precision for the images that belongs to the qth category (Aq) has been computed using (6).

AP =₂ pX! ₍₆₎ k ^E -Aq | A q |

We use MPEG-7 database which consists of 230 images that sample of MPEG-7 image database are shown in Figure 3. Each of the images is divided into small non-overlapping sub-images. The query and database image matching is done using Euclidian distance. The serial implementation of the image retrieval technique is done in C language using a PC with Intel Core 5 Pentium Processor (2.5GHz) and 4 GB RAM.

Figure 2. Architecture of CBIR systems

Figure 3. Sample of MPEG-7 image database

Parallel implementation obtained an average speed up of 140.046×over the serial implementation when running on a GPU named GeForce 610M. The GeForce 610M is an entry-level card with 48 CUDA cores and 900MHz core clock speed.

(a) Flower query, the top 4 retrieved images

(b) Mountain query, the top 4 retrieved images Figure 4. Two query response examples of the presented system

Figure 4 shows the results generated from the presented system that demonstrates the efficiency of this approach and have an average retrieval time as 7.5 seconds. These results show that the performance of the proposed method is better than the other methods. The average Precision and the average Recall of presented method are 39.6668% and 55% respectively. One graph that describes the performance of the system is the Precision-Recall graph. It provides a meaningful result when the database is known and has been used be some earlier systems.

Figure 5. The average Precision/Recall chart of the presented system number of retrieved images. Figure 5 shows the Precision-Recall graph. From the Figure, we notice that the system has good Precision results over the different values of Recall. The maximum average Precision of 100% at Recall value is 10%, and the Precision value decreases to 17.249% at 100% of Recall.

To evaluate our proposed system, we use each image in our database to be a query image and submit it to the system. We calculate the Precisions for each query in all classes. Then we take the average of all calculated Precisions as shown in Table I. Average Precision (AP) and Average Recall (AR) are in Table I. Texture based retrieval method of CBIR manages to find images similar to query image in database but with a drawback of a lot of time consumption. To make faster the method, we parallelized it on CUDA and achieved an average speed up of 140.046×(approx) over the serial implementation when running on a GPU.

TABLE I. P recision and recall of presented system

Recall (%)	Precision (%)
10	100
20	62.0691
30	46.8935
40	38.5588
50	32.3092
60	28.0463
70	26.2116
80	24.843
90	20.4881
100	17.249
AR = 55%	AP = 39.6668%

The comparison of serial implementation over parallel is shown in Table II. Table II also shows that execution time depends on the image resolution for 1000 time iterations, with the optimized code. This Table reports the speed up and the speed up average for varying the problem sizes.

TABLE II. execusion time serial over parallel

IMPLEMENTATION

Resolution (a×a)	CPU Runtime [s]	GPU Runtime [s]	Speed up	Speed up Average
300	536.693	8.5	63.14	140.046
400	953.232	7.92	120.35
500	1490.925	6.3	236.65

V. CONCLUSION AND FUTURE WORK

To evaluate our presented system, we use the Precision-Recall graph. We select all images from each class in the database to use them as queries to calculate the Precision and Recall. For each image, the Precision of the retrieval result is obtained by increasing the

In this paper, parallel implementation was performed for texture based image retrieval using CUDA programming model to run on GPU. The presented method provides low computational complexity and high retrieval accuracy. Experimental result showed that in the presented method, there is an increase in the retrieval speed and showed that parallel implementation obtained an average speed up of 140.046×over the serial implementation. Large color database of 230 images were used for check the retrieval performance. Our method was evaluated using Precision, Recall, and average Precision measures. The average Precision and the average Recall of presented method were calculated 39.6668% and 55% respectively.

In Further, the work can be extended for translation, rotation, and scale invariance texture representation, so that the retrieval efficiency can be further increased and we can develop a system that combines the texture, shape, and spatial features with the color feature to represent the image. This will give good results