Mohamad  Agil  The  Colour  Sorter:  Solving  the  Problem  of  Displaying  2000  Colours  for  Someone  Looking  to  Redecorate  their  Home    Abstract  When  searching  for  a  colour  to  paint  a  room,  we  are  often  presented  with  hundreds  and  sometimes  thousands  of  shades,  which  can  often  lead  to  a  lot  of  time  being  wasted  trying  to  find  the  perfect  colour.  This  report  will  discuss  how  I  used  Machine  Learning,  Computer  Vision  and  Colour  Theory  at  tech  start-­‐up  Digital  Bridge  to  solve  this  problem,  allowing  customers  to  be  as  efficient  as  possible  with  choosing  their  desired  colour.  We  will  explore  the  application  of  the  three  mentioned  fields  as  well  as  the  technologies  that  were  used  to  develop  the  final  product,  which  you  could  potentially  be  using  in  the  next  couple  of  years.    

F r i d a y   2 3 r d   S e p t e m b e r   2 0 1 6  

 

 

 

 

Digital  Bridge  Summer  Placement  Report  

Table  of  Contents  

TABLE  OF  CONTENTS   2  

TABLE  OF  FIGURES   4  

INTRODUCTION  AND  CONTEXT   5  

Disclaimers   5  

The  Company   5  

The  Team   5  

My  Project   6  

Preparation  and  Research   6  

Technologies   8  

Testing   8  

DEVELOPMENT   9  

Iteration  1:  The  Colour  Grid   9  Colour  Perception   9  Putting  the  Theory  into  Practice   10  Results   10  

Iteration  2:  Adding  Saturation  to  the  Equation   12  Feature  Weighting   12  Putting  the  Theory  into  Practice   12  Results   12  Using  the  LAB  Colour  Space   13  

Iteration  3:  Clustering  the  Colours   14  The  Problem  at  Hand   14  Clustering   14  Results   15  

Iteration  4:  Colour  Schemes   17  Questioning  the  Goals   17  The  Idea   18  The  Colour  Harmonies   19  The  Program  Structure:  Matplotlib,  Grapefruit  and  NumPy   19  The  Result   21  

Iteration  5:  Converting  the  Program  into  a  Web  API   23  RESTful  APIs  and  Flask   23  

TESTING   24  

The  Types  of  Testing   24  

Unit  Testing   24  

DOCUMENTATION   26  

EVALUATION  AND  CONCLUSION   27  

REFERENCES   28    

 

Table  of  Figures  Figure  1:  Three  different  companies  using  a  similar  tactic  to  group  their  colours.  ________________________  7  Figure  2:  There  is  a  lack  of  consistency  between  visual  difference  and  numerical  difference  in  RGB  colours.  ___  9  Figure  3:  The  HSV  colour  wheel,  showing  the  effects  of  varying  the  three  components  ___________________  10  Figure  4:  The  first  attempt  did  a  reasonable  job  with  sorting  the  colours  however  there  was  still  room  for  improvement.   ____________________________________________________________________________  11  Figure  5:  Using  the  LAB  colour  space  yielded  a  much  cleaner  colour  space,  with  virtually  no  artefacts.  Note  that  the  grid  has  been  split  into  two  to  allow  for  clearer  presentation.   ___________________________________  13  Figure  6:  One  of  these  colours  has  a  hue  of  30,  the  other  180.  Visually  they  look  very  similar,  but  the  computer  would  recognise  them  as  completely  different  colours  because  of  their  numerical  values.   ________________  14  Figure  7:  When  datapoints  with  similar  characteristics  are  plotted  on  a  graph,  they  form  clusters  [6].   ______  15  Figure  8:  Using  the  K-­‐Means  algorithm  to  cluster  similar  colours  yield  some  positive  results  but  with  a  significant  number  of  anomalies.  _____________________________________________________________  16  Figure  9:  The  report  detailed  out  the  theory  behind  interior  design,  colour  harmonies  and  computer  vision.  __  18  Figure  10:  The  program  had  a  front  end,  a  back  end  and  a  control  layer  in  between  to  regulate  the  flow  of  data.  ________________________________________________________________________________________  19  Figure  11:  Matplotlib  allowed  for  several  graphs  to  be  displayed  on  one  graph.  This  feature  was  used  to  display  several  colour  harmonies  on  one  screen.  _______________________________________________________  20  Figure  12:  The  final  product  of  iteration  4.  ______________________________________________________  21  Figure  13:  The  program  is  shown  with  a  different  uploaded  image.  This  time,  the  colour  of  the  sofas  is  the  one  we  are  interested.  _________________________________________________________________________  22  Figure  14:  The  output  from  the  developed  web  API.  The  developers  that  created  the  new  front  end  used  this.   23  Figure  15:  This  is  what  a  typical  unit  test  looks  like  in  Python.   ______________________________________  24  Figure  16:  This  is  the  output  of  a  set  of  Python  unit  tests  when  they  are  run  and  they  all  pass.  _____________  24  Figure  17:    This  sort  of  documentation  was  written  for  all  of  the  functions  that  had  been  created  during  the  placement.  _______________________________________________________________________________  26    

Introduction  and  Context  

Disclaimers  All  of  the  implementations  and  screenshots  shown  in  this  document  are  property  of  Digital  Bridge  Ltd.  Some  details  have  been  omitted  from  this  report  to  keep  in  line  with  copyright  regulations.  In  these  cases,  context  has  been  dismissed  and  the  relevant  Computer  Science  principles  have  been  described  instead.  

This  placement  took  place  in  summer  2015  and  lasted  for  12  weeks.  The  placement  I  completed  in  summer  2016  was  with  RBS  and  was  unrelated  to  Computer  Science  due  to  them  placing  me  in  the  Operations  team  after  there  were  business  changes  that  disallowed  me  from  joining  the  technology  team,  which  was  the  original  plan.  

The  Company  The  company  that  I  worked  for  during  my  placement  is  called  Digital  Bridge.  It  is  a  start-­‐up  that  was  founded  in  2013  by  CEO  David  Levine.  It  attempts  to  solve  the  problem  of  visualising  what  a  room  would  look  like  when  it  is  redecorated  using  Machine  Learning  (ML)  and  Augmented  Reality.  The  process  of  using  their  tool  is  as  follows:  

1.  Take  a  picture  of  your  room  using  a  smartphone.  2. Open  that  image  instantly  on  the  web  on  a  laptop,  desktop  or  tablet  using  a  unique  

token  that  is  generated  for  that  image.  3. The  program  will  attempt  to  detect  the  objects,  borders  and  shading  in  the  room  

using  ML  algorithms.  4. Begin  redecorating  by  adding  furniture,  changing  the  wallpapers,  adding  paint  and  

changing  the  flooring  to  see  what  your  room  will  look  like  with  a  supplier's  products.  

The  long-­‐term  vision  of  the  company  is  to  sell  this  product  onto  interior  design  companies  so  that  their  customers  can  begin  using  the  program  to  test  their  products  before  buying.  So  far  John  Lewis  has  rewarded  the  product  with  some  acceleration  funding,  with  several  contracts  with  other  companies  currently  in  the  negotiating  stage.  

A  Google  search  of  the  terms  “interior  design  augment  reality”  shows  that  Digital  Bridge  currently  has  several  competitors  including  Augment,  Decolabs  and  Dezeen  who  work  on  similar  projects.  

The  Team  The  company  (at  the  time  of  the  placement)  had  around  fifteen  employees  so  the  casual,  hard-­‐working  start-­‐up  culture  was  very  much  rife  during  that  period.  There  were  three  main  teams  within  the  company:  

1. The  directors:  this  team  consisted  of  founder  and  CEO  David  Levine,  CTO  Martin  Fergie,  COO  Mike  Corlett  and  Product  Owner  James  Lewis.  This  team  was  the  company's  core  leadership  and  was  responsible  for  the  day-­‐to-­‐day  management  of  the  projects.  

2. The  developers:  this  team  carried  out  the  bulk  of  the  program's  planning,  development  and  testing.  

3. The  researchers:  this  is  the  team  that  I  was  placed  in.  We  carried  out  research  and  software  development  for  low-­‐priority  projects  that  could  potentially  be  added  to  the  product.  Once  prototypes  were  developed  to  an  acceptable  standard,  they  were  passed  on  to  the  developers  to  further  flesh  out,  test  and  incorporate  into  the  product.  

My  Project  The  project  that  I  was  working  on  solved  the  problem  of  colour  sorting.  When  you  want  to  choose  a  paint  colour  for  your  room,  you  are  presented  with  hundreds  and  sometimes  thousands  of  options,  with  many  shades  being  very  similar.  Ultimately  there  is  only  one  colour  that  will  satisfy  you  and  that  is  right  for  your  room.  The  colour  sorter  used  a  blend  of  Artificial  Intelligence  (AI)  and  User  Experience  (UX)  theory  to  present  the  available  colours  in  a  way  that  helped  the  user  choose  their  paint  in  the  fastest  way  possible.  

The  development  of  the  colour  sorter  was  carried  out  in  an  agile  way,  using  iterations  that  lasted  anywhere  between  two  and  four  weeks.  It  was  developed  in  coordination  with  CTO  Martin  Fergie,  who  directed  the  technical  side  of  the  development  and  Product  Owner  James  Lewis,  who  decided  what  direction  the  project  was  headed  in  by  reviewing  each  iteration  and  suggesting  alterations.  Once  the  internship  was  over,  whatever  was  developed  was  handed  over  to  COO  Mike  Corlett,  who  tested  and  added  it  to  the  product's  Git  repository  and  one  of  the  main  developers  who  supposedly  developed  it  further.  

The  following  tools  were  used  to  support  the  development  of  the  project:  

• Git:  this  was  used  to  manage  the  evolution  of  the  project  and  roll  back  when  required.  

• Trello:  this  was  used  to  monitor  the  user  stories  of  the  project  and  to  support  the  agile  process.  

This  report  will  detail  out  the  iterations  and  explain  how  the  project  evolved  into  what  it  is  today  but  first,  it  is  worth  putting  things  into  context  by  explaining  the  research  and  preparation  that  was  done  before  the  actual  development  as  well  as  what  technologies  were  used  to  build  the  project  and  the  reasoning  behind  the  choices  that  were  made.  

Preparation  and  Research  The  first  task  of  the  project  was  to  research  how  colours  were  currently  being  displayed  on  other  sites  and  what  real  users  actually  wanted  using  online  research  and  customer  interviews  respectively.  

Two  important  and  interesting  observations  were  made:  

1. Pretty  much  all  existing  sites  used  some  form  of  colour  grouping  as  shown  in  Figure  1  whereby  users  were  presented  with  a  high  level  view  of  all  of  the  colour  groups  e.g.  reds,  greens,  yellows,  etc.  and  then  were  shown  all  the  shades  within  that  group.  

2. These  results  were  in  consistency  with  what  real  users  wanted  when  they  were  asked  for  ideas  during  customer  interviews-­‐  they  all  expressed  a  mutual  desire  for  colours  to  be  grouped  before  they  were  shown  specific  shades.  

 

 Figure  1:  Three  different  companies  using  a  similar  tactic  to  group  their  colours.  

 

These  two  observations  were  the  basis  for  the  start  of  the  project-­‐  the  tool  was  going  to  show  the  colours  grouped  in  some  way  and  it  was  to  be  evolved  and  enhanced  one  agile  iteration  at  a  time.  

 

Technologies  To  add  further  context  to  the  project,  it  is  worth  noting  which  specific  technologies  were  used  for  the  development.  The  selected  programming  language  was  Python.  Although  there  were  technical  reasons  for  this  related  to  the  company's  servers  and  their  compatibility,  the  decision  was  also  based  on  the  fact  that  Python  had  four  particular  packages  that  were  heavily  related  to  this  project's  purpose:  

1. NumPy:  this  is  a  package  that  allows  for  fast  processing  of  matrices  compared  to  Python  lists  [1].  A  Stack  Overflow  user  explains  that  it  can  scale  the  processing  speed  up  anywhere  between  0.6  and  61  times  compared  to  using  conventional  Python  lists  [3],  which  came  in  handy  for  processing  matrices  containing  thousands  of  values.  

2. Sci-­‐Kit  Learn:  this  package  contained  several  useful  ML  algorithm  implementations  that  were  used  to  speed  up  some  of  the  operations  on  the  datasets,  as  we  will  see  later  [2].  

3. Matplotlib:  this  package  contained  data  plotting  and  manipulation  utilities  that  would  otherwise  be  very  fiddly  to  implement  from  scratch  [5].  

4. Flask:  this  is  a  package  that  allows  a  programmer  to  develop  web  APIs.  This  will  be  discussed  in  more  detail  in  the  chapter  describing  iteration  five.  

The  first  week  or  two  of  the  internship  were  spent  intensely  learning  Python  and  the  stated  packages  so  that  I  was  familiar  with  the  technologies  when  it  came  to  developing  the  project.  Needless  to  say,  this  was  a  very  steep  learning  curve  that  didn't  stop  throughout  the  internship,  which  gave  me  an  appreciation  as  to  how  much  technical  knowledge  there  is  yet  to  learn.  

Testing  To  test  the  program,  a  dataset  of  around  2060  colours  was  used.  This  dataset  was  given  to  the  company  by  Dulux  and  would  be  used  to  carry  out  all  sorts  of  experiments,  as  we  will  see  in  the  coming  chapters.  

The  colours  themselves  were  stored  in  text  format,  with  each  colour  being  represented  by  three  values  corresponding  to  the  amount  of  red,  green  and  blue  there  was  in  each  colour.  More  on  this  in  the  next  chapter.  

Development  

Iteration  1:  The  Colour  Grid  The  purpose  of  this  iteration  was  to  gain  some  understanding  into  colour  theory  and  be  able  to  visualise  how  colours  would  look  when  they  were  sorted  in  certain  ways.  The  way  to  do  this  was  through  representing  the  colours  as  numbers  and  sorting  them  using  some  intuitive  algorithm.  

Colour  Perception  Most  people  probably  understand  the  RGB  colour  space.  It  is  a  representation  that  allows  any  colours  to  be  represented  using  three  integers  between  0  and  255,  where  each  integer  represents  how  much  red,  blue  or  green  is  an  image  respectively.  The  problem  with  this  colour  space  is  that  it  isn’t  consistent  with  human  perception  of  colour.  This  is  best  illustrated  using  Figure  2,  which  shows  four  colours  and  their  RGB  values.  The  figure  and  the  description  have  been  extracted  from  my  third  year  project  report.  

 

Figure  2:  There  is  a  lack  of  consistency  between  visual  difference  and  numerical  difference  in  RGB  colours.  

“Figure  2  shows  four  different  colours  along  with  their  RGB  values.  The  visual  difference  between  the  top  left  and  top  right  isn’t  very  great  however  the  numbers  seem  to  say  otherwise.  There  is  a  difference  of  80  between  the  two  channels,  which  is  relatively  high  considering  the  maximum  for  each  channel  is  255.  

Likewise,  the  visual  difference  between  the  bottom  right  and  top  left  is  much  greater  than  that  of  the  previous  example  and  yet  there  is  only  a  numerical  difference  of  150,  which  doesn’t  seem  proportional,  relative  to  the  numerical  difference  from  the  first  example.”  [6]  

To  work  around  this  obstacle,  it  was  necessary  to  use  a  colour  space  that  whose  numbers  were  more  consistent  with  human  perception  of  colour.  This  was  the  HSV  colour  space,  which  is  illustrated  in  Figure  3.  

 

Figure  3:  The  HSV  colour  wheel,  showing  the  effects  of  varying  the  three  components  

“HSV  has  three  channels:  

1. Hue:  the  position  of  a  colour  on  the  colour  wheel.  Colours  on  the  wheel  are  identified  by  a  value  between  0  and  360  (the  number  of  degrees  in  a  circle).    

2. Saturation:  How  “rich”  a  colour  is.  The  higher  the  saturation,  the  bolder  a  colour  appears.  

3. Brightness:  How  bright  an  image  is.  Colours  with  a  value  of  zero  are  black  and  ones  that  have  maximum  brightness  are  white.”  [6]  

Putting  the  Theory   into  Practice  The  first  prototype  that  was  built  based  on  this  principle  was  a  very  simple  grid  that  sorted  the  colours  to  make  them  look  visually  appealing.  The  idea  was  to  have  the  colours  sorted  by  hue  horizontally,  but  by  value  vertically.  

This  was  to  create  an  effect  of  having,  say,  the  reds  in  one  ‘block’  on  the  grid,  but  within  that  block  have  the  darker  reds  at  the  top  and  lighter  reds  at  the  bottom.  This  form  of  two-­‐way  sorting  is  no  easy  task,  so  the  following  algorithm  was  designed  to  attempt  to  satisfy  that  requirement:  

Sort  all  the  colours  in  ascending  order  of  hue.  Create  a  grid  of  size  n  x  10  where  n  is  a  number  large  enough  to  fit  all  the  colours  from  the  test  dataset.  For  each  group  of  10  colours  (which  would  act  as  a  single  column  within  the  grid),  sort  these  colours  in  descending  order  of  value.  Insert  these  10  colours  into  a  new  column,  starting  from  the  left  hand  side  of  the  grid.  

Results  This  was  the  output  of  the  program  when  the  algorithm  was  implemented:  

Figure  4:  The  first  attempt  did  a  reasonable  job  with  sorting  the  colours  however  there  was  still  room  for  improvement.  

As  shown  in  the  figure,  the  grid  did  indeed  sort  colours  into  their  respective  visual  categories.  We  can  clearly  see  some  sensible  grouping  of  reds,  yellows,  greens  and  blues  horizontally.  

Vertically  however,  the  algorithm  didn’t  do  so  well.  Although  there  was  a  net  decrease  from  dark  to  light  going  top  to  bottom  of  any  given  column,  in  between  there  was  clearly  some  disordering,  evident  by  the  random  ‘artefacts’  that  didn’t  follow  the  intended  pattern.  

This  result  led  to  the  idea  of  incorporating  the  colours’  saturations  into  the  algorithm,  since  we  had  only  looked  at  two  of  the  three  channels  of  the  colour  space  so  far.  

Iteration  2:  Adding  Saturation  to  the  Equation  In  this  iteration  the  focus  was  placed  on  how  to  sort  the  colours  vertically  using  two  different  characteristics  (saturation  and  value)  which  introduces  the  principle  of  feature  weighting.  

Feature  Weighting  To  decide  on  how  to  order  the  colours,  it  was  necessary  to  merge  our  two  characteristics  (or  features  in  ML  terms)  into  one.  This  was  done  by  normalising  both  values  to  the  [0,  1]  range  using  Matplotlib’s  Color  class  and  then  adding  them  together.  

The  question  was  how  do  we  decide  which  value  to  give  a  higher  precedence?  The  purpose  was  to  achieve  increasing  visual  brightness  amongst  the  colours,  but  does  that  come  more  from  the  colour’s  value  or  its  saturation?  

To  illustrate  this  principle,  imagine  you  had  to  order  ten  students  according  to  their  intelligence  and  you  had  two  pieces  of  information  about  each  student:  their  Intelligence  Quotation  (IQ)  and  their  score  from  a  maths  exam  they  recently  sat.  The  idea  of  intelligence  is  subjective  according  to  different  people.  

One  person  may  say  that  the  student’s  intelligence  is  purely  based  on  their  IQ  and  that  their  exam  score  doesn’t  give  us  any  extra  information.  In  that  case,  they  would  calculate  a  student’s  score  using  (1  *  IQ)  +  (0  *  exam  score).  The  1  and  the  0  here  are  known  as  weightings,  which  tell  us  how  much  consideration  a  feature  is  being  given  (0  being  unconsidered  and  1  being  the  most  consideration).  

Putting  the  Theory   into  Practice  Applying  this  principle  to  what  was  built  in  iteration  1  made  the  following  changes  to  the  algorithm:  

Sort  all  the  colours  in  ascending  order  of  hue.  

Create  a  grid  of  size  n  x  10  where  n  is  a  number  large  enough  to  fit  all  the  colours  from  the  test  dataset.  

For  each  saturation  weighting,  0.0  to  1.0  in  increments  of  0.1:  

 For  each  value  weighting,  0.0  to  1.0  in  increments  of  0.1:  

For  each  group  of  10  colours  (which  would  act  as  a  single  column  within  the  grid),  sort  these  colours  in  descending  order  of  brightness  value,  which  is  calculated  using  (saturation  weighting  *  saturation)  +  (value  weighting  *  value).  

Insert  these  10  colours  into  a  new  column,  starting  from  the  left  hand  side  of  the  grid.  

Results  There  were  two  problems  with  evaluating  the  results  from  this  iteration:  

1. There  was  no  solid  measure  of  correctness  of  implementation.  From  this  algorithm,  one  hundred  different  grids  were  generated.  How  ‘correct’  one  grid  is  depends  on  

visual  judgement  and  is  subjective  to  each  individual  and  what  they  perceive  to  be  visually  appealing.  

2. Even  if  there  was  a  way  to  find  the  best  solution,  how  do  we  know  that  these  weightings  would  work  for  another  colour  dataset?  It  may  be  that  for  one  dataset  the  best  weightings  for  saturation  and  value  are  0.4  and  1.0  respectively,  whilst  it  is  0.9  and  0.3  for  another.  

In  addition  to  these  obstacles,  the  new  algorithm  didn’t  actually  improve  the  visual  results  from  the  previous  iteration  greatly.  The  conclusion  from  this  was  that  saturation  and  value  weren’t  good  features  to  use  for  the  vertical  sorting  and  that  a  different  component(s)  of  a  different  colour  space  was  necessary.  

Using  the  LAB  Colour  Space  So  far  we  have  looked  at  the  RGB  and  HSV  colour  spaces.  The  third  colour  space  that  was  looked  at  which  proved  to  be  useful  was  the  LAB  colour  space.  The  only  component  deemed  to  be  useful  was  the  L  (lightness)  component.  This  component  was  used  to  replace  the  V  component  of  the  HSV  data,  so  that  the  colours  were  stored  as  HSL.  

The  colours  were  then  sorted  using  the  first  algorithm  mentioned  on  page  10.  Using  this  algorithm  on  the  newly  defined  colour  space  yielded  the  following  results:  

 

This  result  was  a)  cleaner  than  the  previous  ones,  b)  had  little  or  no  artefacts  within  the  grid  (depending  on  your  perception  of  the  grid)  and  c)  was  a  lot  faster  than  the  previous  solution  since  the  looping  over  the  different  weightings  no  longer  occurred.  

It  was  decided  that  this  was  to  be  the  algorithm  and  colour  space  to  use  when  sorting  all  of  the  colours.  Now  that  the  foundations  of  the  colour  sorter  were  in  place,  it  was  now  time  to  begin  to  implement  solutions  that  enhanced  the  user  experience.  The  first  field  that  was  explored  used  a  Machine  Learning  algorithm.  

 

Figure  5:  Using  the  LAB  colour  space  yielded  a  much  cleaner  colour  space,  with  virtually  no  artefacts.  Note  that  the  grid  has  been  split  into  two  to  allow  for  clearer  presentation.  

Iteration  3:  Clustering  the  Colours  

The  Problem  at  Hand  Referring  back  to  the  commercial  examples  shown  in  Figure  1,  it  was  clear  that  simply  showing  all  of  the  colours  in  a  sorted  fashion  without  any  further  organisation  was  a)  messy  and  b)  not  innovative  enough  to  keep  ahead  of  the  market’s  competition.  It  was  therefore  decided  to  further  develop  the  way  the  colours  were  organised,  building  on  the  principles  discussed  so  far.  

The  idea  of  clustering  visually  similar  colours  together  was  the  first  to  be  explored.  One  would  assume  that  the  simplest  way  of  achieving  this  would  be  to  break  off  certain  ‘chunks’  of  the  original  grid.  This  would  work  to  some  extent  however  we  run  into  two  obstacles:  

1. Different  colours  on  the  grid  take  up  a  different  amount  of  space  and  so  our  grids  wouldn’t  be  of  equal  size,  which  isn’t  a  positive  user  experience  since  users  prefer  consistency  of  size  and  structure.  For  example,  in  Figure  5  shades  of  orange  take  up  a  much  larger  space  than  that  taken  up  by  the  shades  of  yellow,  which  would  make  both  categories  uneven  in  size.  

