Объясните этот алгоритм (Сравните точки в алгоритме SURF)

Question

Мне нужно знать, известен ли этот алгоритм:

void getMatches(IpVec &ipts1, IpVec &ipts2, IpPairVec &matches, float ratio) {
    float dist, d1, d2;
    Ipoint *match;

    matches.clear();

    for (unsigned int i = 0; i < ipts1.size(); i++) {
        d1 = d2 = FLT_MAX;

        for (unsigned int j = 0; j < ipts2.size(); j++) {
            dist = ipts1[i] - ipts2[j];

            if (dist < d1) // if this feature matches better than current best
            {
                d2 = d1;
                d1 = dist;
                match = &ipts2[j];
            } else if (dist < d2) // this feature matches better than second best
            {
                d2 = dist;
            }
        }

        // If match has a d1:d2 ratio < 0.65 ipoints are a match
        if (d1 / d2 < ratio) {
            // Store the change in position
            ipts1[i].dx = match->x - ipts1[i].x;
            ipts1[i].dy = match->y - ipts1[i].y;
            matches.push_back(std::make_pair(ipts1[i], *match));
        }
    }
}

---

class Ipoint {
public:

    //! Destructor

    ~Ipoint() {
    };

    //! Constructor

    Ipoint() : orientation(0) {
    };

    //! Gets the distance in descriptor space between Ipoints

    float operator-(const Ipoint &rhs) {
        float sum = 0.f;
        for (int i = 0; i < 64; ++i) {
            //std::cout << i << "\n";
            try {
                sum += (this->descriptor[i] - rhs.descriptor[i])*(this->descriptor[i] - rhs.descriptor[i]);
            } catch (char *str) {
                std::cout << "Caught some other exception: " << str << "\n";
            }

        }
        return sqrt(sum);
    };

    //! Coordinates of the detected interest point
    float x, y;

    //! Detected scale
    float scale;

    //! Orientation measured anti-clockwise from +ve x-axis
    float orientation;

    //! Sign of laplacian for fast matching purposes
    int laplacian;

    //! Vector of descriptor components
    float descriptor[64];

    //! Placeholds for point motion (can be used for frame to frame motion analysis)
    float dx, dy;

    //! Used to store cluster index
    int clusterIndex;
};

Сравнивает результаты алгоритма SURF.

1. Это алгоритм ближайшего соседа? Похоже, что функция ищет ближайшую точку каждой точки.
2. Могу ли я сделать то же самое, используя Quadtree или kd-tree?
3. Есть лучший алгоритм для сравнения точек изображений и определения, являются ли они одинаковыми или похожими?
4. Желательно, чтобы я хотел сохранить их в mysql и построить дерево kd для сравнения 1 изображения по всем изображениям, это возможно?
5. RANSAC полезен для чего-либо в этой задаче?
6. Есть ли какой-нибудь способ отловить ложные срабатывания?

Answer 1

Вы задали много вопросов, и я не думаю, что смогу ответить на все из них, но вот ответы на как можно большую часть вашего вопроса.

1. Это, безусловно, алгоритм ближайшего соседа, цель которого состоит в том, чтобы найти две ближайшие точки к каждой точке в первом векторе и затем проверить, меньше ли отношение их расстояний, чем какое-либо значение отсечки.

2. Вы могли бы сделать это с помощью дерева quadtree или kd, но поскольку все ваши точки являются одномерными значениями, вы могли бы добиться большего успеха, используя сбалансированное двоичное дерево поиска. При наличии такого дерева, если вы пронизываете связанный список через узлы, вы можете найти k ближайших соседей к некоторой контрольной точке p, посмотрев ближайший элемент p в двоичном дереве поиска, а затем пройдя (k + 1) шаги в каждом направление и взятие k ближайших точек того, что вы найдете. Это выполняется за время O (lg n + k), где n - количество точек, а k такое же, как указано выше. Это существенно более эффективно, чем то, что у вас есть сейчас, что занимает O (n) время на поиск.

   Если размерность вашего векторного элемента больше 1, но меньше 20, тогда использование kd-деревьев было бы очень эффективной мерой.

   Для более высоких размерностей вы можете либо уменьшить число измерений с помощью PCA, прежде чем применять kd-дерево, или использовать более масштабируемую структуру ANN, такую ​​как хеширование, зависящее от местоположения.

3. SURF лучше всего подходит для обнаружения сцен и объектов. Если вам необходимо выяснить, совпадают ли два изображения, вам лучше использовать алгоритмы глобального дескриптора, такие как GIST. Преимущество использования глобального дескриптора состоит в том, что вы получаете один вектор для всего изображения, а сравнение изображений выполняется с простым евклидовым расстоянием.

4. Вы можете определенно сделать это, используя MySQL, потому что вам не нужно kd-дерево. Достаточно простого сбалансированного двоичного дерева.

5. RANSAC - это метод оценки параметров модели, устойчивый к выбросам. Это полезно для использования функций SURF для объединения нескольких фотографий в 3D-сцену.

6. Проверка на ложные срабатывания, безусловно, является упражнением для машинного обучения, и я не очень хорошо обучен в этой области. Вероятно, вы могли бы сделать это, используя контролируемый алгоритм обучения (такой как SVM, расширенное дерево решений или нейронная сеть), но я не знаю достаточно, чтобы дать вам совет по этому вопросу.

Надеюсь, это поможет!

Answer 2

Я просто отвечу на 5, так как templatetypedef обращается к остальным.RANSAC - это метод оценки параметров (вроде поиска линии, наиболее подходящей для набора точек данных).Таким образом, это непосредственно не полезно в поисках ближайшего соседа.