Flood fill algorithm implementation. More...

#include <flood_fill.h>

Inheritance diagram for Beatmup::FloodFill:

Public Types
enum	BorderMorphology { NONE = 0 , DILATE , ERODE }
	Morphological postprocessing operation applied to discovered connected components. More...

Public Types inherited from Beatmup::AbstractTask
enum class	TaskDeviceRequirement { CPU_ONLY , GPU_OR_CPU , GPU_ONLY }
	Specifies which device (CPU and/or GPU) is used to run the task. More...

Public Member Functions
	FloodFill ()

	~FloodFill ()

const AbstractBitmap *	getInput () const
	Returns input bitmap (null if not set yet) More...

const AbstractBitmap *	getOutput () const
	Returns output bitmap (null if not set yet) More...

IntRectangle	getBounds () const
	Returns bounding box of the computed mask. More...

int	getContourCount () const
	Returns number of detected contours. More...

const IntegerContour2D &	getContour (int contourIndex) const
	Returns a contour by index if computeContours was `true`, throws an exception otherwise. More...

void	setInput (AbstractBitmap *)
	Sets the input bitmap. More...

void	setOutput (AbstractBitmap *)
	Specifies the bitmap to put the resulting mask to. More...

void	setMaskPos (const IntPoint &)
	Specifies left-top corner position of the mask to compute inside the input bitmap. More...

void	setSeeds (const IntPoint seeds[], int seedCount)
	Specifies a set of seeds (starting points) More...

void	setSeeds (const int seedsXY[], int seedCount)

void	setTolerance (float)
	Sets the intensity tolerance threshold used to decide on similarity of neighboring pixels. More...

float	getTolerance () const
	Returns yjr intensity tolerance threshold. More...

void	setBorderPostprocessing (BorderMorphology operation, float holdRadius, float releaseRadius)
	Specifies a morphological operation to apply to the mask border. More...

void	setComputeContours (bool)
	Enables or disables contours computation. More...

ThreadIndex	getMaxThreads () const
	Gives the upper limint on the number of threads the task may be performed by. More...

virtual bool	process (TaskThread &thread) final
	Executes the task on CPU within a given thread. More...

virtual void	beforeProcessing (ThreadIndex threadCount, ProcessingTarget target, GraphicPipeline *gpu) final
	Instruction called before the task is executed. More...

virtual void	afterProcessing (ThreadIndex threadCount, GraphicPipeline *gpu, bool aborted) final
	Instruction called after the task is executed. More...

Public Member Functions inherited from Beatmup::AbstractTask
virtual bool	processOnGPU (GraphicPipeline &gpu, TaskThread &thread)
	Executes the task on GPU. More...

virtual TaskDeviceRequirement	getUsedDevices () const
	Communicates devices (CPU and/or GPU) the task is run on. More...

Public Member Functions inherited from Beatmup::Object
virtual	~Object ()

Protected Attributes
AbstractBitmap *	input
	input bitmap More...

AbstractBitmap *	output
	resulting mask More...

AbstractBitmap *	ignoredSeeds
	1-bit bitmap storing flags marking used pixels More...

IntPoint	maskPos
	left-top corner of the mask to compute over the input bitmap More...

IntRectangle	bounds
	mask bounds More...

std::mutex	access
	access control assuring internal thread safety More...

std::vector< IntPoint >	seeds
	set of starting points (seed points) More...

std::vector< IntegerContour2D * >	contours
	contours to store borders for each seed More...

BorderMorphology	borderMorphology
	border morphological postprocessing More...

float	tolerance
	intensity tolerance value More...

float	borderHold

float	borderRelease

bool	computeContours
	if `true`, border contours will be computed per each seed More...

Additional Inherited Members
Static Public Member Functions inherited from Beatmup::AbstractTask
static ThreadIndex	validThreadCount (int number)
	Valid thread count from a given integer value. More...

Private Member Functions inherited from Beatmup::BitmapContentLock
	BitmapContentLock ()

	~BitmapContentLock ()

void	readLock (GraphicPipeline gpu, AbstractBitmap bitmap, ProcessingTarget target)
	Locks content of a bitmap for reading using a specific processing target device. More...

void	writeLock (GraphicPipeline gpu, AbstractBitmap bitmap, ProcessingTarget target)
	Locks content of a bitmap for writing using a specific processing target device. More...

void	unlock (AbstractBitmap *bitmap)
	Drops a lock to the bitmap. More...

void	unlockAll ()
	Unlocks all the locked bitmaps unconditionally. More...

template<const ProcessingTarget target>
void	lock (GraphicPipeline gpu, AbstractBitmap input, AbstractBitmap *output)

void	lock (GraphicPipeline gpu, ProcessingTarget target, AbstractBitmap input, AbstractBitmap *output)

template<const ProcessingTarget target>
void	lock (GraphicPipeline gpu, std::initializer_list< AbstractBitmap > read, std::initializer_list< AbstractBitmap * > write)

template<typename ... Args>
void	unlock (AbstractBitmap *first, Args ... others)

Detailed Description

Flood fill algorithm implementation.

Discovers areas of similar colors up to a tolerance threshold around given positions (seeds) in the input image. These areas are filled with white color in another image (output). If the output bitmap is a binary mask, corresponding pixels are set to 1. The rest of the output image remains unchanged. Optionally, computes contours around the discovered areas and stores the contour positions. Also optionally, applies post-processing by dilating or eroding the discovered regions in the output image.

Definition at line 36 of file flood_fill.h.

Member Enumeration Documentation

◆ BorderMorphology

enum Beatmup::FloodFill::BorderMorphology

Morphological postprocessing operation applied to discovered connected components.

Enumerator
NONE	no postprocessing
DILATE	apply a dilatation
ERODE	apply an erosion

Definition at line 41 of file flood_fill.h.

                               {
             NONE = 0,           //!< no postprocessing
             DILATE,             //!< apply a dilatation
             ERODE               //!< apply an erosion
         };

Constructor & Destructor Documentation

◆ FloodFill()

FloodFill::FloodFill ( )

Definition at line 28 of file flood_fill.cpp.

                     :
     input(nullptr), output(nullptr), maskPos(0, 0), bounds(0,0,0,0), borderMorphology(NONE), tolerance(0), borderHold(0), borderRelease(0), computeContours(false)
 {}

◆ ~FloodFill()

FloodFill::~FloodFill ( )

Definition at line 33 of file flood_fill.cpp.

                       {
     // deleting contours, if any
     for (IntegerContour2D* contour : contours)
         delete contour;
     contours.clear();
 }

Member Function Documentation

◆ getInput()

const AbstractBitmap* Beatmup::FloodFill::getInput ( ) const

inline

Returns input bitmap (null if not set yet)

Definition at line 73 of file flood_fill.h.

73 { return input; }

◆ getOutput()

const AbstractBitmap* Beatmup::FloodFill::getOutput ( ) const

inline

Returns output bitmap (null if not set yet)

Definition at line 78 of file flood_fill.h.

78 { return output; }

◆ getBounds()

IntRectangle Beatmup::FloodFill::getBounds ( ) const

inline

Returns bounding box of the computed mask.

Definition at line 83 of file flood_fill.h.

83 { return bounds; }

◆ getContourCount()

int Beatmup::FloodFill::getContourCount ( ) const

inline

Returns number of detected contours.

Definition at line 88 of file flood_fill.h.

88 { return contours.size(); }

◆ getContour()

const IntegerContour2D & FloodFill::getContour ( int contourIndex ) const

Returns a contour by index if computeContours was true, throws an exception otherwise.

Definition at line 173 of file flood_fill.cpp.

                                                                     {
     RuntimeError::check(contourIndex >= 0 && contourIndex < contours.size(),
         "Contour index is out of range. Contours computation may have been disabled.");
     return *contours[contourIndex];
 }

◆ setInput()

void FloodFill::setInput ( AbstractBitmap * inputBitmap )

Sets the input bitmap.

Definition at line 41 of file flood_fill.cpp.

                                                     {
     this->input = inputBitmap;
 }

◆ setOutput()

void FloodFill::setOutput ( AbstractBitmap * mask )

Specifies the bitmap to put the resulting mask to.

Definition at line 46 of file flood_fill.cpp.

                                               {
     this->output = mask;
 }

◆ setMaskPos()

void FloodFill::setMaskPos ( const IntPoint & pos )

Specifies left-top corner position of the mask to compute inside the input bitmap.

Definition at line 51 of file flood_fill.cpp.

                                               {
     this->maskPos = pos;
 }

◆ setSeeds() [1/2]

void FloodFill::setSeeds	(	const IntPoint	seeds[],
		int	seedCount
	)

Specifies a set of seeds (starting points)

Definition at line 56 of file flood_fill.cpp.

                                                               {
     this->seeds.clear();
     for (int n = 0; n < seedCount; n++)
         this->seeds.push_back(seeds[n]);
 }

◆ setSeeds() [2/2]

void FloodFill::setSeeds	(	const int	seedsXY[],
		int	seedCount
	)

Definition at line 63 of file flood_fill.cpp.

                                                            {
     this->seeds.clear();
     for (int n = 0; n < seedCount; n++)
         this->seeds.push_back(IntPoint(seedsXY[2*n], seedsXY[2*n+1]));
 }

