Rotation and scale invariant profiles are generated for matching to a pattern template using a fast regular shaped pattern construction method. The invention achieves rotation invariant matching, rotation and scale invariant matching, and/or scale invariant matching. Invariant profiles are used to perform fast rotation, rotation and scale, or scale invariant search for initial detection of match candidates. The rotation invariant contours of this invention approximate circular contours through use of regular shaped patterns such as octagon or multiple rotated octagons. Rotation invariant search does not depend on rotation angles and is very fast.