unit filterSPV;
(* ***** BEGIN LICENSE BLOCK *****
 * Copyright (C) 2004 Durand Emmanuel
 * Copyright (C) 2004 Burgel Eric
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Contact :
 *   filters@edurand.com
 *   filters@burgel.com
 * Site :
 *   http://filters.sourceforge.net/
 *
 * ***** END LICENSE BLOCK ***** *)

{
 implemented by "Emmanuel Durand"
 edurand (filters@edurand.com)
}

{
  SPV : Sparse Pixel Vectorization
  original author = "Dov Dori and Wenyin Liu"
  http://dori2.technion.ac.il/opm/documents/articles/article180.pdf
}

interface
uses
  filter, fparameters, image, SysUtils;

type

  TMonitoring = (None, Tracking, PixelChain, PolygonalApproximation, CriticalPoints);

  THorizontalVertical = (Horizontal, Vertical);

  TRunInfo = record
    segment : TSegment;
    length : Single;
    middleRunPoint : TFPoint;
  end;

  TMedialAxisInfo = record
    point : TFPoint;
    lengthDirection : THorizontalVertical;
  end;

  TTrackingCycleInfo = record
    initalMedialAxisInfo : TMedialAxisInfo;
    trakingStepStopPoint : TFPoint;
    trackingStepLength : Integer;
    widthRunMedialAxisInfo : TRunInfo;
    newMedialAxisInfo : TMedialAxisInfo;
    continuationConditionsSatisfied : Integer;
    widthAverage : Single;
  end;

  TTrackingCycleInfoList = array of TTrackingCycleInfo;

  TFilterSPV = class(TFilter)
  public
    constructor Create; override;
    destructor Destroy; override;
    procedure Run(); override;
    procedure setParameterImage( const aName: String; const aImage: PBitmap32); override ;
  private
    parameterBackgroundThreshold : TParameterInteger;
    parameterScanLineIncrement : TParameterInteger;
    parameterMonitoring : TParameterString;
    parameterShowVectorWidth : TParameterString;
    parameterShowConnectedVector : TParameterString;
    parameterMaximalTrackingStep : TParameterInteger;
    parameterMaximalTrackingCycles : TParameterInteger;
    parameterPolygonalApproximationEpsilone : TParameterInteger;
    parameterImageIn : TParameterImage;
    outputParameterImageOuts : TParameterImages;
    _imageOuts : ArrayOfPBitmap32;
    _backgroundThreshold : Word;
    _w,_h :Integer;
    _Src : PColor32Array;
    _imageIn : PBitmap32;
    _trackMonitoringOutImage, _soleOccupencyImage, _vectorOutImage : PBitmap32;
    _imageSrcRowmax, _imageSrcColmax : Integer;
    _maximalTrackingStep, _currentTrackingRunLengthMax : Integer;
    _currentTrackingCycleInfoList : TTrackingCycleInfoList;
    _segmentList : TSegmentList;
    _monitoring : TMonitoring;
    _showVectorWidth, _showConnectedVector : boolean;
    _epsylone : Single;
    procedure deleteImages;
    procedure _run();
    function findStartMedialAxisPoint(currentPixel : TFPoint) : TMedialAxisInfo;
    function horizontalDirectedRun(currentPixel : TFPoint; runSign : Integer) : TFPoint;
    function horizontalRun(currentPixel : TFPoint) : TRunInfo;
    function verticalDirectedRun(currentPixel : TFPoint; runSign : Integer) : TFPoint;
    function verticalRun(currentPixel : TFPoint) : TRunInfo;
    procedure startTracking(startMedialAxisInfo : TMedialAxisInfo);
    function directedTracking(startMedialAxisInfo : TMedialAxisInfo; runSign : Integer) : TSegmentList;
    procedure trackingCycles(initialMedialAxisInfo : TMedialAxisInfo; runSign : Integer);
    function trackingCycle(lastTrackingCycleInfo : TTrackingCycleInfo; runSign : Integer) : TTrackingCycleInfo;
    function trackingStep(currentMedialAxisInfo : TMedialAxisInfo; runSign : Integer) : TFPoint;
    function startJunctionRecoveryProcess(lastTrackingCycleInfo : TTrackingCycleInfo; runSign : Integer) : TTrackingCycleInfo;
    function polygonalization(segmentList : TSegmentList) : TSegmentList;
    function isInSoleOccupency(point:TFPoint) : boolean;
  end;

