我用块匹配算法找到的绘图矢量没有发现任何变化

Question

我正在尝试对图像的亮度值实施块匹配算法。

我从未见过它的实现，所以不得不对我的实现方式采取随意的方式。

均值差函数看起来像这样，我认为它工作得很好：

/// <summary>
/// intended to loop over the 8x8 chunk and calculate the MAD
/// </summary>
/// <param name="C">Original frame</param>
/// <param name="R">New frame</param>
/// <param name="x">x coord in the new matrix to check</param>
/// <param name="y">y coord in the new to check</param>
/// <param name="oi">old i index in old frame. stays the same</param>
/// <param name="oj">old j index in the old frame</param>
/// <param name="N">block size (8)</param>
/// <returns></returns>
public static float MeanDifference(List<List<float>> C, List<List<float>> R, int x, int y, int oi, int oj, int N ) {
    float MAD = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i + oi < C.Count && j + oj < C[i].Count && i + x < R.Count && j + y < R[i].Count)
                MAD += Math.Abs(C[i + oi][j + oj] - R[i + x][j + y]);
        }
    }
    return MAD /= (N * N);
}

我认为问题出在我的循环方式上，但我不能肯定地说。

/// <summary>
/// Step function advances the seach algorithm through the indexes.
/// </summary>
/// <param name="i">vertical index by which we search</param>
/// <param name="j">horizontal index by which we search</param>
/// <param name="width">width of search (16)</param>
/// <param name="height">height of search(16)</param>
/// <returns></returns>
public static bool Step(ref int i, ref int j, int width, int height) {
    if (j + 1 + 8 < width) {
        j++;
    }else if (j + 1 + 8 >= width && i + 1 + 8 < height) {
        j = 0;
        i++;
    }
    else {
        return false;
    }
    return true;
}
/// <summary>
///  Search algorithm
/// </summary>
/// <param name="C"></param>
/// <param name="R"></param>
/// <param name="searchSize"></param>
/// <param name="oi"></param>
/// <param name="oj"></param>
/// <param name="sx"></param>
/// <param name="sy"></param>
/// <returns></returns>
public static Tuple<Point, Point> Search(List<List<float>> C, List<List<float>> R, int searchSize, int oi, int oj, int sx, int sy) {
    int i = sy;
    int j = sx;
    int height = searchSize;
    int width = searchSize;

    float lowest = 1000;
    Point sp = new Point(oi, oj);
    Point ep = new Point();

    bool keepStepping = true;

    while(keepStepping) {
        float mad = ExaustiveSearch.MeanDifference(C, R, i, j, oi, oj, 8);
        if (mad < lowest) {
            lowest = mad;
            ep.X = j;
            ep.Y = i;
        }
        keepStepping = ExaustiveSearch.Step(ref i, ref j, searchSize, searchSize);
    }


    return new Tuple<Point, Point>(sp, ep);
}

调用一切的函数：

List<Tuple<Point, Point>> vectorData = new List<Tuple<Point, Point>>();
for (int i = 0; i < leftPicture.Height; i+=8) {
    for (int j = 0; j < leftPicture.Width; j+=8) {
        vectorData.Add(ExaustiveSearch.Search(Manager.LumList, Manager2.LumList, 16, i + 8, j + 8, i, j));
    }
}

即使是简单的测试用例，我似乎遇到的问题是，对于一个相同且只有一部分向左移动的图像，我最终得到的向量不仅没有检测到移动，而且还指向下方。

这是我在绘制矢量时看到的。（是的，我在原始图像上绘制了矢量）

我希望任何对块搜索算法有一定了解的人都能对我做错的事情有所了解，或者告诉我有人会如何实际实施它。

Answer 1

如果有人再次遇到这个问题，这里有一些代码可以解决。

测试代码：

DataManager manager = new DataManager();
Image im1 = Image.FromFile("./pic1.jpg");
Image im2 = Image.FromFile("./pic2.jpg");

manager.SetLeftPicture(im1);
manager.SplitBytesIntoColorSpaces();
manager.DrawYcbcrOnRightBitmap(1);
first.Image = manager.LeftImageBitmap;

DataManager manager2 = new DataManager();
manager2.SetLeftPicture(im2);
manager2.SplitBytesIntoColorSpaces();
manager2.DrawYcbcrOnRightBitmap(1);
second.Image = manager2.LeftImageBitmap;

List<Tuple<Point, Point>> mvs = new List<Tuple<Point, Point>>();

for (int oi = 0; oi < manager.LumList.Count; oi += 16) {
    for (int oj = 0; oj < manager.LumList.Count; oj += 16) {
        List<List<float>> C = manager.LumList.GetSquare(oi, oj, 16);
        List<List<float>> R = manager2.LumList.GetSquare(oi, oj, 16);
        List<List<float>> checkBlock = C.GetSquare(4, 4, 8);
        float mad = ExaustiveSearch.MeanDifference(checkBlock, R, 8, 4, 4);
        Point sp = new Point(oi + 4, oj + 4);
        Point ep = new Point(oi + 4, oj + 4);

        for (int i = 0; i < oi + 8; i++) {
            for (int j = 0; j < oj + 8; j++) {
                float nmad = ExaustiveSearch.MeanDifference(checkBlock, R, 8, i, j);
                if (nmad < mad) {
                    mad = nmad;
                    ep = new Point(i + oi, j + oj);
                }
            }
        }
        mvs.Add(new Tuple<Point, Point>(sp, ep));
    }
}

Bitmap map1 = new Bitmap(manager.LumList.Count, manager.LumList.Count);
Bitmap map2 = new Bitmap(manager2.LumList.Count, manager2.LumList.Count);

for (int i = 0; i < map1.Height; i++) {
    for (int j = 0; j < map1.Width; j++) {
        map1.SetPixel(i, j, Color.FromArgb((int)manager.LumList[i][j], 0,0,0));
        map2.SetPixel(i, j, Color.FromArgb((int)manager2.LumList[i][j], 0, 0, 0));
    }
}
using (Graphics g = Graphics.FromImage(map1)) {
    Pen p = Pens.AliceBlue;
    foreach (Tuple<Point, Point> mv in mvs) {
        g.DrawLine(p, mv.Item1, mv.Item2);
    }
}

first.Image = map1;
second.Image = map2;

GetSquare 代码

public static List<List<T>> GetSquare<T>(this List<List<T>> data, int x, int y, int block) {
    List<List<T>> output = new List<List<T>>();
    for (int i = x; i < block + x; i++) {
        List<T> dat = new List<T>();
        for (int j = y; j < block + y; j++) {
            dat.Add(data[i][j]);
        }
        output.Add(dat);
    }
    return output;
}

平均差异代码

public static float MeanDifference(List<List<float>> C, List<List<float>> R, int N, int x, int y) {
    float MAD = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (j + y >= N || i + x >= N) continue;
            MAD += Math.Abs(C[i][j] - R[i + x][j + y]);
        }
    }
    return MAD /= (N*N);
}

输出：

我用块匹配算法找到的绘图矢量没有发现任何变化

Drawing vectors I found with block matching algorithm not finding any changes

c#

signal-processing

vector