From: Lubomir Bourdev (lbourdev_at_[hidden])
Date: 2007-04-29 12:06:27
On 4/29/07 12:41 AM, "John Femiani" <JOHN.FEMIANI_at_[hidden]> wrote:
> 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>
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
>> 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
> 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
> 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
I just posted my reply to the sourceforge thread:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk