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

Если σ очень мала (например, < 1), то сглаживание даст незначительный результат, поскольку весовые коэффициенты всех пикселей, находящихся не в центре, будут очень малыми. Для бо́льшей σ у соседних пикселей весовые коэффициенты при применении схемы взвешенного среднего будут больше, что, в свою очередь, означает, что среднее значение будет сильно стремиться к согласованию с соседями – это будет хорошая оценка значения пикселя, а за счёт размывания исчезнет большая часть шума. Ядро с большой σ приведёт к тому, что вместе с шумом исчезнет и большая часть элементов изображения. Если  слишком мала, то ненулевым будет только один элемент матрицы. Если же σ велика, то k также должно быть большим, иначе не будет учтён вклад пикселей, которые должны входить со значительными весовыми коэффициентами.[4]

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

1.2.2 Нормализация по контрасту  и яркости

 

Известные алгоритмы нормализации обеспечивают выравнивание гистограммы  на изображении, приведение к заданным значениям среднего и дисперсии.

Процесс нормализации яркости строится на базе следующей математической модели изображения, в котором значительную часть поля яркости f(n₁,n₂) занимает пространственно-протяженный объект. Область изображения разбивается на две, соответствующие объекту D₀ и фону D_b: D=D₀ U D_b. Области D можно сопоставить соответствующее эталонное изображение, каждый элемент которого определяется в зависимости от его принадлежности области D₀ или D_b:

                                              (1.1)

При этом модель нормализованного изображения выглядит следующим образом:

                                                            (1.2)

Преобразование  устранения яркостных искажений изображения должно обеспечивать:

- минимизацию некоторого критерия сходства нормализованного изображения в окне с эталонным:

         ,                             (1.3)

где у – вектор признаков, вычисляемых на области изображения  D;

- инвариантность к линейному  яркостному преобразованию изображения:

           ,                               (1.4)

где А, В – параметры  преобразования;

- для эталонного изображения  должно выполняться соотношение:

                                         (1.5)

Построение нормализующего преобразование ведется при использовании  статистических характеристик изображения - среднего и дисперсии 

, ,      (1.6)

где , , , - соответственно, средние значения и дисперсии случайной составляющей на участках фона и объекта;

     ,                                                (1.7) 
где k - доля площади изображения, занимаемая объектом;

      количество элементов в областях и .

Следуя из вышесказанного, определяются оптимальные параметры преобразования:

, .             (1.8)

При использовании данных параметров реализуются два различных алгоритма  нормализации:

- алгоритм МНК (с определением  параметров по методу наименьших  квадратов);

- алгоритм НСД (с нормализацией среднего и дисперсии).

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

Тем не менее, алгоритм НСД широко используется для нормализации изображений.  При этом параметры вычисляются  через оценки среднего и дисперсии. Если пренебречь случайной составляющей на изображении, то параметры преобразования примут вид

                              , ,                                          (1.9)

в которых параметры искажения  можно заменить оценками и средних на фоне и объекте:

                              , .                            (1.10)

Использование полученного преобразования возможно как для глобальной, так и для локальной нормализации изображения. В первом случае формула (2) применяется с постоянными параметрами a и b для всего изображения целиком. При локальной нормализации требование вычислительной эффективности вынуждает в ряде задач использовать дополнительные элементы ускорения процессов расчета параметров.

В частности, для практического применения преобразования (2) используется алгоритм, основанный на одновременном использовании двух скользящих окон, в которых реализуется оценка средних значений яркости на объекте и фоне (НЛК - алгоритм нормализации локального контраста). Одно из окон является основным, и в нем реализуется обработка изображения. Во втором окне вычисляется только сумма значений элементов изображения. Форма этого окна выбирается таким образом, чтобы при центральном расположении объекта в окне, «разность» окон соответствовала фону и использовалась для оценки среднего на фоне.

Алгоритм МНК

Для определения параметров a и b необходимо решить систему линейных уравнений:

 

 

(1.11) 

С учетом система принимает вид:

  (1.12)

Откуда:

,  ,                              (1.13)

где - доля окна, занимаемая объектом.

При этих значениях относительная  величина квадрата отклонения нормализованного изображения от эталонного равна:

,                                                        (1.14)

где - отношение «сигнал/шум» на искаженном изображении.

Расстояние Махаланобиса в этом случае равно:

 

                                                . (1.15)

Алгоритм НСД

Параметры преобразования, обеспечивающие нормализацию среднего и дисперсии  в окне, для упрощенной модели изображения  определяются следующим образом:

,  .                   (1.16)

Относительная величина квадрата отклонения при данных параметрах:

.                                 (1.17)

Расстояние Махаланобиса при этом:

.            (1.18)

Алгоритм НЛК

При использовании алгоритма  нормализации локального контраста  оцениваются параметры:

, .                                                               (1.19)

Показатели эффективности  данного алгоритма выглядят следующим  образом:

