{"id":1370,"date":"2024-08-29T17:33:44","date_gmt":"2024-08-29T17:33:44","guid":{"rendered":"https:\/\/summergeometry.org\/sgi2024\/?p=1370"},"modified":"2024-11-13T15:03:16","modified_gmt":"2024-11-13T15:03:16","slug":"using-bicubic-curves-for-a-differentiable-representation-of-2d-curve-networks","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2024\/using-bicubic-curves-for-a-differentiable-representation-of-2d-curve-networks\/","title":{"rendered":"Using Bicubic Curves for a Differentiable Representation of 2D Curve Networks"},"content":{"rendered":"\n

SGI Fellows: <\/strong>Harini Rammohan, Ashlyn Lee, Diana Aldana Moreno, Ehsan Shams, Taylor Hospodarec <\/p>\n\n\n\n

Project Mentor:<\/strong> Mikhail Bessmeltsev<\/p>\n\n\n\n

SGI Volunteer:<\/strong> Daniel Perazzo<\/p>\n\n\n\n

Raster vs Vector Images<\/h3>\n\n\n\n

Raster and vector graphics are two fundamental types of image representations used in digital design, each with distinct characteristics and applications. A raster image is a collection of colored pixels in a bitmap, making it well-suited for capturing detailed, complex images like photographs. However, raster graphics provide no additional information about the structure of the object they represent. This limitation can be problematic in scenarios where precision and scalability are essential. For example, representing an artist’s sketch as a raster image may result in jagged curves and the loss of fine details from the original sketch. In such cases, a vector graphics representation is preferred. Unlike raster images, vector graphics use mathematical equations to define shapes, lines, and curves, allowing unlimited scalability without losing quality. This makes vector graphics ideal for logos, illustrations, and other designs where clarity and precision are crucial, regardless of size.<\/p>\n\n\n

\n
\"\"
Bitmap and vector images on magnifying
Image from https:\/\/en.wikipedia.org\/wiki\/Image_tracing<\/a> <\/figcaption><\/figure>\n<\/div>\n\n\n

Bicubic Curves for Vectorization<\/h3>\n\n\n\n

In this project, we aimed to obtain a vector graphics representation of a given sketch in raster form using bicubic curves. A bicubic curve is a polynomial of the form<\/p>\n\n\n

\n
\"{\\displaystyle<\/figure>\n<\/div>\n\n\n

The value a bicubic function takes on a given grid cell is assumed to be uniquely determined by the value the function and its derivatives take at the vertices of the cell. Using bicubic curves allows us to more easily handle self-intersections and closed curves. Additionally, we can create discontinuities at the edges of grid cells by adding some noise to the given bicubic function. This will enable us to vectorize not only smooth but also discontinuous sketches.<\/p>\n\n\n

\n
\"\"
A bicubic curve with a self-intersection at (0, 0)<\/figcaption><\/figure>\n<\/div>\n\n
\n
\"\"
Adding discontinuities at the grid cell edges<\/figcaption><\/figure>\n<\/div>\n\n\n

Preliminary Work<\/h3>\n\n\n\n

During the first week of the project, we implemented the following using Python:<\/p>\n\n\n\n

    \n
  1. For any given grid cell, given its size and the function value p(v) as well as the derivatives px<\/sub>(v), py<\/sub>(v), and pxy<\/sub>(v) at each vertex v, we reconstructed and plotted the unique bicubic function satisfying these values. This reduces to solving a system of sixteen linear equations, following the steps mentioned in the “Bicubic Interpolation” Wikipedia page {4}. <\/li>\n\n\n\n
  2. We added noise to the bicubic functions in each cell to create discontinuities. We also found the endpoints of curves in the grid due to the discontinuities formed above.<\/li>\n\n\n\n
  3. At each point in the grid, we found the gradient of the bicubic functions using fsolve <\/em>{5} and used them to plot the tangents at some points on the curves.<\/li>\n\n\n\n
  4. We looked for self-intersections within a grid cell by finding saddle points of the bicubic function (such that the function value is 0 there). If the function is factorizable, it suffices to find the points of intersections between the 0-levels of two or more factors. Here too, we used fsolve<\/em>.<\/li>\n<\/ol>\n\n\n
    \n
    \"\"
    Bicubic curves with tangents produced by picking four random values between -1 and 1 at each vertex<\/figcaption><\/figure>\n<\/div>\n\n\n
    \n
    \"\"<\/figure>\n\n\n\n
    \"\"<\/figure>\n
    Bicubic curves with self-intersections marked<\/figcaption><\/figure>\n\n\n\n

    Optimization and Rendering<\/h3>\n\n\n\n

    Vectorization<\/h5>\n\n\n\n

    During the second week of the project, I attempted to vectorize the bitmap image by minimizing a function known as the L2 loss. <\/p>\n\n\n\n

    The L2 loss between the predicted and target bitmap images is computed as the sum of the squared differences for each pixel. To account for this, I gave the bicubic curves some thickness by replacing the curve Z = 0 (here Z = p(x, y) is a bicubic function) in each grid cell with the image of the function e-Z\u00b2<\/sup>. This allowed me to determine the color at each point in the grid, defining the color of each pixel as the color at its center. Additionally, I calculated the gradient of the color at each point in a grid cell with respect to the coordinates of the corresponding bicubic curve. Using this approach, I defined the L2 loss function and its gradient as follows:<\/p>\n\n\n\n

    # Defining the loss function\ndef L2_loss(coeffs, d, width, height, x, y):\n    c = np.zeros((height, width))\n    for i in range(height):\n        for j in range(width):\n            c[i, j] = np.exp(-bicubic_function(x[j], y[i], coeffs) ** 2)\n    return np.sum((c - d) ** 2)\n\n# Derivative of c(x, y) wrt to the coeff of the x ** m * y ** n term\ndef colour_gradient(x, y, coeffs, m, n):\n    return np.exp(-bicubic_function(x, y, coeffs) ** 2) * (-2 * bicubic_function(x, y, coeffs) * x ** m * y ** n)\n\n# Gradient of the loss function\ndef gradient(coeffs, d, width, height, x, y):\n    grad = np.zeros(16,)\n    c = np.zeros((height, width))\n    for i in range(height):\n        for j in range(width):\n            c[i, j] = np.exp(-bicubic_function(x[j], y[i], coeffs) ** 2)\n            for n in range(4):\n                for m in range(4):\n                    k = m + 4 * n\n                    grad[k] += 2 * (c[i, j] - d[i, j]) * colour_gradient(x[j], y[i], coeffs, m, n)\n    return grad<\/code><\/pre>\n\n\n\n
    In this code, d is the normalized numpy array of the target image and x and y are the lists of the x- and y-coordinates of the corresponding pixel centers.<\/p>\n\n\n\n
    Minimizing this L2 loss in each grid cell gives the vectorization that best approximates the target raster image.<\/p>\n\n\n\n
    Results<\/h5>\n\n\n\n
    Below are some test bitmap images and their vectorized outputs.<\/p>\n\n\n\n
    \n
    \"\"<\/figure>\n\n\n\n
    \"\"<\/figure>\n<\/figure>\n\n\n\n
    <\/p>\n\n\n\n
    \n
    \"\"<\/figure>\n\n\n\n
    \"\"<\/figure>\n<\/figure>\n\n\n\n
    <\/p>\n\n\n\n
    \n
    \"\"<\/figure>\n\n\n\n
    \"\"<\/figure>\n<\/figure>\n\n\n\n
    <\/p>\n\n\n\n
    \n
    \"\"<\/figure>\n\n\n\n
    \"\"<\/figure>\n<\/figure>\n\n\n\n
    <\/p>\n\n\n\n
    \n
    \"\"<\/figure>\n\n\n\n
    \"\"<\/figure>\n<\/figure>\n\n\n\n
    Though the curves mimic the structure of the original sketch, they are not always in the same direction as in the actual sketch. It seems like the curves assume this orientation to depict the thickness of the sketch lines.<\/p>\n\n\n\n
    Conclusion<\/h3>\n\n\n\n
    Our initial plan was to utilize the code developed in the first week to create a differentiable vectorization. This approach would involve differentiating the functions we wrote to find the endpoints and intersections with respect to the coefficients of the bicubic curve. We would also use the tangents we calculated to determine the curve that best fits the original sketch.<\/p>\n\n\n\n
    Throughout the project, we worked with bicubic curves to ensure intersections and continuity of isolines between adjacent grid cells. However, we suspect that biquadratic curves might be sufficient for our needs and could significantly improve the implementation’s effectiveness. We are yet to confirm this and also explore whether an even lower degree might be feasible.<\/p>\n\n\n\n
    This project has opened up exciting avenues for future work and the potential to refine our methods further promises valuable contributions to the field. I am deeply grateful to Mikhail and Daniel for their guidance and support throughout this project. <\/p>\n\n\n\n
    References:<\/h3>\n\n\n\n
    {1} Guillard, Benoit, et al. “MeshUDF: Fast and Differentiable Meshing of Unsigned Distance Field Networks”, ECCV 2022, https:\/\/doi.org\/10.48550\/arXiv.2111.14549<\/a><\/p>\n\n\n\n
    {2} Yan, Chuan, et al. “Deep Sketch Vectorization via Implicit Surface Extraction” SIGGRAPH 202<\/em>4, https:\/\/doi.org\/10.1145\/3658197<\/a>.<\/p>\n\n\n\n
    {3} Liu, Shichen, et al. “Soft Rasterizer: A Differentiable Renderer for Image-based 3D Reasoning” ICCV <\/em>2019, https:\/\/doi.org\/10.48550\/arXiv.1904.01786<\/a>.<\/p>\n\n\n\n
    {4} “Bicubic Interpolation”. Wikipedia<\/em>, https:\/\/en.wikipedia.org\/wiki\/Bicubic_interpolation<\/a>.<\/p>\n\n\n\n
    {5} SciPy – fsolve (scipy.optimize.fsolve), https:\/\/docs.scipy.org\/doc\/scipy\/reference\/generated\/scipy.optimize.fsolve.html<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    SGI Fellows: Harini Rammohan, Ashlyn Lee, Diana Aldana Moreno, Ehsan Shams, Taylor Hospodarec Project Mentor: Mikhail Bessmeltsev SGI Volunteer: Daniel Perazzo Raster vs Vector Images Raster and vector graphics are two fundamental types of image representations used in digital design, each with distinct characteristics and applications. A raster image is a collection of colored pixels […]<\/p>\n","protected":false},"author":73,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[37],"tags":[],"ppma_author":[17],"class_list":["post-1370","post","type-post","status-publish","format-standard","hentry","category-research"],"authors":[{"term_id":17,"user_id":0,"is_guest":1,"slug":"cap-harini","display_name":"harini","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","author_category":"","first_name":"","last_name":"","user_url":"","job_title":"","description":""}],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/1370","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/users\/73"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/comments?post=1370"}],"version-history":[{"count":9,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/1370\/revisions"}],"predecessor-version":[{"id":3618,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/posts\/1370\/revisions\/3618"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/media?parent=1370"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/categories?post=1370"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/tags?post=1370"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2024\/wp-json\/wp\/v2\/ppma_author?post=1370"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}