May 182013
 

My last post was about creating a tiny just in time (JIT) compiler for mathematical expressions. This new project builds on that work. JITted mathematical expressions were the first problem to solve on the way to making a toy programming language for image processing. I have called this new project Pixslam, the sourcode and a decent amount of documentation are on GitHub.

Edge detection demo

Edge detection with Pixslam

From Expressions to Images

The first step was to extended the expression evaluator of JitCalc to evaluate its function for all the pixels in some input images and store the results in some output image. This was achieved by adding:

  • Image reading and writing for reasonable image formats (PNG, jpeg) using the stb_image library.
  • Putting the original expression evaluation code into a “loop over the image” and storing the result into an output image.
  • Tweaking the symbol handler to look up into the current pixel (calculated by the above loop) of each input image.

Since most of the code generation snippets I showed last time were very simple let’s take a look at the different methods from JitCalc and Pixslam. Feel free skip the code and scroll down to the nice images below (there is even a GIF!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Generate method from JitCalc.
// Pretty much just the boilerplate for an AsmJit function call and an "eval"
FuncPtrType generate(const Cell &c){
    compiler.newFunc(AsmJit::kX86FuncConvDefault, 
                     AsmJit::FuncBuilder1<double, const double *>());
    AsmJit::XmmVar retVar = eval(c);
    compiler.ret(retVar);
    compiler.endFunc();
    return reinterpret_cast<FuncPtrType>(compiler.make());
}
 
// Generate method from Pixslam.
// Deals with image arguments, settings some useful symbols and looping over the image.
// The "AsmJit::XmmVar retVar = eval(c);" remains though!
JitImageFunction::FuncPtrType JitImageFunction::generate(const Cell &c){
    using namespace AsmJit;
    compiler.newFunc(AsmJit::kX86FuncConvDefault, 
                     AsmJit::FuncBuilder5<void, Arguments, size_t, size_t, size_t, double *>());
 
    // Bind input array of image pointers to AsmJit vars.
    GpVar pargv = compiler.getGpArg(0);
    for(size_t i = 0; i < argNameToIndex.size(); ++i){
        argv.push_back(compiler.newGpVar());
        compiler.mov(argv.back(), ptr(pargv, i*sizeof(double)));
    }
 
    // Setup some useful constants.
    zero = compiler.newXmmVar();
    one = compiler.newXmmVar();
    SetXmmVar(compiler, zero, 0.0);
    SetXmmVar(compiler, one, 1.0);
 
    w = compiler.getGpArg(1);
    h = compiler.getGpArg(2);
    stride = compiler.getGpArg(3);
    out = compiler.getGpArg(4);
 
    // Convert above into doubles so they can be bound to symbols.
    wd = compiler.newXmmVar();
    hd = compiler.newXmmVar();
    compiler.cvtsi2sd(wd, w);
    compiler.cvtsi2sd(hd, h);
    symbols["w"] = wd;
    symbols["h"] = hd;
 
    // Perpare loop vars
    n = compiler.newGpVar();
    compiler.mov(n, w);
    compiler.imul(n, h);
    currentIndex = compiler.newGpVar();
    compiler.mov(currentIndex, imm(0));
 
    currentI = compiler.newGpVar();
    currentJ = compiler.newGpVar();
    compiler.mov(currentI, imm(0));
    compiler.mov(currentJ, imm(0));
 
    // for i = 0..h
    // for j = 0..w
    Label startLoop(compiler.newLabel());
    compiler.bind(startLoop);
    {
        compiler.mov(currentIndex, currentI);
        compiler.imul(currentIndex, stride);
        compiler.add(currentIndex, currentJ);
        // im(i,j) = f(x)
        AsmJit::XmmVar retVar = eval(c);
        compiler.movq(ptr(out, currentIndex, kScale8Times), retVar);
 
    }
    compiler.add(currentJ, imm(1));
    compiler.cmp(currentJ, w);
    compiler.jne(startLoop);
    compiler.mov(currentJ, imm(0));
    compiler.add(currentI, imm(1));
    compiler.cmp(currentI, h);
    compiler.jne(startLoop);
 
    compiler.endFunc();
    return reinterpret_cast<FuncPtrType>(compiler.make());
}

The results of this are fairly dull, but it is an important stepping stone. With this in place we can do the following:

1
2
3
4
5
6
7
; Add two images together.
; Command line: pixslam compose.psm lena.png duck.png compose_out.png
((A B)
     ( * 0.5 ; normalise back to [0,1]
        ( + A B)
     )
)

First Pixslam Example

Adding two images together. Input images on top row, bottom is the result.

Accessing Our Images

Of course this alone would not allow for much image processing – we need to be able to perform operations using more than one pixel value from input images at once for true image processing. In many image processing algorithms we want to look at a neighborhood of pixels around the one we are processing. Relative indexing helps us implement these kinds of algorithms neatly.

In Pixslam “realive indexing” is the following: processing pixel \((i,j)\) then (A y x) evaluates to pixel \((i+y, j+x)\). Relative indexing was added to the expression evaluator framework simply by having the function handler run a special case when an argument name is used as a symbol. Note we are using row/column indexing – this is actually fairy common when dealing with images (for example Matlab, OpenCV). Once we have this we can do some standard image processing – like a simple box blur.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
; Normalized 3x3 box filter.
; That is: replace each pixel with the average value of the pixels in 3x3 neighbourhood 
((A)
    ( /
        (
            + 
            (A -1 -1)
            (A -1 0)
            (A -1 1)
            (A 0 -1)
            (A 0 0)
            (A 0 1)
            (A 1 -1)
            (A 1 0)
            (A 1 1)
        )
        9
    )
)

Lenna blur demo

Top: Original, Bottom: Box Blurred

Absolute indexing is important too. It allows us to perform “global” operations like rotating an image. Pixslam provides the following syntax for absolute indexing: (@A i j) evaluates to the value of the the pixel at row \(i\) and column \(j\) in image \(A\). The symbols width and height are bound to the width and height of the image. Again implementing this was a case of extending the function handler and special variables \(i\) and \(j\) were dealt with by extending the symbol handle.

1
2
3
; Flip image vertically.
; Demos absolute indexing operator.
((A) (@A (- height i) j))
Flipped Duck

The results of the flip vertical example!

A more interesting use of absolute indexing is to create images from mathematical expressions on the indices only. In the example below Metaballs are drawn, the input image is only used to specify the size of the result. Have a look at the examples directory to see how this is done.

Metaballs

Metaballs demo

More Examples

Now sprinkle in some extra operations: min, max and comparisons. We are now ready to have some fun.

Metaballs with some fancy thresholding.

Metaballs with some fancy thresholding.

Erosion demo

Erosion with a 5×5 kernel. Using the “min” operator.

If we allow Pixslam to operate recursively on the same image it is Turing complete. Proof: Here’s Conway’s game of life in Pixslam!

Game of life in Pixslam

Game of life in Pixslam. See the examples directory on the GitHub for more details!

Almost everything above is described in more detail in the project readme. In addition all the images above are automatically generated during the build process – take a look at the examples directory.

 Posted by at 9:58 am

  One Response to “Just In Time Image Processing: Pixslam”

  1. Splendid stuff, mate!

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)