Уважаемые коллеги!
В пятницу 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 | Сидорова Василина Викторовна |