- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# block_match.cpp

    00001 /* ***** BEGIN LICENSE BLOCK *****
    00002 *
    00003 * $Id: block_match.cpp,v 1.3 2005/01/30 05:11:42 gabest Exp $ $Name:  $
    00004 *
    00005 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
    00006 *
    00007 * The contents of this file are subject to the Mozilla Public License
    00008 * Version 1.1 (the "License"); you may not use this file except in compliance
    00009 * with the License. You may obtain a copy of the License at
    00010 * http://www.mozilla.org/MPL/
    00011 *
    00012 * Software distributed under the License is distributed on an "AS IS" basis,
    00013 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
    00014 * the specific language governing rights and limitations under the License.
    00015 *
    00016 * The Original Code is BBC Research and Development code.
    00017 *
    00018 * The Initial Developer of the Original Code is the British Broadcasting
    00019 * Corporation.
    00020 * Portions created by the Initial Developer are Copyright (C) 2004.
    00021 * All Rights Reserved.
    00022 *
    00023 * Contributor(s): Thomas Davies (Original Author)
    00024 *
    00025 * Alternatively, the contents of this file may be used under the terms of
    00026 * the GNU General Public License Version 2 (the "GPL"), or the GNU Lesser
    00027 * Public License Version 2.1 (the "LGPL"), in which case the provisions of
    00028 * the GPL or the LGPL are applicable instead of those above. If you wish to
    00029 * allow use of your version of this file only under the terms of the either
    00030 * the GPL or LGPL and not to allow others to use your version of this file
    00031 * under the MPL, indicate your decision by deleting the provisions above
    00032 * and replace them with the notice and other provisions required by the GPL
    00033 * or LGPL. If you do not delete the provisions above, a recipient may use
    00034 * your version of this file under the terms of any one of the MPL, the GPL
    00035 * or the LGPL.
    00036 * ***** END LICENSE BLOCK ***** */
    00037
    00038 #include <libdirac_motionest/block_match.h>
    00039 #include <libdirac_motionest/me_utils.h>
    00040 using namespace dirac;
    00041
    00042 #include <cmath>
    00043 using std::vector;
    00044
    00045 namespace dirac
    00046 {
    00047
    00048 ValueType GetVar( const MVector& predmv , const MVector& mv )
    00049 {
    00050     MVector diff;
    00051     diff.x = mv.x-predmv.x;
    00052     diff.y = mv.y-predmv.y;
    00053
    00054     return std::max( Norm1( diff ) , 48 );
    00055 }
    00056
    00057 ValueType GetVar( const std::vector<MVector>& pred_list , const MVector& mv)
    00058 {
    00059     ValueType sum=0;
    00060     MVector diff;
    00061     for (size_t i=0 ; i<pred_list.size() ; ++i)
    00062     {
    00063         diff.x = mv.x - pred_list[i].x;
    00064         diff.y = mv.y - pred_list[i].y;
    00065         sum += Norm1( diff );
    00066     }
    00067
    00068     return sum;
    00069 }
    00070
    00071 void AddNewVlist( CandidateList& vect_list, const MVector& mv, const int xr , const int yr , const int step )
    00072 {
    00073       //Creates a new motion vector list in a square region around mv
    00074
    00075     vector<MVector> tmp_list;
    00076     vect_list.push_back(tmp_list);
    00077     int list_num=vect_list.size()-1;
    00078
    00079     MVector tmp_mv( mv );
    00080     AddVect(vect_list , tmp_mv , list_num );
    00081
    00082     for ( int i=1 ; i<=xr ; ++i )
    00083     {
    00084         tmp_mv.x = mv.x + i*step;
    00085         AddVect( vect_list , tmp_mv , list_num );
    00086
    00087         tmp_mv.x = mv.x - i*step;
    00088         AddVect( vect_list , tmp_mv , list_num );
    00089     }
    00090
    00091     for ( int j=1 ; j<=yr ; ++j)
    00092     {
    00093         for ( int i=-xr ; i<=xr ; ++i)
    00094         {
    00095             tmp_mv.x = mv.x + i*step;
    00096             tmp_mv.y = mv.y + j*step;
    00097             AddVect(vect_list,tmp_mv,list_num);
    00098
    00099             tmp_mv.y = mv.y -j*step;
    00100             AddVect(vect_list,tmp_mv,list_num);
    00101
    00102         }// i
    00103     }// j
    00104
    00105     // If we've not managed to add any element to the list
    00106     // remove the list so we don't ever have to check its size
    00107     if ( vect_list[list_num].size() == 0 )
    00108         vect_list.erase( vect_list.begin() + list_num );
    00109 }
    00110
    00111 void AddNewVlist( CandidateList& vect_list , const MVector& mv , const int xr , const int yr)
    00112 {
    00113       // Creates a new motion vector list in a square region around mv
    00114
    00115     vector<MVector> tmp_list;
    00116     vect_list.push_back(tmp_list);
    00117     int list_num=vect_list.size()-1;
    00118
    00119     MVector tmp_mv(mv);
    00120     AddVect(vect_list,tmp_mv,list_num);
    00121
    00122     for ( int i=1 ; i<=xr ; ++i)
    00123     {
    00124         tmp_mv.x = mv.x + i;
    00125         AddVect( vect_list , tmp_mv , list_num );
    00126
    00127         tmp_mv.x = mv.x - i;
    00128         AddVect( vect_list , tmp_mv , list_num );
    00129     }
    00130
    00131     for ( int j=1 ; j<=yr ; ++j)
    00132     {
    00133         for ( int i=-xr ; i<=xr ; ++i)
    00134         {
    00135             tmp_mv.x = mv.x + i;
    00136             tmp_mv.y = mv.y + j;
    00137             AddVect( vect_list , tmp_mv , list_num );
    00138
    00139             tmp_mv.y = mv.y-j;
    00140             AddVect( vect_list , tmp_mv , list_num );
    00141         }
    00142     }
    00143
    00144     // If we've not managed to add any element to the list
    00145     // remove the list so we don't ever have to check its size
    00146     if ( vect_list[list_num].size() == 0 )
    00147         vect_list.erase( vect_list.begin() + list_num );
    00148 }
    00149
    00150 void AddNewVlistD( CandidateList& vect_list , const MVector& mv , const int xr , const int yr )
    00151 {
    00152       //As above, but using a diamond pattern
    00153
    00154     vector<MVector> tmp_list;
    00155     vect_list.push_back( tmp_list );
    00156
    00157     int list_num=vect_list.size()-1;
    00158     int xlim;
    00159
    00160     MVector tmp_mv( mv );
    00161     AddVect( vect_list , tmp_mv , list_num );
    00162
    00163     for ( int i=1 ; i<=xr ; ++i)
    00164     {
    00165         tmp_mv.x = mv.x + i;
    00166         AddVect( vect_list , tmp_mv , list_num );
    00167
    00168         tmp_mv.x = mv.x - i;
    00169         AddVect( vect_list , tmp_mv , list_num );
    00170     }
    00171
    00172     for ( int j=1 ; j<=yr ; ++j)
    00173     {
    00174         xlim = xr * (yr-std::abs(j)) / yr;
    00175         for ( int i=-xlim ; i<=xlim ; ++i)
    00176         {
    00177             tmp_mv.x = mv.x + i;
    00178             tmp_mv.y = mv.y + j;
    00179             AddVect( vect_list , tmp_mv , list_num );
    00180
    00181             tmp_mv.y = mv.y - j;
    00182             AddVect( vect_list , tmp_mv , list_num );
    00183         }
    00184     }
    00185
    00186     // If we've not managed to add any element to the list
    00187     // remove the list so we don't ever have to check its size
    00188     if ( vect_list[list_num].size() == 0 )
    00189         vect_list.erase( vect_list.begin() + list_num );
    00190 }
    00191
    00192 void AddVect(CandidateList& vect_list,const MVector& mv,int list_num)
    00193 {
    00194
    00195     bool is_in_list=false;
    00196
    00197     size_t lnum=0;
    00198     size_t i;
    00199
    00200     while( !is_in_list && lnum<vect_list.size() )
    00201     {
    00202         i=0;
    00203         while( !is_in_list && i<vect_list[lnum].size())
    00204         {
    00205             if ( vect_list[lnum][i].x == mv.x && vect_list[lnum][i].y == mv.y )
    00206                 is_in_list=true;
    00207             ++i;
    00208         }
    00209         ++lnum;
    00210     }
    00211
    00212     if ( !is_in_list )
    00213         vect_list[list_num].push_back(mv);
    00214
    00215 }
    00216
    00217 BlockMatcher::BlockMatcher( const PicArray& pic_data , const PicArray& ref_data , const OLBParams& bparams ,
    00218                             const MvArray& mv_array , const TwoDArray< MvCostData >& cost_array):
    00219     m_pic_data(pic_data),
    00220     m_ref_data(ref_data),
    00221     m_mv_array(mv_array),
    00222     m_cost_array(cost_array),
    00223     m_simplediff( ref_data , pic_data ), //NB: ORDER!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    00224     m_checkdiff( ref_data , pic_data ),
    00225     m_simplediffup( ref_data , pic_data ),
    00226     m_checkdiffup( ref_data , pic_data ),
    00227     m_bparams(bparams)
    00228 {}
    00229
    00230 void BlockMatcher::FindBestMatch(int xpos , int ypos ,
    00231                                  const CandidateList& cand_list,
    00232                                  const MVector& mv_prediction,
    00233                                  float lambda)
    00234 {
    00235     BlockDiffParams dparams;
    00236     dparams.SetBlockLimits( m_bparams , m_pic_data , xpos , ypos);
    00237     lambda /= m_bparams.Xblen()*m_bparams.Yblen();
    00238     lambda *= dparams.Xl()*dparams.Yl();
    00239
    00240     // Pointer to either a simple block diff object, or a bounds-checking one
    00241     BlockDiff* mydiff;
    00242
    00243        //now test against the offsets in the MV list to get the lowest cost//
    00245
    00246     // Numbers of the lists to do more searching in
    00247     vector<int> list_nums;
    00248
    00249     // Costs of the initial vectors in each list
    00250     OneDArray<float> list_costs( cand_list.size() );
    00251
    00252     // The minimum cost so far
    00253     float min_cost;
    00254
    00255     // First test the first in each of the lists to choose which lists to pursue
    00256
    00257     MvCostData best_costs;
    00258     // Initialise so that we choose a valid vector to start with!
    00259     best_costs.total=100000000.0f;
    00260     MVector best_mv( cand_list[0][0] );
    00261
    00262     MVector cand_mv;
    00263     MvCostData cand_costs;
    00264
    00265     for (size_t lnum=0 ; lnum<cand_list.size() ; ++lnum )
    00266     {
    00267
    00268         cand_mv = cand_list[lnum][0];
    00269         cand_costs.mvcost = GetVar( mv_prediction , cand_mv );
    00270
    00271         // See whether we need to do bounds checking or not
    00272         if (( dparams.Xp()+cand_mv.x )<0 || ( dparams.Xp()+dparams.Xl()+cand_mv.x) >= m_ref_data.LengthX() ||
    00273             (dparams.Yp()+cand_mv.y)<0 || (dparams.Yp()+dparams.Yl()+cand_mv.y) >= m_ref_data.LengthY() )
    00274             mydiff = &m_checkdiff;
    00275         else
    00276             mydiff = &m_simplediff;
    00277
    00278         cand_costs.SAD = mydiff->Diff( dparams , cand_mv );
    00279         cand_costs.SetTotal( lambda );
    00280
    00281         if ( cand_costs.total < best_costs.total)
    00282         {
    00283             best_costs = cand_costs;
    00284             best_mv = cand_mv ;
    00285
    00286         }
    00287
    00288         list_costs[lnum] = cand_costs.total;
    00289
    00290     }// lnum
    00291
    00292
    00293     // Select which lists we're going to use //
    00295
    00296     min_cost = list_costs[0];
    00297
    00298     for ( int lnum=1 ; lnum<list_costs.Length() ; ++lnum)
    00299     {
    00300         if ( list_costs[lnum]<min_cost )
    00301             min_cost = list_costs[lnum];
    00302     }// lnum
    00303
    00304     for ( int lnum=0 ; lnum<list_costs.Length() ; ++lnum)
    00305     {
    00306         // Only do lists whose 1st element isn't too far off best
    00307         if ( list_costs[lnum] < 1.5*min_cost ) // (value of 1.5 TBD)
    00308             list_nums.push_back( lnum );
    00309     }// lnum
    00310
    00311
    00312     // Ok, now we know which lists to pursue. Just go through all of them //
    00314     int list_num;
    00315
    00316     for ( size_t num=0 ; num<list_nums.size() ; ++num)
    00317     {
    00318         list_num = list_nums[num];
    00319
    00320         for (size_t i=1 ; i<cand_list[list_num].size() ; ++i)
    00321         {//start at 1 since did 0 above
    00322
    00323             cand_mv = cand_list[list_num][i];
    00324             cand_costs.mvcost =  GetVar( mv_prediction , cand_mv);
    00325
    00326             if ((dparams.Xp()+cand_mv.x)<0 || (dparams.Xp()+dparams.Xl()+cand_mv.x) > m_ref_data.LengthX() ||
    00327                 (dparams.Yp()+cand_mv.y)<0 || (dparams.Yp()+dparams.Yl()+cand_mv.y) > m_ref_data.LengthY() )
    00328                 mydiff = &m_checkdiff;
    00329             else
    00330                 mydiff = &m_simplediff;
    00331
    00332             cand_costs.SAD = mydiff->Diff( dparams , cand_mv );
    00333             cand_costs.SetTotal( lambda );
    00334
    00335             if ( cand_costs.total < best_costs.total)
    00336             {
    00337                 best_costs = cand_costs;
    00338                 best_mv = cand_mv;
    00339
    00340             }
    00341         }// i
    00342     }// num
    00343
    00344     // Write the results in the arrays //
    00346
    00347     m_mv_array[ypos][xpos] = best_mv;
    00348     m_cost_array[ypos][xpos] = best_costs;
    00349 }
    00350
    00351
    00352
    00353
    00354 void BlockMatcher::FindBestMatchSubp(int xpos, int ypos,
    00355                                       const CandidateList& cand_list,
    00356                                       const MVector& mv_prediction,
    00357                                       float lambda)
    00358 {
    00359
    00360     BlockDiffParams dparams;
    00361     dparams.SetBlockLimits( m_bparams , m_pic_data , xpos , ypos);
    00362
    00363     // Pointer to either a simple block diff object, or a bounds-checking one
    00364     BlockDiff* mydiff;
    00365
    00366        //now test against the offsets in the MV list to get the lowest cost//
    00368
    00369     // Numbers of the lists to do more searching in
    00370     vector<int> list_nums;
    00371
    00372     // Costs of the initial vectors in each list
    00373     OneDArray<float> list_costs( cand_list.size() );
    00374
    00375     // The minimum cost so far
    00376     float min_cost;
    00377
    00378     // First test the first in each of the lists to choose which lists to pursue
    00379     MvCostData best_costs( m_cost_array[ypos][xpos] );
    00380     MVector best_mv( m_mv_array[ypos][xpos] );
    00381
    00382     MvCostData cand_costs;
    00383     MVector cand_mv;
    00384
    00385     for (size_t list_num=0 ; list_num<cand_list.size() ; ++list_num )
    00386     {
    00387
    00388         cand_mv = cand_list[list_num][0];
    00389         cand_costs.mvcost = GetVar( mv_prediction , cand_mv );
    00390
    00391         // See whether we need to do bounds checking or not
    00392         if (   (( dparams.Xp()<<1 )+(cand_mv.x>>2))<0
    00393             || ((( dparams.Xp()+dparams.Xl() )<<1)+(cand_mv.x>>2)) >= m_ref_data.LengthX()
    00394             || (( dparams.Yp()<<1)+(cand_mv.y>>2))<0
    00395             || (((dparams.Yp()+dparams.Yl())<<1)+(cand_mv.y>>2)) >= m_ref_data.LengthY() )
    00396             mydiff = &m_checkdiffup;
    00397         else
    00398             mydiff = &m_simplediffup;
    00399
    00400         cand_costs.SAD = mydiff->Diff( dparams , cand_mv );
    00401         cand_costs.SetTotal( lambda );
    00402
    00403        if (cand_costs.total< best_costs.total)
    00404         {
    00405             best_costs = cand_costs;
    00406             best_mv = cand_mv;
    00407         }
    00408
    00409         list_costs[list_num] = cand_costs.total;
    00410     }// list_num
    00411
    00412
    00413     // Select which lists we're going to use //
    00415
    00416     min_cost = list_costs[0];
    00417
    00418     for ( int lnum=1 ; lnum<list_costs.Length() ; ++lnum)
    00419     {
    00420         if ( list_costs[lnum]<min_cost )
    00421             min_cost = list_costs[lnum];
    00422     }// lnum
    00423
    00424     for ( int lnum=0 ; lnum<list_costs.Length() ; ++lnum )
    00425     {
    00426         // Only do lists whose 1st element isn't too far off best
    00427         if ( list_costs[lnum] < 1.5*min_cost ) // (value of 1.5 TBD)
    00428             list_nums.push_back( lnum );
    00429     }// lnum
    00430
    00431     // Ok, now we know which lists to pursue. Just go through all of them //
    00433     int list_num;
    00434
    00435     for ( size_t num=0 ; num<list_nums.size() ; ++num)
    00436     {
    00437         list_num = list_nums[num];
    00438
    00439         for (size_t i=1 ; i<cand_list[list_num].size() ; ++i)
    00440         {//start at 1 since did 0 above
    00441
    00442             cand_mv = cand_list[list_num][i];
    00443             cand_costs.mvcost = GetVar( mv_prediction , cand_mv );
    00444
    00445             if (   (( dparams.Xp()<<1 )+( cand_mv.x>>2 ))<0
    00446                 || ((( dparams.Xp()+dparams.Xl() )<<1)+( cand_mv.x>>2 )) >= m_ref_data.LengthX()
    00447                 || (( dparams.Yp()<<1 )+( cand_mv.y>>2 ))<0
    00448                 || ((( dparams.Yp()+dparams.Yl() )<<1)+(cand_mv.y>>2)) >= m_ref_data.LengthY() )
    00449                  mydiff = &m_checkdiffup;
    00450             else
    00451                 mydiff = &m_simplediffup;
    00452
    00453             cand_costs.SAD = mydiff->Diff( dparams , cand_mv );
    00454             cand_costs.SetTotal( lambda );
    00455
    00456             if (cand_costs.total< best_costs.total)
    00457             {
    00458                 best_costs = cand_costs;
    00459                 best_mv = cand_mv;
    00460             }
    00461
    00462         }// i
    00463     }// num
    00464
    00465     // Write the results in the arrays //
    00467
    00468      m_mv_array[ypos][xpos] = best_mv;
    00469      m_cost_array[ypos][xpos] = best_costs;
    00470
    00471 }
    00472 } // namespace dirac