Data sources for design by analogy

External stimuli available in various databases can benefit designers, especially those who have limited domain knowledge. Data sources for design by analogy can vary across different types and forms. In terms of representation modalities, stimuli can be pictorial or verbal/textual. Many computational tools and methods have been proposed to search and retrieve textual stimuli to support design-by-analogy. Patent databases and biology corpora are two primary data sources for textual stimuli. IDEA-INSPIRE was presented by Chakrabarti et al. to automatically search analogies from a biological database to solve a given design problem (Chakrabarti et al., Reference Chakrabarti, Sarkar, Leelavathamma and Nataraju2005; Sarkar and Chakrabarti, Reference Sarkar and Chakrabarti2008). Shu et al. took advantage of natural language analysis to correlate functional basis terms with biological keywords extracted from biological knowledge available in books and journals (Chiu and Shu, Reference Chiu and Shu2007; Cheong et al., Reference Cheong, Chiu, Shu, Stone and McAdams2011; Shu, Reference Shu2010). Goel et al. proposed DANE (Design by Analogy to Nature Engine) to search and retrieve the functioning of biological systems in the Structure-Behavior-Function library to address engineering problems (Vattam et al., Reference Vattam, Wiltgen, Helms, Goel and Yen2011; Goel et al., Reference Goel, Vattam, Wiltgen and Helms2012). Luo et al. developed a data-driven tool to search technology knowledge from a patent database to detect design opportunities and directions (Luo et al., Reference Luo, Yan and Wood2017). Fu et al. presented a computational method to discover the functional and surface similarity of patents, and then designers can automatically retrieve analogical stimuli from these patents (Fu et al., Reference Fu, Cagan, Kotovsky and Wood2013a).

As designers are considered visualizers who are skillful in making and manipulating visual representations, they prefer visual stimuli. The use of visual stimuli through analogy is seen as a powerful strategy for designers to generate creative concepts. Jin and Benami indicated that the shapes and structures of a design artifact might be more stimulating than the functions (Jin and Benami, Reference Jin and Benami2010). Goldschmidt et al. showed that designers surrounded by visual stimuli could produce more ideas with a high level of creativity (Goldschmidt and Smolkov, Reference Goldschmidt and Smolkov2006). Linsey et al. showed that designers often prefer visual representations to textual descriptions for idea generation, and photographs are growing in popularity due to easy retrieval from the Internet (Linsey et al., Reference Linsey, Clauss, Kurtoglu, Murphy, Wood and Markman2011; Atilola et al., Reference Atilola, Tomko and Linsey2016). Du and MacDonald indicated that designers should be presented experimental product information as visual features that can be more easily recognized and recalled than text (Du and MacDonald, Reference Du and MacDonald2015). Goucher-Lambert et al. expanded upon why visual analogies can supplement or replace other modes of analogical transfer in design on the cognitive side (Goucher-Lambert et al., Reference Goucher-Lambert, Moss and Cagan2019; Goucher-Lambert et al., Reference Goucher-Lambert, Gyory, Kotovsky and Cagan2020).

Sketch as one of the visual inspiration sources significantly contributes to provoking idea generation. The display of sketches can help designers discover potentially visual hints that could help define a specific space in which a search for a creative concept is productive (Shah et al., Reference Shah, Vargas-Hernandez, Summers and Kulkarni2001). McKoy et al. showed that novice designers could generate higher quality and more novel design concepts when presented with sketches (McKoy et al., Reference McKoy, Vargas-Hernández, Summers and Shah2001). Goel indicated that a sketch could be transformed into another visually related sketch but distinct from its previous sketch (Goel, Reference Goel1995). Yang et al. suggested that the designer should create a drawing to elicit information from the user that will be useful in driving the design forward (Yang, Reference Yang2009; Macomber and Yang, Reference Macomber and Yang2011). The power of sketches to promote visual analogy has been recognized by many researchers. The sketch is an ideal source to serve as a visual stimulus. However, few computational tools have been proposed to search and retrieve visual analogies from sketches effectively.

Sketch-based image retrieval

Researchers in the human–computer interaction and graphics communities have developed many sketch-based interactive tools to enable intuitive and rich user experiences, such as sketch-based image retrieval (SBIR). The goal of SBIR is to allow users to draw visual content and then find the most relevant examples in large image databases. As keyword-based queries can become cumbersome when representing complex visual appearances, Sketch-based queries can be a complement to depicting the shape of an object (Chen et al., Reference Chen, Cheng, Tan, Shamir and Hu2009; Eitz et al., Reference Eitz, Hildebrand, Boubekeur and Alexa2010; Hu et al., Reference Hu, Barnard and Collomosse2010; Cao et al., Reference Cao, Zhang, Liu, Guo and Lin2013; Yu et al., Reference Yu, Liu, Song, Xiang, Hospedales and Loy2016).

Recent neuroscience work suggests that shape ambiguity can cause the human brain to recognize and reinterpret different objects from the same sketch (Walther et al., Reference Walther, Chai, Caddigan, Beck and Fei-Fei2011). Shape ambiguity can be regarded as shape similarity in this case, as separate objects can be abstracted into a common representation. An effective SBIR system should accurately retrieve relevant images in the same category as the query sketch. However, in this paper, we argue that SBIR needs to go beyond category recognition in engineering design. If designers want to search for images from a particular category, then keyword-based image search already gives them an efficient way to find vast amounts of relevant images. Designers often explore ideas in fields different from their original domain area, for example, designers of concept cars consider the trends in boat design. This process is highly subjective and personal. Hence, how to retrieve images from multiple categories based on visual similarity becomes a critical problem in our research.

