📄 371-374.html
字号:
<HTML>
<HEAD>
<META name=vsisbn content="1558515682"><META name=vstitle content="Java Digital Signal Processing"><META name=vsauthor content="Douglas A. Lyon"><META name=vsimprint content="M&T Books"><META name=vspublisher content="IDG Books Worldwide, Inc."><META name=vspubdate content="11/01/97"><META name=vscategory content="Web and Software Development: Programming, Scripting, and Markup Languages: Java"><TITLE>Java Digital Signal Processing:Image Processing in Java</TITLE>
<!-- HEADER --><STYLE type="text/css"> <!-- A:hover { color : Red; } --></STYLE><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW">
<!--ISBN=1558515682//-->
<!--TITLE=Java Digital Signal Processing//-->
<!--AUTHOR=Douglas A. Lyon//-->
<!--PUBLISHER=IDG Books Worldwide, Inc.//-->
<!--IMPRINT=M & T Books//-->
<!--CHAPTER=9//-->
<!--PAGES=371-374//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="365-371.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="374-378.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>Traversing the vector list in the minimum time is a similar problem to that faced by a mail carrier starting from a post office and delivering letters to each block with minimum walking. This is called the <I>Chinese postman problem</I> [Roberts].</P>
<P>Another application of critical need in network communications is in data compression. If we could transmit a geometry faster than a bitmapped rendering of the geometry, we could render the geometry at any resolution using a Java program running on the client. For example, suppose that we wanted to distribute a popular test pattern (such as color bars). We could render the test pattern at various resolutions and then download them over the net, but this approach would waste of bandwidth and local data storage. Color bars consist of 11 rectangles of various sizes and colors. A 640 × 480 image of color bars could take more than 300K of memory. The program needed to store and display 11 rectangles takes less than 100 bytes of memory (and is much more flexible!).</P>
<P>Before a raster to vector conversion can start, we assume that we have good edges. Edge detection is a thorny problem and can be accomplished in one of several ways. We have already seen how to perform edge detection using a high-pass filter created with an FFT. In Chapter 7 we saw how a domain-specific edge detector can find the centroid of a thick edge. Sometimes we need to combine methods, such as the auto-scale and negate methods, with a threshold. In this section, we assume that a good edge-detected image is used as input. The goal is to take the edge-detected image and create a vector description of it. Figure 9.13 shows the output of the edge detector and the result of a raster to vector conversion. The file was saved as line segments to a PICT file.</P>
<P><A NAME="Fig13"></A><A HREF="javascript:displayWindow('images/09-13.jpg',437,360 )"><IMG SRC="images/09-13t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/09-13.jpg',437,360)"><FONT COLOR="#000077"><B>Figure 9.13</B></FONT></A> Raster to vector converter.</P>
<P>The basic idea in raster to vector conversion is that a list of integer coordinates of the following form should be used as input:
</P>
<!-- CODE SNIP //-->
<PRE>
x1 y1
x2 y2
...
</PRE>
<!-- END CODE SNIP //-->
<P>The output consists of a series of vectors of the following form:
</P>
<!-- CODE SNIP //-->
<PRE>
x1 y1 x2 y2
x3 y3 x4 y4
...
</PRE>
<!-- END CODE SNIP //-->
<P>The idea is that the points used as input will exhibit intraframe coherence. We exploit this coherence by connecting the dots (the white pixels). The success of the algorithm depends on many points satisfying a <I>criterion of adjacency</I>, which is used to determine when two points are next to each other.</P>
<P>Typically, we say that two points are adjacent if they lie within a circle whose radius is one pixel. If two points are adjacent they can be used to form a line segment that is exactly two pixels long. The line segment consists of a head, a tail, and a slope. The compression ratio depends on the quality of the image edge detection, the amount of intraframe coherence, and the criterion of adjacency. Using a randomly selected GIF image found on the Internet, we were able to take 1,314 points (edge-detected pixels) and create 51 editable lines (a 25:1 compression ratio). When converting an image that contains lines (such as diffraction grating), the compression ratio increases to 132:1. Furthermore, our slope tolerance was very tight, so there was no introduced distortion. Our experience with various images indicates that it is difficult to generalize about the expected compression ratios.</P>
<H4 ALIGN="LEFT"><A NAME="Heading10"></A><FONT COLOR="#000077">A Raster to Vector Algorithm</FONT></H4>
<P>In this section we present an algorithm that runs in <I>O</I>(<I>N<SUP>2</SUP></I>), where <I>N</I> is the number of input points. We start with a set of points in a point list, <I>pl</I>. Our objective is to create a set of vectors, <I>v</I>. The following code is excerpted from the <I>Xy2vec</I> class in the <I>lyon.ipl</I> package:</P>
<!-- CODE SNIP //-->
<PRE>
public static void main(String args[]) {
Vector v = new Vector();
PointList pl = new PointList();
Xy2vec x = new Xy2vec();
</PRE>
<!-- END CODE SNIP //-->
<P>The following line reads the points from an input file and places the data into the point list <I>pl</I>:</P>
<!-- CODE SNIP //-->
<PRE>
x.readPoints(pl);
</PRE>
<!-- END CODE SNIP //-->
<P>The point list is treated as a stack, where the <I>popPoint</I> method returns a point from the top of the stack:</P>
<!-- CODE SNIP //-->
<PRE>
Points p = pl.popPoint();
</PRE>
<!-- END CODE SNIP //-->
<P><I>Points</I> is a point list data type, a class in the <I>lyon.ipl</I> package that we cover in a later section. In the following <I>while</I> loop, we check to make sure that the point list is not empty. Our objective is to place the point in one of a list of vectors. If we cannot, we make a new vector:</P>
<!-- CODE SNIP //-->
<PRE>
while (p != null) {
boolean point_not_stashed = true;
// Empty vector ?
if (v.size() == 0) {
</PRE>
<!-- END CODE SNIP //-->
<P>The <I>Vec</I> class is another class in the <I>lyon.ipl</I> package. An instance of a <I>Vec</I> consists of a head, a tail, and a slope. When a <I>Vec</I> instance is first created, the tail is null. To keep track of this, we provide a flag called <I>tail_is_empty</I>. We set this flag to true whenever we make a new <I>Vec</I> instance. To complicate matters somewhat, the list of <I>Vec</I> instances is stored in an instance of the <I>Vector</I> class, <I>v</I>.</P>
<!-- CODE SNIP //-->
<PRE>
Vec W = new Vec(p);
W.tail_is_empty = true;
v.addElement(W);
point_not_stashed = false;
} else {
</PRE>
<!-- END CODE SNIP //-->
<P>For each <I>Vec</I> instance in the list of vectors, <I>v</I>, we test to see whether the point is adjacent to the <I>Vec</I> instance. If it is, we test to see whether the slope is within a tolerance. If the point is adjacent to the vector’s endpoints and the slope is within tolerance, we grow the vector by one point. We then declare that the point is placed in the list of vectors and move to the next point. If we cannot place the point, we create a new vector with the orphaned point at the head.</P>
<!-- CODE //-->
<PRE>
for (int i=0; (i<(int)v.size())&&point_not_stashed;i++) {
Vec newV = (Vec)v.elementAt(i);
if (newV.head.isAdjacent(p)&&
newV.isSlopeAcceptable(p)) {
newV.addHead(p);
point_not_stashed = false;
}
// Put new point to tail
if (point_not_stashed) {
if ((newV.tail_is_empty &&
newV.head.isAdjacent(p))||
(!newV.tail_is_empty &&
newV.tail.isAdjacent(p)&&
newV.isSlopeAcceptable(p))) {
newV.addTail(p);
if (newV.tail_is_empty) {
newV.tail_is_empty = false;
newV.getSlope();}
point_not_stashed = false;
}
}
}// for
// Put new point to head
if (point_not_stashed) {
Vec nv = new Vec(p);
nv.tail_is_empty = true;
v.addElement(nv);
point_not_stashed = false;
}
}
</PRE>
<!-- END CODE //-->
<P>After we are finished with the point, we proceed to the next point:
</P>
<!-- CODE SNIP //-->
<PRE>
p = pl.popPoint(); // Get new point
}// while
x.printOutData( v);
</PRE>
<!-- END CODE SNIP //-->
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="365-371.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="374-378.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<hr width="90%" size="1" noshade><div align="center"><font face="Verdana,sans-serif" size="1">Copyright © <a href="/reference/idgbooks00001.html">IDG Books Worldwide, Inc.</a></font></div>
<!-- all of the reference materials (books) have the footer and subfoot reveresed --><!-- reference_subfoot = footer --><!-- reference_footer = subfoot --></BODY></HTML><!-- END FOOTER -->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -