Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp phân vùng miền kết hợp với thuật toán cắt đồ thị cho tối thiểu hóa biến thiên tổng
Tóm tắt
Gần đây, các thuật toán cắt đồ thị đã được sử dụng để giải quyết các vấn đề phục hồi hình ảnh biến phân, đặc biệt là trong việc loại bỏ nhiễu và phân đoạn. So với các phương pháp PDE theo thời gian, các phương pháp dựa trên cắt đồ thị hiệu quả hơn và có khả năng đạt được tối thiểu toàn cục. Tuy nhiên, đối với hình ảnh độ phân giải cao và quy mô lớn, chi phí cả về bộ nhớ và thời gian tính toán gia tăng đáng kể. Trong bài viết này, chúng tôi kết hợp phương pháp phân vùng miền và thuật toán cắt đồ thị để giải quyết bài toán tối thiểu hóa biến thiên tổng với các hạng mục độ chính xác L1 và L2. Nhiều thí nghiệm số trên dữ liệu quy mô lớn chứng minh rằng thuật toán được đề xuất mang lại kết quả tốt về thời gian tính toán và mức sử dụng bộ nhớ.
Từ khóa
#thuật toán cắt đồ thị #tối thiểu hóa biến thiên #phân vùng miền #hồi phục hình ảnh #loại bỏ nhiễu #phân đoạn hình ảnhTài liệu tham khảo
Alliney, S.: Digital filters as absolute norm regularizers. IEEE Trans. Signal Process. 40(6), 1548–1562 (1992)
Alliney, S.: A property of the minimum vectors of a regularizing functional defined by means of the absolute norm. IEEE Trans. Signal Process. 45(4), 913–917 (1997)
Alliney, S., Ruzinsky, S.: An algorithm for the minimization of mixed l 1 and l 2 norms with application to Bayesian estimation. IEEE Trans. Signal Process. 42(3), 618–627 (1994)
Boykov, Y., Kolmogorov, V.: Computing geodesics and minimal surfaces via graph cuts. In: IEEE International Conference on Computer Vision, Nice, France, vol I, pp. 26–33 (2003)
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. 26(9), 1124–1137 (2004)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1222–1239 (2001)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1), 89–97 (2004)
Chambolle, A.: Total variation minimization and a class of binary MRF models. Energy minimization methods in computer vision and pattern recognition: 5th international workshop, EMMCVPR 2005. Lect. Notes Comput. Sci. 3757, 136–152 (2005)
Chan, T., Esedoglu, S.: Aspects of total variation regularized l 1 function approximation. SIAM J. Appl. Math. 65(5), 1817–1837 (2005)
Chan, T., Mathew, T.: Domain decomposition algorithms. Acta Numer. 3, 61–143 (1994)
Chan, T., Shen, J.: Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods. Society for Industrial and Applied Mathematics (2005)
Chan, T., Shen, J., Vese, L.: Variational PDE models in image processing. Not. Am. Math. Soc. 50(1), 14–26 (2003)
Chen, K., Tai, X.: A nonlinear multigrid method for total variation minimization from image restoration. J. Sci. Comput. 33(2), 115–138 (2007)
Darbon, J.: Total variation minimization with l 1 data fidelity as a contrast invariant filter. In: Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis (ISPA 2005), Zagreb, Croatia (2005)
Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation part I: fast and exact optimization. J. Math. Imaging Vis. 26(3), 261–276 (2006)
Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation part II: levelable functions, convex priors and non-convex cases. J. Math. Imaging Vis. 26(3), 277–291 (2006)
Dong, Y., Hintermúller, M., Neri, M.: A primal-dual method for L1 TV image denoising. SIAM J. Imaging Sci. 2, 577–613 (2009)
Ford, L., Fulkerson, D.: Flows in Networks. Princeton University Press (1962)
Gallo, G., Grigoriadis, M., Tarjan, R.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30–55 (1989)
Goldberg, A., Tarjan, R.: A new approach to the maximum-flow problem. J. Assoc. Comput. Mach. (JACM) 35(4), 921–940 (1988)
Goldfarb, D., Yin, W.: Parametric maximum flow algorithms for fast total variation minimization. SIAM J. Sci. Comput. 31(5), 3712–3743 (2009)
Goldstein, T., Osher, S.: The split Bregman method for L1 regularized problems. SIAM J. Imaging Sci. 2(2), 323–343 (2009)
Greig, D., Porteous, B., Seheult, A.: Exact maximum a posteriori estimation for binary images. J. R. Stat. Soc., B (Methodological) 51(2), 271–279 (1989)
Guichard, F., Morel, J.: Mathematical morphology “almost everywhere”. In: Proceedings of ISMM, Csiro Publishing, pp. 293–303 (2002)
Ishikawa, H.: Exact optimization for Markov random fields with convex priors. IEEE Trans. Pattern Anal. Mach. Intell. 25(10), 1333–1336 (2003)
Jia, R., Zhao, H.: A fast algorithm for the total variation model of image denoising. Adv. Comput. Math. 33(2), 231–241 (2010)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147–159 (2004)
Nikolova, M.: A variational approach to remove outliers and impulse noise. J. Math. Imaging Vis. 20(1), 99–120 (2004)
Osher, S., Sole, A., Vese, L.: Image decomposition and restoration using total variation minimization and the h − 1 norm. Multiscale Model. Simul. 1(3), 349–370 (2003)
Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4(2), 460–489 (2006)
Pollak, I., Willsky, A., Huang, Y.: Nonlinear evolution equations as fast and exact solvers of estimation problems. IEEE Trans. Signal Process. 53(2), 484–498 (2005)
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1–4), 259–268 (1992)
Rudin, L., Osher, S., Inc, C., Santa Monica, C.: Total variation based image restoration with free local constraints. In: IEEE International Conference Image Processing, Austin, TX, pp. 31–35 (1994)
Sauer, K., Bouman, C.: Bayesian estimation of transmission tomograms using segmentation based optimization. IEEE Trans. Nucl. Sci. 39(4), 1144–1152 (1992)
Savage, J., Chen, K.: An improved and accelerated non-linear multigrid method for total-variation denoising. Int. J. Comput. Math. 82(8), 1001–1015 (2005)
Tai, X.: Parallel function decomposition and space decomposition methods: Part II. Space decomposition. Beijing Math. 1, 135–152 (1995)
Tai, X.: Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities. Numer. Math. 93(4), 755–786 (2003)
Tai, X., Espedal, M.: Rate of convergence of some space decomposition methods for linear and nonlinear problems. SIAM J. Numer. Anal. 35(4), 1558–1570 (1998)
Tai, X., Wu, C.: Augmented lagrangian method, dual methods and split bregman iteration for ROF model. In: Scale Space and Variational Methods in Computer Vision, Second International Conference, pp. 502–513. Springer (2009)
Tai, X., Xu, J.: Global and uniform convergence of subspace correction methods for some convex optimization problems. Math. Comput. 71(237), 105–124 (2002)
Vogel, C., Oman, M.: Iterative methods for total variation denoising. SIAM J. Sci. Comput. 17(1), 227–238 (1996)
Wen, Y., Ng, M., Huang, Y.: Efficient total variation minimization methods for color image restoration. IEEE Trans. Image Process. 17(11), 2081–2088 (2008)
Wu, C., Tai, X.: Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models. SIAM J. Imaging Sci. 3, 300–339 (2010)
Wu, C., Zhang, J., Tai, X.: Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. UCLA CAM Report 09–82, Department of Mathematics, UCLA, Los Angeles, CA, CAM Report (2009)