itkShapeUniqueLabelMapFilter.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright NumFOCUS
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://www.apache.org/licenses/LICENSE-2.0.txt
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *
 *=========================================================================*/
#ifndef itkShapeUniqueLabelMapFilter_h
#define itkShapeUniqueLabelMapFilter_h
 
#include "itkInPlaceLabelMapFilter.h"
#include "itkShapeLabelObjectAccessors.h"
#include "itkProgressReporter.h"
#include <queue>
#include "itkMath.h"
 
namespace itk
{
template <typename TImage>
class ITK_TEMPLATE_EXPORT ShapeUniqueLabelMapFilter : public InPlaceLabelMapFilter<TImage>
{
public:
  ITK_DISALLOW_COPY_AND_MOVE(ShapeUniqueLabelMapFilter);
 
  using Self = ShapeUniqueLabelMapFilter;
  using Superclass = InPlaceLabelMapFilter<TImage>;
  using Pointer = SmartPointer<Self>;
  using ConstPointer = SmartPointer<const Self>;
 
  using ImageType = TImage;
  using ImagePointer = typename ImageType::Pointer;
  using ImageConstPointer = typename ImageType::ConstPointer;
  using PixelType = typename ImageType::PixelType;
  using IndexType = typename ImageType::IndexType;
  using LabelObjectType = typename ImageType::LabelObjectType;
  using LineType = typename LabelObjectType::LineType;
 
  using AttributeType = typename LabelObjectType::AttributeType;
 
  static constexpr unsigned int ImageDimension = TImage::ImageDimension;
 
  itkNewMacro(Self);
 
  itkOverrideGetNameOfClassMacro(ShapeUniqueLabelMapFilter);
 
#ifdef ITK_USE_CONCEPT_CHECKING
  // Begin concept checking
/*  itkConceptMacro(InputEqualityComparableCheck,
    (Concept::EqualityComparable<InputImagePixelType>));
  itkConceptMacro(IntConvertibleToInputCheck,
    (Concept::Convertible<int, InputImagePixelType>));
  itkConceptMacro(InputOStreamWritableCheck,
    (Concept::OStreamWritable<InputImagePixelType>));*/
// End concept checking
#endif
 
  itkGetConstMacro(ReverseOrdering, bool);
  itkSetMacro(ReverseOrdering, bool);
  itkBooleanMacro(ReverseOrdering);
  itkGetConstMacro(Attribute, AttributeType);
  itkSetMacro(Attribute, AttributeType);
  void
  SetAttribute(const std::string & s)
  {
    this->SetAttribute(LabelObjectType::GetAttributeFromName(s));
  }
protected:
  ShapeUniqueLabelMapFilter();
  ~ShapeUniqueLabelMapFilter() override = default;
 
  void
  GenerateData() override;
 
