调整大小 quad_tree

Question

将矩阵的大小更改为 2^m × 2^m 。这是这样做的如下。如果m≥n，用2^m-n×2^m-n矩阵替换原图的每个像素点所有值都等于原始像素。如果m < n，将矩阵分成2^m × 2^m 子矩阵，每个大小为 2^n-m × 2^n-m ，并用一个像素替换每个子矩阵值在子矩阵中出现的频率更高。如果相等，选1。

How to resize region quadtree of height n with height m. QUADTREE is defined as follows:
An image is considered to be a 2n × 2n matrix, each of whose entries is 0 (white) or 1 (black). Each entry is called a pixel. Instead of storing the whole matrix, different data structures are used to reduce the size. The quad-tree is one such. A quad-tree is a rooted tree in which every node has either 0 or 4 children. Every node in the tree corresponds to some sub-matrix of the whole matrix, with size 2i × 2i for some 0 ≤ i ≤ n. The root node is the entire matrix. If all entries in a sub-matrix corresponding to a node are equal, the node is a leaf node, and it stores the value of the pixels in the sub-matrix. If there are distinct entries in the sub-matrix, divide it into 4 sub-matrices of size 2i-1 × 2i-1 , called top-left, top-right, bottom-right, bottom-left, and recursively construct the sub-trees corresponding to the 4 sub-matrices.

Answer 1

我实现了两个解决方案，第一个是四叉树的情况，第二个是二维向量（数组）的情况（我的第二个解决方案实际上是我的第一个，我错误地实现了它，忘了注意到我们需要特别的四叉树结构，但是如果它对某人有帮助，我仍然会留下第二个。

第一个解决方案 使用四叉树结构。

四叉树实现为四叉树模板结构，可以存储任何数据类型T，默认情况下它存储二进制图像数据为size_t类型（0/1，black/white） .有函数 CreateQT 用于创建和填充给定高度的四叉树，TraverseQT 一个遍历所有树节点并将给定回调应用于每个叶节点的函数，ResizeQT 实际解决给定任务- 将四叉树的大小从当前高度 n 调整为新高度 m，DumpQT 函数将四叉树转储到字符串，以便将其输出到控制台。

main() 函数只是通过 rand() % 2 调用用随机二进制数据填充它来创建高度为 n 和 CreateQT 的输入树，然后它输出原始图像到控制台通过 DumpQT 调用，然后通过调用 ResizeQT 从高度 n 调整到高度 m，并使用 DumpQT.[=43= 将最终调整大小的图像输出到控制台]

Try it online!

#include <cstdlib>
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <array>
#include <memory>
#include <string>
#include <functional>
using namespace std;

template <typename T>
struct QuadTree {
    typedef T data_t;
    size_t height() const {
        return st[0] ? st[0]->height() + 1 : 0;
    }
    
    T data = T();
    // Sub-trees, in order Top-Left, Top-Right, Bottom-Left, Bottom-Right.
    array< shared_ptr<QuadTree>, 4 > st = {};
};

template <typename T>
static shared_ptr< QuadTree<T> > CreateQT(size_t const height, function<T()> const & filler) {
    shared_ptr< QuadTree<T> > r(new QuadTree<T>());
    if (height <= 0)
        r->data = filler();
    else
        for (size_t i = 0; i < r->st.size(); ++i)
            r->st[i] = CreateQT(height - 1, filler);
    return r;
}

template <typename T>
static void TraverseQT(QuadTree<T> const & qt, function<void(T const &)> const & visitor) {
    if (qt.height() <= 0)
        visitor(qt.data);
    else
        for (size_t i = 0; i < qt.st.size(); ++i)
            TraverseQT<T>(*qt.st[i], visitor);
}

template <typename T>
static void ResizeQT(QuadTree<T> & qt, size_t const m) {
    size_t const n = qt.height();
    if (n == m)
        return;
    if (n > 0 && m > 0) {
        for (size_t i = 0; i < qt.st.size(); ++i)
            ResizeQT(*qt.st[i], m - 1);
    } else if (m > 0) {
        qt.st = CreateQT<T>(m, [&](){ return qt.data; })->st;
        qt.data = T();
    } else if (n > 0) {
        map<T, size_t> cnt;
        TraverseQT<T>(qt, [&](T const & v){ ++cnt[v]; });
        // Find max
        pair<T, size_t> maxv = {{}, 0};
        for (auto const & p: cnt)
            if (p.second > maxv.second)
                maxv = p;
        qt.data = maxv.first;
        for (size_t i = 0; i < qt.st.size(); ++i)
            qt.st[i].reset();
    }
    return;
}

