[WIP] Rescale&Rotate Tool

[lithander]

The original post is edited beyond recognition

I'd like to to animate a low resolution sprites using a skeleton system. One requirement is to be able to rescale&rotate pixel art. Harder then expected as discussed in this thread

I started to implement a couple of algorithms to experiment. Here is a little tool that allows you to apply different upscaling, transformation and sampling algorithms to pixel art and compare their quality.



Download: PixelPunch004.rar

• For upscaling I implemented the non anti-aliasing algorithms mentioned in the wikipedia article: http://en.wikipedia.org/wiki/Pixel_art_scaling_algorithms
  My improved versions aim to solve some artifact-problems and are marked with the suffix HQ.
  
• For transformation I implemented a standared projective approach that resamples the image based on a homogeneous 3x3 matrix. The visual effect resembles a projection from one plane through a point on another plane.
  I also implemented a bilinear transformation that does not preserve lines and just fits the content of the source image into the target quadrilateral.
  
• Lastly sampling. The transformation yields a coordinate (with fractional part) in the source image for each pixel in the target. Based on that coordinate the sampling algorithms decide on a color to put there.
  
  Sampling methods do NOT preserve the palette:
  
  Smooth bilinear considers the 4 closest pixels assigns them weights (that sum up to 1) and and mixes a new color.
  
  Smooth bicubic works similarily but considers the closest 16 pixels. (Just google bicubic sampling)
  
  Sampling methods DO preserve the palette:
  
  Major bilinear works like smooth bilinear but instead of mixing 4 pixels it choses the one with the biggest weight.
  
  Second bilinear does the same but returns the pixel with the second biggest weight.
  
  Best fit narrow works like Smooth bicubic but instead of returning the calculated color it returns that out of the 4 cloest pixels that match this color best. (best aka least squares of the difference in R, G and B)
  
  Best fit wide does the same but returns the best fit out of the 16 closest pixels.
  
  Best fit Any does the same but returns the best fit out of ALL pixels. (So every color in the palette is considered as an option)
  
  Bilinear Mix is a little crazy. In the first pass it does the same thing as "major bilinear". Then it compares the result with "smooth bicubic" building a difference map. Pixels that are a local maxima in the difference map and where the difference exceeds a certain "Mix Threshold" are replaced with the result of Second bilinear in that location. However, the threshold required for the second best option to be chosen scales with the weight of that second best option.
  

Usage:

1. Drag a PixelArt image into the program.

2. Chose a Upscaling method.

3. Chose a Transform method. If transformation is enabled you can...

   a) Skew the image. Click & Drag edges and corners with your LEFT mouse button
   b) Rotate the image. Click & Drag somewhere with your RIGHT mouse button to rotate around that point.

4. Chose a Sampling method. This only takes effect if transformation is enabled.

Last but not least you can...
...adjust the size of the image to your screen with the Zoom slider.
...hold SPACE to compare the current Sampling-Type with the previous one.
...toggle Fullscreen by pressing the F key.
...save the image (as you currently see it) by pressing the S key.

Which combination do you think works best? What other approach could be promising?

[Mathias]

Just to clarify - interpolation is anytime a computer processes pixels during supersampling and subsampling; changing a pic's size.
Whether or not the interpolation method/algorithm uses anti-aliasing is what's in question.


Nice tool. Think about batching capabilities if you really want to make it useful. Dropping an unknown filetype into the app crashes it. (haven't taken the time to test your algorithms yet)

I see you're linking to the ROTsprite thread, but your link is broken.

[Atnas]

Very nice program! I ran some of my stuff through it:



I think I prefer scale2x the most.

It'd be nice to have a clear image function, so you could load different files in without having to reload the program.  c :

[lithander]

Thanks for giving it a try! I really appreciate it!

@Mathias: I tried to find the correct term for "algorithms that doesn't mess up the color palette" but of course these are interpolating too. Non-antialiasing is better.
And while at the moment I'm more interested in functionality then usability I agree that commandline parameters are great to build automated content pipelines.

But a way to compare and evaluate different upscaling approaches is the sole purpose of the tool in it's current form.

@Atlas: You shouldn't have to restart the application. Just drop another file and it will replace the old one. Cute little sprites you got there, btw! And thanks for taking the time to screenshot!

All the algorithms I found and implemented had some small flaws. Like introducing artefacts or making individual pixels disproportional small. Those weren't bugs in my implementation but just how these simple filters work.
I tried to leverage that and added some custom versions that I have marked with a 'HQ' suffix. They take longer to compute (I now display the time the upscaling takes) but I really like the results. Personally I'd say that Scale4x HQ looks best! What do you think?

PixelPunch02.rar

Last but not least I added two Shortcuts:
Holding SPACE will switch to your previously selected Scale-Type so you can easily compare two different algorithms!
Press F-Key to toggle Fullscreen.

[ErekT]

The app doesn't work here, all I get are some grey and white boxes where the text should be. My gfx "card" is extremely poor; gma950, so that's probably why

If you're interested, I tried to do my own scaling algorithm some time ago. It's based on the Rotsprite trickery with checking similar pixels instead of just equals, and also some extra step-smoothing vanilla Scale2X lacks. Let me know and I'll post the source here with some explanations (written in Blitzmax).

[lithander]

@ErekT: I'd be glad to hear more of your approach, that would be great!

The app uses OpenGL to render the screen. That's probably overkill but it's been familiar ground coding-wise so I just used that. I guess gma950 doesn't like non-power-of-two textures.

[lithander]

[i messed up editing^^]

[Fawful]

this gives some really nice effects

[ErekT]

Okay, here's my super-great ScalErekT function. It's written in a Basic language called Blitzmax, which is a really sweet language btw. The code is big and bloated but super-simple, I just go with brute-force tactics all the way. Lots of comments too. But just in case I included some operator and function explanations below.

Ugly it may be but the code works! It smooths better than Scale2X overall imo and also preserves most edges/corners, which helps kill the claymation-effect most pixel-art filters suffer from. The down-side is that it reads two to three times more pixels than Scale2X so it's quite a bit slower also. No biggie if you're not using it for real-time full screen scaling tho.

Some operator differences between C and blitzmax:
'         ==     //
<>     ==     !=
And    ==     &&
Or      ==     ||

Other stuff:

P = PMPixels[pos]       ==     Variable P = pixel at position pos of source image
x2PMPixels[] = P_1     ==     Write pixel value stored in P_1 to output image
Pixmap                      ==     Just a normal bitmap image

And yeah, here's an exe file to check out the effect. Put your image in the same folder as the exe and rename it to test.bmp. Run the exe and press 1 for no scaling, 2 for Scale2X and 3 for ScalErekT:

http://www.mediafire.com/?9prowd8jyydh8sn


And the code:

' standard Scale2X.

Function Scale2X(Pixmap:TPixmap)

   Local Pix_W:Int = PixmapWidth(Pixmap)
   Local Pix_H:Int = PixmapHeight(Pixmap)
   Local x:Int
   Local y:Int

   Local ScaledPixmap:TPixmap = CreatePixmap(Pix_W*2,Pix_H*2,PF_RGB888)

   Local P:Int
   Local A:Int
   Local B:Int
   Local C:Int
   Local D:Int

   Local P_1:Int
   Local P_2:Int
   Local P_3:Int
   Local P_4:Int

   ' go through all pixels in the image
   For x = 0 To Pix_W - 1
      For y = 0 To Pix_H - 1

         ' read the source pixel and its surrounding pixels
         P = ReadPixel(Pixmap,x,y)
         If x > 0 And x < Pix_W - 1 And y > 0 And y < Pix_H - 1
            A = ReadPixel(Pixmap,x,y-1)
            B = ReadPixel(Pixmap,x+1,y)
            C = ReadPixel(Pixmap,x-1,y)
            D = ReadPixel(Pixmap,x,y+1)
         Else
            A = P
            B = P
            C = P
            D = P
         EndIf

         P_1 = P
         P_2 = P
         P_3 = P
         P_4 = P

         ' check for equal pixels around P and modify output pixels accordingly
         If A = C And B <> C And A <> D Then P_1 = A
         If A = B And B <> C And A <> D Then P_2 = B
         If D = C And A <> D And B <> C Then P_3 = C
         If B = D And B <> C And A <> D Then P_4 = D


         WritePixel(ScaledPixmap,x*2,y*2,P_1)
         WritePixel(ScaledPixmap,(x*2)+1,y*2,P_2)
         WritePixel(ScaledPixmap,x*2,(y*2)+1,P_3)
         WritePixel(ScaledPixmap,(x*2)+1,(y*2)+1,P_4)
      Next
   Next

   OutputPixmap = CopyPixmap(ScaledPixmap)

End Function



' My function :]

Function ScalErekT(PM:TPixmap)

   Local PMPixels: Int Ptr = Int Ptr(pm.pixels)
   Local Pix_W:Int = PixmapWidth(PM)
   Local Pix_H:Int = PixmapHeight(PM)
   Local x:Int
   Local y:Int
   Local yt:Int
   Local yb:Int
   Local xl:Int
   Local xr:Int
   Local yt2:Int
   Local yb2:Int
   Local xl2:Int
   Local xr2:Int
   
   Local ScaledPM:TPixmap = CreatePixmap(Pix_W*2,Pix_H*2,PF_RGBA8888)
   Local x2PMPixels:Int Ptr = Int Ptr (ScaledPM.pixels)
   
   Local x2Pix_W:Int = PixmapWidth(ScaledPM)
   Local x2Pix_H:Int = PixmapHeight(ScaledPM)
   
   Local P:Int
   Local A:Int
   Local B:Int
   Local C:Int
   Local D:Int
   Local FL:Int   ' far left pixel (beside C)
   Local TR:Int   ' top right pixel
   Local FR:Int   ' far right pixel (beside B)
   Local TL:Int   ' top left pixel
   Local FT:Int   ' far top pixel
   Local FB:Int   ' far bottom pixel
   Local BL:Int   ' bottom left pixel
   Local BR:Int   ' bottom right pixel
   
   Local P_1:Int   ' output pixel top-left
   Local P_2:Int   ' output pixel top-right
   Local P_3:Int   ' output pixel bottom-left
   Local P_4:Int   ' output pixel bottom-right

   ' RotSprite vars
   Local P_Clr:Int[4]   ' 1 = R, 2 = G, 3 = B
   Local A_Clr:Int[4]   ' 1 = R, 2 = G, 3 = B
   Local B_Clr:Int[4]   ' 1 = R, 2 = G, 3 = B
   Local C_Clr:Int[4]   ' 1 = R, 2 = G, 3 = B
   Local D_Clr:Int[4]   ' 1 = R, 2 = G, 3 = B
   Local P_Value:Int      ' holds average of RGB values
   Local A_Value:Int
   Local B_Value:Int
   Local C_Value:Int
   Local D_Value:Int

   ' color class vars
   Local P_Red:Int = False
   Local A_Red:Int = False
   Local B_Red:Int = False
   Local C_Red:Int = False
   Local D_Red:Int = False
   Local P_Green:Int = False
   Local A_Green:Int = False
   Local B_Green:Int = False
   Local C_Green:Int = False
   Local D_Green:Int = False
   Local P_Blue:Int = False
   Local A_Blue:Int = False
   Local B_Blue:Int = False
   Local C_Blue:Int = False
   Local D_Blue:Int = False

   ' go through all pixels in the image
   For x = 0 To Pix_W - 1
      For y = 0 To Pix_H - 1
         yt = (y-1)*Pix_W
         yb = (y+1)*Pix_W
         yt2 = (y-2)*Pix_W
         yb2 = (y+2)*Pix_W
         xl2 = (x-2)
         xr2 = (x+2)
         xl = x-1
         xr = x+1
         Local yc:Int = y*pix_W
         ' read the source pixel and its surrounding pixels
         P = PMPixels[yc+x]
         If x > 0 And x < Pix_W - 1 And y > 0 And y < Pix_H - 1
            A = PMPixels[yt+x]
            B = PMPixels[yc+xr]
            C = PMPixels[yc+xl]
            D = PMPixels[yb+x]
         Else
            A = P
            B = P
            C = P
            D = P
         EndIf

         P_1 = P
         P_2 = P
         P_3 = P
         P_4 = P

         ' get colors
         P_Clr[1] = (P & $FF0000) Shr 16   ' red
         P_Clr[2] = (P & $FF00) Shr 8      ' green
         P_Clr[3] = (P & $FF)         ' blue
         A_Clr[1] = (A & $FF0000) Shr 16   ' red
         A_Clr[2] = (A & $FF00) Shr 8      ' green
         A_Clr[3] = (A & $FF)         ' blue
         B_Clr[1] = (B & $FF0000) Shr 16   ' red
         B_Clr[2] = (B & $FF00) Shr 8      ' green
         B_Clr[3] = (B & $FF)         ' blue
         C_Clr[1] = (C & $FF0000) Shr 16   ' red
         C_Clr[2] = (C & $FF00) Shr 8      ' green
         C_Clr[3] = (C & $FF)         ' blue
         D_Clr[1] = (D & $FF0000) Shr 16   ' red
         D_Clr[2] = (D & $FF00) Shr 8      ' green
         D_Clr[3] = (D & $FF)         ' blue

         ' set average value from RGB
         P_Value = (P_Clr[1] + P_Clr[2] + P_Clr[3]) / 3
         A_Value = (A_Clr[1] + A_Clr[2] + A_Clr[3]) / 3
         B_Value = (B_Clr[1] + B_Clr[2] + B_Clr[3]) / 3
         C_Value = (C_Clr[1] + C_Clr[2] + C_Clr[3]) / 3
         D_Value = (D_Clr[1] + D_Clr[2] + D_Clr[3]) / 3

         ' check for equal pixels around P and modify output pixels accordingly
         If B <> C And A <> D And (A = C Or A = B Or C = D Or B = D)
            ' if A = C then check far left and top right pixel to see if it's necessary
            ' to modify P_2 as well
            If A = C
               P_1 = A
               ' check pixel at far left and top right to see if stepping needs easing
               If x > 1 Then FL = PMPixels[yc+xl2]
               ' if FL = C then read another pixel: TR
               If FL = C
                  If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                  ' If both = A && C then set P_2 to be A as well.
                  If FL = C And TR = A Then P_2 = A
               EndIf

               ' If FL is C and TR is A then we already know what to smooth here so
               ' we can skip checking for vertical stepping and save CPU load. But if not
               ' then do another check for P_3 to see if the bottom left and far top
               ' pixels are the same.
               If FL <> C Or TR <> A
                  ' check pixel at far top and bottom left to see if stepping needs easing
                  If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                  If BL = C
                     If y > 1 Then FT = PMPixels[yt2+x]
                     ' If both = A && C then set P_3 to be C as well
                     If BL = C And FT = A Then P_3 = C
                  EndIf
               EndIf

               ' stepping has been applied but if BL and TL and TR are equal then
               ' P_1-4 make up a corner so undo stepping
               If P_1 = A
                  ' check top left first, if it's equal to A then check bottom left
                  If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                  If TL = A
                     ' TL has been read; this way we don't need to read the pixel twice
                     Local TL_Read:Int = True
                     ' now check bottom left
                     If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                     If BL = A
                        ' BL has been read; this way we don't need to read the pixel twice
                        Local BL_Read:Int = True
                        ' if P_2 = A then we don't need to check TR: it's already checked
                        If P_2 <> A
                           If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                        EndIf
                        ' now compare them all and see if they make up a corner
                        ' NOTE: checking TR would be enough; the others have been
                        ' confirmed already. But I included them anyway for read-
                        ' ability
                        If TL = A And BL = A And TR = A
                           P_1 = P
                           P_2 = P
                        EndIf
                     EndIf
                  EndIf
               EndIf


            ' if A = B then check far right and top left pixel to see if it's necessary
            ' to modify P_1 as well
            ElseIf A = B
               P_2 = B
               If x < Pix_W - 2 Then FR = PMPixels[yc+xr2]
               If FR = B
                  If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                  If FR = B And TL = A Then P_1 = B
               EndIf

               If FR <> B Or TL <> A
                  If x < Pix_W - 1 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                  If BR = B
                     If y > 1 Then FT = PMPixels[yt2+x]
                     If BR = B And FT = A Then P_4 = B
                  EndIf
               EndIf

               ' stepping has been applied but if TL and TR and BR are equal then
               ' P_1-4 make up a corner so undo stepping
               If P_2 = A
                  ' check top right first, if it's equal to B then check bottom right
                  If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                  If TR = A
                     ' now check bottom right
                     If x < Pix_W - 1 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                     If BR = A
                        ' if P_1 = A then we don't need to check TL: it's already checked
                        If P_1 <> A
                           If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                        EndIf
                        ' now compare them all and see if they make up a corner
                        ' NOTE: checking TL would be enough; the others have been
                        ' confirmed already. But I included them anyway for read-
                        ' ability
                        If TR = A And BR = A And TL = A
                           P_1 = P
                           P_2 = P
                        EndIf
                     EndIf
                  EndIf
               EndIf

            ' if C = D then check far left and bottom right pixel to see if it's necessary
            ' to modify P_4 as well
            ElseIf C = D
               P_3 = C
               If x > 1 Then FL = PMPixels[yc+xl2]
               If FL = C
                  If x > 0 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                  If FL = C And BR = D Then P_4 = C
               EndIf

               If FL <> C Or BR <> D
                  If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                  If TL = C
                     If y < Pix_H - 2 Then FB = PMPixels[yb2+x]
                     If TL = C And FB = D Then P_1 = C
                  EndIf
               EndIf

               ' stepping has been applied but if TL and BL and BR are equal then
               ' P_1-4 make up a corner so undo stepping
               If P_3 = D
                  ' check top left first, if it's equal to A then check bottom left
                  If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                  If TL = D
                     ' now check bottom left
                     If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                     If BL = D
                        ' if P_4 = D then we don't need to check BR: it's already checked
                        If P_4 <> D
                           If x > 0 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                        EndIf
                        ' now compare them all and see if they make up a corner
                        ' NOTE: checking BR would be enough; the others have been
                        ' confirmed already. But I included them anyway for read-
                        ' ability
                        If TL = D And BL = D And BR = D
                           P_3 = P
                           P_4 = P
                        EndIf
                     EndIf
                  EndIf
               EndIf

            ' if B = D then check far right and bottom left pixel to see if it's necessary
            ' to modify P_3 as well
            ElseIf B = D
               P_4 = D
               If x < Pix_W - 2 Then FR = PMPixels[yc+xr2]
               If FR = B
                  If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                  If FR = B And BL = D Then P_3 = D
               EndIf

               If FR <> B Or BL <> D
                  If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                  If TR = B
                     If y < Pix_H - 2 Then FB = PMPixels[yb2+x]
                     If TR = B And FB = D Then P_2 = B
                  EndIf
               EndIf

               ' stepping has been applied but if TR and BR and BL are equal then
               ' P_1-4 make up a corner so undo stepping
               If P_3 = D
                  ' check top right first, if it's equal to D then check bottom right
                  If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                  If TR = D
                     ' now check bottom right
                     If x < Pix_W - 1 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                     If BR = D
                        ' if P_3 = D then we don't need to check BL: it's already checked
                        If P_3 <> D
                           If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                        EndIf
                        ' now compare them all and see if they make up a corner
                        ' NOTE: checking BL would be enough; the others have been
                        ' confirmed already. But I included them anyway for read-
                        ' ability
                        If TR = D And BR = D And BL = D
                           P_3 = P
                           P_4 = P
                        EndIf
                     EndIf
                  EndIf
               EndIf

            EndIf
         EndIf


         ' vars to get value difference between P and B/C/D. Used to compare and set P
         ' to the value closest to it; prevents "stray" pixel artifacts
         Local A_P_Difference:Int
         Local B_P_Difference:Int
         Local C_P_Difference:Int
         Local D_P_Difference:Int

         If P_1 <> P And P_1 <> P_3 And P_1 <> P_2   ' compare P_1 and P_3 to make sure there's been no vertical step smoothing
            ' check which pixel is closer to P: C or A?
            If C_Value > P_Value Then C_P_Difference = C_Value - P_Value
            If C_Value <= P_Value Then C_P_Difference = P_Value - C_Value
            If A_Value > P_Value Then A_P_Difference = A_Value - P_Value
            If A_Value <= P_Value Then A_P_Difference = P_Value - A_Value

            If C_P_Difference > A_P_Difference
               P_1 = A
            Else
               P_1 = C
            EndIf
         EndIf
         If P_2 <> P And P_2 <> P_4 And P_1 <> P_2   ' compare P_2 and P_4 to make sure there's been no vertical step smoothing
            ' check which pixel is closer to P: B or A?
            If B_Value > P_Value Then B_P_Difference = B_Value - P_Value
            If B_Value <= P_Value Then B_P_Difference = P_Value - B_Value
            If A_Value > P_Value Then A_P_Difference = A_Value - P_Value
            If A_Value <= P_Value Then A_P_Difference = P_Value - A_Value

            If B_P_Difference > A_P_Difference
               P_2 = A
            Else
               P_2 = B
            EndIf
         EndIf
         If P_3 <> P And P_3 <> P_1 And P_4 <> P_3   ' compare P_3 and P_1 to make sure there's been no vertical step smoothing
            ' check which pixel is closer to P: C or D?
            If C_Value > P_Value Then C_P_Difference = C_Value - P_Value
            If C_Value <= P_Value Then C_P_Difference = P_Value - C_Value
            If D_Value > P_Value Then D_P_Difference = D_Value - P_Value
            If D_Value <= P_Value Then D_P_Difference = P_Value - D_Value

            If C_P_Difference > D_P_Difference
               P_3 = D
            Else
               P_3 = C
            EndIf
         EndIf
         If P_4 <> P And P_4 <> P_2 And P_4 <> P_3   ' compare P_4 and P_2 to make sure there's been no vertical step smoothing
            ' check which pixel is closer to P: B or D?
            If B_Value > P_Value Then B_P_Difference = B_Value - P_Value
            If B_Value <= P_Value Then B_P_Difference = P_Value - B_Value
            If D_Value > P_Value Then D_P_Difference = D_Value - P_Value
            If D_Value <= P_Value Then D_P_Difference = P_Value - D_Value

            If B_P_Difference > D_P_Difference
               P_4 = D
            Else
               P_4 = B
            EndIf
         EndIf



         ' if equal pixel conditions aren't met then check for similar pixels instead:

         If P_1 = P And C <> A   ' P_3 is unmodified and C & D are similar but not equal
            ' if C is similar to A and very different from P then turn P_1 into either C or A
            If A_Value < C_Value + 40 And A_Value > C_Value - 40 And ((P_Value >= C_Value + 40 Or P_Value <= C_Value - 40) Or (P_Value >= A_Value + 40 Or P_Value <= A_Value - 40)) And C <> D And B <> A
               If A <> D And B <> C And P_3 <> D And P_4 <> D And P_3 <> C And P_4 <> B
                  ' check top-left pixel; only modify P_1 if TL <> P (no diagonal line from TL to P)
                  If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                  If TL <> P
                     ' check BL and TR -> if they're the same as TL then P is a
                     ' corner = don't modify
                     If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                     ' TL = BL -> OK to check TR as well
                     If TL = BL
                        If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                     EndIf
                     ' if they're all the same then leave P_3 as-is
                     If TL = BL And TL = TR
                        P_1 = P
                     Else
                        ' check which pixel is closer to P: C or A?
                        If C_Value > P_Value Then C_P_Difference = C_Value - P_Value
                        If C_Value <= P_Value Then C_P_Difference = P_Value - C_Value
                        If A_Value > P_Value Then A_P_Difference = A_Value - P_Value
                        If A_Value <= P_Value Then A_P_Difference = P_Value - A_Value

                        If C_P_Difference > A_P_Difference
                           P_1 = A
                        Else
                           P_1 = C
                        EndIf
                     EndIf
                  EndIf
               EndIf
            EndIf
         EndIf

         If P_2 = P And A <> B   ' P_2 is unmodified and A & B are similar but not equal
            ' if D is similar to B and very different from P then turn P_4 into either B or D
            If B_Value < A_Value + 40 And B_Value > A_Value - 40 And ((P_Value >= A_Value + 40 Or P_Value <= A_Value - 40) Or (P_Value >= B_Value + 40 Or P_Value <= B_Value - 40)) And C <> A And D <> B
               If B <> C And A <> D And P_3 <> C And P_4 <> D And P_3 <> D And P_4 <> B
                  ' check top-right pixel; only modify P_2 if TR <> P (no diagonal line from TR to P)
                  If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                  If BR <> P   ' old: If BR <> P Then P_4 = B
                     ' check BR and TL -> if they're the same as TR then P is a
                     ' corner = don't modify
                     If x < Pix_W - 1 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                     ' TR = BR -> OK to check TL as well
                     If TR = BR
                        If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                     EndIf
                     ' if they're all the same then leave P_2 as-is
                     If TR = BR And TR = TL
                        P_2 = P
                     Else
                        ' check which pixel is closer to P: B or A?
                        If B_Value > P_Value Then B_P_Difference = B_Value - P_Value
                        If B_Value <= P_Value Then B_P_Difference = P_Value - B_Value
                        If A_Value > P_Value Then A_P_Difference = A_Value - P_Value
                        If A_Value <= P_Value Then A_P_Difference = P_Value - A_Value

                        If B_P_Difference > A_P_Difference
                           P_2 = A
                        Else
                           P_2 = B
                        EndIf
                     EndIf
                  EndIf
               EndIf
            EndIf
         EndIf

         If P_3 = P And C <> D   ' P_3 is unmodified and C & D are similar but not equal
            ' if C is similar to D and very different from P then turn P_3 into either C or D
            If D_Value < C_Value + 40 And D_Value > C_Value - 40 And ((P_Value >= C_Value + 40 Or P_Value <= C_Value - 40) Or (P_Value >= D_Value + 40 Or P_Value <= D_Value - 40)) And B <> D And C <> A
               If A <> D And B <> C And P_1 <> C And P_2 <> A And P_1 <> A And P_2 <> B
                  ' check bottom-left pixel; only modify P_3 if BL <> P (no diagonal line from BL to P)
                  If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                  If BL <> P   ' old: If BL <> P Then P_3 = D
                     ' check TL and BR -> if they're the same as BL then P is a
                     ' corner = don't modify
                     If x > 0 And y > 0 Then TL = PMPixels[yt+xl]
                     ' TL = BL -> OK to check BR as well
                     If TL = BL
                        If x < Pix_W - 1 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                     EndIf
                     ' if they're all the same then leave P_3 as-is
                     If TL = BL And TL = BR
                        P_3 = P
                     Else
                        ' check which pixel is closer to P: C or D?
                        If C_Value > P_Value Then C_P_Difference = C_Value - P_Value
                        If C_Value <= P_Value Then C_P_Difference = P_Value - C_Value
                        If D_Value > P_Value Then D_P_Difference = D_Value - P_Value
                        If D_Value <= P_Value Then D_P_Difference = P_Value - D_Value

                        If C_P_Difference > D_P_Difference
                           P_3 = D
                        Else
                           P_3 = C
                        EndIf
                     EndIf
                  EndIf
               EndIf
            EndIf
         EndIf

         If P_4 = P And B <> D   ' P_4 is unmodified and B & D are similar but not equal
            ' if D is similar to B and very different from P then turn P_4 into either B or D
            If B_Value < D_Value + 40 And B_Value > D_Value - 40 And ((P_Value >= D_Value + 40 Or P_Value <= D_Value - 40) Or (P_Value >= B_Value + 40 Or P_Value <= B_Value - 40)) And B <> A And D <> C
               If B <> C And A <> D And P_1 <> C And P_2 <> A And P_1 <> A And P_2 <> B
                  ' check bottom-right pixel; only modify P_4 if BR <> P (no diagonal line from BR to P)
                  If x < Pix_W - 1 And y < Pix_H - 1 Then BR = PMPixels[yb+xr]
                  If BR <> P   ' old: If BR <> P Then P_4 = B
                     ' check TR and BL -> if they're the same as BR then P is a
                     ' corner = don't modify
                     If x < Pix_W - 1 And y > 0 Then TR = PMPixels[yt+xr]
                     ' TR = BR -> OK to check BL as well
                     If TR = BR
                        If x > 0 And y < Pix_H - 1 Then BL = PMPixels[yb+xl]
                     EndIf
                     ' if they're all the same then leave P_4 as-is
                     If TR = BR And TR = BL
                        P_4 = P
                     Else
                        ' check which pixel is closer to P: B or D?
                        If B_Value > P_Value Then B_P_Difference = B_Value - P_Value
                        If B_Value <= P_Value Then B_P_Difference = P_Value - B_Value
                        If D_Value > P_Value Then D_P_Difference = D_Value - P_Value
                        If D_Value <= P_Value Then D_P_Difference = P_Value - D_Value

                        If B_P_Difference > D_P_Difference
                           P_4 = D
                        Else
                           P_4 = B
                        EndIf
                     EndIf
                  EndIf
               EndIf
            EndIf
         EndIf


         ' Write pixels to output pixmap
         x2PMPixels[(y*2  )*ScaledPM.Width+(x*2  )] = P_1
         x2PMPixels[(y*2  )*ScaledPM.width+(x*2+1)] = P_2
         x2PMPixels[(y*2+1)*ScaledPM.width+(x*2  )] = P_3
         x2PMPixels[(y*2+1)*ScaledPM.Width+(x*2+1)] = P_4
      Next
   Next

   OutputPixmap = ScaledPM

End Function

Hope it's useful, if you're wondering about anything just let me know

EDIT: Replaced crappy download link.

[Ai]

Your method is interesting. Can you post some example before+after images, for those who cannot run ".exe" files?

[lithander]

Cool ErekT! I'll check it out in detail when I get home from work. Is there a way to start the exe in windowed mode?

@Ai: If you give me an image I can use (I don't want to steal someones work and my own is too crappy to serve as reference) I'll post the different results.

[ErekT]

Here you go.

[lithander]

Okay, I ran one of the images Erek posted through the different filters that I've implemented. Realized that my HQ filters can't cope with dithering... how would you upscale dithering in an ideal world?

[blumunkee]

I have never understood the appeal of upscale filtering. Real men don't filter their pixels, they take 'em straight.

Algorithmically the only thing I can think of is adding a dither special case, say any block that looks like a 2x3 or larger dither pattern gets rendered differently.

[lithander]

I have never understood the appeal of upscale filtering. Real men don't filter their pixels, they take 'em straight.

I want to be able to rescale and rotate pixel art. Once you try that and pixels in the new image fall inbetween pixels in the old image and picking the right one becomes tricky. You have to pick because just mixing them like you'd normally do messes up the palette.

Upscaling increases the data available to sample so that you don't have to consider a cluster of pixels to guess the shape but can just pick a local one and trust that it's not too far off. I'll fake some results to make it obvious:



The center one shows less artefacts then the right one thanks to upscaling with Scale4xHQ. I hope to reach even better results in the end.

[ErekT]

Real men don't filter their pixels, they take 'em straight.

Yep, but if you're doing commercial stuff then customers may come in all flavours. Options are always good, no?

[pistachio]

An interesting tool, this. Perhaps you could invent an algorithm that could shrink pixels while keeping it readable? Actually it doesn't seem that plausible when you think about it, but I'm just wondering if it is.

[Conzeit]

I see the point with the rotation stuff. I think maybe a good test would be to take a Boktai floor tile and rotate it, see if it would work for a topdown game?

How does your program compare to the RotSprite one? that one was pretty decent

Pistachio I'm almost sure someone in here posted something like that. Cant remember right now...


Oh, also for non-pixel stuff AlienSkin BlowUp is great...maybe you can take some ideas from there?

Also, when thinking of rescaling I feel the need to mention this http://www.youtube.com/watch?v=vIFCV2spKtg&feature=player_embedded for no particular reason...just that it works very well, maybe some of that logic is necesary when downscaling?


Other than rescaling, there's a filter I've always really wanted to put my pixels trough, it's that TV look filter, Like one of those NTSC filters you have in Kega and Zsnes emulators, if you can do that it'd be great. I asked the guy who makes those filters and he gave me some libraries, if u want em  I can send em to ya :p

[lithander]

The main difference for me when comparing my program with RotSprite is that I have the source code, so I can really shape it like I need it. And I've a lot more planned than what RotSprite currently offers. For example I hope to offer a WYSIWYG interface and allow scaling and rotating at the same time. It's just a fun side project for me but I wan't to improve my knowledge about that topic, see where I can take it. Because if RotSprite is the best tool available so far there seems to be room for improvement.^^

Another nice thing about it is that it should be easy to compile it to Linux and Mac.

When I first heard about the retargeting algorithm I thought it would be a great step for image processing software but I've yet to see it used in any of the programs I use! And thanks for the other tip... "AlienSkin BlowUp" never heard of it but it looks pretty sophisticated. But I can't find any background infos about how their algorithms work.

[Ai]

re: AlienSkin Blowup:
That looks rather similar to a more tuned version of 'smart upscale' from G'MIC -- which is anyway something you should be keeping an eye on if you are interested in image processing

re:Linux, Mac:
Well, if you provide the source, it could happen -- I'm personally interested in trying it (I run Arch Linux), so I'd give porting it a go.
If you want it to be both portable and GUI, probably going to something like GTK+ would work well.

[yrizoud]

Ok so I've put a similar algorithm as rotsprite (but simplified) in Grafx2's latest WIP build :
http://code.google.com/p/grafx2/downloads/detail?name=grafx2-2.4wip1790-win32.zip
It's... rather disappointing.
 Now I understand better what it's good at: it's good at avoiding some patterns where a long straight edge becomes exactly horizontal or vertical and shows "noise", pixels that are randomly of the color of either side.
Here's an explanation of the phenomenon:

On the upper image, the grid intersections show which pixels will be picked by a standard roto(zoom) algorithm. I've put some "zoom balloons" at the bottom to show that  a noisy pattern will emerge from a line that should be straight : black*1, white*3, black*1, white*2, black*1.

Using scale2x to soften the edges statistically reduces the times when a newly-horizontal line has the grid intersect on the parts where the pixels are "spikey". (I should have highlighted... in the picture above with a 45° rotation, there is a 10/16 risk of noise pattern using standard algorithm, reduced to 3/16 with scale2x 3 times)

But it's the only case where I see an improvement... For example with pure line art (single-pixel lines), it still produces a mess of lines that are randomly thicker or interrupted, and it absolutely can't improve the rotation of dithered surfaces, antialiased lines etc... Any case where the pixels are in small cluster, ie. most of the detailed PA.

So... no miracle there, still requires finely tweaking the rotation angle until you find one exact angle the produces the least number of artifacts. Grafx2 has a problem here, as it computes the final coordinates of the 4 new angles (rounded to integer), so you can't make sub-pixel adjustments... and it's some part of code that I have never understood, so I won't be able to fix it.

[lithander]

yrizoud, that visualization you posted is quite nice. Makes discussing the matter a lot easier!

But, first here's one of mine:



As you can see one of the properties of the upscaling algorithm is that they "rounden" the image. Without upscaling diagonals would appear jagged (due to the low resolution) and the artist relies on the eye of the viewer to reconstruct the image. With the right upscaling algorithm the "real" shape of the depicted thing is approximated. And this improves the quality when rotating, transforming and rescaling the image. A chunk of pixels that is meant to have a certain shape is more likely to end up in that shape after the transformation!

My progress is a lot slower then I hoped for (due to a lot of distractions, not because I don't believe in it's doability) but in my most recent build you can freely transform (left mouse button) and rotate (right mouse button) the image allready, and I think that it allready domonstrates that using an upsaled source image does improve the final quality.

PixelPunch003.rar



It's far from perfect but there's still one step in the transformation process that I didn't adress yet. Sampling. Your illustration and explaination show perfectly what causes the artefacts. Now let's say for every green square you count the number of white and black sub-pixels to make a decision. That would get rid of most of the artefacts except where there are diagonals in the source image that introduce jaggedness because of the low resolution in which case (hopefully) the upscaling will kick in.

P.S.: None of the artworks shown in the screenshots are done by me. But they all have been posted on the forums so I hope it's okay for me to use them in the screenshots.

[yrizoud]

> Now let's say for every green square you count the number of white and black sub-pixels to make a decision
This would introduce a bias 'majoritarian color wins'. Maybe it can be countered by choosing a pre-filter that favors (bloats) the smaller pixel clusters.. Like in your screenshot, where a single pixel doubled becomes 5 pixels instead of the theorical 4.

[questseeker]

An idea I'm considering for when I have enough time to write a Gimp plugin is automatically sampling different subpixel offsets and different angles and picking the most common output out of hundreds of samples as the result (the second most common result for each pixel could be put in a separate "second opinion" layer as a reference for handmade corrections).
Hopefully jagged edges would be smoothed out, but maybe to the point of annihilating dithering and antialiasing pixels and altering line thickness.

[lithander]

@questseeker: given that for every pixel in the destination only 4 pixels in the source are close enough to be considered (because when you are not scaling, only rotating all others are more then a pixel away) you shouldn't need hundreds of subsamples to evaluate which one fits best. Whatever result you could achieve with a lot of subsamples you could achieve with sampling only the 4 pixels and some calculations based on their exact position (the fractional part of the coordinate matters now). But I fear that finding the best match out of the 4 possible values is not possible with only considering those 4 pixels. Imagine a single white pixel on a patch of black. In some cases only a small part of the white pixel (roughly a quarter) is overlapping with four destination pixels and when you decide (for each destination pixel individually) wether to write white or black all will become black in all solutions I can come up with right now. :/ How would your plugin solve that?

Upscaling the source should help a little (that's why it's part of my test app) but it's not perfect...

[questseeker]

@lithander:

• I'm considering combined upscaling and rotation, like Rotsprite.
• Upscaling (with arbitrary fancy algorithms) then casting hundreds of "votes" is an elegant and general brute force approach to perform what you gloss over as "some calculations"; more source pixels than the 4 nearest neighbours of the output pixel might have some influence. The appropriate amount of gratuitous upscaling, the pattern of sample positions, and how many samples are enough, are of course three open questions.
• In the isolated white pixel example, it's indeed likely to be obliterated because all output pixels have less than half white in their region of interest, but I don't see it as much of a problem: hand retouching is expected, and by choosing the center of rotation (and thus the alignment between the original and rotated grid) the user has significant control over what "falls through the cracks".
  An upscaling algorithm that inflates isolated pixels at the expense of background ones would distort other features and make clusters of 2 or more white pixels possible, which might or might not be a good tradeoff depending on what is being rescaled.

If preventing dropouts is important, 1:1 scale rotation can be implemented by two successive skew operations: if you shift each column and row a whole number of pixels you get exactly the same pixels that were in the source (plus transparent padding on the sides). This jaggy image could be used as a reference for postprocessing (what source pixels disappeared? Where do I want to restore them?) rather than as an output.

[lithander]

@questseeker:
Interesting ideas! I didn't know that you can achieve a rotation by just shifting rows and columns. That sounds incredible efficient! Do you happen to know any piece of software that implements it so I could see how it looks? Wonder how it compares to nearest neighbour sampling... same goes for your "hundreds of votes" approach: I still think that I could achieve the same effect cheaper but if you'd have an example where this technique is used we could just compare the results?

Also, while I don't expect perfect results I hope to end up with a set of algorithms that produce acceptable results where hand retouching is not necessary. In the scenario I want to use it that would just not be possible. An individual pixel that flickers between visibility and invisibilty depending on the current rotation would be a pretty huge flaw.
But your idea of using a reference to compare against might help here. How about also interpolating the image with a standard approach (that actually mixes close colors together) then, by comparing the local neighbourhood in that smooth-filtered image with the result where we don't mix numbers and based on the amount of difference (error) we reconsider our choice of pixels to reduce the summed local difference in comparision with the reference. Hmmm...

[lithander]

I've updated the first post with a new version of the tool. I added a rather detailed explaination of what the different options do. Also some usage guidelines. So please give it a try and tell me what combination yields the best possible results in your opinion. I find it very hard to judge that. I think that some combinations (Scale3xHQ -> Bilinear Transformation -> Best Fit Wide (or on some images Any)) result in transformed images that preserve the original pretty well but none are without loss. Makes me anxious if this will suffice for the big plan: animated items/characters based on static elements in a source texture.

What do you think? At the moment I don't have any new features planned but if you got ideas let me hear!

[lithander]

Found an interesting paper about vectorization of pixel art. Could be useful as an intermediate format for rotation & scaling, I guess.
http://research.microsoft.com/en-us/um/people/kopf/pixelart/paper/pixel.pdf

[ui]

zooommg....so you did it!! JAJAJA... amazing man! :DDD i will test this like NOW!!! :DDD let us know about any update and thx for your work