CSE 382 Algorithms and Data Structures

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Laboratory 5 - Tracing Images

Introduction

So far the array is the only data structure that you have used for constructing programs.  Over the years,  software engineers have developed a rich collection of data structures which simplify program design.  The Java Collections framework includes a number of powerful data structures which you will study during the remainder of the course.  While you may later simply use these structures,  during the course itself you will construct your own versions in order to better understand how they work. 

A list is an expandable collection of elements in which each element has a position or index relative to the other members of the list.  Iterators are used to sequentially access members of a list.  This ability to sequentially prowerful lists is very useful.  In this laboratory,  you will use lists in picture processing. 

Getting Started

Create a new directory for the files of this exercise, and in it, save copies of the files:  LinkedList.javaIteratorDemo.javastrawberry.jpg,  and Tracer.java

Implementing Lists

Implement your List class as a doubly-linked list as shown in class.  Also,  be sure to implement a finalze() method for both your LinkedList and Node classes which unlinks all of their pointers.  Remember to implement the Iterator ADT and a ListIterator and the listIterator(int index) method for your LInked List.  You should also invoke super.finalize() as the last statement in your finalze() method. 

Field Summary
protected  int modCount
          The number of times this list has been structurally modified.
 
Constructor Summary
LinkedList()
          Constructs an empty list.
LinkedList(Collection c)
          Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
 
Method Summary
 Object clone()
          Returns a shallow clone of this List.  The stored objects are not duplicated.  The copy will contain a reference to a clone of the internal LinkedList, not a reference to the original internal LinkedList of this Stack object. 
 boolean contains(Object o)
          Returns true if this list contains the specified element.
 boolean containsAll(Collection c)
          Returns true if this list contains all of the elements of the specified collection.
 boolean equals(Object o)
          Compares the specified object with this list for equality.
 E get(int index)
          Returns the element at the specified position in this list.
 int hashCode()
          Returns the hash code value for this list.
 int indexOf(Object o)
          Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not contain this element.
 boolean isEmpty()
          Returns true if this list contains no elements.
 Iterator iterator()
          Returns an iterator over the elements in this list in proper sequence.
 int lastIndexOf(Object o)
          Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element.
 ListIterator listIterator()
          Returns a list iterator of the elements in this list (in proper sequence).
 ListIterator listIterator(int index)
          Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.
 int size()
          Returns the number of elements in this list.
 List subList(int fromIndex, int toIndex)
          Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
 Object[] toArray()
          Returns an array containing all of the elements in this list in proper sequence.
 Object[] toArray(Object[] a)
          Returns an array containing all of the elements in this list in proper sequence; the runtime type of the returned array is that of the specified array.
 String toString()
          Returns a string representation of this Stack, containing the String representation of each element. 

Optional Methods Required for this Project

You will need to implement a number of the "optional" List methods in addition to the required methods shown in the table above.  These additional methods will allow you to add and remove points from your list. 

Method Summary
 boolean add(Object element)
          Appends the specified element to the end of this list. 
 boolean add(int index, Object element)
          Inserts the specified element at the specified position in this list. 
 boolean remove(Object o)
          Removes the first occurrence in this list of the specified element. 

Implementing ListIterators

You will need to implement a ListIterator class to support your List class.  As we discussed in class, Iterators can be dangerous.  This is because a list can be modified behind the back of an iterator.  The Java Class Library solves this by throwing an exception when you try to use an Iterator after the List has been modified without first effectively reseting the Iterator.  This is accomplished by maintaining a structural modification count for each LinkedList object.  A ListIterator must initialize its copy of the modification count when it is constructed.  ListIterator methods will throw an exception if its copy of modCount does not match the version of modCount maintained by the List object.  Consequently,  we are able to maintain our iterators as specialized nodes which are not actually part of the the list chain.  While the father and son links inside the ListIterator attach to nodes in the List,  no node in the List links to one of its iterators.  The optional Iterator methods set and remove both modify the List structure.  These two methods must increment both the copy modCount maintained by the and the version maintained by the List. 

You can implement your Iterator as if it were an extension of the Node class.  Your Iterator will have a specialized constructor method which must copy the value of modCount into an an internal final variable.  Your iterator must also maintain a link to the current value of modCount in your LinkedList ojbect.  This is not necessarily as difficult as it appears if your Iterator class is defined internally to your List class and implement the Iterator interface.  As an alternative,  you can encapsulate modCount as an Integer object and pass the object to your ListIterator when it is constructed.  Since your ListIterator will have access to the internal nodes of your List it will be able to access your list as long as the list's structure is not modified. 

Iterators are inherently more efficient for doubly linked lists than for singly linked lists.  Specificly,  the problem is with the previous accessor method.  The cost of next is O(1) for both singly and doubly linked lists,  but the cost of previous is O(n) for singly linked lists. 

Field Summary
int index
          The current location of the iterator relative to the begining of the list.  The index is 0 when the iterator is to the left of the first list element.  The index is equal to the List's count when it is to the right of the last element in the list.
Node left
          The Node in the List to the left of the iterator.
int modCount
          Set equal to the modCount of the parent List when the iterator is created or when the same iterator successfully adds or removes a node.
Node right
          The Node in the List to the right of the iterator.
 
Method Summary
 boolean hasNext()
          Returns true if this list iterator has more elements when traversing the list in the forward direction.
 boolean hasPrevious()
          Returns true if this list iterator has more elements when traversing the list in the reverse direction.
 Object next()
          Returns the next element in the list.
 int nextIndex()
          Returns the index of the element that would be returned by a subsequent call to next.
 Object previous()
          Returns the previous element in the list.
 int previousIndex()
          Returns the index of the element that would be returned by a subsequent call to previous.
 
Optional Methods
 void add(Object o)
          Inserts the specified element into the list.
 void remove(Object o)
          Removes from the list the last element that was returned by next or previous.
 void set(Object o)
          Replaces the last element returned by next or previous with the specified element.
 

Loading Images

When you think of digital images,  you probably think of sampled image formats such as the JPEG image format used in digital photography,  or GIF images commonly used on web pages.  All programs that can use these images must first convert them from that external format into an internal format.  Java 2D™ supports loading these external image formats into its BufferedImage format using its Image I/O API which is in the javax.imageio package. Image I/O has built-in support for GIF,  PNG,  JPEG,  BMP,  and WBMP.  Image I/O is also extensible so that developers or administrators can "plug-in" support for additional formats.  For example, plug-ins for TIFF and JPEG 2000 are separately available.  To load an image from a specific file use the following code:


BufferedImage img = null;
try {
    img = ImageIO.read(new File("strawberry.jpg"));
    } catch (IOException e) { }

Decoding Images

The BufferedImage class provides a common environment for reading and decoding images.  The core data structure inside a BufferedImage is a rasterized image called a Raster.  A rasterized image consists of rows of colored dots or picture elements called pixels.  Raster images are commonly used in televison and for computer displays.  You can retrieve an individual pixel from a BufferedImage object by calling its getRGB() method and supplying the x,y coordinates of the pixel as arguments of type int. The pixel is returned as type int in the TYPE_INT_ARGB format,  which consists of four 8-bit values for the alpha and RGB color components packed into the 32-bit word.  There is also an overloaded version of getRGB() that returns an array of pixels from a portion of the image data. 

BufferedImage Methods
 int getHeight()
          Returns the height of the BufferedImage
 int getRGB(int x, int y)
          Returns an integer pixel in the default RGB color model (TYPE_INT_ARGB) and default sRGB colorspace. 
 int[] getRGB(int startX, int startY, int w, int h, int[] rgbArray, int offset, int scansize)
          Returns an array of integer pixels in the default RGB color model (TYPE_INT_ARGB) and default sRGB color space,  from a portion of the image data. 
 int getWidth()
          Returns the width of the BufferedImage

Decoding ARGB Pixels

This type constant indicates that the image uses a direct color model.  A direct color model means that the value of each pixel contains the complete information about its color.  Each pixel is coded on one integer (four bytes).  The information coded in each pixel is the red,  green,  and blue (RGB) components of the color used by the pixel.  Each color component is coded on a single byte.  The fourth byte is used to represent the transparency of the pixel,  sometimes also known as the alpha component of the color.  Images of this type can have a transparent background,  or they can be translucent.  The following code fragment grabs the pixel at x, y and extracts the four fields.  This works because & performs a bitwise AND operation and 255 is equivalent to all of the bottom eight bits containing a 1 (TRUE) and the remaining bits containing a 0 (FALSE).  The >> operation shifts the bit pattern in code to the right by eight bits,  thereby moving each of the original four ARGB fields into the bottom eight bits.


	int code   = buffer.getRGB(x,y);
	int fieldB = code & 255; code = code>>8;
	int fieldG = code & 255; code = code>>8;
	int fieldR = code & 255; code = code>>8;
	int fieldA = code & 255;
You can calculate the luminosity by summing the individual color components.  Transparancy is a multiplicative factor. Recall that A,  R,  G,  and B should all have maximum values for an opaque white field. 

Outlining Images

Image processing programs such as Adobe Photoshop often have facilities for outlining images and simplifying these by reducing the number of vertices in the resulting sketch.  The remaining vertices are sometimes called critical points.  You will write a program which constructs a a list of critical points

A two-dimensional shape can be defined by its boundary-polygon, which is simply a list of all coordinates ordered by a traversal of its outline.  The original image is traced to produce an outline.  The outline can then be simplified to produce an abstract boundary,  using only the "most important" vertices.  We can assign an importance measure to a vertex P by considering its neighbors L and R.  We compute the lengths of the line segments LP, PR, and LR.  Call these lengths l1l2,  and l3.  Define the importance of vertex P as l1 + l2 - l3.  Use the following algorithm to find the n most important points. 

1.     while the number of points is greatern than n
2.     Compute the importance of each point.
3.     Remove the least significant one.
Modify Tracer.java to read in an an image file,  trace the outline of the image in the file to produce an outline,  and reduce the list to the n most significant points,  where n is an in put value.  Finally,  draw the initial and resulting shapes.  All of the points in the outline will fall on background pixels adjacent to the target image. 

In order to produce the initial outline from an image file you will need to: 

1.     Read the image file into a BufferedImage object.
2.     Find the boundary of the image by assuming that the background is white. 
	   1.     Starting with the first scan line,  scan from left-to-right to find the first 
	          non-background pixel if any. 
	   2.     Repeat until a non-background pixel is found. 
	          Enter the pixel immmediately to the left of this pixel into your list.  
	          The first pixel in your list is the initial previous pixel. 
	   3.     Scan along the next line until you find the first non-background pixel.  
	   		  If you fail to find a non-background pixel,  perform step 2 on the next 
	   		  can line.  If you do find a non-background pixel,  then enter 
	          the pixel immmediately to the left of this pixel into your list.  
	          The second pixel in your list is the initial current pixel. 
	   4.     If the pixel found in step 3 is not a neighbor of the pixel found in step 2, 
	          then find an adjacent boundary pixel on the same scan line as the pixel found in step 2.
	          Use the left-hand pixel of this pair of adjacent pixels as "current" and the right-hand 
	          pixel as "previous".
	   5.     Enter the "previous" pixel into the list followed by the "current" pixel. 
3.     Trace the boundary by following the "left-hand-rule" until you return to
       the start point. The left-hand-rule keeps the image to the "left" of your
       direction of travel. The boundary is where the white background ends. Thus, the
       boundary is white, but is adjacent to non-white. White is generally represented
       by maximum values in each of the RGB components of the image.
	   1.     Search the seven eligible pixels adjacent to the "current" pixel begining with 
	          the first pixel "after" the "previous" pixel and continuing in a counter-clockwise 
	          direction until you encounter the first non-background pixel.  Enter this pixel 
	          into the list. 
	   2.     The "current" pixel becomes the new "previous" pixel and the newly found pixel 
	          becomes the new "current" pixel. 
	   3.     Repeat until the initial pixel is found.   

For extra credit,  add a slider to your application,  showing each step of the simplification.  Becasue a slider can go back and forth, l you have to either store the results of each simplification step or regenerate the simplification from the original image.  Consult the Java API documentation on how to use a slider

Writing to a Buffered Image

Creating a WritableRaster object will allow you to write to a BufferedImage.  You can create a WritableRaster for your BufferedImage  by invoking the getRaster() method. 

Design

As usual, we will apply object-centered design to solve this problem.

Behavior. A sketch consists of a list of points and is drawn by drawing lines between pairs of adjacent points and connecting the points at the beginning and end of the list.  Your Point class should include accessor methods which return display coordinates and the "importance" of the point.  You will need to be careful to examine both neighbors of each point including the initial point put into the list and the last.  You may find it convenient to link the first node and the last node of the list together to produce a circular list. In this case you will need to use the size() method to determine when you have examined the last point when searching for a point to remove from the sketch. 

Objects. Using this behavioral description,  we can identify the following objects: 

 

Phrases you should now understand:

BufferedImageCollectionIteratorListListIteratorLinked ListDoublely Linked List

CollaborationYou will complete this project with your lab partner. 
ImplementationYou must implement your system as a Java application.  You may use Jgrasp.  Do not use netbeans or produce a Java applet. 
EnvironmentYour program must execute on the podium computer in our classroom.
Turn inYou must turn in both a report containing complete program sources and an executable electronic version of your program.

Last modified: 2008 FEB 25
bnostran@syr.edu