When implementing image algorithms, I am prone to make these mistakes:
- swapping x and y;
- working on the wrong channel;
- making off-by-one errors, especially in window algorithms;
- making division-by-zero errors;
- handling borders incorrectly; and
- handling non-power-of-two sized images incorrectly.
Since these types of errors are prevalent in many image-processing algorithms, it would be useful to develop, once and for all, general tests that will catch these errors quickly for any algorithm.
This post is about such tests.
Continue reading “Catching Common Image Processing Programming Errors with Generic Unit Tests”
I wrote an article for Dev.Mag covering some techniques for working with seamless tile sets such as making blend tiles, getting more variety with procedural colour manipulation, tile placement strategies, and so on.
Check it out!
The Python Image Code has also been updated with some of the algorithms explained in the article.
I finally laid my hands on Donald Knuth’s The Art of Computer Programming (what a wonderful set of books!), and found a neat algorithm for generating random integers 0, 1, 2, … , n – 1, with probabilities p_0, p_1, … , p_(n-1).
I have written about generating random numbers (floats) with arbitrary distributions for one dimension and higher dimensions, and indeed that method can be adapted for generating integers with specific probabilities. However, the method described below is much more concise, and efficient (I would guess) for this special case. Moreover, it is also easy to adapt it to generate floats for continuous distributions.
Continue reading “Generating Random Integers With Arbitrary Probabilities”
It is sometimes necessary to find the distribution given a sample set from that distribution. If we do not know anything about the distribution, we cannot recover it exactly, so here we look at ways of finding a (discrete) approximation.
Continue reading “Estimating a Continuous Distribution from a Sample Set”
I have already covered how to generate random numbers from arbitrary distributions in the one-dimensional case. Here we look at a generalisation of that method that works for higher dimensions.
The basic trick, while easy to understand, is hard to put in words (without reverting to mathematical equations). For two dimensions, we divide the plane into slices. Each slice is a 1D distribution. We also calculate a distribution from summing the frequencies in each slice. The latter distribution gives us one coordinate, and the appropriate slice to use. The distribution of that slice then gives the second coordinate. All distributions are put into inverse accumulative response curves as was done to generate one-dimensional random numbers. (You should review that before implementing the 2D case).
In more dimensions, we also slice the space up into 1D distributions. Sums of these give us more distributions, which we can sum again, and again, until we reach a single distribution. This is used for the first coordinate, and to determine which distribution to use for the next coordinate. This goes on, until a 1D slice gives us the final coordinate. Again, all distributions are converted to inverse accumulative response curves.
If the above is unclear, I hope the detailed description below clears things up.
Continue reading “Generating Random Points from Arbitrary Distributions for 2D and Up”
A while back I wrote about a simple texture algorithm that I have been exploring. The Python implementation was very slow – so much, that I decided to implement it in C++ to see what performance gain I would get. Surprisingly, the C++ version is about 100 faster, if not more. I expected a decent increase, but what once took several hours can now be done in a minute!
Continue reading “A simple texture algorithm – faster code and more results”
The code below implements some quadtree extensions, as discussed in another Dev.Mag tutorial about quadtrees (see Issue 27). The tutorial covers the following topics:
- what to consider in choosing whether to use a quadtree or not;
- tests to help you choose an appropriate threshold;
- how to handle discrete data; and
- some modifications to the basic algorithm.
Handling Discrete Data
When it comes to discrete data, the “average” of a number of pixels doesn’t make sense. However, we can give it meaning and still use it to get good approximations of the original data, as illustrated in the images below.
||The original grid of discrete data. The grid contains integers from 0 to 4. Every integer is mapped to a colour in this image. (If this grid represented a tile map, every integer would be mapped to a different tile).
||Here we allowed floating point numbers in the quadtree. Results of queries into the quadtree are rounded before mapping them to colours.
||Here we used the floating point part of queries to bias a randomly selected integer. For example, a result of 1.25 will result in a 75% chance of yielding 2.
||Here we use a quadtree with interpolation. The result is rounded before it is mapped.
||Here we use a quadtree with interpolation, and use the floating point part of the number to bias a randomly selected tile, as above.
Download from: http://code-spot.co.za/python-image-code/ (See quadtree.py, quadtree_image.py, and quadtree_demo.py).
In a previous post I explained a simple algorithm for generating textures. Below are some more examples of the kinds of textures that the algorithm can generate, as well as how the different parameters influence the result. You can also download the code.
Continue reading “A Simple Procedural Texture Algorithm – More Results and Code”
I use this code to illustrate many of the tutorials on this site, and the articles I write for Dev.Mag. Ideally, I would like to package the code so that it is the minimal necessary for the particular tutorial; however, a lot of the code is reused, so that it becomes difficult to maintain. Instead, I distribute it all together. That way, new updates and extensions can be found in one place.
The current version includes classes and functions for:
- easy-syntax 2D and 3D arrays (for example, you can use grid[1:20:2, 2:3:20] to access the pixels in every second column (starting with column 1 and ending before column 20) and every third row (starting from row 2 and ending before row 20) (docs);
- general image utility function (docs);
- perlin noise (docs, tutorial);
- poisson-disk sampling (docs, tutorial);
- texture generation algorithms (docs, tutorial);
- quadtrees (docs, tutorial part1 and part 2);
- classes for generating random points (1D and 2D) from arbitrary distributions (docs, tutorial);
- functions for blending between images (for smooth transitions between regions in seamless tile sets) [see blend_demo.py, tutorial]; and
- functions for image quilting (under construction).
A few notes:
- The code is not optimised, and in general convenience and clarity takes precedence over speed. This code is not suitable for many applications where speed is important.
- The code will change often. At this stage I do not try to make it backwards compatible.
Python Image Code v0.6
python_image_code_v0_6.zip (593 KB)
Requires PIL (Python Image Library).
This version includes some of the dependencies that accidentally got left behind in the previous version.
(Photo by Darren Hester)
Some algorithms take a long time to return their results. Whether it is because the algorithm has to operate on a huge data set, or because it has combinatorial complexity; every time you run it you have to wait minutes or even hours for the thing to finish, making errors very expensive.
This post gives some advice on how to prototype slow algorithms with as little frustration as possible. We assume that this algorithm is being implemented experimentally – that is, you will tweak it and change it often before it is finished (it is not the kind of algorithm you type in straight from a text book). For example, I used the ideas outlined here while playing with the texture generating algorithm of the previous post.
Continue reading “5 Tips for Prototyping Slow Algorithms”