Concepts
   Neuron
   Automata
   Entropy
   Waves
   Thoughts

Computation
   Synapses
   Coherence
   Neuralwaves

Sequences
   Circuits
   Clusters
   Code

Software
   Prism
   Kali












Home-> Software->Prism


Prism      


Design     Components     Compiler     Logic     Filter     Associations

Prism is a pattern recognition software. It associates character strings with pattern formations. For example, image processing features extracted from a photograph are coded with string sequences. Identification of pictures is done by constructing a pattern descriptor from string sequences which are unique to each picture.


Once a sequence pattern is extracted it can be further classified using a logical filter. Unlike the neural network which contain no explicit logical or Boolean operatives, PRISM classifies sequential data according to a rule-based profile dictionary. The image processing software uses generic edge enchancement techniques from syntactic pattern recognition, and contour detection.



Design

The Prism software uses the idea of grouping or clustering sets of words to form an abstract description of the data. The cluster of words is called a pattern descriptor, PD. The PD is a representation of the characteristic properties of the data. They lay the foundation or bases upon which the data is structured or classified. The PDs may also be thought as the components parts of a large set of characteristic descriptors of the data.

Representing Images as Strings

PRISM can recognize images which have been rotated or scaled in size, and can recognize different image elements randomly scattered throughout the picture. This is because each image is an abstract representation of the 2-dimensional picture in the form of a sequence of characters like the mapping of genetic code.

For example, multi-dimensional image recognition is accomplished by converting the graphical image into an abstract representation. This representation maybe be implemented by transforming the image picture elements into sequences of character symbols or strings. One of the most efficient ways to describe a picture is by drawing the contour outline of the objects in the picture verses describing the filled objects. For human beings, recognizing contours comes very naturally, however, for machines which have not evolved the mechanisms to do this, contours are sets of pixels which are similar in intensity or color. We call the constant intensity or color contour an isoterm. Pictures may contain large sets of pixels with similar intensity and colors. They may be hard to to identify if you had to disinguish many picture elements in the image. On the other hand, an image with distinct, sharply contrasting intensity or color patterns would be easier to recognize. The algorithm to trace the contour of constant intensity is to propagate around the image in a clockwise direction always keeping the area of constant intensity on the right-hand side. The trace is a string representing the propagation direction in each cell or grid.

If the center cell is represented by 0, then there are eight neighborhood cells surrounding cell 0.

            
Eight Neighborhood Cell         Octal Primitive

For example, a simple rectangle is represented by the string, 234345678781.

  
      Image Contour

The starting point of the trace is P0. It is found by a left to right, and up to down, scan of the image. The contour of an object is traced by finding the cell on the leftmost side as you trace the contour keeping the interior of it on the rightmost side.

Image pattern recognition on a series of handwritten characters can be greatly enhanced using a neural network. Isotermal sequence of handwritten characters are used to train a simple neural network. For a small set of characters, the simple neural network performs perfectly.


Components   

The pattern compiler, PC, condenses sets of pattern descriptors, PDs, into associative lists which are used to perform the pattern recognition. A PD is composed of a logical sequence of character strings describing the pattern data. These string sets are transformed into complex representation of patterns with boolean operators. The PC condenses many pattern descriptors together in an efficient manner.

The attribute filter, AF, uses the dictionary produced by the PC module to evaluate the text data and assign attribute codes to the data.

Single words or sequences of words are the elements which PRISM uses to classify data. These language elements in the pattern descriptors are the nodes in a semantic network.

    name: pattern-one.
    logic: A + B.
    definition:
        A: item1, item2 item3, item4;
        B: item5.
    assignment: attribute1.

Data descriptors in a semantic network are linked to other elements in the network thereby forming relationships. These sets or sequences of words which are used in logic processing are called the operands. The operands build the logical relationships in the semantic network.

Pattern descriptors contain attributes of the text data you want to match. A PD's logical disposition is defined in relationship to all the other PD's which are nodes in the semantic network. The pattern descriptor is defined by the following items:

    (1) Node name which is an element defined
        globally across the entire network.
    (2) Logic operands which are nodal elememts
        defined system wide.
    (3) Description of each operand consisting
        of keywords and phrases.
    (4) Association consists of words describing
        the semantic connections.
A PD or nodal element can represent any abstract description of an object such as an image, idea or concept. The PD is composed by using the logic operands to create functions or relationships, complex attribute descriptions, and associative interconnections.

