Research/Video Coding
[구현] Block-based Translational, Affine, Perspective Motion Estimation을 직접 구현해보기 (2)
영스퀘어
2021. 4. 9. 15:56
-
소스 코드
<Affine ME>
using System;
using System.IO;
namespace MEModule_Affine
{
class Program
{
static void Main(string[] args)
{
...
byte[] result_stream = make_stream(full_search(luma, frame, width, height),
frame, width, height);
...
}
private static byte[,,] full_search(byte[] luma, int frame, int width, int height)
{
byte[,,] result = new byte[frame - 1, width, height];
ulong[] allResi = new ulong[frame - 1];
int MB = 32; // 매크로블록 사이즈
int SubMB = 16; // Sub 블록 사이즈
int SU = 16; // 매크로블록에서 위아래 얼마나 더 가져올지
int SR = SU * 2 + SubMB; // 서치레인지 사이즈(32x32)
int REST = MB + SU;
int REST_X = REST + ((width - (REST * 2))
- ((int)((width - (REST * 2)) / MB) * MB));
int REST_Y = REST + ((height - (REST * 2))
- ((int)((height - (REST * 2)) / MB) * MB));
int SubPoint = (MB - 1) - SubMB;
int numControlPoint = 3;
int numParam = 6;
// 4개의 control point
double[,] ControlPoint = new double[numControlPoint, 4];
for (int f = 0; f < frame - 1; f++)
{
byte[,] curr = get_frame(luma, f + 1, width, height);
byte[,] prev = get_frame(luma, f, width, height);
// Padding
// i : width, j : height
for (int j = 0; j < height; j++)
{
for (int i = 0; i < REST; i++) //좌
{
result[f, i, j] = curr[i, j];
}
for (int i = (width - REST_X); i < width; i++) //우
{
result[f, i, j] = curr[i, j];
}
}
for (int i = 0; i < width; i++)
{
for (int j = 0; j < REST; j++) //위
{
result[f, i, j] = curr[i, j];
}
for (int j = (height - REST_Y); j < height; j++) //아래
{
result[f, i, j] = curr[i, j];
}
}
//매크로 블록, 4개의 sub 블록, 서치 레인지 가져오기
byte[,] mb = new byte[MB, MB]; // 32X32
byte[,] sr = new byte[SR + MB, SR + MB];
byte[,] submbLeftTop = new byte[SubMB, SubMB]; // 16X16
byte[,] submbRightTop = new byte[SubMB, SubMB]; // 16X16
byte[,] submbLeftBottom = new byte[SubMB, SubMB]; // 16X16
byte[,] srLeftTop = new byte[SR + SubMB, SR + SubMB];
byte[,] srRightTop = new byte[SR + SubMB, SR + SubMB];
byte[,] srLeftBottom = new byte[SR + SubMB, SR + SubMB];
double[,] affineMat = new double[numParam, numParam];
double[,] affineMatInverse = new double[numParam, numParam];
double[,] affinePrime = new double[numParam, 1];
double[,] affineParam = new double[numParam, 1];
for (int h = REST; h < height - REST_Y; h += MB)
{
for (int w = REST; w < width - REST_X; w += MB)
{
//매크로 블록
for (int j = 0; j < MB; j++)
{
for (int i = 0; i < MB; i++)
{
mb[i, j] = curr[w + i, h + j];
}
}
//Sub 블록
for (int j = 0; j < SubMB; j++)
{
for (int i = 0; i < SubMB; i++)
{
submbLeftTop[i, j] = mb[i, j];
submbRightTop[i, j] = mb[i + SubPoint, j];
submbLeftBottom[i, j] = mb[i, j + SubPoint];
}
}
//일반적인 Translational ME 수행
int x = w - SU;
int y = h - SU;
if (width - x < SR + MB && height - y >= SR + MB)
{
for (int j = 0; j < SR + MB; j++)
{
for (int i = 0; i < width - x; i++)
{
sr[i, j] = prev[x + i, y + j];
}
}
}
else if (width - x >= SR + MB && height - y < SR + MB)
{
for (int j = 0; j < height - y; j++)
{
for (int i = 0; i < SR + MB; i++)
{
sr[i, j] = prev[x + i, y + j];
}
}
}
else if (width - x < SR + MB && height - y < SR + MB)
{
for (int j = 0; j < height - y; j++)
{
for (int i = 0; i < width - x; i++)
{
sr[i, j] = prev[x + i, y + j];
}
}
}
else
{
for (int j = 0; j < SR + MB; j++)
{
for (int i = 0; i < SR + MB; i++)
{
sr[i, j] = prev[x + i, y + j];
}
}
}
// SAD (Sum of Absolute Difference)
int[,] sad = new int[SR, SR];
int sum = 0;
// sad 전체를 임의의 큰값인 999로 초기화시킨다.
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
sad[i, j] = 999;
}
}
int sr_width_length = sr.GetLength(0);
int sr_height_length = sr.GetLength(1);
int VALID_SR_WIDTH = SR - ((SR + MB) - sr_width_length);
int VALID_SR_HEIGHT = SR - ((SR + MB) - sr_height_length);
// 서치레인지
for (int j = 0; j < VALID_SR_HEIGHT; j++)
{
for (int i = 0; i < VALID_SR_WIDTH; i++)
{
// 매크로 블록
for (int l = 0; l < MB; l++)
{
for (int k = 0; k < MB; k++)
{
sum += Math.Abs(sr[k + i, l + j] - mb[k, l]);
}
}
sad[i, j] = sum;
sum = 0;
}
}
// 가장 유사한 블록 구하기
int trans_min_sum = int.MaxValue;
int trans_x_prime = 0;
int trans_y_prime = 0;
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
if (sad[i, j] < trans_min_sum)
{
trans_min_sum = sad[i, j];
trans_x_prime = x + i;
trans_y_prime = y + j;
}
}
}
int xLeftTop = w - SU;
int yLeftTop = h - SU;
int xRightTop = w - SU + SubPoint;
int yRightTop = h - SU;
int xLeftBottom = w - SU;
int yLeftBottom = h - SU + SubPoint;
// 4개 sub 블록에 대한 각각의 ME를 수행한다.
//-------------------------------------------
// srLeftTop
if (width - xLeftTop < SR + SubMB && height - yLeftTop >= SR + SubMB)
{
for (int j = 0; j < SR + SubMB; j++)
{
for (int i = 0; i < width - xLeftTop; i++)
{
srLeftTop[i, j] = prev[xLeftTop + i, yLeftTop + j];
}
}
}
else if (width - xLeftTop >= SR + SubMB && height - yLeftTop
< SR + SubMB)
{
for (int j = 0; j < height - yLeftTop; j++)
{
for (int i = 0; i < SR + SubMB; i++)
{
srLeftTop[i, j] = prev[xLeftTop + i, yLeftTop + j];
}
}
}
else if (width - xLeftTop < SR + SubMB && height - yLeftTop
< SR + SubMB)
{
for (int j = 0; j < height - yLeftTop; j++)
{
for (int i = 0; i < width - xLeftTop; i++)
{
srLeftTop[i, j] = prev[xLeftTop + i, yLeftTop + j];
}
}
}
else
{
for (int j = 0; j < SR + SubMB; j++)
{
for (int i = 0; i < SR + SubMB; i++)
{
srLeftTop[i, j] = prev[xLeftTop + i, yLeftTop + j];
}
}
}
sum = 0;
// sad 전체를 임의의 큰값인 999로 초기화
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
sad[i, j] = 999;
}
}
sr_width_length = srLeftTop.GetLength(0);
sr_height_length = srLeftTop.GetLength(1);
VALID_SR_WIDTH = SR - ((SR + SubMB) - sr_width_length);
VALID_SR_HEIGHT = SR - ((SR + SubMB) - sr_height_length);
for (int j = 0; j < VALID_SR_HEIGHT; j++)
{
for (int i = 0; i < VALID_SR_WIDTH; i++)
{
//Left Top (0,0)
for (int l = 0; l < SubMB; l++)
{
for (int k = 0; k < SubMB; k++)
{
sum += Math.Abs(srLeftTop[k + i, l + j]
- submbLeftTop[k, l]);
}
}
sad[i, j] = sum;
sum = 0;
}
}
int min = int.MaxValue;
int mv_x = 0;
int mv_y = 0;
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
if (sad[i, j] < min)
{
min = sad[i, j];
mv_x = xLeftTop + i;
mv_y = yLeftTop + j;
}
}
}
ControlPoint[0, 0] = 0;
ControlPoint[0, 1] = 0;
ControlPoint[0, 2] = mv_x - w;
ControlPoint[0, 3] = mv_y - h;
//---------------------------------
// srRightTop
if (width - xRightTop < SR + SubMB && height - yRightTop >= SR + SubMB)
{
for (int j = 0; j < SR + SubMB; j++)
{
for (int i = 0; i < width - xRightTop; i++)
{
srRightTop[i, j] = prev[xRightTop + i, yRightTop + j];
}
}
}
else if (width - xRightTop >= SR + SubMB && height - yRightTop
< SR + SubMB)
{
for (int j = 0; j < height - yRightTop; j++)
{
for (int i = 0; i < SR + SubMB; i++)
{
srRightTop[i, j] = prev[xRightTop + i, yRightTop + j];
}
}
}
else if (width - xRightTop < SR + SubMB && height - yRightTop
< SR + SubMB)
{
for (int j = 0; j < height - yRightTop; j++)
{
for (int i = 0; i < width - xRightTop; i++)
{
srRightTop[i, j] = prev[xRightTop + i, yRightTop + j];
}
}
}
else
{
for (int j = 0; j < SR + SubMB; j++)
{
for (int i = 0; i < SR + SubMB; i++)
{
srRightTop[i, j] = prev[xRightTop + i, yRightTop + j];
}
}
}
// SAD (Sum of Absolute Difference)
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
sad[i, j] = 999;
}
}
sr_width_length = srRightTop.GetLength(0);
sr_height_length = srRightTop.GetLength(1);
VALID_SR_WIDTH = SR - ((SR + SubMB) - sr_width_length);
VALID_SR_HEIGHT = SR - ((SR + SubMB) - sr_height_length);
for (int j = 0; j < VALID_SR_HEIGHT; j++)
{
for (int i = 0; i < VALID_SR_WIDTH; i++)
{
//Right Top (13,0)
for (int l = 0; l < SubMB; l++)
{
for (int k = 0; k < SubMB; k++)
{
sum += Math.Abs(srRightTop[k + i, l + j]
- submbRightTop[k, l]);
}
}
sad[i, j] = sum;
sum = 0;
}
}
min = int.MaxValue;
mv_x = 0;
mv_y = 0;
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
if (sad[i, j] < min)
{
min = sad[i, j];
mv_x = xRightTop + i;
mv_y = yRightTop + j;
}
}
}
ControlPoint[1, 0] = MB;
ControlPoint[1, 1] = 0;
ControlPoint[1, 2] = mv_x - (w + SubPoint) + MB;
ControlPoint[1, 3] = mv_y - h;
//----------------------------------------
// srLeftBottom
if (width - xLeftBottom < SR + SubMB && height - yLeftBottom
>= SR + SubMB)
{
for (int j = 0; j < SR + SubMB; j++)
{
for (int i = 0; i < width - xLeftBottom; i++)
{
srLeftBottom[i, j] = prev[xLeftBottom + i, yLeftBottom + j];
}
}
}
else if (width - xLeftBottom >= SR + SubMB && height - yLeftBottom
< SR + SubMB)
{
for (int j = 0; j < height - yLeftBottom; j++)
{
for (int i = 0; i < SR + SubMB; i++)
{
srLeftBottom[i, j] = prev[xLeftBottom + i, yLeftBottom + j];
}
}
}
else if (width - xLeftBottom < SR + SubMB && height - yLeftBottom
< SR + SubMB)
{
for (int j = 0; j < height - yLeftBottom; j++)
{
for (int i = 0; i < width - xLeftBottom; i++)
{
srLeftBottom[i, j] = prev[xLeftBottom + i, yLeftBottom + j];
}
}
}
else
{
for (int j = 0; j < SR + SubMB; j++)
{
for (int i = 0; i < SR + SubMB; i++)
{
srLeftBottom[i, j] = prev[xLeftBottom + i, yLeftBottom + j];
}
}
}
// SAD (Sum of Absolute Difference)
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
sad[i, j] = 999;
}
}
sr_width_length = srLeftBottom.GetLength(0);
sr_height_length = srLeftBottom.GetLength(1);
VALID_SR_WIDTH = SR - ((SR + SubMB) - sr_width_length);
VALID_SR_HEIGHT = SR - ((SR + SubMB) - sr_height_length);
for (int j = 0; j < VALID_SR_HEIGHT; j++)
{
for (int i = 0; i < VALID_SR_WIDTH; i++)
{
//Left Bottom (13,0)
for (int l = 0; l < SubMB; l++)
{
for (int k = 0; k < SubMB; k++)
{
sum += Math.Abs(srLeftBottom[k + i, l + j]
- submbLeftBottom[k, l]);
}
}
sad[i, j] = sum;
sum = 0;
}
}
min = int.MaxValue;
mv_x = 0;
mv_y = 0;
for (int j = 0; j < SR; j++)
{
for (int i = 0; i < SR; i++)
{
if (sad[i, j] < min)
{
min = sad[i, j];
mv_x = xLeftBottom + i;
mv_y = yLeftBottom + j;
}
}
}
ControlPoint[2, 0] = 0;
ControlPoint[2, 1] = MB;
ControlPoint[2, 2] = mv_x - w;
ControlPoint[2, 3] = mv_y - (h + SubPoint) + MB;
//-------------------------------------
// create matrix
for (int m = 0; m < numParam / 2; m++)
{
//짝수 행 (0, 2, 4)
affineMat[2 * m, 0] = ControlPoint[m, 0];
affineMat[2 * m, 1] = ControlPoint[m, 1];
affineMat[2 * m, 2] = 0;
affineMat[2 * m, 3] = 0;
affineMat[2 * m, 4] = 1;
affineMat[2 * m, 5] = 0;
//홀수 행 (1, 3, 5)
affineMat[2 * m + 1, 0] = 0;
affineMat[2 * m + 1, 1] = 0;
affineMat[2 * m + 1, 2] = ControlPoint[m, 0];
affineMat[2 * m + 1, 3] = ControlPoint[m, 1];
affineMat[2 * m + 1, 4] = 0;
affineMat[2 * m + 1, 5] = 1;
affinePrime[2 * m, 0] = ControlPoint[m, 2];
affinePrime[2 * m + 1, 0] = ControlPoint[m, 3];
}
// inverse matrix 생성
affineMatInverse = GetInverseMatrix(affineMat, numParam);
// product matrix x vector
affineParam = MMult(affineMatInverse, affinePrime);
uint sum_affine_block = 0;
for (int a = 0; a < MB; a += 4)
{
for (int b = 0; b < MB; b += 4)
{
int eachSubMB_x = w + b;
int eachSubMB_y = h + a;
int eachSubMBcenter_x = b + (4 / 2);
int eachSubMBcenter_y = a + (4 / 2);
double eachSubMBcenterPrime_x
= ((affineParam[0, 0] * eachSubMBcenter_x)
+ (affineParam[1, 0] * eachSubMBcenter_y)
+ (affineParam[4, 0]));
double eachSubMBcenterPrime_y
= ((affineParam[2, 0] * eachSubMBcenter_x)
+ (affineParam[3, 0] * eachSubMBcenter_y)
+ (affineParam[5, 0]));
int eachSubMBMV_x = (int)(eachSubMBcenterPrime_x
- (double)eachSubMBcenter_x);
int eachSubMBMV_y = (int)(eachSubMBcenterPrime_y
- (double)eachSubMBcenter_y);
for (int c = 0; c < 4; c++)
{
for (int d = 0; d < 4; d++)
{
if (eachSubMB_x + eachSubMBMV_x + 4 < width
&& eachSubMB_y + eachSubMBMV_y + 4 < height)
{
if (eachSubMB_x + eachSubMBMV_x < 0
&& eachSubMB_y + eachSubMBMV_y < 0)
{
sum_affine_block += (byte)Math.Abs(
prev[0 + d, 0 + c]
- curr[eachSubMB_x + d, eachSubMB_y + c]);
}
else if (eachSubMB_x + eachSubMBMV_x < 0
&& eachSubMB_y + eachSubMBMV_y >= 0)
{
sum_affine_block += (byte)Math.Abs(
prev[0 + d, eachSubMB_y
+ c + eachSubMBMV_y]
- curr[eachSubMB_x + d, eachSubMB_y + c]);
}
else if (eachSubMB_x + eachSubMBMV_x >= 0
&& eachSubMB_y + eachSubMBMV_y < 0)
{
sum_affine_block += (byte)Math.Abs(
prev[eachSubMB_x
+ d + eachSubMBMV_x, 0 + c]
- curr[eachSubMB_x + d, eachSubMB_y + c]);
}
else
{
sum_affine_block += (byte)Math.Abs(
prev[eachSubMB_x + d +
eachSubMBMV_x, eachSubMB_y
+ c + eachSubMBMV_y]
- curr[eachSubMB_x + d, eachSubMB_y + c]);
}
}
}
}
}
}
if (trans_min_sum <= sum_affine_block)
{
for (int c = 0; c < MB; c++)
{
for (int d = 0; d < MB; d++)
{
result[f, w + d, h + c] = (byte)Math.Abs(
prev[trans_x_prime + d, trans_y_prime + c]
- curr[w + d, h + c]);
allResi[f] += result[f, w + d, h + c];
}
}
}
else
{
for (int a = 0; a < MB; a += 4)
{
for (int b = 0; b < MB; b += 4)
{
int eachSubMB_x = w + b;
int eachSubMB_y = h + a;
int eachSubMBcenter_x = b + (4 / 2);
int eachSubMBcenter_y = a + (4 / 2);
double eachSubMBcenterPrime_x
= ((affineParam[0, 0] * eachSubMBcenter_x)
+ (affineParam[1, 0] * eachSubMBcenter_y)
+ (affineParam[4, 0]));
double eachSubMBcenterPrime_y
= ((affineParam[2, 0] * eachSubMBcenter_x)
+ (affineParam[3, 0] * eachSubMBcenter_y)
+ (affineParam[5, 0]));
int eachSubMBMV_x = (int)(eachSubMBcenterPrime_x
- (double)eachSubMBcenter_x);
int eachSubMBMV_y = (int)(eachSubMBcenterPrime_y
- (double)eachSubMBcenter_y);
for (int c = 0; c < 4; c++)
{
for (int d = 0; d < 4; d++)
{
if (eachSubMB_x + eachSubMBMV_x + 4 < width
&& eachSubMB_y + eachSubMBMV_y + 4 < height)
{
if (eachSubMB_x + eachSubMBMV_x < 0
&& eachSubMB_y + eachSubMBMV_y < 0)
{
result[f, eachSubMB_x + d, eachSubMB_y + c]
= (byte)Math.Abs(prev[0 + d, 0 + c]
- curr[eachSubMB_x + d, eachSubMB_y
+ c]);
allResi[f] += result[f, eachSubMB_x + d,
eachSubMB_y + c];
}
else if (eachSubMB_x + eachSubMBMV_x < 0
&& eachSubMB_y + eachSubMBMV_y >= 0)
{
result[f, eachSubMB_x + d, eachSubMB_y + c]
= (byte)Math.Abs(prev[0 + d, eachSubMB_y
+ c + eachSubMBMV_y]
- curr[eachSubMB_x + d, eachSubMB_y
+ c]);
allResi[f] += result[f, eachSubMB_x + d,
eachSubMB_y + c];
}
else if (eachSubMB_x + eachSubMBMV_x >= 0
&& eachSubMB_y + eachSubMBMV_y < 0)
{
result[f, eachSubMB_x + d, eachSubMB_y + c]
= (byte)Math.Abs(prev[eachSubMB_x + d
+ eachSubMBMV_x, 0 + c]
- curr[eachSubMB_x + d, eachSubMB_y + c]);
allResi[f] += result[f, eachSubMB_x + d,
eachSubMB_y + c];
}
else
{
result[f, eachSubMB_x + d, eachSubMB_y + c]
= (byte)Math.Abs(prev[eachSubMB_x + d
+ eachSubMBMV_x, eachSubMB_y + c
+ eachSubMBMV_y]
- curr[eachSubMB_x + d, eachSubMB_y + c]);
allResi[f] += result[f, eachSubMB_x + d,
eachSubMB_y + c];
}
}
}
}
}
}
}
}
}
}
for (int p = 0; p < frame - 1; p++)
{
string line = String.Format("{0} {1}", p, allResi[p]);
Console.WriteLine(line);
}
return result;
}
private static byte[] make_stream(byte[,,] residual, int frame, int width, int height)
{
...
}
private static byte[,] get_frame(byte[] luma, int f, int width, int height)
{
...
}
public static double[,] GetInverseMatrix(double[,] input, int dim)
{
...
}
public static double[,] MMult(double[,] m1, double[,] m2)
{
...
}
}
}