z(\vec{p}^{2,a-1,b}) = \sum_{i=1}^{a-1} \frac{E_i}{2} +E_b \left(\theta+\frac{1}{2}\right)+\sum_{i=b+1}^{c}E_i + E_c\left(\delta+1 - E_bS_{a+1,b}\right).
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{2,a-1,b})$, yields the inequality,

\begin{align}\label{eqn:e_ageqe_b}
(E_a-2E_c)(E_a-E_b) \geq 0.
\end{align}

which establishes the result since $E_a > E_b$ (the inequality is strict by assumption A1).

Case 2 $(a-1,b,c)$ is a bad-triplet: From (<ref>), we have that $(b,c)$ belongs to the domain of $g$. Combining the case description with (<ref>), we have that $g(b,c)=a$.Combining (<ref>) and $a>0$, we have that $(b,c) \in \mathcal{X}_3$. Hence,

\begin{align}
z(\vec{p}^{3,b,c}) = \sum_{i=1}^{a-1} \frac{E_i}{2} +E_b\theta+\sum_{i=b+1}^{c}E_i + \frac{E_a}{2}\left(\delta - E_bS_{a+1,b-1}\right).
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{3,b,c})$, yields the inequality,

\begin{align}
\left(E_c-\frac{E_a}{2}\right)\left(\delta-E_bS_{a+1,b}\right) > 0,
\end{align}

which establishes the result from (<ref>).

3) We consider three cases. The cases make sense since, $b \geq r+1$ from (<ref>), and if $b>r+1$, $(a,b-1,c-1) \in [0:r-1] \times [r+1:n] \times [r+1:n]$ from (<ref>).

Case 1 $b = r+1$: This case reduces to, $\sum_{i=a+1}^r \frac{E_c}{E_i} \geq \frac{r-a}{2}$, which is true due to 1.

Case 2 $b>r+1$, $(a,b-1,c-1)$ is a bad-triplet: Combining $b -1 \geq r+1$ and (<ref>), we have that $(a,b-1)$ belongs to the domain of $e$. From $b-1 \geq r+1$, (<ref>), and Lemma <ref>-1-a, we have that $(a,b-1,c)$ is a good-triplet. Hence, we have $e(a,b-1) = c$. Combining with (<ref>), we have $(a,b-1) \in \mathcal{X}_2$. Hence,

\begin{align}
z(\vec{p}^{2,a,b-1}) = \sum_{i=1}^{a} \frac{E_i}{2} +E_{b-1} \left(\theta-1\right)+\sum_{i=b}^{c}E_i + E_c\left(\delta-1 - E_{b-1}S_{a+1,b-1}\right).
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{2,a,b-1})$, yields the inequality,

\begin{align}
(E_b-E_{b-1})(\theta-1-E_cS_{a+1,b-1}) > 0,
\end{align}

yields the result since $E_{b-1} > E_b$ (the inequality is strict due to assumption A1).

Case 3 $b>r+1$, $(a,b-1,c-1)$ is a good-triplet: Combining $c-1 \geq b-1geq r+1$, with (<ref>), we have that $(a,c-1)$ belongs to the domain of $h$. Combining (<ref>), and the case description, we have that $h(a,c-1)=b-1$. Notice that $b-1 \geq r+1$. Hence, $(a,c-1) \in \mathcal{X}_1$, and $\min\{h(a,c-1),c-1\} = b-1$. Hence,

\begin{align}
z(\vec{p}^{1,a,c-1}) = \sum_{i=1}^{a} \frac{E_i}{2} +\frac{\left(\theta-1\right)\delta}{S_{a+1,b-1}} +\sum_{i=b}^{c-1}E_i
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{1,a,c-1})$, yields the inequality,

\begin{align}
\left(\theta-1-E_cS_{a+1,b-1}\right)\left(\delta-E_bS_{a+1,b-1}\right) \leq 0,
\end{align}

which establishes the result due to (<ref>).

4) Notice that the above reduces to,

\begin{align}
\theta \geq E_cS_{a+1,b}.
\end{align}

We consider three cases. The cases make sense since (<ref>) tells us $b+1 \leq c$ and hence $(a,b+1,c) \in [0:r-1] \times [r+1:n] \times [r+1:n]$, and $b \leq c$ from (<ref>).

Case 1 $(a,b+1,c)$ is a bad-triplet: Due to (<ref>), we have that $(a,b)$ belongs to the domain of $h$. Combining the case description with (<ref>), we have that $h(a,c) = b$. Since, $b \geq r+1$ from (<ref>), we have that $(a,c) \in \mathcal{X}_1$, and $\min\{h(a,c),c\} = b$. Hence,

\begin{align}
z(\vec{p}^{1,a,c}) = \sum_{i=1}^{a} \frac{E_i}{2} +\frac{\theta\delta}{S_{a+1,b}} +\sum_{i=b+1}^{c}E_i
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{1,a,c})$, yields the inequality,

\begin{align}
\left(E_cS_{a+1,b}-\theta\right)\left(E_bS_{a+1,b}-\delta\right) < 0,
\end{align}

which establishes the result due to (<ref>).

Case 2 $b+1 = c$, and $(a,b+1,c)$ is a good-triplet: Due to (<ref>), we have that $(a,b)$ belongs to the domain pf $h$. Since, $(a,b+1,c)$ is a good-triplet, we have $h(a,c) \geq b+1 = c$. Since, $b+1 > r+1$ from (<ref>), we have $(a,c) \in \mathcal{X}_1$, and $\min\{h(a,c),c\} = c = b+1$. Hence,

\begin{align}
z(\vec{p}^{1,a,b+1}) = \sum_{i=1}^{a} \frac{E_i}{2} +\frac{(\theta+1)(\delta+1)}{S_{a+1,b+1}}
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{1,a,b+1})$, yields the inequality,

\begin{align}
(E_bS_{a+1,b+1}-\delta-1)(E_{b+1}S_{a+1,b}-\theta) \leq 0,
\end{align}

which yields the result since $E_bS_{a+1,b+1} \geq E_bS_{a+1,b}+1 > \delta+1$ ($E_b > E_{b+1}$ and (<ref>)).

Case 3 $b+1 < c$, and $(a,b+1,c)$ is a good-triplet: Due to (<ref>), we have that, $(a,b+1)$ belongs to the domain of $e$. Combining (<ref>), $c-1 \geq r+1$ from (<ref>), and Lemma <ref>-2-a, we have that, $(a,b+1,c-1)$ is a bad-triplet. Combining with the case description, we have that $e(a,b+1) = c$. Since, $b+1<c \leq n$, we have that, $(a,b+1) \in \mathcal{X}_2$. Hence,

\begin{align}
z(\vec{p}^{2,a,b+1}) = \sum_{i=1}^{a} \frac{E_i}{2} +E_{b+1} \left(\theta+1\right)+\sum_{i=b+2}^{c}E_i + E_c\left(\delta+1 - E_{b+1}S_{a+1,b+1}\right).
\end{align}

Using $z(\vec{p}^{2,a,b}) \geq z(\vec{p}^{2,a,b+1})$, yields the inequality,

\begin{align}
(E_b-E_{b+1})\left(\theta-E_cS_{a+1,b}\right) > 0,
\end{align}

yields the result since $E_{b} > E_{b+1}$ (the inequality is strict due to assumption A1).

Now, we construct a Lagrange multiplier, similar to case 1. Consider $\vec{\mu} \in \mathbb{R}^n$, given by,

\begin{align}
\mu_k = \begin{cases}
\frac{E_c}{E_k} - \frac{1}{2} & \text{ if } a+1 \leq k \leq r\\
1-\frac{E_c}{E_k} & \text{ if } r+1 \leq k \leq b-1\\
E_cS_{a+1,b-1}+1-\theta & \text{ if } k = b\\
0 & \text{ otherwise }
\end{cases},
\end{align}

The above $\vec{\mu}$ satisfies $\vec{\mu} \geq 0$. If $k \in [a+1,r]$, we have that,

\begin{align}
\mu_k =  \frac{E_c}{E_k} - \frac{1}{2} \geq \frac{E_c}{E_{a+1}} - \frac{1}{2} \geq 0,
\end{align}

where the last inequality follows due to Lemma <ref>-1.  If $k \in [r+1,b-1]$, we have that,

\begin{align}
\mu_k = 1- \frac{E_c}{E_k} \geq 1-\frac{E_c}{E_c} \geq 0,
\end{align}

If $k = b$, $\mu_k \geq 0$, is Lemma <ref>-3.

Using the above $\mu$ as a Lagrange multiplier for problem (P-1,2,..,r), we have the problem,

p⃗,γ∑_j =1^a p_jE_j/2 + ∑_j =a+1^b-1p_j E_c  +p_bE_b(θ- E_cS_a+1,b-1)+∑_j =b+1^n p_jE_j
p⃗∈ℐ, λ∈ℝ

Notice that due to Lemma <ref>, we have that $E_j/2 \geq E_c$ for $j \in [1:a]$, $E_j\geq E_c$ for $j \in [b+1:c]$, $E_j\leq E_c$ for $j \in [c+1:n]$, and $(\theta - E_cS_{a+1,b-1})\geq E_c$. Hence, an optimal solution $\vec{p}$ for the above problem is $\vec{p} = \vec{p}^{2,a,b}$ with arbitrary $\gamma$. Let, $\gamma = E_b$. Notice that from Lemma <ref>, part-2-b, we have that $(\vec{p}^{1,a,b}, \gamma)$ is feasible for (P-1,2,..,r). Also, notice that from the definition of $\vec{\mu}$, we have $\mu_k > 0$ implies $p^{2,a,b}_kE_k = E_b$. Hence, from Lemma <ref>, we have that $(\vec{p}^{2,a,b}, \gamma)$ solves (P-1,2,..,r), as desired.

Case 3: Best vector in $\mathcal{A}$ comes from $\mathcal{A}_3$

Let $\vec{p}^{3,b,c}$ denote the best vector where $(b,c) \in \mathcal{X}_3$, and let $a = g(b,c)>0$. Define

\begin{align}\label{eqn:gamma_def_2}
\theta = \frac{r-a}{2}+b-r
\end{align}

and $\delta = r-a+b-c$.  Now we prove the following lemma.

We have that,

* If $c<n$, then $\frac{E_a}{2} \geq E_{c+1}$

* $\frac{E_{a}}{2}S_{a+1,b-1} +1\geq \theta$

* $E_b\left(\theta - \frac{E_a}{2}S_{a+1,b-1}\right) \geq \frac{E_a}{2}$

* $2E_{c}\geq E_a$

1) From (<ref>) we have that $(a-1,b)$ belongs to the domain of $e$. Combining $a>0$ from (<ref>), $c+1 \leq n$ from the statement description, Lemma <ref>-1-d, and (<ref>), we have that, $(a-1,b,c+1)$ is a good-triplet. Combining this with (<ref>), we have that $e(a-1,b) = c+1$. Notice that, $b < c+1 \leq n$ from (<ref>). Hence, $(a-1,b) \in \mathcal{X}_2$. Hence,

\begin{align}
z(\vec{p}^{2,a-1,b}) = \sum_{i=1}^{a-1} \frac{E_i}{2} +E_b\left(\theta+\frac{1}{2}\right)+\sum_{i=b+1}^{c}E_i + E_{c+1}\left(\delta + 1- E_bS_{a+1,b}\right).
\end{align}

Using $z(\vec{p}^{3,b,c}) \geq z(\vec{p}^{2,a-1,b})$, yields,

\begin{align}
\left(\frac{E_a}{2}-E_{c+1}\right)\left(\delta+1-E_bS_{a,b}\right) \geq 0,
\end{align}

which establishes the desired inequality from (<ref>).

2) We consider three cases. The cases make sense since $b \geq r+1$, and if $b>r+1$, we have that $(a-1,b-1,c) \in [0:r+1] \times [r+1:n] \times [r+1:n]$ from (<ref>).

Case 1 $b = r+1$: This case reduces to $E_aS_{a+1,r} \geq r-a$, which follows since $E_a \geq E_i\ \forall i \in [a+1:r]$.

Case 2 $b>r+1$ and $(a-1,b-1,c)$ is a bad-triplet: Due to $b-1\geq r+1$, and (<ref>), we have that $(b-1,c)$ belongs to the domain of $g$. From (<ref>), $b-1 \geq r+1$, and Lemma <ref>-1-a, we have that, $(a,b-1,c)$ is a good-triplet. Combining with the case description, we have that $g(b-1,c) = a$. Notice that $b-1<c \leq n$, and $0 < a \leq r-1$ from (<ref>). Hence, $(b-1,c) \in \mathcal{X}_3$. Hence,

\begin{align}
z(\vec{p}^{3,b-1,c}) = \sum_{i=1}^{a} \frac{E_i}{2} +E_{b-1} \left(\theta-1\right)+\sum_{i=b}^{c}E_i + \frac{E_a}{2}\left(\delta-1 - E_{b-1}S_{a+1,b-1}\right).
\end{align}

Using $z(\vec{p}^{3,b,c}) \geq z(\vec{p}^{3,b-1,c})$, yields the inequality,

\begin{align}
(E_b-E_{b-1})\left(\theta-1-\frac{E_a}{2}S_{a+1,b-1}\right) > 0,
\end{align}

yields the result since $E_{b-1} > E_b$ (the inequality is strict due to assumption A1).

Case 3 $b>r+1$, $(a-1,b-1,c)$ is a good-triplet: Due to (<ref>), we have that $(a-1,c)$ belongs to the domain of $h$. Combining the case description with (<ref>), we have that $h(a-1,c)=b-1$. Since $b-1 \geq r+1$, from the case description we have, $(a-1,c) \in \mathcal{X}_1$, and $\min\{h(a-1,c),c\} = b-1$. Hence,

\begin{align}
z(\vec{p}^{1,a-1,c}) = \sum_{i=1}^{a-1} \frac{E_i}{2} +\frac{\left(\theta-\frac{1}{2}\right)\delta}{S_{a,b-1}} +\sum_{i=b}^{c}E_i
\end{align}

Using $z(\vec{p}^{3,b,c}) \geq z(\vec{p}^{1,a-1,c})$, yields the inequality,

\begin{align}
\left(\frac{E_a}{2}S_{a+1,b-1}-\theta+1\right)\left(E_bS_{a,b-1}-\delta\right) \leq 0,
\end{align}

which establishes the result from (<ref>).

3) Notice that the above reduces to,

\begin{align}
\theta \geq \frac{E_a}{2}S_{a+1,b}.
\end{align}

We consider three cases. The cases make sense since, $b \leq c$ by (<ref>), and if $c>b$, we have to have that $(a,b+1,c) \in [0:r+1] \times [r+1:n] \times [r+1:n]$ from (<ref>).

Case 1 $b=c$: From (<ref>), we have that, $h(a,c) \geq b = c$. Since $c \geq r+1$, we have that, $(a,c) \in \mathcal{X}_1$. Moreover, $\min\{h(a,c) ,c\} = c= b$. Hence,

\begin{align}
z(\vec{p}^{1,a,b}) = \sum_{i=1}^{a} \frac{E_i}{2} +\frac{\theta\delta}{S_{a+1,b}}
\end{align}

Using $z(\vec{p}^{3,b,c}) \geq z(\vec{p}^{1,a,b})$, yields the inequality,

\begin{align}
\left(\frac{E_a}{2}S_{a+1,b}-\theta\right)\left(E_bS_{a+1,b}-\delta\right) < 0,
\end{align}

which establishes the result from (<ref>).

Case 2 $b<c$, and $(a,b+1,c)$ is a good-triplet:  Since $b+1 \leq c \leq n$, where the last inequality follows from (<ref>), we have that $(b+1,c)$ belongs to the domain of $g$. Combining (<ref>), $b+1\leq c \leq n$, with Lemma <ref>-2-a, we have that $(a-1,b+1,c)$ is a bad-triplet. Combining with the case description, we have that $g(b+1,c) = a$. Notice that $b+1 \leq c$, and $0 < a \leq r-1$ from (<ref>). Hence, $(b+1,c) \in \mathcal{X}_3$. Hence,

\begin{align}
z(\vec{p}^{3,b+1,c}) = \sum_{i=1}^{a} \frac{E_i}{2} +E_{b+1} \left(\theta+1\right)+\sum_{i=b+2}^{c}E_i + \frac{E_a}{2}\left(\delta+1 - E_{b+1}S_{a+1,b+1}\right).
\end{align}

Using $z(\vec{p}^{3,b,c}) \geq z(\vec{p}^{3,b+1,c})$, yields the inequality,

\begin{align}
(E_b-E_{b+1})\left(\theta-\frac{E_a}{2}S_{a+1,b}\right) > 0,
\end{align}

yields the result since $E_{b} > E_{b+1}$ (the inequality is strict due to assumption A1).

Case 3 $b<c$, and $(a,b+1,c)$ is a good-triplet: From (<ref>), we have that $(a,c)$ belongs to the domain of $h$. Combining the case description with (<ref>), we have that $h(a,c)=b$. Notice that $b \geq r+1$ from (<ref>). Hence, $(a,c) \in \mathcal{X}_1$, and $\min\{h(a,c),c \} = b$. Hence,

\begin{align}
z(\vec{p}^{1,a,c}) = \sum_{i=1}^{a} \frac{E_i}{2} +\frac{\theta\delta}{S_{a+1,b}} +\sum_{i=b+1}^{c}E_i
\end{align}

Using $z(\vec{p}^{3,b,c}) \geq z(\vec{p}^{1,a,c})$, yields the inequality,

\begin{align}
\left(\frac{E_a}{2}S_{a+1,b}-\theta\right)\left(E_bS_{a+1,b}-\delta\right) < 0,
\end{align}

which establishes the result from (<ref>).

4) We consider two cases. The cases make sense since $b \leq c$ from (<ref>).

Case 1 $b = c$: Notice that from part 2 of the lemma,

\begin{align}
\theta - \frac{E_a}{2}S_{a+1,b-1} \leq 1.
\end{align}

Substituting this in part 3, we have the result.

Case 2 $b < c$: From (<ref>), we have that, $(a,b)$ belongs to the domain of $e$. Combining (<ref>), $c-1 \geq b \geq r+1$, from the case description, with Lemma <ref>-2-d, we have that, $(a,b,c-1)$ is a bad-triplet. Combining with (<ref>), we have that  $e(a,b) = c$. Notice that $b < c \leq n$, where the last inequality follows from (<ref>). Hence, $(a,b) \in \mathcal{X}_2$. Hence,

\begin{align}
z(\vec{p}^{2,a,b}) = \sum_{i=1}^{a} \frac{E_i}{2} +E_b\theta+\sum_{i=b+1}^{c}E_i + E_{c}\left(\delta- E_bS_{a+1,b}\right).
\end{align}

Using $z(\vec{p}^{3,b,c}) \geq z(\vec{p}^{2,a,b})$, yields,

\begin{align}
\left(\frac{E_a}{2}-E_{c}\right)\left(\delta-E_bS_{a+1,b}\right) \geq 0,
\end{align}

which establishes the desired inequality due to (<ref>)

Now, we construct a Lagrange multiplier, similar to case 1. Consider $\vec{\mu} \in \mathbb{R}^n$, given by,

\begin{align}
\mu_k = \begin{cases}
\frac{E_a}{2E_k} - \frac{1}{2} & \text{ if } a+1 \leq k \leq r\\
1-\frac{E_2}{2E_k} & \text{ if } r+1 \leq k \leq b-1\\
\frac{E_a}{2}S_{a+1,b-1}+1-\theta & \text{ if } k = b\\
0 & \text{ otherwise }
\end{cases},
\end{align}

The above $\vec{\mu}$ satisfies $\vec{\mu} \geq 0$. If $k \in [a+1,r]$, we have that,

\begin{align}
\mu_k =  \frac{E_a}{2E_k} - \frac{1}{2} \geq \frac{E_a}{2E_{a}} - \frac{1}{2} = 0,
\end{align}

If $k \in [r+1,b-1]$, we have that,

\begin{align}
\mu_k = 1- \frac{E_a}{2E_k} \geq 1-\frac{E_a}{2E_c} \geq 0,
\end{align}

where the last inequality follows due to Lemma <ref>-4

If $k = b$, $\mu_k \geq 0$, is Lemma <ref>-2.

Using the above $\mu$ as a Lagrange multiplier for problem (P-1,2,..,r), we have the problem,

p⃗,γ∑_j =1^a p_jE_j/2 + ∑_j =a+1^b-1 p_jE_a/2  +p_bE_b(θ- E_a/2S_a+1,b-1)+∑_j =b+1^n p_jE_j
p⃗∈ℐ , λ∈ℝ

Notice that due to Lemma <ref>, we have that, $E_j/2 \geq E_a/2$ for $j \in [1:a]$, $E_j\leq E_{c+1} \leq E_a/2$ for $j \in [c+1:n]$, $E_j\geq E_{c} \geq \frac{E_a}{2}$ for $j \in [b+1:c]$, and $E_b\left(\theta - \frac{E_a}{2}S_{a+1,b-1}\right)\geq \frac{E_a}{2}$. Hence, an optimal solution $\vec{p}$ for the above problem is $\vec{p} = \vec{p}^{3,b,c}$ with arbitrary $\gamma$. Let, $\gamma = E_b$. Notice that from Lemma <ref>, part-2-c, we have that $(\vec{p}^{3,b,c}, \gamma)$ is feasible for (P-1,2,..,r). Also, notice that from the definition of $\vec{\mu}$, we have $\mu_k > 0$ implies  $p^{3,b,c}_kE_k = E_b$. Hence, from Lemma <ref>, we have that $(\vec{p}^{3,b,c}, \gamma)$ solves (P-1,2,..,r), as desired.

Case 4:  Best vector in $\mathcal{A}$ is $\vec{p}^0$.

We have that,

\begin{align}
\frac{E_r}{2} \geq E_{r+1}.
\end{align}

Notice that,

\begin{align}
r-(r-1) = 1 <E_{r+1}S_{r,r+1} = 1 + \frac{E_{r+1}}{E_r}.
\end{align}

Hence, $(r-1,r+1,r+1)$ is a good-triplet. Hence, $h(r-1,r+1) \geq r+1$. Clearly, $(r-1,r+1) \in \mathcal{X}_1$. Also, $\min\{h(r-1,r+1),r+1\} = r+1$.

\begin{align}
z(\vec{p}^{1,r-1,r+1}) = \sum_{i=1}^{r-1} \frac{E_i}{2} + \frac{3}{2S_{r,r+1}}
\end{align}

Using $z(\vec{p}^0) > z(\vec{p}^{1,r-1,r+1})$, yields the desired inequality.

In this case we can use $\vec{\mu} = \vec{0}$ as a Lagrange multiplier vector for (P-1,2,..,r), which gives the problem,

p⃗,γ∑_j =1^r p_jE_j/2 +∑_j =r+1^n p_jE_j

Due to Lemma <ref>, we have that $\vec{p}=\vec{p}^0$ is an optimal solution for the above problem with arbitrary $\gamma$. Let, $\gamma = E_{r+1}$. From Lemma <ref>, part-2-d we have that $(\vec{p}^0, \gamma)$ is feasible for
(P-1,2,..,r). Also, notice that $\mu_k = 0$ for all $k \in [1:n]$. Hence from Lemma <ref>, we have that $(\vec{p}^0, \gamma)$ solves (P-1,2,..,r), as desired.

§ ALGORITHM TO PROJECT ONTO $\MATHCAL{I}$

Algorithm <ref> takes as input $\vec{p} \in \mathbb{R}^n$, and projects $\vec{p}$ onto $\mathcal{I}$.

Sort the input vector $\vec{x}$ to a vector $\vec{y}$

Initialize $a = b = r$

\begin{align}\label{eqn:mu_ab}
\mu_{a,b} = \frac{\sum_{j=a}^by_j - (r-a+1)}{b-a+1},
\end{align}

\begin{align}\label{eqn:three_conds}
&\mathcal{A}_{a,b} = \mathbbm{1}\{y_b \geq \mu_{a,b} \geq y_a - 1\}\\
&\mathcal{B}_{a,b} = \mathbbm{1}\{(b = n) \text{ or }[(b < n) \text{ and } (y_{b+1} < \mu_{a,b})]\}\\
&\mathcal{C}_{a,b} = \mathbbm{1}\{(a = 1) \text{ or }[(a > 1)\text{ and }(y_{a-1} -1 > \mu_{a,b})]\}
\end{align}

for all $1 \leq a \leq b \leq n$

$\mathcal{A}_{a,b}$ and $\mathcal{B}_{a,b}$ and $\mathcal{C}_{a,b}$

Set $b \leftarrow b+1$

Set $a \leftarrow a-1$

each $i \in [1:n]$
$x_i \leftarrow \Pi_{[0,1]}(x_i-\mu_{a,b})$ (Here $\Pi_{[0,1]}$ denotes the projection onto $[0,1]$)

Output $\vec{x}$

Algorithm to project to $\mathcal{I}$

Analysis of Algorithm <ref>: Notice that the problem of projection of $\vec{y} \in \mathbb{R}^n$ onto $\mathcal{I}$ is,

z⃗1/2‖z⃗ - y⃗ ‖^2

Now consider the partial Lagrangian $L(\vec{z}, \mu)$ for $\mu \in \mathbb{R}$ given by,

\begin{align}
L(\vec{z}, \mu) = \frac{1}{2}\lVert\vec{z} - \vec{y} \rVert^2 + \mu\left(\sum_{j=1}^n z_j - r\right),
\end{align}

and the problem,

z⃗ L(z⃗, μ)(P6-μ)

for a fixed $\mu \in \mathbb{R}$. Let us assume the existence of a $\mu^* \in \mathbb{R}$ such that the solution $\vec{z}^*$ of $\text{(P6-}\mu^*\text{)}$ satisfies, $\sum_{j=1}^n z^*_j = r$. Notice that $\vec{z}^*$ is optimal for the original problem since for any $\vec{z} \in \mathcal{I}$,

\begin{align}
\frac{1}{2}\lVert\vec{z} - \vec{y} \rVert^2 = L(\vec{z}, \mu^*) \geq L(\vec{z}^*, \mu^*) = \frac{1}{2}\lVert\vec{z}^* - \vec{y} \rVert^2.
\end{align}

Hence, we focus on finding such a $\mu^*$ and the corresponding $\vec{z}^*$. First, we focus on solving $\text{(P6-}\mu^*\text{)}$. Notice that $\text{(P6-}\mu^*\text{)}$ is a separable quadratic program in the entries of $\vec{z}$. Hence, the optimal $z_j$ can be obtained by projecting the unconstrained optimal value for each entry of $\vec{z}$ onto $[0,1]$. Hence, the solution is,

\begin{align}
z_j = \Pi_{[0,1]}(y_j - \mu),
\end{align}

for all $j \in [1:n]$, where $\Pi_{[0,1]}$ denotes the projection operator onto $[0,1]$ . Now we need to find $\mu^*$ such that the optimal solution $\vec{z}^*$ of $\text{(P6-}\mu^*\text{)}$ satisfies $\vec{z}^* \in \mathcal{I}$. Hence we require,

\begin{align}\label{eqn:proj_eq}
\sum_{j=1}^n \Pi_{[0,1]}(y_j - \mu^*) = r.
\end{align}

We assume, without loss of generality, that $\vec{y}$ is sorted in non-increasing order (Notice that if $\vec{y}$ is not sorted, we could sort $\vec{y}$, perform the projection, and rearrange the elements according to the original order. This works since the set $\mathcal{I}$ is closed under the permutation of entries of its element vectors).

For $\mu \in \mathbb{R}$, define the set,

\begin{align}
\mathcal{K}_{\mu} = \{i ; 1\leq i \leq n, \mu +1 \geq y_j \geq \mu\}.
\end{align}

Notice that for each $\mu \in \mathbb{R}$, $\mathcal{K}_{\mu}$ is either the empty set or a set of the form $[a:b]$ where $1 \leq a\leq b\leq n$. Assume that $K_{\mu}$ is not empty. Let $\mathcal{K}_{\mu} = [a:b]$ where $1 \leq a\leq b\leq n$. This is equivalent to  $\mu$ satisfying the three conditions,

\begin{align}\label{eqn:conds_mu}
&y_b \geq \mu \geq y_a-1\nonumber\\
& (b = n) \text{ or } [(b<n) \text{ and }(y_{b+1} < \mu)] \nonumber\\
& (a = 1) \text{ or } [(a > 1) \text{ and }(y_{a-1}-1 > \mu)]
\end{align}

Now, notice that (<ref>) translates to,

\begin{align}\label{eqn:mu_eq_muab}
\mu = \frac{\sum_{j=a}^b y_j - (r - a+1)}{b-a+1} = \mu_{a,b}.
\end{align}

Combining (<ref>) and (<ref>), we have that if we can find $a,b$ ($1 \leq a\leq b\leq n$) such that the three conditions $\mathcal{A}_{a,b},\mathcal{B}_{a,b}$ and $\mathcal{C}_{a,b}$ (See (<ref>)) are satisfied, we are guaranteed that the solution $\vec{z}^*$ of (P6-$\mu_{a,b}$) satisfies $\vec{z}^* \in \mathcal{I}$. From the stopping condition of Algorithm <ref>, we have that the above three conditions are satisfied for the output $a,b$ of Algorithm <ref>. Hence, we are only required to prove that Algorithm <ref> always meets the stopping conditions of the loops. The inner loops trivially meet the stopping condition. Hence, we establish that the outer loop eventually meets the stopping condition.

We first prove that after each inner iteration of Algorithm <ref>, $\mathcal{A}_{a,b}$ is satisfied. To prove this, notice that $\mathcal{A}_{r,r}$ is true, and hence, for the initial values of $a,b$, $\mathcal{A}_{a,b}$ is true. Now we prove that if before executing an iteration of the first inner loop of Algorithm <ref>, $\mathcal{A}_{a,b}$ is true, then so is after the iteration. To see this, notice that the iteration is executed if only if $b< n$, and $\mu_{a,b} \leq y_{b+1}$. Hence,

\begin{align}
\mu_{a,b+1} = \frac{\mu_{a,b}(b-a+1) + y_{b+1}}{b-a+2} \leq \frac{y_{b+1}(b-a+1) + y_{b+1}}{b-a+2} = y_{b+1},
\end{align}

\begin{align}
\mu_{a,b+1} = \frac{\mu_{a,b}(b-a+1) + y_{b+1}}{b-a+2}  = \mu_{a,b} + \frac{y_{b+1} - \mu_{a,b} }{b-a+2} \geq_{(a)} \mu_{a,b} \geq_{(b)} y_a-1,
\end{align}

where (a) follows since $y_{b+1} \geq \mu_{a,b}$ and (b) follows since $\mathcal{A}_{a,b}$ is true by assumption. Hence, we have that $\mathcal{A}_{a,b+1}$ is true. Using the same argument, we can prove that if before executing an iteration of the second inner loop of Algorithm <ref>, $\mathcal{A}_{a,b}$ is true, then so is after the iteration. Hence, we have the result.

Hence, notice that after an outer iteration of Algorithm <ref>, if the stopping condition is not met, we should have $\overline{\mathcal{B}_{a,b}}$, which would increase $b$ in the next iteration. This process has to stop since $b$ has to stay between $1$ and $n$. Hence, we have the desired result.

[1]
J. F. Nash, “Equilibrium points in $n$-person games,” Proceedings of the National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950. [Online]. Available: <https://www.pnas.org/doi/abs/10.1073/pnas.36.1.48>

[2]
J. Nash, “Non-cooperative games,” Annals of Mathematics, vol. 54, no. 2, pp. 286–295, 1951. [Online]. Available: <http://www.jstor.org/stable/1969529>

[3]
R. Aumann, “Subjectivity and correlation in randomized strategies,” Journal of Mathematical Economics, vol. 1, pp. 67–96, 02 1974.

[4]
R. J. Aumann, “Correlated equilibrium as an expression of Bayesian rationality,” Econometrica, vol. 55, no. 1, pp. 1–18, 1987. [Online]. Available: <http://www.jstor.org/stable/1911154>

[5]
M. J. Osborne and A. Rubinstein, A Course in Game Theory, ser. MIT Press Books.1em plus 0.5em minus 0.4emThe MIT Press, December 1994, vol. 1, no. 0262650401. [Online]. Available: <https://ideas.repec.org/b/mtp/titles/0262650401.html>

[6]
T. Lattimore and C. Szepesvári, Bandit Algorithms.1em plus 0.5em minus 0.4emCambridge University Press, 2020.

[7]
Q. Cui, Z. Xiong, M. Fazel, and S. S. Du, “Learning in congestion games with bandit feedback,” ArXiv, vol. abs/2206.01880, 2022.

[8]
R. W. Rosenthal, “A class of games possessing pure-strategy Nash equilibria,” International Journal of Game Theory, vol. 2, pp. 65–67, 1973.

[9]
E. Nikolova and N. E. Stier-Moses, “Stochastic selfish routing,” in Algorithmic Game Theory, G. Persiano, Ed.1em plus 0.5em minus 0.4emBerlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 314–325.

[10]
H. Angelidakis, D. Fotakis, and T. Lianeas, “Stochastic congestion games with risk-averse players,” in Lecture Notes in Computer Science, 10 2013.

[11]
T. Harks, M. Henle, M. Klimm, J. Matuschke, and A. Schedel, “Multi-leader congestion games with an adversary,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 5, 2022, pp. 5068–5075.

[12]
M. Babaioff, R. Kleinberg, and C. H. Papadimitriou, “Congestion games with malicious players,” Games and Economic Behavior, vol. 67, no. 1, pp. 22–35, 2009, special Section of Games and Economic Behavior Dedicated to the 8th ACM Conference on Electronic Commerce. [Online]. Available: <https://www.sciencedirect.com/science/article/pii/S0899825609000773>

[13]
M. Wijewardena and M. J. Neely, “A two-player resource-sharing game with asymmetric information,” Games, vol. 14, no. 5, 2023. [Online]. Available: <https://www.mdpi.com/2073-4336/14/5/61>

[14]
K. Akkarajitsakul, E. Hossain, D. Niyato, and D. I. Kim, “Game theoretic approaches for multiple access in wireless networks: A survey,” IEEE Communications Surveys & Tutorials, vol. 13, no. 3, pp. 372–395, 2011.

[15]
E. Aryafar, A. Keshavarz-Haddad, M. Wang, and M. Chiang, “Rat selection games in hetnets,” in 2013 Proceedings IEEE INFOCOM, 2013, pp. 998–1006.

[16]
M. Felegyhazi, M. Cagalj, S. S. Bidokhti, and J.-P. Hubaux, “Non-cooperative multi-radio channel allocation in wireless networks,” in IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, 2007, pp. 1442–1450.

[17]
B. Li, Q. Qu, Z. Yan, and M. Yang, “Survey on ofdma based mac protocols for the next generation wlan,” in 2015 IEEE Wireless Communications and Networking Conference Workshops (WCNCW), 2015, pp. 131–135.

[18]
V. Syrgkanis, “The complexity of equilibria in cost sharing games,” 12 2010, pp. 366–377.

[19]
E. Hazan and S. Kale, “Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization,” J. Mach. Learn. Res., vol. 15, no. 1, p. 2489–2512, jan 2014.

