Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #1226 > unrolled thread

AppleShop Project - Euclidian Distance and Nearest Color in DHGR - Historical Info if Any?

Back to article view | Back to comp.sys.apple2.programmer

Contents

  AppleShop Project - Euclidian Distance and Nearest Color in DHGR - Historical Info if Any? "Bill Buckels" <bbuckels@mts.net> - 2014-06-04 08:39 -0500
    Re: AppleShop Project - Euclidian Distance and Nearest Color in DHGR - Historical Info if Any? "Bill Buckels" <bbuckels@mts.net> - 2014-06-10 05:14 -0500
      Re: AppleShop Project - Euclidian Distance and Nearest Color in DHGR - Historical Info if Any? Dagen Brock <DagenBrock@gmail.com> - 2014-06-24 12:48 -0700
        Re: AppleShop Project - Euclidian Distance and Nearest Color in DHGR - Historical Info if Any? "Bill Buckels" <bbuckels@mts.net> - 2014-08-07 07:35 -0500

#1226 — AppleShop Project - Euclidian Distance and Nearest Color in DHGR - Historical Info if Any?

Sorry if this is "old hat" to you. Please ignore if so.

You may have seen my post in csa2 about Joel Yliluoma's arbitrary-palette 
positional dithering algorithm:

http://bisqwit.iki.fi/story/howto/dither/jy/

Since we have lots of memory on a modern computer, and a floating point 
processor, even if we are not dithering, I think we can easily take 
advantage of this method of nearest color for conversion of modern graphics 
to any of the Apple II graphics modes, but especially for DHGR and with 
considerably more work (similar to what Jonas has done), for SHR. Believe it 
or not, it is probably also quite effective for LGR and DLGR 16 color 
palette matching which is the same as DHGR... but low resolution limits the 
effectiveness of these lo-res modes to conversion of simple images. It would 
also be effective for normal HGR's 6 colors. Color distance is more 
effective than color loss that occurs through bit shifting I think, so color 
compare is not precise.

This also gives rise to the discussion of what colors we are comparing to... 
the answer to that is that it's always 16 except in HGR where it's 6. The 
other part of that is that for the fixed modes we can use different 
palettes... for example AppleWin colors are what I normally use. But there 
are several palettes that could be tried alternately for best match. In the 
solitary case of SHR the idea would be for best fit of segmented palettes, 
except in Broolks mode3200 which would of course benefit from dithering on 
photos, but the Euclidian Distance can be applied to reducing banding when 
used in conjunction with population method quantization compared to an image 
level color count.

However, the main idea here is that no fixed palette of the input file would 
ever be needed because the colors would always match to one of the 16 colors 
in the same manner that they do today in modern high-end applications. That 
would eliminate the need to do anything but scale the image and perhaps on 
the higher end images that are not photos (which will likely benefit more 
from dithering per the link above) an error diffusion option would create 
smoother transformations. John Bridges said so to me in Apple II 
Enthusiasts. He should know. He wrote the first Paint Program for the PC 
based on what he saw on the Apple II, and stayed with that occupation for 
most of his life so far. I already have classic error diffusion implemented 
in my pile of unreleased stuff for SHR. This article is helpful on extending 
that to include several methods which of course apply to photos especially 
for DHGR but more especially for SHR.

The value of this article is that it is so dummied down that even I can 
understand it. Combined with the fact that it is quite current and very 
broad reaching, so much so that patented algorithms from PhotoShop are 
explained in clear detail.

Back to nearest color...

This is a very simple formula and amounts to using the sqrt of the sum of 
the squared R,G,B gun values of

So based on that hypothesis, I wondered if in all of the Apple II's history, 
did anyone at all ever apply a simple euclidian distance nearest color 
algorithm to posterize r,g,b values in Apple II output? Where? On the IIe, 
IIgs, or as some other utility for MS-DOS or the Mac 68XXX that got lost? 
Was color distance even considered in the early days? Or did people just 
take what little they got in BASIC and think that was cool to see, type-in 
some BASIC lines, and think they did something? Today, expectations are 
high, but where's the programs?

I can think of many reasons why this may not have occurred. The first is the 
lack of access to a math library. The second is the general lack of 
knowledge of this technique by software developers during the time that the 
Apple II and IIgs were viable commercial platforms.