2. Even  if  we  were  happy  with  uneven  colours,  how  would  the  computer  know  where  to  ‘cut  off’  the  colours?  Computer  Vision  doesn’t  see  colours  the  way  humans  do-­‐  they  are  stored  purely  as  numbers.  The  idea  of  filtering  colours  by  hue  range  (e.g.  if  a  colour  has  a  hue  in  the  range  [180,  240]  then  it  is  a  shade  of  blue)  however  this  is  clouded  by  the  effect  that  the  extremes  of  saturation  and  value  have  on  the  colour.  Figure  6  shows  two  colours  with  completely  different  hues,  but  because  they  have  low  brightness  they  are  perceived  by  humans  to  be  almost  identical.  This  means  that  although  these  two  colours  are  visually  similar,  the  program  would  place  them  in  different  categories  because  they  fall  under  different  hue  ranges.  

 

To  work  around  these  issues,  we  had  to  take  more  than  just  the  colour’s  hue  into  consideration.  This  is  where  the  principle  of  colour  clustering  came  in.  

Clustering  

Figure  6:  One  of  these  colours  has  a  hue  of  30,  the  other  180.  Visually  they  look  very  similar,  but  the  computer  would  recognise  them  as  completely  different  colours  because  of  their  numerical  values.  

If  we  were  to  take  a  random  sample  of  professional  rugby  players  and  ballerinas  and  plot  their  weights  and  heights,  we  would  probably  get  a  graph  that  looks  like  the  one  in  Figure  7.  

As  demonstrated,  the  rugby  players  tend  to  be  shorter  in  height  and  heavier  in  weight  and  so  are  placed  in  close  proximity  on  the  graph,  while  it  is  the  converse  for  the  ballerinas.  

There  is  a  Machine  Learning  algorithm  called  the  K-­‐Means  algorithm  that  recognises  clusters  like  these  generated  from  datasets.  The  algorithm  is  one  of  many  clustering  algorithms.  This  particular  one  was  chosen  because  according  to  a  research  paper  titled  Data  Clustering:  A  Review  by  three  researchers,  the  K-­‐Means  algorithm  is  the  “simplest  and  most  commonly  used  algorithm”  because  it  is  “easy  to  implement  and  its  time  complexity  is  O(n)”  [4].  

“The  way  the  k-­‐means  algorithm  works  is  as  follows:  

1. Define  k,  the  number  of  clusters  in  our  dataset.  This  means  that  the  number  of  clusters  needs  to  be  known  before  execution,  one  of  the  downsides  of  the  algorithm.  

2. Set  k  random  points  as  the  centroids  of  the  dataset.  A  centroid  is  the  centre  of  a  cluster.  It  is  worth  noting  that  a  centroid  doesn’t  need  to  be  a  data  point,  it  could  be  any  coordinate  within  the  space.  

3. Assign  each  data  point  to  its  nearest  centroid  so  that  we  end  up  with  k  clusters.  

4. Re-­‐compute  the  centroid  positions  as  an  average  of  all  the  data  points  in  the  corresponding  cluster  and  reassign  the  data  points  to  the  nearest  centroid.  

5. Iterate  step  4  until  convergence.”  [6]  

In  addition  to  performance  advantages,  the  algorithm  also  allowed  the  user  to  define  the  number  of  clusters  they  want  to  separate  the  colours  into,  which  gave  us  some  control  over  how  many  colours  we  wanted  to  place  in  each  cluster.  

Results  

Figure  7:  When  datapoints  with  similar  characteristics  are  plotted  on  a  graph,  

they  form  clusters  [6].  

Implementing  the  algorithm  on  the  colours  using  the  LAB  representation  of  our  colours  gave  the  following  results:  

The  figure  shows  that  the  algorithm  did  do  a  decent  job  in  recognising  some  visually  similar  colours  however  there  were  too  many  anomalies  for  this  implementation  to  be  considered  acceptable  for  the  company’s  product.  

The  K-­‐Means  algorithm  was  experimented  with  the  colours’  RGB,  HSV  and  LAB  properties  without  an  acceptable  solution  being  produced.  

The  only  parameter  that  was  left  to  experiment  with  was  the  way  in  which  the  algorithm  measured  the  numerical  distance  between  two  colours.  There  are  several  different  ways  of  measuring  distance  between  multi-­‐dimensional  distances  such  as  the  Euclidean  and  Manhattan  distance  calculation  methods,  as  described  in  a  research  paper  from  the  Hebrew  University  of  Jerusalem  [7].  

After  testing  all  of  the  distance  measurement  methods  made  available  by  Sci-­‐Kit  Learn,  it  was  realised  that  using  the  K-­‐Means  algorithm  was  a  dead  end,  since  we  weren’t  coming  out  with  a  set  of  results  that  would  be  presentable  enough  to  be  placed  in  front  of  a  customer.  This  led  on  to  the  next  iteration,  which  grouped  colours  in  a  slightly  different  way.  

Figure  8:  Using  the  K-­‐Means  algorithm  to  cluster  similar  colours  yield  some  positive  results  but  with  a  significant  number  of  anomalies.  

Iteration  4:  Colour  Schemes  

Questioning  the  Goals  By  now,  it  was  clear  to  the  team  that  colour  grouping  in  the  way  that  competitors  were  doing  it  given  the  available  technologies  and  time  constraints  wasn’t  possible.  Aside  from  the  circumstances,  it  also  became  clear  that  even  if  our  targets  were  met  before,  the  program  still  wouldn’t  be  innovative  and  unique,  and  in  a  way  it  only  half  solves  the  problem.  

Product  Owner  James  Lewis  made  an  interesting  comment  at  this  point.  He  said,  “even  if  we  could  organise  all  2000  colours  in  a  neater  way  than  our  competitors,  why  should  our  customers  have  access  to  all  2000?  Surely  they’d  only  be  interested  in  a  certain  category  of  colours  depending  on  the  colours  of  their  existing  flooring  and  furniture?”  

This  prompted  the  temporary  suspension  of  development  and  the  initiation  of  some  more  market  research  before  the  topic  of  the  next  iteration  was  decided.  A  report  was  drafted  on  how  the  human  mind  perceives  colours  in  interior  design  and  which  colours  work  well  together  in  a  numerical  sense.  

The  report  acted  as  the  basis  for  the  next  iteration,  which  revolved  around  giving  users  access  to  a  limited  number  of  colours  based  on  the  current  colours  shown  in  their  room  when  they  took  a  picture  of  it.  

 

 

 

 

 

 

 

 

The  Idea  

