Переполнение стека в глубине первого поиска

Я пишу маркировку компонентов, связанных с DFS, основная идея очень проста, просто рекурсивно применять DFS к ЧЕТЫРЕМ соседям (влево, вправо, вверх, вниз).

Проблема в том, что когда подключенная область слишком велика, скажем, 100 * 100 пикселей, она получает ошибку во время выполнения,

0xC00000FD: Stack overflow (:  0x00000001, 0x001D2EB4)

Я думаю, что это потому, что это идет слишком глубоко. Есть ли оптимизация или решение для этого?

Вот код:

void DFS_Traversal(cv::Mat &InputMat, cv::Mat &LabelMat, cv::Point2i cur_SP, int Thresh, int cur_Label){

if (cur_SP.y > 2 && cur_SP.y < (InputMat.rows - 2) && cur_SP.x > 2 && cur_SP.x < (InputMat.cols - 2)){
uchar* pre_Input_rowPtr = InputMat.ptr<uchar>(cur_SP.y - 1);
uchar* cur_Input_rowPtr = InputMat.ptr<uchar>(cur_SP.y);
uchar* next_Input_rowPtr = InputMat.ptr<uchar>(cur_SP.y + 1);
uchar* pre_Label_rowPtr = LabelMat.ptr<uchar>(cur_SP.y - 1);
uchar* cur_Label_rowPtr = LabelMat.ptr<uchar>(cur_SP.y);
uchar* next_Label_rowPtr = LabelMat.ptr<uchar>(cur_SP.y + 1);

//cur_Label_rowPtr[cur_SP.x] = cur_Label;

//Left Point
if ( cur_Label_rowPtr[cur_SP.x - 1] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - cur_Input_rowPtr[cur_SP.x - 1]) < Thresh){
cv::Point2i left_Point(cur_SP.x - 1, cur_SP.y);

cur_Label_rowPtr[cur_SP.x - 1] = cur_Label;
DFS_Traversal(InputMat, LabelMat, left_Point, Thresh, cur_Label);
}
//Right Point
if ( cur_Label_rowPtr[cur_SP.x + 1] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - cur_Input_rowPtr[cur_SP.x + 1]) < Thresh){
cv::Point2i right_Point(cur_SP.x + 1, cur_SP.y);

cur_Label_rowPtr[cur_SP.x + 1] = cur_Label;
DFS_Traversal(InputMat, LabelMat, right_Point, Thresh, cur_Label);
}
//Up Point
if ( pre_Label_rowPtr[cur_SP.x] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - pre_Input_rowPtr[cur_SP.x]) < Thresh){
cv::Point2i up_Point(cur_SP.x, cur_SP.y - 1);

pre_Label_rowPtr[cur_SP.x] = cur_Label;
DFS_Traversal(InputMat, LabelMat, up_Point, Thresh, cur_Label);
}
//Down Point
if ( next_Label_rowPtr[cur_SP.x] == 0 && std::abs(cur_Input_rowPtr[cur_SP.x] - next_Input_rowPtr[cur_SP.x]) < Thresh){
cv::Point2i down_Point(cur_SP.x, cur_SP.y + 1);

next_Label_rowPtr[cur_SP.x] = cur_Label;
DFS_Traversal(InputMat, LabelMat, down_Point, Thresh, cur_Label);
}

}
return;

}

Работая на ноутбуке с 8G RAM, максимальная площадь без переполнения составляет 72 * 72, что составляет около 5000 уровней рекурсий. Как я могу сделать лучше с DFS?

1

Решение

Замените рекурсию циклом и используйте явный стек (подойдет любой список).

Стек будет имитировать стек вызовов, но не будет так сильно ограничен.

Смотрите итеративную реализацию от Википедия:

iterativeInorder(node)
s ← empty stack
while (not s.isEmpty() or node ≠ null)
if (node ≠ null)
s.push(node)
node ← node.left
else
node ← s.pop()
visit(node)
node ← node.right
1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector