CODEWITHSUNDEEP
c++algorithmopencv
mans
mans

Reputation: 18188

what is the fastest way to search inside a matrix for min and max alongside of different rows or cols in c++

assume that I need to search inside a matrix over rows and cols to find min values, what is the best way to do this?

What I can think of it at the moment is to have two nested vector as follow:

std::vector<std::vector<float>> myData;

and search it in this way:

// row search on row say 10
int index= std::min_element(myData[10].begin(), myData[10].end()) - myData[10].begin();

but for searching on cols, I need to write a for loop to do the search.

 // col search say on col 20
 float min_value=10000000;  / assuming values in table are less than this value
 int min_index=-1;
 for(int i=0;i<myData.size();++i)
 {
       if(myData[i][20] <min_value)
       {
            min_value=myData[i][20];
            min_index=i;
        }
  }

Is there any better way to do this? I also have access to OpenCV.

Upvotes: 3

Views: 2062

Answers (5)

beaker
beaker

Reputation: 16811

If you have an OpenCV Mat, you can use minMaxLoc:

void minMaxLoc(InputArray src, double* minVal, double* maxVal=0, 
    Point* minLoc=0, Point* maxLoc=0, InputArray mask=noArray())

The return values minVal/maxVal contain the actual values while minLoc/maxLoc are the coordinates of the min/max (the first occurrence if there are multiple).

Obviously, if you pass the entire matrix you'll get the global min/max, but you can also just pass a single row or column.

For a matrix C you can find the min/max for column n using Mat::col

minMaxLoc(C.col(n), &minVal, &maxVal, &minLoc, &maxLoc);

or for row m using Mat::row

minMaxLoc(C.row(m), &minVal, &maxVal, &minLoc, &maxLoc);

Both Mat::col and Mat::row are O(1) operations in that they don't copy any data, but I haven't done any benchmarks to determine how fast their column iteration is.

Upvotes: 2

kiranpradeep
kiranpradeep

Reputation: 11221

Instead of using minMaxLoc with range/roi, we can use cv::reduce(1) for row/column wise minimum/maximum. Sample below. 

unsigned char data[4][2] = { 1,2,3,4,5,6,7,8 };
Mat img(4, 2, CV_8UC1, data) ;

Mat rowMinImg;
int singleCoumnResult = 1;
cv::reduce(img, rowMinImg, singleCoumnResult, CV_REDUCE_MIN );

//Mat colMinImg;
//int singleRowResult = 0;
//cv::reduce(img, colMinImg, singleRowResult, CV_REDUCE_MIN );

A quick look into implementation of cv::reduce(2), shows it is a simple for loop to find min/max values. So, if you have your data already in an OpenCV Mat, I think this is the way to go.

Upvotes: 1

nils
nils

Reputation: 2534

If I understood you correctly, you want to be able to find minimum and maximum values (and locations) of a given matrix:

  1. globally
  2. in a single row, and,
  3. in a single column

Then the following MWE may help you. Let's first look at the output:

mat = 
[75, 97, 66, 95, 15, 22;
 24, 21, 71, 72, 34, 66;
 21, 69, 88, 72, 64, 1;
 26, 47, 26, 40, 95, 24;
 70, 37, 9, 83, 16, 83]

global min =   1 @ [5, 2]
global max =  97 @ [1, 0]

Row 0 min =  15 @ [4, 0] max =  97 @ [1, 0]
Row 1 min =  21 @ [1, 1] max =  72 @ [3, 1]
Row 2 min =   1 @ [5, 2] max =  88 @ [2, 2]
Row 3 min =  24 @ [5, 3] max =  95 @ [4, 3]
Row 4 min =   9 @ [2, 4] max =  83 @ [3, 4]

Col 0 min =  21 @ [0, 2] max =  75 @ [0, 0]
Col 1 min =  21 @ [1, 1] max =  97 @ [1, 0]
Col 2 min =   9 @ [2, 4] max =  88 @ [2, 2]
Col 3 min =  40 @ [3, 3] max =  95 @ [3, 0]
Col 4 min =  15 @ [4, 0] max =  95 @ [4, 3]
Col 5 min =   1 @ [5, 2] max =  83 @ [5, 4]

And the corresponding code (which you said is OK to use OpenCV):

#include <opencv2/core/core.hpp>

