픽셀까지의 거리를 기준으로 한 그레디언트

Question

마스크의 가장 가까운 픽셀까지의 거리를 기준으로 그레이 스케일 그라디언트를 만드는 알고리즘이 있습니다. 나는 점점 반경의 원을 구성하고 원의 픽셀에 대해 마스크에 모든 픽셀을 샘플링하여 픽셀을 찾을 :

for (x = 0; x < width; x++){ 
    for (y = 0; y < height; y++) { 
     bool pixelFound = false; 
     for (radius = 0; radius < resolution, pixelFound == false; radius++) { 
     for (alpha = 0; alpha < 2 * PI; alpha += 1/radius) { 
      xx = x + cos(alpha)*radius; 
      yy = y + sin(alpha)*radius; 

      if (MaskHasPixel(xx, yy)) { 
       pixelFound = true; 
       gradient = 1 - Magnitude(xx-x, yy-y)/resolution; 
       WriteGradientForPixel(x,y, gradient); 
      } 
     } 
     } 
    } 
} 

은 현재 알고리즘이 매우 느리다 -의 512 × 512 마스크 크기의 이미지 128x128 일 경우 512 * 512 * 384 * 41 = 4 127 195 136 비교를 수행해야하므로 CPU에서 계산하는 데 엄청난 시간이 걸립니다. 옵션 중 하나는 GPU에서 연산을 수행하는 것이지만이 알고리즘을 최적화하여 훨씬 빠르게 작동하게 할 수 있습니까? 나는 결국 비교적 부드러운 부드러운 그라디언트를 얻고 싶습니다.

감사합니다.

Answer 1

알고리듬을 3 배 빠르게 만드는 방법을 찾았습니다. 1. 내 테두리 마스크의 기하학적 중심을 계산하십시오. 2. 현재 픽셀에서 위에서 언급 한 중심까지의 방향을 계산합니다. dir = (center - pixel) .normalized 3.국경 픽셀 여부에 관계없이 센터쪽으로가는 모든 픽셀을 확인하십시오. 4. 그렇다면 검색이 끝났습니다. 5. 테두리 픽셀을 가운데로 찾지 못한 경우 원래의 느린 방법으로 이동하십시오.

속도를 높이는 또 다른 방법은 원본 이미지의 크기를 줄이는 것입니다. 이것은 많은 도움이 될 것입니다.

Answer 2

글쎄, 다음 확장판은입니다. 그들은 수정 된 알고리즘으로 수행 될 수 있습니다. 마스크가 0 인 배경에있는 마스크라고 가정합니다. 이미지에 위치 시키십시오 (제로의 배경을 확대하여이 스테이지의 이미지는 그 크기에 따라 unsigned short 또는 unsigned int의 배열이 될 수 있습니다 - 거리의 픽셀 값을 입력해야합니다).

다음 연산은 거리 계산입니다. 보다 신속하게하기 위해서 먼저 마스크의 경계선을 찾아서 좌표 배열에 저장하십시오. 그 후 우리는 그 배열을 통해 8 개의 연결된 0이 아닌 픽셀을 새로운 테두리 배열을 동시에 채우는 픽셀로 채 웁니다.

첫 번째 반복 끝에 free() 첫 번째 테두리 배열을 만들고 새 배열로 두 번째 반복을 실행하고 2를 이웃에 배치하고 다음 테두리 배열을 채 웁니다.

마지막 테두리 배열에 0 개의 멤버가있을 때까지 반복합니다.

---

또 다른 변형은 당신처럼, 직접 알고리즘이다. 마스크의 경계를 계산하고 저장하십시오. 승인. 이제 확장 된 이미지 크기 마스크의 모든 픽셀을 스캔하기 시작하십시오.

픽셀 값 == 0 인 경우, 경계선의 모든 픽셀을 통과하여 최소 거리를 저장합니다. 그라디언트의 값이됩니다.

이 알고리즘은 우리 점의 측면에있는 경계선의 픽셀에만 거리를 계산하여 향상시킬 수 있습니다. 이를 위해 경계 픽셀의 좌표뿐만 아니라 마스크의 중력 중심으로부터 각도를 저장해야합니다. 그런 다음 경계선을 스캐닝 할 때 현재 이미지 포인트와 마스크와의 각도가 같은 픽셀을 던져 버릴 수도 있고 마스크 중심점의 일부 값 (π/2?)을 버릴 수도 있습니다.

계산을 더 빠르게하는 또 다른 방법은 sinuses & cosinuses를 약간의 단계로 작게 만들기 때문에 이웃 구성원 간의 값은 무시할 수 있습니다. 이 단계는 중심으로부터 이미지 각도의 각 픽셀 크기 일 수 있습니다. 아니면 더 커.

---

물론이 문제에 대한 다른 최적화 방법이 많이 있으며, 그 중 일부는 훨씬 더 빠를 것입니다. 조사 문제입니다.