Learn PyQt: Implementing QPainter flood fill in PyQt5/PySide

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?

Raggedy fill

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-matchedbytestring.

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.

1. Start with our start pixel, fill colour, and two empty lists seen and queue.
2. Look at our current pixel's colour. This is the target for our fill. Store this initial location in queue.
3. Taking the first item from queue (initially our start (x,y) location) look at each of the 4 pixels surrounding our location (cardinal points)
4. 1. If they have not been previously seen — compare their colour to the one we're looking for.
5. If they match, add the (x,y) location to queue and update the pixel with the fill colour.
6. Add the (x,y) location to seen to keep track of where we've looked before (and avoid the overhead of looking again).
7. 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.

• PyQt5
• PySide2

python

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_()

python

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_()

QImage.pixel()

The simplest approach to identify which pixels are filled with the correct colour is to use QImage.pixel(). This accepts an x and 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 QColor.

python

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.

python

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 QPixmap.

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.

python

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)]

The set() named 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.

The 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.

python

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.

python

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 x and 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 queue and 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.

x	y	Area	Time (s)
500	10	5000	0.0145067
500	50	25000	0.0726196
500	100	50000	0.1422842
500	500	250000	0.7466553
500	1000	500000	1.5315427
500	5000	2500000	7.8900651

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).

Flood fill result at 500x10 pixels

You can opt to save the images on each iteration if you like, in order to check they are working.

python

self.pixmap().save(<filename>)

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.

Python bytestring

We should be able to get a considerable increase in speed by removing the calls to .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.

Helpfully QImage provides a method .bits() to return the image as bits, which we can convert to a bytestring using .asstring() (PyQt5) or .tobytes() (PySide2). This results in a bytestring of w * h * 4 bytes — 4 bytes per pixel, of RGBA.

• PyQt5
• PySide2

python

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)

python

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.

With our 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.

python

# 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 s[i:i+3].

The main loop is modified to use our new get_pixel method, but there are no other changes necessary.

python

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.

x	y	Area	Time (s)
500	10	5000	0.0000757
500	50	25000	0.0001531
500	100	50000	0.0002526
500	500	250000	0.0009021
500	1000	500000	0.0017306
500	5000	2500000	0.0075104

Boolean bytestring

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 queue and have_seen with pixel locations.

To generate a boolean-byte-per-pixel representation we can use the following.

python

s = b''.join(b'\xff' if s[n:n+3] == target_color else b'\x00' for n in range(0, len(s), 4))

The get_pixel method can be modified to remove the *4 multiplier, since we now only have a single byte per pixel.

python

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 True or False respectively.

python

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.

x	y	Area	Time (s)
500	10	5000	0.5358033
500	50	25000	0.105307
500	100	50000	0.052575
500	500	250000	0.009535
500	1000	500000	0.0049397
500	5000	2500000	0.001065

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 QImage.pixel() method.

Performance

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.

Duration of flood fill for each algorithm

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.

Testing the bytestring algorithm further, we can reach 50000 pixels before the algorithm duration reaches > 100 ms and 500000 before it rises above 1 second.

from Planet Python
via read more