FAQs about CS 559 Project 1



Follow the links to find more info or clarifications about the topic.

Operation Points
Load 0, provided
Save 0, provided
Difference 0, provided
Run 0, provided
Color to Grayscale 5
Uniform Quantization 5
Populosity 20
Median Cut 50
Naive Threshold Dithering 5
Brightness Preserving Threshold Dithering 5
Random Dithering 5
Ordered Dithering 10
Clustered Dithering 5
Floyd-Steinberg Dithering 15
Box Filter 15 or 3
Bartlett Filter 15 or 3
Gaussian Filter 15 or 3
Edge Detect (High Pass) Filter 15 or 3
Edge Enhance Filter 15 or 3
Half Size 8
Double Size 12
Arbitrary Uniform Scale 25
Composite Over15 or 3
Composite Inside15 or 3
Composite Outside15 or 3
Composite Atop15 or 3
Composite Xor15 or 3
Arbitrary Rotation 25
Blue Screen 10
------------------
Solution program 0, provided
Dividing Alpha from RGBA Hint
General programming Q's  



Color to Grayscale

Date: Feb. 28, 2002

> I have a quick question concerning gray and 559.tga.  When I perform my gray
> on 559.tga then take the diff to the original 559.tga I get a black image
> which suggests that it works.  Then if I do the same thing with the
> reference program I get the same results.  If I diff my gray image with the
> reference programs I get slight variations (gray or what appear to be gray
> pixels).  There is not a lot of them but there are some.  Is this wrong? Am
> I not perserving alpha correctly?

My guess is that you are doing something wrong with the alpha. Alpha should
remain unchanged through the gray operation, so in theory you can just apply
the to-gray equation and be done with it (without taking the pre-multiplied
alpha into consideration.) However, you might be getting different effective
color resolution which may be giving you the gray pixels in the diff.

Basically, cs559.tga is output from anti-aliased text in photoshop or
similar, which has black text on a transparent background with a few
partially white pixels around the edge of the text. Those edge pixels
are apparently giving you grief.

(next question shown below under compositing)


Quant-Pop

Title: Quant-Pop is Slow

Date: Mar. 4, 2002

> The last step of quant-pop, selecting the closest color from the histogram.
> My codes are as follows:
> for (i = 0 ; i < width * height * 4 ; i += 4)  {
> for(k=0;k<256;k++){
> dist = sqrt(pow((),2)+pow((),2)+pow((),2));
> }
>   }
> However, it's very time consuming, and takes long time to run(I've 
> debugged, just this step causes the long running time). I don't think this 
> a good algorithm since the reference program doesn't take that long.
> Could you tell me what the problem is ?

As I've said before, there is no reason to take the sqrt when you
are only going to compare distances. And it's much much faster to use
x * x rather than pow(x,2). Only ever use pow() for non-integer powers
or really large powers.

Prof Chenney.


Title: Silly Quant-Pop in Reference Program

Date: Mar. 5, 2002

> I tested zred.tga, and the colors of all pixes are red.(r=255, g=0 and b=0).
> after transformation to 32 groups, it's (r=253,g=3,b=3). What I'm think is 
> that if we continuously run the quant-pop(based on the image produced from 
> last quant-pop), the color should not change(always r=253,g=3 and b=3). 
> That's what my quant-pop does.
> But when I test the reference program, if I continuously run quant-pop, the 
> color will change, finally it becomes black.

I suspect that the reference program is doing something silly with the
alpha in zred.tga. But we won't be testing quantization for non-unit
alpha, and we are only going to run the quantization methods once on
any given image.

Prof Chenney.


Brightness Preserving Threshold Dithering

Title: Intensity Range and Dithering Alpha

Date: Feb. 18, 2002

> Is it also correct to add that the intensity range is from [0, 255] in our
> case?

For all the images you read in, the intensity range will be 0-255. That's
a property of libtarga.

> Also, I don't understand why the description told us that we should
> "dither the alpha channel", when in fact the alpha value of this
> particular image: wiz.tga is of 255 (white). I found that only when I
> changed/threshold the r,g,b values, my result image looks like the
> solution.  By any chance the 2 things are related? I'm rather confused
> now. 

"Dither" as I use it here means "convert to black and white." For alpha
it means convert to either fully opaque or fully transparent. Now the
wiz.tga has alpha=1 already, so it gets dithered to alpha=1 (ie it's
unchanged and your results will look the same even if you ignore alpha
entirely.)

When dithering treat rgb and alpha as two completely separate things. Do one
thing with the rgb channels and always threshold dither alpha. Then put
the results back together.

I think for all the images we gave you the alpha is trivial, so it isn't
likely to be a problem. I put the discussion in there for completeness.

Prof Chenney.


Title: Brightness Threshold

Date: Feb. 26, 2002

James Lang said:
> Hey Professor Chenney
> I was doing the brightness preserving dithering, and I was looking at the
> class notes for some help with it.  However, I came to this question: how do
> you "choose a threshold so that x% is above and x% is below"?  I am not sure
> what that even means really.  For example, in one test image, the average
> brightness is 45/255 or something like .17 on a 0-1.0 scale.  So now I need
> to select a threshold so 17% is above and 83% is below?  I don't get what
> that means, or how one would go about doing it.  Thanks for any help

Say you want the final brightness to be .17 on a 0-1 scale. Now the final
image will have that brightness if 0.17 of them are white, and 0.83 of them
are black. Each output pixel comes from comparing the input pixel to the
threshold. So you want 0.17 of those comparisons to result in white pixels,
and 0.83 to result in black.

To find out what that threshold is, sort the input pixel intensities in
increasing order. Then chose the 0.83th one as the threshold. That way,
0.83 of the pixels will be below the threshold, and will be black, and
0.17 of them will be above the threshold and will be white.

Prof Chenney.


Title: Sorting using qsort()

Date: Feb. 28, 2002

> Professor,
> 
> Thanks for the tip on how to get a threshold for dither bright. I am now
> trying to sort my array, but instead of writing my own less than optimal
> sort, I wanted to use the "qsort" function I found in the help files. I am
> pretty new to C++, and am having trouble... can you clue me up?

qsort takes arguments for the array to be sorted, the number of elements,
the size of each element and the function to do the comparison.

Typical usage would be (under unix at least):

int
sortFunc(const void *a, const void *b)
{
    int x = *(int*)a;
    int y = *(int*)b;

    if ( x < y )
        return -1;
    else if ( x == y )
return 0;
    else
return 1;
}


    int array[100];
    ...
    qsort((void*)array, 100, sizeof(int), sortFunc);


Title: Further Advice on Using qsort()

Date: Feb. 28, 2002

Several people have asked about brightness preserving dithering, and there
has been some confusion as to how it works.

First, there was an error in the class lecture notes. The example
statement should read:
   "For example, if the average intensity is 0.6, use a threshold that is
    higher than 40% of the pixels, and lower than the remaining 60%."

To implement it:
- Copy your grey pixel data into a linear array of floating point values
- Use qsort(...) to sort that array
- Compute the average brightness
- In the sorted array, find the appropriate threshold (now it's easy to
  find it)
- Use that threshold to threshold dither the original image.

qsort is a useful function provided as part of the standard libraries.
Read the documentation for Visual C++ to learn how to use it. Or
"man qsort" on a Unix machine.

End of hints.

Prof Chenney.


Title: Edges, Error, and Float Conversion

Date: Feb. 18, 2002

> 3. What do you want us to do with the pixels at the edge with
> floyd-steinberg dithering?

You can do what you like. Easiest is to throw the error away if there is no
pixel to receive it. Which is what the reference does (I think).

...

> 5. Also, when doing error difusion dithering what do you want us to do if
> the error propogation gives us values that are out of range for the
> pixels?

You should not do anything about out of range pixels - your image should be
able to store negative values and values bigger than 255 while running the
dither algorithm. That means you should convert your image to a floating
point image (an array of floats instead of unsigned chars) and do the
computation on that. Then convert back to unsigned chars.

Cheers,
Prof Chenney.


Title: Testing of Brightness Preserving Threshold Dithering

Date: Feb. 28, 2002

We will only be testing brightness preserving threshold dithering on fully
opaque images.  That is images with every alpha value equal to 255.  Your
implementation need not modify the alpha channel for this dithering
method.  The supplied wiz.tga image is a good test image for this.  

Please note that this is for brightness preserving threshold dithering
only.


Eric


Random Dithering

Date: Feb. 23, 2002

James Lang said:
> I was wondering if the example version of the random dithering uses the
> conserved brightness version or the threshold version since my results are
> not similar to the example at all.

The version in the reference program uses a constant 0.5 threshold.

> Also, in calculating the random number
> to be added, I used a
> srand(10000)
> and a
> rand()%102-51
> for my random numbers to be added.  Is this correct syntax here (I wanted to
> use time(NULL) as my seed, but the time.h is not included in the skeleton.)
> However, I COULD get my results to look pretty good if I used rand()%51
> which would not include negative values.  In any case, thanks for any light
> you could shed on the situation.

You should use the first version, giving negative random values to add.
Take care when adding unsigned char's as values that sum to greater than 255
will be stored as (a + b) % 255. Similarly for negative values. The trick is
to cast the unsigned char to an int, do the math, then convert it back
again, truncating appropriately.

Prof Chenney.


Ordered Dithering

Date: Mar. 3, 2002

> In the ordered dither, for the given threshold matrix, which element is 
> corresponding to (0,0) of the 4*4 block? top-left or bottom-left?

If the top left of your image is 0,0, then the top left of the dither matrix
is 0,0. At least, that's the way the reference program is written (as I
recall).

In the bigger scheme of things, it really doesn't make much difference.
The qualitative appearince will be the same.

Prof Chenney.


Floyd-Steinberg Dithering

Date: Feb. 19, 2002

Christian Kaiserlian said:
> I've got a question about Floyd-Steinberg dithering.  When we compute
> the error, we (to put it in the language of the slides from the lecture
> notes) take the difference between what should be there and what's
> actually there.  The question is:  does "what should be there" take into
> account any error we've already propagated to that pixel, or is that
> strictly the value from the _original_ image?  I've looked up a few
> explanations on the web, and they seem to conflict on this issue.

What "should be there" is the original value PLUS its propagated errors.
That's the whole point of propagating errors, to make sure that they are
accounted for in subsequent pixels.

Never trust the web (well, always check multiple sources).

Cheers,
Prof Chenney.


Title: Threshold Value for Floyd-Steinberg Dithering

Date: Mar. 4, 2002

"Zhenyu (James) Kong" said:
> What's the threshold value does the reference program use for 
> Floyd-steinberg dithering?
> I need it to compare my result with that of the reference program.

It uses 0.5 for the threshold at each pixel for Floyd-Steinberg.

Prof Chenney.


Title: Error Distribution Orientation

Date: Mar. 6, 2002

> On dither-fs, when we are doing the movement in the opposite direction, do
> we change the orientation of right and left?
> (i.e, left to right, add the right adjacent pixel 7/16 of the error, how
> about when we move from right to left, we instead add 7/16 to the adjacent
> left pixel?)

Yes. Mirror the way pixel error is distributed when going right to left.
Basically, you are always distributing to pixels that have not yet been
thresholded.

Prof Chenney.


Title: Further Error Distribution Orientation

Date: Mar. 11, 2002

> I do not understand when I have to mirror error propagation. You said that
> error should always be distributed to the pixels that have not been
> thresholded yet. But when moving the filter in the zig-zag pattern
> described in class, won't the not-thresholded pixels always be to the
> right and down of the pixel being thresholded? Won't mirroring the filter
> cause error to propagate (in some instances) to pixels that have already
> been thresholded?
> 
> Maybe I am just thinking about a wrong zig-zag pattern?
> Here's what I thought it should be, is this right?
> 
http://rnvs.informatik.tu-chemnitz.de/~jan/MPEG/HTML/zigzag.gif
> 
> Thanks
> 
> Vladimir

By zigzag in the context of FLotyd-Steinberg I mean:
- Go horizontally from left to right
- for the next row, go horizontally from right to left
- for the next row, go horizontally from left to right
- and so on:

The zigzag on the web page is the one used for JPEG encoding, and
hence MPEG encoding.

Prof Chenney.


Filters

Title: Box Filter

Date: Mar. 2, 2002

> For box filter, how should I extend the input image, so as to make the 
> output image have the same size as original?

Your choice on what to do. It will have no impact upon your grade.

Prof Chenney.


Title: Edge Filter Truncation

Date: Mar. 5, 2002

> one quick question about the edge filter.  in lecture, you said that
> areas of similar colors will go to gray, and edges will go to a combo of
> black and white (for grayed images, or opposite colors for colored
> images).  my edge does that.  but the reference program makes that
> background all black.  am i missing something?

In lecture I discussed re-scaling pixel values to make sure they fall
within the visible range (the best thing to do).

But for the project, I want you to do the simpler thing which is to just
truncate values that fall out of range. It saves you from having to do
a whole bunch of annoying stuff.

Cheers,
Prof Chenney.


Date: Mar. 1, 2002

> I am working on the filters for Project 1 right now. So far the box filter
> is working. But for the rest of filters, my result picture has a worse
> "resolution" than the original picture (or the soln picture). My basic
> idea is to go through all the pixels (or bytes except for the alpha
> byte), store them as float numbers. At a second pass, I center the filter
> array at every pixel I go through.  Then I multiply all the surrounding
> pixels by the corresponding value according to the filter array and store
> the result as the value of current pixel. I can't seem to figure out why
> it is giving me that behavior. (I can sort of see small squares all over
> the image).  Could you give me some suggestion on where I may be doing it
> wrong? 

I think this is a problem many of you are having. When filtering, you must
always use _original_ pixel values in computing the filter. You must NOT use
neighboring pixels that have already been filtered. The easiest way to make
this work is to create an new image, filter values into it one by one, and
then replace the current image with the new one you generate.

That to me sounds like the most likely source of your problem.

Prof Chenney.


Title: Edge Enhance Filter

Date: Mar. 7, 2002

> I have question regarding the filter-enhance. I suppose to do this is you
> do filter-edge (doing high-pass filter) at the first time. But I don't
> understand when you say to add back the high frequency back to the
> image. What do you mean by that?

Take the result of the high-pass and literally add it, pixel by pixel,
to the original pixel values.

 output[x][y] = input[x][y] + highPass(input[x][y])

Not that you would write code like that, but it gets the message across.

Also, for everyone, the primary test image for edge enhance is the grey
checkers image, which will not take values out of range. You can of course
see what edge-enhance does to other images too.

Prof Chenney.


Title: Borders and Size of Filtered Images

Date: Mar. 6, 2002

Patrick Culbert said:
> When we do the filters, can we just throw out the unfiltered edge pixels.  i.e.
> with a 3x3 kernal would you throw out (or make black) the first and last row and
> column?  Or do you want us to reflect out the edge pixels to make a larger
> original image before filtering?

Your choice on what to do, but I would like the image size to stay the same.
Your options are:
- Put black, white or the unfiltered color where the filter cannot be applied.
- Reflect the image about the boundaries.

Prof Chenney.


Title: Pre-Multiplied Alpha in Filters

Date: Mar. 4, 2002

> I am doing the filtering algorithms and I am having some discrepancy from
> the solutions.  If you look at the box and bartlett filter of the
> zcolorcheck.tga image, the squares just change shape, but don't really blur
> at all.  My solution blurs the edges rather well, and I am wondering why the
> solution looks like that.

What you get when filtering this image will depend on how you manage
alpha when you filter:
- If you filter _without_ dividing out alpha, then you get the result
  like the reference program.
- If you divide out alpha, then filter all the channels, then put the
  filtered alpha back in, then you will get an image that looks like it
  has blurred edges on the squares.

You can figure out that difference by simulating the two techniques by
hand. You will see that the reference program's method gives pixels
for which the underlying color is fully intense but the alpha is blurred,
vs something with both the color and alpha blurred with yoru approach.
It's not clear which is better.

On the other hand, we're not grading filtering with non-unit alpha, so
it doesn't matter which version you do.

Prof Chenney.


Title: Banding Trouble in Filters

Date: Mar. 5, 2002

Many of you have been having problems with banding when you filter images.
At the bottom of this message is one student's solution, and you can all
learn from it.

With the frequent use of integers or unsigned data in graphics, it is
essential to pay careful attention to the effect of operations of data
of different types. Here's another common error, that someone had in
homework 2:
  1/3 gives zero, whereas 1/3.0 gives 0.3333333.

  int x = 3;
  float y = 1 / (float)x;

... will also put the right value in y.

