Программы для распознавания образов.
Программы для распознавания образов.
Задача в общем виде:
программе показывают изображения нескольких классов объектов, указывая их класс. Затем программа должна классифицировать вновь предъявляемые объекты.
Известные алгоритмы реализации таких программ:
1. Персептрон: многоуровневая сеть рецепторов, где каждый связан с каждым связью с изменяемым значением силы связи. Каждый предъявляемый объект характеризуется одним числом. Программа подгоняет значения сил связей так, чтобы объекты разных классов попадали в непересекающиеся массивы.
2. Алгоритм Finereader-а [могу ошибаться]: программа ищет для каждого объекта функции топологически связанных точек и сравнивает их с имеющимся словарём, с возможностью дополнения словаря при обучении.
3. [Есть ли какие другие алгоритмы?]
У нас задача проще: все объекты относятся к одному классу, поэтому мы вводим в программу шаблон, к которому программа должна подогнать предъявляемое изображение.
В программу вводится известная последовательность нуклеотидов и указываются маркёрные дорожки, полосы в которых соответствуют расщеплению по определённым нуклеотидам. Программа должна идентифицировать все полосы и соотнести их с последовательностью и потом сопоставить с ними все полосы рабочих дорожек.
Я пытался реализовать принцип ‘’искажения перспективы’’: изображение переводится в двумерный массив точек максимумов интенсивности, которые подгоняются под идеальный шаблон, введением различных функций изменения расстояний между соседними точками по осям X и Y.
Сначала программа находит на маркерной дорожке максимумы и подгоняет их сетку под задаваемый последовательностью нуклеотидов шаблон, постепенно отбрасывая наименьшие максимумы, пока не найдёт соответствия. Затем программа начинает заново искать максимумы рядом с определёнными максимумами, запоминая расстояния. Потом программа ищет все максимумы на других дорожках и двигает дорожки как целое, ища минимум разности между близлежащими пиками разных дорожек [тут нужно вводить ручную корректировку, поскольку велика вероятность неправильного сдвига дорожки на целое число шагов]. Последний шаг: программа должны выдать интегральное значение всех пиков на всех дорожках соотнося их с заданной последовательностью.
Алгоритм нахождения пиков A+G маркёра.
1. Берётся скан нижней части дорожки A+G (это где полосы сильно разнесены) – 1200-1500 точек – обычно примерно четверть геля и, суммируя по 10 точек справа и слева, находятся координаты всех пиков.
2. Суммирует по 10 точек около максимума каждого пика. Все значения суммируются и находится среднее. Если пик в 2 раза меньше среднего (+ поправочный коэффициент из пункта 6) он обнуляется.
3. Если расстояние между соседними пиками меньше 5 точек один удаляется.
4. Находится минимальное расстояние между соседними пиками. (Предполагается, что это расстояние соответствует соседним парам оснований – если на выбранном участке не будет соседствующих пуринов (A+G) – программа ничего не распознает).
5. Программа составляет массив 0 и 1 : 1 – A+G полоса, 0 – С+Т пропуск. Число пропусков определяется по формуле – целое от расстояния между пиками, делённого на минимальное расстояние.
6. Через этот массив протаскивается последовательность – если соответствие (+ допуск в 2 пика) не находится - вводится поправочный коэффициент на отсечение пика и возврат в пункт 2.
7. Поиск следующего A+G пика по последовательности. [До этого принимали, что на первом участке пики расположены примерно равномерно – затем сжатие расстояний между пиками увеличивается]. Программа смотрит по последовательности, через сколько шагов должен быть следующий A+G пик и ищет, постепенно увеличивая район поиска. После нахождения корректирует межпиковый шаг и ищет координаты следующего пика.
(Последние исправления - 20.07.2006)
