cvrQuickMedian.h

Go to the documentation of this file.

/*
 * Copyright (C) 1998 - 2005
 * Lehrstuhl fuer Technische Informatik, RWTH-Aachen, Germany
 *
 *
 * This file is part of the Computer Vision and Robotics Library (CVR-Lib)
 *
 * The CVR-Lib is free software; you can redistribute it and/or
 * modify it under the terms of the BSD License.
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * 3. Neither the name of the authors nor the names of its contributors may be
 *    used to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */



/**
 * \file   cvrQuickMedian.h
 *         This file contains the functor quickMedian, which
 *         calculates the median quickly
 * \author Guy Wafo
 * \date   27.03.2001
 *
 * $Id: cvrQuickMedian.h,v 1.5 2007/10/13 00:18:22 alvarado Exp $
 */

#ifndef _CVR_QUICKMEDIAN_H_
#define _CVR_QUICKMEDIAN_H_

#include "cvrFunctor.h"
#include "cvrVector.h"
#include "cvrMatrix.h"
#include "cvrMedianEvenCase.h"

namespace cvr {

  /**
   * Quick median search.
   *
   * This class is used to extract the median of the elements of a
   * given vector or matrix.  The median is defined as the element at
   * the middle position of the sorted vector.  The algorithm used is
   * based on the quick sort.
   * For vectors (or matrices) with an even number n of elements, the
   * median will be the element at (n/2) or (n/2)-1 depending on the
   * parameter settings.
   *
   * On-place applies are in this implementation faster than on copy ones.
   *
   * The type of the vector elements (T) must accept the operators <
   * and >.
   *
   * @ingroup gStatistics
   */
  class quickMedian : public functor {
  public:

    /**
     * The parameters for the class quickMedian
     */
    class parameters : public functor::parameters {
    public:
      /**
       * Default constructor
       */
      parameters();

      /**
       * copy constructor
       * @param other the parameters object to be copied
       */
      parameters(const parameters& other);

      /**
       * destructor
       */
      ~parameters();

      /**
       * Returns the name of this class.
       */
      const std::string& name() const;

      /**
       * copy the contents of a parameters object
       * @param other the parameters object to be copied
       * @return a reference to this parameters object
       */
      parameters& copy(const parameters& other);

      /**
       * Alias for copy member
       * @param other the functor to be copied
       * @return a reference to this functor object
       */
      parameters& operator=(const parameters& other);

      /**
       * returns a pointer to a clone of the parameters
       */
      virtual parameters* clone() const;

      /**
       * returns a pointer to a new instance of the parameters
       */
      virtual parameters* newInstance() const;

      /**
       * Write the parameters in the given ioHandler
       * @param handler the ioHandler to be used
       * @param complete if true (the default) the enclosing begin/end will
       *        be also written, otherwise only the data block will be written.
       * @return true if write was successful
       */
      virtual bool write(ioHandler& handler,const bool complete=true) const;

      /**
       * Read the parameters from the given ioHandler
       * @param handler the ioHandler to be used
       * @param complete if true (the default) the enclosing begin/end will
       *        be also written, otherwise only the data block will be written.
       * @return true if write was successful
       */
      virtual bool read(ioHandler& handler,const bool complete=true);

      // ------------------------------------------------
      // the parameters
      // ------------------------------------------------

      /**
       * Specifies how to consider the case when the number of elements of
       * the vector is even (see cvr::eMedianEvenCase)
       *
       * This parameter has no effect for odd-sized vectors.
       *
       * Default value: TakeLower
       */
      eMedianEvenCase medianEvenCase;
    };

    /**
     * Default constructor
     */
    quickMedian();

    /**
     * Constructor to set parameters
     */
    quickMedian(const parameters& param);

    /**
     * Constructor with indicator what to do for even-sized vectors
     */
    quickMedian(const eMedianEvenCase medianEvenCase);

    /**
     * copy constructor
     * @param other the object to be copied
     */
    quickMedian(const quickMedian& other);

    /**
     * destructor
     */
    virtual ~quickMedian();

    /**
     * Returns the name of this class.
     */
    const std::string& name() const;

