Protected: Wifi / bluetooth RSSI signal strength to distance

This content is password protected. To view it please enter your password below:

Advertisements

Laplace Transform – visualized

The Laplace Transform is a particular tool that is used in mathematics, science, engineering and so on.  There are many books, web pages, and so on about it.

And yet I cannot find a single decent visualization of it!  Not a single person that I can find appears to have tried to actually visualize what it is doing.  There are plenty of animations for the Fourier Transform like:

fourier

But nothing for Laplace Transform that I can find.

So, I will attempt to fill that gap.

What is the Laplace Transform?

It’s a way to represent a function that is 0 for time < 0 (typically) as a sum of many waves that look more like:

laplace

Graph of e^t cos(10t)

Note that what I just said isn’t entirely true, because there’s an imaginary component here too, and we’re actually integrating.  So take this as a crude idea just to get started, and let’s move onto the math to get a better idea:

Math

The goal of this is to visualize how the Laplace Transform works:

\displaystyle\mathscr{L}\{f(t)\}=F(s)

To do this, we need to look at the definition of the inverse Laplace Transform:

\displaystyle f(t) = \mathscr{L}^{-1}\{F(s)\}=\frac{1}{2\pi j}\int^{c+j\infty}_{c-j\infty} F(s)e^{st}\mathrm{d}s

While pretty, it’s not so nice to work with, so let’s make the substitution:

\displaystyle s := c+jr

so that our new limits are just \infty to -\infty, and \mathrm{d}s/\mathrm{d}r = j giving:

\displaystyle f(t) = \mathscr{L}^{-1}\{F(s)\}=\frac{1}{2\pi j}\int^{\infty}_{-\infty} F(c+jr)e^{(c+jr)t}j\mathrm{d}r

\displaystyle = \frac{1}{2\pi}\int^{\infty}_{-\infty} F(c+jr)e^{(c+jr)t}\mathrm{d}r

Which we will now approximate as:

\displaystyle \approx \frac{1}{2\pi}\sum^{n}_{i=-n} F(c+jr_i)e^{(c+jr_i)t}\Delta r_i

Code

The code turned out to be a bit too large for a blog post, so I’ve put it here:

https://github.com/johnflux/laplace-transform-visualized/blob/master/Laplace%20Transform.ipynb

Results

Note: The graphs say “Next frequency to add: … where s = c+rj“, but really it should be “Next two frequencies to add: … where s = c\pm rj” since we are adding two frequencies at a time, in such a way that their imaginary parts cancel out, allowing us to keep everything real in the plots.  I fixed this comment in the code, but didn’t want to rerender all the videos.

A cubic polynomial:

A cosine wave:

Now a square wave.  This has infinities going to infinity, so it’s not technically possible to plot.  But I tried anyway, and it seems to visually work:

 

Gibbs Phenomenon

Note the overshoot ‘ringing’ at the corners in the square wave. This is the Gibbs phenomenon and occurs in Fourier Transforms as well. See that link for more information.

 

Now some that it absolutely can’t handle, like: \delta(t).  (A function that is 0 everywhere, except a sharp peak at exactly time = 0).  In the S domain, this is a constant, meaning that we never converge.  But visually it’s still cool.

Note that this never ‘settles down’ (converges) because the frequency is constantly increasing while the magnitude remains constant.

There is visual ‘aliasing’ (like how a wheel can appear to go backwards as its speed increases). This is not “real” – it is an artifact of trying to render high frequency waves. If we rendered (and played back) the video at a higher resolution, the effect would disappear.

At the very end, it appears as if the wave is just about to converge. This is not a coincidence and it isn’t real. It happens because the frequency of the waves becomes too high so that we just don’t see them, making the line appear to go smooth, when in reality the waves are just too close together to see.

The code is automatically calculating this point and setting our time step such that it only breaksdown at the very end of the video. If make the timestep smaller, this effect would disappear.

And a simple step function:

A sawtooth:

Compiler is ignoring my C code!

Sometimes you come across a weird bug where the output seems to be completely impossible.  And it’s extremely hard to debug or search on google for, if you don’t know about this:

If your code has Undefined Behaviour, the compiler is allowed to assume it won’t happen, and can ‘optimize out’ chunks of your code.

Here’s a code snippet in a real bug I found yesterday:

 

#define FOO_SIZE 10
int foo2[FOO_SIZE];
...
int n=0;
do {
    p->foo[n] = foo2[n];
    n++;
} while( (foo2[n] != 0) && (n < FOO_SIZE) );
printk("n is %d\n", n);

 

 

This printed out:

   n is 165

and the system crashed.

But how can n become larger than FOO_SIZE=10 ?  Because the compiler ‘optimized’ away the check.  Here’s the asm:

} while( (foo2[n] != 0) && (n < FOO_SIZE) );
   21a14:       f813 2f01       ldrb.w  r2, [r3, #1]!
   21a18:       2a00            cmp     r2, #0
   21a1a:       d1f8            bne.n   21a0e <NV_Get+0x82>
   21a1c:       e7ca            b.n     219b4 <NV_Get+0x28>

What we are seeing here is that the “n < FOO_SIZE”  check has been completely removed by the compiler.  Why?

Because in the check, if n == FOO_SIZE, we would be checking if:  foo2[FOO_SIZE] != 0.  But this is out of bounds for foo.  The compiler knows that this is out of bounds, and so knows that this is undefined behaviour.  But the compiler is allowed to assume that undefined behaviour doesn’t happen, and so it assumes that n can NEVER be >= FOO_SIZE.  Thus it can remove the n < FOO_SIZE check.

This can be fixed by switching the order of the && like:

} while( (n < FOO_SIZE) && (foo2[n] != 0) );

Or, by checking n-1 instead  (which is slightly different behaviour, but good enough for me.  I was changing a lot of code with this bug.)

} while( (foo2[n-1] != 0) && (n < FOO_SIZE) );
   21a26:       7809            ldrb    r1, [r1, #0]
   21a28:       2900            cmp     r1, #0
   21a2a:       d0c3            beq.n   219b4 <NV_Get+0x28>
   21a2c:       429a            cmp     r2, r3
   21a2e:       d1f5            bne.n   21a1c <NV_Get+0x90>
   21a30:       e7c0            b.n     219b4 <NV_Get+0x28>

Now we see the second comparison in the asm.

Calibrating Cameras

It is common to want to calibrate cameras for lens distortion.

 

First print out a standard chequerboard image, and take some photos of it from various angles. You can print out images, for example, here:

https://calib.io/pages/camera-calibration-pattern-generator

Here I assume these photos are in camera_cal/calibration*.jpg

Even if you ultimately want to calibrate the images from c++, python, javascript etc, the calibration itself can be done separately, in a more convenient language, producing a matrix that you can use pretty much anywhere.  In my case, I calibrate in a jypter notebook, but use the matrix in c++.

%matplotlib inline

import numpy as np
import cv2
import glob
import matplotlib.pyplot as plt
#%matplotlib qt

# prepare object points, like (0,0,0), (1,0,0), (2,0,0) ....,(6,5,0)
objp = np.zeros((6*9,3), np.float32)
objp[:,:2] = np.mgrid[0:9,0:6].T.reshape(-1,2)

# Arrays to store object points and image points from all the images.
objpoints = [] # 3d points in real world space
imgpoints = [] # 2d points in image plane.

# Make a list of calibration images
images = glob.glob('camera_cal/calibration*.jpg')

# Step through the list and search for chessboard corners
for fname in images:
img = cv2.imread(fname)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

# Find the chessboard corners
ret, corners = cv2.findChessboardCorners(gray, (9,6),None)

# If found, add object points, image points
if ret == True:
objpoints.append(objp)
imgpoints.append(corners)

# Draw and display the corners
img = cv2.drawChessboardCorners(img, (9,6), corners, ret)
plt.imshow(img)
plt.show()

ret, camera_undistort_matrix, camera_undistort_dist, rvecs, tvecs = cv2.calibrateCamera(objpoints, imgpoints, gray.shape[::-1], None, None)

fname = images[8]
img = cv2.imread(fname)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
ret, corners = cv2.findChessboardCorners(gray, (9,6),None)
print(ret)
img = cv2.drawChessboardCorners(img, (9,6), corners, ret)
dst = cv2.undistort(img, camera_undistort_matrix, camera_undistort_dist, None, camera_undistort_matrix)
img = np.concatenate((img, dst), axis=1)
plt.imshow(img)
cv2.imwrite("output_images/undistort_chessboard.png", img)
plt.show()

output_2_1

On the left is the original photo, and on the right is after applying the undistortion matrix warp.

import pickle
with open('camera_undistort_matrix.pkl', 'wb') as f:
pickle.dump((camera_undistort_matrix, camera_undistort_dist), f)
print(camera_undistort_matrix)
[[ 1.15777829e+03 0.00000000e+00 6.67113865e+02]
[ 0.00000000e+00 1.15282230e+03 3.86124659e+02]
[ 0.00000000e+00 0.00000000e+00 1.00000000e+00]]

 

img = cv2.imread("test_images/straight_lines1.jpg")
dst = cv2.undistort(img, camera_undistort_matrix, dist, None, camera_undistort_matrix)
img = np.concatenate((img,dst),axis=1)
img_rgb = cv2.cvtColor(np.asarray(img), cv2.COLOR_BGR2RGB)
plt.imshow(img_rgb)
cv2.imwrite("output_images/undistort_straight_lines1.png", img)
plt.show()

In the top left is the original image, in the top right is the undistorted image.  There is little difference to the eye, but the distortion lets us to now apply further distortions such as a perspective transform to provide an apparent “top-down view”.

It is also useful for applying other transforms key to stitching together images from multiple cameras.

 

 

My software in the wild

It was cool to see my VR software being used by the Dallas Cowboys:

To make this a bit more of a technical post, instead of purely a brag, we use a fair amount of machine learning behind the scenes. We look for similar items in the scene between cameras, to match up and align the seams:

We try to ‘autotune’ all the parameters. We adjust both the seam position and the camera warp to minimize the squared RGB pixel difference in the overlapped areas. This is actually quite computationally expensive, so we run this in CUDA to accelerate it.

Interactive dialogue on a webpage with React and Promises

Here’s the goal:

A way to make a webpage that lets you have an interactive dialogue by choosing options, like the old Interactive Fiction games.

The input file is very simple:

PRINT Hello!
WAIT ; This is a comment.  Wait for a key press or mouse click
PRINT I would like to ask you a question.
PRINTW Please don't be nervous. ; The 'W' means WAIT afterwards
PRINT Are you happy?
PRINT [0] Yes
PRINT [1] Not really...
CALL INPUTINT(0, 1)
IF RESULT == 0
    PRINTW I'M SO HAPPY THAT YOU'RE HAPPY!
ELSE
    PRINTW Then I am miserable 😦
ENDIF

The challenge is to make a webpage that could read that input, and run it, producing the interactive output shown in the video above.

Perhaps have a think if you don’t know how you would implement this. It is perhaps not so obvious.

Here is the approach that I decided to take.  Note that I only wanted to spend a weekend on this, so I took various shortcuts that I wouldn’t recommend if writing for production:

 

  1. Read in the input file in, using javascript with a Tokenizer and Parser.
  2. Output javascript using the above Parser, effectively making a transpiler from the input language to javascript.  Call outside javascript functions to ‘PRINT’ etc.
  3. Use ‘eval’ to run the resulting transpiled code.  Yes, eval is evil and this is a case of don’t do what I do.
  4. Use Promises, via async and await, to ‘pause’ and allow interaction.  Implement ‘WAIT’, ‘PRINTW’ ‘INPUTINT’ etc functions in javascript with Promises, so that they only resolve when the user has clicked, typed a number etc.
  5. Display output by just appending to a list, and displaying that list in React.

 

1. Read the file in, using Javascript with a Tokenizer and Parser

I used jison.  Although the README blurb says that it is for Context Free Grammars, because it is based on BISON which is likewise, it does actually support context.  This was vital because the input file language is not actually a context free grammar.

2. Output javascript using the above Parser, effectively making a transpiler from the input language to javascript

The correct way to do this would be to create an Abstract Syntax Tree, however I didn’t want to take too long on this, and instead simply outputted javascript code as a string.

3. Use ‘eval’ to run the resulting transpiled code.

This is very frowned upon, but this was a weekend project, so….

There is one trick that I used here.  I wrap the entire program to be ‘eval’ed like:

async function() { ..... }()

This allows the program code inside to use async and await to wait for input, and the eval is returning a Promise.  One minor point – when we use eval to evaluate this, we want to catch errors that the Promise throws, to provide clear feedback to the user if there are problems.  E.g.

try {
    await eval(program);
} catch(e) { ... }

4. Use Promises, via async and await, to ‘pause’ and allow interaction.  Implement ‘WAIT’, ‘PRINTW’ ‘INPUTINT’ etc functions in javascript with Promises, so that they only resolve when the user has clicked, typed a number etc.

I used two layers of callbacks, to implement a poor-man’s publish and subscribe system.

So the transpiler turns:

PRINTW Hello!

into:

printLine("Hello!");
await wait();

And the wait() function is implemented as:

async function wait() {
  await new Promise(
    resolve => cb_setClickListener(() => resolve())
  )
}

So we subscribe to a click listener via the callback ‘cb_setClickListener’ and then resolve the promise (and thus resume running the program) when the click is published.

Inside the React page, we now listen for clicks and publish it to the callback:

<App onclick={
  () => this.state.clickListener &&
        this.state.clickListener()
}>

And likewise for keypresses.  (Note, I’ve simplified the code here a bit.  In the real code, I pass the keypressed etc, so that INPUTINT can listen to a particular key).

5. Display output by just appending to a list, and displaying that list in React.

The ‘printLine’ function was implemented like:

function printLine(str) {
  const newLine = <div>{str}</div>;
  this.setState({displayLines: [...displayLines, newLine]})
}

One extra detail – if the string starts with a number in a bracket like: “[0] Yes”, then I output a link that publishes that number like:

<div className="clickable" onClick={
    () => this.state.keyPressedListener &&
          this.state.keyPressedListener(number)
  }
>{str}</div>

This way, when presented with a choice, the user can just click a link instead.   I maintain two separate output lists, so that I can disable the links once we are done with them.

Conclusion and notes

It worked very nicely! I further extended this to support variables, entering strings, showing pictures, and so on.

The language is actually a real language, but very niche and used almost exclusively by Japanese. It hasn’t seen much acceptance or use outside of Japan.