Patent ID: 12243135

DETAILED DESCRIPTION

Overview

Content processing systems are often tasked with imparting a unique style and customizations to vector objects included as part of digital content. The vector objects are defined mathematically (e.g., as a collection of Bezier curves) to include paths that are rendered for output, e.g., for display in a user interface, onto a physical medium, and so forth. In this way, vector objects are scalable without a loss in visual quality.

When editing vector objects, in some instances it is desirable to impart visual qualities from one vector object to another vector object, e.g., vector object morphing. However, conventional techniques to support such customizations are limited and challenging. For instance, conventional mesh based and/or raster based morphing techniques lose the underlying mathematical structure and cause these edits to forgo the advantages made possible by vector objects involving discrete path definition and arrangement. Further, conventional vector morphing techniques are constrained based on an initial arrangement of paths and thus have limited applications.

Accordingly, techniques and systems for vector object blending are described that overcome these challenges and limitations to generate customized vector objects by generating a transformed vector object based on visual characteristics of a source vector object and a target vector object (or multiple target vector objects). In this way, the techniques described herein enable the source vector object and the target vector object to be “blended together” to produce transformed vector objects that represent realistic intermediates with visual properties of both the source vector object and the target vector object.

In an example, a computing device implements a transformation system to receive input data describing a first vector object, e.g., a source vector object, and a second vector object, e.g., a target vector object. The first vector object includes a plurality of first paths, and the second vector object includes a plurality of second paths. In various examples, the first paths and/or the second paths include one or more path groups, e.g., simple groups that organize the paths to structure the first or second vector object, or complex groups such as compound paths and/or clipping groups. The complex groups, for instance, impart specific functionality and define visual effects for the vector objects.

In some examples, the transformation system is operable to generate blendable hierarchies from the first vector object and the second vector object. Generally, the blendable hierarchies organize paths of a same path group (e.g., simple groups, clipping groups, compound paths, etc.) such that path groups from the first vector object are matchable with alike path groups from the second vector object. The transformation system is thus operable to match paths of simple groups from the first vector object with paths of simple groups from the second vector object, and paths of complex groups from the first vector object with paths of complex groups from the second vector object such that the paths are blendable in accordance with the techniques described below. In this way, the transformation system ensures that the complex groups retain their underlying functionality and/or visual effects in a subsequently generated transformed vector object.

In order to generate a transformed vector object that includes visual features of both the first vector object and the second vector object, the transformation system is employed to generate path pairs that include one of the first paths and one of the second paths. Path pairs with a high level of correspondence between the first path and the second path have a low cost, while path pairs with a low level of correspondence have a high cost. High-cost path pairs have a propensity to cause visual artifacts in a subsequently generated transformed vector object.

Accordingly, the transformation system is operable to compute morphing costs based on a correspondence within a plurality of candidate path pairs. A candidate path pair includes one of the first paths and one of the second paths, and in an example, candidate path pairs are generated for each possible combination of path pairs between the first paths and the second paths. In some implementations, the morphing costs quantify a variety of correspondences within a candidate path pair, such as one or more of a spatial displacement, a volumetric proximity, and/or a geometric concurrence. Thus, morphing costs include one or more of a spatial cost, a volumetric cost, and/or a geometric cost that describe such correspondences.

Based on the morphing costs, the transformation system is operable to generate a mapping of paths between the plurality of first paths and the plurality of second paths. Generally, the mapping of paths represents a plurality of path pairs that minimizes the overall morphing costs, and thus improves the visual quality of the subsequently generated transformed vector object. In one example, the transformation system is operable to leverage a pairing algorithm that is configured to receive as input the morphing costs to generate the mapping of paths.

For instance, the morphing costs (e.g., the geometric costs, spatial costs, and volumetric costs as described above) are normalized, weighted, and consolidated into a cost matrix. Continuing with this example, the pairing algorithm is a Hungarian pairing algorithm that receives the cost matrix as input and generates least cost path pairs between the first paths and the second paths. The transformation system is further operable to suppress high-cost pairings that are above a cost threshold, as well as generate path pairs for any unmatched paths by generating one or more artificial paths.

Based on the mapping, the transformation system is operable to generate a transformed vector object, e.g., as a transformation of the first vector object, by adjusting a property of at least one of the first paths. In an example, the properties include one or more of a geometry (e.g., shape, orientation, size, etc.), appearance (e.g., color, gradient, fill, etc.), and/or z-order (e.g., overlap order of constituent entities) of the at least one first path and generating the transformed vector object includes linearly interpolating one or more of these properties. In some implementations, linearly interpolating the z-order includes employing a z-order crossfading scheme to control an z-order migration of a path. In this way, the techniques described herein enable various properties of a first vector object and a second vector object to be blended to produce transformed vector objects that represent realistic intermediates with visual properties of both the first vector object and the second vector object.

In the following discussion, an example environment is first described that employs examples of techniques described herein. Example procedures are also described which are performable in the example environment and other environments. Consequently, performance of the example procedures is not limited to the example environment and the example environment is not limited to performance of the example procedures.

Example Environment

FIG.1is an illustration of a digital medium environment100in an example implementation that is operable to employ the vector object blending techniques described herein. The illustrated environment100includes a computing device102, which is configurable in a variety of ways.

The computing device102, for instance, is configurable as a desktop computer, a laptop computer, a mobile device (e.g., assuming a handheld configuration such as a tablet or mobile phone as illustrated), one or more processing devices and so forth. Thus, the computing device102ranges from full resource devices with substantial memory and processor resources (e.g., personal computers, game consoles) to a low-resource device with limited memory and/or processing resources (e.g., mobile devices). Additionally, although a single computing device102is shown, the computing device102is also representative of a plurality of different devices, such as multiple servers utilized by a business to perform operations “over the cloud” as described inFIG.11.

