Рядом наборы - Near sets

Рисунок 1. Описательно, очень близкие множества

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

Фигура 2. Описательно, минимально около множеств

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

Ближайшие наборы имеют множество применений в таких областях, как топология^[37], обнаружение паттернов и классификация^[50], абстрактная алгебра^[51], математика в информатике^[38], и решение множества проблем на основе человеческого восприятия^{[42][82][47][52][56]} которые возникают в таких областях, как анализ изображений^{[54][14][46][17][18]}, обработка изображений^[40], распознавание лица^[13], этология^[64], а также инженерные и научные проблемы^{[55][64][42][19][17][18]}. С самого начала описательно близкие множества оказались полезными в приложениях топологии.^[37], и визуальное распознавание образов ^[50], охватывающий широкий спектр приложений, включая камуфляж обнаружение микропалеонтология, обнаружение подделки почерка, биомедицинский анализ изображений, поиск изображений на основе содержимого, динамика населения, факторная топология, текстильный дизайн, оформление витрин, и топологическая психология.

В качестве иллюстрации степени описательной близости между двумя наборами рассмотрим пример цветовой модели Генри для различной степени близости между наборами элементов изображения на изображениях (см. например,^[17] §4.3). Две пары овалов на рис. 1 и 2 содержат цветные сегменты. Каждый сегмент на рисунках соответствует классу эквивалентности, где все пиксели в классе имеют похожие описания, т.е., элементы изображения с похожими цветами. Овалы на рис.1 описательно ближе друг к другу, чем овалы на рис.2.

История

Было замечено, что простая концепция близость унифицирует различные концепции топологических структур^[20] поскольку категория Около всех пространств близости и карт, сохраняющих близость, содержит категории Стоп (симметричные топологические пространства и непрерывные отображения^[3]), Прокси (пространства близости и ${displaystyle delta}$-карты^[8][67]), Unif (равномерные пространства и равномерно непрерывные отображения^[81][77]) и Cont (пространства примыкания и карты примыкания^[24]) как встроенные полные подкатегории^[20][59]. Категории ${displaystyle {oldsymbol {varepsilon {ANear}}}}$ и ${displaystyle {oldsymbol {varepsilon {AMer}}}}$ показаны как полные суперкатегории различных хорошо известных категорий, включая категорию ${displaystyle {oldsymbol {sTop}}}$ симметрических топологических пространств и непрерывных отображений, а категория ${displaystyle {oldsymbol {Met ^ {infty}}}}$ расширенных метрических пространств и нерасширяющих отображений. Обозначение ${displaystyle {oldsymbol {A}} hookrightarrow {oldsymbol {B}}}$ читает категория ${displaystyle {oldsymbol {A}}}$ встроен в категорию ${displaystyle {oldsymbol {B}}}$. Категории ${displaystyle {oldsymbol {varepsilon AMer}}}$ и ${displaystyle {oldsymbol {varepsilon ANear}}}$ суперкатегории для множества знакомых категорий^[76] показано на рис. 3. Пусть ${displaystyle {oldsymbol {varepsilon {ANear}}}}$ обозначают категорию всех ${displaystyle varepsilon}$-подойдите к пространствам близости и схваткам, и пусть ${displaystyle {oldsymbol {varepsilon AMer}}}$ обозначают категорию всех ${displaystyle varepsilon}$-приблизиться к меротопическим пространствам и сжатиям.

Рисунок 3. Суперкоты

Среди этих знакомых категорий есть ${displaystyle {oldsymbol {sTop}}}$, симметричная форма ${displaystyle {oldsymbol {Top}}}$ (увидеть категория топологических пространств ), категория с объектами, которые являются топологическими пространствами, и морфизмами, непрерывными отображениями между ними^[1][32]. ${displaystyle {oldsymbol {Met ^ {infty}}}}$ с объектами, которые являются расширенными метрическими пространствами, является подкатегорией ${displaystyle {oldsymbol {varepsilon AP}}}$ (имея объекты ${displaystyle varepsilon}$-пространства подхода и стягивания) (см. также^[57][75]). Позволять ${displaystyle ho _ {X}, ho _ {Y}}$ быть расширенной псевдометрикой на непустых множествах ${displaystyle X, Y}$соответственно. Карта ${displaystyle f: (X, ho _ {X}) longrightarrow (Y, ho _ {Y})}$ является сжатием тогда и только тогда, когда ${displaystyle f: (X, u _ {D_ {ho _ {X}}}) longrightarrow (Y, u _ {D_ {ho _ {Y}}})}$ это сокращение. Для непустых подмножеств ${displaystyle A, корзина 2 ^ {X}}$ , функция расстояния ${displaystyle D_ {ho}: 2 ^ {X} imes 2 ^ {X} longrightarrow [0, infty]}$ определяется

${displaystyle D_ {ho} (A, B) = {egin {case} inf {{ho (a, b): ain A, bin B}}, & {ext {if}} A {ext {and}} B {ext {не пусто}}, infty, & {ext {if}} A {ext {или}} B {ext {пусто}}. end {case}}}$

