Hough 변환을위한 누적 기 충전

Question

최적화해야 할 코드를 작성했습니다. 코드가 실제로 최적인지 확인하기 위해 커뮤니티와 확인하는 것만 큼 좋았습니다. 그것은 Hough 변환을위한 축약을 채 웁니다. 실제로 OpenCV 라이브러리에서 대부분의 코드를 복사하여 복사합니다. 감사!

---

int i,j,n,index; 
for (i = 0;i<numrows;i++) 
{ 
    for (j = 0;j<numcols;j++) 
    { 
      if (img[i*numcols + j] == 100) 
     { 
      for (n = 300;n<600;n++) 
      { 
       index = cvRound(j*tabCos[n] + i * tabSin[n]) + (numrho-1)/2; 
       accum[(n+1) * (numrho+2) + index+1]++; 
      } 
     } 
    } 
} 

Answer 1

없음을 그렇지 없습니다. 문제가되는 배열을 반복하는 간단한 포인터 산술로 최대한 많은 수의 [] 사용법을 대체하십시오. 불변 식을 로컬 변수로 추상화합니다.

그러나 첫 번째 질문은 프로파일 러가이 코드가 전체 앱의 컨텍스트에서 병목 현상임을 보여 줍니까? 그렇지 않다면 왜 마이크로 최적화를 방해합니까?

편집 : 루프 마이크로 최적화 - 크고 반복적 인 호우가 왠지 너무 붙어있어 코드의 조각에 변환이

int ints[100]; 
int i; 
int *pi; 

for (i = 0; i < 100; ++i) 
{ 
    printf("%d", ints[i]); 
} 

for (pi = ints; pi < ints + 100; ++pi) 
{ 
    printf("%d", *pi); 
} 

Answer 2

두 번째에는 배열 인덱싱이 필요하지 않기 때문에 (멀티 포트 대 추가) 선호 . 코드의 해당 부분의 관리자는 어큐뮬레이터에 대해 약간의 성공을 거둔 희소 배열 (실제로는 C++ std::map이 셀 인덱스에 맞춰져 있음)을 실험 해 보았습니다.

속도 향상은 캐시 지역 문제와 관련이 있으며 확실히 인 데이터가 희박합니다. 스파 스입니다.

---

업데이트 : 위에서 언급 한 소프트웨어는 많은 입자 물리학 실험 서비스를 제공하기위한 것입니다,하지만 원래 테스트 베드 프로젝트 (즉, 소규모)를 사용. 우리가 더 큰 프로젝트를 수행하는 것에 대해 진지하게 생각하고 그들을 위해 Monte Carlo를 시작 했으므로, Hough 변환은 드문 드문 한 행렬에서도 병목이 될 것입니다.

아직 해결 방법이 없지만 동료 중 하나가 Gandalf에 "fast hough transform"을 포함하고 있는데, 이는 쿼드 트리와 같은 방식으로 변환을 평가하는 것으로 보입니다 (2D에서, 아마도 3D로 oct-tree를 사용합니다) 작업 순서를 줄이십시오. 우리는 아마도 이것을 실험 할 것입니다.

추가 업데이트 : 동료는 결국 현재 우리가 가지고있는 가장 빠른 버전 인 것으로 보이는 코드에서 점진적이고 확률 론적 인 Hough 변환을 구현했습니다. 모든 포인트가 라인에 할당되도록 요구하지 않는 경우 가장 효과적입니다.

Answer 3

응용 프로그램에 따라 Hough Transform을 최적화 할 수있는 다양한 방법이 있으며 저수준 코드를 사용하는 것은 아마도 마지막 것일 수 있습니다. 나는 Randomized HT 또는 Multiresolution HT로 시작하여 Hybrid approach merge를 따랐다. 우선 알고리즘을 최적화하는 것이 더 낫다고 생각합니다. 마지막 단계는 CAD 메모리와 같은 하드웨어 최적화를 사용하는 것입니다.