Building Piecasso (a PyQt5 Paint clone) I was disappointed to discover that while QPainter comes with a huge number of paint methods, ranging from pixels and lines to fully-filled polygons, it doesn't include a method for flood filling regions of an image.
That makes a lot of sense, firstly because flood-filling is slow to do — requiring a pixel-by-pixel search through an image — and it's not that useful when drawing a UI, since you usually (and probably should) know what you're drawing and where.
Still, I was disappointed there wasn't one, because I needed one for my app. What's Paint without being able to fill raggedy shapes in horrible colours?
In this short walkthrough I'll cover the process of implementing a basic flood-fill algorithm in PyQt5, first using
QImage.pixel() and then using a significantly faster Python
bytestring approach, and a more memory efficient pre-matched
If you find yourself needing flood fill in your own apps, one of these will do the trick.
Flood fill algorithm
The implementation here uses a basic Forest Fire flood fill algorithm. In this approach we start from any given pixel, and iteratively check if any adjacent pixels match, and then any adjacent pixels of those pixels, and …so on. Once we've tested a given pixel we don't need to return to it so we can colour it with our target colour.
This is analogous to a forest fire which starts from a given point and spreads outwards, but will not return to areas it's already "burnt" (changed colour). The following animation gives a good visualisation of the process.
The steps of the algorithm are explained below.
- Start with our start pixel, fill colour, and two empty lists
- Look at our current pixel's colour. This is the target for our fill. Store this initial location in
- Taking the first item from
queue(initially our start (x,y) location) look at each of the 4 pixels surrounding our location (cardinal points)
- If they have not been previously seen — compare their colour to the one we're looking for.
- If they match, add the (x,y) location to
queueand update the pixel with the fill colour.
- Add the (x,y) location to
seento keep track of where we've looked before (and avoid the overhead of looking again).
- Repeat from step 3, until the queue is empty.
You can opt to check 8 directions, if you want to be able to fill through diagonal gaps.
The order you visit pixels will change depending on whether you add new locations to the beginning or end of your
queue list. But this won't affect the result.
Below we'll look at implementing this algorithm in Python, using PyQt5/PySide2. The
fill methods described below can each be inserted into the following app skeleton if you want to test them yourself.
from PyQt5 import QtCore, QtGui, QtWidgets from PyQt5.QtGui import QPainter, QPen, QColor from PyQt5.QtCore import QPoint FILL_COLOR = '#ff0000' class Window(QtWidgets.QLabel): def __init__(self, *args, **kwargs): super(Window, self).__init__(*args, **kwargs) p = QtGui.QPixmap(dim, 500) p.fill(QtGui.QColor('#ffffff')) # Fill entire canvas. self.setPixmap(p) self.fill(0, 0) def fill(x, y): # ... see below .. app = QtWidgets.QApplication(sys.argv) w = Window() w.show() app.exec_()
from PySide2 import QtCore, QtGui, QtWidgets from PySide2.QtGui import QPainter, QPen, QColor from PySide2.QtCore import QPoint FILL_COLOR = '#ff0000' class Window(QtWidgets.QLabel): def __init__(self, *args, **kwargs): super(Window, self).__init__(*args, **kwargs) p = QtGui.QPixmap(dim, 500) p.fill(QtGui.QColor('#ffffff')) # Fill entire canvas. self.setPixmap(p) self.fill(0, 0) def fill(x, y): # ... see below .. app = QtWidgets.QApplication(sys.argv) w = Window() w.show() app.exec_()
The simplest approach to identify which pixels are filled with the correct colour is to use
QImage.pixel(). This accepts an
y coordinate and returns the colour at the given coordinates. There are two methods available — one to return the colour of the pixel as
QRgb object, one as a
QImage.pixel(x, y) # returns a QRgb object QImage.pixelColor(x, y) # returns a QColor object
Unfortunately, both are a bit slow. This isn't too surprising, since each time we call
.pixel() PyQt5 must call out to Qt to get the actual data and then must construct the appropriate Python
QRgb object for return.
Below is an implementation of the fill algorithm described above using direct pixel access via
QImage.pixel. We'll use this to generate some timings.
image = self.pixmap().toImage() w, h = image.width(), image.height() # Get our target color from origin. target_color = image.pixel(x,y) have_seen = set() queue = [(x, y)] def get_cardinal_points(have_seen, center_pos): points =  cx, cy = center_pos for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)]: xx, yy = cx + x, cy + y if (xx >= 0 and xx < w and yy >= 0 and yy < h and (xx, yy) not in have_seen): points.append((xx, yy)) have_seen.add((xx, yy)) return points # Now perform the search and fill. p = QPainter(self.pixmap()) p.setPen(QColor(FILL_COLOR)) while queue: x, y = queue.pop() if image.pixel(x, y) == target_color: p.drawPoint(QPoint(x, y)) # Prepend to the queue queue[0:0] = get_cardinal_points(have_seen, (x, y)) # or append, # queue.extend(get_cardinal_points(have_seen, (x, y)) self.update()
This code fragment will work as-is on a
QLabel widget which is displaying a
QPixmap image (returned by
self.pixmap()). However you can modify it to work on any
First we get an image representation of the
QPixmap, so we can perform the
.pixel() lookup operation. Then we get the dimensions, to determine the limits of our search, and finally, the target colour — taken from the pixel where we start the fill.
image = self.pixmap().toImage() w, h = image.width(), image.height() # Get our target color from origin. target_color = image.pixel(x,y) have_seen = set() queue = [(x, y)]
have_seen is used to track pixels that we've already visited, and therefore do not need to revisit. This is technically not neccessary since pixels we've visited will be recoloured and no longer match the original point, but it's quicker.
This is necessary in our later implementations that do not query the image directly.
queue holds a list of
(x, y) tuples of all locations that we still need to visit. The
queue is set to our initial fill position, and
have_seen is reset to an empty set.
To determine what to put in the queue, we call the method
get_cardinal_points which for a given position looks at all surrounding positions — if they haven't been looked at yet — and tests whether it is a hit or a miss.
def get_cardinal_points(have_seen, center_pos): points =  cx, cy = center_pos for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)]: xx, yy = cx + x, cy + y if (xx >= 0 and xx < w and yy >= 0 and yy < h and (xx, yy) not in have_seen): points.append((xx, yy)) have_seen.add((xx, yy)) return points
If it's a hit, we return that pixel to look and fill later. The result of this method is added to the
queue in the main loop of the search.
while queue: x, y = queue.pop() if image.pixel(x, y) == target_color: p.drawPoint(QPoint(x, y)) # Prepend to the queue queue[0:0] = get_cardinal_points(have_seen, (x, y))
This loops over the current queue, which is constantly expanding. Each loop it removes the first element
y positions, checking the pixel at that location. If it is a match, we draw our fill colour. Finally, we check all cardinal points of the current location, updating the
have_seen as appropriate.
Below is a table showing the time taken to fill an area of the given size (in pixels) using this algorithm.
As you can see, at smaller fill areas the speed is reasonable, although still not fast. If you run the code, you'll see the following image only (the final 500x10 run).
You can opt to save the images on each iteration if you like, in order to check they are working.
Filling an area of 500 x 100 pixels takes > 100 ms while a 500 x 5000 pixel region takes almost 8 seconds. The majority of time during the fill is spent on the call to
.pixel(). In the next algorithm we'll replace this call with Python operations on a
bystestring representation of the image.
We should be able to get a considerable increase in speed by removing the calls
.pixel() and thereby avoiding creating the
QRgb objects (and popping in and out of Qt entirely). To do this we need a representation of the image in Python, and the
bytestring (a raw block of byte data) is an ideal candidate.
QImage provides a method
.bits() to return the image as bits, which we can convert to a
.asstring() (PyQt5) or
.tobytes() (PySide2). This results in a
w * h * 4 bytes — 4 bytes per pixel, of RGBA.
image = self.pixmap().toImage() # Convert to image if you have a QPixmap w, h = image.width(), image.height() s = image.bits().asstring(w * h * 4)
image = self.pixmap().toImage() # Convert to image if you have a QPixmap w, h = image.width(), image.height() s = image.bits().tobytes()
The format itself is unimportant, as we're only interested in whether a given series of bytes matches the bytes of our start pixel.
bytestring representation ready, our next task is to implement our own version of the
.pixel() method used to return the value of a given pixel.
# Lookup the 3-byte value at a given location. def get_pixel(x, y): i = (x + (y * w)) * 4 return s[i:i+3] # Get our target color from origin. target_color = image.pixel(x,y) target_color = target_color.to_bytes(4, byteorder='big')
To get the pixel value we calculate the current x, y location in the byte string — each pixel is 4 bytes long. We then return the data for that pixel, a
bytestring of 4 bytes in length, to compare against our
target_color, in the same format.
If you don't care about the transparency of the given pixel, you can get only the first 3 bytes using
The main loop is modified to use our new
get_pixel method, but there are no other changes necessary.
while queue: x, y = queue.pop() if get_pixel(x, y) == target_color: p.drawPoint(QPoint(x, y)) queue.extend(get_cardinal_points(have_seen, (x, y)))
The resulting times for this algorithm are shown below.
If memory is a concern, you can optionally down-sample the
bytestring representation to a single-byte per pixel, or even single-bit per pixel based on pre-matching. This still requires you to have a copy of the image in memory temporarily, but before you start extending the
have_seen with pixel locations.
To generate a boolean-byte-per-pixel representation we can use the following.
s = b''.join(b'\xff' if s[n:n+3] == target_color else b'\x00' for n in range(0, len(s), 4))
get_pixel method can be modified to remove the
*4 multiplier, since we now only have a single byte per pixel.
def get_pixel(x, y): i = (x + (y * w)) return s[i]
And finally, in the main loop, the return value of
get_pixel no longer needs to be compared to our target colour, since we've done that already. The return value is 255 or 0 which Python will interpret as
while queue: x, y = queue.pop() if get_pixel(x, y): p.drawPoint(QPoint(x, y)) queue[0:0] = get_cardinal_points(have_seen, (x, y))
Testing this algorithm gives the following performance numbers.
You'll notice that performance is slower, versus the
bytestring implementation,. This is because we now perform an extra loop over the data while reducing it to boolean bytes. However, it is still faster than the
The plot below shows the timings of each method relative to each other, lower values on the y axis Time (s) is better. The y axis is logarithmic for clarity.
As you can see, all algorithms grow linearly with the fill area (i.e. by the number of pixels) as would be expected given we perform a pixel-by-pixel search over the filled area. The
bytestring algorithm however performs significantly better by eliminating the overhead of calling out to
QImage.pixel() for each test.
bytestring algorithm further, we can reach 50000 pixels before the algorithm duration reaches > 100 ms and 500000 before it rises above 1 second.