Задача алгоритма: классификация бинарных изображений с равномерным шумом

У меня есть очень интересный проблема алгоритма (не обработка изображений!). Но я все еще не понимаю. Помогите пожалуйста мне.

Проблема:
Есть 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 (шумовое изображение)ас
0 (шумовое изображение)б

Затем, учитывая шаблон и фрагмент изображения шума (4 × 4), вероятность того, что шаблон является фрагментом изображения шума, следующая.

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

Короче,

9(a+d)/1016

Итак, разве оно не должно быть пропорционально a+d? Но ответ пропорционален a-b.

Мой вопрос в приведенной выше задаче, почему ответ пропорционален a-d, и почему правильный ответ, когда он равен 0, не учитывая его? пожалуйста, помогите мне..

Хорошая домашняя работа...

Yves Daoust 17.05.2022 08:37
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
4
1
37
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Поскольку доска 16x16 была инициализирована как 0, если только количество 1 в паттерне не очень мало, крайне маловероятно, что «переворот на 10%» приведет к неправильному расположению паттерна. Другими словами, «Где существовал шаблон» решается автоматически.

Таким образом, вопрос, по сути, звучит так: «Я применил 10% переворот к определенному шаблону 4x4. Какой шаблон является исходным?»

Я думаю, что от содержания 10 паттернов будет зависеть, какая из следующих групп более эффективна для решения этой проблемы.

  • a и b: «1(шаблон) должен быть 1(шумовое изображение)»
  • c и d: «0 (шаблон) должен быть 0 (шумовое изображение)»

Если формы, состоящие из 1, характерны и недостаточно похожи друг на друга, следует оценить первые (a и b). В этом случае, даже если некоторые 1 будут потеряны/вызваны «переворотом», это не повлияет на различие формы. Добавление c и d к оценке может только увеличить вероятность ошибочной идентификации, вызванной «переключением 0 на 1». (Я думаю, что у вас такая ситуация.)

Если большинство мест в узоре — 1, а остальные лишь немногие — 0, история обратная.

Другие вопросы по теме