string VecToStr(vector<string> const & a) {
    string r;
    for (size_t i = 0; i < a.size(); ++i) {
        r += a[i];
        if (i < a.size() - 1)
            r += "\n";
    }
    return r;
}

template <typename T>
static vector<string> DumpQT(QuadTree<T> const & qt) {
    if (qt.height() <= 0)
        return {to_string(qt.data)};
    auto JoinH = [](vector<string> const & a, vector<string> const & b) {
        vector<string> r;
        for (size_t i = 0; i < min(a.size(), b.size()); ++i)
            r.push_back(a[i] + " " + b[i]);
        return r;
    };
    auto JoinV = [](vector<string> const & a, vector<string> const & b) {
        vector<string> r = a;
        r.insert(r.end(), b.begin(), b.end());
        return r;
    };
    return JoinV(
        JoinH(DumpQT(*qt.st[0]), DumpQT(*qt.st[1])),
        JoinH(DumpQT(*qt.st[2]), DumpQT(*qt.st[3]))
    );
}

int main() {
    try {
        vector< pair<size_t, size_t> > const nm = {{2, 3}, {3, 3}, {4, 3}};
        srand(0);
        typedef QuadTree<size_t> ImgQT;
        // Iterate through all "nm" tests
        for (size_t t = 0; t < nm.size(); ++t) {
            size_t n = nm[t].first, m = nm[t].second;
            cout << "n = " << n << ", m = " << m << endl;
            // Create/Fill input img of size 2^n with random values.
            ImgQT img = *CreateQT<ImgQT::data_t>(n, []()->size_t{ return rand() % 2; });
            cout << "Original:" << endl << VecToStr(DumpQT(img)) << endl;
            // Solve task, resize to 2^m.
            ResizeQT(img, m);
            cout << "Resized:" << endl << VecToStr(DumpQT(img)) << endl;
        }
        return 0;
    } catch (exception const & ex) {
        cout << "Exception: " << ex.what() << endl;
        return -1;
    } catch (...) {
        cout << "Unknown Exception!" << endl;
        return -1;
    }
}

控制台输出：

n = 2, m = 3
Original:
0 1 1 1
0 1 1 1
0 0 0 1
1 0 1 1
Resized:
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 1
n = 3, m = 3
Original:
1 1 0 1 0 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 1 0 1 0
1 0 0 0 1 1 0 1
0 0 1 1 0 0 0 0
1 0 0 1 1 0 1 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 1 0
Resized:
1 1 0 1 0 1 1 1
1 0 1 0 1 1 0 1
1 1 1 0 1 0 1 0
1 0 0 0 1 1 0 1
0 0 1 1 0 0 0 0
1 0 0 1 1 0 1 1
1 0 0 0 1 1 1 1
1 0 0 0 0 0 1 0
n = 4, m = 3
Original:
1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0
1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1
1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1
1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1
1 1 0 0 1 0 0 1 1 0 1 1 0 0 1 1
0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1
1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1
0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0
1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1
0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0
1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1
1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1
0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1
Resized:
0 0 0 0 0 0 0 0
1 0 1 0 1 1 0 1
1 0 1 0 0 1 0 1
0 0 0 0 0 1 0 0
1 1 0 1 0 0 0 1
0 1 0 0 1 0 0 0
1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1

第二种解决方案 使用二维向量。

在代码的开头，使用您想要的 n 和 m 值向 nm 数组添加额外的测试。输入图像 pre-filled 具有小的随机整数值，如果需要，您可以更改它以读取一些输入。

每个图像像素表示为一个 fixed-size 数组，其大小等于通道数（例如，1 代表灰色，3 代表 RGB）。在下一个代码中，为简单起见，每个像素都有 1 个通道，只有一个整数。通道数由 nchans 常量配置，将 nchans 更改为例如3 用于测试 RGB 图像。

每个像素都填充有随机整数，随机整数的范围由代码中的下一个表达式控制rand() % (t <= 1 ? 10 : 3)，修改模数后的值%以更改可能值的范围大小。

Try it online!

#include <cstdlib>
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <algorithm>
#include <array>
using namespace std;