Таким образом ${displaystyle {oldsymbol {varepsilon}}}$AP встроена как полная подкатегория в ${displaystyle {oldsymbol {varepsilon {ANear}}}}$ функтором ${displaystyle F: {oldsymbol {varepsilon {AP}}} longrightarrow {oldsymbol {varepsilon {ANear}}}}$ определяется ${displaystyle F ((X, ho)) = (X, u _ {D_ {ho}})}$ и ${displaystyle F (f) = f}$. потом ${displaystyle f: (X, ho _ {X}) longrightarrow (Y, ho _ {Y})}$ является сжатием тогда и только тогда, когда ${displaystyle f: (X, u _ {D_ {ho _ {X}}}) longrightarrow (Y, u _ {D_ {ho _ {Y}}})}$ это сокращение. Таким образом ${displaystyle {oldsymbol {varepsilon {AP}}}}$ встроена как полная подкатегория в ${displaystyle {oldsymbol {varepsilon {ANear}}}}$ функтором ${displaystyle F: {oldsymbol {varepsilon {AP}}} longrightarrow {oldsymbol {varepsilon {ANear}}}}$ определяется ${displaystyle F ((X, ho)) = (X, u _ {D_ {ho}})}$ и ${displaystyle F (f) = f.}$ Поскольку категория ${displaystyle {oldsymbol {Met ^ {infty}}}}$ расширенных метрических пространств и нерасширяющих отображений является полной подкатегорией ${displaystyle {oldsymbol {varepsilon {AP}}}}$, следовательно, ${displaystyle {oldsymbol {varepsilon {ANear}}}}$ также является полной суперкатегорией ${displaystyle {oldsymbol {Met ^ {infty}}}}$. Категория ${displaystyle {oldsymbol {varepsilon {ANear}}}}$ топологическая конструкция^[76].

Рисунок 4. Фриджес Рис, 1880-1956

Представления о ближнем и дальнем^[A] в математике можно проследить до работ Иоганн Бенедикт Листинг и Феликс Хаусдорф. Связанные с этим понятия сходства и сходства можно проследить до J.H. Пуанкаре, которые представили наборы подобных ощущений (зарождающиеся классы толерантности), чтобы представить результаты G.T. Эксперименты Фехнера с чувственной чувствительностью^[10] и основу для изучения сходства в репрезентативных пространствах как моделей того, что он назвал физическими континуумами.^[63][60][61]. Элементы физического континуума (ПК) - это наборы ощущений. Понятие ПК и различных репрезентативных пространств (тактильных, визуальных, моторных) было введено Пуанкаре в статье 1894 года о математическом континууме.^[63], статья о космосе и геометрии 1895 г.^[60] и сборник 1902 года по науке и гипотезам^[61] с последующим рядом доработок, например,^[62]. Статьи 1893 и 1895 годов о континуумах (Pt. 1, ch. II), а также репрезентативных пространствах и геометрии (Pt. 2, ch IV) включены в качестве глав в^[61]. Позже Ф. Рисс ввел понятие близости или близости пар множеств в Международный конгресс математиков (ICM) в 1908 году^[65].

В 1960-е гг. Э. К. Зееман введены допуски при моделировании визуального восприятия^[83]. А.Б. Сосинский наблюдал в 1986 г.^[71] что основная идея, лежащая в основе теории пространства толерантности, исходит от Пуанкаре, особенно^[60]. В 2002 г. З. Павлак и Дж. Петерс^[B] рассматривали неформальный подход к восприятию близости физических объектов, таких как снежинки, не ограничиваясь пространственной близостью. В 2006 г. формальный подход к описательной близости объектов рассматривался Дж. Петерсом, А. Сковроном и Я. Степанюком.^[C] в контексте пространств близости^{[39][33][35][21]}. В 2007 г. описательно близкие множества были введены Дж. Петерсом.^[D][E] с последующим введением допуска возле наборов^[41][45]. Недавно изучение дескриптивно близких множеств привело к алгебраическим^[22][51], топологическое пространство и пространство близости^[37] основы таких наборов.

Близость множеств

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

Точная идея близости, «сходства» или «нахождения в пределах допуска» достаточно универсальна, чтобы появиться, вполне естественно, почти в любом математическом контексте (см. например,^[66]). Это особенно естественно в математических приложениях: практические задачи чаще всего связаны с приблизительными исходными данными и требуют только жизнеспособных результатов с допустимым уровнем погрешности.^[71].

Слова около и далеко используются в повседневной жизни, и это было острым предложением Ф. Рис^[65] чтобы эти интуитивные концепции были строгими. Он представил концепцию близости пар множеств на ICM в Риме в 1908 году. Эта концепция полезна для упрощения обучения исчислению и продвинутому исчислению. Например, переход от интуитивного определения непрерывности функции в точке к ее строгому эпсилон-дельта-определению иногда бывает трудно объяснить учителям, а ученикам - понять. Интуитивно непрерывность можно объяснить языком близости, т.е., функция ${displaystyle f: mathbb {R} ightarrow mathbb {R}}$ непрерывно в точке ${displaystyle c}$, при условии баллов ${displaystyle {x}}$ около ${displaystyle c}$ перейти к пунктам ${displaystyle {f (x)}}$ около ${displaystyle f (c)}$. Используя идею Рисса, это определение можно сделать более точным, и его противоположностью является знакомое определение^[4][36].

Обобщение множества пересечений

С пространственной точки зрения близость (она же близость) считается обобщением множества пересечение. Для непересекающихся множеств форма пересечения множеств близости определяется в терминах набора объектов (извлеченных из непересекающихся множеств), которые имеют схожие характеристики в пределах некоторого допуска (см. например, § 3 в^[80]). Например, овалы на рис. 1 считаются близкими друг к другу, поскольку эти овалы содержат пары классов, отображающих похожие (визуально неразличимые) цвета.

Пространство близости Ефремовича

Позволять ${displaystyle X}$ обозначить метрика топологическое пространство который наделен одним или несколькими отношениями близости, и пусть ${displaystyle 2 ^ {X}}$ обозначают совокупность всех подмножеств ${displaystyle X}$. Коллекция ${displaystyle 2 ^ {X}}$ называется набор мощности из ${displaystyle X}$.

