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

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

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

Show all headers | View raw

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 

Back to comp.sys.apple2.programmer | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

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

csiph-web