## Saturday, February 13, 2016

### Octree color quantizer in Python

Some time ago I found interesting octree color quantization algorithm, previously often used in computer graphics (when devices can display only a limited number of colors), and nowadays mainly used in gif images.

I've implemented one of the most used algorithm of octree color quantization in Python. Here is a repository on github: https://github.com/delimitry/octree_color_quantizer

Original image (24 bit):

Result image (colors reduced to 8 bit):

Result image palette:

Algorithm:
Octree is a tree where each node has up to 8 children. Leaf node has no active children.
Each leaf node have a number of pixels with this color (pixel_count) and color value.

1) Addition of a new color to the octree.
Start at the level 0.
For example a pixel RGB color is (90, 13, 157). In binary it is (01011010, 01110001, 10011101).
The next level node index is calculated the following way:
Write in binary R, G and B bits, starting from MSB, for current level. So the index will be from 000 to 111 (binary), i.e. from 0 to 7 (decimal).
If the maximum depth of tree is less than 8, only first bits of color will matter.
Here is the image with first steps of addition the color:
If we have a tree with maximum depth of 8, eventually we will have the next indices:
The full tree with depth 8 after add the color (90, 113, 157):
If the next pixel color is again (90, 113, 157), the leaf node color R, G, B values will be increased by new color R, G, B values as well as the value of pixels with this color. And the color will be (180, 226, 314) and pixel_count will be 2:

2) Reduction
To make image color palette with for example 256 colors maximum, from palette with far more colors the tree leaves must be reduced.
The reduction of nodes:
As we have a sum of R, G and B values and the number of pixels with this color, we can add all leaves pixels count and color channels to parent node and make it a leaf node (we could not even remove it, because get leaves method will not go deeper if current node is leaf).
Reduction continues while leaves count it more than needed maximum colors (in our case 256).
The main disadvantage of this approach is that up to 8 leaves can be reduced from node and the palette could have only 248 colors (in worst case) instead of expected 256 colors.
As soon as we've got count of leaves less or equal needed maximum colors we can build a palette.

3) Palette building
Palette is filled with average colors, from each leaf. As each leaf has the number of pixels with color and color's sum of R, G and B values, average color could be received by dividing color channels by the number of pixels: palette_color = (color.R / pixel_count, color.G/ pixel_count,  color.B / pixel_count).

## Wednesday, February 3, 2016

### Installing tesseract for python on Ubuntu 15.10

Some time ago I've already written a tutorial how to install tesseract for python on Ubuntu 14.04.
And today I've struggled with the new challenges during the installation of tesseract and python-tesseract on Ubuntu 15.10. So here is my way to make it usable.

user@server:~\$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=15.10
DISTRIB_CODENAME=wily
DISTRIB_DESCRIPTION="Ubuntu 15.10"

Install packages
sudo apt-get install python-distutils-extra tesseract-ocr tesseract-ocr-eng libopencv-dev libtesseract-dev libleptonica-dev python-all-dev swig libcv-dev python-opencv python-numpy python-setuptools build-essential subversion git
sudo apt-get install autoconf automake libtool
sudo apt-get install libpng12-dev libjpeg62-dev libtiff4-dev zlib1g-dev

wget http://www.leptonica.com/source/leptonica-1.73.tar.gz
tar xvf leptonica-1.73.tar.gz

build it

cd leptonica-1.73
./configure
make
make install

wget https://github.com/tesseract-ocr/tesseract/archive/3.04.00.tar.gz

tar xvf 3.04.00.tar.gz
cd tesseract-3.04.00
./autogen.sh
./configure
make
sudo make install
sudo ldconfig

And test:

user@server:~\$ tesseract
Usage:
tesseract imagename|stdin outputbase|stdout [options...] [configfile...]

Check out `python-tesseract`

git clone https://bitbucket.org/3togo/python-tesseract.git

It's needed to update "baseapi_mini.h" file in ./python-tesseract/src/ folder:

....
class MutableIterator;
line: 85
class TessResultRenderer;
....

line 316:
//void SetImage(const Pix* pix);
void SetImage(Pix* pix);

line 477:
/*
bool ProcessPages(const char* filename,
const char* retry_config, int timeout_millisec,
STRING* text_out);
*/
bool ProcessPages(const char* filename,
const char* retry_config, int timeout_millisec,
TessResultRenderer* renderer);

line 493:
/*
bool ProcessPage(Pix* pix, int page_index, const char* filename,
const char* retry_config, int timeout_millisec,
STRING* text_out);
*/
bool ProcessPage(Pix* pix, int page_index, const char* filename,
const char* retry_config, int timeout_millisec,
TessResultRenderer* renderer);

It's needed to update "main.cpp" file in ./python-tesseract/src/ folder:

line: 15
#include "renderer.h"

line: 64
char* ProcessPagesWrapper(const char* image,tesseract::TessBaseAPI* api) {
const char *data = "";
tesseract::TessTextRenderer renderer(data);
api->ProcessPages(image, NULL, 0, &renderer);
return api->GetUTF8Text();
}

line: 73
char* ProcessPagesPix(const char* image,tesseract::TessBaseAPI* api) {
const char *data = "";
tesseract::TessTextRenderer renderer(data);
int page=0;
Pix *pix;
api->ProcessPage(pix, page, NULL, NULL, 0, &renderer);
free(pix->data);
free(pix->text);
return api->GetUTF8Text();
}

