A probabilistic image analysis problem and random linear equations

Consider an image that depicts two objects. Two randomly selected pixels of the image are examined. A decision system emits “0” if both pixels belong to the same object, otherwise it emits “1”. Image noise and imperfections in the decision system render the outputs unreliable, that is, there will be pairs of pixels incorrectly classified. The question we address is the following: as the result of successive comparisons accumulate, can one reliably decide which pixels belong to each object? We present and discuss results that shed some light on this problem and discuss it from different angles.