Nof S.Y. Springer Handbook of Automation

Подождите немного. Документ загружается.

1645

Collaborative

93. Collaborative Analytics

for Astrophysics Explorations

Cecilia R. Aragon

Many of today’s important scientiﬁc breakthroughs

are made by large, interdisciplinary collabo-

rations of scientists working in geographically

distributed locations, producing and collecting

vast and complex datasets. Experimental as-

trophysics, in particular, has recently become

a data-intensive science after many decades of

relative data poverty. These large-scale science

projects require software tools that support not

only insight into complex data but collabora-

tive science discovery. Such projects do not easily

lend themselves to fully automated solutions, re-

quiring hybrid human–automation systems that

facilitate scientist input at key points throughout

the data analysis and scientiﬁc discovery process.

This chapter presents some of the issues to con-

sider when developing such software tools, and

describes Sunfall, a collaborative visual analytics

system developed for the Nearby Supernova Fac-

tory, an international astrophysics experiment and

the largest data volume supernova search currently

in operation. Sunfall utilizes novel interactive vi-

sualization and analysis techniques to facilitate

deeper scientiﬁc insight into complex, noisy, high-

dimensional, high-volume, time-critical data. The

system combines novel image-processing algo-

93.1 Scope ..................................................1645

93.2 Science Background ..............................1646

93.3 Previous Work ......................................1648

93.4 Sunfall Design Process...........................1649

93.5 Sunfall Architecture and Components .....1650

93.5.1 Search ...................................... 1650

93.5.2 Workﬂow Status Monitor ............. 1655

93.5.3 Data Forklift ..............................1655

93.5.4 Supernova Warehouse ................1657

93.6 Conclusions..........................................1666

93.6.1 Future Research Directions .......... 1668

References ..................................................1668

rithms, statistical analysis, and machine learning

with highly interactive visual interfaces to enable

collaborative, user-driven scientiﬁc exploration

of supernova image and spectral data. Sunfall is

currently in operation at the Nearby Supernova

Factory; it is the ﬁrst visual analytics system in

production use at a major astrophysics project.

The chapter concludes with a set of guidelines

and lessons learned about developing software to

support scientiﬁc collaborations.

93.1 Scope

Computational and experimental sciencesare producing

and collecting ever-larger and complex datasets, often

in large-scale, multi-institution projects. The inability

to gain insight into complex scientiﬁc phenomena using

current software tools is a bottleneck facing virtually

all endeavors of science. As scientiﬁc datasets explode

at an exponential rate, present-day systems are strug-

gling to capture, process, store, transfer, and interpret

data many orders of magnitude greater than scientists

have seen before. Computational challenges are aris-

ing in unexpected areas, not just in requirements for

processor speed, but in software development, scalabil-

ity, data transfer, and ﬁle management. Additionally, it

is not sufﬁcient merely to solve the automation chal-

lenges; scientiﬁc insight and decision-making require

human interaction and smooth collaboration with au-

tomated systems. However, there are few guidelines or

examples to support the interdisciplinary developers of

Part I 93

1646 Part I Home, Ofﬁce, and Enterprise Automation

collaborative scientiﬁc analytics systems, which need

to integrate tools and techniques from a broad array

of computing disciplines with highly sophisticated and

rapidly changing domain-speciﬁc scientiﬁc algorithms,

as well as incorporate effective human–computer inter-

action design for scientists.

Among all the sciences, experimental astrophysics

is undergoing extraordinarily rapid growth in observa-

tional image data captured, at the precise time that new

and tantalizing questions about the nature of the uni-

verse have arisen, the answers to which will require

study of ever-larger areas of the sky in ever-greater de-

tail. As a result, the nature of astrophysics research itself

is changing, and many of the algorithms developed for

processing astronomical data, although well established

for low-volume data capture, do not scale well to to-

day’s high-volume sky surveys and transient searches.

One of the grand challenges in astrophysics today

