Patent ID: 6823077
Filing Date: 2004-11-23
Classification: G06F,G06K

Abstract:
A method of interpolation to ascertain relative movement along an axis in an optical navigation system, the method comprising the steps of:(a) illuminating a work surface to be navigated upon; (b) coupling light reflected as an image on the illuminated work surface to an array of photo detectors that produce output signals whose amplitudes represent features in the image; (c) digitizing to multiple bits the output signals of step (b) to create a reference array stored in a memory; (d) applying a spatial filter to the reference array of step (c) to create a filtered reference array stored in memory, each value in the filtered reference array being a single bit; (e) digitizing to multiple bits the output signals of another instance of step (b) to create a sample array stored in memory; (f) applying a spatial filter to the sample array of step (e) to create a filtered sample array stored in memory, each value in the filtered sample array being a single bit; (g) subsequent to steps (d) and (f), comparing by an exclusive OR operation shifted versions of one of the filtered arrays with an unshifted version of the other, the shifts including one pixel left, one pixel left and one pixel down, one pixel down, one pixel down and one pixel right, one pixel right, one pixel right and one pixel up, one pixel up, and a null shift that is in the center of the foregoing eight shifts, and for each such shift adding to an accumulation the number of exclusive OR operations that indicate differences between bits in the filtered arrays; (h) storing, as correlation values, the differences accumulated for each shifted version in the position of a correlation array that corresponds to the shifts of step (g); (i) selecting at least three correlation values from the correlation array that represent no trial shifting along one axis and the various remaining trial shifts along the axis to be interpolated on; (j) determining which of the correlation values selected in step (i) represents the least correlation; (k) associating with the correlation value determined in step (j) an adjacent correlation value from the ones selected in step (i) that is also nearer the center of the correlation array than the one determined in step (j), but that has the same sign of trial pixel shift or is the null shift; (l) associating a first straight line with the values of step (k), the coordinate system of the line pixel displacements for the trial shifts as an abscissa and correlation value as an ordinate; (m) associating a second straight line with a remaining correlation value corresponding to a trial pixel shift of sign opposite that of step (k) and slope that is the negative of that of the first line, the coordinate system for the second line being the same as for the first line; and (n) finding the abscissa of the intersection of the first and second lines.