The computing device102is illustrated as including a content processing system104. The content processing system104is implemented at least partially in hardware of the computing device102to process and transform digital content106, which is illustrated as maintained in storage108of the computing device102. Such processing includes creation of the digital content106, modification of the digital content106, and rendering of the digital content106in a user interface110for output, e.g., by a display device112. Although illustrated as implemented locally at the computing device102, functionality of the content processing system104is also configurable as whole or part via functionality available via the network114, such as part of a web service or “in the cloud.”

An example of functionality incorporated by the content processing system104to process the digital content106is illustrated as a transformation module116. The transformation module116is configured to generate a transformed vector object118(e.g., as a transformation of a source vector object) based on visual characteristics of the source vector object and a target vector object automatically and without user intervention, and thus increase creative customization capabilities while maintaining functionality of a mathematical representation. For instance, in the illustrated example the transformation module116receives input data120including a first vector object122, e.g., a source vector object, and a second vector object124, e.g., a target vector object. In this example, the first vector object122depicts a brown cow and the second vector object124depicts a black and white spotted cow that has horns.

The first vector object122includes a plurality of first paths and the second vector object124include a plurality of second paths. The transformation module116is operable to generate a mapping of paths between the first vector object122and the second vector object124. Generally, the transformation module116generates the mapping of paths to minimize an overall morphing cost. As further described below, the transformation module116is operable to compute a variety of morphing costs in a variety of ways to minimize the overall morphing cost. By minimizing morphing costs, the techniques described herein enable generation of transformed vector objects118that depict recognizable intermediates between the first vector object122and the second vector object124while also enhancing computational efficiency.

Based on the mapping of paths, the transformation module116generates the transformed vector object118by adjusting a property of one or more paths of the first vector object122. In the illustrated example, the transformation module116adjusts the geometry, appearance, and z-order of a plurality of paths from the first vector object122, e.g., by linearly interpolating these properties based on the mapping of paths. In the illustrated example, a continuum126is rendered for display, and includes several examples of transformed vector objects118with varying levels of influence of visual characteristics of the brown cow and the spotted cow.

For instance, the leftmost vector object in the continuum126includes visual properties similar to the brown cow, while the rightmost vector object appears similar to the spotted cow. Accordingly, an example transformed vector object118denoted by a black box shares visual properties of both the brown cow and the spotted cow, e.g., has a color in between brown and white, has a body shape that shares attributes of the brown cow and the spotted cow, has some small black spots, and has small horns. In this way, the techniques described herein overcome the limitations of conventional techniques by enabling creative customization of vector objects based on visual characteristics of multiple vector objects, while maintaining functionality of a mathematical representation associated with vector output. Further discussion of these and other techniques are included in the following section and shown using corresponding figures.

Vector Object Blending

FIG.2depicts a system200in an example implementation showing operation of a transformation module116.FIG.3depicts an example300of vector object blending illustrating functionality of an extraction module to generate blendable hierarchies.FIG.4depicts an example400of vector object blending illustrating generation of transformed vector objects including compound paths.FIG.5depicts an example500of vector object blending illustrating generation of transformed vector objects including clipping groups.FIGS.6aand6bdepicts an example600a,600bof vector object blending illustrating advantages of using neighborhood enriched dynamic time warping.FIG.7depicts an example700of vector object blending illustrating advantages of using high-cost outlier suppression.FIG.8depicts an example800of vector object blending illustrating advantages of using z-order cross-fading.FIG.9depicts an example900of vector object blending to generate a plurality of transformed vector objects.FIG.10depicts a procedure1000in an example implementation of vector object blending.

The following discussion describes techniques that are implementable utilizing the previously described systems and devices. Aspects of each of the procedures are implemented in hardware, firmware, software, or a combination thereof. The procedures are shown as a set of blocks that specify operations performed by one or more devices and are not necessarily limited to the orders shown for performing the operations by the respective blocks. In portions of the following discussion, reference will be made toFIGS.1-10.

Generating Blendable Hierarchies

To begin in this example, a transformation module116receives input data120that describes a first vector object122and a second vector object124(block1002). The first vector object122includes a plurality of first paths, and the second vector object124includes a plurality of second paths. In various examples, the paths of the first vector object122and/or the second vector object124are organized into one or more path groups including simple groups and/or complex groups such as compound paths, and/or clipping groups. This is by way of example and not limitation, and a variety of additional path groups are considered as well.

Generally, a simple group provides meaningful organization to a number of paths, for instance to organize the paths in a particular geometric configuration. A compound path is usable to control fill regions of grouped entities (e.g., lines, shapes, bodies, etc.) by implementing rules such as even-odd filling and/or non-zero winding. Clipping groups are implemented to customize the geometry of constituent entities of a vector object and are further usable to occlude or stencil the constituent entities in various regions of the vector object. Accordingly, the path groups include functionality that define a variety of visual effects for vector objects. In some examples, the first vector object122and/or the second vector object124include groups of groups, e.g., groups that are “nested” within one or more other groups. Conventional techniques fail to provide consideration for complex groups, and thus are unable to include functionality of path groups in morphed vector objects.

To address these limitations, in some examples the transformation module116includes an extraction module202that is operable to generate one or more blendable hierarchies204from the first vector object122and one or more corresponding blendable hierarchies204from the second vector object124. Generally, the blendable hierarchies204organize paths of the same path group (e.g., simple groups, clipping groups, compound paths) such that path groups of the first vector object122are matchable with alike path groups of the second vector object124. Thus, simple groups of the first vector object122are matched with simple groups of the second vector object124, compound paths of the first vector object122are matched with compound paths of the second vector object124, and clipping groups of the first vector object122are matched with clipping groups of the second vector object124.

In an example, complex groups are matched based on correspondence between key paths of the complex groups. For instance, a largest and topmost path is a key path for a compound path, and a path that clips other paths is a key path for a clipping group. The key paths of the complex groups are matched using the cost computation and mapping techniques further described below, e.g., using a pairing algorithm to find a least cost mapping of the key paths. The transformation module116is then operable to individually process the matched path groups in accordance with the techniques described below, and subsequently reassemble the path groups as part of generating the transformed vector object118. In this way, the transformation system ensures that the transformed vector object118includes the functionality and visual effects imparted by the complex groups.

Example operations of the extraction module202are illustrated in an example300ofFIG.3in a first stage302and a second stage304. As shown in first stage302, an example of a first vector object122, e.g., a “source art”, depicts circular features, and an example of a second vector object124, e.g., a “target art”, depicts rectangular features. The second stage304depicts a representation306of path groups that define the first vector object122and the second vector object124. As illustrated, the first vector object122includes two simple groups such as a first circle308and a second circle310. The first vector object122also includes a first clipping group312that includes an ellipse314, a first circular compound path316, and a second circular compound path318. Similarly, the second vector object124includes two simple groups such as a first rectangle320and a second rectangle322. The second vector object124also includes a second clipping group324that includes a third rectangle326, a first rectangular compound path328, and a second rectangular compound path330.

Based on the groups of paths, the extraction module202is operable to generate two top-level blendable hierarchies for the first vector object122. For instance, the extraction module202generates a first simple blendable hierarchy332that includes the simple groups such as the first circle308and the second circle310. The extraction module202also generates a first complex blendable hierarchy334that includes the complex groups, e.g., the first clipping group312. Similarly, the extraction module202generates corresponding blendable hierarchies204for the second vector object124. For instance, a second simple blendable hierarchy336includes the simple groups, e.g., the first rectangle320and the second rectangle322. A second complex blendable hierarchy338includes the complex groups, e.g., the second clipping group324. The extraction module202is further operable to repeat the process of generating blendable hierarchies204for nested path groups, such as the compound paths316,318,328, and330in this example.

Based on the blendable hierarchies204, the transformation module116is operable to individually process the path groups one-by-one in accordance with the techniques as described in more detail below. For instance, continuing the above example, paths of the first simple blendable hierarchy332are matched with paths of the second simple blendable hierarchy336. Similarly, paths of the first complex blendable hierarchy334are matched with paths of the second complex blendable hierarchy338.

In this way, paths from simple groups of the first vector object122are matched with paths from simple groups of the second vector object124, compound paths of the first vector object122are matched to compound paths of the second vector object124, and clipping groups of the first vector object122are matched to clipping groups of the second vector object124. The transformation module116is thus operable to separately process paths according to path groups and subsequently reassemble them as further described below. In this way, the techniques described herein support inclusion of complex groups such as clipping groups and compound paths in a subsequently generated transformed vector object118without a loss in visual quality or underlying functionality of the path groups.

An example400of this functionality is depicted inFIG.4in a first stage402, a second stage404, and a third stage406. In this example, as shown in the first stage402, a first vector object122depicts a first key408with three prongs and a circular head. A second vector object124depicts a second key410with two prongs, and an stylized, ovaloid head shape. Further, the first key408and the second key410include a plurality of compound paths. Second stage404depicts a continuum412that represents attempted blending of the first key408and the second key410without providing consideration for the complex groups, e.g., the compound paths. Consequently, vector objects included in the continuum412contain visual artifacts and do not depict realistic intermediates. For instance, a vector object414depicts an amorphous, poorly defined shape that is not identifiable as a key.

In contrast, third stage406depicts a continuum416that represents blending the first key408with the second key410in accordance with the techniques described herein. This includes leveraging the extraction module202to generate blendable hierarchies204, in conjunction with the techniques as further described below. Based on the blendable hierarchies, the transformation module116is operable to retain the functionality and visual effects of the plurality of compound paths included in the first key408and the second key410. Accordingly, a subsequently generated transformed vector object118, e.g., a third key418, is artifact free and is of superior visual quality when compared with the limitations depicted in second stage404.

A further example500of this functionality is depicted inFIG.5in a first stage502, a second stage504, and a third stage506. In this example, as shown in the first stage502, a first vector object122depicts a cherry cupcake508and a second vector object124depicts a blueberry cupcake510. In this example, the cherry cupcake508and the blueberry cupcake510include a plurality of clipping groups. Second stage504depicts a continuum512that represents attempted blending of the cherry cupcake508and the blueberry cupcake510without accommodation for the complex groups, e.g., the clipping groups. Consequently, the vector objects included in the continuum512include visual artifacts and do not depict realistic intermediates between the cherry cupcake508and the blueberry cupcake510.

In contrast, third stage506depicts a continuum514that represents blending the cherry cupcake508with the blueberry cupcake510in accordance with the techniques described herein, for instance leveraging the extraction module202to generate blendable hierarchies204. Based on the blendable hierarchies204, the transformation module116is operable to retain the functionality and visual effects of the plurality of clipping groups included in the first vector object122(e.g., the cherry cupcake508) and the second vector object124(e.g., the blueberry cupcake510). Accordingly, the transformed vector objects118included in the continuum514are artifact free and represent usable intermediates which overcomes the limitations depicted in second stage504.

Morphing Cost Computation

Continuing the discussion on how to generate the transformed vector object118, the transformation module116is employed to generate path pairs that include one of the first paths (e.g., a path from the first vector object122) and one of the second paths, e.g., a path from the second vector object124. As discussed above, in examples in which the first vector object122and second vector object124include one or more path groups (e.g., simple groups, clipping groups, compound paths, etc.) path pairs are generated between analogous path groups according to the one or more blendable hierarchies204. Further, to augment the visual quality of the transformed vector object118, an objective in generating the path pairs is to reduce a cost to blend the paths of the path pairs, i.e., morphing costs208.

Accordingly, the transformation module116includes a cost module206that is operable to compute morphing costs208based on a correspondence within candidate path pairs that include one of the first paths and one of the second paths (block1004). The candidate path pairs include one of the first paths from the first vector object122and one of the second paths from the second vector object124. In an example, candidate path pairs are generated for each possible combination of path pairs between the first paths and the second paths. The cost module206is operable to determine the correspondence based on a variety of factors such as a spatial correspondence, a volumetric correspondence, and/or a geometric correspondence. Accordingly, in various implementations, the morphing costs208include one or more of a spatial cost210, a volumetric cost212, and/or a geometric cost214that describe such correspondences.

For instance, the cost module206is operable to determine a spatial cost210that indicates a cost of spatial displacement to blend one of the first paths with one of the second paths. Consider an example candidate path pair that includes one of the first paths and one of the second paths. To calculate the spatial cost210for the example candidate path pair, the cost module206computes a first offset distance of the first path from a center of the first vector object122. The cost module206also computes a second offset distance of the second path from a center of the second vector object124. The cost module206then computes the difference between the first offset distance and the second offset distance to determine the spatial cost210. In some examples, the spatial cost210represents a two-dimensional measure that includes two cost metrics, e.g., an “x” and a “y” spatial cost for each Cartesian axis. In an alternative or additional example, multiple dimensions of the spatial cost210are integrated into a single metric. Minimization of the spatial cost (e.g., as part of generating a mapping as discussed below) prevents unnecessary path migration during blending.

The cost module206is also operable to generate a volumetric cost212that enables path pairs to include similarly sized paths. Consider the example candidate path pair that includes a first path and a second path as described above. To calculate the volumetric cost212, the cost module206computes a horizontal span and a vertical span for the first path and for the second path. The cost module206calculates a difference between the horizontal span of the first path and the horizontal span of the second path, as well as a difference between the vertical span of the first path and the vertical span of the second path. The differences between these spans represent the volumetric cost212.

In some examples, the volumetric cost212includes two cost metrics, e.g., one for horizontal span and one for vertical span. In an alternative or additional example, the volumetric cost212is integrated into a single metric. In various implementations, the volumetric cost212has a greater impact on visual properties associated with blending. That is, relatively slight discrepancies in horizontal/vertical span between the first path and second path result in visual artifacts. Accordingly, in some examples, the volumetric cost212is penalized on a logarithmic scale to reduce such volumetric discrepancies. In this way, the techniques described herein prevent large objects from blending to small objects and vice versa during subsequent blending.

The cost module206is also operable to compute a geometric cost214that indicates a geometric concurrence between the first path and the second path of the candidate path pair, e.g., an “edit distance” between a geometry of the first path and a geometry of the second path. To calculate the geometric cost214, the cost module206leverages a neighborhood enriched dynamic time warping (“DTW”) to compute a distance between the first path and the second path as a measure for the geometric cost214. DTW provides a mechanism to compare two temporal series of possibly unequal lengths and finds an optimal mapping of each of the sampled points between terminal points (i.e., start and end points) of the series.

To calculate the geometric cost214for an example candidate path pair, the cost module206first normalizes the first path and second path to account for possible rotations of the first path and/or the second path. In one embodiment, Principal Component Analysis (“PCA”) using bounding ellipsoids of paths and Procrustes analysis is used to normalize the input paths for rotation, for instance as described by Ross, et. al. Procrustes analysis. Depaitment of Computer Science and Engineering, University of South Carolina, SC 29208. The cost module206is also operable to convert the first path and second path to an input series, e.g., a series of points, that are able to be analyzed using DTW.

Further, the cost module206enriches the input series with regional (e.g., locality) information. For instance, the cost module206defines a neighborhood of size “n.” The cost module206is thus operable to consider the influence of n/2 points to the left and n/2 points to the right of each point in the input series, e.g., as an average of x and y gradient values in the neighborhood n. In this way, the techniques described herein accommodate for pronounced regional changes associated with blending complex vector objects. Accordingly, the cost module206leverages neighborhood enriched DTW to find the geometric cost214between control points of the first path and the second path to reduce an amount that the geometry of a particular path changes unnecessarily during blending.

Examples600a,600billustrate advantages of neighborhood enriched DTW compared to conventional DTW as shown inFIGS.6a,6bin a first stage602, a second stage604, a third stage606, and a fourth stage608. For instance,FIG.6adepicts an example of conventional DTW that does not use the neighborhood enrichment techniques as described herein. An example candidate path pair includes a first path from a first vector object122that depicts a forearm of a first arm610and a second path from a second vector object124that depicts a second arm612including a bicep and a forearm.

As depicted in first stage602, the first path is shown at614and the second path is shown at616in an example conventional DTW mapping. Point mappings of the first path to the second path are depicted by the lines in between the first path614and the second path616. Notably, conventional DTW fails to capture significant regional variations between the first vector object122and the second vector object124, e.g., a significant regional difference in the upper arm area between the first arm610and the second arm612, and thus the mapping lines are disjointed and irregular.

Accordingly, as depicted in second stage604, an attempt to blend the first arm610and the second arm612based on conventional DTW techniques results in generation of a vector object618with significant visual artifacts. For instance, the pink lines denote point mappings of the first arm to the second arm. Notably, several anchor mappings connect a thumb of the first arm610to a bicep region of the second arm612. Thus, the attempted blending causes the thumb to be “pulled back” to the bicep region and the vector object618is not recognizable as an arm.

