15
3
In this challenge, you need to find a specific pixel within an photograph (taken with a real camera).
You are passed an (R, G, B) tuple and an image, and you need to return a point (x,y) within the image that matches the RGB color given. The image may have multiple points that match the color; you only need to find 1.
The challenge is that you need to do it while reading as few pixels as possible. Your score will be total number of pixels read across all test cases.
If you wish, you can read the entire image into an array of RGB values, as long as you don't do any processing on the pixels. I allow this purely for efficiency purposes. For example, in Python, list(Image.open("image_name+".jpg").convert("RGB").getdata())
is ok.
Hardcoding locations is not allowed. Your algorithm should work well for more than just the test cases listed below. You are not allowed to save data between test cases. I've chosen RGB values that appear infrequently (<10
) in the image (in case that makes a difference for your algorithm). If you are using randomness in your algorithm, please set a seed, so that your score is constant.
Images can be found on Github
Test cases:
image_name:
(r, g, b) [all possible answers]
barn:
(143,91,33) [(887,1096),(2226,1397),(2007,1402),(2161,1508),(1187,1702)]
(53,35,59) [(1999,1260)]
(20,24,27) [(1328,1087),(154,1271)]
(167,148,176) [(1748,1204)]
(137,50,7) [(596,1498)]
(116,95,94) [(1340,1123)]
(72,49,59) [(1344,857),(1345,858),(1380,926),(1405,974),(1480,1117)]
(211,163,175) [(1963,745)]
(30,20,0) [(1609,1462),(1133,1477),(1908,1632)]
(88,36,23) [(543,1494),(431,1575)]
daisy:
(21,57,91) [(1440,1935),(2832,2090),(2232,2130),(1877,2131),(1890,2132)]
(201,175,140) [(1537,1749),(2319,1757)]
(169,160,0) [(2124,759)]
(113,123,114) [(1012,994),(2134,1060),(1803,1183),(1119,1335)]
(225,226,231) [(3207,829),(3256,889),(3257,889),(1434,981),(2599,1118),(2656,1348),(2656,1351)]
(17,62,117) [(2514,3874),(2336,3885)]
(226,225,204) [(3209,812)]
(119,124,146) [(2151,974),(2194,1021),(2194,1022),(2202,1034),(2812,1500)]
(2,63,120) [(2165,3881),(2326,3882),(2330,3882),(2228,3887)]
(200,167,113) [(1453,1759)]
dandelion:
(55,2,46) [(667,825),(668,825)]
(95,37,33) [(1637,1721),(1625,1724),(1405,1753),(2026,2276),(2016,2298)]
(27,41,50) [(1267,126),(424,519),(2703,1323),(1804,3466)]
(58,92,129) [(2213,3274)]
(136,159,105) [(1300,2363),(2123,2645),(1429,3428),(1430,3432),(1417,3467),(1393,3490),(1958,3493)]
(152,174,63) [(2256,2556)]
(78,49,19) [(2128,2836)]
(217,178,205) [(2736,3531)]
(69,95,130) [(870,305),(493,460),(2777,1085),(2791,1292),(2634,3100)]
(150,171,174) [(2816,1201),(2724,2669),(1180,2706),(1470,3215),(1471,3215)]
gerbera:
(218,186,171) [(4282,1342)]
(180,153,40) [(4596,1634),(4369,1682),(4390,1708),(4367,1750)]
(201,179,119) [(4282,1876),(4479,1928)]
(116,112,149) [(5884,252),(4168,371),(4169,372),(4164,384),(5742,576)]
(222,176,65) [(4232,1548)]
(108,129,156) [(5341,3574),(5339,3595),(5302,3734)]
(125,99,48) [(4548,1825),(4136,1932),(5054,2013),(5058,2023),(5058,2035),(5055,2050),(5031,2073)]
(170,149,32) [(4461,1630),(4520,1640)]
(156,185,203) [(3809,108)]
(103,67,17) [(4844,1790)]
hot-air:
(48,21,36) [(1992,1029),(2005,1030),(2015,1034),(2018,1036)]
(104,65,36) [(3173,1890),(3163,1893)]
(169,89,62) [(4181,931),(4210,938),(4330,1046),(4171,1056),(3117,1814)]
(68,59,60) [(1872,220),(1874,220),(1878,220),(1696,225),(3785,429)]
(198,96,74) [(4352,1057)]
(136,43,53) [(1700,931)]
(82,42,32) [(4556,961),(4559,973),(4563,989),(4563,990),(4441,1004),(4387,1126),(4378,1128)]
(192,132,72) [(1399,900),(3105,1822),(3104,1824),(3105,1824),(3107,1826),(3107,1827),(3104,1839),(3119,1852)]
(146,21,63) [(1716,993)]
(125,64,36) [(4332,937)]
in-input:
(204,90,1) [(1526,1997),(1385,2145),(4780,2807),(4788,3414)]
(227,163,53) [(1467,1739),(2414,1925),(2441,2198),(134,2446)]
(196,179,135) [(3770,2740),(1110,3012),(3909,3216),(1409,3263),(571,3405)]
(208,59,27) [(1134,1980),(4518,2108),(4515,2142)]
(149,70,1) [(4499,1790),(2416,2042),(1338,2150),(3731,2408),(3722,2409),(4400,3618)]
(168,3,7) [(987,402),(951,432),(1790,1213),(1790,1214),(1848,1217),(4218,1840),(4344,1870),(1511,1898)]
(218,118,4) [(3857,1701),(1442,1980),(1411,2156),(25,2606)]
(127,153,4) [(3710,2813)]
(224,230,246) [(2086,160),(2761,222),(4482,1442)]
(213,127,66) [(4601,1860),(4515,2527),(4757,2863)]
klatschmohn:
(170,133,19) [(1202,2274),(1202,2275),(957,2493),(1034,2633),(3740,3389),(3740,3391),(3683,3439)]
(162,92,4) [(489,2854)]
(159,175,104) [(3095,2475),(3098,2481)]
(199,139,43) [(1956,3055)]
(171,169,170) [(3669,1487),(3674,1490),(3701,1507)]
(184,115,58) [(1958,2404)]
(228,169,5) [(1316,2336),(1317,2336)]
(179,165,43) [(3879,2380),(1842,2497),(1842,2498)]
(67,21,6) [(1959,2197),(2157,2317),(2158,2317),(2158,2318),(2116,2373)]
(213,100,106) [(1303,1816)]
tajinaste-rojo:
(243,56,99) [(1811,2876),(1668,4141),(2089,4518),(1981,4732),(1659,4778),(2221,5373),(1779,5598),(2210,5673),(2373,5860)]
(147,157,210) [(1835,1028),(1431,3358)]
(114,37,19) [(1792,3572),(1818,3592)]
(108,117,116) [(2772,4722),(1269,5672),(2512,5811),(2509,5830),(2186,5842),(2186,5846),(2190,5851),(2211,5884)]
(214,197,93) [(1653,4386)]
(163,102,101) [(2226,2832),(2213,3683),(1894,4091),(1875,4117)]
(192,192,164) [(2175,2962),(2206,3667),(2315,3858),(1561,3977),(3039,5037),(3201,5641)]
(92,118,45) [(1881,1704),(1983,1877),(2254,2126),(3753,5862),(3766,5883)]
(145,180,173) [(1826,1585)]
(181,124,105) [(1969,3892)]
turret-arch:
(116,70,36) [(384,648),(516,669)]
(121,115,119) [(2419,958)]
(183,222,237) [(172,601),(183,601),(110,611),(111,617)]
(237,136,82) [(2020,282),(676,383),(748,406),(854,482),(638,497),(647,661),(1069,838),(1809,895),(1823,911)]
(193,199,215) [(1567,919),(1793,1047)]
(33,30,25) [(1307,861),(309,885),(1995,895),(504,1232),(2417,1494)]
(17,23,39) [(1745,1033),(788,1090),(967,1250)]
(192,139,95) [(1445,1337)]
(176,125,98) [(1197,1030)]
(178,83,0) [(2378,1136)]
water-lilies:
(86,140,80) [(2322,2855),(4542,3005),(4540,3006),(4577,3019)]
(218,124,174) [(1910,2457)]
(191,77,50) [(2076,1588)]
(197,211,186) [(4402,1894)]
(236,199,181) [(2154,1836)]
(253,242,162) [(1653,1430)]
(114,111,92) [(1936,2499)]
(111,93,27) [(2301,2423),(2127,2592),(2137,2717),(2147,2717)]
(139,92,102) [(1284,2243),(1297,2258)]
(199,157,117) [(3096,993)]
2Is there any correlation in the images we will be tested on? (Can images be noise) If not, surely the only way will be randomly sampling until the correct pixel is chosen? – Blue – 2016-05-24T18:02:31.410
2@muddyfish the images are taken with real cameras of real objects, so there is optimization to be found. Your algorithm should definitely be targeting the images, just not the specific colors I give. – Nathan Merrill – 2016-05-24T18:04:53.697
"while reading as few pixels as possible" how do you determine this? – David – 2016-05-25T03:25:37.133
Due to differences in libraries and languages, I can't define methods that are considered "accessing". What in particular are you thinking about? – Nathan Merrill – 2016-05-25T03:53:05.317
Should a solution output the number of pixels it checked? – trichoplax – 2016-05-25T15:04:49.363
@trichoplax you can certainly output that, if it makes counting the number of pixels it tests easier. For scoring, I'd like algorithms to be deterministic, yes. – Nathan Merrill – 2016-05-25T15:12:01.673
The barn.jpg image is 2600x1733 pixels yet you provide an (x,y) list
[(1096,887),(1397,2226),(1402,2007),(1508,2161),(1702,1187)]
that includes y values larger than 1733. Am I misunderstanding these lists? – Logic Knight – 2016-05-25T16:41:56.987@CarpetPython err....maybe I made them (y,x)? Let me check – Nathan Merrill – 2016-05-25T16:43:57.347
For the
barn
image, I get a pixel list of[(612, 1131), (690, 1155), (784, 1065), (888, 1106), (900, 1729), (903, 1099), (980, 1498), (1581, 1420), (1661, 1529), (1811, 1484), (2140, 1650)]
for the(143, 91, 33)
colour value. At least one of our programs has an error. – Logic Knight – 2016-05-25T16:56:05.737@CarpetPython Mine definitely had an error. I'm not getting that many, but I am printing out (y,x) values instead of (x,y). I've also separately verified that
(887, 1096)
has the correct value of(143, 91, 33)
– Nathan Merrill – 2016-05-25T17:21:11.930I am still having problem replicating your result. My code:
def findpixels(fname): im = Image.open(fname+'.jpg'); px = im.load(); print 'TEST', px[(887, 1096)]
usingbarn
prints(142, 91, 38)
. Could you specify the origin (top left?) you are using? Maybe using 1-based rather than 0-based indexing? – Logic Knight – 2016-05-26T01:45:37.570You need
im.convert('RGB')
– Nathan Merrill – 2016-05-26T01:48:08.393I added
im.convert('RGB')
with same result. Python 2.7.10, Ubuntu Linux 64 bit. Can you verify that my code above (withconvert
) returns the expected colour on your machine? – Logic Knight – 2016-05-26T01:53:06.540Let us continue this discussion in chat.
– Nathan Merrill – 2016-05-26T02:03:47.980