convolve4d.py

import cv2
import numpy as np
import time
# Main20.py
# Stride = 2

wantDebug = False
wanthOut = False

def processImage(theimage):
  theimage = cv2.imread(theimage)
  theimage = cv2.cvtColor(src=theimage, code=cv2.COLOR_BGR2GRAY)
  return theimage

def convolve2D(image, kernel, padding=0, strides=1): # convolve2D(image, kernel)
    # Cross Correlation
    kernel = np.flipud(np.fliplr(kernel))

    # Gather Shapes of Kernel + Image + Padding
    yKernShape = kernel.shape[0]
    xKernShape = kernel.shape[1]

    yImgShape = image.shape[0]
    xImgShape = image.shape[1]

    # Shape of Output Convolution
    # yOutput = int(((yImgShape - yKernShape + 2 * padding) / strides) + 1)
    yOutput = int(((yImgShape - yKernShape + 2 * padding) / strides)) + 1
    xOutput = int(((xImgShape - xKernShape + 2 * padding) / strides)) + 1
    output = np.zeros((yOutput, xOutput))

    # Apply Equal Padding to All Sides
    if padding != 0:
        imagePadded = np.zeros((image.shape[1] + padding*2, image.shape[0] + padding*2))
        imagePadded[int(padding):int(-1 * padding), int(padding):int(-1 * padding)] = image
    else:
        imagePadded = image

    yImgPadded = yImgShape + padding*2
    xImgPadded = xImgShape + padding*2

    # Iterate through image
    counter = 0
    for y in range(imagePadded.shape[0]):   # y is row
        # Exit Convolution
        if y > imagePadded.shape[0] - yKernShape:
            break
        # Only Convolve if y has gone down by the specified Strides
        if y % strides == 0:
            for x in range(imagePadded.shape[1]):    # x is column
                # Go to next row once kernel is out of bounds
                if x > imagePadded.shape[1] - xKernShape:   # shape[1] adalah x atau column
                    break
                try:
                    # Only Convolve if x has moved by the specified Strides
                    if x % strides == 0:
                        yTemp = int(y/strides)
                        xTemp = int(x/strides)
                        hout = (kernel * imagePadded[y: y + yKernShape, x: x + xKernShape]).sum()
                        if wantDebug and 0:
                            print ("Position temp[{}, {}] = {}" .format(yTemp, xTemp, hout))
                        output[yTemp, xTemp] = (kernel * imagePadded[y: y + yKernShape, x: x + xKernShape]).sum()
                        counter = counter + 1
                except:
                    break
    # print ('Total loop convolve2D = {}'.format(counter))
    print(f"Total loop convolve2D = {counter:,}")
    return output

def createAKernelTile(size, aKernel, strides=1):
    # Input  : a matrix 2D. aKernel = (3x3)
    # Output : a matrix 2D. Strides = 1, aTileKernel = (9x9).   0, 3, 6
    #                       Strides = 2, aTilekernel = (11x11). 0, 4, 8
    if strides == 1:
        side = size * size
    elif strides == 2:
        side = size * size + strides

    arrTile = np.zeros((side, side))
    for row in range(size):
        if strides == 1:
            yTarget = row * size
        elif strides == 2:
            yTarget = row * size + row
        for col in range(size):
            if strides == 1:
                xTarget = col * size
            elif strides == 2:
                xTarget = col * size + col
            arrTile[yTarget:yTarget+size, xTarget:xTarget+size] = aKernel
    return arrTile

def convolve2DT4DS1(image, kernel, padding=0, strides=1):
    if wantDebug:
        print ("Padding = ", padding)
        print ("Strides = ", strides)

    # Cross Correlation
    kernel = np.flipud(np.fliplr(kernel))

    # Gather Shapes of Kernel + Image + Padding
    yKernShape = kernel.shape[0]
    xKernShape = kernel.shape[1]

    # Create aTile
    tileLength = xKernShape * xKernShape
    aTile = createAKernelTile(xKernShape, kernel, strides)

    yImgShape  = image.shape[0]
    xImgShape  = image.shape[1]

    # Apply Equal Padding to All Sides
    yReserve = yImgShape + padding*2 + tileLength
    xReserve = xImgShape + padding*2 + tileLength

    # Apply Equal Padding to All Sides
    if padding != 0:
        imagePadded = np.zeros((yReserve, xReserve))
        imagePadded[int(padding):int(-1 * padding)-tileLength, int(padding):int(-1 * padding)-tileLength] = image
    else:
        imagePadded = image

    yImgPadded = yImgShape + padding*2
    xImgPadded = xImgShape + padding*2

    # imageshape = 227, padding = 2
    # e.g. tileLength = 9 (from 3 x 3)
    #      imagePadded = 231x231 pixel. 231/9 = 25 blocks and remainder = 6 columns
    remainder = xImgPadded % tileLength
    if (remainder == 0):
        blocks = xImgPadded // tileLength  # 231 // 9 = 25 blocks remainder = 6
    else:
        blocks = (xImgPadded // tileLength) + 1  # One more tile length for remainder process
    total = (blocks * tileLength) + xKernShape
    # print ("Process {} blocks with total {} pixels".format(blocks, total))

    # Shape of Output Convolution
    yOutput = int(((yImgShape - yKernShape + 2 * padding) / strides) + 1)
    xOutput = int(((xImgShape - xKernShape + 2 * padding) / strides) + 1)
    temp = np.zeros((total, total))
    output = np.zeros((yOutput, xOutput))
    # print ('Output size = {} x {} '.format(yOutput, xOutput))

    yMax = yImgPadded - yKernShape - 1
    xMax = xImgPadded - xKernShape - 1

    counter = 0
    row = 0
    smallYCounter = 0
    switch = 0
    while row <= yMax:
        column = 0
        smallXCounter = 0
        while column <= xMax:
            # Take aBlock from imagePadded
            aBlock = imagePadded[row:row+tileLength, column:column+tileLength]
            hOut = aBlock * aTile # Hadamart
            # Convolution process is here
            for ySum in range(yKernShape):
                ySource = ySum * yKernShape
                for xSum in range(xKernShape):
                    xSource = xSum * xKernShape
                    temp[row+(ySum*yKernShape), column+(xSum*xKernShape)] = np.sum(hOut[ySource:ySource+yKernShape, xSource:xSource+xKernShape])
                    counter = counter + 1 # Just want know how many loop in total

            smallXCounter = smallXCounter + strides
            if smallXCounter >= xKernShape:
                smallXCounter = 0
                column = column + tileLength - xKernShape + strides**2 + (xKernShape - 3)
            else:
                column = column + strides

        smallYCounter = smallYCounter + strides
        if smallYCounter >= yKernShape:
            smallYCounter = 0
            row = row + tileLength - yKernShape + strides**2 + (yKernShape - 3)
        else:
            row = row + strides

    # Only outputSize are returned
    output = temp[0:yOutput, 0:xOutput]

    print(f"Total loop convolve2DT4D = {counter:,} with padding = {padding} and strides = {strides}")
    return output

def convolve2DT4DS2(image, kernel, padding=0, strides=2):
    if wantDebug:
        print ("Padding = ", padding)
        print ("Strides = ", strides)

    # Cross Correlation
    kernel = np.flipud(np.fliplr(kernel))

    # Gather Shapes of Kernel + Image + Padding
    yKernShape = kernel.shape[0]
    xKernShape = kernel.shape[1]

    # Create aTile
    tileLength = xKernShape * xKernShape
    aTile = createAKernelTile(xKernShape, kernel, strides)

    yImgShape  = image.shape[0]
    xImgShape  = image.shape[1]

    # Apply Equal Padding to All Sides
    yReserve = yImgShape + padding*2 + tileLength
    xReserve = xImgShape + padding*2 + tileLength

    # Apply Equal Padding to All Sides
    if padding != 0:
        imagePadded = np.zeros((yReserve, xReserve))
        imagePadded[int(padding):int(-1 * padding)-tileLength, int(padding):int(-1 * padding)-tileLength] = image
    else:
        imagePadded = image

    yImgPadded = yImgShape + padding*2
    xImgPadded = xImgShape + padding*2

    # imageshape = 227, padding = 2
    # e.g. tileLength = 9 (from 3 x 3)
    #      imagePadded = 231x231 pixel. 231/9 = 25 blocks and remainder = 6 columns
    remainder = xImgPadded % tileLength
    if (remainder == 0):
        blocks = xImgPadded // tileLength  # 231 // 9 = 25 blocks remainder = 6
    else:
        blocks = (xImgPadded // tileLength) + 1  # One more tile length for remainder process
    total = (blocks * tileLength) + xKernShape
    # print ("Process {} blocks with total {} pixels".format(blocks, total))

    # Shape of Output Convolution
    yOutput = int(((yImgShape - yKernShape + 2 * padding) / strides)) + 1
    xOutput = int(((xImgShape - xKernShape + 2 * padding) / strides)) + 1
    temp = np.zeros((total, total))
    output = np.zeros((yOutput, xOutput))
    # print ('Output size = {} x {} '.format(yOutput, xOutput))

    yMax = yImgPadded - yKernShape - 1
    xMax = xImgPadded - xKernShape - 1

    counter = 0
    row = 0
    smallYCounter = 0
    switch = 0
    while row <= yMax:
        column = 0
        smallXCounter = 0
        while column <= xMax:
            # Take aBlock from imagePadded
            aBlock = imagePadded[row:row+tileLength+strides, column:column+tileLength+strides]
            # hOut = aBlock * aTile
            hOut = aBlock * aTile
            if wantDebug and wanthOut:
                print ("Row = {}, Col = {}, hOut = \n {}".format(row, column, hOut))

            # Convolution process is here
            for ySum in range(yKernShape):
                # strides == 2:   # 0, 4, 8    2, 6, 10      12, 16, 20    14, 18, 22    24, 28, 32,    26, 30, 34 ...
                yTarget = int((row + (ySum * xKernShape) + ySum)/strides)
                ySource = (ySum * yKernShape) + ySum

                for xSum in range(xKernShape):
                    # strides == 2:   # 0, 4, 8    2, 6, 10      12, 16, 20    14, 18, 22    24, 28, 32,    26, 30, 34 ...
                    xTarget = int((column + (xSum * xKernShape) + xSum)/strides)
                    xSource = xSum * xKernShape + xSum

                    aBox  = hOut[ySource:ySource+yKernShape, xSource:xSource+xKernShape]
                    total = np.sum(hOut[ySource:ySource+yKernShape, xSource:xSource+xKernShape])
                    temp[yTarget, xTarget] = np.sum(hOut[ySource:ySource+yKernShape, xSource:xSource+xKernShape])

                    if wantDebug:
                        # print ("\nySource = {}, xSource = {}, \naBox = \n {}, \n Temp[{},{}] = {}".format(ySource, xSource, aBox, yTarget, xTarget, total))
                        print ("ySource = {}, xSource = {}, Temp[{},{}] = {}".format(ySource, xSource, yTarget, xTarget, total))
                    counter = counter + 1 # Just want know how many loop in total

            smallXCounter = smallXCounter + strides
            if smallXCounter >= xKernShape:
                smallXCounter = 0
                column = column + tileLength - xKernShape + strides**2 + (xKernShape - 3)
            else:
                column = column + strides

        smallYCounter = smallYCounter + strides
        if smallYCounter >= yKernShape:
            smallYCounter = 0
            row = row + tileLength - yKernShape + strides**2 + (yKernShape - 3)
        else:
            row = row + strides

    # Only outputSize are returned
    output = temp[0:yOutput, 0:xOutput]

    print(f"Total loop convolve2DT4D = {counter:,} with padding = {padding} and strides = {strides}")
    return output

if __name__ == '__main__':
    myimage = processImage('ikan416.jpeg')

    # Edge Detection Kernel 3x3
    kernel3 = np.array([[-1, -1, -1], [-1, 8, -1], [-1, -1, -1]])

    # Kernel 3x3 old Stride 1
    start_old_s1 = time.time()
    output_old_s1 = convolve2D(myimage, kernel3, padding=2, strides=1)
    end_old_s1 = time.time()
    cv2.imwrite('2DConvolved33_old_s1.jpg', output_old_s1)
    total1 = end_old_s1 - start_old_s1
    print('Process convolve2D old s1, 3x3 = {:5.3f} seconds'.format(total1))

    # Kernel 3x3 new Stride 1
    start_new_s1 = time.time()
    output_new_s1 = convolve2DT4DS1(myimage, kernel3, padding=2, strides=1)
    end_new_s1 = time.time()
    cv2.imwrite('4DConvolved33_new_s1.jpg', output_new_s1)
    total2 = end_new_s1 - start_new_s1
    print ('Process convolve2DT4DS1 new s1, 3x3 = {:5.3f} seconds'.format(total2))

    print ('Time saves = {:5.3f} seconds'.format(total1-total2))
    diff = output_old_s1 - output_new_s1
    print ('Differences 3x3 Stride 1 = ', diff.sum())
    print('========================\n')

    # Kernel 3x3 old Stride 2
    # start_old_s2 = time.time()
    # output_old_s2 = convolve2D(myimage, kernel3, padding=2, strides=2)
    # end_old_s2 = time.time()
    # cv2.imwrite('2DConvolved33_old_s2.jpg', output_old_s2)
    # total1 = end_old_s2 - start_old_s2
    # print('Process convolve2D old, s2, 3x3 = {:5.3f} seconds'.format(total1))
    #
    # # Kernel 3x3 new Stride 2
    # start_new_s2 = time.time()
    # output_new_s2 = convolve2DT4DS2(myimage, kernel3, padding=2, strides=2)
    # end_new_s2 = time.time()
    # cv2.imwrite('4DConvolved33_new_s2.jpg', output_new_s2)
    # total2 = end_new_s2 - start_new_s2
    # print ('Process convolve2DT4DS2 new s2, 3x3 = {:5.3f} seconds'.format(total2))
    #
    # print ('Time saves = {:5.3f} seconds'.format(total1-total2))
    # diff = output_old_s2 - output_new_s2
    # print ('Differences 3x3 Stride 2 = ', diff.sum())
    # print('========================\n')