{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"name":"python","version":"3.10.12","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"kaggle":{"accelerator":"none","dataSources":[],"dockerImageVersionId":30635,"isInternetEnabled":true,"language":"python","sourceType":"notebook","isGpuEnabled":false}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# RLE coding notebook with exported python module\n\nTo reuse these encode/decode function you attach this notebook to your code and add path to the his resource [wiki](https://en.wikipedia.org/wiki/Run-length_encoding)\n\n## Brief explanation\n\n> In order to reduce the submission file size, teams must submit segmentation results using run-length encoding on the pixel values. That is, 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. '0 3' implies starting at pixel 0 and running a total of 3 pixels (0,1,2). The competition format requires a space delimited list of pairs. For example, '0 3 10 5' implies pixels 0,1,2, and 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: 0 is pixel (0,0), 1 is pixel (1,0), and 2 is pixel (2,0) etc. [source](https://www.kaggle.com/code/leahscherschel/run-length-encoding?scriptVersionId=47248117&cellId=2)\n\n## Code illustration\n\nSee the source [publication](https://www.researchgate.net/publication/339534216_How_to_speed_Connected_Component_Labeling_up_with_SIMD_RLE_algorithms)\n\n![](https://www.researchgate.net/profile/Lionel-Lacassagne/publication/339534216/figure/fig1/AS:863172827299840@1582807847162/Example-of-a-segment-and-its-associated-run-length-encoding-with-a-semi-open-interval-0_W640.jpg)\n\n\n**Code ref: https://github.com/Borda/kaggle_image-segm**","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"code","source":"import sys\n\nsys.path.append(\"/kaggle/working/\")  # this will be path to this notebook","metadata":{"execution":{"iopub.status.busy":"2024-01-22T11:10:44.657939Z","iopub.execute_input":"2024-01-22T11:10:44.658989Z","iopub.status.idle":"2024-01-22T11:10:44.699970Z","shell.execute_reply.started":"2024-01-22T11:10:44.658950Z","shell.execute_reply":"2024-01-22T11:10:44.698331Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## RLE encoding\n\nconvert the 2D image with labels to dictionary with strings","metadata":{}},{"cell_type":"code","source":"%%writefile rle.py\n\nimport numpy as np\nfrom typing import Dict\n\ndef rle_encode(mask: np.ndarray, label_bg: int = 0) -> Dict[int, str]:\n    \"\"\"Encode mask to Run-length encoding.\n\n    Inspiration took from: https://gist.github.com/nvictus/66627b580c13068589957d6ab0919e66\n    \"\"\"\n    vec = mask.flatten()\n    nb = len(vec)\n    where = np.flatnonzero\n    starts = np.r_[0, where(~np.isclose(vec[1:], vec[:-1], equal_nan=True)) + 1]\n    lengths = np.diff(np.r_[starts, nb])\n    values = vec[starts]\n    assert len(starts) == len(lengths) == len(values)\n    rle = {}\n    for start, length, val in zip(starts, lengths, values):\n        if val == label_bg:\n            continue\n        rle[val] = rle.get(val, []) + [str(start), length]\n    # post-processing\n    rle = {lb: \" \".join(map(str, id_lens)) for lb, id_lens in rle.items()}\n    return rle","metadata":{"execution":{"iopub.status.busy":"2024-01-22T11:10:44.702543Z","iopub.execute_input":"2024-01-22T11:10:44.703020Z","iopub.status.idle":"2024-01-22T11:10:44.711733Z","shell.execute_reply.started":"2024-01-22T11:10:44.702976Z","shell.execute_reply":"2024-01-22T11:10:44.709940Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## RLE decoding\n\nReconstruct the string with indexes and lengths to 2D binary image","metadata":{}},{"cell_type":"code","source":"%%writefile -a rle.py\n\ndef rle_decode(rle_code: str, img: np.ndarray = None, img_shape: tuple = None, label: int = 1) -> np.ndarray:\n    \"\"\"Create a single label mask for Run-length encoding.\"\"\"\n    seq = rle_code.split()\n    starts = np.array(list(map(int, seq[0::2])))\n    lengths = np.array(list(map(int, seq[1::2])))\n    assert len(starts) == len(lengths)\n    ends = starts + lengths\n\n    if img is None:\n        img = np.zeros((np.product(img_shape),), dtype=np.uint16)\n    else:\n        img_shape = img.shape\n        img = img.flatten()\n    for begin, end in zip(starts, ends):\n        img[begin:end] = label\n\n    # https://stackoverflow.com/a/46574906/4521646\n    img.shape = img_shape  # inplace reshape\n    return img","metadata":{"execution":{"iopub.status.busy":"2024-01-22T11:10:44.713702Z","iopub.execute_input":"2024-01-22T11:10:44.714166Z","iopub.status.idle":"2024-01-22T11:10:44.728742Z","shell.execute_reply.started":"2024-01-22T11:10:44.714123Z","shell.execute_reply":"2024-01-22T11:10:44.727357Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## simple example\n\nHere we show how to code and decode sample mask","metadata":{}},{"cell_type":"code","source":"import numpy as np\n\n# Demo sample image\nimg = np.zeros((8, 10), dtype=np.uint8)\nimg[1:6, 2:7] = 1\nimg[4:7, 5:9] = 2\nprint(img)","metadata":{"execution":{"iopub.status.busy":"2024-01-22T11:10:44.732387Z","iopub.execute_input":"2024-01-22T11:10:44.732778Z","iopub.status.idle":"2024-01-22T11:10:44.741494Z","shell.execute_reply.started":"2024-01-22T11:10:44.732745Z","shell.execute_reply":"2024-01-22T11:10:44.739872Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from rle import rle_encode\n\n# encode demo segmentation with N labels\nrles = rle_encode(img)\nprint(rles)","metadata":{"execution":{"iopub.status.busy":"2024-01-22T11:10:44.743271Z","iopub.execute_input":"2024-01-22T11:10:44.743708Z","iopub.status.idle":"2024-01-22T11:10:44.760263Z","shell.execute_reply.started":"2024-01-22T11:10:44.743669Z","shell.execute_reply":"2024-01-22T11:10:44.758866Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from rle import rle_decode\n\nseg = None\n# recosntruct the image from RLE\nfor lb, rle_ in rles.items():\n    seg = rle_decode(rle_, seg, img_shape=img.shape, label=lb)\n\nprint(seg)","metadata":{"execution":{"iopub.status.busy":"2024-01-22T11:10:44.762008Z","iopub.execute_input":"2024-01-22T11:10:44.762486Z","iopub.status.idle":"2024-01-22T11:10:44.771176Z","shell.execute_reply.started":"2024-01-22T11:10:44.762443Z","shell.execute_reply":"2024-01-22T11:10:44.770112Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# if the RLE code and decode is corerct the diff shall be zero\nprint(img - seg)","metadata":{"execution":{"iopub.status.busy":"2024-01-22T11:10:44.772622Z","iopub.execute_input":"2024-01-22T11:10:44.773098Z","iopub.status.idle":"2024-01-22T11:10:44.791052Z","shell.execute_reply.started":"2024-01-22T11:10:44.773064Z","shell.execute_reply":"2024-01-22T11:10:44.790013Z"},"trusted":true},"execution_count":null,"outputs":[]}]}