网格最近邻 BFS 慢

Question

我正在尝试对图像进行上采样。我用这种方式用相应的像素填充上采样版本。
伪代码： upsampled.getPixel(((int)(x * factorX), (int)(y * factorY))) = old.getPixel(x, y)
结果我得到了未完全填充的位图，我尝试用它最近的填充像素填充每个未填充的像素。
我将此方法用于 nn 搜索并为每个未填充的像素调用它。在更改其值后，我不会将未填充的像素标记为已填充，因为它可能会产生一些奇怪的图案。问题是 - 它工作但非常慢。我的 i7 9700k 上 2500 x 3000 img 的执行时间按因子 x = 1,5 和 y = 1,5 缩放大约需要 10 秒。

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});
}

bitmap.getDataIndex() 的运行时间为 O(1)。这是它的实现

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;
}

我已经花了一段时间调试它，但无法真正找到是什么让它这么慢。
理论上当按因子 x = 1,5, y = 1,5 缩放时，填充像素与未填充像素的距离不应超过 2 个像素，因此实现良好的 BFS 不会花费很长时间。

我也对位图使用这种编码，例如 3x3x3 图像

     * (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},

Answer 1

the filled pixel should be no further than 2 pixels from unfilled one, so well implemented BFS wouldn't take long.

当然，做一次不会花很长时间。但是你需要对输出图像中的几乎每个像素都这样做，并且做很多次不需要很长时间的事情仍然需要很长时间。

不用搜索设置的像素，而是使用您拥有的关于早期计算的信息直接找到您要查找的值。

例如，在您的输出图像中，设置像素为 ((int)(x * factorX), (int)(y * factorY))，整数 x 和 y。所以对于一个非集合像素(a, b)，可以通过((int)(round(a/factorX)*factorX), (int)(round(b/factorY)*factorY)).

找到最近的集合像素

但是，您最好直接以更简单的方式对图像进行上采样：不要遍历输入像素，而是遍历输出像素，然后找到相应的输入像素。

网格最近邻 BFS 慢

Grid nearest neighbour BFS slow

c++

algorithm

grid

image-processing

breadth-first-search