Figure  9:  The  report  detailed  out  the  theory  behind  interior  design,  colour  harmonies  and  computer  vision.  

This  iteration’s  target  was  to  build  a  prototype  that  would  test  out  whether  James’  idea  would  be  effective  from  a  UX  perspective.  It  was  based  around  being  able  to  upload  a  photo,  click  on  a  colour  in  the  photo  you  wanted  to  match  and  then  being  presented  with  colour  harmonies  that  would  suit  that  particular  colour,  based  on  the  research  carried  out  prior  to  the  development.  

It  is  worth  noting  that  the  goal  was  to  deliver  value  as  soon  as  possible  and  so  some  aspects  of  the  software  built  were  simulated  in  order  to  deliver  the  minimum  viable  product  (MVP).  In  particular,  the  front  end  was  built  up  to  a  very  basic  standard  since  it  wasn’t  an  essential  component  at  this  stage-­‐  the  only  aspect  we  were  concerned  with  was  which  colours  the  users  were  being  shown  when  they  clicked  somewhere  on  their  image.  

The  Colour  Harmonies  The  colour  harmonies  that  were  studied  through  the  report  had  different  applications  for  different  interior  designs.  For  example,  a  complementary  colour  harmony  is  used  to  draw  attention  to  a  particular  design  element  whereas  an  analogous  scheme  is  used  to  keep  the  room  a  little  more  neutral.  

The  details  of  each  colour  scheme  is  beyond  the  scope  of  this  report  however  it  is  important  to  have  an  appreciation  for  how  these  colour  schemes  are  generated.  The  hue  (talked  about  earlier)  of  any  given  colour  lies  somewhere  on  the  colour  wheel  shown  in  Figure  3  and  is  stored  as  a  value  between  0  and  360  degrees.  A  colour  that  is  part  of  a  harmony  is  calculated  by  adding  a  certain  number  of  degrees  to  the  original  colour.  For  example,  to  obtain  the  complement  of  a  colour  for  a  complementary  harmony,  we  add  180  degrees  to  its  hue  and  mod  the  result  to  the  range  [0,  360].  

Once  a  colour  was  calculated,  the  program  would  then  find  the  colour  from  the  dataset  that  was  closest  to  it  and  use  it  as  the  output  since  the  user  would  be  selecting  a  colour  from  a  company’s  product  range  so  there  was  no  guarantee  that  the  exact  calculated  colour  would  be  available.  

 

The  Program  Structure:  Matplotl ib,  Grapefruit  and  NumPy  To  implement  this  iteration,  the  front  and  back  end  started  to  separate  into  separate  classes  and  files  due  to  the  growing  complexity  of  the  program.  The  program  structure  would  look  something  like  this:  

Figure  10:  The  program  had  a  front  end,  a  back  end  and  a  control  layer  in  between  to  regulate  the  flow  of  data.  

1. Back  End  

This  was  implemented  mainly  using  NumPy  and  Grapefruit  tools.  Grapefruit  is  a  Python  package  that  calculates  the  components  of  a  colour  harmony  described  earlier  given  an  input  colour  [8].  The  back  end  did  all  of  colour  calculations  using  this  package,  which  would  then  be  manipulated  further  by  NumPy  functions.  

2. Front  End  

This  was  the  part  of  the  program  that  a  user  would  interact  with  to  talk  to  the  software.  It  was  implemented  at  a  very  basic  level  using  Matplotlib’s  graphing  features.  At  a  very  basic  level,  Matplotlib  can  be  used  to  display  simple  graphs  on  a  panel.  On  a  slightly  more  advanced  level,  several  graphs  can  be  placed  on  the  same  panel  for  various  purposes  as  shown  in  Figure  11.  

This  feature  was  used  to  enable  us  to  display  several  colour  harmonies  on  screens.  The  graphs  were  substituted  for  images  (where  one  image  showed  on  colour  harmony)  as  Matplotlib  also  allows  for  the  display  of  images.  

3. Control  Layer  

This  was  an  intermediate  layer  between  the  front  and  back  end.  The  purpose  of  this  layer  was  to  tidy  up  the  data  transfer  between  the  other  two  components.  Since  this  code  was  to  be  modified  by  the  development  team,  it  was  essential  to  make  it  as  reusable  as  possible  by  adhering  to  good  code  organisation  practices.  A  typical  task  

Figure  11:  Matplotlib  allowed  for  several  graphs  to  be  displayed  on  one  graph.  This  feature  was  used  to  display  several  colour  harmonies  on  one  screen.  

of  this  layer  would  be  something  like  converting  a  colour  harmony  into  a  displayable  image  that  would  be  passed  on  to  the  front  end  to  show,  using  a  minimal  number  of  lines  of  code.  

 

The  Result  The  result  of  the  program  is  shown  in  Figure  12.  The  program  displays  the  following  items  (working  left  to  right,  top  to  bottom):  

• Uploaded  image:  this  is  the  image  of  the  user’s  room  they  wish  to  repaint.  They  would  supposedly  click  on  a  colour  in  their  room  that  they  are  interested  in  and  the  suggested  colours  would  be  based  on  that  one.  In  this  case,  we  have  clicked  on  the  far  pink  wall  of  the  room.  

• Selected  Colour:  this  is  a  tile  that  shows  the  user  which  colour  they  have  clicked  on.  

• Complementary,  split-­‐complementary,  triadic,  analogous  and  monochromatic  harmonies:  each  of  these  images  suggested  the  colours  that  would  match  the  selected  colour  in  the  context  of  the  respective  harmony.  As  mentioned  previously,  the  science  behind  each  harmony  is  outside  the  scope  of  this  report  however  the  colours  shown  in  Figure  12  are  the  ones  that  a  user  would  naturally  be  inclined  to  choose  based  on  their  selected  colour.  

• Similar  Colours:  this  was  a  last  minute  addition  to  this  iteration.  The  product  owner  suggested  it  in  case  the  user  was  interested  in  a  different  shade  of  the  colour  they  selected.  This  is  because  sometimes  they  might  click  on  a  colour  in  the  uploaded  image  that  is  not  quite  the  shade  they  want  due  to  factors  such  as  camera  and  lighting  quality.  They  could  then  click  on  a  similar  colour  that  is  the  shade  they  are  interested  in  and  the  harmonies  would  change  to  correspond  to  the  new  colour.  

