SHAPEFS 1.2.0.0-20051020

A Plug-In Bringing Horn Shape From Shading to GIMP!

Table of Contents:

  1. Introduction.
  2. User Interface.
  3. Examples on Feature in THEMIS V01354003.
  4. Example on Feature in MGS-MOC Image E03-02550.
  5. Notes on Compilation and Use.
  6. Known Bugs and Other Issues.
  7. Download GNU-GPL Licensed Source and Executable.
  8. References.

1) Introduction:

Upgraded for GIMP version 2.2.8 and GTK+ version 2.6.9.

Shape from shading algorithms have been around for a while.  Dr. Mark J. Carlotto describes a simplified version in his New Frontiers of Science page [Shape From Shading].  In that page, Dr. Carlotto describes the Berthold Klaus Paul Horn algorithm for generating shape from shading, first described by Horn in 1989.  Numerous references are available on the internet:

  1. Implementation of a Single Photo Shape From Shading Method for The Automatic DTM Generation. (Hashemi, et. al., 2000. PDF).
     
  2. AIM-1105: Height and Gradient from Shading (Horn, 1989. PDF).
     
  3. AITR-232: Shape From Shading: A Method for Obtaining the Shape of a Smooth Opaque Object From One View. (Horn, 1970. PDF).
     
  4. AI Publications: numerous memos by Dr. Horn.

This minor release corrects many of the bugs that where encountered on previous releases, and gives new functionality to the plug-in.  Among the most important bugs corrected was edge curling that was related to the rotation of the source image to correspond to the Sun Azimuth ancillary parameter.  This bug was corrected by implementing trigonometric rotation rather than using gimp_image_rotate.  Changing the rotation method from an actual image rotation to a mathematical rotation corrected the second major bug, which was in generating the height map accurately.  Other features where added such as use of the pixel aspect ratio, an alternate formula for computing the height map, and a user welcome status that shows the source file being worked on and the source size in pixels.  Please see the revision history file, shapefs_rev_hist.txt, in the release package.

This author hopes that you find this plug-in instructive for your own plug-in creations, informative with respect to Mars or other surfaces, and exciting to use.

2) User Interface:

The user interface is illustrated in Figure 1, below:

User interface of ShapeFS GIMP plug-in. Figure 1.

Description of the user interface form controls are as follows:

  1. Algorithm Selection: - Radio buttons which select the processing algorithm.  Currently only the simplified Horn algorithm is implemented.  Ghasemlou and Lee algorithms are not implemented in version 1.2.0.0 and will generate a warning box if checked.  This is the next major revision upgrade task that this author will attempt to endeavor.
     
  2. Application Control: - Pushbutton controls that determine how different application features operate.
     
    1. Delete Images - If checked, deletes the last generated image, otherwise it is left.  This feature is used to enable the user to try different 3D rendering parameter combinations quickly without having to delete old unwanted images manually.
       
    2. Matrix Warnings - If checked, enables a message box that warns whenever a transformation matrix is singular (determinant = 0) or if it is ill conditioned (determinant << 1).  Both conditions will result in erroneous results, which may be remedied by judicious change to Viewer X, Y, and Z-axis angles.  This button may be disabled without affecting program operation.
       
    3. Memory Warnings - If checked, enables a message box that warns of memory allocation errors and out of bounds conditions in the vector sort section of the algorithm.  Allocation errors are fatal to rendering.  Such an error will cause the rendering section to abort, which returns to the user dialog without rendering an image.  These normally are the result of an excessively large image.  Out of bounds conditions result from mapping vectors into illegal addresses, such as negative addresses and addresses beyond legally accessible memory.  This button may be disabled without affecting program operation.
       
    4. Draw Axes - If checked, draws an X and Y axis along with end labels on the rendered image.
       
    5. Generate Movie - If checked, generates a layer movie using the parameters specified in Movie Control.  GIMP can save this as a PSD file which can then be imported to a program such as Adobe Imageready 7.0 for conversion into a smaller GIF format. Users in some countries outside of the United States may be able to directly generate GIMP GIF based movies due to the inapplicability of the Unisys patent to GIF image generation. See the movie notes sub-section below for important information on generating movies.
       
    6. NEW FEATURE:Save Height Map - If checked, saves a height map in the format specified by the state of the Excel Map Type check box.  This can result in a fairly large text file.  The height map path specification is set in the box adjacent to this check box.
       
    7. NEW FEATURE:Excel Map Type - If checked, saves the file in a format suitable for importation into Microsoft® Excel 2003 for creation of 3D surface plots.  However, be aware that Microsoft® Excel 2003 can only plot surfaces of 255 square elements (R1C1:R254C254 in R1C1 reference style).  Therefore large images, such as a full size version of E0300824 (Mars 'Face' full resolution image at 1.86 m/pixel, crop, 1548 ∙1584 pixels) will significantly exceed this capability.  If unchecked, ShapeFS outputs a text file with entries in x, y, z format separated by new line characters.  This type of output is suitable for applications that do not have the input data limitations of Microsoft® Excel 2003.
       
  3. MOC/THEMIS Image Ancillary Parameters: - These directly correspond to the ancillary parameters that are given on Mars Global Surveyor (MGS) / Mars Orbiter Camera (MOC) and Mars Odyssey Thermal Imaging System (THEMIS) images.
     
  4. 3D Rendering Parameters: - These user inputs determine how the image generates.  As follows:
     
    1. Image Scale - Performs the {Image » Scale Image} function that is part of GIMP.  Scales the image depending on the scaling algorithm selected in the GIMP Preferences.  Unless your machine is slow, the author recommends Cubic interpolation be used as the default interpolation method.
       
    2. Viewer X-Axis Angle - This user control is a counterclockwise rotation looking into the x-axis, which defines the counterclockwise rotation of the (x, y) plane on x-axis.  At 90°, the viewer is at nadir, and at -90° is directly below the 3D image.  0° is on edge with the 3D image. Represents tilt of the viewer with respect to the top and bottom of the image.  See the Eric Weisstein's World of Mathematics (MathWorld) page on Rotation Matrices at (4) to see a graphic representation of what each rotation means.
       
    3. Viewer Y-Axis Angle - This user control is a counterclockwise rotation looking into the y-axis, which defines the counterclockwise rotation of the (x, y) plane on y-axis.  0° is flat on and 90° is edge on to the image.  Again, see Rotation Matrices at (4) to for a graphic representation of what each rotation means.
       
    4. Viewer Z-Axis Angle - This user control is a clockwise rotation looking into the z-axis which defines the clockwise rotation of the (x, y) plane on z-axis.  Using the same value as used in Sun Azimuth results in an image that is oriented in the same direction as the source image.
       
    5. Focal Distance - This is the arbitrary distance away from the image plane, and may be left at its default value.  Used to generate the coefficients in the perspective transformation matrix.
       
    6. Max. Output Size - This is the extent of both height and width of the rendered 3D image in pixels.  May be used in combination with Image Scale to reduce spotting caused by sorting round off.  Please realize that this is not the actual size of the output image but rather the maximum allowed size of the output image.  The output image may render significantly below this value in a way that cannot be predetermined.
       
    7. NEW FEATURE: Auto Correct Y-Axis Tilt - If checked, will automatically try to correct for the y-axis tilt bias that is a processing artifact of this type of shape from shading algorithm (See: Synthetic Image Example, last paragraph[1]).  The algorithm uses the endpoints of the rotated x-axis to compute the tilt angle via trigonometry (θ = tan-1Δy/Δx).  This angle is automatically placed in the Viewer Y-Axis Angle entry box.  If Save Height Map is selected, the computed height map is copied, and prior to writing to a file, is corrected for this tilt.  This is accomplished by coordinate rotation using the negative of θ on the height map values, as specified in Standard Mathematical Tables and Formulae[6], page 305, formula 4.2.2.  As image rows are operated on individually (x-coordinate, height), a column vector (x, y) and a 2x2 square matrix are sufficient as opposed the more general solution used in the actual image generation.
       
    8. NEW FEATURE:Alternate Formula - The alternate formula check box was added due to a certain ambiguity in the simplified Horn algorithm as described by Carlotto[1].  In the formula described in that reference, the current pixel height is defined as 'z(x,y) = z(x-1,y) + [i(x,y) - a cos(s)] / a sin(s)'.  The ambiguity results in the last term '/a sin(s)'.  This can both be interpreted as 'sin(s)[i(x,y) - a cos(s)] / a' or as '[i(x,y) - a cos(s)]/(a sin(s))'.  Due to this, this author has included both options.  If checked, the formula divisor is the former, else it is the latter.  Both render elevation maps with a slight difference in elevation.
       
  5. Movie Control: - These user inputs determine how the layer movie will be generated.  Only applicable if Generate Movie is checked.

    1. Z-Axis, Y-Axis, X-Axis - This radio button set controls which axis is varied.  Only one axis may be varied at a time.  Remember to set the appropriate angles for the other constant axes.  The Y-Axis and X-Axis putatively rotate in a counterclockwise fashion, while the Z-Axis rotates in a clockwise fashion.  However there are exceptions to this, see Known Bugs and Other Issues, (d).

    2. Starting Movie Angle - The movie will start with a layer having this angle value.

    3. Ending Movie Angle - The movie will end with a layer having this angle value.

    4. Movie Frame Count - The movie will have this many frames in it.  The angle step size is (Ending Movie Angle - Starting Movie Angle) / Movie Frame Count.  All layers of the GIMP movie are labeled with Z-Axis, Y-Axis, X-Axis and frame count for clarity.

  6. Status: - Application status display area, showing rudimentary blurbs that indicate the status or operating location of the plug-in.
     
    1. NEW FEATURE: Progress Bar - This feature was added to allow the user to see the completion status of the plug-in with respect to the given rendering configuration.  The bar displays both as a gauge and as a percentage displayed in the center of the bar.

    2. NEW FEATURE: Activity Bar - This feature (not displayed in Figure 1) allows the user to visually verify that the plug-in is active.  Due to the computationally intensive nature of this plug-in, previous versions would appear to be stalled during certain portions of the computation cycle.  This secondary guage is located under the Progress Bar, however it only appears when the START button is clicked.  It cycles back and forth on a 100 msec pulse cycle, and stops when the current round of processing is complete and the plug-in is waiting for further user input.
       
    3. NEW FEATURE: Completed Algorithm Module Status - This feature was added to allow both the user and author to determine at which processing step the plug-in is in.  The default pre-START text is displayed below the Movie Control frame in Figure 1.

3) Examples on Feature in THEMIS V01354003 (to be updated to ShapeFS 1.2.0.0 at a later date):

shapefs.exe example image 1 (Figure 2) showing feature in THEMIS data release V01354002 at (483, 2964) rotated (60, 0, 80). Figure 2.

Figure 2 is an example from the salient feature of THEMIS V01354003 as analyzed by this author in his page: - Petaled 'Crater' - in Mars Terra Sirenum, Figure 3, with the text and graphics layers removed (background only).  The conjecture on that page is that the feature shown here is a raised feature.  From the three examples given (Figures 2, 3, and 4), and assuming that the photoclinometry is correct, it is observable that this feature does posses significant height as compared to the two adjacent craters.

shapefs.exe example image 2 (Figure 3) showing feature in THEMIS data release V01354002 at (483, 2964), rotated (20, 20, 70). Figure 3.

In Figure 3, significant depth is rendered, showing appreciable 3D features.  Users must be willing to spend a little time playing with angle combinations to get the best rendering possible from the shapefs plug-in filter.

shapefs.exe example image 3 (Figure 4) showing feature in THEMIS data release V01354002 at (483, 2964), rotated (-65, 50, -151.02). Figure 4.

Finally, Figure 4 shows the target image viewed from below.  Notice the location of the shadowing.  Users must be aware of this kind of detail, as it is possible to render inaccurate images by using angle combinations that are inappropriate or that cancel each other out.  Though the image should be oriented equally with respect to the source image, that being 208.977° - 360° = -151.02°, however the X-Axis rotation of -65° flips the image over!

4) Example on Feature in MGS-MOC Image E03-02550:

shapefs.exe example 4 source image (Figure 5) showing unprocessed feature in MGS/MOC E0202550 at (196, 4885). Figure 5.

Figure 5 is the source image for Figure 6 and is a feature found in E03-02550 at (196, 4855) in the IMG PDS image file.

shapefs.exe example 4 (Figure 6) image showing feature in MGS/MOC E0202550 at (196, 4885), rotated (30, 30, 30), scaled 2. Figure 6.

Figure 6 shows an example of the scaling feature and axis designators.  Smoothing of the image is apparent, similar to blurring functions.  Judicious use of image size and scaling increase the quality of your rendered image!  Finally, a GIF movie of Figure 5 is available by clicking on Figure 7 below, which is the first frame of the GIF Movie (541KB).  This movie rotates the image on the X axis from 10° through 180° and back, allowing a showing of height and hidden element removal.  The angles on the Y and Z axes are set to 0°.

Frame 1 of E0302550 GIF movie, linking to movie itself. Figure 7 (541KB).  

5) Notes on Compilation and Use:

  1. Development and Compilation notes:
    1. Development and compilation was initially performed using Dev-C++ Version 4.9.9.2 WX Beta 6.8, a port of Dev-C++ Version 4.9.9.2 to wxWidgets. Dev-C++ is a freeware product of Bloodshed Software.  Version 1.2.0.0 was completed using Dev-C++ Version 4.9.9.2 only, due to not needing the tools in the wxWidgets port of Dev-C++.
       
    2. The development platform is a Dell OptiPlex GX280, running Windows XP Professional Version 5.1.2600 Service Pack 2, having dual 3.0GHz P-IVs, with 1024MB of memory.
       
    3. There are significantly more developer packages to download and install with this version of GIMP.  The specific file locations are specified in shapefs.h.  However, for convenience the links to the development files are indicated following, taken from Tor Lillqvist's (tml) GTK+ (not GIMP) for Windows download page.  If you get declaration or linking errors, look to see if you've placed the corresponding header file in the correct place. 

      1. atk-dev-1.9.0.zip           ATK development package, i.e. headers, import libraries and documentation. (FTP)
      2. glib-dev-2.6.6.zip          GLIB development package. (FTP)
      3. gimp-dev-2.2.7.zip        GIMP developer package. (HTML download)
      4. gtk+-dev-2.6.9.zip        GIMP Tool Kit development package. (FTP)
      5. pango-dev-1.8.2.zip      PANGO development package. (FTP)
         
    4. The build is for use with Gimp 2.2.8 as provided by Source Forge on their Gimp for Windows Installers Page.  You must download and install first Gtk+ then GIMP to use GIMP and this plug-in.
       
    5. The plug-in language is C++, and the minimum required source files to compile it are shapefs.h, shapefs_ComAlgo.cpp, shapefs_Main.cpp, shapefs_Math.cpp, shapefs_Message.cpp, and shapefs_Horn.cpp.  You will also need the header files specified in shapefs.h and the corresponding libraries.  Modifications may be necessary to the header and include file declarations in shapefs.h depending on the configuration of the target system. The header file shapefs.h also contains further compile, debugging, and information notes at its beginning.   
       
    6. This plug-in has been memory leak checked using LeakTracer.  A Windows XP compatible modification of the original source file is included titled SFS_LeakTracer.cpp is included for those that wish to try memory leak checking.  Valgrind was not used as, to this author's knowledge, it is not available for the Windows platform.  To use LeakTracer, you must have Perl installed and in the proper path.  Please read the README.html file in the LeakTracer install package, LeakTracer.tar.gz, for instructions on how to use LeakTracer.

    7. Make verification was performed using the MSYS make utility in a Bourne shell rxvt window.  The command used is "make -f makefile.win all", executed from the source file directory.  As a side note, MSYS and MinGW are both indispensable tool for the software developer who is on a Microsoft Windows platform as opposed to Linux/Unix.  It ports the useful tools of Linux/Unix such as grep, find, tar, awk, etc., to the Microsoft Windows platform, creating a very effective development environment.

    8. The author recommends 512 MB minimum in the target system, and the fastest possible processor.  For example, on a 1024 x 1026 source, the application pulls, at minimum, 288,512 MB during the peak computation section of code, and takes approximately 2.676 seconds of actual CPU time (as reported by Windows Task Manager, 2.5GHz P-IV) to render each image frame, with a buffered elevation map on a 37 frame movie.
       
  2. This plug-in operates stably for the above configuration.  Theoretically, it should port over to Unix/Linux without problems.  However, the author cannot guarantee that it will do so without major effort on your part!
     
  3. It is always beneficial to verify the image by setting Viewer X-Axis Angle to 90° and the Viewer Y and Z-Axis Angles to 0° and insuring the correctness of the image by looking at it from above.  This view should match the current view of the source image.

  4. Movie loops of -180° through 180° result in a movie that rotates the image in a circular fashion.  Movie loops of a lesser angular range can be made to look better by copying all layers and inserting them in reverse on the top of the layer stack.  This is easily done by using the layer duplicate button on each layer, then starting with the top or highest numbered layer, select the layer, then use Shift-Ctrl-F to move each selected layer to the top of the layer stack, in decreasing numeric order. Such user editing gives a foward-reverse action to the movie which is very easy on the eye.  If text labeling is required, it must be added manually by the user to each frame of the movie.  The author did not wish to open this can of worms, though at some point the Status: frame output may be moved to the status bar, and the Status: frame changed to a text layer user entry form.

  5. Another movie technique is to flatten the image on the y-axis.  This is now automatic using the Auto-Correct Y-Axis Tilt check box. Another option to set all viewer angles to 0°, then render that frame  Generate Movie  unchecked.  Using the GIMP Measure Tool, measure from the left lower (lower or upper) corner to the right (lower or upper) corner and read the angle from the status bar.  Insert that measured angle value into the Viewer Y-Axis Angle entry box, and render again.  If you like the results, then try it with Generate Movie checked.  This gives a movie that is oriented horizontally with respect to the viewer.
     
  6. To load Planetary Data System files into GIMP, be sure to download and/or create the GIMP PDS Loader, by Holger Isenberg.  It's also available from directly from Mr. Isenberg's page, PDS Loader.  It will operate of the following PDS data sets (not inclusive): Mars Express HRSC, 2001 Mars Odyssey THEMIS EDR/RDR-QUB (RGB-loader), Mars Global Surveyor MOC, Mars Pathfinder, and Viking Lander.

6) Known Bugs and Other Issues:

  1. Incorrect mapping very rarely occurs in the vector sort section of the algorithm, which causes invalid mapping addresses to be attempted.  Though an extensive rewrite of the sort algorithm maximum and minimums test in this release works significantly better, there are still attempted excursions outside of the address limits on occasion.  We will keep plugging at this issue until it's totally figured out!

  2. The perspective matrix does work and has been verified, however it does not perform as expected.  The final perspective matrix selected was that performs reasonably.  Therefore, the focal distance parameter is not very functional.  Implementing full perspective capability appears to be beyond the scope of this plug-in in it's current incarnation.  Documentation is provided in both shapefs_Horn.cpp and shapefs_Math.cpp source files for any with an interest in the source of the mathematics.
     
  3. Round off errors occur in vertex sorting with certain 3D rendering parameter combinations and resolutions.  This manifests itself as black dots or stripes, sometimes what appears to be loss of raster lines, etc.  Judicious use of Image Scale and Max. Output Size can correct this problem, sometimes.  This is not a bug but rather an effect of image digitization.  The easiest solution to resolve this is to use the GIMP Image → Scale Image command on the source image with Quality → Interpolation →  Cubic (Best).  If you have a 600x600 source and wish an output display of that size, scale the image to at least 200% to 300% of the original size, selecting percent as the unit of change and keeping the aspect ratio locked (the chain icon should not be broken).
     
  4. Not all possible angle combinations work correctly.  Certain angle combinations may result in a singular rotation matrix that will produce erroneous results.  Further, due to the cyclical nature of trigonometric functions, certain renderings are ambiguous or result in Escher-esque renderings that are non sequitur to the source image.  Though the hidden element removal section of the algorithm was appreciably worked on, it is not totally failsafe.  Though not necessarily a bug, this result is obviously unwanted.  Further, certain angle combinations will lead to the error described above in a.  Pay particular attention for this during movie generation and  use common visual sense.  An example of this is that though a Z-axis rotation mathematically should appear to go clockwise looking into the axis, sometimes the reverse occurs.  This should cue you on the appearance of this ambiguity.  A perfect example is the source image used in Figure 1, M0803500, scaled to 200%.  Using M0803500, compare a 37 frame movie on the Z-Axis at a 0° Viewer X-Axis Angle, with a 37 frame movie on the X-Axis, which does not show the same ambiguity.
     
  5. ShapeFS 1.2.0.0 has reduced memory consumption by approximately 30% from version 1.1.0.0 and previous versions.  However, very large images will cause the plug-in to crash due to running out of memory.  You can tell this happened when you get the following report or a similar one:
    ShapeFS out of memory error example. Figure 8.
    This is not a bug, rather a limitation in resources.  As an example, the following task manager report was issued upon completion of a 37 frame movie rendering of a 2048 x 1680 pixel image at 500 pixel output resolution (capture from ShapeFS 1.1.0.0 run): 
    ShapeFS Windows Task Manager memory report. Figure 9.
    The condition that resulted in the error of Figure 8 attempt to generate the same 37 frame movie of the same 2048 x 1680 pixel image, also at 500 pixel output resolution, with many other applications active.    The actualization of this error is directly related to original image size and what other applications are active at the time you click the Start button.  Computer slowdown will occur during execution and and while paging to and from memory, as attempting to process such a large image will result in everything that is not active being paged out to hard disk.  If this occurs, try scaling your source image down to manageable proportions using the GIMP Image → Scale Image command on the source image with Quality → Interpolation →  Cubic (Best).  However, be aware of the trade off doing this with respect to round off error.
     
  6. Clouds, wind stripes, dust devil marks, or similar artifacts on the source image will give erroneous results, such as slopes where obviously there are no slopes.  This is to be expected from the algorithm in question (Horn) and the lack of ground truthing. 


7) Download GNU-GPL Licensed Source and Executable:

Requires WinZip 8.0, minimum, or a compatible un-zipper such as 7Zip.  This plug-in has been generated from the Windows XP Professional build, with a dual hard drive configuration, with GIMP installed in the directory d:\GIMP-2.0\ and Dev-C++ installed in the directory d:\Dev-Cpp\.   If you're running another configuration or OS, don't extract to the original folders!  Obsolete versions are no longer on this site due to space constraints.

Download shapefs-1.2.0.0-20051020.zip now (324 KB). Windows GIMP 2.2.8 port, including executable. (shapefs.exe WinZip 8.0 CRC: 0eea5ed4).
Download shapefs-1.2.0.0-20051020.tar.gz now (199 KB).  No executable in this file as it's meant for Linux/Unix users. (gzip CRC: 2774aa48).

Included in this distribution is an image of the Mars 'King Face' for your processing enjoyment.  This file, titled M0203051.xcf, is the Gimp XCF version of the file available at Analysis of M0203051, without the text layer, with the raw MGS/MOC PDS IMG/IMQ image available at M0203051.

ShapeFS took approximately 600 hours to develop.  Hopefully, you found or will find ShapeFS useful in examining your MGS-MOC images in 3D.  If you did, then a small voluntary donation would be very appreciated to help defray the costs of hosting a website at Yahoo! Geocities and for the hours expended developing ShapeFS.  Regardless, this plug-in will be maintained as long as possible to keep up with GIMP updates.
 

8) References:

  1. Shape From Shading, (Carlotto, 1996, HTML)
     
  2. Implementation of a Single Photo Shape From Shading Method for The Automatic DTM Generation. (Hashemi, et. al., 2000. PDF).
     
  3. AIM-1105: Height and Gradient from Shading (Horn, 1989. PDF).
     
  4. AITR-232: Shape From Shading: A Method for Obtaining the Shape of a Smooth Opaque Object From One View. (Horn, 1970. PDF).
     
  5. AI Publications: numerous memos by Dr. Horn.
     
  6. C.R.C. Standard Mathematical Tables and Formulae, Daniel Zwillinger, 2003, Chapman & Hall/CRC
     

Back To Home Page
© 2003-2005

Alfred P. Reaud
Independent Investigator
Created: Monday, May 5, 2003
Current: Friday, October 21, 2005
Valid HTML 4.01!
Official PayPal Seal