Building a real-time facial recognition system with Approximate Nearest Neighbors Oh Yeah (Annoy)

Tram Ho

Theory

What is ANNOY?

Tree-based algorithms are one of the most used things when it comes to ANN (Artificial Neural Networks). We construct forests from data by refactoring it into data subsets. One of the most outstanding solutions is Annoy.

Annoy: Approximate Nearest Neighbors Oh Yeah is a C ++ library with Python constraints to search for points in space close to a given query point.

Nearest neighbors and vector pattern

The figure above shows a set of two-dimensional points, but in reality most vector models have more than two dimensions. Our goal here is to build a data structure that allows us to find the points closest to any query point in linear time. We will build a tree that can query with a complexity of O (log n). That's the way Annoy works. In fact, it's a binary tree where each node is a random split.

First we will choose 2 random points on the plane and then divide the plane into two parts from those two random points (Figure above).

And keep going from the next 2 random points we divide into 2 planes, and so on until there are maximum K items in each node with the image above we choose K = 10

With the plane above we have the corresponding binary tree (above), we end up with a binary tree with explicit partitions with points being each node. We can see the points near each other in space on the plane with k = 10 being very close to each other in the tree. so we can find out which side of the plane we need to continue and that determines if we go down the left or right child. We then sort all the nodes by distance and return the nearest K neighbors. And that's how the search algorithm works in Annoy.

Annoy will perform well if there are more trees, with the way to add more trees, we will have the opportunity to find the most favorable splits.

The annoying "A" for " approximate " means that the approximation also makes sense while the search is lacking some acceptable points. The whole idea behind the approximate algorithm is to sacrifice a bit of accuracy in exchange for greater performance.

Library Face Recognition

A very famous face recognition library and quite good accuracy built on python's dlib and written in C ++. The accuracy of the model on Labeled Faces in the Wild is 99.38%.

Github : Here

API : Here

Install : pip install face_recognition

Practice

Step 1: Prepare the data

First, we will prepare the image data set with structure like this, in each folder with their own images.

Step 2: Save data on annoy

We will create an annoy_save.py file to save the images in these directories into annoy:

Expain code:

Step 3: Load data from annoy

Once the index file is saved as images.ann, we will start loading from that file:

Step 4: Get name

As for Step 1, we have the image folder of each person corresponding to their name for each of those folders, now we will take each person's name for each of their images in the folder and append to an array, you have If you ask me why, I will say more about this later:

Step 5: Face recognition

Yep, by this point we're about 70% of our work done:

After locating the face and the name of the person in the database, we will proceed to show it on the camera:

Result

While writing an article I do not understand anything, the below cmt okay, if you are not correct, please comment, thank you. 😄

Reference

https://github.com/spotify/annoy

https://github.com/ageitgey/face_recognition

https://www.pyimagesearch.com/2018/09/24/opencv-face-recognition/

https://face-recognition.readthedocs.io/en/latest/readme.html#installation

https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html

Share the news now

Source : Viblo