1 //

2 // Copyright (c) 2003-2011, MIST Project, Nagoya University

3 // All rights reserved.

4 //

5 // Redistribution and use in source and binary forms, with or without modification,

6 // are permitted provided that the following conditions are met:

7 //

8 // 1. Redistributions of source code must retain the above copyright notice,

9 // this list of conditions and the following disclaimer.

10 //

11 // 2. Redistributions in binary form must reproduce the above copyright notice,

12 // this list of conditions and the following disclaimer in the documentation

13 // and/or other materials provided with the distribution.

14 //

15 // 3. Neither the name of the Nagoya University nor the names of its contributors

16 // may be used to endorse or promote products derived from this software

17 // without specific prior written permission.

18 //

19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR

20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND

21 // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR

22 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

23 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER

25 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF

26 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

27 //

28 

33 

34 #ifndef __INCLUDE_DP_MATCHING_H__

35 #define __INCLUDE_DP_MATCHING_H__

36 

37 #include <mist/mist.h>

38 #include <mist/config/color.h>

39 #include <vector>

40 #include <functional>

41 

42 

43 // mist名前空間の始まり

44 _MIST_BEGIN

45 

46 

47 namespace __dp__

48 {

49  // 要素間の2乗距離を返すファンクタ（インスタンスはコンストラクタのデフォルト引数となる）

50  template< typename Type >

51  struct square_error : public std::binary_function< Type, Type, double >

52  {

53  double operator( )( const Type &v0, const Type &v1 ) const

54  {

55  return ( static_cast< double >( v0 ) - v1 ) * ( static_cast< double >( v0 ) - v1 );

56  }

57  };

58 

59  // 要素間の2乗距離を返すファンクタ（インスタンスはコンストラクタのデフォルト引数となる）

60  template< typename Type >

61  struct square_error< mist::rgb< Type > > : public std::binary_function< mist::rgb< Type >, mist::rgb< Type >, double >

62  {

63  double operator( )( const mist::rgb< Type > &v0, const mist::rgb< Type > &v1 ) const

64  {

65  return ( static_cast< double >( v0.r ) - v1.r ) * ( static_cast< double >( v0.r ) - v1.r ) + ( static_cast< double >( v0.g ) - v1.g ) * ( static_cast< double >( v0.g ) - v1.g ) + ( static_cast< double >( v0.b ) - v1.b ) * ( static_cast< double >( v0.b ) - v1.b );

66  }

67  };

68 }

69 

70 // 対応付け結果を格納するための構造体

71 class dp_pair

72 {

73  size_t a_;

74  size_t b_;

75 

76 public:

77 

78  dp_pair( )

79  {

80  }

81 

82  dp_pair( const size_t a, const size_t b ) : a_( a ), b_( b )

83  {

84  }

85 

86  size_t a( ) const

87  {

88  return a_;

89  }

90 

91  size_t b( ) const

92  {

93  return b_;

94  }

95 };

96 

97 inline bool operator !=( const dp_pair &p0, const dp_pair &p1 )

98 {

99  return ( ( p0.a( ) != p1.a( ) ) || ( p0.b( ) != p1.b( ) ) );

100 }

101 

102 inline std::ostream &operator <<( std::ostream &out, const dp_pair &in )

103 {

104  return ( out << "( " << in.a( ) << ", " << in.b( ) << " )" );

105 }

106 

107 

115 

116 

117 

164 //1 #include <functional>

174 template< typename Value_type, typename Functor = __dp__::square_error< Value_type > >

175 class dp_matching

