Stories
Slash Boxes
Comments

SoylentNews is people

SoylentNews is powered by your submissions, so send in your scoop. Only 19 submissions in the queue.
posted by janrinok on Sunday September 25 2016, @02:09AM   Printer-friendly
from the how-it's-done dept.

Following up on NCommander's recent "original content" series, I decided to write up a bit about a recent thesis I supervised. Full disclaimer: I supervised this thesis and I'd like to see the thesis results being used more widely.

Introduction
In 2013, the nation-wide exams for primary schools somehow leaked onto the streets and were being traded over the internet. One newspaper reporting on it showed a blurred page of the exam questions 5 days before the exam was to take place. This made me wonder: would it be possible to recover the exam questions from that blurred photo?

Fast-forward one bachelor thesis investigating this (resulting in a 3/4ths complete plugin) and a few years. A team of BSc students is interested in picking up the deblurring project. Previous experience showed that asking one student to pick this up for a BSc thesis is a lot, but at my current institute BSc theses are done in teams. Challenging, but why not?

The original assignment was to implement Cho's algorithm for deblurring [Cho et al 2013] as a GIMP plugin. The previous bachelor thesis had found this algorithm as the best deblurring algorithm for recovering text. However, time marches on. During the literature review phase, the team came across some advances in deblurring. Moreover, the algorithm's description in the paper was incomplete, and patented. (Interestingly enough, the patent did not clarify the incompleteness.) There was a new algorithm by Pan et al [Pan et al 2014] that was simpler, faster, and: open source. However, the original was coded in Matlab, which is (1) proprietary, (2) not freely available, and (3) not in much use by people who want to edit pictures.

So, the team investigated both algorithms in great (and hairy) detail, and implemented Pan et al's algo as an open source GIMP plugin. This required a working understanding of the maths involved (which is not explicitly taught in the Bachelor programme). Moreover, the end result is a sleek piece of work, showcasing the team's CS creds as well.

Below, a tiny bit about how blurring works, and how to deblur. I'll skip most of the maths, promised.

[Continues ...]

Blurring
Blurring is an operation on a digital image. We can represent each pixel by a value (rgb, grayscale, etc.). For example (marking one pixel for blurring):

145 167 222 255 255 255
109 112 216 255 243 248
124 131 143 128 232 201
145 167 140 198 196 203
113 125 132 162 178 193

For each pixel in the output image, its value is computed by a weighted average of the neighboring pixels in the input image. In typical Gaussian blur, the pixel under consideration is given the heighest weight, and weights for pixels further away lower with distance to this pixel.
There are two parameters: how many neighbors to consider, and how to distribute the weights. For example, if you take into account all neighbors one pixel away (including diagonal), you could assign the central pixel a weight of 40%, the neighbors up/down/left/right weights of 10%, and the diagonal neighbors weights of 0.05%:

0.05 0.10 0.05
0.10 0.40 0.10
0.05 0.10 0.05

This matrix is called the kernel. The one here is for a Gaussian blur ("a bit vagued up" if you will). If we use it to blur the marked pixel (original value: 143), we put the kernel's center on the pixel under consideration and then just multiply all weights and add the result together. Overlaying results in the following:

0.05 * 112 0.10 * 216 0.05 * 255
0.10 * 131 0.40 * 143 0.10 * 128
0.05 * 167 0.10 * 140 0.05 * 198

And adding all these together should result in 155.3 (rounded to 155).

Of course, other kernel sizes and other distributions are possible. Another typical class of blur is motion blur - the blur you'd get in the background if you take a photo of a racecar while keeping the racecar focused. While weights in a Gaussian blur trail off (sort of) circular around the pixel that will be blurred, in motion blurring the main weights are distributed in the direction of motion - usually left to right or vice versa.

How to deblur
Blurring can be expressed as: Y = X * K + n.
Here, X is the input image, Y the output image, K the kernel, n a noise factor and '*' is a mathematical operation called convolution. Deblurring is then a matter of inverting this, i.e. deconvolution. Deblurring if you don't know the kernel used originally is called blind deconvolution. There's tons of works about this. What we're interested in is recovering text from blurred images. So perhaps there's a way to use specific properties of text to "help" the blind deconvolution?

This is what Cho et al's algorithm did. It used the fact that text has high contrast (e.g. black on white). Of course, not all such stark contrasts are text. Cho et al used an algorithm to determine the "stroke width" - the width of each stroke of the letters. If this was fairly consistent, then this was probably a letter.

Of course, if you're looking for strokes in the picture, your process slows down quite a bit. Interestingly enough, a follow-up algorithm by Pan et al does not use specific features of text, but still improves upon the algorithm of Cho et al.

Both algorithms follow roughly the same outline: First, a kernel is estimated and then a preliminary deblur image is computed. The preliminary result is used to improve the kernel estimate, etc. etc.. Finally, the final kernel estimate is applied to the original input image -- the preliminary images help reveal details about contrast, but ruin the image and thus cannot be used for this step.

There's a lot more to this (Fourier transforms, gradients, Laplacian deconvolution, etc), but that goes beyond an already lengthy article. If you're interested, read the thesis or see the papers.

About the plugin
You might think it's easy to convert code from Matlab to a GIMP plugin. Well... no.
You see, Matlab comes packed to the brim with mathematical functions. GIMP plugins are coded in C, C++, or Python. So you have to use libraries for the maths functions you need. Unfortunately, some implementations of the mathematical functions needed give different results than others. The team had to discover that the hard way, and then either update their calls if they could track down the problem or implement the function themselves if they couldn't.

But that's just the mathematics - how does it work, you ask?
Well, the end result is a sleek-looking, mature plugin. You select an area, run the filter, and up pops a dialog window where you can set some parameters (e.g. kernel size estimate), and even toggle a preview function. What impressed me is that the team managed to implement a meaningful progress bar. Since the algorithm loops, and the amount of processing in each loop is not universally determined, this was pretty tricky. They ended up running a lot of test cases with timing controls embedded in the code, and found out how much progress was made in each step.
Sometimes, the progress bar pauses for a bit longer than anticipated - basically when the next portion uses more time than the generic estimate allowed.

All in all, I encourage you to download the plugin and play with it. I'll try to be around in the comments when this story runs.

Final words and links
- The GIMP plugin is available from here
- Pan et al's project page

