11institutetext: Indian Statistical Institute, Kolkata, India 22institutetext:
State University of New York at Stony Brook, New York, USA
22email<EMAIL_ADDRESS>
# Covering and Packing of Rectilinear Subdivision

Satyabrata Jana 11 Supantha Pandit The author is partially supported by the
Indo-US Science & Technology Forum (IUSSTF) under the SERB Indo-US
Postdoctoral Fellowship scheme with grant number 2017/94, Department of
Science and Technology, Government of India.22

###### Abstract

We study a class of geometric covering and packing problems for bounded
regions on the plane. We are given a set of axis-parallel line segments that
induces a planar subdivision with a set of bounded (rectilinear) faces. We are
interested in the following problems.

(P1) Stabbing-Subdivision:

Stab all bounded faces by selecting a minimum number of points in the plane.

(P2) Independent-Subdivision:

Select a maximum size collection of pairwise non-intersecting bounded faces.

(P3) Dominating-Subdivision:

Select a minimum size collection of faces such that any other face has a non-
empty intersection (i.e., sharing an edge or a vertex) with some selected
faces.

We show that these problems are $\mathsf{NP}$-hard. We even prove that these
problems are $\mathsf{NP}$-hard when we concentrate only on the rectangular
faces of the subdivision. Further, we provide constant factor approximation
algorithms for the Stabbing-Subdivision problem.

###### Keywords:

Planar subdivision Set cover Independent set Dominating set$\mathsf{NP}$-hard
$\mathsf{PTAS}$.

##  1 Introduction

Set Cover and Independent Set problems are two well-studied problems in across
fields. In Set Cover problem, we are given a set of points and a set of
objects, the goal is to find a minimum collection of objects which covers all
the points. In Independent Set problems we are given a set of objects and find
a maximum collection of a pairwise non-intersecting set of objects. A
Dominating Set problem is a variation of the Set Cover problem. In this
problem, we are given a set of objects and find a minimum collection of
objects such that any remaining object has a non-empty intersection with some
chosen objects.

In this paper, we study a variation of the Set Cover, Independent Set, and
Dominating Set problems. We are given $m$ axis-parallel line segments that
induce a planar subdivision $\mathcal{P}$ with a set $F$ of $n$ bounded
rectilinear faces. We formally define these problems as follows.

(P1) Stabbing-Subdivision: We are given a planar subdivision of $n$ bounded
faces $F$, find a minimum size points in the plane such that each face in $F$
is stabbed.

(P2) Independent-Subdivision: We are given a planar subdivision of $n$ bounded
faces $F$, find a maximum size objects $F^{\prime}\subseteq F$ such that any
pair of objects in $F^{\prime}$ is non-intersecting.

(P3) Dominating-Subdivision: We are given a planar subdivision of $n$ bounded
faces $F$, find a minimum size objects $F^{\prime}\subseteq F$ such that any
objects in $F\setminus F^{\prime}$ has a non-empty intersection with an object
in $F^{\prime}$.

A special case of the Stabbing-Subdivision problem has an application to the
art gallery problem [4]. Suppose a rectangular art gallery is given. The
gallery is subdivided into rectangular rooms. Now the question is “how many
guards are needed to be stationed in the gallery so as to protect all the
rooms?” This problem is nothing but the Stabbing-Subdivision problem where the
input faces are all rectangular. We also consider the rectilinear rooms (the
original input of the Stabbing-Subdivision problem) instead of the rectangular
rooms in a planar subdivision and ask the same question as “how many guards
(also name as representatives) are needed to be stationed in the gallery so as
to protect all of the rectilinear rooms?”.

One thing we need to mention that, in this paper, we sometime use rectangles
to interpret rectangular faces of a subdivision.

###  1.1 Previous Work

Set Cover, Independent Set, and Dominating Set problems are $\mathsf{NP}$-hard
for simple geometric objects such as disks [5], squares [5], rectangles [5],
etc. There is a long line of research of these problems and its various
variants and special cases [7, 13, 12, 2, 1, 11, 3, 14, 10].

Recently, Korman et al. [9] studied an interesting variation of the Set Cover
problem, the Line-Segment Covering problem. In this problem, they cover all
the cells of an arrangement formed by a set of line segments in the plane
using a minimum number of line segments. They showed that the problem is NP-
hard, even when all segments are axis-aligned. In fact,they also proved that
it is $\mathsf{NP}$-hard to cover all rectangular cells of the arrangement by
a minimum number of axis-parallel line segments.

In [6], Gaur et al. studied the rectangle stabbing problem. Here [6] given a
set of rectangles, the objective is to stab all rectangles with a minimum
number of axis-parallel lines. They provided a 2-approximation for this
problem.

Czyzowicz et al. [4] considered the guarding problem in rectangular art
galleries. They showed that if a rectangular art gallery divided into $n$
rectangular rooms, then $\lceil n/2\rceil$ guards are always sufficient to
protect all rooms in that rectangular art gallery. They also extend their
result in non-rectangular galleries and 3-dimensional art galleries [4].

###  1.2 Our Results

In this paper, we present the following results.

  * ➥

We first prove that the Stabbing-Subdivision problem is $\mathsf{NP}$-hard
when we stab all the rectangular faces of the subdivision. Next, we show that
the Stabbing-Subdivision problem is $\mathsf{NP}$-hard. Further, we provide a
2.083-approximation and a $\mathsf{PTAS}$ for this problem. (Section 2)

  * ➥

We prove that the Independent-Subdivision problem is $\mathsf{NP}$-hard when
we consider only the rectangular faces. Then we prove that the Independent-
Subdivision problem is $\mathsf{NP}$-hard. (Section 3)

  * ➥

We prove that the Dominating-Subdivision problem is $\mathsf{NP}$-hard by
considering only the rectangular faces. Next, we prove that the Dominating-
Subdivision problem is $\mathsf{NP}$-hard. (Section 4)

##  2 Stabbing-Subdivision

###  2.1 $\mathsf{NP}$-hardness

In this section, we first prove that the Stabbing-Subdivision problem is
$\mathsf{NP}$-hard when we are restricted to stab only rectangular faces of
the subdivision. Next, we modify the construction to show that the Stabbing-
Subdivision problem is $\mathsf{NP}$-hard. We give a reduction from the
Rectilinear Planar 3SAT (RP3SAT) Problem. Knuth and Raghunathan [8] proved
that this problem is $\mathsf{NP}$-complete. We define this problem as
follows. We are given a 3-SAT formula $\phi$ with $n$ variables
$x_{1},x_{2},\ldots,x_{n}$ and $m$ clauses $C_{1},C_{2},\ldots,C_{m}$ where
each clause contains exactly 3 literals. For each variable or clause take a
rectangle. The variable rectangles are placed on a horizontal line such that
no two of them intersect. The clause rectangles are placed above and below
this horizontal line such that they form a nested structure. The clause
rectangles connect to the variable rectangles by vertical lines such that no
two lines intersect. The objective is to decide whether there is a truth
assignment to the variables that satisfies $\phi$. See Figure 1(a) for an
instance of the RP3SAT problem.

(a)

(b)

Figure 1: (a) An instance of the RP3SAT problem. We only show the clauses
which connect to the variables from above. The solid (resp. dotted) lines
represent that the variable is positively (resp. negatively) present in the
corresponding clauses. (b) Structure of a variable gadget.

We now construct an instance $I$ of Stabbing-Subdivision problem from an
instance $\phi$ of the RP3SAT problem.

Variable gadget: The gadget of $x_{i}$ consists of $8m+4$ vertical and $4$
horizontal line segments. See Figure 1(b) for the construction of the gadget.
The 4 segments $v_{1},v_{4},h_{1}$, and $h_{4}$ together form a rectangular
region $R$. Next, the 2 vertical segments $v_{2}$ and $v_{3}$ partition $R$
vertically into 3 rectangles $R_{1}$, $R_{2}$, and $R_{3}$. Further, two
horizontal segments $h_{2}$ and $h_{3}$ partition $R_{2}$ horizontally into
three rectangles $R_{4}$, $R_{5}$, and $R_{6}$. Finally, the $4m$ vertical
segments $l_{1},l_{2},\ldots,l_{4m}$ partition $R_{4}$ vertically into $4m+1$
small rectangles $r_{1},r_{2},\ldots,r_{4m+1}$. Similarly, the $4m$ vertical
segments $l_{4m+1},l_{4m+2},\ldots,l_{8m}$ partition $R_{6}$ vertically into
$4m+1$ small rectangles $r_{4m+2},r_{4m+3},\ldots,r_{8m+2}$. Finally we have
the total of $8m+5$ rectangles $R_{1},R_{3},R_{5},r_{1},r_{2},\ldots,r_{8m+2}$
inside $R$. Clearly, these rectangles except $R_{5}$ form a cycle of size
$8m+4$. Observe that any point along the cycle can stab at most two
consecutive regions. Therefore there are two optimal solutions
$P^{i}_{1}=\\{p_{1},p_{3},\ldots,p_{8m+3}\\}$ and
$P^{i}_{2}=\\{p_{2},p_{4},\ldots,p_{8m+4}\\}$ each of size $4m+2$ (Note that
these points are not as a part of the input, they are one set of canonical
points.). These two solutions are corresponding to the truth value of $x_{i}$.

Clause gadget: The gadget for the clause $C_{\alpha}$ consists of a single
rectangle $r_{\alpha}$ that is formed by four line segments. The rectangle
$r_{\alpha}$ can be interpreted as the same rectangle as $C_{\alpha}$ in the
RP3SAT-problem instance.

Interaction: Now we describe how the clause gadgets interact with the variable
gadgets. Observe that the description for the clauses which connect to the
variables from above are independent with the clauses which connect to the
variables from below. Therefore, we only describe the construction for the
clauses which connect to the variables from above. Let
$C^{i}_{1},C^{i}_{2},\ldots,C^{i}_{\tau}$ be the left to right order of the
clauses which connect to $x_{i}$ from above. Then we say that $C^{i}_{k}$ is
the $k$th clause for $x_{i}$. For example, $C_{3}$, $C_{2}$, and $C_{4}$ are
the 1st, 2nd, and 3rd clause for the variable $x_{4}$ in Figure 1(a). Let
$C_{\alpha}$ be a clause containing the variable $x_{i},x_{j},x_{t}$. We say
that the clause $C_{\alpha}$ is the ${k_{1}}$, ${k_{2}}$, and ${k_{3}}$th
clause for variable $x_{i}$, $x_{j}$, and $x_{t}$ respectively based on the
above ordering. For example, $C_{3}$ is the 3rd, 1st, and 1st clause for
variable $x_{2}$, $x_{3}$, and $x_{4}$ respectively in Figure 1(a). Let
$r_{\alpha}$ be the rectangle corresponding to $C_{\alpha}$. Now we have the
following cases.

  * $\bullet$

If $x_{i}$ appears as a positive literal in clause $C_{\alpha}$, then extend
the 3 segments $l_{4k_{1}-3}$, $l_{4k_{1}-2}$, and $l_{4k_{1}-1}$ vertically
upward such that it touches the bottom boundary of the rectangle $r_{\alpha}$.

  * $\bullet$

If $x_{i}$ appears as a negative literal in clause $C_{\alpha}$, then extend
the 3 segments $l_{4k_{1}-2}$, $l_{4k_{1}-1}$, and $l_{4k_{1}}$ vertically
upward such that it touches the bottom boundary of the rectangle $r_{\alpha}$.

Figure 2: Variable clause interaction.

The similar construction can be done for $x_{j}$ and $x_{t}$ by replacing
$k_{1}$ with $k_{2}$ and $k_{3}$ respectively. The whole construction is shown
in Figure 2. Note that, we break the horizontal segment $h_{1}$ in the
variable gadgets into smaller intervals and shifted the intervals vertically
along with the extension of the vertical lines. This completes the
construction and clearly, it can be done in polynomial time.

###### Lemma 1

$\phi$ is satisfiable if and only if there is a solution to the Stabbing-
Subdivision problem to stab only rectangular faces with $n(4m+2)$ points.

###### Proof

Assume that $\phi$ is satisfiable i.e., we have a truth assignment of the
variables in $\phi$. Now consider a variable $x_{i}$. If $x_{i}$ is true, we
select the set $P^{i}_{1}$, otherwise we select the set $P^{i}_{2}$. Clearly,
the $n(4m+2)$ selected points corresponding to all variable gadgets stab all
the rectangular faces of the construction.

On the other hand, assume that Stabbing-Subdivision problem has a solution
with $n(4m+2)$ points. Observe that at least $(4m+2)$ points are needed to
stab all the faces of a variable gadget. Since the rectangular faces of
variable gadgets are disjoint from each other, exactly $(4m+2)$ points must be
selected from each variable gadget. Now there are exactly two solutions of
size $(4m+2)$, either $P_{1}^{i}$ or $P_{2}^{i}$. Therefore, we set variable
$x_{i}$ to be true if $P_{1}^{i}$ is selected from the gadget of $x_{i}$,
otherwise we set $x_{i}$ to be false. Note that for each clause $C_{\alpha}$
the six faces corresponding to three literals it contains, touches the
rectangle $r_{\alpha}$. Since $r_{\alpha}$ is stabbed, at least one of the
selected points must be chosen in the solution. Such a point is either in one
of the sets $P^{i}_{1}$ or $P_{2}^{i}$ of the corresponding variable gadget
based on whether the variable is positively or negatively present in that
clause. Hence, the above assignment is a satisfying assignment. ∎

###### Theorem 1

The Stabbing-Subdivision problem is $\mathsf{NP}$-hard for stabbing only
rectangular faces of a subdivision.

The Stabbing-Subdivision problem for stabbing all rectilinear faces: We now
prove that it is also $\mathsf{NP}$-hard to stab all (rectilinear) faces of a
subdivision. We modify the above $\mathsf{NP}$-hardness to prove the hardness.
Note that, after embedding the gadgets on the plane, the subdivision creates
three types of faces, (i) variable faces: the faces interior to a variable
gadget (note that all variable faces are rectangular), (ii) clause faces:
rectangular faces associated with clause gadgets, and (iii) outer faces: faces
that are not included to any of (i) or (ii).

Note that, in the proof of the Lemma 1, we assume that the canonical points
(set of $4m+2$ points to stab $8m+5$ rectangles in a variable gadget) are on
the lines $h_{2}$ and $h_{3}$ (see Figure 1(b)). However, in this case, we
keep only one point either on $h_{2}$ or on $h_{3}$ (to stab the rectangle
$R_{5}$) and out of the remaining points that are on $h_{2}$ we shift them
vertically upward to $h_{1}$ and that are on $h_{3}$ we shift them vertically
downward to $h_{4}$. Clearly, any outer face includes some variable canonical
points. Hence, with this modification, it is immediate that the Lemma 1 is
true even when we are restricted to stab all the faces of the subdivision.

###  2.2 Approximation algorithms

####  2.2.1 Factor 2.083 approximation

We are given $m$ axis-parallel line segments that induce a planar subdivision
$\mathcal{P}$ with a set $F$ of $n$ bounded rectilinear faces. To provide the
approximation algorithm, we transform any instance of the Stabbing-Subdivision
problem into an instance of the Set Cover problem where the size of each set
is at most 4. Observe that, there exists an optimal solution to the Stabbing-
Subdivision problem that only contains vertices of $\mathcal{P}$ (we can call
them as corner points of $F$). Also, any corner point of $F$ can stab at most
$4$ rectilinear faces in $\mathcal{P}$.

We now create an instance of the Set Cover problem as follows. The set of
elements is the set of all faces and the collection is all sets of faces
corresponding to the corner points of $F$. Note that each set in the
collection is of size at most 4, since any corner point can stab at most 4
faces. This Set Cover instance admits a 2.083 ($H_{4}$ i.e., harmonic series
sum of the first 4 terms) factor approximation [15]. Hence we have the
following theorem.

###### Theorem 2

There exists a $2.083$ factor approximation algorithm for Stabbing-Subdivision
problem in a planar subdivision by rectilinear line segments.

###  2.3 PTAS via Local Search Algorithm

In this section, we show that a local search framework [13] leads to a
$\mathsf{PTAS}$ for the Stabbing-Subdivision problem. We are given a planar
subdivision with a set $F$ of $n$ bounded faces. Note that, we can choose
points only from the vertex set $V$ of the subdivision. Therefore, ${\cal
R}=(V,F)$ be the given range space. Clearly $V$ is a feasible solution to the
Stabbing-Subdivision problem. We apply the $k$-level local search ($k$ is a
given parameter) as follows.

  1. 1.

Let $X$ be some feasible solution to the Stabbing-Subdivision problem
(initially take $X$ as $V$).

  2. 2.

Do the following:

    1. (a)

Search for $X^{\prime}\subseteq X$ and $Y$ such that $|Y|\subseteq V$,
$|Y|<|X^{\prime}|\leqslant k$ and $(X\setminus X^{\prime})\cup Y$ is a
feasible solution.

    2. (b)

If such $X^{\prime}$ and $Y$ exist, update $X$ with $(X\setminus
X^{\prime})\cup Y$ and repeat the above step. Otherwise, return $X$ and stop.

It is easy to see that the running time of the algorithm is polynomial.
Further, the local search algorithm always returns a local optimum solution. A
feasible solution $X$ is said to be a local optimum if there is no
$X^{\prime}$ exists in Step 2(a) in the above algorithm. We show that given
any $\epsilon>0$, a $O(1/\epsilon^{2})$-level local search returns a hitting
set of size at most $(1+\epsilon)$ times an optimal hitting set for $\cal R$.

Locality condition ([13]): A range space $\cal R$ $=(V,F)$ satisfies the
locality condition if for any two disjoint subsets $R,B\subseteq V$, it is
possible to construct a planar bipartite graph $G=(R\cup B,E)$ with all edges
going between $R$ and $B$ such that for any $f\in F$, there exist two vertices
$u\in f\cap R$ and $v\in f\cap B$ such that edge $(u,v)\in E$.

###### Theorem 3

[13] Let $\cal R$ $=(V,F)$ be a range space satisfying the locality condition.
Let $R\subseteq V$ be an optimal hitting set for $F$, and $B\subseteq V$ be
the hitting set returned by a $k$-level local search. Furthermore, assume
$R\cap B=\phi$. Then there exists a planar bipartite graph $G=(R\cup B,E)$
such that for every subset $B^{\prime}\subseteq B$ of size at most $k$,
$|N_{G}(B^{\prime})|\geq|B^{\prime}|$ where $N_{G}(W)$ denotes the set of all
neighbours of the vertices of $W$ in $G.$

The following lemma implies that given any $\epsilon>0$, a $k$-level local
search with $\epsilon=\dfrac{c}{\sqrt{k}}$ gives a
$(1+\epsilon)$-approximation for the Stabbing-Subdivision problem.

###### Lemma 2

[13] Let $G=(R\cup B,E)$ be a bipartite planar graph on red and blue vertex
sets $R$ and $B$, $|R|\geq 2$, such that for every subset $B^{\prime}\subseteq
B$ of size at most $k$, where $k$ is a large enough number,
$|N_{G}(B^{\prime})|\geq|B^{\prime}|$. Then
$|B|\leq(1+\dfrac{c}{\sqrt{k}})|R|$, where $c$ is a constant.

$\mathsf{PTAS}$ for the Stabbing-Subdivision problem: Let $R$ (red) and $B$
(blue) be disjoint subsets of the vertices in planar subdivision $\mathcal{P}$
where $R$ and $B$ be an optimum solution and the solution returned by the
$k$-level local search respectively. For simplicity, we assume that $R\cap
B=\phi$. Otherwise, we can remove the common elements from each of $R$ and
$B$, and then do the similar analysis. As we remove the same number of
elements from both $R$ and $B$, the approximation ratio of the original
instance is at most the approximation ratio of the restricted one. We
construct the required graph $G$ on the vertices $R\cup B$ in the following
way. Since $R$ and $B$ are feasible solutions of the Stabbing-Subdivision
problem, every face $f\in F$ must contain at least one red and one blue point.
We simply join exactly one pair of red and blue points by an edge for each
face $f\in F$. Clearly, the edge for a face $f\in F$ lies completely inside
$f$. Therefore $G$ becomes a planar bipartite graph and hence $\cal R$
satisfies the locality condition. Therefore, from Theorem 3 and Lemma 2, we
say that the Stabbing-Subdivision problem admits a $\mathsf{PTAS}$.

##  3 Independent-Subdivision

In this section, we prove that the Independent-Subdivision problem is
$\mathsf{NP}$-hard by giving a reduction from the RP3SAT problem. The
reduction follows the same line of the reduction presented in Section 2. We
construct an instance $I$ of the Independent-Subdivision problem from an
instance $\phi$ of the RP3SAT problem and prove that the construction is
correct.

Variable gadget: The variable gadget is similar to the variable gadget that is
described in the Section 2. See Figure 3 for the construction of a variable
gadget. The difference of this variable gadget from the gadget in the Section
2 is that we partition $R_{4}$ into $4m-2$ smaller rectangles
$r_{1},r_{2},\ldots,r_{4m-2}$ and $R_{6}$ into $4m-2$ smaller rectangles
$r_{4m-1},r_{4m},\ldots,r_{8m-4}$. Finally, we have the total of $8m-1$
rectangles $R_{1},R_{3},R_{5},r_{1},r_{2},\ldots,r_{8m-4}$ inside $R$. Notice
that, these rectangles except $R_{5}$ form a cycle of size $8m-2$. Therefore
there are exactly two optimal solutions
$S^{i}_{1}=\\{R_{3},r_{1},r_{3},\ldots,r_{4m-3},r_{4m},r_{4m+2},\ldots,r_{8m-4}\\}$
and
$S^{i}_{2}=\\{R_{1},r_{2},r_{4},\ldots,r_{4m-2},r_{4m-1},r_{4m+1},\ldots,r_{8m-5}\\}$,
each with size $4m-1$. These two solutions are corresponding to the truth
values of the variable $x_{i}$.

Figure 3: Structure of a variable gadget.