is the effort to comprehend the mysterious dark energy,

which accounts for three-quarters of the matter/energy

budget of the universe. The existence of dark energy

may well require the development of new theories of

physics and cosmology. Dark energy acts to accelerate

the expansion of the universe (as opposed to gravity,

which acts to decelerate the expansion). Our current un-

derstanding of dark energy comes primarily from the

study of supernovae (SNe).

The Nearby Supernova Factory (SNfactory) [93.1]

is an international astrophysics experiment designed to

discover and measure type Ia supernovae in greater

number and detail than has ever been done before.

These supernovae are stellar explosions (Fig.93.1)that

have a consistent maximum brightness, allowing them

to be used as standard candles to measure distances to

other galaxies and to trace the rate of expansion of the

universe and how dark energy affects the structure of

the cosmos.

In order to facilitatethe astrophysicssearch and data

analysis process and enable scientiﬁc discovery for ob-

servationalastrophysicists, an interdisciplinary group of

computer scientists, software engineers, and astrophysi-

cists developed the Supernova Factory Assembly Line

(Sunfall), a collaborative visual analytics system for the

Nearby Supernova Factory that has been in production

use since 2006 [93.2]. Sunfall incorporates:

Fig. 93.1 Hubble Space Telescope image of supernova

SN1994D in galaxy NGC4526, observed 1994

•

Novel astrophysics image-processing algorithms

running in parallel on a 300node cluster

•

Machine learning capabilities including boosted de-

cision trees and support vector machines

•

A specialized data transfer mechanism that not only

manages a large amount of data on a 24/7 basis,

but also robustly handles the error-free transfers of

a large number of small ﬁles

•

Highly interactive visual interfaces to enable collab-

orative, user-driven scientiﬁc exploration of super-

nova image and spectral data.

The remainder of this chapter is structured as fol-

lows. Section 93.2 describes the science background for

supernova detection and spectral analysis, including the

SNfactory project data ﬂow. Section 93.3 contains in-

formation on previous work, including systems built for

other supernova experiments and other scientiﬁc work-

ﬂow systems. Section 93.4 discusses the Sunfall design

approach, and Sect.93.5 describes the Sunfall archi-

tecture in detail, including its four major components:

Search, Workﬂow Status Monitor, Data Forklift, and

Supernova Warehouse. Section 93.6 discusses lessons

learned and presents our conclusions and their poten-

tial impact on the ﬁelds of astronomy and cosmology,

as many more such large-scale surveys are planned for

the future as physicists attempt to unravel the mystery

of dark energy.

93.2 Science Background

The discovery of dark energy is primarily due to ob-

servations of type Ia supernovae at high redshift (up

to z = 1, or a lookback time of about 8billion years)

[93.3, 4]. This supernova cosmology technique hinges

Part I 93.2

Collaborative Analytics for Astrophysics Explorations 93.2 Science Background 1647

on the ability to reliably compare luminosities of high-

redshift events to those at low redshift, necessitating

detailed study of low-redshiftevents. Large-scale digital

sky surveys are now being planned in order to constrain

the properties of dark energy. These studies typically

involve high-volume, time-constrained processing of

wide-ﬁeld charge-coupled device (CCD) images, in or-

der to detect type Ia SNe and capture detailed images

and spectra on multiple nights over their lifespans.

A stellar explosion resulting in a type Ia SN will oc-

cur on average only once or twice per millennium in

a typical galaxy of 400 billion stars, and then will re-

main visible for only a few weeks to a few months.

Additionally, themaximum scientiﬁcbeneﬁt is obtained

if the supernova is discovered as early as possible be-

fore it attains peak brightness. To further add to the

challenge, the imaging data from which SNe must be

detected are extremely noisy, corrupted with spurious

objects such as cosmic rays, satellite tracks, asteroids,

and CCD artifacts such as diffraction spikes, saturated

pixels, and ghosts.

The SNfactory was designed to accumulate the

largest homogeneously calibrated spectrophotometric

(containing both images and spectra) dataset ever stud-

ied of type Ia SNe in the nearby redshift range

(0.03 < z < 0.08, or about 0.4–1.1billion light years

distant) [93.1]. On a typical night, 50–80GB of

data (approximately 30000 images containing 600000

potential supernovae) are received by SNfactory

image-processing software. These data are processed

overnight; the best candidates are selected each morn-

ing by humans for further follow-up measurements.

Likely candidate supernovae are sent to a dedicated

custom-built spectrograph for follow-up imaging and

spectrography. The resulting spectra typically each con-

a) b) c)

Fig. 93.2a–c Example supernova images. (a) Reference image of galaxy, (b) new image of galaxy plus new bright spot,

tain 2000–3000 data points of ﬂux as a function of

wavelength. The SNfactory database will be released

to astronomers worldwide and become a deﬁnitive re-

source for measurements of dark energy. This program

is the largest data volume supernova search currently in

operation.

The SNfactory obtains wide-ﬁeld imaging data

from the Near-Earth Asteroid Tracking Program

(NEAT) [93.5] using the 112 CCD QUEST II camera

of the Mt. Palomar Oschin 1.2m telescope [93.6], cov-

ering 8.5square degrees per exposure. (For comparison,

the full moon covers 0.2square degrees.)

Images are transferred from Mt. Palomar via the

High-Performance Wireless Research and Education

Network (HPWREN) to the High-Performance Stor-

age System (HPSS) at the National Energy Research

Scientiﬁc Computing Center (NERSC) in Oakland,

California. Each morning, SNfactory search software

running on NERSC’s 300node computing cluster, the

Parallel Distributed Systems Facility (PDSF), matches

images ofthe same area of thesky, processesthem to re-

move noise and CCD artifacts, then performs an image

subtraction from previously observed reference images

on each set of matched images (Fig.93.2) [93.7–10].

Supernova candidates are identiﬁed from among

the over 600 000 objects processed per night by a set

of image features including object shape (roundness

and contour irregularity computed from Fourier contour

descriptors) [93.7, 11], position, distance from nearest

object, and motion. These features are used as input to

machine learning algorithms that select candidates to

be sent to humans for scanning and vetting [93.8, 9].

Promising SN candidates that pass the human scan-

ning andvetting procedure aresent for conﬁrmation and

spectrophotometric follow-upby theSupernova Integral

Part I 93.2

1648 Part I Home, Ofﬁce, and Enterprise Automation

Field Spectrograph (SNIFS) [93.12] on the University

of Hawaii 2.2m telescope on Mauna Kea, Hawaii.

Candidates are imaged through a 15×15 microlens

array on SNIFS and the spectral data are saved to

a database in France. The SNIFS observing process

is challenging. The telescope is operated remotely, via

a text-based legacy control system. Astronomers must

be able to analyze and evaluate a large amount of data

and make cognitively demanding calculations under

time pressure (in some cases in as little as 45s), while

at the same time being fully aware of changing weather

conditions, the approach of daylight, and other safety

issues. They must focus on individually demanding and

precise tasks while maintaining an overall understand-

ing of a large amount of dynamic data affecting the

telescope’s operation and safety.

Understanding type Ia SNe through their spec-

tra is important because it places constraints on their

presupernova evolution and the immediate stellar en-

vironment of the event, and provides clues that can

expose correlations between peak brightness and the

physics of the explosion. With a better understanding

of the physics of type Ia SNe through their spectra,

it is believed that their utility as standardized can-

dles for cosmological distance measurements can be

reﬁned for their use in future precision cosmology

experiments such as the Joint Dark Energy Mission

(JDEM) [93.13].

93.3 Previous Work

We discuss related work in the areas of astronomical

applications, speciﬁcally software developed for large-

scale supernova searches, and more generally including

astronomical calculations and visualizations, and visual

