Description
Problem Statement: In this assignment, you are required to use CUDA for parallel computation. You are not allowed to use any framework. Instead, work on CUDA (version CUDA 11) in C++. You will be given a Data RGB image (call it L) and a small query RGB image (call it Q). Your task is to locate the query image Q approximately in the data image L. Note that the query image Q need not be upright with respect to the data image L. There may be a rotated copy of query image Q in data image L. Thus, a match is specified by the X, Y row-column numbers of the lower-left corner of the query image Q in the data image L and its counter-clockwise rotation in degree of the base of query image Q. To simplify the problem, we will only rotate the query image from -45° to +45° in steps of 45°. Image coordinates are (0,0) on the lower left. The required output is a series of <X, Y, degree> triplets. Please note (X, Y) represents row number and column number from the bottom left of Data image L. The images will be passed as a text file. The first two space-separated integers would represent the number of rows (m) and the number of columns (n). Then m*n*3 space-separated integers will be given that would represent the coordinate at Image [i,j,k]. R G B R G B (M*N times) -> Reading row by row So for array A of m*n*3 integers, X[m-i-1,j,k] = A[i*n*3 + j*3 + k] (Indexing corrected as we consider bottom left of image as X[0,0,:]). That means it would read the image row by row from the top row to the bottom row and write each pixel as a triplet of R G B channel values. Pixel value that is X[i,j,k] lies in range [0,255] with integers value only. A perfect match is found if the pixels of the query image Q match the pixel values of the data image L exactly. Note that pixel coordinate <X, Y> of the query image may not have integer coordinates after rotation by d degrees. You compute the colour of non-integer pixel locations of an image using bilinear interpolation. Read bilinear interpolation. We use the interpolated data pixel to match against each query pixel in the case of a rotated query image. We are looking for similarity and not necessarily a perfect match. The similarity will be checked by the RMSD score. We will check if the RMSD (root mean square of the differences) between two images is less than some given threshold. One can read in detail about RMSD. RMSD is the root of the mean of the sum of squares of the difference between corresponding pixel values for each channel (R, G, B). If the image size is m*n*3 where 3 represents RGB channels, then RMSD is given by: The brute force method may be too time-consuming. One can always filter out the image on the basis of some basic condition. There are several filtering techniques. We will use a very simple one. Convert each image to grayscale by taking the grey value V to be (R+G+B)/3. Also, for filtering, we can compare with the upright bounding rectangle of the query image (as one can see a red square in the image below). In the case of the rotated query image, we use its axis-aligned bounding box in the data image to filter. Only if the average of all grey values of the bounding box image is within TH2 of the query image (rotated and interpolated), shall we check if the RMSD is within TH1. An image summary can be computed to represent areas of an image. If two images do not have a similar summary, they may be considered different enough and the detailed RMSD computation may not be necessary. In our case image summary would be the average of all pixel values means it would be an integer. Filtering method: In the above figure, each grid location stands for a pixel. The green rectangle represents the query image rotated by 40°. Its bottom-left corner (coordinate 0,0) is aligned with some pixel of the data image (represented by the upright grid). The filled green circle of the query image is compared with the interpolated value from the four dark-red data pixels. The average data grey-scale values in the bounding box marked in dark red are used for filtering. Any data pixel on the boundary of the bounding box is included in the average. Note: In the example above angle is given at 40 degrees. But for our testing, we will use only three angles -45, 0 and 45 degrees. Example: Data Image (L): Query Image (Q): For the above image, for n=1, the output triple would be (290,330,-45), given the data image size is (600*600) and the query image size is (80,80). One may notice that it is possible not to get integer coordinates, so bilinear interpolation is used to get approximate values. Evaluation Scheme: We will check the triplet outputs for each given data image, query image, threshold 1, threshold 2 and ‘n’. We will see if RMSD is within the threshold and is in top n. You will get full marks if you give the topmost match ( n=1). If you give top ‘n’, there is a 15% bonus. Deliverables ● A zip archive with the filename _.zip. On unzipping it should produce a directory with the name as your _ (all in caps). ● The directory should contain the make file, a bash file, and other files to run your code. Do not refrain from this format. ● First, we will run the make file. It should give executable. You are required to write a run.sh bash file which will take executable and arguments and write top ‘n’ triplets in output.txt. ● We will run bash file as follows: ./run.sh ● We will be using CUDA 11 in our HPC testing system. Please ensure it runs for our testing system.
