I'm writing a DFS connected component labelling, basic idea is really simple, just applying DFS to FOUR neighbours(left,right,up,down) recursively.
The problem is that when the connected area is too large, say, 100 * 100 pixels, it gets a runtime error,
0xC00000FD: Stack overflow (: 0x00000001, 0x001D2EB4)
I think it's because it goes too deep. Is there any optimization or solution to this?
Here is the code:
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;
}
Running on a laptop with 8G RAM, the max area without over flow is 72 * 72, which is near 5000 levels of recursions. How can I do better with DFS?
Replace the recursion with loop and use explicit stack (any list will do).
The stack will simulate call stack but will not be so tightly bounded.
See the iterative implementation from Wikipedia:
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
User contributions licensed under CC BY-SA 3.0