An Interseting Excerpt

nanak

Leave a comment

Counting and the Mind

Here is an interesting fact taken verbatim from the book “A Passion for Mathematics” by Clifford A Pickover.

Question

I quickly toss a number of marbles onto a pillow. You may stare at them for an instant to determine how many marbles are on the pillow. Obviously, if I were to toss just two marbles, you could easily determine that two marbles sit on the pillow. What is the largest number of marbles you can quantify, at a glance, without having to individually count them?

Answer

Seven. In 1949, Kaufman, Lord, Reese, and Volkmann flashed random patterns of dots on a screen. When subjects looked at patterns containing up to five or six dots, the subjects made no errors. The performance on these small numbers of dots was so different from the subjects’ performance with more dots that the observation methods were given special names. Below seven, the subjects were said to subitize; above seven, they were said to estimate. For more information, see E. L. Kaufman, M. W. Lord, T. W. Reese, and J. Volkmann, “The Discrimination of Visual Number,” American Journal of Psychology 62 (1949): 498–525. Also see George Miller, “The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information,” The Psychological Review 63 (1956): 81–97.

Leave a comment

Advice for Patients and Family

Managing schizophrenia is a significant challenge. The immediate people effected are the patient himself and his family. Though I do not consider myself to be 100% cured, yet I feel that I am content with my life. It is almost 10 years since I was admitted in hospital for my first break. I have learned a lot through my experience with the disease. In this post I will be discussing some tips that may be helpful in coping with this mental disorder.

First of all, the family need to be patient. The disease take some time to develop and may take a considerably more time to recover. There is no magic pill. The medicine will also take time to relieve the symptoms. The family should realize that the thinking process of the patient is not the same as normal individuals. It is not the case that you tell the patient that you are thinking illogically and the patient accept that and that is end of it. Every patient goes into this illness in his own way and will recover in his own way.

The main advice for the patient is self counseling and self arguments. You may be extremely unlucky that you have been diagnosed with this serious illness, but that is not the end of life. Try to systematize your delusions. Try to identify those thoughts that do not make sense. Try to indulge in other healthy and interesting activities. Explore you interests and activities you enjoy. Make daily, weekly etc goals and chase them. Be proactive. Discuss your delusions with someone close to you. You may write them in a diary or start a blog like me.

If the medicine is not helping in relieving the symptoms, discuss with your doctor. It may take some time that you find the combination that works right for you. If the physician is not receptive, change the physician. I usually prefer the clinical psychologist over psychiatrist. The disease can be very well managed and the patients can spend healthy life. It may be the most serious disease in psychiatry but your fate is not doomed for good. Many people with this illness has demonstrated that they can very well be on the road to successful rehabilitation. Many such stories can be found on internet, books etc.

The main difficulty facing the family is how to handle the psychosis. The only thing that you can do is to keep silent and listen. The patient will believe in his delusion as the only truths. You can’t argue with the patient. The things may be obviously wrong and non sense to you, but those would be making perfect sense to the patient. If you want to correct him or streamline his thoughts and delusions, talk to the patient when he is in light mode. Try to make him realize his delusions gradually. He may systematize some of those. I personally think that my delusions will never be systematized completely. I keep on developing new one as I shed the old ones!

The last point that I wanted to discuss is the forced medication specially injections. I have been forced a few times and I consider them to be worst parts of my life. The shrinks may have different opinion on those but in my opinion these are violation of human rights and dignity. If the life of patient or someone else is in danger then they may be enforced. I never committed violence during my psychosis, but violence was committed against me by forced medication. My only message is to stop those. We are as human as any one else on this planet.

Leave a comment

My 3 Ingredients of Recovery

Schizophrenia is a complicated disease. It takes a considerable time to recover. I have never heard of it before. Though I have watched the Hollywood movie ‘A Beautiful Mind’ before my diagnosis, but I never bothered to know the name/pronunciation or nature of the disease. It was primarily my interest in Nobel prizes. It took almost 2 years to understand and accept the disease. The recovery was not rapid either. I tried to read books but it appeared to me that I was reading words. The comprehension was very low. I would boot the computer, see the monitor and could not make out what to do. The main concerns were the nature of the disease itself and future itself. Will I be ever able to overcome it? Gradually I tried to regroup my self around my interests. These are 3 main points which proved to be vital in my recovery.

I think Linux is/was my first love as described in this blog post. My admission in hospital put a break in it. I was admitted for too long, about a year. There was no counseling at all by the psychiatrists. My path to recovery was my own struggle with the considerable help from my family. I forgot about many commands, steps and tricks about Linux. Though I had it installed but I rarely used it. I was a regular reader of Linux Weekly News, but my admission put a break of about a year. I was unaware of recent developments. I bought the DVD of Fedora 7 and gradually refreshing my skills. It was the first distribution I installed after my diagnosis. Gradually I have ‘another’ interest besides my illness and future prospects.

As discussed, I had difficulty in reading and comprehending books. I started feeling that I would not be able to learn new things. Comprehension was low but I kept trying. Programming was one of my strong points. We learned FORTRAN in our studies. I did my project in Visual Basic. I had not used them for a while, so I had forgotten about them. I had saved some notes on C programming by my project adviser Omar Bashir that can be found here. I decided to learn C using these notes. The notes are beautifully written. As I started reading, I was able to comprehend and understand them well. This gave me confidence that I could understand new things and the disease can be managed.

