OpenCvSharpをつかう　その8 (LSH)

OpenCvSharp

突然レベルが急上昇している気がしますが、LSHのサンプルを作ってみたのでご紹介します。LSHの関数はOpenCV 2.0で追加されました。

LSH (Locality Sensitive Hashing)とは

わざわざこのように節を作りましたが、実のところ勉強が足りないものでほとんど説明が出来ません。現状での自分の理解を書いておきます。


指定したクエリと近い値を、何万次元といった高次元のデータから探索するとします。普通にやると大変です。

これを「距離が近いと同じ値になる」ようなハッシュ関数を使って高速化します。あらかじめ検索対象のデータをハッシュ化してテーブルに入れておきます。検索するときは、クエリを同じハッシュ関数にかけてハッシュ値にして、テーブルから同じ値のものを引いてきます。ハッシュテーブルからの探索の計算量は O(1) ですから高速というわけです。

ここまではいいとして、ではそんな都合の良いハッシュ関数なんてあるのか、というところがこのLSHの核心になってくるのですが、そこまでは理解が追いついていないので、興味がある方はどうぞお調べになってください。

OpenCVでのLSH

OpenCVでは、CvLSHという構造体がLSHの処理の中心となります。あらかじめ検索対象のデータをハッシュ化してテーブルに入れておくのはcvLSHAdd, 検索を行うのはcvLSHQueryという関数が対応します。この2つに加え、CvLSH構造体を初期化するcvCreateMemoryLSH、解放するcvReleaseLSH、基本的にこの4つを押さえておけば良さそうです。(cv.hでの定義)

CvLSHを初期化する関数にはcvCreateMemoryLSHの他に、cvCreateLSHというものもあります。こちらを使うと、ソースコードをざっと見てみた限りでは、自前で定義したハッシュテーブルを使うことが出来るようです。cvCreateMemoryLSHを使うと、OpenCV内部で既に定義されたハッシュテーブルが使われるようですので、通常はこちらを使えばよいと思います。なおOpenCvSharpではcvCreateLSHは実質未サポートです。

要は、検索対象とクエリのデータさえあれば、ハッシュ関数はどうするかとか難しいことは考えずにLSHができます。

コード

先人のCvLSHを使ったコードは調べた限りではほとんど皆無で、かろうじて以下のものが見つかりました。
http://moscoso.org/pub/video/opencv/svn/opencvlibrary/trunk/opencv/tests/python/lsh_tests.py
このtest_basicを参考にしました。

実は以下のコードも何をやっているかいまいちよくわからないし、そもそも合ってるのかも不明なのですが、10000次元のデータを64次元に圧縮して、探索を行っています。探索対象データに良く似たクエリを用意して探索して、正しくマッチするか確かめているのだと思います。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using OpenCvSharp;

/// <summary>
/// Locality Sensitive Hashing
/// </summary>
/// <remarks>
/// http://moscoso.org/pub/video/opencv/svn/opencvlibrary/trunk/opencv/tests/python/lsh_tests.py
/// </remarks>
class LSH
{
    static void Main(string[] args)
    {
        const int D = 64;
        const int N = 10000;
        const int K = 1;

        // constructs a LSH table
        using (CvLSH lsh = Cv.CreateMemoryLSH(D, N))
        {
            // creates test data
            Random rand = new Random();
            CvMat data = CreateRandomData(N, D, rand);
            CvMat queryPoints = CreateQueryPoints(data, rand);   

            // adds vectors to the LSH
            Cv.LSHAdd(lsh, data);

            // queries the LSH n times for at most k nearest points
            CvMat indices = new CvMat(N, K, MatrixType.S32C1);
            CvMat dist = new CvMat(N, K, MatrixType.F64C1);
            Cv.LSHQuery(lsh, queryPoints, indices, dist, K, 100);

            // calculates percent of correct results
            int correct = 0;
            for (int i = 0; i < N * K; i++)
            {
                //Console.WriteLine(indices[i]);
                if (indices[i] == i)
                    correct++;
            }
            double percent = (double)correct / (N*K) * 100;
            Console.WriteLine("correct: {0}%", percent);
        }

        Console.ReadLine();
    }

    static CvMat CreateRandomData(int n, int d, Random rand)
    {
        CvMat data = new CvMat(n, d, MatrixType.F64C1);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < d; j++)
            {
                data[i, j] = rand.NextDouble() * 2 - 1;
            }
        }
        return data;
    }

    static CvMat CreateQueryPoints(CvMat data, Random rand)
    {
        const double R = 0.4;
        int n = data.Rows;
        int d = data.Cols;
        CvMat query = new CvMat(n, d, MatrixType.F64C1);

        for (int i = 0; i < n; i++)
        {
            double[] ra = CreateRandomArray(d, rand);
            double sqsum = Math.Sqrt(ra.Sum<double>(elem => elem * elem));

            for (int j = 0; j < d; j++)
            {
                double add = (rand.NextDouble() * R * ra[j]) / sqsum;
                query[i, j] = data[i, j] + add;
            }
        }
        return query;
    }

    static double[] CreateRandomArray(int length, Random rand)
    {
        double[] arr = new double[length];
        for (int i = 0; i < length; i++)
        {
            arr[i] = rand.NextDouble();
        }
        return arr;
    }
}

おそらく99.7%程度の値が出力されるかと思います。


なお、OpenCvSharpでは、Cv.LSHQuery(lsh, ...); のような関数は、

lsh.Query( .... );

と書くこともできます。しっくりくるほうをどうぞ。

新版暗号技術入門 秘密の国のアリス

新版暗号技術入門 秘密の国のアリス