Вернуться к разделу "Реализация проекта BookScanLib".
Как уже говорилось в пункте 6. FreeImage-функции поворота растра, функция поворота растра FreeImage_RotateClassic обладает некоторыми недостатками, из-за которых она непригодна к прямому использованию в проекте BookScanLib.
Я подкорректировал функцию FreeImage_RotateClassic с целью устранения этих недостатков. Новая функция получила рабочее название BSL_RotateClassic.
Вот список добавлений/исправлений, внесённых в эту новую функцию:
Таким образом, функция BSL_RotateClassic - это готовый к использованию алгоритм поворота на произвольный угол практически любого изображения в формате TIF - чёрно-белого, серого или цветного. В том числе в режиме сжатия CCIT FAX G4 или LZW (JPG тоже вроде бы можно). Поворот пока не предусмотрен для изображений в формате GIF и для 4-битных изображений - в случае необходимости это также будет сделано.
Я написал простейшую консольную программу для демонстрации работы функции BSL_RotateClassic. На входе она принимает имя графического файла через командную строку и значение угла в градусах, на который нужно повернуть изображение из этого файла. Угол может принимать нецелые значения - для отделения дробной части используется точка. Дробная часть может иметь любое количество знаков после запятой.
Всё необходимое для тестирования этой программы (компиляционный проект, готовый экзешник, файл-пример и bat-файлы для тестирования программы) я оформил в небольшой пакет:
Скачать пакет bsl_rot (81 КБ)
(Для работы программы требуется 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
// ==========================================================
// Bitmap rotation by means of 3 shears.
// Demo listing (e.g. not full for the simplicity - see the "BSL_ClassicRotate.cpp" for the details)
#include "FreeImage.h"
#include "Utilities.h"
#define ROTATE_PI double (3.1415926535897932384626433832795)
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Prototypes definition
static void HorizontalSkew(FIBITMAP *src, FIBITMAP *dst, int row, int iOffset, double dWeight, int conv);
static void VerticalSkew(FIBITMAP *src, FIBITMAP *dst, int col, int iOffset, double dWeight);
/* These functions are not shown in this code listing - just for the simplicity
static FIBITMAP* Rotate90(FIBITMAP *src);
static FIBITMAP* Rotate180(FIBITMAP *src);
static FIBITMAP* Rotate270(FIBITMAP *src);
*/
static FIBITMAP* Rotate45(FIBITMAP *src, double dAngle);
static FIBITMAP* RotateAny(FIBITMAP *src, double dAngle);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
Skews a row horizontally (with filtered weights).
Limited to 45 degree skewing only. Filters two adjacent pixels.
@param src Pointer to source image to rotate
@param dst Pointer to destination image
@param row Row index
@param iOffset Skew offset
@param dWeight Relative weight of right pixel
*/
static void
HorizontalSkew(FIBITMAP *src, FIBITMAP *dst, int row, int iOffset, BYTE Weight, int bg_color, int conv)
{
int i, j;
int iXPos;
int src_width = FreeImage_GetWidth(src);
int dst_width = FreeImage_GetWidth(dst);
switch(FreeImage_GetBPP(src)) {
case 8:
case 24:
case 32:
{
if (!conv) {
BYTE pxlSrc[4], pxlLeft[4], pxlOldLeft[4]; // 4 = 32-bit max
// calculate the number of bytes per pixel (1 for 8-bit, 3 for 24-bit or 4 for 32-bit)
int bytespp = FreeImage_GetLine(src) / FreeImage_GetWidth(src);
BYTE *src_bits = FreeImage_GetScanLine(src, row);
BYTE *dst_bits = FreeImage_GetScanLine(dst, row);
memset(&pxlOldLeft[0], 0, bytespp);
for(i = 0; i < src_width; i++)
{
// loop through row pixels
memcpy(&pxlSrc[0], src_bits, bytespp);
// calculate weights
for(j = 0; j < bytespp; j++)
pxlLeft[j] = BYTE(((WORD)pxlSrc[j] * Weight) / 256);
// check boundaries
iXPos = i + iOffset;
if((iXPos >= 0) && (iXPos < dst_width))
{
// update left over on source
for(j = 0; j < bytespp; j++)
pxlSrc[j] = pxlSrc[j] - (pxlLeft[j] - pxlOldLeft[j]);
memcpy(&dst_bits[iXPos*bytespp], &pxlSrc[0], bytespp);
}
// save leftover for next pixel in scan
memcpy(&pxlOldLeft[0], &pxlLeft[0], bytespp);
// next pixel in scan
src_bits += bytespp;
}
if(iOffset >= 0)
memset(dst_bits, bg_color, (iOffset+1) * bytespp);
// go to rightmost point of skew
iXPos = src_width + iOffset;
if(iXPos < dst_width)
{
dst_bits = FreeImage_GetScanLine(dst, row) + iXPos * bytespp;
// If still in image bounds, put leftovers there
memcpy(dst_bits, &pxlOldLeft[0], bytespp);
// clear to the right of the skewed line with background
dst_bits += bytespp;
memset(dst_bits - bytespp, bg_color, bytespp * (dst_width - iXPos + 1));
}
}
// *****************************************************************************************
// start of the bulk of the new code (not all the new code is here of course)
else // if conv...
{
// converting 8-bit image to 1-bit image
BYTE pxlSrc, pxlLeft, pxlOldLeft, T = 128;
int bytespp = 1;
BYTE *src_bits = FreeImage_GetScanLine(src, row);
BYTE *dst_bits = FreeImage_GetScanLine(dst, row);
BYTE wp = (FreeImage_GetColorType(src) == FIC_MINISWHITE) ? 255 : 0;
memset(&pxlOldLeft, 0, bytespp);
for(i = 0; i < src_width; i++)
{
// loop through row pixels
memcpy(&pxlSrc, src_bits, bytespp);
// calculate weights
pxlLeft = BYTE(((WORD)pxlSrc * Weight) / 256);
// check boundaries
iXPos = i + iOffset;
if((iXPos >= 0) && (iXPos < dst_width))
{
// update left over on source
pxlSrc = pxlSrc - (pxlLeft - pxlOldLeft);
if(wp^((pxlSrc < T)? 0 : 255))
{
// Set bit(x, y) to 0
dst_bits[iXPos >> 3] &= (0xFF7F >> (iXPos & 0x7));
} else {
// Set bit(x, y) to 1
dst_bits[iXPos >> 3] |= (0x80 >> (iXPos & 0x7));
}
}
// save leftover for next pixel in scan
memcpy(&pxlOldLeft, &pxlLeft, bytespp);
// next pixel in scan
src_bits += bytespp;
}
if(iOffset >= 0)
for(i = 0; i < (iOffset+1); i++)
// Set bit(x, y) to 0
dst_bits[i >> 3] &= (0xFF7F >> (i & 0x7));
}
}
break;
case 1:
{
BYTE pxlSrc, pxlLeft, pxlOldLeft;
int bytespp = 1; // preparing to force 1-bit dib to 8-bit dib...
unsigned x = 0; // pix num incrementation
BYTE wp = (FreeImage_GetColorType(src) == FIC_MINISWHITE) ? 255 : 0;
BYTE *src_bits = FreeImage_GetScanLine(src, row);
//Returns a pointer to the start of the given scanline in the bitmap’s data-bits.
BYTE *dst_bits = FreeImage_GetScanLine(dst, row);
memset(&pxlOldLeft, 0, bytespp);
for(i = 0; i < src_width; i++)
{
// loop through row pixels
pxlSrc = wp^((src_bits[x >> 3] & (0x80 >> (x & 0x07))) != 0 ? 255 : 0);
//forcing 1-bit pixel to 8-bit pixel and invert it case FIC_MINISWHITE
// calculate weights
pxlLeft = BYTE(((WORD)pxlSrc * Weight) / 256);
// check boundaries
iXPos = i + iOffset;
if((iXPos >= 0) && (iXPos < dst_width))
{
// update left over on source
pxlSrc = pxlSrc - (pxlLeft - pxlOldLeft);
memcpy(&dst_bits[iXPos*bytespp], &pxlSrc, bytespp);
}
// save leftover for next pixel in scan
memcpy(&pxlOldLeft, &pxlLeft, bytespp);
// next pixel in scan
x += bytespp;
}
if(iOffset >= 0)
memset(dst_bits, bg_color, (iOffset+1) * bytespp);
// go to rightmost point of skew
iXPos = src_width + iOffset;
if(iXPos < dst_width)
{
dst_bits = FreeImage_GetScanLine(dst, row) + iXPos * bytespp;
// If still in image bounds, put leftovers there
memcpy(dst_bits, &pxlOldLeft, bytespp);
// clear to the right of the skewed line with background
dst_bits += bytespp;
memset(dst_bits - bytespp, bg_color, bytespp * (dst_width - iXPos + 1));
}
}
break;
// end of the bulk of the new code
// *****************************************************************************************
}
}
/**
Skews a column vertically (with filtered weights).
Limited to 45 degree skewing only. Filters two adjacent pixels.
@param src Pointer to source image to rotate
@param dst Pointer to destination image
@param col Column index
@param iOffset Skew offset
@param dWeight Relative weight of upper pixel
*/
static void
VerticalSkew(FIBITMAP *src, FIBITMAP *dst, int col, int iOffset, BYTE Weight, int bg_color)
{
int i, j, iYPos;
int src_height = FreeImage_GetHeight(src);
int dst_height = FreeImage_GetHeight(dst);
switch(FreeImage_GetBPP(src)) {
case 8:
case 24:
case 32:
{
BYTE pxlSrc[4], pxlLeft[4], pxlOldLeft[4]; // 4 = 32-bit max
// calculate the number of bytes per pixel (1 for 8-bit, 3 for 24-bit or 4 for 32-bit)
int bytespp = FreeImage_GetLine(src) / FreeImage_GetWidth(src);
unsigned src_pitch = FreeImage_GetPitch(src);
unsigned dst_pitch = FreeImage_GetPitch(dst);
unsigned index = col * bytespp;
BYTE *src_bits = FreeImage_GetBits(src) + index;
BYTE *dst_bits = FreeImage_GetBits(dst) + index;
memset(&pxlOldLeft[0], 0, bytespp);
for(i = 0; i < src_height; i++)
{
// loop through column pixels
memcpy(&pxlSrc[0], src_bits, bytespp);
// calculate weights
for(j = 0; j < bytespp; j++)
pxlLeft[j] = BYTE(((WORD)pxlSrc[j] * Weight) / 256);
// check boundaries
iYPos = i + iOffset;
if((iYPos >= 0) && (iYPos < dst_height))
{
// update left over on source
for(j = 0; j < bytespp; j++)
pxlSrc[j] = pxlSrc[j] - (pxlLeft[j] - pxlOldLeft[j]);
dst_bits = FreeImage_GetScanLine(dst, iYPos) + index;
memcpy(dst_bits, &pxlSrc[0], bytespp);
}
// save leftover for next pixel in scan
memcpy(&pxlOldLeft[0], &pxlLeft[0], bytespp);
// next pixel in scan
src_bits += src_pitch;
}
dst_bits = FreeImage_GetBits(dst) + index;
for(i = 0; i <= iOffset; i++)
{
memset(dst_bits, bg_color, bytespp);
dst_bits += dst_pitch;
}
// go to bottom point of skew
iYPos = src_height + iOffset-1; // new
if(iYPos < dst_height)
{
dst_bits = FreeImage_GetScanLine(dst, iYPos) + index;
// clear below skewed line with background
while(++iYPos < dst_height)
{
dst_bits += dst_pitch;
memset(dst_bits, bg_color, bytespp);
}
}
}
break;
}
}
// *****************************
// Here are not shown the ortho-rotation functions... (they did not change since the FreeImage_RotateClassic)
// *****************************
/**
Rotates an image by a given degree in range [-45 .. +45] (counter clockwise)
using the 3-shear technique.
@param src Pointer to source image to rotate
@param dAngle Rotation angle
@return Returns a pointer to a newly allocated rotated image if successful, returns NULL otherwise
*/
static FIBITMAP*
Rotate45(FIBITMAP *src, double dAngle) {
int u;
int bpp_src = FreeImage_GetBPP(src);
int bpp;
int bg_color = 255; // white color - for greyscale and color (probably depends on the chosen palette)
// new
if (bpp_src == 1) bpp = 8;
else bpp = bpp_src;
// end of new
double dRadAngle = dAngle * ROTATE_PI / double(180); // Angle in radians
double dSinE = sin(dRadAngle);
double dTan = tan(dRadAngle / 2);
int src_width = FreeImage_GetWidth(src);
int src_height = FreeImage_GetHeight(src);
// Calc first shear (horizontal) destination image dimensions
int width_1 = src_width + int((double)src_height * fabs(dTan) + 0.5);
int height_1 = src_height;
/******* Perform 1st shear (horizontal) ******/
// Allocate image for 1st shear
FIBITMAP *dst1 = FreeImage_Allocate(width_1, height_1, bpp);
if(NULL == dst1) {
return NULL;
}
for(u = 0; u < height_1; u++) {
double dShear;
if(dTan >= 0) {
// Positive angle
dShear = (double(u) + 0.5) * dTan;
}
else {
// Negative angle
dShear = (double(int(u) - height_1) + 0.5) * dTan;
}
int iShear = int(floor(dShear));
HorizontalSkew(src, dst1, u, iShear, BYTE(255 * (dShear - double(iShear)) + 1), bg_color, 0);
}
/******* Perform 2nd shear (vertical) ******/
// Calc 2nd shear (vertical) destination image dimensions
int width_2 = width_1;
int height_2 = int((double)src_width * fabs(dSinE) + (double)src_height * cos(dRadAngle) + 0.5) + 1;
// Allocate image for 2nd shear
FIBITMAP *dst2 = FreeImage_Allocate(width_2, height_2, bpp);
if(NULL == dst2) {
FreeImage_Unload(dst1);
return NULL;
}
double dOffset; // Variable skew offset
if(dSinE > 0) {
// Positive angle
dOffset = double(src_width - 1) * dSinE;
}
else {
// Negative angle
dOffset = -dSinE * double (src_width - width_2);
}
for(u = 0; u < width_2; u++, dOffset -= dSinE) {
int iShear = int(floor(dOffset));
VerticalSkew(dst1, dst2, u, iShear, BYTE(255 * (dOffset - double(iShear)) + 1), bg_color);
}
/******* Perform 3rd shear (horizontal) ******/
// Free result of 1st shear
FreeImage_Unload(dst1);
// Calc 3rd shear (horizontal) destination image dimensions
int width_3 = int(double(src_height) * fabs(dSinE) + double(src_width) * cos(dRadAngle) + 0.5) + 1;
int height_3 = height_2;
// new
int conv = 0;
if (bpp_src == 1) {bpp = 1; conv = 1;}
// end of new
// Allocate image for 3rd shear
FIBITMAP *dst3 = FreeImage_Allocate(width_3, height_3, bpp);
if(NULL == dst3) {
FreeImage_Unload(dst2);
return NULL;
}
if(dSinE >= 0) {
// Positive angle
dOffset = double(src_width - 1) * dSinE * -dTan;
}
else {
// Negative angle
dOffset = dTan * (double(src_width - 1) * -dSinE + double(1 - height_3));
}
for(u = 0; u < height_3; u++, dOffset += dTan) {
int iShear = int(floor(dOffset));
HorizontalSkew(dst2, dst3, u, iShear, BYTE(255 * (dOffset - double (iShear)) + 1), bg_color, conv);
}
// Free result of 2nd shear
FreeImage_Unload(dst2);
// Return result of 3rd shear
return dst3;
}
// *****************************
/* static FIBITMAP* RotateAny(FIBITMAP *src, double dAngle) {
... // the uninteresting stuff is not shown here
return Rotate45(src, dAngle); }
*/
// *****************************
FIBITMAP *DLL_CALLCONV
BSL_RotateClassic(FIBITMAP *dib, double angle) {
if(!dib) return NULL;
if(0 == angle) {
return FreeImage_Clone(dib);
}
// DIB are stored upside down ...
angle *= -1;
try {
int bpp = FreeImage_GetBPP(dib);
if(bpp == 1) {
// perform the rotation
FIBITMAP *dst = RotateAny(dib, angle);
if(!dst) throw(1);
// build a monochrome palette
RGBQUAD *dst_pal = FreeImage_GetPalette(dst);
if(FreeImage_GetColorType(dib) == FIC_MINISBLACK)
{
dst_pal[0].rgbRed = dst_pal[0].rgbGreen = dst_pal[0].rgbBlue = 0;
dst_pal[1].rgbRed = dst_pal[1].rgbGreen = dst_pal[1].rgbBlue = 255;
}
else if(FreeImage_GetColorType(dib) == FIC_MINISWHITE)
{
dst_pal[0].rgbRed = dst_pal[0].rgbGreen = dst_pal[0].rgbBlue = 255;
dst_pal[1].rgbRed = dst_pal[1].rgbGreen = dst_pal[1].rgbBlue = 0;
}
// Copying the DPI...
FreeImage_SetDotsPerMeterX(dst, FreeImage_GetDotsPerMeterX(dib));
FreeImage_SetDotsPerMeterY(dst, FreeImage_GetDotsPerMeterY(dib));
return dst;
}
if((bpp == 8) || (bpp == 24) || (bpp == 32)) {
FIBITMAP *dst = RotateAny(dib, angle);
if(!dst) throw(1);
if(bpp == 8)
{
// copy original palette to rotated bitmap
RGBQUAD *src_pal = FreeImage_GetPalette(dib);
RGBQUAD *dst_pal = FreeImage_GetPalette(dst);
memcpy(&dst_pal[0], &src_pal[0], 256 * sizeof(RGBQUAD));
}
// Copying the DPI...
FreeImage_SetDotsPerMeterX(dst, FreeImage_GetDotsPerMeterX(dib));
FreeImage_SetDotsPerMeterY(dst, FreeImage_GetDotsPerMeterY(dib));
return dst;
}
} catch(int) {
return NULL;
}
return NULL;
}
|
Примечание: Здесь не показан "управляющий" исходный код для функции BSL_RotateClassic. В принципе, он практически совпадает с исходниками, описанными в пункте 6. FreeImage-функции поворота растра.
Несмотря на устрашающе длинный листинг, этот алгоритм достаточно постижим. Хотя я по-прежнему даже и не пытался полностью разобраться в его теоретической части :) - что однако не помешало мне переделать исходную функцию в нужной степени.
Основную идею этого алгоритма можно почерпнуть в его научном описании. Всё построено в основном на обычной школьной геометрии и на знании синусов-косинусов.
В этом алгоритме процедура поворота растра на произвольный угол подменяется 3-мя процедурами взаимно-перпендикулярных "сдвигов с деформацией" этого растра. Для понимания всего это нужно взглянуть на картиночку "Figure 1" из описания алгоритма. Если нам, скажем, нужно крутануть треугольничек против часовой стрелки на некоторый произвольный угол, то мы его не поворачиваем на самом деле - а взамен "тащим" его "влево -> вниз -> вправо". Получается как раз 3 сдвига (т.е. "shear" - сдвиг (англ.), причём на каждом таком сдвиге наш треугольничек деформируется хитрым образом и в строго в определённой степени (по формуле). В результате за 3 таких сдвига все эти деформации полностью взаимно компенсируются - и на выходе мы получаем уже "повёрнутый" треугольничек.
Если бы мы стали вращать треугольничек обычным образом - то нам пришлось бы для каждой его точки вычислять новое "повёрнутое" положение - по формуле с синусами-косинусами. А так лишь для каждой строки пикселей треугольничка вычисляется общее значение сдвига - с участием синусов-косинусов (правда, трижды). Видимо, в результате получается некая экономия вычислений при повороте - а значит, поворот происходит быстрее.
Основная цель, которую я преследовал, модифицируя старую функцию поворота - приспособить алгоритм для вращения на произвольный угол чёрно-белых изображений (а не только серых и цветных). Этой цели я достиг наиболее простым способом: в процессе первого сдвига чёрно-белые пиксели изображения автоматически и органично "на лету" преобразуются в серые, и во время второго сдвига изображение "сдвигается" уже по-старому - как серое, а во время третьего сдвига наоборот - серые пиксели изображения точно также автоматически преобразуются в чёрно-белые - по заданному порогу (я выбрал наугад 128 - т.е. посерёдке шкалы цветов 0 - 255).
Все эти модификации были сделаны мною исключительно при помощи простейшего здравого смысла и путём использования кусков других функций из библиотеки FreeImage. То есть никаких именно математических знаний пока не потребовалось - а только базовое знание языка СИ. Потребовалось, однако, разобраться в общих принципах структуры Tif-файла - там есть т.н. "заголовок" (где и хранится значение DPI), и некая "палетка" цветов, а сами пиксели - это не цвета непосредственно оказались, а лишь карта с номерами цветов из палетки. Всё это нетрудно было понять, разглядывая реализации разных готовых функций из библиотеки FreeImage (что надёжней, чем, скажем, вычитать всё это из некоей книги).
Я надеюсь (с некоторыми основаниями), что при повороте чёрно-белого изображения (например, скан страницы книги) посредством этого алгоритма возникающие артефакты (т.е. искажения) будут минимальны. В принципе, каким способом ни вращай чёрно-белую картинку на произвольный угол - артефакты неизбежны (в отличие от серой и цветной картинки) - так как надо округлять синусы-косинусы либо в чёрное, либо в белое (а не подбирать один из многочисленных серых или цветных цветов, что дало бы бОльшую точность). В случае чего можно попробовать ещё поиграться со значением порога бинаризации - используемого во время 3-го сдвига (для этого нужно будет залезть в исходники, т.к. я этот порог не стал выводить как параметр функции).