Thuật toán để cắt các mặt phẳng (tại chỗ) ra khỏi một dãy các giá trị RGB

Question

Tôi có một mảng phẳng các giá trị byte RGB đi R1 G1 B1 R2 G2 B2 R3 G3 B3 ... Rn Gn Bn. Vì vậy, dữ liệu của tôi trông giống như:

char imageData[WIDTH * HEIGHT * 3]; 

Nhưng tôi muốn chuyển mảng WIDTH * HEIGHT vào thư viện C hiện có dự kiến ​​một mặt phẳng duy nhất của dữ liệu này. Đó sẽ là một chuỗi chỉ các giá trị R (hoặc chỉ là G, hoặc chỉ B).

Thật dễ dàng để phân bổ mảng mới và sao chép dữ liệu (duh). Nhưng hình ảnh rất lớn. Nếu nó không phải là một thư viện C nhưng đã lấy một số loại giao diện lặp lại để làm nổi bật quá trình truyền tải "cắt", điều đó sẽ rất tuyệt vời. Nhưng tôi không thể chỉnh sửa mã tôi đang gọi ... nó muốn một con trỏ cũ đơn giản đến một khối bộ nhớ tuần tự.

TÔI CÓ quyền truy cập ghi vào mảng này như thế nào. Nó là khả thi để tạo ra một thói quen mà sẽ sắp xếp nó thành máy bay màu. Tôi cũng cần một phép chuyển đổi ngược lại để đặt nó trở lại, nhưng theo định nghĩa, cùng một phương pháp sắp xếp nó thành các mặt phẳng có thể được áp dụng để hủy bỏ nó.

Làm thế nào hiệu quả tôi có thể (tại chỗ) biến mảng này thành R1 R2 R3 ... Rn G1 G2 G3 ... Gn B1 B2 B3 ... Bn và sau đó quay lại? Bất kỳ thuật toán không ngây thơ?

Answer 1

char *imageData = malloc (WIDTH * HEIGHT * 3 * sizeof(char)); 

chức năng này thực hiện điều này R1 R2 R3 ... Rn G1 G2 G3 ... St B1 B2 B3 ... Bn ,,

char *toRGB(char *imageData, int WIDTH, int HEIGHT){ 
    int len = WIDTH * HEIGHT; 
    char *RGB = malloc (len * sizeof(char)); 
    int i, j = 0,flag = 0; 

    for(i=0 ; i<=len ; i++, j+=3){ 
     if(j<len) 
      RGB[i] = imageData[j]; 
     else{ 
      switch(flag){ 
       case 0: j=-2; flag=1; break; // j=-2 the next iteration will start at j=1 
       case 1: j=-1; break; // j=-1 the next iteration will start at j=2 
      } 
     } 
    } 
    return RGB; 
} 

Answer 2

giấy này "A Simple In-Place Algorithm for In-Shuffle" mô tả làm thế nào để transpose ma trận 2 * N và đưa ra một gợi ý làm thế nào để làm điều đó cho các trường hợp khác, vì vậy 3 * N có thể cũng có thể. This answer to other question cho thấy rằng nó thực sự là có thể.

Hoặc sử dụng thuật toán ghi mỗi giá trị vào vị trí được chuyển đổi, sau đó thực hiện tương tự cho giá trị từ địa điểm đó, v.v. cho đến khi chu trình được kết nối. Gắn cờ các giá trị được xử lý trong một bit bit. Và tiếp tục cho đến khi vector này là tất cả 1s.

Cả hai thuật toán đều không thân thiện với bộ nhớ cache. Có lẽ một số sử dụng thông minh của PREFETCH hướng dẫn có thể cải thiện điều này.

Edit:

C++, RGB để máy bay duy nhất, không được tối ưu hóa:

#include <iostream> 
#include <bitset> 
#include <vector> 

enum {N = 8}; 

void transpose(std::vector<char>& a) 
{ 
    std::bitset<3*N> b; 

    for (int i = 1; i < 3*N; ++i) 
    { 
    if (b[i]) 
     continue; 

    int ptr = i; 
    int next; 
    char nextVal = a[i]; 

    do { 
     next = ptr/3 + N*(ptr%3); 
     char prevVal = nextVal; 
     nextVal = a[next]; 
     a[next] = prevVal; 
     ptr = next; 
     b[ptr] = true; 
    } 
    while (ptr != i); 
    } 
} 

int main() 
{ 
    std::vector<char> a(3*N); 

    for (int i = 0; i != 3*N; ++i) 
    a[i] = i; 

    transpose(a); 

    for (int i = 0; i != 3*N; ++i) 
    std::cout << (int)a[i] << std::endl; 

    return 0; 
} 

ý định ban đầu của tôi là sử dụng một vector chút kích thước WIDTH HEIGHT, mang đến cho overhead của WIDTH HEIGHT/8. Nhưng nó luôn luôn có thể hy sinh tốc độ cho không gian. Vector bit có thể có kích thước WIDTH hoặc HEIGHT hoặc bất kỳ giá trị mong muốn nào, thậm chí 0. Bí quyết là duy trì một con trỏ tới ô, trước khi tất cả các giá trị được chuyển đổi. Vector bit là dành cho các ô, bắt đầu từ con trỏ này. Sau khi nó là tất cả 1s, nó được chuyển đến vị trí tiếp theo, sau đó tất cả các bước thuật toán được thực hiện ngoại trừ chuyển động dữ liệu thực tế. Và bit bit đã sẵn sàng để tiếp tục chuyển đổi. Biến thể này là O (N^2) thay vì O (N).

Edit2:

PREFITCH tối ưu hóa không phải là khó thực hiện: chỉ cần tính toán chỉ số, gọi Prefetch, và đưa chỉ số để một hàng đợi (ringbuffer), sau đó nhận được chỉ số từ hàng đợi và di chuyển dữ liệu.

Edit3:

Ý tưởng của thuật toán khác, đó là O (1) kích thước, O (N * log (N)) thời gian, là bộ nhớ cache thân thiện và có thể nhanh hơn so với thuật toán "chu kỳ" (đối với hình ảnh kích thước < 1Gb):

• Chia N * 3 ma trận để vài 3 * 3 ma trận của char và transpose họ
• chia kết quả đến 3 * 3 ma trận của char [3] và transpose họ
• Tiếp tục khi kích thước ma trận nhỏ hơn kích thước mảng
• Bây giờ chúng tôi có tối đa 3 * 2 * log3 (N) các phần được sắp xếp. Tham gia cùng họ.
• Các mảnh ghép đầu tiên có kích thước bằng nhau. Rất đơn giản "chu kỳ" của chiều dài 4 có thể được sử dụng.
• Tham mảnh bất bình đẳng quá lớn với những đảo ngược (reverse (a), đảo ngược (b))

Answer 3

Nếu bạn chỉ cần một chiếc máy bay, điều này dường như khá dễ dàng. Nếu bạn cần tất cả 3 bạn có thể sẽ có may mắn hơn với một thuật toán phức tạp hơn.

void PlanarizeR(char * imageData, int width, int height) 
{ 
    char *in = imageData; 
    int pixelCount = width * height; 
    for (int i = 0; i < pixelCount; ++i, in+=3) 
     std::swap(*in, imageData[i]) 
} 

Sẽ không quá khó để chạy vòng lặp ngược từ cao đến thấp để đảo ngược quy trình.