Main content

Alert message

Inventor: Dr. Hagit Hel-Or, Haifa

   

Background

   

In pattern matching, the goal is to find all the occurrences of a given pattern in a given signal. The pattern and the signal’s domain can be 2D (images) or higher in other cases (e.g., 3D in video streams).

 

Pattern matching can be performed by measuring the “similarity” between the pattern and every “window” within the signal whose size is similar to the pattern size. The similarity is defined by a distance measure and a pre-defined threshold. Any signal window whose distance is under the pre-defined threshold is considered similar.

   

New Invention

   

Fast and real-time pattern matching, block matching in motion estimation and in mpeg video compression, real-time non-parametric texture synthesis, feature detection.

 

This invention presents a new technique to solve pattern matching problems very quickly, when the distance measure is either Euclidean or normalized inner-product.

 

Based on successive projections of each signal window onto a set of vectors, each such projection produces a single value from which a lower boundary on the true distance is obtained. As the number of projections increase, the lower boundary becomes tighter.

 

During the projection process, any window whose lower boundary is above the pre-defined threshold is rejected from further consideration. The projection vectors are chosen in a classical technique, but such that the projections are fast to compute and the tight lower boundary is obtained quickly (using few projections).

 

The innovation defines the projection vectors used and develops a novel, efficient, and quick technique for projecting signal windows onto these vectors. The technique reduces run time by two orders of magnitude over existing techniques.

   

Applications

   

Cellular companies that do pattern recognition (e.g. face/car detection).