Feature extracting method

A feature extraction method for converting image data of an input line drawing into a graph representation and for recognizing the input line drawing by use of the graph representation, said feature extracting method comprising:

• a first step of equally dividing the image data of the input line drawing into meshes, each mesh being an observation unit;
• a second step of forming a cell by joining one or more adjacent meshes, each cell being an observation unit and having only one black picture region connecting component;
• and
• a third step of recognizing a cell pattern for each cell obtained so as to form a graph in correspondence with each of the cells, the recognizing step including:
• (1) obtaining a pattern of a link of black pixels on a cell boundary and local features within the cell;
• wherein said first step divides the image data into meshes which overlap each other, said second step obtains the cell by integrating adjacent meshes which commonly own a black picture element at a corner point or commonly own a link which traverses no line segment, said link being a run which is observed on boundary pixels of the meshes or cells, and said third step recognizes the cell pattern by obtaining a pattern of a link of black pixels on a cell boundary and local features within the cell, obtains a partial graph of a first order graph depending on the recognized cell pattern and the local features, obtains a second order graph by correcting the local features using a combination or propagation of local features of cells adjacent to an object cell, combining the local features while tracing the first and second order graphs, and finally obtains a hierarchical graph representation of the line drawing by repeating a process of obtaining a graph representation with a higher degree of abstract.