Geometry processing

By Natasha Diederen, Sahra Yusuf, and Olga Guțan

I. Introduction

An algorithm is a finite sequence of well-defined, computer-implementable instructions, typically designed to solve a class of specific problems or to perform a computation. Similarly to how we use our brains to (sometimes wrongly) categorize things in order to make sense of the world, a computer needs an algorithm to make sense of what the user is asking it to do. Since an algorithm is a way of communication between two vastly different entities — a human and a machine — some information gets lost along the way. The process is intellectually intriguing to witness, however, problems can arise when we use algorithms to make decisions that influence the lives of humans and other self-aware living beings.

Algorithms are indispensable for efficiently processing data; therefore they will continue to be part of our programming ecosystem. However, we can (and must) keep some space in our minds for the additional nuances that reality contains. While a programmer may not be able to fully convey these nuances to a computer, we must be aware that no algorithm’s output is final, all-encompassing, and universally true. Furthermore, we must be mindful of the conclusions we draw from the output of algorithms.

II. Algorithms Gone Wrong

Broadly speaking, potential pitfalls for algorithms are manifold. The issues stem from the nature of the algorithms — a communication tool between a human entity and a nonhuman entity (a computer). These problems morph into different real-life issues based on what types of algorithms we use and what we use them for.

Even when playing with algorithms intended to solve toy problems that we already have the answers to, we can notice errors. However, in real life, data is (even) more messy and consequences are far larger. In 2018, Elaine Herzberg was hit and killed by a self-driving taxi. She was jaywalking in the dark with a bicycle by her side and the car alternated between classifying her as a person and a bicycle, thus miscalculating her trajectory and not classifying Elaine as an obstruction. In this case, the safety driver was distracted by a television program, and thus not entirely blameless. However, this serves as an example of how our blind trust in the reliability of algorithms can often result in complacency, with far reaching consequences.

A further example of error in algorithms is adversarial attacks on neural networks. This is when researchers (or hackers) feed a neural network a modified image, where changes made to the image are imperceptible to the human eye. Nevertheless, this can result in incorrect classification by neural networks, with high confidence to boot.

Figure 1. A demonstration of fast adversarial example generation applied to GoogLeNet (Szegedy et al., 2014a) on ImageNet. Source.

In Figure 1 we see how by adding an imperceptibly small vector whose elements are equal to the sign of the elements of the gradient of the cost function with respect to the input, we can change GoogLeNet’s classification of the image. Here the \(\epsilon\) of 0.007 corresponds to the magnitude of the smallest bit of an 8 bit image encoding after GoogLeNet’s conversion to real numbers.

Although researchers are working on making neural networks more robust to these sorts of attacks, susceptibility to adversarial attacks seems to be an inherent weakness of deep neural networks. This has serious security implications as computer vision increasingly relies on these models for facial recognition, autonomous vehicles, speech recognition and much more.

III. Geometry Processing with Imperfect Data

In geometry processing, there is often a need for refinement of geometric data, especially when the data is taken from “real” contexts. Examples of imperfections in 3D models include gaps, self-intersections, and non-manifold geometry, or geometry which cannot exist in reality (e.g. edges included in more than two faces and disconnected vertices).

One common source of imperfect, “real-life” data is 3D object scanning. The resulting models typically include gaps and large self-intersections as a result of incomplete scanning or other error arising from the scanning method. Despite these significant problems, scanned data is still invaluable for rapidly generating assets for use in game development and other applications. During our time at the Summer Geometry Institute, Dr. Matthias Nießner spoke about 3D scene reconstruction with scanned data. His work demonstrated a method of improving the overall quality of reconstructed scenes using bundle adjustment and other techniques. He also worked on solving the problem of incomplete scanned objects using machine learning. Previously, we have written about possible mistakes arising from the weaknesses of machine learning, but Dr. Nießner’s work demonstrates that machine learning is a valuable tool for refining data and eliminating mistakes as well.

Although error in geometry processing is not as frequently discussed, the implications are just as important as those of mistakes arising from the use of machine learning. This is primarily due to the fact that machine learning and geometry processing are not isolated fields or tools, but are often used together, especially in the sorts of situations we described earlier. By researching and developing new methods of data refinement, we can improve the usability of natural data and increase, for example, the safety of systems which rely on visual data.

