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).

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

Download leptonica

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

Download tesseract-ocr

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;
pix = pixRead(image);
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");
pix=pixReadStream(fp,0);
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);
pix=pixReadStream(stream,0);
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.
Failed loading language 'eng'
Tesseract couldn't load any languages!
AdaptedTemplates != NULL:Error:Assert failed:in file adaptmatch.cpp, line 174
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) {
    datadir = argv0;
  } else {
    if (getenv("TESSDATA_PREFIX")) {
      datadir = getenv("TESSDATA_PREFIX");
    } else {
#ifdef TESSDATA_PREFIX
#define _STR(a) #a
#define _XSTR(a) _STR(a)
    datadir = _XSTR(TESSDATA_PREFIX);
#undef _XSTR
#undef _STR
#endif
    }
  }

  // insert code here

  // datadir may still be empty:
  if (datadir.length() == 0) {
    datadir = "./";

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

  if (getenv("TESSDATA_PREFIX")) {
      datadir = 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)) {    
      datadir = "/usr/share/tesseract-ocr";
    }
  }

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
fiber 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
fiber 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
fiber 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

R2D2-style sound generator in Python

I've wrote a StarWars' R2-D2-style sound generator in Python. A link to my repo on github is: https://github.com/delimitry/r2d2_sound
To play wav file uses sound-playing interface for Windows (module winsound).

Python 3 check using type([1.0 for i in [1]][0]) is type([1 for i in [1]][0])

Yesterday I've stumbled on a very interesting tweet: "guess why: (by arigo) so a way to know "are we on python 3" is: type([1.0 for i in [1]][0]) is type([1 for i in [1]][0])". Original link is https://twitter.com/fijall/status/675651525000175616

In Python 3 the result is:

>>> type([1.0 for i in [1]][0]) is type([1 for i in [1]][0])
>>> True

but in Python 2:

>>> type([1.0 for i in [1]][0]) is type([1 for i in [1]][0])
>>> False

It is interesting that items' types in Python 3 are both float:

>>> type([1.0 for i in [1]][0]), type([1 for i in [1]][0])
>>> (<class 'float'>, <class 'float'>)

but in Python 2 they are different:

>>> type([1.0 for i in [1]][0]), type([1 for i in [1]][0])
>>> (<type 'float'>, <type 'int'>)

The first part of a secret is that in Python 3 list comprehensions have their own scope, but in Python 2 they haven't. Guido van Rossum wrote about this "dirty little secret" here.

In Python 3 for list comprehensions a special code object listcomp was created.

And the second part of a secret is that both listcomp code objects from this example are located at the same address, because declared on the one line in code.

Here is a bytecode (I've used dis module to get is):

...
 6 LOAD_CONST       1 (<code object <listcomp> at 0x7fd91d983270, file "main.py", line 3>)
...
35 LOAD_CONST       1 (<code object <listcomp> at 0x7fd91d983270, file "main.py", line 3>)
...

List comprehensions [1.0 for i in [1]] and [1 for i in [1]] are on one line have the same address (address of the first listcomp code object), because their listcomp code objects are the same.
Update: As Rhomboid correctly noticed in the discussion on reddit, constants for current code object are stored in dictionary (although displayed as tuple) and the same code object constants are folded.
As hash values for [1.0 for i in [1]][0] and [1 for i in [1]][0] are the same, when addition to the dict is performed - items' values are compared using code_richcompare methods (in this way python dict resolves collisions).

Here is how hash for code object is calculated (from codeobject.c):

static Py_hash_t
code_hash(PyCodeObject *co)
{
    Py_hash_t h, h0, h1, h2, h3, h4, h5, h6;
    h0 = PyObject_Hash(co->co_name);
    if (h0 == -1) return -1;
    h1 = PyObject_Hash(co->co_code);
    if (h1 == -1) return -1;
    h2 = PyObject_Hash(co->co_consts);
    if (h2 == -1) return -1;
    h3 = PyObject_Hash(co->co_names);
    if (h3 == -1) return -1;
    h4 = PyObject_Hash(co->co_varnames);
    if (h4 == -1) return -1;
    h5 = PyObject_Hash(co->co_freevars);
    if (h5 == -1) return -1;
    h6 = PyObject_Hash(co->co_cellvars);
    if (h6 == -1) return -1;
    h = h0 ^ h1 ^ h2 ^ h3 ^ h4 ^ h5 ^ h6 ^
        co->co_argcount ^ co->co_kwonlyargcount ^
        co->co_nlocals ^ co->co_flags;
    if (h == -1) h = -2;
    return h;
}

Here is how code objects are compared (from codeobject.c):

static PyObject *
code_richcompare(PyObject *self, PyObject *other, int op)
{
    PyCodeObject *co, *cp;
    int eq;
    PyObject *res;

    if ((op != Py_EQ && op != Py_NE) ||
        !PyCode_Check(self) ||
        !PyCode_Check(other)) {
        Py_RETURN_NOTIMPLEMENTED;
    }

    co = (PyCodeObject *)self;
    cp = (PyCodeObject *)other;

    eq = PyObject_RichCompareBool(co->co_name, cp->co_name, Py_EQ);
    if (eq <= 0) goto unequal;
    eq = co->co_argcount == cp->co_argcount;
    if (!eq) goto unequal;
    eq = co->co_kwonlyargcount == cp->co_kwonlyargcount;
    if (!eq) goto unequal;
    eq = co->co_nlocals == cp->co_nlocals;
    if (!eq) goto unequal;
    eq = co->co_flags == cp->co_flags;
    if (!eq) goto unequal;
    eq = co->co_firstlineno == cp->co_firstlineno;
    if (!eq) goto unequal;
    eq = PyObject_RichCompareBool(co->co_code, cp->co_code, Py_EQ);
    if (eq <= 0) goto unequal;
    eq = PyObject_RichCompareBool(co->co_consts, cp->co_consts, Py_EQ);
    if (eq <= 0) goto unequal;
    eq = PyObject_RichCompareBool(co->co_names, cp->co_names, Py_EQ);
    if (eq <= 0) goto unequal;
    eq = PyObject_RichCompareBool(co->co_varnames, cp->co_varnames, Py_EQ);
    if (eq <= 0) goto unequal;
    eq = PyObject_RichCompareBool(co->co_freevars, cp->co_freevars, Py_EQ);
    if (eq <= 0) goto unequal;
    eq = PyObject_RichCompareBool(co->co_cellvars, cp->co_cellvars, Py_EQ);
    if (eq <= 0) goto unequal;

    if (op == Py_EQ)
        res = Py_True;
    else
        res = Py_False;
    goto done;

  unequal:
    if (eq < 0)
        return NULL;
    if (op == Py_NE)
        res = Py_True;
    else
        res = Py_False;

  done:
    Py_INCREF(res);
    return res;
}

For the first list comprehension code object variables are the next:

co_name = <listcomp>
co_argcount = 1
co_kwonlyargcount = 0
co_nlocals = 2
co_flags = 83
co_firstlineno = 3
co_code = b'g\x00\x00|\x00\x00]\x0c\x00}\x01\x00d\x00\x00\x91\x02\x00q\x06\x00S' 
co_consts = (1.0,) 
co_names = () 
co_varnames = ('.0', 'i') 
co_freevars = () 
co_cellvars = () 

And for the second one code object variables are the same, except co_consts:

co_consts = (1,)

But as 1.0 == 1, and tuples (1.0,) and (1,) are equal. Therefore Python considers the second code object as duplicate of the first one, and its address is the same. So identity operator "is" returns True for the same objects.

And that is why in Python 3 the next expressions will also be valid.

>>> a = type([1.0 for i in [1]][0]); b = type([1 for i in [1]][0])
>>> print(a, b)
>>> <class 'float'> <class 'float'>

>>> type([1 for i in [1]][0]) is type([True for i in [1]][0])
>>> True

See also: how hash values are calculated in Python read in my article Python hash calculation algorithms

Just for Fun

Recently I've finished a book "Just for Fun: The Story of an Accidental Revolutionary" by Linus Torvalds and David Diamond. One more easy-reading autobiography of Linus Torvalds about Linux creation history, free software, open source, meaning of life and Linus' law of life.
Along with a technical information about Linux and its creation, in the book there are a lot of interesting facts about life in Finland and US, history and reminiscences. By the way, first public version on Linux, which was uploaded to internet is still there: ftp://ftp.funet.fi/pub/Linux/historical/kernel/
I highly recommend it to Linuxoids, IT-people and biography books lover.

Spritesheet cutter

Yesterday in our SPb Python telegram chat a question "how to automatically cut spritesheet into several sprites" was asked. An example of spritesheet image is here: http://www.spriters-resource.com/3ds/animalcrossinghappyhomedesigner/sheet/68350/
Several solutions were proposed, and today I've decided to write my own solution.

So the problem is to cut each sprite out and save to separate file. As a parameter could be passed the color of border. By the way by default it could be fetched from top left pixel. I've coded a Python script that takes input spritesheet image, border color if known, and output folder to save found and cutted out sprites. Output sprite images are grouped by size.

Gracker game

Gracker - it's a good game for beginners to develop skills in searching and exploiting vulnerabilities.
To start the game connect using SSH to level0@gracker.org with password level0.
After solving each level you could read solution (recap) from the author.

I recommend this game if you are interested in CTF and want to improve your skills. Check also smashthestack (if you haven't seen yet).

You can also read about creating this game on the author's site:
http://www.smrrd.de/creating-a-hacking-game-part-1-introduction.html
http://www.smrrd.de/creating-a-hacking-game-part-2-the-system.html