Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced       Help   

 The Delphion Integrated View

  Buy Now:   Buy PDF- 20pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
 Email this to a friend  Email this to a friend 
Title: US5067166: Method and apparatus for DP matching using multiple templates
[ Derwent Title ]

Country: US United States of America

View Images High


20 pages

Inventor: Ito, Nobuyasu; Kawasaki, Japan

Assignee: International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
 News, Profiles, Stocks and More about this company

Published / Filed: 1991-11-19 / 1990-03-23

Application Number: US1990000498310

IPC Code: Advanced: G06F 17/30; G06K 9/62; G06K 9/70; G06T 7/00; G10L 11/00; G10L 15/06; G10L 15/12;
IPC-7: G06K 9/68;

ECLA Code: G06F17/30Z1T; G06F17/30Z2P5;

U.S. Class: Current: 382/215; 382/226; 707/E17.012; 707/E17.039;
Original: 382/037; 382/030; 382/038;

Field of Search: 381/041,42,43 382/030,34,37,38 364/513.5

Priority Number:
1989-03-24  JP1989000070442

Abstract: A pattern recognition method and apparatus using dynamic programming in which an input sequence of labels is matched to a set of candidate templates (candidate reference label sequences). The set of candidate reference label sequences is grouped into subsets, where each reference label sequence in a subset has a common root reference label subsequence. Using this set organization, a depth-first search is performed to identify a local optimum template and its local optimum match score with the input sequence of labels. Using the local optimum match score as a threshold, the input sequence of labels is matched to root reference label subsequences, eliminating those root reference label subsequences having match scores above the threshold. Surviving root reference label subsequences having match scores below the threshold remain recognition candidates, and are further investigated.

Attorney, Agent or Firm: Schechter, Marc D. ;

Primary / Asst. Examiners: Moore, David K.; Couso, Jose L.

Maintenance Status: E2 Expired  Check current status

INPADOC Legal Status: Show legal status actions          Buy Now: Family Legal Status Report

Designated Country: DE FR GB 

Family: Show 6 known family members

First Claim:
Show all 14 claims
I claim:     1. A method for DP matching multiple label-sequences which form templates comprising the steps of:
  • (a) generating from said multiple label-sequences a tree-structured dictionary having a root node, a plurality of intermediate nodes, a plurality of end nodes, and a plurality of paths from the root node through intermediate nodes to end nodes, each intermediate and each end node having only one incoming path segment from the root node to the intermediate node, each intermediate node having one ancestor node adjacent to the intermediate node along the incoming path segment into the intermediate node, each intermediate node having at least one outgoing path segment from the intermediate node to an end node, each intermediate node having one or more descendent nodes adjacent to the intermediate node along the outgoing path segments from the intermediate node, where each node corresponds to one label, and storing it in a storage device,
  • (b) providing such label node in said tree-structured dictionary with a buffer area in said storage device,
  • (b1) selecting an ancestor node in said tree-structured dictionary, said selected ancestor node having at least two descendent nodes,
  • (c) selecting one descendent node of the two or more descendent nodes of the selected ancestor node, performing a stage calculation between the label corresponding to the selected descendent node and an input label sequence and storing the result in the buffer provided for the selected descendent node, the step (c) comprising the sub-steps of:
  • (c1) referring to the stage calculation result stored in the buffer for the selected ancestor node,
  • (c2) determining a label in the input label sequence providing the minimum value of the stage calculation result obtained in said sub-step (c1) and
  • (c3) selecting a descendent node of the selected ancestor node, which descendent node corresponds to a label having the minimum distance from a label immediately after the label determined in the sub-step (c2) in the input label sequence, and
  • (d1) if the selected descendent node is not an end node, then replacing the selected ancestor node with the selected descendent node, and repeating step (c), and
  • (d2) after performing the stage calculation for the node which corresponds to the end of one template, storing the stage calculation result obtained for the end node with the identification data of the template as solution candidate information into said storage device.

Background / Summary: Show background / summary

Drawing Descriptions: Show drawing descriptions

Description: Show description

Forward References: Show 37 U.S. patent(s) that reference this one

U.S. References: Go to Result Set: All U.S. references   |  Forward references (37)   |   Backward references (3)   |   Citation Link

Patent  Pub.Date  Inventor Assignee   Title
Get PDF - 14pp US3979722  1976-09 Sakoe  Nippon Electric Company, Ltd. Automatic character recognition device employing dynamic programming
Get PDF - 29pp US4467437  1984-08 Tsuruta et al.  Nippon Electric Co., Ltd. Pattern matching device with a DP technique applied to feature vectors of two information compressed patterns
Get PDF - 11pp US4882756  1989-11 Watari  NEC Corporation Pattern matching system using dynamic programming
Foreign References: None

Other Abstract Info: DERABS G90-292183 JAPABS 140581P000122

Other References:
  • Ney, H., et al. "A Data Driven Organization of the Dynamic Programming Beam Search for Continuous Speech Recognition", Proc. ICASSP 87, pp. 833-836, 1987.
  • Sakoe, H., "A Generalization of Dynamic Programming Based Pattern Matching Algorithm Stack DP-Matching", Transactions of the Committee on Speech Research, The Acoustic Society of Japan, p. S83-23, 1983.
  • Sakoe, H., "A Generalized Two-Level DP-Matching Algorithm for Continuous Speech Recognition", Transactions of the IECE of Japan, vol. E65, No. 11, pp. 649-656, Nov. 1982.

  • Inquire Regarding Licensing

    Powered by Verity

    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2014 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help