IV. Human Error and Bias

The errors we have discussed so far exclude human error and bias, which can aggravate existing inequalities in society. For example, a Fellow one of us worked with during SGI mentioned how he worked on a project which used face tracking to animate digital characters. However, the state-of-the-art trackers only worked on him (a white male) and could not track eye or mouth movement for those in his team of black descent. Additionally, as we heard from Theodore Kim in another brilliant SGI talk, animation is focused on designing white skin and non-type 4 hair, further highlighting the systemic racism present in society.

Moreover, the fact that 94.8% of Automatic Gender Recognition (AGR) papers recognize gender as binary has huge implications for the misgendering of trans people. This could lead to issues with AGR based access control for things like public bathrooms, where transgender people may be excluded from both male and female facilities. The combination of machine and human error is especially dangerous, and it is important to recognize this, so that we can mitigate against the worst harm.

V. Conclusion

Algorithms have become a fundamental part of human existence, however our blind faith that algorithms are always (1) correct and (2) unbiased is deeply flawed. The world is a complicated place, with far too much data for computers to handle, placing a strong reliance on simplification algorithms.

As we have seen from the examples above, these algorithms are far from perfect and can sometimes erase or distort important data. This does not mean we should stop using algorithms entirely. What this does, however, mean is that we must employ a hearty dose of critical thinking and skepticism when analyzing results outputted by an algorithm. We must be especially careful if we use these results for making decisions that would influence the lives of other humans.

By Bryce Van Ross and Olga Guțan

Brief Existential Background

Most branches of geometry are viewed as either (1) subsets of pure mathematics or (2) disciplines derived from problems in engineering, architecture, and computational mathematics. But what is geometry itself?

Our work in the Summer Geometry Institute has been in the modern field of geometry processing. In this post, we will consider the philosophical aspects of geometry, and what they tell us about geometry processing specifically. The discussion has an inherent Eurocentric bias, and is, unfortunately, limited to Caucasian male philosophers.

The Roots of Geometry

In the eighteenth century, mathematics was primarily used to understand the natural sciences. For example, it was perceived as a language to better articulate physics, rather than as having intrinsic value. At that time, geometry was perceived as a form of applied mathematics. But where does the philosophy of geometry have its roots?

First we have Kant (1724-1804), who believed that our grasp of euclidean geometry must be instinctive. Opinions about this vary, based on each individual’s definitions of a priori knowledge and empiricism. Helmholtz, for example, agreed with Kant.

However, geometry processing incorporates not only euclidean geometry, but also calculus, linear algebra, differential equations, and topology. In addition, geometry processing includes a framework of algorithmic and optimization techniques. The knowledge of these topics varies from person to person, and therefore geometry processing can not be known a priori.

Back to the 18th century: as logical empiricism became popular, the progress of philosophy of geometry stalled. Geometry was reduced to a system of definitions and conventions; logic and mathematics were given priority. As a result, the last big wave of interest in the philosophy of geometry was in the 1920s — 100 years ago, and 116 years after Kant!

Space as a Mathematical Concept

Mathematical conclusions depend on the structure we confer to a space. The structure determines the permissible elements, as well as the operations that can be applied to the elements. Without imposing structure, it is difficult to impose “rules,” and the potency of math is, thus, diluted. Most spaces in euclidean geometry exist; in fact, they are embedded in the reality we live in. With other kinds of geometry, we must define the properties of the space first. Then, we can ask: what are the conditions for creating a space? What kinds of spaces, and therefore geometries, can we have? (Our personal favorite is the geometry of chance.)

Helmholtz (1821-1894) said the only allowable spaces are those that maintain constant curvature. This was eventually challenged by Einstein’s (1879-1955) Theory of Relativity. Weyl (1885-1955) came up with intuitive spaces, where it is possible to compare lengths only if two edges share the same spatio-temporal point. Similarly to the earlier-mentioned Kant (1724-1804), Carnap (1891-1970) claimed that intuition of spaces requires an n-dimensional topological space. As the philosophy of geometry evolved, so did our understanding of space.