  template <typename TAttributeAccessor>
  void
  TemplatedGenerateData(const TAttributeAccessor & accessor)
  {
    // Allocate the output
    this->AllocateOutputs();
 
    // the priority queue to store all the lines of all the objects sorted
    using PriorityQueueType =
      typename std::priority_queue<LineOfLabelObject, std::vector<LineOfLabelObject>, LineOfLabelObjectComparator>;
    PriorityQueueType priorityQueue;
 
    const ProgressReporter progress(this, 0, 1);
    // TODO: really report the progress
 
    for (typename ImageType::Iterator it(this->GetLabelMap()); !it.IsAtEnd(); ++it)
    {
      LabelObjectType * labelObject = it.GetLabelObject();
 
      // may reduce the number of lines to proceed
      labelObject->Optimize();
 
      typename LabelObjectType::ConstLineIterator lit(labelObject);
      while (!lit.IsAtEnd())
      {
        priorityQueue.push(LineOfLabelObject(lit.GetLine(), labelObject));
        ++lit;
      }
 
      // clear the lines to read them later
      labelObject->Clear();
 
      // go to the next label
      // progress.CompletedPixel();
    }
 
    if (priorityQueue.empty())
    {
      // nothing to do
      return;
    }
 
    using LinesType = typename std::deque<LineOfLabelObject>;
    LinesType lines;
 
    lines.push_back(priorityQueue.top());
    LineOfLabelObject prev = lines.back();
    IndexType         prevIdx = prev.line.GetIndex();
    priorityQueue.pop();
 
    while (!priorityQueue.empty())
    {
      LineOfLabelObject l = priorityQueue.top();
      IndexType         idx = l.line.GetIndex();
      priorityQueue.pop();
 
      bool newMainLine = false;
      // don't check dim 0!
      for (unsigned int i = 1; i < ImageDimension; ++i)
      {
        if (idx[i] != prevIdx[i])
        {
          newMainLine = true;
        }
      }
 
      assert(newMainLine || (idx[0] >= prevIdx[0]));
 
      if (newMainLine)
      {
        // just push the line
        lines.push_back(l);
      }
      else
      {
        OffsetValueType       prevLength = prev.line.GetLength();
        const OffsetValueType length = l.line.GetLength();
 
        if (prevIdx[0] + prevLength > idx[0])
        {
          // the lines are overlapping. We need to choose which line to keep.
          // the label, the only "attribute" to be guaranteed to be unique, is
          // used to choose
          // which line to keep. This is necessary to avoid the case where a
          // part of a label is over
          // a second label, and below in another part of the image.
          bool                                                  keepCurrent;
          const typename TAttributeAccessor::AttributeValueType prevAttr = accessor(prev.labelObject);
          const typename TAttributeAccessor::AttributeValueType attr = accessor(l.labelObject);
          // this may be changed to a single boolean expression, but may become
          // quite difficult to read
          if (Math::ExactlyEquals(attr, prevAttr))
          {
            if (l.labelObject->GetLabel() > prev.labelObject->GetLabel())
            {
              keepCurrent = !m_ReverseOrdering;
            }
            else
            {
              keepCurrent = m_ReverseOrdering;
            }
          }
          else
          {
            if (attr > prevAttr)
            {
              keepCurrent = !m_ReverseOrdering;
            }
            else
            {
              keepCurrent = m_ReverseOrdering;
            }
          }
 
          if (keepCurrent)
          {
            // keep the current one. We must truncate the previous one to remove
            // the
            // overlap, and take care of the end of the previous line if it
            // extends
            // after the current one.
            if (prevIdx[0] + prevLength > idx[0] + length)
            {
              // the previous line is longer than the current one. Lets take its
              // tail and
              // add it to the priority queue
              IndexType newIdx = idx;
              newIdx[0] = idx[0] + length;
              const OffsetValueType newLength = prevIdx[0] + prevLength - newIdx[0];
              priorityQueue.push(LineOfLabelObject(LineType(newIdx, newLength), prev.labelObject));
            }
            // truncate the previous line to let some place for the current one
            prevLength = idx[0] - prevIdx[0];
            if (prevLength != 0)
            {
              assert(prevIdx[0] <= idx[0]);
              lines.back().line.SetLength(idx[0] - prevIdx[0]);
            }
            else
            {
              // length is 0 - no need to keep that line
              lines.pop_back();
            }
            // and push the current one
            lines.push_back(l);
          }
          else
          {
            // keep the previous one. If the previous line fully overlap the
            // current one,
            // the current one is fully discarded.
            if (prevIdx[0] + prevLength >= idx[0] + length)
            {
              // discarding the current line - just do nothing
            }
            else
            {
              IndexType newIdx = idx;
              newIdx[0] = prevIdx[0] + prevLength;
              const OffsetValueType newLength = idx[0] + length - newIdx[0];
              if (newLength > 0)
              {
                l.line.SetIndex(newIdx);
                l.line.SetLength(newLength);
                // The front of this line is trimmed, it may occur after a line in the queue
                // so the queue is used for the proper ordering.
                priorityQueue.push(l);
              }
            }
          }
        }
        else
        {
          // no overlap - things are just fine already
          lines.push_back(l);
        }
      }
 
      // store the current line as the previous one, and go to the next one.
      prev = lines.back();
      prevIdx = prev.line.GetIndex();
    }
 
    // put the lines in their object
    for (size_t i = 0; i < lines.size(); ++i)
    {
      LineOfLabelObject & l = lines[i];
      l.labelObject->AddLine(l.line);
    }
 
    // remove objects without lines
    typename ImageType::Iterator it(this->GetLabelMap());
    while (!it.IsAtEnd())
    {
      const typename LabelObjectType::LabelType label = it.GetLabel();
      LabelObjectType *                         labelObject = it.GetLabelObject();
 
      if (labelObject->Empty())
      {
        // must increment the iterator before removing the object to avoid
        // invalidating the iterator
        ++it;
        this->GetLabelMap()->RemoveLabel(label);
      }
      else
      {
        ++it;
      }
    }
  }
 
  void
  PrintSelf(std::ostream & os, Indent indent) const override;
 
  AttributeType m_Attribute{};
 
private:
  bool m_ReverseOrdering{};
  struct LineOfLabelObject
  {
    using LineType = typename LabelObjectType::LineType;
    LineOfLabelObject(const LineType _line, LabelObjectType * _lo)
    {
      this->line = _line;
      this->labelObject = _lo;
    }
 
    LineType          line;
    LabelObjectType * labelObject;
  };
 
  class LineOfLabelObjectComparator
  {
  public:
    bool
    operator()(const LineOfLabelObject & lla, const LineOfLabelObject & llb)
    {
      for (int i = ImageDimension - 1; i >= 0; i--)
      {
        if (lla.line.GetIndex()[i] > llb.line.GetIndex()[i])
        {
          return true;
        }
        else if (lla.line.GetIndex()[i] < llb.line.GetIndex()[i])
        {
          return false;
        }
      }
      return false;
    }
  };
}; // end of class
} // end namespace itk
 
#ifndef ITK_MANUAL_INSTANTIATION
#  include "itkShapeUniqueLabelMapFilter.hxx"
#endif
 
#endif