Clause gadget: The gadget of the clause $C_{\alpha}$ includes 9 rectangles
$r_{\alpha}^{1},r_{\alpha}^{2},\ldots,r_{\alpha}^{9}$ (see green rectangles in
Figure 4. The six rectangles
$r_{\alpha}^{4},r_{\alpha}^{5},\ldots,r_{\alpha}^{9}$ are placed inside the
rectangle of $C_{\alpha}$ in the RP3SAT-problem instance and the other three
rectangles $r_{\alpha}^{1},r_{\alpha}^{2},r_{\alpha}^{3}$ are corresponding to
the three vertical legs between $C_{\alpha}$ and the three variables it
contains. Note that there is another rectangle present in the clause gadget
bounded by the above 9 rectangles. However, this rectangle has no effect in
the reduction, since picking this rectangle makes other 9 rectangles invalid
(can not be selected).

Interaction: Here also we describe the construction for the clauses that
connect to the variables from above, since the construction is similar and
independent from the clauses that connect to the variables from below. Let
$C_{\alpha}$ be a clause containing the variables $x_{i},x_{j},x_{t}$. Also
assume that this is the left to right order of these variables in which they
appear in $\phi$. Using the similar way as before (Section 2), we say that the
clause $C_{\alpha}$ is the ${k_{1}}$, ${k_{2}}$, and ${k_{3}}$th clause for
the variables $x_{i}$, $x_{j}$, and $x_{t}$ respectively.

  * $\bullet$

If $x_{i}$ appears as a positive literal in the clause $C_{\alpha}$, then
attach the rectangle $r_{\alpha}^{1}$ to the rectangle $r_{4k_{1}-3}$.

  * $\bullet$

If $x_{i}$ appears as a negative literal in clause $C_{\alpha}$, then attach
the rectangle $r_{\alpha}^{1}$ to the rectangle $r_{4k_{1}-2}$.

The similar construction can be done for $x_{j}$ by replacing $r_{\alpha}^{1}$
and $k_{1}$ with $r_{\alpha}^{2}$ and $k_{2}$ respectively and for $x_{t}$ by
replacing $r_{\alpha}^{1}$ and $k_{1}$ with $r_{\alpha}^{3}$ and $k_{3}$
respectively. The whole construction is depicted in Figure 4. Clearly, the
construction can be done in polynomial time. We now prove the correctness of
the construction.

Figure 4: Variable clause interaction.

###### Lemma 3

$\phi$ is satisfiable if and only if there is a solution of size $n(4m-1)+4m$
to Independent-Subdivision problem while considering only rectangular faces.

###### Proof

Assume that $\phi$ has a satisfying assignment. For the variable $x_{i}$, if
$x_{i}$ is true, select the set $S^{i}_{2}$, otherwise select the set
$S^{i}_{1}$. Since each set is of cardinality $(4m-1)$, clearly we select
$n(4m-1)$ independent rectangles across all variable gadgets. Now let
$C_{\alpha}$ be a clause containing variables $x_{i},x_{j},x_{t}$. Since
$C_{\alpha}$ is satisfiable at least one of the three rectangles
$r_{\alpha}^{1},r_{\alpha}^{2},r_{\alpha}^{3}$ is free to choose in a
solution. This implies we can select exactly 4 rectangles from the gadget of
$C_{\alpha}$. We can picked 4 rectangles independently from each clause
gadget. Hence, in total we can select $n(4m-1)+4m$ rectangles.

On the other hand, assume that the Independent-Subdivision problem has a
solution $S$ with $n(4m-1)+4m$ rectangles. Note that for each variable gadget
the size of an optimal independent set is $(4m-1)$, either the set $S_{1}^{i}$
or $S_{2}^{i}$. We set the variable $x_{i}$ to be true if $S_{2}^{i}$ is
selected from the gadget of $x_{i}$, otherwise we set $x_{i}$ to be false. Now
we have to show that this assignment is a satisfying assignment for $\phi$
i.e, each clause of $\phi$ is satisfied. Since the variable gadgets are
independent, there are at most $n(4m-1)$ rectangles from the variable gadgets
belongs to $S$. Also since the size of the solution is $n(4m-1)+4m$, from each
clause gadget exactly 4 rectangles is in $S$. Let $C_{\alpha}$ be a clause
containing variables $x_{i},x_{j},x_{t}$. As there are 4 independent
rectangles from the set
$\\{r_{\alpha}^{1},r_{\alpha}^{2},\ldots,r_{\alpha}^{9}\\}$, so one must be
from the set $\\{r_{\alpha}^{1},r_{\alpha}^{2},r_{\alpha}^{3}\\}$ that is in
the given solution. W.l.o.g. let $r_{\alpha}^{1}$ be present, then surely
$x_{i}$ is a true variable as our assignment. Hence the above assignment is a
satisfying assignment. ∎

###### Theorem 4

The Independent-Subdivision problem is $\mathsf{NP}$-hard by considering only
rectangular faces of a subdivision.

The Independent-Subdivision problem for all rectilinear faces: We now prove
that it is also $\mathsf{NP}$-hard to find a maximum independent set of
rectilinear faces in a subdivision. After embedding the construction on the
plane, the subdivision creates three types of faces, (i) variable faces: The
faces that are interior to a variable gadget, (ii) clause faces: the faces
associated with the clause gadgets, and (iii) outer faces: any other faces
that are not included to any of (i) or (ii).

Visualize that we are attaching each clause gadget one by one with the
variable gadgets. Then each clause gadget creates two additional rectilinear
faces, both sides of the rectangle corresponding to the middle leg. Note that,
each such face is adjacent with at least 4 clause rectangles and at least 4
variable rectangles. Therefore, picking one of these new faces to the optimal
solution makes the solution size strictly less than the original. Therefore,
even if we consider all rectilinear faces, Lemma 3 holds and so Theorem 4.

##  4 Dominating-Subdivision

In this section, we prove that the Dominating-Subdivision problem is
$\mathsf{NP}$-hard. We give a reduction from the RP3SAT problem similar to
Section 3.

We construct an instance $I$ of the Dominating-Subdivision problem from an
instance $\phi$ of the RP3SAT problem and prove that the construction is
correct.

Variable gadget: Variable gadgets are similar to the variable gadgets that is
described in Section 2. The difference between this variable gadget and that
of in Section 2 is as follows. We partition $R_{4}$ into $3m+1$ small
rectangles $r_{1},r_{2},\ldots,r_{3m+1}$ and $R_{6}$ into $3m+1$ small
rectangles $r_{3m+4},r_{3m+5},\ldots,r_{6m+4}$. We partition $R_{1}$ into two
rectangles $r_{6m+6}$, $r_{6m+5}$ and $R_{3}$ into $r_{3m+2}$, $r_{3m+3}$.
Next we take $2m+2$ mutually independent rectangles
$s_{1},s_{2},\ldots,s_{2m+2}$ inside $R_{5}$ such that rectangle $s_{i}$
touches the two regions $r_{3i-2}$ and $r_{3i-1}$, for $1\leq i\leq 2m+2$.
Finally we have a total of $8m+8$ rectangles
$r_{1},r_{2},\ldots,r_{6m+6},s_{1},s_{2},\ldots,s_{2m+2}$ inside $R$. Figure 5
illustrate the construction of a variable gadget just described.

Figure 5: Structure of a variable gadget.

###### Lemma 4

There exists exactly two optimal dominating sets of rectangles,
$D_{1}^{i}=\\{r_{1},r_{4},\ldots,r_{6m+4}\\}$ and
$D_{2}^{i}=\\{r_{2},r_{5},\ldots,r_{6m+5}\\}$, for the gadget of $x_{i}$.

###### Proof

There is no rectangle that can dominate more than 4 rectangles. Since there
are in total $(8m+8)$ rectangles, any dominating set cannot have size less
than $(2m+2)$. Further, both $D_{1}^{i}$ and $D_{2}^{i}$, each of size
$(2m+2)$, dominate all the faces of the subdivision and hence they are optimal
solutions. Now we show that there is no other optimal solution.

Clearly, no rectangle of the form $r_{3k}$ or $s_{k}$ where $1\leq
k\leq(2m+2)$ can be a part of an optimal solution, since each of them
dominates exactly 3 rectangles. As a result, any optimal solution contains
only rectangles of the form $r_{3k-1}$ or $r_{3k-2}$, for $1\leq k\leq(2m+2)$.
Also, two rectangles, one of the form $r_{3k-1}$ and other of the form
$r_{3k-2}$, together cannot be a part of any optimal solution. ∎

Clause gadget: The gadget for the clause $C_{\alpha}$ is a rectangle
$r_{\alpha}$ (Figure 6).

Interaction: Here we describe the construction for the clauses that connect to
the variables from above. A similar construction can be done for the clauses
that connect to the variables from below. As before, we interpret $C_{\alpha}$
that contains variables $x_{i}$, $x_{j}$, and $x_{t}$ as the ${k_{1}}$,
${k_{2}}$, and ${k_{3}}$th clause for the variables $x_{i}$, $x_{j}$, and
$x_{t}$ respectively.

  * $\bullet$

If $x_{i}$ appears as a positive literal in the clause $C_{\alpha}$, then we
extend the rectangle $r_{3k_{1}-1}$ vertically upward such that it touches the
rectangle $r_{\alpha}$.

  * $\bullet$

If $x_{i}$ appears as a negative literal in the clause $C_{\alpha}$, then we
extend the rectangle $r_{3k_{1}-2}$ vertically upward such that it touches the
rectangle $r_{\alpha}$.

We make the similar construction for $x_{j}$ and $x_{t}$ by replacing $k_{1}$
with $k_{2}$ and $k_{3}$ respectively. The whole construction is depicted in
Figure 6. Clearly, the construction can be done in polynomial time. We now
prove the correctness.

Figure 6: Variable clause interaction.

###### Lemma 5

$\phi$ is satisfiable if and only if there is a solution of size $n(2m+2)$ to
the Dominating-Subdivision problem while considering only rectangular faces.

###### Proof

Assume that $\phi$ is satisfiable i.e., we have a truth assignment to the
variables of $\phi$. For the variable $x_{i}$, if $x_{i}$ is true we select
the set $D^{i}_{2}$, otherwise we select the set $D^{i}_{1}$. Clearly, the
$n(2m+2)$ selected rectangles corresponding to all the variable gadgets
dominate all the rectangular faces of the subdivision.

On the other hand, assume that the Dominating-Subdivision problem has a
solution with $n(2m+2)$ rectangles. Observe that at least $(2m+2)$ rectangles
are needed to dominate all the rectangular faces of a variable gadget. Since
the rectangular faces of variable gadgets are disjoint from each other and the
size of the solution is $n(2m+2)$, from each variable gadget exactly $(2m+2)$
rectangles must be selected. Therefore, we set variable $x_{i}$ to be true if
$D_{2}^{i}$ is selected from the gadget of $x_{i}$, otherwise we set $x_{i}$
to be false. Note that for each clause $C_{\alpha}$ the three rectangles
corresponding to the three literals it contains attach to the rectangle
$r_{\alpha}$. Since $r_{\alpha}$ is dominated, at least one of these three
rectangles is chosen in the solution. Such a rectangle is either in
$D^{i}_{2}$ or $D_{1}^{i}$ of the corresponding variable gadget based on
whether the variable is positively or negatively present in that clause.
Hence, the above assignment is a satisfying assignment. ∎

###### Theorem 5

The Dominating-Subdivision problem is $\mathsf{NP}$-hard when we are
constrained to dominate all the rectangular faces of a subdivision.

The Dominating-Subdivision problem for all rectilinear faces: We only modify
the variable gadgets such that it has exactly two distinct optimal

Figure 7: Modified variable gadget.

solutions and the rest of the construction and the proofs remain the same. We
take $2m+2$ rectangles $b_{1},b_{2},\ldots,b_{2m+2}$. We place the rectangle
$b_{i}$ in between the rectangles $r_{3i-2}$ and $r_{3i-1}$, for $1\leq i\leq
2m+2$ of the variable gadget shown in Figure 5 (see Figure 7). These
additional rectangles enforce not to choose $R_{5}$ in an optimal solution.
Now it is easy to verify that the Lemma 4 remains true for this modified
gadget even when we consider all the bounded faces of the subdivision.

## References

  * [1] Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: FOCS. pp. 400–409 (2013)
  * [2] Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry 48(2), 373–392 (2012)
  * [3] Chuzhoy, J., Ene, A.: On approximating maximum independent set of rectangles. In: FOCS. pp. 820–829 (2016)
  * [4] Czyzowicz, J., Rivera-Campo, E., Santoro, N., Urrutia, J., Zaks, J.: Guarding rectangular art galleries. Discrete Applied Mathematics 50(2), 149–157 (1994)
  * [5] Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Information Processing Letters 12, 133 – 137 (1981)
  * [6] Gaur, D.R., Ibaraki, T., Krishnamurti, R.: Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. Journal of Algorithms 43(1), 138–152 (2002)
  * [7] Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130–136 (1985)
  * [8] Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM Journal on Discrete Mathematics 5(3), 422–427 (1992)
  * [9] Korman, M., Poon, S.H., Roeloffzen, M.: Line segment covering of cells in arrangements. Information Processing Letters 129, 25–30 (2018)
  * [10] van Leeuwen, E.J.: Optimization and approximation on systems of geometric objects. Ph.D. thesis, University of Amsterdam (2009)
  * [11] Mudgal, A., Pandit, S.: Covering, hitting, piercing and packing rectangles intersecting an inclined line. In: COCOA. pp. 126–137 (2015)
  * [12] Mustafa, N.H., Raman, R., Ray, S.: Settling the APX-hardness status for geometric set cover. In: FOCS. pp. 541–550 (2014)
  * [13] Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete & Computational Geometry 44(4), 883–895 (2010)
  * [14] Pandit, S.: Dominating set of rectangles intersecting a straight line. In: Canadian Conference on Computational Geometry, CCCG. pp. 144–149 (2017)
  * [15] Vazirani, V.V.: Approximation algorithms. Springer (2001)


# IB-U-Nets: Improving medical image segmentation tasks with 3D Inductive
Biased kernels

Shrajan Bhandary1, Zahra Babaiee1, Dejan Kostyszyn2, 3, 4, Tobias Fechter2, 3,
4, Constantinos Zamboglou2, 3, 4, 5, Anca-Ligia Grosu2, 3, 4, Radu Grosu1

###### Abstract

Despite the success of convolutional neural networks for 3D medical-image
segmentation, the architectures currently used are still not robust enough to
the protocols of different scanners, and the variety of image properties they
produce. Moreover, access to large-scale datasets with annotated regions of
interest is scarce, and obtaining good results is thus difficult. To overcome
these challenges, we introduce IB-U-Nets, a novel architecture with inductive
bias, inspired by the visual processing in vertebrates. With the 3D U-Net as
the base, we add two 3D residual components to the second encoder blocks. They
provide an inductive bias, helping U-Nets to segment anatomical structures
from 3D images with increased robustness and accuracy. We compared IB-U-Nets
with state-of-the-art 3D U-Nets on multiple modalities and organs, such as the
prostate and spleen, using the same training and testing pipeline, including
data processing, augmentation and cross-validation. Our results demonstrate
the superior robustness and accuracy of IB-U-Nets, especially on small
datasets, as is typically the case in medical-image analysis. IB-U-Nets source
code and models are publicly available.

## Introduction

Manual segmentation of organs from medical images is an essential tool for
diagnosis, treatment, and progression monitoring of several diseases
(Goldenberg, Nir, and Salcudean 2019; Spohn et al. 2021; Singh et al. 2020;
Antonelli et al. 2022; Isensee et al. 2021). Unfortunately, manual
segmentation is time-consuming and underlies significant interobserver
heterogeneity (Rischke et al. 2013; Steenbergen et al. 2015). Fortunately,
recent advances in deep learning (DL) hold a great promise for automatic
segmentation. Since the success of AlexNet (Krizhevsky, Sutskever, and Hinton
2012), the biomedical-imaging community has been investigating various
convolutional neural-network architectures (CNN) to enhance cancer-detection
efficiency (Singh et al. 2020). In particular, U-Nets yielded most accurate
segmentation on medical datasets (Ronneberger, Fischer, and Brox 2015), first
in 2D and later on in 3D medical-imaging scenarios (Çiçek et al. 2016).
However, the U-Nets currently in use are still not sufficiently robust to
images obtained from different scanners, to shape variability, and to poor
tissue contrast of some organs (Gillespie et al. 2020). Moreover, the
segmentation accuracy of U-Nets still leaves room for improvement, especially
in small-sized 3D datasets (Litjens et al. 2017; Isensee et al. 2021).

Figure 1: Extending U-Net variants with two 3D inductive biases, On and Off
center-surround convolution respectively, enhances their segmentation accuracy
and robustness to distribution shifts.

In this paper we address the above limitations, by enhancing state-of-the-art
(SOTA) 3D U-Nets, with an inductive bias (IB) inspired by the retinal-
processing pathways of vertebrates. In particular, we add two 3D residual
components (an on- and an off-center-surround convolution, with predefined
weights) to the second encoder blocks of U-Nets (in parallel to the max-
pooling component), as depicted in Figure 1. The IB provided by these
components, helps the U-Nets to scrutinize and delineate anatomical structures
of 3D images with increased precision, as shown in Figure 2.

For a comprehensive analysis, we implemented several alternative architectures
with IB extensions and evaluated robustness against changes in parameter
values.

Figure 2: Comparison of the attention maps between the nnU-Net and IB-nnU-Net
for volumes with a significant difference in accuracy. (a) The raw MR and CT
images with annotated regions of interest – in PROMISE-prostate the red
contour is the prostate, and in MSD-spleen the purple contour is the spleen.
(b) The attention maps of nnU-Net for the given input volume. The white box in
the attention map of nnU-Net for the PROMISE-prostate input signifies the area
that should not have been activated. Whereas, the red arrows in the attention
map for the MSD-spleen image denote sections missed by the model. (c) The
attention maps of IB-nnU-Net for the given input volume. (d) Final predictions
made by the networks for each task; green and yellow contours correspond to
outputs of nnU-Net and IB-nnU-Net, respectively.

To demonstrate the general applicability of our method we performed
experiments on 3D medical multi modal image datasets containing unique organs.
A limiting factor in multiple clinical studies is the low number of datasets
available for training. To address this issue, we conducted multiple
experiments with varying number of training datasets to test clinical
suitability. We performed our experiments on two prostate-contour-annotated
datasets: PROMISE-12 and MSD-prostate. PROMISE-12 (prostate MRI segmentation
2012) challenge (Litjens et al. 2014) and MSD-prostate (medical segmentation
decathlon) (Simpson et al. 2019; Antonelli et al. 2021, 2022) are two of the
most widely used and publicly available datasets. Additionally, we carried out
experiments with the spleen dataset from medical segmentation decathlon (MSD-
spleen) (Simpson et al. 2019; Antonelli et al. 2021, 2022). We created a
framework, similar to the design principles of other popular frameworks such
as MONAI (Consortium 2020) and nnU-Net (Isensee et al. 2021), to objectively
compare and evaluate different U-Net variants. We also extended the U-Net
architecture of the nnU-Net with the IB kernels to examine their effectiveness
on a strong and versatile medical segmentation baseline. In particular, we
provide our results for U-Nets (nnU-Net), Attention-U-Nets (Oktay et al. 2018)
and SegResNets (Litjens et al. 2017), and their IB-extensions, as these
networks had the highest accuracy in our experiments. The 3D IB filters are
modular, independent, and easily deployable to any existing U-Net
architecture. Our extension of SOTA U-Nets shows an increased performance in
automatic organ segmentation from 3D MR and CT images and superior robustness
for small datasets.

In summary our paper: (1) Introduces novel 3D inductive biase (IB) and shows
how to use them in U-Net variations for optimal performance. (2) Extends nnU-
Nets, Attention-U-Nets and SegResNets with the above IB and shows superior
accuracy and robustness on datasets of multiple organs with different
modalities.

## Related Work

### U-Net Variations.

This paper is mainly concerned with U-Nets (Ronneberger, Fischer, and Brox
2015; Çiçek et al. 2016) and their variations (Isensee et al. 2021; Oktay et
al. 2018; Myronenko 2019; Milletari, Navab, and Ahmadi 2016), as they are the
most popular biomedical-segmentation architecture in recent times. U-Nets have
an encoder-decoder structure, where the encoder acts as a classifier
identifying key features. In contrast, the decoder reconstructs the image from
its low-dimensional discriminative features to its original pixel-level space.
One of the variants named V-Net (Milletari, Navab, and Ahmadi 2016) replaces
the U-Nets pooling layers with down/up convolutions for smaller memory
footprint during training and introduce skip connections within every encoder
block to improve convergence and learn residual functions. An alternative
called Attention-U-Net (Oktay et al. 2018) employs an attention-gate module to
automatically learn to emphasize target structures of varying shapes and
sizes.

SegResNet (Myronenko 2019) is another variation of the U-Net that has a
segmentation architecture similar to V-Nets, but in addition uses a
variational auto-encoder (VAE) branch. A VAE branch reconstructs the input
image in order to regularize the shared decoder and impose additional
constraints on its layers. On the other hand, the nnU-Net framework (Isensee
et al. 2021) provides robust, and self-adapting networks based on 2D and 3D
vanilla U-Nets, and a U-Net cascade. nnU-Net is the most widely used framework
in medical image analysis after it achieved the first rank in multiple
challenges.

### Medical-Image Segmentation

#### Prostate-gland segmentation.

Over the past decade, significant research has been devoted to automatic
segmentation of the prostate from MRIs (Gillespie et al. 2020). The original
V-Net was trained on the PROMISE-12 dataset, where it achieved top results
using dice loss and the model’s performance was determined by an overlap-based
metric called dice similarity coefficient (DSC) (Milletari, Navab, and Ahmadi
2016). Ghavami et al. (2019) conducted a survey with four U-Net variants
trained on a 3D MR dataset of 232 prostate patient volumes, and the results
show that a statistically significant difference exists in the performances of
these models. Tian et al. (2020) investigated an interactive segmentation
approach by using a graph CNN to predict the prostate gland from the
PROMISE-12 dataset. The nnU-Net framework (Isensee et al. 2021) achieved
superior performance in prostate segmentation from PROMISE-12 and prostate-MSD
datasets.

#### Spleen segmentation.

Several studies have applied DL approaches to segment spleen from medical
images (Altini et al. 2022). Gibson et al. (2018) proposed an encoder-decoder
model called Dense V-Network for segmenting eight organs, including the
spleen. The architecture of the Dense V-Network is similar to the U-Net, with
the exception that they used dense blocks during the encoding path and
bilinear upsampling in the decoding path. The nnU-Net framework (Isensee et
al. 2021) again secured the top place for segmenting spleen from the MSD
dataset. Inspired by the success of transformers for natural language
processing, Hatamizadeh et al. (2022) proposed a new architecture called UNEt
TRansformers (UNETR). While retaining the shape of the U-Net and without
relying on convolutional layers for feature extraction, the UNETR uses a pure
vision transformer as its encoder. The UNETR achieved good results on multi-
organ segmentations, including the MSD-spleen segmentation task.

Based on previous works, it is evident that CNN based DL algorithms such as
U-Nets are efficient in automatically segmenting organs from medical images.

### Biologically Inspired Architectures

#### Vision models.

Initially, these models were inspired by neuroscience and psychology. In the
meantime, both neuroscience and artificial intelligence (AI), particularly
computer vision, have enormously progressed. However, most of today’s neural
networks remained only loosely inspired by the visual system. The interaction
between the fields has become less common, compared to the early age of AI,
despite the importance of neuroscience in generating insightful ideas for AI
(Brooks et al. 2012; Hassabis et al. 2017). One line of inquiry remained in
the search for neuroscience-inspired enhancements of CNN architectures to
increase their interpretability and robustness (Nayebi et al. 2018; Li et al.
2019; Dapello et al. 2020; Babaiee et al. 2021). In (Nayebi et al. 2018),
local recurrence within cortical areas and long-range feedback from downstream
areas to upstream areas are exploited in the design of novel recurrent CNNs,
to increase interpretability and improve classification performance.

Li et al. (2019) proposed a new regularization technique of CNNs, which uses
large-scale neuroscience data to learn more robust neural features in terms of
representational similarity. In Dapello et al. (2020), a CNN architecture
whose hidden layers better match with the primate primary visual cortex is
proposed, which is more robust to adversarial attacks, such as imperceptibly
small and explicitly crafted perturbations. Finally, the authors of Babaiee et
al. (2021) added 2D On and Off center-surround parallel pathways present in
the retina of vertebrates to CNNs and improved the robustness of image
classification. This paper draws inspiration from U-Net variations and Babaiee
et al. (2021) to design a medical-image segmentation architecture that can
learn accurate and robust prostate segmentation from small 3D medical
datasets.

Figure 3: Different geometrical representations of the IB kernels. (a)
Spherical On and Off 3D center-surround receptive fields. (b) The 3D IB-On
cubic kernel. The 3D-IB Off cubic kernel is complimentary; all its signs are
inverted. Figure 4: A qualitative accuracy comparison of vanilla U-Nets and
their IB extended variants on the prostate and spleen segmentation tasks. IB-
nnU-Nets perform the best.

## Inductive Biases in U-Net Variations

This section first shows how we compute the two 3D IB kernels. We then discuss
how to extend the architecture of U-Net variations with the two inductive-bias
kernels.

### The Design of the 3D-IB Kernels

Receptive fields in the primate retina are captured with a difference of two
Gaussians (DoG) (Rodieck 1965). For 2D kernels, Equation 1 computes the center
and surround weights (Kruizinga and Petkov 2000; Petkov and Visser 2005):

$DoG_{\sigma,\gamma}(x,y)=\frac{A_{c}}{\gamma^{2}}\,e^{-\frac{x^{2}+y^{2}}{2\gamma^{2}\sigma^{2}}}-A_{s}\,e^{-\frac{x^{2}+y^{2}}{2\sigma^{2}}}$
(1)

where $\gamma\,{<}\,1$ is the ratio of the radius of the center to the one of
the surround, $\sigma$ is the variance of the Gaussian function, and $A_{c}$
and $A_{s}$ are the center and surround coefficients. To construct 3D-IB
kernels, a naive way would be to use Equation 1 and repeat the kernels in the
third axis. However, this approach would result in a cylindrical center-
surround structure. A better way is to design a spherical structure, with
excitatory center and an inhibitory surround. We therefore extend the 2D
version as follows:

$DoG_{\sigma,\gamma}(x,y,z)=\frac{A_{c}}{\gamma^{3}}\,e^{-\frac{x^{2}+y^{2}+z^{2}}{2\gamma^{2}\sigma^{2}}}-A_{s}\,e^{-\frac{x^{2}+y^{2}+z^{2}}{2\sigma^{2}}}$
(2)

We set the absolute value of the sum of the negative and positive weights to
be equal to an arbitrary value $c\geq 1$. This ensures the proper balance
between excitation and inhibition, and the kernel weights will be large
enough.

$[DoG_{\sigma,\gamma}(x,y,z)]^{+}dxdydz=c,$ (3)
$[DoG_{\sigma,\gamma}(x,y,z)]^{-}dxdydz=-c$ (4)

By setting the sum of negative and positive values to the same value, the
coefficients $A_{c}$ and $A_{s}$ will be equal in the infinite continuous
case. To show that this result holds, we can write the DoG equation in polar
coordinates:

$\int_{0}^{r_{s}}\\!\\!\\!\\!\int_{0}^{\pi}\\!\\!\\!\\!\int_{0}^{2\pi}\\!\\!\\!\\!\\!\\!r^{2}\,sin(\varphi)\,\left(\frac{A_{c}}{\gamma^{3}}\
e^{-\frac{r^{2}}{2\gamma^{2}\sigma^{2}}}-A_{s}\,e^{-\frac{r^{2}}{2\sigma^{2}}}\right)d\theta
d\varphi dr$ (5)

where $r$ is the radius of the central sphere. We can calculate the integral
when $r\,{\to}\,\infty$, and by knowing that the sum of positive and negative
weights is zero, we have:

$\frac{2\sqrt{2}\pi^{\frac{3}{2}}}{(\frac{1}{\sigma^{2}})^{\frac{3}{2}}}(A_{c}-A_{s})=0\
\ \Rightarrow\ \ A_{c}=A_{s}$ (6)

Assuming that the values of the coefficients are still close enough in the
finite discrete case as well, we can approximate the variance of the Gaussians
as follows:

$\sigma\approx\frac{r}{\gamma}\sqrt{\frac{1-\gamma^{2}}{-6\ln{\gamma}}}$ (7)

### The Architecture of the Second Encoder Block

We used Equation 2 to calculate the fixed kernel weights for the On and Off
(identical equation, but with signs inverted) convolutions. Note that we only
needed to determine the kernel size ($k$), the ratio of the radius of the
center to surround, and the sum of positive and negative values to compute the
fixed kernels. Figure 3 shows the $5\,{\times}\,5\,{\times}\,5$ On kernel that
we use in our experiments. Here we set $\gamma=2/3$ and $r=3$. For a given
input $\chi$, we calculate the On and Off responses by convolving $\chi$ with
the computed kernels separately:

$\begin{array}[]{c@{\ }c@{\ }l}\chi_{\rm
On}[x,y,z]&=&(\chi*+DoG[r,\gamma,c])[x,y,z]\\\\[2.84526pt] \chi_{\rm
Off}[x,y,z]&=&(\chi*-DoG[r,\gamma,c])[x,y,z]\end{array}$ (8)

Table 1: Robustness of U-Net variants on the MSD-prostate dataset using DSC metric. Dataset | Subsample | Model | No-Noise | Gaussian Blur | Random Gaussian
---|---|---|---|---|---
Name | Size | Name |  | Noise, $\sigma=2$ | Noise, $\sigma=45$
MSD-prostate | $8$ | SegResNet | $0.555\pm 0.337$ | $0.513\pm 0.319$ | $0.540\pm 0.225$
|  | IB-SegResNet | $0.560\pm 0.231$ | $0.555\pm 0.214$ | $0.526\pm 0.303$
|  | Attention-U-Net | $0.456\pm 0.289$ | $0.153\pm 0.198$ | $0.520\pm 0.308$
|  | IB-Att-U-Net | $0.657\pm 0.109$ | $0.609\pm 0.101$ | $0.627\pm 0.112$
|  | nnU-Net | $0.705\pm 0.095$ | $0.673\pm 0.105$ | $0.704\pm 0.098$
|  | IB-nnU-Net | $\mathbf{0.720\pm 0.071}$ | $\mathbf{0.690\pm 0.100}$ | $\mathbf{0.716\pm 0.077}$
MSD-prostate | $16$ | SegResNet | $0.705\pm 0.251$ | $0.464\pm 0.301$ | $0.704\pm 0.261$
|  | IB-SegResNet | $0.754\pm 0.206$ | $0.591\pm 0.257$ | $0.733\pm 0.214$
|  | Attention-U-Net | $0.682\pm 0.261$ | $0.144\pm 0.266$ | $0.665\pm 0.273$
|  | IB-Att-U-Net | $0.779\pm 0.078$ | $0.742\pm 0.105$ | $0.777\pm 0.076$
|  | nnU-Net | $0.804\pm 0.073$ | $0.758\pm 0.095$ | $0.782\pm 0.087$
|  | IB-nnU-Net | $\mathbf{0.821\pm 0.063}$ | $\mathbf{0.789\pm 0.085}$ | $\mathbf{0.793\pm 0.076}$
MSD-prostate | $24$ | SegResNet | $0.805\pm 0.181$ | $0.672\pm 0.230$ | $0.733\pm 0.264$
|  | IB-SegResNet | $0.808\pm 0.188$ | $0.685\pm 0.220$ | $0.790\pm 0.193$
|  | Attention-U-Net | $0.816\pm 0.119$ | $0.478\pm 0.341$ | $0.773\pm 0.159$
|  | IB-Att-U-Net | $0.819\pm 0.113$ | $0.594\pm 0.314$ | $0.776\pm 0.202$
|  | nnU-Net | $0.823\pm 0.065$ | $0.803\pm 0.097$ | $0.816\pm 0.087$
|  | IB-nnU-Net | $\mathbf{0.831\pm 0.042}$ | $\mathbf{0.819\pm 0.079}$ | $\mathbf{0.822\pm 0.071}$

We extended a 3D U-Net segmentation variation to a 3D IB-U-Net variation by
changing its second encoder block to a 3D IB encoder block with $k=5$, as
shown in Figure 1. Through extensive experimentation, we found out that this
IB extension results in the best accuracy and robustness on the chosen small-
sized datasets. For instance, initially the input to IB layers was the outputs
of the max-pooling layers, but the results improved only by an insignificant
margin. We also used different values for the IB parameters, such as $\gamma$
and $r$, thus creating kernels of different sizes. The use of even shaped
kernels for convolution operation requires extra padding, and since this
introduces artificial values, we restricted our design to kernels with odd
shapes ($k=3,5,7,9$). When using a kernel size of 3 ($r=1$, $\gamma=1/2$), the
performance improved, but it was it is not always guaranteed. For larger
kernel sizes such as $k=7$ ($r=3$, $\gamma=3/4$) and $k=9$ ($r=4$,
$\gamma=4/5$), there was a large increase in the number of network parameters
and training time with an insignificant margin of improvement (less than 0.1%)
as compared to when $k=5$.

In other scenarios, we added the IB layers in the second decoder block to
maintain a degree of symmetry in the networks. However, this did not prove
beneficial, as it helped for some scans but made some other volumetric
segmentation results worse. In addition, we created networks where the IB
layers were placed in all the encoder blocks, not just in the second encoder
block. By doing this, we not only introduced more parameters, but our models
started over-fitting as well. Therefore, we decided to utilize the IB kernels
only in the second encoder block.

To add the On and Off IBs to the second convolution block, we first divided
the convolution layers of the block into two parallel pathways, with half of
the filters in the original layer in each divided convolution. This
architecture mimics the so-called On and Off pathways in the retina. We added
the 3D On and Off convolved inputs of the block to the activation maps of the
first convolution layers of the pathways before max-pooling, such that we do
not lose information. This required the use of a stride of two for the IBs. We
experimentally observed that adding the IBs after max-pooling and with a
stride of one leads to worse results. Finally, we concatenated the activation
maps of the last layers on the pathways, resulting in the outputs with the
same shapes as the outputs of the original block.

Table 2: Robustness of U-Net variants on the PROMISE-12 dataset using DSC metric. Subsample | Model | No-Noise | Gaussian Blur | Random Gaussian
---|---|---|---|---
Size | Name |  | Noise, $\sigma=2$ | Noise, $\sigma=45$
$8$ | SegResNet | $0.559\pm 0.267$ | $0.392\pm 0.311$ | $0.510\pm 0.326$
| IB-SegResNet | $0.624\pm 0.214$ | $0.495\pm 0.246$ | $0.639\pm 0.189$
| Attention-U-Net | $0.512\pm 0.325$ | $0.079\pm 0.123$ | $0.508\pm 0.317$
| IB-Att-U-Net | $0.674\pm 0.104$ | $0.623\pm 0.199$ | $0.662\pm 0.112$
| nnU-Net | $0.722\pm 0.136$ | $0.704\pm 0.175$ | $0.721\pm 0.146$
| IB-nnU-Net | $\mathbf{0.735\pm 0.127}$ | $\mathbf{0.713\pm 0.159}$ | $\mathbf{0.719\pm 0.135}$
$16$ | SegResNet | $0.618\pm 0.267$ | $0.603\pm 0.301$ | $0.611\pm 0.268$
| IB-SegResNet | $0.705\pm 0.213$ | $0.650\pm 0.297$ | $0.678\pm 0.224$
| Attention-U-Net | $0.582\pm 0.298$ | $0.241\pm 0.304$ | $0.589\pm 0.273$
| IB-Att-U-Net | $0.622\pm 0.251$ | $0.461\pm 0.349$ | $0.617\pm 0.261$
| nnU-Net | $0.759\pm 0.155$ | $0.740\pm 0.169$ | $\mathbf{0.751\pm 0.160}$
| IB-nnU-Net | $\mathbf{0.779\pm 0.146}$ | $\mathbf{0.743\pm 0.158}$ | $0.738\pm 0.175$
$24$ | SegResNet | $0.645\pm 0.234$ | $0.532\pm 0.244$ | $0.594\pm 0.296$
| IB-SegResNet | $0.768\pm 0.130$ | $0.596\pm 0.237$ | $0.723\pm 0.239$
| Attention-U-Net | $0.690\pm 0.234$ | $0.449\pm 0.302$ | $0.640\pm 0.245$
| IB-Att-U-Net | $0.737\pm 0.162$ | $0.487\pm 0.307$ | $0.645\pm 0.288$
| nnU-Net | $0.803\pm 0.104$ | $0.794\pm 0.125$ | $0.800\pm 0.124$
| IB-nnU-Net | $\mathbf{0.811\pm 0.095}$ | $\mathbf{0.800\pm 0.120}$ | $\mathbf{0.802\pm 0.108}$

## Materials and Methods

### U-Net Variations Used in Our Experiments

To explore the merit of IBs in U-Nets, we first examined the accuracy and
robustness of all variations mentioned in Section Related Work and their
extension. Attention-U-Nets and SegResNets introduced novel multi-view and
multi-scale functions, which enhanced the receptive fields of the networks and
reduced bottlenecks during computation, essentially shortening the time
required to converge. Furthermore, these architectures showed excellent
performances on the public dataset. Therefore, we proceeded to further
benchmark these two architectures in our framework. However, we excluded the
V-Net from this paper, as the SegResNet has a similar structure as that of the
former model. Moreover, the SegResNet improves on the V-Net by introducing a
VAE branch. While all variations benefited from the IB extension, nnU-Nets,
Attention-U-Nets and SegResNets performed best. nnU-Nets, Attention-U-Nets and
SegResNets were extended with 3D-IB filters of kernel sizes $k=5$. The
resulting new networks are called as follows: IB-nnU-Net, IB-Att-U-Net and IB-
SegResNet respectively.

### Datasets

In all our experiments concerning the prostate organ, we utilized two MRI
datasets from two different public sources: PROMISE-12 and MSD-prostate.

#### PROMISE-12:

The PROMISE-12 dataset offers 80 (training=50, testing=30) volumes of
transversal T2-weighted MRIs of the prostate. This dataset was selected as it
is a compilation of scans collected from multiple centres and vendors with
different acquisition protocols. Due to this fact, there is a heterogeneity in
the voxel-spacings and the slice thickness of the volumes.

Table 3: Robustness of U-Net variants on the MSD-spleen dataset using DSC metric. Subsample | Model | No-Noise | Gaussian Blur | Random Gaussian
---|---|---|---|---
Size | Name |  | Noise, $\sigma=2$ | Noise, $\sigma=45$
$8$ | SegResNet | $0.601\pm 0.311$ | $0.605\pm 0.304$ | $0.593\pm 0.294$
| IB-SegResNet | $0.621\pm 0.271$ | $0.618\pm 0.285$ | $0.616\pm 0.274$
| Attention-U-Net | $0.615\pm 0.293$ | $0.603\pm 0.303$ | $0.611\pm 0.300$
| IB-Att-U-Net | $0.630\pm 0.235$ | $0.612\pm 0.289$ | $0.615\pm 0.275$
| nnU-Net | $0.652\pm 0.247$ | $0.628\pm 0.244$ | $0.650\pm 0.236$
| IB-nnU-Net | $\mathbf{0.665\pm 0.233}$ | $\mathbf{0.631\pm 0.241}$ | $\mathbf{0.659\pm 0.234}$
$16$ | SegResNet | $0.704\pm 0.197$ | $0.661\pm 0.211$ | $0.679\pm 0.201$
| IB-SegResNet | $0.715\pm 0.183$ | $0.704\pm 0.190$ | $0.711\pm 0.178$
| Attention-U-Net | $0.728\pm 0.171$ | $0.719\pm 0.180$ | $0.720\pm 0.184$
| IB-Att-U-Net | $0.739\pm 0.168$ | $0.722\pm 0.181$ | $0.734\pm 0.169$
| nnU-Net | $\mathbf{0.754\pm 0.152}$ | $0.730\pm 0.168$ | $\mathbf{0.746\pm 0.149}$
| IB-nnU-Net | $0.751\pm 0.154$ | $\mathbf{0.732\pm 0.166}$ | $0.741\pm 0.150$
$24$ | SegResNet | $0.818\pm 0.118$ | $0.776\pm 0.146$ | $0.765\pm 0.148$
| IB-SegResNet | $0.819\pm 0.109$ | $0.799\pm 0.121$ | $0.786\pm 0.135$
| Attention-U-Net | $0.841\pm 0.088$ | $0.824\pm 0.114$ | $0.817\pm 0.122$
| IB-Att-U-Net | $0.843\pm 0.080$ | $0.833\pm 0.091$ | $0.829\pm 0.106$
| nnU-Net | $0.868\pm 0.067$ | $0.840\pm 0.102$ | $\mathbf{0.852\pm 0.093}$
| IB-nnU-Net | $\mathbf{0.872\pm 0.067}$ | $\mathbf{0.842\pm 0.100}$ | $0.851\pm 0.093$

#### MSD-prostate:

The MSD-prostate dataset comprises of 48 (training=32, testing=16) multimodal
(T2, ADC) 3D MRI samples. We only considered the T2-weighted modality as they
provide most of the necessary anatomical information, whereas the ADC modality
is often considered for tumour characterization/segmentation. Furthermore, the
ground-truth labels of the original MSD-prostate dataset are separated into
annotations of the central prostate gland and the peripheral zone. We combined
the two regions into one label such that all U-Net variations could learn a
binary image segmentation. Similar to the PROMISE-12, the MSD-prostate dataset
was selected as it has a significant amount of inter-subject variability.

#### MSD-spleen:

The spleen dataset consists of 61 (training=41, testing=20) monomodal 3D CT
samples. We wanted to work with this dataset because of two reasons; first, it
has a small sample size, and second, we wanted to check the potential of the
IB kernels when handling CT images with large variations in their field-of-
view.

### Implementation of our framework

Other than extending the networks with the IB kernels, we did not make any
alterations to the original networks, including the convolution and
normalization layers (Ioffe and Szegedy 2015), activation functions, and
dropout layers and probabilities. All the necessary source code for the
framework was implemented in PyTorch (Paszke et al. 2019).

The volumes in the three datasets have varying voxel spacings, and CNNs
disregard this information while operating on the voxel grids. To handle this
heterogeneity in the datasets, all the images and their corresponding ground
truth labels were resampled to the target voxel spacings of their respective
datasets: $0.6125\times 0.6125\times 2.2mm^{3}$ for PROMISE-12, $0.625\times
0.625\times 3.6mm^{3}$ for the MSD-prostate and $0.79\times 0.79\times
1.6mm^{3}$ for MSD-spleen. We employed tri-linear and nearest-neighbour
interpolation to resample the images and annotated labels, respectively. In
most biomedical cases, we cannot fit the complete image into the GPU due to
the large sizes. For that reason, 3D patches of foreground and background were
randomly sampled with equal probabilities. The shape of the sampled patches
were: $192\,{\times}\,192\,{\times}\,16$ voxels for the PROMISE-12 dataset,
$288\,{\times}\,288\,{\times}\,16$ for the MSD-prostate set, and
$192\,{\times}\,192\,{\times}\,96$ for the spleen dataset.

The intensity values of the MR scans were linearly scaled using a standard
(z-score) normalization such that the mean value and standard deviation of the
transformed data equalled to 0 and 1, respectively. As for CT images, the
first 0.5 and 99.5 percentiles of the foreground voxels were clipped, and then
normalized using the global foreground mean and standard deviation. To
synthesize additional data during training, the data pipeline carried out
augmentations, such as elastic deformations, gamma correction, random Gaussian
noise, Gaussian blur, rotations, and scaling. Throughout all the experiments,
we used the Adam optimization algorithm with an initial learning rate of 1e-04
that decays using a polynomial scheduler (Myronenko 2019) for 500 epochs. We
used L2 regularization on the convolution kernel parameters with a weight of
1e-05. The gradient updates were evaluated with a mini-batch size of two for
all the datasets.

#### Loss functions:

We utilized a combination of two-loss functions; Binary Cross-Entropy loss
(LBCE) and Sørensen-Dice Loss (Ldice) (Sudre et al. 2017) together make BCE-
dice loss (LBCE-dice) (Milletari, Navab, and Ahmadi 2016) to train the models.
This compound loss is defined over all semantic classes and is less sensitive
to class imbalance, as demonstrated experimentally in Ma et al. (2021). The
equations for BCE-dice loss are given as follows:

$\begin{array}[]{l@{\
}l}L\textsubscript{BCE}&=-\frac{1}{N}\cdot\sum_{i=1}^{N}g_{i}\cdot
log(p_{i})+(1-g_{i})\cdot log(1-p_{i})\end{array}$ (9) $\begin{array}[]{l@{\
}l}L\textsubscript{dice}&=1-\frac{2*\sum_{i=1}^{N}p_{i}g_{i}}{\sum_{i=1}^{N}p_{i}^{2}+\sum_{i=1}^{N}g_{i}^{2}}\end{array}$
(10) $\begin{array}[]{l@{\ }l}L\textsubscript{BCE-
dice}&=L\textsubscript{BCE}+L\textsubscript{dice}\end{array}$ (11)

$N$ is the number of voxels, $p_{i}$ and $g_{i}$ denote the prediction and
ground-truth label at voxel $i$ respectively, for an image.

Table 4: Accuracy of U-Net variants and their IB extensions on the full datasets without any artifacts. Model Name | MSD-prostate ($32$) | PROMISE-12 ($50$) | Spleen dataset ($41$)
---|---|---|---
SegResNet | $0.841\pm 0.085$ | $0.885\pm 0.035$ | $0.901\pm 0.083$
IB-SegResNet | $\mathbf{0.844\pm 0.078}$ | $\mathbf{0.888\pm 0.033}$ | $\mathbf{0.902\pm 0.080}$
Attention-U-Net | $0.835\pm 0.075$ | $0.891\pm 0.033$ | $0.938\pm 0.062$
IB-Att-U-Net | $\mathbf{0.845\pm 0.066}$ | $\mathbf{0.892\pm 0.032}$ | $\mathbf{0.941\pm 0.058}$
nnU-Net | $0.882\pm 0.118$ | $0.890\pm 0.101$ | $0.966\pm 0.044$
IB-nnU-Net | $\mathbf{0.895\pm 0.042}$ | $\mathbf{0.902\pm 0.036}$ | $\mathbf{0.970\pm 0.017}$

In the validation phase, neither patch sampling was done nor any augmentations
were applied, rather only the appropriate normalization techniques were
applied to the full image. Next, to predict the label, a sliding window
technique was used with an overlap of $1/2$ in each dimension, and the window
shape was the set to the training patch size. The state values of the model
configuration with the highest metric value was saved and later used for
inference. The models were evaluated based on the DSC metric (Dice score), as
it exhibits a low overall bias in 3D medical image segmentation tasks (Taha
and Hanbury 2015; Maier-Hein et al. 2022). The Dice score is defined in
equation 12, where $\epsilon$ is the smoothing factor with a value of
$10^{-}6$.

$\begin{array}[]{l@{\
}l}\text{DSC}&=\frac{2*\sum_{i=1}^{N}p_{i}g_{i}+\epsilon}{\sum_{i=1}^{N}p_{i}^{2}+\sum_{i=1}^{N}g_{i}^{2}+\epsilon}\end{array}$
(12)

Once the training was finished, first the voxel-wise semantic predictions were
generated using the best network parameters, and then the labels were
resampled to their original spacings. Next, we retrieved the desired region by
taking the largest connected component (apart from the background) of the
resultant resampled volume. The inference step ended after the final metric
values were calculated, and the detailed results were saved.

## Experiments and Results

The proposed 3D IB filters are modular and independent of the network’s
architecture, allowing them to be easily deployed to image segmentation tasks.
Unfortunately, the ground-truth labels for the testing images are not publicly
available for any of the datasets mentioned in Section Datasets. Consequently,
to analyze the capabilities of the networks, we conducted two kinds of CV
using the 50 MR volumes, 32 MR images and 41 CT scans from the PROMISE-12,
MSD-prostate, and MSD-spleen datasets, respectively. First, we implemented
8-fold CV by randomly sampling three subsets each from the datasets. The
sample size was chosen such that it would be a factor of $8$, hence, the
number of volumes in each sub-sample was $8$, $16$ and $24$ respectively. This
made sure that we could investigate the capabilities of our IB extensions on
small-sized datasets. Second, we investigated the models for all available
volumes in the three datasets for completeness using 5-fold CV. For the nnU-
Net framework, we extended the U-Net of the nnU-Net with the IB kernels, and
then followed the steps detailed in Isensee et al. (2021). We ran our
experiments on an NVIDIA Titan RTXs with 24 GB memory. The CV method for a
single network on one dataset was completed in four and six days with our
framework and when using the nnU-Net framework, respectively. We acknowledge
that training models for a long period could possibly negatively impact the
environment, but this can be mitigated in future works by training the best
model presented in this paper with a 5-fold CV method.

Initially, we examined the accuracy and robustness of the SegResNets,
Attention-U-Nets, nnU-Nets and their IB extensions on the original volumes.
Figure 4 illustrates a few of the qualitative examples by comparing the
predictions of the U-Net variations and their IB extensions, and it is evident
that the IB extensions are more accurate than the original U-Nets. The IB-nnU-
Net attained the highest result. In the next stage, we corrupted the original
volumes by adding two types of noise: Gaussian blur and random Gaussian noise.
We used the Torchio package (Pérez-García, Sparks, and Ourselin 2021) to
create the noisy datasets.

### Robustness Evaluation on Small Subsets

Tables 1, 2 and 3 summarise our accuracy and robustness results for
SegResNets, Attention-U-Nets, nnU-Nets and their IB extensions. The best
performance is emphasized in boldface. The key takeaway is that IB extensions
are more performant. As demonstrated by Table 1, the IB extensions always have
superior performance on the MSD-prostate dataset. Additionally, in Tables 2
and 3, a similar observation is also true for the PROMISE-12 and the spleen
dataset, with a few exceptions: the nnU-Net for 16 and 24 subsamples. In these
cases, the lower performance of the IB extension could be attributed to the
presence of outliers. Please note, however, that the variance in these two
cases is relatively high. Thus, the results for the IB extensions are still
within the same range as the ones for original nnU-Net. In general, the
variance of the vanilla U-Net variants is larger in these tables than the one
of their IB extensions.

### Robustness Evaluation on Full Dataset

For completeness, in Table 4 we provide the DSC-accuracy results of
SegResNets, Attention-U-Nets, nnU-Nets and their IB-extensions, for all
available volumes in the three datasets. Similar to Tables 1, 2 and 3, the IB-
extensions are performing better for full datasets. However, the performance
improvement is not that significant any more. In other words, the smaller the
dataset, the more rectifying is the addition of IB to the U-Nets. This is true
in general for machine learning (ML): the smaller the dataset, the more
important is the ML algorithm.

### Cylindrical versus Spherical IB kernels

The extension of the IB kernel from 2D to 3D is non-trivial. If we assume that
the 3D IB kernel is simply the repeated stacking of the 2D kernel on top of
one another (along the z-axis, with each slice having the same weights), then
this leads to a cylindrical kernel. Table 5 shows the performance of the
spherical kernel against the cylindrical kernels for the Attention U-Net. As
one can see, our spherical kernel outperforms other variants, while the
cylindrical versions are inferior compared to the original Attention U-Net.
The cylindrical kernels make mistakes when considering 3D contours; therefore,
it is crucial to make modifications. Moreover, Babaiee et al. (2021) used
natural images to evaluate the performance of the 2D IB kernels, and the
kernels that work for 2D may not necessarily be suitable in the 3D setting.
The properties of 3D medical images, such as the voxel spacings, matrix
directions, origins etc., produce significant artifacts that the cylindrical
kernels cannot handle well.

Table 5: Comparison of robustness among Attention U-Net, cylindrical IB-attention U-Nets ($k=3$ and $k=5$), and spherical IB-attention U-Net ($k=5$) on subsample size 8 of the PROMISE-12 dataset using the DSC metric. To be added in the final version. Model Name | DSC ($\uparrow$)
---|---
Attention-U-Net | $0.512\pm 0.325$
Cyl IB-Att. U-Net (k3) | $0.438\pm 0.358$
Cyl IB-Att. U-Net (k5) | $0.445\pm 0.336$
IB-Att. U-Net (k5) | $\mathbf{0.674\pm 0.104}$
Table 6: Comparison of robustness amongst nnU-Net and its IB-extended U-Nets (k3, k5, k7 and k9) on the full PROMISE-12 dataset using the DSC metric. We will add it in the final version. Model Name | DSC ($\uparrow$)
---|---
nnU-Net | $0.890\pm 0.101$
IB-nnU-Net ($k=3$, $r=1$, $\gamma=1/2$) | $0.887\pm 0.086$
IB-nnU-Net ($k=5$, $r=2$, $\gamma=2/3$) | $\mathbf{0.902\pm 0.036}$
IB-nnU-Net ($k=7$, $r=3$, $\gamma=3/4$) | $0.898\pm 0.055$
IB-nnU-Net ($k=9$, $r=4$, $\gamma=4/5$) | $0.895\pm 0.058$
Table 7: Accuracy of nnU-Net and IB-nnU-Net on the full datasets without any artifacts using the HD95 (in mm) metric. To be added. Dataset Name | Model Name | HD95 in mm ($\downarrow$)
---|---|---
MSD-prostate | nnU-Net | $15.078\pm 75.203$
| IB-nnU-Net | $\mathbf{1.738\pm 1.122}$
PROMISE-12 | nnU-Net | $9.735\pm 59.565$
| IB-nnU-Net | $\mathbf{1.237\pm 0.556}$
MSD-spleen | nnU-Net | $1.640\pm 4.708$
| IB-nnU-Net | $\mathbf{1.189\pm 1.914}$

### Different parameters of IB kernels

The section on the architecture of the second encoder block discusses the
performances of the various IB-extended U-Net architectures, such as U-Nets
with multiple IB blocks; however, their performances were not satisfactory. We
also conducted experiments with different $k$, $r$, and $\gamma$, and the
quantitative results are given in Table 6. It is clear that the IB-nnU-Net
variant with parameter values of $k=5$, $r=2$, and $\gamma=2/3$ is the best
performing version

## Discussion and Conclusion

We introduced two new 3D kernels, inspired by the on and off center-surround
pathways originating in the vertebrate retina, and we proposed a procedure to
compute the kernel weights. We showed how to extend the second encoder block
of U-Net variations, using these precomputed kernels as inductive biases,
helping to scrutinize and delineate anatomical structures of 3D images with
increased accuracy. Although our proposed 3D-IB-encoder block slightly
increases the number of training parameters of the networks, the modification
steps are effortless, and it requires minimal computational overhead.

The IB kernels can help in scenarios where the dataset has at least two
outliers (very different samples). In this case, the other models have
difficulties in segmenting the region of interest (ROI). This is evident in
Figures 2 and 4, as well as in Table 4, where the standard deviation of the
best performing IB-nnU-Net is smaller than that of the second place nnU-Net.
The marginal improvement of performances in Table 3 could be due to sampling
very similar volumes from the spleen task without any outliers. In the full
MSD-spleen dataset, the ROI is so large that when the model prediction is
incorrect by a significant margin, the DSC metric may not capture this
distinction accurately. Therefore, in Table 7 we have listed the segmentation
performances of the nnU-Net and IB-nnU-Net, respectively, using a surface
distance metric called the 95th percentile Hausdorff distance (HD95).

Robustness to distribution shifts is a crucial attribute of any deep neural
network, and it is of even higher importance for networks used in critical
domains like bio-medical tasks. Our experiments on multiple organ segmentation
tasks with our baseline networks and their IB extensions show notable
enhancements in the performance of the IB-equipped networks. Furthermore, our
robustness experiments demonstrate the superior performance of IB extended
networks. Figure 2 shows that the IB extension improves a network’s focus on
critical structures. In conclusion, the proposed method could make the 3D-IB
kernels a favourable approach to achieve accurate results in 3D medical image
segmentation tasks with small sized datasets.

## Acknowledgements

This research was funded in part by the Austrian Science Fund (FWF): I 4718,
and the Federal Ministry of Education and Research (BMBF) Germany, under the
frame of ERA PerMed. Z. B. was supported by the Doctoral College Resilient
Embedded Systems, which is run jointly by the TU Wien’s Faculty of Informatics
and the UAS Technikum Wien.

## Code and Data Availability

All code and data are included in https://github.com/Shrajan/IB_U_Nets.

## References

  * Altini et al. (2022) Altini, N.; Prencipe, B.; Cascarano, G. D.; Brunetti, A.; Brunetti, G.; Triggiani, V.; Carnimeo, L.; Marino, F.; Guerriero, A.; Villani, L.; Scardapane, A.; and Bevilacqua, V. 2022.  Liver, kidney and spleen segmentation from CT scans and MRI with deep learning: A survey.  _Neurocomputing_ , 490: 30–53.
  * Antonelli et al. (2021) Antonelli, M.; Reinke, A.; Bakas, S.; Farahani, K.; AnnetteKopp-Schneider; Landman, B. A.; Litjens, G.; Menze, B.; Ronneberger, O.; Summers, R. M.; van Ginneken, B.; Bilello, M.; Bilic, P.; Christ, P. F.; Do, R. K. G.; Gollub, M. J.; Heckers, S. H.; Huisman, H.; Jarnagin, W. R.; McHugo, M. K.; Napel, S.; Pernicka, J. S. G.; Rhode, K.; Tobon-Gomez, C.; Vorontsov, E.; Huisman, H.; Meakin, J. A.; Ourselin, S.; Wiesenfarth, M.; Arbelaez, P.; Bae, B.; Chen, S.; Daza, L.; Feng, J.; He, B.; Isensee, F.; Ji, Y.; Jia, F.; Kim, N.; Kim, I.; Merhof, D.; Pai, A.; Park, B.; Perslev, M.; Rezaiifar, R.; Rippel, O.; Sarasua, I.; Shen, W.; Son, J.; Wachinger, C.; Wang, L.; Wang, Y.; Xia, Y.; Xu, D.; Xu, Z.; Zheng, Y.; Simpson, A. L.; Maier-Hein, L.; and Cardoso, M. J. 2021.  The Medical Segmentation Decathlon.  _arXiv preprint arXiv:2106.05735_.
  * Antonelli et al. (2022) Antonelli, M.; Reinke, A.; Bakas, S.; Farahani, K.; Kopp-Schneider, A.; Landman, B. A.; Litjens, G.; Menze, B.; Ronneberger, O.; Summers, R. M.; van Ginneken, B.; Bilello, M.; Bilic, P.; Christ, P. F.; Do, R. K. G.; Gollub, M. J.; Heckers, S. H.; Huisman, H.; Jarnagin, W. R.; McHugo, M. K.; Napel, S.; Pernicka, J. S. G.; Rhode, K.; Tobon-Gomez, C.; Vorontsov, E.; Meakin, J. A.; Ourselin, S.; Wiesenfarth, M.; Arbeláez, P.; Bae, B.; Chen, S.; Daza, L.; Feng, J.; He, B.; Isensee, F.; Ji, Y.; Jia, F.; Kim, I.; Maier-Hein, K.; Merhof, D.; Pai, A.; Park, B.; Perslev, M.; Rezaiifar, R.; Rippel, O.; Sarasua, I.; Shen, W.; Son, J.; Wachinger, C.; Wang, L.; Wang, Y.; Xia, Y.; Xu, D.; Xu, Z.; Zheng, Y.; Simpson, A. L.; Maier-Hein, L.; and Cardoso, M. J. 2022.  The Medical Segmentation Decathlon.  _Nature Communications_ , 13(1): 4128.
  * Babaiee et al. (2021) Babaiee, Z.; Hasani, R.; Lechner, M.; Rus, D.; and Grosu, R. 2021.  On-Off Center-Surround Receptive Fields for Accurate and Robust Image Classification.  _Proceedings of the 38th International Conference on Machine Learning_ , 139: 478–489.
  * Brooks et al. (2012) Brooks, R.; Hassabis, D.; Bray, D.; and Shashua, A. 2012.  Turing centenary: Is the brain a good model for machine intelligence?  _Nature_ , 482: 462–3.
  * Çiçek et al. (2016) Çiçek, Ö.; Abdulkadir, A.; Lienkamp, S. S.; Brox, T.; and Ronneberger, O. 2016.  3D U-Net: learning dense volumetric segmentation from sparse annotation.  _International conference on medical image computing and computer-assisted intervention_ , 424–432.
  * Consortium (2020) Consortium, M. 2020.  MONAI: Medical Open Network for AI.
  * Dapello et al. (2020) Dapello, J.; Marques, T.; Schrimpf, M.; Geiger, F.; Cox, D.; and DiCarlo, J. J. 2020\.  Simulating a Primary Visual Cortex at the Front of CNNs Improves Robustness to Image Perturbations.  _Advances in Neural Information Processing Systems_ , 33: 13073–13087.
  * Ghavami et al. (2019) Ghavami, N.; Hu, Y.; Gibson, E.; Bonmati, E.; Emberton, M.; Moore, C. M.; and Barratt, D. C. 2019.  Automatic segmentation of prostate MRI using convolutional neural networks: Investigating the impact of network architecture on the accuracy of volume measurement and MRI-ultrasound registration.  _Medical Image Analysis_ , 58.
  * Gibson et al. (2018) Gibson, E.; Giganti, F.; Hu, Y.; Bonmati, E.; Bandula, S.; Gurusamy, K.; Davidson, B.; Pereira, S. P.; Clarkson, M. J.; and Barratt, D. C. 2018.  Automatic Multi-Organ Segmentation on Abdominal CT With Dense V-Networks.  _IEEE Transactions on Medical Imaging_ , 37(8): 1822–1834.
  * Gillespie et al. (2020) Gillespie, D.; Kendrick, C.; Boon, I.; Boon, C.; Rattay, T.; and Yap, M. H. 2020\.  Deep learning in magnetic resonance prostate segmentation: A review and a new perspective.  _arXiv preprint arXiv:2011.07795_.
  * Goldenberg, Nir, and Salcudean (2019) Goldenberg, S. L.; Nir, G.; and Salcudean, S. E. 2019.  A new era: artificial intelligence and machine learning in prostate cancer.  _Nature Reviews Urology_ , 16(7): 391–403.
  * Hassabis et al. (2017) Hassabis, D.; Kumaran, D.; Summerfield, C.; and Botvinick, M. 2017.  Neuroscience-Inspired Artificial Intelligence.  _Neuron_ , 95(2): 245–258.
  * Hatamizadeh et al. (2022) Hatamizadeh, A.; Tang, Y.; Nath, V.; Yang, D.; Myronenko, A.; Landman, B.; Roth, H. R.; and Xu, D. 2022.  Unetr: Transformers for 3d medical image segmentation.  _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 574–584.
  * Ioffe and Szegedy (2015) Ioffe, S.; and Szegedy, C. 2015.  Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift.  _Proceedings of the 32nd International Conference on Machine Learning_ , 37: 448–456.
  * Isensee et al. (2021) Isensee, F.; Jaeger, P. F.; Kohl, S. A. A.; Petersen, J.; and Maier-Hein, K. H. 2021\.  nnU-Net: a self-configuring method for deep learning-based biomedical image segmentation.  _Nature methods_ , 18(2): 203—211.
  * Krizhevsky, Sutskever, and Hinton (2012) Krizhevsky, A.; Sutskever, I.; and Hinton, G. E. 2012.  ImageNet Classification with Deep Convolutional Neural Networks.  _Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 1_ , 1097–1105.
  * Kruizinga and Petkov (2000) Kruizinga, P.; and Petkov, N. 2000.  Computational model of dot-pattern selective cells.  _Biological Cybernetics_ , 83(4): 313–325.
  * Li et al. (2019) Li, Z.; Brendel, W.; Walker, E.; Cobos, E.; Muhammad, T.; Reimer, J.; Bethge, M.; Sinz, F.; Pitkow, Z.; and Tolias, A. 2019.  Learning from brains how to regularize machines.  _Advances in neural information processing systems_ , 32.
  * Litjens et al. (2017) Litjens, G.; Kooi, T.; Bejnordi, B. E.; Setio, A. A. A.; Ciompi, F.; Ghafoorian, M.; van der Laak, J. A.; van Ginneken, B.; and Sánchez, C. I. 2017.  A survey on deep learning in medical image analysis.  _Medical Image Analysis_ , 42: 60–88.
  * Litjens et al. (2014) Litjens, G.; Toth, R.; (van de Ven), W.; Hoeks, C.; Kerkstra, S.; (van Ginneken), B.; Vincent, G.; Guillard, G.; Birbeck, N.; Zhang, J.; Strand, R.; Malmberg, F.; Ou, Y.; Davatzikos, C.; Kirschner, M.; Jung, F.; Yuan, J.; Qiu, W.; Gao, Q.; Edwards, P. E.; Maan, B.; van-der Heijden, F.; Ghose, S.; Mitra, J.; Dowling, J.; Barratt, D.; Huisman, H.; and Madabhushi, A. 2014.  Evaluation of prostate segmentation algorithms for MRI: The PROMISE12 challenge.  _Medical Image Analysis_ , 18(2): 359–373.
  * Ma et al. (2021) Ma, J.; Chen, J.; Ng, M.; Huang, R.; Li, Y.; Li, C.; Yang, X.; and Martel, A. L. 2021.  Loss odyssey in medical image segmentation.  _Medical Image Analysis_ , 71: 102035.
  * Maier-Hein et al. (2022) Maier-Hein, L.; Reinke, A.; Christodoulou, E.; Glocker, B.; Godau, P.; Isensee, F.; Kleesiek, J.; Kozubek, M.; Reyes, M.; Riegler, M. A.; et al. 2022.  Metrics reloaded: Pitfalls and recommendations for image analysis validation.  _arXiv preprint arXiv:2206.01653_.
  * Milletari, Navab, and Ahmadi (2016) Milletari, F.; Navab, N.; and Ahmadi, S.-A. 2016.  V-Net: Fully Convolutional Neural Networks for Volumetric Medical Image Segmentation.  _2016 Fourth International Conference on 3D Vision (3DV)_ , 565–571.
  * Myronenko (2019) Myronenko, A. 2019.  3D MRI Brain Tumor Segmentation Using Autoencoder Regularization.  _Brainlesion: Glioma, Multiple Sclerosis, Stroke and Traumatic Brain Injuries_ , 311–320.
  * Nayebi et al. (2018) Nayebi, A.; Bear, D.; Kubilius, J.; Kar, K.; Ganguli, S.; Sussillo, D.; DiCarlo, J. J.; and Yamins, D. L. 2018.  Task-Driven Convolutional Recurrent Models of the Visual System.  _Advances in Neural Information Processing Systems_ , 31.
  * Oktay et al. (2018) Oktay, O.; Schlemper, J.; Folgoc, L. L.; Lee, M. C. H.; Heinrich, M. P.; Misawa, K.; Mori, K.; McDonagh, S. G.; Hammerla, N. Y.; Kainz, B.; Glocker, B.; and Rueckert, D. 2018.  Attention U-Net: Learning Where to Look for the Pancreas.  _Medical Imaging with Deep Learning_.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; et al. 2019.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32.
  * Petkov and Visser (2005) Petkov, N.; and Visser, W. T. 2005.  Modifications of Center-Surround, Spot Detection and Dot-Pattern Selective Operators.  Technical Report 2005-9-01, Institute of Mathematics and Computing Science, University of Groningen, Netherlands.
  * Pérez-García, Sparks, and Ourselin (2021) Pérez-García, F.; Sparks, R.; and Ourselin, S. 2021.  TorchIO: A Python library for efficient loading, preprocessing, augmentation and patch-based sampling of medical images in deep learning.  _Computer Methods and Programs in Biomedicine_ , 208: 106236.
  * Rischke et al. (2013) Rischke, H. C.; Nestle, U.; Fechter, T.; Doll, C.; Volegova-Neher, N.; Henne, K.; Scholber, J.; Knippen, S.; Kirste, S.; Grosu, A. L.; and Jilg, C. A. 2013\.  3 Tesla multiparametric MRI for GTV-definition of Dominant Intraprostatic Lesions in patients with Prostate Cancer–an interobserver variability study.  _Radiation oncology (London, England)_ , 8: 183–183.
  * Rodieck (1965) Rodieck, R. 1965.  Quantitative analysis of cat retinal ganglion cell response to visual stimuli.  _Vision Research_ , 5(12): 583–601.
  * Ronneberger, Fischer, and Brox (2015) Ronneberger, O.; Fischer, P.; and Brox, T. 2015.  U-Net: Convolutional Networks for Biomedical Image Segmentation.  _Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015_ , 234–241.
  * Simpson et al. (2019) Simpson, A. L.; Antonelli, M.; Bakas, S.; Bilello, M.; Farahani, K.; van Ginneken, B.; Kopp-Schneider, A.; Landman, B. A.; Litjens, G.; Menze, B. H.; Ronneberger, O.; Summers, R. M.; Bilic, P.; Christ, P. F.; Do, R. K. G.; Gollub, M.; Golia-Pernicka, J.; Heckers, S.; Jarnagin, W. R.; McHugo, M.; Napel, S.; Vorontsov, E.; Maier-Hein, L.; and Cardoso, M. J. 2019\.  A large annotated medical image dataset for the development and evaluation of segmentation algorithms.  _arXiv preprint arXiv:1902.09063_.
  * Singh et al. (2020) Singh, S. P.; Wang, L.; Gupta, S.; Goli, H.; Padmanabhan, P.; and Gulyás, B. 2020\.  3D Deep Learning on Medical Images: A Review.  _Sensors_ , 20(18).
  * Spohn et al. (2021) Spohn, S. K.; Bettermann, A. S.; Bamberg, F.; Benndorf, M.; Mix, M.; Nicolay, N. H.; Fechter, T.; Hölscher, T.; Grosu, R.; Chiti, A.; Grosu, A. L.; and Zamboglou, C. 2021.  Radiomics in prostate cancer imaging for a personalized treatment approach - current aspects of methodology and a systematic review on validated studies.  _Theranostics_ , 11: 8027–8042.
  * Steenbergen et al. (2015) Steenbergen, P.; Haustermans, K.; Lerut, E.; Oyen, R.; De Wever, L.; Van den Bergh, L.; Kerkmeijer, L. G.; Pameijer, F. A.; Veldhuis, W. B.; van der Voort van Zyp, J. R.; Pos, F. J.; Heijmink, S. W.; Kalisvaart, R.; Teertstra, H. J.; Dinh, C. V.; Ghobadi, G.; and van der Heide, U. A. 2015.  Prostate tumor delineation using multiparametric magnetic resonance imaging: Inter-observer variability and pathology validation.  _Radiotherapy and Oncology_ , 115(2): 186–190.
  * Sudre et al. (2017) Sudre, C. H.; Li, W.; Vercauteren, T. K. M.; Ourselin, S.; and Cardoso, M. J. 2017\.  Generalised Dice overlap as a deep learning loss function for highly unbalanced segmentations.  _Deep learning in medical image analysis and multimodal learning for clinical decision support_ , 240–248.
  * Taha and Hanbury (2015) Taha, A. A.; and Hanbury, A. 2015.  Metrics for evaluating 3D medical image segmentation: analysis, selection, and tool.  _BMC Medical Imaging_ , 15(1): 29.
  * Tian et al. (2020) Tian, Z.; Li, X.; Zheng, Y.; Chen, Z.; Shi, Z.; Liu, L.; and Fei, B. 2020.  Graph-convolutional-network-based interactive prostate segmentation in MR images.  _Medical Physics_ , 47(9): 4164–4176.