Find n greatest values in a Matrix

[kurt_come]

Hi,

off topic:

   I'm developing Hough Transform by Labview, and actually I'm working with matrix vote.

end off topic.

In a matrix with POSITIVE VALUES, I have to find the coordinates of the 5 greatest values

( example: Matrix=[1 , 2 , 3  ; 4 , 5 , 6 ; 7 , 8 , 9 ]        Matrix [ 3x3 ]

Then ,  5 , 6 , 7 , 8 , 9 are the greatest values, and

their coordinates are: 5 ----> 1,1    6----> 1,2   7--->2,0........................................)

I solve this problem with a simple approach (the program work):

I use the module Array Max & Min, and when I find the max value and its coordinates, I overwrite the value with ZERO (the less value) .

 I repeat this operation for five times on the overwrited matrix, so I find the coordinates of five points.

IMPORTANT: I have to find 5 values in a matrix 200x200.

What do you think about this approach?

Have you got a more efficient?

Thank you

Labview 7.1

Message Edited by kurt_come on 12-17-2005 11:45 AM

[altenbach]

This approach sounds OK. I don't think you can do it significantly more efficient. If you are worried about performance, code a few alternative solutions, then race them against each other. 😮

One modification. You should replace the current value by [-Inf], not zero, else the algorithm will fail e.g. if your array contains mostly negative numbers. 😉 Sure, your array is all positive at the moment, but it is always better to make the code more universal so you (1) don't need to document limitations on the input and (2) don't need to modify it in the future.

You may also want to think about handling of "pathological" situations. What should the output be if all elements are identical? What if there are only 3 highest elements, the rest are zero? etc. What should happen if certain values are NaN?

[altenbach]

Size 200x200 is pretty small. I takes about 3ms to find the top 5 on my computer (see attached example, LabVIEW 7.1).

[bogdani]

I must agree that  this simple solution is the best, if you don't need to chceck other parameters.

I thought about it, but I didn't find anythink better.

bogdani

[WNM]

It is possible to squeeze a bit more speed out of it at the cost of more complexity. See the attached, revised VI. I guess it depends on what is most important to you. Speed or ease of understanding the block diagram.

[altenbach]

Warren,

Very nice implementation! Yes, I thought something like this should be faster, because each element is "touched" only once, and yes, it is about 5x faster as expected. (each arrayMinMax need to look at each array element, thus each element will be checked 5x in the simple code). It is worth to implement for large arrays and if you are concered about speed, especially if the code executed repetitively.

Two things:

1. Make sure to "Sequence" the two sequence structures, else they run concurrently and the timings are meaningless. See the marked blue wire in v3. (With the blue wire in place, your code seems even faster (try with a 2000x2000 array ;)).
2. The sorting can be simplified. Remember that an array of clusters is sorted by cluster element zero. 😄  

[kurt_come]

Thanks at all.

Sorry for my delay, but my pc doesn't work.

Kurt_come

[Dynamik]

Hi Altenbach,

      Found a subtle bug in your solution.  The Max/Min function is finding the minimum value before the replacement, but the new threshold should be the lowest value in the new array.

That said, my first/only shot at this was MANY times slower than yours!

Cheers from the cheap-seats.

Message Edited by Dynamik on 01-03-2006 05:15 AM

Message Edited by Dynamik on 01-03-2006 05:16 AM

[altenbach]

---

@Dynamik wrote:

Hi Altenbach,
      Found a subtle bug in your solution.  The Max/Min function is finding the minimum value before the replacement, but the new threshold should be the lowest value in the new array.

---

Hmm, you're probably talking about Warren's Code 😉 (I just cleaned up the sorting).

I'll have to study this a bit. Do you have a set of artificial input data where it changes the outcome?

[WNM]

---

@Dynamik wrote:

      Found a subtle bug in your solution.  The Max/Min function is finding the minimum value before the replacement, but the new threshold should be the lowest value in the new array.

---

Good catch! You are correct. As it was, subsequent comparisons (whether or not the TRUE case is executed) would be made against a value that was no longer in the Top5 results array. Whether or not it would cause incorrect results would depend on the values and their ordering within the input array. I have modified the VI so that this should no longer be a problem.