[math-fun] Am I reinventing the wheel?
Dear Math-Funsters, As an aspect of my Soviet retrocomputing recreations, I'm trying to extract the font of the original drum printer used before the beginningt of the infamous IBM-cloning program by the Eastern bloc. The starting point is a fairly low-quality (200dpi) scan of a very low quality printout of the diagonal test: http://besm6.sourceforge.net/static_gallery_mirror/images/21_1.jpg (the printer was ~40 years old and the ribbon likely hasn't been re-inked for many years). The charset is GOST-10859. I was able to segment the image into individual tiles 21x33 px automatically using maxima of average intensities per line and per column, accounting for some downward drift toward the right side and the fact that the glyphs are top-heavy due to dot gain as a result of drum surface velocity orthogonal to hammers' velocity . (~100 C++ lines) Then I've implemented a homebrew super-resolution algorithm by iteratively finding min. mean square error per pixel of the overlapping rectangle (i.e. dividing the sum of squared errors by the number of pixels squared to disfavor matching empty corners with empty corners) of the average collected so far and every tile per codepoint. The non-adaptive mean of all tiles, with some contrast enhancement, is used as the seed for the algorithm. (also ~100 C++ lines). (For better results, tiles are normalized (pnmnorm) and edge-enhanced (pgmenhance or pnmnlfilt) before running the super-resolution, and the result is normalized again. This yielded http://mailcom.com/besm6/acpu/enhanced/ As you can see, the top-heavy dot gain is still quite pronounced (e.g. compare the serifs of I, code 102). Then I tried to experiment with erosion algorithms. Straight erosion (new value of a pixel = max({R-nbrhd(pixel)}) is too strong, eating away weak lines. I've came up with new.val = max(cur. pixel, max({R-nbrhd})+min({R-nbrhd})-mean({R-nbrhd \ cur. pixel})) NB that excluding the current pixel from the mean is important to leave a pixel surrounded by white pixels unchanged. This is a much more gentle erosion than the straight maximum. As an experiment, I've changed the formula to be new.val = max({R-nbrhd})+min({R-nbrhd})-mean({R-nbrhd \ cur. pixel}) to see what happens when it is erosion-dilation indifferent. The result is very amusing: http://ic.pics.livejournal.com/spamsink/7162160/44779/44779_original.gif (iteratively applied to the output of 'pgmramp -e 100 100', R = 2.5, neighborhood size 21 pixels) Is there anything I could have done better? Are there smarter super-resolution algorithms? Erosion algorithms? Am I reinventing the wheel with the "water circles" formula new = max({R-nbrhd})+min({R-nbrhd})-mean({R-nbrhd \ cur}) ? Thanks, Leo
Oh, and in case anyone is interested in playing with the tiles, http://mailcom.com/besm6/acpu/tiles.zip Leo
Suppose we want to estimate the number of positive integers <= x that are products of odd numbers. Piece of cake — these are just the odd numbers themselves, to x/2 is a good asymptotic estimate. Now suppose that for given N in Z+ and q with 0 <= q < N we want to estimate the number #(x; N, q) of positive integers <= x that are product of numbers of the form kN + q, for any various values of k in Z+. Example: #(150; 5, 4) = |{4x4, 4x9, 4x14, 4x19, 4x24, 4x29, 4x34, 9x9, 9x14, 4x4x4, 4x4x9}| = 11 . Heuristically, for each integer X <= x this should be pretty close to the case where q = 0. Which would imply that if we put the integer x in the form: X = L N^s with gcd(L, N) = 1, and s in Z[>=0], then YIKES, this will already involve the partitions P of s each paired with the number of ways L can be factored into |P| factors — counting order but avoiding duplicates . . . added over all X <= x. There must be a better way. —Dan
="Dan Asimov" <asimov@msri.org> ... we want to estimate the number #(x; N, q) of positive integers <= x that are product of numbers of the form kN + q, Heuristically, for each integer X <= x this should be pretty close to the case where q = 0. ...then YIKES... There must be a better way.
If I understand aright, it seems maybe you're worrying yourself overmuch? Note that in the odd numbers example you included all the odd primes, but in your 5N+4 example you omitted the 30 singletons 4, 19, ... 144, 149. These are the most common form of "products", approximately x/N in all. For closer estimates you can indeed add terms for the pairs, triples, etc, and subtract for duplicates, etc. How sharp an approximation do you need?
Yeah, there's no reason to omit those singletons. I don't need any approximation, but would be interested in the best one available. —Dan
On Jun 15, 2016, at 1:50 PM, Marc LeBrun <mlb@well.com> wrote:
="Dan Asimov" <asimov@msri.org> ... we want to estimate the number #(x; N, q) of positive integers <= x that are product of numbers of the form kN + q, Heuristically, for each integer X <= x this should be pretty close to the case where q = 0. ...then YIKES... There must be a better way.
If I understand aright, it seems maybe you're worrying yourself overmuch? Note that in the odd numbers example you included all the odd primes, but in your 5N+4 example you omitted the 30 singletons 4, 19, ... 144, 149. These are the most common form of "products", approximately x/N in all. For closer estimates you can indeed add terms for the pairs, triples, etc, and subtract for duplicates, etc. How sharp an approximation do you need?
participants (4)
-
Dan Asimov -
Dan Asimov -
Leo Broukhis -
Marc LeBrun