Discrete Pulse Transform!


OH MY GOD! its finally done! You have no idea how happy i am right now… (and pretty drained)

I’ve spent the last three days debugging the conversion i did from matlab to c++. The problem was that the program would complete but the image wouldnt have been totally cleared (ie. be a fixed value throughout). Okay i’m getting ahead of myself. Basically the DPT algorithm (which we still have to name) seperates an image according to the contrast grouping. Its basically an intense smoother.

It starts out by identifying all the local minimum and maximum pixel groupings, it does this by recursively finding all pixel groupings and each groupings adjacent pixels (border pixels), it then compares the pixel groups color value to its adjacent pixels, if it is larger or smaller than all these values, then the group is a maximum or minimum respectively.

This seems to be the most intensive operation in the algorithm , i havent had time to slap it through a profiler yet so i cant be sure of this.

Once this initial “search” is complete, we start extracting “pulses”/pixel groups of a certain size. We start at size 1 and continue until there is only one group left (ie, the entire image has been smoothed down to a single color). When we extract the group, we check if it is a max or a min group, if so then we set the value of the pixels in that group to the max or min value of the adjacent pixels, and then we “grow” to see if it will now expand to the neighboring pixel, it may even overlap with another grouping, if this occurs we simply merge the two groups. By setting the groups pixel to a value neighbouring it we’re always guaranteed that the group will grow, so we are always guaranteed to full smooth an image.

Max groups are called “up pulses” and min groups are “down pulses”, once the image has been cleared we can then use these extracted “pulses” and reconstruct the image from the pulses, either full or partially. I’ve provided sample output of the program below, i entered in an image and then did several partial reconstructions with the extracted pulses.

full.png
Original Image

partial200to350.png
Partial Reconstruction: Grouping size 200 – 350

partial350to800.png
Partial Reconstruction: Grouping size 350 – 800

partial1000to2000.png
Partial Reconstruction: Grouping size 1000 – 2000

partial2000to35000.png
Partial Reconstruction: Grouping size 2000 – 35000

partial35000to60000.png
Partial Reconstruction: Grouping size 35000 – 60000

partial35000to85000.png
Partial Reconstruction: Grouping size 35000 – 85000

Kinda cool huh? Anyways the really funny thing is now that the algorithm is complete, we need to figure out the application for the algorithm. Kinda like developing a cure for a disease that hasnt been discovered yet. Should prove fun…

The next step for me know is to develop a win32 application that will function as a work bench for this algorithm so that we can easily see the results, i honestly have no idea how complicated it will be to embed my ANSI c++ code into a visual c++ program and so that will be my next challenge. Keep an eye out.

Also since this is now complete (i was envisioning debugging code for most of the weekend) I can now spend a large chunk of the weekend working on the design document for our mod. That’s gonna be a lot of work but work that i’m looking forward to.

Source: https://github.com/BobbyAnguelov/DPT

3 thoughts on “Discrete Pulse Transform!

  1. This looks like a pretty cool algorithm. Trying to think of an application for it without really understanding how it works myself is a bit difficult. Of course the most obvious application might be some form of compression, but I also find myself wondering if it might be somehow useful as part of some larger algorithm for squeezing the range of an HDR image. Your partial reconstructions look like they might be useful for some kind of vectorization algorithm, too. It would also be interesting to see this applied to a video source to see if there are any obvious motion tracking and/or video compression algorithms to derive.

  2. I think I’d agree with video compression algorythm, but that would require x number of frames to be processed per second, and a contiguous pixel summation function(grouper) function would seem to involve numerous sequential cycles to reach an endpoint of some number of colors in the image. I’m thinking item or shape recognition in a variety of lighting situations — security systems, perhaps.

    Or medical. Try an x-ray, look for osteopenia (light bone density – potential osteoporosis) or osteocarcinoma (mixed – could be light could be dark) from standard radiographs, MRI and/or CT image analysis. I would think a digital analysis might be enhanced with an ability to toggle between images that have detail subtracted at various grouping levels.

    Perhaps there would be applications where you would superimpose a photo’s surface (altering the alpha) over a digital thermogram of some type.

    Fun to think about. More experimentation should give you clarity.

  3. Thanks for the replies. I’ll definitely look into your suggestions! I have to now write the algorithm out in pseudo code, so once i complete that I’ll post that here as well, hopefully provide you with a better understanding of the algorithm and techniques, its a very simple thing at the end of the day…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s