How to minimize the consuming time of LOG funcation

[Sean_usc]

we have an U8 array, whose size is 4K*48 . the value of each array element is between 0 to 256. we need to calculate by using the following formula:

Result=20LOG( x(i,j)/MAX(x)). If we use the normal LOG function, it is too time consuming. Is there any fast way to do this calculation. We hope the calculation time should be less than 1ms.

Thanks

xiaochex@usc.edu

[Sean_usc]

a look up table might be a solution. How to build a look up table for LOG function? thanks

Sean

[Kevin_Price]

I tried to whip up a lookup-table based solution to check this out, but it still took about 6-7 msec on a 2.8 GHz P4. Then I started thinking about it more...

You're trying to do an awful lot of computation in 1 msec. You've got almost 200k values to access and perform some calculations on, not to mention the comparisons needed to identify the max value. You're talking about a nearly 200 MHz element-processing rate. And for each element you process you need to perform:

1. memory access to retrieve element value
2. comparison operation to determine if element is MAX value (probably done in a separate loop prior to the loop that does the next steps)
3. memory access to retrieve the value
4. memory access when using the value as an index into a lookup table
5. floating-point subtraction of LOG(MAX(x)). This is because LOG(a/b) = LOG(a) - LOG(b) and subtraction will be faster than division.
6. floating-point multiplication by 20
7. memory access to push the value into the floating point output array

I'm inclined to wonder if even hand-optimized assembly can do this. Perhaps (I'm no expert) -- but it probably wouldn't be trivial.

Can you describe your app more? Do you really need to process 200k values every msec in real-time? Or could you live with streaming to disk and then post-processing at the end?

-Kevin P.

[Sean_usc]

Thank you very much!

in fact, i am trying to do high frame rate ultrasound imaging. the final goal is to obtain 150 frames/sec.

each frame has at least 1K*100 data or more. In our program, first we need to transfer those data from AD card to computer memory, then do the log compression and display it. Even though, maybe our eyes can not see the difference between 100frame/s and 30 frames/s, my boss still wants to do it.

Considering about the data transfer time and other stuffs. we hope the log compression time is around 5ms inintially. then we will do further. I am sure that your code must be very beautiful. if it is possible, could you send me your code? I do appreciate.

Sean

xiaochex@usc.edu

[altenbach]

I agree that even with a fast lookup table, you won't get into the low ms, but you probably can get close.

What should be the data type of the output (SGL, DBL, U8, U16, U32)?

Since the lookup table only needs MAX(x) number of elements and x is U8, the lookup table is size 256 in the worst case.

I would proceed as follows:

(1) Use "Array max" on the 2D array to get MAX(x) (this alone takes about 1ms).
(2) In a FOR loop generate the lookup table for x=0...max(x) using the entire given formula: 20log(i/Max(x), where i is the loop iteration terminal. Autoindex the result and you'll get a max(x)+1 sized 1D array containing all possible answers. e.g. element #5 contains the result for x=5, etc.
(2) Now place "index" array inside two FOR loops with your image set to autoindex and wired to the array index. Wire the lookup table array of the desired representation to the array input of index array (disable autoindexing).
(4) wire the element output of index array out of your two FOR loop. The resulting array will contain your adjusted image.

[altenbach]

OK, I spent a few minutes to implement two primitive version (LabVIEW 7.1) of the lookup table solution to give you some ideas. I don't claim these are optimized, see if you can speed them up :).

The timing for the computation is shown, but remember that the display operation takes additional time!

(1) If the output array is also U8, it is fastest to re-use the array for the output. Since all your transformed values are negative, I multiply by -20 instead of 20 to make them positive. (see ImageProcess01_U8.vi). Alternatively, you could just add 48 to make the output positive. Pick whatever is more appropriate.

(2) If the representation of the output array is different (e.g. SGL), you can use the method described in my other post (see ImageProcess_SGL).

(3) It might also be pretty fast to display it as a paletted image (8 bit pixmap) and then simply transform the palette. (I am not very familiar with the image tools so no example).

(There are also some loose ends with your formula that need to be addressed, e.g. if x=0, the transform is undefined.)

[Kevin_Price]

Sean,

The code snapshot I'm attaching is extremely similar to that posted by altenbach. There are just a few comments I'd like to make that may help you get more speed, some at the expense of accuracy and others at the expense of "purity" (not using an actual decibel measurement).

1. You'll want to avoid division in an inner loop. So rewrite your equation as the equivalent 20*LOG10(x(i,j)) - 20*LOG10(MAX(x))
The entire first term, including the multiplication, can be stored as the lookup value. The second term is calculated just once after find the MAX value. The innermost loop will then just perform a lookup operation and a single subtraction.

2. How important is the actual MAX value? Can you ignore it altogther? If not, here are a couple ways that may help you speed up a MAX search at the expense of some accuracy.
2A. Make your own MAX function that terminates as soon as you find a value "close enough" to 255, the max possible U8 value.
2B. You may be able to take a small random sampling of your ~200k of frame data and use the MAX of the sample as an estimate of MAX for the frame. Combined with 2A, you may often get good results with just hundreds of elements rather than the entire 200k. You'd probably need to predefine the random numbers as another lookup table though since you wouldn't want to calculate them live.

3. A log is a log is a log. Your original equation measures an amplitude ratio and expresses it in decibels. If you can switch to a different base for your LOG function and use another multiplier, you can get more resolution in your lookup table (assuming the table is a set of U8's or other integer values).
The method to make the table is to perform the LOG calculation and multiplication in floating point first, then convert to U8. With decibels, your LOG10 values will range from 0 to 2.4 After multiplying by 20 and converting to U8, they'll range from 0 to 48.
But why not use more of the available bits to define your LOG lookup table? For example, if you perform LOG2 you can get values from 0 to 7.994 If you then multiply by 32 and convert to U8 you'll use the entire range 0 to 255. Using base 2 and powers of 2 may be advantageous if you can write the routine in C or assembly. In my sample, I stuck with base 10 but multiplied by 100 rather than 20 to make better use of the possible U8 range.

4. As altenbach mentioned, your ratio is always <=1 so the LOG of it will always be <=0. This may actually work out ok for you. Under U8 subtraction, a result that "wants" to be -1 will be represented as 255. Intensity values that are close to max would "want" to be small negative values, but would actually turn out as values close to 255.
WARNING: If you use my idea 2A or 2B, you may end up with individual elements that are actually larger than your approx or estimated MAX. Even if you don't, there are still some elements that will be equal to MAX. These subtractions will be small numbers >= 0, which makes them appear more like elements with very low intensity. You would need to deal with this issue carefully. In my sample, I found the actual MAX and simply incremented the value for LOG(MAX(x)) so it would always be larger than any actual value in the frame.