""" Copyright (C) 2021 Microsoft Corporation """ from collections import defaultdict from fitz import Rect def apply_threshold(objects, threshold): """ Filter out objects below a certain score. """ return [obj for obj in objects if obj['score'] >= threshold] def apply_class_thresholds(bboxes, labels, scores, class_names, class_thresholds): """ Filter out bounding boxes whose confidence is below the confidence threshold for its associated class label. """ # Apply class-specific thresholds indices_above_threshold = [idx for idx, (score, label) in enumerate(zip(scores, labels)) if score >= class_thresholds[ class_names[label] ] ] bboxes = [bboxes[idx] for idx in indices_above_threshold] scores = [scores[idx] for idx in indices_above_threshold] labels = [labels[idx] for idx in indices_above_threshold] return bboxes, scores, labels def iou(bbox1, bbox2): """ Compute the intersection-over-union of two bounding boxes. """ intersection = Rect(bbox1).intersect(bbox2) union = Rect(bbox1).include_rect(bbox2) union_area = union.get_area() # getArea() if union_area > 0: return intersection.get_area() / union.get_area() # .getArea() return 0 def iob(bbox1, bbox2): """ Compute the intersection area over box area, for bbox1. """ intersection = Rect(bbox1).intersect(bbox2) bbox1_area = Rect(bbox1).get_area() # .getArea() if bbox1_area > 0: return intersection.get_area() / bbox1_area # getArea() return 0 def objects_to_cells(table, objects_in_table, tokens_in_table, class_map, class_thresholds): """ Process the bounding boxes produced by the table structure recognition model and the token/word/span bounding boxes into table cells. Also return a confidence score based on how well the text was able to be uniquely slotted into the cells detected by the table model. """ table_structures = objects_to_table_structures(table, objects_in_table, tokens_in_table, class_map, class_thresholds) # Check for a valid table if len(table_structures['columns']) < 1 or len(table_structures['rows']) < 1: cells = []#None confidence_score = 0 else: cells, confidence_score = table_structure_to_cells(table_structures, tokens_in_table, table['bbox']) return table_structures, cells, confidence_score def objects_to_table_structures(table_object, objects_in_table, tokens_in_table, class_names, class_thresholds): """ Process the bounding boxes produced by the table structure recognition model into a *consistent* set of table structures (rows, columns, supercells, headers). This entails resolving conflicts/overlaps, and ensuring the boxes meet certain alignment conditions (for example: rows should all have the same width, etc.). """ page_num = table_object['page_num'] table_structures = {} columns = [obj for obj in objects_in_table if class_names[obj['label']] == 'table column'] rows = [obj for obj in objects_in_table if class_names[obj['label']] == 'table row'] headers = [obj for obj in objects_in_table if class_names[obj['label']] == 'table column header'] supercells = [obj for obj in objects_in_table if class_names[obj['label']] == 'table spanning cell'] for obj in supercells: obj['subheader'] = False subheaders = [obj for obj in objects_in_table if class_names[obj['label']] == 'table projected row header'] for obj in subheaders: obj['subheader'] = True supercells += subheaders for obj in rows: obj['header'] = False for header_obj in headers: if iob(obj['bbox'], header_obj['bbox']) >= 0.5: obj['header'] = True for row in rows: row['page'] = page_num for column in columns: column['page'] = page_num #Refine table structures rows = refine_rows(rows, tokens_in_table, class_thresholds['table row']) columns = refine_columns(columns, tokens_in_table, class_thresholds['table column']) # Shrink table bbox to just the total height of the rows # and the total width of the columns row_rect = Rect() for obj in rows: row_rect.include_rect(obj['bbox']) column_rect = Rect() for obj in columns: column_rect.include_rect(obj['bbox']) table_object['row_column_bbox'] = [column_rect[0], row_rect[1], column_rect[2], row_rect[3]] table_object['bbox'] = table_object['row_column_bbox'] # Process the rows and columns into a complete segmented table columns = align_columns(columns, table_object['row_column_bbox']) rows = align_rows(rows, table_object['row_column_bbox']) table_structures['rows'] = rows table_structures['columns'] = columns table_structures['headers'] = headers table_structures['supercells'] = supercells if len(rows) > 0 and len(columns) > 1: table_structures = refine_table_structures(table_object['bbox'], table_structures, tokens_in_table, class_thresholds) return table_structures def refine_rows(rows, page_spans, score_threshold): """ Apply operations to the detected rows, such as thresholding, NMS, and alignment. """ #MODIFY rows = [obj for obj in rows if obj['score'] >= score_threshold or obj['header']] ### rows = nms_by_containment(rows, page_spans, overlap_threshold=0.5) # remove_objects_without_content(page_spans, rows) # TODO if len(rows) > 1: rows = sort_objects_top_to_bottom(rows) return rows def refine_columns(columns, page_spans, score_threshold): """ Apply operations to the detected columns, such as thresholding, NMS, and alignment. """ #MODIFY columns = [obj for obj in columns if obj['score'] >= score_threshold] ### columns = nms_by_containment(columns, page_spans, overlap_threshold=0.5) # remove_objects_without_content(page_spans, columns) # TODO if len(columns) > 1: columns = sort_objects_left_to_right(columns) return columns def nms_by_containment(container_objects, package_objects, overlap_threshold=0.5): """ Non-maxima suppression (NMS) of objects based on shared containment of other objects. """ container_objects = sort_objects_by_score(container_objects) num_objects = len(container_objects) suppression = [False for obj in container_objects] packages_by_container, _, _ = slot_into_containers(container_objects, package_objects, overlap_threshold=overlap_threshold, unique_assignment=True, forced_assignment=False) for object2_num in range(1, num_objects): object2_packages = set(packages_by_container[object2_num]) if len(object2_packages) == 0: suppression[object2_num] = True for object1_num in range(object2_num): if not suppression[object1_num]: object1_packages = set(packages_by_container[object1_num]) if len(object2_packages.intersection(object1_packages)) > 0: suppression[object2_num] = True final_objects = [obj for idx, obj in enumerate(container_objects) if not suppression[idx]] return final_objects def slot_into_containers(container_objects, package_objects, overlap_threshold=0.5, unique_assignment=True, forced_assignment=False): """ Slot a collection of objects into the container they occupy most (the container which holds the largest fraction of the object). """ best_match_scores = [] container_assignments = [[] for container in container_objects] package_assignments = [[] for package in package_objects] if len(container_objects) == 0 or len(package_objects) == 0: return container_assignments, package_assignments, best_match_scores match_scores = defaultdict(dict) for package_num, package in enumerate(package_objects): match_scores = [] package_rect = Rect(package['bbox']) package_area = package_rect.get_area() # getArea() for container_num, container in enumerate(container_objects): container_rect = Rect(container['bbox']) intersect_area = container_rect.intersect(package['bbox']).get_area() # getArea() overlap_fraction = intersect_area / package_area match_scores.append({'container': container, 'container_num': container_num, 'score': overlap_fraction}) sorted_match_scores = sort_objects_by_score(match_scores) best_match_score = sorted_match_scores[0] best_match_scores.append(best_match_score['score']) if forced_assignment or best_match_score['score'] >= overlap_threshold: container_assignments[best_match_score['container_num']].append(package_num) package_assignments[package_num].append(best_match_score['container_num']) if not unique_assignment: # slot package into all eligible slots for match_score in sorted_match_scores[1:]: if match_score['score'] >= overlap_threshold: container_assignments[match_score['container_num']].append(package_num) package_assignments[package_num].append(match_score['container_num']) else: break return container_assignments, package_assignments, best_match_scores def sort_objects_by_score(objects, reverse=True): """ Put any set of objects in order from high score to low score. """ if reverse: sign = -1 else: sign = 1 return sorted(objects, key=lambda k: sign*k['score']) def remove_objects_without_content(page_spans, objects): """ Remove any objects (these can be rows, columns, supercells, etc.) that don't have any text associated with them. """ for obj in objects[:]: object_text, _ = extract_text_inside_bbox(page_spans, obj['bbox']) if len(object_text.strip()) == 0: objects.remove(obj) def extract_text_inside_bbox(spans, bbox): """ Extract the text inside a bounding box. """ bbox_spans = get_bbox_span_subset(spans, bbox) bbox_text = extract_text_from_spans(bbox_spans, remove_integer_superscripts=True) return bbox_text, bbox_spans def get_bbox_span_subset(spans, bbox, threshold=0.5): """ Reduce the set of spans to those that fall within a bounding box. threshold: the fraction of the span that must overlap with the bbox. """ span_subset = [] for span in spans: if overlaps(span['bbox'], bbox, threshold): span_subset.append(span) return span_subset def overlaps(bbox1, bbox2, threshold=0.5): """ Test if more than "threshold" fraction of bbox1 overlaps with bbox2. """ rect1 = Rect(list(bbox1)) area1 = rect1.get_area() # .getArea() if area1 == 0: return False return rect1.intersect(list(bbox2)).get_area()/area1 >= threshold # getArea() def extract_text_from_spans(spans, join_with_space=True, remove_integer_superscripts=True): """ Convert a collection of page tokens/words/spans into a single text string. """ if join_with_space: join_char = " " else: join_char = "" spans_copy = spans[:] if remove_integer_superscripts: for span in spans: flags = span['flags'] if flags & 2**0: # superscript flag if is_int(span['text']): spans_copy.remove(span) else: span['superscript'] = True if len(spans_copy) == 0: return "" spans_copy.sort(key=lambda span: span['span_num']) spans_copy.sort(key=lambda span: span['line_num']) spans_copy.sort(key=lambda span: span['block_num']) # Force the span at the end of every line within a block to have exactly one space # unless the line ends with a space or ends with a non-space followed by a hyphen line_texts = [] line_span_texts = [spans_copy[0]['text']] for span1, span2 in zip(spans_copy[:-1], spans_copy[1:]): if not span1['block_num'] == span2['block_num'] or not span1['line_num'] == span2['line_num']: line_text = join_char.join(line_span_texts).strip() if (len(line_text) > 0 and not line_text[-1] == ' ' and not (len(line_text) > 1 and line_text[-1] == "-" and not line_text[-2] == ' ')): if not join_with_space: line_text += ' ' line_texts.append(line_text) line_span_texts = [span2['text']] else: line_span_texts.append(span2['text']) line_text = join_char.join(line_span_texts) line_texts.append(line_text) return join_char.join(line_texts).strip() def sort_objects_left_to_right(objs): """ Put the objects in order from left to right. """ return sorted(objs, key=lambda k: k['bbox'][0] + k['bbox'][2]) def sort_objects_top_to_bottom(objs): """ Put the objects in order from top to bottom. """ return sorted(objs, key=lambda k: k['bbox'][1] + k['bbox'][3]) def align_columns(columns, bbox): """ For every column, align the top and bottom boundaries to the final table bounding box. """ try: for column in columns: column['bbox'][1] = bbox[1] column['bbox'][3] = bbox[3] except Exception as err: print("Could not align columns: {}".format(err)) pass return columns def align_rows(rows, bbox): """ For every row, align the left and right boundaries to the final table bounding box. """ try: for row in rows: row['bbox'][0] = bbox[0] row['bbox'][2] = bbox[2] except Exception as err: print("Could not align rows: {}".format(err)) pass return rows def refine_table_structures(table_bbox, table_structures, page_spans, class_thresholds): """ Apply operations to the detected table structure objects such as thresholding, NMS, and alignment. """ rows = table_structures["rows"] columns = table_structures['columns'] #columns = fill_column_gaps(columns, table_bbox) #rows = fill_row_gaps(rows, table_bbox) # Process the headers headers = table_structures['headers'] headers = apply_threshold(headers, class_thresholds["table column header"]) headers = nms(headers) headers = align_headers(headers, rows) # Process supercells supercells = [elem for elem in table_structures['supercells'] if not elem['subheader']] subheaders = [elem for elem in table_structures['supercells'] if elem['subheader']] supercells = apply_threshold(supercells, class_thresholds["table spanning cell"]) subheaders = apply_threshold(subheaders, class_thresholds["table projected row header"]) supercells += subheaders # Align before NMS for supercells because alignment brings them into agreement # with rows and columns first; if supercells still overlap after this operation, # the threshold for NMS can basically be lowered to just above 0 supercells = align_supercells(supercells, rows, columns) supercells = nms_supercells(supercells) header_supercell_tree(supercells) table_structures['columns'] = columns table_structures['rows'] = rows table_structures['supercells'] = supercells table_structures['headers'] = headers return table_structures def nms(objects, match_criteria="object2_overlap", match_threshold=0.05, keep_metric="score", keep_higher=True): """ A customizable version of non-maxima suppression (NMS). Default behavior: If a lower-confidence object overlaps more than 5% of its area with a higher-confidence object, remove the lower-confidence object. objects: set of dicts; each object dict must have a 'bbox' and a 'score' field match_criteria: how to measure how much two objects "overlap" match_threshold: the cutoff for determining that overlap requires suppression of one object keep_metric: which metric to use to determine the object to keep keep_higher: if True, keep the object with the higher metric; otherwise, keep the lower """ if len(objects) == 0: return [] if keep_metric=="score": objects = sort_objects_by_score(objects, reverse=keep_higher) elif keep_metric=="area": objects = sort_objects_by_area(objects, reverse=keep_higher) num_objects = len(objects) suppression = [False for obj in objects] for object2_num in range(1, num_objects): object2_rect = Rect(objects[object2_num]['bbox']) object2_area = object2_rect.get_area() # .getArea() for object1_num in range(object2_num): if not suppression[object1_num]: object1_rect = Rect(objects[object1_num]['bbox']) object1_area = object1_rect.get_area() # .getArea() intersect_area = object1_rect.intersect(object2_rect).get_area() # .getArea() try: if match_criteria=="object1_overlap": metric = intersect_area / object1_area elif match_criteria=="object2_overlap": metric = intersect_area / object2_area elif match_criteria=="iou": metric = intersect_area / (object1_area + object2_area - intersect_area) if metric >= match_threshold: suppression[object2_num] = True break except Exception: # Intended to recover from divide-by-zero pass return [obj for idx, obj in enumerate(objects) if not suppression[idx]] def align_headers(headers, rows): """ Adjust the header boundary to be the convex hull of the rows it intersects at least 50% of the height of. For now, we are not supporting tables with multiple headers, so we need to eliminate anything besides the top-most header. """ aligned_headers = [] for row in rows: row['header'] = False header_row_nums = [] for header in headers: for row_num, row in enumerate(rows): row_height = row['bbox'][3] - row['bbox'][1] min_row_overlap = max(row['bbox'][1], header['bbox'][1]) max_row_overlap = min(row['bbox'][3], header['bbox'][3]) overlap_height = max_row_overlap - min_row_overlap if overlap_height / row_height >= 0.5: header_row_nums.append(row_num) if len(header_row_nums) == 0: return aligned_headers header_rect = Rect() if header_row_nums[0] > 0: header_row_nums = list(range(header_row_nums[0]+1)) + header_row_nums last_row_num = -1 for row_num in header_row_nums: if row_num == last_row_num + 1: row = rows[row_num] row['header'] = True header_rect = header_rect.include_rect(row['bbox']) last_row_num = row_num else: # Break as soon as a non-header row is encountered. # This ignores any subsequent rows in the table labeled as a header. # Having more than 1 header is not supported currently. break header = {'bbox': list(header_rect)} aligned_headers.append(header) return aligned_headers def align_supercells(supercells, rows, columns): """ For each supercell, align it to the rows it intersects 50% of the height of, and the columns it intersects 50% of the width of. Eliminate supercells for which there are no rows and columns it intersects 50% with. """ aligned_supercells = [] for supercell in supercells: supercell['header'] = False row_bbox_rect = None col_bbox_rect = None intersecting_header_rows = set() intersecting_data_rows = set() for row_num, row in enumerate(rows): row_height = row['bbox'][3] - row['bbox'][1] supercell_height = supercell['bbox'][3] - supercell['bbox'][1] min_row_overlap = max(row['bbox'][1], supercell['bbox'][1]) max_row_overlap = min(row['bbox'][3], supercell['bbox'][3]) overlap_height = max_row_overlap - min_row_overlap if 'span' in supercell: overlap_fraction = max(overlap_height/row_height, overlap_height/supercell_height) else: overlap_fraction = overlap_height / row_height if overlap_fraction >= 0.5: if 'header' in row and row['header']: intersecting_header_rows.add(row_num) else: intersecting_data_rows.add(row_num) # Supercell cannot span across the header boundary; eliminate whichever # group of rows is the smallest supercell['header'] = False if len(intersecting_data_rows) > 0 and len(intersecting_header_rows) > 0: if len(intersecting_data_rows) > len(intersecting_header_rows): intersecting_header_rows = set() else: intersecting_data_rows = set() if len(intersecting_header_rows) > 0: supercell['header'] = True elif 'span' in supercell: continue # Require span supercell to be in the header intersecting_rows = intersecting_data_rows.union(intersecting_header_rows) # Determine vertical span of aligned supercell for row_num in intersecting_rows: if row_bbox_rect is None: row_bbox_rect = Rect(rows[row_num]['bbox']) else: row_bbox_rect = row_bbox_rect.include_rect(rows[row_num]['bbox']) if row_bbox_rect is None: continue intersecting_cols = [] for col_num, col in enumerate(columns): col_width = col['bbox'][2] - col['bbox'][0] supercell_width = supercell['bbox'][2] - supercell['bbox'][0] min_col_overlap = max(col['bbox'][0], supercell['bbox'][0]) max_col_overlap = min(col['bbox'][2], supercell['bbox'][2]) overlap_width = max_col_overlap - min_col_overlap if 'span' in supercell: overlap_fraction = max(overlap_width/col_width, overlap_width/supercell_width) # Multiply by 2 effectively lowers the threshold to 0.25 if supercell['header']: overlap_fraction = overlap_fraction * 2 else: overlap_fraction = overlap_width / col_width if overlap_fraction >= 0.5: intersecting_cols.append(col_num) if col_bbox_rect is None: col_bbox_rect = Rect(col['bbox']) else: col_bbox_rect = col_bbox_rect.include_rect(col['bbox']) if col_bbox_rect is None: continue supercell_bbox = list(row_bbox_rect.intersect(col_bbox_rect)) supercell['bbox'] = supercell_bbox # Only a true supercell if it joins across multiple rows or columns if (len(intersecting_rows) > 0 and len(intersecting_cols) > 0 and (len(intersecting_rows) > 1 or len(intersecting_cols) > 1)): supercell['row_numbers'] = list(intersecting_rows) supercell['column_numbers'] = intersecting_cols aligned_supercells.append(supercell) # A span supercell in the header means there must be supercells above it in the header if 'span' in supercell and supercell['header'] and len(supercell['column_numbers']) > 1: for row_num in range(0, min(supercell['row_numbers'])): new_supercell = {'row_numbers': [row_num], 'column_numbers': supercell['column_numbers'], 'score': supercell['score'], 'propagated': True} new_supercell_columns = [columns[idx] for idx in supercell['column_numbers']] new_supercell_rows = [rows[idx] for idx in supercell['row_numbers']] bbox = [min([column['bbox'][0] for column in new_supercell_columns]), min([row['bbox'][1] for row in new_supercell_rows]), max([column['bbox'][2] for column in new_supercell_columns]), max([row['bbox'][3] for row in new_supercell_rows])] new_supercell['bbox'] = bbox aligned_supercells.append(new_supercell) return aligned_supercells def nms_supercells(supercells): """ A NMS scheme for supercells that first attempts to shrink supercells to resolve overlap. If two supercells overlap the same (sub)cell, shrink the lower confidence supercell to resolve the overlap. If shrunk supercell is empty, remove it. """ supercells = sort_objects_by_score(supercells) num_supercells = len(supercells) suppression = [False for supercell in supercells] for supercell2_num in range(1, num_supercells): supercell2 = supercells[supercell2_num] for supercell1_num in range(supercell2_num): supercell1 = supercells[supercell1_num] remove_supercell_overlap(supercell1, supercell2) if ((len(supercell2['row_numbers']) < 2 and len(supercell2['column_numbers']) < 2) or len(supercell2['row_numbers']) == 0 or len(supercell2['column_numbers']) == 0): suppression[supercell2_num] = True return [obj for idx, obj in enumerate(supercells) if not suppression[idx]] def header_supercell_tree(supercells): """ Make sure no supercell in the header is below more than one supercell in any row above it. The cells in the header form a tree, but a supercell with more than one supercell in a row above it means that some cell has more than one parent, which is not allowed. Eliminate any supercell that would cause this to be violated. """ header_supercells = [supercell for supercell in supercells if 'header' in supercell and supercell['header']] header_supercells = sort_objects_by_score(header_supercells) for header_supercell in header_supercells[:]: ancestors_by_row = defaultdict(int) min_row = min(header_supercell['row_numbers']) for header_supercell2 in header_supercells: max_row2 = max(header_supercell2['row_numbers']) if max_row2 < min_row: if (set(header_supercell['column_numbers']).issubset( set(header_supercell2['column_numbers']))): for row2 in header_supercell2['row_numbers']: ancestors_by_row[row2] += 1 for row in range(0, min_row): if not ancestors_by_row[row] == 1: supercells.remove(header_supercell) break def table_structure_to_cells(table_structures, table_spans, table_bbox): """ Assuming the row, column, supercell, and header bounding boxes have been refined into a set of consistent table structures, process these table structures into table cells. This is a universal representation format for the table, which can later be exported to Pandas or CSV formats. Classify the cells as header/access cells or data cells based on if they intersect with the header bounding box. """ columns = table_structures['columns'] rows = table_structures['rows'] supercells = table_structures['supercells'] cells = [] subcells = [] # Identify complete cells and subcells for column_num, column in enumerate(columns): for row_num, row in enumerate(rows): column_rect = Rect(list(column['bbox'])) row_rect = Rect(list(row['bbox'])) cell_rect = row_rect.intersect(column_rect) header = 'header' in row and row['header'] cell = {'bbox': list(cell_rect), 'column_nums': [column_num], 'row_nums': [row_num], 'header': header} cell['subcell'] = False for supercell in supercells: supercell_rect = Rect(list(supercell['bbox'])) if (supercell_rect.intersect(cell_rect).get_area() # .getArea() / cell_rect.get_area()) > 0.5: # getArea() cell['subcell'] = True break if cell['subcell']: subcells.append(cell) else: #cell_text = extract_text_inside_bbox(table_spans, cell['bbox']) #cell['cell_text'] = cell_text cell['subheader'] = False cells.append(cell) for supercell in supercells: supercell_rect = Rect(list(supercell['bbox'])) cell_columns = set() cell_rows = set() cell_rect = None header = True for subcell in subcells: subcell_rect = Rect(list(subcell['bbox'])) subcell_rect_area = subcell_rect.get_area() # .getArea() if (subcell_rect.intersect(supercell_rect).get_area() # .getArea() / subcell_rect_area) > 0.5: if cell_rect is None: cell_rect = Rect(list(subcell['bbox'])) else: cell_rect.include_rect(Rect(list(subcell['bbox']))) cell_rows = cell_rows.union(set(subcell['row_nums'])) cell_columns = cell_columns.union(set(subcell['column_nums'])) # By convention here, all subcells must be classified # as header cells for a supercell to be classified as a header cell; # otherwise, this could lead to a non-rectangular header region header = header and 'header' in subcell and subcell['header'] if len(cell_rows) > 0 and len(cell_columns) > 0: cell = {'bbox': list(cell_rect), 'column_nums': list(cell_columns), 'row_nums': list(cell_rows), 'header': header, 'subheader': supercell['subheader']} cells.append(cell) # Compute a confidence score based on how well the page tokens # slot into the cells reported by the model _, _, cell_match_scores = slot_into_containers(cells, table_spans) try: mean_match_score = sum(cell_match_scores) / len(cell_match_scores) min_match_score = min(cell_match_scores) confidence_score = (mean_match_score + min_match_score)/2 except: confidence_score = 0 # Dilate rows and columns before final extraction #dilated_columns = fill_column_gaps(columns, table_bbox) dilated_columns = columns #dilated_rows = fill_row_gaps(rows, table_bbox) dilated_rows = rows for cell in cells: column_rect = Rect() for column_num in cell['column_nums']: column_rect.include_rect(list(dilated_columns[column_num]['bbox'])) row_rect = Rect() for row_num in cell['row_nums']: row_rect.include_rect(list(dilated_rows[row_num]['bbox'])) cell_rect = column_rect.intersect(row_rect) cell['bbox'] = list(cell_rect) span_nums_by_cell, _, _ = slot_into_containers(cells, table_spans, overlap_threshold=0.001, unique_assignment=True, forced_assignment=False) for cell, cell_span_nums in zip(cells, span_nums_by_cell): cell_spans = [table_spans[num] for num in cell_span_nums] # TODO: Refine how text is extracted; should be character-based, not span-based; # but need to associate # cell['cell_text'] = extract_text_from_spans(cell_spans, remove_integer_superscripts=False) # TODO cell['spans'] = cell_spans # Adjust the row, column, and cell bounding boxes to reflect the extracted text num_rows = len(rows) rows = sort_objects_top_to_bottom(rows) num_columns = len(columns) columns = sort_objects_left_to_right(columns) min_y_values_by_row = defaultdict(list) max_y_values_by_row = defaultdict(list) min_x_values_by_column = defaultdict(list) max_x_values_by_column = defaultdict(list) for cell in cells: min_row = min(cell["row_nums"]) max_row = max(cell["row_nums"]) min_column = min(cell["column_nums"]) max_column = max(cell["column_nums"]) for span in cell['spans']: min_x_values_by_column[min_column].append(span['bbox'][0]) min_y_values_by_row[min_row].append(span['bbox'][1]) max_x_values_by_column[max_column].append(span['bbox'][2]) max_y_values_by_row[max_row].append(span['bbox'][3]) for row_num, row in enumerate(rows): if len(min_x_values_by_column[0]) > 0: row['bbox'][0] = min(min_x_values_by_column[0]) if len(min_y_values_by_row[row_num]) > 0: row['bbox'][1] = min(min_y_values_by_row[row_num]) if len(max_x_values_by_column[num_columns-1]) > 0: row['bbox'][2] = max(max_x_values_by_column[num_columns-1]) if len(max_y_values_by_row[row_num]) > 0: row['bbox'][3] = max(max_y_values_by_row[row_num]) for column_num, column in enumerate(columns): if len(min_x_values_by_column[column_num]) > 0: column['bbox'][0] = min(min_x_values_by_column[column_num]) if len(min_y_values_by_row[0]) > 0: column['bbox'][1] = min(min_y_values_by_row[0]) if len(max_x_values_by_column[column_num]) > 0: column['bbox'][2] = max(max_x_values_by_column[column_num]) if len(max_y_values_by_row[num_rows-1]) > 0: column['bbox'][3] = max(max_y_values_by_row[num_rows-1]) for cell in cells: row_rect = Rect() column_rect = Rect() for row_num in cell['row_nums']: row_rect.include_rect(list(rows[row_num]['bbox'])) for column_num in cell['column_nums']: column_rect.include_rect(list(columns[column_num]['bbox'])) cell_rect = row_rect.intersect(column_rect) if cell_rect.get_area() > 0: # getArea() cell['bbox'] = list(cell_rect) pass return cells, confidence_score def remove_supercell_overlap(supercell1, supercell2): """ This function resolves overlap between supercells (supercells must be disjoint) by iteratively shrinking supercells by the fewest grid cells necessary to resolve the overlap. Example: If two supercells overlap at grid cell (R, C), and supercell #1 is less confident than supercell #2, we eliminate either row R from supercell #1 or column C from supercell #1 by comparing the number of columns in row R versus the number of rows in column C. If the number of columns in row R is less than the number of rows in column C, we eliminate row R from supercell #1. This resolves the overlap by removing fewer grid cells from supercell #1 than if we eliminated column C from it. """ common_rows = set(supercell1['row_numbers']).intersection(set(supercell2['row_numbers'])) common_columns = set(supercell1['column_numbers']).intersection(set(supercell2['column_numbers'])) # While the supercells have overlapping grid cells, continue shrinking the less-confident # supercell one row or one column at a time while len(common_rows) > 0 and len(common_columns) > 0: # Try to shrink the supercell as little as possible to remove the overlap; # if the supercell has fewer rows than columns, remove an overlapping column, # because this removes fewer grid cells from the supercell; # otherwise remove an overlapping row if len(supercell2['row_numbers']) < len(supercell2['column_numbers']): min_column = min(supercell2['column_numbers']) max_column = max(supercell2['column_numbers']) if max_column in common_columns: common_columns.remove(max_column) supercell2['column_numbers'].remove(max_column) elif min_column in common_columns: common_columns.remove(min_column) supercell2['column_numbers'].remove(min_column) else: supercell2['column_numbers'] = [] common_columns = set() else: min_row = min(supercell2['row_numbers']) max_row = max(supercell2['row_numbers']) if max_row in common_rows: common_rows.remove(max_row) supercell2['row_numbers'].remove(max_row) elif min_row in common_rows: common_rows.remove(min_row) supercell2['row_numbers'].remove(min_row) else: supercell2['row_numbers'] = [] common_rows = set()