Creating and Modifying Images Using Newton’s Method for Solving Equations

Year: 2010 Authors: Stanley Spencer

Core claim

Newton’s method can be programmed as an image-making system that produces meaningful, controllable pictures from root/step dynamics and even inverted pixel evolution.

Topics

Newton’s method, image synthesis, iterative dynamics, fractal boundaries, image modification

Domains

numerical analysis, complex polynomials, root-finding, fractal geometry, digital art, generative imagery, visual pattern design, animation

Methods

Newton-Raphson iteration, root/step matrix, pixel-to-complex mapping, inverse transformation

Media

software, digital images, high-resolution pixel grids, animated frames

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2010: Mathematics, Music, Art, Architecture, Culture

Creating and Modifying Images Using Newton’s Method for Solving Equations

Stanley Spencer The Sycamores Queens Road Hodthorpe Worksop Nottinghamshire, England, S80 4UT pythagoras@bcs.org.uk

Abstract

The pictures associated with Newton’s Method of finding the roots of an equation are familiar to mathematicians and non-mathematicians. The main purpose of this paper is to look at ways by which a recognisable image can be produced or modified using the same mathematical process. This paper looks at several ways that an arbitrary pixel image can be iteratively transformed using Newton type algorithms. The standard approach of letting the pixels evolve towards attractors was interesting, but a second approach, one that inverted the process so that attractors became expellers, looks fruitful for creating interesting images. The process was designed to allow equations with up to a hundred roots which created challenges but also opportunities for meaningful outcomes.

1. Introduction

Upon reading Pietgen and Richter’s The Beauty of Fractals [1] for the first time, I used my programming skills and a long-forgotten set of notes on complex numbers to reproduce most of its pictures based on Julia set fractals, Yang Lee singularities and Newton’s method for complex polynomials. The book also contains an interesting discussion concerning the nature of art and science (page 20), particularly with regard to the lack of choice and human concern. This discussion intrigued me into experimenting with something more than just conventional use of colour to represent the speed of convergence. This paper is limited to examples from Newton’s method for solving polynomials. To improve the graphic possibilities up to a hundred roots was allowed.

2. The Basic Process

Newton’s method for finding a root relates to a process of producing an improved estimate for a root from a previous estimate. I explored two methods, the first being Newton’s original and the second a development known as the Newton Raphsons method. For the, albeit limited examination, both approaches gave identical results. The latter, however, was chosen because it was more general and therefore more amenable to programming. The process for a polynomial produces a sequence of points formed by using

183

Spencer

Figure 1: The result of applying Newton’s method to $f(x)=x^3-1$

In the complex plane a colour is given to the starting point depending upon which root it reaches and the number of steps it takes to reach it. A more detailed account can be found at [2],[6]

3. Creating Images

Unlike the work described in [2] and [6] my aim was to develop software that would allow the creation and manipulation of images that had a significance other than mathematical. From a pictorial point of view the process requires complex roots allowing for two dimensional images. The usual approach interprets each pixel as a complex number, which is used as an initial guess, in the Newton - Rahpson process; and giving the pixel a colour depending upon the root it leads to and the number of iterations it takes to reach the root [1],[2]. Figure 1 shows a typical result for the roots of

The positions of the three roots are indicated by the small circles. Two of the roots are complex and the third real. They lie on the unit circle.

4. A Brief Description of the Software

As in most art work, colour is an important feature as is the scale of the picture. The software was designed to develop pictures up to 10 layers each of up to 120 megapixels and 256 colours. This being the limit of the hardware available. The length of these calculations necessitated regular dump and restart facilities in the software. The time involved in the creation of a high resolution picture can be considerable, frequently over 20 hours, so the software allowed the development of a low resolution picture prior to the final version. Frames of an animated sequence can be saved so that the dynamics of the process can be studied. I allowed for polynomials with up to 100 roots. Optionally, the software could start with the equation or the roots. In practice the latter provided more control over the shape and form of the final output and was more relevant to my aims. With this approach a complex polynomial has to be created from the roots rather than the other way round.

