2
$\begingroup$

Was playing with some pictures and ran the ruby code below. The code reads an input image using the ImageMagick library, gets an array of pixels, re-sorts the pixels and then writes out an image with the re-sorted pixels and using the same dimensions as the original image.

require 'rmagick'

include Magick

img = ImageList.new("images/test-image.jpg")
pixels = img.get_pixels(0,0,img.columns,img.rows)

# Sort pixels by total intensity

# https://apidock.com/ruby/Array/sort
# The block must implement a comparison between a and b and
# * <0 when b follows a,
# * 0 when a and b are equivalent, 
# * >0 when a follows b

# The result is not guaranteed to be stable.
# When the comparison of two elements returns 0, the order of the elements is unpredictable.

pixels = pixels.sort {|p| p.red + p.green + p.blue}

out_img = Magick::Image.new(img.columns, img.rows)
out_img.store_pixels(0,0, img.columns, img.rows, pixels)
out_img.write("images/test-image-out.jpg")

I was trying to sort the pixels by the sum of their RGB values, but for that I should have used sort_by instead of sort on the pixels array.

So the pixels are not being sorted by the sum of their RGB values, but I don't know how they are being sorted either, and why when sorted that way they generate the pattern on the sample pictures below.

I included the short documentation of the Ruby Array.sort method to help understand with what's going on.

Original picture: enter image description here

Picture with re-ordered pixels (using pixels.sort {|p| p.red + p.green + p.blue} or pixels = pixels.sort {|a,b| 1}): enter image description here

Following suggestions from @OlliNiemitalo and @xiota, if instead of doing pixels = pixels.sort {|p| p.red + p.green + p.blue} the code does pixels = pixels.sort {|a,b| 1}, the output is the same (the weird repetition pattern).

When doing pixels = pixels.sort {|a,b| b <=> a} though, the output looks like the picture below.

enter image description here

Below is what happens when running (0..1023).to_a.sort{|p| 1} on the irb (ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin16]). Can't really tell what the pattern is just by looking at the numbers.

