using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Numerics;
namespace Algorithms.ImageProcessing
{
/// </summary>
public class BinaryMorphology
{
bool[] BinaryInput { get; set; }
int Width { get; set; }
int Height { get; set; }
BigInteger PackedImage;
int Padding { get; set; }
/// <summary>
/// constructor for BinaryMorphology class
/// </summary>
/// <param name="image">the image to process</param>
/// <param name="width">the width of the provided image</param>
/// <param name="padding">the padding to apply when storing this image, usually half the length of the structuring element</param>
public BinaryMorphology(bool[] image, int width, int padding)
{
Width = width + padding;
int height = (image.Length / width);
Height = height;
Padding = padding;
// last padding is for right padding the last line
BinaryInput = new bool[Width * Height + Padding];
// copy the data in the new array with necessary amount of left padding at every line
for (int i = 0; i < height; i++)
Buffer.BlockCopy(image, i * width, BinaryInput, i * Width + Padding, width); // one bool is encoded as 1 byte in c#
// convert to packed format
BitArray packed = new BitArray(BinaryInput);
// use intermediate byte[]
byte[] scratch = new byte[(BinaryInput.Length >> 3) + 1];
packed.CopyTo(scratch, 0);
// create BigInteger Image
PackedImage = new BigInteger(scratch);
}
/// <summary>
/// constructor for BinaryMorphology class
/// </summary>
/// <param name="image">the image to process</param>
/// <param name="threshold">the threshold level</param>
/// <param name="width">the width of the provided image</param>
/// <param name="padding">the padding to apply when storing this image, usually half the length of the structuring element</param>
public BinaryMorphology(byte[] image, byte threshold, int width, int padding)
: this(image.Select(b => b > threshold).ToArray(), width, padding)
{
}
/// <summary>
/// hit or miss transform:
/// X x (H,M) X: image, H: hit set (elements are ps), M: miss set (elements are qs)
/// X x (H,M) => result = p1 & ... & pn & ~q1 & ... & ~qn
/// refer to: Methods for Fast Morphological Image Transforms Using Bitmapped Binary Images (REINVAN DEN BOOMGAARD, RICHARD VAN BALEN)
///
/// -> dilation is ~(X x (0,S))
/// but the following takes fewer operations because ~(~a&~b) = (~(~a) | ~(~b)) = a | b
/// -> erosion is X x (S,0)
/// decreases object size (msb bits are erased)
/// </summary>
/// <param name="hmMask"></param>
/// <param name="input"></param>
/// <param name="output"></param>
public void ApplyHitOrMissTransform(HitOrMissMask hmMask, ref BigInteger input, out BigInteger output)
{
BigInteger scratchImageHit = -1;
BigInteger scratchImageMiss = 0;
for (int i = 0; i < hmMask.HitOrMiss.Length; i++)
if (hmMask.HitOrMiss[i] > 0)
scratchImageHit &= (input >> (Width * hmMask.HitOrMissY[i] + hmMask.HitOrMissX[i]));
for (int i = 0; i < hmMask.HitOrMiss.Length; i++)
if (hmMask.HitOrMiss[i] < 0)
scratchImageMiss |= (input >> (Width * hmMask.HitOrMissY[i] + hmMask.HitOrMissX[i]));
output = scratchImageHit & (~scratchImageMiss);
}
public void ApplyHitOrMissTransform(HitOrMissMask hmMask)
{
ApplyHitOrMissTransform(hmMask, ref PackedImage, out PackedImage);
}
private void Erode(byte[] mask, int width, int xCenter, int yCenter, ref BigInteger input, out BigInteger output)
{
sbyte[] erodeMask = mask.Select(p => (sbyte)((p == 0) ? 0 : 1)).ToArray();
HitOrMissMask erodeHmMask = new HitOrMissMask(erodeMask, width, xCenter, yCenter);
ApplyHitOrMissTransform(erodeHmMask, ref input, out output);
}
public void Erode(byte[] mask, int width, int xCenter, int yCenter)
{
Erode(mask, width, xCenter, yCenter, ref PackedImage, out PackedImage);
}
private void ErodeDisk1(ref BigInteger input, out BigInteger output)
{
byte[] erodeMask = HitOrMissMask.Disk1;
Erode(erodeMask, 3, 1, 1, ref input, out output);
}
public void ErodeDisk1()
{
ErodeDisk1(ref PackedImage, out PackedImage);
}
private void Dilate(byte[] mask, int width, int xCenter, int yCenter, ref BigInteger input, out BigInteger output)
{
sbyte[] dilateMask = mask.Select(p => (sbyte)((p == 0) ? 0 : -1)).ToArray();
HitOrMissMask dilateHmMask = new HitOrMissMask(dilateMask, width, xCenter, yCenter);
ApplyHitOrMissTransform(dilateHmMask, ref input, out output);
output = ~output;
}
public void Dilate(byte[] mask, int width, int xCenter, int yCenter)
{
Dilate(mask, width, xCenter, yCenter, ref PackedImage, out PackedImage);
}
private void DilateDisk1(ref BigInteger input, out BigInteger output)
{
byte[] dilateMask = HitOrMissMask.Disk1;
Dilate(dilateMask, 3, 1, 1, ref input, out output);
}
public void DilateDisk1()
{
DilateDisk1(ref PackedImage, out PackedImage);
}
public void Open(byte[] mask, int width, int xCenter, int yCenter)
{
Erode(mask, width, xCenter, yCenter);
Dilate(mask, width, xCenter, yCenter);
}
public void Close(byte[] mask, int width, int xCenter, int yCenter)
{
Dilate(mask, width, xCenter, yCenter);
Erode(mask, width, xCenter, yCenter);
}
/// <summary>
/// Returns a bool[] containing the perimeter image calculated by subtracting
/// from the image an eroded version of itself.
/// </summary>
/// <returns></returns>
public bool[] GetPerimeterImage()
{
BigInteger perim, eroded;
ErodeDisk1(ref PackedImage, out eroded);
perim = PackedImage & ~eroded;
return GetBoolArray(perim);
}
/// <summary>
/// unpack and return processed data in bool[]
/// </summary>
/// <returns></returns>
private bool[] GetBoolArray(BigInteger image)
{
bool[] boolProcessedCropped = new bool[(Width - Padding) * Height];
byte[] t1 = image.ToByteArray();
BitArray t2 = new BitArray(t1);
bool[] boolProcessed = new bool[t1.Length * 8];
t2.CopyTo(boolProcessed, 0);
// this is necessary as the size of the big integer might have changed
// (the msb bits are affected) when we do the erosion-dilation operations
// and that depends on the data.
for (int i = 0; i < Height; i++)
{
int off = i * (Width - Padding);
int bytesToCopy = Math.Max(0, Math.Min(boolProcessedCropped.Length, off + Width - Padding) - i * (Width - Padding));
bytesToCopy = Math.Min(bytesToCopy, boolProcessed.Length - (i * Width + Padding));
if (bytesToCopy > 0)
Buffer.BlockCopy(boolProcessed, i * Width + Padding, boolProcessedCropped, off, bytesToCopy);
}
return boolProcessedCropped;
}
/// <summary>
/// unpack and return processed data in bool[]
/// </summary>
/// <returns></returns>
public bool[] GetBoolArray()
{
return GetBoolArray(PackedImage);
}
/// <summary>
/// turn off pixels with count or more neighbors cleared in the 8-connected neighborhood
/// </summary>
/// <param name="count"></param>
public void Erode(int count)
{
Erode(ref PackedImage, out PackedImage, count);
}
/// <summary>
/// clear pixels for which at least count neighbors are cleared else the pixel is set
/// </summary>
/// <param name="imageIn"></param>
/// <param name="imageOut"></param>
/// <param name="count"></param>
private void Erode(ref BigInteger imageIn, out BigInteger imageOut, int count)
{
BigInteger[] BitsAround = GetSortedNeighborhoodBits(ref imageIn, count);
imageOut = imageIn & BitsAround[8 - count];
}
/// <summary>
/// turn off pixels with count or more neighbors cleared in the 8-connected neighborhood
/// </summary>
/// <param name="count"></param>
public void Dilate(int count)
{
Dilate(ref PackedImage, out PackedImage, count);
}
/// <summary>
/// set pixels for which at least count neighbors are set else the pixel is set
/// </summary>
/// <param name="imageIn"></param>
/// <param name="imageOut"></param>
/// <param name="count"></param>
private void Dilate(ref BigInteger imageIn, out BigInteger imageOut, int count)
{
BigInteger[] BitsAround = GetSortedNeighborhoodBits(ref imageIn, count);
imageOut = imageIn | BitsAround[count - 1];
}
/// <summary>
/// returns a list of images that contain the bits in the 8-connected neighborhood of
/// every pixel in imageIn. The neighborhood bits are sorted (set and unset bits are
/// seperated). ones go in the images with low ordinals, zeros go in the images with
/// higher ordinals
/// </summary>
/// <param name="imageIn"></param>
/// <param name="count"></param>
/// <returns></returns>
private BigInteger[] GetSortedNeighborhoodBits(ref BigInteger imageIn, int count)
{
// this could be done by reimplementing sum and accumulating into more than one array
// (using c1=A1&input, A1=A1|input, c2=A2&c1, A2=A2|c1, c3= A3&c2, A3=A3|c2,
// A1,A2,A3 are accumulator arrays, c1, c2, c3 are carry arrays )
BigInteger temp;
BigInteger[] BitsAround = new BigInteger[8];
int index = 0;
for (int i = -1; i <= 1; i++)
for (int j = -Width; j <= Width; j += Width)
{
if (!(i == 0 && j == 0)) // avoid considering the center pixel
{
BitsAround[index] = imageIn << (j + i); // negative shifts handled by framework
index++;
}
}
// swap bits such that ones go in the images with lower ordinals
// and zeros go in the images with higher ordinals
// need to do more than one pass to bring an on pixel in the highest ordinal
// down to the low ordinals
for (int i = 0; i < 7; i++)
for (int j = 0; j < 7; j++)
{
temp = BitsAround[j + 1];
BitsAround[j + 1] = BitsAround[j + 1] & BitsAround[j];
BitsAround[j] = BitsAround[j] | temp;
}
return BitsAround;
}
}
}