Im trying to upsample my image. I fill the upsampled version with corresponding pixels in this way.

pseudocode:

`upsampled.getPixel(((int)(x * factorX), (int)(y * factorY))) = old.getPixel(x, y)`

as a result i end up with the bitmap that is not completely filled and I try to fill each not filled pixel with it’s nearest filled neighbor.

I use this method for nn search and call it for each unfilled pixel. I do not flag unfilled pixel as filled after changing its value as it may create some weird patterns. The problem is that – it works but very slow. Execution time on my i7 9700k for 2500 x 3000 img scaled by factor x = 1,5 and y = 1,5 takes about 10 seconds.

```
template<typename T>
std::pair<int, int> cn::Utils::nearestNeighbour(const Bitmap <T> &bitmap, const std::pair<int, int> &point, int channel, const bool *filledArr) {
auto belongs = [](const cn::Bitmap<T> &bitmap, const std::pair<int, int> &point){
return point.first >= 0 && point.first < bitmap.w && point.second >= 0 && point.second < bitmap.h;
};
if(!(belongs(bitmap, point))){
throw std::out_of_range("This point does not belong to bitmap!");
}
auto hash = [](std::pair<int, int> const &pair){
std::size_t h1 = std::hash<int>()(pair.first);
std::size_t h2 = std::hash<int>()(pair.second);
return h1 ^ h2;
};
//from where, point
std::queue<std::pair<int, int>> queue;
queue.push(point);
std::unordered_set<std::pair<int, int>, decltype(hash)> visited(10, hash);
while (!queue.empty()){
auto p = queue.front();
queue.pop();
visited.insert(p);
if(belongs(bitmap, p)){
if(filledArr[bitmap.getDataIndex(p.first, p.second, channel)]){
return {p.first, p.second};
}
std::vector<std::pair<int,int>> neighbors(4);
neighbors[0] = {p.first - 1, p.second};
neighbors[1] = {p.first + 1, p.second};
neighbors[2] = {p.first, p.second - 1};
neighbors[3] = {p.first, p.second + 1};
for(auto n : neighbors) {
if (visited.find(n) == visited.end()) {
queue.push(n);
}
}
}
}
return std::pair<int, int>({-1, -1});
}
```

the bitmap.getDataIndex() works in O(1) time. Here’s its implementation

```
template<typename T>
int cn::Bitmap<T>::getDataIndex(int col, int row, int depth) const{
if(col >= this->w or col < 0 or row >= this->h or row < 0 or depth >= this->d or depth < 0){
throw std::invalid_argument("cell does not belong to bitmap!");
}
return depth * w * h + row * w + col;
}
```

I have spent a while on debugging this but could not really find what makes it so slow.

Theoretically when scaling by factor x = 1,5, y = 1,5, the filled pixel should be no further than 2 pixels from unfilled one, so well implemented BFS wouldn’t take long.

Also i use such encoding for bitmap, example for 3x3x3 image

```
* (each row and channel is in ascending order)
* {00, 01, 02}, | {09, 10, 11}, | {18, 19, 20},
c0 {03, 04, 05}, c1{12, 13, 14}, c2{21, 22, 23},
* {06, 07, 08}, | {15, 16, 17}, | {24, 25, 26},
```

Source: Windows Questions C++