A relatively simple motion search, known as "EPZS" or "Diamond", is as follows. Let us define the SAD function as follows: it takes the source block to be comp

A relatively simple motion search, known as "EPZS" or "Diamond", is as follows. Let us define the SAD function as follows: it takes the source block to be compared to, and a candidate block location in a reference frame. Each block is a 16x16 array of 8-bit unsigned values with a large stride (since its smack in the middle of a much larger reference image). SAD(mx,my) means compare the current block to the reference block located at <mx,my>, where <0,0> is the colocated block in the reference frame. The function itself sums up, for each 8-bit value (x from 0 to 255), abs(source[x]-ref[x]). Note that SAD is always run on unaligned data (well, 15/16 of the time). For speed purposes, SADs are usually done in groups of 4. With this method, on modern CPUs, assuming that the data is in cache, a, unaligned 16x16 SAD takes: Nehalem: 38 clocks Penryn: 49 clocks Conroe: 52 clocks (Don't have the Phenom numbers on me, but its around the high 30s) Also note that in practice, the SAD function, at the end, adds the approximate bit cost of the motion vector to the candidate score. This is very important, because this bit cost depends on its difference from the predicted motion vector. Diamond search: For the current macroblock: 1. Start at the predicted motion vector. Let this value be <mx,my>. Set bsad equal to SAD(mx,my). 2. Set bsad equal to the lowest of SAD(mx-1,my), SAD(mx+1,my), SAD(mx,my-1), SAD(mx,my+1), and the previous bsad. 3. Set the new mx and my equal to the ones which gave the lowest SAD value. 4. If mx and my did not change in 2), terminate. Otherwise, GOTO 2. This has two non-CUDA-friendly portions to it: 1. You must know the predicted motion vector: you can't simply search all blocks independently, as the predicted motion vector depends on the top, left, top right, and left blocks relative to the current one. 2. Some blocks might need 1 iteration, some might need 15. It gets worse when you realize how damn fast the CPU can do SADs (38 clocks to process 512 pixels, on a single core!). Note that using the exhaustive search I mentioned above, sequential elimination, a modern CPU can get this value down to an "effective" 5-6 clocks per 16x16 block SAD. Now, from my reverse engineering based on output bitstreams, I know approximately how Badaboom, the (rather awful) nVidia CUDA GPU encoder, does its motion search. 1. Set n = 16. 2. Downscale the image by a factor of n. 3. Do the above algorithm on this image. 4. Divide n by 2. 5. Downscale the image by a factor of n. 6. Each motion vector from before now represents the vector on 4 blocks. 7. Refine the motion vectors on these four blocks by a constant X number of iterations of diamond search (I'm guessing one or two). 8. If n isn't 1, GOTO 4. Note how much more GPU-friendly this algorithm is. Its called a pyramidal search. It has many disadvantages though, such as the fact that it results in many false motion vectors (as the highly-downscaled search can move a whole bunch of blocks in a given direction due to some small motion in the center of that bunch of blocks, and then that vector doesn't get reversed back to normal in the lower level searches).