int main() {
    try {
        vector< pair<size_t, size_t> > const nm = {{2, 3}, {3, 3}, {4, 3}};
        size_t const nchans = 1; // Number of channels (colors), e.g. 1 for Gray and 3 for RGB.
        typedef array<size_t, nchans> PixelT;
        srand(0);
        // Iterate through all "nm" tests
        for (size_t t = 0; t < nm.size(); ++t) {
            vector< vector<PixelT> > img;
            size_t n = nm[t].first, m = nm[t].second;
            cout << "n = " << n << ", m = " << m << endl;
            cout << "Original:" << endl;
            // Create/Fill input img of size 2^n with random values.
            // (1 << n) is same as 2^n (power of 2).
            for (size_t i = 0; i < (1 << n); ++i) {
                img.resize(img.size() + 1);
                for (size_t j = 0; j < (1 << n); ++j) {
                    PixelT p = {};
                    for (size_t k = 0; k < p.size(); ++k) {
                        p[k] = rand() % (t <= 1 ? 10 : 3);
                        cout << p[k];
                        if (k < p.size() - 1)
                            cout << ",";
                    }
                    cout << " ";
                    img[i].push_back(p);
                }
                cout << endl;
            }
            // Solve task, resize to 2^m.
            vector< vector<PixelT> > oimg;
            if (n <= m) {
                for (size_t i = 0; i < (1 << m); ++i) {
                    oimg.resize(oimg.size() + 1);
                    for (size_t j = 0; j < (1 << m); ++j) {
                        oimg[i].push_back(
                            img[i >> (m - n)][j >> (m - n)]
                        );
                    }
                }
            } else {
                for (size_t i = 0; i < (1 << m); ++i) {
                    oimg.resize(oimg.size() + 1);
                    for (size_t j = 0; j < (1 << m); ++j) {
                        // Count number of occurances
                        map<PixelT, size_t> cnt;
                        for (size_t k = (i << (n - m)); k < ((i << (n - m)) + (1 << (n - m))); ++k)
                            for (size_t l = (j << (n - m)); l < ((j << (n - m)) + (1 << (n - m))); ++l)
                                ++cnt[img[k][l]];
                        // Find max
                        pair<PixelT, size_t> maxv = {{}, 0};
                        for (auto const & p: cnt)
                            if (p.second > maxv.second)
                                maxv = p;
                        oimg[i].push_back(maxv.first);
                    }
                }
            }
            // Output results
            cout << "Resized:" << endl;
            for (size_t i = 0; i < oimg.size(); ++i) {
                for (size_t j = 0; j < oimg[i].size(); ++j) {
                    auto const & p = oimg[i][j];
                    for (size_t k = 0; k < p.size(); ++k) {
                        cout << p[k];
                        if (k < p.size() - 1)
                            cout << ",";
                    }
                    cout << " ";
                }
                cout << endl;
            }
        }
        return 0;
    } catch (exception const & ex) {
        cout << "Exception: " << ex.what() << endl;
        return -1;
    } catch (...) {
        cout << "Unknown Exception!" << endl;
        return -1;
    }
}

灰度图像 (nchans = 1) 的示例输出：

n = 2, m = 3
Original:
8 9 8 7 
5 7 5 5 
0 2 3 0 
2 1 7 1 
Resized:
8 8 9 9 8 8 7 7 
8 8 9 9 8 8 7 7 
5 5 7 7 5 5 5 5 
5 5 7 7 5 5 5 5 
0 0 2 2 3 3 0 0 
0 0 2 2 3 3 0 0 
2 2 1 1 7 7 1 1 
2 2 1 1 7 7 1 1 
n = 3, m = 3
Original:
5 5 7 0 6 1 5 6 
7 3 1 0 5 8 6 0 
0 7 7 7 1 7 6 7 
3 8 3 7 7 4 2 1 
8 6 9 4 9 5 8 9 
9 6 1 4 4 6 8 2 
2 4 7 6 8 2 7 3 
3 3 0 2 7 5 1 4 
Resized:
5 5 7 0 6 1 5 6 
7 3 1 0 5 8 6 0 
0 7 7 7 1 7 6 7 
3 8 3 7 7 4 2 1 
8 6 9 4 9 5 8 9 
9 6 1 4 4 6 8 2 
2 4 7 6 8 2 7 3 
3 3 0 2 7 5 1 4 
n = 4, m = 3
Original:
2 2 2 2 2 1 2 2 2 0 1 0 0 0 0 2 
0 0 2 2 2 2 1 2 1 2 1 2 0 1 1 2 
1 0 2 0 1 0 2 1 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 1 1 1 1 1 1 0 2 0 1 
2 1 0 0 2 2 1 1 0 1 1 2 1 1 2 0 
1 1 0 0 1 1 1 2 2 1 2 2 0 2 1 2 
1 0 0 0 1 2 1 0 2 2 0 0 0 2 1 2 
2 1 0 0 1 2 1 0 1 0 2 2 2 0 2 2 
0 1 1 2 2 1 0 2 1 0 1 2 0 2 2 1 
0 0 0 2 0 1 2 2 2 1 1 2 1 1 1 2 
1 1 1 0 2 2 2 1 1 2 1 0 0 0 0 2 
1 0 0 0 2 2 1 1 2 2 0 0 1 1 1 2 
1 2 2 1 1 1 2 2 2 2 0 0 2 2 2 2 
1 2 1 2 2 2 2 2 0 0 2 2 0 0 0 2 
0 0 0 0 2 0 0 1 1 2 2 0 1 1 0 0 
0 0 1 1 0 0 1 1 0 0 1 2 1 2 1 0 
Resized:
0 2 2 2 2 1 0 2 
0 0 0 1 1 1 1 1 
1 0 1 1 1 2 1 2 
1 0 1 0 2 0 0 2 
0 2 1 2 1 1 1 1 
1 0 2 1 2 0 0 2 
1 1 1 2 0 0 0 2 
0 0 0 1 0 2 1 0

