2009-12-03 45 views
7

Tôi đang cố gắng tạo bitmap khá lớn trong ứng dụng C# (6000x6000, mặc dù hầu hết là trong suốt) và cần vẽ chúng vào API đầu ra cụ thể chỉ hỗ trợ vẽ hình chữ nhật.Thuật toán để giảm hình ảnh thành hình chữ nhật?

Bây giờ, tôi tự hỏi liệu có ai có thuật toán để giảm bitmap thành một chuỗi hình chữ nhật được tô màu của các ảnh bitmap có màu tương tự hay không; kể từ khi vẽ tất cả mọi thứ như một hình chữ nhật 1x1 là cách quá chậm cho mục đích này. Ví dụ, một vòng tròn nên được giảm xuống một hình chữ nhật trung tâm lớn, trong khi phần còn lại của vòng tròn được giảm xuống thành hình chữ nhật hiệu quả. Thuật toán thậm chí không cần phải nhanh như vậy, vì phần lớn thời gian được thực hiện bằng phương pháp đơn pixel của tôi là bằng cách lặp qua từng hình chữ nhật trên chính API đó.

+0

Tôi cho rằng bạn không muốn cho phép thuật toán thay đổi pixel để giảm số lượng hình chữ nhật? Ngoài ra, bạn có bất kỳ ý tưởng về những đặc điểm của các hình dạng sẽ được? Các hình dạng như hình tròn có nhiều đường thẳng đứng hoặc nằm ngang sẽ có nhiều hình chữ nhật hơn. –

Trả lời

3

Có vẻ như bạn cần cấu trúc cổ điển QuadTree. Xem liên kết này để có một giải thích tốt đẹp về cách bạn sẽ sử dụng một quadtree để định lượng một hình ảnh thành hình chữ nhật.

Đây là tài liệu tham khảo thú vị về CodeProject cung cấp mẫu, triển khai đơn giản mà bạn có thể thay đổi theo nhu cầu của mình.

+0

Có một ví dụ điển hình nào về việc khi cây quad tạo ra ít pixel hơn một dòng ngây thơ bằng thuật toán dòng không? Trong ví dụ trong liên kết đầu tiên, biểu diễn cây quad mất 22 hình chữ nhật để vẽ hình dạng màu xanh lá cây so với 28 nếu thực hiện pixel theo pixel, và chỉ 8 nếu được thực hiện từng dòng như tôi mô tả trong trả lời của tôi. Tôi có thể thấy cách cây quad là tuyệt vời cho việc phân vùng và lưu trữ, nhưng không phải cách chúng tối ưu để phân tách thành ít hình chữ nhật nhất có thể. –

+0

Ví dụ trong liên kết đầu tiên có thể được thực hiện trong 3 hình chữ nhật chồng chéo hoặc 5 hình chữ nhật không chồng chéo; bạn đang cố gắng đạt phiên bản nào? – Dolphin

+0

Tôi thấy cách tạo hình ảnh đó bằng 3 hoặc 5 hình chữ nhật. Những gì tôi không thể tìm ra là làm thế nào mà liên quan đến cây quad. –

0

Thuật toán đơn giản để triển khai sẽ là vẽ hình chữ nhật 1xN.

Bắt đầu trên dòng 0 và tìm điểm ảnh không trống đầu tiên. Tiếp tục lặp qua pixel cho đến khi màu của các pixel bạn đang xem thay đổi. Bây giờ, vẽ một chuỗi các điểm ảnh có màu giống như hình chữ nhật 1xN.

Nếu ảnh thực tế của bạn có các vùng đồng nhất lớn, điều này có thể là "đủ tốt". Tùy thuộc vào hình ảnh trông như thế nào, việc vẽ các đường thẳng đứng có thể tốt hơn.

Nếu tôi thực hiện phép toán, sử dụng phương pháp này, vòng tròn bán kính 100 pixel sẽ sử dụng 200 "đường" để vẽ, thay vì 30.000 pixel nếu thực hiện một pixel tại một thời điểm. Dường như với tôi một phân tích cây quad sẽ sử dụng ít nhất 1000 hình chữ nhật hoặc nhiều hơn cho một vòng tròn như vậy, nếu bạn có may mắn với nơi góc phần tư giảm.

Các vấn đề liên quan