, .                                                                 (1.20)

1.2.3 Бинаризация (Метод  Отсу для вычисления порога)

 

Существуют десятки методов  выбор порога. Быстрым и эффективным  методом является метод, придуманный  японским ученым Нобуюки Отсу в 1979 году. В методе Отсу используется гистограмма изображения для расчета порога. Гистограмма (рисунок 1.9) — это набор бинов, каждый из которых характеризуется количеством попаданий в него элементов выборки. Выборка — это пиксели различной яркости, которые являются целыми значениями от 0 до 255.

 

Рисунок 1.9 – Гистограмма серого изображения

 

На гистограмме легко различаются два четко разделяющихся класса. Суть метода Отсу заключается в том, чтобы выставить порог между классами таким образом, чтобы каждый их них был как можно более «плотным». Математически это описывается как сведение к минимизации внутриклассовой дисперсии, которая определяется как взвешенная сумма дисперсий двух классов: В работе Отсу показывается, что минимизация внутриклассовой дисперсии эквивалента максимизации межклассовой дисперсии, которая равна:

                                                             (1.21)

В данной формуле w1 и w2 — вероятности первого и второго классов соответственно.

В работе Отсу показывается, что минимизация внутриклассовой дисперсии эквивалента максимизации межклассовой дисперсии, которая равна:

                                                        (1.22)

В этой формуле a1 и a2 — средние арифметические значения для каждого из классов.

Особенность этой формулы заключается  в том, что w1(t + 1), w2(t + 1), a1(t + 1), a2(t + 1) легко выражаются через предыдущие значения w1(t), w2(t), a1(t), a2(t) (t — текущий порог). Эта особенность позволила добиться разработки быстрого алгоритма:

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

Б) Начиная с порога t = 1, проверяется вся гистограмма, на каждом шаге пересчитывается дисперсия σb(t). Если на каком-то из шагов дисперсия оказалась больше максимума, то обновляется дисперсия и T = t.

В) Искомый порог равен T (рисунок 1.10).[5]

 

Рисунок 1.10 – Расчитанный порог

1.2.4 Выделение контура объекта

 

Простой цепной код впервые предлагался Фрименом. Идея простого цепного кода заключается в том, что для любой связной линии на растре кодируются координаты начального пиксела, а для каждого последующего пиксела цепочки в качестве кода используется его приращение, определяющее переход на один из смежных пикселов (рисунок 1.11а). Поскольку таких смежных пикселов всего 8, то для кодирования каждого пиксела необходимо 3 бита информации. Таким образом, оценка информационной емкости линий на растре – 3 бита на элемент, без учета служебной информации (координат начальной точки и количества пикселов в цепочке, либо признака окончания цепочки). К недостаткам простого цепного кода относятся допустимость возвратных переходов и переходов второго порядка в смежные пикселы, что приводит к эффекту образования пятен на линиях. Более гибкая схема предусматривается дифференциальным цепным кодом (ДЦК), в котором кодируются координаты начального пиксела, следующий пиксел кодируется простым цепным кодом, а для всех последующих пикселов кодируются не приращения, а изменения направления переходов на растре (рисунок 1.11б).

а) цепной код            б) дифференциальный цепной код

Рисунок 1.11 – Цепные коды

 

Если в этой схеме исключаются возвратные переходы и переходы второго порядка в смежные пикселы, а также ортогональные переходы (точки, соответствующие таким пикселам являются особыми концевыми узлами линейных сегментов типа «излом», которые сегментируют линии на отдельные гладкие сегменты), то для кодирования каждого пиксела необходимо три состояния (1,5 бита на элемент).[6]

1.2.5 Нормализация ориентации и  положения изображения проекции объекта

 

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

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

Принцип работы алгоритма  представлен на рисунке 1.12.

Рисунок 1.12. - Алгоритм нормализации пространственного расположения объекта. Исходный объект (а) нахождение двух точек на контуре с максимальной удаленностью (б), самые удаленные точки на одной горизонтали (в) довернутый объект на минимальный оставшийся угол к горизонту (в)

 

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

Вычисление максимальной длины объекта можно произвести по формуле:

                                             (1.23) ,

где и – координаты первой и второй точек.

Для поворота объекта по максимальной длине параллельно оси Х необходимо посчитать угол наклона линии  максимальной длины относительно этой оси. Вычислить угол можно через направляющие векторы этих линий:

                                      (1.24),

где и – направляющие векторы для линии максимальной длины и линии, параллельной оси Х.

Получив угол между направляющими векторами можно поворачивать объект до параллельности с осью Х относительно максимальной длины таким образом, чтобы количество точек контура выше линии максимальной длины было снизу. Затем объект вписывается в минимальный прямоугольник объект, и поворачивается на минимальный оставшийся угол к горизонту так, что стороны описанного прямоугольника становятся параллельными осям X и Y.