In contrast,FIG.6bdepicts an example implementation of neighborhood enriched DTW. In this example, as depicted in third stage606, the first path is shown at620and the second path is shown at622. By considering regional information, the neighborhood enriched DTW considers the significant regional difference in the upper arm area between the first arm610and the second arm612. Accordingly, the mapping lines between the first path and second path are relatively parallel compared to the mapping lines depicted in first stage602. Further, as shown in fourth stage608, the mappings between the first arm610and second arm612are also relatively parallel and match similar regions of the first arm610to similar regions of the second arm612. Thus, generating a transformed vector object118based on the first arm610and the second arm612in accordance with the techniques described herein, for instance utilizing neighborhood enriched DTW to compute morphing costs208, results in reduced incidence of visual artifacts. Accordingly, the transformed vector object depicted at624is recognizable as an arm and is superior in visual quality to the vector object618.

Generating a Mapping of Paths

Once the morphing costs208are computed by the cost module206, a mapping module216is operable to generate a mapping of paths218between the plurality of first paths and the plurality of second paths based on the morphing costs208(block1006). Generally, the mapping of paths218represents a plurality of path pairs that minimizes the overall morphing costs208, and thus improves the visual quality of the transformed vector object118in subsequent blending, i.e., generation of the transformed vector object118. In various examples, the morphing costs208are configured as a cost matrix that includes the spatial cost210, volumetric cost212, and geometric cost214for each candidate path pair.

For example, the mapping module216generates the cost matrix as an n*m matrix, where n is the number of first paths and m is the number of second paths. The mapping module216is operable to normalize the costs using min-max normalization to remap the morphing costs208to a common range, e.g., a [0-1] range. In an example, the mapping module216computes an overall cost for a candidate path pair “if” where “i” is a first path and “j” is a second path according to the following formula:
Cij=0.2*∥Gij∥+0.22∥Sx,ij∥+0.22*∥Sy,ij∥+0.18*∥Vx,ij∥+0.18*∥Vy,ij∥

In this example, “Cij” represents an overall cost for the candidate path pair ij. “G” represents the geometric cost214, “S” represents the spatial cost210, and “V” represents the volumetric cost212. In this example, the spatial cost210includes two cost metrics, e.g., “Sx” represents spatial cost along an x-axis and “Sy” represents a spatial cost along a y-axis. Similarly, the volumetric cost212includes two cost metrics, for instance “Vx” represents a volumetric cost along an x-axis and “Vy” represents a volumetric cost along a y-axis. The “∥ ∥” represents the min-max normalization to remap the morphing costs to a [0-1] range. The numerical values represent respective weights, and in this example are configured to minimize the overall cost and reduce incidence of visual artifacts. However, this is by way of example and not limitation and the weights are adjustable. In one example, the weights for the spatial cost210, volumetric cost212, and geometric cost214are adjusted based on a user input, e.g., via the user interface110using one or more sliders, buttons, text inputs, etc. In this way, a user of the computing device102is able to control influence of individual costs that impact the visual appearance of a subsequently generated transformed vector object118.

In an embodiment, the mapping module216leverages a pairing algorithm220that is configured to receive as input the morphing costs208to generate the mapping of paths218. In an example, the pairing algorithm220is a Hungarian pairing algorithm, such as a Hungarian pairing algorithm described by Harold W. Kuhn.The Hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955. The pairing algorithm220receives as input the cost matrix as described above and generates low cost path pairs that include a first path and a second path. In this way, the mapping module216enables generation of a mapping of paths218that minimizes the overall cost, and further is independent of the initial arrangement of the first paths and second paths. This overcomes the limitations of conventional techniques, which are limited by the initial arrangement of paths.

As mentioned above, in examples in which the first vector object122and/or second vector object124include complex groups such as clipping groups and compound paths, the mapping module216is operable to generate the mapping of paths218based on key paths of the complex groups. In one example, the mapping module216is configured to ensure that key paths of analogous complex groups are paired with one another, for instance not with paths of other groups, by setting a morphing cost208for key path pairs to zero before inputting the cost matrix to the pairing algorithm220. In this way, the mapping module216is configured to ensure key paths of complex groups are matched with one another, and thus preserve functionality of the complex groups when generating the mapping of paths218.

As part of generating the mapping of paths218, in some examples the mapping module216includes a filter module222that is operable to suppress high-cost outlier pairings, e.g., path pairs generated by the pairing algorithm220that have a high cost. High-cost path pairs have a propensity to cause visual artifacts in a subsequently generated transformed vector object118. Accordingly, path pairs are suppressed if they are over a threshold cost value for one or more of the spatial cost210, volumetric cost212, geometric cost214, and/or an overall cost. Thus, the quality of the resultant transformed vector object118is improved by filtering out path pairs with a high cost that would likely result in visual artifacts.

In an example, the filter module222suppresses a path pair “if” where “i” is a first path and “f” is a second path according to the following criteria:
Sij=∥Cij∥>Z∥C∥1.7and (∥Gij∥>Z∥C∥1.8or
∥Sx,ij∥>Z∥Sx∥1.8or ∥Sy,ij∥<Z∥Sy∥1.8or
∥Vx,ij∥>Z∥Vx∥1.8or ∥Vy,ij∥>Z∥Vy∥1.8)

In this example, Sijis a boolean value that if “true” the path pair ij is suppressed and if “false” the path pair ij is not suppressed. Similar to the above example, “G” represents the geometric cost214, “S” represents the spatial cost210, and “V” represents the volumetric cost212. “Sx” represents spatial cost along an x-axis, “Sy” represents a spatial cost along a y-axis, “Vx” represents a volumetric cost along the x-axis, and “Vy” represents a volumetric cost along the y-axis.

“Z” represents a z-score, such that a z-score of x is defined as x*σ away from a mean cost, with σ being the standard deviation of the dataset. For instance, Z∥C∥1.7represents a z-score of 1.7 for normalized overall cost Cij∀i,j. Accordingly, in an example if the overall morphing cost208has a greater z-score than 1.7, and if one or more of the spatial cost210, volumetric cost212, or geometric cost214have a z-score greater than 1.8, the path pair ij is rejected, and not included as part of the mapping of paths218. This is by way of example and not limitation, and the values for z-scores vary in other implementations.

An example700of the advantages of filtering high-cost outliers is depicted inFIG.7in a first stage702, a second stage704, and a third stage706. In this example, as shown in the first stage702, a first vector object122depicts a cat708and a second vector object124depicts a dog710. Second stage704depicts a continuum712that represents attempted blending of the first vector object122, e.g., the cat708, and the second vector object124, e.g., the dog710, without suppressing high-cost outliers. Consequently, vector objects included in a continuum712include visual artifacts and do not depict realistic intermediates. For instance, as depicted by the vector object714, whiskers from the cat708are blending with ears from the dog710.

In contrast, third stage706depicts a continuum716that represents blending the first vector object122with the second vector object124in accordance with the techniques described herein. In this example, the filter module222suppresses high-cost outlier path pairs, e.g., path pairs including paths associated with the whiskers of the cat708and the ears of the dog710. Accordingly, subsequently generated transformed vector objects118are artifact free and are of superior visual quality when compared with the limitations depicted in second stage704.

In some examples, the mapping module216further includes a balance module224. Consider an example in which the first vector object122includes m number of paths and the second vector object124includes n number of paths. The pairing algorithm220is configured to generate a one-to-one mapping, and thus generates min(m,n) number of path pairs. Accordingly, if the first vector object122has less paths than the second vector object124, the second vector object124will have one or more unmatched paths after matching is performed using the pairing algorithm220. Likewise, if the second vector object124has less paths than the first vector object122, the first vector object122will have one or more unmatched paths. Further, in some instances suppression of high-cost path pairs by the filter module222creates one or more unmatched paths.

Accordingly, the balance module224is operable to process unmatched paths of the first vector object122and/or the second vector object124to create a one-to-one mapping for each path, such that the first paths and second paths are each part of a path pair including in the mapping of paths218. To do so, the balance module224is operable to identify one or more unmatched paths of the first paths and/or the second paths. The balance module224then generates one or more artificial paths to form path pairs with the previously unmatched paths. In some instances, the artificial paths include duplicate paths. In additional or alternative examples, the artificial paths include a singularity such as a degenerate single anchor path.

Consider an example in which one of the first paths is an unmatched path. The balance module224is operable to determine whether or not there exists a second path that is a candidate for duplication. To do so, the balance module224computes morphing costs208to match the first path with each of the second paths in accordance with the techniques described above, even if the second path is already part of a path pair. If the morphing costs208to match the first path with a particular second path are below the z-score thresholds as described above (e.g., 1.7 for overall morphing cost and 1.8 for spatial cost210, volumetric cost212, and geometric cost214) then the balance module224determines that the particular second path is a candidate for duplication. Accordingly, the balance module224is employed to duplicate the candidate second path to generate an artificial path to match with the first path. In an example with more than one candidate for duplication, the candidate with the least overall cost is selected for duplication.

In some instances, however, no candidate pairs exist that are below the z-score thresholds. Accordingly, the balance module224is operable to generate an artificial path that is a singularity, e.g., a degenerate single anchor path. Consider an example in which one of the first paths is an unmatched path. To generate the single anchor path to match with the first path, the balance module224determines the x-displacement and the y-displacement of the first path from the center of the first vector object122. The balance module224then creates the single anchor path at an equivalent relative x-displacement and y-displacement from a center of the second vector object124. This ensures minimum migration of the first path while blending. Further, the balance module224is operable to insert the single anchor path at a same z-order of the first path. The single anchor path does not have a visual effect on the second vector object124, rather is defined by a single “invisible” anchor point. Thus, during subsequent blending the previously unmatched path appears as if it is “disappearing into” or “appearing out of” a digital canvas.

Generating a Transformed Vector Object

Upon balancing unmatched paths, the mapping of paths218includes low-cost path pairs for each of the first paths and each of the second paths. The transformation module116includes a morphing module226that is employed to generate the transformed vector object118by adjusting a property of at least one of the first paths based on the mapping (block1008). In an example, the properties include one or more of a geometry (e.g., shape, orientation, size, etc.), appearance (e.g., color, gradient, fill, etc.), and/or z-order (e.g., overlap order of constituent entities) of the at least one first path.

To generate the transformed vector object118, the morphing module226employs an interpolation module228that is operable to linearly interpolate one or more of the properties. In an example, the interpolation module228generates an interpolation axis, e.g., from zero to one, such that the transformed vector object118falls on the axis between zero and one. In this example, the closer the transformed vector object118is to one, the more the transformed vector object118looks like the second vector object124while closer to zero the transformed vector object118looks similar to the first vector object122. Accordingly, at 0.5, the transformed vector object118is equally influenced by the first vector object122and the second vector object124.

In some embodiments the transformed vector object118is based on a relative amount230of influence of the second vector object124on the first vector object122. For instance, properties of the first vector object122are adjusted to an extent determined by the relative amount230. In one example, the relative amount230is received as user input received via a user interface110, for instance, as a specified amount of influence of the second vector object124on the first vector object122. In another example, the relative amount230is determined automatically and without user intervention, for instance based on a preset level of influence.

