x264的哈達(dá)瑪變換(hadamard)的實現(xiàn)和優(yōu)化

pgj555 2014-05-02

展開全文

hadamard 變換理論

很多網(wǎng)頁都有介紹，我就不拷貝了，給兩個鏈接。

下面的是harvey mudd college 的一個“計算機圖像處理分析”課件中哈達(dá)瑪變換的一個章節(jié)

（JASON GARRETT-GLASER x264的主開發(fā)就是在這個學(xué)校上過學(xué)阿。很棒的一個工程類大學(xué)）

http://fourier.eng./e161/lectures/wht/index.html

大概提綱：

1.介紹了hadamard 矩陣的定義

2.快速hadamard變換算法（hadamard orderd）

3. Sequency Ordered hadamard 矩陣的定義 --h264使用了這個定義

4. 快速hadamard變換算法（Sequency orderd）

http://www.cnblogs.com/xkfz007/articles/2616143.html

這個是中文的一個博客“X264中SATD實現(xiàn)分析”

優(yōu)點是-中文，哈哈。步驟也比較詳細(xì)，缺點是關(guān)于h264使用的sequency ordered那部分交代的不清楚。

JM86中hadamard的實現(xiàn)

函數(shù) SATD 里

if (use_hadamard)   //++ 如果采用了Hadamard變換，則先對殘差塊進(jìn)行Hadamard變換，然后將變換后的16個殘差值取絕對值相加作為代價
{
    /*===== hadamard transform =====*/
    m[ 0] = d[ 0] + d[12];
    m[ 4] = d[ 4] + d[ 8];
    m[ 8] = d[ 4] - d[ 8];
    m[12] = d[ 0] - d[12];
    m[ 1] = d[ 1] + d[13];
    m[ 5] = d[ 5] + d[ 9];
    m[ 9] = d[ 5] - d[ 9];
    m[13] = d[ 1] - d[13];
    m[ 2] = d[ 2] + d[14];
    m[ 6] = d[ 6] + d[10];
    m[10] = d[ 6] - d[10];
    m[14] = d[ 2] - d[14];
    m[ 3] = d[ 3] + d[15];
    m[ 7] = d[ 7] + d[11];
    m[11] = d[ 7] - d[11];
    m[15] = d[ 3] - d[15];

    d[ 0] = m[ 0] + m[ 4];
    d[ 8] = m[ 0] - m[ 4];
    d[ 4] = m[ 8] + m[12];
    d[12] = m[12] - m[ 8];
    d[ 1] = m[ 1] + m[ 5];
    d[ 9] = m[ 1] - m[ 5];
    d[ 5] = m[ 9] + m[13];
    d[13] = m[13] - m[ 9];
    d[ 2] = m[ 2] + m[ 6];
    d[10] = m[ 2] - m[ 6];
    d[ 6] = m[10] + m[14];
    d[14] = m[14] - m[10];
    d[ 3] = m[ 3] + m[ 7];
    d[11] = m[ 3] - m[ 7];
    d[ 7] = m[11] + m[15];
    d[15] = m[15] - m[11];

    m[ 0] = d[ 0] + d[ 3];
    m[ 1] = d[ 1] + d[ 2];
    m[ 2] = d[ 1] - d[ 2];
    m[ 3] = d[ 0] - d[ 3];
    m[ 4] = d[ 4] + d[ 7];
    m[ 5] = d[ 5] + d[ 6];
    m[ 6] = d[ 5] - d[ 6];
    m[ 7] = d[ 4] - d[ 7];
    m[ 8] = d[ 8] + d[11];
    m[ 9] = d[ 9] + d[10];
    m[10] = d[ 9] - d[10];
    m[11] = d[ 8] - d[11];
    m[12] = d[12] + d[15];
    m[13] = d[13] + d[14];
    m[14] = d[13] - d[14];
    m[15] = d[12] - d[15];

    d[ 0] = m[ 0] + m[ 1];
    d[ 1] = m[ 0] - m[ 1];
    d[ 2] = m[ 2] + m[ 3];
    d[ 3] = m[ 3] - m[ 2];
    d[ 4] = m[ 4] + m[ 5];
    d[ 5] = m[ 4] - m[ 5];
    d[ 6] = m[ 6] + m[ 7];
    d[ 7] = m[ 7] - m[ 6];
    d[ 8] = m[ 8] + m[ 9];
    d[ 9] = m[ 8] - m[ 9];
    d[10] = m[10] + m[11];
    d[11] = m[11] - m[10];
    d[12] = m[12] + m[13];
    d[13] = m[12] - m[13];
    d[14] = m[14] + m[15];
    d[15] = m[15] - m[14];

    /*===== sum up =====*/
    for (dd=diff[k=0]; k<16; dd=diff[++k])
    {
      satd += (dd < 0 ? -dd : dd);
    }
    satd >>= 1;
}

