Tạo lại hình ảnh chỉ sử dụng hình vuông chồng chéo

Question

Tôi đang cố gắng chụp ảnh nguồn và tạo lại hình ảnh đó trên khung trong suốt chỉ sử dụng hình vuông có màu đơn sắc chồng lên nhau. Mục tiêu là sử dụng càng ít ô vuông càng tốt.

Nói cách khác, tôi lấy một hình ảnh trong suốt trống và vẽ các hình vuông có nhiều màu khác nhau cho đến khi tôi tạo lại hình ảnh nguồn, với mục tiêu là sử dụng ít ô vuông nhất có thể.

Ví dụ:

Đây là một hình ảnh nguồn. Nó có hai màu: đỏ và xanh lục. Tôi chỉ muốn sử dụng các ô vuông , có thể chồng lên nhau, để tạo lại hình ảnh nguồn.

Giải pháp lý tưởng sẽ là một hình vuông màu đỏ lớn, và sau đó là hai hình vuông màu xanh được vẽ trên đầu - đó là những gì tôi muốn thuật toán của tôi tìm thấy, với bất kỳ hình ảnh nguồn nào - vị trí, kích thước, màu sắc và thứ tự của mỗi ô vuông.

---

hình ảnh mục tiêu của tôi rằng tôi có ý định để xử lý là thế này:

(8x mở rộng)

Nó có 1411 pixel không trong suốt (trường hợp xấu nhất), và với một giải pháp bạo lực không sử dụng hình vuông chồng chéo, tôi đã tạo lại hình ảnh bằng cách sử dụng 1246 ô vuông.

---

giải pháp hiện tại của tôi là một phương pháp brute force dọc theo dòng:

1. Tạo một danh sách tất cả các màu sắc được sử dụng trong hình ảnh nguồn. Mỗi mục là một "lớp". Một lớp có một màu và một mảng 2D đại diện cho các điểm ảnh. Thứ tự quan trọng, nhưng tôi không biết thứ tự các lớp cần là gì, nên ban đầu nó tùy ý.
2. Đối với mỗi lớp trong danh sách, khởi tạo mảng 2D. Mỗi phần tử tương ứng với một pixel trong hình ảnh nguồn. Các pixel có cùng màu với màu được chọn của lớp được đánh dấu là '1'. Các điểm ảnh nằm trong một lớp Ở trên lớp hiện tại được đánh dấu là "không quan tâm". Tất cả các pixel khác được đánh dấu là '0'.
3. Sử dụng một số thuật toán để xử lý từng lớp, sử dụng số lượng hình vuông nhỏ nhất để tiếp cận mọi pixel được đánh dấu '1', mà không chạm vào bất kỳ pixel nào được đánh dấu '0'.
4. Sắp xếp thứ tự các lớp và quay lại Bước 2. Thực hiện việc này cho mọi kết hợp có thể có của các lớp, sau đó kiểm tra xem thứ tự nào sử dụng số lượng ô vuông tối thiểu trong tổng số.

Ai đó có lẽ là giải thích tốt hơn trong phản hồi; nhưng kiểm tra lực lượng vũ phu mỗi hoán vị là không khả thi, bởi vì hình ảnh mục tiêu của tôi có 31 màu (kết quả là 31 hoán vị).

Đối với lý do tại sao tôi làm điều này? Tôi đang cố gắng tạo ra một hình ảnh trong một trò chơi (Starbound), nơi tôi chỉ có thể sử dụng hình vuông. Giải pháp lười biếng là sử dụng một hình vuông cho mỗi pixel, nhưng đó chỉ là quá nhiều ô vuông.

Answer 1

Chỉ là đề xuất cho giải pháp khả thi. Tôi đã không thử nó.

Đó là cách tiếp cận tham lam.

Đối với mỗi pixel, tính toán hình vuông đồng nhất lớn nhất có chứa nó.

Sau đó chọn lớn nhất trong tất cả các hình vuông và đánh dấu tất cả các điểm ảnh mà nó bao phủ là "được bao phủ".

Sau đó, trong số tất cả các điểm ảnh không được đánh dấu, chọn hình vuông bao phủ lớn nhất, v.v. cho đến khi không còn pixel nào được đánh dấu.

