28.11.14

Types of Exponents

Definition: A universal exponent of the positive integer n is a positive integer U such that

aU = 1 mod n

for all integers a relatively prime to n

Example 1: By Euler's theorem

aφ(n) = 1 mod n 

for all a relatively prime to n. Therefore, φ(n) is a universal exponent of n.

Example 2: By Claim 1 that I proved here, if n is the product of two distinct primes both greater than 2, then:

 aφ(n)/2 = 1 mod n 

for all a relatively prime to n. Therefore, φ(n)/2 is a universal exponent of n.

Clearly, when n is the product of two distinct primes both greater than 2, then n has at least 2 universal exponents, namely φ(n) and φ(n)/2. Although I proved this logically, the behaviour can be observed in any exponentiation table in Zwhen n is the product of two distinct primes both greater than 2.

Example 3: Below is the exponentiation table for Z35 where n = 5 * 7 = 35, the smallest safe primes.
φ(35) = (5-1)*(7-1) = 24  and φ(35)/2 = 24/2 = 12 and so note the column below the 24th exponent and the 12th exponent and see how identical they are.



Universal exponents are useful but there are other types of exponents that prove to be useful in generating exponentiation tables of Zn.

In the Exponentiation tables in Zn  post I observed several peculiar behaviours of specific tables, which need to be proven in general.

Claim 2: Given a positive integer n, then

(n-1)2 = 1 mod n

Proof: A nice and simple direct proof from elementary algebra.

(n-1)2 = [(n-1)*(n-1)] mod n
= (n2 - 2n + 1) mod n
= (n2 mod n) - (2n mod n) + (1 mod n)
since any multiple of n is divisible by n
= (0 mod n) - (0 mod n) + (1 mod n)
= 1 mod n

.'.

This gives rise to an even bigger claim and its proof explains why the last row of any exponentiation table is a repetition of 1 and n-1

Claim 3:  Given two positive integers n and x such that x < n then either

(n-1)x = 1 mod n     if x is even
or
(n-1)x = n-1 mod n     if x is odd

Proof: Again, direct proof from elementary algebra.  

Case 1: If x is even then x = 2k for some positive integer k 
(n-1)x =  (n-1)2k mod n 
= (n-1)*(n-1)*(n-1)*...*(n-1) mod n            2k factors
= (n2k - 2kn2k + ... - 2kn + 1) mod n            where ... represents decreasing powers of n
= (0 - 0 + ... - 0 + 1)  mod n                         since any multiple of n is divisible by n
= 1 mod n

Case 2: If x is odd then x = 2k + 1, so
(n-1)x =  (n-1)2k+1 mod n
= [(n-1)2k]*[(n-1)1] mod n                                  
= [1 * (n-1)] mod n                       by Case 1
=(n-1) mod n

.'.

In Finding Phi it was shown that φ(n) is even and in fact it is 2x even in the case when n is the product of two distinct odd primes p and q since φ(n) = (p-1)(q-1) and since p and q are both odd primes then both (p-1) and (q-1) are even integers.

By definition of an even integer,
(p - 1) = 2r 

for some positive integer r strictly smaller than p and 

(q - 1) = 2s 

for some positive integer s < q, so multiplying (p-1) times (q-1),

φ(n) = (p-1)*(q-1) = 2r * 2s = 4rs

So φ(n)/2 = (4rs)/2 = 2rs and since the order of any integer smaller than and relatively prime to n  divides φ(n)/2 when n is the product of two odd primes, then the following different types of smallest exponents, or finite orders of integers relatively prime to n in the cyclic group Zn  are possible:

  1. a2rs  = 1 mod n  
  2. brs = 1 mod n
  3. cr = 1 mod n
  4. ds = 1 mod n
  5. e2 = 1 mod n
  6. 2r  = 1 mod n  
  7. g2s  = 1 mod n  
where a,b,c,d,e, r, s are all positive integers.

Example 4: Clearly (n-1) belongs to the 5th type since it was proven in Claim 2 above that

(n-1)2 = 1 mod n


11.11.14

Finding Phi

Euler's phi function, namely φ(n), pops up in many odd places even though φ(n) is always even. 

Definition 1: φ(n) is the number of integers smaller than n that are relatively prime, or coprime to n. [Page 227 from Elementary Number Theory, by Kenneth H. Rosen.]


Theorem 00: If n is the product of two distinct primes p and q, then 

φ(n) = (p-1)(q-1). 

Proof: If n is the product of two distinct primes p and q then φ(n) = (p-1)(q-1) because for any prime p its greatest common divisor GCD with any integer other than itself is 1, therefore  the number of integers coprime with p is p-1. So if p and q are prime integers, then:


φ(p)*φ(q) = (p-1)(q-1) = φ(n)


