Функция размера - Size function

Функции размера являются дескрипторами формы в геометрическом / топологическом смысле. Это функции из полуплоскости ${displaystyle x$ к натуральным числам, считая некоторые компоненты связности топологическое пространство. Они используются в распознавание образов и топология.

Формальное определение

В теория размеров, то функция размера ${displaystyle ell _ {(M, varphi)}: Delta ^ {+} = {(x, y) в mathbb {R} ^ {2}: x$ связанный с пара размеров ${displaystyle (M, varphi: M o mathbb {R})}$ определяется следующим образом. Для каждого ${displaystyle (x, y) в дельте ^ {+}}$ , ${displaystyle ell _ {(M, varphi)} (x, y)}$ равно количеству связных компонент множества ${displaystyle {pin M: varphi (p) leq y}}$ которые содержат хотя бы одну точку, в которой функция измерения (а непрерывная функция из топологическое пространство ${displaystyle M}$ к ${displaystyle mathbb {R} ^ {k}}$ ^[1]^[2]) ${displaystyle varphi}$ принимает значение меньше или равное ${displaystyle x}$ .^[3]Концепция функции размера может быть легко расширена на случай функции измерения. ${displaystyle varphi: M o mathbb {R} ^ {k}}$ , куда ${displaystyle mathbb {R} ^ {k}}$ наделен обычным частичным порядком.^[4] Обзор функций размера (и теория размеров ) можно найти в.^[5]

Пример функции размера. (A) Размер пары ${displaystyle (M, varphi: M o mathbb {R})}$ , куда ${displaystyle M}$ это синяя кривая и ${displaystyle varphi: M o mathbb {R}}$ - функция высоты. (B) Множество ${displaystyle {pin M: varphi (p) leq b}}$ изображен зеленым цветом. (C) Множество точек, в которых функция измерения ${displaystyle varphi}$ принимает значение меньше или равное ${displaystyle a}$ , то есть, ${displaystyle {pin M: varphi (p) leq a}}$ , изображен красным. (D) Две связные компоненты множества ${displaystyle {pin M: varphi (p) leq b}}$ содержать хотя бы одну точку в ${displaystyle {pin M: varphi (p) leq a}}$ , то есть хотя бы одну точку, где функция измерения ${displaystyle varphi}$ принимает значение меньше или равное ${displaystyle a}$ . (E) Значение функции размера ${displaystyle ell _ {(M, varphi)}}$ в точке ${displaystyle (a, b)}$ равно ${displaystyle 2}$ .

История и приложения

Функции размера были введены в^[6]для частного случая ${displaystyle M}$ равны топологическому пространству всех кусочно ${displaystyle C ^ {1}}$ закрытые пути в ${displaystyle C ^ {infty}}$ закрытый коллектор вложен в евклидово пространство. Здесь топология на ${displaystyle M}$ индуцируется ${displaystyle C ^ {0}}$ -норма, а функция измерения ${displaystyle varphi}$ идет по каждому пути ${displaystyle gamma в M}$ на его длину.^[7]случай ${displaystyle M}$ равны топологическому пространству всех упорядоченных ${displaystyle k}$ -наборы точек в подмногообразии евклидова пространства. Здесь топология на ${displaystyle M}$ индуцирована метрикой ${displaystyle d ((P_ {1}, ldots, P_ {k}), (Q_ {1} ldots, Q_ {k})) = max _ {1leq ileq k} | P_ {i} -Q_ {i} | }$ .

Расширение концепции функции размера на алгебраическая топология был сделан в^[2]где концепция размер гомотопической группы был представлен. Здесь функции измерения принимая ценности в ${displaystyle mathbb {R} ^ {k}}$ разрешены. теория гомологии (в функтор размера ) был введен в.^[8]Концепции размер гомотопической группы и функтор размера строго связаны с концепцией стойкая группа гомологии^[9]учился в стойкая гомология. Стоит отметить, что функция размера - это ранг ${displaystyle 0}$ -я стойкая группа гомологий, в то время как связь между стойкой группой гомологий и гомотопической группой размера аналогична той, которая существует между группы гомологии и гомотопические группы.

Функции размера были первоначально введены как математический инструмент для сравнения форм в компьютерное зрение и распознавание образов, и составили семя теория размеров^[3]^[10]^[11]^[12]^[13]^[14]^[15]^[16].^[17]Главное, что размерные функции инвариантны для каждого преобразования, сохраняя функция измерения. Следовательно, их можно адаптировать ко многим различным приложениям, просто изменив функция измерения чтобы получить желаемую инвариантность. Более того, размерные функции показывают свойства относительной устойчивости к шуму в зависимости от того, что они распределяют информацию по всей полуплоскости. ${displaystyle Delta ^ {+}}$ .

Основные свойства

Предположить, что ${displaystyle M}$ компактное локально связное хаусдорфово пространство. Имеют место следующие утверждения:

функция любого размера ${displaystyle ell _ {(M, varphi)} (x, y)}$ это неубывающая функция в переменной ${displaystyle x}$ и невозрастающая функция в переменной ${displaystyle y}$ .

функция любого размера ${displaystyle ell _ {(M, varphi)} (x, y)}$ локально константа справа по обеим переменным.

для каждого ${displaystyle x$ , ${displaystyle ell _ {(M, varphi)} (x, y)}$ конечно.

для каждого ${displaystyle x$ и каждый ${displaystyle y> x}$ , ${displaystyle ell _ {(M, varphi)} (x, y) = 0}$ .

для каждого ${displaystyle ygeq max varphi}$ и каждый ${displaystyle x$ , ${displaystyle ell _ {(M, varphi)} (x, y)}$ равно количеству связанных компонентов ${displaystyle M}$ на котором минимальное значение ${displaystyle varphi}$ меньше или равно ${displaystyle x}$ .

Если мы также предположим, что ${displaystyle M}$ гладкий закрытый коллектор и ${displaystyle varphi}$ это ${displaystyle C ^ {1}}$ -функции имеет место следующее полезное свойство:

для того, чтобы ${displaystyle (x, y)}$ является точкой разрыва для ${displaystyle ell _ {(M, varphi)}}$ необходимо, чтобы либо ${displaystyle x}$ или же ${displaystyle y}$ или оба являются критическими значениями для ${displaystyle varphi}$

.^[18]

Сильная связь между концепцией размерной функции и концепцией естественная псевдодистантность ${displaystyle d ((M, varphi), (N, psi))}$ между парами размеров ${displaystyle (M, varphi), (N, psi)}$ существуют^[1]^[19]

если ${displaystyle ell _ {(N, psi)} ({ar {x}}, {ar {y}})> ell _ {(M, varphi)} ({ilde {x}}, {ilde {y}} )}$ тогда ${displaystyle d ((M, varphi), (N, psi)) geq min {{ilde {x}} - {ar {x}}, {ar {y}} - {ilde {y}}}}$ .

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

Представление формальным рядом

Алгебраическое представление размерных функций в терминах наборов точек и прямых на реальной плоскости с множественностями, то есть в виде конкретных формальных рядов, было представлено в^[1]^[20].^[21]Точки (называемые угловые точки) и линии (называемые угловые) таких формальных рядов кодируют информацию о разрывах соответствующих функций размера, а их кратности содержат информацию о значениях, принимаемых функцией размера.

Формально:

угловые точки определяются как эти точки ${displaystyle p = (x, y)}$ , с ${displaystyle x$ , такое что число

${displaystyle mu (p) {stackrel {m {def}} {=}} min _ {alpha> 0, eta> 0} ell _ {({M}, varphi)} (x + alpha, y- eta) - ell _ {({M}, varphi)} (x + alpha, y + eta) -ell _ {({M}, varphi)} (x-alpha, y- eta) + ell _ {({M}, varphi )} (x-альфа, y + eta)}$ положительное число. ${displaystyle mu (p)}$ считается множественность из ${displaystyle p}$ .

угловые и определяются как эти строки ${displaystyle r: x = k}$ такой, что

${displaystyle mu (r) {stackrel {m {def}} {=}} min _ {alpha> 0, k + alpha 0.}$ Номер ${displaystyle mu (r)}$ грустно быть множественность из ${displaystyle r}$ .

Теорема представления: Для каждого ${displaystyle {ar {x}} <{ar {y}}}$ , он держит ${displaystyle ell _ {({M}, varphi)} ({ar {x}}, {ar {y}}) = sum _ {p = (x, y) на вершине xleq {ar {x}}, y> {ar {y}}} mu {ig (} p {ig)} + sum _ {r: x = k atop kleq {ar {x}}} mu {ig (} r {ig)}}$

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

Этот алгебраический подход к функциям размера приводит к определению новых мер подобия между формами, переводя проблему сравнения функций размера в проблему сравнения формальных рядов. Наиболее изученным среди этих показателей функции размера является расстояние согласования.^[3]

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

[FroLa99-1] а ^б ^c Патрицио Фрозини и Клаудиа Ланди, Теория размеров как топологический инструмент компьютерного зрения, Распознавание образов и анализ изображений, 9 (4): 596–603, 1999.

[FroMu99-2] а ^б Патрицио Фрозини и Микеле Мулаццани, Гомотопические группы размера для вычисления расстояний естественного размера, Бюллетень Бельгийского математического общества, 6:455–464 1999.

[dAFrLa06-3] а ^б ^c Микеле д'Амико, Патрицио Фрозини и Клаудиа Ланди, Использование расстояния совпадения в теории размеров: обзор, Международный журнал систем и технологий обработки изображений, 16 (5): 154–161, 2006 г.

[BiCeFr08-4] Сильвия Биазотти, Андреа Черри, Патрицио Фрозини, Клаудиа Ланди, Функции многомерного размера для сравнения форм, Journal of Mathematical Imaging and Vision 32: 161–179, 2008.

[BiDeFa08-5] Сильвия Биазотти, Лейла Де Флориани, Бьянка Фальцидиено, Патрицио Фрозини, Даниэла Джорджи, Клаудиа Ланди, Лаура Папалео, Микела Спаньоло,Описание форм с помощью геометрическо-топологических свойств вещественных функцийACM Computing Surveys, vol. 40 (2008), п. 4, 12: 1–12: 87.

[Fro90-6] Патрицио Фрозини, Расстояние для классов подобия подмногообразий евклидова пространства, Бюллетень Австралийского математического общества, 42 (3): 407–416, 1990.

[Fro91-7] Патрицио Фрозини, Измерение форм по функциям размера, Proc. SPIE, Интеллектуальные роботы и компьютерное зрение X: алгоритмы и методы, Бостон, Массачусетс, 1607: 122–133, 1991.

[CaFePo01-8] Франческа Кальяри, Массимо Ферри и Паола Поцци, Функции размера с категориальной точки зрения, Acta Applicandae Mathematicae, 67 (3): 225–235, 2001.

[EdLeZo02-9] Герберт Эдельсбруннер, Дэвид Летчер и Афра Зомородян, Топологическая устойчивость и упрощение, Дискретная и вычислительная геометрия, 28(4):511–533, 2002.

[10] Клаудио Урас и Алессандро Верри, Описание и распознавание формы с помощью функций размера Технический отчет ICSI TR-92-057, Беркли, 1992.

[11] Алессандро Верри, Клаудио Урас, Патрицио Фрозини и Массимо Ферри,Об использовании функций размера для анализа формы, Биологическая кибернетика, 70: 99–107, 1993.

[12] Патрицио Фрозини и Клаудиа Ланди,Размерные функции и морфологические преобразования, Acta Applicandae Mathematicae, 49 (1): 85–104, 1997.

[13] Алессандро Верри и Клаудио Урас,Метрико-топологический подход к формепредставление и признание,Image Vision Comput., 14: 189–207, 1996.

[14] Алессандро Верри и Клаудио Урас,Вычисление функций размера из карт границ, Междунар. J. Comput. Видение, 23 (2): 169–183, 1997.

[15] Франсуаза Дибуш, Патрицио Фрозини и Дени Паскиньон,Использование функций размера для сравнения форм через дифференциальные инварианты, Journal of Mathematical Imaging and Vision, 21 (2): 107–118, 2004.

[CeFeGi06-16] Андреа Черри, Массимо Ферри, Даниэла Джорджи, Получение изображений товарных знаков с помощью функций размера Графические модели 68:451–471, 2006.

[BiGiSp08-17] Сильвия Биазотти, Даниэла Джорджи, Микела Спаньоло, Бьянка Фальцидиено, Функции размера для сравнения 3D-моделей Распознавание образов 41: 2855–2873, 2008.

[Fro96-18] Патрицио Фрозини, Связь между размерными функциями и критическими точками, Математические методы в прикладных науках, 19: 555–569, 1996.

[DoFro04-19] Пьетро Донатини и Патрицио Фрозини, Нижние оценки естественных псевдодальностей через функции размера, Архивы неравенств и приложений, 2 (1): 1–12, 2004.

[LaFro97-20] Клаудиа Ланди и Патрицио Фрозини, Новые псевдодистанции для размерного функционального пространства, Proc. SPIE Vol. 3168, стр. 52-60, Vision Geometry VI, Роберт А. Мелтер, Анжела Ю. Ву, Лонгин Дж. Латецки (ред.), 1997.

[FroLa01-21] Патрицио Фрозини и Клаудиа Ланди, Функции размера и формальные ряды, Прил. Algebra Engrg. Comm. Вычисл., 12: 327–349, 2001.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]