Fog Creek Software
Discussion Board




Algorithm for Photoshop's AutoLevel/AutoColors?

I'm trying to figure out how PhotoShop implements AutoLevels (and AutoColor in 7.0). Does anyone know exactly what it's doing?

Joel Spolsky
Wednesday, March 26, 2003

It would probably be easier to goto http://www.gimp.org/ and look at the Gimp source to see how they do it.  As long as you reimplement the code (and not just copy it), you aren;t covered by the GPL.

RocketJeff
Wednesday, March 26, 2003

Alternatively you can post at Michael Herf's (one of KPT's creators) forum at http://www.stereopsis.com.

rexguo
Wednesday, March 26, 2003

Joel,

For auto levels, you need to compute and analyse the histogram of the image.

The histogram is a graph showing the distribution of pixels over the range of possible pixel values. That is, for each value from a range of 0...255, how many pixels have that value.

Auto levels is basically expanding the range of an image by mapping the smallest value (from the histogram) to min (0), and highest value to max (255). The net effect is increased contrast for most images because they tend to have less dynamic range.

Photoshop treats the RGB channels separately, that is, perform the above to each channel independently, so you often see color shifts in the resulting image. A better way will be to use the luminance, or simple grey conversion, to compute the histogram, so that you preserve colors.

For auto colors, the histogram is built from the color saturation of each pixel. To get the saturation, you need to convert the image from RGB color space to HSL color space. This conversion code can be found from the code in Graphics Gems. Try googling for it.

After getting the saturation histogram, you map the smallest and highest to min and max respectively like in auto levels, and convert the image from HSL back to RGB.

Hope that helps. Or you can contract me to do it, since I'm a freelance graphics programmer. ;-)

rexguo
Wednesday, March 26, 2003

A little bit of a shorter definition:

It defines the lightest and darkest pixels as white and black, and then redistributes the intermediate pixel values proportionately.

Mark
Wednesday, March 26, 2003

You might also want to clip outlying values, in the case of a washed out image with one bright white highlight, for instance.

Tom (a programmer)
Wednesday, March 26, 2003

Rexguo,

What you just described is called "histogram stretching" in the image processing world. It is a common and cheap technique to enhance the quality of an image.

By using the full "spectrum" of greyscale colors, the contrast is improved.

Eli Bendersky
Wednesday, March 26, 2003

Cool! That sounds like all I need to know to put a pretty decent autolevel type feature into CityDesk. (I know it doesn't always get the greatest results, but my experience is that it improves about 90% of the photographs you throw at it, so it's a good feature for a basic image editor.)

I'm going to try to do this with the raster image functions built into LeadTools, although from these descriptions I could probably figure out the bit manipulations on my own.

Joel Spolsky
Wednesday, March 26, 2003

This is a really interesting discussion. Paint Shop Pro has similar functions and I learned something new today.

The nice thing about Lead Tools is that (if I recall correctly) they give you better and more consistent memory structures for the raster image than the Windows slop like DIBs and HBITMAPS and variable representations for internal images based upon the screen driver in place.

I just hope you don't pork up CityDesk with additional features that would move it out of the lean&mean, easy to download category. An argument could be made that image manipulation is outside the scope of web authoring, but I also suspect that you've been asked for this from at least several users already so it's a done deal.

Bored Bystander
Wednesday, March 26, 2003

Joel, why not team up with a graphics program that is already in the market? And then offer two versions of City Desk, one with the graphics program, and one without?

My experience is that most people already have a graphics program; after all to get photos on to the web you need a scanner or digital camera, and both come with OEM versions of graphics programs included.

Stephen Jones
Wednesday, March 26, 2003

There is a very small number of image editing operations that are a fundamental part of creating websites:

* rotate images
* scale images
* crop images
* adjust colors

With these 4 simple features CityDesk is good enough to put pictures on the web. Without them, you see a lot of sites with 2000x3000 pictures, badly cropped, and ugly colors. We've always let you work with an external editor for fancy stuff but most people who just want to put photos on their site are overwhelmed by the typical overpowered photo editor.

Joel Spolsky
Wednesday, March 26, 2003

Sounds like the kind of winnowing down of functional requirements that Alan Cooper extolls. Instead of being mediocre at a comprehensively bloated list of functions, be excellent at a small set of core requirements that 90% of the users will appreciate.

I agree with your definition of the problem. Good job.

Bored Bystander
Wednesday, March 26, 2003

Those 4 operations you mentioned is about right for straight fixing up common photos. All the other niceties in various Fireworks or Photoshop tools are for making mockups or making a webpage look really professional. If someone packaged these operations into a downloadable ActiveX control or a tiny executable how big would it be?

Li-fan Chen
Wednesday, March 26, 2003

Anyone know any good websites that do this? (looking up internet-based mail-order prints right now)

Li-fan Chen
Wednesday, March 26, 2003

A set of actions I think I do more than anything else with digital images:
1) Crop
2) Resize
3) Reduce Palette
4) Compress (jpegify)

It *might* be worthwhile to take a stab at a button that's "crop for web" - click and drag an area on a pic, get a dialog prompting for final dimensions, then the software does the rest...

to be honest, could work great, could suck - I'd have to actually try it to know for sure...

Philo

Philo
Wednesday, March 26, 2003

I should have trusted you. I thought you were getting into the kind of feature creep that web design packages often produce, giving you a graphics program that doesn't serve as a full scale stand-alone program but increases the complexity and the price.

I would have thought you would need a way of converting to either gif's or .jpg's at varying compressions. I still get scanned documents sent me as .bmp's!

Don't know if this is easy or complicated, or if it has licensing problems.

And at a later date you might consider a "convert to raised button" feature, so a graphical hyperlink, LOOKS LIKE A LINK. Might even consider trying it on this page :)