Question: Is it possible to find φ(n) without factoring n to find the values of p and q?




The answer is yes and the next paragraphs explain why and how to obtain the value of φ(n) without factoring n.

Theorem 0φ(n) is even when n = p*q where p and q are 2 distinct prime integers.

Proof: All prime integers greater than 2 are odd since by definition of an even integer e, e is 2 times some other integer, namely  e = 2k for some positive integer k in Z, 
therefore e is divisible by 2 and yet a prime integer is only divisible by itself and 1.

Therefore, all primes greater than 2 are odd and by definition an odd integer is an even integer plus one, so if p is prime then p = 2v + 1 for some v in Z and since p-1 = (2v+1)-1=2v then for all primes p, p-1 is an even integer. (p-1)(q-1) is also even since say for some primes p, q  p-1 = 2r for some r in Z and q-1 = 2s for some s in Z. Therefore,


 (p-1)(q-1) = 2r2s = 4rs = 2(2rs) 

and since 2,r,s are all integers in Z, which is closed with respect to multiplication, then their product is also an integer in Z. Therefore, (p-1)(q-1) is an even integer. Therefore φ(n) is even when n = p*q where p & q are prime integers .'.

Since φ(n) is even when n is the product of 2 primes, then φ(n)/2 is a whole integer as well.

Euler also came up with the term primitive root to describe integers whose order is exactly φ(n). The order of an integer mod n is by definition:

Definition 2: The order of an element a in Zis the smallest integer k such that ak= 1 mod n. [Page 334 from Elementary Number Theory, by Kenneth H. Rosen.]

Euler correctly saw and proved that: 

aφ(n) = 1 mod n for any a co-prime with n. 

Euler also came up with the term primitive root, which he defined as:

Definition 3: If r and n are relatively prime (co-prime) integers with n > 0 and if the order of r mod n is equal to φ(n) then r is called a primitive root modulo n. [Page 336 from Elementary Number Theory, by Kenneth H. Rosen.]

Euler also correctly saw that every prime has a primitive root but his proof for this was incorrect. Lagrange provided the correct proof years later and in fact it can be shown that:

Theorem 1: A positive integer n has a primitive root if and only if it is of the form 2, 4, pt, or 2p where p is prime and t is a positive integer in Z.

Proof:  See pages 351 to 353 from Elementary Number Theory, by Kenneth H. Rosen. In particular, Theorem 9.15 from chapter 9.3: The Existence of Primitive Roots


Example 1: Below are a few examples of exponentiation tables in  Zn, which among other things reveal the order of elements that are co-prime with n. When n is 6  by Theorem 1 it must have a primitive root because it is of the form 2 times 3. The exponentiation table for Z6 reveals that 5 is a primitive root of 6 because 52 = 1 mod 6 and φ(6)=(3-1)(2-1)=2. Similarly, 10 = 2*5 so by Theorem 1 it should have a primitive root as it does.  


An exponentiation table to find orders of elements in Zwhen n is equal to 6 or 10


Example 2: When n is the product of two distinct primes both greater than 2, then by Theorem 1. n will not have any primitive roots as is shown in the table for Z35 when n = 5*7. In this case φ(35) = (5-1)*(7-1) = 24 but the smallest integer k such that ak= 1 mod 35 for any a in Z35 is 12, which is half of φ(35).


An exponentiation table to find orders of elements in Z35

The implications of this wicked construct, the grupoid  Zn under exponentiation, are not immediately obvious unless you are hunting for φ(n). 

Claim 1: The order of any element co-prime with n in the group Zn under multiplication when n is the product of two distinct primes p and q where p >2 and q >2 divides φ(n)/2

Proof:  Suppose that φ(n) is the smallest integer such that



aφ(n) = 1 mod n 

for any a relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2

The order of the group composed of all integers co-prime with n when n is the product of two distinct primes greater than 2 is φ(n) and for every element a relatively prime to n if has order k, then by Lagrange's Theorem the order of a divides the order of the group , namely k divides φ(n). Since it was assumed that φ(n) is the smallest integer such that  aφ(n) = 1 mod n  then k must be equal to φ(n).

However since n=p*q for some primes p and q both both greater than 2, then n does not have any primitive roots.  [See pages 351 to 353 from Elementary Number Theory, by Kenneth H. Rosen. In particular, Theorem 9.15 from chapter 9.3: The Existence of Primitive Roots]


In other words, the group composed of all integers co-prime with n does not have any elements a relatively prime to n, whose order equals φ(n).Therefore, φ(n) is not the smallest integer such that  aφ(n) = 1 for any a relatively prime to n when n is the product of two distinct primes p and q where p >2 and q >2.