A specific example is of the form:

    name: pattern-one.
    logic: A but not B.
    definition: A: lion, zebra, hyena;
                B: panda, kangarro.
    assignment: african-animals.



Pattern Compiler   

There are numerous ways to interweave the PD elements into computer data structures like binary trees, hash buckets, graphs and so forth.

Searching

Binary lists or trees are good for ordering or sorting a set. However, if the number of items in the set grows large, the search time increases. We can very effectively decrease the search time if we used many small sets instead of one large one. This can be implemented by using hash buckets.

  

The elements used to identify a word in the text is to first use a hash map, HMAP, and then funnel the words through a hashbucket index to the binary keyword trees.

     _____
    |     |  Hashmap (6 blocks = 24576 bits)
    |_____|
    |     |  Index (10 blocks)
    |     |
    |_____|
    |     |  Tree (Variable extension. Nodes for binary
    |     |        trees, keywords, strings, node data
    |     |        lists, etc.)
    |_____|

The index is composed of keyword nodes, KNODEs, pointers. Each entry is 4 bytes. A total of 1270 entries occupy the 10 block index. Index entry 1271 is the pointer to data descriptor node or profile, PNODE, root.

Primary Nodes

The keyword, continuation and PD nodes have the same primary node structure.

     ___
    |___| c, contents
    |___| l, left node link
    |___| r, right node link
    |___| w, weight or subtree size
    |___| d, data pointer

Keyword Nodes

    KNODE     CLIST (if phase) 

    KNODE
     ___        ____              ____
    |___| ---> |____| clist ---> |____| CNODE
               |____| olist
               |____| plist



Logic Processing   

Element A in the logic statement above is the logic operand or ONUM. The ONUMs are assigned in consecutive ascending order during the PD parsing phase, and is used as bit numbers in a bitmap, OMAP, which covers all of the logic operands in the resultant compiled dictionary. An operand list, OLIST, which contains ONUMs is built for each keyword or phrase. The keyword list, KLIST, or continuation phrase, CLIST, contains the pointer to the OLIST. Logic processing using these structures determines how the bit number in the OMAP will be filled. The OMAP covers all of the operands in the dictionary. The current maximum number of operands in the PRISM logic statements can total 8192 because the operand bitmap, OMAP, is 2 (512 bytes) blocks in size.

    OLIST
     ____
    |____| operand number, ONUM
    |____| zones
    |____| next OLIST pointer

The logic routine parses the logic statement in the pattern descriptor, PD. The logic operand, ONUM, is used as bit numbers in the OMAP. The OLIST entry consists of ONUMs and the zone number. There are five types of logic operators:

    1. and,
    2. not,
    3. or,
    4. and within n words,
    5. not within n words.

The statement "A" and within 5 words "B" is parsed into short form as "A+5B". Any statement which contains the "within" clause is called a relational statement. The logic control record, LCR, contains logical relationships between the operands which are marked in the OMAP. The OMAP can only validate non-relational statements. If the LCR contains any relational statement logic, then the RNODES which key off the ONUM must be examined to determine whether the "within" window relationship holds. RNODE

    RNODE
     ___
    |_c_| ---> ONUM
    |_l_|
    |_r_|
    |_w_|                    ___
    |_d_| ---> RLIST        |___|  RTWC 1
                            |___|  RTWC 2
                            |___|    "

The relational statement is processed by reading sequentially through the RLIST, comparing each RTWCs in the list for ONUM n to the RTWCs in the list for ONUM n+1.


Relational Statements

Relational statements, RS, are the internal LCR representation of one relational clause of a PD logic statement. There are two types of relational statements: ANDs and NOTs. AND Relational Statement This type of RS has the form (...((A + mB) + nC)...) where operands are related by the AND WITHIN N WORDS clause. The proximity of words are indicated by the m, n, etc. NOT Relational Statement This type of RS has the form (...((A - mB) - nC)...) where each operand is related by the NOT WITHIN N WORDS clause.


The Logic Control Record