analytics systems developed for cognitively loaded or

time-pressured users. We also brieﬂy touch on scien-

tiﬁc analytics and situation awareness research, as the

development of situationawarenessat thetelescope dur-

ing observation is critical for astrophysics experiment

success.

Since the discovery of dark energy via studies of

type Ia supernovae nearly a decade ago [93.3,4], astro-

physicists have developed several large-scale supernova

searches to collect as much data as possible on these

rare events. These searches typically rely on custom

image subtraction software containing highly complex,

hand-tuned heuristics and cuts to extract supernova

candidates. They are often plagued by large numbers

of false positives, which must then be screened out

by humans in a labor-intensive process. For example,

the 2005 Sloan Digital Sky Survey II (SDSS) super-

nova program generated approximately 4000 objects

per night which needed to be visually checked by hu-

mans for veriﬁcation [93.14]. The Equation of State:

Supernovae Trace Cosmic Expansion (ESSENCE)and

Supernova Legacy Survey (SNLS) supernova searches

both resulted in 100–200 objects to scan per night

with a signiﬁcantly smaller input data load than the

SNfactory [93.15]. Techniques used in these surveys

will not scale to future, much larger data sets.

In 2005, theSNfactory pioneered theuse ofmachine

learning algorithms to replace cuts for supernova object

detection [93.9], and since then, such techniques have

been utilized by other supernova searches, including

SDSS and SNLS [93.14, 15]. The SDSS autoscanner

uses a combination of heuristics and a naive Bayes

classiﬁer to ﬁlter out non-SN objects, but they do

not provide a comparison of the efﬁcacy of any other

types of machine learning algorithms for supernova

search. SNLS uses multinight data and an artiﬁcial neu-

ral net to screen candidates; however, their techniques

are not applicable to large-scale, rapid transient alert

pipelines.

After supernova data have been collected, they are

typically stored in a databaseaccessible viaa web-based

interface. These websites display information in tabular

form, listing the supernova coordinates and providing

links to images. They are designed to provide all the

necessary information for astronomers to observe su-

pernovae with their own telescopes. Examples are the

SNLS and SDSS web sites [93.16,17]. In [93.14], Sako

et al. describe the SDSS software tools for supernova

search and follow-up. They include sets of scripts that

perform functions similar to parts of Sunfall, but require

human intervention at numerous stages during the su-

pernova search and follow-up process. None of these

groups has built a complete scientiﬁc analytics system

that enables human–automation collaboration and en-

compasses theentire data search,analysis, and scientiﬁc

discovery process.

The astronomical calculations in the Sky visual-

ization used in Sunfall Data Taking are derived from

SkyCalc, originally written by Thorstensen [93.18,19].

Previously, astronomers would run SkyCalc from the

Part I 93.3

Collaborative Analytics for Astrophysics Explorations 93.4 Sunfall Design Process 1649

command line at the telescope, inputting their observa-

tory parameters, observing date, and target lists. This

would provide times of sun and moon rise/set and

hourly tables of the elevations of each target. The as-

tronomer would then try to collate this information, but

would have to re-input many parameters to examine

a slightly different what–if scenario. Visual wrappers

to SkyCalc have been developed before, including

Thorstensen’s SkyCalc GUI and SkyCalcDisp [93.18,

19]; however, the former is simply a graphical version

of the command-line interface and the latter contains

a three-dimensional projection of object positions that

does not facilitate prediction of target motion. On the

other hand, the Sky visualization in Sunfall Data Tak-

ing was designed speciﬁcally to help the astronomer

balance the above-described constraints in a visually in-

tuitive way – often during a nighttime observing session

– at the click of a button.

The Sky differs from other astronomy visualiza-

tion programs in that many of them are after-the-fact

image-processing programs, designed to enhance faint

or low-contrast image data, rather than to provide an

operational simpliﬁcation to aid in time-constrained

observational decisions [93.20–22]. Astronomers fre-

