Discrete Optimization Algorithm for Converting an Image to a Connected Graph of Strings

Introduction

By using ordinary linear least squares for the optimization task, defined by $$ \min _{x}\|A x-y\|_{2}^{2} \quad \text { with } \quad A : \mathbb{R}^{n} \rightarrow \mathbb{R}^{m} $$ we propose an algorithm which takes a normal image as input and turns it into a linked string graph that best attempts to re-assemble the image input.

Results

⊕Left: Original image; Right: Approximation with a connected graph of strings.

The algorithm finds the darkest line between two pins. It adds this line to a new blank image and removes the same line from the original image. The output is an image created out of straight lines where every line goes through the whole image.

Background

Generally it is thought that the transformation of continuous signals into discrete representations inevitably leads to information loss, as Shannon's sampling theorem demonstrates. Yet our algorithm suggests a more nuanced perspective: by carefully selecting a basis of straight-line elements guided by an L2-norm optimization, we achieve a form of lossy compression that preserves perceptually significant features. This approach shadows the fundamental principles of sparse coding in signal processing, where patterns are represented through an optimal selection of basis functions, though in our case, these bases are constrained to physical realizability as actual strings. The implementation below demonstrates how this interplay between information theory's limits and optimization's possibilities can yield aesthetically pleasant results.

Code

The core algorithm implementation:

// Initialize circle of pins around the image
        private void init() {
            double rad = Math.min(img.getWidth(), img.getHeight()) / 2;
            for (int i = 0; i < numberOfPins; ++i) {
                double d = Math.PI * 2.0 * (double)i / (double)numberOfPins;
                px[i] = img.getWidth()/2 + Math.sin(d) * rad;
                py[i] = img.getHeight()/2 + Math.cos(d) * rad;
            }
        }
        
        // Core optimization: Find darkest line between pins
        void calculateLine() {
            double limit = 1000000;
            int bestFirstPin = 0, bestSecondPin = 0;
            int i = currentPin;
            
            // For current pin, check lines to all other valid pins
            for(int j = 1 + ignoreNeighbors; j < numberOfPins - ignoreNeighbors; ++j) {
                int nextPin = (i + j) % numberOfPins;
                if(nextPin == i) continue;
                
                // Calculate line intensity by sampling points along the line
                double dx = px[nextPin] - px[i];
                double dy = py[nextPin] - py[i];
                double len = lengths[j];
                double intensity = 0;
                
                for(int k = 0; k < len; ++k) {
                    double s = (double)k/len;
                    intensity += img.getRGB((int)(px[i] + dx * s), 
                                         (int)(py[i] + dy * s));
                }
                
                // Update if darkest line found
                double currIntensity = intensity / len;
                if(limit > currIntensity) {
                    limit = currIntensity;
                    bestFirstPin = i;
                    bestSecondPin = nextPin;
                }
            }
            
            // Draw the found line and update the source image
            drawLine(bestFirstPin, bestSecondPin);
            currentPin = bestSecondPin;  // Continue from end of last line
        }

GitHub Repository with the complete code