# 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:[1][2][3]

• Morphological operations on binary images[6][7]
• 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)
• add two images: g(x)=f1(x)+f2(x)
• 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."[9]
• spatial location filtering (convolution),
• spatial frequency filtering using high- and low-pass digital filters,
• the unsharp masking technique[10]
• 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[11][12][13][14][15]

• downscaling with gamma correction[16]
• path finding[17]
• aliasing [18]
• 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[19]
  "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[20]

path finding

Algorithms[21]

Methods:

# polygons

• geometric operations for two-dimensional polygons[22][23]

## 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
}