GLCM_trying_with_FMM.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# to make this problem simple, we will use for loop while calculating."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "image = np.random.randint(0, 256, size=(1000, 1000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#leveling\n",
    "level = 3\n",
    "image = (image/(256/level)).astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# normal GLCM(2D-if-counting)\n",
    "# O(n^2)\n",
    "\n",
    "def GLCM_Normal(image, level = 3, distance = 2, angle = math.pi):\n",
    "    rows = image.shape[0]\n",
    "    cols = image.shape[1]\n",
    "    \n",
    "    row = int(round(np.sin(angle))) * distance\n",
    "    col = int(round(np.cos(angle))) * distance\n",
    "    \n",
    "    if col > 0:\n",
    "        subarray_1 = image[:rows-row, :cols-col]\n",
    "        subarray_2 = image[row:, col:]\n",
    "    else:\n",
    "        subarray_1 = image[:rows-row, -col:]\n",
    "        subarray_2 = image[row:, :cols+col]\n",
    "    \n",
    "    GLCM_Matrix = np.zeros(shape=(level, level))\n",
    "    \n",
    "    print(subarray_1.shape[0])\n",
    "    print(subarray_1.shape[1])\n",
    "    \n",
    "    for i in range(subarray_1.shape[0]):\n",
    "        for j in range(subarray_1.shape[1]):\n",
    "            left_value = subarray_1[i, j]\n",
    "            right_value = subarray_2[i, j]\n",
    "            \n",
    "            GLCM_Matrix[left_value, right_value] += 1\n",
    "    \n",
    "    return GLCM_Matrix\n",
    "            \n",
    "    \n",
    "        \n",
    "    \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000\n",
      "998\n",
      "CPU times: user 888 ms, sys: 6.76 ms, total: 895 ms\n",
      "Wall time: 894 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[ 112308.,  111622.,  111262.],\n",
       "       [ 111351.,  110154.,  110176.],\n",
       "       [ 111528.,  109873.,  109726.]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "GLCM_Normal(image)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Lagrange Version\n",
    "# O(n^2 * level^3)\n",
    "def GLCM_Lagrange(image, level = 3, distance = 2, angle = math.pi):\n",
    "    \n",
    "    # same as above\n",
    "    rows = image.shape[0]\n",
    "    cols = image.shape[1]\n",
    "    \n",
    "    row = int(round(np.sin(angle))) * distance\n",
    "    col = int(round(np.cos(angle))) * distance\n",
    "    \n",
    "    if col > 0:\n",
    "        subarray_1 = image[:rows-row, :cols-col]\n",
    "        subarray_2 = image[row:, col:]\n",
    "    else:\n",
    "        subarray_1 = image[:rows-row, -col:]\n",
    "        subarray_2 = image[row:, :cols+col]\n",
    "    \n",
    "    GLCM_Matrix = np.zeros(shape=(level, level))\n",
    "    \n",
    "    for i in range(subarray_1.shape[0]):\n",
    "        for j in range(subarray_1.shape[1]):\n",
    "            for k in range(level):\n",
    "                for l in range(level):\n",
    "                    #initial of results\n",
    "                    Left_result = 1\n",
    "                    Right_result = 1\n",
    "                    for m in range(level):\n",
    "                        if(k != m):\n",
    "                            Left_result *= (subarray_1[i, j]-m)/(k-m)\n",
    "                        if(l != m):\n",
    "                            Right_result *= (subarray_2[i, j]-m)/(l-m)\n",
    "                    \n",
    "                    result = Left_result*Right_result\n",
    "                    GLCM_Matrix[k, l] += result\n",
    "    \n",
    "    return GLCM_Matrix\n",
    "                \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 34.7 s, sys: 96.2 ms, total: 34.8 s\n",
      "Wall time: 34.9 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[ 112308.,  111622.,  111262.],\n",
       "       [ 111351.,  110154.,  110176.],\n",
       "       [ 111528.,  109873.,  109726.]])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "GLCM_Lagrange(image)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "圖上總共有$n^2$個數對，每個數對可能有$level^2$種不同情況，所以每個數對要跑$level^2$次Lagrange。\n",
    "\n",
    "以 $ f(0) = y_0, f(1) = y_1, ... ,f(level) = y_{level} $為例，單個Lagrange的運算是$O(level^2)$。\n",
    "\n",
    "（分數運算花一個level，再加上分數和$ y_i $的乘積和，再花一個level)\n",
    "\n",
    "而由於我們的y只有0跟1兩種結果，0的乘積自動為0，1也只有一項，所以本來就是$O(level)$的運算了，\n",
    "\n",
    "用 fast-multipole也不會比較快。\n",
    "\n",
    "\n",
    "這樣最後會是$O(n^2 * level^3)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "總的來說，這個做法比count慢的原因有兩個：\n",
    "\n",
    "1. 每個數對要檢查 $level^2$ 次\n",
    "2. 每個Lagrange要花 $level^1$ 的時間檢查。\n",
    "\n",
    "但如果矩陣夠大，level夠小，好像也沒關係(？)。"
   ]
  },
  {
   "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
}