Алгоритм и структура данных для поиска и хранения окрестности суперпикселей в Stack Overflow
У меня есть изображение, содержащее результаты сегментации, как этот.
Мне нужно построить график окрестностей патчей, раскрашенных в разные цвета.
В результате я хотел бы структуру, представляющую следующее
Здесь числа представляют отдельные участки, а линии представляют окрестности участков.
В настоящее время я не могу понять, с чего начать, какие ключевые слова для Google.
Кто-нибудь может предложить что-нибудь полезное?
Изображение хранится в классе OpenCV cv :: Mat, а для графика я планирую использовать библиотеку Boost.Graph.
Поэтому, пожалуйста, дайте мне несколько ссылок на примеры кода и алгоритмы или ключевые слова.
Благодарю.
Обновить.
После перерыва на кофе и некоторых дискуссий мне пришло в голову следующее.
- Постройте большой граф решетки, где каждый узел соответствует каждому пикселю изображения, а ссылки соединяют 8 или 4 соседа.
- Пометьте каждый узел графа соответствующим значением пикселя.
- Попробуйте как-то объединить узлы с одинаковой меткой.
Другая моя проблема в том, что я не знаком с BGL (но книга уже в пути :)).
Итак, что вы думаете об этом решении?
Update2
Возможно, это ссылка на сайт может помочь.
Однако решение до сих пор не найдено.
Решение
Вы можете решить это так:
-
Определите регионы (ваши цифры на графике)
- сделать 2D массив, в котором хранится номер региона
- начать с (0/0) и установить его в 1 (номер региона)
- установить весь регион как 1, используя алгоритм залива или что-то в этом роде.
- во время заливки вы, вероятно, встречаете координаты, которые имеют разный цвет. хранить их в очереди. начните заполнение с этих координат и увеличьте номер региона, если ваше предыдущее заполнение выполнено.
.
-
Сделать ссылки между регионами
- переберите свой 2D массив
- если у вас есть соседние номера, сохраните пару номеров (вероятно, отсортированным образом, вам также необходимо проверить, существует ли пара уже или нет). Вам нужно только проверить элемент ниже, справа и диагональ вправо, если вы продвигаетесь слева направо.
Хотя я должен признать, что ничего не знаю об этой теме … просто моя простая идея ..
Другие решения
Вы могли бы использовать BFS отмечать регионы.
Чтобы выставить cv :: Mat в BGL, вы должны написать много кода. Я думаю, что написание ваших собственных bfs намного проще.
Чем ты за каждых двух негров пишешь свои оценки std::set<std::pair<mark_t, mark_t>>,
И чем построить график из этого.
Я думаю, что если ваши цветовые пятна случайны, вам, вероятно, понадобится алгоритм грубой силы, чтобы делать то, что вы хотите. Идея может быть:
- Сделайте первый пассивный перебор. Это должно идентифицировать все патчи. Например, сделайте матрицу A того же размера, что и изображение, и инициализируйте ее равной 0. Для каждого пикселя, который по-прежнему равен нулю, начните с него и отметьте его как новый патч, и попробуйте метод грубой силы, чтобы найти целое протяженность патча. Каждая ячейка матрицы будет иметь значение, равное номеру патча, в котором она находится.
- Номера патчей должны быть
2^Nнапример 1, 2, 4, 8, … - Сделайте еще одну матрицу B размером изображения, но каждая ячейка содержит два значения. Это будет представлять связь между пикселями. Для каждой ячейки матрицы B первое значение будет абсолютной разницей между номером фрагмента в пикселе и номером фрагмента смежного пикселя. Первое значение — это разница с пикселем ниже, второе — с пикселем слева.
- Выберите все уникальные значения в матрице B, у вас есть все возможные соединения.
Это работает, потому что каждая разница между количеством патчей уникальна. Например, если в B вы получите цифры 3, 6, 7, это будет означать, что между патчами (4,1), (8,2) и (8,1) есть контакты. Значение 0, разумеется, означает, что в одном патче есть два пикселя рядом друг с другом, поэтому вы просто игнорируете их.
detector