Therefore, the maximum order than an element of the group composed of all integers co-prime with n when n is the product of 2 distinct odd primes can have is φ(n)/2  since 2 is the smallest integer > 1 to divide φ(n), which by Theorem 0 is an even integer.'.

Finally Finding Phi

To find φ(n), one must find which are the elements with the maximum order. 

Note that by Theorem 1: 
2 times any prime always has a primitive root yet if 2 does not divide n and n is the product of 2 primes p , q > 2 and p is not equal to 2 then the following conjecture arises: 

16.10.14

Safe Check

Back in September of 2012, I went to a Facebook Developer's Hackathon in Vancouver where in less than 7 hours my team (consisting of me and my husband) developed an app called Famcheck. It basically grabbed the location of a user's closest people, fired an API call to Wunderground to check if there are any severe weather alerts for the areas where they live, and gave the user a chance to call their closest people using Twilio API.




What was unique about it was the fact that it used the Graph API to make a "call a person" action or whatever and so it won the award for Best Open Graph app. You won't actually see any mention of it anywhere on Facebook other than somewhere in the beginning of this group. This is how I learned to only go to hackathons that promise free software that I can use in my more profitable ideas.

I really didn't expect it to win anything especially since Facebook supposedly cut access to survivors of the Haiti 2010 earthquake because they were overwhelming the system. I don't have family in Haiti but I do have family in other eathquake prone areas such as Bulgaria and Japan.


I won an iPad and not a single mention of it anywhere on FB.
Silicon Valley is not a meritocracy. It's an oligarchy.

Anyway, winning felt good. Being accused of winning only because I'm cute didn't. That's right, after the ceremony a sore Vancouverite loser came up to me and told me that I only won because I'm cute and not because my app was based on a great idea that used 3 different APIs and was built in less than 7 hours.

I dropped Famcheck from my list of apps I care to work on and since then I've moved on to implementing other, more profitable ideas but it was always a sore spot. Until today.

Today Facebook released a new tool called "Safety Check".

8.10.14

Exponentiation Tables in Z sub n

The following post describes Zunder exponentiation where n is the product of two primes.  Each entry in each exponentiation table here is constructed by raising the row index a to the power of the column index b mod n. Note that since this construction is not Abelian the opposite statement does not hold in its exponentiation tables. The post was inspired by a small discovery I came across while taking CMPUT 210 at the University of Alberta.

Zn is closed with respect to exponentiation since for all a, b in Zn, ab = a*a*a*a*... (b factors) and since Zn is closed with respect to multiplication then a*a*a*a*... (b factors) is also in Zn.

However, Zn under exponentiation is not Abelian since ab is not always congruent to ba mod n, therefore most of what was said about multiplication tables in Z sub n and addition tables in Z sub n doesn't necessarily hold.


In fact, Zn under exponentiation as constructed below where n is the product of two primes is not even a group.


So, is it still possible to generate exponentiation tables for Z without actually computing the greatest common divisor of (ab, n) for all a and b in Zn?


11.9.14

Multiplication Tables in Z sub n

Here I talked about finding patterns to generate operation tables in Zn and I provided a pattern for fast generation of addition tables in Zn.

The group Zn is also closed with respect to multiplication, i.e. for all a, b in Zn, the result of a*b is also in Zn.

Let's consider a few statements, which also hold true in Z:
  1. Zn is Abelian, or in other words for all a, b in Zn, a*b = b*a
  2. All entries in the first row and the first column of the multiplication table of Zn are always 0 since 0*a=0 for all a in Zn;
  3. The second row or column of Zn lists all elements in Zn since 1 is the identity element in Zn  and so 1*a = a for all a in Zn;
  4. If n is a prime p then every column or row contains all elements of Zn without duplicates since Z sub p is an integral domain;

#4 ensures that there are two distinct types of multiplication table patterns of Zn depending on whether n is prime or composite. The multiplication table of Zn when n is composite may contain rows and columns with zero divisors, or duplicate entries.

So let's start with a few multiplication tables of Zn when n is prime.

If n is prime, then n is either 2 or n is odd since all even integers are divisible by 2 and all prime integers are only divisible by themselves and 1.

Therefore, if n > 2, then the last element of Zn, namely n - 1 is even (since by definition every odd integer n can be represented as 2q + 1 for some q and so n - 1 =  (2q + 1) - 1 = 2q, and 2q is by definition an even integer (1A) ), which means that the meat of the multiplication table, or in other words, all non-zero rows of the table, can be equally divided into 2 sets, i.e. one set Alpha starting from row 1 to row (n-1)/2 and another set Alpha_Upside_Down starting from row [(n-1)/2]+1 to row n-1.(2A)

Since Zn is Abelian, then Alpha_Upside_Down is simply the inverse of Alpha. The same argument holds for the columns of the multiplication tables of Zn, when n is prime, i.e. they can be equally divided into two sets where one is the inverse of the other. (3A) A few examples below when n = 5, 7, and 11:


Upside down alpha (TM)

In other words, only a pattern for the first half of the multiplication table is needed to generate the whole thing because the second half is just a mirror image of the first half. (0A)

The second interesting observation one might have is that row 2 in each table (k = 2) lists all even, then all odd integers up to n-1. For example, in row 2 of Z5 we have (2,4,1,3).  Similarly, in Z7 there are (2,4,6,1,3,5), and in Z11 there are (2,4,6,8,10,1,3,5,7,9). This is because n - 1 is even as shown in (1A)

In each subsequent row there appears to be a shift by k integers where k is the row index of the table about the identity element. But how can it be known where the identity would fall on each row without doing any calculations?

Firstly, on each row k > 1 the identity element 1 always falls right behind n - (k - 1) , and the integer after the identity is always k + 1


Another interesting observation is that the rows of these examples can be divided into consecutive subsets that seem to be dependant on each other.

For example the 3rd row of Z11  is [0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8] and it can be divided into several consecutive subsets, namely: (0, 3, 6, 9), (1, 4, 7, 10), (2, 5, 8).  Note that these subsets may not have the same cardinality: some may have more elements that the others.

Clearly,  the second subset is simply the first subset shifted by one up to n-1, and the third subset is just the second subset shifted by 1 up to n-1"

An intimate close-up of the multiplication table of Z11


Similarly, the 4th row of Z11 can also be divided into several subsets, namely: (0,4,8),(1,5,9),(2,6,10),(3,7) and once again every subset is a shift of 1 from the previous subset.

In both rows 3 and 4 the last element kfirst_last of the first subset is equivalent to n-(k-1) where k is the row index.

But what happens if the last element kfirst_last of the first subset is not equal to n-(k-1)?

In Z11 for example, this happens in row 5: (0,5,10),(4,9),(3,8),(2,7),(1,6). The last element of the first subset is 10, the first element in the second subset is 1 less than the first element of the first subset. 1 =  11 - 10

If  kfirst_last is not equal to n-(k-1), then it appears that the next element after kfirst_last is (n - kfirst_last ) less than the first element of the first subset (4A) until n-(k-1) is reached, which changes things a bit, but more on this later.

On another note, as a direct result of (2A), the last column of each multiplication table is simply the inverse of column 1, which is known in its entirety since 1*a = a for all a in Zn

In other words, the last element of the last subset is always n-k, so if n-k is reached then it is certain that the end of the row is reached where k is the index of the row.(5A)

Also if the current row k is equal to (n-1)/2, then the first half of the multiplication table has been reached, and the second half is trivial to generate since it is the inverse of the first half since the group is Abelian.(6A)

Here's a bigger example, which reveals the bigger picture, (and how tiny my handwriting really is)

Each element in the table is computed as GCD(ki*kj, 23)
 for all rows and columns ki, kj  
Also, the total number of integers in the first half of the table is n*((n-1)/2) since there are n columns and ((n-1)/2) rows in the table.(7A)

