PHP image pixelate?

I need to make this effect with php. I know that there is IMG_FILTER_PIXELATE in PHP image filter. But I need it to be smoother and embossed? like in this image:

This effect will make any image uploaded by user become pixelated and the edge of the picture become red (I know IMG_FILTER_EDGEDETECT but I don't know how to use it to change edge color).

I have no idea how to do this.

As the last answer was theoretical and seemed to be not enough, I've created a practical example:
Note: This is far from the "ideal" and perfect pixelate effect function, but it does it's job. Feel free to edit it according to your own needs.

<?php
/* Function to make pixelated images
* Supported input: .png .jpg .jpeg .gif
* 
*
* Created on 24.01.2011 by Henrik Peinar
*/


/*
* image - the location of the image to pixelate 
* pixelate_x - the size of "pixelate" effect on X axis (default 10)
* pixelate_y - the size of "pixelate" effect on Y axis (default 10)
* output - the name of the output file (extension will be added)
*/
function pixelate($image, $output, $pixelate_x = 20, $pixelate_y = 20)
{
    // check if the input file exists
    if(!file_exists($image))
        echo 'File "'. $image .'" not found';

    // get the input file extension and create a GD resource from it
    $ext = pathinfo($image, PATHINFO_EXTENSION);
    if($ext == "jpg" || $ext == "jpeg")
        $img = imagecreatefromjpeg($image);
    elseif($ext == "png")
        $img = imagecreatefrompng($image);
    elseif($ext == "gif")
        $img = imagecreatefromgif($image);
    else
        echo 'Unsupported file extension';

    // now we have the image loaded up and ready for the effect to be applied
    // get the image size
    $size = getimagesize($image);
    $height = $size[1];
    $width = $size[0];

    // start from the top-left pixel and keep looping until we have the desired effect
    for($y = 0;$y < $height;$y += $pixelate_y+1)
    {

        for($x = 0;$x < $width;$x += $pixelate_x+1)
        {
            // get the color for current pixel
            $rgb = imagecolorsforindex($img, imagecolorat($img, $x, $y));

            // get the closest color from palette
            $color = imagecolorclosest($img, $rgb['red'], $rgb['green'], $rgb['blue']);
            imagefilledrectangle($img, $x, $y, $x+$pixelate_x, $y+$pixelate_y, $color);

        }       
    }

    // save the image
    $output_name = $output .'_'. time() .'.jpg';

    imagejpeg($img, $output_name);
    imagedestroy($img); 
}


pixelate("test.jpg", "testing");


?>

This is the example function to create pixelated effect on images. Here's an example results of using this function:
Original:

Pixelated 5px:

Pixelated 10px:

Pixelated 20px: