Распознавание & AI, часть 1

Основы

Photo by charlesdeluvio on Unsplash

Введение

Наша способность к распознаванию просто удивительна. Каким образом мы все, не сговариваясь, узнаём на фото выше собаку? Почему многие убеждены, что это обязательно пудель?

Распознавание — центральное направление в создании искусственного интеллекта (AI), и его главное преимущество — в возможности объективно оценить эффективность предлагаемого решения.

Простая задача, которую сложно поручить компьютеру

Попробуйте объединить в пары похожие объекты.

Рис. 1. Шесть объектов “простой” задачи

Знаю, вы легко справились, но чтобы составить программу, которая могла бы вас заменить, необходимо дать строгое определение понятию “сходство фигур разной формы”. Есть идеи?

Но сперва давайте уточним: а что мы имеем в виду, когда говорим о фигурах, имеющих одинаковую форму? По сути, это означает, что, перемещая одну из фигур и, возможно, по ходу вращая и меняя ее размер, можно достичь полного совпадения с другой фигурой. К примеру, все квадраты имеют одинаковую форму. То же самое относительно окружностей и равносторонних треугольников. А вот прямоугольный и равносторонний треугольники — очевидный пример фигур разной формы.

Два подхода к обработке изображений

Большинство операций обработки изображений можно выполнять или в пространстве изображений (space domain), или в частотном пространстве (frequency domain). В первом случае мы манипулируем отдельными пикселями, а во втором рассматриваем изображение как двумерную функцию яркости, к которой применили преобразование Фурье. Поскольку далее мы будем широко пользоваться частотным пространством, то исходные изображения фигур, как правило, будут приведены к “каноническому виду”, т. е. представлены своим контурным изображением меньшего размера. Полностью сохраняя форму фигуры, мы этим существенно уменьшаем число ненулевых (информативных) пикселей. Такое “каноническое изображение” легко анализировать в частотном пространстве, так как его магнитуда Фурье представляет собой гладкую функцию.

Здесь слева видим исходное изображение объекта, затем в центре рисунка этот же объект представлен в каноническом виде, а справа показана низкочастотная часть магнитуды (модуля) спектра Фурье с использованием цветной палитры COLORMAP_HSV.

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

Определение степени сходства геометрических фигур одинаковой формы, т. е. отличающихся размером и ориентацией на плоскости

Пример таких фигур вместе с их каноническим представлением и магнитудами показан ниже.

Рис. 2. Фигуры одинаковой формы и их магнитуды

Поскольку фигура слева на рис. 2 меньше фигуры справа и повернута относительно нее по часовой стрелке, то, в полном соответствии с основными свойствами спектра, ее магнитуда пропорционально растянута и повернута на тот же угол.

В частотном пространстве легко установить точные значения этого преобразования, т. е. масштабный коэффициент (scale) и угол поворота (angle). Для этого найдем координаты нескольких локальных максимумов обеих магнитуд (что несложно, учитывая гладкость этих функций) и проведем векторы R1 и R2, идущие от центра к соответствующим друг другу максимумам.

Рис. 3. Соответствие локальных максимумов магнитуд: 8 -> 3, 0 -> 0

Длина и направление R1 и R2 всецело определяют искомые параметры scale и angle. Преобразование с их использованием и его результат показаны ниже.

mat_rotate = cv2.getRotationMatrix2D(center, angle, scale)

image_left_warp = cv2.warpAffine(image_left, mat_rotate, dsize)

Рис. 4. Преобразованная магнитуда фигуры слева и магнитуда фигуры справа

Как видим, после поворота на угол angle и масштабирования с коэффициентом scale магнитуды полностью совпали в своей ненулевой, низкочастотной части. Другими словами, здесь мы устранили всякое различие, обусловленное размерами и ориентацией фигур. Поэтому расстояние D между фигурами одинаковой формы можно определить как среднее различие между ненулевыми частями магнитуд после указанного выше поворота и масштабирования. Из-за ошибок вычислений величина D может немного меняться, но при этом всегда оставаясь близкой к нулю.

Еще шире используют понятие степени сходства между фигурами S (similarity), определяемой как S = 1 / (1 + coeff * D), которая для фигур одинаковой формы близка к 1 или 100%.

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

Ниже мы приводим текст программы вычисления сходства двух фигур (рис 2).

import time
from pathlib import Path

from max2.src import cfg_max2
from max2.src.utils import init_directory, remove_directory
from max2.src.set_params import set_params
from max2.src.compare_shapes import compare_shapes

# -------------------------------------------------------------
cfg_max2.image_name = 'loc_left.png'
cfg_max2.templ_name = 'loc_right.png'
# -------------------------------------------------------------

cfg_max2.dir_data = 'IMAGES_DATA_max2'
cfg_max2.dir_debug = 'RESULTS_max2'

cfg_max2.path_image \
    = str(Path.cwd() / cfg_max2.dir_data / cfg_max2.image_name)
cfg_max2.path_templ \
    = str(Path.cwd() / cfg_max2.dir_data / cfg_max2.templ_name)

cfg_max2.debug_mode = True
if cfg_max2.debug_mode:
    init_directory(cfg_max2.dir_debug)
else:
    remove_directory(cfg_max2.dir_debug)

set_params(
    12,        # n_peaks (local maxima)
    100,       # canonical_size = 100 x 100 pixels
    0.333)     # cutoff = 0.333, low-pass filter parameter

begin = time.time()

distance, similarity = compare_shapes(cfg_max2.path_image,
                                      cfg_max2.path_templ)
end = time.time()

print(f'\n{cfg_max2.image_name}   vs.  {cfg_max2.templ_name}'
      f'\ndistance = {distance:.4f}\t similarity = {similarity:.4f}'
      f'\ntime = {(end - begin):.1f} sec')

Рис. 5. Результат работы программы на PyCharm

Определение степени сходства геометрических фигур разной формы

Пример таких фигур позаимствуем из рис. 1 начала статьи.

Рис. 6. Фигуры разной формы и их магнитуды

Снова найдем локальные максимумы обеих магнитуд и укажем три из них, соответствующие друг другу: 2 –> 1, 7 –> 13, 0 –> 0.

Рис. 7. Соответствие локальных максимумов двух магнитуд

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

        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)

Рис. 8. Преобразованная магнитуда фигуры слева и магнитуда фигуры справа

И снова ненулевые части магнитуд практически совпадают.

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

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

Предложенный метод мы назвали max3, или “метод распознавания геометрических фигур по трем локальным максимумам магнитуды”. Соответственно, предыдущий метод, использованный выше при сравнении фигур одинаковой формы, мы назвали max2, или “метод распознавания геометрических фигур по двум локальным максимумам”.

Замечание. При сравнении фигур разной формы max2 работает значительно хуже max3 и применяется лишь тогда, когда текущее расположение локальных максимумов делает невозможным применение перспективного преобразования. К примеру, это часто встречается при распознавании единиц “1” в известном собрании рукописных цифр MNIST Dataset.

Ниже приведена программа вычисления сходства двух сердец рис. 1.

import time
from pathlib import Path

from max3.src import cfg_max3
from max3.src.utils import init_directory, remove_directory
from max3.src.set_params import set_params
from max3.src.compare_shapes import compare_shapes

# -------------------------------------------------------------
cfg_max3.image_name = 'heart_c.png'
cfg_max3.templ_name = 'heart_f.png'
# -------------------------------------------------------------

cfg_max3.dir_data = 'IMAGES_DATA_max3'
cfg_max3.dir_debug = 'RESULTS_max3'

cfg_max3.path_image \
    = str(Path.cwd() / cfg_max3.dir_data / cfg_max3.image_name)
cfg_max3.path_templ \
    = str(Path.cwd() / cfg_max3.dir_data / cfg_max3.templ_name)

cfg_max3.debug_mode = True
if cfg_max3.debug_mode:
    init_directory(cfg_max3.dir_debug)
else:
    remove_directory(cfg_max3.dir_debug)

set_params(
    15,        # n_peaks (local maxima)
    100,       # canonical_size = 100 x 100 pixels
    0.25)      # cutoff = 0.25, low-pass filter parameter

begin = time.time()

distance, similarity = compare_shapes(cfg_max3.path_image,
                                      cfg_max3.path_templ)
end = time.time()

print(f'\n{cfg_max3.image_name}   vs.  {cfg_max3.templ_name}'
      f'\ndistance = {distance:.4f}\t similarity = {similarity:.4f}'
      f'\ntime = {(end - begin):.1f} sec')

Рис. 9. Результат вычисления сходства двух фигур (сердец) разной формы

Решение “простой” задачи

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

Как видим, наиболее похожими (с наибольшей величиной similarity) у нас оказались следующие пары: a-e, b-d и c-f.

Рис. 10. Решение “простой” задачи

Доказательство эффективности

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

Предположим, у вас имеются две группы объектов разного типа — типа А (a1, a2, a3) и типа B (b1, b2, b3). Составим списки MATCH и MISMATCH для последующего вычисления степени сходства между объектами:

MATCH:
a1 - a2
a1 - a3
a2 - a3
b1 - b2
b1 - b3
b2 - b3

MISMATCH:
a1 - b1
a1 - b2
a1 - b3
a2 - b1
a2 - b2
a2 - b3
a3 - b1
a3 - b2
a3 - b3

Как видим, список MATCH составляют пары кандидатов на сравнение одного и того же типа, а, соответственно, в списке MISMATCH все пары составлены из объектов разных типов. Если наша оценка сходства адекватно отражает действительность, то значения сходства между объектами, составляющие пары списка MATCH, будут, как правило, больше по величине, чем у пар объектов списка MISMATCH. Последнее означает, что гистограмма, построенная по результатам сравнений списка MATCH, будет смещена вправо относительно другой гистограммы, построенной на основе списка MISMATCH. Убедимся в этом!

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

При этом количество объектов (звезд) каждого типа мы увеличим до 50, что повлечет увеличение списка MATCH до 2 450 сравниваемых пар и, соответственно, списка MISMATCH — до 2 500.

Ниже приведен результат первого вычислительного эксперимента. Как следует из заголовка, здесь участие принимали четырех- и пятиконечные звезды.

А это результат второго вычислительного эксперимента, с участием пяти- и шестиконечных звезд.

На рисунке выше голубым цветом представлены результаты сравнения объектов разных типов, а оранжевым — объекты одного типа. Как видим, оранжевые гистограммы смещены вправо относительно голубых, т. е. однотипные звезды при сравнении обычно показывают более высокие значения степени сходства. При этом размер области перекрытия гистограмм отражает вероятность ошибки при принятии решений, а при значениях similarity > 0.9 вы надежно распознаёте неизвестную звезду.

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

Замечание

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

Исходный код test-max2 и test-max3 доступен на GitHub. На этапе подготовки тестирования требуется загрузить файлы данных (изображения фигур) в папки _DATA_1 и _DATA_2, а затем последовательно выполнить четыре консольные аппликации, содержащиеся в test-max2 или test-max3:

1_create_batch_files.py — автоматическое создание списков сравниваемых файлов MATCH (match.txt) и MISMATCH (mismatch.txt).

2_calc_max2 или 2_calc_max3 — вычисление степени сходства для каждой пары изображений в файлах match.txt и mismatch.txt.

3_sort_max2 или 3_sort_max3 — сортировка по значениям степени сходства.

4_histogram_max2 или 4_histogram_max3 — создание гистограмм.

Данные для желающих самостоятельно решить “простую” задачу можно скачать здесь, а картинки искаженных звезд, использованных в вычислительных экспериментах, — здесь.

Технологии создания разнообразных геометрических форм посвящена наша статья Hand-Drawn Shape Generation. Эта технология дает возможность сравнивать собственные оригинальные наборы геометрических фигур.