My third ingredient is related to internet usage. I had kept the usage of internet to my interests mainly Linux, science history and engineering. I was a fan of mit opencourseware. But I was slow to adopt the other sides of the internet, the world of free books and torrents. I started categorizing and saving my data since my days in Army. It had a very few books. My younger brother, Yasir introduced me to a giant folder that contained a lot of math books and tutorials. He has collected them from one of his friends. This started my quest for free books. I started searching the internet for sites dedicated to books. The 4 main sites that I used were rapidshare, gigapedia, ebookshare and freebookspot. The first 3 have been closed. From these I have learned a lot.

These were not the only factors in my recovery. They proved to be crucial. The thing which is/was above all, was the support of my family specially my parents.

,

2 Comments

Some Mathematical GIFs

Here are some GIFs I have collected over internet that explain mathematical ideas. The following GIF explain what is meant by tangent/parallel lines and asymptotes.

par_n_tan

The following GIF explains how to construct a regular heptagon using straight edge and compass.

heptagon

The following 2 GIFs explain what an ellipse is and how to draw it.

ellipse

ellipsebande

The area of the circle with unit radius is \pi and so is the circumference of the circle with unit diameter. The following 2 GIFs illustrate that.

area_circ

pi_unrolled

The following GIF explain a method to find the Golden Ratio (\phi).

phi

The following 3 GIFs are the illustrations of Pythagorean Theorem.

pythag

pythanimpythagoras3d

If you move along a unit circle with center at origin, then its coordinates are (\cos \theta, \sin \theta ). The following 3 GIFs exploit this fact.

trig

trig3

trign

The following GIF explains that how a sine wave is compressed or expanded if its period is changed.

sinax

The following GIF explain how to plot a graph by moving from rectangular to polar coordinates.

rect2pol

The following 2 GIFs demonstrate the creation of cardoid. In first a cardoid is obtained by rotating a circle around one of half its radius. The second one shows a parametric equation for the curve.

cardiod

cardioid_par

The following two GIFs demonstrate the creation of hypotrochoids.

hypotrochoid

hypotrochoid2

In the following GIF, circles of radius 1 and 3 roll together along a straight line, tracing out a fixed cycloid along with rotating cardioids and deltoids.

cdc

The animation illustrates the Gram-Schmidt process for obtaining an orthonormal basis of vectors for 3-dimensional euclidean space.

gram-schm

All differential functions are continuous but not vice versa. The following animation shows a continuous function that is not differential at zero.

continuity

Taylor series is used for approximation of functions. The following 2 animations show a sinusoid and its Taylor polynomials of different orders.

taylortaylor2

The following 2 animations demonstrates the Fourier Series and Transform.It demonstrates how a series of waves with increasing frequencies, and carefully chosen decreasing amplitudes, adds up to give a square wave with flat peaks and troughs. Fourier analysis provides a method for choosing the amplitudes of the waves.

fourier2

fourier

The last 3 GIFs are misc curves. The last one is the batman curve.

cubincube

spiral

batflaps

Leave a comment

3 interesting GIFs

Here are 3 interesting GIFs I find very amusing.

funny-gif-computer-transformer

mousecpp-vs-java

Leave a comment

Spherical Trigonometry and Navigational Calculations

Introduction

Navigation is the process of planning, recording, and controlling the movement of a craft or vehicle from one location to another. The word derives from the Latin roots navis (“ship”) and agere (“to move or direct”). To achieve these goals in a general way, a coordinate system is needed that allow quantitative calculations. The most commonly used notation involves latitudes and longitudes in a spherical coordinate system. Spherical Trigonometry deals with triangles drawn on a sphere The development of spherical trigonometry lead to improvements in the art of earth-surfaced, orbital, space and inertial navigation, map making, positions of sunrise and sunset, and astronomy.

History

Spherical trigonometry was dealt with by early Greek mathematicians such as Menelaus of Alexandria who wrote a book that dealt with spherical trigonometry called “Sphaerica”. The subject further developed in the Islamic Caliphates of the Middle East, North Africa and Spain during the 8th to 14th centuries. It arose to solve an apparently simple problem: Which direction is Mecca? In the 10th century, Abu al-Wafa al-Buzjani established the angle addition identities, e.g. \sin (\alpha + \beta), and discovered the law of sines for spherical trigonometry. Al-Jayyani (989-1079), an Arabic mathematician in Islamic Spain, wrote what some consider the first treatise on spherical trigonometry, circa 1060, entitled “The Book of Unknown Arcs of a Sphere” in which spherical trigonometry was brought into its modern form. This treatise later had a strong influence on European mathematics. In the 13th century, Nasir al-Din al Tusi (1201–74) and al-Battani, continued to develop spherical trigonometry. Tusi was the first (c. 1250) to write a work on trigonometry independently of astronomy. The final major development in classical trigonometry was the invention of logarithms by the Scottish mathematician John Napier in 1614 that greatly facilitated the art of numerical computation – including the compilation of trigonometry tables.

Navigational Terminology

Although the Earth is very round, in fact, it is a flattened sphere or spheroid with values for the radius of curvature of 6336 km at the equator and 6399 km at the poles. Approximating the earth as a sphere with a radius of 6370 km results in an actual error of up to about 0.5%. The flattening of the ellipsoid is ~1/300 (1/298.257222101 is the defined value for the GPS ellipsoid WGS-84). Flattening is (a-b)/a where a is the semi-major axis and b is the semi-minor axis. The value of a is taken as 6378.137 km in GPS ellipsoid WGS-84.

