Faster, faster!

In the preceding post I described the fairly naive algorithm I've been using to find the white borders of a scanned page's image, in order to automatically scale it to fill the image display window. The time taken to scan about a million white pixels was rather distressingly long. In fact it was worse than I described there.

A New Baseline

I was testing the find_image_margins() function by calling it through the profiling function: cProfile.run('find_image_margins(qimage)', 'profdata') but I hadn't actually looked at the margins it was returning. When I did look, I discovered that the left margin was only 2, when to the eye it should be at least an inch-worth, 150 or more. So I looked closer at the test image and found there was a little patch of black at the extreme lower left corner. The test image originally had some black crud on the left side and I'd cleaned it up in Photoshop but had missed this little patch.

As a result, at the end of the first inner loop, from the middle of the left side down, it found an unrealistically small left margin of 2. Then the second inner loop, from the top to the middle, never looked past pixel 2, which made it unrealistically fast.

After erasing the speck on the image, I made one logical change to the inner_loop code. When it stops, it has found a black patch 3 pixels wide, and its margin variable indexes the innermost pixel of that patch. It was returning that value, but it ought to return the index of the outermost pixel of the three. So it now read:

        pa, pb = 255, 255 # virtual white outside column
        for row in row_range:
            for col in range(col_start, margin, col_step):
                pc = color_table[ ord(bytes_ptr[row+col]) ]
                if (pa + pb + pc) < 24 : # black or dark gray trio
                    margin = col # new, narrower, margin
                    break # no need to look further on this row
                pa, pb = pb, pc # else shift 3-pixel window
        return margin - (2*col_step) # allow for window width

With that change and a realistic test image, cProfile now returned the following numbers:

         1171608 function calls in 2.348 seconds
   Ordered by: internal time
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        4    2.282    0.571    2.348    0.587 imagetest.py:20(inner_loop)
  1171591    0.066    0.000    0.066    0.000 {built-in method ord}
        1    0.000    0.000    2.348    2.348 imagetest.py:12(find_image_margins)

Bottom line: 2.35 seconds to examine 1.17 million pixels.

Getting rid of ord()

One thing that bugged me about the above code is the need to take the ord() of the pixel byte, in order to use it as a list index. This is because Python, for reasons best known to itself, gives an error if you try to use a byte value as an index (and not an IndexError, either, but a typeError; try it: [1,2][b'0']). Well, what structure will accept a byte as an index? A dictionary. I changed the list comprehension that created the color table, into a dict comprehension:

    color_table = { bytes([c]): int((image.color(c) >> 8) & 255)
                     for c in range(image.colorCount()) }

The bytes() function requires an iterable, hence it is necessary to write bytes([c]), converting the scalar integer c into a list so that bytes() will make it into a scalar byte. But whatever; the extra code at this point is executed only once per color. The overhead is trivial compared to code that is executed once per pixel. That code could now read:

                pc = color_table[ bytes_ptr[row+col] ]

Using the byte returned by the voidptr directly to get a color. Did it save any time?

  ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        4    2.179    0.545    2.179    0.545 imagetestB.py:20(inner_loop)
        1    0.000    0.000    2.179    2.179 imagetestB.py:12(find_image_margins)
        1    0.000    0.000    2.179    2.179 {built-in method exec}

Yes, a little. Total time dropped from 2.348 to 2.179, a saving of about 7%. I thought and thought about some way to code the three-pixel window scan in a better way, and could not. If I've missed something, please tell me in a comment! But now I turned my attention to the other attack, reducing the number of pixels examined.

Skipping rows

To look at single pixels is to examine a page image at extremely fine detail. Is there a valid character that is less than three pixels tall? No. So why am I looking at every row? To look at every row of pixels means looking at every line of characters at least four times, more likely eight or ten times. Let's skip a few!

It turned out to be trivially easy to look at every second row of the image. Recall that the call to the inner_loop passes a range iterator:

    left_margin = inner_loop(
                    range(int(rows/2)*stride, (rows-1)*stride, stride),
                    0, int(cols/2), 1

The first argument to range is the starting value, in this case, the byte-offset to the middle row of the image. The second is the end value that the range output will never exceed. In this example, that's the offset to the last row of the image. The third is the step value, the number of bytes from one row of pixels to the next. In order to look at only every second row, I added two characters to that statement:

    left_margin = inner_loop(
                    range(int(rows/2)*stride, (rows-1)*stride, stride*2),
                    0, int(cols/2), 1

This had a good effect on the cProfile stats:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        4    1.125    0.281    1.125    0.281 imagetestB2.py:20(inner_loop)
        1    0.000    0.000    1.125    1.125 imagetestB2.py:12(find_image_margins)
        1    0.000    0.000    1.125    1.125 {built-in method exec}

From 2.179 seconds down to 1.125, a reduction of 49%. Not a surprise: do half the work, take half the time; but still, nice. And the returned margin values were almost the same.

Shrinking the image

It would be easy to try skipping three of every four rows, but that might result in missing something like a wide horizontal rule. Instead, I thought, what about scaling the image down by half, using a smooth translation? That would have something like the effect on the eye of holding the page at arm's length: shrink it and blur it but retain the outline. To run the inner loops on a half-size image would mean looking at 1/4th the pixels (half the columns of half the rows). The returned margins could be scaled up again.

I added the following code to the setup:

    scale_factor = 2
    orig_rows = image.height() # number of pixels high
    orig_cols = image.width() # number of logical pixels across
    image = image.scaled(
        QSize(int(orig_cols/scale_factor),int(orig_rows/scale_factor)),
        Qt.KeepAspectRatio, Qt.SmoothTransformation)
    image = image.convertToFormat(QImage.Format_Indexed8,Qt.ColorOnly)

I found that the QImage.scaled() method could change the format from the Indexed8 that it started with, so it was necessary to add the convertToFormat() call to restore the expected byte-per-pixel ratio. (Which meant, it was no longer necessary to enforce that format before calling this find_image_margins function.)

The rest of the setup was just as before, setting the row and column counts and the stride, but for this reduced image. The final line was no longer return left_margin, right_margin but this:

    return left_margin*scale_factor-scale_factor, right_margin*scale_factor+scale_factor

This worked, and returned almost the same margin values as before, different by only a couple of pixels, much less than 1%. And the total execution time was now 0.333 seconds, distributed as follows:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        4    0.294    0.074    0.294    0.074 imagetestC.py:20(inner_loop)
        1    0.032    0.032    0.032    0.032 {built-in method scaled}
        1    0.006    0.006    0.006    0.006 {built-in method convertToFormat}
        1    0.000    0.000    0.333    0.333 imagetestC.py:12(find_image_margins)

That was such a success, running in 30% of the previous best time, that I tried increasing the scale_factor to 4, with this result:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        4    0.167    0.042    0.167    0.042 imagetestC.py:20(inner_loop)
        1    0.031    0.031    0.031    0.031 {built-in method scaled}
        1    0.001    0.001    0.001    0.001 {built-in method convertToFormat}
        1    0.001    0.001    0.001    0.001 imagetestC.py:52(<dictcomp>)
        1    0.000    0.000    0.200    0.200 imagetestC.py:12(find_image_margins)

Total time of 0.2 seconds. That's a reduction of only 1/3 from the scale factor of 2, so clearly we are having diminishing returns. But the total is now only 8% of the execution time of the original algorithm. Not too shabby! The returned margins were still the same. The total time is now small enough that the contribution of the dictionary comprehension for the color table is noticeable. And the largest component, after the inner loop, is the QImage.scaled() call.

This is fast enough that there should be no objectionable delay on clicking the To Width button, even on slow hardware. I will proceed to integrate this into the imageview module and its unit-test. When that's done, I will be able to proceed to a preliminary version of the main window!

Scanning the pixels

Last post I described how you can get a "voidptr" through which you can PEEK the bytes of an image. This is needed to implement zoom-to-width and zoom-to-height buttons on the imageview. The code that I wrote for this in V.1 never felt right. It's a pure CPU-burning FORTRAN-style loop process; even more so than the character or word census of a large text. The scan image for a typical page is several megapixels (the test image used below is about 1800x2700, or 5Mpx) and the only process I could find for determining the margin has to access a good fraction of them. Clicking "To Width" or "To Height" on an older laptop incurs a noticeable pause of a second or more. I want to shorten that.

(Note that in what follows, the code for to-width and to-height is virtually the same, just substituting "top" and "bottom" for "left" and "right". I'm writing about to-width; whatever lessons I learn are immediately applicable to to-height.)

Starting point

Let's look at the code as it is now. The point is to find out how much of the left and right margins of the image are all-white, then scale and center the image to exclude them. To find the left margin, I look at the pixels of each row from left to right, stopping at a black spot. Once I've found a black spot, I never have to scan farther to the right than that point. I keep going to successive rows, hoping to find a black spot even more to the left. After looking at all rows I know the pixel count to the left of the leftmost black spot. The same logic applies to the right margin: look at all rows from right to left, in order to find the rightmost black spot.

An early complication was that finding a single black pixel threw up false positives. Scan images often have one-pixel, even two-pixel "fly specks" outside the text area. So I modified the code to stop only on a dark spot of at least 3 pixels, which added some overhead. I added a heuristic. Noting that many pages have large white areas at the top and bottom, I started the scan with the middle row, hoping to quickly find some black pixels nearer the left margin.

The following code is heavily rewritten and refactored. You can view the original if you like, but don't bother. The original has four nearly-identical loops for scanning the left margin, middle to end then top to middle, then the right margin the same. These loops—I realized yesterday—differ only in the start, stop and step values of their controlling ranges. So I factored the inner loops out to this:

    def inner_loop(row_range, col_start, margin, col_step):
        '''
        Perform inner loop over columns of current margin within rows of
        row_range. Look for a better margin and return that value.
        '''
        pa, pb = 255, 255 # virtual white outside column
        for row in row_range:
            for col in range(col_start, margin, col_step):
                pc = color_table[ ord(bytes_ptr[row+col]) ]
                if (pa + pb + pc) < 24 : # black or dark gray trio
                    margin = col # new, narrower, margin
                    break # no need to look further on this row
                pa, pb = pb, pc # else shift 3-pixel window
        return margin

The key statement is pc = color_table[ ord(bytes_ptr[row+col]) ]. From inside, out: bytes_ptr[row+col] peeks the next pixel value which is an index into the color table. ord() is needed because the voidptr access returns a byte value and (for reasons that escape me) Python will not permit a byte type as a list index. The color_table is a list of the possible GG values from RRGGBB, smaller numbers being darker. I'll talk about it in a minute.

The operation of this code should be fairly clear: slide a 3-pixel window along the pixels of one row up to a limit; when they comprise a dark spot, break the loop and set a new, more stringent limit. Return the final limit value.

Now let's look at the code that sets up for and calls that inner loop.

def find_image_margins(image):
    '''
    Determine the left and right margin widths that are (effectively)
    all-white in an image, returning the tuple (left,right). The image is
    presumed to be a scanned book page in the Indexed-8 format, one byte per
    pixel, where a pixel value is an index into a color table with 32-bit
    entries 0xAARRGGBB (AA=alpha channel).
    '''
    rows = image.height() # number of pixels high
    cols = image.width() # number of logical pixels across
    stride = (cols + 3) & (-4) # scan-line width in bytes
    bytes_ptr = image.bits() # uchar * a_bunch_o_pixels
    bytes_ptr.setsize(stride * rows) # make the pointer indexable
    # Get a reduced version of the color table by extracting just
    # the GG values of each entry. If the image is PNG-1, this
    # gives [0,255] but it could have 8, 16, even 256 elements.
    color_table = [ int((image.color(c) >> 8) & 255)
                     for c in range(image.colorCount()) ]

The first five lines of code set up the voidptr to the image bytes. The stride value is used because the Qt documentation notes that every pixel row occupies a whole number of 32-bit words.

Note the remark about the "presumed" image format? In early testing I forgot to force the image to Indexed-8. The calculation stride * rows yielded about 5MB but that was much larger than the true memory size of a compressed 1-bit PNG file. The result was that the first time the inner loop tried to access a byte of a middle row—Python seg-faulted. Yes, you can bring down, not just your own app, but the whole interpreter, by mis-using a voidptr.

If the image file is really monochrome and stored as PNG-1, the color table will have two entries. But I can't require that or assume that. It will be a PNG but it might be a PNG-8 with actual colors. So make a color table of just the GG values (Green is commonly used as a proxy for pixel brightness) and index it by the pixel value.

Now, to work:

    # Some pages start with many lines of white pixels so in hopes of
    # establishing a narrow margin quickly, start at the middle, go to
    # the end, then do the top half. Begin: left side from the middle down.
    left_margin = inner_loop(
                    range(int(rows/2)*stride, (rows-1)*stride, stride),
                    0, int(cols/2), 1
    )
    # With hopefully narrower margin, scan from the top to the middle:
    left_margin = inner_loop(
                    range(0, int(rows/2)*stride, stride),
                    0, left_margin, 1
                    )
    # Now do exactly the same but for the right margin, taking columns
    # from the rightmost, inward.
    right_margin = inner_loop(
                    range(int(rows/2)*stride, (rows-1)*stride, stride),
                    cols-1, int(cols/2), -1
                    )
    right_margin = inner_loop(
                    range(0, int(rows/2)*stride, stride),
                    cols-1, right_margin, -1
                    )
    return left_margin, right_margin

Each call to the inner loop passes a range of rows to examine—in the form of pre-calculated byte offsets—and the three factors for a range of columns. The end result is the width of the white margins of the page.

Timings of this code

When I use the ctime package to time one application of find_image_margins() to a representative page image, I get these not awfully helpful stats:

         871938 function calls in 1.921 seconds
   Ordered by: internal time
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        4    1.815    0.454    1.921    0.480 imagetest.py:20(inner_loop)
   871922    0.106    0.000    0.106    0.000 {built-in method ord}
        1    0.000    0.000    1.921    1.921 {built-in method exec}
        1    0.000    0.000    1.921    1.921 imagetest.py:12(find_image_margins)

The remaining lines are all-zero times. So: running under cprofile, this takes almost two seconds to run. On a 2.8GHz CPU, that's roughly six billion instructions. Wow! This would have been completely infeasible on, say, my old Mac Plus where it would have taken something like 20 minutes to complete on its 8 megahertz CPU. On my current Macbook Pro, it's a minor annoyance.

The count of 871,922 calls to ord tells how many pixels were examined in the inner loop. The total time of 1.815 tells how much time the inner loop spent on those pixels, or about 108,000,000 microseconds on 900,000 pixels giving 120 microseconds per pixel examined.

Optimizing

I see two approaches to optimizing this program. One: reduce the 120μsec spent in the inner loop on each pixel. Two: reduce the number of pixels examined in the inner loop. Reducing either number by half would halve the program execution time.

I believe I will spend a bit of time exploring both approaches, and report in the next post.