line: 86
char* ProcessPagesFileStream(const char* image,tesseract::TessBaseAPI* api) {
Pix *pix;
const char *data = "";
tesseract::TessTextRenderer renderer(data);
int page=0;
FILE *fp=fopen(image,"rb");
fclose(fp);
api->ProcessPage(pix, page, NULL, NULL, 0, &renderer);
free(pix->data);
free(pix->text);
return api->GetUTF8Text();
}

line 107:
char* ProcessPagesBuffer(char* buffer, int fileLen, tesseract::TessBaseAPI* api) {
FILE *stream;
stream=fmemopen((void*)buffer,fileLen,"rb");
if (stream == NULL) {
puts("cant't open stream using fmemopen");
return (char*)"Error";
}
Pix *pix;
int page=0;
const char *data = "";
tesseract::TessTextRenderer renderer(data);
if (stream != NULL)
fclose(stream);
api->ProcessPage(pix, page, NULL, NULL, 0, &renderer);
free(pix->data);
free(pix->text);
return api->GetUTF8Text();
}

and build it:

python setup.py clean
python setup.py build
sudo python setup.py install

After that try to run your python example.

If you'll get such error:
Error opening data file ./tessdata/eng.traineddata
Please make sure the TESSDATA_PREFIX environment variable is set to the parent directory of your "tessdata" directory.
Segmentation fault (core dumped)

You could fix it by patching "mainblk.cpp" file inside tesseract-3.04.00/ccutil/ folder the next way:

In the "mainblk.cpp" file code:

if (argv0 != NULL) {
} else {
if (getenv("TESSDATA_PREFIX")) {
} else {
#ifdef TESSDATA_PREFIX
#define _STR(a) #a
#define _XSTR(a) _STR(a)
#undef _XSTR
#undef _STR
#endif
}
}

// insert code here

// datadir may still be empty:

add into "insert code here" place the next code:

if (getenv("TESSDATA_PREFIX")) {
} else {
// check dir with tessdata
struct stat sb;
if (stat("/usr/share/tesseract-ocr/tessdata", &sb) == 0 && S_ISDIR(sb.st_mode)) {
}
}

and include the next:

#include <sys/stat.h>

Rebuild and reinstall tesseract-ocr:

cd tesseract-3.04.00
make
sudo make install

So, after that, if you have TESSDATA_PREFIX env variable, it will be loaded, and if you have tessdata folder with files in /usr/share/tesseract-ocr/ it will be loaded, otherwise directory with your python example module (./) will be checked for tessdata folder.

Test installed python tesseract using the tests in test folder:

user@server:~/python-tesseract/src/test\$ python test.py
result(ProcessPagesWrapper)= The (quick) [brown] {fox} jumps!
Over the \$43,456.78 <lazy> #90 dog
& duck/goose, as 12.5% of E-mail
from aspammer@website.com is spam.
Der ,,schnelle” braune Fuchs springt
ﬁber den faulen Hund. Le renard brun
«rapide» saute par-dessus le chien
paresseux. La volpe marrone rapida
salta sopra i] cane pigro. El zorro
marrén répido salta sobre el perro
perezoso. A raposa marrom répida
salta sobre 0 C50 preguieoso.

result(ProcessPagesFileStream)= The (quick) [brown] {fox} jumps!
Over the \$43,456.78 <lazy> #90 dog
& duck/goose, as 12.5% of E-mail
from aspammer@website.com is spam.
Der ,,schnelle” braune Fuchs springt
ﬁber den faulen Hund. Le renard brun
«rapide» saute par-dessus le chien
paresseux. La volpe marrone rapida
salta sopra i] cane pigro. El zorro
marrén répido salta sobre el perro
perezoso. A raposa marrom répida
salta sobre 0 C50 preguicoso.

size=156302
retStr length=422
result(ProcessPagesRaw) The (quick) [brown] {fox} jumps!
Over the \$43,456.78 <lazy> #90 dog
& duck/goose, as 12.5% of E-mail
from aspammer@website.com is spam.
Der ,,schnelle” braune Fuchs springt
iiber den faulen Hund. Le renard brun
«rapide» saute par-dessus le chien
paresseux. La volpe marrone rapida
salta sopra i] cane pigro. El zorro
marrén répido salta sobre el perro
perezoso. A raposa marrom rapida
salta sobre 0 C50 preguicoso.

len=156302
result(ProcessPagesBuffer)= The (quick) [brown] {fox} jumps!
Over the \$43,456.78 <lazy> #90 dog
& duck/goose, as 12.5% of E-mail
from aspammer@website.com is spam.
Der ,,schnelle” braune Fuchs springt
iiber den faulen Hund. Le renard brun
«rapide» saute par-dessus le chien
paresseux. La volpe marrone rapida
salta sopra i] cane pigro. El zorro
marrén répido salta sobre el perro
perezoso. A raposa marrom rapida
salta sobre 0 C50 preguicoso.

user@server:~/python-tesseract/src/test\$ python test2.py
The (quick) [brown] {fox} jumps!
Over the \$43,456.78 <lazy> #90 dog
& duck/goose, as 12.5% of E-mail
from aspammer@website.com is spam.
Der ,,schnelle” braune Fuchs springt
ﬁber den faulen Hund. Le renard brun
«rapide» saute par-dessus le chien
paresseux. La volpe marrone rapida
salta sopra i] cane pigro. El zorro
marrén répido salta sobre el perro
perezoso. A raposa marrom répida
salta sobre 0 C50 preguieoso.

88