Final_submission.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import cv2\n",
    "\n",
    "from PIL import Image\n",
    "from scipy.stats import norm\n",
    "from numba import jit\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "class Line:\n",
    "    def __init__(self, x1, y1, x2, y2, rho=None, theta=None):\n",
    "        self.x1 = x1\n",
    "        self.y1 = y1\n",
    "        self.x2 = x2\n",
    "        self.y2 = y2\n",
    "        self.rho = rho\n",
    "        self.theta = theta\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"Line(x1:{}, y1:{}, x2:{}, y2:{})\".format(self.x1, self.y1, self.x2, self.y2)\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"Line(x1:{}, y1:{}, x2:{}, y2:{})\".format(self.x1, self.y1, self.x2, self.y2)\n",
    "    \n",
    "    def extract(self):\n",
    "        return [[self.x1, self.y1], [self.x2, self.y2]]\n",
    "    \n",
    "    @staticmethod\n",
    "    def __intersection_point(line1, line2, _mode=None):\n",
    "        uan = (line2.x2-line2.x1)*(line1.y1-line2.y1)-(line2.y2-line2.y1)*(line1.x1-line2.x1)\n",
    "        ubn = (line1.x2-line1.x1)*(line1.y1-line2.y1)-(line1.y2-line1.y1)*(line1.x1-line2.x1)\n",
    "\n",
    "        denom = (line2.y2-line2.y1)*(line1.x2-line1.x1)-(line2.x2-line2.x1)*(line1.y2-line1.y1)\n",
    "\n",
    "        if _mode == 'intersect':\n",
    "            # intersecting lines\n",
    "            return not denom == 0\n",
    "        \n",
    "        elif _mode == 'parallel':\n",
    "            # parallel lines\n",
    "            return denom == 0\n",
    "        elif _mode == 'coincident':\n",
    "            # coincident lines:\n",
    "            return denom == uan == ubn == 0\n",
    "\n",
    "        if denom == 0:\n",
    "            raise Exception(\"{} and {} are parallel !\".format(line1, line2))\n",
    "\n",
    "        ua = uan/denom\n",
    "        ub = ubn/denom         \n",
    "\n",
    "        x = line1.x1 + ua * (line1.x2 - line1.x1)\n",
    "        y = line1.y1 + ua * (line1.y2 - line1.y1)\n",
    "\n",
    "        return np.int(np.round(x)), np.int(np.round(y))\n",
    "    \n",
    "    # intersect is used to determine if two lines, intersect each other.\n",
    "    @staticmethod\n",
    "    def intersect(line1, line2):\n",
    "        def _ccw(A,B,C):\n",
    "            return (C[1]-A[1]) * (B[0]-A[0]) > (B[1]-A[1]) * (C[0]-A[0])\n",
    "        \n",
    "        A, B = line1.extract()\n",
    "        C, D = line2.extract()\n",
    "\n",
    "        return _ccw(A,C,D) != _ccw(B,C,D) and _ccw(A,B,C) != _ccw(A,B,D)\n",
    "    \n",
    "    # intersect_beta is another method used to determine if two lines intersect each other.\n",
    "    @classmethod\n",
    "    def intersect_beta(cls, line1, line2):\n",
    "        return cls.__intersection_point(line1, line2, _mode='intersect')\n",
    "    \n",
    "    # parallel_beta is used to determine if two lines are parallel each other.\n",
    "    @classmethod\n",
    "    def parallel_beta(cls, line1, line2):\n",
    "        return cls.__intersection_point(line1, line2, _mode='parallel')\n",
    "    \n",
    "    # co_incident_beta is used to determine if two lines are coincidental.\n",
    "    @classmethod\n",
    "    def co_incident_beta(cls, line1, line2):\n",
    "        return cls.__intersection_point(line1, line2, _mode='coincident')\n",
    "\n",
    "    # get_intersection_point is used to determine the point of intersection of two lines. \n",
    "    @classmethod\n",
    "    def get_intersection_point(cls, line1, line2):\n",
    "        return cls.__intersection_point(line1, line2)\n",
    "    \n",
    "    \n",
    "class parallelogram:\n",
    "    def __init__(self, pgp1, pgp2):\n",
    "        x1, y1 = Line.get_intersection_point(pgp1[0], pgp2[0])\n",
    "        x2, y2 = Line.get_intersection_point(pgp1[0], pgp2[1])\n",
    "        x3, y3 = Line.get_intersection_point(pgp1[1], pgp2[0])\n",
    "        x4, y4 = Line.get_intersection_point(pgp1[1], pgp2[1])\n",
    "\n",
    "        self.co_ordinates = [(x1,y1), (x2,y2), (x3,y3), (x4, y4)]\n",
    "        \n",
    "        self.line1 = Line(x1, y1, x2, y2)\n",
    "        self.line3 = Line(x3, y3, x4, y4)\n",
    "        \n",
    "        # determines if the line fromed by these points are the diagonals of the parallelogram\n",
    "        if Line.intersect(Line(x1,y1,x3,y3), Line(x2,y2,x4,y4)):\n",
    "            self.line2 = Line(x1, y1, x4, y4)\n",
    "            self.line4 = Line(x2, y2, x3, y3)\n",
    "            \n",
    "        else:\n",
    "            self.line2 = Line(x1,y1,x3,y3)\n",
    "            self.line4 = Line(x2,y2,x4,y4)\n",
    "            \n",
    "    def extract(self):\n",
    "        return [self.line1, self.line2, self.line3, self.line4]\n",
    "\n",
    "    \n",
    "@jit\n",
    "def rgb2grey(image_array):\n",
    "    height, width, _ = image_array.shape\n",
    "    out_img = np.zeros(shape=(height, width), dtype=np.uint8)\n",
    "\n",
    "    for x in range(height):\n",
    "        for y in range(width):\n",
    "            r, g, b = image_array[x][y]\n",
    "            out_img[x][y] = np.uint8((0.3 * r) + (0.59 * g) + (0.11 * b))\n",
    "\n",
    "    return out_img\n",
    "\n",
    "\n",
    "# custom convolution operator. takes two arrays as input. the second array is considered to be the mask\n",
    "@jit\n",
    "def convolution(image_array, mask):\n",
    "    mk_height, mk_width = mask.shape\n",
    "    im_height, im_width = image_array.shape\n",
    "    out_img = np.zeros(shape=image_array.shape)\n",
    "\n",
    "    # offset is calculated to avoid the edges of the image. As a result, the size of the image decreases \n",
    "    _offset = mk_height // 2\n",
    "\n",
    "    for x in range(_offset, im_height - _offset):\n",
    "        for y in range(_offset, im_width - _offset):\n",
    "            # calculates the start and end position of the sliding window on the image.\n",
    "            imgx = x - mk_height // 2\n",
    "            imgy = y - mk_width // 2\n",
    "            \n",
    "            # compute the sum of the element by element product of the mask and sliding window\n",
    "            out_img[x][y] = np.sum(image_array[imgx: imgx + mk_height, imgy: imgy + mk_width] * mask)\n",
    "\n",
    "    return out_img[_offset: -_offset, _offset: -_offset]\n",
    "\n",
    "\n",
    "# custom gaussian filter. generates a gaussian mask of the specified size.\n",
    "@jit\n",
    "def gaussian_filter(image_array, size=11, sigma=3):\n",
    "    interval = (2 * sigma + 1.) / size\n",
    "    x = np.linspace(-sigma - interval / 2., sigma + interval / 2., size + 1)\n",
    "    kern1d = np.diff(norm.cdf(x))\n",
    "    kernel_raw = np.sqrt(np.outer(kern1d, kern1d))\n",
    "    kernel = kernel_raw / kernel_raw.sum()\n",
    "\n",
    "    return convolution(image_array, kernel)\n",
    "\n",
    "\n",
    "# custom median filter. the size of the neighborhood can be varied by the 'size' paramater\n",
    "@jit\n",
    "def median_filter(img_array, mask_size=5):\n",
    "    _offset = mask_size // 2\n",
    "    height, width = img_array.shape\n",
    "    out_img = np.zeros(shape=(height, width), dtype=np.uint8)\n",
    "\n",
    "    for x in range(_offset, height - _offset):\n",
    "        for y in range(_offset, width - _offset):\n",
    "            img_x = x - _offset\n",
    "            img_y = y - _offset\n",
    "            # finds the median value in the sliding window formed\n",
    "            out_img[x, y] = np.median(img_array[img_x: img_x + mask_size, img_y: img_y + mask_size])\n",
    "\n",
    "    return out_img[_offset:-_offset, _offset:-_offset]\n",
    "\n",
    "\n",
    "# method to compute the edge orientations by dividing the y_gradients by the x_gradients.\n",
    "@jit\n",
    "def get_edge_orientations(grad_y, grad_x):\n",
    "    angles = np.zeros(shape=grad_y.shape, dtype=np.float64)\n",
    "\n",
    "    for x in range(angles.shape[0]):\n",
    "        for y in range(angles.shape[1]):\n",
    "            # handles the potential divide by zero error if a particular x_gradient is 0\n",
    "            if grad_x[x][y] == 0:\n",
    "                angles[x][y] = 0 if grad_y[x][y] == 0 else 90\n",
    "            else:\n",
    "                angles[x][y] = np.rad2deg(np.arctan(grad_y[x][y] / grad_x[x][y]))\n",
    "\n",
    "    return angles\n",
    "\n",
    "\n",
    "# custom sobel operator. can perform thresholding or high pass filtering or neither.\n",
    "@jit\n",
    "def sobel(image_array, threshold=None, filter_mode=False):\n",
    "    mask_x = np.array([\n",
    "        [-1, 0, 1],\n",
    "        [-2, 0, 2],\n",
    "        [-1, 0, 1]\n",
    "    ])\n",
    "\n",
    "    mask_y = np.array([\n",
    "        [1, 2, 1],\n",
    "        [0, 0, 0],\n",
    "        [-1, -2, -1]\n",
    "    ])\n",
    "\n",
    "    # compute gradient x and gradient y.\n",
    "    gradient_x = convolution(image_array, mask_x)\n",
    "    gradient_y = convolution(image_array, mask_y)\n",
    "\n",
    "    # compute the edge orientations \n",
    "    angles = get_edge_orientations(gradient_y, gradient_x)\n",
    "\n",
    "    # compute the gradient magnitude\n",
    "    gradient = np.sqrt(np.square(gradient_x) + np.square(gradient_y))\n",
    "\n",
    "    # normalize the gradient magnitude\n",
    "    gradient *= 255 / np.max(gradient)\n",
    "\n",
    "    \n",
    "    if threshold is not None:\n",
    "        # high pass filter the gradient magnitude\n",
    "        gradient[gradient < threshold] = 0\n",
    "        \n",
    "        if not filter_mode:\n",
    "            # threshold the gradient magnitude\n",
    "            gradient[gradient >= threshold] = 255\n",
    "\n",
    "    return gradient, angles\n",
    "\n",
    "\n",
    "# calculate the sector of an angle for non maxima supression\n",
    "@jit\n",
    "def _quant(angle):\n",
    "    ang = angle % 180\n",
    "\n",
    "    if 22.5 <= ang < 67.5:\n",
    "        return 1\n",
    "    elif 67.5 <= ang < 112.5:\n",
    "        return 2\n",
    "    elif 112.5 <= ang < 157.5:\n",
    "        return 3\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "\n",
    "# assign a sector to every single pixel in the edge\n",
    "@jit\n",
    "def quantize(angles):\n",
    "    quants = np.zeros(shape=angles.shape, dtype=np.uint8)\n",
    "    for x in range(quants.shape[0]):\n",
    "        for y in range(quants.shape[1]):\n",
    "            quants[x][y] = _quant(angles[x][y])\n",
    "\n",
    "    return quants\n",
    "\n",
    "\n",
    "# performs non maxima supression\n",
    "@jit\n",
    "def nms(grads, angles):\n",
    "    quantized_angles = quantize(angles)\n",
    "    supressed_gradients = grads.copy()\n",
    "    \n",
    "    # sets the boundary pixels to zero to avoid calculation out of bounds of image.\n",
    "    supressed_gradients[:, 0] = 0\n",
    "    supressed_gradients[:, -1] = 0\n",
    "    supressed_gradients[0, :] = 0\n",
    "    supressed_gradients[-1, :] = 0\n",
    "\n",
    "    for x in range(1, supressed_gradients.shape[0] - 1):\n",
    "        for y in range(1, supressed_gradients.shape[1] - 1):\n",
    "            condition = [0, 0]\n",
    "            if quantized_angles[x][y] == 0:\n",
    "                condition[0] = grads[x][y - 1]\n",
    "                condition[1] = grads[x][y + 1]\n",
    "\n",
    "            elif quantized_angles[x][y] == 1:\n",
    "                condition[0] = grads[x - 1][y + 1]\n",
    "                condition[1] = grads[x + 1][y - 1]\n",
    "\n",
    "            elif quantized_angles[x][y] == 2:\n",
    "                condition[0] = grads[x + 1][y]\n",
    "                condition[1] = grads[x - 1][y]\n",
    "\n",
    "            else:\n",
    "                condition[0] = grads[x + 1][y - 1]\n",
    "                condition[1] = grads[x - 1][y + 1]\n",
    "\n",
    "            if not condition[0] < grads[x][y] > condition[1]:\n",
    "                supressed_gradients[x][y] = 0\n",
    "\n",
    "    return supressed_gradients\n",
    "\n",
    "\n",
    "# method to pad the boundary of an image with zeros. \n",
    "# used to restore an image to its original size after multiple convolution operations\n",
    "@jit\n",
    "def restore_size(image_array, target_shape):\n",
    "    pad_x_size, pad_y_size = target_shape[0] - image_array.shape[0], target_shape[1] - image_array.shape[1]\n",
    "\n",
    "    return np.pad(image_array, (pad_x_size // 2, pad_y_size // 2), 'constant', constant_values=0)\n",
    "\n",
    "\n",
    "# performs hough transform and returns the accumulator array, rho_values and theta_values. \n",
    "@jit\n",
    "def hough(img_array, angle_step=1):\n",
    "    height, width = img_array.shape\n",
    "\n",
    "    max_distance = np.int(np.ceil(np.sqrt(np.square(height) + np.square(width))))\n",
    "\n",
    "    # compute all possible values of rho and theta for the given precision\n",
    "    all_rhos = np.arange(-max_distance, max_distance)\n",
    "    all_thetas = np.radians(np.arange(-90, 90, angle_step))\n",
    "\n",
    "    # Initialize the accumulator array\n",
    "    accumulator = np.zeros((all_rhos.size, all_thetas.size), dtype=np.uint64)\n",
    "\n",
    "    # gives the indices of points with value > 0, that is, the edge points\n",
    "    edges = np.where(img_array > 0)\n",
    "\n",
    "    for x, y in zip(edges[0], edges[1]):\n",
    "        for index, theta in enumerate(all_thetas):\n",
    "            rho = np.int(np.round(y * np.cos(theta) + x * np.sin(theta))) + max_distance\n",
    "            accumulator[rho][index] += 1\n",
    "\n",
    "    return accumulator, all_rhos, all_thetas\n",
    "\n",
    "\n",
    "# finds the cartesian product of a set with itself. \n",
    "# used to generate the indices of the neighborhood pixels\n",
    "@jit\n",
    "def _cartesian_product(x):\n",
    "    return np.dstack(np.meshgrid(x, x)).reshape(-1, 2)\n",
    "\n",
    "\n",
    "# finds the peaks present in the accumulator array.\n",
    "# Can change the size of the comparison neighborhood for higher accuracy.\n",
    "@jit\n",
    "def hough_peaks(input_array, neighborhoodsize=1):\n",
    "    output = input_array.copy()\n",
    "    # find the indices of all points with value > 0.\n",
    "    peaks = np.where(input_array > 0)\n",
    "    # compute neighbours indicies for the given neighborhood size.\n",
    "    neighbours = _cartesian_product(np.arange(-neighborhoodsize, neighborhoodsize + 1))\n",
    "\n",
    "    for x, y in zip(peaks[0], peaks[1]):\n",
    "        # array used to store the value of the accumulator at each point of the neighborhood\n",
    "        max_pixel = np.zeros(neighbours.shape[0])\n",
    "        for index, xy in enumerate(neighbours):\n",
    "            if x + xy[0] < input_array.shape[0] and y + xy[1] < input_array.shape[1]:\n",
    "                max_pixel[index] = input_array[x + xy[0]][y + xy[1]]\n",
    "\n",
    "        # checks if value of current cell of accumulator array is equivalent\n",
    "        # to the maximal value in the current neighborhood\n",
    "        if input_array[x][y] != np.max(max_pixel):\n",
    "            output[x][y] = 0\n",
    "\n",
    "    return output\n",
    "\n",
    "\n",
    "# method used to draw a line on an image array. \n",
    "# can accept either a line object or two points.\n",
    "# variable thickness\n",
    "def draw_line(src_img, line=None, pt1=None, pt2=None, thickness=2):\n",
    "    img = src_img.copy()\n",
    "    if line: \n",
    "        cv2.line(img, (line.x1, line.y1), (line.x2, line.y2), (255,0,0), thickness)\n",
    "    else:\n",
    "        cv2.line(img, pt1, pt2, (255,0,0), thickness)\n",
    "    return img\n",
    "\n",
    "\n",
    "# method used to compute the co-ordinates of the end points of the lines detected by hough transform.\n",
    "@jit\n",
    "def retrieve_lines(accumulator_array, rhos, thetas):\n",
    "    peaks_locations = np.where(accumulator_array > 0)\n",
    "\n",
    "    x_peaks, y_peaks = peaks_locations\n",
    "\n",
    "    lines = []\n",
    "    for index, xy in enumerate(zip(x_peaks, y_peaks)):\n",
    "        x, y = xy\n",
    "        a = np.cos(thetas[y])\n",
    "        b = np.sin(thetas[y])\n",
    "        x0 = a * rhos[x]\n",
    "        y0 = b * rhos[x]\n",
    "        x1 = int(x0 - 1000 * b)\n",
    "        y1 = int(y0 + 1000 * a)\n",
    "        x2 = int(x0 + 1000 * b)\n",
    "        y2 = int(y0 - 1000 * a)\n",
    "    \n",
    "        lines.append(Line(x1, y1, x2, y2, rhos[x], thetas[y]))\n",
    "    \n",
    "    return lines\n",
    "\n",
    "\n",
    "# method used to divide the input lines into mutually parallel groups\n",
    "def make_lines_pairs(input_lines, leniency=5, merge=False ,_flag=False):\n",
    "    main = []\n",
    "    if merge and _flag:\n",
    "        angles = np.abs(np.array([np.degrees(each.theta) for each in input_lines]))\n",
    "    else:\n",
    "        angles = np.array([np.degrees(each.theta) for each in input_lines])\n",
    "        \n",
    "    for index in range(angles.size):\n",
    "        T = np.abs(angles - angles[index])\n",
    "        indicies = np.where(T <= leniency)\n",
    "        if indicies[0].size > 1:\n",
    "            main.append(indicies[0])\n",
    "    \n",
    "    # Merge groups in list main containing common items\n",
    "    iset = set([frozenset(s) for s in main])\n",
    "    result = []\n",
    "    while(iset):\n",
    "        nset = set(iset.pop())\n",
    "        check = len(iset)\n",
    "        while check:\n",
    "            check = False\n",
    "            for s in iset.copy():\n",
    "                if nset.intersection(s):\n",
    "                    check = True\n",
    "                    iset.remove(s)\n",
    "                    nset.update(s)\n",
    "        result.append(sorted(list(nset)))\n",
    "    \n",
    "    result.sort(key= lambda x:x[0])\n",
    "    \n",
    "    # Convert Indices stored in list main into line objects\n",
    "    main = []\n",
    "    for each_group in result:\n",
    "        temp = []\n",
    "        for each_line_index in each_group:\n",
    "            temp.append(input_lines[each_line_index])\n",
    "        main.append(temp)\n",
    "  \n",
    "    # merge positive and negative angles, within leniency range, into groups\n",
    "    if merge and not _flag:\n",
    "        temp = []\n",
    "        for each in main:\n",
    "            temp += each\n",
    "    \n",
    "        main = make_lines_pairs(temp, leniency, True, True)\n",
    "        \n",
    "    return main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# main method of the program. \n",
    "# Takes a dictionay object an input containing all the information like file names and threshold values.\n",
    "def detect_parallelograms(PARAMETERS, DEBUG=False):\n",
    "    # open the image.\n",
    "    test_img = Image.open(PARAMETERS['name'])\n",
    "    # convert image into an array\n",
    "    test_img_array = np.asarray(test_img)\n",
    "    # convert color image array into a greyscale image array\n",
    "    test_img_greyscale_array = rgb2grey(test_img_array)\n",
    "\n",
    "    # determine the order of the filters to be applied\n",
    "    if PARAMETERS['filter_order'] == 'gaussian then median':\n",
    "        # perform gaussian filtering first\n",
    "        filtered_img_array = gaussian_filter(test_img_greyscale_array, PARAMETERS['gaussian_filter_size'])\n",
    "        # perform median filtering second\n",
    "        filtered_img_array = median_filter(filtered_img_array, PARAMETERS['median_filter_size'])\n",
    "    \n",
    "    else:\n",
    "        # perform median filtering first\n",
    "        filtered_img_array = median_filter(test_img_greyscale_array, PARAMETERS['median_filter_size'])\n",
    "        # perform gaussian filtering second\n",
    "        filtered_img_array = gaussian_filter(filtered_img_array, PARAMETERS['gaussian_filter_size'])\n",
    "\n",
    "    # compute the edge gradient magnitudes and edge gradient angles by sobel operator.\n",
    "    test_img_edges, test_img_edge_angles = sobel(filtered_img_array, PARAMETERS['sobel_threshold'], filter_mode=True)\n",
    "    # supress the thick edges obtained by soble's operator\n",
    "    test_img_edges_suppressed = nms(test_img_edges, test_img_edge_angles)\n",
    "    # pad the boundary of the suppressed edges to match the original size of the input image\n",
    "    test_img_restored = restore_size(test_img_edges_suppressed, test_img_greyscale_array.shape)\n",
    "\n",
    "    # perform hough transform.\n",
    "    accumulator, rho_values, theta_values = hough(test_img_restored)\n",
    "    # threshold the hough accumulator array\n",
    "    accumulator[accumulator < PARAMETERS['hough_threshold']] = 0\n",
    "    # find the peaks present in the accumulator array\n",
    "    accumulator_peaks = hough_peaks(accumulator, PARAMETERS['hough_peaks_neighborhood_size'])\n",
    "\n",
    "    # find all lines detected by hough transform. Is a list containing several Line objects.\n",
    "    all_lines = retrieve_lines(accumulator_peaks, rho_values, theta_values)\n",
    "    # divide all the lines into smaller groups. ideally 2 groups\n",
    "    parallel_groups = make_lines_pairs(all_lines, leniency=PARAMETERS['parallel_lines_leniency'], merge=True)\n",
    "\n",
    "    group_1 = parallel_groups[0]\n",
    "    group_2 = parallel_groups[1]\n",
    "    # find every possbile combination of picking two lines in each group\n",
    "    all_pairs_group_1 = list(combinations(group_1, 2))\n",
    "    all_pairs_group_2 = list(combinations(group_2, 2))\n",
    "\n",
    "    # finding every possbile parallelogram that can be formed by by picking 2 lines from each group\n",
    "    all_possible_parallelograms = []\n",
    "    for each_group_1_pair in all_pairs_group_1:\n",
    "        for each_group_2_pair in all_pairs_group_2:\n",
    "            all_possible_parallelograms.append(parallelogram(each_group_1_pair, each_group_2_pair))\n",
    "\n",
    "    weighted_parallelograms = []\n",
    "    # copy of unsuppressed edge gradient\n",
    "    raw_edge_map = restore_size(test_img_edges, test_img_greyscale_array.shape)\n",
    "\n",
    "    for each_parallelogram in all_possible_parallelograms:\n",
    "        # generate a blank image array of the same size as the input image\n",
    "        blank_img = np.zeros(shape=test_img_restored.shape)\n",
    "\n",
    "        # draw the parallelogram on the blank image array\n",
    "        for each_line in each_parallelogram.extract():\n",
    "            blank_img = draw_line(blank_img, each_line, thickness=1)\n",
    "\n",
    "        # count the number of pixels / cells in the blank image array that is nonzero\n",
    "        parallelogram_perimeter = np.count_nonzero(blank_img)\n",
    "        # perform logical and of the blank image array and the unsupressed edge gradient\n",
    "        coincidence_value = np.count_nonzero(np.logical_and(blank_img, raw_edge_map))\n",
    "\n",
    "        # avoid a divide by zero error\n",
    "        if parallelogram_perimeter == 0:\n",
    "            continue\n",
    "\n",
    "        # compute the percentage of pixels of the parallelogram that lies on the detected edges of the image.\n",
    "        coincidence_percentage = coincidence_value / parallelogram_perimeter * 100\n",
    "\n",
    "        # threshold the parallelogram on the basis of the length of the perimeter and the coincidence percentage\n",
    "        if parallelogram_perimeter >= PARAMETERS['parallelogram_perimeter_threshold'] and coincidence_percentage > PARAMETERS['coincidence_percentage_threshold']:\n",
    "            weighted_parallelograms.append((np.round(coincidence_percentage), each_parallelogram, parallelogram_perimeter))\n",
    "\n",
    "    # sort the parallelograms that passed though the previous steps. \n",
    "    # first by coincidence percentage then by lenght of perimeter.\n",
    "    weighted_parallelograms.sort(key= lambda x: (x[0], x[2]), reverse=True)\n",
    "\n",
    "    # remove any duplicate parallelograms that may have been detected.\n",
    "    non_duplicates = []\n",
    "    pllgm_list = []\n",
    "    for each in weighted_parallelograms:\n",
    "        if each[2] not in non_duplicates:\n",
    "            non_duplicates.append(each[2])\n",
    "            pllgm_list.append(each)\n",
    "    weighted_parallelograms = pllgm_list\n",
    "\n",
    "    # draw all parallelograms that passed through the previous step, on top of the original image. \n",
    "    output = test_img_array.copy()\n",
    "    for index in range(len(weighted_parallelograms)):\n",
    "        for each_line in weighted_parallelograms[index][1].extract():\n",
    "            output = draw_line(output, each_line)\n",
    "\n",
    "    # save the image with the drawn parallelograms in the same directory if debug mode is not active.\n",
    "    if not DEBUG:\n",
    "        Image.fromarray(output).save(PARAMETERS['name'][:-4]+\"_detected_parallelograms.jpg\")\n",
    "    \n",
    "    # debug mode is used to save all the images that are obtained at every stage of the program.\n",
    "    if DEBUG:\n",
    "        from os import mkdir, chdir\n",
    "        try:\n",
    "            mkdir(PARAMETERS['name'][:-4] + \"_files\")\n",
    "        except FileExistsError:\n",
    "            pass\n",
    "        chdir(PARAMETERS['name'][:-4] + \"_files\")\n",
    "        \n",
    "        Image.fromarray(test_img_array).save(\"1_\" + PARAMETERS['name'][:-4] + \"_original.jpg\")\n",
    "        Image.fromarray(test_img_greyscale_array).convert('RGB').save(\"2_\" + PARAMETERS['name'][:-4] + \"_greyscale.jpg\")\n",
    "        Image.fromarray(filtered_img_array).convert('RGB').save(\"3_\" + PARAMETERS['name'][:-4] + \"_filtered.jpg\")\n",
    "        tresholded_edges, _ = sobel(filtered_img_array, PARAMETERS['sobel_threshold'])\n",
    "        Image.fromarray(tresholded_edges).convert('RGB').save(\"4_\" + PARAMETERS['name'][:-4] + \"_edge_magnitude.jpg\")\n",
    "        temp = test_img_edges_suppressed.copy()\n",
    "        temp[temp > 0] = 255\n",
    "        Image.fromarray(temp).convert('RGB').save(\"5_\" + PARAMETERS['name'][:-4] + \"_edge_magnitude_suppressed.jpg\")\n",
    "        temp = test_img_array.copy()\n",
    "        for each_line in all_lines:\n",
    "            temp = draw_line(temp, each_line)\n",
    "        Image.fromarray(temp).save(\"6_\" + PARAMETERS['name'][:-4] + \"_all_detected_lines.jpg\")\n",
    "        Image.fromarray(output).save(\"7_\" + PARAMETERS['name'][:-4]+\"_detected_parallelograms.jpg\")\n",
    "        with open(PARAMETERS['name'][:-4] + \"_parallelogram_co-ordinates.txt\", 'w') as file:\n",
    "            for index, each_parallelogram in enumerate(weighted_parallelograms):\n",
    "                file.write(\"Parallelogram #{} Co-ordinates: {}\\n\".format(index, each_parallelogram[1].co_ordinates))\n",
    "        chdir(\"..\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test_image_1_parameters = {\n",
    "    'name': 'TestImage1c.jpg',\n",
    "    'filter_order': 'median then gaussian',\n",
    "    'median_filter_size': 11,\n",
    "    'gaussian_filter_size': 11,\n",
    "    'sobel_threshold': 160,\n",
    "    'hough_threshold': 90,\n",
    "    'hough_peaks_neighborhood_size': 11,\n",
    "    'parallel_lines_leniency': 5,\n",
    "    'parallelogram_perimeter_threshold': 203,\n",
    "    'coincidence_percentage_threshold': 88.0\n",
    "}\n",
    "\n",
    "test_image_2_parameters = {\n",
    "    'name': 'TestImage2c.jpg',\n",
    "    'filter_order': 'gaussian then median',\n",
    "    'median_filter_size': 15,\n",
    "    'gaussian_filter_size': 9,\n",
    "    'sobel_threshold': 18,\n",
    "    'hough_threshold': 40,\n",
    "    'hough_peaks_neighborhood_size': 39,\n",
    "    'parallel_lines_leniency': 15,\n",
    "    'parallelogram_perimeter_threshold': 203,\n",
    "    'coincidence_percentage_threshold': 73.0\n",
    "}\n",
    "\n",
    "test_image_3_parameters = {\n",
    "    'name': 'TestImage3.jpg',\n",
    "    'filter_order': 'gaussian then median',\n",
    "    'median_filter_size': 5,\n",
    "    'gaussian_filter_size': 5,\n",
    "    'sobel_threshold': 20,\n",
    "    'hough_threshold': 63,\n",
    "    'hough_peaks_neighborhood_size': 9,\n",
    "    'parallel_lines_leniency': 5,\n",
    "    'parallelogram_perimeter_threshold': 203,\n",
    "    'coincidence_percentage_threshold': 93.25\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "detect_parallelograms(test_image_1_parameters, DEBUG=True)\n",
    "detect_parallelograms(test_image_2_parameters, DEBUG=True)\n",
    "detect_parallelograms(test_image_3_parameters, DEBUG=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}