Box counting algorithm

[taietel]

I'm working on this project for some time, but today I had the chance to give it a real test: to determine the area occupied by a complex building, based on a picture taken from above.

The idea is simple: it changes the picture in BW format, break it in small pieces (boxes) down to a pixel and then, after the process is done, the number of boxes that cover the area * size of the pixel * scale factor = area.

Here is just the module, without calculus, and the two examples of scanning:

- first is scanning only the edges/borders of the inside area

- second example scans the area.

expandcollapse popup

#include <ScreenCapture.au3>
#include <WindowsConstants.au3>
#include <WinAPI.au3>
#include <GuiConstantsEx.au3>
#include <Misc.au3>
#include <Array.au3>
;==================================================================================
; Main Application...:  Box Counting
; Module.............:  Image processing
; Version............:  2.0.0 (rewritten the core functions)
; Last Rev...........:  August 16, 2011
; Author.............:  M. Iancu (taietel at yahoo dot com)
; Thanks.............:  UEZ, for pointing me in the right direction ([url="http://autoitscript.com/forum/topic/131383-cpu-gets-high-when-using-gdi/"]http://autoitscript.com/forum/topic/131383-cpu-gets-high-when-using-gdi/[/url])
;       Authenticity, for GDIP.au3
;==================================================================================
HotKeySet("{ESC}","_Exit")
Opt("MustDeclareVars", 1)
Opt("CaretCoordMode", 0)
Global $iD, $iFilled, $hBrush, $bgColour

Global $sImage = @ScriptDir & "\fractal_tree.jpg"
If Not FileExists($sImage) Then
 InetGet("[url="http://read.pudn.com/downloads115/sourcecode/graph/fractal/482731/box-counting/fractal_tree.jpg"]http://read.pudn.com/downloads115/sourcecode/graph/fractal/482731/box-counting/fractal_tree.jpg[/url]", $sImage)
EndIf

Global $first = _StartBoxing($sImage, 0) ; example - get only the borders
_ArrayDisplay($first)
Global $second = _StartBoxing($sImage, 1) ; example - get the whole areas inside
_ArrayDisplay($second)
Exit

While 1
 Sleep(10)
 Switch GUIGetMsg()
  Case -3
   _Exit()
 EndSwitch
WEnd

; #FUNCTION# ====================================================================================================================
; Name ..........: _StartBoxing
; Description ...: Determine the number of boxes that cover an area (or the borders of that area)
; Syntax ........: _StartBoxing($sImage[, $iType = 0, [$lBoxColour = 0xA000FF00, [$iSaveImages=False]]])
; Parameters ....: $sImage              - Path to image.
;                  $iType               - [optional] Processing mode.
;                  |0                - scan only outside borders of the inside areas [Default].
;                  |1                - scan just the inside areas.
;                  $lBoxColour   - box colour. Default 0xA000FF00
;                  $iSaveImages         - True=capture image of every step in the Image folder. Default=False
; Return values .: Array of values
;                  |[0][0]              - description
;                  |[0][1]              - value
;                  |[1][0]              - Surface boxing mode
;                  |[1][1]              - BORDER or SURFACE
;                  |[2][0]              - Image width
;                  |[2][1]              - value (pixels)
;                  |[3][0]              - Image height
;                  |[3][1]              - value (pixels)
;                  |[4][0]              - Background colour (top-left pixel of the image)
;                  |[4][1]              - value (format AARRGGBB)
;                  |[5][0]              - Width of the squared image (if width>height then it is width, otherwise is height)
;                  |[5][1]              - value (pixels)
;                  |[6][0]              - Number of steps
;                  |[6][1]              - values (delimited by "|")
;                  |[7][0]              - Box width
;                  |[7][1]              - values (delimited by "|")
;                  |[8][0]              - Number of boxes
;                  |[8][1]              - values (delimited by "|")
;                  |[9][0]              - Number of filled boxes
;                  |[9][1]              - values (delimited by "|")
; Author ........: Mihai Iancu (aka taietel)
; Modified ......:
; Remarks .......:
; Related .......:
; Link ..........:
; Example .......: Yes
; ===============================================================================================================================
Func _StartBoxing($sImage, $iType = 0, $lBoxColour=0xA000FF00, $bSaveImages=False)
 Local $aRet[10][2]
 $aRet[0][0]="Description"
 $aRet[0][1]="Value"

 If $bSaveImages Then
  If Not FileExists(@ScriptDir&"\Images") Then DirCreate(@ScriptDir&"\Images")
 EndIf

 If $iType=1 Then
  $aRet[1][0]="Surface boxing mode"
  $aRet[1][1]="SURFACE"
 Else
  $aRet[1][0]="Outline border boxing mode"
  $aRet[1][1]="BORDER"
 EndIf

 _GDIPlus_Startup()

 Local $iTimer = TimerInit()

 Local $hBitmap, $iW, $iH, $hBMPbw, $aB, $hGUI, $iC, $hGraphic
 $hBitmap = _GDIPlus_BitmapCreateFromFile($sImage)

 $iW = _GDIPlus_ImageGetWidth($hBitmap)
 $iH = _GDIPlus_ImageGetHeight($hBitmap)

 $aRet[2][0]="Image width"
 $aRet[2][1]=$iW

 $aRet[3][0]="Image height"
 $aRet[3][1]=$iH

 $hBMPbw = _GDIPlus_BitmapCloneArea($hBitmap, 0, 0, $iW, $iH, $GDIP_PXF01INDEXED)

 ;get the top-left pixel - this will be the background colour
 Local $c = DllCall($ghGDIPDll, "uint", "GdipBitmapGetPixel", "hwnd", $hBMPbw, "int", 0, "int", 0, "uint*", 0)
 $bgColour = Hex($c[4])

 $aRet[4][0]="Background colour"
 $aRet[4][1]=$bgColour

 Local $aBW = __SetImageBWArray($hBMPbw, $iType)
 $hBMPbw = $aBW[0]
 $hGUI = GUICreate("Test", $iW, $iH, -1, -1, $WS_POPUP + $WS_BORDER, $WS_EX_TOPMOST)
 GUICtrlCreatePic("", 0, 0, $iW, $iH, -1, $GUI_WS_EX_PARENTDRAG)
 GUISetState()
 $iC = WinGetCaretPos()

 $hGraphic = _GDIPlus_GraphicsCreateFromHWND($hGUI)
 _GDIPlus_GraphicsSetSmoothingMode($hGraphic, 2)

 $hBrush = _GDIPlus_BrushCreateSolid($lBoxColour)

 If $iW >= $iH Then
  $iD = $iW
 Else
  $iD = $iH
 EndIf

 $aRet[5][0]="Width of the squared image"
 $aRet[5][1]=$iD

 Local $i = 0, $j = 0, $iBoxes, $iBoxWdth

 _ScreenCapture_SetJPGQuality(90)

 Local $iSteps="", $iBoxWidth="", $iNoBoxes="", $iNoFilled=""
 Do
  _GDIPlus_GraphicsDrawImageRect($hGraphic, $hBitmap, 0, 0, $iW, $iH)
  $iBoxes = 2 ^ $i
  $iBoxWdth = $iD / $iBoxes
  $iFilled = 0
  If $j = 0 Then
   If $bSaveImages Then
    Sleep(300);give time for capturing
    _ScreenCapture_CaptureWnd(@ScriptDir & "\Images\Image_"& $iType & "_00.jpg", $hGUI, $iC[0], $iC[1], $iW, $iH, False)
   EndIf
   $iFilled = 1
  Else
   __Box_FillBoxes($iBoxes, $hGraphic, $iW, $iH, $hBMPbw, $aBW[1])
   If $bSaveImages Then _ScreenCapture_CaptureWnd(@ScriptDir & "\Images\Image_" & $iType & "_" & StringFormat("%02i", $j) & ".jpg", $hGUI, $iC[0], $iC[1], $iW, $iH, False)
  EndIf
  $iSteps &= $j&"|"
  $iBoxWidth &= StringFormat("%.3f", $iBoxWdth) &"|"
  $iNoBoxes &= $iBoxes ^ 2 & "|"
  $iNoFilled &= $iFilled & "|"
  $j += 1
  $i += 1
 Until $iBoxWdth < 1

 $aRet[6][0]="Steps"
 $aRet[6][1]=StringTrimRight($iSteps,1)

 $aRet[7][0]="Box width"
 $aRet[7][1]=StringTrimRight($iBoxWidth,1)

 $aRet[8][0]="Number of boxes"
 $aRet[8][1]=StringTrimRight($iNoBoxes,1)

 $aRet[9][0]="Number of filled boxes"
 $aRet[9][1]=StringTrimRight($iNoFilled,1)

 _GDIPlus_BrushDispose($hBrush)
 _GDIPlus_BitmapDispose($hBitmap)
 _GDIPlus_BitmapDispose($hBMPbw)
 _GDIPlus_GraphicsDispose($hGraphic)
 _GDIPlus_Shutdown()
 GUIDelete($hGUI)
 Return $aRet
EndFunc   ;==>_StartBoxing

Func _Exit()
 Exit
EndFunc

#region #INTERNAL_USE_ONLY#
Func __Box_CheckPixels($hBmp, $x, $y, $s, $w, $h, $aArray)
 For $i = $x To $x + $s
  For $j = $y To $y + $s
   If $i < $w And $j < $h Then
    If $aArray[$i][$j] = 1 Then Return True
   EndIf
  Next
 Next
 Return False
EndFunc   ;==>__Box_CheckPixels

Func __Box_FillBoxes($iSize, $hContext, $w, $h, $hBitmap, $aArray, $bBackground = False)
 Local $x, $y, $draw, $s = Ceiling($iD / $iSize)
 For $y = 0 To $h Step $s
  For $x = 0 To $w Step $s
   $draw = __Box_CheckPixels($hBitmap, $x, $y, $s, $w, $h, $aArray)
   Switch $bBackground
    Case False
     If $draw Then
      $iFilled += 1
      _GDIPlus_GraphicsFillRect($hContext, $x, $y, $s, $s, $hBrush)
     EndIf
    Case Else
     If Not $draw Then
      $iFilled += 1
      _GDIPlus_GraphicsFillRect($hContext, $x, $y, $s, $s, $hBrush)
     EndIf
   EndSwitch
  Next
 Next
 Return
EndFunc   ;==>__Box_FillBoxes

Func __GetImageBWArray($hBmp)
 Local $tBmpData, $stride, $Scan0
 Local $v_Buffer, $width, $height
 Local $i, $j

 $tBmpData = __GDIPlus_BitmapLockBitsAll($hBmp, $GDIP_ILMREAD)

 $width  = DllStructGetData($tBmpData, "Width")
 $height = DllStructGetData($tBmpData, "Height")
 $stride = DllStructGetData($tBmpData, "Stride")
 $Scan0  = DllStructGetData($tBmpData, "Scan0")

 Local $aArray[$width][$height]

 For $i = 0 To $width - 1
  For $j = 0 To $height - 1
   $v_Buffer = DllStructCreate("dword", $Scan0 + ($j * $stride) + ($i * 4))
   $aArray[$i][$j] = _Iif(Hex(DllStructGetData($v_Buffer, 1)) = $bgColour, 0, 1)
  Next
 Next
 _GDIPlus_BitmapUnlockBits($hBmp, $tBmpData)
 Return $aArray
EndFunc   ;==>__GetImageBWArray

Func __SetImageBWArray($hBmp, $bFill = 0)
 Local $aRet[2], $aArray, $aTmpArray
 ;__Test("->Loading image to array...")
 $aArray = __GetImageBWArray($hBmp)
 ;__Test("->Processing array...")
 $aTmpArray = $aArray

 If $bFill = 0 Then
  Local $tBmpData, $w, $h, $Scan0
  Local $sResult = "", $v_BufferA
  Local $i, $j
  $tBmpData = __GDIPlus_BitmapLockBitsAll($hBmp, $GDIP_ILMWRITE)
  $w = DllStructGetData($tBmpData, "Width")
  $h = DllStructGetData($tBmpData, "Height")
  $Scan0 = DllStructGetData($tBmpData, "Scan0")
  $v_BufferA = DllStructCreate("byte[" & $h * $w * 4 & "]", $Scan0)
  For $j = 0 To $h - 1
   For $i = 0 To $w - 1
    If $i > 0 And $j > 0 And $i < $w - 1 And $j < $h - 1 Then
     If $aArray[$i][$j] = 1 Then
      If BitAND($aArray[$i - 1][$j - 1], $aArray[$i - 1][$j], $aArray[$i - 1][$j - 1], $aArray[$i][$j - 1], $aArray[$i][$j], $aArray[$i][$j + 1], $aArray[$i + 1][$j - 1], $aArray[$i + 1][$j], $aArray[$i + 1][$j + 1]) = 1 Then $aTmpArray[$i][$j] = 0
     EndIf
    EndIf
   Next
  Next
  For $j = 0 To $h - 1
   For $i = 0 To $w - 1
    $sResult &= _Iif($aTmpArray[$i][$j] = 1, "FF000000", "FF" & $bgColour)
   Next
  Next
  DllStructSetData($v_BufferA, 1, Binary("0x" & $sResult))
  _GDIPlus_BitmapUnlockBits($hBmp, $tBmpData)
 EndIf
 $aRet[0]=$hBmp
 $aRet[1]=$aTmpArray
 Return $aRet
EndFunc   ;==>__SetImageBWArray

Func __GDIPlus_BitmapLockBitsAll($hBitmap, $iFlags = $GDIP_ILMREAD, $iFormat = $GDIP_PXF32ARGB)
 Local $tData = DllStructCreate($tagGDIPBITMAPDATA)
 Local $pData = DllStructGetPtr($tData)
 Local $aResult = DllCall($ghGDIPDll, "int", "GdipBitmapLockBits", "handle", $hBitmap, "ptr", 0, "uint", $iFlags, "int", $iFormat, "ptr", $pData)
 If @error Then Return SetError(@error, @extended, 0)
 Return SetExtended($aResult[0], $tData)
EndFunc   ;==>__GDIPlus_BitmapLockBitsAll

Func __Test($sT)
 ConsoleWrite($sT & @CRLF)
EndFunc   ;==>__Test
#endregion #INTERNAL_USE_ONLY#

When the interface is ready (still needs a few touches), I will post it here, along with the calculus.

[monoscout999]

I like this kind of programs, very useful if you are in the topic. I work with Layher structures, and i was working in a script to auto calculate the material we have to use if you want to do some kind of sctructure, also with options about the sizes... is a good work to do and useful stuff. i quit that idea when i found that Layher already have a program like that.