“Waiting for Godot” in a Hyperbolic Space?

(The authors would like to gratefully acknowledge the primary source for the following sections.)

So what is geometry? Many people study it or use it… but what exactly are we interacting with?

As an exercise of imagination, consider being a two-dimensional (2D) entity in a 2D universe. In fact, you don’t even have to imagine, somebody already wrote about this. The book is, unfortunately, at times misogynistic, but the geometry is intriguing to consider. Back to the exercise of imagination: since everything in the 2D universe is finite, is the universe itself finite? A 2D mathematician might suggest that the universe looks like a rectangle. Does, then, the universe have a point beyond which travel is impossible? If so, it likely is different from all other points of the universe, by its construction, since it has a boundary. Imagine you are playing Asteroids. As you move your rocket ship towards the right — once it reaches the boundary, it will reappear on the left side. In mathematical language we say that “the left edge of the rectangle has been identified, point by point, with the right edge.”

Figure 1. A finite 2D world with no boundary. Source.

How to Build a Torus When You Are Two-Dimensional

In three dimensions, we can glue these boundaries. First, we bend the rectangle to produce a cylinder, while being careful to glue only the left and right edges together. Since we are operating in a ‘perfect’ thought-based mathematical world, the cylinder is malleable. Now we bend it to achieve this second gluing, which looks like a donut. We call this a torus.

Recall that our reader currently lives in a 2D universe. A 2D person would not be able to see this torus in multiple dimensions. However, one would understand the space perfectly well, since the space can be identified back to the initial rectangle with edges. In this case, the universe is clearly finite, and with no edges.

Another surface with similar properties would be a two-dimensional sphere. A ladybug traveling on the sphere will notice that, locally, their world looks like a flat plane, and that the surface has no edges. On a small scale, if the mathematician ladybug splits the plane into triangles, the sum of the angles in each triangle will be 180 degrees. This is, in fact, known as a defining feature of euclidean geometry. However, on a larger scale, things start breaking.

A very large triangle drawn on the surface of the sphere has an angle sum far exceeding 180 degrees. Consider the triangle formed by the North Pole and two points on the equator of the sphere. The angle at each point on the equator is 90 degrees, so the total sum exceeds 180 degrees. Therefore, we conclude that — on a global scale — we can not apply euclidean geometry to a sphere. We call this hyperbolic geometry.

Figure 3. Angles add up to more than 180 degrees. Source.

Shape and Connection

To conclude this exercise of imagination, we must say that there is a wonderful connection between the shape (topology) of a surface and the type of geometry it inherits. This relationship is given, mathematically, by the Gauss-Bonnet equation:

\(\kappa A = 2 \pi \xi\)

Where \(\kappa \) is the Gaussian curvature of a surface, A is the element of area of the surface, \(\pi \) is our good old friend 3.1415…, and \(\xi\) is the Euler characteristic of the surface. In other words, the “geometry” is on the left side of the equation and the “topology” is on the right side of the equation; and the equal sign shows how deeply connected they are.

Studying various shapes and how they connect is not only interesting, but also important. Particularly, if a two-dimensional entity can deduce what sort of global geometry reigns their immediate world, they may be able to deduce the possible shapes for the things in their larger universe.

To Really Conclude…

Although geometry processing has been around for a few decades, its philosophy is not yet well-studied. So far, this area shares themes with the broader philosophy of geometry, in certain topics:

a priori vs empiricist knowledge,
the evaluation of space and its elements,
geometric human intuition,
construction of geometries, and
the study of shape and connection.

Given the computational aspect of geometry processing, there are additional important philosophical questions that arise, however they go beyond the scope of this post. It is difficult to determine whether such questions are best understood from the perspective of philosophy of geometry or philosophy of computer science, or both.

As geometry processing continues to impact our technological world, the philosophy of geometry processing will grow too. In the meantime, we should continue critically questioning our programming, our modeling, and — most importantly — the ethical implications of our work. We must also ensure that we have a functional understanding of the parts that constitute geometry processing. At the same time, it must be said that the discipline is more than just the sum of its parts.