2011-08-16 25 views
8

Tôi đang làm việc trong OpenCV nhưng tôi không nghĩ rằng có một chức năng cho việc này. Tôi có thể tìm thấy một chức năng để tìm biến đổi affine, nhưng biến đổi affine bao gồm mở rộng quy mô, và tôi chỉ muốn xem xét việc xoay + dịch.căn chỉnh một bộ điểm 2d với một điểm khác bằng cách sử dụng bản dịch và xoay

Hãy tưởng tượng tôi có hai bộ điểm trong 2ngày - giả sử mỗi bộ có chính xác 50 điểm.

Ví dụ: đặt A = {x1, y1, x2, y2, ..., x50, y50}

đặt B = {x1 ', y1', x2 ', y2', ..., x50 ', y50'}

Tôi muốn tìm kết hợp xoay và dịch gần nhất với bộ bản đồ A thành bộ B. Tôi đoán tôi sẽ xác định "gần nhất" làm giảm khoảng cách trung bình giữa các điểm trong A và các điểm tương ứng trong BIe, giảm thiểu mức trung bình khoảng cách giữa (x1, y1) và (x1 ', y1'), v.v.

Tôi đoán tôi có thể sử dụng kiểm tra sức mạnh tất cả các phép dịch và phép quay nhưng điều này sẽ cực kỳ không hiệu quả. Có ai biết một cách đơn giản hơn?

Cảm ơn!

+0

Có sự tương ứng một-một giữa các điểm không? Họ thực sự là cùng một điểm và bạn chỉ cần tìm sự chuyển đổi? – phkahler

Trả lời

6

Vấn đề này có một giải pháp rất thanh lịch về phân tích giá trị số ít của ma trận lân cận (khoảng cách giữa các cặp điểm). Tên của điều này là orthogonal Procrustes problem, sau truyền thuyết Hy Lạp về một người đã cung cấp cho du khách một chiếc giường phù hợp với bất kỳ ai.

Giải pháp đến từ việc tìm ma trận trực giao gần nhất với ma trận đã cho (không nhất thiết trực giao).

+1

cảm ơn. Tôi tìm thấy cùng một giải pháp xung quanh về thời gian mà bạn đăng câu trả lời của bạn: http://en.wikipedia.org/wiki/Procrustes_analysis – Andrew

+2

@Andrew: Đó là một ứng dụng gọn gàng/đáng ngạc nhiên của SVD, có vẻ như với tôi. Các giải pháp của Peter Schonemann được thúc đẩy bởi một ứng dụng để kiểm tra các số liệu trong tâm lý học/khoa học xã hội. Để chắc chắn nếu bạn có ý định loại trừ các phản xạ (trái ngược với các bản dịch và phép quay), cần phải chỉnh sửa một chút các giá trị số ít. – hardmath

0

Cách tôi thực hiện trong Excel là tạo một vài cột đại diện cho các điểm. Các tế bào biểu thị xoay/dịch của một bộ (không cần xoay và dịch cả hai). Sau đó, các cột đại diện cho những điểm giống nhau được xoay/dịch.
Sau đó, một cột khác cho khoảng cách giữa các điểm của điểm được dịch/xoay.
Sau đó, một ô của tổng khoảng cách giữa các điểm. Cuối cùng, hãy sử dụng Bộ giải để tối ưu hóa các ô xoay và dịch.

+0

cảm ơn câu trả lời của bạn. tôi đã có thể làm những gì tôi cần bằng cách tính điểm trung bình cho mỗi bộ để tính toán bản dịch, và sau đó sử dụng trang này để tìm ra góc quay http://en.wikipedia.org/wiki/Procrustes_analysis – Andrew

0

Nếu bạn sửa một số vòng quay, bạn có thể nhận được câu trả lời bằng cách sử dụng ternary search. Chạy tìm kiếm trong x và cho mỗi x thử nghiệm chạy nó trong y để có được giá trị tốt nhất. Điều này sẽ cung cấp cho bạn câu trả lời chính xác vì hàm (tổng khoảng cách tương ứng) là lồi (điều này có thể được chứng minh bằng cách quan sát rằng hạn chế của hàm cho bất kỳ dòng nào là hàm lồi một chiều, và cuối cùng là một thực tế tiêu chuẩn: tổng của một số hàm lồi là lồi). Thay vì bạo lực trên góc, tôi có thể đề xuất phương pháp như vậy dựa trên tìm kiếm thứ ba. Chọn một số bước không lớn lắm S. Tính toán hàm mục tiêu cho mọi góc trong (0, S, 2S, ...). Sau đó, nếu S đủ nhỏ, chúng ta có thể loại trừ một số phân đoạn (iS, (i + 1) S). Cụ thể là những cái có giá trị tương đối lớn với các góc iS và (i + 1) S. Được thực hiện một cách cẩn thận, điều này có thể đưa ra câu trả lời và có thể làm nhanh hơn so với lực lượng vũ phu.

+1

cảm ơn câu trả lời của bạn . tôi đã có thể làm những gì tôi cần bằng cách tính điểm trung bình cho mỗi bộ để tính toán bản dịch, và sau đó sử dụng trang này để tìm ra góc quay http: //en.wikipedia.org/wiki/Procrustes_analysis – Andrew

+0

Bạn sẽ không nhận được bất kỳ xấp xỉ nào tốt cho câu trả lời bằng cách sử dụng điểm trung bình ngay cả trong trường hợp một chiều. Ví dụ: một bộ (0, 2, 100) có nghĩa là 34, số khác là (0, 50, 100) với giá trị trung bình 50. Sau khi di chuyển, bạn sẽ nhận được (16, 18, 116) và kết quả là 16 + 32 + 16 = 64. Nhưng nếu bạn không di chuyển bạn sẽ nhận được chỉ 48. Và thậm chí xoay trên máy bay sẽ không giúp đỡ ở đây. –

+0

@SergeyBankevich: Sử dụng giá trị trung bình là bản dịch giảm thiểu khoảng cách ** ** trung bình **, có xu hướng có giá trị hơn khoảng cách trung bình – Eric

Các vấn đề liên quan