tìm các điểm yên theo chiều cao 3d

Question

Đặt bản đồ chiều cao 3d (từ máy quét laser), làm cách nào để tìm thấy saddle points?

I.e. một cái gì đó cho như thế này:

Tôi đang tìm kiếm cho tất cả các điểm mà độ cong dương theo một hướng và tiêu cực trong khác.

(Các hướng này không cần phải căn chỉnh với trục X và Y. Tôi biết cách kiểm tra độ cong theo hướng X có dấu trái ngược với độ cong theo hướng Y hay không, nhưng không bao gồm tất cả các trường hợp . để làm cho vấn đề tồi tệ hơn, độ phân giải trong X là khác biệt so với độ phân giải trong Y)

Lý tưởng nhất tôi đang tìm kiếm một thuật toán có thể chịu đựng được một số lượng tiếng ồn và chỉ đánh dấu "đáng kể" điểm yên ngựa.

Answer 1

(Từ đoán tại toán học chứ không phải là kinh nghiệm thực tế)

Fit một bậc lên bề mặt trong một bản vá nhỏ xung quanh mỗi điểm ứng cử viên, ví dụ với ít ô vuông nhất. Làm thế nào lớn các bản vá là một cách để kiểm soát tiếng ồn, và bạn có thể đạt được bằng cách trọng điểm tùy thuộc vào khoảng cách của họ từ điểm ứng cử viên. Trong ký hiệu ma trận, bạn có thể biểu diễn bậc hai là x'Ax + b'x + c, trong đó A là đối xứng.

Phương trình bậc hai sẽ có độ dốc bằng không tại x = (A^-1) b/2. Nếu điều này không nằm trong bản vá, hãy loại bỏ nó.

Nếu A có cả giá trị + ve và -giá trị riêng, bạn có điểm yên tại x. Vì A chỉ là 2x2 và do đó có nhiều nhất hai giá trị riêng, bạn có thể bỏ qua trường hợp khi nó là một giá trị riêng và không thể đảo ngược nó ở giai đoạn trước.

Answer 2

Tôi đã khám phá một vấn đề tương tự cho lớp học topo tính toán và đã có một số thành công với phương pháp được nêu bên dưới.

Trước tiên, bạn sẽ cần một hàm so sánh sẽ đánh giá chiều cao tại hai điểm đầu vào và sẽ trả lại < hoặc> (không bằng) cho bất kỳ đầu vào nào. Một cách để làm điều này là nếu các điểm có chiều cao bằng nhau, bạn sử dụng một số chỉ số dựa trên vị trí hoặc ngẫu nhiên để tìm điểm lớn hơn. Bạn có thể nghĩ về điều này như thêm một sự nhiễu loạn vô cùng tối cao.

Bây giờ, đối với mỗi điểm, bạn sẽ so sánh chiều cao ở tất cả các hàng xóm xung quanh (sẽ có 8 người hàng xóm trên lưới hình chữ nhật 2D). Liên kết thấp hơn cho một điểm sẽ là tập hợp của tất cả các nước láng giềng có chiều cao nhỏ hơn điểm.

Nếu tất cả các giá trị lân cận nằm trong liên kết thấp hơn, bạn đang ở mức tối đa địa phương. Nếu không có điểm nào trong liên kết thấp hơn bạn đang ở mức tối thiểu địa phương. Nếu không, nếu liên kết thấp hơn là một bộ kết nối đơn, bạn đang ở một điểm thường xuyên trên một sườn dốc. Nhưng nếu liên kết thấp hơn là hai bộ chưa kết nối, bạn đang ở yên.

Trong 2D, bạn có thể xây dựng danh sách 8 điểm lân cận theo thứ tự tuần hoàn xung quanh điểm bạn đang kiểm tra. Bạn chỉ định giá trị +/- 1 cho mỗi người hàng xóm tùy thuộc vào hàm so sánh của bạn. Sau đó, bạn có thể duyệt qua danh sách đó (nhớ so sánh hai điểm kết thúc) và đếm số lần dấu hiệu thay đổi để xác định số lượng thành phần được kết nối trong liên kết thấp hơn.

Xác định bộ đệm nào là "quan trọng" là phân tích khó hơn. Bạn có thể xem xét điều này: http://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Gyulassy08.pdf để được hướng dẫn.

-Michael