home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / research / 400 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  3.3 KB
  1. Path: sparky!uunet!ogicse!mimbres.cs.unm.edu!moe.ksu.ksu.edu!usenet-feed.umr.edu!quandt
  2. From: quandt@cs.umr.edu (Brian Quandt)
  3. Newsgroups: comp.compression.research
  4. Subject: motion estimation
  5. Message-ID: <1993Jan27.024157.9222@umr.edu>
  6. Date: 27 Jan 93 02:41:57 GMT
  7. Article-I.D.: umr.1993Jan27.024157.9222
  8. Sender: cnews@umr.edu (UMR Usenet News Post)
  9. Organization: University of Missouri - Rolla, Rolla, MO
  10. Lines: 63
  11. Nntp-Posting-Host: next4.cs.umr.edu
  12.  
  13. First I apologize that my last message ended up containing nothing
  14. for the body... who knows why but anyways.
  15.  
  16. Well, since the last message got messed up I thought I would take my
  17. time and write this one with hopefully a clear head.
  18.  
  19. I'm working on MPEG motion estimation (eventually to become a
  20. parallel encoder... but that's later).  
  21.  
  22. A thought occurred to me whether the string matching algorithm found
  23. in Udi Manber's text "Introduction to Algorithms, A Creative Approach"
  24. pg 141, could be useful in effciently matching the macroblocks used in MPEG.
  25. Quickly stated:
  26.     Given two strings 'A' and 'B' match 'B' within the string 'A'.
  27.  
  28.     String 'B' is first preprossesed to generate a thing called a 'next' 
  29.     table.  Bascically this table reduces the amount of time that
  30.     'B' has to be looked at when a match against 'A' fails.  This
  31.     is the main 'time' saving feature of this alogrithm...if you 
  32.     need more help on this consult the book, but suffice it to say that
  33.     it involves things like 'prefix' and 'suffix' of a string.
  34.  
  35. So anyways I was wondering if this algorithm could apply to motion
  36. estimation.  My thought was to treat the macroblock to find as the 'B'
  37. string, preprocess it creating a 'next' table and then use this information
  38. to help find a match within the 'frame'.
  39.  
  40. THE PROBLEMS (at least the ones I immediately see)
  41.  
  42. 1) The string match algo is a 1-diminsional algorithm.  How can it
  43. be modified to work on 2-dim objects?
  44.  
  45.     My initial thought is to just pick a row within a macroblock and 
  46.     compare this against one row at a time within the frame.  When 
  47.     a match occurs (or find the best match) then use brute force to 
  48.     check the other rows of the macroblock with the appropriate rows
  49.     within the frame.  Since we are looking for a best match I would
  50.     just maintain the best (least errors) macroblock.
  51.  
  52. 2) Using the algorithm from above (chosing a row within the macroblock),
  53. which row should be chosen?
  54.  
  55.     Here I think the answer would be to choose the row that has the most 
  56.     random/differing data within it.  This should result in the 'string' 
  57.     matching algorithm to perform much better.
  58.  
  59. Okay so here's a rough outline of the algorithm
  60.     Set the found matched macroblock to NULL
  61.     Set the number of errors in matching to MAXINT (infinity)
  62.     Find the most random row within the macroblock.
  63.     Calculate 'next' for this row.
  64.     For each row within the frame (or whatever you search range).
  65.         Do the fast 'string' match using the 'next' table.
  66.             For each found matching prefix... calculate the error
  67.                 for the potential macroblock versus the macroblock to match.
  68.             If the error is better (less errors) save this potential macroblock.
  69.     The best matching macroblock should be found when finished.
  70.  
  71.  
  72. That should do it, I know I left lots out, but hopefully someone out there
  73. remembers this string matching alogrithm.  I appreciate hearing from anyone
  74.  
  75.                                 Brian Quandt
  76.