The position of a point on the surface of the Earth, or any other planet, for that matter, can be specified with two angles, latitude and longitude. These angles can be specified in degrees or radians. Degrees are far more common in geographic usage while radians win out during the calculation.

Latitude is the angle at the center of the Earth between the plane of the Equator (0^o latitude) and a line through the center passing through the surface at the point in question. Latitude is positive in the Northern Hemisphere, reaching a limit of +90^o at the North Pole, and negative in the Southern Hemisphere, reaching a limit of -90^o at the South Pole. Lines of constant latitude are called parallels. Longitude is the angle at the center of the planet between two planes passing through the center and perpendicular to the plane of the Equator. One plane passes through the surface point in question, and the other plane is the prime meridian (0^o longitude), which is defined by the location of the Royal Observatory in Greenwich, England. Lines of constant longitude are called meridians. All meridians converge at the north and south poles (90^oN and -90^oS). Longitudes typically range from -180^o to +180^o. Longitudes can also be specified as east of Greenwich (E or positive) and west of Greenwich (W or negative). Figure 1 illustrates the typical latitudes and longitudes on Earth. In spherical or geodetic coordinates, a position is a latitude taken together with a longitude, e.g., (lat, lon), which defines the horizontal coordinates of a point on the surface of a planet. Azimuth or bearing or true course is the angle a line makes with a meridian, taken clockwise from north. Usually azimuth is measured clockwise from north (0 = North, 90 = East, 180 = South 270= West, 360=0=North).

latlongFigure 1: Typical latitude and longitude values on earth surface

A rhumb line is a curve that crosses each meridian at the same angle. Although a great circle is a shortest path, it is difficult to navigate because your bearing (or azimuth) continuously changes as you proceed. Following a rhumb line covers more distance than following a geodesic, but it is easier to navigate. Unlike a great circle which encircles the earth, a pilot flying a rhumb line would spiral indefinitely poleward. The rumb line formulas are more complicated and will not be discussed.

Spherical Trigonometry

Great/Small Circles and Geodesic

Any plane will cut a sphere in a circle. A great circle is a section of a sphere by a plane passing through the center. Other circles are called small circles. All meridians are great circles, but all parallels, with the exception of the equator, are not. There is only one great circle through two arbitrary points that are not the opposite endpoints of a diameter. The smaller arc of the great circle through two given points is called a geodesic, and the length of this arc is the shortest distance on the sphere between the two points. The great circles on the sphere play a role similar to the role of straight lines on the plane.

Spherical Triangle

A figure formed by three great circle arcs pairwise connecting three arbitrary points on the sphere is called a spherical triangle or Euler triangle as shown in Figure 2. The vertices of the triangles are formed by 3 vectors (\vec{OA},\vec{OB},\vec{OC}). The angles less than \pi between the vectors are called the sides a, b and c of a spherical triangle. To each side of a triangle there corresponds a great circle arc on the sphere. Each pair of vectors forms a plane. The angles A, B and C opposite the sides a, b and c of a spherical triangle are the angles between the great circle arcs corresponding to the sides of the triangle, or, equivalently, the angles between the planes determined by these vectors.

sphtrgFigure 2: A spherical triangle on a sphere

Spherical Triangle and Navigation

In navigation applications the angles and sides of spherical triangles have specific meanings. Sides (a, b or c) when multiplied by the radius of the Earth gives the geodesic distances between the points. By definition one nautical mile is equivalent to 1min of latitude extended at the surface of Earth. When one point is the North pole, the two sides originating from that point (b and c in Figure 2) are the co-latitudes of the other two points. The angles at the other two points (B and C in Figure 2) are the azimuth or bearing to the other point.

Spherical Triangle Formulas

Most formulas from plane trigonometry have an analogous representation in spherical trigonometry. For example, there is a spherical law of sines and a spherical law of cosines. Let the sphere in Figure 2 be a unit sphere. Then vectors \vec{OA}, \vec{OB} and \vec{OC} are unit vectors. We take OA as the Z-axis, and OB projected into the plane perpendicular to OA as the X-axis. Vectors \vec{OB} and \vec{OC} has components (\sin c, 0, \cos c) and (\sin b \cos A, \sin b \sin A, \cos b) respectively. From dot product rule:

\cos a = \vec{OB} \bullet \vec{OC}
\cos = (\sin c, 0, \cos c) \bullet (\sin b \cos A, \sin b \sin A, \cos b)

This gives the identity (and its two analogous formulas) known as law of cosines for sides.

\cos a = \cos b \cos c + \sin b sin c \cos A
\cos b = \cos c \cos a + \sin c sin a \cos B
\cos c = \cos a \cos b + \sin a sin b \cos C

Similarly by using the \sin formula for vector cross product we get the law of sines.

\frac{\sin A}{\sin a} = \frac{\sin B}{\sin b} = \frac{\sin C}{\sin c}

The law of cosines for angle is given by.

\cos A = -\cos B \cos C + \sin B \sin C \cos a
\cos B = -\cos C \cos A + \sin C \sin A \cos b
\cos C = -\cos A \cos B + \sin A \sin B \cos c

There are numerous other identities. All these identities allow us to solve the spherical triangles when appropriate angles and sides are given.

The sum of the angles of a spherical triangle is between \pi and 3\pi radians (180^o and 540^o). The spherical excess is defined as E = A + B + C - \pi, and is measured in radians. The area A of spherical triangle with radius R and spherical excess E is given by the following Girard’s Theorem.

A = R^2E

The spherical geometry is a simplest model of elliptic geometry, which itself is a form of non-Euclidean geometry, where lines are geodesics. It is inconsistent with the “parallel line” postulate of Euclid. In the elliptic model, for any given line l and a point A, which is not on l, all lines through A will intersect l. Moreover the sum of angles in the triangle will be greater than 180^o. For example for two of the sides, take lines of longitude that differ by 90^o. For the third side, take the equator. This gives us a triangle with an angle sum of 270^o.

Navigational Calculations

Distance and Bearing Calculation

The problem of determining the distance and bearing can easily be calculated. Let point B and C have positions (lat1, lon1) and (lat2, lon2) respectively. Let point A be the North Pole as shown in Figure 2. The angle A is the difference between the longitudes. Moreover the sides b and c are (90^o - lat1) and (90^o - lat2) respectively. Keeping theses in mind and using law of cosines for sides we get.

\cos a = \sin (lat1) \sin (lat2) + \cos (lat1) \cos (lat2) \cos (lon2 - lon1)

Taking \cos^{-1} we get the value of side a between 0 and \pi radians. By multiplying it with the radius of earth we get the required distance. The triangle can be solved for all sides. The angle B is the bearing from B to C. The values of \sin B and \cos B can be calculated using the flowing relations.

\cos B = \cos (lat2) \sin (lon2 - lon1)
\cos B = \cos (lat1) \sin (lat2) - \sin (lat1) \cos (lat2) \cos (lon2 - lon1)

The angle B can be computed using two-argument inverse tan function (usually denoted by tan2^{-1} or atan2), which gives the value between \pi and -\pi radians.

Dead Reckoning

Dead reckoning (DR) is the process of estimating one’s current position based upon a previously determined position, or fix, and advancing that position based upon known speed, elapsed time (or distance) and course. In studies of animal navigation, dead reckoning is more commonly (though not exclusively) known as path integration, and animals use it to estimate their current location based on the movements they made since their last known location. Here we present the algorithm to compute the position of the destination if the distance and azimuth from previous position is known. Let the starting point has position (lat, lon). The azimuth from starting point is azm and the angular distance covered is dis in radians. Let the position of the destination be (newlat, newlon). Then latitude can be calculated by

