Блог

Я ищу способ кластеризации по одной ссылке с помощью OpenCV. Мой сценарий:

• Сотни (потенциально тысячи) векторов объектов (размерность векторов может составлять до ~ 800 объектов).
• Неизвестное количество кластеров (вероятно, намного меньше, чем количество векторов).
• Исправлен порог сходства E — если норма l1 между двумя векторами меньше E , то векторы должны находиться в одном кластере.
• Мне не нужно, чтобы кластер был компактным. То есть мне не нужно, чтобы все векторы в кластере находились внутри E друг друга. Это может привести к длинным «цепочкам» вместо кластеров, но я согласен с этим.

Я пытался использовать K-means, но поскольку я не знаю количества кластеров, это здесь неприменимо. Я мог бы выполнять итеративные K-средние значения и искать лучшее K, но это звучит неэффективно. Есть ли более подходящий алгоритм кластеризации, реализованный в OpenCV, который я мог бы использовать здесь?

В идеале мне нужно что-то похожее на алгоритм SLINK, поскольку это то, что цитируется в статье, которую я сейчас пытаюсь реализовать. Мои варианты — реализовать SLINK напрямую (небольшая задача из-за отладки и тестирования) или искать существующий алгоритм, который делает что-то подобное.

Есть предложения?

Я бы предложил построить график по вашему порогу сходства и найти связанные компоненты. Как только вы построите график, поиск связанных компонентов будет довольно простым и эффективным. Если вам нравится NetworkX, в нем уже есть функция подключенного компонента.

В итоге я сам выполнил реализацию:

 import cv
def main():
    import sys
    x = cv.Load(sys.argv[1])
    epsilon = float(sys.argv[2])
    y = cv.CloneImage(x)
    labels = range(x.height)
    tmp = cv.CreateImage((x.width, 1), x.depth, x.nChannels)
    for i in range(x.height):
        cv.SetImageROI(x, (0, i, x.width, 1))
        for j in range(i 1, x.height):
            cv.SetImageROI(y, (0, j, x.width, 1))
            cv.AbsDiff(x, y, tmp)
            dist, _, _, _ = cv.Avg(tmp)
            if dist < epsilon:
                for k, lbl in enumerate(labels):
                    if lbl == j:
                        labels[k] = i

    for i, lbl in enumerate(labels):
        print i, lbl

if __name__ == '__main__':
    main()
  

x представляет собой N x M матрицу, содержащую N векторы. Размерность вектора равна M . Он в основном сравнивает каждую пару векторов, используя норму L1, и считает пару идентичной, если их разница меньше epsilon . Этот алгоритм очень медленный O(N^3) , но на данный момент он достаточно хорош для меня.