Алгоритм определения расположения и размеров объектов на основе анализа изображений объектов

Для решения многих задач требуется определение расстояния до визуальных объектов, например, в робототехнике, в задачах, связанных с дорожнотранспортными объектами и т.д. В настоящее время существуют устройства [1], реализованные на радарном принципе, заключающемся в вычислении расстояния пройденного сигнала излучения от источника излучения до объекта и обратно до источника излучения. Подобные системы применяются с использованием различных видов излучений: радиоволн, ультразвука, лазерного излучения и т.д. При этом слабой стороной этих систем является зависимость от угла отражаемой поверхности и материала отражающего объекта [1]. По этой причине в некоторых случаях требуется наличие дополнительной установки отражателя на объекте, до которого необходимо определить расстояние. Возможны также искажения сигналов и неточности в результате воздействия других источников излучения или в результате рассеивания сигналов при определённых погодных условиях, например, при дневном свете. Кроме того, для таких систем необходимо наличие постоянного источника излучения.

Цель и методы решения задачи

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

Подобная система в какой-то степени имитирует работу биологического глаза в возможности визуальной оценки расстояния до объекта и размеров объектов с той разницей, что для оценки расстояния до объекта в биологических системах используются предварительно известные знания размеров изображений (предметов, людей и т.д.), а также сложные механизмы распознавания [3 - 7] этих объектов, при этом сама оценка производится путём приблизительного сопоставления и приблизительной оценки дистанций до объектов, тогда как предлагаемый алгоритм определяет результаты достаточно точно на основе использования законов оптики и возможностей вычислительных технологий.

Рис. 1. Формирование изображения на движущемся экране с использованием одной линзы (a); формирование изображения на движущемся экране с использованием двух линз (б)

На рис. 1 a приведён пример формирования набора изображений с использованием одной линзы. Принцип работы заключается в последовательном приближении и удалении экрана или линзы относительно друг друга вдоль оптической оси в некотором заданном диапазоне Δ x . В качестве оптической системы может использоваться и более

сложная система линз, в этом случае изображение будет строиться согласно используемой схеме, пример рис. 1 б . На экране в каждый дискретный момент времени фиксируется и запоминается результат преломлённого через линзу изображения. В итоге, за период времени, необходимый для прохождения пути А х, запоминается массив изображений (кадров) M [di] , размерность которого зависит от величины А х и шага дискретизации времени А t фиксирования одного кадра. Для каждого фиксированного изображения запоминается значение d i , соответствующее значению расстояния от линзы до экрана в момент i- ого фиксирования изображения. Дальнейшее действие будет заключаться в алгоритме программного исследования полученного массива изображения M [di] с целью определения наиболее чётких объектов изображений в массиве изображений M [di].

Расстояния до объекта для случая рис. 1 а определятся на основе формулы отрезков [2] применительно для выпуклой линзы с равными фокусными отрезками:

—-- +     ,

F Di di откуда

D i —

diF di — F

где D_i – расстояния от объекта до линзы для i -го изображения (кадра) массива, F – фокусное расстояние линзы, d_i – расстояние от линзы до изображения i -го кадра массива. Для случая с двумя линзами (рис. 1 б ) значение D определяется путём последовательного применения выражения (1) к каждой линзе. При этом D находится по выражению:

D —

d ₁ F ₁

d i ^— F i

где значение d 1 соответствует расстоянию от первой линзы до изображения первой линзы (рис. 1 б ), определяемое аналогичным образом из формулы отрезков применительно ко второй линзе:

d_L — d 1 —

d ₂ F ₂

d 2 — F 2

d ₁

— d_L

d ₂ F ₂

d ₂ - F ₂

где d L – расстояние между линзами, F 1 , F 2 – фокусные расстояния первой и второй линзы.

При этом если каждому фиксированному изображению из массива M [di] соответствует значение di, то, следовательно, каждому кадру-изображению соответствует определённое по выражениям (1 - 3) значение Di, на расстоянии которого объекты данного изображения будут наиболее чёткими. Исходя из этого, дальнейшие действия заключаются в опреде- лении наиболее чётких объектов изображений из всего массива изображений M [di].

Алгоритм определения чёткого изображения объекта заключается в получении коэффициентов размытости границ объектов изображений ( tn) на основе исследования одной или нескольких строк, столбцов пикселей изображения с шагом дискрити-зации dx . При этом каждый набор пикселей представляется как кривая изменений значений оттенков цветовой палитры. Например, для чёрно-белого изображения на рис. 2 б кривая (рис. 2 а ) отражает изменение значений чёрно-белой палитры изображения для вертикального столбца рис. 2 б (1). В случае цветного изображения таких кривых может быть несколько в зависимости от используемой схемы цветового отображения (RGB, CMYK и т.д.).

¹К tie

Рис. 2. Кривая изменения значений чёрно-белой палитры (а), чёрно-белое изображение с выделенным столбцом 1 (б)

Для каждой полученной кривой выполняется вычисление на предмет определения резких перепадов в цветовых оттенках значений изображений. Для упрощения данной процедуры предварительно выполняется сегментация кривых, алгоритм которой заключается в следующем. Если сегментация кривой начинается с некоторой точки ( х i , y i ), то, начиная с этой точки, вычисляется угол отклонения 9 i в этой точке по выражению (4), при этом смежные с ней точки ( х i- 1 , y i- 1 ) и ( х i+ 1 , y i+ 1 ) представляются как вершины мини-сегментов (рис. 3 а ) смежных точек кривой рис. 2 a , координаты векторов по оси х которых равны шагу dx .

9 i — arctg I        1 — arctg I yi——

V x + i ^— x i )         ( x i ^— x i — 1

Если значение 9 i больше некоторого заданного значения 0 ( 9 i >  0 ), то в этом случае точка ( x i , y i ) принимается как конечная вершина предыдущего сегмента ( s i ) и начальная вершина следующего сегмента ( 5 i+ 1 ). Если же значение 9 i меньше значения 0

( 9 _i <  P ), то в этом случае вычисляется значение 9 i+ 1 аналогичным образом для следующей точки ( х i+ 1 , y i+ 1 ), а значение итогового отклонения 9 определяется как сумма предыдущего и текущего отклонений ( 9 = 9 i + 9 i+ 1 , рис. 3 б) . Процедура выполняется аналогичным образом до тех пор, пока не будет выполнено условие 9 >  р . С целью исключения возможного влияния зашумлённости кривой, например, в результате малой разрешающей способности экрана по отношению к шагу дискретизации dx, необходимо повторить аналогичную процедуру на несколько шагов dx вперёд, даже если условие 9 >  Р выполняется. После выполнения данного условия фиксируется значение вершины нового сегмента. При этом чем меньше значение р , тем более детализированной будет в итоге сегментированная кривая.

Рис. 3. Представление отклонения угла θ (а), определение вершин сегмента (б)

На рис. 4 приведён результат сегментирования кривой для выделенного столбца рис. 2 б (1) с использованием значения р = 30°.

Рис. 4. Сегментация кривой и локализация диапазонов объектов

Локализация наиболее выраженных участков перепадов кривой рис. 4 (1, 2) определяется путём последовательного вычисления коэффициентов размытости границ объектов, представляющих собой максимальные и минимальные значения тангенсов {tnmax, tnmin} (5), определяемых в массиве всех сегментов кривой при условии, что значение перепада dyi превышает некоторое принятое dymin, значение которого, в свою очередь, может определяться по-разному, например, для рис. 4 - как значение среднего перепада dyi по всей кривой.

I dy , I tn max = max l "Г I ,

I dx )

I dy I tn min = ^mm/ I .

^ dxi)

В выражении (5) dy, dx – изменение i– го сегмента по оси y и x, max () , min () – функции, определяющие максимальные и минимальные значения на некотором диапазоне сегментированной кривой.

На рис. 4 (1,2) каждому значению tn max соответствует значение tn min , что в итоге соответствует двум выделенным интервалам объектов по вертикали изображения на рис. 2 б (1). Из двух выделенных интервалов на рис. 4 по выражениям (5) определяется интервал, соответствующий наиболее чёткому изображению объекта. Координаты концов найденного интервала сохраняются.

Для определения границ выделенного объекта по оси X выполняется аналогичная процедура и анализ кривой по горизонтальной составляющей, координата Y которой вычисляется как среднее значение между определёнными границами объекта ( y 1 , y 2 ) рис. 5 б (1).

Y = ( У1 + У 2)/2.

Координаты крайних значений выделенных интервалов по оси X также сохраняются.

К цв

a)

X

б)

Рис. 5. Кривая изменения по оси х (a); выделенные участки изображения (б)

Из рис. 5б можно видеть, что локализация объекта на изображении недостаточно полно охватывает весь объект. Для более целостного выделения объекта выполняется несколько повторных локализа- ций (рис. 6). При этом каждая локализация происходит после сдвига оси Y на некоторый дискретный шаг dxY выполняемого в пределах выделенного диапазона изображения объекта.

Рис. 6. Локализация объекта на одном кадре при разных смещениях оси Y

