Быстрое L1-преобразование Гаусса для сглаживания изображений с сохранением границ

Преобразование Гаусса, также как и его дискретный аналог, является важнейшим инструментом во множестве математических дисциплин и находит свое применение во многих научных и инженерных областях, таких как математическая статистика и теория вероятностей, физика, математическое моделирование, машинное обучение и обработка изображений и прочие. Ввиду высокой вычислительной сложности преобразования Гаусса (квадратичная сложность относительно количества точек и экспоненциальная - относительно размерности точек), необходимы эффективные и быстрые методы его аппроксимации, обладающие большей точностью по сравнению с существующими ныне методами, такими как Быстрое Преобразование Фурье или оконное преобразование. В данной статье предложен новый метод аппроксимации преобразования Гаусса для равномерно распределенный множеств точек (например, двумерных изображений), основанный на использовании L 2 метрики и метода разделения доменов. Такой подход позволяет значительно сократить количество вычислительных операций путем выполнения предварительных вычислений, и снизить вычислительную сложность метода до линейной. Результаты ряда численных экспериментов показали, что разработанный алгоритм позволяет получить более высокую точность аппроксимации без потери скорости вычисления в сравнении со стандартными методами. Также в качестве примера применения предлагаемого алгоритма была разработана новая схема смежной фильтрации изображения. Было показано, что новый фильтр на основе быстрого L 1 преобразования Гаусса позволяет получить результат более высокого качества при сопоставимой скорости вычисления и при этом избежать появления нежелательных артефактов в результате обработки, таких как эффект ореола.

фильтр Гаусса, распреледение Лапласа, быстрый метод аппроксимации

1. A. Elgammal, R. Duraiswami, and L. Davis, “Efficient kernel density estimation using the fast Gauss transform with applications to color modeling and tracking,” IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol. 25, no. 11, pp. 1499-1504, 2003.

2. S. Paris and F. Durand, “A fast approximation of the bilateral filter using a signal processing approach,” in Proc. of European Conference on Computer Vision (ECCV). Springer, 2006, pp. 568-580.

3. L. Greengard and J. Strain, “The fast Gauss transform,” SIAM Journal on Scientific and Statistical Computing, vol. 12, no. 1, pp. 79-94, 1991.

4. D. Lee, A. Gray, and A. Moore, “Dual-tree fast Gauss transforms,” Advances in Neural Information Processing Systems (NIPS), vol. 18, pp. 747-754, 2006.

5. C. Yang, R. Duraiswami, N. A. Gumerov, and L. Davis, “Improved fast Gauss transform and efficient kernel density estimation.” in Proc. of International Conference on Computer Vision (ICCV), vol. 1, 2003, pp. 464-471.

6. A. Adams, N. Gelfand, J. Dolson, and M. Levoy, “Gaussian kd-trees for fast high-dimensional filtering,” in ACM Transactions on Graphics (TOG), vol. 28, no. 3, ACM, 2009.

7. E. Dougherty, Digital Image Processing Methods. CRC Press, 1994.

8. R. Deriche, “Fast algorithms for low-level vision,” IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol. 12, no. 1, pp. 78-87, 1990.

9. D. Lang, M. Klaas, and N. de Freitas, “Empirical testing of fast kernel density estimation algorithms,” University of British Columbia, Technical Report UBC TR-2005-03, 2005.

10. P. Getreuer, “A survey of Gaussian convolution algorithms,” Image Process. On Line, vol. 3, pp. 276-300, 2013.

11. S. Yoshizawa and H. Yokota, “Fast L1 Gaussian convolution via domain splitting,” in Proc. of IEEE International Conference on Image Processing (ICIP). IEEE, 2014, pp. 2908-2912.

12. He, Kaiming, Jian Sun, and Xiaoou Tang. "Guided image filtering." IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol. 35, no. 6, pp. 1397-1409, 2013.

13. T. Ooura, General Purpose FFT (Fast Fourier/Cosine/Sine Transform) Package. www.kurims.kyoto-u.ac.jp/∼ooura/fft.html, 2006.

14. Kopf, Johannes, et al. "Joint bilateral upsampling." ACM Transactions on Graphics (TOG), vol. 26. no. 3. ACM, 2007.

15. Тихонов, А. Н. "О некорректных задачах линейной алгебры и устойчивом методе их решения." ДАН СССР, 1965, 163.3.

16. D. Bashkirova, S. Yoshizawa, R. Latypov and H. Yokota. “Fast L1 Gauss 2D Image Transforms”, in Proc. of Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE), Institute for System Programming, RAS, 2017, pp. 145-149. Доступно по ссылке http://syrcose.ispras.ru/2017/SYRCoSE2017_Proceedings.pdf, дата обращения 10.06.2017.