There have been significant advancements in deep neural network models to learn a common and general feature space for sketches. QuickDraw is a massive dataset of human-drawn sketches obtained from an online game called Quick, Draw!. Sketch-rnn is an unsupervised learning model based on the Variational AutoEncoder (VAE) framework for extracting shape patterns from the sketches in QuickDraw database and generating similar sketches conditioned on learned shape features (Kingma and Welling, Reference Kingma and Welling2013; Ha and Eck, Reference Ha and Eck2017). As a modification of sketch-rnn, Sketch-pix2seq is proposed to present shape features of multi-category objects in a latent space (Chen et al., Reference Chen, Tu, Yi and Xu2017). Recently, the authors have introduced dc-sketch-pix2seq which can reveal shape features for multiple categories of sketches and cluster sketches simultaneously (Zhang and Jin, Reference Zhang and Jin2020). This model has better performance for discovering visual similarities between sketch categories. In this paper, our dc-sketch-pix2seq is applied to learn a latent space that can represent the shape features of sketches. In the latent space, the visual similarity between different sketch categories can be quantified for measuring the analogical distance.

In summary, a rich body of research on computational methods has yet to be integrated into the extensive work on visual analogy. In this paper, we aim to fill the gap by developing a computational framework to search and retrieve visual stimuli from a comprehensive sketch database to support visual analogy.

Technical abstraction of visual stimuli search and retrieval framework

The main idea of our computational framework is to search and retrieve sketches generated by humans as creative source materials and stimulate designers to create potentially more innovative concepts driven by visual analogy. To realize this, we propose steps for building the computational framework, which is shown in Figure 2. It consists of three major steps, including: (1) pretrain the dc-sketch-pix2seq model, (2) quantify visual similarities, and (3) search and retrieve relevant sketches.

Fig. 2.

Steps for building the visual stimuli search and retrieval framework.

In the first step, the training dataset of the dc-sketch-pix2seq model contains sketches with different categories from Quickdraw. The model can learn the weights of the encoder and decoder and a latent space in which the shape features of the training sketches can be captured and represented. After acquiring the low-dimensional representations (latent vectors) for the training sketches, the deep clustering layer can learn a clustering space in which each latent vector is clustered using a soft clustering method to generate probability distribution. The distribution can be used to determine which one or more clusters each latent vector belongs to.

In the second step, the TCD method is proposed to measure how many clusters one sketch may belong to quantitatively. Based on the results of TCD, sketches in each category can be classified into four different types: Native (N); Departed (D); Native-Overlap (NO); and Departed-Overlap (DO). The classified sketches can be saved in four databases with indexes. A N-sketch is useful to represent the shape of its category. A D-sketch, NO-sketch, or DO-sketch can be used to measure the visual similarity between the given category and other categories. Given the classification result in a given category, different weights are assigned to different types of sketches. By accumulating the weights, we can quantify the similarity magnitude and rank other categories in descending order. The rank can tell the most similar or least similar categories to the given category. Finally, calculate the visual similarity rank for each category and save the ranks in a database named vs.

In the third step, a designer draws a sketch that reflects the rough idea without details. The sketch is the input for the encoder of dc-sketch-pix2seq, which copies the weights from the learned encoder in step 1. The input can be mapped to the learned latent space to produce a latent vector that catches the shape features. In the latent space, the k-nearest neighbor algorithm is applied to find the nearest k latent vectors of the input sketch. The k latent vectors are from the training sketches, and their category labels are known. The input sketch will be labeled according to the most frequent label of these k latent vectors. Given the category label of the input sketch, we can retrieve the same category sketches from N, D, NO, and DO database; or retrieve vs database to find out categories with high and low similarity, and then retrieve sketches from N, D, NO, and DO database of other categories.

Deep clustering encoder for extracting shape representations

A shape representation extraction approach is taken to learn about the low-dimensional latent feature space of the given sketch datasets. More specifically, it is desired that a generative model can be trained that can discover embedded shape patterns of different sketch categories in the latent feature space without supervised information (e.g., category labels). Among various deep generative models, the variational autoencoder (VAE) is a widely used technique due to its good performance in learning a smooth latent representation of the input images.

Ha and Eck (Reference Ha and Eck2017) proposed a sequence-to-sequence VAE for generating sketch drawings for completing a user's stroke-based drawing sequence of common objects. In this model, the stroke-based sketch drawings are captured as a recurrent neural network (RNN) that can carry out conditional and unconditional sketch generation. Due to its stroke-based modeling approach, however, it has a key limitation, which is the insufficient quality of learning latent representations of sketches from multiple categories. The limitation made it inadequate to learn visual relationships between multiple categories.

To overcome the limitation of learning from single category sketches, Chen et al. (Reference Chen, Tu, Yi and Xu2017) replaced the RNN layers with CNN layers to deal with pixel-based sketches (i.e., images). This change also removed the limitation of single-category sketch drawings and made it possible for the CNN to learn from sketches of multiple categories and generate a wide variety of sketches based on the user's input. Since this paper considers visual analogies from multiple categories, it is important that our generative model learns from sketches of multiple categories. The deep learning-based sketch generative model, called the dc-sketch-pix2seq model, is defined as follows.

