Astronomical	  Data	  Compression:	  Algorithms	  &	  Architectures	  Rob	  Seaman	  –	  Na#onal	  Op#cal	  Astronomy	  Observatory	  William	  Pence	  –	  NASA	  /	  Goddard	  Space	  Flight	  Center	  Richard	  White	  –	  Space	  Telescope	  Science	  Ins#tute	  Séverin	  Gaudet	  –	  Na#onal	  Research	  Council	  Canada	  See	  also	  poster	  57,	  “Op#mal	  Compression	  Methods	  for	  Floa#ng-­‐point	  Format	  Images”,	  Pence,	  et	  al.	  

Astronomical	  Data	  Analysis	  SoAware	  &	  Systems	  XIX	  –	  Sapporo,	  Japan	  Agenda	  • Overview	  –	  Rob	  • Tile	  compression	  and	  CFITSIO	  –	  Bill	  • Experiences	  with	  FITS	  compression	  in	  a	  large	  astronomical	  archive	  –	  Séverin	  • Lossy	  compression	  –	  Rick	  • Open	  discussion	  • Door	  prize!	  
Thanks	  to	  Pete	  Marenfeld	  &	  Koji	  Mukai	  5	  October	  2009	  2	  Overview	  • FITS	  Ule	  compression	  • Rice	  algorithm	  • CFITSIO	  /	  FPACK	  • IRAF	  and	  community	  soAware	  • The	  ubiquity	  of	  noise:	  	  opUmal	  DN	  encoding	  • The	  role	  of	  sparsity:	  	  compressive	  sensing	  • An	  informaUon	  theory	  example	  5	  October	  2009	  3	  Overview	  • FITS	  Ule	  compression	  • Rice	  algorithm	  • CFITSIO	  /	  FPACK	  • IRAF	  and	  community	  soAware	  • The	  ubiquity	  of	  noise:	  	  opUmal	  DN	  encoding	  • The	  role	  of	  sparsity:	  	  compressive	  sensing	  • An	  informaUon	  theory	  example	  5	  October	  2009	  4	  References	  • Too	  many	  ADASS	  presentaUons	  to	  list	  • See	  references	  within:	  	  “Lossless	  Astronomical	  Image	  Compression	  and	  the	  Eﬀects	  of	  Noise”,	  Pence,	  Seaman	  &	  White,	  PASP	  v121	  n878	  2009,	  hPp://arxiv.org/abs/0903.2140v1	  5	  October	  2009	  5	  FITS	  Ule	  compression	  • ADASS	  1999	  (Pence,	  White,	  Greenﬁeld,	  Tody)	  • FITS	  ConvenUon	  v2.1,	  2009	  • Images	  mapped	  onto	  FITS	  binary	  tables	  • Headers	  remain	  readable	  • Tiling	  permits	  rapid	  RW	  access	  • Supports	  mulUple	  compression	  algorithms	  • First	  &	  every	  copy	  can	  be	  compressed	  5	  October	  2009	  6	  Rice	  algorithm	  • Fast	  (diﬀerence	  coding)	  – near	  opUmum	  compression	  raUo	  – throughput	  is	  key,	  not	  just	  storage	  volume	  • Numerical,	  not	  character-­‐based	  like	  gzip	  • Depends	  on	  pixel	  value	  so	  BITPIX	  =	  32	  compresses	  to	  same	  size	  as	  BITPIX	  =	  16	  5	  October	  2009	  7	  CFITSIO	  /	  FPACK	  • fpack	  can	  be	  swapped	  in	  for	  gzip	  	  &	  funpack	  for	  gunzip	  • Library	  support	  (eg,	  CFITSIO)	  allows	  jpeg-­‐like	  access	  –	  compression	  built	  into	  the	  format	  • More	  opUons	  means	  more	  parameters	  –	  	  sejng	  appropriate	  defaults	  is	  key	  5	  October	  2009	  8	  IRAF	  and	  community	  soAware	  • Tile	  compression	  can	  &	  should	  be	  supported	  by	  all	  soAware	  that	  reads	  FITS	  • Instrument	  and	  pipeline	  soAware	  may	  beneﬁt	  strongly	  from	  wri#ng	  compressed	  FITS	  • Transport	  &	  storage	  always	  beneﬁt	  • IRAF	  ﬁtsuUl	  package	  in	  beta	  tesUng	  • Work	  on	  a	  new	  IRAF	  FITS	  kernel	  pending	  • VO	  applicaUons	  and	  services	  5	  October	  2009	  9	  The	  ubiquity	  of	  noise	  • Noise	  is	  incompressible	  • Signals	  are	  correlated	  – physically	  – instrumentally	  • Shannon	  entropy:	  	  H	  =	  –	  Σ	  p	  log	  p	  – depends	  only	  on	  the	  probabiliUes	  of	  the	  states	  – measures	  “irreducible	  complexity”	  of	  the	  data	  5	  October	  2009	  10	  OpUmal	  DN	  encoding	  • CCD	  “square-­‐rooUng”	  • Variance	  stabilizaUon,	  more	  generally	  – many	  staUsUcal	  methods	  assume	  homoscedasUcity	  – generalized	  Anscombe	  transform	  • FoundaUons	  of	  the	  empirical	  world	  view:	  – ergodicity	  (staUsUcal	  homogeneity)	  – Markov	  processes	  (memoryless	  systems)	  • hPp://www.aspbooks.org/publica#ons/411/101.pdf	  5	  October	  2009	  11	  The	  role	  of	  sparsity	  • For	  most	  astronomical	  data,	  compression	  raUo	  depends	  only	  on	  the	  background	  noise	  – Sparse	  signals	  are	  negligible	  (in	  whatever	  axes)	  – Noise	  is	  incompressible	  	  R	  =	  BITPIX	  /	  (Nbits	  +	  K)	  	  K	  is	  about	  1.2	  for	  Rice	  5	  October	  2009	  12	  Compression	  raUo	  Mosaic	  II	  R	  16	  Dec	  2008	  Noise	  bits	  Compression	  correlates	  closely	  with	  noise	  DisUncUve	  funcUonal	  behavior	  For	  three	  very	  diﬀerent	  comp.	  algorithms	  For	  ﬂat-­‐ﬁeld	  and	  bias	  exposures	  as	  well	  	  	  	  	  	  	  as	  for	  science	  data	  That	  is,	  for	  pictures	  of:	  the	  sky	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  	  a	  lamp	  in	  the	  dome	  	  no	  exposure	  at	  all	  Signal	  doesn’t	  maser!	  –8–A	  beser	  compression	  diagram	  15

R1.2Compressed bits per pixel

Lossy	  algorithms	  shi^	  le^	  to	  move	  down	  1.5

10

2.0
50

K
432
10016	  Dec	  2008	  GZIP	  4.0Rice	  Hcompress	  Margin	  for	  improvement	  510	  R	  =	  BITPIX	  /	  (Nbits	  +	  K)	  	  EﬀecUve	  BITPIX:	  	   	  BITEFF	  =	  BITPIX	  /	  R	  	   	  BITEFF	  =	  Nbits	  +	  K	  	  Line	  with:	  	  Slope	  =	  1	  	  Intercept	  =	  K	  15Nbits Noise

Fig. 1.— Plot of compressed bits per pixel versus the number of noise bits in 16-bit synthetic
images. The solid lines are generated from the images that have N bits of pure noise, and theCompressive	  sensing	  • Real	  world	  data	  are	  oAen	  sparse	  (correlated)	  • Nyquist/Shannon	  sampling	  applies	  broadly	  • But	  we	  can	  do	  even	  beser	  if	  we	  sample	  against	  purpose-­‐speciﬁc	  axes:	  hPp://www.dsp.ece.rice.edu/cs	  hPp://nuit-­‐blanche.blogspot.com	  • Herschel	  proof	  of	  concept,	  Starck,	  et	  al.	  
• CS	  is	  about	  the	  sampling	  theorem	  • OpUmal	  encoding	  is	  about	  quanUzaUon	  5	  October	  2009	  15	  hPp://www.mapsofconsciousness.com/12coins	  An	  informaUon	  theory	  example	  example of objective

