Matrix help

[phorce]

Hello,

I have 2 massive matrix's and I need to compare one matrix with another.. Now, I have come up with a solution that takes a 5x5 block of the matrix1 and compares it with a 5x5 block of matrix2, this happens until the end of both matrix's..

I'm confused to how I would select a 5x5 block of the two matrix. Here is the code:

for(int i=0; (i < 512); i++) // rows
    {
        for(int l=0; (l < 512); l++) // columns
        {
            for(int j=0; (j < 5); j++) // select 5 rows
            {
                for(int k=0; (k < 5); k++) // select 5 columns
                {
                    cout << matrix2[j*512+k] << ' ';
                }
                cout << endl;
            }
        }
    }

Does anyone have any ideas?

Thanks :)

[jaskij]

IMO, you could just go by every single value and check if they're equal. Like when comparing strings. It doesn't really matter how you go through them, if the matrices are equal you WILL go through every single value anyways. And what you do just asks for bugs.
Why not do something like

// 262144 is 512^2
bool equal=true;
for(i=0;i<262144;i++){
	if(a[i]!=b[i]){
		equal=false;
		cout<<different;
		break;
	}
}
if(equal)cout<<equal;

Also, you could think of pre-computing some cheap (?) metric of those matrices and using it as a precondition when checking for equality.

[phorce]

Hello,

Thanks for the reply..

Have you heard of an FFT (Fast Fourier transform) it's this way I'm trying to implement. I know what you're suggesting but wouldn't it be a timely process? For example:

If I have:

Matrix 1:

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

Matrix 2:

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

Matrix 2 is the matrix that Matrix 1 needs to be..

First comparison:

0 1 1 -> 0 0 0
0 1 1 1 1 0

Then find the mean value..

0 1 1 -> 0 0 0
0 1 1 1 1 0

1 0

They do not match, swop them..

Something along those lines? =)

[ravenous]

Have you heard of an FFT (Fast Fourier transform) it's this way I'm trying to implement.

I'm afraid I don't see how any of this relates to FFTs? Are you trying to implement some kind of bit reversal?

If I have:

Matrix 1:

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

Matrix 2:

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

Matrix 2 is the matrix that Matrix 1 needs to be..

First comparison:

0 1 1 -> 0 0 0
0 1 1 1 1 0

Then find the mean value..

0 1 1 -> 0 0 0
0 1 1 1 1 0

1 0

They do not match, swop them..

I'm afraid I also don't understand what you're getting at here either. Would you be able to explain further?

Finally, looking at your original code snippet, you can compare in 5 x 5 blocks by doing this:

for( int i = 0; i < 512; i += 5 /* Increment this by your block size */) // rows
{
    for( int l = 0; l < 512; l += 5 /* Increment this by your block size */) // columns
    {
        for( int j = i /* Don't set this to zero */; j < 5; ++j ) // select 5 rows
        {
            for( int k = j /* Don't set this to zero */; k < 5; ++k ) // select 5 columns
            {
                cout << matrix2[ j*512+k ] << ' ';
            }
            cout << endl;
        }
    }
}

This isn't quite right, since 512 isn't a multiple of 5, so you will try to access invalid elements of matrix2 towards the end, but that can be sorted out fairly easily.

[phorce]

Hello thank you for your reply..

I have 2 matrices that are different but contain similarities. At the minute, I'm checking each individual bit and then swopping the values from matrix 2 to matrix 1 when they do not match. Doing this process bit by bit is timely.

I have been thinking and wanting to implementing an algorithm that swops the values by blocks of 32 x 32 because (512/16 = 32)... So in theory the process would work like this:

Run through the matrix1
Select a 32x32 block from matrix 1
Find the mean of this block
Select a 32x32 block from matrix2
Find the mean of this block
If the mean of both blocks do not match
Swop block2 to matrix1 [at the same position]
if the mean matchs, leave the block
end

Is this possible?

[ravenous]

I have 2 matrices that are different but contain similarities. At the minute, I'm checking each individual bit and then swopping the values from matrix 2 to matrix 1 when they do not match.

Isn't this just the same as setting matrix1 equal to matrix2 ?

Run through the matrix1
Select a 32x32 block from matrix 1
Find the mean of this block
Select a 32x32 block from matrix2
Find the mean of this block
If the mean of both blocks do not match
Swop block2 to matrix1 [at the same position]
if the mean matchs, leave the block
end

It's entirely possible to do this, but I'm not sure what it achieves. It's confusing, because it doesn't sound the same as the element-wise comparison you described first.

[phorce]

It's entirely possible to do this, but I'm not sure what it achieves. It's confusing, because it doesn't sound the same as the element-wise comparison you described first.

What I'm trying to achieve is by swopping by 32 x 32 blocks rather than single bits.. This will make it a lot more efficient kind of like this method:
- Find the mean value of both matrices; subtract each element of
the matrices by its mean value
- For the numerator, multiply matrices element by element; take
the sum of the resultant matrix after multiplication
- For the denominator,square each matrix element by element;
take the sum of each squared matrix; multiply the sum; square
the multiplied results
- Divide the numerator by the denominator
- The larger the similarity score, the more similar the matrices
are simular

If that makes more sense?

[ravenous]

It sounds like your trying to cacluate the cross-correlation between the two matrices. If so, one element at a time is basically as good as it gets, unless your going to start building some concurrency into your program. Doing it in blocks like you're proposing adds complication, but doesn't speed anything up. Even if you decided to use some form of concurency, the over head may be higher than the saving from doing some parts in parallel, except for really big matrices. For a 512 x 512 matrix, doing it in a simple element by element manner is probably sufficient.

[phorce]

I was getting confused, I apologise..

Basically the cross-correlation between two matrices basically determines whether they are simular or not? If they are not simular then the swopping happens to make them simular..

One question regarding the cross-correlation: Can I do it on binary bits? Like find the mean etc..? Or do I have to convert the binary to the bit value (1, 2, 4, 8, 16 et..)?