irb(main):009:0> (0..1023).to_a.sort{|p| 1}
=> [22, 512, 0, 513, 1, 514, 2, 515, 3, 516, 4, 517, 25, 518, 29, 519, 33, 520, 40, 41, 275, 787, 147, 659, 403, 915, 83, 595, 339, 723, 211, 851, 467, 979, 51, 563, 307, 627, 179, 691, 371, 755, 115, 819, 435, 883, 243, 947, 499, 1011, 15, 547, 291, 579, 163, 611, 323, 643, 99, 675, 355, 707, 195, 739, 387, 771, 67, 803, 419, 835, 227, 867, 451, 899, 131, 931, 483, 963, 259, 995, 18, 523, 7, 539, 283, 555, 155, 571, 299, 587, 91, 603, 315, 619, 171, 635, 331, 651, 59, 667, 347, 683, 187, 699, 363, 715, 107, 731, 379, 747, 203, 763, 395, 779, 43, 795, 411, 811, 219, 827, 427, 843, 123, 859, 443, 875, 235, 891, 459, 907, 75, 923, 475, 939, 251, 955, 491, 971, 139, 987, 507, 1003, 267, 1019, 271, 527, 27, 535, 279, 543, 151, 551, 287, 559, 87, 567, 295, 575, 159, 583, 303, 591, 55, 599, 311, 607, 167, 615, 319, 623, 95, 631, 327, 639, 175, 647, 335, 655, 30, 663, 343, 671, 183, 679, 351, 687, 103, 695, 359, 703, 191, 711, 367, 719, 63, 727, 375, 735, 199, 743, 383, 751, 111, 759, 391, 767, 207, 775, 399, 783, 11, 791, 407, 799, 215, 807, 415, 815, 119, 823, 423, 831, 223, 839, 431, 847, 71, 855, 439, 863, 231, 871, 447, 879, 127, 887, 455, 895, 239, 903, 463, 911, 47, 919, 471, 927, 247, 935, 479, 943, 135, 951, 487, 959, 255, 967, 495, 975, 79, 983, 503, 991, 263, 999, 511, 1007, 143, 1015, 36, 1023, 145, 525, 273, 529, 35, 533, 277, 537, 149, 541, 281, 545, 85, 549, 285, 553, 153, 557, 289, 561, 53, 565, 293, 569, 157, 573, 297, 577, 89, 581, 301, 585, 161, 589, 305, 593, 17, 597, 309, 601, 165, 605, 313, 609, 93, 613, 317, 617, 169, 621, 321, 625, 57, 629, 325, 633, 173, 637, 329, 641, 97, 645, 333, 649, 177, 653, 337, 657, 9, 661, 341, 665, 181, 669, 345, 673, 101, 677, 349, 681, 185, 685, 353, 689, 61, 693, 357, 697, 189, 701, 361, 705, 105, 709, 365, 713, 193, 717, 369, 721, 39, 725, 373, 729, 197, 733, 377, 737, 109, 741, 381, 745, 201, 749, 385, 753, 65, 757, 389, 761, 205, 765, 393, 769, 113, 773, 397, 777, 209, 781, 401, 785, 5, 789, 405, 793, 213, 797, 409, 801, 117, 805, 413, 809, 217, 813, 417, 817, 69, 821, 421, 825, 221, 829, 425, 833, 121, 837, 429, 841, 225, 845, 433, 849, 45, 853, 437, 857, 229, 861, 441, 865, 125, 869, 445, 873, 233, 877, 449, 881, 73, 885, 453, 889, 237, 893, 457, 897, 129, 901, 461, 905, 241, 909, 465, 913, 13, 917, 469, 921, 245, 925, 473, 929, 133, 933, 477, 937, 249, 941, 481, 945, 77, 949, 485, 953, 253, 957, 489, 961, 137, 965, 493, 969, 257, 973, 497, 977, 49, 981, 501, 985, 261, 989, 505, 993, 141, 997, 509, 1001, 265, 1005, 20, 1009, 81, 1013, 28, 1017, 269, 1021, 37, 522, 82, 524, 272, 526, 146, 528, 274, 530, 521, 532, 276, 534, 148, 536, 278, 538, 84, 540, 280, 542, 150, 544, 282, 546, 52, 548, 284, 550, 152, 552, 286, 554, 86, 556, 288, 558, 154, 560, 290, 562, 16, 564, 292, 566, 156, 568, 294, 570, 88, 572, 296, 574, 158, 576, 298, 578, 54, 580, 300, 582, 160, 584, 302, 586, 90, 588, 304, 590, 162, 592, 306, 594, 8, 596, 308, 598, 164, 600, 310, 602, 92, 604, 312, 606, 166, 608, 314, 610, 56, 612, 316, 614, 168, 616, 318, 618, 94, 620, 320, 622, 170, 624, 322, 626, 26, 628, 324, 630, 172, 632, 326, 634, 96, 636, 328, 638, 174, 640, 330, 642, 58, 644, 332, 646, 176, 648, 334, 650, 98, 652, 336, 654, 178, 656, 338, 658, 23, 660, 340, 662, 180, 664, 342, 666, 100, 668, 344, 670, 182, 672, 346, 674, 60, 676, 348, 678, 184, 680, 350, 682, 102, 684, 352, 686, 186, 688, 354, 690, 34, 692, 356, 694, 188, 696, 358, 698, 104, 700, 360, 702, 190, 704, 362, 706, 62, 708, 364, 710, 192, 712, 366, 714, 106, 716, 368, 718, 194, 720, 370, 722, 10, 724, 372, 726, 196, 728, 374, 730, 108, 732, 376, 734, 198, 736, 378, 738, 64, 740, 380, 742, 200, 744, 382, 746, 110, 748, 384, 750, 202, 752, 386, 754, 42, 756, 388, 758, 204, 760, 390, 762, 112, 764, 392, 766, 206, 768, 394, 770, 66, 772, 396, 774, 208, 776, 398, 778, 114, 780, 400, 782, 210, 784, 402, 786, 31, 788, 404, 790, 212, 792, 406, 794, 116, 796, 408, 798, 214, 800, 410, 802, 68, 804, 412, 806, 216, 808, 414, 810, 118, 812, 416, 814, 218, 816, 418, 818, 44, 820, 420, 822, 220, 824, 422, 826, 120, 828, 424, 830, 222, 832, 426, 834, 70, 836, 428, 838, 224, 840, 430, 842, 122, 844, 432, 846, 226, 848, 434, 850, 12, 852, 436, 854, 228, 856, 438, 858, 124, 860, 440, 862, 230, 864, 442, 866, 72, 868, 444, 870, 232, 872, 446, 874, 126, 876, 448, 878, 234, 880, 450, 882, 46, 884, 452, 886, 236, 888, 454, 890, 128, 892, 456, 894, 238, 896, 458, 898, 74, 900, 460, 902, 240, 904, 462, 906, 130, 908, 464, 910, 242, 912, 466, 914, 6, 916, 468, 918, 244, 920, 470, 922, 132, 924, 472, 926, 246, 928, 474, 930, 76, 932, 476, 934, 248, 936, 478, 938, 134, 940, 480, 942, 250, 944, 482, 946, 48, 948, 484, 950, 252, 952, 486, 954, 136, 956, 488, 958, 254, 960, 490, 962, 78, 964, 492, 966, 256, 968, 494, 970, 138, 972, 496, 974, 258, 976, 498, 978, 14, 980, 500, 982, 260, 984, 502, 986, 140, 988, 504, 990, 262, 992, 506, 994, 80, 996, 508, 998, 264, 1000, 510, 1002, 142, 1004, 21, 1006, 266, 1008, 19, 1010, 50, 1012, 24, 1014, 268, 1016, 32, 1018, 144, 1020, 38, 1022, 270, 531]

