Cần có thuật toán tốt hơn để tìm ánh xạ giữa 2 tập hợp điểm với khoảng cách tối thiểu

Question

Vấn đề: Tôi có hai hình dạng 2D chồng lên nhau, A và B, mỗi hình có cùng số pixel, nhưng khác nhau về hình dạng. Một số phần của hình dạng chồng lên nhau, và có một số phần của mỗi hình không bị trùng lặp. Mục tiêu của tôi là di chuyển tất cả các pixel không chồng lên nhau trong hình dạng A đến các pixel không chồng chéo trong hình B. Vì số lượng pixel trong mỗi hình dạng giống nhau nên tôi có thể tìm thấy ánh xạ 1 đến 1 pixel. Hạn chế là tôi muốn tìm ánh xạ giúp giảm thiểu tổng khoảng cách được di chuyển bởi tất cả các pixel di chuyển.

Lực lượng vũ phu: Cách tiếp cận bạo lực để giải quyết vấn đề này rõ ràng là không có câu hỏi, vì tôi sẽ tính tổng khoảng cách của tất cả các ánh xạ có thể mà tôi nghĩ là có n! (trong đó n là số điểm ảnh không chồng chéo trong một hình) lần tính toán khoảng cách cho mỗi cặp điểm trong ánh xạ, n, cho tổng cộng O (n * n!) hoặc một cái gì đó tương tự.

Backtracking: Giải pháp "tốt hơn" tôi có thể nghĩ là sử dụng backtracking, nơi tôi sẽ theo dõi mức tối thiểu hiện tại cho đến thời điểm này. hoặc vượt quá mức tối thiểu đó, tôi chuyển sang bản đồ tiếp theo. Ngay cả điều này sẽ không làm tốt hơn O (n!).

Có cách nào để giải quyết vấn đề này với độ phức tạp hợp lý không?

Cũng lưu ý rằng cách tiếp cận "rõ ràng" chỉ đơn giản là ánh xạ một điểm đến đối tượng lân cận gần nhất của nó không phải lúc nào cũng mang lại giải pháp tối ưu.

đơn giản hơn cách tiếp cận ?: Như một câu hỏi phụ, nếu một giải pháp khả thi không tồn tại, một khả năng có thể để phân vùng từng bộ phận không chồng chéo thành các vùng nhỏ, và bản đồ các khu vực này, làm giảm đáng kể số lượng các ánh xạ . Để tính toán khoảng cách giữa hai vùng, tôi sẽ sử dụng trung tâm khối lượng (trung bình của các vị trí pixel trong khu vực). Tuy nhiên, điều này trình bày vấn đề làm thế nào tôi nên đi về làm phân vùng để có được một câu trả lời gần tối ưu.

Bất kỳ ý tưởng nào được đánh giá cao !!

Answer 1

Đây là vấn đề về Đối sánh tối thiểu và bạn chính xác rằng đó là vấn đề khó khăn nói chung. Tuy nhiên đối với trường hợp 2D Euclidean Bipartite Minimum Matching, nó có thể giải quyết được gần với O (n²) (xem liên kết).

Để có xấp xỉ nhanh, FryGuy đang đi đúng hướng với Simulated Annealing. Đây là một cách tiếp cận.

Ngoài ra, hãy xem Approximation algorithms for bipartite and non-bipartite matching in the plane cho sơ đồ xấp xỉ O ((n/ε)^1.5 * log^5 (n)) (1 + ε)).

Answer 2

Bạn có thể xem xét simulated annealing cho việc này. Bắt đầu bằng cách gán A [x] -> B [y] cho mỗi pixel, ngẫu nhiên và tính tổng các khoảng cách bình phương. Sau đó hoán đổi một cặp x < -> y ánh xạ, ngẫu nhiên. Sau đó chọn chấp nhận điều này với xác suất Q, trong đó Q cao hơn nếu ánh xạ mới tốt hơn và có xu hướng về không theo thời gian. Xem bài viết wikipedia để có giải thích tốt hơn.

Answer 3

1. Sắp xếp điểm ảnh trong hình A: thứ tự tăng dần của 'x' và sau đó 'y' phối
2. Sắp xếp điểm ảnh trong hình B: trong việc giảm thứ tự 'x' và sau đó tăng 'y'

Pixel bản đồ tại cùng một chỉ mục: trong danh sách được sắp xếp, pixel đầu tiên trong A sẽ ánh xạ tới điểm ảnh đầu tiên trong B. Đây có phải là bản đồ bạn đang tìm không?