Cấu trúc dữ liệu để nhận dạng mẫu dựa trên pixel

Question

Tôi có một ứng dụng tạo hình ảnh ngẫu nhiên dựa trên các ràng buộc. Các pixel màu khác nhau được chọn ngẫu nhiên và được đặt trong một lưới đáp ứng tất cả các ràng buộc. Ví dụ (đơn giản hóa), có thể có một ràng buộc cho biết nếu một pixel màu xanh hoặc màu xanh lá cây là (0, -1) và pixel màu đỏ là (-1, -1) và (-1, 0), sau đó đặt một điểm ảnh màu trắng bị cấm. Các toạ độ này là các vectơ từ vị trí hiện tại (tức là vùng lân cận).

Ngay bây giờ tôi đang lưu trữ các ràng buộc trong một mảng và lặp qua chúng, kiểm tra xem mỗi loại có áp dụng hay không. Tôi phải làm điều này cho mỗi pixel tôi đặt trong lưới. Vì vậy, hiệu suất bị hạn chế thêm. Ngoài ra, có thể có hai ràng buộc trong xung đột nhưng không dễ để kiểm tra điều đó. Tôi nghĩ rằng cấu trúc dữ liệu kiểu biểu đồ (cây?) Có thể là cách để lưu trữ tất cả các ràng buộc sao cho tôi có thể nhanh chóng xác định từ vùng lân cận pixel mà (nếu có) các ràng buộc áp dụng. Nhưng tôi không thể tìm ra cách để tạo ra một cấu trúc như vậy, với điều kiện một tọa độ duy nhất có thể chứa nhiều màu sắc và cách kết hợp một tập hợp các tọa độ/màu để thiết lập các màu pixel bị cấm. Ý tưởng nào?

Answer 1

Bạn có thể sử dụng cắt đồ thị để giải quyết vấn đề này. Nó thậm chí sẽ chăm sóc các cuộc xung đột được đề cập. Đây là cơ bản cách hoạt động: nó cố gắng gán nhãn dựa trên một hàm chi phí mà bạn muốn giảm thiểu.Trong trường hợp của bạn, hàm chi phí có thể là một cái gì đó như:

E(x)=infinite ; if constraint is violated 
and 0  ; otherwise 

Cắt đồ thị sẽ gán nhãn giảm thiểu chức năng chi phí này. Thêm vào đó, nó rất nhanh và hiệu quả và hội tụ với minima. Hãy nhìn vào hai tài liệu tham khảo sau đây:

1. Graph cuts for energy Minimization
2. Code for implementing graph cut

Các liên kết thứ hai cung cấp mã readymade cho cắt đồ thị, nơi bạn có thể sử dụng hàm chi phí của riêng bạn mà là để được giảm thiểu (và có thể phụ thuộc vào các giá trị hàng xóm như trong trường hợp của bạn).

Answer 2

Đối với vấn đề này, bạn có thể sử dụng các loại cây khác nhau.

Điều này có vẻ là chủ đề được nghiên cứu rộng rãi và có lẽ câu trả lời sẽ dài hơn bình thường so với câu trả lời SO bình thường. Tham khảo liên kết tiếp theo:

https://books.google.co.uk/books?id=ixDjBQAAQBAJ&pg=PA119&lpg=PA119&dq=best+data+structure+for+pattern+recognition&source=bl&ots=BLEx5TOrW9&sig=d_1HjGTeQ7SptvHJ0iZ_yXUG5Vo&hl=sl&sa=X&ei=dgI6VYDTKZPVapmTgdgD&ved=0CFcQ6AEwCA#v=onepage&q=best%20data%20structure%20for%20pattern%20recognition&f=false

http://www.computer.org/csdl/trans/ts/1977/02/01702419.pdf

http://www.ablesw.com/3d-doctor/3dseg.html

Answer 3

havent làm việc với mô hình kết hợp, nhưng những gì nói đến cái tâm là:

Hãy ds đồ thị thông thường nơi đỉnh sẽ là của bạn vectơ và các cạnh sẽ bị cấm màu sắc kết nối chúng. Ở đây bạn có thể kết nối tất cả các đỉnh giữa nhau, tối ưu hơn sẽ có một số hướng mà bạn sẽ sử dụng điền vào ds của bạn, bạn nên sử dụng cùng một điểm bắt đầu và hướng khi bạn sẽ đi qua mảng pixel. Từ ví dụ của bạn nếu bạn bắt đầu từ (0, -1) theo chiều kim đồng hồ, nó sẽ giống như sau: (0, -1) - xanh - (-1, -1), (0, -1) --green - (-1, -1), (-1, -1) --red - (-1, 0), (-1, 0) --red - (- 1, 1), (-1 , 1) --white - (0, 1), (-1, 1) --white-- (1, 1), (-1, 1) --white-- (1, 0)

Bây giờ hãy sử dụng DFS để tìm kiếm màu sắc để kiểm tra (nó sẽ là cạnh)

Answer 4

Dường như với tôi lựa chọn thuận tiện sẽ là cây kd. Bằng cách lưu trữ các ràng buộc của bạn trong một cây kd, bạn có thể truy cập các ràng buộc áp dụng với một kiểu truy vấn lân cận gần nhất.

Tôi khuyên bạn nên xem sách Algorithms in a Nutshell. Bạn có thể tìm thấy số easy implementation của cây kd có thể áp dụng cho vấn đề của bạn.

Tuy nhiên, hãy nhớ rằng nếu các ràng buộc không được phân bố đồng đều trong cảnh của bạn, thì cây kết quả có thể không cân bằng tốt. Trong trường hợp này, bạn nên tìm một biểu diễn tốt hơn cho các ràng buộc, hoặc độ phức tạp thực tế của thuật toán sẽ gần với giá trị tệ nhất O (n), chứ không phải giá trị trung bình (và tốt nhất) O (log n).