Some kind of a low-resolution high speed camera and optics that takes many photos (at hundreds or thousands of frames per second) of the surface it is moving on, and compares them in real time with a built-in purpose-built processor to measure motion. Preferably all on a chip, with a convenient MCU interface.
In other words, an optical mouse sensor.

Unfortunately, it looks like the Avago parts are no longer stocked in distribution, but you could hack an optical mouse, which will give you the optics and the illumination LED as well (you may have to modify the optics to get an appropriate distance). Many of the sensors appear to be from Pixart in Taiwan, and the datasheets are available (often not true).