Если бы не шумовые линии, мы бы смогли сразу точно определить расположение цифр на изображении путем отсечения светлых участков со всех четырех сторон — наши цифры были бы единственным темным пятном. Но придется решить небольшую оптимизационную задачу. Задача оптимизации в общем виде состоит в поиске оптимального значения параметров некоторой целевой функции, значение которой необходимо максимизировать или минимизировать.
В нашем случае целевой функцией будет суммарная яркость (точнее её обратное значение] области предполагаемого расположения надписи. Другими словами мы будем стараться найти на изображении темное пятно, по форме напоминающее нашу надпись (нам известны размеры цифр и расстояния между ними). Итак, у нас есть 4 прямоугольника, которые при наличии наклона шрифта превращаются в параллелограммы, необходимо найти такое расположение этой группы параллелограммов и такой наклон, чтобы минимизировать суммарную яркость внутри этих параллелограммов.
В итоге у нас есть три параметра: х, у [левый верхний угол первого параллелограмма] и d — сдвиг нижнего основания относительно верхнего. Такой метод поиска надписи будет эффективен для не слишком зашумленных линиями изображений, о которых мы и говорили выше. Для решения подобных задач оптимизации, таких, для которых нет возможности найти аналитическое решение, хорошо подходят генетические алгоритмы.
Генетический алгоритм моделирует процессы биологической эволюции: на основе естественного отбора направляет случайный перебор решений в нужном направлении (максимизации или минимизации целевой функции]. На первом шаге алгоритма создается начальная популяция особей, каждая особь — один из вариантов решения (набор параметров).
Затем для каждой особи рассчитывается значение целевой функции, называемое в контексте эволюции приспособленностью. Если значение целевой функции устраивает постановщика задачи, алгоритм останавливается, если нет — начинается создание нового поколения. Новое поколение формируется на основе предыдущего с помощью операторов мутации и кроссовера, которые моделируют соответствующие биологические процессы.
Оператор мутации изменяет случайным образом один из параметров решения, а оператор кроссовера скрещивает два решения (например, случайным образом выбирается часть параметров первого решения и соединяется с соответствующими параметрами второго). Отбор особей для создания нового поколения осуществляется по принципу естественного отбора - чем выше значение целевой функции (приспособленность) особи, тем выше вероятность её перехода в новую популяцию.
После создания нового поколения вновь проводится оценка каждой особи, выявляется лучшая и проверяется условие остановки. Если цель всё ещё не достигнута, создается очередная популяция и т.д. В нашем случае решением является вектор из трех переменных х, у и d, а целевая функция — суммарная яркость пикселов внутри параллелограммов. Расчет целевой функции производится следующим образом:
Комментариев нет:
Отправить комментарий