Войти
Логин:
Пароль:
Забыли пароль?
научная деятельность
структура институтаобразовательные проектыпериодические изданиясотрудники институтапресс-центрконтакты
русский | english

Об аддитивной сложности классического и быстрого преобразований Хафа

Уважаемые коллеги!

В пятницу 2 марта 2018 г. в 17:00 в аудитории 615 ИППИ РАН состоится открытый семинар лаборатории № 11.

Тема семинара: Об аддитивной сложности классического и быстрого преобразований Хафа

Докладчик: Тимур Ханипов (м.н.с. лаборатории № 11 «Зрительные системы» ИППИ РАН).

Аннотация: Преобразование Хафа изображения размера n × n (определенной на двумерной целочисленной решетке функции, носитель которой содержится в квадрате n × n) сопоставляет каждой дискретной прямой из некоторого семейства сумму составляющих её пикселей (значений функции в соответствующих точках) аналогично тому, как преобразование Радона функции на плоскости сопоставляет непрерывным прямым линейные интегралы. На практике обычно рассматривают плотные семейства из Θ(n²) дискретных прямых с некоторой фиксированной параметризацией. Простейший алгоритм, вычисляющий преобразование Хафа для таких семейств, требует выполнения Θ(n³) сложений.

Быстрое преобразование Хафа (БПХ) является аппроксимацией классического преобразования Хафа, когда суммирование ведётся по “диадическим прямым”, которые чрезвычайно удобны с вычислительной точки зрения и в худшем случае уклоняются от “брезенхемовских” дискретных прямых как Θ(log n). БПХ вычисляется за Θ(n² log n) сложений и потому на практике активно применяется вместо классического преобразования Хафа там, где скорость обработки изображений является критическим фактором.

Ранее не были известны оценки аддитивной сложности вычисления преобразования Хафа кроме тривиальных Ω(n²) снизу и O(n³) сверху, также не имелось нетривиальных оценок снизу для аддитивной сложности БПХ. В докладе планируется изложить два результата, дающих некоторое продвижение в первом вопросе и с точностью до константы решающих второй:

1. С помощью известной оценки сложности реализации булевых линейных операторов будет показано, что ни одно из двух вышеперечисленных преобразований нельзя вычислить быстрее, чем за Θ(n² log n). Это, в частности, демонстрирует асимптотическую оптимальность стандартного алгоритма вычисления БПХ, причём константа в ограничении снизу всего на 5% отличается от константы сложности алгоритма.

2. Будет конструктивно доказано, что сложность вычисления классического преобразования Хафа ограничена сверху как O(n³ / log n). Предлагаемый способ построения вычислительной схемы состоит в декомпозиции прямых с близкими наклонами на общие части с сокращением на каждом шаге количества рассматриваемых наклонов вдвое (идейно он похож на алгоритм БПХ). Получающиеся в результате схемы могут иметь и меньшую, чем Θ(n³ / log n), сложность, это планируется проверить в ходе дальнейшего исследования. Интересно отметить, что при применении алгоритма к диадическим прямым естественным образом получается стандартный способ вычисления БПХ.

Подробнее с результатами можно ознакомиться по ссылкам http://arxiv.org/pdf/1801.01054.pdf и http://arxiv.org/pdf/1802.06619.pdf.


Ключевые слова: преобразование Хафа, быстрое преобразование Хафа, аддитивная сложность, задача вычисления семейства, дерево разбиений, сложность линейных булевых операторов.

 

Семинар открытый, приглашаются все желающие!

21.02.2018 | Сидорова Василина Викторовна
 

 

  © Федеральное государственное бюджетное учреждение науки
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, 2018
Об институте  |  Контакты  |  Старая версия сайта