newlat = \sin^{-1}(\sin (lat) \cos (dis) + \cos (lat) \sin (lat) \sin (dis) \cos (azm)

The calculation of longitude can be carried out as under.

lon1 = lon + tan2^{-1}(\sin (dis) \sin (azm), \cos (lat) \cos (dis) - \sin (lat) \sin (dis) \cos (dis)

The value of lon1 can be outside the range of \pi and \pi radians. The function angpi2pi brings it in the required range.

newlon = angpi2pi(lon1)

Conclusion

Spherical trigonometry is used for most calculations in navigation and astronomy. For the most accurate navigation and map projection calculation, ellipsoidal forms of the equations are used but these equations are much more complex. Dead reckoning is used extensively in Inertial Navigation Systems (INS). Spherical trigonometry along with linear algebra forms the backbone for modern navigation systems such as GPS. It is a prerequisite for good understanding of GIS. It is much more pertinent to integrate course of spherical trigonometry in the engineering curriculum.

Note: This is the edited version of the paper I presented at Institute of Space Technology in end 2008. You can download the associated paper from here and PowerPoint presentation from here.

, ,

Leave a comment

A New Simulation of Spiral Architecture

Introduction

Hexagonal structure is different from the traditional square structure for image representation. The geometrical arrangement of pixels on hexagonal structure can be described in terms of a hexagonal grid. Hexagonal structure provides an easy way for image translation and rotation information. Spiral Architecture is a relatively new and powerful approach to machine vision system. However, all the existing hardware for capturing image and for displaying image are produced based on rectangular architecture. It has become a serious problem affecting the advanced research on Spiral Architecture. In this paper, a new approach to Spiral Architecture is presented using MATLAB. This mimic Spiral Architecture almost retains image resolution and does not introduce distortion. Furthermore, images can be smoothly and easily transferred between the traditional square structure and this new hexagonal structure.

Overview of Hexagonal Grid

A digital image contains thousands of pixels to represent the real world and when we touch the term ‘pixel’ so far, that means a rectangular box in an image. Almost all the previous image processing and image analysis research is based on this traditional image structure. The advantages of using a hexagonal grid to represent digit images have been investigated for more than thirty years. The importance of the hexagonal representation is that it possesses special computational features that are pertinent to the vision process. Dozens of reports describing the advantages of using such a grid type have been found in the literature. The hexagonal image structure has features of higher degree of circular symmetry, uniform connectivity, greater angular resolution, and a reduced need of storage and computation in image processing operations. Its computational power for intelligent vision pushes forward the image processing field consists of the organizational units of vision. In spite of its numerous advantages, hexagonal grid has so far not yet been widely used in computer vision and graphics field. The main problem that limits the use of hexagonal image structure is believed due to lack of hardware for capturing and displaying hexagonal-based images. In hexagonal grid each unit is a set of seven hexagons compared with the traditional rectangular image architecture using a set of 3× 3 vision unit as shown in Figure 1. On a hexagonal image structure, each pixel has only six neighbouring pixels which have the same distance to the central pixel. In this report, we will construct a hexagonal structure that is converted from the traditional square structure easily and quickly using MATLAB

pic1Figure 1. Unit of vision in two image architectures

Virtual Hexagonal Structure

Using virtual Spiral Architecture, images on rectangular structure can be smoothly converted to Spiral Architecture. The Virtual Spiral Architecture exists only during the procedure of image processing. Finally, the resulted data can be mapped back to rectangular architecture for display as shown in Figure 2. The main disadvantage of using this approach is that the computation cost is high when converting between the square based images and hexagon based images.

simFigure 2. Image processing on virtual Spiral Architecture

Spiral Addressing

Unlike the square lattice, the points in a hexagonal lattice do not easily lend themselves to be addressed by integer Cartesian coordinates. This is because the points are not aligned in two orthogonal directions. Apparently, the hexagonal pixels cannot be labelled in row and column order as in the traditional rectangular structure. In order to properly address and store hexagonal images data, Sheridan proposed a one-dimensional addressing scheme for a hexagonal structure. The first step in Spiral Addressing formulation is initially labelling each of the individual hexagons with a unique address. The addresses of these hexagons will then be simply referred to as the hexagons. This is achieved by a process that is initially applied to a collection of seven hexagons. Each of these seven hexagons is labelled consecutively with addresses 0, 1, 2, 3, 4, 5 and 6 as displayed in Figure 3.

pic3Figure 3. A collection of seven hexagons with unique addresses

Dilate the structure so that six additional collections of seven hexagons can be placed about the addressed hexagons, and multiply each address by 10. For each new collection of seven hexagons, label each of the hexagons consecutively from the centre address as we did for the first seven hexagons. The repetition of the above steps permits the collection of hexagons to grow in powers of seven with uniquely assigned addresses. It is this pattern of growth of addresses that generates the Spiral as illustrated in Figure 4.

SAFigure 4. Spiral Architecture with spiral addressing

The addresses are consecutive in base seven. MATLAB functions dec2hept and hept2dec are used to convert between base 7 and decimal numbers. The important aspect of each hexagon is that it has six neighbouring hexagons. This establishes the property that for all hexagons, the centre of each hexagon has a constant distance from every one of its six neighbours.

For the whole image, following the spiral rotation direction, as shown in Figure 4, one can find out the location of any hexagonal pixel with a given spiral address starting from the central pixel of address 0. From Figure 4, it is easy to see that finding neighbouring pixels plays a very important role to locate a pixel and hence is critical in the process of the two operations defined on the SA. The location of the pixel with a given spiral address

eq1can be found from the locations of

eq2For example, to find the location of the pixel with spiral address 43, we need only know the locations of the pixels with spiral addresses 40 and 3.

Construction of Hexagonal Pixels

To construct hexagonal pixels, each square pixel is first separated into 7×7 smaller pixels, called sub-pixels. To be simple, the light intensity for each of these sub-pixels is set to be the same as that of the pixel from which the sub-pixels are separated. Each virtual hexagonal pixel is formed by 56 sub-pixels arranged as shown in Figure 5. To be simple, the light intensity of each constructed hexagonal pixel is computed as the average of the intensities of the 56 sub-pixels forming the hexagonal pixel. A hexagonal pixel, called a hyperpel, is simulated using a set of many square pixels. The MATLAB function hypel is used to simulate a hexagonal pixel on a square grid according to Figure 5.

pic2Figure 5. The structure of a single hexagonal pixel

Note that the size of each constructed pixel is

eq2.5bigger than each square pixel. Hence, the number of hexagonal pixels is 12.5% less than the number of square pixels to cover the same image. Because of this percentage, the hexagonal pixels constructed in the way above will not lose image resolution if proper light intensities of hexagonal pixels are assigned or interpolated.

Simulation of Spiral Architecture

Figure 6 shows a collection of seven hexagonal pixels constructed with spiral addresses from 0 to 6.

pic4Figure 6. A cluster of seven hexagonal pixels

From Figure 6, it is easy to see that the hexagonal pixels constructed in this way tile the whole plane without spaces and overlaps. From Figure 6, it can be easily computed that the distance from pixel 0 to pixel 1 or pixel 4 is 8. The distance from pixel 0 to pixel 2, pixel 3, pixel 5 or pixel 6 is

eq7This is close to 8. Hence, the feature of equal distance is almost retained and hence this construction hardly introduces image distortion.

Locating Hexagonal Pixels

To simulate spiral architecture, we only need to derive the way to locate the pixel with spiral address in the form of

eq3Let us use vector [0 0] to denote the location of the hexagonal with spiral address 0, and vector [j k] (j, k are integers) to denote the location of a pixel that is obtained by moving from [0 0] down (or up if j is negative) for |j| sub-pixels and towards right (or left if k is negative) for |k| sub-pixels and. If we also use L(a) to denote the location of the hexagonal pixel with spiral address a, then we have L(0) = [0 0]. From Figure 6, it is easy to see that

L(1) = [8 0], L(2) = [4 -7], L(3) = [-4 -7], L(4) = [-8 0], L(5) = [-4 7] and L(6) = [4 7]

The location of hexagonal pixel with address 10 is obtained by moving from pixel 1 in the direction from pixel 6 towards pixel 1 for two pixels distance. The MATLAB function spl_shift is used to calculate the shift from the pixel with 0 spiral address. The shift for addresses 0 to 6 are base cases for the recursive algorithm. The algorithm for multiples of 10 is given by.

eq4While the location of the pixel with a given spiral address

eq5can be computed by

eq6MATLAB Simulation of Spiral Architecture

MATLAB functions sprl2rect is used to simulate a hexagonal image represented in spiral addressing scheme. Figures 7 to 9 are MATLAB images of hexagonal images given as one dimensional array. The MATLAB script is given at the end.

fig07Figure 7. A cluster of 7 hexagonal pixels

fig08

Figure 8. A cluster of 7^2 = 49 hexagonal pixels
fig09Figure 9. A cluster of 7^3 = 243 hexagonal pixels

The Figure 10 shows a simple conversion of an image from rectangular architecture to spiral architecture. More complex examples are not considered due to high computation power requirement. The MATLAB script is given at the end.

r2sFigure 10. A simple conversion from rectangular to spiral architecture

Conclusion

In this report, a novel method to construct or mimic the Spiral Architecture has been implemented in MATLAB. This constructed hexagonal structure does not change the image resolution and introduce image distortion. It retains the advantages of the real hexagonal system such as higher degree of symmetry, uniformly connected and closed-packed form. This structure together with the light intensities cannot be displayed and it exists only in the computer memory during the procedure of image processing. Image processing based on a hexagonal structure can be implemented using this structure. The construction of this new mimic structure does not require complex computation for determining the regions of hexagonal pixels, and does not require to build a large table stored in the computer memory to record the pixel locations. The location of each pixel can be easily and quickly determined and computed using mathematical formulae.

MATLAB Code

function mat = hypel( mat, row, col, val )
%HYPEL Returns hexagonal pixels

mat(row:row + 7, col:col + 4) = val;
mat(row + 1:row + 6, col - 1) = val;
mat(row + 1:row + 6, col + 5) = val;
mat(row + 3:row + 4, col - 2) = val;
mat(row + 3:row + 4, col + 6) = val;
function dec = hept2dec(num)
%HEPT2DEC Converts base 7 number into decimal number

len = length(num2str(num)) - 1;
 
dec = 0;
 
for n = len:-1:0
    digit = fix(num / 10 ^ n);
    dec = dec + digit * 7 ^ n;
    num = mod(num, 10 ^ n);
end 
function hept = dec2hept(num)
%DEC2HEPT Converts decimal number into a base 7 number.
 
hept = 0;
temp = fix(num/7);
r = mod(num,7);
exp = 0;
 
while temp ~= 0;
    hept = hept + r * 10 ^ exp;
    r = mod(temp,7);
    exp = exp + 1;
    temp = fix(temp/7);
end
 
hept = hept + r * 10 ^ exp;
function sft = spl_shift( address )
%SPL_SHIFT Returns the horizontal and vertical shift as a 2 %element row vector.
%The address must be a base 7 number. 
 
if address == 0
    sft = [0 0];
elseif address == 1
    sft = [8 0];
elseif address == 2
    sft = [4 -7];
elseif address == 3
    sft = [-4 -7];
elseif address == 4
    sft = [-8 0];
elseif address == 5
    sft = [-4 7];
elseif address == 6
    sft = [4 7];
    
elseif mod(address,10) == 0
    len = length(num2str(address));
       
    for n = (len - 1):-1:1
        digit = fix(address / 10 ^ n);
        if digit == 0
            break
        elseif digit ~= 6
            sft = spl_shift(digit * 10 ^ (n - 1)) + ...
                2 * spl_shift((digit + 1) * 10 ^ (n - 1));
        else
            sft = spl_shift(6 * 10 ^(n - 1)) + 2 * ...
                spl_shift(10 ^ (n-1));
        end
        address = mod(address, 10 ^ n);
    end
    
else
    len = length(num2str(address))-1;
    sft = [0 0];
    
    for n = len:-1:0
        digit = fix(address / 10 ^ n);
        if digit ~= 0
            sft = sft + spl_shift(digit * 10 ^ n);
        end
        address = mod(address, 10 ^ n);
    end
end
function rect = sprl2rect( sprl )
%SPRL2RECT Converts SA into Rectangular for display.

len = length(sprl);
rad = ceil(log(len)/log(7));
size = ceil(8.06 * (3 ^ rad));
cent = fix(size / 2);
rect = uint8(zeros(size));
start = [cent cent];
for i = 0:(len - 1)
    spl_address = dec2hept(i);
    coord = start + spl_shift(spl_address);
    rect = hypel(rect,coord(1),coord(2),sprl(i+1));
end
% Sample script to display an image of spiral architecture.

image(1:7) = 80;
image(8:49) = 120;
image(50:7^3) = 180;
image(7^3+1:7^4) = 220;
sqgrd = sprl2rect(image);
imview(sqgrd);
% Sample script to convert a 3 x 3 image from rectangular % to spiral architecture.
im = uint8([120 120 120;120 20 120;120 120 120]);
new = imresize(im, 8, 'nearest');
subplot(121);imshow(new),title('Rectangular');
start = [9 10];
for i = 0:6
   coord = start + spl_shift(dec2hept(i));
   row = coord(1);
   col = coord(2);
   val = (sum(sum(new(row:row + 7, col:col + 4))) + ...
          sum(new(row + 1:row + 6, col - 1)) + ... 
          sum(new(row + 1:row + 6, col + 5)) + ... 
          sum(new(row + 3:row + 4, col - 2)) + ... 
          sum(new(row + 3:row + 4, col + 6))) / 56;
          spr(i+1) = uint8(val);
end
sqrgrd = sprl2rect(spr);
subplot(122);
imshow(sqrgrd),title('Spiral');

Resources

  • Xiangjian He, Wenjing Jia, Qiang Wu, Namho Hur, Tom Hintz, Huaqing Wang and Jinwoong Kim, ” Basic Transformations on Virtual Hexagonal Structure”, Proceedings of the international conference on Computer Graphics, Imaging and Visualization, 2006.
  • H. Wang, M. Wang, T. Hintz, et al., “VSA-based Fractal Image Compression, Journal of WSCG”, 2005.
  • Xiangjian He, Tom Hintz, Qiang Wu, Huaqing Wang and Wenjing Jia, “A New Simulation of Spiral Architecture” Proc. of International Conference on Image Processing, Computer Vision, and Pattern Recognition, 2006.
  • P. Sheridan, T. Hintz, and D. Alexander, “Pseudo-invariant Image Transformations on a Hexagonal Lattice,” Image and Vision Computing, 2000.
  • Lee Middleton and Jayanthi Sivaswamy, “Hexagonal Image Processing: A Practical Approach” Springer-Verlag London Limited, 2005.
  • This is the web version of the project report in the subject Digital Image Processing that I took in College of EME. You can download Word document from here. You can download associated paper from here and PowerPoint presentation from here.

,

Leave a comment

Linux Clustering with openMosix

The hardest thing is to go to sleep at night, when there are so many urgent things needing to be done. A huge gap exists between what we know is possible with today’s machines and what we have so far been able to finish.   Donald E. Knuth

Introduction

Supercomputer is a generic term that refers to a computer that can perform far better than an ordinary computer. Clustering technologies allow two or more networked systems (called “nodes”) to combine their computing resources. Software is an integral part of any cluster. Support for clustering can be built directly into the operating system or may sit above the operating system at the application level, often in user space. The primary drawback of second approach is that they require specially designed software, written with explicit PVM (Parallel Virtual Machine) or MPI (Messaging Passing Interface) support. When clustering support is part of the operating system, all nodes in the cluster need to have identical or nearly identical kernels; this is called a single system image (SSI). Therefore, there is no need to change or even link applications with any special library. openMosix is a typical example of SSI. The simplest approach is a symmetric cluster in which each node can function as an individual computer. A typical setup is shown in Figure 1.

fig01Figure 1

Overview of openMosix

The openMosix project originated as a fork from the earlier MOSIX (Multicomputer Operating System for Unix) project. Mosix started in 1981 at the Hebrew university of Jerusalem as a research project. Mosix was basically developed on BSD system. It was ported to Linux in 1999. In 2002 Moshe Bar, the Mosix project co-manager started the openMosix project after the Mosix project lead opted for a non-GPL license. The openMosix Project was officially closed on March 1, 2008. Source code and mail archives continue to be available from SourceForge. The original MOSIX project is still quite active under the direction of Amnon Barak. MOSIX Version 2 (MOSIX2) is a viable alternative that can be obtained at no cost for educational purposes. Basically, the openMosix software includes both a set of kernel patches and support tools. The patches extend the kernel to provide support for moving processes among machines in the cluster. Typically, process migration is totally transparent to the user.

Cluster Planning

The project is aimed at building an openMosix cluster and demonstrating its capabilities. The following methodology has been adopted.

  • Installing a basic cluster requires at least 2 network connected machines. The project uses two computers connected using Fast Ethernet (100 Mbps).
  • The project uses the Red Hat Linux 9 distribution. Its default kernel is 2.4.20-8 which is at a level with openMosix-2.4.26 we have used later.
  • The openMosix is considered stable on Linux kernel 2.4.x for the x86 architecture. The porting to Linux 2.6 kernel remained in the alpha stage. The LinuxPMI project is continuing development of the former openMosix code. It has not yet released stable patches for 2.6 series.
  • The 2.4 series of Linux kernel does not support SATA drives. The installation of Red Hat Linux 9 needs the PCs wit PATA IDE Drives. The beta version i.e. openmosix-kernel-2.6.15-openmosixbeta.i686 also has some issues with some SATA. For 2.6 series kernel, the MOSIX2 is not freely available over the internet.
  • An openMosix enable live CD, named bccd-2.2.1c14-bloat has been downloaded and checked. BCCD was developed by Paul Gray as an educational tool to facilitate instruction of parallel computing aspects and paradigms. It uses openMosix-2.4.26. It is a non-destructive overlay on top of the currently hardware.

Installing Binary openMosix Packages

  • Binary and source RPMs are also available at http://sourceforge.net/projects/openmosix. Because of availability of SMP capable processors in VLSI Lab openmosix-kernel-smp-2.4.24-openmosix2.i686.rpm has been used. As an alterative openmosix-kernel-2.4.26-openmosix1.i686.rpm has also been installed. After downloading use rpm –ivh pakage.rpm command as a root to install.
  • The kernel has been installed in the /boot directory and appropriate options have been made in the grub menu.

Installing openMosix by Recompiling

Despite its large code base (over seven million lines of code), the Linux kernel is the most flexible operating system that has ever been created. By customizing the kernel for some specific environment, it is possible to create something that is both smaller and faster than the kernel provided by most Linux distributions.

  • The set of patches for 2.4.26 kernel version was downloaded from SourceForge site. The kernel was downloaded from http://www.kernel.org/pub/linux/kernel/v2.4. The kernel source was copied in /usr/src and compiled. The command session is given below.
[root@tux root]# cd /usr/src/
[root@tux src]# tar xjvf linux-2.4.26.tar.bz2
[root@tux src]# cd linux-2.4.26
[root@tux linux-2.4.26]# cat openMosix-2.4.26-1.bz2 | bzip2 -d | patch -p1 -l
patching file arch/i386/config.in
patching file arch/i386/defconfig
patching file arch/i386/kernel/entry.S
.
.
.
patching file net/sunrpc/sched.c
patching file net/sunrpc/svc.c
patching file openMosix_MAINTAINERS
  • The next step is to create the appropriate configuration file. The output concerning the openMosic menus using the commands make menuconfig is shown in Figure 2. Configuration parameters are arranged in groups by functionality.
  • fig02Figure 2
  • Alternatively make xconfig can be used, which requires X windows and TCL/TK libraries. The main window is shown in Figure 3. The openMosix menu window is shown in Figure 4.
  • After configuration, it is time to make the kernel. It uses make dep, make clean, make bzImage, make modules, make modules_install commands. These commands take a while and produce a lot of output, which has been omitted here. The minimum options are shown in Figure 2 and 3.

fig03Figure 3

fig04Figure 4

  • As currently installed, the next reboot will give the option of starting openMosix but it won’t be the default kernel.

Configuring openMosix

While the installation will take care of the stuff that can be automated, there are a few changes that have to do manually to get openMosix running. These are very straightforward and given below.

  • The openMosix uses UDP ports in the 5000-5700 range, UDP port 5428, and TCP ports 723 and 4660. It will also need to allow any other related traffic such as NFS or SSH traffic. The firewall was configured to allow all such traffic.
  • The openMosix userland tools are available at SourceForge site. The openmosix-tools-0.3.6-2 has been installed. These are command line tools for managing and monitoring the openMosix cluster. The openmosixview-1.5 has also been installed. It is a GUI frontend to openmosix-tools mentioned above.
  • The openMosix needs to know about the other machines in the cluster. For small, static clusters, it is easier to edit /etc/hosts files for each cluster. A typical example is shown below.
127.0.0.1
192.168.1.1 om1
  • The configuration for /etc/openmosix.map is shown below. For a simple cluster, this file can be very short. Its simplest form has one entry for each machine. In this format, each entry consists of three fields—a unique device node number (starting at 1) for each machine, the machine’s IP address, and a 1 indicating that it is a single machine.
1 192.168.1.1 1
2 192.168.1.2 1
  • It is also possible to have a single entry for a range of machines that have contiguous IP addresses. In that case, the first two fields are the same—the node number for the first machine and the IP address of the first machine. The third field is the number of machines in the range. The address can be an IP number or a device name from your /etc/hosts file. For example, consider the following entry.
  • There is also a configuration file /etc/openmosix/openmosix.config. This file is heavily commented, so it should be clear what you might need to change, if anything. It can be ignored for most small clusters using a map file.

OpenMosix Up and Running

After configuration, all node are needed to be up and running openMosix. The steps are shown described as under.

  • The setpe command can be used to manually configure a node. As root, use /sbin/setpe -w -f /etc/openmosix.map to start openMosix with a specific configuration file.
  • The openMosixView extends the basic functionality of the user tools while providing a spiffy X-based GUI. However, the basic user tools must be installed for openMosixView to work. openMosixView is actually seven applications that can be invoked from the main administration application.
  • Once installed, we are basically ready to run. The main applications window is shown in Figure 5. This view displays information for each of the two nodes in the cluster. The first column displays the node’s status by node number. The background colour is green if the node is available or red if it is unavailable. The second column, buttons with IP numbers, allows to configure individual systems.

fig05Figure 5

Testing openMosix

The openMosix cluster was put o task using a CPU stress test. The openMosixView provides a number of additional tools. These include a 3D process viewer (3dmosmon), a data collection daemon (openMosixcollector), an analyzer (openMosixanalyzer), an application for viewing process history (openMosixHistory), and a migration monitor and controller (openMosixmigmon) that supports drag-and-drop control on process migration. Figure 6 shows a pictorial view of a migration monitor and controller (openMosixmigmon) that supports drag-and-drop control on process migration.

fig06Figure 6

  • The Figures 7 through 9 shows the output of openMosixanalyzer and openMosixHistory for the tested load.

fig07Figure 7

fig08Figure 8

fig10Figure 9

Conclusion

The openMosix is a powerful solution for intelligently distributing work across a cluster of Linux machines. In best-case scenarios, openMosix scales almost linearly with the CPU horsepower of the cluster, and openMosix has a very low remote execution overhead to boot. To develop a cluster on 2.6 kernel series unfinished patches by LinuxPMI project can be used. A fully functional Linux workstation or cluster node can easily run without hard drives, CD-ROMs, or floppies, which saves administration time and maintenance. Using Pre eXecution Environment (PXE) capable NIC, a diskless client can be built using Trivial File Transfer Protocol (TFTP). Moreover a heterogeneous cluster with coMosix and openMosix can be built that allows the Windows machine to run openMosix enabled Linux kernel. The Windows machines act as a cluster agent.

openMosix has a lot to recommend it. Not having to change your application code is probably the biggest advantage. As a control mechanism, it provides both transparency to the casual user and a high degree of control for the more experienced user. With precompiled kernels, setup is very straightforward and goes quickly.

Resources

,

2 Comments

2014 in review

The WordPress.com stats helper monkeys prepared a 2014 annual report for this blog.

Here’s an excerpt:

A New York City subway train holds 1,200 people. This blog was viewed about 5,000 times in 2014. If it were a NYC subway train, it would take about 4 trips to carry that many people.

Click here to see the complete report.

Leave a comment

Follow

Get every new post delivered to your Inbox.

Join 110 other followers

%d bloggers like this: