4 ms·

How does max pool deal with this? It seems similar where you rank all the pixel values and take the max (rather than median). The problem with ties still occurs

• GistNoesis 7y ago
  Good idea. I've looked at tensorflow approach for backward max pool [0] They seem to be using a naive algorithm, scanning over the pool area and picking the first index whose value match the pooled max, so the bigger the kernel radius the slower it gets. They deal with the tie problem by taking the index of first value that match the max value (with float32 that's an edge case that should almost never happen so it's a fine speedup). My guess is it's probably possible to apply this constant time algorithm doing the same sort of approximation for the ties, but you also need to enrich the histograms so that in addition to the count it also store and update the last index associated with the count. I also just noticed that the constant time algorithm hasn't been run for float values. It's not really a problem though because we can use some order preserving bit-tricks to convert float32 to UInt32 and then truncate to UInt16 [1]. [0] https://github.com/tensorflow/tensorflow/blob/master/tensorflow/core/kernels/maxpooling_op_gpu.cu.cc#L337 https://github.com/tensorflow/tensorflow/blob/master/tensorf... [1] https://fgiesen.wordpress.com/2013/01/21/order-preserving-bijections/ https://fgiesen.wordpress.com/2013/01/21/order-preserving-bi...