Matrix help

Question

phorce 131 Posting Whiz in Training

14 Years Ago

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 :)

c++ matrix-multiplication

Edited 14 Years Ago by phorce because: n/a

3 Contributors
8 Replies
133 Views
1 Day Discussion Span
Latest Post 14 Years Ago Latest Post by phorce

Dani AI

Generated 9 Months Ago

Summary and corrective notes tied to the thread: wants to make a 512x512 binary matrix A match matrix B by copying 32x32 blocks when a block is "different". correctly pointed out element-wise equality is simplest for exact match. was right to question FFT — FFT-based correlation is useful when you must search over many shifts, not when comparing blocks at the same coordinates.

Why a block mean is fragile
A block mean (fraction of ones) loses spatial information: two very different 32x32 patterns can share the same mean. For binary data a far better, cheap metric is Hamming distance (count of differing bits) or a normalized cross-correlation specialized for 0/1 data. Those both reflect actual per-pixel agreement instead of just density.

Practical, fast approach

Precompute three summed-area tables (integral images): S_A for A, S_B for B, and S_AB for elementwise AND (A & B). That takes O(N^2) to build and then yields onesA, onesB and common (A&B) for any axis-aligned block in O(1) via four lookups. See Summed-area table.

Use Hamming distance or normalized cross-correlation for the block:


N = block_w * block_h
onesA = sum(A block)      // from S_A
onesB = sum(B block)      // from S_B
common = sum(A&B block)   // from S_AB

hamming = onesA + onesB - 2common
NCC = (common - onesAonesB/N) / sqrt((onesA - onesAonesA/N)(onesB - onesB*onesB/N))


Handle zero-variance blocks (all-zeros or all-ones) separately.

3) Implementation alternatives
- If storing rows as 64-bit words, compute per-block Hamming with XOR+popcount on the covered words (very fast on modern CPUs using __builtin_popcountll or POPCNT).
- If you need many different block positions/sizes, summed-area tables are easiest and fastest per-query.

When to use FFT
Only use FFT-based convolution/correlation if you must compute cross-correlation across many relative displacements (search for best offset). For fixed-position comparisons or block-by-block similarity, FFT is unnecessary overhead. See [Normalized cross-correlation](https://en.wikipedia.org/wiki/Normalized_cross-correlation).

Practical tips
- 32x32 is fine (512 is divisible by 32, yielding 16x16 blocks). Benchmark both summed-area and bit-packed popcount implementations to pick the fastest for your workload.  
- Choose a clear threshold on Hamming or NCC to decide when to copy a block. Copying a whole block is only worthwhile if the expected cost of copying is less than correcting differing pixels individually.

All 8 Replies

jaskij 45 Junior Poster in Training

14 Years Ago

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.

ravenous 266 Posting Pro in Training

14 Years Ago

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.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

phorce 131 Posting Whiz in Training Featured Poster · Answer 1 · 2012-03-03T06:03:09+00:00

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? =)

phorce 131 Posting Whiz in Training Featured Poster · Answer 2 · 2012-03-03T19:14:03+00:00

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 266 Posting Pro in Training · Answer 3 · 2012-03-03T21:10:54+00:00

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 131 Posting Whiz in Training Featured Poster · Answer 4 · 2012-03-03T21:50:30+00:00

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 266 Posting Pro in Training · Answer 5 · 2012-03-03T23:27:59+00:00

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 131 Posting Whiz in Training Featured Poster · Answer 6 · 2012-03-03T23:33:45+00:00

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..)?

Matrix help

Dani AI

Recommended Answers Collapse Answers

All 8 Replies

Recommended Answers