Stephen Jones
Wednesday, March 26, 2003

A few days ago I've learned from our local gurus some simple PhotoShop 7.0 for dummies steps I could pick up for fixing photos:

1) Add the Hue/Saturation layer and apply these settings to the properties: +18 to the Saturation, adjust to taste--this adds color to the picture;
2) Add the Brightness/Contrast layer and apply these settings to the properties: -5 on the Brightness, +18 on the Contrast, adjust to taste--some camera overdarken for an overly strong flash or you just took picture in a dark environment--this fixes that--if the picture has a lot of grays, the contrast takes away the grays;
3) Colorize a bit with Overlay layer is sometimes helpful, just adjust the opacity to taste;
4) Despeckle and blurs (radius of 1 and 2 is enough for me) will sometimes rid the grains, but it's a hit and miss.

Li-fan Chen
Wednesday, March 26, 2003

Aside: Joel, you do know about the licensing issue with GIFs, don't you? Of course you do, sorry. A vendor that sells software that is capable of writing GIF files compressed by  LZW compression must pay royalties. 

I once got ahold of the license agreement with Unisys, which some image library vendors demand a copy of as a trigger for enabling GIF writing in their product, and it looked like a REAL pain in the ass.

That's the most cumbersome aspect of supporting image manipulation for end users, IMO. If GIF would just vanish, the world might be a better place for SW developers.

Bored Bystander
Wednesday, March 26, 2003

Depending on when this release is planned to ship, the patent might not be an issue.

The patent that Unisys has on LZW compression expires on June 20, 2003 (20 years from the original filing - more then 17 from date of issue December 10, 1985).

To see the patent in question, goto the patent office search - http://patft.uspto.gov/netahtml/srchnum.htm - and look for patent number 4558302 (I'd post the resulting link, but it'd be 3 likes long).

RocketJeff
Wednesday, March 26, 2003

I don't want to encourage you to bloat your image editor, Joel, but adding Sharpen to the list would be great. My non-technical friends and family are often amazed at what a simple Auto Levels and Sharpen does!

I use Auto Levels and Sharpen quite a bit on the DSA web site photos, as it's quick and easy and improves most snapshots:
http://www.dsansw.org.au/

Darren Collins
Wednesday, March 26, 2003

I vote for a 'sharpen' function, too. I use it a lot in my work.

Also, would there be a compression strength option for JPEG?

Don't want to bloat the features either, but ...

Bored Bystander
Wednesday, March 26, 2003

Sharpen will sharpen noise and the JPEG blocky artifacts. Real photoshop users use the Unsharp Mask.

rexguo
Thursday, March 27, 2003

ImageMagick -- http://www.imagemagick.org/ -- is a freely distributable image processing library that does everything Joel needs. It's not GPL and you can use it in proprietary software without a fee. Joel, check it out!

It is possible to create valid GIFs that don't use LZW compression -- see http://prtr-13.ucsc.edu/~badger/software/libungif/index.shtml -- but they're huge compared to compressed GIFs. PNG was designed as a replacement, and is very widely supported -- http://www.libpng.org/pub/png/. (IE still can't do PNG transparency, though). Use PNG.

Tom Payne
Thursday, March 27, 2003

I've just bought Adobe Photoshop Album, which features a simple Fix function with buttons for Auto Colours, Auto Levels, Auto Contrast and Sharpen. It works well for the majority of cases, so I look forward to seeing something similar in CityDesk.

John Topley
Thursday, March 27, 2003

Red eye reduction is a must for me.

Tony E
Thursday, March 27, 2003

On Imagemagick: good luck chopping it down to what you need. It's an enormous, unwieldly, complex library of functions, with not-very-good documentation. And it was developed under Unix, so the build process in Windows will require a *lot* of tinkering, and what you need it to do often isn't documented very well.

I thought the same thing and I looked at it a while back for a similar application. After playing with it for a while and getting nowhere I decided that if I was really serious about developing the application I'd just buy someone's imaging library.

It is feature-rich, though. A shame that someone hasn't (for a fee) productized it for Win32 development.

Bored Bystander
Thursday, March 27, 2003

Don't implement brightness/contrast as in Photoshop. Apple did this in iPhoto 1 and it's some serious bloat (for inexperienced users). Instead implement auto-levels (that is, stretch each rgb channel separately to its fullest) which is now the enhance button in iPhoto 2.

Better yet, make it a slider. So the user can choose the unfinished picture, the radically enhanced one and anything in between. That's how Apple should have done it in the first place.

Holger
Thursday, March 27, 2003

Hmmm, I've just had an idea for a little bit of .net coding practice... Do autolevels on a whole directory tree at a time? That'd be cool...

optimistic coder
Thursday, March 27, 2003

RocketJeff, are you sure about the LZW patent expiring? I thought patents issued before 1995 expired 20 years from the *grant* date, not the file date. This resulted in companies taking their own sweet time to do whatever was necessary to get the patent actually granted. The rules were changed, and current patents expire 20 years from the original filing date. (At least if I understood our patent guy correctly.)

Martha
Thursday, March 27, 2003

First, IANAL (I Am Not A Lawyer)[I think the acronym is really appropriate for this, however].

I base my June 2003 on reading several sites including http://lpf.ai.mit.edu/Patents/Gif/Gif.html which states that Unisys says that there patent expires then.

Also, IIRC, it used to be 17 years from the date of issue (not 20) and the new rule states that it's either 17 from date of issue or 20 from date of filing (which ever is later).

Again, IANAL. I'd check with a patent lawyer to be certain.

RocketJeff
Thursday, March 27, 2003

*  Recent Topics

*  Fog Creek Home