Интеллектуальные системы.
Теория и приложения

Аннотация

Метод построения выпуклых линейных оболочек конечного множества точек часто используется в задачах распознавания. В \(n-\)мерном пространстве для этого перебираются \(n\) элементные подмножества точек. Если оставшиеся точки лежат по одну сторону от гиперплоскости, содержащей выбранные точки, то эта гиперплоскость называется гранью. Проверка новой точки на принадлежность выпуклой линейной оболочке сводится к проверке выполнения системы линейных неравенств, образованных гранями.

Предлагается решать огрублённую задачу, когда координаты точек принимают три значения \(0,1,-1\), интерпретируемые как элементы поля из трёх элементов. При этом линейная функция равна нулю в точках, лежащих на гиперплоскости, равна \(1\) с одной стороны от неё, и равна \(-1\) с другой стороны. Проверка принадлежности точки выпуклой линейной оболочке сводится к проверке условий \(S_a(x)\in \{0,\lambda _a\}\) для всех граней \(S_a\) выпуклой линейной оболочки, где значение \(0\) соответствует принадлежности точки гиперплоскости \(S_a\), а \(\lambda _a\) является общим значением линейной формы на точках множества, не принадлежащих \(S_a\). Таким образом, принадлежность новой точки выпуклой линейной оболочке определяется её положением относительно всех граней оболочки.

Ключевые слова: выпуклая линейная оболочка, конечные поля, пространство $E_3^n$, линейные формы, распознавание образов, классификация изображений.