이미지에서 자기 유사성 속도를 높입니다

StackOverflow https://stackoverflow.com/questions/1801509

문제

이미지를 생성 할 프로그램을 작성하고 있습니다. 내가 원하는 한 가지 측정은 이미지에서 "자기 유사성"의 양입니다. 그림의 각 Sizewindow * Sizewindow 창에 대한 Countbest-Th Best Matches를 찾는 다음 코드를 작성했습니다.

double Pattern::selfSimilar(int sizeWindow, int countBest) {
    std::vector<int> *pvecount;

    double similarity;
    int match;
    int x1;
    int x2;
    int xWindow;
    int y1;
    int y2;
    int yWindow;

    similarity = 0.0;

    // (x1, y1) is the original that's looking for matches.

    for (x1 = 0; x1 < k_maxX - sizeWindow; x1++) {
        for (y1 = 0; y1 < k_maxY - sizeWindow; y1++) {
             pvecount = new std::vector<int>();

             // (x2, y2) is the possible match.
             for (x2 = 0; x2 < k_maxX - sizeWindow; x2++) {
                 for (y2 = 0; y2 < k_maxY - sizeWindow; y2++) {
                     // Testing... 
                     match = 0;

                     for (xWindow = 0; xWindow < sizeWindow; xWindow++) {
                         for (yWindow = 0; yWindow < sizeWindow; yWindow++) {
                             if (m_color[x1 + xWindow][y1 + yWindow] == m_color[x2 + xWindow][y2 + yWindow]) {
                                 match++;
                             }
                         }
                     }

                     pvecount->push_back(match);
                 }
             }

             nth_element(pvecount->begin(), pvecount->end()-countBest, pvecount->end());

             similarity += (1.0 / ((k_maxX - sizeWindow) * (k_maxY - sizeWindow))) *
                 (*(pvecount->end()-countBest) / (double) (sizeWindow * sizeWindow));

             delete pvecount;
        }
    }

    return similarity;
}

좋은 소식은 알고리즘이 내가 원하는 것을 수행한다는 것입니다. 그림의 '자체 유사'가 어떻게 '자기 유사한'에 대해 0.0에서 1.0까지의 값을 반환합니다.

당신이 이미 언급했다고 확신하는 나쁜 소식은 알고리즘이 매우 느리다는 것입니다. 필요합니다 (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow 달리기 단계.

변수에 대한 몇 가지 일반적인 값 :

k_maxX = 1280
k_maxY = 1024
sizeWindow = between 5 and 25
countBest = 3, 4, or 5
m_color[x][y] is defined as short m_color[k_maxX][k_maxY] with values between 0 and 3 (but may increase in the future.)

지금은 ~ 아니다 PVeCount가 취한 메모리 발자국에 대해 걱정했습니다. 나중에 CountBest보다 작을 때 다른 요소를 추가하지 않는 정렬 된 데이터 세트를 사용할 수 있습니다. 알고리즘 속도 만 걱정됩니다.

이것을 어떻게 속도를 높일 수 있습니까?

도움이 되었습니까?

해결책

귀하의 문제는 수행해야 할 계산을 강력히 상기시켜줍니다. 모션 보상 비디오 압축에서. 어쩌면 당신은 그 지역에서 무엇을했는지 자세히 살펴 봐야 할 것입니다.

Rlbond가 이미 지적했듯이, 색상이 정확히 일치하는 창에서 점수 수를 계산하는 것은 일반적으로 그림을 비교할 때 수행되지 않습니다. 이산 코사인 또는 웨이블릿 변환을 사용하는 것보다 개념적으로 더 간단한 방법은 차이의 사각형을 추가하는 것입니다.

diff = (m_color[x1 + xWindow][y1 + yWindow] - m_color[x2 + xWindow][y2 + yWindow]);
sum += diff*diff;

그리고 사용 합집합 대신에 성냥 유사성에 대한 기준으로 (이제 더 작은 의미).

당신이 정말로 요청한 것로 돌아가 : 요인 2/Sizewindow (아마도 제곱) 런 런 시간을 줄일 수 있다고 생각하지만 약간 지저분합니다. Y1을 1로 증가시킬 때 비교하는 특정 사각형 쌍의 제곱 쌍이 거의 동일하게 유지된다는 사실을 기반으로합니다. 오프셋이 xoff = x2-x1 및 yoff = y2-y1이 동일하면 상단 (rsp. 하단) 수직 스트라이프 만 동일합니다. 사각형의 정사각형은 더 이상 (지금은 Rsp.이지만 이전에는 아님) 일치합니다. 오프셋 xoff = x2-x1 및 yoff = y2-y1에 의해 색인 된 2 차원 배열에서 일치하는 값을 유지하면 y1의 새로운 값 [xoff] [yoff]가 1만큼 증가 할 수 있습니다. 및 x1은 2*Sizewindow 비교로 동일하게 유지 :

for (int x = x1; x < x1 + sizeWindow; x++) {
    if (m_color[x][y1] == m_color[x + xOff][y1 + yOff]) {
        match[xOff][yOff]--; // top stripes no longer compared
    }

    if (m_color[x][y1+sizeWindow] == m_color[x + xOff][y1 + sizeWindow + yOff]) {
        match[xOff][yOff]++; // bottom stripe compared not, but wasn't before
    }
}

(YOFF의 가능한 값이 변경됨에 따라 -Y1을 증가시켜 [Y2 -Y1, K_MAXY -SIZEWINDOW -Y1-1] 간격 [Y2 -Y1-1, K_MAXY -SIZEWINDOW -Y1-2]까지 변경할 수 있습니다. 두 번째 색인 yoff = k_maxy -sizewindow -y1-1과 일치하며 두 번째 색인 yoff = y2 -y1-1과 일치하는 일치를 계산해야합니다). 어쩌면 다른 2/Sizewindow 속도를 얻기 위해 배열에서 루프 중에 일치하는지/감소 [] []를 얼마나 많이 증가시킬 수도 있습니다.

다른 팁

좋아, 먼저,이 접근법은 전혀 안정적이지 않습니다. 이미지에 임의의 노이즈를 추가하면 두 이미지 사이의 유사성이 크게 줄어 듭니다. 더 중요한 것은 이미지 처리 관점에서 효율적이거나 특히 좋지 않습니다. 나는 또 다른 접근법을 제안한다. 예를 들어 웨이블릿 기반 접근법을 사용합니다. 몇 레벨 동안 이미지에서 2D DWT를 수행하고 스케일링 계수를 비교하면 더 나은 결과를 얻을 수 있습니다. 또한 이산 웨이블릿 변환은 O (n)입니다.

단점은 웨이블릿이 고급 수학적 주제라는 것입니다. 웨이블릿과 필터 뱅크에 좋은 오펜스 코스웨어 노트가 있습니다. 여기.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top