运动矢量搜索的对数搜索算法 c++

以下是基于C++实现的对数搜索算法的运动矢量搜索代码：

#define SEARCH_RANGE 8 // 搜索范围
#define BLOCK_SIZE 16 // 编码块大小
#define MAX_SAD 65535 // 最大SAD值

// 对数搜索算法
int log_search(int x, int y, int width, unsigned char *pRefFrame, unsigned char *pCurFrame, int *pMVx, int *pMVy)
{
    int dx = 0, dy = 0;
    int SADCenter = computeSAD(pCurFrame, pRefFrame, x, y, width);
    int SADMin = SADCenter;
    *pMVx = 0;
    *pMVy = 0;

    for (int i = 1; i <= SEARCH_RANGE; i <<= 1)
    {
        int x1 = x - i;
        int x2 = x + i;
        int y1 = y - i;
        int y2 = y + i;

        // 检查搜索范围边界
        if (x1 < 0) x1 = 0;
        if (x2 >= width - BLOCK_SIZE) x2 = width - BLOCK_SIZE - 1;
        if (y1 < 0) y1 = 0;
        if (y2 >= width - BLOCK_SIZE) y2 = width - BLOCK_SIZE - 1;

        // 对角线上四个点
        int SAD = computeSAD(pCurFrame, pRefFrame, x1, y1, width);
        if (SAD < SADMin)
        {
            SADMin = SAD;
            dx = x1 - x;
            dy = y1 - y;
        }

        SAD = computeSAD(pCurFrame, pRefFrame, x2, y1, width);
        if (SAD < SADMin)
        {
            SADMin = SAD;
            dx = x2 - x;
            dy = y1 - y;
        }

        SAD = computeSAD(pCurFrame, pRefFrame, x1, y2, width);
        if (SAD < SADMin)
        {
            SADMin = SAD;
            dx = x1 - x;
            dy = y2 - y;
        }

        SAD = computeSAD(pCurFrame, pRefFrame, x2, y2, width);
        if (SAD < SADMin)
        {
            SADMin = SAD;
            dx = x2 - x;
            dy = y2 - y;
        }
    }

    // 对数搜索
    if (dx || dy)
    {
        int x0 = x + dx;
        int y0 = y + dy;
        int SAD0 = computeSAD(pCurFrame, pRefFrame, x0, y0, width);
        if (SAD0 < SADMin)
        {
            SADMin = SAD0;
            *pMVx = dx;
            *pMVy = dy;
        }

        for (int i = 1; i < SEARCH_RANGE; i <<= 1)
        {
            int x1 = x0 - i;
            int x2 = x0 + i;
            int y1 = y0 - i;
            int y2 = y0 + i;

            if (x1 < x - SEARCH_RANGE) x1 = x - SEARCH_RANGE;
            if (x2 > x + SEARCH_RANGE) x2 = x + SEARCH_RANGE;
            if (y1 < y - SEARCH_RANGE) y1 = y - SEARCH_RANGE;
            if (y2 > y + SEARCH_RANGE) y2 = y + SEARCH_RANGE;

            int SAD = 0;
            int minSAD = MAX_SAD;

            // 横向
            for (int x = x1; x <= x2; x++)
            {
                SAD = computeSAD(pCurFrame, pRefFrame, x, y0, width);
                if (SAD < minSAD)
                {
                    minSAD = SAD;
                    dx = x - x0;
                }
            }

            // 纵向
            for (int y = y1; y <= y2; y++)
            {
                SAD = computeSAD(pCurFrame, pRefFrame, x0, y, width);
                if (SAD < minSAD)
                {
                    minSAD = SAD;
                    dy = y - y0;
                }
            }

            if (dx || dy)
            {
                x0 += dx;
                y0 += dy;
                SAD = computeSAD(pCurFrame, pRefFrame, x0, y0, width);
                if (SAD < SADMin)
                {
                    SADMin = SAD;
                    *pMVx = x0 - x;
                    *pMVy = y0 - y;
                }
            }
        }
    }

    return SADMin;
}

其中，computeSAD()函数计算两个图像块之间的SAD值，pCurFrame和pRefFrame分别表示当前图像块和参考图像块的指针，x和y表示当前图像块的左上角坐标，width表示图像宽度。pMVx和pMVy表示返回的运动矢量。整个算法实现了对数搜索，具体来说，首先在对角线上四个点中找到SAD最小的一个点，然后以该点为中心，按照一定的步长进行对数搜索，每次搜索完横向和纵向后，再以新的点为中心，继续进行对数搜索，直到搜索结束。最后，返回SAD最小的点所对应的运动矢量。