algorithm problem: uniform noise binary image classification

Question

I have a very interesting algorithm problem (not image processing!). But I still don't understand. Please help me.

Problem:
There are 10 patterns with 4×4 size (binary). For example,

and there's a 16×16 board (it is initialized to 0).

Now, let's choose one of 10 patterns and put it in a random position on the 16×16 board (position and pattern are selected randomly). For example,

000000000....
000100000....
001100000
001100000
000100000
000000000
000000000
........

After that, each value will be flipped with a 10% probability. For example,

000000000....
000100010....
001000000
001100100
000100000
010000000
000000100
........

Here, the problem is to guess which pattern originally existed(accuracy more than 70% allowed). In other words, out of 100 queries, it has to be successful 70 times or more.

My first approach was to calculate the accuracy for every possible patch and pattern. For example,

int NOISE_IMAGE[16][16];
int PATTERN[10][4][4];
double getScore(int x, int y, int pIdx){
    int confusion[2][2] = { 0, };
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            confusion[NOISE_IMAGE[x + i][y + j]][PATTERN[pIdx][i][j]]++;
        }
    }
    return (double)(confusion[0][0] + confusion[1][1]) / 16.;
}

void solve(){
    for (int pattern = 0; pattern < 10; pattern++){
        for (int x = 0; x < 14; x++){
            for (int y = 0; y < 14; y++){
                double score = getScore(x, y, pattern);
            }
        }
    }
}

However, this approach has disastrous results. I think it's because the more zeros in the pattern, the higher the score.

A successful approach simply computes the difference only in the region where the pattern is 1.

int getScore(int x, int y, int pIdx){
    int confusion[2][2] = { 0, };
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            confusion[NOISE_IMAGE[x + i][y + j]][PATTERN[pIdx][i][j]]++;
        }
    }
    return confusion[1][1] - confusion[0][1];
}

I don't understand why this formula came up. Why don't we need to consider regions where the pattern is zero?

After more study, I was able to get the following formula:

Let's assume

	1 (pattern)	0 (pattern)
1 (noise image)	a	c
0 (noise image)	b	d

Then, given a pattern and a noise image patch (4×4), the probability that a pattern be a noise image patch is as follows.

(9/10)^(a+d) * (1/10)^(b+c)

In short,

9^(a+d)/10¹⁶

So, shouldn't it be proportional to a+d? But the answer is proportional to a-b.

My question is, in the above problem, why is the answer proportional to a-d, and why is the correct answer when it is 0 without considering it? please help me..

user_18362054 · Answer

Because 16x16 board was initialized to 0, unless the number of 1 in the pattern is extremely small, it will be extremely unlikely that "10% flipping" will mislead the location of the pattern. In other words, "Where the pattern existed" is automatically solved.

Therefore, the question is essentially "I applied 10% flipping to a specific 4x4 pattern. Which is the original pattern?"

I think that, which of the following groups is more effective for this problem will depend on the content of the 10 patterns.

a and b : "1(pattern) must be 1(noise image)"
c and d : "0(pattern) must be 0(noise image)"

If the shapes composed of 1 are characteristic and are not sufficiently similar to each other, the former(a and b) should be evaluated. In this case, even if some 1 are lost/caused by "flip", it will not affect the shape distinction. Adding c and d to the evaluation can only increase the likelihood of misidentification caused by "0 to 1 flipping". (I think your situation is like this.)

If most of the places in the pattern are 1 and only a few of the rest are 0, the story is reversed.

algorithm problem: uniform noise binary image classification

1 Answers