\section{Introduction}
\vspace{-1mm}
In this work, we aim to develop an automatic Language-Based Image Editing (LBIE) system. Given a source image, which can be a sketch, a grayscale image or a natural image, the system will automatically generate a target image by editing the source image following natural language instructions provided by users. Such a system has a wide range of applications from Computer-Aided Design (CAD) to Virtual Reality (VR). As illustrated in Figure \ref{fig:design}, a fashion designer presents a sketch of a pair of new shoes (i.e., the source image) to a customer, who can provide modifications on the style and color in verbal description, which can then be taken by the LBIE system to change the original design. The final output (i.e., the target image) is the revised and enriched design that meets the customer’s requirement. Figure \ref{fig:VR} showcases the use of LBIE for VR. While most VR systems still use button-controlled or touchscreen interface, LBIE provides a natural user interface for future VR systems, where users can easily modify the virtual environment via natural language instructions.

\begin{figure}[t]
\centering
\includegraphics[width=0.43\linewidth]{fig/design_example.png}
\caption{In an interactive design interface, a sketch of shoes is presented to a customer, who then gives a verbal instruction on how to modify the design: ``\textit{The insole of the shoes should be brown. The vamp and the heel should be purple and shining}''. The system colorizes the sketch following the customer's instruction. (images from \cite{isola2016image}).}
\label{fig:design}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=0.43\linewidth]{fig/vr_example2.png}
\includegraphics[width=0.43\linewidth]{fig/vr_example.png}
\caption{The image on the left is an initial virtual environment. The user provides a textual description: ``The afternoon light flooded the little room from the window, shining the ground in front of a brown bookshelf made of wood. Besides the bookshelf lies a sofa with light-colored cushions. There is a blue carpet in front of the sofa, and a clock with dark contours above it...''. The system modifies the virtual environment into the target image on the right.}
\label{fig:VR}
\end{figure}
\begin{figure}[t]
\centering
\includegraphics[width=0.33\linewidth, height = 1.8cm]{fig/00296_orginal_sketch.jpg}%
\includegraphics[width=0.33\linewidth, height = 1.8cm]{fig/00296_bw.jpg}
\includegraphics[width=0.33\linewidth, height = 1.8cm]{fig/image_00296.jpg}
\caption{Left: sketch image. Middle: grayscale image. Right: color image (from \cite{Nilsback08}). A language-based image editing system will take either of the first two images as the input, and generate the third color image following a natural language expression: \textit{``The flower has red petals with yellow stigmas in the middle''},.}
\label{fig:rendering}
\vspace{-4mm}
\end{figure}
LBIE covers a broad range of tasks in image generation: shape, color, size, texture, position, etc. This paper focuses on two basic sub-tasks: language-based segmentation and colorization for shapes and colors. As shown in Figure \ref{fig:rendering}, given a grayscale image and the expression \textit{``The flower has red petals with yellow stigmas in the middle''}, the segmentation model will identify regions of the image as ``\textit{petals}'', ``\textit{stigmas}'', and the colorization model will paint each pixel with the suggested color.
In this intertwined task of segmentation and colorization, the distribution of target images can be multi-modal in the sense that each pixel will have a definitive ground truth on segmentation, but not necessarily on color. For example, the pixels on petals in Figure \ref{fig:rendering} should be red based on the textual description, but the specific numeric values of the red color in the RGB space is not uniquely specified. The system is required to colorize the petals based on real-world knowledge. Another uncertainty lies in the fact that the input description might not cover every detail of the image. The regions that are not described, such as the leaves in the given example, need to be rendered based on common sense knowledge. In summary, we aim to generate images that not only are consistent with the natural language expressions, but also align with common sense.

Language-based image segmentation has been studied previously in \cite{hu2016segmentation}. However, our task is far more challenging because the textual description often contains multiple sentences (as in Figure \ref{fig:VR}), while in \cite{hu2016segmentation} most of the expressions are simple phrases. To the best of our knowledge, language-based colorization has not been studied systematically before. In most previous work, images are generated either solely based on natural language expressions \cite{reed2016generative},\cite{zhang2016stackgan} or based on another image \cite{isola2016image},\cite{cheng2015deep},\cite{zhang2016colorful}. Instead, we want to generate a target image based on both the natural language expression and the source image. Related tasks will be discussed in detail in Section \ref{sec:related}.

A unique challenge in language-based image editing is the complexity of natural language expressions and their correlation with the source images. As shown in Figure \ref{fig:VR}, the description usually consists of multiple sentences, each referring to multiple objects in the source image. When human edits the source image based on a textual description, we often keep in mind which sentences are related to which region/object in the image, and go back to the description multiple times while editing that region. This behavior of ``going back'' often varies from region to region, depending on the complexity of the description for that region. An investigation of this problem is carried out on CoSaL, which is a synthetic dataset described in Section \ref{sec:experiment}.

Our goal is to design a generic framework for the two sub-tasks in language-based image editing. A diagram of our model is shown in Figure \ref{fig:model}. Inspired by the observation aforementioned, we introduce a recurrent attentive fusion module in our framework. The fusion module takes as input the image features that encode the source image via a convolutional neural network, and the textual features that encode the natural language expression via an LSTM, and outputs the fused features to be upsampled by a deconvolutional network into the target image. In the fusion module, recurrent attentive models are employed to extract distinct textual features based on the spatial features from different regions of an image. A termination gate is introduced for each region to control the number of steps it interacts with the textual features. The Gumbel-Softmax reparametrization trick \cite{jang2016categorical} is used for end-to-end training of the entire network. Details of the models and the training process are described in Section \ref{sec:model}.

\begin{figure*}[t]
\centering
\includegraphics[width=0.8\textwidth,height=7cm]{fig/fig-new-model.pdf}
\caption{A high-level diagram of our model, composed of a convolutional image encoder, an LSTM text encoder, a fusion module, a deconvolutional upsampling layer, with an optional convolutional discriminator.}
\label{fig:model}
\vspace{-2mm}
\end{figure*}

Our contributions are summarized as follows:
\begin{itemize}
	\setlength\itemsep{0.001em}
	\item We define a new task of language-based image editing (LBIE).
	\item We present a generic modeling framework based on recurrent attentive models for two sub-tasks of LBIE: language-based image segmentation and colorization.
	\item We introduce a synthetic dataset CoSaL designed specifically for the LBIE task.
	\item We achieve new state-of-the-art performance on language-based image segmentation on the ReferIt dataset.
	\item We present the first language-based colorization result on the Oxford-102 Flowers dataset, with human evaluations validating the performance of our model
	\vspace{-2mm}
\end{itemize}

\vspace{-2mm}
\section{Related Work} \label{sec:related}
\vspace{-1mm}
While the task of language-based image editing has not been studied, the community has taken significant steps in several related areas, including Language Based object detection and Segmentation (LBS) \cite{hu2016segmentation},\cite{hu2016natural}, Image-to-Image Translation (IIT) \cite{isola2016image}, Generating Images from Text (GIT) \cite{reed2016learning}, \cite{zhang2016stackgan}, Image Captioning (IC) \cite{karpathy2015deep}, \cite{vinyals2015show}, \cite{xu2015show}, Visual Question Answering (VQA) \cite{antol2015vqa}, \cite{yang2016stacked},  Machine Reading Comprehension (MRC) \cite{hermann2015teaching}, etc. We summarize the types of inputs and outputs for these related tasks in Table \ref{table:tasks}.

\begin{table}[h!]
\centering
\begin{tabular}{||c| c c| c c||}
\hline
& \multicolumn{2}{c}{Inputs}&\multicolumn{2}{c||}{Outputs}  \\
 \hline
 & Text &Image&Text&Image \\
 \hline
 MRC &YES&NO&YES&NO \\
 VQA & YES &YES&YES&NO \\
 IIT & NO &YES&NO&YES \\
 IC & NO &YES&YES&NO \\
 GIT& YES &NO&NO&YES \\
 LBS & YES &YES&NO&YES \\
 \textbf{LBIE} & \textbf{YES} &\textbf{YES}&\textbf{NO}&\textbf{YES} \\
 \hline
\end{tabular}
\caption{The types of inputs and outputs for related tasks}
\label{table:tasks}
\end{table}
\vspace{-2mm}
\subsection*{Recurrent attentive models}
\vspace{-1mm}
Recurrent attentive models have been applied to visual question answering (VQA)
to fuse language and image features \cite{yang2016stacked}. The stacked attention network proposed in \cite{yang2016stacked} identifies the image regions that are relevant to the question via multiple attention layers, which can progressively filter out noises and pinpoint the regions relevant to the answer. In image generation, a sequential variational auto-encoder framework, such as DRAW\cite{gregor2015draw}, has shown substantial improvement over standard variational auto-encoders (VAE) \cite{kingma2013auto}. Similar ideas have also been explored for machine reading comprehension, where models can take multiple iterations to infer an answer based on the given query and document \cite{dhingra2016gated}, \cite{weston2015towards}, \cite{wang2016machine}, \cite{xiong2016dynamic}, \cite{liu2017stochastic}. In \cite{shen2017reasonet} and \cite{shen2016implicit}, a novel neural network architecture called ReasoNet is proposed for reading comprehension. ReasoNet performs multi-step inference where the number of steps is determined by a termination gate according to the difficulty of the problem. ReasoNet is trained using policy gradient methods.

\vspace{-2mm}
\subsection*{Segmentation from language expressions}
\vspace{-1mm}
The task of language-based image segmentation is first proposed in \cite{hu2016segmentation}. Given an image and a natural language description, the system will identify the regions of the image that correspond to the visual entities described in the text. The authors in \cite{hu2016segmentation} proposed an end-to-end approach that uses three neural networks: a convolutional network to encode source images, an LSTM network to encode natural language descriptions, and a fully convolutional classification and upsampling network for pixel-wise segmentation.

One of the key differences between their approach and ours is the way of integrating image and text features. In \cite{hu2016segmentation}, for each region in the image, the extracted spatial features are concatenated with the same textual features.
Inspired by the alignment model of \cite{karpathy2015deep}, in our approach, each spatial feature is aligned with different textual features based on attention models. Our approach yields superior segmentation results than that of \cite{hu2016segmentation} on a benchmark dataset.
\vspace{-2mm}
\subsection*{Conditional GANs in image generation}
\vspace{-1mm}
Generative adversarial networks (GANs) \cite{goodfellow2014generative} have been widely used for image generation. Conditional GANs \cite{mirza2014conditional} are often employed when there are constraints that a generated image needs to satisfy. For example, deep convolutional conditional GANs \cite{radford2015unsupervised} have been used to synthesize images based on textual descriptions \cite{reed2016generative}
\cite{zhang2016stackgan}. \cite{isola2016image} proposed the use of conditional GANs for image-to-image translation.
Different from these tasks, LBIE takes both image and text as input, presenting an additional challenge of fusing the features of the source image and the textual description.

\vspace{-2mm}
\section{The Framework}\label{sec:model}
\paragraph{Overview} The proposed modeling framework, as shown in \ref{fig:model}, is based on neural networks, and is generic to both the language-based image segmentation and colorization tasks. The framework is composed of a convolutional image encoder, an LSTM text encoder, a fusion network that generates a fusion feature map by integrating image and text features, a deconvolutional network that generates pixel-wise outputs (the target image) by upsampling the fusion feature map, and an optional convolutional discriminator used for training colorization models.

\vspace{-5mm}
\paragraph{Image encoder} The image encoder is a multi-layer convolutional neural network (CNN). Given a source image of size $H\times W$, the CNN encoder produces a $M \times N$
spatial feature map, with each position on the feature map containing a $D$-dimensional feature vector ($D$ channels), $V=\{v_{i}:i=1,\dots,M\times N\},v_i\in \mathbb R^{D}.$
\vspace{-5mm}
\paragraph{Language encoder}  The language encoder is a recurrent Long Short-Term Memory (LSTM) network. Given a natural language expression of length $L$, we first embed each word into a vector through a word embedding matrix, then use LSTM to produce for each word a contextual vector that encodes its contextual information such as word order and word-word dependencies. The resulting language feature map is $U=\{u_{i}:i=1,\dots,L\}, u_{i} \in\mathbb R^{K}$.

\vspace{-5mm}
\paragraph{Recurrent attentive fusion module} The fusion network fuses text information in $U$ into the $M\times N$ image feature map $V$, and outputs an $M\times N$ fusion feature map, with each position (image region) containing an editing feature vector, $O=\{o_i:i=1,\dots,M\times N\}, o_i \in\mathbb  R^{D}$.

The fusion network is devised to mimic the human image editing process. For each region in the source image $v_{i}$, the fusion network reads the language feature map $U$ repeatedly with attention on different parts each time until enough editing information is collected to generate the target image region. The number of steps varies from region to region.

\vspace{-5mm}
\subparagraph{Internal state} The internal state at time step $t$ is denoted as $S^t=\{s_{i}^t,i=1,\dots,M\times N\}$, which is a spatial feature map, with each poition (image region) containing a vector representation of the editing information state. The initial state is the spatial feature map from the source image, $S^0=V$. The sequence of internal states is modeled by Convolutional Gated Recurrent Units (C-GRUs) which will be described below.
\vspace{-5mm}
\subparagraph{Attention} The attention at time step $t$ is denoted as $\hat{U}^t=\{\hat{u}_{i}^t,i=1,\dots,M\times N\}$, which is a spatial feature map generated based on the current internal state $S^t$ and the language feature map $U$:
\vspace{-2mm}
\begin{equation*}
\hat{U}^t = \textbf{Attention}(U, S^t; \theta_a),
\vspace{-2mm}
\end{equation*}
where \textbf{Attention}(.) is implemented as follows:
\vspace{-2mm}
\begin{align*}
\beta_{ij} &\propto \exp\{{s_{i}^t}^TWu_j\},\\
\hat u_{i}^t &= \sum_{j=1}^L\beta_{ij}u_j.\\
\vspace{-2mm}
\end{align*}

\vspace{-5mm}
\subparagraph{C-GRUs} C-GRUs update the current internal state $S^t$ by infusing the attention feature map $\hat{U}^t$:
\vspace{-2mm}
\begin{equation*}
S^{t+1}=\textbf{C-GRUs}(S^t, \hat{U}^t; \theta_c).
\vspace{-2mm}
\end{equation*}
The \textbf{C-GRUs}(.) is implemented as follows:
\vspace{-2mm}
\begin{align*}
\mathbf z&= \sigma (W_1\otimes S^t + W_2\otimes\hat U^t+b_1),\\
\mathbf r&= \sigma (W_3\otimes S^t + W_4\otimes\hat U^t+b_2),\\
\mathbf c&=\text{ReLU}(W_5\otimes(\mathbf r\odot S^t)+W_6\otimes\hat U^t + b),\\
\hat{O}^t&=\mathbf{h} = (1 - \mathbf z)\odot S^t + \mathbf z\odot \mathbf c,\\
S^{t+1}&= W_7 \otimes \mathbf{h},
\vspace{-2mm}
\end{align*}
where $\odot$ is the elementwise-product, and $\otimes$ is the convolutional operator. Note that $\hat{O}^t$ is the intermediate output of the fusion feature map at time step $t$.

\vspace{-5mm}
\subparagraph{Termination gates} There are $M\times N$ termination gates, each for one image region $v_i$ in $V$. Each termination gate generates a binary random variable according to the current internal state of its image region: $\tau_{i}^t \sim p(\cdot │ f_{tg} (s_{i}^t;\theta_{tg}))$. If $\tau_{i}^t=1$, the fusion process for the image region $v_i$ stops at $t$, and the editing feature vector for this image region is set as $o_{i}=\hat{o}_i^t$. When all terminate gates are true, the fusion process for the entire image is completed, and the fustion network outputs the fusion feature map $O$. \newline
We define $\pmb \zeta = (\zeta_1,\zeta_2,\dots,\zeta_{M\times N})$, where $\zeta_i = (\tau_i^1,\tau_i^2,\dots,\tau_i^T)$, a categorical distribution with $p(\zeta_i=e_t)=\beta_i^t$, where
\vspace{-2mm}
\begin{equation*}
\beta_i^t = f_{tg}(s_i^t;\theta_{tg})\prod_{k<t}(1-f_{tg}(s_i^k;\theta_{tg})).
\vspace{-2mm}
\end{equation*}
the probability of stopping the fusion process at the $i$-th image region of the feature map at time $t$.
\vspace{-5mm}
\subparagraph{Inference} Algorithm \ref{alg:inference} describes the stochastic inference process of the fusion network. The state sequence $S^{(1:T)}$ is hidden and dynamic, chained through attention and C-GRU in a recurrent fashion. The fusion network outputs for each image region $v_i$ an editing feature vector $o_{i}$ at the $t_i$-th step, where $t_i$ is controlled by the $i$th termination gate, which varies from region to region.

  \begin{algorithm}
       \caption{Stochastic Inference of the Fusion Network}
       \label{alg:inference}
       \begin{algorithmic}
       \Require $V\in\mathbb R^{D\times (M\times N)}$: Spatial feature map of image.
       \Require $U\in\mathbb R^{K\times L}$: Language feature map of expression.
       \Ensure Fusion feature map $O\in\mathbb R^{D\times (M\times N)}$.
       \Function {Fusion}{$V,U$}
       	  \State Initialize $S^0=V$.
           \ForAll  {$t=0$ to $t_{max}-1$}
           	\State $\hat U^t = \textbf{Attention}(U,S^t;\theta_a) $
 			\State $S^{t+1},\hat{O}^{t} =\textbf{C-GRUs}(S^t,\hat U^t;\theta_c) $
           \State Sample $\pmb{\tau}^{t+1}\sim p(\cdot|f_{tg} (S^{t+1};\theta_{tg}))$
           \If {$\tau_{i}^{t+1}=1$ and $\tau_{i}^s=0$ for $s\leq t$}
             \State Set $O_{i}=\hat O_{i}^{t+1}$.
           \EndIf
           \EndFor

           \ForAll {$i=1$ to $M\times N$}
           	\If {$\tau_{i}=0$}
             	\State Set $o_{i}=\hat{o}_{i}^{t_{max}-1} $
             \EndIf
 		  \EndFor
 	  \EndFunction
       \end{algorithmic}
 \end{algorithm}
\vspace{-5mm}
\paragraph{Image decoder} The image decoder is a multi-layer deconvolutional network. It takes as input the $M\times N$ fusion feature map $O$ produced by the fusion module, and unsamples from $O$ to produce a $H\times W\times D_e$ editing map $E$ of the same size as the target image, where $D_e$ is the number of classes in segmentation and $2$ ($ab$ channels) in colorization.
\vspace{-5mm}
\paragraph{Discriminator} The discriminator $D_\phi(E)$ takes in a generated image and its corresponding language description and outputs the probability of the image being realistic. The discriminator uses a convolutional neural network to extract features from the image, as in \cite{reed2016generative}, and uses an LSTM to encode language. The language features are extracted using the attention mechanism and aligned to features extracted from each region of the image respectively. Parameters of the LSTM and the attention map are not shared with those of the previous language encoder.
\vspace{-5mm}
\paragraph{Loss and training}
Denote the loss as $L(\theta)=\mathbb E_{\pmb \zeta}[l(E(\pmb \zeta,\theta),Y)]$, where the expectation is taken over the categorical variables $\pmb \zeta$ generated by termination gates, and $l_\theta(\pmb \zeta)=l(E(\pmb \zeta,\theta),Y)$ is the loss of output at $\pmb \zeta$, and $Y$ is the target image (i.e., the class labels in segmentation or the $ab$ channels in colorization). Denote the probability mass function of $\pmb \zeta$ by $p_\theta(\pmb \zeta)$. Because the sample space is of exponential size $T^{M\times N}$, it is intractable to sum over the entire sample space.  A naive approach to approximation is to subsample the loss and update parameters via the gradient of Monte Carlo estimate of loss:
\vspace{-2mm}
\begin{align*}
\nabla_\theta L(\theta) &= \nabla_\theta\mathbb E_{\pmb \zeta}[l_\theta(\pmb \zeta)]\\
&= \nabla_\theta\mathbb E_{\pmb \zeta}[l_\theta(\pmb \zeta)]\\
&=\sum_{\pmb \zeta}p_\theta (\pmb \zeta) \big ( l_\theta(\pmb \zeta)\nabla_\theta \log p_\theta(\pmb \zeta)\big ) + \nabla_\theta l_\theta(\pmb \zeta)\big )\\
&\approx \frac{1}{|\mathbf S|}\sum_{\pmb \zeta\in\mathbf S} l_\theta(\pmb \zeta)\nabla_\theta \log p_\theta(\pmb \zeta)+\nabla_\theta l_\theta(\pmb \zeta),
\vspace{-2mm}
\end{align*}
where $\mathbf S$ is a subset of $\pmb \zeta$ sampled from the distributon $p_\theta(\pmb \zeta)$. The above update is called a REINFORCE-type algorithm \cite{williams1992simple}. In experiments, we found that the above Monte Carlo estimate suffers from high variance. To resolve this issue, we employ the Gumbel-Softmax reparameterization trick \cite{jang2016categorical}, which replaces every $\zeta_i\in\{0,1\}^T$ sampled from $\text{Cat}(\beta_1,\beta_2,\dots,\beta_T)$ by another random variable $z_i$ generated from Gumbel-Softmax distribution:
\vspace{-2mm}
\begin{equation*}
z_i^t = \frac{\exp((\log\beta_i^t+\varepsilon_i^t)/\lambda)}{\sum_{k=1}^T\exp((\log\beta_i^t+\varepsilon_i^t)/\lambda)},
\vspace{-2mm}
\end{equation*}
where $\lambda$ is a temperature annealed via a fixed schedule and the auxiliary random variables $\varepsilon_i^1,\dots,\varepsilon_i^T$ are i.i.d. samples drawn from Gumbel$(0,1)$ independent of the parameters $\beta_i$:
\vspace{-2mm}
\begin{equation*}
\varepsilon_i^t = -\log(-\log u_i^t), u_i^t\sim \text{Unif}(0,1).
\vspace{-2mm}
\end{equation*}
Define $\mathbf z(\pmb\varepsilon,\theta) = (z_1,z_2,\dots,z_{MN})$. The loss can be rewritten as $L(\theta) = \mathbb E_{\pmb\varepsilon}[l_\theta(\pmb z(\pmb\varepsilon,\theta) )]$, and the update is approximated by taking the gradient of Monte Carlo estimates of the loss obtained from sampling $\pmb\varepsilon$.

We use two different losses for segmentation and colorization, respectively.
\vspace{-5mm}
\subparagraph{Segmentation} In segmentation, we assume there is a unique answer for each pixel on whether or not it is being referred in the stage of segmentation. The response map $E$ is of size $H\times W\times D_e$, which produces a log probability for each class for each pixel. We use a pixel-wise softmax cross-entropy loss during training:
\vspace{-2mm}
\begin{equation*}
l(E,Y) = \text{Cross-Entropy}(\text{Softmax}(E), Y).
\vspace{-2mm}
\end{equation*}
\vspace{-5mm}
\subparagraph{Colorization} In colorization, the high-level goal is to generate realistic images under the constraint of natural language expressions and input scene representations, we introduce a mixture of GAN loss and $L1$ loss for optimization as in \cite{isola2016image}. A discriminator $D_\phi$ parametrized by $\phi$ is introduced for constructing the GAN loss.

The response map $E$ is the predicted $ab$ color channels. It is combined with the grayscale source image to produce a generated color image $E'$. The generator loss is a GAN loss taking $E'$ as input, and $L1$ loss between the $ab$ channels of the target image $Y$ and the response map $E$:
\vspace{-2mm}
\begin{equation*}
l(E,Y) = \log (1-D_\phi(E)) + \gamma \|E-Y\|_1 \text{ } (\gamma=0.01).
\vspace{-2mm}
\end{equation*}

The discriminator $D_\phi$ is trained by first generating a sample $E$ via Algorithm \ref{alg:inference}, combined with the grayscale source image to produce $E'$, and optimize the following loss over $\phi$:
\vspace{-2mm}
\begin{equation*}
\log (D_\phi(E')) + \log (1-D_\phi(Y)).
\vspace{-2mm}
\end{equation*}

The generator loss and the discriminator loss are optimized alternatively in the training stage.

\vspace{-2mm}
\section{Experiments}\label{sec:experiment}
We conducted three experiments to validate the performance of the proposed framework. A new synthetic dataset CoSaL (Colorizing Shapes with Artificial Language) was introduced to test the capability of understanding multi-sentence descriptions and associating the inferred textual features with visual features. Our framework also yielded state-of-the-art performance on the benchmark dataset ReferIt \cite{KazemzadehOrdonezMattenBergEMNLP14} for image segmentation. A third experiment was carried out on the Oxford-102 Flowers dataset \cite{Nilsback08}, for the language-based colorization task. All experiments were coded in TensorFlow. Codes for reproducing the key results are available online\footnote{\url{https://github.com/Jianbo-Lab/LBIE}}.
\subsection{Experiments on CoSaL}
\vspace{-2mm}
\paragraph{Dataset}
Each image in the CoSaL dataset consists of nine shapes, paired with a textual description of the image. The task is defined as: given a black-white image and its corresponding description, colorize the nine shapes following the textual description. Figure \ref{fig:cosal2} shows an example. It requires sophisticated coreference resolution, multi-step inference and logical reasoning to accomplish the task.

The dataset was created as follows: first, we divide a white-background image into $3\times 3$ regions. Each region contains a shape randomly sampled from a set of $S$ shapes (e.g., squares, fat rectangles, tall rectangles, circles, fat ellipses, tall ellipses, diamonds, etc.)  Each shape is then filled with one of $C$ color choices, chosen at random. The position and the size of each shape are generated by uniform random variables. As illustrated in Figure \ref{fig:cosal2}, the difficulty of this task increases with the number of color choices. In our experiments, we specify $C=3$.

The descriptive sentences for each image can be divided into two categories: direct descriptions and relational descriptions. The former prescribes the color of a certain shape (e.g., \textit{Diamond is red}), and the latter depicts one shape conditional of another (e.g., \textit{The shape left to Diamond is blue}). To understand direct descriptions, the model needs to associate a specified shape with its textual features. Relational description adds another degree of difficulty, which requires advanced inference capability of relational/multi-step reasoning. The ratio of direct descriptions to relational descriptions varies among different images, and all the colors and shapes in each image are uniquely determined by the description. In our experiment, we randomly generated $50,000$ images with corresponding descriptions for training purpose, and $10,000$ images with descriptions for testing.
\vspace{-2mm}
\begin{figure}[H]
\centering
\includegraphics[width=0.57\linewidth]{fig/attented_language_expression.png}%
\includegraphics[width=0.42\linewidth]{fig/truth.png}
\caption{Right: ground truth image. Left: illustration of which sentences are attended to at each time step. Red, yellow and green represent the first, second and third time step, respectively.}
\vspace{-3mm}
\label{fig:cosal2}
\end{figure}
\begin{table}[H]
\centering
\begin{tabular}{||c c c c c||}
\hline
&&  \multicolumn{3}{c||}{Number of direct descriptions}  \\
 \hline

 $T$ & Attention &4&6&8  \\ [0.5ex]
 \hline\hline
 1 & No &0.2107&0.2499&0.3186 \\
 \hline
 1 & Yes &0.4030&0.5220&\textbf{0.7097} \\
 \hline
 4 & Yes & \textbf{0.5033}&\textbf{0.5313}&0.7017 \\
 \hline
\end{tabular}
\caption{The average IoU of two models, without attention at $T=1$ and with attention at $T=1,4$. Performance varies among datasets with different ratios of direct to relational descriptions.}
\vspace{-3mm}
\label{table:cosal}
\end{table}

\begin{table*}[h]
\centering
\begin{tabular}{||c c c c c c c||}
 \hline
 Model &  Precision@0.5 & Precision@0.6& Precision@0.7& Precision@0.8& Precision@0.9 &IoU   \\ [0.5ex]
 \hline\hline
 SCRC bbox \cite{hu2016natural} & 9.73\% & 4.43\% & 1.51\% & 0.27\% & 0.03\% & 21.72\% \\
 GroundeR bbox \cite{donahue2015long} & 11.08\% &6.20\% &2.74\% &0.78\% &0.20\% &20.50\%
 \\
 Hu, etc.\cite{hu2016segmentation} & \textbf{34.02}\% & 26.71\% & \textbf{19.32}\% & 11.63\% & 3.92\% & 48.03\% \\
 Our model & 32.53\% & \textbf{27.9}\% & 18.76\% & \textbf{12.37}\% & \textbf{4.37}\% & \textbf{50.09}\%   \\
 \hline
\end{tabular}
\caption{The results of previous models and our model on the ReferIt dataset.}
\vspace{-3mm}
\label{table:referit1}
\end{table*}

\vspace{-5mm}
\paragraph{Metric} For this task, we use \textit{average IoU over nine shapes and the background} as the evaluation metric. Specifically, for each region, we compute the intersection-over-union (IoU), which is the ratio of the total intersection area to the total union area of predicted colors and ground truth colors. We also compute the IoU for the background (white) of each image. The IoU for $10$ classes ($9$ shapes $+$ $1$ background) are computed over the entire test set and then averaged.
\vspace{-5mm}
\paragraph{Model Implementation} A six-layer convolutional network is implemented as the image feature extractor. Each layer has a $3\times 3$ kernel with stride $1$ and output dimension $4,4,8,8,16,16$. ReLU is used for nonlinearity after each layer, and a max-pooling layer with a kernel of size 2 is inserted after every two layers. Each sentence in the textual description is encoded with bidirectional LSTMs that share parameters. Another LSTM with attention is put on top of the encoded sentences. The LSTMs have $16$ units. In the fusion network, the attention model has $16$ units, the GRU cells use $16$ units, and the termination gate uses a linear map on top of the hidden state of each GRU cell. Two convolutional layers of kernel size $1\times 1$ with the output dimension of $16,7$ are put on top of the fused features as a classifier. Then an upsampling layer is implemented on top of it, with a single-layer deconvolutional network of kernel size $16$, stride $8$ to upsample the classifier to the original resolution. The upsampling layer is initialized with bilinear transforms. The maximum of termination steps $T$ vary from $1$ to $4$. When $T=1$, the model is reduced to simply concatenating features extracted from the convolutional network with the last vector from LSTM.
\vspace{-5mm}
\paragraph{Results}
Results in Table \ref{table:cosal} show that the model with attention and $T=4$ achieves a better performance when there are more relational descriptions in the dataset. When there are more direct descriptions, the two models achieve similar performance.
This demonstrates the framework's capability of interpreting multiple-sentence descriptions and associating them with their source image.

Figure \ref{fig:cosal2} illustrates how the model with $T=3$ interprets the nine sentences during each inference step. In each step, we take the sentence with the largest attention score as the one being attended to. Sentences in red are attended to in the first step. Those in yellow and green are attended to in the next two consecutive steps. We observe that the model tends to first extract information from direct descriptions, and then extract information from relational descriptions via reasoning.

\subsection{Experiments on ReferIt}
\paragraph{Dataset} The ReferIt dataset is composed of $19,894$ photographs of real world scenes, along with $130,525$ natural language descriptions on $96,654$ distinct objects in those photographs \cite{KazemzadehOrdonezMattenBergEMNLP14}. The dataset contains $238$ different object categories, including animals, people, buildings, objects and background elements (e.g., grass, sky). Both training and development datasets include $10,000$ images.
\vspace{-5mm}
\paragraph{Metric} Following \cite{hu2016segmentation}, we use two metrics for evaluation: 1) \textit{overall intersection-over-union (overall IoU)} of the predicted and ground truth of each region, averaged over the entire test set; 2) \textit{precision@threshold}, the percentage of test data whose (per image) IoU between prediction and ground truth is above the threshold.
Thresholds are set to $0.5,0.6,0.7,0.8,0.9$.
\vspace{-5mm}
\paragraph{Model Implementation}
A VGG-16 model \cite{simonyan2014very} is used as the image encoder for images of size $512\times 512$. Textual descriptions are encoded with an LSTM of $1,024$ units. In the fusion network, the attention model uses $512$ units and the GRU cells $1,024$ units, on top of which is a classifier and an upsampling layer similar to the implementation in Section 4.1.
The maximum number of inference steps is $3$. ReLU is used on top of each convolutional layer. $L2$-normalization is applied to the parameters of the network.
\vspace{-5mm}
\paragraph{Results}

Table \ref{table:referit1} shows the experimental results of our model and the previous methods on the ReferIt dataset. We see that our framework yields a better IoU and precision than \cite{hu2016segmentation}. We attribute the superior performance to the unique attention mechanism used by our fusion network. It efficiently associates individual descriptive sentences with different regions of the source image. There is not much discrepancy between the two models with $T=1$ and $T=3$, probably due to the fact that most textual descriptions in this dataset are simple.

\subsection{Experiments on Oxford-102 Flower Dataset}
\begin{figure*}[h!]
\centering
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/1_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/5_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/7_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/40_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/75_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/109_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/154_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/213_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/269_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/358_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/498_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/613_targets.jpg} \\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/1_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/5_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/7_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/40_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/75_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/109_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/154_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/213_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/269_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/358_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/498_notext.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/613_notext.jpg}\\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/1_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/5_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/7_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/40_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/75_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/109_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/154_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/213_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/269_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/358_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/498_text.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig6/613_text.jpg}
\caption{First row: original images. Second row: results from the image-to-image translation model in \cite{isola2016image}, without text input. Third row: results from our model, taking textual descriptions into account. The textual descriptions and more examples can be found in Appendix.}
\label{fig:flower1}
\end{figure*}