I was expecting some problems with not being able to determine to which root a pixel would be attracted. Trapping these and other exceptional conditions proved to be straightforward. Some images were produced by uniquely colouring pixels with uncertain outcomes. Experiments were conducted which identified pixels, the corners of which would be attracted to different roots. These I referred to as Newton’s border of uncertainty.

The trapping of overflow errors was necessary with the large powers associated with polynomials having a large number of roots.

The matrix of colours and roots could accommodate up to 100 roots and 500 steps. This table could be generated, manually, systematically by algorithm or created from an image providing a mosaic type result. Three general approaches were allowed. The first allowing the position of the roots and the colour/root matrix to determine the outcome. The second started with an image. The subsequent position of its pixels were manipulated according to the Newton - Raphson method. The third approach was the inverse of the second i.e. What image would I need to have started with to obtain a particular given image?

Creating and Modifying Images Using Newton’s Method for Solving Equations

5. Examples of Images Controlled by the Root/Steps Matrix

Figure 2: The Olympic rings are represented by 5 roots at the centre of each ring.

Figure 3: This image called Newton’s rose had 10 roots forming two concentric pentagons. Figure 4: I have called this image Newton’s rainbow

The images on this page were created using the roots as the starting point. Figure 2 has five roots each one at the centre of an Olympic ring. Only the pixels that reached a root in 5, 7 or 11 steps were coloured. Figure 3 has five fold symmetry and the roots form two concentric pentagons. This symmetry is similar to that of the Christmas rose. When Newton was born his birthday was Christmas Day, consequently I called this image Newton’s Rose. Newton’s work included a study of the way in which white light was broken down into he component colours of the spectrum by a prism. Figure 4 shows an image coloured in the rainbow colours. There are six roots formed by two concentric triangles. I have called this image Newton’s Rainbow. Newton spent a lot of his life studying Alchemy, which was illegal in the 17th century. Newton left a detailed description of the Philosopher’s stone. A facsimile of this and other of Newton’s papers in Newton’s original hand can be found at [5]. The image in figure 5 has 14 roots formed by two concentric heptagons. Naturally, I called this image the Philosopher’s Stone.

Figure 5: The Philosopher’s Stone is based on Newton’s description

Spencer

Figure 6: The Dubai Tile - 20 roots

Figure 7: Extended Newton’s Rainbow - 60 roots

The images on this page were created using a larger number of roots. The Geometry of Figure 6 was based on 20 points from the geometry of the tiles of a prayer room at Dubai Airport. The areas coloured magenta are areas where overflow would have occurred had I not trapped the errors. Figure 7 is a detail from another version of Newton’s Rainbow this time there are 20 concentric triangles giving 60 roots. The colour scheme was the same as figure 4. The grey areas at the centres of the florets are overflow areas. Figure 8, The linear rose, consists of 30 real roots. The blue outer region is the result of overflow. Figure 9 represents a peacock. There are forty roots formed by two concentric polygons each with 20 sides.

Figure 8: The Linear Rose 30 roots

Figure 9: S R Peacock - 40 roots

Creating and Modifying Images Using Newton’s Method for Solving Equations

6. Sudoku Images

Figure 10 is based upon the Magic Sudoku. The 3x3 square at the centre is a magic square. The other 3x3 squares are semi magic. The colouring scheme is based upon the resistor colour code. There are 39 roots lying on alternate sides of a hexagon. The magenta are overflow regions.

Figure 11 is my solution to a Cubic Sudoku. This is a cube with $9\times 9\times 9$ cells each containing one of the numbers 1-9 such that each of the 27 vertical and horizontal slices through the cube give a valid Sudoku. There needs a minimum of 81 roots. The image below has 90 roots arranged along the arms of a nine pointed star. The green circular image shows the detail at the centre of the star. The white circular regions on both images are the areas of overflow.

Figure 10: Based upon a magic sudoku. The $3\times 3$ square at the centre is a magic square. The other $3\times 3$ squares are semi magic.

