home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / ai / 4341 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  3.0 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!jvnc.net!nuscc!iti.gov.sg!news
  2. From: kaykit@iti.gov.sg (Chan Kay Kit (KSL))
  3. Newsgroups: comp.ai
  4. Subject: A pattern recognition problem
  5. Message-ID: <1992Nov19.111439.25445@iti.gov.sg>
  6. Date: 19 Nov 92 11:14:39 GMT
  7. Sender: news@iti.gov.sg (News Admin)
  8. Reply-To: kaykit@iti.gov.sg
  9. Organization: Information Technology Institute, National Computer Board, S'pore
  10. Lines: 75
  11.  
  12.  
  13. Hello,
  14.  
  15.     I have an interesting problem on hand that I feel should have
  16. been solved before but have been unable to find any literature on. Hence
  17. I hope to seek some pointers by airing the problem in this newsgroup.
  18.  
  19.     Say there are a few types of printed documents each with its own
  20. different format and layout. These documents are simple enough to be 
  21. segmented into rectangles containing pure text (assuming the documents are
  22. clean and clearly printed). All rectangles so segmented are either upright
  23. or lie flat ie. the text is not tilted. 
  24.  
  25.     The formats have been so restricted such that the spatial 
  26. relationships between all the rectangles is sufficient to distinguish 
  27. the different types of documents. The size of individual rectangles is
  28. of secondary importance as the width or height of some of them can vary even 
  29. within a single format. For a particular format, it is known in advance
  30. which rectangle is of variable height/width. 
  31.  
  32.     Spatial relationships refer to the type of overlap between any
  33. 2 rectangles both in the horizontal and the vertical direction eg. for
  34. the horizontal direction, some possible overlap types are
  35.  
  36.  
  37. _________________
  38. _______
  39.  
  40.  
  41. and
  42.  
  43. ________________
  44.     _______
  45.  
  46. and
  47.  
  48. _____________
  49.         ____________    
  50.  
  51.  
  52.  
  53. The effect of variable size rectangles is that, for some rectangle-pairs, the
  54. overlap types can vary from one document to the next for a single document
  55. type.
  56.  
  57.     For each type of document, I have scanned in a typical sample,
  58. segmented it into rectangles and computed the spatial relationships between 
  59. all pairs of rectangles. 
  60.  
  61.     THE PROBLEM IS THIS: given a new document, how do I match its pattern of 
  62. rectangles to the database of known formats to determine its type? The algorithm
  63. must be robust enough to handle noise in this new document which can corrupt the
  64. pattern of rectangles. It should also be able to output a similiarity measure for
  65. the document type(s) that it has chosen so that one can reject the document as 
  66. being foreign if one deems the similiarity to be too low.
  67.  
  68.     At first glance, I thought syntactic pattern recognition or case-based 
  69. reasoning might be a good way to solve the problem. Are there any pattern 
  70. recognition gurus out there who can offer suggestions/ftpable code/references 
  71. for an accurate and efficient solution? If so, please email to kaykit@iti.gov.sg. 
  72. If there is sufficient interest, I will summarise all replies to the net. 
  73.  
  74.     Thanks a million!
  75.  
  76. (Sorry for occupying so much bandwidth)
  77.  
  78.  
  79.  
  80.  
  81.  
  82. ---
  83. Kay-Kit CHAN                | Internet: kaykit@iti.gov.sg
  84. Knowledge Systems Lab            | Bitnet:   kaykit@itivax
  85. Information Technology Institute    | Tel:      (65) 772-0920
  86. National Computer Board of Singapore    | Fax:      (65) 770-3043
  87.