算法题：均匀噪声二值图像分类

Question

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

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

还有一个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，除非pattern中1的数量极少，否则“10%翻转”误导棋盘位置的可能性极小图案。换句话说，“模式存在的地方”是自动解决的。

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

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

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

如果由1组成的形状具有特征性且彼此之间不够相似，则应评估前者（a和b）。这样的话，即使有些1被“翻转”成了lost/caused，也不会影响形状区分。在评价中加入c和d，只能增加“0到1翻转”造成误判的可能性。（我觉得你的情况是这样的。）

如果模式中的大部分地方是1而其余只有少数地方是0，则故事是相反的。

算法题：均匀噪声二值图像分类

algorithm problem: uniform noise binary image classification

algorithm

probability