Оптимизация процедуры поиска объектов на изображении. Иммунологический способ локализации узлов железнодорожных подвижных единиц на основе алгоритма клональной селекции. Применение одноклассового метода опорных векторов для формирования обучающей выборки.
Аннотация к работе
Система автоматического визуального диагностирования железнодорожных вагонов «Техновизор» [1, 2] реализует естественный и общедоступный подход к решению данной задачи посредством обработки и анализа информации об объекте, получаемой путем видеофиксации отдельных конструктивных элементов подвижных единиц. Для сокращения ресурсоемкости решения этой задачи целесообразно использовать различные эвристические подходы, учитывающие специфику процедуры поиска целевых объектов на изображении и уменьшающих, тем самым, пространство поиска [3]. В данной работе предлагается иммунологический метод визуальной локализации (ИМЛ) узлов железнодорожных подвижных единиц на основе одноклассового метода опорных векторов [4 - 6] и алгоритма клональной селекции [7 - 10], позволяющий оптимизировать процедуру поиска объектов на анализируемом изображении и, тем самым, значительно сократить время обработки требуемого объема данных. 1), однако для сокращения вычислительных затрат в качестве предварительного этапа алгоритма представляется целесообразным использовать алгоритм клональной селекции, определяющий некоторый набор участков изображения (набор координат угловых точек рамки поиска) для их обработки классификатором. Например, для этой цели можно использовать следующее правило: если по истечению заданного времени, найденный локальный минимум функции не соответствует пороговому значению, то принимается решение, что обрабатываемое изображение не содержит искомый объект. клональный селекция железнодорожный иммунологическийПредложенный в работе иммунологический метод локализации узлов железнодорожных подвижных единиц характеризуется высокой скоростью работы за счет комплексного применения одноклассовой классификации по методу опорных векторов и алгоритма клональной селекции.
Введение
Задача диагностирования подвижных единиц в железнодорожном составе является крайне актуальной для реализации технологического комплекса работ, позволяющего определить возможность и целесообразность дальнейшей эксплуатации подвижного состава, оценить остаточный ресурс его металлоконструкций и, в результате, продлить срок службы вагонов. При этом одним из основных требований к системе диагностирования является использование методов неразрушающего контроля, обеспечивающих пригодность вагона к дальнейшей эксплуатации.
Система автоматического визуального диагностирования железнодорожных вагонов «Техновизор» [1, 2] реализует естественный и общедоступный подход к решению данной задачи посредством обработки и анализа информации об объекте, получаемой путем видеофиксации отдельных конструктивных элементов подвижных единиц. Автоматизация этого процесса, предполагающего использование системы видеокамер высокого разрешения для видеофиксации интересующих конструктивных элементов вагонов и анализа их состояния в реальном масштабе времени, сопряжена с необходимостью высокоточной и оперативной локализацией различных узлов и участков интересующих элементов конструкции подвижной единицы на изображении высокого разрешения. В большинстве случаев, это крайне ресурсоемкий процесс, т.к. он представляет собой NP-сложную задачу, решение которой требует, как правило, проведения полного перебора всех участков полученного в результате видеофиксации изображения.
Для сокращения ресурсоемкости решения этой задачи целесообразно использовать различные эвристические подходы, учитывающие специфику процедуры поиска целевых объектов на изображении и уменьшающих, тем самым, пространство поиска [3]. В данной работе предлагается иммунологический метод визуальной локализации (ИМЛ) узлов железнодорожных подвижных единиц на основе одноклассового метода опорных векторов [4 - 6] и алгоритма клональной селекции [7 - 10], позволяющий оптимизировать процедуру поиска объектов на анализируемом изображении и, тем самым, значительно сократить время обработки требуемого объема данных.
1. Иммунологический метод визуальной локализации
Предлагаемый метод визуальной локализации основан на использовании классификатора, построенного по методу одноклассового метода опорных векторов, заключающегося в поиске глобального минимума выходной функции классификатора, на вход которого подаются фрагменты анализируемого изображения. В общем случае эти изображения формируются по принципу скользящего окна (рис. 1), однако для сокращения вычислительных затрат в качестве предварительного этапа алгоритма представляется целесообразным использовать алгоритм клональной селекции, определяющий некоторый набор участков изображения (набор координат угловых точек рамки поиска) для их обработки классификатором. Замена полного перебора эвристическим алгоритмом позволяет находить приемлемое решение при использовании существенно меньшего количества вычислительных ресурсов, а, следовательно, и сократить время поиска решения. Кроме того, применение одноклассового метода опорных векторов позволяет сократить время на составление обучающей выборки, т.к. требует для процесса обучения только положительных примеров изображения искомого объекта.
Рис. 1 Метод скользящего окна
Таким образом, иммунологический метод локализации является результатом совокупной работы алгоритма клональной селекции и одноклассового метода опорных векторов. Основная идея метода заключается в том, что на очередной итерации алгоритма клональной селекции формируется набор (популяция) фрагментов изображения для анализа (рис. 2), которая далее передается на обработку классификатору.
Рис. 2 Популяция фрагментов изображений
На заключительном этапе результат работы классификатора представляется в виде некоторой поверхности, соответствующей целевой функции (рис. 3), для которой осуществляется поиск глобального минимума. Решение об окончании работы алгоритма принимается на основе некоторых пороговых значений и/или временных интервалов, подобранных эмпирически. Например, для этой цели можно использовать следующее правило: если по истечению заданного времени, найденный локальный минимум функции не соответствует пороговому значению, то принимается решение, что обрабатываемое изображение не содержит искомый объект. клональный селекция железнодорожный иммунологический
Рис. 3 Поверхность целевой функции (х,y - координата левого верхнего угла скользящего окна, z - аффинность решения)
Для детализации рассматриваемого метода рассмотрим более подробно реализацию его этапов применительно к решаемой задачи: этап формирования популяции изображений и этапа классификации.
Этап формирования популяции изображений на основе алгоритма клональной селекции
Известно [5], что функция клональной селекции иммунной системы может быть интерпретирована как закон эволюции, с тремя основными принципами: многообразие, изменение и естественный отбор.
Несмотря на то, что алгоритм клональной селекции имеет множество вариаций, можно выделить общий принцип работы: подвергание популяции антител некоторым преобразованиям, увеличивающее их афинность.
В данной работе используется модификация алгоритма клональной селекции, представленная в виде блок-схемы, приведенной на рис. 4.
Рис. 4 Блок-схема алгоритма клональной селекции
Согласно рис. 4 очередная итерация рассматриваемого алгоритма клональной селекции может быть представлена в виде следующих шести шагов, в результате которых формируется новое поколение клеток (т.е. новый набор координат угловых точек рамки поиска): 1. Генерация очередной популяции клеток P из вариантов решения, состоящего из подмножества ячеек памяти (M), добавленных в оставшуюся (Pr) популяцию
P = Pr M
Как отмечалось выше, данная популяция соответствует исходному для текущей итерации набору координат угловых точек рамки поиска;
2. Отбор n-лучших особей из популяции (Pn), основанный на мере близости;
3. Клонирование отобранных n-лучших особей, временно увеличивающее количество клонов (C) особей популяции. Размер клона - возрастающая функция сродства с антигеном.
4. Прохождение популяции клонов через схему гипермутаций, где уровень гипермутации зависит от аффинности антитела с антигеном. Генерация популяции созревших антител (C*);
5. Повторный отбор улучшенных особей из C*, составляющих множество (M) клеток памяти. Некоторые клетки множества P заменяются улучшенными клетками множества C*;
6. Замена d-антител новыми (введение разнообразия). Клетки с низкой афинностью имеют более высокую вероятность быть замененными.
Этап классификации на основе одноклассового метода опорных векторов
Использованный при решении рассматриваемой задачи визуальной локализации метод классификации является одноклассовым методом, использующим неявную трансформационную функцию ?(·), определяемую как ядро матрицы проекции данных в более высокую размерность.
В качестве класса, содержащего множество положительных примеров, выбирался класс «Балка», соответствующий множеству изображений наиболее близких к эталонному изображению данного элемента конструкции. При этом функция, задающая границу разделения данного класса (гиперплоскость) g(·) определялась следующим образом:
где w - вектор-перпендикуляр границе решения и p - коэффициент смещения.
Далее, выражение (1) показывает решение функции, которая использует одноклассовый метод опорных векторов в целях выявления точек выбранного класса положительных примеров. Функция возвращает положительное значение для положительных примеров и отрицательное в противоположном случае: (1)
Метод одноклассовой классификации традиционно применяется на наборе смешанных данных, которые являются частично маркированными. На выходе алгоритма получается ответ вида: точка принадлежит заданному классу «Балка», либо нет, а также степень близости классифицируемого примера к границе разделения классов.
Вычислительные эксперименты
Для проведения вычислительных экспериментов метод ИМЛ был реализован в виде программного прототипа. В качестве примеров обучающего и тестового множества использовались монохромные изображения надрессорной балки тележки ж.-д. вагонов (рис. 5), полученные с помощью образца системы «Техновизор», подготовленного для проведения опытной эксплуатации.
В обучающем множестве, используемом для обучения классификатора, содержалось 6 тыс. уникальных положительных примеров размерностью 936 на 350 пикселей (всего 327600 признаков), а в тестовом - 1 тыс. положительных и 1 тыс. отрицательных примеров. Тестовая выборка для ИМЛ была представлена 1 тыс. изображений тележки (2004 на 930 пикселей).
Рис. 5 Примеры обучающей выборки
Программа экспериментов состояла из двух этапов: 1. Локализация надрессорной балки с помощью полного перебора и классификации с помощью одноклассового метода опорных векторов;
2. Локализация надрессорной балки с помощью предлагаемого подхода, использующего ИМЛ.
Каждый из экспериментов проводился по пять раз, а полученные результаты усреднялись.
Пример работы классификатора представлен на рис. 6 в виде тепловой карты (темно синий цвет - глобальный минимум, темно красный - локальные максимумы). Тепловая карта составлена из нормализованных значений «ответов» классификатора - аффинности. Оси абсцисс, ординат - значения координат центра скользящего окна классификатора. Значение целевой функции в искомой точке (529; 103) равняется нулю (глобальный минимум). Среднее время полного прохода классификатора скользящим окном по изображению тележки (2004 на 930 пикселей) составляет 8,5 часов.
Рис. 6 Пример локализованной надрессорной балки с соответствующей ей картой поверхности целевой функции локализации
Применение ИМЛ позволило сократить время локализации надрессорной балки (нахождения глобального минимума) до 30 секунд за счет отсутствия необходимости использования полного перебора. Количество найденных глобальных минимумов целевой функции составило 99,9% всей тестовой выборки.
Эксперименты выполнялись на специализированном компьютере серверного исполнения с установленными двумя процессорами Intel Xeon E5-2660V2 частотой 2660 МГЦ.
Вывод
Предложенный в работе иммунологический метод локализации узлов железнодорожных подвижных единиц характеризуется высокой скоростью работы за счет комплексного применения одноклассовой классификации по методу опорных векторов и алгоритма клональной селекции. Кроме того, применение в качестве классификатора одноклассового метода опорных векторов, для обучения которого используются только положительные примеры, существенно уменьшает сложность и сокращает время формирования обучающей выборки.
Работа выполнена при финансовой поддержке РФФИ, проект № 13-07-00226 А, проект № 13-07-13109 офи_м_РЖД.
Список литературы
1. A. Dolgiy, S. Kovalev, V. Samsonov, A. Khatlamadzhiyan. Processing of fuzzy graphic images in intelligent computer vision systems on railway transport. 9th International Conference “Application of information and communication technologies - AICT2015”, IEEE: CFP1556H-ART, pp.118-121.
2. И.С. Артемьев, А.И. Долгий, А.И. Лебедев, А.Е. Хатламаджиян. Модель оптической локализации железнодорожных подвижных единиц на основе искусственной иммунной системы отрицательного отбора // Инженерный вестник Дона, 2014. - № 4 URL: ivdon.ru/ru/magazine/archive/N4y2014/2700
3. И.С. Артемьев, А.И. Лебедев, А.И. Долгий, А.Е. Хатламаджиян, В.Д. Меерович. Метод блочного оптического распознавания инвентарных номеров железнодорожных подвижных единиц на основе комитетной нейроиммунной модели классификации // Инженерный вестник Дона, 2014, - № 1 URL: ivdon.ru/ru/magazine/archive/n1y2014/2259
4. Timmis J. Artificial immune systems - today and tomorrow // Natural Computing. March 2007, Volume 6, Issue 1, pp. 1-18.
5. Cziko, G. (1995), The Immune System: Selection by the Enemy, In Without Miracles, G. Cziko, A Bradford Book, The MIT Press, pp. 39-48.
6. Holland, J. H. (1995), Adaptation in Natural and Artificial Systems, 4th Ed., MIT Press.
7. B. Sch?lkopf, J.C. Platt, J. Shawe-Taylor, A.J. Smola, and R.C. Williamson. Estimating the support of a high-dimensional distribution. Neural computation, 13(7):1443-71, July 2001.
8. R. Vert, J.-P. Vert, Consistency and Convergence Rates of One-Class SVMS and Related Algorithms, JMLR 7, 817-854, 2006.
9. V. Vapnik and A. Lerner. Pattern recognition using generalized portrait method. Automation and Remote Control, 24:774-780, 1963.
10. Larry M. Manevitz, Malik Yousef. One-Class SVMS for Document Classification // Journal of Machine Learning Research 2, 2001. - pp. 139-154.
References
1. A. Dolgiy, S. Kovalev, V. Samsonov, A. Khatlamadzhiyan. Processing of fuzzy graphic images in intelligent computer vision systems on railway transport. 9th International Conference “Application of information and communication technologies - AICT2015”, IEEE: CFP1556H-ART, pp.118-121.
4. Timmis J. Artificial immune systems - today and tomorrow. Natural Computing. March 2007, Volume 6, Issue 1, pp. 1-18.
5. Cziko, G. (1995), The Immune System: Selection by the Enemy, In Without Miracles, G. Cziko, A Bradford Book, The MIT Press, pp. 39-48.
6. Holland, J. H. (1995), Adaptation in Natural and Artificial Systems, 4th Ed., MIT Press.
7. B. Sch?lkopf, J.C. Platt, J. Shawe-Taylor, A.J. Smola, and R.C. Williamson. Estimating the support of a high-dimensional distribution. Neural computation, 13(7):1443-71, July 2001.
8. R. Vert, J.-P. Vert, Consistency and Convergence Rates of One-Class SVMS and Related Algorithms, JMLR 7, 817-854, 2006.
9. V. Vapnik and A. Lerner. Pattern recognition using generalized portrait method. Automation and Remote Control, 24:774-780, 1963.
10. Larry M. Manevitz, Malik Yousef. One-Class SVMS for Document Classification. Journal of Machine Learning Research 2, 2001. pp. 139-154.