RGB 图像 (nchans = 3) 的示例输出：

n = 2, m = 3
Original:
8,9,8 7,5,7 5,5,0 2,3,0 
2,1,7 1,5,5 7,0,6 1,5,6 
7,3,1 0,5,8 6,0,0 7,7,7 
1,7,6 7,3,8 3,7,7 4,2,1 
Resized:
8,9,8 8,9,8 7,5,7 7,5,7 5,5,0 5,5,0 2,3,0 2,3,0 
8,9,8 8,9,8 7,5,7 7,5,7 5,5,0 5,5,0 2,3,0 2,3,0 
2,1,7 2,1,7 1,5,5 1,5,5 7,0,6 7,0,6 1,5,6 1,5,6 
2,1,7 2,1,7 1,5,5 1,5,5 7,0,6 7,0,6 1,5,6 1,5,6 
7,3,1 7,3,1 0,5,8 0,5,8 6,0,0 6,0,0 7,7,7 7,7,7 
7,3,1 7,3,1 0,5,8 0,5,8 6,0,0 6,0,0 7,7,7 7,7,7 
1,7,6 1,7,6 7,3,8 7,3,8 3,7,7 3,7,7 4,2,1 4,2,1 
1,7,6 1,7,6 7,3,8 7,3,8 3,7,7 3,7,7 4,2,1 4,2,1 
n = 3, m = 3
Original:
8,6,9 4,9,5 8,9,9 6,1,4 4,6,8 2,2,4 7,6,8 2,7,3 
3,3,0 2,7,5 1,4,3 2,9,4 9,6,4 7,3,5 3,3,0 4,3,1 
4,5,9 0,7,6 9,6,9 7,0,3 2,4,1 2,5,1 9,7,0 0,4,8 
4,7,6 1,8,2 0,4,1 5,7,0 4,2,6 7,3,4 8,4,4 1,7,6 
6,3,0 2,7,0 7,8,3 3,9,3 1,4,1 3,2,1 4,0,9 4,1,2 
0,2,8 6,1,5 6,9,8 5,7,0 4,3,5 1,4,7 6,6,1 7,4,1 
3,9,4 6,4,9 5,7,0 2,5,0 6,0,2 3,5,7 8,7,5 1,0,7 
3,1,6 2,7,2 1,3,2 5,5,6 5,9,7 3,3,7 2,2,1 4,6,5 
Resized:
8,6,9 4,9,5 8,9,9 6,1,4 4,6,8 2,2,4 7,6,8 2,7,3 
3,3,0 2,7,5 1,4,3 2,9,4 9,6,4 7,3,5 3,3,0 4,3,1 
4,5,9 0,7,6 9,6,9 7,0,3 2,4,1 2,5,1 9,7,0 0,4,8 
4,7,6 1,8,2 0,4,1 5,7,0 4,2,6 7,3,4 8,4,4 1,7,6 
6,3,0 2,7,0 7,8,3 3,9,3 1,4,1 3,2,1 4,0,9 4,1,2 
0,2,8 6,1,5 6,9,8 5,7,0 4,3,5 1,4,7 6,6,1 7,4,1 
3,9,4 6,4,9 5,7,0 2,5,0 6,0,2 3,5,7 8,7,5 1,0,7 
3,1,6 2,7,2 1,3,2 5,5,6 5,9,7 3,3,7 2,2,1 4,6,5 
n = 4, m = 3
Original:
1,1,0 1,0,0 1,0,1 1,0,0 0,1,0 1,0,1 0,1,0 0,0,1 0,1,1 1,1,0 1,0,0 0,1,1 1,1,0 0,1,0 1,1,0 0,0,0 
0,1,0 1,1,1 1,0,1 0,1,0 0,1,0 0,0,0 1,0,0 0,0,1 1,1,0 1,0,1 0,1,0 0,1,1 0,0,1 1,1,0 0,0,1 1,0,1 
0,0,1 1,0,1 0,1,0 1,0,0 0,1,0 0,1,0 1,0,1 1,1,0 0,0,1 1,0,0 0,1,0 0,1,1 1,0,1 1,0,0 0,1,0 1,1,1 
1,1,1 1,1,1 1,1,1 0,0,1 1,1,1 0,0,0 1,0,0 0,0,0 1,1,1 1,1,0 1,1,0 1,1,0 0,1,0 1,0,0 0,1,1 0,1,0 
0,1,1 0,0,0 0,1,1 0,0,1 1,1,0 1,0,1 0,1,0 1,0,1 1,1,0 0,0,1 1,1,0 1,0,0 1,0,0 0,0,1 1,1,1 1,0,0 
1,1,1 0,1,1 1,1,0 0,0,1 1,0,1 1,0,0 0,1,1 0,1,1 0,1,1 1,1,1 1,1,1 1,1,1 1,1,0 0,1,1 0,0,0 0,1,0 
0,1,0 1,0,0 1,1,1 0,1,1 0,0,0 0,0,0 1,0,0 1,0,0 1,0,1 1,0,1 0,0,1 1,0,0 0,1,1 1,1,0 0,1,0 1,1,1 
0,1,0 1,0,0 1,0,0 0,1,0 1,1,1 1,0,0 1,1,0 0,0,1 1,1,1 1,1,0 1,1,0 0,1,0 0,1,0 1,1,1 1,1,1 1,0,1 
1,0,0 0,0,1 1,0,1 0,1,1 1,1,1 1,0,1 0,1,0 0,1,1 0,1,0 0,1,0 1,1,1 1,0,1 1,0,1 1,0,0 1,1,0 0,1,1 
0,1,0 1,0,1 1,1,0 0,1,1 0,0,1 0,0,1 0,0,1 1,1,1 1,1,1 1,1,0 1,0,0 0,1,1 0,0,0 0,1,1 1,0,0 1,0,1 
0,1,1 0,1,0 0,0,0 1,0,1 1,0,1 1,0,0 1,0,0 0,1,1 1,1,1 1,0,0 1,0,1 0,0,0 1,0,0 0,1,1 0,1,0 0,1,0 
0,1,0 0,0,0 1,0,1 0,0,1 0,1,0 1,0,0 1,0,1 0,0,0 1,1,1 1,1,0 0,0,0 0,0,1 0,0,1 1,1,0 1,1,1 0,1,1 
1,1,1 1,0,0 0,1,0 1,0,0 0,0,1 0,1,0 0,0,0 0,0,1 0,1,0 0,1,0 1,1,1 0,1,0 0,0,0 0,1,0 0,1,1 1,0,0 
1,1,1 0,0,0 0,1,0 0,0,0 0,1,1 1,0,1 0,1,0 1,1,1 0,0,1 0,0,0 0,0,0 1,0,1 1,1,0 1,0,1 1,1,0 1,1,0 
1,0,1 1,1,1 0,1,0 1,1,0 1,0,1 1,1,0 1,0,1 1,0,0 0,0,1 0,0,1 1,1,0 0,1,0 1,0,1 0,1,0 1,0,0 0,1,0 
0,1,1 0,0,0 0,1,0 0,0,0 0,1,0 0,1,1 1,1,0 1,0,1 1,1,1 0,0,1 0,0,1 1,1,1 0,1,1 0,0,0 0,0,0 0,0,0 
Resized:
0,1,0 1,0,1 0,1,0 0,0,1 1,1,0 0,1,1 1,1,0 0,0,0 
1,1,1 0,0,1 0,1,0 0,0,0 0,0,1 1,1,0 1,0,0 0,1,0 
0,1,1 0,0,1 1,0,1 0,1,1 0,0,1 1,1,1 0,0,1 0,0,0 
0,1,0 0,1,0 0,0,0 1,0,0 1,0,1 0,0,1 0,1,0 1,1,1 
0,0,1 0,1,1 0,0,1 0,0,1 0,1,0 0,1,1 0,0,0 0,1,1 
0,1,0 1,0,1 1,0,0 0,0,0 1,1,1 0,0,0 0,0,1 0,1,0 
1,1,1 0,1,0 0,0,1 0,0,0 0,1,0 0,0,0 0,0,0 1,1,0 
0,0,0 0,1,0 0,1,0 1,0,1 0,0,1 0,0,1 0,0,0 0,0,0

调整大小 quad_tree

Resize quad_tree

c++

data-structures

quadtree