\section*{Acknowledgements}

We would like to thank Jim McCann and his colleagues at the Carnegie Mellon Textiles Lab for providing us with the necessary tools to programmatically write patterns for our industrial knitting machine.

\bibliographystyle{icml2019}

\section{Introduction}
Advanced manufacturing methods that allow completely automated production of customized objects and parts are transforming today's economy. One prime example of these methods is whole-garment knitting that is used to mass-produce many common textile products (e.g., socks, gloves, sportswear, shoes, car seats, etc.). During its operation, a whole garment knitting machine executes a custom low-level program to manufacture each textile object. Typically, generating the code corresponding to each design is a difficult and tedious process requiring expert knowledge. A few recent works have tackled the digital design workflow for whole-garment knitting~\cite{Underwood09, McCann16, Narayanan18,Yuksel2012,Wu18a,Wu18b}. None of these works, however, provide an easy way to specify patterns.

\figTeaser
\figMove
\figKnitMissTuck

The importance of patterning in textile design is evident in pattern books \cite{Donohue15, Shida17}, which contain instructions for hundreds of decorative designs that have been manually crafted and tested over time.
Unfortunately, these pattern libraries are geared towards hand-knitting and they are often incompatible with the operations of industrial knitting machines.
Even in cases when a direct translation is possible, the patterns are only specified in stitch-level operation sequences. Hence, they would have to be manually specified and tested for each machine type similarly to low-level assembly programming.

In this work, we propose an inverse design method using deep learning to automate the pattern design for industrial knitting machines. In our \emph{inverse knitting}, machine instructions are directly inferred from an image of the fabric pattern.
To this end, we collect a paired dataset of knitting instruction maps and corresponding images of knitted patterns.
We augment this dataset with synthetically generated pairs obtained using a knitting simulator~\cite{Shima11}.
This combined dataset facilitates a learning-based approach.
More specifically, we propose a theoretically inspired image-to-program map synthesis method that leverages both real and simulated data for learning.
Our contributions include:
{\setlength{\leftmargini}{6mm}
\begin{itemize}
\setlength\itemsep{0mm}
    \item An automatic translation of images to sequential instructions for a real manufacturing process;
    \item A diverse knitting pattern dataset that provides a mapping between images and instruction programs specified using a new domain-specific language (DSL)~\cite{kant2018recent} that significantly simplifies low-level instructions and can be decoded without ambiguity;
    \item A theoretically inspired deep learning pipeline to tackle this inverse design problem; and
    \item A novel usage of synthetic data to learn to neutralize real-world, visual perturbations.
\end{itemize}
}
In the rest of the paper, we first provide the necessary background in machine knitting and explain our 2D regular instructions, we then go over our dataset acquisition, detail our learning pipeline making use of synthetic data, and finally go over our experiment results.
\section{Knitting Background}
\label{sec:background}
Knitting is one of the most common forms of textile manufacturing.
The type of knitting machine we are considering in this work is known as a \emph{V-bed} machine, which allows automatic knitting of whole garments.
This machine type uses two beds of individually controllable needles, both of which are oriented in an inverted \emph{V} shape allowing opposite needles to transfer loops between beds.
The basic operations are illustrated in Figures~\ref{fig:knit_miss_tuck} and ~\ref{fig:move}:

{\setlength{\leftmargini}{4mm}
\begin{itemize}
\setlength\itemsep{-0.5mm}
    \item \textbf{Knit} pulls a new loop of yarn through all current loops,
    \item \textbf{Tuck} stacks a new loop onto a needle,
    \item \textbf{Miss} skips a needle,
    \item \textbf{Transfer} moves a needle's content to the other bed,
    \item \textbf{Racking} changes the offset between the two beds.
\end{itemize}
}

