{"cells":[{"metadata":{},"cell_type":"markdown","source":"# RLE_NUMBA Function Explained\n\n**Description:**\n - rle_numba is a function used in a number of public HuBMAP notebooks for inference and creating a submission.\n - Seemed to me this function was essential to making a submission, and so I thought I would comb through the function line by line to get a better understanding of how it works.\n\n**References:**\n - https://www.kaggle.com/leighplt/pytorch-fcn-resnet50\n - https://www.kaggle.com/joshi98kishan/hubmap-keras-pipeline-training-inference\n - https://www.kaggle.com/c/hubmap-kidney-segmentation/overview/supervised-ml-evaluation\n \n**Function Expectation:**\n\n - \"In order to reduce the submission file size, our metric uses run-length encoding on the pixel values.  Instead of submitting an exhaustive list of indices for your segmentation, you will submit pairs of values that contain a start position and a run length. E.g. '1 3' implies starting at pixel 1 and running a total of 3 pixels (1,2,3).\"  \n - \"Note that, at the time of encoding, the mask should be binary, meaning the masks for all objects in an image are joined into a single large mask. A value of 0 should indicate pixels that are not masked, and a value of 1 will indicate pixels that are masked.  The competition format requires a space delimited list of pairs. For example, '1 3 10 5' implies pixels 1,2,3,10,11,12,13,14 are to be included in the mask. The metric checks that the pairs are sorted, positive, and the decoded pixel values are not duplicated. The pixels are numbered from top to bottom, then left to right: 1 is pixel (1,1), 2 is pixel (2,1), etc.\""},{"metadata":{},"cell_type":"markdown","source":"# Imports"},{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"code","source":"import numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\nimport os","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Full Function"},{"metadata":{"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","trusted":true},"cell_type":"code","source":"def rle_numba(pixels):\n    size = len(pixels)\n    points = []\n    if pixels[0] == 1: points.append(1)\n    flag = True\n    for i in range(1, size):\n        if pixels[i] != pixels[i-1]:\n            if flag:\n                points.append(i+1)\n                flag = False\n            else:\n                points.append(i+1 - points[-1])\n                flag = True\n    if pixels[-1] == 1: points.append(size-points[-1]+1)    \n    return points","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Generate Fake Data"},{"metadata":{"trusted":true},"cell_type":"code","source":"np.random.seed(0)\npixels = np.where(np.random.randint(0,100,20)>50,1,0)\nprint(\"pixels list:\")\npixels","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Run Function"},{"metadata":{"trusted":true},"cell_type":"code","source":"rle_numba(pixels)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Line by Line Walkthrough"},{"metadata":{},"cell_type":"markdown","source":"* get the length of the sequence"},{"metadata":{"trusted":true},"cell_type":"code","source":"size = len(pixels)\nprint(\"size of list 'pixels': \", size)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* if the first value is 1, append 0 to points\n* otherwise, do nothing"},{"metadata":{"trusted":true},"cell_type":"code","source":"points = []\nif pixels[0] == 1: \n    points.append(0)\nprint(\"points list:\")\npoints","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* we start at position 1 in pixels, and we compare the current position to the previous"},{"metadata":{"trusted":true},"cell_type":"code","source":"i = 1\nprint(\"current value in list pixels: \", pixels[i])\nprint(\"previous value in list pixels: \", pixels[i-1])","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* set 'flag' to True\n* if the current position is not equal to the previous position, append i+1 to points, or i.e. the current position value plus 1; then set flag to False\n* otherwise, do nothing\n\n**in this case, we do nothing because our previous and current values are equal (so flag is still True)**"},{"metadata":{"trusted":true},"cell_type":"code","source":"flag = True\nif pixels[i] != pixels[i-1]:\n    if flag:\n        points.append(i+1)\n        flag = False\nprint(\"points list:\")\npoints","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* iterate to the next position and get previous and current values"},{"metadata":{"trusted":true},"cell_type":"code","source":"i = 2\nprint(\"current value in list pixels: \", pixels[i])\nprint(\"previous value in list pixels: \", pixels[i-1])","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* remember that previously, we still have flag set to True, and since the current value != previous value, we enter the first 'if flag' section\n* this time we append i+1 to points and flag is set to False\n\n### Note that when flag = True, seems the function is appending 'the starting position of a mask' to our output list."},{"metadata":{"trusted":true},"cell_type":"code","source":"flag = True\nif pixels[i] != pixels[i-1]:\n    if flag:\n        points.append(i+1)\n        flag = False\n    else:\n        print(points[-1])\n        print(i+1)\n        print(i+1 - points[-1])\n        points.append(i+1 - points[-1])\n        flag = True\nprint(\"points list:\")\nprint(points)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* iterate to the next position and get previous and current values"},{"metadata":{"trusted":true},"cell_type":"code","source":"i = 3\nprint(\"current value in list pixels: \", pixels[i])\nprint(\"previous value in list pixels: \", pixels[i-1])","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":" * note, previously, we set flag to False\n * since the previous and current values are equal, we do nothing"},{"metadata":{"trusted":true},"cell_type":"code","source":"flag = False\nif pixels[i] != pixels[i-1]:\n    if flag:\n        points.append(i+1)\n        flag = False\n    else:\n        print(points[-1])\n        print(i+1)\n        print(i+1 - points[-1])\n        points.append(i+1 - points[-1])\n        flag = True\nprint(\"points list:\")\nprint(points)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":" * in fact, we do nothing until poisition 5, where previous and current values are now unequal"},{"metadata":{"trusted":true},"cell_type":"code","source":"i = 5\nprint(\"current value in list pixels: \", pixels[i])\nprint(\"previous value in list pixels: \", pixels[i-1])","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":" * again, remember that flag is still currently False\n * since previous and current values are unequal and flag is False, we enter the else statement\n * this time, we appned {i+1 - 'last value'} and we set flag back to True\n\n### First, note that when flag is False, it seems the function is appending 'the run length of the mask' to our output list.  Also note that {i+1 - 'last value'} is another way of saying {where we are - where we were}.  \n\n### Notice how we flip back and forth between appending {i+1} and {i+1 - 'last value'} every time the previous value and current value are unequal."},{"metadata":{"trusted":true},"cell_type":"code","source":"flag = False\nif pixels[i] != pixels[i-1]:\n    if flag:\n        points.append(i+1)\n        flag = False\n    else:\n        print(\"last values in list points: \", points[-1])\n        print(\"i+1: \", i+1)\n        print(\"i+1 - last values in list points: \", i+1 - points[-1])\n        points.append(i+1 - points[-1])\n        flag = True\nprint(\"points list:\")\nprint(points)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* We complete this for all values in list 'pixels'"},{"metadata":{"trusted":true},"cell_type":"code","source":"flag = True\nfor i in range(6, size):\n    if pixels[i] != pixels[i-1]:\n        if flag:\n            points.append(i+1)\n            flag = False\n        else:\n            points.append(i+1 - points[-1])\n            flag = True\nprint(\"points list:\")\nprint(points)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"* Finally, if the last value in list 'pixels' is 1, we append a final value to points of {size - 'last value' + 1}\n\nWe do this because if the final mask runs to the end (i.e. pixels list ends with a series of 1's), there is no value change at the end of the list; so if the final value is 1, we just take {size - 'last value' + 1} as our final run length. "},{"metadata":{"trusted":true},"cell_type":"code","source":"pixels","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"pixels[-1]","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"if pixels[-1] == 1:\n    print(\"size: \", size)\n    print(\"last values in list points: \", points[-1])\n    print(\"size - last value in list points + 1:\", size-points[-1]+1)\n    points.append(size-points[-1]+1)  \nprint(\"points list:\")\nprint(points)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Caveats"},{"metadata":{},"cell_type":"markdown","source":" * If the 'pixels' list starts with a 1 pixel mask, then the rest of the output looks off\n * A 1 pixel mask in the beginning probably doesn't make sense, but if your model produces something like this by chance, then you could have a problem\n \n * also note that it seems like the function is not expecting to start with a short mask, which again probably doesn't make sense, but if your model produces something like this by chance, again you could have a problem"},{"metadata":{"trusted":true},"cell_type":"code","source":"np.random.seed(1331)\npixels = np.where(np.random.randint(0,100,20)>50,1,0)\npixels","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"rle_numba(pixels)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# My Function Revision\n\nI think the original function might have a coding error.  Below is an alternative function that appends 1, and in addition sets flag to False, if the the list 'pixels' starts with a mask.  If we're appending 1 and starting with a mask, we want our next appended value to be a run length.  By setting flag to False when pixels[0]==1, we accomplish this. "},{"metadata":{"trusted":true},"cell_type":"code","source":"np.random.seed(1331)\npixels = np.where(np.random.randint(0,100,20)>50,1,0)\npixels","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def rle_numba_v2(pixels):\n    size = len(pixels)\n    points = []\n    if pixels[0] == 1: \n        points.append(1)\n        flag = False\n    else:\n        flag = True\n    for i in range(1, size):\n        if pixels[i] != pixels[i-1]:\n            if flag:\n                points.append(i+1)\n                flag = False\n            else:\n                points.append(i+1 - points[-1])\n                flag = True\n    if pixels[-1] == 1: points.append(size-points[-1]+1)    \n    return points","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"rle_numba_v2(pixels)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# The End\n\nThanks for reading :).  Would love to hear your thoughts and feedback in the comments.  Thanks again!"},{"metadata":{"trusted":true},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}