Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2017-29(4)-4

Полный текст:

Аннотация

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

Об авторах

Д. Р. Башкирова
RIKEN; Казанский (Приволжский) Федеральный Университет
Япония


Ш. Йошидзава
RIKEN
Япония


Р. Х. Латыпов
Казанский (Приволжский) Федеральный Университет
Россия


Х. Йокота
RIKEN
Япония


Список литературы

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.


Для цитирования:


Башкирова Д.Р., Йошидзава Ш., Латыпов Р.Х., Йокота Х. Быстрое L1-преобразование Гаусса для сглаживания изображений с сохранением границ. Труды Института системного программирования РАН. 2017;29(4):55-72. https://doi.org/10.15514/ISPRAS-2017-29(4)-4

For citation:


Bashkirova D.R., Yoshizawa S., Latypov R.H., Yokota H. Fast L1 Gauss Transforms for Edge-Aware Image Filtering. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(4):55-72. https://doi.org/10.15514/ISPRAS-2017-29(4)-4

Просмотров: 120


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)