Алгоритм и структура данных для поиска и сохранения соседства суперпикселей в C++

У меня есть изображение, содержащее результаты сегментации, как это. введите здесь описание изображения

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

Здесь числа обозначают отдельные участки, а линии — окрестности участков. Пока не могу понять с чего начать, какие ключевые слова гуглить.

Может ли кто-нибудь предложить что-нибудь полезное?

Изображение хранится в классе OpenCV cv::Mat, что касается графика, я планирую использовать библиотеку Boost.Graph.

Так что, пожалуйста, дайте мне несколько ссылок на примеры кода и алгоритмы или ключевые слова.

Спасибо.

Обновить. После кофе-брейка и некоторых дискуссий мне пришло в голову следующее.

  1. Постройте большой решетчатый граф, где каждый узел соответствует каждому пикселю изображения, а связи соединяют 8 или 4 соседа.
  2. Пометьте каждый узел графика соответствующим значением пикселя.
  3. Попробуйте как-то объединить узлы с одинаковыми метками.

Другая моя проблема в том, что я не знаком с BGL (но книга уже в пути :)).

Итак, что вы думаете об этом решении?

Update2 Вероятно, эта ссылка может помочь.

Однако решение до сих пор не найдено.


c++ data-structures boost-graph
person wl2776    schedule 18.12.2012    source источник

Ответы (3)


arrow_upward
5
arrow_downward

Вы можете решить это так:

  1. Определить регионы (ваши цифры на графике)

    • make a 2D array which stores the region number
    • начните с (0/0) и установите его на 1 (номер региона)
    • установите весь регион как 1, используя алгоритм заливки или что-то в этом роде.
    • во время заполнения вы, вероятно, сталкиваетесь с координатами, которые имеют другой цвет. хранить их в очереди. начните заполнение с этих координат и увеличьте номер региона, если предыдущее заполнение выполнено.

    .

  2. Сделать связи между регионами

    • iterate through your 2D array.
    • если у вас есть соседние номера, сохраните пару номеров (возможно, в отсортированном виде, вы также должны проверить, существует ли пара уже или нет). Вам нужно только проверить элемент ниже, справа и одну диагональ справа, если вы продвигаетесь слева направо.

Хотя я должен признать, что ничего не знаю об этой теме.. просто моя простая идея..

person duedl0r    schedule 18.12.2012

arrow_upward
2
arrow_downward

Вы можете использовать BFS, чтобы отметить регионы.

Чтобы открыть cv::Mat для BGL, вы должны написать много кода. Я думаю, что писать свои собственные bfs гораздо проще.

Затем вы за каждых двух негров пишете свои оценки в std::set<std::pair<mark_t, mark_t>>. И чем строить график из этого.

person kassak    schedule 18.12.2012

arrow_upward
1
arrow_downward

Я думаю, что если ваши цветовые пятна настолько случайны, вам, вероятно, понадобится алгоритм грубой силы, чтобы делать то, что вы хотите. Идея может быть:

  • Сделайте первый проход грубой силы. Это должно идентифицировать все патчи. Например, создайте матрицу A того же размера, что и изображение, и инициализируйте ее значением 0. Для каждого пикселя, который все еще равен нулю, начните с него и пометьте его как новый патч, и попробуйте метод грубой силы, чтобы найти весь размер патча. Тогда каждая ячейка матрицы будет иметь значение, равное номеру патча, в котором она находится.
  • Номера патчей должны быть 2^N, например 1, 2, 4, 8, ...
  • Создайте еще одну матрицу B размером с изображение, но каждая ячейка содержит два значения. Это будет представлять связь между пикселями. Для каждой ячейки матрицы B первым значением будет абсолютная разница между номером патча в пикселе и номером патча соседнего пикселя. Первое значение — это разница с пикселем ниже, второе — с пикселем слева.
  • Выберите все уникальные значения в матрице B, у вас есть все возможные соединения.

Это работает, потому что каждая разница между номерами патчей уникальна. Например, если в B вы окажетесь с числами 3, 6, 7, это будет означать, что между участками (4,1), (8,2) и (8,1) есть контакты. Значение 0, конечно же, означает, что в одном и том же патче есть два пикселя рядом друг с другом, поэтому вы просто их игнорируете.

person Svalorzen    schedule 18.12.2012