Do Deep Neural Networks for Segmentation Understand Insideness?
Authors: Kimberly M Villalobos
Vilim Stih
Amineh Ahmadinejad
Jamell Dozier
Andrew Francl
Frederico Azevedo
Tomotake Sasaki
Xavier Boix
Venue:  (2020)
Keywords: Image Segmentation
Deep Networks for Spatial Relationships
Visual Routines
Recurrent Neural Networks

Abstract: Image segmentation aims at grouping pixels that belong to the same object or region. At the heart of image segmentation lies the problem of determining whether a pixel is inside or outside a region, which we denote as the "insideness" problem. Many Deep Neural Networks (DNNs) variants excel in segmentation benchmarks, but regarding insideness, they have not been well visualized or understood: What representations do DNNs use to address the long-range relationships of insideness? How do architectural choices affect the learning of these representations? In this paper, we take the reductionist approach by analyzing DNNs solving the insideness problem in isolation, i.e. determining the inside of closed (Jordan) curves. We demonstrate analytically that state-of-the-art feed-forward and recurrent architectures can implement solutions of the insideness problem for any given curve. Yet, only recurrent networks could  learn these general solutions when the training enforced a specific "routine" capable of breaking down the long-range relationships. Our results highlights the need for new training strategies that decompose the learning into appropriate stages, and that lead to the general class of solutions necessary for DNNs to understand insideness.

