完整搜尋頁面 →

逐步說明淹水演算法

選讀・IP 10・影像分割(一):邊緣偵測、閾值化與區域偵測 的補充資料(第 5/6 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

分水嶺把影像 gg(通常是梯度大小)當成地形,從它的區域極小值開始淹水。

水壩用 IP 09 的形態學來築。當兩個已淹水的連通成分快要合併時,以 3×33 \times 3 結構元素分別膨脹它們,並限制在低於目前水位的像素內;在同一步被兩者同時碰到的像素就是水壩像素,設成比影像最大值還高。這樣築出的水壩只有一個像素寬,而且是連通的。

令 M1,…,MRM_1, \dots, M_R 為影像 gg 的區域極小值,min⁡\min、max⁡\max 為其極值,T[n]={(s,t):g(s,t)<n}T[n] = \{(s, t) : g(s, t) < n\} 為低於水位 nn 的像素集合,C[n]C[n] 為水位 nn 時所有集水盆已淹部分的聯集。淹水從 n=min⁡+1n = \min + 1 進行到 max⁡+1\max + 1,以 C[min⁡+1]=T[min⁡+1]C[\min + 1] = T[\min + 1] 開始。在每個水位,對 T[n]T[n] 的每個連通成分 qq 與 C[n−1]C[n-1] 比較:

  1. q∩C[n−1]q \cap C[n-1] 為空:出現新的極小值,qq 成為新的集水盆。
  2. q∩C[n−1]q \cap C[n-1] 只含 C[n−1]C[n-1] 的一個成分:qq 位於某個既有集水盆中,把它加進去。
  3. q∩C[n−1]q \cap C[n-1] 含兩個以上成分:集水盆正在相遇,依前述方法在 qq 中築壩。

參考文獻

  1. R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 10. publisher page
  2. D. Marr and E. Hildreth, “Theory of edge detection,” Proceedings of the Royal Society of London. Series B, vol. 207, no. 1167, pp. 187–217, 1980. doi
  3. J. Canny, “A Computational Approach to Edge Detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 6, pp. 679–698, 1986. doi
  4. R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,” Communications of the ACM, vol. 15, pp. 11–15, 1972. doi
  5. N. Otsu, “A Threshold Selection Method from Gray-Level Histograms,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, no. 1, pp. 62–66, 1979. doi
  6. M. Sezgin and B. Sankur, “Survey over image thresholding techniques and quantitative performance evaluation,” Journal of Electronic Imaging, vol. 13, no. 1, pp. 146–165, 2004. doi
  7. J. Sauvola and M. Pietikäinen, “Adaptive document image binarization,” Pattern Recognition, vol. 33, no. 2, pp. 225–236, 2000. doi
  8. R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua and S. Süsstrunk, “SLIC Superpixels Compared to State-of-the-Art Superpixel Methods,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 11, pp. 2274–2282, 2012. doi
  9. J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888–905, 2000. doi
  10. L. Vincent and P. Soille, “Watersheds in digital spaces: an efficient algorithm based on immersion simulations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583–598, 1991. doi
  11. S. Minaee, Y. Boykov, F. Porikli, A. Plaza, N. Kehtarnavaz and D. Terzopoulos, “Image Segmentation Using Deep Learning: A Survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 7, pp. 3523–3542, 2022. doi · arXiv
  12. T. Zhou, W. Xia, F. Zhang, B. Chang, W. Wang, Y. Yuan, E. Konukoglu and D. Cremers, “Image Segmentation in Foundation Model Era: A Survey,” arXiv:2408.12957, 2024. arXiv
  13. J. Long, E. Shelhamer and T. Darrell, “Fully Convolutional Networks for Semantic Segmentation,” arXiv:1411.4038, 2014. arXiv
  14. O. Ronneberger, P. Fischer and T. Brox, “U-Net: Convolutional Networks for Biomedical Image Segmentation,” in Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015, Lecture Notes in Computer Science, vol. 9351, pp. 234–241, Springer, 2015. doi · arXiv
  15. K. He, G. Gkioxari, P. Dollár and R. Girshick, “Mask R-CNN,” arXiv:1703.06870, 2017. arXiv
  16. L.-C. Chen, G. Papandreou, I. Kokkinos, K. Murphy and A. L. Yuille, “DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 4, pp. 834–848, 2018. doi · arXiv
  17. A. Kirillov, E. Mintun, N. Ravi et al., “Segment Anything,” arXiv:2304.02643, 2023. arXiv
  18. R. Sun, T. Lei, Q. Chen, Z. Wang, X. Du, W. Zhao and A. K. Nandi, “Survey of Image Edge Detection,” Frontiers in Signal Processing, 2022. doi
  19. S. Xie and Z. Tu, “Holistically-Nested Edge Detection,” arXiv:1504.06375, 2015. arXiv
  20. D. Stutz, A. Hermans and B. Leibe, “Superpixels: An Evaluation of the State-of-the-Art,” Computer Vision and Image Understanding, vol. 166, pp. 1–27, 2018. doi
  21. I. Arganda-Carreras, S. C. Turaga, D. R. Berger et al., “Crowdsourcing the creation of image segmentation algorithms for connectomics,” Frontiers in Neuroanatomy, vol. 9, 2015. doi
  22. M. Maška, V. Ulman, D. Svoboda et al., “A benchmark for comparison of cell tracking algorithms,” Bioinformatics, vol. 30, no. 11, pp. 1609–1617, 2014. doi · Cell Tracking Challenge