    /**
     * Calculates the median of the given matrix, which WILL BE modified.
     * The elements of the matrix will be considered as part of a vector
     * with "columns()" times "rows()" elements.
     *
     * @param src matrix<T> with the source data.
     * @param median the median value of the given matrix.
     * @return \c true on success \c false otherwise
     */
    template <typename T>
    bool apply(matrix<T>& src, T& median) const;

    /**
     * Calculates the median of the given matrix, which is NOT modified.
     * The elements of the matrix will be considered as part of a vector
     * with "columns()" times "rows()" elements.
     *
     * @param src matrix<T> with the source data.
     * @param median the median value of the given matrix.
     * @return \c true on success \c false otherwise
     */
    template <typename T>
    bool apply(const matrix<T>& src, T& median) const;

    /**
     * Calculates the median of \a src, the result is left in \a dest.
     * The elements of the matrix will be considered as part of a vector
     * with "columns()" times "rows()" elements.
     *
     * @param src matrix<T> with the source data.
     * @param dest partially sorted matrix.
     * @param median the median value of the given matrix.
     * @return true on success false otherwise
     */
    template <typename T>
    bool apply(const matrix<T>& src, matrix<T>& dest, T& median) const;

    /**
     * Find the median of a vector type V, which can be an cvr::genericVector
     * or its derived classes, or a std::vector.  In principle the container
     * type V just needs to support:
     * - the type definitions V::size_type and V::value_type,
     * - the operator[] returning elements of type V::value_type
     * - the V::value_type has to be comparable with the operator<.
     * - the method empty()
     * - the method size() returning a V::size_type
     *
     * The resulting vector contains the elements less or equal than the median
     * for the indexes <code>x</code> such that <code>x < size()/2</code>,
     * and higher or equal otherwise.
     *
     * @param srcdest vector<T> with the source data.  The result
     *                 will be left here too.
     * @param median  the median value
     *
     * @return true on success false otherwise
     */
    template <class V>
    bool apply(V& srcdest, typename V::value_type& median) const;

    /**
     * Operates on the given parameter.
     * @param src vector with the source data.
     * @param median the median value
     * @return true on success false otherwise
     */
    template <class V>
    bool apply(const V& src, typename V::value_type& median) const;

    /**
     * Operates on the given parameter.
     * @param src vector with the source data.
     * @param dest the partially sorted vector.  The elements at the
     *             first half of the vector are less or equal than the median
     *             and on the other half greater or equal.
     * @param median  the median value
     * @return true on success false otherwise
     */
    template <class V>
    bool apply(const V& src, V& dest,
               typename V::value_type& median) const;

    /**
     * A shortcut function for apply(const vector<T>&, T&) const. Note
     * that internally another vector and T are used.
     *
     * @param src vector whose median is sought
     * @returns the median of \a src
     */
    template <class V>
    typename V::value_type median(const V& src) const;

    /**
     * Copy data of "other" functor.
     * @param other the functor to be copied
     * @return a reference to this functor object
     */
    quickMedian& copy(const quickMedian& other);

    /**
     * Returns a pointer to a clone of this functor.
     */
    virtual quickMedian* clone() const;

    /**
     * Returns a pointer to a new instance of this functor.
     */
    virtual quickMedian* newInstance() const;

    /**
     * Returns used parameters
     */
    const parameters& getParameters() const;

  protected:
    /**
     * This method calculates the median in a recursively form.
     * The template type V has to be a vector following an interface like
     * the cvr::vector or the std::vector, implementing the operator[]
     */
    template <class V>
    typename V::value_type findMedian(V& vct,
                                      const int begin,
                                      const int end,
                                      const int medianPos) const;

    /**
     * This method chooses a pivot-value and ensures that lower values lie
     * at the left and higher values at the right of its final position, which
     * will be returned.
     * The template type V has to be a vector following an interface like
     * the cvr::vector or the std::vector, implementing the operator[]
     */
    template <class V>
    int partition(V& vct,
                  const int begin,
                  const int end) const;

  };

}


#include "cvrQuickMedian_template.h"

#endif