Figure 11: Based upon a Sudoku cube. Each of the 27 vertical or horizontal slices through the cube gives a valid Sudoku.

Spencer

7. Mosaic Type Images

Figure 12: The monarch butterfly was an early image. The process used an equation with 41 roots

Figure 13: The depicts Newton’s religious nature.

The possibility of having more than 30 roots each having at least 30 steps allows for a 30x30 matrix of colours making up a reasonable mosaic type image. Some examples are shown on this page.

Figure 12 is the monarch butterfly using a scheme of 41 roots. The outer dark region results from trapping overflow errors

Figure 13 depicts Newton’s religious personality. The image contains a cross motif with Newton’s face superimposed. This was based upon an Enoch Seeman portrait in 1726.

Figure 14 is based upon Sir Godfrey Kneller’s 1689 portrait. The other images include a red cross which was painted on the doors of plague victims and a “flower of kent” apple. It was this apple which supposedly fell on Newton whilst he was contemplating the laws of gravity.

It was the closure of Cambridge University because of the plague that gave Newton the opportunity to develop the theory of gravity which explained Kepler’s empirical laws of planetary motion.

Figure 14: These images are concerned with Newton explaining Kepler’s empirical laws of planetary motion. The right picture is the central detail which is barely visible

Creating and Modifying Images Using Newton’s Method for Solving Equations

8. Borders of Uncertainty

Figure 15: The border of uncertainty for Newton’s rose measuring $512\times 512$ pixels.

Figure 16: The border of uncertainty for Newton’s rose measuring $4096\times 4096$ pixels.

Figure 17: The graph showing the length of the border of uncertainty vs pixel size for two different polynomials.

In reality a pixel represents, not a point, but a small square in the complex plane. A border of uncertainty can be seen when the four corners of a pixel are separately used as an initial guess. In figures 15 and 16 the white areas are pixels where the four corners lead to the same root. The corners of the black pixels don’t lead to the same root and are therefore uncertain. Counting the black pixels leads to an estimate of the length of the border of uncertainty. This experiment was repeated for image size of $128\times 128$ pixels up to $4096\times 4096$ . The pixel size and the length of the border was calculated and the results plotted on logarithmic graph paper (see figure 17). You might expect that the more accurately the length of the border was measured then the closer you get to the “true” value. Figure 17 suggests that the border length increases as the accuracy of the measurement increases. This is consistent with Mandelbrot’s concept of a fractal dimension.[2][3][4]

Spencer

Figure 18: The far left picture shows the first few stages of the pixels in the outer border as the pixels are attracted to the roots. In the right image the roots form the Ursa Major constellation.

9. Modification of Images

Figure 19: The initial image is shown on the far left. The image on the right would produce the far left image after nine iterations of the Newton process.

The software has been developed to deal with the modification of image. The images on this page were used as test pieces for the software. Figure 18 shows two examples of an image being manipulated using Newton’s method. The first shows a series of images formed by the application of the process. The initial guesses were limited to the outer magenta square. The other shapes show the subsequent guesses. The right hand image started as two circles and a bear which were, subsequently, attracted to the roots. In this case the roots formed the shape of the constellation Ursa Major. Figure 19 shows an example of the inverse of the process. There are 6 roots forming two concentric triangles which act as repellers for the pixels in the original image. The images are of Queen Anne who knighted Isaac Newton, late in his life, for political rather than scientific reasons.

References

[1] Peitgen and Richter, The Beauty of Fractals, ISBN 3-540-15851,-0 Springer, 1986 [2] Hans Lauwerier, Fractals Images of Chaos, ISBN 0-14-014411,-0 Penguin, 1991 [3] David Wells, Curious and Interesting Geometry, ISBN 0-14-011813-6, Penguin, 1991 [4] Chaos Theory, <http: chaos_theory="" en.wikipedia.org="" wiki="">, (Accessed 28.12.2007) [5] http://www3.babson.edu/Archives/Newton_collection/MS416C.pdf (accessed 01.11.2009) [6] http://www.polynmiography.com(accessed01.04.2010</http:>