Восстановление наклона оцифрованной линии

11

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

(Понятие оцифрованной строки, которую я использую, - это Розенфельд: набор пар где располагается над целыми числами (или блоком последовательных целых чисел), а обозначает целое число ближайший к (если , мы берем ).)я п я п т ( х ) х х = к + 1 / 2 л я п т ( х ) = к(я,NяNT(aя+б))яNяNT(Икс)ИксИксзнак равноК+1/2NяNT(Икс)знак равноК

Я проделал некоторую работу над этим самостоятельно (см. Http://jamespropp.org/SeeSlope.nb ), но у меня нет формального фона в вычислительной геометрии, поэтому я подозреваю, что могу заново изобретать колесо, так как вопрос кажется таким основной.

На самом деле, я знаю, что метод линейной регрессии для оценки уклона есть в литературе, но я нигде не смог найти свой результат . (Этот результат говорит о том, что если в случайным образом выбрать и равномерно в случайном порядке , то разница между наклоном линии и наклоном линии регрессии, аппроксимирующей точек ( ) имеет стандартное отклонение .)a b [ 0 , 1 ] a y = a x + b ¯ a n ( i , n i n t ( a i + b ) ) 1 i n O ( 1 / n 1,5 )О(1/N1,5)aб[0,1]aYзнак равноaИкс+бa¯N(я,NяNT(aя+б))1яNО(1/N1,5)

Будем весьма благодарны за любые ссылки или ссылки на соответствующую литературу.

Джим Пропп (JamesPropp@ignorethis.gmail.com)

Джим Пропп
источник
Таким образом, точечная оцифровка - это грубо говоря, набор ячеек из сетки n × n ? NN×N
Суреш Венкат
1
Что именно вы подразумеваете под оцифрованной строкой? Я предположил, что вы имели в виду что-то вроде прямой линии на фотографии или растеризованном изображении, но из разговоров о линейной регрессии это звучит больше как то, что вы заинтересованы в поиске линии, наиболее подходящей для некоторых выборочных данных.
Джо Фицсимонс
Таким образом, интересующая вас модель - это не точное решение и b , а лишь их приближение? Я бы упростил задачу, не принимая во внимание b (это просто раздражающий сдвиг), и придерживаясь a x (оказывается, это просто еще один сдвиг). Кроме того , что п здесь? aббaИксN
Митч
Прости, Митч; Я забыл объяснить , что было! Я добавил это к оригинальному сообщению. - ДжимN
Джим Пропп

Ответы:

1

См. Случайное генерирование конечных слов Штурма по Berstel и Pocchiola для доказательства того, что допустимая область вашего LP имеет только три или четыре стороны, а также простой алгоритм для нахождения многоугольника с заданным наклоном и перехватом. (Они имеют дело с распознаванием слов Штурма, но проблемы тесно связаны.)

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

deinst
источник
4

Подход вычислительной геометрии заменяет каждый пиксель (i, j) вертикальным сегментом (i, j + [- 1 / 2,1 / 2]), принимает выпуклые оболочки верхнего и нижнего наборов конечных точек и вычисляет внутреннюю общую касательные - они ограничивают диапазон наклонов, которые производят эту цифровую линию. Это просто геометрическая интерпретация линейной программы, которую вы упоминаете в своих слайдах. O (n) времени достаточно для LP Меггиддо или для корпусов и касательных Грэма-Яо.

Джек
источник
2

Как насчет стандартного метода преобразования Хафа, который используется для обнаружения линий при обработке изображений: http://en.wikipedia.org/wiki/Hough_transform ?

Если вы хотите получить некоторую скорость, вы можете использовать рандомизированную версию HT.

Марцио де Биаси
источник
1
  • Я не знаю какой-либо работы в cg (или любой другой группе по этому вопросу) по получению наклона из набора дискретных точек, но это больше отражает мое отсутствие знаний.

  • ΔYΔИксИксYИксY

Митч
источник
О(1/N)