算法问题：均匀噪声二进制图像分类。

Question

我有一个非常有趣的算法问题（不是图像处理！），但我还是不理解。请帮帮我。

问题：
有10个大小为4×4的模式（二进制）。例如，

0001
0011
0111
0001

现在，有一个16×16的棋盘（初始设为0）。

现在，我们选择10个模式中的一个，并将其放置在16×16的棋盘上的随机位置上（位置和模式均随机选择）。例如：

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

接下来，每个值都将以10%的概率翻转。例如，

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

这里的问题是猜测最初存在的模式（允许70%以上的准确率）。换句话说，在100个查询中，必须成功70次或以上。

我的第一种方法是计算每个可能补丁和模式的准确率。例如，

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);
            }
        }
    }
}

然而，这种方法结果灾难性。我认为这是因为模式中的零越多，分数就越高。 成功的方法只计算模式为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];
}

我不理解这个公式是怎么得出来的。为什么我们不需要考虑模式为零的区域？

经过更多的研究，我得到了以下的公式：

我们假设：

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

那么，给定一个模式和一个噪声图像块（4×4），模式成为一个噪声图像块的概率如下：

(9/10)^(a+d) * (1/10)^(b+c) 简而言之，

9^(a+d)/10¹⁶ 所以，它不应该与a+d成比例吗？但答案是与a-b成比例。

我的问题是，在上述问题中，为什么答案与a-d成比例，为什么在没有考虑它时，正确的答案是0？请帮我解决这个问题。

- 장해웅

Answer 1

因为16x16的棋盘被初始化为0，除非图案中的1数量极少，否则“10%翻转”很难误导图案的位置。 换句话说，“图案存在的位置”是自动解决的。

因此，问题本质上是“我对特定的4x4图案应用了10%的翻转。哪一个是原始图案？”

我认为，以下哪一组对于这个问题更有效取决于这10个图案的内容。

• a和b：“1（图案）必须是1（噪音图像）”
• c和d：“0（图案）必须是0（噪音图像）”

如果由1组成的形状具有特征且彼此不太相似，则应评估前者（a和b）。 在这种情况下，即使由于“翻转”而丢失/引起了一些1，也不会影响形状区分。 将c和d加入评估只会增加由“0到1翻转”引起的误识别的可能性。 （我认为你的情况就是这样。）

如果图案中的大多数地方都是1，而其余只有少量为0，则情况将反转。

- fana