21 |
* along with this program ; if not, write to the Free Software |
* along with this program ; if not, write to the Free Software |
22 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
23 |
* |
* |
24 |
* $Id: mbtransquant.c,v 1.21.2.19 2003-11-23 17:01:08 edgomez Exp $ |
* $Id: mbtransquant.c,v 1.21.2.20 2003-11-24 22:06:19 edgomez Exp $ |
25 |
* |
* |
26 |
****************************************************************************/ |
****************************************************************************/ |
27 |
|
|
647 |
* IEEE Transactions on Image Processing, Vol.9, No.8, Aug. 2000. |
* IEEE Transactions on Image Processing, Vol.9, No.8, Aug. 2000. |
648 |
* |
* |
649 |
* we are at stake with a simplified Bellmand-Ford / Dijkstra Single |
* we are at stake with a simplified Bellmand-Ford / Dijkstra Single |
650 |
* Source Shorted Path algo. But due to the underlying graph structure |
* Source Shortest Path algo. But due to the underlying graph structure |
651 |
* ("Trellis"), it can be turned into a dynamic programming algo, |
* ("Trellis"), it can be turned into a dynamic programming algo, |
652 |
* partially saving the explicit graph's nodes representation. And |
* partially saving the explicit graph's nodes representation. And |
653 |
* without using a heap, since the open frontier of the DAG is always |
* without using a heap, since the open frontier of the DAG is always |
654 |
* known, and of fixed sized. |
* known, and of fixed size. |
655 |
*--------------------------------------------------------------------------*/ |
*--------------------------------------------------------------------------*/ |
656 |
|
|
657 |
|
|
799 |
int Non_Zero) |
int Non_Zero) |
800 |
{ |
{ |
801 |
|
|
802 |
/* |
/* Note: We should search last non-zero coeffs on *real* DCT input coeffs |
803 |
* Note: We should search last non-zero coeffs on *real* DCT input coeffs (In[]), |
* (In[]), not quantized one (Out[]). However, it only improves the result |
804 |
* not quantized one (Out[]). However, it only improves the result *very* |
* *very* slightly (~0.01dB), whereas speed drops to crawling level :) |
805 |
* slightly (~0.01dB), whereas speed drops to crawling level :) |
* Well, actually, taking 1 more coeff past Non_Zero into account sometimes |
806 |
* Well, actually, taking 1 more coeff past Non_Zero into account sometimes helps. |
* helps. */ |
|
*/ |
|
807 |
typedef struct { int16_t Run, Level; } NODE; |
typedef struct { int16_t Run, Level; } NODE; |
808 |
|
|
809 |
NODE Nodes[65], Last; |
NODE Nodes[65], Last; |
810 |
uint32_t Run_Costs0[64+1]; |
uint32_t Run_Costs0[64+1]; |
811 |
uint32_t * const Run_Costs = Run_Costs0 + 1; |
uint32_t * const Run_Costs = Run_Costs0 + 1; |
812 |
|
|
813 |
const int Lambda = Trellis_Lambda_Tabs[Q-1]; /* it's 1/lambda, actually */ |
/* it's 1/lambda, actually */ |
814 |
|
const int Lambda = Trellis_Lambda_Tabs[Q-1]; |
815 |
|
|
816 |
int Run_Start = -1; |
int Run_Start = -1; |
817 |
uint32_t Min_Cost = 2<<TL_SHIFT; |
uint32_t Min_Cost = 2<<TL_SHIFT; |
820 |
uint32_t Last_Cost = 0; |
uint32_t Last_Cost = 0; |
821 |
|
|
822 |
int i, j, sum; |
int i, j, sum; |
823 |
Run_Costs[-1] = 2<<TL_SHIFT; /* source (w/ CBP penalty) */ |
|
824 |
|
/* source (w/ CBP penalty) */ |
825 |
|
Run_Costs[-1] = 2<<TL_SHIFT; |
826 |
|
|
827 |
Non_Zero = Find_Last(Out, Zigzag, Non_Zero); |
Non_Zero = Find_Last(Out, Zigzag, Non_Zero); |
828 |
if (Non_Zero<0) |
if (Non_Zero<0) |
862 |
const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<TL_SHIFT); |
const uint32_t Cost = Cost_Base + (Code_Len20[Run-1]<<TL_SHIFT); |
863 |
const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<TL_SHIFT); |
const uint32_t lCost = Cost_Base + (Code_Len24[Run-1]<<TL_SHIFT); |
864 |
|
|
865 |
/* |
/* TODO: what about tie-breaks? Should we favor short runs or |
|
* TODO: what about tie-breaks? Should we favor short runs or |
|
866 |
* long runs? Although the error is the same, it would not be |
* long runs? Although the error is the same, it would not be |
867 |
* spread the same way along high and low frequencies... |
* spread the same way along high and low frequencies... */ |
|
*/ |
|
868 |
|
|
869 |
/* (I'd say: favour short runs => hifreq errors (HVS) -- gruel ) */ |
/* Gruel: I'd say, favour short runs => hifreq errors (HVS) */ |
870 |
|
|
871 |
if (Cost<Best_Cost) { |
if (Cost<Best_Cost) { |
872 |
Best_Cost = Cost; |
Best_Cost = Cost; |
881 |
} |
} |
882 |
if (Last_Node==i) |
if (Last_Node==i) |
883 |
Last.Level = Nodes[i].Level; |
Last.Level = Nodes[i].Level; |
884 |
} else { /* "big" levels */ |
} else if (51U>(uint32_t)(Level1+25)) { |
885 |
|
/* "big" levels (not less than ESC3, though) */ |
886 |
const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last; |
const uint8_t *Tbl_L1, *Tbl_L2, *Tbl_L1_Last, *Tbl_L2_Last; |
887 |
int Level2; |
int Level2; |
888 |
int dQ1, dQ2; |
int dQ1, dQ2; |
918 |
uint32_t Cost1, Cost2; |
uint32_t Cost1, Cost2; |
919 |
int bLevel; |
int bLevel; |
920 |
|
|
921 |
/* |
/* for sub-optimal (but slightly worth it, speed-wise) search, |
922 |
* for sub-optimal (but slightly worth it, speed-wise) search, uncomment the following: |
* uncomment the following: |
923 |
* if (Cost_Base>=Best_Cost) continue; |
* if (Cost_Base>=Best_Cost) continue; |
924 |
* (? doesn't seem to have any effect -- gruel ) |
* (? doesn't seem to have any effect -- gruel ) */ |
|
*/ |
|
925 |
|
|
926 |
Cost1 = Cost_Base + (Tbl_L1[Run-1]<<TL_SHIFT); |
Cost1 = Cost_Base + (Tbl_L1[Run-1]<<TL_SHIFT); |
927 |
Cost2 = Cost_Base + (Tbl_L2[Run-1]<<TL_SHIFT) + dDist21; |
Cost2 = Cost_Base + (Tbl_L2[Run-1]<<TL_SHIFT) + dDist21; |
956 |
Last_Node = i; |
Last_Node = i; |
957 |
} |
} |
958 |
} /* end of "for Run" */ |
} /* end of "for Run" */ |
959 |
|
} else { |
960 |
|
/* Very very high levels, with no chance of being optimizable |
961 |
|
* => Simply pick best Run. */ |
962 |
|
int Run; |
963 |
|
for(Run=i-Run_Start; Run>0; --Run) { |
964 |
|
/* 30 bits + no distortion */ |
965 |
|
const uint32_t Cost = (30<<TL_SHIFT) + Run_Costs[i-Run]; |
966 |
|
if (Cost<Best_Cost) { |
967 |
|
Best_Cost = Cost; |
968 |
|
Nodes[i].Run = Run; |
969 |
|
Nodes[i].Level = Level1; |
970 |
|
} |
971 |
|
|
972 |
|
if (Cost<Last_Cost) { |
973 |
|
Last_Cost = Cost; |
974 |
|
Last.Run = Run; |
975 |
|
Last.Level = Level1; |
976 |
|
Last_Node = i; |
977 |
|
} |
978 |
|
} |
979 |
} |
} |
980 |
|
|
981 |
|
|
982 |
Run_Costs[i] = Best_Cost; |
Run_Costs[i] = Best_Cost; |
983 |
|
|
984 |
if (Best_Cost < Min_Cost + Dist0) { |
if (Best_Cost < Min_Cost + Dist0) { |
985 |
Min_Cost = Best_Cost; |
Min_Cost = Best_Cost; |
986 |
Run_Start = i; |
Run_Start = i; |
987 |
} else { |
} else { |
988 |
/* |
/* as noticed by Michael Niedermayer (michaelni at gmx.at), |
989 |
* as noticed by Michael Niedermayer (michaelni at gmx.at), there's |
* there's a code shorter by 1 bit for a larger run (!), same |
990 |
* a code shorter by 1 bit for a larger run (!), same level. We give |
* level. We give it a chance by not moving the left barrier too |
991 |
* it a chance by not moving the left barrier too much. |
* much. */ |
|
*/ |
|
|
|
|
992 |
while( Run_Costs[Run_Start]>Min_Cost+(1<<TL_SHIFT) ) |
while( Run_Costs[Run_Start]>Min_Cost+(1<<TL_SHIFT) ) |
993 |
Run_Start++; |
Run_Start++; |
994 |
|
|
995 |
/* spread on preceding coeffs the cost incurred by skipping this one */ |
/* spread on preceding coeffs the cost incurred by skipping this |
996 |
|
* one */ |
997 |
for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0; |
for(j=Run_Start; j<i; ++j) Run_Costs[j] += Dist0; |
998 |
Min_Cost += Dist0; |
Min_Cost += Dist0; |
999 |
} |
} |
1000 |
} |
} |
1001 |
|
|
1002 |
/* It seems trellis doesn't give good results... just compute the Out sum and |
/* It seems trellis doesn't give good results... just compute the Out sum |
1003 |
* quit (even if we did not modify it, upperlayer relies on this data) */ |
* and quit */ |
1004 |
if (Last_Node<0) |
if (Last_Node<0) |
1005 |
return Compute_Sum(Out, Non_Zero); |
return Compute_Sum(Out, Non_Zero); |
1006 |
|
|