Существует много способов определения близости Ефремовича в топологических пространствах (дискретная близость, стандартная близость, метрическая близость, близость Чеха, близость Александрова и близость Фрейденталя). Подробнее см. § 2, стр. 93–94 в^[6]. Основное внимание здесь уделяется стандартная близость на топологическом пространстве. Для ${displaystyle A, Bsubset X}$, ${displaystyle A}$ рядом ${displaystyle B}$ (обозначается ${displaystyle A delta B}$) при условии, что их замыкания разделяют общую точку.

В закрытие подмножества ${displaystyle Ain 2 ^ {X}}$ (обозначается ${displaystyle {mbox {cl}} (A)}$) обычный Куратовски закрытие набора^[F], введенный в § 4, с. 20^[27], определяется

${displaystyle {egin {align} {mbox {cl}} (A) & = left {xin X: D (x, A) = 0ight}, {mbox {where}} D (x, A) & = infleft { d (x, a): ain Aight} .end {выровнено}}}$

т.е. ${displaystyle {mbox {cl}} (A)}$ это множество всех точек ${displaystyle x}$ в ${displaystyle X}$ которые близки к ${displaystyle A}$ (${displaystyle D (x, A)}$ - расстояние Хаусдорфа (см. § 22, с. 128, в^[15]) между ${displaystyle x}$ и набор ${displaystyle A}$ и ${displaystyle d (x, a) = left | x-aight |}$ (стандартное расстояние)). А стандарт отношение близости определяется

${displaystyle delta = left {(A, B) через 2 ^ {X} раза 2 ^ {X}: {mbox {cl}} (A) cap {mbox {cl}} (B) eq emptyset ight}.}$

Каждый раз, когда устанавливается ${displaystyle A}$ и ${displaystyle B}$ не имеют общих точек, наборы далекодруг от друга (обозначены ${displaystyle A {подчеркивание {delta}} B}$).

Следующая EF-близость^[Г] аксиомы пространства даны Юрием Михайловым Смирновым^[67] на основе чего Вадим Арсеньевич Ефремович введен в первой половине 1930-х гг.^[8]. Позволять ${displaystyle A, B, Ein 2 ^ {X}}$.

EF.1

Если набор ${displaystyle A}$ близко к ${displaystyle B}$, тогда ${displaystyle B}$ близко к ${displaystyle A}$.

EF.2

${displaystyle Acup B}$ близко к ${displaystyle E}$, тогда и только тогда, когда хотя бы одно из множеств ${displaystyle A}$ или ${displaystyle B}$ близко к ${displaystyle E}$.

EF.3

Две точки близки тогда и только тогда, когда они являются одной и той же точкой.

EF.4

Все наборы далеко не пустые ${displaystyle emptyset}$.

EF.5

Для любых двух наборов ${displaystyle A}$ и ${displaystyle B}$ которые далеко друг от друга, существует ${displaystyle C, Din 2 ^ {X}}$, ${displaystyle Ccup D = X}$, так что ${displaystyle A}$ далеко от ${displaystyle C}$ и ${displaystyle B}$ далеко от ${displaystyle D}$ (Ефремович-аксиома).

Пара ${displaystyle (X, delta)}$ называется EF-пространство близости. В этом контексте Космос представляет собой набор с некоторой дополнительной структурой. С пространством близости ${displaystyle X}$, структура ${displaystyle X}$ индуцируется соотношением EF-близости ${displaystyle delta}$. В непосредственной близости ${displaystyle X}$, закрытие ${displaystyle A}$ в ${displaystyle X}$ совпадает с пересечением всех замкнутых множеств, содержащих ${displaystyle A}$.

Теорема 1.^[67]

Закрытие любого набора ${displaystyle A}$ в пространстве близости ${displaystyle X}$ это набор точек ${displaystyle xin X}$ которые близки к ${displaystyle A}$.

Визуализация EF-аксиомы

Рисунок 5. Пример описательного отношения EF-близости между множествами ${displaystyle A, B}$, и ${displaystyle C ^ {c}}$

Пусть набор ${displaystyle X}$ будут представлены точками внутри прямоугольной области на рис. 5. Пусть также ${displaystyle A, B}$ - любые два непересекающихся подмножества (т.е. пространственно удаленных друг от друга подмножеств) в ${displaystyle X}$, как показано на рис. 5. Пусть ${displaystyle C ^ {c} = X ackslash C}$ (дополнять из набора ${displaystyle C}$). Затем из аксиомы EF обратите внимание на следующее:

${displaystyle {egin {align} A & {underline {delta}} B, B & subset C, D & = C ^ {c}, X & = Dcup C, A & subset D, {mbox {следовательно, мы можем написать}} A {подчеркивание {дельта}} B и стрелка вправо A {подчеркивание {дельта}} C {mbox {и}} B {подчеркивание {дельта}} D, {mbox {для некоторых}} C, D {mbox {in}} X {mbox {так что}} Ccup D = X.qquad не имеет квадратного конца {выровнено}}}$

Пространство описательной близости

Описательно близкие множества были введены как средство решения проблем классификации и распознавания образов, возникающих из непересекающихся множеств, которые похожи друг на друга.^[44][43]. Недавно связь между ближними множествами в EF-пространствах и близкими множествами в описательных EF-пространствах близости была исследована в^[53][48].

Опять же, пусть ${displaystyle X}$ - метрическое топологическое пространство и пусть ${displaystyle Phi = left {phi _ {1}, dots, phi _ {n} ight}}$ набор тестовых функций, которые представляют особенности каждого ${displaystyle xin X}$. Сделанное здесь предположение ${displaystyle X}$ содержит неабстрактные точки с измеримыми функциями, такими как ориентация градиента. Неабстрактная точка имеет местоположение и особенности, которые можно измерить (см. § 3 в ^[26]).

