Encoding_decoding.ipynb 24.8 KB
Newer Older
Kelly Chang's avatar
Kelly Chang committed
1 2 3 4
{
 "cells": [
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
5
   "execution_count": 1,
Kelly Chang's avatar
Kelly Chang committed
6 7 8 9 10 11 12 13 14 15 16
   "id": "14f74f21",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "from itertools import product\n",
    "import os\n",
    "import sys\n",
    "from PIL import Image\n",
    "from scipy.optimize import minimize,linprog\n",
17 18
    "# import time\n",
    "# import seaborn as sns\n",
Kelly Chang's avatar
Kelly Chang committed
19
    "from sklearn.neighbors import KernelDensity\n",
20
    "# import pandas as pd\n",
Kelly Chang's avatar
Kelly Chang committed
21
    "from collections import Counter\n",
Kelly Chang's avatar
Kelly Chang committed
22
    "import numpy.linalg as la"
Kelly Chang's avatar
Kelly Chang committed
23 24 25 26
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
27
   "execution_count": 2,
Kelly Chang's avatar
Kelly Chang committed
28 29 30 31 32 33 34 35
   "id": "c16af61f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def file_extractor(dirname=\"images\"):\n",
    "    files = os.listdir(dirname)\n",
    "    scenes = []\n",
    "    for file in files:\n",
Kelly Chang's avatar
Kelly Chang committed
36 37 38 39
    "        if file == '.DS_Store':\n",
    "            continue\n",
    "        else:\n",
    "            scenes.append(os.path.join(dirname, file))\n",
Kelly Chang's avatar
Kelly Chang committed
40 41 42 43 44 45 46
    "    return scenes\n",
    "\n",
    "def image_extractor(scenes):\n",
    "    image_folder = []\n",
    "    for scene in scenes:\n",
    "        files = os.listdir(scene)\n",
    "        for file in files:\n",
Kelly Chang's avatar
Kelly Chang committed
47 48 49 50 51
    "            if file[-5:] != \".tiff\" or file[-7:] == \"_6.tiff\":\n",
    "                continue\n",
    "            else:\n",
    "                image_folder.append(os.path.join(scene, file))\n",
    "    return image_folder #returns a list of file paths to .tiff files in the specified directory given in file_extractor\n",
Kelly Chang's avatar
Kelly Chang committed
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
    "\n",
    "def im_distribution(images, num):\n",
    "    \"\"\"\n",
    "    Function that extracts tiff files from specific cameras and returns a list of all\n",
    "    the tiff files corresponding to that camera. i.e. all pictures labeled \"_7.tiff\" or otherwise\n",
    "    specified camera numbers.\n",
    "    \n",
    "    Parameters:\n",
    "        images (list): list of all tiff files, regardless of classification. This is NOT a list of directories but\n",
    "        of specific tiff files that can be opened right away. This is the list that we iterate through and \n",
    "        divide.\n",
    "        \n",
    "        num (str): a string designation for the camera number that we want to extract i.e. \"14\" for double digits\n",
    "        of \"_1\" for single digits.\n",
    "        \n",
    "    Returns:\n",
    "        tiff (list): A list of tiff files that have the specified designation from num. They are the files extracted\n",
    "        from the 'images' list that correspond to the given num.\n",
    "    \"\"\"\n",
    "    tiff = []\n",
    "    for im in images:\n",
    "        if im[-7:-5] == num:\n",
    "            tiff.append(im)\n",
    "    return tiff"
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
80
   "execution_count": 3,
Kelly Chang's avatar
Kelly Chang committed
81
   "id": "53786325",
Kelly Chang's avatar
Kelly Chang committed
82 83 84
   "metadata": {},
   "outputs": [],
   "source": [
85
    "def predict_pix(tiff_image_path, difference = True):\n",
Kelly Chang's avatar
Kelly Chang committed
86
    "    \"\"\"\n",
Kelly Chang's avatar
Kelly Chang committed
87 88 89 90 91 92 93 94 95 96
    "    This function predict the pixel values excluding the boundary.\n",
    "    Using the 4 neighbor pixel values and MSE to predict the next pixel value\n",
    "    (-1,1) (0,1) (1,1)  => relative position of the 4 other given values\n",
    "    (-1,0) (0,0)        => (0,0) is the one we want to predict\n",
    "    take the derivative of mean square error to solve for the system of equation \n",
    "    A = np.array([[3,0,-1],[0,3,3],[1,-3,-4]])\n",
    "    A @ [a, b, c] = [-z0+z2-z3, z0+z1+z2, -z0-z1-z2-z3] where z0 = (-1,1), z1 = (0,1), z2 = (1,1), z3 = (-1,0)\n",
    "    and the predicted pixel value is c.\n",
    "    \n",
    "    Input:\n",
97
    "    tiff_image_path (string): path to the tiff file\n",
Kelly Chang's avatar
Kelly Chang committed
98
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
99
    "    Return:\n",
100 101 102 103 104 105
    "    image   ndarray(512 X 640): original image \n",
    "    predict ndarray(325380,): predicted image excluding the boundary\n",
    "    diff.   ndarray(325380,): IF difference = TRUE, difference between the min and max of four neighbors exclude the boundary\n",
    "                            ELSE: the residuals of the four nearest pixels to a fitted hyperplane\n",
    "    error   ndarray(325380,): difference between the original image and predicted image\n",
    "    A       ndarray(3 X 3): system of equation\n",
Kelly Chang's avatar
Kelly Chang committed
106
    "    \"\"\"\n",
107 108 109
    "    image_obj = Image.open(tiff_image_path)    #Open the image and read it as an Image object\n",
    "    image_array = np.array(image_obj)[1:,:].astype(int)    #Convert to an array, leaving out the first row because the first row is just housekeeping data\n",
    "    # image_array = image_array.astype(int) \n",
Kelly Chang's avatar
Kelly Chang committed
110
    "    A = np.array([[3,0,-1],[0,3,3],[1,-3,-4]]) # the matrix for system of equation\n",
Kelly Chang's avatar
Kelly Chang committed
111
    "    # where z0 = (-1,1), z1 = (0,1), z2 = (1,1), z3 = (-1,0)\n",
112 113 114 115
    "    z0 = image_array[0:-2,0:-2]   # get all the first pixel for the entire image\n",
    "    z1 = image_array[0:-2,1:-1]   # get all the second pixel for the entire image\n",
    "    z2 = image_array[0:-2,2::]    # get all the third pixel for the entire image\n",
    "    z3 = image_array[1:-1,0:-2]   # get all the forth pixel for the entire image\n",
Nathaniel Callens's avatar
Nathaniel Callens committed
116
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
117 118 119 120 121
    "    # calculate the out put of the system of equation\n",
    "    y0 = np.ravel(-z0+z2-z3)\n",
    "    y1 = np.ravel(z0+z1+z2)\n",
    "    y2 = np.ravel(-z0-z1-z2-z3)\n",
    "    y = np.vstack((y0,y1,y2))\n",
Nathaniel Callens's avatar
Nathaniel Callens committed
122
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
123
    "    # use numpy solver to solve the system of equations all at once\n",
Kelly Chang's avatar
Kelly Chang committed
124 125
    "    #predict = np.floor(np.linalg.solve(A,y)[-1])\n",
    "    predict = np.round(np.round((np.linalg.solve(A,y)[-1]),1))\n",
Kelly Chang's avatar
Kelly Chang committed
126 127 128 129
    "    \n",
    "    #Matrix system of points that will be used to solve the least squares fitting hyperplane\n",
    "    points = np.array([[-1,-1,1], [-1,0,1], [-1,1,1], [0,-1,1]])\n",
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
130 131 132 133 134 135
    "    # flatten the neighbor pixlels and stack them together\n",
    "    z0 = np.ravel(z0)\n",
    "    z1 = np.ravel(z1)\n",
    "    z2 = np.ravel(z2)\n",
    "    z3 = np.ravel(z3)\n",
    "    neighbor = np.vstack((z0,z1,z2,z3)).T\n",
Kelly Chang's avatar
Kelly Chang committed
136 137 138 139 140 141 142 143 144
    "    \n",
    "    if difference:\n",
    "        # calculate the difference\n",
    "        diff = np.max(neighbor,axis = 1) - np.min(neighbor, axis=1)\n",
    "    \n",
    "    else:\n",
    "        #Compute the best fitting hyperplane using least squares\n",
    "        #The res is the residuals of the four points used to fit the hyperplane (summed distance of each of the \n",
    "        #points to the hyperplane), it is a measure of gradient\n",
145
    "        f, diff, rank, s = la.lstsq(points, neighbor.T, rcond=None)\n",
Kelly Chang's avatar
Kelly Chang committed
146 147
    "        diff = diff.astype(int)\n",
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
148
    "    # calculate the error\n",
149
    "    error = np.ravel(image_array[1:-1,1:-1])-predict\n",
Kelly Chang's avatar
Kelly Chang committed
150
    "    \n",
151
    "    return image_array, predict, diff, error, A"
Kelly Chang's avatar
Kelly Chang committed
152 153 154 155
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
156
   "execution_count": 4,
Kelly Chang's avatar
Kelly Chang committed
157 158 159 160
   "id": "6b965751",
   "metadata": {},
   "outputs": [],
   "source": [
Kelly Chang's avatar
Kelly Chang committed
161
    "\"\"\"\n",
162
    "this huffman encoding code is found online\n",
Kelly Chang's avatar
Kelly Chang committed
163 164 165
    "https://favtutor.com/blogs/huffman-coding\n",
    "\"\"\"\n",
    "\n",
Kelly Chang's avatar
Kelly Chang committed
166 167 168 169 170 171 172 173 174
    "class NodeTree(object):\n",
    "    def __init__(self, left=None, right=None):\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def children(self):\n",
    "        return self.left, self.right\n",
    "\n",
    "    def __str__(self):\n",
175
    "        return self.left, self.right\n",
Kelly Chang's avatar
Kelly Chang committed
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202
    "\n",
    "\n",
    "def huffman_code_tree(node, binString=''):\n",
    "    '''\n",
    "    Function to find Huffman Code\n",
    "    '''\n",
    "    if type(node) is str:\n",
    "        return {node: binString}\n",
    "    (l, r) = node.children()\n",
    "    d = dict()\n",
    "    d.update(huffman_code_tree(l, binString + '0'))\n",
    "    d.update(huffman_code_tree(r, binString + '1'))\n",
    "    return d\n",
    "\n",
    "\n",
    "def make_tree(nodes):\n",
    "    '''\n",
    "    Function to make tree\n",
    "    :param nodes: Nodes\n",
    "    :return: Root of the tree\n",
    "    '''\n",
    "    while len(nodes) > 1:\n",
    "        (key1, c1) = nodes[-1]\n",
    "        (key2, c2) = nodes[-2]\n",
    "        nodes = nodes[:-2]\n",
    "        node = NodeTree(key1, key2)\n",
    "        nodes.append((node, c1 + c2))\n",
Bryce Hepner's avatar
Bryce Hepner committed
203
    "        #reverse True, decending order\n",
204 205 206 207
    "\n",
    "        #There is a huge memory leak here, no idea how or why\n",
    "        nodes = sorted(nodes, key=lambda x: x[1], reverse=True)\n",
    "    return nodes[0][0]"
Kelly Chang's avatar
Kelly Chang committed
208 209 210 211
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
212
   "execution_count": 5,
Kelly Chang's avatar
Kelly Chang committed
213 214 215 216
   "id": "b7561883",
   "metadata": {},
   "outputs": [],
   "source": [
217
    "def huffman(tiff_image_path, num_bins=4, difference = True):\n",
Kelly Chang's avatar
Kelly Chang committed
218 219 220 221 222
    "    \"\"\"\n",
    "    This function is used to encode the error based on the difference\n",
    "    and split the difference into different bins\n",
    "    \n",
    "    Input:\n",
223 224
    "    tiff_image_path     (string): path to the tiff file\n",
    "    num_bins            (int): number of bins\n",
Kelly Chang's avatar
Kelly Chang committed
225 226
    "    \n",
    "    Return:\n",
227 228 229 230 231 232 233 234
    "    huffman_encoding_list  list    (num_bins + 1): a list of dictionary\n",
    "    image_array            ndarray (512, 640): original image\n",
    "    new_error              ndarray (512, 640): error that includes the boundary\n",
    "    diff                   ndarray (510, 638): difference of min and max of the 4 neighbors\n",
    "    boundary               ndarray (2300,): the boundary values after subtracting the very first pixel value\n",
    "    predict                ndarray (325380,): the list of predicted values\n",
    "    bins                   list    (num_bins - 1,): a list of threshold to cut the bins\n",
    "    A                      ndarray (3 X 3): system of equation\n",
Kelly Chang's avatar
Kelly Chang committed
235 236
    "    \n",
    "    \"\"\"\n",
237 238
    "    # get the image_array, etc\n",
    "    image_array, predict, diff, error, A = predict_pix(tiff_image_path, difference)\n",
Kelly Chang's avatar
Kelly Chang committed
239
    "    \n",
240
    "    # calculate the number of points that will go in each bin\n",
241 242
    "    data_points_per_bin = diff.size // num_bins\n",
    "\n",
Kelly Chang's avatar
Kelly Chang committed
243
    "    # sort the difference and create the bins\n",
244
    "    sorted_diff = np.sort(diff.copy())\n",
Kelly Chang's avatar
Kelly Chang committed
245 246 247
    "    bins = [sorted_diff[i*data_points_per_bin] for i in range(1,num_bins)]\n",
    "    \n",
    "    # get the boundary \n",
248
    "    boundary = np.hstack((image_array[0,:],image_array[-1,:],image_array[1:-1,0],image_array[1:-1,-1]))\n",
Kelly Chang's avatar
Kelly Chang committed
249 250
    "    \n",
    "    # take the difference of the boundary with the very first pixel\n",
251
    "    boundary = boundary - image_array[0,0]\n",
252 253
    "    \n",
    "    #boundary is 1dim, so boundary[0] is just the first element\n",
254
    "    boundary[0] = image_array[0,0]\n",
Kelly Chang's avatar
Kelly Chang committed
255
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
256
    "    # huffman encode the boundary\n",
Bryce Hepner's avatar
Bryce Hepner committed
257 258
    "    bound_vals_as_string = [str(i) for i in boundary]\n",
    "    freq = dict(Counter(bound_vals_as_string))\n",
Kelly Chang's avatar
Kelly Chang committed
259 260
    "    freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)\n",
    "    node = make_tree(freq)\n",
261
    "    huffman_encoding_dict = huffman_code_tree(node)\n",
Kelly Chang's avatar
Kelly Chang committed
262
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
263
    "    # create a list of huffman table\n",
264
    "    huffman_encoding_list = [huffman_encoding_dict]\n",
Kelly Chang's avatar
Kelly Chang committed
265
    "    n = len(bins)\n",
Kelly Chang's avatar
Kelly Chang committed
266
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
267 268
    "    # loop through different bins\n",
    "    for i in range (0,n):\n",
269
    "        # the first bin\n",
Kelly Chang's avatar
Kelly Chang committed
270
    "        if i == 0 :\n",
271
    "            # get the point within the bin and huffman huffman_encoding_dict\n",
Kelly Chang's avatar
Kelly Chang committed
272
    "            mask = diff <= bins[i]\n",
Bryce Hepner's avatar
Bryce Hepner committed
273 274
    "            line_as_string = [str(i) for i in error[mask].astype(int)]\n",
    "            freq = dict(Counter(line_as_string))\n",
Kelly Chang's avatar
Kelly Chang committed
275 276
    "            freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)\n",
    "            node = make_tree(freq)\n",
277 278
    "            huffman_encoding_dict = huffman_code_tree(node)\n",
    "            huffman_encoding_list.append(huffman_encoding_dict)\n",
Kelly Chang's avatar
Kelly Chang committed
279 280 281
    "            \n",
    "        # the middle bins\n",
    "        else:\n",
282
    "            # get the point within the bin and huffman huffman_encoding_dict\n",
Kelly Chang's avatar
Kelly Chang committed
283 284 285
    "            mask = diff > bins[i-1]\n",
    "            new_error = error[mask]\n",
    "            mask2 = diff[mask] <= bins[i]\n",
Bryce Hepner's avatar
Bryce Hepner committed
286 287
    "            line_as_string = [str(i) for i in new_error[mask2].astype(int)]\n",
    "            freq = dict(Counter(line_as_string))\n",
Kelly Chang's avatar
Kelly Chang committed
288 289
    "            freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)\n",
    "            node = make_tree(freq)\n",
290 291
    "            huffman_encoding_dict = huffman_code_tree(node)\n",
    "            huffman_encoding_list.append(huffman_encoding_dict)\n",
Kelly Chang's avatar
Kelly Chang committed
292 293
    "            \n",
    "    # the last bin       \n",
294
    "    # get the point within the bin and huffman huffman_encoding_dict\n",
Kelly Chang's avatar
Kelly Chang committed
295
    "    mask = diff > bins[-1]\n",
Bryce Hepner's avatar
Bryce Hepner committed
296 297
    "    line_as_string = [str(i) for i in error[mask].astype(int)]\n",
    "    freq = dict(Counter(line_as_string))\n",
Kelly Chang's avatar
Kelly Chang committed
298 299
    "    freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)\n",
    "    node = make_tree(freq)\n",
300 301
    "    huffman_encoding_dict = huffman_code_tree(node)\n",
    "    huffman_encoding_list.append(huffman_encoding_dict)\n",
Kelly Chang's avatar
Kelly Chang committed
302
    "\n",
Kelly Chang's avatar
Kelly Chang committed
303
    "    # create a error matrix that includes the boundary (used in encoding matrix)\n",
304
    "    new_error = np.copy(image_array)\n",
Kelly Chang's avatar
Kelly Chang committed
305 306 307 308 309 310 311
    "    new_error[1:-1,1:-1] = np.reshape(error,(510, 638))\n",
    "    keep = new_error[0,0]\n",
    "    new_error[0,:] = new_error[0,:] - keep\n",
    "    new_error[-1,:] = new_error[-1,:] - keep\n",
    "    new_error[1:-1,0] = new_error[1:-1,0] - keep\n",
    "    new_error[1:-1,-1] = new_error[1:-1,-1] - keep\n",
    "    new_error[0,0] = keep\n",
312
    "    # huffman_encoding_list = list(set(huffman_encoding_list))\n",
Kelly Chang's avatar
Kelly Chang committed
313
    "    diff = np.reshape(diff,(510,638))\n",
Kelly Chang's avatar
Kelly Chang committed
314
    "    # return the huffman dictionary\n",
315
    "    return huffman_encoding_list, image_array, new_error, diff, boundary, predict, bins, A\n",
Kelly Chang's avatar
Kelly Chang committed
316
    " \n"
Kelly Chang's avatar
Kelly Chang committed
317 318 319 320
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
321
   "execution_count": 6,
Kelly Chang's avatar
Kelly Chang committed
322 323 324 325 326
   "id": "2eb774d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def encoder(error, list_dic, diff, bound, bins):\n",
Kelly Chang's avatar
Kelly Chang committed
327
    "    \"\"\"\n",
Kelly Chang's avatar
Kelly Chang committed
328 329 330 331 332 333 334 335 336 337
    "    This function encode the matrix with huffman coding tables\n",
    "    \n",
    "    Input:\n",
    "    error     (512, 640): a matrix with all the errors\n",
    "    list_dic  (num_dic + 1,): a list of huffman coding table \n",
    "    bound     (2300,): the boundary values after subtracting the very first pixel value\n",
    "    bins       (num_bins - 1,): a list of threshold to cut the bins\n",
    "    \n",
    "    Return:\n",
    "    encoded   (512, 640): encoded matrix\n",
Kelly Chang's avatar
Kelly Chang committed
338
    "    \"\"\"\n",
Kelly Chang's avatar
Kelly Chang committed
339
    "    # copy the error matrix (including the boundary)\n",
Kelly Chang's avatar
Kelly Chang committed
340
    "    encoded = np.copy(error).astype(int).astype(str).astype(object)\n",
Kelly Chang's avatar
Kelly Chang committed
341
    "    #diff = np.reshape(diff,(510,638))\n",
Kelly Chang's avatar
Kelly Chang committed
342
    "    # loop through all the pixel to encode\n",
Kelly Chang's avatar
Kelly Chang committed
343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
    "    for i in range(encoded.shape[0]):\n",
    "        for j in range(encoded.shape[1]):\n",
    "            if i == 0 or i == encoded.shape[0]-1 or j == 0 or j == encoded.shape[1]-1:\n",
    "                encoded[i][j] = list_dic[0][encoded[i][j]]\n",
    "            elif diff[i-1][j-1] <= bins[0]:\n",
    "                encoded[i][j] = list_dic[1][encoded[i][j]]\n",
    "            elif diff[i-1][j-1] <= bins[1] and diff[i-1][j-1] > bins[0]:\n",
    "                encoded[i][j] = list_dic[2][encoded[i][j]]\n",
    "            elif diff[i-1][j-1] <= bins[2] and diff[i-1][j-1] > bins[1]:\n",
    "                encoded[i][j] = list_dic[3][encoded[i][j]]\n",
    "            else: \n",
    "                encoded[i][j] = list_dic[4][encoded[i][j]]\n",
    "\n",
    "    return encoded"
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
361
   "execution_count": 7,
Kelly Chang's avatar
Kelly Chang committed
362 363 364 365
   "id": "8eeb40d0",
   "metadata": {},
   "outputs": [],
   "source": [
Kelly Chang's avatar
Kelly Chang committed
366
    "def decoder(A, encoded_matrix, list_dic, bins, use_diff):\n",
Kelly Chang's avatar
Kelly Chang committed
367
    "    \"\"\"\n",
Kelly Chang's avatar
Kelly Chang committed
368 369 370 371 372 373
    "    This function decodes the encoded_matrix.\n",
    "    Input:\n",
    "    A               (3 X 3): system of equation\n",
    "    list_dic        (num_dic + 1,): a list of huffman coding table \n",
    "    encoded_matrix  (512, 640): encoded matrix\n",
    "    bins            (num_bins - 1,): a list of threshold to cut the bins\n",
Kelly Chang's avatar
Kelly Chang committed
374
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
375 376
    "    Return:\n",
    "    decode_matrix   (512, 640): decoded matrix\n",
Kelly Chang's avatar
Kelly Chang committed
377
    "    \"\"\"\n",
Kelly Chang's avatar
Kelly Chang committed
378
    "    # change the dictionary back to list\n",
Kelly Chang's avatar
Kelly Chang committed
379
    "    # !!!!!WARNING!!!! has to change this part, eveytime you change the number of bins\n",
Kelly Chang's avatar
Kelly Chang committed
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
    "    the_keys0 = list(list_dic[0].keys())\n",
    "    the_values0 = list(list_dic[0].values())\n",
    "    \n",
    "    the_keys1 = list(list_dic[1].keys())\n",
    "    the_values1 = list(list_dic[1].values())\n",
    "    \n",
    "    the_keys2 = list(list_dic[2].keys())\n",
    "    the_values2 = list(list_dic[2].values())\n",
    "    \n",
    "    the_keys3 = list(list_dic[3].keys())\n",
    "    the_values3 = list(list_dic[3].values())\n",
    "    \n",
    "    the_keys4 = list(list_dic[4].keys())\n",
    "    the_values4 = list(list_dic[4].values())\n",
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
395 396 397
    "    #Matrix system of points that will be used to solve the least squares fitting hyperplane\n",
    "    points = np.array([[-1,-1,1], [-1,0,1], [-1,1,1], [0,-1,1]])\n",
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
398
    "    decode_matrix = np.zeros((512,640))\n",
Kelly Chang's avatar
Kelly Chang committed
399
    "    # loop through all the element in the matrix\n",
Kelly Chang's avatar
Kelly Chang committed
400 401
    "    for i in range(decode_matrix.shape[0]):\n",
    "        for j in range(decode_matrix.shape[1]):\n",
Kelly Chang's avatar
Kelly Chang committed
402
    "            # if it's the very first pixel on the image\n",
Kelly Chang's avatar
Kelly Chang committed
403
    "            if i == 0 and j == 0:\n",
Kelly Chang's avatar
Kelly Chang committed
404
    "                decode_matrix[i][j] = int(the_keys0[the_values0.index(encoded_matrix[i,j])])\n",
405 406 407
    "                print(encoded_matrix[i][j])\n",
    "                print(the_values0.index(encoded_matrix[i,j]))\n",
    "                print(int(the_keys0[the_values0.index(encoded_matrix[i,j])]))\n",
408
    "            # if it's on the boundary (any of the 4 edges)\n",
Kelly Chang's avatar
Kelly Chang committed
409 410
    "            elif i == 0 or i == decode_matrix.shape[0]-1 or j == 0 or j == decode_matrix.shape[1]-1:\n",
    "                decode_matrix[i][j] = int(the_keys0[the_values0.index(encoded_matrix[i,j])]) + decode_matrix[0][0]\n",
Kelly Chang's avatar
Kelly Chang committed
411
    "            # if not the boundary\n",
Kelly Chang's avatar
Kelly Chang committed
412
    "            else:\n",
Kelly Chang's avatar
Kelly Chang committed
413
    "                # predict the image with the known pixel value\n",
Kelly Chang's avatar
Kelly Chang committed
414 415 416 417
    "                z0 = decode_matrix[i-1][j-1]\n",
    "                z1 = decode_matrix[i-1][j]\n",
    "                z2 = decode_matrix[i-1][j+1]\n",
    "                z3 = decode_matrix[i][j-1]\n",
Kelly Chang's avatar
Kelly Chang committed
418 419 420 421
    "                y0 = int(-z0+z2-z3)\n",
    "                y1 = int(z0+z1+z2)\n",
    "                y2 = int(-z0-z1-z2-z3)\n",
    "                y = np.vstack((y0,y1,y2))\n",
Kelly Chang's avatar
Kelly Chang committed
422 423 424 425 426 427 428
    "                if use_diff:\n",
    "                    difference = max(z0,z1,z2,z3) - min(z0,z1,z2,z3)\n",
    "                else:\n",
    "                    \n",
    "                    f, difference, rank, s = la.lstsq(points, [z0,z1,z2,z3], rcond=None) \n",
    "                    difference = difference.astype(int)\n",
    "                    \n",
Kelly Chang's avatar
Kelly Chang committed
429
    "                predict = np.round(np.round(np.linalg.solve(A,y)[-1][0],1))\n",
Kelly Chang's avatar
Kelly Chang committed
430 431
    "                \n",
    "                # add on the difference by searching the dictionary\n",
Kelly Chang's avatar
Kelly Chang committed
432
    "                # !!!!!WARNING!!!! has to change this part, eveytime you change the number of bins\n",
Kelly Chang's avatar
Kelly Chang committed
433
    "                if difference <= bins[0]:\n",
Kelly Chang's avatar
Kelly Chang committed
434
    "                    decode_matrix[i][j] = int(the_keys1[the_values1.index(encoded_matrix[i,j])]) + int(predict)\n",
Kelly Chang's avatar
Kelly Chang committed
435
    "                elif difference <= bins[1] and difference > bins[0]:\n",
Kelly Chang's avatar
Kelly Chang committed
436
    "                    decode_matrix[i][j] = int(the_keys2[the_values2.index(encoded_matrix[i,j])]) + int(predict)\n",
Kelly Chang's avatar
Kelly Chang committed
437
    "                elif difference <= bins[2] and difference > bins[1]:\n",
Kelly Chang's avatar
Kelly Chang committed
438
    "                    decode_matrix[i][j] = int(the_keys3[the_values3.index(encoded_matrix[i,j])]) + int(predict)\n",
Kelly Chang's avatar
Kelly Chang committed
439
    "                else:\n",
Kelly Chang's avatar
Kelly Chang committed
440
    "                    decode_matrix[i][j] = int(the_keys4[the_values4.index(encoded_matrix[i,j])]) + int(predict)\n",
Kelly Chang's avatar
Kelly Chang committed
441 442
    "                \n",
    "                \n",
Kelly Chang's avatar
Kelly Chang committed
443
    "    return decode_matrix.astype(int)"
Kelly Chang's avatar
Kelly Chang committed
444 445
   ]
  },
Kelly Chang's avatar
Kelly Chang committed
446 447
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
448
   "execution_count": 8,
Kelly Chang's avatar
Kelly Chang committed
449 450 451 452
   "id": "f959fe93",
   "metadata": {},
   "outputs": [],
   "source": [
453
    "def compress_rate(image_array, new_error, diff, bound, huffman_encoding_list, bins):\n",
Kelly Chang's avatar
Kelly Chang committed
454 455
    "    '''\n",
    "    This function is used to calculate the compression rate.\n",
Kelly Chang's avatar
Kelly Chang committed
456
    "    Input:\n",
457
    "    image_array      (512, 640): original_core image\n",
Kelly Chang's avatar
Kelly Chang committed
458 459 460
    "    new_error  (512, 640): error that includes the boundary\n",
    "    diff       (510, 638): difference of min and max of the 4 neighbors\n",
    "    bound      (2300,): the boundary values after subtracting the very first pixel value\n",
461
    "    huffman_encoding_list   (num_dic + 1,): a list of huffman coding table \n",
Kelly Chang's avatar
Kelly Chang committed
462
    "    bins       (num_bins - 1,): a list of threshold to cut the bins\n",
Kelly Chang's avatar
Kelly Chang committed
463
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
464 465
    "    Return:\n",
    "    compression rate\n",
Kelly Chang's avatar
Kelly Chang committed
466
    "    '''\n",
Kelly Chang's avatar
Kelly Chang committed
467
    "    # the bits for the original image\n",
Kelly Chang's avatar
Kelly Chang committed
468
    "    o_len = 0\n",
Kelly Chang's avatar
Kelly Chang committed
469
    "    # the bits for the compressed image\n",
Kelly Chang's avatar
Kelly Chang committed
470
    "    c_len = 0\n",
Kelly Chang's avatar
Kelly Chang committed
471
    "    # initializing the varible \n",
472 473 474 475 476 477 478
    "    \n",
    "    #this was unused\n",
    "    # im = np.reshape(image,(512, 640))\n",
    "    \n",
    "    real_boundary = np.hstack((image_array[0,:],image_array[-1,:],image_array[1:-1,0],image_array[1:-1,-1]))\n",
    "    #Bryce's notes: Why are they all reshaped?\n",
    "    original_core = image_array[1:-1,1:-1].reshape(-1)\n",
Kelly Chang's avatar
Kelly Chang committed
479
    "    diff = diff.reshape(-1)\n",
Kelly Chang's avatar
Kelly Chang committed
480
    "    error = new_error[1:-1,1:-1].reshape(-1)\n",
Kelly Chang's avatar
Kelly Chang committed
481 482 483
    "    \n",
    "    # calculate the bit for boundary\n",
    "    for i in range(0,len(bound)):\n",
484 485
    "        o_len += len(bin(real_boundary[i])[2:])\n",
    "        c_len += len(huffman_encoding_list[0][str(bound[i])])\n",
Kelly Chang's avatar
Kelly Chang committed
486
    "    \n",
Kelly Chang's avatar
Kelly Chang committed
487
    "    # calculate the bit for the pixels inside the boundary\n",
488
    "    for i in range(0,len(original_core)):\n",
Kelly Chang's avatar
Kelly Chang committed
489
    "\n",
Kelly Chang's avatar
Kelly Chang committed
490
    "        # for the original image\n",
491
    "        o_len += len(bin(original_core[i])[2:])\n",
Kelly Chang's avatar
Kelly Chang committed
492 493
    "        \n",
    "        # check the difference and find the coresponding huffman table\n",
Kelly Chang's avatar
Kelly Chang committed
494
    "        # !!!!!WARNING!!!! has to change this part, eveytime you change the number of bins\n",
Kelly Chang's avatar
Kelly Chang committed
495
    "        if diff[i] <= bins[0]:\n",
496
    "            c_len += len(huffman_encoding_list[1][str(int(error[i]))])\n",
Kelly Chang's avatar
Kelly Chang committed
497 498
    "            \n",
    "        elif diff[i] <= bins[1] and diff[i] > bins[0]:\n",
499
    "            c_len += len(huffman_encoding_list[2][str(int(error[i]))])\n",
Kelly Chang's avatar
Kelly Chang committed
500 501
    "            \n",
    "        elif diff[i] <= bins[2] and diff[i] > bins[1]:\n",
502
    "            c_len += len(huffman_encoding_list[3][str(int(error[i]))])\n",
Kelly Chang's avatar
Kelly Chang committed
503
    "\n",
Kelly Chang's avatar
Kelly Chang committed
504
    "        else: \n",
505
    "            c_len += len(huffman_encoding_list[4][str(int(error[i]))])\n",
506
    "            \n",
Kelly Chang's avatar
Kelly Chang committed
507 508 509
    "    return c_len/o_len"
   ]
  },
Kelly Chang's avatar
Kelly Chang committed
510 511
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
512
   "execution_count": 9,
Kelly Chang's avatar
Kelly Chang committed
513 514
   "id": "3e0e9742",
   "metadata": {},
Kelly Chang's avatar
Kelly Chang committed
515 516 517 518 519
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
520 521 522
      "11100100000\n",
      "499\n",
      "22275\n",
Kelly Chang's avatar
Kelly Chang committed
523 524 525 526 527
      "True\n",
      "5\n"
     ]
    }
   ],