這個算法過程很清楚，參見上面的 "快速hadamard變換算法（hadamard orderd）"

可能有點搞不清楚的地方就是，大部分資料講的是一維的哈達(dá)嗎的變換，二維的都只是交代一下先變換二維圖像行，再在變換后的基礎(chǔ)上在變換列。我當(dāng)時糊涂了半天（要吃核桃了），那現(xiàn)在看到這個實現(xiàn)，應(yīng)該很清楚了，實際上就是算兩次，

第一次以把4x4橫向劃分為4個1x4矢量，做一維變換，總共做四次，這樣以行做變換就完成了，

第二次，在得到的4x4矩陣上再縱向劃分為4個1x4矢量，做一維變換?？偣沧鏊拇巍＿@樣就做完了二維的變換了。

x264未優(yōu)化c語言版本的hadamard變換實現(xiàn)

在版本 commit 5dc0aae2f900064d1f58579929a2285ab289a436 ，也就是最開始的版本

在函數(shù) pixel_satd_wxh 中

            for( d = 0; d < 4; d++ )
            {
                int s01, s23;
                int d01, d23;

                s01 = diff[d][0] + diff[d][1]; s23 = diff[d][2] + diff[d][3];
                d01 = diff[d][0] - diff[d][1]; d23 = diff[d][2] - diff[d][3];

                tmp[d][0] = s01 + s23;
                tmp[d][1] = s01 - s23;
                tmp[d][2] = d01 - d23;
                tmp[d][3] = d01 + d23;
            }
            for( d = 0; d < 4; d++ )
            {
                int s01, s23;
                int d01, d23;

                s01 = tmp[0][d] + tmp[1][d]; s23 = tmp[2][d] + tmp[3][d];
                d01 = tmp[0][d] - tmp[1][d]; d23 = tmp[2][d] - tmp[3][d];

                i_satd += abs( s01 + s23 ) + abs( s01 - s23 ) + abs( d01 - d23 ) + abs( d01 + d23 );
            }
可以看到算法有些和JM86的不一樣，因為他用了哈達(dá)嗎變換的Sequency orderd。

說實話，在課件里的”快速hadamard變換算法（Sequency orderd）“ 說明，我沒看很懂阿。有高手能講解下嗎？但是這段代碼大致不難理解，也是典型的碟形算法。只是次序和JM86不一樣估計是因為采用了Sequency ordered的原因。之所以采用這種ordered，我理解是因為Sequency ordered 是按照hadamard變換矩陣的符號變換次序重拍列了。變化最少的在嘴上面，最多的在最下面一列。這樣應(yīng)該能量更加集中在了左上角，更方便后面的壓縮。

x264優(yōu)化c語言版本的hadamard變換實現(xiàn)

參見patch “
1.6x faster satd_c (and sa8d and hadamard_ac) with pseudo-simd.”

static NOINLINE int x264_pixel_satd_4x4( pixel *pix1, intptr_t i_pix1, pixel *pix2, intptr_t i_pix2 )
{
    sum2_t tmp[4][2];
    sum2_t a0, a1, a2, a3, b0, b1;
    sum2_t sum = 0;
    for( int i = 0; i < 4; i++, pix1 += i_pix1, pix2 += i_pix2 )
    {
        a0 = pix1[0] - pix2[0];
        a1 = pix1[1] - pix2[1];
        b0 = (a0+a1) + ((a0-a1)<<BITS_PER_SUM);
        a2 = pix1[2] - pix2[2];
        a3 = pix1[3] - pix2[3];
        b1 = (a2+a3) + ((a2-a3)<<BITS_PER_SUM);
        tmp[i][0] = b0 + b1;
        tmp[i][1] = b0 - b1;
    }
    for( int i = 0; i < 2; i++ )
    {
        HADAMARD4( a0, a1, a2, a3, tmp[0][i], tmp[1][i], tmp[2][i], tmp[3][i] );
        a0 = abs2(a0) + abs2(a1) + abs2(a2) + abs2(a3);
        sum += ((sum_t)a0) + (a0>>BITS_PER_SUM);
    }
    return sum >> 1;
}
仔細(xì)觀察可以發(fā)現(xiàn)，快速的哈達(dá)嗎變換算法是對稱的。