OCR Preprocessing with the Radon Transform

At work I deal with a lot of reports that aren't particularly helpful.  All the information I need is in them, but they aren't searchable and I can't filter them.  What I'd really like is to be able to run SQL style queries against the data as if it were database.  This is even harder than it seems as the only way to access the data is via printed reports.  Apart from possibly tapping the LAN connection to the printer there is no way for me to electronically get the data.  So I thought I'd have a go at scanning the documents and using tesseract-ocr on the printed reports.  The results are quite good, but I'd like to do a little preprocessing to improve them.  For my idea to work the documents need to have text parallel to the edge of the scanned image.  This sounds like a job for the Radon Transform, an image processing technique that is ideal for finding long lines in an image.  As I can't show you the actual document because it contains company information, a test document that contains gibberish has been generated with the exact same layout.  The document has been rotated, blurred and had small amounts of noise added to it to simulate a scanned image.  Using this file the features of the Radon Transform can demonstrated and it can be shown how rotation can be detected.

All the processing was done using the open source Matlab equivalent Octave.  I initially looked at OpenCV, but there was way too much to learn to actually get a result.  Octave allows me to quickly test my ideas. The files used in this example can be found here.

Test Document with 0.6 degree rotation and noise added

The Radon transform is a powerful image processing technique that has wide ranging applications.  It's mainly used in situations where you want to detect a long line in an image.  The transform itself is quite easy to conceptually understand.  Imagine placing a series of fine parallel lines over the original image, and going along each line and adding up how much white you see.  After doing this you would end up with a series of intensity values that make up a vertical column of the Radon transform output image.  This process is repeated with the image being turned a set amount each time.  It's similar to taking multiple x-ray images of a subject on a turntable with the subject being rotated slightly between exposures.

Below is the Radon transform of the test image.  Its width is determined by how many times the image is rotated and by how much.  In this case it is rotated from 0 to 180 degrees with 0.2 degree steps.  This gives an image 901 pixels wide.  The height is determined by the maximum size experienced when rotating the image, i.e. the diagonal size of the image.  The original image is 990 x 704 pixels, this makes it 1214.8 pixels diagonally.  The output below is actually 1219 pixels across, this is a little bigger than the diagonal due to the way the transform is calculated.

Radon Transform of report from 0 to 180 degree with 0.2 degree steps

You can see some detail in the above image, but not much.  The centre of the image represents the short edge of the test page while the edges represent the long edge.  The problem with this image is that it's looking at how much white is in the test image, and no matter what direction you go in there will be a lot of white.  Even text is made of mostly white space.  This makes all values of the output look quite similar.  What we really want to look at is how much black is in the image.  The Radon transform doesn't work like that, but we can get the same effect by inverting the image before putting it through the transform.

Radon Transform of the Inverted Image

Now we're getting somewhere.  A lot more detail is visible, but there's still one more step I'd like to perform. There's quite a range of values in the image with some bright details, and some very faint ones.  To better explore the image I'm going to apply a simple dynamic compression algorithm to it.  It's important to note that all the values in the output are zero or positive.  By adding 1 and then taking the log of every pixel in the image it will make the faint details more visible.  After rescaling the data for the output image, black details will remain black, and the brightest features will still be the brightest.

Dynamic Compression applied to the Inverted Radon Transform

That's a lot better.  I explain the details in the output image in a little bit, but first I'll want to show you something I think is really cool.  Remember the first image that I said didn't show much detail?  Well, if you apply something to it called the inverse Radon transform you get back the original image.  You can see in the image below that you get a perfectly good recreation of the original image (with some artefacts).  The quality of the output image depends on the angular resolution of the Radon transform.  Now that's pretty awesome, but what's even better is that this is basically what happens in a CT scanner.  An emitter and linear detector spin around the patient taking multiple exposures.  They are then processed by a similar, but more sophisticated algorithm to produce an image of a slice through the patients body.  The quality of the final image is determined by the resolution of the linear detector and how many exposures are taken around the body.  There's a lot more too it than that, but at the core of it the concept is pretty simple.

Inverse Radon Transform of the Radon Transform

Now I'll explain the details in the image.  I've highlighted the test and the transformed images below with corresponding colours to explain the different features visible in the Radon transform.  You may need to click on the images to see more detail.

