六边形搜索比菱形搜索稍复杂，先以六边形搜索找出最小损耗的像素点，再对该像素点进行正方形搜索以找到更高精度的mv。源码如下：
case X264_ME_HEX:
{
me_hex2:
/* equivalent to the above, but eliminates duplicate candidates */
/* hexagon */
//第一次对bmx,bmy像素周围的6个点对应的宏块计算损耗，保存到costs中
COST_MV_X3_DIR( -2,0, -1, 2, 1, 2, costs );
COST_MV_X3_DIR( 2,0, 1,-2, -1,-2, costs+4 ); /* +4 for 16-byte alignment */
bcost <<= 3; //左移3位，因为bcost低3位要存放代表像素位置的数据
COPY1_IF_LT( bcost, (costs[0]<<3)+2 );
COPY1_IF_LT( bcost, (costs[1]<<3)+3 );
COPY1_IF_LT( bcost, (costs[2]<<3)+4 );
COPY1_IF_LT( bcost, (costs[4]<<3)+5 );
COPY1_IF_LT( bcost, (costs[5]<<3)+6 );
COPY1_IF_LT( bcost, (costs[6]<<3)+7 );
if( bcost&7 ) //若不为0，则说明周围6个像素点中存在比原来bcost小的点
{
int dir = (bcost&7)-2;
bmx += hex2[dir+1][0];
bmy += hex2[dir+1][1]; //得到下一个六边形中心点
/* half hexagon, not overlapping the previous iteration */
for( int i = (i_me_range>>1) - 1; i > 0 && CHECK_MVRANGE(bmx, bmy); i-- )
{
COST_MV_X3_DIR( hex2[dir+0][0], hex2[dir+0][1],
hex2[dir+1][0], hex2[dir+1][1],
hex2[dir+2][0], hex2[dir+2][1],
costs ); //因为新的六边形中心周围的3个顶点在上一次已经计算过了，所以这次只计算另外3个顶点
bcost &= ~7;
COPY1_IF_LT( bcost, (costs[0]<<3)+1 );
COPY1_IF_LT( bcost, (costs[1]<<3)+2 );
COPY1_IF_LT( bcost, (costs[2]<<3)+3 );
if( !(bcost&7) )
break;
dir += (bcost&7)-2;
dir = mod6m1[dir+1];
bmx += hex2[dir+1][0]; //得到下一个中心点
bmy += hex2[dir+1][1];
}
}
bcost >>= 3;
/* square refine */
bcost <<= 4;
COST_MV_X4_DIR( 0,-1, 0,1, -1,0, 1,0, costs ); //对六边形搜索选出的点再进行正方形搜索
COPY1_IF_LT( bcost, (costs[0]<<4)+1 );
COPY1_IF_LT( bcost, (costs[1]<<4)+2 );
COPY1_IF_LT( bcost, (costs[2]<<4)+3 );
COPY1_IF_LT( bcost, (costs[3]<<4)+4 );
COST_MV_X4_DIR( -1,-1, -1,1, 1,-1, 1,1, costs );
COPY1_IF_LT( bcost, (costs[0]<<4)+5 );
COPY1_IF_LT( bcost, (costs[1]<<4)+6 );
COPY1_IF_LT( bcost, (costs[2]<<4)+7 );
COPY1_IF_LT( bcost, (costs[3]<<4)+8 );
bmx += square1[bcost&15][0];
bmy += square1[bcost&15][1];
bcost >>= 4;
break;
}
如源码中的注释，第一次搜索时，需要对以bmx,bmy坐标为中心的六边形的6个顶点都计算，如下图：
六边形搜索00.png
我们再看源码中的hex2数组，如下：
static const int8_t hex2[8][2] = {{-1,-2}, {-2,0}, {-1,2}, {1,2}, {2,0}, {1,-2}, {-1,-2}, {-2,0}};
它实际上是用来辅助定位新搜索的坐标的。
我们举个例子，假设开始bmx, bmy都为0，就是图中叉叉的位置，如第一次六边形搜索计算得到最小损耗的是4号像素，则bcost&7==5, dir==(bcost&7)-2==3, 则新的bmx==hex2[3+1][0]==2，新的bmy==hex2[3+1][1]==0，正是4号像素点的坐标。如下图：
六边形搜索01.png
然后我们继续进行第二次六边形搜索，以4号像素为中心，因为左边的三个顶点（即x,5,6）再第一次已经比较过了，这次只需要计算剩下三个，坐标分别是hex2[3+0][0]==(1,2), hex2[3+1][0]==(2,0), hex2[3+2][0]==(1,-2)。就是图中虚线1，2，3三个像素点。以此类推，直到找到最小像素点或超过搜索范围为止。
六边形搜索完毕之后，会对该点再进行正方形搜索，与上篇文章的菱形搜索类似，不再赘述。
网友评论