Today I tried local sensitivity hashing in C. The result is very interesting. Suppose you have N feature vectors, each vector is in R^D, you want to hash them to 1<<K bytes. Local Sensitivity Hashing give you the answer in O(NDK);
It might be useful for image compression. Of course, k-means is preferred and you should always work in LAB color space instead of GBR.
The feature vectors (LAB color) are stored in M[N][D].
P.S. Just a try, I did not generate uniform sampling.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
void LocalSensitivityHashing() { // init vector seeds srand(time(0) ^ 141592653); for (int i = 0; i < BUCKET_BITS; ++i) { for (int v = 0; v < VECTOR_LENGTH; ++v) { r[i][v] = ((float)rand() / (RAND_MAX)) * 2.0 - 1.0; } } // computer LSH for (int b = 0; b < FEATURE_ROWS; ++b) { int cluster_id = 0; for (int i = 0; i < BUCKET_BITS; ++i) { float hashsign = 0; for (int v = 0; v < VECTOR_LENGTH; ++v) { hashsign += (float)((float)M[b][v] - 127.5) * r[i][v]; } cluster_id <<= 1; if (hashsign >= 0) ++cluster_id; } LSH_val[b] = cluster_id; ++LSH_cnt[cluster_id]; for (int v = 0; v < VECTOR_LENGTH; ++v) { LSH_photon[cluster_id][v] += M[b][v]; } } } void outputLSH(int fid, int cid, Mat&out) { Mat reslab(HEIGHT, WIDTH, CV_8UC3); for (int i = 0; i < HEIGHT; ++i) { for (int j = 0; j < WIDTH; ++j) { int k = i * WIDTH + j; //for (int c = 0; c < CAMS; ++c) { for (int p = 0; p < 3; ++p) { reslab.at<Vec3b>(i, j)[p] = (uint8_t)((double)LSH_photon[LSH_val[k]][cid * 3 + p] / LSH_cnt[LSH_val[k]]); } //} } } cv::cvtColor(reslab, out, CV_Lab2BGR); } |
