Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Chỉ số tương tự nhanh cho các ứng dụng ghép mẫu thời gian thực
Tóm tắt
Trong nghiên cứu này, một chỉ số tương tự trực quan dựa trên đồ thị precision-recall được trình bày như một lựa chọn thay thế cho khoảng cách Hausdorff (HD) thường được sử dụng. Chỉ số này, được gọi là chỉ số tương tự độ lớn tối đa, được tính toán giữa một hình dạng tham chiếu và một mẫu thử, mỗi mẫu được đại diện bởi một tập hợp các điểm cạnh. Chúng tôi giải quyết bài toán này bằng cách sử dụng một đồ thị bipartite để mô tả mối quan hệ giữa các tập hợp. Bài toán ghép là được giải quyết bằng thuật toán Hopcroft–Karp, tận dụng độ phức tạp tính toán thấp của nó. Chúng tôi trình bày một so sánh giữa kết quả của chúng tôi và những kết quả thu được từ việc áp dụng khoảng cách Hausdorff một phần (PHD) cho cùng một bộ thử nghiệm. Các kết quả tương tự đã được tìm thấy khi sử dụng cả hai phương pháp cho các ứng dụng ghép mẫu tiêu chuẩn. Tuy nhiên, phương pháp đề xuất chính xác hơn trong việc xác định tính hoàn thiện của các hình dạng một phần trong điều kiện nhiễu. Hơn nữa, thời gian xử lý cần thiết cho phương pháp của chúng tôi thấp hơn thời gian cần thiết để tính toán PHD cho một tập hợp lớn các điểm.
Từ khóa
#tương tự #ghép mẫu #đồ thị bipartite #khoảng cách Hausdorff #thuật toán Hopcroft–Karp #độ phức tạp tính toánTài liệu tham khảo
Ali, M., Ghafoor, M., Taj, I.A., Hayat, K.: Palm print recognition using oriented Hausdorff distance transform. In: Proceedings of Frontiers of Information Technology, pp. 85–88 (2011)
Arbelaez, P., Fowlkes, C, Martin, D.: The Berkeley segmentation dataset and benchmark. http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/. Accessed Dec 2012.
Belongie, S., Malik, J., Puzicha, J.: Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. Mach. Intell. 24(4), 509–522 (2002)
Canny, J.: A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8(6), 679–698 (1986)
Correa-Tome, F.E., Sanchez-Yanez, R.E., Ayala-Ramirez, V.: Comparison of perceptual color spaces for natural image segmentation tasks. Opt. Eng. 50(11), 117203 (2011)
Correa-Tome, F.E., Sanchez-Yanez, R.E., Ayala-Ramirez, V.: Measuring empirical discrepancy in image segmentation results. IET Comput. Vis. 6(3), 224–230 (2012)
Dastmalchi, H., Jafaryahya, J., Najafi, R., Daneshkhah, A.: Averaged segmental partial Hausdorff distance for robust face recognition. In: Proceedings of 2nd International Conference on Intelligent Systems, pp. 35–39 (2011)
Hanniel, I., Krishnamurthy, A., McMains, S.: Computing the Hausdorff distance between NURBS surfaces using numerical iteration on the GPU. Graph. Models 74(4), 255–264 (2012)
Hopcroft, J.E., Karp, R.M.: A n 5/2 algorithm for maximum matchings in bipartite graphs. In: Proceedings of IEEE Annual Symposium on Foundations of Computer Science, pp. 122–125 (1971)
Hossain, M.J., Dewan, M.A.A., Ahn, K., Chae, O.: A linear time algorithm of computing Hausdorff distance for content-based image analysis. Circ. Syst. Signal. Process 31(1), 389–399 (2011)
Hossain, M.J., Dewan, M.A.A., Chae, O. A flexible edge matching technique for object detection in dynamic environment. Appl. Intell. 36(3), 638–648 (2011)
Hu, Y., Wang, Z.: A similarity measure based on Hausdorff distance for human face recognition. In: Proceedings of 18th International Conference on Pattern Recognition, pp. 1131–1134 (2006)
Huttenlocher, D.P., Klanderman, G.A., Rucklidge, W.J. Comparing images using the Hausdorff distance. IEEE Trans. Pattern Anal. Mach. Intell. 15(9), 850–863 (1993)
Huttenlocher, D.P., Rucklidge, W.J.: A multi-resolution technique for comparing images using the Hausdorff distance. In: Proceedings of Computer Vision and Pattern Recognition, pp. 705–706 (1993)
Ji, Y.H., Song, J.B., Choi, J.H.: Outdoor mobile robot localization using Hausdorff distance-based matching between COAG features of elevation maps and laser range data. In: Proceedings of 11th International Conference on Control, Automation and Systems, pp. 686–689 (2011)
Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325–340 (1987)
Knauer, C., Lffler, M., Scherfenberg, M., Wolle, T.: The directed Hausdorff distance between imprecise point sets. Theor. Comput. Sci. 412(32), 4173–4186 (2011)
Krishnamurthy, A., McMains, S., Hanniel, I.: GPU-accelerated Hausdorff distance computation between dynamic deformable NURBS surfaces. Comput.-Aided Des. 43(11), 1370–1379 (2011)
Li, Y., Stevenson, R.L.: A similarity metric for multimodal images based on modified Hausdorff distance. In: Proceedings of 9th International Conference on Advanced Video and Signal-Based Surveillance, pp. 143–148 (2012)
Lin, K.H., Guo, B., Lam, K.M., Siu, W.C.: Human face recognition using a spatially weighted modified Hausdorff distance. In: Proceedings of International Symposium on Intelligent Multimedia, Video and Speech Processing, pp. 477–480 (2001)
Lin, P.L., Lai, Y.H., Huang, P.W. Dental biometrics: human identification based on teeth and dental works in bitewing radiographs. Pattern Recogn. 45(3), 934–946 (2012)
Liu, Y., Lee, S.: PSU Near-Regular Texture Database. http://vivid.cse.psu.edu/. Accessed December 2012
Martin, D.R., Fowlkes, C.C., Tal, D., Malik, J.K.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Proceedings of 8th International Conference on Computer Vision, vol. 2, pp. 416–423 (2001)
Martin, D.R., Fowlkes, C.C., Malik, J.: Learning to detect natural image boundaries using local brightness, color, and texture cues. IEEE Trans. Pattern Anal. Mach. Intell. 26(5), 530–549 (2004)
Niu, L.P., Jiang, X.H., Zhang, W.H., Shi, D.X.: Image registration based on Hausdorff distance. In: Proceedings of International Conference on Networking and Information Technology, pp. 252–256 (2010)
Rucklidge, W.J.: Locating objects using the Hausdorff distance. In: Proceedings of 5th International Conference on Computer Vision, pp. 457–464 (1995)
Rucklidge, W.J.: Efficiently locating objects using the Hausdorff distance. Int. J. Comput. Vis. 24(3), 251–270 (1997)
Sim, D.G., Park, R.H.: Two-dimensional object alignment based on the robust oriented Hausdorff similarity measure. IEEE Trans. Image Process. 10(3), 475–483 (2001)
Tsapanos, N., Tefas, A., Nikolaidis, N., Pitas, I.: Shape matching using a binary search tree structure of weak classifiers. Pattern Recogn. 45(6), 2363–2376 (2012)
van Rijsbergen, C.J.: Information retrieval, 2 edn. Butterworths, London (1979)
Xu, D.: A unified approach to autofocus and alignment for pattern localization using hybrid weighted Hausdorff distance. Pattern Recogn. Lett. 32(14), 1747–1755 (2011)
Yang, C.H.T., Lai, S.H., Chang, L.W.: Hybrid image matching combining Hausdorff distance with normalized gradient matching. Pattern Recogn. 40(4), 1173–1181 (2007)