quently use tools such as SAOImage ds9 (Smithsonian

Astrophysical Observatory Image ds9) [93.23] for de-

tailed viewing of their images, or Image Reduction and

Analysis Facility (IRAF) [93.24] for spectral visual-

ization. However, neither of these is integrated into an

observing package as is Sunfall data taking.

In the ﬁeld of scientiﬁc visualization for astronomy,

software such as Li et al.’s scalable World-In-Miniature

(WIM) [93.25] focuses on the ability to browse

a large-scale three-dimensional model of the universe.

However, this technique is not designed for use under

time pressure.

There has been much recent work in the develop-

ment of systems designed for ﬁrst responders and other

cognitively loaded users, including several systems to

visualize time-varying data [93.26–29], noting the con-

straints of updating time-critical visual information on

a low-resolution device. Other efforts to develop mobile

systems for emergency response include the Measured

Response Project of the Purdue Synthetic Environment

for Analysis and Simulation [93.30].

Related efforts involve approaches to visualizing

time-varying geographic data, such as [93.31–33], and

Tesone and Goodall have developed a visual analytics

technique, smart aggregation, speciﬁcally to aid with

situation awareness [93.34]. There is a large body of

literature on situation awareness in general, and a full

description of such literature is beyond the scope of

this chapter. The book by Endsley and Garland [93.35]

provides an excellent survey of the work in this area.

93.4 Sunfall Design Process

In order to design an effective collaborative visual an-

alytics system for the SNfactory, we ﬁrst conducted,

in mid-2005, an extensive, 2month evaluation of the

existing SNfactory procedures and environment. Data

sources used for evaluation included individual inter-

views, observation of team members performing typical

project tasks, review of existing source code, litera-

ture reviews, examination of other supernova search

projects, and consultation with physicists and computer

scientists with relevant experience building similar sci-

entiﬁc software systems.

We conducted over 100h of interviews with

Lawrence Berkeley National Laboratory (LBNL)sci-

entists, postdoctoral researchers, and students, and

SNfactory collaboration members outside LBNL. This

included 19 current and former team and collaboration

members, and 12 scientists with relevant experience

outside the SNfactory collaboration. We also performed

a detailed software review of over 150000lines of

SNfactory legacy code in C++, Interactive Data Lan-

guage (IDL), Perl, and shell scripts.

We established the following requirements for the

Sunfall software framework: It must encompass the

entire scientiﬁc data capture, processing, storage, and

analysis process, enable collaborative, time-critical sci-

entiﬁc discovery, and incorporate SNfactory legacy

code (custom astronomical image-processing algo-

rithms). It must reduce the number of false positives

sent to humans and improve the quality of the subtrac-

tion image processing. It must automate repetitive data

transfers and other manual tasks to leverage domain ex-

perts’ uniqueprocessing and image-recognition skills to

the maximum extent.

The Sunfall user interface was designed and im-

plemented using participatory and iterative design

techniques; for example, interactive prototypes were

used to evaluate areas where existing interfaces did

not support scientists’ workﬂow. Scientists’ feedback

Part I 93.4

1650 Part I Home, Ofﬁce, and Enterprise Automation

sometimes led to major redesigns of the interface. The

system was implemented from the beginning with this

possibility in mind, so that changes were easily made

and accepted as an appropriate part of the development

process [93.36]. Sunfall has been in operation at the

SNfactory since 2006.

93.5 Sunfall Architecture and Components

Sunfall consists of four major components: Search,

Workﬂow Status Monitor, Data Forklift, and Supernova

Warehouse (Fig.93.3). This section will describe each

component’s structure in detail.

The Search component handles image processing

and subtraction, and includes machine learning algo-

rithms and novel Fourier contour descriptor algorithms

to reduce the number of false-positive SN candidates.

The Workﬂow Status Monitor is a web-based dash-

board that facilitates collaboration and improves project

scientists’ situational awareness of the data ﬂow by

