- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# pixel_match.cpp

    00001 /* ***** BEGIN LICENSE BLOCK *****
    00002 *
    00003 * $Id: pixel_match.cpp,v 1.2 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 Copm_yright (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/pixel_match.h>
    00039 #include <libdirac_motionest/block_match.h>
    00040 #include <libdirac_common/motion.h>
    00041 #include <libdirac_common/frame_buffer.h>
    00042 #include <libdirac_motionest/downconvert.h>
    00043 #include <libdirac_motionest/me_mode_decn.h>
    00044 #include <libdirac_motionest/me_subpel.h>
    00045 using namespace dirac;
    00046
    00047 #include <cmath>
    00048 #include <vector>
    00049
    00050 using std::vector;
    00051 using std::log;
    00052
    00053 PixelMatcher::PixelMatcher( const EncoderParams& encp):
    00054     m_encparams(encp)
    00055 {}
    00056
    00057
    00058 void PixelMatcher::DoSearch(const FrameBuffer& my_buffer, int frame_num, MEData& me_data)
    00059 {
    00060
    00061      //does an initial search using hierarchical matching to get guide vectors
    00062
    00063     // Frame numbers of references
    00064     int ref1,ref2;
    00065
    00066     // Use the luminance only for motion estimating
    00067     const PicArray& pic_data = my_buffer.GetComponent( frame_num , Y_COMP );
    00068
    00069     const vector<int>& refs = my_buffer.GetFrame( frame_num ).GetFparams().Refs();
    00070     ref1 = refs[0];
    00071     if (refs.size()>1)
    00072         ref2 = refs[1];
    00073     else
    00074         ref2 = ref1;
    00075
    00076     // Obtain C++ references to the reference picture luma components
    00077     const PicArray& ref1_data = my_buffer.GetComponent(ref1 , Y_COMP);
    00078     const PicArray& ref2_data = my_buffer.GetComponent(ref2 , Y_COMP);
    00079
    00080     // Determine the frame sort - this affects the motion estimation Lagrangian parameter
    00081     m_fsort = my_buffer.GetFrame(frame_num).GetFparams().FSort();
    00082
    00083     // Set the number of downconversion levels - not too many or we run out of picture!
    00084     m_depth = ( int) std::min( log(((double) pic_data.LengthX())/12.0)/log(2.0) ,
    00085                              log(((double) pic_data.LengthY())/12.0)/log(2.0) );
    00086
    00087     // These arrays will contain the downconverted picture and MvData hierarchy
    00088     OneDArray<PicArray*> ref1_down( Range( 1 , m_depth ) );
    00089     OneDArray<PicArray*> ref2_down( Range( 1 , m_depth ) );
    00090     OneDArray<PicArray*> pic_down( Range( 1 , m_depth ) );
    00091     OneDArray<MEData*> me_data_set( Range( 1 , m_depth ) );
    00092
    00093     // Populate the hierarchies
    00094     MakePicHierarchy( pic_data , pic_down );
    00095     MakePicHierarchy( ref1_data , ref1_down );
    00096     if (ref1 != ref2)
    00097         MakePicHierarchy( ref2_data , ref2_down );
    00098
    00099     MakeMEDataHierarchy( pic_down , me_data_set );
    00100
    00101      // Now do the work! //
    00103
    00104     // Start with motion estimating at the very lowest level
    00105     m_level = m_depth;
    00106
    00107     MatchPic( *(pic_down[m_depth]) , *(ref1_down[m_depth]) , *(me_data_set[m_depth]) ,
    00108                                      *(me_data_set[m_depth]) , 1 );
    00109     if ( ref1 != ref2 )
    00110         MatchPic( *(pic_down[m_depth]) , *(ref2_down[m_depth]) , *(me_data_set[m_depth]) ,
    00111                                          *(me_data_set[m_depth]) , 2 );
    00112
    00113      // Do the intervening levels - here we can have a genuine set of guide vectors
    00114     for ( m_level=m_depth-1 ; m_level>=1 ; --m_level )
    00115     {
    00116         MatchPic( *(pic_down[m_level]) , *(ref1_down[m_level]) , *(me_data_set[m_level]) ,
    00117                                          *(me_data_set[m_level+1]) , 1 );
    00118         if (ref1!=ref2)
    00119             MatchPic( *(pic_down[m_level]) , *(ref2_down[m_level]) , *(me_data_set[m_level]) ,
    00120                                              *(me_data_set[m_level+1]) , 2 );
    00121
    00122     }// level
    00123
    00124     // Finally, do the top level, with the pictures themselves
    00125     m_level = 0;
    00126     MatchPic( pic_data , ref1_data, me_data , *(me_data_set[1]) , 1 );
    00127     if ( ref1 != ref2 )
    00128         MatchPic( pic_data , ref2_data , me_data , *(me_data_set[1]) , 2 );
    00129
    00130     // Now we're finished, tidy everything up ...
    00131     TidyPics( pic_down );
    00132     TidyPics( ref1_down );
    00133     if (ref1 != ref2)
    00134         TidyPics( ref2_down );
    00135     TidyMEData( me_data_set );
    00136
    00137 }
    00138
    00139 void PixelMatcher::MakePicHierarchy(const PicArray& data ,
    00140                                     OneDArray< PicArray* >& down_data)
    00141 {
    00142
    00143     DownConverter mydcon;
    00144
    00145     // Allocate
    00146     int scale_factor = 1;
    00147     for (int i=1 ; i<=m_depth;++i)
    00148     {
    00149         // Dimensions of pic_down[i] will be shrunk by a factor 2**i
    00150         scale_factor*=2;
    00151         down_data[i] = new PicArray( data.LengthY()/scale_factor , data.LengthX()/scale_factor);
    00152     }
    00153
    00154     //do all the downconversions
    00155     if (m_depth>0)
    00156     {
    00157         mydcon.DoDownConvert( data , *(down_data[1]) );
    00158
    00159         for (int i=1 ; i<m_depth ; ++i)
    00160             mydcon.DoDownConvert( *(down_data[i]) , *(down_data[i+1]) );
    00161
    00162     }
    00163 }
    00164
    00165 void PixelMatcher::MakeMEDataHierarchy(const OneDArray< PicArray*>& down_data,
    00166                                        OneDArray< MEData* >& me_data_set )
    00167 {
    00168
    00169     int xnumblocks , ynumblocks;
    00170     const OLBParams bparams = m_encparams.LumaBParams(2);
    00171
    00172     for (int i=1 ; i<=m_depth;++i)
    00173     {
    00174
    00175         xnumblocks = down_data[i]->LengthX()/bparams.Xbsep();
    00176         ynumblocks = down_data[i]->LengthY()/bparams.Ybsep();
    00177
    00178         if (( down_data[i]->LengthX() )%bparams.Xbsep() != 0)
    00179             xnumblocks++;
    00180
    00181         if (( down_data[i]->LengthY() )%bparams.Ybsep() != 0)
    00182             ynumblocks++;
    00183
    00184         me_data_set[i] = new MEData( 0 , 0 , xnumblocks , ynumblocks );
    00185     }// i
    00186
    00187 }
    00188
    00189 void PixelMatcher::TidyPics( OneDArray< PicArray*>& down_data )
    00190 {
    00191     for (int i=1 ; i <= m_depth ; ++i)
    00192     {
    00193         delete down_data[i];
    00194     }// i
    00195
    00196 }
    00197
    00198 void PixelMatcher::TidyMEData( OneDArray< MEData*>& me_data_set )
    00199 {
    00200     for (int i=1 ; i <= m_depth ; ++i)
    00201     {
    00202         delete me_data_set[i];
    00203     }// i
    00204
    00205 }
    00206
    00207
    00208
    00209 void PixelMatcher::MatchPic(const PicArray& pic_data , const PicArray& ref_data , MEData& me_data ,
    00210                             const MvData& guide_data, int ref_id)
    00211 {
    00212
    00213     // Initialisation //
    00215
    00216     // Set the search ranges according to the level
    00217     if ( m_level == m_depth )
    00218     {
    00219         m_xr = 5;
    00220         m_yr = 5;
    00221     }
    00222     else if ( m_level == m_depth-1 )
    00223     {
    00224         m_xr = 4;
    00225         m_yr = 4;
    00226     }
    00227     else
    00228     {
    00229         m_xr = 2;
    00230         m_yr = 2;
    00231     }
    00232
    00233     // Provide aliases for the appropriate motion vector data components
    00234
    00235     MvArray& mv_array = me_data.Vectors( ref_id );
    00236     const MvArray& guide_array = guide_data.Vectors( ref_id );
    00237     TwoDArray<MvCostData>& pred_costs = me_data.PredCosts( ref_id );
    00238
    00239     // Provide a block matching object to do the work
    00240     BlockMatcher my_bmatch( pic_data , ref_data , m_encparams.LumaBParams(2) , mv_array , pred_costs );
    00241
    00242     float loc_lambda( 0.0 );
    00243
    00244     // Do the work - loop over all the blocks, finding the best match //
    00246
    00247     /*
    00248     The idea is for each block construct a list of candidate vectors,which will
    00249     be tested. This list is actually a list of lists, implemented as a C++
    00250     vector of C++ vectors. This is so that FindBestMatch can shorten the
    00251     search process by looking at the beginning of each sublist and
    00252     discarding that sub-list if it's too far off.
    00253     */
    00254
    00255     // Make a zero-based list that is always used
    00256     m_cand_list.clear();
    00257     MVector zero_mv( 0 , 0 );
    00258     AddNewVlistD( m_cand_list , zero_mv , m_xr , m_yr);
    00259
    00260     // Now loop over the blocks and find the best matches.
    00261     // The loop is unrolled because predictions are different at picture edges.
    00262     // The purpose of the loop is to create appropriate candidate lists, and then
    00263     // call the DoBlock() function which does the actual work.
    00264
    00265     // First do TL corner
    00266
    00267     // Set the prediction as the zero vector
    00268     m_mv_prediction = zero_mv;
    00269
    00270     // m_lambda is the Lagrangian smoothing parameter set to zero to get us started
    00271     m_lambda = 0.0;
    00272     DoBlock(0, 0 , pred_costs , mv_array, guide_array , my_bmatch);
    00273
    00274     // The rest of the first row
    00275     // ( use reduced lambda here )
    00276     m_lambda = loc_lambda / float( m_encparams.YNumBlocks() );
    00277     for ( int xpos=1 ; xpos<mv_array.LengthX() ; ++xpos )
    00278     {
    00279         m_mv_prediction = mv_array[0][xpos-1];
    00280         DoBlock(xpos, 0 , pred_costs , mv_array, guide_array , my_bmatch);
    00281     }// xpos
    00282
    00283     // All the remaining rows except the last
    00284     for ( int ypos=1 ; ypos<mv_array.LengthY() ; ++ypos )
    00285     {
    00286
    00287         // The first element of each row
    00288         m_mv_prediction = mv_array[ypos-1][0];
    00289         m_lambda = loc_lambda/float(m_encparams.XNumBlocks());
    00290         DoBlock(0, ypos , pred_costs , mv_array, guide_array , my_bmatch );
    00291
    00292          // The middle elementes of each row
    00293         m_lambda = loc_lambda;
    00294         for ( int xpos=1 ; xpos<mv_array.LastX() ; ++xpos )
    00295         {
    00296             m_mv_prediction = MvMedian( mv_array[ypos][xpos-1],
    00297                                         mv_array[ypos-1][xpos],
    00298                                         mv_array[ypos-1][xpos+1]);
    00299             DoBlock(xpos, ypos , pred_costs , mv_array, guide_array , my_bmatch );
    00300
    00301         }// xpos
    00302
    00303          // The last element in each row
    00304         m_lambda = loc_lambda/float( m_encparams.XNumBlocks() );
    00305         m_mv_prediction = MvMean( mv_array[ypos-1][ mv_array.LastX() ],
    00306                                   mv_array[ypos][ mv_array.LastX()-1 ]);
    00307         DoBlock(mv_array.LastX() , ypos , pred_costs , mv_array, guide_array , my_bmatch );
    00308
    00309     }//ypos
    00310
    00311 }
    00312
    00313 void PixelMatcher::DoBlock(int xpos, int ypos ,
    00314                            TwoDArray<MvCostData>& pred_costs,
    00315                            MvArray& mv_array,
    00316                            const MvArray& guide_array,
    00317                            BlockMatcher& block_match)
    00318 {
    00319
    00320     // Find the best match for each block ...
    00321
    00322     // Use guide from lower down if one exists
    00323     if ( m_level<m_depth )
    00324         AddNewVlistD( m_cand_list , guide_array[ ypos>>1 ][ xpos>>1 ] * 2 , m_xr , m_yr );
    00325
    00326     // use the spatial prediction, also, as a guide
    00327     AddNewVlistD( m_cand_list , m_mv_prediction , m_xr , m_yr );
    00328
    00329     // Find the best motion vector //
    00331
    00332     block_match.FindBestMatch( xpos , ypos , m_cand_list, m_mv_prediction, m_lambda );
    00333
    00334     // Reset the lists ready for the next block (don't erase the first sublist as
    00335     // this is a neighbourhood of zero, which we always look at)
    00336     m_cand_list.erase( m_cand_list.begin()+1 , m_cand_list.end() );
    00337 }