GLIMSView Source Code Documentation

extensions/ImageShapeFinder.cpp

Go to the documentation of this file.

#include "ImageShapeFinder.h"
#include <qmessagebox.h>
//#include <qprogressbar.h>
#include <qdialog.h>
#include <qlayout.h>

ImageShapeFinder::ImageShapeFinder(int x, int y, int w, int h, std::vector<double>* vals){

  lowx   = x ;
  lowy   = y ;
  width  = w ;
  height = h ;
  curDir = 0 ;
  pathsFilled = false ;

  if(vals->size() != (unsigned int)(width * height))
    QMessageBox::information( 0, "ImageShapeFinder Error", "Input vector size does not match expected." );

  layer = vals;

}

ImageShapeFinder::~ImageShapeFinder(){
  for (unsigned int i = 0 ; i < selections.size() ; i++) {
    if (selections[i] != NULL) {
      delete (selections[i]) ;
    }
  }
}

void ImageShapeFinder::setSelectedValues(std::vector<double> sel){
  inSelection = sel ;
  doSelecting();
}

std::vector<ImageSelectionCube*> ImageShapeFinder::getSelections(){
  return selections;
}


double ImageShapeFinder::getValueAtLocal(int x, int y, int z){
  int t = z ; t++ ; // just to turn off compiler warning
  return (*layer)[((y*(width))+(x))];
}


double ImageShapeFinder::getValueAtOverall(int x, int y, int z){
  int nx = x-lowx;
  int ny = y-lowy;

  return getValueAtLocal(nx, ny, z);

}


void ImageShapeFinder::doSelecting(){

  // this is really slow, so we'll provide a progress bar to entertain the user
  /*
  QWidget *progressDlg = new QWidget( NULL, NULL, true );
  QVBoxLayout *vbl = new QVBoxLayout( progressDlg, 10, 10 );
  vbl->setAutoAdd( true );
  new QLabel( "Creating polygons. Patience is a virtue.", progressDlg );
  QProgressBar *progressBar = new QProgressBar( progressDlg );
  float progress = 0.0 ;
  progressDlg->show();
  progressBar->setProgress(1) ; 
  */


  std::vector<bool> * flags = new std::vector<bool>(layer->size(), false) ;

  for(unsigned int i = 0; i < layer->size(); i++){//run through the layer
    if(isSelectable((*layer)[i])){

      // check the four pixels touching
      // if one is not selectable, change this to true in flags
      // to denote this pixel is on the edge. Same goes for 
      // a pixel on the edge of the image.
      std::vector<bool> legal = checkLegalAdjacents(i);

      //check above
      if(legal[1]){
        if(!isSelectable((*layer)[i-width])) {
          (*flags)[i] = true;
          continue;
        }
      }
      else {
        (*flags)[i] = true;
        continue;
      }

      //check right
      if(legal[3]){
        if(!isSelectable((*layer)[i+1])) {
          (*flags)[i] = true;
          continue;
        }
      } 
      else {
        (*flags)[i] = true;
        continue;
      }

      //check below
      if(legal[5]){
        if(!isSelectable((*layer)[i+width])){
          (*flags)[i] = true;
          continue;
        }
      }
      else {
        (*flags)[i] = true;
        continue;
      }

      //check left
      if(legal[7]){
        if(!isSelectable((*layer)[i-1])){
          (*flags)[i] = true;
          continue;
        }
      }
      else {
        (*flags)[i] = true;
        continue;
      }

    }
  }


  // debugging - write out raw image (edge selections)
  fstream flagsFile ;
  flagsFile.open ("shapeFinderEdgeFlags.raw", fstream::out | fstream::binary) ;
  if (flagsFile.is_open()) {
    for (int hei = 0 ; hei < height ; hei++) {
      for (int wid = 0 ; wid < width ; wid++) {
        flagsFile << (int) ((*flags)[width * hei + wid]) ;
      }
    }
    flagsFile.close() ;
  }
  // end debugging


  // debugging - write out raw image (adjacency count)
  flagsFile.open ("shapeFinderAdjacentCount.raw", fstream::out | fstream::binary) ;
  if (flagsFile.is_open()) {
    for (int hei = 0 ; hei < height ; hei++) {
      for (int wid = 0 ; wid < width ; wid++) {
        if ((*flags)[width * hei + wid]) {
          flagsFile << adjacentBorderPixs(width * hei + wid, *flags) ;
        }
        else {
          flagsFile << 0 ;
        }
      }
    }
    flagsFile.close() ;
  }
  // end debugging

  //first handle only lone points
  //these are just getting wiped, so we don't add them
  for (unsigned int j = 0; j < flags->size() ; j++){
    if((*flags)[j] == true)
      if(adjacentBorderPixs(j, (*flags)) == 0) {
        (*flags)[j] = false;
      }
  }


  /*
  //next handle lines, if a line splits we stop and will pick
  //it up with another line later
  for (unsigned int k = 0 ; k < flags->size() ; k++){
    if((*flags)[k] == true)
      if(adjacentBorderPixs(k, (*flags)) == 1) {
        handleLine(k, (*flags));
      }
  }
  */

  //finally, anything left should be a polygon...we hope
  //if not, it will handle lines too
  for (unsigned int l = 0 ; l < flags->size() ; l++){
    /*
    progress = ((float)l / (float)(flags->size())) * 100.0  ;
    progressBar->setProgress ((int)progress) ;
    */

    if((*flags)[l] == true) {
      paths = new std::vector<int>(layer->size(), false) ;
      handlePoly(l, (*flags));
      pathsFilled = false ;
      delete paths ;
    }
  }

  //delete progressDlg ;
  delete flags;
}


int ImageShapeFinder::nextBorderPoint(int i, std::vector<bool> &flags ){
  int num = adjacentBorderPixs(i, flags) ;

  // start new algorithm (Tweak 2)
  if (num > 1) {
    if (algorithm == 2) {
      return findLongestPath (i, flags) ;
    }
  }
  // end new algorithm (Tweak 2)


  std::vector<bool> legal = checkLegalAdjacents(i) ;
  int curDirTemp = curDir ;

  bool newAlgorithm ;
  if (algorithm == 0) {
    newAlgorithm = false ;
  }
  else {
    newAlgorithm = true ;
  }

  // start new algorithm (Tweak 1)
  // looks for next step in same direction as last step,
  // moving increasingly clockwise and counterclockwise
  // away from that direction searching for a valid path to follow
  for (int j = 1 ; newAlgorithm && j <= 4 ; j++) {
    switch (curDir) {
      case 0:
        if(legal[0]){
          if(flags[(i-1)-width]) return (i-1)-width;
        }
        break;
      case 1:
        if(legal[1]){
          if(flags[i-width]) return i-width;
        }
        break;
      case 2:
        if(legal[2]){
          if(flags[(i+1)-width]) return (i+1)-width;
        }
        break;
      case 3:
        if(legal[3]){
          if(flags[i+1]) return i+1;
        }
        break;
      case 4:
        if(legal[4]){
          if(flags[(i+1)+width]) return (i+1)+width;
        }
        break;
      case 5:
        if(legal[5]){
          if(flags[i+width]) return i+width;
        }
        break;
      case 6:
        if(legal[6]){
          if(flags[(i-1)+width]) return (i-1)+width;
        }
        break;
      case 7:
        if(legal[7]){
          if(flags[i-1]) return i-1;
        }
        break;
    }
  
    curDir = (curDirTemp + j) % 8 ;
    switch (curDir) {
      case 0:
        if(legal[0]){
          if(flags[(i-1)-width]) return (i-1)-width;
        }
        break;
      case 1:
        if(legal[1]){
          if(flags[i-width]) return i-width;
        }
        break;
      case 2:
        if(legal[2]){
          if(flags[(i+1)-width]) return (i+1)-width;
        }
        break;
      case 3:
        if(legal[3]){
          if(flags[i+1]) return i+1;
        }
        break;
      case 4:
        if(legal[4]){
          if(flags[(i+1)+width]) return (i+1)+width;
        }
        break;
      case 5:
        if(legal[5]){
          if(flags[i+width]) return i+width;
        }
        break;
      case 6:
        if(legal[6]){
          if(flags[(i-1)+width]) return (i-1)+width;
        }
        break;
      case 7:
        if(legal[7]){
          if(flags[i-1]) return i-1;
        }
        break;
    }
    curDir = (curDirTemp - j + 8) % 8 ;
  }
  // end new algorithm (Tweak 1)
  
  // start old algorithm (Basic Drawing Algorithm)
  // starts with vertical and horizontal "strong" paths,
  // then looks for paths to follow along the diagonals.
  if (!newAlgorithm) {
    if(legal[1]){
      if(flags[i-width]) return i-width;
    }
  
    if(legal[2]){
      if(flags[(i+1)-width]) return (i+1)-width;
    }
  
    if(legal[3]){
      if(flags[i+1]) return i+1;
    }
  
    if(legal[4]){
      if(flags[(i+1)+width]) return (i+1)+width;
    }
  
    if(legal[5]){
      if(flags[i+width]) return i+width;
    }
  
    if(legal[6]){
      if(flags[(i-1)+width]) return (i-1)+width;
    }
  
    if(legal[7]){
      if(flags[i-1]) return i-1;
    }
  
    if(legal[0]){
      if(flags[(i-1)-width]) return (i-1)-width;
    }
  }
  // end original algorithm
  
  

  curDir = curDirTemp ;
  return -1;
}


bool ImageShapeFinder::isSelectable(double val){
  for(unsigned int j = 0; j < inSelection.size(); j++){
    if (inSelection[j] == val) return true;
  }

  return false;
}


int ImageShapeFinder::adjacentBorderPixs(int i, std::vector<bool> &flags){
  std::vector<bool> legal = checkLegalAdjacents(i);

  int count = 0;

  if(legal[0]){
    if(flags[(i-1)-width]) count++;
  }

  if(legal[1]){
    if(flags[i-width]) count++;
  }

  if(legal[2]){
    if(flags[(i+1)-width]) count++;
  }

  if(legal[3]){
    if(flags[i+1]) count++;
  }

  if(legal[4]){
    if(flags[(i+1)+width]) count++;
  }

  if(legal[5]){
    if(flags[i+width]) count++;
  }

  if(legal[6]){
    if(flags[(i-1)+width]) count++;
  }

  if(legal[7]){
    if(flags[i-1]) count++;
  }

  return count;
}



int ImageShapeFinder::findLongestPath(int i, std::vector<bool> &flags) {
  std::vector<bool> legal = checkLegalAdjacents(i);
  int length = 0 ;
  int longest = -1 ;
  int longestCount = 0 ;

  if(legal[0]){
    length = 0 ;
    if(flags[(i-1)-width]) {
      length = findLongestPathLength((i-1)-width, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = (i-1)-width ;
      }
    }
  }

  if(legal[1]){
    length = 0 ;
    if(flags[i-width]) {
      length = findLongestPathLength(i-width, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = i-width ;
      }
    }
  }

  if(legal[2]){
    length = 0 ;
    if(flags[(i+1)-width]) {
      length = findLongestPathLength((i+1)-width, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = i-width ;
      }
    }
  }

  if(legal[3]){
    length = 0 ;
    if(flags[i+1])  {
      length = findLongestPathLength(i+1, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = i+1 ;
      }
    }
  }

  if(legal[4]){
    length = 0 ;
    if(flags[(i+1)+width]) {
      length = findLongestPathLength((i+1)+width, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = (i+1)+width ;
      }
    }
  }

  if(legal[5]){
    length = 0 ;
    if(flags[i+width])  {
      length = findLongestPathLength(i+width, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = i+width ;
      }
    }
  }

  if(legal[6]){
    length = 0 ;
    if(flags[(i-1)+width]) {
      length = findLongestPathLength((i-1)+width, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = (i-1)+width ;
      }
    }
  }

  if(legal[7]){
    length = 0 ;
    if(flags[i-1]) {
      length = findLongestPathLength(i-1, flags, i) ;
      if (length > longestCount) {
        longestCount = length ;
        longest = i-1 ;
      }
    }
  }

  return longest ;


}

int ImageShapeFinder::findLongestPathLength(int i, std::vector<bool> &flags, int source) {
  std::vector<bool> legal = checkLegalAdjacents(i);
  int num = adjacentBorderPixs(i, flags) ;
  int length = 0 ;
  int longestCount = 0 ;



    // temporarily disable this pixel so it's not revisited
    flags[i] = false ;

    if (num == 0) {
      // re-enable this pixel
      flags[i] = true ;
      return 1 ;
    }

    int index = 0 ;

    if(legal[0]){
      length = 0 ;
      index = (i - 1) - width ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }

    if(legal[1]){
      length = 0 ;
      index = i - width ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }

    if(legal[2]){
      length = 0 ;
      index = (i + 1) - width ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }

    if(legal[3]){
      length = 0 ;
      index = i + 1 ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }

    if(legal[4]){
      length = 0 ;
      index = (i + 1) + width ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }

    if(legal[5]){
      length = 0 ;
      index = i + width ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }


    if(legal[6]){
      length = 0 ;
      index = (i - 1) + width ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }


    if(legal[4]){
      length = 0 ;
      index = i - 1 ;
      
      if(flags[index] && index != source) {
        if (pathsFilled) {
          length = (*paths)[index] ;
        }
        else {
          length = findLongestPathLength(index, flags, source) ;
          (*paths)[index] = length ;
        }
        if (length > longestCount) {
         longestCount = length ;
        }
      }
    }


  pathsFilled = true ;

  // re-enable this pixel
  flags[i] = true ;
  
  return ++longestCount ;

}



  /* for reference
   *      0 1 2
   *      7 X 3
   *      6 5 4
   */

std::vector<bool> ImageShapeFinder::checkLegalAdjacents(int i){
  std::vector<bool> legals(8, true);

  //check the values above
  // if the value is in the top line of the image, set values above to false
  if (i < width) {
    legals[0] = false;
    legals[1] = false;
    legals[2] = false;
  }

  //check the values below
  // if the value is in the bottom line of the image, set values below to false
  if( i > (int)(layer->size() - width)){
    legals[4] = false;
    legals[5] = false;
    legals[6] = false;
  }

  //check the left edge
  // if the value is in the first sample of the image, set values left to false
  if( (i % width) == 0){
    legals[0] = false;
    legals[7] = false;
    legals[6] = false;
  }

  //check the right edge
  if( (i % width) == (width - 1) ){
  // if the value is in the last sample of the image, set values right to false
    legals[2] = false;
    legals[3] = false;
    legals[4] = false;
  }

  return legals;

}


void ImageShapeFinder::handlePoint(int i, std::vector<bool> &flags){
  //std::vector<ImageCube::Pixel> temp = *(new std::vector<ImageCube::Pixel>());
  std::vector<ImageCube::Pixel> temp;

  //create a pixel for this
  ImageCube::Pixel fpix;
  fpix.x = (i % width);
  fpix.y = (i / width);

  //push it into a vector
  temp.push_back(fpix);

  //remove it from flags
  flags[i] = false;

  //create a cube for this
  ImageSelectionCube* cube = (new ImageSelectionCube(fpix.x, fpix.y, 1, 1));
  //ImageSelectionCube cube(fpix.x, fpix.y, 1, 1);
  cube->setSelection(temp);


  selections.push_back(cube);

}


void ImageShapeFinder::handleLine(int i, std::vector<bool> &flags){

  if (adjacentBorderPixs(i, flags) == 0) return;

  std::vector<ImageCube::Pixel> temp;

  int j = i;

  int num = adjacentBorderPixs(j, flags) ;

  int hx, lx, hy, ly;

  hx = lx = (j % width);
  hy = ly = (j / width);
  
  //while each borderPixel has only one adjacent we have a line
  while((j!=-1) && num == 1) {

    //create a Pixel for this
    ImageCube::Pixel fpix;
    fpix.x = (j % width);
    fpix.y = (j / width);

    //push it
    temp.push_back(fpix);

    flags[j] = false;

    //use for determining the box that contains this line
    if(fpix.x > hx) {
      hx = fpix.x;
    }
    else if (fpix.x < lx) {
      lx = fpix.x;
    }

    if(fpix.y > hy) {
      hy = fpix.y;
    }
    else if (fpix.y < ly) {
      ly = fpix.y;
    }

    j = nextBorderPoint(j, flags);
    num = adjacentBorderPixs(j, flags) ;
  }

  //if we've reached a point where there's no adjacent border pix, it's the end
  if(num == 0){

    ImageCube::Pixel fpix;
    fpix.x = (j % width);
    fpix.y = (j / width);

    temp.push_back(fpix);

    flags[j] = false;

  }

  //create cube
  ImageSelectionCube* cube = (new ImageSelectionCube(lx-1, ly-1, (hx-lx)+1, (hy-ly)+1));
  cube->setSelection(temp);
  selections.push_back(cube);

}


void ImageShapeFinder::handlePoly(int i, std::vector<bool> &flags){
  std::vector<ImageCube::Pixel> temp;

  int j = i;
  int num = adjacentBorderPixs(j, flags) ;
  int hx, lx, hy, ly;


  // set l and h x/y to the current pixel location 
  // (convert from 1-dimensional array coordinates to
  // 2-dimensional image coordinates)
  hx = lx = (j % width);
  hy = ly = (j / width);

  //bool leavelast = true;

  // push the first pixel into the polygon structure
  ImageCube::Pixel fpix;
  fpix.x = (j % width);
  fpix.y = (j / width);

  temp.push_back(fpix);

  // get border pixel next to input
  j = nextBorderPoint(j, flags);
  num = adjacentBorderPixs(j, flags) ;

  //while each borderPixel has at least one adjacent, we're tracing a poly
  while((j!=-1) && num != 0 ){

    // set mpix to the current pixel location 
    // (convert from 1-dimensional array coordinates to
    // 2-dimensional image coordinates)
    ImageCube::Pixel mpix;
    mpix.x = (j % width);
    mpix.y = (j / width);

    temp.push_back(mpix);

    //**
    //if the line splits, or this is the beginning,
    //we may need this pixel later.  so we only kill it
    //if there's only one direction to go

    //flags[j] = false;

    if(num <= 1) {
      flags[j] = false;
    }

    /*
    else if(leavelast && num == 2){
      flags[j] = false;
      leavelast = false;
    }

    else if(num > 1) {
      leavelast = true;
      flags[j] = true;
    }
    */

    flags[j] = false;

    //use for determining bounding box
    // (mpix is current pixel, l/h x/y were set to input pixel)
    if(mpix.x > hx) {
      hx = mpix.x;
    }
    else if (mpix.x < lx) {
      lx = mpix.x;
    }

    if(mpix.y > hy) {
      hy = mpix.y;
    }
    else if (mpix.y < ly) {
      ly = mpix.y;
    }

    // get the border pixel next to the current one
    j = nextBorderPoint(j, flags);
    num = adjacentBorderPixs(j, flags) ;

    // if this is the end of the line and we're not close to the starting pixel, walk 
    // back to where we branched off and chop this section off as its own line
    if (num == 0 && (abs(fpix.x - (j % width)) <= 2 && abs(fpix.y - (j / width)) <= 2) ) {

      flags[j] = false ;
      std::vector<ImageCube::Pixel> templine ;

      // prepare to walk backwards in case we've reached the end
      // and check for other routes to trace
      int t = j ;
      int tNum = adjacentBorderPixs(t, flags) ;
      vector<ImageCube::Pixel>::iterator stepback = temp.end () - 1 ;
      vector<ImageCube::Pixel>::iterator stepbackPrev = stepback ;

      // walk backwards until a pixel with adj border pixels is found
      // and start processing from there to pick up the funny corners
      // and dangling hairs
      while (tNum == 0 && stepback >= temp.begin()) {
        t = ( (*stepback).y * width + (*stepback).x ) ;
        tNum = adjacentBorderPixs(t, flags) ;
        
        templine.push_back(*stepback) ;

        stepback = temp.end() - 1 ;
        if (stepback == stepbackPrev) {
          break ;
        }
        stepbackPrev = stepback ;
        //temp.erase(stepbackPrev, stepbackPrev) ;
      }

      // push line chopped off our polygon into selections
      if (templine.size() >= 2) {
        ImageSelectionCube* cube = (new ImageSelectionCube(lx-1, ly-1, (hx-lx)+1, (hy-ly)+1));
        cube->setSelection(templine);
        selections.push_back(cube);
      }

      // reset values to pixel found during step-back search
      if (tNum != 0) {
        j = t ;
        num = adjacentBorderPixs(j, flags) ;
      }
    }

  } // end while

  //if we've reached a point where there's no adjacent border pix, it's the end
  // todo dls didn't we push this pixel already? should this be the starting pixel?

  //if(num == 0 && j >= 0) {
    ImageCube::Pixel lpix;
    lpix.x = (j % width) ;
    lpix.y = (j / width) ;

    temp.push_back(lpix) ;
    flags[j] = false ;
  //}

    // if the last pixel is close to the first pixel, close the polygon
    // by pushing the first pixel into the selection
    if (abs(lpix.x - fpix.x) <= 10 && abs(lpix.y - fpix.y) <= 10 ) {
      temp.push_back(fpix) ;
    }



  //temp.push_back(fpix);


  ImageSelectionCube* cube = (new ImageSelectionCube(lx-1, ly-1, (hx-lx)+1, (hy-ly)+1));
  cube->setSelection(temp);
  selections.push_back(cube);

}

---

Home | Search | Disclaimers & Privacy | Contact Us GLIMSView Maintainer: dsoltesz@usgs.gov