두 이미지 간의 이미지 하위 집합 찾기

Question

하드웨어 기반 비트 맵 애니메이션을 처리하는 방법을 연구 중입니다. 입력으로, 간단한 비트 맵 이미지 시퀀스가 ​​있습니다. 비디오는 아니며 비트 맵 채우기를 포함해도 단순한 셰이프와 같습니다. 저는이 애니메이션의 텍스처 맵을 만들고 있습니다. (그래서 GPU로 빠르게 렌더링 될 수 있습니다.) 그리고이 시퀀스는 대개 애니메이션의 일부분이 움직이는 동안 정지되어 있기 때문에, 두 이미지 사이의 "공통 부분"이므로 메모리를 절약 할 수 있습니다.

이미지의 크기가 같지 않을 수 있습니다 (예 : 개체가 커지거나 줄어드는 경우). 둘 사이의 가장 큰 공통 영역을 감지 할 방법이 필요합니다. 나는 this answer을 보았고 부분적으로 내 문제를 해결합니다. 그래도 크기가 다양하기 때문에 이미지가 다른 이미지에 반드시 포함되어 있지 않기 때문에 이미 내 케이스에 대한 더 나은 알고리즘이 있는지 알고 싶습니다.하지만 이미지 사이에 공통된 부분을 찾아야합니다. 두.

Answer 1

내가 보는 한 가지 문제는 한 이미지가 다른 이미지에 여러 가지 방식으로 포함될 수 있다는 것입니다. 어떻게 정답을 결정합니까?

실시간이어야합니까? 그렇지 않다면 피트니스 기능을 사용하여 간단한 O (n^4) 검색을 수행 할 수 있습니다.

적합도 함수는 이미지 간의 오차 일 수 있습니다 (n^8 알고리즘 제공).

업데이트 : 잘못된 분석은 죄송합니다. 탐색은 n^2이고 적합도 함수는 n^2이며 n^4이다.

w1 = width of image 1 
w2 = width of image 2 
h1 = height of image 1 
h2 = height of image 2 

for x = -w1 to w1+w2 
    for y = -h1 to h1+h2 
    find max fitness(x,y) 

fitness(xc,yc){ 
    m=0 
    for each x where image 1 overlaps image 2 displaced by xc 
    for each y where image 1 overlaps image 2 displaced by yc 
     if (image1[x][y] == image2[x+xc][y+yc]) 
     m += 1 
    return m 
} 

UPDATE : 중복의 번호를 확인하고 대부분의 중복을 찾기 위해 시도하는 수정 된 피트니스 기능

전체 알고리즘은 다음과 같이 될 것이다.