By way of example, consider the continuums416,514, and716depicted inFIGS.4,5, and7that illustrate various levels of influence of the second vector object124on the first vector object122. The continuums416,514,716demonstrate linear interpolation of geometry, appearance, and z-order based on various relative amounts230to generate transformed vector objects118that “look like” the first vector object122and/or the second vector object124to varying degrees. While in these examples transformed vector objects118are depicted as vector images, in some examples the techniques described herein are usable to generate one or more blending animations, videos, GIFs, SVGs, multi-state objects, etc.

To adjust the geometry of the at least one first path, the interpolation module228is operable to adjust a location of one or more control points (e.g., anchors and/or handles) of the first path based on the mapping of paths218. The interpolation module228is also employed to adjust the appearance of the at least one path, for instance by gradationally editing fill and stroke operations applied to the first path, e.g., based on the relative amount230. In some instances, the interpolation module228linearly interpolates the z-order, e.g., to adjust the z-order of the first path. However, in various examples the mapping module216generates the mapping of paths218regardless of z-order to minimize the cost of generating path pairs. For instance, a first path associated with a high z-order is matched with a second path with a low z-order. Thus, the first path “migrates” from high z-order to a lower z-order as part of blending. Because the first vector object122and second vector object124include a plurality of paths, this often results in z-order conflicts, i.e., z-order inversions. A naïve z-order migration scheme does not consider such conflicts, and thus a resultant transformed vector object118includes visual artifacts.

Accordingly, in various implementations the interpolation module228leverages a z-order crossfading scheme to control the z-order migration. Use of the z-order crossfading scheme enables the first paths to migrate to a targeted z-order, e.g., from a higher z-order to a lower z-order or vice versa while the geometry and appearance are interpolated in a two-dimensional plane. In an example, the interpolation module228calculates a table of z-order migrations to efficiently implement the z-order crossfading scheme, and thus conserve computational resources. The z-order crossfading scheme further utilizes fractional indexing to resolve z-order conflicts such as z-order inversions, e.g., when path pairs “cross” during z-order migration.

Fractional indexing allows the interpolation module228to generate fractional indices that represent “intermediate” z-orders. For instance, to resolve a z-order conflict between paths of 0th order and 1″ order, the interpolation module228is operable to generate fractional indices between the 0th and 1″ order, such as 0.5 z-order, 0.25 z-order, 0.125 z-order, etc. In this way, the interpolation module228resolves z-order conflicts and ensures proper z-order for each path pair during blending. The z-order crossfading scheme and implementation of fractional indexing further result in fewer migrations per path pair, and thus conserves computational resources in z-order interpolation.

FIG.8depicts an example800of advantages of z-order crossfading in a first stage802, a second stage804, and a third stage806. In this example, as shown in the first stage802, a first vector object122depicts a first plant808with drooping leaves in a large pot. A second vector object124depicts a second plant810with elliptic leaves in a relatively small pot. Second stage404depicts a continuum812that represents an attempt to blend the first plant808and the second plant810without utilizing the z-order crossfading scheme as described above. Consequently, vector objects included in the continuum812include visual artifacts and do not depict realistic intermediates. For instance, a vector object814depicts a vector object with multiple layer inconsistencies and a fragmented visual appearance.

In contrast, third stage806depicts a continuum816that represents blending the first plant808with the second plant810in accordance with the techniques described herein, for instance utilizing z-order crossfading. For instance, the interpolation module228leverages a z-order crossfading scheme to control the z-order interpolation. Accordingly, a subsequently generated transformed vector object118, e.g., a third plant818, is artifact free and is of superior visual quality when compared with the limitations depicted in second stage804.

The morphing module226further includes a reassembly module232. As described above, in some examples the first vector object122and second vector object124include a plurality of blendable hierarchies204that are processed individually. The reassembly module232is operable to reassemble the blendable hierarchies204to generate the transformed vector object118based on an original configuration of the blendable hierarchies204in the first vector object122. Accordingly, the transformed vector object118includes paths that have been blended, (e.g., linearly interpolated) however retain the functionality, editability, and visual effects as defined by various path groups, e.g., simple groups, clipping groups, compound paths, etc.

FIG.9depicts an example900of a practical application of the techniques described herein in first stage902and second stage904. In this example, a graphic designer has two mockups for a design however would like a representation that combines aspects of both designs. As depicted in first stage902, a first logo906includes a circular design with mountains and a second logo908is a shield shape with no mountains, and a hammer graphic under the text. Using the techniques described herein, the transformation module116is operable to generate a variety of example logos based on the first logo906and the second logo908, for instance by using the first logo906as the first vector object122and the second logo908as the second vector object124. Accordingly, the user is presented with a variety of multistate objects, i.e., transformed vector objects118, that represent identifiable and practical intermediates that include visual characteristics of both the first logo906and the second logo908. In this way, the techniques described herein overcome the limitations of conventional techniques by enabling creative customization of vector objects based on visual characteristics of multiple vector objects, while maintaining functionality of a mathematical representation associated with vector output.

Example System and Device

FIG.11illustrates an example system generally at1100that includes an example computing device1102that is representative of one or more computing systems and/or devices that implement the various techniques described herein. This is illustrated through inclusion of the transformation module116. The computing device1102is configurable, for example, as a server of a service provider, a device associated with a client (e.g., a client device), an on-chip system, and/or any other suitable computing device or computing system.

The example computing device1102as illustrated includes a processing system1104, one or more computer-readable media1106, and one or more I/O interface1108that are communicatively coupled, one to another. Although not shown, the computing device1102further includes a system bus or other data and command transfer system that couples the various components, one to another. A system bus can include any one or combination of different bus structures, such as a memory bus or memory controller, a peripheral bus, a universal serial bus, and/or a processor or local bus that utilizes any of a variety of bus architectures. A variety of other examples are also contemplated, such as control and data lines.

