Структура данных и алгоритм объединения нескольких диапазонов целых чисел в C

Question

Я работаю над проблемой Computer Vision, в которой мне нужно объединить области изображения. Область (или большой двоичный объект) определяется его линиями, то есть следующей областью O:

  0123456789
0 XXXXOXXXXX
1 XXXOOOXXXX
2 XXXOOXXXXX
3 XXXOXXXXXX
4 XXXXXXXXXX

определяется как:

row: 0, cols: 4-4
row: 1, cols: 3-5
row: 2, cols: 3-4
row: 3, cols: 3-3

Я выбрал эту структуру данных, потому что мне нужно быстро найти соседей региона, т. Е. Все пиксели, которые "касаются" его.

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

С этой настройкой у меня есть два вопроса:

1. В C какова лучшая структура данных для этих данных? Типичное изображение - 16x16, что означает не так много строк / столбцов. Я сделаю много слияний (цель состоит в том, чтобы начать с одной области на пиксель и закончить одной большой областью, то есть 16x16 - 1 слиянием). Я мог бы пойти с указателем и распределить / освободить вещи, или использовать char * для хранения cols и последующего синтаксического анализа, например.

2. Как эффективно объединить два региона? Мне нужно найти потенциальные столбцы, которые находятся рядом, чтобы объединить их (например, 3-5 и 6-9 становятся 3-9), желательно без перераспределения и копирования.

Answer 1

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

unsigned short image[16]

Объединение может быть выполнено с помощью побитовой логики, которая довольно эффективна для массива из 16 элементов.

Answer 2

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

Billy3

Answer 3

Если память не является проблемой, возможно, можно улучшить скорость поиска, сохраняя указатели на соседние пиксели.например, создать структуру «Pixel», в которой будет храниться ее значение и список указателей на соседние пиксели.Как упомянуто выше, создайте многомерный массив 16x16 пикселей.Как только память настроена, просмотрите массив и настройте список соседних пикселей, чтобы он указывал на соседние пиксели.После того, как все настроено, поиск пикселя и его соседей должен быть очень быстрым.

Answer 4

Готовы ли вы обменять пространство на скорость? В таком случае вы можете статически выделить всю структуру 16x16.

struct Image {
    struct Range ranges[16*16];
};

каждая строка ([0..15], [16..31] ...) будет содержать не более 16 различных диапазонов (при условии, что у вас нет только двоичных данных, в таком случае 8 будет), последний диапазон будет обозначаться каким-либо часовым значением, например, «-1», «0» или чем-то еще.

В зависимости от операции, может быть предпочтительнее задать диапазон структуры, например:

struct Range {
    int startpos;
    int count; /* or int endpos - depending on your preference */
};

Слияние путем создания нового изображения легко - вы проходите каждую строку в обоих «входных» изображениях одновременно с левой стороны и выводите ту, у которой меньше «startpos», в случае объединения соседних областей вы обновляете последнюю записанную область ,

Объединение на месте не так уж сложно, с некоторым буфером это можно сделать и за один прогон.