{"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":"# Introduction\n\nIn this notebook, we attempt to extract information from dot plots without utilizing any training data. The proposed solution is rule-based which depends on basic morpgological transformations and contour filters. ","metadata":{}},{"cell_type":"markdown","source":"### Libraries","metadata":{}},{"cell_type":"code","source":"import os\nimport cv2\nimport json \nimport shutil\nimport urllib\nimport random\nfrom   tqdm              import tqdm\nimport pandas            as      pd \nimport numpy             as      np\nimport matplotlib.pyplot as      plt","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2023-05-13T15:15:19.251183Z","iopub.execute_input":"2023-05-13T15:15:19.251497Z","iopub.status.idle":"2023-05-13T15:15:19.257764Z","shell.execute_reply.started":"2023-05-13T15:15:19.251476Z","shell.execute_reply":"2023-05-13T15:15:19.256445Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Custom Functions","metadata":{}},{"cell_type":"code","source":"# Return RGB image and its binary version \ndef load_image(img_path):\n    image  = cv2.imread(img_path)\n    gray   = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)\n    binary = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)[1]\n    return image, binary\n\n# Applies morphological transformation\ndef morph_transform(params):\n    kernel = cv2.getStructuringElement(cv2.MORPH_RECT, params['kernel_size'])\n    output = cv2.morphologyEx(params['input'], params['operation'], kernel, iterations=params['iterations'])\n    return output\n\n# Detects contours\ndef contour_detection(params):\n    contours = cv2.findContours(params['input'], mode=params['mode'], method=params['approx'])\n    contours = contours[0] if len(contours) == 2 else contours[1]\n    return contours\n\n# An index-based filter that rejects data with False index\ndef boolean_filter(data, condition):\n    idx = np.where(condition)[0]\n    return [d for i, d in enumerate(data) if i in idx]\n\n# Detects filled shapes (circles/bars/....)\ndef filled_shapes_detection(img):\n    morph_params   = {'kernel_size': (3,3), 'input': img, 'operation': cv2.MORPH_OPEN, 'iterations': 2}\n    contour_params = {'input': morph_transform(morph_params), 'mode': cv2.RETR_TREE, 'approx': cv2.CHAIN_APPROX_NONE}\n    contours       = contour_detection(contour_params)\n    return contours \n\ndef axis_detection(img, min_thresh, max_thresh, axis='x'):\n    kernel_size    = (9, 1) if axis=='x' else (1, 9)\n    id             = 0 if axis=='x' else 1\n    morph_params   = {'kernel_size': kernel_size, 'input': img, 'operation': cv2.MORPH_OPEN, 'iterations': 2}\n    contour_params = {'input': morph_transform(morph_params), 'mode': cv2.RETR_TREE, 'approx': cv2.CHAIN_APPROX_NONE}\n    contours       = contour_detection(contour_params)\n    if not contours:\n        return []\n    length   = np.array([c[:, :, id].max() - c[:, :, id].min() for c in contours])\n    contours = boolean_filter(contours, (min_thresh < length) & (length < max_thresh))\n    if not contours:\n        return []\n    if len(contours) > 1:\n        if id:\n            far_points = np.array([c[:, :, 0].min() for c in contours])\n            contours = boolean_filter(contours, far_points == min(far_points))\n        else:\n            far_points = np.array([c[:, :, 1].max() for c in contours])\n            contours = boolean_filter(contours, far_points == max(far_points))\n    return contours\n\n# Returns a black image with highlighted elements (below x-axis/ next to y-axis)\ndef highlight_axis(img, contour, axis='x'):\n    highlight_img = np.zeros(img.shape, dtype=np.uint8)\n    if axis=='x':\n        start_row = contour[0][:, :, 1].min() \n        start_col = contour[0][:, :, 0].min() \n        end_col   = contour[0][:, :, 0].max() + 1\n        highlight_img[start_row:, start_col:end_col] = img[start_row:, start_col:end_col]\n    else:\n        end_col   = contour[0][:, :, 0].max() + 1 \n        start_row = contour[0][:, :, 1].min() \n        end_row   = contour[0][:, :, 0].max() + 1\n        highlight_img[start_row:end_row, :end_col] = img[start_row:end_row, :end_col]\n    return highlight_img\n\n# Removes x-axis/y-axis line\ndef remove_axis(img, axis='x'):\n    contour_params = {'input': img, 'mode': cv2.RETR_TREE, 'approx': cv2.CHAIN_APPROX_NONE}\n    contours       = contour_detection(contour_params)\n    if axis=='x':\n        start          = [c[:, :, 1].min() for c in contours]\n        axis_line      = boolean_filter(contours, start == min(start))\n        row            = axis_line[0][:, :, 1].max() + 1 \n        img[:row, :]   = 0 \n    else:\n        end            = [c[:, :, 0].max() for c in contours]\n        axis_line      = boolean_filter(contours, end == max(end))\n        col            = axis_line[0][:, :, 0].min() \n        img[:, col:]   = 0 \n    return img\n\ndef text_detection(img, axis='x'):\n    morph_params   = {'kernel_size': (7,7), 'input': img, 'operation': cv2.MORPH_CLOSE, 'iterations': 1}\n    contour_params = {'input': morph_transform(morph_params), 'mode': cv2.RETR_EXTERNAL, 'approx': cv2.CHAIN_APPROX_NONE}\n    contours       = contour_detection(contour_params)\n    tolerance      = 5\n    if axis=='x':\n        start_row  = [c[:, :, 1].min() for c in contours]\n        matches    = np.array([len(np.where(np.abs(start_row - start_row[i]) < tolerance)[0]) for i in range(len(start_row))])\n    else:\n        end_col    = [c[:, :, 0].max() for c in contours]\n        matches    = np.array([len(np.where(np.abs(end_col - end_col[i]) < tolerance)[0]) for i in range(len(end_col))])\n    return boolean_filter(contours, matches == max(matches))\n\n# Returns limits of bounding boxes for text labels\ndef text_limits(contours, axis='x'):\n    id     = 0 if axis=='x' else 1\n    start  = np.array([c[:, :, id].min() for c in contours]) - 2\n    end    = np.array([c[:, :, id].max() for c in contours]) + 3\n    limits = np.sort(np.concatenate([start, end]))\n    return [range(limits[2*i], limits[2*i+1]) for i in range(int(len(limits)/2))]\n","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2023-05-13T15:15:19.285696Z","iopub.execute_input":"2023-05-13T15:15:19.286076Z","iopub.status.idle":"2023-05-13T15:15:19.313435Z","shell.execute_reply.started":"2023-05-13T15:15:19.286052Z","shell.execute_reply":"2023-05-13T15:15:19.312157Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### CSV file generation for dot plots","metadata":{}},{"cell_type":"code","source":"target     = 'dot'\nannotation = '/kaggle/input/benetech-making-graphs-accessible/train/annotations'\ndot_df    = pd.DataFrame()\nfor root, _, files in os.walk(annotation):\n    for name in tqdm(files):       \n        f = os.path.join(root, name)\n        with open(f) as f:\n            d = json.load(f)\n        tt = pd.json_normalize(d)\n        if tt['chart-type'].values == target:\n            tt['file']= name.split('.')[0]\n            tt['x']   = ';'.join([str(i['x']) for i in tt['data-series'].values[0]])\n            tt['y']   = ';'.join([str(j['y']) for j in tt['data-series'].values[0]])\n            dot_df    = pd.concat([dot_df, tt[['file', 'x', 'y']]], axis=0)\ndot_df.head()","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2023-05-13T15:15:19.505138Z","iopub.execute_input":"2023-05-13T15:15:19.505452Z","iopub.status.idle":"2023-05-13T15:18:15.737528Z","shell.execute_reply.started":"2023-05-13T15:15:19.505427Z","shell.execute_reply":"2023-05-13T15:18:15.736332Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Model","metadata":{}},{"cell_type":"code","source":"class DotSolver:\n    def __init__(self, path):\n        self.img, self.binary = load_image(path)\n\n        self.candidates      = filled_shapes_detection(self.binary)\n        self.dot_contours    = self.filter_dots() if self.candidates else []\n        self.y_map           = self.count_dots() if self.dot_contours else []\n\n        min_threshold        = self.get_min_threshold() if self.dot_contours else int(self.binary.shape[1]) / 4\n        max_threshold        = int(self.binary.shape[1]) - 2\n        self.x_axis_contour  = axis_detection(self.binary, min_threshold, max_threshold, axis='x')\n        self.x_axis          = highlight_axis(self.binary, self.x_axis_contour, axis='x')\n        self.x_labels        = remove_axis(self.x_axis.copy(), axis='x')\n        self.x_text_contours = text_detection(self.x_labels, axis='x')\n        self.x_range         = text_limits(self.x_text_contours, axis='x')\n\n        self.y_series        = self.solve_y() \n\n    # Returns dot contours via area filtering (threshold = 0.8 * max(area))\n    def filter_dots(self):\n        area = np.array([cv2.contourArea(c) for c in self.candidates])\n        threshold = 0.8 * max(area)  \n        return boolean_filter(self.candidates, area > threshold)\n  \n    # Returns the center of the column and y value of the column\n    def count_dots(self):\n        dots      = [cv2.minEnclosingCircle(c) for c in self.dot_contours]\n        centers   = np.array([np.int32(np.round(d[0])) for d in dots])\n        radii     = np.array([np.int32(np.round(d[1])) for d in dots])\n        tolerance = int(np.mean(radii))\n        center_x  = centers[:, 0]\n        mapping = {'x_center': [], 'y_count': []}\n        move = True\n        while move:\n            min_x = min(center_x)\n            idx = np.where(np.abs(center_x - min_x) < tolerance)[0]\n            mapping['x_center'].append(min_x)\n            mapping['y_count'].append(len(idx))\n            center_x = [c for i, c in enumerate(center_x) if i not in idx]\n            move = True if center_x else False\n        return mapping\n\n    # Computes the minimum length of horizontal line for x-axis consideration\n    def get_min_threshold(self):\n        end = max([c[:, :, 0].max() for c in self.dot_contours])\n        start = min([c[:, :, 0].min() for c in self.dot_contours])\n        return end - start\n\n    # Returns y-series\n    def solve_y(self):\n        if len(self.x_range) > len(self.y_map['x_center']):\n            check = [any([j in i for j in self.y_map['x_center']]) for i in self.x_range]\n            return [self.y_map['y_count'].pop(0) if i else 0 for i in check]\n        else:\n            return self.y_map['y_count']","metadata":{"execution":{"iopub.status.busy":"2023-05-13T15:18:15.740098Z","iopub.execute_input":"2023-05-13T15:18:15.741189Z","iopub.status.idle":"2023-05-13T15:18:15.758878Z","shell.execute_reply.started":"2023-05-13T15:18:15.741157Z","shell.execute_reply":"2023-05-13T15:18:15.758175Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Load a dot plot","metadata":{}},{"cell_type":"code","source":"img_files = dot_df.file.values\ntrue_y    = dot_df.y.values\nnumber    = 25\nmain_path = '/kaggle/input/benetech-making-graphs-accessible/train/images/'\nimage_path= main_path + img_files[number] + '.jpg'\nresult    = DotSolver(image_path)","metadata":{"execution":{"iopub.status.busy":"2023-05-13T15:18:15.760467Z","iopub.execute_input":"2023-05-13T15:18:15.760939Z","iopub.status.idle":"2023-05-13T15:18:15.796975Z","shell.execute_reply.started":"2023-05-13T15:18:15.760917Z","shell.execute_reply":"2023-05-13T15:18:15.796043Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"img, binary = load_image(image_path)\nplt.imshow(img);\nplt.axis('off');","metadata":{"execution":{"iopub.status.busy":"2023-05-13T15:18:15.800127Z","iopub.execute_input":"2023-05-13T15:18:15.800626Z","iopub.status.idle":"2023-05-13T15:18:15.930610Z","shell.execute_reply.started":"2023-05-13T15:18:15.800596Z","shell.execute_reply":"2023-05-13T15:18:15.930040Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Morphological Transformation\nA filled shape could be easily detected using a morphological open operation. The operation is equivalent to erosion followed by dilation. Check this [source](https://docs.opencv.org/4.x/d9/d61/tutorial_py_morphological_ops.html) for more information on morphological transformations.","metadata":{}},{"cell_type":"code","source":"morph_params    = {'kernel_size': (3,3), 'input': binary, 'operation': cv2.MORPH_OPEN, 'iterations': 2}\ntransformed_img = morph_transform(morph_params)\nplt.imshow(transformed_img);\nplt.axis('off');","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2023-05-13T15:18:15.931650Z","iopub.execute_input":"2023-05-13T15:18:15.932055Z","iopub.status.idle":"2023-05-13T15:18:16.025879Z","shell.execute_reply.started":"2023-05-13T15:18:15.932029Z","shell.execute_reply":"2023-05-13T15:18:16.025183Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The above figure shows the dots only. However, there could be some additional small dots from large bold text regions, therefore additional processing would guarantee the detection of dots only. The proposed model solves this issue via contour detection and area filtration.","metadata":{}},{"cell_type":"code","source":"cv2.drawContours(image=result.img, contours=result.dot_contours, contourIdx=-1, color=(0, 0, 255), thickness=2, lineType=cv2.LINE_AA)\nplt.imshow(result.img);\nplt.axis('off');","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2023-05-13T15:18:16.027019Z","iopub.execute_input":"2023-05-13T15:18:16.027416Z","iopub.status.idle":"2023-05-13T15:18:16.161775Z","shell.execute_reply.started":"2023-05-13T15:18:16.027390Z","shell.execute_reply":"2023-05-13T15:18:16.160694Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Axis and Label Detection\n\nThere are many methods that could be used to detect horizontal and vertical lines. However, we use morphological transform for consistency. The detection of axis is considered a pre-processing step for label detetion.","metadata":{}},{"cell_type":"code","source":"cv2.drawContours(image=result.img, contours=result.x_axis_contour, contourIdx=-1, color=(0, 0, 255), thickness=2, lineType=cv2.LINE_AA)\ncv2.drawContours(image=result.img, contours=result.x_text_contours, contourIdx=-1, color=(0, 0, 255), thickness=2, lineType=cv2.LINE_AA)\nplt.imshow(result.img);\nplt.axis('off');","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2023-05-13T15:18:16.163205Z","iopub.execute_input":"2023-05-13T15:18:16.163475Z","iopub.status.idle":"2023-05-13T15:18:16.304144Z","shell.execute_reply.started":"2023-05-13T15:18:16.163450Z","shell.execute_reply":"2023-05-13T15:18:16.303033Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Y-series generation\nAfter vertically counting the dots in the plot, the centers of dots are matched to the bounding boxes of x-axis text. This step is essential for post-processing x-lables that have zero dots. ","metadata":{}},{"cell_type":"code","source":"predict_y = ';'.join([str(i) for i in result.y_series])\nprint(f'Predicted Y-series: {predict_y}')\nprint(f'True Y-series:      {true_y[number]}')","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2023-05-13T15:18:16.305544Z","iopub.execute_input":"2023-05-13T15:18:16.305826Z","iopub.status.idle":"2023-05-13T15:18:16.312776Z","shell.execute_reply.started":"2023-05-13T15:18:16.305800Z","shell.execute_reply":"2023-05-13T15:18:16.311341Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Since x-labels were already detected, all that's left is passing the detected text to OCR ([easyocr](https://github.com/JaidedAI/EasyOCR), [keras_ocr](https://github.com/faustomorales/keras-ocr), [pytesseract](https://github.com/madmaze/pytesseract)). Additionally, this dataset could be used to compare OCR methods. Note that the OCR step is not implemented yet.","metadata":{}},{"cell_type":"markdown","source":"# Conclusion\n1. DotSolver does not require any training data.\n2. The model is a rule-based solution that expects a filled geometric shape for analysis. If the dot is replaced by a hollow circle, the output of first transformation will probably result in zeros. However, since dot plots are mainly defined to be color-filled circles this will not be a concern.\n3. The y-series might be slighly inaccurate if there is something covering the dots. There are very few samples that contain this case in the generated dataset.\n4. While the DotSolver accounts for y-axis detection, the function is written only for the case of horizontal bar charts. However, y-axis and y-label detection is not required to get the y-series for dot plots.\n5. The model performed well with low resolution and compressed dot plots in the generated dataset as long as point 3 is excluded.\n6. While horizontal bars could be solved using some principles from DotSolver, the final step for series generation will require interpolation instead of simple interpolation.","metadata":{}},{"cell_type":"markdown","source":"# Random Testing","metadata":{}},{"cell_type":"code","source":"number    = random.randint(0,len(dot_df)-1)\nimage_path= main_path + img_files[number] + '.jpg'\nresult    = DotSolver(image_path)\ncv2.drawContours(image=result.img, contours=result.dot_contours, contourIdx=-1, color=(0, 0, 255), thickness=2, lineType=cv2.LINE_AA)\ncv2.drawContours(image=result.img, contours=result.x_axis_contour, contourIdx=-1, color=(0, 0, 255), thickness=2, lineType=cv2.LINE_AA)\ncv2.drawContours(image=result.img, contours=result.x_text_contours, contourIdx=-1, color=(0, 0, 255), thickness=2, lineType=cv2.LINE_AA)\nplt.imshow(result.img);\nplt.axis('off');\npredict_y = ';'.join([str(i) for i in result.y_series])\nprint(f'Predicted Y-series: {predict_y}')\nprint(f'True Y-series:      {true_y[number]}')","metadata":{"execution":{"iopub.status.busy":"2023-05-13T15:18:16.314604Z","iopub.execute_input":"2023-05-13T15:18:16.315483Z","iopub.status.idle":"2023-05-13T15:18:16.476483Z","shell.execute_reply.started":"2023-05-13T15:18:16.315452Z","shell.execute_reply":"2023-05-13T15:18:16.475732Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Thank you for reaching the end. Hope you found it helpful.","metadata":{}},{"cell_type":"code","source":"","metadata":{},"execution_count":null,"outputs":[]}]}