Figure 3 shows the model structure of dc-sketch-pix2seq. Before inputting into the convolutional neural network, a sketch is filtered by a 3 × 3 matrix on the bottom left to extract salient shape features. The configurations of convolutional layers are expressed as h × w@d/s, where h, w, d, and s represent height, width, depth, and stride, respectively. The type of activate function is above each convolutional layer. The last convolutional layer outputs a one-dimensional vector, which is subsequently fed into two separate, fully connected layers. μ and σ are the mean and standard deviation of the posterior distribution, which is learned by the encoder, where z  =  μ + σ ⋅ ɛ is the latent vector and x is the input image. ɛ is a Gaussian noise. z is an input of the recurrent neural network defined in the paper (Ha and Eck, Reference Ha and Eck2017), which is the decoder. The goal of the decoder is to reconstruct the output, which is almost identical to the input. A clustering layer is concatenated to the latent space to cluster sketches during the training of the model.

Fig. 3.

Structure of deep clustering sketch-pix2seq.

The input of dc-sketch-pix2seq is a set of n sketches ${\boldsymbol x} = \{ {x_{\boldsymbol i}\in X} \} _{i = 1}^n$. X is the data space. The encoder compresses x into n latent vector ${\boldsymbol z} = \{ {z_{\boldsymbol i}\in Z} \} _{i = 1}^n$. Z is the latent space. The dimensionality of Z is typically much smaller than X. The decoder samples n sketches ${\boldsymbol {x}^{\prime}} = \{ {{{x}^{\prime}}_i\in X} \} _{i = 1}^n$ conditional on given latent vector z. The reconstruction loss of the dc-sketch-pix2seq model is:

(1)$$L_{\rm r} = E_{q_\phi ( {{\boldsymbol z}{\rm \vert }{\boldsymbol x}} ) }[ {\log p_\theta ( {{\boldsymbol {x}^{\prime}}{\rm \vert }{\boldsymbol z}} ) } ], $$

where q( ⋅ ) denotes the encoder and p( ⋅ ) denotes the decoder. ϕ and θ are the parameters to be trained in the encoder and decoder, respectively. The parameters are typically the weights and biases of the neural networks.$\;E_{q_\phi ( {{\boldsymbol z}{\rm \vert }{\boldsymbol x}} ) }({\cdot} )$ ensures the similarity between the generated strokes and the strokes within the sketches in the training set.

The clustering layer clusters all latent vectors in the latent space Z by simultaneously learning a set of K cluster centers $\{ {\mu_{\boldsymbol j}\in Z}\} _{j = 1}^K$ and mapping each latent vector z _i into a soft label q _i by student's t-distribution (Maaten and Hinton, Reference Maaten and Hinton2008). q_i = [q _i1, …, q _ij, …q _ik] is a soft label which quantifies the similarity between z _i and cluster center μ _j.

(2)$$q_{ij} = \displaystyle{{{( {1 + z_i-\mu_j^2 } ) }^{{-}1}} \over {\mathop \sum \nolimits_j {( {1 + z_i-\mu_j^2 } ) }^{{-}1}}},$$

where q _ij is the jth entry of q_i, representing the probability of z _i belonging to cluster j.

The clustering loss L _c is defined as a KL divergence between the distribution of soft labels Q measured by student's t-distribution and the predefined target distribution P derived from Q. The clustering loss is defined as

(3)$$L_{\rm c} = D_{\rm KL}( {PQ} ) = \mathop \sum \limits_i \mathop \sum \limits_j p_{ij}\log \displaystyle{{\,p_{ij}} \over {q_{ij}}},$$

where the target distribution P is defined as

(4)$$p_{ij} = \displaystyle{{q_{ij}^2 /\mathop \sum \nolimits_i q_{ij}\;\;} \over {\mathop \sum \nolimits_j \left({q_{ij}^2 /\mathop \sum \nolimits_i q_{ij}} \right)}}.$$

Raising q _ij to the second power and then dividing by the frequency per cluster allows the target distribution P to improve cluster purity and stress on confident labels while normalizing the contribution of each centroid on the clustering loss to prevent large clusters from distorting the latent space. Therefore, data points with high confidence are used as supervision, and points in each cluster distribute more densely, where D _KL measures the nonsymmetric difference between two probability distributions, P, and Q are defined by (4) and (2), and match Q to P.

In dc-sketch-pix2seq, the encoder and decoder are used to learn representations in an unsupervised manner and the learned latent space can preserve shape features in sketches. The clustering loss is responsible for manipulating the latent space in order to cluster sketches based on visual similarity. The objective of dc-sketch-pix2seq is

(5)$$L_{\rm rc} = L_{\rm r} + \tau L_{\rm c},$$

where L _r is a reconstruction loss from (2) and L _c is a clustering loss from (3). The coefficient τ is better to be less than 1 and more than 0.

The training process of dc-sketch-pix2seq and the performance comparison of dc-sketch-pix2seq with other two deep learning models (Chen et al., Reference Chen, Tu, Yi and Xu2017; Ha and Eck, Reference Ha and Eck2017) are illustrated in our previous work (Zhang and Jin, Reference Zhang and Jin2020).

Sketch classifications

The output of the clustering layer is the probability distribution of each latent vector z _i into each soft clustering label j. By clustering space, we mean any K-dimensional vector ρ ∈ ℝ^K that represents a probability distribution of clustering, ρ = [p(c ₁|ρ), …, p(c _k|ρ), …, p(c _K|ρ)], c _k(1 ≤ k ≤ K) represents the jth cluster. p(c _k|ρ) means the probability of data ρ belonging to kth cluster.

