# Adjoining edges to $G\mathbin{\square}H$ to construct a
minimal dominating set of size $\gamma(G)\gamma(H)$

Allan van Hulst
<EMAIL_ADDRESS>
###### Abstract

For graphs $G,H$ it is possible to add $(|V(G)|-\gamma(G))(|V(H)|-\gamma(H))$
edges to the Cartesian product $G\mathbin{\square}H$ such that a minimal
dominating set $D$ of size $\gamma(G)\gamma(H)$ emerges. We hypothesize that
$D$ is also a minimum dominating set for the resulting graph and show that
this implies Vizing’s conjecture.

All graphs $G=(V(G),E(G))$ in this note are assumed to be simple and without
isolated vertices. A set $D\subseteq V(G)$ dominates $G$ if for all $v\in
V(G)-D$ there exists a $u\in D$ such that $u\sim v$. The expression
$\gamma(G)$ denotes the minimum cardinality of such a $D$. A dominating set
$D$ is minimal if it does not have a strict subset that dominates $G$, which
may include cases where $|D|>\gamma(G)$. The Cartesian product
$G\mathbin{\square}H$ is a graph having $V(G)\times V(H)$ as its set of
vertices. Adjacency in $G\mathbin{\square}H$ is defined as
$(u,v)\sim(u^{\prime},v^{\prime})$ if and only if either (a) $u=u^{\prime}$
and $v\sim v^{\prime}$ in $H$ or (b) $v=v^{\prime}$ and $u\sim u^{\prime}$ in
$G$. These definitions are standard in the literature on graphs and dominating
sets [3, 4].

Vizing111I would like to thank Anna Kathekina for translating parts of
Vizing’s original work for me. postulated the following inequality over all
$G$ and $H$ as a conjecture [6, 7]:

$\gamma(G)\gamma(H)\leq\gamma(G\mathbin{\square}H)$ (1)

which is a sharp bound if (1) holds true. For more background information on
Vizing’s conjecture, survey articles are available [2, 5]. The objective of
this note is to study a conceptual reversal of the inequality in (1): it is
shown that a number of edge-additions to $G\mathbin{\square}H$ creates a
minimal dominating set $D$ of size $\gamma(G)\gamma(H)$. If $D$ can also be
shown to be a minimum dominating set for the edge-adjoined graph, Vizing’s
conjecture follows directly. For clarity, this conditional implication refers
to inequality $(\ref{eqn:vizing})$ and not to some alternative form of
Vizing’s conjecture on these edge-adjoined graphs.

We now establish some further groundwork. The open neighborhood of a vertex
$u\in V(G)$ is defined as $N(u)=\\{v\in V(G)\mid u\sim v\\}$. A vertex $v\in
V(G)-D$ is said to be a private neighbor of $u\in D$ if $u\sim v$ and
$N(v)\cap D=\\{u\\}$. The set of private neighbors of a $u\in D$ is denoted by
$P(u)$. A dominating set $D\subseteq V(G)$ is said to be in canonical form if
every $u\in D$ has at least one private neighbor in $G$. Canonical dominating
sets of minimum size always exist, although these are not necessarily unique.

######  Lemma 1.

[Adapted from [1], page 7] For all graphs $G$ there exists a canonical
dominating set $D\subseteq V(G)$ such that $|D|=\gamma(G)$.

###### Proof.

Pick a minimum dominating set $D$ such that the number of edges in the
subgraph induced by $D$ is maximal. Let $u\in D$ and assume towards a
contradiction that $P(u)=\emptyset$. We distinguish between two cases: (a) if
there exists a $u^{\prime}\in D$ such that $u\sim u^{\prime}$ then $D-\\{u\\}$
is a smaller dominating set and, (b) if $N(u)\cap D=\emptyset$ then there must
exist at least one $v\in V(G)-D$ such that $u\sim v$ which makes
$(D-\\{u\\})\cup\\{v\\}$ a dominating set inducing a subgraph with more edges.
∎

A dominating set $D$ in canonical form provides an insightful way to construct
a surjective function from the non-dominated vertices onto $D$, thereby
following edges.

######  Lemma 2.

For all graphs $G$ and canonical dominating sets $D\subseteq V(G)$ there
exists a surjection $F:V(G)-D\longrightarrow D$ such that $F(v)=u$ implies
$u\sim v$.

###### Proof.

First, we create a surjective partial function by setting $F(v)=u$ for all
$u\in D$ and $v\in P(u)$, Then, we can extend $F$ to a total function by
assigning any remaining vertices in $V(G)-D$ to an arbitrary neighbor in $D$.
∎

We now move to the setting of the Cartesian product and extend the surjective
functions associated with the operands to a new function. Let $D_{G}\subseteq
V(G)$ and $D_{H}\subseteq V(H)$ be respective canonical dominating sets for
graphs $G$ and $H$ derived by Lemma 1. Additionally, let
$F_{G}:V(G)-D_{G}\longrightarrow D_{G}$ and $F_{H}:V(H)-D_{H}\longrightarrow
D_{H}$ be surjective functions as obtained from Lemma 2 and define
$S:V(G\mathbin{\square}H)-D_{G}\times D_{H}\longrightarrow D_{G}\times D_{H}$
as:

$S(u,v)=\begin{cases}(F_{G}\,(u),v)&\mathrm{if}\,\,u\in
V(G)-D_{G}\,\,\mathrm{and}\,\,v\in D_{H}\\\ (u,F_{H}\,(v))&\mathrm{if}\,\,u\in
D_{G}\,\,\mathrm{and}\,\,v\in V(H)-D_{H}\\\
(F_{G}\,(u),F_{H}(v))&\mathrm{if}\,\,u\in V(H)-D_{G}\,\,\mathrm{and}\,\,v\in
V(H)-D_{H}.\\\ \end{cases}$

Observe that $S$ is always total, univalent and surjective onto $D_{G}\times
D_{H}$. We can now define an adjoint graph $A_{G,H}[F_{G},F_{H}]$ as:

$A_{G,H}[F_{G},F_{H}]=(V(G\mathbin{\square}H),E(G\mathbin{\square}H)\cup
E_{S}),$

where $E_{S}$ is defined as:

$E_{S}=\\{\\{(u,v),(u^{\prime},v^{\prime})\\}\mid
S(u,v)=(u^{\prime},v^{\prime}),\,(u,v)\in(V(G)-D_{G})\times(V(H)-D_{H})\\}.$

We may now prove an interesting property, notably:

######  Lemma 3.

$D_{G}\times D_{H}$ is a minimal dominating set for $A_{G,H}[F_{G},F_{H}]$.

###### Proof.

First, we show that $D_{G}\times D_{H}$ is a dominating set. Let $(u,v)\in
V(G\mathbin{\square}H)-D_{G}\times D_{H}$. If $u\in D_{G}$ and $v\in
V(H)-D_{H}$ then there exists an edge $v\sim v^{\prime}$ for some
$v^{\prime}\in D_{H}$ and an edge $(u,v)\sim(u,v^{\prime})$ in
$G\mathbin{\square}H$. The case for $u\in V(G)-D_{G}$ and $v\in D_{H}$ is
symmetric. If $u\in V(G)-D_{G}$ and $v\in V(H)-D_{H}$ then there exists a
$(u^{\prime},v^{\prime})\in D_{G}\times D_{H}$ such that
$S(u,v)=(u^{\prime},v^{\prime})$.

Then, we must show that $D_{G}\times D_{H}$ is minimal. Assume that
$D=D_{G}\times D_{H}-\\{(u,v)\\}$ for some $(u,v)\in D_{G}\times D_{H}$ and
observe that none of the vertices in $P(u)\times P(v)$ can be dominated by
$D$. ∎

This leads to a conjecture stated in a form similar to Lemma 3:

######  Conjecture 1.

$D_{G}\times D_{H}$ is a minimum dominating set for $A_{G,H}[F_{G},F_{H}]$.

It is clear that any dominating set $D\subseteq V(G\mathbin{\square}H)$ for
$G\mathbin{\square}H$, in particular when $|D|=\gamma(G\mathbin{\square}H)$,
must also dominate $A_{G,H}[F_{G},F_{H}]$ since $G\mathbin{\square}H$ is a
subgraph of $A_{G,H}[F_{G},F_{H}]$ on the same set of vertices. Therefore, it
is sufficient to prove Conjecture 1 to resolve Vizing’s conjecture as the
result $\gamma(G)\gamma(H)=|D_{G}\times
D_{H}|\leq|D|=\gamma(G\mathbin{\square}H)$ is direct.

## References

  * [1] B. Bollobás and E. Cockayne. Graph-theoretic parameters concerning domination, independence, and irredundance. _Journal of Graph Theory_ , 3(3):241–249, 1979.
  * [2] B. Brešar, P. Dorbec, W. Goddard, B. Hartnell, M. Henning, S. Klavžar, and D. Rall. Vizing’s conjecture: a survey and recent results. _Journal of Graph Theory_ , 69(1):46–76, 2012\.
  * [3] E. Cockayne. Domination of undirected graphs — a survey. _Theory and Applications of Graphs_ , 141–147, 1978.
  * [4] E. Cockayne and S. Hedetniemi. Towards a theory of domination in graphs. _Networks_ 7(3):247–261, 1977.
  * [5] B. Hartnell and D. Rall. Domination in Cartesian products: Vizing’s conjecture. _Domination in graphs_ in Monographs and Textbooks in Pure and Applied Mathematics, 209:163–190, 2017.
  * [6] V. Vizing. The Cartesian product of graphs (in Russian). _Vychislitel’nye sistemy_ , 9:30–43, 1963.
  * [7] V. Vizing. Some unsolved problems in graph theory (in Russian). _Uspekhi Matematicheskikh Nauk_ , 23(6):117–134, 1968.


# Impact of Blockchain Technology on Electric Power Grids – A case study in
LO3 Energy

Sakineh Khalili1 Vahid Disfani2 Mo Ahmadi1 1 Gary W. Rollins College of
Business, University of Tennessee at Chattanooga, TN 37403
2 ConnectSmart Research Laboratory, Department of Electrical Engineering,
University of Tennessee at Chattanooga, TN 37403

###### Abstract

The increasing amount of distributed energy resources including renewable
energy systems and electric vehicles is expected to change electric power
grids significantly, where conventional consumers are transformed to prosumers
since they can produce electricity as well. In such an ecosystem, prosumers
can start offering their excess energy to supply demands of the other
customers on the grids behind the meter without interference of distribution
system operators (DSO). Besides, DSOs require more accurate and more frequent
data form prosumers’ net demand to be able to operate their network
efficiently. The main challenge in these new distribution grids is the amount
of data that needs to be collected in this platform is unbelievably high, and
more immortally, prosumers will likely refuse to share their information with
DSOs due to their potential privacy and economic concerns. Blockchain
technology as an efficient distributed solution for management of data and
financial transactions, has been considered to solve this trust issue. With
blockchain-based solutions, data and financial transactions between all
parties will take placed through distributed ledgers without any interference
from an intermediary. In this paper, impacts of blockchain technologies on
electric power industry is studied. The paper specifically focuses on LO3
Energy –one of startups applying blockchain to electric power grids,– their
blockchain-based solution called Exergy, and their use cases to implement such
solutions.

##  1 Introduction

Information Technology (IT) benefits all businesses by enabling them to
enhance their data storage systems, process transactions faster, disseminate
information more effectively, and to improve quality of their products and
services in a more efficient manner. In short, adoption of IT enables
businesses to (1) solves their problems faster and more simply through
computer applications, (2) make their decisions and respond to changes rapidly
by studying their available data and collecting their team members’ inputs,
and (3) to enhance their customer service quality by connecting with their
customers, hearing their stories first hand, and providing prompt assistance
(Eason, 2014).

Among these technologies, blockchain technology emerged from its use as
verification mechanism for cryptocurrencies in 2008 and heads to a broader
field of economic applications (Mengelkamp, Notheisen ., 2018). Blockchain has
been implemented in various industries including finance and insurance
(Tapscott Tapscott, 2017; Eyal, 2017), information and communication (Huckle
., 2016; Huh ., 2017), healthcare (Mettler, 2016; Peterson ., 2016), and
energy (Aitzhan Svetinovic, 2018; Kim ., 2018; Mengelkamp, Notheisen ., 2018;
Mengelkamp, Gärttner ., 2018). Figure 2 illustrates share of startups
developing blockchain technology for different industry sectors (Friedlmaier
., 2017).

In energy sectors alone, around 120 energy blockchain startups raised a total
of $324 million in 2017 (Muzzy, 2018). By October 2017, there were 15
international firms leading in energy blockchain from which 6 firms –Drift,
GridPlus, ImpactPPA, LO3 Energy, Power Ledger, SolarCoin– are based in the
United States, 8 reside in Europe, one is located in Asia, and one in Africa.
(Deign, 2017).

This paper focuses on LO3 Energy which is one of the US-based companies
developing blockchain solutions for electric power systems. LO3 Energy has
proposed a distributed ledger system, called Exergy, which functions across
grid-connected hardware and advances electricity market design and technology
in tandem (LO3-Energy, 20173)

##  2 Blockchain Technology

Blockchain technology was first emerged as a cryptocurrency system and the
underlying technology of Bitcoin in 2008 and swiftly headed toward a broader
filed of economic applications (Noor ., 2018). This technology is expected to
revolutionize the functioning of transaction systems and enable fully
distributed market platforms (Yuan Wang, 2016).

A blockchain system consists of distributed ledgers, decentralized consensus
mechanisms, and cryptographic security measures. Blockchain technology
provides a transparent and valid record of past transactions which may not be
changed retrospectively and allows faster and more efficient resolutions of
conflicts and dismantles information asymmetries without any need for
governing intermediaries (Beck ., 2016). In other words, with blockchain,
contracts are embedded in digital codes and stored in shared, transparent
databases protected from deletion, tampering, and revision. Using blockchain,
all agreements, processes, tasks, and payments will have digital records and
signatures which can be identified, validated, stored, and shared. Thus,
intermediaries like lawyers, brokers, and bankers might no longer be needed
for verification process or conflict resolutions (Iansiti Lakhani, 2017).

###  2.1 How Blockchain Works

Blockchain is a chain of blocks that contains information and includes a
distributed ledger which is completely open to everyone. Each block contains
some data, the hash (address) of the block, and the hash of the previous
block. The data stored inside a block depends on the type of blockchain. The
hash can be compared with a fingerprint, is unique, and identifies the block
and all of its contents. The third element inside each block is the hash of
the previous block to create the chain. This effectively creates a chain of
blocks and it is this technique that makes a blockchain very secure. There is
one more way that blockchains secure themselves and that is by being
distributed. Instead of being a central entity to manage the chain,
blockchains use the peer-to-peer network where everyone is allowed to join.
Anyone who joins the network, they get the full copy of the blockchain. When
someone creates a new block, that new block is sent to everyone on the
network, and each node verifies validity of the block. If all the nodes in
this network verifies the validity, consensus is created and each node adds
the block to their own blockchain. Blocks that are not valid will be rejected
by other nodes in the network. If hackers wants to corrupt the database, they
need to hack all blocks on the chain, redo hash calculations for each block,
and take control of more than 50% of the peer-to-peer network. Since it is s
very unlikely action, blockchain is considered extremely secure.(Singhal .,
2018)

###  2.2 Blockchain Principles

Blockchain transactions are continuously verified, cleared, and stored by the
network in digital blocks connected to previous blocks, thereby creating a
chain. The structure permanently time-stamps and stores exchanges of value.
Since each block must refer to the preceding block to be valid, altering the
ledger is almost impossible. To steal anything of value, a thief would have to
rewrite its entire history on the blockchain. Collective self-interest ensures
the blockchain’s safety and reliability. Therefore, we think blockchain
provides a powerful mechanism for blowing traditional and centralized models,
such as that of the corporation, to bits.

Blockchain technology is constructed by the following 5 underlying, basic
principles (Iansiti Lakhani, 2017):

  1. 1.

Distributed Database: There is no single party in the blockchain controlling
the data or the information. Instead, all parties have access to the entire
database and its complete history and are able to verify the records of their
transaction partners directly, without any intermediary.

  2. 2.

Peer-to-Peer Transmission: Blockchain is based on direct data communication
between parties (peers) instead of through a central node. While receiving a
new block of data, each party stores after validation and forwards it to all
other parties.

  3. 3.

Transparency with Pseudonymity: In blockchain, all transactions and their
associated values are transparent to all parties with access to the system. On
the other hand, parties on a blockchain are identified by a unique 30-plus-
character alphanumeric addresses, and transactions occur between blockchain
addresses. Parties may opt to remain anonymous or provide proof of their
identity to other parties.

  4. 4.

Irreversibility of Records: In blockchain, each block of data is identified by
an address called hash number and is linked to its previous data block in
blockchain by containing its hash number. Various computational algorithms and
approaches are deployed to ensure that the recording on the database is
permanent, chronologically ordered, and available to all others on the
network. Once a transaction enters the database, the records cannot be changed
since they are linked to its previous block, and corruption of one block
invalidates all down-stream blocks.

  5. 5.

Computational Logic: Blockchain transactions can be tied to computational
logic and in essence programmed. The digital nature of the ledgers enables
users to set up algorithms and rules that automatically trigger transactions
between parties.

In short, blockchain technology offers three main advantages (Tapscott
Tapscott, 2017):

  * •

It is distributed and runs on computers provided by volunteers around the
world, so there is no central database to hack.

  * •

It is public, and anyone can view it at any time because it resides on the
network;

  * •

It is encrypted and uses heavy-duty encryption to maintain security.

###  2.3 Need for Blockchain in Electric Power Grids

In the US, there is an 86% inefficiency in converting energy and delivering it
to the end users as the useful product, described by physicists as exergy,
which creates costly health and environmental challenges as well as
significant loss of economic values. Such problems will persist as long as
utilities use outdated constructs of its consumers as rate payers and miss the
opportunity and value only a customer or end user can provide (LO3-Energy,
20173).

Relatively high price of electricity, global commitments to halting climate
change, a slew of energy efficiency policies, and subsidies for renewable
power have motivated a new wave of technological innovation such as smart
energy services, battery storage, and rooftop solar Photovoltaic (PV) systems.
These technologies making it possible for customers to not only save energy,
but to produce their own power in factories and homes and become prosumers,
consumers with capability of producing energy. Therefore, for optimal
operation of their power grids, utilities need to have visibility into
millions of new consumer devices and distributed energy resources popping up
at the grid edge.

However, end users have no obligation to reveal their personal information and
may refuse to share their energy consumption and production data with
utilities due to various concerns such as privacy and economic interests.
Also, aggregation of all data from all customers in utilities’ databases is
not a secure solution. Thus, Blockchain as a reliable distributed data
management system has been investigated by several firms in electric power
sectors, including LO3 Energy.

Employing Blockchain technology enables utilities to have access to customers’
data for optimal asset management as well as to benefit from their new roles
as new value domains which customers will provide, including grid management
services –capacity, real power, reactive power, and frequency regulations
(LO3-Energy, 20171). Such data access allows this new values to be unlocked in
future structure of power grids. This data not only includes customers’ energy
demand or consumption, but also accounts for the state of the grid, the time
and location of production, and consumption requirements of a multi-party
electricity system (LO3-Energy, 20171).

Other than data management, adoption of blockchain in transactions between
customers and utilities as well as between customers themselves removes
friction in buying and selling real value-added energy services. Thus, smart
contracts and tokenization are seriously considered in application of
blockchain in power systems (Kim ., 2018).

###  2.4 Implementation of Blockchain by LO3 Energy

LO3 ENERGY has proposed and implemented blockchain by developing the concept
of Exergy consisting of a distributed ledger system which functions across
grid-connected hardware, a token system for transactive energy, and a
foundation which advances market design and technology in tandem. Exergy is
based on a market model called transactive energy, which refers to economic
and control techniques that enable broad participation in the new multi-party
energy system, and designed to provide all market participants more
opportunities to connect customers to energy system value. Exergy enables
customers and utilities to buy and sell value by ensuring data availability
for transactions at all electricity market levels. The Exergy blockchain is
the private distributed ledger which secures and manages the data needed to
create marketplace transactions, and settles those transactions cost-
effectively. Thus, blockchain is implemented by LO3 Energy, through Exergy, in
order to manage both data and transactions. (LO3-Energy, 20171, 20173, 20172)

####  2.4.1 Exergy Data Management System

For information systems, Exergy develops distributed ledger accounts to enable
data within the energy system to be securely transacted for different
marketplace behaviors such as buying or selling, and setting and reacting to
prices. Exergy runs on a private, permissioned blockchain –where certain
actions are just permitted by certain players within blockchain– through a
network of globally distributed computing nodes. Some of these Exergy-enabled
devices, which are developed by LO3 Energy as well as other 3rd party
providers, control, manage and validate actual power flows on the electricity
grid. Others simply verify and monitor marketplace rules and activity.

An Exergy-based data Collection system collects, controls and secures the data
to provide a wide range of advantages throughout power markets and ecosystems,
including (1) efficient and adaptive market pricing, (2) improved system
reliability and flexibility Pathway for technological innovation, (3) data
needed to develop additional direct and derivative markets, (4) improved
balance of risk and reward for asset owners, and (5) a rich, interactive
future for an energy industry serving informed communities (LO3-Energy,
20173).

####  2.4.2 Exergy Transaction Management System

For transaction management systems, Exergy System’s top layer, the “Exergy
Layer,” will use a blockchain to establish and manage a global network of
power market participants. It also establishes location, security and proof of
ownership. The Exergy token (“XRG”) is an ERC20-compliant exchange medium and
will be used to attract consumers, prosumers and communities to the
marketplace. Consumers and prosumers will be rewarded for their participation
in local energy markets, and other market participants such as generators,
aggregators and service providers can also acquire and hold tokens. The XRG
token is staked to access the marketplace, where available data and
transaction behavior can be verified into blocks and, where necessary, linked
to actual control of assets and settlement of energy transactions.

An Exergy-based transactive energy system (1) allows market participants
around the world to buy and sell electricity and (2) offer grid services based
on what the new decentralized system needs to operate at maximum efficiency,
reliability and flexibility. The Exergy token (XRG) also provides the
incentive for energy prosumers, consumers, and commercial market players to
participate in an energy marketplace where consumers are front and center.

###  2.5 LO3 Energy Use Cases for Blockchain Application

Through blockchain technology and innovative solutions, LO3 Energy has
developed Exergy, a permissioned data platform to create localized energy
marketplaces for transacting energy across existing grid infrastructure.
According to their white-papers (LO3-Energy, 20171, 20173, 20172), LO3 Energy
team have identified 4 use cases where blockchain technology has been or is
going to be implemented within its organization. These use cases are detailed
below and summarized in Table 1 on page 1.

####  2.5.1 Use Case 1 – Peer-to-Peer Energy: Brooklyn Microgrid

LO3 Energy has already implemented a peer-to-peer use case, the Brooklyn
Microgrid, to explore full market value of peer-to-peer energy. Blockchain
technology is used in this platform to let prosumers and consumers exchange
their data of excess energy and their power demand with each other without any
intermediary managing their communications. This data exchange allows
prosumers to transact their excess energy autonomously in real-time with
consumers on the platform in their local marketplace. Blockchain technology is
then used to clear value transactions between supply and demand parties using
XRG tokens.

####  2.5.2 Use Case 2: Microgrid

A microgrid is an ecosystem of connected prosumer and consumer energy assets,
where energy is generated, stored, and transacted locally and enhances
efficiency, resiliency and sustainability within communities. Applying Exergy
offers additional value to microgrid project developers, operators and other
hardware vendors. System-wide operational efficiency is improved by realizing
responsive load management and improving return on investment (ROI) and
economics for developers and operators. The blockchain-based Exergy (1) allows
monitoring of excess capacity and potential to sell to other microgrids, and
(2) finds value for the storage and other services available from the
microgrid. Data transparency and uniformity across project portfolios –as a
result of adopting blockchain technology– will further support future
commercial investments in microgrid ecosystem. Consumers and prosumers’ roles
in the microgrid use case look to similar to Use Case 1. The difference is
that in Use Case 2, there are several distinct microgrids connected to one
another over the existing distribution network, and the distribution system
operators (DSO) can open up their network to let electricity flow between
microgrids.

####  2.5.3 Use Case 3: Distribution System Operator (DSO) Use Case

With the current transformation in customers’ roles in power grids and their
capability of generating energy, the distribution network operator role is
also evolving as more activity is required by them to ensure real and reactive
power requirements are met in a world of distributed energy resources.
Microgrids and individual customers are also able to offer different ancillary
services including spinning reserve, frequency regulations, voltage control,
and demand response. Through blockchain, the distributed system operator is
granted access to consumer data like building management systems. Using price
as a proxy, the DSO manages energy use, load balancing, and demand response at
negotiated rates. Blockchain-based Exergy solution are developed for DSO and
microgrids to securely share their supply and demand data with each other and
coordinate exchange of ancillary services and associated value transactions.

####  2.5.4 Use Case 4: Electric Vehicle smart charging

Number of electric vehicle (EV) on roads is exponentially increasing every
year, so their adoption is accelerating rapidly. In 2016 the number of EVs
reached one million for the first time; In ealry 2018, there were more than 2
million EVs, and their number is forecasted to be 40 to 70 million in 2025.
With an average power consumption of 3 MWh per EV per year, these new cars
will consume the output of 100 new 400-MW power plants every year. It will be
very important for grid management where, when, and how drivers charge their
EVs . Today, in the US alone, that market is $250 million. Globally, by 2025,
it will reach $25 billion. When a charging station –public or private– or an
electric vehicle has a surplus of energy, it is made available for purchase on
the local network. Consumers can set budgets and be alerted to the
availability via mobile app.

Blockchain-based solutions such as Exergy not only enables EVSEs (EV supply
equipment) –also known as EV charging stations– and EVs to share their parking
availability and their charging demand with each other to be matched more
efficiently, but also it enables DSOs to be aware of where charging events
will take place and how they would affect the operation of the distribution
system. All data and value transactions can be securely taken placed through
blockchain without any need for intermediaries.

##  3 Exergy Competitive Advantages in Electric Power Grids

Employing blockchain in electric power grids is proved to be very valuable. As
detailed above, Exergy is a blockchain-based solution developed by LO3 Energy
to realize data and value transactions between supply and demand in electric
power grids. In all 4 use cases which LO3 Energy team consider to expand their
business, Exergy is used as a solution to build trust between demand and
supply parties to securely share their availability and demand data of
different services without any need for regulating intermediaries. Blockchain
technology is also used to record value transactions between these parties as
an exchange for service provided by supply to demand side. Exergy uses XRG
tokens to monetize these transactions. Through these solutions, LO3 Energy has
offered several technical advantages to electric power grids in different
levels.

Further, adoption of blockchain in operation of electric power grids is also
rare. There are few firms actively working in this business. Use cases defined
by these firms are rather new and have not been completely implemented yet.
LO3 Energy team has already implemented one of their use cases in Brooklyn
Microgrid project in new York, as the first peer-to-peer trading pilot project
in history, which keeps them some steps ahead of the other firms competing
with them.

The complexity of the blockchin technology makes its adoption in electric
power systems hard to imitate. Blockchain technology involves a very
complicated mathematical background and data management algorithms which
requires high level of knowledge and expertise. Thus it is very difficult for
new firms to enter this market without investing time, energy, and assets.

The main competitors of startups like LO3 Energy are distribution system
operators (DSOs). However, current operation procedures adopted by DSOs are
well established and are used for decades, and development and application of
blockchain is hard to substitute by them because (1) utilities are normally
reluctant to significant changes in their operation procedures until the
modifications are well proved and tested and (2) blockchain technology will
likely threaten or even end their authorities over their network and
customers’ data. This fact, on the other hand, makes it difficult and costly
for startups like LO3 Energy to adopt blockchain technologies when it comes to
the use cases 2-3 where DSO is one of the involved parties.

##  4 Conclusion

In this report, we have studied impacts of blockchain technologies on electric
power grids, with a particular focus on LO3 Energy as one of the firms
developing blockchain solutions for energy sector. LO3 Energy has developed a
technology called Exergy to implement blockchain in distribution power grids.
Exergy includes both data and financial transaction management systems via
blockchain for several use cases including peer-to-peer energy sharing,
microgrid management, DSO services, and EV charging management. They have one
active project in Brooklyn, New York, where prosumers who own rooftop solar
PVs share their excess energy with other consumers in the grid. Benefits of
Exergy in these use cases are comprehensively discussed in the report.

There are two major concerns associated with blockchain solutions in power
industry which lead to the following two recommendations:

  1. 1.

Although distributed nature of blockchain makes it extremely secure, it also
mandates all parties in the network to invest on creating database on their
nodes. That is, the cost associated with database is now multiplied by the
number of parties, which makes this technology extremely costly. Right now, in
pilot projects like Brooklyn Microgrid, the solution looks viable because of
the limited number of active prosumers, but its adoption to larger grids with
higher number of parties would be very expensive. Thus, a major improvements
in technology of computer memories is needed to reduce implementation costs of
such distributed solutions.

  2. 2.

Consumers and prosumers sound very interested in adopting these technologies
in power industry since they resolve their privacy and economic concerns very
well. On the other hand, such technologies significantly reduce the authority
of the utilities or DSOs on distribution power grids. In addition, to maintain
the minimum reliability needed in distribution systems, DSOs always want to
make sure new solutions are completely compatible with their current
procedures and technologies before they start adopting them. These concerns
make DSOs reluctant against these evaluations on the grid. Startups such as
LO3 Energy need to engage DSOs and establish a full cooperation with them in
their technology development process. When DSOs are parts of the business, the
new technologies will be more effective and practical.

Figure 1: Percentage of blockchain startups operating in each industry sector.

Figure 2: Number of Employee currently working in LO3 Energy.

Parameters/Use Case |  1: Peer-to-Peer Energy |  2: Microgrid |  3: Ancillary Services for DSOs, e.g. EPB |  4: Electric Vehicle Smart Charging
---|---|---|---|---
Parties |  Supply |  Prosumer |  Microgrid 1 |  All Microgrids |  EVSEs (EV Chargers)
Demand |  Consumers |  Microgrid 2 |  DSO |  EV
Translated Data via Blockchain |  Supply |  Excess Energy/Price |  Excess Energy/Price |  Availability to Provide Service + Service Price |  Parking Availability and Maximum Power Rate + Desired Price
Demand |  Power Demand/Budget |  Power Demand/Budget |  Need for Ancillary Services + Budget |  Charging/Parking Demand + Budget
Other |  N/A |  Network Constraint by DSO to make sure transaction is feasible |  Network Constraint by DSO to make sure transaction is feasible |  N/A
Transacted Service through Blockchain |  Excess energy of prosumer supplies consumers’ demand |  Excess energy from MG1 to MG2 demand. DSO checks feasibility of power exchange |  Ancillary services INCLUDING reserve, frequency and voltage regulation, demand side management, and demand response |  EV Charging/Parking
Transacted Value through Blockchain |  XRG |  XRG |  XRG |  XRG

Table 1: Summary of Use Cases of Blockchain-based Exergy, Developed by LO3
Energy.

## References

  * Aitzhan Svetinovic (2018) aitzhan2018securityAitzhan, NZ. Svetinovic, D.  2018\.  Security and privacy in decentralized energy trading through multi-signatures, blockchain and anonymous messaging streams Security and privacy in decentralized energy trading through multi-signatures, blockchain and anonymous messaging streams.  IEEE Transactions on Dependable and Secure Computing155840–852.
  * Beck . (2016) beck2016blockchainBeck, R., Czepluch, JS., Lollike, N. Malone, S.  2016\.  Blockchain-the Gateway to Trust-Free Cryptographic Transactions. Blockchain-the gateway to trust-free cryptographic transactions.  ECIS Ecis ( ResearchPaper153).
  * Deign (2017) Deign2017FirmsDeign, J.  2017\.  15 Firms Leading the Way on Energy Blockchain. 15 firms leading the way on energy blockchain.  https://www.greentechmedia.com/articles/read/leading-energy-blockchain-firmsgs.AXquYS8.  Accessed: 2018-10-21
  * Eason (2014) eason2014informationEason, KD.  2014\.  Information technology and organisational change Information technology and organisational change.  CRC Press.
  * Eyal (2017) eyal2017blockchainEyal, I.  2017\.  Blockchain technology: Transforming libertarian cryptocurrency dreams to finance and banking realities Blockchain technology: Transforming libertarian cryptocurrency dreams to finance and banking realities.  Computer50938–49.
  * Friedlmaier . (2017) friedlmaier2017disruptingFriedlmaier, M., Tumasjan, A. Welpe, IM.  2017\.  Disrupting industries with blockchain: The industry, venture capital funding, and regional distribution of blockchain ventures Disrupting industries with blockchain: The industry, venture capital funding, and regional distribution of blockchain ventures.
  * Huckle . (2016) huckle2016internetHuckle, S., Bhattacharya, R., White, M. Beloff, N.  2016\.  Internet of things, blockchain and shared economy applications Internet of things, blockchain and shared economy applications.  Procedia computer science98461–466.
  * Huh . (2017) huh2017managingHuh, S., Cho, S. Kim, S.  2017\.  Managing IoT devices using blockchain platform Managing iot devices using blockchain platform.  Advanced Communication Technology (ICACT), 2017 19th International Conference on Advanced communication technology (icact), 2017 19th international conference on ( 464–467).
  * Iansiti Lakhani (2017) iansiti2017truthIansiti, M. Lakhani, KR.  2017\.  The truth about blockchain The truth about blockchain.  Harvard Business Review951118–127.
  * Kim . (2018) kim2018studyKim, G., Park, J. Ryou, J.  2018\.  A Study on Utilization of Blockchain for Electricity Trading in Microgrid A study on utilization of blockchain for electricity trading in microgrid.  Big Data and Smart Computing (BigComp), 2018 IEEE International Conference on Big data and smart computing (bigcomp), 2018 ieee international conference on ( 743–746).
  * LO3-Energy (20171) LO3Tech2017LO3-Energy.  2017112\.  Building a robust value mechanism to facilitate transactive energy Building a robust value mechanism to facilitate transactive energy .
  * LO3-Energy (20172) LO3ExeSum2017LO3-Energy.  2017212\.  Executive Summary Executive Summary .
  * LO3-Energy (20173) LO3Business2017LO3-Energy.  2017312\.  Introduction to Exergy Introduction to Exergy .
  * Mengelkamp, Gärttner . (2018) mengelkamp2018designingMengelkamp, E., Gärttner, J., Rock, K., Kessler, S., Orsini, L. Weinhardt, C.  2018\.  Designing microgrid energy markets: A case study: The Brooklyn Microgrid Designing microgrid energy markets: A case study: The brooklyn microgrid.  Applied Energy210870–880.
  * Mengelkamp, Notheisen . (2018) mengelkamp2018blockchainMengelkamp, E., Notheisen, B., Beer, C., Dauer, D. Weinhardt, C.  2018\.  A blockchain-based smart grid: towards sustainable local energy markets A blockchain-based smart grid: towards sustainable local energy markets.  Computer Science-Research and Development331-2207–214.
  * Mettler (2016) mettler2016blockchainMettler, M.  2016\.  Blockchain technology in healthcare: The revolution starts here Blockchain technology in healthcare: The revolution starts here.  e-Health Networking, Applications and Services (Healthcom), 2016 IEEE 18th International Conference on e-health networking, applications and services (healthcom), 2016 ieee 18th international conference on ( 1–3).
  * Muzzy (2018) Muzzy2018BlockchainMuzzy, E.  2018\.  Blockchain and The Energy Industry. Blockchain and the energy industry.  https://media.consensys.net/the-state-of-energy-blockchain-37268e053bbd.  Accessed: 2018-11-01
  * Noor . (2018) noor2018energyNoor, S., Yang, W., Guo, M., van Dam, KH. Wang, X.  2018\.  Energy Demand Side Management within micro-grid networks enhanced by blockchain Energy demand side management within micro-grid networks enhanced by blockchain.  Applied energy2281385–1398.
  * Peterson . (2016) peterson2016blockchainPeterson, K., Deeduvanu, R., Kanjamala, P. Boles, K.  2016\.  A blockchain-based approach to health information exchange networks A blockchain-based approach to health information exchange networks.  Proc. NIST Workshop Blockchain Healthcare Proc. nist workshop blockchain healthcare ( 1, 1–10).
  * Singhal . (2018) singhal2018blockchainSinghal, B., Dhameja, G. Panda, PS.  2018\.  How blockchain works How blockchain works.  Beginning Blockchain Beginning blockchain ( 31–148).  Springer.
  * Tapscott Tapscott (2017) tapscott2017blockchainTapscott, A. Tapscott, D.  2017\.  How blockchain is changing finance How blockchain is changing finance.  Harvard Business Review1.
  * Yuan Wang (2016) yuan2016towardsYuan, Y. Wang, FY.  2016\.  Towards blockchain-based intelligent transportation systems Towards blockchain-based intelligent transportation systems.  Intelligent Transportation Systems (ITSC), 2016 IEEE 19th International Conference on Intelligent transportation systems (itsc), 2016 ieee 19th international conference on ( 2663–2668).

