Lower memory usage

[StefanoD]

Using numpy.lexsort() results in very high memory usage. If an image is too big, this can result in a signal 9 abort.
If someone really needs this implementation for production, than this issue has to be addressed.

Pull requests are welcome.

[vitorsr]

(Sorry for responding to an older thread.)

A clever trick I've used in the past is to put all the information in a single string, sortable hash, or even in distinct binary or decimal ranges in the order we'd like lexicographically sorted. Then,
.argsort() that array.

Note that finfo("float64").eps is 2e-16 (lots of room to spare). Equivalently, a 64-bit unsigned integer can hold 8 8-bit unsigned integers if you stack them along 8-bit-sized bands.

Anyways, thanks for this implementation. I will work on my own. I'll put a link to your repository as credit for the assistance. (I'd fork but I'll probably rewrite the history, which misses the point of forking. I'm still deciding.)

[StefanoD]

@vitorsr
Thanks for your insights and your credits! ☺
Actually, I implemented this algorithm only to proof to myself that I actually understood it and it was just for fun.
Currently I have no desire to rework the library. But pull requests are of course welcome, if there is any interest.
Of course you can start from scratch in your own repository. ☺

[coderforlife]

@vitorsr I have a library for this and it uses essentially what you say, however it is slightly more complex than that, but yeah, it works. With the additional fact that numpy now uses radix sort, it is quite a bit faster. See https://github.com/coderforlife/histmatch.

[StefanoD]

@coderforlife
Thx for your comment.
Your link is not working.
Why did you look for an another lib when your lib did the work? Just curious. 🙂

[coderforlife]

I was actually searching for the asymptotic memory usage of lexsort (I think the search was simply lexsort memory usage) and this issue was the first search result! I didn't even search for exact histogram equalization, just found this one randomly.

The link didn't work since it was private since it includes some thing I am working on publishing a paper about. However, at this point the paper is being submitted very soon so not much of a risk.