tic-tac-toe-algorytm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import division\n",
    "\n",
    "import os\n",
    "import random as rnd\n",
    "\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "import skimage as ski\n",
    "from matplotlib import pylab as plt\n",
    "from pylab import *\n",
    "from skimage import exposure\n",
    "from skimage import img_as_float\n",
    "from skimage import io, filters\n",
    "from skimage import measure\n",
    "from skimage import restoration\n",
    "from skimage.color import rgb2gray\n",
    "from skimage.color import rgb2hed\n",
    "from skimage.morphology import remove_small_objects, convex_hull_image\n",
    "from skimage.transform import hough_line, hough_line_peaks, probabilistic_hough_line, hough_circle, hough_circle_peaks\n",
    "from skimage.feature import canny\n",
    "\n",
    "import cv2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prepare_img(img):\n",
    "    ihc_hed = rgb2hed(img) # zmiana na format hed w celu poprawy kontrastu\n",
    "    h = exposure.rescale_intensity(ihc_hed[:, :, 0], out_range=(0, 1))\n",
    "    d = exposure.rescale_intensity(ihc_hed[:, :, 2], out_range=(0, 1))\n",
    "    zdh = np.dstack((np.zeros_like(h), d, h)) # połaczenie wysokiego i niskiego kontrastu\n",
    "    tmp = rgb2gray(zdh)\n",
    "    p0_5, p99_5 = np.percentile(tmp, (0.5, 99.5))\n",
    "    tmp = exposure.rescale_intensity(tmp, (p0_5, p99_5)) # poprawa kontrastu według percentyli\n",
    "    tmp = filters.prewitt(tmp) \n",
    "    tmp = restoration.denoise_nl_means(tmp, h=0.95, fast_mode=True, patch_size=3, patch_distance=7, multichannel=False) # odszumieanie z użyciem średniej\n",
    "    return tmp\n",
    "\n",
    "\n",
    "def thresh_img(prepared_img):\n",
    "    try:\n",
    "        binary = (prepared_img > filters.threshold_minimum(prepared_img)) # progowanie oparte na metodzie minimum\n",
    "    except:\n",
    "        binary = (prepared_img > filters.threshold_mean(prepared_img)) # awaryjne progowanie dla przypadku jednoskośnego lub sbyt płaskiego histogramu\n",
    "    return binary\n",
    "\n",
    "\n",
    "def outline_img(img):\n",
    "    tmp = filters.prewitt(img)\n",
    "#     tmp_outline = filters.sobel(tmp)\n",
    "#     tmp_outline = canny(tmp)\n",
    "#     tmp_outline = sp.ndimage.binary_fill_holes(tmp_outline)\n",
    "#     tmp_outline = remove_small_objects(tmp_outline, 20 * 20)\n",
    "    return tmp\n",
    "\n",
    "\n",
    "def get_solidities_and_boundings(outlined_img):\n",
    "    outlines, count = sp.ndimage.label(outlined_img)\n",
    "    outlines = measure.regionprops(outlines) \n",
    "    solidities = []\n",
    "    boundings = []\n",
    "    for outline in outlines:\n",
    "        solidity  = outline.solidity\n",
    "        solidities.append(solidity)\n",
    "        x1, y1, x2, y2 = outline.bbox\n",
    "        boundings.append([(x1, y1), (x2, y2)])\n",
    "    return solidities, boundings\n",
    "        \n",
    "\n",
    "def find_game_areas(solidities_arr, boundings_arr):\n",
    "    solidities = np.array(solidities_arr)\n",
    "    boundings = np.array(boundings_arr)\n",
    "    game_areas = boundings[solidities < 0.35] # wartość wyznaczona empirycznie 24\n",
    "    return game_areas\n",
    "\n",
    "\n",
    "def resize_bounding_box(shape, game_area, resize_multiplier=1):\n",
    "    delta1 = int((game_area[1, 0] - game_area[0, 0])*(game_area[1, 0] - game_area[0, 0])/shape[0]) * int(resize_multiplier)\n",
    "    delta2 = int((game_area[1, 1] - game_area[0, 1])*(game_area[1, 1] - game_area[0, 1])/shape[1]) * int(resize_multiplier)\n",
    "    x1_d = game_area[0, 0] - delta1\n",
    "    x1 = x1_d if x1_d > 0 else 0\n",
    "    x2_d = game_area[1, 0] + delta1\n",
    "    x2 = x2_d if x2_d < shape[0] else shape[0]-1\n",
    "    y1_d = game_area[0, 1] - delta2\n",
    "    y1 = y1_d if y1_d > 0 else 0\n",
    "    y2_d = game_area[1, 1] + delta2\n",
    "    y2 = y2_d if y2_d < shape[1] else shape[1]-1\n",
    "    return x1, y1, x2, y2\n",
    "\n",
    "\n",
    "def find_lines(prep_img):\n",
    "    tested_angles = np.linspace(-np.pi / 2, np.pi / 2, 360)\n",
    "    h, theta, d = hough_line(prep_img, theta=tested_angles)\n",
    "    \n",
    "    _, angles, dists = hough_line_peaks(h, theta, d, threshold=0.5*max([max(h_n) for h_n in h]), min_distance=100)\n",
    "    return angles, dists\n",
    "\n",
    "def line_polar_to_cartesian(angles, dists):\n",
    "    x = np.array([0, 1])\n",
    "    lines_factors = []\n",
    "    for angle, dist in zip(angles, dists):\n",
    "        y0, y1 = (dist - x*np.cos(angle))/np.sin(angle)\n",
    "        a = (y0 - y1)/-1\n",
    "        b = y0\n",
    "        lines_factors.append([a, b])\n",
    "    lines_factors = np.array(lines_factors)\n",
    "    return lines_factors\n",
    "\n",
    "\n",
    "def equal(x0, x1, precision=0):\n",
    "    div = np.abs(x0 - x1)\n",
    "    return div <= precision\n",
    "\n",
    "\n",
    "# def count_dist(a, b, x, y):\n",
    "#     return np.absolute(a*x+y+b)/np.sqrt(a**2+1)\n",
    "\n",
    "\n",
    "def find_parallel_lines(angles, dists, prec):\n",
    "    parallel_lines = []\n",
    "    ln = angles.shape[0]\n",
    "    for i in range(ln-1):\n",
    "        ang_i = angles[i]\n",
    "        for j in range(i+1, ln):\n",
    "            ang_j = angles[j]\n",
    "            if (equal(ang_i, ang_j, prec)):\n",
    "                parallel_lines.append([[ang_i, dists[i]], [ang_j, dists[j]]])\n",
    "    parallel_lines = np.array(parallel_lines)\n",
    "    return parallel_lines\n",
    "\n",
    "\n",
    "def find_game_lines(parallel_lines, prec=0):\n",
    "    game_areas = []\n",
    "    ln = parallel_lines.shape[0]\n",
    "    for i in range(ln-1):\n",
    "        ang_1, dist_1 = parallel_lines[i, 0] \n",
    "        ang_2, dist_2 = parallel_lines[i, 1]\n",
    "        for j in range(i+1, ln):\n",
    "            ang_3, dist_3 = parallel_lines[j, 0]\n",
    "            ang_4, dist_4 = parallel_lines[j, 1]\n",
    "            if(equal(ang_1, np.pi-ang_3, prec) and equal(ang_2, np.pi-ang_4, prec) \n",
    "               and equal(ang_1, np.pi-ang_4, prec) and equal(ang_2, np.pi-ang_3, prec)):\n",
    "                game_areas.append([[ang_1, dist_1], [ang_2, dist_2], [ang_3, dist_3], [ang_4, dist_4]])\n",
    "    game_areas = np.array(game_areas)\n",
    "    return game_areas\n",
    "\n",
    "\n",
    "def get_lines_crossing(l1, l2):\n",
    "    a = np.array([[l1[0], -1], [l2[0], -1]])\n",
    "    b = np.array([-l1[1], -l2[1]])\n",
    "    point  = np.linalg.solve(a, b)\n",
    "    point_int = np.array([int(point[0]), int(point[1])])\n",
    "    return point_int\n",
    "\n",
    "\n",
    "def get_line_eq(p1, p2):\n",
    "    a = (p1[1] - p2[1])/(p1[0] - p2[0])\n",
    "    b = p1[1] - a*p1[0]\n",
    "    return (a, b)\n",
    "\n",
    "\n",
    "def line_func(x, a, b):\n",
    "    return a*x+b\n",
    "\n",
    "\n",
    "def get_mark(img):\n",
    "    tmp = sp.ndimage.binary_fill_holes(img.astype(int))\n",
    "    label, count = sp.ndimage.label(tmp)\n",
    "    region_prop = measure.regionprops(label)\n",
    "    if(len(region_prop)>0):\n",
    "        solidity = region_prop[0].solidity\n",
    "        if(solidity > 0.97):\n",
    "            return 'O'\n",
    "        else:\n",
    "            return 'X'\n",
    "    else:\n",
    "        return 'P'\n",
    "\n",
    "\n",
    "def count_dist(p0, p1):\n",
    "    dist = np.sqrt((p1[0] - p0[0])**2 + (p1[1] - p0[1])**2)\n",
    "    return dist\n",
    "    \n",
    "    \n",
    "def get_closest_ind(p0, points):\n",
    "    dist = np.inf\n",
    "    closest = 0\n",
    "    for i in range(len(points)):\n",
    "        tmp = count_dist(p0, points[i])\n",
    "        if (tmp < dist):\n",
    "            dist = tmp\n",
    "            closest = i\n",
    "    return closest\n",
    "   \n",
    "\n",
    "def find_minmax_vals(points):\n",
    "    x = []\n",
    "    y = []\n",
    "    for point in points:\n",
    "        x.append(point[0])\n",
    "        y.append(point[1])\n",
    "        \n",
    "    x_min = min(x)\n",
    "    x_max = max(x)\n",
    "    y_min = min(y)\n",
    "    y_max = max(y)\n",
    "    return [x_min, y_min, x_max, y_max]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dir = 'zdjęcia'\n",
    "dir_listed = os.listdir(dir)    # lista plików w folderze\n",
    "\n",
    "# dir_listed = ['IMG_6617.jpg']\n",
    "\n",
    "for img_name in dir_listed:\n",
    "    img = io.imread(os.path.join(dir, img_name))\n",
    "    fig, ax = subplots(figsize=(50, 100))\n",
    "    ax.imshow(img)\n",
    "    ax.set_axis_off()\n",
    "    plt.show()\n",
    "    prep_img = prepare_img(img)\n",
    "    threshed_img = thresh_img(prep_img)\n",
    "    labels, count = sp.ndimage.label(threshed_img)\n",
    "    region_props = measure.regionprops(labels)\n",
    "    centroids = []\n",
    "    solidities = []\n",
    "    boundings = []\n",
    "    for region_prop in region_props:\n",
    "        centroids.append(region_prop.centroid)\n",
    "        solidity  = region_prop.solidity\n",
    "        solidities.append(solidity)\n",
    "        x1, y1, x2, y2 = region_prop.bbox\n",
    "        boundings.append([(x1, y1), (x2, y2)])\n",
    "    games_areas = find_game_areas(solidities, boundings)\n",
    "    outlined_img = outline_img(threshed_img)\n",
    "    threshed_img_r = remove_small_objects(threshed_img, 30 * 30)\n",
    "    sh = outlined_img.shape\n",
    "    result_img = img\n",
    "    for game_area in games_areas:\n",
    "        x1, y1, x2, y2 = resize_bounding_box(sh, game_area)\n",
    "        temp_img = outlined_img[x1:x2, y1:y2]\n",
    "        part_img = img[x1:x2, y1:y2]\n",
    "        th_part = threshed_img_r[x1:x2, y1:y2]\n",
    "        angles, dists = find_lines(temp_img)\n",
    "        \n",
    "#         tmp_lines = line_polar_to_cartesian(angles, dists)\n",
    "#         fig, ax = subplots(figsize=(100, 50))\n",
    "\n",
    "#         ax.imshow(temp_img, cmap=plt.cm.gray)\n",
    "#         x = np.array([0, temp_img.shape[1]])\n",
    "#         for a, b in tmp_lines:\n",
    "#             ax.plot(x, line_func(x, a, b), \"r\")\n",
    "#         ax.axes.set_xlim(x)\n",
    "#         ax.set_ylim([temp_img.shape[0], 0])\n",
    "#         ax.set_axis_off()\n",
    "\n",
    "#         plt.show()\n",
    "        \n",
    "        \n",
    "        parallel_lines = find_parallel_lines(angles, dists, np.pi/5)\n",
    "        \n",
    "#         ax.imshow(temp_img, cmap=plt.cm.gray)\n",
    "#         x = np.array([0, temp_img.shape[1]])\n",
    "#         for lines in _lines:\n",
    "#             for a, b in lines:\n",
    "#                 ax.plot(x, line_func(x, a, b), \"r\")\n",
    "#         ax.axes.set_xlim(x)\n",
    "#         ax.set_ylim([temp_img.shape[0], 0])\n",
    "#         ax.set_axis_off()\n",
    "#         plt.show()\n",
    "        \n",
    "        game_lines = find_game_lines(parallel_lines, np.pi)\n",
    "        \n",
    "        for i in range(len(game_lines)):\n",
    "            for j in range(4):\n",
    "                ang, dist = game_lines[i, j]\n",
    "                a, b  = line_polar_to_cartesian([ang], [dist])[0]\n",
    "                game_lines[i, j] = [a, b]\n",
    "        \n",
    "        sh_tmp = temp_img.shape\n",
    "        fields = [] # obliecznie punktów centralnych pól planszy\n",
    "        try:\n",
    "            for game in game_lines:\n",
    "                central_field_corners = []\n",
    "                for i in range(2):\n",
    "                    for j in range(2, 4):\n",
    "                        crossing = get_lines_crossing(game[i], game[j])\n",
    "                        central_field_corners.append(crossing)\n",
    "\n",
    "                l1 = get_line_eq(central_field_corners[0], central_field_corners[3])\n",
    "                l2 = get_line_eq(central_field_corners[2], central_field_corners[1])\n",
    "                central_field = get_lines_crossing(l1, l2)\n",
    "\n",
    "                p1 = (central_field_corners[1] + central_field_corners[0])//2 # znajdujemy punkt na środku krawędzi pola centralnego\n",
    "                v = p1 - central_field # obliczamy wektor między środkiem centralnego pola, a środkiem jego krawędzi\n",
    "                f2 = p1 + v # \"przesuwamy\" pole na przybliżony środek pola skrajnego\n",
    "                # powyższe kroki powtarzamy dla pozostałych trzech pól mających wspólną krawędź z polem centralnym\n",
    "\n",
    "                p2 = (central_field_corners[3] + central_field_corners[2])//2\n",
    "                v = p2 - central_field\n",
    "                f6 = p2 + v\n",
    "\n",
    "                p3 = (central_field_corners[0] + central_field_corners[2])//2\n",
    "                v = p3 - central_field\n",
    "                f8 = p3 + v\n",
    "\n",
    "                p4 = (central_field_corners[3] + central_field_corners[1])//2\n",
    "                v = p4 - central_field\n",
    "                f4 = p4 + v\n",
    "\n",
    "                # obliczanie przybiżonych środków pól na skos od centralnego pola\n",
    "                v = central_field_corners[0] - central_field # obliczamy wektor mięszy środkiem pola centralnego a rogiem tego pola\n",
    "                f1 = central_field_corners[0] + v # \"przesuwamy\" pole o ten wektor uzyskując przybliżony środek pola\n",
    "\n",
    "                v = central_field_corners[1] - central_field\n",
    "                f3 = central_field_corners[1] + v\n",
    "\n",
    "                v = central_field_corners[3] - central_field\n",
    "                f5 = central_field_corners[3] + v\n",
    "\n",
    "                v = central_field_corners[2] - central_field\n",
    "                f7 = central_field_corners[2] + v\n",
    "\n",
    "                fields.append(f1)\n",
    "                fields.append(f2)\n",
    "                fields.append(f3)\n",
    "                fields.append(f4)\n",
    "                fields.append(f5)\n",
    "                fields.append(f6)\n",
    "                fields.append(f7)\n",
    "                fields.append(f8)\n",
    "                fields.append(central_field)\n",
    "        except:\n",
    "            continue\n",
    "            \n",
    "#         prep_part_img = prepare_img(part_img)\n",
    "#         outlined_part_img = thresh_img(prep_part_img)\n",
    "#         part_img_labels, part_img_count = sp.ndimage.label(outlined_part_img)\n",
    "        part_img_labels, part_img_count = sp.ndimage.label(th_part)\n",
    "        part_img_region_props = measure.regionprops(part_img_labels)\n",
    "        part_img_centroids = []\n",
    "        part_img_solidities = []\n",
    "        part_img_bbox_areas = []\n",
    "        part_img_boundings = []\n",
    "        for part_img_region_prop in part_img_region_props:\n",
    "            part_x1, part_y1, part_x2, part_y2 = part_img_region_prop.bbox\n",
    "            part_img_boundings.append([(part_x1, part_y1), (part_x2, part_y2)])\n",
    "            part_img_bbox_area = np.absolute(part_x2 - part_x1)*np.absolute(part_y2 - part_y1)\n",
    "            part_img_bbox_areas.append(part_img_bbox_area)\n",
    "            part_img_centroids.append(part_img_region_prop.centroid)\n",
    "            solidity  = part_img_region_prop.solidity\n",
    "            part_img_solidities.append(solidity)\n",
    "            \n",
    "        max_bbox_area = 0\n",
    "        max_ind = -100\n",
    "        for i in range(len(part_img_centroids)):\n",
    "            if(part_img_bbox_areas[i] > max_bbox_area):\n",
    "                max_bbox_area = part_img_bbox_areas[i]\n",
    "                max_ind = i\n",
    "                \n",
    "        if(max_ind != -100):\n",
    "            if max_ind < len(part_img_centroids):\n",
    "                part_img_bbox_areas = part_img_bbox_areas[:max_ind] + part_img_bbox_areas[max_ind+1:]\n",
    "                part_img_centroids = part_img_centroids[:max_ind] + part_img_centroids[max_ind+1:]\n",
    "                part_img_solidities = part_img_solidities[:max_ind] + part_img_solidities[max_ind+1:]\n",
    "                part_img_boundings = part_img_boundings[:max_ind] + part_img_boundings[max_ind+1:]\n",
    "            else:\n",
    "                part_img_bbox_areas = part_img_bbox_areas[:max_ind]\n",
    "                part_img_centroids = part_img_centroids[:max_ind]\n",
    "                part_img_solidities = part_img_solidities[:max_ind]\n",
    "                part_img_boundings = part_img_boundings[:max_ind]\n",
    "        \n",
    "        marks_on_fields = {}\n",
    "        for centroid, solidity, bounding in zip(part_img_centroids, part_img_solidities, part_img_boundings):\n",
    "            ind = get_closest_ind([centroid[1], centroid[0]], fields)\n",
    "            px1, py1 = bounding[0]\n",
    "            px2, py2 = bounding[1]\n",
    "            mark = get_mark(th_part[px1:px2, py1:py2])\n",
    "            marks_on_fields[str(ind)] = mark\n",
    "            \n",
    "            \n",
    "            \n",
    "        num = 1\n",
    "        for i in range(len(fields)):\n",
    "            if str(i) in marks_on_fields:\n",
    "                mark = marks_on_fields[str(i)]\n",
    "            else:\n",
    "                mark = 'P'\n",
    "#             cv2.putText(temp_img, str(num), (field[0], field[1]), cv2.FONT_HERSHEY_SIMPLEX, 1, (1.0), 2)\n",
    "            cv2.putText(part_img, str(num) + \":\" + mark, (fields[i][0], fields[i][1]), cv2.FONT_HERSHEY_SIMPLEX, 2, (255, 0, 0), 2)\n",
    "            num += 1\n",
    "            \n",
    "#         for centroid, bounding in zip(part_img_centroids, part_img_boundings):\n",
    "#             px1, py1 = bounding[0]\n",
    "#             px2, py2 = bounding[1]\n",
    "#             cv2.putText(part_img, get_mark(th_part[px1:px2, py1:py2]), (int(centroid[1]), int(centroid[0])), cv2.FONT_HERSHEY_SIMPLEX, 2, (0, 255, 0), 2)\n",
    "        \n",
    "        result_img[x1:x2, y1:y2] = part_img\n",
    "        \n",
    "#         for pairs in game_lines:\n",
    "#             fig, ax = subplots(figsize=(100, 50))\n",
    "\n",
    "#             ax.imshow(temp_img, cmap=plt.cm.gray)\n",
    "#             x = np.array([0, temp_img.shape[1]])\n",
    "#             for a, b in pairs:\n",
    "#                 ax.plot(x, line_func(x, a, b), \"r\")\n",
    "#             ax.axes.set_xlim(x)\n",
    "#             ax.set_ylim([temp_img.shape[0], 0])\n",
    "#             ax.set_axis_off()\n",
    "\n",
    "#             plt.show()\n",
    "        \n",
    "            \n",
    "    fig, ax = subplots(figsize=(50, 100))\n",
    "\n",
    "    ax.imshow(result_img)\n",
    "    ax.set_axis_off()\n",
    "\n",
    "    plt.show()"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}