top of page
Search
  • Writer's pictureDinesh Thogulua

Defeating Nazis and quantization noise

The year was 1943. RAF were conducting day-light bombing raids over Germany and German-occupied territories. The bombers were unaccompanied by fighters when they were above the target area, as the fighters didn't have a long enough range to go from England all the way into enemy territory and back. RAF was losing a lot of men and aircraft during the raids. The objective of the strategic bombing was to slow down the production of heavy guns, armoured vehicles and so on, along with cutting off communication lines (roads, bridges, railways). But this process was proving to be costly for RAF. They had to come up with a better way.



All factories need electricity and water. Often waterways are also used for transporting finished goods. Naturally many factories historically have been located near rivers. This was the case in Germany as well during the war. Germans had built a lot of dams along the Rhine river to supply hydro-electric power to the factories which were also located along the banks of Rhine. RAF came up with a great idea: "What if we just blow up the dams when they are full?" The resulting flooding would be catastrophic as it would flood the factories, and cut-off power to them. But bombing a dam is different from bombing factories: Factories presented large target footprints, but a dam is just a wall - if the bombs aren't accurate, they will either fall behind the dam wall in the water and in front of the dam wall, rendering them useless.


The British were working on a mechanical computer for calculating bomb trajectories. But there was a major problem: You see, mechanical computers had gears and cogs in those computers and their movements were known to be jerky, resulting in inaccurate calculations in the lab. But since they had no better option, and so RAF decided to put them anyway on their bombers and try them out. And surprise, surprise!, their calculations were very accurate once they were on the planes! This was ironic: Something that wasn't working well in perfect lab conditions was working great in the actual aircraft which is a vibrating platform. But therein lay the magic: The aircraft's vibrations were actually solving the accuracy problem.


Useful noise

Whenever you hear the word "noise", it always carries a negative connotation. Noise deteriorates the useful information and we typically don't want it. But there is one noise that is very useful indeed It is called "Dither" and is the subject of this post.


How would you represent a fractional number using only integers? One way is to pass a series of integers through an averaging operation. For example, you can represent 4.5 by averaging a series of integers, namely [4, 5]. And you want to represent 4.25, put a series [4, 4, 4, 5] or a variation of it (ex. 4, 5, 4, 4) through an averaging function. In signal processing, this fact is utilised while converting analog signals into digital signals. Consider the analog sinusoid shown below. Say we need to sample the signal and quantise it because we want to some digital domain processing. Now, consider just the samples in red-colour: These are evenly spaced samples occurring in every period of the sinusoid. Suppose we are digitising this signal using four bits, we will end up always quantising the value (4.25) of these red samples always as 4. This results in a quantisation error (i.e., quantisation noise) that is correlated with the signal and is very noticeable to the human ear.



However, suppose we add a (discrete) uniform random noise whose value is between -0.5 and 0.4 to the analog signal before quantisation. This means the red samples will now themselves be a uniform random variable varying from (4.25-0.5) to (4.25+0.4). Wherever the value of our uniform random noise is 0.3 or 0.4, the resulting red sample will have a value greater than 4.5 and hence quantised to 5. This happens only for 20% the red samples because the combined probability of 0.3 or 0.4 occurring in our uniform noise is 20%. The remaining 80% of the time, the red sample values will be quantised to 4. Now average the red samples and what do we get?: (80%)*4 + (20%)*5 = 4.2, which is very close to the original analog value of 4.25.


You may ask, "Where is this averaging operating happening?". Well it is happening inside the human ear. Ears carry out averaging of several periods of sine wave just the way our eyes average out changes in flip books to create the illusion of motion, or see white colour when a newton's disc is rotated at high speed.


A better Einstein

The usefulness of dither is even more apparent in images than in 1-D signal. Consider Einstein's stunningly it gray scale image below.



If we want to convert this to a black and white image - i.e., an image with just two tones - we could just make all the pixels with tonal values above half-gray to white and those below half-gray to black. However that would result in this:



It looks as if Mr. Bean tried to redraw Einstein after he ruined his picture, doesn't it. Now, instead of directly converting the gray scale Einstein to B&W, we add dither first and then convert to B&W, see what happens:


Not bad for a 1 bit/pixel image, is it? In fact, one could upsample the image (repeat every pixel 2 times or 3 times or n times), and add dither to the upsampled image and then convert it to B&W and achieve and even better image as shown below:


Now it is hard to believe that this is a two-tone image! If you don't believe me, you can zoom into the image to your heart's content and make sure that there are no gray pixels at all - they are all either black or white. This idea of using combining oversampling and dither before quantizing is common in both signal and image processing.


As before, it is the human eye (or rather, human brain) that averages pixels and creates an illusion of a wide tonal range from this two-tone image. This fact was exploited in the late 19th century to print grayscale images in newspapers using just two-tones: The black ink of the newspaper and the paper's colour. It used a technique called half-toning, which in itself is very interesting a topic.


Back to bombing Nazis

So what has all this got to do with accurately bombing German dams? Nothing, actually - RAF used a rather simple technique to bust the German dams: They used a reverse spinning barrel full of explosives, which would be dropped in the water in front of the dam, and just like stones skipping on the water surface, the barrels would skip on the water surface until they hit the dam wall, upon which a fuse would be triggered setting the explosives off.


Having said that, the story about mechanical bomb sights not working on the ground, while working just fine on the aircraft is entirely true. The vibration in the aircraft were like adding dither to the irregular movements of cogs and wheels of the computer and improving their accuracy. I just added the story about the dams just to make this an even more juicy story!! Now you now two interesting things instead of just one: Dither and the dambusters (Google it).


Post script

1. Isn't it amazing that the solution to accurately hitting the dam wall didn't involve mechanical computers and the brightest engineers in Britain? It is interesting to note that difficult problems can have simple solutions.


2. Here is the code is used for adding dither to Einstein's picture. You can play with the code with different OSR, different images and have fun.


""" dither_image.py - Demonstrates usefulness of dithering while
    quantizing gray scale image to black and white. """

import numpy as np
from skimage import io, transform
import matplotlib.pyplot as plt

img = io.imread('Albert_Einstein_Head.jpg')
meanval = np.mean(img)

# Convert to B&W
bw_img = np.empty(shape=img.shape)
bw_img[img<meanval] = 0     # Set pixels below mean pixel value to black,
bw_img[img>=meanval] = 255  # and the rest to white

# Add dither and convert to B&W
dither = np.random.uniform(low=-meanval, high =meanval, size = img.shape)
dithered_img = img + dither

bw_img_post_dither = np.empty(shape=img.shape)
bw_img_post_dither[dithered_img<meanval] = 0     # Set pixels below mean pixel value to black,
bw_img_post_dither[dithered_img>=meanval] = 255  # and the rest to white

# Upsample by 4x, add dither and convert to B&W
img_4x = np.kron(img, np.ones((4,4))) 
dither_4x = np.random.uniform(low=-meanval, high =meanval, size = img_4x.shape)
dithered_img_4x = img_4x + dither_4x

bw_img_4x_post_dither = np.empty(shape=img_4x.shape)
bw_img_4x_post_dither[dithered_img_4x<meanval] = 0     # Set pixels below mean pixel value to black,
bw_img_4x_post_dither[dithered_img_4x>=meanval] = 255  # and the rest to white

# Visualisation
fig1, ax1 = plt.subplots()
ax1.imshow(img, cmap='gray')
fig1.suptitle('Original')

fig2, ax2 = plt.subplots()
ax2.imshow(bw_img, cmap='gray')
fig2.suptitle('Black and white (without using dither)')

fig3, ax3 = plt.subplots()
ax3.imshow(bw_img_post_dither, cmap='gray')
fig3.suptitle('Black and white (using dither)')

fig4, ax4 = plt.subplots()
ax4.imshow(img_4x, cmap='gray')
fig4.suptitle('Orignal image with 4x OSR')

plt.show()







24 views0 comments

Recent Posts

See All

Works

Comments


bottom of page