Efficient search for a gray-level pattern in an image using ranges of sums

A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for discarding incorrect transformations when trying to find an optimal transformation of a gray level pattern in an image, the method comprising the steps of:

• dividing a transformation space into a plurality of groups of translations;
• creating one or more image arrays, each image array includes one or more sums of pixels of a region of said image;
• creating one or more pattern arrays, each pattern array includes one or more sums of pixels of a region of said pattern;
• creating one or more minimum arrays based on said image arrays, wherein said minimum arrays contain the minimum value of a portion of said image arrays;
• creating one or more maximum arrays based on said image arrays, wherein said maximum arrays contain the maximum value of a portion of said image arrays;
• determining a first difference value for each group, each first difference value based on a first pattern array, a first minimum array corresponding to said first image array and a first maximum array corresponding to said first image array;
• and
• discarding translations in one or more groups having a first difference value greater than a previously determined best known difference value, wherein the best known difference value corresponds to a first difference value for a previously considered group.

An apparatus for finding a transformation of a gray level pattern in an image, comprising:

• an input device;
• a display for showing said image;
• a processing unit in communication with said input device and said display;
• and
• a processor readable storage device in communication with said processing unit, said processor readable storage device storing processor readable code, said processor readable code for programming said processing unit to perform a method comprising the steps of:
• dividing a transformation space into a plurality of groups of translations,
• creating one or more image arrays, each image array includes one or more sums of pixels of a region of said image,
• creating one or more pattern arrays, each pattern array includes one or more sums of pixels of a region of said pattern,
• creating one or more minimum arrays based on said image arrays, wherein said minimum arrays contain the minimum value of a portion of said image arrays,
• creating one or more maximum arrays based on said image arrays, wherein said maximum arrays contain the maximum value of a portion of said image arrays,
• determining a first difference value for each group, each first difference value based on a first pattern array, a first minimum array corresponding to said first image array and a first maximum array corresponding to said first image array,
• discarding translations in one or more groups having a first difference value greater than a previously determined best known difference value, wherein the best known difference value corresponds to a first difference value for a previously considered group, and
• determining which translation that has not been discarded has an optimal difference value, said translation having said optimal difference value is said best transformation of said gray level pattern in said image.