Có các thuật toán để tính toán các ranh giới giới hạn của sprites được vẽ trên nền đơn sắc không?

Question

Hãy tưởng tượng một bitmap hình chữ nhật đơn giản có kích thước 1024x768 pixel được tô màu trắng. Có một vài (không chồng chéo) sprites rút ra vào bitmap: vòng tròn, hình vuông và hình tam giác. Có một thuật toán (thậm chí có thể thực hiện C++), với bitmap và màu là màu nền (màu trắng, trong ví dụ trên), tạo ra một danh sách chứa các hình chữ nhật nhỏ nhất cho mỗi sprites ?

Dưới đây là một số mẫu: Ở bên trái, bạn có thể thấy bitmap mẫu mà mã của tôi được cung cấp (cùng với thông tin 'nền' màu trắng). Ở bên phải bạn có thể thấy cùng một hình ảnh cùng với các hình chữ nhật giới hạn của bốn hình dạng (màu đỏ); thuật toán tôi đang tìm kiếm tính toán hình học của các hình chữ nhật này.

Input picture http://s1.directupload.net/images/111215/ruycwlgl.pngOutput picture http://s1.directupload.net/images/111215/encr84ps.png

Một số phần mềm đồ hoạ có một tính năng tương tự cho việc lựa chọn hình dạng: họ thậm chí có thể tính toán đa giác ranh giới dường như tùy ý. Thay vì kéo một hình chữ nhật lựa chọn theo cách thủ công, bạn có thể nhấp vào 'nền' (nền là gì và những gì không được xác định bởi một số ngưỡng) và sau đó công cụ tự động tính hình dạng của đối tượng được vẽ lên nền. Tôi cần một cái gì đó như thế này, ngoại trừ việc tôi hoàn toàn ổn nếu tôi chỉ có những vùng hình chữ nhật cho các đối tượng.

Tôi đã nhận biết được OpenCV; nó dường như có liên quan (nó có vẻ là một thư viện bao gồm mọi thuật toán đồ họa mà tôi có thể nghĩ đến - và sau đó là một số) nhưng với số lượng thông tin nhanh, tôi không thể tìm ra cách để thuật toán tôi đang nghĩ đến. Tôi sẽ ngạc nhiên nếu OpenCV không thể làm được điều này, nhưng tôi e rằng bạn phải có bằng tiến sĩ để sử dụng nó. :-)

Answer 1

Dưới đây là bài viết tuyệt vời về đề tài này:

http://softsurfer.com/Archive/algorithm_0107/algorithm_0107.htm

Tôi nghĩ rằng tiến sĩ mà không được yêu cầu ở đây :)

Answer 2

Đây là những suy nghĩ đầu tiên của tôi, không ai phức tạp, ngoại trừ việc phát hiện cạnh

For each square, 
    if it's not-white 
     mark as "found" 
     if you havn't found one next to it already 
      add it to points list 
for each point in the points list 
    use basic edge detection to find outline 
    keep track of bounds while doing so 
    add bounds to shapes list 
remove duplicates from shapes list. (this can happen for concave shapes) 

Tôi chỉ nhận ra điều này sẽ xem xét trắng "lỗ" (như trong hình tròn tận cùng bên trái của bạn trong mẫu của bạn) để được đó là hình dạng của riêng nó. Nếu "vòng lặp" đầu tiên là tràn ngập, nó không có vấn đề này, nhưng sẽ chậm hơn nhiều/chiếm nhiều bộ nhớ hơn.

Các phát hiện cạnh cơ bản tôi đã nghĩ đến việc rất đơn giản:

given eight cardinal directions left, downleft, etc... 
given two relative directions cw(direction-1) and ccw(direction+1) 
starting with a point "begin" 
set bounds to point 
find direction d, where the begin+d is not white, and begin+cw(d) is white. 
set current to begin+d 
do 
    if current is outside of bounds, increase bounds 
    set d = cw(d) 
    while(cur+d is white or cur+ccw(d) is not white) 
     d = ccw(d) 
    cur = cur + d; 
while(cur != begin 

http://ideone.com/

Có một khá một vài trường hợp cạnh không xem xét ở đây: những gì nếu bắt đầu là một điểm duy nhất, những gì nếu nó chạy đến rìa của hình ảnh, nếu điểm bắt đầu chỉ rộng 1 px, nhưng có các đốm màu ở hai bên, có thể là các phần khác ... Nhưng thuật toán cơ bản không phức tạp.