Tentang diriku

Halo, Habr! Nama saya Pavel, saya bekerja sebagai direktur teknis di sebuah perusahaan yang bergerak dalam produksi perangkat IoT. Kami memproduksi banyak hal - mulai dari pengontrol rumah pintar hingga perangkat pengukuran pintar pada protokol jaringan sensor yang kami patenkan.

Mereka juga bertindak sebagai direktur umum perusahaan IT. Di masa lalu, semi finalis ACM ICPC dari pemrograman Piala Dunia.

Motivasi

Saya menulis artikel ini karena tim kami membunuh sekitar satu bulan untuk menemukan solusi (dua minggu lagi untuk mengimplementasikan dan menulis tes) untuk menyimpan dan secara efisien menemukan orang-orang yang dikenal dalam database, untuk menghemat waktu bagi Anda dalam proyek Anda. Spoiler: mereka tidak menemukan sesuatu yang siap pakai seperti plug-in keren untuk DBMS yang ada, tetapi tenggat waktu sangat menyala, jadi kami menulis DBMS kami sendiri untuk tugas ini (menyimpan embeddings wajah dalam jumlah besar). Artikel saya sama sekali tidak mengklaim sebagai panduan lengkap, tetapi saya berharap artikel ini akan memberikan titik awal untuk studi lebih lanjut dan pengembangan pemikiran kita.

Embedding adalah pemetaan dari vektor diskrit fitur kategorikal ke dalam vektor kontinu dengan dimensi yang telah ditentukan.

Jadi dari mana semua itu bermula?

- , , , / , . , , , , . "" 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. , .

Jika ada opsi lain untuk menyelesaikan masalah ini, saya dengan senang hati akan membacanya di komentar.

Dan moral dari dongeng ini adalah ini - orang banyak bahkan jatuh singasolusi open source diuji oleh waktu. Pelajari algoritma, pasan :)