Newb Newb - 1 year ago 126
C++ Question

Stack Overflow in Depth First Search

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?

Answer Source

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 
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download