Programming

※NCC(Normalized Cross Correlation)

앞 포스트 영상 정합 포스트를 사정상 중간에 마무리했다. 해당 포스트는 영상 정합 포스트 마지막 내용을 이어서 쓰는 포스트이다. 따라서 해당 포스트를 읽기 전에 앞 포스트 "영상 정합 포스트"를 읽기 추천한다. 시작하겠다.

평균 밝기를 0으로 맞추는 것은 두 패치의 전체적인 밝기/평균 밝기에 큰 차이가 있을 때 SSD와 SAD에서 제대로 영상 접합을 할 수 없기 때문에 한다. 밝기의 표준 편차를 1로 맞추는 것은 평균 밝기가 같더라도 명암이 크게 차이가 나서 SSD나 SAD값이 달라질 수 있기 때문이다. 명암이 크다는 것은 어두운 픽셀과 밝은 픽셀이 영상 안에 많이 존재한다는 뜻이다. 따라서 평균 밝기가 같더라도 명암의 차이가 많이 난다면 입력 영상들의 픽셀값이 서로 많이 차이나 SSD나 SAD가 제대로 이루어 질 수 없다. 평균 밝기를 0으로 맞추고 표준 편차를 1로 맞추는 개념을 바탕으로 두 패치 사이의 NCC 값을 다음과 같이 나타낼 수 있다.

위에서 m1과 m2는 각 패치의 평균 밝기를 나타내고 시그마1과 시그마2는 각 패치 밝기의 표준편차를 나타낸다. 이렇게 구한 NCC값은 클수록 두 패치가 비슷하다고 나타내고, 작을수록 다르다는 것을 나타낸다. 다음은 NCC를 계산하는 코드이다. 평균과 표준편차를 구하는 부분과 표준편차를 이용하여 앞의 수식에 해당하는 NCC값을 구하는 부분으로 이루어진다. 표준편차를 구하는 데는 다음의 공식을 사용한다.

float _CalcNCC(const CByteImage& src1, const CByteImage& src2, int x1, int y1, int x2, int y2, int nhSize)
{
	if ((x1-nhSize)<0 || (x2-nhSize)<0 || (x1+nhSize)>=src1.GetWidth()  || (x2+nhSize)>=src2.GetWidth() ||
		(y1-nhSize)<0 || (y2-nhSize)<0 || (y1+nhSize)>=src1.GetHeight() || (y2+nhSize)>=src2.GetHeight())
		return FLT_MIN;

	// 평균과 표준편차 계산
	int nSum1=0, nSum2=0;
	int nSqr1=0, nSqr2=0;

	for (int r=-nhSize ; r<=nhSize ; r++)
	{
		BYTE* pSrc1 = src1.GetPtr(y1+r);
		BYTE* pSrc2 = src2.GetPtr(y2+r);

		for (int c=-nhSize ; c<=nhSize ; c++)
		{
			nSum1 += pSrc1[x1+c];
			nSqr1 += pSrc1[x1+c]*pSrc1[x1+c];
			nSum2 += pSrc2[x2+c];
			nSqr2 += pSrc2[x2+c]*pSrc2[x2+c];
		}
	}

	int nPixels = (nhSize*2+1)*(nhSize*2+1);
	float fMean1 = nSum1/nPixels;
	float fMean2 = nSum2/nPixels;
	float fVar1 = nSqr1/nPixels - fMean1*fMean1;
	float fVar2 = nSqr2/nPixels - fMean2*fMean2;

	// NCC값 계산
	float fSumProd = 0.0f;
	for (int r=-nhSize ; r<=nhSize ; r++)
	{
		BYTE* pSrc1 = src1.GetPtr(y1+r);
		BYTE* pSrc2 = src2.GetPtr(y2+r);

		for (int c=-nhSize ; c<=nhSize ; c++)
		{
			fSumProd += (pSrc1[x1+c]-fMean1)*(pSrc2[x2+c]-fMean2);
		}
	}

	return fSumProd/(sqrt(fVar1*fVar2))/nPixels;
}

※ 교차 검토를 이용한 패치 기반 정합

특징점 기반 영상 정합을 수행할 때는 일반적으로 한 영상을 기준 영상으로, 다른 영상을 목표 영상으로 설정한다. 그리고 기준 영상의 모든 특징점에 대해, SSD와 SAD, NCC 등의 방법을 통해 목표 영상의 대응점을 찾는 방식을 사용한다. 그런데 기준 영상의 한 특징점 P1에 대해 목표 영상에서 대응점 Q1을 찾았다고 해서, 거꾸로 목표 영상의 점 Q1에 대해 기준 영상에서 대응점을 찾은 결과가 처음의 P1과 일치한다는 보장은 없다. 즉, 기준 영상의 P1에 대해서는 목표 영상의 Q1이 가장 유사도가 높은 점일지라도 Q1의 입장에서는 기준 영상의 또 다른 점 P2가 가장 유사도가 높은 점일 수도 있는 것이다.

이렇듯 양 방향으로 검색 결과가 다르다는 것은 찾아낸 대응이 믿을 만한 결과가 아니라는 것을 뜻한다. 이러한 점들은 최종 대응 결과에서 제외하는 것이 바람직하다. 이러한 기법을 서로 교차하여 대응점 검색을 수행한다고 하여 교차검토라고 한다. 교차 검토를 사용하면 양방향으로 검사해야 하므로 계산시간이 최대 두 배까지 걸릴 수 있다. 하지만 정합을 더욱 정확하게 수행하고자 한다면 이를 사용하는 것이 바람직하다. 다음은 교차 검토를 이용한 패치 기반 SSD, SAD, NCC 정합을 구현한 메서드이다.

void CImageMatchDlg::_MAtchUsingSSD(int nPatchSize, int nThreshold)
{
	// 코너 추출
	double X1[1000], Y1[1000];
	double X2[1000], Y2[1000];

	int numCorner1 = HarrisCorner(m_imageIn1, 1e8, 0.04, 1000, X1, Y1);
	int numCorner2 = HarrisCorner(m_imageIn2, 1e8, 0.04, 1000, X2, Y2);

	m_imageOut = CByteImage(m_imageIn1.GetWidth() + m_imageIn2.GetWidth(), 
							MAX(m_imageIn1.GetHeight(), m_imageIn2.GetHeight()), 3);
	int nWidth1 = m_imageIn1.GetWidth();
	m_imageOut.Paste(Gray2RGB(m_imageIn1), 0, 0);
	m_imageOut.Paste(Gray2RGB(m_imageIn2), nWidth1, 0);

	// 패치 단위 대응점 검색
	for (int i=0 ; i<numCorner1 ; i++)
	{
		int nIdx2 = -1;
		int minSSD = INT_MAX;
		for (int j=0 ; j<numCorner2 ; j++)
		{
			int nSSD = _CalcSSD(m_imageIn1, m_imageIn2, X1[i], Y1[i], X2[j], Y2[j], nPatchSize/2);
			if (nSSD < minSSD)
			{
				nIdx2 = j;
				minSSD = nSSD;
			}
		}

		if (minSSD > nPatchSize*nPatchSize*nThreshold*nThreshold)
			continue;

		bool bCrsChk = true;
		for (int j=0 ; j<numCorner1 ; j++)
		{
			int nSSD = _CalcSSD(m_imageIn1, m_imageIn2, X1[j], Y1[j], X2[nIdx2], Y2[nIdx2], nPatchSize/2);
			if (nSSD < minSSD)
			{
				bCrsChk = false;
				break;
			}
		}

		if (bCrsChk)
		{
			DrawLine(m_imageOut, X1[i], Y1[i], X2[nIdx2]+nWidth1, Y2[nIdx2], 255, 0, 0);
		}
	}
}

void CImageMatchDlg::_MAtchUsingSAD(int nPatchSize, int nThreshold)
{
	// 코너 추출
	double X1[1000], Y1[1000];
	double X2[1000], Y2[1000];

	int numCorner1 = HarrisCorner(m_imageIn1, 1e8, 0.04, 1000, X1, Y1);
	int numCorner2 = HarrisCorner(m_imageIn2, 1e8, 0.04, 1000, X2, Y2);

	m_imageOut = CByteImage(m_imageIn1.GetWidth() + m_imageIn2.GetWidth(), 
							MAX(m_imageIn1.GetHeight(), m_imageIn2.GetHeight()), 3);
	int nWidth1 = m_imageIn1.GetWidth();
	m_imageOut.Paste(Gray2RGB(m_imageIn1), 0, 0);
	m_imageOut.Paste(Gray2RGB(m_imageIn2), nWidth1, 0);

	for (int i=0 ; i<numCorner1 ; i++)
	{
		int nIdx2 = -1;
		int minSAD = INT_MAX;
		for (int j=0 ; j<numCorner2 ; j++)
		{
			int nSAD = _CalcSAD(m_imageIn1, m_imageIn2, X1[i], Y1[i], X2[j], Y2[j], nPatchSize/2);
			if (nSAD < minSAD)
			{
				nIdx2 = j;
				minSAD = nSAD;
			}
		}

		if (minSAD > nPatchSize*nPatchSize*nThreshold)
			continue;

		bool bCrsChk = true;
		for (int j=0 ; j<numCorner1 ; j++)
		{
			int nSAD = _CalcSAD(m_imageIn1, m_imageIn2, X1[j], Y1[j], X2[nIdx2], Y2[nIdx2], nPatchSize/2);
			if (nSAD < minSAD)
			{
				bCrsChk = false;
				break;
			}
		}

		if (bCrsChk)
		{
			DrawLine(m_imageOut, X1[i], Y1[i], X2[nIdx2]+nWidth1, Y2[nIdx2], 255, 0, 0);
		}
	}
}

void CImageMatchDlg::_MAtchUsingNCC(int nPatchSize, float fThreshold)
{
	double X1[1000], Y1[1000];
	double X2[1000], Y2[1000];

	int numCorner1 = HarrisCorner(m_imageIn1, 1e8, 0.04, 1000, X1, Y1);
	int numCorner2 = HarrisCorner(m_imageIn2, 1e8, 0.04, 1000, X2, Y2);

	m_imageOut = CByteImage(m_imageIn1.GetWidth() + m_imageIn2.GetWidth(), 
							MAX(m_imageIn1.GetHeight(), m_imageIn2.GetHeight()), 3);
	int nWidth1 = m_imageIn1.GetWidth();
	m_imageOut.Paste(Gray2RGB(m_imageIn1), 0, 0);
	m_imageOut.Paste(Gray2RGB(m_imageIn2), nWidth1, 0);

	for (int i=0 ; i<numCorner1 ; i++)
	{
		int nIdx2 = -1;
		float maxNCC = FLT_MIN;
		for (int j=0 ; j<numCorner2 ; j++)
		{
			float fNCC = _CalcNCC(m_imageIn1, m_imageIn2, X1[i], Y1[i], X2[j], Y2[j], nPatchSize/2);
			if (fNCC > maxNCC)
			{
				nIdx2 = j;
				maxNCC = fNCC;
			}
		}

		if (maxNCC < fThreshold)
			continue;

		bool bCrsChk = true;
		for (int j=0 ; j<numCorner1 ; j++)
		{
			float fNCC = _CalcNCC(m_imageIn1, m_imageIn2, X1[j], Y1[j], X2[nIdx2], Y2[nIdx2], nPatchSize/2);
			if (fNCC > maxNCC)
			{
				bCrsChk = false;
				break;
			}
		}

		if (bCrsChk)
		{
			DrawLine(m_imageOut, X1[i], Y1[i], X2[nIdx2]+nWidth1, Y2[nIdx2], 255, 0, 0);
		}
	}
}

위 메서드들은 정합에 사용할 특징점을 이전 포스트에서 배운 해리스 코너 검출기로 얻는다. SSD에서는 밝기의 차이를 제곱하기 때문에 패치 전체의 문턱값을 nPatchSize*nPatchSize*nThreshold*nThreshold와 같이 계산했다. SAD에서는 절댓값을 이용하므로 패치 전체의 문턱값을 nPatchSize*nPatchSize*nThreshold와 같이 계산한다.

다음 그림은 전체적인 밝기가 차이가 있는 영상에 대해서 영상 접합을 수행한 결과이다. 

위 그림을 보면 NCC가 SSD와 SAD에 비해서 입력 영상의 대응점을 잘 찾는 걸 볼 수 있다.

※ 특징 기술자를 이용한 영상 정합

패치를 이용한 영상 정합은 영상의 가하학적 변화에 상당히 민감하다는 문제가 있다. 영상의 크기가 조금만 변하거나 카메라의 시점 변화가 있을 시 치명적이다. 따라서 이러한 기하학적 변화가 있어도 안정적으로 두 점 사이의 대응 관계를 찾는 기법이 연구 중이다. 

특징 기술자는 영상 안의 점에 대한 고유 특성을 표현할 수 있는 숫자들의 조합으로 보통 벡터나 행렬로 주어진다. 영상 패치도 일종의 특정 기술자이다. 패치 자체가 특징 기술자가 되어, 픽셀 값들로 이루어진 행렬이 특징 기술자가 된다. 그러나 패치 자체를 사용하는 것은 많은 문제가 있기 때문에 더 효율적인 특정 기술자들이 제안되고 이는 데 그중 가장 대표적인 SIFT 특징 기술자에 대해서 알아보자

※SIFT 특징 검출기

SIFT(Scale Invariant Feature Transform)은 영상의 스케일(비율) 변화에도 변하지 않는 특징 기술자를 생성하는 것을 목표로 개발되었다. 따라서 이를 사용하면 스케일이 다른 두 영상도 정합할 수 있다. 또한 시점 변화에 따른 영상의 기하학적 변화에도 어느 정도 강인하게 정합을 수행할 수 있는 장점이 있다.

SIFT는 특징점 검출기와 특징 기술자 생성기가 함께 구성된다. 특징점 검출기는 여러 스케일을 가지는 특징점을 모두 검출하기 위해 입력 영상을 여러 단계의 크기로 축소하여 이를 쌓아 올려 만든 영상 피라미드 상에서 특징점 검출을 수행한다. 다음은 영상 피라미드의 예이다.

영상 피라미드를 사용하면 위 그림처럼 모서리의 모양이 같지만 스케일이 서로 다른 코너들이 한 영상에 나타나도 이들을 모두 코너로 검출할 수 있다. 이때, 영상 피라미드에서 레벨 0에 가까운 낮은 단계에서는 위 그림에서 작은 사각형과 같이 세밀한 구조의 특징점이 검출되고 높은 단계에서는 큰 사각형에서와 같은 큼직한 특징점이 검출된다. 예를 들어 해리스 코너 검출기를 큰 스케일 영상에서 한다면 다음 그림의 오른쪽과 같이 커다란 하나의 코너만 나올 것이다. 하지만 작은 스케일 영상에서 한다면 왼쪽 그림과 같이 여러 개의 코너가 나올 수 있다. 따라서 해리스 코너 검출기를 사용할 때도 별도의 영상 피라미드를 만들어 각 단계에 대해 특징점 검출을 수행해야한다. 이러한 원리로 SIFT에서도 특징점을 모두 검출하기 위해서 영상 피라미드를 사용한다.

이 포스트도 이쯤에서 마치고 SIFT에 대한 추가적인 설명은 사정상 다음 포스트에서 설명할 예정이다. 양해 부탁드립니다.