Распознавание геометрических фигур
Часть 1
Содержание
- Описание простой задачи, которую трудно перепоручить компьютеру.
- Два разных подхода к обработке изображений.
- Определение степени сходства геометрических фигур, отличающихся размером и ориентацией на плоскости.
- Определение степени сходства геометрических фигур разной формы.
- Данные численных экспериментов.
- Два способа доказательства эффективности методов распознавания.
- Заключение.
1. Простая задача
Попробуйте объединить в пары схожие объекты.
Знаю, вы легко справились, но для составления программы, которая могла бы вас в этом заменить, сперва надо определиться с понятием “степень сходства фигур разной формы”. Есть идеи? Попутно заметим, что размер фигур или их ориентация на плоскости не играют никакой роли. Действительно, поворачивая квадрат или увеличивая размер квадрата, мы не меняем его форму.
2. Два разных подхода к обработке изображений
Как известно, большинство операций обработки изображений можно выполнять или в пространстве изображений (space domain), или в частотном пространстве (frequency domain). В первом случае мы манипулируем отдельными пикселями, а во втором рассматриваем изображение как двумерную функцию яркости, к которой применили преобразование Фурье. Поскольку далее мы будем использовать исключительно частотное пространство, необходимо заметить следующее: стандартные цветные изображения геометрических фигур на белом фоне вначале будут приведены к “каноническому виду”, т. е. преобразованы в монохромные, сильно уменьшенные в размере и инвертированные. Сохраняя форму фигуры, мы при этом существенно уменьшаем число ненулевых (информативных) пикселей изображения. Магнитуда спектра Фурье такого “канонического изображения” являет собой гладкую функцию.
На рисунке слева дано цветное изображение объекта, затем в центре рисунка этот же объект представлен в каноническом виде, и наконец справа показана низкочастотная часть магнитуды (модуля) спектра Фурье с использованием цветной палитры COLORMAP_HSV.
Основные свойства магнитуды спектра Фурье хорошо известны: она не меняется при смещении объекта, вращается параллельно с ним и пропорционально сжимается при его увеличении. Равенство изображений влечет совпадение их магнитуд, хотя обратное не всегда справедливо.
Замечание. Размер исходного цветного изображения особой роли не играет, но, как правило, мы выбираем [200 x 200] пикселей. Это необходимо, если для тестирования процедур распознавания используются AI Tables (см. ниже).
3. Определение степени сходства геометрических фигур, отличающихся размером и ориентацией на плоскости
Для начала сравним фигуры одной формы, но разного размера и направленности. Пример таких фигур показан ниже вместе с их каноническим представлением.
Заодно покажем магнитуды их спектров.
Поскольку фигура слева меньше правой и повернута относительно нее по часовой стрелке, то, в полном соответствии с основными свойствами спектра, ее магнитуда пропорционально растянута и повернута на тот же угол.
Давайте установим точные численные значения этого преобразования, т. е. масштабный коэффициент (scale) и угол поворота (angle). Для этого найдем координаты нескольких первых локальных максимумов магнитуд (что несложно, учитывая гладкость этих функций) и проведем векторы R1 и R2, идущие от центра к соответствующим друг другу максимумам.
Длина и направление этих векторов всецело определяют искомые параметры. Их использование и результат преобразования показаны ниже.
mat_rotate = cv2.getRotationMatrix2D(center, angle, scale)
image_left_warp = cv2.warpAffine(image_left, mat_rotate, dsize)
Как видим, теперь магнитуды полностью совпали в своей центральной части. Другими словами, в центре мы устранили всякое различие, обусловленное размерами и ориентацией фигур, а любое дополнительное различие в этой области будет следствием неравенства их геометрических форм.
В качестве меры сходства (similarity) двух фигур разной формы мы предлагаем использовать различие между их магнитудами после предложенного выше поворота и масштабирования.
Это различие вычисляется как средняя величина расхождений сравниваемых магнитуд в каждой точке с последующей нормировкой к интервалу [0.0 — 1.0].
Заметим также, что если значения similarity между геометрической фигурой и всеми фигурами определенного класса близки к 1, то мы говорим о принадлежности фигуры к этому классу или о ее распознавании.
Изложенный метод вычисления similarity был назван pnt2, или метод распознавания по двум точкам. Установив pnt2 из PyPI стандартным образом — pip install pnt2, вы полностью готовы к его использованию:
"""
HOW TO USE:
"""
from pathlib import Path
from pnt2 import get_similarity
path_1 = str(Path.cwd() / ‘first_image.png')
path_2 = str(Path.cwd() / ’second_image.png')
similarity = get_similarity(path_1, path_2)
print(f’Similarity = {round(similarity, 7)}’)4. Определение степени сходства геометрических фигур разной формы
Пример таких фигур позаимствуем из нашего рисунка в начале статьи.
А это их представление в частотном пространстве:
Как и прежде, найдем локальные максимумы магнитуд и укажем три из них, соответствующие друг другу: 3 — 8, 8 — 6, 0 — 0.
Аффинное преобразование, которое переводит три точки одного изображения в соответствующие им три точки другого изображения, представлено ниже. Далее показан результат выполнения этого преобразования.
pts_image1 = np.float32([[x1_image1, y1_image1],
[x2_image1, y2_image1],
[x0, x0]])
pts_image2 = np.float32([[x1_image2, y1_image2],
[x2_image2, y2_image2],
[x0, x0]])
mat_affine = cv.getAffineTransform(pts_image1, pts_image2)
image_warp = cv.warpAffine(image_1, mat_affine, dsize)
И снова центральные части практически совпадают.
В качестве еще одной меры сходства двух фигур разной формы мы предлагаем использовать различие между их магнитудами после аффинного преобразования по трем соответствующим друг другу локальным максимумам.
Этот метод вычисления степени сходства (similarity) мы назвали pnt3, или метод распознавания по трем точкам.
"""
HOW TO USE:
"""
from pathlib import Path
from pnt3 import get_similarity
path_1 = str(Path.cwd() / ‘first_image.png')
path_2 = str(Path.cwd() / 'second_image.png')
similarity = get_similarity(path_1, path_2)
print(f’Similarity = {round(similarity, 7)}’)Замечания
А. Исходные тексты pnt2 и pnt3, файлы данных и примеры работы программ проще всего скачать с нашего сайта.
Б. В режиме отладки cfg.debug_mode == True оба пакета иллюстрируют все этапы получения результата. Малая часть этих иллюстраций использована в данной статье.
В. Существуют десять различных определений сходства между плоскими геометрическими фигурами. Какой смысл и далее увеличивать этот длинный список? Ниже мы покажем, как изложенные технологии позволяют справиться с задачами, которые не могли быть решены прежде.
5. Данные численных экспериментов
Первый тип данных (изображения мастей игральных карт) создавался вручную на iPad с помощью программы рисования INKredible, затем полученные рисунки масштабировались к размеру [200 x 200] пикселей.
Второй тип данных (изображения звезд) генерировался пакетом Hand-Drawn Shape Simulation в автоматическом режиме. Это позволяет создавать практически неограниченное число искаженных случайным образом геометрических фигур и делать наши выводы статистически обоснованными.
6. Два способа доказательства эффективности методов распознавания
А. Сортировка AI таблиц
В левой таблице данные первого типа расположены хаотично. Требуется изменить их положение таким образом, чтобы все похожие фигуры находились в общем столбце. На таблице справа показан пример одного из возможных решений.
Заметим, что любая программа сортировки таблиц основана на вычислении степени сходства ее элементов. Таким образом, успех в сортировке свидетельствует об эффективности применяемой процедуры распознавания геометрических фигур.
Подробное обсуждение этой задачи и ее успешное решение для широкого круга данных вы найдете в нашей предыдущей статье — “Замечательные AI-таблицы”. Однако установка новой версии этой программы, install shapes-recognition==3.2.0, дает важное преимущество: теперь вы можете выбирать, какой из двух методов распознавания — pnt2 или pnt3 — применять в каждом конкретном случае.
import shapes_recognition as sr
sr.init()
"""
2 - pnt2, 3 - pnt3, others - random
"""
sr.set_calc_similarity_method(2)
# S E L F - S T U D Y
# ---------------------------------------------
# Get a list of shapes for self-study
list_self_study_in = sr.get_self_study_data('DATA_SELF_STUDY')
# Self-study
list_self_study_out = sr.self_study(list_self_study_in)
# Show self-study result
sr.show_self_study_results(list_self_study_in, list_self_study_out)
# ---------------------------------------------
# R E C O G N I T I O N
# ---------------------------------------------
# Get a list of shapes for recognition
list_recognition = sr.get_recognition_data('DATA_RECOGNITION')
# Recognition
recogn_dictionary = \
sr.recognition(list_self_study_out, list_recognition)
# Show recognition result
sr.show_recognition_results(recogn_dictionary)
# ---------------------------------------------Кроме того, программа стала быстрее и даже на базе pnt2 успешно сортирует изображения, сильно отличающиеся по форме (см. пример с данными второго типа ниже).
Б. Построение и анализ гистограмм
Лучший способ оценки эффективности процедуры распознавания и самое беспристрастное сравнение различных методов распознавания состоит в анализе результатов путем построения гистограмм. Этим мы сейчас и займемся.
В качестве первого примера рассмотрим черные масти игральных карт, уже использованные выше: трефы (clubs) и пики (spades). Список match в своем последнем столбце содержит значения степени сходства (similarity) между изображениями одного и того же класса (трефы сравниваются с трефами, а пики с пиками).
список "match", метод "pnt2"
1 clubs_1.png clubs_2.png 0.56070001
2 clubs_1.png clubs_3.png 0.55136621
3 clubs_1.png clubs_4.png 0.54751737
4 clubs_1.png clubs_5.png 0.55803732
5 clubs_1.png clubs_6.png 0.59316292
6 clubs_2.png clubs_3.png 0.55408618
7 clubs_2.png clubs_4.png 0.54963147
8 clubs_2.png clubs_5.png 0.54132218
9 clubs_2.png clubs_6.png 0.55478911
10 clubs_3.png clubs_4.png 0.60338862
11 clubs_3.png clubs_5.png 0.56295087
12 clubs_3.png clubs_6.png 0.55916441
13 clubs_4.png clubs_5.png 0.56276984
14 clubs_4.png clubs_6.png 0.57363807
15 clubs_5.png clubs_6.png 0.57309041
16 spades_1.png spades_2.png 0.58182963
17 spades_1.png spades_3.png 0.52718553
18 spades_1.png spades_4.png 0.57701902
19 spades_1.png spades_5.png 0.59346156
20 spades_1.png spades_6.png 0.61351867
21 spades_2.png spades_3.png 0.52777798
22 spades_2.png spades_4.png 0.58018384
23 spades_2.png spades_5.png 0.59047866
24 spades_2.png spades_6.png 0.56184697
25 spades_3.png spades_4.png 0.52817713
26 spades_3.png spades_5.png 0.53300819
27 spades_3.png spades_6.png 0.52446784
28 spades_4.png spades_5.png 0.56555371
29 spades_4.png spades_6.png 0.59190648
30 spades_5.png spades_6.png 0.57739733А в списке mismatch приведены значения similarity между изображениями разных классов (все возможные сравнения треф с пиками).
список "mismatch", метод "pnt2"
1 clubs_1.png spades_1.png 0.54192863
2 clubs_1.png spades_2.png 0.53416434
3 clubs_1.png spades_3.png 0.53119831
4 clubs_1.png spades_4.png 0.5379787
5 clubs_1.png spades_5.png 0.5163439
6 clubs_1.png spades_6.png 0.53674907
7 clubs_2.png spades_1.png 0.53659498
8 clubs_2.png spades_2.png 0.54463789
9 clubs_2.png spades_3.png 0.52812881
10 clubs_2.png spades_4.png 0.53527197
11 clubs_2.png spades_5.png 0.51754406
12 clubs_2.png spades_6.png 0.51932797
13 clubs_3.png spades_1.png 0.53340233
14 clubs_3.png spades_2.png 0.51930335
15 clubs_3.png spades_3.png 0.50842647
16 clubs_3.png spades_4.png 0.53139809
17 clubs_3.png spades_5.png 0.50607686
18 clubs_3.png spades_6.png 0.52450555
19 clubs_4.png spades_1.png 0.5169884
20 clubs_4.png spades_2.png 0.52087741
21 clubs_4.png spades_3.png 0.504485
22 clubs_4.png spades_4.png 0.52916215
23 clubs_4.png spades_5.png 0.49581141
24 clubs_4.png spades_6.png 0.51879692
25 clubs_5.png spades_1.png 0.5361981
26 clubs_5.png spades_2.png 0.51875466
27 clubs_5.png spades_3.png 0.51964995
28 clubs_5.png spades_4.png 0.53019745
29 clubs_5.png spades_5.png 0.50247776
30 clubs_5.png spades_6.png 0.52523978
31 clubs_6.png spades_1.png 0.54236326
32 clubs_6.png spades_2.png 0.53349987
33 clubs_6.png spades_3.png 0.53377427
34 clubs_6.png spades_4.png 0.54604526
35 clubs_6.png spades_5.png 0.51578293
36 clubs_6.png spades_6.png 0.53814251Если процедура вычисления similarity адекватно отражает положение дел, то значения similarity в списке match будут, как правило, больше по величине, чем в списке mismatch. Следовательно, гистограмма, построенная на данных первого списка, должна быть смещена вправо относительно другой, построенной на базе второго списка.
Рисунок с заголовком pnt2: Clubs vs. Spades — это графическое представление списков выше. Смещение гистограмм очевидно, что и доказывает полезность метода pnt2 для распознавания фигур разной формы. Но если для тех же данных применить метод pnt3 (рисунок справа), то смещение гистограмм станет еще более выраженным, что говорит о преимуществе pnt3 относительно pnt2.
А как сказывается смена набора данных? Ниже показаны результаты обработки красных мастей — бубен (diamonds) и червей (hearts). Как видим, смещение гистограмм выражено еще больше, но это уже следствие смены данных, а не метода. Здесь мы вправе утверждать, что красные масти отличать друг от друга проще, чем черные.
Рисунки ниже получены на данных второго типа — искаженных звездах. Здесь обрабатывалось по 50 образцов каждого класса, что увеличивает список match до 2450 сравнений, а список mismatch до 2500. Как и прежде, очевидно не только преимущество метода pnt3, но и то, что отличить трехконечные звезды от четырехконечных значительно проще, чем пятиконечные от шестиконечных. В первом случае область перекрытия меньше. Наводит на размышление тот факт, что и нам, людям, гораздо легче отличать звезды с малым числом концов и простую форму бубен от всех остальных карточных мастей.
7. Заключение
Ряд нейробиологов и физиологов зрения, начиная с Campbell and Robson, 1968; Pollen and Lee, 1971; Maffei and Fiorentiny, 1973 и Glezer et al., 1989, предложили рассматривать зрительную кору мозга как частотный анализатор. Другими словами, ими была высказана гипотеза, что обработка зрительной информации выполняется в частотном пространстве. В перечисленных ниже статьях мы последовательно подтверждаем эту точку зрения:
А. New High-Quality Edge Detector — Feb 2, 2022
Одно из самых заметных достижений в экспериментальном исследовании мозга (Нобелевская премия 1981 года) — это обнаружение Д. Хьюбелом и Т. Визелом ориентационно-селективных нейронов (orientation-selective neurons). При этом роль этих нейронов оставалась до конца неясной. Перенеся рассмотрение в частотное пространство, мы выяснили назначение ориентационно-селективных нейронов и на этой основе создали, пожалуй, лучший из существующих методов построения контуров — vc-filter.
Б. Image Processing in the Visual Cortex — Feb 18, 2022
Переход в частотное пространство дал возможность объяснить известные оптические иллюзии (Müller-Lyer illusion, Vertical-horizontal illusion).
В. Данная статья тоже не стала исключением. Она показывает, как легко в частотном пространстве решаются основные задачи распознавания образов. Поскольку магнитуда отражает распределение энергии в плоскости изображения, то похожими мы считаем такие изображения, которые после простых преобразований имеют схожее распределение энергии.
Важность перечисленных выше работ состоит в построении математических моделей интеллекта, инициированных наблюдениями и экспериментами. Мы строго следуем системе, которая доказала свою плодотворность в естественных науках, и рассматриваем зрительную кору как еще одно природное явление наряду с гравитацией и электромагнетизмом.