1. Green box - This encloses a line of alternating black and white features.  This indicates where the rows of text are.  Where this feature is most prominent will be used to work out how far out of parallel the input text is to the edge of the image.
2. Red centre line - This line indicates where features from text perfectly parallel to the edges of the image should appear.  In this case the features are 3 pixels to the left of this line.  This is then used to calculate the rotation angle.  3 pixels x 180 degrees / 900 pixels = 0.6 degrees.  This corresponds to how much I rotated the test image.
3. White circle - This shows the long edge as seen from the short side.  By definition this parallel to itself and is exactly in the centre of the image on the red line.
4. Yellow Box -  The brightest features on the image are caused by the long unbroken lines near the heading of the report.
5. Blue Box - These indicate the columns of numerical data on the report
6. Brown Box - These are the first 2 columns of data that contains a wide column of mainly text
7. Maroon Box - This shows a column of data that has a decimal point.  The location of the column of decimal points creates a dark spot as there are only a few dots to see in this particular orientation.

Notable Features of the transform

Notable Features on the Report

I'm still playing around with things and working out a strategy, but what I'd ultimately like to do is extract each line in the report and make it it's own image.  Using Octave under Linux it's simple to automate this behaviour so that all I need to do is drop the image in a folder and then it's automatically processed.

Hopefully you have a better idea of what the Radon transform can be used for.  This has been a lot of fun, I haven't done any image processing in a while and I've forgotten how much I love it.  The challenge of replicating what a human can easily do with their vision system is surprisingly hard and rewarding.

Testing Capacitors From a Dead Modem

A couple weeks back I started having problems with my ADSL2+ internet connection.  A lot of dropouts and slow downloads, and at times speeds lower than dial-up.  I knew what my connection was capable of, before the problems started I was getting around 14 Mb/s downloads and after it was around 3 Mb/s at best, so I knew that the distance from the phone exchange had nothing to do with my issues.

After several phone calls to my provider, TPG, and going though their frustrating isolation tests and checking cables they confirmed that there was fault on the line and they'd send a technician out to investigate.  While waiting, I decided to replace the modem.  It was old and I wanted to make sure that the problem wasn't on my end.  After removing the old modem and setting up the new one, the connection was still slow, so I decided to reconnect the old one until the issue was sorted.  After turning it on all I got was flashing lights.  I'd had this problem before, leave the modem on for a couple of minutes, power cycle it, and it would start working.  This time, no luck, it just wouldn't start.  I put the new modem back in and threw the old one in the corner for the time being.  I suspected the capacitors in it were dead.

Old NetComm NB6Plus4W modem

Old NetComm NB6Plus4W modem

Old NetComm NB6Plus4W modem

After the technician came out and fixed the line fault, I still didn't have a decent connection.  One more phone call to TPG and things were back to normal.  The last phone call involved a troubleshooting step that required me to plug my phone line into the network port to reset my firmware.  Yeah, it sounded dodgy to me too, there can be over 100 V on the phone line when ringing, but after two weeks of almost no internet connection I was willing to sacrifice a modem on the off chance it'd work.  I figured the designers of these things anticipate that at some point someone would accidentally plug the phone line into the network port and there would be appropriate protection in place.  Surprisingly this worked.  It doesn't sit well with me though.

I still don't know what the real problem with the connection was, it's unusual for two things to fail at once.  If I had to guess, I'd say that the suspected dead capacitors in the modem created noise on the line that caused it to switch to a low speed profile.  As for TPG finding a fault and getting it fixed, if you look long enough you'll find something wrong and something to fix, but to be honest I don't really know, I'm just happy things are working again.  That old modem was bugging me though, I needed to know what went wrong.  Time for a tear down.

Let's go through and see what does what on the PCB.

1. Power supply.  It takes a 12V AC input, rectifies and filters it to about 15.5 Volts DC.  Two MP1410 step down converters provide 1.8 and 3.3 Volt rails
2. Ethernet sockets and associated isolation transformers.  I suppose plugging in a phone cable wouldn't actually hurt the device
3. USB input.  You can see the traces coming out of it and heading to the main processor
4. Phone line input and transformer
5. Broadcom BCM5325EKQMG Ethernet switch
6. 7805 5 Volt regulator and Broadcom 6301KSG ADSL line driver
7. Elpida DS1216AGTA 128 Mbit SDRAM - working memory
8. Broadcom BCM6348KPBG single chip ADSL2+ controller
9. Samsung k8d3216UBC 32 Mbit Flash Memory - non volatile memory to hold software
10. Broadcom BCM4318KFBG 802.11 b/g transceiver
11. Skyworks SE2521A60 Wireless LAN front end.  Power amplifier and associated RF functions

Modem PCB Top Side

What's underneath? Nothing much, just some passives and transistors by the look of it.  At the top of the board you can see where heat from the main processor on the other side has discoloured the PCB over time.

Modem PCB Bottom Side

My initial assessment of why the modem stopped working was that the electrolytic capacitors had dried out and weren't doing their job any more.  I based this diagnosis on what I knew about the modem.  It was at least 4 years old and had operated pretty much non stop since then.  With a maximum power draw of 12W and only passive cooling, it did get quite warm.  These are perfect conditions for capacitor failure either by an increase in their ESR or by a decrease in value.  I also suspected bad caps when I tried to start it and the lights on the front kept flashing in a manner that indicated that it was powering up but a power glitch caused it to reset and start again.  From a cursory visual inspection it seemed this was the case.  Everywhere I looked I saw bulging capacitors, a sure sign of a capacitor on it's last legs.  One of them was positioned right against the heat sink of a voltage regulator.  I suppose that was to keep it warm if it got cold.  Facepalm.

Bulging Capacitor

Bulging Capacitor

Bulging Capacitor

Bulging Capacitor

Bulging Capacitor

After seeing the state of the capacitors I decided to test them to see what kind of condition they were really in.  I removed 5 to test their capacitance and ESR values.  I don't have any equipment designed to specifically measure capacitor parameters so I thought I'd see what I could do with what was lying around.

Using the information found on Geoff Graham's Measuing ESR page I thought I could put together a quick and easy way to test capacitor ESR.  All that was needed was to apply a quick voltage pulse to a capacitor under test through a resistor.  Any ESR will cause the voltage across the capacitor to immediately rise but will be too fast to charge the capacitor.  The size of the voltage step can be used to calculate the capacitor's ESR. This is when I found out my function generator is pretty much useless.  It can't do pulses, only square waves with duty cycles above 50%.  So I scrapped that idea and built a tester myself with an old development board and a few components out of my junk box.

An AVR development board was used to create the waveforms required for testing.  Its output was connected to a logic inverter on some perf board.  The inverter gives a better rise time, giving a nice sharp transition to drive the capacitor under test.  A buffer would be better but I didn't have one, so I used the inverter and then inverted the pulse in software.  One more stage is needed though, the logic inverter doesn't have a large enough drive current to charge the capacitor fast enough.  To fix that a transistor push-pull stage was put on the output to increase the current capacity.

Micro-controller Driven Test Rig

Before testing the ESR of the capacitors I thought I'd see if their values had degraded much.  I started by testing a 22uF tantalum control capacitor that I was reasonably sure was in good working order.  For this test I set the development board to generate a square wave with a period of 500 ms.  By taking measurements from the charge discharge curve of the capacitor through a 100 ohm resistor I could determine the capacitor's value.

22uF Tantalum Control Capacitor Under Test

RC Step Response 22 uF capacitor, 100 ohm resistor

RC Step Response 22 uF capacitor, 100 ohm resistor

The voltage across a capacitor in an RC circuit when driven with a step response can be described by the following equation.

As the resistor and capcitor are driven from a push pull BJT output stage the capacitor will never get to 0 volts.  This doesn't matter though, you just have to consider the change in voltage of the step and the change in voltage of the capacitor. With a bit of rearrangement it can be shown that the time taken for the capacitor voltage to rise 50% of the step voltage is equal to.

We know the resistor value, we can measure the time, this means we can calculate the capacitance.

From the scope screen shot above it can be seen that the capacitor takes about 1.5 ms to reach the 50% voltage point when charged through a 100 ohm resistor.  This gives a capacitance of about 21.6 uF which is in agreeance with the components markings.  So I know my test rig gives usable results. By no means are they accurate or precise, but they give me an idea of what's happening.  Now to test the five capacitors from the modem.  I've shown screen shots of one of the tests below.

2200uF Electrolytic Capacitor Under Test

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

RC Step Response 2200 uF capacitor, 100 ohm resistor

Capacitor Number	Capacitor Value (uF)	Temperature Rating (C)	Step Size (V)	50% rise time (us)	Calculated Capacitance (uF)
1	2200	105	4.1	275	3.96
2	1000	105	3.7	600	8.65
3	1000	85	3.8	200	2.88
4	1000	85	3.8	350	5.04
5	2200	105	3.8	2000	28.8

