Project Proposal: Graph Rewriting

Supervisor: Alan Sexton

Keywords: Final Year Undergraduate Students Only, Document Image Analysis

Brief Description:

One the the most promising techniques for higher level analysis of documents (i.e. after all the low level image analysis and character recognition has been completed) is Graph Rewriting. The idea is that the objects discovered in an image are placed in a graph data structure with links between objects based on their spatial relationship to each other (e.g. to-the-right-near or above-left-far etc). Identifying the higher level structure in the document can then be done by rewriting the graph: e.g. if one object is an italic "x" at ten point size and above-right-near there is a "2" at 8 point size we might reasonably rewrite the two objects and the link into a single "x squared" object, while keeping the remainder of the graph the same. A whole sequence of rewrites could recognise a whole mathematical expression. The same techniques can be applied to diagram recognition, form recognition or general document analysis.

Special Equipment: No special equipment requirements

Special Software: No special software requirements