Under review as a conference paper at ICLR 2020
Do DEEP NEURAL NETWORKS FOR SEGMENTATION UNDERSTAND INSIDENESS?
Anonymous authors
Paper under double-blind review
ABSTRACT
Image segmentation aims at grouping pixels that belong the same object or re- gion. At the heart of image segmentation lies the problem of determining whether pixel is inside or outside a region, which we denote as the "insideness" problem. Many Deep Neural Networks (DNNs) variants excel in segmentation benchmarks, but regarding insideness, they have not been well visualized or understood: What representations do DNNs use to address the long-range relationships of inside- ness? How do architectural choices affect the learning of these representations? In this paper, we take the reductionist approach by analyzing DNNs solving the in- sideness problem in isolation, ie. determining the inside of closed (Jordan) curves. We demonstrate analytically that state-of-the of-the-art weeward and recurrent archi- tectures can implement solutions of the insideness problem for any given curve. Yet, only recurrent networks could learn these general solutions when the training enforced a specific "routine" capable of breaking down the long-range relation- ships. Our results highlights the need for new training strategies that decompose the learning into appropriate stages, and that lead to the general class of solutions necessary for DNNs to understand insideness.
INTRODUCTION
Image segmentation is necessary for complete image understanding. key component of image segmentation is to determine whether pixel is inside or outside region, ie. the "insideness" prob- lem (Ullman| 1984, 1996). Deep Neural Networks (DNNs) have been treeenduusly successful in image segmentation benchmarks, but it is not well understood whether DNNs represent insideness or how.
Insideness has been overlooked in DNNs for segmentation since they have been mainly applied to the modality of "semantic segmentation", ie. labelling each pixel with its object category (Ronneberger
et al. [2015] Yu & Koltun 2016 Visin et al., 2016)] [Badrinrayyaaan et al., 2017] Chen et 20188) Lateef & Ruichek] (219). In such cases, insideness is not necessary since a solution can rely only on object recognition. Yet, the recent need to solve more sophisticated visual tasks has fueled the development of DNNs with the ability to segment individual object instances,
Long et al. 2015;
2016 2017 Song et al. 2018 Chen et 2018a Hu al.) 2018 Maninis et al.) 2018) Liu et al. 2018b He et al. 2017). In these segmentation modalities, insideness plays central role, especially when there are few cues besides the boundaries of the objects, e.g. when there is lack of texture and color, and objects are unfamiliar. Thus, insideness is necessary to achieve true generalization image segmentation.
rather than object categories (Li et al.
In this paper, we investigate derived and learned insideness-related representations in DNNs for segmentation. We take the reductionist approach by isolating insideness from other components in image segmentation. We analyze the segmentation of closed curves, similar to the methodology in Minsky & Papert's 's historic book Perceptrons (Minsky & Papert] [969).. In this way, we distill insideness minimum representation by eliminating other components.
We analytically demonstrate that two state-of-the. network architectures, namely, DNNs with dilated convolutions (Yu & Koltun| 2016; Chen et al.) 2018b) and convolutional LSTMs (ConyL- STMs) (Xingiaan et al. (2015). among other networks, can exactly solve the insideness problem for any given curve with network sizes that are easily implemented in practice. The proofs draw

---

Under review as a conference paper at ICLR 2020
algorithmic ideas from classical work on visual routines (Ullman intersection method and the coloring method, to derive equivalent neural networks that implement these algorithms. Then, in a series of experiments with synthetically generated closed curves, evaluate the capabilities of these DNNs to learn the insideness problem. The experiments show that when using standard training strategies, the DNNS do not learn general solutions for insideness, even though these DNNs are sufficiently complex to capture the long-range relationships. The only net- work that achieves almost full generalization in all tested cases a recurrent network with a training strategy designed to encourage a specific mechanism for dealing with long- -aage relationships.
1984
1996), namely, the ray-
These results add to the growing body of works that show that DNNs have problems in learning to solve some elemental visual tasks (Linsley et al. 2018 Liu et al.) [018aa] Wu et al., 2018 [hhale- Shwartz et al. 2017). Shalev-Shwartz et al. (2017) introduced several tasks that DNNs can in theory solve, as it was shown mathematically, but the networks were unable to learn, not even for the given dataset, due to difficulties in the optimization with gradient descent. In contrast, the challenges report for insideness are related to poor generalization rather than optimization, ments show the networks succeed in solving insideness for the given dataset. [insley et al. (2018) introduced new architectures that better capture the long-ran oongerange dependencies in images. Here, show that the training strategy has a big impact in capturing the long-range dependencies. Even the DNNs tested had the capacity to capture such long-range dependencies, they do not learn general solution with the standard training strategies.
our experi-
2 THE REDUCTIONIST APPROACH TO INSIDENESS
We now introduce the paradigm that will serve to analyze insideness-related representations in DNNs. Rather than using natural images, we use synthetic stimuli that solely contains closed curve. In this way. we do not mix the insideness problem with other components of image segmen- tation found in natural images, egg. self-similarity of segments at the level of object categories or parts, representation of the hierarchy of segments, etc. These components will be studied separately in future works, and finally put together to improve and understand how DNNs segment images.
Let X E {0, NNN be image matrix of size N X N pixels. We use XI,j and (X);.² in- distinguishably, to denote the value of the image in position (). We use this notation for indexing elements in any of the images and matrices that appear in the rest of the paper. Also, in the figures we use white and black represent 0 and 1, respectively.
Insideness refers to finding which pixels are in the inside and which ones in the outside of closed curve. We assume without loss of generality that there only one closed curve in the image and that it is a digital version of Jordan curve (Kong, (001), ie. a closed curve without self-crosses nor self-touches and containing only horizontal and vertical turns, as shown in Fig. [ We further assume that the curve does not contain the border of the image. The curve is the set of pixels equal to and is denoted by Fx = ((i,j) X1,= =
The pixels in X that are not in Fx can be classified into two categories: the inside and the outside of the curve (Kong 2001). We define the segmentation of X as S(X) E (0, NxN, where
{
O if XL, is inside
S(X) Dij =
(1)
if Xf, is outside
and for the pixels in Fx, the value of S(X) (., can be either 0 or 1. Note that unlike object recogni- tion. the definition of insideness rigorously and uniquely determined by the input image itself.
The number of all digital Jordan curves is enormous even if the image size is relatively small, e.g. it more than 10 for the size 32 32 (App.A)) A). In addition, insideness is global problem; whether pixel is inside or outside depends on the entire image, and not just on some local area around the pixel. Therefore, simple pattern matching, ie. memorization, is impossible in practice.
3 CAN DNNS FOR SEGMENTATION SOLVE INSIDENESS?
The universal approximation theorem (Cybenko 1989) tells us that even a shallow neural network is able solve the insideness problem. Yet, it could be that the amount of units is too large to
2

---

Under review as a conference paper at ICLR 2020
Figure 1: Intersections of the Ray and the Curve. (a) Example of ray going from one region to the opposite one when crossing the curve. (b) Example of ray staying the same region after intersecting the curve. (c) All cases in which a ray could intersect a curve. In the three cases above the ray travels from one region to the opposite one, while in the two cases below the ray does not change regions.
be implementable in practice. In this Section, we introduce two DNN architectures that are able solve the insideness problem at perfection and they are easily implementable in practice. One architecture is feed-forward with dilated convolutions (Yu & Koltun 2016 Chen et al., 2018b) and the other is recurrent: a ConvLSTM (Xingiian et al. 2015).
3.1 FEED-FORWARD ARCHITECTURE WITH DILATED CONVOLUTIONS
Dilated convolutions facilitate capturing long-range dependencies which are key for segmenta- Chen tion (Yu & Koltun 2016 Chen et al.] 2018b). To demonstrate that there are architectures with dilated convolutions that can solve the insideness problem. we borrow insights from the rayiintersection method. The inyerrternection method (Ullman) 1984, 1996), also known as the crossings test or the even-odd test (Haines) 1994), is built on the following fact: Any ray that goes from a pixel to the border of the image alternates between inside and outside regions every time it crosses the curve. Therefore, the parity of the total number of such crossings determines the region to which the pixel belongs. If the parity is odd then the pixel is inside, otherwise it is outside (see Fig. TT..
The definition of crossing should take into account cases like the one depicted Fig. [b, which the ray intersects the curve, but does not change region after the intersection. To address these cases, we enumerate all possible intersections of a ray and a curve, and analyze which cases should count consider only horizontal
crossings and which ones should not. Without loss of generality, rays. As we can see in Fig. [. there are only five cases for how a horizontal ray can intersect the curve. The three cases the top of Fig. [T] are crosses because the ray goes from one region the opposite one, while the two cases at the bottom (like in Fig. [T)) are not considered crosses because the ray remains in the same region.
Let Xii,j) E {0, 10 be a horizontal ray starting from pixel (i, which we define as
(i.j) = [Xi, Xijt1, Xis+2, X.,N, 0, O.....)). Oj.
where zeros are padded to the vector if the ray goes outside the image, such that (ii is always of dimension N. Let (i, X( 1, be the inner product of the ray starting from (i,j) and the
ray starting from the pixel below, (1)). Note that the contribution to this inner product from the three cases the top of Fig. [ (the crossings) is odd, whereas the contribution from the other two intersections is even. Thus, the parity of (ii,j) X(i + 1,5) is the same the parity of the total number of crosses and determines the insideness of the pixel (f,
S(X), = parity (X(1.)) X(i 1.5)).
Dilated convolutions, also called atrous convolutions, are convolutions with upsampled kernels, which enlarge the receptive fields of the units but preserve the number of parameters of the kernel (Yu) & Koltun 2016 Chen et al. 2018b). In App. B we prove that equation can be easily implemented with a neural network with dilated convolutions. The demonstration is based on implementing the dot product in equation 3 with multiple layers of dilated convolutions, as they facilitate capturing the information across the ray. The number dilated convolutional layers is equal to the logarithm in base-2 of the image size, N. The dot product can also be implemented with two convolutional
3

---

Under review as a conference paper at ICLR 2020
tann
M-
H"
Expand
Block
X
(a)
(b)
Figure 2: The Coloring Method with ConvLSTM. (a) The coloring method consists of several iter- ations of the coloring routine, ie. expanding the outside region and blocking on the curve. (b) Diagram of the ConvLSTM implementing the coloring method, we highlight the connections be- tween layers that are used for insideness. -X denotes the element-wise "Boolean not" of X.
layers, but with the drawback of using long kernel of size x N. The multiple dilated convolutions use kernels of size x 3. and they are equivalent the long kernel of 1 x N. Finally, the parity function in equation i implemented by adapting the network introduced by (Shalev-Shwartee et al. (017), which yields
layer convolutional network with 1 kernels.
Note that the proof introduces the smallest network we could find that solves the insideness problem with dilated convolutions. Larger networks than the one introduced can also solve the insideness problem, as the network size can be reduced by setting kernels to zero and layers to implement the identity operation.
3.2 RECURRENT ARCHITECTURE: CONVOLUTIIONAL LSTMS
Convolutional LSTM (ConvLSTMM (Xingjian et al. 2015) is another architecture designed to handle long-range dependencies. We now show that a ConvLSTM with just one kernel of size x 3 is sufficient solve the insideness problem. This is achieved by exploiting its internal back-projection of the LSTM, ie. the flow of information from a posterior layer to an anterior layer.
Our demonstration is inspired by the coloring method (Ullman 1984 gorithm for the insideness problem. This algorithm is based on the fact that neighboring pixels not separated by the curve are in the same region. We present a version of this method that will allow us to introduce the network with an LSTM. This method consists of multiple iterations of two steps: (i) expand the outside region from the borders of the image (which by assumption are in the outside region) and (ii) block the expansion when the curve is reached. The blocking operation prevents the outside region from expanding to the inside of the curve, yielding the solution of the insideness problem, as depicted in Fig. 2a. We call one iteration of expanding and blocking coloring routine.
1996), which is another al-
We use E E {0, 1) NNN (expansion) and B E {0, N (blocking) to represent the result of the two operations after iteration l. A The coloring routine can then be written (i) E Expand (B'-1) and (ii) B = Block Fx). Let B maintain a value known be outside and 0 for all pixels whose region is not yet determined
for all pixels that belong to the curve. Thus, we initialize Bd to have value 1 (outside) for all border pixels of the image and O for the rest. In step (i), the outside region of B is expanded by setting also to 1 (outside) its neighboring pixels, and the result is assigned to E Next, in step (ii), the pixels in E' that were labeled with a (outside) and belong to the curve, Fx, are reverted assigned to B'. This algorithm ends when the outside region can not expand anymore, which is at most after 22 iterations (worst case where each iteration expands the outside region by only one pixel). Therefore, we have N = S(X).
(inside), and the result is
In App. D we demonstrate that a COnVLSTM with one kernel applied on image X can implement the coloring algorithm. In the following we provide a summary of the proof. Let I', F*, O'. C., and H' R.M. X be the activations of the input, forget, and output gates, and cell and hidden states of a ConvLSTM at step t, respectively. By analyzing the equations of the ConVLSTM (equation IT] and equation 12 in App. D we see that the output layer, O', back-projects the hidden layer,
4

---

Under review as a conference paper at ICLR 2020
H'. In the coloring algorithm. E' and B are related in a similar manner. Thus, we define O =E' (expansion) and H' = B' (blocking). The 2 factor is a technicality due to non-linearities, which is compensated in the output gate and has relevance in this discussion.
We initialize H = 3 B (recall B is 1 for all pixels in the border of the image and 0 for the rest). The output gate expands the hidden representations using one 3 x 3 kernel. To stop the outside region from expanding to the inside of the curve, H' takes the expansion output Of and sets the pixels at the curve's s location 0 (inside). This the same as the element-wise product of O' and the "Boolean not" of X, which is denoted as -x. Thus, the blocking operation can be implemented as H OO' ④ -X), and can be achieved C' is equal to -X. In Fig. 2 we depict these computations.
In App. D we show that the weights of a ConvLSTM with just one kernel of size 3 x 3 can be configured to reproduce these computations. A key component is that many of the weights use value that tends to infinity. This value denoted as q and used to saturate the non-linearities of the ConvLSTM, which are hyperbolic tangents and sigmoids. Note that it is common in practice to have weights that asymptotically tend to infinity, e.g. when using the cross-entropy loss to train a network (Soudry et al. 2018). In practice, we found that saturating non-linear units using Q 100 is enough to solve the insideness problem for all curves in our datasets. Note that only one kernel is sufficient for ConvLSTM to solve the insideness problem, regardless of image size. Furthermore, networks with multiple stacked ConvLSTY and more than one kernel can implement the coloring method by setting unnecessary ConvLSTMs implement the identity operation (App. D and the unnecessary kernels to O.
Finally, we point out that there are networks with a much lower complexity than LSTMs that can solve the insideness problem, although these networks rarely find applications in practice. In App. D we show that convolutional recurrent network as small as having one sigmoidal hidden unit per pixel, with a 3 x 3 kernel, can also solve the insideness problem for any given curve.
4 CAN DNNS FOR SEGMENTATION LEARN INSIDENESS?
After having identified DNNs that have sufficient complexity to solve the insideness problem, we focus on analyzing whether these solutions can be learnt from examples. We report experiments on synthetically generated Jordan curves. The goal of the network is to learn to predict for each pixel in the image whether it is inside or outside of the curve. In the following, we first describe the experimental setup, then analyze the generalization capabilities of the DNNs trained in standard manner and finally, analyse the advantages of the recurrent networks.
4.1 EXPERIMENTAL SETUP
Datasets. Given that the number of Jordan curves explodes exponentially with the image size, procedure that could provide curves without introducing bias for learning is unknown. We introduce three algorithms to generate different types of Jordan curves. For each dataset, we generate 95K images for training, 5K for validation and 10K for testing. All the datasets constructed to fulfill the constraints introduced in Sec. In addition, for testing and validation sets, we only use images that are dissimilar all images from the training set. Two images are considered dissimilar if at least 25% of the pixels of the curve are in different locations. In the following, we briefly introduce each dataset (see App. For details). Fig. B.. shows examples of curves for each dataset. Polar Dataset (32 x 32 pixels): We use polar coordinates to generate this dataset. We randomly select the center of the figure and a random number of vertices that are connected with straight lines. The vertices are determined by their angles and distance with respect to the center of the figure. We generate 5 datasets with different maximum amount of vertices, namely, 4, 9, 14, 19 and 24, and refer to each dataset by this number, e.g. 24-Polar.
Spiral Dataset (42 x 42 pixels): The curves are generated by growing intervals of a spiral in random directions from random starting point. The spiral has random thickness at the different intervals. Digs Dataset (42 x 42 pixels): We generate a rectangle of random size and then, we create "digs" of random thicknesses in the rectangle. The digs are created sequentially random number of times.
Evaluation metrics. From the definition of the problem in Sec. 2 the pixels in the Jordan curve Fx are not evaluated. For the rest of the pixels, we the following metrics:
5

---

Under review as a conference paper at ICLR 2020
Examples of Jordan Curves of Each Dataset
(%)
100
Test Acc. on Polar
per image acc. (%)
100
Test Acc. Polar
98
Diated
Diated
Ray-nf.
50
Ray It.
96
2
Uiet
Like
2LSTM
1STM
1LSTM
q
14
19
24
14
19
24
Polar Dataset
Polar Dataset
(b)
(c)
Dilated
LSTM
Generalization Acc. on Polar
Generalization Acc. on Polar
Spinal
(9g
100
per image acc. (96)
100
Train Set
Train Set
Digh
19 Set
Polar
Tast
(d)
(e)
Datasets and Results in Polar. (a) Images of the curves used train and test the DNNs. Each row correspond to different dataset. Intra cara-dataset evaluation using (b) per pixel accuracy and (c) per image accuracy. Evaluation using the testing set each Polar datasets for (d) Dilated and (e) 2-LSTM networks.
Figure 3:
Per pixel accuracy (%): It is the average of the accuracy for inside and outside, evaluated sepa- rately. In this way, the metric weights the two categories equally, as there is an imbalance of inside and outside pixels.
Per image accuracy (%): We use a second metric which is more stringent. Each image is consid- ered correctly classified if all the pixels in the image correctly classified.
Architectures. We evaluate the network architectures that we analyzed theoretically and also other relevant baselines:
Ford-forward Architecture: We use the dilated convolutional DNN (Dilated) introduced in Sec. 3.1 We also evaluate two variants of Dilated, which the Ray-intersection network (Ray- in which uses a receptive field of x N instead of the dilated convolutions, and a convolutional network (CNN), which has all the dilation factors to d Finally, we also evaluate UNer. which is a popular architecture with skip connections and de- de-convolutions (Ronneberger et al. (015)). Recurrent Architectures. We test the ConvLSTM (I-LS7MM corresponding to the architecture troduced in Sec. 3.2 We initialize the hidden and cell states to O (inside) everywhere except the border of the image which is initialized to (outside). such that the network can learn to color by expanding the outside region. We also evaluate 2-layers ConvLSTM (2-LSTM) by stacking one 1- LSTM after another, both with the initialization of the hidden and cell states of the I-LSTM. Finally, to evaluate the effect of such initialization, we test the 2-LSTM without it (2-LSTM w/o init.). ie. with the hidden and cell states initialized all to O. We use backpropagation through time by unrolling 50 time steps, for both training and testing.
The parameters are initialized using Xavier initialization (Glorot & Bengio 2010). The derived parameters obtained in the theoretical demonstrations obtain 100% accuracy but do not use them in this analysis as they are not learned from examples. The ground-truth consists on the insideness for each pixel in the image, in equation [ For all experiments, we use the cross-entropy with softmax as the loss function averaged accross pixels. Thus, the networks have two outputs per pixel (note that this does not affect the result that the networks are sufficiently complex to solve insideness, as the second output can be set to a constant threshold of 0.5). We found that the cross-entropy loss leads better accuracy than other losses. Moreover, we found that using a weighted loss improves the accuracy of the networks. The weight, which we denote as a, multiplies the loss relative to inside, and (1 ax) multiplies the loss relative to outside. This a is a hyperparamter that we tune and can be equal to 0.1, 0.2 and 0.4. We try batch sizes of 32, 256 and 2048 when they fit in the GPUs' memory (12GB), and we try learning rates from to 10 (dividing by 10). We train the networks for all the hyperparameters for at least 50 epochs, and until there is no more improvement of the validation set loss. In the following, we report the testing accuracy for the hyperparameters that achieved the highest per image accuracy at the validation set. We test large
Learning.

---

Under review as a conference paper at ICLR 2020
Dilated
CNN
UNet
LSTM
2 LSTM, w/olnit.
100
Polar
99
4.6
94
99
3.1
97
99
5.3
98
99
14
99
.66
80
Set
60
Spiral
18
99
92
24
99
98
0.56
99
98
30
99
99
31
99
99
40
Digs
16
0.88
8.7
0.69
11
32
1.3
10
23
3.7
58
14
28
20
Polar Spiral Both Train Set
Polar Spiral Both Train Set
Polar Spiral Both Train Set
Spiral Train Set
Polar Spiral Train Set
Evaluation of the networks trained in 24-Polar, Spiral and both 24-Polar and Spiral datasets. The tesing sets are 24-Polar, Spiral and Digs datasets.
Figure 4: Cross-dataser Results.
set of hyperparameters (we trained several thousands of networks per dataset), which we report them in detail in App. G
4.2 RESULTS
Intra-dataset Evaluation. In 3p and с we show per pixel and per image accuracy for the networks trained on the same Polar dataset that are being tested. Dilated, 2-LSTM and UNet achieve a testing accuracy very close to 100%, but Ray-int. and 1-LSTM perform much worse. Training accuracy of Ray-int. and 1-LSTM is the same as their testing accuracy (Fig, [Lop and b). This indicates an optimization problem similar to the cases reported by Shaley-Shwarte et al. (2017). Note that for the network with ConvLSTMs, we need two LSTMs to achieve an accuracy very close to 100%, even though one LSTM is sufficient to generalize, as we have previously shown. Similarly, both Dilated and Ray-int. to understand why stochastic gradient descend performs so differently in each of these architectures can all generalize in theory. Finally, note that the per pixel accuracy is in most cases very high, and from now on, we only report the per image accuracy.
able to generalize, but only Dilated does so. It is open question
Cross-dataset Evaluation. We now evaluate if the networks that have achieved very high accuracies (Dilated, 2-LSTM and UNet), have learnt the general solution of insideness that we introduced in Sec. B. To do so, we train on one dataset and test on the different one. In Fig Bl and e, we observe that Dilated and 2-LS7M do not generalize to Polar datasets with larger amount of vertices than the Polar dataset on which they were trained. Only if the networks are trained 24-Polar, the networks generalize in all the Polar datasets. The same conclusions can be extracted for UNet (Fig. L.6e).
We further test generalization capabilities of these networks beyond the Polar dataset. In this more broad analysis, also include the CNN and 2-LSTM w/o init, by training them on 24-Polar, Spiral and both 24-Polar and Spiral, and test them on 24-Polar, Spiral and Digs separately. We can see in Fig. 4 that all tested networks generalize to new curves of the same family the training set. Yet, the networks do not generalize to curves of other families. In Fig. [.12 we show qualitative examples of failed segmentations produced by networks trained 24-Polar and Spiral and tested on the Digs dataset.
Furthermore, note that using a more varied training set ("Both") does not necessarily lead to better cross-dataset accuracy in all cases. For example, for UNet and 2-LSTM w/o init., training on Polar achieves better accuracy in Digs than when training on "Both". Also, for Dilated, training on "Both" harms its accuracy: the accuracy drops more than 6% in P4lPolar and Spiral. In this case, the training accuracy close to 100%, which indicates a problem of overfitting. We tried to address this problem by regularizing using weight decay, but it did not improve the accuracy (App.
Visualization. We now visualize the networks to study the representations learnt. In Fig. I.7 we analyze different units of Dilated trained on 24-Polar and Spiral. We display three units of the same kernel from the second and sixth layers, by showing the nine images in the testing set that produce the unit to be most active across all images (Zeiler & Fergus] 2014). For each image, we indicate the unit location by a gray dot. The visualizations suggest that units the second layer are tuned to local features (e.g. Unit 19 is tuned to close parallel lines), while in layer 6 they are tuned to global ones (e.g. Unit 27 captures the space left in the center of a spiral). These features seem to capture characteristics of the curves in the training set. This is quite different from the representations that
7

---

Under review as a conference paper at ICLR 2020
100
1idden
80
per image accuracy
hidden
polar digs spiral
Ingur
Coloring net 2-LSTM Dilated
hidden
hislen--1
impu:
20
hiklan
ingur
number of training examples
hiddon
(a)
Figure 5: Learning the Coloring Routine. (a) 64 possible inputs and outputs of the training set of the Coloring Net for the relevant inputs. The Coloring Net is trained to reproduce one step of the Coloring Routine. (b) Per image accuracy for different datasets training with different amounts of examples. 2-LSTM and Dilation are trained on 24-Polar.
derived theoretically, which accumulate the number of crossings in ray from each pixel. This is further supported by visualizing the feature maps in Fig.
In Fig. I.II display the feature maps of 2-LSTM trained 24-Polar and Spiral. The figure shows the feature maps of the layers at different time steps. We can see that the network expands the borders of the image, which have been initialized to outside. Yet, also expands the curve, which is not what our analytical solution does (Fig. I.10). This explains why this representation does not generalize new datasets, because it not possible know the direction where to expand the curve without having priori knowledge of the curve.
4.3 LEARNING THE COLORING ROUTINE IN ISOLATION
We now analyse a property the coloring method that is relevant for learning: the coloring routine does not contain long-range relationships because it just takes into account 3 x 3 neighbourhoods. The long-range relationships are captured by applying the coloring routine multiple times. The standard training strategy enforces the ground-truth after the last step, and hence, requires learning the full long-range relationships at once. Yet, if we decompose the learning of insideness into learning the coloring routine in isolation, the problem becomes much simpler it only requires learning an operation in a 3 x neighbourhood.
The coloring routine can be learned by enforcing each step the ground-truth produced by the routine, rather than waiting until the last step. The inputs of a step are the image and the hidden state of the previous step. Recall that the coloring routine determines that pixel is outside if there is at least one neighbor assigned to outside that is not at the curve border. All input cases (64) are depicted in Fig. 5h. leaving the irrelevant inputs for the coloring routine at O. During learning, such irrelevant pixels are assigned randomly value of 0 or 1.
We have done an architecture search learn the coloring routine. We could not make any of the previously introduced LSTM networks fit step of the coloring routine due to optimization problems. Yet, we found simple network that succeeded: a convolutional recurrent neural network with sigmoidal hidden layer and an output layer that backprojects to the hidden layer. The kernel sizes are 3 and x for the hidden and output layers, respectively, and we use kernels. We call this network Coloring Net. Observe that this network is sufficiently complex to solve the insideness problem, because is the network introduced in App. with an additional layer and connections.
The Coloring Net reaches 0 training error about 40% of the times after randomly initializing the parameters. After training the Coloring Ner in one step, we unroll it and apply it to images of Jordan curves. In Fig. (5b report the accuracy of the Coloring Net in the 24-Pol Spiral and Digs datasets, for different amounts of training examples (generated through adding more variations of the irrelevant inputs). We compare the results with the 2-1.7MM and Dilation networks previously
8

---

Under review as a conference paper at ICLR 2020
introduced, trained 24-Polar. We see that with less than 1000 examples the Coloring Net is able to generalize to any of the datasets, while the other networks do not. This demonstrates the great potential of decomposing the learning facilitate the emergence of the routine.
CONCLUSIONS AND FUTURE WORK
We have shown that DNNs with dilated convolutions and convolutional LSTM that are imple- mentable in practice are sufficiently complex to solve the insideness problem for any given curve. When using the standard training strategies, the units in these networks become specialized to detect characteristics of the curves in the training set and only generalize to curves of the same family as training, even when using large number of training examples. Yet, we found that when simple recurrent networks supervised to lear the coloring routine, which does not contain long-range relationships, the general solution for the insideness problem emerged using orders magnitude less data.
This raises the question of whether these findings can be translated to improvements of segmenta- tion methods for natural images. The following experiment suggests that state-of-the-an methods for image segmentation suffer from learning general solutions to the insideness problem. We evalu- off-the-shelf methods, namely DEXTR (Maninis et 2018) for instance segmentation and DeepLabv3+ (Chen et al. (2018c) for semantic segmentation, which have been trained on PASCAL VOC 2012 (Everingham al.) and ImageNet (Russakovsky determine the insideness for vast majority of curves, even after fine-tuning in the Both dataset (Deeplabv3+ achieved 36.58% per image accuracy in Both dataset and 2.18% Digs, see imple- mentation details and qualitative examples in Ap. Thus, extending these methods with recurrent connections and a training strategy that could capture the coloring routine, could help increase their segmentation accuracy, especially for different conditions on which they have been trained.
al.] 2015). These methods fail to
REFERENCES
A140517: Number of cycles in n x grid. The On-Line Encyclopedia of Integer Sequences. [Online]. Available: https: wwt.////ess./////////ee.. orq/A140517
Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. SegNet: A deep convolutional encoder- decoder architecture for image segmentation. TPAMI, 2017.
Liang-Chich Chen, Alexander Hermans, George Papandreou, Florian Schroff, Peng Wang, and Hartwig Adam. MaskLab: Instance segmentation by refining object detection with semantic and direction features. In CVPR, 2018a.
Liang-Chieh Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L Yuille. DeepLab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected CRFs. TPAMI, 2018b.
Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam. Encoder-decoder with atrous separable convolution for semantic image segmentation. CoRR, abs/1 htss/802.00211. 2018c. URL http::t/ttxii..oooo www. wwwpg//abb/BBBe 02611
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics control, signals and systems, 2(4):303-314 1989.
M. Everingham, L. Van Gool, C. K. Williams. J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge 2012 (VOC2012) Results. http://www.paccal- h/w.0///oooosoooood/e....mmm
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neu- ral networks. In In Proceedings of the International Conference on Artificial Intelligence and Statisties (AISTATSIO). Society for Artificial Intelligence and Statistics, 2010.
Eric Haines. Point in polygon strategies. In Paul Heckbert (ed.), Graphics Gems IV, pp. 24 26. Academic Press, 1994.

---

Under review as a conference paper at ICLR 2020
Frank Harary. Graph Theory. Addison-Wesd Wesley, 1969.
Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask R-CNN. ICCV, 2017.
Ronghang Hu, Piotr Dollár, Kaiming He, Trevor Darrell, and Ross Girshick. Learning to segment every thing. In CVPR, 2018.
Hiroaki Iwashita, Yoshio Nakazawa, Jun Kawahara, Takeaki Uno, and Shinichi Minato. Fast com- putation of the number of paths in grid graph. In The 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG2 2013), Tokyo, September 2013.
Artem M. Karavaev and Hiroaki and Iwashita. Table of a(n) for 0.266. In The On-Line Encyclopedia of Integer Sequences. [Online]. Available:
b140517.txt
T. Yung Kong. Digital topology. In Larry S. Davis (ed.), Foundations of Image Understanding, pp- 73 93. Springer, 2001.
Fahad Lateef and Yassine Ruichek. Survey on semantic segmentation using deep learning tech- niques. Neurocomputingg 2019.
Ke Li, Bharath Hariharan, and Jitendra Malik. Iterative instance segmentation. In CVPR, 2016.
Yi Li, Haozhi Qi, Jifeng Dai, Xiangyang Ji, and Yichen Wei. Fully convolutional instance-aware semantic segmentation. CVPR, 2017.
Drew Linsley, Junkyung Kim, Vijay Veerabadran, Charles Windolf, and Thomas Serre. Learning long-range spatial dependencies with horizontal gated recurrent units. In NeurIPS, 2018.
Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski. An intriguing failing of convolutional neural networks and the coordconv solution. In NeurIPS, 2018a.
Shu Liu, Lu Qi, Haifang Qin, Jianping Shi, and Jiaya Jia. Path aggregation network for instance segmentation. In CVPR, 2018b.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In CVPR, 2015.
Kevis-Kokitsi Maninis, Sergi Caelles, Jordi Pont-Tuset, and Lue Van Gool. Deep extreme cut: From extreme points to object segmentation. In CVPR, 2018.
Marvin L. Minsky and Seymour A. Papert. Perceptrons: An Introduction to Computational Geom- eiry. MIT Press, 1st edition, 1969.
Olaf Ronneberger. Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomed- ical image segmentation. In International Conference on Medical Image Computing and Computer-Assisted Intervention, 2015.
Azriel Rosenfeld.
Connectivity in digital pictures. ACM, 1701):466160, January 1970. ISSN 0004-5411. doi: 10.1145/321556.215500 URLhttp:://oo wttp://.............oo.o...o
B21556. 321570
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei- Fei. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211-522, 2015.
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In ICML, 2017.
Gwangmo Song, Heesoo Mycong, and Kyoung Mu Lee. SeedNet: Automatic seed generation with deep reinforcement learning for robust interactive segmentation. In CVPR, 2018.
10

---

Under review as a conference paper at ICLR 2020
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 2018.
Shimon Ullman. Visual routines.
Cognition, 18:97-159, 1984.
Shimon Ullman. High-Level Vision: Object Recognition and Visual Cognition. MIT Press, 1st edition, 1996.
Francesco Visin, Marco Ciccone, Adriana Romero, Kyle Kastner, Kyunghyun Cho, Yoshua Bengio, Matteo Matteucci, and Aaron Courville. ReSeg: A recurrent neural network-based model for semantic segmentation. In CVPR Workshops, 2016.
Xiaolin Wu, Xi Zhang, and Xiao Shu. Cognitive deficit of deep learning in numerosity. In AAAI, 2018.
SHI Xingjian, Zhourong Chen, Hao Wang, Dit- Yan Yeung, Wai-Kin Wong, and Wang-chun Woo. Convolutional LSTM network: A machine learning approach for precipitation nowcasting. In NIPS, 2015.
Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. In ICLR, 2016.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In ECCV, 2014.

---

Under review as a conference paper at ICLR 2020
(b)
Figure A.I: Subgraph Representations of Figures. (a) A figure in an image of size 5 5 pixels (left) and subgraph representation grid graph of x vertices (right). (b) Cycles that are not digital Jordan curves (top) and their correspondents (bottom).
A NUMBER OF DIGITAL JORDAN CURVES
We now introduce procedure to derive a lower bound of the number of Jordan curves in an image. We represent an image of size N N pixels by using grid graph (square lattice) with N x N vertices. We employ 4-adjacency for black pixels and corresponding grid points, and 8-adjacency (the set of black pixels) corresponds
for white pixels and their counterpart. Then, subgraph of the base grid graph (Fig, A.
In this representation, a digital Jordan curve is defined subgraph specified by a sequence of vertices (vo, VI. Vi...., vr.) satisfying the following conditions (Rosenfeld 1970 Kong 2001
1. 4,4,
2. v. if and only if and
3. is 4-adjacent to v, if and only if = s (mod L 1).
Note that conditions and 2 defines cycle (Harary 1969) in grid graph. Therefore, any digital Jordan curve is cycle but not vice versa. Figure A.I shows examples of cycles that are not digital Jordan curves.
The numbers of all cycles in grid graphs of different sizes were computed up to 27 x 27 ver- tices (Twashita al., 2013 A14), and utilize this result to get lower bounds for the number of digital Jordan curves with the following considerations.
Although cycle in a grid graph is necessarily digital Jordan curve as shown above, we can obtain a digital Jordan curve in a larger image from any cycle by "upsampling" as shown in Fig. A.2 Note that there are other digital Jordan curves than the ones obtained this manner (therefore we get a lower bound with this technique). See Fig. A.2p for examples.
We also consider "padding" shown Fig. A.3 assure that digital Jordan curve does not contain the border of image (this is what we assume the main body of the paper).
Taking everything into consideration, we can obtain lower bound of the number of digital Jordan curves in an N x N image that does not contain border pixels utilizing the above-mentionel re- sult (Iwashita et al. 20133 A14), upsampling and padding. Table shows lower bounds obtained in this way. For example, starting with the row 2 of (Karavaev & Iwashita) in (A14) (this represents the number all cycles the grid graph with 3 x vertices), we get a lower bound 13 for the number of digital Jordan curves in 5 5 images by considering the upsampling and get the same number as a lower bound for the number of digital Jordan curves that do not contain border pixels in 7 x images by considering the padding.
12

---

Under review as a conference paper at ICLR 2020
(a)
(b)
Figure A.2: "Upsampling" Operation and Its Limitations. (a) Depiction of "upsampling" operation. (b) Digital Jordan curves that cannot be obtained by the upsampling shown in (a). (Left) The issue is the place of the digital Jordan curve. We can get the same curve on the upper-left, upper-right, lower-left and lower-right corners but cannot get the one in the center. (Right) The issue is the length of the side. We cannot get side with 4 vertices (4 pixels) nor with even number vertices (pixels) in general.
Figure A.3: Depiction of "Padding" ".
B INSIDENESS WITH DILATED CONVOLUTIONAL NETWORKS
We first introduce feed-forward convolutional DNN for which there exist parameters that repro- duce equation 3 Then, we show that one of the layers in this network can be better expressed with multiple dilated convolutions.
B. CONVOLUTIONAL DNN TO IMPLEMENT THE RAY-INTERSECTION METHOD
The smallest CNN that we found that implements the ray-intersection method has 4-layers. As we show the following, the first two layers compute X((i.j) X + 1,j), and the last two layers compute the parity. We use (k) E N and [+] to denote the activations of the units at the k-th layer, and the ReLU activation function, respectively. Fig. [.44 depicts the architecutre.
First and Second Layer: Inner product. For the sake of simplicity, we only use horizontal rays, but the network that introduce be easily adapted to any ray direction. The first layer imple- ments all products needed for the inner products across all rays in the image, ie. X X Vii,j)- Note that there is exactly one product per pixel, and each product can be reused for multiple rays.
For convenience, (!))) represents the product in pixel (i, ie. H Xi.5 X1+1,5- Since the input consists of binary images, each product be reformulated
#
{
if X1, = =X =1 otherwise
(4)
This equality can be implemented with a ReLU: H.) = [1 X.,; + -X,115 1]+ Thus, (()) convolutional layer with kernel that détects the intersections shown in Fig. [T. This
13

---

Under review as a conference paper at ICLR 2020
Table 1: Lower bounds (LBs) of the number of digital Jordan curves in N N images that do not contain border pixels.
5
7
33
35
L.
13
213
1.203 x 10#7
1.157 x 10
3.395 x 10
6.71 x 10
X
11
S(X)
1010
32/2
$221
422
Figure B.4: The Ray-Intersection Network. (a) The receptive field colored in green has size 1 x N, and can be substituted by an equivalent network composed of multiple dilated convolutions. (b) The x N kernel of the ray-intersection network is equivalent to multiple dilated convolutional layers. The figure shows an horizontal ray of the activations of several layers, starting from the first layer H(2), The green arrows indicate the locations in the ray that lead to the desired sum of the activations, ie. the sum of the ray.
layer can also be implemented with standard convolutional layer with 3 x 3 kernel, by setting the unnecessary elements of the kernel
The second layer sums over the products of each ray. To do so, we use kernel of dimension 1 x N with weights equal and bias equal 0, ie. 11 1 1Ix ! X (i. X(i + 1,j), in which 1 I denotes the matrix of size / x J with all entries equal to 1. Zero Zero-padding is used to keep the kernel size constant across the image.
Note that the shape of the kernel, x N. is not common in the DNN literature. Here, it is necessary capture the long-range dependencies of insideness. We show in the next subsection that can be substituted by multiple layers of dilated convolutions.
Third and Fourth Layers: Parity. To calculate the parity of each unit's value in H (2), we borrow the DNN introduced by SShalev-Shwartz et al. (2017) (namely, Lemma 3 in the supplemental material of the paper). This network obtains the parity of any integer bounded by a constant C. The network has 3C/2 hidden ReLUs and one output unit, which 1 the input is even, otherwise (see App. C for details).
We apply this parity network all units (2) via convolutions, reproducing the network for each unit. Since a ray through closed curve in an N x N image can not have more than N crossings, C upper bounded by N. Thus, the third layer has 3N/2 kernels, and both the third and output layer are convolutions with 1 x kernel. At this point we have shown that the DNN explained above is feasible practice, as the number of kernels is ON), and it requires no more than convolutional layers with ReLUs. The network has a layer with kernel of size 1 x N, and next we show that this layer is equivalent to several layers of dilated convolutions of kernel size x 3.
B.2 DILATED CONVOLUTIONS TO IMPLEMENT THE 1 x N KERNEL
We use *d to denote a dilated convolution, in which d is the dilation factor. Let H E N be the units of a layer and let K * be kernel of size i x k. A dilated convolution is defined Hu+dv,i+der Ky,u- in which Hi+do.j+dw is i + du or + dw are smaller than 0 or larger than N, ie. we abuse notation for the zero- prrddpddding-.. Note that in the dilated convolution the kernel is applied in sparse manner, every d units, rather than in consecutive units. See Yu & Koltun (216): Chen et al. (2018b) for more details on dilated convolutions.
as follows: (H N, K);; -
14

---

Under review as a conference paper at ICLR 2020
Recall the kernel of size x N is set to 1 1xN to perform the sum of the units corresponding to the ray in the first layer, ie. Loswen H1 iij+e We can obtain this long-range sum with a series of dilated convolutions using the following 3 kernel:
0
K
0
1
(5)
First, we apply this K to the H()) through *1 in order to accumulate the first two entries in the ray, which yields: (H)(2)) b. (H K)ts Easigi iij+t. As shown in Fig. B.4b, to accumulate the entries of the ray, we can apply K with dilated convolution of dilation factor = 2, which leads to (H{)) i.j Eosoca H!)) To further accumulate more entries of the ray, 1.j+0
we need larger dilation factors. It can be seen in Fig. B.4b that these dilation factors are powers of 2, which yield the following expression:
( 1.5 = (HH--)) 221-2 K)
Σ
iift"
(6)
US
Observe that when we reach layer logg (N) + 2, the units accumulate the entire ray of length N, ie. Eoswen H Networks with dilation factors 2 are common in practice, egg. Yu & Koltun (2016) uses these exact dilation factors.
In summary, DNNs with dilated convolutions can solve the insideness problem and are imple- mentable in practice, since the number of layers and the number of kernels grow logarithmically and linearly with the image size, respectively.
C PARITY NETWORK BY
ET AL. (2017)
To calculate the parity of each unit's value in (2), we borrow the DNN introduced by Shalev- Shwartz et al. (namely, Lemma 3 the supplemental material of SShale--Shware et al.] (2017). ). This network obtains the parity of any integer bounded by constant C. The network has hidden units with ReLUs and one output unit, which is 1 if the input is even, O otherwise. Since such a network requires an upper bound the number whose parity is being found, define C as the maximum number of times that a horizontal ray can cross Fx. This number can be regarded as an index express the complexity of the shape.
There is subtle difference between the network introduced by Shwlar-S et al. (2017) and the network we use in the paper. In Shalev-Shwarde et al. (2017). the input of the network a string of bits, but in our case, the sum is done in the previous layer, through the dilated convolutions. Thus, we use the network in Shalav-Shwartz al. (2017) after the sum of bits is done, ie. after the first dot product in the first layer in Shalev-Shwarzz et al. (2017).
S i < [C/2]]. the network has three hidden units that threshold at (2i - 2). 2i and (2i + !), ie. -0.5. 0.5, 1.5, 2.5, 3.5, 4, 4.5.... ... The output layer linearly combines all the hidden units and weights each triplet units by 2, -4 and 2. Observe that when the input is an odd number, the three units in the triplet are either all below or all above the threshold. The triplets that are all below the threshold contribute 0 to the output because the units are inactive, and the triplets that are all above the threshold also contribute 0 because the linear combination is 2(2i }) 4(2)) + 2(2i + + = O. For even numbers, the triplet corresponding to that even number has one unit below, equal and above the threshold. The unit that is above the threshold contributes 1 to the output, yielding the parity function.
To calculate the parity, for each even number between and (0 included), {2i
D COLORING ROUTINE WITH CONVOLUTIONAL LSTM
Here we prove that a LSTVLSTM can implement the coloring routine, namely, the iteration of the expansion and the blocking operations. A ConvL applied an image X is defined as the fol-
15

---

Under review as a conference paper at ICLR 2020
lowing set of layers (see Xingjian et al. (2015) for comprehensive introduction to the ConvLSTM):
I' = (W X + W * +b))
(7)
F (Waf
X + W bb))
(8)
Ö = tanh (W X + Whe * H 1- + bb) C = F' Φ C + r の C
(9)
(10)
O =0 a (W X W H bb)
(11)
H' O'= o tanh (C*)
(12)
where 1' F", "', and H' NNNN are the activation of the units of the input, forget, cell state, output and hidden layers at f, respectively. Note that C' has been decomposed with the help of the auxiliary equation defining C² Note also that each of these layers use a different set of weights that are applied X and to H' denoted as W E NxN with superindices that indicate the connections between layers, e.g. W are the weights that connect X to I. Similarly, the biases are denoted as E V x with the superindices indicating the layers. The symbols and O denote the (usual, not dilated) convolution and the element-wise product, respectively. Finally, and tanh are the sigmoid and the hyperbolic tangent, which are used as non- non-rineasssies.
We can see by analyzing equation I1 and equation 12 that the output layer, O', paok-projects to the hidden layer, H' In the coloring algorithm, E' and B' are related a similar manner. Thus, we define Oc E' (expansion) and H' 2/2 B' (blocking), as depicted in Fig.
2b. The & factor will become clear below, and does not affect the correctness. We initialize H 2 B (recall B is 1 for all pixels in the border of the image and 0 for the rest). We now show how to implement the iteration of the expansion and the blocking operations with the ConvLSTM:
(i) Expansion, O': We set the output layer in equation 11 in the following way:
O =a [2q 3x3
H
2 2 1NNN)
q
(13)
Note that this layer does not use the input, and sets the convolutional layer hho to use a 3 x kernel that is equal to 2g 1 xx3. in which g is a scalar constant, and the bias equal to N
For very large values of g. this layer expands the outside region. This can be seen by noticing that for a unit in H'-1, if at least one neighbor has value 1/2, then 0 limg (g) 1. Also, when all neighbouring elements of the unit are 0, then no expansion occurs because O lim o 8)
To stop the outside region from expanding the inside of the curve, H' takes the expansion output O' and sets the pixels at the curve's location to 0 (inside). This is the same as the element-wise product between Of and the element-wise "Boolean not" of X, which is denoted as - Thus, the blocking operation can be implemented as H' = (O' ) -X). Observe that if C = -x, this is equal to equation
(ii) Blocking, H':
12 of the LSTM, because tanh(0) = 0 and tanh(1) = 1/2, ie.
1 0c --X.
H' O' @ tanh (C*)
(14)
2
We can obtain C²_ = -X, by imposing I' = - and C = 11, as shown in Fig. 2b. To do so, 1 NxN, and equation & becomes the following
let Was -91111 1x1, Whi 0 ONxN, and b' 2
expression:
r lim a ( (-ql1x1 90000
+ 2
1 NNNN)
(15)
Observe that when & tends to infinity, we have 1i, lim o 1 when X1,; = 0 and
I limg a--3 3) 0 when X1, = 1, which means I' -X. Next, to obtain C' I', NxN and bc q1 NxN. This leads to the
set W wh we Whee 0 -NNNN. = NxN
desired result:
F' lim a (-qINxN) ONXN, 700
(16)
Ō lim tanh (91 NxN) = =NNNN -o
C² -'=ONXX cL-L 1 - -X
(17)
16

---

Under review as a conference paper at ICLR 2020
Thus, the coloring method can be implemented with network small one ConvLSTM with one kernel. A network with more than one kernel and multiple stacked ConvLSTM can also solve the insideness problem for any given curve. The kernels that are not needed to implement the coloring method can be just set to 0 and the Convl LSTM that are not needed should implement the identity operation, ie. the output layer is equal to the input. To implement the identity operator, equation [1 can be rewritten in the following way:
O' lim σ (q11x1 X 9 1 2
2
(18)
0-000
where Who 0ix is to remove the connections with the hidden units, and is the constant that tends to infinity. Observe that Xij 1, then O limmg-ce (g/2) = 1. If Xi, = 0, then O = limg (-2//2) = O. Thus, the ConvLSTM implements the identity operation.
E COLORING ROUTINE WITH A SIGMOIDAL CONVOLUTIONAL RNN
There are other recurrent networks simpler than a ConvLSTM that can also implement the color- ing algorithm. We introduce here convolutional recurrent network that uses sigmoids non- lincarities. Since it a convolutional network, for the sake of simplicity we just describe the op- erations done to obtain also corresponds to the output of the network. Let (hf ( be the hidden state of the output pixel indexed by j and its 4-neighbourhood, at step f. Let Xi, be the only relevant input im- age pixel. A necessary condition is that the outputs of the sigmoid should asymptotically be close to 0 1, otherwise the coloring routine would fade after many steps. It is easy check that ki a (1 (EREN, h4 5X... - -1/2) implements the coloring routine, where is the factor that ensures saturation the sigmoid.
output pixel in step. The network has only one hidden layer, which
F DATASET GENERATION
In Fig. F.5 show examples of curves in the datasets. In the following we provide more detailed description of the algorithms to generate the curves:
Polar Dataset (32 x 32 pixels): We polar coordinates to generate this dataset. We randomly select the center of the figure and a random number of vertices that are connected with straight lines. These lines constrained to follow the definition of digital Jordan curve in Sec. in the main paper (and App. A in this supplementary material). The vertices are determined by their angles, which are randomly generated. The distance with respect the center of the figure also randomly generated to be between 3 to 14 pixels away from the center.
We generate 5 datasets with different maximum amount of vertices, namely, 4, 9, 14, 19 and 24. We refer to each of these datasets as Polar with a prefix with the amount of vertices.
Spiral Dataset (42 42 pixels): The curves in these data set are generated from a random walk. First, a starting position is chosen uniformly at random from [10, 20] x [10, 20). Then, a segment of the spiral is built in the following way: random direction (up, down, left, right) and a random length from 3 to 10 are chosen so that the walk is extended by turning pixels in the given direction. However, such extension can only happen if adding random thickness E 2, 4) to both sides of this segment does not cause self intersections. These segments are added repeatedly until there is no space to add a new segment without violating the definition of a Jordan curve.
Digs Dataset (42 x 42 pixels): We generate rectangle of random size and then, we create "digs" of random thicknesses in the rectangle. The number "digs" is random number between to 10. The digs created sequentially and they are of random depth (between pixel to the length of the rectangle minus pixels). ). For each new "dig", we made sure to not cross previous digs by adjusting the depth of the "dig".
G HYPERPARAMETERS
In this Section we report all the tried hyperparameters for all architectures. In all cases, the convo- lutional layers zero-padding.
17

---

Under review as a conference paper at ICLR 2020
Examples of Jordan Curves of Each Dataset
D
A
D
0
A
500
A
T
24
E
D0g
P
Der
Figure FS: Datasets. Images of the curves used to train and test the DNNs. Each row correspond to different dataset.
Dilated Convolution DNN (Dilated): This network was introduced in Sec. 3.1
We the same
hyperparameters as in Yu & Koltun (016)) 3 x kernels, a number of kernels equal to 2 x {2, 4, 8}, where / is the number of layers and ranges between 8 11, with 2 (the first layer and the last two layers d = 1). The number of kernels in the layer that calculates the parity can be (5, 10, 20, 40, 80}.
Ray- intersntersnttonn network (Ray-int.): This is the architecture introduced in Sec. 3.1 which uses receptive field of N instead of the dilated convolutions. The rest of the hyperparameters are as in Dilated.
Convolutional DNN (CNN): To analyze the usefulness of the dilated convolutions, we use the Dilated architecture with all dilation factors d = 1. Also, we adding more layers than in Dilated, up to 25.
UNet: This is popular architecture with skip connections and de-convolutions. We use similar hyperparameters as Ronneherger al. (2015): starting with kernels x 3) at the first layer and doubling this number after each max-pooling; total of 1 to 3 max-pooling layers in all the network, that are placed after sequences of 1 or convolutional layers.
Convolutional LSTM (I-LSTM): This is the architecture with just one ConvLSTM, introduced in Sec. 3.2 The number of time steps fixed to 50. We initialize the hidden and cell states to 0 (inside) everywhere except the border of the image which is initialized to (outside).
2-layers Convolutional LSTM (2-LSTM): We stack one convolutional LSTM after another. The first LSTM has 64 kernels, and the hidden and cell states initialized as in the 1-LSTM.
2-layers Convolutional LSTM without initialization (2-LSTM w/o init.): this the same as the 2-LSTM architecture the hidden and cell states are initialized to (outside).
H ADDITIONAL EXPERIMENTS OF FEED-FORWARD NETWORKS
In Fig. we have observed that Dilated trained on both 24-Polar and Spiral datasets, obtains test accuracy of less than 95% these datasets while the accuracy in the training set very close to 100%. We added weight decay in all the layers in order to regularize the network. tried values between 10-5 to 1, scaling by a factor of 10. In all these experiments we have observed overfitting except for a weight decay of 1, in which the training never converged.
Also, note that the CNN does not have this overfitting problem. Yet. the number of layers needed 25, which is more than the double than for Dilated, which 9 layers. We added more layers to Dilated but the accuracy did not improve.
18

---

Under review as a conference paper at ICLR 2020
I
ADDITIONAL FIGURES AND VISUALIZATIONS
Train Acc. on Polar
Train Acc. on Polar
Generalization Acc. on Polar
1100
100
per Image acc. (99
100
per image acc.
Train Set
98
Diated
Ray-int.
Ray-int.
50
96
UNet
UNet
24STT
14
14STMM
14
19
24
9
14
19
24
9
14
19
24
Polar Dataset
Polar Dataset
Polar Test Set (c)
(a)
(b)
Figure 1.6: Training Accuracy in the Polar Dataset. Intra-dataset evaluation using (a) per pixel accuracy and (b) per image accuracy on the training set, which are very similar to the test accuracy reported in Fig. 30 and c. (c) Intra-dataset evaluation of Unet.
Layer 2
Layer 6 Unit 15
Unit 3
Unit 10
Unit 19
Unit 10
Unit 27
+
D
>>
A
E
A
g
Figure 1.7: Visualization of the Units Learnt by Dilation. Each block are the 9 images that produce the maximum activation of a units in convolutional across the test set. The gray dot indicates the location of the unit. Fig. [8 shows more examples.
Layer
Unit 0
Unit
Unit 12
Unit 24
Unit 26
Unit 28
#3
4
x
>>
03
?
A
3
Layer
Unit 0
Unit 3
Unit
Unit 7
Unit 10
Unit 14
+
x3
Layer
Unit 2
Unit 4
Unit 8
Unit 16
Unit 17
Unit 21
3
D
L
Figure 1.8: More examples of Visualization of the Units Learnt by Dilation.
19

---

Under review as a conference paper at ICLR 2020
Examples of Feature Maps of the Dilated Conv. DNN
Figure 199: Visualization of the Feature Maps of the DNV with Dilated Convolations. We display several feature maps at different layers (each row in each block is different layer). We can see that the first layers detect lower level features such as edges with specific orientations, while the later layers capture long-range dependencies of the curve relative to insideness.
1=0
[=4
t=8
t=12
t=16
t=20
t=0
1=4
t=8
t=12
t=16
t=20
0
5
5
5
t=4
t=8
t=12
t=16
t=
t=0
t=4
t=8
1=12
t=16
t=20
Figure 1.10: Visualization of Convolutional LSTM with the Mathematically Derived Parameters. We can see that only the border the image (outside) propagated, and not the curve, as in the learnt solution.
20

---

Under review as a conference paper at ICLR 2020
1=0
1=8
1=12
t=16
1=20
[=0
1=4
[=8
t=12
t=16
t=20
0
026
4
H2H
HPH
A
4
OX.0
ox.
A
O ex.1
O ex1
Figure 1.11 Activation Maps of the Learnt Representations by 2-LSTM. Each row corresponds to different layer and each colum to different time step.
Dilated
CNN
UNet
2-LSTM
Dilated
CNN
UNet
2-LSTM
X
-
A
Figure L.1: Qualitative Examples from the Digs dataset. Networks trained in 24-Polar and Spiral dataset fail to segment in the Digs dataset.
21

---

Under review as a conference paper at ICLR 2020
J NETWORKS PRE-TRAINED ON NATURAL IMAGES
We chose two state-of-the-art networks on Instance Segmentation, DEXTR (Maninis et al., 2018) and DeepLabv3+ (Chen al. 2018c), investigate their ability in solving the insideness problem.
DEXTR. Deep Exteme Cut (DEXTR) is a neural network used for interactive instance segmentation. We use the pre-trained model PASCAL VOC 2012 (Everingham al.) and show some of the qualitative results in Fig. J.13
DeepLabv3+. This architecture extends DeepLabv3 (Chen al. 2018b) by utilizing as an en- coder network and adding a decoder network to refine segmentation boundaries. The encoder em- ploys dilated convolution and Atrous Spatial Pyramid Pooling module for feature extraction. we use DeepLabv3+ with Xception backbone pretrained on PASCAL VOC 2012, and fine-tune its last layer with Polar and Spiral datasets for training. The ratio of input image spatial resolution to encoder output image is referred to as output stride and varies according to dilation rates. We use output strides of 8 and as suggested in the paper; loss weight (ax) 0.1, 0.2 and 0.4; and initial learning rates from 0.1 to 10 (dividing by 10). We train the network on Polar and Spiral datasets until there no improvement of the accuracy at the validations set, and we then reduce the learning rate by ratio of 10 and stop the next plateau of the validation set accuracy.
22

---

Under review as a conference paper at ICLR 2020
4
5
4
4
Figure J.13: Qualitative Results with DEXTR on the Polar Dataset. We use the publicly available pre-trained DEXTR model (Maninis al., 2018). DEXTR uses 4 points marked by the user (indi- cated with crosses). We report the best found points, two examples of them per image.
23

---

Under review as a conference paper at ICLR 2020
Polar
Spiral
Digs
Figure J.14: Results of DeepLabv3+ on Polar, Spiral and Digs Datasets. The network is fine-tuned on Polar and Spiral. The results show that the network predicts well most of the pixels except in the borders. For the cross- dataset evaluations in the Digs dataset, the network is not able generalize.
24


Reviews:
[{"review_id": "r1ldz9K69r", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the problem of modeling insideness using neural networks. To this end, the authors carefully designed both feedforward and recurrent neural networks, which are, in principle, able to learn the insideness in its global optima. For evaluation, these methods are trained to predict the insideness in synthetically generated Jordan curves and tested under various settings such as generalization to the different configuration of curves or even different types of curves. The experiment results showed that the tested models are able to learn insideness, but it is not generalizable due to the severe overfitting. Authors also demonstrated that injecting step-wise supervision in coloring routine in recurrent networks can help the model to learn generalizable insideness. \n\nThis paper presents an interesting problem of learning to predict insideness using neural networks, and experiments are well-executed. However, I believe that the paper requires more justifications and analyses to convince some claims and observations presented in the paper. More detailed comments are described below.\n\n1. Regarding the usefulness of learning insideness to improve segmentation\nThe authors motivated the importance of learning insideness in terms of improving segmentation (e.g., instance-wise segmentation). However, I believe that this claim is highly arguable and needs clear evidence to be convincing. Although I appreciate the experiments in the supplementary file showing that some off-the-shelf segmentation models fail to predict insideness, I believe that these two are very different tasks (one is filling the region inside the closed curve and the other is predicting the labels given the object texture and prior knowledge on shapes; please also note that segmentation masks also can be in very complex shapes, where the prior on insideness may not be helpful). It is still weak to support the claim that learning to predict insideness is useful to improve segmentation. \n\n2. More analyses for experiment results      \nIn the experiment, the authors concluded that both feedforward and recurrent neural networks are not generalized to predict insideness in fairly different types of curves. However, it is hard to find further insights in the experiments, such as what makes it hard to generalize this fairly simple task. Improving generalization using step-wise supervision in a recurrent neural network is interesting but not surprising since we simply force it to learn the procedure of predicting insideness using additional supervision. \n\nTo summarize, although the problem and some experiment results presented in the paper are interesting, I feel that the paper lacks justifications on the importance of the problem and insights/discussions of the results. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "HyeXzhdjYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission introduces a new concept, termed insideness, to study semantic segmentation in deep learning era. The authors raise many interesting questions, such as (1) Does deep neural networks (DNN) understand insideness? (2) What representations do DNNs use to address the long-range relationships of insideness? (3) How do architectural choices affect the learning of these representations? This work adopts two popular networks, dilated DNN and ConvLSTM, to implement solutions for insideness problem in isolation. The results can help future research in semantic segmentation for the models to generalize better. \n\nI give an initial rating of weak accept because I think (1) This paper is well written and well motivated. (2) The idea is novel, and the proposed \"insideness\" seems like a valid metric. This work is not like other segmentation publications that just propose a network and start training, but perform some deep analysis about the generalization capability of the existing network architectures. (3) The experiments are solid and thorough. Datasets are built appropriately for demonstration purposes. All the implementation details and results can be found in appendix. (4) The results are interesting and useful. It help other researchers to rethink the boundary problem by using the insideness concept. I think this work will have an impact in semantic segmentation field. \n\nI have one concern though. The authors mention that people will raise the question of whether these findings can be translated to improvements of segmentation methods for natural images. However, their experiments do not answer this question. Fine-tuning DEXTR and Deeplabv3+ on the synthetic datasets can only show the models' weakness, but can't show your findings will help generalize the model to natural images. Adding an experiment on widely adopted benchmark datasets, such as Cityscapes, VOC or ADE20K, will make the submission much stronger. \n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HkgS6FcY9H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper shows that deep-nets can actually learn to solve the problem of \"what is inside a curve\" by using a sort of progressive filling of the space outside the curve. The paper suceeds in explaining that and in pointing out the limitations if standard learning to address this problem.\n\nHowever, \n(1) the proposed demonstration is based in ideal (continuous, noiseless) curves. What would happen in actual (discontinuous, noisy) curves?. What implications does this has in the requirements of the network.\n(2) I think more connections to classical and current algorithms are required. For instance:\n(2.1) The proposed demonstration (and the arguments of Ullman) reminds me of classical watersheed algorithms [see 2.1]. What is the gain of using deep networks with regard to rather old techniques?. Advantages are not clear in the text.\n(2.2) What about connections to recent algorithms of automatic fill-in of images of contours based on conditional GANs [see 2.2]. It seems that these recent techniques already solved the \"insideness\" problem and even learnt how to fill the inside in sensible ways...\nThen, what is the gain of the proposed approach?. \n\nREFERENCES:\n\n[2.1] Fundamenta Informaticae 41 (2001) 187–228\nThe Watershed Transform:  Definitions, Algorithms and Parallelization Strategies\nJos B.T.M. Roerdink and Arnold Meijster\nhttp://www.cs.rug.nl/~roe/publications/parwshed.pdf\n\n[2.2] Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks\nJun-Yan Zhu, Taesung Park, Phillip Isola, Alexei A. Efros\nICCV 2017 https://arxiv.org/abs/1703.10593", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates a notion of recognizing insideness (i.e., whether a pixel is inside a closed curve/shape in the image) with deep networks. It's an interesting problem, and the authors provide analysis on the limitations of existing architectures (e.g., feedforward and recurrent networks) and present a trick to handle the long-range relationships. While the topic is interesting, the constructed datasets are quite artificial and it's unclear how this study can lead to practically useful results (e.g., improvement in semantic segmentation, etc.). 
Decision: Reject