##  5 Attachment: LO3 Energy Background

LO3 Energy, founded 2012 in Brooklyn, NY, is developing blockchain based
innovations to revolutionize how energy can be generated, stored, bought, sold
and used, all at the local level. Over the last two years, the LO3 Energy team
has delivered the Brooklyn Microgrid and the world’s first ever energy
blockchain transaction in April 2016. The team consists of a founder and CEO,
a co-founder, a senior VP, a vice president, a product owner, 6 directors, a
developer, 5 senior engineer, 7 engineers, and a cloud architect Figure 2. The
team has developed a unique knowledge base of integrating blockchain with
physical energy generation and management assets in a regulated
environment.Through blockchain technology and their own innovative solutions,
they have developed Exergy, a permissioned data platform that creates
localized energy marketplaces for transacting energy across existing grid
infrastructure. they are just beginning to uncover the potential of the Exergy
platform to influence the energy model of the future, and already the
possibilities seem endless.


figure table

#  leave a trace – A People Tracking System Meets Anomaly Detection

Dominik Rueß  Humboldt-Universität zu Berlin, Institut für Informatik, Unter
den Linden 6, 10099 Berlin, Germany  Konstantinos Amplianitis  Humboldt-
Universität zu Berlin, Institut für Informatik, Unter den Linden 6, 10099
Berlin, Germany  Niklas Deckers  Humboldt-Universität zu Berlin, Institut für
Informatik, Unter den Linden 6, 10099 Berlin, Germany  Michele Adduci
Humboldt-Universität zu Berlin, Institut für Informatik, Unter den Linden 6,
10099 Berlin, Germany  Kristian Manthey  German Aerospace Center,
Rutherfordstraße 2, 12489 Berlin, Germany  Ralf Reulke  Humboldt-Universität
zu Berlin, Institut für Informatik, Unter den Linden 6, 10099 Berlin, Germany

###### Abstract

Video surveillance always had a negative connotation, among others because of
the loss of privacy and because it may not automatically increase public
safety. If it was able to detect atypical (i.e. dangerous) situations in real
time, autonomously and anonymously, this could change. A prerequisite for this
is a reliable automatic detection of possibly dangerous situations from video
data. This is done classically by object extraction and tracking. From the
derived trajectories, we then want to determine dangerous situations by
detecting atypical trajectories. However, due to ethical considerations it is
better to develop such a system on data without people being threatened or
even harmed, plus with having them know that there is such a tracking system
installed. Another important point is that these situations do not occur very
often in real, public CCTV areas and may be captured properly even less.
In the artistic project leave a trace the tracked objects, people in an atrium
of a institutional building, become actor and thus part of the installation.
Visualisation in real-time allows interaction by these actors, which in turn
creates many atypical interaction situations on which we can develop our
situation detection. The data set has evolved over three years and hence, is
huge.
In this article we describe the tracking system and several approaches for the
detection of atypical trajectories.

###### keywords:

Image Processing, Computer Vision, Arts, Tracking, Machine Vision, Imaging
Systems

Contact Address<EMAIL_ADDRESS>
##  1 Introduction

Leave a trace is an object detection and tracking system that was built on
existing state-of-the-art algorithms and improved for the purpose of tracking
people walking in an atrium of the Charité – Universitätsmedizin Berlin, in
Berlin, Germany. It was launched in early 2014 and has been running every
since. The tracks (trajectories) of one or more people are displayed in real-
time on a large monitor placed in the atrium of the main building. The
visitors can interact with their own track to create distinct imagery. The
tracks will accumulate over time but also slowly fade away to avoid cluttering
of the screen and adding the time component. The system resets itself every
morning as everyday it has its own collection of tracks. A typical output of
the screen may consist of cumulative tracks for the usual walking paths. Every
now and then a visitor may write or draw something, which is – in a sense –
some kind of unusual behaviour.

Apart from the artistic nature of this project, it also provides a large
database of anonymized movement, collected every day – over the years. This
data can be used to develop methods to analyse the movement and to detect
anomalous behaviour, for instance. This is especially true since it has users
react to their own movement being displayed and hence, acting differently to
most other visitors who usually just walk to their rooms and back.

The system works with a CCTV camera placed almost vertical in the 5 floor in
the atrium, to reduce perspective effects. The high data throughput of 15
frames per second, each frame of size 2 mega-pixels, is transmitted via Gig-E
to a server which runs the image processing, tracking, data visualisation and
data storage. The screen has a diagonal of 80 inches and a resolution of 4K
and thus also required a high throughput graphics card and connection.

In this article we will describe the technical and software setup of the
system. The contribution is organized as follows: Firstly, we describe the
artistic goal of this project. Secondly, we will provide insight into the
hardware required to work on the huge amount of input data, as well as to work
interruption free. Thirdly, we will list the methods used to extract and track
the movement of people from the input images. Lastly, we present an evaluation
method to detect anomalies in trajectories.

The Internet address of the project is https://leave-a-
trace.charite.de/leave_a_trace/. It provides an on-line and live visualisation
of the current movement in the atrium. Furthermore, it provides recent daily
data sets which you can use for projects of your own. An example python script
can be used for basic data reading (download here:
https://sourceforge.net/projects/leave-a-trace-tools/). In Figure 1 the
installation and the screen is shown.

Figure 1:  View on the installation of the leave a trace system.

##  2 Related Work

###  2.1 Sensors and Systems

Pedestrian tracking from video stream in urban environment is often used for
safety and security reasons. Multi-camera multi-target tracking is the typical
approach, which is also one of the most active research topics in computer
vision.

In recent years, robust, real-time and model-based tracking techniques have
been developed for rigid and non-rigid moving objects. They enable automated
monitoring and event detection.

In general, there is the following approach: object detection, tracking and
fusion, as well as the interpretation of the derived trajectories into normal
or typical and abnormal or atypical. In principle, the differentiation of
abnormal trajectories is also of interest.

Pedestrian detection can be carried out either by stationary or by moving
cameras (on-board, e.g. Ikoma et al[1] and off-board camera camera, e.g.
Aycard et al[2]). To avoid occlusions and extend the field of view of the
whole camera system, multi-camera systems are used (e.g. see Batista[3],
Berclaz et al[4] or Fuhr and Jung[5]). In addition to classical cameras, which
operate in the visible spectral range pan-chromatically or colorfully in rgb,
NIR (e.g. Kumar[6]) and thermal infrared cameras (e.g. Li et al[7]) are also
used.

Camera calibration is also an important point in the use of multi-camera
systems and cameras with a special imaging geometry (see Ikoma[8] where a
omni-directional camera was used). The aim is to avoid the complex camera
calibration, especially for multi-camera systems (e.g. Varga et al[9] and
Hyodo et al[10]).

The use of alternative sensors and the fusion with cameras or stereo cameras
is also possible. Streubel and Yang[11] reports about fusion of stereo camera
and MIMO-FMCW radar, Ikoma[8] uses a composite sensor of laser range finder
and omni-directional camera.

###  2.2 Detection of Abnormal Behaviour

Berclaz et al[4] introduce a new behavioural model to describe pedestrian
movements. These are capable of discerning movement patterns resulting from
the mixture of different categories of random trajectories. It is also capable
of characterizing atypical individual movements.

Gong[12] presents the results of a trainable stochastic temporal models for
automatic event and behaviour detection. They provide an approach for
modelling and recognizing complex activities with simultaneous movement of
several objects. Dynamic probabilistic graph models are used to model the
temporal relationships between a set of different object-time events.

The paper of Junejo[13] deals with the problem of scene modelling. A scene
model is constructed to distinguish normal and acceptable behaviour from
atypical one. The proposed method is divided into a training phase and a test
phase. During the training phase, the input trajectories are used to identify
different paths or routes. Important discriminating features are then
extracted to learn a dynamic Bayesian network (DBN).

The paper by Makris and Ellis[14] deals with the problem of extracting
frequently used pedestrian paths. Path models are trained from the
accumulation of trajectory data over long periods of time. In particular, the
model can be used to calculate a probabilistic prediction of the position of
the pedestrian ahead of time and to support the recognition of unusual
behaviour.

Reulke et al[15] discussed a trajectory-based recognition algorithm to extend
the common approaches for atypical event detection in multi-object traffic
scenarios. They have searched for path-based types of information (e.g. maps
of velocity patterns, trajectory curvatures, or unpredictable movements). They
also implemented the merging of object data from different cameras with a
multi-target tracking approach. This approach opens up possibilities to
identify and specify traffic objects, their location, speed and other
characteristic object information.

A statistically substantiated model of object trajectories is presented by
Johnson and Hogg[16]. Trajectory data is provided by a tracker based on Active
Shape Models, from which a model of the distribution of typical trajectories
is trained. An approach for identifying atypical events based on the model
described is given.

The article by Zhou et al[17] investigates the problem of detecting abnormal
events by analysing the motion paths in videos. The core of the problem is to
provide a robust and accurate function for measuring the similarities of
trajectory pairs.

Most of the articles only consider individual trajectories. In Reulke[19] an
approach to finding interactions between objects in a scene based on
trajectories has been introduced.

##  3 Goal of the Project

The project is part of an art in architecture installation inside an atrium of
a building of the Charité in Berlin, Germany: the CharitéCrossOver building
(CCO). Tyyne Claudia Pollmann developed a concept of a movement visualisation
for this atrium. Persons’ walking paths would be represented in real-time on a
large screen, in different colors for each day: The track color of a day
becomes the background color of the next day. For each week, a new random
color collection is selected. The line width represents the day of the week,
it increases from thin lines on Mondays to very thick lines on Sundays. Tracks
will disappear with time to be able to recognise recent activities. People
moving in the atrium are the originators of the traces and thus the essential
part of the art. Every day, apart from the usual tracks being walked,
individual traces are being produced, which are recognisable as certain
shapes, symbols or messages. The atrium is frequently used for science
exhibitions, conferences or other types of gatherings, which result in
different and specific patterns due to the spatial installations for the
events. So, the outcome is a variety of different patterns and traces which
form a constantly changing visual information on the screen.

##  4 Hardware Description

The CCTV-Camera is a fast and robust industrial camera with a sensor size of 2
mega-pixel and a high quality lens. We have calibrated this Camera using the
Brown model[18], to correct for distortion and principal point offset. This
model is used frequently in photogrammetric applications. It does correct
distorted image coordinates for barrel, pincushion and trapezoidal errors.
This allows for a much more accurate map of the image plane to the ground
plane and hence, a more accurate tracking of objects. A high position of the
camera reduces the effects of perspective projection, which will influence
object positions on the ground plane mapping. The camera is connected to the
computation server by an Gigabit-Ethernet connection, such that we could
employ the GigE-Vision protocol for the large data throughput.

For the computation unit we chose server components, such that the system will
run with as few interruptions and failures as possible. The most important
system parts are an Intel Xeon E5 3.4GHz CPU with 8 virtual Cores, 16GB RAM
and a NVIDIA GeForce GTX 670 graphics card, the latter for both, displaying in
4K and running image processing algorithms in parallel. An uninterrupted power
supply will secure the system from monthly routine power cutoffs. The
operating system is Debian and it allows for automation of daily routines,
including re-start, emptying system cache, data backup, video generation, etc.

Figure 2 shows the different components in a block diagram.

The above system has already exceeded the budget and hence it was not possible
to install more cameras to improve distinguishing persons from the background
– e.g. by stereo methods.

##  5 Image Processing and Tracking

The people tracking system works similar to the methods described in Reulke et
al and Rueß et al[15, 19, 20], however it was altered and improved to be able
to track in an indoor environment prone to changing lighting conditions, a
high frame rate and large image size from only one camera. Also it was
optimized to tracking people.

The image processing of up to 15 frames per second, of which each frame has 2
mega-pixels, is a very challenging task. We have implemented a chain of tools
which ultimately result in the tracks visualising the people’s movement. The
goal was to be as exact and as fast as possible, this will always result in
compromises regarding the resolutions and image parts we used.

Wherever possible we preferred the GPU methods of the computer vision library
OpenCV over the CPU ones. At the same time, whenever we encountered data
parallelism in CPU methods, we have all 8 cores work on that particular task.

The steps of the proposed framework are given below:

Figure 2:  Block diagram of the system with the interaction of the different
components.

###  5.1 Pre-Processing

First of all, it was important to introduce some plausibility checks. For
instance, the image may be too dark or too bright due to fast changes in the
illumination conditions. In this case we have the tracking stop for some
frames. As mentioned above, we needed to detect sunlight areas. Connected
areas with enough saturated pixels will be added to a blacklist mask. These
areas will not be considered in the further object extraction.

###  5.2 Object Extraction

Object detection was performed using a adapted background estimation approach.
The reason for this is because the background would sometimes undergo
significant changes e.g., an event in the atrium. Sun reflection or cloud
shadows were also taken into account for modelling the background.

The well-known open source OpenCV library provides a Gaussian Mixture-based
Model (GMM)[21] implementation, which is also available for GPUs. The
advantage of this approach is that it can remove instant shadows due to the
manually-defined number of frames that it requires to build the background.
For example, for a person appearing in the scene for 5 seconds and an update
of the background every 10 seconds, the person’s shadow will not become part
of the background.

Next step is the extraction of active blobs satisfying some criteria (not too
thin, too large or too small). The barycentre of the blobs serve as object
coordinates, which are later on undistorted and projected to ground floor
coordinates.

All of this is done in planar space, by projecting the image coordinates onto
the ground plane.

###  5.3 Object update

Before and after solving the assignment problem, it is necessary to reset the
detection and tracking system. For instance, check old, likely dead tracks,
even if they are within the usually active region. Also, if a new track would
be initiated but there is already a recent nearby track, we try to connect
these two. Sometimes, if a group of people splits within the active region,
new tracks will be initiated. We try to add a track history for this new track
from a recent and nearby older track. Again, some plausibility checks are
necessary: For instance, some tracks have too large jumps.

For assigning blobs to existing tracks we use a Kalman filter to predict
tracks, however the prediction is not always accurate, especially in the
initialisation stage but also when the moving person turns abruptly, for
instance. We added the OpenCV optical flow method[22] for an independent
prediction of the object. This is implemented for the GPU but is not fast
enough for the 2MP image. Therefore a scaled down version of this algorithm
was developed.

The solution of the assignment problem is purely based on the two predicted
positions. Due to the filtering of the blobs there are not too many objects
left, so we can use the Hungarian algorithm[23, 24] to find the globally most
plausible matching.

For robustness’ sake not every detection is used in the matching. New
(possibly unmatched) detections will have to accumulate over a couple of
frames to become a proper track. A filter also removes non-plausible
detections, like not within a mask, masked out by saturated (or dark) pixels,
out of boundary and too extreme object size.

###  5.4 Data Preparation

The data preparation turns out to be an expensive task too. Consider drawing a
track which consists of many line segments: For every corner a joint needs to
be computed. Then, the drawing is not opaque, see also Figure 3. All of this
needs to be done in 4K/UHD resolution and with many and possibly long tracks,
being repainted on every frame with different alpha.

There are more steps for data preparation, once a second the web-server will
obtain a new rendered and downscaled image. A higher resolution image is saved
at larger intervals, also provided for downloading. Finally, the data XML file
will be updated quite frequently to not lose too much data in case of a system
failure.

##  6 Tracking System Evaluation

Figure 3 provides some exemplary outputs for different days. The different
foreground, background colors and line widths are part of the artistic
concept.

|
---|---
Figure 3:  Exemplary (artistic) output of two different days. You can see an
accumulation of tracks for typical walking paths. Note how the colors and line
widths are different on a per-day basis. Refer to the main text for more
information.

The tracking system works with a throughput of 12 frames per second, on
average, each frame having a size of 2 mega-pixels. It is able to track an
arbitrary number of people which has been proven at days with conferences
taking place in that atrium. It will track almost all of the people and other
objects like cleaning machines etc.

We have encountered the following issues: Firstly, due to perspective and the
swinging motion behaviour of humans, the tracks have a slight wobble in them,
roughly to the extent of up to a third of a person size (viewed from above).
See section 7 for how this issue is addressed in the evaluation of this data.

Secondly, the atrium is prone to sunlight changes, since they rays reflect
from the walls and ultimately cast areas of bright light onto the floor. This
light is so much brighter than the surroundings that we could only temporarily
block these areas from tracking, wherever a collection of saturated pixels
were found. The camera sensor does in fact have a dynamic range of 12
significant bits but that was just not enough.

Lastly, since the atrium is in some building within the Charité, people tend
to wear bright, white coats more often. Thus, there are some issues with
loosing track of people more often. This is due to the very bright floor tiles
which are not very distinct from the cloak’s white color. Again, the dynamic
range is still not high enough to distinguish between these types of cloak and
the floor.

##  7 Data Evaluation – Anomaly Detection

###  7.1 Justification

In the above sections we have described how we obtained a top-down view of the
scene with 2D trajectories of each person. An automatic image analysis with
the aim of recognising atypical trajectories may be applied, within leave a
trace these are desired as a creative factor and determine the meaning of the
installation. Image analysis frequently serves the recognition of atypical
events in public space with the aid of optical sensors and are frequently
correlated with hazardous situations. Atypical events can be extrapolated from
untypical motion sequences. To this aim modern camera technology is used to
(decentralized) capture situations, which are then centrally reconstructed
into an overall situation and finally analyzed using intelligent-learning
procedures. Masking by infrastructure and other participants is problematic
here. The selection (segmentation) of individual people or particular objects
is complicated and sometimes even impossible. It has become apparent that
neither algorithms nor monitoring equipment (e.g. stereo cameras) have reached
adequate levels to be able to solve such problems reliably. Nevertheless it
must be said that bases for this were established within this project and
realized prototypically. In this way movements can be detected, segmented from
the background and monitored.

Figure 6 shows two more examples. The corresponding values are provided in
Table 1.

We pursued two approaches in order to attempt an evaluation. Figure 4 shows an
example of trajectories recorded within a single day (left) and an extracted
trajectory as an example.

ID | nPoints | dFit | dist | cRect | cMain | Figure
---|---|---|---|---|---|---
4 | 178 | 11.2 | 2276 | 4589 | 52.9 |  Figure 4 right
53 | 2590 | 342.7 | 26933 | 59978 | 1.95 |  Figure 5 right
488 | 1129 | 160.1 | 5788 | 3305 | 0.99 |  Figure 6 left
541 | 923 | 292.1 | 7558 | 7093 | 1.34 |  Figure 6 right
Table 1: Parameters for normal (ID 4) and atypical trajectories.

###  7.2 First Approach

A categorisation can be done with the aid of specific properties such as
length, duration or direction of a trajectory. Normal or atypical trajectories
can be extrapolated from these features and statistical analyses. A first
obvious approach is based on the following criteria: Normal trajectories are
the results of direct routes between the entrance door and the doors of
different building complexes. An evident criterion is the deviation of the
trajectory from the linearity or other smooth curve, which can be described by
a polynomial of higher order polynomial (see Figure 4 right).

Based on this, the following criteria are also used for the detection of
abnormal objects (see Figure 5): Number of points (nPoints), Deviation from
the linear fit (dFit), Distance travelled (dist), Circumference of the figure
relative to a horizontal rectangle (cRect) and Circumference of the figure
relative to a main axis (cMain).

The leave a trace project provides interaction with the system to passersby
via a screen in the atrium. Such interactions are expressed by special forms
that differ from straight-line movements. For example, a user can write words
or draw something artistic. Such a movement pattern is shown in Figure 6.

Figure 4: Accumulated tracks from 02-04-2014 (left), extracted normal
trajectory (right).

Figure 5: Atypical tracks (left), collection of atypical trajectory (right).

###  7.3 Machine Learning approach for anomaly detection

Another anomaly detection method was developed on the basis of machine
learning. This unsupervised learning method implements a dynamic training set,
particularly by using a ring buffer storing trajectory equivalents, in order
to provide up-to-date anomaly detection in real time on our data set. This
challenge is created by the high variety of events (exhibitions, conferences
etc.) that are recorded and have to be handled dynamically. Changing or even
just slightly adjusting the training set would require methods like in Johnson
and Hogg[16] to trigger a new training process, resulting in massive
computation power problems at surveillance applications. The same problem
applies to the traditional method of manually selecting regions of interests
(ROIs) in the camera or top-down view.

Figure 6: Atypical tracks (left), collection of atypical trajectory (right).

Given this dynamic training set, classifying every trajectory as normal or
atypical is performed. We define a measure of normality of single trajectories
in relation to the training data. Using a threshold the final classification
as normal or atypical can be performed. This method allows a real-time
classification and even regression for these trajectories that can be used for
security applications.

All of the trajectory points were combined in time intervals of 0.5 seconds
(trajectory steps). This reduces the amount of data used in the calculation
and provides a uniform data quality.

For defining the measure of normality a 4-dimensional so called normality
array is defined whose first two dimensions represent the 2D coordinates and
whose last two dimensions represent the velocity of the observed persons with
its x and y dimension. Each trajectory step can be assigned to a position in
this 4-dimensional space.

Every trajectory step in the training data set will increase the value of this
array at its corresponding position, increasing the measure of normality of
this or a similar step.

The resolution of the 4-dimensional array may be low compared to the original
raw data: In our application a (10x10x5x5) size was sufficient. Using this
array we are still able to differentiate between 2500 distinct trajectory
steps and may calculate the results for steps in between. This requires a
transformation from the trajectory space to the normality array space.

In order to apply a trajectory step at its intermediate position in the
4-dimensional array we calculate a Gaussian kernel with its centre at the
step’s position. The radial basis function kernel is commonly used in machine
learning, mainly for support vector machines [25]. In this application it can
be described as

$K_{t}(p)=\exp{\left(-\sum_{dim=1}^{4}\frac{(t_{dim}-p_{dim})^{2}}{\sigma_{dim}^{2}}\right)},$
(1)

where $t$ is the 4-dimensional trajectory representation and $p$ is the
normality array position. We received good results using (1,1,0.5,0.5) sigma
values. Using a kernel instead of a single position respects the differences
that exist even between similar movements.

The kernel is added to the 4-dimensional normality array after multiplying it
with a weight that is calculated from the current step’s velocity. This
compensates the stronger influence of very slow movements on the normality
array due to a longer time span.

After the normality array has been initialized using the dynamic training data
set, the measure of normality of a single step can be calculated as the
average of the surrounding array entries weighted with the reciprocal of the
distance to these surrounding positions. The measure of normality for
trajectory $t$ can therefore be described as

$n(t)=\frac{1}{|P_{t}|}\sum_{p\in P_{t}}\frac{N(p)}{\left\|t-p\right\|},$ (2)

where $P_{t}$ represents the set of the 4-dimensional integer values that
surround $t$ (with cardinality $|P_{t}|$) and $N(p)$ describes the normality
array value at $p$. The normality value of a trajectory can be defined as the
average of the normality values of its steps. This defines rare trajectories
as atypical while rarity is defined by location and velocity, which can be
useful for security and safety applications.

Unloading a trajectory from the normality array in terms of the ring buffer
method mentioned above may be performed by subtracting the kernels of its
trajectory steps which may be stored in the ring buffer instead of the
trajectories respectively.

This method can be executed in real time and requires low computation power
compared to other methods used for similar purposes. Another advantage is that
the fault tolerance of the method can be matched with the trajectory
generation system’s specifications (see wobble problem in section 6) by
adjusting the normality array resolution and kernel size and sigma.

Results can be seen in Figure 7.

In order to perform a final classification the required threshold may be
derived by calculating the maximum normality of the most atypical 10% of the
trajectories (or another fixed percentage).

Figure 8 shows a histogram of trajectory normality values of an everyday
situation. Because of the nature of normal trajectories they have a normality
similar to multiple other trajectories’ normality values. This results in
higher influence on the histogram which typically leads to a gap between
atypical and normal trajectories’ values. Maximizing a combination of a
histogram’s gap descriptor and a function with a peak at the fixed percentage
value mentioned above will result in an automatic detection for such
classification thresholds.

Figure 7: All tracks, atypical trajectory are in red. Normal (left) and conference situation (right). |
---|---
(a) | (b)
|
(c) | (d)
Figure 8:  (a) Trajectories of everyday scenario with normality depicted by
color as in Figure 7. It contains normal and atypical trajectories. (b)
Histogram of trajectories’ normality values. Note the gap at 0.14. (c)
Trajectories with a normality below 0.14. They can be identified as atypical.
(d) Trajectories with a normality between 0.14 and 0.3. The result contains no
severely atypical trajectories.

##  8 Conclusion

We have presented a people tracking system, used for an art in architecture
project within an atrium of the Charité in Berlin, Germany. It will let people
interact with their own tracks and thus produce individual, artistic results.
The visual results are generally different from day to day, which is the
artistic concept of this project.

For this work we had the advantage of having a huge data set at hand. It has
been running 9 hours a day, continuously for the last 3 years and has not
produced a system failure yet. The data can be downloaded by everyone, from
the Internet-address mentioned in the introduction, which makes this an
important contribution to the field of trajectory research. We have also
published a script which can open and read the data, again the link for this
can be found in the introduction. This huge data set makes this work very
interesting, since it contains many unusual events produced by its users as
well as varying scenarios. Also, its shear size forced us to implement robust
algorithms which can handle the variety in the appearance of people, objects
and the different events held at this atrium.

The tracking was implemented and optimized for an indoor environment, for
difficult lighting situations due to sun reflections and quickly changing
illumination conditions. It works in real-time with at least 12 frames per
second, with each frame having a size of 2 mega-pixels. The system’s hardware
consists of one camera placed high above the atrium and a computation unit
with up to 8 cores and a fast graphics card. This poses a difficult problem,
in future projects it might be easier to save money on other hardware and
introduce more sensors, like a second camera. This would allow for more
precise tracking, even of persons who wear a white coat which is pretty much
the color of the background.

In the future the system can be improved by more robust object detection and
better group handling (clustering). Since many applications will use only one
sensor or camera, the focus will likely stay within the mono-camera
applications.

In this paper we proved, that machine learning approaches should be applied in
order to process this data. The proposed approach is able to handle a variety
of different scenarios because of a dynamic training set, which makes this
approach novel and suitable in the area of trajectory analysis. It may be
extended further using different machine learning methods with the goal of
developing a real-time adapting classification which will be a topic of
further research.

###### Acknowledgements.

We would like to thank Prof. Tyyne Claudia Pollmann and the Charité for making
the track data available to us and the public. Finally, we would also like to
thank Alberto Massa and Marc Uhlig for their contribution to the
implementation of the tracking system and data evaluation process.

## References

  * [1] N. Ikoma, Y. Haraguchi, and H. Hasegawa. On an evaluation of tracking performance improvement by smc-phd filter with intensity image of pedestrians detection over on-board camera using neural network. 2014 World Automation Congress (Wac): Emerging Technologies for a New Paradigm in System of Systems Engineering, 2014.
  * [2] O. Aycard, A. Spalanzani, J. Burlet, C. Fulgenzi, T. D. Vu, D. Raulo, and M. Yguel. Pedestrians tracking using offboard cameras. 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, Vols 1-12, page 513, 2006.
  * [3] J. P. Batista.  Tracking pedestrians under occlusion using multiple cameras. Image Analysis and Recognition, Pt 2, Proceedings, 3212:552–562, 2004.
  * [4] J. Berclaz, F. Fleuret, and P. Fua. Multi-camera tracking and atypical motion detection with behavioral maps. Computer Vision - ECCV 2008, Pt Iii,Proceedings, 5304:112, 2008.
  * [5] G. Fuhr and C. R. Jung. Combining patch matching and detection for robust pedestrian tracking in monocular calibrated cameras. Pattern Recognition Letters, 39:11–20, 2014.
  * [6] K. S. C. Kumar. Phase-edge based approach for pedestrian segmentation using nir camera and tracking for driver assistance. 2013 Ieee Second International Conference on Image Information Processing (ICIIP), pages 214–218, 2013.
  * [7] X. Li, R. Guo, and C. Chen. Robust pedestrian tracking and recognition from flir video: a unified approach via sparse coding. Sensors (Basel), 14(6):11245–59, 2014.
  * [8] N. Ikoma. Multiple pedestrians tracking with composite sensor of laser range finder and omni-directional camera by smc implementation of phd filter. 6th International Conference on Soft Computing and Intelligent Systems, and the 13th International Symposium on Advanced Intelligent Systems, pages 705–710, 2012.
  * [9] D. Varga, T. Sziranyi, A. Kiss, L. Sporas, and L. Havasi. A multi-view pedestrian tracking method in an uncalibrated camera network. 2015 Ieee International Conference on Computer Vision Workshop (ICCVW), pages 184–191, 2015.
  * [10] Y. Hyodo, K. Fujimura, S. Yuasa, T. Naito, and S. Kamijo. Pedestrian tracking through camera network for wide area surveillance. 2008 IEEE International Conference on Systems, Man and Cybernetics (Smc), Vols 1-6, page 656, 2008.
  * [11] R. Streubel and B. Yang. Fusion of stereo camera and mimo-fmcw radar for pedestrian tracking in indoor environments. 2016 19th International Conference on Information Fusion (Fusion), pages 565–572, 2016.
  * [12] S. G. Gong. Towards behaviour recognition based video surveillance. Optics and Photonics for Counterterrorism and Crime Fighting, 5616:1–15, 2004.
  * [13] I. N. Junejo. Using dynamic bayesian network for scene modeling and anomaly detection. Signal Image and Video Processing, 4(1):1–10, 2010.
  * [14] D. Makris and T. Ellis. Path detection in video surveillance. Image and Vision Computing, 20(12):895–903, 2002.
  * [15] R. Reulke, F. Meysel, and S. Bauer. Situation analysis and atypical event detection with multiple cameras and multi-object tracking Robot Vision, Proceedings, 4931:234–247, 2008.
  * [16] Neil Johnson and David Hogg. Learning the distribution of object trajectories for event recognition. Image and Vision Computing, 14(8):609–615, 1996.
  * [17] Y. Zhou, S. Yan, and T. S. Huang. Detecting anomaly in videos from trajectory similarity analysis. In IEEE International Conference on Multimedia and Expo, pages 1087–1090, 2007.
  * [18] Duane C. Brown. Close-range camera calibration. Photogramm. Eng 37.8 (1971): 855-866.
  * [19] R. Reulke, D. Rueß, K. Manthey and A. Luber. Traffic Observation and Situation Assessment. Lecture Notes in Computer Sciences, 7474. Springer Berlin Heidelberg, 2012.
  * [20] D. Rueß, K. Manthey, and R. Reulke. An accurate 3d feature tracking system with wide-baseline stereo smart cameras. Distributed Smart Cameras (ICDSC), 2011 Fifth ACM/IEEE International Conference on. IEEE, 2011.
  * [21] P. KaewTraKulPong and R. Bowden. An improved adaptive background mixture model for real-time tracking with shadow detection. Video-based surveillance systems. Springer US, 2002. 135-144.
  * [22] G. Farnebäck. Two-frame motion estimation based on polynomial expansion. Scandinavian conference on Image analysis. Springer Berlin Heidelberg, 2003.
  * [23] H.W. Kuhn. The Hungarian method for the assignment problem. Naval research logistics quarterly 2.1-2 (1955): 83-97.
  * [24] J. Munkres. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics 5.1 (1957): 32-38.
  * [25] Y.-W. Chang, C.-J. Hsieh, K.-W. Chang, M. Ringgaard and C.J. Lin Training and testing low-degree polynomial data mappings via linear SVM. J. Machine Learning Research 11:1471–1490, 2010