Change the size of the matrix to 2m × 2m . This is done as follows. If m ≥ n, replace each pixel of the original image by a 2m-n × 2m-n matrix with all values equal to the original pixel. If m < n, divide the matrix into 2m × 2m submatrices, each of size 2n-m × 2n-m , and replace each submatrix by a pixel whose value occurs more often in the submatrix. If equal, choose 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.
I implemented two solutions, first is for QuadTree case, second for 2D vector (array) case (my second solution was actually my first, I implemented it by mistake, forgot to notice that we need specifically QuadTree structure, but still I leave second one if it will help someone).
First solution using QuadTree structure.
Quad tree is implemented as QuadTree template structure that can store any data type T, by default it stores binary image data as size_t type (0/1, black/white). There are functions CreateQT for creating and filling quad tree of given height, TraverseQT a function that traverses all tree nodes and applies given callback to each of leaf nodes, ResizeQT that actually solves given task - resizes quad tree from current height n to new height m, DumpQT function that dumps quad tree to string for possibility of outputting it to console.
main() function just creates input tree of height n with CreateQT by filling it with random binary data by rand() % 2 calls, then it outputs original image to console by DumpQT call, then resizes from height n to height m by calling ResizeQT, and outputs final resized image to console using DumpQT.
#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;
}
}
Console output:
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
Second solution using 2D vector.
In the beginning of code add extra tests to nm array with your desired n and m values. Input image is pre-filled with small random integer values, you may change this to read some input if needed.
Each image pixel is represented as a fixed-size array of size equal to number of channels (e.g. 1 for Gray and 3 for RGB). In next code each pixel has 1 channel, just one integer, for simplicity. Number of channels is configured by nchans constant, change nchans to e.g. 3 for testing of RGB image.
Each pixel is filled with random integers, range for random integers is controlled by next expression inside code rand() % (t <= 1 ? 10 : 3), modify value after modulus % to change range size of possible values.
#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;
}
}
Example output for Gray image (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
Example output for RGB image (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