Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 79

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 79)

Здесь мы сталкиваемся с маленькой неприятностью. Если плоскость изображения считается бесконечной, величина р может принимать произвольно большие значения, и равномерное распределение задать нельзя'). К счастью, эту трудность легко обойти, договорившись с самого начала, что мы рассматриваем только линии, проходящие через сетчатку, которую предварительно определили. Это означает, что мы можем ограничить внимание таким подмно.

жеством плоскости (0, р), которое соответствует линиям ((0, р), проходящим через сетчатку. Затем мы введем термин «случайным об- ') Проблема здесь в точвости такая же, как при попытке строго <выбрать случайным образом число среди всех веществеииых чисел». Неопределеииое выражение <случайяьог образом» обычно понимается в смысле «с равномерным распределеиием», и мы сталкиваемся с мистическим «равиомериым распределением по всем веществ«иным числам». Гл. Р. Описания линии и формы разом», обозначая им равномерное распределение на этом множестве.

Используем эту формализацию для разрешения парадокса Бертрана. Зададим нашу сетчатку в виде круга единичного радиуса и вычислим вероятность того, что случайная линия, брошенная на сетчатку, имеет длину, равную по меньшей мере )л 3. Как показано на рнс. 9.30, множество точек на плоскости (О, р), которые соответствуют линиям, проходящим через круглую сетчатку, представляет собой прямоугольник высотой ! и шириной 2п.

Точки, лежащие в нижней половине прямоугольника, соответствуют хордам, превос-. ходящим по длине )~ 3, как мы убедились в предыдущих рассуждениях. Следовательно, ответ равен 1/2, поскольку распределение на плоскости (6, р) равномерно в пределах боль- 7 шого прямоугольника.

Перечислим без доказа- тельств некоторые свойства 6 пересечений случайных линий с объектами. Полагаем всюду, что используются параметры й и р, и поэтому перечисляемые свойства будут ин- РиС. 9.30. РаЗРЕШСН«Е ПЯРЯЯОКСа БЕРТ- вариантны к любым переносам и вращениям, которые полностью сохраняют обьект внутри сетчатки. Мы должны заранее ожидать, что некоторые из этих свойств будут зависеть от самой сетчатки. Например, если сетчатка очень велика по сравнению с объектом, то только малая доля случайных линий, брошенных на сетчатку, будет вообще пересекать объект. В дальнейшем будем обозначать длину периметра сетчатки через )с и будем считать, что объект состоит из одной просто связной компоненты с границей В.

Наш первый результат определяет, насколько велика вероятность пересечения случайной линией объекта. Результпт лг Вероятность того, что случайная линия пересечет объект, равна О/)(, где Н вЂ” длина периметра выпуклой оболочки границы. У читателя не должно возникнуть трудностей с вопросом, почему искомая вероятность зависит от выпуклой оболочки гракицы; линия пересекает объект в том и только в том случае, если она.пересекает его выпуклую оболочку.

Таким образом, результат 1 представляет собой элегантную формулировку того интуитивно ясного факта, что чем больше объект (по сравнению с размером сетчатки), тем больше вероятность его пересечения случайной линией. У.З. Олисаняе 4юрлы З97 Второй результат относится к числу пересечений объекта случайной линией. Резугавггаатм й Ожидаемое число Пересечений границы В одной линией равно (2~В~)/В, где ~В~ — длина границы. Это математическое ожидание зависит, конечно, от самой границы В, а не от Н, поскольку, если граница В очень извилиста, линия, пересекающая ее хотя бы один раз, скорее всего пересечет ее много раз. Последний результат, который мы хотим привести, относится к площади объекта.

Резулвгггагга 370жидаемаядлнна пересечения случайной линии с произвольным объектом пропорциональна площади объекта. Перечисленные результаты типичны для методов интегральной геометрии. Ясно, однако, что эти результаты сами по себе не особенно полезны при описании объектов. Например, если мы хотим измерить длину границы объекта, есть, конечно, и более прямой метод, чем бросание случайной линии и использование результата 2 '). Мы получим несколько более полезное представление об интегральной геометрии, если расширим наши горизонты и ясно осознаем, что результат эксперимента по бросанию линии представляет собой наблюдение случайной величины.

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

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

Конечно, возможен случай, когда бросание х) Часто утверждают, что метод интегральной геометрии обладает преимупгеством «выносливостиы Малый разрыв в границе В создает трудности для алгоритма прослеживания кривых, но, по-видимому, не очень влияет на работо. способность метода бросания линий. Гл. У. Описании линии и фирин единственной линии дает неприемлемо высокую байесовскую вероятность ошибки. Это аналогично описанию образа с помощью не очень информативного набора признаков.

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

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

Тогда прн бросании линии мы можем наблюдать кривизну границы в точке пересечения. Эти наблюдения. как можно ожидать, должны быть связаны с общей кривизной границы объекта. Второе расширение метода заключается в бросании на сетчатку каких-либо кривых вместо прямых линий. Например, мы можем бросать сегменты линий (вместо бесконечных линий); данные, получаемые в этом эксперименте, могут быть связаны с углом между двумя прямыми линиями на сетчатке.

Дальнейшие расширения мы предоставляем списку литературы и воображению читателя. эзк БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ 9ЛЛ. ОПИСАНИЕ ЛИНИИ Первые работы по аппроксимации множества точек линией были, скорее всего, стимулированы потребностями ученых-экспериментаторов; простейший путь «объяснить» совокупность наблюдений состоит в том, чтобы связать зависимые и независимые переменные посредством уравнения прямой линии.

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

Отношение между чисто числовым методом МСКО и статистическим методом часто называют теоремой Гаусса — Маркова (что показывает, насколько стар подбор по МСКО). Подробные сведения об этом можно найти в стандартных руководствах по статистике, таких, как книга Уилкса (1962). Все другие методы подбора линий, обсуждаемые в этой главе, были разработаны для целей анализа изображений. Преобразование точки в кривую, описанное в п. 9,1.3, было предложено Дудой и Хартом (1972).

Характеристики

Список файлов книги