The Logic Control Record, LCR, containing the logic statement with the ONUM values for the operand. For example, the statement "A and B and within 5 words C" is shorten by the parser to the form: "A+(B+5C) with A, B and C" represented by ONUM values. The algorithm to effect the "within" clause uses information in the Logic Control Record, LCR. The relative text word count, RTWC, is used to keep track of the keyword position relative to other words in the text. Evaluation of the LCRs are separated into processing non-relative, NR, and relative, R, statements. The R statements contains a windowing factor between operands. The compound statement "A+(B+5C)" is made up of an NR and R statement. The expression B+5C is an R statement. R statements should be processed first. The operand "B" is looked up in the OMAP. If it is not found, then the statement (B+5C) is void. If it is found, then the operand "C" is checked to see if it is marked. If it is the RNODEs for both the B and C operands are construclists. The RTWC in both the RNODEs are compared to see if they differ by more than 5. If they do, the statement is void, otherwise it is satisfied.


Language Extensions

An extension of this algorithm would be to associate simple groups of words in a sentence together. Particularly, a very often seen pattern in sentences is the grouping of words around verbs. For example, the verb "likes" will immediately trigger a process operator which will look for a noun preceding the verb and an object following the verb. Usually, a noun precedes the verb by only a few words. Similarly, the object of the action verb follows within a couple of words. Consider, for example, the sentence "Tom likes airplanes." In the pattern descriptor example of the node Africa above, suppose we made the statement "Zebra exists in Africa." This statement would be transposed into "exists (zebra; Africa)" which parses into a syntactic tree. These "deep mechanisms" can be built into the pattern descriptor. The outcome could be a fast parser which relates simple patterns for simple finite machines.


Attribute Filter   

Step 1

The test file is opened. Each word is hashed to see if it might be contained in one of the 1270 hashbuckets. If the bit corresponding to the hash value is set in the HMAP, the KTREE is scanned to check for the keyword. If the word is there, and the zone(s) match, a bit is marked in the OMAP using the OLIST pointed to in the KLIST. The OLIST contains both the non-relative and relative operands. Both type of operands are marked in the OMAP. Nodes for relative operands are inserted into the KNODE list.

             _____                    ___
            |     | Text             |___|  RNODE
            |_____|                   _|_   list
             /   \                   |___|
          __/_   _\__                 _|_
    mark |    | |    | fill in       |___|
    OMAP |____| |____| RNODE

The ONUM is coded with a N or R ascii character which indicates that the operand is either non-relative or relative. The following ascii string is the operands integral values.

          __________________
    ONUM | N/R Ascii digits |
         |__________________|

The RLIST has the following structure.
   RNODE  c -> onum
          l  left node pointer
          r  right node pointer
          w  weight
          d -> RLIST


   RLIST  chain structure
          unsigned short  number (RTWC)
          struct chain  next

Step 2

Each LCR is processed in ascending order of the PNUM. The OMAP is used to evaluate the LCRs. If the operand in the LCR was marked in the OMAP in STEP1, then check the OLIST to see if the operand is a non-relative or relative number. If the operand is non-relative, no further checks are needed. If it is a relative operand scan through the RLIST to validate the within word factor. If the LCR of the PD is validated, then the PD bit number is set in the PMAP.

    KLIST ---> OLIST
    PDATA ---> LCR 

Step 3

During STEP3, the text assignments are obtained by looking at the bits set in the PMAP. The attribution codes are extracted from the PDATA of each PD. These codes are inserted into the text descriptor record.


Associations   

The logic statement is of the form: "LOGIC: A and B and within 5 words C". The parser shortens the statement to the form: "A+(B+5C)". The parser identifies relative statements within parenthesis. The logic assignment is evaluated using the operand bit map, OMAP. The PD bit map, PMAP, is produced as a result of the logic evaluation of the OMAP. The OMAP is obtained by reading the OLIST in each keyword record. The PD number bit map, PMAP, is obtained by reading the PLIST in each keyword record.

Evaluation of the Logic Control Record, LCR

(i) Evaluation of the LCR are separated into processing non-relative statements, and relative statements. The non-relative, NR, statements do not contain a windowing factor between operands whereas the relative, R, statements do.

(ii) The compound statement "A+(B+5C)" is made up of an NR and R statement. The statement B+5C is a R-statement. The relative statement should be processed first.

(iii) Operand "B" is looked up in the OMAP. If it is not found, then the statement (B+5C) is void. If it is found, then the operand "C" is checked to see if it is marked. If it is the RNODEs for both the B and C operands are constructed. The RTWCs are inserted in each of the RNODE lists. The RTWC in both the RNODEs are compared to see if they differ by more than 5. If they do, the statement is void. If not, the statement is satisfied. After each LCR is processed the PD bit number, PNUM, in the PMAP should be either cleared or left on as an active PD.