Có ai biết thuật toán lọc trung bình nhanh cho mảng 16 bit (không dấu ngắn) trong C++ không?Bộ lọc nhanh trung bình trong C++
Cái này có vẻ khá hứa hẹn, nhưng nó dường như chỉ để làm việc với mảng byte. Có ai biết làm thế nào để sửa đổi nó để làm việc với quần short hoặc một thuật toán thay thế?
Here (PDF) là một cái gì đó cho C, đó là một bài báo có tiêu đề "Tìm kiếm trung bình nhanh: triển khai ANSI C". Tác giả cho rằng đó là O (log (n)), anh ta cũng cung cấp một số mã, có thể nó sẽ giúp bạn. Nó không tốt hơn mã được đề xuất của bạn, nhưng có thể có giá trị.
Giấy được liên kết trong câu hỏi là O (1) tốt hơn O (log n). –
Đúng, nhưng điều này có thể mang lại nhiều xung động hơn, nhưng bạn chắc chắn đúng. Tôi đã thực hiện một chỉnh sửa nhỏ, làm rõ ý định của tôi. –
@MarkRansom: O (1) không tự động có nghĩa là tốt hơn O (log (n)) vì luôn luôn có một ẩn ký hiệu O. Trong trường hợp này, thuật toán O (1) chậm hơn rất nhiều so với thuật toán O (log (n)) (đối với các giá trị kênh 2 bit hoặc 4 bit). Các O (1) giấy làm việc với biểu đồ, mà làm cho thời gian chạy mỗi pixel tỷ lệ thuận với 2^b, trong đó b là số bit cho mỗi kênh, trong đó 8 bit là 256 và 16 bit là 65536 (mặc dù những con số này là hằng số, do đó O (1)). Điều này nhanh chóng làm cho thuật toán O (1) _extremely slow_ càng nhiều bit bạn thêm vào các giá trị kênh. – HelloGoodbye
Kỹ thuật trong bài viết dựa trên việc tạo biểu đồ với 256 thùng cho kênh pixel 8 bit. Việc chuyển đổi thành 16 bit trên mỗi kênh sẽ yêu cầu một biểu đồ có 65536 thùng và cần phải có biểu đồ cho mỗi cột của hình ảnh. Việc bơm các yêu cầu bộ nhớ bằng 256 làm cho thuật toán này kém hiệu quả hơn, nhưng vẫn có thể thực hiện được với phần cứng ngày nay.
Sử dụng tối ưu hóa đề xuất của họ về việc phá vỡ biểu đồ thành các phần thô và tốt nên giảm thêm thời gian chạy xuống chỉ còn 16x.
Đối với các giá trị bán kính nhỏ, tôi nghĩ bạn sẽ tìm thấy các phương pháp lọc trung bình truyền thống sẽ hiệu quả hơn.
Xem phương trình 4 và 5 trong bài viết sau. Độ phức tạp là O (N * W) trong đó W là chiều rộng của bộ lọc và N là số lượng mẫu.
Tôi biết câu hỏi này là hơi cũ nhưng tôi cũng đã quan tâm đến việc lọc trung bình. Nếu một người đang làm việc với tín hiệu hoặc hình ảnh, thì sẽ có một chồng chéo lớn dữ liệu cho cửa sổ xử lý. Điều này có thể được lợi dụng.
tôi đã đăng một số mã chuẩn ở đây: 1D moving median filtering in C++
Nó mẫu dựa vì thế nên làm việc với hầu hết các loại dữ liệu POD.
Theo kết quả của tôi std::nth_element có hiệu suất kém đối với một trung vị chuyển động, vì nó phải sắp xếp cửa sổ giá trị mỗi lần.
Tuy nhiên, bằng cách sử dụng một nhóm giá trị được sắp xếp, người ta có thể thực hiện trung vị với 3 thao tác.
Trung vị bây giờ là giá trị trung bình trong hồ bơi.
Tôi hy vọng ai đó thấy điều này thú vị và đóng góp ý tưởng của họ!
Bài viết này mô tả một phương pháp để lọc trung bình của các hình ảnh chạy trong thời gian O (log r) thời gian cho mỗi pixel, nơi r là bán kính lọc, và làm việc cho bất kỳ loại dữ liệu (có thể là 8 số nguyên bit hoặc đôi):
Bạn đã thử std :: nth_element? Đó là O (n) so với O (n log n) cho một quicksort. – smocking
Bạn không muốn sửa đổi thuật toán này để làm cho nó hoạt động với thời gian ngắn vì thời gian chạy trên mỗi pixel là tỷ lệ thuận với 2^n, trong đó n là số bit trong kiểu dữ liệu được sử dụng. 256 cho mảng 8 bit đã đủ đau đớn, bạn không muốn đi đến 65536 cho mảng 16 bit. Xem câu trả lời của tôi cho một thuật toán nhanh hơn, mặc dù nó là O (log r) trên mỗi pixel thay vì O (1). – HelloGoodbye
Nếu bạn không muốn lọc trung bình, đó là những gì bạn làm trong ví dụ về xử lý hình ảnh nơi bạn tìm thấy một trung vị cho từng pixel, nhưng chỉ muốn tìm một vị trí trung bình, nhận xét của @ smocking có liên quan. – HelloGoodbye