# Algorithms

postprocessing = modification of the image = graphic algorithms = image processing

Algorithms by graphic type

• raster algorithms
• vector algorithms

Five classes of image processing algorithms:

• image restoration
• image analysis
• image synthesis
• image enhancement
• image compression.

List:

• Morphological operations on binary images
• morphological closing = dilation followed by erosion
• morphological opening = erosion followed by dilation

Postprocessing

• Two types of edge detection
• Pseudo-3D projections
• Star field generator
• Random dot stereograms (aka Magic Eye)
• Motion blur for animations
• Interlacing
• Embossing
• Antialiasing
• Palette emulation to allow color cycling on true-color displays
• True color emulation that provides dithering on 256-color display

Algorithms:

## types

### range

The image processing operators ( algorithms) can be classified into the 4 categories

• pixel algorithms = pixel processing: the point operator acts on individual pixels : g = H(f)
• the histogram
• look-up table (LUT)
• windowing
• local algorithms = kernaling = local processing: "A local operator calculates the pixel value g(x) based not only on the value in the same position in the input image, i.e. f(x) , but it used several values in nearby points f(x+y). Local operators are at the heart of almost all image processing tasks."
• spatial location filtering (convolution),
• spatial frequency filtering using high- and low-pass digital filters,
• geometric processing = geometric transformations: "Whereas a point operator changes the value of all pixels a geometrical operator doesn’t change the value but instead it ‘moves’ a pixel to a new position."
• Global Operators: "A global operator (potentially) needs al pixel values in the input image to calculate the value for just one pixel in the output image."

# dense image

Dense image

• downscaling with gamma correction
• path finding
• aliasing 
• changing algorithm ( representation function) from discrete to continous, like from level set method of escape time to continous ( DEM )
  "the denser the area, the more heavy the anti-aliasing have to be in order to make it look good."  knighty
  "the details are smaller than pixel spacing, so all that remains is the bands of colour shift from period-doubling of features making it even denser"  claude

path finding

Algorithms

Methods:

# polygons

• geometric operations for two-dimensional polygons

## How to tell whether a point is to the right or left side of a line ?

/*
How to tell whether a point is to the right or left side of a line ?

http://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-to-the-right-or-left-side-of-a-line

a, b = points
line = ab
pont to check = z

position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
It is 0 on the line, and +1 on one side, -1 on the other side.

*/

double CheckSide(double Zx, double Zy, double Ax, double Ay, double Bx, double By)
{
return ((Bx - Ax) * (Zy - Ay) - (By - Ay) * (Zx - Ax));

}


## Testing if point is inside triangle

/*
c console program
gcc t.c -Wall
./a.out

*/

# include <stdio.h>

// 3 points define triangle
double Zax = -0.250000000000000;
double Zay = 0.433012701892219;
// left when y
double Zlx = -0.112538773749444;
double Zly = 0.436719687479814 ;

double Zrx = -0.335875821657728;
double Zry = 0.316782798339332;

// points to test
// = inside triangle
double Zx = -0.209881783739630;
double Zy =   +0.4;

// outside triangle
double Zxo = -0.193503885412548  ;
double Zyo = 0.521747636163664;

double Zxo2 = -0.338750000000000;
double Zyo2 = +0.440690927838329;

// ============ http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-2d-triangle
// In general, the simplest (and quite optimal) algorithm is checking on which side of the half-plane created by the edges the point is.
double sign (double  x1, double y1,  double x2, double y2, double x3, double y3)
{
return (x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3);
}

int  PointInTriangle (double x, double y, double x1, double y1, double x2, double y2, double x3, double y3)
{
double  b1, b2, b3;

b1 = sign(x, y, x1, y1, x2, y2) < 0.0;
b2 = sign(x, y, x2, y2, x3, y3) < 0.0;
b3 = sign(x, y, x3, y3, x1, y1) < 0.0;

return ((b1 == b2) && (b2 == b3));
}

int Describe_Position(double Zx, double Zy){
if (PointInTriangle( Zx, Zy, Zax, Zay, Zlx, Zly, Zrx, Zry))
printf(" Z is inside \n");
else printf(" Z is outside \n");

return 0;
}

// ======================================

int main(void){

Describe_Position(Zx, Zy);
Describe_Position(Zxo, Zyo);
Describe_Position(Zxo2, Zyo2);

return 0;
}


## Orientation and area of the triangle

Orientation and area of the triangle : how to do it ?

// gcc t.c -Wall
// ./a.out
# include <stdio.h>

// http://ncalculators.com/geometry/triangle-area-by-3-points.htm
double GiveTriangleArea(double xa, double ya, double xb, double yb, double xc, double yc)
{
return ((xb*ya-xa*yb)+(xc*yb-xb*yc)+(xa*yc-xc*ya))/2.0;
}

/*

wiki Curve_orientation
[http://mathoverflow.net/questions/44096/detecting-whether-directed-cycle-is-clockwise-or-counterclockwise]

The orientation of a triangle (clockwise/counterclockwise) is the sign of the determinant

matrix = { {1 , x1, y1}, {1 ,x2, y2} , {1,  x3, y3}}

where


# test external tangency of 2 circles

/*
distance between 2 points
z1 = x1 + y1*I
z2 = x2 + y2*I
en.wikipedia.org/wiki/Distance#Geometry

*/

double GiveDistance(int x1, int y1, int x2, int y2){
return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

/*
mutually and externally tangent circles
mathworld.wolfram.com/TangentCircles.html
Two circles are mutually and externally tangent if distance between their centers is equal to the sum of their radii

*/

double TestTangency(int x1, int y1, int r1, int x2, int y2, int r2){
double distance;

distance = GiveDistance(x1, y1, x2, y2);
return ( distance - (r1+r2));
// return should be zero
}