5	  October	  2009	  16	  About the CoinsIf you like this game send feedback

Compression	  =	  opUmal	  representaUon	  A. 11	  coins	  all	  the	  same	  	  +	  1	  coin,	  idenUcal	  except	  for	  weight	  B. Scale	  to	  weigh	  groups	  of	  coins	  C. In	  only	  3	  steps,	  must	  idenUfy:	  	  the	  coin	  that	  is	  diﬀerent	  and	  	  whether	  it	  is	  light	  or	  heavy	  “The	  12-­‐balls	  Problem	  as	  an	  IllustraUon	  of	  the	  ApplicaUon	  of	  InformaUon	  Theory”	  –	  R.H.	  Thouless,	  1970,	  Math.	  GazePe,	  v54n389.	  
5	  October	  2009	  17	  How	  to	  solve	  a	  problem	  • First,	  deﬁne	  the	  problem	  – second,	  entertain	  soluUons	  – third,	  iterate	  (don’t	  give	  up)	  • More	  basic	  yet,	  what	  is	  the	  goal?	  
– to	  solve	  the	  problem?	  
– or	  to	  understand	  how	  to	  solve	  it?	  

• StaUng	  a	  problem	  constrains	  its	  soluUons	  5	  October	  2009	  18	  What	  do	  we	  know?	  
• One	  bit	  discriminates	  two	  equally	  likely	  alternaUves	  	  To	  select	  between	  N	  equal	  choices,	  Nbits	  =	  log2	  N	  • For	  12-­‐coin	  problem,	  Nbits	  =	  log2	  (12)	  +	  1	  =	  log2	  24	  	  (must	  also	  disUnguish	  light	  vs.	  heavy)	  • InformaUon	  provided	  in	  each	  measurement	  is	  log2	  3	  	  (3	  posiUons	  for	  scale:	  le^,	  right,	  balanced)	  • For	  three	  weighings,	  Wbits	  =	  log2	  33	  =	  log2	  27	  	  Meets	  necessary	  condiUon	  that	  Wbits	  >=	  Nbits	  5	  October	  2009	  19	  Necessary,	  but	  not	  suﬃcient	  • A	  strategy	  is	  also	  necessary	  such	  that	  	  	   	  Wbits	  >=	  Nbits	  	  (remaining)	  	  is	  saUsﬁed	  at	  each	  step	  to	  the	  soluUon	  	  	  	  • Nbits	  is	  the	  same	  thing	  as	  the	  entropy	  H	   	  H	  =	  –	  Σ	  p	  log	  p	  	  	  	  where	  	  	  p	  =	  1/N	  	  	  	  	  	  	  =	  –	  Σ	  (1/N)	  log	  (1/N)	  =	  (Σ	  (1/N))	  log	  N	  =	  log	  N	  	  	  H	  =	  log2	  N	  	  	  (in	  bits)	  5	  October	  2009	  20	  What	  else	  do	  we	  know?	  
• Physical	  priors!	  
– only	  one	  coin	  is	  fake	  – astronomical	  data	  occupy	  sparse	  phase	  space	  • FITS	  arrays	  =	  images	  (physical	  priors)	  – of	  astrophysical	  sources	  – taken	  through	  physical	  opUcs	  – recorded	  by	  physical	  electronics	  – digiUzaUon	  is	  	  restricted	  by	  informaUon	  theory	  – possessing	  a	  disUncUve	  noise	  model	  5	  October	  2009	  21	  5	  October	  2009	  22	  example of objective

5	  October	  2009	  23	  example of objective

5	  October	  2009	  24	  example of objective

5	  October	  2009	  25	  example of objective

ObservaUons	  about	  observaUons	  • The	  sequence	  of	  three	  measurements	  can	  occur	  in	  any	  order	  • The	  systemaUzaUon	  of	  the	  soluUon	  occurs	  during	  its	  deﬁniUon,	  not	  at	  run	  Ume	  5	  October	  2009	  26	  Try	  it	  yourself	  hPp://heasarc.gsfc.nasa.gov/ﬁtsio/fpack	  hPp://www.mapsofconsciousness.com/12coins	  5	  October	  2009	  27