So sánh cấu trúc ba chiều

Question

Tôi cần đánh giá xem hai tập hợp các điểm 3d có giống nhau hay không (bỏ qua các bản dịch và phép quay) bằng cách tìm và so sánh một băm hình học thích hợp. Tôi đã làm một số nghiên cứu giấy về kỹ thuật băm hình học, và tôi tìm thấy một vài thuật toán, tuy nhiên có xu hướng phức tạp bởi "yêu cầu tầm nhìn" (ví dụ: 2d đến 3d, occlusions, shadows, etc).

Hơn nữa, tôi rất thích điều đó, nếu hai hình học hơi khác một chút, các băm cũng không khác lắm.

Có ai biết một số thuật toán phù hợp với nhu cầu của tôi và có thể cung cấp một số liên kết để nghiên cứu sâu hơn không?

Cảm ơn

Answer 1

Đây là cách tôi sẽ làm điều đó:

1. Chức bộ ở trung tâm của khối
2. Tính inertia tensor. Điều này cho bạn ba trục tọa độ. Xoay chúng. [*]
3. Viết ra danh sách các điểm theo một thứ tự nhất định (ví dụ: từ trên xuống dưới, từ trái sang phải) với độ chính xác được yêu cầu của bạn.
4. Áp dụng bất kỳ thuật toán nào bạn muốn cho một mảng kết quả.

Để so sánh hai bộ, trừ khi bạn cần lưu trước kết quả băm, chỉ cần áp dụng thuật toán so sánh yêu thích của bạn cho tập hợp các điểm của bước 3. Điều này có thể, ví dụ, tính toán khoảng cách giữa hai bộ .

Tôi không chắc chắn liệu tôi có thể giới thiệu cho bạn thuật toán cho bước 4 vì dường như các yêu cầu của bạn là mâu thuẫn hay không. Bất cứ thứ gì được gọi là băm thường có đặc tính là một thay đổi nhỏ trong kết quả đầu vào ở đầu ra rất khác nhau. Dù sao, bây giờ tôi đã giảm vấn đề cho một dãy số, vì vậy bạn sẽ có thể tìm ra mọi thứ.

[*] Nếu hai hoặc ba trục của bạn trùng khớp với một số phương tiện khác, ví dụ: là khoảng cách dài nhất. Nhưng điều này là cực kỳ hiếm đối với các điểm ngẫu nhiên.

Answer 2

Có vẻ như vấn đề tối ưu hóa số cho tôi. Bạn muốn tìm các tham số của phép chuyển đổi mà biến đổi một tập các điểm càng gần nhau càng tốt. Xác định một số loại dư hoặc "năng lượng" được giảm thiểu khi các điểm là trùng hợp, và mâm cặp nó ở một số tối ưu bình phương nhỏ nhất hoặc tương tự. Nếu nó quản lý để tối ưu hóa điểm số bằng không (hoặc gần như có thể được dự kiến ​​cho lỗi dấu chấm động) thì các điểm giống nhau.

Googling

least squares rotation translation 

lần lượt lên khá một tòa nhà vài giấy tờ về kỹ thuật này (ví dụ "Least-Squares Estimation of Transformation Parameters Between Two Point Patterns").

Cập nhật nhận xét sau bên dưới: Nếu một sự tương ứng giữa các điểm không được biết (như được giả định bởi bài viết trên), thì bạn chỉ cần đảm bảo rằng điểm số được thu nhỏ là độc lập với thứ tự điểm. Ví dụ, nếu bạn coi các điểm là khối lượng nhỏ (quả cầu bán kính hữu hạn để tránh nổ khoảng cách zero) và đặt ra để giảm thiểu tổng năng lượng hấp dẫn của hệ thống bằng cách tối ưu hóa các thông số xoay vòng &.

Answer 3

Có một loạt ấn phẩm SIGGRAPH có thể hữu ích cho bạn.

ví dụ: "Alignment toàn cầu Non-cứng của 3-D Quét" của Brown và Rusinkiewicz:

http://portal.acm.org/citation.cfm?id=1276404

Một tìm kiếm chung có thể giúp bạn bắt đầu:

http://scholar.google.com/scholar?q=siggraph+point+cloud+registration

Answer 4

spin images là một con đường để đi về nó.

Answer 5

Suy nghĩ đầu tiên của bạn có thể là tìm cách xoay vòng bản đồ một đối tượng này sang đối tượng khác nhưng đây là một chủ đề rất phức tạp ... và không thực sự cần thiết! Bạn không hỏi làm thế nào để phù hợp nhất với hai, bạn chỉ cần hỏi xem họ có giống nhau hay không.

Đặc trưng cho mô hình của bạn bằng danh sách tất cả khoảng cách điểm giữa. Sắp xếp danh sách theo khoảng cách đó. Bây giờ so sánh danh sách cho từng đối tượng. Chúng phải giống hệt nhau, vì khoảng cách giữa các điểm không bị ảnh hưởng bởi dịch hoặc xoay.

Ba vấn đề:

1) Điều gì nếu số lượng điểm lớn, đó là một danh sách lớn các cặp (N * (N-1)/2). Trong trường hợp này, bạn có thể chọn chỉ giữ lại những cái dài nhất, hoặc thậm chí tốt hơn, giữ 1 hoặc 2 cái dài nhất cho mỗi đỉnh sao cho mỗi phần của mô hình của bạn có một số đóng góp.Giảm thông tin như thế này tuy nhiên thay đổi vấn đề là xác suất và không xác định.

