ECE 734 PROJECT PROPOSAL Implementing Memory and Run-Time Efficient Texture Classification using NVIDIA GPU, as a co-processor. Shreyas ParnerkarMotivation: Classification refers to as assigning a physical object or incident into one of a set of predefined categories. In texture classification the goal is to assign an unknown sample image to one of a set of known texture classes. Texture analysis is important in many applications of computer image analysis for classification or segmentation of images based on local spatial variations of intensity or color. Important applications include industrial and biomedical surface inspection, for example for defects and disease, ground classification and segmentation of satellite or aerial imagery, segmentation of textured regions in document analysis, and content-based access to image databases. However, a major problem is that textures in the real world are often not uniform, due to changes in orientation, scale or other visual appearance. In addition, the degree of computational complexity of many of the proposed texture measures is very high. The most successful methods for texture classification are through textons which are cluster centers in a feature space derived from the input. The feature space is built on the output of a filter bank. The process is computationally expensive since the images are convolved with large filter banks and in most cases requires clustering in high dimensional space. [1] LM filter bank results in a 48 dimensional feature space, while S filter bank results in a 13 dimensional feature space [1]. [1] proposes a new method for texture classification without the use of textons. Tuzel et al. use image intensities and norms of first and second order derivatives of intensities in both x and y direction for texture classification which results in a 5 dimensional feature space. Approach: The texture classification algorithm is usually divided into two phases namely training and testing. In the training phase, random square regions of random sizes are sampled from the training set of images and covariance matrices are calculated. Thus each texture image is represented with these covariance matrices. We form a set of such covariance matrices for all the texture images. This is again done for all classes of textures. In the testing phase again covariance matrices are computed for randomly selected regions from the test image and are compared with the covariance matrices using a distance metric. [3] gives a distance metric for Co-variance matrices. [1] and [2] propose that computing co-variance matrices using integral images is an efficient way of computing co-variance matrices compared to conventional histogram matching algorithm.Observations: [1] , [2] & [3] together combine to form a complete algorithm for texture classification. But the entire algorithm is not real time and is also a memory intensive implementation. The features that are extracted from each image form a 3 dimensional feature space. Fig 1 In order to obtain the last 4 values, first order and second order derivatives need to computed. This corresponds to the gradient and the Laplacian filtering. Further this feature space is used to compute the co-variance matrices using integral images resulting in 3 dimensional co-variance matrices. Though the co-variance matrices using integral images is an efficient way of computing [2], it still takes a large number of cycles in the range of 10^9 for a 256*256 pixel image and a search region of 32*32. The algorithm proposed in [2] is computationally intensive because of the highly nested loops. The calculation of co-variance matrices is done in both training and testing phase. Hence this part needs optimization both in terms of memory usage and the computation time in order to make it a real time algorithm. Algorithm: Calculation of P & Q Integral Images P --- Integral Image (3D): Dimensions = rows * columns * number of features (F)…… Fig 1 for x in 1 to rows for y in 1 to columns for index in 1 to featureLength for i in 1 to x for j in 1 to y P(x, y, index) = P(x, y, index) + F (i, j, index); end end end end end The algorithm for P and Q integral image calculations is an iterative algorithm and also has true dependencies because of cumulative additions (P integral image) and multiply and accumulate operations( Q integral images)Q --- Integral Image (4D): Dimensions = rows * columns * number of features (F)*number of features for x in 1 to rows for y in 1 to columns for index1 in 1 to featureLength for index2 in 1 to featureLength for i in 1 to x for j in 1 to y Q (x,y,index1,index2) = Q(x,y,index1,index2) + F(i, j,index1)*F(i, j, index2); end end end end end end Result of above algorithm: These P and Q matrices are then used for Co-Variance Matrices using the following formulae. [1] The region R as shown in figure 2 is selected from the image. The size of the region is varied and different Co-Variances are calculated, which helps in increasing the accuracy of Texture Classification. Fig 1. I implemented a sample version of the code in Matlab in order to estimate the execution time for the algorithm. The execution time is in tens of minutes. The algorithms clearly require a need to optimize the nested loop and the dependencies in the P & Q calculations in order to achieve considerable speed up. Fig2 Also very little work has been done on implementing texture classification algorithms on SIMT architectures in order to exploit parallelism.My Approach: 1. Optimizing integral image (histogram) calculation using techniques learnt in the class. The main emphasis will on usage of pipelining and parallel processing. For this, dependence graph for the nested loops will be analyzed in order to exploit possible parallelism. Along with this other techniques such as single assignment transformation, loop transformation, look-ahead transformation will be used to further enhance the parallel implementation. 2. Then after the algorithm reformulation, it will be implemented in Matlab in order to do the benchmarking for the runtime of the algorithm and the memory usage of the algorithm. 3. Further the
View Full Document
Unlocking...