# 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)
• 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,
• 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]

# size

• how to opern big image
• vliv: The principle behind Vliv (only load parts of the image that is visible, and leverage the TIFF format - tiled pyramidal images) can be implemented on any OS. The API for plugins consists only of 5 functions, see the vlivplugins repo for examples.

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
}


# map projections

## Stereographic

Stereographic projection is a map projection obtained by projecting points P on the surface of sphere from the sphere's north pole N to point P' in a plane tangent to the south pole S.[64]

take the north pole N to be the standard unit vector (0, 0, 1) and the center of the sphere to be the origin, so that the tangent plane at the south pole is has equation z = 1. Given a point P = (x, y, z) on the unit sphere which is not the north pole, its image is equal to[65]

${\displaystyle P'=f(P)=({\frac {2x}{1-z}},{\frac {2y}{1-z}})=(u,v)}$


## cylindrical

Cylindrical projections in general have an increased vertical stretching as one moves towards either of the poles. Indeed, the poles themselves can't be represented (except at infinity). This stretching is reduced in the  Mercator projection by the natural logarithm scaling. [66]


### Mercator projection

• conformal
• cylindrical = the Mercator projection maps from the sphere to an cylinder. Cylinder is cut along y axis and unrolled. It gives rectangle of infinite extent in both y-directions ( see truncation)

Two equivalent constructions of standard Mercator projection:

• from sphere to cylinder ( one step)
• 2 steps :
• project the sphere to an intermediate ( stereographic) plane using the standard stereographic projection, which is conformal
• by equating the stereographic plane to the complex plane ( the image of this plane under the complex logarithm function, which is everywhere conformal except at the origin (with a branch cut) the

complex logarithm f(z) = ln(z). Effectively, a complex point z with polar coordinates (ρ,θ) is mapped to f(z) = ln(ρ) + iθ. This yields a horizontal strip,

the standard vertical Mercator mapping by rotating 90° afterwards, or equivalently f(z) can be defined as f(z) = i*ln(z).

Normal Mercator Transverse Mercator

\

#### streching

Cylindrical projections in general have an increased vertical stretching as one moves towards either of the poles. Indeed, the poles themselves can't be represented (except at infinity). This stretching is reduced in the  Mercator projection by the natural logarithm scaling. [67]


#### truncution

Cylinder is nor finity so Mercator projections give ininite stripes with increasing distorion at poles of sphere. Thus the coordinate y of the Mercator projection becomes infinite at the poles and the map must be truncated ( cropped) at some latitude less than ninety degrees at both ends .

This need not be done symmetrically:

• Mercator's original map is truncated at 80°N and 66°S with the result that European countries were moved toward the centre of the map.

#### geometry of the earth

earth as sphere

Coordinate systems for the Earth in geography ${\displaystyle (\phi ,\lambda )}$

• latitude is a coordinate that specifies the north–south position of a point on the surface of the Earth or another celestial body. Latitude is given as an angle that ranges from –90° at the south pole to 90° at the north pole, with 0° at the Equator. is usually denoted by the Greek lower-case letter phi (ϕ or φ). It is measured in degrees, minutes and seconds or decimal degrees, north or south of the equator.
• Longitude is a geographic coordinate that specifies the east–west position of a point on the surface of the Earth. It is an angular measurement, usually expressed in degrees and denoted by the Geek letter lambda (λ).

#### equation

One step method:

Consider a point on the globe of radius R with longitude λ and latitude φ. The value λ0 is the longitude of an arbitrary central meridian that is usually, but not always, that of Greenwich (i.e., zero). The angles λ and φ are expressed in radians.

Map from point P on the unit sphere ${\displaystyle P=(R,\lambda ,\varphi )}$ to point on the Cartesian plane ${\displaystyle Q=(x,y)}$

${\displaystyle {\begin{matrix}x=R(\lambda -\lambda _{0})\\y=R\ln \left[\tan \left({\frac {\pi }{4}}+{\frac {\varphi }{2}}\right)\right]\end{matrix}}}$

Two step method

• stereographic
• complex log

The spherical form of the stereographic projection is usually expressed in polar coordinates:

${\displaystyle {\begin{matrix}r&=2R\tan \left({\frac {\pi }{4}}-{\frac {\varphi }{2}}\right)\\\theta &=\lambda \end{matrix}}}$

where ${\displaystyle R}$ is the radius of the sphere, and ${\displaystyle \varphi }$ and ${\displaystyle \lambda }$ are the latitude and longitude, respectively.

rectangular coordinates

Assumption: A, B, C, and D are real numbers such that ${\displaystyle A^{2}+B^{2}+C^{2}\neq 0}$.

Definitions

• ${\displaystyle \Sigma }$ is defined to be the unit sphere in the Euclidean space, i.e.
  ${\displaystyle \Sigma :={\big \{}(x,y,z)\in \mathbb {R} ^{3}:x^{2}+y^{2}+z^{2}=1{\big \}}.}$

• ${\displaystyle N}$ is defined to be the northern pole of the unit sphere, i.e. ${\displaystyle N:=(0,0,1)}$.
• ${\displaystyle S}$ is defined to be the stereographic projection, i.e. the function ${\displaystyle S:\Sigma \setminus \{N\}\rightarrow \mathbb {R} ^{2}}$ satisfying
  ${\displaystyle Q=S{\big (}(x,y,z){\big )}={\Big (}{\frac {x}{1-z}},{\frac {y}{1-z}}{\Big )}}$


for every ${\displaystyle (x,y,z)\in \Sigma \setminus \{N\}}$.

Cylindrical coordinates

Cylindrical coordinates (axial radius ρ, azimuth φ, elevation z) may be converted into spherical coordinates (central radius r, inclination θ, azimuth φ), by the formulas

{\displaystyle {\begin{aligned}r&={\sqrt {\rho ^{2}+z^{2}}},\\\theta &=\arctan {\frac {\rho }{z}}=\arccos {\frac {z}{\sqrt {\rho ^{2}+z^{2}}}},\\\varphi &=\varphi .\end{aligned}}}

Conversely, the spherical coordinates may be converted into cylindrical coordinates by the formulae

{\displaystyle {\begin{aligned}\rho &=r\sin \theta ,\\\varphi &=\varphi ,\\z&=r\cos \theta .\end{aligned}}}

These formulae assume that the two systems have the same origin and same reference plane, measure the azimuth angle φ in the same senses from the same axis, and that the spherical angle θ is inclination from the cylindrical z axis.

Code

# Signal processing

Filter Linear continuous-time filters

• The frequency response can be classified into a number of different bandforms describing which frequency bands the filter passes (the passband) and which it rejects (the stopband):
• Low-pass filter – low frequencies are passed, high frequencies are attenuated.
• High-pass filter – high frequencies are passed, low frequencies are attenuated.
• Band-pass filter – only frequencies in a frequency band are passed.
• Band-stop filter or band-reject filter – only frequencies in a frequency band are attenuated.
• Notch filter – rejects just one specific frequency - an extreme band-stop filter.
• Comb filter – has multiple regularly spaced narrow passbands giving the bandform the appearance of a comb.
• All-pass filter – all frequencies are passed, but the phase of the output is modified.
• Cutoff frequency is the frequency beyond which the filter will not pass signals. It is usually measured at a specific attenuation such as 3 dB.
• Roll-off is the rate at which attenuation increases beyond the cut-off frequency.
• Transition band, the (usually narrow) band of frequencies between a passband and stopband.
• Ripple is the variation of the filter's insertion loss in the passband.
• The order of a filter is the degree of the approximating polynomial and in passive filters corresponds to the number of elements required to build it. Increasing order increases roll-off and brings the filter closer to the ideal response.