Large Scale Face Recognition with NMSLIB

Non-Metris Space Library or shortly NMSLIB is an efficient similarity search package. We have mentioned similarity search solutions of tech giants: Spotify Annoy and Facebook Faiss. However, this package was developed by just a few PhD students. Amazon adopted nmslib in Elasticsearch recently. Product and service recommendations, image, document and video search are some use cases for similarity search. We are going to adapt nmslib similarity search library into a face recognition task in this post.

Webinar

There are billions images indexed by Google but reverse image search returns responses just in seconds. This has nothing to do with the hardware it has. You can either continue to read this tutorial or watch the following video. They both cover large scale facial recognition with NMSLIB.

---

🙋‍♂️ You may consider to enroll my top-rated machine learning course on Udemy

---

As Ara Guler declared if the best camera had taken the best photograph then the one would be the best novelist who has the best typewriter.

Face recognition pipeline

We should remember the common stages of a modern face recognition pipeline. These are detection, alignment, representation and verification. We feed a facial image to a CNN model and it returns a representation. Verification step finds the distance between representations of a face pair and verify them as same person if the distance is less than a threshold.

If the number of face pairs a huge, e.g. millions, response times might be problem in a face recognition pipeline. This post aims to solve this trouble with an approximation method.

Installation

Its python distribution is stable and available on PyPI. I run my tests with its 2.0.6 version in this study.

#!pip install nmslib==2.0.6
import nmslib

Data set

There are several facial images in the DeepFace package unit test folder.

#Clone images from this repo: https://github.com/serengil/deepface/tree/master/tests/dataset
files = []
for r, d, f in os.walk("deepface/tests/dataset/"):
    for file in f:
        if ('.jpg' in file):
            exact_path = r + file
            files.append(exact_path)

Deepface framework for python wraps several state-of-the-art face recognition models: VGG-Face, Google FaceNet, OpenFace, Facebook DeepFace, DeepID, Dlib and ArcFace.

I will build a Dlib ResNet face recognition model.

FaceNet, VGG-Face, Dlib and ArcFace overperform among others. Here, you can watch how to determine the best model.

---

---

Facial representations

Represent facial images with Dlib ResNet model.

embeddings = []
for index in tqdm(range(0, len(files)), desc='Finding embeddings'):
    img_path = files[index]
    embedding = DeepFace.represent(img_path = img_path, model_name = "Dlib")[0]["embedding"]
    embeddings.append(embedding)

Synthetic data generation

Unit test folder stores a few facial images. I will create a synthetic data to make the problem more complex.

for i in tqdm(range(len(embeddings), 1000000), desc='Finding embeddings'):
    key = 'deepface/tests/dataset/synthetic_%d' % (i)
    vector = [random.gauss(-0.35, 0.48) for z in range(embedding_size)]

    embeddings.append(vector)
    files.append(key)

Finally, convert embeddings list to numpy array because nmslib expects numpy type as input.

embeddings = np.array(embeddings)

Embeddings object is (1M, 128) shaped numpy array. In other words, it stores 1M 128 dimensional vectors.

Target image

We are going to search the following target image in 1M data set.

We will detect and align face of the target image firstly. Secondly, represent facial image as 128 dimensional vector with Dlib ResNet model. Thirdly, make it 2D matrix as nmslib expects.

target_representation = DeepFace.represent(img_path = "target.jpg", model_name = "Dlib")[0]["embedding"]

#(128,) to (1, 128)
target_representation = np.expand_dims(target_representation, axis = 0)

Initialization

We can initialize the nmslib index based on the similarity metric: euclidean distance and cosine similarity.

metric = 'euclidean'
if metric == 'euclidean':
    index = nmslib.init(space='l2')
elif metric == 'cosine':
    index = nmslib.init(space='cosinesimil')

Initialization lasts 0.00010442733764648438 seconds.

Adding vectors to index

We then add the vector representations of the faces to the index. Here, embeddings object is (1M, 128) shaped numpy array. In other words, it stores 1M 128 dimensional vector.

index.addDataPointBatch(embeddings)

Adding data points lasts 0.805 seconds.

---

---

Building the index

