有关图像的色彩分离以及颜色替换 (200分)

P

pomb

Unregistered / Unconfirmed
GUEST, unregistred user!
问题是这样的:一副图像(可能是256,也可能是真彩),需要根据用户指定的颜色数,将整个
图像全部表示为N种色彩(这些色彩可以是原图中的某些颜色,也可以根本是原来没有的).
要求:1.这可跟256->16色转换完全不同的,千万不要告诉我什么PixelFormat := pf4bit之
类的说:)
2.要求在N远小于原图的情况下(例如真彩转16色),图像尽可能保留原图边界区域,即,
颜色可以根原来差别很大,但原图中差别比较明显的地方最好不要使用同种颜色.
3.速度尽可能快(这个速度可以不必考虑Delphi的TCanvas读写象素点颜色的影响,
小弟已经参照FastBmp写出一个方便操作的类).
4.如有什么介绍色彩学及颜色分离方面的科技期刊网站之类的介绍一下,也许也能
得分哦!
 
G

g622

Unregistered / Unconfirmed
GUEST, unregistred user!
没学过色彩学,瞎说几句,
似乎是要得到需要替换得图的色彩范围,然后按条件把范围量化为n,
直接分析频域只能得到灰度的分布,可以先求所有点和相临点的差值,然后把差值,本点,
相临点记录在数组内,然后可以统计出哪两种颜色在图中构成了大多数的边界,选择前n对
也就得到了n个需要直接转换的颜色值,他们向你提供的颜色集转换过程中应该使每对的差
异最大。(可以考虑sqr((r1-r2)^2+(g1-g2)^2+(b1-b2)^2)的值最大,但严格说似乎该考虑
眼睛对色彩敏感不同吧)对于图中其他的颜色只要判断和统计出的前n种颜色哪种最接近即
可。呵呵是这样吗?
 
P

pomb

Unregistered / Unconfirmed
GUEST, unregistred user!
谢谢你的意见,你说的是对的,正是需要根据一定的规则将整幅图中涉及的颜色量化为
N(其实应该叫做聚类).现在的关键在于难以确定一个有效的准则来划分这N个类.
曾经试过的方法有:根据灰度值,将最小灰度和最大灰度之间划分为N阶,然后根据落点取
色彩平均去替换,结果是边界较明显而颜色差太多;也试过方差由小到大聚类,我是用的
比较笨的方法,速度奇慢,但我想用方差的话是两两之间的关系,那么比较次数一定非常大,
对于颜色值较多(比如真彩)的图像恐怕要Game Over;其他诸如什么HSI,RGB平均,甚至灰度+
HSI都试过了,效果都不能说很好,所以才上来问的说:)
不管怎么说,谢谢你给了个意见的说:)
 
P

pomb

Unregistered / Unconfirmed
GUEST, unregistred user!
怎么没人愿意回答呀? 难道大家只对有现成答案可抄的问题感兴趣吗?如果是这样的话我
早就抄了呀!真失望啊!
 
W

wjiachun

Unregistered / Unconfirmed
GUEST, unregistred user!
pomb:如果你还要继续讨论请定期提前你的帖子,如果不想继续讨论请结束帖子。
 

吕雪松

Unregistered / Unconfirmed
GUEST, unregistred user!
我想问题的关键就是如何找到一个有效的符合你要求的计算象素在某象限内取值的公式。
我想一般的线性方程是不行的,在边界处的变化是不连续的,而且离采样点越远变化越快。
多选几个拟合方程试试。
 
W

wang_junfan

Unregistered / Unconfirmed
GUEST, unregistred user!
根据灰度值,将最小灰度和最大灰度之间划分为N阶,然后根据落点取
色彩平均去替换,这种方法理论上是可行的,但人的眼睛对不同灰度
范围的色彩感觉不同,在色彩亮度较低的区域,人的眼睛对光线强弱
十分敏感,色彩亮度较高的区域,人的眼睛对光线强弱分辨能力较差
;即‘非线性’,这需要用各种曲线方程进行运算,目前还没有十分精
确的方程,你最好根据你要转换的色彩的性质自己尝试几种方程,然
后选择速度和效果较好的方程,如:F(X):=SQR(X*X-2X)<N;
 
J

JohnsonGuo

Unregistered / Unconfirmed
GUEST, unregistred user!
我个人认为不应该使用在灰度进行处理。很明显一幅红字灰底的图片,
进行灰度处理的话极有可能是整幅图象都变为只有一种颜色了。
我认为应该使用HSV空间来表示颜色,对图象中的象素的色调值(Hue)绘制直方图,
通过直方图提取峰值来对颜色选择会比用灰度图象来选择颜色要好得多。
 
Z

zytzjx

Unregistered / Unconfirmed
GUEST, unregistred user!
这个问题不能只根据灰度,还要根据色相,要利用方差最小才可以。
 
P

pomb

Unregistered / Unconfirmed
GUEST, unregistred user!
首先应当感谢各位的指教.
To 千堆雪:文章看过了,谢谢.有一处不懂,请指教:对真彩色来说,通常在R,G,B分量上会
包含0~255所有的值,那么WidestColor应如何选择?这里在R,G,B分量上的最大差都是255.
这样,按照击中的频率和来划分色彩区域好像不知如何下手?
To JohnsonGuo :
好像仅仅根据色相是不行的说,我已经试过了.
 
O

OopsWare

Unregistered / Unconfirmed
GUEST, unregistred user!
知道俺的E文差,卷起千堆雪tyn还是贴了这么多的洋码子,头晕。。。
如果转换中颜色数差别较大,就要使用抖动算法了。
那.GIF就是最好的例子,GIF最高只支持256色,可以研究一下的。
 

卷起千堆雪tyn

Unregistered / Unconfirmed
GUEST, unregistred user!
给你一篇文章看看!
Most digitized images use 24 bits per pixel. That's 16 million colors. The problem is that most color monitors
show only 256 colors at a time. I discovered this several years ago as I struggled to get a video digitizer
ready for a trade show. Almost too close to the deadline, I found out that it's a long step between capturing
a 24-bit image and making it pretty on an 8-bit screen.
Somehow, I had to pick the 256 colors that best represented all the subtle shades of the original image.
then
I had to map those thousands of shades into my chosen 256 colors. It's a tough problem, common to most
image-handling software, and I think you'll find the solution a fascinating brain-twister in solid geometry.
I have to confess that I didn't invent the color-selection algorithm. I got it from Paul Heckbert's excellent
theoretical article, "Color Image Quantization for the Frame Buffer Display" (Computer Graphics. 16[3]:297- 307).
This article will show you how his algorithm works and how you can apply it to any limited-palette monitor,
such as EGA and VGA displays. My program runs on the Mac II in 68000 assembler.
First, let's take a close look at a color image. Fresh off the digitizer, a typical image uses 24-bit pixels
having 1 byte per color component, as shown in Figure 1. Each pixel is one of 16 million variations of red,
green, and blue (256-by-256-by-256). The pixels are laid out in a rectangle, 640-by-480. This gives us
a grand total of 307,200 pixels per image, with 3 bytes per pixel or just under a megabyte of data.
For simplicity, let's assume the display buffer for the color monitor is also 640-by-480. That way,
the only difference between the image and display buffers is the size of the pixel.
The display buffer uses 8-bit pixels, which are not actually colors but indexes into a small palette of colors.
On an 8-bit display card, like a VGA card for the PC or an Apple color card for the Macintosh, we choose a small
palette of 256 colors from some larger range determined by the hardware. then
we load these colors into the color
look-up table on the display card. (On the Macintosh, youdo
n't directly load the video card. Instead, you go
through the Palette Manager. This little piece of indirection leaves some of the more subtle problems, such as
hardware independence and multiple palettes, in Apple's hands.) The look-up table translates an eight-bit palette
index into the corresponding video display color.
Translating
Now we've set up the hardware to correctly translate an image composed of 8-bit palette indexes. Our digitized
image, however, is built from 24-bit pixels. We need to translate these pixels into palette indexes and put
them in the video display buffer.
Let's say our image pixel is described by its three color components, RiGiBi. We want to find the palette
index k such that the palette color RkGkBk is the best match for the image pixel. We want to minimize the
difference equation:
d = abs (Ri - Rk) + abs(Gi - Gk) + abs(Bi-Bk)
Unfortunately, we need to calculate d for each of 256 palette entries and each of 307,200 pixels.
That's about 78 million calculations just to translate the image into palette indexes. Later,
I'll show you how we can apply a strategy that gets around all these calculations.
So here's the problem. We need to choose a small palette of colors that best represents the full
range of colors in the image. We also need to translate the image from 24-bit colors to 8-bit palette indexes.
The first step in choosing the palette is to find out which colors are used in the image. Every pixel
could be the same shade of blue or a different color. To find our palette, we'll use a histogram to count how many times each color occurs.
Color Histogram
If we collected a histogram for every possible color, we'd need 16 million one-word entries;
that is, a 32MB table. To conserve memory,
we'll limit the range of our histogram to 215 entries by using only the upper five bits of each color component, as shown in Figure 2.
Naturally, this will cost us in color resolution. By ignoring the low three bits, we lumped together the nearest eight shades of each
color component. Each histogram entry represents a group of colors consisting of the 512 neighboring shades of red, green, and blue
(8-by- 8-by-8).do
es this hurt the appearance of our displayed image? Sure itdo
es. But as we move from 16 million to 256 colors,
we'll be losing quite a bit of color resolution anyway.
To calculate the histogram, first we set all entries to zero. then
we make one pass through the original image, converting
every 24-bit pixel to a 15-bit index and incrementing the count at that index.
Listing the Colors
Most imagesdo
n't contain every color. In my experience, a typical image captured with a good camera uses fewer than 5,000
of the 32,000 colors available in the histogram. These are the colors we're interested in, and wedo
n't need to waste time
on the others. So we'll create an array called colorList, containing only those 15-bit color indexes that appeared in the
image. Finally, we're ready to choose the colors.
Let's get into that solid geometry I promised you earlier. Imagine that all possible colors are represented with a
three-dimensional matrix, where the three axes are the color components red, green, and blue. Each component has five
bits of resolution, as in our histogram, or 32 shades.
Our digitalized image will typically use fewer than 5,000 of the 32,000 colors. In fact, the color histogram is this cube,
with the nonzero entries representing the colors in our image. What we'd like todo
now is carve the cube into 256 equal
regions. But whatdo
we mean by equal?
If we divide the color cube into regions of equal volume, we'll get a uniform distribution of all the colors. This is called
a uniform palette. It's a useful first approximation, but itdo
esn't take into account the actual distribution of colors in
our image. In other words, it treats a blue seaside vista the same as a crimson summer sunset, as shown in Figure 3.
Instead, we'd like to divide the cube into regions of equal color count, where the color count is the sum of the histogram
counts enclosed by each region. For example, the sunset image has heavily shaded mixtures of red and green. That means the
colors occur most frequently toward the far-upper right corner, as already shown. Since we'll want our palette to have more
colors in that area, we should carve more regions from that area. The regions should be smaller and more numerous where
the histogram color counts are highest. Now, howdo
we write an algorithm that will create those regions?
Data Structure
Let's start by representing a three-dimensional rectangle within the color cube as a data structure called colorRect,
shown in Listing 1. Remember that colorList contains all the colors that appeared in the image. first and last define
a range within colorList, the image colors that fell within the region. In Figure 4, first is 271, and last is 276.
histSum is the sum of the color counts for the colors in the region. In Figure 4, histSum is 820.
mins and maxs are the geometric coordinates of the region. The mins represent the near upper-left corner. The maxs
represent the far lower-right corner. A typical region within the cube might look something like Figure 4.
The colorList for this region has only six colors, shown with their associated histogram counts. Notice how the list
is sorted by red, then
green, then
blue. That's because the widestColor is red.
The widestColor is the color component with the longest leg of the region. In Figure 4, red is the widestColor, with four shades.
red, green, and blue are the palette colors. When we've created every region, we'll come back and figure out what
color we want in the palette for each region. Every image color that maps into this region will be displayed with this palette color.
The Algorithm
To initialize the algorithm, we'll create a single colorRect that encloses the entire RGB cube. We'll set the mins to 0 and the
maxs to 31, enclosing the cube. then
, we'll set first to 0 and last to the end of colorList to include all the colors that appeared in the image.
Now we're ready to divide the cube, in this fashion:
* Scan the colorList from first to last, finding the minimums and maximums of each color component and adding the color counts to histSum.
Afterdo
ing this, we can determine the widestColor by comparing the mins and maxs and selecting the component with the biggest difference.
* Sort the colorList colors within the region in order of the widestColor. This prepares us for the next step.
* Find the median. Scan through the colorList again, from first to last, adding the color counts to a running sum. When the running sum
equals half the histSum, we've found the median point. We'll adjust this median point so it always breaks between two shades of the
widestColor. In the preceding example, the best median is between (11, 8,18) and (11, 9,17), two colors that have the same shade of red.
But since we need to break between shades of red, we'll set the median between (10, 8,17) and (11,8,18).
* Split the cube into two regions. Create two colorRects from the current colorRect, dividing the colorList range at the median.
We've created two regions from one by splitting the region on its longest axis at the point where the color counts in the two halves were roughly equal.
To build 256 regions, we just continue this process until we've used 256 colorRects. The time-consuming part is the number of
times we sort the colorList. We sort it each time we create a new region, each time sorting successively smaller portions of the list.
I used the quick-sort method from Carl Reynolds' "Sorts of Sorts" (COMPUTER LANGUAGE, Mar. 1988, p. 56).
What? No Recursion?
Any eager student of computer science would latch onto this as one of the rare opportunities to use recursion. That's how I first tried
to solve this problem, using the approach shown in Listing 2.
As I discovered, recursiondo
esn't work. It creates what (I later remembered) is called a depth-first spanning tree, subdividing
only the lesser regions in each recursive call. It never gets around to subdividing the greater regions.
Instead, at each iteration, we want to choose the largest of all the remaining regions for the next division. The method I wound up
using chooses the region with the highest color count. To find that region, I built an index list for the colorRect structures
and wrote routines to insert and remove those structures in order of their histSum. Now our algorithm looks like Listing 3.
Assigning Colors
Once you've created the regions, it's easy to assign them color values. Just add up all the colors that occurred in the region,
multiply each by its histogram count, and divide by the total count for the region, as shown in Listing 4.
So far, we've been determining which colors appear in the palette. Now we need a look-up table that translates an arbitrary
24-bit color to the index of the closest palette color. We saw earlier that it can take 78 million iterations to translate a
640-by-480 image. And I said we'd find a way around that.
Somehow, we need to map the colors in our RGB cube to the palette indexes. But that's exactly what the colorRect structure
does with mins and maxs that define the geometric bounds of each palette color. All we need todo
is fill another RGB cube
with palette indexes, and we've got our lookup table color. Given an arbitrary 24-bit color, we first convert it to a 15-bit
color, then
use that 15-bit color as an index into the cube and look up the corresponding palette index. Any color that falls
within that region gets the same palette index.
Listing 5 shows the code to initialize the palette look-up table for one region. This algorithm is strictly linear, which means
that the inner loop executes only once for each look-up table entry.
That's it. We've chosen 256 good colors from our original image and built a map to translate that image into the smaller palette.
But Is It Fast?
We have bridged the gap between 24-bit scanners and 8-bit monitors by modeling the data geometrically and applying classic
divide-and-conquer techniques. More to the point, perhaps, we let people like Paul Heckertdo
this for us and concentrated on
a good engineering implementation.
I can tell you the results in hard numbers. This algorithm executes in six seconds on a MacIIx, converting a 640-by-480 image
from 24-bit pixels to 8- bit indexes and yielding a high-quality displayed image. A well-written but brute-force solution
takes about 70 seconds and yields a lesser-quality image. It took me about three weeks to write and debug the code resulting
in 30 pages (1,500 lines) of assembler and a 9K object file.
Thanks to Dave Pratt and Vivian Russell of Digital Vision Inc. for giving me permission to write this article. All the software
described here was written under contract to Digital Vision as part of its ComuterEye video digitizer.
Dave Pomerantz is president of Micro Alliance Inc., a software consulting firm in Wakefield, Mass.
 
W

wjiachun

Unregistered / Unconfirmed
GUEST, unregistred user!
接受答案了.
 

Similar threads

D
Replies
0
Views
443
DelphiTeacher的专栏
D
D
Replies
0
Views
361
DelphiTeacher的专栏
D
D
Replies
0
Views
248
DelphiTeacher的专栏
D
S
Replies
0
Views
835
SUNSTONE的Delphi笔记
S
S
Replies
0
Views
429
SUNSTONE的Delphi笔记
S
Top Bottom