Thursday, January 18, 2018

Verifying RSA decryption equation

I was reading Wikipedia on RSA algorithm for asymmetric key encryption. At first decryption equation seemed like magic. Tried to verify quickly that raising the cipher to exponent and then doing a modulus with n will give the actual message. Below was the result.


Saturday, November 4, 2017

Who were the Samaritans?

I've always thought that the term Samaritans in the Bible was referring to all inhabitants of northern ten tribe kingdom of Samaria right after the division of united Israel (after king Solomon's death). I got interested more about them when reading the account in John chapter four where Jesus spoke with a Samaritan women near a well revealing that he is the foretold savior of world. I got intrigued by the fact that Jews in Jesus time looked down upon Samaritans. If Samaritans were simply from northern ten tribe kingdom then why would Jews look down upon their own brothers and relatives? So I thought I would do some personal study on this.

Until the time of Solomon all Israel was under a united monarchy with one king ruling from Jerusalem. The division as pronounced by Jehovah's prophet Ahijah happened during the time of Solomon's son Rehoboam. God was displeased by the presumptuousness of Rehoboam in his later years when he abandoned pure worship and led his own tribe Judah in to a course of badness prevalent among neighboring nations (1 Kings 14:22-24). So it came about that Israel was split in to two kingdoms with only the two tribes of Benjamin and Judah in south giving allegiance to rulers from David's offspring and remaining ten tribes in north (Samaria) under a different king Jeroboam, one of Solomon's officers (1 Kings 11:29-31). It can be said that majority of the prophetical books in "old testament" (Hebrew/Aramaic scriptures) starting from the book of Isaiah is dealing with God's message to unfaithful people in both kingdoms that unless they turnaround they will be taken as captives for their sins. But people in both kingdoms willfully continued practicing what was bad.

The destruction of ten tribe northern kingdom of Samaria happened in 740 BC when king Shalmaneser V of ancient Assyria invaded and took most of them as captives. Later in 607 BC the two tribe kingdom of Judah was also invaded and taken as captives by Babylonians under king Nebuchadnezzar II until their liberation from exile by the decree of Mede Cyrus the Great in 537 BC.

Coming back to my original question on the origin of Samaritans here is some thing I found from Insight on Scriptures Bible encyclopedia. Apparently my assumption that the term Samaritans was used in Bible to refer ten tribe kingdom of north was correct, but only until their conquest in 740 BC. After that the term started to have a different meaning. Assyrians had a practice of removing captives from conquered territory and transplanting in their place peoples from other parts of the empire to avoid future uprisings. So in this instance other national groups brought into northern territory eventually became intermingled both racially and religiously with remaining minority Israelites in north. At some point later the name carried more of a religious rather than racial or political connotation. Samaritans acknowledged only the first five books of the Bible (Pentateuch or Torah) by Moses as authentic. The division is very clear when Samaritans opposed Jews reconstructing their temple and walls of Jerusalem after return from exile in 537 BC. This new religion can be traced back to northern kingdom's first king Jeroboam's efforts to alienate his people from southern kingdom by encouraging calf worship in the name of Jehovah. This is so that he could prevent people from north visiting Jehovah's temple in Jerusalem located in southern kingdom and getting reunited. In time religious and political differences between Jews and Samaritans widened to the point they didn't mingle each other. Jews looked down on Samaritans as having an inferior and polluted form of worship, while Samaritans believed the opposite. Then I had my aha moment.

In a similar line the term Jews was originally applied to those from the tribe of Judah in southern kingdom. After the end of exile in Babylon this included all Israelites joined them in their restoration of worship which came to be known as Judaism. People of the nations who adopted Judaism as circumcised proselytes also identified themselves as Jews. People of the other nations were referred to as Gentiles.

What is more interesting is that Samaritans exist even until today in modern Israel! Like their ancient counterparts modern Samaritans only regard the first five books of Bible from Moses as being authentic. Their version of the first five books is called Samaritan Pentateuch (Samaritan Torah) which is almost identical to first five books of modern Bible translations. In fact it is quite accurate that some modern Bible translations use Samaritan Pentateuch as a comparative reference in their translation work. One peculiar belief of Samaritans is the special importance to Mount Gerizim which they consider as a holy mountain of God. Even today majority Samaritans live nearby this mountain and consider it as holy.

Mount Gerizim is the place near which Jehovah promised Abraham (forefather of Israelites) that he will bless his offspring and give them "this land". Jacob, Abraham's grandson also once camped in its vicinity. Later under Moses instruction in 14th century BC the tribes of Israel assembled at Mount Gerizam and Ebal and the people heard the reading of the blessings they would receive if they obeyed Jehovah and the maledictions that awaited if they disobeyed. Modern archaeologists have confirmed that due to the excellent acoustics in this area even today a large group of people could hear the words from positions in front of either mountains Gerizim or Ebal.

This all makes sense rewinding forward to 1st century CE especially when we compare the account in John 4:7-26 when Jesus was in Samaria. A Samaritan women said to Jesus "Our forefathers worshipped on this mountain, but you people say that in Jerusalem is the place where people must worship". In reply suggesting salvation not just belongs to Jews he said, "the hour is coming, and it is now, when the true worshippers will worship the Father [Jehovah] with spirit and truth, for indeed, the Father [Jehovah] is looking for ones like these to worship him".

The Samaritans also believed in the arrival of a savior just like the Jews. This is because they probably took note of what Moses said about another great prophet who will be raised by God after his death. (Dueteronomy 18:18-19) That's why she replied to Jesus "I know that Messiah is coming, who is called Christ. Whenever that one comes, he will declare all things to us openly." And then Jesus revealed to her "I am he, the one speaking to you". When touching historical facts the internal harmony of Bible is amazing even though it was written over a long period and writers themselves were not contemporaneous.



Monday, February 20, 2017

Treasure in home town

About five years ago I woke up with a news that surprised many in the city of Trivandrum (Thiruvananthapuram). It is the capital of the state of Kerala in extreme southwest of India, and I grew up around 15 miles down south from the city before I moved to United States in 2011. Archaeologists just unearthed treasures worth over $1 trillion US dollars in a much overlooked temple in the middle of the city! 

Who in the world would have thought that just another Hindu temple among the thousands in Kerala that anybody can walk in anytime hosted a grand treasure in its secret vaults underneath. Looks like a perfect set for another Indiana Jones movie is in making. The temple in spotlight is called Sree Pathmanabha Swamy Temple. It was built in around 16th century and was dedicated to Padmanabha Swamy a Hindu deity much revered by erstwhile royal family of Travancore. When India got independence from the British in 1947, both Travancore and neighboring Cochin Kingdoms joined the Indian Union and later together the Malayalam speaking region formed the state of Kerala. Since then the temples glory diminished as the royal family lost its grandiose and their chief deity became less relevant to people. 

Image of the temple from Forbes website

As a young boy I been personally around the temple many times for attending the teaching programs of Jehovah's Witnesses in a close by auditorium. The temple had no guards and it was easily accessible to public anytime. Of course not after the discovery, currently protected with machine guns, security cameras, motion detectors and seismic sensors. To mention a few, the items discovered in four vaults included golden idols studded with diamonds and other precious stones, a gold sheaf weighing over 1000 pounds, an 80 pound golden veil, hundreds of thousands of gold coins, golden artifacts, necklaces, diadems, rubies, sapphires, emeralds and other gemstones. Further two more vaults were not opened yet, since temple priests objected citing bad omens and the Supreme Court of India which directed archaeologists to investigate the matter put that on hold.

To give a comparison, being one of the largest economies in world the net GDP of present Indian economy is around $1.87 trillion USD, but researchers are estimating this treasure by antique value to be worth over $1 trillion USD. It is believed that the treasure is an accumulation of wealth over the past two millenniums by trade, tax and gifts to royal family and their predecessor kingdoms. Gold has a major role in Indian women's adornment, and even today India's obsession to gold and precious stones is well known. Likely when the British colonies were established in around 17th century, the rulers who were aware of this treasure put it in secret vaults underneath their much revered temple to protect it against plundering. Today there is already a debate among the public as to how this treasure should be used, with some suggesting that it should be used for public welfare, others dissent and opine that it belongs to the deity and should be left alone. Meanwhile the royal family is also claiming a stake on the wealth opposing the current ownership by Kerala state government and the legal dispute is currently pending before the Supreme Court of India.

As someone interested in history of Christianity and biblical archaeology in general, among the discoveries what particularly stroke me was over one hundred thousand golden coins dating back to 1st century Roman Empire with imprints of contemporary Caesars. No wonder Roman politicians and historians are on record decrying the loss of silver and gold to buy commodities from India to pamper Roman wives. 

It is undisputed that Christianity in India existed at least from 5th century AD. However Saint Thomas Christians, an ancient community of Christians in Kerala trace back their origins to 1st century AD. The doctrines and practices of modern day Saint Thomas Christians doesn't differ much from that of Roman Catholics, with tradition and creed superseding scriptural authority. They assert by tradition that Thomas the apostle of Jesus traveled to South India and convinced their ancestors who were Hindu priestly class to mass convert to Christianity. Though it is a possibility, there is no solid evidence or record for this. The Bible does mention India a few times such as in the Book of Esther as a boundary for 4th century BC Persian empire by Xerxes I and in the Book of Revelation using the words "Indian spice". However the Bible never mention much about the activity of Thomas the apostle after Jesus' death and resurrection. Regardless a number of 3rd and 4th century Roman writers mention Thomas' trip to India. 

Another fact is that there is an ancient body of Jews in Kerala called Cochin Jews, most immigrated to modern Israel after independence. They claim that their ancestors arrived in Kerala during the time of King Solomon to do trade. In the Bible we read accounts of King Solomon having a fleet of trading ships, which bought from far lands among other things peacock, particularly found in Indian subcontinent. Though we are not sure if they lived in Kerala during Solomon's time in 10th century BC, historians agree that Cochin Jews existed at least since 1st century AD in Kerala. So it is possible that a Jewish missionary in first century joined a Jewish merchant to reach the shores of Kerala via the Arabian sea.

I read in one of The Watchtower magazine some years ago that an apostle could have easily taken a trade ship to reach India or even further southeast to Thailand, Cambodia, Sumatra, and Java. Jesus' disciples were commissioned to preach the good news to the most distant parts of then earth and later in his epistle to the Colossians Paul mentions that the good news was preached in all creation under then heaven. 

This discovery solidifies the claims by both Cochin Jews and Saint Thomas Christians, however only the apostle knows if he ever visited India.


Sunday, January 27, 2013

Energy Efficient Ethernet - Performance Analysis

Energy Efficient Ethernet was a recent development in the field of computer networks which aims at minimizing use of energy over networks. The idea for saving energy in communication systems was proposed as early as 2003 and its implementation in Ethernet links was officially made as a standard by IEEE 802.3az task force. It is estimated that the internet core is consuming about 6TWh power each year and it keeps growing. One of the major power consumption is in Ethernet links. Since links can be physically long significant power would be needed to transmit information through the wires. IEEE standard defines a low power mode for idle links and thereby encourages saving energy

Description of EEE standard


EEE concept is described in figure (1) as seen in the Reviriego et al. 2009. Link is made active when a packet arrives and when no packets are left link enters in to a low power mode. Periodically link is made active for a short time to make sure that it is working. This is denoted as a refresh cycle in figure. Table (1) shows the proposed mean sleep time, wake-up time from Reviriego et al 2009.

Simulation experiments

Simulation of EEE was done using the CSIM. CSIM is a simulation library from Mesquisite software. It provides facility for simulating queues. It is believed that the arrival of packets in Ethernet networks follows an exponential distribution and therefore EEE can be simulated as a Poisson process. Coincidentally packet arrivals and leaving on Ethernet links can be modeled as an M/M/1 queue. Service center would be link and queue will be packets arrived on link. Simulation was done with 5000 packets each for 100Mbps, 1Gbps and 10 Gbps. Energy consumption for link was calculated using following known formula.

= Plow power  · (1 − load) + Pactive · load

 Plow power is the power consumed in low power mode and Pactive   is the power consumed when link is active. Load was increased from 0 to 100 at intervals of 5. It is assumed that both forward and backwards packet transfer between the links are independent of each other. I also neglected refresh cycle since it has little effect on performance. Further bulk arrivals were simulated using geometric distribution with their means equivalent to desired burst length. In this experiment I used mean burst lengths of 2, 5 and 10 to find its effect on power consumption. Finally I did experiments on real world packet traces collected from a personal computer. Trace files used in this experiment were collected from a 100 Mbps Ethernet link. Trace files were collected when user did a typical browsing, downloading and surfing on internet.

Simulation Results


Results of the simulation on regular EEE model is plotted in the graphs shown in figures (2), (3) and (5).


Results for the simulation on regular EEE was as expected. For burst arrivals we notice that the performance is improved when burst length is increased. Table II shows results for real world packet trace analysis.








Results Analysis


Graphs for regular EEE at various loads show that performance is as expected. Energy consumption is proportional to traffic of the packets as inferred from results. In 100Mbps, results are close to proportional (ideal) case. However in 1Gbps and 10 Gbps links, results are not good especially when traffic is high. It appears that the link is spending more time in sleeping and waking up at higher traffic.

When packets appear in burst, performance is improved as expected. This is because link is made to wake up and sleep only for whole burst packet length. More the burst arrivals, more the performance getting close to ideal case.

For real world data, power consumption in EEE looks very low when compared to that of normal Ethernet. This might be because packet arrival rate in real world is higher than that of in simulation models and hence link is in sleep most of the time.

Enhancing EEE

Improving EEE using predictive packet arrival


From our results we see that the performance is affected in high speed links when the packets arrive at high speed because link would be spending more time in sleeping and waking up. To overcome this issue I propose to make use of a predictive sleep method in which we sleep only if the queue is empty and mean arrival delay till the last packet is greater than sleep time. By doing so we could overcome the overhead issue due to continuous sleep and wake up in high speed networks; however we would be incurring a penalty if  prediction was wrong. If a packet did not arrive within the mean delay time we would need to sleep. Therefore penalty for a failed prediction in that case would be

Penalty = Mean packet arrival delay + TS

However before making any judgments it is better to analyze the proposed model using simulation.

Simulation experiments


Experiments were conducted for the proposed enhancement method using CSIM Software. When each packet is leaving the system we check if the queue is empty. If the queue is empty we next verify that the mean delay for past packet arrivals is less than sleep time. If that is the case then we continue without sleeping, otherwise we would sleep. If packet arrives before the predicted mean delay we gain a power loss for the time equivalent to the difference between sleep time and mean packet delay time. If a packet did not arrive before the predicted mean delay time we incur the penalty described above. 

Simulation Results


The result of the proposed simulation model is shown in figure (8), (9) & (10).






Result Analysis

The simulation results of the proposed model show that it could improve the performance without losing any packets. It also shows that the proposed method would work better for 100Mbps. The graph gets skewed toward the ideal case. Notice that a slight variation could produce increased cost benefits, and therefore this method looks better than the original proposal theoretically. There is no packet loss in this suggested improvement.

Summary


In this post we reproduced the results of EEE simulation. We found that when burst arrivals are high performance in EEE is enhanced. It is also noteworthy that given the round trip time on typical internet servers are in milliseconds, the small delay in terms of micro seconds in the Ethernet links is negligible when compared with the significant economic benefit. We also proposed a method to improve the performance of EEE without packet loss. However we need more testing of the proposed system using real data before assuring its enhanced performance.


Wednesday, November 7, 2012

Edge and circle detection

Edge detection is an important application of Image processing. As the name indicates the idea is to detect edges in an input image and to highlight it using image processing algorithms. Different methods exist today to detect edges and the most commonly used algorithm is Sobel edge detection. Sobel edge detection is a direct application of differential calculus. Circle detection is an extension of edge detection in which we aim to find circle like edges in input image. Hough transform is an important geometric method to find circles from edges in an image. In this article we will discuss both the concepts and its implementation, both in gray-scale and color images.

Edge detection

As we know a digitized image is represented in a computer as an array of two-dimensional pixels. A pixel is a smallest unit inside an image which can be uniquely captured using the camera. The number of pixels in an image depends on the resolution capacity of the camera. In gray scale image each pixel corresponds to the intensity level in that particular pixel and its value ranges from zero to 255. In color images each pixel has red, green and blue color levels with values ranging from zero to 255. Theoretically a mixture of these three colors can generate any visually identifiable colors of human perception.

In edge detection our aim is to identify portions of the image where information is densely populated. This means we are interested in identifying those pixels which form edges in an image. Edges in the image are identified by comparing it with the pixel intensity of  neighboring pixels. Larger the difference or variation in brightness of pixel values, larger the likelihood that it is an edge pixel. Therefore our interest is to identify those pixels which significantly differ from its neighboring pixels. 

The application of calculus comes in to play here. We know that calculus is the study of change just like geometry is the study of shapes. Assuming that the pixel values in an image forms a discrete function, our aim is to find the points in the discrete function whose slope is higher. Since an image is a 2-D function, operators describing edges can be expressed by using partial differential equations. The points lie on a edge can be detected by detecting the local maxima or minima of the first derivative or by detecting zero-crossing of the second derivative. The idea is described in figure (1) for 1-D analysis. However since noise in an image often forms pseudo-edges we have to pre-process the image. Therefore edge detection can be described in four steps as below.

(a)   Smoothing – to reduce noise without destroying true edges
(b)   Enhancement – improve the quality of the edges (eg. by improving sharpness)
(c)   Detection: find the edge pixels
(d)   Localization: find the exact location of edge. (eg. linking edges together)





Figure (1) - Idea of edge detection in 1-D intensity signal function. Changes in edge can be detected using local maxima or minima of first derivative or using the zero-crossing in the second derivative. (Source here)


Derivative of a 1-D signal can be computed by approximating derivative by finite differences. 

Therefore








Mask for 1D signal: [-1 0 1] (centered about x)

Computing the second derivative gives,









Mask for 1-D signal using second derivative: [1 -2 1] (centered about x)

Based on the 1-D theoretical analysis, the same idea can be extended to two dimensional pixel planes and one such extension is known as Sobel operator. Sobel operator performs an accurate approximation to calculate derivative of two-dimensional image by computing spatial gradient measurement of an image. Sobel detector uses a pair of 3 x 3 convolution masks, one for x direction and other for y direction. Sobel operator for two-dimensional image is as follows and it slides over image.

Figure (2) – Sobel operator for edge detection in images.

The magnitude of the gradient is calculated using the resultant formula:

The direction is calculated by using inverse tangent of the gradients in each direction.
















.
Figure (3) – Gradient edge and direction (source)

Some of the results of applying Sobel operator in grayscale images and color images are shown below. In color images we compute the intensity and use it for edge detection.

Intensity  I = (red + green + blue) / 3

After computing the edges, thresholding is applied to highlight edges which are highly likely. Again we can highlight those edges which are in a particular direction by thresholding edge intensity image using computed direction information.


Figure (4) Original Image, Edge image, Thresholded edge image and direction thresholded edge image (clockwise). ROI (x,y,sx,sy) = (10,10,450,620), threshold value = 80 and direction threshold value = 80 to 90 degrees.


Figure (5) Original Image, Edge image, Thresholded edge image and direction thresholded edge image. The ROI (x,y,sx,sy) = (10,10,450,620), threshold value = 80 and direction threshold value = 70 +- 10  degrees.



Figure (6) Original Image, Edge image, Thresholded edge image and direction thresholded edge image. The ROI (x,y,sx,sy) = (10,10,550,550), threshold value = 80 and direction threshold value = 45 +- 10 degrees.

Circle detection using hough transform

Circle detection in image processing is done using Hough transform. Hough transform is a feature extraction technique to find imperfect instances of objects within a certain class or shape. This is done by parameterization and then voting the parameter space to find a local maxima. First we compute the edges of image using edge detection. Then we threshold the edge image so that we can find significant edges. Now we have to find those edges which form a circle. Note that after edge detection circumference of the circles might not be connected clearly. So we apply Hough transform.

A circle can be described completely with three pieces of information: the center (a, b) and the radius R.

x = a + Rcosθ
y = b + Rsinθ

When the θ varies from 0 to 360, a complete circle of radius R is generated. We note that for a circle the parameters (a, b, R) is constant. In the parameter space we plot the co-ordinates with (a, b) boundary equivalent to the set of all possible centers in a given image where θ ranges from 0 to 360. For each edge points that corresponds to (x,y,R) of a particular circle in real space we draw the sphere in the corresponding (a,b,R) parameter space. If we are looking for circles of a particular radius R then we have a 2D parameter space. 


Figure (7) – Each point in the geometric space (left) generates a circle in parameter space (right). The circles in the parameter space intersect at (a,b) the center of the circle in geometric space.(source)

Rearranging the equations we get

a = x1 – Rcosθ
b = y1 – Rsinθ

After plotting the circles in parameter space, we will note that the points at which circles in parameter space intersect correspond to the center of the circle in real space. To find circles which are more likely true we compute intersections which have a high density. This is done by sampling the parameter space with a suitable bin size. Once we compute the local maxima we highlight the circle in the original space. Some results for both grey scale and color images are shown below.


Figure (8) Original Image, Edge image, Thresholded edge image, PSpace image and Resulted circle. The ROI (x,y,sx,sy) = (10,10,300,300), threshold value = 80 and radius = 33 px.




Figure (10) Original Image, Edge image, Thresholded edge image, PSpace image and Resulted circle. The ROIs (x,y,sx,sy) = (110 10 200 200)(110 280 200 200), threshold value = 80 and radius = 90 px.



Figure (11) Original Image, Edge image, Thresholded edge image, PSpace image and Resulted circles. The ROIs (x,y,sx,sy) = (180 220 80 80) (180 320 80 80), threshold value = 80 and radius = 11 px.


I have included sample code in c++ for edge detection and hough transform. Code for classes ROI, Image are excluded.

Thursday, October 25, 2012

Histogram Equalization

Histogram is a graphical representation of the tonal values of an image. In greyscale image we have only one channel, and its value range from 0 to 255. Based on the number of pixels falling under a particular tonal value we plot the histogram graph. 

Grey histogram Equalization

In Grey histogram equalization we enhance contrast of images by using usable pixel values in the image to the close contrast values of the display device. This is accomplished by spreading out the most frequent intensity values to the neighboring intensities. First we compute the cumulative distributive function of histogram. Then we use the general histogram formula to accomplish this.
The general histogram equalization formula is:

Where cdfmin is the minimum value of the cumulative distribution function, M × N gives the image's number of pixels and L is the number of grey levels used. Some sample results are shown below. Note that equalization is done within the two region of interest.

(a)   Original Image

(b)   Histogram for ROI 1 before and after equalization ( x = 10, y = 10, sx = 300, sy = 300)



(c)    Histogram for ROI 2 before and after equalization ( x =315, y =315, sx = 400, sy = 400)

(d) Resulted equalized image



Color Histogram Generation (RGB)

In color images we have three channels namely red, green and blue. Therefore in order to generate the histograms we apply the same principle for greyscale images separately for each channel.

Color Histogram Equalization (RGB)

In color histogram normalization we apply the same method used for grey-scale equalization for each of the three channels separately. The results are shown below.

(a)   Original Image
(b) Histogram for ROI 1 – Before and after equalization - RGB ( x = 10, y = 10, sx = 300, sy = 300)

(c)   Resulted equalized image (all channels together)

(d)   Equalization separately - Original and  RGB channels respectively (Clockwise)



               

HSI histogram generation

HSI is a color model which is more intuitive and perceptually relevant co-ordinate space. It has wide applications in the field of computer graphics and vision. Like RGB it has three channels namely Hue (H), Saturation(S) and Intensity (I). Hue falls from 0 to 360 degrees, and other two falls from 0 to 1. For the sake of calculations we make saturation to fall between 0 to 99 and Intensity to fall from 0 to 255 respectively. For HSI histogram generation we need to convert the RGB color model to HSI. We then generate histogram for the three channels separately. The formula for HSI to RGB and from RGB to HSI is below from the Gonzales and Woods text.


HSI histogram equalization

After generating HSI histogram we then compute the equalized histogram from it. For that we make use of the same histogram formula we used before. After equalization we then convert it back to RGB image for display. The resulted images are shown below.

(a)   HSI histogram for I channel – Before and after equalization (x = 10, y =10, sx = 300, sy = 300)
(b)    HSI equalization (original and I channel respectively)


Program

Some of the functions I used to do above operations in C++ are in Git here. Note that the custom class Image and ROI are not included here. However this code is enough for explaining the main logic.