2) Điều này chỉ sử dụng các đỉnh để xác định hình dạng chứ không phải cạnh. Điều này có thể là tốt (và trong thực tế sẽ được), nhưng nếu bạn mong đợi để có con số với đỉnh giống hệt nhau nhưng các cạnh kết nối khác nhau. Nếu vậy, kiểm tra độ tương tự đỉnh đầu tiên. Nếu điều đó trôi qua, sau đó gán một nhãn duy nhất cho mỗi đỉnh bằng cách sử dụng khoảng cách được sắp xếp đó. Cạnh dài nhất có hai đỉnh. Đối với mỗi đỉnh ĐÚNG, hãy tìm đỉnh có cạnh dài nhất (còn lại). Dán nhãn đỉnh đầu tiên 0 và đỉnh tiếp theo 1. Lặp lại các đỉnh khác theo thứ tự, và bạn sẽ gán các thẻ được dịch chuyển và xoay độc lập. Bây giờ bạn có thể so sánh chính xác các cạnh trong đối tượng 1 giữa hai đỉnh, có một cạnh tương ứng giữa hai đỉnh giống nhau trong đối tượng 2) Lưu ý: điều này bắt đầu trở nên phức tạp nếu bạn có nhiều khoảng cách interpoint giống nhau và do đó bạn cần sự so sánh của bộ tách để làm cho các bài tập ổn định và độc đáo.

3) Có khả năng hai số có chiều dài cạnh giống hệt nhau nhưng chúng không giống nhau .. điều này đúng khi một đối tượng là hình ảnh phản chiếu của đối tượng kia. Điều này khá khó chịu để phát hiện! Một cách để làm điều đó là sử dụng bốn điểm không đồng phẳng (có lẽ là các điểm được gắn nhãn 0 đến 3 từ bước trước) và so sánh "độ" của hệ tọa độ mà chúng xác định. Nếu bàn tay không khớp, các vật thể là hình ảnh phản chiếu.

Lưu ý danh sách các khoảng cách cho phép bạn dễ dàng từ chối các đối tượng không giống hệt nhau. Nó cũng cho phép bạn thêm chấp nhận "mờ" bằng cách cho phép một số lượng lỗi nhất định trong các lệnh. Có lẽ lấy sự khác biệt bình phương gốc giữa hai danh sách là một "biện pháp tương tự" sẽ hoạt động tốt.

Chỉnh sửa: Dường như vấn đề của bạn là đám mây điểm không có cạnh. Sau đó, các vấn đề gây phiền nhiễu của thư từ cạnh (# 2) thậm chí không áp dụng và có thể được bỏ qua! Tuy nhiên, bạn vẫn phải cẩn thận với vấn đề về hình ảnh gương.

Answer 6

1. Nếu bạn muốn ước tính cứng nhắc chuyển giữa hai đám mây điểm tương tự bạn có thể sử dụng cũng như thành lập lặp gần nhất Point phương pháp. Phương pháp này bắt đầu với ước tính thô của phép biến đổi và sau đó tối ưu hóa lặp lại cho phép chuyển đổi , bằng cách tính toán hàng xóm gần nhất và giảm thiểu hàm chi phí liên quan . Nó có thể được thực hiện một cách hiệu quả (thậm chí thời gian thực) và có sẵn triển khai sẵn sàng cho matlab, C++ ... Phương pháp này đã được mở rộng và có nhiều biến thể, bao gồm ước lượng không cứng nhắc biến dạng, nếu bạn quan tâm trong các tiện ích mở rộng, bạn nên xem Các giấy tờ đồ họa máy tính giải quyết vấn đề đăng ký quét , trong đó vấn đề của bạn là một bước quan trọng. Đối với điểm xuất phát, hãy xem Wikipedia page on Iterative Closest Point có một số liên kết tốt bên ngoài . Chỉ cần một hình ảnh trêu ghẹo từ một matlab implementation được thiết kế để phù hợp với chỉ những đám mây: alt text http://www.mathworks.com/matlabcentral/fx_files/12627/1/icp.gif

   Sau khi sắp xếp, bạn có thể đo lường lỗi cuối cùng để nói như thế nào tương tự như các hai đám mây điểm là, nhưng đây là rất nhiều một Adhoc giải pháp, có nên là một giải pháp tốt hơn.

2. Sử dụng mô tả hình dạng một lon dấu vân tay tính toán của các hình dạng mà thường bất biến dưới dịch/quay. Trong hầu hết các trường hợp, chúng được định nghĩa cho các mắt lưới và không phải là các đám mây điểm, tuy nhiên có vô số các bộ mô tả hình dạng, do đó tùy thuộc vào đầu vào và các yêu cầu của bạn, bạn có thể tìm thấy một cái gì đó hữu ích. Đối với điều này, bạn sẽ muốn nhìn vào lĩnh vực shape analysis, và có lẽ this 2004 SIGGRAPH course presentation có thể cung cấp cho một cảm giác về những gì mọi người làm để tính toán mô tả hình dạng.

Answer 7

Có thể bạn cũng nên đọc kỹ thuật toán RANSAC. Nó thường được sử dụng để ghép các hình ảnh toàn cảnh với nhau, có vẻ hơi giống với vấn đề của bạn, chỉ trong 2 chiều. Chỉ cần google cho RANSAC, ảnh toàn cảnh và/hoặc khâu để bắt đầu.