Antialias
From CDS 130
Contents 
1. Objective
 To introduce a ubiquitous image manipulation technique.
2. Motivation
 To apply the concepts of nested
for
loops andif
statements to a basic image manipulation problem.  To prepare for doing a computational simulation on a 2D grid.
3. Prequestion

4. Notes
4.1. Creating an image
 To draw a number or letter on a screen, create a matrix.
 Place 1s where you want white, 0s where you want black.
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
4.2. The problem
 The sharp edges make letters look "unpleasant" when zoomed out.
From [1]
4.3. Eye trick
 Fill in places where black is near white with gray.
 Translated to a mathematical statment:
If a0
is next to a1
, replace the0
with a0.5
.
From [2].
4.4. Eye trick cont.
 Fill in places where black is near white with gray.
 The small antialiased letter is considered "more pleasant" by most readers.
4.5. Question
This trick has been known for a long time. Why wasn't it used on old computers?
4.6. Your task
 Your task will be to antialias this "dot".
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
4.7. Part I
 An important part of computation is identifying the important part of the problem that you want to solve. The above examples are twodimensional (each pixel has a horizontal and vertical position and is represented as a matrix).
 Before trying the twodimensional problem, try a onedimensional problem (apply the algorithm to an array instead of a matrix).
 Write a program that implements the algorithm:
If a0
is next to a1
, replace the0
with a0.5
.
 Write a program that implements the above algorithm on any array of 1s and 0s. To test your algorithm, use this array:
A = [0,1,0,0,1, 1,1,0,0,0];
 Instructions: Work on your own or with a partner on this problem. I will ask for students to suggest solutions in 510 minutes.
4.8. Part II
(Don't start doing this until I finish the explanations of the instructions.)
Create a script file named antialias.m
and copy the following code into it. In the same file, below this code, write a program that antialiases the image that is created when your run the program.
% This program creates a circular shape. clear;clf; for i = [1:16] for j = [1:16] if ( (i  8)^2 + (j  8)^2 ) <= 17 M(i,j) = 0; else M(i,j) = 1; end end end imagesc(M); M axis square;grid on; C = [0,0,0; 0.5,0.5,0.5; 1,1,1]; colormap(C);
4.9. Instructions Part II
 Discuss how you will approach this problem with a partner (you may work on your own).
 After 5 minutes, I will ask a few students to come to the board and explain the algorithm.
5. Questions
5.1. 1D Antialias
In this problem you will write a program using the techniques covered in If_Statement and Antialias that antialiases a given array. Then, you will use a special function to create an array of randomly placed 1s and 0s. You will first test your algorithm on this given array:
A = [0,1,0,1,0,0,0,1,0,1,0]
Then you will test your algorithm on the 10element array created using this command:
A = round(rand(1,10))
To see what the above command does, enter it on the command line twice in a row. Each time you should see an array with 10 elements that are either 0 or 1. The array (will almost always) be different each time you execute the command.
Instructions:
 Open a text file named
hw8_1d.m
. On the first line enter
A = [0,1,0,1,0,0,0,1,0,1,0]
 Below this, write a program (using
for
loops andif
statements) that replaces any0
that is next to a1
with0.5
in the arrayA
.  When you are able to get this result:
A = [0.5,1.0,0.5,1.0,0.5,0.0,0.5,1.0,0.5,1.0,0.5]
 then your program correctly antialiases the given array
A
.
 In your text file, replace the line
A = [0,1,0,1,0,0,0,1,0,1,0]
 with
A = round(rand(1,10))
 and run your program several times. Your program is working if after each time you run it, any
0
that was next to a1
was replaced with a0.5
.
(Extra credit: Write a program that repeats your program 1000 times. That is, write a program that would do the same thing as if you typed hw8_1d
and the enter key 1000 times.)
Answer 

Previously, we have replaced elements in an array using If_Statements clear;clc; A = [0,1,0,1,0,0,0,1,0,1,0] for i = 1:11 % We could replace 11 with length(A) if (A(i) == 0) % Note the double equal A(i) = 0.5; end end A The above needs to be modified so that if an element is zero and the next element is 1, change that element to a 0.5. Said another way, we only want the statement clear;clc; A = [0,1,0,1,0,0,0,1,0,1,0] for i = 1:11 % We could replace 11 with length(A) if (A(i) == 0) % Note the double equal if (A(i+1) == 1) A(i) = 0.5; end end end A The solution is to change i=1:11 to i=1:10 clear;clc; A = [0,1,0,1,0,0,0,1,0,1,0] for i = 1:10 % We could replace 10 with length(A)1 if (A(i) == 0) if (A(i+1) == 1) A(i) = 0.5; end end end A When this is executed, we get A = Columns 1 through 8 0.5000 1.0000 0.5000 1.0000 0 0 0.5000 1.0000 Columns 9 through 11 0.5000 1.0000 0 Note that there are still occurrences of a 1 followed by a zero. The solution is to repeat the previous for loop except check for a 1 that is followed by a zero. clear;clc; A = [0,1,0,1,0,0,0,1,0,1,0] for i = 1:10 % We could replace 10 with length(A)1 if (A(i) == 0) if (A(i+1) == 1) A(i) = 0.5; end end end for i = 1:10 % We could replace 10 with length(A)1 if (A(i+1) == 0) if (A(i) == 1) A(i+1) = 0.5; end end end A You can check your answer for many different arrays by replacing the second line in the program above with A = round(rand(1,10)) end executing the program many times. To repeat the process 1000 times, use clear;clc; for z = 1:1000 % Note that index named i is already used A = round(rand(1,10)) for i = 1:10 % We could replace 10 with length(A)1 if (A(i) == 0) if (A(i+1) == 1) A(i) = 0.5; end end end for i = 1:10 % We could replace 10 with length(A)1 if (A(i+1) == 0) if (A(i) == 1) A(i+1) = 0.5; end end end A end 
5.2. 2D Antialias
Copy the following program into a script file:
close all; clear all; n = 16; for i = [1:n] for j = [1:n] if ( (i  n/2)^2 + (j  n/2)^2) <= (n/4)^2 M(i,j) = 0; else M(i,j) = 1; end end end C = [0,0,0;0.5,0.5,0.5;1,1,1]; figure(1);hold on;axis square;grid on; imagesc(M); colormap(C); print dpng circle_before.png
In the same file, copy the commands
i = 8; for j = [1:n1] if (M(i,j) == 0) if (M(i,j+1) == 1) M(i,j) = 0.5; end end end figure(2);hold on;axis square;grid on; imagesc(M); colormap(C); print dpng circle_after.png
By building on the above set of commands (starting at i=8
), write a program that converts the circle created in figure 1 to the circle shown in figure 2 below.
Answer 

clear close all; clear all; n = 16; for i = [1:n] for j = [1:n] if ( (i  n/2)^2 + (j  n/2)^2) <= (n/4)^2 M(i,j) = 0; else M(i,j) = 1; end end end C = [0,0,0;0.5,0.5,0.5;1,1,1]; figure(1);hold on;axis square;grid on; imagesc(M); colormap(C); print dpng circle_before.png for i = [1:n]; for j = [1:n1] if (M(i,j) == 0) if (M(i,j+1) == 1) M(i,j) = 0.5; end if (j>1) if (M(i,j1) == 1) M(i,j) = 0.5; end end end end end figure(2); hold on; axis square; grid on; imagesc(M); colormap(C); print dpng circle_after.png 
5.3. 2D Antialias II
Copy the following program into a matlab:
close all; clear all; n=16 for i = [1:n] for j = [1:n] if ( (i  8)^2 + (j  8)^2 ) <= 17 M(i,j) = 1; else M(i,j) = 0; end if (j>7 && j<9) M(i,j) =0; end end end imagesc(M); M axis square;grid on; C = [0,0,0; 0.5,0.5,0.5; 1,1,1]; colormap(C);
In the same file, copy the commands
i = 8; for j = [1:n1] if (M(i,j) == 0) if (M(i,j+1) == 1) M(i,j) = 0.5; end end end figure(2);hold on;axis square;grid on; imagesc(M); colormap(C); print dpng circle_after.png
By building on the above set of commands, write a program that converts the image in figure 1 to the image shown in figure 2 below.
Answer 

for i = [1:n]; for j = [1:n1] if (M(i,j) == 0) if (M(i,j+1) == 1) M(i,j) = 0.5; end if (j>1) if (M(i,j1) == 1) M(i,j) = 0.5; end end end end end figure(2); hold on; axis square; grid on; imagesc(M); colormap(C); print dpng circle_after.png 
5.4. Extra Credit
Right click on the following image: and save it to the directory that is shown when you type
pwd
on the Octave command line.
Open a file named hw8ec.m
and enter
M = imread('a.png');
Below this command, write a program that
 Plots the matrix as a blackandwhite image, and
 Antialiases the image.
6. References
 Interactive Applet demonstrating antialiasing [3]