176 {

177  typedef typename Functor::result_type distance_type;

178 

179  mist::array< Value_type > pattern_a_;

180  mist::array< Value_type > pattern_b_;

181  mist::array< dp_pair > path_;

182  distance_type distance_;

183  double weight_0_;

184  double weight_1_;

185  double weight_2_;

186  Functor func_;

187 

188  distance_type __distance( const size_t i0, const size_t i1 ) const

189  {

190  return func_( pattern_a_[ i0 ], pattern_b_[ i1 ] );

191  }

192 

193  void __find_path( )

194  {

195  mist::array2< distance_type > distance_array( pattern_a_.size( ), pattern_b_.size( ) );

196  mist::array2< size_t > path_array( pattern_a_.size( ), pattern_b_.size( ) );

197  distance_array( 0, 0 ) = __distance( 0, 0 );

198  for( size_t i = 1 ; i < distance_array.width( ) ; i ++ )

199  {

200  distance_array( i, 0 ) = static_cast< distance_type >( distance_array( i - 1, 0 ) + __distance( i, 0 ) * weight_0_ );

201  path_array( i, 0 ) = 0;

202  }

203  for( size_t j = 1 ; j < distance_array.height( ) ; j ++ )

204  {

205  distance_array( 0, j ) = static_cast< distance_type >( distance_array( 0, j - 1 ) + __distance( 0, j ) * weight_2_ );

206  path_array( 0, j ) = 2;

207  for( size_t i = 1 ; i < distance_array.width( ) ; i ++ )

208  {

209  const distance_type distance = __distance( i, j );

210  const distance_type distance_0 = static_cast< distance_type >( distance_array( i - 1, j ) + distance * weight_0_ );

211  const distance_type distance_1 = static_cast< distance_type >( distance_array( i - 1, j - 1 ) + distance * weight_1_ );

212  const distance_type distance_2 = static_cast< distance_type >( distance_array( i, j - 1 ) + distance * weight_2_ );

213  path_array( i, j ) = ( distance_0 < distance_1 ) ? ( ( distance_0 < distance_2 ) ? 0 : 2 ) : ( ( distance_1 < distance_2 ) ? 1 : 2 );

214  switch( path_array( i, j ) )

215  {

216  case 0:

217  distance_array( i, j ) = distance_0;

218  break;

219  case 1:

220  distance_array( i, j ) = distance_1;

221  break;

222  case 2:

223  distance_array( i, j ) = distance_2;

224  break;

225  default:

226  break;

227  }

228  }

229  }

230  distance_ = distance_array( distance_array.width( ) - 1, distance_array.height( ) - 1 );

231  std::vector< dp_pair > path;

232  path.reserve( pattern_a_.size( ) );

233  size_t mi = pattern_a_.size( ) - 1;

234  size_t mj = pattern_b_.size( ) - 1;

235  path.push_back( dp_pair( mi, mj ) );

236  while( dp_pair( mi, mj ) != dp_pair( 0, 0 ) )

237  {

238  switch( path_array( mi, mj ) )

239  {

240  case 0:

241  path.push_back( dp_pair( -- mi, mj ) );

242  break;

243  case 1:

244  path.push_back( dp_pair( -- mi, -- mj ) );

245  break;

246  case 2:

247  path.push_back( dp_pair( mi, -- mj ) );

248  break;

249  default:

250  break;

251  }

252  }

253  path_.resize( path.size( ) );

254  for( size_t i = 0 ; i < path_.size( ) ; i ++ )

255  {

256  path_[ i ] = path[ path_.size( ) - 1 - i ];

257  }

258  }

259 

260 public:

261 

271  dp_matching( const mist::array< Value_type > &pattern_a, const mist::array< Value_type > &pattern_b, const double weight_0, const double weight_1, const double weight_2, const Functor func = __dp__::square_error< Value_type >( ) )

272  : pattern_a_( pattern_a ), pattern_b_( pattern_b ), weight_0_( weight_0 ), weight_1_( weight_1 ), weight_2_( weight_2 ), func_( func )

273  {

274  __find_path( );

275  }

276 

283  void weights( const double weight_0, const double weight_1, const double weight_2 )

284  {

285  weight_0_ = weight_0;

286  weight_1_ = weight_1;

287  weight_2_ = weight_2;

288  __find_path( );

289  }

290 

295  const mist::array< dp_pair > &path( ) const

296  {

297  return path_;

298  }

299 

304  size_t length( ) const

305  {

306  return path_.size( );

307  }

308 

313  distance_type distance( ) const

314  {

315  return distance_;

316  }

317 };

318 

319 

321 // DPマッチンググループの終わり

322 

323 

324 // mist名前空間の終わり

325 _MIST_END

326 

327 

328 #endif // __INCLUDE_DP_MATCHING_H__

329