Efficient watchlist searching with normalized similarity

1. A method for face recognition and response, comprising:

extracting a face image from a video stream;

generating a pre-processed index by determining the similarity distances between face images stored in a watchlist, where a similarity distance (x,y) between a face image x and a face image y is based on a normalized similarity score s(x,y) as d(x,y)=√{square root over (1−s(x,y) 2 )};

searching a pre-processed index for a watchlist image that matches the face image, based on a similarity distance that is computed from a normalized similarity score to satisfy metric properties, wherein the index of the watchlist includes similarity distances between face images stored in the watchlist; and

performing an action responsive to a determination that the extracted face image matches the watchlist image.

2. The method of claim 1 , wherein generating the pre-processed index further includes partitioning the watchlist and generating respective indices for each partition.

3. The method of claim 1 , wherein determining the normalized similarity scores further includes dividing each initial similarity score by a maximum similarity score.

4. The method of claim 3 , wherein determining the normalized similarity scores further includes determining the maximum similarity score by a comparison of a face image with itself.

5. The method of claim 1 , wherein searching a pre-processed index includes performing an approximating and eliminating search.

6. The method of claim 1 , wherein searching the pre-processed index includes:

searching the pre-processed index in a number of iterations; and

halting the searching of the pre-processing index responsive to the determination that the number of steps has reached a maximum number of iterations.

7. The method of claim 1 , wherein the action is selected from the group consisting of sounding an alarm, locking a door, changing the operational status of one or more machines, triggering an environmental control, and engaging or disengaging a traffic control device.

8. A method for face recognition and response, comprising:

a hardware processor; and

a memory that stores a computer program product, which, when executed by the hardware processor, causes the hardware processor to:

extract a face image from a video stream;

generate a pre-processed index by determining the similarity distances between face images stored in a watchlist, where a similarity distance (x,y) between a face image x and a face image y is based on a normalized similarity score s(x,y) as d(x,y)=√{square root over (1−s(x,y) 2 )};

search a pre-processed index for a watchlist image that matches the face image, based on a similarity distance that is computed from a normalized similarity score to satisfy metric properties, wherein the index of the watchlist includes similarity distances between face images stored in the watchlist; and

perform an action responsive to a determination that the extracted face image matches the watchlist image.

9. The system of claim 8 , wherein the computer program product further causes the hardware processor to partition the watchlist and generate respective indices for each partition.

10. The system of claim 8 , wherein the computer program product further causes the hardware processor to divide each initial similarity score by a maximum similarity score to generate the normalized similarity scores.

11. The system of claim 10 , wherein the computer program product further causes the hardware processor to determine the maximum similarity score by a comparison of a face image with itself.

12. The system of claim 8 , the search of the pre-processed index includes an approximating and eliminating search.

13. The system of claim 8 , wherein the computer program product further causes the hardware processor to search the pre-processed index in a number of iterations, and to halt search of the pre-processing index responsive to the determination that the number of steps has reached a maximum number of iterations.

14. The system of claim 8 , wherein the action is selected from the group consisting of sounding an alarm, locking a door, changing the operational status of one or more machines, triggering an environmental control, and engaging or disengaging a traffic control device.