July 7, 2008 08:09am pdt

1. JoseParrot 11,750
2. ikework 6,625
3. ozo 6,200
4. harfang 2,000
4. jaime_ol... 2,000
4. dejanpazin 2,000
4. shirsoft 2,000
4. MASQUERAID 2,000
4. jgordos 2,000
4. Mamouri 2,000
11. Warpseh 1,500
12. Talmash 1,000
12. B_Iversen 1,000
12. PockyMaster 1,000
12. anmalaver 1,000
12. Kdo 1,000

1. JoseParrot 49,414
2. ozo 18,900
3. davebytes 17,052
4. ikework 13,125
5. sunnycoder 10,833
6. MASQUERAID 4,500
7. bcladd 4,180
8. thegilb 3,592
9. Interact... 3,500
10. carl_tawn 3,000
11. bredbored 2,760
12. fl0yd 2,750
13. info_expert 2,655
14. jgordos 2,600
15. jamietoner 2,400

03.09.2005 at 06:37AM PST, ID: 21343664

	[x] Attachment Details

[x]

The Solution Rating System

With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.

The Grade of the Solution
The Zone Rank of the Expert Providing the Solution
The Number of Author and Expert Comments
The Number of Experts Contributing
The Feedback of the Community

Your Input Matters
Because of the way the system is set up, the most important variable in this equation is you. As a member of Experts Exchange, you are able to cast your vote on the quality of the solutions in regard to how complete, accurate, helpful and easy to understand each solution is. When you provide your feedback, each rating is adjusted accordingly. So, if you see a solution that has a poor rating that you think is a good solution, let us know by rating it. As you do, the rating will be adjusted and will become more accurate for other members of our site.

If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support.

Thank you!

5.6

Need an efficient C/C++ code for rotating an image

Zone: Graphics & Game Programming

Tags: image, code, rotate

I need an efficient C or C++ code for rotating an image (in my case it is a float array and two integers representing the dimentions, but anything semilar is ok) by X degrees around the center, using BiCubic interpolation.
Any tips are welcome.
Please note that I'm developing under Linux (no DirectX or OpenGL).
Source code with SSE support will be even better.

Start your free trial to view this solution

Question Stats

Zone: Programming

Question Asked By: ygal02

Solution Provided By: guitaristx

Participating Experts: 10

Solution Grade: A

Translate:

Loading Advertisement...

Microsoft

Internet Protocols
Applications

Development
OS

Hardware
Windows Security

Apple

Operating Systems
Hardware

Programming
Networking

Software

Internet

Search Engines
File Sharing
WebTrends / Stats
Spy / Ad Blockers

Web Browsers
New Net Users
Web Development
Chat / IM

Anti Spam
Web Servers
Anti-Virus
Email Clients

Gamers

Tips
Online / MMORPG
Puzzle
Emulators

Action / Adventure
Role Playing
Consoles
Game Programming

Strategy
Sports
Misc
Computer Games

Digital Living

Hardware
New Net Users
New Users

Software
Digital Music
Gaming World

Home Security
Apple
Networking Hardware

Virus & Spyware

Vulnerabilities
IDS
Encryption
Anti-Virus

Operating Systems Security
Software Firewalls
WebApplications
Cell Phones

Operating Systems
Internet
Hardware Firewalls

Hardware

Handhelds / PDAs
Displays / Monitors
Components
Networking Hardware

Peripherals
Laptops/Notebooks
Storage
Servers

Desktops
New Users
Misc
Apple

Software

System Utilities
Industry Specific
Network Management
Photos / Graphics
Page Layout
VMWare
Misc
Web Development

OS
CYGWIN
Voice Recognition
Message Queue
Quality Assurance
Security
Firewalls
MultiMedia Applications

Development
Database
Office / Productivity
Business Management
OS/2 Apps
Server Software
Internet / Email

ITPro

OS
Storage
Encryption
Operating Systems Security
Apple Hardware
Laptops & Notebooks
Servers
Networking Hardware
Peripherals

Devices
Displays / Monitors
WebTrends / Stats
Search Engines
Firewalls
WebApplications
IDS
Vulnerabilities
Email Clients

File Sharing
Spy / Ad Blockers
Web Browsers
Web Servers
Networking
Anti-Virus
Chat / IM
Anti Spam

Developer

Web Servers
Web Browsers
Game Programming
Dev Tools
Industry Specific
Office / Productivity

