Developers Club geek daily blog

Nonlocal algorithm for smoothing of images

1 year, 4 months ago
Disposal of the image of noise – one of fundamental operations of computer sight. Smoothing algorithms are applied almost everywhere: they can be both independent procedure for improvement of the photo, and the first step for more difficult procedure, for example, for object recognition on the image. Therefore there is a huge set of methods of smoothing, and I would like to tell about one of them differing from the others in good applicability on textures and images with a large number of identical parts.

Under a cat there are a lot of pictures, is accurater with traffic.

Read more »


We mix colors correctly or we optimize AlphaBlend

1 year, 4 months ago
I write multilegal (but not multiplatform, alas, now only windows) a messenger which meanwhile supports only the TOX protocol. But the speech not about a messenger, and about its interface, and if more precisely, about its basic function — AlphaBlend. Yes, I decided to write the GUI bicycle. And what modern GUI without translucent elements and smooth curves? Therefore sharply there was a need to mix images taking into account translucency, i.e. alpha mixing or alpha blending. Fortunately, in the Windows GDI such function is available — AlphaBlend. Works as it is necessary, does what is necessary. But I that still the builder of bicycles, and it became interesting to me whether I will be able to write the same function, but faster. Result of my works under a cat.

Read more »


How to squeeze a flat cat

1 year, 4 months ago
Once during an ice cold winter time … exactly a year ago, we had a nontrivial task. There is a screen on electronic ink, there is a MHz processor 16 (yes, in the built-in electronics, especially ultralow energy consumption, also such meet) and at all there is no memory. Well, i.e. kilobytes of 8 RAM and 256 Flash. Kilobytes, Carle. And it is necessary to push several images in these sad kilobytes 800х600 in four shades of gray. Having quickly multiplied in mind 800 on 600 and on 2 bits per pixel we receive 120 thousand bytes. Does not get a little. It is necessary to squeeze.

So we saw a task: "how to squeeze a flat cat"? Why cat? Yes because on cats tested on what to check black-and-white pictures. Not on dollar banknotes.

Read more »


Magic bitborda and Russian checkers

1 year, 4 months ago
This article — an illustration how bit tricks can be used not only in tasks on interviews, but also at a solution of real tasks. In article the description of one method of fast generation of the courses in the Russian checkers on the basis of magic bitbord (magic bitboard) is given. Bitborda — representation of a position in the form of several unsigned integers which each bit is responsible for a status of some game element, for example cages. Usually use of bitbord gives a prize on performance and on the amount of the used memory, but is connected with more sophisticated programming. At the same time often there is a problem of receipt of value of certain bits in a bitborda, for example, for the subsequent addressing the table. There are two basic approaches to a solution of this task. The first — use and support of excess representation in the form of additional bitbord with renumbering of bits. Such bitborda asto are called rotated. The second method — multiplication by a magic constant, shift and the addressing the table. About such magic bitborda the speech in this article will also go.

Read more »


Investigation materials: "200 years since the birth of Ada Lovelace, the first programmer of mankind"

1 year, 4 months ago
Date: On December 10, 2015, to the head of department No. 8 from the investigator of id1033.
Request type: investigation initiation.
Reason: in connection with suspicious activity of the user of id1596704383 during the period from July 30, 2005 to December 9, 2015, I ask to provide necessary resources in the Form 2 and to give authority according to the Observer-z protocol.
Justification: on the basis of the data obtained from open sources by system of analytics of POPSII-2014 ("Juniper") unique signatures (identifiers from sig8876 on sig8951 are appropriated) testimonial of active collecting and analytics of materials from a network from discharge "Primary source-18" were revealed. According to the order of November 20, 2015 to report without delay on any activity in the reality connected about "Primary source-18", I notify that on December 10 at 16-00 Moscow time, the user of id1596704383 passed to active actions into realities.

I apply the materials intercepted from the user's draft copies on December id1596704383 10, 2015 on the public Habrahabr resource to request.



"I am a devil or an angel" (Ada Lovelace, from the letter to Charles Babbage 1843)

200 years since the birth of Ada Lovelace, the first programmer of mankind

On December 10, 1815 at the poet Byron the daughter who in 1842 in the 27 years wrote the first program for the computer (steam) of Babbage was born.

"The essence and purpose of the machine will change from what information we will enclose in it. The machine will be able to write music, to draw pictures and will show to science such ways which we never and anywhere saw." Ada Lovelace