#include <algorithm>
#include <iostream>
#include <iomanip>

namespace {

template <typename T>
std::pair< cv::Point, cv::Point > findMinMaxLoc( cv::Mat_<T> & mat )
{
    double ignored1, ignored2;
    std::pair< cv::Point, cv::Point > mmloc;
    cv::minMaxLoc( mat, &ignored1, &ignored2, &(mmloc.first), &(mmloc.second) );

    return mmloc;
}

template <typename T>
std::pair< cv::Point, cv::Point > minMaxLocRow( cv::Mat_<T> & mat, int row )
{
    cv::Rect roi( 0, row, mat.size().width, 1 );
    cv::Mat_<T> matRow = mat( roi );

    std::pair< cv::Point, cv::Point > mmloc = findMinMaxLoc( matRow );
    mmloc.first.y  = row;
    mmloc.second.y = row;

    return mmloc;
}

template <typename T>
std::pair< cv::Point, cv::Point > minMaxLocCol( cv::Mat_<T> & mat, int col )
{
    cv::Rect roi( col, 0, 1, mat.size().height  );
    cv::Mat_<T> matCol = mat( roi );

    std::pair< cv::Point, cv::Point > mmloc = findMinMaxLoc( matCol );
    mmloc.first.x  = col;
    mmloc.second.x = col;

    return mmloc;
}

} // namespace

int main( int argc, char ** argv )
{
    // Generate a matrix filled with random data.
    cv::Size size( 6, 5 );
    cv::Mat1i mat( size ); // Or cv::Mat1b, cv::Mat3f, etc.
    cv::RNG rng( cv::getCPUTickCount() );

    rng.fill( mat, cv::RNG::UNIFORM, 0, 100 );

    std::cout << "mat = " << std::endl << mat << std::endl << std::endl;

    // Find the global minimum and maximum.
    std::pair< cv::Point, cv::Point > mmloc = findMinMaxLoc( mat );

    std::cout << "global min = " << std::setw( 3 ) << std::setfill( ' ' );
    std::cout << mat( mmloc.first )  << " @ " << mmloc.first  << std::endl;
    std::cout << "global max = " << std::setw( 3 ) << std::setfill( ' ' );
    std::cout << mat( mmloc.second ) << " @ " << mmloc.second << std::endl << std::endl;

    // Row-wise extrema.
    for ( int row = 0; row < size.height; ++row )
    {
        std::pair< cv::Point, cv::Point > mmloc = minMaxLocRow( mat, row );

        std::cout << "Row " << row;
        std::cout << " min = " << std::setw( 3 ) << std::setfill( ' ' );
        std::cout << mat( mmloc.first )  << " @ " << mmloc.first;
        std::cout << " max = " << std::setw( 3 ) << std::setfill( ' ' );
        std::cout << mat( mmloc.second ) << " @ " << mmloc.second << std::endl;
    }
    std::cout << std::endl;

    // Column-wise extrema.
    for ( int col = 0; col < size.width; ++col )
    {
        std::pair< cv::Point, cv::Point > mmloc = minMaxLocCol( mat, col );

        std::cout << "Col " << col;
        std::cout << " min = " << std::setw( 3 ) << std::setfill( ' ' );
        std::cout << mat( mmloc.first )  << " @ " << mmloc.first;
        std::cout << " max = " << std::setw( 3 ) << std::setfill( ' ' );
        std::cout << mat( mmloc.second ) << " @ " << mmloc.second << std::endl;
    }

    return 0;
}

Maybe my proposed solution isn't best way (which you explicitly asked for), but it's a simple one.

Upvotes: 0

rwfeather
rwfeather

Reputation: 101

While this may be more complicated than you would like, it could be possible to subclass the iterator base class. There is a simple example there. You would redefine the operators to traverse the column instead. That way, you could pass them into min_element just like the row iterators.

Upvotes: 0

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70999

As the elements of your structure are going to be changing, the best option you have is to implement Range minimum query(RMQ) using binary index trees(a.k.a Fenwick trees). I suggest you keep one such tree for each row and for each column. You can also implement a tree of such trees if you want to support a query for a submatrix of the original matrix. The solution I propose will require O(N * M ) additional memory where N and M are the dimensions of the matrix. It will also support query and update with complexity O(log(N) + log(M)).

Upvotes: 2

Related Questions