Fast Orthogonal Haar Transform PatternMatching via Image Square Sum

Although using image strip sum, an orthogonal Haar transform (OHT) pattern matching algorithm may have good performance, it requires three subtractions to calculate each Haar projection value on the sliding windows. By establishing a solid mathematical foundation for OHT, this paper based on the concept of image square sum, proposes a novel fast orthogonal Haar transform (FOHT) pattern matching algorithm, from which a Haar projection value can be obtained by only one subtraction. Thus, higher speed-ups can be achieved, while producing the same results with the full search pattern matching. A large number of experiments show that the speed-ups of FOHT are very competitive with OHT in most cases of matching one single pattern, and generally higher than OHT in all cases of matching multiple patterns, exceeding other high-level full search equivalent algorithms.