We should build the index when data points added. I will be able to search any vector in this built index. Notice that building is done once.

index_time_params = {'M': 15, 'indexThreadQty': 4, 'efConstruction': 100}
index.createIndex(index_time_params)

Building lasts 263.9547507762909 seconds. This is very huge against Annoy and Faiss.

Searching in the index

I can find the most similar vectors in the built index fast.

neighbors, distances = index.knnQueryBatch(target_representation, k = 3, num_threads = 4)[0]

Searching lasts 0.0034360885620117188 seconds

Notice that I will run knn query batch command when I search an entity in my data set. But I don’t have to build index in each call. Building can be planned weekly or monthly.

Brute force

Brute force method lasts 7.18 seconds. On the other hand, adding data points lasts 0.805 seconds, creating index lasts 263 seconds, knn query lasts 0.003 seconds. Notice that I can store the built index in production and just call knn query stage. So, nmslib is 2300 times faster than the brute force method over 1M vectors.

distances = []
for embedding in embeddings:
    distance = findEuclideanDistance(target_representation, embedding)
    distances.append(distance)

idx = np.argmin(distances)
print("Nearest one: ", idx)

Save and restoration the index

As I mentioned, index building is costly operation but you don’t have to re-build it always. That’s why, you should save the built index and restore it when you need.

#save
index.saveIndex('index.bin', save_data=False)

#restore
restored_index = nmslib.init(space='l2')
restored_index.loadIndex('index.bin')
restored_index.knnQueryBatch(target_representation, k = 3, num_threads = 4)

Scalability

Spotify Annoy, Facebook Faiss and NMSLIB are amazing libraries enabling us to search on very large scale data set fast. But they are very core libraries and scalability of those libraries on production pipelines might be problematic. Herein, Elasticsearch wraps NMSLIB to perform approximate nearest neighbor algorithm but it comes with highly scalability feature by default. In this way, we can run a-nn algorithm on many clusters easily.

Face recognition with deepface

Face recognition can be handled within deepface. It handles all common stages of a face recognition pipeline: detect, align, represent and verify. Also, it applies face verification several times in the background. All you need is to call find function and it returns a pandas data frame.

#!pip install deepface
from deepface import DeepFace
 
models = ['VGG-Face', 'Facenet', 'OpenFace', 'DeepFace', 'DeepID', 'Dlib']
 
df = DeepFace.find(img_path = "img.jpg", db_path = "C:/my_db", model_name = models[0])
print(df.head())

It wraps state-of-the-art VGG-Face, Google FaceNet, OpenFace, Facebook DeepFace, DeepID and Dlib face recognition models.

---

---

Here, you can watch how face verification is handled in deepface.

Face recognition requires to apply face verification several times.

The other ann packages

Spotify Annoy is not the unique approximate nearest neighbor implementation of the open source community. If you like this post, I strongly recommend you to read this tutorial:

• Large Scale Face Recognition with Facebook Faiss
• Large Scale Face Recognition with Spotify Annoy
• Large Scale Face Recognition with Elasticsearch

Picking up the right tool for the right job is important. If your use case requires to creating and building index often, then search time is the key performance. On the other hand, if your use case requires to re-build index often, then adding embeddings and index building times are important. The following table demonstrates the times I spent for those a-nn packages on 1M vectors.

Map Reduce Technology

Approximate nearest neighbor algorithm reduces the time complexity dramatically but it does not guarantee to find the closest ones always. If you have million level data, big data systems and map reduce technology might match your satisfactions if your concern is not to discard important ones. Herein, mongoDB, Cassandra, Redis and Hadoop are the most popular solutions.

Tech Stack Recommendations

Face recognition is mainly based on representing facial images as vectors. Herein, storing the vector representations is a key factor for building robust facial recognition systems. I summarize the tech stack recommendations in the following video.

Conclusion

So, we’ve mentioned nmslib to perform knn algorithm and similarity search on a large scale data set. It seems that nmslib is much slower than Spotify Annoy and Facebook Faiss. Still it is faster than Faiss but slower than Annoy in searching step.

I pushed the source code of this study into the GitHub. You can support this study if you star⭐️ the repo.

---

Like this blog? Support me on Patreon

---