Jump to content
  • Advertisement
Sign in to follow this  
docyoung83

software design (not algorithms) for digital image processing

This topic is 5399 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

There has been something troubling me for quite a while now that I was hoping some people could clear up. I am writing a program that has to do some, but not a lot, of image processing. For example, all the functions necessary are blurring algorithms, zooming algorithms, and histogram algorithms (setting high and low values). However, most of the images are at least 4096x4096 pixels, which causes some problems in terms of algorithm completion time and storage in memory. I don't need any help on the algorithms, but designing an efficient and fast piece of digital image processing software is far more complicated than I expected it would be. This is what I'm doing so far, along with the problems I'm either 1) already experiencing, or 2) predict I will experience sooner or later. 1) User opens an image. 2) The original pixel values are stored in an unchangable array. This way the original picture is always located in memory in case a full reversion needs to be done by the artist. 3) Now the user selects a blur function. 4) The new pixel values (after having the blur applied to them) are stored in a new array. This array will hold all of the values for the currently generated image. 5) The user selects a histogram function and sets the high and low values (contrast function). 6) The values in the array created in step 4 are rescaled according to the selected high and low values. Ok, that was just a sample run. One of my questions is: how can the user "undo" his way back to the beginning without storing a new array of generated image data for every processing command he runs? For example, after step 6 above, the user selects Undo, the previous image values (that were calculated by doing the blur) were re-written when the user did the contrast function. So there is nothing for the user to go back to! I cannot think of any other way than storing a temporary array of image data after every single command, and then just loading the previous array every time the user clicks Undo until finally he's back to the beginning. I would Google for this, but I honestly don't know what to ask.

Share this post


Link to post
Share on other sites
Advertisement
Your algorithms may be fine for working small images, but if you have alot of:

blur (x,y) => f ( x+1,y )+f(x-1,y)+f(x,y-1) .... to blend with the 8 surounding pixels.

you are probably running into cache misses. Blocking out you image into smaller 64x64 chunks may help. And if you only process
part of the image you only have to store the changed blocks, and not the whole image.

so assuming linear array storage of the image you changed
imagedata[(x+y*4096)] to imagedata[(blockx,blocky)][(x+y*64)]

just food for thought....

Share this post


Link to post
Share on other sites
You could:

a) compress every step into lossless format like PNG (will save memory versus the raw arrays, but still use extra memory or use temporary storage on the harddisk)
b) store each command into a 'command queue' and recreate the image from those commands from the original (this will be slow and grow linearly with each command)
c) combine the two, store 'keyframes' into a lossless format and then build a command queue for each step after a keyframe until the next...
d) combine (c) with the knowledge that some image processing algorithms are invertible and use that knowledge whenever possible
e) use 'double buffering', one source buffer and one destination buffer.. source is initially the original image, destination is originally buffer[0], after the first operation, src=buffer[0], dst=buffer[1], then you can just switch between buffer[0] and buffer[1] for your src/dst (allows almost instant undo of last opertion)

So, to visualize this it would look like:
Step 0: Original Image
Step 1: Operation
Step 2: Operation
Step 3: Invertible Operation - Keyframe
Step 4: Operation
Step 5: Invertible Operation - Backbuffer
Step 6: Invertible Operation - Current - Keyframe

So you'll have 3 buffers, representing the original, a front buffer which is the result of Step6 and a backbuffer for Step5. You'll then have to try to find the shortest path to get to the desired operation, which would be:
Step 0: set original buffer as your front buffer - O(1)
Step 1: repeat the first operation on the original image
Step 2: Load keyframe from step 3, and do the inverse operation
Step 3: Load keyframe
Step 4: Load keyframe and do operation or do inverse operation on backbuffer
Step 5: Set backbuffer to frontbuffer
Step 6: already there

It's up to you how often you want to save keyframes, but the algorithm for finding the shortest path wouldn't be hard, just:
A) Find the node in your command queue that represents where you want to undo to
B) If it's a keyframe or buffer, set that as your frontbuffer
C) Else, travel forward until you hit a buffer, keyframe, or un-invertible operation (counting how many nodes you travel) and save a pointer to the node you run into
D) If you hit an uninvertible operation before a buffer or keyframe, you cannot get there by travelling backwards (set forwardNodeCount to 0xFFFF or something)
E) Now from your target node travel backwards until you hit a buffer or keyframe (counting how many nodes you travel) and save a pointer to the node you run into
F) Compare the length of the forward and backwards traversals, use whichever length is shorter, and then calculate the image by going through the list from the stored 'hit' node to your target node, doing the appropriate operations (or inverse operations) along the path

It should work fine and you can tweak the speed versus size by increasing or decreasing the number of stored keyframes (as well as implementing the inverse of any operations are invertible)

-nohbdy

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!