Method and apparatus for recognition of graphic symbols
First Claim
1. A method of operating a computerized graphics system to recognize a graphic symbol, comprising the steps of:
- (a) providing a list of stored vectors produced by vectorizing a drawing or the like, including vectors of the graphic symbol to be recognized;
(b) providing a rule base decision true including a plurality of different geometric tests for various features of the graphic symbol;
(c) defining a window that effectively surrounds a graphic symbol to be recognized;
(d) selecting a softward blackboard corresponding to the window;
(e) operating on the stored vectors to form a linked list of vectors representative of features of the graphic symbol by fetching a vector from the list of stored vectors and inserting the vector into a symbol slot in the blackboard, the symbol slot having locational parameters that correspond to a location of the vector in the window, and creating the symbol slot with locational parameters that correspond to the location of the vector if the symbol slot does not already exist;
(f) inserting the vector in a subsymbol slot in the symbol slot, and adding the vector to a linked list including a vector already in the subsymbol slot if there is one;
(g) creating the subsymbol slot if there does not already exist a previous subsymbol slot into which the vector can be inserted, inserting the vector into the created subsymbol slot, and adding the created subsymbol slot to a linked list of subsymbol slots that includes the previous subsymbol slot;
(h) creating a plurality of subsymbol slots in the course of fetching a plurality of vectors from the list of stored vectors and inserting subsymbol slots into the symbol slot, determining if certain portions of subsymbols in various subsymbol slots are sufficiently close to be merged, and if so, merging such subsymbols;
(i) creating a plurality of symbol slots and subsymbol slots therein, respectively, in the course of fetching a plurality of vectors and inserting them into the blackboard, determining if any subsymbols in a first symbol slot are sufficiently close to subsymbols in a second symbol slot to be mergable with subsymbols in the first symbol slot, and if so, moving the mergable subsymbol from the second symbol slot to the first symbol slot; and
(j) performing sequences of the different geometric tests on selected portions of the linked list at successive notes of the decision tree and producing a symbol identifier corresponding to the graphic symbol if a predetermined outcome of the tests occurs.
3 Assignments
0 Petitions
Accused Products
Abstract
A technique for recognizing hand-drawn graphic symbols operates on vectorized graphic data, including lines, arcs, and circles, that have been produced by an automatic drawing recognition system. The user creates segmented rule bases for recognizing various symbols by describing the geometric structures of recognizable symbols and subsymbols. The rule bases each are compiled into a respective decision tree. Fetched input vectors and entities are placed in software "blackboards", and more particularly, into appropriate symbol slots and subsymbol slots thereof. The growing symbols and subsymbols on the blackboards are continually restructured until they form closed loops or the blackboards are filled. The decision tree then is applied to all possible permutations of the symbols and/or subsymbols to accomplish partial or complete recognition. An inference engine subsystem controls application of the decision trees to limited bits of the symbols and subsymbols, matching decision subtree segment labels to attributes associated with the blackboard data, and orders the matched data according to degree of matching to effectuate application of the decision tree to the linked lists.
117 Citations
30 Claims
-
1. A method of operating a computerized graphics system to recognize a graphic symbol, comprising the steps of:
-
(a) providing a list of stored vectors produced by vectorizing a drawing or the like, including vectors of the graphic symbol to be recognized; (b) providing a rule base decision true including a plurality of different geometric tests for various features of the graphic symbol; (c) defining a window that effectively surrounds a graphic symbol to be recognized; (d) selecting a softward blackboard corresponding to the window; (e) operating on the stored vectors to form a linked list of vectors representative of features of the graphic symbol by fetching a vector from the list of stored vectors and inserting the vector into a symbol slot in the blackboard, the symbol slot having locational parameters that correspond to a location of the vector in the window, and creating the symbol slot with locational parameters that correspond to the location of the vector if the symbol slot does not already exist; (f) inserting the vector in a subsymbol slot in the symbol slot, and adding the vector to a linked list including a vector already in the subsymbol slot if there is one; (g) creating the subsymbol slot if there does not already exist a previous subsymbol slot into which the vector can be inserted, inserting the vector into the created subsymbol slot, and adding the created subsymbol slot to a linked list of subsymbol slots that includes the previous subsymbol slot; (h) creating a plurality of subsymbol slots in the course of fetching a plurality of vectors from the list of stored vectors and inserting subsymbol slots into the symbol slot, determining if certain portions of subsymbols in various subsymbol slots are sufficiently close to be merged, and if so, merging such subsymbols; (i) creating a plurality of symbol slots and subsymbol slots therein, respectively, in the course of fetching a plurality of vectors and inserting them into the blackboard, determining if any subsymbols in a first symbol slot are sufficiently close to subsymbols in a second symbol slot to be mergable with subsymbols in the first symbol slot, and if so, moving the mergable subsymbol from the second symbol slot to the first symbol slot; and (j) performing sequences of the different geometric tests on selected portions of the linked list at successive notes of the decision tree and producing a symbol identifier corresponding to the graphic symbol if a predetermined outcome of the tests occurs. - View Dependent Claims (2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
3. The method of claim I wherein each of the subsymbol selects corresponds to a portion of memory space of the computerized graphics system and each symbol slot corresponds to a portion of memory space of the computerized graphics system.
-
14. In a computerized graphics system, a symbol recognition system comprising in combination:
-
(a) a processor and a memory coupled to the processor; (b) means in the memory for storing a list of stored vectors produced by vectorizing a drawing or the like, including vectors of the graphic symbol to be recognized; (c) means in the memory for storing a rule base decision tree including a plurality of geometric tests for various features of the graphic symbol; (d) means in the processor for defining a window that surrounds a relatively small region of the drawing containing the graphic symbol, wherein the linked list forming means includes means for selecting a software backboard that corresponds to the window; (e) means in the processor for forming a linked list of vectors representative of features of the graphic symbol and storing the linked list in the memory, wherein the linked list forming means includes i. means coupled to the vector storing means for fetching a vector from the list of stored vectors and means responsive to the vector fetching means for inserting the vector into a symbol slot in the blackboard, the symbol slot having locational parameters that correspond to the location of the vector in the window, ii. means responsive to the vector fetching means for creating the symbol slot with locational parameters that correspond to the location of the vector if the symbol slot does not already exist, iii. means responsive to the vector fetching means for inserting the vector in a subsymbol slot in the symbol slot, and means for adding the vector to a linked list including a vector already in the subsymbol slot if there is one, iv. means responsive to the vector fetching means for creating the subsymbol slot if there does not already exist a previous subsymbol slot into which the vector can be inserted, means for inserting the vector into the created subsymbol slot, and means for adding the created subsymbol slot to a linked list of subsymbol slots that includes the previous subsymbol slot; and (f) means in the processor responsive to the linked list forming means for performing sequences of the geometric tests on selected portions of the linked list at successive nodes of the decision tree and producing a symbol identifier corresponding to the graphic symbol if a predetermined outcome of the tests occurs. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
29. A method of operating a computerized graphic system to recognize graphic symbols, comprising the steps of:
-
(a) providing a list of stored vectors produced by vectorizing a drawing or the like, including vectors of graphic symbols to be recognized; (b) providing a rule base decision tree including a plurality of nodes and a plurality of sequences of geometric tests for various subsymbol features which are performed at each node respectively, each sequence of geometric tests having a tree outcome and a false outcome that point to different depending nodes, respectively, of the decision tree; (c) defining a window that effectively surrounds a graphic symbol to be recognized; (d) selecting a software blackboard corresponding to the window; (e) fetching a vector from the stored vector list and inserting the vector into a subsymbol slot in a symbol slot located in the blackboard, the symbol slot having locational parameters that correspond to a location of the vector in the window, to form or add to a linked list of subsymbols; (f) determining if any subsymbol in a first symbol slot is sufficiently close to a subsymbol in a second symbol slot to be merged with the subsymbol in the first symbol slot, and if so, moving the mergeable subsymbol from the second symbol slot to the first symbol slot; (g) determining if any subsymbol in the first subsymbol slot can be merged, and if so merging them; (h) performing a sequence of geometric tests on the linked list of vectors if it forms a closed loop to recognize the closed loop subsymbol; (i) repeating steps (e) through (h) for all other vectors from the window, adding the vectors to the linked list or to one or more other linked lists that are formed during such repeating; (j) performing sequences of geometric tests on selected portions of the linked list at successive nodes on the decision tree, and producing a symbol identifier corresponding to the graphic symbol in the symbol slot if the geometric tests identify a symbol in the linked list; (k) determining if any type of subsymbol included in the linked list of subsymbol slots occurs more than once, and if so, determining a number of possible permutations of subsymbols of the type which occur more than once with other subsymbols in the linked list; (1) if no further permutations of the linked lists are possible and no true outcome is obtained for the present node, performing a sequence of geometric tests at the node pointed to by the false outcome of the sequence of geometric tests previously performed at the present node of the decision tree; and (m) if the sequence of geometric tests results in a symbol identifier being produced, sending the symbol identifier to a utilization program and using it to access a symbol library to obtain detailed data descriptive of the recognized graphic symbol.
-
-
30. A system for operating a computerized graphic system to recognize graphic symbols, comprising inn combination:
-
(a) a processor and a memory; (b) means in the memory for storing a list of stored vectors produced by vectorizing a drawing or the like, including vectors of graphic symbols to be recognized; (c) means in the memory for storing a rule base decision tree including a plurality of nodes and a plurality of sequences of geometric tests for various subsymbol features which arc performed at each node, respectively, each sequence of geometric tests having a true outcome and a false outcome that point to different depending nodes, respectively, of the decision tree; (d) means in the processor for defining a window that effectively surrounds a graphic symbol to be recognized and storing the window in the memory; (e) means in the processor for selecting a software blackboard in the memory corresponding to the window; (f) means in the processor for fetching a vector from the stored vector list and means in the processor for inserting the vector into a subsymbol slot in a symbol slot located in the blackboard, the symbol slot having locational parameters that correspond to a location of the vector in the window to form or add to a linked list of subsymbols; (g) means in the processor responsive to the vector fetching means for determining if any subsymbol in a first symbol slot is sufficiently close to a subsymbol in a second symbol slot to be merged with the subsymbol in the first symbol slot, and if so, moving the mergable subsymbol from the second symbol slot to the first symbol slot; (h) means in the processor for determining if any subsymbols in the first subsymbol slot can be merged, and if so merging them; (i) means in the processor for performing a sequence of geometric tests on the linked list of vectors if it forms a closed loop to recognize the closed loop subsymbol; (j) means in the geometric test performing means for determining if any type of subsymbol included in the linked list of subsymbol slots occurs more than one, and if so, determining a number of possible permutations of the subsymbol of the type which occurs more that once with each subsymbols in the linked list; (l) means in the geometric test performing means for performing a sequence of geometric tests at the node pointed to by the false outcome of the sequence of geometric tests previously performed at the present node of the decision tree if no further permutations of the linked list are possible and no true outcome is obtained for the present node; and (m) means in the processor responsive to the geometric test performing means for sending the symbol identifier to a utilization program and using it to access a symbol library to obtain detailed data descriptive of the recognized graphic symbol, if the sequence of geometric tests results in a symbol identifier being produced.
-
Specification