Typical applications involving image retrieval processes demand a great amount of computation. The visual content of the images is extracted and represented by means of descriptor vectors of multidimensional characteristics. The image retrieval process consists of two tasks: (1) generation of database and indexing; and (2) the search process. The first task involves the construction of descriptor vectors. Then, an index is built upon the database to speed the search process. The second requires calculating a descriptor vector for the query image and computes the similarity search with the ones stored in the index. In this context, it is relevant to devise new algorithms and different parallel platforms that can reduce execution times. In particular, this work focuses on platforms with FPGAs based SoCs to present and evaluate a two stage system where the index is constructed off-line and the similarity search is executed on-line. Results show that the FPGA is 73% faster than a 2 Quad CPU to compute the descriptor vector of an image when using the Color Layout Descriptor of MPEG-7.
TopIntroduction
With the increasing growth of data new applications are developed which demand the use of data more complex than plain-text. Metric spaces have proven to be useful and practical for performing similarity search on very-large collections of complex objects. In this case, queries are objects of the same type of those stored in the database where, for example, one is interested in retrieving the k most similar objects to a given query. The similarity between any two objects is calculated by an application-dependent distance function, which is usually expensive to compute. For complex objects, like fingerprints or biologic components such as DNA and proteins, some authors claim that the distance function is even more expensive than plain disk accesses (Zezula et al., 2006).
Applications of image retrieval based on visual content are also known as Content based Image Retrieval systems (CBIR). CBIR systems can be modeled with metric spaces and imply basically two operations: a) visual descriptor calculations to characterize and describe the content of a query image and database images (the characteristic or descriptor vectors); and b) the similarity measure to select candidate images from the database (for the search process).
To describe the content of an image, at least one descriptor must be extracted from it. The color layout descriptor (CLD) of the MPEG-7 standard (Schafer, 1998), is widely used in the technical literature as a visual descriptor. It is an effective description for sketch-based retrieval, content filtering using image indexing, and visualization. When the CLD is used to represent an image, the first operation executed in a CBIR system involves different tasks like partitioning the image, computing expensive functions like the Discrete Cosine Transform (DCT) and changing the color space among others. Intra-query or intra-image parallelism is achieved when some of these tasks are executed in parallel, e.g. changing the color space requires computing three descriptor vectors which can be done in parallel for a single image. Moreover, inter-query or inter-image parallelism is also introduced when multiple images are processed to speed-up both the descriptor vectors construction and the similarity search process.
CBIR systems are used to implement images indexing and retrieval, widely used in bioscience, real-time content delivery systems such as security video cameras in an airport or biometric systems used in police control points, where it is critical to deal efficiently with streams of queries rather than with single queries and to reduce running time. Additionally, the operations executed by a CBIR system can significantly affect the performance of these systems as more images are added to the database because it invariably ends in longer response times. In that point, it is important to find efficient retrieval software and effective technologies to provide rapid query processing and hence High Performance Computing is required (HPC). In this regard, new technologies to support the development of embedded systems have been developed in the last decades offering very interesting characteristics such as low power consumption, parallel processing capacity, and reconfigurability, just to name a few of them. Programmable Logic Devices such FPGAs and Graphics Processing Units (GPU) are components that offer interesting and diverse characteristics from traditional CPU and whose integration into new computational model is a very interesting and challenging research field.
FPGAs were introduced by Ratha and Jain (1999) in computer vision applications as good candidates for HPC. FPGAs are inherently parallel devices that implement the required logic for a specific design building separated blocks in hardware for each function. They are also configurable devices that permit the hardware to be programmed multiple times after manufacture. The incorporation of programmable logic has been facilitated with the development of high level synthesis tools such as Catapult-C from Mentor Graphics, Vivado HLS from Xilinx, or Synphony from Synopsys. Moreover, successive Top500 lists have shown that machines that placed some hardware co-processor devices can provide significant improvement to many high performance applications.