In dc-sketch-pix2seq, the inputs are sketches belonging to different categories, x = [x ₁₁, …, x _ij, …, x _st], x _ij means the jth sketch belonging to ith category, s is the number of categories, t is the number of sketches in sth category. In the latent space, latent vectors are z = [z ₁₁, …, z _ij, …, z _st]. In the clustering space, the probability distributions of latent vectors can be represented by a super matrix ℚ, ℚ = [Q₁, Q₂, …, Q_s]. For matrix Q_i (1 ≤ i ≤ s), it includes n sketches. Q_i = [q_i1, …, q_ij, …, q_in], q_ij(1 ≤ j ≤ n) represents the probability distribution of a latent vector z _ij, that is q_ij = [p(c ₁|z _ij), …, p(c _k|z _ij), …, p(c _K|z _ij)], where P(c _k|z _ij) means the probability of z _ij belonging to cluster c _k, $\;\sum\nolimits_1^K {P( {{c}_k{\rm \vert }z_{ij}} ) } = 1$. Soft clustering produces multi-cluster predictions for x _ij, while the ground truth category of x _ij is single labeled. For example, in a three-dimensional clustering space, assuming that all sketches also come from three categories, ω ₁, ω ₂, ω ₃. When the ground truth category of x _ij is ω _i, the probability distribution of the corresponding latent vector z _ij might be q_ij = [0.8, 0.1, 0.1]. The cluster prediction of z _ij is c ₁ which has the maximum probability. However, if q_ij = [0.46, 0.45, 0.09], could we still say z _ij should be clustered to c ₁ rather than both c ₁ and c ₂? Therefore, sketch x _ij might belong to more than one cluster. One sketch can belong to multiple clusters because it includes some shape features shared by various categories. It means these special sketches in the latent space can be helpful to calculate the visual similarity between different categories.

In Figure 4, circles “o” indicate input sketches and crosses “×” represent cluster centroids in the latent space. Different categories are rendered with different colors. Solid lines indicate decision boundaries that are perpendicular bisectors of adjacent cluster centers. There are some sketches from the categories ω ₁, ω ₂, ω ₃. The cluster label of each category is determined by which cluster prediction most sketches belong. We call it the ground truth cluster. Supposed most sketches from the category ω ₁ are predicted to belong to cluster c ₁. Then, the ground truth cluster for category ω ₁ is c ₁. We assume sketches in the same category should have similar shapes and can be distinguished from other categories. Therefore, most sketches from the same category can be grouped in the same cluster based on shape similarity. The ground truth cluster is not assigned a priori but based on the location of most sketches from a category in the latent space. Each input sketch x _ij can be classified into four possible types, including:

• • Native – only one clustering prediction that is the same as the ground truth cluster.

• • Departed – only one clustering prediction that is not the same as the ground truth cluster.

• • Native-Overlap (n) – multi-clustering predications that include the ground truth cluster; the overlap number n should be no more than the number of clusters.

• • Departed-Overlap (n) – multi-clustering predictions that do not include the ground truth cluster; the overlap number n should be no more than the number of clusters.

Fig. 4.

Different types of sketches in a latent space including three clusters.

In Figure 4, for category ω ₁, all orange points belonging to cluster c ₁ are native points; the orange points belonging to cluster c ₂ or c ₃ are departed points; the orange point located in the line between cluster c ₁ and c ₂ areas is a native-overlap point with two overlaps; the orange point located in the line between cluster c ₁, c ₂, and c ₃ areas is a native-overlap point with three overlaps; the orange point located in the line between cluster c ₂ and c ₃ areas is a departed-overlap point with two overlaps.

Based on shape similarity, Native (N) points are representatives of a category. Native-Overlap (NO) points share similar shape features with other categories. Departed (D) points are “accidentally” clustered into another single category. It means the shapes of these sketches are more similar to another category. Departed-Overlap (DO) points are “accidentally” clustered into multiple other categories. It means the shapes of these sketches are more similar to other multiple categories. Possible reasons for why D and DO points appear as users of QuickDraw application are given a keyword to draw a sketch; they draw salient shape features of an object to represent the category. Some participants’ visual understanding of the keyword may be different from most participants,’ or they did not draw the sketch in the same shape pattern as most participants did.

Top clustering detection-based visual similarity measurement

In Figure 4, we can see points from the same category can be distributed in different clusters. It is not appropriate to use distances between cluster centroids to measure the similarity between different categories. For example, the centroid (orange) of the category ω ₁ has almost the same distance to the centroid (blue) of the category ω ₂ and the centroid (green) of category ω ₃. Therefore, category ω ₂ and category ω ₃ have the same similarity with category ω ₁ based on Euclidean distance. However, we can tell category ω ₁ is more similar to category ω ₃ than category ω ₂ based on the overlap magnitude, as more sharing points exist in the overlap regions between category ω ₁ and category ω ₂. In this paper, we propose a novel method called top clustering detection (TCD) which can determine the most suitable number of top clustering for a sketch by finding the minimum Euclidean distance between the sketch with K ideal centers. K is the number of clusters. Generally, the ideal centers from 1-clustering to K-clustering are defined as follows.

(6)$$\left[{\matrix{ {\matrix{ {\matrix{ {l_1} \cr {l_2} \cr } } \cr \vdots \cr } } \cr {l_K} \cr } } \right] = \left[{\matrix{ 1 & 0 & 0 & \cdots & 0 \cr 1 & 1 & 0 & \cdots & 0 \cr \vdots & \vdots & \vdots & \cdots & \vdots \cr 1 & 1 & 1 & \cdots & 1 \cr } } \right]_{KK}.$$

