| 73 | |
| 74 | template<typename T> |
| 75 | void regions(Param<T> out, CParam<char> in, af_connectivity connectivity) { |
| 76 | const af::dim4 inDims = in.dims(); |
| 77 | const char* inPtr = in.get(); |
| 78 | T* outPtr = out.get(); |
| 79 | |
| 80 | // Map labels |
| 81 | typedef typename std::unique_ptr<LabelNode<T>> UnqLabelPtr; |
| 82 | typedef typename std::map<T, UnqLabelPtr> LabelMap; |
| 83 | typedef typename LabelMap::iterator LabelMapIterator; |
| 84 | |
| 85 | LabelMap lmap; |
| 86 | |
| 87 | // Initial label |
| 88 | T label = (T)1; |
| 89 | |
| 90 | for (int j = 0; j < (int)inDims[1]; j++) { |
| 91 | for (int i = 0; i < (int)inDims[0]; i++) { |
| 92 | int idx = j * inDims[0] + i; |
| 93 | if (inPtr[idx] != 0) { |
| 94 | std::vector<T> l; |
| 95 | |
| 96 | // Test neighbors |
| 97 | if (i > 0 && outPtr[j * (int)inDims[0] + i - 1] > 0) |
| 98 | l.push_back(outPtr[j * inDims[0] + i - 1]); |
| 99 | if (j > 0 && outPtr[(j - 1) * (int)inDims[0] + i] > 0) |
| 100 | l.push_back(outPtr[(j - 1) * inDims[0] + i]); |
| 101 | if (connectivity == AF_CONNECTIVITY_8 && i > 0 && j > 0 && |
| 102 | outPtr[(j - 1) * inDims[0] + i - 1] > 0) |
| 103 | l.push_back(outPtr[(j - 1) * inDims[0] + i - 1]); |
| 104 | if (connectivity == AF_CONNECTIVITY_8 && |
| 105 | i < (int)inDims[0] - 1 && j > 0 && |
| 106 | outPtr[(j - 1) * inDims[0] + i + 1] != 0) |
| 107 | l.push_back(outPtr[(j - 1) * inDims[0] + i + 1]); |
| 108 | |
| 109 | if (!l.empty()) { |
| 110 | T minl = l[0]; |
| 111 | for (size_t k = 0; k < l.size(); k++) { |
| 112 | minl = std::min(l[k], minl); |
| 113 | LabelMapIterator currentMap = lmap.find(l[k]); |
| 114 | LabelNode<T>* node = currentMap->second.get(); |
| 115 | // Group labels of the same region under a disjoint set |
| 116 | for (size_t m = k + 1; m < l.size(); m++) |
| 117 | setUnion(node, lmap.find(l[m])->second.get()); |
| 118 | } |
| 119 | // Set label to smallest neighbor label |
| 120 | outPtr[idx] = minl; |
| 121 | } else { |
| 122 | // Insert new label in map |
| 123 | lmap.insert(std::make_pair( |
| 124 | label, UnqLabelPtr(new LabelNode<T>(label)))); |
| 125 | outPtr[idx] = label++; |
| 126 | } |
| 127 | } |
| 128 | } |
| 129 | } |
| 130 | |
| 131 | std::set<T> removed; |
| 132 | |