Figure  12:  The  final  product  of  iteration  4.  

 

At  this  point,  the  team  was  happy  with  the  principle  of  only  giving  the  user  access  to  suggested  colours.  It  was  now  time  to  incorporate  what  had  been  developed  into  the  company’s  main  program.  

 

Figure  13:  The  program  is  shown  with  a  different  uploaded  image.  This  time,  the  colour  of  the  sofas  is  the  one  we  are  interested.  

Iteration  5:  Converting  the  Program  into  a  Web  API  The  focus  of  this  iteration  was  to  scrap  the  front-­‐end  of  what  was  developed  and  add  a  web  API  (Application  Programming  Interface)  to  the  back  end  so  that  it  could  be  integrated  into  the  main  system.  The  company’s  development  team  would  then  use  this  to  create  the  new  front  end.  

RESTful  APIs  and  Flask  To  meet  the  aim  of  this  iteration,  it  was  necessary  to  develop  a  RESTful  API.  A  RESTful  API  uses  HTTP  requests  such  as  GET,  PUT,  POST  and  DELETE  to  handle  data  generated  by  a  back  end  [9].  

Python  has  a  package  called  Flask  that  does  just  that  [10].  Many  programmers  use  Flask  to  create  web  applications  however  in  our  case  it  was  used  purely  to  create  the  API.  

There  isn’t  much  to  say  about  the  implementation  this  iteration  since  the  bottom  line  of  it  was  to  simply  take  what  the  back  end  was  outputting  to  the  control  layer  and  output  it  as  a  string  on  a  webpage  using  Flask’s  POST  function.  Figure  14  shows  the  output  of  the  web  API  when  a  random  colour  is  used  as  the  input.  The  whole  iteration  was  implemented  in  a  matter  of  days  using  very  few  lines  of  code.  

 

One  would  assume  that  the  program  at  this  point  would  be  ready  to  hand  over  to  the  development  team.  That  is  true  to  some  extent-­‐  the  software  in  its  current  state  would  be  ready  however  in  the  long  term  when  software  updates  and  additions  come  along  there  needs  to  be  a  way  to  ensure  that  the  code  that  was  written  is  still  compatible  with  whatever  is  integrated  with  it.  

By  this  stage  there  were  only  a  couple  of  weeks  left  of  the  placement,  so  the  remaining  time  was  spent  unit  testing  what  had  been  built  and  writing  up  its  documentation.  

Figure  14:  The  output  from  the  developed  web  API.  The  developers  that  created  the  new  front  end  used  this.  

Testing  

The  Types  of  Testing  There  are  two  types  of  testing  in  software  development:  unit  testing  and  integration  testing.  Unit  testing  is  the  process  of  testing  individual  functions  in  a  program  [11].  

Integration  testing  on  the  other  hand  tests  the  compatibility  of  a  new  piece  of  software  in  the  bigger  picture  i.e.  the  interaction  between  different  components  when  everything  has  been  put  together  [11].  

Since  integrating  the  software  into  the  main  program  was  outside  of  my  remit,  I  only  worked  on  unit  testing  for  this  part  of  the  software  development  cycle  and  the  integration  was  left  to  the  main  development  team.  

Unit  Testing  To  test  individual  components  of  the  software,  Python’s  Unit  Testing  library  was  used.  This  library  allows  a  programmer  to  enter  some  input  parameters  and  tell  the  program  what  output  to  expect  when  the  program  is  run  with  that  input.  

That  way,  when  the  code  is  refactored  all  that  needs  to  be  done  is  that  the  unit  tests  need  to  be  run  once.  If  the  command  line  shows  a  positive  output  such  as  that  in  Figure  16,  then  we  can  be  confident  that  the  code  does  what  it  is  supposed  to  be  doing.  An  example  of  a  unit  test  is  shown  in  Figure  15.  

Here,  we  are  testing  a  function  called  n_colours_is_valid,  which  is  in  the  utils  class.  The  first  three  tests  pass  a  parameter  to  the  function  that  should  cause  it  to  return  false.  The  fourth  and  fifth  tests  pass  a  parameter  that  should  cause  the  function  to  return  true.  When  this  unit  test  is  executed,  the  function  calls  are  made  and  the  actual  outputs  are  tested  against  

Figure  16:  This  is  the  output  of  a  set  of  Python  unit  tests  when  they  are  run  and  they  all  pass.  

Figure  15:  This  is  what  a  typical  unit  test  looks  like  in  Python.  

the  expected  outputs.  If  there  were  any  mismatches,  Python  would  give  us  the  details  of  them.  If  all  is  well  however,  then  we  are  given  an  “OK”  and  we  are  confident  that  our  functions  work  properly.  

Similar  tests  were  written  for  all  of  the  functions  within  the  program,  with  each  test  trying  out  correct,  edge  and  erroneous  inputs  to  ensure  that  the  code  was  thoroughly  tested.  With  all  tests  being  successful,  the  development  team  could  be  handed  over  the  code  with  confidence  that  it  was  working  according  to  its  specification.  

The  final  task  of  the  placement  was  to  write  up  the  documentation  for  the  code.  This  would  allow  future  developers  to  understand  the  code  better  when  it  came  to  altering  it.  

Documentation  One  lesson  that  was  learnt  during  the  placement  was  the  importance  of  documenting  code.  The  fact  that  a  human  wrote  the  code  means  that  it  needs  to  be  human-­‐readable  and  one  of  the  best  complements  to  well-­‐written  code  is  good  documentation.  

The  documentation  for  the  code  that  was  written  according  to  the  PEP  8  standard  which  is  a  set  of  guidelines  for  writing  good  Python  code,  tests  and  documentation  [12].    

Figure  17  shows  what  a  typical  piece  of  documentation  for  a  certain  function  would’ve  looked  like.  

 

Lines  10  to  13  described  any  input  parameters  that  were  required  for  a  function  to  ensure  that  the  correct  data  types  were  being  passed  to  the  function.  

Lines  14  to  17  described  exactly  what  the  function  returned  and  what  data  type  it  was  so  that  someone  maintaining  the  code  could  know  exactly  what  to  expect  from  the  function.  

Lines  18  onwards  would  be  any  extra  notes  about  the  particular  function  that  the  programmer  may  need  to  be  aware  of.  In  this  case  no  notes  have  been  written  about  the  function  since  the  function  name  clearly  explains  what  it  does.  

