Searching through Vector for another vector

[phorce]

Hello,

I have 2 vectors, and I'm trying to search/scan the first vector for the second vector.

Let's say I have this vector/Matrix:
M1 =

0 1 1 0
0 1 1 1
1 0 1 1
0 0 0 1

M2 =

0 1
0 1

Then I will search the M1 for M2 by scanning each value (Kind of like a binary tree) or until it's found the right solution. Now I'm using an algorithm like this:

const int ROW_BOUNDS = matrix1.size() - matrix2.size(); // 16 - 4
const int COL_BOUNDS = 4 - 2;

   bool found = false;

   for(int i=0; (i < ROW_BOUNDS); i++)
   {
      bool matchFound = false;

      for(int j=0; (j < COL_BOUNDS); j++) {
         cout << matrix1[i*4+j] << ' ';
      }
      cout << endl;
   }

But when I try to output the results (using the same data provided above) I get this:

0 1 
0 1 
1 0 
0 0 
0 1 
2.1536e-314 2.1536e-314 
0 0 
0 0 
0 1 
9.88131e-324 2.78134e-309 
0 0 
0 0 

But I have tried different calculations, different values and I get the same result. I'm wondering if anyone can see where I'm going wrong and offer some help?

Thanks :)

[histrungalot]

Try, but only tested it a little

#include <vector>
#include <iostream>
using namespace std;

int main(){
   vector<int> m1,m2,m3;
   m1.push_back(0); m1.push_back(1); m1.push_back(1); m1.push_back(0);
   m1.push_back(0); m1.push_back(1); m1.push_back(1); m1.push_back(1);
   m1.push_back(1); m1.push_back(0); m1.push_back(1); m1.push_back(1);
   m1.push_back(0); m1.push_back(0); m1.push_back(0); m1.push_back(1);

   m2.push_back(0); m2.push_back(1);
   m2.push_back(0); m2.push_back(1);

//------------------------------------------  
// Just thinking
//   1 2 3 4 5 6 
//   1 2 
//     1 2 
//       1 2 
//         1 2 
//           1 2 

   int mat1Rows(4), mat1Cols(4),
       mat2Rows(2), mat2Cols(2);

   const int ROW_BOUNDS(mat1Rows-mat2Rows+1);
   const int COL_BOUNDS(mat1Cols-mat2Cols+1);

   for(int i=0; (i < ROW_BOUNDS); i++) {
      for(int j=0; (j < COL_BOUNDS); j++) {
         m3.clear();
         for (int row(0); row < mat2Rows; row++){
            for (int col(0); col < mat2Cols; col++){
               cout << m1[i*4+row*4+col+j] << ' ';
               m3.push_back(m1[i*4+row*4+col+j]);
            }
            cout << endl;
         }
         if ( m3 == m2 )
            cout << "Equal!" << endl;
         else 
            cout << "Not equal!" << endl;
         cout << endl;
      }
   }
}

Output

$ ./a.out
0 1 
0 1 
Equal!

1 1 
1 1 
Not equal!

1 0 
1 1 
Not equal!

0 1 
1 0 
Not equal!

1 1 
0 1 
Not equal!

1 1 
1 1 
Not equal!

1 0 
0 0 
Not equal!

0 1 
0 0 
Not equal!

1 1 
0 1 
Not equal!
$

[phorce]

Hey thank you, it works on the test data (4x4), (2x2) but when I try it on actual data (1024x786) and the small matrix is: (36x49) it doesn't seem to work and just carries on printing..

    int mat1Rows(1024), mat1Cols(786),
    mat2Rows(36), mat2Cols(49);

    const int ROW_BOUNDS(mat1Rows-mat2Rows+1);
    const int COL_BOUNDS(mat1Cols-mat2Cols+1);
    vector<double> m3;
    for(int i=0; (i < ROW_BOUNDS); i++) {
        for(int j=0; (j < COL_BOUNDS); j++) {
            m3.clear();
            for (int row(0); row < mat2Rows; row++){
                for (int col(0); col < mat2Cols; col++){
                    cout << matrix1[i*1024+row*1024+col+j] << ' ';
                    m3.push_back(matrix1[i*1024+row*1024+col+j]);
                }
                cout << endl;
            }
            if ( m3 == matrix2 )
            {
                cout << "Equal!" << endl;
            }else{
                cout << "Not Equal!" << endl;
            }
        }
    }

Do you think I would need to change the ROW_BOUNDS, COL_BOUNDS?

Thank you again by the way :)

[histrungalot]

line 12, 13 should not be 1024 but mat1Cols inplace of the 1024. You want to stride by columns not rows.

Edit: Remove the printing so it goes faster and we can just see the Equal or Not.

[phorce]

Hey (And my life just get's worse) ..

It appears that Matrix 2, doesn't actually exist inside Matrix 1 .. Well, it does, it just contains noise and such

Do you think I could pass m3 to a function that checks the simulairty of M3 to M2 and whichever has the highest simularity then this is the resulting matrix?

Thanks

[histrungalot]

Just thinking out loud, you could multiply m2 and m3 element by element and the sum the result. The value m3 x m2 that is closest to m2 x m2 might be close enough for you to declare as a match. It's like an autocorrelation. It's not perfect but it's a start.

[phorce]

Hey thanks for the advice, something like this:

    double compareMatrix(vector<double> &theMatrix1, vector<double> &theMatrix2)
{
    double matrix1Sum = 0;
    double matrix2Sum = 0;
    double simualirty = 0;

    for(int i=0; (i < theMatrix1.size()); i++)
    {
        matrix1Sum = theMatrix1[i] * theMatrix1[i + 1];
    }

    for(int i=0; (i < theMatrix2.size()); i++)
    {
        matrix2Sum = theMatrix2[i] * theMatrix2[i + 1];
    }

    simualirty = (matrix1Sum+matrix2Sum);

    return simualirty;
}
// main
    double corrVal = 0;
    int mat1Rows(4), mat1Cols(4),
    mat2Rows(2), mat2Cols(2);

    const int ROW_BOUNDS(mat1Rows-mat2Rows+1);
    const int COL_BOUNDS(mat1Cols-mat2Cols+1);
    vector<double> m3(2*2, 0);
    for(int i=0; (i < ROW_BOUNDS); i++) {
        for(int j=0; (j < COL_BOUNDS); j++) {
            m3.clear();
            for (int row(0); row < mat2Rows; row++){
                for (int col(0); col < mat2Cols; col++){
                    //cout << matrix1[i*mat1Cols+row*mat1Cols+col+j] << ' ';
                    m3.push_back(matrix1[i*mat1Cols+row*mat1Cols+col+j]);
                    double currentCorrVal = compareMatrix(m3, matrix2);
                    if(currentCorrVal > corrval)
                    {


                    }
                }
            }
        }
    }

But the only problem I can see with this is, once I've found the best match for the matrix2, I need change all the elements in matrix2 to "0" but, it has to be in the same position as it is in matrix1 because I need to output. If this makes sense? So basically:

Check if currentCorrVal > corrVal
   if true 
    store the position of the best fit matrix in matrix1
   if false
      iterate through again

Change all the elements in the highest result (matrix) to all 0's

If that makes sense?

Thanks :)

[histrungalot]

Or maybe like
http://stackoverflow.com/questions/938260/comparing-two-matrices-in-matlab
Use the same logic, just need to change it to C++