Как обрабатывается изображение в оптической мыши? Неужели текущее изображение сравнивается с предыдущим, двигая его в разные стороны пока не получится наибольшее сходство? Но ведь на это надо куча времени!

http://www.ixbt.com/peripheral/mice-sensor.shtml
google рулит

Спасибо, но это лишь обзорная статья о мышах. Об алгоритмах там нет ничего

Вам скорее надо обратится к литературе по сжатию видео. Любой алгоритм основан на определении вектора (или векторов) смещения изображения. На MPEG2 точно должна быть документация в сети.

Насколько помнится из косвенных сведений алгоритм примерно именно такой

В простейшем случае для простой светящей диодом мышки.
смотрим на квадрат 16х16 или немногим более и следим куда оно (картинко) поехало. На самом деле это не так трудно - особенно когда у вас спец чип который заточен скажем на рассчет корреляции для 8 или менее битных входных данных.

Так как мыш дает информацию только о dx dy - т.е. о изменении координат - то ошибки определения смещения более менее не мешают жить.

А что вас так пугает в поиске смещения картинки относительно картинки?

вот вам принтер который гораздо круче мышки в плане точности вычисления своих координат и тоже работает на принципе "смещение картинки".
http://printdreams.com/inside/printbrush.html

Был когда-то сканер, работающий как этот printbrush - жаль канул в Лету

Алгоритм называется Optical Flow, ищите в гугле и википедии.