회전하는 비트맵입니다.코드
https://stackoverflow.com/questions/848025
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
빠른 방법이 있을 회전 크 비트맵 90 또는 270 도 이상 단순히 하고 있는 중첩된 루프로 역 좌표?
비트맵 8bpp 고 일반적으로 2048*2400*8bpp
현재 저는 이렇게 하여 복사하는 간단과 함께 인수하 반전,대략(의사 코드:
for x = 0 to 2048-1
for y = 0 to 2048-1
dest[x][y]=src[y][x];
(현실에서 나는 그것을 포인터로,조금 더 자세한 정보를 원하시 속도,그러나 그가 대략 동일한 크기)
GDI 은 아주 느린 큰 이미지,GPU load/store 시간 텍스처(GF7 카드)에 있으로 같은 크기 현재의 CPU 시간입니다.
모든 팁,점?알고리즘을 것이라도 더 좋지만,속도보다 더 중요되고 있습니다.
대상은 델파이,그러나 그것은 더 많은 알고리즘 질문입니다.SSE(2)벡터화 문제 없습니다,그것은 충분히 큰 문제는 나를 위해 코드에서 어셈블러
까지 따라 닐스'응답
- 이미지 2048x2700->2700x2048
- 컴파일러 터보 탐색으로 2006 년에 최적화.
- 윈도우:전력 방식 설정에"항상"입니다.(중요!!!!)
- 기:코어 2 6600(2.4)
시간을 가진 오래 된 일상적인:32ms(1 단계)
시간 stepsize8:12ms
시간 stepsize16:10ms
시간 stepsize32+:9ms
한편 나도 테스트에 Athlon64X2(5200+iirc),속도가 약간 더보다는 네 가지 요인(80 19ms).
속도까지는 잘 가치가있다,감사합니다.어쩌면 여름 개월 동안 나는 고문에 나 자신 SSE(2)버전입니다.그러나 나는 이미 생각하는 방법에 대한 해결,그리고 나서 실행 SSE2 등록 똑바로 구현:
for n:=0 to 7 do
begin
load r0, <source+n*rowsize>
shift byte from r0 into r1
shift byte from r0 into r2
..
shift byte from r0 into r8
end;
store r1, <target>
store r2, <target+1*<rowsize>
..
store r8, <target+7*<rowsize>
그래서 8×8 9 요구를 등록하지만,32-bits SSE 는 8.어쨌든 그를 위해 무언가가 여름 개월 동안:-)
포인터는 것은 뭔가가 나의 본능이지만,그것은 될 수 있는 실제로는 무언가를하는 경우에,그것의 크기는하지 않 하드,컴파일러 설정할 수 없 mul 으로 이동합니다.동 muls 는 sich 는 저렴한 요즘,그들은 또한 더 생성하는 등 압력 afaik.
코드(에 의해 검증을 빼서 결과에서"naieve"rotate1 구현):
const stepsize = 32;
procedure rotatealign(Source: tbw8image; Target:tbw8image);
var stepsx,stepsy,restx,resty : Integer;
RowPitchSource, RowPitchTarget : Integer;
pSource, pTarget,ps1,ps2 : pchar;
x,y,i,j: integer;
rpstep : integer;
begin
RowPitchSource := source.RowPitch; // bytes to jump to next line. Can be negative (includes alignment)
RowPitchTarget := target.RowPitch; rpstep:=RowPitchTarget*stepsize;
stepsx:=source.ImageWidth div stepsize;
stepsy:=source.ImageHeight div stepsize;
// check if mod 16=0 here for both dimensions, if so -> SSE2.
for y := 0 to stepsy - 1 do
begin
psource:=source.GetImagePointer(0,y*stepsize); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(target.imagewidth-(y+1)*stepsize,0);
for x := 0 to stepsx - 1 do
begin
for i := 0 to stepsize - 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[stepsize-1-i]; // (maxx-i,0);
for j := 0 to stepsize - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
inc(psource,stepsize);
inc(ptarget,rpstep);
end;
end;
// 3 more areas to do, with dimensions
// - stepsy*stepsize * restx // right most column of restx width
// - stepsx*stepsize * resty // bottom row with resty height
// - restx*resty // bottom-right rectangle.
restx:=source.ImageWidth mod stepsize; // typically zero because width is
// typically 1024 or 2048
resty:=source.Imageheight mod stepsize;
if restx>0 then
begin
// one loop less, since we know this fits in one line of "blocks"
psource:=source.GetImagePointer(source.ImageWidth-restx,0); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(Target.imagewidth-stepsize,Target.imageheight-restx);
for y := 0 to stepsy - 1 do
begin
for i := 0 to stepsize - 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[stepsize-1-i]; // (maxx-i,0);
for j := 0 to restx - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
inc(psource,stepsize*RowPitchSource);
dec(ptarget,stepsize);
end;
end;
if resty>0 then
begin
// one loop less, since we know this fits in one line of "blocks"
psource:=source.GetImagePointer(0,source.ImageHeight-resty); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(0,0);
for x := 0 to stepsx - 1 do
begin
for i := 0 to resty- 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[resty-1-i]; // (maxx-i,0);
for j := 0 to stepsize - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
inc(psource,stepsize);
inc(ptarget,rpstep);
end;
end;
if (resty>0) and (restx>0) then
begin
// another loop less, since only one block
psource:=source.GetImagePointer(source.ImageWidth-restx,source.ImageHeight-resty); // gets pointer to pixel x,y
ptarget:=Target.GetImagePointer(0,target.ImageHeight-restx);
for i := 0 to resty- 1 do
begin
ps1:=@psource[rowpitchsource*i]; // ( 0,i)
ps2:=@ptarget[resty-1-i]; // (maxx-i,0);
for j := 0 to restx - 1 do
begin
ps2[0]:=ps1[j];
inc(ps2,RowPitchTarget);
end;
end;
end;
end;
업데이트 2Generics
나를 업데이트 코드를 generics 버전에서 Delphi XE.지 못했기 때문에 품질 관리 99703,그리고 포럼의 사람들이 이미 확인 그것은 또한에서 존재한 XE2.투표하시기 바랍:-)
업데이트 3Generics 지금 작동에 XE10
해결책
Yes,빠른 방법이 있습니다.
단순 루프의 대부분을 지출 시간에 캐시를 벗어났습니다.이게 되나요하기 때문에 당신은 터치 많은 양의 데이터에서는 매우 다른 곳에 단단한다.더:귀하의 메모리 위치가 정확히 힘의 두 떨어져있다.는 크기 캐시 수행합니다.
당신이 회전 알고리즘을 개량하면 지역의 당신의 기억을 액세스합니다.
간단한 방법으로 이를 수행하는 것 회전 각 8x8 픽셀 블록에 그것을 사용하여 자신 동일한 코드를 사용해 전체 비트맵,그리고 포장이 다른 반복되는 분할 이미지 회전으로 덩어리의 8×8 각 픽셀.
E.g.이 같은 것(선택하지 않습니 C-코드입니다.내 Delphi 기술지 않는 날짜까지):
// this is the outer-loop that breaks your image rotation
// into chunks of 8x8 pixels each:
for (int block_x = 0; block_x < 2048; block_x+=8)
{
for (int block_y = 0; blocky_y < 2048; block_y+=8)
{
// this is the inner-loop that processes a block
// of 8x8 pixels.
for (int x= 0; x<8; x++)
for (int y=0; y<8; y++)
dest[x+block_x][y+block_y] = src[y+block_y][x+block_x]
}
}
다른 방법이 있습니다.당신은 데이터를 처리할 수 있습니다 힐베르트 주문 또는 모니다.는 것에 이론 심지어 조금 빨리,하지만 코드는 것이 훨씬 더 복잡합니다.
Btw-기 때문 당신이 언급했다는 SSE 은 당신을 위해 옵션을 제공합니다.참고할 수 있는 회전 8×8 바이트 블럭 이내에 SSE-레지스터가 있습니다.그것은 까다로운 작업을 얻을 수 있지만,보고 SSE 매트릭스 트랜스 코드를 받아야 활동을 시작하게 된 계기는 그것이 동일한 것입니다.
편집:
그냥 확인:
블록 크기의 8x8 픽셀 단위로 코드를 실행 ca.5 번 더 빠르게 내 컴퓨터에.블록 크기의 16x16 실행 10 배 빠릅니다.
처럼 보인 그것의 좋은 아이디어를 실험으로 다른 블록 크기입니다.
여기에는(아주 간단한)테스트 프로그램을 사용:
#include <stdio.h>
#include <windows.h>
char temp1[2048*2048];
char temp2[2048*2048];
void rotate1 (void)
{
int x,y;
for (y=0; y<2048; y++)
for (x=0; x<2048; x++)
temp2[2048*y+x] = temp1[2048*x+y];
}
void rotate2 (void)
{
int x,y;
int bx, by;
for (by=0; by<2048; by+=8)
for (bx=0; bx<2048; bx+=8)
for (y=0; y<8; y++)
for (x=0; x<8; x++)
temp2[2048*(y+by)+x+bx] = temp1[2048*(x+bx)+y+by];
}
void rotate3 (void)
{
int x,y;
int bx, by;
for (by=0; by<2048; by+=16)
for (bx=0; bx<2048; bx+=16)
for (y=0; y<16; y++)
for (x=0; x<16; x++)
temp2[2048*(y+by)+x+bx] = temp1[2048*(x+bx)+y+by];
}
int main (int argc, char **args)
{
int i, t1;
t1 = GetTickCount();
for (i=0; i<20; i++) rotate1();
printf ("%d\n", GetTickCount()-t1);
t1 = GetTickCount();
for (i=0; i<20; i++) rotate2();
printf ("%d\n", GetTickCount()-t1);
t1 = GetTickCount();
for (i=0; i<20; i++) rotate3();
printf ("%d\n", GetTickCount()-t1);
}
다른 팁
C ++를 사용할 수 있다면보고 싶을 수도 있습니다. 고유.
사용하는 C ++ 템플릿 라이브러리입니다 SSE (2 이상) 및 Altivec 명령어는 벡터화되지 않은 코드로 우아한 폴백을 갖는 세트.
빠른. (벤치 마크 참조).
표현식 템플릿을 사용하면 임시를 지능적으로 제거하고 게으른 평가를 가능하게 할 수 있습니다. 이는 적절한 경우 에이 겐은 이것을 자동으로 처리하고 대부분의 경우 별명을 처리합니다.
SSE (2 이상) 및 Altivec 명령 세트에 대해 명시 적 벡터화가 수행되며, 벡터화되지 않은 코드로의 우아한 폴백이 있습니다. 표현식 템플릿을 사용하면 전체 표현식을 위해 전 세계적으로 이러한 최적화를 수행 할 수 있습니다.
고정 크기의 객체를 사용하면 동적 메모리 할당을 피하고 루프가 이해되면 풀리지 않습니다.
큰 매트릭스의 경우 캐시 친화성에 특별한주의를 기울입니다.
너 ~할 것 같다 SRC DEST의 보폭은 (Delphi가 MAJOR MAJOR MAJOR인지 여부에 따라 다름)가되기 때문에 행보 대신 캐시 정렬 블록을 복사하여 복사하여 개선 할 수 있어야합니다.
이미지가 정사각형이 아닌 경우 내내에서 할 수 없습니다. 정사각형 이미지로 작업하더라도 변환은 내내 작업에 도움이되지 않습니다.
조금 더 빨리 일을하려고한다면, 행 발폭을 활용하여 작동하도록 노력할 수 있지만, 최선을 다하는 것은 소스에서 한 번에 한 번에 4 바이트를 읽는 것입니다. 그런 다음 Dest에서 4 개의 연속 행에 기록하십시오. 그것은 당신의 오버 헤드를 줄여야하지만, 나는 5% 이상의 개선을 기대하지 않을 것입니다.