Kelly Chang's avatar
Kelly Chang committed
528
   "source": [
Kelly Chang's avatar
Kelly Chang committed
529 530
    "scenes = file_extractor()\n",
    "images = image_extractor(scenes)\n",
Kelly Chang's avatar
Kelly Chang committed
531
    "list_dic, image, new_error, diff, bound, predict, bins, A = huffman(images[0], 4, False)\n",
Kelly Chang's avatar
Kelly Chang committed
532
    "encoded_matrix = encoder(new_error, list_dic, diff, bound, bins)\n",
Kelly Chang's avatar
Kelly Chang committed
533
    "reconstruct_image = decoder(A, encoded_matrix, list_dic, bins, False)\n",
Kelly Chang's avatar
Kelly Chang committed
534
    "print(np.allclose(image, reconstruct_image))\n",
Kelly Chang's avatar
Kelly Chang committed
535
    "print(len(list_dic))"
Kelly Chang's avatar
Kelly Chang committed
536 537 538 539
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
540
   "execution_count": 10,
Kelly Chang's avatar
Kelly Chang committed
541
   "id": "004e8ba8",
Kelly Chang's avatar
Kelly Chang committed
542
   "metadata": {},
Kelly Chang's avatar
Kelly Chang committed
543 544
   "outputs": [
    {
Kelly Chang's avatar
Kelly Chang committed
545 546
     "data": {
      "text/plain": [
547
       "0.4232928466796875"
Kelly Chang's avatar
Kelly Chang committed
548 549
      ]
     },
Bryce Hepner's avatar
Bryce Hepner committed
550
     "execution_count": 10,
Kelly Chang's avatar
Kelly Chang committed
551 552
     "metadata": {},
     "output_type": "execute_result"
Kelly Chang's avatar
Kelly Chang committed
553 554
    }
   ],
Kelly Chang's avatar
Kelly Chang committed
555
   "source": [
Kelly Chang's avatar
Kelly Chang committed
556
    "compress_rate(image, new_error, diff, bound, list_dic, bins)"
Kelly Chang's avatar
Kelly Chang committed
557 558 559 560
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
561
   "execution_count": 11,
Kelly Chang's avatar
Kelly Chang committed
562
   "id": "a282f9e6",
Kelly Chang's avatar
Kelly Chang committed
563
   "metadata": {},
564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2621552\n",
      "2621552\n"
     ]
    }
   ],
   "source": [
    "print(sys.getsizeof(encoded_matrix))\n",
    "print(sys.getsizeof(reconstruct_image))"
   ]
  },
  {
   "cell_type": "code",
Bryce Hepner's avatar
Bryce Hepner committed
581
   "execution_count": null,
582 583
   "id": "7efe26b9",
   "metadata": {},
Bryce Hepner's avatar
Bryce Hepner committed
584
   "outputs": [],
585 586 587 588 589 590 591
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b46343b2",
   "metadata": {},
Kelly Chang's avatar
Kelly Chang committed
592
   "outputs": [],
Kelly Chang's avatar
Kelly Chang committed
593
   "source": []
Kelly Chang's avatar
Kelly Chang committed
594 595 596 597
  }
 ],
 "metadata": {
  "kernelspec": {
598
   "display_name": "Python 3.8.10 64-bit",
Kelly Chang's avatar
Kelly Chang committed
599 600 601 602 603 604 605 606 607 608 609 610 611
   "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",
612
   "version": "3.8.10"
613 614 615 616 617
  },
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
Kelly Chang's avatar
Kelly Chang committed
618 619 620 621 622
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}