Database
CYGWIN
Web Development
Search Engines
File Sharing
WebTrends / Stats

Programming
Content Management
Application Servers
Protocols

Storage

Removable Backup Media
Storage Technology
Servers

Grid
Remote Access
Backup / Restore

Misc
Hard Drives

Miscellaneous
Security
Development
Linux
VMWare

MainFrame OS
Unix
Apple
OS / 2
AS / 400

BeOS
Microsoft
VMS / OpenVMS

Database

Oracle
Miscellaneous
MySQL
Software
Sybase
Contact Management
PostgreSQL
Data Manipulation
Clarion
InterSystems Cache

Siebel
MUMPS
OLAP
SQLBase
SAS
GIS & GPS
4GL
Berkeley DB
DB2
Informix

Interbase / Firebird
FoxPro
Reporting
LDAP
Filemaker Pro
MS SQL Server
dBase
MS Access

Security

Misc
Web Browsers
Software Firewalls
Operating Systems Security
File Sharing

Spy / Ad Blockers
Vulnerabilities
WebApplications
IDS
Anti-Virus

Encryption
Anti Spam
Email Clients
VPN
Chat / IM

Programming

Editors IDEs
Installation
Handhelds / PDAs
Multimedia Programming
System / Kernel

Algorithms
Game
Signal Processing
Project Management
Open Source

Database
Misc
Languages
Processor Platforms
Theory

Web Development

Scripting
Blogs
Web Servers
Software
Search Engines
Web Graphics
Images

Internet Marketing
Images and Photos
Components
Document Imaging
Web Languages/Standards
Illustration
WebApplications

Fonts
WebTrends / Stats
Authoring
Digital Camera Software
Miscellaneous

Networking

Protocols
Apple Networking
Network Management
Message Queue
Application Servers
Content Management
File Servers
Email Servers
Misc
Java Editors & IDEs

Wireless
Networking Hardware
Backup / Restore
System Utilities
ISPs & Hosting
Web Servers
Storage Technology
Removable Backup Media
Servers
Broadband

Grid
OS / 2
Novell Netware
Unix Networking
Windows Networking
Security
Telecommunications
Operating Systems
Linux Networking

Other

Community Advisor
Lounge
Community Support
New Net Users

Philosophy / Religion
Math / Science
Miscellaneous
URLs

Expert Lounge
Politics
Puzzles / Riddles

Community Support

Suggestions
New to EE
New Topics
Community Advisor

CleanUp
Announcements
General

Feedback
Input
EE Bugs

03.10.2005 at 09:19AM PST, ID: 13508354

ozo:

You can do it with 3 simple shear transforms
see Subject 3.01: How do I rotate a bitmap?
in http://www.faqs.org/faqs/graphics/algorithms-faq/

Assisted Solution

03.10.2005 at 09:28AM PST, ID: 13508463

ozo:

03.13.2005 at 12:51AM PST, ID: 13527766

ygal02:

ozo,
Thanks for your comment, but what I'm looking for, is the following:
Rotating an image using Bilinear interpolation is quick and easy, but, unfortunately does not yeild a high quality results. Using Shear transformations on the other hand will be too slow.
It seems to me that Bicubic interpolation is a good compramise. Unfortunately I could not find any efficient algorithms for BiCubic interpolation (it seems to me that since this is a well known problem probably there are well known efficient solutions as well).

Any help is very welcome.

Thanks

03.22.2005 at 05:18PM PST, ID: 13607601

DanMacDonald:

Look up the Anti Grain Gemoetry projects, AGG. It's an opensource 2d Graphics project that has code for subpixel accuracy in rotations etc.

Assisted Solution

03.28.2005 at 06:02AM PST, ID: 13643439

gtokas:

DirectX have a function to rotate a bitmap....
I tried it myself but didn't make it a year ago...
Maybe now it is possible...
Also GDI+ have such function also...
There are plenty of examples to rotate a bitmap but with a size larger than 200x200 its VERY slow.. About 2secs to do it with P4 2200 and GForceMX440 with 512Mb RAM...
GDI+ functions are 100% faster.. I had 1sec to rotate 5 degrees..
As you can see (the way I made it) both functions were slow...
I don't know about DirectX yet...

gtokas.

Assisted Solution

04.12.2005 at 11:13AM PDT, ID: 13765414

guitaristx:

Actually, you can do it in two shear operations.

