Image & Kernel Indexing: Cross-Correlation vs Convolution

Indexing issues are a common point of misunderstanding and error when applying convolution and cross correlation to an image. Because of this, your company has compartmentalized the index selection process into a method findOperationIndexPairs(idx, n, opType) and has asked you to implement.

The method is passed three variables: idx, n, and opType.

idx: a tuple representing an x and y index into an image, of form (x, y). You can assume that the image has been properly padded and that idx is a point within the body of the image (no need to worry about edge conditions).

n: an integer representing the dimension of an n*n square filter/kernel being applied to the image.

opType: is a boolean representing the type of operation.

o True: Cross Correlation

o False: Convolution

Your method should return a single variable: indexPairs.

indexPairs: a list of pairs of tuples, where each pair represents the index into the image (first) and the index into the filter/kernel (second).

o Ex: [((x_img_0, y_img_0)(x_kernel_0, y_kernel_0)), , ((x_img_i, y_img_i)(x_kernel_i, y_kernel_i))]

Each pair of coordinates represents indices into the image and kernel that will be used to retrieve the values which will be multiplied and summed together in performance of the given operation. You are not expected to calculate the sum of these products, your methods should only return the correct indices so that later in the image processing pipeline another method can perform those functions. The size of your returned list depends on the size of the kernel, so for a kernel of size n, you will return a list of n*n pairs of coordinates.

It is fine to modify the input/output structure to work better with your language/development environment, as long as it implements the core functionality.

Please attach the code to your report and address the following:

Show the output for a 5x5 filter at image index of your choice, for cross-correlation and convolution.

Explain the outputs with respect to the formulation/equation of 2D cross-correlation and convolution.

Include a drawing/sketch of your indexing example for cross-correlation and convolution. For example, you could sketch the grid of the image and filter and use numbers or colors to indicate indexing.

Input: idx tuple, (x,y) index into a given inage - int, dimension of a square nen kernel - bool, represents operation type. True -> Cross Correlation, False -> Convolution op Type # Output: indexPairs - list of tuples, [[{x_ing, y_ing), (x_ker, y_ker)), - 1 def findOperation IndexPairs(idx, n, opType): indexPairs = [] #TODO: Implement method here return indexPairs Input: idx tuple, (x,y) index into a given inage - int, dimension of a square nen kernel - bool, represents operation type. True -> Cross Correlation, False -> Convolution op Type # Output: indexPairs - list of tuples, [[{x_ing, y_ing), (x_ker, y_ker)), - 1 def findOperation IndexPairs(idx, n, opType): indexPairs = [] #TODO: Implement method here return indexPairs