United States Patent (19)
`Bailey et al.
`
`|||||||||III
`US005459798A
`11) Patent Number:
`5,459,798
`45) Date of Patent:
`Oct. 17, 1995
`
`(54)
`
`SYSTEMAND METHOD OF PATTERN
`RECOGNITION EMPLOYING A
`MULTIPROCESSENG PEPELNED
`APPARATUS WITH PRIVATE PATTERN
`MEMORY
`
`... 382/34
`56122445 2/1983 Japan .......
`62-117744 ll/1988 Japan ....................................... 382/34
`OTHER PUBLICATIONS
`English Translation of Japanese Kokai 58-24975 (to
`Komiya, publ. Feb. 1983).
`English Translation of Japanese Kokai 63-282586 (to Min
`ewaki, publ. Nov. 1988).
`Primary Examiner-Leo H. Boudreau
`Assistant Examiner-Andrew W. Johns
`Attorney, Agent, or Firm-Blakely, Sokoloff, Taylor & Zaf
`Appl. No.: 60,579
`la
`Filed:
`May 12, 1993
`ABSTRACT
`57
`Related U.S. Application Data
`A computer implemented apparatus and method of pattern
`recognition utilizing a pattern recognition engine coupled
`Continuation-in-part of Ser. No. 34,678, Mar. 19, 1993.
`with a general purpose computer system. The present inven
`Int. Cl. ...r. G06K 9/68
`tion system provides increased accuracy and performance in
`U.S. Cl. ....................... 382,218, 382/303: 364,231.8
`handwriting and voice recognition Systems and may inter
`364/DIG. 1; 364/926.8; 364/948.34; 364/DIG. 2
`face with general purpose computer systems. A pattern
`Field of Search
`382/13, 30, 33
`recognition engine is provided within the present invention
`382,34, 41,49,364,229 2, 231 s 240
`that contains five pipelines which operate in parallel and are
`240.2, 242 3 243 243.43 243 44 243 45.
`specially optimized for Dynamic Time Warping and Hidden
`a w 926.8 948 34 964 964 2 964 26
`Markov Models procedures for pattern recognition, espe
`ow Y I was
`Yw is - w a
`w a
`cially handwriting recognition. These pipelines comprise
`References Cited
`two arithmetic pipelines, one control pipeline and two
`pointer pipelines. Further, a private memory is associated
`U.S. PATENT DOCUMENTS
`with each pattern recognition engine for library storage of
`reference or prototype patterns. Recognition procedures are
`E. 15 Sin, al.". 35 partitioned across a CPU and the pattern recognition engine.
`5.0143275/1991 Potterta. I? Use of a private memory allows quick access of the library
`5,111,512 5/1992 Fan et al. .................................... 382/3
`patterns without impeding the performance of programs
`5,226,091
`7/1993 Howell et al. ..
`... 382/3
`operating on the main CPU or the hostbus. Communication
`5,265,174 11/1993 Nakatsuka .......
`... 382A38
`between the CPU and the pattern recognition engine is
`FOREIGN PATENT DOCUMENTS
`accomplished over the host bus.
`
`Inventors: Delbert D. Bailey, Aptos; Carole
`Dulong, Saratoga, both of Calif.
`Assignee: Intel Corporation, Santa Clara, Calif.
`
`75)
`
`73)
`
`(21)
`22)
`
`(63)
`(51)
`(52)
`
`(58)
`
`(56
`
`0550865 7/1993 European Pat. Off. ................. 382/13
`
`50 Claims, 16 Drawing Sheets
`
`SYSTEMBUS
`MEMORYBUS
`
`
`
`
`
`OO
`
`O
`
`
`
`
`
`30
`
`22 O Pa
`
`225
`
`MEMORY
`
`34a
`
`34b
`
`
`
`53
`
`MEMORY
`
`
`
`
`
`36
`
`39
`
`REGISTERS
`
`DISTANCE
`ALUi (16BIT)
`
`55
`
`
`
`O
`
`
`
`BEST PATH
`ALU2 (16BIT)
`
`MEMORYBUS
`
`GOOGLE EXHIBIT 1021
`
`Page 1 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 1 of 16
`
`5,459,798
`
`FG. A
`
`O O O O
`
`O O O O
`
`O O-O Q
`O
`
`7. 1
`
`Os
`-
`O O O O O
`
`O O O ... O O O
`
`O
`
`O O O O O
`
`7
`
`6
`
`8
`
`7
`
`6
`
`
`
`
`
`UNKNOWN
`
`UNKNOWN
`
`201N 21 N 23
`N
`N
`N
`Y
`N
`N
`A
`(A
`
`26
`
`22
`
`N.
`24
`N
`N
`N
`
`O
`
`O
`
`REFERENCE
`3
`
`Page 2 of 53
`
`

`

`U.S. Patent
`
`5,459,798
`
`
`
`
`
`
`
`
`
`
`9|9719
`
`219
`
`WWH
`
`| 39
`
`TOHI NOO
`
`AWTdSIC]
`
`029
`
`819
`
`?
`
`Page 3 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 3 of 16
`
`5,459,798
`
`510
`
`522
`
`52
`
`CPU
`
`INPUT
`PATERN
`
`RAM
`
`100
`
`525a
`
`525b.
`
`525C
`
`PRE
`
`65a
`
`65b.
`
`615C
`
`PRE
`
`MEM
`
`FG 33A
`
`
`
`INPUT
`PATTERN
`
`Page 4 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 4 of 16
`
`5,459,798
`
`400
`
`GET NEXT
`
`40
`
`402
`
`STYLUS
`INPUT
`
`PREPROCESS
`UNKNOWN
`
`
`
`YES
`
`403
`
`NO
`
`REPORT
`ONEACH
`PROTTYPE
`
`
`
`
`
`
`
`
`
`
`
`COMPARE LIBRARY
`PATTERNS TO
`UNKNOWN; REPORT
`RESULTS ONEACH
`
`
`
`COMPARE LIBRARY
`PATTERNS TO
`UNKNOWN; REPORT
`ON END OF LIBRARY
`
`
`
`405
`
`406
`
`POST
`PROCESS
`RESULTS
`
`
`
`
`
`NO
`
`
`
`OF
`UNKNOWNS
`
`407
`
`YES
`
`4.08
`
`EXIT
`
`FIG 4
`
`Page 5 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 5 of 16
`
`5,459,798
`
`
`
`OFF
`CHIP
`PRIVATE
`MEMORY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`525
`
`PROGRAM
`MEMORY
`
`WLW
`EXECUTION
`
`MEMORY TO
`MEMORY
`TRANSFER
`
`SYSTEM BUS
`INTERFACE
`
`100
`
`FIG 55
`
`Page 6 of 53
`
`

`

`5,459,798
`
`OvONY8¢vSv
`
`9“Dia
`
`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 6 of 16
`
`SSIYOWSNSSANN3dldSLIMVv
`
`
`c€ONY0€
`GreONYBre¥344Nd
`
`dIHO-dd0
`
`AYOWSW
`
`2|a
`
`T
`
`W907
`
`HSINIOd
`
`OLLAWHLIYV
`
`SANIT3did
`
`ONIGO9SG
`
`SNOLLONYLSNI
`
`WVHDOud
`
`AYOWSN
`
`TOULNOD
`
`LINA
`
`esp
`
`NOILONYLSNI
`
`Y3435Nd
`
`Page 7 of 53
`
`Page 7 of 53
`
`
`
`
`
`
`
`

`

`U.S. Patent
`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 7 of 16
`
`5,459,798
`5,459,798
`
`AHOWSIvSSUAINIOdGeeAHOWSIN
`
`IBld
`
`
`
`
`
`Ne
`
`Ly
`
`9¢
`
`||
`
`SHALSIDSY
`
`HlVdLSaq98FONVISIG
`
`
`(11891)env(L1G9b)LNTV
`
`
`gg
`
`Olt
`
`sndAHOWSWZ“Dia
`
`2, º? D. INHI
`
`qveeve
`
`BLeS|d0¢2
`
`001SNWALSAS
`
`OltSN@AHOWSAN
`0€
`
`
`
`
`
`Page 8 of 53
`
`Page 8 of 53
`
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 8 of 16
`
`5,459,798
`
`System Bus
`
`
`
`from MMT
`
`100
`
`15
`
`30
`
`- - - - - - - - - - -Immediate---
`Sension
`62
`
`86
`
`Write Address from
`Memory Bus 110
`Pb
`225
`Read Address
`time from MMT
`
`Pta
`
`220
`
`to MMT
`
`/ 37
`
`to Pt
`
`
`
`Regf
`Register
`File
`
`Regd
`
`36
`
`90
`
`76
`
`/ N Memory
`
`BUS
`110
`from MMT
`15
`100 1 System Bus
`
`a SC CE)
`Y/
`X
`
`SOUrCel
`
`68
`
`X
`
`Source 2
`
`
`
`69
`
`
`
`-
`
`+f-
`70b
`
`ALU
`70c
`
`
`
`
`
`ACCumulator
`----------------------
`
`Page 9 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 9 of 16
`
`5,459,798
`
`s
`
`122
`
`
`
`100
`System Bus SQ
`
`N 93 /
`
`ACCumulator
`PTb
`
`---
`E.---
`
`504
`
`505
`
`immediate
`- 102 Y1
`62
`86
`SIZEXT
`16 somy
`
`Regf
`
`PTa
`
`\ 220
`
`PTa
`(
`
`150
`
`S-Type-1
`PTb
`
`225
`
`165
`
`F N 7.
`S-C sie
`
`155
`
`8
`
`6
`
`
`
`150
`
`REGISTER
`FILE
`
`173
`
`WE
`
`FG
`
`Page 10 of 53
`
`

`

`U.S. Patent
`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 10 of 16
`
`5,459,798
`5,459,798
`
`OILSWHLIWV
`
`éSNMAdid
`
`
`
`OILLSWHLIEV
`
`bSNMAdid
`
`602
`
`a0¢dld
`dqOLVYSdO
`
`206
`
`
`
`GDI ºsº D' I) |
`
`
`
`
`
`
`
`
`dpe
`
`uld
`
`ANMAdld
`
`eS
`
`9}
`
`9|
`
`YALNIOd
`
`YS1SIDSu
`
`qs
`
`Page 11 of 53
`
`Page 11 of 53
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 11 of 16
`
`5,459,798
`
`100
`
`Regf
`\
`37
`
`System Bus
`MemorW BUS
`ry
`110
`
`262
`
`240 - Address from MMT
`Pta Or Ptb
`
`200
`
`Pointer File
`
`263
`
`242
`
`RAa 264
`
`244
`
`Pta field from
`ALU instruction
`Ptb field from
`ALU instruction
`Address from MMT
`or SB
`
`Ptb
`
`265
`
`248
`
`\ Y. A 250
`
`Pta + Regf
`
`255
`
`Inc field from
`Pointer instruction
`Zero Extended
`
`8 bit immediate
`from ALU instruction
`
`Regf
`
`37
`
`225
`
`34a
`
`
`
`
`
`FIG
`
`Page 12 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 12 of 16
`
`5,459,798
`
`FROMMC
`
`454.
`
`SYSTEM BUS
`GENERAL PURPOSE
`REGISTER
`
`ADDRESS
`FROMMC
`OR SB
`
`P.C. LOGIC
`
`70
`
`CONTROL REGISTER
`16X 16BITS BA
`
`707
`
`
`
`RA2
`
`m OR p
`
`TO MC
`OR SB
`
`703B
`
`MMEDIATE
`SIGN
`EXTENDED
`
`REGISTER
`
`REGISTER
`
`703A
`
`704
`
`ADD/SUB
`
`705
`
`
`
`ALU
`
`ALU2
`
`COND
`
`FLAGS
`FROM
`ALL
`PIPELINES
`
`FLAG
`REGISTER
`708
`
`
`
`R G. 2
`
`FLAGSELECTION CONDMASK
`FOR CONTROL
`FLOW DECISION
`
`Page 13 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 13 of 16
`
`5,459,798
`
`al
`
`0eZ
`
`dl
`
`WVYHDOHd
`
`AHOWAW
`
`LN
`
`IGSWOHGV3HOdssauady
`
`bet4,804Sky22L
`o1ZLHOHS/DNOT
`HSHAGGVaHOd
`
`G2ZHALSIDYALLISaimosav
`HOLVHadO|||922HSLSIOSY||
`|ANMTAdidMOT|TOHLNODWOH
`
`L2Z
`
`€2Z
`
`<i
`
`“DE
`
`Page 14 of 53
`
`Page 14 of 53
`
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 14 of 16
`
`5,459,798
`
`SCALAR LOADS
`416
`& STORES FROM
`Y - - - - - EXECUTION UNIT
`
`8 OD
`N
`CONTROL. 1
`
`82OD
`N
`CONTROLO
`
`
`
`811
`
`- - - -
`
`49
`
`COUNT
`
`EXTERNAL ADD
`INTERNAApp
`
`COUNTO
`EXTERNAL ADDO
`INTERNAL ADDO
`
`MEMORY
`CONTROLLER
`INTERFACE
`
`810A
`810B
`C
`810C
`-
`820A
`|
`20c - - - - - - -
`
`87
`N
`EXT. ADDRESS
`
`ACTIVE
`CHANNEL
`
`
`
`ACCESS TO EU
`
`
`
`
`
`
`
`
`
`FROM GENERAL PURPOSE
`REGISTERS 36
`
`arra
`
`is m m is m sm m - m am
`
`SYSTEM BUS
`INTERFACE
`
`Page 15 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 15 of 16
`
`5,459,798
`
`830
`
`INACTIVE
`
`ACTIVATION O 83
`
`F CHANNEL
`NOT FREE
`
`F CHANNE
`FREE
`
`PENDING
`
`ACTIVE
`
`832
`
`834
`
`GENERATE
`DONE
`FLAG
`
`
`
`836
`
`833
`
`835
`
`ABORT
`OR
`ERROR
`
`837
`
`ABORTED
`
`GENERATE DONE FLAG
`
`838
`COUNT
`
`GENERATE
`DONE FLAG
`
`FIG 55
`
`Page 16 of 53
`
`

`

`U.S. Patent
`
`Oct. 17, 1995
`
`Sheet 16 of 16
`
`5,459,798
`
`
`
`DATA MEMORY
`
`30
`
`EXTERNAL MEMORY
`
`615
`
`LETTERZ
`
`BUFFER2
`860A
`
`BUFFER
`860B
`
`UNKNOWN
`CHARACTER
`860C
`
`FG (S
`
`Page 17 of 53
`
`

`

`5,459,798
`
`1.
`SYSTEMAND METHOD OF PATTERN
`RECOGNITION EMPLOYNGA
`MULTIPROCESSING PIPELINED
`APPARATUS WITH PRIVATE PATTERN
`MEMORY
`W
`
`1. Related US Application
`The present invention is a continuation in part of appli
`cation Ser. No. 08/034,678 filed Mar. 19, 1993, entitled, “A
`Memory Transfer Apparatus and Method Useful Within a
`Pattern Recognition System' and assigned to the assignee of
`the present invention.
`
`2
`pattern recognition system that eliminates this additional bus
`accessing to the reference patterns. The present invention
`allows such capability.
`Heretofore, prior an systems for pattern recognition have
`typically been implemented using software techniques in
`general purpose computers. Although offering a good deal of
`flexibility, these general purpose computers do not offer the
`processing power and efficiency required to process the vast
`amount of data required for voice and/or handwriting rec
`ognition applications. In order to provide accurate and
`useful pattern recognition capabilities within a general pur
`pose computer system, the reference library must contain a
`fair amount of reference patterns. Further, each reference
`pattern must contain a level of resolution to distinguish each
`individual known input. Moreover, since voice and hand
`writing samples may vary from person to person, each
`known reference pattern should contain a multitude of
`pattern variations. Each of the above limitations and require
`ments of a pattern recognition system require a great deal of
`computer processing capability. Prior an software systems
`simply to not offer enough processing power to allow a
`personal computer or desktop platform to realize accurate
`and useful handwriting and/or voice recognition applica
`tions. More processing power is needed to provide real-time
`accurate voice and/or handwriting recognition applications
`than the prior art can provide. Specifically, prioran computer
`systems that have pattern recognition procedures imple
`mented primarily in software offer poor performance and do
`not readily provide rapid response time between an
`unknown pattern input and the resultant match output and
`are therefore not entirely user interactive.
`General purpose computer systems offering pattern rec
`ognition capability are typically implemented within one of
`three levels of processing complexity. The first level of
`complexity (the lowest level) is programmed to recognize
`only patterns input according to a tight or ridged and
`predetermined format. For instance, these system recognize
`only handwritten letters if written within predetermined
`boxes on a predetermined format or voice input within
`predetermined timing windows. A second and higher level
`of complexity is system that can recognize a particular
`persons writing but does not require predetermined input
`boxes and may allow individual characters to touch or be
`cursive or natural. A third, and highest level of pattern
`recognition would recognize any written or spoken pattern
`that a person could otherwise recognize. As can be seen,
`each level of pattern recognition sophistication requires
`more processing power from the computer system. It would
`be advantageous to provide a system that could be used to
`interface with any of the systems as specified above to
`increase performance and accuracy of pattern recognition
`applications. The present invention offers such capability.
`Therefore, it would be advantageous to provide a system that
`could be interfaced with a general purpose computer, that
`would offer the power and efficiency for processing pattern
`recognition procedures while at the same offering the flex
`ibility of a programmed general purpose computer system.
`It would further be advantageous to offer the above in a
`system specially optimized for voice and/or handwriting
`pattern recognition. The present invention offers such capa
`bilities.
`Accordingly, it is an object of the present invention to
`provide a pattern recognition system having the processing
`power and efficiency to realize real-time accurate pattern
`recognition procedures operating with general purpose com
`puter systems. Further, it is an object of the present invention
`to provide such a pattern recognition system within a
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`BACKGROUND OF THE INVENTION
`2. Field of the Invention
`The present invention relates to the field of pattern
`recognition. Specifically, the present invention relates to the
`field of systems for pattern recognition particularly useful
`for voice and handwriting recognition applications.
`2. Prior Art
`The ability to store and accurately recognize patterns is a
`particularly good application for general computer systems.
`Computer systems offer the unique ability to process at high
`speeds specialized procedures that are developed for the
`field of pattern recognition. Using pattern recegnition tech
`nology, a computer system can be advantageously utilized to
`respond to variable patterns of information (such as hand
`written characters and voice) rather than rigid input devices,
`such as a keyboard input device. Using such technology, a
`computer system can be utilized to recognize visible pat
`terns, such as pictures and video frame, or audible patterns,
`such as voice and other sounds, or movement patterns such
`as handwriting. It would be advantageous, then, to provide
`a computer system with an efficient mechanism for pattern
`recognition for handwriting and voice input applications.
`The present invention offers such capability.
`Typically, a library of reference or prototype patterns may
`be stored within the memory storage devices of a general
`purpose computer system implemented by software for
`pattern recognition. Each library pattern is further composed
`of many individual points or states that, in total, comprise
`the pattern representation. These known library reference
`patterns are then individually compared against an input
`pattern also composed of a multitude of points or states. The
`general purpose computer systems of the prior art are
`programmed to individually compare, point by point, or
`state by state, the individual components of a particular
`reference pattern to the individual components of the input
`unknown pattern. This continues for each reference pattern
`in the library of patterns. For each pattern a match path is
`developed that indicates the level of identity between the
`unknown and the reference patterns. Reference patterns with
`good match paths are then selected by the computer system
`as candidates for a resultant match. The computer system
`then analyzes each of the reported candidates to determine
`which is best matches the unknown input pattern. During a
`comparison, since the reference patterns are each compared
`against the unknown, they are constantly accessed by the
`computer system. Prior art pattern recognition systems store
`the reference patterns in a memory array that is coupled to
`the computer system bus. When a pattern recognition pro
`cedure is operating the constant access of these reference
`patterns over the host system bus tends to interfere with, if
`not eliminate, other tasks that the computer system may
`perform. Therefore, it would be advantageous to provide a
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Page 18 of 53
`
`

`

`5,459,798
`
`10
`
`15
`
`20
`
`3
`personal computer or desktop platform or pen-based com
`puter system. It is an object of the present invention to
`provide a pattern recognition system having the capability to
`process high resolution patterns and provide enough accu
`racy to allow meaningful pattern recognition of voice and/or
`handwriting input patterns in real-time applications. More
`over, it is an object of the present invention to offer the
`capability of interfacing with any general purpose computer
`system to increase its overall pattern recognition power and
`efficiency as well as increasing accuracy of pattern recog
`nition and performance. It is yet an object of the present
`invention to provide a pattern recognition system that inter
`faces with a general purpose computer system whereby the
`present invention reduces the pattern recognition processing
`load of a central processing unit of the general purpose
`computer system thus freeing the general purpose computer
`system for processing of other tasks or higher level pattern
`recognition software tasks. It is yet another object of the
`present invention to provide a method and mechanism to
`reduce bandwidth requirements over a computer system bus
`resulting in accessing of reference patterns to free up the
`computer bus for other information or communication tasks.
`
`SUMMARY OF THE INVENTION
`Embodiments of the present invention include a system
`for pattern recognition comprising: general purpose host
`computer system means comprising: a host bus means for
`providing communication within the general purpose host
`computer system means; central processor means for execut
`ing host instructions, the central processor coupled to the
`host bus means; and host memory means for storing host
`information, the host memory means coupled to the hostbus
`means; and programmable multiprocessing means (which
`may be optimized for Dynamic Time Warping or Hidden
`Markov Models pattern recognition procedures) for execut
`ing pattern recognition instructions for comparing an
`unknown pattern against a plurality of reference patterns; the
`programmable multiprocessing means coupled to the host
`bus means; and private memory means coupled to the
`programmable multiprocessing means for storing a library
`of the plurality of reference patterns, the private memory
`means having at least one communication pathway to the
`programmable multiprocessing means that bypasses the host
`bus means wherein access of the private memory means by
`the programmable multiprocessing means does not neces
`sarily increase information flow across the hostbus means.
`Further embodiments of the present invention include the
`above wherein the programmable multiprocessing means
`further comprises: two arithmetic pipelines for executing
`two arithmetic instructions in parallel; two pointer pipelines
`for executing two pointer instructions in parallel, each of the
`pointer pipelines for supplying pointer information for an
`associated arithmetic pipeline; and a control pipeline for
`providing instruction flow control for the pattern recognition
`procedures, and wherein the two arithmetic pipelines, the
`two pointer pipelines and the control pipeline operate in
`parallel to execute Very Long Instruction Words within the
`pattern recognition procedures.
`Further embodiments of the present invention include the
`above wherein the programmable multiprocessing means
`further comprises: first internal buffer means for containing
`the unknown pattern and for containing at least one selected
`reference pattern of the plurality of reference patterns;
`second internal buffer means for containing results gener
`ated from the programmable multiprocessing means; and
`program storage means for containing instructions executed
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`by the programmable multiprocessing means.
`Further embodiments of the present invention include a
`computer implemented method of performing pattern rec
`ognition on an unknown pattern, the method comprising the
`computer implemented steps of executing high level pattern
`recognition instructions by a host processor means; execut
`ing lower level pattern recognition instructions by a pro
`grammable multiprocessor means to compare the unknown
`pattern against selected reference patterns, the step of
`executing lower level pattern recognition instructions fur
`ther comprising the steps of executing arithmetic instruc
`tions by an arithmetic pipeline; and executing pointer
`instructions by a pointer pipeline in parallel with the step of
`executing arithmetic instructions; and communicating
`between the host processor means and the programmable
`multiprocessor means via a host computer bus means; and
`transferring the selected reference patterns from a private
`memory array to the programmable multiprocessor means,
`the step of transferring bypassing the host computer bus
`C2S,
`Embodiments of the present invention include the above
`and further comprising the computer implemented steps of:
`transferring results of the programmable multiprocessor
`means over the host computer bus means to the host pro
`cessor means; and identifying the unknown pattern based on
`the results of the programmable multiprocessor means, the
`step of identifying performed by the host processor means.
`
`BRIEF DESCRIPTION OF THE DRAWENGS
`FIG. 1(A) is an illustration of a lattice constructed
`between points of a reference pattern and points of an input
`unknown pattern during a Dynamic Time Warping pattern
`recognition procedure.
`FIG. 1(B) is an illustration of a lattice construction
`between states of a reference pattern and probability states
`of an input unknown pattern during a Hidden Markov
`Models pattern recognition procedure.
`FIG. 2 is an overall block diagram of a computer system
`of the present invention utilizing a pattern recognition
`engine (with a private memory) for performing and report
`ing the results of pattern comparisons.
`FIG. 3(A) is a block diagram of pertinent components of
`a computer system of the present invention that utilize
`multiple pattern recognition engines for performing pattern
`recognition, each engine having separate memories.
`FIG. 3(B) is a block diagram of pertinent components of
`a computer system of the present invention that utilize
`multiple pattern recognition engines for performing pattern
`recognition, each engine sharing the same separate memory.
`FIG. 4 illustrates an overall process flow of a pattern
`recognition procedure that has various tasks partitioned
`between a system central processing unit and a pattern
`recognition engine of the present invention.
`FIG. 5 is a block diagram illustrating the major elements
`of pattern recognition engine of the present invention as well
`as the private off chip memory unit.
`FIG. 6 illustrates a block diagram of the elements of the
`execution unit of the pattern recognition engine of the
`present invention.
`FIG. 7 is a block diagram illustrating the two arithmetic
`pipelines, the two pointer pipelines, the data memories,
`pointer registers, and general purpose registers of the present
`invention.
`FIG. 8 is a block diagram of an arithmetic pipeline of the
`
`Page 19 of 53
`
`

`

`5,459,798
`
`S
`
`present invention.
`FIG. 9 is a detailed block diagram of an arithmetic
`pipeline of the present invention.
`FIG. 10 is an illustration of the interface of the pointer
`pipelines of the present invention to the arithmetic pipelines.
`FIG. 11 is a detailed block diagram of a pointer pipeline
`of the present invention.
`FIG. 12 is a detailed block diagram of the control flow
`pipeline of the present invention.
`FIG. 13 is a detailed diagram of the program counter logic
`of the present invention.
`FIG. 14 is a diagram of the internal logical functions of
`the memory to memory transfer unit and channel parameters
`of the present invention.
`FIG. 15 is a state and event diagram illustrating the states
`and events of a memory transfer channel of the present
`invention.
`FIG. 16 is a diagram illustrating a double buffering
`technique that can be employed by the present invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`6
`processing steps required for DTW and HMM procedures
`used for pattern recognition. It is appreciated that a full
`understanding of DTW and/or HMM procedures is not a
`requirement to understanding the elements of the present
`invention. In so far as the elements of the DTW and HMM
`procedures have driven the design of the present invention,
`these elements are discussed herein. It is noted that for
`additional background information regarding the well
`known DTW and HMM procedures used in voice and
`handwriting recognition, reference is made to: "An Intro
`duction to Hidden Markov Models," by L. R. Rabiner and B.
`H. Juang, IEEE ASSP Magazine, January 1986; T. Parsons
`author of "Voice and Speech Processing,” published by
`McGraw-Hill in 1987; "On line Handwriting Recogni
`tion-A Survey,” by C. C. Tappert, C. Y. Suen, and T.
`Wakahara, IEEE, 1988; and C. C. Tappert, "Cursive Script
`Recognition by Elastic Matching.” IBM J. Res. Develop.
`Vol. 26, No. 6, Nov. 1982.
`Regarding FIG. 1(A), there is illustrated a graphical
`representation of the two axis used in the Dynamic Time
`Warping (DTW) procedure used for pattern recognition.
`According to the DTW procedure, there are several refer
`ence patterns that are known and are placed into a reference
`library. One goal of the DTW procedure is to compare an
`unknown (input) pattern against the reference patterns of the
`library in order to locate a match between the unknown and
`the reference patterns. FIG. 1(A) graphically illustrates the
`DTW procedure applied to one reference pattern against the
`unknown pattern. It is appreciated that the DTW procedure
`operates, as will be described herein, for each reference
`pattern in the library against the unknown pattern. Along the
`vertical axis are plotted points (from 1 to 9) that comprise a
`reference pattern that is stored in the reference library within
`a memory unit of computer system. Along the horizontal
`axis is plotted points (from 1 to 9) that comprise an unknown
`pattern that is compared by the computer processing system
`against the reference pattern. As each point of the unknown
`is compared against each point of the reference pattern, a
`lattice or array of points is generated within the two axis.
`As each point is compared, a cost function is generated
`across the lattice that runs from left to fight across the lattice.
`A goal of the DTW procedure and the present invention is
`to locate the lowest cost path across the lattice for each
`reference pattern and compare the paths of each of the
`reference patterns in order to locate the best matched pattern
`to the unknown. Each point of the pattern has a given
`number of features. A classical feature of a point includes the
`spatial (x, y) coordinates of that point. DTW allows the
`computer system to locate the best way of distorting the
`unknown pattern to match the reference pattern at a mini
`mum cost. The cost is called the distance between the
`unknown pattern and the reference pattern. The reference
`pattern for which the distance to the unknown is the lowest
`is the best candidate for a pattern match. The DTW proce
`dure computes the lattice of points using well known
`Dynamic Programming techniques.
`At each point of the lattice, two independent computa
`tions need be performed by the present invention. First, a
`local distance (d), must be computed between the associated
`point of the unknown pattern verses the reference pattern
`point. Secondly, the best path to get to the current point from
`the "neighbor” points must be determined. The two com
`putations are performed in repetition during the DTW pro
`cedure. The independence between these two computations
`is the basic property used by the present invention to
`accelerate the DTW procedure. For example, the DTW
`procedure begins at the lower left side of the lattice (at point
`
`10
`
`5
`
`20
`
`25
`
`30
`
`I. Introduction
`The present invention includes an apparatus and method
`for accurate and high performance real-time pattern recog
`nition within a general purpose computer system that may be
`utilized for handwriting and voice recognition applications.
`The present invention includes a specially optimized mul
`tiprocessing hardware unit capable of performing, in paral
`lel, a multitude of steps required for pattern recognition
`procedures, such as Dynamic Time Warping and Hidden
`Markov Models. The present invention multiprocessing
`hardware unit may interface with the address/dam bus of a
`general purpose computer system operating a high level
`pattern recognition procedure; the multiprocessing hardware
`unit (also called Pattern Recognition Engine, (PR) executes
`the low level steps of the recognition procedure. The present
`invention provides a private memory array coupled to the
`PR engine for storage of reference patterns. The present
`invention may operate effectively on any general purpose
`desktop computer system or pen-based computer system,
`such as for example, a MacintoshTM platform available from
`45
`Apple Computer Inc., of Cupertino, Calif. or an IBM or IBM
`compatible personal computer system or platform.
`In the following derailed description of the present inven
`tion numerous specific details are set forth in order to
`provide a thorough understanding of the present invention.
`However, it will be obvious to one skilled in the art that the
`present invention may be practiced without these specific
`details. In other instances well known methods, apparatus,
`systems, components, and procedures have not been
`described in detail as not to unnecessarily obscure the
`present invention.
`
`35
`
`40
`
`50
`
`55
`
`II. DTW and HMM Pattern Recognition Procedures
`As discussed above, the present invention may be par
`ticularly used within the field of pattern recognition of
`computer systems. Two well known procedures utilized by
`pattern recognition computer systems are described. These
`procedures are called Dynamic Time Warping and Hidden
`Markov Models. The present invention is optimized to
`operate these procedures in order to render pattern recogni
`tion. Therefore, the following is a discussion of the pertinent
`
`60
`
`65
`
`Page 20 of 53
`
`

`

`10
`
`5
`
`20
`
`30
`
`25
`
`7
`6) and calculates upward along the first lattice line until the
`end (top) point is reached. Within the first vertical lattice
`line, the first point of the unknown pattern is compared
`against all of the points of the reference pattern. At the end
`of the first lattice line, the DTW procedure then starts at the
`second vertical lattice line (i.e., the line above unknown
`point 2 on the horizontal axis) and compares each of the
`reference pattern points against the second point of the
`unknown pattern and so forth down the lattice line for each
`unknown point.
`For instance, at point 10, the spatial feature of the fifth
`point of the unknown is compared against the fifth point of
`the reference pattern. Basically the (x, y) values associated
`with each of the points are subtracted from each other to
`yield the absolute value of the result. This is called the
`distance computation. Next, the DTW procedure examines
`the cost function of associated with each neighbor point to
`point 10, these would be points 11, 15, and 14 which are
`some valid neighbors in this DTW example. The neighbor
`with the lowest cost function is then selected, say point 14,
`and this value is then added to the distance value for point
`10. The path of the lowest cost (the best path) then includes
`the link point 14 to point 10. As the lattice grows from left
`to fight the lowest cost path will be generated. The operation
`used the in DTW procedure to determine the best neighbor
`point is called the path function in these discussions.
`As can been seen from this discussion a distance compu
`tation and a path computation are required for each point of
`the lattice for DTW processing. Each point of the unknown
`is compared against each point of the reference pattern
`generating a multitude of computations. Since there are no
`data dependencies between the best path computations and
`the distance computations for any individual point within the
`lattice, the present invention may perform these computa
`tions in parallel. Furthermore, each of the above two com
`35
`putations require pointers which indicate the locations of
`data used in the computation. The computations to update
`these pointers is also performed in parallel within the present
`invention. Therefore, the present invention is optimized to
`perform D