[<<][staapl][>>][..]
Fri Jul 11 11:26:04 CEST 2008

fold

Given a way to transform loop body specification (- (x 0) (x 1))
into an expanded loop, how to perform folds?

The Hough transform: for each (x,y) accumulate

   r = x cos t + y sin t

into an (r,t) plane.

Maybe it's best not to write this as a fold. The problem is that this
is not a fold of a simple symmetric binary operator, but of a piksel
and the state (r,t) accumulator. In pseudo:

    (fold (lambda (piksel accu x y)
            (+ accu (sino x y)))
          accu0
          image)

How to add this kind of operation?

Maybe formalize the grid version first: Sobel is

(fn (a)
  (let ((dx (- (a 0 0) (a 0 1)))
        (dy (- (a 0 0) (a 1 0))))
    (+ (* dx dx)
       (* dy dy))))

Aha! This is why sets are necessary for local binding of loop
pointers. It eliminates common subexpressions!

The 'let' form seems to work, however, current parsing messes up the
syntax by mis-identifying expressions as grids. This needs some kind
of parameter substitution.

'let' doesn't seem to work for expression statements. The code below
expands fine, but cgen.ss expands the 'let' incorrectly.


(src->code
 '(loop (= (grid result 0 0)
           (let ((dx (- (grid a 0 0) (grid a 0 1)))
                 (dy (- (grid a 0 0) (grid a 1 0))))
             (+ (* dx dx)
                (* dy dy))))))
=>

(statements
 (block
  (var int i)
  (for-head (= i 0) (< i (* 400 300)) (+= i 300))
  (block
   (vars
    (float* a_p0 (+ a (+ i (* 0 300))))
    (float* result_p0 (+ result (+ i (* 0 300))))
    (float* a_p1 (+ a (+ i (* 1 300)))))
   (statements
    (block
     (var int j)
     (for-head (= j 0) (< j 300) (+= j 1))
     (block
      (vars
       (float* a_p0_p1 (+ a_p0 (+ j 1)))
       (float* a_p0_p0 (+ a_p0 (+ j 0)))
       (float* result_p0_p0 (+ result_p0 (+ j 0)))
       (float* a_p1_p0 (+ a_p1 (+ j 0))))
      (loop
       (=
        (grid result_p0_p0)
        (let ((dx (- (grid a_p0_p0) (grid a_p0_p1)))
              (dy (- (grid a_p0_p0) (grid a_p1_p0))))
          (+ (* dx dx) (* dy dy)))))))))))

Seems like this is called let*
-> some small bug still. Ok, fixed.

It's working now:

(p '(loop (= (grid result 0 0)
             (let ((float dx (- (grid a 0 0) (grid a 0 1)))
                   (float dy (- (grid a 0 0) (grid a 1 0))))
               (+ (* dx dx)
                  (* dy dy))))))

=>

{
  int i;
  for (i = 0; i < (400 * 300); i += 300)
  {
    float* a_p0 = a + (i + (0 * 300));
    float* a_p1 = a + (i + (1 * 300));
    float* result_p0 = result + (i + (0 * 300));
    {
      int j;
      for (j = 0; j < 300; j += 1)
      {
        float* a_p1_p0 = a_p1 + (j + 0);
        float* a_p0_p1 = a_p0 + (j + 1);
        float* a_p0_p0 = a_p0 + (j + 0);
        float* result_p0_p0 = result_p0 + (j + 0);
        *(result_p0_p0) = ({
          float dx = (*(a_p0_p0) - *(a_p0_p1));
          float dy = (*(a_p0_p0) - *(a_p1_p0));
          ((dx * dx) + (dy * dy));
        });
      }
    }
  }
}


Now, how should i see this? It is an image comprehension with built-in
shift operators. What about the following specification syntax:


(for/grid (a result)  ;; grids
          ((i 100)    ;; dimensions, possibly inferred
           (j 100))
   (= (result 0 0)
      (let ((dx (- (a 0 0) (a 0 1)))
            (dy (- (a 0 0) (a 1 0))))
        (+ (* dx dx)
           (* dy dy))))))

where 'let' uses type inference from the values.

I'm not sure wether it's a good idea to have a grid iterator. Maybe
factoring in smaller for-loop like comprehensions is a better idea?

Sufficiently confused again..

The Hough loop + edge detection should look like this:

(for/grid (a)  ;; grids
  (let ((dx (- (a 0 0) (a 0 1)))
        (dy (- (a 0 0) (a 1 0))))
    (let ((sobel
           (+ (* dx dx)
              (* dy dy))))
          (if (> sobel 600)
              (accu! x y)))))

It doesn't look like this is going to work. Too experimental
still. Let's move to straight C.



[Reply][About]
[<<][staapl][>>][..]