Вернуться к разделу "Реализация проекта BookScanLib".


10. Программная реализация алгоритма Normal Despeckle

Как известно теперь, любой алгоритм Despeckle работает только с чёрно-белыми изображениями. Такова его природа. На серые и цветные изображения он не оказывает никакого эффекта (или размывает их неприемлемым образом).

В прошлом пункте 9. Программная реализация базового алгоритма Despeckle мы создали канонический алгоритм Despeckle на базе медианного фильтра.

Однако, он оказался слишком медленным. В этом пункте мы сделаем более "быструю" реализацию алгоритма Despeckle. Его "убыстрение" будет достигнуто за счёт следующих моментов:

1. Использование вместо медианного фильтра (Median filter) усредняющего фильтра (Mean filter). Устредняющий фильтр - это вырожденный медианный фильтр для случая чёрно-белых изображений, поэтому алгоритм от этого нисколько не ухудшится.

2. Проходя в цикле по всем пикселям изображения, мы будем сразу же пропускать все белые пиксели. Это, конечно же, серьёзное отклонение от стандартной реализации алгоритма Despeckle. Ведь возможны ситуации, когда в рабочем окошке 3х3 пикселя в центре - белый пиксель, а вокруг него - чёрные. Эти случаи мы будем игнорировать (что не очень хорошо и правильно).

Зато это радикально, в десятки раз, увеличивает скорость работы алгоритма. При этом его качество падает незначительно (по сравнению с канонической "правильной" реализацией), а вычищающая способность даже увеличивается (правда, контуры буквы становятся чуть более "изъеденными").

Как оказалось, именно так работает алгоритм Normal Despeckle в СканКромсаторе. Это выяснилось случайно - одна и та же картинка, обработанная данным алгоритмом, и алгоритмом Normal Despeckle в СканКромсаторе, получилась абсолютно идентичной. Размер апертуры Normal Despeckle в СканКромсаторе оказался равным 3х3.

К слову, в СканКромсаторе ещё есть Fine Despeckle - это "геометрический" Despeckle, который удаляет в заданной области все объекты меньше заданного размера, и Safe Despeckle - который строит контуры букв и чистит за их пределами.

Я написал простейшую консольную программу для демонстрации работы медианного алгоритма Normal Despeckle. На входе она принимает имя графического файла через командную строку и размер обрабатывающего окна (т.н. апертура), а на выходе выдаёт этот же файл, обработанный алгоритмом Normal Despeckle.

Всё необходимое для тестирования этой программы (компиляционный проект, готовый экзешник, файл-пример и bat-файлы для тестирования программы) я оформил в небольшой пакет:

Скачать пакет despec2 (64 КБ)

(Для работы программы требуется FreeImage dll-библиотека из пакета FreeImage DLL v3.9.2 - см. статью 1. Знакомство с FreeImage).

Рассмотрим исходные коды этой программы:


//	This program is free software; you can redistribute it and/or modify
//	it under the terms of the GNU General Public License as published by
//	the Free Software Foundation; either version 2 of the License, or
//	(at your option) any later version.
//
//	This program 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 General Public License for more details.
//
//	You should have received a copy of the GNU General Public License
//	along with this program; if not, write to the Free Software
//	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//	http://www.gnu.org/copyleft/gpl.html

//	Copyright (C) 2007-2008:
//	monday2000	monday2000@yandex.ru
// ==========================================================
// Simple despeckle mean filter (for BW only) based on the FreeImage library
//
// This code is taken from the CxImage Library at http://www.xdp.it/cximage.htm
// and adapted for the FreeImage Library
//
#include <stdio.h>
#include <stdlib.h>

#include "FreeImage.h"

// ----------------------------------------------------------

BOOL AddPixel(BYTE *bits, unsigned bpp, unsigned x, BYTE *value)
{	// this function is simplified from FreeImage_GetPixelIndex
	switch(bpp)
	{
	case 1:
		*value += (bits[x >> 3] & (0x80 >> (x & 0x07))) != 0;
		break;

	default:
		return FALSE;
	}
	
	return TRUE;
}

// ----------------------------------------------------------

BOOL SetPixel(BYTE *bits, unsigned bpp, unsigned x, BYTE *value)
{   // this function is simplified from FreeImage_SetPixelIndex
	switch(bpp)
	{
	case 1:
		*value ? bits[x >> 3] |= (0x80 >> (x & 0x7)) : bits[x >> 3] &= (0xFF7F >> (x & 0x7));
		break;
	default:
		return FALSE;
	}
	
	return TRUE;
}

// ----------------------------------------------------------

/**
FreeImage error handler
@param fif Format / Plugin responsible for the error 
@param message Error message
*/
void FreeImageErrorHandler(FREE_IMAGE_FORMAT fif, const char *message) {
	printf("\n*** "); 
	printf("%s Format\n", FreeImage_GetFormatFromFIF(fif));
	printf(message);
	printf(" ***\n");
}

// ----------------------------------------------------------

/** Generic image loader

  @param lpszPathName Pointer to the full file name
  @param flag Optional load flag constant
  @return Returns the loaded dib if successful, returns NULL otherwise
*/

FIBITMAP* GenericLoader(const char* lpszPathName, int flag)
{	
	FREE_IMAGE_FORMAT fif = FIF_UNKNOWN;
	// check the file signature and deduce its format
	// (the second argument is currently not used by FreeImage)
	
	fif = FreeImage_GetFileType(lpszPathName, 0);
	
	if(fif == FIF_UNKNOWN)
	{
		// no signature ?
		// try to guess the file format from the file extension
		fif = FreeImage_GetFIFFromFilename(lpszPathName);
	}
	
	// check that the plugin has reading capabilities ...
	if((fif != FIF_UNKNOWN) && FreeImage_FIFSupportsReading(fif))
	{
		// ok, let's load the file
		FIBITMAP *dib = FreeImage_Load(fif, lpszPathName, flag);
		
		// unless a bad file format, we are done !
		return dib;
	}
	
	return NULL;
}

// ----------------------------------------------------------

FIBITMAP *CxImage_Mean(FIBITMAP *dib, unsigned Ksize)
{	
	// Ksize is a square sliding aperture side size and it must be ONLY an odd value
	// greater than 1, e.g. 3, 5, 7, 9, 11, ...
	
	if (!dib) return false;
	
	FIBITMAP *tmp = FreeImage_Clone(dib);
	
	// FreeImage_Clone - makes an exact reproduction of an existing bitmap, including
	// metadata and attached profile if any
	
	if (!tmp) return false;
	
	// in this implementation we use only the BW-bitmaps - because despeckle 
	// does not produce any effect on non-BW images
	
	//---------------------------
	
	int k2 = Ksize/2;
	int kmax = Ksize-k2;
	int i,j,k;
	int mean = Ksize*Ksize/2;
	
	unsigned xmax,ymax, x1, y1;
	
	xmax = FreeImage_GetWidth(dib);
	
	ymax = FreeImage_GetHeight(dib);
	
	unsigned bpp = FreeImage_GetBPP(dib);
	
	unsigned pitch = FreeImage_GetPitch(dib);
	
	BYTE *bits = (BYTE*)FreeImage_GetBits(dib);	
	
	BYTE *bits_tmp = (BYTE*)FreeImage_GetBits(tmp);	
	
	BYTE val;
	
	//---------------------------
	
	for(unsigned y = 0; y < ymax; y++)
		
		for(unsigned x = 0; x < xmax; x++)
		{
			val = 0;
			
			if (!AddPixel(bits + pitch * y, bpp, x, &val)) return false;
			
			if (val < 1 ) continue; else val = 0;
			// check if this is not a background pixel
			
			for(k = -k2, i=0; k<kmax; k++)
				
				for(j = -k2; j<kmax; j++, i++)
				{
					x1 = x+j; y1 = y+k;
					
					if ((x1 < 0) || (y1 < 0) || (x1 > xmax) || (y1 > ymax))	continue;
					// if this is a border pixel
					
					if (!AddPixel(bits + pitch * y1, bpp, x1, &val)) return false;
				}
				
				if (val > mean) val = 1; else val = 0;
				
				SetPixel(bits_tmp + pitch * y, bpp, x, &val);
		}
		
		return tmp;
}

// ----------------------------------------------------------

int main(int argc, char *argv[]) {
	
	// call this ONLY when linking with FreeImage as a static library
#ifdef FREEIMAGE_LIB
	FreeImage_Initialise();
#endif // FREEIMAGE_LIB
	
	// initialize your own FreeImage error handler
	
	FreeImage_SetOutputMessage(FreeImageErrorHandler);
	
	if(argc != 3) {
		printf("Usage : despec2 <input file name> <aperture size>\n");
		return 0;
	}
	
	unsigned Ksize = atoi(argv[2]);
	
	FIBITMAP *dib = GenericLoader(argv[1], 0);
	
	if (dib)
	{		
		// bitmap successfully loaded!
		
		// despeckle the loaded image
		FIBITMAP *despeckled = CxImage_Mean(dib, Ksize);
		
		// save the despeckled bitmap
		const char *output_filename = "despeckled.tif";
		
		// first, check the output format from the file name or file extension
		FREE_IMAGE_FORMAT out_fif = FreeImage_GetFIFFromFilename(output_filename);
		
		if(out_fif != FIF_UNKNOWN)
		{
			// then save the file
			FreeImage_Save(out_fif, despeckled, output_filename, 0);
		}
		
		// free the loaded FIBITMAP
		FreeImage_Unload(dib);
		
		// free the loaded FIBITMAP
		FreeImage_Unload(despeckled);
		
	}
	
	// call this ONLY when linking with FreeImage as a static library
#ifdef FREEIMAGE_LIB
	FreeImage_DeInitialise();
#endif // FREEIMAGE_LIB
	
	return 0;
} 

Алгоритм очень прост: проходим окошком 3х3 пикселя (апертурой) в цикле по всем пикселям изображения. Белые пиксели сразу пропускаем и обрабатываем только чёрные. Складываем номера цветов 9 пикселей апертуры, делим пополам. Если результат больше половины полностью-чёрной апертуры - то ставим взамен текущего пикселя чёрный, если нет - то белый. Края изображения игнорируем.

Hosted by uCoz