Ada — the programming language created in 1979 — 1980 during the project by the Ministry of Defence of the USA with the purpose to develop a uniform programming language for the embedded systems (that is management systems the automated complexes functioning in real time). First of all, onboard management systems military facilities (the ships, by airplanes, tanks, rockets, shells, etc.) meant. On December 10, 1980 the language standard was approved.

Read more »


The general scheme of creation of algorithms on the example of Rubik's cube

1 year, 4 months ago
Perhaps, many of readers tried to collect Rubik's cube 3×3 independently, but after a set of unsuccessful attempts or gave up this occupation, or looked for a ready solution. The purpose of this article is to show on the example of Rubik's cube that to find a solution any (from a class of solved) tasks independently, are quite feasible task for everyone if at the same time to be guided by a certain rule set. This solution is received by me in 10 hours, plus this algorithm that it does not demand to remember difficult combinations and a progressive tense to train — to collect by this method only several times enough.

Read more »


Bit magic: receipt of the following lexicographic combination

1 year, 4 months ago

Introduction


Let's allow we have some set which consists of N elements. Let's consider that elements are numbered from zero to N-1. The set of k-element subsets of this set (combinations) can be presented or in the form of an array of indexes of length of k. Or in the form of sequence from N bits in which k from them is set exactly. At Donald Cnut in its TAoCP the algorithm of generation of combinations is given in dictionary order when combinations are set in the form of an array of indexes. We will try to transfer this algorithm to a case of bit masks.

Read more »


Neuronet on Python, part 2: gradient descent

1 year, 4 months ago
Part 1

Give a code at once!


import numpy as np
X = np.array([ [0,0,1],[0,1,1],[1,0,1],[1,1,1] ])
y = np.array([[0,1,1,0]]).T
alpha,hidden_dim = (0.5,4)
synapse_0 = 2*np.random.random((3,hidden_dim)) - 1
synapse_1 = 2*np.random.random((hidden_dim,1)) - 1
for j in xrange(60000):
    layer_1 = 1/(1+np.exp(-(np.dot(X,synapse_0))))
    layer_2 = 1/(1+np.exp(-(np.dot(layer_1,synapse_1))))
    layer_2_delta = (layer_2 - y)*(layer_2*(1-layer_2))
    layer_1_delta = layer_2_delta.dot(synapse_1.T) * (layer_1 * (1-layer_1))
    synapse_1 -= (alpha * layer_1.T.dot(layer_2_delta))
    synapse_0 -= (alpha * X.T.dot(layer_1_delta))

Part 1: Optimization


In the first part I described the basic principles of the return distribution in a simple neuronet. The network allowed us to measure how each of scales of a network makes the contribution to an error. And it allowed us to change weight by means of other algorithm — gradient descent.

The essence of the events is that the return distribution does not enter optimization to network functioning. It moves incorrect information since the end of a network on everything weight inside that other algorithm could already optimize these weight so that they corresponded to our data. But in principle, we have also much other methods of nonlinear optimization which we can use with the return distribution:

Read more »


Whether it is easy to recognize information on the cash card?

1 year, 4 months ago


When we communicate with our customers, being specialists in this area, actively we use the corresponding terminology, in particular the word "recognition". At the same time the listening audience which is brought up on Cuneiform and FineReader often puts in this term a problem of comparison of the cut image section to some number (a character code) which is solved neural network approach today and is not the first stage in a problem of recognition of information. At the beginning it is necessary to localize a card on the image, to find information fields, to execute segmentation on characters. Each listed subtask from the formal point of view is an independent problem of recognition. And if for training of neural networks there are proved approaches and tools, then in problems of orientation and segmentation every time is required an individual approach. If it is interesting to you to learn about approaches which we used at a solution of a problem of recognition of the cash card, then welcome under kat!

Read more »


Under Redis cowl: Hash table (part 2) and List

1 year, 4 months ago
In the first part I told that a hash the table is a few LIST, SET and SORTED SET. You judge — LIST consists of ziplist/linkedlist, SET consists of dict/intset, and SORTED SET is ziplist/skiplist. We already considered the dictionary (dict), and in the second part of article we will consider structure of ziplist — the second most often applicable structure under Redis cowl. Let's look at LIST — the second part of its "kitchen" is simple implementation of the chained list. It is useful to us attentively to consider often mentioned council about optimization a hash of tables through their replacement by lists. Let's consider how many it is required to memory on overhead costs when using these structures what price you pay for economy of memory. Let's sum up the results during the work about a hash as tables, when using the coding in ziplist.

Last time we finished that ziplist of 1,000,000 keys saved with use occupied 16 MB of random access memory whereas in dict the same data demanded 104 MB (ziplist 6 times less!). Let's understand what price:

Read more »