The main reason that I don't think this was likely on the Apple II itself 
was the lack of processor speed. But just in case I am wrong, correct me. 
Quickdraw may or may not have used Euclidian Distance for near colors... if 
it did, did anyone ever do anything with it and if they did, would they have 
published the code for verifiable purposes? Unlikely I think. Trade secrets 
are like privacy rights or Name,Rank,Serial Number in an unmarked grave.

I think it important for me to ask about what has been done on euclidian 
distance for color matching to the Apple II modes. There may be some nuances 
like gamma correction that need to be considered as well. Comments on that 
might also be helpful.

In a vacuum of lack of evidence, I will document this as having likely never 
been done. For the reasons that I gave above. I will also qualify that sort 
of cavalier remark with but due to lack of evidence I don't really know. I 
realize that just because I can't find it, that doesn't mean that it didn't 
happen... someone must have at least considered it.

And having said that, if a real expert like Antoine or Olivier wanted to 
give this euclidian distance idea a try, that would be real interesting too.

As for me, I won't even attempt this on the IIe or IIgs... my idea is to add 
this to all my utilities because every one would benefit. Image scaling 
would be enhanced immensely as well and could include both fixed and 
variable scaling, and existing code highly simplified.

A modern computer has lots of resources. So even do hand-held devices like 
iPhones.

So has this been done? I assume not. This is a partially separate topic from 
dithering and alot simpler one. It addresses a different potential feature 
of AppleShop which currently resides in ClipShop with little more than some 
old HGR routines, and some old PrintShop stuff.

In the grand scheme of things, the dovetail between cc65 and cross-platform 
AppleShop for all Apple II Graphics Modes seems quite clear. But it will not 
be dones in a day or a year, so there is time for some ideas.

Bill 

[toc] | [next] | [standalone]

#1229

"Bill Buckels" <bbuckels@mts.net> wrote:
>I wondered if in all of the Apple II's history, did anyone at all ever 
>apply a simple euclidian distance nearest color algorithm

Sheldon Simms did. And he also did much more.

>So has this been done? I assume not.

But I assumed wrongly...

http://wsxyz.net/tohgr.html

Windows version archive is now fixed and Sheldon has also put the source 
code online and made it freely available.

Thanks Sheldon.

Bill

[toc] | [prev] | [next] | [standalone]

#1235

Hi Bill,

Sorry I'm not very familiar with the early HGR/DHGR converters and such.  I just came here to say that I based some of my IIgs image conversion experiments on CIEDE2000.   I guess you could say it's Euclidian Distance within a defined color space and perceptual adjustments.  

The only reason I bring it up is that there is a difference between a simple algorithmic distance, and human eye perceptual difference (psychovisual).  Our eyes have bias for certain colors (among other weird things, like tetrachromacy).  I used a PHP library, but it was painfully slow for production code, but there are other implementations out there for one to absorb into their own code.  I ended up scrapping it anyway, but I just wanted to make the point that there are other algorithms out there that try to compensate for the way our eyes (generally) work.  

http://en.wikipedia.org/wiki/Color_difference#CIEDE2000


Sorry if this is old news or if I've repeated myself from other posts. 

[toc] | [prev] | [next] | [standalone]

#1268

"Dagen Brock" <DagenBrock@gmail.com> wrote:
> I just came here to say that I based some of my IIgs image conversion 
> experiments on CIEDE2000.   I guess you could say it's Euclidian Distance 
> within a defined color space and perceptual adjustments.

That's precisely it.

http://bisqwit.iki.fi/story/howto/dither/jy/

>The only reason I bring it up is that there is a difference between a 
>simple algorithmic distance, and human eye perceptual difference 
>(psychovisual).

My last couple of converters apply Euclidian Distance and the Pychovisual 
Model. I am currently attempting to develop a simpler horizontal alternating 
ordered dithering algorithm.

I have an error diffusion filter in place but I am not convinced that 
smearing the colors diagonally is as effective for DHGR and HGR conversions 
of complex images as smearing the colors in the xaxis only like in a 2 pixel 
merge. But a merge dulls the colors and somewhat defeats the PsychoVisual 
model.

My suspicion is that alternating a horizontal dither between line pairs 
using a simple pair of thresholds for pixel pairs, one  based on the kegs 
palette that we both use with the safe colors, and the other being a 
midpoint threshold variation, might work well enough.

I hope to try this later today before advancing to the other methods in 
Joel's paper.

Bill 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.sys.apple2.programmer

csiph-web