Однако, TeX — очень мощная система, способная даже решать кубические уравнения! Неужели она не справится с такой простой задачей? Справится, и еще как!
( Не пугаться! )Строить массив [R, Θ] можно двумя способами. Первый — последовательно пройтись по всем точкам этого массива, занося туда суммарную интенсивность пикселей, расположенных на соответствующей прямой. Сложность этого способа пропорциональна произведению площади изображения-преобразования Хафа на характерный размер оригинального изображения.
Второй способ — последовательно пройтись по всем точкам изображения, инкрементируя на величину интенсивности в данном пикселе все ячейки преобразования Хафа, соответствующие возможным прямым, проходящим через данный пиксель. Сложность этого способа пропорциональна произведению площади изображения на характерный размер изображения-преобразования Хафа.
Какой из способов использовать — выбор наиболее оптимальной производительности. В моем случае второй способ был удобнее (т.к. изображение-преобразование Хафа имеет меньшую площадь).
Еще один вопрос: что заносить в ячейки преобразования Хафа. Мы можем заносить туда единицу для каждого пикселя, чья интенсивность выше некоего порогового значения, а можем заносить саму эту интенсивность. Я выбрал второй способ, т.к. он лучше отражает наиболее интенсивные линии на фоне более слабых.
Так как это преобразование — задача довольно ресурсоемкая, ее можно попытаться распараллелить. Единственным узким местом является точка занесения данных в результирующий массив. Поэтому желательно либо синхронизовать эту точку (при помощи мьютексов, например), либо же использовать атомарные операции.