Figure  17:    This  sort  of  documentation  was  written  for  all  of  the  functions  that  had  been  created  during  the  placement.  

Evaluation  and  Conclusion  Although  I  believe  I  worked  hard  during  the  placement  and  developed  my  skills  a  great  deal,  I  would  do  certain  things  differently  if  I  could  start  again  since  there  is  always  room  for  growth  and  improvement.  

• I  would  try  to  be  a  lot  more  innovative  in  my  thinking.  The  fact  that  it  took  four  iterations  to  reach  a  product  that  delivered  value  shows  that  a  lot  of  time  was  wasted  in  the  first  couple  of  iterations.  This  reinforces  the  Pareto  principle  in  Software  Engineering  which  states  that  80%  of  the  value  is  found  in  20%  of  the  product  which  is  something  that  tech  companies  are  trying  to  avoid  in  order  to  be  more  efficient  compared  to  their  competitors  in  a  market  that  is  more  saturated  than  ever  [13].  

• I  would  spend  more  time  collaborating  with  fellow  employees  to  gain  a  second  perspective  on  the  work  I  was  doing.  I  very  rarely  spoke  to  my  colleagues  about  work  since  they  were  developing  completely  different  projects  so  it  never  crossed  my  mind  that  they  could  potentially  be  able  to  give  me  a  different  flavoured  input  to  possibly  take  a  different  approach  to  my  work  and  (hopefully)  deliver  more  value  faster  to  the  company.  

• I  would’ve  explored  various  other  Python  packages  to  widen  my  knowledge  of  the  programming  world.  I  was  always  very  reluctant  to  try  new  packages  and  techniques  for  my  code  since  I  naturally  tend  to  be  afraid  of  messing  up  something.  If  I  could  go  back  in  time  I  would  strive  to  be  more  courageous  in  trying  out  something  completely  new  and  convincing  myself  that  the  worst  thing  that  could  happen  would  be  that  my  code  would  fail,  which  isn’t  really  a  major  issue.  

The  placement  was  definitely  very  insightful  and  allowed  me  to  see  the  real  life  application  of  what  I  had  learned  during  the  previous  years  at  university.  I  developed  an  appreciation  for  the  software  development  world  as  well  as  for  the  Machine  Learning  and  Computer  Vision  fields-­‐  two  areas  that  I  was  previously  quite  oblivious  to.  

I  do  hope  that  the  code  I  developed  does  go  on  to  add  some  value  to  the  company  be  it  big  or  small  and  I  look  forward  to  graduating  and  working  a  lot  harder  in  the  world  of  Computer  Science  in  order  to  develop  my  knowledge  more  and  to  try  to  add  some  positivity  to  the  world  in  which  we  all  live  in.  

References  [1] Docs.scipy.org.  (2016).  What  is  NumPy?  —  NumPy  v1.10  Manual.  [online]  Available  

at:  http://docs.scipy.org/doc/numpy-­‐1.10.1/user/whatisnumpy.html  [Accessed  15  Sep.  2016].  

[2] Scikit-­‐learn.org.  (2016).  About  us  —  scikit-­‐learn  0.17.1  documentation.  [online]  Available  at:  http://scikit-­‐learn.org/stable/about.html  [Accessed  15  Sep.  2016].  

[3] Stackoverflow.com.  (2016).  Why  NumPy  instead  of  Python  lists?.  [online]  Available  at:  http://stackoverflow.com/questions/993984/why-­‐numpy-­‐instead-­‐of-­‐python-­‐lists  [Accessed  18  Sep.  2016].  

[4] Jain,  A.,  Murty,  M.  and  Flynn,  P.  (1999).  Data  Clustering.  [online]  Michigan  State  University,  Indian  Institute  of  Sciences,  Ohio  State  University.  Available  at:  https://www.cs.rutgers.edu/~mlittman/courses/lightai03/jain99data.pdf  [Accessed  18  Sep.  2016].  

[5] Matplotlib.org.  (2016).  matplotlib:  python  plotting  —  Matplotlib  1.5.3  documentation.  [online]  Available  at:  http://matplotlib.org/  [Accessed  21  Sep.  2016].  

[6] Agil,  M.  (2016).  Sorting  the  Wood  from  the  Trees.  Manchester:  The  University  of  Manchester.  

[7] Pele,  O.  and  Werman,  M.  (n.d.).  The  Quadratic-­‐Chi  Histogram  Distance  Family.  [online]  Jerusalem:  Hebrew  University  of  Jerusalem.  Available  at:  http://www.ariel.ac.il/sites/ofirpele/publications/eccv2010.pdf  [Accessed  18  Sep.  2016].  

[8] Pypi.python.org.  (2016).  grapefruit  0.1a3  :  Python  Package  Index.  [online]  Available  at:  https://pypi.python.org/pypi/grapefruit/0.1a3  [Accessed  21  Sep.  2016].  

[9] SearchCloudStorage.  (2016).  What  is  RESTful  API?  -­‐  Definition  from  WhatIs.com.  [online]  Available  at:  http://searchcloudstorage.techtarget.com/definition/RESTful-­‐API  [Accessed  22  Sep.  2016].  

[10] Flask.pocoo.org.  (2016).  Welcome  |  Flask  (A  Python  Microframework).  [online]  Available  at:  http://flask.pocoo.org/  [Accessed  22  Sep.  2016].  

[11] SearchSoftwareQuality.  (2016).  What  is  unit  testing?  -­‐  Definition  from  WhatIs.com.  [online]  Available  at:  http://searchsoftwarequality.techtarget.com/definition/unit-­‐testing  [Accessed  22  Sep.  2016].  

[12] Python.org.  (2016).  PEP  8  -­‐-­‐  Style  Guide  for  Python  Code.  [online]  Available  at:  https://www.python.org/dev/peps/pep-­‐0008/  [Accessed  23  Sep.  2016].  

[13] Kiremire,  A.  (2016).  THE  APPLICATION  OF  THE  PARETO  PRINCIPLE  IN  SOFTWARE  ENGINEERING..  [online]  Available  at:  http://www2.latech.edu/~box/ase/papers2011/Ankunda_termpaper.PDF  [Accessed  23  Sep.  2016].