displaying all relevant (search pipeline) status data on

a single site.

The Data Forklift is a middleware mechanism con-

sisting of a coordinator and a suite of services to

automate astronomical data transfers in a secure, re-

liable, extensible, and fault-tolerant manner. The Data

Forklift also provides the middleware for the other

three components, transferring data between heteroge-

neous systems, databases, and formats securely and

reliably.

Sunfall

Supernova

Warehouse

SNwarehouse

PostgreSQL

= Data Forklift

Vetting,

data taking,

spectral

analysis

Image storage

(tape, disk)

Workflow Status Monitor

Warehouse GUI

SNF DB

NEAT

(Near Earth

asteroid tracking

images)

Fig. 93.3 Sunfall architecture diagram depicting the four components (Search, Workﬂow Status Monitor, Data Forklift,

and Supernova Warehouse) and data ﬂow between the components

The Supernova Warehouse (SNwarehouse) is

a comprehensive supernova data management, work-

ﬂow visualization, and collaborative scientiﬁc anal-

ysis tool. The SNwarehouse contains a PostgreSQL

database, Forklift middleware, and a graphical user in-

terface implemented in Java.

93.5.1 Search

The supernova search component of Sunfall is an ex-

ample of analytic discourse, deﬁned by Thomas and

Cook in Illuminating the Path [93.37]as“theinter-

active, computer-mediated process of applying human

judgment to assess an issue”, applied to the realm of

astrophysics. Sunfall search has increased efﬁciency of

supernova detection and enabled more effective human

intervention by reducing the number of false-positive

candidates by nearly an order of magnitude [93.8, 9]

and, through the use of intelligent interfaces, by in-

creasing human efﬁciency in evaluating candidates by

a factor of four [93.2,36].

Part I 93.5

Collaborative Analytics for Astrophysics Explorations 93.5 Sunfall Architecture and Components 1651

The legacy search software computed 19 photomet-

ric and geometric features on each of over 600 000 SN

candidate subimages per night and applied threshold

cuts to each of these features. Subimages that satis-

ﬁed all thresholds (1094 on a typical night in October

2005, before the new software was put into production)

were sent to human scanners who selected potential SN

candidates for follow-up study. The majority of subim-

ages that passed the thresholds were false positives that

humans had to manually reject. These manually tuned

thresholds were brittle and often resulted in both missed

SNe and too many false positives for human scanners to

evaluate daily. The process of scanning on the order of

1000 subimages took 6–8 people several hours per day.

We ﬁrst developed a set of new features for im-

proved image detection, including the use of a very

efﬁcient (O(k), where k is the pixel diameter of a super-

nova candidate) Fourier contour analysis algorithm for

determining the shape of an object, described in more

detail in the section on fast contour descriptor algorithm

for supernova image classiﬁcation [93.7].

Machine learning algorithms, including support

vector machines and boosted trees, were evaluated for

incorporation into the search software. By replacing

simple threshold cuts on the image features with clas-

siﬁers of the high-dimensional data in the feature space,

we reduced the number of false positives by a factor

of ten while increasing our rate of supernova detection.

We applied several different classiﬁcation algorithms,

a) b) c) d)

e) f) g) h)

Fig. 93.5a–h Visual scanning interface. Top row: three new images (a–c), (d) reference image. Bottom row:three

subtractions

(e–g), (h) negative subtraction

0 0.2

Original threshold cuts

Support vector machine

Random forest

Boosted tree

0.4 0.6 0.8 1

False-positive rate

True-positive rate (signal efficiency)

–1

–2

–3

–4

–5

Fig. 93.4 Comparison of boosted trees (solid line), ran-

dom forest (dashed line), and support vector machines

(dotted line) for false-positive identiﬁcation fraction ver-

sus true-positive identiﬁcation fraction. The square shows

the performance of the original threshold cuts. The lower

right corner of the plot represents ideal performance (af-

ter [93.8])

including boosted trees, random forests, support vector

machines, and combinations of the above. All clas-

siﬁers provided signiﬁcantly better performance over

Part I 93.5

1652 Part I Home, Ofﬁce, and Enterprise Automation

the conventional threshold cuts. Boosted trees pro-

duced the best classiﬁcation performance overall [93.8]

(Fig.93.4) and signiﬁcantly decreased scientists’ work-

load by reducing the number of false positives by an or-

der of magnitude (from 1094 to 113 on typical nights in

2005 and 2006). This resulted in labor savings of nearly

90%, where the process of scanning now takes one per-

son a couple of hours each day [93.2,9]. Additionally,

system tests determined that the new algorithms had

a true-positive ratio equal to or better than the original

algorithm (in other words, they did not miss any more

actual supernovae). The data are depicted in Fig.93.4.

Currently, of the approximately 100 visually

scanned subimages per night, about 10–30 are ﬂagged

as containing potential supernova candidates. These

candidates (about 0.001–0.01% of the objects originally

imaged) are sent to the SNIFS spectrograph for spec-

trophotometric screening and follow-up. Typically two

to ﬁve of the objects examined by SNIFS will ﬁnally

be determined to be supernovae, of which (on average)

about one per night is the sought-after type Ia super-

nova. Thus, of the objects originally imaged, some-

where near 0.0002% prove to be type Ia supernovae.

For conﬁrmation and selection of promising super-

nova candidates, the scanners use a visual interface

to view and analyze the candidates (Figs. 93.5 and

93.6). This visual scanning interface was redesigned to

increase interactivity and allow humans to focus exclu-

Fig. 93.6 Visual interface for managing image subtraction workﬂow

sively on the imagery itself. Previously, scientists spent

much of their time cutting and pasting long ﬁlenames,

pausing the scanning process to look up data on sev-

eral different external web sites, and waiting for image

data to be retrieved from tape storage. Formerly, this

process took 2min per candidate on average; with this

interface and other Sunfall tools, a decision could be

made within 30s.

By applying intelligent algorithms to the search

data, and by developing intelligent visual interfaces to

view the data, we were able to leverage the unique

human abilities that enable the ﬁnal detection of true su-

pernova candidates, and not only minimize the number

of false positives, but also increase the efﬁciency of the

spectroscopic follow-up. Techniques such as these are

critical for successful human–automation collaboration

in scientiﬁc experiments.As an example ofan algorithm

we developed to maximize the effectiveness of human

visual pattern-recognition ability by screening out bad

supernova candidates before they are presented to users,

we now describe our fast contour descriptor algorithm

in more detail.

A Fast Contour Descriptor Algorithm

for Supernova Image Classiﬁcation

Fourier descriptors are an established method for

parameterizing the outer contour of an object by

decomposing it in terms of complex exponential func-

Part I 93.5

Collaborative Analytics for Astrophysics Explorations 93.5 Sunfall Architecture and Components 1653

tions [93.11]. However, Fourier-transform-based meth-

ods were initially considered infeasible, due to their

computational complexity, for the high-throughput re-

quirements of the Supernova Factory. We devised an

extremely fast contour descriptor implementation that

meets the processing budget of the application. Noting

that the lowest-order descriptors (F

and F

−1

)convey

the circular or elliptical aspect of the contour, our fea-

tures are based on those two terms and the total variance

or power in the contour. The features are thus equipped

to detect eccentric or irregular objects, classes to which

the poor candidates generally belong.

Our fast contour descriptor algorithm was applied

to 600000 candidate objects in 50–80 GB of supernova

image data per night. Our shape-detection algorithm

reduced the number of false positives generated by

the supernova search pipeline by 41% while produc-

ing no measurable impact on running time. Because the

number of Fourier terms to be calculated is ﬁxed and

small, the algorithm runs in linear time, rather than the

O(n logn) time of a fast Fourier transform (FFT). Con-