А функция зонда ${displaystyle phi: Xightarrow mathbb {R}}$ представляет собой особенность точки выборки в ${displaystyle X}$. Отображение ${displaystyle Phi: Xlongrightarrow mathbb {R} ^ {n}}$ определяется ${displaystyle Phi (x) = (phi _ {1} (x), точки, phi _ {n} (x))}$, где ${displaystyle mathbb {R} ^ {n}}$ является n-мерным вещественным евклидовым векторное пространство. ${displaystyle Phi (x)}$ вектор признаков для ${displaystyle x}$, который содержит описание ${displaystyle xin X}$. Например, это приводит к приближенному виду наборов точек изображения в цифровых изображениях.^[48].

Чтобы получить описательное отношение близости (обозначается ${displaystyle delta _ {Phi}}$) сначала выбирается набор пробных функций. Позволять ${displaystyle {mathcal {Q}}: 2 ^ {X} longrightarrow 2 ^ {R ^ {n}}}$ отображение на подмножестве ${displaystyle 2 ^ {X}}$ в подмножество ${displaystyle 2 ^ {R ^ {n}}}$. Например, пусть ${displaystyle A, корзина 2 ^ {X}}$ и ${displaystyle {mathcal {Q}} (A), {mathcal {Q}} (B)}$ обозначают множества описаний точек в ${displaystyle A, B}$соответственно. Это,

${displaystyle {egin {выровнено} {mathcal {Q}} (A) & = left {Phi (a): ain Aight}, {mathcal {Q}} (B) & = left {Phi (b): bin Bight } .end {выровнено}}}$

Выражение ${displaystyle A delta _ {Phi} B}$ читает ${displaystyle A}$ описательно близко ${displaystyle B}$. Так же, ${displaystyle A {подчеркивание {delta}} _ {Phi} B}$ читает ${displaystyle A}$ описательно далек от ${displaystyle B}$. Описательная близость ${displaystyle A}$ и ${displaystyle B}$ определяется

${displaystyle A delta _ {Phi} BLeftrightarrow {mathcal {Q}} ({mbox {cl}} (A)); delta; {mathcal {Q}} ({mbox {cl}} (B)) eq emptyset.}$

В описательное пересечение ${displaystyle mathop {cap} _ {Phi}}$ из ${displaystyle A}$ и ${displaystyle B}$ определяется

${displaystyle A mathop {cap} _ {Phi} B = left {xin Acup B: {mathcal {Q}} (A); delta; {mathcal {Q}} (B) ight}.}.$

Это, ${displaystyle xin Acup B}$ в ${displaystyle A mathop {cap} _ {Phi} B}$, предоставлена ${displaystyle Phi (x) = Phi (a) = Phi (b)}$ для некоторых ${displaystyle ain A, bin B}$. Заметьте, что ${displaystyle A}$ и ${displaystyle B}$ может быть непересекающимся и все же ${displaystyle A mathop {cap} _ {Phi} B}$ может быть непустым. Отношение описательной близости ${displaystyle delta _ {Phi}}$ определяется

${displaystyle delta _ {Phi} = left {(A, B) через 2 ^ {X} время 2 ^ {X}: {mbox {cl}} (A) mathop {cap} _ {Phi} {mbox {cl} } (B) eq emptyset ight}.}$

Каждый раз, когда устанавливается ${displaystyle A}$ и ${displaystyle B}$ не имеют точек с соответствующими описаниями, наборы описательно далеко друг от друга (обозначается ${displaystyle A {подчеркивание {delta}} _ {Phi} B}$).

Бинарное отношение ${displaystyle delta _ {Phi}}$ это описательная EF-близостьпри условии выполнения следующих аксиом для ${displaystyle A, B, Esubset X}$.

dEF.1

Если набор ${displaystyle A}$ описательно близок к ${displaystyle B}$, тогда ${displaystyle B}$ описательно близок к ${displaystyle A}$.

dEF.2

${displaystyle Acup B}$ описательно близок к ${displaystyle E}$, тогда и только тогда, когда хотя бы одно из множеств ${displaystyle A}$ или ${displaystyle B}$ описательно близок к ${displaystyle E}$.

dEF.3

Две точки ${displaystyle x, yin X}$ описательно близки тогда и только тогда, когда описание ${displaystyle x}$ соответствует описанию ${displaystyle y}$.

dEF.4

Все непустые множества описательно далеки от пустого множества ${displaystyle emptyset}$.

dEF.5

Для любых двух наборов ${displaystyle A}$ и ${displaystyle B}$ которые описательно далеки друг от друга, существует ${displaystyle C, Din 2 ^ {X}}$, ${displaystyle Ccup D = X}$, так что ${displaystyle A}$ описательно далек от ${displaystyle C}$ и ${displaystyle B}$ описательно далек от ${displaystyle D}$ (Описательная аксиома Ефремовича).

Пара ${displaystyle (X, delta _ {Phi})}$ называется пространством описательной близости.

Проксимальные пространства отношений

