[prev in list] [next in list] [prev in thread] [next in thread] 

List:       schrodinger-devel
Subject:    Re: [Schrodinger-devel] Possible optimsation of the sort_u8() into schrofilter.c
From:       salsaman <salsaman () gmail ! com>
Date:       2012-05-28 9:07:03
Message-ID: CAA74=eXXcHHmuoQkt8nLh2TB4ah_1_MRzroHU8byAZof7-vQBw () mail ! gmail ! com
[Download RAW message or body]

If you are trying to find the median of a set of values, the fastest
method is probably the median of medians algorithm:

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm


which can be done in O(n) time. As opposed to bubble sort which is
worst case O(n**2) time.


Salsaman.


http://lives.sourceforge.net
https://www.ohloh.net/accounts/salsaman


On Fri, May 25, 2012 at 7:51 PM,  <yann.lepetitcorps@free.fr> wrote:
> Selon yann.lepetitcorps@free.fr:
> 
> > > > I see that the sort_u8() func into schrofilter.c  use a basic bubble
> > > > sort scheme
> > > > => is it volontary ?
> > > > ...
> > 
> > > This is only used in the center-weighted median code, which must
> > > be specifically enabled.  CWM is particularly bad at filtering out
> > > noise in video, especially the kind of noise that make video encoders
> > > less efficient.
> > 
> > 
> > Where is the source file that store the  center-weighted median code ?
> 
> I have found a C routine that is very very speed for to find the median value at
> http://ndevilla.free.fr/median/median/index.html (quickselect.c)
> 
> => If it's only for to find the median value, it's a lot more faster that to
> make a bubble sort of the **entire** array for only to can read the median value
> that is in the middle of the array ...
> 
> 
> > > Sorting neighboring pixel values is a particularly dumb method of
> > > doing a CWM filter (when all you want is the median), so fixing the
> > > dumb method of sorting is not really going to make the code good.
> > > The correct way to do CWM is roughly min(max(center,min(neighbors),
> > > max(neighbors)), at least for weight=4.  (IIRC, this is from memory)
> > 
> > ???
> > 
> > lapatoucompri :(
> > 
> > What is the signication of "min(max(center,min(neighbors), max(neighbors)),
> > at
> > least for weight 4" ???
> > 
> > If I have understand, this is something like sorting color fragments
> > intensities for to find the median and min/max colors/intensities of a zone
> > for
> > to apply on it a more adapted denoising  ?
> 
> 
> Now, I can very speedly found the min/max and median value
> 
> But I always don't understand what is the signification of
> "min(max(center,min(neighbors),max(neighbors)), at least for weight=4" :(
> 
> Perhaps because that it seem to lack a parenthesis somewhere :)
> 
> 
> > > I'm only going to apply patches to this code to a) remove it, or b)
> > > rewrite it in Orc.  The latter clearly requires using something
> > > SIMDable for median filtering.  Interestingly, bubble sort can be
> > > implemented in SIMD, which may provide insight into why it was
> > > originally chosen.  (But my guess is that the reason why it was
> > > chosen is that it took <5 minutes to implement.)
> 
> The quickselect.c code is **really very very speed** for to find the median
> value
> 
> I have benchmark it with various implementation of the bubble sort, qsort,
> mergesort  and a lot of others sorting algorithms
> => the quickselect.c code seem to be the fastest for to find the median value
> 
> > I take a look about how to make median filtering / denoising into a SIMD way
> > and
> > come back when I have find enough interesting infos on the subject
> 
> I have begin to study about the aggregation into a single byte of the hightest
> bit of each 8 byte generated with PCMPGTs, where this aggregated byte can be
> used as index into a cascade of arrays for to can automatically find the index
> of the median pixel if we have the same type of byte/index computed for the
> heights pixels around the selected pixel on a 3x3 array
> (so of course, this compute only the index of the median on the local 3x3 array,
> not for the entire picture)
> => I think to study this idea until the end of the next week, because perhaps
> that this can to give something good (but perhaps not ...)
> 
> 
> @+
> Yannoo
> 
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Schrodinger-devel mailing list
> Schrodinger-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/schrodinger-devel

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and 
threat landscape has changed and how IT managers can respond. Discussions 
will include endpoint security, mobile security and the latest in malware 
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Schrodinger-devel mailing list
Schrodinger-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/schrodinger-devel


[prev in list] [next in list] [prev in thread] [next in thread]