{"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_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Faster RLE\n\n`\" \".join()` function gets slower as the precision of the inference result decreases. This notebook describes how to use `np.savetxt` to prevent slowdowns.","metadata":{}},{"cell_type":"code","source":"import numpy as np\nfrom io import StringIO\n\ndef rle(img, img_id):\n    flat_img = img.flatten().astype(np.uint8)\n\n    starts = np.array((flat_img[:-1] == 0) & (flat_img[1:] == 1))\n    ends = np.array((flat_img[:-1] == 1) & (flat_img[1:] == 0))\n    starts_ix = np.where(starts)[0] + 2\n    ends_ix = np.where(ends)[0] + 2\n    lengths = ends_ix - starts_ix\n    \n    predicted = \" \".join(map(str, sum(zip(starts_ix, lengths), ())))\n    return {\"Id\": img_id, \"Predicted\": predicted}\n\n\ndef fast_rle(img, img_id):\n    flat_img = img.flatten().astype(np.uint8)\n\n    starts = np.array((flat_img[:-1] == 0) & (flat_img[1:] == 1))\n    ends = np.array((flat_img[:-1] == 1) & (flat_img[1:] == 0))\n    starts_ix = np.where(starts)[0] + 2\n    ends_ix = np.where(ends)[0] + 2\n    lengths = ends_ix - starts_ix\n    predicted_arr = np.stack([starts_ix, lengths]).T.flatten()\n    f = StringIO()\n    np.savetxt(f, predicted_arr.reshape(1, -1), delimiter=\" \", fmt=\"%d\")\n    predicted = f.getvalue().strip()\n    return {\"Id\": img_id, \"Predicted\": predicted}\n","metadata":{"execution":{"iopub.status.busy":"2023-04-05T04:06:03.289722Z","iopub.execute_input":"2023-04-05T04:06:03.290178Z","iopub.status.idle":"2023-04-05T04:06:03.304844Z","shell.execute_reply.started":"2023-04-05T04:06:03.290141Z","shell.execute_reply":"2023-04-05T04:06:03.303273Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Postscript: There are other implementations like https://www.kaggle.com/code/stainsby/fast-tested-rle/notebook . It uses the join function, but it is fast, so it seems that the original function was slow due to the combination with the zip function.","metadata":{}},{"cell_type":"code","source":"def stainsby_rle(img, img_id):\n    pixels = img.flatten()\n    pixels[0] = 0\n    pixels[-1] = 0\n    runs = np.where(pixels[1:] != pixels[:-1])[0] + 2\n    runs[1::2] = runs[1::2] - runs[:-1:2]\n    predicted = ' '.join(str(x) for x in runs)\n    return {\"Id\": img_id, \"Predicted\": predicted}\n\ndef combined_rle(img, img_id):\n    pixels = img.flatten()\n    pixels[0] = 0\n    pixels[-1] = 0\n    runs = np.where(pixels[1:] != pixels[:-1])[0] + 2\n    runs[1::2] = runs[1::2] - runs[:-1:2]\n    f = StringIO()\n    np.savetxt(f, runs.reshape(1, -1), delimiter=\" \", fmt=\"%d\")\n    predicted = f.getvalue().strip()\n    return {\"Id\": img_id, \"Predicted\": predicted}","metadata":{"execution":{"iopub.status.busy":"2023-04-05T04:06:03.308003Z","iopub.execute_input":"2023-04-05T04:06:03.308499Z","iopub.status.idle":"2023-04-05T04:06:03.325777Z","shell.execute_reply.started":"2023-04-05T04:06:03.308442Z","shell.execute_reply":"2023-04-05T04:06:03.324060Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### conversion when precision is good ","metadata":{}},{"cell_type":"code","source":"import numpy as np\nimport matplotlib.pyplot as plt\nfrom PIL import Image\nimport time\n\ndef check_time(img):\n    ref_start = time.time()\n    ref_result = rle(img, \"a\")\n    ref_end = time.time()\n    print(\"rle:\", ref_end - ref_start)\n    \n    start = time.time()\n    result = fast_rle(img, \"a\")\n    end = time.time()\n    ratio = (ref_end - ref_start) / (end - start)\n    print(\"fast_rle:\", end - start, f\"({ratio:.2f} x faster)\")\n    assert ref_result[\"Predicted\"] == result[\"Predicted\"]\n    \n    start = time.time()\n    result = stainsby_rle(img, \"a\")\n    end = time.time()\n    ratio = (ref_end - ref_start) / (end - start)\n    print(\"stainsby's rle:\", end - start, f\"({ratio:.2f} x faster)\")\n    assert ref_result[\"Predicted\"] == result[\"Predicted\"]\n\n    start = time.time()\n    result = combined_rle(img, \"a\")\n    end = time.time()\n    ratio = (ref_end - ref_start) / (end - start)\n    print(\"combined rle:\", end - start, f\"({ratio:.2f} x faster)\")\n    assert ref_result[\"Predicted\"] == result[\"Predicted\"]","metadata":{"execution":{"iopub.status.busy":"2023-04-05T04:06:03.327632Z","iopub.execute_input":"2023-04-05T04:06:03.328025Z","iopub.status.idle":"2023-04-05T04:06:03.344902Z","shell.execute_reply.started":"2023-04-05T04:06:03.327987Z","shell.execute_reply":"2023-04-05T04:06:03.343098Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"img = np.array(Image.open(\"/kaggle/input/vesuvius-challenge-ink-detection/train/1/inklabels.png\"))\nplt.imshow(img, cmap=\"gray\")\nplt.show()\n\ncheck_time(img)","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2023-04-05T04:06:03.347310Z","iopub.execute_input":"2023-04-05T04:06:03.348096Z","iopub.status.idle":"2023-04-05T04:06:11.578085Z","shell.execute_reply.started":"2023-04-05T04:06:03.348044Z","shell.execute_reply":"2023-04-05T04:06:11.576630Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### conversion when precision is bad","metadata":{}},{"cell_type":"code","source":"# add noise to image\nrandom_img = np.random.uniform(size=img.shape)\nthres = 0.001\nimg[random_img > 1 - thres] = 1\nimg[random_img < thres] = 0\n\ncheck_time(img)","metadata":{"execution":{"iopub.status.busy":"2023-04-05T04:06:11.581524Z","iopub.execute_input":"2023-04-05T04:06:11.582255Z","iopub.status.idle":"2023-04-05T04:06:59.656986Z","shell.execute_reply.started":"2023-04-05T04:06:11.582189Z","shell.execute_reply":"2023-04-05T04:06:59.655223Z"},"trusted":true},"execution_count":null,"outputs":[]}]}