完整搜尋頁面 →

以四元樹做區域分裂與合併

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

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

不用種子,而是從整張影像 RR 與述詞 QQ 開始:

  1. 對 Q(Ri)=FALSEQ(R_i) = \text{FALSE} 的區域 RiR_i,分裂成四個等大的象限。
  2. 重複,直到所有區域都通過 QQ,或達到最小尺寸。
  3. 對任意兩個相鄰區域 Rj,RkR_j, R_k,若 Q(Rj∪Rk)=TRUEQ(R_j \cup R_k) = \text{TRUE} 就合併。
  4. 無法再分裂或合併時停止。

分裂的過程以四元樹(quadtree)儲存:根節點是整張影像,每個節點有四個子節點。只分裂會得到方塊狀的區域;合併才讓區域能跨越象限邊界。典型的述詞如「標準差大於 aa,且平均介於 bb 與 cc 之間」。

參考文獻

  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