Based on the TCD method, each sketch will be assigned to one or more than one clusters. Based on the assumption that sketches coming from the same category share more shape features. There is a high possibility that sketches in the same category will be assigned to the same cluster. The ground truth cluster of a category is determined by which cluster label has the largest number of the top 1-clustering sketches. According to the previous section, we can classify sketches of each category into four types of points. Based on the type of points, we define the corresponding weights. According to the weights, we can calculate the similarity magnitude between different categories. The procedure to classify sketches into the category ω _i and calculate the visual similarity between category ω _i with other categories is shown as follows:

• Step 1: In a K-dimensional clustering space, the probability distribution of a latent vector z_ij is

  (7)$${\boldsymbol q}_{{\boldsymbol ij}} = [ p( {{ c}_1{\rm \vert }z_{{\boldsymbol ij}}} ) , \;\ldots , \;p( {{c}_k{\rm \vert }z_{{\boldsymbol ij}}} ) , \;\ldots , \;p( {c}_K\vert z_{{\boldsymbol ij}}) ]. $$

• Step 2: Find the maximum probability in q_ij, then normalize q_ij.

  (8)$$\bar{{\boldsymbol q}}_{ij} = \displaystyle{{{\boldsymbol q}_{{\boldsymbol ij}}} \over {\mathop {\max }\limits_k {\boldsymbol q}_{{\boldsymbol ij}}}}.$$

• Step 3: Sort $\bar{{\boldsymbol q}}_{ij}$ in descending order to obtain $\bar{{\boldsymbol q}}_{ij}^s$.

• Step 4: Argsort $\;\bar{{\boldsymbol q}}_{ij}$ in descending order to obtain ${\bar{\boldsymbol {q}}^{\prime}}_{ij} = [ {{{c}^{\prime}}_1, \;\;{{c}^{\prime}}_2, \;\ldots , \;{{c}^{\prime}}_K} ]$, where the topmost labels are more likely to be the multiple clustering labels of the input data x _ij.

• Step 5: Calculate the Euclidean distance between $\bar{{\boldsymbol q}}_{ij}^s$ and l _k (k = 1, 2, …, K), and the most possible number of clustering ${k}^{\prime}_{ij}$ is given by:

  (9)$${k}^{\prime}_{ij} = \mathop {{\rm argmin}}\limits_k \bar{{\boldsymbol q}}_{ij}^s -l_k,$$

where l _k is the ideal cluster center of the topmost k clustering, which is defined in (6).

• Step 6: The clustering labels c_ij of x _ij is the first k′ elements of $\bar{{\boldsymbol q}}_{ij}^{\prime}$, namely ${\boldsymbol c}_{ij} = [ {{{c}^{\prime}}_1, \;{{c}^{\prime}}_2, \;\ldots , \;{{c}^{\prime}}_{{k}^{\prime}}} ]$. If k′ = 1, x _ij is a top 1-cluster point. If k′ > 1, x _ij is a multiple cluster point.

• Step 7: Determine the ground truth cluster label of the category ω _i (i = 1, 2, …, s) based on the most assigned cluster label of top 1-cluster points, assume it is c _i.

• Step 8: Classify all input points into four types and determine weights. From step 6, assume all sketches in category ω _i are assigned by cluster label c _i. if x _ij is a native point ${\boldsymbol c}_{ij} = [ {{{c}^{\prime}}_k} ]$ $( {{{c}^{\prime}}_k = c_i} )$, then add x _ij to a native point set N _i; if x _ij is a departed point ${\boldsymbol c}_{ij} = [ {{{c}^{\prime}}_k} ]$ $( {{{c}^{\prime}}_k\ne c_i} )$, define the weight $w_{{{c}^{\prime}}_k}^{ij}$ as 1, then add x _ij to a departed point set D _i; If x _ij is a native-overlap (k′) point ${\boldsymbol c}_{ij} = \underbrace{{[ {{{c}^{\prime}}_1, \;{{c}^{\prime}}_2, \;\ldots , \;{{c}^{\prime}}_{{k}^{\prime}\;}} ] }}_{{{k}^{\prime}}}$ (c _i is included), define the weight $w_{{{c}^{\prime}}_k}^{ij} ( {{{c}^{\prime}}_k\ne c_i} )$ as 1/n, then add x _ij to a native-overlap point set NO _i; If x _ij is a departed-overlap (k′) point ${\boldsymbol c}_{ij} = \underbrace{{[ {{{c}^{\prime}}_1, \;{{c}^{\prime}}_2, \;\ldots , \;{{c}^{\prime}}_{{k}^{\prime}\;}} ] }}_{{{k}^{\prime}}}$ (c _i is not included), define the weight $w_{c_k^{^{\prime}\;} }^{ij}$ as 1/n, then add x _ij to a departed-overlap point set DO _i.

• Step 9: For all sketches in the category ω _i, accumulate all weight values of other clusters $\underbrace{{[ {{{c}^{\prime}}_1, \;{{c}^{\prime}}_2, \;\ldots , \;{{c}^{\prime}}_K} ] }}_{{K-1}}$ (c _i is not included). The cluster with the largest weight summation has the highest underlying shape similarity with cluster c _i, whose corresponding category is ω _i.

• Step 10: Determine visual similarity. The similarity is computed by normalizing the weight summation by the largest number among all weights.

