Detection of near rectangular cells

Patent metadata

Field	Value
Publication number	US-10268920-B2
Application number	US-201715692683-A
Country	US
Kind code	B2
Filing date	Aug 31, 2017
Priority date	Aug 31, 2017
Publication date	Apr 23, 2019
Grant date	Apr 23, 2019

Abstract

A method for image processing is provided. The method includes: generating a skeleton graph associated with the table and comprising a plurality of edges; identifying, in the skeleton graph, a corner vertex, a starting vertex adjacent to the corner vertex, and an ending vertex adjacent to the corner vertex; determining a set of route options for the starting vertex that includes a first set of vertices adjacent to the starting vertex; selecting a candidate vertex from the first set of vertices as a first vertex; determining a set of route options for a second vertex comprising a second set of vertices adjacent to the second vertex; determining the second set of vertices comprises the ending vertex; and generating a route for a cell in the table and comprising the corner vertex, the starting vertex, the first vertex, the second vertex, and the ending vertex.

First claim

What is claimed is:

1. A method for processing an image comprising a table, comprising:
processing the image to generate a skeleton graph associated with the table in the image, wherein the skeleton graph comprises a plurality of edges;
identifying, in the skeleton graph, a corner vertex, a starting vertex adjacent to the corner vertex, and an ending vertex adjacent to the corner vertex;
calculating a travel direction from the corner vertex to the starting vertex;
determining a set of route options for the starting vertex comprising:
a first set of vertices adjacent to the starting vertex in the skeleton graph;
a set of travel directions from the starting vertex to the first set of vertices; and
a set of turn costs for the first set of vertices based on the set of travel directions and a perpendicular of the travel direction from the corner vertex to the starting vertex;

selecting a candidate vertex from the first set of vertices as a first vertex based on the set of turn costs;
determining a set of route options for a second vertex comprising a second set of vertices adjacent to the second vertex in the skeleton graph;
determining the second set of vertices comprises the ending vertex; and
identifying a cell of the table in the processed image by generating a route for the cell,
wherein the route comprises the corner vertex, the starting vertex, the first vertex, the second vertex, and the ending vertex.

2. The method of claim 1 , further comprising:
calculating a length of an edge between the starting vertex and the first vertex of the first set of vertices;
determining the length is less than a predetermined threshold; and
setting, before selecting the first vertex, a travel direction from the starting vertex to the first vertex as the travel direction from the corner vertex to the starting vertex.

3. The method of claim 1 , further comprising:
determining a change in cardinal direction between the travel direction from the corner vertex to the starting vertex and a travel direction from the starting vertex to the candidate vertex;
adding, in response to the change in cardinal direction, the set of route options for the starting vertex, excluding the candidate vertex, to a turn history (TH) data structure;
determining the candidate vertex has no route options;
retrieving, from the TH data structure and in response to the candidate vertex having no route options, the set of route options;
selecting, in response to the candidate vertex having no route options, a replacement vertex from the set of route options as the first vertex based on the set of turn costs; and
determining a set of route options for the replacement vertex.

4. The method of claim 3 , wherein the candidate vertex has a lowest turn cost of the set of turn costs, and wherein the replacement vertex has a second lowest turn cost of the set of turn costs.

5. The method of claim 3 , wherein the travel direction from the corner vertex to the starting vertex is EAST, and wherein the travel direction from the starting vertex to the candidate vertex is SOUTH.

6. The method of claim 1 , further comprising:
adding the ending vertex, the corner vertex, and the starting vertex to a visited vertices (VV) data structure;
adding the candidate vertex to the VV data structure in response to the candidate vertex being absent from the VV data structure and at least one selected from a group consisting of:
a travel direction from the corner vertex to the starting vertex matching a travel direction from the starting vertex to the candidate vertex; and
a clockwise change in cardinal direction between the travel direction from the corner vertex to the starting vertex and the travel direction from the starting vertex to the candidate vertex.

7. The method of claim 1 , further comprising:
populating a cameFrom data structure with the ending vertex, the corner vertex, the starting vertex, the set of vertices adjacent the starting vertex, the second vertex, and the set of vertices adjacent to the second vertex; and
populating, for each entry in the cameFrom data structure, a preceding vertex.

8. The method of claim 7 , wherein generating the route comprises tracing vertices in the cameFrom data structure starting at the second vertex and ending at the ending vertex.

9. The method of claim 1 , wherein the image comprises a writing board, and the table is hand-drawn on the writing board with a marker.

10. A non-transitory computer readable medium (CRM) storing computer readable program code embodied therein that:
processes an image comprising a table to generate a skeleton graph associated with the table in the image, wherein the skeleton graph comprise a plurality of edges;
identifies, in the skeleton graph, a corner vertex, a starting vertex adjacent to the corner vertex, and an ending vertex adjacent to the corner vertex;
calculates a travel direction from the corner vertex to the starting vertex;
determines a set of route options for the starting vertex comprising:
a first set of vertices adjacent to the starting vertex in the skeleton graph;
a set of travel directions from the starting vertex to the first set of vertices; and
a set of turn costs for the first set of vertices based on the set of travel directions and a perpendicular of the travel direction from the corner vertex to the starting vertex;

selects a candidate vertex from the first set of vertices as a first vertex based on the set of turn costs;
determines a set of route options for a second vertex comprising a second set of vertices adjacent to the second vertex in the skeleton graph;
determines the second set of vertices comprises the ending vertex; and
identifies a cell of the table in the processed image by generating a route for the cell,
wherein the route comprises the corner vertex, the starting vertex, the first vertex, the second vertex, and the ending vertex.

11. The non-transitory CRM of claim 10 , further storing computer readable program code embodied therein that:
calculates a length of an edge between the starting vertex and the first vertex of the first set of vertices;
determines the length is less than a predetermined threshold; and
sets, before selecting the first vertex, a travel direction from the starting vertex to the first vertex as the travel direction from the corner vertex to the starting vertex.

12. The non-transitory CRM of claim 10 , further storing computer readable program code embodied therein that:
determines a change in cardinal direction between the travel direction from the corner vertex to the starting vertex and a travel direction from the starting vertex to the candidate vertex;
adds, in response to the change in cardinal direction, the set of route options for the starting vertex, excluding the candidate vertex, to a turn history (TH) data structure;
determines the candidate vertex has no route options;
retrieves, from the TH data structure and in response to the candidate vertex having no route options, the set of route options;
selects, in response to the candidate vertex having no route options, a replacement vertex from the set of route options as the first vertex based on the set of turn costs; and
determines a set of route options for the replacement vertex.

13. The non-transitory CRM of claim 12 , wherein
the candidate vertex has a lowest turn cost of the set of turn costs, and wherein the replacement vertex has a second lowest turn cost of the set of turn costs, and
the travel direction from the corner vertex to the starting vertex is EAST, and wherein the travel direction from the starting vertex to the candidate vertex is SO

Assignees

• Konica Minolta Laboratory Usa Inc

Inventors

• Bellert Darrell Eugene

Classifications

• G06V10/44 Primary

  Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components · CPC title

• G06V10/34

  Smoothing or thinning of the pattern; Morphological operations; Skeletonisation · CPC title

• G06V10/457

  by analysing connectivity, e.g. edge linking, connected component analysis or slices · CPC title

• G06K9/4604

  Physics · mapped topic

• G06K9/469

  Physics · mapped topic