Thuật toán cho vị trí tối ưu của các vùng bị cắt để chụp các đối tượng địa lý (đốm) trong một hình ảnh

Question

Tôi có một hình ảnh lớn chứa các "đốm màu" quan tâm trên nền. Tôi có vị trí (centroid, bounding box, area) của tất cả các đốm màu. Tôi muốn cắt một số vùng có giới hạn kích thước cố định trong hình ảnh cho phép tôi chụp hầu hết các đốm màu. Ví dụ dưới đây cho 1, 2 hoặc 3 vùng bị cắt trong cùng một hình ảnh.

Ví dụ này cho thấy rằng cắt xén 1 khu vực (màu đỏ) là tương đối dễ dàng: chỉ cần chọn khu vực với càng nhiều đốm màu càng tốt. Điều này có thể được giải quyết bằng cách chỉ cần cố gắng tất cả mọi thứ hoặc có thể bằng cách tính toán mật độ của các đốm màu bằng cách sử dụng một bộ ước lượng mật độ hạt nhân hoặc một cái gì đó như thế này.

Nhưng cắt xén 2 vùng (có màu xanh dương) không chỉ là cắt xén vụ mùa tốt nhất tiếp theo sau lần chọn đầu tiên ở trên. Đây là một vấn đề mới mà tôi cần phải tìm ra sự kết hợp tối ưu của 2 vụ. Việc thử tất cả các kết hợp của 2 vụ (lực lượng vũ phu) có thể trở nên quá tốn kém tính toán (tôi có nhiều hình ảnh để xử lý và chúng lớn).

Tương tự, việc cắt xén 3 vùng (màu xanh lục) là một vấn đề mới và một vấn đề mà lực lượng vũ phu thậm chí còn ít phù hợp hơn. Trong ví dụ cụ thể 2 của 3 vùng là giống với trường hợp màu xanh và một vùng mới được thêm vào nhưng đây không phải là trường hợp chung (tôi chỉ muốn hiển thị một kịch bản hơi phức tạp).

Tôi không có ý tưởng về thuật toán để giải quyết trường hợp n-cây trồng. Tôi tự hỏi nếu có một giải pháp lý thuyết/nổi tiếng cho vấn đề này.

Ngoài ra:

• hình học của vấn đề là xấp xỉ bằng các ví dụ trên (tối đa hai loại cây trồng so với chiều cao của hình ảnh, nhiều loại cây trồng so với chiều rộng); trong trường hợp đơn giản hóa mọi thứ
• cây trồng không nên giao
• blobs nên được như là trung tâm càng tốt trong cây trồng (tức https://dl.dropboxusercontent.com/u/1047321/SO_crop/cutout_one_blob.png )
• cây trồng nên ở trong ranh giới hình ảnh ban đầu (x hoặc ví dụ trên)
• khu vực của blob nên được đưa vào tài khoản (tôi quan tâm nhiều hơn các đốm màu lớn hơn những cái nhỏ); nhưng có thể có thể được giới thiệu trong bất kỳ thuật toán nào bằng cách liên kết trọng lượng với từng đốm màu để tính toán điểm số của từng bố cục cắt.
• bạn có thể để lại một số đốm màu. Trên thực tế, tôi có thể tính toán một thông số phức tạp về chi phí, chẳng hạn như số lượng blob mới thêm một loại cây trồng sẽ nhận được và đặt ngưỡng mà theo đó tôi ngừng thêm cây trồng.

Cảm ơn trước cho bất kỳ con trỏ nào.

PS: Ngôn ngữ mã hóa không thực sự quan trọng ở đây vì cốt lõi của thuật toán (tìm vị trí tối ưu của các loại cây trồng cho vị trí/kích thước của đốm) chỉ cần các mảng nhỏ (vị trí/kích thước ~ 100 blobs cho mỗi hình ảnh)) để được tính toán. Có thể tôi sẽ sử dụng Python hoặc R.

Answer 1

Nếu các đốm màu tương đối nhỏ như được hiển thị trong hình ảnh, bạn có thể chạy k-Means Clustering với trung tâm blob x, y pairs. Gói python scikit-learning khá trưởng thành và hoạt động tốt: http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html (hàm fit_predict của trình phân loại KMeans)

k là đầu vào và biểu thị số cụm bạn muốn. Thuật toán sẽ tách các đốm màu (mẫu) thành các cụm k (bộ). Sau đó, bạn có thể tính toán khung x, y (min-x, max-x, min-y, max-y) của mỗi bộ và cũng bao gồm các kích thước cá nhân của các đốm màu hoặc chỉ mất tối đa nếu chúng khá nhỏ.

Sau đó, bạn có thể sắp xếp các cụm theo tỷ lệ # blobs/khung hình khu vực của chúng và tổng hợp chúng, ví dụ: cho đến khi đủ các đốm màu được che phủ (xong) - hoặc tổng diện tích của bạn trở nên quá lớn (trong trường hợp đó lại chạy với k lớn hơn).