Sobre mí

Hola Habr! Mi nombre es Pavel, trabajo como director técnico en una empresa dedicada a la producción de dispositivos IoT. Producimos muchas cosas, desde controladores domésticos inteligentes hasta dispositivos de medición inteligentes en nuestro protocolo de red de sensores patentado.

También actúan como el director general de la empresa de TI. En el pasado, ACM ICPC semifinalista de la programación de la Copa Mundial.

Motivación

Escribo este artículo porque nuestro equipo mató aproximadamente un mes para encontrar una solución (otras dos semanas para implementar y escribir pruebas) para almacenar y encontrar de manera eficiente a personas reconocidas en la base de datos, para ahorrar tiempo en sus proyectos. Spoiler: no encontraron nada listo como un complemento genial para el DBMS existente, pero los plazos eran abrumadores, por lo que escribimos nuestro propio DBMS para esta tarea (almacenar una gran cantidad de incrustaciones faciales). Mi artículo de ninguna manera pretende ser una guía exhaustiva, pero espero que brinde un punto de partida para un mayor estudio y desarrollo de nuestros pensamientos.

La incrustación es un mapeo de un vector discreto de características categóricas en un vector continuo con una dimensión predeterminada.

Entonces, ¿dónde comenzó todo

- , , , / , . , , , , . "" 87%, , , . , 3 . . 2-3 . — … , , - "" ( ) 6 . .

, , : ( ) , , , , , , . 10 200 , . , 50 . 10.

, +- , .

, , , dlib, . C++, BLAS, Python CPU. .

, dlib , 0.6, . 128.

, . , , , , , . , , k , k , , - -. , -, -.

.

. dlib .

def get_img_vector(img):
    dets = detector(img, 1)
    for k, d in enumerate(dets):
        shape = sp(img, d)
        return facerec.compute_face_descriptor(img, shape)
    return None

def prepare_database():
    database = {}

    for file in glob.glob("_images/*"):
        identity = os.path.splitext(os.path.basename(file))[0]
        img = cv2.imread(file, 1)

        database[identity] = get_img_vector(img)

    return database

def who_is_it(img, shape, database):
    face_descriptor1 = facerec.compute_face_descriptor(img, shape)

    min_dist = 100
    identity = None

    for (name, db_enc) in database.items():
        dist = distance.euclidean(db_enc, face_descriptor1)

        if dist < min_dist:
            min_dist = dist
            identity = name

    print(min_dist)
    if min_dist > 0.57:
        return None
    else:
        return str(identity)

if __name__ == "__main__":
    global sp
    sp = dlib.shape_predictor('weights/shape_predictor_face_landmarks.dat')
    global facerec
    facerec = dlib.face_recognition_model_v1('weights/dlib_face_recognition_resnet_model_v1.dat')
    global detector
    detector = dlib.get_frontal_face_detector()

    database = prepare_database()
    webcam_face_recognizer(database)

webcam_face_recognizer ( cv2- ) . who_is_it, . , , , , !

, 1 . (N*k), N — , k — . , , . , , - . .

, ?

— , , . — . , , , L2 .

scores = np.linalg.norm(face_descriptor1 - np.asarray(database.items()), axis=1)
min_el_ind = scores.argmax()

, , , .

, , nmslib. HNSW k . , . :

import nmslib

index = nmslib.init(method='hnsw', space='l2', data_type=nmslib.DataType.DENSE_VECTOR)

for idx, emb in enumerate(database.items()):
    index.addDataPoint(idx, emb)

index_params = {
    'indexThreadQty': 5,
    'skip_optimized_index': 0,
    'post': 3,
    'delaunay_type': 2,
    'M': 100,
    'efConstruction': 2000
}

index.createIndex(index_params, print_progress=True)
index.saveIndex('./db/database.bin')

HNSW .

"" . ?

, 4 . dlib , .

, . , , . .

postgresql

- , , (, . ) .

:

import postgresql

def setup_db():
    db = postgresql.open('pq://user:pass@localhost:5434/db')
    db.execute("create extension if not exists cube;")
    db.execute("drop table if exists vectors")
    db.execute("create table vectors (id serial, file varchar, vec_low cube, vec_high cube);")
    db.execute("create index vectors_vec_idx on vectors (vec_low, vec_high);")

:

query = "INSERT INTO vectors (file, vec_low, vec_high) VALUES ('{}', CUBE(array[{}]), CUBE(array[{}]))".format(
            file_name,
            ','.join(str(s) for s in encodings[0][0:64]),
            ','.join(str(s) for s in encodings[0][64:128]),
        )
db.execute(query)

:

import time
import postgresql
import random

db = postgresql.open('pq://user:pass@localhost:5434/db')

for i in range(100):
    t = time.time()
    encodings = [random.random() for i in range(128)]

    threshold = 0.6
    query = "SELECT file FROM vectors WHERE sqrt(power(CUBE(array[{}]) <-> vec_low, 2) + power(CUBE(array[{}]) <-> vec_high, 2)) <= {} ".format(
        ','.join(str(s) for s in encodings[0:64]),
        ','.join(str(s) for s in encodings[64:128]),
        threshold,
    ) + \
            "ORDER BY sqrt(power(CUBE(array[{}]) <-> vec_low, 2) + power(CUBE(array[{}]) <-> vec_high, 2)) ASC LIMIT 1".format(
                ','.join(str(s) for s in encodings[0:64]),
                ','.join(str(s) for s in encodings[64:128]),
            )
    print(db.query(query))
    print('inset time', time.time() - t, 'ind', i)

10^5 (4- i5, 2,33 GHz) 0.034 .
? +- ( ). , , … , .

K-d

- , , " ", . , .

, , , .

K-d — k- . , ( , . .), .

, :

.

(N) , , , (N). , !

"" , NDA.

. , .

15 . , . . .

— . , , :)

k-tree , ( ), , ( -), 4-6 . .

, . — 1,5 , , , , , , . , , .

, , , . , mail cloud. , .

Si hay otras opciones para resolver este problema, con mucho gusto lo leeré en los comentarios.

Y la moraleja de esta fábula es esta: la multitud incluso cayó El leónSoluciones de código abierto probadas por el tiempo. Aprenda algoritmos, pasans :)