Я пытаюсь сделать узора водных потеков алгоритма диагностики с 8-подключениями для двоичного изображения (монохромного) (координат ограничивающей коробки вверх-влево и вниз-вправо точек), которые использовать небольшое количество памяти (необходимо, поскольку большое разрешение изображения) на C++. Есть такие инструменты, как OpenCV, но у него много фильтров и слишком медленно, если вы хотите обнаружить каждый blob в двоичном образе, есть также CvBlobsLib, но поддержка устарела (последняя версия до 5 лет), а я coudnt настроил его для Visual Studio 2013 (он должен быть скомпилирован с помощью Cmake, и он дает ошибки). В википедии есть два типа алгоритмов: «один компонент времени» и «двухпроходный» conected-component, но оба они используют метки, означающие, что у вас будет еще один 2D массив целых чисел, но для этого потребуется много памяти, потому что от размера int (4 байта), и нам нужно int из-за размера изображения и возможности более 65535 ярлыков (что является коротким). Если он будет коротким, это займет меньше памяти, что опять-таки много. Я нашел «quickblob», написанный на C quicblobsalgol, но я не могу запустить его из источника (но exe работает нормально), попытался проанализировать код, и у меня что-то появилось, но вся эта идея была для меня неопределенной, поэтому я попробовал также что-то вроде floodFill алгоритм и что-то вроде «структуры данных с отключенным набором»link, который удерживает капли, а это означает, что используемая память теоретически определяется количеством блоков (одиночные черные пиксели не распознаются как капли). Вот C++ код:Blobs обнаруживая алгоритм
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <math.h>
#define ROWS 4000
#define COLS 4000
#define BLOBS 1000000
using namespace std;
void floodFillAlgorithm(short(&arr)[ROWS][COLS]);
int recurciveMarkBlob(short(&arr)[ROWS][COLS], int **ptr_labels, int i, int j, int group);
int main(){
short arr[ROWS][COLS];
srand((unsigned int)time(0)); // use current time as seed for random generator
for (int i = 0; i < ROWS; i++)
{
for (int j = 0; j < COLS; j++)
{
arr[i][j] = rand() % 2;
}
}
/*for (int i = 0; i < ROWS; i++)
{
for (int j = 0; j < COLS; j++)
{
cout << arr[i][j] << '\t';
}
cout << '\n';
}*/
floodFillAlgorithm(arr);
cout << '\n';
cout << '\n';
/*for (int i = 0; i < ROWS; i++)
{
for (int j = 0; j < COLS; j++)
{
cout << arr[i][j] << '\t';
}
cout << '\n';
}*/
system("PAUSE");
return 0;}
void floodFillAlgorithm(short(&arr)[ROWS][COLS])
{
int group = 0;
int **ptr_labels;
ptr_labels = (int **)malloc(BLOBS * sizeof(int*));
if (ptr_labels == 0)
{
printf("ERROR: Out of memory\n");
}
for (int i = 0; i < BLOBS; i++)
{
ptr_labels[i] = NULL;
}
for (int i = 0; i < ROWS; i++)
{
for (int j = 0; j < COLS; j++)
{
if (arr[i][j] == 1)
{
recurciveMarkBlob(arr, ptr_labels,i, j, ++group);
arr[i][j] = 1;
}
}
}
int count = 0;
for (int i = 0; i < BLOBS; i++)
{
if (ptr_labels[i] != NULL)
{
count++;
//cout << "Label: " << i << " ; X1: " << ptr_labels[i][0] << " ; Y1: " << ptr_labels[i][1] << " ; X2: " << ptr_labels[i][2] << " ; Y2: " << ptr_labels[i][3] << " ; X3: " << ptr_labels[i][4] << " ; Y3: " << ptr_labels[i][5] << " ; POINTS: " << ptr_labels[i][6] << endl;
}
}
cout << "Count: " << count << endl;
system("PAUSE");
for (int i = 0; i < BLOBS; i++)
{
if (ptr_labels[i] != NULL)
{
free(ptr_labels[i]);
}
}
free(ptr_labels);
}
int recurciveMarkBlob(short(&arr)[ROWS][COLS], int **ptr_labels, int i, int j, int group)
{
//cout << " i : " << i << " j: " << j << endl;
if (j != 0)
{
if ((arr[i][j] == arr[i][j - 1]) && (arr[i][j - 1] == 1))
{
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j - 1;
ptr_labels[group][1] = i;
ptr_labels[group][2] = j;
ptr_labels[group][3] = i;
ptr_labels[group][4] = j;
ptr_labels[group][5] = i;
ptr_labels[group][6] = 2; // taken points (area) for current shape
}
else
{
if (ptr_labels[group][0] > j - 1)
{
ptr_labels[group][0] = j - 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i, j - 1, group);
arr[i][j] = 1;
}
}
if (j != COLS - 1)
{
if ((arr[i][j] == arr[i][j + 1]) && (arr[i][j + 1] == 1))
{
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j;
ptr_labels[group][1] = i;
ptr_labels[group][2] = j + 1;
ptr_labels[group][3] = i;
ptr_labels[group][4] = j;
ptr_labels[group][5] = i;
ptr_labels[group][6] = 2; // taken points (area) for current shape
}
else
{
if (ptr_labels[group][2] < j + 1)
{
ptr_labels[group][2] = j + 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i, j + 1, group);
arr[i][j] = 1;
}
}
if (i != 0)
{
if ((arr[i][j] == arr[i - 1][j]) && (arr[i - 1][j] == 1))
{
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j;
ptr_labels[group][1] = i - 1;
ptr_labels[group][2] = j;
ptr_labels[group][3] = i;
ptr_labels[group][4] = j;
ptr_labels[group][5] = i;
ptr_labels[group][6] = 2; // taken points (area) for current shape
}
else
{
if (ptr_labels[group][1] > i - 1)
{
ptr_labels[group][1] = i - 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i - 1, j, group);
arr[i][j] = 1;
}
}
if (i != ROWS - 1)
{
if ((arr[i][j] == arr[i + 1][j]) && (arr[i + 1][j] == 1))
{
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j;
ptr_labels[group][1] = i;
ptr_labels[group][2] = j;
ptr_labels[group][3] = i + 1;
ptr_labels[group][4] = j;
ptr_labels[group][5] = i;
ptr_labels[group][6] = 2; // taken points (area) for current shape
}
else
{
if (ptr_labels[group][3] < i + 1)
{
ptr_labels[group][3] = i + 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i + 1, j, group);
arr[i][j] = 1;
}
}
if ((i != 0) && (j != 0))
{
if ((arr[i][j] == arr[i - 1][j - 1]) && (arr[i - 1][j - 1] == 1))
{
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j - 1;
ptr_labels[group][1] = i - 1;
ptr_labels[group][2] = j;
ptr_labels[group][3] = i;
ptr_labels[group][4] = j;
ptr_labels[group][5] = i;
ptr_labels[group][6] = 2; // taken points (area) for current shape
}
else
{
if (ptr_labels[group][0] > j - 1)
{
ptr_labels[group][0] = j - 1;
}
if (ptr_labels[group][1] > i - 1)
{
ptr_labels[group][1] = i - 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i - 1, j - 1, group);
arr[i][j] = 1;
}
}
if ((i != 0) && (j != COLS - 1))
{
//cout << "i: " << i << " ; j: " << j << endl;
if ((arr[i][j] == arr[i - 1][j + 1]) && (arr[i - 1][j + 1] == 1))
{
//cout << "i: " << i << " ; j: " << j << endl;
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j;
ptr_labels[group][1] = i - 1;
ptr_labels[group][2] = j + 1;
ptr_labels[group][3] = i;
ptr_labels[group][4] = j;
ptr_labels[group][5] = i;
ptr_labels[group][6] = 2; // taken points (area) for current shape
//cout << "Label: " << group << " ; X1: " << ptr_labels[group][0] << " ; Y1: " << ptr_labels[group][1] << " ; X2: " << ptr_labels[group][2] << " ; Y2: " << ptr_labels[group][3] << endl;
}
else
{
if (ptr_labels[group][2] < j + 1)
{
ptr_labels[group][2] = j + 1;
}
if (ptr_labels[group][1] > i - 1)
{
ptr_labels[group][1] = i - 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i - 1, j + 1, group);
arr[i][j] = 1;
}
}
if ((i != ROWS - 1) && (j != 0))
{
if ((arr[i][j] == arr[i + 1][j - 1]) && (arr[i + 1][j - 1] == 1))
{
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j - 1;
ptr_labels[group][1] = i;
ptr_labels[group][2] = j;
ptr_labels[group][3] = i + 1;
ptr_labels[group][4] = j;
ptr_labels[group][5] = i;
ptr_labels[group][6] = 2; // taken points (area) for current shape
}
else
{
if (ptr_labels[group][0] > j - 1)
{
ptr_labels[group][0] = j - 1;
}
if (ptr_labels[group][3] < i + 1)
{
ptr_labels[group][3] = i + 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i + 1, j - 1, group);
arr[i][j] = 1;
}
}
if ((i != ROWS - 1) && (j != COLS - 1))
{
if ((arr[i][j] == arr[i + 1][j + 1]) && (arr[i + 1][j + 1] == 1))
{
if (ptr_labels[group] == NULL)
{
ptr_labels[group] = (int *)malloc(7 * sizeof(int*));
ptr_labels[group][0] = j;
ptr_labels[group][1] = i;
ptr_labels[group][2] = j + 1;
ptr_labels[group][3] = i + 1;
ptr_labels[group][4] = j; // x of pixel in black
ptr_labels[group][5] = i; // y of pixel in black
ptr_labels[group][6] = 2; // taken points (area) for current shape
}
else
{
if (ptr_labels[group][2] < j + 1)
{
ptr_labels[group][2] = j + 1;
}
if (ptr_labels[group][3] < i + 1)
{
ptr_labels[group][3] = i + 1;
}
ptr_labels[group][6]++;
}
arr[i][j] = 0;
recurciveMarkBlob(arr, ptr_labels, i + 1, j + 1, group);
arr[i][j] = 1;
}
}
/**/
arr[i][j] = 0;
return 0;
}
Основной вопрос, почему до конца основной функции так много оперативной памяти до сих пор используется (147 МБ). Рекурсия хвоста «recurciveMarkBlob()» использует параметры по значению i, j, group и динамическому распределению памяти, и поэтому память временно перескакивает до 600 МБ (в основном из параметров), освобождая динамически распределенную память по-прежнему занимает 148 МБ, изображение составляет 4 000 х 4 000 х 2 байта = 16 000 000 байтов = 16 МБ. Я читал о «функции, принятой в память» here, но я все еще не могу понять, почему. Если кто-то может объяснить это с помощью кода assebler, что такое happeing, и это обычное явление. Я использую Relese режимаrelese vs debug
системы ("PAUSE") в основной()
Также каждый может дать представление для быстрого и низкого алгоритма памяти с для блочного обнаружения больших двоичных изображений.
Попробуйте скомпилировать cvBlobLib используя opencv! его простой в использовании. –
Быстро ли cvBlobLib для больших изображений с разрешением 9960 x 14040 и сколько оперативной памяти это займет. Можете ли вы предоставить правильную ссылку для ее компиляции с визуальной студией? Я извиняюсь за КАПИТАЛИЗАЦИЮ, я ее отредактировал. – nicksona
Вы хотя бы реализовали полное opencv-решение и профилировали его? В вашем вопросе есть много неправильных предположений, и вы преждевременно оптимизируете ситуацию. – Miki