А родственник это не лишенная свободы семья отношений ${displaystyle {mathcal {R}}}$ на непустом множестве ${displaystyle X}$^[72]. Пара ${displaystyle (X, {mathcal {R}})}$ (также обозначается ${displaystyle X ({mathcal {R}})}$) называется пространством отношений. Пространства отношений - естественные обобщения упорядоченных множеств и равномерных пространств.^[73][74]}. С введением семьи отношений близости ${displaystyle {mathcal {R}} _ {delta}}$ на ${displaystyle X}$, получаем проксимальное пространство отношений ${displaystyle (X, {mathcal {R}} _ {delta})}$. Для простоты мы рассматриваем только два отношения близости, а именно близость Ефремовича. ${displaystyle delta}$^[8] и описательная близость ${displaystyle delta _ {Phi}}$ в определении описательный родственник ${displaystyle {mathcal {R}} _ {delta _ {Phi}}}$^[53][48]. Пара ${displaystyle (X, {mathcal {R}} _ {delta _ {Phi}})}$ называется проксимальное пространство отношений ^[49]. В этой работе, ${displaystyle X}$ обозначает метрическое топологическое пространство, наделенное отношениями проксимального отношения. С введением ${displaystyle (X, {mathcal {R}} _ {delta _ {Phi}})}$, традиционное закрытие подмножества (например, ^[9][7]) можно сравнить с более поздним описательным закрытием подмножества.

В проксимальном пространстве отношений ${displaystyle X}$, то описательное закрытие набора ${displaystyle A}$ (обозначается ${displaystyle {mbox {cl}} _ {Phi} (A)}$) определяется

${displaystyle {mbox {cl}} _ {Phi} (A) = left {xin X: {Phi (x)} delta {mathcal {Q}} ({mbox {cl}} (A)) ight}.}$

Это, ${displaystyle xin X}$ находится в описательном закрытии ${displaystyle A}$при условии закрытия ${displaystyle Phi (x)}$ и закрытие ${displaystyle {mathcal {Q}} ({mbox {cl}} (A))}$ иметь хотя бы один общий элемент.

Теорема 2. ^[50]

Описательное закрытие любого набора ${displaystyle A}$ в описательном EF-пространстве близости ${displaystyle (X, {mathcal {R}} _ {delta _ {Phi}})}$ это набор точек ${displaystyle xin X}$ которые описательно близки к ${displaystyle A}$.

Теорема 3. ^[50]

Куратовски закрытие набора ${displaystyle A}$ является подмножеством описательного замыкания ${displaystyle A}$ в описательном EF-пространстве близости.

Теорема 4. ^[49]

Позволять ${displaystyle (X, {mathcal {R}} _ {delta _ {Phi}})}$ быть проксимальным пространством отношения, ${displaystyle Asubset X}$. потом ${displaystyle {mbox {cl}} (A) substeq {mbox {cl}} _ {Phi} (A)}$.

Доказательство

Позволять ${displaystyle Phi (x) in {mathcal {Q}} (Xsetminus {mbox {cl}} (A))}$ такой, что ${displaystyle Phi (x) = Phi (a)}$ для некоторых ${displaystyle ain {mbox {cl}} A}$. Вследствие этого, ${displaystyle Phi (x) в {mathcal {Q}} ({mbox {cl}} _ {Phi} (A))}$. Следовательно, ${displaystyle {mbox {cl}} (A) substeq {mbox {cl}} _ {Phi} (A)}$

В проксимальном пространстве отношений EF-близость ${displaystyle delta}$ приводит к следующим результатам для описательной близости ${displaystyle delta _ {Phi}}$.

Теорема 5. ^[49]

Позволять ${displaystyle (X, {mathcal {R}} _ {delta _ {Phi}})}$ быть проксимальным пространством отношения, ${displaystyle A, B, Csubset X}$. потом

1${displaystyle ^ {circ}}$

${displaystyle A delta B {mbox {implies}} A delta _ {Phi} B}$.

2${displaystyle ^ {circ}}$

${displaystyle (Acup B) delta C {mbox {implies}} (Acup B) delta _ {Phi} C}$.

3${displaystyle ^ {circ}}$

${displaystyle {mbox {cl}} A delta {mbox {cl}} B {mbox {implies}} {mbox {cl}} A delta _ {Phi} {mbox {cl}} B}$.

Доказательство

1${displaystyle ^ {circ}}$

${displaystyle A delta BLeftrightarrow Acap Beq emptyset}$. Для ${displaystyle xin Acap B, Phi (x) in {mathcal {Q}} (A)}$ и ${displaystyle Phi (x) in {mathcal {Q}} (B)}$. Вследствие этого, ${displaystyle A delta _ {Phi} B}$.

${displaystyle 1 ^ {circ} Стрелка вправо 2 ^ {circ}}$

3${displaystyle ^ {circ}}$

${displaystyle {mbox {cl}} A delta {mbox {cl}} B}$ подразумевает, что ${displaystyle {mbox {cl}} A}$ и ${displaystyle {mbox {cl}} A}$ имеют хотя бы одну общую черту. Следовательно, 1${displaystyle ^ {o} Стрелка вправо 3 ^ {o}}$.

${displaystyle qquad missingsquare}$

Описательный ${displaystyle delta}$-окрестности

Рисунок 6. Пример с изображением ${displaystyle delta}$-окрестности

В псевдометрическом проксимальном пространстве отношений ${displaystyle X}$, окрестность точки ${displaystyle xin X}$ (обозначается ${displaystyle N_ {x, varepsilon}}$), для ${displaystyle varepsilon> 0}$, определяется

