Распознавание изображения SURF-методом

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:15, 25 июня 2016.
Open book.svg Авторство
Е. С. Сараева
Н. В. Чичварин
Согласовано: 11.06.2016

SURF (англ. Speeded Up Robust Features) – метод распознавания изображений, основанный на поиске особых точек изображения и создания их дескрипторов.

Формулировка задачи

Решение задачи обнаружения и распознавания. Определение координат уникального объекта в произвольном изображении. В изображении, в котором априори присутствует искомый объект, определить его положение.

Методика распознавания

В качестве методики распознавания был выбран SURF-метод. Данная методика основана на поиске особых точек изображения и создание их дескрипторов. Дескрипторы инвариантны к масштабированию и вращению. Для каждой точки считается градиент максимального изменения яркости и коэффициент масштабирования по матрице Гессе. Согласно статистическим данным, эта методика достаточно хорошо зарекомендовала себя, однако, как будет показано далее по ходу работы, в случае недостаточно ярко выраженных особых точек, распознавание объекта затрудняется. Так же такой метод достаточно быстр.

Среда разработки

Работа выполняется в среде Matlab, поскольку для выполнения требуются средства утилиты Image ToolBox Processing, подробное описание которой удалось найти только для Matlab. Информации, которая содержится в e-book MATHCAD, к сожалению, оказалось не достаточно для выполнения задания. Подробную информацию о каждой из используемых далее функций можно найти в [4]

Выполнение работы

Тестирование на скомпанованном изображении

Для начала в качестве оригинала изображения возьмем игральную карту. Не большое количество элементов, малое количество цветов обеспечат высокую наглядность (Рис. 1).

Рис. 1. Исходное изображение.


Далее определимся с фоновым изображением, на котором будем производить поиски. Возьмем просто красивый уральский пейзаж (Рис. 2).

Рис. 2. Фон для поиска исходного изображения.


Средствами Paint соединим две картинки вместе. Чтобы задача распознавания была хоть чуточку сложнее, перевернем изображение карты на 90 градусов (Рис. 3).

Рис. 3. Наложенное изображение


Итак, приступим к работе. Подадим программе на вход оригинал изображения – карту. Следующие строки кода преобразовывают ее в черно-белое изображение, которое в дальнейшем понадобится нам для работы. Третья строка выделяет SURF-дескрипторы на сером изображении. Четвертая строка возвращает векторы признаков и их местоположение. Далее мы накладываем на оригинальное изображение наиболее сильные 50 дескрипторов и выводим их на экран (Рис. 4).

1  orig_img = imread('C:\hw\card.jpg');
2  orig_img_gray = rgb2gray(orig_img);
3  orig_pts = detectSURFFeatures(orig_img_gray);
4  [orig_features, orig_validPts] = extractFeatures(orig_img_gray,  orig_pts);
5  figure; imshow(orig_img);
6  hold on; plot(orig_pts.selectStrongest(50));
Рис. 4. Карта с выделенными особыми точками

Плюс такой реализации главным образом в наглядности, потому что на каждом шаге мы можем посмотреть, что делает программа, что за ключевые точки она себе выделила, и, таким образом, проконтролировать ход работы. Далее рассмотрим 25 наиболее сильных дескрипторов. Для этого нам потребуется следующий код. Седьмая строка обращается к объекту. Восьмой строкой мы сообщаем Matlab, что в графическом окне нужно будет построить не один объект, а несколько. 5 и 5 – количество объектов по горизонтали и по вертикали, а 3 – номер графического окна, в котором это будет строиться. Далее следует цикл for, который вычисляет 25 кусочков картинки для вывода на экран. Он же задает размеры картинок и местоположение в графическом окне (Рис.5).

 7  figure;
 8  subplot(5,5,3);
 9  for i=1:25
10  scale = orig_pts(i).Scale;
11  small_images = imcrop(orig_img,[orig_pts(i).Location-10*scale 20*scale 20*scale]);
12  subplot(5,5,i);
13  imshow(small_images);
14  hold on;
15  rectangle('Position',[5*scale 5*scale 10*scale 10*scale],'Curvature',1,'EdgeColor','g');
16  end
Рис. 5. 25 наиболее сильных дескрипторов

