2010年12月30日 星期四
2010年12月6日 星期一
Molecular Dynamic Simulation - 威佐、雙魚
--------- 2010 . 12. 06 ----------
威佐 :
目前已經將幾個常用的 Operations 取出,
需要計算的力包括:
Bonded(Bond length、Bond angle、Dihedral 三種力)和 Non-Bonded,
我相信這是簡化過的形式,但對於我們做加速運算已經足夠,
我現在使用的 Code 是學長給的那本書中的 Code (老師我沒有自己寫一個...)。
但是因為要先嘗試做 translator,所以先暫用書中的 Code,等到評估期過後,
我們可以自己改一份 MD 的 Code,
另外,現在成熟的 MD 套件大概是 CHAMBER、AMBER、NAMD、GROMACS,
可以下載使用,看一下別人如何做的,當然我們不需要做到像這些軟體這麼複雜。
雙魚:
著手將 MD 的 Code 改成 Multi-Thread,
目前先規劃將 Non-Bonded Force 的部份給平行,
如果修改完成,可以再加入 Bonded 的部分。
下一步,就是將它寫成 SPCI 的 Component。
威佐 :
目前已經將幾個常用的 Operations 取出,
需要計算的力包括:
Bonded(Bond length、Bond angle、Dihedral 三種力)和 Non-Bonded,
我相信這是簡化過的形式,但對於我們做加速運算已經足夠,
我現在使用的 Code 是學長給的那本書中的 Code (老師我沒有自己寫一個...)。
但是因為要先嘗試做 translator,所以先暫用書中的 Code,等到評估期過後,
我們可以自己改一份 MD 的 Code,
另外,現在成熟的 MD 套件大概是 CHAMBER、AMBER、NAMD、GROMACS,
可以下載使用,看一下別人如何做的,當然我們不需要做到像這些軟體這麼複雜。
雙魚:
著手將 MD 的 Code 改成 Multi-Thread,
目前先規劃將 Non-Bonded Force 的部份給平行,
如果修改完成,可以再加入 Bonded 的部分。
下一步,就是將它寫成 SPCI 的 Component。
2010年12月5日 星期日
ROC - 雙魚
=== 2010.11.23 ===
更改成matlab可連結的函式後
把此份.c檔放到要執行的matlab資料夾內
編譯.c檔的流程如下:
(1)如果是第一次用mex,先設定編譯器
執行 mex , 畫面會列出你電腦上現有的編譯器
選擇好後電腦會記下,以後使用就不用執行這步驟
(2)編譯.c檔 : 執行 mex xx.c (xx為檔名)
如果順利編譯通過,同一個資料夾下會出現xx.dll檔案
(3)接著就可以執行matlab code
比較原本matlab程式和呼叫 C library的matlab程式時間
(1)原本matlab程式:
for j = 1:1000 呼叫ROC計算函式 end
時間為: 8分鐘
(2)呼叫 C library的matlab程式:
for j = 1:1000 呼叫 ROC_scream() end
時間為: 0.679 s
呼叫 C library的matlab程式時間節省不少
11/23把此程式交給龔老師,也跟他說明了使用方法
ROC改寫到底為止
=== 2010.11.19 ===
把改寫後的C code包成matlab可用的library型式
即可在matlab程式中直接使用改寫後的code
參考連結: http://twntwn.info/blog/ajer001/archives/790
按照連結中的方法來更動原本的C code
matlab迴圈呼叫的寫法:
for j = 1:1000
[auc_resp_sf fa_resp_sf hr_resp_sf] = ROC_scream(all4type, all4respyesno_sf);
end
說明: ROC_scream()為改寫後的C code
all4type,all4respyesno_sf為輸入的數列
[auc_resp_sf fa_resp_sf hr_resp_sf]為output
fa_resp_sf和 hr_resp_sf是數列,auc_resp_sf為1*1的double
更動步驟如下:
(1)在code中開頭加入 #include "mex.h"
(2)將程式主要部分放在 mexFunction()中
mexFunction(int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[])
mexFunction()為程式的進入點,prototype不可隨意更動
(3)要把matlab輸入數列換成 C陣列
value = mxGetPr(prhs[0]);
sign = mxGetPr(prhs[1]);
bufsize = mxGetM(prhs[0]);
n = mxGetN(prhs[0]);
說明:
plhs: ROC_scream函式等號左邊參數本體
prhs: ROC_scream函式等號右邊參數本體
mxGetPr:取得矩陣之實數部分
mxGetM:取得矩陣之第一維大小
value會取得ROC_scream()中 all4type數列
sign會取得ROC_scream()中all4respyesno_sf數列
bufsize是all4type數列的row數量
n是all4type數列的column數量
(4)給予輸出陣列的記憶體空間
plhs[0]= mxCreateDoubleMatrix(mA,nA,mxREAL);
area = mxGetPr(plhs[0]);
說明:
利用mxCreateDoubleMatrix()建立空間
mA是row數量 nA是column數
plhs[0]代表為回傳的第一個參數,並取出取得矩陣之實數部分
=== 2010.11.08 ===
跟龔老師拿了他們使用輸入輸出的數據
以便於我們做更多數據的比對
每次輸入的a和b數列各160筆,要跑1000次
(1)和matlab code輸入相同的a,b數列
比對C code算出的面積數字是否和原本一樣
比對的結果皆正確
(2)比較兩份code時間 (迴圈1000次,每次160筆data)
matlab迴圈寫法為:
for j = 1:1000 呼叫ROC計算函式 end
時間結果如下:
Matlab時間為= 483.58 s ≈ 8分鐘
C code時間為= 1.984 s ≈ 約兩秒
=== 2010.10.30 ===
完成 ROC C code改寫
ROC程式內容如下:
(1)從輸入的數列中找出沒有重複的uv數列
input: 數列a和b (random ,各200個數值)
找出uv數列:為a和b中沒有重複的數值
舉例說明:
a = {-2,-1,0,3,8 }
b = {-3,1,3,0,8 }
uv = {-3,-2,-1,0,1,3,8}
(2)找 hit rate (hr) and false alarms (fa)
fa: a中有幾個大於等於uv數值 / a數列總合
hr: b中有幾個大於等於uv數值 / b數列總合
uv中每個數值都要檢查一次
舉例說明: uv ={ -3,-2,-1,0,1,3,8 }
a ={ -2,-1,0,3,8 } , b ={ -3,1,3,0,8 }
當uv[0]= -3 , fa[0]=1 and hr[0]=1
當uv[1]= -2 , fa[1]=1 and hr[1]=4/5
(3)計算ROC曲線下的面積 (參考圖)

