title: Fast transposition of an image and Sobel Filter optimization in C (SIMD)
body: <p>I want to implement a really (really) fast <a href="http://en.wikipedia.org/wiki/Sobel_operator">Sobel operator</a> for a ray-tracer a friend of me and I wrote (sources can be found <a href="http://sourceforge.net/projects/thedreammachine/">here</a>). What follows is what I figure out so far...</p>
  
  <p>First, let assume the image is a grey-scale picture store line by line in an 8 bits unsigned integers array.</p>
  
  <p>To write a real Sobel filter, I need to compute Gx and Gy for each pixel. Each of these numbers are computed thanks to 6 pixels next to the origin. But SIMD instruction allow me to deal with 16 or even 32 (AVX) pixels. Hopefully, the kernel of the operator has some nice property, so that I can compute Gy by :</p>
  
  <ul>
  <li>subtracting each i and i+2 rows and store the result in a i+1 row of some other picture (array)</li>
  <li>adding the i, twice of the i+1 and the i+2 columns give the i+1 column of the final picture</li>
  </ul>
  
  <p>I would do the same (but transposed) to compute Gx then add the two pictures.</p>
  
  <p>Some notes : </p>
  
  <ul>
  <li>I don't care about memory allocation since everything will be allocated at the beginning.</li>
  <li>I can deal with the overflow and sign problem dividing the values by four (thanks to _mm_srli_epi8)
  <code>(uint8_t >> 2 - uint8_t >> 2) = int7_t //really store as int8_t<br/> 
  int7_t + uint8_t &lt;&lt; 1 >> 2 + int7_t = uint8_t <br/> //some precision is lost but I don't care</code></li>
  </ul>
  
  <p>The real problem I'm facing is to go from the rows to the columns. Since I couldn't load the picture in the SIMD register otherwise. I must flip the image three time at least isn't it ?</p>
  
  <p>Once the original picture. Then I can compute the first step for Gx and Gy and then flip the resulting pictures to compute the second step.</p>
  
  <p>So, here is my questions :</p>
  
  <ul>
  <li>Is this kind of implementation a good idea ?</li>
  <li>Is there a way to transpose an array faster than the dumb algorithm ? (I don't think so)</li>
  <li>Where will be the bottlenecks ? (any guess ? :P) </li>
  </ul>