The wisest, as far as view accuracy is concerned, is to make the post-rotated image bigger (in terms of pixel count), so that you can maintain a bit more detail. Then, use pixel-averaging to dither the image back down:

1. Double the size (or whatever seems sufficient).
2. Shear horizontal
3. Shear vertical
4. Reduce resolution by pixel-averaging

Believe it or not, shearing twice is going to be blazingly fast compared to almost any other method.

Assisted Solution

04.12.2005 at 11:26PM PDT, ID: 13769753

ygal02:

guitaristx:
Thanks for your comment.
It seems you suggested a linear interpolation for resizing, then rotating and then another linear interpolation for shrinking (?).
In his case the interpolation method probably wont' do the job. I tried a few interpolation methods, including using a resizing operatin prior to the rotation and it seems that the best quality to efficiency ratio is for BiCubic interpolation.
Linear interpolation is not good enough (losing quality too fast).
Using resizing operations on the other hand are not better than BiCubic interpolation but are slower !

I can get some commercial licraries (like Intel's IPP) which has a "Image Rotation" functions, but since my images have some "special" properties I need to write the code myself.

Thanks,
Yaniv

04.13.2005 at 06:38AM PDT, ID: 13772024

guitaristx:

First, I'm not recommending a linear interpolation for resizing, I'm recommending a resize operation that will scale the image up by a whole-number factor -- no interpolation required.

Your problem is that you'll have a trade-off on speed vs. accuracy. Two shears is how most of the imaging libraries work. I mentioned resizing the image because you say that you need extra accuracy. HOWEVER, that extra accuracy will cost you some speed.

I've dealt with this sort of thing before - I used to work as a software engineer for a company that specialized in image processing software. You just need to make sure that you're avoiding the slow operations: conditions, multiplication, division.

If two shear operations is not accurate enough, then you need to figure out a way to preserve more detail in the image, which means resizing. The first resize operation (if it's done right) should be relatively cost-free, since all you're doing is doubling the size. The second resize operation is what will be costly, especially if you're dealing with a color image. However, there are some tricks:

When you're averaging pixels, you're averaging the values of four bytes, which means that, mathematically, you add the four values together and divide by four:
(p1 + p2 + p3 + p4) / 4 = a
You'll do this once for a grayscale image, and three times for an RGB image.

However, you can change the above formula to look like this:
p1/4 + p2/4 + p3/4 + p4/4 = a

So, now you can generate a 256 byte lookup table where each value is the index divided by four, and you've eliminated division altogether, which makes for a significant speed increase.

What's "special" about your images?

Accepted Solution

04.13.2005 at 06:40AM PDT, ID: 13772050

guitaristx:

Also, SSE doesn't apply here - you'll be doing integer math exclusively. MMX would apply. MMX applies to integer math, whereas SSE applies to floating-point math.

04.13.2005 at 06:50AM PDT, ID: 13772155

guitaristx:

An MMX programming primer:
http://codeproject.com/cpp/mmxintro.asp

04.13.2005 at 06:56AM PDT, ID: 13772216

guitaristx:

> Also, SSE doesn't apply here - you'll be doing integer math exclusively.
> MMX would apply. MMX applies to integer math, whereas SSE applies to floating-point math.

I just re-read your original post - SSE would apply, since you're dealing with floating-point arrays.

However, are you certain that you need your 'image' data as floating-point? Can you go into any details about the application/usage for these images?

04.13.2005 at 11:01PM PDT, ID: 13779075

ygal02:

guitarx,
My images are multi-layer images. You can think of it as a 3D image that should be rotated around one of the axes. They must be floating point, as they take part of an accurate optimization algorithm of image processing. Actually I had to make them floating point in order to gain efficiency since originally they were double, so I lost some accuracy.
I liked your tip about the efficient devision using lookup table, I'll keep it in mind.
It seems that although I'm an Image Processing algorithm developer I don't know enough about efficient code writting :(

Please let me know if you can think about anything else.

Thanks.

04.14.2005 at 06:58AM PDT, ID: 13781620

guitaristx:

Using floating-point values for your pixel data is very out-of-the-ordinary for image processing as i know it. If I may, I would recommend running some analysis on your images, and find out the following:

minimum value
maximum value
minimum exponent
maximum exponent
percentage of data points that have another data point within some threshold (say, .1%)

The range of a single-precision float is (+/-)3.4e(+/-)38. Examine your data, and see what range your pixels fall into. Use some statistical analysis; ignore the upper and lower 5 or 10%, and consider the minimum and maximum values.

This will tell you whether or not you need a floating-point array to store your pixel data. If your data tends to fall within a very small range of what float can store, then you can safely reduce the precision of your pixels without sacrificing accuracy. Using floating-point values is going to slow your algorithm considerably, and I'm trying to warn you against using it unless it's ABSOLUTELY NECESSARY. It's very possible you could reduce the pixels to an unsigned short (16 bits) and maintain sufficient accuracy. It also makes that lookup table possible - the table size would be 64k, whereas the lookup table for float would be 4GB!

Float math is slooooow, avoid it if at all possible.

04.16.2005 at 05:37AM PDT, ID: 13797119

Paladin_VB:

const float piover180 = 0.0174532925f;

float x , xinc , y , yinc;

x -= xinc;
y += yinc;

xinc=(float)sin(rotation*piover180) * 0.5;
yinc=(float)cos(rotation*piover180) * 0.5;

04.16.2005 at 11:44PM PDT, ID: 13800154

ygal02:

Paladin_VB,
Can you explain the purpose ?

05.13.2005 at 10:00AM PDT, ID: 13997684

makc_the_great:

>Two shears is how most of the imaging libraries work.

oh yeah? what about >= 90 degrees? there's more logic involved.

>Can you explain the purpose

well if you'd walk through your image with those steps (if Paladin got em right), you'd have a choppy picture like if viewpoint would be rotated. if you'd plot your image using these to increment output coords, you'd have even choppiest rotated image. that was nice trick back on old, really slow machines, which allowed for only two extra multiplications for whole image to be rotated.

05.13.2005 at 12:11PM PDT, ID: 13998788

guitaristx:

> oh yeah? what about >= 90 degrees? there's more logic involved.

Yes, but the additional logic to handle angles >= 90 degrees is trivial compared to the shear operations. Shear is still going to be the best thing that I've seen thus far.

05.18.2005 at 08:55AM PDT, ID: 14028265

wkokke:

> oh yeah? what about >= 90 degrees? there's more logic involved.

rotating by 90 degrees exactly is very trivial, so the problem can always be reduced to a rotation < 90 degrees

05.18.2005 at 09:53AM PDT, ID: 14029035

gkatz:

ygal,

I am not an expert in image processing but I wanted to include a couple of quick notes.

guitaristx, you talked about using MMX ops. As far as I understand MMX is actually slows down your program because it does not have it's own register set so it is necessary to clear the registers, reload the registers with your data, perform the ops and then reset the registers, which ends up taking longer than just doing the operations normally. SSE avoids this by having their own set of registers. It would be interesting to know if they've fixed the issue with MMX in newer CPUs.

Another option for speeding up your process is to perform the biCubic interpolation on the graphics card. Current graphics cards support 32 bit floating point numbers. We recently performed some tests and found nice speed improvements when writing a CG program to perform simple image processing algorithms. One thing to consider is that your users will need to have a compatable graphics card. A quick tip if you decide to go down this path, you stated that your image is multilayer. Do not attempt to use a 3d texture to hold your data. It will be much slower than using a 2d texture and then mapping it to a 3d texture inside of your cg program.

gkatz

Assisted Solution

06.09.2005 at 11:57AM PDT, ID: 14182734

Nevering:

gkatz, is it possible to use the GPU without DirectX or OpenGL, as he said he was using niether.

07.04.2005 at 12:37AM PDT, ID: 14360455

Venabili:

This question has been classified as abandoned as it has no comments in the last 21 days. I will make a recommendation to the moderators on its resolution in approximately 4 days. I would appreciate any comments by the experts that would help me in making a recommendation.

It is assumed that any participant not responding to this request is no longer interested in its final disposition.

If the asker does not know how to close the question, the options are here:
http://www.experts-exchange.com/help.jsp#hs5

Venabili
EE Cleanup Volunteer

07.04.2005 at 05:14AM PDT, ID: 14361951

ygal02:

Venabili,

Neither of the experts actually answered my question.
I would like to give to give 100 points to guitaristx and 20 points to each one of the other participates for their good will.

Thanks.

07.04.2005 at 05:16AM PDT, ID: 14361962

Venabili:

Post a request here:http://www.experts-exchange.com/Community_Support/

Also - please in the future, try to answer to the experts:)

20080236-EE-VQP-29