Row-Ordered 데이터를 Column-Ordered 데이터로 가장 빠른 변환

Question

openCV의 IplImage를 가지고 있습니다.이 데이터는 행 순서 형식으로 데이터를 저장합니다.

이미지 데이터는 1 차원 배열 char * data에 저장됩니다. 위치 (x)에서의 소자는, 예를

주어진다

elem(x,y) = data[y*width + x] // see note at end 

I가 칼럼 정렬 된 포맷으로 데이터를 저장하는 제 2 화상 포맷에서 최대한 빨리 이미지 변환하고자; 즉,

elem(x,y) = data[x*height + y] 

이 변환을 수행하는 한 가지 방법은 단순히 double for 루프를 통해 요소별로 수행하는 것입니다.

더 빠른 방법이 있습니까? 에서 OpenCV afficionados위한

---

참고 ELEM의 실제 위치 (X, Y)은 data + y*widthstep + x*sizeof(element) 주어진 그러나 이것은 문자 데이터를 sizeof (요소) = 1의 일반적인 아이디어를 제공하고, 우리는 = 폭 widthstep 수있다 따라서 수식이 정확합니다.

Answer 1

"매트릭스 전치" 최적의 방법은 작은 타일 을 하나 또는 몇 개의 캐시 슬롯 크기로 스와핑하여 캐시 누락 횟수를 최소화하려고 시도합니다. 다중 레벨 캐시의 경우 어려워 질 것입니다.

this one is a bit more advanced

start reading here

은 BTW URL은 "대신에"전치 처리합니다. 트랜스 포즈 된 복사본을 만드는 것은 다릅니다 (두 배의 캐시 슬롯을 사용합니다.)

Answer 2

모든 요소가 이동 된 새 배열이 필요하다고 가정하면 알고리즘 속도에서 가장 빠르게 관리 할 수있는 요소의 수는 요소 수 (즉 너비 * 높이)에 O (N)입니다.

실제 시간은 각 요소가 일부 요소를 복사하는 여러 스레드를 생성하는 것이 가능합니다. 당신이 정말로 많은 것을 가지고 있다면 이것은 물론 가치가 있습니다.

스레드가 이미 만들어져 있고 대기열에있는 작업을 수락하면이 이미지를 많이 처리 할 때 가장 효율적입니다.

개인 "루프"에서 동일한 곱셈을 여러 번하는 것을 피할 수 있으며 물론 포인터 연산은 임의 액세스보다 약간 빠르다.

Answer 3

독자는 코드가 없지만 답변을 드렸습니다.

typedef struct 
{ 
    unsigned char r; 
    unsigned char g; 
    unsigned char b; 
}somePixelFormat; 

#define HEIGHT 2 
#define WIDTH 4 

// let's say this is original image width=4 height=2 expresed as one dimentional 
// array of structs that adhere to your pixel format 
somePixelFormat src[ WIDTH * HEIGHT ] = 
{ 
    {0,0,0}, {1,1,1}, {2,2,2}, {3,3,3}, 
    {4,4,4}, {5,5,5}, {6,6,6}, {7,7,7} 
}; 

somePixelFormat dst[ WIDTH * HEIGHT ]; 

void printImage(void *img, int width, int height, int pixelByteCount) 
{ 
    for (int row = 0; row < height; row++) 
    { 
     for (int col = 0; col < width; col++) 
     { 
      printf("(%02d,%02d,%02d) ", ((somePixelFormat*)img + width * row + col)->r, 
             ((somePixelFormat*)img + width * row + col)->g, 
             ((somePixelFormat*)img + width * row + col)->b); 
     } 

     printf ("\n"); 
    } 
    printf("\n\n"); 
} 

void flip(void *dstImg, void *srcImg, int srcWidth, int srcHeight, int pixelByteCount) 
{ 
    for (int row = 0; row < srcHeight; row++) 
    { 
     for (int col = 0; col < srcWidth; col++) 
     { 
      *((somePixelFormat*)dstImg + srcHeight * col + row) = *((somePixelFormat*)srcImg + srcWidth * row + col); 
     } 
    } 
} 

int main() 
{ 
    printImage(src, 4, 2, sizeof(somePixelFormat)); 
    flip(dst, src, 4, 2, sizeof(somePixelFormat)); 
    printImage(dst, 2, 4, sizeof(somePixelFormat)); 

    getchar(); 
    return 0; 
} 

을 그리고 여기에 출력 예입니다 : 당신이 있기 때문에

(00,00,00) (01,01,01) (02,02,02) (03,03,03) 
(04,04,04) (05,05,05) (06,06,06) (07,07,07) 


(00,00,00) (04,04,04) 
(01,01,01) (05,05,05) 
(02,02,02) (06,06,06) 
(03,03,03) (07,07,07)