As per @xiota's additional suggestion, running pixels = pixels.sort {|a,b| a <=> b} creates a sort of "reverse" image of the one generated with pixels = pixels.sort {|a,b| b <=> a} (notice the change of a and b's position when being compared). Here's the output:

Another image

$\endgroup$
  • $\begingroup$ I wonder if you get the same result from pixels = pixels.sort {|p| 1}. $\endgroup$ – Olli Niemitalo Aug 14 at 11:33
  • $\begingroup$ @OlliNiemitalo yes, I get the same result using that line :) $\endgroup$ – Nico Brenner Aug 14 at 17:02
  • $\begingroup$ What happens if you put pixels = pixels.sort {|a,b| 1} ? What about pixels = pixels.sort {|a,b| b <=> a} ? $\endgroup$ – xiota Aug 14 at 21:08
  • $\begingroup$ @xiota thank you for the help in trying to figure this out. This line pixels = pixels.sort {|a,b| 1} generates the same pattern as pixels.sort {|p| p.red + p.green + p.blue} in the output picture. The line pixels = pixels.sort {|a,b| 1} generates a different pattern (you can see the corresponding picture on the question now). $\endgroup$ – Nico Brenner Aug 14 at 21:32
  • $\begingroup$ @OlliNiemitalo figured out that the pattern is generated by the quicksort algorithm implementation of ruby. but I'm still unable to conceptually explain/understand how it works in relation to what the picture looks like. What would be a more semantical (less procedural) explanation? What additional meaning could be assigned to this? $\endgroup$ – Nico Brenner Aug 14 at 21:35
3
$\begingroup$

In support of Comparable mixin, a default <=> or spaceship operator for pixels is defined in the function Pixel_spaceship in rmpixel.c. However, in your use of the sort method, you define your own code block that overrides the <=> operator, and yours takes a single argument rather than two which would be correct, so the definition is broken and will not work correctly in sorting. The undefined sorting result will depend on the sorting algorithm used. Ruby sorts arrays using the Quicksort algorithm, which is a divide-and-conquer algorithm, dividing the problem into progressively smaller sub-problems. You can see this behavior in your output image, which I think is an artifact from using Quicksort with a broken <=> operator.

