Can Linear Search be optimized when searching for multiple elements in an Unsorted Matrix?

Question

I have a 76800 points Point Cloud. It is organized with a width of 240 and height of 320 and was input from the Kinect.

Now I want to search for around 5000 points in the Point Cloud. Note that I know that they are there, as they are the result of a series of processing (filtering) steps on the same Point Cloud.

I cannot afford to use a kd-tree or sort the matrix in any way, because I would like to know the indices of each point in the cloud.

I'm doing Linear Search at the moment. However, it runs way too slow. Can search be optimized for such a situation.

Also, I'm using the Point Cloud Library for the calculations, if that helps.

Code is as below :

// Search for a Point in the Original Point Cloud 

pcl::PointXYZ searchPoint;
cv::Point imagePoint;

for (pcl::PointCloud<pcl::PointXYZ>::iterator k = pointCloud3D->begin(); k != pointCloud3D->end(); k++) {

    int pointFlag = 0;

    searchPoint.x = k->x;
    searchPoint.y = k->y;
    searchPoint.z = k->z;

    for (size_t i = 0; i < cloud->height; ++i)
    {

        for (size_t j = 0; j < cloud->width; j++) {

            pcl::PointXYZ currentPoint = cloud->at(j, i);

            if (searchPoint.x == currentPoint.x && searchPoint.y == currentPoint.y && searchPoint.z == currentPoint.z)
            {
                pointFlag = 1;
                //cout << " Point found at location: i = " << i << " j = " << j << endl;
                imagePoint.x = i;
                imagePoint.y = j;

            }

            //cout << "Point at : i = " << i << " j =  " << j << "    " << cloud->at(j, i) << endl;

            if (pointFlag == 1) {
                break;
            }

        }

    }