Prof Chenney.

Forwarded message:
> I was getting banding effects in the filtering algorithm for wiz.tga and I
> fixed the problem.   And you told me to e-mail you if i fixed because a lot
> of other people were having similar problems.
> 
> So here's what I did:
> The problem is related to loss of information in C++.  My algorithm was
> performing integer operations when it should have been doing double or
> float.  So I just made sure that when I did all the multiplication against
> the 5x5 filter matrix that everything was a double.  This would mean that
> the scalar 25 would become 25.0  as well as casting everything to a (double)
> or a (float) so no information is lost.
> 
> Lewis


Double Size

Date: Mar. 11, 2002

> I am really  confused about use of 2d filters in the Double operation.
> 
> Description says:
> Double the image size, using a 5x5 Bartlett filter to compute the
> intermediate pixel values.
> 
> So, do we have to apply the filter only at half pixels? Class notes gave
> me the impression that we had to apply it every pixel and every half
> pixel.
> 
> I also have a question about construction of 2d filters
> 
> 
> {1 2 3 2 1} (are these the right values for 1d Barlett filter?) filter
> covers 5 pixels when centered over a pixel:
>       ^
>     /   \
>   /       \
> /-+-+-+-+-+-\ (+ - pixels)
> 
> But as far as I understand it, when centered at half pixel (graph
> above shifted .5 to the right) it covers 6 pixels. Is this right? If so
> are we supposed to use 6x5, 5x6, and 6x6 filters or do we just
> truncate?  Which pixel do we throw away then?
> 
> I am probably just hopelessly confused, but isn't it right that because of
> the symmetry 1d Bartlett (1 2 3 2 1, at least, |dy/dx|=1) centered at
> half pixel can only cover even number of pixels?

Yes, it's confusing, and it's not your fault.

Here's the easiest way to do it:

- Double the image size, and put zeros where you don't easily have pixels. So
    1 1 1 1           1 0 1 0 1 0 1 0
    1 1 1 1  becomes  0 0 0 0 0 0 0 0
      1 0 1 0 1 0 1 0
      0 0 0 0 0 0 0 0
- Filter the new image with a 5x5 bartlett filter, but with the normalization
  constant set to multiply the brightness by 4 (to take into account all the
  zeros you are filtering.)

You can use either 1 2 3 2 1 or 1 3 5 3 1 for the 1D filter (to construct a
2D filter.)  I'm not sure what the reference solution does.

You can also double by replicating, like this:
    a b c d           a a b b c c d d 
    e f g h  becomes  a a b b c c d d 
      e e f f g g h h 
      e e f f g g h h 

That might give slightly better results, and you don't have to change the
normalization constant.

Cheers,
Prof Chenney.


Arbitrary Uniform Scale

Date: Mar. 4, 2002

> The directions online for this operation say:
> "Scale the image up or down by the given multiplicative factor."
> 
> But the comments in the skeleton for this operation state:
> " Scale the image dimensions by the given factor.  The given factor is 
> //  assumed to be greater than one."
> 
> If you assume a scale greater than one, how do you scale down?
> I  assume this is a typo and should read "greater than zero" please confirm.

Yes, that is the way it should read. Any scale strictly > 0 is allowed.
And it will be tested.

Thanks for pointing that out.

Prof Chenney.


Compositing

Date: Feb. 19, 2002

Steven Long said:
> Which images would you recommend for us to use to test our compositing
> functions?  I couldn't find any two of the provided images that had the
> same dimensions.  Also, I couldn't get the viewer program to display some
> of the images such as 'zred.tga'.

We'll probably get some more ready for this problem.

The intended images are the zred.tga and another that size with checkered
colors. I seem to remember some problem with those images, and I'll
ask Eric or Matt to take a look at it.

Cheers,
Prof Chenney.


(continued from grayscale question above)

> One more quick question while I am emailing.  When we do composite ... are
> the images going to always be the same size?  If not what should we do?

You can safely assume that the images are the same size.

Prof Chenney.


Solution program

Title: Project1 Solution Fix #2

Date: Feb. 19, 2002

Yet another new solution application is now available.  Brightness
preserving dithering did not correctly handle black and white images.  It
now does.  Thank you Lewis for pointing out the problem.