Whole garments (e.g. socks, sweatshirts, hats) can be automatically manufactured by scheduling complex sequences of these basic operations~\cite{Underwood09, McCann16}.
Furthermore, this manufacturing process also enables complex surface texture and various types of patterns.
Our aim is to automatically generate machine instructions to reproduce any geometric pattern from a single close-up photograph (e.g. of your friend's garment collection).
To simplify the problem, we assume the input image only captures 2D patterning effects of flat fabric, and we disregard variations associated with the 3D shape of garments.
\section{Instruction Set}

\figInstructionSet

General knitting programs are sequences of operations which may not necessarily have a regular structure.
In order to make our inverse design process more tractable, we devise a set of $17$ pattern
instructions (derived from a subset of the hundreds of instructions from~\cite{Shima11}).
These instructions include all basic knitting pattern operations and they are specified on a regular 2D grid that can be parsed and executed line-by-line.
We first detail these instructions and then explain how they are sequentially processed.

The first group of instructions are based on the first three operations, namely: \textbf{Knit}, \textbf{Tuck} and \textbf{Miss}.

Then, \emph{transfer} operations allow moving loops of yarn across beds.
This is important because knitting on the opposite side produces a very distinct stitch appearance known as reverse stitch or \textbf{Purl} -- our complement instruction of \emph{Knit}.

Furthermore, the combination of transfers with \emph{racking} allows moving loops within a bed.
We separate such higher-level operations into two groups:
\textbf{Move} instructions only consider combinations that do not cross other such instructions so that their relative scheduling does not matter, and
\textbf{Cross} instructions are done in pairs so that both sides are swapped, producing what is known as \emph{cable} patterns.
The scheduling of \emph{cross} instructions is naturally defined by the instructions themselves.
These combined operations do not create any new loop by themselves, and thus we assume they all apply a \emph{Knit} operation before executing the associated needle moves, so as to maintain spatial regularity.

Finally, transfers also allow different stacking orders when multiple loops are joined together. We model this with our final \textbf{Stack} instruction.
The corresponding symbols and color coding of the instructions are shown in Figure~\ref{fig:instruction_set}.

\figDataset

\subsection{Knitting Operation Scheduling}

Given a line of instructions, the sequence of operations is done over a full line using the following steps:\vspace{-2mm}

{\setlength{\leftmargini}{4mm}
\begin{enumerate}
\setlength\itemsep{0mm}
    \item The current stitches are transferred to the new instruction side without racking;
    \item The base operation (\emph{knit}, \emph{tuck} or \emph{miss}) is executed;
    \item The needles of all transfer-related instructions are transferred to the opposite bed without racking;
    \item Instructions that involve moving within a bed proceed to transfer back to the initial side using the appropriate racking and order;
    \item Stack instructions transfer back to the initial side without racking.
\end{enumerate}
}

\paragraph{Instruction Side}
The only instructions requiring an associated bed \emph{side} are those performing a \emph{knit} operation.
We thus encode the bed side in the instructions (\emph{knit}, \emph{purl}, \emph{moves}), except for those where the side can be inferred from the local context.
This inference applies to \emph{Cross} which use the same side as past instructions (for aesthetic reasons), and \emph{Stack} which uses the side of its associated \emph{Move} instruction.
Although this is a simplification of the design space, we did not have any pattern with a different behaviour.
\section{Dataset for Knitting Patterns}

Before developing a learning pipeline, we describe our dataset and its acquisition process.
The frequency of different instruction types is shown in Figure~\ref{fig:dataset}.

The main challenge is that, while machine knitting can produce a large amount of pattern data reasonably quickly, we still need to specify these patterns (and thus generate reasonable pattern instructions), and acquire calibrated images for supervised learning.

\figSupervisedData

\subsection{Pattern Instructions}

We extracted pattern instructions from the proprietary software KnitPaint~\cite{Shima11}. These patterns have various sizes and span a large variety of designs from cable patterns to pointelle stitches, lace, and regular reverse stitches.

Given this set of initial patterns (around a thousand), we normalized the patterns by computing crops of $20\times 20$ instructions with $50\%$ overlap, while using default front stitches for the background of smaller patterns. This provided us with 12,392 individual $20\times 20$ patterns (after pruning invalid patterns since random cropping can destroy the structure).

We then generated the corresponding images in two different ways:
(1) by knitting a subset of 1,044 patches, \emph{i.e}\onedot} \def\Ie{{I.e}\onedot, Real data, and (2) by rendering all of them using the basic pattern preview from KnitPaint, \emph{i.e}\onedot} \def\Ie{{I.e}\onedot, Simulated data.
See Figure~\ref{fig:supervised_data} for sample images.

\subsection{Knitting Many Samples}

The main consideration for capturing knitted patterns is that their tension should be as regular as possible so that knitting units would align with corresponding pattern instructions.
We initially proceeded with knitting and capturing patterns individually but this proved to not be scalable.

We then chose to knit sets of $25$ patterns over a $5\times 5$ tile grid, each of which would be separated by both horizontal and vertical tubular knit structures.
The tubular structures are designed to allow sliding $1/8$ inch steel rods which we use to normalize the tension, as shown in Figure~\ref{fig:acquisition}.
Note that each knitted pattern effectively provides us with two full opposite patterns (the front side, and its back whose instructions can be directly mapped from the front ones). This doubles the size of our real knitted dataset to \emph{2,088 samples} after annotating and cropping the knitted samples.

\figAcquisition[t]

\section{Instruction Synthesis Model}

We present our deep neural network model that infers a 2D knitting instruction map from an image of patterns.
In this section, we provide the theoretical motivation of our framework, and then we describe the loss functions we used, as well as implementation details.

\subsection{Learning from different domains}
When we have a limited number of real data, it is appealing to leverage simulated data because high quality annotations are automatically available.
However, learning from synthetic data is problematic due to apparent domain gaps between synthetic and real data.
We study how we can further leverage simulated data.
We are motivated by the recent {work}, Simulated+Unsupervised (S+U) learning~\cite{shrivastava2017learning}, but in contrast to them, we develop our framework from the generalization error perspective.

Let ${\mathcal{X}}$ be input space (image), and ${\mathcal{Y}}$ output space (instruction label), and ${\mathcal{D}}$ a data distribution on ${\mathcal{X}}$ paired with
a true labeling function $y_{\mathcal{D}}{:}\,{\mathcal{X}} {\rightarrow} {\mathcal{Y}}$.
As a typical learning problem, we seek a hypothesis classifier $h{:}\,{\mathcal{X}} {\rightarrow} {\mathcal{Y}}$ that best fits the target function $y$ in terms of an expected loss: ${\mathcal{L}}_{\mathcal{D}}(h,h') {=} \mathbb E_{x\sim {\mathcal{D}}}[l\left( h(x), h'(x) \right)]$ for classifiers $h,h'$, where $l{:}\,{\mathcal{Y}}{\times}{\mathcal{Y}} \,{\rightarrow}\, \mathbb R_+$ denotes a loss function.
We denote its empirical loss as ${\hat {\mathcal{L}}_{\hat{\mathcal{D}}}}(h,h') = \tfrac{1}{|{\hat{\mathcal{D}}}|} \sum_{i=1}^{|{\hat{\mathcal{D}}}|} l(h(x_i), h'(x_i))$, where $\hat{\mathcal{D}} {=} \{x\}$ is the sampled dataset.

In our problem, since we have two types of data available, a source domain ${\mathcal{D}}_S$ and a target domain ${\mathcal{D}}_T$ (which is real or simulated as specified later), our goal is to find $h$ by minimizing the combination of empirical source and target losses as $\alpha$-mixed loss,
${\hat{\mathcal{L}}}_\alpha(h, y) = \alpha {\hat{\mathcal{L}}}_{S}(h, y) + (1{-}\alpha) {\hat{\mathcal{L}}}_{T}(h, y),$ where $0 {\leq} \alpha {\leq} 1$, and for simplicity we shorten ${\mathcal{L}}_{{\mathcal{D}}_{\{S,T\}}} {=} {\mathcal{L}}_{\{S,T\}}$ and
we use the parallel notation ${\mathcal{L}}_{\{S,T\}}$ and $\hat{{\mathcal{L}}}_{\{S,T\}}$.
Our underlying goal is to achieve a minimal generalized target loss ${\mathcal{L}}_{T}$.
To develop a generalizable framework, we present a bound over the target loss in terms of its empirical $\alpha$-mixed loss, which is a slight modification of Theorem 3 of \cite{ben2010theory}.

\input{meta/theorem1.tex}

The proof can be found in the supplementary material.
Compared to \cite{ben2010theory}, Theorem~\ref{thm:generalization_bound} is purposely extended to use a more general definition of discrepancy $\textrm{disc}_{{\mathcal{H}}}(\cdot, \cdot)$ \cite{mansour2009domain} that measures the discrepancy of two distributions (the definition can be found in the supplementary material) and to be agnostic to the model type (simplification), so that we can clearly present our motivation of our model design.