• Step 11: Rank other clusters based on the weights in descending order to obtain visual similarity rank vs _i.

The TCD-based visual similarity quantification algorithm is shown as follows.

Algorithm 1

TCD-based visual similarity quantification

For example, in a latent space including three clusters, firstly, assuming the latent vector z_ij of the sketch x _ij from category ω ₁ has a probability distribution q_ij = [0.5, 0.4, 0.1]. After normalizing q_ij by the maximum probability of 0.5, we can have $\bar{{\boldsymbol q}}_{ij} = [ {1, \;0.8, \;0.2} ]$. Secondly, $\bar{{\boldsymbol q}}_{ij}$ is sorted in a descending order to generate $\bar{{\boldsymbol q}}_{ij}^s = [ {1, \;\;0.8, \;\;0.2} ]$. The cluster rank is ${\bar{\boldsymbol {q}}^{\prime}}_{ij} = [ {1, \;\;2, \;\;3} ]$. Thirdly, the ideal centers for top 1-clustering, 2-clustering, and 3-clustering are l ₁ = [1, 0, 0], l ₂ = [1, 1, 0], and l ₃ = [1, 1, 1]. The sketch x _ij will be assigned to the top k-clustering if l _k (k = 1, 2, or 3) is the nearest ideal center for the sketch. After calculation, the Euclidean distance between $\bar{{\boldsymbol q}}_{ij}^s$ with l ₁, l ₂, and l ₃ are 0.82, 0.28, and 0.82, respectively. The possible number of clustering ${k}^{\prime}_{ij}$ is 2. It means the sketch x _ij will be assigned to the top 2-clustering of ${\bar{\boldsymbol {q}}^{\prime}}_{ij}$. The clustering labels c_ij = [1, 2]. x _ij is a multiple cluster point as it belongs to two clusters. Assume most top 1-clustering sketches in the category ω ₁ are assigned to cluster c ₁ and one category can be assigned to a unique cluster. Therefore, the ground truth cluster label of the category ω _i is 1. As c_ij includes cluster label 1, the type of x _ij is native-overlap (2). x _ij could be a point between category ω ₁ and ω ₂ in Figure 4. x _ij can be added to native-overlap point set NO _i and the weight $w_{c_2}^{ij} = 0.5$, which means the simialrity between cluster c ₁ and cluster c ₂ will be accumulated by 0.5 because of x _ij. For all skecthes in category ω ₁, we can accumulate all weight values and find the similarity between category ω ₁ with other categories. Take another example, there are only seven points in the category ω ₁. In a latent space including three clusters, the weights for these seven classified sketches in category ω ₁ are shown in Table 1.

Table 1.

Example of weights for four types points of category ω ₁ in a latent space including three clusters

From the weight column, we can sum the weights of clusters c ₂ and c ₃, which are $w_{c_2}^{{\rm sum}} = 7/3$, $w_{c_3}^{{\rm sum}} = 7/3$. The higher weight summation means higher shape similarity with cluster c ₁ which represents category ω ₁. In this case, clusters c ₂ and c ₃ have same similarity with cluster c ₁.

Dataset and settings

The sketch data categories used for evaluation are television, canoe, drill, umbrella, car, floor lamp, guitar, windmill, wine bottle, and flower. The 75 K sketches for each category are divided into training, validation, and testing sets with 70, 2.5, and 2.5 K, respectively. The raw sketches from the Quickdraw dataset are converted to monochrome png files of size 48 × 48, which are used as the input data for the deep neural network model. The batch size is 100 for all datasets. The maximum number of epochs is set to 50. In each iteration, we train the encoder for one epoch using an Adam optimizer with a learning rate λ = 0.001, β ₁ = 0.9, β ₂ = 0.999. We implement the model end-to-end based on Python and Keras. The dimension of the latent space in the models is 128, which is the same as those used in Chen et al. (Reference Chen, Tu, Yi and Xu2017) and Ha and Eck (Reference Ha and Eck2017). For training the dc-sketch-pix2seq model, the coefficient τ of clustering loss in (5) is chosen as 0.05, which is determined by a grid search in {0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0} to evaluate different τ settings with unsupervised clustering accuracy (ACC). The ACC is defined as the best match between ground truth y and predicted cluster labels c:

(10)$${\rm ACC}( {{\boldsymbol y}, \;{\boldsymbol c}} ) = \mathop {\max }\limits_{m\in {\cal M}} \displaystyle{{\mathop \sum \nolimits_{i = 1}^n 1{ {y_i = m( {c_i} ) } } } \over n},$$

where n is the total number of samples, y _i is the ground truth label, c _i is the predicted cluster label of the example x _i obtained by the model, and ${\cal M}$ is the set of all possible one-to-one mappings between predicted cluster labels to ground truth cluster. The best cluster assignment can be efficiently computed by the Hungarian algorithm (Kuhn, Reference Kuhn1955). In Figure 5, when τ = 0.05, the dc-sketch-pix2seq model has the best clustering performance under the given value settings.

Fig. 5.

ACC values under different τ value settings.

A visualization of the learned features

The dimensionality reduction technique t-SNE (t-Distributed Stochastic Neighbor Embedding) (Maaten and Hinton, Reference Maaten and Hinton2008) is applied to present a visualization of the learned latent space of 10 categories by projecting 128 dimensions to 2 dimensions. As shown in Figure 6, different color dots denote the sketches from different categories. Sketches in the same category are clustered in close proximity. The illustration in Figure 6 affirms our assumption that sketches in the same group have similar shape features and they are more likely clustered in the same group.

Fig. 6.

Visualization of the latent space of 10 categories and different types of sketches.

The overlap regions between different categories make it possible to find out the sharing shape features. In Figure 7, each category has 2,500 sketches. Most sketches of each category are native sketches with 0 overlaps with other categories, except for the windmill in the center of the latent space in Figure 6. This means windmill can have more “interactions” with other categories. For most categories, the numbers of sketches having overlaps with more than three categories are all below 250%, 10% of the total sketches in each category. In the section “Visual similarity quantification and rank”, we consider the overlap within at most n (1 ≤ n ≤9) categories to calculate the weights in the top clustering detection-based method. However, in Figure 6, we only consider the overlap within at most three categories to show that sketches in different regions from the same category can have slightly different shapes. Take the “television” category as an example. As shown in Figure 6, t ₁ is a native point. It means t ₁ can represent the most frequently drawn television sketch by users. It includes two rectangles to present the monitor and two intersected lines to present an antenna. t ₂, t ₃, and t ₄ are native-overlap (2) points. t ₂ is in the overlap region of car and television. It has a long thin rectangle which is like the body of a car. t ₃ is in the overlap region of windmill and television. It has an antenna that can be regarded as blades and a base stand which can be regarded as the body of a windmill. t ₄ is in the overlap region of wine bottle and television. It has a long tall shape which is like the appearance of a wine bottle. t ₅ is a native-overlap (3) point. It is in the overlap region of car, television, and windmill. It has a base stand and a long thin rectangle. t ₆ is a departed point. It is “mistakenly” clustered in the car category and not overlapped with other categories. It has two circles which are like two wheels and a long thin rectangle that is like the body of a car. t ₆ has more shape features of a car than t ₂. t ₇ is a departed-overlap (2) point. It is “mistakenly” clustered in the car category and overlapped with canoe category. For t ₆ and t ₇, it is not so obvious to see they belong to television sketches.

Fig. 7.

Sketch number distributions on different overlap numbers for 10 categories.

Drill and guitar are separated into several subgroups and located in different areas in the latent space. After retrieving sketches, we can find, for drill, one major cluster can represent handheld drill, another can represent ground drill; For guitar, one major cluster is acoustic, and another major is electric. Other clusters from these two categories have multiple orientations and slight shape modifications. This shows rotation and shape change can affect the results of clustering. Since windmills and flowers share too many shape features, they are merged into each other. In the clockwise or anti-clockwise direction, we can see the shape is gradually changing across different categories. The localization of sketch categories in the latent space suggests that the learned features are very useful for both within-category and cross-category sketch retrievals. Categories with higher visual similarity have shorter distances. The visual similarity should be quantified before we can effectively retrieve sketches.

Visual similarity quantification and rank

In the latent space, when the categories are densely clustered, such as canoe and car, it is easy to use Euclidean distance to measure the similarity between them. However, when categories are mixed together, such as windmill and flower, or separated as several subgroups, such as drill and guitar, Euclidean distance may not be accurate enough. In this section, we compare the proposed top clustering detection (TCD) method with the Euclidean distance-based method to measure the visual similarity between different categories. Let s _ij present the similarity between category i and j based on Euclidean distance, which can be computed as follows (Karimi et al., Reference Karimi, Maher, Davis and Grace2019):

(11)$$s_{ij} = 1-\displaystyle{{d_{ij}} \over {\mathop {\max }\limits_j d_{ij}}},$$

where d _ij is the Euclidean distance between category i and j, and $\mathop {\max }\limits_j d_{ij}$ is the longest Euclidean distance from category i to other categories.

Figure 8 visualizes the similarity matrix for 10 categories; the size of a square means the value of similarity. A larger square means a higher similarity value. For each row, it represents the similarity magnitude of other categories to the row category. It is not easy to find the largest square immediately. It means similarity magnitude is not so differentiable for each category as the several distances are so close. For categories that are separated into some subgroups, such as drill and guitar, using Euclidean distance may not be accurate. Drill is more similar to car than umbrella as its centroid is closer to that of the cars. After checking the sketches, umbrella should be more visually similar to drill. Many points of guitar are merged into the wine bottle cluster. However, the similarity value of guitar to wine bottle is low as the centroid distance between them is large.

Fig. 8.

Similarity matrix based on Euclidean distance.

Figure 9 visualizes the similarity between different categories based on our top clustering detection method with different overlap values. Overlap value means the largest number of categories one category can have overlaps with when calculating similarity based on the TCD method. For example, if the overlap value equals 1, it means one category is inclined to build a similarity relationship with the nearest one category in the latent space. In Figure 9, when the overlap value becomes larger, it is easier to see that one category has more chance to build similarity relationships with more categories. For example, when the overlap value is 1, we can only find at most one category that is similar to it for each category. When the overlap value is 3 or 8, we can easily find several categories that are similar to it for each category. The reason is when using the TCD method to calculate the similarity values between one category to other categories, the sketches in the overlap regions with more categories are counted when the overlap value becomes larger. How to choose the optimal overlap value is a tradeoff. We need to consider how many visually similar or dissimilar categories should be retrieved and present to the users. If setting the overlap value to a small number, users may miss some important visual similarity information. If setting the overlap value to a large number, the user may be provided too much visual similarity information to filter some significant ones.

Fig. 9.

Similarity matrix based on TCD with different overlap values.