The processing system1104is representative of functionality to perform one or more operations using hardware. Accordingly, the processing system1104is illustrated as including hardware element1110that is configurable as processors, functional blocks, and so forth. This includes implementation in hardware as an application specific integrated circuit or other logic device formed using one or more semiconductors. The hardware elements1110are not limited by the materials from which they are formed or the processing mechanisms employed therein. For example, processors are configurable as semiconductor(s) and/or transistors (e.g., electronic integrated circuits (ICs)). In such a context, processor-executable instructions are electronically-executable instructions.

The computer-readable storage media1106is illustrated as including memory/storage1112. The memory/storage1112represents memory/storage capacity associated with one or more computer-readable media. The memory/storage1112includes volatile media (such as random access memory (RAM)) and/or nonvolatile media (such as read only memory (ROM), Flash memory, optical disks, magnetic disks, and so forth). The memory/storage1112includes fixed media (e.g., RAM, ROM, a fixed hard drive, and so on) as well as removable media (e.g., Flash memory, a removable hard drive, an optical disc, and so forth). The computer-readable media1106is configurable in a variety of other ways as further described below.

Input/output interface(s)1108are representative of functionality to allow a user to enter commands and information to computing device1102, and also allow information to be presented to the user and/or other components or devices using various input/output devices. Examples of input devices include a keyboard, a cursor control device (e.g., a mouse), a microphone, a scanner, touch functionality (e.g., capacitive or other sensors that are configured to detect physical touch), a camera (e.g., employing visible or non-visible wavelengths such as infrared frequencies to recognize movement as gestures that do not involve touch), and so forth. Examples of output devices include a display device (e.g., a monitor or projector), speakers, a printer, a network card, tactile-response device, and so forth. Thus, the computing device1102is configurable in a variety of ways as further described below to support user interaction.

Various techniques are described herein in the general context of software, hardware elements, or program modules. Generally, such modules include routines, programs, objects, elements, components, data structures, and so forth that perform particular tasks or implement particular abstract data types. The terms “module,” “functionality,” and “component” as used herein generally represent software, firmware, hardware, or a combination thereof. The features of the techniques described herein are platform-independent, meaning that the techniques are configurable on a variety of commercial computing platforms having a variety of processors.

An implementation of the described modules and techniques is stored on or transmitted across some form of computer-readable media. The computer-readable media includes a variety of media that is accessed by the computing device1102. By way of example, and not limitation, computer-readable media includes “computer-readable storage media” and “computer-readable signal media.”

“Computer-readable storage media” refers to media and/or devices that enable persistent and/or non-transitory storage of information in contrast to mere signal transmission, carrier waves, or signals per se. Thus, computer-readable storage media refers to non-signal bearing media. The computer-readable storage media includes hardware such as volatile and non-volatile, removable and non-removable media and/or storage devices implemented in a method or technology suitable for storage of information such as computer readable instructions, data structures, program modules, logic elements/circuits, or other data. Examples of computer-readable storage media include but are not limited to RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, hard disks, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or other storage device, tangible media, or article of manufacture suitable to store the desired information and are accessible by a computer.

“Computer-readable signal media” refers to a signal-bearing medium that is configured to transmit instructions to the hardware of the computing device1102, such as via a network. Signal media typically embodies computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as carrier waves, data signals, or other transport mechanism. Signal media also include any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media include wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared, and other wireless media.

As previously described, hardware elements1110and computer-readable media1106are representative of modules, programmable device logic and/or fixed device logic implemented in a hardware form that are employed in some embodiments to implement at least some aspects of the techniques described herein, such as to perform one or more instructions. Hardware includes components of an integrated circuit or on-chip system, an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), a complex programmable logic device (CPLD), and other implementations in silicon or other hardware. In this context, hardware operates as a processing device that performs program tasks defined by instructions and/or logic embodied by the hardware as well as a hardware utilized to store instructions for execution, e.g., the computer-readable storage media described previously.

Combinations of the foregoing are also be employed to implement various techniques described herein. Accordingly, software, hardware, or executable modules are implemented as one or more instructions and/or logic embodied on some form of computer-readable storage media and/or by one or more hardware elements1110. The computing device1102is configured to implement particular instructions and/or functions corresponding to the software and/or hardware modules. Accordingly, implementation of a module that is executable by the computing device1102as software is achieved at least partially in hardware, e.g., through use of computer-readable storage media and/or hardware elements1110of the processing system1104. The instructions and/or functions are executable/operable by one or more articles of manufacture (for example, one or more computing devices1102and/or processing systems1104) to implement techniques, modules, and examples described herein.

The techniques described herein are supported by various configurations of the computing device1102and are not limited to the specific examples of the techniques described herein. This functionality is also implementable all or in part through use of a distributed system, such as over a “cloud”1114via a platform1116as described below.

The cloud1114includes and/or is representative of a platform1116for resources1118. The platform1116abstracts underlying functionality of hardware (e.g., servers) and software resources of the cloud1114. The resources1118include applications and/or data that can be utilized while computer processing is executed on servers that are remote from the computing device1102. Resources1118can also include services provided over the Internet and/or through a subscriber network, such as a cellular or Wi-Fi network.

The platform1116abstracts resources and functions to connect the computing device1102with other computing devices. The platform1116also serves to abstract scaling of resources to provide a corresponding level of scale to encountered demand for the resources1118that are implemented via the platform1116. Accordingly, in an interconnected device embodiment, implementation of functionality described herein is distributable throughout the system1100. For example, the functionality is implementable in part on the computing device1102as well as via the platform1116that abstracts the functionality of the cloud1114.

CONCLUSION

Although the invention has been described in language specific to structural features and/or methodological acts, it is to be understood that the invention defined in the appended claims is not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as example forms of implementing the claimed invention.