On some computing platforms, Ruby uses the platform's Quicksort implementation (see rb_sort in array.c and ruby_qsort in util.c), so the undefined results also vary depending on the platform, as demonstrated in comments to the question. See util.c for Ruby's own Quicksort implementation. For someone who wants to take the time to tackle this, you'd replace each <=> comparison by constant 1, and simplify the code.

Let's plot the question's ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin16] platform "sorted" 0..1023 test data (labeled Source #) as function of position, using | markers to more clearly see step sizes:

enter image description here

Ignoring small-scale detail, as if we were looking at a very large image from a very large distance, we can deduce that with $n=0,1,2,3,\ldots$, each $2$nd $1/(n+2)$ part of the output image is an additive mixture of scaled parts of the input image:

  • the $2$nd $1/2$ part of the image enlarged by a factor of $2^{-n}$ with mixing weight $1/2$,
  • the $2$nd $1/4$ part of the image enlarged by a factor of $2^{1-n}$ with mixing weight $1/4$,
  • the $2$nd $1/8$ part of the image enlarged by a factor of $2^{2-n}$ with mixing weight $1/8$,
  • the $2$nd $1/16$ part of the image enlarged by a factor of $2^{3-n}$ with mixing weight $1/16$,
  • ... (until the part size goes to zero).

Here, enlarged by a factor of $2^x$ means that if $x < 1$ then the image part in question is reduced in size by factor $2^{-x}$ and replicated (tiled), and if $x > 1$, then the image part is enlarged by factor $2^x$ and the $2^x$ enlarged $1/2^x$ sub-parts are additively mixed with equal weight $1/2^x$.

The small-scale detail ignored in this analysis is the interlacing, which from a large distance looks like additive mixing. Also some unexplained details that don't seem to scale with the data size are ignored.

Here is a Python script (sorry, I don't know Ruby) that reproduces most of the aesthetic qualities of the picture, not by using the above analysis but by mimicking the interlacing in the plot above:

from PIL import Image
import requests
from io import BytesIO

response = requests.get("https://i.stack.imgur.com/T520A.jpg")
img = Image.open(BytesIO(response.content))
pix = img.load()
w, h = img.size
pix_flat = []
for y in range(h):
    for x in range(w):
        pix_flat.append(pix[x, y])

for y in range(h):
    for x in range(w):
        if (x > 0 or y > 0):  # Do not touch pix[0, 0]
            i = x + w*y     
            j = i
            while j < w*h//2:
                j *= 2
            k = i
            while k & 1:
                j >>= 1
                k >>= 1
            pix[x, y] = pix_flat[j]

img.save("output.jpg", "JPEG")

Result #1:

enter image description here

We can get rid of the vertical striping by replacing the interlacing by weighted summation in a linear color space, assuming that the source image is in sRGB color space, in Python:

from PIL import Image
import requests
from io import BytesIO

response = requests.get("https://i.stack.imgur.com/T520A.jpg")
img = Image.open(BytesIO(response.content))
pix = img.load()
w, h = img.size

# These originate from https://stackoverflow.com/questions/34472375/linear-to-srgb-conversion
def srgb2lin(s):  
    if s <= 0.0404482362771082:
        lin = s / 12.92
    else:
        lin = pow(((s + 0.055) / 1.055), 2.4)
    return lin

def lin2srgb(lin):
    if lin > 0.0031308:
        s = 1.055 * (pow(lin, (1.0 / 2.4))) - 0.055
    else:
        s = 12.92 * lin
    return s

pix_flat_lin = []
for y in range(h):
    for x in range(w):
        pix_flat_lin.append([srgb2lin(pix[x, y][k]/255) for k in range(3)])

for y in range(h):
    for x in range(w):
        if (x > 0 or y > 0):  # Do not touch pix[0, 0]
            i = x + w*y     
            j = i
            while j < w*h//2:
                j *= 2
            pixel_lin = [pix_flat_lin[j][k] * 0.5 for k in range(3)]
            j >>= 1
            m = 0.25
            while j:
                pixel_lin = [pixel_lin[k] + pix_flat_lin[j][k] * m for k in range(3)]
                j >>= 1
                m *= 0.5
            pix[x, y] = tuple([int(round(lin2srgb(pixel_lin[k])*255)) for k in range(3)])
    print(str(y+1)+"/"+str(h))

img.save("output2.jpg", "JPEG")

Result #2:

enter image description here

This still has the horizontal stripes.

$\endgroup$
  • $\begingroup$ That's a very well researched and insightful answer! And makes a lot of sense that the sorting algorithm itself is being "reflected"/"imprinted" in the picture. Cool, thank you :) $\endgroup$ – Nico Brenner Aug 14 at 5:58
  • $\begingroup$ So, if you wanted to generate the picture with the artifacts on purpose, without using the broken Quicksort, how would you do it? $\endgroup$ – Nico Brenner Aug 14 at 6:26
  • $\begingroup$ Do you mean to include also the small-scale details of the artifact (also in the bottom half)? That would sound difficult. $\endgroup$ – Olli Niemitalo Aug 14 at 6:37
  • 1
    $\begingroup$ You could "sort" (0..width*height-1), and then put the pixels to the places pointed out by that list. $\endgroup$ – Olli Niemitalo Aug 16 at 3:57
  • 1
    $\begingroup$ That is correct, at least if attempting the reconstruction by pixel reordering. Neither is result #1 guaranteed to not duplicate pixels. I was aiming for similar aesthetics only. $\endgroup$ – Olli Niemitalo Aug 16 at 6:49
2
$\begingroup$

I'm not a Ruby programmer, so there will be a lot of handwaving in this answer. If you are particularly concerned about skipped details, you'll have to look in the Ruby source code.

  • In array.sort {|a,b| a <=> b}, the sort method of array is being called with a block { ... }. The arguments used by the block are given by |a,b|. The comparison "spaceship" operator is a <=> b. It returns 1, 0, -1, depending on whether a is "larger" than b.

  • In the code you wrote, pixels = pixels.sort {|p| p.red + p.green + p.blue}, you are adding three positive integers. The result is another positive integer that is interpreted as 1. So sort behaves as if the comparison is always evaluating as "larger". Instead of separating, or recombining, values into arrays based on size, as you would expect sort to behave, they are split based on the order in which they appeared in the original array.

    This causes smaller copies of the original image to be created when every other pixel is put into a different array. This is repeated for every array, until we're down to pairs. The arrays are then merged back together to get the result you see. (This is a major handwaving checkpoint. You'll have to look at the sort implementation to see exactly how the arrays are merged.)

  • The output ends up looking the same as either of the following. It doesn't matter if you have |p| or |a,b| because the arguments are ignored.

    pixels = pixels.sort {|p| 1}
    pixels = pixels.sort {|a,b| 1}
    

    weird

  • To get the result you're seeking, you can use:

    pixels = pixels.sort {|a,b| (a.red + a.green + a.blue) <=> (b.red + b.green + b.blue)}
    

    desired result

  • The default Pixel_spaceship operator that Olli Niemitalo mentions is different from the function you intend, so pixels = pixels.sort {|a,b| a <=> b} has a striped appearance. Using b <=> a will reverse the order.

    a <=> b

$\endgroup$
  • $\begingroup$ pixels = pixels.sort {|a,b| (a.red + a.green + a.blue) <=> (b.red + b.green + b.blue)} generates this image i.stack.imgur.com/1WwpX.jpg $\endgroup$ – Nico Brenner Aug 15 at 8:04
  • $\begingroup$ added the image for pixels = pixels.sort {|a,b| a <=> b} on the question. It looks like a "reverse" or flipped version of the previous one (b <=> a) $\endgroup$ – Nico Brenner Aug 15 at 8:12
  • $\begingroup$ This answers what puzzled me about the output you were getting. If you want more details about what's happening inside sort, looks like Olli Niemitalo is willing to get into it. $\endgroup$ – xiota Aug 15 at 8:36
  • $\begingroup$ @xiota not really :D but I did analyze the effective result. $\endgroup$ – Olli Niemitalo Aug 15 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.