straints on objectsize allow further optimizationsso that

the total cost of producing the required contour descrip-

tors is about 4n addition/subtraction operations, where

n is the length of the contour.

Because transform-based image analysis methods

are often avoided in high-throughput applications due

to their computational cost, it is important to distinguish

the contour Fourier descriptor from other Fourier-based

methods. For a two-dimensional image of diameter D

pixels, the processing time for a Fourier transform of

the image can scale as severely as D

. In fortunate

cases where the Cooley–Tukey FFT [93.11,38,39] can

be used, the processing still scales as D

log(D

). The

contour Fourier descriptor operates not on the object

image but on its outer contour, which is essentially

a one-dimensional(albeit complex-valued)sequence, of

length proportional to object diameter D. Since we cal-

culate a ﬁxed number of terms rather than requiring

a full discrete Fourier transform (DFT), the calculation

time is actually proportional to D.

Algorithm Overview. We compute two new features (or

scores) on each subimage containing an object, and add

them to the set of features already calculated in the su-

pernova search pipeline. These two features are: R1,

which measures the roundness or eccentricity of the

candidate object, and R2, which measures the amount

of irregularity in the object contour.

Our approach inserts the following steps into the

processing pipeline for candidate supernova objects:

1. Find the outer contour of the object and store it as

a sequence of (x, y) points.

2. Calculate the lowest Fourier descriptorterms F

and

−1

on the contour point sequence.

3. Form two roundness-related features: R1 measures

the eccentricity of the object (0 is a circle, 1.0 is

a line, and intermediate values are ellipses); R2

measures the amount of irregularity in the object

contour

R1 =

F



F

−1



R2 =

(

|k|>1

F



(

k=0

F



The features R1andR2 are added to the list of thresh-

olds or cuts applied to image objects, so that objects

with too high R1 or too high R2 are rejected as super-

nova candidates, and are not sent for human scanning.

Algorithm Results. For testing, the fast contour de-

scriptor algorithm was implemented and incorporated

into the existing supernova search pipeline software.

The new scores R1andR2 were added to the exist-

ing image feature set, without yet setting thresholds, but

with diagnostic output to permit analysis of the distri-

bution of scores. First, we examined the scores within

the class of good candidates, using a validation set of

90 supernovae. For the ﬁrst roundness feature, all of the

supernovae in the validation set yielded R1 ≤0.08 (and

frequently much closer to zero). For the second feature,

nearly all (89 of 90) gave R2 < 0.1.

A second evaluation was performed on a much

larger data set representing both classes (good and bad

Table 93.1 Graph and table of image rejection rate versus R1

threshold

0.6 0.70 0.1 0.2 0.3 0.4

Fraction of images

rejected (%)R1

< 0.1

< 0.15

< 0.2

< 0.25

< 0.3

< 0.5

0.5

Fraction of scanning eliminated

R1 threshold

0.4

0.3

0.2

0.1

Part I 93.5

1654 Part I Home, Ofﬁce, and Enterprise Automation

candidates), to determine appropriate threshold values

for R1andR2. Thegoal was toreduce the scanningload

(remove the bad candidates) as far as possible without

a) b) c)

Fig. 93.7a–c Supernova found in November 2006 by the Nearby Supernova Factory: SNF20061117-000. (a) Reference

image of galaxy,

(b) new image of galaxy plus bright spot, (c) subtraction revealing new supernova

a) b) c)

Fig. 93.8a–c Example of a bad subtraction. (a) Reference image, (b) new image, (c) subtraction (the images were

misaligned, leaving the subtraction with a meniscus-shaped object). This object is screened out by R1

a) b) c)

Fig. 93.9a–c Example of a bad subtraction. (a) Reference image of empty space, (b) new image with edge of bright

object present,

sacriﬁcing any good candidates (possible supernovae)

at all. The algorithm was run on a test set of approxi-

mately 35000 subtracted images, of which 1094 would

Part I 93.5