for (j=0;j<16;j)
?? {
?? ??? for (i=0;i<16;i)
?? ??? {
?? ?? M1[ i ][j]=imgY_org[img->opix_y+j][img->opix_x+i]-img->mprr_2[k][j][ i ]; ?? ?? 計算當前宏塊殘差塊
?? ?? M0[i%4][i/4][j%4][j/4]=M1[ i ][j];
?? ??? }
?? }
?? current_intra_sad_2=0; ?? ?? ?? ??? // no SAD start handicap here
?? for (jj=0;jj<4;jj)
?? {
?? ??? for (ii=0;ii<4;ii)
?? ??? {
?? ?? for (j=0;j<4;j) ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 第一次一維Hadamard變換
?? ?? { ?? ?? ?? ?? ?? ?? ?? ?? ?? ???
?? ?? ?? M3[0]=M0[0][ii][j][jj]+M0[3][ii][j][jj];
?? ?? ?? M3[1]=M0[1][ii][j][jj]+M0[2][ii][j][jj];
?? ?? ?? M3[2]=M0[1][ii][j][jj]-M0[2][ii][j][jj];
?? ?? ?? M3[3]=M0[0][ii][j][jj]-M0[3][ii][j][jj];
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???
?? ?? ?? M0[0][ii][j][jj]=M3[0]+M3[1]; ?? ?? ?? ?? ?? ?? ??
?? ?? ?? M0[2][ii][j][jj]=M3[0]-M3[1]; ?? ?? ?? ?? ?? ?? ??
?? ?? ?? M0[1][ii][j][jj]=M3[2]+M3[3]; ?? ?? ?? ?? ?? ?? ??
?? ?? ?? M0[3][ii][j][jj]=M3[3]-M3[2]; ?? ?? ?? ?? ?? ?? ??
?? ?? } ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

?? ?? for (i=0;i<4;i) ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???
?? ?? { ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ?? ?? M3[0]=M0[ i ][ii][0][jj]+M0[ i ][ii][3][jj];
?? ?? ?? M3[1]=M0[ i ][ii][1][jj]+M0[ i ][ii][2][jj];
?? ?? ?? M3[2]=M0[ i ][ii][1][jj]-M0[ i ][ii][2][jj];
?? ?? ?? M3[3]=M0[ i ][ii][0][jj]-M0[ i ][ii][3][jj];
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 第二次一維Hadamard變換
?? ?? ?? M0[ i ][ii][0][jj]=M3[0]+M3[1]; ?? ?? ?? ?? ?? ?? ??
?? ?? ?? M0[ i ][ii][2][jj]=M3[0]-M3[1]; ?? ?? ?? ?? ?? ?? ??
?? ?? ?? M0[ i ][ii][1][jj]=M3[2]+M3[3]; ?? ?? ?? ?? ?? ?? ??
?? ?? ?? M0[ i ][ii][3][jj]=M3[3]-M3[2]; ?? ?? ?? ?? ?? ?? ??
?? ?? ?? for (j=0;j<4;j) ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ?? ?? ??? if ((i+j)!=0) ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???
?? ?? ?? ?? current_intra_sad_2 += abs(M0[ i ][ii][j][jj]); ?? ?? 變換后的AC殘差值取絕對值求和作為代價
?? ?? } ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ??? }
?? }

?? for (j=0;j<4;j)
?? ??? for (i=0;i<4;i)
?? ?? M4[ i ][j]=M0[0][ i ][0][j]/4;

?? ??? // Hadamard of DC koeff
?? ??? for (j=0;j<4;j) ?? ?? 后面兩個for循環對當前宏塊的DC殘差進行Hadamard變換并將變換后的值取絕對值求和作為代價
?? ??? {
?? ?? M3[0]=M4[0][j]+M4[3][j];
?? ?? M3[1]=M4[1][j]+M4[2][j];
?? ?? M3[2]=M4[1][j]-M4[2][j];
?? ?? M3[3]=M4[0][j]-M4[3][j];

?? ?? M4[0][j]=M3[0]+M3[1];
?? ?? M4[2][j]=M3[0]-M3[1];
?? ?? M4[1][j]=M3[2]+M3[3];
?? ?? M4[3][j]=M3[3]-M3[2];
?? ??? }

?? ??? for (i=0;i<4;i)
?? ??? {
?? ?? M3[0]=M4[ i ][0]+M4[ i ][3];
?? ?? M3[1]=M4[ i ][1]+M4[ i ][2];
?? ?? M3[2]=M4[ i ][1]-M4[ i ][2];
?? ?? M3[3]=M4[ i ][0]-M4[ i ][3];

?? ?? M4[ i ][0]=M3[0]+M3[1];
?? ?? M4[ i ][2]=M3[0]-M3[1];
?? ?? M4[ i ][1]=M3[2]+M3[3];
?? ?? M4[ i ][3]=M3[3]-M3[2];

?? ?? for (j=0;j<4;j)
?? ?? ?? current_intra_sad_2 += abs(M4[ i ][j]);
?? ??? }
?? ??? if(current_intra_sad_2 < best_intra_sad2)
?? ??? {
?? ?? best_intra_sad2=current_intra_sad_2;
?? ?? *intra_mode = k; // update best intra mode

?? ??? }
}
?? }
?? best_intra_sad2 = best_intra_sad2/2;

?? return best_intra_sad2;
}



以上是源程序里的一段，intra_16*16并不是計算SAD值，而是計算SATD。
其中M1中放的是宏塊的殘差，M0也是，不過為了下面計算HADAMARD變換方便，他表示成M0[4][4][4][4]的形式，前2個[4][4]表示8X8塊坐標，后2個[4][4]表示一個8X8里的4X4塊坐標。
程序先對殘差進行HADAMARD變換，然后把所有的DC分量提出來，再對DC分量做HADAMARD變換，
最后得到的是SATD。
有兩點不明白，誰知道的解釋一下：
1 在提取DC分量時為什么要除以4？
2 最后的best_intra_sad2 為什么要除以2？

這主要是由于SATD變換不是歸一化矩陣，變換后的系數值幅值增加，因此要相應的/2和/4

hadamard 變換本身就有一個 /2 的操作，因此每次變換都要對所有系數進行 /2。而 find_sad_16x16 函數執行了兩次 hadamard 變換：首先對 256 個系數進行一次，其次對所有 DC 系數再做一次，因此對 DC 系數應該 /4，而對 AC 系數應該 /2。find_sad_16x16 函數中的：M4[ i ][j]=M0[0][ i ][0][j]/4;就是對 DC 系數 /4，而最后的：best_intra_sad2 = best_intra_sad2/2;可以認為是對 AC 系數的變相 /2。但這里相當于是對所有系數 /2，所以 DC 系數多了一次 /2。這個多的一次就不知道原因了。

264樂園群里探討過這個問題。對于hadamard變換的/2已經有了結論。但是對DC系數多除的那一次2，目前尚未找到根據。
4階hadamard變換的定義式本身就是包含了這個/2的。可以見http://en.wikipedia.org/wiki/Hadamard_transform 。這里再多解釋一點
假設hadamard變換沒有/2, 變換矩陣為：
1?? 1?? 1?? 1
1 -1?? 1 -1
1?? 1 -1 -1
1 -1 -1?? 1
這時對一個列向量v = (1, 1, 1, 1)'做變換，即用變換矩陣左乘列向量v，得到的變換后向量v' = (4, 0, 0, 0)'。

現在觀察v和v'，在歐氏空間中，對一個向量的“大小”的衡量就是其長度，通過計算內積得到。那么
len(v)?? = sqrt( 1^2 + 1^2 + 1^2 + 1^2) = 2
len(v') = sqrt( 4^2 + 0^2 + 0^2 + 0^2) = 4
由此可見如果沒有那個/2，變換前后，該向量的長度發生了變化。這樣的變換是違背正交變換的定義的。

所以，作為正交變換的hadamard變換，必須要有這個/2的歸一化。

A:推而廣之，整數 DCT 變換在變換前后向量的長度也發生了變化，為什么沒有除以 2 呢？

DCT變換（非整數）也是歸一化的整數變換也是正交變換，所以也一定會滿足歸一化的。firstime是不是忘記把scaling matrix考慮進來了啊。

按照畢厚杰書上 113 頁，變換矩陣為公式 6.15（這個時候 scaling matrix 還沒分離出來吧？）：
a?? a?? a?? a
b?? c -c -b
a -a -a?? a
c -b?? b -c
其中 a = 1/2，b = (2/5)^0.5。這個矩陣對列向量v = (1, 1, 1, 1)'做變換前后的向量長度并不相等啊。