matlab code : auc = trapz(fa,hr);
trapezoid function使用梯形公式算曲線下的面積
梯形的高為 fa[i] – fa[i+1]
上底為hr[i],下底為hr[i+1]
Auc = 梯形公式 ((上底+下底)*高)/2
舉例說明:
trapz([123],[124])
梯形第一塊: ((1+2)*(2-1))/2
梯形第二塊: ((2+4)*(3-2))/2
=== 2010.10.19 ===
在分析fMRI數據時,需要花費大量的計算和時間
心理系龔老師希望我們來幫忙減少code的計算時間
龔老師提供了他們主要計算部分的matlab程式碼
其中以"ROC"此部分所花費的時間最多
因此我們從此部分著手
老師的想法是把ROC此部分改成C code
改完後測時間看是否還要再作平行的方法
更改成matlab可連結的函式後
把此份.c檔放到要執行的matlab資料夾內
編譯.c檔的流程如下:
(1)如果是第一次用mex,先設定編譯器
執行 mex , 畫面會列出你電腦上現有的編譯器
選擇好後電腦會記下,以後使用就不用執行這步驟
(2)編譯.c檔 : 執行 mex xx.c (xx為檔名)
如果順利編譯通過,同一個資料夾下會出現xx.dll檔案
(3)接著就可以執行matlab code
比較原本matlab程式和呼叫 C library的matlab程式時間
(1)原本matlab程式:
for j = 1:1000 呼叫ROC計算函式 end
時間為: 8分鐘
(2)呼叫 C library的matlab程式:
for j = 1:1000 呼叫 ROC_scream() end
時間為: 0.679 s
呼叫 C library的matlab程式時間節省不少
11/23把此程式交給龔老師,也跟他說明了使用方法
ROC改寫到底為止
=== 2010.11.19 ===
把改寫後的C code包成matlab可用的library型式
即可在matlab程式中直接使用改寫後的code
參考連結: http://twntwn.info/blog/ajer001/archives/790
按照連結中的方法來更動原本的C code
matlab迴圈呼叫的寫法:
for j = 1:1000
[auc_resp_sf fa_resp_sf hr_resp_sf] = ROC_scream(all4type, all4respyesno_sf);
end
說明: ROC_scream()為改寫後的C code
all4type,all4respyesno_sf為輸入的數列
[auc_resp_sf fa_resp_sf hr_resp_sf]為output
fa_resp_sf和 hr_resp_sf是數列,auc_resp_sf為1*1的double
更動步驟如下:
(1)在code中開頭加入 #include "mex.h"
(2)將程式主要部分放在 mexFunction()中
mexFunction(int nlhs, mxArray *plhs[],
int nrhs, const mxArray *prhs[])
mexFunction()為程式的進入點,prototype不可隨意更動
(3)要把matlab輸入數列換成 C陣列
value = mxGetPr(prhs[0]);
sign = mxGetPr(prhs[1]);
bufsize = mxGetM(prhs[0]);
n = mxGetN(prhs[0]);
說明:
plhs: ROC_scream函式等號左邊參數本體
prhs: ROC_scream函式等號右邊參數本體
mxGetPr:取得矩陣之實數部分
mxGetM:取得矩陣之第一維大小
value會取得ROC_scream()中 all4type數列
sign會取得ROC_scream()中all4respyesno_sf數列
bufsize是all4type數列的row數量
n是all4type數列的column數量
(4)給予輸出陣列的記憶體空間
plhs[0]= mxCreateDoubleMatrix(mA,nA,mxREAL);
area = mxGetPr(plhs[0]);
說明:
利用mxCreateDoubleMatrix()建立空間
mA是row數量 nA是column數
plhs[0]代表為回傳的第一個參數,並取出取得矩陣之實數部分
=== 2010.11.08 ===
跟龔老師拿了他們使用輸入輸出的數據
以便於我們做更多數據的比對
每次輸入的a和b數列各160筆,要跑1000次
(1)和matlab code輸入相同的a,b數列
比對C code算出的面積數字是否和原本一樣
比對的結果皆正確
(2)比較兩份code時間 (迴圈1000次,每次160筆data)
matlab迴圈寫法為:
for j = 1:1000 呼叫ROC計算函式 end
時間結果如下:
Matlab時間為= 483.58 s ≈ 8分鐘
C code時間為= 1.984 s ≈ 約兩秒
=== 2010.10.30 ===
完成 ROC C code改寫
ROC程式內容如下:
(1)從輸入的數列中找出沒有重複的uv數列
input: 數列a和b (random ,各200個數值)
找出uv數列:為a和b中沒有重複的數值
舉例說明:
a = {-2,-1,0,3,8 }
b = {-3,1,3,0,8 }
uv = {-3,-2,-1,0,1,3,8}
(2)找 hit rate (hr) and false alarms (fa)
fa: a中有幾個大於等於uv數值 / a數列總合
hr: b中有幾個大於等於uv數值 / b數列總合
uv中每個數值都要檢查一次
舉例說明: uv ={ -3,-2,-1,0,1,3,8 }
a ={ -2,-1,0,3,8 } , b ={ -3,1,3,0,8 }
當uv[0]= -3 , fa[0]=1 and hr[0]=1
當uv[1]= -2 , fa[1]=1 and hr[1]=4/5
(3)計算ROC曲線下的面積 (參考圖)

matlab code : auc = trapz(fa,hr);
trapezoid function使用梯形公式算曲線下的面積
梯形的高為 fa[i] – fa[i+1]
上底為hr[i],下底為hr[i+1]
Auc = 梯形公式 ((上底+下底)*高)/2
舉例說明:
trapz([123],[124])
梯形第一塊: ((1+2)*(2-1))/2
梯形第二塊: ((2+4)*(3-2))/2
=== 2010.10.19 ===
在分析fMRI數據時,需要花費大量的計算和時間
心理系龔老師希望我們來幫忙減少code的計算時間
龔老師提供了他們主要計算部分的matlab程式碼
其中以"ROC"此部分所花費的時間最多
因此我們從此部分著手
老師的想法是把ROC此部分改成C code
改完後測時間看是否還要再作平行的方法
2010年12月3日 星期五
AVS/ H.264 -- 雙魚
=== 2010.10.08 ===
要開始進行motion search
用不同大小的block到reference frame中去找出cost最小的部分
這邊AVS是使用UMHexagonS Algorithm來做搜尋
演算法分成五個部分:
(1)Initial search point prediction
這個階段要找出一個比較適合的搜尋起始點
有四種prediction方法可以找出比較適合的點:
1.Median Prediction:
利用上一次算出來mvp去搜尋,找出cost最小的地方
2.UpLayer Prediction:
16x8,8x16: 參考16x16的mv去搜尋
8x8: 參考16x8的mv去搜尋
16x16:不作此項
3.Corresponding-block Prediction:
利用前一張frame同位置區塊的mv去搜尋

4.Neighboring Ref-frame Prediction:
利用到前面兩張frame來算出mv(如圖)
mv_pred = mv*(n-n')/(n-(n+1))

拿目前搜尋塊左上角座標,搭配上述四種方法提供的mv
到前一張frame去搜尋找出cost最小的區塊
如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,使用(2)去搜尋
(2)十字搜尋法:
搜尋範圍-16~16 水平範圍-16~16 垂直範圍-8~8
(參考圖) 每隔2個pixel當作一個搜尋點,找cost最小的區塊

如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,使用(3)去搜尋
(3)Uneven Multi-Hexagon-grid search:
分成兩個部分作搜尋:

1.小方型搜尋: (圖中紅色點區域)
先在-2~2之間內搜尋25點,找出cost最小的位置
如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,使用多重六角型搜尋
2.多重六角型搜尋: (圖中藍色點)
在六角形上的16個點作搜尋,用early termination去判斷是否要繼續
如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,重複上述步驟來找出cost最小的位置
(4)六角形搜尋法:
搜尋六角形上的六點頂點和中心點
沿著cost最小的點再造出六角型繼續搜尋
當cost最小的點出現在中心點即可結束搜尋
(5)小鑽石搜尋法:
搜尋菱形邊上的8個點和中心點
沿著cost最小的點再造出菱形繼續搜尋
當cost最小的點出現在中心點即可結束搜尋
做完上面流程可找出此次motion search的mincost和最佳mv
此部分code還有錯誤,AVS改寫就進行到這裡
=== 2010.09.20 ===
完成算Motion Vector Predictor的code
找motion vector(MV)前要先算Motion Vector Predictor(MVP)
利用周圍block的MV去推斷出這次壓縮比較可能的MV

MVP條件選擇如下:
1.先判斷block A,B,C 是否存在 (如果C不存在,則參考block D)
如果只有block A存在: 選block A的MV當 mvp
如果只有block B存在: 選block B的MV當 mvp
如果只有block C存在: 選block C的MV當 mvp
2.依照inter prediction的block size會有特殊選擇
如果是8x16 : 選block A的MV當 mvp ( A不存在就選 C )
如果是16x8 : 選block B的MV當 mvp ( B不存在就選 A )
3.block A,B,C都存在且block size不是8x16或16x8
先算三個block互相相減的差值: D1(A,B),D2(B,C),D3(C,A)
如果 D1 == median (D1, D2,D3 ),選block C的MV當 mvp
如果 D2 == median (D1, D2,D3 ),選block A的MV當 mvp
如果 D3 == median (D1, D2,D3 ),選block B的MV當 mvp
=== 2010.09.07 ===
完成 1/4 interpolation的code
先開一個圖片四倍大的記憶體空間 (4*352)*(4*288)
接著進行1/4 interpolation:

->灰點是原本的pixel,藍點是做完二分之一的pixel
白點是做完四分之一的pixel
(1)二分之一: filter用(-1, 5, 5, -1)
算法: b=(-C+5D+5E-F+4)>>3, j=(-aa+5b+5s-dd+4)>>3
(2)四分之一: filter用(1, 7, 7, 1)
算法: a=(ee+7D+7b+E+64)>>7, e=(D+j+64)>>7
結束運算後把結果依照相對位置存成16張352*288
圖中每個顏色的點要自己存成一張352*288

=== 2010.08.15 ===
規劃 inter prediction的流程:
1. 作四分之一的Interpolation

->灰點是原本的pixel,藍點是做完二分之一的pixel
白點是做完四分之一的pixel
(1)二分之一: filter用(-1, 5, 5, -1)
算法: b=(-C+5D+5E-F+4)>>3, j=(-aa+5b+5s-dd+4)>>3
(2)四分之一: filter用(1, 7, 7, 1)
算法: a=(ee+7D+7b+E+64)>>7, e=(D+j+64)>>7
2.找 motion vector

原本block位置是(10,4), 到前一張去找到最適合的block位置是(5,9)
motion vector則是(5,-5)
3.決定最好的inter mode
AVS提供16*16,16*8,8*16,8*8這幾種模式
每種模式都要去找motion vector,接著計算和原本pixel的差值
然後從中決定一種最好的mode
=== 2010.08.07 ===
規畫VLC的流程:
1. 每個8*8 block要經過z字型掃描
2. 找出block中的每組level和run,level是非0數值
run是這個非0值和下個非0值中間有幾個0
3.
(1)用maxAbslevel去找要查的table編號,initial從0開始

(2)透過(run,level)在table中找到對應的trans_coefficient

(3)利用trans_coefficient在golomb表找出相對應的bitstream
AVS有指定每張table要用的order

(4)若level的絕對值>maxAbslevel,要更新maxAbslevel和table編號
如果(run,level)在table中找不到對應的trans_coefficient,編碼流程如下:
(1) trans_coefficient = 59+ (run<<1)>0)? 1:0 )
(2) 拿(1)計算的trans_coefficient在golomb表找出bitstream
(3) 找RefAbsLevel數值 :
if run > MaxRun, RefAbsLevel =1 (MaxRun要查表)
Otherwise:從table中找到RefAbsLevel數值

(4) escape_level_diff = abs(level) – RefAbsLevel
(5) 拿(4)計算的escape_level_diff在golomb表找出bitstream
目前進度:完成上述流程的程式內容
以及和原本code比對最後找到的bitstream的長度和數值
=== 2010.07.20 ===
完成intra prediction流程的程式內容
for (block=0; block<4; diff =" 原本數值-最佳的預測數值;" recy =" new_diff" diff =" 原本數值-最佳的預測數值--(1)" recv =" new_diff"> quant -> inv_quant -> inv_DCT後的new_diff
還原回來的數值等於new_diff 加上 預測出來最佳mode的數值
luma/chroma predictionn算每種mode的預測值會用到還原回來的數值
接著去比對還原回來的數值是否和原本程式一樣
=== 2010.07.05 ===
畫intra prediction的流程:
for (block=0; block<4;> quant -> inv_quant -> inv_DCT
因為圖片為4個Y對到一個U一個V,所以一個MB只會對到1個8*8的U和V
所以等四個Luma_Prediction結束後換成Chroma_Prediction()
Chroma_Prediction()裡面包含U,V的prediction
最後就是DCT-> quant -> inv_quant -> inv_DCT
Luma_Prediction()流程:
(1)算luma prediction中每種mode的預測值
(2)算 mostProbableMode
(3)從5個mode中找出cost最小的mode,mostProbableMode會影響cost

原本5種mode需要花3個bit去表示,所以每個mode都需要3 bit
若有mostProbableMode來標記,其他4個mode各需要3bit
但mostProbableMode的只要1 bit,就能省下一些bit
Chroma_Prediction()流程:
(1)算chroma prediction中每種mode的預測值
(3)從4個mode中找出cost最小的mode
=== 2010.06.22 ===
完成 quantization 和 inverse quantization函式
quantization是 把DCT transform後的數值除以一個數
避免用除法,所以先乘上一個倍數,四捨五入後再shift回來,看式子(1)
(1) b = ( a * quantTable(QP) + qp_const) >> 15
b:quantization後的數值 , a:DCT transform後取絕對值的數值
quantTable(QP): 這張表裡有每個QP應該乘上的數值
qp_const: 四捨五入用
>>15: 是把quantTable(QP)乘上的倍數shift回來
inverse quantization則是把 quantization後的數值乘上一個數,式子(2)
(2) c=( (b*DequantTable(QP))+ 2ShiftTable(QP)–1)>> ShiftTable(QP)
b:quantization後的數值
DequantTable(QP):表中有每個QP應該乘上的數值
2ShiftTable(QP)–1 : 四捨五入用
>> ShiftTable(QP): 把DequantTable(QP)乘上的倍數shift回來
程式流程: DCT-> quant -> inv_quant -> inv_DCT
開檔讀進DCT前的數值,比對inv_DCT後的數值是否和原本程式數值一樣
=== 2010.06.13 ===
完成 DCT transform 和 inverse DCT 的函式
DCT transform 流程: X是這次要作transform的8*8矩陣
(1) D =(X)(A) , A是AVS規定要乘的DCT 8*8矩陣
(2) D'=(T)(D) , T是A矩陣的轉置矩陣
(3) 讓D'數值落在 -2^15 ~ 2^15 中
inverse DCT 流程: X是這次要作inv_transform的8*8矩陣
(1) D =(X)(T) , T是AVS規定的8*8矩陣的轉置矩陣
(2) 讓D數值落在 -2^15 ~ 2^15 中
(3) D'=(A)(D) , A是AVS規定要乘的DCT 8*8矩陣
(4) 讓D'數值落在 -2^15 ~ 2^15 中
開檔讀進 DCT前 和 inv_DCT前的數值
各經過 DCT transform 和 inverse DCT 計算
去比對 DCT後 和 inv_DCT後 的數值是否和原本程式數值一樣
=== 2010.06.04 ===
從DCT transform開始,一樣從去原本程式找DCT transform
luma DCT在 rdpot.c , chroma DCT 在marcoblock.c
luma chroma的inverse DCT步驟都包含在squant函式中
squant函式位在block.c中
squant函式會呼叫inv_transform函式作inverse transform
取出 "DCT前, DCT後,inv_DCT前,inv_DCT後" 的數值
這些數值用來比對接下來改寫後的數值是否正確
=== 2010.05.28 ===
這禮拜找intra chroma 8*8的最佳模式
算完每種模式預測的數值,要從中選一種最好的預測數值
去計算(原本圖片數值 - 預測數值)之間的差值總和
差值越小的就是最好的預測模式
最後拿原本程式取出的 最佳模式預測結果數值
來比對數值是否正確
intra prediction因為進度不如預期
之前寫的內容就先暫時這樣
決定改成從DCT transform開始寫
=== 2010.05.21 ===
這禮拜先找intra luma 8*8的最佳模式
算完每種模式預測的數值,要從中選一種最好的預測數值
去計算(原本圖片數值 - 預測數值)的絕對值總和
總和越小的就是最好的預測模式
這邊要先算每個8*8 block的upmode 和 leftmode
如果8*8的y座標等於0 代表此8*8位在frame的最上排
所以此block的upmode等於-1
如果8*8的x座標等於0 代表此8*8位在frame的最左邊排
所以此block的leftmode等於-1
如果8*8不是位在最上排和最左排
upmode和leftmode要參考鄰近block的mode (參考下圖)

1.左上橘色塊: upmode = 1 , leftmode = 2
2.右上橘色塊: upmode = 4 , leftmode = 3
3.左下橘色塊: upmode = 3 , leftmode = 3
4.右下橘色塊: upmode = 2 , leftmode = 2
紫色數字是代表前一個步驟橘色塊算出來的bestmode
最後用upmode和leftmode去找出probable mode
probable mode會影響到計算差值總和
最後拿原本程式取出的 最佳模式預測結果數值
來比對數值是否正確
=== 2010.05.14 ===
這禮拜寫intra chroma 8*8提供的4種模式
4種模式分別是 垂直 水平 DC plane
參考文件提供的數學式和原本程式內容去改寫
原本程式是開一個陣列 a[2][][]去存U,V
a[0][][]存U , a[1][][]存V
我的程式是用*pre_U *preV分別去存
所以原本程式有些地方要跑迴圈 一次算U一次算V
改寫後可以把迴圈拿掉 一次直接算完U,V
這邊也是把程式內容的判斷式作整理
有些相同判斷的內容可以合併一起
最後拿原本程式取出的每種模式預測結果數值
來比對數值是否正確
=== 2010.05.07 ===
從intra luma 8*8提供的5種模式開始寫
5種模式分別是 垂直 水平 DC down_left down_right
參考文件提供的數學式和原本程式內容去改寫
主要是將程式內容的判斷式作整理
有些相同判斷的內容可以合併一起
最後拿原本程式取出的每種模式預測結果數值
來比對數值是否正確
=== 2010.04.30 ===
定義目前寫程式需要用到的資料結構
例如frame的基本資訊(YUV數值的大小型態和frame寬高 座標位置)
MarcoBlock的資料(YUV數值和座標位置)
intra prediction用來參考的MB資料
從intra prediction開始, AVS提供8*8大小的prediction
所以先去原本程式中找intra prediction的程式內容
intra luma在block.c, intra chroma在marcoblock.c
取出 "預測前, 每種模式的預測結果, 最好的預測結果" 的數值
這些數值用來比對接下來改寫後的數值是否正確
== 2010.02.28===
在程式中去找intra prediction幾種比對模式的程式碼
luma有分成16*16和4*4兩種,Chroma提供4種兩個8*8模式
(1)luma 16*16是以一個16*16大小block去作預測,提供4種模式

(2)luma 4*4是把一個16*16 block再切成4個4*4去作預測,提供9種模式

(3)Chroma提供4種兩個8*8模式,分別是DC Mode、Horizontal Mode、
Vertical Mode、和 Plane Mode , 其中DC Mode會把8*8再切成4*4 block
依照每個4*4 block上側和左側資訊而有不同的數學式子去進行預測
這邊有從網路上找資料,資料pdf中有每一種預測模式的數學式子
從式子去推導每一點像素的式子數字,接著再和程式碼的寫法相對照
參考的pdf連結: http://0rz.com/LnhA
這學期理想的進度甘特圖

希望一個月可以完成一個元件的改寫,先從intra prediction開始
下禮拜會看AVS中intra prediction的文件內容
== 2010.02.01===
對quatization後的Y數值來壓縮和解壓縮
利用上次產生出來的codeword table來練習
(1)去找每個數值對應的codeword
ex:有三個數值5,13,-5, 5的codeword是101
13的codeword是0101 ,-5的codeword是1111
(2)codeword累積到8個以1個byte寫入新的檔案
設一個變數unsigned char c去記錄要寫入檔案的數值
a陣列記錄要壓縮數值所對應的codeword
當a[i]=1 , c = c先往左shift一個 再和00000001 作or
當a[i]=0 , c = c往左shift一個
如果c未滿8個 後面也沒有其他數值要壓縮
c=c往左shift讓剩下位置補0到滿8個
ex: 要壓數值5,13,-5 , codeword如(1)
第一次a陣列中是101, 判斷完a陣列中每個位置後 c=00000101
第二次a陣列中是0101, 判斷完a陣列中每個位置後 c=01010101
第三次a陣列中是1111, 判斷完a[0]位置後 c=10101011 已經達到8個
這時候就要把c寫入檔案 , 寫檔後讓c=0 再繼續判斷a陣列中剩下的位置
判斷完剩下的位置 c=00000111 , 因為後面沒有數值要壓縮所以補0
c = 11100000 , 最後再把此值寫入檔案中
(3)把(2)寫入的檔案讀出 , 把1個byte拆成8個bit
讀出1個unsigned char c 後 ,下面的動作要作8次
先 c= c和10000000作and , 再讓c往左shift一位
把解出來的bit放在buf 陣列中
ex: 把(2)產生的檔案數值讀出做完拆解判斷後
buf中會是: 10101011 11100000
(4)到table中找codeword對應的數值
table會先依照codeword大小排序 , 從小到大排序
buf會一個一個位置去找現在停在哪個codeword中的哪bit
如果此codeword下一個bit是'\0' , 代表找到一個對應的數值
ex: 假設table只有三種codeword , 設定如(1)
codeword排序後是: 0101 , 101 , 1111
buf是: 10101011 11100000
當buf[0]=1 , 會停在 codeword 101 中的第0個bit
當buf[1]=0 , 會停在 codeword 101 中的第1個bit
當buf[2]=1 , 會停在 codeword 101 中的第2個bit
codeword 101 第三個bit是 '\0' , 所以就找到一個對應數值5
== 2010.01.22===
建立 huffman tree來產生對應的codeword
拿上禮拜作完quatization後的Y數值來練習
(1)去計算Y數值中每一種數值出現的機率
假設4種節點機率分別為0.15 , 0.2 , 0.25 , 0.4 (圖中紫色點)
(2)開始建立 huffman tree
S為所有節點的集合 , 從S中找出機率最小的兩個 : t1 t2
用t1 t2來產生一新節點N, N 是 t1 和 t2 的 parent節點
而且N的機率為 t1 + t2 , 接著把 t1 t2 從S中刪掉, 把新節點 N 加入S中
圖中用4種節點來說明步驟 , S= {0.15,0.2,0.25,0.4}
先拿0.15 和 0.2 來組合 , 此樹節點機率為0.35 (圖中藍色點)
把 0.15 和 0.2 從S中刪掉 , 把藍色點的樹0.35加入S中
接著拿0.25 和 藍色點的樹 來組合 , 此樹節點機率為0.6 (圖中咖啡點)
把0.25 和 藍色點的樹從S中刪掉, 把咖啡點的樹0.6加入S中
最後拿0.4和 咖啡點的樹 來組合 , 最後root的機率為1

(3)去找每種數值對應的codeword
左邊樹分支填 0, 右邊樹分支填 1
每個分支的 0 或 1 是圖上的黃底綠色字
每種數值的codeword就是從root到該數值節點的 0 和 1 組合
從圖上標記可以看到:
數值0.4的codeword是 0
數值 0.25的codeword是 10
數值 0.15的codeword是 110
數值 0.2 的codeword是 111
== 2010.01.15===
完成 DCT-> quatization -> IDCT 的練習
一樣是用txt檔案中的YUV數值
分別對YUV去作DCT-> quatization -> IDCT
YUV以4:2:0的方式儲存 , 4個Y共用一個U和V
所以 Y 範圍是352*288 , U和V則是 176 *144
先對Y作處理 , 接著就是U和V , 每次都以8*8為單位
流程如下:
(1)用下列的公式去產生DCT 8*8矩陣的數值
Aij = Ci*(cos((2*j+1)*i*pi)/2*N) ,
when i=0 , Ci= (1/N)^1/2
when i>0 , Ci= (2/N)^1/2
因為DCT是8*8 , 所以N=8
Aij代表的是矩陣中第 i行第j列的數值
DCT陣列的數值是double的形態儲存
(2)利用 D=(A)(X)(T)來作DCT
A是步驟(1)產生的DCT矩陣
T是A矩陣的轉置矩陣
X是圖片切出來的8*8方塊
D是AXT三者作矩陣運算後的8*8矩陣
D也是用double的形態儲存
(3)去網路找 YUV的 quatization table
quatization table也是8*8的矩陣
把經過DCT後的數值除以quatization table上的數值
除以quatization後的數值先做四捨五入
接著以 int的型式儲存起來
(4)把步驟(3)儲存的數值再乘上quatization table的數值
再以double的形態把乘完quatization的數值儲存起來
這時候會發現數值和一開始經過DCT後的數值有稍微的不同
ex: 經過DCT後是527.89 , 除以quatization 16 再四捨五入後
會以33的數值存起來 , 再乘回quatization 16 會變成528
雖然會有些微的不同 但是誤差都不會太大
(5)利用 X=(T)(D)(A) 來作IDCT
A是步驟(1)產生的DCT矩陣
T是A矩陣的轉置矩陣
D是步驟(4)儲存的8*8矩陣
X是TDA三者作矩陣運算得到的8*8矩陣
要去判斷X中的每一點的數值
如果數值>255, 要讓它等於255
如果數值<0 30="="="">RGB 的公式去計算
如果轉換後的數值>255, 要讓它等於255
如果轉換後的數值<0 ,要讓它等於0

這邊是練習對MB 和 frame的位置概念
參考圖片 , 整張圖是352*288, MB是16*16 (圖中紅色方塊)
txt檔中是把每個MB中16的點 由左至右 由上到下寫入
一個MB寫完在換下一個 , MB也是由左至右 由上到下
frame是一個點一個點讀取 由左至右 由上到下 (圖中紫色方塊)
所以讀出txt檔每一個數值, 都要放回它在圖片的原本位置
步驟2是把圖片一個點一個點的讀入,然後儲存起來
最後再比較這兩個種數值是否有一致
== 2009.12.10===
目前已經把上次提的數值抓出
除了bitrate, 其他數值都以binary型式寫入檔案
1. 每個16*16 (MB) 的數值
圖片大小352*288 , 每16*16切成一塊
把16*16裡每點的pixel數值寫入檔案
2. 每個MB作完intra prediction的different值
intra prediction 分成 4*4和 16*16 兩種
(1) 4*4有9種mode , 每一種mode都會算出一個different值
先用一個陣列暫存每種mode算出來的different值
接著計算每種mode的cost大小, 找出一個最好的mode
這邊也會有個變數去記錄哪個mode是cost最小的
最後把此種mode的different值存進陣列(a4)
以4*4 去算different值 , 但最後要的是16*16
所以每次算完的4*4 要按著順序存進陣列(a4)
(2)16*16則有4種mode , 作法同上
差別在於 這邊是用16*16去算different值
只要把最好mode的different值存進陣列(a16)即可
作完上述兩點 , 每個MB會有 4*4 和 16*16算完的最佳解
會從中選一個來當作這個MB使用的different值
所以最後選出的different值才是要寫入檔案的
3. 每個MB作完 DCT+ quantization 後的數值
程式作完 DCT+ quantization的值存在 nMBQuant_Y變數裡
而且大小也是宣告成 16*16
只要將 此變數中 256個數值 寫入檔案即可
有記錄 Frame_I DCT+ quantization 後的數值
以及 Frame_P DCT+ quantization 後的數值
4. 得到每個MB需要的bits數量
此數值存在nRDBitRate變數裡
只要將此變數的值寫入檔案即可
一樣要記錄 Frame_I 和 Frame_P的BitRate
== 2009.11.18 ===
已經跟小新學長拿了程式
為了達成了解基本的H.264運作流程
計畫先取出下列幾個數值:
1.抓出MB pixel值
2.抓出MB pixel值 做過 Prediction(inter or intra)
3.抓出MB 4x4 DCT值
4.抓出MB 4x4 DCT值做過 quantization
5.得到MB壓縮所需要的bits數量
把這五個項目的數值取出來,分別存成一個新檔
這些檔案裡面的數值是後續步驟會使用到的
存檔的類型沒有限制 , 我想說把每項的數據存成txt檔
就從第一項開始作起 , 現在剛看程式 大略知道第一項要的數值在哪
這邊會再問一下學長 , 希望下禮拜可以抓出第一項的數值
要開始進行motion search
用不同大小的block到reference frame中去找出cost最小的部分
這邊AVS是使用UMHexagonS Algorithm來做搜尋
演算法分成五個部分:
(1)Initial search point prediction
這個階段要找出一個比較適合的搜尋起始點
有四種prediction方法可以找出比較適合的點:
1.Median Prediction:
利用上一次算出來mvp去搜尋,找出cost最小的地方
2.UpLayer Prediction:
16x8,8x16: 參考16x16的mv去搜尋
8x8: 參考16x8的mv去搜尋
16x16:不作此項
3.Corresponding-block Prediction:
利用前一張frame同位置區塊的mv去搜尋

4.Neighboring Ref-frame Prediction:
利用到前面兩張frame來算出mv(如圖)
mv_pred = mv*(n-n')/(n-(n+1))

拿目前搜尋塊左上角座標,搭配上述四種方法提供的mv
到前一張frame去搜尋找出cost最小的區塊
如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,使用(2)去搜尋
(2)十字搜尋法:
搜尋範圍-16~16 水平範圍-16~16 垂直範圍-8~8
(參考圖) 每隔2個pixel當作一個搜尋點,找cost最小的區塊

如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,使用(3)去搜尋
(3)Uneven Multi-Hexagon-grid search:
分成兩個部分作搜尋:

1.小方型搜尋: (圖中紅色點區域)
先在-2~2之間內搜尋25點,找出cost最小的位置
如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,使用多重六角型搜尋
2.多重六角型搜尋: (圖中藍色點)
在六角形上的16個點作搜尋,用early termination去判斷是否要繼續
如果此時有符合early termination的條件
可直接跳到(4)或(5)進行小範圍搜尋
如果沒有符合條件,重複上述步驟來找出cost最小的位置
(4)六角形搜尋法:
搜尋六角形上的六點頂點和中心點
沿著cost最小的點再造出六角型繼續搜尋
當cost最小的點出現在中心點即可結束搜尋
(5)小鑽石搜尋法:
搜尋菱形邊上的8個點和中心點
沿著cost最小的點再造出菱形繼續搜尋
當cost最小的點出現在中心點即可結束搜尋
做完上面流程可找出此次motion search的mincost和最佳mv
此部分code還有錯誤,AVS改寫就進行到這裡
=== 2010.09.20 ===
完成算Motion Vector Predictor的code
找motion vector(MV)前要先算Motion Vector Predictor(MVP)
利用周圍block的MV去推斷出這次壓縮比較可能的MV

MVP條件選擇如下:
1.先判斷block A,B,C 是否存在 (如果C不存在,則參考block D)
如果只有block A存在: 選block A的MV當 mvp
如果只有block B存在: 選block B的MV當 mvp
如果只有block C存在: 選block C的MV當 mvp
2.依照inter prediction的block size會有特殊選擇
如果是8x16 : 選block A的MV當 mvp ( A不存在就選 C )
如果是16x8 : 選block B的MV當 mvp ( B不存在就選 A )
3.block A,B,C都存在且block size不是8x16或16x8
先算三個block互相相減的差值: D1(A,B),D2(B,C),D3(C,A)
如果 D1 == median (D1, D2,D3 ),選block C的MV當 mvp
如果 D2 == median (D1, D2,D3 ),選block A的MV當 mvp
如果 D3 == median (D1, D2,D3 ),選block B的MV當 mvp
=== 2010.09.07 ===
完成 1/4 interpolation的code
先開一個圖片四倍大的記憶體空間 (4*352)*(4*288)
接著進行1/4 interpolation:
->灰點是原本的pixel,藍點是做完二分之一的pixel
白點是做完四分之一的pixel
(1)二分之一: filter用(-1, 5, 5, -1)
算法: b=(-C+5D+5E-F+4)>>3, j=(-aa+5b+5s-dd+4)>>3
(2)四分之一: filter用(1, 7, 7, 1)
算法: a=(ee+7D+7b+E+64)>>7, e=(D+j+64)>>7
結束運算後把結果依照相對位置存成16張352*288
圖中每個顏色的點要自己存成一張352*288

=== 2010.08.15 ===
規劃 inter prediction的流程:
1. 作四分之一的Interpolation
->灰點是原本的pixel,藍點是做完二分之一的pixel
白點是做完四分之一的pixel
(1)二分之一: filter用(-1, 5, 5, -1)
算法: b=(-C+5D+5E-F+4)>>3, j=(-aa+5b+5s-dd+4)>>3
(2)四分之一: filter用(1, 7, 7, 1)
算法: a=(ee+7D+7b+E+64)>>7, e=(D+j+64)>>7
2.找 motion vector
原本block位置是(10,4), 到前一張去找到最適合的block位置是(5,9)
motion vector則是(5,-5)
3.決定最好的inter mode
AVS提供16*16,16*8,8*16,8*8這幾種模式
每種模式都要去找motion vector,接著計算和原本pixel的差值
然後從中決定一種最好的mode
=== 2010.08.07 ===
規畫VLC的流程:
1. 每個8*8 block要經過z字型掃描
2. 找出block中的每組level和run,level是非0數值
run是這個非0值和下個非0值中間有幾個0
3.
(1)用maxAbslevel去找要查的table編號,initial從0開始
(2)透過(run,level)在table中找到對應的trans_coefficient
(3)利用trans_coefficient在golomb表找出相對應的bitstream
AVS有指定每張table要用的order
(4)若level的絕對值>maxAbslevel,要更新maxAbslevel和table編號
如果(run,level)在table中找不到對應的trans_coefficient,編碼流程如下:
(1) trans_coefficient = 59+ (run<<1)>0)? 1:0 )
(2) 拿(1)計算的trans_coefficient在golomb表找出bitstream
(3) 找RefAbsLevel數值 :
if run > MaxRun, RefAbsLevel =1 (MaxRun要查表)
Otherwise:從table中找到RefAbsLevel數值
(4) escape_level_diff = abs(level) – RefAbsLevel
(5) 拿(4)計算的escape_level_diff在golomb表找出bitstream
目前進度:完成上述流程的程式內容
以及和原本code比對最後找到的bitstream的長度和數值
=== 2010.07.20 ===
完成intra prediction流程的程式內容
for (block=0; block<4; diff =" 原本數值-最佳的預測數值;" recy =" new_diff" diff =" 原本數值-最佳的預測數值--(1)" recv =" new_diff"> quant -> inv_quant -> inv_DCT後的new_diff
還原回來的數值等於new_diff 加上 預測出來最佳mode的數值
luma/chroma predictionn算每種mode的預測值會用到還原回來的數值
接著去比對還原回來的數值是否和原本程式一樣
=== 2010.07.05 ===
畫intra prediction的流程:
for (block=0; block<4;> quant -> inv_quant -> inv_DCT
因為圖片為4個Y對到一個U一個V,所以一個MB只會對到1個8*8的U和V
所以等四個Luma_Prediction結束後換成Chroma_Prediction()
Chroma_Prediction()裡面包含U,V的prediction
最後就是DCT-> quant -> inv_quant -> inv_DCT
Luma_Prediction()流程:
(1)算luma prediction中每種mode的預測值
(2)算 mostProbableMode
(3)從5個mode中找出cost最小的mode,mostProbableMode會影響cost
原本5種mode需要花3個bit去表示,所以每個mode都需要3 bit
若有mostProbableMode來標記,其他4個mode各需要3bit
但mostProbableMode的只要1 bit,就能省下一些bit
Chroma_Prediction()流程:
(1)算chroma prediction中每種mode的預測值
(3)從4個mode中找出cost最小的mode
=== 2010.06.22 ===
完成 quantization 和 inverse quantization函式
quantization是 把DCT transform後的數值除以一個數
避免用除法,所以先乘上一個倍數,四捨五入後再shift回來,看式子(1)
(1) b = ( a * quantTable(QP) + qp_const) >> 15
b:quantization後的數值 , a:DCT transform後取絕對值的數值
quantTable(QP): 這張表裡有每個QP應該乘上的數值
qp_const: 四捨五入用
>>15: 是把quantTable(QP)乘上的倍數shift回來
inverse quantization則是把 quantization後的數值乘上一個數,式子(2)
(2) c=( (b*DequantTable(QP))+ 2ShiftTable(QP)–1)>> ShiftTable(QP)
b:quantization後的數值
DequantTable(QP):表中有每個QP應該乘上的數值
2ShiftTable(QP)–1 : 四捨五入用
>> ShiftTable(QP): 把DequantTable(QP)乘上的倍數shift回來
程式流程: DCT-> quant -> inv_quant -> inv_DCT
開檔讀進DCT前的數值,比對inv_DCT後的數值是否和原本程式數值一樣
=== 2010.06.13 ===
完成 DCT transform 和 inverse DCT 的函式
DCT transform 流程: X是這次要作transform的8*8矩陣
(1) D =(X)(A) , A是AVS規定要乘的DCT 8*8矩陣
(2) D'=(T)(D) , T是A矩陣的轉置矩陣
(3) 讓D'數值落在 -2^15 ~ 2^15 中
inverse DCT 流程: X是這次要作inv_transform的8*8矩陣
(1) D =(X)(T) , T是AVS規定的8*8矩陣的轉置矩陣
(2) 讓D數值落在 -2^15 ~ 2^15 中
(3) D'=(A)(D) , A是AVS規定要乘的DCT 8*8矩陣
(4) 讓D'數值落在 -2^15 ~ 2^15 中
開檔讀進 DCT前 和 inv_DCT前的數值
各經過 DCT transform 和 inverse DCT 計算
去比對 DCT後 和 inv_DCT後 的數值是否和原本程式數值一樣
=== 2010.06.04 ===
從DCT transform開始,一樣從去原本程式找DCT transform
luma DCT在 rdpot.c , chroma DCT 在marcoblock.c
luma chroma的inverse DCT步驟都包含在squant函式中
squant函式位在block.c中
squant函式會呼叫inv_transform函式作inverse transform
取出 "DCT前, DCT後,inv_DCT前,inv_DCT後" 的數值
這些數值用來比對接下來改寫後的數值是否正確
=== 2010.05.28 ===
這禮拜找intra chroma 8*8的最佳模式
算完每種模式預測的數值,要從中選一種最好的預測數值
去計算(原本圖片數值 - 預測數值)之間的差值總和
差值越小的就是最好的預測模式
最後拿原本程式取出的 最佳模式預測結果數值
來比對數值是否正確
intra prediction因為進度不如預期
之前寫的內容就先暫時這樣
決定改成從DCT transform開始寫
=== 2010.05.21 ===
這禮拜先找intra luma 8*8的最佳模式
算完每種模式預測的數值,要從中選一種最好的預測數值
去計算(原本圖片數值 - 預測數值)的絕對值總和
總和越小的就是最好的預測模式
這邊要先算每個8*8 block的upmode 和 leftmode
如果8*8的y座標等於0 代表此8*8位在frame的最上排
所以此block的upmode等於-1
如果8*8的x座標等於0 代表此8*8位在frame的最左邊排
所以此block的leftmode等於-1
如果8*8不是位在最上排和最左排
upmode和leftmode要參考鄰近block的mode (參考下圖)
1.左上橘色塊: upmode = 1 , leftmode = 2
2.右上橘色塊: upmode = 4 , leftmode = 3
3.左下橘色塊: upmode = 3 , leftmode = 3
4.右下橘色塊: upmode = 2 , leftmode = 2
紫色數字是代表前一個步驟橘色塊算出來的bestmode
最後用upmode和leftmode去找出probable mode
probable mode會影響到計算差值總和
最後拿原本程式取出的 最佳模式預測結果數值
來比對數值是否正確
=== 2010.05.14 ===
這禮拜寫intra chroma 8*8提供的4種模式
4種模式分別是 垂直 水平 DC plane
參考文件提供的數學式和原本程式內容去改寫
原本程式是開一個陣列 a[2][][]去存U,V
a[0][][]存U , a[1][][]存V
我的程式是用*pre_U *preV分別去存
所以原本程式有些地方要跑迴圈 一次算U一次算V
改寫後可以把迴圈拿掉 一次直接算完U,V
這邊也是把程式內容的判斷式作整理
有些相同判斷的內容可以合併一起
最後拿原本程式取出的每種模式預測結果數值
來比對數值是否正確
=== 2010.05.07 ===
從intra luma 8*8提供的5種模式開始寫
5種模式分別是 垂直 水平 DC down_left down_right
參考文件提供的數學式和原本程式內容去改寫
主要是將程式內容的判斷式作整理
有些相同判斷的內容可以合併一起
最後拿原本程式取出的每種模式預測結果數值
來比對數值是否正確
=== 2010.04.30 ===
定義目前寫程式需要用到的資料結構
例如frame的基本資訊(YUV數值的大小型態和frame寬高 座標位置)
MarcoBlock的資料(YUV數值和座標位置)
intra prediction用來參考的MB資料
從intra prediction開始, AVS提供8*8大小的prediction
所以先去原本程式中找intra prediction的程式內容
intra luma在block.c, intra chroma在marcoblock.c
取出 "預測前, 每種模式的預測結果, 最好的預測結果" 的數值
這些數值用來比對接下來改寫後的數值是否正確
== 2010.02.28===
在程式中去找intra prediction幾種比對模式的程式碼
luma有分成16*16和4*4兩種,Chroma提供4種兩個8*8模式
(1)luma 16*16是以一個16*16大小block去作預測,提供4種模式
(2)luma 4*4是把一個16*16 block再切成4個4*4去作預測,提供9種模式
(3)Chroma提供4種兩個8*8模式,分別是DC Mode、Horizontal Mode、
Vertical Mode、和 Plane Mode , 其中DC Mode會把8*8再切成4*4 block
依照每個4*4 block上側和左側資訊而有不同的數學式子去進行預測
這邊有從網路上找資料,資料pdf中有每一種預測模式的數學式子
從式子去推導每一點像素的式子數字,接著再和程式碼的寫法相對照
參考的pdf連結: http://0rz.com/LnhA
這學期理想的進度甘特圖

希望一個月可以完成一個元件的改寫,先從intra prediction開始
下禮拜會看AVS中intra prediction的文件內容
== 2010.02.01===
對quatization後的Y數值來壓縮和解壓縮
利用上次產生出來的codeword table來練習
(1)去找每個數值對應的codeword
ex:有三個數值5,13,-5, 5的codeword是101
13的codeword是0101 ,-5的codeword是1111
(2)codeword累積到8個以1個byte寫入新的檔案
設一個變數unsigned char c去記錄要寫入檔案的數值
a陣列記錄要壓縮數值所對應的codeword
當a[i]=1 , c = c先往左shift一個 再和00000001 作or
當a[i]=0 , c = c往左shift一個
如果c未滿8個 後面也沒有其他數值要壓縮
c=c往左shift讓剩下位置補0到滿8個
ex: 要壓數值5,13,-5 , codeword如(1)
第一次a陣列中是101, 判斷完a陣列中每個位置後 c=00000101
第二次a陣列中是0101, 判斷完a陣列中每個位置後 c=01010101
第三次a陣列中是1111, 判斷完a[0]位置後 c=10101011 已經達到8個
這時候就要把c寫入檔案 , 寫檔後讓c=0 再繼續判斷a陣列中剩下的位置
判斷完剩下的位置 c=00000111 , 因為後面沒有數值要壓縮所以補0
c = 11100000 , 最後再把此值寫入檔案中
(3)把(2)寫入的檔案讀出 , 把1個byte拆成8個bit
讀出1個unsigned char c 後 ,下面的動作要作8次
先 c= c和10000000作and , 再讓c往左shift一位
把解出來的bit放在buf 陣列中
ex: 把(2)產生的檔案數值讀出做完拆解判斷後
buf中會是: 10101011 11100000
(4)到table中找codeword對應的數值
table會先依照codeword大小排序 , 從小到大排序
buf會一個一個位置去找現在停在哪個codeword中的哪bit
如果此codeword下一個bit是'\0' , 代表找到一個對應的數值
ex: 假設table只有三種codeword , 設定如(1)
codeword排序後是: 0101 , 101 , 1111
buf是: 10101011 11100000
當buf[0]=1 , 會停在 codeword 101 中的第0個bit
當buf[1]=0 , 會停在 codeword 101 中的第1個bit
當buf[2]=1 , 會停在 codeword 101 中的第2個bit
codeword 101 第三個bit是 '\0' , 所以就找到一個對應數值5
== 2010.01.22===
建立 huffman tree來產生對應的codeword
拿上禮拜作完quatization後的Y數值來練習
(1)去計算Y數值中每一種數值出現的機率
假設4種節點機率分別為0.15 , 0.2 , 0.25 , 0.4 (圖中紫色點)
(2)開始建立 huffman tree
S為所有節點的集合 , 從S中找出機率最小的兩個 : t1 t2
用t1 t2來產生一新節點N, N 是 t1 和 t2 的 parent節點
而且N的機率為 t1 + t2 , 接著把 t1 t2 從S中刪掉, 把新節點 N 加入S中
圖中用4種節點來說明步驟 , S= {0.15,0.2,0.25,0.4}
先拿0.15 和 0.2 來組合 , 此樹節點機率為0.35 (圖中藍色點)
把 0.15 和 0.2 從S中刪掉 , 把藍色點的樹0.35加入S中
接著拿0.25 和 藍色點的樹 來組合 , 此樹節點機率為0.6 (圖中咖啡點)
把0.25 和 藍色點的樹從S中刪掉, 把咖啡點的樹0.6加入S中
最後拿0.4和 咖啡點的樹 來組合 , 最後root的機率為1
(3)去找每種數值對應的codeword
左邊樹分支填 0, 右邊樹分支填 1
每個分支的 0 或 1 是圖上的黃底綠色字
每種數值的codeword就是從root到該數值節點的 0 和 1 組合
從圖上標記可以看到:
數值0.4的codeword是 0
數值 0.25的codeword是 10
數值 0.15的codeword是 110
數值 0.2 的codeword是 111
== 2010.01.15===
完成 DCT-> quatization -> IDCT 的練習
一樣是用txt檔案中的YUV數值
分別對YUV去作DCT-> quatization -> IDCT
YUV以4:2:0的方式儲存 , 4個Y共用一個U和V
所以 Y 範圍是352*288 , U和V則是 176 *144
先對Y作處理 , 接著就是U和V , 每次都以8*8為單位
流程如下:
(1)用下列的公式去產生DCT 8*8矩陣的數值
Aij = Ci*(cos((2*j+1)*i*pi)/2*N) ,
when i=0 , Ci= (1/N)^1/2
when i>0 , Ci= (2/N)^1/2
因為DCT是8*8 , 所以N=8
Aij代表的是矩陣中第 i行第j列的數值
DCT陣列的數值是double的形態儲存
(2)利用 D=(A)(X)(T)來作DCT
A是步驟(1)產生的DCT矩陣
T是A矩陣的轉置矩陣
X是圖片切出來的8*8方塊
D是AXT三者作矩陣運算後的8*8矩陣
D也是用double的形態儲存
(3)去網路找 YUV的 quatization table
quatization table也是8*8的矩陣
把經過DCT後的數值除以quatization table上的數值
除以quatization後的數值先做四捨五入
接著以 int的型式儲存起來
(4)把步驟(3)儲存的數值再乘上quatization table的數值
再以double的形態把乘完quatization的數值儲存起來
這時候會發現數值和一開始經過DCT後的數值有稍微的不同
ex: 經過DCT後是527.89 , 除以quatization 16 再四捨五入後
會以33的數值存起來 , 再乘回quatization 16 會變成528
雖然會有些微的不同 但是誤差都不會太大
(5)利用 X=(T)(D)(A) 來作IDCT
A是步驟(1)產生的DCT矩陣
T是A矩陣的轉置矩陣
D是步驟(4)儲存的8*8矩陣
X是TDA三者作矩陣運算得到的8*8矩陣
要去判斷X中的每一點的數值
如果數值>255, 要讓它等於255
如果數值<0 30="="="">RGB 的公式去計算
如果轉換後的數值>255, 要讓它等於255
如果轉換後的數值<0 ,要讓它等於0
這邊是練習對MB 和 frame的位置概念
參考圖片 , 整張圖是352*288, MB是16*16 (圖中紅色方塊)
txt檔中是把每個MB中16的點 由左至右 由上到下寫入
一個MB寫完在換下一個 , MB也是由左至右 由上到下
frame是一個點一個點讀取 由左至右 由上到下 (圖中紫色方塊)
所以讀出txt檔每一個數值, 都要放回它在圖片的原本位置
步驟2是把圖片一個點一個點的讀入,然後儲存起來
最後再比較這兩個種數值是否有一致
== 2009.12.10===
目前已經把上次提的數值抓出
除了bitrate, 其他數值都以binary型式寫入檔案
1. 每個16*16 (MB) 的數值
圖片大小352*288 , 每16*16切成一塊
把16*16裡每點的pixel數值寫入檔案
2. 每個MB作完intra prediction的different值
intra prediction 分成 4*4和 16*16 兩種
(1) 4*4有9種mode , 每一種mode都會算出一個different值
先用一個陣列暫存每種mode算出來的different值
接著計算每種mode的cost大小, 找出一個最好的mode
這邊也會有個變數去記錄哪個mode是cost最小的
最後把此種mode的different值存進陣列(a4)
以4*4 去算different值 , 但最後要的是16*16
所以每次算完的4*4 要按著順序存進陣列(a4)
(2)16*16則有4種mode , 作法同上
差別在於 這邊是用16*16去算different值
只要把最好mode的different值存進陣列(a16)即可
作完上述兩點 , 每個MB會有 4*4 和 16*16算完的最佳解
會從中選一個來當作這個MB使用的different值
所以最後選出的different值才是要寫入檔案的
3. 每個MB作完 DCT+ quantization 後的數值
程式作完 DCT+ quantization的值存在 nMBQuant_Y變數裡
而且大小也是宣告成 16*16
只要將 此變數中 256個數值 寫入檔案即可
有記錄 Frame_I DCT+ quantization 後的數值
以及 Frame_P DCT+ quantization 後的數值
4. 得到每個MB需要的bits數量
此數值存在nRDBitRate變數裡
只要將此變數的值寫入檔案即可
一樣要記錄 Frame_I 和 Frame_P的BitRate
== 2009.11.18 ===
已經跟小新學長拿了程式
為了達成了解基本的H.264運作流程
計畫先取出下列幾個數值:
1.抓出MB pixel值
2.抓出MB pixel值 做過 Prediction(inter or intra)
3.抓出MB 4x4 DCT值
4.抓出MB 4x4 DCT值做過 quantization
5.得到MB壓縮所需要的bits數量
把這五個項目的數值取出來,分別存成一個新檔
這些檔案裡面的數值是後續步驟會使用到的
存檔的類型沒有限制 , 我想說把每項的數據存成txt檔
就從第一項開始作起 , 現在剛看程式 大略知道第一項要的數值在哪
這邊會再問一下學長 , 希望下禮拜可以抓出第一項的數值
2010年12月1日 星期三
SCREAM Processor-Cluster Platform Simulator - 威佐
-------- 2010 . 12. 01 ----------
目前模擬器已經開始使用 & 測試,
雖然不大穩定,但可以邊使用邊 debug。
昨天仕偉學長寫了一個 bubble sort 的程式,
連線遇到了一點小問題,不過我用了些方法先解決(之後會有更好的作法),所以程式有順利上傳執行。
接著就是在平台上加些功能,目前會先加的包括,
1.傳輸時 broadcast 的功能。
2.使用者端可以自行撰寫一支程式,接收平台傳來的資料,以便做應用。
3.Report,回報傳輸時間,以及每個component在core上執行時間等資訊。
因為使用者的需求不同,所以如果使用有什麼功能需要加,希望大家告訴我,我可以補上。
另外可能會遇到的問題就是使用者 resource 的釋放問題,
之前宜豊學長有提出,但我還沒找到適當的 solution。
下一步會開始進行的是容錯機制的設計。
如果順利的話,希望可以在寒假時將模擬器 porting 到板子上。
接著是開發者與前四位下載使用者的合影留念
目前模擬器已經開始使用 & 測試,
雖然不大穩定,但可以邊使用邊 debug。
昨天仕偉學長寫了一個 bubble sort 的程式,
連線遇到了一點小問題,不過我用了些方法先解決(之後會有更好的作法),所以程式有順利上傳執行。
接著就是在平台上加些功能,目前會先加的包括,
1.傳輸時 broadcast 的功能。
2.使用者端可以自行撰寫一支程式,接收平台傳來的資料,以便做應用。
3.Report,回報傳輸時間,以及每個component在core上執行時間等資訊。
因為使用者的需求不同,所以如果使用有什麼功能需要加,希望大家告訴我,我可以補上。
另外可能會遇到的問題就是使用者 resource 的釋放問題,
之前宜豊學長有提出,但我還沒找到適當的 solution。
下一步會開始進行的是容錯機制的設計。
如果順利的話,希望可以在寒假時將模擬器 porting 到板子上。
接著是開發者與前四位下載使用者的合影留念
2010年10月13日 星期三
2010年9月6日 星期一
2010年8月27日 星期五
2010 SCREAM Lab Summer Training Courses
今年規畫的比較晚,大概是因為我生了一場病,之後也比較疏懶一點,不過這傳統還是不希望斷掉。今年的訓練課程偏重實際,但是多增加一點練習,請講師多費心,下學期的多核心課程裡,我希望是這些課程裡部分的延續。
9/6 AM: Verilog 講師: 哲榮
9/6 PM: Verilog LAB and ModelSim 講師: 哲榮
9/7 AM: SMIMS FPGA SDK and FPGA Lab 講師: 巴菲特
9/7 PM: SCREAM Lab Multicore Platform/Emulator Programming Front End 講師: 威佐
9/8 AM: Android/QEMU/Cracking HTC Desire 講師: 塞公; SLIM/aSLIM programming 講師: 易聰
9/8 PM: SLIM/aSLIM Lab 講師: 塞公
9/9 AM: SMIMS Android/QEMU/FPGA 講師:君宇
9/9 PM: SMIMS Android/QEMU/FPGA Lab 講師:格銘
9/10 AM: SystemC/OpenESL/Eclipse 講師: 威佐
9/10 PM: SystemC/OpenESL/Eclipse Lab 講師: ruru
請Lab的講師出Lab所需的練習題目並提供解答,請Senior學長協助Junior學弟製作課程投影片。
請在9/5以前上傳投影片。投影片請各自開主題,並註明年分,作者,以及分類。並在串裡附上摘要。
標籤:
Android,
Courses,
ESL,
ESL Design Flow,
FPGA,
OpenESL,
Programming,
SCREAMLab. 活動預告與紀實,
SLIM,
Tool Chain
2010年8月21日 星期六
GCC Bug
今天遇到一個Bug, GCC有最佳化, 在x86上執行.
double f(double z)
{
return z;
}
void foo(double fraction)
{
double z = fraction * 20.0;
int t1 = z;
int t2 = f(z);
printf("t1=%d, t2=%d\n", t1, t2);
}
void main()
{
foo(6.0/20.0);
}
結果 t1 是5, t2是6
詳細的原因我沒去追, 不過compile的時後多加個flag就解決了
-ffloat-store
double f(double z)
{
return z;
}
void foo(double fraction)
{
double z = fraction * 20.0;
int t1 = z;
int t2 = f(z);
printf("t1=%d, t2=%d\n", t1, t2);
}
void main()
{
foo(6.0/20.0);
}
結果 t1 是5, t2是6
詳細的原因我沒去追, 不過compile的時後多加個flag就解決了
-ffloat-store
2010年8月17日 星期二
lab旅遊-宜蘭行程
第一天:
坐車到礁溪-五琪峰瀑布(步行30~40分)-跑馬古道-礁溪買鴨賞(巴菲特)-川湯春天養生館(溫泉魚 spa 滑水道 2小時)
-正常鮮小籠湯包(宜蘭)-宜蘭逛東門夜市-看夜景(橘子咖灰)-到羅東民宿check in-休息[住羅東]
橘子咖啡
03-9220171
地址:宜蘭縣員山鄉枕山一村19號3樓
第二天:
開車到南澳火車站(9點集合)-(9.30)開始溯溪-(中間午餐)-4點結束
-南方澳吃海產-羅東逛羅東夜市-羅東運動公園-休息
第三天:
外澳衝浪-樂屋日本料理-芋冰-附近的街道?買名產(諾貝爾奶凍捲)-宜蘭還車回家-坐車回家
聯發芋冰老店
地址: 宜蘭縣頭城鎮青雲路三段190號
樂屋日本料理
03-9777525
旅遊每人初估:
1.車錢: 350*2 + 150*2 + 950 = 1950
(台南-台北) 噶瑪蘭號(台北-宜蘭) 宜蘭租車 油錢
((2500+2200)*2+1000)/11
2.住宿: (950*10+1300)/11 = 990
3.玩樂: 220 + 500 + 1600 = 2320
川湯 衝浪 溯溪
4.保險合菜: 40 + 500 = 540
保險 合菜(海產)
合計 1950+990+2320+540 = 5800
坐車到礁溪-五琪峰瀑布(步行30~40分)-跑馬古道-礁溪買鴨賞(巴菲特)-川湯春天養生館(溫泉魚 spa 滑水道 2小時)
-正常鮮小籠湯包(宜蘭)-宜蘭逛東門夜市-看夜景(橘子咖灰)-到羅東民宿check in-休息[住羅東]
橘子咖啡
03-9220171
地址:宜蘭縣員山鄉枕山一村19號3樓
第二天:
開車到南澳火車站(9點集合)-(9.30)開始溯溪-(中間午餐)-4點結束
-南方澳吃海產-羅東逛羅東夜市-羅東運動公園-休息
第三天:
外澳衝浪-樂屋日本料理-芋冰-附近的街道?買名產(諾貝爾奶凍捲)-宜蘭還車回家-坐車回家
聯發芋冰老店
地址: 宜蘭縣頭城鎮青雲路三段190號
樂屋日本料理
03-9777525
旅遊每人初估:
1.車錢: 350*2 + 150*2 + 950 = 1950
(台南-台北) 噶瑪蘭號(台北-宜蘭) 宜蘭租車 油錢
((2500+2200)*2+1000)/11
2.住宿: (950*10+1300)/11 = 990
3.玩樂: 220 + 500 + 1600 = 2320
川湯 衝浪 溯溪
4.保險合菜: 40 + 500 = 540
保險 合菜(海產)
合計 1950+990+2320+540 = 5800
訂閱:
文章 (Atom)