The results weren't great.  None of the capacitors really followed a standard exponential RC charge discharge curve.  No matter how much I turned the timebase down I couldn't see a step caused by ESR. It was more of an asymptotic curve.  I think there's more going on here than just an increase in ESR or a drop in value.  Although I don't think it's entirely valid, the previous formula was applied to calculate the capacitance.

Maybe an LCR meter could give me a better idea, but one thing is certain, capacitors that big shouldn't charge that fast.  Although the I think the calculated capacitance is probably wrong because the situation is more complex than I first thought, they definitely shouldn't be that low.

I could have tried replacing the capacitors, but decent quality parts would be pricey and I was in the market for a modem with more flexibility.  The modem I bought to replace this one is only a stop gap.  In time I'd like to get a modem from a company like Billion with a built in VPN.  This would allow me to use a mobile device more securely when I'm on the go.

What's clear is that the capacitors in the modem have definitely failed.  It does seem to be a common problem with this model.  This would cause the voltage rails to become unstable, causing soft failures at first followed by more obvious symptoms like complete failure of the device.  This was most likely caused by spending extended periods at high temperatures.  Although some of the capacitors probably had too low of a temperature rating for a passively cooled device with no heatsinks that operated in a city where 40 degree days aren't uncommon, they did last a significant amount of time, and any attempt to improve the lifetime of the modem with better components, active cooling, or more heatsink would have increased its price tag.

Confined Space Tool Bag/Sack

I recently had to do a bit of work under the house that required quite a few tools but found it too cumbersome to carry them individually.  It was a reasonably small space and I had to crawl quite far to get there.  I was however lucky enough to have just the right thing for the job.

The 3 foot clearance under the house

I happen to eat a fair bit of rice, and being a cheapskate, I like to buy it in bulk.  This means I'm starting to get quite a collection of the sacks that the rice comes in.  They seem too good to throw out and I use them when I can.  If I had a need for them I reckon that they would make some nice couch cushions, but in this case the bags were perfect for carrying my tools.

Ad hoc Tool Bag

Why not use a proper tool bag for the job I hear you ask.  Well, I don't do this kind of thing too often and it would just take up space I don't have, besides, I already had this on hand.

The bags even come with a handy little zip on the top to stop things falling out.  This made the job so much easier.  I was able to throw my tools in the bag and crawl to where I needed to be without too much hassle, and because everything was secure in the bag I didn't have to worry about losing things. 

Zip on the rice bag

Installing Hollow Wall Anchors With Common Tools

I recently had to install a new TV antenna point for my Grandmother and I felt the wall was too thin and weak to screw the wall plate to.  The easiest thing to do was just use some hollow wall anchors.

Wall Anchor Before Tightening

They're easy to use.  The anchor is inserted into a hole in the wall large enough for its body and then expanded until the bendable metal tabs force the fitting against the sheeting and lock it into place.

Wall Anchor After Tightening

Installing the fittings can be done a couple of different ways.  If you're going to be using a lot of them, go out and spend $30 on the correct tool for the job.  It's kind of like a pop rivet gun, except it pulls on the head of the screw to expand the tabs in the wall.  I only needed to use a couple of anchors so I decided to try a different (cheaper) method.

Insert the anchor and screw into the hole and lightly tap it into place with a hammer to push the locking teeth into the wall sheeting.

Wall Anchor In Position

The metal tabs on the back can then be expanded by tightening the screw.  There is a slight problem though, tightening the screw takes quite a lot of torque, and if you're not careful the anchor may just spin around without tightening the screw.  To prevent this, a second screwdriver is wedged against the locking teeth on the front of the fitting.

Using Screwdrivers to Tighten the Wall Anchor

With the second screwdriver against the locking teeth the screw can be tightened until the anchor is locked into place.  At this point you can remove the screw and securely attach whatever you want to the wall.  This method does require you to put a bit of force onto the screwdrivers which can be a bad idea.  Whenever forcing something with a screwdriver make sure your other hand is positioned so it wont get stabbed if the tool slips.  Be careful.

Job done.  My Grandmother has now made the switch to digital TV and is getting a good signal via a neat antenna point on the wall.  Installing anchors this way is really easy once you get the hang of it, but I'd only recommend it for the occasional fitting, for bigger jobs, get the right tool.  Besides, I'll take any reason to get a new tool (toy).