In Figure 9, the categories are arranged in the same order as shown in Figure 8 to aid comparison. From Figure 9, it is easier to figure out the visual similarity relationship between different categories than in Figure 8, as every point in the latent space contributes to computing the similarity rather than measuring the distance of the centroids. Take Figure 9(b) as an example to compare with Figure 8. For dense clusters with few overlapped regions with other categories, such as canoe, car, television, floor lamp, and umbrella, two methods have similar rankings for each category. However, for categories that are separated in the latent space, such as drill and guitar, the top clustering detection-based method is more reasonable for the similarity ranking. The distance between drill and windmill is shorter than drill and guitar. Guitar is ranked higher than windmill, which is more reasonable as more points of guitar mixed with drill. There is one subgroup of guitar which is separated away from other subgroups and merges with wine bottle. The centroid of guitar cannot accurately reflect the locations of some sketches in the latent space. Drill has the shortest Euclidean distance category from guitar. However, wine bottle has the largest overlapped region with it. Based on our method, wine bottle is the most similar category to guitar. Canoe has the longest distance from guitar. However, it has the second-largest overlapped region with guitar. Therefore, it is the second similar category in our method and last similar category based on Euclidean distance. Also, the most similar category to wine bottle is guitar rather than the shortest distance category floor lamp. Finally, for each category, the visual similarity rank can be obtained and stores in a database.

Within-category and cross-category retrieval

The retrieval performance of our proposed method is evaluated by top-k retrieval accuracy with majority hits. The k represents the number of nearest neighbors of the query in the latent space. The majority hits mean more than half of k nearest neighbors having exactly the same category label as the query. In the experiment for evaluating the retrieval performance, the label of a query is known beforehand. The criteria to evaluate whether a model has a good retrieval performance is the retrieval accuracy rate which equals the number of successful major hits over the total number of the sample data. The retrieval accuracy rate can reflect the shape feature extraction and clustering performance of the model. In Figure 10(a), the query label is blue, and the major label of the 5 nearest neighbors is also blue. Therefore, it is a successful retrieval with major hits. In Figure 10(b), the query label is blue, and the major label of the 5 nearest neighbors is also green. Therefore, it is an unsuccessful retrieval with major hits, meaning that this query is more visually similar to the green cluster.

Fig. 10.

The successful and unsuccessful retrieval with 5 nearest neighbors in the latent space.

We randomly sampled 10 K sketches from each category as queries. These sketches are from the Quickdraw dataset and are not used in training our model. The top-k retrieval accuracy at different k with different hits is plotted in Figure 11. The retrieval accuracy rate can reflect the density of each category in the latent space. For example, as car is the densest category in Figure 6, it has the highest top-k retrieval accuracy rate with different k values. As windmill is the loosest category in Figure 6, it has the lowest top-k retrieval accuracy rate with different k values. In general, the top-5 retrieval accuracy rate is nearly the highest for all 10 categories. Therefore, we choose 5 nearest neighbors of the query and determine which category the query is most visually similar to.

Fig. 11.

The top-k retrieval accuracy with majority hits of each category.

Our generated visual analogy database quantifies the visual similarity between different sketch categories and stores these visual relationships. In the visual stimuli searching and retrieving scenario, if designers would like to find short-distance and long-distance visual stimuli in our system, firstly, our systems need to know which category has the highest visual similarity with the query. Therefore, the major category label of the top 5 nearest neighbors of the query is determined. In this category, designers can most likely find short-distance visual analogies (e.g., images and category information). We call the major category label the assigned label. Also, based on the quantified visual relationships, our system can easily find long-distance visual analogies (e.g., images and category information) from several categories having low similarity with the assigned category. Ten retrieval experiments are done before deciding on the appropriately assigned label for the query. In Table 2, we show some examples of assigning labels to queries based on the top-5 retrievals. We choose five categories and list them in rows based on the top-5 retrieval accuracy in descending order. From Table 2, we can see categories with high top-5 retrieval accuracies, such as car, wine bottle, and television, have a higher possibility of being assigned correct (ground truth) labels than categories with low top-5 retrieval accuracy. The categories with higher retrieval accuracy imply they are more distinguishable from other categories.

Table 2.

Examples of assigned labels and top-5 retrievals for queries

Based on the assigned categories, we can retrieve sketches from within-category and cross-category, as shown in Table 3. For each category, all the points are classified into four different datasets. Given the assigned category label from Table 2, we can retrieve sketches from the four datasets of the assigned category and the most or least similar category of the assigned category based on the visual similarity rank. In Table 3, we randomly retrieve one sketch for each dataset; within-category is the assigned category of the query, and cross-category is the category that has the highest/lowest similarity with the assigned category. In Table 3, we only show sketches from cross-categories with the highest similarity.

Table 3.

Within-category and cross-category retrieval based on the assigned labels of queries

Note: N means native points, D means departed points, NO (2) means native-overlap points within two categories, DO (2) means departed-overlap points within two categories.

Finally, we check whether our model can retrieve similar sketches even if the categories of queries are not in the training dataset. These categories are called unseen categories. Here, we randomly select five unseen categories: a fan, screwdriver, parachute, radio, and roller skates. For each of them, we visualize the top-5 retrievals that are most similar to the unseen categories, as shown in Table 4. We can see that the top-5 retrievals are visually correlated with the sketches from unseen categories, and the generalization ability of our model can be very intuitive and explainable.

Table 4.

Top-5 most similar sketches to the queries from unseen categories