${displaystyle N_ {x, varepsilon} = left {yin X: d (x, y)$

Интерьер набора ${displaystyle A}$ (обозначается ${displaystyle {mbox {int}} (A)}$) и граница ${displaystyle A}$ (обозначается ${displaystyle {mbox {bdy}} (А)}$) в проксимальном пространстве отношений ${displaystyle X}$ определены

${displaystyle {mbox {int}} (A) = left {xin X: N_ {x, varepsilon} subteq Aight}.}$

${displaystyle {mbox {bdy}} (A) = {mbox {cl}} (A) setminus {mbox {int}} (A).}$

Множество ${displaystyle A}$ имеет естественное сильное включение в комплекте ${displaystyle B}$ связан с ${displaystyle delta}$^[5][6]} (обозначается ${displaystyle A ll _ {delta} B}$), предоставлена ${displaystyle Asubset {mbox {int}} B}$, т.е., ${displaystyle A {подчеркивание {delta}} Xsetminus {mbox {int}} B}$ (${displaystyle A}$ далеко от дополнения ${displaystyle {mbox {int}} B}$). Соответственно, набор ${displaystyle A}$ имеет описательное сильное включение в комплекте ${displaystyle B}$ связан с ${displaystyle delta _ {Phi}}$ (обозначается ${displaystyle A mathop {ll} _ {Phi} B}$), предоставлена ${displaystyle {mathcal {Q}} (A) subset {mathcal {Q}} ({mbox {int}} B)}$, т.е., ${displaystyle A {underline {delta}} _ {Phi} Xsetminus {mbox {int}} B}$ (${displaystyle {mathcal {Q}} (A)}$ далеко от дополнения ${displaystyle {mbox {int}} B}$).

Позволять ${displaystyle mathop {ll} _ {Phi}}$ быть описательным ${displaystyle delta}$-соседство, определяемое

${displaystyle mathop {ll} _ {Phi} = left {(A, B) через 2 ^ {X} раза 2 ^ {X}: {mathcal {Q}} (A) подмножество {mathcal {Q}} ({mbox {int}} B) ight}.}$

Это, ${displaystyle A mathop {ll} _ {Phi} B}$, предоставил описание каждого ${displaystyle ain A}$ содержится в наборе описаний точек ${displaystyle bin {mbox {int}} B}$. Теперь заметьте, что любой ${displaystyle A, B}$ в проксимальном пространстве отношений ${displaystyle X}$ такой, что ${displaystyle A {подчеркивание {delta}} _ {Phi} B}$ не пересекаются ${displaystyle delta _ {Phi}}$-окрестности, т.е.,

${displaystyle A {underline {delta}} _ {Phi} BLeftrightarrow A mathop {ll} _ {Phi} E1, B mathop {ll} _ {Phi} E2, {mbox {for some}} E1, E2subset X {mbox { (См. Рис. 6).}}}$

Теорема 6. ^[50]

Любые два набора, описательно далекие друг от друга, принадлежат непересекающимся описательным ${displaystyle delta _ {Phi}}$-окрестности в описательном пространстве близости ${displaystyle X}$.

Рассмотрение строгого содержания непустого множества в другом наборе приводит к изучению топологий «ударил-промахнулся» и топологии Вейсмана.^[2].

Допуск возле наборов

Позволять ${displaystyle varepsilon}$ быть действительным числом больше нуля. При изучении множеств, которые проксимально близки в пределах некоторого допуска, множество отношений близости ${displaystyle {mathcal {R}} _ {delta _ {Phi}}}$ дополняется псевдометрический отношение близости толерантности (обозначается ${displaystyle delta _ {Phi, varepsilon}}$) определяется

${displaystyle {egin {выровнено} D_ {Phi} (A, B) & = infleft {d (Phi (a), Phi (a)): Phi (a) в {mathcal {Q}} (A), Phi ( а) in {mathcal {Q}} (B) ight}, d (Phi (a), Phi (a)) & = mathop {sum} _ {i = 1} ^ {n} | phi _ {i} (a) -phi _ {i} (b) |, delta _ {Phi, varepsilon} & = left {(A, B) через 2 ^ {X} время 2 ^ {X}: | D ({mbox { cl}} (A), {mbox {cl}} (B)) |$

Позволять ${displaystyle {mathcal {R}} _ {delta _ {Phi, varepsilon}} = {mathcal {R}} _ {delta _ {Phi}} чашка влево {delta _ {Phi, varepsilon} ight}}$. Другими словами, непустое множество, снабженное проксимальным соотношением ${displaystyle {mathcal {R}} _ {delta _ {Phi, varepsilon}}}$ имеет основу структура предоставленный ближайшим родственником ${displaystyle {mathcal {R}} _ {delta _ {Phi}}}$ и обеспечивает основу для изучения толерантности вблизи множеств в ${displaystyle X}$ которые находятся в пределах некоторого допуска. Наборы ${displaystyle A, B}$ в описательном псевдометрическом проксимальном пространстве отношений ${displaystyle (X, {mathcal {R}} _ {delta _ {Phi, varepsilon}})}$ допускаются рядом с множествами (т.е., ${displaystyle A delta _ {Phi, varepsilon} B}$), предоставлена

${displaystyle D_ {Phi} (A, B) <варепсилон.}$

Классы допуска и преклассы

Отношения с теми же формальными свойствами, что и отношения подобия ощущений, рассмотренные Пуанкаре^[62] в наши дни, после Zeeman^[83], называется отношения терпимости. А толерантность ${displaystyle au}$ на съемочной площадке ${displaystyle O}$ это отношение ${displaystyle au substeq O imes O}$ то есть рефлексивно и симметрично. В алгебре термин отношение терпимости также используется в узком смысле для обозначения рефлексивных и симметрических отношений, определенных на вселенных алгебр, которые также совместимы с операциями данной алгебры, т.е., они являются обобщениями конгруэнтных соотношений (см. например,^[12]). Применительно к таким отношениям термин алгебраическая терпимость или срок отношение алгебраической терпимости Отношения транзитивной толерантности являются отношениями эквивалентности. Множество ${displaystyle O}$ вместе с терпимостью ${displaystyle au}$ называется пространство допуска (обозначено ${displaystyle (O, au)}$). Множество ${displaystyle Asubseteq O}$ это ${displaystyle au}$-предкласс (или кратко прекласс когда ${displaystyle au}$ понимается) тогда и только тогда, когда для любого ${displaystyle x, yin A}$, ${displaystyle (x, y) в au}$.

Семейство всех преклассов пространства допусков естественным образом упорядочено по включению множества, и преклассы, максимальные по включению множества, называются ${displaystyle au}$-классы или просто классы, когда ${displaystyle au}$ понимается. Семья всех классов пространства ${displaystyle (O, au)}$ особенно интересен и обозначается ${displaystyle H_ {au} (O)}$. Семья ${displaystyle H_ {au} (O)}$ это покрытие ${displaystyle O}$^[58].

Работа Пуанкаре и Зеемана о подобии предвещает введение близких множеств.^[44][43] и исследования отношений сходства, например,^[79]. В науке и технике толерантность к множествам - это практическое приложение изучения множеств, которые находятся в пределах некоторого допуска. Терпимость ${displaystyle varepsilon in (0, infty]}$ напрямую связано с идеей близости или сходства (т.е., находясь в пределах некоторого допуска) при сравнении объектов. Путем применения подхода Пуанкаре к определению визуальных пространств и подхода Зеемана к отношениям толерантности, основная идея состоит в сравнении объектов, таких как участки изображения внутри цифровых изображений.

Примеры

Простой пример

Следующий простой пример демонстрирует построение классов допуска на основе реальных данных. Рассмотрим 20 объектов в таблице ниже с ${displaystyle | Phi | = 1}$.

Образец системы восприятия

${displaystyle x_ {i}}$	${displaystyle phi (x)}$	${displaystyle x_ {i}}$	${displaystyle phi (x)}$	${displaystyle x_ {i}}$	${displaystyle phi (x)}$	${displaystyle x_ {i}}$	${displaystyle phi (x)}$
${displaystyle x_ {1}}$	.4518	${displaystyle x_ {6}}$	.6943	${displaystyle x_ {11}}$	.4002	${displaystyle x_ {16}}$	.6079
${displaystyle x_ {2}}$	.9166	${displaystyle x_ {7}}$	.9246	${displaystyle x_ {12}}$	.1910	${displaystyle x_ {17}}$	.1869
${displaystyle x_ {3}}$	.1398	${displaystyle x_ {8}}$	.3537	${displaystyle x_ {13}}$	.7476	${displaystyle x_ {18}}$	.8489
${displaystyle x_ {4}}$	.7972	${displaystyle x_ {9}}$	.4722	${displaystyle x_ {14}}$	.4990	${displaystyle x_ {19}}$	.9170
${displaystyle x_ {5}}$	.6281	${displaystyle x_ {10}}$	.4523	${displaystyle x_ {15}}$	.6289	${displaystyle x_ {20}}$	.7143

Пусть отношение терпимости быть определенным как

${displaystyle cong _ {varepsilon} = {(x, y) в O imes O:; parallel Phi (x) -Phi (y) parallel _ {_ {2}} leq varepsilon}}$

Затем, установив ${displaystyle varepsilon = 0,1}$ дает следующие классы допуска:

${displaystyle {egin {align} H_ {cong _ {varepsilon}} (O) = & {{x_ {1}, x_ {8}, x_ {10}, x_ {11}}, {x_ {1}, x_ {9}, x_ {10}, x_ {11}, x_ {14}}, & {x_ {2}, x_ {7}, x_ {18}, x_ {19}}, & {x_ {3 }, x_ {12}, x_ {17}}, & {x_ {4}, x_ {13}, x_ {20}}, {x_ {4}, x_ {18}}, & {x_ {5 }, x_ {6}, x_ {15}, x_ {16}}, {x_ {5}, x_ {6}, x_ {15}, x_ {20}}, & {x_ {6}, x_ { 13}, x_ {20}}}. Конец {выровнено}}}$

Обратите внимание, что каждый объект в классе допуска удовлетворяет условию ${displaystyle parallel Phi (x) -Phi (y) parallel _ {2} leq varepsilon}$, и что почти все объекты входят более чем в один класс. Более того, было бы двадцать классов, если бы использовалось отношение неразличимости, так как нет двух объектов с совпадающими описаниями.

Пример обработки изображения

Рисунок 7. Пример изображений, которые находятся рядом друг с другом. (а) и (б) Изображения из свободно доступного набора LeavesDataset (см. например, www.vision.caltech.edu/archive.html).

В следующем примере представлен пример, основанный на цифровых изображениях. Пусть фрагмент изображения определяется как небольшое подмножество пиксели принадлежащий цифровому изображению, так что пиксели, содержащиеся в фрагменте изображения, образуют квадрат. Тогда пусть множества ${displaystyle X}$ и ${displaystyle Y}$ соответственно представляют собой фрагменты изображений, полученные из двух разных изображений, и пусть ${displaystyle O = {Xcup Y}}$. Наконец, пусть описание объекта дается зеленой составляющей в Цветовая модель RGB. Следующим шагом является поиск всех классов допуска с использованием отношения допуска, определенного в предыдущем примере. Используя эту информацию, можно сформировать классы допусков, содержащие объекты, которые имеют похожие (в пределах некоторого небольшого ${displaystyle varepsilon}$) значения для зеленого компонента в цветовой модели RGB. Кроме того, изображения, которые близки (похожи) друг к другу, должны иметь классы допусков, разделенные между обоими изображениями (вместо классов допусков, содержащихся только в одном из изображений). Например, рисунок, сопровождающий этот пример, показывает подмножество классов допуска, полученных из двух изображений листьев. На этом рисунке каждому классу допуска присвоен отдельный цвет. Как можно видеть, два листа имеют одинаковые классы допуска. Этот пример подчеркивает необходимость измерения степени близости двух множеств.

Мера близости

Позволять ${displaystyle (U, {mathcal {R}} _ {delta _ {Phi, varepsilon}})}$ обозначают конкретное описательное псевдометрическое EF-проксимальное пространство отношений, снабженное отношением близости ${displaystyle delta _ {Phi, varepsilon}}$ и с непустыми подмножествами ${displaystyle X, Инь 2 ^ {U}}$ и с отношением толерантности ${displaystyle cong _ {Phi, varepsilon}}$ определяется набором датчиков ${displaystyle Phi}$ и с ${displaystyle varepsilon in (0, infty]}$, где

Рисунок 8. Примеры степени близости между двумя наборами: (а) высокая степень близости и (б) низкая степень близости.

${displaystyle simeq _ {Phi, varepsilon} = {(x, y) in U imes Umid | Phi (x) -Phi (y) | leq varepsilon}.}.$

Далее, предположим ${displaystyle Z = Xcup Y}$ и разреши ${displaystyle H_ {au _ {Phi, varepsilon}} (Z)}$ обозначим семейство всех классов в пространстве ${displaystyle (Z, simeq _ {Phi, varepsilon})}$.

Позволять ${displaystyle Asubseteq X, Bsubseteq Y}$. Расстояние ${displaystyle D _ {_ {tNM}}: 2 ^ {U} imes 2 ^ {U}: longrightarrow [0, infty]}$ определяется

${displaystyle D _ {_ {tNM}} (X, Y) = {egin {case} 1-tNM (A, B), & {mbox {if}} X {mbox {and}} Y {mbox {не пустые }}, infty, & {mbox {if}} X {mbox {или}} Y {mbox {is empty}}, end {case}}}$

где

${displaystyle tNM (A, B) = {Biggl (} sum _ {Cin H_ {au _ {Phi, varepsilon}} (Z)} | C | {Biggr)} ^ {- 1} cdot sum _ {Cin H_ { au _ {Phi, varepsilon}} (Z)} | C | {frac {min (| Ccap A |, | [Ccap B |)} {max (| Ccap A |, | Ccap B |)}}.}$

Детали, касающиеся ${displaystyle tNM}$ даны в^[14][16][17]. Идея, лежащая в основе ${displaystyle tNM}$ состоит в том, что похожие наборы должны иметь одинаковое количество объектов в каждом классе допуска. Таким образом, для каждого класса допуска, полученного при покрытии ${displaystyle Z = Xcup Y}$, ${displaystyle tNM}$ подсчитывает количество объектов, принадлежащих ${displaystyle X}$ и ${displaystyle Y}$ и принимает соотношение (как правильную долю) их мощностей. Кроме того, каждое соотношение взвешивается по общему размеру класса допуска (таким образом, придается значение более крупным классам), а конечный результат нормализуется путем деления на сумму всех мощностей. Диапазон ${displaystyle tNM}$ находится в интервале [0,1], где значение 1 получается, если наборы эквивалентны (на основе описаний объектов), и значение 0 получается, если у них нет общих описаний.

В качестве примера степени близости между двумя наборами рассмотрим рисунок ниже, на котором каждое изображение состоит из двух наборов объектов, ${displaystyle X}$ и ${displaystyle Y}$. Каждый цвет на рисунках соответствует набору, в котором все объекты в классе имеют одно и то же описание. Идея, лежащая в основе ${displaystyle tNM}$ состоит в том, что близость множеств в системе восприятия основана на мощности классов толерантности, которые они разделяют. Таким образом, наборы в левой части рисунка ближе (более близки) друг к другу с точки зрения их описания, чем наборы в правой части рисунка.

Система оценки и распознавания на близком расстоянии (NEAR)

Рисунок 9. GUI системы NEAR.

Система оценки и распознавания близких множеств (NEAR) - это система, разработанная для демонстрации практического применения теории близких множеств к проблемам оценки сегментации изображений и соответствия изображений. Это было мотивировано потребностью в свободно доступном программном инструменте, который может предоставить результаты для исследований и вызвать интерес к теории почти множеств. В системе реализован многодокументный интерфейс (MDI), в котором каждая отдельная задача обработки выполняется в собственном дочернем фрейме. Объекты (в близком к заданному смысле) в этой системе являются частями изображений обрабатываемых изображений, а функции (функции) зонда - это функции обработки изображений, определенные на этих изображениях. Система была написана на C ++ и была разработана для облегчения добавления новых задач обработки и функций проверки. В настоящее время система выполняет шесть основных задач, а именно: отображение классов эквивалентности и допусков для изображения, выполнение оценки сегментации, измерение близости двух изображений, выполнение поиска изображений на основе содержимого (CBIR) и отображение результатов обработки изображения с использованием специфическая функция датчика.

Система близости

Рисунок 10. Система близости.

Proximity System - это приложение, разработанное для демонстрации основанных на описании топологических подходов к близости и близости в контексте анализа цифровых изображений. Система близости выросла из работ С. Наимпалли и Дж. Петерса по топологическим пространствам. Система Proximity была написана на Java и предназначена для работы в двух разных операционных средах, а именно на смартфонах и планшетах Android, а также на настольных платформах, на которых работает виртуальная машина Java. Что касается среды рабочего стола, Proximity System - это кроссплатформенное приложение Java для систем Windows, OSX и Linux, которое было протестировано в Windows 7 и Debian Linux с использованием среды выполнения Sun Java 6. С точки зрения реализации теоретических подходов, как Android, так и настольные приложения используют одни и те же серверные библиотеки для выполнения вычислений на основе описания, где единственными различиями являются пользовательский интерфейс, а версия Android имеет меньше доступных функций из-за ограничениям на системные ресурсы.

Смотрите также

Заметки

использованная литература