So, to sum up the algorithm for generating the first half of the multiplication table of Zn when n is prime without actually computing the GCD(each_row_index*each_column_index, n) so far from the points made in 2A, 3A, 4A, 5A, 7A:

  1. (Generate a subset with starting index ki ,while starting index ki is less than or equal to n-1 shift it by k, add that subset to a table T, (return T if it reached the n*((n-1)/2)th index)
  2. If the last index of that subset is equal to  n - ( k - 1 ) then go to (1.) with  k= 1, k = k, and table T; 
  3. Else if the last index of that subset is equal to n - k then go to (1.) with k= 0, k = k+1, and table T; 
  4. Else if the last index of that subset is less than n and the row k is less than n/2 then shift  new_ki = k-(n - ki) and go to (1.) with k= new_k,  k = k, and table T;
  5. Return table T;

The following Javascript implementation, which showcases exactly how "creative" my javascripting skills are, spits out the most desired first (n-1)/2 rows of the multiplication table of Zn when n is prime.

//Author: Marina Ibrishimova
//generating the first half of the multiplication table of Zn 
//when n is prime without actually computing
//the GCD(each_row_index*each_column_index, n)
function HammerTime(ki, k, n, table_so_far) {  
  var len = table_so_far.length;  
  var half_table_slots = n*((n-1)/2);  
  if(len == half_table_slots) {return;}  
  else {   
   while ( ki <= (n - 1)) {  
   table_so_far.push(ki);  
   ki = ki + k;  
   }  
   len = table_so_far.length;  
   var last_inset = table_so_far[len-1];  
   var k_dist = n - last_inset;   
   var new_ki = k - k_dist;   
   var n_k = k + 1;  
   if(last_inset == n-(k-1) && k < n/2) { HammerTime(1, k, n, table_so_far); }  
   if(last_inset == n-k && k < n/2) { HammerTime(0, n_k , n, table_so_far);}  
   else if(last_inset < n && k < n/2){ HammerTime(new_ki, k, n, table_so_far); }  
   }  
   return table_so_far;    
 }  


So far I've only discussed the multiplication table of Zn when n is prime, but it is easy to modify the existing algorithm to accommodate for the differences between the multiplication table of Zn when n is prime and the multiplication table of Zn when n is the product of 2 or more primes.

The main difference in the multiplication table of Zn when n is the product of 2 or more primes is that certain rows will contain 0 divisors, or in other words, integers a > 0, b > 0 such that a*b = 0 and as a result of this the first subset may repeat k times until the end of the kth row. Such rows are easy to spot because the last element of the first subset in that row will always be n-k.

The other difference is that in Zn when n is the product of 2 or more primes (n-1) may be odd but 2A still holds since Zn is Abelian for any n in Z. So when n is composite and (n-1) is odd, the number of rows needed to generate the first part of the table is the ceiling of (n-1)/2

Here is a better algorithm for generating the multiplication table of Zn

DISCLAIMER: I'm not sure if any of this has been done before because every time I go to search for something useful on the interwebs, I end up looking up adorable kittens instead. It's not in any of the textbooks I own so that's why I pursue it mostly during my lunch break but in case this has been done before then all I can say is, "Great minds think alike".  
If, however, it hasn't been done before, please contact me to chat about it as opposed to just snatching this halfway through or else. Or else I'll put a hex on you. White gypsy hex. That's right. 

5.9.14

Addition Tables in Z sub n

Problem: How can we compute the result of running an operation on two integers in a group without actually running the operation on the 2 integers?

This problem seems like a paradox but it isn’t. The so called “idiot savants” have been doing it without memorizing operation tables so why can’t the rest of the humans do it as well? I suspect that it is because the so called “idiot savants” are better equipped to recognize patterns in nature.  

Let’s paraphrase the abstract problem for a concrete operation and start with the simplest operation there is: addition in Zn. It is trivial to verify that Zn is a group closed with respect to addition. In other words, for any a,b <= n-1 in Zn, the result of a+b is also in Zn. Namely, a + b = c  where c is in Zn and c = n.q + r = r where r is the greatest common divisor of (a+b, n) 

Problem: How can we compute the result of adding two integers in Zn without actually adding the 2 integers?

Solution: Find a pattern to generate all subsequent rows/columns in the table from the first trivial row/column.

First, let's compute the addition tables for the congruence classes of Zn for some n, namely 5, 6, and 7. 

Below are the addition tables for Z sub 5, Z sub 6, and Z sub 7






The pattern should be easy to spot:

The first row simply lists all elements in Zn, and each subsequent row is simply a shift to the left by 1 integer from the previous row.

Here's the conjecture:


The proof is as trivial as the pattern itself: by definition.

This was the simplest of operations in Zn. I can't think of any real world applications for it, other than Abstract Algebra exams: you will never have to think what's 15+16 in Z sub 17 while writing out addition tables.  Actually, navigation through different timezones is another real world application, duh.

However, there are other, much more powerful operations that are used in various aspects of our modern life and there is a method to the madness there as well. 

6.7.14

Making Colour

The digital reality that people surround themselves with these days differs from their physical reality in many ways but I'm only interested in the way that annoys me the most.

Digital displays do not accurately represent all colours people perceive in the real world. In digital images colours become colors.

What's worse, color combinations in digital images are severely distorted. It has to do with what is known to artists and scientists as primary colours.

When artists speak of primary colours they generally mean red, blue, and yellow. When scientists speak of primary colors they generally mean red, blue, and green.

It's amusing to watch artists and scientists quarrel over primary colour labels because both camps are correct in their assertions. Sort of but not really.

Artists made colours from crystals back in the day and considered yellow to be primary because they could not break down yellow pigments into other pigments yet when they combined yellow pigments with other pigments they produced new pigments. Yellow pigments mixed with red pigments produced orange pigments, red and blue pigment mixtures resulted in violet, while yellow and blue produced green.

Fig1.1 A spectacular exhibit.

Scientists consider green to be primary because, to put it simply, green occupies a greater portion of the rainbow as experienced by the average human than yellow does [as illustrated in the image below on Fig1.2, not the one above on Fig1.1].

Yet each cone cell in the human eyeball that's responsible for deciphering the rainbow responds to a range of colour wavelengths, not a particular colour, and the perception of colour is relative to the observer.

The rainbow, which illustrates the visible light region of the electromagnetic spectrum, is continuous and there are no set boundaries between different colours. Yellow is adjacent to green, which is adjacent to blue, and where each one begins and the other one ends is only a rough estimate. Different device manufacturers have different rough estimates.

Fig1.2 A slice of the rainbow
Regardless of which came first, green or yellow, both artists and scientists agree that the average human requires 3 primary colours to make and perceive all other colours on the rainbow/visible portion of the electromagnetic spectrum.

As I've established here already, not everyone experiences the visible portion of the electromagnetic spectrum as the average human but even the average human is shortlisted when it comes to digital displays.

Digital displays still cannot accurately display all colors experienced in reality by the average human. In other words, every kitten photo you clicked on today was only an approximation of the kitten in real life, at least colour-wise. Some manufacturers considered adding a fourth primary to compensate. However, even this four-primary tech does not yet reach the range of colours that average trichromat humans are capable of perceiving. Perhaps one of these primary colours was not really primary.

Take the digital image below. The left portion contains an image of a plant known as Hot Poker. The image is composed of pixels where each pixel is described by 3 integer values between 0 and 255 that represent the amounts of red, blue, and green in it. Green, not yellow, because where's the fun in displaying colours accurately. The right portion of the image contains the main colors of the left portion.  


Fig1.3 Hot Pokers and their digital colors 
In the physical world the yellow and red petals of the hot pokers flow more sinuously. Same goes for their green stems and leafs. Unfortunately, at this point there's not much that can be done to restore the original colours of the physical scene but something can still be done to harmonize the digital image.

When I first started working on Coloroid's harmonic template filters I attempted to recreate the magic that happens in this paper. But then that magic turned out to be too computationally expensive for a mobile web app so I had to come up with my own magic.

The 'Hot Pokers' digital image exists in a 3D color space where the combination of the 3 integer values of each pixel contains not only information about the pixel's color or hue, but also it contains information about how vivid that colour is and how bright it is, which means each one of the 3 variables: r, g, and b contains information about the pixel's hue, saturation, and brightness.

Trying to obtain a single color from a digital image could be a nightmare. Take green for example. Intuitively, one would imagine that if the values of  r and b are 0 then g would describe a green pixel, which is true but not the kind of green you typically experience. In the composite image below, the first two images illustrate the two main flavours of "green" from the "Hot Pokers" image, the 3rd one represents the "primary" green obtained from zeroing the r and b channels (note how once r and b are 0, the g channel is the kind of green you rarely experience in nature)

Fig 1.4 Flavours of green: the one on the far left is more like ochre than green

If the 3 channels are flattened so that the hue is separate from the brightness and the saturation, then the different colours can be categorized with greater ease and this information can be used to create different harmonious colour combinations of the image from its existing colour combinations.

In order to separate hue, saturation, and brightness into 3 separate channels one must convert from RGB to HSV for example (although HSV is lossy, it is also quick and inexpensive).

Below is an illustration of the first flavour of ochre green in "Hot Pokers", although to call this colour ochre green is probably an insult to someone somewhere. Also, the whole colour wheel below is an atrocity to colours everywhere 'cept for the interwebs.

Fig1.5 HSL wheel
Once the hue info is stored separately in a single variable it can be easily checked to see where each pixel stands on the spectrum and decide what to do with it. Standard implementations of the HSL and HSV algorithms return the hue, saturation and brightness or luminance as a float value between 0 and 1.

Fig1.5: A separate channel for the hue

Since h is between 0 and 1, it is easy to find then the complementary color range of any h.

This is useful in making harmonious combinations because regardless of whether people talk about expressionism or cubism, or surrealism and classicism, or whatever, what makes most of everyone's favourite paintings so appealing is that none of them contain red, blue, and green in equal amounts at the same time.

All of them fall into one of the harmonic colour templates as described on Figure 2 in this paper.

Fig2.0 Types of harmonic templates on the hue wheel


None of these templates uses 3 primary colours in equal amounts at the same time. The i-type, V-type , and T-type of harmonic templates correspond to monochromatic or dichromatic images (ones made of shades of the same colour, or shades of the same 2 colours respectively).  A favourite technique of great painters is to use complimentary colours or split complimentary colours, which correspond to the X & I types, and Y and L types of harmonic templates respectively.

A sample of famous paintings from different genres.

Since h is between 0.0 and 1.0, then the complementary colour range for a given pixel's hue h < 0.5 is h + 0.5, and for any h > 0.5 the complementary color is h - 0.5., the split complimentary is at h +  0.3 and h - 0.3 respectively, and the analogous is at +/- 0.1. With this in mind, the following algorithms shift every pixel of a particular colour specified in the if condition to its complementary hue.

In this particular case, the algorithm complements every pixel which isn't in the blue range and matches it to blue in order to force the image either into the i-type, the V-type , or T-type  where the entire image becomes either monochromatic (composed of shades of blue) or dichromatic (composed of shades of blue and shades of red).

 /* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova (http://ibrius.net)  
 Version: 1.0  
 ---------------------------------------------------- */  
function match_blue($filename)
{
     $image = '/path_to/'.$filename;  
      if (file_exists($image))
      {   
           $im = imagecreatefromjpeg($image);
           $width = imagesx($im);  
           $height = imagesy($im);  
           //because you really don't want to loop through more that this  
           if ($width >= 1000)  
           return FALSE;  
           //let the looping begin  
           for($x = 0; $x < $width; $x++)   
           {  
                for($y = 0; $y < $height; $y++)   
                {  
                     $rgb = imagecolorat($im, $x, $y);  
                     $r = ($rgb >> 16) & 0xFF;  
                     $g = ($rgb >> 8) & 0xFF;  
                     $b = $rgb & 0xFF;  
                     $alpha = ($rgb & 0xFF000000) >> 24;  
                     //convert to hsl
                     list($h, $s, $l) = rgb2hsv($r, $g, $b);
                     //we're in red&green&yellow, convert to blue hue
                     if ($h > 0.7)
                     {
                         $h = $h - 0.5;
                     }
                     else if ($h < 0.5)
                     {
                         $h = $h + 0.5;
                     }
                     if($h > 1) {$h=1;}
                     //convert back to rgb
                     list($r, $g, $b) = hsv2rgb($h, $s, $l);
                     //piece everything together  
                     imagesetpixel($im, $x, $y, 
                     imagecolorallocatealpha($im, $r, $g, $b, $alpha));  
                }  
           }
           if(imagejpeg($im, 'path_to_temp/'.$filename))  
           {return TRUE;  }
           imagedestroy($im);  
      }  
 return FALSE;  
 }

Below is a demo of this algorithm in JS. Note that this algorithm does not take into account the spatial relation between different pixels with the exact same hue so it will shift all pixels of the same hue. Because where's the fun in solving all problems at the same time.

Also note that this filter is not in Coloroid. The harmonic filters there are slightly different. This one simply illustrates how to turn a trichromatic image into either a monochromatic or a dichromatic one.

23.6.14

50 Shades Of Grey

No, not those 50 shades of grey so put it away please. Ladies, you too.
I never actually read that book; all I know is British people turn red when someone mentions it, which means there's probably some French kissing involved.

10.6.14

Cartesian Fingers

I was working on a mobile app that has a special type of events-tracking calendar chart, which needed to be visible and interactive at all times, and which can have up to 140 days. 

That's a lot of days to display on a 7-10 inch screen. 

In addition, each day has several fields and there must be enough space for the user to enter stuff in these fields. In other words, no inch can be squandered.

Ideally, the calendar would be a torus, or better yet a simple 2D ring, an inner and an outer circle drawn on a Cartesian plane, and each day would be a segment of the 2D ring. I say ideally because this is how these charts are usually illustrated in my client's books. However, the chart in the app  must be interactive.

Example chart with 8 segments


Problem: As the user adds new days to the chart, the number of days on the ring will grow so therefore either the diameter must grow bigger or the segments must grow smaller.

If the diameter grows bigger, then some of it will become obfuscated on the limited screen real estate of mobile devices. On the other hand, if the segments grow smaller, then the user might not be able to select a particular day, which would be frustrating if the user could view and expand only 1 day at a time.

But if the user could view and expand 5 days at a time: 2 ahead and 2 behind the selected day, then things wouldn't be so bad because (2*Pi/140)*5 = 0.22, which means that even in a chart with the maximum number of days where individual segments might be too small to select, five neighbouring segments still make a decent arc and the user is more likely to see the day they wish to see.

Even if the user accidentally selects a segment slightly off the 5 segments displayed, they can still quickly and easily retrieve the segment they want by scrolling through the neighbouring ones left and right.

The average chart has more days than this one.


This display is not only functional but it is also very similar to my client's actual logo, which is a bonus.


The implementation should be easy: each segment has an arc of length 2Pi/(number of days). When a user clicks on the chart it is easy to retrieve their x and y coordinates and if (x=0,y=0) is the point at the centre of the ring, then we can easily turn the x and y coordinates into polar coordinates using trigonometry because:


(θ, t) are the polar coordinates equivalent to the cartesian coordinates (x, y) obtained in the following manner:


θ = atan2(y,x) 

t^2 = x^2 + y^2  => t = sqrt( x^2 + y^2 )

Both the radius of the small circle (r) and the radius of the big circle(R) are static. The arc length and the number of arcs are not but they known : arc-length = 2Pi/#of days;    #of arcs  =  #of days; so the starting and ending point of each segment is also known.

So a simple pseudo code would read like this:

//draw ring
draw inner circle
draw outer circle

//for each segment in array of segments add start and end
Segments{start: startingAngle, end: endingAngle}

//obtain the polar coordinates from cartesian coords of the click
θ = atan2(y, x);
t = sqrt(abs((x*x) + (y*y)));

//check to see if cartesian coords of the click are within ring
if(t > r && t < R)
{
//convert from (pi, -pi) to (0, 2Pi)
if(θ < 0){θ +=2*Pi}

        //check to see which segment the angle θ is in
for (var i=0; i < Segments.length; i++)
{
if (θ >Segments[i].start && θ < Segments[i].end) {print("Boom! You're in sector "+j);}
}

}
else
{
print(Moob. Finger is not on ring);
}

And in an ideal world where everyone cares for the sanity of Mathematics lovers this works perfectly. But we don't live in an ideal world as illustrated by this funky meme I made especially for all JS lovers.


To be fair, this is not just JS Canvas arc's vision. This is how arcs behave in many scripting languages.

And it wouldn't have mattered if it wasn't for the fact that different segments may have different colours so orientation of the drawing does matter.

The problem was reduced to either hacking up the atan2 function to calculate the reflection or hacking up the segment drawing function to display the segments in the opposite rotation - the one that atan2 expects.

The obvious choice was to alter the mathematically finicky drawing function and the result is demoed below. First day is always red, the rest may vary. Also, currently it's set to accept any number of days but it will only display days between 1 and 140.

31.1.14

What Makes Art Creative?

Some people say that something is not creative unless it is popular. Luckily, those who first discovered Vincent Van Gogh's totally unpopular work after his death were not among the people who say this.

What makes something creative? Or rather what makes something creative desirable? Because let's face it: if you created it and you didn't get the sudden urge to destroy it or let others destroy it, then your creation is creative to at least one person: You, the creator.

In many cases, what makes a creative piece desirable is the advertising skills of the creator. Take Pablo Picasso for example - art's greatest hustler. The famous cubist elements that made his paintings so desirable were generously borrowed from certain sculptures found in one school of African art, which was not popular in the Western world at the time. He took the unique stylized shapes and forms of these sculptures and made them popular to white Westerners by fuzing them with provocative scenes and subjects that would appeal to white Westerners. Like Red Light District workers.

Picasso was a marketing genius! A behavioral psychologist extraordinaire! And many other things I'm sure.
 
And then there was Vincent Van Gogh who was completely unpopular while he was alive. Yet today he is worshiped just as much as Picasso if not more and his popularity keeps growing. Despite being ginger. He invented a movement influenced by nothing other than his internal turmoil.

If you look at the hue histograms of Van Gogh paintings, it becomes quite obvious why he has more likes on Facebook than Picasso (to put in terms that people today would understand). Van Gogh appears to have had a superior understanding of colour. Apparently, very few people do.

He was able to combine colors in a manner, which pleases the eyeball. All eyeballs. Or at least 90% of all eyeballs. Which is a pretty hard task considering that eyeball pleasing is an objective affair.

To loosely quote my favourite paper on color harmony loosely quoting their favourite paper on color harmony, there is no exact formulation that defines a harmonic set of colors but there is a general consensus among artists when a color set is harmonic and there are certain templates that are based on this consensus.

Harmonic templates on the hue wheel. Templates may be rotated by an arbitrary angle.
These hue wheel templates illustrate which color combinations generally work and which color combinations do not. As you can imagine this has many applications. One novel application would be for example: I have this red top with a yellow stripe that I want to match with a jacket to look ultra cool but I'm not sure which jacket will look cool with it.

For about two years I've been working on an image filter that harmonizes the colors of an image and I am finally am starting to scratch the surface of answering the question about my red top.

Initially, I took the naive approach of simply flattening the color space entirely to a color space with way less colors to fit a particular template. The Color Vision filters of Coloroid do just that. It has a slightly skewed versions of this algorithm, and it takes into account the pure assumption that people with color vision deficiencies see the world through harmonic templates, the I type and the X type in particular. Some people have total color blindness: they see the world in black and white. Black & White is another harmonic template, namely the N type, which is why B&W selfies are popular.

Now I'm taking a more sophisticated approach where I keep track of certain pixels, and distance between them. Below is the original image of a tree hugger in a blue jacket and a harmonized image on the right along with their hue wheels.





And below are a few other harmonized choices. The one on the right is pushing it. My personal favourite is the one on the left, which is actually the exact color of the jacket in reality before being exposed to the destructive nature of iPhone's automatic processing.




























More on the subject of colours.

References:
Antal Nemcsics et al, Computational Color Harmony Based On The Coloroid System, 2005
Daniel Cohen-Or et al., Color Harmonization,