Re: [boost] [gil] Ideas to make my extension more generic?

From: Lubomir Bourdev (lbourdev_at_[hidden])
Date: 2007-04-29 12:06:27

John,

On 4/29/07 12:41 AM, "John Femiani" <JOHN.FEMIANI_at_[hidden]> wrote:
> 
> Lubomir, 
> Regarding your comment:
> 
>> I haven't thought much about this, but this is
>> k-order statistic (in an array of numbers, find
>> the K-th smallest one). There is an algorithm to do
>> this in O(N). This would be rather useful, perhaps
>> someone should put it in Boost?
> 
> It is part of the stl already: std::nth_element in the <algorithm>
> header.

My understanding is that std::nth_element partially sorts the range,
suggesting O(NlogN) running time. There are algorithms to return the n-th
smallest element in an unordered list in O(N).

> 
>> My suggestion is to ignore the fact that there are multiple channels
> in a
>> pixel and just white the algorithm to operate on a grayscale image. It
> is
>> then trivial to extend it by using nth_channel_view.
> 
> But nth_channel_view does not work for heterogeneous pixels, runtime
> specification of the channel requires that all channels be of the same
> type. As you said in an earlier post 'n' means runtime, 'k' means
> compile time. 

True. But it should be easy to create kth_channel_view, in which the channel
index is specified at compile time. And this should work for heterogeneous
pixels.

> This is exactly the type of issue I have been having when I try to write
> code that is generic enough to apply to heterogeneous pixels.
> Unfortunately I have started writing code that simply precludes
> heterogeneous pixels (using nth_channel_view or operator[] to loop
> through channels) because I was spending too much time trying to write
> functors for every operation I needed to do on an image.

I agree it is hard.

> I posted a message on the sourceforge discussion and I will summarize it
> here:
> 
> I saw the recent posting on fixed point (or scaled value) types in the
> works by Phil Endecott, and apparently another version by Maurizio
> Vitale, and I was wondering whether GIL folks thought this could be
> useful for describing individual samples in gil.  Instead of using
> bits8, one could define a pixel in terms of scaled<uint8_t, 255>, or
> scaled<uint16_t, 255>, etc. Operations on the pixels can deduce the
> return type for each channel using the methods applied by the fixed
> point authors.  This way each channel, regardless of its type, should
> produce expected results for an expression without all the tweaking
> required when dealing with integer types directly. Any operation on a
> pixel could be applied to each of its channels, like in valarray, and
> code that uses operations on pixels is automatically generic wrt
> heterogeneous layouts as long as all channels have similar semantic
> meanings.
>     
I just posted my reply to the sourceforge thread:
http://sourceforge.net/forum/message.php?msg_id=4286563

To summarize it, nothing stops you from using Phil's fixed point numbers as
GIL channels. However, I don't think there is a generic way to perform
arithmetic operations on arbitrary types with the same performance as
hand-writing the operation for a given type. In my opinion, this is best
handled by providing a set of atomic operations that have overloads or
specializations that are tuned to the specific types involved.

Lubomir