◆ setTolerance()

void FloodFill::setTolerance ( float tolerance )

Sets the intensity tolerance threshold used to decide on similarity of neighboring pixels.

Definition at line 161 of file flood_fill.cpp.

                                             {
     this->tolerance = tolerance;
 }

◆ getTolerance()

float Beatmup::FloodFill::getTolerance ( ) const

inline

Returns yjr intensity tolerance threshold.

Definition at line 124 of file flood_fill.h.

124 { return tolerance; };

◆ setBorderPostprocessing()

void FloodFill::setBorderPostprocessing	(	BorderMorphology	operation,
		float	holdRadius,
		float	releaseRadius
	)

Specifies a morphological operation to apply to the mask border.

Parameters

operation	A postprocessing operation
holdRadius	Erosion/dilation hold radius (output values set to 1)
releaseRadius	Erosion/dilation radius of transition from 1 to 0

Definition at line 166 of file flood_fill.cpp.

                                                                                                          {
     borderMorphology = operation;
     borderHold = std::max(0.0f, holdRadius);
     borderRelease = std::max(borderHold, releaseRadius);
 }

◆ setComputeContours()

void FloodFill::setComputeContours ( bool compute )

Enables or disables contours computation.

Definition at line 70 of file flood_fill.cpp.

                                                {
     this->computeContours = compute;
 }

◆ getMaxThreads()

ThreadIndex FloodFill::getMaxThreads ( ) const

virtual

Gives the upper limint on the number of threads the task may be performed by.

The actual number of threads running a specific task may be less or equal to the returned value, depending on the number of workers in ThreadPool running the task.

Reimplemented from Beatmup::AbstractTask.

Definition at line 75 of file flood_fill.cpp.

                                            {
     return validThreadCount((int)seeds.size());
 }

◆ process()

bool FloodFill::process ( TaskThread & thread )

finalvirtual

Executes the task on CPU within a given thread.

Generally called by multiple threads.

Parameters

thread associated task execution context

Returns: true if the execution is finished correctly, false otherwise

Implements Beatmup::AbstractTask.

Definition at line 80 of file flood_fill.cpp.

                                           {
     std::vector<IntPoint> border;
     border.reserve((output->getWidth() + output->getHeight()) * 2);
  
     std::vector<IntegerContour2D*> myContours;
     IntRectangle bounds;
     bounds.a = bounds.b = seeds[thread.currentThread()];
  
     for (int n = thread.currentThread(); n < seeds.size(); n += thread.numThreads())
         if (!thread.isTaskAborted()) {
             IntPoint seed = seeds[n];
             if (seed.x >= maskPos.x && seed.y >= maskPos.y && seed.x < maskPos.x + output->getWidth() && seed.y < maskPos.x + output->getHeight()) {
                 BitmapProcessing::pipelineWithMaskOutput<Kernels::FillRegion>(*input, *output, maskPos, seed, tolerance, border, bounds);
             }
         }
  
     // compute contours
     if (!thread.isTaskAborted())
         if (computeContours) {
             BinaryMaskWriter writer(*ignoredSeeds);
             IntegerContour2D::computeBoundary(myContours, *output, border, writer, 0);
         }
  
     if (!thread.isTaskAborted())
         switch (borderMorphology) {
         case DILATE:
             BitmapProcessing::writeToMask<Kernels::CircularDilatation>(*output, border, 255, borderHold, borderRelease);
             bounds.grow((int) ceilf(borderHold + borderRelease));
             bounds.limit(output->getSize().closedRectangle());
             break;
         case ERODE:
             BitmapProcessing::writeToMask<Kernels::CircularErosion>(*output, border, 255, borderHold, borderRelease);
             bounds.grow(-(int) floorf(borderHold));
             break;
         default: break;
         }
  
     // updating bounds and merging contours
     {
         std::lock_guard<std::mutex> lock(access);
         if (bounds.a.x < this->bounds.a.x) this->bounds.a.x = bounds.a.x;
         if (bounds.a.y < this->bounds.a.y) this->bounds.a.y = bounds.a.y;
         if (bounds.b.x > this->bounds.b.x) this->bounds.b.x = bounds.b.x;
         if (bounds.b.y > this->bounds.b.y) this->bounds.b.y = bounds.b.y;
  
         if (computeContours) {
             contours.reserve(contours.size() + myContours.size());
             for (auto contour : myContours)
                 contours.push_back(contour);
         }
     }
  
     return true;
 }

◆ beforeProcessing()

void FloodFill::beforeProcessing	(	ThreadIndex	threadCount,
		ProcessingTarget	target,
		GraphicPipeline *	gpu
	)

finalvirtual

Instruction called before the task is executed.

Parameters

threadCount	Number of threads used to perform the task
target	Device used to perform the task
gpu	A graphic pipeline instance; may be null.

Reimplemented from Beatmup::AbstractTask.

Definition at line 136 of file flood_fill.cpp.

                                                                                                        {
     NullTaskInput::check(input, "input bitmap");
     NullTaskInput::check(output, "output bitmap");
     lock<ProcessingTarget::CPU>(gpu, input, output);
     for (IntegerContour2D* contour : contours)
         delete contour;
     contours.clear();
     if (computeContours) {
         ignoredSeeds = new InternalBitmap(input->getContext(), PixelFormat::BinaryMask, output->getWidth(), output->getHeight());
         writeLock(gpu, ignoredSeeds,  ProcessingTarget::CPU);
         std::memset(ignoredSeeds->getData(0, 0), 0, ignoredSeeds->getMemorySize());
     }
     bounds.a = bounds.b = seeds[0];
 }

◆ afterProcessing()

void FloodFill::afterProcessing	(	ThreadIndex	threadCount,
		GraphicPipeline *	gpu,
		bool	aborted
	)

finalvirtual

Instruction called after the task is executed.

Parameters

threadCount	Number of threads used to perform the task
gpu	GPU to be used to execute the task; may be null.
aborted	`true` if the task was aborted

Reimplemented from Beatmup::AbstractTask.

Definition at line 152 of file flood_fill.cpp.

                                                                                            {
     unlock(input, output);
     if (computeContours) {
         unlock(ignoredSeeds);
         delete ignoredSeeds;
     }
 }

Member Data Documentation

◆ input

AbstractBitmap* Beatmup::FloodFill::input

protected

input bitmap

Definition at line 49 of file flood_fill.h.

◆ output

AbstractBitmap * Beatmup::FloodFill::output

protected

resulting mask

Definition at line 50 of file flood_fill.h.

◆ ignoredSeeds

AbstractBitmap * Beatmup::FloodFill::ignoredSeeds

protected

1-bit bitmap storing flags marking used pixels

Definition at line 51 of file flood_fill.h.

◆ maskPos

IntPoint Beatmup::FloodFill::maskPos

protected

left-top corner of the mask to compute over the input bitmap

Definition at line 53 of file flood_fill.h.

◆ bounds

IntRectangle Beatmup::FloodFill::bounds

protected

mask bounds

Definition at line 54 of file flood_fill.h.

◆ access

std::mutex Beatmup::FloodFill::access

protected

access control assuring internal thread safety

Definition at line 55 of file flood_fill.h.

◆ seeds

std::vector<IntPoint> Beatmup::FloodFill::seeds

protected

set of starting points (seed points)

Definition at line 56 of file flood_fill.h.

◆ contours

std::vector<IntegerContour2D*> Beatmup::FloodFill::contours

protected

contours to store borders for each seed

Definition at line 57 of file flood_fill.h.

◆ borderMorphology

BorderMorphology Beatmup::FloodFill::borderMorphology

protected

border morphological postprocessing

Definition at line 58 of file flood_fill.h.

◆ tolerance

float Beatmup::FloodFill::tolerance

protected

intensity tolerance value

Definition at line 60 of file flood_fill.h.

◆ borderHold

float Beatmup::FloodFill::borderHold

protected

Definition at line 62 of file flood_fill.h.

◆ borderRelease

float Beatmup::FloodFill::borderRelease

protected

Definition at line 63 of file flood_fill.h.

◆ computeContours

bool Beatmup::FloodFill::computeContours

protected

if true, border contours will be computed per each seed

Definition at line 64 of file flood_fill.h.

The documentation for this class was generated from the following files:

core/masking/flood_fill.h
core/masking/flood_fill.cpp

Public Types

Public Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ BorderMorphology

Constructor & Destructor Documentation

◆ FloodFill()

◆ ~FloodFill()

Member Function Documentation

◆ getInput()

◆ getOutput()

◆ getBounds()

◆ getContourCount()

◆ getContour()

◆ setInput()

◆ setOutput()

◆ setMaskPos()

◆ setSeeds() [1/2]

◆ setSeeds() [2/2]

◆ setTolerance()

◆ getTolerance()

◆ setBorderPostprocessing()

◆ setComputeContours()

◆ getMaxThreads()

◆ process()

◆ beforeProcessing()

◆ afterProcessing()

Member Data Documentation

◆ input

◆ output

◆ ignoredSeeds

◆ maskPos

◆ bounds

◆ access

◆ seeds

◆ contours

◆ borderMorphology

◆ tolerance

◆ borderHold

◆ borderRelease

◆ computeContours