A new method for object search is proposed. Conventional template matching schemes tend to fail in presence of irregularities and ill-conditions like background variations, illumination fluctuations resulting from shadowing or highlighting etc. The proposed scheme is robust against such irregularities in the real world scenes since it is based on matching gradient information around each pixel, computed in the form of orientation codes, rather than the gray levels directly. A probabilistic model for robust matching is given and verified by real image data. Experimental results for real world scenes demonstrate the effectiveness of the proposed method for object search in the presence of different potential causes of mismatches.