Both the windows and linux solutions have been updated.

I'm sure there are more bugs to be found so keep em coming.

Eric

--
Eric McDaniel                Phone:  (608)262-9822
                             Email:  chate@cs.wisc.edu
                               Web:  http:www.cs.wisc.edu/~chate/


Blue Screen

Date: Feb. 25, 2002

>    When I work on the project, I have some problem about the blue screen.
> What we need to do is to find out which pixels contain the blue color, such as
> (0,0,b), or (c, c, b+c) and then set the alpha of the pixel to become one?

If a pixel is close to blue in color then set its alpha to be 0 (so the blue
parts are transparent.) "Close to blue" means the color is close to (0,0,255),
and "close" means that red is 255-c, where c is
a constant you determine experimentally.

Prof Chenney.


Hints

Date: Feb. 19, 2002

Not sure if any of you have had this problem, but one thing to be
careful of when dividing out alpha is the following:

unsigned char a = 128;
unsigned char b = 256;
float c = a / b;

After this, c has the value 0, because the division is integer division.
To fix it, cast b to a float (or double):

unsigned char a = 128;
unsigned char b = 256;
float c = a / (float)b;

This forces the compiler to generate floating point division code, generating
the right result.

In general, this project is very prone to numerical bugs of this type.

Prof Chenney.


Title: Pre-Multiplied Alpha Question (Project Questions)

Date: Mar. 4, 2002

> 1) For what set of operations do we need to worry about pre-multiplied
> alpha?  Is it all of them?  Right now I have coded color quantization and
> dither operations and haven't worried about alpha other than threshold
> dithering for the appropriate operations.

Operations that we will only test with alpha=1 images:
- To grey
- All the color quantization algorithms
- All the dithering algorithms
- All the filtering algorithms

Operations that we will explicitly test with non-trivial alpha images:
- All the compositing operations
- The resize and rotate operations (including double and half)
- The blue screen.

Prof Chenney.


Title: Question about Pre-Multiplied Alpha

Date: Mar. 10, 2002

Patrick Culbert said:
> Stephen Chenney wrote:
> 
> > > > Operations that we will explicitly test with non-trivial alpha images:
> > > > - All the compositing operations
> > > > - The resize and rotate operations (including double and half)
> > > > - The blue screen.
> 
> If we have to deal with alpha for half and double operations, does that mean we
> have to divide out the alpha from each channel of each pixel, run the filter, then
> multiply each pixel by the new alpha, or will it work if we filter all four
> channels individually without dividing out the alpha channel.

It turns out that you have to divide out the alpha, filter all separately,
then multiply the alpha back in.

You can do the math if you like, but you get different results if you do it
the other way (which was the long time error in the reference program,
recently fixed.)

Prof Chenney.



Title: Ongoing Saga of Alpha Filtering (Project Questions)

Date: Mar. 9, 2002

> Not to belabor the point, but in the project description on Dithering it
> says that 
> 
> "These operaions should all threshold dither the alpha channel, regardless
> fo what they do to the gray channel..."
> 
> Based on the e-mail below, should we ignore this description and not
> write the code to dither the alpha channel?

Yep. Good point. There is no need to write code for explicitly managing
alpha for dithering.

Prof Chenney.


Title: Ongoing Saga of Alpha Filtering

Date: Mar. 4, 2002

I reiterate up front:
 Filtering will only be tested on images with alpha = 1.

But, half and double size is supposed to work on alpha, and the reference
solution was broken for those cases. It has now been fixed. This will only
be of interest to you if you are doing double or half.

The reference solution is still broken for rotate, but lets say we won't
test that on non-trivial alpha.

Prof Chenney.


Implementation questions

Title: Adding functions to classes

Date: Feb. 20, 2002

> Hi Eric,
>       
>       Besides changing specified function implementations, are we
> allowed to add private, or even public funtions to TargaImage.cpp and
> TargaImage.h? Also can we add more data fields to TargaImage.h? Thank
you
> for your time!
> 
> Sincerely,
>
> xxx
> 
>

You are welcome to add items to the TargaImage class.  However, do not
modify the interface of the class.

The interface of the class is the public members and methods.

You can add class members and methods as you see fit.  In fact, adding
helper methods to the class will greatly simplify the project.

Eric