🚀 go-pugleaf

First I apologize that my last message ended up containing nothing
for the body... who knows why but anyways.

Well, since the last message got messed up I thought I would take my
time and write this one with hopefully a clear head.

I'm working on MPEG motion estimation (eventually to become a
parallel encoder... but that's later).  

A thought occurred to me whether the string matching algorithm found
in Udi Manber's text "Introduction to Algorithms, A Creative Approach"
pg 141, could be useful in effciently matching the macroblocks used in MPEG.
Quickly stated:
	Given two strings 'A' and 'B' match 'B' within the string 'A'.

	String 'B' is first preprossesed to generate a thing called a 'next' 
	table.  Bascically this table reduces the amount of time that
	'B' has to be looked at when a match against 'A' fails.  This
	is the main 'time' saving feature of this alogrithm...if you 
	need more help on this consult the book, but suffice it to say that
	it involves things like 'prefix' and 'suffix' of a string.

So anyways I was wondering if this algorithm could apply to motion
estimation.  My thought was to treat the macroblock to find as the 'B'
string, preprocess it creating a 'next' table and then use this information
to help find a match within the 'frame'.

THE PROBLEMS (at least the ones I immediately see)

1) The string match algo is a 1-diminsional algorithm.  How can it
be modified to work on 2-dim objects?

	My initial thought is to just pick a row within a macroblock and 
	compare this against one row at a time within the frame.  When 
	a match occurs (or find the best match) then use brute force to 
	check the other rows of the macroblock with the appropriate rows
	within the frame.  Since we are looking for a best match I would
	just maintain the best (least errors) macroblock.

2) Using the algorithm from above (chosing a row within the macroblock),
which row should be chosen?

	Here I think the answer would be to choose the row that has the most 
	random/differing data within it.  This should result in the 'string' 
	matching algorithm to perform much better.

Okay so here's a rough outline of the algorithm
	Set the found matched macroblock to NULL
	Set the number of errors in matching to MAXINT (infinity)
	Find the most random row within the macroblock.
	Calculate 'next' for this row.
	For each row within the frame (or whatever you search range).
		Do the fast 'string' match using the 'next' table.
			For each found matching prefix... calculate the error
				for the potential macroblock versus the macroblock to match.
			If the error is better (less errors) save this potential macroblock.
	The best matching macroblock should be found when finished.


That should do it, I know I left lots out, but hopefully someone out there
remembers this string matching alogrithm.  I appreciate hearing from anyone

								Brian Quandt