Сенсорные системы, 2020, T. 34, № 2, стр. 131-146

Проективная нормализация изображений

Путем устранения радиальной дисторсии (Kunina et al., 2017) практически любая изображающая оптическая система может быть сведена к ортоскопической оптической системе, т.е. к такой изображающей оптической системе, которая описывается проективной моделью камеры (Шапиро и др., 2013). В рамках проективной модели камеры произвольная плоскость сцены оказывается связана с плоскостью изображения проективным преобразованием.

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

Проективная нормализация активно используется в качестве этапа предобработки изображений при решении различных задач технического зрения, таких как распознавание текстового содержания документов (Зейналов и др., 2009; Болотова и др., 2017; Шемякина и др., 2017; Skoryukina et al., 2018); распознавание автомобильных номеров (Povolotskiy et al., 2017); автоматическое узнавание телевизионной передачи по фотографии экрана телевизора (Skoryukina et al., 2017); детектирование шахматной доски с целью калибровки камеры (Xie Y et al., 2018); детектирование искусственной неровности на дорогах (Arvind et al., 2018); сопоставление контура представленного на изображении объекта с объектом в базе данных (Dubuisson, Jain, 1994; Sim et al., 1999; Orrite, Herrero, 2004; Николаев, 2016; Балицкий и др., 2017; Савчик, Николаев, 2018); томографическая реконструкция: при предобработке томографических проекций перед применением алгоритма реконструкции при использовании спиральной, конусной схемы сканирования (Бузмаков, 2019), спутниковый мониторинг (оценка временной изменчивости температуры поверхности океана, определение скорости передвижения облачных масс и многое другое) (Катаманов, 2007), составление планов и карт местности по результатам аэрофотосъемки (Karpenko et al., 2015; Холопов, 2017) и многих других. Кроме того, проективная нормализация фотографии документа применима для облегчения восприятия ее человеком (Legge et al., 1985).

Обзор геометрических критериев точности проективной нормализации изображений

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

Начнем с введения используемых далее определений и обозначений:

${{I}_{{input}}}$ – входное изображение (рис. 1). Обычно им является фотография.

H – проективное преобразование, задающее идеальную нормализацию изображения ${{I}_{{input}}}$. Далее будем рассматривать только случаи, когда H – единственное. На практике ${\text{H}}$ не известно, но считается известным при тестировании методов ПНИ.

${\hat {H}}$ – проективное преобразование, получаемое методом ПНИ и оценивающее H.

${{I}_{{ideal}}}$ – идеально нормализованное изображение. Формируется в результате применения ${\text{H}}$ к ${{I}_{{input}}}$.

${{I}_{{pract}}}$ – практически нормализованное изображение. Формируется в результате применения ${\hat {H}}$ к ${{I}_{{input}}}$.

${\mathbf{x}}\;\mathop = \limits^{{\text{def}}} \;{{\left[ {\begin{array}{*{20}{c}} {{{x}_{1}}}&{{{x}_{2}}} \end{array}} \right]}^{T}}$– декартовы координаты пикселей на плоскости изображения ${{I}_{{ideal}}}$.

${\mathbf{y}}\;\mathop = \limits^{{\text{def}}} \;{{\left[ {\begin{array}{*{20}{c}} {{{y}_{1}}}&{{{y}_{2}}} \end{array}} \right]}^{T}}$– декартовы координаты пикселей на плоскости изображения ${{I}_{{pract}}}$.

${\text{V}}\;\mathop = \limits^{{\text{def}}} \;{\hat {H}}{{{\text{H}}}^{{ - 1}}}$– остаточное проективное преобразование, для каждой точки сцены переводящее координаты ее образа на изображении ${{I}_{{ideal}}}$ в координаты ее образа на изображении ${{I}_{{pract}}}$: ${\mathbf{y}} = {\text{V}}({\mathbf{x}}).$

${\text{d}}({\mathbf{x}}\,|\,{\text{V}})\;\mathop = \limits^{{\text{def}}} \;{{\left\| {{\mathbf{x}} - {\text{V}}({\mathbf{x}})} \right\|}_{2}}$– невязка координат (Kunina et al., 2016), поточечно характеризующая ошибку ПНИ.

