src/Image/Image_Diff.cxx

   1 // Created on: 2012-07-10
   2 // Created by: VRO
   3 // Copyright (c) 2012-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #include <Image_Diff.hxx>
  17 #include <Image_AlienPixMap.hxx>
  18
  19 #include <TColStd_MapIteratorOfMapOfInteger.hxx>
  20
  21 #include <cstdlib>
  22
  23
  24 IMPLEMENT_STANDARD_RTTIEXT(Image_Diff,Standard_Transient)
  25
  26 //! POD structure for packed RGB color value (3 bytes)
  27 struct Image_ColorXXX24
  28 {
  29   Standard_Byte v[3];
  30   typedef Standard_Byte ComponentType_t;         //!< Component type
  31   static Standard_Integer Length() { return 3; } //!< Returns the number of components
  32 };
  33
  34 inline Image_ColorXXX24 operator- (const Image_ColorXXX24& theA,
  35                                    const Image_ColorXXX24& theB)
  36 {
  37   return Image_ColorSub3 (theA, theB);
  38 }
  39
  40 //! Dot squared for difference of two colors
  41 inline Standard_Integer dotSquared (const Image_ColorXXX24& theColor)
  42 {
  43   // explicitly convert to integer
  44   const Standard_Integer r = theColor.v[0];
  45   const Standard_Integer g = theColor.v[1];
  46   const Standard_Integer b = theColor.v[2];
  47   return r * r + g * g + b * b;
  48 }
  49
  50 //! @return true if pixel is black
  51 inline bool isBlack (const Image_ColorXXX24& theColor)
  52 {
  53   return theColor.v[0] == 0
  54       && theColor.v[1] == 0
  55       && theColor.v[2] == 0;
  56 }
  57
  58 //! Converts a pixel position (row, column) to one integer value
  59 inline Standard_Size pixel2Int (const Standard_Size aRow,
  60                                 const Standard_Size aCol)
  61 {
  62   return aCol + (aRow << 15);
  63 }
  64
  65 //! Converts an integer value to pixel coordinates (row, column)
  66 inline void int2Pixel (const Standard_Size theValue,
  67                        Standard_Size&      theRow,
  68                        Standard_Size&      theCol)
  69 {
  70   theRow = (theValue >> 15);
  71   theCol = theValue - (theRow << 15);
  72 }
  73
  74 namespace
  75 {
  76
  77   inline ptrdiff_t getAbs (const ptrdiff_t theValue)
  78   {
  79     return theValue >= 0 ? theValue : -theValue;
  80   }
  81
  82   static const Standard_Size NEIGHBOR_PIXELS_NB = 8;
  83   static struct
  84   {
  85     Standard_Integer row_inc;
  86     Standard_Integer col_inc;
  87
  88     inline Standard_Size pixel2Int (const Standard_Size theRowCenter,
  89                                     const Standard_Size theColCenter) const
  90     {
  91       return ::pixel2Int (theRowCenter + Standard_Size(row_inc),
  92                           theColCenter + Standard_Size(col_inc));
  93     }
  94
  95     inline bool isBlack (const Image_PixMap& theData,
  96                          const Standard_Size theRowCenter,
  97                          const Standard_Size theColCenter) const
  98     {
  99       return ::isBlack (theData.Value<Image_ColorXXX24> (theRowCenter + Standard_Size(row_inc),
 100                                                          theColCenter + Standard_Size(col_inc)));
 101     }
 102
 103     inline bool isValid (const Image_PixMap& theData,
 104                          const Standard_Size theRowCenter,
 105                          const Standard_Size theColCenter) const
 106     {
 107       const Standard_Size aRow = theRowCenter + Standard_Size(row_inc);
 108       const Standard_Size aCol = theColCenter + Standard_Size(col_inc);
 109       return aRow < theData.SizeX()  // this unsigned math checks Standard_Size(-1) at-once
 110           && aCol < theData.SizeY();
 111     }
 112   }
 113   const NEIGHBOR_PIXELS[NEIGHBOR_PIXELS_NB] =
 114   {
 115     {-1, -1}, {-1,  0}, {-1,  1},
 116     { 0, -1},           { 0,  1},
 117     { 1, -1}, { 1,  0}, { 1,  1}
 118   };
 119
 120   static bool isSupportedFormat (const Image_PixMap::ImgFormat theFormat)
 121   {
 122     return theFormat == Image_PixMap::ImgRGB
 123         || theFormat == Image_PixMap::ImgBGR
 124         || theFormat == Image_PixMap::ImgRGB32
 125         || theFormat == Image_PixMap::ImgBGR32
 126         || theFormat == Image_PixMap::ImgRGBA
 127         || theFormat == Image_PixMap::ImgBGRA;
 128   }
 129
 130 } // anonymous namespace
 131
 132 // =======================================================================
 133 // function : Image_Diff
 134 // purpose  :
 135 // =======================================================================
 136 Image_Diff::Image_Diff()
 137 : myColorTolerance (0.0),
 138   myIsBorderFilterOn (Standard_False)
 139 {
 140   //
 141 }
 142
 143 // =======================================================================
 144 // function : ~Image_Diff
 145 // purpose  :
 146 // =======================================================================
 147 Image_Diff::~Image_Diff()
 148 {
 149   releaseGroupsOfDiffPixels();
 150 }
 151
 152 // =======================================================================
 153 // function : Init
 154 // purpose  :
 155 // =======================================================================
 156 Standard_Boolean Image_Diff::Init (const Handle(Image_PixMap)& theImageRef,
 157                                    const Handle(Image_PixMap)& theImageNew,
 158                                    const Standard_Boolean      theToBlackWhite)
 159 {
 160   myImageRef.Nullify();
 161   myImageNew.Nullify();
 162   myDiffPixels.Clear();
 163   releaseGroupsOfDiffPixels();
 164   if (theImageRef.IsNull()   || theImageNew.IsNull()
 165    || theImageRef->IsEmpty() || theImageNew->IsEmpty()
 166    || theImageRef->SizeX()   != theImageNew->SizeX()
 167    || theImageRef->SizeY()   != theImageNew->SizeY()
 168    || theImageRef->Format()  != theImageNew->Format())
 169   {
 170 #ifdef OCCT_DEBUG
 171     std::cerr << "Images has different format or dimensions\n";
 172 #endif
 173     return Standard_False;
 174   }
 175   else if (!isSupportedFormat (theImageRef->Format()))
 176   {
 177 #ifdef OCCT_DEBUG
 178     std::cerr << "Images has unsupported pixel format\n";
 179 #endif
 180     return Standard_False;
 181   }
 182   else if (theImageRef->SizeX() >= 0xFFFF
 183         || theImageRef->SizeY() >= 0xFFFF)
 184   {
 185 #ifdef OCCT_DEBUG
 186     std::cerr << "Image too large\n";
 187 #endif
 188     return Standard_False;
 189   }
 190
 191   myImageRef = theImageRef;
 192   myImageNew = theImageNew;
 193
 194   if (theToBlackWhite)
 195   {
 196     // Convert the images to white/black
 197     const Image_ColorXXX24 aWhite = {{255, 255, 255}};
 198     for (Standard_Size aRow = 0; aRow < myImageRef->SizeY(); ++aRow)
 199     {
 200       for (Standard_Size aCol = 0; aCol < myImageRef->SizeX(); ++aCol)
 201       {
 202         Image_ColorXXX24& aPixel1 = myImageRef->ChangeValue<Image_ColorXXX24> (aRow, aCol);
 203         if (!isBlack (aPixel1))
 204         {
 205           aPixel1 = aWhite;
 206         }
 207         Image_ColorXXX24& aPixel2 = myImageNew->ChangeValue<Image_ColorXXX24> (aRow, aCol);
 208         if (!isBlack (aPixel2))
 209         {
 210           aPixel2 = aWhite;
 211         }
 212       }
 213     }
 214   }
 215
 216   return Standard_True;
 217 }
 218
 219
 220 // =======================================================================
 221 // function : Init
 222 // purpose  :
 223 // =======================================================================
 224 Standard_Boolean Image_Diff::Init (const TCollection_AsciiString& theImgPathRef,
 225                                    const TCollection_AsciiString& theImgPathNew,
 226                                    const Standard_Boolean         theToBlackWhite)
 227 {
 228   Handle(Image_AlienPixMap) anImgRef = new Image_AlienPixMap();
 229   Handle(Image_AlienPixMap) anImgNew = new Image_AlienPixMap();
 230   if (!anImgRef->Load (theImgPathRef)
 231    || !anImgNew->Load (theImgPathNew))
 232   {
 233 #ifdef OCCT_DEBUG
 234     std::cerr << "Failed to load image(s) file(s)\n";
 235 #endif
 236     return Standard_False;
 237   }
 238   return Init (anImgRef, anImgNew, theToBlackWhite);
 239 }
 240
 241 // =======================================================================
 242 // function : SetColorTolerance
 243 // purpose  :
 244 // =======================================================================
 245 void Image_Diff::SetColorTolerance (const Standard_Real theTolerance)
 246 {
 247   myColorTolerance = theTolerance;
 248 }
 249
 250 // =======================================================================
 251 // function : ColorTolerance
 252 // purpose  :
 253 // =======================================================================
 254 Standard_Real Image_Diff::ColorTolerance() const
 255 {
 256   return myColorTolerance;
 257 }
 258
 259 // =======================================================================
 260 // function : SetBorderFilterOn
 261 // purpose  :
 262 // =======================================================================
 263 void Image_Diff::SetBorderFilterOn (const Standard_Boolean theToIgnore)
 264 {
 265   myIsBorderFilterOn = theToIgnore;
 266 }
 267
 268 // =======================================================================
 269 // function : IsBorderFilterOn
 270 // purpose  :
 271 // =======================================================================
 272 Standard_Boolean Image_Diff::IsBorderFilterOn() const
 273 {
 274   return myIsBorderFilterOn;
 275 }
 276
 277 // =======================================================================
 278 // function : Compare
 279 // purpose  :
 280 // =======================================================================
 281 Standard_Integer Image_Diff::Compare()
 282 {
 283   // Number of different pixels (by color)
 284   Standard_Integer aNbDiffColors = 0;
 285   myDiffPixels.Clear();
 286
 287   if (myImageRef.IsNull() || myImageNew.IsNull())
 288   {
 289     return -1;
 290   }
 291
 292   // first check if images are exactly teh same
 293   if (! memcmp (myImageNew->Data(), myImageRef->Data(), myImageRef->SizeBytes()))
 294   {
 295     return 0;
 296   }
 297
 298   // Tolerance of comparison operation for color
 299   // Maximum difference between colors (white - black) = 100%
 300   Image_ColorXXX24 aDiff = {{255, 255, 255}};
 301   const Standard_Integer aMaxDiffColor  = dotSquared (aDiff);
 302   const Standard_Integer aDiffThreshold = Standard_Integer(Standard_Real(aMaxDiffColor) * myColorTolerance);
 303
 304   // we don't care about RGB/BGR/RGBA/BGRA/RGB32/BGR32 differences
 305   // because we just compute summ of r g b components
 306
 307   // compare colors of each pixel
 308   for (Standard_Size aRow = 0; aRow < myImageRef->SizeY(); ++aRow)
 309   {
 310     for (Standard_Size aCol = 0; aCol < myImageRef->SizeX(); ++aCol)
 311     {
 312       aDiff = myImageNew->Value<Image_ColorXXX24> (aRow, aCol) - myImageRef->Value<Image_ColorXXX24> (aRow, aCol);
 313       if (dotSquared (aDiff) > aDiffThreshold)
 314       {
 315         const Standard_Size aValue = pixel2Int (aRow, aCol);
 316         myDiffPixels.Append (aValue);
 317         ++aNbDiffColors;
 318       }
 319     }
 320   }
 321
 322   // take into account a border effect
 323   if (myIsBorderFilterOn && myDiffPixels.Length() > 0)
 324   {
 325     aNbDiffColors = ignoreBorderEffect();
 326   }
 327
 328   return aNbDiffColors;
 329 }
 330
 331 // =======================================================================
 332 // function : SaveDiffImage
 333 // purpose  :
 334 // =======================================================================
 335 Standard_Boolean Image_Diff::SaveDiffImage (Image_PixMap& theDiffImage) const
 336 {
 337   if (myImageRef.IsNull() || myImageNew.IsNull())
 338   {
 339     return Standard_False;
 340   }
 341
 342   if (theDiffImage.IsEmpty()
 343    || theDiffImage.SizeX() != myImageRef->SizeX()
 344    || theDiffImage.SizeY() != myImageRef->SizeY()
 345    || !isSupportedFormat (theDiffImage.Format()))
 346   {
 347     if (!theDiffImage.InitTrash (Image_PixMap::ImgRGB, myImageRef->SizeX(), myImageRef->SizeY()))
 348     {
 349       return Standard_False;
 350     }
 351   }
 352
 353   Standard_Size aRow, aCol;
 354   const Image_ColorXXX24 aWhite = {{255, 255, 255}};
 355
 356   // initialize black image for dump
 357   memset (theDiffImage.ChangeData(), 0, theDiffImage.SizeBytes());
 358   if (myGroupsOfDiffPixels.IsEmpty())
 359   {
 360     if (myIsBorderFilterOn)
 361     {
 362       return Standard_True;
 363     }
 364
 365     for (Standard_Integer aPixelId = 0; aPixelId < myDiffPixels.Length(); ++aPixelId)
 366     {
 367       const Standard_Size aValue = myDiffPixels.Value (aPixelId);
 368       int2Pixel (aValue, aRow, aCol);
 369       theDiffImage.ChangeValue<Image_ColorXXX24> (aRow, aCol) = aWhite;
 370     }
 371
 372     return Standard_True;
 373   }
 374
 375   Standard_Integer aGroupId = 1;
 376   for (ListOfMapOfInteger::Iterator aGrIter (myGroupsOfDiffPixels); aGrIter.More(); aGrIter.Next(), ++aGroupId)
 377   {
 378     if (myLinearGroups.Contains (aGroupId))
 379     {
 380       continue; // skip linear groups
 381     }
 382
 383     const TColStd_MapOfInteger* aGroup = aGrIter.Value();
 384     for (TColStd_MapIteratorOfMapOfInteger aPixelIter(*aGroup);
 385          aPixelIter.More(); aPixelIter.Next())
 386     {
 387       int2Pixel (aPixelIter.Key(), aRow, aCol);
 388       theDiffImage.ChangeValue<Image_ColorXXX24> (aRow, aCol) = aWhite;
 389     }
 390   }
 391
 392   return Standard_True;
 393 }
 394
 395 // =======================================================================
 396 // function : SaveDiffImage
 397 // purpose  :
 398 // =======================================================================
 399 Standard_Boolean Image_Diff::SaveDiffImage (const TCollection_AsciiString& theDiffPath) const
 400 {
 401   if (myImageRef.IsNull() || myImageNew.IsNull() || theDiffPath.IsEmpty())
 402   {
 403     return Standard_False;
 404   }
 405
 406   Image_AlienPixMap aDiff;
 407   if (!aDiff.InitTrash (Image_PixMap::ImgRGB, myImageRef->SizeX(), myImageRef->SizeY())
 408    || !SaveDiffImage (aDiff))
 409   {
 410     return Standard_False;
 411   }
 412
 413   // save image
 414   return aDiff.Save (theDiffPath);
 415 }
 416
 417 // =======================================================================
 418 // function : ignoreBorderEffect
 419 // purpose  :
 420 // =======================================================================
 421 Standard_Integer Image_Diff::ignoreBorderEffect()
 422 {
 423   if (myImageRef.IsNull() || myImageNew.IsNull())
 424   {
 425     return 0;
 426   }
 427
 428   // allocate groups of different pixels
 429   releaseGroupsOfDiffPixels();
 430
 431   // Find a different area (a set of close to each other pixels which colors differ in both images).
 432   // It filters alone pixels with different color.
 433   Standard_Size aRow1 = 0, aCol1 = 0, aRow2, aCol2;
 434   Standard_Integer aLen1 = (myDiffPixels.Length() > 0) ? (myDiffPixels.Length() - 1) : 0;
 435   for (Standard_Integer aPixelId1 = 0; aPixelId1 < aLen1; ++aPixelId1)
 436   {
 437     const Standard_Size aValue1 = myDiffPixels.Value (aPixelId1);
 438     int2Pixel (aValue1, aRow1, aCol1);
 439
 440     // Check other pixels in the list looking for a neighbour of this one
 441     for (Standard_Integer aPixelId2 = aPixelId1 + 1; aPixelId2 < myDiffPixels.Length(); ++aPixelId2)
 442     {
 443       const Standard_Size aValue2 = myDiffPixels.Value (aPixelId2);
 444       int2Pixel (aValue2, aRow2, aCol2);
 445       if (getAbs (ptrdiff_t (aCol1 - aCol2)) <= 1 &&
 446           getAbs (ptrdiff_t (aRow1 - aRow2)) <= 1)
 447       {
 448         // A neighbour is found. Create a new group and add both pixels.
 449         if (myGroupsOfDiffPixels.IsEmpty())
 450         {
 451           TColStd_MapOfInteger* aGroup = new TColStd_MapOfInteger();
 452           aGroup->Add ((Standard_Integer)aValue1);
 453           aGroup->Add ((Standard_Integer)aValue2);
 454           myGroupsOfDiffPixels.Append (aGroup);
 455         }
 456         else
 457         {
 458           // Find a group the pixels belong to.
 459           Standard_Boolean isFound = Standard_False;
 460           for (ListOfMapOfInteger::Iterator aGrIter (myGroupsOfDiffPixels); aGrIter.More(); aGrIter.Next())
 461           {
 462             TColStd_MapOfInteger*& aGroup = aGrIter.ChangeValue();
 463             if (aGroup->Contains ((Standard_Integer)aValue1))
 464             {
 465               aGroup->Add ((Standard_Integer)aValue2);
 466               isFound = Standard_True;
 467               break;
 468             }
 469           }
 470
 471           if (!isFound)
 472           {
 473             // Create a new group
 474             TColStd_MapOfInteger* aGroup = new TColStd_MapOfInteger();
 475             aGroup->Add ((Standard_Integer)aValue1);
 476             aGroup->Add ((Standard_Integer)aValue2);
 477             myGroupsOfDiffPixels.Append (aGroup);
 478           }
 479         }
 480       }
 481     }
 482   }
 483
 484   // filter linear groups which represent border of a solid shape
 485   Standard_Integer aGroupId = 1;
 486   for (ListOfMapOfInteger::Iterator aGrIter (myGroupsOfDiffPixels); aGrIter.More(); aGrIter.Next(), ++aGroupId)
 487   {
 488     Standard_Integer aNeighboursNb = 0;
 489     Standard_Boolean isLine = Standard_True;
 490     const TColStd_MapOfInteger* aGroup = aGrIter.Value();
 491     for (TColStd_MapIteratorOfMapOfInteger aPixelIter (*aGroup); aPixelIter.More(); aPixelIter.Next())
 492     {
 493       int2Pixel (aPixelIter.Key(), aRow1, aCol1);
 494       aNeighboursNb = 0;
 495
 496       // pixels of a line have only 1 or 2 neighbour pixels inside the same group
 497       // check all neighbour pixels on presence in the group
 498       for (Standard_Size aNgbrIter = 0; aNgbrIter < NEIGHBOR_PIXELS_NB; ++aNgbrIter)
 499       {
 500         if (NEIGHBOR_PIXELS[aNgbrIter].isValid (*myImageRef, aRow1, aCol1)
 501          && aGroup->Contains ((Standard_Integer)NEIGHBOR_PIXELS[aNgbrIter].pixel2Int (aRow1, aCol1)))
 502         {
 503           ++aNeighboursNb;
 504         }
 505       }
 506
 507       if (aNeighboursNb > 2)
 508       {
 509         isLine = Standard_False;
 510         break;
 511       }
 512     } // for pixels inside group...
 513
 514     if (isLine)
 515     {
 516       // Test a pixel of the linear group on belonging to a solid shape.
 517       // Consider neighbour pixels of the last pixel of the linear group in the 1st image.
 518       // If the pixel has greater than 1 not black neighbour pixel, it is a border of a shape.
 519       // Otherwise, it may be a topological edge, for example.
 520       aNeighboursNb = 0;
 521       for (Standard_Size aNgbrIter = 0; aNgbrIter < NEIGHBOR_PIXELS_NB; ++aNgbrIter)
 522       {
 523         if ( NEIGHBOR_PIXELS[aNgbrIter].isValid (*myImageRef, aRow1, aCol1)
 524          && !NEIGHBOR_PIXELS[aNgbrIter].isBlack (*myImageRef, aRow1, aCol1))
 525         {
 526           ++aNeighboursNb;
 527         }
 528       }
 529
 530       if (aNeighboursNb > 1)
 531       {
 532         myLinearGroups.Add (aGroupId);
 533       }
 534     }
 535   } // for groups...
 536
 537   // number of different groups of pixels (except linear groups)
 538   Standard_Integer aNbDiffColors = 0;
 539   aGroupId = 1;
 540   for (ListOfMapOfInteger::Iterator aGrIter (myGroupsOfDiffPixels); aGrIter.More(); aGrIter.Next(), ++aGroupId)
 541   {
 542     if (!myLinearGroups.Contains (aGroupId))
 543       ++aNbDiffColors;
 544   }
 545
 546   return aNbDiffColors;
 547 }
 548
 549 // =======================================================================
 550 // function : releaseGroupsOfDiffPixels
 551 // purpose  :
 552 // =======================================================================
 553 void Image_Diff::releaseGroupsOfDiffPixels()
 554 {
 555   for (ListOfMapOfInteger::Iterator aGrIter (myGroupsOfDiffPixels); aGrIter.More(); aGrIter.Next())
 556   {
 557     TColStd_MapOfInteger*& aGroup = aGrIter.ChangeValue();
 558     delete aGroup;
 559   }
 560   myGroupsOfDiffPixels.Clear();
 561   myLinearGroups.Clear();
 562 }