\begin{figure*}[h!]
\centering
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/0_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/1_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/2_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/3_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/4_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/5_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/6_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/7_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/8_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/9_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/10_targets.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/11_targets.jpg} \\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_0_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_1_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_2_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_3_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_4_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_5_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_6_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_7_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_8_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_9_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_10_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/white_11_outputs.jpg} \\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_0_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_1_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_2_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_3_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_4_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_5_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_6_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_7_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_8_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_9_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_10_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/red_11_outputs.jpg} \\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_0_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_1_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_2_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_3_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_4_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_5_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_6_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_7_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_8_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_9_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_10_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/orange_11_outputs.jpg} \\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_0_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_1_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_2_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_3_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_4_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_5_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_6_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_7_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_8_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_9_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_10_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/yellow_11_outputs.jpg} \\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_0_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_1_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_2_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_3_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_4_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_5_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_6_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_7_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_8_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_9_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_10_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/blue_11_outputs.jpg} \\
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_0_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_1_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_2_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_3_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_4_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_5_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_6_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_7_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_8_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_9_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_10_outputs.jpg}
\includegraphics[width=1.3cm, height=1.3cm]{fig/fig7/purple_11_outputs.jpg}
\caption{First row: original images. Remaining rows: results generated from our framework with arbitrary text input: \textit{``The flower is white/red/orange/yellow/blue/purple in color''}. }
\label{fig:flower2}
\end{figure*}
\paragraph{Dataset}
The Oxford-102 Flowers dataset \cite{Nilsback08} contains $8,189$ images from $102$ flower categories. Each image has five textual descriptions \cite{reed2016generative}. Following \cite{reed2016generative}, \cite{reed2016learning} and \cite{akata2015evaluation}, we split the dataset into 82 classes for training and 20 classes for testing. The task is defined as follows: Given a grayscale image of a flower and a description of the shapes and colors of the flower, colorize the image according to the description.

\vspace{-2mm}
\paragraph{Model Implementation}
A 15-layer convolutional network similar to \cite{zhang2016colorful} is used for encoding $256\times 256$ images. Textual descriptions are encoded with an bidirectional LSTM of $512$ units. In the fusion network, the attention model uses $128$ units and the GRU cells $128$ units. The image encoder
is composed of $2$ deconvolutional layers, each followed by $2$ convolutional layers, to upsample the fusion feature map to the target image space of $256\times 256\times 2$. The maximum length of the spatial RNN is $1$. The discriminator is composed of 5 layers of convolutional networks of stride $2$, with the output dimension $256,128,64,32,31$. The discriminator score is the average of the final output. ReLU is used for nonlinearity following each convolutional layer, except for the last one which uses the sigmoid function.
\vspace{-2mm}
\paragraph{Setup} Due to the lack of available models for the task, we compare our framework with a previous model developed for image-to-image translation as baseline, which colorizes images without text descriptions. We carried out two human evaluations using Mechanical Turk to compare the performance of our model and the baseline. For each experiment, we randomly sampled 1,000 images from the test set and then turned these images into black and white. For each image, we generated a pair of two images using our model and the baseline, respectively. Our model took into account the caption in generation while the baseline did not. Then we randomly permuted the 2,000 generated images. In the first experiment, we presented to human annotators the 2,000 images, together with their original captions, and asked humans to rate the consistency between the generated images and the captions in a scale of $0$ and $1$, with $0$ indicating no consistency and $1$ indicating consistency. In the second experiment, we presented to human annotators the same 2,000 images without captions, but asked human annotators to rate the quality of each image without providing its original caption. The quality was rated in a scale of $0$ and $1$, with $0$ indicating low quality and $1$ indicating high quality.

\vspace{-2mm}
\paragraph{Results} The results of comparison are shown in Table~\ref{table:flower}. Our model achieves better consistency with captions and also better image quality by making use of information in captions. The colorization results on 10 randomly-sampled images from the test set are shown in Figure \ref{fig:flower1}. As we can see, without text input, the baseline approach often colorizes images with the same color (in this dataset, most images are painted with purple, red or white), while our framework can generate flowers similar to their original colors which are specified in texts. Figure \ref{fig:flower2} provides some example images generated with arbitrary text description using our model.