На рис. 6 приведены примеры локализации объекта с шагом dx Y = 10 пикс. Результатом каждого выделения объекта являются координаты границ выделенной прямоугольной области ( y top,i , y bottom,i , x left,i , x right,i ). По итогам всех выделений выполняется объединение выделенных областей, в результате чего формируется область всего объекта. При этом объединение выделенных областей выполняется путём определения наибольших и наименьших границ выделенных участков объекта:

tn min = –16,066 в пятом кадре определяют наиболее чёткое изображение объекта.

Соответствующее этому изображению M [ d 5 ] значение d 5 будет использовано в выражениях (2, 3) для определения расстояния D до предполагаемого объекта.

Помимо расстояния до объекта, возможно также определить размеры выделенного объекта { H x , H y } [2]. Для случая с использованием одной линзы (рис. 1 а ) значения { H x , H y } определяются как

Dh

H = Tir, Hy =    , didi

где h x , h y – горизонтальные и вертикальные размеры выделенной области объекта изображения; H x , H y – горизонтальные и вертикальные размеры реального объекта. При этом выражения (6) справедливы и для случая смещения объектов относительно оси оптической системы (рис. 8), что подтверждается подобием треугольников Δ BCO , Δ B 1 C 1 O и Δ ABO , Δ A 1 B 1 O (рис. 8) и соответственно пропорциональностью сторон:

BC = BO AO = BO

B1 C1 = B1 O ’ A1 O " B1 O ’ ytop = max(У top,i) , Уктот = min(Уьо«от,i ) ,

откуда

BC = AO

B1 C1 = A1 O ’ xright = max(xngh«,i) , xf = min(Х*^

где y top , y bottom – верхняя и нижняя границы по оси Y ; x left , x right – правая и левая границы по оси X .

Для определения расстояния до объекта выполняется аналогичная процедура для всего массива изображений, при этом с целью ускорения всего процесса вычисления могут ограничиться в пределах выделенного диапазона изображения. На рис. 7а приводится пример из пяти кадров массива в пределах локализованной области рис. 5б объекта изображения. Для приведённых фрагментов графиков сегментированных кривых по оси X рис. 7а наибольшее и наименьшее значение tnmax = 13,431, где значение d1 определяется по выражению (3).

6) t„=l,878   -1,683 2,423        -2,408 3,306        -3,369 5,200       -4,789 13,431      -16,066

Рис. 7. Фрагмент изображения на разных кадрах

равнозначно выражению (6), где BC = H , B 1 C 1 = h , AO = D , A 1 O = d .

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

Dh       ( d L ^- d i ) h 2

H = —L, h = -----— d1

.

В итоге из выражений (7) значения H x и H y определяются как

H = D (dL - dC) hx H = D (dL - Q hy x         d1d2       , y          d1d2

Рис. 8. Смещение объекта относительно центральной оси

Аналогично вычисляются смещения S x , S y объекта относительно оси экрана (рис. 8) по выражениям

S _ DSx  S _ DSy x      di , y      di ,

и для рис. 1 а , и для схемы рис. 1 б по выражениям

_S _ D ( d L - d 1 ) s x S _ D ( d L - d 1 ) s y ^x         d ₁ d ₂       ^{, y}         d ₁ d ₂

где s x , s y – горизонтальные и вертикальные составляющие смещения центра объекта изображения относительно центра изображения, экрана; S x , S y – горизонтальные и вертикальные смещения реального объекта относительно оптической оси. При этом значения s x , s y определяются как

_ xr-ig^htl + xltfft X _ yo>p + ybottom Y sx        2        2 ,sy 2         2 , где X, Y – ширина и высота изображения кадра; xright, xleft , ytop , ybottom – координаты границ выделенной области объекта изображения.

Заключение

Отметим, что выражения (1 - 3), (6 - 10) приведены для случаев с использованием одно- и двухлинзовых оптических систем. При этом увеличение расстояния до объекта потребует увеличения разрешения экрана и, соответственно, уменьшения шага дискретизации кривой (рис. 2 а ) или использования более сложной оптики, в этом случае приведённые выражения (1 - 3), (6 - 10) будут иными, согласно сложности используемых систем.

Для ускорения процедуры вычисления полный анализ изображения может проводиться для отдельно выбранных (основных) кадров с целью выделения всех существующих объектов в пределах видимости оптической системы, на остальных же кадрах анализ может проводиться в тех диапа- зонах, где объекты были уже локализованы. Аналогично в основных кадрах полная сегментация и анализ кривых может проводиться только по одному направлению оси координат, например, по оси Y. Кроме того, для ускорения процесса вычисления возможно проводить слежку за объектами. Это означает, что если объект уже обнаружен, то предположительно в следующий момент времени его место расположения можно определить в некотором диапазоне без необходимости просмотра всего изображения и всего массива кадров.