[20]
M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ser. ICML'03.1em plus 0.5em minus 0.4emAAAI Press, 2003, p. 928–935.

[21]
A. Agarwal, O. Dekel, and L. Xiao, “Optimal algorithms for online convex optimization with multi-point bandit feedback.” in Annual Conference Computational Learning Theory, 2010. [Online]. Available: <https://api.semanticscholar.org/CorpusID:118314530>

[22]
B. O'Donoghue, T. Lattimore, and I. Osband, “Matrix games with bandit feedback,” 2021.

[23]
D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, no. 1, pp. 124–143, 1996. [Online]. Available: <https://www.sciencedirect.com/science/article/pii/S0899825696900445>

[24]
S. Chien and A. Sinclair, “Convergence to approximate Nash equilibria in congestion games,” Games and Economic Behavior, vol. 71, no. 2, pp. 315–327, 2011. [Online]. Available: <https://www.sciencedirect.com/science/article/pii/S0899825609001110>

[25]
K. Bhawalkar, M. Gairing, and T. Roughgarden, “Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness,” in Lecture Notes in Computer Science, 09 2010, pp. 17–28.

[26]
I. Milchtaich, “Congestion games with player-specific payoff functions,” Games and Economic Behavior, vol. 13, no. 1, pp. 111–124, 1996. [Online]. Available: <https://www.sciencedirect.com/science/article/pii/S0899825696900275>

[27]
H. Ackermann, P. W. Goldberg, V. S. Mirrokni, H. Röglin, and B. Vöcking, “A Unified Approach to Congestion Games and Two-Sided Markets,” Internet Mathematics, vol. 5, no. 4, pp. 439 – 458, 2008. [Online]. Available: <https://doi.org/>

[28]
D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis, “The structure and complexity of Nash equilibria for a selfish routing game,” Theoretical Computer Science, vol. 410, no. 36, pp. 3305–3326, 2009, graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. [Online]. Available: <https://www.sciencedirect.com/science/article/pii/S0304397508000261>

[29]
M. Gairing, T. Lücking, M. Mavronicolas, and B. Monien, “Computing Nash equilibria for scheduling on restricted parallel links,” in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, ser. STOC '04.1em plus 0.5em minus 0.4emNew York, NY, USA: Association for Computing Machinery, 2004, p. 613–622. [Online]. Available: <https://doi.org/10.1145/1007352.1007446>

[30]
S. Grundel, P. Borm, and H. Hamers, “Resource allocation games: a compromise stable extension of bankruptcy games,” Mathematical Methods of Operations Research, vol. 78, pp. 149–169, 2013. [Online]. Available: <https://api.semanticscholar.org/CorpusID:31249499>

[31]
——, “Resource allocation problems with concave reward functions,” TOP, vol. 27, 05 2018.

[32]
J.-B. Seo and H. Jin, “Two-user noma uplink random access games,” IEEE Communications Letters, vol. 22, no. 11, pp. 2246–2249, 2018.

[33]
——, “Revisiting two-user s-aloha games,” IEEE Communications Letters, vol. 22, no. 6, pp. 1172–1175, 2018.

[34]
I. Malanchini, M. Cesana, and N. Gatti, “Network selection and resource allocation games for wireless access networks,” IEEE Transactions on Mobile Computing, vol. 12, no. 12, pp. 2427–2440, 2013.

[35]
E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden, “The price of stability for network design with fair cost allocation,” in 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 295–304.

[36]
M. Liu and Y. Wu, “Spectum sharing as congestion games,” in 2008 46th Annual Allerton Conference on Communication, Control, and Computing.1em plus 0.5em minus 0.4emIEEE, 2008, pp. 1146–1153.

[37]
M. Liu, S. H. A. Ahmad, and Y. Wu, “Congestion games with resource reuse and applications in spectrum sharing,” in 2009 International Conference on Game Theory for Networks, 2009, pp. 171–179.

[38]
I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli, “Tight bounds for selfish and greedy load balancing,” Algorithmica, vol. 58, pp. 311–322, 01 2006.

[39]
F. Zhang and M. M. Wang, “Stochastic congestion game for load balancing in mobile-edge computing,” IEEE Internet of Things Journal, vol. 8, no. 2, pp. 778–790, 2021.

[40]
M. Ibrahim, K. Khawam, and S. Tohme, “Congestion games for distributed radio access selection in broadband networks,” in 2010 IEEE Global Telecommunications Conference GLOBECOM 2010, 2010, pp. 1–5.

[41]
S. Le, Y. Wu, and M. Toyoda, “A congestion game framework for service chain composition in NFV with function benefit,” Inf. Sci., vol. 514, no. C, p. 512–522, apr 2020. [Online]. Available: <https://doi.org/10.1016/j.ins.2019.11.015>

[42]
L. Zhang, K. Gong, and M. Xu, “Congestion control in charging stations allocation with Q-learning,” Sustainability, vol. 11, no. 14, 2019. [Online]. Available: <https://www.mdpi.com/2071-1050/11/14/3900>

[43]
T. Quint and M. Shubik, “A model of migration,” Working Paper, 1994. [Online]. Available: <https://elischolar.library.yale.edu/cowles-discussion-paper-series/1331>

[44]
C. Leuridan, “Hypersimplex coefficients,” Mathematics Stack Exchange, uRL:https://math.stackexchange.com/q/4577341 (version: 2022-11-17). [Online]. Available: <https://math.stackexchange.com/q/4577341>

[45]
T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches.1em plus 0.5em minus 0.4emCambridge, MA, USA: MIT Press, 1988.

[46]
C. Jin, P. Netrapalli, and M. Jordan, “What is local optimality in nonconvex-nonconcave minimax optimization?” in Proceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119.1em plus 0.5em minus 0.4emPMLR, 13–18 Jul 2020, pp. 4880–4889. [Online]. Available: <https://proceedings.mlr.press/v119/jin20e.html>

[47]
B. Grünbaum, V. Kaibel, V. Klee, and G. Ziegler, Convex Polytopes, ser. Graduate Texts in Mathematics.1em plus 0.5em minus 0.4emSpringer, 2003. [Online]. Available: <https://books.google.com/books?id=5iV75P9gIUgC>


11institutetext:  University of Minnesota 22institutetext: Carleton College
33institutetext: University of North Dakota
33email: {helle246<EMAIL_ADDRESS>
# The KiTS19 Challenge Data:
300 Kidney Tumor Cases with Clinical
Context, CT Semantic Segmentations, and Surgical Outcomes

Nicholas Heller 11 Niranjan Sathianathen 11 Arveen Kalapara 11 Edward Walczak
11 Keenan Moore 22 Heather Kaluzniak 33 Joel Rosenberg 11 Paul Blake 11
Zachary Rengel 11 Makinna Oestreich 11 Joshua Dean 11 Michael Tradewell 11
Aneri Shah 11 Resha Tejpaul 11 Zachary Edgerton 11 Matthew Peterson 11
Shaneabbas Raza 33 Subodh Regmi 11 Nikolaos Papanikolopoulos 11 Christopher
Weight 11

###### Abstract

Characterization of the relationship between a kidney tumor’s appearance on
cross-sectional imaging and it’s treatment outcomes is a promising direction
for informing treatement decisions and improving patient outcomes.
Unfortunately, the rigorous study of tumor morphology is limited by the
laborious and noisy process of making manual radiographic measurements.
Semantic segmentation of the tumor and surrounding organ offers a precise
quantitative description of that morphology, but it too requires significant
manual effort. A large publicly available dataset of high-fidelity semantic
segmentations along with clinical context and treatment outcomes could
accelerate not only the study of how morphology relates to outcomes, but also
the development of automatic semantic segmentation systems which could enable
such studies on unprecedented scales. We present the KiTS19 challenge dataset:
a collection of segmented CT imaging and treatment outcomes for 300 patients
treated with partial or radical nephrectomy between 2010 and 2018. 210 of
these cases have been released publicly and the remaining 90 remain private
for the objective evaluation of prediction systems developed using the public
cases.

###### Keywords:

Kidney Tumors Nephrometry Semantic Segmentation

##  1 Background & Summary

There were more than 400,000 kidney cancer diagnoses worldwide in 2018
resulting in more than 175,000 deaths [1], up from 208,000 diagnoses and
102,000 deaths in 2002 [19]. The incidence is higher in developed countries
than in developing countries, and peaks between the ages of 60 and 70 [2].
With the increase in abdominal imaging for various unrelated indications, the
incidental detection of asymptomatic renal masses has become increasingly
common. This has increased the proportion of tumors that are small and
localized when treated, which is thought to be a contributing factor to the
disease’s increased overall survival [10]. Some established risk factors for
kidney cancer are smoking, obesity, and hypertension [3]. Historically,
removal of both the tumor and affected kidney, termed Radical Nephrectomy
(RN), was standard of care for kidney tumors, but advancements in surgery in
conjunction with earlier tumor detection have precipitated shift in kidney
cancer treatment toward more conservative nephron sparing procedures, termed
Partial Nephrectomies (PNs) [21]. These are typically less invasive and limit
renal function impairment, thus they are preferred when feasible.

In an effort to more reliably quantify tumor details and accurately compare
decisions about kidney tumor treatment (notably, the decision between RN and
PN), various nephrometry scoring systems were proposed based on the tumor’s
presentation in cross-sectional imaging. Among these are R.E.N.A.L. [13],
P.A.D.U.A. [6], and the Centrality Index [20]. Once proposed, these scoring
systems were found to be associated with surgical approach and a wide range of
clinical outcomes including recurrence after treatment [17, 7], benign vs
malignant tumor [18], and high-grade tumor pathology [12]. In spite of their
impressive predictive power, existing nephrometry scores characteristically
utilize relatively simple and easy-to-extract image features such as location,
degree of endophycity, and diameter of the tumor. Further, the most popular
R.E.N.A.L. and P.A.D.U.A. scores reduce continuous variables into discrete
bins, further limiting their expressive power in favor of more expedient and
repeatable manual evaluation [11]. In contrast, semantic segmentation produces
a rich quantitative representation of the tumor and affected organ,
trivializing the precise extraction of enumerable morphological traits such as
contact surface area [15] and irregularity [22].

Our objectives in releasing this data are (1) to accelerate the research and
development of new nephrometric features to aid in prognosis and treatment
planning for kidney tumors, and (2) to enable the creation of reliable
learning-based kidney and kidney tumor semantic segmentation methods which
will allow the features developed in (1) to be automated and applied at an
unprecedented scale.

##  2 Methods

We conducted a retrospective review111This work was reviewed and approved by
the Institutional Review Board at the University of Minnesota as Study
1611M00821. of the 544 patients who underwent RN or PN at our institution
between 2010 and mid-2018 to excise a renal tumor. For 326 of these patients,
preoperative abdominal CT imaging in the late-arterial phase was available,
and the remaining patients were excluded. To simplify an unambiguous
definition of kidney tumor voxels, all patients with tumor thrombus were also
excluded, leaving 300 patients who met our inclusion criteria and comprise our
dataset.

The data collection procedure for each included patient consisted of four
steps: (1) chart review, (2) CT collection, (3) CT annotation, and (4) quality
assurance. This work was done primarily by medical students under the
supervision of author Christopher Weight, an experienced fellowship-trained
urologic oncologist who specializes in kidney tumors.

###  2.1 Chart Review

The objective of the chart review phase of the data collection procedure was
to record relevant clinical information about each patient’s demographics,
comorbidities, intervention, and clinical outcomes. This information was found
by a manual review of each patient’s Electronic Medical Record (EMR) in
conjunction with a database query for certain structured fields. An exhaustive
list and short description of each of the collected attributes from this phase
can be found in Section 3.

###  2.2 CT Collection

The objective of the CT collection phase of the data collection procedure was
to secure a local copy of the most recent preoperative CT study for each
patient that contained at least one series in late arterial contrast phase
that depicts the entirety of the abdomen (at least). Despite the fact that
such imaging is standard of care for kidney tumors [2], many patients were
excluded at this stage because it was either done at a referring institution
and not available to our team, or MRI was used instead for preoperative
planning.

In rare cases where several preoperative studies captured within one week of
each other meet this criteria, preference was given to the study containing
the late arterial series with smallest slice-thickness.

###  2.3 CT Annotation

Once a patient’s clinical attributes and imaging were collected, they were
moved to the third phase of our data collection procedure: manual delineation
of the kidney and tumor boundaries. To perform these annotations in a
distributed manner, we developed a simple web application based on the HTML5
Canvas element that allowed users to draw freehand contours on images [9]. All
annotations were performed in the transverse plane, and series were regularly
subsampled in the longitudinal direction such that the number of annotated
slices depicting any kidney was roughly 50 per patient. Interpolation
(described later) was performed to compute labels for the excluded slices.

####  2.3.1 Manual Delineation

The students performing these annotations were given the following
instructions:

  1. 1.

Confirm that the collection of images for this patient depicts the entirety of
all kidneys. Some of the patients found in our review had horseshoe kidneys or
were transplant recipients. These were included so long as the entirety of all
kidneys were shown. Let the $i$th case have $J$ transverse slices. We will
refer to the voxels from the $j$th slice of the $i$th case as $I^{(i)}_{j}$.

  2. 2.

For each connected component of pixels belonging to a region of interest, draw
a contour which includes the entire renal capsule and any renal tumors or
cysts, but excludes all tissue other than renal parenchyma that appears more
radiodense than the perinephric fat. In slices where the hilum was present,
the students were to introduce a concavity so as to exclude the bright ureter
and renal vessels (see Fig. 1b). Let there be $N^{(i)}_{j}$ such contours in
the $j$th axial section of the $i$th case. We will refer to the set of voxels
inside one of these contours by $A^{(i)}_{j,n}$.

  3. 3.

For each connected component of tumor tissue, draw a contour which includes
that tumor component, but excludes all kidney tissue. Effectively, these
contours only specify the interface between the kidney and tumor, since the
rest of the tumor boundary was already specified in step 2 (see Fig. 1c). Let
there be $M^{(i)}_{j}$ such contours in the $j$th image of the $i$th case. We
will refer to the set of voxels inside one of these contours by
$C^{(i)}_{j,m}$.

This annotation procedure enabled the students to provide a complete and
unambiguous representation of the kidneys and kidney-tumor boundary while
limiting the number of tedious, voxel-wise decisions.

Figure 1: Left: An axial section of a kidney and tumor from the database,
$I^{(i)}_{j}$. Middle: An example of the first contour the students were
instructed to draw around the whole renal capsule and tumor but excluding the
intra-hilar structures, $\partial A^{(i)}_{j,0}$. Right: An example of the
second contour the students were instructed to draw which includes the tumor
but excludes all kidney tissue, $\partial C^{(i)}_{j,0}$.

####  2.3.2 Thresholding and Hilum Filling

It is well-established that kidneys, tumors, and cysts (HU > 0.0) are
significantly more radiodense than fat (HU < -90.0) [14], thus a simple HU
threshold can be used to precisely define the boundary between the two.
Certain CT series, those especially captured with low-dose techniques [16],
exhibit random noise which can degrade the performance of the threshold-
defined boundary. To mitigate this, we convolve a 3x3 mean filter with each
slice before performing a threshold. Experimentally, we determined that a
cutoff of -30.0 HU successfully discriminated perinephric fat and the tissue
in our regions of interest. In certain cases where the CT had a large amount
of noise and no cysts were present, we applied a 7x7 median filter to each
slice and raised the threshold value to 0 HU. We will refer to the set voxels
in the $j$th slice of the $i$th case found to be above its respective
threshold as $S^{(i)}_{j}$.

Between the manually-drawn contours and the thresholding, we partition the
voxels from our annotated slices into three bins:

  1. 1.

Loose Background, $B_{loose}$, a superset of True Background $B$, everything
outside of the intersection between the thresholded voxels, $S^{(i)}_{j}$ and
the union of all kidney+tumor contour interiors, $A^{(i)}_{j}$

$B^{(i)}_{j}\subseteq
B^{(i)}_{loose,j}=I^{(i)}_{j}\setminus\left(\bigcup_{m=1}^{M^{(i)}_{j}}A^{(i)}_{j,m}\cap
S^{(i)}_{j}\right)$

  2. 2.

True Tumor, $T$, the intersection of the tumor contour interiors,
$C^{(i)}_{j}$, with the kidney contour interiors, $A^{(i)}_{j}$, and
threshold, $S^{(i)}_{j}$

$T^{(i)}_{j}=\left(\bigcup_{m=1}^{M^{(i)}_{j}}A^{(i)}_{j,m}\cap
S^{(i)}_{j}\right)\bigcap\left(\bigcup_{n=1}^{N^{(i)}_{j}}C^{(i)}_{j,n}\right)$

  3. 3.

Strict Kidney, $K_{strict}$, a subset of true kidney, $K$, voxels which appear
in the intersection of the kidney contour interiors and threshold but not the
tumor contour interiors.

$K^{(i)}_{j}\supseteq
K^{(i)}_{strict,j}=\left(\bigcup_{m=1}^{M^{(i)}_{j}}A^{(i)}_{j,m}\cap
S^{(i)}_{j}\right)\bigcap\left(\bigcap_{n=1}^{N^{(i)}_{j}}I^{(i)}_{j}\setminus
C^{(i)}_{j,n}\right)$

These bins are depicted in Fig. 2b. Consider the kidney or cyst voxels
excluded from $K_{strict}$. We refer to these as
$K^{(i)}_{exc,j}=K^{(i)}_{j}\setminus K^{(i)}_{strict,j}$. By definition:

$\displaystyle K^{(i)}_{j}$ $\displaystyle=K^{(i)}_{strict,j}\cup
K^{(i)}_{exc,j}$ $\displaystyle B^{(i)}_{j}$
$\displaystyle=B^{(i)}_{loose,j}\setminus K^{(i)}_{exc,j}$

Therefore, if we identify $K_{exc}$, we can compute the final ground truth
partition, $B,K,\text{and}\;T$ for each annotated slice.

On inspection and trial we found that reliably delineating the boundary
between the complex intra-hilar structures and kidney parenchyma is not
feasible, and to attempt this would only introduce ambiguity and error into
our dataset, something that’s been shown to markedly hinder the performance of
deep learning-based automatic segmentation [8].

To address this, we chose to include these intra-hilar structures in our
“kidney” label. We define the boundary for these features to be that line
which spans the concavity formed by the exclusion of this tissue in the
manually-drawn contours (see Fig. 2b). This line, $H^{(i)}_{j}$, is computed
by a call to OpenCV’s convexHull() function followed by convexityDefects(). An
heuristic approach based on location and shape was used to automatically
select the correct defect and these were manually checked and corrected where
necessary. Thus, $K^{(i)}_{j}$ is defined by the inclusive interior of the
contour given by $\partial K^{(i)}_{strict,j}\cup H^{(i)}_{j}$, where
$\partial K$ denotes the set $K$’s boundary.

Figure 2: A demonstration of the various stages of the algorithm which
produces the ground truth segmentation masks given the manually-drawn
contours, best viewed in color. Left: The union of all the strict kidney sets,
$K^{(i)}_{strict,j}$. Middle: The hilum found by the heuristic based detection
algorithm as well as the true tumor found by the intersection of the tumor
contour with the left figure, $K^{(i)}_{strict,j}\cup H^{(i)}_{j}$. Right: The
final kidney and tumor labels found by including all tissue within the hilum
that’s above the threshold, blue: $T^{(i)}_{j}$, red: $K^{(i)}_{j}$.

####  2.3.3 Interpolation

Until now, we have described only the procedure defining the ground truth
given these manually drawn contours, but for practical reasons only a fraction
of the total number of slices containing a region of interest were annotated.
In order to produce contours for the remaining slices, and interpolation
methodology was used. Our algorithm for interpolating contours for the $l$th
slice from contours drawn in slices $l+a$ and $l-b$ in Algorithm 1. Once these
contours are inferred, the ground truth is computed just as it is for manually
provided contours.

Algorithm 1 Interpolate Contours

1:function MatchContourPoints(contour1, contour2)

2: result $\leftarrow$ []

3: for $\vec{x}$ in contour1 do

4: mindist $\leftarrow inf$

5: $\vec{m}\leftarrow\text{Centroid(contour1)}$

6: for $\vec{y}$ in contour2 do

7: if $\left\lVert\vec{x}-\vec{y}\right\lVert_{2}<\text{mindist}$ then

8: $\text{mindist}\leftarrow\left\lVert\vec{x}-\vec{y}\right\lVert_{2}$

9: $\vec{m}\leftarrow\vec{y}$

10: Append($(\vec{x},\vec{m})$, result) return result

11:# Populates $A^{(i)}_{l}$, $C^{(i)}_{l}$, W.L.O.G Assume $M^{(i)}_{l+a}\geq
M^{(i)}_{l+a}$, $N^{(i)}_{l+a}\geq N^{(i)}_{l+a}$

12:# Distance between contours is taken the euclidean distance between
centroids

13:$D_{max}\leftarrow 20$ # Maximum distance where contours are still morphed
together

14:$A^{(i)}_{l}\leftarrow\\{\\}$

15:for $m$ in $\\{1...M^{(i)}_{l+a}\\}$ do

16: $P\leftarrow$ nearest of contours from $A^{(i)}_{l-b}$ or $\\{\\}$ if
nearest is farther than $D_{max}$

17: $R\leftarrow$ MatchContourPoints($A^{(i)}_{l-b,m}$, $P$)

18: $A^{(i)}_{l}\leftarrow
A^{(i)}_{l}\cup\left\\{\frac{a}{a+b}*R[:,1]+\frac{b}{a+b}*R[:,2]\right\\}$

19:for $n$ in $\\{1...N^{(i)}_{l+a}\\}$ do

20: $P\leftarrow$ nearest of contours from $C^{(i)}_{l-b}$ or $\\{\\}$ if
nearest is farther than $D_{max}$

21: $R\leftarrow$ MatchContourPoints($C^{(i)}_{l-b,n}$, $P$)

22: $C^{(i)}_{l}\leftarrow
C^{(i)}_{l}\cup\left\\{\frac{a}{a+b}*R[:,1]+\frac{b}{a+b}*R[:,2]\right\\}$

###  2.4 Code Availability

Make code available for this hilum filling and interpolation. Have own github,
be able to run a demo

###  2.5 Quality Assurance

####  2.5.1 Chart Review

During chart review, the students were instructed to leave blank any field
that they were not certain about. These fields were then revisited at a later
time by two students. If those students did not agree on the field’s correct
value, author Christopher Weight was consulted to make the final
determination.

####  2.5.2 Imaging Annotations

Students performing annotations were instructed to read the radiology note
from the preoperative CT scan in order to properly locate and delineate the
tumor(s) in concordance with the expert clinician. A reviewing student
examined each and every image-ground truth pair in both the transverse and
coronal planes, checking for consistent boundary treatment, and once again for
concordance with the radiologist’s impression. Cases found to have minor
issues were fixed by this reviewing student directly, and then accepted,
whereas rare cases with major issues were sent back to the first student for
fixing, and subsequent re-review. This second practice helped to not only
reduce the annotation burden on the reviewing student, but also to educate the
annotating students and prevent similar issues in the future. We discuss our
method’s interobserver variability in section 4.

##  3 Data Records

The imaging and semantic segmentation labels that were used for the 2019 KiTS
Challenge were originally released on
GitHub222https://github.com/neheller/kits19. The kits19 repository contains a
directory named data/ which has a subdirectory for each case using the naming
convention e.g. case_00123 for case 123. Cases are numbered beginning at 0,
and the first 210 cases (case_00000 \- case_00209) comprise the public portion
of the dataset. Within each subfolder is the case’s imaging and segmentation
labels (named imaging.nii.gz and segmentation.nii.gz respectively) as well as
a JSON file with that case’s clinical attributes. A comprehensive
specification of that JSON file can be found below.

  * •

case_id (String): A unique identifier for each case. This takes the form of
"case_" followed by five digits, where the least significant digits correspond
to the case index and unused digits are assigned zero. For instance,
"case_00000", "case_00017", "case_00202"

  * •

age_at_nephrectomy (Integer): The age of the patient at the time that they
underwent nephrectomy for their renal tumor.

  * •

gender (Categorical): The gender of the patient. This takes one of the
following values: {"male", "female"}

  * •

body_mass_index (Float): The body mass index of the patient at the time
measured nearest to the most recent imaging in the dataset.

  * •

comorbidities (Object - Bitmap): This takes an object with the following
boolean attributes: myocardial_infarction, congestive_heart_failure,
peripheral_vascular_disease, cerebrovascular_disease, dementia,
copd, connective_tissue_disease, peptic_ulcer_disease,
uncomplicated_diabetes_mellitus,
diabetes_mellitus_with_end_organ_damage, chronic_kidney_disease,
hemiplegia_from_stroke, leukemia, malignant_lymphoma,
localized_solid_tumor, metastatic_solid_tumor, mild_liver_disease,
moderate_to_severe_liver_disease, aids

  * •

smoking_history (Categorical): This attribute can take any of the following
values: {"never_smoked", "previous_smoker", "current_smoker"}.

  * •

age_when_quit_smoking (Integer): The age at which the patient quit smoking.
This takes the value of "not_applicable" for cases in which it is not
applicable and null for cases in which it’s not known (22 instances).

  * •

pack_years (Integer): An estimate of the number of cigarette pack-years that
this patient has smoked. This takes the value null if it is unknown (67
instances).

  * •

chewing_tobacco_use (Categorical): This attribute can take any of the
following values: {"never_or_not_for_more_than_3mo", "quit_in_last_3mo",
"currently_chews"}.

  * •

alcohol_use (Categorical): This attribute can take any of the following
values: {"never_or_not_in_last_3mo", "two_or_less_daily",
"more_than_two_daily", "quit_in_last_3mo"}.

  * •

intraoperative_complications (Object - Bitmap): This takes an object with the
following boolean attributes: blood_transfusion,
injury_to_surrounding_organ, cardiac_event

  * •

hospitalization (Integer): The number of days this patient spent in the
hospital after their nephrectomy operation. If the patient died before being
discharged from the hospital, this attribute will take the value
"died_before_discharge".

  * •

ischemia_time (Integer): The number of minutes that the kidney was deprived of
blood during the nephrectomy operation. This takes the value of
"not_applicable" for radical nephrectomies and null for partial nephrectomies
for which this value is not available (10 instances).

  * •

radiographic_size (Float): The size of the tumor reported in the radiology
report.

  * •

pathologic_size (Float): The size of the tumor reported in the surgical
pathology report.

  * •

malignant (Boolean): true if the post-operative surgical pathology report
indicates that the tumor was malignant, false otherwise.

  * •

pathology_t_stage (Categorical): The T-stage reported in the post-operative
surgical pathology report. This takes one of the following {"X", "0", "1a",
"1b", "1c", "2a", "2b", "3", "4"}

  * •

pathology_n_stage (Categorical): The N-stage reported in the post-operative
surgical pathology report. This takes one of the following {"X", "0", "1"}

  * •

pathology_m_stage (Categorical): The M-stage reported in the post-operative
surgical pathology report. This takes one of the following {"X", "0", "1"}

  * •

tumor_histologic_subtype (Categorical): The histologic subtype proved by
surgical pathology. This takes one of the following values {"clear_cell_rcc",
"clear_cell_papillary_rcc", "papillary",
"chromophobe", "urothelial", "rcc_unclassified",
"multilocular_cystic_rcc", "wilms", "oncocytoma",
"angiomyolipoma", "mest", "spindle_cell_neoplasm"}.

  * •

tumor_necrosis (Boolean): true if the post-operative surgical pathology report
indicates that necrotic tissue is present within the tumor, false if the
report indicates that it is not, and null if the report does not mention this
(23 instances).

  * •

tumor_isup_grade (Integer): The WHO ISUP [5] grade of the tumor indicated in
the post-operative surgical pathology report. The value of Null is used for
cases where ISUP grade does not apply, such as benign tumors or Chromophobes.

  * •

clavien_surgical_complications (Categorical): This takes one of following
values defined by the Clavien Dindo Grade [4]: {"0", "1", "2", "3a", "3b",
"4", "5"} or null if this could not be determined (1 instance).

  * •

er_visit (Boolean): true if the patient visited the ER less than 24 hours
after discharge but was not admitted, false if not, and null if this could not
be determined (2 instances).

  * •

readmission (Boolean): true if the patient was readmitted to a hospital within
90 days of the surgery, false if not, and null if this could not be determined
(2 instances – e.g. a censor or death date of less than 90 days after
surgery).

  * •

estimated_blood_loss (Integer): The volume of blood in ml that the surgeon
estimates was lost during the nephrectomy procedure, or null if this is not
available (1 instance).

  * •

surgery_type (Categorical): Takes one of the following values {"open",
"laparoscopic", or "robotic"}.

  * •

surgical_procedure (Categorical): Takes one of the following values
{"partial_nephrectomy", "radical_nephrectomy"}.

  * •

surgical_approach (Categorical): Takes one of the following values
{"retroperitoneal", "transperitoneal"}.

  * •

operative_time (Integer): The time that the nephrectomy procedure took in
minutes, or null if this could not be retrieved (2 instances).

  * •

cytoreductive (Boolean): true if the nephrectomy was performed for debulking
purposes, false otherwise

  * •

positive_resection_margins (Boolean): true if the post-operative surgical
pathology report indicates that there is malignant tissue still present in the
margins of the excised tissue, false if the report indicates that the margins
are clear.

  * •

last_preop_egfr (Object): Information about the most recent estimated Glomular
Filtration Rate (eGFR) value that was measured before the nephrectomy. In
cases where no preoperative eGFR value was available, this object takes the
value null (57 instances).

    * –

value (Float): The measured value in ml/min. In cases where the value was 90
or greater, a value of ">=90" was recorded. In cases where the patient was
younger than 16 years old, GFR cannot be reliably estimated so a value of
age<16 was recorded.

    * –

days_before_nephrectomy (Integer): The number of days before the nephrectomy
that this measurement was taken.

  * •

first_postop_egfr (Object): Information about the first estimated Glomular
Filtration Rate (eGFR) value that was measured after the nephrectomy. In cases
where no postoperative eGFR value was available, this object takes the value
null (53 instances).

    * –

value (Float): The measured value in ml/min. In cases where the value was 90
or greater, a value of ">=90" was recorded. In cases where the patient was
younger than 16 years old, GFR cannot be reliably estimated so a value of
age<16 was recorded.

    * –

days_after_nephrectomy (Integer): The number of days after the nephrectomy at
which this measurement was taken.

  * •

last_postop_egfr (Object): Information about the most recent estimated
Glomular Filtration Rate (eGFR) value that was measured after the nephrectomy.
In cases where one or fewer postoperative eGFR values were available, this
object takes the value null (122 instances).

    * –

value (Float): The measured value in ml/min. In cases where the value was 90
or greater, a value of ">=90" was recorded. In cases where the patient was
younger than 16 years old, GFR cannot be reliably estimated so a value of
age<16 was recorded.

    * –

days_after_nephrectomy (Integer): The number of days after the nephrectomy at
which this measurement was taken.

  * •

vital_status (Categorical): The current vital status of the patient. Takes one
of the following values: {"Censored", "Dead"}

  * •

vital_days_after_surgery (Integer): The number of days after nephrectomy until
either the censor date or the date of death.

This data has since been archived by The Cancer Imaging
Archive333https://wiki.cancerimagingarchive.net/pages/viewpage.action?pageId=61081171
where the imaging and segmentations are stored in DICOM format and the
clinical data has been converted to a single CSV file. Bitmaps within the JSON
are flattened using two underscores, such that for example the value accessed
by [“comorbidities”][“copd”] in the JSON file is stored in the CSV under the
column “comorbidities__copd”.

##  4 Technical Validation

Any large dataset is bound to be imperfect, and this is especially true of
semantic segmentation. Such datasets are still useful, of course, but their
utility can be enhanced by estimating the nature and extent of these
imperfections. In order to characterize the errors in our segmentation labels,
we randomly selected 30 cases from the challenge’s training set and repeated
the image annotation process on this subset. This allowed us to estimate
agreement that our annotation process has with itself, and thus assess the
fidelity of the labels. We measured this agreement using the same metrics as
the KiTS19 challenge. This allowed for a direct comparison to the performance
of the automatic systems submitted as part of the challenge such that an
automatic system that is as reliable as or better than our manual annotation
process would be expected to achieve the same score as that from repeating our
annotation process. The results of this study can be found in table 1.

Region | Manual Mean Dice
---|---
Kidney + Tumor | 0.983
Tumor Only | 0.923
Table 1: The agreement of the manual annotation process with itself measured
by the average Sørenson Dice score over 30 cases randomly selected from the
first 210 cases.

##  5 Usage Notes

In addition to the release of this data, we have also released some Python
starter code which includes scripts to load and visualize the data. This can
be found on GitHub at https://github.com/neheller/kits19.

## Acknowledgements

Research reported in this publication was supported by the National Cancer
Institute of the National Institutes of Health under Award Number R01CA225435.
The content is solely the responsibility of the authors and does not
necessarily represent the official views of the National Institutes of Health.

We also gratefully acknowledge Climb 4 Kidney Cancer (C4KC) for providing
student scholarships which were essential to the collection and annotation of
this data. C4KC is an organization dedicated to advocacy for kidney cancer
patients and the advancement of kidney cancer research. More inforamtion about
C4KC can be found at climb4kc.org

## References

  * [1] Bray, F., Ferlay, J., Soerjomataram, I., Siegel, R.L., Torre, L.A., Jemal, A.: Global cancer statistics 2018: Globocan estimates of incidence and mortality worldwide for 36 cancers in 185 countries. CA: a cancer journal for clinicians 68(6), 394–424 (2018)
  * [2] Capitanio, U., Montorsi, F.: Renal cancer. The Lancet 387(10021), 894–906 (2016)
  * [3] Chow, W.H., Dong, L.M., Devesa, S.S.: Epidemiology and risk factors for kidney cancer. Nature Reviews Urology 7(5), 245 (2010)
  * [4] Clavien, P.A., Sanabria, J.R., Strasberg, S.M.: Proposed classification of complications of surgery with examples of utility in cholecystectomy. Surgery 111(5), 518–526 (1992)
  * [5] Epstein, J.I., Amin, M.B., Reuter, V.R., Mostofi, F.K., Committee, B.C.C., et al.: The world health organization/international society of urological pathology consensus classification of urothelial (transitional cell) neoplasms of the urinary bladder. The American journal of surgical pathology 22(12), 1435–1448 (1998)
  * [6] Ficarra, V., Novara, G., Secco, S., Macchi, V., Porzionato, A., De Caro, R., Artibani, W.: Preoperative aspects and dimensions used for an anatomical (padua) classification of renal tumours in patients who are candidates for nephron-sparing surgery. European urology 56(5), 786–793 (2009)
  * [7] Gahan, J.C., Richter, M.D., Seideman, C.A., Trimmer, C., Chan, D., Weaver, M., Olweny, E.O., Cadeddu, J.A.: The performance of a modified renal nephrometry score in predicting renal mass radiofrequency ablation success. Urology 85(1), 125–129 (2015)
  * [8] Heller, N., Dean, J., Papanikolopoulos, N.: Imperfect segmentation labels: How much do they matter? In: Intravascular Imaging and Computer Assisted Stenting and Large-Scale Annotation of Biomedical Data and Expert Label Synthesis, pp. 112–120. Springer (2018)
  * [9] Heller, N., Stanitsas, P., Morellas, V., Papanikolopoulos, N.: A web-based platform for distributed annotation of computerized tomography scans. In: Intravascular Imaging and Computer Assisted Stenting, and Large-Scale Annotation of Biomedical Data and Expert Label Synthesis, pp. 136–145. Springer (2017)
  * [10] Homma, Y., Kawabe, K., Kitamura, T., Nishimura, Y., Shinohara, M., Kondo, Y., Saito, I., Minowada, S., Asakage, Y.: Increased incidental detection and reduced mortality in renal cancer—recent retrospective analysis at eight institutions. International journal of urology 2(2), 77–80 (1995)
  * [11] Joshi, S.S., Uzzo, R.G.: Renal tumor anatomic complexity: clinical implications for urologists. Urologic Clinics 44(2), 179–187 (2017)
  * [12] Kutikov, A., Smaldone, M.C., Egleston, B.L., Manley, B.J., Canter, D.J., Simhan, J., Boorjian, S.A., Viterbo, R., Chen, D.Y., Greenberg, R.E., et al.: Anatomic features of enhancing renal masses predict malignant and high-grade pathology: a preoperative nomogram using the renal nephrometry score. European urology 60(2), 241–248 (2011)
  * [13] Kutikov, A., Uzzo, R.G.: The renal nephrometry score: a comprehensive standardized system for quantitating renal tumor size, location and depth. The Journal of urology 182(3), 844–853 (2009)
  * [14] Lepor, H.: Prostatic diseases, vol. 2000. WB Saunders Company (2000)
  * [15] Leslie, S., Gill, I.S., de Castro Abreu, A.L., Rahmanuddin, S., Gill, K.S., Nguyen, M., Berger, A.K., Goh, A.C., Cai, J., Duddalwar, V.A., et al.: Renal tumor contact surface area: a novel parameter for predicting complexity and outcomes of partial nephrectomy. European urology 66(5), 884–893 (2014)
  * [16] Lu, H., Hsiao, T., Li, X., Liang, Z.: Noise properties of low-dose ct projections and noise treatment by scale transformations. In: 2001 IEEE Nuclear Science Symposium Conference Record (Cat. No. 01CH37310). vol. 3, pp. 1662–1666. IEEE (2001)
  * [17] Maxwell, A.W., Baird, G.L., Iannuccilli, J.D., Mayo-Smith, W.W., Dupuy, D.E.: Renal cell carcinoma: comparison of renal nephrometry and padua scores with maximum tumor diameter for prediction of local recurrence after thermal ablation. Radiology 283(2), 590–597 (2016)
  * [18] Osawa, T., Hafez, K.S., Miller, D.C., Montgomery, J.S., Morgan, T.M., Palapattu, G.S., Weizer, A.Z., Caoili, E.M., Ellis, J.H., Kunju, L.P., et al.: Comparison of percutaneous renal mass biopsy and renal nephrometry score nomograms for determining benign vs malignant disease and low-risk vs high-risk renal tumors. Urology 96, 87–92 (2016)
  * [19] Parkin, D.M., Bray, F., Ferlay, J., Pisani, P.: Global cancer statistics, 2002. CA: a cancer journal for clinicians 55(2), 74–108 (2005)
  * [20] Simmons, M.N., Ching, C.B., Samplaski, M.K., Park, C.H., Gill, I.S.: Kidney tumor location measurement using the c index method. The Journal of urology 183(5), 1708–1713 (2010)
  * [21] Sun, M., Abdollah, F., Bianchi, M., Trinh, Q.D., Jeldres, C., Thuret, R., Tian, Z., Shariat, S.F., Montorsi, F., Perrotte, P., et al.: Treatment management of small renal masses in the 21st century: a paradigm shift. Annals of surgical oncology 19(7), 2380–2387 (2012)
  * [22] Yap, F.Y., Hwang, D.H., Cen, S.Y., Varghese, B.A., Desai, B., Quinn, B.D., Gupta, M.N., Rajarubendra, N., Desai, M.M., Aron, M., et al.: Quantitative contour analysis as an image-based discriminator between benign and malignant renal tumors. Urology 114, 121–127 (2018)


# RepViT-SAM: Towards Real-Time Segmenting Anything

Ao Wang1 Hui Chen1 Zijia Lin1 Jungong Han2 Guiguang Ding111footnotemark: 1
1Tsinghua University 2 The University of Sheffield
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author.

###### Abstract

Segment Anything Model (SAM) [13] has shown impressive zero-shot transfer
performance for various computer vision tasks recently [3, 9, 19, 28, 26].
However, its heavy computation costs remain daunting for practical
applications. MobileSAM [27] proposes to replace the heavyweight image encoder
in SAM with TinyViT [27] by employing distillation, which results in a
significant reduction in computational requirements. However, its deployment
on resource-constrained mobile devices still encounters challenges due to the
substantial memory and computational overhead caused by self-attention
mechanisms. Recently, RepViT [21] achieves the state-of-the-art performance
and latency trade-off on mobile devices by incorporating efficient
architectural designs of ViTs into CNNs. Here, to achieve real-time segmenting
anything on mobile devices, following [27], we replace the heavyweight image
encoder in SAM with RepViT model, ending up with the RepViT-SAM model.
Extensive experiments show that RepViT-SAM can enjoy significantly better
zero-shot transfer capability than MobileSAM [27], along with nearly
$10\times$ faster inference speed. The code and models are available at
https://github.com/THU-MIG/RepViT.

##  1 Methodology

SAM [13] is composed of a heavyweight ViT-based image encoder and a
lightweight prompt-guided mask decoder. Its huge image encoder accounts for
the majority of the inference time overhead. Therefore, MobileSAM [27]
suggests to replace the default ViT-H [6] image encoder in SAM with a
lightweight one, _i.e_., TinyViT [24]. TinyViT consists of four stages which
gradually reduce the resolution. The initial stage of TinyViT is composed of
convolution blocks utilizing inverted residual blocks [20]. To downsample the
resolution at the outset of the model, two convolution blocks with a stride of
2 are employed. Similarly, the convolution blocks with a stride of 2 is
adopted to perform spatial downsampling between adjacent stages. In order to
align the final resolution of TinyViT with that of the ViT-H image encoder of
the original SAM, MobileSAM sets the stride of the last downsampling
convolution in the TinyViT to 1. Besides, MobileSAM presents the decoupled
distillation strategy to efficiently train the lightweight image encoder, in
which the TinyViT model is directly distilled from the ViT-H in the original
SAM without the prompt-guided mask decoder. Despite significantly reducing the
computational requirements of segmenting anything, the deployment of MobileSAM
on mobile devices still poses considerable challenges. As shown in Table 1,
MobileSAM fails to run on an iPhone 12 due to its substantial memory
footprint. Besides, on a Macbook, its inference time for processing a single
image is 494ms, indicating significant room for improvement.

Table 1:  Comparison between RepViT-SAM and others in terms of latency. The
latency (ms) is measured with the standard resolution [7] of 1024$\times$1024
on iPhone 12 and Macbook M1 Pro by Core ML Tools. OOM means out of memory.

Platform | Image encoder |  Mask decoder
---|---|---
RepViT-SAM |  MobileSAM [27] |  ViT-B-SAM [13]
iPhone | 48.9 | OOM | OOM | 11.6
Macbook | 44.8 | 482.2 | 6249.5 | 11.8

Recently, RepViT [21] demonstrates the state-of-the-art performance and
latency trade-off on mobile devices by revisiting the efficient designs of
CNNs from ViT perspective. RepViT employs the early convolutions [25] as the
stem, _i.e_., two convolutions with a stride of 2 to perform 4$\times$
downsampling for the input. It adopts the RepViT block, which is composed of
structural reparameterized depthwise convolutions [4, 5] and feed forward
module. A deep downsample module is employed between adjacent stages, which
leverage a depthwise convolution with a stride of 2 and a pointwise
convolution to perform spatial downsampling and channel dimension modulation,
respectively. Besides, the squeeze-and-excitation [8] layers is utilized for
all stages in a cross-block manner. RepViT shows substantial advantages in
terms of latency in high-resolution vision tasks [21], due to its pure
convolutional architecture. As shown in Table 1, after replacing the ViT-H
image encoder with the RepViT-M2.3 model, RepViT-SAM exhibits a significant
reduction in latency compared with others. On iPhone 12, RepViT-SAM can
perform model inference smoothly. Besides, on Macbook, RepViT-SAM is nearly
10$\times$ faster than MobileSAM.

Following [27], we train the RepViT-SAM by directly distilling the image
encoder, _i.e_., RepViT-M2.3, from the ViT-H in the original SAM [13],
leveraging a simple MSE loss. Like [27], the stride of 2 in the last
downsampling depthwise convolution in RepViT is set to 1 for making the output
resolution compatible with the prompt-guided mask decoder in the original SAM
[13].

##  2 Experiments

###  2.1 Implementation details

RepViT-SAM is trained for 8 epochs under the same setting as [27]. Like
MobileSAM [27], we use only 1% data in the SAM-1B dataset [13]. To expedite
the training process, we precompute and save the image embeddings from the
ViT-H image encoder prior to the distillation phase, which eliminates the need
to run the forward process of ViT-H during distillation, like [27]. We
evaluate the performance of RepViT-SAM on zero-shot edge detection on BSDS500
[17, 1], zero-shot instance segmentation using COCO [14], and segmentation in
the wild benchmark [29] (SegInW), zero-shot video object/instance segmentation
using DAVIS 2017 [18]/UVO v1.0 [23], zero-shot salient object segmentation
using DUTS [22], and zero-shot anomaly detection using MVTec-AD [2], following
[13, 12, 19, 9, 3].

Table 2:  Comparison results on zero-shot edge detection. Bold indicates the best, and underline indicates the second best.  Model | zero-shot edge detection
---|---
ODS | OIS | AP
ViT-H-SAM [13] | .768 | .786 | .794
ViT-B-SAM [13] | .743 | .764 | .726
MobileSAM [27] | .756 | .768 | .746
RepViT-SAM | .764 | .786 | .773

###  2.2 Zero-shot edge detection

Following [13], we utilize a 16$\times$16 regular grid of foreground points as
prompts for the model. We apply NMS to remove redundant masks. Additionally, a
Sobel filter is employed to the unthreshold probability maps of the masks,
along with standard lightweight postprocessing, including edge NMS, as
described in [13]. As shown in Table 2, our RepViT-SAM outperforms MobileSAM
and ViT-B-SAM on all metrics. Compared with ViT-H-SAM, which is the largest
SAM model with over 615M parameters, our small RepViT-SAM can obtain
comparable performance in terms of ODS and OIS.

###  2.3 Zero-shot instance segmentation

We leverage the state-of-the-art H-Deformable-DETR [10] with Swin-L [16] as
the object detector and prompt the model with its output boxes, like [12, 13].
As shown in Table 3, our RepViT-SAM significantly outperforms MobileSAM and
ViT-B-SAM by 1.7 and 1.9 AP, respectively. Besides, it can be observed that
the models obtained by the decoupled distillation strategy, _i.e_., MobileSAM
and RepViT-SAM, typically outperform the model obtained by the coupled
distillation, _i.e_., ViT-B-SAM, on large objects, but exhibits comparatively
poorer performance on small objects. Such phenomenon may be attributed to the
fact that the decoupled distillation strategy enables more transfer of macro-
level visual features but falls short in fine-grained features.

###  2.4 Segmentation in the wild benchmark

We follow [12] to equip the Grounding-DINO [15] as box prompts to evaluate the
model on the zero-shot track. As shown in Table 3, our RepViT-SAM outperforms
MobileSAM and ViT-B-SAM by 2.2 and 1.3 mean AP, respectively. It well
indicates the strong transferability of RepViT-SAM to diverse downstream
segmentation tasks.

Table 3:  Comparison results on zero-shot instance segmentation and
segmentation in the wild benchmark (SegInW). Bold indicates the best, and
underline indicates the second best.

Model | zero-shot instance segmentation | SegInW
---|---|---
AP |  APS |  APM |  APL | Mean AP
ViT-H-SAM [13] | 46.8 | 31.8 | 51.0 | 63.6 | 48.7
ViT-B-SAM [13] | 42.5 | 29.8 | 47.0 | 56.8 | 44.8
MobileSAM [27] | 42.7 | 27.0 | 46.5 | 61.1 | 43.9
RepViT-SAM | 44.4 | 29.1 | 48.6 | 61.4 | 46.1

Table 4:  Comparison results on zero-shot video object segmentation (z.s. VOS) and video instance segmentation (z.s. VIS). Bold indicates the best, and underline indicates the second best.  Model | z.s. VOS | z.s. VIS
---|---|---
$\mathcal{J\&F}$ | $\mathcal{J}$ | $\mathcal{F}$ | AR100
ViT-H-SAM [13] | 77.4 | 74.6 | 80.2 | 28.8
ViT-B-SAM [13] | 71.3 | 68.5 | 74.1 | 19.1
MobileSAM [27] | 71.1 | 68.6 | 73.6 | 22.7
RepViT-SAM | 73.5 | 71.0 | 76.1 | 25.3

###  2.5 Zero-shot video object/instance segmentation

We leverage SAM-PT [19] to evaluate the performance of RepViT-SAM on the
validation splits of DAVIS 2017 [18] and UVO [23] datasets. We simply replace
the original SAM in SAM-PT with our RepViT-SAM, using the CoTracker [11] as
the point tracker without the reinitialization strategy. As shown in Table 4,
on DAVIS 2017, our RepViT-SAM obtains a mean $\mathcal{J\&F}$ score of 73.5,
significantly outperforming MobileSAM and ViT-B-SAM by 2.4 and 2.2,
respectively. Besides, on UVO, RepViT-SAM surpasses MobileSAM and ViT-B-SAM
with considerable margins of 2.6 and 6.2, respectively. These results show the
superiority of RepViT-SAM compared with other lightweight ones is not limited
to image segmentation tasks but can also be extended to video segmentation
tasks.

Table 5:  Comparison results on zero-shot salient object segmentation (z.s. s.o.s.) and zero-shot anomaly detection (z.s. a.d.). Bold indicates the best, and underline indicates the second best.  Model | z.s. s.o.s. | z.s. a.d.
---|---|---
$\mathcal{M}$ $\downarrow$ | $\mathcal{F}_{p}$
ViT-H-SAM [13] | 0.046 | 37.65
ViT-B-SAM [13] | 0.121 | 36.62
MobileSAM [27] | 0.147 | 36.44
RepViT-SAM | 0.066 | 37.96

###  2.6 Zero-shot salient object segmentation

We follow [9] to first leverage RepViT-SAM to generate N potential objects
masks for a given image. Subsequently, we select the most appropriate mask by
evaluating its alignment with the ground truth. The intersection over union
(IoU) score is adopted as the alignment metric. Following [9], we report mean
absolute error (MAE) score. Note that a lower MAE indicates better
segmentation results. As shown in Table 5, our RepViT-SAM shows its
superiority compared with MobileSAM and ViT-B-SAM in terms of MAE score.

###  2.7 Zero-shot anomaly detection

We leverage SAA+ [3] to evaluate the performance of RepViT-SAM on the MVTec-AD
benchmark dataset. We simply replace the original SAM in SAA+ with our RepViT-
SAM. We follow [3] to report max-F1-pixel ($\mathcal{F}_{p}$), which
quantifies the F1-score for pixel-wise segmentation at the optimal threshold.
As shown in Table 5, our RepViT-SAM achieves the best performance in terms of
$\mathcal{F}_{p}$, even outperforming ViT-H-SAM. It indicates that for certain
specific downstream task, the decoupled distilled model can achieve
performance than the original SAM, along with much lower latency, showing the
promising applications of RepViT-SAM.

##  3 Visualization

In Figure 1, we showcase the predicted masks of SAM [13], MobileSAM [27], and
RepViT-SAM with point and box prompts. It shows that RepViT-SAM can generate
high-quality mask predictions similar to SAM across various scenarios, where
MobileSAM may encounter challenges in accurately predicting masks.
Furthermore, we present qualitative comparison results for zero-shot edge
detection in Figure 2. RepViT-SAM effectively produces reasonable edge maps,
achieving performance comparable to SAM. In contrast, MobileSAM may struggle
to generate accurate edge maps in regions that contain intricate details.

##  4 Conclusion

In summary, our RepViT-SAM demonstrates outstanding efficiency while
maintaining impressive transfer performance for various downstream tasks. We
hope that our RepViT-SAM model can serve as a robust baseline for SAM in edge
deployments, showcasing its potential for practical applications.

Figure 1: Mask predictions of SAM, MobileSAM, and RepViT-SAM with point
prompts (top) and box prompts (bottom). Figure 2: Visualization results of
SAM, MobileSAM, and RepViT-SAM for zero-shot edge detection on BSDS500.

## References

  * Arbelaez et al. [2010] Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik.  Contour detection and hierarchical image segmentation.  _IEEE transactions on pattern analysis and machine intelligence_ , 33(5):898–916, 2010.
  * Bergmann et al. [2019] Paul Bergmann, Michael Fauser, David Sattlegger, and Carsten Steger.  Mvtec ad–a comprehensive real-world dataset for unsupervised anomaly detection.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 9592–9600, 2019.
  * Cao et al. [2023] Yunkang Cao, Xiaohao Xu, Chen Sun, Yuqi Cheng, Zongwei Du, Liang Gao, and Weiming Shen.  Segment any anomaly without training via hybrid prompt regularization.  _arXiv preprint arXiv:2305.10724_ , 2023.
  * Chu et al. [2022] Xiangxiang Chu, Liang Li, and Bo Zhang.  Make repvgg greater again: A quantization-aware approach.  _arXiv preprint arXiv:2212.01593_ , 2022.
  * Ding et al. [2021] Xiaohan Ding, Xiangyu Zhang, Ningning Ma, Jungong Han, Guiguang Ding, and Jian Sun.  Repvgg: Making vgg-style convnets great again.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 13733–13742, 2021.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Ghiasi et al. [2021] Golnaz Ghiasi, Yin Cui, Aravind Srinivas, Rui Qian, Tsung-Yi Lin, Ekin D Cubuk, Quoc V Le, and Barret Zoph.  Simple copy-paste is a strong data augmentation method for instance segmentation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 2918–2928, 2021.
  * Hu et al. [2018] Jie Hu, Li Shen, and Gang Sun.  Squeeze-and-excitation networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 7132–7141, 2018.
  * Ji et al. [2023] Wei Ji, Jingjing Li, Qi Bi, Wenbo Li, and Li Cheng.  Segment anything is not always perfect: An investigation of sam on different real-world applications.  _arXiv preprint arXiv:2304.05750_ , 2023.
  * Jia et al. [2023] Ding Jia, Yuhui Yuan, Haodi He, Xiaopei Wu, Haojun Yu, Weihong Lin, Lei Sun, Chao Zhang, and Han Hu.  Detrs with hybrid matching.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 19702–19712, 2023.
  * Karaev et al. [2023] Nikita Karaev, Ignacio Rocco, Benjamin Graham, Natalia Neverova, Andrea Vedaldi, and Christian Rupprecht.  Cotracker: It is better to track together.  _arXiv preprint arXiv:2307.07635_ , 2023.
  * Ke et al. [2023] Lei Ke, Mingqiao Ye, Martin Danelljan, Yifan Liu, Yu-Wing Tai, Chi-Keung Tang, and Fisher Yu.  Segment anything in high quality.  _arXiv preprint arXiv:2306.01567_ , 2023.
  * Kirillov et al. [2023] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al.  Segment anything.  _arXiv preprint arXiv:2304.02643_ , 2023.
  * Lin et al. [2014] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence 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_ , pages 740–755. Springer, 2014.
  * Liu et al. [2023] Shilong Liu, Zhaoyang Zeng, Tianhe Ren, Feng Li, Hao Zhang, Jie Yang, Chunyuan Li, Jianwei Yang, Hang Su, Jun Zhu, et al.  Grounding dino: Marrying dino with grounded pre-training for open-set object detection.  _arXiv preprint arXiv:2303.05499_ , 2023.
  * Liu et al. [2021] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 10012–10022, 2021.
  * Martin et al. [2001] David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik.  A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics.  In _Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001_ , pages 416–423. IEEE, 2001.
  * Pont-Tuset et al. [2017] Jordi Pont-Tuset, Federico Perazzi, Sergi Caelles, Pablo Arbeláez, Alex Sorkine-Hornung, and Luc Van Gool.  The 2017 davis challenge on video object segmentation.  _arXiv preprint arXiv:1704.00675_ , 2017.
  * Rajič et al. [2023] Frano Rajič, Lei Ke, Yu-Wing Tai, Chi-Keung Tang, Martin Danelljan, and Fisher Yu.  Segment anything meets point tracking.  _arXiv preprint arXiv:2307.01197_ , 2023.
  * Sandler et al. [2018] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4510–4520, 2018.
  * Wang et al. [2023] Ao Wang, Hui Chen, Zijia Lin, Hengjun Pu, and Guiguang Ding.  Repvit: Revisiting mobile cnn from vit perspective.  _arXiv preprint arXiv:2307.09283_ , 2023.
  * Wang et al. [2017] Lijun Wang, Huchuan Lu, Yifan Wang, Mengyang Feng, Dong Wang, Baocai Yin, and Xiang Ruan.  Learning to detect salient objects with image-level supervision.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 136–145, 2017.
  * Wang et al. [2021] Weiyao Wang, Matt Feiszli, Heng Wang, and Du Tran.  Unidentified video objects: A benchmark for dense, open-world segmentation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10776–10785, 2021.
  * Wu et al. [2022] Kan Wu, Jinnian Zhang, Houwen Peng, Mengchen Liu, Bin Xiao, Jianlong Fu, and Lu Yuan.  Tinyvit: Fast pretraining distillation for small vision transformers.  In _European Conference on Computer Vision_ , pages 68–85. Springer, 2022.
  * Xiao et al. [2021] Tete Xiao, Mannat Singh, Eric Mintun, Trevor Darrell, Piotr Dollár, and Ross Girshick.  Early convolutions help transformers see better.  _Advances in neural information processing systems_ , 34:30392–30400, 2021.
  * Xiong et al. [2023] Yunyang Xiong, Bala Varadarajan, Lemeng Wu, Xiaoyu Xiang, Fanyi Xiao, Chenchen Zhu, Xiaoliang Dai, Dilin Wang, Fei Sun, Forrest Iandola, et al.  Efficientsam: Leveraged masked image pretraining for efficient segment anything.  _arXiv preprint arXiv:2312.00863_ , 2023.
  * Zhang et al. [2023] Chaoning Zhang, Dongshen Han, Yu Qiao, Jung Uk Kim, Sung-Ho Bae, Seungkyu Lee, and Choong Seon Hong.  Faster segment anything: Towards lightweight sam for mobile applications.  _arXiv preprint arXiv:2306.14289_ , 2023.
  * Zhao et al. [2023] Xu Zhao, Wenchao Ding, Yongqi An, Yinglong Du, Tao Yu, Min Li, Ming Tang, and Jinqiao Wang.  Fast segment anything.  _arXiv preprint arXiv:2306.12156_ , 2023.
  * Zou et al. [2023] Xueyan Zou, Zi-Yi Dou, Jianwei Yang, Zhe Gan, Linjie Li, Chunyuan Li, Xiyang Dai, Harkirat Behl, Jianfeng Wang, Lu Yuan, et al.  Generalized decoding for pixel, image, and language.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15116–15127, 2023.