Theorem~\ref{thm:generalization_bound} shows that mixing two sources of data is possible to achieve a better generalization in the target domain.
The bound is always at least as tight as either of $\alpha=0$ or $\alpha=1$ (The case that uses either source or target dataset alone).
Also, as the total number of the combined data sample $m$ is larger, a tighter bound can be obtained.
We consider 0-1 loss for $l$ in this section for simplicity, but not limited to.

A factor that the generalization gap (the right hand side in \Eref{thm:generalization_bound}) strongly depends on is the discrepancy $\mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T)$.
This suggests that we can achieve a tighter bound if we can reduce $\mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T)$.
We re-parameterize the target distribution ${\mathcal{D}}_T$ as ${\mathcal{D}}_R$ so that ${\mathcal{D}}_T {=} g\circ {\mathcal{D}}_R$, where $g$ is a distribution mapping function.
Then, we find the mapping $g^*$ that leads to the minimal discrepancy for the empirical distribution ${\hat {\mathcal{D}}}_R$ as:\vspace{-1mm}
\begin{align}
    g^* =& \operatornamewithlimits{argmin}\nolimits_g \mathrm{disc}_{\mathcal{H}}({\hat{\mathcal{D}}}_S,~g\circ {\hat{\mathcal{D}}}_R) \nonumber\\
       =& \operatornamewithlimits{argmin}\nolimits_g \max_{h,h'\in {\mathcal{H}}} | {\mathcal{L}}_{{\hat{\mathcal{D}}}_S}(h,h') - {\mathcal{L}}_{g\circ {\hat{\mathcal{D}}}_R}(h,h') |,
\end{align}
which is a min-max problem.
Even though the problem is defined for an empirical distribution, it is intractable to search the entire solution space;
thus, motivated by \cite{ganin2016domain}, we approximately minimize the discrepancy by generative adversarial networks (GAN)~\cite{goodfellow2014generative}.
Therefore, deriving from Theorem~\ref{thm:generalization_bound}, our empirical minimization is formulated by minimizing the convex combination of source and target domain losses as well as the discrepancy as:
\begin{equation}
{\hat h, \hat g} = \operatornamewithlimits{argmin}_{h\in {\mathcal{H}}, g \in {\mathcal{G}}} {\hat {\mathcal{L}}}_\alpha(h,y) + \tau\cdot\mathrm{disc}_{\mathcal{H}}({\hat{\mathcal{D}}}_S, g{\circ} {\hat{\mathcal{D}}}_R).
\end{equation}

Along with leveraging GAN, our key idea for reducing the discrepancy between two data distributions, \emph{i.e}\onedot} \def\Ie{{I.e}\onedot, domain gap, is to transfer the real knitting images (target domain, ${\hat{\mathcal{D}}}_R$) to synthetic looking data (source domain, ${\hat{\mathcal{D}}}_S$) rather than the other way around, \emph{i.e}\onedot} \def\Ie{{I.e}\onedot, making ${\hat{\mathcal{D}}}_S \approx \hat g \circ{\hat{\mathcal{D}}}_R$.
The previous methods have investigated generating realistic looking images to adapt the domain gap.
However, we observe that, when simulated data is mapped to real data, the mapping is a one-to-many mapping due to real-world effects, such as lighting variation, geometric deformation, background clutter, noise, \emph{etc}\onedot} \def\vs{{vs}\onedot.
This introduces an unnecessary challenge to learn $g(\cdot)$; thus, we instead learn to neutralize the real-world perturbation by mapping from real data to synthetic looking data.
Beyond simplifying the learning of $g(\cdot)$, it also allows the mapping to be utilized at test time for processing of real-world images.

We implement $h$ and $g$ using convolutional neural networks (CNN), and formulate the problem as a local instruction classification\footnote{While our program synthesis can be regarded as a multi-class classification, for simplicity, we consider the simplest binary classification here. However, multi-class classification can be extended by a combination of binary classifications
 \cite{shalev2014understanding}.}
 and represent the output as a 2D array of classification vectors $\Vec{s}_{(i,j)} \in [0;1]^K$ (\emph{i.e}\onedot} \def\Ie{{I.e}\onedot, softmax values over $k\in K$) for our $K = 17$ instructions at each spatial location $(i,j)$.
In the following, we describe the loss we use to train our model $h\circ g$ and details about our end-to-end training procedure.

\newcommand{\sumi}[1][h]{\sum_{i=1}^{#1}}
\newcommand{\sumj}[1][w]{\sum_{j=1}^{#1}}
\newcommand{\sum_{k=1}^{K}}{\sum_{k=1}^{K}}
\newcommand{\sum_{d=1}^8}{\sum_{d=1}^8}
\newcommand{\ifactor}[1]{\dfrac{1}{#1}}

\paragraph{Loss function}
We use the cross entropy for the loss ${\mathcal{L}}$.
We supervise the inferred instruction to match the ground-truth instruction using the standard multi-class cross-entropy
\hbox{$\textrm{CE}(\Vec{s}, \Vec{y}) = - \sum_k y_k\log\left( {s_k}\right)$}
where $s_k$ is the predicted likelihood (softmax value) for instruction $k$, which we compute at each spatial location $(i,j)$.

For synthetic data, we have precise localization of the predicted instructions.
In the case of the real knitted data, human annotations are imperfect and this can cause a minor spatial misalignment of the image with respect to the original instructions. For this reason, we allow the predicted instruction map to be globally shifted by up to one instruction.
In practice, motivated by multiple instance learning~\cite{dietterich1997solving}, we consider the minimum of the per-image cross-entropy over all possibles one-pixel shifts (as well as the default no-shift variant), \emph{i.e}\onedot} \def\Ie{{I.e}\onedot, our complete cross entropy loss is\vspace{-1mm}
\begin{equation}
\label{eq:mil_xentropy}
    \mathcal{L}_\textrm{CE} = \frac{1}{Z_{CE}} \min_{d} \sum\nolimits_{i,j \in \mathcal{N}_s} \textrm{CE}(\Vec{s}_{(i,j) + d}, \Vec{y}_{(i,j)}),
\end{equation}
where $d\in \{(dx,dy)\,|\,dx,dy\in\{-1,0,+1\}\}$ is the pattern displacement for the real data and $d \in \{(0,0)\}$ for the synthetic data.
The loss is accumulated over the spatial domain $\mathcal{N}_s = \{2,\dots,w{-}1\} {\times} \{2,\dots,h{-}1\}$ for the instruction map size $w \times h$ reduced by boundary pixels. $Z_{CE} = |\mathcal{N}_s|$ is a normalization factor.

\subsection{Implementation details}
{Our base architecture is illustrated in Figure~\ref{fig:teaser}.}
We implemented it using TensorFlow~\cite{abadi2016tensorflow}.
The prediction network \texttt{Img2prog} takes $160{\times} 160$ grayscale images as input and generates $20{\times}20$ instruction maps.
The structure consists of an initial set of 3 convolution layers with stride 2 that downsample the image to $20{\times}20$ spatial resolution, a feature transformation part made of $6$ residual blocks~\cite{he2016deep, Zhu17}, and two final convolutions producing the instructions.
The kernel size of all convolution layers is $3{\times}3$, except for the last layer which is $1{\times}1$.
We use instance normalization~\cite{Ulyanov16} for each of the initial down-convolutions, and ReLU everywhere.

We solve the minimax problem of the discrepancy $\textrm{disc}(\cdot, \cdot)$ \emph{w.r.t}\onedot} \def\dof{d.o.f\onedot $g$ using the least-square Patch-GAN \cite{Zhu17}.
Additionally, we add the perceptual loss and style loss~\cite{johnson2016perceptual} between input real images and its generated images and between simulated images and generated images, respectively, to regularize the GAN training, which stably speeds up the training of $g$.

The structure of the \texttt{Refiner} network $g$ and the balance between losses can be found in the supplementary.

\paragraph{Training procedure}
We train our network with a combination of the real knitted patterns and the rendered images.
We have oversampled the real data to achieve 1:1 mix ratio with several data augmentation strategies, which can be found in the supplementary material.
We train with 80\% of the real data, withholding 5\% for validation and 15\% for testing, whereas we use all the synthetic data for training.

According to the typical training method for GAN~\cite{goodfellow2014generative}, we alternate the training between discriminator and the other networks, $h$ and $g$, but we update the discriminator only every other iteration, and the iteration is counted according to the number of updates for $h$ and $g$.

We trained our model for $150k$ iterations with batch size $2$ for each domain data using {ADAM} optimizer with initial learning rate $0.0005$, exponential decay rate $0.3$ every $50,000$ iterations. The training took from $3$ to ${4}$ hours (depending on the model) on a Titan Xp GPU.

\section{Experiments}

We first evaluate baseline models for our new task, along with an ablation study looking at the impact of our loss and the trade-off between real and synthetic data mixing.
Finally, we look at the impact of the size of our dataset..

\paragraph{Accuracy Metric}
For the same reason our loss in \Eref{eq:mil_xentropy} takes into consideration a 1-pixel ambiguity along the spatial domain, we use a similarly defined accuracy.
It is measured by the average of
$\max_{d} \tfrac{1}{N_\textrm{inst}}\sum_{i,j} \mathbb{I}[{y_\textrm{GT}}_{(i,j)}\,{=}\,\operatornamewithlimits{argmax}_k {s}_{(i,j) + d}^k]$
over the whole dataset,
where $N_\textrm{inst} = Z_\textrm{CE}$ is the same normalization constant as in \Eref{eq:mil_xentropy}, $y_\textrm{GT}$ the ground-truth label,
$\mathbb{I}[\cdot]$ is the indicator function that returns 1 if the statement is true, 0 otherwise.
We report two variants: \texttt{FULL} averages over all the instructions, whereas \texttt{FG} considers all instructions but the background (\emph{i.e}\onedot} \def\Ie{{I.e}\onedot, discard the most predominant instruction in the pattern).

\paragraph{Perceptual Metrics}
For the baselines and the ablation experiments, we additionally provide perceptual metrics that measure how similar the knitted pattern would look.
An indirect method for evaluation is to apply a pre-trained neural network to generated images and calculate statistics of its
output, \emph{e.g}\onedot} \def\Eg{{E.g}\onedot, Inception Score~\cite{salimans2016improved}.
Inspired by this, we learn a separate network to render simulated images of
the generated instructions and compare it to the rendering of the ground truth using standard PSNR and SSIM metrics.
Similarly to the accuracy,
we allow for one instruction shift, which translates to full 8 pixels shifts in the image domain.

\subsection{Comparison to Baselines}

\Tref{tab:comparisons} compares the measured accuracy of predicted instructions on our real image test set.
We also provide qualitative results in \refFig{baselines}.

\tabComparisons

The first 5 rows of \Tref{tab:comparisons}-(a1-5) present results of previous works to provide snippets of other domain methods.
For CycleGAN, no direct supervision is provided and the domains are mapped in a fully unsupervised manner.
Together with Pix2pix, the two first methods do not use cross-entropy but L1 losses with GAN.
Although they can provide interesting image translations, they are not specialized for multi-class classification problems, and thus cannot compete.
All baselines are trained from scratch.
Furthermore, since their architectures use the same spatial resolution for both input and output, we up-sampled instruction maps to the same image dimensions using nearest neighbor interpolation.

S+U Learning \cite{shrivastava2017learning} used a refinement network to generate a training dataset that makes existing synthetic data look realistic.
In this case, our implementation uses our base network \texttt{Img2prog} and approximates real domain transfer by using style transfer.
We tried two variants: using the original Neural Style Transfer~\cite{Gatys16} and CycleGAN~\cite{Zhu17}.
Both input data types lead to very similar accuracy (negligible difference) when added as a source of real data.
We thus only report the numbers from the first one \cite{Gatys16}.

\tabPerInstruction

\subsection{Impact of Loss and Data Mixing Ratio}

The second group in \Tref{tab:comparisons}-(b1-2) considers our base network $h$ (\texttt{Img2prog}) without the refinement network $g$ (\texttt{Refiner}) that translates real images onto the synthetic domain.
In this case, \texttt{Img2prog} maps real images directly onto the instruction domain.
The results generated by all direct image translation networks trained with cross-entropy (a3-5) compare similarly with our base \texttt{Img2prog} on both accuracy and perceptual metrics.
This shows our base network allows a fair comparison with the competing methods, and as will be shown, our final performance (c1-5, d1) is not gained
from the design of \texttt{Img2prog} but \texttt{Refiner}.

The third group in \Tref{tab:comparisons}-(c1-5) looks at the impact of the mixing ratio $\alpha$ when using our full architecture.
In this case, the refinement network $g$ translates our real image into a synthetic looking one, which is then translated by \texttt{Img2prog} into instructions.
This combination favorably improves both the accuracy and perceptual quality of the results with the best mixing ratio of $\alpha {=} 2/3$ as well as a stable performance regime of $\alpha\in[0.5,0.9]$, which favors more the supervision from diverse simulated data.
While $\epsilon$ in Theorem~\ref{thm:generalization_bound} has a minimum at $\alpha{=}\beta$, we have a biased $\alpha$ due to other effects, $\textrm{disc}(\cdot)$ and $\lambda$.

We tried learning the opposite mapping $g$ (from synthetic image to realistic looking), while directly feeding real data to $h$.
This leads to detrimental results with mode collapsing.
The learned $g$ maps to a trivial pattern and texture that injects the pattern information in invisible noise -- \emph{i.e}\onedot} \def\Ie{{I.e}\onedot, adversarial perturbation -- to enforce that $h$  maintains a plausible inference.
We postulate this might be due to the non-trivial one-to-many mapping relationship from simulated data to real data, and overburden for $h$ to learn to compensate real perturbations by itself.

In the last row of \Tref{tab:comparisons}-(d1), we present the result obtained with a variant network, \texttt{Img2prog++} which additionally uses skip connections from each down-convolution of \texttt{Img2prog} to increase its representation power.
This is our best model in the qualitative comparisons of \refFig{baselines}.

Finally, we check the per-instruction behavior of our best model, shown through the per-instruction accuracy in Table~\ref{tab:per_instruction}.
Although there is a large difference in instruction frequency, our method still manages to learn some useful representation for rare instructions but the variability is high.
This suggests the need for a systematic way of tackling the class imbalance~\cite{Huang16, Lin18}.

\subsection{Impact of Dataset Size}

\figDatasetAccuracy
In Figure~\ref{fig:dataset_accuracy}, we show the impact of the real data amount on accuracy.
As expected, increasing the amount of training data helps (and we have yet to reach saturation).
With low amounts of data (here $400$ samples or less), the training is not always stable -- some data splits lead to overfitting.

\figBaselines
\section{Discussion and Related Work}

\noindent\textbf{Knitting instruction generation}\quad
We introduce automatic program synthesis for machine kitting using deep images translation.
Recent works allow automatic conversion of 3D meshes to machine instructions~\cite{Narayanan18}, or directly model garment patterns on specialized meshes~\cite{Yuksel2012, Wu18a}, which can then be translated into hand knitting instruction~\cite{Wu18b}.
While this does enable a wide range of achievable patterns, the accompanying interface requires stitch-level specification.
This can be tedious, requires prior knitting experience and the resulting knits are not machine-knittable.
We bypass the complete need of modeling these patterns and allow direct synthesis from image exemplars that are simpler to acquire and also machine knittable.

\noindent\textbf{Simulated data based learning}\quad
We demonstrate a way to effectively leverage both simulated and real knitting data.
There have been a recent surge of adversarial learning based domain adaptation methods~\cite{shrivastava2017learning,tzeng2017adversarial,hoffman2018cycada} in the simulation-based learning paradigm.
They deploy GANs and refiners to refine the synthetic or simulated data to look real.
We instead take the opposite direction to exploit the simple and regular domain properties of synthetic data.
Also, while they require multi-step training, our networks are end-to-end trained from scratch and only need a one-sided mapping rather than a two-sided cyclic mapping~\cite{hoffman2018cycada}.

\noindent\textbf{Semantic segmentation}\quad
Our problem is to transform photographs of knit structures into their corresponding instruction maps.
This resembles semantic segmentation which is a per-pixel multi-class classification problem except that the spatial extent of individual instruction interactions is much larger when looked at from the original image domain.
From a program synthesis perspective, we have access to a set of constraints on valid instruction interactions (e.g. \emph{Stack} is always paired with a \emph{Move} instruction reaching it).
This conditional dependency is referred to as context in semantic segmentation, and there have been many efforts to explicitly tackle this by Conditional Random Field (CRF) \cite{zheng2015conditional,chen2018deeplab,rother2004grabcut}.
They clean up spurious predictions of a weak classifier by favoring same-label assignments to neighboring pixels, \emph{e.g}\onedot} \def\Eg{{E.g}\onedot, Potts model.
For our problem, we tried a first-order syntax compatibility loss, but there was no noticeable improvement.
However we note that \cite{YuKoltun2016} observed that a CNN with a large receptive field but without CRF can outperform or compare similarly to its counterpart with CRF for subsequent structured guidance~\cite{zheng2015conditional,chen2018deeplab}.
While we did not consider any CRF post processing in this work, sophisticated modeling of the knittability would be worth exploring as a future direction.

Another apparent difference between knitting and semantic segmentation is that semantic segmentation is an easy -- although tedious -- task for humans, whereas parsing knitting instructions requires vast expertise or reverse engineering.

Finally, we tried to use a state-of-the-art scene parsing network with very large capacity and pretraining~\cite{Zhou16} which led to similar results to our best performing setup, but with a significantly more complicated model and training time.
See the supplementary for details.

\noindent\textbf{Neural program synthesis}\quad
In terms of returning explicit interpretable programs, our work is closely related to program synthesis, which is a \ignore{traditional} challenging, ongoing problem.\footnote{A similar concept is \emph{program induction}, in which the model learns to mimic the program rather than explicitly return it. From our perspective, semantic segmentation is closer to program induction, while our task is program synthesis.}
The recent advance of deep learning has made notable progress in this domain, \emph{e.g}\onedot} \def\Eg{{E.g}\onedot, \cite{johnson2017inferring, devlin2017robustfill}.
Our task would have potentials to extend the research boundary of this field, since it differs from any other prior task on program synthesis in that:
1) while program synthesis solutions adopt a sequence generation paradigm~\cite{kant2018recent},
our type of input-output pairs are 2D program maps, and
2) the domain specific language \ignore{(our instruction set)} is newly developed and
applicable to practical knitting.

\noindent\textbf{Limitations}\quad
This work has two main limitations:
(1) it does not explicitly model the pattern scale; and
(2) it does not impose hard constraints on the output semantics, thus the intent of some instructions may be violated.
We provide preliminary scale identification results in the supplementary, together with the details on the necessary post-processing that enables machine knitting of any output.
\section{Conclusion}

We have proposed an inverse process for translating high level specifications to manufacturing instructions based on deep learning.
In particular, we have developed a framework that translates images of knitted patterns to instructions for industrial whole-garment knitting machines.
In order to realize this framework, we have collected a dataset of machine instructions and corresponding images of knitted patterns.
We have shown both theoretically and empirically how we can improve the quality of our translation process by combining synthetic and real image data.
We have shown an uncommon usage of synthetic data to develop a model that maps real images onto a more regular domain from which machine instructions can more easily be inferred.

The different trends between our perceptual and semantic metrics bring the question of whether adding a perceptual loss on the instructions might also help improve the semantic accuracy.
This could be done with a differentiable rendering system.
Another interesting question is whether using higher-accuracy simulations~\cite{Yuksel2012, Wu18a} could help and how the difference in regularity affects the generalization capabilities of our prediction.

We believe that our work will stimulate research to develop machine learning methods for design and manufacturing.

\section*{Contents}
\begin{itemize}
\setlength{\itemsep}{0mm}

    \item[*] Details of the \texttt{Refiner} network.
    \item[*] Loss balancing parameters.
    \item[*] Used data augmentation details.
    \item[*] Pattern scale identification.
    \item[*] Post-processing details.
    \item[*] Additional quantitative results.
    \item[*] Additional qualitative results.
    \item[*] Lemmas and theorem with the proofs.
\end{itemize}

\section*{Additional Resources}
Additional knitting-related resources (the dataset, code and overview videos of the machine knitting process) can be found on our project page:\\ \url{http://deepknitting.csail.mit.edu/}

\section*{The \texttt{Refiner} Network}
Our refinement network translates real images into regular images that look similar to synthetic images. Its implementation is similar to \texttt{Img2prog}, except that it outputs the same resolution image as input, of which illustration is shown in Figure~\ref{fig:network_refiner}.

\section*{Loss Balancing Parameters}
When learning our full architecture with both \texttt{Refiner} and \texttt{Img2prog}, we have three different losses: the cross-entropy loss $\mathcal{L}_{CE}$, the perceptual loss $\mathcal{L}_\textrm{Perc}$, and the PatchGAN loss.

Our combined loss is the weighted sum
\begin{equation}
    \mathcal{L} = \lambda_\textrm{CE} \mathcal{L}_\textrm{CE}
                + \lambda_\textrm{Perc} \mathcal{L}_\textrm{Perc}
                + \lambda_\textrm{GAN} \mathcal{L}_\textrm{GAN}
\end{equation}
where we used the weights:
$\lambda_\textrm{CE} = 3$, $\lambda_\textrm{Perc} = 0.02/(128)^2$ and $\lambda_\textrm{GAN} = 0.2$.
The losses $\mathcal{L}_\textrm{Perc}$ and $\lambda_\textrm{GAN}$ are measured on the output of \texttt{Refiner}, while the loss $\lambda_\textrm{CE}$ is measured on \texttt{Img2prog}.

The perceptual loss~\citep{johnson2016perceptual} consists of the feature matching loss and style loss (using the gram matrix).
If not mentioned here, we follow the implementation details
of \cite{johnson2016perceptual}, where VGG-16~\cite{Simonyan14} is used for feature extraction, after replacing max-pooling operations with average-pooling.
The feature matching part is done using the \texttt{pool3} layer, comparing the input real image and the output of \texttt{Refiner} so as to preserve the content of the input data.
For the style matching part, we use the gram matrices of the \{\texttt{conv1\_2}, \texttt{conv2\_2}, \texttt{conv3\_3}\} layers with the respective relative weights \{0.3, 0.5, 1.0\}.
The measured style loss is between the synthetic image and the output of \texttt{Refiner}.

For ${\mathcal{L}}_\textrm{GAN}$ and the loss for the discriminator, the least-square Patch-GAN loss~\cite{Zhu17} is used.
We used $\{-1,1\}$ for the regression labels for respective fake and real samples insted of the label $\{0,1\}$ used in \cite{Zhu17}.

For training, we normalize the loss $\lambda_\textrm{CE}$ to be balanced according to the data ratio of a batch.
Specifically, for example, suppose a batch consisting of 2 real and 4 synthetic samples, respectively.
Then, we inversely weighted the respective cross entropy losses for real and synthetic data by the weights of $\tfrac{4}{6}$ and $\tfrac{2}{6}$, so that the effects from the losses are balanced.
This encourages the best performance to be expected at near $\alpha=0.5$ within a batch.

\begin{figure}[!t]
    \centering
    \includegraphics[width=0.8\linewidth]{figures/refiner_arch.pdf}
    \caption{The illustration of the \texttt{Refiner} network architecture, where S$\#N$ denotes the stride size of $\#N$, \texttt{IN\_ReLU} indicates the Instance normalization followed by ReLU, \texttt{Resblk} is the residual block that consists of ConvS1-ReLU-ConvS1 with shortcut connection~\cite{he2016deep}, Upsample is the nearest neighbor upsampling with the factor $2\times$, $F$ is the output channel dimension.
    If not mentioned, the default parameters for all the convolutions are the stride size of 2, $F=64$, and the $3\times 3$ kernel size.
    }
    \label{fig:network_refiner}
\end{figure}

\figScaleEstimationExp

\section*{Data Augmentation}
We use multiple types of data augmentation to notably increase the diversity of yarn colors, lighting conditions, yarn tension, and scale:
\begin{itemize}
    \item \textbf{Global Crop Perturbation}: we add random noise to the location of the crop borders for the real data images, and crop on-the-fly during training; the noise intensity is chosen such that each border can shift at most by half of one stitch;
    \item \textbf{Local Warping}: we randomly warp the input images locally using non-linear warping with linear RBF kernels on a sparse grid.
    We use one kernel per instruction and the shift noise is a 0-centered gaussian with $\sigma$ being $1/5$ of the default instruction extent in image space (i.e. $\sigma = 8/5$);
    \item \textbf{Intensity augmentation}: we randomly pick a single color channel and use it as a mono-channel input, so that it provides diverse  spectral characteristics. Also note that, in order to enhance the intensity scale invariance, we apply instance normalization \cite{Ulyanov16} for the upfront convolution layers of our encoder network.
\end{itemize}

\section*{Pattern scale identification}
Our base system assumes that the input image is taken at a specific zoom level designed for our dataset, which is likely not going to be true for a random image.
We currently assume this to be solved by the user given proper visual feedback (i.e., the user would see the pattern in real-time as they scan their pattern of interest with a mobile phone).

Here, we investigate the potential of automatically discovering the scale of the pattern.
Our base idea is to evaluate the confidence of the output instruction map for different candidate scales and to choose the one with highest confidence.
Although the softmax output cannot directly be considered as a valid probability distribution, it can serve as an approximation, which can be calibrated for~\cite{guo2017calibration}.
As a proof of concept, we take a full $5\times 5$ pattern image from our dataset and crop its center at different scales from $160$ pixels to $2000$ pixels of width.
We then measure the output of the network and compute a \emph{scale pseudo-confidence} as the average over pixels of the maximum softmax component.

In Figure~\ref{fig:scale}, we show a sample image with crops at various scales, together with the corresponding uncalibrated pseudo-confidence measure, which peaks at around $600$ pixels scale.
Coincidentally, this corresponds to the scale of our ground truth crops for that image.

This suggests two potential scenarios:
(1) the user takes a much larger image and then that pattern image gets analysed offline to figure out the correct scale to work at using a similar procedure, and then generates a full output by using a tiling of crops at the detected scale, or
(2) an interactive system could provide scale information and suggest the user to get closer to (or farther from) the target depending on the confidence gradient.

\tableLargeNetwork

\section*{Data post-processing}

As mentioned in the main paper, our framework does not enforce hard constraint on the output semantics.
This implies that some outputs may not be machine-knittable as-is.

\newcommand{\textsc{Cross}}{\textsc{Cross}}
\newcommand{\textsc{Move}}{\textsc{Move}}
\newcommand{\textsc{Stack}}{\textsc{Stack}}
\newcommand{\textsc{Knit}}{\textsc{Knit}}

More precisely, the output of our network may contain invalid instructions pairs or a lack thereof.
We remedy to these conflicts by relaxing the conflicting instruction, which happens in only two cases:
{
\setdefaultleftmargin{4mm}{}{}{}{}{}
\begin{enumerate}
    \item Unpaired \textsc{Cross}~instructions -- we reduce such instructions into their corresponding \textsc{Move}~variants (since \textsc{Cross}~are \textsc{Move}{}s with relative scheduling), and
    \item \textsc{Cross}~pairs with conflicting schedules (e.g., both pair sides have same priority, or instructions within a pair's side having different priorities) -- in this case, we randomly pick a valid schedule (i.e., its impact is local).
\end{enumerate}
}
This is sufficient to allow knitting on the machine.
Note that \textsc{Stack}~are semantically \emph{supposed} to appear with a \textsc{Move}, but they don’t prevent knitting since their operations lead to the same as \textsc{Knit}~when unpaired, and thus do not require any specific post-processing.

\section*{Additional quantitative results}

The focus of the experiments in the main paper was on assessing specific trends such as the impact of the dataset size, or the different behaviours of baseline networks, the impact of mixing data types and the ratios of these.

As can be noted, we used a standard (residual) architecture and tried to avoid over-engineering our network or its parameters.
However, we provide here results that show that we can obviously still do better by using more complex and larger networks, to the detriment of having to train for a longer time and resulting in a much larger model size.

In our baseline, we compared with a sample architecture from~\cite{Zhou16}, which we made small enough to compare with our baseline \texttt{Img2prog} implementation. Furthermore, our baseline implementations were all trained from scratch and did not make use of pre-training on any other dataset.

Here, we provide results for a much larger variant of that network, which we name \emph{Large Scene Parsing}, and makes use of pre-training on ImageNet~\cite{russakovsky2015imagenet}.
The quantitative comparison is provided in Table~\ref{tab:large}, which shows that we can achieve even better accuracy than our best current results using our \texttt{Refiner}+\texttt{Img2prog}++ combination.
However, note that this comes with a much larger model size: ours has $1.4M$ parameters\footnote{M for Million}, whereas \emph{Large Scene Parsing} has $51.4M$.
Furthermore, this requires pre-training on ImageNet with millions of images (compared to our model working with a few thousands only).

\section*{Additional qualitative results}
We present additional qualitative results obtained from several networks in Figure~\ref{fig:baselines_large}.

\figBaselinesL

\section*{Proof of Theorem 1}
We first describe the necessary definitions and lemmas to prove Theorem 1.
We need a general way to measure the discrepancy between two distributions, which we borrow from the definition of discrepancy suggested by~\cite{mansour2009domain}.\vspace{1mm}

\begin{definition}[Discrepancy \cite{mansour2009domain}]
Let ${\mathcal{H}}$ be a class of functions mapping from ${\mathcal{X}}$ to ${\mathcal{Y}}$. The discrepancy between two distribution ${\mathcal{D}}_1$ and ${\mathcal{D}}_2$ over ${\mathcal{X}}$ is defined as
\begin{equation}
\mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_1, {\mathcal{D}}_2) = \max\limits_{h,h' {\in} {\mathcal{H}}} \left| {\mathcal{L}}_{{\mathcal{D}}_1}(h, h') - {\mathcal{L}}_{{\mathcal{D}}_2}(h, h')\right|.
\end{equation}
\end{definition}
The discrepancy is symmetric and satisfies the triangle inequality, regardless of any loss function.
This can be used to compare distributions for general tasks even including regression.

The following lemma is the extension of Lemma 4 in \cite{ben2010theory} to be generalized by the above discrepancy.\vspace{1mm}

\begin{lemma}
	\label{thm:mixeddomain_gap}
	Let $h$ be a hypothesis in class ${\mathcal{H}}$, and assume that ${\mathcal{L}}$ is symmetric and obeys the triangle inequality. Then
	\begin{equation}
	|{\mathcal{L}}_\alpha(h,y) - {\mathcal{L}}_T(h,y)| \leq \alpha \left( \mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T) + \lambda \right),
	\end{equation}
	where \hbox{$\lambda {=} {\mathcal{L}}_{S}(h^*, y) {+} {\mathcal{L}}_{T}(h^*,y)$}, and the ideal joint hypothesis $h^*$ is defined as \hbox{$h^*{=}\operatornamewithlimits{argmin}_{h\in {\mathcal{H}}} {\mathcal{L}}_{S}(h, y) {+} {\mathcal{L}}_{T}(h,y)$}.
\end{lemma}
\begin{proof}
The proof is based on the triangle inequality of ${\mathcal{L}}$, and the last inequality follows the definition of the discrepancy.
\begin{align}
        &   |{\mathcal{L}}_\alpha(h,y) - {\mathcal{L}}_T(h,y)| \nonumber\\
=       &   \alpha |{\mathcal{L}}_S(h,y) - {\mathcal{L}}_T(h,y)| \nonumber\\
=       &   \alpha \left|{\mathcal{L}}_S(h,y) - {\mathcal{L}}_S(h^*,h) + {\mathcal{L}}_S(h^*,h) \right. \nonumber\\
        &   -{\mathcal{L}}_T(h^*,h) + {\mathcal{L}}_T(h^*,h) - {\mathcal{L}}_T(h,y) \left| \right. \nonumber\\
\leq    &   \alpha \big| \left|{\mathcal{L}}_S(h,y) - {\mathcal{L}}_S(h^*,h) \right| +  \nonumber\\
        &   \left|{\mathcal{L}}_S(h^*,h) - {\mathcal{L}}_T(h^*,h) \right|
    + \left|{\mathcal{L}}_T(h^*,h) - {\mathcal{L}}_T(h,y) \right|  \big|  \nonumber\\
\leq    & \alpha \big| {\mathcal{L}}_S(h^*,y) {+} |{\mathcal{L}}_S(h^*,h) {-} {\mathcal{L}}_T(h^*,h)|
    {+} {\mathcal{L}}_T(h^*,y)   \big|  \nonumber\\
\leq    & \alpha \left( \mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S, {\mathcal{D}}_T) + \lambda \right).
\end{align}
We conclude the proof.
\end{proof}

Many types of losses satisfy the triangle inequality, \emph{e.g}\onedot} \def\Eg{{E.g}\onedot, the $0-1$ loss \cite{ben2010theory,crammer2008learning} and
$l_1$-norm obey the triangle inequality, and $l_p$-norm ($p>1$) obeys the pseudo triangle inequality \cite{galanti2017theory}.

Lemma~\ref{thm:mixeddomain_gap} bounds the difference between the target loss and $\alpha$-mixed loss.
In order to derive the relationship between a true expected loss and its empirical loss, we rely on the following lemma.\vspace{1mm}

\begin{lemma}[\cite{ben2010theory}]
    \label{thm:true_empricial_gap}
For a fixed hypothesis $h$, if a random labeled sample of size $m$ is generated by
drawing $\beta m$ points from ${\mathcal{D}}_S$ and $(1 - \beta)m$ points from ${\mathcal{D}}_T$, and labeling them according
to $y_S$ and $y_T$ respectively, then for any $\delta\in(0,1)$, with probability at least $1-\delta$ (over the choice of the samples),
\begin{equation}
\label{eq:true_empricial_gap}
    |{\hat{\mathcal{L}}}_\alpha (h,y) - {{\mathcal{L}}}_\alpha (h,y)| \leq \epsilon(m, \alpha, \beta, \delta),
\end{equation}
where $\epsilon(m, \alpha, \beta, \delta) = \sqrt{ \tfrac{1}{2m} \left( \tfrac{\alpha^2}{\beta} + \tfrac{(1-\alpha)^2}{1-\beta} \right) \log(\tfrac{2}{\delta}) }$.
\end{lemma}
The detail function form of $\epsilon$ will be omitted for simplicity.
We can fix $m$, $\alpha$, $\beta$, and $\delta$ when the learning task is specified, then we can treat $\epsilon(\cdot)$ as a constant.\vspace{1mm}

\clearpage

\setcounter{theorem}{0}
\input{meta/theorem1.tex}

\begin{proof}
We use Lemmas~\ref{thm:mixeddomain_gap} and \ref{thm:true_empricial_gap} for the bound derivation with their associated assumptions.
\begin{align}
& {\mathcal{L}}_T({\hat h},y) \nonumber\\
& \leq {\mathcal{L}}_\alpha({\hat h},y) + \alpha \left( \mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T) + \lambda \right),\\
& \hspace{0.6\linewidth} \textrm{(By Lemma~\ref{thm:mixeddomain_gap})} \nonumber\\
& \leq {\hat{\mathcal{L}}}_\alpha({\hat h},y) + \alpha \left( \mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T) + \lambda \right) + \epsilon, \\
& \hspace{0.6\linewidth} \textrm{(By Lemma~\ref{thm:true_empricial_gap})} \nonumber\\
& \leq {\hat{\mathcal{L}}}_\alpha(h^*_T,y) + \alpha \left( \mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T) + \lambda \right) + \epsilon, \\
& \hspace{0.6\linewidth} ({\hat h} = \operatornamewithlimits{argmin}_{h\in{\mathcal{H}}} {\hat {\mathcal{L}}}_\alpha(h)) \nonumber\\
& \leq {{\mathcal{L}}}_\alpha(h^*_T,y) + \alpha \left( \mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T) + \lambda \right) + 2\epsilon, \\
& \hspace{0.6\linewidth} \textrm{(By Lemma~\ref{thm:true_empricial_gap})} \nonumber\\
& \leq {{\mathcal{L}}}_T(h^*_T,y) + 2\alpha \left( \mathrm{disc}_{\mathcal{H}}({\mathcal{D}}_S,{\mathcal{D}}_T) + \lambda \right) + 2\epsilon, \\
& \hspace{0.6\linewidth} \textrm{(By Lemma~\ref{thm:mixeddomain_gap})} \nonumber
\end{align}
which concludes the proof.
\end{proof}

Theorem 1 does not have unnecessary dependencies for our purpose, which are used in~\cite{ben2010theory} such as unsupervised data and the restriction of the model type to finite  VC-dimensions.