Теперь, когда исходное изображение проанализировано, загрузим комбинированную картинку и проделаем с ней те же самые действия, что мы проделывали с картой (Рис.6).

17  backgrd = imread('C:\hw\landscape2.jpg’);
18  Bkg = rgb2gray(backgrd);
19  Bkg_pts = detectSURFFeatures(Bkg);
20  [Bkg_features, Bkg_validPts] = extractFeatures(Bkg, Bkg_pts);
21  figure; imshow(backgrd);
22  hold on; plot(Bkg_pts.selectStrongest(50));

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

Рис. 6. Дескрипторы фонового изображения

Теперь, когда мы имеем дескрипторы обеих картинок, можно определить соответствие между ними. 23 строка находит совпадающие дескрипторы. Далее определяем дескрипторы, у которых есть «пара», на первом изображении, аналогично на втором, и выводим полученные результаты на экран (Рис.7).

23  index_pairs = matchFeatures(orig_features, Bkg_features);
24  orig_matched_pts = orig_validPts(index_pairs(:,1)).Location;
25  Bkg_matched_pts = Bkg_validPts(index_pairs(:,2)).Location;
26  figure, showMatchedFeatures(backgrd, orig_img, Bkg_matched_pts, orig_matched_pts, 'montage');
Рис. 7. Нахождение совпадающих дескрипторов

Здесь отчетливо видны ложные срабатывания. Для удобства я выделила их четкими жирными линиями. Они появились, так как программе показалось, что точки идентичны. Однако в данном случае это не критично, потому что таких точек оказалось всего 4 (Рис.8).

Рис. 8. Выделение ложных срабатываний

Теперь постараемся избавиться от этих ложных срабатываний. Для этого рассчитаем такое геометрическое преобразование, чтобы найденные точки наилучшим образом соответствовали друг другу. Для этого воспользуемся методом под названием RANSAC – Random Sample Consensus. В этом методе рассматриваются различные наборы признаков для поиска наилучшего, находится преобразование, из формирования которого выбрасываются дескрипторы, которые ему не удовлетворяют. 27 строка возвращает 2D пеобразование объекта. Объект gte отображает соответствие между найденными дескрипторами карты и скомпанованной картинки. Команда step строит переходную функцию. Далее сохраняем найденные соответствия и визуализируем полученные данные (Рис.9).

27  gte = vision.GeometricTransformEstimator; 
28  gte.Method = 'Random Sample Consensus (RANSAC)';
29  [tform_matrix, inlierIdx] = step(gte, orig_matched_pts, Bkg_matched_pts);
30  orig_inlier_pts = orig_matched_pts(inlierIdx,:);
31  Bkg_inlier_pts = Bkg_matched_pts(inlierIdx,:);
32  figure;showMatchedFeatures(backgrd, orig_img, Bkg_inlier_pts, orig_inlier_pts, 'montage');
Рис.9. Найденные соответствия после геометрического преобразования RANSAC

Здесь мы видим, что ложных срабатываний больше нет, а самих линий гораздо меньше. Теперь мы можем вычислить углы наклона и выделить найденное изображение.

33 tform = maketform('affine',double(tform_matrix));
34 
35 [width, height,~] = size(orig_img);
36 
37 corners = [0,0;height,0;height,width;0,width];
38 
39 new_corners = tformfwd(tform, corners(:,1),corners(:,2));
40 
41 figure;imshow(backgrd);
42 
43 patch(new_corners(:,1),new_corners(:,2),[0 1 0],'FaceAlpha',0.5);
Рис.10. Выделение найденного изображения

Изображение найдено, победа.

Тестирование на реальном изображении

Теперь рассмотрим другое изображение (Рис.11).

Рис.11. Групповое фото команды по черлидингу МГТУ им. Н.Э.Баумана

Фотография была сделана на телефон при верхнем неравномерном освещении, что говорит о сравнительно низком качестве фотографии. Стоит отметить, что низкое качество фото может существенно повлиять на результаты анализа. В качестве искомого изображения возьмем лицо автора этой статьи (Рис.12).

Рис.12. Искомое изображение

Обработку изображений будем производить той же самой программой, поэтому теперь код и комментарии к нему приводиться не будут. Аналогично с предыдущим экспериментом, подадим на вход программе мое лицо, и посмотрим, какие признаки она сможет выделить (Рис.13).

Рис.13. Искомое изображение с выделенными дескрипторами

Получилось достаточно много признаков, каждый из которых имеет отношение к лицу. Теперь посмотрим на общую фотографию. Наиболее сильные признаки расположены где угодно, но только не на лицах участниц (Рис.14). Тем не менее, не стоит забывать, что здесь показаны только самые яркие дескрипторы. Поэтому, посмотрим, найдет ли программа совпадения (Рис.15).

Рис.14. Дескрипторы на полном изображении
Рис.15. Поиск совпадений

Уже сейчас отчетливо видно, что программа не промахнулась. Более того, в отличие от предыдущего эксперимента, у нас нет ложных срабатываний. На всякий случай проделаем ту же операцию с расчётом геометрического преобразования (Рис.16).

Рис.16. Геометрическое преобразование

Линии расположены довольно плотно, но в целом картинка не изменилась. И теперь выделим искомый объект. Как видно из следующего рисунка, ошибки не произошло.

Рис.17. Эталонное изображение найдено

Тестирование на размытом изображении

Тем не менее, по данным Финогеева А.Г. и Четверговой М.В., которые написали статью «МЕТОДИКА РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ РАНДОМНЫХ ДЕРЕВЬЕВ В СИСТЕМАХ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ РАСШИРЕННОЙ РЕАЛЬНОСТИ», выбранный метод не самым лучшим образом справляется с распознаванием. Далее я приведу таблицу с аналитическим результатом сравнения различных методик распознавания из их работы.

Метод Количество точек Качество распознавания, % Объем требуемой памяти, Мб Время сопоставления, сек
SURF 200 74 0,05 ~0,5-1
SIFT 200 63 0,98 ~0,5-1
RF (base) 200 68 6,1 ~0,4-0,8
RF (extended) 200 88 18,3 ~0,8-1,2
SURF 500 76 0,86 ~0,8-1,3
SIFT 500 78 0,93 ~0,8-1,3
RF (base) 500 80 12,5 ~1-1,5
RF (extended) 500 92 26,7 ~1-2
SURF 1000 75 1,2 ~1-1,2
SIFT 1000 78 1,2 ~1-1,3
RF (base) 1000 82 25,6 ~2
RF (extended) 1000 94 56,9 ~2


Из этой же таблицы отлично видны плюсы этого метода. Даже при большом количестве точек, метод требует сравнительно небольшое количество памяти и в 2-3 раза меньше времени, чем другие методы. Поскольку теперь мы знаем, что приблизительно в 25% случаях образец на изображении не находится, придется поэкспериментировать еще немного, чтобы найти то изображение, которое распознать не удастся. В этот раз в качестве оригинала будем использовать плюшевую игрушку, которую попытаемся распознать на размытой фотографии.

Этапы обработки/изображения Оригинал изображения Фон
Загрузка оригиналов
Рис.18. Эталонное изображение
Рис.19. Фоновое изображение
Поиск особых точек
Рис.20. Особые точки эталонного изображения
Рис.21. Дескрипторы фонового изображения
Результат
Рис.22. Совпадений не найдено

Из таблицы можно видеть, что найти нужную игрушку программе не удалось (Рис.22). Это связано с низкой степенью четкости и контрастности обоих фотографий. В данных условиях выбранный метод показал свою неэффективность.

Область применения

Этот метод может найти широкое применение в биометрической аутентификации. Он быстрый, достаточно надежный, а главное, при отсутствии помех на изображении, показывает высокие результаты. Далее рассмотрим несколько примеров.

Идентификация по радужке глаза

Обоснование идентификации по радужной оболочке. Исследования показывают, что рисунок радужной оболочки глаза человека уникален и не меняется с течением жизни. Даже при изменении цвета радужной оболочки вследствие заболеваний/хирургического вмешательства, рисунок остается неизменным. Кроме того, изображение глаза для проведения процедуры идентификации легко можно получить с помощью обычной цифровой камеры. Идея использования рисунка радужной оболочки глаза в качестве идентификатора появилась еще в 70-80х годах прошлого века. С тех пор множество ученых занимаются исследованиями в этой области. Высокая эффективность такого метода обосновывается количеством степеней случайности рисунка. Рисунок радужки в большой степени случаен, а чем больше степень случайности, тем больше вероятность того, что конкретный рисунок будет уникальным. Математически "случайность" описывается степенью свободы. Исследования показали, что текстура радужки имеет степень свободы равной 250, что гораздо больше степени свободы отпечатков пальцев (35) и изображений лиц (20).

Теперь посмотрим, на сколько SURF-метод применим в данном случае. Результаты представим в виде таблицы для наглядности.

Верное соответствие Неверное соответствие
Образец глаза
Рис.23. Образец радужной оболочки
Рис.24. Образец радужной оболочки
Лицо
Рис.25. Образец лица - оригинал
Рис.26. Образец лица - ложный образ
Характерные точки глаза
Рис.27. Дескрипторы глаза
Рис.28. Дескрипторы глаза
Характерные точки лица
Рис.29. Дескрипторы лица-оригинала
Рис.30. Дескрипторы лица-ложного образа
Соотношение точек
Рис.31. Поиск соответствия между образцом радужной оболочки и лицом-оригиналом
Рис.32. Поиск соответствия между образцом радужной оболочки и ложным образом
Результат
Рис.33. Найденное соответствие
Совпадений не найдено

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

Идентификация одного из близнецов по лицу

Так же актуальной темой является идентификация одного из близнецов. Дело в том, что идентичность взрослых близнецов – это не более чем нежелание нашего мозга замечать между ними разницу. Лицевые мышцы развиваются по-разному, и чем дольше они живут, тем меньше они похожи. Сейчас мы так же сравним двух близнецов и посмотрим, на сколько SURF-метод применим в данном конкретном случае.

Эталонное изображение Общее изображение
Загрузка изображений
Рис.34. Оригинальное изображение -левый близнец
Рис.35. Общее изображение
Особые точки
Рис.36. Дескрипторы оригинального изображения
Рис.37. Дескрипторы общего изображения
Особые точки
Рис.38. Дескрипторы правого близнеца
Рис.39. Дескрипторы общего изображения
Линии соответствия
Рис.40. Поиск одинаковых точек между изображением левого близнеца и общим изображением
Результат
Рис.41. Выделение найденного близнеца

В данном конкретном случае рассматриваемый метод справился с заданием. Безусловно, он не поможет идентифицировать человека по снимку с камеры видео-наблюдения, потому что человек, особенно если он хочет остаться инкогнито, не будет стоять и позировать. Но такой метод вполне может быть применим в качестве системы идентификации для доступа, например, в какие-то здания, лаборатории, архивы и прочие помещения, доступ в которые должны иметь только строго ограниченный круг лиц.

Литература

  1. @fanden. Применение метода SURF в системах контроля и управления доступом на основе биометрических технологий [Электронный ресурс] // Хабрахабр: информ.-справочный портал, 2006-2016. URL: https://habrahabr.ru/post/152679/ (дата обращения 08.05.2016)
  2. Финогеев А.Г.,Четвергова М. В. Методика распознавания изображений на основе рандомных деревьев в системах автоматизированного проектирования расширенной реальности [Электронный ресурс] // Современные проблемы науки и образования: научный журнал, 2005 - 2015. Выпуск №5/2012. URL: http://cyberleninka.ru/article/n/metodika-raspoznavaniya-izobrazheniy-na-osnove-randomnyh-dereviev-v-sistemah-avtomatizirovannogo-proektirovaniya-rasshirennoy (дата обращения 11.05.2016)
  3. Журавель И.М. Image Processing Toolbox - Обработка сигналов и изображений [Электронный ресурс] // Материалы по продуктам MATLAB & Toolboxes: информ.-справочный портал, 2001-2014. URL: http://matlab.exponenta.ru/imageprocess/index.php (дата обращения: 10.05.2016)
  4. The MathWork.Inc MathWorks [Электронный ресурс] // MathWorks: информ.-справочный портал, 1994-2016. URL: http://www.mathworks.com/ (дата обращения: 10.05.2016)
  5. Дегтерева А., Вежневец В. Методы идентификация личности по радужной оболочке глаза [Электронный ресурс] // Компьютерная графика и мультимедиа: сетевой журнал, 2003-2011. URL: http://cgm.computergraphics.ru/content/view/61 (дата обращения 08.05.2016)