Method and apparatus for recognition of graphic symbols

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.

Claim 2

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.

Claim 4

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.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.