s2fieldsofstudy:
Computer Science
Environmental Science

text:
The Matsu Wheel: a reanalysis framework for Earth satellite imagery in data commons

Project Matsu is a collaboration between the Open Commons Consortium and NASA focused on developing open source technology for the cloud-based processing of Earth satellite imagery and for detecting fires and floods to help support natural disaster detection and relief. We describe a framework for efficient analysis and reanalysis of large amounts of data called the Matsu “Wheel” and the analytics used to process hyperspectral data produced daily by NASA’s Earth Observing-1 (EO-1) satellite. The wheel is designed to be able to support scanning queries using cloud computing applications, such as Hadoop and Accumulo. A scanning query processes all, or most, of the data in a database or data repository. In contrast, standard queries typically process a relatively small percentage of the data. The wheel is a framework in which multiple scanning queries are grouped together and processed in turn, over chunks of data from the database or repository. Over time, the framework brings all data to each group of scanning queries. With this approach, contention and the overall time to process all scanning queries can be reduced. We describe our Wheel analytics, including an anomaly detector for rare spectral signatures or anomalies in hyperspectral data and a land cover classifier that can be used for water and flood detection. The resultant products of the analytics are made accessible through an API for further distribution. The Matsu Wheel allows many shared data services to be performed together to efficiently use resources for processing hyperspectral satellite image data and other, e.g., large environmental datasets that may be analyzed for many purposes.

Introduction
Although large amounts of satellite imagery data are available for download from NASA, as well as from other sources, by and large, these large volumes of data are not easy to process and analyze for many researchers. Scientists are finding that the bottleneck to discovery is no longer a lack of data but an inability to manage and analyze large datasets. Imaging from Earth satellites in particular can quickly produce large volumes of data, necessitating a computing environment capable of scientific analysis of many images.
Project Matsu is a collaborative effort between the Open Science Data Cloud (OSDC), managed by the Open Commons Consortium (OCC), and NASA, working to alleviate these difficulties by developing open source tools for processing and analyzing Earth satellite imagery in cloud-based "data commons," or cyber-infrastructure that colocate data with storage and commonly used data access and analysis tools [2]. The goals of Project Matsu are to: (1) Develop an open source cloud-based infrastructure to process Earth satellite image data with API-accessible services, (2) Develop parallel algorithms and analytics using Hadoop's MapReduce and related frameworks for processing large amounts of satellite image data to detect floods and other events for disaster assistance and relief, and (3) Operate persistent cloud-based services that process satellite image data and other data sources each day and make the resulting reports available to the research community and other interested parties.
The Matsu "Wheel" is a framework we have developed for simplifying Earth satellite image analysis on large volumes of data by providing an efficient system that performs all the common data services and then passes the prepared chunks of data in a common format to the analytics, which process each new chunk of data in turn.
This paper is organized as follows: In the subsections below, we provide motivation for an analytic wheel framework and introduce the hyperspectral satellite data to which we apply this framework. In Sect. 2 we put this analytic wheel approach and the algorithms applied in context of related work. In Section 3, we describe the workflow of our analytic wheel implementation in our data commons, providing details on the computational environment in which it runs and the preprocessing applied to the data in 3.1 and 3.2. The architecture of the wheel, the flow of data through the wheel analytics, and design considerations are discussed in Sects. 3.3 and 3.4. In Sect. 4, we describe the structure of an individual analytic in the wheel and detail each of the algorithms the Matsu Wheel runs, including several anomaly detection algorithms and a classification algorithm. We discuss efficiencies in our application and directions this work can be extended in Sect. 5 and close with a summary in Sect. 6.

Motivation for an analytic wheel
A common class of problems require applying an analytic computation over an entire dataset. Sometimes these are called scanning queries since they involve a scan of the entire dataset. For example, analyzing each image in a large collection of images is an example of a scanning query. In contrast, standard queries typically process a relatively small percentage of the data in a database or data repository.
With multiple scanning queries that are run within a time that is comparable to the length of time required for a single scan, it can be much more efficient to scan the entire dataset once and apply each analytic, in turn, versus scanning the entire dataset for each scanning query as the query arrives. This is the case unless the data management infrastructure has specific technology for recognizing and processing scanning queries. In this paper, we introduce a software application called the Matsu Wheel that is designed to support multiple scanning queries over satellite imagery data.
The motivation for using an analytic wheel is that by performing all of the data processing services together on chunks of data, a data commons can more efficiently use resources, including available network bandwidth, access to secondary storage, and available computing resources. The wheel consolidates operations that are shared by multiple analytic pipelines, such as data loading, and applies them together before scanning queries process the data. This is especially important with reanalysis of data in a repository, in which the entire dataset is processed using an updated algorithm, a recalibration of the data, a new normalization of the data, a new workflow, etc. The motivation behind the analytic wheel is to streamline and share these services so that they are only performed once on each chunk of data in a scanning query, regardless of the number or type of scanning analytics run over the data, so that new scanning analytics can be added at minimal cost.
The wheel analytic approach differs from common workflows around data accessed from repositories. Traditionally, individual researchers may use stand-alone workstations to download datasets and run an analytic in isolation. This may be possible for smaller datasets but can be difficult to impossible for large datasets exceeding the resources of individual workstations.
For data stored in a relational database, a potentially longrunning query is needed to fetch the dataset for each analytic, which is especially inefficient for scanning queries which access all or large subsets of datasets. Multiple scanning queries in this case adds the additional complexity inherent in concurrent retrievals of the same data.
In a compute-on-demand cloud, virtual machines may be launched to run specific analytics over data that are mounted to the instance. In this case, again, contention issues may arise as multiple virtual machines concurrently access the same data mount. Additionally, for data that have preprocessing requirements that may be the same for several commonly applied analytics, it is inefficient for each analytic to separately apply preprocessing.
While each analysis framework has its distinct advantages, the Matsu Wheel system provides a significantly more efficient use of resources over alternative methods (1) for datasets that are large and may be continuously growing or updated, (2) for datasets that may require preprocessing (e.g., commonly applied corrections or normalizations), and (3) for datasets where multiple analytics are applied to the same data and the number of scanning queries grows. These characteristics are generally the case for Earth satellite imagery data.

Application to Earth satellite data
In Earth satellite and hyperspectral image data, especially, the Matsu Wheel system can increase the efficiency of a data analytics system. Earth satellite data can be large and have high-volume throughput as new data are continuously acquired for active satellite missions. Earth satellite data also may require heavy preprocessing common to many types of applications, such as atmospheric corrections or geographic coordinate corrections. In these types of use cases, using a system like the Matsu Wheel system can consolidate operations by grouping them for multiple analytics.
The Matsu Wheel is currently used to process the data produced each day by NASA's Earth Observing-1 (EO-1) satellite and makes a variety of data products available to the public. In addition to the Atmospheric Corrector, the EO-1 satellite has two primary scientific instruments for land observations, the Advanced Land Imager (ALI) and a hyperspectral imager called Hyperion [3,4]. EO-1 was launched in November 2000 as part of NASA's New Millennium Program (NMP) initiative for advancing new technologies in space and is currently in an extended mission.
The ALI instrument acquires data in 9 different bands from 0.48-2.35 µm with 30-meter resolution plus a panchromatic band with higher 10-meter spatial resolution. The standard scene size projected on the Earth surface equates to 37 km × 42 km (width × length). The Hyperion instrument has similar spatial resolution but higher spectral resolution, observing in 242 band channels from 0.357-2.576 µm with 10-nm bandwidth. Hyperion scenes have a smaller standard footprint width of 7.7 km.
The Matsu Wheel runs analytics over Level 1G data, which are data that have several common corrections applied and are also transformed to Geographic Tagged Image File Format (GeoTiff) format. These data are radiometrically corrected, resampled for geometric correction, and registered to a geographic map projection. The GeoTiff data and metadata for all bands in a single Hyperion scene can amount to 1.5-2.5 GB of data for only the Level 1G data. The total size of ALI and Hyperion Level 1G GeoTiff data over one year (2015) is about 11 terabytes, and a similar amount of data is produced by each analytic that creates GeoTiff data products. A cloud environment for shared storage and computing capabilities is ideal for scientific analysis of many scenes, which can quickly grow to a large amount of data.

Related work
The Matsu Wheel approach differs from other common data management or data processing systems. Real-time distributed data processing frameworks (for example, Storm, S4, or Akka) are designed to process data in real time as it flows through a distributed system (see also, e.g., [5][6][7]). In contrast, the wheel is designed for the reanalysis of an entire static dataset that is stored in distributed storage system (for example, the Hadoop Distributed File System) or distributed database (for example, HBase or Accumulo).
A number of data flow systems exist for simplifying largescale data processing, and particularly over Hadoop storage systems. For example, the Apache Pig project provides a system for applying SQL-like queries to build complex data flows over Hadoop and is designed for performing long series of data operations [8]. In contrast, the wheel approach is for independent operations that have a need to be applied to all data and whose results should be updated with the addition of new data. Oozie also provides a way to bundle Hadoop jobs into work flows [9]. In contrast, the wheel approach is designed for preprocessing of common heavy tasks and allowing individual analytics to be written without having to be concerned with interacting with other tasks. Additionally, Spark is a tool that adds in-memory data processing to Hadoop enabling multiple applications to share datasets [10], whereas the wheel approach is to remove common operations from analytics by preprocessing data and the pass data to the analytics in tandem.
It is important to note that any distributed scale-out data processing system based upon virtual machines has certain performance issues due to the shared workload across multiple virtual machines associated with a single physical node. In particular, these types of applications may have significant variability in performance for real scientific workloads [11]. This is true, when multiple scanning queries hit a distributed file system, a NoSQL database, or a wheel-based system on top of one these infrastructures. When a NoSQL database is used for multiple scanning queries with a framework like the wheel, the NoSQL database can quickly become overloaded.
For the context of the individual Matsu Wheel analytics presented here, Griffin et. al. [12] provide an overview of example analyses of data from the EO-1 satellite and of hyperspectral imaging data in general. Analysis of hyperspectral data falls primarily into one of two categories. The first class is terrain characterization, which can be approached more generally as a classification problem applied to the spectrum at each pixel. Related work in remote sensing has been done to develop algorithms for cloud detection and land coverage classification, with applications to agriculture, forestry, mineral mapping, vegetation studies, and biodiversity (see, e.g., [13][14][15]). The second class is source/object detection, which is mainly applied to detect rare objects against a heterogeneous background and can subsequently be framed as an anomaly detection problem (see, e.g., [16] and references therein). Given the variety of analyses that can be applied to the same hyperspectral imaging data, these use cases are particularly well suited to an analytic wheel framework, and we present both anomaly detection and land coverage classification types of analyses in Sect. 4.

Computational environment
The computing infrastructure for the daily processing of EO-1 data for Project Matsu involves both an OpenStack-based computing platform for preprocessing and a Hadoop-based computing platform for the Wheel analytic scanning queries, both of which are managed by the OCC (www.occ-data.org) in conjunction with the University of Chicago. The Open-Stack platform (the Open Science Data Cloud [17]) currently contains 60 nodes, 1208 compute cores, 4832 GB of compute RAM, and 1096 TB of raw storage. The Hadoop [18] platform currently contains 28 nodes, 896 compute cores, 261 TB of storage, and 3584 GB of compute RAM.

Preprocessing of data on the OSDC
The OpenStack-based Open Science Data Cloud provides a number of cloud-based services for Project Matsu. As new EO-1 observations are received from NASA each day, the data are stored on a distributed, fault-tolerant file system (GlusterFS and Ceph) and preprocessed prior to the application of the wheel-based analytics. The images are converted into SequenceFile format, a file format more suited for MapReduce, and uploaded into the Hadoop Distributed File System (HDFS) [19]. Metadata and compute summary statistics are extracted for each scene and are stored in Accumulo, a distributed NoSQL database [20]. The metadata are used to display the geospatial location of scenes via a web map service so that users can easily visualize which areas of the Earth are observed in the data processed by the Matsu Wheel.
The Matsu data flow for processing EO-1 images and producing data and analytic products is described below:

Analytic "wheel" architecture
The analytic wheel is so named because multiple analytics are applied to all of the data one chunk of data at a time, roughly analogous to the way a Ferris Wheel works. By the time a Ferris Wheel makes a complete revolution, all of the chairs have been processed exactly one time. With big data, retrieving or processing data multiple times is an inefficient use of resources and should be avoided. The Matsu Wheel system is unique in that, essentially, the data are flowing through the framework while the analytic queries sit in place and wait for new data to scan. This type of scanning framework, in which the data only need to be read once for multiple analytics, is increasingly important as scientific datasets become larger, new data are acquired at a faster rate, and data are used and reused for many purposes.

Key components of the data commons environment
In Sect. 1.1, we discussed how an analytic wheel may be more efficient for scanning query type analytics that process all or most of the data in a dataset. Specifically, an analytic wheel framework is well suited for the processing and analysis or reanalysis of data in a data commons, which is cyber-infrastructure that colocates data archives with storage and computing resources and commonly used tools for analyzing and sharing data to create a resource for the research community [2].
The architecture of a data commons requires consideration of balancing the needs of both data archiving for persistent storage and also computation on an active system where data may be physically moved, updated, or distributed across different resources. To manage references and queries to pieces of data to be processed by the analytic wheel, we assign digital identifiers to the location (url) of each scene (image file) to be analyzed. Data are then accessed via digital identifiers through a simple tracking and index server with a REST-like API interface.
These identifiers are returned through the available images map at matsu.opensciencedatacloud.org that allows for simple search for data of interest by date of observation, location, and overall radiance (brightness) level. Each scanning analytic in the wheel refers to batches of scenes accessed by their digital identifiers and subsequently uses the identifiers as the keys for entries in each analytic's summary results database table, as described in the next section.

Running the Matsu Wheel analytics
The EO-1 Satellite collects data daily, and lower level processing is performed over the raw data in the commons, as described in Sect. 3.2, to generate the Level 1 data used by the analytic wheel.
To detect and stage new Level 1 data to be processed by the wheel, we currently use Apache Storm, a distributed and fault-tolerant computation framework for stream processing. Storm topologies continuously watch for newly available Level 1 GeoTiff files, convert these data to SequenceFile format and load into HDFS, index the data by applying digital identifier to scenes, and update an Accumulo database tracking all images available in the commons for processing.
When a new batch of data becomes available in HDFS as part of the preprocessing described above, the MapReduce scanning analytics in the wheel kick off. In our implementation, the Matsu Wheel is run daily after receiving the previous day's observations. To run the wheel over a daily batch, the digital identifiers for that day's observations are passed to the start of the wheel, and each analytic in the wheel in turn processes the batch. Intermediate output is written to HDFS, and each analytic's results are stored in an Accumulo table as JSON. Secondary analysis that may process the results of other analytics can be done "off the wheel" by using the Accumulo-stored JSON as input.
As many analytics can be included in the wheel as can run in the allowed time. If new data are obtained each day, then the limit is 24 h to avoid back-ups in processing. For other use cases, there may be a different time window in which the results are needed. This can be seconds, minutes, or hours. Our MapReduce analytic environment is not designed to yield immediate results, but the analytics can be run on individual images at a per minute speed. Analytics with results that need to be made available as soon as possible can be configured to run first in the wheel. Similarly, downstream analytics can use the results of other analytics by appropriate placement running in the wheel. We show a diagram of the flow of EO-1 satellite data from acquisition and ingest into HDFS through the analytic wheel framework in Fig. 1.
The wheel architecture is an efficient framework not restricted only to image processing or to daily batch processing, but is applicable to any workflow where an assortment of analytics is applied to data that require heavy preprocessing, have high-volume throughput, or may be regularly reprocessed or reanalyzed.

Design considerations of the "wheel"
The analytic wheel is designed so that different analytics are batched together, and each geospatial region is accessed once by the wheel and the batch of analytics is applied. In the current design, virtual machines are used for the processing of each geospatial region. If there is a desire to complete a turn of the wheel in a fixed period of time (for example once a day), then as the complexity of the analytics increases, the data can be chunked at a finer resolution and additional virtual machines can be used to process the data. As a simple example, change detection can be implemented in this way by simply using a virtual machine to process all the data for a given spatial region over a period of time. Once the basic satellite images are processed, finer and finer spatial resolutions can be used to increase the scale of parallelism to process all of the data in a fixed period of time for all of the analytics being applied as part of the change detection algorithm. If necessary, the set of analytics being applied to a given spatial region being fetched by the wheel can be split into two or more sub-batches, with each sub-batch processed by a separate virtual machine in parallel. This type of application was one of the motivations for the wheel architecture.
In general when accessing data from databases, it is usually significantly faster to access the data using an indexed scan. On the other hand, when it is required to evaluate each record in a database (a "full table scan"), then using the optimizations provided by a full table scan versus an indexed scan is significantly faster [21]. Since a disk can only access one contiguous sequence of blocks at a time, as the number of concurrent full table scans increases, it becomes more and more advantageous to batch the computations together and apply them to the data once it is loaded into memory versus separately fetching the blocks of data into memory for each analytic separately. The Matsu Wheel essentially uses the same optimizations but applies them currently to each virtual machine accessing distinct geospatial regions.

Analytics
In this section, we describe the Matsu Wheel analytics currently in place. We are running five scanning queries on daily images from NASA's EO-1 satellite with the Matsu Wheel, including several spectral anomaly detection algorithms and a land cover classification analytic.

Analytic requirements
Generally, an analytic wheel framework requires that each scanning query analytic take as input a batch of data. Existing queries then plug in easily and may need only small modifications before being included in the wheel. Queries do not Fig. 1 A diagram of the flow of EO-1 ALI and Hyperion data from data acquisition and ingest through the Matsu Wheel framework. Orange denotes the processes performed on the OSDC Hadoop cloud. With the wheel architecture, the data need to be read in only once regardless of the number of analytics applied to the data. The Matsu Wheel system is unique in that, essentially, the data are flowing through the framework while the analytic queries sit in place and scan for new data. Additional analytics plug in easily, with the requirement that an analytic takes as input a batch of data to be processed. An analytic query may be written such that it can be run on its own in the wheel or written to take as input the output of an upstream analytic. The report generators are an example of the latter case, generating summary information from upstream analytics need to be ordered in the wheel unless the query references results from a query that must be run earlier or unless the query is slotted early in the wheel for time considerations.
Our implementation of the analytic wheel for Project Matsu reads and processes data with Hadoop and stored results in JSON format written to Accumulo tables. For additional analytics to be included in the Matsu Wheel, a query must take as input a list of sequential files in .seqpng format stored in HDFS. The query then executes the analytic(s) and writes output results (e.g., cluster size, cluster location in latitude and longitude, anomaly score) in JSON format to an Accumulo table using the assigned identifier for the analyzed scene as the database entry key.

Contours and Clusters
The Contours and Clusters analytic produces contours of geospatial regions, showing clusters of pixels with rare spectral signatures. The contours are false-color outlines of regions, and the darker the color, the higher the density of pixels with the specific signature.
The input data consist of Level 1G EO-1 scenes from the Hyperion instrument, essentially a set of radiances for all spectral bands for each pixel in an image. The radiance in each band is then divided by its underlying solar irradiance to convert to units of reflectivity or at-sensor reflectance. This is done by scaling each band individually by the irradiance and then applying a geometric correction for the solar elevation and Earth-Sun distance, as shown in Eq. 1, where ρ i is the at-sensor reflectance at channel i, μ 0 = cos (solar zenith angle), F 0,i is the incident solar flux at channel i, d Earth−Sun is the Earth-Sun distance, and L i is the irradiance recorded at channel i [12]. This correction accounts for differences in the data due to time of day or year.
We then apply a principal component analysis (PCA) to the set of reflectivities and extract the top N (we choose N = 5) PCA components for further analysis. Pixels are clustered in the transformed 5-dimensional spectral space using a k-means clustering algorithm. For an individual image, k = 50 spectral clusters are formed and then ranked from most to least extreme using a normalized Mahalanobis distance metric to identify the most anomalous spectra. For each spectral cluster, adjacent pixels in an image are grouped together into contiguous objects based on the purity or fraction of pixels that belong to that cluster and are then ranked again based on their distance from the spectral cluster center.
For each cluster, two scores are produced, indicating (1) how anomalous the spectral signature is in comparison with the rest of the image and (2) how close the pixels within the contour are to the cluster signature. The top ten most anomalous clusters across all scenes in an analytic wheel batch are singled out for manual review and highlighted in a daily overview summary report.
The analytic returns the clusters as contours of geographic regions of spectral "anomalies" which can then be viewed as polygonal overlays on a map. The Matsu Wheel produces image reports for each image, which contain an interactive map with options for an OpenStreetMap, Google Physical, or Google Satellite base layer and an RGB image created from the hyperspectral data and identified polygon contours as options for overlays. The results can be easily accessed via daily image reports through a web browser.
This wheel analytic has successfully identified and rank ordered regions of interesting activity on the Earth's surface, including several volcanic events. We show an example analytic image report for one significant event detection in Fig. 2. This detection is from an Earth Observing-1 visit from late June 2016 of the Kilauea volcano in Hawaii, a few days prior to a flow eruption from a vent from the Pu'u 'O'o crater. The top left table shows summary information about the observation. The top right shows the interactive map overlay with a purple contour in the center, which encircles a large spectral anomaly. The cluster and contour scores for this object are shown in the table in the bottom left, and the spectrum of the area enclosed by the contour is shown in the bottom right.

Rare Pixel Finder
The Rare Pixel Finder (RPF) is another anomaly detector. This analytic is designed to find small clusters of unusual pixels in a hyperspectral image. The algorithm, as we implement it, is applied directly to the EO-1 data in radiances, but the data can also be transformed to reflectances or other metrics or can have logs applied.
Using the subset of k hyperspectral bands that are determined to be most informative, it computes k-dimensional Mahalanobis distances and finds the pixels most distant.
From this subset, pixels that are both spectrally similar and geographically proximate are retained. Spectrally similar pixels that can be further grouped into small compact sets are reported as potential outlying clusters. Details of the different steps of the algorithm are given below.
In the preprocessing step, we remove areas of the image that are obvious anomalies not related to the image (e.g., zero radiances on the edges of images), as well as spectral bands that correspond to water absorption or other phenomena that result in near-zero observed radiances. Any transformations are applied to the data at this point, such as transforming radiance to reflectance or logs.
Once the data are preprocessed, the Mahalanobis distance (D i ) is calculated for each pixel. Then, only the subset S 1 of pixels that satisfy D i > k 1 are selected, where k 1 is chosen such that S 1 only contains 0.1-0.5% of pixels. In practice, k 1 was based on the upper 6σ of the distribution of sample distances, assuming a log-normal distribution for the distances.
For the subset of S 1 pixels chosen in the previous step, we next compute a similarity matrix T with elements T i j measuring the spectral similarity between each pair of pixels. The similarity metric is based on the dot product between each pair of points and measures the multi-dimensional angle between points. The matrix is only formed for the subset S 1 and contains a few hundred rows. The pixels are then further subset. Pixel i is selected for set S 2 if T i j > k 2 for j = i. The parameter k 2 is chosen to be very close to 1; in this way, we select objects that are both spectrally extreme but still have similar spectral profiles to one another.
In order to cluster the pixels geographically, we assume they lie on a rectangular grid. An L 1 norm metric is applied to the subset S 2 in order to further whittle down the candidate set to pixels that are spectrally extreme, spectrally similar, and geographically proximate. The metric is set so that traversing from one pixel to an immediately adjacent one would give a distance of 1, as if only vertical and horizontal movements were allowed. Pixel i is selected for set S 3 if M i j < k 3 for j = i and for some small value of k 3 . We used k 3 = 3, so that pixels either needed to be touching on a face or diagonally adjacent.
In the final step, a simple heuristic designed to find the connected components of an undirected graph is applied. We further restrict to a set S 4 that are geographically proximate to at least k 4 other pixels (including itself). We used k 4 = 5, with the goal of finding compact clusters of between 5 and 20 pixels in size. The clumping heuristic then returns the pixels that were mapped into a cluster, the corresponding cluster ID's, and the associated distances for the elements of the cluster.
The flagged pixels are reported as "objects." These groups of objects are further filtered in order to make sure that they actually represent regions of interest. The following criteria must be satisfied in order to qualify: available as overlays on an OpenStreetMap, Google Physical, or Google Satellite base layer. In this analytic, interesting regions are given a cluster score from 0 to 1000 based on how anomalous they are compared to the average detection and appear as colored contours over the image. The bottom right shows the spectrum for the anomalous region 1. Spectral extremeness The mean Mahalanobis distance must be greater than or equal to some parameter p 1 . This selects clusters that are sufficiently extreme in spectral space.

Spectral closeness
The signal-to-noise ratio must be greater than or equal to some parameter p 2 . This selects clusters that have similar values of Mahalanobis distance. 3. Cluster size All clusters must be between a minimum value parameter p 3 and a maximum parameter p 4 pixels in size (the goal of this classifier is to find small clusters). 4. Cluster dimension All clusters must have at least some parameter p 5 rows and columns (but are not restricted to be rectangles).
Parameters p 1p 5 are all tuning parameters that can be set in the algorithm to achieve the desired results. Examples of the parameters used can be shown in Table 1.

Gaussian Mixture Model and K-Nearest Neighbors (GMM-KNN) algorithm
We apply the GMM-KNN analytic to data from the ALI instrument. The GMM-KNN algorithm is another analytic designed to find small clusters of unusual pixels in a multi-spectral image. In short, using fewer spectral bands, it fits the most common spectral shapes to a Gaussian Mixture Model (smoothly varying, but makes strong assumptions about tails of the distribution) and also a K-Nearest Neighbor model (more detailed description of tails, but granular), then searches for pixels that are far from common. Once a set of candidate pixels have been found, they are expanded and merged into "clumps" using a flood-fill algorithm. The clumps are then characterized by deriving a suite of features via KNN, edge detection, and the distribution of pixel spectra in the clump. The clumps with the most unusual features are scored and rank ordered. The first step in the GMM-KNN analytic is preprocessing specific to this analytic. The preprocessing steps are motivated by two assumptions about the input data: (1) Absorption or selective reflection of light is multiplicative and (2) the predominant source of variation in most images is intensity, not color. However, variations in intensity are transient, depending on changes in observation orientation, while variations in color are more indicative of real objects on the ground. To address this, we take the logarithm of the radiance value of each band and project the result onto a color-only basis to remove variations in intensity and highlight instead ground objects. The next step is to fit a Gaussian Mixture Model of k = 20 Gaussian components to the spectra of all pixels. This is sufficiently large to cover the major structures in a typical image. A Gaussian Mixture Model generalizes clustering by allowing components to be asymmetrically shaped and allowing cluster inclusion to be nonexclusive. Since the Gaussian Mixture Model describes the major features of the distribution, pixels with spectra that are far from the Gaussian centroids are outliers. We use the log-likelihood of the GMM distribution as a "GMM outlier score." The GMM score is derived purely from spectral shape, so we use a flood-fill to expand GMM outliers to enclose any surrounding region that is also anomalous and merge GMM outliers if they are in the same clump. We then characterize the merged multi-pixel multispectral clumps using a variant of K-Nearest Neighbors, in which we specify a radius in log-spectral space and count the number of spectra within that radius. In particular, we used a Gaussian measure with standard deviation r for r = 0.2 and r = 0.5. The count is not an integer because of the Gaussian measure, and it is normalized to the total number of non-mask pixels in the image to derive a "KNN outlier score." More anomalous spectra have lower scores (less density).
The spectral clumps detected in a given analytic wheel batch of images are rank ordered by their GMM and KNN outlier scores and presented in a summary report with spectral details available for individual outliers. We show an example summary report produced by the Matsu Wheel for the GMM-KNN analytic in Fig. 3.

Spectral Blobs
The Spectral Blobs analytic is used to identify anomalous "blobs" of regions that are similar within the region in spectral space but far from other blobs. Here, a "blob" is a set of pixels that are spectrally similar to one another and need not be spatially contiguous, unlike the Contours and Clusters analytics, which detects both spectral similarity and spatial contiguity.
The Spectral Blobs algorithm uses a "windowing" technique to create a boundary mask from the standard deviation of neighboring pixels. A catalog of blobs that contain varying numbers of pixels is created. Blobs are scored by comparing similarity to other blobs within the same image.
First, the analytic creates a boundary mask using a rolling window of 3-by-3 pixel windows. It uses an undirected graph search algorithm to separately label each group of spatially connected components of the mask. It then applies statistical significance tests (t-test, Chi-squared) to the spectral features of the blobs to test whether regions can be merged together, according to a tunable threshold. Spectrally similar regions are merged together.
The anomalous regions are the small spatial blobs that are not a member of any larger spatial cluster. A spectral dissimilarity score for each blob is generated by comparison to other blobs. A high score indicates increasing dissimilarity from other blobs in an image.

Supervised Spectral Classifier
The Supervised Spectral Classifier is a land coverage classification algorithm for the Matsu Wheel. We are particularly interested in developing these analytics for the detection of water and constructing flood maps to complement the onboard EO-1 flood detection system [22]. This analytic is applied to both ALI and Hyperion Level 1G data and classifies each pixel in an image as a member of a given class in a provided training set. We currently implement this analytic with a simple land coverage classification training set with four possible classes: clouds, water, desert / dry land, and vegetation.
The classifier takes as input the reflectance values of each pixel as the characterizing vector and applies a support vector machine (SVM) algorithm. In this implementation of the classifier, we bin Hyperion data to resemble ALI spectra for ease of use and computation speed in training the classifier. We construct a vector space from all ALI bands and two additional ALI band ratios, the ratios between ALI bands 3:7 and 4:8.
We make use of the SVM method provided by the Python scikit-learn machine learning package [23], which provides multi-class classification support via a "one-against-one" approach in which multiple classifiers are constructed, each Fig. 3 An example GMM-KNN wheel analytic report summary from the end of September, 2016. This analytic has processed a batch of 10 new scenes from the EO-1 ALI instrument, identified and scored anomalous spectral objects as described in the text, and presented a rank ordering of the most interesting features from this wheel batch as a summary report training data from two classes [24]. The result of this analytic is a GeoTiff showing the classification at each pixel.

Building a training dataset
We constructed a training dataset of classified spectra from sections of EO-1 Hyperion images over areas with known land coverage and cloud coverage and confirmed our selections by visual inspection of three-color (RGB) images created of the training images. We used a combination of Hyperion bands B16 (508.22 nm), B23 (579.45 nm), and B29 (640.5 nm) to construct the RGB images. For each image contributing to the training dataset, we only included spectra for collections of pixels that were visually confirmed as exclusively desert, water, clouds, or vegetation.
The training dataset consists of approximately 6,000 to 9,000 objects for each class. We include spectra for a variety of different regions on the Earth observed during different times of the year and a range of solar elevation angles. Because absolute values are necessary to directly compare the training data to all test images, we convert the raw irradiance values from the Level 1G data to at-sensor reflectance using Eq. 1. Table 2 lists general properties of the Hyperion scenes used in constructing the training set, where the class column indicates the class(es) (C = cloud, W = water, V = vegetation, and D = desert) to which that scene contributed.
In Fig. 4, we show a plot of the average reflectance spectra for each of the four classes in our training set. These spectra are in good agreement with the spectral signatures of cloud, vegetation, and desert sand presented in other examples of EO-1 Hyperion data analysis, specifically Figures 3 and 4 in Griffin et. al. [12,25].

Classifier results
We show a visual comparison of cloud coverage determined by our classifier with cloud coverage amounts stated by EarthExplorer for three Hyperion scenes of the big island of Hawaii with varying amounts of clouds and an additional scene of a section of the coast of Valencia. In Fig. 5, we show the resulting image report of the classifier analytic. This report shows a classification of an ALI observation of the Danube River in the Szekszard region of Hungary, with the river water in the classified overlay colored as blue, veg- etation colored green, dry land colored brown, and cloud colored white. This classifier has some difficulty in distinguishing between clouds and ground water, as can be seen with the white pixels following the Danube River path.
To further confirm that the classifier analytic is generating reasonable results, we compare the fractional amount of land coverage types calculated by the classifier with known fractional amounts from other sources. We compare our results for classified cloud coverage with the cloud coverage amounts stated for individual scenes available through the EarthExplorer tool from the US Geological Survey (USGS) [26]. In Fig. 6, we show a plot comparing expected cloud and water coverage to the coverages determined by our classifier for 20 random test scenes. For each scene, the expected cloud coverage is taken as the center of the range provided by the USGS EarthExplorer summary for that image. The expected water coverage is calculated from scenes of islands that are completely contained within the image. We can then calculate expected water coverage by removing the known fractional land area of the islands and the USGS reported cloud coverage. We fit a regression line to the data, which shows an overall consistent relationship between the classified results and expected estimates.

Viewing analytic results
For convenience, each analytic produces a report after each run of the wheel. These reports are built from the JSON results stored in Accumulo and are accessible to the public via a web page. The generated reports contain spectral and geospatial information about the scene analyzed as well as analytic results. An overview summary report is created for  Comparison of expected cloud and water coverages from USGS vs. coverages calculated from our classifier. Expected water points (triangles) are calculated from island scenes as described in the text. Expected cloud coverage estimates (circles) are taken from USGS EarthExplorer quoted cloud coverage for each image. The linear regression is the solid black line, and the gray shaded area is the 95% confidence interval. A 1-1 relationship is shown as a dashed black line for comparison all daily data processed by an analytic in one run of the wheel in addition to reports for individual scenes. These reports are generated and viewable immediately upon completion of the scan of new data available each day at the following address: https://matsu-analytics.opensciencedatacloud.org. Analytic products are also made programmatically accessible through a Web Map Service.

Discussion
In our application of an analytic wheel, the preprocessing and bundling of common operations provides significant efficiency for the subsequent analytics over the Earth Observing-1 data. For example, the atmospheric and other corrections applied to Level 0 Hyperion data and the conversion to Geo-Tiff file format for all bands in Hyperion can take 30 min to over an hour for a single scene on a 32-core OSDC virtual machine. With even just a dozen scenes per day and five analytics in our current system, the wheel saves significant overhead in terms of time to process.
In terms of scaling up the number of analytics, as many analytics can be pushed into the wheel as can run in a given time frame, and data generation may outpace the wheel revolution. However, this problem is not unique to the wheel framework, but in any processing pipeline that may have some finite compute capacity. If certain analytics have more stringent time constraints than others, they can be set to run in the wheel earlier than others. There is also flexibility in the types of analytics that can be placed in the wheel. In the example analytics we have provided here, all take as input a batch of EO-1 scenes, though some act on individual scenes within the batch (like the classifier analytic) and others ana-lyze the products of all scenes in a batch (for example, the rank ordering of all anomalous objects across scenes in a daily batch of EO-1 data).
In terms of analytics, the Matsu Wheel allows for additional analytics to be easily slotted in with no change to the existing framework so that we can continue to develop a variety of scanning analytics over these data. We are extending our existing Supervised Spectral Classifier to use specifically over floodplain regions to aid in flood detection for disaster relief. We are also planning to develop a similar analytic to aid in the detection of fires.
The analytics we described here are all detection algorithms, but we can also apply this framework and the results of our current analytics to implement algorithms for prediction. For example, our future work includes developing Wheel analytics for the prediction of floods. This could be done using the following approach: 1. Develop a dataset of features describing the observed topology of the Earth. 2. Use the topological data to identify "flood basins," or regions that may accumulate water around a local minimum. 3. Determine the relationship between detected water coverage in flood basins and the volume of water present. 4. Use observed water coverage on specific dates to relate the water volume in flood basins with time. 5. Use geospatial climate data to relate recent rainfall amounts with water volume, which then provides a simple model relating rainfall to expected water coverage at any pixel.
This proposed scanning analytic would provide important information particularly if implemented over satellite data with global and frequent coverage, such as data from the Global Precipitation Measurement (GPM) mission [27,28]. Our future work also involves continuing to develop the Matsu Wheel analytics and apply this framework to additional Earth satellite datasets.

Summary
We have described here the Project Matsu Wheel, which is what we believe to be the first working application of a Hadoop-based framework for creating analysis products from a daily application of scanning queries to satellite imagery data. This system is unique in that it allows for new analytics to be dropped into a daily process that scans all available data and produces new data analysis products. With an analytic wheel scanning framework, the data need to be read in only once, regardless of the number or types of analytics applied, which is particularly advantageous when large volumes of data, such as those produced by Earth satellite observations, need to be processed or reprocessed by an assortment of analytics.
We currently use the Matsu Wheel to process daily spectral data from NASA's EO-1 satellite and make the data and wheel analytic products available to the public through the Open Science Data Cloud and via analytic reports on the web.
A driving goal of Project Matsu is to develop open source technology for satellite imagery analysis and data mining analytics to provide data products in support of humanassisted disaster relief. The open nature of this project and its implementation over commodity hardware encourage the development and growth of a community of contributors to develop new scanning analytics that can be dropped into the analytic wheel for processing these and other Earth satellite data.


Skeletonization in Natural Image using Delaunay Triangulation

A R T I C L E I N F O A B S T R A C T Article history: Received: 18 May, 2017 Accepted: 15 June, 2017 Online: 11 July, 2017 In this paper a novel approach to extract 2D skeleton information (skeletonization) from natural image is proposed. The work presented here is the extension of our previous paper presented at the International Sympsosium on Multimedia 2016. In the past work, a threshold based method is utilized. Here the algorithm is further improved by using a better edge points detection and skeleton extraction. Furthermore the proposed method is compared with the Skeleton Strength Map (SSM) and shows better result visually and numerically (F-measure comparison).

Introduction
This paper is an extension of the work [1] originally presented at International Symposium on Multimedia 2016 (ISM'16). In this paper we provide a more detail and some improvement from the previous paper presented at ISM 2016.
Skeletonization is a process to extract the simplest, the most compact form of an object (skeleton) from 2D or 3D objects. Although mostly used in animation [2], skeleton information has also been used in symmetry detection [3], shape analysis [4], etc. Based on the input to the skeletonization, we can classify it into two types; 2D skeletonization and 3D skeletonization. In this paper, we are dealing with the first type, i.e. the 2D skeletonization or skeletonization from an image.
Corneat et al. [5] classify skeletonization into 4 classes, i.e. thinning and boundary propagation, distance field-based, geometric and general-field functions. While most of these approach works well, it only applies to the binary image.
In order to get the binary image, of course one can use a foreground-background separation, but unfortunately foreground-background separation is still an open problem in image processing field. Another way to see the problem is that conventional approaches need a closed boundary information to extract the skeleton information. It holds when the object and the background information has a high contrast, but does not hold for object with a low contrast value with the background (such as similar color and texture).
When the input image is not a binary image, the skeletonization is often referred as grey-scale skeletonization. Grey-scale skeletonization can be regarded as a relaxation of the conventional skeletonization. Instead of a binary image, the input to greyscale skeletonization is usually the brightness image (grey-scale image) or the color images. Skeleton is related closely to the symmetry information, therefore several authors are utilizing the symmetricity. You and Tang [6] proposed a method to detect the skeleton of characters using the wavelet. Widynski et al. [3] proposed a method based on particle filter approach. Levinshtein et al. [7] proposed a method based on superpixel segmentation and learned affinity function. In the last two methods, a supervised learning step is incorporated.
Du et al. [8] proposed a method based on a structure adaptive anisotropic filtering. The method is extracting the skeleton by updating the scale orientation and kernel of every pixel. The process is done iteratively including the update step therefore requiring a high computational cost. Another method is proposed by Li et al. [9] using a distance transform method [10]. By first extracting the edge information using Canny edge extraction algorithm and then calculating the inverted of the distance transform, this method can extract the skeleton of the object and its surrounding. To further increase the performance, a learned context model is utilized. Since this method relies on the distance transform, connected edge pixel is needed to V. Sintunata et al. / Advances in Science, Technology and Engineering Systems Journal Vol. 2, No. 3, 1013-1018(2017 some extend. It is important to note again here that while the connected edge pixel can be retrieved or extracted in an image where the object has high contrast, the opposite is not true. This condition results in a sparse or unconnected edge pixels in the image. Most of the papers mentioned above has high computational cost or need a learning step in one of their method. In this paper we tried to solve the grey-scale skeletonization without a learning step. Furthermore the proposal can be used to relax the unconnected (sparse) boundary pixel condition. The rest of the paper is as follows: in section 2 the more detail explanation of the proposed method is presented. In section 3 some examples of the result and discussion will be presented. Finally section 4 will conclude this paper.

Proposed Method
The general framework for the proposed method can be seen in Figure 1. There are three major steps in the method: boundary points extraction, skeleton extraction and pruning step.

Boundary Points Extraction
The method starts by making a grid of the input image and finding the edge points inside each grid. This edge points are selected by choosing the highest intensity among the pixels inside the grid. The question is then how are we suppose to find these edge points. It is very common to get the edge information from the gradient of the image. The higher the intensity of the gradient image is, the higher the probability it is considered to be the boundary object. Instead of using Canny edge detection which relies on the brightness image only, we calculate the edge (or gradient) information from both the brightness image and the color images.
First, the input image is converted into CIE color space and then split to each corresponding channels (i.e. brightness or luminance (L*) and two color channels (u* and v*)). Let e c (i, j) denotes the value of the gradient image at channel c (c ∈ L*, u*, v*) at (i,j) position. The value of e c (i, j) is calculated from the standard deviation of a pixel at (i,j) with its surrounding (n × n patch) at its respective channels (1). The benefit of calculating the standard deviation is that textured object will have a higher deviation which results in an easier way to locate the boundary pixel between two different objects. Finally we can combine them by averaging the values of these edge images (2) at each pixel.
Since we are only interested on the boundary of the object, we can further reduce the texture effect by redoing the previous step onto the combined image (generated from 2). This will reduce the texture inside the object, but will also make the boundary of the object to lies inside a "valley". This can be avoided by applying the resulting image with the Laplacian operator. Let I L be the image after applying the Laplacian operator. I L will then be convoluted with the standard deviation image of the combined image, to construct the final edge image. Figure 2 shows the example of this approach. The edge points are then extracted from this edge image. Since we are selecting the edge points from the grid, there will be points which lie in the non-edge position. Filtering these points (candidate points) is done by using a method similar to a method proposed in [11,12]. The idea is very intuitive: at each pixel in the image, generate a patch and divide it into two halves along an orientation. At each section calculate its histogram (intensity, colors, etc.) and compare both of the sections. The higher the distance between the histograms (χ 2 distance) the more likely the examined pixel to be an edge pixels.
Notice that we need to have an orientation at each candidate point. To approximate the orientation at each candidate point, the phase calculated from the difference of horizontal and vertical neighboring pixels of the edge image is used (Sobel operator). Let d x (i, j) and d y (i, j) denote the gradient in x and y direction respectively and θ(i, j) defined in (3), denotes the V. Sintunata et al. / Advances in Science, Technology and Engineering Systems Journal Vol. 2, No. 3, 10132, No. 3, -10182, No. 3, (2017 phase at position (i,j). Let p θ (i, j) be the approximation of orientation in a candidate point with coordinate (i,j) and is defined by (4). Equation 4 means that the angle approximation is determined by the average of the phase surrounding the point. Finally the filtering is done by using the k-means (k = 2) algorithm with the histograms' difference as features along with the intensity value at the corresponding pixel in the edge image.
Some of the points will lie very near with each other and it will affect the triangulation in the next step. Therefore a merging step is also applied to the filtered points, i.e. merging the points which lie near each other. The merged new position is calculated based on the average position of the merge points.

Skeleton Extraction
Skeleton extraction is done by first applying the Delaunay Triangulation to the edge points acquired in previous step. In order to do the skeleton extraction, a triangle grouping should be done. In [13,14] the authors classify triangles into 3 types: terminal triangle, junction triangle and sleeve triangle. The terminal triangle is defined as a triangle which has two outer contour as its edges. Junction triangle is defined as a triangle which does not have outer contour as its edges. Sleeve triangle is defined as a triangle which has only one outer contour as one of its edges. Note that in their application, which can be classified as the binary image skeletonization, the information regarding the outer edge is readily available. In our approach, we do not have that kind of information. Note that in the previous step during clustering using k-means, we do have the idea to determine a point whether it belongs to the boundary points or non-boundary points based on its histogram distance feature. Therefore, we used this information to cluster the edge as follows. Let point m i be the middle point of the i-th edge. By applying the same approach as in section 2, i.e. orientation approximation and histogram calculation, we can determine point m i to be an edge point based on its (feature-) vector distance to the center points of each cluster. Another way to see this is, we are not recalculating the cluster centers since the cluster centers (which will determine whether a point is a boundary or non-boundary point) has already been calculated in the previous step, the evaluation of these edge points (m) can be done just by calculating the distance to the cluster centers. If dist(m i , C k ) is defined as the L2 distance between point m i and the k-th center, then point m i belongs to the the k-th cluster if it has the minimum distance compared to another cluster's center.
In this case we can similarly define the triangles as in [13,14]. In sleeve triangle, two of its non-boundary m points will be connected together and no connection will be established in terminal triangle. Two types of junction triangles are defined: obtuse triangle and acute triangle. In case of acute triangle, an additional point (the center of triangle) will be added and every m points will be connected to this additional point. In obtuse triangle type, instead of generating an additional point, we connect the points on two of the edges of the largest angle to the point lying in front of the angle. See Figure 3 for visualization. Note that the yellow point (e.g. m 1 in Figure 3.a) represents m belonging to the boundary cluster. Given an initial skeleton (point to point connection) from the previous step, the problem now is to determine which of the connection belongs to the same object. Let T denotes the set of pixels traversed by the skeleton's edge (Figure 4). By calculating the mean pixel value of T we can get a set of feature vector (f ) to represent the skeleton for the clustering algorithm (5). The subscript l denotes the type of image the pixel belongs to, i.e. color images, brightness image, etc. Figure 5 shows the result of the clustering algorithm. Note that since the contrast of the color images might be low for some images and resulting in a non-discriminative cluster, a contrast limited adaptive histogram equalization (CLAHE) is applied to the color images. There is a possibility that the generated skeleton has a loop. In order to prevent such condition, loop removal step is applied. This is done by merging all the points of the loop into a point c, where c is the mean position of the points belonging to that loop ( Figure  6). If a loop consists of a smaller loop, only the largest loop is considered (Figure 7).

Skeleton Pruning
Some might notice some redundant skeleton branches from Figure 5. Skeleton pruning is the step required to remove these branches. Borrowing the triangle types term, depending on the number of connection it has, skeleton points can be classified into three types: terminal, sleeve, and junction point. Terminal point means that the point only has one connection with another skeleton point. Sleeve point means that it has two connections with two other skeleton points. Junction point defines a point with more than two connections with other points. In this paper, skeleton branches are defined as the terminal points which connect to junction point. If there are such connection, then the connection will be deleted ( Figure 8).
Finally, a bezier smoothing is applied to the skeleton. A curve skeleton is defined as the set of points starting from the terminal point until a junction point, therefore taking Figure 8 as an example, there are two curve skeletons in Figure 8. The sleeve points will be used as the control points for the bezier curve generation.

Experimental Result and Discussion
All experiments were done using a C++ language and OpenCV 2.4.9 library. There are several parameters which are fixed in this paper, i.e. the number of histogram bins is set to 16 and the size of the grid is set to 5 (refer to section 2.1). CIE Luv is used in this paper. Five images taken from the Berkeley dataset [15] were used for the experiment.
The results of the proposed method are then compared with a method based on [9]. Figure 9 shows the comparison, including the ground truth image generated by human observer. The first column is the ground truth skeleton image, the second column is the proposed method and the third column is skeleton generated based on [9]. Notice that although the proposed method did not generate the skeleton perfectly, it still represents the object in the image better than the method based on [9].
In order to further assess the result, F-measure of the ground truth and the methods were calculated (6). The precision and recall is calculated following (7) and (8). The number of true positive (tp) is calculated by counting the number of pixel where both the ground truth (GT) image (with a σ = 1 allowance) and the generated skeleton image have the same value. σ here means that if the generated skeleton differs only slightly, i.e. still inside the allowance σ then it is still considered to be true positive and hence counted. Notice again that when comparing both the image to calculate the F-measure, skeleton image generated has binary color where the pixels will have a 1 (white colored) value if the pixel is not traversed by the skeleton edge and 0 (black colored) if it is traversed by the skeleton edge. For the false negative (fn), it is calculated as the number of pixel where it has a value of 1 in the ground truth image, but 0 in the skeleton im-V.Sintunata, T.Aoki / Advances in Science, Technology and Engineering Systems Journal Vol. 2, No. 3, 10132, No. 3, -10182, No. 3, (2017 age. Vice versa, for false positive (fp), we are counting the number of pixel where it has value of 0 in the ground truth but 1 in the skeleton image. Table  1 shows the result of the F-measure calculation. Figure 9: The skeleton is overlaid on top of the input image. For visualization purpose, the skeleton is colored red.
P recision = tp tp + f p Recall = tp tp + f n (8) Although every image has its own best parameters, for general purpose, we try to find the parameter values which gave the best average F-measure from the test images. Four window sizes, which is used for histogram calculation, were tested (n = 7, 9, 11, and 15) along with the CLAHE limit parameter (l = 2 and 4). The result is shown in Figure 10. The x-axis is the combination parameters, i.e. (n,l). As shown in Figure 10 the combination of n = 9 and l = 4 has higher average F-measure among the other combinations.

Conclusion
In this paper a novel method to extract 2D skeleton information from a natural image is proposed. Based on the results shown in section 3, the proposed method shows a higher performance compared to the SSM method. Not only compared visually, in order to have a better comparison, the proposed method and SSM method is also compared by calculating their F-measures, which is shown to outperform the SSM method. There are several limitations for the proposed method, e.g. some images still have redundant skeleton branches and user interference (manually select) when choosing the final skeleton cluster (subsection 2.2). Therefore for our future work, we are going to solve these problems.


Towards Green Sensing Virtual Enterprises: Interconnected Sensing Enterprises, Intelligent Assets and Smart Products in the Cyber-Physical Circular Economy

This paper undertakes the conceptual development of Green Sensing Virtual Enterprises (GSVEs) and their potential application environments, as goal-oriented networks that are dynamically created and composed by a short-term alliance of green enterprises with sensing capabilities, whose interactions are enabled by sensor networks and supported by computer systems, in order to answer to collaboration opportunities requiring competencies beyond those available in any single enterprise, and will evolve or dissolve once their mission is accomplished. GSVEs are seen as the organisational counterpart of intelligent assets and smart products in an emerging Dynamic Cyber-Physical Circular Economy powered by pervasive digital transformation, where the synergy of the Internet of Things (IoT) paradigm, the Sensing Enterprise (SE) capabilities and the agile and environmental-friendly nature of Green Virtual Enterprises (GVEs) will unlock the full potential of circular business opportunities.

INTRODUCTION
Reflecting the necessary evolution from 'business as usual' in Circular Economy (EMF, 2016) eco-systems towards self-aware and proactive ones, where Sensing Enterprises (SEs) (FInES Cluster, 2011) and their dynamic value networks (Noran et al., 2014) interact with intelligent assets1 (EMF, 2016) and smart products 1 (Kiritsis, 2011), this exploratory research work aims to unlock new 'circular business' opportunities (Bocken et al., 2013) that can create significant sources of sustainable value for networked Small and Medium-sized Enterprises (SMEs). This endeavour presents as a necessity in the context of exponential growth of a Digital Economy (Deloitte Digital, 2012) bringing closer than ever people, organisations and resources within (virtual) collaborative networks (Camarinha-Matos et al., 2008;2009;2010), and thus connecting networked manufacturers and service providers with their value offers (e.g. product-service systems (Reim et al., 2015) by means of the Internet of Things (IoT) (Ashton, 2009), Cyber-Physical Systems (CPSs) (Lee, 2008) and Future Internet Enterprise Systems (FInES) (FInES Cluster, 2009) . Moreover, the Circular Economy (CE) is evolving towards a more Dynamic and Cyber-Physical form (DCPCE), where current circular business opportunities are being maximised by IoT, CPSs and FInES technologies and also creating new ones (e.g. digital servitization). In other words, creating new green revenue streams based on extending products' use cycle (e.g. reuse, repair and other value-added service offers) and thus creating more value from each unit of resource recovered (e.g. refurbishment, remanufacturing and recycling) enabled by the possibility of identifying, authenticating, locating, tracking and remotely interacting with intelligent assets and smart products across their entire useful life. 1 A physical object that is able to sense, record and communicate information about itself and/or their surroundings (Kiritsis, 2011; EMF, 2016).

SENSING ENTERPRISES AND DYNAMIC VIRTUAL ENTERPRISES
In the context of an ever increasing Networked and Digital Economy, successful enterprises are bound to exhibit increasing pervasiveness supported by IoT, CPS and FInES technologies, which are blurring their traditional boundaries to such extent that stimuli coming from within vs. outside of the enterprise can no longer be effectively distinguished. In fact, it is not characterised only by awareness (as the term implies), but also by decentralised intelligence (Noran et al., 2014).
A SE can be described as "an enterprise that can foresee future decisions by using multi-dimensional information captured through physical and virtual objects so as to enhance its global context awareness" (FInES Cluster, 2011). SEs also feature decentralised intelligence, relevant not only to collaborative decision making, but also to purposefulness and well-being of the human side; thus, a SE can in fact be considered a 'social' enterprise. The 'liquid' (ubiquitous) character increasingly attributed to the SE is owing to the trend of sensors becoming a shared commodity (FInES Cluster, 2011) that allows other organisations to provide value-added services, based on observations of these sensors (Noran et al., 2014).
The typical key capabilities of the SE are awareness, perceptivity, intelligence and extroversion (Zdravković et al., 2014). Awareness can be internal (self-), environmental (external-) but also universal -enabling the observation of unknown or unexpected sources, whether multi-modal, multidimensional, discrete or continuous. Perceptivity is a capability of an SE to assign a meaning to an internal or external observation and then decide on a suitable course of action as a result of a cognitive process using intelligence. SE extroversion relates to the willingness and capability of the SE to articulate its actions and demonstrates its business motivation and/or a concern about its physical and social environment (Zdravković et al., 2014; Noran et al., 2014).

INTRODUCTION
Reflecting the necessary evolution from 'business as usual' in Circular Economy (EMF, 2016) eco-systems towards self-aware and proactive ones, where Sensing Enterprises (SEs) (FInES Cluster, 2011) and their dynamic value networks (Noran et al., 2014) interact with intelligent assets1 (EMF, 2016) and smart products 1 (Kiritsis, 2011), this exploratory research work aims to unlock new 'circular business' opportunities (Bocken et al., 2013) that can create significant sources of sustainable value for networked Small and Medium-sized Enterprises (SMEs). This endeavour presents as a necessity in the context of exponential growth of a Digital Economy (Deloitte Digital, 2012) bringing closer than ever people, organisations and resources within (virtual) collaborative networks (Camarinha-Matos et al., 2008;2009;2010), and thus connecting networked manufacturers and service providers with their value offers (e.g. product-service systems (Reim et al., 2015)  Moreover, the Circular Economy (CE) is evolving towards a more Dynamic and Cyber-Physical form (DCPCE), where current circular business opportunities are being maximised by IoT, CPSs and FInES technologies and also creating new ones (e.g. digital servitization). In other words, creating new green revenue streams based on extending products' use cycle (e.g. reuse, repair and other value-added service offers) and thus creating more value from each unit of resource recovered (e.g. refurbishment, remanufacturing and recycling) enabled by the possibility of identifying, authenticating, locating, tracking and remotely interacting with intelligent assets and smart products across their entire useful life. 1 A physical object that is able to sense, record and communicate information about itself and/or their surroundings (Kiritsis, 2011; EMF, 2016).

SENSING ENTERPRISES AND DYNAMIC VIRTUAL ENTERPRISES
In the context of an ever increasing Networked and Digital Economy, successful enterprises are bound to exhibit increasing pervasiveness supported by IoT, CPS and FInES technologies, which are blurring their traditional boundaries to such extent that stimuli coming from within vs. outside of the enterprise can no longer be effectively distinguished. In fact, it is not characterised only by awareness (as the term implies), but also by decentralised intelligence (Noran et al., 2014).
A SE can be described as "an enterprise that can foresee future decisions by using multi-dimensional information captured through physical and virtual objects so as to enhance its global context awareness" (FInES Cluster, 2011). SEs also feature decentralised intelligence, relevant not only to collaborative decision making, but also to purposefulness and well-being of the human side; thus, a SE can in fact be considered a 'social' enterprise. The 'liquid' (ubiquitous) character increasingly attributed to the SE is owing to the trend of sensors becoming a shared commodity (FInES Cluster, 2011) that allows other organisations to provide value-added services, based on observations of these sensors (Noran et al., 2014).
The typical key capabilities of the SE are awareness, perceptivity, intelligence and extroversion (Zdravković et al., 2014). Awareness can be internal (self-), environmental (external-) but also universal -enabling the observation of unknown or unexpected sources, whether multi-modal, multidimensional, discrete or continuous. Perceptivity is a capability of an SE to assign a meaning to an internal or external observation and then decide on a suitable course of action as a result of a cognitive process using intelligence. SE extroversion relates to the willingness and capability of the SE to articulate its actions and demonstrates its business motivation and/or a concern about its physical and social environment (

Towards Green Sensing Virtual Enterprises: Interconnected Sensing Enterprises, Intelligent Assets and Smart Products in the Cyber-Physical Circular Economy
David Romero *, ** , Ovidiu Noran ** ,  *Tecnológico de Monterrey, Mexico, david.romero.diaz@gmail.com **Griffith University, Australia, o.noran@griffith.edu.au Abstract. This paper undertakes the conceptual development of Green Sensing Virtual Enterprises (GSVEs) and their potential application environments, as goal-oriented networks that are dynamically created and composed by a short-term alliance of green enterprises with sensing capabilities, whose interactions are enabled by sensor networks and supported by computer systems, in order to answer to collaboration opportunities requiring competencies beyond those available in any single enterprise, and will evolve or dissolve once their mission is accomplished. GSVEs are seen as the organisational counterpart of intelligent assets and smart products in an emerging Dynamic Cyber-Physical Circular Economy powered by pervasive digital transformation, where the synergy of the Internet of Things (IoT) paradigm, the Sensing Enterprise (SE) capabilities and the agile and environmental-friendly nature of Green Virtual Enterprises (GVEs) will unlock the full potential of circular business opportunities. . In other words, creating new green revenue streams based on extending products' use cycle (e.g. reuse, repair and other value-added service offers) and thus creating more value from each unit of resource recovered (e.g. refurbishment, remanufacturing and recycling) enabled by the possibility of identifying, authenticating, locating, tracking and remotely interacting with intelligent assets and smart products across their entire useful life.

SENSING ENTERPRISES AND DYNAMIC VIRTUAL ENTERPRISES
In the context of an ever increasing Networked and Digital Economy, successful enterprises are bound to exhibit increasing pervasiveness supported by IoT, CPS and FInES technologies, which are blurring their traditional boundaries to such extent that stimuli coming from within vs. outside of the enterprise can no longer be effectively distinguished. In fact, it is not characterised only by awareness (as the term implies), but also by decentralised intelligence (Noran et al., 2014).
A SE can be described as "an enterprise that can foresee future decisions by using multi-dimensional information captured through physical and virtual objects so as to enhance its global context awareness" (FInES Cluster, 2011). SEs also feature decentralised intelligence, relevant not only to collaborative decision making, but also to purposefulness and well-being of the human side; thus, a SE can in fact be considered a 'social' enterprise. The 'liquid' (ubiquitous) character increasingly attributed to the SE is owing to the trend of sensors becoming a shared commodity (FInES Cluster, 2011) that allows other organisations to provide value-added services, based on observations of these sensors (Noran et al., 2014).
The typical key capabilities of the SE are awareness, perceptivity, intelligence and extroversion (Zdravković et al., 2014). Awareness can be internal (self-), environmental (external-) but also universal -enabling the observation of unknown or unexpected sources, whether multi-modal, multidimensional, discrete or continuous. Perceptivity is a capability of an SE to assign a meaning to an internal or external observation and then decide on a suitable course of action as a result of a cognitive process using intelligence. SE extroversion relates to the willingness and capability of the SE to articulate its actions and demonstrates its business motivation and/or a concern about its physical and social environment (

Towards Green Sensing Virtual Enterprises: Interconnected Sensing Enterprises, Intelligent Assets and Smart Products in the Cyber-Physical Circular Economy
David Romero *, ** , Ovidiu Noran ** ,  *Tecnológico de Monterrey, Mexico, david.romero.diaz@gmail.com **Griffith University, Australia, o.noran@griffith.edu.au Abstract. This paper undertakes the conceptual development of Green Sensing Virtual Enterprises (GSVEs) and their potential application environments, as goal-oriented networks that are dynamically created and composed by a short-term alliance of green enterprises with sensing capabilities, whose interactions are enabled by sensor networks and supported by computer systems, in order to answer to collaboration opportunities requiring competencies beyond those available in any single enterprise, and will evolve or dissolve once their mission is accomplished. GSVEs are seen as the organisational counterpart of intelligent assets and smart products in an emerging Dynamic Cyber-Physical Circular Economy powered by pervasive digital transformation, where the synergy of the Internet of Things (IoT) paradigm, the Sensing Enterprise (SE) capabilities and the agile and environmental-friendly nature of Green Virtual Enterprises (GVEs) will unlock the full potential of circular business opportunities.

SENSING ENTERPRISES AND DYNAMIC VIRTUAL ENTERPRISES
In the context of an ever increasing Networked and Digital Economy, successful enterprises are bound to exhibit increasing pervasiveness supported by IoT, CPS and FInES technologies, which are blurring their traditional boundaries to such extent that stimuli coming from within vs. outside of the enterprise can no longer be effectively distinguished. In fact, it is not characterised only by awareness (as the term implies), but also by decentralised intelligence (Noran et al., 2014).
A SE can be described as "an enterprise that can foresee future decisions by using multi-dimensional information captured through physical and virtual objects so as to enhance its global context awareness" (FInES Cluster, 2011). SEs also feature decentralised intelligence, relevant not only to collaborative decision making, but also to purposefulness and well-being of the human side; thus, a SE can in fact be considered a 'social' enterprise. The 'liquid' (ubiquitous) character increasingly attributed to the SE is owing to the trend of sensors becoming a shared commodity (FInES Cluster, 2011) that allows other organisations to provide value-added services, based on observations of these sensors (Noran et al., 2014).
The typical key capabilities of the SE are awareness, perceptivity, intelligence and extroversion (Zdravković et al., 2014). Awareness can be internal (self-), environmental (external-) but also universal -enabling the observation of unknown or unexpected sources, whether multi-modal, multidimensional, discrete or continuous. Perceptivity is a capability of an SE to assign a meaning to an internal or external observation and then decide on a suitable course of action as a result of a cognitive process using intelligence. SE extroversion relates to the willingness and capability of the SE to articulate its actions and demonstrates its business motivation and/or a concern about its physical and social environment (Zdravković et al., 2014;Noran et al., 2014).

INTRODUCTION
Reflecting the necessary evolution from 'business as usual' in Circular Economy (EMF, 2016) eco-systems towards self-aware and proactive ones, where Sensing Enterprises (SEs) (FInES Cluster, 2011) and their dynamic value networks (Noran et al., 2014) interact with intelligent assets1 (EMF, 2016) and smart products 1 (Kiritsis, 2011), this exploratory research work aims to unlock new 'circular business' opportunities (Bocken et al., 2013) that can create significant sources of sustainable value for networked Small and Medium-sized Enterprises (SMEs). This endeavour presents as a necessity in the context of exponential growth of a Digital Economy (Deloitte Digital, 2012) bringing closer than ever people, organisations and resources within (virtual) collaborative networks (Camarinha-Matos et al., 2008;2009;2010), and thus connecting networked manufacturers and service providers with their value offers (e.g. product-service systems (Reim et al., 2015)  Moreover, the Circular Economy (CE) is evolving towards a more Dynamic and Cyber-Physical form (DCPCE), where current circular business opportunities are being maximised by IoT, CPSs and FInES technologies and also creating new ones (e.g. digital servitization). In other words, creating new green revenue streams based on extending products' use cycle (e.g. reuse, repair and other value-added service offers) and thus creating more value from each unit of resource recovered (e.g. refurbishment, remanufacturing and recycling) enabled by the possibility of identifying, authenticating, locating, tracking and remotely interacting with intelligent assets and smart products across their entire useful life. 1 A physical object that is able to sense, record and communicate information about itself and/or their surroundings (Kiritsis, 2011; EMF, 2016).

SENSING ENTERPRISES AND DYNAMIC VIRTUAL ENTERPRISES
In the context of an ever increasing Networked and Digital Economy, successful enterprises are bound to exhibit increasing pervasiveness supported by IoT, CPS and FInES technologies, which are blurring their traditional boundaries to such extent that stimuli coming from within vs. outside of the enterprise can no longer be effectively distinguished. In fact, it is not characterised only by awareness (as the term implies), but also by decentralised intelligence (Noran et al., 2014).
A SE can be described as "an enterprise that can foresee future decisions by using multi-dimensional information captured through physical and virtual objects so as to enhance its global context awareness" (FInES Cluster, 2011). SEs also feature decentralised intelligence, relevant not only to collaborative decision making, but also to purposefulness and well-being of the human side; thus, a SE can in fact be considered a 'social' enterprise. The 'liquid' (ubiquitous) character increasingly attributed to the SE is owing to the trend of sensors becoming a shared commodity (FInES Cluster, 2011) that allows other organisations to provide value-added services, based on observations of these sensors (Noran et al., 2014).
The typical key capabilities of the SE are awareness, perceptivity, intelligence and extroversion (Zdravković et al., 2014). Awareness can be internal (self-), environmental (external-) but also universal -enabling the observation of unknown or unexpected sources, whether multi-modal, multidimensional, discrete or continuous. Perceptivity is a capability of an SE to assign a meaning to an internal or external observation and then decide on a suitable course of action as a result of a cognitive process using intelligence. SE extroversion relates to the willingness and capability of the SE to articulate its actions and demonstrates its business motivation and/or a concern about its physical and social environment (Zdravković et al., 2014;Noran et al., 2014).

INTRODUCTION
Reflecting the necessary evolution from 'business as usual' in Circular Economy (EMF, 2016) eco-systems towards self-aware and proactive ones, where Sensing Enterprises (SEs) (FInES Cluster, 2011) and their dynamic value networks (Noran et al., 2014) interact with intelligent assets1 (EMF, 2016) and smart products 1 (Kiritsis, 2011), this exploratory research work aims to unlock new 'circular business' opportunities (Bocken et al., 2013) that can create significant sources of sustainable value for networked Small and Medium-sized Enterprises (SMEs). This endeavour presents as a necessity in the context of exponential growth of a Digital Economy (Deloitte Digital, 2012) bringing closer than ever people, organisations and resources within (virtual) collaborative networks (Camarinha-Matos et al., 2008;2009;2010), and thus connecting networked manufacturers and service providers with their value offers (e.g. product-service systems (Reim et al., 2015)  Moreover, the Circular Economy (CE) is evolving towards a more Dynamic and Cyber-Physical form (DCPCE), where current circular business opportunities are being maximised by IoT, CPSs and FInES technologies and also creating new ones (e.g. digital servitization). In other words, creating new green revenue streams based on extending products' use cycle (e.g. reuse, repair and other value-added service offers) and thus creating more value from each unit of resource recovered (e.g. refurbishment, remanufacturing and recycling) enabled by the possibility of identifying, authenticating, locating, tracking and remotely interacting with intelligent assets and smart products across their entire useful life. 1 A physical object that is able to sense, record and communicate information about itself and/or their surroundings (Kiritsis, 2011; EMF, 2016).

SENSING ENTERPRISES AND DYNAMIC VIRTUAL ENTERPRISES
In the context of an ever increasing Networked and Digital Economy, successful enterprises are bound to exhibit increasing pervasiveness supported by IoT, CPS and FInES technologies, which are blurring their traditional boundaries to such extent that stimuli coming from within vs. outside of the enterprise can no longer be effectively distinguished. In fact, it is not characterised only by awareness (as the term implies), but also by decentralised intelligence (Noran et al., 2014).
A SE can be described as "an enterprise that can foresee future decisions by using multi-dimensional information captured through physical and virtual objects so as to enhance its global context awareness" (FInES Cluster, 2011). SEs also feature decentralised intelligence, relevant not only to collaborative decision making, but also to purposefulness and well-being of the human side; thus, a SE can in fact be considered a 'social' enterprise. The 'liquid' (ubiquitous) character increasingly attributed to the SE is owing to the trend of sensors becoming a shared commodity (FInES Cluster, 2011) that allows other organisations to provide value-added services, based on observations of these sensors (Noran et al., 2014).
The typical key capabilities of the SE are awareness, perceptivity, intelligence and extroversion (Zdravković et al., 2014). Awareness can be internal (self-), environmental (external-) but also universal -enabling the observation of unknown or unexpected sources, whether multi-modal, multidimensional, discrete or continuous. Perceptivity is a capability of an SE to assign a meaning to an internal or external observation and then decide on a suitable course of action as a result of a cognitive process using intelligence. SE extroversion relates to the willingness and capability of the SE to articulate its actions and demonstrates its business motivation and/or a concern about its physical and social environment ( The second source of sustainable value and enabler for a DCPCE relies on the ever increasing variety of new 'intelligent assets' and 'smart products' having various degrees of ability to sense, store and communicate information about themselves and/or their surroundings in order to expose (new) servitization (e.g. maintenance, repair and overhaul) and circularity (e.g. reuse, refurbishment, remanufacture and recycling) business opportunities (Kiritsis, 2011;EMF, 2016;Romero & Molina, 2013;2014;2015). This intelligence ('smartness') is enabled by the IoT paradigm, transforming previously passive assets and products into 'live' (active) entities capable of sharing information about their location, condition and availability; moreover, these live entities would also be capable to trigger a call for action, e.g. for service provisioning to be provided by their Original Equipment Manufacturer (OEM). As a result, intelligent assets and smart products become 'omnipresent things' that rely on an 'alert' OEM across their useful life (lifecycle), who continuously senses their status and requirements for ad-hoc service provisioning.
Based on the next generation assets and products scenario described above, the third source of sustainable value and enabler of a DCPCE identified by the authors relies on the sensing capabilities of the intelligent assets and smart products manufacturers and service providers -in other words, on the SEs (see Section 2), which are "[…] capable of anticipating future decisions by using multi-dimensional information capture through physical and virtual objects and providing added value information to enhance its global context awareness" (FInES Cluster, 2011;Noran et al., 2014). Thus, manufacturing and service provisioning enterprises will appropriately sense and capture the necessary information in real-time from intelligent assets and smart products and their environment, thus providing the enterprises belonging to that asset-or product value chain with 'sense and respond' capabilities for a wide-ranging set of business stimuli.
In this paper, the authors employ the above-described concepts in exploring the conceptual development of Green Sensing Virtual Enterprises (GSVEs), as goal-oriented cohesive and loosely coupled mini-networks that are dynamically created and are typically composed by a short-term alliance of green enterprises with sensing capabilities, whose interactions are enabled by sensor networks and supported by computer systems. GSVEs are created in order to rise to a collaboration opportunity and will dissolve once their mission is accomplished [see Figure 1].

Green
Sensing Virtual Enterprise