我有一個非常有趣的演算法問題（不是影像處理！）。但我還是不明白。請幫我。
問題：
有 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（模式） | 0（模式） | |
|---|---|---|
| 1（噪聲影像） | 一種 | C |
| 0（噪聲影像） | b | d |
然后，給定一個模式和一個噪聲影像塊（4×4），一個模式是噪聲影像塊的概率如下。
(9/10) (a d) * (1/10) (b c)
簡而言之，
9 (a d) /10 16
那么，它不應該與a d成正比嗎？但答案與 ab 成正比。
我的問題是，在上面的問題中，為什么答案與ad成正比，為什么不考慮它為0時正確答案是什么？請幫我..
uj5u.com熱心網友回復：
由于 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，那么故事就顛倒了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478414.html
下一篇：如何向后查找索引