Newb - 8 months ago 78

C++ Question

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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**