In conclusion: there is a free, open source GIMP plugin available. The plugin could be (significantly) sped up by making use of GPU processing - but this is a finished academic project, so don't look to me for that. Interesting to note is that the project took a bit of a side step: Pan's algorithm (like Cho's) focuses mainly on deblurring uniform motion blur, not on deblurring artificially induced blur.
Given that the main difference between these is the kernel used for blurring, it's possible to update the plugin to be able to inject your own specially crafted kernel estimate to be used for deblurring. Basically, instead of the algorithm estimating a blur kernel, you just supply it. That would enable it to be used for the originally intended purpose.

Be that as it may, I'm (more than) happy with the result, and hope that others will make use of this plugin.


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 0) by Anonymous Coward on Sunday September 25 2016, @02:27PM

    by Anonymous Coward on Sunday September 25 2016, @02:27PM (#406261)

    On Ubuntu 16.04 It fails during "make" with...
    make[2]: *** No rule to make target '@ALL_LINGUAS@.po', needed by '@ALL_LINGUAS@.gmo'. Stop.
    make[2]: Leaving directory '/home/trunk/po'
    Makefile:728: recipe for target 'all-recursive' failed
    make[1]: *** [all-recursive] Error 1
    make[1]: Leaving directory '/home/trunk'
    Makefile:422: recipe for target 'all' failed
    make: *** [all] Error 2

  • (Score: 2) by FakeBeldin on Sunday September 25 2016, @05:40PM

    by FakeBeldin (3360) on Sunday September 25 2016, @05:40PM (#406323) Journal

    Hmms. First thing that comes to mind (and that forgot in the install description) is that OpenCV is not installed.
    I've updated the install description for that.
    If it's not that, I'd like to hear.

    • (Score: 1) by gtomorrow on Sunday September 25 2016, @06:41PM

      by gtomorrow (2230) on Sunday September 25 2016, @06:41PM (#406344)

      I realise this isn't the place for FAQs, issues and whatnot but since yr asking...

      I tried to install this on my iMac and my Ubuntu laptop, OpenCV already installed on both. Both stopped after the ./configure with the following:

      checking for GIMP... no
      configure: error: Package requirements (gimp-2.0 >= 2.2.0 gimpui-2.0 >= 2.2.0) were not met:
      No package 'gimp-2.0' found
      No package 'gimpui-2.0' found
      Consider adjusting the PKG_CONFIG_PATH environment variable if you
      installed software in a non-standard prefix.
      Alternatively, you may set the environment variables GIMP_CFLAGS
      and GIMP_LIBS to avoid the need to call pkg-config.
      See the pkg-config man page for more details.

      I have GIMP 2.8 installed on both. I can kind of understand the Mac error being how that's GIMP.app (not X11) but the Ubuntu install has all the binaries and libraries where they should be, so...hmmmm.

      Thanks.

      • (Score: 2, Informative) by Anonymous Coward on Sunday September 25 2016, @07:16PM

        by Anonymous Coward on Sunday September 25 2016, @07:16PM (#406361)

        You have to install libgimp2.0-dev in order to install gimp plugins from source.

    • (Score: 0) by Anonymous Coward on Sunday September 25 2016, @08:38PM

      by Anonymous Coward on Sunday September 25 2016, @08:38PM (#406384)

      OpenCV is already installed.

      • (Score: 0) by Anonymous Coward on Monday September 26 2016, @09:13PM

        by Anonymous Coward on Monday September 26 2016, @09:13PM (#406747)

        Well... After a few days of tinkering around trying to get this installed on 2 different Ubuntu computers, it's time to throw in the towel. Any chance of packaging this up as a GIMP drop in, or a snap package? I'm sure a lot of GIMP users that migrated away from Photoshop (and Windows) would be very interested in this.

        • (Score: 1) by gtomorrow on Tuesday September 27 2016, @06:44AM

          by gtomorrow (2230) on Tuesday September 27 2016, @06:44AM (#406863)

          Agreed. I, for one, would've liked to see/test it. Installed OpenCV, installed libgimp2.0-dev, ended up at the same '@ALL_LINGUAS@.po' error.

        • (Score: 2, Informative) by gtomorrow on Tuesday September 27 2016, @08:13AM

          by gtomorrow (2230) on Tuesday September 27 2016, @08:13AM (#406876)

          You need intltool and liblog4c installed! Those dependencies fulfilled, BINGO!

          • (Score: 0) by Anonymous Coward on Tuesday September 27 2016, @08:15PM

            by Anonymous Coward on Tuesday September 27 2016, @08:15PM (#407081)

            I gave it another shot after installing intltool. liblog4c was already installed. The "@ALL_LINGUAS@.po" error is gone but new errors show up...

            collect2: error: ld returned 1 exit status
            Makefile:530: recipe for target 'gimp-plugin-template' failed
            make[2]: *** [gimp-plugin-template] Error 1
            make[2]: Leaving directory '/home/trunk'
            Makefile:740: recipe for target 'all-recursive' failed
            make[1]: *** [all-recursive] Error 1
            make[1]: Leaving directory '/home/trunk'
            Makefile:434: recipe for target 'all' failed
            make: *** [all] Error 2
            I give up.

            • (Score: 0) by Anonymous Coward on Tuesday September 27 2016, @11:18PM

              by Anonymous Coward on Tuesday September 27 2016, @11:18PM (#407129)

              OK, I lied... I gave it one more try on my other Ubuntu PC. It's the same Ubuntu version and software on both PCs but different processors. The one with an Intel i7 installed just fine with all the recommendations made here. The one with the crappy Intel Pentium J2900 is the one that pooped. So, I guess it's dependent on the right hardware.
              Good work!

        • (Score: 2) by FakeBeldin on Tuesday September 27 2016, @11:48AM

          by FakeBeldin (3360) on Tuesday September 27 2016, @11:48AM (#406912) Journal

          Thanks for taking the time to try it out - and thank you for letting me know about the problems.
          I'm trying to reach the original team to see if if any of them is willing to follow up on suggestions. I'll add the notes in the reply below about which tools need to be installed - apparently I missed out on a few that I installed along the way :s.

          It's curious that it's working for some and not for others...