$R \subset {{\mathbb{R}}^{2}}$ – занятое образом целевого объекта сцены (документа, автомобильного номера, здания и другое) множество точек изображения ${{I}_{{ideal}}}$, называемое областью интереса.

$Q\;\mathop = \limits^{{\text{def}}} \;{\text{V}}[R]\;\mathop = \limits^{{\text{def}}} \;\{ {\text{V}}({\mathbf{x}}):{\mathbf{x}} \in R\} $– образ области интереса R на изображении ${{I}_{{pract}}}$.

Перейдем непосредственно к обзору геометрических критериев точности ПНИ:

1. На конкурсе “Smartphone document capture” конференции ICDAR (Zhukovsky et al., 2017) в качестве критерия выбран коэффициент Жаккарда (Jaccard, 1901), который равен площади пересечения множеств Q и R, отнесенной к площади их объединения: ${{K}_{{Jaccard}}}(Q,R)\mathop = \limits^{{\text{def}}} \frac{{S(Q \cap R)}}{{S(Q \cup R)}}.$

2. В работе (Sim et al., 1999) для проективного сопоставления объектов используется метрика Хаус-дорфа, равная наибольшему расстоянию от точек одного множества до соответствующих им ближайших точек второго множества: ${{d}_{{Hausdorff}}}(Q,R)\;\mathop = \limits^{{\text{def}}} $ $\mathop = \limits^{{\text{def}}} \;\max \left\{ {\mathop {\max }\limits_{{\mathbf{y}} \in Q} \mathop {\min }\limits_{{\mathbf{x}} \in R} {{{\left\| {{\mathbf{y}} - {\mathbf{x}}} \right\|}}_{2}},\;\mathop {\max }\limits_{{\mathbf{x}} \in R} \mathop {\min }\limits_{{\mathbf{y}} \in Q} {{{\left\| {{\mathbf{x}} - {\mathbf{y}}} \right\|}}_{2}}} \right\}.$

В статье (Orrite, Herrero, 2004) она используется для проективного выравнивания частично заслоненных контуров, в статье (Jesorsky et al., 2001) – для робастной детекции лиц, в работе (Huttenlocher et al., 1993) – для вычисления близости двух изображений. В ряде работ опубликованы ее модификации (Dubuisson, Jain, 1994; Ефимов, Новиков, 2016).

3. В статье (Притула и др., 2014) для измерения близости двух контуров после проективного выравнивания в задаче проективно-инвариантного распознавания плоских замкнутых контуров применяется расстояние Фреше (Fréchet, 1906), которое определяется следующим образом: $F(Q,R)\;\mathop = \limits^{{\text{def}}} \;\mathop {\inf }\limits_{a,b} \;\mathop {\max }\limits_{t \in [0,1)} \;{{\left\| {\delta Q(a(t)),\delta R(b(t))} \right\|}_{2}},$ где $\delta Q$ и $\delta R$ – непрерывные отображения отрезка [0, 1] в границы множеств Q и R соответственно, $a,\;b$ – непрерывные неубывающие сюръекции отрезка $[0,1]$ в себя (репараметризация). От метрики Хаусдорфа расстояние Фреше отличается тем, что накладывает ограничения на повторное использование точек из Q и R. Этот критерий используется также для вычисления точности сегментации изображений (Березский, Березская, 2015) и точности сопоставления карт (Wei et al., 2013).

4. В задаче автоматической коррекции дисторсии, вызванной кривизной линзы и движением камеры (Hsu, Sawhney, 1998), используется среднеквадратичный критерий: ${{L}_{2}}({\text{V}};R)\;\mathop = \limits^{{\text{def}}} \;\sqrt {\frac{1}{{S(R)}}\int_R {{{{\text{d}}}^{2}}({\mathbf{x}}\,|\,{\text{V}})d{\mathbf{x}}} } ,$ где $S(R)$ – площадь области интереса R. Он же используется для вычисления точности формирования единого изображения при помощи матрицы проекторов (Chen et al., 2002).

