Convert 8x8 Matrix into flatten vector using zigzag scan

Question

So I need to convert an opencv mat that is 8x8 into a flattened vector using a zig zag scan as shown in this image.

I understand what it is supposed to be doing and I think I have gotten the first half implementation down but I am receiving an error when I am trying to set the value to the vector.

std::vector<float> *ZigZagScanner::scan(cv::Mat &input) {
std::vector<float> *output = new std::vector<float>();
// TODO Traverse the input in a zigzag scan, and store the result in output
//set row and column start values to zero, set increment flag to false

 // TODO Traverse the input in a zigzag scan, and store the result in output
//set row and column start values to zero, set increment flag to false
int row, col = 0;
bool  increment = false;

//create nest for loops to traverse through the first half of the matrix in a zig zag fashion
for(int y = 1; y <= 8; ++y){
    for(int x = 0; x < y; ++x){
        //add the current row and column to the flatten vector

        //ERROR HERE
        cv::Rect rect = cv::Rect(y,x, 8, 8);
        output->push_back(new cv::Mat(input, rect));


        if(x + 1 == y){
            break;
        }

        //when the increment flag is true increase the row and decrease the column
        if(increment == true){
            ++row, --col;
        }
        else{
            --row, ++col;
        }
    }
    //if y gets to out of bounds break the loop
  if(y == 8){
    break;
  }
  //if the increment flag is true then increment the row and switch the flag, otherwise increment the column and swap the flag
  if(increment == true){
      ++row, increment = false;
  }
  else{
      ++col, increment = true;
  }
}

//update the columns and rows to the correct values to go through the second half of the matrix
if(row == 0){
    if(col == 7){
        ++row;
    }
    else{
        ++col;
        increment = true;
    }
}
else{
    if(row == 7){
        ++col;
    }
    else{
        ++row;
        increment = false;
    }
}

for(int k, j = 7; j > 0; --j){
    if(j > 8){
        k = 8;
    }
    else{
        k = j;
    }

    for(int i = 0; i < k; i++){

        //ERROR HERE AS WELL
        cv::Rect rect = cv::Rect(y,x, 8, 8);
        output->push_back(new cv::Mat(input, rect));
    }
}

At this point, I am just struggling to figure this portion out and any advice would mean a ton! return output; }

Answer 1

Iterate over diagonals, then over diagonal elements. All you need is simple math to calculate element indices:

const int n = 8;
for (int diag = 0; diag < 2 * n - 1; ++diag) {
    const auto i_min = std::max(0, diag - n + 1);
    const auto i_max = i_min + std::min(diag, 2 * (n - 1) - diag);
    for (auto i = i_min; i <= i_max; ++i) {
        const auto row = diag % 2 ? i : (diag - i);
        const auto col = diag % 2 ? (diag - i) : i;

        // (row, col) is current element
    }
}

You can force the compiler to unroll all these loops:

namespace impl {
template<int offset, int... is>
constexpr auto offset_sequence(std::integer_sequence<int, is...>) {
    return std::integer_sequence<int, (is + offset)...>{};
}

template<int diag, class Fn, int... is>
constexpr void zigzag2(Fn fn, std::integer_sequence<int, is...>) {
    (fn(diag % 2 ? is : diag - is, diag % 2 ? diag - is : is), ...);
}

template<int size, class Fn, int... diags>
constexpr void zigzag1(Fn fn, std::integer_sequence<int, diags...>) {
    (zigzag2<diags>(fn, offset_sequence<std::max(0, diags - size + 1)>(
        std::make_integer_sequence<int, 
            1 + std::min(diags, 2 * (size - 1) - diags)>{})), ...);
}
}

template<int size, class Fn>
constexpr void zigzag(Fn fn) {
    impl::zigzag1<size>(fn, std::make_integer_sequence<int, 2 * size - 1>{});
}

template<int size>
constexpr auto zigzag_indices() {
    std::array<std::pair<int, int>, size * size> arr{};
    auto it = arr.begin();
    zigzag<size>([&it](int x, int y) { it->first = x; it->second = y; ++it; });
    assert(it == arr.end());
    return arr;
}

zigzag<n>() generates n * n calls of the given functional object without loops and branches. zigzag_indices() generates an array of pairs of indices (idea taken from rafix07's answer). This function is constexpr, so that this array can be generated at compile-time.

Usage examples:

// 1.
zigzag<8>([&](int x, int y) { 
    output->push_back(input.at<float>(y, x));
});

// 2.
constexpr auto indices = zigzag_indices<8>();
for (auto i : indices) { 
    output->push_back(input.at<float>(i.second, i.first));
}

Demo

Answer 2

Your output vector stores float, so why do you try pushing a pointer to cv::Mat there?

If you have 8x8 matrix of float, just use .at<float>(y,x) method to access one float value of input matrix.

output->push_back(input.at<float>(y-1,x)); // -1 because you iterate in range <1,8>

Your approach seems that you want to use Rect as ROI and apply it on input matrix. If you want to get subregion of input Mat as 1x1 rect you could:

cv::Rect roi(x,y-1,1,1); // 1x1 matrix
output->push_back( input(roi).at<float>(0,0) );

Also I don't get it why you use N loops to make zigzag order, instead of array of pairs:

std::pair<int,int> zigZagOrder[64] = { {0,0},{1,0},{1,0},...};

then only look-up this.

In image processing every millisecond is imporant, don't waste time for fancy way of doing zigzag order.

Answer 3

I'm very sorry not to provide the code in C/C++, but I'm pretty sure you'll be able to translate this into C/C++ without any problem, because I did not use anything specific to python:

#!/usr/bin/env python

N = 4

i, j = 0, 0

while j != (N-1) :
    print i, j

    if i == 0 and (j & 1) :
        j += 1
        continue

    if j == 0 and (i & 1) == 0:
        i += 1
        continue

    if (i ^ j) & 1 :
        i -= 1
        j += 1
        continue

    if (i ^ j) & 1 == 0 :
        i += 1
        j -= 1
        continue

while i != (N-1) or j != (N-1) :

    print i, j

    if i == (N-1) and (j & 1) :
        j += 1
        continue

    if j == (N-1) and (i & 1) == 0 :
        i += 1
        continue

    if (i ^ j) & 1 :
        i -= 1
        j += 1
        continue

    if (i ^ j) & 1 == 0 :
        i += 1
        j -= 1
        continue

print i, j  # last square

output:

0 0
1 0
0 1
0 2
1 1
2 0
3 0
2 1
1 2
0 3
1 3
2 2
3 1
3 2
2 3
3 3