# Resource Allocation for D2D Communications Underlaying a NOMA-Based Cellular
Network

Yijin Pan, Cunhua Pan, Zhaohui Yang, Ming Chen
Y. Pan, Z. Yang and M. Chen are with the National Mobile Communications
Research Laboratory, Southeast University, Nanjing 211111, China.
<EMAIL_ADDRESS>Pan is with the School of
Electronic Engineering and Computer Science, Queen Mary, University of London,
London E1 4NS, UK. Email<EMAIL_ADDRESS>
###### Abstract

This letter investigates the power control and channel assignment problem in
device-to-device (D2D) communications underlaying a non-orthogonal multiple
access (NOMA) cellular network. With the successive interference cancellation
decoding order constraints, our target is to maximize the sum rate of D2D
pairs while guaranteeing the minimum rate requirements of NOMA-based cellular
users. Specifically, the optimal conditions for power control of cellular
users on each subchannel are derived first. Then, based on these results, we
propose a dual-based iterative algorithm to solve the resource allocation
problem. Simulation results validate the superiority of proposed resource
allocation algorithm over the existing orthogonal multiple access scheme.

###### Index Terms:

D2D, NOMA, power control, channel assignment.

##  I Introduction

The device-to-device (D2D) communications have been considered as a promising
way to alleviate the upcoming traffic pressure on core networks. Due to the
short transmission distance of D2D pairs, the spectrum efficiency can be
significantly improved by the spectrum reuse with cellular users (CUs). In
conventional networks, the uplink resources are normally provided for D2D
communications since traffic in downlink is significantly heavier than that in
uplink [1, 2]. However, some uplink applications with high rate requirements
are becoming popular in the future networks such as the Skype video call[3].
Hence, the traffic between uplink and downlink is becoming less asymmetric and
the resource allocation problem for D2D communications underlaying the
downlink celluar network should be studied as well [4, 5, 6].

Apart from D2D communications, non-orthogonal multiple access (NOMA) is
another emerging technology to handle the transmission pressure in the near
future [7]. In a NOMA-based cellular network, multiple CUs are allowed to
share the same subchannel via different power levels, and successive
interference cancellation (SIC) is adopted at the CUs for decoding. In this
way, the NOMA-based cellular network can greatly increase system throughput
and allow massive connectivities. Recently, several approaches have been
proposed to combine the D2D communications with NOMA technology [8, 9]. The
D2D users were grouped through the NOMA way in [8] to achieve better D2D rate
performance, and the channel allocation problem for the NOMA-based D2D groups
is modeled as a Many-to-One matching. Furthermore, the D2D assisted NOMA
scheme was proposed in [9] to enhance system throughput performance. D2D pairs
were merely assumed to transmit on exclusive channels without sharing channels
with CUs in [9], even though frequency reuse between D2D pairs and CUs is
spectrum efficient. However, when D2D pairs reuse spectrum with NOMA-based
CUs, the co-channel interference in SIC decoding will become further
complicated, which may destroy the original SIC decoding order of CUs. To
conquer this issue, one should impose an additional restriction for the power
control and channel assignment of the D2D pairs, which has not been studied in
current literature. This motivates us to reconsider the resource allocation
problem for D2D communications when the D2D pairs share spectrum with the
NOMA-based CUs.

In this letter, we consider the power control and channel assignment for the
D2D pairs underlaying NOMA-based cellular networks with consideration of the
SIC decoding constraints. This scenario is different from that in [8], where
NOMA is implemented in D2D transmissions. Furthermore, since power control is
not considered for either CUs or NOMA-based D2D groups in [8], the approach in
[8] cannot be directly applied to solve our problem. Our target is to maximize
the sum rate of D2D pairs while guaranteeing the minimum rate requirements of
CUs. We derive the optimal conditions for power control of the NOMA-based CUs
first, then propose a dual-based iterative algorithm to solve the resource
allocation problem. Specifically, by adopting the auxiliary variables and
relaxing the binary constraints, the formulated optimization problem is
transformed into a convex one, which can be optimally solved by the dual
method. Finally, simulation results show the significant D2D sum rate gains of
proposed algorithm over the conventional orthogonal multiple access (OMA)
scheme.

##  II System Model and Problem Formulation

Consider a downlink NOMA-based cellular network, where base station (BS)
serves CUs through $N$ subchannels (SCs). By adopting NOMA, $M$ CUs are
multiplexed in the same SC by splitting them in the power domain111It is
assumed that CUs served by the same SC are already scheduled. The CU grouping
issues (see e.g. [7]) are generally the task of the upper-layer, which are
beyond the scope of this paper.. That is to say, the total number of CUs is
$NM$. Meanwhile, there are $K(K\leq N)$ underlaid D2D pairs randomly
distributed in the cell.

Denote $\mathcal{K}=\\{1,\cdots,K\\}$ and $\mathcal{N}=\\{1,\cdots,N\\}$ as
the sets of D2D pairs and SCs, respectively. The superposition symbol
transmitted by BS on SC $n$ to CUs is

$x^{n}=\sum_{i=1}^{M}\sqrt{p^{n}_{i}}s^{n}_{i},$ (1)

where $s^{n}_{i}$ and $p^{n}_{i}$ are the transmit signal and transmit power
for CU $i$ on SC $n$, respectively.

To implement NOMA, BS needs to inform each CU of the SIC decoding order, so
that strong CUs can decode and remove the signal from weak CUs. In current
work, it is generally assumed that the SIC decoding order follows the
increasing order of channel gains [10, 11]. Let $h^{n}_{i}$ denote the channel
from BS to CU $i$ on $n$-th SC222Similar as [10, 11], the receivers are
assumed to have the perfect channel state information by channel feedback..
When
$|h^{n}_{1}|\\!\leq|h^{n}_{2}|\\!\leq\\!\\!\cdots\\!\\!\leq\\!|h^{n}_{M}|$, CU
$i$ can successfully decode and remove the interference from CU $j,\forall
j<i$. However, in our work, underlaid D2D pairs also contribute to the co-
channel interference, which affects the NOMA decoding order.

In this case, the received SINR at CU $i$ to decode the signal $s_{j},j<i$, on
SC $n$ is

$\text{SINR}^{n}_{i\to
j}=\frac{p^{n}_{j}|h^{n}_{i}|^{2}}{|h^{n}_{i}|^{2}\sum_{t=j+1}^{M}p^{n}_{t}+\sum_{k=1}^{K}\alpha^{n}_{k}q^{n}_{k}|h^{n}_{k,i}|^{2}+\sigma^{2}},$
(2)

where the binary variable $\alpha^{n}_{k}$ denotes whether or not SC $n$ is
assigned to D2D pair $k$. The term
$\sum_{k=1}^{K}\alpha^{n}_{k}q^{n}_{k}|h^{n}_{k,i}|^{2}$ represents the co-
channel interference to CU $i$ from the underlaid D2D pairs on SC $n$, where
$q^{n}_{k}$ is the transmit power of D2D pair $k$ and $|h^{n}_{k,i}|$
represents the channel gain from D2D pair $k$ to CU $i$ on SC $n$.
Specifically, when CU $i$ desires to decode the signal of CU $j$ from
superposition symbol $x^{n}$, the interference cancellation is successful if
the CU $i$’s received SINR is larger or equal to CU $j$’s own received SINR.
Therefore, to protect the given SIC decoding order, the following conditions
should be satisfied.

$\frac{\sum_{k=1}^{K}\alpha^{n}_{k}q^{n}_{k}|h^{n}_{k,j}|^{2}+\sigma^{2}}{|h^{n}_{j}|^{2}}\geq\frac{\sum_{k=1}^{K}\alpha^{n}_{k}q^{n}_{k}|h^{n}_{k,{i}}|^{2}+\sigma^{2}}{|h^{n}_{i}|^{2}},$
(3)

for $i,j\in\\{1,\cdots,M\\}\triangleq\mathcal{M}$, $j<i$, and
$n\in\mathcal{N}$. The set $\mathcal{M}$ represents the set of CUs’ index on
each SC. Note that there will be $\frac{M(M-1)}{2}$ constraints for each SC in
the form of (3). To simplify the decoding order constraints, the following
equivalent inequalities can be implied from (3)

$\frac{\sum_{k=1}^{K}\alpha^{n}_{k}q^{n}_{k}|h^{n}_{k,i}|^{2}+\sigma^{2}}{|h^{n}_{i}|^{2}}\geq\frac{\sum_{k=1}^{K}\alpha^{n}_{k}q^{n}_{k}|h^{n}_{k,{i+1}}|^{2}+\sigma^{2}}{|h^{n}_{i+1}|^{2}},$
(4)

for $i\in\mathcal{M}\setminus\\{M\\}$, and $n\in\mathcal{N}$. In this form,
there are only $M-1$ constraints on each SC.

The achievable rate of CU $i$ on SC $n$ in bits/s/Hz is

$R^{n}_{i\to i}=\log_{2}(1+\text{SINR}^{n}_{i\to i}).\vspace{-0.75em}$ (5)

Although the spectrum efficiency can be improved by allowing multiple D2D
pairs reusing the same SC, the design of efficient resource allocation schemes
in this paradigm requires high computation complexity. Moreover, heavy
signaling overhead exchange occurs since channel state information of the
interference channels between different D2D pairs over all SCs should be
estimated. Given theses concerns, we assume that one SC is only allocated to
at most one D2D pair. Consequently, we have the following channel assignment
constraints:

$\displaystyle\sum_{k=1}^{K}\alpha^{n}_{k}\leq
1,\alpha^{n}_{k}\in\\{0,1\\},\forall n\in\mathcal{N},k\in\mathcal{K}.$ (6)

The SINR at the receiver of D2D pair $k$ on SC $n$ is

$\text{SINR}^{n}_{k}=\frac{q^{n}_{k}|g^{n}_{k}|^{2}}{|g^{n}_{k,B}|^{2}\sum_{i=1}^{M}p^{n}_{i}+\sigma^{2}},$
(7)

where $|g^{n}_{k}|$ is the channel gain between the transmitter and receiver
of D2D pair $k$ on SC $n$, and $|g^{n}_{k,B}|$ is the interference channel
gain from BS to the receiver of D2D pair $k$ on SC $n$. In this case, the
achievable rate of D2D pair $k$ on SC $n$ in bits/s/Hz is

$R^{n}_{k}=\log_{2}(1+\text{SINR}^{n}_{k}).$ (8)

Meanwhile, to guarantee the rate fairness among CUs, the minimum rate
requirements for CUs are imposed as

$R^{n}_{i\to i}\geq\gamma_{i}^{n},\forall i\in\mathcal{M},n\in\mathcal{N},$
(9)

where $\gamma_{i}^{n}$ is the rate requirement of CU $i$ on SC $n$. The
transmit power constraints for D2D pairs and BS for CUs are

$\sum_{n=1}^{N}\alpha_{k}^{n}q^{n}_{k}\leq P^{D}_{\max},\forall
k\in\mathcal{K},$ (10) $\sum_{i=1}^{M}p^{n}_{i}\leq P^{C}_{\max},\forall
n\in\mathcal{N}.$ (11)

To maximize the sum rate of D2D pairs, the following optimization problem is
obtained.

$\displaystyle\mathcal{P}1:\mathop{\max}_{\\{p^{n}_{k},\alpha^{n}_{k},q^{n}_{k}\\}}$
$\displaystyle\quad
R_{\text{max}}^{D}=\sum_{k=1}^{K}\sum^{N}_{n=1}\alpha^{n}_{k}R^{n}_{k},$ (12a)
s.t. $\displaystyle\quad(\ref{c0}),(\ref{c1}),(\ref{c2})-(\ref{c4}).$

##  III Power Control and Channel Assignment

To solve the sum rate maximization Problem $\mathcal{P}1$, the optimal
conditions for power control of the NOMA-based CUs on a given SC are first
investigated. Then, we propose a dual-based iterative method to obtain the
power control and channel assignment for D2D pairs.

###  III-A Optimal Power Control for CUs

If SC $n$ is assigned to D2D pair $k$, we first determine the optimal transmit
power conditions for CUs. For simplicity, the superscript $n$ is omitted in
the following analysis of this subsection. To solve the power control problem,
we define

$\xi_{k,i}=\frac{|h_{k,i}|^{2}}{|h_{i}|^{2}},\Delta_{i}=\frac{\sigma^{2}}{|h_{i}|^{2}},\forall
i\in\cal M.$ (13)

It is easy to know that the constraint (9) should hold with equality for the
optimal transmit power of CU $i$ denoted as $p_{i}^{\ast},\forall
i\in\mathcal{M}$[4, 5]. Otherwise, the sum rate of D2D pairs can be further
improved by decreasing $p_{i}^{\ast}$. Setting $(\ref{c2})$ with equality for
CU $M$, we have

$p_{M}^{\ast}=(2^{\gamma_{M}}-1)\left(q_{k}\xi_{k,M}+\Delta_{M}\right).$ (14)

Accordingly, for the CU $i,\forall i\in\mathcal{M}\setminus\\{M\\}$, the
optimal transmit power $p_{i}^{\ast}$ is

$p_{i}^{\ast}=\left(2^{\gamma_{i}}-1\right)\left(q_{k}\xi_{k,i}+\Delta_{i}+\sum_{t=i+1}^{M}p_{t}^{\ast}\right).$
(15)

It is not easy to obtain the explicit expression of $p_{i}^{\ast}$ from (15).
To assist solving this issue, we define $S_{i}=\sum_{t=i}^{M}p_{t}^{\ast}$,
which represents the summation of transmit powers from CU $i$ to CU $M$.
Substituting $S_{i}$ in (15), we have

$S_{i}=(2^{\gamma_{i}}-1)(q_{k}\xi_{k,i}+\Delta_{i})+2^{\gamma_{i}}S_{i+1}.$
(16)

According to the recursive relations, we can obtain that

$S_{i}\\!\\!=\\!\\!\\!\\!\sum_{j=0}^{M-i-1}2^{\sum_{l=0}^{j-1}\gamma_{i+l}}(2^{\gamma_{i+j}}-1)(q_{k}\xi_{k,i+j}\\!+\\!\Delta_{i+j})+2^{\sum_{s=0}^{M-i-1}\gamma_{i+s}}S_{M}.$
(17)

where we define $2^{\sum_{l=0}^{-1}\gamma_{i+l}}=2^{0}=1$. Obviously,
$S_{M}=p_{M}^{\ast}$. Based on (14), (17) is simplified to

$\\!\\!S_{i}=\sum_{j=0}^{M-i}2^{\sum_{l=0}^{j-1}\gamma_{i+l}}(2^{\gamma_{i+j}}-1)(q_{k}\xi_{k,i+j}\\!+\\!\Delta_{i+j}).$
(18)

In addition, the optimal transmit power for CU $i,\forall
i\in\mathcal{M}\setminus\\{M\\}$ is obtained by
$p_{i}^{\ast}=\sum_{t=i}^{M}p_{t}^{\ast}-\sum_{t=i+1}^{M}p_{t}^{\ast}=S_{i}-S_{i+1}$.
By further using (18) and defining $\sum_{l=1}^{0}\gamma_{i+l}=2^{0}=1$, we
have

$p_{i}^{\ast}=(2^{\gamma_{i}}-1)\sum_{j=1}^{M-i}2^{\sum_{l=1}^{j-1}\gamma_{i+l}}(2^{\gamma_{i+j}}-1)(q_{k}\xi_{k,{i+j}}+\Delta_{i+j})+(2^{\gamma_{i}}-1)(q_{k}\xi_{k,{i}}+\Delta_{i}),i\in\mathcal{M}\setminus\\{M\\}.$
(19)

###  III-B D2D Power Control and Channel Assignment

Based on the previous analysis, the transmit powers for CUs are all determined
by the transmit power of the multiplexed D2D pair. When SC $n$ is assigned to
D2D pair $k$, according to (18), the transmit power constraint (11) is
equivalent to

$\sum_{j=0}^{M-1}\Gamma_{j}(q^{n}_{k}\xi^{n}_{k,1+j}\\!+\\!\Delta^{n}_{1+j})\leq
P^{C}_{\max}.$ (20)

where $\Gamma_{j}=2^{\sum_{l=1}^{j}\gamma_{l}}(2^{\gamma_{1+j}}-1)$. Then, the
following inequality holds.

$q_{k}^{n}\leq\frac{P^{C}_{\max}-\sum_{j=0}^{M-1}\Gamma_{j}\Delta^{n}_{1+j}}{\sum_{j=0}^{M-1}\Gamma_{j}\xi_{k,1+j}^{n}}.$
(21)

According to (18), the SIC successful decoding order constraints in (4) can be
rewritten as

$q^{n}_{k}\xi^{n}_{k,i}+\Delta^{n}_{i}\geq
q^{n}_{k}\xi^{n}_{k,i+1}+\Delta^{n}_{i+1},\forall
i\in\mathcal{M}\setminus\\{M\\}.$ (22)

Recall that $\Delta^{n}_{i+1}\leq\Delta^{n}_{i}$ since
$|h^{n}_{i}|\leq|h^{n}_{i+1}|$. Note that if
$\xi^{n}_{k,i}\geq\xi^{n}_{k,i+1}$, (22) is feasible for any non-negative
$q^{n}_{k}$. Hence, the transmit power of D2D pair $k$ on SC $n$ should
satisfy

$q^{n}_{k}\leq\min\limits_{\\{i\in\mathcal{M}\setminus\\{M\\}|\xi^{n}_{k,i}<\xi^{n}_{k,i+1}\\}}\left\\{\frac{\Delta^{n}_{i+1}-\Delta^{n}_{i}}{\xi^{n}_{k,i}-\xi^{n}_{k,i+1}}\right\\}.$
(23)

Remark: According to (23), we find that if $\xi^{n}_{k,i}<\xi^{n}_{k,i+1}$,
i.e.,
$\frac{|h^{n}_{k,i}|^{2}}{|h^{n}_{i}|^{2}}<\frac{|h^{n}_{k,i+1}|^{2}}{|h^{n}_{i+1}|^{2}}$,
one additional transmit power constraint is imposed on the D2D pair to protect
the SIC decoding order of CUs. On the other hand, if the condition
$\xi^{n}_{k,i}\geq\xi^{n}_{k,i+1}$, i.e.,
$\frac{|h^{n}_{k,i}|^{2}}{|h^{n}_{i}|^{2}}\geq\frac{|h^{n}_{k,i+1}|^{2}}{|h^{n}_{i+1}|^{2}}$
holds for all $i\in\mathcal{M}\setminus\\{M\\}$, the SIC decoding order
constraints in (4) are alway satisfied.

Substituting (18) into (8), the achievable rate of D2D pair $k$ on SC $n$ is

$R^{n}_{k}(q^{n}_{k})=\log_{2}\left(1+\frac{d^{n}_{k}q^{n}_{k}}{q^{n}_{k}+e^{n}_{k}}\right),$
(24)

where
$d^{n}_{k}=\frac{|g^{n}_{k}|^{2}}{|g^{n}_{k,B}|^{2}\sum_{j=0}^{M-1}\Gamma_{j}\xi_{j+1}}$,
$e^{n}_{k}=\frac{|g^{n}_{k,B}|^{2}\sum_{j=0}^{M-1}\Gamma_{j}\Delta_{j+1}+\sigma^{2}}{|g^{n}_{k,B}|^{2}\sum_{j=0}^{M-1}\Gamma_{j}\xi_{j+1}}$.
Given the above results, the original Problem $\mathcal{P}1$ is simplified to

$\displaystyle\mathcal{P}2:\mathop{\max}_{\\{\alpha^{n}_{k},q^{n}_{k}\\}}$
$\displaystyle\quad
R_{\text{max}}^{D}=\sum_{k=1}^{K}\sum_{n=1}^{N}\alpha_{k}^{n}R^{n}_{k}(q^{n}_{k}),$
(25a) s.t. $\displaystyle\quad(\ref{c1}),(\ref{c3}),$ (25b)
$\displaystyle\quad 0\leq q^{n}_{k}\leq Q^{n}_{k},\forall
k\in\mathcal{K},n\in\mathcal{N},$ (25c)

where
$Q^{n}_{k}=\min\left\\{\max\left\\{0,\frac{P^{C}_{\max}-\sum_{j=0}^{M-1}\Gamma_{j}\Delta^{n}_{1+j}}{\sum_{j=0}^{M-1}\Gamma_{j}\xi_{k,1+j}^{n}}\right\\},\min\limits_{\\{i\in\mathcal{M}\setminus\\{M\\}|\xi^{n}_{k,i}<\xi^{n}_{k,i+1}\\}}\left\\{\frac{\Delta^{n}_{i+1}-\Delta^{n}_{i}}{\xi^{n}_{k,i}-\xi^{n}_{k,i+1}}\right\\}\right\\}.$

It is easy to see that
$f(q^{n}_{k})=\frac{d^{n}_{k}q^{n}_{k}}{q^{n}_{k}+e^{n}_{k}}$ is concave with
respect to (w.r.t) $q^{n}_{k}$. Consequently, $R^{n}_{k}(q^{n}_{k})$ is
concave w.r.t $q^{n}_{k}$ due to that the logarithmic function is increasing
and concave [12, Page 84]. However, problem $\mathcal{P}2$ is not convex due
to (25a) and (6). By introducing the auxiliary variable
$x^{n}_{k}=\alpha^{n}_{k}q^{n}_{k}$, and temporarily relaxing the integer
constraints for $\\{\alpha^{n}_{k}\\}$, Problem $\mathcal{P}2$ is transformed
into

$\displaystyle\mathcal{P}3:\underset{\underset{x^{n}_{k}\in[0,\alpha_{k}^{n}Q^{n}_{k}]}{\alpha^{n}_{k}\in[0,1]}}{\mathop{\max}}$
$\displaystyle\quad
R_{\text{max}}^{D}(\alpha_{k}^{n},x^{n}_{k})=\sum_{k=1}^{K}\sum_{n=1}^{N}\alpha_{k}^{n}R^{n}_{k}\left(\frac{x^{n}_{k}}{\alpha_{k}^{n}}\right),$
(26a) s.t. $\displaystyle\quad\sum_{n=1}^{N}x^{n}_{k}\leq P^{D}_{\max},\forall
k\in\mathcal{K},$ (26b) $\displaystyle\quad\sum_{k=1}^{K}\alpha^{n}_{k}\leq
1,\forall n\in\mathcal{N}.$ (26c)

It is inferred that $R_{\text{max}}^{D}(\alpha_{k}^{n},x^{n}_{k})$ is concave
w.r.t $(\alpha_{k}^{n},x^{n}_{k})$ within a triangular region due to the
perspective property [4, 13], so that Problem $\mathcal{P}3$ is convex.
Therefore, the optimal solution to Problem $\mathcal{P}3$ can be obtained by
using the standard dual method. The Lagrangian is obtained as

$\mathcal{L}=\sum_{k=1}^{K}\sum_{n=1}^{N}\alpha_{k}^{n}R^{n}_{k}\left(\frac{x^{n}_{k}}{\alpha_{k}^{n}}\right)+\sum_{k=1}^{K}\lambda_{k}\left(P^{D}_{\max}-\sum_{n=1}^{N}x_{k}^{n}\right)+\sum_{n=1}^{N}\beta_{n}\left(1-\sum_{k=1}^{K}\alpha^{n}_{k}\right),$
(27)

where $\\{\lambda_{k}\\}$ and $\\{\beta_{n}\\}$ are the non-negative dual
variables associated with the constraints (26b) and (26c), respectively.
Taking the derivative of $\mathcal{L}$ w.r.t $x_{k}^{n}$ and $\alpha^{n}_{k}$
respectively, we have

$\displaystyle\frac{\partial\mathcal{L}}{\partial
x_{k}^{n}}={R^{n}_{k}}^{\prime}\left(\frac{x^{n}_{k}}{\alpha_{k}^{n}}\right)-\lambda_{k},\quad\frac{\partial\mathcal{L}}{\partial\alpha^{n}_{k}}={R^{n}_{k}}\left(\frac{x^{n}_{k}}{\alpha_{k}^{n}}\right)-\frac{x^{n}_{k}}{\alpha_{k}^{n}}{R^{n}_{k}}^{\prime}\left(\frac{x^{n}_{k}}{\alpha_{k}^{n}}\right)-\beta_{n},$
(28)

where ${R^{n}_{k}}^{\prime}(t)$ is the derivative of $R^{n}_{k}(t)$ w.r.t $t$.
Applying the Karush-Kuhn-Tucker conditions, we can obtain the following
necessary conditions for the optimal solution
$({\alpha_{k}^{n}}^{*},{x_{k}^{n}}^{*})$.

If ${\alpha_{k}^{n}}^{*}=0$, then ${x_{k}^{n}}^{*}=0$, and we have
$\frac{\partial\mathcal{L}}{\partial
x_{k}^{n}}<0,\frac{\partial\mathcal{L}}{\partial\alpha_{k}^{n}}<0$, for all
$\alpha_{k}^{n}\in(0,1]$ and $x_{k}^{n}\in(0,Q_{k}^{n}]$.

If ${\alpha_{k}^{n}}^{*}\neq 0$, we have

$\frac{\partial\mathcal{L}}{\partial
x_{k}^{n}}\left\\{\begin{array}[]{llll}<0,&\text{if }{x_{k}^{n}}^{*}=0\\\
=0,&\text{if }{x_{k}^{n}}^{*}\in(0,Q_{k}^{n})\\\ >0,&\text{if
}{x_{k}^{n}}^{*}=Q_{k}^{n}\end{array}\right.,\quad\frac{\partial\mathcal{L}}{\partial\alpha_{k}^{n}}\left\\{\begin{array}[]{llll}=0,&\text{if
}{\alpha_{k}^{n}}^{*}\in(0,Q_{k}^{n})\\\ >0,&\text{if
}{\alpha_{k}^{n}}^{*}=1.\end{array}\right.$ (29)

When ${x_{k}^{n}}^{*}\in(0,Q_{k}^{n})$, ${x_{k}^{n}}^{*}$ can be obtained by
solving $\frac{\partial\mathcal{L}}{\partial x_{k}^{n}}=0$. Denoting
$t=\frac{{x_{k}^{n}}^{*}}{{\alpha_{k}^{n}}^{*}}$,
$\frac{\partial\mathcal{L}}{\partial x_{k}^{n}}=0$ is equivalent to the
following quadratic equation.

$(d^{n}_{k}+1)t^{2}+(d^{n}_{k}+2)e^{n}_{k}t+(e^{n}_{k})^{2}-\frac{d^{n}_{k}e^{n}_{k}}{\lambda_{k}\ln
2}=0.$ (30)

Note that the discriminant of this quadratic equation is
$\Delta={e^{n}_{k}d^{n}_{k}}^{2}+\frac{4{d^{n}_{k}}^{2}}{\lambda_{k}\ln
2}+\frac{e^{n}_{k}d^{n}_{k}}{\lambda_{k}\ln 2}$, indicating that (30) has two
real roots. According to the quadratic solution formula, we define
$t^{n}_{k}(\lambda_{k})=\frac{-(d^{n}_{k}+2)e^{n}_{k}+\sqrt{\Delta}}{2(d^{n}_{k}+1)}$.
Given that ${x^{n}_{k}}^{*}\in[0,\alpha_{k}^{n}Q^{n}_{k}]$, we can conclude
that

${x_{k}^{n}}^{*}={\alpha_{k}^{n}}^{*}{T_{k}^{n}}^{*},$ (31)

where ${T_{k}^{n}}^{*}=[t^{n}_{k}(\lambda_{k})]^{Q_{k}^{n}}_{0}$, and
$[x]^{a}_{b}=\min\\{\max\\{x,b\\},a\\}$. According to (29), it follows that

${\alpha_{k}^{n}}^{*}=\left\\{\begin{array}[]{llll}1,&\text{if
}H_{k}^{n}>\beta_{n}\\\ 0,&\text{if }H_{k}^{n}<\beta_{n}\end{array}\right.$
(32)

where
$H_{k}^{n}={R^{n}_{k}}\left({T_{k}^{n}}^{*}\right)-{T_{k}^{n}}^{*}{R^{n}_{k}}^{\prime}\left({T_{k}^{n}}^{*}\right)$.
If $H_{k}^{n}$ are all different for $k\in\mathcal{K}$, according to
constraint $(\ref{st_asg})$ and (32), we have

${\alpha_{k^{\prime}}^{n}}^{*}=1,{\alpha_{k}^{n}}^{*}=0,\forall k\neq
k^{\prime},$ (33)

where $k^{\prime}=\arg\underset{k}{\max}H^{n}_{k}$. For SC $n$, only the D2D
pair with the largest $H_{k}^{n}$ should be assigned this SC. Note that the
value of $\lambda_{k}$ can be determined by the sub-gradient method [14]. The
updating procedure of $\lambda_{k}$ in the $(t+1)$-th iteration is

$\lambda_{k}^{(t+1)}=\left[\lambda_{k}^{(t)}-\theta_{k}^{(t)}\left(P^{D}_{\max}-\sum_{n}^{N}(x_{k}^{n})^{(t)}\right)\right]^{+}.$
(34)

where $[a]^{+}=\max\\{0,a\\}$, and $\theta_{k}^{(t)}$ is the positive step
size. According to [14, Proposition 6.3.1], the sub-gradient method converges
to the optimal solution to Problem $\mathcal{P}3$ for sufficient small step
size $\theta_{k}^{(t)}$. Thus, the transmit power of the D2D pairs can be
obtained as $q_{k}^{n}=\alpha_{k}^{n}x_{k}^{n}$. Overall, the above analysis
is summarized as the following dual-based iterative resource allocation
(DBIRA) algorithm to solve problem $\mathcal{P}1$.

##  IV Simulation Results

The performance of the proposed resource allocation scheme is evaluated by
simulations in this section. The cell is a 500 m $\times$ 500 m square area
with BS located in center. The maximum distance between each D2D transmitter
and receiver is 30 m. The rate requirements for CUs are the same and denoted
by $\gamma_{th}$. We set $N=30$, $P^{C}_{\max}=35$ dBm, $P^{D}_{\max}=25$ dBm,
and $\sigma^{2}=-114$ dBm. The Okumura-Hata loss model is adopted and the
standard deviation of log-normal shadow fading is 4 dB. All results are
averaged over 1000 random realizations. For comparison, we adopt the
orthogonal frequency division multiple access (OFDMA) system that have
multiple CUs on each SC as the benchmark, labeled as the MCU-OFDMA scheme,
where the joint power control and channel assignment algorithm in [4] is
applied. In MCU-OFDMA system, each SC is also shared by $M$ CUs, but each CU
is only allowed to access $\frac{1}{M}$ fraction of SC bandwidth, so that the
multiplexed D2D pair in MCU-OFDMA is also interfered by $M$ co-channel CUs.

Algorithm 1 Dual Based Iterative Resource Allocation (DBIRA) Algorithm

Initialize ${x_{k}^{n}}^{(0)}=0,{\alpha_{k}^{n}}^{(0)}=0,\forall
k\in\mathcal{K},n\in\mathcal{N}$.

Initialize $\lambda_{k}^{(0)}$, step size $\theta_{k}^{(0)}$ for all
$k\in\mathcal{K}$, and set the precision $\epsilon$.

repeat

for $n\in\mathcal{N}$,$k\in\mathcal{K}$ do

Calculate ${\alpha_{k}^{n}}^{(t)}$ and ${x_{k}^{n}}^{(t)}$ according to (33)
and (31), respectively;

end for

Update $\lambda_{k}^{(t)}$ according to (34) ;

Update ${R_{\text{max}}^{D}}^{(t)}$ according to (26a) ;

until $|{R_{\text{max}}^{D}}^{(t)}-{R_{\text{max}}^{D}}^{(t-1)}|<\epsilon$ ;

Calculate $q_{k}^{n}$ and $p_{k}^{n}$ according to (19) for all
$k\in\mathcal{K},n\in\mathcal{N}$;

$q_{k}^{n}$, $p_{k}^{n}$, ${\alpha_{k}^{n}}^{(t)}$,
${R_{\text{max}}^{D}}^{(t)}$.

Fig. 2 illustrates the convergence behavior of the proposed DBIRA algorithm
versus the number of iterations under different $M$. As expected, it is shown
that the sum rate of D2D pairs monotonically increases during the initial
iterations. Moreover, the sum rate performance converges within 20 iterations
for all considered three cases, which validates the effectiveness of the
proposed DBIRA algorithm.

Fig. 2 shows the sum rate of D2D pairs w.r.t CUs’ minimum rate requirements
$\gamma_{th}$ under different $M$. As expected, the NOMA-based scheme
outperforms MCU-OFDMA scheme, especially when the number of CU multiplexed on
each SC is large. The CUs need larger transmit power in MCU-OFDMA scheme to
satisfy the same rate requirement, compared with NOMA-based scheme. This leads
to larger interference to the D2D pairs in MCU-OFDMA scheme than that in NOMA-
based scheme, since the interferences to D2D pairs are summed from all
multiplexed $M$ CUs in both MCU-OFDMA and NOMA schemes. Moreover, the sum rate
of D2D pairs decreases with the rate requirements of cellular links, which is
also due to the larger transmit power for CUs required by the higher data rate
requirements.

Figure 1:  Convergence performance of DBIRA algorithm.

Figure 2:  D2D sum rate w.r.t CUs’ rate requirements.

##  V Conclusion

The resource allocation problem for D2D communications underlaying a NOMA-
based cellular network was investigated in this letter. Although additional
power constraints are introduced to D2D pairs for the sake of the NOMA
decoding order, it is shown that the D2D underlaying NOMA cellular network
still outperforms the conventional scheme for the network with high data
requirements and myriad users.

## References

  * [1] S. Dang, J. P. Coon, and G. Chen, “Resource allocation for full-duplex relay-assisted device-to-device multicarrier systems,” _IEEE Wireless Commun. Lett._ , vol. 6, no. 2, pp. 166–169, April 2017.
  * [2] T. D. Hoang, L. B. Le, and T. Le-Ngoc, “Resource allocation for D2D communication underlaid cellular networks using graph-based approach,” _IEEE Tans. Wireless Commun._ , vol. 15, no. 10, pp. 7099–7113, October 2016\.
  * [3] S. Luo, R. Zhang, and T. J. Lim, “Downlink and uplink energy minimization through user association and beamforming in C-RAN,” _IEEE Trans. Wireless Commun._ , vol. 14, no. 1, pp. 494–508, Jan 2015.
  * [4] D. Zhu, J. Wang, A. L. Swindlehurst, and C. Zhao, “Downlink resource reuse for device-to-device communications underlaying cellular networks,” _IEEE Signal Process. Lett._ , vol. 21, no. 5, pp. 531–534, May 2014.
  * [5] Z. Yang, N. Huang, H. Xu, Y. Pan, Y. Li, and M. Chen, “Downlink resource allocation and power control for device-to-device communication underlaying cellular networks,” _IEEE Commun. Lett._ , vol. 20, no. 7, pp. 1449–1452, July 2016.
  * [6] F. Malandrino, Z. Limani, C. Casetti, and C. F. Chiasserini, “Interference-aware downlink and uplink resource allocation in hetnets with D2D support,” _IEEE Tans. Wireless Commun._ , vol. 14, no. 5, pp. 2729–2741, May 2015.
  * [7] L. Dai, B. Wang, Y. Yuan, S. Han, C. l. I, and Z. Wang, “Non-orthogonal multiple access for 5G: solutions, challenges, opportunities, and future research trends,” _IEEE Commun. Mag._ , vol. 53, no. 9, pp. 74–81, September 2015.
  * [8] J. Zhao, Y. Liu, K. K. Chai, Y. Chen, M. Elkashlan, and J. Alonso-Zarate, “NOMA-based D2D communications: Towards 5G,” in _Proc. of the IEEE Global Commun. Conf. (GLOBECOM)_ , Dec 2016, pp. 1–6.
  * [9] Z. Zhang, Z. Ma, M. Xiao, Z. Ding, and P. Fan, “Full-duplex device-to-device aided cooperative non-orthogonal multiple access,” _IEEE Trans. Veh. Technol._ , vol. PP, no. 99, pp. 1–1, 2016.
  * [10] Z. Yang, W. Xu, C. Pan, Y. Pan, and M. Chen, “On the optimality of power allocation for NOMA downlinks with individual QoS constraints,” _IEEE Commun. Lett._ , vol. PP, no. 99, pp. 1–1, 2017.
  * [11] Z. Ding, Z. Yang, P. Fan, and H. V. Poor, “On the performance of non-orthogonal multiple access in 5G systems with randomly deployed users,” _IEEE Signal Process. Lett._ , vol. 21, no. 12, pp. 1501–1505, Dec 2014.
  * [12] S. Boyd and L. Vandenberghe, _Convex Optimization_. Cambridge university press, 2004.
  * [13] C. Y. Wong, R. S. Cheng, K. B. Lataief, and R. D. Murch, “Multiuser OFDM with adaptive subcarrier, bit, and power allocation,” _IEEE J. Sel. Areas Commun._ , vol. 17, no. 10, pp. 1747–1758, Oct 1999.
  * [14] D. Bertsimas and R. Weismantel, _Optimization over integers_. Dynamic Ideas Belmont, 2005, vol. 13.


0 Research please specify ∗These two authors contributed equally to this work
All authors are with the Department of Computer Science & Electrical
Engineering at the University of Maryland, Baltimore County.

# SeeBel: Seeing is Believing

Sourajit Saha∗0000-0003-1357-7813  Shubhashis Roy Dipta∗0000-0002-9176-1782

###### Abstract

Semantic Segmentation is a significant research field in Computer Vision.
Despite being a widely studied subject area, many visualization tools do not
exist that capture segmentation quality and dataset statistics such as a class
imbalance in the same view. While the significance of discovering and
introspecting the correlation between dataset statistics and AI model
performance for dense prediction computer vision tasks such as semantic
segmentation is well established in the computer vision literature, to the
best of our knowledge, no visualization tools have been proposed to view and
analyze the aforementioned tasks. Our project aims to bridge this gap by
proposing three visualizations that enable users to compare dataset statistics
and AI performance for segmenting all images, a single image in the dataset,
explore the AI model’s attention on image regions once trained and browse the
quality of masks predicted by AI for any selected (by user) number of objects
under the same tool. Our project tries to further increase the
interpretability of the trained AI model for segmentation by visualizing its
image attention weights. For visualization, we use Scatterplot and Heatmap to
encode correlation and features, respectively. We further propose to conduct
surveys on real users to study the efficacy of our visualization tool in
computer vision and AI domain. The full system can be accessed at
https://github.com/dipta007/SeeBel.

###### keywords:

Data Visualization, Computer Vision, Semantic Segmentation, Machine Learning,
Explainable AI

Correlation between object size and object performance for different object
categories in cityscapes dataset [1] with an overview-detail view. In overview
view, all object categories are shown, whereas in the detail view, specific
object is shown.

##  1 Introduction

In this project, we study how Data Visualization can aid machine learning
systems users (researchers, engineers, practitioners) in analyzing the effects
of class imbalance on semantic segmentation performance. Semantic segmentation
is a high-level computer vision task where each pixel is assigned a class
label delineating the object type (e.g., car, person, etc.) present in that
pixel. Image datasets that are usually used to train machine learning models
to perform semantic segmentation are imbalanced in terms of class distribution
[2, 1, 3, 4, 5, 6, 7, 8]. Moreover, class imbalance can negatively impact [9]
the performance of semantic segmentation systems. Therefore, investigating how
class imbalance and the performance of semantic segmentation models are
correlated is a significant research topic that requires investigation. The
dataset that we use is Cityscapes [1] dataset. Our proposed visualization aims
to visually assist machine learning systems users in inspecting the
aforementioned correlation. Our proposed visualization consists of three key
tasks:

###  1.1 User Discovers Correlation

For this task, the user aims to discover correlation between class
distribution and performance for semantic segmentation. We aim to design this
visualization so that users can visually inspect prediction scores (by the
trained model) and object size and compare these two attributes for all object
classes in a given dataset. This task can potentially help users gain insights
into how class distribution and AI performance relate to each other.

###  1.2 User Locate/Explore/Browse Features

For this task, the user aims to locate, explore, or browse the model’s
attention weights across the entire image for each class, depending on the
user’s requirement. When segmenting an object, a trained AI model gives
different amounts of attention to different portions of the image. With our
visualization, the user can explore, browse, and locate through the image to
find the amount of attention by AI at different image locations. Through this
visualization, users can potentially gain insights into the AI model’s
behavior while predicting different objects.

###  1.3 User Locate/Browse/Explore Distributions

For this task, the user’s goal is to locate, browse or explore different
object categories at different image regions as a trained AI model segments an
image. This task will help the user visually/qualitatively inspect the
segmentation quality of the model, and we propose an interaction for this task
that allows users to bring all or any number of objects into view. Another
objective of this task aims to help the user discover a quantitative
correlation between object size and the confidence of the AI model to predict
that object for a set of object categories that users can select. While the
aim of the first task (described in section 1.1) is to discover a correlation
between object size and performance quantitatively for all images in the
entire dataset, this task, however, does the same (both qualitatively and
quantitatively) but for a single image.

###  1.4 The problem potentially solved with our proposed visualization

Our proposed visualization can potentially become a helping tool for
researchers who train semantic segmentation models and individuals who are
responsible for policy-making to deploy these systems in real-world
applications. Semantic segmentation datasets are often imbalanced, and
different techniques such as weighted loss function [10] and resampling data
[11] are usually used to mitigate these challenges. However, all of these
techniques require an understanding of the dataset’s statistics. These
statistics include the distribution of classes across a number of images (the
number of images containing some object may be different than the number of
images containing some other object), distribution of classes across the
amount of pixel area (amount of pixel area containing some object may be
different than the amount of pixel area containing some other object). With
the knowledge of class distribution, the user can then design a loss function
by assigning higher weights to the rare classes (low frequency, small object
size) and lower weights to the abundant classes (high frequency, larger object
size) before training the machine learning models. Sometimes, the
aforementioned loss function’s weights require an adaptive update. To
understand in which direction an update is required (if at all), it is
essential to know the classes’ performance. And this knowledge can guide the
user to change loss weights adaptively and learning rates or even to re-
initiate training with a different approach if the performance for rare
classes is still not improved, which can reduce both time, cost, and carbon
footprint since the training of large machine learning models is expensive,
time-consuming and power hungry. Our visualization, thus, can help the user
depict these statistics, both before initiating the training and after
training.

###  1.5 Domain & Typical Users

The domain of our visualization is Machine Learning & Computer Vision. Hence,
some of the pronounced users of our visualization are Machine Learning (ML)
and Computer Vision (CV) practitioners/researchers who might want to discover
correlation between dataset statistics and performance. Another typical user
is self-driving vehicle manufacturers who might want to discover how their
trained AI model is doing for some crucial objects, i.e., roads, pedestrians,
and traffic lights. The medical imaging community can be another set of
typical users who might find it useful to discover the effect of dataset
statistics on training, as medical data is often highly imbalanced.

###  1.6 Our Contribution

Our contributions are the following:

  * •

Our first visualization (detailed in section 4.1) helps the user discover
correlation between class distributions and performance for each class.

  * •

Our second visualization (detailed in section 4.2) allows the user to explore
the attention weights of trained Semantic Segmentation models (AI) on images
while predicting particular objects.

  * •

Our last visualization (detailed in section 4.3) helps the user quantitatively
discover correlations between object size and performance, both qualitatively
and quantitatively for any single image and any number of object categories.

  * •

Our visualizations can potentially help the users better understand their
machine learning(AI) models and the effect of dataset statistics on training,
contributing to enhancement in AI interpretability and building robust AI
models.

  * •

To the best of our knowledge, research efforts that are invested in building
robust AI models do not typically use visualization tools to view dataset
statistics and AI performance in a unified platform. While it is realized that
dataset statistics and AI performance are closely related, a one-stop
visualization tool to uncover that closeness is of sheer research
significance.

##  2 Related Works

Some studies discovered the distribution of different classes in the
cityscapes dataset in terms of the number of pixels occupied by each class [1,
12], the proportion of labeled pixels for each class [1], number of images for
each class [1], etc. These studies, however, are limited to analyzing
(discovering) class distribution alone and do not compare any correlation
between class distribution and performance. On the other hand, some studies -
to depict the efficacy of their respective machine learning models - have
reported [13, 14] a detailed overview of performance for each class trained on
various semantic segmentation datasets. Yet, they do not establish any
connection between performance and class distribution. To the best of our
knowledge, our visualization is the first to address a correlation between the
aforementioned attributes.

Cost Curves [15] is an essential visualization method to uncover machine
learning model performance over a range of class distributions. The idiom for
the cost curve is a line plot. The authors plot the probability cost of a wide
range of sampling distributions over a dataset and their corresponding
normalized expected cost. Moreover, to encode data, the authors have used
horizontal and vertical spatial positions, connection lines, point marks, and
shape channels for the user to find trends and correlations. However,
generalizing the cost curve method to a semantic segmentation model is
computationally (both memory and time) expensive since (1) cityscapes have 19
trainable classes, and the cost curve method uses only two classes to sample a
wide range of distribution samples and (2) the complexity of a segmentation
model is much higher than that of a classification model because. Furthermore,
the cost curve is not easily interpretable from a visualization perspective.
It takes domain-specific knowledge on the user’s end and added cognitive load
to compare a correlation between a class distribution and model performance.
Therefore, we only propose to report model performance and class distributions
of the dataset using Scatter plots to discover their correlation in our
project.

In Natural Language Processing (NLP), attention-based models have achieved
state-of-the-art results in different domains of NLP tasks. But the
interpretability of how they work remains a mystery. In this work [16], the
authors have used different idioms to increase the interpretability of
attention-based models. The authors have provided three interactive idioms. In
the attention-head view, authors have explored the self-attention weights for
one or multiple heads for each input. They have used color hue to express the
weight and line for word connections. Subsequently, in the model view, the
authors have presented an overview-detail view with color hue as categorical
layers and lines as word connections in a detailed view. And in the neuron
view, authors have drawn a simple line connection idiom to show the individual
neuron weights with respect to the query, key, and value. All of the views are
interactive, with the option to choose layers and heads and zoom in on the
individual head. Even though our proposal domain (computer vision) differs
from this work’s, the interpretability of their visualization has inspired us
to study similar analogies for Computer Vision.

Another study [17] was recently conducted, which proposed radial bar chart-
based visualization of classification performance. They used the radial
positions to represent model performance and the color and angular positions
to represent classes. The authors further show how they draw different numbers
of samples from a dataset and report the error rate for all of them after
certain iterations. However, using such a design for our purpose will be
cumbersome as we have more classes in cityscapes, and discovering trends from
different figures (since it requires one visualization per iteration in this
design mechanism) will increase the cognitive load on the user’s part. Due to
the inefficiency of this proposed idiom, we have extensively used scatter
plots in our visualization, which can show more points with less cognitive
load.

A subsequent study [18] proposes a visualization that depicts the internal
information processed by an autonomous vehicle so that the user, with a
reduced cognitive load, can access that information and asses the vehicle’s
next move. It allows the users to perceive the vehicle’s detection
capabilities, and the authors processed the semantic segmentation of road
scene images for image classification based on pixels. They use color hue for
categorical attributes to show the color distributions of the object
visualization. Additionally, different shapes are used as identity channels to
show dynamic and static objects. Furthermore, box plots and violin plots are
used to show the distribution of data points. More specifically, violin plots
are used to show the perceived ability to detect dynamic and static objects
and the system’s ranking. Whereas this visualization can successfully depict
the information of autonomous vehicles, it has a limitation on the number of
bins. Our dataset [1] has 19 classes, and a scatter plot is a more efficient
choice than using a box plot.

In a later study [19], the authors have proposed to learn insights into the
training dataset from the corresponding classification results. Furthermore,
this study aims to find how classification performance is related to class
distribution by visually inspecting how far a predicted class is from the
ground truth class in the class map space. The authors further show how they
use scatter plots as their choice of idiom. The horizontal spatial position
denotes class distance, and the vertical axis spatial position denotes the
probability that the model assigns to alternative classes. One of the major
issues with this visualization is that it needs to be repeated for each class;
therefore, using this mechanism to visualize the semantic segmentation
performance for all the classes (19 of them) will be challenging, and
discovering trends from multiple idioms will pose added cognitive load on the
user’s part.

InstanceFlow [20] is a sophisticated visualization tool that allows users to
compare learning behavior between iterations on an instance level. They use a
Sankey diagram with glyphs to depict a temporal analysis of the training
process. They have used color to show the importance of the flow. With their
proposed visualization, the authors offer a unified solution to discover
trends between performance at different iterations at the expense of a
complicated visualization and added cognitive load. We aim to allow the user
to discover the exact correlation with a much simpler visualization (Scatter
plot, images, and superimposed layer) with lesser strains on cognition.

##  3 Implementation

###  3.1 Data

The cityscapes [1] dataset has 5000 images with an identical resolution of
1024 × 2048 pixels. The dataset further contains masks for different objects
in each image, and all of the images are taken while driving in different
cities in Germany. Cityscapes contains 2975 training images, 500 validation
images, and 1525 test images, contributing to a total of 5000 images.
Moreover, the 1525 test images do not contain annotated masks. Those labels
are not made public and are only used internally to score models submitted to
the Cityscapes leaderboard 111https://www.cityscapes-dataset.com/benchmarks/.
And therefore, we only use the training images for training our AI model and
all relevant visualizations throughout the entirety of this project. The
annotated masks provided in the dataset account for 30 classes. Although only
19 classes are used for evaluation, and therefore all of our experiments,
including the pre-processing of the data and the corresponding visualizations,
will contain 19 classes.

Figure 1: Input image along with it’s given, and AI predicted masks for object
category: car, building.

The semantics of this dataset are street scene images captured from vehicles.
For every image in the dataset, there exists a set of corresponding masks that
encompasses the objects present in that image and the position (pixel
location) and category (i.e., car, bus, traffic light, etc.) of the object.
Another way to think of this data is that all the pixels in an image contain
an object of some kind (people, car, road, etc.). The dataset uses color hue
(different color hues to represent different objects) for every pixel to
describe what kind of object is present in that pixel.

###  3.2 Data Transformation

The cityscapes dataset contains images (RGB images of scenes) and
corresponding mask images. The dataset type for Cityscapes is geometry since
images convey information about items with explicit spatial grid positions on
a 2D surface. Therefore, the data type for cityscapes is items and spatial
positions. One of the limitations of the Cityscapes dataset is the abundance
of background classes meaning only a few objects of interest are labeled,
leaving a lot of pixel space unlabeled (background class). Moreover, since we
visualize the performance on the cityscapes dataset, one of the challenges in
getting good performance on this dataset is the limited number of labeled
training images [3, 4]. Moreover, to denote the performance of AI models, we
use the IoU (Intersection over Union) metric that signifies the overlap
between the given mask and predicted mask for an object category in an image.
The ideal range of IoU is $[0,1]$ [21] however, for semantic segmentation IoU
is traditionally [22, 7, 5, 23, 24] expressed as a percentage and therefore
the range becomes $[0,100]$ (multiplied by 100).

Now, there are multiple stages of transformation that we need to perform on
the data. The first stage of transformation is task agnostic, and the second
stage is task specific.

###  3.3 Task Agnostic Data Transformation

Firstly, since we need to get our data ready to be trained, we need to Resize
the images from the original resolution (1024 x 2048) to 512 x 1024 pixels to
match the computational capacity of our training hardware (NVIDIA RTX 3090
GPU). We use this image size for the remainder of this project in all of our
experiments and analysis. Therefore, all the visualizations that use object
size depend on the resized image rather than the original image. Training the
AI model on the dataset is our project’s significant data transformation
process. Because once trained, we store the trained model to perform
prediction later. Specifically, we have trained a Convolutional Neural Network
based AI model called HRNet [22] on the cityscapes dataset. Furthermore, the
hyper-parameters we have used for training are identical to this study [22].
Now, we perform these transformations because prediction masks are some of the
attributes in our proposed visualizations, as described in section 1.1, 1.2,
and 1.3.

###  3.4 Task Specific Data Transformation for Task 1

Each image contains multiple objects (e.g., car, bus, road, etc.) and multiple
masks. Consequently, a one-to-many mapping exists between images and masks.
Figure 1 depicts two of many masks (mask of object category: car and building)
for an image in the cityscapes dataset. To discover a correlation between
object size and object IoU for different category classes, we transform the
original dataset into a table using Algorithm 1. We iterate over all the masks
($m\in M$) in the original cityscapes dataset where $M$ is the set of all
masks. Then, for each mask ($\forall m\in M$), we run the corresponding image,
$i_{m}$, through an AI model ($AI$) to compute prediction mask $p$.
Sequentially, we compute the IoU score ($IoU$) between each prediction $p$ and
given mask $m$, object size of the given mask $m$ ($Size_{m}$), and object
type of the given mask $m$ ($Object_{m}$) to construct each row of the table.

Algorithm 1 Data transformation to construct a table from the original image
dataset for the user to discover correlation among object size and object IoU
for different object classes.

$Table$ = []

for $m\in M$ do $\triangleright$ M is the set of all masks in the dataset

$p\leftarrow AI(i_{m})$ $\triangleright$ Compute AI prediction

$\triangleright$ for current mask $m$

$IoU\leftarrow Score_{IoU}(p,m)$ $\triangleright$ Compute IoU between AI
prediction

$\triangleright$ mask and current mask

$Size_{m}\leftarrow Area_{pixel}(m)$ $\triangleright$ Compute pixel area

$\triangleright$ for current mask

$Object_{m}\leftarrow ObjectType(m)$ $\triangleright$ Extract object class of

$\triangleright$ the current mask

$Table.add(Object_{m}$, $IoU_{m}$, $Size_{m})$ $\triangleright$ Add new mask
to the table

end for

return $Table$

###  3.5 Task Specific Data Transformation for Task 2

To visualize the attention of the AI model for segmenting different objects,
we utilize Grad-cam [25], an Explainable AI method. Grad-cam produces an image
that shows the area of the input image to which the model is paying more
attention than others, referred to as grad-cam weights. We transform the
images (given in the dataset) to a superimposed view where the original images
are superimposed with a grad-cam weight. The grad-cam algorithms must be
called to retrieve AI attention weights to predict a particular object type.
Now, the grad-cam algorithm requires a trained AI model ($AI$), image ($i$),
and object category ($c$). We denote the grad-cam algorithm as $G$ and the
grad-cam weight, $w=G(i,AI,c)$. Precisely, we repeat this process for all
possible ($i,c$) pairs over the entire dataset $\forall i\in I$ and $\forall
c\in C$. Here $I$ is the set of all images in the dataset, and $C$ is the set
of all object categories in the dataset. Finally, to superimpose image $i$ and
grad-cam weight $w$ together, we first display the original image $i$ with
opacity $\alpha_{1}$. Then we display the grad-cam weight $w$ with opacity
$\alpha_{2}$ to get the superimposed view $S$. This sequential process is
described in Equation 1. Here, $\alpha_{1}>\alpha_{2}$ so that the original
image is visually accessible behind the grad-cam weight in the superimposed
view.

$S(i,w)=\\{Display(i,\alpha_{1}),Display(w,\alpha_{2})\\}$ (1)

###  3.6 Task Specific Data Transformation for Task 3

We transform the images in the dataset into a table for this task with the
help of the trained AI model ($AI$). We first run each image $i\in I$ in the
dataset (where $I$ is the set of all images) through the trained AI model to
get the predicted mask $p=AI(i)$. Then, we extract the given mask $m$
corresponding to image $i$. From both $m$ and $p$ we compute the number of
pixels occupied by each object present in the corresponding masks. From the
pixel count for each object category, we normalize these count values in the
$[0,100]$ range to express these pixel counts in pixel occupancy percentage.
Sequentially, we construct a table where each row is the current object’s
category in the image, the object’s pixel occupancy in the given mask, and
pixel occupancy in the predicted mask.

###  3.7 Programming Language & Visualization Tool

We use Python3.7 [26] as our base programming language. We use Python Image
Library (PIL) [27] to manipulate and display images in our visualization. For
the visualization itself, we use matplotlib [28], GRAD-Cam [29], and Jupyter
Widgets [30] for the interaction in our visualizations. Also, we used PyTorch
[31] to train the machine learning model to predict the labels and mask. Also,
for data manipulation, we used pandas [32], chardet [33], and einops [34].

###  3.8 Software Architecture

We use conda [35] and pip [36] package manager to install all of our
dependencies for the code environment. We use JupyterLab [37] to run, host,
and interact with the plotting. In our early alpha and beta release
experiments, we tried other tools, i.e., seaborn [38], tableau [39], but we
switched to JupyterLab because we required more control over manipulating
visualization, data transformation, and computational efficiency.

##  4 Results

###  4.1 Task 1: Discovering Correlation Between Object Size and Object IoU
for Different Category Classes

####  4.1.1 Proposed Artifact

While using our proposed visualization tool (Figure 2), the users’ goal is to
discover a correlation between object size and IoU for different category
classes. Our proposed artifact uses two scatter plots with an overview/detail
view, shown in Figure 2. While our tool shows a scatter plot of object size
and IoU for all object classes on the left (overview), the user, with the help
of our dropdown menu, can select a particular object class and the scatter
plot for the selected object category is then displayed on the right (detail).
Figure 2 shows a snippet of how users can interactively use our tool for the
aforementioned task.

Figure 2: Snippet of our proposed tool for Task (section 4.1) from jupyter
notebook. Top: a screen capture of how users can interact with the tool. The
users can select an object class from the dropdown menu. At the initial
condition when the user is yet to interact with the tool, on the left is
displayed scatterplot for all objects (overview), and on the right is
displayed the scatterplot for car object (detail). Down: screen capture of
when the user selects building; on the left is displayed scatterplot for all
objects (overview), and on the right is displayed the scatterplot for building
object (detail).

####  4.1.2 Data Abstraction

The dataset type for this task is a 2D table with items and attributes as data
types. In the aforementioned table, each item (row) is an object mask in the
dataset. And there are three attributes (columns): (1) categorical attribute:
object type (e.g., road, person), (2) ordinal attribute: object IoU (e.g., 55
%, 92 %), and (2) ordinal attribute: object size (number of pixels occupied).
We use a horizontal position channel to encode object size, a vertical
position channel to encode object IoU, and a color-hue channel to encode
object category (class). Finally, we use a point mark for this idiom.

####  4.1.3 Task Abstraction

The user task is to discover a correlation between object size and object IoU
for different category classes. These correlations can be positive, negative,
reversing (first goes up and then down and vice-versa), or weak correlations.

####  4.1.4 Encoding and Interaction Idiom

For visual encoding, we use a scatter plot. Furthermore, we use
overview/detail interaction with the same encoding but with a subset of the
data. Finally, the dropdown menu we use to choose an object category is
another form of interaction that falls under the select category. In the
initial overview, our tool shows an overview scatter plot of object size and
IoU for all object categories and a detail-view scatter plot of object size
and IoU for the car object category (Figure 2).

####  4.1.5 Critical Analysis

In overview mode, our proposed tool (Figure 2) is supposed to give a sense of
correlation between object size and IoU across the whole dataset for all
object categories to the user. However, it is difficult to track objects in
overview mode simply because there are too many masks in the dataset and,
therefore, too many data points and colors in the scatter plot, as shown in
Figure 2. However, in detail mode, it is much easier for the user to discover
correlation because there is only a single object in the view, and the user is
not shown data points for other object categories. Also, showing a scatter
plot for a single object eliminates the need for color to denote object
category, reducing a channel.

Figure 2, 3 further suggests that correlation can be observed using our
proposed tool. For example, it can be observed (Figure 3) that for certain
objects (e.g., road, train), there is no obvious correlation followed by all
the masks. While for other objects (e.g., buildings), there is a positive
correlation (Figure 2).

Figure 3: Cropped screenshot of our proposed tool for Task (section 4.2) from
Jupyter notebook. Left: detail view of the correlation between object size and
IoU for road objects, Middle: detail view of the correlation between object
size and IoU for traffic sign objects, Right: detail view of the correlation
between object size and IoU for train objects.

Interestingly, along with the goal of discovering correlation, it is further
observed in Figure 3 that from the density of the scatter plot, the user can
also identify data distribution (e.g., there are fewer instances of train
objects in the cityscapes dataset in comparison to that of traffic sign).
Furthermore, our proposed visualization tool (Figure 2, 3) also helps the user
identify other interesting distributions, such as most of the car objects
sizes are below an upper limit of 0.6 Million, whereas most of the road object
is sized within 0.4 to 1 Million and certain objects such as traffic signs are
very tiny in size (within 0.05 Million).

On the other hand, one limitation of our design (Figure 2) is the scalability
issues that can arise with increased data because scatter plots are usually
best suited for hundreds of data points. Another design limitation is the
separability of objects with different color hues in overview mode. For
example, bus and train are not easily differentiable (Figure 2) with the
assigned colors, and as the number of object categories grows, the problem
worsens.

Color hue denotes different object categories proposed in the cityscapes
dataset [1] are traditionally followed in computer vision literature [24, 23,
40]. Since our target users are vision researchers, we have decided to honor
that choice using the same color map used originally in the cityscapes
dataset. We hope this decision will partly attract more target users to use
our tool. Data transformation performed for this task (described in section
3.4) improves the match between data semantics and the task because
discovering correlations between attributes (Object size and IoU) would not
have been possible without the transformation. Additionally, we have used a
horizontal position channel to denote object size, a vertical position channel
to denote object IoU, and a color hue channel to denote object category.
Removing any of these channels will disable us from showing all of these three
attributes (object type, size, and IoU).

###  4.2 Task 2: Locating, Browsing and Exploring Features

####  4.2.1 Proposed Artifact

The goal of users with our proposed visualization tool (Figure 4) for this
task is to locate, browse, and explore grad-cam features. Our proposed
artifact uses one image and one superimposed layer in a multiform view. As
with our current design, the user cannot choose a different image for this
tool; therefore, this tool runs with a static image chosen in the background.
With the help of the dropdown menu, the user can select object category and
colormap. The static RGB image is displayed on the left, and GRAD-Cam weights
(superimposed with the static RGB image) are displayed on the right side of
the multiform view. Moreover, the user can interact with the superimposed
GRAD-CAM layer by hovering with the mouse, and the corresponding GRAD-CAM
weight is annotated at the mouse location. Figure 4 shows an overview of our
proposed tool for this task. GRAD-CAM [25] weights signify the amount of
importance given by the AI model to the image while predicting a certain
object category.

Figure 4: Screenshot of our proposed tool for Task (section 4.2) from Jupyter
notebook. Top Left: A screen capture of the view where the user hovers over
the GRAD-CAM image without interacting with colormap and object choices.
Bottom Left: A screen capture of the view where the user only hovers over the
GRAD-CAM image and changes the colormap. Top Right: A screen capture of the
view where the user hovers over the GRAD-CAM image and changes both the
colormap and object category. Bottom Right: A screen capture of the view where
the user hovers over the GRAD-CAM image and changes the object category only.

####  4.2.2 Data Abstraction

The dataset type for task 2 is Spatial Field, and the data type is grid,
position, and attribute. In the grid, each location denotes pixel coordinates
while the attributes are pixel values. In the case of RGB images, the data can
be viewed as 3 spatial fields where each spatial field’s grid positions
contain quantitative attributes such as R/G/B color values (different color
channels at different spatial fields). There are several channels: (1)
horizontal spatial position, (2) vertical spatial position, (3) color hue
(when categorical color maps are used with color bins for the grad-cam
superimposed layer), and (4) color saturation (when sequential color maps are
used for the grad-cam superimposed layer or for showing images). Finally, we
use the area as the mark for this idiom.

####  4.2.3 Task Abstraction

When the user hovers to a particular grad-cam superimposed layer position,
their goal is to browse features (grad-cam weight). When the user looks at the
color bar and wants to find a particular color in the grad-cam superimposed
layer, the user wants to locate feature (either grad-cam weight or color). And
finally, another use-case is when the user hovers through the grad-cam
superimposed layer to explore features (grad-cam weight) to get a sense of the
AI models’ attention on different parts of the image.

####  4.2.4 Encoding and Interaction Idiom

We use a multiform view encoding with multiple interaction choices. As shown
in Figure 4, on the left of the multi-form view is an image, and on the right
is a superimposed layer. One interaction choice is select (mouse hover) over
the superimposed layer. Another form of interaction we use is highlighting; at
the hovered mouse position of the superimposed layer, we display grad-cam
weight at that position. Finally, the dropdown menu we use to choose object
categories and colormaps is another form of interaction (select). In the
initial overview, our tool shows an image, and it’s a superimposed version
with grad-cam weights for the road object category in the turbo color map.

####  4.2.5 Critical Analysis

Firstly, when the user hovers in the superimposed layer of our multiform-view
tool, the corresponding grad-cam weight value is displayed (Figure 4). This
design is effective because the user - without needing additional interaction
with or prompt on the tool - can browse grad-cam attentions at different image
regions, and the view (superimposing image with the grad-cam weight) updates
when the user hovers to a new location are relatively seamless. Moreover, the
user can easily select object categories and colormaps from the dropdown menu
to load into the view (Figure 4).

Figure 5: Cropped screenshot of our proposed tool for Task (section 4.2) from
Jupyter notebook. Top Left: GRAD-CAM image with categorical (color-hue)
colormap: nippy-spectral. Top Right: GRAD-CAM image with categorical (color-
hue) colormap: Paired. Bottom Left: GRAD-CAM image with sequential colormap:
Turbo. Bottom Right: GRAD-CAM image with sequential colormap: rainbow. Figure
6: Cropped screenshot of our proposed tool for Task (section 4.3) from Jupyter
notebook. Top Left: initial view of the proposed tool with no interaction.
Bottom Left and Top Right: Original image, given mask, AI predicted mask, 3
scatter plots - (1) given and predicted pixel occupancy, (2) IoU and given
pixel occupancy, and (3) IoU and predicted pixel occupancy for selected
objects with hovers at the given mask (Bottom Left) and predicted mask (Top
Right). Bottom Right: View after deselecting all objects with hover at the
given mask.

Additionally, if the user attempts to locate a particular color (from the
displayed color bar) in the image, they can do so by searching through the
entire superimposed layer (Figure 4). How easy or difficult it is for the user
to do so is highly contingent on the choice of the colormap. For example, if
the user uses sequential color maps such as ’paired’, locating a color hue
becomes much easier. In Figure 5, it can be observed that locating the second
highest ranked color bin on the top right screen capture (categorical color
map) is much easier than it is in the bottom left screen capture (sequential
color map) where a sequential color map (’turbo’) has been used. However, when
the user focuses on exploring features which for this task translates to
exploring which regions of the image are more important than the other when
the AI model tries to find a certain object, sequential colormap (’turbo’,
’viridis) are more user friendly (Figure 5). This advantage stems from the
superimposed layer with sequential colormap yields a smoother distribution of
color hue and, therefore, gradcam weights, as seen in Figure 5. Our
recommended colormap for the user to explore features is turbo [41] as it is
more perceptually uniform and therefore imposes a lesser cognitive load on the
user.

Interestingly, while using our proposed tool for task 2, it can be further
observed (Figure 4) that when the AI model tries to predict bicycles, it looks
at a portion of the image (legs of a person) that has some level of pseudo-
similarity with the shape of bicycles (two rods connecting the wheels). This
is a feature explored by decoding our design that may be of interest to the
users (computer vision, AI researchers) while using this tool.

One limitation of our current design (Figure 4, 5) for this task is that AI
attention weight can be explored/browsed/located for one object category at a
time. Though it can be posited that viewing weights for too many objects at a
time can be a high-load task, it may as well be desirable for particular users
to explore/browse/locate grad-cam features for more than one category at a
time. Moreover, running the gradcam algorithm [25] is time-consuming, which is
why we have restricted our tool (Figure 4) to view grad-cam weights for one
object category at a time since viewing multiple categories at once requires
running the gradcam algorithm multiple times as well.

Data transformation performed for this task (described in section 3.5)
improves the match between data semantics and the task because
exploring/browsing/locating grad-cam features would not have been possible
without the transformation (running grad-cam algorithm on the original data
and training AI on the original data). The interactions tool that we use here
(Figure 4, 5) is effective because the user can locate grad-cam weights only
by hovering. Also, while the user can locate the gradcam feature with the help
of a color map and color bar, the hover gives the user the additional ability
to locate grad-cam features more easily as the user does not have to depend on
the color map while hovering (Figure 5). Moreover, we have used the horizontal
spatial position channel, vertical spatial position channel to denote each
image pixel, and the color-hue/color-saturation (depending on the chosen color
map) channel is used to show (Figure 4) the image and grad-cam weight
(superimposed with image). Therefore, eliminating any of these channels won’t
allow us to show the aforementioned images and superimposed layers, which
corroborates our hypothesis of "no redundant marks and channels".

###  4.3 Task 3: Discovering Correlation Between Object Size and Object IoU
for Different Category Classes

####  4.3.1 Proposed Artifact

While using this proposed tool (Figure 6), users’ goal is to locate, browse,
and explore object categories in segmented images from a given image in the
dataset. In our multiform view, we first display the input image, the
corresponding given mask, and AI predicted mask. Additionally, this tool also
provides (with three scatter plots) the user the ability to discover
correlation among three pairs of attributes: (1) given and predicted pixel
occupancy, (2) IoU and given pixel occupancy, and (3) IoU and predicted pixel
occupancy for a given image, it’s mask and AI predicted mask. We have used
check boxes for all object categories in the cityscapes dataset. The user can
select or deselect any of them at any given time. The information (Image,
given mask, predicted mask, 3 scatter plots) is updated into the view
(multiform) according to the objects selected.

####  4.3.2 Data Abstraction

The dataset type for this task is a spatial field (images and masks) and table
(computed IoU, pixel occupancy for different objects in an image). While the
data type for images and masks is grid, position, and attribute, the data
types for IoU and pixel occupancy for different objects are items and
attributes. In the table, each item is an object mask in the chosen image. And
there are three attributes: (1) categorical attribute: object type, (2)
ordinal attribute: object IoU, and (2) ordinal attribute: object size. We use
a point mark and one horizontal position channel to encode pixel occupancy, a
vertical position channel to encode object IoU in one view and pixel occupancy
in another, and a color-hue channel to encode object category (class). For the
images and masks, there are four channels: (1) horizontal spatial position,
(2) vertical spatial position, (3) color saturation (while showing images),
and (4) color hue (while showing masks). The mark used in this visualization
is area.

####  4.3.3 Task Abstraction

When the user hovers over a given or predicted mask, the goal is to locate,
browse, and explore distribution. In the case when they hover over a
particular object and the object name is displayed, the user locates objects.
Then, when the user hovers over a particular location of the image and the
corresponding object name displays, the user browses objects. Finally, the
user explores objects when they hover over different locations of the image,
and our tool displays the corresponding object category. Furthermore, the user
task is to discover the correlation among (1) pixel occupancy (in the given
mask) and object IoU, (2) pixel occupancy (in the prediction mask) and object
IoU, (3) pixel occupancy (in the given mask) and pixel occupancy (in the
prediction mask).

####  4.3.4 Encoding and Interaction Idiom

We use a multiform view encoding. As shown in Figure 6, on the top left of the
multi-form view, we show an image; on the top middle, we show the given mask,
and on the top right, we display the predicted mask and all of them are
visually encoded in the form of an image. Then, we show three correlations on
the bottom and use three scatter plots to encode them. Our design has multiple
interaction choices. Firstly the user can select any number of object
categories using the checkboxes that we implement. Then the user can also
hover (select and highlight) the prediction and given masks. The initial
overview shows the scatter plots, images, and masks for all the object
categories in the cityscapes dataset.

####  4.3.5 Critical Analysis

One of the principal goals of this task is to locate/browse/explore object
categories in the image by looking at given and predicted masks. While looking
at the predicted and given a mask with our tool (Figure 6), the users can
discern different objects with the user of color hue, though this can be
difficult sometimes. In cases with too many objects in an image or the objects
are densely meshed, our designed color hue may not be enough to tell different
objects apart. We have incorporated the hover (select) option to remedy that
situation. The users can easily locate/explore different objects by hovering
since our tool displays the object category at each mouse position, as seen in
Figure 6.

Another efficacious design choice that we use for this tool is the multiform
view. Since we are showing (Figure 6) different information/data (6 in this
case) with different idioms (2 in this case), this choice helps take the
cognition load off of the user. And when there is information being displayed
for too many object categories (how many is too many can be different for
every image since some images may contain too many object categories meshed
with each other, some may contain the same amount of objects but spaced apart
evenly), decoding the object categories from the mask can be challenging. To
remedy that, we introduce (Figure 6) the ability to interact as the users can
choose for which object categories they want our tool to load information.

It is further observed in Figure 6 that for all objects, some of the scatter
plots are difficult to read, especially when many points are positioned
densely (the last two scatter plots in the Top Left of Figure 6). On the other
hand, Figure 6 shows that the user can understand the correlation between
pixel occupancy and IoU for different objects by looking at the scatter plots.
Since the scatter plots exhibit a positive correlation (Figure 6), it helps
the users answer questions such as: Does occupying more pixels lead to higher
AI performance? The first scatter plot in Figure 6 also shows if, for
different objects, the pixel occupancy in the given mask is equal or more or
less in comparison to that of the predicted mask.

Section 3.6 describes the required data transformations to change the data
semantics for task 3. These transformations are exceedingly crucial because,
without the trained AI model, we cannot display AI-predicted masks and cannot
compute IoU and pixel occupancy in the predicted mask, which are all
visualized attributes (Figure 6) in the proposed idiom.

Figure 7: Four nested levels of visualization design with user validation
sample questions for tools 1, 2, and 3 are shown on the left, middle, and
right respectively. For each tool, the four nested levels with the required
validation are on top, and on the bottom are the sample questions for those
required validations.

##  5 User Survey/Validation

We further propose a set of validation mechanisms for our devised
visualization tools with inspirations from [42, 43, 44, 45]. As Figure 7
depicts, we primarily focus on visual encoding/interaction idiom and data/task
abstraction level for visualization tool 1 (described in Section 4.1) and tool
2 (described in Section 4.2) and further include algorithm level validation
for tool 3 (described in Section 4.3).

###  5.1 Validating Task 1

####  5.1.1 Visual encoding/interaction idiom validation

We propose a set of lab study questionnaire to validate the efficacy of our
visualization tool for task 1 (described in Section 4.1). Q3.1 to Q3.6 in
Figure 7 depicts some of the sample (high-level) questions that determine the
user’s understanding of the correlation between IoU and object size. We aim to
compute the average accuracy of these questions (Q3.1 to Q3.6 in Figure 7) on
a scale of 100 to measure the effectiveness of our tool in decoding
information. We further propose to measure the average time (normalized to a
scale of 100) taken by users to answer the questions (Q3.1 to Q3.6 in Figure
7) in order to estimate our proposed tool’s efficacy. Finally, we propose to
take a weighted average of accuracy $a$ with the weight of $\alpha$ and
measured time $t$ with the weight of $\beta$ to score
($s=(a\alpha+t\beta)/(\alpha+\beta)$) the effectiveness of our tool. The
values of $\alpha$, and $\beta$ are subject to further experimentation.
Additionally, as an in-house (downstream) idiom validation step, we further
aim to quantitatively validate the designed tool, without the need of a user,
by using the graphical perception of density metric [46] to quantify the
occlusion/distinguish-ability between data points to discern patterns.

####  5.1.2 Data / Task abstraction validation

We propose a field study (Tool 1 in Figure 7) to ask the target users to use
our visualization tool in real-life situations, considering which
visualization tool was developed. Example: (1) Registering if computer vision
and machine learning researchers use this tool to gain insights at the end of
each epoch/iteration of training. (2) Class imbalanced data requires training
with many different models and mechanisms, increasing the time to develop a
final model. We plan to observe if the usage of our tool can reduce the
aforementioned time.

###  5.2 Validating Task 2

####  5.2.1 Visual encoding/interaction idiom validation

We propose a set of lab study questionnaires (Q2.1 to Q2.5 in Figure 7) to
examine how well users can decode information using our tool for task 2
(Section 4.2). Q2.1 in Figure 7 determines if the user can browse the features
of the grad-cam. On the other hand, Q2.3 in Figure 7 suggests if the user can
locate grad-cam features, while Q2.5 in Figure 7 defines how well the user can
browse grad-cam features. Along with the answers to these questions
(correctness is defined by the answer’s accuracy $a$), we further aim to
record time $t$ (to study how fast the user can decode), number of mouse
clicks $m$ (to understand it requires more interactions to answer certain
questions than others which helps us understand how complex our visualization
tool is) and user’s confidence $c$ in answering each question. To record the
user’s confidence in each answer, we prompt five options: highly confident
(value of $100$), confident (value of $80$), somewhat confident (value of
$60$), not confident (value of $40$), not confident at all (value of $0$). We
will then take a weighted average of these four quantities averaged over all
questions and compute a score
$s=(a\alpha+t\beta+(1-m)\gamma+c\delta)/(\alpha+\beta+\gamma+\delta)$ where
$\alpha$, $\beta$, $\gamma$, $\delta$ are weights of $a$ (scale of 100), $t$
(normalized to a scale of 100), $(1-m)$ (normalized to a scale of 100), $c$
(scale of 100).

####  5.2.2 Data / Task abstraction validation

To collect anecdotal evidence (Tool 2 in Figure 7), we plan to have a computer
vision researcher try our tool and register qualitative feedback regarding the
usefulness of the tool in their usage. Furthermore, we propose a field study
(Tool 2 in Figure 7) to ask the target users to use the visualization tool in
their real-world workflow, observe and document how the deployed visualization
tool is used, and register the changes (if any) occurring in their existing
workflow. One way to do that is to observe if the users apply this tool more
frequently when they train an AI model(s) for semantic segmentation.

###  5.3 Validating Task 3

####  5.3.1 Algorithm validation

We propose (Tool 3 in Figure 7) to analyze the computational complexity of the
design using the following criterion. Every time the user selects a new set of
object categories, new mask information is loaded on the screen that is
specific to the selected objects. Currently (Figure 6), we use for loop to
iteratively update the screen with user interaction. We plan to replace these
iterative approaches with linear algebra operations on the segmentation mask
tensors to examine if this is a bottleneck and if this proposed solution can
reduce the computational load.

####  5.3.2 Visual encoding/interaction idiom validation

As a form of Immediate validation (Tool 3 in Figure 7), we first investigate
if the design occludes any information without involving the users for task 3
(Section 4.3). And furthermore, we investigate if our design incorporating a
multi-form view instead of switching between views has reduced cognitive load
based on our judgment.

For the purpose of the lab study, we propose a set of questionnaires (Q3.1 to
Q3.6 in Figure 7). Q3.1 to Q3.4 in Figure 7 depicts the understanding of the
user in terms of exploring/locating/browsing object categories in the
segmented images (both by given mask and AI model). While Q3.5 to Q3.6 in
Figure 7 determines the understanding of the user in discovering correlations
between object distribution and IoU. We plan to use the scoring mechanism
identical to Section 5.2.1 to determine the efficacy of our proposed
visualization tool 3.

####  5.3.3 Data / Task abstraction validation

We propose a field study (Tool 3 in Figure 7) to study our design’s
effectiveness. One of our proposed criteria to validate abstraction is to
observe and record if the users are using this tool on research that is
strictly related to training of AI models on class imbalanced semantic
segmentation dataset; if so, the users are trying to compare the correlation
between performance (IoU) and object frequency (pixel occupancy).

##  6 Future Work

One of the more pronounced stretch goals of our visualization tool is to
facilitate the usage of our tool in the training phase. What currently
prevents us from incorporating this feature is the computational complexity of
our tool. To run the grad-cam algorithm during the training phase, which is
computationally expensive, becomes an added stress to the user. Because,
usually, while training AI models, most of the hardware memory is occupied by
models and data loaders, allowing computational resources to the visualization
is challenging. More sophisticated re-factorization of our code to ensure
optimal hardware usage is required to solve the aforementioned issue. If
Incorporated, this feature will help the user gain insights into the model’s
behavior as they train models. Furthermore, this feature will help the user
understand how model weights change during training. This visualization can,
therefore, potentially become a helping tool towards demystifying the infamous
black-box issues [47] in machine learning.

Another stretch goal of ours is applying our visualization tool to additional
datasets and different types of AI models. We have only experimented on CNN-
based AI models; the next candidate AI model we plan to experiment with is
vision-transformer [48] based AI models. Then we plan to expand our
experimentation on different semantic segmentation datasets from various
application sub-domains such as autonomous vehicle application: Scannet [49],
GTA5 [50], IDD [12] and medical application: Kvasir-SEG [51], PROMISE12 [52].
Additional experiments such as those mentioned above can potentially yield
more insights into our visualization’s usability, efficacy, and adaptability
in different domains.

In terms of usage, one of the biggest limitations of our visualization tool is
its adaptability to another dataset by a different user. Developing a web
portal or a generic Python library can potentially solve that problem. A user
can easily use the web portal without configuring any new environment on their
system and can use our visualization from the server. On the other hand,
developing a Python library will help users integrate the visualization into
their project easily with some basic configuration changes due to their (the
user’s) dataset and AI model. To mitigate these challenges, we require proper
documentation of our code, which can further attract more contributors to our
GitHub repository to drive project growth, quality, and usability.

Another limitation of our visualization tool is that users can’t select or
upload images for the tasks described in Section 4.2, 4.3. Giving that level
of control to users will enable them to use our visualization tool for
demonstration purposes more easily; our tool can be viewed as a readily
available platform for the aforementioned tasks. Finally, there is always more
room for making the visualizations more interactive, and these decisions and
design policies need to be made with extensive research, prototyping, and the
adoption of user feedback.

##  7 Conclusion

We have presented three visualizations to understand AI interpretability and
explore semantics between dataset statistics and AI models in a novel way. We
further propose a user survey that can potentially help us understand how our
proposed visualization can help target users better correlate their data and
models. With learning incorporated effectively from user feedback and surveys,
we hope that our visualization tool will be an efficacious choice in
completing the aforementioned tasks driven by our visualization tool in our
target user’s real-life workflow. We believe that with the incorporation of
our stretch goals, our proposed visualization tool can potentially be a
significant research tool in computer vision.

##  8 Acknowledgement

The authors would like to express gratitude to Professor Rebecca Williams for
their guidance during the course that led to this paper’s development. Their
expertise and support greatly contributed to the quality of this research.

## References

  * [1] M. Cordts, M. Omran, S. Ramos, T. Rehfeld, M. Enzweiler, R. Benenson, U. Franke, S. Roth, and B. Schiele, “The cityscapes dataset for semantic urban scene understanding,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 3213–3223.
  * [2] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun, “Vision meets robotics: The kitti dataset,” _The International Journal of Robotics Research_ , vol. 32, no. 11, pp. 1231–1237, 2013.
  * [3] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_. Springer, 2014, pp. 740–755.
  * [4] B. Zhou, H. Zhao, X. Puig, S. Fidler, A. Barriuso, and A. Torralba, “Scene parsing through ade20k dataset,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 633–641.
  * [5] C. Couprie, C. Farabet, L. Najman, and Y. LeCun, “Indoor semantic segmentation using depth information,” _arXiv preprint arXiv:1301.3572_ , 2013.
  * [6] R. Mottaghi, X. Chen, X. Liu, N.-G. Cho, S.-W. Lee, S. Fidler, R. Urtasun, and A. Yuille, “The role of context for object detection and semantic segmentation in the wild,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2014, pp. 891–898.
  * [7] G. J. Brostow, J. Fauqueur, and R. Cipolla, “Semantic object classes in video: A high-definition ground truth database,” _Pattern Recognition Letters_ , vol. 30, no. 2, pp. 88–97, 2009.
  * [8] J. Pont-Tuset, F. Perazzi, S. Caelles, P. Arbeláez, A. Sorkine-Hornung, and L. Van Gool, “The 2017 davis challenge on video object segmentation,” _arXiv preprint arXiv:1704.00675_ , 2017.
  * [9] M. S. Hossain, J. M. Betts, and A. P. Paplinski, “Dual focal loss to address class imbalance in semantic segmentation,” _Neurocomputing_ , vol. 462, pp. 69–87, 2021.
  * [10] M. J. Jozani, É. Marchand, and A. Parsian, “On estimation with weighted balanced-type loss function,” _Statistics & Probability Letters_, vol. 76, no. 8, pp. 773–780, 2006.
  * [11] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “Smote: synthetic minority over-sampling technique,” _Journal of artificial intelligence research_ , vol. 16, pp. 321–357, 2002.
  * [12] G. Varma, A. Subramanian, A. Namboodiri, M. Chandraker, and C. Jawahar, “Idd: A dataset for exploring problems of autonomous navigation in unconstrained environments,” in _2019 IEEE Winter Conference on Applications of Computer Vision (WACV)_. IEEE, 2019, pp. 1743–1751.
  * [13] X. Zhang, H. Xu, H. Mo, J. Tan, C. Yang, L. Wang, and W. Ren, “Dcnas: Densely connected neural architecture search for semantic image segmentation,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 13 956–13 967.
  * [14] T. Takikawa, D. Acuna, V. Jampani, and S. Fidler, “Gated-scnn: Gated shape cnns for semantic segmentation,” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 5229–5238.
  * [15] C. Drummond and R. C. Holte, “Cost curves: An improved method for visualizing classifier performance,” _Machine learning_ , vol. 65, pp. 95–130, 2006\.
  * [16] J. Vig, “A multiscale visualization of attention in the transformer model,” _arXiv preprint arXiv:1906.05714_ , 2019.
  * [17] A. Luque, M. Mazzoleni, A. Carrasco, and A. Ferramosca, “Visualizing classification results: Confusion star and confusion gear,” _IEEE Access_ , vol. 10, pp. 1659–1677, 2021.
  * [18] M. Colley, B. Eder, J. O. Rixen, and E. Rukzio, “Effects of semantic segmentation visualization on trust, situation awareness, and cognitive load in highly automated vehicles,” in _Proceedings of the 2021 CHI conference on human factors in computing systems_ , 2021, pp. 1–11.
  * [19] J. Raymaekers, P. J. Rousseeuw, and M. Hubert, “Class maps for visualizing classification results,” _Technometrics_ , vol. 64, no. 2, pp. 151–165, 2022\.
  * [20] M. Pühringer, A. Hinterreiter, and M. Streit, “Instanceflow: Visualizing the evolution of classifier confusion at the instance level,” in _2020 IEEE visualization conference (VIS)_. IEEE, 2020, pp. 291–295.
  * [21] H. Rezatofighi, N. Tsoi, J. Gwak, A. Sadeghian, I. Reid, and S. Savarese, “Generalized intersection over union,” June 2019.
  * [22] J. Wang, K. Sun, T. Cheng, B. Jiang, C. Deng, Y. Zhao, D. Liu, Y. Mu, M. Tan, X. Wang _et al._ , “Deep high-resolution representation learning for visual recognition,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 43, no. 10, pp. 3349–3364, 2020.
  * [23] Z. Huang, X. Wang, L. Huang, C. Huang, Y. Wei, and W. Liu, “Ccnet: Criss-cross attention for semantic segmentation,” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 603–612.
  * [24] P. Wang, P. Chen, Y. Yuan, D. Liu, Z. Huang, X. Hou, and G. Cottrell, “Understanding convolution for semantic segmentation,” in _2018 IEEE winter conference on applications of computer vision (WACV)_. Ieee, 2018, pp. 1451–1460.
  * [25] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra, “Grad-cam: Visual explanations from deep networks via gradient-based localization,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 618–626.
  * [26] G. Van Rossum and F. L. Drake, _Python 3 Reference Manual_. Scotts Valley, CA: CreateSpace, 2009.
  * [27] P. Umesh, “Image processing in python,” _CSI Communications_ , vol. 23, no. 2, 2012.
  * [28] J. D. Hunter, “Matplotlib: A 2d graphics environment,” _Computing in Science & Engineering_, vol. 9, no. 3, pp. 90–95, 2007.
  * [29] “GitHub - jacobgil/pytorch-grad-cam: Advanced AI Explainability for computer vision. Support for CNNs, Vision Transformers, Classification, Object detection, Segmentation, Image similarity and more. — github.com,” https://github.com/jacobgil/pytorch-grad-cam, [Accessed 10-May-2023].
  * [30] “Jupyter Widgets; Jupyter Widgets 8.0.5 documentation — ipywidgets.readthedocs.io,” https://ipywidgets.readthedocs.io/en/stable/, [Accessed 10-May-2023].
  * [31] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [32] W. McKinney _et al._ , “Data structures for statistical computing in python,” in _Proceedings of the 9th Python in Science Conference_ , vol. 445\. Austin, TX, 2010, pp. 51–56.
  * [33] “chardet — pypi.org,” https://pypi.org/project/chardet/, [Accessed 10-May-2023].
  * [34] “Einops — einops.rocks,” https://einops.rocks/, [Accessed 10-May-2023].
  * [35] “Anaconda software distribution,” 2020. [Online]. Available: https://docs.anaconda.com/
  * [36] “pip — pypi.org,” https://pypi.org/project/pip/, [Accessed 10-May-2023].
  * [37] “Project Jupyter — jupyter.org,” https://jupyter.org/, [Accessed 10-May-2023].
  * [38] M. L. Waskom, “seaborn: statistical data visualization,” _Journal of Open Source Software_ , vol. 6, no. 60, p. 3021, 2021. [Online]. Available: https://doi.org/10.21105/joss.03021
  * [39] “Tableau: Business Intelligence and Analytics Software — tableau.com,” https://www.tableau.com/, [Accessed 10-May-2023].
  * [40] J. Breitenstein and T. Fingscheidt, “Amodal cityscapes: A new dataset, its generation, and an amodal semantic segmentation challenge baseline,” in _2022 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2022, pp. 1018–1025.
  * [41] “Turbo, An Improved Rainbow Colormap for Visualization — ai.googleblog.com,” https://ai.googleblog.com/2019/08/turbo-improved-rainbow-colormap-for.html, [Accessed 10-May-2023].
  * [42] G. Robertson, R. Fernandez, D. Fisher, B. Lee, and J. Stasko, “Effectiveness of animation in trend visualization,” _IEEE transactions on visualization and computer graphics_ , vol. 14, no. 6, pp. 1325–1332, 2008.
  * [43] L. Padilla, R. Fygenson, S. C. Castro, and E. Bertini, “Multiple forecast visualizations (mfvs): Trade-offs in trust and performance in multiple covid-19 forecast visualizations,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 29, no. 1, pp. 12–22, 2022.
  * [44] C. Nobre, D. Wootton, L. Harrison, and A. Lex, “Evaluating multivariate network visualization techniques using a validated design and crowdsourcing approach,” in _Proceedings of the 2020 CHI conference on human factors in computing systems_ , 2020, pp. 1–12.
  * [45] A. Franklin, S. Gantela, S. Shifarraw, T. R. Johnson, D. J. Robinson, B. R. King, A. M. Mehta, C. L. Maddow, N. R. Hoot, V. Nguyen _et al._ , “Dashboard visualizations: Supporting real-time throughput decision-making,” _Journal of biomedical informatics_ , vol. 71, pp. 211–221, 2017.
  * [46] S. Dakin, M. Tibber, J. Greenwood, M. Morgan _et al._ , “The common perceptual metric for human discrimination of number and density,” _Journal of Vision_ , vol. 11, no. 11, pp. 1203–1203, 2011.
  * [47] C. Rudin, “Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead,” _Nature machine intelligence_ , vol. 1, no. 5, pp. 206–215, 2019.
  * [48] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _arXiv preprint arXiv:2010.11929_ , 2020.
  * [49] A. Dai, A. X. Chang, M. Savva, M. Halber, T. Funkhouser, and M. Nießner, “Scannet: Richly-annotated 3d reconstructions of indoor scenes,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 5828–5839.
  * [50] S. R. Richter, V. Vineet, S. Roth, and V. Koltun, “Playing for data: Ground truth from computer games,” in _Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part II 14_. Springer, 2016, pp. 102–118.
  * [51] D. Jha, P. H. Smedsrud, M. A. Riegler, P. Halvorsen, T. de Lange, D. Johansen, and H. D. Johansen, “Kvasir-seg: A segmented polyp dataset,” in _MultiMedia Modeling: 26th International Conference, MMM 2020, Daejeon, South Korea, January 5–8, 2020, Proceedings, Part II 26_. Springer, 2020, pp. 451–462.
  * [52] G. Litjens, R. Toth, W. Van De Ven, C. Hoeks, S. Kerkstra, B. van Ginneken, G. Vincent, G. Guillard, N. Birbeck, J. Zhang _et al._ , “Evaluation of prostate segmentation algorithms for mri: the promise12 challenge,” _Medical image analysis_ , vol. 18, no. 2, pp. 359–373, 2014.