Premature Optimization is the Root of All Evil

Since it is so often used as an excuse to pessimize, here’s the full quote:

There is no doubt that the grail of efficiency leads to abuse. Pro­gramm­ers waste en­orm­ous amounts of time think­ing about, or wor­ry­ing about, the speed of non­crit­ical parts of their pro­grams, and these at­tempts at ef­ficien­cy ac­tual­ly have a strong negative im­pact when de­bugg­ing and main­tenan­ce are con­sidered. We should for­get about small ef­ficien­cies, say about 97% of the time: pre­ma­ture opt­imiza­tion is the root of all evil.

Yet we should not pass up our op­por­tunit­ies in that crit­ical 3%. A good programmer will not be be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. […]

Donald Knuth, Structured Programming with go to statements

Low Level C++

Alex Darby over on AltDevBlogADay has written a wonderful series of blog posts that explains in great detail how C++ code translates into assembler (and back). After covering the basics the current post discusses user defined types and explains how types are laid out in memory.

Note: While Alex uses Visual Studio, you can get similar output on Linux with the objdump utility. In order to see the generated intel assembler output intermixed with the source code just execute:

objdump --demangle --line-numbers --source
        --disassembler-options=intel <executable>

Update [2013-07-24]: The g++ compiler supports a --dump-class-hierarchy flag which can be used as a replacement for Visual Studio’s /d1reportSingleClassLayout. If given, g++ will write information to a .class file for each source file, like memory layout, alignment, virtual method tables, …. It is worth piping these files through the c++filt tool before reading.

Update [2013-12-06]: I just learned that the clang compiler also supports dumping the memory layout using clang -cc1 -fdump-record-layouts source.cpp.

Rescue Bad Scans With Morphological Operations

We now have these nifty copying machines that allow you to save scanned pages to a PDF document instead of printing them. Using Acrobat Pro, it is very easy to turn these scans into fully searchable PDFs. Much better than simple paper copies. So, last time I wanted to keep some pages of a book for reference, guess what I did.

Unfortunately, after returning the book to the library I discovered that the default settings of the copier try to save space and produce heavily pixelated black and white images. The text is nearly unreadable. Zooming in to 200%, the scan looks like this:

Bad scan

Nevertheless, the problem can be fixed using morphological operations which are readily available in OpenCV. After applying a closing operation (a dilation followed by an erosion) with a small circle as structuring element the image already looks much better (pixels added by the closing highlighted in red):

Scanned image after closing operation

As you can see, the closing operation fills all the tiny gaps but keeps the shape of letters intact. Finally, I applied a small blur filter and then increased the contrast to get nice, smooth edges. Here is a comparison of the scan before and after the repair:

Scan before and after repair

Now, that is something I can live with. And all of this can be done in just a few lines of code:

#!/usr/bin/env python
import sys
import cv2
import numpy as np
 
kernel = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (3, 3))
 
for filename in sys.argv[1:]:
    print "Processing {0:s}n".format(filename)
 
    # read image as grayscale:
    img = cv2.imread(filename, 0)
 
    # close gaps:
    cv2.erode(img, kernel, img)
    cv2.dilate(img, kernel, img)
 
    # blur and then increase contrast to get smooth edges:
    img = cv2.GaussianBlur(img, (5, 5), 0)
    tmp = (img.astype('int32') - 25) * ((255 + 50) / 255.0)
    np.clip(tmp, 0, 255, out=tmp)
    img = tmp.astype('uint8')
 
    cv2.imwrite(filename, img)

Simple Transparency in OpenCV

Transparent circles

OpenCV’s drawing functions for geometric primitives like lines and circles regrettably do not support alpha-transparency. As workaround, the documentation remarks that one should paint to a separate buffer and then blend this buffer with the main image. But how does this work in practise?

A convenient way to blend images is via the addWeighted function (there is an explanation of image overlays on AI Shack that basically reimplements addWeighted by hand). To get standard transparency, simply make sure the weights add up to 1. Here’s the code I used to create the image above:

#!/usr/bin/env python
import cv2
 
img = cv2.imread('lena.png')
 
# (1) create a copy of the original:
overlay = img.copy()
# (2) draw shapes:
cv2.circle(overlay, (133, 132), 12, (0, 255, 0), -1)
cv2.circle(overlay, (166, 132), 12, (0, 255, 0), -1)
# (3) blend with the original:
opacity = 0.4
cv2.addWeighted(overlay, opacity, img, 1 - opacity, 0, img)
 
# display result (press 'q' to quit):
cv2.namedWindow('Transparency')
cv2.imshow('Transparency', img)
while (cv2.waitKey() & 0xff) != ord('q'): pass
cv2.destroyAllWindows()

What’s important about this method is to start the overlay buffer with a copy of the original, not with a blank image. With this neat little trick, all points that are not affected by the drawing operations will retain their color. Otherwise, they are blended with the background color of the overlay buffer.

Pushing a git Repository to Subversion

I’m currently listening to a lecture at university that requires solutions to be submitted to a subversion server. While subversion has its merits, I usually prefer git to satisfy my version control needs. I really like git’s staging area and all the flexibility it comes with (like rewriting local history with interactive rebase and such). Luckily, git can work together with a subversion server via git svn so that it is possible to have the best of both worlds.

As the people at university set up our svn accounts a week after the tutorials started, I already had a local git repository. How to push an existing git repository to a remote svn is explained on Stack Overflow, of course, but without some extra care messes up the author information. To get the authors right, you need to create an authors files that maps svn to git users. So, inside the local repository create a file, say authors.txt. Each line of this file should be an entry of the form:

svnuser = Git User <gituser_email>

Here, “Git User” is the name that appears in your git logs. Once you have created the authors file, inside the local repository run:

git config svn.authorsFile authors.txt
svn mkdir --parents svn://server/path/to/repo/PROJECT/trunk -m "Import."
git svn init --stdlayout svn://server/path/to/repo/PROJECT
git svn fetch
git svn rebase trunk
git svn dcommit

If the remote svn repository isn’t empty, you might have to fix some merge conflicts after the rebase. For me, it just worked.

Note: dcommit replaces the timestamp of each commit inside your local history with the time the commit gets pushed to svn. Although this needs a bit getting used to, there are good reasons for this behaviour.