implementation
uses
  imageIO, Classes, polygonalyzation;

constructor TFilterSPV.Create;
begin
  inherited;
  parameterImageIn:=addParameterImage('inImage','image to process');
  outputParameterImageOuts:=addOutputParameterImages('outImages','0:monitor/1:vector');
  parameterMonitoring:=addParameterString('monitoring','NONE/TRACKING/PIXEL CHAIN/POLYGONAL APPROXIMATION/CRITICAL POINTS','TRACKING');
  parameterShowVectorWidth:=addParameterString('showVectorWidth','TRUE/FALSE','FALSE');
  parameterShowConnectedVector:=addParameterString('showConnectedVector','TRUE/FALSE','TRUE');
  parameterBackgroundThreshold:=addParameterInteger('backgroundThreshold','',1,255,200);
  parameterScanLineIncrement:=addParameterInteger('scanLineIncrement','',1,20,5);
  parameterMaximalTrackingStep:=addParameterInteger('maximalTrackingStep','',2,100,8);
  parameterMaximalTrackingCycles:=addParameterInteger('maximalTrackingCycles','',1,9999,9999);
  parameterPolygonalApproximationEpsilone:=addParameterInteger('polygonalApproximationEpsilone','',1,40,10);
  SetLength(_imageOuts,2);
end;

destructor TFilterSPV.Destroy;
begin
  deleteImages;
  SetLength(_segmentList,0);
end;

procedure TFilterSPV.deleteImages;
var
  i : Integer;
begin
  if _imageOuts<>nil then begin
    for i:=Low(_imageOuts) to High(_imageOuts) do begin
      image.freeImage(_imageOuts[i]);
    end;
  end;
  image.freeImage(_soleOccupencyImage);
end;

procedure TFilterSPV.Run();
begin
 if (parameterImageIn.Image<>nil) then begin
  _backgroundThreshold:=parameterBackgroundThreshold.Value;
  _maximalTrackingStep:=parameterMaximalTrackingStep.Value;
  _currentTrackingRunLengthMax:=_maximalTrackingStep;
  _h:=parameterImageIn.Image.Height;
  _w:=parameterImageIn.Image.Width;
  _Src:=parameterImageIn.Image.Bits;
  _imageIn:=parameterImageIn.Image;
  if _imageOuts[0]=nil then _imageOuts[0]:=createImageLike(parameterImageIn.Image);
  if _imageOuts[1]=nil then _imageOuts[1]:=createImageLike(parameterImageIn.Image);
  if _soleOccupencyImage=nil then _soleOccupencyImage:=createImageLike(parameterImageIn.Image);
  setOutputParameterImages('outImages',_imageOuts);
  eraseImage(_soleOccupencyImage);
  eraseImage(outputParameterImageOuts.Images[1]);
  _imageSrcRowmax:=_h-1;
  _imageSrcColmax:=_w-1;
  SetLength(_segmentList,0);
  _vectorOutImage:=outputParameterImageOuts.Images[1];
  _trackMonitoringOutImage:=outputParameterImageOuts.Images[0];
  _monitoring:=None;
  if parameterMonitoring.Value='TRACKING' then _monitoring:=Tracking;
  if parameterMonitoring.Value='PIXEL CHAIN' then _monitoring:=PixelChain;
  if parameterMonitoring.Value='POLYGONAL APPROXIMATION' then _monitoring:=PolygonalApproximation;
  if parameterMonitoring.Value='CRITICAL POINTS' then _monitoring:=CriticalPoints;
  _showVectorWidth:=false;
  if parameterShowVectorWidth.Value='TRUE' then _showVectorWidth:=true;
  _showConnectedVector:=true;
  if parameterShowConnectedVector.Value='FALSE' then _showConnectedVector:=false;
  _epsylone:=parameterPolygonalApproximationEpsilone.Value / 10;
  // start process
  if _monitoring=None then begin
    eraseImage(outputParameterImageOuts.Images[0]);
  end else begin
    copyImageToImage(parameterImageIn.Image,outputParameterImageOuts.Images[0]);
  end;
  Image.resetNextColor();
  _run();
 end;
end;

procedure TFilterSPV.setParameterImage( const aName: String; const aImage: PBitmap32);
begin
  if aName='inImage' then begin
    deleteImages;
  end;
  inherited;
end;

procedure TFilterSPV._run();
var
  c : Word;
  imageSrcRow, imageSrcCol : Integer;
  scanLineIncrement : Integer;
  startMedialAxisInfo : TMedialAxisInfo;
  currentPixel : TFPoint;
  stop : boolean;
  trackingCyclesCount : Integer;
begin
  scanLineIncrement:=parameterScanLineIncrement.Value;
  imageSrcRow:=0;
  stop:=false;
  trackingCyclesCount:=0;
  repeat
    for imageSrcCol:=0 to _imageSrcColmax do begin
      c:=Image.Intensity(_Src[imageSrcRow*_w+imageSrcCol]);
      // monitoring
      if _monitoring=Tracking then begin
        if Image.getPixel(_trackMonitoringOutImage,imageSrcCol,imageSrcRow)=clBlack32 then begin
          Image.setPixel(_trackMonitoringOutImage,imageSrcCol,imageSrcRow,clGray32);
        end;
      end;
      // if we enter in a line
      if c>=_backgroundThreshold then begin
        currentPixel.x:=imageSrcCol;
        currentPixel.y:=imageSrcRow;
        // if we are not in a known vector
        if isInSoleOccupency(currentPixel)=false then begin
          startMedialAxisInfo:=findStartMedialAxisPoint(currentPixel);
          // if this new start medial axis point is not in a known vector
          if isInSoleOccupency(startMedialAxisInfo.point)=false then begin
            startTracking(startMedialAxisInfo);
            Inc(trackingCyclesCount);
          end;
        end;
        if trackingCyclesCount>=parameterMaximalTrackingCycles.Value then begin
          stop:=true;
          break;
        end;
      end;
    end;
    Inc(imageSrcRow,scanLineIncrement);
  until (imageSrcRow>_imageSrcRowmax) or (stop=true);
end;

function TFilterSPV.findStartMedialAxisPoint(currentPixel : TFPoint) : TMedialAxisInfo;
var
  startMedialAxisInfo : TMedialAxisInfo;
  horizontalRunInfo, verticalRunInfo : TRunInfo;
  distance : Single;
  p : TFPoint;
  searchCount : Integer;
begin
  p:=currentPixel;
  searchCount:=0;
  repeat
    horizontalRunInfo:=horizontalRun(p);
    verticalRunInfo:=verticalRun(horizontalRunInfo.middleRunPoint);
    distance:=getDistance(horizontalRunInfo.middleRunPoint,verticalRunInfo.middleRunPoint);
    p:=verticalRunInfo.middleRunPoint;
    Inc(searchCount); // we set a limit (not specified by Dori)
  until (distance<=1) or (searchCount=10);
  startMedialAxisInfo.point:=verticalRunInfo.middleRunPoint;
  if horizontalRunInfo.length>verticalRunInfo.length then begin
    startMedialAxisInfo.lengthDirection:=Horizontal;
  end else begin
    startMedialAxisInfo.lengthDirection:=Vertical;
  end;
  result:=startMedialAxisInfo;
end;

function TFilterSPV.horizontalRun(currentPixel : TFPoint) : TRunInfo;
var
  horizontalRunInfo : TRunInfo;
begin
  horizontalRunInfo.segment.p2:=horizontalDirectedRun(currentPixel,1);
  horizontalRunInfo.segment.p1:=horizontalDirectedRun(currentPixel,-1);
  horizontalRunInfo.length:=Abs(horizontalRunInfo.segment.p2.x-horizontalRunInfo.segment.p1.x+1);
  horizontalRunInfo.middleRunPoint.x:=horizontalRunInfo.segment.p1.x + (horizontalRunInfo.length / 2) - 0.5;
  horizontalRunInfo.middleRunPoint.y:=currentPixel.y;
  Result:=horizontalRunInfo;
end;

{
runSign>=0 : left->right; runSign<0 : right->left
}
function TFilterSPV.horizontalDirectedRun(currentPixel : TFPoint; runSign : Integer) : TFPoint;
var
  scanPixel : TColor32;
  horizontalRunPoint : TFPoint;
  x,y : Integer;
  runLength : Integer;
begin
  scanPixel:=255;
  x:=Round(currentPixel.x);
  y:=Round(currentPixel.y);
  runLength:=0;
  if Image.isValidPoint(_imageIn,x,y)=true then begin
   if runSign>=0 then begin
    while (x<_imageSrcColmax) and (scanPixel>=_backgroundThreshold) and (runLength<_currentTrackingRunLengthMax) do begin
      Inc(runLength);
      Inc(x);
      scanPixel:=Image.Intensity(_Src[y*_w+x]);
    end;
    Dec(x);
   end else begin
    while (x>=1) and (scanPixel>=_backgroundThreshold) and (runLength<_currentTrackingRunLengthMax) do begin
      Inc(runLength);
      Dec(x);
      scanPixel:=Image.Intensity(_Src[y*_w+x]);
    end;
    Inc(x);
   end;
  end;
  horizontalRunPoint.x:=x;
  horizontalRunPoint.y:=y;
  Result:=horizontalRunPoint;
end;

function TFilterSPV.verticalRun(currentPixel : TFPoint) : TRunInfo;
var
  verticalRunInfo : TRunInfo;
begin
  verticalRunInfo.segment.p2:=verticalDirectedRun(currentPixel,1);
  verticalRunInfo.segment.p1:=verticalDirectedRun(currentPixel,-1);
  verticalRunInfo.length:=Abs(verticalRunInfo.segment.p2.y-verticalRunInfo.segment.p1.y+1);
  verticalRunInfo.middleRunPoint.x:=currentPixel.x;
  verticalRunInfo.middleRunPoint.y:=verticalRunInfo.segment.p1.y + (verticalRunInfo.length / 2) - 0.5;
  Result:=verticalRunInfo;
end;

{
runSign>=0 : left->right; runSign<0 : right->left
}
function TFilterSPV.verticalDirectedRun(currentPixel : TFPoint; runSign : Integer) : TFPoint;
var
  scanPixel : Word;
  verticalRunPoint : TFPoint;
  x,y : Integer;
  runLength : Integer;
begin
  scanPixel:=255;
  x:=Round(currentPixel.x);
  y:=Round(currentPixel.y);
  runLength:=0;
  if Image.isValidPoint(_imageIn,x,y)=true then begin
   if runSign>=0 then begin
    while (y<_imageSrcRowmax) and (scanPixel>=_backgroundThreshold) and (runLength<_currentTrackingRunLengthMax) do begin
      Inc(runLength);
      Inc(y);
      scanPixel:=Image.Intensity(_Src[y*_w+x]);
    end;
    Dec(y);
   end else begin
    while (y>=1) and (scanPixel>=_backgroundThreshold) and (runLength<_currentTrackingRunLengthMax) do begin
      Inc(runLength);
      Dec(y);
      scanPixel:=Image.Intensity(_Src[y*_w+x]);
    end;
    Inc(y);
   end;
  end;
  verticalRunPoint.x:=x;
  verticalRunPoint.y:=y;
  Result:=verticalRunPoint;
end;

procedure TFilterSPV.startTracking(startMedialAxisInfo : TMedialAxisInfo);
var
  segmentList, appoximatedSegmentList : TSegmentList;
  i : Integer;
  segment : TSegment;
  vectorColor : TColor32;
  vectorWidth, averagedVectorWidth : Single;
  initialSegmentListLength : Integer;
  newSegmentCount : Integer;
begin
  initialSegmentListLength:=Length(_segmentList);
  vectorWidth:=0;
  // directed tracking right->left
  _currentTrackingRunLengthMax:=_maximalTrackingStep;
  segmentList:=directedTracking(startMedialAxisInfo,-1);
  appoximatedSegmentList:=polygonalization(segmentList);
  for i:=Length(appoximatedSegmentList)-1 downto 0 do begin
    segment:=appoximatedSegmentList[i];
    addSegment(_segmentList,segment.p2,segment.p1,segment.width);
    vectorWidth:=vectorWidth+segment.width;
  end;
  // directed tracking left->right
  _currentTrackingRunLengthMax:=_maximalTrackingStep;
  segmentList:=directedTracking(startMedialAxisInfo,1);
  appoximatedSegmentList:=polygonalization(segmentList);
  for i:=0 to Length(appoximatedSegmentList)-1 do begin
    segment:=appoximatedSegmentList[i];
    addSegment(_segmentList,segment.p1,segment.p2,segment.width);
    vectorWidth:=vectorWidth+segment.width;
  end;
  newSegmentCount:=Length(_segmentList) - initialSegmentListLength;
  if newSegmentCount>0 then begin
    // averaging width between both track
    averagedVectorWidth:=vectorWidth / newSegmentCount;
    for i:=initialSegmentListLength to Length(_segmentList)-1 do begin
      _segmentList[i].width:=averagedVectorWidth;
    end;
    // draw new segments
    vectorColor:=Image.getNextColor();
    for i:=initialSegmentListLength to Length(_segmentList)-1 do begin
      segment:=_segmentList[i];
      // draw vectors
      if _showVectorWidth=false then begin
        if _showConnectedVector=false then begin
          vectorColor:=Image.getNextColor();
        end;
        Image.drawLine(_vectorOutImage,segment.p1,segment.p2,vectorColor);
      end else begin
        Image.drawLine(_vectorOutImage,segment.p1,segment.p2,clWhite32,segment.width);
      end;
      // draw critical point
      if _monitoring=CriticalPoints then begin
        Image.setPixel(_trackMonitoringOutImage,segment.p1.x,segment.p1.y,clRed32);
        Image.setPixel(_trackMonitoringOutImage,segment.p2.x,segment.p2.y,clRed32);
      end;
    end;
  end;
end;

function TFilterSPV.directedTracking(startMedialAxisInfo : TMedialAxisInfo; runSign : Integer) : TSegmentList;
var
  lastBadTrackingCycleInfo, lastGoodTrackingCycleInfo : TTrackingCycleInfo;
  i : Integer;
  trackInfo : TTrackingCycleInfo;
  segmentList : TSegmentList;
  p1,p2 : PFPoint;
  segment : TSegment;
begin
  SetLength(_currentTrackingCycleInfoList,1);
  // start tracking cycles
  trackingCycles(startMedialAxisInfo,runSign);
  lastBadTrackingCycleInfo:=_currentTrackingCycleInfoList[Length(_currentTrackingCycleInfoList)-1];
  // if we must start a Junction Recovery Process
  if (lastBadTrackingCycleInfo.continuationConditionsSatisfied=1) or
     (lastBadTrackingCycleInfo.continuationConditionsSatisfied=2) or
     (lastBadTrackingCycleInfo.continuationConditionsSatisfied=3) then begin
    lastGoodTrackingCycleInfo:=_currentTrackingCycleInfoList[Length(_currentTrackingCycleInfoList)-2];
    // we must start the junction recovery process from the last good point
    lastGoodTrackingCycleInfo:=startJunctionRecoveryProcess(lastGoodTrackingCycleInfo,runSign);
    if lastGoodTrackingCycleInfo.continuationConditionsSatisfied=0 then begin
      // we have found a new point that will replace the last bad one
      _currentTrackingCycleInfoList[Length(_currentTrackingCycleInfoList)-1]:=lastGoodTrackingCycleInfo;
    end else begin
      // we have not found a new point, so we remove the last bad one
      SetLength(_currentTrackingCycleInfoList,Length(_currentTrackingCycleInfoList)-1);
    end;
  end else begin
    // we remove the last bad one
    SetLength(_currentTrackingCycleInfoList,Length(_currentTrackingCycleInfoList)-1);
  end;
  // if there is only the startMedialAxis point, then we have found nothing
  if Length(_currentTrackingCycleInfoList)=1 then begin
    SetLength(_currentTrackingCycleInfoList,0);
  end;
  // use this tracking cycle info list
  if Length(_currentTrackingCycleInfoList)>0 then begin
    if _monitoring=Tracking then begin
      // draw track monitoring
      for i:=Low(_currentTrackingCycleInfoList)+1 to High(_currentTrackingCycleInfoList) do begin
        trackInfo:=_currentTrackingCycleInfoList[i];
        Image.drawLine(_trackMonitoringOutImage,trackInfo.initalMedialAxisInfo.point,trackInfo.trakingStepStopPoint,clGreen32);
        Image.drawLine(_trackMonitoringOutImage,trackInfo.widthRunMedialAxisInfo.segment.p1,trackInfo.widthRunMedialAxisInfo.segment.p2,clBlue32);
      end;
      trackInfo:=_currentTrackingCycleInfoList[Low(_currentTrackingCycleInfoList)];
      Image.setPixel(_trackMonitoringOutImage,
        Image.getValidX(_trackMonitoringOutImage, trackInfo.initalMedialAxisInfo.point.x),
        Image.getValidY(_trackMonitoringOutImage, trackInfo.initalMedialAxisInfo.point.y),clRed32);
    end;
    // create all segments
    p1:=nil;
    for i:=Low(_currentTrackingCycleInfoList) to High(_currentTrackingCycleInfoList) do begin
      p2:=@_currentTrackingCycleInfoList[i].newMedialAxisInfo.point;
      if p1<>nil then begin
        addSegment(segmentList,p1^,p2^,_currentTrackingCycleInfoList[i].widthRunMedialAxisInfo.length);
        // draw points
        if _monitoring=PixelChain then begin
          Image.setPixel(_trackMonitoringOutImage,p1^.x,p1.y,clRed32);
          Image.setPixel(_trackMonitoringOutImage,p2^.x,p2.y,clRed32);
        end;
      end;
      p1:=p2;
    end;
    // draw sole occupency
    for i:=Low(segmentList) to High(segmentList) do begin
      segment:=segmentList[i];
      Image.drawLine(_soleOccupencyImage,segment.p1,segment.p2,clWhite32,segment.width);
    end;
  end;
  Result:=segmentList;
end;

procedure TFilterSPV.trackingCycles(initialMedialAxisInfo : TMedialAxisInfo; runSign : Integer);
var
  trackingCycleInfo, lastTrackingCycleInfo : TTrackingCycleInfo;
  trackingCycleInfoCount : Integer;
begin
  trackingCycleInfoCount:=Length(_currentTrackingCycleInfoList);
  trackingCycleInfo:=_currentTrackingCycleInfoList[trackingCycleInfoCount-1];
  trackingCycleInfo.initalMedialAxisInfo:=initialMedialAxisInfo;
  trackingCycleInfo.widthAverage:=0;
  trackingCycleInfo.newMedialAxisInfo:=initialMedialAxisInfo;
  _currentTrackingCycleInfoList[trackingCycleInfoCount-1]:=trackingCycleInfo;
  repeat
    lastTrackingCycleInfo:=trackingCycleInfo;
    // call trackingCycle function
    trackingCycleInfo:=trackingCycle(lastTrackingCycleInfo,runSign);
    // in all case, we add this track
    Inc(trackingCycleInfoCount);
    SetLength(_currentTrackingCycleInfoList,trackingCycleInfoCount);
    _currentTrackingCycleInfoList[trackingCycleInfoCount-1]:=trackingCycleInfo;
  until trackingCycleInfo.continuationConditionsSatisfied>0;
end;

function TFilterSPV.trackingCycle(lastTrackingCycleInfo : TTrackingCycleInfo; runSign : Integer) : TTrackingCycleInfo;
var
  trackingCycleInfo : TTrackingCycleInfo;
  currentMedialAxisInfo : TMedialAxisInfo;
  widthDifference : Single;
  c : TColor32;
begin
  currentMedialAxisInfo:=lastTrackingCycleInfo.newMedialAxisInfo;
  trackingCycleInfo.initalMedialAxisInfo:=currentMedialAxisInfo;
  // make a tracking step
  trackingCycleInfo.trakingStepStopPoint:=trackingStep(currentMedialAxisInfo,runSign);
  // make the width run to found the new medial axis point
  if currentMedialAxisInfo.lengthDirection=Horizontal then begin
    trackingCycleInfo.trackingStepLength:=Abs(Round(trackingCycleInfo.trakingStepStopPoint.x-currentMedialAxisInfo.point.x));
    trackingCycleInfo.widthRunMedialAxisInfo:=verticalRun(trackingCycleInfo.trakingStepStopPoint);
    // direction as changed ?
    if trackingCycleInfo.trackingStepLength<(trackingCycleInfo.widthRunMedialAxisInfo.length / 2) then begin
      trackingCycleInfo.newMedialAxisInfo.lengthDirection:=Vertical;
    end else begin
      trackingCycleInfo.newMedialAxisInfo.lengthDirection:=Horizontal;
    end;
  end else begin
    trackingCycleInfo.trackingStepLength:=Abs(Round(trackingCycleInfo.trakingStepStopPoint.y-currentMedialAxisInfo.point.y));
    trackingCycleInfo.widthRunMedialAxisInfo:=horizontalRun(trackingCycleInfo.trakingStepStopPoint);
    // direction as changed ?
    if trackingCycleInfo.trackingStepLength<(trackingCycleInfo.widthRunMedialAxisInfo.length / 2) then begin
      trackingCycleInfo.newMedialAxisInfo.lengthDirection:=Horizontal;
    end else begin
      trackingCycleInfo.newMedialAxisInfo.lengthDirection:=Vertical;
    end;
  end;
  trackingCycleInfo.newMedialAxisInfo.point:=trackingCycleInfo.widthRunMedialAxisInfo.middleRunPoint;

  // continuationConditionsSatisfied
  trackingCycleInfo.continuationConditionsSatisfied:=0;
  // -- Positive tracking step length (we must check it first)
  if trackingCycleInfo.continuationConditionsSatisfied=0 then begin
    if trackingCycleInfo.trackingStepLength<=0 then begin
      trackingCycleInfo.continuationConditionsSatisfied:=4;
    end;
  end;
  // -- Width preservation
  if trackingCycleInfo.continuationConditionsSatisfied=0 then begin
    if lastTrackingCycleInfo.widthAverage=0 then begin
      trackingCycleInfo.widthAverage:=trackingCycleInfo.widthRunMedialAxisInfo.length;
    end else begin
      trackingCycleInfo.widthAverage:=(lastTrackingCycleInfo.widthAverage + trackingCycleInfo.widthRunMedialAxisInfo.length) / 2;
    end;
    widthDifference:=Abs(trackingCycleInfo.widthAverage-trackingCycleInfo.widthRunMedialAxisInfo.length);
    if widthDifference>(trackingCycleInfo.widthAverage/2) then begin
      trackingCycleInfo.continuationConditionsSatisfied:=1;
    end;
  end;
  // -- Sole occupancy
  if trackingCycleInfo.continuationConditionsSatisfied=0 then begin
    c:=Image.getPixel(_soleOccupencyImage,
      Image.getValidX(_soleOccupencyImage,Round(trackingCycleInfo.newMedialAxisInfo.point.x)),
      Image.getValidY(_soleOccupencyImage,Round(trackingCycleInfo.newMedialAxisInfo.point.y)));
    if c<>0 then begin
      trackingCycleInfo.continuationConditionsSatisfied:=2;
    end;
  end;
  // -- Length direction consistency
  if trackingCycleInfo.continuationConditionsSatisfied=0 then begin
    if trackingCycleInfo.newMedialAxisInfo.lengthDirection<>trackingCycleInfo.initalMedialAxisInfo.lengthDirection then begin
      trackingCycleInfo.continuationConditionsSatisfied:=3;
    end;
  end;

  Result:=trackingCycleInfo;
end;

function TFilterSPV.trackingStep(currentMedialAxisInfo : TMedialAxisInfo; runSign : Integer) : TFPoint;
var
  trakingStepStopPoint : TFPoint;
begin
  if currentMedialAxisInfo.lengthDirection=Horizontal then begin
    trakingStepStopPoint:=horizontalDirectedRun(currentMedialAxisInfo.point,runSign);
  end else begin
    trakingStepStopPoint:=verticalDirectedRun(currentMedialAxisInfo.point,runSign);
  end;
  Result:=trakingStepStopPoint;
end;

function TFilterSPV.startJunctionRecoveryProcess(lastTrackingCycleInfo : TTrackingCycleInfo; runSign : Integer) : TTrackingCycleInfo;
var
  trackingCycleInfo : TTrackingCycleInfo;
begin
  repeat
    _currentTrackingRunLengthMax:=_currentTrackingRunLengthMax div 2;
    trackingCycleInfo:=trackingCycle(lastTrackingCycleInfo,runSign);
  until (trackingCycleInfo.continuationConditionsSatisfied=0) or (_currentTrackingRunLengthMax=0);
  Result:=trackingCycleInfo;
end;

function TFilterSPV.polygonalization(segmentList : TSegmentList) : TSegmentList;
var
  imageMonitoring : PBitmap32;
begin
  imageMonitoring:=nil;
  if _monitoring=PolygonalApproximation then begin
    imageMonitoring:=_trackMonitoringOutImage;
  end;
  Result:=polygonalization_SklanskyGonzalez(segmentList,_epsylone,imageMonitoring);
end;

function TFilterSPV.isInSoleOccupency(point:TFPoint) : boolean;
begin
  Result:=false;
  if Image.getPixel(_soleOccupencyImage,
       Image.getValidX(_soleOccupencyImage,point.x),
       Image.getValidY(_soleOccupencyImage,point.y)) <>0 then begin
    Result:=true;
  end;
end;


end.