Quan hệ không thành vấn đề, chỉ cần lấy bất kỳ hình vuông lớn nhất nào và đánh dấu pixel của nó.

CẬP NHẬT: chồng chéo cung cấp cơ hội giảm số lượng ô vuông.

Xem xét tất cả các hoán vị có thể có của thứ tự điền của các hình dạng. Các hình dạng được vẽ đầu tiên, trên các lớp dưới cùng, có thể được (một phần) ẩn bởi một số người khác. Xử lý các hình dạng bắt đầu từ lớp trên cùng. Khi bạn xử lý một hình dạng để liên kết mọi pixel với hình vuông đồng nhất lớn nhất có chứa nó, hãy xử lý tất cả các pixel được bao phủ mà không quan tâm.

Trong ví dụ đã cho, trước tiên hãy điền các ô màu xanh lục; sau đó khi lấp đầy hình vuông màu đỏ, các pixel màu xanh lá cây có thể được coi là màu đỏ hay không, tùy thuộc vào sự tiện lợi.

Nếu bạn không thể thử tất cả các hoán vị, hãy thử chúng một cách ngẫu nhiên. Các phương pháp tiếp cận heuristic như thuật toán di truyền hoặc ủ mô phỏng có thể hữu ích. Không có gì đơn giản ở đây.

Answer 2

Sẽ rất khó để đảm bảo một giải pháp tối ưu. Tìm kiếm bạo lực sẽ rất lớn. Điều này đòi hỏi một heuristic.

Bắt đầu ở các cạnh. Đi bộ cạnh bên ngoài, tìm màu sắc thường xuyên nhất. Vẽ hình vuông để lấp đầy nền.

Lặp lại, làm việc hướng vào vẽ hình vuông nhỏ hơn và nhỏ hơn bao gồm nhiều nhất pixel sai màu. Kết thúc bằng các ô vuông đơn pixel.

Làm việc vào trong có nghĩa là giảm kích thước của hộp giới hạn, bên ngoài trong đó tất cả các pixel là màu chính xác. Ở mỗi bước, giới hạn trên về kích thước của một hình vuông sẽ được lắp vào hộp giới hạn. Chọn các ô vuông cho điểm tốt nhất.

Điểm dựa trên màu cũ và màu mới sai hoặc phải, do đó, có 4 giá trị có thể cho mỗi pixel. Một ví dụ chức năng cho điểm mỗi pixel sẽ là:

• sai -> sai: 0
• sai -> phải: 1
• đúng -> phải: 1
• đúng -> sai: - 2

Tôi nghĩ rằng nếu bạn luôn giảm số lượng ô vuông sai trên cạnh của hộp giới hạn và không bao giờ tăng kích thước hình vuông, thì thuật toán phải dừng lại bằng giải pháp mà không cần phải quay lại. Một giải pháp backtracking có lẽ có thể làm tốt hơn.

Answer 3

Phương pháp phỏng đoán "xói mòn".

---

• xem xét tất cả các pixel phác thảo, ví dụ:có ít nhất một người hàng xóm bên ngoài hình dạng.

• Trong số các pixel này, hãy chọn một màu (điểm ảnh thường xuyên nhất?).

• Đối với tất cả các pixel phác thảo của màu này, hãy tính hình vuông lớn nhất không vượt quá hình dạng.

• Điền vào các ô vuông này, từ lớn hơn đến nhỏ hơn, cho đến khi toàn bộ đường viền được bao phủ.

• Xóa các pixel được lấp đầy chính xác và khởi động lại quy trình trên hình bị xói mòn.

---

Trong trường hợp của các hình vuông màu đỏ, tất cả các pixel phác thảo sẽ được bao phủ bởi các hình vuông màu đỏ chính nó, và điền đầu tiên sẽ "tiêu thụ" toàn bộ khu vực.

Sau đó, xóa các pixel được bao phủ bằng màu đỏ, hai ô vuông màu xanh lá cây sẽ vẫn giữ nguyên.

Tất cả các điểm phác thảo màu xanh lá cây bây giờ sẽ được bao phủ bởi hai ô vuông màu xanh lá cây và hai lần lấp đầy đầu tiên sẽ "tiêu thụ" tất cả khu vực màu xanh lục.