\vspace{-1mm}
\begin{table}[H
\centering
\begin{tabular}{||c c c c||}
 \hline
  &  Our Model & BaseLine & Truth\\ [0.5ex]
 \hline\hline
Consistency & \textbf{0.849} & 0.27 & N/A \\
\hline
Quality & 0.598 & 0.404 & \textbf{0.856}\\
 \hline
\end{tabular}
\caption{The average rate of consistency with captions and image quality for our model and the baseline model respectively, averaged over $1,000$ images. The average quality of 1,000 truth images from the data set is also provided for comparison.}
\label{table:flower}
\vspace{-2mm}
\end{table}

\vspace{-2mm}
\section{Conclusion and Future Work}
In this paper we introduce the problem of Language-Based Image Editing (LBIE), and propose a generic modeling framework for two sub-tasks of LBIE: language-based image segmentation and colorization. At the heart of the proposed framework is a fusion module that uses recurrent attentive models to dynamically decide, for each region of an image, whether to continue the text-to-image fusion process. Our models have demonstrated superior empirical results on three datasets: the ReferIt dataset for image segmentation, the Oxford-102 Flower dataset for colorization, and the synthetic CoSaL dataset for evaluating the end-to-end performance of the LBIE system. In future, we will extend the framework to other image editing subtasks and build a dialogue-based image editing system that allows users to edit images interactively.

{\small
\bibliographystyle{ieee}


\section{\label{sec:intro}Introduction}

One outstanding problem for the cold dark matter (CDM) paradigm is the missing satellites problem (MSP).  When originally formulated, the MSP highlighted the discrepancy between the number of satellites predicted in CDM simulations, numbering in the 100s, and observed in the Milky Way (MW), numbering $\sim$10 \cite{1993MNRAS.264..201K, 1999ApJ...522...82K, 1999ApJ...524L..19M}.  Since then, increasingly sensitive surveys have pushed the observed satellite count to $\sim$50 (e.g., Ref.~\cite{drlica-wagner2015,Bechtol:2015cbp,Koposov:2015cua}).  Simultaneously, however, improved resolution in numerical simulations has also increased the number of predicted satellites (e.g., \cite{2008MNRAS.391.1685S}).

A crucial step towards resolving the MSP is to correct for those satellites that have not yet been detected.  Only a fraction of the MW's virial volume has been surveyed \cite{2017arXiv170804247N}.  The Sloan Digital Sky Survey (SDSS), by which ultra-faint dwarfs with luminosities as low as 340 L$_\odot$ (Segue I) were discovered, covered only about a third of the sky.  For the faintest dwarfs, SDSS was complete to $\sim$10\% of the MW's virial radius \cite{2008ApJ...686..279K,2009AJ....137..450W}.  The observed count is thus a lower bound on the luminous MW satellite population.  Completeness corrections must be applied to derive the total number of luminous MW satellites.

Fully resolving the MSP requires that the completeness-corrected galaxy count match the predicted \emph{luminous} satellite abundance.  This depends on the physics of an additional key component: baryons.  There is growing evidence that not all dark matter subhalos host an observable galaxy.  Galaxy evolution models \cite{2000ApJ...539..517B} and star-formation histories of ultra-faint dwarfs \cite{2014ApJ...796...91B} indicate that feedback processes and reionization prevent star formation.  In fact, subhalos below $\sim$10$^9$ M$_\odot$ are inefficient in forming a luminous component \cite{2014MNRAS.442.1396W, 2014ApJ...792...99S}.  In CDM, most MW subhalos are dark.

In this work, we compare completeness corrections of the observed MW luminous galaxy population to theoretical predictions for the luminous galaxy population.  We use an analytic approach to highlight specific physics, and provide a roadmap for future MW-based DM constraints.  Our completeness correction is inspired by Refs.~\cite{2008ApJ...688..277T, 2014ApJ...795L..13H, 2016arXiv161207834J, 2017arXiv170804247N}, which used simulations or Bayesian techniques to estimate that the MW hosts hundreds of luminous satellites.  We calculate the total number of luminous galaxies down to 340 L$_\odot$ based on the satellites observed by SDSS.  For comparison, we predict the number of luminous satellites expected in CDM based on empirical scaling relations between halos and galaxies.

Successful dark matter models cannot produce just enough dark matter subhalos to match the corrected galaxy count---they must produce enough \emph{luminous} galaxies.  This places stringent constraints on warm dark matter (WDM) and sterile neutrino models, competitive with Lyman-$\alpha$ forest constraints \cite{Irsic:2017ixq}.

Successful galaxy formation models must produce enough luminous galaxies to match the corrected galaxy count.  This has implications for the mass threshold for the subhalos that host the faintest galaxies, the redshift of reionization, and the tidal stripping of subhalos.

\section{\label{sec:corrections}Completeness Corrections}

The total number of luminous satellites within the MW virial radius ($R_\text{vir}$ = 300 kpc) can be extrapolated from the number of observed satellites by calculating the correction factor $c$ that converts
\begin{equation}
N_\text{tot} = c(\Phi) N_\text{obs}, \label{eqn:c0}
\end{equation}
where $\Phi$ represents the set of parameters the correction depends on.  This includes the survey area, survey sensitivity, and the spatial distribution of satellites.

Recasting in luminosities $L$, and given either a continuous observed luminosity function $dN_\text{obs}/dL$, or set of $N_\text{obs}$ satellites we can express Eq. \ref{eqn:c0} as
\begin{equation}
N_\text{tot} = \int c(L) \frac{dN_\text{obs}}{dL} dL ~ \approx ~ \sum_{i=1}^{N_\text{obs}} c(L_i),
\end{equation}
i.e. we integrate over the luminosity function or sum together the correction for each observed satellite.  The correction is
\begin{equation}
c(L) = \frac{\int_{V_\text{vir}} n(\mathbf{r}) ~ d\mathbf{r}}{\int_{V_\text{obs}(L)} n(\mathbf{r}) ~ d\mathbf{r}} \label{eqn:cM}
\end{equation}
where $n(\mathbf{r})$ is the 3D satellite distribution, $V_\text{vir}$ the MW virial volume, and $V_\text{obs}(L)$ the volume over which a satellite of luminosity $L$ has been surveyed.  Note that the normalization to the spatial distribution cancels, and thus the correction depends only on the shape of the spatial distribution function---not the absolute number of satellites.  Eq. \ref{eqn:cM} naturally accounts for anisotropies in the satellite distribution.

Although there are hints that the luminous satellite distribution is anisotropic \cite{1982Obs...102..202L, 1994ApJ...431L..17M, 2005MNRAS.363..146L, 2008ApJ...688..277T, drlica-wagner2015, bechtol2015, koposov2015, 2017arXiv170804247N}, we assume it is sufficiently isotropic
to be separable. The correction factor is thus
\begin{equation}
c(L) = c_r(L) ~ c_\Omega(L)
\end{equation}
where $c_r$ and $c_\Omega$ are the radial and angular corrections, respectively, and
\begin{equation}
c_r(L) = \frac{\int_0^{R_\text{vir}} \frac{dN}{dr} ~ dr}{\int_0^{r_c(L)} \frac{dN}{dr} ~ dr}
\hspace{0.5 cm} \text{and} \hspace{0.5 cm}
c_\Omega = \frac{4 \pi}{\int_0^{\Omega_c} d\Omega}
\end{equation}
and $r_c(L)$ is the radius out to which a survey covering an area $\Omega_c$ of the sky is complete for a galaxy with luminosity $L$.  To predict the number of satellites out to a given detection limit for other surveys based on counts from an earlier survey like SDSS, one can replace $R_\text{vir}$ with the radius out to which those surveys are complete.  For SDSS, we adopt the completeness radius derived by Ref. \cite{2009AJ....137..450W}, for which
\begin{equation}
r_c(L) = 15.7 \text{ kpc } \left( \frac{L}{100~\text{L}_\odot} \right)^{0.51}.
\end{equation}
The angular correction dominates for the brightest galaxies, while the radial correction dominates for the faintest galaxies.  The turnover between the two occurs at roughly L = 500 - 2000 L$_\odot$ (depending on the satellite distribution), and rapidly becomes large at lower luminosities.

\begin{figure}
\includegraphics[width=0.5\textwidth]{menc_bands.pdf}
\caption{Normalized radial distributions.  The cumulative number of satellites within radius $r$, normalized to the total number of satellites at $R_\text{vir}$ = 300 kpc, is shown.  Distributions marked by dashed lines are expected when satellites survive extreme tidal stripping. The solid red lines are our fiducial radial distributions, matching the MW classical satellites.  The dotted black line depicts the latter distribution depleted by Ref.~\cite{2017MNRAS.471.1709G}'s tidal stripping model.  See text for details.}
\label{fig:profiles}
\end{figure}

The radial distribution of luminous satellites, which is highly uncertain, has a significant impact on the corrected galaxy count.  Well-motivated radial profiles from the literature, spanning the range of uncertainty on tidal stripping and subhalo-galaxy identification, are shown in Fig.~\ref{fig:profiles}. The centrally concentrated NFW (with concentration $c_\text{-2}$ = 9) \cite{1996ApJ...462..563N} and SIS (singular isothermal sphere) \cite{2011ApJ...731...44N} models correspond to the smooth dark matter distribution of the host.  These profiles include satellites that are severely tidally stripped \cite{2016MNRAS.457.1208H, 2017arXiv170804247N}, which may be considered destroyed in other contexts (or unresolved in numerical simulations). The light red line is representative of distributions generated from dark matter only (DMO) simulations, but with assumptions on which subhalos host galaxies \cite{2014ApJ...795L..13H, 2017MNRAS.471.4894D}.  The black dotted line shows how tidal stripping by a baryonic disk reduces the number of satellites close to the center of the MW as in Ref.~\cite{2017MNRAS.471.1709G} (hereafter GK17; see also \cite{2010ApJ...709.1138D}).  In contrast, the most severely stripped halos in Ref.~\cite{2014MNRAS.438.2578G} are shown in green.  This corresponds to the hypothesis that the SDSS satellites are highly stripped remnants of larger galaxies.  For our fiducial distribution, we adopt that derived in Ref.~\cite{2017MNRAS.471.4894D} (hereafter D17; shown by the dark red line), which matches the distribution of observed classical MW satellites.

\begin{figure*}
\centerline{
\includegraphics[scale=0.6]{ntot.pdf}
\includegraphics[scale=0.6]{min_mass.pdf}}
\caption{The number of completeness corrected luminous satellites (left) and the infall mass of the lowest mass subhalo hosting a $L > 340 L_\odot$ galaxy (right). Color match those in Fig.~\ref{fig:profiles}; the dark red denotes results based on D17.  The light colored bands denote the uncertainty due to anisotropy (based on \cite{2008ApJ...688..277T}).  Left: The gray-shaded region shows the predicted number of luminous satellites expected for the MW based on the calculation described in Sec. \ref{sec:constraints}.  If the completeness-corrected count falls within these bounds, there is no MSP. Right: The width of the dark bands is set by the uncertainty on the MW mass, (1-2) $\times 10^{12}$ M$_\odot$.  The light bands denote uncertainties due to anisotropy.  The bottom axis shows the subhalo mass at infall, and the top axis shows the average corresponding subhalo mass today \cite{2005MNRAS.356.1233V}.}
\label{fig:ntot}
\end{figure*}

We correct the number of galaxies observed through SDSS Data Release 8 (DR8) with these radial profiles.  Our results are shown in the left panel of Fig.~\ref{fig:ntot} and are listed in Tab.~\ref{tab:counts}.  The width of the bars denote the uncertainty due to anisotropy, as measured in \cite{2008ApJ...688..277T} (see supplementary material for a detailed discussion of anisotropies).  In agreement with Refs. \cite{2014ApJ...795L..13H, 2017arXiv170804247N}, we find that the correction is insensitive to the MW halo mass.

Radial distributions corresponding to the hypothesis that satellites survive extreme tidal stripping (NFW and SIS) are more centrally concentrated, resulting in smaller corrected counts.  Accounting for the effects of tidal stripping due to the presence of a baryonic disk as predicted by \cite{2017MNRAS.471.1709G} produce the largest corrections.

These results are a lower limit to the number of luminous satellites of the MW.  We have not included the satellites of the Large Magellanic Cloud, dwarfs with surface brightnesses $\mu \le$ 30 mag arcsec$^{-2}$ (``stealth galaxies", e.g. \cite{2010ApJ...717.1043B, 2016MNRAS.459.2370T}), which are below the detection limit of SDSS DR8, although they have been found by new surveys \cite{drlica-wagner2015,2016MNRAS.459.2370T}, and dwarfs with luminosities below Segue I's.  Segue I itself accounts for $\sim$40\% of the correction; accounting for even fainter galaxies will increase the total number significantly.  The inferred luminosity function of satellites is shown in the supplementary material.

\begin{table}
\caption{Completeness corrected satellite counts}
\label{tab:counts}
\begin{tabular}[b]{l c c c} \hline
&\multicolumn{3}{c}{Predictions} \\
distribution & all sky & DES & LSST Year 1 \\ \hline
NFW & 124 & 11 & 56 \\
SIS & 157 & 13 & 69 \\
ELVIS, stripped & 139 & 13 & 65 \\
D17 & 235 & 18 & 102 \\
DMO + gal & 250-503 & 20-28 & 109-198 \\
DMO + gal + GK17 & 830-1740 & 49-69 & 335-614 \\ \hline
\multicolumn{4}{p{\linewidth}}{\footnotesize Predictions for DES, when complete after year 5, and sensitive down to apparent magnitudes $V$ = 24.7; and for LSST after year 1, down to $V$ = 26.} \\
\end{tabular}
\end{table}

\section{\label{sec:constraints}Constraints on galaxy evolution and dark matter models}

The calculations above set only the total number of \emph{luminous} MW satellites that we can infer exists based on the observed dwarfs.  Do the corrected counts imply that the MSP is solved?  We present our fiducial calculation here, and provide details on choices and variants in the supplementary material.

The number of dark matter subhalos hosted by the MW is derived by integrating the CDM mass function, which follows the form
\begin{equation}
\frac{dN}{dM} = K_0 \left( \frac{M}{M_\odot} \right)^{-\alpha} \frac{M_\text{host}}{M_\odot}.
\end{equation}
where $M$ denotes the mass of a subhalo at infall.  The mass function based on present day (e.g. $z$ = 0) subhalo masses is lower due to tidal stripping ($M(z=0) < M$).  We adopt $K_0 = 1.88 \times 10^{-3}$ M$_\odot^{-1}$ and $\alpha = 1.87$ as in D17.  The total number of subhalos above a threshold $M_\text{min}$ is thus
\begin{equation}
N_\text{sub} = \int^{M_\text{host}}_{M_\text{min}} \frac{dN}{dM} ~ dM.
\end{equation}
Not all subhalos are believed to host galaxies \cite{2016MNRAS.456...85S, 2017arXiv170503018S, 2002MNRAS.333..177B, 2002ApJ...572L..23S}.  Given the fraction of subhalos of a given mass that host a luminous galaxy, $f_\text{lum}(M)$, we can derive the total number of luminous galaxies
\begin{equation} \label{eq:reionization}
N_\text{gal} = \int^{M_\text{host}}_{M_\text{min}} \frac{dN}{dM} f_\text{lum}(M) dM.
\end{equation}
The luminous fraction is a strong function of reionization redshift. $z_\text{re}$, and the survival criteria \cite{2000ApJ...542..535G}. We adopt the relation by D17 (see their Fig. 3), which assumes $z_\text{re}$ = 9.3 and a generous baryon survival criterion, which requires $v_\text{max}$ = 9.5 km/s (the peak of the circular velocity curve) at $z < z_\text{re}$ and $v_\text{peak} = 23.5$ km/s at $z > z_\text{re}$.  Adopting a less generous criterion to match other work in the literature \cite{2013MNRAS.432.1989S, 2014ApJ...786...87B, 2015ApJ...807L..12O} drops the predicted number of luminous satellites by a factor 2---our results thus represent an upper bound.

For comparison with our completeness correction, which only includes galaxies brighter than Segue I, we adopt $M_\text{min}$ = $M_\text{SegI}$.  We derive its total stellar mass by assuming a stellar mass-to-light ratio of 2 (i.e. $M_*^\text{SegI} = 680$ M$_\odot$, expected for an ancient metal-poor stellar population with a Kroupa initial mass function \cite{kroupa2001, martin2008}.  To derive Segue I's halo mass, we make use of the fact that a galaxy's stellar mass is empirically tightly correlated with halo mass \citep{2004MNRAS.353..189V, 2004ApJ...609...35K}, a relation known as the stellar-mass--halo-mass (SMHM) relation.  SMHM relations have only been calibrated for stellar masses greater than $M_*\sim 10^8M_\odot$ \cite{2013ApJ...770...57B, 2013MNRAS.428.3121M}, but hydrodynamic simulations indicate that extrapolations to low masses are reasonable \cite{2017arXiv170506286M}.  We adopt three SMHM relations that capture the diversity of SMHM relations and their scatter \citep{2014ApJ...784L..14B, 2013MNRAS.428.3121M, 2013ApJ...770...57B}, which gives a large range for $M_\text{SegI}$ = 8$\times$10$^6$ to 7$\times$10$^8$ M$_\odot$.  The SMHM of Moster et al. \cite{2013MNRAS.428.3121M} best matches hydrodynamic simulations of isolated galaxies \cite{2014MNRAS.445..581H,2017arXiv170506286M}.

\begin{figure}
\includegraphics[width=0.5\textwidth]{mf_nsubs.pdf}
\caption{The number of luminous (solid) and total (dashed) subhalos allowed by CDM and WDM mass functions for a given lower bound on the lowest mass subhalo, assuming a MW mass of 1.5 $\times$ 10$^{12}$ M$_\odot$.  The number of luminous subhalos is modeled as in D17, assuming a reionization redshift $z_\text{re}$ = 9.3 \cite{2016A&A...596A.108P}.  The grey band shows SHMH predictions for the infall mass of Segue I.}
\label{fig:mf_nsubs}
\end{figure}

The resultant number of subhalos and galaxies assuming a MW mass of 1.5 $\times$ 10$^{12}$ M$_\odot$ is shown in Fig.~\ref{fig:mf_nsubs}.  The solid line denote the number of luminous satellites predicted by CDM; the dashed line shows the total number of subhalos.  Down to $M_\text{min}$ = 10$^7$ M$_\odot$, there exists $\sim$2600 total subhalos and 280 galaxies, implying that only $\sim$10\% of such subhalos are luminous.  The number of luminous satellites down to $M_\text{SegI}$ for our range of SMHM relations is shown by the gray-shaded regions in Fig.~\ref{fig:mf_nsubs} and the left-hand panel of Fig.~\ref{fig:ntot}.  The SMHM relation of Moster et al. \cite{2013MNRAS.428.3121M} predicts $\sim$120 galaxies.

We now have all the tools required to match the theoretical and completeness-corrected galaxy counts.  Our key result is shown in the left-hand plot of Fig. \ref{fig:ntot}.  The number of galaxies more luminous than Segue I predicted in CDM matches the completeness-corrected observations for even the most conservative radial profile models (i.e. lies inside the gray-shaded region).  Moreover, some radial profiles lead to corrected counts that exceed the predicted range.  This is exacerbated if the reionization of the Local Group occurs earlier (see supplementary material).  We call this the ``too many satellites" problem.

These results have implications for galaxy formation theory and dark matter physics.

\emph{Subhalo minimum mass}.  Matching the corrected counts to CDM predictions gives a minimum subhalo mass for galaxies as faint as Segue I, as suggested by Ref.~\cite{2016arXiv161207834J}.  This is shown on the right panel of Fig.~\ref{fig:ntot}.  The bars denote the uncertainty on the lowest mass galaxy halo due to uncertainties on the MW mass, which we allowed to range from  $(1-2)\times$ 10$^{12}$ M$_\odot$.  As the transition from mostly bright to mostly dark subhalos (e.g. $f_\text{lum}$ = 0.5) occurs at $\sim$10$^8$ M$_\odot$ in our reionization model, the lowest mass galaxy is near that mass threshold.  Counts accounting for tidal stripping as in GK17 predict even smaller masses.  The tidal-stripping-induced uncertainty on the completeness correction is the single-biggest driver of uncertainty in the subhalo minimum mass.

\emph{Dark matter model}.  Dark matter models with suppressed matter power spectra \cite{2016PhRvD..93l3527C, 2014MNRAS.442.2487K, 2017PhRvD..95h3015C, 2016MNRAS.461...60L, 2017MNRAS.468.4285L, 2016MNRAS.463.3848B, 2017MNRAS.464.4520B, 2011PhRvD..83d3506P,2017PhRvD..95d3541H, 2014NatPh..10..496S, 2016PhRvD..94d3513S, 2017MNRAS.471.4559M, 2010IJMPD..19.1385K}, such as WDM, must reproduce \emph{at a minimum} the completeness-corrected counts.  We briefly sketch the constraints we can place on WDM models with our corrected counts.  This calculation is not intended to be a rigorous derivation of WDM constraints, but an illustration of possible limits when corrected counts are taken into account.

The radial distribution of WDM satellites closely follows CDM \cite{2014MNRAS.439..300L}, and thus the corrected counts derived above applies.  To obtain the number of luminous satellites predicted by WDM, an identical analysis as in the previous section can be performed with the WDM mass function, which can be obtained from the CDM mass function by multiplying the factor
\begin{equation}
	\frac{dn_\text{WDM}}{dn_\text{CDM}} = \left( 1 + \frac{M_\text{hm}}{M} \right)^{-\beta},
\end{equation}
where $\beta = 1.16$, $M$ is the infall mass, and $M_\textrm{hm}$ is the half-mode mass quantifying the suppression scale of the matter power spectrum \cite{2012MNRAS.424..684S}. We again use D17's reionization cutoff to estimate the number of luminous galaxies.  This is a conservative overestimate, as WDM halos tend to form, and form stars, later than in CDM \cite{2018arXiv180305424B}, and because some of the satellites will be fainter than Segue I.  In Fig.~\ref{fig:mf_nsubs}, we show the number of satellites predicted by WDM mass functions for thermal relic particle masses ranging from 1-8 keV.  If the MW has 120-150 galaxies brighter than Segue I, thermal relics below $\sim$4 keV are ruled out, although this depends on the MW halo mass (\cite{2014MNRAS.442.2487K}, and see supplementary material).  This implies that the 7 keV sterile neutrino is in tension with satellite counts.  More robust limits require the machinery of Ref. \cite{2016arXiv161207834J}, who find a 95\% lower limit of 2.9 keV.

\section{Conclusions}

Since the MSP was first identified, several advances in our understanding of dwarf galaxy evolution have reduced the severity of the missing satellites problem.  Star formation in low-mass halos has been demonstrated to be suppressed by reionization and feedback.  The discovery of many new dwarfs below the luminosity limit of the classical dwarfs have also closed the gap, as has the understanding that completeness corrections for the new dwarfs are large.  In this Letter, we show that such corrections imply that the number of satellite galaxies that inhabit the Milky Way is consistent with the number of luminous satellites predicted by CDM down to halo masses of $\sim$10$^8$ M$_\odot$.  There is thus no missing satellites problem.  If anything, there may be a ``too many satellites" problem.  The major remaining uncertainty is the radial distribution of satellites, stemming from the uncertainty in tidal stripping.  Our result pushes the scale for tests of CDM below $10^8 M_\odot$ in infall mass, or $\sim$10$^7$ M$_\odot$ in present day subhalo mass.  Methods that do not rely on baryonic tracers, like substructure lensing \cite{2014MNRAS.442.2434N, 2016JCAP...11..048H, 2018arXiv180101505V} or stellar stream gaps \cite{2017MNRAS.466..628B}, are required to test the predictions of CDM below this scale.  The implications for dark matter models are significant.  WDM theories equivalent to having thermal relic particle masses below 4 keV are in tension with MW satellite counts.

\section*{Acknowledgments}

We thank John Beacom, Andrew Benson, Matthew Buckley, Francis-Yan Cyr-Racine, Greg Dooley, Anna Nierenberg, Todd Thompson, and David Weinberg for helpful comments.  AHGP acknowledges support from National Science Foundation (NSF) Grant No. AST-1615838.