Суперпиксели, извлеченные с помощью энергетической выборки (SEEDS)

Question

Меня интересуют суперпиксели, извлекаемые с помощью энергетической выборки (SEEDS), которая является методом сегментации изображения с использованием суперпикселей. Это также то, что OpenCV использует для создания суперпикселей. У меня проблемы с поиском документации по алгоритму SEEDS. OpenCV дает очень общее описание, которое можно найти здесь.

Я ищу более подробное описание того, как работает SEEDS (общий обзор или математическое объяснение). Любые ссылки или мысли по поводу алгоритма будет высоко ценится! Я не могу найти хороший материал. Спасибо!

Answer 1

Сначала я перейду к некоторым общим ссылкам и ресурсам, а затем попытаюсь описать общую идею алгоритма.

Реализация SEEDS:

Вы, очевидно, уже видели документацию здесь. Пример использования для реализации SEEDS в OpenCV можно найти здесь: https://github.com/Itseez/opencv_contrib/blob/6cd8e9f556c8c55c05178dec05d5277ae00020d9/modules/ximgproc/samples/seeds.cpp, и позволяет адаптировать количество суперпикселей, количество уровней и другие параметры в реальном времени - так что после чтения на Идея, лежащая в основе SEEDS, вы обязательно должны попробовать на примере. Исходную реализацию, а также пересмотренную реализацию (часть моей дипломной работы) можно найти на GitHub: https://github.com/davidstutz/superpixels-revisited/tree/master/lib_seeds и https://github.com/davidstutz/seeds-revised. Реализации должны быть довольно сопоставимыми.

Публикация и другие ресурсы:

Документ был выпущен на arxiv: http://arxiv.org/abs/1309.3848. Несколько более короткое описание (за которым легче следовать) доступно на моем веб-сайте: http://davidstutz.de/efficient-high-quality-superpixels-seeds-revised/. Приведенное описание алгоритма должно быть простым в использовании и, в лучшем случае, позволять внедрять SEEDS (см. Раздел "Алгоритм" статьи). Более точное описание также можно найти в моей дипломной работе, в частности в разделе 3.1.

Общее описание:

Обратите внимание, что это описание основано как на вышеупомянутой статье, так и на моей дипломной работе. Оба предлагают математически краткое описание.

Дано изображение с шириной W и высота H, SEEDS начинается с группировки пикселей в блоки размера w x h, Эти блоки в дальнейшем объединены в группы 2 x 2, Эта схема повторяется для L уровни (это параметр количества уровней). Так на уровне l, у вас есть блоки размера

w*2^(l - 1) x h*2^(l - 1).

Количество суперпикселей определяется блоками на уровне L т.е. w_L а также h_L обозначим ширину и высоту блоков на уровне L количество суперпикселей

S = W/w_L * H/h_L

где мы используем целочисленные деления.

Начальная сегментация суперпикселей, которая теперь итеративно уточняется путем обмена блоками пикселей и отдельными пикселями между соседними суперпикселями. С этой целью вычисляются цветные гистограммы суперпикселей и всех блоков (гистограммы определяются параметром количества бинов в реализации). Это можно сделать эффективно, если увидеть, что гистограмма суперпикселя является просто суммой гистограмм 2 x 2 блоков, из которых он состоит, и гистограмма одного из этих блоков является суммой гистограмм 2 x 2 базовые блоки (и так далее). Так что давайте h_i быть гистограммой блока пикселей, принадлежащих суперпикселю j, а также h_j гистограмма этого суперпикселя. Тогда сходство блока j суперпикселю j вычисляется пересечением гистограммы h_i а также h_j (см. один из вышеуказанных ресурсов для уравнения). Точно так же сходство пикселя и суперпикселя - это либо евклидово расстояние цвета пикселя до среднего цвета суперпикселя (это более эффективный вариант), либо вероятность того, что цвет пикселя принадлежит суперпикселю (который просто нормализован запись гистограммы суперпикселя в цвете пикселя). На этом фоне алгоритм можно обобщить следующим образом:

initialize block hierarchy and the initial superpixel segmentation
for l = L - 1 to 1 // go through all levels
    // for level l = L these are the initial superpixels
    for each block in level l
        initialize the color histogram of this block
        // as described this is done using the histograms of the level below
// now we start exchanging blocks between superpixels
for l = L - 1 to 1
    for each block at level l
        if the block lies at the border to a superpixel it does not belong to
            compute the histogram intersection with both superpixels
            assign the block to the superpixel with the highest intersection
// now we exchange individual pixels between superpixels
for all pixels
    if the pixel lies at the border to a superpixel it does not belong to
        compute the Euclidean distance of the pixel to both superpixel's mean color
        assign the pixel to the closest superpixel

На практике обновления блоков и обновлений пикселей повторяются чаще, чем единицы (что является параметром количества итераций), и часто выполняется вдвое больше итераций на уровень (что является параметром двойного шага). В исходной сегментации число суперпикселей вычисляется из w, h, L и размер изображения. В OpenCV, используя приведенные выше уравнения, w а также h вычисляется из требуемого количества суперпикселей и количества уровней (которые определяются соответствующими параметрами).

Один параметр остается неясным: предыдущий пытается установить гладкие границы. На практике это делается с учетом 3 x 3 окрестности вокруг пикселя, который будет обновляться. Если большинство пикселей в этом районе принадлежат суперпикселю j пиксель, подлежащий обновлению, также с большей вероятностью будет принадлежать суперпикселю j (и наоборот). Реализация OpenCV, а также моя реализация (пересмотренная SEEDS), позволяют учитывать большие окрестности k x k с k in {0,...,5} в случае OpenCV.