5. В работе (Катаманов, 2007) для вычисления точности автоматической привязки, полученной с геостационарного спутника изображений, использовался минимаксный критерий, равный максимальному значению невязки координат на области интереса R: ${{L}_{\infty }}({\text{V}};R)\;\mathop = \limits^{{\text{def}}} \;\mathop {\max }\limits_{{\mathbf{x}} \in R} {\text{ d}}({\mathbf{x}}\,|\,{\text{V}}).$

6. Некоторые критерии предназначены только для случая, когда область интереса R является прямоугольником. Тогда ее искаженный образ Q является четырехугольником. Например, в работах (Rodríguez-Piñeiro et al., 2011; Zhang, He, 2007; Takezawa et al., 2016; Awal et al., 2017) для оценки точности ПНИ используется ошибка в соотношении сторон четырехугольника Q. В работе (Calore et al., 2012) для оценки точности устранения проективных искажений используется угол между противоположными сторонами четырехугольника Q, а в работе (Холопов, 2017) – критерий, равный отношению минимального и максимального углов четырехугольника Q.

Заметим, что все найденные в литературе геометрические критерии точности зависят от ${\hat {H}}$ и H только через . Поэтому точность оценки ${\hat {H}}$ преобразования H можно понимать как близость остаточного преобразования V к тождественному преобразованию I.

Угловой модуль

Для описания абсолютной разницы между углами α и β введем угловой модуль, равный углу между векторами $\left[ {\begin{array}{*{20}{c}} {\cos (\alpha )} \\ {\sin (\alpha )} \end{array}} \right]$ и $\left[ {\begin{array}{*{20}{c}} {\cos (\beta )} \\ {\sin (\beta )} \end{array}} \right]$:

Угловой модуль отличается от обычного модуля тем, что учитывает периодичность углов (рис. 5).

Невязка направлений

Напомним, что остаточное проективное преобразование V для каждой точки сцены переводит координаты ее образа на изображении ${{I}_{{ideal}}}$ в координаты ее образа на изображении ${{I}_{{pract}}}$: ${\mathbf{y}} = {\text{V}}({\mathbf{x}}).$ Сперва рассмотрим случай общего положения, который заключается в том, что матрица Якоби $J({\mathbf{x}})$ преобразования V существует и невырождена в каждой точке выпуклой оболочки области интереса ${\mathbf{x}} \in {\text{Conv}}(R)$. Тогда бесконечно малый вектор, исходящий из точки ${\mathbf{x}} \in {\text{Conv}}(R)$ по направлению α, после преобразования V перейдет в бесконечно малый вектор, исходящий из точки ${\text{V}}({\mathbf{x}})$ по направлению β, которое можно рассчитать по формуле

где ${\text{arctg2}}\left[ {\mathbf{b}} \right]$ – измеренная в радианах ориентация вектора b. Отметим, что различные направления α поворачиваются на разные углы $\langle \beta - \alpha \rangle $. Осуществляя предельный переход, линеаризуем аргумент арктангенса в точке ${\mathbf{x}}$, тогда

Проективное преобразование по определению сохраняет прямые, поэтому вместо бесконечно малых векторов c тем же результатом можно рассматривать произвольные. Таким образом, радиус R в формуле (2) можно не устремлять к нулю, а выбирать его произвольно положительным (рис. 6, г):

Невязкой направлений назовем функцию, которая в каждой точке ${\mathbf{x}} \in {\text{Conv}}(R)$ равняется искажению каждого направления α остаточным преобразованием V:

Примеры графиков Δ для различных x и V можно видеть на рис. 6, 7 и 8. Так как проективное преобразование сохраняет прямые, невязка направлений, как функция от x, не меняется по направлению α. В силу дифференцируемости проективного преобразования невязка направлений имеет период, равный π.

Поточечная максимальная невязка направлений

Известно, что невязки направлений различных типов (скос, поворот) создают сложности при сегментации и распознавании текста (Bezmaternykh et al., 2018). При этом неизвестно случая, чтобы большая невязка по какому-то из направлений не создавала таковых сложностей. Более того, невязки направлений $\Delta ({\mathbf{x}},\alpha \,|\,{\text{V}})$ – функции не произвольные, а всего лишь трехпараметрические – по числу элементов матрицы Якоби (3) без учета масштаба, и большое значение невязки по одному направлению влечет за собой сопоставимые значения по большой части оставшихся направлений. Таким образом, для возникновения сложностей при сегментации и распознавании текста достаточно большой невязки хотя бы по одному из направлений. Поэтому в качестве критерия точности ПНИ в точке мы предлагаем поточечную максимальную невязку направлений:

Примеры графиков ${{\Delta }_{\infty }}$ для различных V можно видеть на рис. 9 и 10.

Максимальная невязка направлений

В качестве скалярного интегрального критерия точности проективной нормализации изображения ${{I}_{{pract}}}$ предлагается максимальная невязка направлений, равная максимальной по области интереса R поточечной максимальной невязке направлений:

Остаточное преобразование V – проективное, а значит, преобразует прямые в прямые. Следовательно, критерий $\Delta _{\infty }^{\infty }$ равняется наибольшему среди углов, на которые преобразование V поворачивает всевозможные прямые ${\mathbf{l}}$, пересекающие область интереса R:

Таким образом, мы построили критерий точности ПНИ, “максимально” чувствительный к невязкам направлений. Напомним, что мотивацией для построения такого критерия послужила недостаточная чувствительность к невязкам направлений критериев, основанных на невязках координат. Однако критерий $\Delta _{\infty }^{\infty }$ сам по себе тем более не может претендовать на связь с качеством последующего распознавания нормализованного изображения, так как равняется строго нулю при сколь угодно большом сдвиге и изотропном масштабировании (рис. 6). Решение этой проблемы авторы видят в комбинированном использовании критерия максимальной невязки направлений $\Delta _{\infty }^{\infty }$ и критерия максимальной невязки координат

ранее исследованного в работе (Konovalenko, Shemiakina, 2018).

Вырожденные случаи

Выше мы рассматривали только случай общего положения, когда матрица Якоби $J({\mathbf{x}})$ преобразования V существует и невырождена в каждой точке x выпуклой оболочки области интереса ${\text{Conv}}(R)$. В этом разделе рассмотрим остальные случаи, которые будем называть вырожденными.

$ \bullet $ Пусть существуют точки ${\text{Conv}}(R)$, в которых не существует матрицы Якоби. Выясним, что это за точки. Параметризуем преобразование V однородной матрицей $V\;\mathop = \limits^{{\text{def}}} \;({{{v}}_{{ij}}}) \in {{\mathbb{R}}^{{3 \times 3}}}$ следующим образом:

Прямую с уравнением ${{{v}}_{{31}}}{{x}_{1}} + {{{v}}_{{32}}}{{x}_{2}} + {{{v}}_{{33}}} = 0$, на которой знаменатель преобразования ${\text{V}}$ обращается в ноль, будем называть горизонтом и обозначать ${{{\mathbf{l}}}_{\infty }} \subset {{\mathbb{R}}^{2}}$. Легко видеть, что матрица Якоби преобразования V существует во всех точках евклидовой плоскости за исключением горизонта: ${{\mathbb{R}}^{2}}{\backslash }{{{\mathbf{l}}}_{\infty }}$. Соответственно поточечная максимальная невязка направлений ${{\Delta }_{\infty }}$ для ${\mathbf{x}} \in {{{\mathbf{l}}}_{\infty }}$ формулой (4) не определяется. Однако оказывается, что ${{\Delta }_{\infty }}$ равняется π всюду по одну из сторон от горизонта. Это объясняется тем, что по “ту” сторону горизонта происходит отражение изображения, а значит, всегда найдется направление, противоположное исходному. Поэтому поточечная максимальная невязка направлений естественно доопределяется:

$ \bullet $ Пусть существуют точки ${\text{Conv}}(R)$, в которых матрица Якоби вырождена. Для проективного преобразования, как и для линейного, вырожденность матрицы Якоби в одной точке влечет ее вырожденность во всех точках. При этом плоскость изображения ${{I}_{{ideal}}}$ схлопывается в прямую или точку. Поточечная максимальная невязка направлений ${{\Delta }_{\infty }}$ в таком случае формулой (4) не определяется и смысла не имеет.

Вычисление поточечной максимальной невязки направлений

Начнем с подзадачи вычисления поточечной максимальной невязки направлений (4):

Если ${\mathbf{x}} \in {{{\mathbf{l}}}_{\infty }}$, то ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}}) = \pi $ по формуле (7). Далее рассмотрим случай ${\mathbf{x}} \notin {{{\mathbf{l}}}_{\infty }}$. Запишем задачу с использованием формулы (3):

Матрица Якоби – константа, обозначим ее $J\;\mathop = \limits^{{\text{def}}} \;J({\mathbf{x}})$. Переменный единичный вектор обозначим ${\mathbf{a}}(\alpha )\;\mathop = \limits^{{\text{def}}} \;\left[ {\begin{array}{*{20}{c}} {\cos (\alpha )} \\ {\sin (\alpha )} \end{array}} \right]$. Кроме того, обозначим ${\mathbf{b}}({\mathbf{a}})\;\mathop = \limits^{{\text{def}}} \;J{\mathbf{a}}$ и $\beta ({\mathbf{b}}){\kern 1pt} \mathop = \limits^{{\text{def}}} {\kern 1pt} {\text{arctg2}}\left[ {\mathbf{b}} \right]$, тогда ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}}){\kern 1pt} {\kern 1pt} = {\kern 1pt} {\kern 1pt} \mathop {\max }\limits_\alpha \langle \beta ({\mathbf{b}}({\mathbf{a}}(\alpha )))\, - \,\alpha \rangle .$

Функция $\langle \beta ({\mathbf{b}}({\mathbf{a}}(\alpha ))) - \alpha \rangle $ может достигать максимума только в двух случаях: если недифференцируемая функция $\langle \bullet \rangle $ (1) равна своему локальному и глобальному максимуму π и если равняется нулю производная ее аргумента. Найдем α, соответствующие каждому из этих случаев.

$ \bullet $ Пусть $\langle \beta ({\mathbf{b}}({\mathbf{a}}(\alpha ))) - \alpha \rangle = \pi .$ Тогда в соответствии с определением $\langle \bullet \rangle $ или рис. 5: $\beta ({\mathbf{b}}({\mathbf{a}}(\alpha ))) - \alpha = \pi + 2\pi n$, $n \in \mathbb{Z}$. Значит, вектор ${\mathbf{b}} = J{\mathbf{a}}$ противонаправлен вектору a: $J{\mathbf{a}} = \lambda {\mathbf{a}}$, $\lambda < 0$. В нашем случае a – это собственные векторы матрицы J, соответствующие ее вещественным отрицательным собственным числам λ. Тогда искомые $\alpha = {\text{arctg2}}\left[ {\mathbf{a}} \right]$ – ориентации таких векторов.

$ \bullet $ Пусть

Возьмем производные:

где поэтому (9) опишем так:

Обозначим $K\;\mathop = \limits^{{\text{def}}} \;({{k}_{{ij}}})\;\mathop = \limits^{{\text{def}}} \;{{J}^{T}}{{M}^{T}}JM - {{J}^{T}}J$, тогда

Решая это квадратное уравнение в вещественных числах, находим значения ${\text{tg}}(\alpha )$, из которых получаем искомые α.

Тогда искомый максимум (8) достигается на одном из значений α, вычисленных выше. Таким образом, получено аналитическое решение задачи вычисления поточечной максимальной невязки направлений ${{\Delta }_{\infty }}$. Сформулируем алгоритм вычисления поточечной максимальной невязки направлений.

Вход: Точка ${\mathbf{x}} = {{\left[ {\begin{array}{*{20}{c}} {{{x}_{1}}}&{{{x}_{2}}} \end{array}} \right]}^{T}}$ изображения ${{I}_{{ideal}}}$ и однородная матрица $({{{v}}_{{ij}}}) \in {{\mathbb{R}}^{{3 \times 3}}}$, определяющая (6) остаточное проективное преобразование V.

Выход: поточечная максимальная невязка направлений ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}})$.

– Если ${{{v}}_{{31}}}{{x}_{1}} + {{{v}}_{{32}}}{{x}_{2}} + {{{v}}_{{33}}} = 0$, то ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}}) = \pi $. Иначе далее.

– Рассчитаем матрицу Якоби J проективного преобразования V в точке x.

– Найдем все собственные векторы $\{ {{{\mathbf{a}}}_{j}}\} _{{j = 1}}^{m}$ матрицы J, соответствующие ее вещественным отрицательным собственным числам.

– Рассчитаем углы ${{\alpha }_{j}} = {\text{arctg2}}[{{{\mathbf{a}}}_{j}}]$.

– Рассчитаем матрицу $({{k}_{{ij}}}) = {{J}^{T}}{{M}^{T}}JM - {{J}^{T}}J$, где $M = \left[ {\begin{array}{*{20}{c}} 0&{ - 1} \\ 1&0 \end{array}} \right]$.

– Найдем все вещественные корни $\{ {{t}_{i}}\} _{{i = 1}}^{n}$ квадратного уравнения

– Рассчитаем углы $\alpha _{i}^{'} = {\text{arctg}}[{{t}_{i}}]$.

– Сформируем набор углов $A = \{ \{ {{\alpha }_{j}}\} _{{j = 1}}^{m},\{ {{\alpha '}_{i}}\} _{{i = 1}}^{n}\} $.

– Рассчитаем поточечную максимальную невязку направлений:

Вычисление максимальной невязки направлений

Теперь перейдем непосредственно к задаче вычисления максимальной невязки направлений (5): $\Delta _{\infty }^{\infty }({\text{V}};R) = \mathop {\max }\limits_{{\mathbf{x}} \in R} {\text{ }}{{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}}).$

Проведенные авторами численные эксперименты позволяют выдвинуть гипотезу о том, что поточечная максимальная невязка направлений ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}})$ проективного преобразования – квазивыпуклая функция (рис. 9 и 10). Примем эту гипотезу и допустим, что область интереса R – ограниченное и замкнутое множество. Тогда, в соответствии с теоремой 2 (Приложение), супремум ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}})$ на R равен супремуму на крайних точках выпуклой оболочки R:

Легко видеть, что функция ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}})$ непрерывна, поэтому по теореме Вейерштрасса имеем $\mathop {\max }\limits_{{\mathbf{x}} \in R} {\text{ }}{{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}}) = \mathop {\max }\limits_{{\mathbf{x}} \in {\text{E}}({\text{Conv}}(R))} {{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}}),$ тогда $\Delta _{\infty }^{\infty }({\text{V}};R) = \mathop {\max }\limits_{{\mathbf{x}} \in {\text{E}}({\text{Conv}}(R))} {{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}}),$ что во многих случаях существенно упрощает вычисление $\Delta _{\infty }^{\infty }$. Рассмотрим основной для нашего практического приложения частный случай, когда область интереса R состоит из многоугольников, т.е. является полиэдром. Выпуклая оболочка полиэдра – выпуклый многогранник, а в нашем плоском случае – выпуклый многоугольник. Крайние точки выпуклого многоугольника – его вершины. Значит, максимальную невязку направлений достаточно искать среди вершин $\{ {{{\mathbf{x}}}_{i}}\} _{{i = 1}}^{n}$ многоугольника, являющегося выпуклой оболочкой R (рис. 11):

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

Вход: остаточное проективное преобразование V, полиэдральная область интереса R.

Выход: максимальная невязка направлений $\Delta _{\infty }^{\infty }({\text{V}};R)$.

– Найдем вершины многоугольника, являющегося выпуклой оболочкой R: $\{ {{{\mathbf{x}}}_{i}}\} _{{i = 1}}^{n} = {\text{E}}({\text{Conv}}(R)).$

– Используя алгоритм вычисления ${{\Delta }_{\infty }}({\mathbf{x}}\,|\,{\text{V}})$, вычислим максимальную невязку направлений: $\Delta _{\infty }^{\infty }({\text{V}};R) = \mathop {\max }\limits_i {{\Delta }_{\infty }}({{{\mathbf{x}}}_{i}}\,|\,{\text{V}}).$